Application-Level Multicast RoutingWhat Is Multicast?Some Applications…Why Multicast?Network-Level (IP) MulticastProblems with IP MulticastApplication layer multicastBenefitsApplication-Level MulticastA few concerns…OvercastComponentsBandwidth Efficient Overlay TreesSelf-Organizing AlgorithmSlide 15Connecting ClientsClient joinsState Tracking – the Up/Down protocolIs The Root Node A Single Point Of Failure?EvaluationSlide 21Slide 22Overcast ConclusionEnabling Conferencing Applications on the Internet using an Overlay Multicast ArchitectureSelf-Improving AlgorithmSlide 26Slide 27Comparison of schemesBandwidth – primary set, 1.2 MbpsBandwidth – extended set, 2.4 MbpsRTT – extended set, 2.4 MbpsConclusionMore Recent WorkDiscussion QuestionsApplication-Level Multicast RoutingMichael SiegenthalerCS 614 – Cornell UniversityNovember 2, 2006A few slides are borrowed from Swati Agarwal, CS 614, Fall 2005.What Is Multicast?•Unicast–One-to-one–Destination – unique receiver host address•Broadcast–One-to-all–Destination – address of network•Multicast–One-to-many–Multicast group must be identified–Destination – address of groupKey: Unicast transfer Broadcast transfer Multicast transferFew slides are based on slides originally developed by (1) L. Armstrong, Univ of Delaware, (2) Rao - www.ibr.cs.tu-bs.de/events/netgames2002/presentations/rao.pdfSome Applications…•Streaming broadcast media–Radio–Television•Live events involving multiple parties–Video conferencing–Distance learning•Content distribution–Software–Movies•All of these involve one-to-many communicationWhy Multicast?•Traditional mechanisms for one-to-one communication do not scale–Overloading a single source–Network links carry the same traffic separately for each receiver•Multicasting solves both problems. In the ideal case:–Source only needs to transmit one or a few copies of the data–Each link only caries one copy of the dataNetwork-Level (IP) MulticastBerkeleyCornellDavisMITRouters with multicast support•Reserved a portion of the address space•Route packets to the group identified by the class D destination IP address•“You put packets in at one end, and the network conspires to deliver them to anyone who asks.” – David ClarkProblems with IP Multicast•Deployment is difficult–Requires support from routers•Scalability–Routers maintain per-group state•Difficult to support higher level functionality–Reliability, congestion control•Billing issues•As a result, barely anybody uses itApplication layer multicastDavisMITDav1Dav2Berk2Overlay TreeCornellBerk1BerkeleyCornellDav1Dav2Berk1Berk2MITBenefits•Scalability–Routers do not maintain per group state•Easy to deploy–No change to network infrastructure–Just another application•Simplifies support for higher level functionality–Can utilize existing solutions for unicast congestion controlApplication-Level Multicast•Two basic architectures are possible–Proxy-based•Dedicated server nodes exchange content among themselves•End clients download from one of the servers and do not share their data–Peer to peer•All participating nodes share the load•“End clients” also act as servers and relay data to other nodesA few concerns…•Performance penalty–Redundant traffic on physical links•stress = number of times a semantically identical packet traverses a given link–Increase in latency•stretch = ratio of latency in an overlay network compared to a baseline such as unicast or IP multicast•Constructing efficient overlays–Application needs differ•Adapting to changes–Network dynamics–Group membership – members can join and leave–Both of these contribute to churnOvercast•Single source multicast•Proxy-based architecture–Assumes nodes are well-provisioned•Reliable delivery–Software or video distribution–Buffered streaming media•“Live” could mean delayed by seconds or minutes•Long term storage at each node•Easily deployable, seeks to minimize human intervention•Works in the presence of NATs and firewallsComponents•Root : central source (may be replicated)•Node : internal overcast nodes with permanent storage–Organized into distribution tree•Client : final consumers (HTTP clients)RRoot Node ClientBandwidth Efficient Overlay Trees10 Mb/s100 Mb/s100 Mb/sR12R12R1 2R12“…three ways of organizing the root and the nodes into a distribution tree.”Self-Organizing Algorithm•A new server initially joins at the root•Iteratively moves farther down the tree–Relocate under a sibling if doing so does not sacrifice bandwidth back to the root–This results in a deep tree with high bandwidth to every node•A node periodically reevaluates its position–May relocate under a sibling–May become a sibling of its parent•Fault tolerant–If parent fails, relocate under grandparentSelf-Organizing AlgorithmR110220R12Overcast network treeRound 115R21Overcast network treeRound 2Connecting Clients•Client contacts the root via an HTTP request–Allows unmodified clients to connect–URLs provide flexible addressing•Hostname identifies the root•Pathname identifies the multicast group•Root redirects the client to a node which is geographically close to the client–Root must be aware of all nodesClient joinsR1123456R2R3Key: Content query (multicast join) Query redirect Content deliveryState Tracking – the Up/Down protocol•Each node maintains state about all nodes in its subtree–Reports the “births” and “deaths” among its children–Information is aggregated on its way up the tree•Each child periodically checks in with its parent–Support NATs/firewalls11.1 1.2 1.31.2.1 1.2.31.2.21.2.2.1Birth certificates for 1.2.2, 1.2.2.1No change observed. Propagation halted.Is The Root Node A Single Point Of Failure?•Root is responsible for handling all join requests from clients–Note: root does not deliver content•Root’s Up/Down protocol functionality can not be easily distributed–Root maintains state for all Overcast nodes•Solution: configure a set of nodes linearly from root before splitting into multiple branches–Each node in the linear chain has sufficient information to assume root responsibilities–Natural side effect of Up/Down protocolEvaluationEvaluationLease period = how long a parent will wait to hear from a child before reporting its deathEvaluationOvercast Conclusion•Designed for software,