[Docs] [txt|pdf] [Tracker] [WG] [Email] [Diff1] [Diff2] [Nits]

Versions: 02 RFC 1584

Network Working Group                                             J. Moy
Internet Draft                                             Proteon, Inc.
Expiration date: February 1993                            September 1992


                      Multicast Extensions to OSPF



Status of this Memo

    This document is an Internet  Draft.  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. Internet Drafts may  be
    updated,  replaced,  or obsoleted by other documents at any time. It
    is not appropriate to use Internet Drafts as reference  material  or
    to  cite  them  other  than as a ``working draft'' or ``work in pro-
    gress.'' Please check the 1id-abstracts.txt listing contained in the
    internet-drafts  Shadow  Directories  on  nic.ddn.mil, nnsc.nsf.net,
    nic.nordu.net,  ftp.nisc.sri.com,  or  munnari.oz.au  to  learn  the
    current status of any Internet Draft.

Abstract

    This memo documents enhancements to the OSPF protocol  enabling  the
    routing of IP multicast datagrams. In this proposal, an IP multicast
    packet is routed based both on the packet's source and its multicast
    destination (commonly referred to as source/destination routing). As
    it is routed, the multicast packet follows a shortest path  to  each
    multicast  destination. During packet forwarding, any commonality of
    paths is exploited; when multiple hosts belong to a single multicast
    group,  a multicast packet will be replicated only when the paths to
    the separate hosts diverge.

    OSPF, a link-state  based  routing  protocol,  provides  a  database
    describing  the  Autonomous System's topology. A new OSPF link state
    advertisement is added describing the location of multicast destina-
    tions.  A  multicast  packet's path is then calculated by building a
    pruned shortest-path tree rooted at the packet's  IP  source.  These
    trees  are  built  on demand, and the results of the calculation are
    cached for use by subsequent packets.

    The multicast extensions are built on top of  OSPF  version  2.  The
    extensions  have  been implemented so that a multicast routing capa-
    bility can be introduced piecemeal into an OSPF  version  2  routing
    domain.  Some  of  the  OSPF version 2 routers may run the multicast



[Moy]                                                           [Page 1]

Internet Draft        Multicast Extensions to OSPF        September 1992


    extensions, while others may continue to be restricted to  the  for-
    warding of regular IP traffic (unicasts).

    Please send comments to mospf@gated.cornell.edu.















































[Moy]                                                           [Page 2]

Internet Draft        Multicast Extensions to OSPF        September 1992


Table of Contents

    1       Introduction ........................................... 5
    1.1     Terminology ............................................ 6
    1.2     Acknowledgments ........................................ 7
    2       Multicast routing in MOSPF ............................. 7
    2.1     Routing characteristics ................................ 7
    2.2     Sample path of a multicast datagram .................... 9
    2.3     MOSPF forwarding mechanism ............................ 11
    2.3.1   IGMP interface: the local group database .............. 11
    2.3.2   A datagram's shortest-path tree ....................... 14
    2.3.3   Support for Non-broadcast networks .................... 16
    2.3.4   Details concerning forwarding cache entries ........... 17
    3       Inter-area multicasting ............................... 19
    3.1      Extent of group-membership-LSAs ...................... 20
    3.2      Building inter-area datagram shortest-path trees ..... 23
    4       Inter-AS multicasting ................................. 28
    4.1     Building inter-AS datagram shortest-path trees ........ 29
    4.2     Stub area behavior .................................... 30
    5       Modelling internal group membership ................... 31
    6       Additional capabilities ............................... 34
    6.1     Mixing with non-multicast routers ..................... 34
    6.2     TOS-based multicast ................................... 35
    6.3     Assigning multiple IP networks to a physical network .. 36
    6.4     Networks on Autonomous System boundaries .............. 37
    6.5     Recommended system configuration ...................... 39
    7       Basic implementation requirements ..................... 40
    8       Protocol data structures .............................. 40
    8.1     Additions to the OSPF area structure .................. 41
    8.2     Additions to the OSPF interface structure ............. 42
    8.3     Additions to the OSPF neighbor structure .............. 43
    8.4     The local group database .............................. 43
    8.5     The forwarding cache .................................. 44
    9       Interaction with the IGMP protocol .................... 45
    9.1     Sending IGMP Host Membership Queries .................. 45
    9.2     Receiving IGMP Host Membership Reports ................ 46
    9.3     Aging local group database entries .................... 47
    9.4     Receiving IGMP Host Membership Queries ................ 47
    10      Group-membership-LSAs ................................. 48
    10.1    Constructing group-membership-LSAs .................... 49
    10.2    Flooding group-membership-LSAs ........................ 51
    11      Detailed description of multicast datagram forwarding . 52
    11.1    Associating a MOSPF interface with a received datagram  54
    11.2    Locating the source network ........................... 55
    11.3    Forwarding locally originated multicasts .............. 56
    12      Construction of forwarding cache entries .............. 57
    12.1    The Vertex data structure ............................. 58
    12.2    The SPF calculation ................................... 59



[Moy]                                                           [Page 3]

Internet Draft        Multicast Extensions to OSPF        September 1992


    12.2.1  Candidate list Initialization: Case SourceIntraArea ... 64
    12.2.2  Candidate list Initialization: Case SourceInterArea1 .. 65
    12.2.3  Candidate list Initialization: Case SourceInterArea2 .. 65
    12.2.4  Candidate list Initialization: Case SourceExternal .... 66
    12.2.5  Candidate list Initialization: Case SourceStubExternal  69
    12.2.6  Processing labelled vertices .......................... 70
    12.2.7  Merging datagram shortest-path trees .................. 70
    12.2.8  TOS considerations .................................... 72
    12.2.9  Comparison to the unicast SPF calculation ............. 73
    12.3    Adding local database entries to the forwarding cache   74
    13      Maintaining the forwarding cache ...................... 75
    14      Other additions to the OSPF specification ............. 76
    14.1    The Designated Router ................................. 76
    14.2    Sending Hello packets ................................. 77
    14.3    The Neighbor state machine ............................ 77
    14.4    Receiving Database Description packets ................ 77
    14.5    Sending Database Description packets .................. 78
    14.6    Originating Router-LSAs ............................... 78
    14.7    Originating Network-LSAs .............................. 78
    14.8    Originating Summary-LSAs .............................. 79
    14.9    Originating AS external-LSAs .......................... 79
    14.10   Next step in the flooding procedure ................... 80
    14.11   Virtual links ......................................... 80
    15      References ............................................ 81
    A       Data Formats .......................................... 86
    A.1     The options field ..................................... 87
    A.2     Router-LSA ............................................ 89
    A.3     Group-membership-LSA .................................. 91
    B       Configurable Constants ................................ 93
    B.1     Global parameters ..................................... 93
    B.2     Router interface parameters ........................... 93
    C       Sample datagram shortest-path trees ................... 95
    C.1     An intra-area tree .................................... 96
    C.2     The effect of areas ................................... 98
    C.3     The effect of virtual links ........................... 99
















[Moy]                                                           [Page 4]

Internet Draft        Multicast Extensions to OSPF        September 1992


1.  Introduction

    This memo documents enhancements to OSPF version  2  to  support  IP
    multicast  routing.  The enhancements have been added in a backward-
    compatible fashion; routers running  the  multicast  additions  will
    interoperate with non-multicast OSPF routers when forwarding regular
    (unicast) IP data traffic. The protocol resulting from the  addition
    of  the  multicast enhancements to OSPF is herein referred to as the
    MOSPF protocol.

    IP multicasting is an extension of  LAN  multicasting  to  a  TCP/IP
    internet.  Multicasting  support for TCP/IP hosts has been specified
    in [RFC 1112]. In that document, multicast groups are represented by
    IP  class D addresses. Individual TCP/IP hosts join (and leave) mul-
    ticast groups through the Internet Group Management Protocol  (IGMP,
    also specified in [RFC 1112]). A host need not be a member of a mul-
    ticast group in order to send  datagrams  to  the  group.  Multicast
    datagrams  are to be delivered to each member of the multicast group
    with the same "best-effort" delivery accorded regular  (unicast)  IP
    data traffic.

    MOSPF provides the ability to forward multicast datagrams  from  one
    IP  network  to another (i.e., through internet routers). MOSPF for-
    wards a multicast datagram on  the  basis  of  both  the  datagram's
    source  and destination (this is sometimes called source/destination
    routing). The OSPF link state database provides a complete  descrip-
    tion  of  the  Autonomous System's topology. By adding a new type of
    link state advertisement, the group-membership-LSA, the location  of
    all  multicast group members is pinpointed in the database. The path
    of a multicast  datagram  can  then  be  calculated  by  building  a
    shortest-path tree rooted at the datagram's source. All branches not
    containing multicast members are pruned from the tree. These  pruned
    shortest-path  trees  are initially built when the first datagram is
    received (i.e., on demand).  The results of the shortest path calcu-
    lation  are  then  cached for use by subsequent datagrams having the
    same source and destination.

    OSPF allows an Autonomous System to be split  into  areas.  However,
    when  this  is  done  complete  knowledge of the Autonomous System's
    topology is lost. When forwarding  multicasts  between  areas,  only
    incomplete  shortest-path  trees can be built. This may lead to some
    inefficiency in routing. An  analogous  situation  exists  when  the
    source  of the multicast datagram lies in another Autonomous System.
    In both cases (i.e., the source of the datagram belongs  to  a  dif-
    ferent OSPF area, or to a different Autonomous system) the neighbor-
    hood immediately surrounding the source is unknown. In  these  cases
    the  source's  neighborhood  is  approximated  by  OSPF summary link
    advertisements  or  by  OSPF   AS   external   link   advertisements



[Moy]                                                           [Page 5]

Internet Draft        Multicast Extensions to OSPF        September 1992


    respectively.

    Routers running MOSPF can  be  intermixed  with  non-multicast  OSPF
    routers. Both types of routers can interoperate when forwarding reg-
    ular (unicast) IP data traffic. Obviously, the range  of  IP  multi-
    casts is limited by the number of MOSPF routers present in the Auto-
    nomous System (and their interconnection, if  any).  An  ability  to
    "tunnel"  multicast  datagrams  through non-multicast routers is not
    provided. In MOSPF, just as in the  base  OSPF  protocol,  datagrams
    (multicast  or  unicast)  are routed "as is" -- they are not further
    encapsulated or decapsulated as they transit the Autonomous System.

    1.1.  Terminology

        This memo uses the terminology listed in section 1.2 of  [OSPF].
        For  this  reason,  terms such as "Network", "Autonomous System"
        and "link state advertisement" are assumed to be understood.  In
        addition,  the  abbreviation  LSA is used for "link state adver-
        tisement". For example, router links advertisements are referred
        to  as router-LSAs and the new link state advertisement describ-
        ing the location of members of a multicast group is referred  to
        as a group-membership-LSA.

        [RFC 1112] discusses the data-link encapsulation of IP multicast
        datagrams.  In  contrast  to the normal forwarding of IP unicast
        datagrams, on a broadcast network the mapping of an IP multicast
        destination  to a data-link destination address is not done with
        the ARP protocol. Instead, static  mappings  have  been  defined
        from  IP  multicast  destinations  to data-link addresses. These
        mappings are dependent on network type;  for  some  networks  IP
        multicasts  are  algorithmically  mapped  to data-link multicast
        addresses, for other networks all IP multicast destinations  are
        mapped  onto  the  data-link  broadcast  address.  This document
        loosely describes both of these possible mappings  as  data-link
        multicast.

        The following terms are also used throughout this document:

        o   Non-multicast router. A router running OSPF version  2,  but
            not  the  multicast extensions. These routers do not forward
            multicast datagrams, but can interoperate with MOSPF routers
            in  the  forwarding  of unicast packets. Routers running the
            MOSPF protocol are referred to herein as  either  multicast-
            capable routers or MOSPF routers.

        o   Non-broadcast networks. A network supporting the  attachment
            of  more  than two stations, but not supporting the delivery
            of a  single  physical  datagram  to  multiple  destinations



[Moy]                                                           [Page 6]

Internet Draft        Multicast Extensions to OSPF        September 1992


            (i.e., not supporting data-link multicast). [OSPF] describes
            these networks as non-broadcast, multi-access  networks.  An
            example of a non-broadcast network is an X.25 PDN.

        o   Transit network. A network having two or more  OSPF  routers
            attached.   These  networks can forward data traffic that is
            neither locally-originated nor  locally-destined.  In  OSPF,
            with  the  exception  of point-to-point networks and virtual
            links, the neighborhood of each transit network is described
            by a network links advertisement (network-LSA).

        o   Stub network. A network having only  a  single  OSPF  router
            attached.  A network belonging to an OSPF system is either a
            transit or a stub network, but never both.

    1.2.  Acknowledgments

        The multicast extensions to OSPF are based on Link-State  Multi-
        cast  Routing algorithm presented in [Deering]. In addition, the
        [Deering] paper contains a  section  on  Hierarchical  Multicast
        Routing (providing the ideas for MOSPF's inter-area multicasting
        scheme) and several Distance Vector (also  called  Bellman-Ford)
        multicast  algorithms.  One  of  these Distance Vector multicast
        algorithms, Truncated Reverse Path Broadcasting, has been imple-
        mented in the Internet (see [RFC 1075]).

        The MOSPF protocol has been developed by the MOSPF Working Group
        of  the  Internet  Engineering Task Force. Portions of this work
        have been supported by DARPA under NASA contract NAG 2-650.

2.  Multicast routing in MOSPF

    This section describes MOSPF's basic  multicast  routing  algorithm.
    The  basic algorithm, run inside a single OSPF area, covers the case
    where the source of  the  multicast  datagram  is  inside  the  area
    itself.  Within  the  area,  the  path  of the datagram forms a tree
    rooted at the datagram source.

    2.1.  Routing characteristics

        As a multicast datagram is  forwarded  along  its  shortest-path
        tree,  the  datagram is delivered to each member of the destina-
        tion multicast group. In MOSPF, the forwarding of the  multicast
        datagram has the following properties:

        o   The path taken by a multicast datagram depends both  on  the
            datagram's  source  and  its  multicast  destination. Called
            source/destination routing, this  is  in  contrast  to  most



[Moy]                                                           [Page 7]

Internet Draft        Multicast Extensions to OSPF        September 1992


            unicast  datagram  forwarding  algorithms  (like  OSPF) that
            route based only on destination.

        o   The path taken between the datagram's source and any partic-
            ular  destination group member is the least cost path avail-
            able. Cost is expressed in  terms  of  the  OSPF  link-state
            metric.  For example, if the OSPF metric represents delay, a
            minimum delay path is chosen. OSPF metrics are configurable.
            A  metric  is  assigned  to  each outbound router interface,
            representing the cost of sending a packet on that interface.
            The  cost of a path is the sum of its constituent (outbound)
            router interfaces[1].

        o   MOSPF takes advantage of any commonality of least cost paths
            to  destination  group members. However, when members of the
            multicast group are spread out over multiple  networks,  the
            multicast  datagram must at times be replicated. This repli-
            cation is performed as few times as possible  (at  the  tree
            branches), taking maximum advantage of common path segments.

        o   For a given multicast datagram,  all  routers  calculate  an
            identical shortest-path tree. There is a single path between
            the datagram's source and any particular  destination  group
            member.  This means that, unlike OSPF's treatment of regular
            (unicast) IP data traffic, there is no provision for  equal-
            cost multipath.

        o   On each packet hop, MOSPF  normally  forwards  IP  multicast
            datagrams as data-link multicasts. There are two exceptions.
            First, on non-broadcast networks, since there are  no  data-
            link  multicast/broadcast services the datagram must be for-
            warded to specific  MOSPF  neighbors  (see  Section  2.3.3).
            Second,  a MOSPF router can be configured to forward IP mul-
            ticasts on specific networks as data-link unicasts, in order
            to  avoid  datagram  replication in certain anomalous situa-
            tions (see Section 6.4).

        While MOSPF optimizes the path to any  given  group  member,  it
        does  not  necessarily optimize the use of the internetwork as a
        whole. To do so, instead of calculating  source-based  shortest-
        path  trees,  something similar to a minimal spanning tree (con-
        taining only the group members) would  need  to  be  calculated.
        This  type  of minimal spanning tree is called a Steiner tree in
        the literature. For a comparison of shortest-path  tree  routing
        to  routing  using  Steiner  trees, see [Deering2] and [Bharath-
        Kumar].





[Moy]                                                           [Page 8]

Internet Draft        Multicast Extensions to OSPF        September 1992


    2.2.  Sample path of a multicast datagram

        As an example of multicast datagram routing in  MOSPF,  consider
        the  sample  Autonomous System pictured in Figure 1. This figure
        has been taken from the OSPF  specification  (see  [OSPF]).  The
        larger  rectangles  represent  routers,  the  smaller rectangles
        hosts. Oblongs and circles represent  multi-access  networks[2].
        Lines  joining  routers are point-to-point serial connections. A
        cost has been assigned to each outbound router interface.

        All routers in Figure 1 are  assumed  to  be  running  MOSPF.  A
        number  of  hosts  have  been  added  to  the  figure. The hosts
        labelled Ma have joined a particular multicast  group  (call  it
        group A) via the IGMP protocol.  These hosts are located on net-
        works N2, N6 and N11. Similarly, using IGMP the  hosts  labelled
        Mb  have  joined  a  separate multicast group B; these hosts are
        located on networks N1, N2 and N3. Note that hosts can join mul-
        tiple  multicast  groups; it is only for clarity of presentation
        that each host has joined at most one multicast  group  in  this
        example.   Also, hosts H2 through H5 have been added to the fig-
        ure to serve as sources  for  multicast  datagrams.  Again,  the
        datagrams'  sources  have  been  made  separate  from  the group
        members only for clarity of presentation.

        To illustrate the forwarding of a  multicast  datagram,  suppose
        that host H2 (attached to network N4) sends a multicast datagram
        to multicast group B. This datagram originates  as  a  data-link
        layer  multicast  on  network  N4. Router RT3, being a multicast
        router,  has  "opened  up"  its  interface  data-link  multicast
        filters.  It  therefore  receives  the  multicast  datagram, and
        attempts to forward it to  the  members  of  multicast  group  B
        (located  on  networks  N1,  N2 and N3). This is accomplished by
        sending a single copy of the datagram onto network N3, again  as
        a data-link multicast[3].  Upon receiving the multicast datagram
        from RT3, routers RT1 and RT2 will then multicast  the  datagram
        on their connected stub networks (N1 and N2 respectively).  Note
        that, since the datagram is sent onto network N3 as a  data-link
        multicast, router RT4 will also receive a copy. However, it will
        not forward the datagram, since it does not lie  on  a  shortest
        path  between  the source (host H2) and any members of multicast
        group B.

        Note that the path of the  multicast  datagram  depends  on  the
        datagram's  source  network. If the above multicast datagram was
        instead originated by host H3, the path taken would  be  identi-
        cal,  since  hosts  H2  and H3 lie on the same network (net N4).
        However, if the datagram was originated by  host  H4,  its  path
        would  be  different. In this case, when router RT3 receives the



[Moy]                                                           [Page 9]

Internet Draft        Multicast Extensions to OSPF        September 1992



                 +
                 | 3+---+    +--+  +--+       N12      N14
               N1|--|RT1|\1  |Mb|  |H4|         \ N13 /
                _|  +---+ \  +--+ /+--+         8\ |8/8
               | +         \ _|__/                \|/
             +--+   +--+    /    \   1+---+8    8+---+6
             |Mb|   |Mb|   *  N3  *---|RT4|------|RT5|--------+
             +--+  /+--+    \____/    +---+      +---+        |
                  +         /   |                  |7         |
                  | 3+---+ /    |                  |          |
                N2|--|RT2|/1    |1                 |6         |
                __|  +---+    +---+8            6+---+        |
               |  +           |RT3|--------------|RT6|        |
             +--+    +--+     +---+     +--+     +---+        |
             |Ma|    |H3|_      |2     _|H2|     Ia|7         |
             +--+    +--+ \     |     / +--+       |          |
                           +---------+             |          |
                               N4                  |          |
                                                   |          |
                                                   |          |
                       N11                         |          |
                   +---------+                     |          |
                        |     \                    |          |    N12
                        |3     +--+                |          |6 2/
                      +---+    |Ma|                |        +---+/
                      |RT9|    +--+                |        |RT7|---N15
                      +---+                        |        +---+ 9
                        |1                   +     |          |1
                       _|__                  |   Ib|5       __|_   +--+
                      /    \      1+----+2   |  3+----+1   /    \--|Ma|
                     *  N9  *------|RT11|----|---|RT10|---*  N6  * +--+
                      \____/       +----+    |   +----+    \____/
                        |                    |                |
                        |1                   +                |1
             +--+   10+----+                N8              +---+
             |H1|-----|RT12|                                |RT8|
             +--+SLIP +----+                                +---+  +--+
                        |2                                    |4  _|H5|
                        |                                     |  / +--+
                   +---------+                            +--------+
                       N10                                    N7

                    Figure 1: A sample MOSPF configuration

        datagram, RT3 will drop the datagram instead  of  forwarding  it
        (since  RT3  is  no longer on the shortest path to any member of
        group B).



[Moy]                                                          [Page 10]

Internet Draft        Multicast Extensions to OSPF        September 1992


        Note that the path of the multicast datagram also depends on the
        destination  multicast  group.  If  host H2 sends a multicast to
        group A, the path taken is as follows. The datagram again starts
        as  a  multicast  on  network  N4.  Router  RT3 receives it, and
        creates two copies. One is sent onto net N3 which is  then  for-
        warded  onto network N2 by RT2. The other copy is sent to router
        RT10 (via RT6), where the datagram is again split, eventually to
        be  delivered onto networks N6 and N11. Note that, although mul-
        tiple copies of the datagram are produced, the  datagram  itself
        is  not  modified  as  it  is forwarded. No encapsulation of the
        datagram is performed; the destination of the datagram is always
        listed as the multicast group A.

    2.3.  MOSPF forwarding mechanism

        Each MOSPF router in the path of a multicast datagram bases  its
        forwarding  decision on the contents of a data cache. This cache
        is called the forwarding cache. There is a  separate  forwarding
        cache  entry  for  each source/destination combination[4].  Each
        cache entry indicates, for multicast datagrams  having  matching
        source  and destination, which neighboring node (i.e., router or
        network) the datagram must be received from (called the upstream
        node) and which interfaces the datagram should then be forwarded
        out of (called the downstream interfaces).

        A forwarding cache entry is actually built  from  two  component
        pieces.  The first of these components is called the local group
        database. This database, built by the IGMP  protocol,  indicates
        the group membership of the router's directly attached networks.
        The local group database enables the local delivery of multicast
        datagrams.  The second component is the datagram's shortest path
        tree. This tree, built on  demand,  is  rooted  at  a  multicast
        datagram's source. The datagram's shortest path tree enables the
        delivery of multicast datagrams to distant (i.e.,  not  directly
        attached) group members.

        2.3.1.  IGMP interface: the local group database

            The local group database keeps track of the group membership
            of  the  router's  directly attached networks. Each entry in
            the local group database  is  a  [group,  attached  network]
            pair,  which  indicates that the attached network has one or
            more IP hosts belonging  to  the  IP  multicast  destination
            group.  This  information  is  then  used by the router when
            deciding which  directly  attached  networks  to  forward  a
            received  IP  multicast  datagram onto, in order to complete
            delivery of the datagram to (local) group members.




[Moy]                                                          [Page 11]

Internet Draft        Multicast Extensions to OSPF        September 1992


            The local group database is built through the  operation  of
            the  Internet  Group  Membership  Protocol  (IGMP;  see [RFC
            1112]). When an MOSPF router becomes Designated Router on an
            attached  network  (call  the network N1), it starts sending
            periodic IGMP Host Membership Queries on the network.  Hosts
            then respond with IGMP Host Membership Reports, one for each
            multicast group to which they belong. Upon receiving a  Host
            Membership  Report  for  a  multicast  group  A,  the router
            updates its local group database  by  adding/refreshing  the
            entry  [Group A, N1]. If at a later time Reports for group A
            cease to be heard on the network, the entry is then  deleted
            from the local group database.

            It is important to note that on any particular network,  the
            sending of IGMP Host Membership queries and the listening to
            IGMP Host Membership Reports  is  performed  solely  by  the
            Designated  Router.  A  MOSPF router ignores Host Membership
            Reports received on those networks where the router has  not
            been  elected Designated Router[5].  This means that at most
            one router performs these IGMP functions on  any  particular
            network,  and  ensures that the network appears in the local
            group database of at most one router. This  prevents  multi-
            cast  datagrams  from being replicated as they are delivered
            to local group members. As a  result,  each  router  in  the
            Autonomous System has a different local group database. This
            is in contrast to the MOSPF link  state  database,  and  the
            datagram  shortest-path  trees  (see  Section 2.3.2), all of
            which are identical in each router belonging  to  the  Auto-
            nomous System.

            The existence of local group members must be communicated to
            the  rest  of  the  routers  in  the Autonomous System. This
            ensures that a remotely-originated multicast  datagram  will
            be  forwarded  to  the  router for distribution to its local
            group members. This communication  is  accomplished  through
            the  creation  of  a  group-membership-LSA.  Like other link
            state advertisements, the  group-membership-LSA  is  flooded
            throughout  the  Autonomous  System. The router originates a
            separate group-membership-LSA for each multicast group  hav-
            ing  one  or  more  entries in the local group database. The
            router's group-membership-LSA (say for group A) lists  those
            local  transit  vertices (i.e., the router itself and/or any
            directly connected transit  networks)  that  should  not  be
            pruned  from  group  A's  datagram  shortest-path trees. The
            router lists itself in the group-membership-LSA for group  A
            if  either 1) one or more of the router's attached stub net-
            works contain group A members or 2) the router itself  is  a
            member  of  group  A.  The router lists a directly connected



