|
|
|
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:
Publications:
|
|
For problems or questions regarding this web contact btowles@cva.stanford.edu.
|
