Department of Electrical Engineering and Computer Sciences University of California Berkeley A network defined over another set of networks The overlay addresses its own nodes Links on one layer are network segments of lower layers Requires lower layer routing to be utilized Overlaying mechanism is called tunneling A A A C5 4 7 8 6 11 2 A1 10 3 13 12 B Overlay Network Nodes C5 4 7 8 6 11 2 A1 10 3 13 12 B Overlay Networks are extremely popular MBONE Akamai Virtual Private Networks Napster Gnutella Overlay Networks may even peer 5 4 7 8 6 11 2 1 10 3 13 12 0 1 5 4 7 8 6 11 2 10 c 1 3 a 13 d 12 b ATM links can be the physical layer for IP 0 5 4 7 8 6 11 2 10 c 1 3 a 13 d 12 b Virtual Circuit under Datagram 2 Underlying Network The underlying network induces a complete graph of connectivity No routing required Underlying Network 3 The underlying network induces a complete graph of connectivity No routing required 10 100 But 200 90 90 10 100 20 100 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 0 The underlying network induces a complete graph of connectivity No routing required 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 Underlying Network 0 The underlying network induces a complete graph of connectivity 1 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 5 1 2 4 5 3 Message from 4 1 1 2 3 1 2 4 5 3 4 Message from 4 4 3 2 1 5 1 4 1 3 1 5 2 5 1 Extreme Inefficiencies Possible 0 The underlying network induces a complete graph of connectivity 1 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 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 45 64 a Physical Topology b Naive unicast transmission c IP multicast d Application level multicast From Computer Networks by Peterson Davie 7 8 Three kinds of Overlays 1 Only Hosts Peer to Peer Networks P2P Example Gnutella Napster 2 Only Gateway nodes Infrastructure Overlays Content Distribution Networks CDNs Example Akamai 3 Host and Gateway Nodes Virtual Private Networks Overlay node structure Regular Chord Pastry Adhoc Gnutella Functions Route Enhancement Better QoS Application Level Multicast Resource Discovery P2P 2 64 m5 E m6 F E E E m5 m1 m2 m3 m4 m5 m6 m4 C A m1 D A B C D E F m3 B m2 Distribute file location Idea multicast the request Hot to find a file 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 Advantages Totally decentralized highly robust Disadvantages Not scalable the entire network can be swamped with request to alleviate this problem each request has a TTL 3 64 Assume m1 s neighbors are m2 and m3 m3 s neighbors are m4 and m5 m5 E m6 F E E D E m4 E E C A m1 m3 B m2 Infrastructure Overlays Adding performance and route functionality Resource Discovery P2P Overlays Resource Discovery in Gnutella Example of an Infrastructure Overlay Application Level Multicast Example of a P2P Overlay Content Addressable Networks Conclusions 0 8 Overlay network users are not directly connected to the overlay nodes E g Akamai 1 2 4 5 3 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 E g P2P users nodes colocated 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 1 Overlay nodes interconnect clients Enhance nature of connection 2 Multicast Secure Low Loss Much easier to add functionality than to integrate into a router Overlay nodes can become bottlenecks 3 4 5 Overlay network may contain resources Eg 1 Servers Files 2 Client makes request for resource Overlay must search for closest node that has the resource B D E B F 3 E g find the least loaded server that has a piece of content and that has low network latency to client B 4 A B C 5 A D Overlay network may contain resources Eg D B 1 Servers Files 2 Client makes request for resource Overlay must search for closest node that has the resource B B F D E F C 3 A C D E 4 A B C 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 single index is not scalable Overlay launches a query to locate resource A D 2 Overlay network may contain resources Eg D B 1 Servers Files 2 Client makes request for resource Overlay must search for closest node that has the resource B B F D E F C 3 A C D E 4 A B C 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 single index is not scalable Overlay launches a query to locate resource Query is Routed through the overlay until object is located A D Overlay network may contain resources Eg D B 1 Servers Files 2 Client makes request for resource Overlay must search for closest node that has the resource B B F D E 4 F C 3 4 A C D E 4 A B C 5 E g find the least loaded server that has a piece of content and that is has low network latency to client B 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 3 Overlay network may contain resources Eg D B 1 Servers Files 2 Client makes request for resource Overlay must search for closest node that has the resource B B F D E 4 F C 3 4 A C D E 4 A B C 5 E g find the least loaded server that has a piece of content and that …
View Full Document
Unlocking...