1 Department of Electrical Engineering and Computer SciencesUniversity of CaliforniaBerkeley !" #$# $!$ #%& A network defined over another set of networksThe overlay addresses its own nodesLinks on one layer are network segments of lower layersRequires lower layer routing to be utilizedOverlaying mechanism is called tunnelingA’' !$ $ (AA !" #$# $!$ #%& $ )$*+3121210131167854ABCOverlay Network Nodes !" #$# $!$ #%& , $ )$*+3121210131167854ABC Overlay Networks are extremely popular MBONE, Akamai, Virtual Private Networks, Napster, Gnutella Overlay Networks may even peer! !" #$# $!$ #%& - $ )$*.$3121210131167854 !" #$# $!$ #%& /0 ! 13121210131167854abdcATM links can be the “physical layer” for IP2 !" #$# $!$ #%& 20 ! 3121210131167854abdcVirtual Circuit under Datagram! !" #$# $!$ #%& UnderlyingNetwork"$*$! !" #$# $!$ #%& 3UnderlyingNetwork"$*$! The underlying network induces a complete graph of connectivityNo routing required! !" #$# $!$ #%& "$*$! The underlying network induces a complete graph of connectivityNo routing required!ButOne virtual hop may be many underlying hops away. Latency and cost vary significantly over the virtual linksState information may grow with E (n^2)101002001009010010102090 !" #$# $!$ #%& UnderlyingNetwork"$*0 The underlying network induces a complete graph of connectivityNo routing required!ButOne virtual hop may be many underlying hops away. Latency and cost vary significantly over the virtual linksState information may grow with E (n^2) !" #$# $!$ #%& "$*0 25431The underlying network induces a complete graph of connectivityNo routing required!ButOne virtual hop may be many underlying hops away. Latency and cost vary significantly over the virtual linksState information may grow with E (n^2)3 !" #$# $!$ #%& " $*! *! $# $*$ 25431Message from 4 1 !" #$# $!$ #%& ," $*! *! $# $*$ 25431 25431Message from 4 14 3 2 14 1 3 1 5 2 5 1Extreme Inefficiencies Possible !" #$# $!$ #%& -"$*0 25431The underlying network induces a complete graph of connectivityNo routing required!ButOne virtual hop may be many underlying hops away. Latency and cost vary significantly over the virtual linksState information may grow with E (n^2)At any given time, the overlay network picks a connected sub-graph based on nearest neighborsHow often can varyAlso, structured (Chord) v/sunstructured (Gnutella) !" #$# $!$ #%& /$# 4564 a) Physical Topologyb) Naive unicast transmissionc) IP multicastd) Application level multicastFrom “Computer Networks”, by Peterson & Davie !" #$# $!$ #%& 2 Three kinds of Overlays1.Only Hosts: Peer to Peer Networks (P2P)Example: Gnutella, Napster2.Only Gateway nodes: Infrastructure OverlaysContent Distribution Networks (CDNs)Example: Akamai3.Host and Gateway Nodes: Virtual Private Networks Overlay
View Full Document