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

"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.