tech-invite   World Map     

3GPP     Specs     Glossaries     Architecture     IMS     UICC       IETF     RFCs     Groups     SIP     ABNFs       Search

RFC 1584

 
 
 

Multicast Extensions to OSPF

Part 3 of 4, p. 52 to 76
Prev RFC Part       Next RFC Part

 


prevText      Top      Up      ToC       Page 52 
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
    configuration options (e.g., the IPMulticastForwarding interface
    parameter) 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
    internal applications) are handled instead by the algorithm in
    Section 11.3.

Top      Up      ToC       Page 53 
    Assume that the datagram's IP destination is Group G. The forwarding
    process then consists of the following steps:

    (1) Upon reception of the datagram, the MOSPF router notes the
        following 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
            information 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
        application that has joined Group G 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
        forwarding 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.

    (4) If Group G falls into 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 for use on a local network
        segment only.

    (5) Associate a source network (SourceNet) with the multicast
        datagram, as described in Section 11.2. If SourceNet 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 [SourceNet, Group G, 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:

Top      Up      ToC       Page 54 
        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
        parameter is set to data-link unicast, the datagram should be
        forwarded 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 Group G 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
        forwarding 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
        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
            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 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 1390] 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.

Top      Up      ToC       Page 55 
        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
        forwarding 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
        processed (see Section 9.2).

        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
        interface is then the remaining interface having the highest IP
        interface address (or NULL if there are no remaining
        interfaces)[19].

    11.2.  Locating the source network

        MOSPF forwarding cache entries are indexed by 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
        accomplished by the following algorithm:

Top      Up      ToC       Page 56 
        Look up the OSPF TOS 0 routing table entry[20] corresponding to
        the 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 routing table entry specifies an external route, or there is
        no matching routing table entry), the list of matching AS
        external-link-LSAs is examined. A matching AS external-link-LSA
        is one that describes a network which contains the datagram's IP
        source address. The list of matching AS external-link-LSAs is
        pruned in the following steps to determine the source network:

        (1) Those AS external-link-LSAs with MC-bit clear (see Section
            A.1), or with LS age set to MaxAge, or which have been
            originated by unreachable AS boundary routers are discarded.

        (2) AS external-link-LSAs specifying Type 1 external metrics are
            always preferred over those specifying Type 2 external
            metrics.

        (3) If there are still multiple AS external-link-LSAs remaining,
            those specifying the best matching (i.e., most specific)
            network are selected. The source network is then set to the
            network/subnet/supernet (possibly even the default route)
            described by the best matching AS external-link-LSAs. Note
            that AS external-link-LSAs specifying a cost of LSInfinity
            are eligible for this best match, as long as their MC-bit is
            set.[21]

        It is possible that two different MOSPF routers may calculate
        the same multicast datagram's source network differently. For
        example, consider the network configuration shown in Figure 4.
        When calculating the source network for a datagram whose source
        is Network N10 and destination is Group Ma, Router RT11 would
        calculate the source network as Network N10 itself, while Router
        RT10 would calculate the source network as the aggregate of
        Networks N9-N11 and Host H1 (advertised in a single summary-
        link-LSA by Router RT11). However, despite the possibility of
        routers selecting different source networks, all routers will
        still agree on the datagram's shortest-path tree.

        External sources are treated differently in the above
        calculation 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-link-LSAs and the above use of
        the LSInfinity metric (to indicate a route that is to be used

Top      Up      ToC       Page 57 
        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.

        As an example of the logic for external sources, suppose a
        multicast datagram is received having the IP source address
        10.1.1.1. Suppose also that the three AS external-link-LSAs
        shown in Table 3 are in the router's OSPF database. The OSPF
        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
        consists 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
            multicasting specified in [RFC 1112].

        (2) If the router interface found in the previous step has been
            configured for MOSPF, and if its IPMulticastForwarding
            parameter is not equal to disabled, then set the receiving
            MOSPF interface to that interface.  Otherwise, set the
            receiving MOSPF interface to NULL.

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


         Network    Mask            Cost                 MC-bit
         ______________________________________________________
         10.1.1.0   255.255.255.0   Type 1: 10           clear
         10.1.0.0   255.255.0.0     Type 2: LSInfinity   set
         10.0.0.0   255.0.0.0       Type 2: 1            set


                 Table 3: Sample AS external-link-LSAs

Top      Up      ToC       Page 58 
        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,
        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
        network to SourceNet, its Destination multicast group to Group G
        and its IP TOS field to match the multicast datagram's TOS.
        Initialize 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
            calculation 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 calculation 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.

Top      Up      ToC       Page 59 
        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
            initially set to NULL. After completing Area A's datagram
            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
        calculating 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
        following state information attached to it. Basically, this
        information indicates the current best path from the SourceNet
        to the vertex, and the position of the vertex relative to the
        calculating 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.

Top      Up      ToC       Page 60 
        o   Parent. In the current best path from SourceNet to the
            vertex, 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
            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
            summary 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
            external type 2 and internal OSPF metrics, that the vertex'
            cost parameter reflects both cost components. Remember that
            the 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

Top      Up      ToC       Page 61 
        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
        vertices to which paths have been discovered, but for which the
        optimality of the discovered 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 G are inputs to the calculation (see Step 6 of Section
        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
        calculations 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 LS age equal to 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
            shortest-path tree.  Initialize the state of each vertex in
            Area A (i.e., the area's routers and transit networks) to:
            Parent set to NULL, IncomingLinkType set to ILNone and
            AssociatedInterface/Neighbor set to NULL.

        (2) Initialize the candidate list. One or more vertices are
            initially placed on the candidate list, depending on the
            location 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
                Section 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.

Top      Up      ToC       Page 62 
            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.

            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
                Section 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
                Section 12.2.5.

            Two different routers in Area A may select different
            initialization 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
            SourceInterArea1. Likewise, if Area 3 were configured as an
            OSPF stub area and the datagram source was the external
            Network N12, 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
            candidate list (and in fact, run the rest of the SPF
            calculation) identically.

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

        (4) Move the 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
            remaining, select the vertex having the highest Vertex ID.
            Call the chosen vertex Vertex V. Remove Vertex V from the
            candidate 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
            forwarding cache entry's list of outgoing
            interfaces/neighbors to be updated. See Section 12.2.6 for
            details.

Top      Up      ToC       Page 63 
        (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:

            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
                SourceIntraArea 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,
                modifying its parameters as specified below (Step 5d).
                Otherwise, W is on the candidate list already. In this
                case, if:

                o   C is less than W's current Cost, update W's
                    parameters 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
                    compared to W's current IncomingLinkType, and
                    whichever link has the preferred type is chosen (the
                    preference 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

Top      Up      ToC       Page 64 
                    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 modified as below (Step 5d). Whenever the
                    previously discovered link is chosen, the next link
                    in V's LSA is examined instead.

                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
                IncomingLinkType 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
                according to one of the following cases:

                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 the calculating router
                    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. However, 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, the calculating router is free to pick
                    the sending interface when there are multiple
                    connecting links.

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

                o   V is a transit network, and is directly downstream
                    from the calculating router (i.e., V's
                    AssociatedInterface/Neighbor is non-NULL and V's TTL
                    is set to 1). W is then one of the calculating
                    router's neighbors. In this case, W's TTL parameter
                    is also set to 1. If network V has been configured

Top      Up      ToC       Page 65 
                    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 Network V.

                o   Vertex V is downstream from the calculating router
                    (i.e., V's AssociatedInterface/Neighbor is non-
                    NULL), 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
                    directly from V.  If V is a router, W's TTL
                    parameter 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
        Section 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.  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
            SourceNet 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

Top      Up      ToC       Page 66 
            calculating the Area 2 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 RT8. As another example, the datagram shortest-
            path tree pictured in Figure 3 is really rooted at Router
            RT3 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).  The
            candidate list is then initialized as follows. Examine the
            Area A summary-link-LSAs advertising SourceNet. For each
            such summary-link-LSA: if both a) the MC-bit is set in the
            LSA's Options field and b) the advertised 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.

            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
            calculating router (RTX).  The candidate list is then
            initialized in the following two steps:

            (1) Find the Area A summary-link-LSA that best matches
                SourceNet, excluding those summary-link-LSAs specifying
                cost LSInfinity or having unreachable Advertising
                Routers[24].  A matching summary-link-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 network described by the best
                matching summary-link-LSA.

Top      Up      ToC       Page 67 
            (2) Similar to the logic in the SourceInterArea1 case,
                examine all the Area A summary-link-LSAs which advertise
                SourceRange. For each such summary-link-LSA: if both a)
                the MC-bit is set in the LSA's Options field, b) the
                advertised cost is not equal to LSInfinity and c) the
                Advertising Router is reachable, then the vertex
                representing the LSA's Advertising 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
            boundaries. 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
            SourceRange 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-
            link-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.  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 parameter it
            would be added with is better[25] (closer to SourceNet) than
            its previous value. When the costs are the same, W's
            parameters are still modified if the IncomingLinkType it
            would be added with is better (see IncomingLinkType's
            definition in Section 12.1) than its previous value.

Top      Up      ToC       Page 68 
            For each AS external-link-LSA advertising SourceNet, the
            following steps are performed:

            o   If the AS external-link-LSA's MC-bit is clear or if its
                advertising router is not reachable, then the AS
                external-link-LSA is not used. AS external-link-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-link-LSA's Forwarding address field
                is 0.0.0.0, the following vertices are added to the
                candidate 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-link-LSAs for ASBR are added to the candidate
                list. Each such area border router is added with the
                parameters: IncomingLinkType set to ILSummary, Cost to
                the sum of whatever is advertised in the type 4
                summary-link-LSA plus the value in the original AS
                external-link-LSA, Parent to NULL and
                AssociatedInterface/Neighbor to NULL.

            o   If the AS external-link-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
                    Forwarding address is not usable if either it has no
                    matching routing table entry, or if the matching
                    routing table entry is neither of type intra-area
                    nor of type inter-area.

                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

Top      Up      ToC       Page 69 
                    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-link-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-link-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-link-LSA plus the value in the original AS
                    external-link-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
                    matching routing table entry ForwardNet. First find
                    the Area A summary-link-LSA that best matches
                    ForwardNet, excluding those summary-link-LSAs
                    specifying cost LSInfinity or having unreachable
                    Advertising Routers. Let ForwardRange be the network
                    described by the best matching summary-link-LSA.
                    Then, for each reachable multicast-capable summary-
                    link-LSA (in Area A) advertising ForwardRange, 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-link-LSA plus the value in
                    the original AS external-link-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
            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

Top      Up      ToC       Page 70 
            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
            concatenation of the Type 4 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 external link, IncomingLinkType set to ILExternal
            otherwise, Cost set to the cost of the shortest path from
            vertex to SourceNet, 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
            initialized 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
            SourceStubExternal

            In this case, SourceNet is external to the OSPF routing
            domain, and Area A is an OSPF stub area.  The candidate list
            is then initialized similarly to case SourceInterArea1. The
            Area A summary-link-LSAs advertising DefaultDestination are
            examined. For each such summary-link-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.

            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:

Top      Up      ToC       Page 71 
            (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 may be true when 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 4
            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
            complete, the calculating router (RTX) must decide whether
            Area A, out of all of its attached areas, determines the
            forwarding cache entry's upstream node.  This is done by
            examining RTX's position on the Area A datagram shortest-
            path tree, which is in turn described by RTX's Area A Vertex
            data structure. If RTX's Vertex parameter 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 following 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:

Top      Up      ToC       Page 72 
            o   Choose the area that is "nearest to the source". Nearest
                to the source depends on each area's candidate list
                initialization 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
                initialization 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 SourceInterArea2) 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
                comparison 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
            forwarding 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 to the placeholder EXTERNAL.

        12.2.8.  TOS considerations

            The previous sections 12.2 through 12.2.7 described the
            construction 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

Top      Up      ToC       Page 73 
            the routers on the pruned tree are TOS-capable, a separate
            TOS X datagram shortest-path tree is calculated[30].
            Otherwise, 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.2's tree calculation:

            o   A new piece of state information is added to each
                vertex: 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
                recalculated when/if the vertex' position on the
                candidate list is modified (see Section 12.2'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
            algorithm in Section 12.2 is used, with the modifications
            listed below.

            o   When calculating RangeNet and ForwardRange in Sections
                12.2.3 and 12.2.4 respectively, only summary-link-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 vertices' Cost parameter.

Top      Up      ToC       Page 74 
            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 cost.

            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
            differences. 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
                calculation 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 2, 4 and 5b of
                Section 12.2.

            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.

Top      Up      ToC       Page 75 
            o   While both the multicast and unicast trees select
                shortest 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 implementation of IP multicast's "expanding
                ring search" (see Section 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-
                link-LSAs and AS external-link-LSAs, which sometime form
                the base of the multicast datagram shortest-path trees,
                are specified in the reverse direction (from the
                multicast perspective).

            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 always used, only falling back on the TOS 0
                paths when a TOS X path does not exist.

    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
        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
        interfaces. All local group database entries having Group G as
        MulticastGroup 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

Top      Up      ToC       Page 76 
        N interface was already present in the list of outgoing
        interfaces, 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
        Network 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 its list of downstream
        interfaces.



(page 76 continued on part 4)

Next RFC Part