[Moy]                                                          [Page 12]

Internet Draft        Multicast Extensions to OSPF        September 1992


            transit network in the group-membership-LSA for group  A  if
            both  1)  the router is Designated Router on the network and
            2) the network contains one or more group A members.

            Consider again the example pictured in Figure 1.  If  router
            RT3  has been elected Designated Router for network N3, then
            Table 1: lists the local  group  database  for  the  routers
            RT1-RT4.

            In this case, each of the routers RT1, RT2 and RT3 will ori-
            ginate  a group-membership-LSA for Group B. In addition, RT2
            will also be originating a group-membership-LSA for Group A.
            RT1  and  RT2's  group-membership-LSAs  will list solely the
            routers themselves (N1 and  N2  are  stub  networks).  RT3's
            group-membership-LSA will list the transit network N3.

            Figure 2 displays the Autonomous System's link  state  data-
            base.  A router/transit network is labelled with a multicast
            group if (and only if) it has been  mentioned  in  a  group-
            membership-LSA for the group When building the shortest-path
            tree for a particular  multicast  datagram,  this  labelling
            enables  those  branches  without group members to be pruned
            from  the  tree.  The  process  of  building   a   multicast
            datagram's shortest path tree is discussed in Section 2.3.2.

            Note that none of the hosts in Figure 1 belonging to  multi-
            cast  groups  A  and  B show up explicitly in the link state
            database (see Figure 2).  In fact, looking at the link state
            database  you cannot even determine which stub networks con-
            tain multicast group members. The link state database simply
            indicates  those  routers/transit  networks  having attached
            group members. This is all that is necessary for  successful
            forwarding of multicast datagrams.




                 Router   local group database
                 _____________________________________
                 RT1      [Group B, N1]
                 RT2      [Group A, N2], [Group B, N2]
                 RT3      [Group B, N3]
                 RT4      None


                 Table 1: Sample local group databases





[Moy]                                                          [Page 13]

Internet Draft        Multicast Extensions to OSPF        September 1992



                                **FROM**

                 |RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|
                 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11|12|N3|N6|N8|N9|
              ----- ---------------------------------------------
              RT1|  |  |  |  |  |  |  |  |  |  |  |  |0 |  |  |  |
              RT2|  |  |  |  |  |  |  |  |  |  |  |  |0 |  |  |  |
              RT3|  |  |  |  |  |6 |  |  |  |  |  |  |0 |  |  |  |
              RT4|  |  |  |  |8 |  |  |  |  |  |  |  |0 |  |  |  |
              RT5|  |  |  |8 |  |6 |6 |  |  |  |  |  |  |  |  |  |
              RT6|  |  |8 |  |7 |  |  |  |  |5 |  |  |  |  |  |  |
              RT7|  |  |  |  |6 |  |  |  |  |  |  |  |  |0 |  |  |
          *   RT8|  |  |  |  |  |  |  |  |  |  |  |  |  |0 |  |  |
          *   RT9|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |0 |
          T  RT10|  |  |  |  |  |7 |  |  |  |  |  |  |  |0 |0 |  |
          O  RT11|  |  |  |  |  |  |  |  |  |  |  |  |  |  |0 |0 |
          *  RT12|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |0 |
          *    N1|3 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
               N2|  |3 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
               N3|1 |1 |1 |1 |  |  |  |  |  |  |  |  |  |  |  |  |
               N4|  |  |2 |  |  |  |  |  |  |  |  |  |  |  |  |  |
               N6|  |  |  |  |  |  |1 |1 |  |1 |  |  |  |  |  |  |
               N7|  |  |  |  |  |  |  |4 |  |  |  |  |  |  |  |  |
               N8|  |  |  |  |  |  |  |  |  |3 |2 |  |  |  |  |  |
               N9|  |  |  |  |  |  |  |  |1 |  |1 |1 |  |  |  |  |
              N10|  |  |  |  |  |  |  |  |  |  |  |2 |  |  |  |  |
              N11|  |  |  |  |  |  |  |  |3 |  |  |  |  |  |  |  |
              N12|  |  |  |  |8 |  |2 |  |  |  |  |  |  |  |  |  |
              N13|  |  |  |  |8 |  |  |  |  |  |  |  |  |  |  |  |
              N14|  |  |  |  |8 |  |  |  |  |  |  |  |  |  |  |  |
              N15|  |  |  |  |  |  |9 |  |  |  |  |  |  |  |  |  |
               H1|  |  |  |  |  |  |  |  |  |  |  |10|  |  |  |  |


                     Figure 2: The MOSPF database.

                 Networks and routers are represented by vertices.
                 An edge of cost X connects Vertex A to Vertex B iff
                 the intersection of Column A and Row B is marked
                 with an X. In addition, RT1, RT2 and N3 are labelled
                 with multicast group A and RT1, N6 and RT9 are
                 labelled with multicast group B.

        2.3.2.  A datagram's shortest-path tree

            While  the  local  group  database  facilitates  the   local
            delivery  of  multicast  datagrams, the datagram's shortest-



[Moy]                                                          [Page 14]

Internet Draft        Multicast Extensions to OSPF        September 1992


            path tree describes the intermediate hops taken by a  multi-
            cast  datagram  as it travels from its source to the indivi-
            dual  multicast  group  members.  As  mentioned  above,  the
            datagram's shortest-path tree is a pruned shortest-path tree
            rooted  at  the  datagram's  source.  Two  datagrams  having
            differing  [source  net,  multicast  destination]  pairs may
            have, and in  fact  probably  will  have,  different  pruned
            shortest-path trees.

            A datagram's shortest path tree  is  built  "on  demand"[6],
            i.e., when the first multicast datagram is received having a
            particular [source net, multicast destination]  combination.
            To  build  the  datagram's shortest-path tree, the following
            calculations are performed. First the datagram's  source  IP
            network  is  located  in the link state database. Then using
            the router-LSAs and network-LSAs in the link state database,
            a  shortest-path  tree is built having the source network as
            root. To complete the process, the branches that do not con-
            tain  routers/transit  networks that have been labelled with
            the  particular  multicast   destination   (via   a   group-
            membership-LSA) are pruned from the tree.

            As an example of the building of a datagram's shortest  path
            tree,  again consider the Autonomous System in Figure 1. The
            Autonomous System's link state database is pictured in  Fig-
            ure 2. When a router initially receives a multicast datagram
            sent by Host H2 to the  multicast  group  A,  the  following
            steps  are  taken: Host H2 is first determined to be on net-
            work N4. Then the shortest path tree rooted  at  net  N4  is
            calculated[7],  pruning  those  branches that do not contain
            routers/transit networks that have been  labelled  with  the
            multicast  group A. This results in the pruned shortest-path
            tree pictured in Figure 3. Note that at this point  the  all
            the leaves of the tree are routers/transit networks labelled
            with multicast group A (routers RT2 and RT9 and transit net-
            work N6).

            In order to forward the multicast datagram, each router must
            find  its own position in the datagram's shortest path tree.
            The router's (call it router RT1) position in the datagram's
            pruned shortest-path tree consists of 1) RT1's parent in the
            tree (this will be the  forwarding  cache  entry's  upstream
            node) and 2) the list of RT1's interfaces that lead to down-
            stream routers/transit networks that have been labelled with
            the  datagram's destination (these will be added to the for-
            warding cache entry as  downstream  interfaces).  Note  that
            after  calculating  the  datagram's  shortest  path  tree, a
            router may find that it is itself  not  on  the  tree.  This



[Moy]                                                          [Page 15]

Internet Draft        Multicast Extensions to OSPF        September 1992



                                       o RT3 (N4, origin)
                                      / \
                                    1/   \8
                                    /     \
                           N3 (Mb) o       o RT6
                                  /         \
                                0/           \7
                                /             \
                   RT2 (Ma,Mb) o               o RT10
                                              / \
                                            3/   \1
                                            /     \
                                        N8 o       o N6 (Ma)
                                          /
                                        0/
                                        /
                                  RT11 o
                                      /
                                    1/
                                    /
                                N9 o
                                  /
                                0/
                                /
                      RT9 (Ma) o



                 Figure 3: Sample datagram's shortest-path tree,
                          source N4, destination Group A

            would be indicated by a forwarding  cache  entry  having  no
            upstream node or an empty list of downstream interfaces.

            As an example of a router describing  its  position  on  the
            datagram's  shortest-path tree, consider Router RT10 in Fig-
            ure 3. The upstream node for the datagram is router RT6, and
            there  are two downstream interfaces: one connecting to net-
            work N6 and the other connecting to network N8.

        2.3.3.  Support for Non-broadcast networks

            When forwarding multicast datagrams over non-broadcast  net-
            works, the datagram cannot be sent as a link-level multicast
            (since neither link-level multicast nor broadcast  are  sup-
            ported  on  these  networks),  but must instead be forwarded
            separately  to  specific  neighbors.  To  facilitate   this,



[Moy]                                                          [Page 16]

Internet Draft        Multicast Extensions to OSPF        September 1992


            forwarding  cache entries can also contain downstream neigh-
            bors as well as downstream interfaces.

            The IGMP protocol is not  defined  over  non-broadcast  net-
            works.  For  this  reason,  there  cannot  be  group members
            directly attached to non-broadcast  networks,  nor  do  non-
            broadcast  networks  ever  appear  in  local  group database
            entries.

            As an example, suppose that network N3 in  Figure  1  is  an
            X.25  PDN.  Consider Router RT3's forwarding cache entry for
            datagrams having source network N4 and multicast destination
            Group  B.  In  place  of  having the interface to network N3
            appear as the downstream interface in the matching  forward-
            ing  cache  entry, the neighboring routers RT1 and RT2 would
            instead appear as separate downstream  neighbors.  In  addi-
            tion,  in  this  case  there  could  not be a group B member
            directly attached to network N3.

        2.3.4.  Details concerning forwarding cache entries

            Each of the  downstream  interface/neighbors  in  the  cache
            entry is labelled with a TTL value. This value indicates the
            number of hops a datagram forwarded out of the interface (or
            forwarded  to  the  neighbor)  would  have  to travel before
            encountering a router/transit network requesting the  multi-
            cast  destination. The reason that a hop count is associated
            with  each  downstream  interface/neighbor  is  so  that  IP
            multicast's  expanding  ring  search  procedure  can be more
            efficiently implemented. By expanding ring search  is  meant
            the following. Hosts can restrict the range of the IP multi-
            cast datagrams that they send by appropriate setting of  the
            TTL  value  in the datagram's IP header.  Then, for example,
            to search for the nearest server the host  can  send  multi-
            casts  first  with TTL set to 1, then 2, etc. By attaching a
            hop count to each downstream interface/neighbor in the  for-
            warding  cache,  datagrams will not be forwarded unless they
            will ultimately reach a multicast destination  before  their
            TTL  expires[8].  This avoids wasting network bandwidth dur-
            ing an expanding ring search.

            As an example consider Router  RT10's  forwarding  cache  in
            Figure  3.   Router  RT10's  cache  entry has two downstream
            interfaces. The first, connecting to network N6, is labelled
            as  having  a  group  member  one hop away (Network N6). The
            second, which connects to network N8, is labelled as  having
            a group member two hops away (Router RT9).




[Moy]                                                          [Page 17]

Internet Draft        Multicast Extensions to OSPF        September 1992


            Both the datagram shortest path tree  and  the  local  group
            database  may  contribute  downstream interfaces to the for-
            warding cache entries. As an example,  if  a  router  has  a
            local  group  database  entry of [Group G, NX], then an for-
            warding cache entry for Group G, regardless of  destination,
            will list the router interface to Network NX as a downstream
            interface.  Such  a  downstream  interface  will  always  be
            labelled with a TTL of 1.

            As an example of forwarding cache  entries,  again  consider
            the  Autonomous System pictured in Figure 1. Suppose Host H2
            sends a multicast datagram to multicast  group  B.  In  that
            case,  several routers will not even attempt to build a for-
            warding cache entry (routers RT5 and RT7) because they  will
            never  receive  the  multicast  datagram in the first place.
            Other routers will receive  the  multicast  datagram  (since
            they  are  forwarded  as  link-level  multicasts), but after
            building the pruned shortest path tree will notice that they
            themselves are not a part of the tree (routers RT1, RT4, RT8
            and RT12). These latter routers will install an empty  cache
            entry,  indicating  that they do not participate in the for-
            warding of the multicast datagram. A sample of the  forward-
            ing  cache  entries  built by the other routers in the Auto-
            nomous System is pictured in Table 2.

            A MOSPF router must clear its entire forwarding  cache  when
            the  Autonomous  System's  topology changes, because all the
            datagram shortest-path trees must be rebuilt. Likewise, when
            the  location  of  a  multicast  group's  membership changes
            (reflected by a change in group-membership-LSAs), all  cache
            entries associated with the particular multicast destination
            group  must  be  cleared.  Other  than  these   two   cases,


              Router   Upstream     Downstream interfaces
                       node         (interface:hops)
              ___________________________________________
              RT10     Router RT6   (N6:1), (N8:3)
              RT11     Net N8       (N9:2)
              RT3      Net N4       (N3:1), (RT6:3)
              RT6      Router RT3   (RT10:2)
              RT2      Net N3       (N2:1)


               Table 2: Sample forwarding cache entries,
                 for source N4 and destination Group A.





[Moy]                                                          [Page 18]

Internet Draft        Multicast Extensions to OSPF        September 1992


            forwarding cache entries need not ever be deleted or  other-
            wise  modified;  in particular, the forwarding cache entries
            do not have to be aged. However,  forwarding  cache  entries
            can be freely deleted after some period of inactivity (i.e.,
            garbage collected), if router memory resources are in  short
            supply.

3.  Inter-area multicasting

    Up to this point this memo has discussed multicast  forwarding  when
    the  entire  Autonomous  System is a single OSPF area. The logic for
    when the multicast  datagram's  source  and  its  destination  group
    members  belong  to  the  same  OSPF  area is the same. This section
    explains the behavior of the  MOSPF  protocol  when  the  datagram's
    source  and  (at least some of) its destination group members belong
    to different OSPF areas. This situation is called inter-area  multi-
    cast.

    Inter-area multicast brings  up  the  following  issues,  which  are
    resolved in succeeding sections:

    o   Are the group-membership-LSAs specific to a specific  area?  And
        if  they  are, how is group membership information conveyed from
        one area to the next?

    o   How are the datagram shortest-path trees built in the inter-area
        case,  since complete information concerning the topology of the
        datagram source's neighborhood is not available  to  routers  in
        other areas?

    o   In an area border router, multiple datagram shortest-path  trees
        are  built,  one  for each attached area. How are these separate
        datagram shortest-path trees combined into a  single  forwarding
        cache entry?

    It should be noted in the following that the basic protocol  mechan-
    isms in the inter-area case are the same as for the intra-area case.
    Forwarding of multicasts is still defined by  the  contents  of  the
    forwarding  cache. The forwarding cache is still built from the same
    two components: the local group database and the datagram  shortest-
    path  trees. And while the calculation of the datagram shortest-path
    trees is different in the inter-area case  (see  Section  3.2),  the
    local  group database is built exactly the same as in the intra-area
    case (i.e., MOSPF's interface with IGMP  remains  unchanged  in  the
    presence  of  areas). Finally, the forwarding algorithm described in
    Section 11 is the same for both the intra-area and inter-area cases.





[Moy]                                                          [Page 19]

Internet Draft        Multicast Extensions to OSPF        September 1992


    The following discussion uses the  area  configuration  pictured  in
    Figure  4 as an example. This figure, taken from the OSPF specifica-
    tion, shows an Autonomous System split into  three  areas  (Area  1,
    Area  2  and  Area  3).  A  single backbone area has been configured
    (everything outside of the shading). Since the backbone area must be
    contiguous,  a  single  virtual link has been configured between the
    area border routers RT10 and RT11.  Additionally,  an  area  address
    range has been configured in Router RT11 so that Networks N9-N11 and
    Host H1 will be reported as a single route outside of  Area  3  (via
    summary-LSAs).

    3.1.  Extent of group-membership-LSAs

        Group-membership-LSAs are specific to a single OSPF  area.  This
        means  that,  just  as  with  OSPF router-LSAs, network-LSAs and
        summary-link-LSAs, a group-membership-LSA is flooded  throughout
        a  single  area  only[9].   A  router attached to multiple areas
        (i.e., an area border router) may  end  up  originating  several
        group-membership-LSAs concerning a single multicast destination,
        one for each attached area.  However, as we will see below,  the
        contents  of  these group-membership-LSAs will vary depending on
        their associated areas.

        Just as in OSPF, each MOSPF area has its own  link  state  data-
        base.  The MOSPF database is simply the OSPF link state database
        enhanced by the group-membership-LSAs. Consider again  the  area
        configuration  pictured  in  Figure  4. The result of adding the
        group-membership-LSAs to the area databases yields the databases
        pictured  in  Figures  6  and  7.  Figure 6 shows Area 1's MOSPF
        database. Figure 7 shows the backbone's MOSPF  database.  Super-
        scripts  indicate which transit vertices have been advertised as
        requesting particular multicast destinations. A  superscript  of
        "w"  indicates  that the router is advertising itself as a wild-
        card multicast receiver (see below). The dashed lines  are  OSPF
        summary-link-LSAs or external-link-LSAs.

        Suppose an OSPF router has a  local  group  database  entry  for
        [Group  Y,  network  X].  The  router  then  originates a group-
        membership-LSA for Group Y into the area containing  network  X.
        For  example,  in  the  area configuration pictured in Figure 4,
        Router RT1 originates a group-membership-LSA for Group  B.  This
        group-membership-LSA  is  flooded  throughout  Area  1,  and  no
        further. Likewise, assuming that Router  RT3  has  been  elected
        Designated  Router  for  network  N3,  RT3  originates  a group-
        membership-LSA into Area 1 listing the  transit  network  N3  as
        having  group  members. Note that in the link state database for
        Area 1 (Figure 6) both Router RT1 and network  N3  have  accord-
        ingly been labelled with Group B.



[Moy]                                                          [Page 20]

Internet Draft        Multicast Extensions to OSPF        September 1992



           ..................................
           .     +                          .
           .     | 3+---+    +--+  +--+     . N12      N14
           .   N1|--|RT1|\1  |Mb|  |H4|     .   \ N13 /
           .    _|  +---+ \  +--+ /+--+     .   8\ |8/8
           .   | +         \ _|__/          .     \|/
           . +--+   +--+    /    \   1+---+8.   8+---+6
           . |Mb|   |Mb|   *  N3  *---|RT4|------|RT5|--------+
           . +--+  /+--+    \____/    +---+ .    +---+        |
           .      +         /   |           .      |7         |
           .      | 3+---+ /    |           .      |          |
           .    N2|--|RT2|/1    |1          .      |6         |
           .    __|  +---+    +---+8        .   6+---+        |
           .   |  +           |RT3|--------------|RT6|        |
           . +--+    +--+     +---+     +--+.    +---+        |
           . |Ma|    |H3|_      |2     _|H2|.    Ia|7         |
           . +--+    +--+ \     |     / +--+.      |          |
           .               +---------+      .      |          |
           .Area 1             N4           .      |          |
           ..................................      |          |
           ................................        |          |
           .           N11                .        |          |
           .       +---------+            .        |          |
           .            |     \           .        |          |    N12
           .            |3     +--+       .        |          |6 2/
           .          +---+    |Ma|       .        |        +---+/
           .          |RT9|    +--+       .        |        |RT7|---N15
           .          +---+               .......  |        +---+ 9
           .            |1                .. +  ...|..........|1........
           .           _|__               .. |   Ib|5       __|_   +--+.
           .          /    \      1+----+2.. |  3+----+1   /    \--|Ma|.
           .         *  N9  *------|RT11|----|---|RT10|---*  N6  * +--+.
           .          \____/       +----+ .. |   +----+    \____/      .
           .            |            !*******|*****!          |        .
           .            |1           Virtual + Link           |1       .
           . +--+   10+----+              ..N8              +---+      .
           . |H1|-----|RT12|              ..                |RT8|      .
           . +--+SLIP +----+              ..                +---+  +--+.
           .            |2                ..                  |4  _|H5|.
           .            |                 ..                  |  / +--+.
           .       +---------+            ..              +--------+   .
           .           N10          Area 3..Area 2            N7       .
           .............................................................

                    Figure 4: A sample MOSPF area configuration





[Moy]                                                          [Page 21]

Internet Draft        Multicast Extensions to OSPF        September 1992


        In OSPF, the area border routers forward routing information and
        data  traffic  between  areas.  In  MOSPF.  a subset of the area
        border routers, called the inter-area multicast forwarders, for-
        ward   group  membership  information  and  multicast  datagrams
        between areas. Whether a given OSPF area border router is also a
        MOSPF  inter-area multicast forwarder is configuration dependent
        (see Section B.1). In Figure 4 we assume that  all  area  border
        routers are also inter-area multicast forwarders.

        In order to convey group membership information  between  areas,
        inter-area   multicast  forwarders  "summarize"  their  attached
        areas' group membership to the backbone. This  is  very  similar
        functionality to the summary-link-LSAs that are generated in the
        base OSPF protocol.  An inter-area  multicast  forwarder  calcu-
        lates  which  groups  have  members in its attached non-backbone
        areas. Then, for each of these groups, the inter-area  multicast
        forwarder injects a group-membership-LSA into the backbone area.
        For example, in Figure 4 there are two groups having members  in
        Area  1:  Group A and Group B. For that reason, both of Area 1's
        inter-area multicast forwarders (Routers  RT3  and  RT4)  inject
        group-membership-LSAs  for  these  two groups into the backbone.
        As a result both of these routers are labelled with Groups A and
        B in the backbone link state database (see Figure 7).

        However, unlike the summarization of unicast destinations in the
        base  OSPF  protocol,  the  summarization of group membership in
        MOSPF is asymmetric. While a non-backbone area's  group  member-
        ship is summarized to the backbone, this information is not then
        readvertised  into  other  non-backbone  areas.   Nor   is   the
        backbone's  group  membership  summarized  for  the non-backbone
        areas. Going back to the example in Figure 4, while the presence
        of  Area 3's group (Group A) is advertised to the backbone, this
        information is not then redistributed to Area 1. In other words,
        routers  internal  to  Area  1  have  no  idea of Area 3's group
        membership.

                membership    +------------------+   datagrams
                    + > > > >>|     Backbone     |< < < < +
                    ^         +------------------+        ^
                    ^        /         |          \       ^
                    ^       /          |           \      ^
               +----^-----+/      +----------+      \+----^-----+
               |  Area 1  |       |  Area 2  |       |  Area 3  |
               +----------+       +----------+       +----------+

                    Figure 5: Inter-area routing architecture





[Moy]                                                          [Page 22]

Internet Draft        Multicast Extensions to OSPF        September 1992


        At this point, if no extra functionality  was  added  to  MOSPF,
        multicast  traffic  originating in Area 1 destined for Multicast
        Group A would never be forwarded to those  group  A  members  in
        Area 3. To accomplish this, the notion of wild-card receivers is
        introduced. A wild-card receiver is a router to which all multi-
        cast  traffic,  regardless  of  multicast destination, should be
        forwarded. A router's wild-card multicast  reception  status  is
        per-area.  In  non-backbone areas, all inter-area multicast for-
        warders[10] are wild-card  multicast  receivers.   This  ensures
        that  all  multicast  traffic originating in a non-backbone area
        will be forwarded to its inter-area  multicast  forwarders,  and
        hence  to  the  backbone  area.  Since the backbone has complete
        knowledge of all areas' group membership, the datagram can  then
        be  forwarded  to  all  group members. Note that in the backbone
        itself there is no need for wild-card  multicast  receivers[11].
        As  an example, note that Routers RT3 and RT4 are wild-card mul-
        ticast receivers in Area 1 (see Figure 6), while there are  none
        in the backbone (see Figure 7).

        This yields the inter-area routing architecture pictured in Fig-
        ure  5.   All group membership is advertised by the non-backbone
        areas into the backbone.  Likewise,  all  IP  multicast  traffic
        arising  in the non-backbone areas is forwarded to the backbone.
        Since at this point group membership information meets the  mul-
        ticast  datagram traffic, delivery of the datagrams becomes pos-
        sible.

    3.2.  Building inter-area datagram shortest-path trees

        When building datagram shortest-path trees in  the  presence  of
        areas,  it is often the case that the source of the datagram and
        (at least some of) the destination group members are in separate
        areas.  Since  detailed  topological  information concerning one
        OSPF area is not distributed to other OSPF areas  (the  flooding
        of  router-LSAs,  network-LSAs and group-membership-LSAs is res-
        tricted to a single OSPF area only), the  building  of  complete
        datagram  shortest-path  trees is often impossible in the inter-
        area case. To compensate, approximations are  made  through  the
        use of wild-card multicast receivers and OSPF summary-LSAs.

        When it first receives a datagram for a particular [source  net,
        destination group] pair, a router calculates a separate datagram
        shortest-path tree for each of the router's attached areas. Each
        datagram  shortest-path tree is built solely from LSAs belonging
        to the particular area's link state  database.  Suppose  that  a
        router  is calculating a datagram shortest-path tree for Area A.
        It is useful then to separate out two cases.




[Moy]                                                          [Page 23]

