MIT Department of Electrical Engineering & Computer Science

Some Simple Ideas for Modeling Packet Interactions in Complex Data Networks

Balaji Prabhakar
MIT, EECS and LIDS

Monday, November 24, 1997
4:00 PM (refreshments 3:45)
Edgerton Hall, Room 34-101
EECS Colloquium

Abstract

The "state" of a data network at any time is captured by the occupancy and the contents of the buffers in the network. The buffers reside in the switching or routing elements and their occupancy influences such crucial performance measures as packet delays, packet loss probabilities and throughput. The traditional approach for estimating, controlling and optimizing the usage of buffers in a network has been to assume Poisson or Poisson-like arrivals and exponential service times.

However, these Poisson models are increasingly inadequate to model today's networks. Further, the very act of queueing packet streams at a switch causes them to interact and changes arrival statistics at subsequent switching nodes. Consequently there has been a need for a theory of more general queueing systems, especially ones which model packet interactions. With the aid of simulations various conjectures about the probable behavior of general queueing systems have been made.

In this talk I will trace the origin of these conjectures and show how they are resolved by using techniques from the field of Interacting Particle Systems. It turns out that the key to understanding what happens to a packet stream as it goes through a queue is to look at the "fixed points" of the queue. For example, the fact that a Poisson process is a fixed point for an exponential server queue tells a lot about what such a server would do to a non-Poisson input. I will discuss the implications for network design of modeling packet interations using an intuitively simple notion of "flow entropy."