rfc1583.txt

<VC++网络游戏建摸与实现>源代码

Moy                                                            [Page 15]

RFC 1583                     OSPF Version 2                   March 1994


                     **FROM**                       **FROM**

                  |RT12|N9|N10|H1|             |RT9|RT11|RT12|N9|
           *  --------------------          *  ----------------------
           *  RT12|    |  |   |  |          *   RT9|   |    |    |0 |
           T    N9|1   |  |   |  |          T  RT11|   |    |    |0 |
           O   N10|2   |  |   |  |          O  RT12|   |    |    |0 |
           *    H1|10  |  |   |  |          *    N9|   |    |    |  |
           *                                *
                RT12's router links            N9's network links
                   advertisement                  advertisement

                  Figure 4: Individual link state components

              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.

        identical graphical representation.  A router generates its
        routing table from this graph by calculating a tree of shortest
        paths with the router itself as root.  Obviously, the shortest-
        path tree depends on the router doing the calculation.  The
        shortest-path tree for Router RT6 in our example is depicted in
        Figure 5.

        The tree gives the entire route to any destination network or
        host.  However, only the next hop to the destination is used in
        the forwarding process.  Note also that the best route to any
        router has also been calculated.  For the processing of external
        data, we note the next hop and distance to any router
        advertising external routes.  The resulting routing table for
        Router RT6 is pictured in Table 2.  Note that there is a
        separate route for each end of a numbered serial line (in this
        case, the serial line between Routers RT6 and RT10).


        Routes to networks belonging to other AS'es (such as N12) appear
        as dashed lines on the shortest path tree in Figure 5.  Use of
        this externally derived routing information is considered in the
        next section.


    2.2.  Use of external routing information

        After the tree is created the external routing information is
        examined.  This external routing information may originate from
        another routing protocol such as EGP, or be statically



Moy                                                            [Page 16]

RFC 1583                     OSPF Version 2                   March 1994



                                RT6(origin)
                    RT5 o------------o-----------o Ib
                       /|\    6      |\     7
                     8/8|8\          | \
                     /  |  \         |  \
                    o   |   o        |   \7
                   N12  o  N14       |    \
                       N13        2  |     \
                            N4 o-----o RT3  \
                                    /        \    5
                                  1/     RT10 o-------o Ia
                                  /           |\
                       RT4 o-----o N3        3| \1
                                /|            |  \ N6     RT7
                               / |         N8 o   o---------o
                              /  |            |   |        /|
                         RT2 o   o RT1        |   |      2/ |9
                            /    |            |   |RT8   /  |
                           /3    |3      RT11 o   o     o   o
                          /      |            |   |    N12 N15
                      N2 o       o N1        1|   |4
                                              |   |
                                           N9 o   o N7
                                             /|
                                            / |
                        N11      RT9       /  |RT12
                         o--------o-------o   o--------o H1
                             3                |   10
                                              |2
                                              |
                                              o N10


                     Figure 5: The SPF tree for Router RT6

              Edges that are not marked with a cost have a cost of
              of zero (these are network-to-router links). Routes
              to networks N12-N15 are external information that is
                         considered in Section 2.2











Moy                                                            [Page 17]

RFC 1583                     OSPF Version 2                   March 1994


                   Destination   Next  Hop   Distance
                   __________________________________
                   N1            RT3         10
                   N2            RT3         10
                   N3            RT3         7
                   N4            RT3         8
                   Ib            *           7
                   Ia            RT10        12
                   N6            RT10        8
                   N7            RT10        12
                   N8            RT10        10
                   N9            RT10        11
                   N10           RT10        13
                   N11           RT10        14
                   H1            RT10        21
                   __________________________________
                   RT5           RT5         6
                   RT7           RT10        8


    Table 2: The portion of Router RT6's routing table listing local
                             destinations.

        configured (static routes).  Default routes can also be included
        as part of the Autonomous System's external routing information.

        External routing information is flooded unaltered throughout the
        AS.  In our example, all the routers in the Autonomous System
        know that Router RT7 has two external routes, with metrics 2 and
        9.

        OSPF supports two types of external metrics.  Type 1 external
        metrics are equivalent to the link state metric.  Type 2
        external metrics are greater than the cost of any path internal
        to the AS.  Use of Type 2 external metrics assumes that routing
        between AS'es is the major cost of routing a packet, and
        eliminates the need for conversion of external costs to internal
        link state metrics.

        As an example of Type 1 external metric processing, suppose that
        the Routers RT7 and RT5 in Figure 2 are advertising Type 1
        external metrics.  For each external route, the distance from
        Router RT6 is calculated as the sum of the external route's cost
        and the distance from Router RT6 to the advertising router.  For
        every external destination, the router advertising the shortest
        route is discovered, and the next hop to the advertising router
        becomes the next hop to the destination.