Internet Draft        Multicast Extensions to OSPF        September 1992



                                  **FROM**

                             |RT|RT|RT|RT|RT|RT|
                             |1 |2 |3 |4 |5 |7 |N3|
                          ----- -------------------
                          RT1|  |  |  |  |  |  |0 |
                          RT2|  |  |  |  |  |  |0 |
                          RT3|  |  |  |  |  |  |0 |
                      *   RT4|  |  |  |  |  |  |0 |
                      *   RT5|  |  |14|8 |  |  |  |
                      T   RT7|  |  |20|14|  |  |  |
                      O    N1|3 |  |  |  |  |  |  |
                      *    N2|  |3 |  |  |  |  |  |
                      *    N3|1 |1 |1 |1 |  |  |  |
                           N4|  |  |2 |  |  |  |  |
                        Ia,Ib|  |  |15|22|  |  |  |
                           N6|  |  |16|15|  |  |  |
                           N7|  |  |20|19|  |  |  |
                           N8|  |  |18|18|  |  |  |
                    N9-N11,H1|  |  |19|16|  |  |  |
                          N12|  |  |  |  |8 |2 |  |
                          N13|  |  |  |  |8 |  |  |
                          N14|  |  |  |  |8 |  |  |
                          N15|  |  |  |  |  |9 |  |


                     Figure 6: Area 1's MOSPF database.

             Networks and routers are represented by vertices.
             An edge of cost X connects Vertex A to Vertex B iff
             the intersection of Column A and Row B is marked
             with an X. In addition, RT1, RT2 and N3 are labelled
             with multicast group A, RT1 is labelled with multicast
             group B, and both RT3 and RT4 are labelled as
             wild-card multicast receivers.















[Moy]                                                          [Page 24]

Internet Draft        Multicast Extensions to OSPF        September 1992


                                 **FROM**

                           |RT|RT|RT|RT|RT|RT|RT
                           |3 |4 |5 |6 |7 |10|11|
                        ------------------------
                        RT3|  |  |  |6 |  |  |  |
                        RT4|  |  |8 |  |  |  |  |
                        RT5|  |8 |  |6 |6 |  |  |
                        RT6|8 |  |7 |  |  |5 |  |
                        RT7|  |  |6 |  |  |  |  |
                    *  RT10|  |  |  |7 |  |  |2 |
                    *  RT11|  |  |  |  |  |3 |  |
                    T    N1|4 |4 |  |  |  |  |  |
                    O    N2|4 |4 |  |  |  |  |  |
                    *    N3|1 |1 |  |  |  |  |  |
                    *    N4|2 |3 |  |  |  |  |  |
                         Ia|  |  |  |  |  |5 |  |
                         Ib|  |  |  |7 |  |  |  |
                         N6|  |  |  |  |1 |1 |3 |
                         N7|  |  |  |  |5 |5 |7 |
                         N8|  |  |  |  |4 |3 |2 |
                  N9-N11,H1|  |  |  |  |  |  |1 |
                        N12|  |  |8 |  |2 |  |  |
                        N13|  |  |8 |  |  |  |  |
                        N14|  |  |8 |  |  |  |  |
                        N15|  |  |  |  |9 |  |  |


                 Figure 7: The backbone's MOSPF database.

             Networks and routers are represented by vertices.
             An edge of cost X connects Vertex A to Vertex B iff
             the intersection of Column A and Row B is marked
             with an X. In addition, RT3 and RT4 are labelled
             with both multicast groups A and B, and RT7, RT10,
             and RT11 are labelled with multicast group A.

        The first case, Case 1: The source of the  datagram  belongs  to
        Area  A has already been described in Section 2.3.2. However, in
        the presence of OSPF areas, during tree  pruning  care  must  be
        taken  so that the branches leading to other areas remain, since
        it is unknown whether there are group members in these  (remote)
        areas.  For  this  reason,  only  those branches having no group
        members nor wild-card receivers are pruned  when  producing  the
        datagram shortest-path tree.

        As an example, suppose in Figure 4 that Host H2 sends  a  multi-
        cast  datagram  to  destination  Group  A.  Then  the datagram's



[Moy]                                                          [Page 25]

Internet Draft        Multicast Extensions to OSPF        September 1992


        shortest-path tree for Area 1, built identically by all  routers
        in  Area  1  receiving  the datagram, is shown in Figure 8. Note
        that both inter-area multicast forwarders (RT3 and RT4)  are  on
        the  datagram's shortest-path tree, ensuring the delivery of the
        datagram to the backbone and to Areas 2 and 3.

        o   Case 2: The source of the datagram belongs to an area  other
            than  Area  A.  In  this  case,  when  building the datagram
            shortest-path tree for Area A, the immediate neighborhood of
            the   datagram's  source  is  unknown.  However,  there  are
            summary-LSAs in the Area A link  state  database  indicating
            the  cost  of  the paths between each of Area A's inter-area
            multicast forwarders and the datagram source. These  summary
            links  are  used  to  approximate  the  neighborhood  of the
            datagram's source; the tree begins with links directly  con-
            necting  the source to each of the inter-area multicast for-
            warders. These links point in the reverse direction (towards
            instead  of  away  from  the datagram source) from the links
            considered in Case 1 above. All additional  links  added  to
            the  tree  also  point  in  the reverse direction. The final
            datagram shortest-path tree is then produced by, as  before,
            pruning  all  branches having no group-members nor wild-card
            receivers.

            As an example, suppose again that Host H2 in Figure 4  sends
            a  multicast datagram to destination Group A. The datagram's
            shortest-path tree for the backbone is shown  in  Figure  9.
            The  neighborhood  around  the  source (network N4) has been
            approximated by the summary links advertised by routers  RT3
            and  RT4.  Note  that  all  links  in  Figure  9's  datagram
            shortest-path tree  have  arrows  pointing  in  the  reverse
            direction, towards network N4 instead of away from it.

                                      o RT3 (W, origin=N4)
                                      |
                                     1|
                                      |
                              N3 (Mb) o
                                     / \
                                   0/   \0
                                   /     \
                      RT2 (Ma,Mb) o       o RT4 (W)


                    Figure 8: Datagram's shortest-path tree,
                      Area 1, source N4, destination Group A





[Moy]                                                          [Page 26]

Internet Draft        Multicast Extensions to OSPF        September 1992



                                     o N4
                                    / \
                                  2/   \3
                                  /     \
                     RT3 (Ma,Mb) o       o RT4 (Ma,Mb)
                                /         \
                              6/           \8
                              /             \
                         RT6 o               o RT5
                             |               |
                            5|               |6
                             |               |
                   RT10 (Ma) o               o RT7 (Ma)
                             |
                            2|
                             |
                   RT11 (Ma) o



               Figure 9: Datagram shortest-path tree: Backbone,
                  source N4, destination Group A. Note that
                  reverse costs (i.e., toward origin) are
                             used throughout.


        The reverse costs used for the entire tree in Case 2 are  forced
        because  summary-LSAs only specify the cost towards the datagram
        source. In the presence of asymmetric link costs, this may  lead
        to  less  efficient  routes  when  forwarding multicasts between
        areas

        Those routers attached to multiple areas must calculate multiple
        trees  and then merge them into a single forwarding cache entry.
        As shown in Section 2.3.2, when connected to a single  area  the
        router's  position on the datagram shortest-path tree determines
        (in large part) its forwarding cache  entry.  When  attached  to
        multiple   areas,   and   hence  calculating  multiple  datagram
        shortest-path trees, each tree  contributes  to  the  forwarding
        cache  entry's list of downstream interfaces/neighbors. However,
        only one of the areas' datagram shortest-path trees will  deter-
        mine the forwarding cache entry's upstream node. When one of the
        attached areas contains the  datagram  source,  that  area  will
        determine the upstream node. Otherwise, the tiebreaking rules of
        Section 12.2.7 are invoked.





[Moy]                                                          [Page 27]

Internet Draft        Multicast Extensions to OSPF        September 1992


        Consider again the example of Host H2 in Figure 4 sending a mul-
        ticast  datagram  to destination Group A. Router RT3 will calcu-
        late two datagram shortest-path trees, one for Area  1  and  one
        for  the  backbone.   Since the source of the datagram (Host H2)
        belongs to Area 1, the Area 1 datagram shortest-path tree deter-
        mines RT3's upstream node: Network N4. Router RT3 calculates two
        downstream interfaces for the datagram: the interface to network
        N3  (which  comes from Area 1's datagram shortest-path tree) and
        the serial line to router RT6 (which comes from  the  backbone's
        datagram  shortest-path tree). As for Router RT10, it calculates
        two trees, determining its upstream node from the backbone  tree
        and  its  two  downstream  interfaces  from  the  Area  2  tree.
        Finally, Router RT11 calculates  three  trees,  determining  its
        upstream  node from the Area 2 tree and its downstream interface
        from the Area 3 tree.

4.  Inter-AS multicasting

    This section explains how MOSPF deals with the forwarding of  multi-
    cast  datagrams  between  Autonomous  Systems.  Certain  AS boundary
    routers in a MOSPF system will be configured as  inter-AS  multicast
    forwarders. It is assumed that these routers will also be running an
    inter-AS multicast routing protocol.  This  specification  does  not
    dictate  the  operation of such an inter-AS multicast routing proto-
    col. However, the  following  interactions  between  MOSPF  and  the
    inter-AS routing protocol are assumed:

    (1) MOSPF guarantees that the  inter-AS  multicast  forwarders  will
        receive  all multicast datagrams; but it is up to each router so
        designated to determine whether the datagram should be forwarded
        to other Autonomous Systems. This determination will probably be
        made via the inter-AS routing protocol.

    (2) MOSPF assumes that the inter-AS routing protocol  is  forwarding
        multicast  datagrams  in  an  RPF  (reverse path forwarding; see
        [Deering] for an explanation of this  terminology)  fashion.  In
        other  words,  it  is  assumed  that  a multicast datagram whose
        source (call it X) lies outside the MOSPF domain will enter  the
        MOSPF  domain  at  those points that are advertising (into OSPF)
        the best routes back to X. MOSPF  calculates  the  path  of  the
        datagram through the MOSPF domain based on this assumption.

    MOSPF designates an inter-AS multicast forwarder as a wild-card mul-
    ticast  receiver  in all of its attached areas. As in the inter-area
    case, this ensures that the routers remain on all  pruned  shortest-
    path  trees  and thereby receive all multicast datagrams, regardless
    of destination.




[Moy]                                                          [Page 28]

Internet Draft        Multicast Extensions to OSPF        September 1992


    The presence of inter-AS multicast forwarders is  reflected  in  the
    contents  of the link state database[12].  Suppose that in Figure 1,
    both RT5 and RT7 were configured as inter-AS  multicast  forwarders.
    Then  the  link  state  database would look like the one pictured in
    Figure 2, with the addition of a) wild-card status for RT5  and  RT7
    (they  would  appear  with  superscripts of "w") and b) the external
    links originated  by  RT5  and  RT7  being  labelled  as  multicast-
    capable[13].

    Consider instead the area configuration in Figure 4.  Again  suppose
    RT5 and RT7 are configured as inter-AS multicast forwarders. Then in
    Area 1's link state database (Figure 6),  the  external  links  ori-
    ginated by RT5 and RT7 would again be labelled as multicast-capable.
    However, note that in Area 1's database RT5 and RT7 are not labelled
    as  wild-card  multicast  receivers. This is unnecessary; since Area
    1's inter-area multicast forwarders (RT3 and  RT4)  are  wild-cards,
    all  multicast  datagrams  will be forwarded to the backbone. And in
    the backbone's link state database (Figure 7), RT5 and RT7  will  be
    labelled as wild-cards.

    4.1.  Building inter-AS datagram shortest-path trees.

        When multicast datagrams are to be forwarded between  Autonomous
        Systems,  the  datagram  shortest-path tree is built as follows.
        Remember that the router builds a separate tree for each area to
        which  it is attached; these trees are then merged into a single
        forwarding cache entry. Suppose that the router is building  the
        tree for Area A. We break up the tree building into three cases.
        This first two cases have already been described earlier in this
        memo: Case 1 (the source of the datagram belongs to Area A) hav-
        ing been described in Section 2.3.2 and Case 2  (the  source  of
        the datagram belongs to another OSPF area) having been described
        in Section 3.2. The only modification to  these  cases  is  that
        inter-AS  multicast  forwarders,  as  well  as group members and
        inter-area multicast  forwarders,  must  remain  on  the  pruned
        trees.  The new case is as follows:

        o   Case 3: The source of the datagram belongs to another  Auto-
            nomous  System.  The immediate neighborhood of the source is
            then unknown. In this case the multicast-capable AS external
            links  are  used  to  approximate  the  neighborhood  of the
            source; the tree begins with links  directly  attaching  the
            source  to  one  or  more inter-AS multicast forwarders. The
            approximating AS external links point in the reverse  direc-
            tion  (i.e.,  towards the source), just as with the approxi-
            mating summary links in Case 2. Also,  as  in  Case  2,  all
            links  included in the tree must point in the reverse direc-
            tion. The final datagram shortest-path tree is then produced



[Moy]                                                          [Page 29]

Internet Draft        Multicast Extensions to OSPF        September 1992


            (as  always)  by  pruning  those  branches  having  no group
            members nor wild-card receivers.

            As an example, suppose that a host on Network N12 (see  Fig-
            ure 4) originates a multicast datagram for Destination Group
            B. Assume that all external costs pictured are OSPF external
            type  1  metrics.  Then  any routers in Area 1 receiving the
            datagram would build the datagram  shortest-path  tree  pic-
            tured in Figure 10. Note that all links in the tree point in
            the reverse direction, towards the source.  The  tree  indi-
            cates  that  the  routers  expect  the datagram to enter the
            Autonomous System at router RT7, and then to enter the  area
            at router RT4.

            Note that in those cases where the "best" inter-AS  boundary
            router  is not attached to the area, the neighborhood of the
            source is actually approximated by the  concatenation  of  a
            summary  link and a multicast-capable AS external link. This
            is in fact the case in Figure 10.

        In Case 3 (datagram source in another AS) the  requirement  that
        all  tree  links  point  in  the  reverse direction (towards the
        source) accommodates the fact that summary links and  AS  exter-
        nals  already point in the reverse direction. This also leads to
        the requirement that the  inter-AS  multicast  routing  protocol
        operate in a reverse path forwarding fashion (see condition 2 of
        Section 4). Note that Reverse path forwarding can lead  to  sub-
        optimal routing when costs are configured asymmetrically. And it
        can even lead to non-delivery of multicast datagrams in the case
        of asymmetric reachability.

        Inter-AS multicast forwarders may end up calculating a  forward-
        ing  cache entry's upstream node as being external to the AS. As
        an example, Router RT7 in Figure 10 will end up  calculating  an
        external  router  (via  its external link to network N12) as the
        upstream node for the datagram. This means that RT7 will receive
        the  datagram  from  a router in another AS before injecting the
        datagram into the MOSPF system.

    4.2.  Stub area behavior

        AS external links are not imported into stub areas. Suppose that
        the  source  of  a particular datagram lies outside of the Auto-
        nomous System, and that the datagram is forwarded  into  a  stub
        area.  In the stub area's datagram shortest-path tree the neigh-
        borhood of the datagram's source cannot be  approximated  by  AS
        external  links.  Instead  the  neighborhood  of  the  source is
        approximated by the default summary links (see  Section  3.6  of



[Moy]                                                          [Page 30]

Internet Draft        Multicast Extensions to OSPF        September 1992



                                     o N12
                                     |
                                    2|
                                     |
                                     o RT7
                                     |
                                   14|
                                     |
                                     o RT4 (W)
                                     |
                                    0|
                                     |
                                     o N3 (Mb)
                                    /|\
                                   / | \
                                 1/  | 1\
                                 /  1|   \
                                /    |    \
                      RT1 (Mb) o     |     o RT3 (W)
                                     o
                                RT2 (Ma,Mb)


               Figure 10: Datagram shortest-path tree: Area 1,
                 source N12, destination Group B. Note that
                  reverse costs (i.e., toward origin) are
                             used throughout.

        [OSPF]) that are originated by the stub area's intra-area multi-
        cast forwarders.

        Except for this small change  to  the  construction  of  a  stub
        area's  datagram shortest-path trees, all other MOSPF algorithms
        (e.g., merging with other areas' datagram shortest-path trees to
        form  the  forwarding cache) function the same for stub areas as
        they do for non-stub areas.

5.  Modelling internal group membership

    A MOSPF router may itself contain multicast applications. A  typical
    example  of  this  is a UNIX workstation that doubles as a multicast
    router. This section concerns two alternative ways  of  representing
    the  group  membership  of the MOSPF router's internal applications.
    Both representations have advantages. For maximum  flexibility,  the
    MOSPF  forwarding  algorithm  (see Section 11) has been specified so
    that either representation can be used in a  MOSPF  router  (and  in
    fact,  both  representations  can  be used at once, depending on the



[Moy]                                                          [Page 31]

Internet Draft        Multicast Extensions to OSPF        September 1992


    application).

    The first representation is based on the paradigm presented  in  RFC
    1112. In this case, an application joins a multicast group on one or
    more specific physical interfaces. The application then  receives  a
    multicast  datagram  if  and  only  if  it is received on one of the
    specified interfaces. If a datagram is received on  multiple  speci-
    fied interfaces, the application receives multiple copies. Figure 11
    shows this algorithm as it is implemented  in  (modified)  BSD  UNIX
    kernels.   The  figure shows the processing of a multicast datagram,
    starting with its reception on a particular interface. First  copies
    of  the datagram are given to those applications that have joined on
    the receiving interface. Then the forwarding decision (pictured as a
    box  containing  a question mark) is made, and the packet is (possi-
    bly) forwarded out certain interfaces. If these interfaces  are  not
    capable  of  receiving  their own multicasts, a copy of the datagram
    must be internally looped back to appropriately joined applications.

    The advantages to the RFC 1112 representation are as follows:

    o   It is the standard for  the  way  an  IP  host  joins  multicast
        groups.  It  is  simplest  to  use the same membership model for
        hosts and routers; most would consider an  IP  router  to  be  a

                            +-------+
                            |receive|
                            +-------+
                                |
                                |---> To application
                                |
                      +-------------------+
                      |forwarding decision|
                      +-------------------+
                                |
                               / \
                              /---\----> To application
                             /     \------> To application
                            /       \
                           /         \
                     +--------+  +--------+
                     |transmit|  |transmit|
                     +--------+  +--------+


              Figure 11: RFC 1112 representation of internal
                          group membership





[Moy]                                                          [Page 32]

Internet Draft        Multicast Extensions to OSPF        September 1992


        special case of an IP host anyway.

    o   It is the way group membership has been implemented in BSD UNIX.
        Existing  multicast  applications  are written to join multicast
        groups on specific interfaces.

    o   The  possibility  of  receiving  multiple  datagram  copies  may
        improve  fault  tolerance.  If the datagram is dropped due to an
        error on the path to some interface, another interface may still
        receive a copy.

    o   The ability to specify  a  particular  receiving  interface  may
        improve  the  accuracy  of  IP multicast's TTL scoping mechanism
        (see Section 2.3.4).

    o   Membership in the non-routable  multicast  groups  (224.0.0.1  -
        224.0.0.255)  must  be  on a per-interface basis. An OSPF router
        always belongs to 224.0.0.5 (AllSPFRouters) on its  OSPF  inter-
        faces,  and may belong to 224.0.0.6 (AllDRouters) on one or more
        of its OSPF interfaces.

    The second representation is MOSPF-specific. In this case, an appli-
    cation  joins  a  multicast group on an interface-independent basis.
    In other words, group membership is associated with the router as  a
    whole,  not  separately  on  each  interface.  The  application then
    receives a copy of a multicast datagram if and only if the  datagram
    would actually be forwarded by the MOSPF router. Figure 12 shows how
    this algorithm would be implemented. The datagram is received  on  a
    particular  interface.  If  the datagram is validated for forwarding
    (i.e., the receiving interface connects to the  matching  forwarding
    cache  entry's  upstream node), a copy of the datagram is also given
    to appropriately joined applications. Note that this model of  group
    membership  is  not as general as the RFC 1112 model, in that it can
    only be implemented in MOSPF routers and not in arbitrary IP  hosts.
    However, it has the following advantages:

    o   The application does not need to have knowledge  of  the  router
        interfaces.  It  does  not  need  to  know what kind or how many
        interfaces there are; this will be taken care of  by  the  MOSPF
        protocol itself.

    o   As long as any interface is operational,  the  application  will
        continue  to receive multicast datagrams. This happens automati-
        cally, without the application modifying its group membership.

    o   The application receives only one copy of  the  datagram.  Using
        the  RFC1112  representation,  whenever  an application joins on
        more than one interface (which must be done if  the  application



[Moy]                                                          [Page 33]

Internet Draft        Multicast Extensions to OSPF        September 1992



                            +-------+
                            |receive|
                            +-------+
                                |
                                |
                                |
                      +-------------------+
                      |forwarding decision|---> to application
                      +-------------------+
                                |
                               / \
                              /   \
                             /     \
                            /       \
                           /         \
                     +--------+  +--------+
                     |transmit|  |transmit|
                     +--------+  +--------+


              Figure 12: MOSPF-specific representation of internal
                             group membership

        does not want to rely on a single interface), multiple  datagram
        copies will be received during normal operation.

6.  Additional capabilities

    This section describes the MOSPF configuration  options  that  allow
    routers  of  differing capabilities to be mixed together in the same
    routing domain. Note that these options handle special circumstances
    that  may not be encountered in normal operation. Default values for
    the configuration settings are specified in Appendix B.

    6.1.  Mixing with non-multicast routers

        MOSPF routers can be mixed freely with routers that are  running
        only  the  base  OSPF algorithm (called non-multicast routers in
        the following). This allows MOSPF to be deployed in a  piecemeal
        fashion,  thereby  speeding deployment and allowing experimenta-
        tion with multicast routing on a limited scale.

        When a MOSPF router builds a  datagram  shortest-path  tree,  it
        omits  all  non-multicast  routers. For example, in Figure 1, if
        router RT6 was not a multicast router,  the  datagram  shortest-
        path  tree  in  Figure  3  would be built with a more circuitous
        branch through router RT5, instead of  through  router  RT6.  In



[Moy]                                                          [Page 34]

Internet Draft        Multicast Extensions to OSPF        September 1992


        addition, non-multicast routers do not participate in the flood-
        ing of the new group-membership-LSAs. This adheres to  the  gen-
        eral  principle  that  a  router should not have to handle those
        link state advertisements whose format (or contents) the  router
        does not understand.

        Mixing MOSPF routers with non-multicast routers creates a number
        of  potential  problems.  Certain  mixings  of  MOSPF  and  non-
        multicast routers can cause multicast datagrams to  take  subop-
        timal  paths,  or in other cases can lead to the non-delivery of
        multicast datagrams. In addition, mixing MOSPF routers and  non-
        multicast  routers can cause the paths of multicast datagrams to
        diverge radically from  the  path  of  unicast  datagrams.  Such
        divergences can make routing problems harder to debug.

        In particular, the following  specific  difficulties  may  arise
        when mixing MOSPF routers with non-multicast routers:

        o   Even though there is unicast connectivity to a  destination,
            there  may  not  be  multicast connectivity. For example, if
            Router RT10 in Figure 1 becomes a non-multicast router,  the
            group member connected to network N11 will no longer be able
            to receive multicasts sourced by Host H2.  But the two hosts
            will be able to exchange unicasts (e.g., ICMP pings).

        o   When the Designated Router for a multi-access network  is  a
            non-multicast  router, the network will not be used for for-
            warding multicast datagrams. For example,  if  in  Figure  1
            Router  RT4  is Designated Router for network N3, and RT4 is
            non-multicast, network N3 will not be  used  to  forward  IP
            multicasts.  This  would  mean that multicast datagrams ori-
            ginated by Hosts H2 and H3 would  not  be  forwarded  beyond
            their  local  network  (N4),  even  though it seems that the
            needed multicast connectivity exists.

        o   When forwarding multicast datagrams between areas, mixing of
            MOSPF  routers  and non-multicast routers in the source area
            may cause unexpected loss of multicast connectivity. This is
            because in the inter-area routing of multicast datagrams the
            neighborhood of the datagram's  source  is  approximated  by
            OSPF  summary  link advertisements, and OSPF summary LSAs do
            not carry indications/guarantees of  the  summarized  path's
            multicast routing capability.

    6.2.  TOS-based multicast

        MOSPF allows a separate datagram shortest-path tree to be  built
        for  each  IP  Type  of  Service.  This means that the path of a



[Moy]                                                          [Page 35]

Internet Draft        Multicast Extensions to OSPF        September 1992


        multicast datagram can vary  depending  on  the  datagram's  TOS
        classification, as well as its source and destination.

        For each router interface, OSPF allows a separate metric  to  be
        configured for each IP TOS. When building the shortest path tree
        for TOS X, the cost of a path is the sum of the component inter-
        faces'  TOS  X  metrics.  Note  that  OSPF requires that a TOS 0
        metric be specified for each interface. However, as  a  form  of
        data  compression,  metrics  need only be specified for non-zero
        TOS if they are different than the TOS 0 metric.

        Additionally, OSPF routers can be configured to ignore TOS  when
        forwarding  packets.  Such  routers, called TOS-incapable, build
        only the TOS 0  portion  of  the  routing  table.  TOS-incapable
        routers  can  be mixed freely with TOS-capable routers when for-
        warding unicast packets. The way this  is  handled  for  unicast
        packets  is  that the unicast is forwarded along the TOS 0 route
        whenever the TOS X route does not  exist.  However,  MOSPF  must
        treat  this  situation  somewhat  differently, since each router
        must build the exact same tree rooted at the datagram's source.

        Like OSPF, MOSPF allows TOS-based routing to be  optional.  TOS-
        capable  and TOS-incapable multicast routers can be mixed freely
        in the routing domain.  TOS-incapable  routers  will  only  ever
        build  TOS  0  datagram shortest-path trees. TOS-capable routers
        will first build TOS 0 datagram shortest-path  trees.  If  these
        trees  contain  only TOS-capable routers, datagram shortest-path
        trees are then built separately for non-zero TOS values.  Other-
        wise,  the  TOS 0 datagram shortest-path tree is used to forward
        all traffic, regardless of  its  TOS  designation.   Using  this
        logic,  all  routers  in  essence  continue to utilize identical
        datagram  shortest-path  trees.  See  Section  12.2.8  for  more
        details.

    6.3.  Assigning multiple IP networks to a physical network

        Assigning multiple IP networks/subnets to a single physical net-
        work  causes some confusion in MOSPF. This is because the under-
        lying OSPF protocol treats these IP networks/subnets as entirely
        separate  entities,  originating  separate network-LSAs for each
        and forming separate adjacencies for each, while IGMP recognizes
        only the single underlying physical network. Adding to the prob-
        lem is the fact that when a multicast datagram is received  from
        such a multiply-addressed physical wire, there is no good way to
        choose the datagram's upstream node (which must be done in order
        to make the forwarding decision; see Section 11 for details). As
        a result, unless this situation is dealt with through configura-
        tion, unwanted replication of multicast datagrams may occur when



