Transcript ppt

Decoupling Naming from Routing
via Virtual Id ROuting
A Scalable, Robust and Namespace Independent
Routing Architecture for Future Networks
Zhi-Li Zhang,
University of Minnesota-Twin Cities
Joint work with my students:
Sourabh Jain (now at Cisco), Yingying Chen, Saurabh Jain
Outline
2

Introduction and Motivation




VIRO




Virtual ID layer
Routing Table Construction
vid lookup & Forwarding
Evaluation



Current Trends
Challenges
Recent Proposals
Simulation based Setup
Real Implementation and Prototyping
Summary and On-going work
Current Trends and Future Networks
3



Large number of
mobile users and systems
Large number of
smart appliances

data centers & clouds
Diverse edges



Web, emails
& cloud services
High bandwidth core


Social
networks
mobility
intermittent connectivity
Banking &
e-commerce
Internet
(or Future Networking
Substrate)
More and more
virtualizations:
virtual servers, clients
virtual networks
POTS
surveillance
& Security
Heterogeneous
technologies


IP TV Multimedia Games
Streaming
VoIP
Home users
Smart meters,
Smart phones, smart grid,
sensors, etc.
smart pads,
etc.
Within the Internet Core
4




Large ISPs with large
geographical span
Large content/service
providers with huge data
centers
High capacity,
dense and rich topology
Cloud Computing & Mobile
Services
– public IP addresses for
customer-facing servers/devices
– private IP address realms for
internal servers/devices
Challenges posed by These Trends
5

Scalability: capability to connect tens of thousands or more users
and devices


Mobility: hosts are more mobile, “virtual servers” are also mobile



need to be “proactive” instead of reactive
need to localize effect of failures
Manageability (& Security): ease of deployment, “plug-&-play”



need to separate location (“addressing”) and identity (“naming”)
Availability & Reliability: must be resilient to failures


routing table size, constrained by router memory, lookup speed
need to minimize manual configuration
self-configure, self-organize, while ensuring security and trust
…….
How Existing Technologies Meet these Challenges?
6

(Layer-2) Ethernet/Wireless LANs
 Pluses: plug-&-play, minimal
configuration, better mobility
 Minuses:
 (occasional) data plane
flooding, sub-optimal
routing (using spanning tree),
not robust to failures
 Not scalable to large (&
wide-area) networks

(Layer-3) IPv4/IPv6
 Pluses:
 better data plane scalability, more
“optimal” routing, …
 Minuses:
 control plane flooding, global effect
of network failures
 poor support for mobility
 difficulty/complexity in “network
renaming”

Esp., changing addressing schemes (IPv4 > IPv6 transition) requires modifications in
routing and other network protocols
IP address Management & Mobility
7
Interface IP
Interface IP
IP address (re-)assignment
creates
address:
address:
192.168.1.1
192.168.2.1
To: 192.168.1.2
management
overhead:
 Careful IP configurations
• DHCP servers need to maintain state
• Static
assignment requires
manual
Subnet Prefix:
Subnet Prefix:
192.168.1.0
192.168.2.0
effort
Mask:
Mask:

Breaks
the
mobility
IP address
255.255.255.0
255.255.255.0
IP address
192.168.1.2
192.168.1.2

Firewall
re-configurations
Gateway:
Gateway:
Gateway:
192.168.1.1
192.168.1.1
192.168.2.1
Gateway:
192.168.1.1
Recent proposals
8



SEATTLE [SIGCOMM’08] , VL2 [SIGCOMM’09], TRILL, LISP

Shortest path routing using link state routing protocol on Ethernet switches

“Identifier and location” separation for better mobility

Seattle uses DHT style lookup, VL2 uses a directory service for flooding free lookup

No flooding on data plane

However, control plane still uses flooding!
ROFL [SIGCOMM’06], UIP [HotNets’03]

DHT style routing for scalability (based on “virtual circuits” between id’s)

Uses flat labels for mobility

However, these may incur significant routing stretch due to no topology awareness
No fundamental support for advanced features such as:

Multipath routing

Fast Failure Rerouting
Outline
9

Introduction and Motivation




VIRO




Virtual ID layer
Routing Table Construction
vid lookup & Forwarding
Evaluation



Current Trends
Challenges
Recent Proposals
Simulation based Setup
Real Implementation and Prototyping
Summary and On-going work
Meeting the Challenges:
VIRO: A Scalable and Robust “Plug-&-Play” Routing Architecture
10

