overview - What is TeXCP?
papers - TeXCP documents
related research - other traffic engineering projects
people - who are we?
funding - who sponsors TeXCP?


Overview

Internet users frequently experience congestion and service disruption. These problems are mostly caused by inflexibility in Internet routing, which maps a communication to a single potentially-suboptimal path, typically for as long as the path is available, irrespective of its congestion. Recent studies show that better routing options usually exist- either an alternative path with higher bandwidth or a few paths which in aggregate, provide more throughput and higher availability. Adaptively routing traffic over the better paths can provide a major performance gain and crucial fallback options during DoS attacks or network outages.

There are two ways to implement adaptive multipath routing: end-based adaptation and network-based adaptation. End-based routing adaptation includes overlay routing, inverse multiplexing, and adaptive multihoming. Encouraged by its ease of deployment, much recent research has explored end-based routing adaptation.

This project focuses on the less explored topic of network-based adaptive multipath routing, where an administrative domain uses multiple paths to deliver traffic demands between any two points, adaptively balancing the load across these paths. This is a traffic engineering (TE) problem but differs from prior TE work which consists mostly of static load balancers or offline multipath route optimizers. In contrast, this project advocates an adaptive, distributed, multipath routing approach that rebalances load in realtime to protect the network from congestion caused by attack traffic, flash crowds, BGP transients, or link failures.

This project focuses on network-based adaptive multipath routing for the following reasons. First, measurements indicate that network-based adaptive routing can produce a big throughput and availability gain. Past research shows that ISP networks have very high path diversity and that over 40% of the bottlenecks are intra-AS. Network-based multipath routing can exploit the path diversity inside an AS to avoid these bottlenecks. Second, network-based adaptive routing is easier to stabilize than end-based adaptive routing. Without some form of coordination, a congested path causes everyone to move traffic to the secondary path (or paths) potentially causing the first path to become underutilized and the secondary path to be congested. As a result, everyone moves traffic back to the first path and the cycle repeats. In an autonomous system (AS), all nodes are under the same administration and can be loosely coordinated so that the aggregate traffic moved from one path to another cannot destabilize the network. Control theory tools used in XCP are applicable in this context. Third, network-based and end-based multipath adaptation are complementary. Both should be studied to understand their interaction and tradeoffs.

TeXCP overview

TeXCP has many potential benefits to an ISP:
  • Avoiding congestion within the network - balanced load, small queues, no packet losses
  • Quick reaction to changes in traffic demands, DDoS Attacks, Link Failures and Traffic Spikes
  • Easy to deploy - no need to measure or estimate traffic matrices

Papers

Talks

Resources

People

Faculty/Collaborators:  Dina Katabi   Bruce Davie   Anna Charny  

Graduate Students:  Srikanth Kandula  Asfandyar Qureshi  Shan Sinha 

Related research

Traffic Engineering Projects

  • MATE solves the online adaptive routing problem in a distributed fashion to minimize the total latency over all ingress-egress pairs. [Orig ps] [Local Mirror] [IETF Draft]

    There are significant differences between TeXCP and MATE. First, TeXCP reacts to traffic changes upto two order of magnitudes faster than MATE. Second, while TeXCP minimizes the maximum utilization in the network, MATE minimizes the sum of the delays. Current ISP networks are significantly overprovisioned and hence the delays are usually constant and equal to the propagation delay. This limits the benefit of MATE's load balancing techniques to relatively congested networks. Finally, MATE does not require adding functionality to the core routers making it easier to deploy. On the other hand, TeXCP uses low frequency probe packets that are processed by core routers on the slow path.

  • Optimizing IGP Weights Another approach to multipath routing is to optimize IGP weights. @AT&T Research [ps] [local ps], @Sprint [ps].

    The weight optimizer computes off-line a set of link weights that minimize congestion in the shortest path routing for a given traffic matrix. Although, the problem of finding the optimal weight setting is NP-hard, a few heuristics can be used to find near-optimal solutions.

Traffic Matrix Estimation

  • Yin Zhang's information-theoretic approach to traffic matrix estimation, AT&T's Tomo-gravity project [html]
  • Deriving Traffic Demands for Operational IP Networks [ps]
  • Traffic Matrix Estimation: Existing Techniques and New Directions [pdf], Sprint's IPMON project [html]


NMS @ MIT CSAIL

M. I. T. Computer Science and Artificial Intelligence Laboratory 200 Technology Square Cambridge, MA 02139 USA