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.


Towles, Brian and Dally, William J. , "Worst-case Traffic for Oblivious Routing Functions," (preliminary version) ACM Symposium on Parallel Algorithms and Architectures (SPAA), Winnipeg, Manitoba, Canada, August, 2002.

Towles, Brian and Dally, William J. , "Worst-case Traffic for Oblivious Routing Functions", Computer Architecture Letters, Vol. 1, Feb. 2002.

Towles, Brian, "Finding Worst-case Permutations for Oblivious Routing Algorithms," Concurrent VLSI Architecture Technical Report 121, December 2001.

Back to main page

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