Transcript slides

Placing Relay Nodes for
Intra-Domain Path
Diversity
Meeyoung Cha
Sue Moon
Chong-Dae Park
Aman Shaikh
Proc. of IEEE INFOCOM 2006
Speaker 游鎮鴻
Outline
Introduction and Motivation
 Related Work
 Penalty Quantification
 Placement Algorithms
 Evaluation
 Conclusions and Comments

Routing Instability in the Internet


Link and router failures are frequent.
Routing protocols are used to detect such failures and
route around them.

Convergence time is in the order of seconds or minutes.
 End-to-end connections experience long outages.

How to increase reliability and robustness of missioncritical services against temporary end-to-end path
outages?
Path Diversity and Overlay Networks

Take advantage of path diversity provided by
the network topology.

Overlay path – use a node inside the network to
relay packets over an alternate path that is
different from the default routing path.
ex) RON [Anderson et al., SOSP 2001]
Detour [Savage et al., IEEE Micro 1999]

Idea: use disjoint overlay paths along with the
default routing path to route around failures.
Objective



Previous work has focused on selecting good
relay nodes assuming relay nodes are already
deployed
As an ISP, we consider the problem of placing
relay nodes well
Assumptions:
· Intra-domain setting [Shortest Path First Routing]
· Relays are simply routers with relaying capability
· Overlay paths use single relay node
Path Diversity – Disjoint Overlay Path
Path Diversity – Disjoint Overlay Path
ISP Network
Destination
(egress router)
relays
Origin
(ingress router)
Disjoint overlay path gives maximum
robustness against single link failures!
Impact of ECMP on Overlay Path
Selection

Completely disjoint overlay paths are often not possible.
- Existing path diversity: Equal Cost Multi-Paths (ECMP)
AR
AR
BR
BR
Inter-PoP
BR
BR
AR
AR
Intra-PoP
(PoP: Point of Presences, AR: Access Router, BR:
Backbone Router)
Partially Disjoint Overlay Path
We may need to allow partially disjoint paths.
overlay path
o
r
default path
d
Such overlap makes networks less resilient to failures.
We introduce the notion of penalty to quantify the
quality degradation of overlay paths when paths overlap.
Penalty for Overlapped Links

Impact of a single link failure on a path
- Prob. of a packet routed from o to d encounters a
failed link l
= P[ path od fails | link l fails ]
0.25
0.125
0.125
0.5
o
1.0
0.25
0.125
0.5
d
0.875
0.5
0.75
Penalty for Overlapped Links (cont.)

Consider overlay path (ord) is used with default one
(od).
r
o
d
Penalty – the fraction of traffic carried on the
overlapped link
Penalty of relay and relay set

Penalty of a relay r for OD pair (o,d)
Po,d(r) = P[ both ord and od fail | single link failure ]

Penalty of a relay set R of size k
 sum of minimum penalty of all OD pairs using relays
∑o,d min( Po,d(r) | r ∈ R )
Placement Algorithms

How to find a relay set R of size k with minimum penalty

Optimal solution
 exhaustive search, 0-1 integer programming (IP)

Greedy selection heuristic
 start with 0 relays
 iteratively make greedy choice (minimal penalty)
 repeat until k relays are selected

Local search heuristic
 start with k set of random relays
 repeat single-swaps if penalty is reduced
Evaluation Overview

Performance evaluation
 Number of relays vs. penalty reduction
 Comparison with other heuristics (random, degree)

Sensitivity to network dynamics
 Based on topology snapshot data, do relays selected
remain effective as topology changes?
 Based on network event logs, what is the fraction of
traffic protected from failures by using relays?
Performance Evaluation
Relay Node Properties

Node degree, Hop count, Path weight
Sensitivity to Network Dynamics
5% of nodes are selected as relays
10% of nodes are selected as relays
Relays are relatively insensitive to network dynamics.
Hypothetical Traffic Loss from Failure Event Logs
(failure events)
less than 1% of traffic
lost for 92.8% failures
complete protection
for 75.3% failures
Conclusions

This is the first work to consider relay placement for path
diversity in intra-domain routing.

They quantify the penalty of using partially disjoint
overlay paths; and propose two heuristics for relay
placement.

They evaluate their methods on diverse dataset.

Their heuristics perform consistently well (near-optimal).
 A small number of relay nodes (≤10%) is good enough.
 Relays are relatively insensitive to network dynamics.
Comments
Evaluations are abundant.
 The comparison to Degree method is not a
good example.

Reference

http://an.kaist.ac.kr/~mycha/