Internet DRAFT - draft-flynn-rtgwg-lcf


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  
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 
   The list of Internet-Draft Shadow Directories can be accessed at" 
   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", 
   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. 

   [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. 

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: 
   Room 15E-241                           URI:    
   67 Whippany Road 
   Whippany, NJ   07981 
   Rick Townsend                           Phone:  +1 732 949 8667 
   Lucent Technologies, Bell Labs          Email: 
   Room 4C-605A                            URI:   
   101 Crawfords Corner Road 
   Holmdel, NJ   07733 
   Hans Peter Dommel                       Phone: +1 408 554 4485 
   Computer Engineering Department         Email: 
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 
   Comments are solicited and should be addressed to the working group's 
   mailing list at 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 

Flynn et al          Expires – February 23, 2006            [Page 10]