Routing Working Group L. Flynn Internet Draft R. Townsend Expires: February 23, 2006 Lucent Technologies/Bell Labs H. Dommel Santa Clara University August 22, 2005 Limited Core Fix (LCF) Multicast draft-flynn-rtgwg-lcf-00.txt Status of This Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. "Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/1id-abstracts.html The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html" Abstract This Internet Draft describes the Limited Core Fix (LCF) multicast t protocol for IP multicast routing. Since the existing multicast protocols rely on RFC 1112 as their foundation, multicast is characterized by a host join attribute not involving knowledge by the source. Evolving uses of multicast may be seen to require joins on a more qualified basis and may require knowledge of such joins by the source. An example, is IP wireless multicast in which the source (i.e., service provider) will want to charge for specific channels (in the TV sense) and limit transmission to those hosts paying for the service. Other qualifications may be needed in providing high quality broadband service. Other examples for which a qualification- based multicast could be developed include bandwidth needs, jitter or Flynn et al Expires – February 23, 2006 [Page 1] Internet Draft Limited Core Fix August 22, 2005 latency requirements, or restrictions on who gets particular transmissions. In order to accommodate these requirements, or a dynamic group membership for collaboration activities. The qualification-based multicast described in LCF uses a depth-first- search technique to find new routes to a multicast source when needed, an attribute that minimizes transmission bandwidth to update the tree and utilizes tables significantly smaller than those of normal multicast. The draft discusses the notion of qualification- based multicast as a generalization of Quality-of-Service (QoS) routing for multicast. LCF can be used to build multicast trees in a sparse-mode fashion and implements receiver-initiated multicast repair for damaged multicast trees. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 2. LCF Description . . . . . . . . . . . . . . . . . . . . . . . 3 3. Handling Link/Node Failures and Disqualification . . . . . . 5 4. Cooperation with Various Tree-build Methods . . . . . . . . . 5 4.1 Core-supervised Tree-build . . . . . . . . . . . . . . . . 5 4.2 LCF Sparse Mode Tree-build . . . . . . . . . . . . . . . . 5 5. Wireless Messaging . . . . . . . . . . . . . . . . . . . . . 5 6. Performance . . . . . . . . . . . . . . . . . . . . . . . . . 6 7. Security Considerations . . . . . . . . . . . . . . . . . . . 6 8. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 7 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 7 10.1 Normative References . . . . . . . . . . . . . . . . . . 7 10.2 Informative References . . . . . . . . . . . . . . . . . 9 Authors’ Addresses . . . . . . . . . . . . . . . . . . . . . . . . 9 Full Copyright Statement . . . . . . . . . . . . . . . . . . . . . 10 Conventions used in this document The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC-2119 [2]. 1. Introduction Multicast deployments in the MBone [15] and more recently in the Internet [10] have lead to more sophisticated one-to-many Flynn et al Expires – February 23, 2006 [Page 2] Internet Draft Limited Core Fix August 22, 2005 communication protocols [20], whose primary strength is the significant reduction in bandwidth waste currently incurred through unicast transmissions. While the generality and complexity of MBone- type multicast has been an obstacle to wider acceptance [17] and the proliferation of group-aware applications, the lower price point of investments in large-scale multicast-capable routing infrastructures makes group communication services economically viable in relation to saved bandwidth from the use of multicast. Multicast has been studied in many variants of link layer, routing, reliable transport, and application-level [15] protocols. The field of QoS-supported multicast is of particular interest to service providers and distributors of multimedia content or secure connectivity, and in particular for ad hoc networks [14]. Effective and flexible multicast is highly desirable for interactive environments, where the number of simultaneous participants and applications fluctuates greatly, requiring loose consistency and weak group membership, absence of central servers, and global scalability through sub-partitioning and on-demand formation of transmission topologies [12]. The idea of qualification-based multicast follows this premise of mapping QoS-routing for multicast into a qualification model where user privileges, security levels or pay-per-view transmissions can be traced through qualifiers to enable transmission for some users and disable it for others. The qualifier is a group membership criterion as defined in the taxonomy on multicast [1]. We define a qualified network as one in which only a subset of routers and links are permitted to handle specific qualified types of packets. Qualification is expressed through the evaluation of qualifiers in routers. The qualifier may be a VPN security level [11] or different attribute which determines if traffic may flow through a particular node. Qualifiers can be based on general metrics, traditional QoS parameters such as sampling resolution, latency [3], jitter, and other transmission characteristics, or they can express billing, security, or other application-relevant criteria. The formation and maintenance of qualified multicast trees represent a particular challenge in terms of routing and repair, since criteria for nodes to be on-tree or off-tree are both a function of group membership and the fulfillment of one or more qualifiers. The Limited Core Fix (LCF) multicast protocol uses a novel depth- first-search technique to find new routes to a multicast source when needed, rather than the expanding ring search of on-demand multicast protocols such as AODV/MAODV [8][12] and QoSMIC [21]. LCF has a receiver-initiated multicast repair method which uses a minimum of bandwidth in order to repair qualified and other multicast trees. The LCF protocol may be used to build multicast trees in a sparse-mode [6] style. Flynn et al Expires – February 23, 2006 [Page 3] Internet Draft Limited Core Fix August 22, 2005 2. LCF Description LCF repairs are requested in a limited sequential search towards the core. Routing loops are prevented by requiring on-tree nodes to maintain a pathlist to the core. Each router in LCF MUST maintain a multicast routing table with the fields [group, qualifier, source timestamp, parent, children, predecessor list] for each multicast group. A search table also MUST be maintained with the fields [group, qualifier, neighbors queried, requester timestamp, neighbor replies, request originator id, neighbor to reply to] Additionally, the router MUST maintain a neighbor qualifier table in order to identify which qualifiers neighboring routers possess. Periodically exchanged qualification information between neighboring routers MUST be used to update the neighbor qualifier table. That period is th egroup leave delay overhead in the terminology of RFC 2432 [5]. When a neighbor is found to be unqualified the multicast routing table MUST be changed so that neighbor is no longer a multicast parent or child. On-tree nodes MUST have a list of all nodes on their reverse on-tree path to the core. Off-tree nodes MUST have a standard unicast table irrespective of qualification status. Off-tree nodes MUST also have a neighbor qualification table with information about qualification status of direct neighbors. A node attempting to join the tree MUST send a path-request (PATH) to the qualified neighbor with the shortest standard unicast path to the core. Intermediate nodes MUST follow the same search methodology, and add their own id (IP address) to the request pathlist when they forward the request. All nodes performing the search MUST make an entry in their search table. If the request packet reaches a node with no other qualified neighbors, a negative acknowledgement (NACK) MUST be returned to the requestor. If a node receives a NACK then it MUST send a path request to the qualified neighbor which has not yet been queried and has the shortest standard unicast path. If no unqueried qualified neighbor remains, this node MUST send a NACK to the neighbor which sent the original request. The request to join the tree only fails if the original node receives a NACK from each of its qualified neighbors. The join request Flynn et al Expires – February 23, 2006 [Page 4] Internet Draft Limited Core Fix August 22, 2005 succeeds if it reaches an on-tree node (including the core). The on- tree node MUST append its own stored path to the core to the path listed in the request packet, and MUST return a path-found (F-PATH) packet to its neighbor. The F-PATH packet MUST be forwarded along the new tree path as listed in the packet itself, and as it is forwarded the nodes MUST make entries in their multicast routing table. At the time the original joining node receives the F-PATH, the on-tree path to the joining node has been constructed. LCF control packets (PATH, F-PATH, and NACK) MUST be sent in a reliable manner over each link. (The control packets MUST be acknowledged by receiving routers. If the packet is not acknowledged within a timeout then the packet MUST be resent. If the original path-requester does not receive a reply (F-PATH or NACK) within a timeout period then it MUST resend the path-request to that neighbor. 3. Handling Link/Node Failures and Disqualification Each node directly descendant to a link no longer qualified or working MUST notify the subtree below itself using a reliable subcast. Orphaned nodes send a path-request to their qualified neighbor with the shortest standard unicast path to the core. Repair follows as described above in the LCF protocol overview. 4. Cooperation with various tree-build methods The Limited Core Fix method is able to work on trees built using the Core Supervised protocol or LCF joins alone as long as the build created a pathlist within each router. LCF and core-supervised tree build protocols create a pathlist within on-tree nodes. 4.1 Core-supervised tree build A core-supervised tree build can be done if the following is true: - The multicast core knows all joining nodes. - The multicast core can make nodes qualified OR the multicast core has a qualification-based topology map. - The multicast core has a unicast routing table. The multicast core MUST send CAN-JOIN packets along a known path to each of the joining nodes. The CAN-JOIN packet MUST cause nodes along the path to become part of the multicast forwarding tree and also to store the multicast entry including reverse path to the core. Core supervised session control for initiation is directive as defined in RFC 2729 [1]. Flynn et al Expires – February 23, 2006 [Page 5] Internet Draft Limited Core Fix August 22, 2005 4.2 LCF sparse mode tree build A complete multicast tree can be built in a sparse-mode build style [7] using LCF joins. Sparse-mode multicast receivers initiate joins along a reverse path to the multicast core. An LCF-only sparse mode tree build would leave exactly the information necessary at each node for performing an LCF tree repair. 5. Wireless Messaging The modification of this protocol for wireless messaging [14] requires that LCF control packets have a field indicating which neighbor which the packet is sent to. This modification is required to retain the depth-first-search of LCF instead of a radial search as in the MAODV [12] and QoSMIC [14] protocols. 6. Performance Expected time to join the tree (group join delay overhead, as defined in [5]) is on the order of 2K*1/P, where P is the proportion of qualified nodes joined to the multicast and K is the average link latency plus queued latency time. Wired expected bandwidth use is B*2/P, where B is the LCF control packet size. Wireless expected bandwidth use is N*B*2/P, where N is the average number of neighbors. LCF wired performance join latency and bandwidth use is the same as for the PIM-SM protocol [6] for unqualified multicasts. PIM SM does not route for qualified multicast. Wireless and wired performance of LCF compared to the radial search techniques used by MAODV and QoSMIC generally show superior bandwidth savings by LCF and shorter time to join than radial search techniques. 7. Security Considerations LCF per se does not prescribe specific security measures in the routing process. However, it provides the framework to create more secure forwarding mechanisms among routers. Packets in LCF are only routed in a multicast distribution infrastructure if they fulfill qualification constraints. Such constraints can contain traffic security criteria. In addition, the correctness of qualification-based routing requires cooperative and equal validation of qualifiers in packets across all routers along a delivery path. Incorrectly routed LCF control packets must be dropped by routers on the path or by the recipient if forwarded by an unqualified node. Flynn et al Expires – February 23, 2006 [Page 6] Internet Draft Limited Core Fix August 22, 2005 8. Summary LCF is based on a qualification model of on-demand routing, so it can leverage the service provider’s ability to provide qualifications such as QoS. Considering these qualifications during routing will enable new models of pricing and billing, establishment of secure communication channels or more effective content distribution for interactive systems. LCF is a protocol to rapidly build and repair multicast trees. It operates on the notion of qualifier-driven routing, where software constraints are used to evaluate fulfillment of forwarding criteria in packet flows. In contrast to QoS routing, qualifiers may not only reflect service conditions, but address other application-level conditions, such as payment receipts or security levels. The choice of qualifiers may be made by providers, users or by software agents in applications. LCF maintains multicast trees for dynamic network topologies [1] and qualified receiver groups. LCF implements tree repair using very low bandwidth, independent of a particular tree topology. LCF performance compares favorably to on-demand protocols and LCF always displays superior performance relative to use of distance-vector or topology-map unicast routing tables. 9. Acknowledgments This protocol was initially developed as part of a body of doctoral research work by Lori Flynn under advisor Prof. J.J. Garcia Luna Aceves at the University of California at Santa Cruz. Hans Peter Dommel has further collaborated with Lori Flynn on the protocol details and documentation. 10. References 10.1 Normative References [1] Bagnall, P., Briscoe, R., and Poppitt, A., “Taxonomy of Communication Requirements for Large-scale Multicast Applications”, RFC 2729, December 1999. [2] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [3] Bradner, S., “Benchmarking terminology for network interconnection devices”, RFC 1242, July 1991. Flynn et al Expires – February 23, 2006 [Page 7] Internet Draft Limited Core Fix August 22, 2005 [4] Deering, S., "Host Extensions for IP Multicasting," RFC 1112, August 1989. [5] Dubray, K., “Terminology for IP Multicast Benchmarking”, RFC 2432, October 1998. [6] Estrin, D., Farinacci, D., and et. Al., “Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification, RFC 2362, June 1998. [7] B. Fenner, M. Handley, H. Holbrook, and I. Kouvelas. "Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification (Revised)," draft-ietf-pim-sm-v2-new-10.txt (Work in Progress), July 2004. [8] Perkins, C., Belding-Royer, E., Das, S., “Ad hoc On-Demand Distance Vector (AODV) Routing”, RFC 3561July 2003. [9] Postel, J., ed., "Internet Protocol, Darpa Internet Program Protocol Specification," September 1981. 10.2 Informative References [10] K. Almeroth. The Evolution of Multicast: From the MBone to Interdomain Multicast to Internet2 Deployment. IEEE Network, Jan./Feb. 2000. [11] W. Arbaugh, J. R. Davin, D. J. Farber, J. M. Smith. Security for Virtual Private Intranets. IEEE Computer, V.31, N.9, 48–54, Sept. 1998. [12] E. M. Belding-Royer and C. Perkins. Multicast Operation of the Ad-Hoc On-Demand Distance Vector Routing Protocol. In Proc. MOBICOM, 207–218, 1999. [13] S. Chakrabarti and A. Mishra. QoS Issues in Ad Hoc Networks. IEEE Communications Magazine, 142–148, Feb. 2001. [14] X. Chen and J. Wu. Multicasting Techniques in mobile Ad hoc Networks. In The Handbook of Ad hoc Wireless Networks, CRC Press, 25–40, 2003. [15] Y. Chu, S. G. Rao, S. Seshan, and H. Zhang, Enabling Conferencing Applications on the Internet using an Overlay Multicast Architecture. In Proc. ACM SIGCOMM, San Diego, CA, Aug. 2001. Flynn et al Expires – February 23, 2006 [Page 8] Internet Draft Limited Core Fix August 22, 2005 [16] Stephen Deering, Deborah L. Estrin, Dino Farinacci, Van Jacobson, Ching-Gung Liu, and Liming Wei. The PIM architecture for wide-area multicast routing, IEEE/ACM Trans. Netw., V.4, N.2, 1063-6692, 1996. [17] C. Diot, B.N. Levine, B. Lyles, H. Kassem, and D. Balensiefen. Deployment Issues for the IP Multicast Service and Architecture. IEEE Network, V.14, N.1, 88–98, Jan. 2000. [18] A. S. Thyagarajan and S. E. Deering. Hierarchical distance vector multicast routing for the MBone. In Proc. ACM SIGCOMM ’95, Cambridge, MA, 60–66, 1995. [19] A. Tsirigos and Z.J. Haas. Multipath Routing in the Presence of Frequent Topological Changes. IEEE Communications Magazine, 132- 138, Nov. 2001. [20] L. K. Wright and S. McCanne and J. Lepreau. A Reliable Multicast Webcast Protocol for Multimedia Collaboration and Caching. In Proc. ACM Multimedia, Marina del Rey, 21–30, 2000. [21] S. Yan, M. Faloutsos and A. Banerjea. QoS-Aware Multicast Routing for the Internet: The Design and Evaluation of QoSMIC. IEEE/ACM Transactions on Networking, V.10, N.1, 54–66, Feb. 2002. Author's Addresses Lori Arline Flynn Phone: +1 973 566 2096 Lucent Technologies, Bell Labs Email: laflynn@lucent.com Room 15E-241 URI: 67 Whippany Road Whippany, NJ 07981 USA Rick Townsend Phone: +1 732 949 8667 Lucent Technologies, Bell Labs Email: rltownsend@lucent.com Room 4C-605A URI: 101 Crawfords Corner Road Holmdel, NJ 07733 USA Hans Peter Dommel Phone: +1 408 554 4485 Computer Engineering Department Email: hpdommel@scu.edu Flynn et al Expires – February 23, 2006 [Page 9] Internet Draft Limited Core Fix August 22, 2005 Santa Clara University URI: 500 El Camino Real Santa Clara, CA 95053 USA Comments are solicited and should be addressed to the working group's mailing list at rtgwg@ietf.org and/or to the authors. Full Copyright Statement “Copyright (C) The Internet Society (2005). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights." "This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE." Flynn et al Expires – February 23, 2006 [Page 10]