Advances in Oblivious Network Routing

Routing is a central topic in networking since it determines the connectivity between users. Recently, with the growing use of the Internet to carry real-time multimedia traffic, it has also become important that routing accounts for the quality-of-service needs of applications and customers. A research problem of much current interest is traffic-oblivious routing that ensures that the network provides the needed quality-of-service despite uncertain knowledge of the carried traffic. Traffic-oblivious routing has the potential to make the Internet far more more reliable and robust in the face of dynamically changing traffic patterns. This will facilitate the migration of many more services over the public Internet carried over the ubiquitous Internet Protocol (IP). We have already seen the emergence of many of these services, including VoIP (voice-over-IP), peer-to-peer file sharing, video streaming, and IPTV. The bandwidth requirements of these applications are not only high but show marked variations, both temporally and geographically, compared to traditional telephony voice traffic patterns. This has reduced the time-scales at which traffic changes dynamically, making it impossible to extrapolate seamlessly, it is imperative that the Internet routing infrastructure be reliable and robust in the face of highly unpredicatable and rapidly varying traffic patterns. Oblivious routing due to its lack of dependence on accurate traffic knowledge has hence become an important topic of research. The objective of the book is to describe recent developments in oblivious routing. There are two broad methodologies for routing network traffic in an oblivious manner without detailed knowledge of the traffic matrix. Both these approaches will be covered in the book. The first is Direct Routing which routes packets along fixed paths, from ingress to egress, that are picked to optimize some objective (e.g., maximize network throughput) for traffic that satisfies rudimentary ingress-egress capacity constraints, The second approach is Two- Phase Routing whose origins can be traced back to Valiant's randomized scheme for communication among parallel processors interconnected in a hypercube topology.