# 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