REUNITE: A Recursive Unicast Approach to MulticastIon Stoica T.S. Eugene Ng Hui ZhangMarch 2000CMU-CS-00-120School of Computer ScienceCarnegie Mellon UniversityPittsburgh, PA 15213An earlier version of this paper appeared in Proceedings of IEEE INFOCOM 2000.This research was sponsored by DARPA under contract numbers N66001-96-C-8528, F30602-99-1-0518,and E30602-97-2-0287, and by NSF under grant numbers Career Award NCR-9624979 ANI-9730105, and ANI-9814929. Additionalsupport was provided by Intel, Lucent, and Ericsson.Views and conclusions contained in this document are those of the authors and should not be interpreted asrepresenting the official policies, either expressed or implied, of DARPA, NSF, Intel, Lucent, Ericsson or the U.S.government.Keywords: Multicast routing, state reduction, incremental deployment, load balancing.AbstractWe propose a new multicast protocol called REUNITE. The key idea of REUNITE is to use recur-sive unicast trees to implement multicast service. REUNITE does not use class D IP addresses.Instead, both group identification and data forwarding are based on unicast IP addresses. Com-pared with existing IP multicast protocols, REUNITE has several unique properties. First, onlyrouters that are acting as multicast tree branching points for a group need to keep multicast for-warding state of the group. All other non-branching-point routers simply forward data packets byunicast routing. In addition, REUNITE can be incrementally deployed in the sense that it workseven if only a subset of the routers implement the protocol. Furthermore, REUNITE supports loadbalancing and graceful degradation such that when a router does not have resources (forwardingtable entry, buffer space, processing power) to support additional multicast groups, the branch-ing can be automatically migrated to other less loaded routers. Finally, sender access controlcan be easily supported in REUNITE. Although in REUNITE, routers in a multicast tree still needto maintain control path state, we discuss a variant of REUNITE in which routers do not need tomaintain any control path state. However, this is achieved at the expense of having two additionalprotocol message types, and a slightly more complex protocol.1 IntroductionIP multicast, which was proposed by Deering in 1988, has two important components: the servicemodel and routing protocols [3]. In the IP multicast service model, a group of receiver hosts canbe identified by a single class D IP group address. Any host can send to the group by settingthe destination address in the IP header as the group address. Receivers can dynamically joinand leave the group. Such a service model provides a powerful abstraction for applications asend hosts (senders and receivers) can utilize the service without having to keep track of themembership of the group. It is the responsibility of IP multicast routing protocols to maintain themembership information and to build multicast distribution trees to deliver packets from a senderto all the receivers in a group.Despite a decade of research and development, there are still open technical issues that make itdifficult to deploy IP multicast in the global Internet. From the point of view of routing, existingIP multicast routing protocols [3, 1, 5, 4, 12, 9] scale poorly with large number of groups. Inparticular, with current routing protocols, each router needs to maintain a multicast forwardingtable entry for every group whose distribution tree passes through the router. Therefore, the sizeof the multicast forwarding table needs to grow with the number of active groups, which resultsin higher router cost and lower forwarding performance. From the point of view of the servicemodel, the current model requires each new group to be allocated a globally unique address. Thisis difficult to do in a large-scale distributed environment [8]. In addition, the current model doesnot provide means to control who is allowed to send to the group – any host can send to anyIP multicast address. While this is also the case for IP unicast, the waste of network resources,disruption or denial of service by unauthorized senders can be greatly amplified in the case ofmulticast due to the potentially large number of receivers in the group [9].Several schemes (e.g., Simple Multicast [12] and EXPRESS [9]) have been proposed recentlyto tackle the address allocation and the sender access control problems. In these schemes, thereis a special node (sender or core) associated with each group and the group is identified by a two-tuple<special node’s unicast IP address, class D multicast address>. The allocation of groupaddress becomes trivial as by locally enforcing the uniqueness of the class D addresses used ateach node, the uniqueness of the two-tuples are enforced. In addition, access control of senderscan be supported by forcing all packets to go to the special node to be authenticated before being1multicasted to the receivers.While these proposals address some important issues related to the service model of IP mul-ticast, the scalability problem of IP multicast routing still remains. In this paper, we proposea novel multicast scheme called REUNITE (REcursive UNicast TreE) to address the scalabilityissues. Unlike all existing IP multicast protocols, REUNITE does not use class D IP addresses.Instead, both data forwarding and group identification are based on unicast IP addresses. Mul-ticast data forwarding is implemented with a novel technique called recursive unicast. A groupis identified by a two-tuple< r oot IP addr ess; r oot por t number >where the root node canbe either the sender or a special node. Compared with existing IP multicast solutions, REUNITEhas several important advantages:Enhanced Scalability by Reduction of Forwarding State With REUNITE, only routers thatare acting as multicast tree branching points for a group need to keep multicast forwarding stateof the group. Non-branching-point routers simply forward packets by unicast routing.No Need for Class D IP Address With REUNITE, a multicast group is identified by a two tuple< unicast IP address; por t number >and there is no need for a separate block of class D IPaddresses. In this case, the allocation of unique group identification becomes trivial. In addition,the maximum number of simultaneously active multicast groups increases dramatically.Native Support for Incremental Deployment Since unicast addresses are used as destinationaddresses in the IP header, a