doc: Add RFC documents

1 files changed, 673 insertions, 0 deletions

diff --git a/doc/rfc/rfc1245.txt b/doc/rfc/rfc1245.txt
new file mode 100644
index 0000000..6d154e5
--- /dev/null
+++ b/doc/rfc/rfc1245.txt
@@ -0,0 +1,673 @@
+
+
+
+
+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 ospf@trantor.umd.edu.
+
+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]
+
+RFC 1245                 OSPF protocol analysis                July 1991
+
+
+three advertisements fit in a single packet. (This packet could be
+either a Link State Update packet or a Link State Acknowledgment packet;
+in this analysis we select the Link State Update packet, which is the
+larger). An AS external LSA is 36 bytes long.  Adding one third of a
+packet header (IP header plus OSPF Update packet) yields 52 bytes.
+Transmitting this amount of data every 30 minutes gives an average rate
+of 23/100 bits/second.
+
+If you want to limit your routing traffic to 5% of the link's total
+bandwidth, you get the following maximums for database size:
+
+TABLE 2. Database size as a function of link speed (5% utilization)
+
+
+                 Speed    # external advertisements
+                 _____________________________________
+                 9.6 Kb   2087
+                 56 Kb    12,174
+
+
+Higher line speeds have not been included, because other factors will
+then limit database size (like router memory) before line speed becomes
+a factor. Note that in the above calculation, the size of the data link
+header was not taken into account. Also, note that while the OSPF
+database is likely to be mostly external LSAs, other LSAs have a size
+also. As a ballpark estimate, router links and network links are
+generally three times as large as an AS external link, with summary link
+advertisements being the same size as external link LSAs.
+
+OSPF consumes considerably less link bandwidth than RIP. This has been
+shown experimentally in the NSI network. See Jeffrey Burgan's "NASA
+Sciences Internet" report in [3].
+
+
+3.3  Router memory
+
+Memory requirements in OSPF are dominated by the size of the link state
+database. As in the previous section, it is probably safe to assume that
+most of the advertisements in the database are external LSAs. While an
+external LSA is 36 bytes long, it is generally stored by an OSPF
+implementation together with some support data. So a good estimate of
+router memory consumed by an external LSA is probably 64 bytes. So a
+database having 10,000 external LSAs will consume 640K bytes of router
+memory. OSPF definitely requires more memory than RIP.
+
+Using the Proteon P4200 implementation as an example, the P4200 has
+2Mbytes of memory. This is shared between instruction, data and packet
+buffer memory. The P4200 has enough memory to store 10, 000 external
+
+
+
+[Moy]                                                           [Page 7]
+
+RFC 1245                 OSPF protocol analysis                July 1991
+
+
+LSAs, and still have enough packet buffer memory available to run a
+reasonable number of interfaces.
+
+Also, note that while the OSPF database is likely to be mostly external
+LSAs, other LSAs have a size also. As a ballpark estimate, router links
+and network links consume generally three times as much memory as an AS
+external link, with summary link advertisements being the same size as
+external link LSAs.
+
+
+3.4  Router CPU
+
+Assume that, as the size of the OSPF routing domain grows, the number of
+interfaces per router stays bounded. Then the Dijkstra calculation is of
+order (n * log (n)), where n is the number of routers in the routing
+domain. (This is the complexity of the Dijkstra algorithm in a sparse
+network). Of course, it is implementation specific as to how expensive
+the Dijkstra really is.
+
+We have no experimental numbers for the cost of the Dijkstra calculation
+in a real OSPF implementation. However, Steve Deering presented results
+for the Dijkstra calculation in the "MOSPF meeting report" in [3].
+Steve's calculation was done on a DEC 5000 (10 mips processor), using
+the Stanford internet as a model. His graphs are based on numbers of
+networks, not number of routers. However, if we extrapolate that the
+ratio of routers to networks remains the same, the time to run Dijkstra
+for 200 routers in Steve's implementation was around 15 milliseconds.
+
+This seems a reasonable cost, particularly when you notice that the
+Dijkstra calculation is run very infrequently in operational
+deployments. In the three networks presented in Section 3.1, Dijkstra
+was run on average only every 13 to 50 minutes. Since the Dijkstra is
+run so infrequently, it seems likely that OSPF overall consumes less CPU
+than RIP (because of RIP's frequent updates, requiring routing table
+lookups).
+
+As another example, the routing algorithm in MILNET is SPF-based.
+MILNET's current size is 230 nodes, and the routing calculation still
+consumes less than 5% of the MILNET switches' processor bandwidth [4].
+Because the routing algorithm in the MILNET adapts to network load, it
+runs the Dijkstra process quite frequently (on the order of seconds as
+compared to OSPF's minutes). However, it should be noted that the
+routing algorithm in MILNET incrementally updates the SPF-tree, while
+OSPF rebuilds it from scratch at each Dijkstra calculation
+
+OSPF's Area capability provides a way to reduce Dijkstra overhead, if it
+becomes a burden. The routing domain can be split into areas. The extent
+of the Dijkstra calculation (and its complexity) is limited to a single
+
+
+
+[Moy]                                                           [Page 8]
+
+RFC 1245                 OSPF protocol analysis                July 1991
+
+
+area at a time.
+
+
+3.5  Role of Designated Router
+
+This section explores the number of routers that can be attached to a
+single network. As the number of routers attached to a network grows, so
+does the amount of OSPF routing traffic seen on the network.  Some of
+this is Hello traffic, which is generally multicast by each router every
+10 seconds. This burden is borne by all routers attached to the network.
+However, because of its special role in the flooding process, the
+Designated router ends up sending more Link State Updates than the other
+routers on the network. Also, the Designated Router receives Link State
+Acknowledgments from all attached routers, while the other routers just
+receive them from the DR. (Although it is important to note that the
+rate of Link State Acknowledgments will generally be limited to one per
+second from each router, because acknowledgments are generally delayed.)
+
+So, if the amount of protocol traffic on the LAN becomes a limiting
+factor, the limit is likely to be detected in the Designated Router
+first. However, such a limit is not expected to be reached in practice.
+The amount of routing protocol traffic generated by OSPF has been shown
+to be small (see Section 3.2). Also, if need be OSPF's hello timers can
+be configured to reduce the amount of protocol traffic on the network.
+Note that more than 50 routers have been simulated attached to a single
+LAN (see [1]). Also, in interoperability testing 13 routers have been
+attached to a single ethernet with no problems encountered.
+
+Another factor in the number of routers attached to a single network is
+the cutover time when the Designated Router fails. OSPF has a Backup
+Designated Router so that the cutover does not have to wait for the new
+DR to synchronize (the adjacency bring-up process mentioned earlier)
+with all the other routers on the LAN; as a Backup DR it had already
+synchronized. However, in those rare cases when both DR and Backup DR
+crash at the same time, the new DR will have to synchronize (via the
+adjacency bring-up process) with all other routers before becoming
+functional. Field experience show that this synchronization process
+takes place in a timely fashion (see the OARnet report in [1]). However,
+this may be an issue in systems that have many routers attached to a
+single network.
+
+In the unlikely event that the number of routers attached to a LAN
+becomes a problem, either due to the amount of routing protocol traffic
+or the cutover time, the LAN can be split into separate pieces (similar
+to splitting up the AS into separate areas).
+
+
+
+
+
+
+[Moy]                                                           [Page 9]
+
+RFC 1245                 OSPF protocol analysis                July 1991
+
+
+3.6  Summary
+
+In summary, it seems like the most likely limitation to the size of an
+OSPF system is available router memory. We have given as 10,000 as the
+number of external LSAs that can be supported by the memory available in
+one configuration of a particular implementation (the Proteon P4200).
+Other implementations may vary; nowadays routers are being built with
+more and more memory.  Note that 10,000 routes is considerably larger
+than the largest field implementation (BARRNet; which at 1816 external
+LSAs is still very large).
+
+Note that there may be ways to reduce database size in a routing domain.
+First, the domain can make use of default routing, reducing the number
+of external routes that need to be imported. Secondly, an EGP can be
+used that will transport its own information through the AS instead of
+relying on the IGP (OSPF in this case) to do transfer the information
+for it (the EGP). Thirdly, routers having insufficient memory may be
+able to be assigned to stub areas (whose databases are drastically
+smaller). Lastly, if the Internet went away from a flat address space
+the amount of external information imported into an OSPF domain could be
+reduced drastically.
+
+While not as likely, there could be other issues that would limit the
+size of an OSPF routing domain. If there are slow lines (like 9600
+baud), the size of the database will be limited (see Section 3.2).
+Dijkstra may get to be expensive when there are hundreds of routers in
+the OSPF domain; although at this point the domain can be split into
+areas. Finally, when there are many routers attached to a single
+network, there may be undue burden imposed upon the Designated Router;
+although at that point a LAN can be split into separate LANs.
+
+
+4.0  Suitable environments
+
+Suitable environments for the OSPF protocol range from large to small.
+OSPF is particular suited for transit Autonomous Systems for the
+following reasons. OSPF can accommodate a large number of external
+routes. In OSPF the import of external information is very flexible,
+having provisions for a forwarding address, two levels of external
+metrics, and the ability to tag external routes with their AS number for
+easy management. Also OSPF's ability to do partial updates when external
+information changes is very useful on these networks.
+
+OSPF is also suited for smaller, either stand alone or stub Autonomous
+Systems, because of its wide array of features: fast convergence,
+equal-cost-multipath, TOS routing, areas, etc.
+
+
+
+
+
+[Moy]                                                          [Page 10]
+
+RFC 1245                 OSPF protocol analysis                July 1991
+
+
+5.0  Unsuitable environments
+
+OSPF has a very limited ability to express policy. Basically, its only
+policy mechanisms are in the establishment of a four level routing
+hierarchy: intra-area, inter-area, type 1 and type 2 external routes.  A
+system wanting more sophisticated policies would have to be split up
+into separate ASes, running a policy-based EGP between them.
+
+
+6.0  Reference Documents
+
+The following documents have been referenced by this report:
+
+
+[1] Moy, J., "Experience with the OSPF protocol", RFC 1246, July 1991.
+
+[2] Moy, J., "OSPF Version 2", RFC 1247, July 1991.
+
+[3] Corporation for National Research Initiatives, "Proceedings of the
+    Eighteenth Internet Engineering Task Force", University of British
+    Columbia, July 30-August 3, 1990.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+[Moy]                                                          [Page 11]
+
+RFC 1245                 OSPF protocol analysis                July 1991
+
+
+Security Considerations
+
+Security issues are not discussed in this memo.
+
+
+Author's Address
+
+John Moy
+Proteon Inc.
+2 Technology Drive
+Westborough, MA 01581
+
+Phone: (508) 898-2800
+Email:  jmoy@proteon.com
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+[Moy]                                                          [Page 12]
+