Walking the tightrope

Current intra-domain Traffic Engineering (TE) relies on offline methods, which use long term average traffic demands. It cannot react to realtime traffic changes caused by BGP reroutes, diurnal traffic variations, attacks, or flash crowds. Further, current TE deals with network failures by pre-computing alternative routings for a limited set of failures. It may fail to prevent congestion when unanticipated or combination failures occur, even though the network has enough capacity to handle the failure.This paper presents TeXCP, an online distributed TE protocol that balances load in realtime, responding to actual traffic demands and failures. TeXCP uses multiple paths to deliver demands from an ingress to an egress router, adaptively moving traffic from over-utilized to under-utilized paths. These adaptations are carefully designed such that, though done independently by each edge router based on local information, they balance load in the whole network without oscillations. We model TeXCP, prove the stability of the model, and show that it is easy to implement. Our extensive simulations show that, for the same traffic demands, a network using TeXCP supports the same utilization and failure resilience as a network that uses traditional offline TE, but with half or third the capacity.