We apply queueing theory to derive the probability distribution on the queue buildup associated with greedy routing on an
n x
n array of processors. We assume packets continuously arrive at each node of the array with Poisson rate lambda and have random destinations. We assume an edge may be traversed by only one packet at a time and the time to traverse an edge is Poisson distributed with mean 1.
To analyze the queue size in steady-state, we formulate the problem into an equivalent Jackson queueing network model. It turns out that determining the probability distribution on the queue size at each node is then just a matter of solving O(n^4) simultaneous linear equations which determine the total arrival rate at each node and then plugging these arrival rates into a short formula for the probability distribution given by the queueing theory. However, we even eliminate the need to solve these simultaneous equations by deriving a very simple formula for the total arrival rates in the case of greedy routing.
Lastly, we use this simple formula to prove that the expected queue size at a node of the n x n array increases as the Euclidean distance of the node from the center of the array decreases.
Title
Queueing Theory Analysis of Greedy Routing on Square Arrays
Published
1993-05-20
Full Collection Name
Electrical Engineering & Computer Sciences Technical Reports
Other Identifiers
CSD-93-746
Type
Text
Extent
16 p
Archive
The Engineering Library
Usage Statement
Researchers may make free and open use of the UC Berkeley Library’s digitized public domain materials. However, some materials in our online collections may be protected by U.S. copyright law (Title 17, U.S.C.). Use or reproduction of materials protected by copyright beyond that allowed by fair use (Title 17, U.S.C. § 107) requires permission from the copyright owners. The use or reproduction of some materials may also be restricted by terms of University of California gift or purchase agreements, privacy and publicity rights, or trademark law. Responsibility for determining rights status and permissibility of any use or reproduction rests exclusively with the researcher. To learn more or make inquiries, please see our permissions policies (https://www.lib.berkeley.edu/about/permissions-policies).