Decoupling routing from naming/“addressing” [in “IP/MAC” sense]

“native addressing”/logical naming-independent (i.e., identifier-independent)


“future-proof”: capable of supporting multiple namespaces & inter-operability
Introduce a “self-organizing” virtual id (vid) layer




a layer 2/layer-3 convergence layer: vid – dynamically assigned “locator”
subsume layer-2/layer-3 routing & forwarding functionalities
except for first/last hop: host to switch or switch to host for backward compatibility
 layer-3 addresses (or higher layer names): global “addressing” or naming for
inter-networking and “persistent” identifiers
“DHT-style” routing using a topology-aware, structured vid space
 highly scalable and robust: built-in support for multi-path, fast rerouting


O(log N) routing table size, localize failures, enable fast rerouting
support multiple topologies or virtualized network services
Virtual ID layer and VID space
11
Topology-aware, structured virtual id (vid) space



Kademlia-like “virtual” binary tree (other structures can also be used)
vid: encode (topological) location info (a “locator” a la Cisco LISP or HIP)
IPv4/IPv6 DNS Names
Other
Namespace
1
0
1
1
0
Virtual ID Layer
1
0
C
A
B
M
D
E
F
N
G
H
J
K
Layer 2 Physical Network
Topology
L
0
0
0
1
0
1
10
1
0
0
1
1
0
1
0
1
1
0
1
1 0 1 0 1 0 1 0 10 1 0 10
1 0 10 1
A - B - C - D - M- N - - - - - E - F - G - H - J - - - K - L -
VIRO: Three Core Components
12

Virtual id space construction and vid assignment


Performed at the bootstrap process (i.e., network set up):
Once network is set up/vid space is constructed:



VIRO routing algorithm/protocol:


a new node (a “VIRO switch”) joins: assigned based on neighbors’ vid’s
end-host/device: inherits a vid (prefix) from “host switch” (to which it is attached), plus a
randomly assigned host id; host may be agnostic of its vid
switch
L
vid
DHT-style, but needs to build end-to-end connectivity/routes
 a bottom-up, round-by-round process, no network-wide control flooding
 O(log N) routing entries per node, N ≈ # of VIRO switches
DHT based name/identifier to address/locator mapping service

Data forwarding among VIRO switches using vid only
host
idl
Vid Assignment: Bootstrap Process
13
Initial vid assignment and vid space construction performed during
the network bootstrap process
Via either a centralized (top-down, for “managed” networks) or
distributed (bottom-up, for “ad hoc” nets) vid assignment algorithm


0
M
0
C
0
A
D
E
B
N 0
0 G
0
0
H
0
0
F
0
0
0100
0000
A
C
B
0010
0
\
C
0
L
0
J
00 A
B
B
K
10
1000
M
0000
E
G
0100
F
0010
H 0110
1000
J
K
1100
L
1110
000
A
010
C
B
M
10
N
D 10
G
10
H
00
J
E
00
F
10
00
110
N 010
110
H
D
G
100
000
E
000
F
010
L 10
K 00
000
M
100
N 1001
D 0110
00
00
J
K 100
L 110
Vid Assignment : Key Properties
14
01000
M
Key invariant properties:
N01001
H 10110 closeness: if two nodes are
D 00110
close in the vid space, then they
G
11000
are also close in the physical
L
10100
10000
J
E
11110 topology esp., any two logical
F
K
neighbors must be directly
10010
11100
connected.
connectivity: any logical sub0
1 1
trees must be physically
0
11
connected.
11
0
00100
C
00000
A
B
00010
0
11
00
00 1
00
00 1
1
0
1
00 11
1 0
00
11
0
11
00
1
1
0 11
00
0
11
11
00
1
1 01 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
A- B - C - D - M- N - - - - - E - F - G- H - J - - - K - L -
Vid based distance: Logical distance
15

