Transcript jing2-5-04

A Routing Underlay for Overlay Networks
Akihiro Nakao
Larry Peterson
Andy Bavier
SIGCOMM’03
Reviewer: Jing lu
Motivation

Increasing growth of overlay services:
Motivation

Increasing growth of overlay services:



Common characteristic:


Content distribution network
Multicast overlay
Application-specific routing strategy
Approach:

Ping and traceroute to learn underlying Internet
topology
Motivation

Scalability Issues:

In the number of participating nodes


Multiple overlays run on a single node/subnet.


RON (Resilient Overlay Networks) doesn’t scale beyond
50 nodes.
PlanetLab is an overlay-hosting platform.
Observation:

Network itself has multiple viewpoints, and already has a fairly
complete picture of the network. Single overlay network rediscovers this information for just itself is redundant and
architecturally silly.

Routing underlay can provide a shared set of topology
discovery services for overlays, making overlay resource
discovery more scalable.
Architecture

Some representative overlays:



RON routing overlay
End-system Multicast (ESM) overlay
Peer-to-peer systems
Architecture

RON routing overlay (MIT)



Discover good-quality paths through overlay nodes,
and quickly turn to an alternate path when
congestion or failure happens to the current path.
A clique of N overlay nodes; Probe N2 edges to get
latency; Run link-state routing algorithm to find the
lowest cost routes; Not scale for N > 50.
Routing underlay can provide:


Sparsely connected routing mesh of overlay nodes to
decrease number of probes;
Or, some disjoint paths, and let RON probe just these
paths to select the best one. Should one path fails, RON
can switch to another.
Architecture

ESM overlay:



End systems in a multicast group self-organize into
an overlay structure using distributed protocol.
Adapt to network dynamics and consider
application level performance to achieve high
efficiency.
Organize end hosts into a mesh; run MST
algorithm to produce a multicast tree.
Routing underlay can provide:


Nearest neighbors
Or, ready-built routing mesh based on knowledge of the
underlying network topology.
Architecture

P2P systems like file sharing networks

Routing underlay can provide:


Nearest neighbors to peer with
Or, far-away neighbors for data replication in case of local
disasters.
Architecture

Useful underlay services:




Find nearest neighbors to a node
Find disjoint paths between two nodes
Build a routing mesh
Three primitives underlay should support:



Provide a graph of the network connectivity at a
specified resolution (ASes, Routers, physical links)
and scope (the Internet, some AS, everything within a
radius of N hops);
Expose actual route a packet traverses at a specified
resolution;
Report topological facts about specific paths between
a pair of points according to a specified metric (AS
hops, router hops, latency).
Architecture

Features:


Underlay probes the entire network to provide relative
static information about the network in low frequency.
Overlay probes dynamically changing network
conditions in a reduced scope with higher frequency.
Architecture

Will routing underlay be accepted?

Infrastructure-based overlays like PlanetLab:


“Enforcement” by implementing the probing layer in the
OS kernel.
Pure end-system overlays:



Underlay service is convenient for application writers.
Probing traffic becomes a widely-recognized problem.
“Encouragement” from ISPs and network administrators
by blocking ping and traceroute traffic
Topology Probing kernel

Assumptions:


Primitives are support on every overlay node, which
has access to the BGP routing table at a nearby BGP
router.
Three primitives:



Peering Graph
Path Probe
Distance Probe
Topology Probing kernel

Peering Graph:
PG = GetGraph()

Coarse-grain (AS-level) connectivity of the Internet,
where each vertex in PG corresponds to an AS, and
each edge represents a peering relationship between
ASes.



All overlay nodes send their BGP tables to a centralized
aggregation point.
Each overlay node constructs its own PG independently by
exchanging PG with neighbors.
PG can be constructed using a fixed number of
probes; Peering information changes infrequently,
so exchange can be done in low frequency.
Topology Probing kernel
Topology Probing kernel

Path Probe:
Path = GetPath(src, dst)

Verified AS path traversed by packets sent from IP
address src to IP address dst.


Use BGP table to get the actual AS path.
Distance Probe:
Distance = GetDistance(target, metric)


Distance from the local node to remote target node.
Distance metrics:



Number of AS hops
Number of router hops
RTT
Library of Routing Services

Find Disjoint Paths:


PathSet = DisjointPaths(u, v, N, k)
u, v are a pair of overlay nodes;
N is a set of candidate intermediate nodes;
k disjoint paths.
Implementation:



Use peering graph returned by GetGraph to guess the
shortest disjoint paths (u, w, v), w  N; Sort the list by AS
count.
Use GetPath to verify and drop paths that are not edgedisjoint from the default AS path.
Select k paths based on AS hop count.
Library of Routing Services

Find Nearest Neighbors:


Nodes = NearestNodes(N, k)
N is a set of candidate neighbor nodes;
k closest to the local node.
Implementation:


Use GetPath to sort the list of N neighbors by AS count;
Use GetDistance on the top j (j > k) nodes in the list to
choose k nodes with lowest latency.
Library of Routing Services
Library of Routing Services

Building a Representative Mesh:


Mesh = BuildMesh(N)
N is a set of overlay nodes;
Implementation:




Each overlay node performs analysis (pruning edges)
independently using GetPath primitive. Entire mesh can be
formed by aggregating all the neighbor sets.
Algorithm 1: Prune edge (u, v) if AS path from u to v
includes AS W, where w  N is located.
Algorithm 2: Prune edge (u, v) if w is directly connected to
the AS path from u to v.
In both cases, a node need s to keep track of virtualized
edges and verify virtualization information with neighbors
before pruning.
Library of Routing Services
Library of Routing Services
Conclusion

Overlay networks independently probing the
Internet to make application-specific routing
decisions is unacceptable in the long run.

A shared routing underlay is practical.


Take cost into account
Multiple-layered


Lower layers provide coarse-grain static information at
large scale.
Upper layers probe more frequently for dynamic
information at increasingly reduced scale.