rfc1245.txt

RFC 的详细文档！

Network Working Group                                     J. Moy, Editor
Request for Comments: 1245                                 Proteon, Inc.
                                                               July 1991


                         OSPF protocol analysis



Status of this Memo

This memo provides information for the Internet community. It does not
specify any Internet standard. Distribution of this memo is unlimited.
Please send comments to [e-mail].

Abstract

This is the first of two reports on the OSPF protocol. These reports are
required by the IAB/ IESG in order for an Internet routing protocol to
advance to Draft Standard Status. OSPF is a TCP/IP routing protocol,
designed to be used internal to an Autonomous System (in other words,
OSPF is an Interior Gateway Protocol).

Version 1 of the OSPF protocol was published in RFC 1131. Since then
OSPF version 2 has been developed. Version 2 has been documented in RFC
1247.  The changes between version 1 and version 2 of the OSPF protocol
are explained in Appendix F of RFC 1247. It is OSPF Version 2 that is
the subject of this report.

This report attempts to summarize the key features of OSPF V2. It also
attempts to analyze how the protocol will perform and scale in the
Internet.

1.0  Introduction

This document addresses, for OSPF V2, the requirements set forth by the
IAB/IESG for an Internet routing protocol to advance to Draft Standard
state. This requirements are briefly summarized below. The remaining
sections of this report document how OSPF V2 satisfies these
requirements:

o  What are the key features and algorithms of the protocol?

o  How much link bandwidth, router memory and router CPU cycles does the
   protocol consume under normal conditions?

o  For these metrics, how does the usage scale as the routing
   environment grows? This should include topologies at least an order



[Moy]                                                           [Page 1]

RFC 1245                 OSPF protocol analysis                July 1991


   of magnitude larger than the current environment.

o  What are the limits of the protocol for these metrics? (I.e., when
   will the routing protocol break?)

o  For what environments is the protocol well suited, and for what is it
   not suitable?

1.1  Acknowledgments

The OSPF protocol has been developed by the OSPF Working Group of the
Internet Engineering Task Force.

2.0  Key features of the OSPF protocol

This section summarizes the key features of the OSPF protocol. OSPF is
an Internal gateway protocol; it is designed to be used internal to a
single Autonomous System. OSPF uses link-state or SPF-based technology
(as compared to the distance-vector or Bellman-Ford technology found in
routing protocols such as RIP). Individual link state advertisements
(LSAs) describe pieces of the OSPF routing domain (Autonomous System).
These LSAs are flooded throughout the routing domain, forming the link
state database. Each router has an identical link state database;
synchronization of link state databases is maintained via a reliable
flooding algorithm. From this link state database, each router builds a
routing table by calculating a shortest-path tree, with the root of the
tree being the calculating router itself. This calculation is commonly
referred to as the Dijkstra procedure.

Link state advertisements are small. Each advertisement describes a
small pieces of the OSPF routing domain, namely either: the neighborhood
of a single router, the neighborhood of a single transit network, a
single inter-area route (see below) or a single external route.

The other key features of the OSPF protocol are:

o  Adjacency bringup. Certain pairs of OSPF routers become "adjacent".
   As an adjacency is formed, the two routers synchronize their link
   state databases by exchanging database summaries in the form of OSPF
   Database Exchange packets. Adjacent routers then maintain syn-
   chronization of their link state databases through the reliable
   flooding algorithm. Routers connected by serial lines always become
   adjacent. On multi-access networks (e.g., ethernets or X.25 PDNs),
   all routers attached to the network become adjacent to both the
   Designated Router and the Backup Designated router.

o  Designated router. A Designated Router is elected on all multi-access
   networks (e.g., ethernets or X.25 PDNs). The network's Designated



[Moy]                                                           [Page 2]

RFC 1245                 OSPF protocol analysis                July 1991


   Router originates the network LSA describing the network's local
   environment. It also plays a special role in the flooding algorithm,
   since all routers on the network are synchronizing their link state
   databases by sending and receiving LSAs to/from the Designated Router
   during the flooding process.

