📄 rfc2178.txt
字号:
1.5. Acknowledgments
The author would like to thank Ran Atkinson, Fred Baker, Jeffrey
Burgan, Rob Coltun, Dino Farinacci, Vince Fuller, Phanindra
Jujjavarapu, Milo Medin, Tom Pusateri, Kannan Varadhan, Zhaohui Zhang
and the rest of the OSPF Working Group for the ideas and support they
have given to this project.
The OSPF Point-to-MultiPoint interface is based on work done by Fred
Baker.
The OSPF Cryptographic Authentication option was developed by Fred
Baker and Ran Atkinson.
2. The Link-state Database: organization and calculations
The following subsections describe the organization of OSPF's link-
state database, and the routing calculations that are performed on
the database in order to produce a router's routing table.
2.1. Representation of routers and networks
The Autonomous System's link-state database 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
indicates that the router has an interface on the network. Networks
can be either transit or stub networks. Transit networks are those
capable of carrying data traffic that is neither locally originated
nor locally destined. A transit network is represented by a graph
vertex having both incoming and outgoing edges. A stub network's
vertex has only incoming edges.
The neighborhood of each network node in the graph depends on the
network's type (point-to-point, broadcast, NBMA or Point-to-
MultiPoint) and the number of routers having an interface to the
network. Three cases are depicted in Figure 1a. Rectangles indicate
routers. Circles and oblongs indicate networks. Router names are
prefixed with the letters RT and network names with the letter N.
Router interface names are prefixed by the letter I. Lines between
routers indicate point-to-point networks. The left side of the
figure shows networks with their connected routers, with the
resulting graphs shown on the right.
Moy Standards Track [Page 11]
RFC 2178 OSPF Version 2 July 1997
**FROM**
* |RT1|RT2|
+---+Ia +---+ * ------------
|RT1|------|RT2| T RT1| | X |
+---+ Ib+---+ O RT2| X | |
* Ia| | X |
* Ib| X | |
Physical point-to-point networks
**FROM**
+---+ *
|RT7| * |RT7| N3|
+---+ T ------------
| O RT7| | |
+----------------------+ * N3| X | |
N3 *
Stub networks
+---+ +---+
|RT3| |RT4| |RT3|RT4|RT5|RT6|N2 |
+---+ +---+ * ------------------------
| N2 | * RT3| | | | | X |
+----------------------+ T RT4| | | | | X |
| | O RT5| | | | | X |
+---+ +---+ * RT6| | | | | X |
|RT5| |RT6| * N2| X | X | X | X | |
+---+ +---+
Broadcast or NBMA networks
Figure 1a: Network map components
Networks and routers are represented by vertices. An edge connects
Vertex A to Vertex B iff the intersection of Column A and Row B is
marked with an X.
The top of Figure 1a shows two routers connected by a point-to-point
link. In the resulting link-state database graph, the two router
vertices are directly connected by a pair of edges, one in each
direction. Interfaces to point-to-point networks need not be assigned
IP addresses. When interface addresses are assigned, they are
modelled as stub links, with each router advertising a stub
connection to the other router's interface address. Optionally, an IP
Moy Standards Track [Page 12]
RFC 2178 OSPF Version 2 July 1997
subnet can be assigned to the point-to-point network. In this case,
both routers advertise a stub link to the IP subnet, instead of
advertising each others' IP interface addresses.
The middle of Figure 1a shows a network with only one attached router
(i.e., a stub network). In this case, the network appears on the end
of a stub connection in the link-state database's graph.
When multiple routers are attached to a broadcast network, the link-
state database graph shows all routers bidirectionally connected to
the network vertex. This is pictured at the bottom of Figure 1a.
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.
2.1.1. Representation of non-broadcast networks
As mentioned previously, OSPF can run over non-broadcast networks in
one of two modes: NBMA or Point-to-MultiPoint. The choice of mode
determines the way that the Hello protocol and flooding work over the
non-broadcast network, and the way that the network is represented in
the link-state database.
In NBMA mode, OSPF emulates operation over a broadcast network: a
Designated Router is elected for the NBMA network, and the Designated
Router originates an LSA for the network. The graph representation
for broadcast networks and NBMA networks is identical. This
representation is pictured in the middle of Figure 1a.
NBMA mode is the most efficient way to run OSPF over non-broadcast
networks, both in terms of link-state database size and in terms of
the amount of routing protocol traffic. However, it has one
significant restriction: it requires all routers attached to the NBMA
network to be able to communicate directly. This restriction may be
met on some non-broadcast networks, such as an ATM subnet utilizing
SVCs. But it is often not met on other non-broadcast networks, such
as PVC-only Frame Relay networks. On non-broadcast networks where not
all routers can communicate directly you can break the non-broadcast
network into logical subnets, with the routers on each subnet being
able to communicate directly, and then run each separate subnet as an
NBMA network (see [Ref15]). This however requires quite a bit of
administrative overhead, and is prone to misconfiguration. It is
probably better to run such a non-broadcast network in Point-to-
Multipoint mode.
Moy Standards Track [Page 13]
RFC 2178 OSPF Version 2 July 1997
In Point-to-MultiPoint mode, OSPF treats all router-to-router
connections over the non-broadcast network as if they were point-to-
point links. No Designated Router is elected for the network, nor is
there an LSA generated for the network. In fact, a vertex for the
Point-to-MultiPoint network does not appear in the graph of the
link-state database.
Figure 1b illustrates the link-state database representation of a
Point-to-MultiPoint network. On the left side of the figure, a
Point-to-MultiPoint network is pictured. It is assumed that all
routers can communicate directly, except for routers RT4 and RT5. I3
though I6 indicate the routers' IP interface addresses on the Point-
to-MultiPoint network. In the graphical representation of the link-
state database, routers that can communicate directly over the
Point-to-MultiPoint network are joined by bidirectional edges, and
each router also has a stub connection to its own IP interface
address (which is in contrast to the representation of real point-
to-point links; see Figure 1a).
On some non-broadcast networks, use of Point-to-MultiPoint mode and
data-link protocols such as Inverse ARP (see [Ref14]) will allow
autodiscovery of OSPF neighbors even though broadcast support is not
available.
2.1.2. An example link-state database
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 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 BGP
connections to other Autonomous Systems. A set of BGP-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 BGP-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.
Moy Standards Track [Page 14]
RFC 2178 OSPF Version 2 July 1997
**FROM**
+---+ +---+
|RT3| |RT4| |RT3|RT4|RT5|RT6|
+---+ +---+ * --------------------
I3| N2 |I4 * RT3| | X | X | X |
+----------------------+ T RT4| X | | | X |
I5| |I6 O RT5| X | | | X |
+---+ +---+ * RT6| X | X | X | |
|RT5| |RT6| * I3| X | | | |
+---+ +---+ I4| | X | | |
I5| | | X | |
I6| | | | X |
Figure 1b: Network map components
Point-to-MultiPoint networks
All routers can communicate directly over N2, except
routers RT4 and RT5. I3 through I6 indicate IP
interface addresses
Moy Standards Track [Page 15]
RFC 2178 OSPF Version 2 July 1997
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -