Connectivity Restrictions in Overlay Multicast∗Aditya Ganjam and Hui ZhangCarnegie Mellon University{aganjam,hzhang}@cs.cmu.eduABSTRACTA large number of overlay multicast protocols have been developed,almost all of which assume universal connectivity between end hosts.However, in reality, this assumption is not valid with widespread useof Network Address Translators (NAT) and firewalls. The impact ofNAT and firewall connectivity restrictions on overlay multicast, es-pecially in the application-endpoint setting, has not been seriouslyconsidered. In this paper, we argue that it is critical to consider con-nectivity restrictions because NAT and firewall hosts make up a largefraction of the endpoints, affecting proper functionality as well asperformance of overlay multicast protocols. We present several de-sign enhancements that explicitly consider connectivity restrictions inoverlay multicast and evaluate the design space and tradeoffs basedon real Internet broadcasts and Internet testbed experiments.Categories and Subject DescriptorsC.2.4 [Computer-Communication Networks]: Distributed SystemsGeneral TermsDesign, PerformanceKeywordsOverlay Multicast, Peer-to-peer systems, Network Address Transla-tor, Firewall1. INTRODUCTIONEnabling ubiquitous live video broadcast over the Internet is akey application motivating overlay multicast research. Overlay mul-ticast is an architecture to deploy multicast functionality over the In-ternet where end hosts, instead of routers, perform all multicast op-∗ThisresearchwassponsoredbyDARPAundercontractnumberF30602-99-1-0518, and by NSF under grant numbers Career AwardNCR-9624979 ANI-9730105, ITR Award ANI-0085920, and ANI-9814929. Additional support was provided by Sloan Research Fel-lowship and Intel. Views and conclusions contained in this documentare those of the authors and should not be interpreted as representingthe official policies, either expressed or implied, of DARPA, NSF,Intel the U.S. government.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.NOSSDAV’04, June 16–18, 2004, Cork, Ireland.Copyright 2004 ACM 1-58113-801-6/04/0006 ...$5.00.erations. A key strength of this architecture is its flexibility in de-ployment. One could envision, at one extreme, deployment usinghighly provisioned and reliable end hosts performing multicast op-erations, as done in Akamai[2], or the other extreme, deployment us-ing a purely application-endpoint model. In the latter scenario, onlythe end hosts participating in the application perform multicast oper-ations. The application-endpoint model is very encouraging due to itslow deployment cost, namely there is no need for infrastructure de-ployment or maintenance. A number of overlay multicast protocolshave been developed, many of them in the context of the application-endpoint model [3, 4, 5, 7, 8, 9, 11, 12, 13, 15, 16, 18, 20]. However,a critical issue amplified by the application-endpoint model that theseprotocols do not seriously consider are the connectivity restrictionsimposed by Network Address Translators (NAT) and firewalls, whichhinder and even block communication between certain pairs of hosts.In [6] we describe our experience with deploying a video broad-cast application using overlay multicast. Through several live Internetbroadcasts of video content to a real audience, we have observed en-vironments where the fraction of NAT and firewall hosts in an overlaymulticast group is as high as 80%. Given that most overlay multicastprotocols assume universal connectivity, this property of the Internetposes an important question: is the performance of an overlay mul-ticast protocol significantly affected by the existence of hosts behindNAT and firewall and if so what techniques can be used to improveperformance?Through results from 9 events from our Internet deployment andInternet testbed experiments, we show that performance is severelyaffected if NATs and firewalls are not seriously considered. In thispaper, we describe three solutions to accommodate hosts behind NATand firewall in overlay multicast: Strawman, Basic Contributor andEnhanced Contributor. We observe that in a commercial environment,the Strawman solution, which treats hosts behind NAT and firewall asleaf nodes only, has a high rejection ratio(.43), or fraction of hosts notable to connect to the tree. We show that the Basic Contributor andEnhanced Contributor solutions, which increase connectivity betweenhosts and make NAT and firewall hosts capable of begin interior nodesin the tree, significantly improve the rejection ratio, where EnhancedContributor achieves a rejection ratio of 0. In addition, we proposeand show the benefits of an optimization to overlay tree construction,called Connectivity-Aware Structuring, that uses knowledge of NATand firewall hosts to construct trees with increased available resourcesfor these hosts.2. BACKGROUNDIn this section we provide a background on NATs and firewalls,discuss existing solutions to connect hosts behind NAT and firewalland outline a representative overlay multicast protocol which we usein our evaluation.54NATPublic InternetCPrivateNetworkABDFigure 1: Addressing issues with NAT2.1 NAT and FirewallThere are two network devices that hinder universal connectiv-ity of the Internet: Network Address Translators (NAT) and firewalls.NATs are widely deployed and are used to extend the IP address spaceby using private addresses and ports within a network and translatingto a smaller set of public addresses/ports when communicating out-side the network. The private addresses can be replicated at any num-ber of private networks, whereas the public addresses must be uniqueover the Internet. The translation between a private address/port to apublic address/port is created in the NAT when a packet originatingwithin the network passes through the NAT to reach its destinationoutside the private network. At this point, a packet arriving at theNAT from outside the network that matches the translation insertedinto the NAT, will be reverse translated and sent to the destination.For example, consider Figure 1. Host A behind the NAT can send apacket to host C,
View Full Document
Unlocking...