The goal of this project is to improve the isochronous throughput of packet switched networks.


Network throughput is determined by congestion. Congestion is determined by topology and statistical blocking.

Some network topologies are blocking. One path blocks one or more other paths. This blocking multiplies the effect of the traffic. As an example, two paths through an 8 port Butterfly or Banyan network can be shown to block the other 6 paths. This results in an effective factor of three increase in the traffic. The best way to get around this problem is to add topological redundancy.

Congestion is also determined by statistical blocking. Packets have a certain probability of colliding at the same router output port. This probability decreases with the router fanout and increases geometrically with each router traversed. The larger the router fanout and the fewer routers traversed, the larger the probability is that a packet will traverse the network without a collision, the smaller the congestion, and the larger the throughput of the network. As an example, a packet has a (1/2) to the 4th power probability of traversing a 16 port Butterfly network without a collision. Given a uniform distribution of traffic such a network could maintain 1/16 of its theoretical throughput before congestion.

We are currently generalizing this work to arbitrary networks.

This work is being supported by DARPA under contract MDA972-99-C-008.