Mor Harchol-Balter and Paul E. Black,
Queuing Analysis of Oblivious Packet-Routing Networks,
Proceedings of the 5th ACM-SIAM
Symposium on Discrete Algorithms (SODA '94), Washington, D.C., USA
(January 1994), ACM, 1994, pages 583-592.
We consider the problem of determining the probability distribution on
the queue sizes in a general oblivious packet-routing network. We
assume packets continuously arrive at each node of the network
according to a Poisson process with rate lambda. We also assume that
an edge may be traversed by only one packet at a time, and the time to
traverse an edge is an exponentially distributed variable with mean 1.
We show that the queuing-theoretic solution to the problem requires
solving a large system of simultaneous equations.
We present a simple combinatorial formula which represents the
solution to the system of queuing equations. This combinatorial
formula is especially simple and insightful in the case of greedy
routing to random destinations.
We use the formula to obtain results including: the probability
distribution on the queue sizes, the expected queue sizes, and the
expected packet delay (all as a function of lambda) in the case of an
array network and a torus network with greedy randomized routing.
Get the paper in
Postscript (190k) or
Expanded version with application to tori in
Postscript (203k) or
This page's URL is /~black/Papers/soda.html
Wed Jul 10 10:26:39 2002
by Paul E. Black
Black's papers or
NIST home page.