Moy                                                            [Page 18]

RFC 1583                     OSPF Version 2                   March 1994


        Both Router RT5 and RT7 are advertising an external route to
        destination Network N12.  Router RT7 is preferred since it is
        advertising N12 at a distance of 10 (8+2) to Router RT6, which
        is better than Router RT5's 14 (6+8).  Table 3 shows the entries
        that are added to the routing table when external routes are
        examined:



                         Destination   Next  Hop   Distance
                         __________________________________
                         N12           RT10        10
                         N13           RT5         14
                         N14           RT5         14
                         N15           RT10        17


                 Table 3: The portion of Router RT6's routing table
                           listing external destinations.


        Processing of Type 2 external metrics is simpler.  The AS
        boundary router advertising the smallest external metric is
        chosen, regardless of the internal distance to the AS boundary
        router.  Suppose in our example both Router RT5 and Router RT7
        were advertising Type 2 external routes.  Then all traffic
        destined for Network N12 would be forwarded to Router RT7, since
        2 < 8.  When several equal-cost Type 2 routes exist, the
        internal distance to the advertising routers is used to break
        the tie.

        Both Type 1 and Type 2 external metrics can be present in the AS
        at the same time.  In that event, Type 1 external metrics always
        take precedence.

        This section has assumed that packets destined for external
        destinations are always routed through the advertising AS
        boundary router.  This is not always desirable.  For example,
        suppose in Figure 2 there is an additional router attached to
        Network N6, called Router RTX.  Suppose further that RTX does
        not participate in OSPF routing, but does exchange EGP
        information with the AS boundary router RT7.  Then, Router RT7
        would end up advertising OSPF external routes for all
        destinations that should be routed to RTX.  An extra hop will
        sometimes be introduced if packets for these destinations need
        always be routed first to Router RT7 (the advertising router).

        To deal with this situation, the OSPF protocol allows an AS



Moy                                                            [Page 19]

RFC 1583                     OSPF Version 2                   March 1994


        boundary router to specify a "forwarding address" in its
        external advertisements.  In the above example, Router RT7 would
        specify RTX's IP address as the "forwarding address" for all
        those destinations whose packets should be routed directly to
        RTX.

        The "forwarding address" has one other application.  It enables
        routers in the Autonomous System's interior to function as
        "route servers".  For example, in Figure 2 the router RT6 could
        become a route server, gaining external routing information
        through a combination of static configuration and external
        routing protocols.  RT6 would then start advertising itself as
        an AS boundary router, and would originate a collection of OSPF
        external advertisements.  In each external advertisement, Router
        RT6 would specify the correct Autonomous System exit point to
        use for the destination through appropriate setting of the
        advertisement's "forwarding address" field.


    2.3.  Equal-cost multipath

        The above discussion has been simplified by considering only a
        single route to any destination.  In reality, if multiple
        equal-cost routes to a destination exist, they are all
        discovered and used.  This requires no conceptual changes to the
        algorithm, and its discussion is postponed until we consider the
        tree-building process in more detail.

        With equal cost multipath, a router potentially has several
        available next hops towards any given destination.


    2.4.  TOS-based routing

        OSPF can calculate a separate set of routes for each IP Type of
        Service. This means that, for any destination, there can