Optimal routing in networks with flow-controlled virtual channels

Abstract

Packet switching networks with flow-controlled virtual channels are naturally modeled as queueing networks with closed chains. Available network design and analysis techniques, however, are mostly based upon an open-chain queueing network model. In this paper, we first examine the traffic conditions under which an open-chain model accurately predicts the mean end-to-end delays of a closed-chain model having the same chain throughputs. We next consider the problem of optimally routing a small amount of incremental traffic corresponding to the addition of a new virtual channel (with a window size of one) to a network. We model the new virtual channel as a closed chain. Existing flows in the network are modeled as open chains. An optimal routing algorithm is then presented. The algorithm solves a constrained optimization problem that is a compromise between problems of unconstrained individual-optimization and unconstrained network-optimization.