[Moy]                                                          [Page 36]

Internet Draft        Multicast Extensions to OSPF        September 1992


        they are forwarded over multiply-addressed wires.

        As a remedy, MOSPF allows multicast forwarding to be disabled on
        certain  IP  networks/subnets. When multicast forwarding is dis-
        abled on the wire's "extra" subnets (i.e.,  all  but  one),  the
        extra  subnets  will not appear in datagram shortest-path trees,
        nor will they appear in local group database or forwarding cache
        entries.  As  a  result,  the  possibility  of unwanted datagram
        replication is eliminated. The  actual  disabling  of  multicast
        forwarding  on a subnet is done through setting the IPMulticast-
        Forwarding parameter to disabled on all router  interfaces  con-
        necting to the subnet (see Section B.2).

    6.4.  Networks on Autonomous System boundaries

        Another complication can arise on IP networks/subnets  that  lie
        on  the  boundary  of  a MOSPF Autonomous System. Similar to the
        unicast situation where these networks may be  running  multiple
        IGPs  (Interior  Gateway  Protocols), these networks may also be
        running multiple multicast routing protocols. It may then become
        impossible  for  a MOSPF router to determine whether a multicast
        datagram is being forwarded  along  the  datagram  shortest-path
        tree,  or  whether  it  has been inadvertently received from the
        other Autonomous System.  Guessing  wrong  can  lead  to  either
        unwanted  replication or non-delivery of the multicast datagram.
        In addition, in order to prevent receiving  duplicate  multicast
        datagrams,  group  members on these boundary networks will prob-
        ably want to declare their membership to one  Autonomous  System
        and not another.

        For example, consider the two  Autonomous  Systems  pictured  in
        Figure 13. Network X is on the boundary of both ASes. One possi-
        ble multicast datagram path is shown; the datagram originates in
        a  third  Autonomous System, and is then delivered to both AS #1
        and AS #2 separately. The paths through the two Autonomous  Sys-
        tems  may end up having certain boundary networks as common seg-
        ments. In Figure 13, Network X is common to both paths. In  this
        case,  if  both Autonomous Systems were running (separate copies
        of) MOSPF, the same datagram would appear twice on Network X  as
        a  data-link  multicast. This would cause duplicate datagrams to
        be received by any group members on Network X or downstream from
        Network X.

        MOSPF has two mechanisms to eliminate this replication of multi-
        cast datagrams. First, a system administrator can configure cer-
        tain networks to forward multicast datagrams as  data-link  uni-
        casts  instead  of data-link multicasts. This is done by setting
        the IPMulticastForwarding  parameter  to  data-link  unicast  on



[Moy]                                                          [Page 37]

Internet Draft        Multicast Extensions to OSPF        September 1992



                              <-Datagram path->*
                             *                 *
                             *                 *
                             *            .....*.........
                    .........*.....   |   .    *    AS #2
                    AS #1    *    .   |*****+---+
                            +---+*****|*----|RTC|
                            |RTA|----*|*  . +---+
                            +---+ .  *|*  .
                                  .  *|*  .
                                  .  *|*  . +---+
                            +---+ .  *|*----|RTD|
                            |RTB|----*|*****+---+
                            +---+*****|   .....*..........
                    .........*....    |        *
                             *        |        *
                             *    Network X    *
                             *

                     Figure 13: Networks on AS boundaries

        those router interfaces attaching to the  network  (see  Section
        B.2).  As an example, in Figure 13 the routers in AS #2 could be
        configured so that Router C would send  the  multicast  datagram
        out  onto Network X as a data-link unicast addressed directly to
        Router D. Router D would  accept  this  data-link  unicast,  but
        would reject any data-link multicast forwarded by Router A. This
        would eliminate replication of  multicast  datagrams  downstream
        from Network X. In addition, if the IPMulticastForwarding param-
        eter is set to data-link unicast on Network X, group  membership
        will  not  be  monitored on the network. This will prevent group
        members attached directly to Network X from  receiving  multiple
        datagram  copies, since group membership on the boundary network
        will be monitored from only one AS.

        It should be noted that forwarding IP  multicasts  as  data-link
        unicasts has some disadvantages when three or more MOSPF routers
        are attached to the network. First of all, it is more work for a
        router  to  send  multiple  unicasts  than  a  single multicast.
        Second, the multiple unicasts  consume  more  network  bandwidth
        than  a  single  multicast. And last, it increases the delay for
        some group members since multiple unicasts also take  longer  to
        send than a single multicast.







[Moy]                                                          [Page 38]

Internet Draft        Multicast Extensions to OSPF        September 1992


    6.5.   Recommended system configuration

        In order make MOSPF's selection of routes more  predictable,  it
        is recommended that all routers in any particular OSPF area have
        the same multicast and TOS capabilities.Keeping areas  homogene-
        ous ensures that IP multicast packets will follow relatively the
        same path as IP unicasts. In contrast, while heterogeneous areas
        will  function,  and  will probably be necessary at least during
        the initial introduction of multicast routing,  such  areas  may
        produce  seemingly  sub-optimal and unexpected routes. For exam-
        ple, see Section 6.1above for a detailed description of the pos-
        sible pitfalls when mixing multicast and non-multicast routers.

        As for the other options presented above, to  achieve  the  most
        predictable  results it is recommended that a router interface's
        IPMulticastForwarding parameter be set to  a  value  other  than
        data-link  multicast  only  when  either a) multiple IP networks
        have been assigned to a single physical wire or b) multiple mul-
        ticast routing protocols are running on the attached network.
































[Moy]                                                          [Page 39]

Internet Draft        Multicast Extensions to OSPF        September 1992


7.   Basic implementation requirements

    An implementation of MOSPF requires the following pieces  of  system
    support.  Note that this support is in addition to that required for
    the base OSPF implementation as outlined in Section 4.4 of [OSPF].

    o   Promiscuous multicast reception. In a multicast  router,  it  is
        necessary  to  receive all IP multicasts at the data-link level.
        On those interfaces where IP multicast  datagrams  are  encapsu-
        lated  by  a  wide  range  of  data-link  multicast  destination
        addresses (e.g, ethernet and FDDI), this is most  easily  accom-
        plished  by disabling any hardware filtering of multicast desti-
        nations  (i.e.,  by  "opening  up"  the  interface's   multicast
        filter).

    o   Data-link  multicast/broadcast  detection.  To  avoid   unwanted
        replication of multicast datagrams in certain exceptional condi-
        tions, it is necessary for the  MOSPF  forwarding  mechanism  to
        determine  whether  a  datagram  was  received  as  a  data-link
        multicast/broadcast or as a data-link unicast. See  Section  6.4
        for more details.

    o   An implementation of IGMP. MOSPF uses the Internet Group Manage-
        ment Protocol (IGMP, documented in [RFC 1112]) to monitor multi-
        cast group membership. See Section 9 for details.

8.  Protocol data structures

    The MOSPF protocol is described herein in terms of its operation  on
    various protocol data structures. These data structures are included
    for explanatory uses only, and are not intended to constrain a MOSPF
    implementation.  Besides  the  data  structures  listed  below, this
    specification will also reference the various data structures (e.g.,
    OSPF interfaces and neighbors) defined in [OSPF].

    In a MOSPF router, the following items are added to the list of glo-
    bal OSPF data structures described in Section 5 of [OSPF]:

    o   Local group database. This database describes the group  member-
        ship  on  all  attached  networks for which the router is either
        Designated Router or Backup  Designated  Router.  This  in  turn
        determines  the  group-membership-LSAs that the router will ori-
        ginate, and the local delivery of multicast datagrams (see  Sec-
        tions 2.3.1 and 10).

    o   Forwarding cache. Each entry in the forwarding  cache  describes
        the  path  of  a  multicast datagram having a particular [source
        net,  multicast  destination,  TOS]  combination.  These   cache



[Moy]                                                          [Page 40]

Internet Draft        Multicast Extensions to OSPF        September 1992


        entries  are calculated when building the datagram shortest-path
        trees. See Sections 2.3.4 and 11 for more details.

    o   Multicast routing capability. Indicates whether  the  router  is
        running  the multicast extensions defined in this memo. A router
        running the multicast extensions must still run  the  base  OSPF
        algorithm as set forth in [OSPF]. Such a router will continue to
        interoperate with non-multicast-capable OSPF routers  when  for-
        warding IP unicast traffic.

    o   Inter-area multicast forwarder.  Indicates  whether  the  router
        will forward IP multicasts from one OSPF area to another. Such a
        router declares itself a wild-card  multicast  receiver  in  its
        router-LSA  (see Section 14.6), and also summarizes its attached
        areas' group membership to  the  backbone  in  group-membership-
        LSAs.  When building inter-area datagram shortest-path trees, it
        is  these  routers  that  appear  immediately  adjacent  to  the
        datagram  source  at the root of the tree (see Section 3.2). Not
        all multicast-capable area border routers need be configured  as
        inter-area  multicast forwarders. However, whenever both ends of
        a virtual link are multicast-capable, they must both be  config-
        ured as inter-area multicast forwarders (see Section 14.11).

    o   Inter-AS multicast forwarder. Indicates whether the router  will
        forward  IP multicasts between Autonomous Systems. Such a router
        declares itself a wild-card multicast receiver in its router-LSA
        (see Section 14.6). These routers are also assumed to be running
        some kind of inter-AS multicast protocol. They mark all external
        routes  that they import into the OSPF domain as to whether they
        provide multicast connectivity (see Section 14.9). When building
        inter-AS  multicast  datagram  trees,  it  is these routers that
        appear immediately adjacent to the datagram source at  the  root
        of the tree.

    8.1.  Additions to the OSPF area structure

        The OSPF area data  structure  is  described  in  Section  6  of
        [OSPF].  In  a  MOSPF router, the following item is added to the
        OSPF area structure:

        o   List of group-membership-LSAs. These link  state  advertise-
            ments  describe  the  location of the area's multicast group
            members.  Group-membership-LSAs  are  flooded  throughout  a
            single  area  only. Area border routers also summarize their
            attached areas' membership by originating  group-membership-
            LSAs  into the backbone area. For more information, see Sec-
            tions 3.1 and 10.




[Moy]                                                          [Page 41]

Internet Draft        Multicast Extensions to OSPF        September 1992


    8.2.  Additions to the OSPF interface structure

        The OSPF interface  structure  is  described  in  Section  9  of
        [OSPF].  In a MOSPF router, the following items are added to the
        OSPF interface structure. Note  that  the  IPMulticastForwarding
        parameter  is  really  a description of the attached network. As
        such,  it  should  be  configured  identically  on  all  routers
        attached  to  a  common  network; otherwise incorrect routing of
        multicast datagrams may result[14].

        o   IPMulticastForwarding. This configurable parameter indicates
            whether  IP multicasts should be forwarded over the attached
            network, and if so, how the forwarding should be  done.  The
            parameter can assume one of three possible values: disabled,
            data-link multicast and data-link unicast. When set to  dis-
            abled,  IP multicast datagrams will not be forwarded out the
            interface. When set to  data-link  multicast,  IP  multicast
            datagrams  will  be  forwarded as data-link multicasts. When
            set to data-link unicast, IP  multicast  datagrams  will  be
            forwarded  as data-link unicasts. The default value for this
            parameter is data-link multicast. The other two settings are
            for  use  in the special circumstances described in Sections
            6.3 and 6.4. When set to disabled or to  data-link  unicast,
            IGMP  group membership is not monitored on the attached net-
            work.

        o   IGMPPollingInterval. When the router is actively  monitoring
            group  membership  on  the attached network, it periodically
            sends IGMP Host Membership Queries. IGMPPollingInterval is a
            configurable  parameter  indicating  the  number  of seconds
            between IGMP Host Membership Queries.  The  router  actively
            monitors  group membership on the attached network when both
            a) the interface's IPMulticastForwarding parameter is set to
            data-link  multicast  and  b)  the  router  has been elected
            Designated Router on the attached network. See Section 9 for
            details.

        o   IGMPTimeout.  This  configurable  parameter  indicates   the
            length  of  time  (in  seconds)  that a local group database
            entry associated with this interface  will  persist  without
            another matching IGMP Host Membership Report being received.
            See Section 9 for details.

        o   IGMP polling timer. The firing of this interval timer causes
            an  IGMP Host Membership Query to be sent out the interface.
            The length of this timer is the configurable parameter IGMP-
            PollingInterval. See Section 9 for details.




[Moy]                                                          [Page 42]

Internet Draft        Multicast Extensions to OSPF        September 1992


    8.3.  Additions to the OSPF neighbor structure

        The OSPF neighbor structure is defined in Section 10 of  [OSPF].
        In  a  MOSPF  router,  the following items are added to the OSPF
        neighbor structure:

        o   Neighbor options. This field was already defined in the OSPF
            specification. However, in MOSPF there is a new option which
            indicates the  neighbor's  multicast  capability.  This  new
            option  is  learned in the Database Exchange process through
            reception of the neighbor's  Database  Description  packets,
            and  determines whether group-membership-LSAs are flooded to
            the neighbor. See the items concerning flooding  in  Section
            14 for a more detailed explanation.

    8.4.  The local group database

        The local group database has already been introduced in  Section
        2.3.1.   The current section attempts a more precise definition.
        The local group database tracks  the  group  membership  of  the
        router's   directly  attached  networks.  Database  entries  are
        created and maintained by the IGMP  protocol.  Database  entries
        can  cause group-membership-LSAs to be originated, which in turn
        enable the pruning of datagram shortest-path  trees.  The  local
        group database also dictates the router's responsibility for the
        delivery of  multicast  datagrams  to  directly  attached  group
        members.

        Each entry in the local group database has three components: the
        multicast  group,  the attached network and entry's age. A data-
        base entry is indexed by the  first  two  components:  multicast
        group  and  attached  network.  A  database  lookup  function is
        assumed to exist, so that given  a  [multicast  group,  attached
        network]  pair,  the  matching  database  entry  (if any) can be
        discovered. A database entry for [Group A, network N1] exists if
        and  only if there are Group A members currently located on net-
        work N1.

        The three components of a local group database entry are defined
        as follows:

        o   MulticastGroup. The multicast group whose members are  being
            tracked  by  this entry. Each multicast group is represented
            as a class D IP address.  For  the  semantics  of  multicast
            group membership, see [RFC 1112].

        o   AttachedNetwork. Each database entry is concerned  with  the
            group members belonging to a single attached network. To get



[Moy]                                                          [Page 43]

Internet Draft        Multicast Extensions to OSPF        September 1992


            a complete picture of the local group membership  (when  for
            example  building  a group-membership-LSA), it may be neces-
            sary to consult multiple  database  entries,  one  for  each
            attached  network.  Note  that  a router is only required to
            maintain entries for those attached networks  on  which  the
            router  has  been elected Designated Router or Backup Desig-
            nated Router (see Section 9).

        o   Age. Indicates the number of  seconds  since  an  IGMP  Host
            Membership  Report  for  multicast  Group A has been seen on
            network N1. If the age field hits  network  N1's  configured
            IGMPTimeout value, the local group database entry is removed
            (i.e., the entry has "aged out"). See Sections 9.2  and  9.3
            for more information.

    8.5.  The forwarding cache

        The forwarding cache has already been defined  in  Section  2.3.
        The  current  section  attempts  a more precise definition. Each
        entry in the forwarding cache indicates how a multicast datagram
        having  a  particular  [source  network,  destination  multicast
        group, IP TOS] will be forwarded. A forwarding  cache  entry  is
        built on demand from the local group database and the datagram's
        shortest-path tree. For more details, consult Sections 2.3.4 and
        12.

        Each entry in the forwarding cache has six components: the  mul-
        ticast  datagram's  source  network,  the  destination multicast
        group, the IP TOS, the upstream node,  the  list  of  downstream
        interfaces and (possibly) a list of downstream neighbors. A for-
        warding cache entry is indexed by  source  network,  destination
        multicast  group  and  IP  TOS.  A lookup function is assumed to
        exist, so that given a multicast datagram with a particular  [IP
        source,  destination  multicast group, IP TOS], a matching cache
        entry (if any) can be found.

        The six components of a forwarding cache entry  are  defined  as
        follows:

        o   Source network. The datagram's source network  is  described
            by  a  network/subnet/supernet  number and its corresponding
            mask. The source network for a datagram is discovered via  a
            routing  table/database  lookup  of the datagram's IP source
            address, as described in Section 11.2.

        o   Destination multicast group. The destination group to  which
            matching datagrams are being forwarded. For the semantics of
            multicast group membership, see [RFC 1112].



[Moy]                                                          [Page 44]

Internet Draft        Multicast Extensions to OSPF        September 1992


        o   IP TOS.  The  IP  Type  of  service  specified  by  matching
            datagrams.  Note that this means that the path of the multi-
            cast datagrams depends on their TOS classification.

        o   Upstream node. The attached network/neighboring router  from
            which the datagram must be received. If received from a dif-
            ferent attached  network/neighboring  router,  the  matching
            datagram  is  dropped  instead  of  forwarded. This prevents
            unwanted replication of multicast datagrams. It is  possible
            that  the  upstream node is unspecified (i.e., set to NULL).
            In this case, matching datagrams will always be dropped,  no
            matter  where  they  are  received from. It is also possible
            that the upstream  node  is  specified  as  the  placeholder
            EXTERNAL. This means that the datagram must be received on a
            non-MOSPF interface in order to be forwarded.

        o   List of downstream interfaces. These are the  router  inter-
            faces  that the matching datagram should be forwarded out of
            (assuming that  the  datagram  was  received  from  upstream
            node).  Each  interface is also listed with a TTL value. The
            TTL value is the minimum number of hops necessary  to  reach
            the  closest  (in  terms of router hops) group member.  This
            allows the router to drop datagrams that have no  chance  of
            reaching a destination group member.

        o   List of downstream neighbors. When the  datagram  is  to  be
            forwarded  out  a  non-broadcast multi-access network, or if
            the interface's IPMulticastForwarding parameter  is  set  to
            data-link unicast, the datagram must be forwarded separately
            to each downstream neighbor (see Sections 2.3.3 and 6.4). As
            done  for downstream interfaces, each downstream neighbor is
            specified together with the smallest TTL that will  actually
            reach a group member.

9.  Interaction with the IGMP protocol

    MOSPF uses the IGMP protocol (see [RFC 1112]) to  monitor  multicast
    group  membership.  In  short,  the  Designated  Router on a network
    periodically sends IGMP Host Membership Queries (see  Section  9.1),
    which in turn elicit IGMP Host Membership Reports from the network's
    multicast group members. These  Host  Membership  Reports  are  then
    recorded  in  the Designated Router's and Backup Designated Router's
    local group databases (see Section 9.2).

    9.1.  Sending IGMP Host Membership Queries

        Only the  network's  Designated  Router  sends  Host  Membership
        Queries.    This   minimizes  the  amount  of  group  membership



[Moy]                                                          [Page 45]

Internet Draft        Multicast Extensions to OSPF        September 1992


        information on  the  network,  both  in  terms  of  queries  and
        responses.

        When a MOSPF router becomes Designated Router on a  network,  it
        checks to see that the network's IPMulticastForwarding parameter
        is set to data-link multicast  (see  Section  B.2).  If  so,  it
        starts  the  interface's  IGMP polling timer. Then, whenever the
        timer  fires  (every  IGMPPollingInterval  seconds),  the  MOSPF
        router sends a Host Membership Query out the interface. The des-
        tination of the query is the IP address 224.0.0.1. For the  for-
        mat  of  the  query,  see  [RFC 1112].  If/when the MOSPF router
        ceases to be the network's Designated Router, the  IGMP  polling
        timer is disabled and no more Hosts Membership Queries are sent.

        Unusual behavior  can  result  when  multiple  IP  networks  are
        assigned to a single physical network. MOSPF treats each IP net-
        work separately,  electing  (possibly)  a  different  Designated
        Router  for  each network.  However, IGMP operates on a physical
        network basis only: when a Host Membership Query  is  sent,  all
        group  members  on  the  physical network respond, regardless of
        their IP addresses. So unless the IPMulticastForwarding  parame-
        ter  is set to a value other than data-link multicast on all but
        one of the physical  network's  IP  networks,  excess  multicast
        membership reporting will result.

    9.2.  Receiving IGMP Host Membership Reports

        Received Host Membership  Reports  are  processed  by  both  the
        network's  Designated Router and Backup Designated Router. It is
        the  Designated  Router's  responsibility  to   distribute   the
        network's  group  membership  information throughout the routing
        domain, by originating group-membership-LSAs (see  Section  10).
        The  Backup  Designated  Router processes Reports so that it too
        has a complete picture of the network's group  membership,  ena-
        bling a quick cutover upon Designated Router failure.

        An IGMP Host Membership Report concerns membership in  a  single
        IP multicast group (call it Group A). The Report is also sent to
        the Group A address (see [RFC 1112] for details). When  an  IGMP
        Host  Membership Report, sent on network N[15], is received by a
        MOSPF router, the following steps are executed:

        (1) If the router is  neither  the  Designated  Router  nor  the
            Backup  Designated Router on the network, the Report is dis-
            carded and processing stops.

        (2) If the Report  concerns  a  multicast  group  in  the  range
            224.0.0.1   -  224.0.0.255,  the  Report  is  discarded  and



[Moy]                                                          [Page 46]

Internet Draft        Multicast Extensions to OSPF        September 1992


            processing stops. This range of  multicast  groups  are  for
            local  use  (single  hop)  only, and datagrams sent to these
            destinations are never forwarded by multicast routers.

        (3) Locate the entry for [Group A, Network N] in the local group
            database.  If no such entry exists, create one. In any case,
            set the age of the entry to 0. Note that  even  if  multiple
            hosts  attached  to  network N report membership in the same
            group, only a single local  group  database  entry  will  be
            formed.  See  Section  8.4  for  more details concerning the
            local group database.

        (4) If the router is the  network's  Designated  Router,  and  a
            local group database entry was created in the previous step,
            it may be necessary to originate a new group-membership-LSA.
            See Section 10 for details.

    9.3.  Aging local group database entries

        Every local database entry has an age field. Suppose that  there
        is  a  database  entry  for [Group A, Network N1]. The age field
        then indicates the length of time (in seconds)  since  the  last
        Host  Membership  Report for Group A was received on Network N1.
        If the age of the entry reaches Network  N1's  configured  IGMP-
        Timeout value (see Section B.2), the entry is considered invalid
        and is removed from the database.

        Note that when a router, after having been either  Network  N1's
        Designated  Router  or  Backup  Designated Router, but now being
        neither, will (after IGMPTimeout seconds) automatically age  out
        all  of its local group database entries associated with Network
        N1. For this reason, it is not necessary to  purge  local  group
        database entries on OSPF interface state changes.

    9.4.  Receiving IGMP Host Membership Queries

        If a MOSPF router has internal multicast  applications,  and  if
        the  applications  have  bound  themselves to certain interfaces
        (using the RFC 1112 representation described in Section 5), then
        the MOSPF router responds to received Host Membership Queries by
        issuing Host Membership Reports. Identical to the  operation  of
        any  IP  host  supporting multicast applications, the exact pro-
        cedure for issuing these Host Membership Reports is specified in
        [RFC  1112].  Note  that  in  this  case, if the router has been
        elected Designated Router on a network, its must receive its own
        Host Membership Reports and Host Membership Queries.





[Moy]                                                          [Page 47]

Internet Draft        Multicast Extensions to OSPF        September 1992


        If instead all of its applications  have  joined  groups  in  an
        interface-independent    fashion   (using   the   MOSPF-specific
        representation described in Section 5), the  MOSPF  router  does
        not  respond  to  Host  Membership  Queries.  Instead, the MOSPF
        router communicates this membership information  by  originating
        appropriate group-membership-LSAs (see Section 10.1).

10.  Group-membership-LSAs

    Group-membership-LSAs provide the means of  distributing  membership
    information  throughout  the MOSPF routing domain. Group-membership-
    LSAs are specific to a single OSPF  area  (see  Section  3.1).  Each
    group-membership-LSA concerns a single multicast group. Essentially,
    the group-membership-LSA lists those  networks  which  are  directly
    connected  to  the  LSA's  originator  and which contain one or more
    group members. For more details on how the group-membership-LSA aug-
    ments the OSPF link state database, see Section 2.3.1.

    The creation of group-membership-LSAs is discussed in Section  10.1.
    The  format of the group-membership-LSA is described in Section A.3.
    A router will originate a group membership-LSA for multicast Group A
    when one or more of the following conditions hold:

    (1) The router is Designated Router on a network  (call  it  Network
        X),  the  interface  to  Network X has its IPMulticastForwarding
        parameter set to data-link multicast (see Section B.2), and net-
        work X contains one or more members of Group A.

    (2) The router is an inter-area  multicast  forwarder  (see  Section
        B.1),  and  one  or  more  of the router's attached non-backbone
        areas contain Group A members. In this  case,  the  router  will
        originate  a group-membership-LSA for Group A into the backbone.
        This is the way group membership is conveyed between areas  (see
        Section 3.1).

    (3) The router itself has applications that are  requesting  member-
        ship  in  Group A, in an interface-independent fashion (see Sec-
        tion 5).

    As for all other types  of  OSPF  link  state  advertisements  (e.g,
    router-LSAs,  network-LSAs, etc.), group-membership-LSAs are aged as
    they are held in a router's link state database.  To  prevent  valid
    advertisements  from  "aging  out",  a router must refresh its self-
    originated group-membership-LSAs every  LSRefreshTime  interval,  by
    incrementing  their LS sequence numbers and reissuing them. In addi-
    tion, when an event occurs that would  alter  one  of  the  router's
    self-originated  group-membership-LSAs, a new instance of the LSA is
    issued with an updated (i.e., incremented by 1) LS sequence  number.



