Transcript No Slide Title

An Approach to Alleviate Link
Overload as Observed on an
IP Backbone
Tuesday, April 1st
Infocom 2003
Sundar Iyer1,2, Supratik Bhattacharrya2,
Nina Taft2, Christophe Diot2
1Stanford University, 2ATL SprintLabs
Infocom 2003
Contents
1.
Introduction
2.
Pathology of link overload
3.
Alleviate overload - deflection routing
4.
Performance analysis
Infocom 2003
2
There should be no link overload

Overload: More than 50% utilization

IP backbones are



Overprovisioned  low average utilization
Have multiple paths
Routing algorithms


balance load across multiple shortest paths
should reduce the likelihood of overload
Infocom 2003
3
But there is link overload

Shortest path routing



Unpredictable traffic


Short term load fluctuations e.g. hotspots
Failure


puts load on a small set of equal cost shortest paths
causes unequal use of link capacity
Link failures, fiber cuts, network maintenance
Hard to predict all factors apriori
Infocom 2003
4
Why bother about link overload?



Operators upgrade persistently overloaded
links
 Peaks in link utilization  cannot increase
average utilization
Severe link overload causes packet drops
Interactive, real-time applications make it
mandatory to overcome overload
Infocom 2003
5
Contents
1.
Introduction
2.
Pathology of link overload
3.
Alleviate overload - deflection routing
4.
Performance analysis
Infocom 2003
6
Methodology

Measurement of data from the Sprint
backbone





Analyzed 138 backbone links for 9 months
SNMP link utilization data polled every 5 minutes
The link utilization is an exponentially weighted
moving average (EWMA)
Measurements under-estimate overload
Short term fluctuations are missed
Infocom 2003
7
Maximum load
Maximum Load

Observation 1: There is always some overloaded link
Infocom 2003
8
Contribution of links to overload
Non-Overloaded links
Overloaded links

Observation 2: Most of the links are not overloaded
Infocom 2003
9
Types of link overload
Periods of link overload


Observation 3: Two types — Persistent and temporary overload
Observation 4: Often just 1-2 links are simultaneously overloaded
Infocom 2003
10
Causes of temporary link overload
Link Utilizations

Observation 5: Link failures cause temporary overload

Observation 6: Fiber cuts cause severe overload
Infocom 2003
11
Contents
1.
Introduction
2.
Pathology of link overload
3.
Alleviate overload - deflection routing
4.
Performance analysis
Infocom 2003
12
The case for deflection routing

Previous techniques




useful for long term overload
change normal functioning of the network
useful when overload is common
We observe that link overload





is relatively rare (0.1% of the time on any link)
are typically caused due to link failures/maintenance
lasts for minutes-hours on average
occurs on maximum of 1-2 links simultaneously
can be easily overcome by deflecting packets
Allow normal network operation most of the time
Infocom 2003
13
Problem

Problem:


How can we design a simple, stateless, loop-free
deflection algorithm to overcome link overload?
Theorem 1: (sufficiency)

Any deflection algorithm which deflects packets
with “strictly decreasing cost” is loop-free
Infocom 2003
14
Explanation of Theorem 1

A packet is forwarded from node s to d according
to the strictly decreasing cost criteria as follows
1.
If shortest path not overloaded
Forward the packet on the shortest path with cost C
2.
If link to neighboring node n is not overloaded
Forward the packet to n if n’s cost to d is  C
3.
Else
Forward the packet on the shortest path
Infocom 2003
15
Intuition for Theorem 1
Yes
20
30
Router: n1
10
10
Router: s
20
15
Router: n2
25
Router: d
No
Router: n3


Loop-free
deflection
routing:
Shortest path
routing:



forward packet on the shortest path
the sequence of costs to a destination is strictly decreasing
we do not consider the cost of reaching the deflection node
Infocom 2003
16
Problem

Problem:


Can we always find loop-free deflection paths
according to the strictly decreasing cost criteria?
Theorem 2: (sufficiency)