Logical distance defined on the vid space
d(vidx, vidy) = L – lcp (vidx,vidy)
L: max. tree height; lcp: longest common prefix
e.g. d(00001, 00111) = 5 – lcp(00001, 00111)
=5–2=3
d(01001, 01011) = 5 – lcp(01001, 01011)
=5–3=2
VIRO Routing: Some Definitions
16
For k =1, …, L, and any node x:
• (level-k) sub-tree, denoted by Sk(x):
• set of nodes within a logical distance of k from x
• (level-k) bucket, denoted by Bk(x):
• set of nodes exactly k logical distance from node x
• (level-k) gateway, denoted Gk(x):
• a node in Sk-1(x) which is connected to a node in Bk(x) is a gateway to reach Bk(x)
for node x; a direct neighbor of x that can reach this gateway node is a next-hop for
this node 0
1
0
1
0
0
0 1
–
0
0
1
10
1
Example:
1
1
0
0
1
1
0
1
0
1
1
0
1 011 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
A - B - C - D - M- N - - - - - E - F - G - H - J - - - K - L -
S1(A)= {A},
S2(A) ={A,B}, B2(A)={B}
G2(A)={A},
S3(A) = {A,B,C,D}
B3(A) = {C,d}
G3(A) = {A,B}
VIRO Routing: Routing Table Construction
17
Bottom-up, round-by-round, “publish-&-query” process:
 round 1: neighbor discovery


discover and find directly/locally connected neighbors
round k ( 2 ≤ k ≤L):


build routing entry to reach level-k bucket Bk(x)
-- a list of one or more (gateway, next-hops)
use “publish-query” (rendezvous) mechanisms
Algorithm for building Bk(x) routing entry at node x:



if a node(x) is directly connected to a node in Bk(x), then it is a gateway for Bk(x),
and also publishes it within Sk-1(x).
 nexthop to reach Bk(x) = direct physical neighbor in Bk(x)
else node x queries within Sk-1(x) to discover gateway(s) to reach Bk(x), choose the
logically closest if multiple gateways.
 nexthop to reach Bk(x) = nexthop(gateway)
Correctness of the algorithm can be formally established.
VIRO Routing: Routing Table
18
01000
00100
1
-
-
3
-
-
..
..
..
L
-
-
00110
N
G
B
F
11110
11100
1
1
1
1
0
0
0 1
0
0
1
10
L
K
10010
0
0
10110
11000
J
E
00010
H
10100
10000
-
2
D
A
Gateway Nexthop
01001
C
00000
Level
M
1
0
0
1
1
0
1
1
1
0
1 011 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
A - B - C - D - M- N - - - - - E - F - G - H - J - - - K - L -
VIRO Routing: Packet Forwarding
19

To forward a packet to a destination node, say, L



compute the logical distance to that node
Use the nexthop corresponding to the logical distance for forwarding
the packet
If no routing entry:

drop the packet
01000
Bucket Gateway Nexthop
Distance
1
-
-
2
A
B
3
A
C,D
4
C
C
5
B
B
00100
00000
M
01001
C
D
A
00110
B
H
G
11000
10100
10000
00010
N
J
E
F
10010
K
11100
10110
L
11110
Multiple routing entries: An example
20
1
0
1
1
0
1
0
0
0
A - B -
0
1
1
0
1
1
0
C - D - M - N -
0
1
1
0
0
1
01 1
0
1 0
1
- - - - E - F -
0
1 0
1
0
1
1
G - H -
0
1
1 0
0
1
J - - -
0
1 0
1
K - L -
Multiple Routing Entries
21

Learn multiple gateways at each level
 Default

gateway is the one that is logically closest
Use additional gateways for multi-pathing and fast
failure re-routing
 Requires
consistent gateway selection
 Otherwise
 Use
forwarding loops may occur
appropriate “forwarding directive” while using
alternate gateways
pid to vid translation
22

DHT Style lookup/store mechanism
 Simple

and scalable
A backward compatible approach to work with
Ethernet based protocols
 Re-use
ARP (address resolution protocol) to perform IP
to vid mapping
 Assumes
IP address as the pid for the host-devices
 Simple modification to ARP will allow any host namespace to
vid mapping
VIRO: <IP/MAC, vid> Mapping
23

Host-switch:




a switch directly connected to the host
vidiscover host MAC/IP through ARP, and assign d to host
host-switch publishes pid  vid mappings at an “access-switch”
Access-switch:

a switch whose vid is closest to hash (IP address of the host)
Sz Access-switch for y
IPy
VIDy
register mapping
IPy  VIDy
Sx
x
An example using IP address as pid
Sy
Host-switch for y
IPy
y
MACy
VIDy
Address/vid Lookup & Data Forwarding
24