[Moy]                                                          [Page 48]

Internet Draft        Multicast Extensions to OSPF        September 1992


    Note  however  that  a  router  is  not allowed to originate two new
    instances of the same advertisement  within  MinLSInterval  seconds.
    For  that  reason, occasionally advertisement originations will need
    to be deferred. Also, an event may occur that makes in inappropriate
    for  the  router  to continue to originate a particular LSA. In that
    case, the router flushes the advertisement from the  routing  domain
    by  "premature  aging".  For more information concerning the mainte-
    nance of LSAs, see Sections 12, 12.4, 14 and 14.1 of [OSPF].

    When one of the following events occurs, it may be necessary  for  a
    router to (re)issue one or more group-membership-LSAs:

    (1) One of the router's interfaces changes state. For  example,  the
        router  may  have  become Designated Router on a particular net-
        work, causing the router  to  start  advertising  the  network's
        group  membership  to  the  rest  of  the MOSPF system in group-
        membership-LSAs.

    (2) The router receives an IGMP Host Membership  Report,  causing  a
        new local group database entry to be formed (see Section 9.2).

    (3) One of the router's local group  database  entries  "ages  out",
        because  it  is  no longer being refreshed by received IGMP Host
        Membership Reports (see Section 9.3).

    (4) The router is an inter-area multicast forwarder, and  the  group
        membership  of  one  of the router's attached non-backbone areas
        changes.  This is detected by the reception of  a  new,  or  the
        flushing  of  an  old,  group-membership-LSA  into/from the non-
        backbone area's link state database.

    (5) The group membership of one of the  router's  internal  applica-
        tions changes.

    10.1.  Constructing group-membership-LSAs

        This section details how to build  a  group-membership-LSA.  The
        format  of  a  group-membership-LSA is described in Section A.3.
        Each group-membership-LSA concerns a single multicast group. The
        body  of  the advertisement is a list of the local transit nodes
        (the router itself and directly attached transit networks)  that
        contain  group members. Section 10 listed the conditions requir-
        ing the (re)origination of a group-membership-LSA. Note that  if
        the router is an area border router, it may be necessary to ori-
        ginate a separate group-membership-LSA for each attached area.

        The following defines the contents of a group-membership-LSA, as
        originated  by  Router  X  into  Area  A. It is assumed that the



[Moy]                                                          [Page 49]

Internet Draft        Multicast Extensions to OSPF        September 1992


        group-membership-LSA is to report membership in multicast  Group
        G:

        o   The advertisement fields that are not type-specific (LS age,
            LS  sequence number, LS checksum and length) are set accord-
            ing to Section 12.1 of [OSPF].

        o   The Options field of a group-membership-LSA is not processed
            on  receipt.  However,  for consistency, the Option field in
            these advertisements  should  have  its  MC-bit  set,  T-bit
            clear,  and the E-bit should match the configuration of Area
            A (i.e., set if and only if Area A is not a stub area).  The
            rest of the Options field is set to 0.

        o   The Link State ID is set to the group  whose  membership  is
            being reported (Group G).

        o   The Advertising Router is set to the OSPF Router ID  of  the
            router originating the advertisement (Router X).

        o   The body of the advertisement is a  list  of  local  transit
            vertices  that  should  be  labelled with Group G membership
            (see Section 2.3.1). This list may include  the  advertising
            router  itself,  and  any  of  the transit networks that are
            directly attached to said router. The following steps deter-
            mine  which  of these transit vertices are actually included
            in the group-membership-LSA. Note that any particular vertex
            should be listed at most once, even though the following may
            indicate multiple reasons for  a  particular  vertex  to  be
            listed.  Also note that if no transit vertices are listed by
            the  advertisement,  the   advertisement   should   not   be
            (re)originated;  if an instance of the advertisement already
            exists, it should then be flushed from the link state  data-
            base.

            a.  Consider those entries in the local group database  that
                describe  Group G membership (see Section 8.4). Consider
                each such entry in turn. Each entry  references  one  of
                Router  X's  attached  networks  (call it Network N). If
                either Network N does not belong to Area A, or if Router
                X  is  not  Network N's Designated Router[16], Network N
                should be added to  the  group-membership-LSA,  and  the
                next local group database entry should be examined. Oth-
                erwise, if N is a stub network (e.g., Router  X  is  the
                only OSPF router attached to N), Router X adds itself to
                the advertisement by adding a vertex  with  Vertex  type
                set  to  1 (router) and Vertex ID set to Router X's OSPF
                Router ID. Otherwise, N is a transit  network.  In  this



[Moy]                                                          [Page 50]

Internet Draft        Multicast Extensions to OSPF        September 1992


                case,  Network N should be added to the advertisement by
                adding a vertex with Vertex type set to 2 (network)  and
                Vertex  ID  set  to the IP address of Network N's Desig-
                nated Router (i.e., Router X's IP interface  address  on
                Network N).

            b.  If Router X itself has applications requesting  Group  G
                membership  on  an interface-independent basis (see Sec-
                tion 5), it should add itself to  the  advertisement  by
                adding  a  vertex with Vertex type set to 1 (router) and
                Vertex ID set to Router X's OSPF Router ID.

            c.  If Router X is an inter-area  multicast  forwarder  (see
                Section  3.1),  Area  A  is  the  backbone area (Area ID
                0.0.0.0), and at least one of the attached  non-backbone
                areas  has Group G members (indicated by the presence of
                one or more advertisements in their link state databases
                having  Link State ID set to Group G[17]), then Router X
                should add itself to the advertisement by adding a  ver-
                tex with Vertex type set to 1 (router) and Vertex ID set
                to Router X's OSPF Router ID.

    10.2.  Flooding group-membership-LSAs

        When MOSPF routers and  non-multicast  OSPF  routers  are  mixed
        together  in a routing domain, the group-membership-LSAs are not
        flooded to the non-multicast routers[18].  As a  general  design
        principle,  optional  OSPF  advertisements  are  only flooded to
        those routers that understand them.

        A MOSPF router learns of its neighbor's multicast-capability  at
        the  beginning  of  the "Database Exchange Process" (see Section
        10.6 of [OSPF], receiving Database Description  packets  from  a
        neighbor  in  state Exstart). A neighbor is multicast-capable if
        and only if it sets the MC-bit in the Options field of its Data-
        base  Description  packets.  Then, in the next step of the Data-
        base Exchange process, group-membership-LSAs are included in the
        Database summary list sent to the neighbor (see Sections 7.2 and
        10.3 of [OSPF]) if  and  only  if  the  neighbor  is  multicast-
        capable.

        When flooding group-membership-LSAs  to  adjacent  neighbors,  a
        MOSPF  router looks at the neighbor's multicast-capability. Such
        advertisements are only flooded to multicast-capable  neighbors.
        To   be   more  precise,  in  Section  13.3  of  [OSPF],  group-
        membership-LSAs are only placed on the Link state retransmission
        lists  of  multicast-capable  neighbors[19].   Note however that
        when flooding Link State Update packets as  multicasts,  a  non-



[Moy]                                                          [Page 51]

Internet Draft        Multicast Extensions to OSPF        September 1992


        multicast    neighbor   may   (inadvertently)   receive   group-
        membership-LSAs. The non-multicast router will then simply  dis-
        card  the  LSA  (see Section 13 of [OSPF], receiving LSAs having
        unknown LS types).

11.  Detailed description of multicast datagram forwarding

    This section describes in detail the way MOSPF forwards a  multicast
    datagram.   The  forwarding  process  has  already  been  informally
    presented in Section 2.2. However, there are several obscure  confi-
    guration  options (e.g., the IPMulticastForwarding interface parame-
    ter) that have been presented elsewhere in this document, which  may
    influence  the forwarding process. This section gathers together all
    the influencing factors into a single algorithm.

    It is assumed in the following that the datagram under consideration
    has  actually be received on one of the router's interfaces. Locally
    generated datagrams (i.e., originated by one of the router's  inter-
    nal  applications)  are  handled instead by the algorithm in Section
    11.3.

    The forwarding process consists of the following steps:

    (1) Upon reception of the datagram, the MOSPF router notes the  fol-
        lowing parameters. These parameters are examined in later steps,
        to determine whether the datagram should be forwarded.

        a.  The receiving MOSPF interface associated with the  datagram.
            Based  on  the  receiving  physical interface, the receiving
            MOSPF interface is selected  by  the  algorithm  in  Section
            11.1.

        b.  Whether  the  datagram  was   received   as   a   link-level
            multicast/broadcast  or as a link-level unicast. This infor-
            mation is used later in Step 7 to help determine whether the
            datagram should be forwarded.

    (2) A copy of the datagram should be passed to each internal  appli-
        cation  that  has  joined the destination multicast group on the
        receiving MOSPF interface (see Section 5).

    (3) If the datagram's IP source address matches the receiving  MOSPF
        interface's  IP  address,  the  datagram should not be forwarded
        further, and should instead be discarded,  completing  the  for-
        warding process.  This keeps the router's own locally originated
        datagrams from being mistakenly replicated, in those cases where
        the   receiving  MOSPF  interface  receives  its  own  multicast
        transmissions.



[Moy]                                                          [Page 52]

Internet Draft        Multicast Extensions to OSPF        September 1992


    (4) If the datagram's IP multicast destination falls  in  the  range
        224.0.0.1 through 224.0.0.255 inclusive, the datagram should not
        be forwarded further. This range of addresses has been dedicated
        to local use only.

    (5) Associate a source  network  with  the  multicast  datagram,  as
        described  in  Section  11.2.  If  the  source network cannot be
        determined (i.e., there is no available unicast  route  back  to
        the  datagram  source),  the  datagram  should  not be forwarded
        further.

    (6) Look up the forwarding cache entry (see  Section  8.5)  matching
        the  datagram's  [source network, IP multicast destination, TOS]
        combination. If the cache entry does not yet exist, one is built
        by  the  calculation in Section 12. In order for the datagram to
        be forwarded, the contents of the forwarding cache entry must be
        further verified against the received datagram's characteristics
        as follows:

        a.  If the forwarding cache entry's upstream node is unspecified
            (i.e.,  NULL),  then  the  datagram  should not be forwarded
            further.

        b.  Otherwise,  suppose  that  the  forwarding   cache   entry's
            upstream node is set to EXTERNAL. In this case, the datagram
            is forwarded further if and  only  if  the  receiving  MOSPF
            interface  is set to NULL (i.e., if and only if the datagram
            was received on a non-MOSPF interface).

        c.  Otherwise, if the datagram's receiving MOSPF interface  does
            not  attach  to  the forwarding cache entry's upstream node,
            the datagram should not be forwarded further.

    (7) If the receiving MOSPF interface's IPMulticastForwarding parame-
        ter  is  set  to  data-link unicast, the datagram should be for-
        warded further only if it was received as a data-link unicast.

    (8) At this point the datagram is eligible for  further  forwarding.
        Before  forwarding,  the router checks to see whether it has any
        internal applications that have joined the destination multicast
        group  on  an  interface-independent basis. If so, a copy of the
        datagram should be passed to each  such  requesting  application
        process.

    (9) Examine each of the downstream interfaces listed in the forward-
        ing  cache  entry. If the TTL in the datagram is greater than or
        equal to the TTL specified for the downstream interface, a  copy
        of   the   datagram  should  be  forwarded  out  the  downstream



[Moy]                                                          [Page 53]

Internet Draft        Multicast Extensions to OSPF        September 1992


        interface. Before forwarding the datagram copy, the  copy's  TTL
        should  be decremented by 1. On most interfaces, the datagram is
        forwarded as a data-link multicast/broadcast.  The  exact  data-
        link encapsulation is dependent on the attached network's type:

        o   On ethernet and IEEE 802.3 networks, the  datagram  is  for-
            warded  as  a data-link multicast. The destination data-link
            multicast address is selected as an algorithmic  translation
            of the IP multicast destination. See [RFC 1112] for details.

        o   On FDDI networks, the datagram is forwarded as  a  data-link
            multicast.   The  destination data-link multicast address is
            selected as an algorithmic translation of the  IP  multicast
            destination. See [RFC 1188] for details.

        o   On SMDS networks, the datagram is forwarded using  the  same
            SMDS  address  that  is  used by IP broadcast datagrams. See
            [RFC 1209] for details.

        o   On networks that support broadcast, but not multicast (e.g.,
            the  Experimental  Ethernet), the datagram is forwarded as a
            data-link broadcast. See [RFC 1112] for details.

        o   On point-to-point networks, the datagram is forwarded in the
            same  way  that  unicast  datagrams  are forwarded. See [RFC
            1112] for details.

    (10)
        Examine each of the downstream neighbors listed in the  forward-
        ing  cache  entry. If the TTL in the datagram is greater than or
        equal to the TTL specified for the downstream neighbor,  a  copy
        of  the  datagram should be forwarded to the downstream neighbor
        (as a data-link unicast). Before forwarding the  datagram  copy,
        the copy's TTL should be decremented by 1.

    ICMP error messages are never generated in response to  received  IP
    multicasts.  In  particular,  ICMP destination unreachables and ICMP
    TTL expired messages are not generated by the above procedure if the
    router refuses to forward a multicast datagram.

    11.1.  Associating a MOSPF interface with a received datagram

        A MOSPF interface must be associated with a  received  multicast
        datagram before it is forwarded (see Step 1a of Section 11), and
        with received IGMP Host Membership Reports before they are  pro-
        cessed (see Section 9.2).





[Moy]                                                          [Page 54]

Internet Draft        Multicast Extensions to OSPF        September 1992


        When there is only a single IP network assigned to the  physical
        interface  that  received  the datagram, the choice of receiving
        MOSPF interface is clear. When there  are  multiple  logical  IP
        networks  attached  to  the  receiving  physical  interface, the
        receiving MOSPF interface is selected as follows. Examine all of
        the  MOSPF  interfaces  associated  with  the receiving physical
        interface. Discard those interfaces whose  IPMulticastForwarding
        parameter  has  been set to disabled. The receiving MOSPF inter-
        face is then the  remaining  interface  having  the  highest  IP
        interface  address  (or  NULL  if  there are no remaining inter-
        faces)[20].

    11.2.  Locating the source network

        MOSPF forwarding cache entries  are  rooted  at  the  datagram's
        source  IP network/subnet/supernet. For this reason, whenever an
        IP multicast datagram is received, the IP network  belonging  to
        the  datagram's  IP source address must be found. This is accom-
        plished by the following algorithm:

        Look up the OSPF TOS 0 routing table entry[21] corresponding  to
        datagram's  IP  source  address, as described in Section 11.1 of
        [OSPF]. If this routing table entry describes an OSPF intra-area
        or inter-area route, the source network is set to be the network
        defined by the routing table entry's Destination ID and  Address
        Mask  (see  Section 11 of [OSPF]). Otherwise (i.e., the matching
        routing table entry specifies an external route, or there is  no
        matching  routing table entry), the list of AS external-LSAs are
        examined, determining the best match (i.e., most specific match)
        from among those LSAs which have been originated by reachable AS
        boundary routers and which have their MC-bit  set  (see  Section
        A.1).  The  source network is set to the network/subnet/supernet
        (possibly even the default route) described by the best matching
        AS  external-LSA. AS external-LSAs specifying a cost of LSInfin-
        ity are eligible for this best match, as long as their MC-bit is
        set.

        External sources are treated differently in the  above  calcula-
        tion  since  it  is  likely that the Internet will have separate
        multicast and unicast topologies for some time to come. When the
        multicast  and  unicast  topologies do merge, the MC-bit will be
        set on all AS external-LSAs and the above use of the  LSInfinity
        metric  (to  indicate  a  route that is to be used for multicast
        traffic, but not unicast traffic), will no longer be  necessary.
        At  that  time, the determination of source network for external
        sources will revert to the same simple routing table lookup that
        is used for internal sources.




[Moy]                                                          [Page 55]

Internet Draft        Multicast Extensions to OSPF        September 1992


        As an example of the logic for external sources, suppose a  mul-
        ticast  datagram  is  received  having  the  IP  source  address
        10.1.1.1. Suppose also that the three AS external-LSAs shown  in
        Table  3  are  in  the router's OSPF database. The routing table
        lookup  would  yield  the  network  10.1.1.0  with  a  mask   of
        255.255.255.0,  however  the  above  calculation  would choose a
        source network of 10.1.0.0 with a mask of  255.255.0.0,  despite
        the fact that its matching LSA has a cost of LSInfinity.

    11.3.  Forwarding locally originated multicasts

        This section describes how a MOSPF router forwards  a  multicast
        datagram  that  has  been  originated by one of the router's own
        internal applications.  The  process  begins  with  one  of  the
        router's  internal  applications  formatting  and addressing the
        datagram. Forwarding the locally originated multicast then  con-
        sists of the following steps:

        (1) Find the router  interface  whose  IP  address  matches  the
            datagram's  source  address. Multicast the datagram out that
            interface, according to the Host extensions  for  IP  multi-
            casting specified in [RFC 1112].

        (2) If the router interface found in the previous step has  been
            configured  for  OSPF,  set the receiving MOSPF interface to
            that interface.  Otherwise, set the receiving  MOSPF  inter-
            face to NULL.

        (3) Exeqcute the MOSPF forwarding process described  in  Section
            11, beginning with its Step 4.

        The above algorithm amounts to the  router  always  multicasting
        the  datagram  out  the  source interface, and the executing the
        basic forwarding algorithm (in Section 11) as  if  the  datagram
        had  actually  been  received  on the source interface. In those
        cases where the router receives its own multicast transmissions,


             Network    Mask            Cost         MC-bit
             ______________________________________________
             10.1.1.0   255.255.255.0   10           clear
             10.1.0.0   255.255.0.0     LSInfinity   set
             10.0.0.0   255.0.0.0       1            set


                    Table 3: Sample AS external-LSAs





[Moy]                                                          [Page 56]

Internet Draft        Multicast Extensions to OSPF        September 1992


        unwanted replication is prevented by Step 3 of  Section  11.  In
        fact,  this specification has purposely presented the forwarding
        algorithm  (both  for  received  and  for   locally   originated
        datagrams)  so  that  the  correct  forwarding actions are taken
        independent of whether the router  receives  its  own  multicast
        transmissions.

12.  Construction of forwarding cache entries

    This section details the building of a MOSPF forwarding cache entry.
    A  high  level  discussion  of  this  construction  has already been
    presented in Sections 2.3, 2.3.1, 2.3.2, 3.2,  and  4.1.  Forwarding
    cache  entries  are  built  on  demand, when a multicast datagram is
    received and no matching forwarding cache entry is found (see Step 6
    of Section 11).  The parameters passed to the forwarding cache entry
    build process are: the datagram's source network (see Section  11.2)
    and  its  destination group address. These two parameters are called
    SourceNet and Group G in the following algorithm. The main steps  in
    the build process are the following:

    (1) Allocate the forwarding cache entry. Initialize its Source  net-
        work  to  SourceNet,  its Destination multicast group to Group G
        and its IP TOS field to match the multicast datagram's TOS. Ini-
        tialize  its  upstream node and list of downstream interfaces to
        NULL.

    (2) For each Area A to which the calculating router is attached:

        a.  Calculate Area A's datagram shortest-path tree. This  calcu-
            lation  is  described in Section 12.2 below. In many ways it
            is similar to the calculation of OSPF's  intra-area  routes,
            described  in  Section  16.1 of [OSPF]. The main differences
            between the multicast datagram shortest-path  tree  calcula-
            tion and OSPF's intra-area unicast calculation are listed in
            Section 12.2.9 below. As a product of each  area's  datagram
            shortest-path  tree,  the  forwarding  cache entry's list of
            outgoing interfaces is (possibly) updated.

            Area A's datagram shortest-path tree  is  dependent  on  the
            datagram's IP TOS. Section 12.2 describes the TOS 0 datagram
            shortest-path tree. The modifications necessary for non-zero
            TOS values are detailed in Section 12.2.8.

        b.  Possibly set the forwarding  cache  entry's  upstream  node.
            Only  one  of  the  calculating router's attached areas will
            determine the forwarding cache entry's upstream  node.  This
            area is called the datagram's RootArea. The RootArea is ini-
            tially set to  NULL.  After  completing  Area  A's  datagram



[Moy]                                                          [Page 57]

Internet Draft        Multicast Extensions to OSPF        September 1992


            shortest-path  tree,  the calculation in Section 12.2.7 will
            determine whether Area A is the datagram's RootArea.

    (3) Update the forwarding cache entry's list of outgoing interfaces,
        according  to  the  contents  of  the local group database. This
        ensures multicast delivery to group members residing on the cal-
        culating  router's  directly  attached networks. This process is
        described in Section 12.3.

    These main steps are described in more detail  below.  The  detailed
    description  begins  with an explanation of the major data structure
    used by the datagram shortest-path tree calculation: The Vertex data
    structure.

    12.1.  The Vertex data structure

        A datagram shortest-path tree is built by the  Dijkstra  or  SPF
        algorithm.  The  algorithm is stated herein using graph-oriented
        language: vertices and links. Vertices are  the  area's  routers
        and  transit  networks,  and links are the router interfaces and
        point-to-point lines that connect them. Each vertex has the fol-
        lowing  state information attached to it. Basically, this infor-
        mation indicates the current best path from the SourceNet to the
        vertex, and the position of the vertex relative to the calculat-
        ing router. Note that a separate datagram shortest-path tree  is
        built  for  each area, and that the vertices described below are
        also specific to a single area (called Area A).

        o   Vertex type. Set to 1 for routers, 2 for  transit  networks.
            Note that this coding matches the coding for vertices listed
            in the group-membership-LSA (see Section A.3).

        o   Vertex ID. A 32-bit identifier for the vertex. For  routers,
            set  to  the  router's OSPF Router ID. For transit networks,
            set the IP address of the network's Designated Router.  Note
            that  this  coding matches the coding for vertices listed in
            the group-membership-LSA (see Section A.3).

        o   LSA. The link state  advertisement  describing  the  vertex'
            immediate  neighborhood.  Can  be discovered by performing a
            database lookup in Area A's link state database (see Section
            12.2  of  [OSPF]),  with LS type set to Vertex type and Link
            State ID set to Vertex ID.

        o   Parent. In the current best path from SourceNet to the  ver-
            tex,  the  router/transit  network immediately preceding the
            vertex. Note that the parent can change as better and better
            paths  are  found,  up  until the vertex is installed on the



[Moy]                                                          [Page 58]

Internet Draft        Multicast Extensions to OSPF        September 1992


            shortest-path tree.

        o   IncomingLinkType. This parameter is set to the type of  link
            that  led  to  Vertex's inclusion on the shortest-path tree.
            Listed in order of decreasing preference[22],  the  possible
            types  are:  ILVirtual  (virtual links), ILDirect (vertex is
            directly attached to SourceNet),  ILNormal  (either  router-
            to-router  or router-to-network links), ILSummary (OSPF sum-
            mary links), ILExternal (OSPF AS external links), or  ILNone
            (the vertex is not on the shortest-path tree).

        o   AssociatedInterface/Neighbor. If the current best path  from
            SourceNet to the vertex goes through the calculating router,
            this parameter indicates the calculating router's  interface
            (or neighbor) which leads to the vertex.

        o   Cost. The cost, in terms of the OSPF link state  metric,  of
            the  current  best  path  from SourceNet to the vertex. Note
            that if the cost of the path is a combination of both exter-
            nal  type 2 and internal OSPF metrics, that the vertex' cost
            parameter reflects both cost components. Remember that  type
            2  cost component is always more significant than the type 1
            component.

        o   TTL. If the current best path from SourceNet to vertex  goes
            through  the calculating router, TTL is set to the number of
            routers between the calculating router and the vertex.  This
            includes  the  calculating  router, but does not include the
            vertex itself.

    12.2.  The SPF calculation

        This section details the construction of datagram  shortest-path
        trees.   Such  a tree describes the path of a multicast datagram
        as it traverses an OSPF area. For a given datagram, each  router
        in  an OSPF area builds an identical tree. A router connected to
        multiple areas builds a separate datagram shortest-path tree for
        each area.

        The datagram shortest-path tree is built by the Dijkstra or  SPF
        algorithm,  which  is the same algorithm used to discover OSPF's
        intra-area unicast routes (see  Section  16.1  of  [OSPF]).  The
        algorithm  is  stated  herein and in [OSPF] using graph-oriented
        language: vertices and links. Vertices are  the  area's  routers
        and  transit  networks,  and links are the router interfaces and
        point-to-point lines that connect them. Basically, the algorithm
        manipulates  two  lists  of vertices: the candidate list and the
        forming shortest-path tree. The candidate list consists of those



[Moy]                                                          [Page 59]