o  Backup Designated Router. A Backup Designated Router is elected on
   multi-access networks to speed/ease the transition of Designated
   Routers when the current Designated Router disappears. In that event,
   the Backup DR takes over, and does not need to go through the
   adjacency bringup process on the LAN (since it already had done this
   in its Backup capacity). Also, even before the disappearance of the
   Designated Router is noticed, the Backup DR will enable the reliable
   flooding algorithm to proceed in the DR's absence.

o  Non-broadcast multi-access network support. OSPF treats these
   networks (e.g., X.25 PDNs) pretty much as if they were LANs (i.e., a
   DR is elected, and a network LSA is generated). Additional
   configuration information is needed however for routers attached to
   these network to initially find each other.

o  OSPF areas. OSPF allows the Autonomous Systems to be broken up into
   regions call areas.  This is useful for several reasons. First, it
   provides an extra level of routing protection: routing within an area
   is protected from all information external to the area. Second, by
   splitting an Autonomous System into areas the cost of the Dijkstra
   procedure (in terms of CPU cycles) is reduced.

o  Flexible import of external routing information. In OSPF, each
   external route is imported into the Autonomous System in a separate
   LSA. This reduces the amount of flooding traffic (since external
   routes change often, and you want to only flood the changes). It also
   enables partial routing table updates when only a single external
   route changes. OSPF external LSAs also provide the following
   features.  A forwarding address can be included in the external LSA,
   eliminating extra-hops at the edge of the Autonomous System. There
   are two levels of external metrics that can be specified, type 1 and
   type 2. Also, external routes can be tagged with a 32-bit number (the
   external route tag; commonly used as an AS number of the route's
   origin), simplifying external route management in a transit
   Autonomous System.

o  Four level routing hierarchy. OSPF has a four level routing
   hierarchy, or trust model: intra-area, inter-area, external type 1
   and external type 2 routes. This enables multiple levels of routing
   protection, and simplifies routing management in an Autonomous
   System.




[Moy]                                                           [Page 3]

RFC 1245                 OSPF protocol analysis                July 1991


o  Virtual links. By allowing the configuration of virtual links, OSPF
   removes topological restrictions on area layout in an Autonomous
   System.

o  Authentication of routing protocol exchanges. Every time an OSPF
   router receives a routing protocol packet, it authenticates the
   packet before processing it further.

o  Flexible routing metric. In OSPF, metric are assigned to outbound
   router interfaces. The cost of a path is then the sum of the path's
   component interfaces. The routing metric itself can be assigned by
   the system administrator to indicate any combination of network
   characteristics (e.g., delay, bandwidth, dollar cost, etc.).

o  Equal-cost multipath. When multiple best cost routes to a destination
   exist, OSPF finds them and they can be then used to load share
   traffic to the destination.

o  TOS-based routing. Separate sets of routes can be calculated for each
   IP type of service. For example, low delay traffic could be routed on
   one path, while high bandwidth traffic is routed on another. This is
   done by (optionally) assigning, to each outgoing router interface,
   one metric for each IP TOS.

o  Variable-length subnet support. OSPF includes support for variable-
   length subnet masks by carrying a network mask with each advertised
   destination.

o  Stub area support. To support routers having insufficient memory,
   areas can be configured as stubs. External LSAs (often making up the
   bulk of the Autonomous System) are not flooded into/throughout stub
   areas. Routing to external destinations in stub areas is based solely
   on default.

3.0  Cost of the protocol

This section attempts to analyze how the OSPF protocol will perform and
scale in the Internet. In this analysis, we will concentrate on the
following four areas:

o  Link bandwidth. In OSPF, a reliable flooding mechanism is used to
   ensure that router link state databases are remained synchronized.
   Individual components of the link state databases (the LSAs) are
   refreshed infrequently (every 30 minutes), at least in the absence of
   topological changes. Still, as the size of the database increases,
   the amount of link bandwidth used by the flooding procedure also
   increases.




[Moy]                                                           [Page 4]

RFC 1245                 OSPF protocol analysis                July 1991