A network with redundant equal length paths
always has a loop-free deflection path if the link
weights are in a ratio 1 + 1/(d-1), where d is the
diameter of the network
Infocom 2003
17
Requirements

Intuition:





All link weights are in the range [Wmin ,Wminx]
the minimum cost of the shortest path is dWmin
the maximum cost of the deflection path is (d-1)Wminx
(d-1)Wminx  dWmin  x  1 + 1/(d-1)
Criteria for Theorem 2



Need equal length shortest paths between any two nodes
Weights need to be within a bounded ratio “1 + 1/(d-1)”
The diameter d of the network should be small
Infocom 2003
18
Topology Considerations
Inter-PoP Network
NYC-1
SJ-1
PoP
SJ-2
San JoseSJ-4
SJ-3
PoP
NYC-4
New York
NYC-2
CHI-1
CHI-2
PoP
CHI-4
Chicago
NYC-3
CHI-3
Small diameter, d=3
Redundant equal
length paths are
guaranteed
ANA-1
RTP-1
FW-1
PoP
ANA-4
Anaheim
ANA-2
PoP
FW-4
FW-2
Fort-Worth
ANA-3
RTP-2
PoP
RTP
RTP-4
RTP-3
FW-3
Large inter-POP
weights are within ratio
Infocom 2003
19
Topology Considerations
Complete Network
NYC-1
SJ-1
NYC-3
CHI-4
CHI-2
SJ-3
NYC-4
NYC-2
CHI-1
SJ-4
SJ-2
Perfect
Mesh in
PoPs
CHI-3
Diameter
is larger
Redundant
equal length
paths not
guaranteed
ANA-1
RTP-1
FW-1
ANA-4
ANA-2
FW-4
FW-2
RTP-3
ANA-3
Large
Inter-POP
Weights
Infocom 2003
RTP-4
RTP-2
FW-3
Small (wmax)
Intra-POP
Weights
20
Problem

Inter-PoP Network: PoPs as a single ‘logical node’
+ All criteria for theorem 2 are satisfied

The complete network
- Equal length redundant paths does not exist
- Diameter of the network is not small
- Maximum intra-PoP link weight wmax is unrelated and very
small compared to inter-PoP link weights

Problem
- Cannot satisfy theorem 2 for the complete network
Infocom 2003
21
Practical deflection routing algorithm
Solution: Clumping a PoP

A packet is forwarded from node s to d as follows,
where wgain = wmax
1.
If shortest path not overloaded
Forward the packet on the shortest path (with cost C)
2.
If link to neighboring node n is not overloaded
Forward the packet to n if n’s cost to d is  C – wgain
3.
InterPoP
Else if link to (intra-PoP) node n’ is not overloaded
IntraPoP
Forward the packet if its cost to d is  C + wmax
4.
Forward the packet on the shortest path
Infocom 2003
22
Theorem 3

Theorem 3:


Comments



The practical deflection routing algorithm has no
inter-PoP loops
The sequence of costs strictly decreases across PoPs
This is in keeping with the idea of ‘PoPs’
Link failures

The algorithm is extended by setting wgain = (n-1)wmax
Infocom 2003
23
Contents
1.
Introduction
2.
Pathology of link overload
3.
Alleviate overload - deflection routing
4.
Performance analysis
Infocom 2003
24
Simulations

Simulation parameters





14 node inter-PoP network and 4-5 node intra-PoP network
Estimated traffic matrix with gravity models & link
measurements
Deflection threshold was set to 45%
Deflection based on fast EWMA
Simulations for link failures and fiber cuts
Infocom 2003
25
Link overload due to a fiber cut

Deflection routing decreases the maximum load amongst all
links in the backbone
Infocom 2003
26
Conclusions

Deflection routing algorithm





Note



Based on practical considerations and overload pathology
Exploits backbone architecture, meshed topology
Mandates a condition on weights which is not too restrictive
Is loop-free across PoPs
Needs a redundant backbone network with equal-length paths
Useful when average utilization is low
Future Work

Stability needs to be investigated
Infocom 2003
27