Oblivious Network Routing
Algorithms and Applications
176 pp., 6 x 9 in,
- Published: May 1, 2015
- Publisher: The MIT Press
Versatile solutions to routing network flows in unpredictable circumstances, presenting both mathematical tools and applications.
Our increasingly integrated world relies on networks both physical and virtual to transfer goods and information. The Internet is a network of networks that connects people around the world in a real-time manner, but it can be disrupted by massive data flows, diverse traffic patterns, inadequate infrastructure, and even natural disasters and political conflict. Similar challenges exist for transportation and energy distribution networks. There is an urgent need for intelligent and adaptable routing of network flows, and a rich literature has evolved that treats “oblivious network design.” This book offers novel computational schemes for efficiently solving routing problems in unpredictable circumstances and proposes some real world applications for them. The versatile routing schemes mathematically guarantee long-term efficiency and are most appropriate for networks with non-deterministic (or oblivious) current and past states.
After an introduction to network design and the importance of routing problems, the book presents mathematical tools needed to construct versatile routing schemes, emphasizing the role of linked hierarchical data structures, both top-down and bottom-up. It then describes two important applications of versatile routing schemes: a secure model for congestion-free content-centric networks (which will play a key role in the future of the Internet) and a novel approach for the distribution of green power resources on a smart electricity grid.
This book presents fundamental contributions to the theory and practice of routing problems in oblivious circumstances. It invents computational tools for the generation of versatile solutions, produces rigorous stochastic analysis, employs techniques addressing the future of the Internet, and presents pioneering oblivious routing approaches for content-centric and smart energy distribution grids.
Vahid Tarokh, Area Dean for Electrical Engineering and Perkins Professor of Applied Mathematics, Harvard University
This timely book makes an important contribution to the understanding of efficient routing schemes for handling the amounts of data and the range of uses of the Internet today. Highly recommended for the practitioner who needs effective solutions to real problems.
John Hopcroft, Cornell University
Network routing, whether of data or power, is central to our society. The book succeeds in simplifying a very sophisticated subject. The clarity of its exposition and its choice and sequencing of topics are masterful.
Silvio Micali, Ford Professor of Engineering, MIT
This book develops a novel computational theory to efficiently solve routing problems in unpredictable circumstances. This is supplemented with real-world applications. The book, which is very well written, provides a complete and rigorous treatment of oblivious routing problems. Its quantification of the developed computational theory for oblivious routing is a major strength.
Sartaj Sahni, Distinguished Professor of Computer and Information Sciences and Engineering, University of Florida