o  Router memory. The size of an OSPF link state database can get quite
   large, especially in the presence of many external LSAs. This imposes
   requirements on the amount of router memory available.

o  CPU usage. In OSPF, this is dominated by the length of time it takes
   to run the shortest path calculation (Dijkstra procedure). This is a
   function of the number of routers in the OSPF system.

o  Role of the Designated Router. The Designated router receives and
   sends more packets on a multi-access networks than the other routers
   connected to the network. Also, there is some time involved in
   cutting over to a new Designated Router after the old one fails
   (especially when both the Backup Designated Router and the Designated
   Router fail at the same time). For this reason, it is possible that
   you may want to limit the number of routers connected to a single
   network.

The remaining section will analyze these areas, estimating how much
resources the OSPF protocol will consume, both now and in the future. To
aid in this analysis, the next section will present some data that have
been collected in actual OSPF field deployments.

3.1   Operational data

The OSPF protocol has been deployed in a number of places in the
Internet. For a summary of this deployment, see [1]. Some statistics
have been gathered from this operational experience, via local network
management facilities. Some of these statistics are presented in the
following table:

TABLE 1. Pertinent operational statistics


  Statistic                        BARRNet    NSI        OARnet
  ___________________________________________________________________
  Data gathering (duration)        99 hrs     277 hrs    28 hrs
  Dijkstra frequency               50 min     25 min     13 min
  External incremental frequency   1.2 min    .98 min    not gathered
  Database turnover                29.7 min   30.9 min   28.2 min
  LSAs per packet                  3.38       3.16       2.99
  Flooding retransmits             1.3%       1.4%       .7%


The first line in the above table show the length of time that
statistics were gathered on the three networks. A brief description of
the other statistics follows:





[Moy]                                                           [Page 5]

RFC 1245                 OSPF protocol analysis                July 1991


o  Dijkstra frequency. In OSPF, the Dijkstra calculation involves only
   those routers and transit networks belonging to the AS. The Dijkstra
   is run only when something in the system changes (like a serial line
   between two routers goes down). Note that in these operational
   systems, the Dijkstra process runs only infrequently (the most
   frequent being every 13 minutes).

o  External incremental frequency. In OSPF, when an external route
   changes only its entry in the routing table is recalculated. These
   are called external incremental updates. Note that these happen much
   more frequently than the Dijkstra procedure. (in other words,
   incremental updates are saving quite a bit of processor time).

o  Database turnover. In OSPF, link state advertisements are refreshed
   at a minimum of every 30 minutes. New advertisement instances are
   sent out more frequently when some part of the topology changes. The
   table shows that, even taking topological changes into account, on
   average an advertisement is updated close to only every 30 minutes.
   This statistic will be used in the link bandwidth calculations below.
   Note that NSI actually shows advertisements updated every 30.7 (> 30)
   minutes. This probably means that at one time earlier in the
   measurement period, NSI had a smaller link state database that it did
   at the end.

o  LSAs per packet. In OSPF, multiple LSAs can be included in either
   Link State Update or Link State Acknowledgment packets.The table
   shows that, on average, around 3 LSAs are carried in a single packet.
   This statistic is used when calculating the header overhead in the
   link bandwidth calculation below. This statistic was derived by
   diving the number of LSAs flooded by the number of (non-hello)
   multicasts sent.

o  Flooding retransmits. This counts both retransmission of LS Update
   packets and Link State Acknowledgment packets, as a percentage of the
   original multicast flooded packets. The table shows that flooding is
   working well, and that retransmits can be ignored in the link
   bandwidth calculation below.

3.2  Link bandwidth

In this section we attempt to calculate how much link bandwidth is
consumed by the OSPF flooding process. The amount of link bandwidth
consumed increases linearly with the number of advertisements present in
the OSPF database.We assume that the majority of advertisements in the
database will be AS external LSAs (operationally this is true, see [1]).

From the statistics presented in Section 3.1, any particular
advertisement is flooded (on average) every 30 minutes. In addition,



[Moy]                                                           [Page 6]