Movatterモバイル変換

Network Working Group                                     J. Moy, EditorRequest for Comments: 1245                                 Proteon, Inc.                                                               July 1991OSPF protocol analysisStatus of this MemoThis memo provides information for the Internet community. It does notspecify any Internet standard. Distribution of this memo is unlimited.Please send comments to ospf@trantor.umd.edu.AbstractThis is the first of two reports on the OSPF protocol. These reports arerequired by the IAB/ IESG in order for an Internet routing protocol toadvance 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 inRFC 1131. Since thenOSPF version 2 has been developed. Version 2 has been documented in RFC1247.  The changes between version 1 and version 2 of the OSPF protocolare explained inAppendix F of RFC 1247. It is OSPF Version 2 that isthe subject of this report.This report attempts to summarize the key features of OSPF V2. It alsoattempts to analyze how the protocol will perform and scale in theInternet.1.0  IntroductionThis document addresses, for OSPF V2, the requirements set forth by theIAB/IESG for an Internet routing protocol to advance to Draft Standardstate. This requirements are briefly summarized below. The remainingsections of this report document how OSPF V2 satisfies theserequirements: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  AcknowledgmentsThe OSPF protocol has been developed by the OSPF Working Group of theInternet Engineering Task Force.2.0  Key features of the OSPF protocolThis section summarizes the key features of the OSPF protocol. OSPF isan Internal gateway protocol; it is designed to be used internal to asingle Autonomous System. OSPF uses link-state or SPF-based technology(as compared to the distance-vector or Bellman-Ford technology found inrouting 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 linkstate database. Each router has an identical link state database;synchronization of link state databases is maintained via a reliableflooding algorithm. From this link state database, each router builds arouting table by calculating a shortest-path tree, with the root of thetree being the calculating router itself. This calculation is commonlyreferred to as the Dijkstra procedure.Link state advertisements are small. Each advertisement describes asmall pieces of the OSPF routing domain, namely either: the neighborhoodof a single router, the neighborhood of a single transit network, asingle 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 1991o  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 protocolThis section attempts to analyze how the OSPF protocol will perform andscale in the Internet. In this analysis, we will concentrate on thefollowing 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 1991o  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 muchresources the OSPF protocol will consume, both now and in the future. Toaid in this analysis, the next section will present some data that havebeen collected in actual OSPF field deployments.3.1   Operational dataThe OSPF protocol has been deployed in a number of places in theInternet. For a summary of this deployment, see [1]. Some statisticshave been gathered from this operational experience, via local networkmanagement facilities. Some of these statistics are presented in thefollowing 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 thatstatistics were gathered on the three networks. A brief description ofthe other statistics follows:[Moy]                                                           [Page 5]

RFC 1245                 OSPF protocol analysis                July 1991o  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 bandwidthIn this section we attempt to calculate how much link bandwidth isconsumed by the OSPF flooding process. The amount of link bandwidthconsumed increases linearly with the number of advertisements present inthe OSPF database.We assume that the majority of advertisements in thedatabase will be AS external LSAs (operationally this is true, see [1]).From the statistics presented inSection 3.1, any particularadvertisement is flooded (on average) every 30 minutes. In addition,[Moy]                                                           [Page 6]

RFC 1245                 OSPF protocol analysis                July 1991three advertisements fit in a single packet. (This packet could beeither a Link State Update packet or a Link State Acknowledgment packet;in this analysis we select the Link State Update packet, which is thelarger). An AS external LSA is 36 bytes long.  Adding one third of apacket header (IP header plus OSPF Update packet) yields 52 bytes.Transmitting this amount of data every 30 minutes gives an average rateof 23/100 bits/second.If you want to limit your routing traffic to 5% of the link's totalbandwidth, 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,174Higher line speeds have not been included, because other factors willthen limit database size (like router memory) before line speed becomesa factor. Note that in the above calculation, the size of the data linkheader was not taken into account. Also, note that while the OSPFdatabase is likely to be mostly external LSAs, other LSAs have a sizealso. As a ballpark estimate, router links and network links aregenerally three times as large as an AS external link, with summary linkadvertisements being the same size as external link LSAs.OSPF consumes considerably less link bandwidth than RIP. This has beenshown experimentally in the NSI network. See Jeffrey Burgan's "NASASciences Internet" report in [3].3.3  Router memoryMemory requirements in OSPF are dominated by the size of the link statedatabase. As in the previous section, it is probably safe to assume thatmost of the advertisements in the database are external LSAs. While anexternal LSA is 36 bytes long, it is generally stored by an OSPFimplementation together with some support data. So a good estimate ofrouter memory consumed by an external LSA is probably 64 bytes. So adatabase having 10,000 external LSAs will consume 640K bytes of routermemory. OSPF definitely requires more memory than RIP.Using the Proteon P4200 implementation as an example, the P4200 has2Mbytes of memory. This is shared between instruction, data and packetbuffer memory. The P4200 has enough memory to store 10, 000 external[Moy]                                                           [Page 7]

RFC 1245                 OSPF protocol analysis                July 1991LSAs, and still have enough packet buffer memory available to run areasonable number of interfaces.Also, note that while the OSPF database is likely to be mostly externalLSAs, other LSAs have a size also. As a ballpark estimate, router linksand network links consume generally three times as much memory as an ASexternal link, with summary link advertisements being the same size asexternal link LSAs.3.4  Router CPUAssume that, as the size of the OSPF routing domain grows, the number ofinterfaces per router stays bounded. Then the Dijkstra calculation is oforder (n * log (n)), where n is the number of routers in the routingdomain. (This is the complexity of the Dijkstra algorithm in a sparsenetwork). Of course, it is implementation specific as to how expensivethe Dijkstra really is.We have no experimental numbers for the cost of the Dijkstra calculationin a real OSPF implementation. However, Steve Deering presented resultsfor the Dijkstra calculation in the "MOSPF meeting report" in [3].Steve's calculation was done on a DEC 5000 (10 mips processor), usingthe Stanford internet as a model. His graphs are based on numbers ofnetworks, not number of routers. However, if we extrapolate that theratio of routers to networks remains the same, the time to run Dijkstrafor 200 routers in Steve's implementation was around 15 milliseconds.This seems a reasonable cost, particularly when you notice that theDijkstra calculation is run very infrequently in operationaldeployments. In the three networks presented inSection 3.1, Dijkstrawas run on average only every 13 to 50 minutes. Since the Dijkstra isrun so infrequently, it seems likely that OSPF overall consumes less CPUthan RIP (because of RIP's frequent updates, requiring routing tablelookups).As another example, the routing algorithm in MILNET is SPF-based.MILNET's current size is 230 nodes, and the routing calculation stillconsumes less than 5% of the MILNET switches' processor bandwidth [4].Because the routing algorithm in the MILNET adapts to network load, itruns the Dijkstra process quite frequently (on the order of seconds ascompared to OSPF's minutes). However, it should be noted that therouting algorithm in MILNET incrementally updates the SPF-tree, whileOSPF rebuilds it from scratch at each Dijkstra calculationOSPF's Area capability provides a way to reduce Dijkstra overhead, if itbecomes a burden. The routing domain can be split into areas. The extentof the Dijkstra calculation (and its complexity) is limited to a single[Moy]                                                           [Page 8]

RFC 1245                 OSPF protocol analysis                July 1991area at a time.3.5  Role of Designated RouterThis section explores the number of routers that can be attached to asingle network. As the number of routers attached to a network grows, sodoes the amount of OSPF routing traffic seen on the network.  Some ofthis is Hello traffic, which is generally multicast by each router every10 seconds. This burden is borne by all routers attached to the network.However, because of its special role in the flooding process, theDesignated router ends up sending more Link State Updates than the otherrouters on the network. Also, the Designated Router receives Link StateAcknowledgments from all attached routers, while the other routers justreceive them from the DR. (Although it is important to note that therate of Link State Acknowledgments will generally be limited to one persecond from each router, because acknowledgments are generally delayed.)So, if the amount of protocol traffic on the LAN becomes a limitingfactor, the limit is likely to be detected in the Designated Routerfirst. However, such a limit is not expected to be reached in practice.The amount of routing protocol traffic generated by OSPF has been shownto be small (seeSection 3.2). Also, if need be OSPF's hello timers canbe configured to reduce the amount of protocol traffic on the network.Note that more than 50 routers have been simulated attached to a singleLAN (see [1]). Also, in interoperability testing 13 routers have beenattached to a single ethernet with no problems encountered.Another factor in the number of routers attached to a single network isthe cutover time when the Designated Router fails. OSPF has a BackupDesignated Router so that the cutover does not have to wait for the newDR to synchronize (the adjacency bring-up process mentioned earlier)with all the other routers on the LAN; as a Backup DR it had alreadysynchronized. However, in those rare cases when both DR and Backup DRcrash at the same time, the new DR will have to synchronize (via theadjacency bring-up process) with all other routers before becomingfunctional. Field experience show that this synchronization processtakes 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 asingle network.In the unlikely event that the number of routers attached to a LANbecomes a problem, either due to the amount of routing protocol trafficor the cutover time, the LAN can be split into separate pieces (similarto splitting up the AS into separate areas).[Moy]                                                           [Page 9]

RFC 1245                 OSPF protocol analysis                July 19913.6  SummaryIn summary, it seems like the most likely limitation to the size of anOSPF system is available router memory. We have given as 10,000 as thenumber of external LSAs that can be supported by the memory available inone configuration of a particular implementation (the Proteon P4200).Other implementations may vary; nowadays routers are being built withmore and more memory.  Note that 10,000 routes is considerably largerthan the largest field implementation (BARRNet; which at 1816 externalLSAs 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 numberof external routes that need to be imported. Secondly, an EGP can beused that will transport its own information through the AS instead ofrelying on the IGP (OSPF in this case) to do transfer the informationfor it (the EGP). Thirdly, routers having insufficient memory may beable to be assigned to stub areas (whose databases are drasticallysmaller). Lastly, if the Internet went away from a flat address spacethe amount of external information imported into an OSPF domain could bereduced drastically.While not as likely, there could be other issues that would limit thesize of an OSPF routing domain. If there are slow lines (like 9600baud), the size of the database will be limited (seeSection 3.2).Dijkstra may get to be expensive when there are hundreds of routers inthe OSPF domain; although at this point the domain can be split intoareas. Finally, when there are many routers attached to a singlenetwork, 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 environmentsSuitable environments for the OSPF protocol range from large to small.OSPF is particular suited for transit Autonomous Systems for thefollowing reasons. OSPF can accommodate a large number of externalroutes. In OSPF the import of external information is very flexible,having provisions for a forwarding address, two levels of externalmetrics, and the ability to tag external routes with their AS number foreasy management. Also OSPF's ability to do partial updates when externalinformation changes is very useful on these networks.OSPF is also suited for smaller, either stand alone or stub AutonomousSystems, 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 19915.0  Unsuitable environmentsOSPF has a very limited ability to express policy. Basically, its onlypolicy mechanisms are in the establishment of a four level routinghierarchy: intra-area, inter-area, type 1 and type 2 external routes.  Asystem wanting more sophisticated policies would have to be split upinto separate ASes, running a policy-based EGP between them.6.0  Reference DocumentsThe 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 1991Security ConsiderationsSecurity issues are not discussed in this memo.Author's AddressJohn MoyProteon Inc.2 Technology DriveWestborough, MA 01581Phone: (508) 898-2800Email:  jmoy@proteon.com[Moy]                                                          [Page 12]