Transcript Slide 1

Addressing and Routing in
Multi-substrate Overlay
Networks
Jorg Liebeherr
University of Toronto
Joint work with: Majid Valipour and Boris Drazic
1
What is an overlay anyway?
• An overlay network is a virtual
network of nodes and logical links
built on top of an existing network
Overlay network
• A virtual link in the overlay
corresponds to a path in the
underlay
Substrate (“underlay”) network
2
Multi-substrate Network
• Colors indicate type of substrate
• Overlapping circles and links indicate bidirectional connectivity
Resulting Topology
4
Approaches to Routing
1. “Vanilla” Ad-hoc routing
– Extensively explored
– Not cognizant of substrates
– Scalability limits
2. Single structured overlay
– Simple addressing and routing
– Scales to large networks
– Not always viable
3. Hierarchical
– Within and between groups of
same color
– Needs address and routing
solutions
5
Overlays over multiple substrates
•
Goal: Improve ability to build an overlay over multiple
substrates
•
Problem: How to efficiently propagate information about
address bindings?
•
Solution:
Protocol mechanisms for exchanging address bindings
 Cross Substrate Advertisement (CSA)
6
Address Bindings in Single-substrate Overlay
Overlay node
identifier
B
A
D
C
Substrate address
SA(C)
SA(A)
SA(D)
SA(B)
Substrate Network
• Address binding: [A; SA(A)]
7
Address Bindings in Multi-substrate Overlay
Overlay node
identifier
A
B
D
C
SAS3(D)
Substrate address
SAS3(B)
SAS1(C)
SA(A)
SA
S1(A)
Substrate S1
SAS2(B)
SAS3(A)
SAS2(C) SA(B)
Substrate S2
Substrate S3
• More complex address binding: [A; SAS1(A), SAS3(A)]
8
Cross Substrate Advertising (simplified)
- Outgoing Overlay Socket
Node
ID = A
Source: A
Cross-Substrate Advertisement
SAS1(A)
SAS3(A)
SAS2(A)
Adapter
Node Adapter
Interface
1
SAS1(A)
Interface
2
SAS2(A)
Interface
3
SAS3(A)
Source: A
SAS1(A) SAS2(A) SAS3(A)
List of substrate addresses
9
Cross Substrate Advertising (simplified)
- Incoming Overlay Socket
Node
Source: A
Cross-Substrate Advertisement
ID
A
Substrate addresses
SAS1(A), SAS1(A), SAS1(A)
Adapter
Node Adapter
Interface
2
Source: A
Interface
3
SAS1(A) SAS1(A) SAS1(A)
10
Evaluate Methods for Relayed Address Exchange
Gossip
Exchange address lists
periodically
Protocol-driven
dissemination
Attach address lists to
protocol messages
“Push”
“Push Single”
Add address list
to each message
with info on node
Add preferred address
to each message with
info on node
“Pull”
Request address list
when info is needed
12
Experimental Evaluation
• Local Emulab Testbed
• 20 Linux nodes
CPU
2xQuad-Core Xeon 5400 (2 Ghz)
RAM
4G DDR2
Interface 8x1Gbps (4 Intel card, 4 NetFPGA)
• Software:
• Hypercast with CSA
• Delaunay Triangulation protocol
• Multiple UDP/IP substrates
Mapping of Nodes to Substrates
• K x K substrates  (K+1) x (K+1) regions
• Nodes distributed uniformly across regions
K=2
R12
R11
R21
R31
R22
R23
R13
R23
R33
Performance metrics
• Stability: Do nodes reach a stable state?
– % of nodes satisfying stability criterion for local neighborhood
• Connectivity: Do nodes form a single overlay?
– # of partitioned topologies
A single stable overlay topology has formed when
(1) 100% of nodes are stable; and
(2) there is one topology
15
Stability
K=8 (64 substrates), 648 nodes
Push/Pull
Push-single and gossip
250 ms
500 ms
Gossip
1000 ms
None
Push-single
Connectivity
Number of partitions
Number of partitions
K=8 (64 substrates), 648 nodes
Protocol overhead
Received Traffic (average per node): K=17 (289 substrates), 2592 nodes
Approaches to Routing
1. “Vanilla” Ad-hoc routing
– Extensively explored
– Not cognizant of substrates
– Scalability issues
2. Single structured overlay
– Simple addressing and routing
– Scales to large networks
– Not always viable
3. Hierarchical
– Within and between groups of
same color
– Needs address and routing
solutions
19
Reachability Domain
• Substrate: Set of compatible attachment points
• Reachability Domain: Maximal set of nodes with path in same substrate
Nodes in the same reachability domain must be able to agree on the
scope and identifier of a reachability domain.
Hierarchical routing: First find destination RD, then node within RD
20
Dynamic Reachability Domains
• Number and location of reachability domains are dynamic
New
reachability domain
Location of
reachability domain
changes
 Keeping consistent routing tables may not be feasible
21
Strawman: Landmark Domain Routing
• Inspired by Landmark Routing and Compact Routing
• Key concepts:
– Use least volatile reachability domains as landmark domains
– Route to destination via landmark domain
• Nodes know how to route to landmark domain
• Locator is reverse path from landmark domain
– Locator has one entry per traversed reachability domain
22
Reachability Domain
• Route from A  K
• K’s Locator: {RD6; H, J}
Step 1: Use next-hop information to reach node in landmark domain
Step 2: Use locator for exit node in landmark domain
Step 3: Follow reverse path to K
23
Preliminary Evaluation
• Random static topology
• 100 nodes per substrate with up to 70 reachability domains
• Multiple landmark domains
24
Related Works
• Adhoc Routing
– Hierarchies or clustering for scalability
e.g., [Ramanathan & Steenstrup `98] [Pei et.al. `00] [Eriksson et.al.`04]
– Structured overlays for ad-hoc routing
e.g., [Viana et.al. ‘04]
• Scalable Routing
– Landmark e.g., [Francis `88]
– Compact Routing e.g., [Thorup & Zwick `01]
– Metric Spaces e.g., [Krioukov `10]
• Overlay-based Routing
– Identifier-based e.g, [VRR ’06] [IHR ’08] [ROFL ’06]
– Locator-based + directory e.g., [SEATTLE `08] [SpoVNeT ’08]
25
Summary
• Self-organizing overlay protocols over multiple substrates
• Cross-Substrate Advertisement improves ability to form a
structured overlay over multiple substrates
• Hierarchical routing between reachability domains
• Landmark domain routing awaits full exploration:
– Provable bounds on path stretch
– Scalability vs. dynamics