Transcript On Selfish Routing In Internet

On Selfish Routing In
Internet-like Environments
Lili Qiu (Microsoft Research)
Yang Richard Yang (Yale University)
Yin Zhang (AT&T Labs – Research)
Scott Shenker (ICSI)
ACM SIGCOMM 2003
Selfish Routing
• IP routing is sub-optimal for user performance
– Routing hierarchy and policy routing
– Equipment failure and transient instability
– Slow reaction (if any) to network congestion
• Autonomous routing: users pick their own routes
– Source routing (e.g. Nimrod)
– Overlay routing (e.g. Detour, RON)
• Autonomous routing is selfish by nature
– End hosts or routing overlays greedily select routes
– Optimize their own performance goals
– … without considering system-wide criteria
Bad News
• Selfish routing can seriously degrade
performance [Roughgarden & Tardos]
Worst-case ratio is unbounded
L1(y) = 1
S
D
L0(x) = xn
Total load: x + y = 1
Mean latency: x L0(x) + y L1(y)
• Selfish source routing
• All traffic through lower link
 Mean latency = 1
– Latency optimal routing
• To minimize mean latency,
set x = [1/(n+1)] 1/n
 Mean latency  0 as n  
Questions
• Selfish source routing
– How does selfish source routing perform?
– Are Internet environments among the worst cases?
• Selfish overlay routing
– How does selfish overlay routing perform?
– Does the reduced flexibility avoid the bad cases?
• Horizontal interactions
– Does selfish traffic coexist well with other traffic?
– Do selfish overlays coexist well with each other?
• Vertical interactions
– Does selfish routing interact well with network
traffic engineering?
Outline
• Overview
• Performance results
–
–
–
–
Physical routing
Overlay routing
Multiple overlays
Interaction with traffic engineering
• Summary
• Ongoing and future work
Our Approach
• Game-theoretic approach with simulations
– Equilibrium behavior
• Apply game theory to compute traffic equilibria
• Compare with global optima and default IP routing
– Intra-domain environments
• Compare against theoretical worst-case results
• Realistic topologies, traffic demands, and latency functions
• Disclaimers
– Lots of simplifications & assumptions
• Necessary to limit the parameter space
– Raise more questions than what we answer
• Lots of ongoing and future work
Routing Schemes
• Routing on the physical network
– Source routing
– Latency optimal routing
• Routing on an overlay (less flexible!)
– Overlay source routing
– Overlay latency optimal routing
• Compliant (i.e. default) routing: OSPF
– Hop count, i.e. unit weight
– Optimized weights, i.e. [FRT02]
– Random weights
Internet-like Environments
• Network topologies
– Real tier-1 ISP, Rocketfuel, random power-law graphs
• Logical overlay topology
– Fully connected mesh (i.e. clique)
• Traffic demands
– Real and synthetic traffic demands
• Link latency functions
– Queuing: M/M/1, M/D/1, P/M/1, P/D/1, and BPR
– Propagation: fiber length or geographical distance
• Performance metrics
– User: Average latency
– System: Max link utilization, network cost [FRT02]
25000
20000
15000
10000
5000
selfish source routing
Load scale factor=1
latency optimal routing
compliant routing (minimum network cost)
Good news: Internet-like environments are far
from the worst cases for selfish source routing
PowerD10
PowerD5
PowerD2
Verio
Tiscali
Telstra
Sprint
Level3
Exodus
EBONE
ATT
0
Abovenet
Average latency (us)
Source Routing: Average Latency
Source Routing: Network Cost
Network cost
10000
1000
100
10
PowerD10
PowerD5
PowerD2
Verio
Tiscali
Telstra
Sprint
Level3
Exodus
EBONE
ATT
Abovenet
1
selfish source
routing
Load scale
factor=1
latency optimal routing
compliant routing (minimum network cost)
Bad news: Low latency comes at much higher network cost
Difference between Source Routing
and Overlay Routing
• Even if the overlay includes all network nodes,
routing on an overlay is still different
– Network-level routing can prevent overlay traffic
from using a link by setting the corresponding entry in
routing matrix to 0 (in OSPF this is achieved by
assigning a large weight)
– Certain physical routes cannot be implemented by any
overlay routing
• Routing flexibility is further reduced when only
a fraction of nodes belong to an overlay
200
12000
Max link utilization
Average latency (us)
Selfish Overlay Routing
(Full Overlay Coverage)
10000
8000
6000
4000
2000
0
150
100
50
0
0
0.5
1
1.5
2
0
0.5
1
1.5
Load scale factor
Load scale factor
source routing
overlay-src: opt-weight
source routing
overlay-src: opt-weight
overlay-src: hop-count
overlay-src: rand-weight
overlay-src: hop-count
overlay-src: rand-weight
1) overlay-src with opt-weight and hop-count perform
similarly as source routing
2) overlay-src with random-weight performs much worse.
2
Selfish Overlay Routing
(Partial Overlay Coverage)
• Overlay is formed from all edge nodes in
ISPTopo
ISPTopo
Max link utilization (%)
Average latency (us)
ISPTopo
9500
9000
8500
8000
7500
0
0.5
1
1.5
Load scale factor
all
partial
2
2.5
200
150
100
50
0
0
0.5
1
1.5
Load scale factor
all
partial
The effects of partial overlay coverage is small
in backbone topologies.
2
2.5
Horizontal Interactions
random weights (load scale factor = 1)
Average latency (us)
4.0E+04
3.2E+04
2.4E+04
1.6E+04
8.0E+03
0.0E+00
both
compl.
both
selfish
both
latopt
overlay 1
selfish /
compl.
selfish /
latopt
latopt /
compl.
overlay 2
Different routing schemes coexist well without hurting each other.
With bad weights, selfish overlay also improves compliant traffic.
Recap
• Good news: Unlike the theoretical worst
cases, selfish routing in Internet-like
environments yields close to optimal
latency
– The above result is true for both source
routing and overlay routing
– Selfish routing can achieve good
performance without hurting the traffic
that is using default routing
• Bad news: Selfish routing achieves low
latency at the cost of overloading network
Vertical Interactions
• An iterative process between two players
– Traffic engineering: minimize network cost
• current traffic pattern  new routing matrix
– Selfish overlays: minimize user latency
• current routing matrix  new traffic pattern
• Question:
– Does system reach a state with both low
latency and low network cost?
• Short answer:
– Depends on how much control underlay routing
has
One Round during Vertical
Interaction
T(t) = Traffic matrix when routing matrix is R(t-1)
R(t) = OptimizedRoutingMatrix(T(t))
Traffic engineering installs R(t) to network
Selfish routing redistributes traffic to be T(t+1)
Selfish Overlays vs. OSPF Optimizer
200
180
Max link utilization (%)
Average latency (us)
2.5E+04
2.0E+04
1.5E+04
1.0E+04
5.0E+03
160
140
120
100
80
60
40
20
0.0E+00
0
10
20
30
Round
selfish alone
selfish + TE (OSPF)
40
50
0
0
10
20
30
40
Round
TE alone
selfish alone
TE alone
selfish + TE (OSPF)
OSPF optimizer interacts poorly with selfish overlays
because it only has very coarse-grained control.
50
1.4E+04
120
1.2E+04
100
Max link utilization (%)
Average latency (us)
Selfish Overlays vs. MPLS Optimizer
1.0E+04
80
8.0E+03
60
6.0E+03
40
4.0E+03
2.0E+03
20
0.0E+00
0
0
10
20
30
40
50
0
10
Round
selfish alone
TE alone
20
30
40
50
Round
selfish + TE (MPLS)
selfish alone
TE alone
MPLS optimizer interacts with
selfish overlays much more effectively.
selfish + TE (MPLS)
Conclusions
• Contributions
– Important questions on selfish routing
– Computation of traffic equilibria
– Simulations that partially answer questions
• Main findings on selfish routing
– Near-optimal latency in Internet-like environments
• In sharp contrast with the theoretical worst cases
– Coexists well with other overlays & regular IP traffic
• Background traffic may even benefit in some cases
– Big interactions with network traffic engineering
• Tension between optimizing user latency vs. network load
Lots of Future Work
• Extensions
– Multi-domain IP networks
• Model inter-domain topology
• Model inter-domain traffic demands
• Reduce computation complexity
– Different overlay topologies
• Tree, ring, …
• What overlay topology to form to improve
performance and/or robustness?
– Alternative selfish-routing objectives
• Throughput, loss rate, …
Lots of Future Work (Cont.)
• Study dynamics of selfish routing
– How are traffic equilibria reached?
– What routing protocols enable us to reach
equilibria quickly?
• Improve interactions
– Between selfish routing & traffic engineering
• Bi-level programming?
– Between competing overlay networks
How to achieve traffic equilibria?
• Challenges
– Distributed algorithm
– Responsive to changes in traffic
• Approach
– Probabilistic routing based on distributed
learning
• For each destination k, node i maintains a routing
probability P(i, k, j) for each neighbor j
How to achieve traffic equilibria?
(Cont.)
• Protocol
– For every T seconds
•
•
•
•
Send latency Lik(t) to all neighbors
Receive latency Ljk(t) to all neighbors
Compute Lik(t+1)
Update pikj(t+1) for all neighbors j
• Properties
– Converge to Wardrop equilibria or global
minimum latency
– Responsive to traffic stimuli (e.g., spike, step
function, linear function)
Thank you!
Computing Traffic Equilibrium
of Selfish Routing
• Computing traffic equilibrium of non-overlay traffic
– Use the linear approximation algorithm
• A variant of the Frank-Wolfe algorithm, which is a gradient-based
line search algorithm
• Computing traffic equilibrium of selfish overlay routing
– Construct a logical overlay network
– Use Jacob's relaxation algorithm on top of Sheffi's
diagonalization method for asymmetric logical networks
– Use modified linear approximation algo. in symmetric case
• Computing traffic equilibrium of multiple overlays
– Use a relaxation framework
• In each round, each overlay computes its best response by fixing
the other overlays’ traffic; then the best response and the
previous state are merged using decreasing relaxation factors.
200
12000
Max link utilization
Average latency (us)
Selfish Overlay Routing
(Full Overlay Coverage)
10000
8000
6000
4000
2000
0
150
100
50
0
0
0.5
1
1.5
2
0
0.5
1
1.5
Load scale factor
Load scale factor
source routing
overlay-src: opt-weight
source routing
overlay-src: opt-weight
overlay-src: hop-count
overlay-src: rand-weight
overlay-src: hop-count
overlay-src: rand-weight
1) overlay-src with opt-weight and hop-count perform
similarly as source routing
2) overlay-src with random-weight performs much worse.
2
Selfish Overlay Routing
(Full Overlay Coverage)
• Direct Link Shortest [DLS]
– For any physically adjacent nodes A and B, all the
traffic from A to B is routed through the direct link
AB without involving any other links. (e.g., hop-countbased OSPF)
• For an overlay that covers all network nodes and
satisfies DLS
– routing on the overlay = routing on the underlay
• Hop-count-based OSPF and optimized OSPF
weights satisfy DLS  they perform similarly as
source routing
• Random OSPF weights violate DLS  some links
are pruned, and performance degrades
Selfish Overlay Routing
• Similar results apply for overlay routing
– Achieves close to optimal average latency
– Low latency comes at higher network cost
• Even if overlay covers a fraction of nodes
– Random coverage: 20-100% nodes
– Edge coverage: edge nodes only