Internet DRAFT - draft-flynn-rtgwg-lcf
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
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]
