Mor Harchol and Paul E. Black

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-93-746
May 1993

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/CSD-93-746.pdf

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.

BibTeX citation:

@techreport{Harchol:CSD-93-746,
    Author = {Harchol, Mor and Black, Paul E.},
    Title = {Queueing Theory Analysis of Greedy Routing on Square Arrays},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1993},
    Month = {May},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/6279.html},
    Number = {UCB/CSD-93-746},
    Abstract = {We apply queueing theory to derive the probability distribution on the queue buildup associated with greedy routing on an <i>n</i> x <i>n</i> 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. <p>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 <i>O</i>(<i>n</i>^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. <p>Lastly, we use this simple formula to prove that the expected queue size at a node of the <i>n</i> x <i>n</i> array increases as the Euclidean distance of the node from the center of the array decreases.}
}

EndNote citation:

%0 Report
%A Harchol, Mor
%A Black, Paul E.
%T Queueing Theory Analysis of Greedy Routing on Square Arrays
%I EECS Department, University of California, Berkeley
%D 1993
%@ UCB/CSD-93-746
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/6279.html
%F Harchol:CSD-93-746