rfc1247.txt

著名的RFC文档,其中有一些文档是已经翻译成中文的的.

Labels such as HelloInterval encountered in the text refer to protocol
constants.  They may or may not be configurable.  The architectural
constants are explained in Appendix B.  The configurable constants are
explained in Appendix C.

The detailed specification of the protocol is presented in terms of data
structures.  This is done in order to make the explanation more precise.
Implementations of the protocol are required to support the
functionality described, but need not use the precise data structures
that appear in this paper.


2. The Topological Database

The database of the Autonomous System's topology describes a directed
graph.  The vertices of the graph consist of routers and networks.  A
graph edge connects two routers when they are attached via a physical
point-to-point network.  An edge connecting a router to a network



[Moy]                                                           [Page 6]

RFC 1247                     OSPF Version 2                    July 1991


indicates that the router has an interface on the network.

The vertices of the graph can be further typed according to function.
Only some of these types carry transit data traffic; that is, traffic
that is neither locally originated nor locally destined.  Vertices that
can carry transit traffic are indicated on the graph by having both
incoming and outgoing edges.



                   Vertex type   Vertex name    Transit?
                   _____________________________________
                   1             Router         yes
                   2             Network        yes
                   3             Stub network   no


                        Table 1: OSPF vertex types.


OSPF supports the following types of physical networks:


Point-to-point networks
    A network that joins a single pair of routers.  A 56Kb serial line
    is an example of a point-to-point network.

Broadcast networks
    Networks supporting many (more than two) attached routers, together
    with the capability to address a single physical message to all of
    the attached routers (broadcast).  Neighboring routers are
    discovered dynamically on these nets using OSPF's Hello Protocol.
    The Hello Protocol itself takes advantage of the broadcast
    capability.  The protocol makes further use of multicast
    capabilities, if they exist.  An ethernet is an example of a
    broadcast network.

Non-broadcast networks
    Networks supporting many (more than two) routers, but having no
    broadcast capability.  Neighboring routers are also discovered on
    these nets using OSPF's Hello Protocol.  However, due to the lack of
    broadcast capability, some configuration information is necessary
    for the correct operation of the Hello Protocol.  On these networks,
    OSPF protocol packets that are normally multicast need to be sent to
    each neighboring router, in turn.  An X.25 Public Data Network (PDN)
    is an example of a non-broadcast network.





[Moy]                                                           [Page 7]

RFC 1247                     OSPF Version 2                    July 1991


The neighborhood of each network node in the graph depends on whether
the network has multi-access capabilities (either broadcast or non-
broadcast) and, if so, the number of routers having an interface to the
network.  The three cases are depicted in Figure 1.  Rectangles indicate
routers.  Circles and oblongs indicate multi-access networks.  Router
names are prefixed with the letters RT and network names with N.  Router
interface names are prefixed by I.  Lines between routers indicate
point-to-point networks.  The left side of the figure shows a network
with its connected routers, with the resulting graph shown on the right.


Two routers joined by a point-to-point network are represented in the
directed graph as being directly connected by a pair of edges, one in
each direction.  Interfaces to physical point-to-point networks need not
be assigned IP addresses.  Such a point-to-point network is called
unnumbered.  The graphical representation of point-to-point networks is
designed so that unnumbered networks can be supported naturally.  When
interface addresses exist, they are modelled as stub routes.  Note that
each router would then have a stub connection to the other router's
interface address (see Figure 1).

When multiple routers are attached to a multi-access network, the
directed graph shows all routers bidirectionally connected to the
network vertex (again, see Figure 1).  If only a single router is
attached to a multi-access network, the network will appear in the
directed graph as a stub connection.

Each network (stub or transit) in the graph has an IP address and
associated network mask.  The mask indicates the number of nodes on the
network.  Hosts attached directly to routers (referred to as host
routes) appear on the graph as stub networks.  The network mask for a
host route is always 0xffffffff, which indicates the presence of a
single node.

Figure 2 shows a sample map of an Autonomous System.  The rectangle
labelled H1 indicates a host, which has a SLIP connection to router
RT12.  Router RT12 is therefore advertising a host route.  Lines between


                 ______________________________________

                 (Figure not included in text version.)

                    Figure 1: Network map components
                 ______________________________________






[Moy]                                                           [Page 8]

RFC 1247                     OSPF Version 2                    July 1991


routers indicate physical point-to-point networks.  The only point-to-
point network that has been assigned interface addresses is the one
joining routers RT6 and RT10.  Routers RT5 and RT7 have EGP connections
to other Autonomous Systems.  A set of EGP-learned routes have been
displayed for both of these routers.


A cost is associated with the output side of each router interface.
This cost is configurable by the system administrator.  The lower the
cost, the more likely the interface is to be used to forward data
traffic.  Costs are also associated with the externally derived routing
data (e.g., the EGP-learned routes).

The directed graph resulting from the map in Figure 2 is depicted in
Figure 3.  Arcs are labelled with the cost of the corresponding router
output interface.  Arcs having no labelled cost have a cost of 0.  Note
that arcs leading from networks to routers always have cost 0; they are
significant nonetheless.  Note also that the externally derived routing
data appears on the graph as stubs.


The topological database (or what has been referred to above as the
directed graph) is pieced together from link state advertisements
generated by the routers.  The neighborhood of each transit vertex is
represented in a single, separate link state advertisement.  Figure 4
shows graphically the link state representation of the two kinds of
transit vertices: routers and multi-access networks.  Router RT12 has an


                 ______________________________________

                 (Figure not included in text version.)

                  Figure 2: A sample Autonomous System
                 ______________________________________



               __________________________________________

                (Figures not included in text version.)

                 Figure 3: The resulting directed graph
               Figure 4: Individual link state components
               __________________________________________






[Moy]                                                           [Page 9]

RFC 1247                     OSPF Version 2                    July 1991


interface to two broadcast networks and a SLIP line to a host.  Network
N6 is a broadcast network with three attached routers.  The cost of all
links from network N6 to its attached routers is 0.  Note that the link
state advertisement for network N6 is actually generated by one of the
attached routers: the router that has been elected Designated Router for
the network.


2.1 The shortest-path tree

When no OSPF areas are configured, each router in the Autonomous System
has an identical topological database, leading to an 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.






                 ______________________________________

                 (Figure not included in text version.)

                 Figure 5: The SPF tree for router RT6
                 ______________________________________






[Moy]                                                          [Page 10]

RFC 1247                     OSPF Version 2                    July 1991




                   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.

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

Here is 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



[Moy]                                                          [Page 11]

RFC 1247                     OSPF Version 2                    July 1991


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.

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