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.

Abstract:

    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 PDF (222k). Expanded version with application to tori in Postscript (203k) or PDF (226k).

This page's URL is /~black/Papers/soda.html

Updated Wed Jul 10 10:26:39 2002

Go to Black's papers or NIST home page.