rfc2201.txt

RFC 的详细文档！

Network Working Group                                       A. Ballardie
Request for Comments: 2201                                    Consultant
Category: Experimental                                    September 1997


         Core Based Trees (CBT) Multicast Routing Architecture

Status of this Memo

   This memo defines an Experimental Protocol for the Internet
   community.  This memo does not specify an Internet standard of any
   kind.  Discussion and suggestions for improvement are requested.
   Distribution of this memo is unlimited.

Abstract

   CBT is a multicast routing architecture that builds a single delivery
   tree per group which is shared by all of the group's senders and
   receivers.  Most multicast algorithms build one multicast tree per
   sender (subnetwork), the tree being rooted at the sender's
   subnetwork.  The primary advantage of the shared tree approach is
   that it typically offers more favourable scaling characteristics than
   all other multicast algorithms.

   The CBT protocol [1] is a network layer multicast routing protocol
   that builds and maintains a shared delivery tree for a multicast
   group.  The sending and receiving of multicast data by hosts on a
   subnetwork conforms to the traditional IP multicast service model
   [2].

   CBT is progressing through the IDMR working group of the IETF.  The
   CBT protocol is described in an accompanying document [1]. For this,
   and all IDMR-related documents, see http://www.cs.ucl.ac.uk/ietf/idmr

TABLE OF CONTENTS

   1. Background...................................................  2
   2. Introduction.................................................  2
   3. Source Based Tree Algorithms.................................  3
      3.1 Distance-Vector Multicast Algorithm......................  4
      3.2 Link State Multicast Algorithm...........................  5
      3.3 The Motivation for Shared Trees..........................  5
   4. CBT - The New Architecture...................................  7
      4.1 Design Requirements......................................  7
      4.2 Components & Functions...................................  8
          4.2.1 CBT Control Message Retransmission Strategy........ 10
          4.2.2 Non-Member Sending................................. 11
   5. Interoperability with Other Multicast Routing Protocols ..... 11



Ballardie                     Experimental                      [Page 1]

RFC 2201           CBT Multicast Routing Architecture     September 1997


   6. Core Router Discovery........................................ 11
      6.1 Bootstrap Mechanism Overview............................. 12
   7. Summary ..................................................... 13
   8. Security Considerations...................................... 13
   Acknowledgements ............................................... 14
   References ..................................................... 14
   Author Information.............................................. 15

1.  Background

   Shared trees were first described by Wall in his investigation into
   low-delay approaches to broadcast and selective broadcast [3]. Wall
   concluded that delay will not be minimal, as with shortest-path
   trees, but the delay can be kept within bounds that may be
   acceptable.  Back then, the benefits and uses of multicast were not
   fully understood, and it wasn't until much later that the IP
   multicast address space was defined (class D space [4]). Deering's
   work [2] in the late 1980's was pioneering in that he defined the IP
   multicast service model, and invented algorithms which allow hosts to
   arbitrarily join and leave a multicast group. All of Deering's
   multicast algorithms build source-rooted delivery trees, with one
   delivery tree per sender subnetwork. These algorithms are documented
   in [2].

   After several years practical experience with multicast, we see a
   diversity of multicast applications and correspondingly, a wide
   variety of multicast application requirements.  For example,
   distributed interactive simulation (DIS) applications have strict
   requirements in terms of join latency, group membership dynamics,
   group sender populations, far exceeding the requirements of many
   other multicast applications.

   The multicast-capable part of the Internet, the MBONE, continues to
   expand rapidly.  The obvious popularity and growth of multicast means
   that the scaling aspects of wide-area multicasting cannot be
   overlooked; some predictions talk of thousands of groups being
   present at any one time in the Internet.

   We evaluate scalability in terms of network state maintenance,
   bandwidth efficiency, and protocol overhead. Other factors that can
   affect these parameters include sender set size, and wide-area
   distribution of group members.

2.  Introduction

   Multicasting on the local subnetwork does not require either the
   presence of a multicast router or the implementation of a multicast
   routing algorithm; on most shared media (e.g. Ethernet), a host,



Ballardie                     Experimental                      [Page 2]

RFC 2201           CBT Multicast Routing Architecture     September 1997


   which need not necessarily be a group member, simply sends a
   multicast data packet, which is received by any member hosts
   connected to the same medium.

   For multicasts to extend beyond the scope of the local subnetwork,
   the subnet must have a multicast-capable router attached, which
   itself is attached (possibly "virtually") to another multicast-
   capable router, and so on. The collection of these (virtually)
   connected multicast routers forms the Internet's MBONE.

   All multicast routing protocols make use of IGMP [5], a protocol that
   operates between hosts and multicast router(s) belonging to the same
   subnetwork. IGMP enables the subnet's multicast router(s) to monitor
   group membership presence on its directly attached links, so that if
   multicast data arrives, it knows over which of its links to send a
   copy of the packet.

   In our description of the MBONE so far, we have assumed that all
   multicast routers on the MBONE are running the same multicast routing
   protocol. In reality, this is not the case; the MBONE is a collection
   of autonomously administered multicast regions, each region defined
   by one or more multicast-capable border routers. Each region
   independently chooses to run whichever multicast routing protocol
   best suits its needs, and the regions interconnect via the "backbone
   region", which currently runs the Distance Vector Multicast Routing
   Protocol (DVMRP) [6]. Therefore, it follows that a region's border
   router(s) must interoperate with DVMRP.

   Different algorithms use different techniques for establishing a
   distribution tree. If we classify these algorithms into source-based
   tree algorithms and shared tree algorithms, we'll see that the
   different classes have considerably different scaling
   characteristics, and the characteristics of the resulting trees
   differ too, for example, average delay. Let's look at source-based
   tree algorithms first.