Use DHT look-up for address/vid
resolution with local cache
vid to MAC address translation at
last-hop
Mapping Table at Sz
IP Address
VID
IPy
VIDy
Switch Sz
3. ARP Reply
(IPy  VIDy)
1. ARP Query
(IPy  MAC?)
Switch Sx
x
4. Ethernet Packet
(MACx  VIDy)
2. ARP Query
Forwarded as
Unicast request
(IPy  MAC?)
6. Sy changes
destination
MAC address
Ethernet Packet
(VIDx  MACy)
Switch Sy
5. Sx changes
source MAC address
Ethernet Packet
(VIDx  VIDy)
y
Seamless Host Mobility: An illustration
25
Mapping Table at Sz
Switch Sz
Host y’s vid is
VIDynew
IP Address
VID
Mapping Table at Sz
IPy
VIDy
IP Address
VID
IPy
VIDynew
Host y is vid is
VIDynew
Switch Sw
Switch Sx
x
ARP reply packet
containing the new Switch Sy
vid of host y
y
Outline
26

Introduction and Motivation




VIRO




Virtual ID layer
Routing Table Construction
vid lookup & Forwarding
Evaluation



Current Trends
Challenges
Recent Proposals
Simulation based Setup
Real Implementation and Prototyping
Summary and On-going work
Initial Evaluation using Simulations
27




