Transcript Routing in Multi-Layered Networks

Routing in
Multi-Layered Networks
Srinivasan Seetharaman
Georgia Institute of Technology
[email protected]
Case Western Reserve University
March 2007
Internet Architecture
Current Internet architecture has been guided by
the end-to-end principle:



network layer implements simple primitives
useful for a broad range of end-to-end applications
for good balance between cost vs benefit
2
Internet Evolution
A survey of Cisco router software features…
Feature
Year
Version
Fault restoration
1986
SSR 1
Multicast
1994
IOS 10.2
DiffServ prioritization
1997
IOS 11.0
Tag switching (pre-MPLS)
1997
IOS 11.1
Security – 1: Encryption, Firewalls
2000
IOS 11.2
Security – 2: NAT
2001
IOS 12.0
No dramatic change in services
offered to end-user
2007
IOS 12.4T
3
Internet Evolution (contd.)
Common observations:


Core features are gradually beginning to ossify
Routers are becoming faster and more reliable
Deployability concerns are common with most services
All-or-nothing implementation problems

For example, we still do not see deployment of Secure-BGP
Need for ways to offer new services
and enhance existing services!
4
Overlay Networks
Overlay networking helps overcome functionality
limitations by forming a virtual network that is:


Independent
Customizable
over the IP network (Native layer).
5
Example: Latency-Optimized Overlay
A
50ms
D
Overlay link
Overlay nodes
20ms
20ms
Relaying


B
C
Overlay routing is independent of native layer routing
Each Overlay path comprises one or more Overlay links,
based on a certain selfish objective
6
Service Overlay Networks
Classification
Overlay networks
 Multicast (e.g. ESM, Overcast)
 Better routes (e.g. RON, Detour, X-Bone)
 Customized
forwarding
(e.g. I3, Scattercast)
Peer-to-peer
Routing
overlay
networks QoS (e.g. OverQoS,
networks
SON)
 Security (e.g. DynaBone, SOS)
… and much more
End-system
overlays
(e.g. Skype)
Service
overlays
(e.g. VINI)
7
Service Overlay Networks (contd.)
Throughput optimized
C
overlay
A
F
G
D
B
A
E
C
Latency optimized
overlay
E
F
OVERLAY
H
LAYER
H
NATIVE IP
B
LAYER
D
G
9
Cross-Layer Interaction
Performing dynamic routing at both layers
leads to:

Functionality overlap (Both overlay layer and IP
layer perform similar set of functions)

Mismatch or misalignment of routing objectives

Contention for limited physical resources
10
Cross-Layer Interaction (contd.)
These issues are amplified in the presence of

Selfish motives

Lack of information about other layer

