Transcript Valiant Load-Balancing in Backbone Networks

Designing a Predictable
Backbone Network
Rui Zhang-Shen
[email protected]
http://www.stanford.edu/~rzhang
Clean Slate Seminar — Feb 13, 2006
US Backbone Networks:
Observations





A few tens of “core” nodes,
Each aggregating traffic for a region,
Interconnected by an increasingly rich mesh of high-capacity
long-haul optical trunks
 Robustness
 Load-balancing
Low utilization—links over-provisioned for
 Uncertainty in traffic matrix the network is designed for
 Headroom for future growth
 Granularity of link capacity
 Prepare to take over when links or routers fail
 Minimize congestion and delay variation
Efficiency sacrificed for robustness and flexibility
How flexible are networks today?
What fraction of allowable traffic matrices can they support?
Abilene
25% Over Prov.: 0.025%
50% Over Prov.: 0.66%
AT&T
25% Over Prov.: 0.0006%
50% Over Prov.: 0.15%
Verio
25% Over Prov.: 0.0004%
50% Over Prov.: 1.15%
Sprint
25% Over Prov.: 0.0003%
50% Over Prov.: 0.06%
Verio, AT&T and Sprint topologies courtesy of RocketFuel
Our Approach

Assume we know or estimate the traffic
entering and leaving each Regional Network



Requires only local knowledge of users and
market estimates
Connect regional nodes by a logical full-mesh
Use Valiant Load Balancing (VLB) over whole
network
Valiant Load-Balancing
r
1
42
2r/N
2
3
N
…
r
4
r
r
VLB: Flow View
2
1
3
……
4
N
Characteristics of VLB

Flexible


Simple




Each packet needs look up only once in the backbone
Each flow is evenly split over N paths
Routing decisions are local
Robust


Can support all traffic matrices
Can recover quickly from failures
Efficient


Proof: Requires minimum total capacity for supporting all
traffic matrices
To tolerate k failures, each link needs 2r /(N-k)
Implications of VLB

Network design made simpler




Max. utilization under normal condition = 
Max. utilization under up to k failures = 
Output: capacity required on each link
Routers can be simpler


One IP lookup per packet in network
No dynamic rerouting requirement
What About Delay?

Routing can be adaptive

Only load-balance when needed

There are “express paths”
Delay is bounded
Delay variations are reduced

Delay is less important than delay variations


Questions & Comments?
VLB:
A Network Design Framework



No need to split traffic evenly
Associate pi with node i, where pi ≥0, i pi=1
Load balance pi of each flow to node i


Previous example: pi =1/N, 8 i
Can formulate optimization problems to
determine pi


Can be applied to heterogeneous networks
Can introduce constraints (capacity, etc.)
Heterogeneous Network

Minimize maxi j; j i cij /ri

Answer:
Future Directions


Interconnection of multiple VLB networks
Relationship of physical topology and logical
topology