Algorithms for Next Generation Networks

by Graham Cormode (Editor), Marina Thottan (Editor)

Overview

Data networking now plays a major role in everyday life and new applications continue to appear at a blinding pace. Yet we still do not have a sound foundation for designing, evaluating and managing these networks.

This book covers topics at the intersection of algorithms and networking. It builds a complete picture of the current state of research on Next Generation Networks and the challenges for the years ahead. Particular focus is given to evolving research initiatives and the architecture they propose and implications for networking.

Topics: Network design and provisioning, hardware issues, layer-3 algorithms and MPLS, BGP and Inter AS routing, packet processing for routing, security and network management, load balancing, oblivious routing and shastic algorithms, network coding for multicast, overlay routing for P2P networking and content delivery.

This timely volume will be of interest to a broad readership from graduate students to researchers looking to survey recent research its open questions.

Product Details

ISBN-13:	9781848827646
Publisher:	Springer London
Publication date:	03/04/2010
Series:	Computer Communications and Networks
Edition description:	2010
Pages:	462
Product dimensions:	6.10(w) x 9.25(h) x 0.04(d)

Table of Contents

Part I Network Design

1 Design for Optimizability: Traffic Management of a Future Internet Jiayue He Jennifer Rexford Mung Chiang 3

2 Valiant Load-Balancing: Building Networks That Can Support All Traffic Matrices Rui Zhang-Shen 19

3 Geometric Capacity Provisioning for Wavelength-Switched WDM Networks Li-Wei Chen Eytan Modiano 31

4 Spectrum and Interference Management in Next-Generation Wireless Networks Harish Viswanathan Sivarama Venkatesan 47

5 Cross-Layer Capacity Estimation and Throughput Maximization in Wireless Networks V.S. Anil Kumar Madhav V. Marathe Srinivasan Parthasarathy 67

6 Resource Allocation Algorithms for the Next Generation Cellular Networks David Amzallag Danny Raz 99

7 Ethernet-Based Services for Next Generation Networks Enrique Hernandez-Valencia 131

8 Overlay Networks: Applications, Coexistence with IP Layer, and Transient Dynamics Chen-Nee Chuah Ram Keralapura 157

Part II Network Operations

9 Hash-Based Techniques for High-Speed Packet Processing Adam Kirsch Michael Mitzenmacher George Varghese 181

10 Fast Packet Pattern-Matching Algorithms Fang Yu Yanlei Diao Randy H. Katz T.V. Lakshman 219

11 Anomaly Detection Approaches for Communication Networks Marina Thottan Guanglei Liu Chuanyi Ji 239

12 Model-Based Anomaly Detection for a Transparent Optical Transmission System Thomas Bengtsson Todd Salamon Tin Kam Ho Christopher A. White 263

13 In-Network Monitoring Danny Raz Rolf Stadler Constantine Elster Mads Dam 287

14 Algebraic Approaches for Scalable End-to-End Monitoring and Diagnosis Yao Zhao Yan Chen 319

Part III Emerging Applications

15 Network Coding and Its Applications in Communication Networks Alex Sprintson 343

16 Next Generation Search Debora Donato Aristides Gionis 373

17 At the Intersection of Networks and Highly Interactive Online Games Grenville Armitage 403

18 Wayfinding in Social Networks David Liben-Nowell 435

Index 457

Editorial Reviews

From the reviews:

"Understanding the science behind the networks of today is the necessary foundation for making significant contributions to the rapid evolution of next generation networks. This timely book comprised of chapters from authoritative experts provides an excellent overview of algorithms that form the basis of next generation communication networks. It covers problems ranging in scope from physical layer issues to the design of next generation applications. I strongly recommend this valuable book as essential reading for students, practitioners and researchers who are actively engaged in creating the emerging next generation communication networks."

Debasis Mitra, Bell Laboratories

"A few months ago a colleague at Georgia Tech asked me ‘Which are the top-10 most significant algorithms that have been developed by networking research in the last decade?’ This book would provide an excellent answer. Covering a wide range of topics from the entire spectrum of networking research, this book is highly recommended for anyone that wants to become familiar with the ‘network algorithmics’ state-of-the-art of the evolving Internet."

Constantine Dovrolis, Georgia Institute of Technology

“This book addresses issues surrounding the evolution of the Internet as it matures in the early 21st century. … The focus on algorithms to augment and in some cases replace historical ad hoc designs is timely. … book should be useful to researchers in the field who seek to establish firm foundations for their work. … Each paper has extensive references, and the book has an adequate index. It mercifully steers clear of policy considerations such as Net neutrality.” (J. S. Edwards, ACM Computing Reviews, August, 2010)

From the Publisher