Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Queueing Theory Analysis of Greedy Routing on Arrays and Tori

Mor Harchol and Paul E. Black

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

http://www.eecs.berkeley.edu/Pubs/TechRpts/1993/CSD-93-756.pdf

We apply queueing theory to derive the probability distribution on the queue buildup associated with greedy routing on an n by n array and an n by n torus of processors. We assume packets continuously arrive at each node of the array or torus according to a Poisson Process with 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 exponentially distributed with mean 1.

To analyze the queue size in steady-state, we formulate both these problems as equivalent Jackson queueing network models. With this model, determining the probability distribution on the queue size at each node involves solving O(n^4) simultaneous linear equations. However, we eliminate the need to solve these simultaneous equations by deriving a very simple formula for the total arrival rates and for the expected queue sizes in the case of greedy routing.

This simple formula shows that in the case of the n x n array, the expected queue size at a node increases as the Euclidean distance of the node from the center of the array decreases. Furthermore, in the case of the n x n torus, the probability distribution on the queue size is identical for every node.

We also translate our results about queue sizes into results about the average packet delay.


BibTeX citation:

@techreport{Harchol:CSD-93-756,
    Author = {Harchol, Mor and Black, Paul E.},
    Title = {Queueing Theory Analysis of Greedy Routing on Arrays and Tori},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1993},
    Month = {Jun},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1993/6299.html},
    Number = {UCB/CSD-93-756},
    Abstract = {We apply queueing theory to derive the probability distribution on the queue buildup associated with greedy routing on an <i>n</i> by <i>n</i> array and an <i>n</i> by <i>n</i> torus of processors. We assume packets continuously arrive at each node of the array or torus according to a Poisson Process with 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 exponentially distributed with mean 1. <p>To analyze the queue size in steady-state, we formulate both these problems as equivalent Jackson queueing network models. With this model, determining the probability distribution on the queue size at each node involves solving <i>O</i>(<i>n</i>^4) simultaneous linear equations. However, we eliminate the need to solve these simultaneous equations by deriving a very simple formula for the total arrival rates and for the expected queue sizes in the case of greedy routing. <p>This simple formula shows that in the case of the <i>n</i> x <i>n</i> array, the expected queue size at a node increases as the Euclidean distance of the node from the center of the array decreases. Furthermore, in the case of the <i>n</i> x <i>n</i> torus, the probability distribution on the queue size is identical for every node. <p>We also translate our results about queue sizes into results about the average packet delay.}
}

EndNote citation:

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