iKen BirmanCornell University. CS5410 Fall 2008. Network Overlaysy Consider the Internety It creates the illusion of a fully connected n x n world of dd bl ditaddressable endpointsy In reality, packets must route through a complex infrastructure, but the end user doesn’t see that ,infrastructurey Overlay concept takes this one step furthery We focus on some application… and create a dedicated personal internet just for ityThe dedicated network might have special propertiesyThe dedicated network might have special propertiesUses of overlaysy Load balancing, other forms of quality of servicey Distributing files or data down some form of tree (ll i fih fi structure (allows massive fanouts without forcing any single node to send huge numbers of copies)yRoute around congestionyRoute around congestiony Content routing: packets routed on the basis of the data insidethem(couldlook atfields, or mightdo a data insidethem(couldlook atfields, or mightdo a whole xquery)y Publish subscribe: packets route on the basis of topicy DHT : In fact, even a DHT is an overlay!Early Overlaysy The first overlays were really Internet “tunnels”y Idea was to encapsulate IP packets in some other tk tddnetwork standardy … then route them over a link that used non‐IP technologygyy … then unpack them and drop them back into IP‐landy Then we started to see fancier tunnelsy IP multicast over TCPy IPv6 over IPv4Tunneling IllustratedStep 2pOriginal IPpacketencapsulatedin another IPpacketRouter AWorkstationRouter BWorkstationYpacketOriginal IPpacketNew IPPacketTunnelOriginal IPpacket dest YTunnelWorkstationXOriginal IPpacket dest YStep 1.Original, unroutableIP Packet sent to routerStep 3Original packetextracted, sentto destinationWidely known overlaysy Virtual private networksy End point computers need to have some form of tifi t th t th t id tif th lcertificate that they use to identify themselvesy Typically: each machine has a private key and a public keyyWith this can send “unforgeable” encrypted datagypy So: edge machine authenticates itself to the VPN server, which sends back the current secret key of the VPN (a symmetric key)yThe edge machine tunnels traffic encrypted with the VPN key yThe edge machine tunnels traffic encrypted with the VPN key via the VPN server, which acts as a routerVirtual Dial‐up Example (1)Virtual Dial‐up Example (1)Internet Service ProviderPublic Switched Tl hTunnelGatewayGateway(NAS)Internet Service ProviderTelephone Network (PSTN)Internet(NAS)WorkerHome Networky Worker dials ISP to get basic IP serviceMachiney Worker creates his own tunnel to Home Netw orkVirtual Dial‐up Example (2)Virtual Dial‐up Example (2)Internet Service ProviderPublic Switched Tl hTunnelGateway(NAC)Gateway(NAS)Internet Service ProviderTelephone Network (PSTN)Internet(NAC)(NAS)Home Networky Remote worker connects to Home Netw ork through ISP created tunnelthrough ISP created tunnely Allows wholesale dial‐upLogical NetworkCreationLogical Network CreationGtGtNetwork 1InternetTunnelGateway(NAC)Gateway(NAS)y Remote networks 1 and 2 create a logical networkNetwork 2gy Secure communication at lowest levelOther uses for overlaysy New York Stock Exchange Quote Distribution Systemy Built around 1995y Issue: needed a customizable way to route quotes to overhead displays over internal networkyRequired fault‐toleranceyRequired faulttolerancey Content sources ran at higher speeds than most display end systems could sustainBasic idea…y Build a routing tree for quotesχsourceχχy Then replicate it for fault‐toleranceχχsourceχχχχχComponentsy The source systems were the five or six “clearing” machines used by the NYSE to capture trades, bids, offered pricesoffered pricesy The routers were inexpensive dedicated computers with dual ethernetcards one for each networkwith dual ethernetcards, one for each networky Each network was a separate ethernet with distinct IP addresses and no automated routinggy The overhead displays were basically workstationsFault‐toler ancey They used a virtual synchrony package (Isis) to replicate state within router pairs, and to track subscription patternssubscription patternsReplicate router stateReplicate subscription patternssourceχχχχχpatternsχχχy … lots of groupsWhy an overlay?y Isis wasn’t capable of supporting very large groups with very high data ratesS di h l d/ ’ fiblySo sending the actual trades/quotes wasn’t feasibley Total number of routers was about 75… serving 1000 or more display systemsmore display systemsyBy building a TCP‐based overlay and using the Isis By building a TCPbased overlay and using the Isis groups “out of band”, Isis wasn’ t on the critical pathy Isis knew about the dual IP network… TCP didn’t.Outcome?y The solution was completely robust and was used from 1995 until mid 2006Di h dd h fil d yDuring that decade there were many failures and even entire network outagesyBut the NYSE “rode them all out” absolutely But the NYSE rode them all out absolutely unperturbed: traders saw no glitches at ally So here the overla y plays two rolesy Overlay carries the heavy communication burdenl f h ky One ov erlay for each IP networkResilient Overlay NetworksRon Slideshttp://nms.lcs.mit.edu/ron/Final example for toda y: P6Py Research by Li Dong Zhou and Van Renessey Issue addressed by this worky People want to use IPv6y But the Internet itself is locked into IPv4S id i IP 6 lySo idea is to support IPv6 as an ov erlayFt f IP 6?yFeatures of IPv6?y Very long addresses (64 bits)yAddress doesn’t rev eal location (unlike IPv4)yAddress doesn t rev eal location (unlike IPv4)How P6P worksy Assumes two worldsy An IPv6 world, invisible to themyAn IPv4 world, where P6P livesy Some IPv6 nodes live in both, call them “internal gateway nodes”gateway nodesy These have both an IPv6 and an IPv4 addressyP6P itself implemented by what they call “external P6P itself implemented by what they call external gateway” nodes that run in the IPv4 networkHow P6P worksy They designed a DHT based on Chordy Each IPv6 node must have an associated IG y So treat the (IPv6,IPv4) tuple as a (key,value) pair!y IPv6 address is an index into Chord P d ld (kl) iy New IPv6 node would create a new (key,value) pairy To send an IPv6 packet, look up the IPv4 helper node, then forward the IPv6 packet to the helperthen