Transcript LayeredRouting

UFO: A Resilient Layered
Routing Architecture
Yaping Zhu
Advisor: Prof. Jennifer Rexford
With: Andy Bavier and Nick Feamster (Georgia Tech)
Scalability + High Availability ?
Scalability:
Scalability of routing control plane
Efficiency of routing data plane
High Availability:
Quick adaptation and re-route
2
Can We Have the Best of Both Worlds?
Internet Routing
Scalability
Yes
Availability
No
Overlay Routing
No
Yes
UFO Routing
Yes
Yes
Basic Idea:
1. Layered routing architecture
(borrowing idea from overlay routing)
2. Underlay Support for efficient and scalable overlay routing
3
Outline
• Background
– Internet routing architecture
– Overlay routing (Resilient Overlay Networks)
– Basic idea of Layered routing architecture
•
•
•
•
•
Efficient overlay forwarding
Scalable overlay monitoring
Enhancing the scalability of UFO
Implementation and Evaluation
Conclusion and deployment
4
Internet Routing designed for Scalability
AS
AS
Transit
AS
Autonomous System
(AS)
AS
AS
Peering
AS
AS
AS
AS
AS
AS
AS
AS
AS
AS
AS
AS
AS
AS
AS
AS
AS
5
Internet Routing without High Availability
• Scalability
– Statistics: 25K ASes, 200K prefixes, millions of routers
– Hierarchical: intra-domain / inter-domain routing
– Prefix aggregation
• Routing protocols oblivious to performance
– Intra-domain: static link weights
– Inter-domain: routing policies
• Slow outage detection and recovery
– Disruptions during convergence
– Performance suffers from black-holes and loops
6
Scalable Internet Routing without Customization
• IP does destination-based forwarding
– All traffic follows the same paths
– Independent of the application requirements
• Yet, applications have different needs
– Voice and gaming: low latency and loss
– File sharing: high throughput
low latency,
but low throughput
High throughput,
but high latency
7
Outline
• Background
– Internet routing architecture
– Overlay routing (Resilient Overlay Networks)
– Basic idea of Layered routing architecture
•
•
•
•
•
Efficient overlay forwarding
Scalable overlay monitoring
Enhancing the scalability of UFO
Implementation and Evaluation
Conclusion and deployment
8
RON: Resilient Overlay Networks (by D. Andersen)
Scalable
IP routing substrate
9
RON: Resilient Overlay Networks
System Components
• Overlay Control Plane
– Probing, overlay path evaluation
– Disseminate routing messages, update routes
• Overlay Data Plane
– Tunnel setup: packet
encapsulation/decapsulation
• User Opt-in Method
– DNS redirection to overlay server
– Connection to overlay server: tunnels (e.g VPN)
10
Overlay Routing
• Pros:
– High availability: End hosts discover network-level path
failure and cooperate to re-route.
– Customization: Forwarding paths tailored to the
application
• Applications:
– Content distribution (e.g. Akamai SureRoute)
– Application layer multicast
11
Overlay Routing: Poor Efficiency
• Problem: traffic must traverse bottleneck
link both inbound and outbound
– Additional latency overhead
– Additional traffic consumption
Upstream
ISP
12
Overlay Routing: Poor Scalability
Let’s just
keep
probing
Scalable
IP routing substrate
Shall I reroute if one
packet lost?
I don’t
know when
failure
happens
13
Overlay Routing: Poor Scalability
• Fundamental trade-off between probing freq
and adaptation
– To get Quick adaptation
-> aggressive probing at short time interval
-> poor scalability:
->RON only supports for a small (i.e.,< 50
nodes) set of connected hosts
• Can not differentiate packet lost due to
different events
– Failure -> fast re-route
– Congestions -> may slower? -> oscillation?
14
Outline
• Background
– Internet routing architecture
– Overlay routing (Resilient Overlay Networks)
– Basic idea of Layered routing architecture
•
•
•
•
•
Efficient overlay forwarding
Scalable overlay monitoring
Enhancing the scalability of UFO
Implementation and Evaluation
Conclusion and deployment
15
Can We Have the Best of Both Worlds?
Scalability
Availability Customization
Internet
Routing
Yes
No
No
Overlay
Routing
No
Yes
Yes
UFO
Routing
Yes
Yes
Yes
16
A Resilient Layered Routing Architecture
• Combination of underlay and overlay routing
17
UFO: Underlay Friendly to Overlays
• In-network support for overlays
Underlay Friendly to
Overlays
18
A Resilient Layered Routing Architecture
• Questions:
– Which functionality belong to which layer?
– What are the interfaces between both layers?
• Cross-layer design
– Efficiency improvement:
• Direct control over forwarding table entries
– Scalability improvement:
• Explicit notification about changing network
conditions
19
Outline
• Efficient overlay forwarding
– Overlay forwarding on line cards
– Hosting the overlay control plane
• Scalable overlay monitoring
– Registration of overlay links
– Notification of network events
– Lazy recovery
• Enhancing the scalability of UFO
• Implementation and Evaluation
• Conclusion and deployment
20
Outline
• Efficient overlay forwarding
– Overlay forwarding on line cards
– Hosting the overlay control plane
• Scalable overlay monitoring
– Registration of overlay links
– Notification of network events
– Lazy recovery
• Enhancing the scalability of UFO
• Implementation and Evaluation
• Conclusion and deployment
21
Efficient Overlay Forwarding
• Problem: traffic must traverse bottleneck
link both inbound and outbound
• Solution: reflection points in routers
Upstream
ISP
22
Overlay Forwarding on Router Line Cards
• Building block: tunnels
23
Where the overlay control plane runs? On
Routers
• On Routers: by Router virtualization
– Pros: fast updates of forwarding tables
– Pros: efficient transmission of control
messages
– Pros: fate-sharing
Processors
Router
Switching
Fabric
Line Cards
24
Where the overlay control plane runs? On Servers
25
Where the overlay control plane runs? On Servers
• On separate set of servers
– Update forwarding table on router line cards
– Data packets reflected in-network
• Pros:
– Pros: cheap compared to router
– Pros: compatibility with legacy overlay server
• Cons:
– Lack of fate sharing
26
Outline
• Efficient overlay forwarding
– Overlay forwarding on line cards
– Hosting the overlay control plane
• Scalable overlay monitoring
– Registration of overlay links
– Notification of different kinds of network events
– Lazy recovery
• Enhancing the scalability of UFO
• Implementation and Evaluation
• Conclusion and deployment
27
Scalable Overlay Monitoring
Assumption:
Rich connectivity, multiple alternative overlay paths
Overlays could even tolerate “false positive” notification
What to notify?
Different applications may want notification of different
events
Notification Benefits:
Accurate adaptation (compared with RON)
Reduce probing overhead, and increase scalability
28
Scalable Overlay Monitoring
• Notification preserve overlay link
abstractions
– Message format:
(overlay source, overlay destination, event)
– Routers store states by explicit overlay registration
• Explicit notification about events which
affect performance of overlay applications
– Physical failures of routers or links
– Reachability failures: route withdraw, routing session
failure
– Network congestion
– few “hello” packets lost
29
Registration of Overlay Links
Overlay Nodes: A, B, C
Routers: 1, 2, 3, 4
Register for uni-directional overlay links A->B and A->C
A
1
2
3
4
B
C
30
Periodical Registration of Overlay Links
ACK for successful registration
A
(A,B)
1
(A,B)
2
(A,B)
4
3
(A,B)
B
C
31
Periodical Registration of Overlay Links
Registration kept as soft state
Periodical re-registration
A
(A,B)
(A,C)
1
(A,B)
(A,C)
2
(A,B)
3
(A,B)
B
(A,C)
4
(A,C)
C
32
Notification of Network Events
A
(A,B)
(A,C)
1
(A,B)
(A,C)
2
(A,B)
3
(A,B)
B
(A,C)
4
(A,C)
C
33
Reactive Routing and Lazy Recovery
• Assumption: rich connectivity
• Reactive routing after notification
– Re-route via alternative overlay paths
– Disseminate notification message to peers
• Lazy recovery
– Stick to alternative overlay paths (e.g. for mins)
– Re-register for failed overlay
– Reason: transient period during convergence of
recovery, causing loops and blackholes
34
Outline
• Efficient overlay forwarding
– Overlay forwarding on line cards
– Hosting the overlay control plane
• Scalable overlay monitoring
– Registration of overlay links
– Notification of network events
– Lazy recovery
• Enhancing the scalability of UFO
• Implementation and Evaluation
• Conclusion and deployment
35
Unicast Registration is Inefficient
• Overlay Nodes: A, B, C, D, E and Routers: 1, 2, 3, 4
• Register for overlay links B->A, C->A, D->A, E->A
(B,A)
A
(B,A)
(C,A)
(D,A)
(E,A)
1
(B,A)
(C,A)
(D,A)
(E,A)
2
(B,A)
(C,A)
(D,A)
(E,A)
3
(C,A)
(D,A)
D
(E,A)
E
4
B
C
36
Unicast Notification is inefficient
A
(B,A)
(C,A)
(D,A)
(E,A)
1
(B,A)
(C,A)
(D,A)
(E,A)
2
(B,A)
(C,A)
(D,A)
(E,A)
(B,A)
B
(C,A)
C
3
(D,A)
D
(E,A)
E
4
37
Multicast Registration
GroupA
A
1
GroupA
2
3
GroupA
GroupA
GroupA
GroupA
4
GroupA
B
C
D
E
38
Multicast Notification
GroupA
A
1
GroupA
2
3
GroupA
GroupA
GroupA
GroupA
4
GroupA
B
C
D
E
39
Benefits of Multicast registration/notification
• Reduce registration states stored at routers
– Unicast: store state for each (src, dst) pair, O(n2)
– Multicast: store state each mcast group, O(n)
• Reduce notification message overhead
• Deployment Benefits:
– Exploit IP-Multicast (which routers already have)
40
Outline
• Efficient overlay forwarding
– Overlay forwarding on line cards
– Hosting the overlay control plane
• Scalable overlay monitoring
– Registration of overlay links
– Notification of network events
– Lazy recovery
• Enhancing the scalability of UFO
• Implementation and Evaluation
• Conclusion and deployment
41
Prototype Implementation on VINI
• What’s finished?
– RON
• Control plane: probing and reactive routing
• Data plane: overlay tunnel setup
• User Opt-in: user data packets delivered by overlays
– UFO: Notification of link failure
• What to do next?
– UFO
• Evaluate inter-domain routing convergence
• Notification of link congestion
– Run applications: e.g. VoIP
42
Prototype Implementation on VINI
•
•
•
•
Overlay: RON
Overlay FIB
Client opt-in
Notification by Filter
RON
eth0
XORP
IP Router
eth1
eth2
UML
eth3
Control
Data
Packet
Overlay
Forward
FIB
Engine
Click
Clients
UmlSwitch
element
Tunnel table
Filters
VPN Server
PlanetLab VM
43
Evaluation Setup
• Topology
– Routers and Overlay nodes
s
d
r
44
Evaluation1: Reactive Routing of RON
• How much time does RON spend to detect
outage?
– RON probe interval : 12s
– RON probe timeout: 3s
– Average detection time =
Probe interval / 2 + probe timeout * 3
• What to evaluate?
– Fundamental trade-off between probe
frequency and detection time
– Parameters: probe interval
45
Evaluation1: Reactive Routing of RON
• Detection time = probe interval / 2 + probe timeout *3
46
Evaluation2: comparison of Convergence Speed
• Controlled Experiment
– Fail a link by filtering all the packets
• Comparison of Convergence Speed
– IP routing (XORP)
– RON reactive routing
– Reactive routing with UFO notification
47
Evaluation2: comparison of Convergence Speed
– IP Routing (XORP)
• Hello-interval: 15s
• Router-dead-interval: 45s
Link down
Link up
48
Evaluation2: comparison of Convergence Speed
– RON
• Probe interval: 12s
• Probe timeout: 3s
• Re-route immediately after outage detection
Link down RON up
Link up
49
Evaluation2: comparison of Convergence Speed
– UFO routing with explicit notification
• Re-route immediately after outage notification
UFO up
Link down
RON up
Link up
50
Outline
• Efficient overlay forwarding
– Overlay forwarding on line cards
– Hosting the overlay control plane
• Scalable overlay monitoring
– Registration of overlay links
– Notification of network events
– Lazy recovery
• Enhancing the scalability of UFO
• Implementation and Evaluation
• Conclusion and deployment
51
Deployability Benefits
• Forwarding Support:
– Low barriers to entry
– Routers already have hardware for setting
tunnels
– Upgrade small fraction for overlay forwarding
• Notification Support:
– Upgrade all routers to support notification
(could start with one AS)
– Performance benefits and business incentives
– Better real-time applications: VoIP
52
Related Work
• Overlay routing
– Detour (Collins98)
– Resilient Overlay Networks (Andersen01)
• Improving forwarding efficiency
– Path reflection and path painting (Jannotti02)
• Reducing probing overhead
– Routing Underlay for Overlays (Nakao03)
• Network virtualization
– VINI, GENI, CABO, VERA
53
Conclusion
• Contributions
– Scalable overlay routing is feasible with innetwork support
– UFO provides strong reliability and a
compelling deployment model
• Future Work
– Further performance evaluation
– Applications: VoIP
– Application Layer Multicast (with NEC Lab)
54
Acknowledgement
• General Exam Committee:
– Prof. Jennifer Rexford (Advisor)
– Prof. Larry Peterson
– Prof. Vivek Pai
• Collaborators:
– Andy Bavier and Nick Feamster (Georgia Tech)
• Cabernet Research Group
• VINI Support, Planetlab Operations
55
Questions?
56
FAQ: recovery notification ?
• UFO does NOT support notification of
recovery, because:
– Alternative overlay paths available (overlays
don’t care !)
– Hard for routers to determine intra-domain
convergence: synchronization to determine
data-plane convergence
– Hard for routers to determine inter-domain
convergence
57