12:45PM, Thursday, February 10th 2005.
Gates 104

Making Intra-Domain Routing Robust to Changing and Uncertain Traffic Demands and Network Failures

Edith Cohen
AT&T Research

About the talk:
Two important components of Intra-domain traffic engineering are understanding the traffic demands and configuring the routing protocols.  These two components are inter-linked: With an accurate view of traffic, one can optimize the utilization of the network through configuration of routing protocols.

Traffic demand values, however, are dynamic and illusive.  The performance of a routing that is optimized for a given set of demands can quickly deteriorate when traffic demands change.  Even if current demands are known, frequent changes in the routing can lead to performance degradation.  It is therefore desirable to obtain a routing configuration that is ``robust'' to variations in demands.

We develop novel algorithms for constructing optimal robust routings and for evaluating the performance of any given routing on loosely constrained rich sets of traffic demands.  We show that for a diverse collection of ISP networks our optimal robust routing obtains a nearly optimal utilization on all applicable traffic matrices, even when designed with a fairly limited knowledge of the applicable traffic demands.

We extend the robust routing scheme to handle Link and node failures.  Routing restoration, which computes new routes that avoid failed links, involves tradeoffs between efficient use of network resources, complexity of the restoration strategy and disruption to network traffic.  We develop algorithms for computing optimal restoration paths and a methodology for evaluating the performance guarantees of routing under failures.  We then study the performance of route restoration on a diverse collection of ISP networks where the performance of routing with restoration paths under failures is compared to the best possible performance on the failed network.  We conclude that with careful selection of restoration paths one can obtain restoration strategies that retain nearly optimal performance on the failed network while minimizing disruptions to traffic flows that did not traverse the failed parts of the network.

The talk is based on joint work with David Applegate and Lee Breslau published in SIGCOMM 2003 and SIGMETRICS 2004.

About the speaker:
Edith Cohen is a researcher at AT\&T Labs-Research. She did her undergraduate and Masters studies at Tel-Aviv University, and received a Ph.D. in Computer Science from Stanford University in 1991. She joined AT\&T Labs (then, AT\&T Bell Laboratories) in 1991.  During 1997, she was in UC Berkeley as a visiting professor. Her research interests include design and analysis of algorithms, combinatorial optimization, Web performance, networking, and data mining.