~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
CCS Seminar
Friday - December 14, 2007
12:00 noon
Physics Research Building - Room 595
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Yelena Rykalova
Electrical & Computer Engineering
Boston University


"QUEUES, LATENCY AND CRITICAL PHENOMENA IN INTERCONNECTION NETWORKS: 
BEYOND JACKSON’S THEOREM"

The analysis of the network performance as networks of queues is a 
well-known approach. We apply this method to the multiprocessor network 
with characteristics, which are different of whose discussed in previous 
works. We consider networks modeled as a ring and as a 2-dimensional 
toroidal square lattice of nodes. Each node has two or, respectively, 
four output buffers and a local processor that generates messages with 
certain probability per clock cycle per output port. Once a buffer is 
not empty, the corresponding output port sends out exactly one message 
every clock cycle.

First, we consider homogeneous networks. The buffers capacity is assumed 
to be infinite and every node generates the messages with the same 
probability l. We derive explicit analytical expressions for the queue 
length distribution, the average number of messages in buffers, and the 
latency (average delay) using the assumption that the distribution of 
network states has a product form. It is shown that the network 
experiences a phase transition from equilibrium to the saturation 
regime, and the critical exponent is equal to 1. The critical network 
load is found and shown to be inversely proportional to the distance 
between the source and destination. Empirical results obtained by 
extensive simulations demonstrate an excellent agreement with 
theoretical predictions and validate the assumption of independent 
queues (analogous to the mean field theory in statistical physics).

Next, we obtain and discuss theoretical and numerical results for 
networks with strong correlation between node states: networks with 
limiting buffers, networks where probability to generate messages is 
changing depending on the message flow to a particular router. Both 
networks with heterogeneous activity and those with finite buffers 
displays a behavior completely different from that of homogeneous 
activity networks with infinite buffers, once the load approaches the 
critical value. The emergence of the structure of two phases in a 
dynamic equilibrium with each other, similar to systems in statistical 
physics, and non-trivial values of the critical exponent show that we 
deal with a collective phenomenon, which cannot be accurately described 
within the framework of the “mean field” theory. Thus, the “independent 
queues” hypothesis is not valid anymore, and we find ourselves beyond 
the realm of Jackson’s theorem. An accurate theoretical description of 
such systems seems to be a very challenging problem.



Cheryl Endicott
Administrative Assistant
Center for Computational Science
3 Cummington Street
Boston, MA 02215
tel:617-358-1470
fax:617-358-2487
http://ccs.bu.edu

Created for the Boston University/SCV Projects Page.

Created by The CoCoBoard.