Internet Draft        Multicast Extensions to OSPF        September 1992


        vertices  to which paths have been discovered, but for which the
        optimality of the paths is yet unknown. At  each  cycle  of  the
        algorithm,  the  vertex  closest  to  the tree's root, yet still
        remaining on the candidate list, is  moved  from  the  candidate
        list  to  the shortest-path tree. Then the neighbors of the just
        processed   vertex   are   examined   for   possible    addition
        to/modification  of the candidate list. The algorithm terminates
        when the candidate list is empty.

        The datagram shortest-path tree for Area A is constructed in the
        following  steps.  The  datagram's SourceNet and its destination
        group Group G are inputs to the calculation (see Step 2a of Sec-
        tion 11). The datagram shortest-path tree also depends on the IP
        Type of service specified in the datagrams' IP Header.  However,
        a discussion of TOS is deferred until Section 12.2.8; all calcu-
        lations and costs in the current section  concern  TOS  0  only.
        Call  the  router performing the calculation Router RTX. At each
        step (and in the subordinate  Sections  12.2.1  through  12.2.8)
        LSAs  from  Area  A's  link  state database are examined. In all
        cases, any LSA having age MaxAge is ignored. The  main  body  of
        the  calculation  is  in Steps 4 and 5, which are repeated until
        the candidate list becomes empty:

        (1) Initialize the algorithm's data structures.  Clear  the  SPF
            tree.   Initialize the state of each vertex in Area A (i.e.,
            the area's routers and transit networks) to: Parent  set  to
            NULL,  Incoming  Link  Type  set  to  ILNone  and downstream
            interface/neighbor set to NULL.

        (2) Initialize the candidate list. One or more vertices are ini-
            tially  placed on the candidate list, depending on the loca-
            tion of SourceNet with respect to Area  A  and  Router  RTX.
            This  breaks  down into the following cases (which are named
            for later reference):

            o   Case SourceIntraArea: SourceNet belongs to  Area  A.  In
                this  case, the candidate list is initialized as in Sec-
                tion 12.2.1.

            o   Case SourceInterArea1: SourceNet belongs to an OSPF area
                that  is  not  directly  attached to Router RTX. In this
                case, the candidate list is initialized  as  in  Section
                12.2.2.

            o   Case SourceInterArea2: SourceNet does not belong to Area
                A, but it still belongs to an OSPF area that is directly
                attached to Router RTX.  In  this  case,  the  candidate
                list is initialized as in Section 12.2.3.



[Moy]                                                          [Page 60]

Internet Draft        Multicast Extensions to OSPF        September 1992


            o   Case SourceExternal: SourceNet is external to  the  OSPF
                routing  domain, and Area A is not an OSPF stub area. In
                this case, the candidate list is initialized as in  Sec-
                tion 12.2.4.

            o   Case SourceStubExternal: SourceNet is  external  to  the
                OSPF routing domain, and Area A is an OSPF stub area. In
                this case, the candidate list is initialized as in  Sec-
                tion 12.2.5.

            Two different routers in Area A may  select  different  ini-
            tialization  cases  above. For example, consider the network
            configuration shown in Figure 4. When calculating the Area 3
            datagram  shortest-path  tree for a datagram whose source is
            Network N7 (e.g., from Host H5) and destination is Group Ma,
            Router  RT11  would initialize the candidate list using Case
            SourceInterArea2 while Router RT9 would use  Case  SourceIn-
            terArea1.  Likewise,  if  Area  3 were configured as an OSPF
            stub area, Router RT11  would  use  Case  SourceStubExternal
            while  Router  RT9 would use Case SourceInterArea1! However,
            despite  the  possibility  of  routers  selecting  different
            cases, all routers in an area will still initialize the can-
            didate list (and in fact, run the rest of the  SPF  calcula-
            tion) identically.

        (3) If the candidate list is empty, the algorithm terminates.

        (4) Move closest candidate vertex  to  the  shortest-path  tree.
            Select  the  vertex on the candidate list that is closest to
            SourceNet (i.e., has the smallest Cost value). If there  are
            multiple   possibilities,   select   transit  networks  over
            routers. If there are still multiple  possibilities  remain-
            ing,  select  the  vertex having the highest Vertex ID. Call
            the chosen vertex Vertex V. Remove Vertex V from the  candi-
            date list, and install it on the shortest-path tree.

            Next, determine whether Vertex V has been labelled with  the
            Destination  multicast Group G. If so, it may cause the for-
            warding cache entry's list of outgoing  interfaces/neighbors
            to be updated. See Section 12.2.6 for details.

        (5) Examine Vertex V's neighbors for possible inclusion  in  the
            candidate  list.  Consider  Vertex V's LSA. Each link in the
            LSA describes a connection to a neighboring  router/network.
            If  the  link  connects  to a stub network, examine the next
            link in the LSA. Otherwise, the link (Link L) connects to  a
            neighboring  transit  node. Call this node Vertex W. Perform
            the following steps on Vertex W:



[Moy]                                                          [Page 61]

Internet Draft        Multicast Extensions to OSPF        September 1992


            a.  If W is already on the shortest-path tree, or if W's LSA
                does  not contain a link back to vertex V, or if W's LSA
                has LS age of MaxAge, or if W is  not  multicast-capable
                (indicated  by  the  MC-bit in the LSA's Options field),
                examine the next link in V's LSA.

            b.  Otherwise determine the cost to associate with the  link
                from V to W.  If SourceNet belongs to Area A (Case Sour-
                ceIntraArea in Step 2), use the cost listed for  Link  L
                in  V's  LSA.  Otherwise,  use  the link's reverse cost:
                Examine W's LSA, and find the cost listed for  the  link
                connecting  back  to  V. Actually, when V and W are both
                routers, there may be multiple links  between  them.  In
                this  case,  use the smallest cost listed in W's LSA for
                any of the links connecting back to  V  and  having  the
                same  type  (as  specified  in  the  Router-LSA; must be
                either: point-to-point connection or  virtual  link)  as
                Link L[23].

            c.  Calculate the cost from SourceNet to W, when using  Link
                L.  It  is  the sum of the cost of SourceNet to V (i.e.,
                V's Cost parameter) plus the  link  cost  calculated  in
                Step  5b. Let this sum be Cost C. If W is not yet on the
                candidate list, install W on the candidate list, modify-
                ing  its parameters as specified below (Step 5d). Other-
                wise, W is on the candidate list already. In this  case,
                if:

                o   C is less than W's current cost, update W's  parame-
                    ters  on the candidate list as specified below (Step
                    5d).

                o   C is equal to W's current cost, then  the  following
                    tiebreakers  are invoked. The type of Link L is com-
                    pared to W's current IncomingLinkType, and whichever
                    link  has  the preferred type is chosen (the prefer-
                    ence order of link types is listed in Section 12.1's
                    definition  of  IncomingLinkType). If the link types
                    are the same, then a link whose Parent is a  transit
                    network  is  preferred  over  one  whose Parent is a
                    router. If the links are still equivalent, the  link
                    whose  Parent  has  the  higher Vertex ID is chosen.
                    Whenever Link L is chosen, W's parameters are  modi-
                    fied  as  below  (Step  5d). Whenever the previously
                    discovered link is chosen, the next link in V's  LSA
                    is examined instead.





[Moy]                                                          [Page 62]

Internet Draft        Multicast Extensions to OSPF        September 1992


                o   C is greater than W's current cost, examine the next
                    link in V's LSA.

            d.  At this point, a better candidate path has been found to
                Vertex  W,  using  Link  L. Modify Vertex W's parameters
                accordingly. W's Parent is set to Vertex V.  W's  Incom-
                ingLinkType  is  set to ILVirtual if Link L is a virtual
                link, otherwise IncomingLinkType is set to ILNormal. W's
                Cost    parameter   is   set   to   C.   W's   TTL   and
                AssociatedInterface/Neighbor parameters are set  accord-
                ing to one of the following cases:

                o   Vertex V is upstream of the calculating  router.  In
                    this case, Vertex W's TTL parameter is set to 0, and
                    its AssociatedInterface/Neighbor is set to NULL.

                o   Vertex V is the calculating router itself.  In  this
                    case,  W's TTL parameter is set to 1. If Link L is a
                    virtual link,  W's  AssociatedInterface/Neighbor  is
                    set        to       NULL.       Otherwise,       W's
                    AssociatedInterface/Neighbor  is  set  to  the  non-
                    virtual  interface  connecting  V to W which has the
                    smallest cost value. Note that, in the reverse  cost
                    (inter-area  and inter-AS multicast) cases, this may
                    not be the interface corresponding to Link  L.  How-
                    ever,  since W is only concerned with the node it is
                    receiving the datagram from (the upstream node;  see
                    Section  11),  and not with the particular interface
                    the datagram is received on, V is free to  pick  the
                    sending interface when there are multiple connecting
                    links.

                o   V is a transit network, and is  directly  downstream
                    from the calculating router (i.e., V's TTL is set to
                    1). W is then one of the calculating router's neigh-
                    bors. In this case, W's TTL parameter is also set to
                    1. If network V has been  configured  for  data-link
                    unicasting  (see  Section  B.2)  or  if  V is a non-
                    broadcast network, W's  AssociatedInterface/Neighbor
                    is  set  to  W itself (a neighbor of the calculating
                    router). Otherwise, W's AssociatedInterface/Neighbor
                    is set to the calculating router's interface to Net-
                    work V.

                o   Vertex V is downstream from the calculating  router,
                    and  either a) V is a router or b) V's TTL parameter
                    is   greater   than   1.   In   these   cases,   W's
                    AssociatedInterface/Neighbor   parameter  is  copied



[Moy]                                                          [Page 63]

Internet Draft        Multicast Extensions to OSPF        September 1992


                    directly from V.  If V is a router, W's TTL  parame-
                    ter  is set to V's TTL parameter incremented by one.
                    If V is a transit network, W's TTL parameter is  set
                    directly to V's TTL parameter.

        (6) If the candidate list is non-empty, go to Step 4. Otherwise,
            the algorithm terminates.

        After the datagram shortest-path tree for Area  A  is  complete,
        the  calculating router (RTX) must decide whether Area A, out of
        all of RTX's attached areas,  determines  the  forwarding  cache
        entry's  upstream  node. This determination is described in Sec-
        tion 12.2.7.

        Examples of the above SPF calculation, with particular  emphasis
        on the tiebreaking rules, are given in Appendix C.

        12.2.1.  Candidate list Initialization: Case SourceIntraArea

            In this case, SourceNet belongs  to  Area  A.  This  can  be
            determined by looking up SourceNet in the OSPF routing table
            (see Section 11.1 of [OSPF]). When SourceNet belongs to Area
            A, the matching OSPF routing table entry will have Path-type
            of intra-area and its associated Area will be  Area  A  (see
            Section 11 of [OSPF]).

            The candidate list is then  initialized  as  follows.  Start
            with  the  LSA  listed  as Link State Origin in the matching
            OSPF routing table entry.  If this  LSA  is  not  multicast-
            capable  (i.e,  its  Options field has the MC-bit clear) the
            candidate list should be set to NULL. Otherwise, the  vertex
            identified  by  the  LSA is installed on the candidate list,
            setting its vertex parameters as  follows:  IncomingLinkType
            set  to  ILDirect,  Cost  set  to  0,  Parent  to  NULL  and
            AssociatedInterface/Neighbor to NULL.

            As a consequence of this initialization, note that if  Sour-
            ceNet  is  a  stub  network, then the datagram shortest-path
            tree will not actually be rooted at the datagram source, but
            will instead be rooted at the MOSPF router that attaches the
            stub network to the rest of the MOSPF system.  For  example,
            consider  the  network configuration shown in Figure 4. When
            calculating the Area2  datagram  shortest-path  tree  for  a
            datagram whose source is Network N7 (e.g., from Host H5) and
            destination is Group Ma, Router RT11 (and all other  routers
            attached  to  Area 2) will begin with the candidate list set
            to Router RT. As another example, the datagram shortest-path
            tree  pictured  in  Figure  3 is really rooted at Router RT3



[Moy]                                                          [Page 64]

Internet Draft        Multicast Extensions to OSPF        September 1992


            instead of Network N4.

        12.2.2.  Candidate list Initialization: Case SourceInterArea1

            In this case, SourceNet belongs to an OSPF area that is  not
            directly  attached to the calculating router (RTX). This can
            be determined by looking up SourceNet in  the  OSPF  routing
            table  (see Section 11.1 of [OSPF]); the matching OSPF rout-
            ing table entry will have Path-type of inter-area (see  Sec-
            tion 11 of [OSPF]).

            The candidate list is then initialized as  follows.  Examine
            the Area A summary-LSAs advertising SourceNet. For each such
            summary-LSA: if both a) the MC-bit is set in  the  LSA's  LS
            Options  field  and  b)  the advertised cost is not equal to
            LSInfinity, then the vertex representing the LSA's advertis-
            ing  area  border  router is added to the candidate list. An
            added vertex' state is initialized as: IncomingLinkType  set
            to  ILSummary,  Cost  to  whatever is advertised in the LSA,
            Parent to NULL and AssociatedInterface/Neighbor to NULL.

            For example, consider the  network  configuration  shown  in
            Figure  4.   When  calculating the Area 1 datagram shortest-
            path tree for a datagram whose source is Network  N7  (e.g.,
            from  Host H5) and destination is Group Ma, Router RT2 would
            initialize the candidate list to contain the two area border
            routers RT3 (with a cost of 20) and RT4 (with a cost of 19).
            See Figure 6 for more details.

        12.2.3.  Candidate list Initialization: Case SourceInterArea2

            In this case, SourceNet belongs to an OSPF area  other  than
            Area  A, but one that is still directly attached to the cal-
            culating router (RTX).  This can be determined by looking up
            SourceNet  in  the  OSPF  routing table (see Section 11.1 of
            [OSPF]); the matching OSPF routing  table  entry  will  have
            Path-type  of  intra-area (see Section 11 of [OSPF]) and its
            associated area will be different than Area A.

            The candidate list is then initialized in the following  two
            steps:

            (1) Find the Area A summary-LSA that best matches SourceNet,
                excluding  those summary-LSAs specifying cost LSInfinity
                or having unreachable Advertising Routers[24].  A match-
                ing  summary-LSA  is  one  that  advertises  a  range of
                addresses containing SourceNet; the best matching is  as
                usual  the  most  specific match. Let SourceRange be the



[Moy]                                                          [Page 65]

Internet Draft        Multicast Extensions to OSPF        September 1992


                network described by the best matching summary-LSA.

            (2) Similar to the logic in the SourceInterArea1 case, exam-
                ine  all  the  Area A summary-LSAs which advertise Sour-
                ceRange. For each such summary-LSA: if both a)  the  MC-
                bit  is set in the LSA's Options field and b) the adver-
                tised cost is not equal to LSInfinity, then  the  vertex
                representing the LSA's advertising area border router is
                added to the candidate list. An added vertex'  state  is
                initialized  as: IncomingLinkType set to ILSummary, Cost
                to whatever is advertised in the LSA, Parent to NULL and
                AssociatedInterface/Neighbor to NULL.

            The reason why SourceRange is used, instead of simply  using
            SourceNet  (as  was  done in case SourceInterArea1), is that
            routing information may have been collapsed  at  area  boun-
            daries.  In  order  for Area A's area border routers and its
            internal routers to  construct  the  same  Area  A  datagram
            shortest-path  tree,  they  must both start at SourceRange -
            Area A's internal routers know nothing about SourceNet. Note
            that  SourceRange is not discovered simply by looking at the
            calculating router's configured set of area address  ranges,
            in  order to avoid dependence on the configured area address
            ranges being synchronized across all area border routers.

            For example, consider the  network  configuration  shown  in
            Figure  4.   When  calculating the Area 2 datagram shortest-
            path tree for a datagram whose source  is  Network  N11  and
            destination  is  Group Ma, Router RT11 would calculate Sour-
            ceRange to be the collection: Networks N9-N11 and  Host  H1.
            It  would  then  initialize  the  candidate  list to contain
            itself (RT11) only, with an associated Cost of 1 (since RT11
            is  advertising Networks N9-N11 and Host H1 in a summary-LSA
            with a cost of 1).

        12.2.4.  Candidate list Initialization: Case SourceExternal

            In this case, SourceNet is  external  to  the  OSPF  routing
            domain,  and  Area  A  is not an OSPF stub area. This can be
            determined by looking up SourceNet in the OSPF routing table
            (see  Section  11.1  of  [OSPF]);  the matching OSPF routing
            table entry will have Path-type of either external type 1 or
            external type 2.

            The candidate list is then initialized as follows. Note that
            an  attempt  may  be made to add a Vertex W to the candidate
            list when W already belongs to the candidate list. When this
            happens,  W's  vertex  parameters  are  updated  if the Cost



[Moy]                                                          [Page 66]