Increasing impact ( #overlays  |Traffic| )
11
Outline of my work
 Overlay routing conflicts with native layer load balancing.
- [Infocom07]
 Overlay routing can violate inter-domain policies.
- [ICNP06]
 Failure detected by both layers and rerouted twice, with
each rerouting disrupting the optimality of the previous.
- [Infocom06]
Potential for Indefinite Conflict!
 A framework for improved support of overlay services
- [Hotnets05]
12
Conflict 1. Intra-domain
Overlay routing vs Traffic Engineering
Repeated Non-Cooperative Game
Player1: Overlay Routing - Latency-optimized paths between nodes
Player2: Traffic Engineering - MPLS-based scheme that solves a
linear program (LP) to obtain optimal routes
Overlay Link
Latencies
Overlay
Routing
Overlay
routes

Native link
delays

Overlay layer
traffic
Traffic on each
overlay link
Native
routes
Traffic
Engineering
TM

Background
traffic
14
Illustration of OR vs TE
14ms
Shortest
latency
routes
A
4ms
4ms
5ms
B
10ms
D
23ms
OVERLAY
NATIVE
Minimize
(Max util)
C
E
3
2ms
2
10ms
4
2ms
3
2ms
B
A
F
4
2ms
5
4ms
2
3ms
2
3ms
I
C
4
2ms
3
3ms
G
H
3
6ms
2
10ms
J
2
10ms
3
2ms
Numbers on
each link
represent the
avail-bw
D
Initial State
15
Illustration of OR vs TE (contd.)
14ms
C
A
Multihop paths
6ms
4ms
ABC
5ms
B
10ms
ABD
D
23ms
OVERLAY
NATIVE
E
0
2
10ms
4
2ms
0
2ms
2ms
B
A
1
I
C
2
2
3ms
2ms
4ms
2
3ms
2
3ms
4
2ms
F
G
H
1
2
6ms
2
10ms
Overlay traffic
introduced
J
2
10ms
Avail-bw
changed
2ms
D
16
Illustration of OR vs TE (contd.)
14ms
C
A
5ms
ABC
5ms
B
10ms
ABD
D
23ms
OVERLAY
NATIVE
E
1
2ms
SPLIT
Multihop paths
4ms
2
10ms
2
2ms
1
2ms
B
A
F
3
4ms
1
3ms
1
3ms
I
2
2ms
C
4
2ms
2
3ms
G
H
1
6ms
2
10ms
After TE reacts
J
2
10ms
2
2ms
D
Latency
changed
17
Illustration of OR vs TE (contd.)
14ms
C
A
Multihop paths
4ms
5ms
10ms
ABCD
D
BCD
23ms
OVERLAY
NATIVE
E
1
2ms
SPLIT
ABC
5ms
B
2
10ms
0
2
2ms
1
2ms
B
A
F
5
3
4ms
1
3ms
1
3ms
I
2
10ms
After Overlay
routing reacts
J
0
2
2ms
C
0
2
3ms
4
2ms
G
H
3
1
6ms
2
10ms
0
2
2ms
D
Avail-bw
changed
18
Simulation Results
TE
objective
Round
Overlay
objective
Overall
stability
19
Resolving Conflict
General Approach: Similar to Stackelberg’s game:


Designate leader/follower.
Make Leader act after predicting (or) counteracting the
subsequent reaction of the follower
Leader undertakes preemptive action such that
a. Follower has no desire to change
 Friendly
b. Follower has no alternative to pick  Hostile
Use history to learn desired action gradually.
20
Preemptive Strategies: Summary
We proposed four strategies that improve performance
for one layer and achieve a stable operating point
Inflation factor
=
Steady state obj value with strategy
Best obj value achieved
Inflation
Leader
Strategy
Overlay
TE
Overlay
Friendly: Load-constrained LP
Hostile: Dummy traffic injection
1.082
1.023
1.122
1.992
Native
Friendly: Hopcount-constrained LP
Hostile: Load-based Latency tuning
1.027
1.938
1.184
1.072
22
Preemptive Strategies: Summary (contd.)
Each strategy achieves best performance for the
target layer



within a few rounds
with no interface between the two layers
with all information inferred through simple measurements
23
Conflict 2. Inter-domain
Overlay routing vs Inter-Domain Policy
Inter-Domain Policy Violations
Objective of overlay layer: Offer better latency
routes to end-systems
Harvard
Univ
30 ms
24 ms
Colorado
State Univ
61 ms
Univ of NC
But, what is assumed here?

Harvard is not unhappy with relaying overlay packets
25
Inter-Domain Policy Violations (contd.)
A more realistic picture…
Provider
1
Client
1
A
Peer
Provider
2
$
$
Overlay
route
Valley-free
violation
B
Client
2
Peer
Legitimate
native route
Client
3
C
Unhappy
 Money
 Load
26
Planetlab Overlay Measurements
Topology:
58 geographically distributed Planetlab nodes (Univ +
Commercial). This represents 3306 overlay paths
Measurement steps:
1.
Determine AS path of each overlay link
(Rockettrace / traceroute for hop list + IPAS mapping)
2.
Determine overlay path based on shortest path algorithm
(For Cost = latency, 56.6% overlay paths prefer relaying)
3.
AS relationships inferred using Gao’s algorithm
Data: http://www.cc.gatech.edu/~srini/code
27
Measurement Results
Only multihop overlay paths are violating
Extent of transit policy violations in multihop paths
Violation Type
Provider-AS-Provider
% paths
63.1
Provider-AS-Peer
2.4
Peer-AS-Provider
2.0
Peer-AS-Peer
2.4
Total
69.9
28
Policy Enforcement by Native Layer
As ISPs become aware of the negative impact of
overlays and commence filtering, this leads to

drastic deterioration in overlay route performance

commensurate with the number of ASes enforcing policy
29
Resolving Conflict
Overlay service provider shares some of the cost
incurred by the native layer
 Cost-sharing approach
For a certain fee, we adopt one of the following
strategies for achieving good legitimate paths:
1.
Obtain transit permit from certain AS
2.
Add new node to certain provider AS
30
Illustration of Cost Sharing
With no filtering,
11
Tier-1 provider
13
AS hosting overlay node
Cust-Prov relation
Tier-2 provider
Stub customer
21
31
Peering relation
23
22
32
33
Transit
violation
31
Illustration of Cost Sharing (contd.)
With filtering, we have no multi-hop paths
11
Tier-1 provider
13
AS hosting overlay node
Cust-Prov relation
Tier-2 provider
Stub customer
21
31
Peering relation
23
22
32
33
32
Illustration of Cost Sharing (contd.)
Option 1: Add new overlay node to provider AS 22
11
Tier-1 provider
13
AS hosting overlay node
Cust-Prov relation
Tier-2 provider
Stub customer
21
31
Peering relation
23
22
32
33
Option 2: Obtain transit permit from stub AS 32
33
In Summary, Overlays…
… offer valuable services needed by end-systems
… leads to complex cross-layer interaction with
potentially detrimental effects
… are hard to detect, as seen from efforts with
identifying Skype traffic
35
Ongoing Work
Conflict-aware overlay node placement
Multi-layer testbed using Planetlab-VINI

that allows control of multiple layers
Analysis of other “performance-aware” overlays
(like Bittorrent)
36
Other Work
There exists other forms of collaboration
that are malicious.
I work on exposing their memberships in a
scalable manner
37
Future of Overlays
Overlays are essential as…



Means for end-systems to collaborate
Environment for testing future innovations (GENI)
Architecture for Future Internet in the form of Network
Virtualization
 Cross-layer interaction will affect performance. How
best to design protocols and services in the future?
38
Future Research – Native Layer
How to prepare ISPs for overlay applications?


To promote it
To contain it
No effective solution for identifying relayed traffic.
Need an orthogonal policy between overlay/native.
Need to address the network impasse. How to tune
the network for


.. the new breed of Internet applications? (e.g., file sharing)
…and new paradigms of communication? (e.g., wireless)
39
Future Research – Service Layer
How best to support multiple Internets?


Researchers suggest a future with multiple coexisting
Internets (Potential outcome of NSF-FIND program)
Model as multiple coexisting overlays
Which layer to implement a service at? For example,
a service like multicast can be performed at both
native layer and overlay layer!


Which layer to use for a particular scenario?
Which layer needs optimizing?
40
Thank you!
See: http://www.cc.gatech.edu/~srini
Questions