Y. Rykalova, L.B. Levitin, and R. Brower (USA)

Queueing networks, network performance, latency, network saturation, critical phenomena in networks.

A multiprocessor networks modeled as a ring and as a 2 dimensional toroidal square lattice of nodes are considered. Each node has 2 or, respectively, 4 output buffers of infinite capacity and a local processor that generates messages with 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. We derive explicit analytical expressions for the queue length distribution, the average number of messages in buffers, and the latency (average delay). 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.

Important Links:

Go Back