Internet Draft        Multicast Extensions to OSPF        September 1992


            parameter it would be added with is  better[25]  (closer  to
            SourceNet)  that  its previous value. When the costs are the
            same, W's parameters are still modified if the IncomingLink-
            Type    it    would   be   added   with   is   better   (see
            IncomingLinkType's definition in Section 12.1) than its pre-
            vious value.

            For each AS external-LSA advertising SourceNet, the  follow-
            ing steps are performed:

            o   If the AS external's MC-bit is clear or if its advertis-
                ing router is not reachable, then the AS external-LSA is
                not used. AS external-LSAs having their MC-bit  set  and
                advertising a cost of LSInfinity can be used; these LSAs
                describe paths that can be used for multicast,  but  not
                unicast, data traffic (see Section 11.2).

            o   If the AS external-LSA's  Forwarding  address  field  is
                0.0.0.0,  the following vertices are added to the candi-
                date list. If the Advertising AS boundary  router  (call
                it  ASBR) belongs to Area A, the vertex representing the
                AS boundary router is added to the candidate list  using
                parameters:  IncomingLinkType set to ILExternal, Cost to
                whatever is advertised in the LSA, Parent  to  NULL  and
                AssociatedInterface/Neighbor  to  NULL. Then, regardless
                of whether ASBR belongs to  Area  A,  all  Area  A  area
                border    routers   that   are   advertising   reachable
                multicast-capable (MC-bit set) type 4  summary-LSAs  for
                ASBR  are  added  to  the candidate list. Each such area
                border router  is  added  with  the  parameters:  Incom-
                ingLinkType  set  to ILSummary, Cost to the sum of what-
                ever is advertised in the type 4  summary-LSA  plus  the
                value  in  the  original AS external-LSA, Parent to NULL
                and AssociatedInterface/Neighbor to NULL.

            o   If the AS external-LSA's  Forwarding  address  field  is
                non-zero,  the  Forwarding  address  is looked up in the
                OSPF routing table. Then processing breaks into  one  of
                the following cases:

                o   The Forwarding address is not usable. In this  case,
                    nothing is added to the candidate list. The Forward-
                    ing address is not usable if either it has no match-
                    ing  routing table entry, or if the matching routing
                    table entry is neither of  type  intra-area  nor  of
                    type inter-area.





[Moy]                                                          [Page 67]

Internet Draft        Multicast Extensions to OSPF        September 1992


                o   The Forwarding address belongs to  Area  A[26]:  the
                    Forwarding address' matching routing table entry has
                    Path-type of intra-area and its associated  Area  is
                    Area  A. In this case, the vertex represented by the
                    matching routing table  entry's  Link  State  Origin
                    field  is added to the candidate list (assuming that
                    the vertex  is  multicast-capable).  The  vertex  is
                    added  with  the parameters: IncomingLinkType set to
                    ILExternal, Cost to whatever was advertised  in  the
                    original   AS   external-LSA,  Parent  to  NULL  and
                    AssociatedInterface/Neighbor to NULL.

                o   The Forwarding address belongs to an  area  that  is
                    not  attached  to  Router  RTX[27]:  the  Forwarding
                    address' matching routing table entry has  Path-type
                    of  inter-area.  Call the network represented by the
                    matching routing table entry  ForwardNet.  For  each
                    reachable  multicast-capable summary-LSA (in Area A)
                    advertising ForwardNet, add  the  LSA's  advertising
                    area  border  router  to  the  candidate  list using
                    parameters: IncomingLinkType set to ILSummary,  Cost
                    to   the  sum  of  whatever  is  advertised  in  the
                    summary-LSA  plus  the  value  in  the  original  AS
                    external-LSA,      Parent      to      NULL      and
                    AssociatedInterface/Neighbor to NULL.

                o   The Forwarding address belongs  to  another  one  of
                    Router  RTX's  attached  areas[28]:  the  Forwarding
                    address' matching routing table entry has  Path-type
                    of  intra-area and its associated Area is other than
                    Area A.  Call the network represented by the  match-
                    ing  routing  table entry ForwardNet. First find the
                    Area A  summary-LSA  that  best  matches  SourceNet,
                    excluding  those  summary-LSAs specifying cost LSIn-
                    finity or having  unreachable  Advertising  Routers.
                    Let  ForwardRange  be  the  network described by the
                    best matching summary-LSA. Then, for each  reachable
                    multicast-capable  summary-LSA (in Area A) advertis-
                    ing ForwardRange, add  the  LSA's  advertising  area
                    border  router  to  the candidate list using parame-
                    ters: IncomingLinkType set to ILSummary, Cost to the
                    sum  of  whatever  is  advertised in the summary-LSA
                    plus the value  in  the  original  AS  external-LSA,
                    Parent  to  NULL and AssociatedInterface/Neighbor to
                    NULL.

            The above calculation can be restated as  follows.  Each  of
            Area   A's  inter-area  multicast  forwarders  and  inter-AS



[Moy]                                                          [Page 68]

Internet Draft        Multicast Extensions to OSPF        September 1992


            multicast  forwarders  are   examined.   Those   that   have
            multicast-capable  paths to SourceNet (represented as either
            a multicast-capable AS external link or the concatenation of
            a  type  4  summary link and a multicast-capable AS external
            link) are added to the candidate list  as  router  vertices.
            (It is possible that, when considering a router that is both
            an inter-area multicast forwarder and an inter-AS  multicast
            forwarder,  two  equal cost paths exist to SourceNet, one an
            AS external link and the other a concatenation of a  type  4
            summary link and an AS external link. In this case, the con-
            catenation of the summary link and the AS external  link  is
            preferred).  The  added  vertex'  state  is  set as follows:
            IncomingLinkType set to ILSummary if the path is represented
            as a concatenation of a type 4 summary link and an AS exter-
            nal link, IncomingLinkType set to ILExternal otherwise, Cost
            set  to  the  cost of the shortest path from vertex to Sour-
            ceNet, Parent set to NULL  and  AssociatedInterface/Neighbor
            set to NULL.

            For example, consider the  network  configuration  shown  in
            Figure  4.   When  calculating the Area 2 datagram shortest-
            path tree for a datagram whose source  is  Network  N14  and
            destination  is  Group  Ma, the candidate list would be ini-
            tialized to the two routers RT7 at a cost of 14 and RT10  at
            a  cost of 19. This assumes that the external costs pictured
            in Figure 4 are external Type 1s.

        12.2.5.  Candidate list  Initialization:  Case  SourceStubExter-
            nal

            In this case, SourceNet is  external  to  the  OSPF  routing
            domain,  and Area A is an OSPF stub area. This can be deter-
            mined by looking up SourceNet in the OSPF routing table (see
            Section  11.1  of  [OSPF]);  the matching OSPF routing table
            entry will have Path-type  of  either  external  type  1  or
            external type 2.

            The candidate list is then  initialized  similarly  to  case
            SourceInterArea1.   The   Area  A  summary-LSAs  advertising
            DefaultDestination are examined. For each  such  summary-LSA
            having both its MC-bit set and its advertised cost not equal
            to LSInfinity, the vertex representing the LSA's advertising
            area  border router is added to the candidate list. An added
            vertex' state is initialized  as:  IncomingLinkType  set  to
            ILSummary, Cost to whatever is advertised in the LSA, Parent
            to NULL and AssociatedInterface/Neighbor to NULL.





[Moy]                                                          [Page 69]

Internet Draft        Multicast Extensions to OSPF        September 1992


            The most likely outcome of the above is  that  all  of  stub
            Area  A's  inter-area multicast forwarders will be installed
            on the candidate list, with appropriate costs.

        12.2.6.  Processing labelled vertices

            When  encountered  during  the  SPF  calculation,   vertices
            labelled  with the destination multicast group (Group G) may
            cause  the  forwarding  cache  entry's  list  of  downstream
            interfaces/neighbors  to  be modified.  A Vertex V in Area A
            is labelled with Group G if and only if at least one of  the
            following holds:

            (1) V is a router, and its router-LSA indicates that it is a
                wild-card   multicast  receiver  (i.e.,  bit  W  in  its
                router-LSA is set). This will be true whenever V  is  an
                inter-area or inter-AS multicast forwarder.

            (2) V is listed in the body of a  group  membership-LSA.  In
                particular,  find the originator of Vertex V's LSA; call
                it Router Y. Then find the group-membership-LSA in  Area
                A's  link state database which has Link State ID = Group
                G and Advertising Router = Router Y (see  Section  A.3).
                If  this group-membership-LSA exists, and if Vertex V is
                listed in the body of the LSA (see Sections 10 and A.3),
                then Vertex V is labelled with Group G.

            When Vertex V is added to the shortest-path tree in  Step  3
            of Section 12.2, and if Vertex V is both downstream from the
            calculating       router       (i.e.,       Vertex       V's
            AssociatedInterface/Neighbor  is non-NULL) and labelled with
            Group G, then  Vertex  V's  AssociatedInterface/Neighbor  is
            added  to  the  forwarding  cache entry's list of downstream
            interfaces/neighbors. In addition, Vertex V's TTL  value  is
            attached  to the added downstream interface/neighbor. If the
            particular interface/neighbor had already been added to  the
            list  of downstream interfaces/neighbors, the list is simply
            modified by setting the downstream interface/neighbor's  TTL
            value  to  the  minimum of its existing TTL value and Vertex
            V's TTL value.

        12.2.7.  Merging datagram shortest-path trees

            After the datagram shortest-path tree for  Area  A  is  com-
            plete, the calculating router (RTX) must decide whether Area
            A, out of all of its attached areas, determines the forward-
            ing  cache entry's upstream node.  This is done by examining
            RTX's position on the Area A  datagram  shortest-path  tree,



[Moy]                                                          [Page 70]

Internet Draft        Multicast Extensions to OSPF        September 1992


            which  is  in  turn  described  by  RTX's Area A Vertex data
            structure. If RTX's vertex IncomingLinkType is either ILNone
            (RTX  is not on the tree), ILVirtual or ILSummary, then some
            area other than Area A will  determine  the  upstream  node.
            Otherwise, Area A might possibly determine the upstream node
            (i.e., may be selected the RootArea), depending on the  fol-
            lowing tiebreakers[29]:

            o   If RootArea has not been set, then set RootArea to  Area
                A.  Otherwise, compare the present RootArea to Area A in
                the following:

            o   Choose the area that is "nearest to the source". Nearest
                to the source depends on each area's candidate list ini-
                tialization case, as it occurs  in  Step  2  of  Section
                12.2.  The  initialization  cases,  listed  in  order of
                decreasing preference  (or  nearest  to  farthest)  are:
                SourceIntraArea,  SourceInterArea1,  SourceExternal  and
                SourceStubExternal. Areas whose candidate list initiali-
                zation  falls  into case SourceInterArea2 are never used
                as the RootArea. As an  example,  consider  the  network
                configuration  shown  in  Figure 4. When calculating the
                datagram shortest-path tree for a datagram whose  source
                is  Network  N7  (e.g., from Host H5) and destination is
                Group Ma, Router RT11 would set its RootArea to  Area  2
                (Case SourceIntraArea) instead of Area 3 (Case SourceIn-
                terArea2) or the backbone Area 0 (Case SourceInterArea).

            o   If there are still two equally good areas,  and  one  of
                them is the backbone, set RootArea to the backbone (Area
                0).

            o   If there are still two equally good areas, set  RootArea
                to  the  area whose datagram shortest-path tree provides
                the shortest path from SourceNet to RTX. This is a  com-
                parison of RTX's Vertex parameter Cost in the two areas.

            o   If there are still two equally good areas, set  RootArea
                to one with the highest OSPF Area ID.

            If the above has set the RootArea to be Area A, the forward-
            ing  cache  entry's  upstream  node must be set accordingly.
            This setting depends on the IncomingLinkType in RTX's Area A
            Vertex  structure. If IncomingLinkType is equal to ILDirect,
            the upstream  node  is  set  to  the  appropriate  directly-
            connected  stub  network. If equal to ILNormal, the upstream
            node is set to the Parent  field  in  RTX's  Area  A  Vertex
            structure.  If equal to ILExternal, the upstream node is set



[Moy]                                                          [Page 71]

Internet Draft        Multicast Extensions to OSPF        September 1992


            to the placeholder EXTERNAL.

        12.2.8.  TOS considerations

            The previous sections 12.2 through 12.2.7 described the con-
            struction  of  a  TOS 0 (default TOS) datagram shortest-path
            tree. However, in a TOS-capable router, a separate tree  may
            be  built  for  each TOS. If a TOS-capable router receives a
            multicast datagram that specifies a non-zero TOS X, it first
            builds  the TOS 0 datagram shortest-path tree.  Then, if all
            the routers on the pruned tree are TOS-capable,  a  separate
            TOS  X datagram shortest-path tree is calculated[30]. Other-
            wise, the TOS 0 tree is used for all  datagrams,  regardless
            of their specified TOS.

            To determine whether there are any TOS-incapable routers  on
            the  pruned  TOS 0 tree, the following additions are made to
            Section 12.1's tree calculation:

            o   A new piece of state information is added to  each  ver-
                tex:   TOS-capable  path.  This  indicates  whether  the
                present path from SourceNet to vertex, as represented on
                the  datagram  shortest-path  tree,  contains  only TOS-
                capable routers.

            o   The TOS-capable path parameter is  calculated  when  the
                vertex is first added to the candidate list and recalcu-
                lated when/if the vertex' position on the candidate list
                is modified (see Section 12.1's Step 2 and Step 5d). The
                parameter is set to TRUE if both the  vertex  itself  is
                TOS-capable  and  the vertex' parent has its TOS-capable
                path parameter set to TRUE; otherwise, TOS-capable  path
                is set to FALSE.

            o   All routers on the TOS 0 datagram shortest-path tree are
                TOS-capable  if  and only if, whenever a vertex labelled
                with Group G is added to the shortest-path tree (Section
                12.2.6),  the  value  of  the  vertex'  TOS-capable path
                parameter is TRUE.

            The source of the multicast datagram is always located using
            a  TOS  0 routing table lookup, regardless of the datagram's
            TOS classification (see Section 11.2).  If  the  calculating
            router  is  not  capable of TOS-based routing, it calculates
            only TOS 0 datagram shortest-path trees, and  uses  them  to
            route  datagrams  independent of TOS value.  Otherwise, when
            calculating the TOS X datagram shortest-path tree, the algo-
            rithm in Section 12.1 is used, with the modifications listed



[Moy]                                                          [Page 72]

Internet Draft        Multicast Extensions to OSPF        September 1992


            below.

            o   When calculating RangeNet and ForwardRange  in  Sections
                12.2.3 and 12.2.4 respectively, only summary-LSAs having
                TOS 0 cost of LSInfinity are excluded  (no  change  from
                the  TOS  0  case). However, when adding vertices to the
                candidate list in Sections 12.2.2  through  12.2.5,  the
                TOS X cost of the summary links and/or AS external links
                (and not the TOS 0 cost) are reflected in the added ver-
                tices' Cost parameter.

            o   In Step 5 of Section 12.2, the TOS X cost of Link L  (in
                the appropriate direction) is used, not the TOS 0.

            o   Non-TOS-routers are not added to the candidate list, and
                are thus excluded from the trees.

        12.2.9.  Comparison to the unicast SPF calculation

            There are many similarities between the  construction  of  a
            multicast datagram's shortest-path trees in Section 12.2 and
            OSPF's intra-area  route  calculation  for  unicast  traffic
            (Section  16.1 of [OSPF]). Both have been described in terms
            of Dijkstra's algorithm. However,  there  are  some  differ-
            ences. The major differences are listed below:

            o   In the multicast case, the datagram SPF  calculation  is
                rooted  at  the  datagram's source. In the unicast case,
                each router is the root of its  own  unicast  intra-area
                SPF calculation.

            o   In the multicast case, the datagram  shortest-path  tree
                is  a true tree; i.e., between any two nodes on the tree
                there is one path. However, due  to  the  provision  for
                equal-cost multipath in [OSPF], the unicast SPF calcula-
                tion may add additional links to the shortest-path tree.

            o   In order to  avoid  unwanted  replication  of  multicast
                datagrams,  MOSPF  ensures that, for any given datagram,
                each router builds the exact same datagram shortest-path
                tree.  This  forces two differences from the unicast SPF
                calculation. First, it  eliminates  the  possibility  of
                equal-cost  multipath.  Secondly,  when the MOSPF system
                contains multiple alternate paths,  the  algorithm  must
                ensure  that each MOSPF router deterministically chooses
                the same  alternative.  For  this  reason,  tie-breaking
                mechanisms  have been specified in Steps 3 and 4 of Sec-
                tion 12.1.



[Moy]                                                          [Page 73]

Internet Draft        Multicast Extensions to OSPF        September 1992


            o   The calculation of datagram shortest  path  trees  takes
                into account only those links that connect transit nodes
                (i.e, router to router  or  router  to  transit  network
                links).  The  unicast SPF calculation in Section 16.1 of
                [OSPF] must additionally examine links to stub networks,
                although  this  is  done after all the transit links are
                examined.

            o   While both the multicast and unicast trees select  shor-
                test paths on the basis of the OSPF metric, the datagram
                shortest-path trees also keep track of  the  TTL  values
                between  the root (datagram source) and all destinations
                (group members). This enables more efficient implementa-
                tion of IP multicast's "expanding ring search" (see Sec-
                tion 2.3.4).

            o   In the multicast case, the algorithm is sometimes forced
                to  use  the  link  state cost for the reverse direction
                (i.e, the  cost  towards,  instead  of  away  from,  the
                source).  This is because the costs of OSPF summary-LSAs
                and AS external-LSAs, which sometime form  the  base  of
                the  multicast  datagram shortest-path trees, are speci-
                fied in the reverse direction (from the  multicast  per-
                spective).

            o   There are potentially many more  datagram  shortest-path
                trees  that  need  to be calculated (one for each source
                net, destination group and TOS  combination),  than  the
                limited  number of unicast SPF trees (one per each TOS).
                This is the main reason that the datagram  shortest-path
                trees  are  calculated  on demand; it is hoped that this
                will spread  the  cost  of  the  SPF  calculations  over
                time[31].

            o   The way that the two algorithms handle TOS is different.
                In  the  multicast  case,  if  a  TOS-incapable  node is
                encountered during the calculation of the TOS 0 datagram
                shortest-path  tree,  the  TOS  0 datagram shortest-path
                tree is used instead of trying to build the TOS  X  tree
                (see  Section  12.2.8).  In  the unicast case, the TOS X
                tree is built and TOS-incapable nodes are added  to  the
                TOS X SPF tree using TOS 0 costs.

    12.3.  Adding local database entries to the forwarding cache

        After the datagram shortest-path trees have been built for  each
        attached  area,  the forwarding cache has an upstream node and a
        list of downstream interfaces. In order to ensure  the  delivery



[Moy]                                                          [Page 74]

Internet Draft        Multicast Extensions to OSPF        September 1992


        of  the multicast datagram to group members on directly attached
        networks, the local group database (Section 8.4)  must  then  be
        scanned  for  possible addition to the list of downstream inter-
        faces. All local group database entries having Group G as Multi-
        castGroup  are  examined.   Suppose  [Group G, Network N] is one
        such entry. If the  calculating  router  (RTX)  is  Network  N's
        Designated  Router,  then  RTX's Network N interface is added to
        the list of outgoing interfaces, with a TTL of 1. If the Network
        N  interface  was already present in the list of outgoing inter-
        faces, its TTL is simply set to 1.

        For example, consider the network configuration shown in  Figure
        4  when  calculating  the  forwarding cache entry for a datagram
        whose source is Network N4 (e.g., from Host H2) and  destination
        is  Group  Mb. After calculating the datagram shortest-path tree
        for Area 1, Router RT2 would have set it upstream node  to  Net-
        work  N3 and its list of downstream interfaces to NULL. But then
        looking at its local group database, it would add its Network N2
        interface with a TTL of 1 to the list of downstream interfaces.

13.  Maintaining the forwarding cache

    A MOSPF router may, for resource reasons, limit the size of its for-
    warding  cache.  Old  cache  entries  can be purged to make room for
    newer entries, since they can always be rebuilt if  necessary.  This
    memo does not specify an algorithm to select which entries to purge.
    However, care should be taken to ensure that any particular entry is
    not  continually  built  and  then purged (i.e., thrashing should be
    avoided).

    The building of the forwarding cache has been  previously  described
    in  Section  12.  There are events that force one or more forwarding
    cache entries to be deleted and then rebuilt:

    o   When the internal topology of the MOSPF system changes, all for-
        warding  cache entries must be deleted. This is because internal
        topology  changes  may  invalidate  the  previously   calculated
        datagram shortest-path trees. Since the multicast routing calcu-
        lation depends on the result of  the  unicast  routing  calcula-
        tions,  the forwarding cache should be cleared after the unicast
        routing table is rebuilt.  Internal topology changes  are  indi-
        cated  when  both  a) a new instance of either a router-LSA or a
        network-LSA is received and b) the contents of  the  new  adver-
        tisement  (other  than  the  LS  age,  LS sequence number and LS
        checksum fields) is different from the previous instance.  Among
        other  things,  this  covers routers and links going up or down,
        and also routers that change from being  multicast-incapable  to
        being multicast-capable.



[Moy]                                                          [Page 75]

Internet Draft        Multicast Extensions to OSPF        September 1992


    o   When a type 3 summary-LSA (network summary)  changes,  all  for-
        warding cache entries must be examined. Those entries specifying
        datagram sources belonging to the range of  addresses  described
        by  the updated summary-LSA must be deleted. See Sections 12.2.3
        and 12.2.5.

    o   When the content of an AS external-LSA changes,  all  forwarding
        cache  entries specifying the named external network as datagram
        source must be deleted.

    o   When membership in a multicast  group  changes,  all  forwarding
        cache  entries  for  the particular group must be deleted. Group
        membership changes are indicated when either a) the content of a
        group-membership-LSA  changes  or b) an entry in the local group
        database (see Section 8.4) changes.

    o   When the cost to an  AS  boundary  router  or  to  a  forwarding
        address  specified  by one or more AS external-LSAs changes, all
        forwarding cache  entries  specifying  an  external  network  as
        datagram  source  must be deleted. In this case, potentially all
        inter-AS datagram shortest-path trees have been invalidated. The
        forwarding  cache  entries  should be deleted after the new best
        cost to the AS boundary router/forwarding address has been  cal-
        culated.

14.  Other additions to the OSPF specification

    MOSPF requires some modifications to the  base  OSPF  protocol.  All
    these  modifications are backward-compatible. A router running MOSPF
    will still interoperate with an OSPF router when forwarding  unicast
    traffic.  Most  of  the modifications have been described earlier in
    this document. This section collects together  those  changes  which
    have yet to be mentioned, organizing them by the affected Section of
    [OSPF].

    14.1.  The Designated Router

        This functionality is described in Section  7.3  of  [OSPF].  In
        OSPF,  a  network's Designated Router has two specialized roles.
        First, it originates the network's network-LSA. Second, it  con-
        trols the flooding on the network, in that all of the routers on
        the network synchronize with  the  Designated  Router  (and  the
        backup Designated Router) only.  For these reasons[32], when one
        or more of the network's routers are running MOSPF,  the  Desig-
        nated  Router should be running MOSPF also.  This can be ensured
        by assigning all non-multicast routers the DRPriority of 0.





[Moy]                                                          [Page 76]

Internet Draft        Multicast Extensions to OSPF        September 1992


        In MOSPF, the Designated Router also has the additional  respon-
        sibility of monitoring the network's multicast group membership.
        This is done by periodically sending  Host  Membership  Queries,
        and  receiving  Host Membership Reports in response (see Section
        9). This is yet another reason why the Designated Router must be
        multicast-capable.

    14.2.  Sending Hello packets

        This functionality is described in  Section  9.5  of  [OSPF].  A
        MOSPF  router  sets the MC-bit in the Options field of its Hello
        packets. This indicates that the router is multicast-capable; it
        does  not  necessarily indicate the state of the Hello's sending
        interface's IPMulticastForwarding parameter (see  Section  B.2).
        Setting  the MC-bit in Hellos is done strictly for informational
        purposes. Neighbors receiving the router's Hello packets do  not
        act  on  the  state  of  the  MC-bit.  A  neighbor's  multicast-
        capability is learned instead during the Database Exchange  Pro-
        cess (see Section 14.4).

    14.3.  The Neighbor state machine

        This functionality is described in Section 10.3 of [OSPF].  When
        a  neighbor enters state Exchange, the neighbor Database summary
        list is initialized (see the OSPF neighbor FSM entry for  State:
        ExStart  and Event: NegDone). This list describes of the portion
        of the router's link state database that needs to  be  synchron-
        ized  with  the neighbor.  Group-membership-LSAs are included in
        the neighbor Database summary list if and only if  the  neighbor
        is  multicast-capable.  The  neighbor's  multicast capability is
        learned by examining the neighbor's Database Description packets
        (see Section 14.4).

    14.4.  Receiving Database Description packets

        This functionality is described in Section  10.6  of  [OSPF].  A
        neighbor's  multicast-capability  is  learned  through  received
        Database Description  packets.  When  the  Database  Description
        packet is received that transitions the neighbor from ExStart to
        Exchange, the state of the MC-bit in the packet's Options  field
        is  examined.  The  neighbor is multicast-capable if and only if
        the MC-bit is set.

        The neighbor's  multicast  capability  controls  whether  group-
        membership-LSAs  are summarized to the neighbor during the Data-
        base Exchange process (see Section  14.3),  and  whether  group-
        membership-LSAs  are flooded to the neighbor during the flooding
        process (see Section 10.2).



[Moy]                                                          [Page 77]

Internet Draft        Multicast Extensions to OSPF        September 1992


    14.5.  Sending Database Description packets

        This functionality is described in Section  10.8  of  [OSPF].  A
        MOSPF  router  sets the MC-bit in the Options field of its Data-
        base Description packets. This  indicates  that  the  router  is
        multicast-capable; it does not necessarily indicate the state of
        the Hello's sending interface's IPMulticastForwarding  parameter
        (see  Section  B.2).  Setting the MC-bit in Database Description
        packets indicates the router's multicast-capability to its adja-
        cent neighbors.

        Note that when a router goes  from  being  multicast-capable  to
        multicast-incapable,  or  vice-versa, it must indicate this fact
        to its adjacent neighbors by restarting the Database Description
        process  (i.e., rolling back the state of all adjacent neighbors
        to Exstart).

    14.6.  Originating Router-LSAs

        This functionality is described in Section 12.4.1 of  [OSPF].  A
        MOSPF  router  sets  the  MC-bit  in  the  Options  field of its
        router-LSA. This allows the router to be  included  in  datagram
        shortest-path trees (see Step 4b of Section 12.1).

        In addition, MOSPF has introduced a new flag in the router-LSA's
        rtype  field:  the  W-bit.  When the W-bit is set, the router is
        included on all datagram shortest-path trees, regardless of mul-
        ticast  group  (see  Section  12.2.6). Such a router is called a
        wild-card multicast receiver. The router sets the  W-bit  if  it
        has  been  configured  as an inter-area multicast forwarder (see
        Section 3.1), or as an inter-AS multicast forwarder (see Section
        4).

        A router must originate a new instance of its  router-LSA  when-
        ever  an  event  occurs  that would invalidate the LSA's current
        contents. In particular, if the router's multicast capability or
        its  capability  to  function as either a inter-area or inter-AS
        multicast forwarder  changes,  its  router-LSA  must  be  reori-
        ginated.

    14.7.  Originating Network-LSAs

        This functionality is described in Section 12.4.2 of [OSPF].  In
        OSPF,  a  transit  network's  network-LSA  is  originated by the
        network's Designated Router. The Designated Router sets the  MC-
        bit  in the Options field of the network-LSA if and only if both
        a) the Designated Router  is  multicast-capable  (i.e.,  running
        MOSPF)    and    b)    the   Designated   Router's   interface's



[Moy]                                                          [Page 78]

Internet Draft        Multicast Extensions to OSPF        September 1992


        IPMulticastForwarding parameter has been set to data-link multi-
        cast  (see Section B.2).When the network-LSA has the MC-bit set,
        the network is included in  datagram  shortest-path  trees  (see
        Section 12.2.6).

        It is intended that all routers attached  to  a  common  network
        agree  on  the  network's IPMulticastForwarding capability. How-
        ever, this agreement is not enforced. When there  are  disagree-
        ments, incorrect routing of multicast datagrams can result.

    14.8.  Originating Summary-LSAs

        This functionality is described in  Section  12.4.3  of  [OSPF].
        Inter-area  multicast  forwarders  always  set the MC-bit in the
        Options field of their summary-LSAs, regardless of  whether  the
        path described by the summary-LSA is actually multicast-capable.
        Indeed, it is possible that there is no  multicast-capable  path
        to  the  described  destination.  All  other area border routers
        (ones that are not inter-area multicast  forwarders)  clear  the
        MC-bit in the Options field of their summary-LSAs.

        If its MC-bit is clear, the summary-LSA will not  be  used  when
        initializing  the  candidate list in Sections 12.2.2, 12.2.3 and
        12.2.5.

    14.9.  Originating AS external-LSAs

        This functionality is described in  Section  12.4.4  of  [OSPF].
        Unlike  in  summary-LSAs, an inter-AS multicast forwarder should
        clear the  MC-bit  in  the  Options  field  of  one  of  its  AS
        external-LSAs, if it is known that there is no multicast-capable
        path from the described destination to the router  itself.  This
        knowledge  may possibly be obtained, for example, from an inter-
        AS multicast routing algorithm (see Section 4).  If the inter-AS
        multicast  forwarder  is  unsure  of whether a multicast-capable
        path exists between the described  destination  and  the  router
        itself,  the  MC-bit  should be set in the AS external-LSA.  All
        other AS boundary routers (ones that are not inter-AS  multicast
        forwarders)  clear  the  MC-bit in the Options field of their AS
        external-LSAs.

        If its MC-bit is clear, the AS external-LSA  will  not  be  used
        when initializing the candidate list in Section 12.2.4.

        When multicast connectivity to an external  destination  exists,
        but  no  unicast  connectivity,  an  AS external-LSA can be ori-
        ginated having its MC-bit set and specifying a cost of  LSInfin-
        ity. Such an AS external-LSA will still be used by the multicast



[Moy]                                                          [Page 79]

Internet Draft        Multicast Extensions to OSPF        September 1992


        routing calculation (see Section 12.2.4).

    14.10.  Next step in the flooding procedure

        This functionality is  described  in  Section  13.3  of  [OSPF].
        Group-membership-LSAs  are  specific  to a OSPF single area, and
        are flooded to multicast-capable routers only. When  flooding  a
        group-membership-LSA,  Section 13.3 of the OSPF specification is
        modified as follows: 1) The list of interfaces  examined  during
        flooding  (called  the  eligible  interfaces  in Section 13.3 of
        [OSPF]) is the set of all interfaces attaching to  Area  A  (the
        area  that  the  group-membership-LSA is received from), just as
        for router-LSAs, network-LSAs and summary-LSAs. 2) When  examin-
        ing  each  interface,  a  group-membership-LSA  is  added  to  a
        neighbor's link state retransmission list if and only if both a)
        Step 1d of [OSPF]'s Section 13.3 is reached for the neighbor and
        b) the neighbor is multicast-capable. The  neighbor's  multicast
        capability  is  discovered  during the Database Exchange process
        (see Section 14.4).

        Note that, since on broadcast networks Link  State  Updates  are
        sent  initially as multicasts, non-multicast routers may receive
        group-membership-LSAs. However, non-multicast routers will  sim-
        ply  drop the group-membership-LSAs, for reasons of unrecognized
        LS type (see Step 2 of [OSPF]'s Section  13).  Link  State  ack-
        nowledgments  for  group-membership-LSAs  are  not expected from
        non-multicast routers, and group-membership-LSAs will  never  be
        retransmitted  to  non-multicast routers, since the LSAs are not
        added to these routers' link  state  retransmission  lists  (see
        above paragraph).

        For more information on flooding group-membership-LSAs, see Sec-
        tion 10.2.

    14.11.  Virtual links

        This functionality is described in Section 15 of [OSPF]. When  a
        MOSPF  router  (i.e.,  multicast-capable router) is both an area
        border router and an endpoint of a virtual link whose other end-
        point is also multicast capable, the router must then also be an
        inter-area multicast forwarder. This is necessary to ensure that
        multicast datagrams will flow through the virtual link's transit
        area, from one  endpoint  to  the  other.  When  the  backbone's
        datagram  shortest-path  tree is constructed in Section 12.1, it
        is assumed that virtual links are capable of  forwarding  multi-
        cast datagrams whenever both endpoints are multicast-capable.





[Moy]                                                          [Page 80]

Internet Draft        Multicast Extensions to OSPF        September 1992


15.  References

    [Bharath-Kumar] Bharath-Kumar, K. and Jaffe, J. M. Routing to multi-
                    ple destinations in Computer Networks. IEEE Transac-
                    tions on Communications, COM-31[3], March 1983.

    [Deering]       Deering, S. Multicast Routing in  Internetworks  and
                    Extended  LANs.   SIGCOMM  Summer  1988 Proceedings,
                    August 1988.

    [Deering2]      Deering, S. Multicast routing in a  datagram  inter-
                    network.  Stanford Technical Report STAN-CS-92-1415,
                    Department of Computer Science, Stanford University,
                    December 1991.

    [OSPF]          Moy, J. OSPF Version 2. RFC 1247. July 1991.

    [RFC 1075]      Waitzman, D., Partridge, C. and Deering, S. Distance
                    Vector   Multicast   Routing   Protocol.  RFC  1175,
                    November 1988.

    [RFC 1112]      Deering, S.E.Host extensions  for  IP  multicasting.
                    RFC 1112, May 1988.

    [RFC 1188]      Katz, D. Proposed standard for the  transmission  of
                    IP  datagrams  over FDDI networks. RFC 1188, October
                    1990.

    [RFC 1209]      Piscitello, D.M. Transmission of IP  datagrams  over
                    the SMDS Service.  RFC 1209, March 1991.

    [RFC 1340]      Reynolds, J. and Postel, J.  Assigned  Numbers.  RFC
                    1340, July 1992.


















[Moy]                                                          [Page 81]

Internet Draft        Multicast Extensions to OSPF        September 1992