Used various AS and data center network topologies
VIRO is compared against link-state routing protocol (e.g., OSPF)
Compared routing stretch, routing table size, control overhead,
failure dynamics, etc.
Simulation code implemented in JAVA
AS Topologies
AS1755(295 nodes,
543 edges)
AS3967(353 nodes,
820 edges)
AS6461(654 nodes,
1332 edges)
Data Center
Topologies
DC125(125 nodes,
500 edges)
DC320(320 nodes,
2048 edges)
DC500(500 nodes,
4000 edges)
BRITE Topologies
BT200(200 nodes,
790 edges)
BT400(400 nodes,
1590 edges)
BT600(600 nodes,
2390 edges)
Evaluation: Routing Table Size
28
VIRO: O(log N) routing entries,
compared to O(N) for link state
Evaluation: Control Overhead
29
Significant reduction in control overhead per node
(VIRO-1,2,4 with 1,2 and 4 rendezvous nodes at each level, VIRO-log
has log(k) rendezvous nodes at kth level
Evaluation: Routing Stretch
30
Routing in VIRO is not optimal, but it is close!
VEIL-Click: An initial prototype
31


Implementation of VIRO/VEIL architecture using
Click Modular Router framework
VEIL-Click enabled switch consists of:
A
linux machine
 Multiple network interfaces
 Click Modular Router
 VEIL as Click elements
Summary
32

VIRO provides a scalable & robust substrate for future networks



Support for multiple namespaces


No flooding in both data and control planes
Back up routing entries for robustness
Essential for seamless mobility
VIRO can be realized!

VEIL (Virtual Ethernet ID Layer) for large-scale layer-2 networks





Backward compatible
 compatible with current host protocols (such as ARP etc)
Enables (nearly) configuration-free networks
Built-in support for Multi-path routing
Extensible to support multiple topologies, virtualized network services
Ongoing work:


Prototype using Click & OpenFlow switches
Extensions to enable multiple ‘virtual’ topologies, management control plane…
Thanks!
Please visit http://networking.cs.umn.edu/veil for:
o Demo videos,
o List of related publications,
o Source code!
Thanks!
Or simply search online for “VIRO VEIL”
VIRO Routing: Example
34

Round 1:


each node x discovers and learns about its directly/locally connected
neighbors
build the level-1 routing entry to reach nodes in B1(x)
E.g. Node A: discover two direct neighbors, B,C,D;
build the level-1 routing entry to reach B1(A)={}
01000
Bucket Gateway Nexthop
Distance
1
-
-
2
A
B
3
A
C,D
Routing Table for node A
00100
00000
M
01001
C
D
A
00110
B
H
G
11000
10100
10000
00010
N
J
E
F
10010
K
11100
10110
L
11110
VIRO Routing: Example …
35

Round 2:
if directly connected to a node in B2(x), enter self as
gateway in level-2 routing entry, and publish in S1(x)
 otherwise, query “rendezvous point” in S1(x) and build the
level-2 routing entry to reach nodes in B2(x)

E.g. Node A: B2(A)={B};
node A directly connected to node B;
publish itself as gateway to B2(A)
01000
00100
Bucket Gateway Nexthop
Distance
1
-
-
2
A
B
3
A
C,D
Routing Table for node A
00000
M
01001
C
N
D
A
00110
00010
G
11000
10100
10000
B
H
J
E
F
10010
K
11100
10110
L
11110
VIRO Routing: Example …
36

Round 3:
if directly connected to a node in B3(x), enter self as gateway
in level-3 routing entry, and publish in S2(x)
 otherwise, query “rendezvous point” in S2(x) and build the
level-2 routing entry to reach nodes in B3(x)

E.g. Node A: B3(A)={C,D};
A publishes edges A->C, A->D to “rendezvous point” in S2(A), say, B;
01000
00100
Bucket Gateway Nexthop
Distance
1
-
-
2
A
B
3
A
C,D
00000
M
01001
C
N
D
A
00110
00010
G
11000
10100
10000
B
H
J
E
F
10010
K
11100
10110
L
11110
VIRO Routing: Example …
37

Round 4:


if directly connected to a node in B4(x), enter self as gateway in level4 routing entry, and publish in S3(x)
otherwise, query “rendezvous point” in S3(x) and build the level-4
routing entry to reach nodes in B4(x)
E.g. Node A: B4(A)={M,N};
A queries “rendezvous point” in S3(A), say, C; learns C as gateway
Bucket Gateway Nexthop
Distance
1
-
-
2
A
B
3
A
C,D
4
C
C
01000
00100
00000
M
01001
C
N
D
A
00110
B
G
11000
10100
10000
00010
H
J
E
F
10010
K
11100
10110
L
11110
VIRO Routing: Example …
38

Round 5:
 if directly connected to a node in B5(x), enter self as gateway in level-5
routing entry, and publish in S4(x)
 otherwise, query “rendezvous point” in S4(x) and build the level-4
routing entry to reach nodes in B5(x)
E.g. Node A: B5(A)={E,F,G,H,J,K,L};
A queries “rendezvous point” in S4(A), say, D; learns B as gateway
01000
Bucket Gateway Nexthop
Distance
1
-
-
2
A
B
3
A
C,D
4
C
C
5
B
B
00100
00000
M
01001
C
D
A
00110
B
H
G
11000
10100
10000
00010
N
J
E
F
10010
K
11100
10110
L
11110
Evaluation: vid Assignment
39
Smaller logical distance  shorter physical distances
Evaluation: Localized effect of failure
40
Nodes farther from failed node/link are lesser affected by the
failures!
Evaluation: Failure Fast Rerouting
41
No disconnection during small failures.
(VIRO with 1, 2, and 4 gateways in the routing table
For fast failure rerouting)
Evaluation: Rendezvous Node Overhead
42
Topology: AS3967
(VIRO with 1, 2, and 4 and log(k) rendezvous node at any
kth level sub-tree)
Overhead can be significantly reduced by having more
Rendezvous nodes at higher levels!
Evaluation: Failure Overhead
Total number of failure update
messages
43
VIRO has much lesser overhead to handle the failure
notifications!
Other Advantages/Features
44

Can support multiple namespaces, and inter-operability among such
namespaces (e.g., IPv4<->IPv6, IP<->Phone No., etc.)



Fast rerouting can be naturally incorporated


VIRO: “native” naming/address-independent
simply incorporate more <namespace, vid> directory services
no additional complex mechanisms needed
Support multiple topologies or virtualized network services


e.g., support for VLANs
multiple vid spaces may be constructed


e.g., by defining different types of “physical” neighbors
Also facilitate security support


host and access switches can perform access control
“persistent” id is not used for data forwarding

eliminate flooding attacks
Robustness: Localized Failures
45
00100
00000
01001
N
D
A
00100
M
C
00110
00010
H
11000
J
E
F
10010
10110
00000
01001
N
D
00110
L
11110
B
00010
G
E
F
10010
Initial Topology
10110
11000
J
After link H-L fails
11100
H
10100
10000
K
Routing table for node A
does not change despite
the failure!
M
C
A
G
10100
10000
B
Link H-L
fails
01000
01000
L
11110
K
11100
Bucket
Distance
Gateway
Nexthop
1
-
-
2
A
B
3
A
C,D
4
C
C
5
B
B