A network defined over another set of networks The overlay addresses its own nodes Links on one layer are network segments of lower layers University of California Berkeley Overlaying mechanism is called tunneling C5 4 C5 7 4 8 2 7 8 3 13 A1 12 B 3 13 5 10 12 B Overlay Networks are extremely popular MBONE Akamai Virtual Private Networks Napster Gnutella Overlay Networks may even peer Overlay Network Nodes 11 2 10 4 6 11 6 A1 A A Requires lower layer routing to be utilized Department of Electrical Engineering and Computer Sciences A 0 7 1 5 4 8 6 7 8 6 11 2 11 2 10 10 c 1 3 13 1 12 3 a 13 d 12 b ATM links can be the physical layer for IP 1 0 5 4 7 8 6 11 2 10 Underlying Network c 1 3 a 13 d 12 b Virtual Circuit under Datagram 2 The underlying network induces a complete graph of connectivity The underlying network induces a complete graph of connectivity No routing required No routing required 10 100 But 200 90 Underlying Network 90 10 100 100 20 One virtual hop may be many underlying hops away Latency and cost vary significantly over the virtual links State information may grow with E n 2 10 3 0 The underlying network induces a complete graph of connectivity No routing required 1 But Underlying Network No routing required 2 But One virtual hop may be many underlying hops away Latency and cost vary significantly over the virtual links State information may grow with E n 2 3 4 0 The underlying network induces a complete graph of connectivity One virtual hop may be many underlying hops away Latency and cost vary significantly over the virtual links State information may grow with E n 2 5 2 1 2 1 3 2 3 5 4 Message from 4 5 Message from 4 4 3 2 1 1 2 4 5 4 1 3 1 5 2 5 1 Extreme Inefficiencies Possible 0 1 3 4 1 45 64 The underlying network induces a complete graph of connectivity 1 No routing required 2 a Physical Topology b Naive unicast transmission c IP multicast d Application level multicast But One virtual hop may be many underlying hops away Latency and cost vary significantly over the virtual links State information may grow with E n 2 3 4 At any given time the overlay network picks a connected subgraph based on nearest neighbors 5 How often can vary Also structured Chord v s unstructured Gnutella From Computer Networks by Peterson Davie 7 8 64 Three kinds of Overlays 1 Only Hosts Peer to Peer Networks P2P 2 Only Gateway nodes Infrastructure Overlays m5 Example Gnutella Napster Content Distribution Networks CDNs Example Akamai 3 E m6 F E Host and Gateway Nodes E Virtual Private Networks Overlay node structure E m5 Regular Chord Pastry Adhoc Gnutella m1 m2 m3 m4 m5 m6 m1 Route Enhancement Better QoS Application Level Multicast Resource Discovery P2P 2 m4 C A Functions D A B C D E F B m3 m2 3 64 Assume m1 s neighbors are m2 and m3 m3 s neighbors are m4 and m5 Distribute file location Idea multicast the request Hot to find a file m5 Send request to all neighbors Neighbors recursively multicast the request Eventually a machine that has the file receives the request and it sends back the answer E m6 F E Advantages E Totally decentralized highly robust Not scalable the entire network can be swamped with request to alleviate this problem each request has a TTL E C A B m1 m4 E Disadvantages D E 3 m3 m2 0 8 Overlay network users are not directly connected to the overlay nodes Infrastructure Overlays E g Akamai Adding performance and route functionality Resource Discovery 1 2 4 5 P2P Overlays Resource Discovery in Gnutella 3 Example of an Infrastructure Overlay Application Level Multicast Example of a P2P Overlay Content Addressable Networks Conclusions 1 5 Overlay network users are not directly connected to the overlay nodes E g Akamai 2 User must be redirected to a close by overlay node Edge Mapping or redirection function is hard since IP 5 3 potential users enormous User clients not under direct control 4 When overlay clients are directly connected the edge mapping function is obviated 5 1 5 Overlay nodes interconnect clients Enhance nature of connection 2 Multicast Secure Low Loss Much easier to add functionality than to integrate into a router IP 5 3 4 5 E g P2P users nodes colocated 4 1 Overlay nodes interconnect clients Enhance nature of connection 2 Multicast Secure Low Loss Overlay network may contain resources Eg 1 3 E g find the least loaded server that has a piece of content and that has low network latency to client B 5 A B C A D Client makes request for resource Overlay must search for closest node that has the resource D E 4 Servers Files 2 B F 5 4 B Much easier to add functionality than to integrate into a router Overlay nodes can become bottlenecks 3 Overlay network may contain resources Eg D B 1 B F 2 3 A C D E 4 1 B F Client makes request for resource Overlay must search for closest node that has the resource D E 3 A C D E 4 A single index is not scalable Overlay launches a query to locate resource Query is Routed through the overlay until object is located A D 2 E g find the least loaded server that has a piece of content and that is has low network latency to client B 5 A B C Servers Files 2 F C A single index is not scalable Overlay launches a query to locate resource A D B B E g find the least loaded server that has a piece of content and that is has low network latency to client B 5 A B C D Client makes request for resource Overlay must search for closest node that has the resource D E F C Overlay network may contain resources Eg Servers Files B B 1 B F 2 3 4 A C D E 4 A B C 5 D 4 B F Client makes request for resource Overlay must search for closest node that has the resource D E 4 F C 3 4 A C D E A single index is not scalable Overlay launches a query to locate resource Query is Routed through the overlay until object is located A D Servers Files 2 B E g find the least loaded server that has a piece of content and that is has low network latency to client B B 1 Client makes request for resource Overlay must search for closest node that has the resource D E 4 F C Overlay network may contain resources Eg Servers Files B 3 Overlay network may contain resources Eg D 4 A B C 5 E g find the least loaded server that has a piece …
View Full Document
Unlocking...