Transcript Routing as a Service

Routing as a Service
Karthik Lakshminarayanan
(with Ion Stoica and Scott Shenker)
Sahara/i3 retreat, January 2004
1
Problem
• Applications demand greater flexibility in route
selection
– Resilience: RON, Tapestry
– Performance: Detour
• Applications need different routing functionality
– Multicast: ESM, Overcast
– DDoS defense: SOS, Mayday
– Anycast: Gia
• Difficult to change any routing-level component in
the Internet today!
2
Current approach
• Overlay networks
– Layer above IP
– Deployability
• Problems:
– Ossification: overlay solutions again ossify routing in the
protocol; hard to modify once deployed on large scale
(lessons from the Internet)
– Efficiency: replicate packets multiple times along a
physical link; inefficient route construction
– Lack of control for ISPs: traffic hard for ISPs to control;
circumvent ISPs’ policies
3
Routing in transportation network
Multiple route providers
4
5
Multiple route metrics
6
Time taken
Distance
7
Our thesis
Push routing out of infrastructure
• Argument for “edge-controlled” routing
– Related: NIRA (NewArch group, MIT/ISI)
• Our contribution:
– Fine-grained control over routing
– Control plane for achieving this
8
System architecture
1. Forwarding infrastructure
–
–
Provides basic routing (referred to as default routing)
Exports primitives for inserting routes
9
System architecture
Network information
NEWS-2
NEWS-1
Performance-based,
policy-based routing
(span multiple ISPs)
2. NEWS/Route selector
–
–
Aggregates network information
Selects routes on behalf of applications
10
System architecture
Client A
Network information
Query/reply routing info.
Setup routes
NEWS-1
NEWS-2
Client B
Client C
Client D
3. End-hosts
– Queries NEWS to setup paths
11
Architectural position
Host
Data plane
Internet &
Infrastructure overlays
P2P &
End-host overlays
Our proposal
Infrastructure
Control plane
Data plane
Control plane
Control plane
Data plane
Separate control plane and data plane by
using clean abstractions
12
Challenges
• Open, multi-provider system (design of primitives)
– Unlike intra-domain, e.g. GSMP
– Security: control provided should not be used for
attacking the system
– Trust: between entities of the system, e.g. what
information does system give to NEWS
• Large-scale system (route selection)
– Scalability: monitoring; service to end-hosts
– Stability: should not lead to oscillations
• Deployability: ISP control
13
Infrastructure primitives
• Label-switching-like primitive
– Allows insertion of forwarding entries (id1, id2), where
id1, id2 are labels
– id = [ NodeID : LocalID ]
• Establishing paths – Loose virtual path (LVP)
– Composition of label switches: T = (id1, id2, …, idn) is
composed as (id1, id2), …, (idn-1, idn)
– Construct different topologies
– Aggregation can be performed at the level of tunnels
that end at infrastructure nodes
14
1. Trust
Network infrastructure
NEWS
• Infrastructure provides network information to NEWS
• Verification: NEWS should be able to verify this
– Indirect measurement techniques using primitive alone
– Metrics: Delay, loss, bandwidth
15
1. Trust
Network infrastructure
NEWS
Client C
• NEWS provides routes across the network
• Verification: Network verifies correctness
16
2. Scalability
• Monitoring:
– Monitor a subset of links
– Update period depends on stability (exploit link stationarity)
• For e.g., updates can be sent when metric on the link changes by a
factor of x
• Computation:
– Incremental computation of best paths
– Multiple paths are returned
• Querying:
– Default paths are used if special routing is not needed
– Hierarchical dissemination
– Caching of results: TTL chosen to reflect stability of paths
17
3. Deployment
• Infrastructure nodes
– Hosted at certain points within ISPs
• NEWS/Route selection
– 3rd party provider like Akamai
– Few in number
– Determined by application requirements
• Trust relations
– NEWS trusts infrastructure for information (verifiable)
– ISPs trust paths that NEWS returns (verifiable)
– Export links that obey the underlying policy constraints
18
Implementation status
• i3 primitives for setting up forwarding state
• Distributed NEWS implemented
– Route computation based on delay, loss and
bandwidth
– Deployed on PlanetLab
• i3 proxy has been modified to query NEWS
– Legacy applications can be used with NEWS
19
Summary of results
• Verification of measurement techniques
– Delay: 97% of cases have error < 10%
– Loss-rate: 90% in over 80% of the cases
– Bandwidth: Within a factor of 1.5 in 60% of cases
• Scalability of monitoring
– Simulation-based
– Logarithmic-degree graph
– Achieve 90% RDP of 2.3 (for delay) for TS-16384
20
Summary
• Routing control pushed outside the
infrastructure
• Routes computed by third-party entities
(NEWS) along with measurement
information provided by the infrastructure
• Leads to “evolvable” networks
– Deploy new routing schemes or optimize
existing routing without changing the
infrastructure
21