Routing on Overlay NetworksEECS 228Abhay [email protected] 28, 2002October 28, 2002Abhay K. Parekh: Topics in Routing2T A network defined over another set of networksT The overlay addresses its own nodesT Links on one layer are network segments of lower layersY Requires lower layer routing to be utilizedT Overlaying mechanism is called tunnelingT Example: Virtual Private NetworksY Virtual topology defined via VPN nodesY Telecommuters appear as though they are on the corporate networkY Sessions are more secureY Bits may traverse various kinds of underlying networks T PSTN, Frame Relay etc.A’What is an overlay network?AAOctober 28, 2002Abhay K. Parekh: Topics in Routing3UnderlyingNetworkRouting On the overlayOctober 28, 2002Abhay K. Parekh: Topics in Routing4UnderlyingNetworkRouting on the OverlayT The underlying network induces a complete graph of connectivityY No routing required!October 28, 2002Abhay K. Parekh: Topics in Routing5Routing on the OverlayT The underlying network induces a complete graph of connectivityY No routing required!T ButY One virtual hop may be many underlying hops away. Y Latency and cost vary significantly over the virtual linksY State information may grow with E (n^2)101002001009010010102090October 28, 2002Abhay K. Parekh: Topics in Routing6UnderlyingNetworkRouting IssuesT The underlying network induces a complete graph of connectivityY No routing required!T ButY One virtual hop may be many underlying hops away. Y Latency and cost vary significantly over the virtual linksY State information may grow with E (n^2)T At any given time, the overlay network picks a connected sub-graph based on nearest neighborsY How often can varyY Also, structured (Chord) v/sunstructured (Gnutella)October 28, 2002Abhay K. Parekh: Topics in Routing7Routing Issues25431T The underlying network induces a complete graph of connectivityY No routing required!T ButY One virtual hop may be many underlying hops away. Y Latency and cost vary significantly over the virtual linksY State information may grow with E (n^2)T At any given time, the overlay network picks a connected sub-graph based on nearest neighborsY How often can varyY Also, structured (Chord) v/sunstructured (Gnutella)T The overlay network must ROUTE!October 28, 2002Abhay K. Parekh: Topics in Routing8Routing Issues25431T Overlay network users may not be directly connected to the overlay nodesT E.g. AkamaiOctober 28, 2002Abhay K. Parekh: Topics in Routing9Overlay Routing: Edge Mapping25431T Overlay network users may not be directly connected to the overlay nodesT E.g. AkamaiT User must be redirected to a “close by” overlay nodeT Edge-Mapping, or redirection function is hard sinceY # potential users enormousY User clients not under direct controlT When overlay clients are directly connected the edge mapping function is obviatedY E.g. P2P: users/nodes colocatedIP(5)?October 28, 2002Abhay K. Parekh: Topics in Routing10Overlay Routing: Edge Mapping25431T Overlay nodes interconnect clientsT Enhance nature of connectionY MulticastY SecureY Low LossT Much easier to add functionality than to integrate into a routerIP(5)?October 28, 2002Abhay K. Parekh: Topics in Routing11Overlay Routing: Adding Function to the route25431T Overlay nodes interconnect clientsT Enhance nature of connectionY MulticastY SecureY Low LossT Much easier to add functionality than to integrate into a routerT Overlay nodes can become bottlenecksOctober 28, 2002Abhay K. Parekh: Topics in Routing12Overlay Routing: Resource Location25431ABCADBFBDEB?T Overlay network may contain resources. Eg.Y ServersY FilesT Client makes request for resourceT Overlay must “search” for “closest” node that has the resourceY E.g. find the least loaded server that has a piece of content and that is has low network latency to clientOctober 28, 2002Abhay K. Parekh: Topics in Routing13Overlay Routing: Resource Location25431ABCADBFBDEB?ACDBFCDET Overlay network may contain resources. Eg.Y ServersY FilesT Client makes request for resourceT Overlay must “search” for “closest” node that has the resourceY E.g. find the least loaded server that has a piece of content and that is has low network latency to clientT A single “index” is not scalableT Overlay launches a query to locate resourceOctober 28, 2002Abhay K. Parekh: Topics in Routing14Overlay Routing: Resource Location25431ABCADBFBDEB?ACDBFCDET Overlay network may contain resources. Eg.Y ServersY FilesT Client makes request for resourceT Overlay must “search” for “closest” node that has the resourceY E.g. find the least loaded server that has a piece of content and that is has low network latency to clientT A single “index” is not scalableT Overlay launches a query to locate resourceT Query is “Routed” through the overlay until object is locatedOctober 28, 2002Abhay K. Parekh: Topics in Routing15Overlay Routing: Resource Location25431ABCADBFBDEACDBFCDE44B?4T Overlay network may contain resources. Eg.Y ServersY FilesT Client makes request for resourceT Overlay must “search” for “closest” node that has the resourceY E.g. find the least loaded server that has a piece of content and that is has low network latency to clientT A single “index” is not scalableT Overlay launches a query to locate resourceT Query is “Routed” through the overlay until object is locatedOctober 28, 2002Abhay K. Parekh: Topics in Routing16Overlay Routing: Resource Location25431T Overlay network may contain resources. Eg.Y ServersY FilesT Client makes request for resourceT Overlay must “search” for “closest” node that has the resourceY E.g. find the least loaded server that has a piece of content and that is has low network latency to clientT A single “index” is not scalableT Overlay launches a query to locate resourceT Query is “Routed” through the overlay until object is located ABCADBFBDEACDBFCDE44B?4October 28, 2002Abhay K. Parekh: Topics in Routing17SummaryT Two kinds of overlays functionsY Overlay contains resourcesY Overlay facilitates communication among other client applicationsT Two kinds of virtual topologiesY StructuredY UnstructuredT Two kinds of client connectivtyY Direct: P2PY Not direct: AkamaiT Overlay Network FunctionsY Select Virtual Edges (fast or slow timescales)Y Overlay Routing ProtocolY Edge MappingY Resource LocationT Edge Mapping and Resource Location can be combinedOctober 28, 2002Abhay K. Parekh: Topics in Routing18Content ProducerMedia
View Full Document
Unlocking...