Worst-case Traffic


Recently, the application space of interconnection networks has started expanding to areas such as IP router fabrics and I/O interconnects (e.g. the Avici TSR and InfiniBand).  Unlike traditional processor-memory interconnection, the worst-case throughput of an interconnection network becomes an important design consideration.  For example, in the IP router application, little can be said about the arrival process of incoming packets.  At the same time, there is no path to quickly apply backpressure to slow this flow of packets.  So, if the incoming packet rate exceeds the worst-case throughput of the router, packets may be dropped.  Obviously, a system designer would like to be able to characterize this worst-case behavior.

In this work, we develop a polynomial-time algorithm to find the exact worst-case throughput for most oblivious routing functions on an arbitrary network topology.  An oblivious routing function is one in which a packet's path through the network depends only on its source and destination.  We show several key results using this algorithm:

  • Our algorithm offers a significant increase in accuracy over existing techniques for characterizing the worst-case throughput.

  • Traditional believes about routing function design, such as increased route diversity leads to higher throughput, do not always hold when considering the worst-case.


Back to main page

For problems or questions regarding this web contact btowles@cva.stanford.edu.
Last updated: May 13, 2002.