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.