3.  Source-Based Tree Algorithms

   The strategy we'll use for motivating (CBT) shared tree multicast is
   based, in part, in explaining the characteristics of source-based
   tree multicast, in particular its scalability.

   Most source-based tree multicast algorithms are often referred to as
   "dense-mode" algorithms; they assume that the receiver population
   densely populates the domain of operation, and therefore the
   accompanying overhead (in terms of state, bandwidth usage, and/or
   processing costs) is justified.  Whilst this might be the case in a
   local environment, wide-area group membership tends to be sparsely



Ballardie                     Experimental                      [Page 3]

RFC 2201           CBT Multicast Routing Architecture     September 1997


   distributed throughout the Internet.  There may be "pockets" of
   denseness, but if one views the global picture, wide-area groups tend
   to be sparsely distributed.

   Source-based multicast trees are either built by a distance-vector
   style algorithm, which may be implemented separately from the unicast
   routing algorithm (as is the case with DVMRP), or the multicast tree
   may be built using the information present in the underlying unicast
   routing table (as is the case with PIM-DM [7]). The other algorithm
   used for building source-based trees is the link-state algorithm (a
   protocol instance being M-OSPF [8]).

3.1.  Distance-Vector Multicast Algorithm

   The distance-vector multicast algorithm builds a multicast delivery
   tree using a variant of the Reverse-Path Forwarding technique [9].
   The technique basically is as follows: when a multicast router
   receives a multicast data packet, if the packet arrives on the
   interface used to reach the source of the packet, the packet is
   forwarded over all outgoing interfaces, except leaf subnets with no
   members attached.  A "leaf" subnet is one which no router would use
   to reach the souce of a multicast packet. If the data packet does not
   arrive over the link that would be used to reach the source, the
   packet is discarded.

   This constitutes a "broadcast & prune" approach to multicast tree
   construction; when a data packet reaches a leaf router, if that
   router has no membership registered on any of its directly attached
   subnetworks, the router sends a prune message one hop back towards
   the source. The receiving router then checks its leaf subnets for
   group membership, and checks whether it has received a prune from all
   of its downstream routers (downstream with respect to the source).
   If so, the router itself can send a prune upstream over the interface
   leading to the source.

   The sender and receiver of a prune message must cache the <source,
   group> pair being reported, for a "lifetime" which is at the
   granularity of minutes. Unless a router's prune information is
   refreshed by the receipt of a new prune for <source, group> before
   its "lifetime" expires, that information is removed, allowing data to
   flow over the branch again. State that expires in this way is
   referred to as "soft state".

   Interestingly, routers that do not lead to group members are incurred
   the state overhead incurred by prune messages. For wide-area
   multicasting, which potentially has to support many thousands of
   active groups, each of which may be sparsely distributed, this
   technique clearly does not scale.



Ballardie                     Experimental                      [Page 4]

RFC 2201           CBT Multicast Routing Architecture     September 1997


3.2.  Link-State Multicast Algorithm

   Routers implementing a link state algorithm periodically collect
   reachability information to their directly attached neighbours, then
   flood this throughout the routing domain in so-called link state
   update packets. Deering extended the link state algorithm for
   multicasting by having a router additionally detect group membership
   changes on its incident links before flooding this information in
   link state packets.

   Each router then, has a complete, up-to-date image of a domain's
   topology and group membership. On receiving a multicast data packet,
   each router uses its membership and topology information to calculate
   a shortest-path tree rooted at the sender subnetwork. Provided the
   calculating router falls within the computed tree, it forwards the
   data packet over the interfaces defined by its calculation. Hence,
   multicast data packets only ever traverse routers leading to members,
   either directly attached, or further downstream. That is, the
   delivery tree is a true multicast tree right from the start.

   However, the flooding (reliable broadcasting) of group membership
   information is the predominant factor preventing the link state
   multicast algorithm being applicable over the wide-area.  The other
   limiting factor is the processing cost of the Dijkstra calculation to
   compute the shortest-path tree for each active source.

3.3.  The Motivation for Shared Trees

   The algorithms described in the previous sections clearly motivate
   the need for a multicast algorithm(s) that is more scalable. CBT was
   designed primarily to address the topic of scalability; a shared tree
   architecture offers an improvement in scalability over source tree
   architectures by a factor of the number of active sources (where
   source is usually a subnetwork aggregate).  Source trees scale O(S *
   G), since a distinct delivery tree is built per active source. Shared
   trees eliminate the source (S) scaling factor; all sources use the
   same shared tree, and hence a shared tree scales O(G).  The
   implication of this is that applications with many active senders,
   such as distributed interactive simulation applications, and
   distributed video-gaming (where most receivers are also senders),
   have a significantly lesser impact on underlying multicast routing if
   shared trees are used.









Ballardie                     Experimental                      [Page 5]