Footnotes

    [1]Actually, OSPF allows a separate link cost to be  configured  for
    each  TOS. MOSPF then potentially calculates separate paths for each
    TOS. For details, see Section 6.2.

    [2]We also assume in this section  that  the  pictured  multi-access
    networks provide data-link multicast/broadcast services.

    [3]Note that if N3 were a non-broadcast network,  router  RT3  would
    send  separate  copies of the datagram to routers RT1 and RT2. Since
    the IGMP protocol is not defined on  non-broadcast  networks,  there
    could in this case be no group B member attached to network N3. How-
    ever the multicast datagram would still be delivered to the group  B
    members attached to networks N1 and N2.

    [4]Actually, in MOSPF there is a separate forwarding cache entry for
    each combination of source, destination and TOS. For a discussion of
    TOS-based multicast routing, see Section 6.2.

    [5]The discussion in this section omits mention of the Backup Desig-
    nated  Router's  role  in the IGMP protocol. While the Backup Desig-
    nated Router does not send IGMP Host  Membership  Queries,  it  does
    listen  to  IGMP  Host  Membership  Reports, building "shadow" local
    group database entries in the process. These entries do not lead  to
    group-membership-LSAs,  nor  do they influence delivery of multicast
    datagrams, but are merely maintained to  ease  the  transition  from
    Backup Designated Router to Designated Router, should the Designated
    Router fail. See Sections 2.3.4, 9 and 10 for details.

    [6]One might imagine building all  possible  datagram  shortest-path
    trees up front. However, this might be expensive, both in router CPU
    time and in router memory. It is hoped that  building  the  datagram
    shortest-path  trees  on  demand  and  caching the results will ease
    demands on router resources by spreading out the calculations over a
    longer period of time.

    [7]It is possible that, due to the  existence  of  alternate  paths,
    several  different  shortest-path trees are available. MOSPF depends
    on all routers constructing the exact same shortest path  tree.  For
    that  reason, tie-breaking schemes have been implemented during tree
    construction to ensure that identical trees result. See  Section  12
    for more details.

    [8]Note that the expanding ring search yields the nearest server  in
    terms of hop count, not in terms of the OSPF metric.

    [9]This means that in MOSPF, just as in OSPF, the only kind of  link



[Moy]                                                          [Page 82]

Internet Draft        Multicast Extensions to OSPF        September 1992


    state  advertisement  that  can  be  flooded  between  areas  is the
    external-link-LSA.

    [10]A router indicates that it is an inter-area multicast  forwarder
    by  setting the appropriate flag in its router-LSA. See Section 14.6
    for details.

    [11]This is not quite true. As we shall see, any inter-AS  multicast
    forwarders  belonging  to  the  backbone are designated as wild-card
    multicast receivers. See Section 4.

    [12]As with inter-area multicast forwarders, inter-AS multicast for-
    warders  indicate that status by setting a flag in their router-LSA.
    See Section 14.6 for details.

    [13]It is possible that through the operation of an inter-AS  multi-
    cast  routing  protocol, router RT7 knows that it does not have con-
    nectivity to network N15 (even though it has unicast  connectivity).
    In  this  case,  RT7 would not advertise the external link to N15 as
    being multicast capable.

    [14]Synchronization of the IPMulticastForwarding interface parameter
    is  not  enforced by the MOSPF protocol, since it is not included in
    the contents of a MOSPF router's Hello packets.

    [15]Actually, when multiple IP networks have been  assigned  to  the
    same  physical  network, the first thing that needs to be done is to
    associate an IP network with the received  Host  Membership  Report.
    This  is  done in the same way that a receiving interface is associ-
    ated with a received multicast datagram; see Section 11.1.

    [16]For this reason when a transit network has  both  MOSPF  routers
    and  non-multicast  OSPF  routers  attached, care should be taken to
    ensure that a MOSPF router is elected Designated Router. This can be
    accomplished  through  proper  setting  of  the  routers' configured
    Router Priority.

    [17]Note that just because these advertisements exist  in  the  link
    state database, it does not mean that the Group G members are reach-
    able.  Reachability does not enter into the building of the  transit
    vertex  list, in order to simplify the calculation. This is a trade-
    off. As a result, some multicast datagrams may be forwarded  further
    than  necessary,  when  the  described  Group G members actually are
    unreachable.

    [18]Since the Designated Router controls flooding  on  the  network,
    this  is  another reason to ensure that a MOSPF router is elected as
    Designated Router.



[Moy]                                                          [Page 83]

Internet Draft        Multicast Extensions to OSPF        September 1992


    [19]In other words, group-membership-LSAs will never be  retransmit-
    ted to non-multicast routers.

    [20]This last step will not be necessary if the configuration guide-
    lines presented in Section 6.5 are followed.

    [21]The TOS 0 routing table entry is examined regardless of the  TOS
    specified by the multicast datagram.

    [22]This preference ordering is used in Step 5c of Section 12.2.

    [23]No attempt is made to match the links' two halves. See Step 5d.

    [24]However, a summary-LSA is eligible for matching even if the  MC-
    bit in its LS Options field is clear.

    [25]Costs may have both a Type 2 and a Type 1 component; the Type  2
    component is always most significant.

    [26]This case mirrors the SourceIntraArea candidate list initializa-
    tion in Section 12.2.1.

    [27]This case mirrors the SourceInterArea1 candidate list  initiali-
    zation in Section 12.2.2.

    [28]This case mirrors the SourceInterArea2 candidate list  initiali-
    zation in Section 12.2.3.

    [29]Note that selecting the upstream node in  this  manner  enforces
    the inter-area routing architecture outlined in Section 3.1. Namely,
    the multicast datagram is forwarded from the source area,  over  the
    backbone  and  then  into the non-backbone areas. This is similar to
    the "hub and spoke" architecture for unicast forwarding described in
    Section 3.2 of [OSPF].

    [30]This procedure seems backwards. One would expect that the TOS  X
    datagram  tree  would  be  built first. However, the SPF calculation
    must ensure that all routers participating in the forwarding of that
    datagram, both TOS-capable and non-TOS-capable, build the same tree.
    Since it is known that the non-TOS-capable routers will use the  TOS
    0  tree,  the  only  safe  way to use the TOS X tree is when you are
    guaranteed that the non-TOS-capable routers will decline to  forward
    the  datagram.  This  guarantee  is  clearly met when there are only
    TOS-capable routers on the TOS 0 datagram tree.

    [31]Indeed, there will also be those cases  where  the  router,  not
    being  on  a particular datagram shortest-path tree, will never have
    to calculate the particular tree, since the router will not  receive



[Moy]                                                          [Page 84]

Internet Draft        Multicast Extensions to OSPF        September 1992


    the datagram in the first place.

    [32]Group-membership-LSAs are not processed by non-multicast routers
    (see  Section  10.2). Also, if the Designated Router was not running
    the multicast extensions, multicast datagrams will not be  forwarded
    over  the network because its network-LSA will have its MC-bit clear
    (see Step 4a in Section 12.1).












































[Moy]                                                          [Page 85]

Internet Draft        Multicast Extensions to OSPF        September 1992


A. Data Formats

    This section documents the format of MOSPF protocol packets and link
    state  advertisements  (LSAs). All changes and additions made to the
    OSPF version 2 data formats have been made in a  backward-compatible
    manner.  In other words, multicast routers running MOSPF can intero-
    perate with (non-multicast) OSPF version 2 routers  when  forwarding
    regular (unicast) IP data traffic.

    The MOSPF packet  formats  are  the  same  as  for  OSPF  version  2
    (described  in Appendix A of [OSPF]). One additional option has been
    added to the Options field that appears in OSPF Hello Packets, Data-
    base Description packets and all link state advertisements. This new
    option indicates the router's multicast  capability,  and  is  docu-
    mented  in  Section A.1.  The presence of this new option is ignored
    by all non-multicast routers.

    To support MOSPF, one of OSPF's link state advertisements  has  been
    modified,  and  a  new  link state advertisement has been added. The
    format of the router-LSA has  been  updated  (see  Section  A.2)  to
    include a new flag indicating whether the router is a wild-card mul-
    ticast receiver. A new link state advertisement, called  the  group-
    membership-LSA,  has  been added to pinpoint multicast group members
    in the link  state  database.  This  new  advertisement  is  neither
    flooded   nor   processed   by  non-multicast  routers.  The  group-
    membership-LSA is documented in Section A.3.

























[Moy]                                                          [Page 86]

Internet Draft        Multicast Extensions to OSPF        September 1992


A.1 The options field

    The OSPF options field is present in OSPF  Hello  packets,  Database
    Description  packets  and all link state advertisements. The options
    field enables OSPF routers to  support  (or  not  support)  optional
    capabilities,  and  to  communicate  their capability level to other
    OSPF routers. Through this mechanism routers of differing  capabili-
    ties can be mixed within an OSPF routing domain.

    When used in Hello packets, the options field  allows  a  router  to
    reject  a  neighbor because of a capability mismatch. Alternatively,
    when capabilities are exchanged in Database  Description  packets  a
    router  can  choose  not  to forward certain LSA types to a neighbor
    because of its reduced functionality. Lastly,  listing  capabilities
    in LSAs allows routers to route traffic around reduced functionality
    routers, by excluding them from parts of the routing table  calcula-
    tion.

    Three capabilities are currently defined. For each  capability,  the
    effect  of  the  capability's  appearance (or lack of appearance) in
    Hello packets, Database Description packets and  link  state  adver-
    tisements  is  specified  below.  For  example, the external routing
    capability (below called the E-bit) has meaning only in  OSPF  Hello
    Packets.

                     +---+---+---+---+---+---+---+---+
                     | * | * | * | * | * |MC | E | T |
                     +---+---+---+---+---+---+---+-+-+

                          The OSPF options field


    o   T-bit. This describes the router's TOS capability. If the  T-bit
        is  reset,  then  the router supports only a single TOS (TOS 0).
        Such a router is also said to be incapable of  TOS-routing.  The
        absence  of the T-bit in a router links advertisement causes the
        router to be skipped when building a non-zero TOS  shortest-path
        tree.  In  other words, routers incapable of TOS routing will be
        avoided  as  much  as  possible  when  forwarding  data  traffic
        requesting a non-zero TOS. The absence of the T-bit in a summary
        link advertisement or an AS external  link  advertisement  indi-
        cates  that  the  advertisement is describing a TOS 0 route only
        (and not routes for non-zero TOS).

    o   E-bit. Type 5 AS external link advertisements  are  not  flooded
        into/through OSPF stub areas. The E-bit ensures that all members
        of a stub area agree on that area's configuration. The E-bit  is
        meaningful  only  in OSPF Hello packets. When the E-bit is reset



[Moy]                                                          [Page 87]

Internet Draft        Multicast Extensions to OSPF        September 1992


        in the Hello packet sent out a particular  interface,  it  means
        that the router will neither send nor receive type 5 AS external
        link state advertisements on that interface (in other words, the
        interface  connects to a stub area). Two routers will not become
        neighbors unless they agree on the state of the E-bit.

    o   MC-bit. The MC-bit describes the  multicast  capability  of  the
        various  pieces of the OSPF routing domain. When calculating the
        path of multicast datagrams, only those  link  state  advertise-
        ments  having  their  MC-bit set are used. In addition, a router
        uses the MC-bit in its Database Description packets in order  to
        tell  adjacent  neighbors whether the router will participate in
        the flooding of the new group-membership-LSAs.






































[Moy]                                                          [Page 88]

Internet Draft        Multicast Extensions to OSPF        September 1992


A.2 Router-LSA

    An OSPF router originates a router-LSA into  each  of  its  attached
    areas.  The  router-LSA describes the state and cost of the router's
    interfaces to the area. The contents of the router-LSA are described
    in  detail  in  Section  A.4.2  of  [OSPF].  There  are flags in the
    router-LSA that indicate whether the router is  either  a)  an  area
    border  router  or  b) an AS boundary router or c) the endpoint of a
    virtual link. One more flag has been added  to  the  router-LSA  for
    MOSPF;  it  is  called  bit W below. This flag indicates whether the
    router receives all multicast datagrams  regardless  of  destination
    (i.e., is a wild-card multicast receiver).

        0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |            LS age             |     Options   |       1       |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                        Link State ID                          |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                     Advertising Router                        |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                     LS sequence number                        |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |         LS checksum           |             length            |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |    rtype      |        0      |            # links            |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
       |                          Link ID                              | P
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ E
       |                         Link Data                             | R
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |     Type      |     # TOS     |        TOS 0 metric           | #
     + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ L
     # |      TOS      |        0      |            metric             | I
     T +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ N
     O |                              ...                              | K
     S +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ S
     | |      TOS      |        0      |            metric             | |
     + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
       |                              ...                              |

                                The router LSA








[Moy]                                                          [Page 89]

Internet Draft        Multicast Extensions to OSPF        September 1992


                     +---+---+---+---+---+---+---+---+
                     | * | * | * | * | W | V | E | B |
                     +---+---+---+---+---+---+---+-+-+

                                The rtype field

    The following defines the flags found in the rtype field. Each  flag
    classifies the router by function:

    o   bit B. When set, the router is an area border router (B  is  for
        border). These routers forward unicast data traffic between OSPF
        areas.

    o   bit E. When set, the router is an AS boundary router (E  is  for
        external).  These  routers  forward unicast data traffic between
        Autonomous Systems.

    o   bit V. When set, the router is an endpoint of an active  virtual
        link  (V  is  for  virtual) which uses the described area as its
        transit area.

    o   bit W. When set, the router is a wild-card  multicast  receiver.
        These  routers  receive  all  multicast datagrams, regardless of
        destination.  Inter-area multicast forwarders and inter-AS  mul-
        ticast  forwarders are always wild-card multicast receivers (see
        Sections 3 and 4).

























[Moy]                                                          [Page 90]

Internet Draft        Multicast Extensions to OSPF        September 1992


A.3 Group-membership-LSA

    Group-membership-LSAs are the  type  6  link  state  advertisements.
    Group-membership-LSAs  are  specific to a particular OSPF area. They
    are never flooded beyond  their  area  of  origination.  A  router's
    group-membership-LSA  for  Area  A indicates those directly attached
    networks belonging to Area A and containing members of a  particular
    multicast group. A router originates a group-membership-LSA for mul-
    ticast group D when the following conditions are met  for  at  least
    one directly attached network: 1) the router has been elected Desig-
    nated Router for the network and 2) at least one host on the network
    has joined Group D via the IGMP protocol.

    A router may also originate a group-membership-LSA for  Group  D  if
    the router itself has internal applications belonging to Group D. In
    addition, area border routers  originate  group-membership-LSAs  for
    the  backbone  area  when  there  are  group members in the router's
    attached non-backbone areas. See Section  10  for  more  information
    concerning the origination of group-membership-LSAs.

        0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |            LS age             |     Options   |       6       |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |              Link State ID = Destination Group                |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                     Advertising Router                        |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                     LS sequence number                        |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |         LS checksum           |             length            |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                        Vertex type                            |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                         Vertex ID                             |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                              ...                              |

                           The group-membership-LSA


    The group-membership-LSA consists of the standard 20-byte link state
    header  (see  Section A.4.1 of [OSPF]) followed by a list of transit
    vertices   to   label   with   the   multicast   destination.    The
    advertisement's  Link  State  ID is set to the multicast destination
    group address. There is no metric associated with the advertisement.
    Each  transit  vertex  is specified by its Vertex type and Vertex ID



[Moy]                                                          [Page 91]

Internet Draft        Multicast Extensions to OSPF        September 1992


    (see Section 16.1 of [OSPF] for an explanation of this terminology):

    o   Vertex type. Set equal to 1 for a router, and 2  for  a  transit
        network.   Note that the only router that may be included in the
        list is the Advertising Router itself.

    o   Vertex  ID.  For  router  vertices,  this  field  indicates  the
        router's  OSPF  router  ID.  For  transit network vertices, this
        field indicates the  IP  address  of  the  network's  Designated
        Router.  Note  that the link state advertisement associated with
        the transit vertex is the LSA whose LS type = Vertex type,  Link
        State  ID  =  Vertex  ID  and  Advertising  Router  = the group-
        membership-LSA's Advertising Router.






































[Moy]                                                          [Page 92]

Internet Draft        Multicast Extensions to OSPF        September 1992


B. Configurable Constants

    This section documents the configurable parameters  used  by  OSPF's
    multicast  routing  extensions.  These parameters are in addition to
    the configurable constants used by the  base  OSPF  protocol  (docu-
    mented  in  Appendix  C  of [OSPF]). An implementation of MOSPF must
    provide the ability to set these parameters, either through  network
    management or some other means.

    B.1 Global parameters

        The following parameters apply to the router as a whole.

        o   Multicast capability. An indication of whether the router is
            running  MOSPF. If the router is running MOSPF, it will per-
            form the algorithms as set forth in this specification. Oth-
            erwise, the router is still able to run the basic OSPF algo-
            rithm (as set forth in [OSPF]), and will be able to  intero-
            perate with multicast capable routers (see Section 6.1) when
            forwarding regular (unicast) IP data traffic.

        o   Inter-area multicast  forwarder.  This  parameter  indicates
            whether  the router will forward multicast datagrams between
            OSPF areas. Such a router summarizes group membership infor-
            mation  to  the  backbone, and acts as a wild-card multicast
            receiver in all its attached non-backbone areas (see Section
            3.1).  Not all multicast-capable area border routers need be
            configured as  inter-area  multicast  forwarders.   However,
            whenever  both ends of a virtual link are multicast-capable,
            they must both be configured as  inter-area  multicast  for-
            warders  (see  Section  14.11).  By  default, all multicast-
            capable area border routers  are  configured  as  inter-area
            multicast forwarders.

        o   Inter-AS  multicast  forwarder.  This  parameter   indicates
            whether  the  router  forwards  multicast  datagrams between
            Autonomous Systems. Such a router acts as a wild-card multi-
            cast  receiver  in all attached areas (see Section 4). It is
            also assumed that an inter-AS multicast forwarder runs  some
            kind of inter-AS multicast routing algorithm.

    B.2 Router interface parameters

        The following parameters can be configured separately  for  each
        of the router's OSPF interfaces. Remember that an OSPF interface
        is the connection between the router and one of its attached  IP
        networks.   Note  that  the  IPMulticastForwarding  parameter is
        really a description of the attached network. As such, it should



[Moy]                                                          [Page 93]

Internet Draft        Multicast Extensions to OSPF        September 1992


        be  configured  identically  on all routers attached to a common
        network; otherwise incorrect routing of multicast datagrams  may
        result.

        o   IPMulticastForwarding. This configurable parameter indicates
            whether  IP multicasts should be forwarded over the attached
            network, and if so, how the forwarding should be  done.  The
            parameter can assume one of three possible values: disabled,
            data-link multicast and data-link unicast. When set to  dis-
            abled,  IP multicast datagrams will not be forwarded out the
            interface. When set to  data-link  multicast,  IP  multicast
            datagrams  will  be  forwarded as data-link multicasts. When
            set to data-link unicast, IP  multicast  datagrams  will  be
            forwarded  as data-link unicasts. The default value for this
            parameter is data-link multicast. The other two settings are
            for  use  in the special circumstances described in Sections
            6.3 and 6.4. When set to disabled or to  data-link  unicast,
            IGMP  group membership is not monitored on the attached net-
            work.

        o   IGMPPollingInterval. The  number  of  seconds  between  IGMP
            membership  queries  sent  out  this interface. A multicast-
            capable router sends IGMP membership queries  only  when  it
            has been elected Designated Router for the attached network.
            See [RFC 1112] for a discussion of this parameter's value.

        o   IGMP timeout. If no IGMP membership reports have been  heard
            on  an  attached  network for a particular multicast group A
            after this period of time, the entry [Group A, attached net-
            work] is deleted from the router's local group database. See
            Section 9 for more information.




















[Moy]                                                          [Page 94]

Internet Draft        Multicast Extensions to OSPF        September 1992


C. Sample datagram shortest-path trees

    In MOSPF, all routers  must  calculate  exactly  the  same  datagram
    shortest-path trees. In order to ensure this in internetworks having
    redundant links, a number of tie-breakers were defined in the  MOSPF
    routing  table  calculation (see Steps 4 and 5c of Section 12.2, and
    Sections 12.2.4 and 12.2.7). This section  illustrates  the  use  of
    these tie-breakers on a sample topology.

    Three different examples are given. All examples use the same physi-
    cal  topology and the same set of OSPF interface costs (see the left
    side of Figure 14). The source of the datagram is always Host H1  on
    the  network  at the top of the figure (192.9.1.0), and the destina-
    tion group members are the two hosts labelled with Group Ma  at  the
    bottom  of the figure. The first case shows an example of intra-area
    multicast, while the remaining two cases show the influence of  OSPF
    areas on the path of a multicast datagram.


































[Moy]                                                          [Page 95]

Internet Draft        Multicast Extensions to OSPF        September 1992


C.1 An intra-area tree

    The datagram shortest-path tree resulting from the  intra-area  case
    is  shown  on  the  right  of Figure 14. The root of the tree is the
    source network (192.9.1.0), and the leaves are the two routers  (RT3
    and  RT5) directly attached to the stub networks containing Group Ma
    members.

    There are equal-cost paths available to both group members. For  the
    group  member  on the left, the path could go either through network
    10.1.0.0 or through network 10.2.0.0. By the tie-breaking rules, the
    path  through  10.2.0.0  is  chosen  since it has the larger Network
    number (see Step 5c of Section 12.2).

    For the group member on the right, the path  could  go  either  over
    Network  10.2.0.0 or over the serial line connecting routers RT2 and
    RT3. The path over Network 10.2.0.0 is chosen  after  executing  two
    tie-breaking  rules.  First,  Network  10.2.0.0  is  placed  on  the
    shortest-path tree before  router  RT3  since  networks  are  always
    chosen  over  routers  (see  Step  4 of Section 12.2). Then, given a

                                 +--+
                                 |H1|
                                 +--+
                    Net 192.9.1.0  |
                         +------------------+
                            |            |
        +----------+        |1           |1
        |  Network |     8+---+        +---+            o 192.9.1.0
        | 10.1.0.0 |------|RT1|        |RT2|            |
        +----------+      +---+        +---+           0|
             |              |8          8|              |
            8|         +----------+      |8             o RT1
           +---+10     | Network  |  10+---+            |
           |RT4|-------| 10.2.0.0 |----|RT3|           8|
           +---+       +----------+    +---+            |
             |3                          |3             o 10.2.0.0
             |                           |             / \
        +---------+                  +-------+       0/   \0
             |                           |           /     \
           +--+                        +--+         o       o
           |Ma|                        |Ma|        RT4      RT3
           +--+                        +--+


                        Figure 14: An intra-area tree





[Moy]                                                          [Page 96]

Internet Draft        Multicast Extensions to OSPF        September 1992


    choice of either Network 10.2.0.0 or Router RT2 for RT3's parent  on
    the tree, Net 10.2.0.0 is again preferred since it is a network (see
    Step 5c of Section 12.2)
















































[Moy]                                                          [Page 97]

Internet Draft        Multicast Extensions to OSPF        September 1992


C.2 The effect of areas

    In Figure 15 below, the previous diagram has been  modified  by  the
    inclusion of OSPF areas. The datagram source is now part of the OSPF
    backbone (Area 0), while the rest of the topology is in Area  1.  In
    this case, since the datagram source and the group members belong to
    different areas, reverse costs are used when building the tree  (see
    Step  5b  of  Section 12.2). This actually eliminates the equal cost
    paths from the diagram, and leads to the Area 1  datagram  shortest-
    path tree on the right of Figure 15.











                                 +--+
                                 |H1|
                                 +--+
                    Net 192.9.1.0  |
                         +------------------+
      ..................... |            |
      . +----------+      . |1           |1            192.9.1.0
      . |  Network |     8+---+        +---+                o
      . | 10.1.0.0 |------|RT1|........|RT2|...            / \
      . +----------+      +---+        +---+  .          1/   \1
      .      |              |8          8|    .          /     \
      .     8|         +----------+      |8   .         o RT1   o RT2
      .    +---+10     | Network  |  10+---+  .         |        \
      .    |RT4|-------| 10.2.0.0 |----|RT3|  .        0|         \8
      .    +---+       +----------+    +---+  .         |          \
      .      |3                          |3   .         o 10.1.0.0  o
      .      |                           |    .         |          RT3
      . +---------+                  +-------+.        8|
      .      |                           |    .         |
      .    +--+                        +--+   .         o
      .    |Ma|                        |Ma|   .        RT4
      .    +--+     Area 1             +--+   .
      .........................................

                        Figure 15: The effect of areas





[Moy]                                                          [Page 98]

Internet Draft        Multicast Extensions to OSPF        September 1992


C.3 The effect of virtual links

    In Figure 16 below,  Network  10.1.0.0  has  been  configured  as  a
    separate  area  (Area  1), while everything else belongs to the OSPF
    backbone (Area 0). In addition, a virtual link has  been  configured
    through  Area  1, enhancing the backbone connectivity. In this case,
    both the source and the group members belong to the  same  area,  so
    forward  costs  are used. However, since virtual links are preferred
    over regular links (see Step  5c  of  Section  12.2),  the  backbone
    datagram   shortest-path  tree  uses  Network  10.1.0.0  instead  of
    10.2.0.0 on the path to the left group member.  This  leads  to  the
    tree on the right of Figure 16.









                                 +--+
                                 |H1|
                                 +--+
                    Net 192.9.1.0  |
      ................   +------------------+
      . +----------+ .     /1            |
      . |  Network |8.    /              |1
      . | 10.1.0.0 |-+---+             +---+            o 192.9.1.0
      . +----------+*|RT1|             |RT2|            |
      .     8|*******+---+             +---+           0|
      .Area1 |*VL    .    \8            8|              |
      .....+---+...... +----------+      |8             o RT1
           |RT4|10     | Network  |  10+---+           / \
           +---+-------| 10.2.0.0 |----|RT3|          /8  \8
             |         +----------+    +---+         /     \
             |3                          |3         o 10.1  o 10.2.0.0
             |                           |          |       |
        +---------+                  +-------+      |0      |0
             |                           |          |       |
           +--+                        +--+         o       o
           |Ma|                        |Ma|        RT4      RT3
           +--+                        +--+


                        Figure 14: An intra-area tree





[Moy]                                                          [Page 99]

Internet Draft        Multicast Extensions to OSPF        September 1992


Security Considerations

    Security issues are not discussed in this memo.

Author's Address

    John Moy
    Proteon, Inc.
    2 Technology Drive
    Westborough, MA 01581
    Phone: (508) 898-2800
    Email: jmoy@proteon.com

    This document expires in February 1993.





































[Moy]                                                         [Page 100]


Html markup produced by rfcmarkup 1.107, available from http://tools.ietf.org/tools/rfcmarkup/