Advances in Oblivious Routing of Internet Traffic

Abstract Routing is a central topic in networking since it determines the connectiv- ity between users. Recently, with growing use of the Internet for a wide variety of bandwidth intensive applications, including peer-to-peer and on-demand/real-time multimedia, it has also become important that routing accounts for the quality-of- service needs of applications and users. A research problem of much current in- terest is traffic-oblivious routing for ensuring that the network provides the needed quality-of-service despite uncertain knowldge of the carried traffic. Oblivious rout- ing involves using pre-determined paths to route between each ingress-egress node in the network (typically an Internet domain) that do not change with changing traffic patterns. By removing the need to detect in traffic in real-time or reconfigure the network in response to it, significant simplification in network man- agement/operations and associated reduction in costs can be achieved. Moreover, oblivious routing has the potential to make the Internet much more robust and pre- dictable in the face of rapidly varying and unpredctable traffic patterns. Theoretical advances in the area have shown that oblivious routing can provide these benefits without compromising capacity efficiency. We survey recent advances in oblivious routing with a view towards its application in (intra-domain) Internet routing.