CHAPTER 9
Oblivious Routing
Oblivious routing, in which we route packets without regard for the state of the net-
work, is simple to implement and simple to analyze. While adding information about
network state can potentially improve routing performance, it also adds considerable
complexity and if not done carefully can lead to performance degradation.
The main tradeoff with oblivious routing is between locality and load balance. By
sending each packet first to a random node and from there directly to its destination,
Valiant’s randomized routing algorithm (Section 9.1) exactly balances the load of
any traffic pattern. However, this load balance comes ...
Get Principles and Practices of Interconnection Networks now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
