| RFC 1247 - OSPF Version 2 body { margin: 0px 8px; font-size: 1em; } h1, h2, h3, h4, h5, h6, .h1, .h2, .h3, .h4, .h5, .h6 { font-weight: bold; line-height: 0pt; display: inline; white-space: pre; font-family: monospace; font-size: 1em; font-weight: bold; } pre { font-size: 1em; } .pre { white-space: pre; font-family: monospace; } .header{ font-weight: bold; } .invisible { text-decoration: none; color: white; } @media print { body { font-size: 10.5pt; } h1, h2, h3, h4, h5, h6 { font-size: 10.5pt; } a:link, a:visited { color: inherit; text-decoration: none; } .break { page-break-before: always; } .noprint { display: none; } } @media screen { .grey, .grey a:link, .grey a:visited { color: #777; } .docinfo { background-color: #EEE; } .top { border-top: 7px solid #EEE; } .bgwhite { background-color: white; } .bgred { background-color: #F44; } .bggrey { background-color: #666; } .bgbrown { background-color: #840; } .bgorange { background-color: #FA0; } .bgyellow { background-color: #EE0; } .bgmagenta{ background-color: #F4F; } .bgblue { background-color: #66F; } .bgcyan { background-color: #4DD; } .bggreen { background-color: #4F4; } .legend { font-size: 90%; } .cplate { font-size: 70%; border: solid grey 1px; } } [RFCs/IDs] [Plain Text] [From draft-ietf-ospf-ospf2] Obsoleted by: 1583 DRAFT STANDARDUpdated by: 1349 Network Working Group J. MoyRequest for Comments: 1247 Proteon, Inc.Obsoletes: RFC 1131 July 1991 OSPF Version 2Status of this MemoThis RFC specifies an IAB standards track protocol for the Internetcommunity, and requests discussion and suggestions for improvements.Please refer to the current edition of the ``IAB Official ProtocolStandards'' for the standardization state and status of this protocol.Distribution of this memo is unlimited.AbstractThis memo documents version 2 of the OSPF protocol. OSPF is a link-state based routing protocol. It is designed to be run internal to asingle Autonomous System. Each OSPF router maintains an identicaldatabase describing the Autonomous System's topology. From thisdatabase, a routing table is calculated by constructing a shortest-pathtree.OSPF recalculates routes quickly in the face of topological changes,utilizing a minimum of routing protocol traffic. OSPF provides supportfor equal-cost multipath. Separate routes can be calculated for each IPtype of service. An area routing capability is provided, enabling anadditional level of routing protection and a reduction in routingprotocol traffic. In addition, all OSPF routing protocol exchanges areauthenticated.Version 1 of the OSPF protocol was documented in RFC 1131. Thedifferences between the two versions are explained in Appendix F.Please send comments to ospf@trantor.umd.edu.1. IntroductionThis document is a specification of the Open Shortest Path First (OSPF)internet routing protocol. OSPF is classified as an Internal GatewayProtocol (IGP). This means that it distributes routing informationbetween routers belonging to a single Autonomous System. The OSPFprotocol is based on SPF or link-state technology. This is a departure[Moy] [Page 1] RFC 1247 OSPF Version 2 July 1991from the Bellman-Ford base used by traditional internet routingprotocols.The OSPF protocol was developed by the OSPF working group of theInternet Engineering Task Force. It has been designed expressly for theinternet environment, including explicit support for IP subnetting,TOS-based routing and the tagging of externally-derived routinginformation. OSPF also provides for the authentication of routingupdates, and utilizes IP multicast when sending/receiving the updates.In addition, much work has been done to produce a protocol that respondsquickly to topology changes, yet involves small amounts of routingprotocol traffic.The author would like to thank Rob Coltun, Milo Medin, Mike Petry andthe rest of the OSPF working group for the ideas and support they havegiven to this project.1.1 Protocol overviewOSPF routes IP packets based solely on the destination IP address and IPType of Service found in the IP packet header. IP packets are routed"as is" -- they are not encapsulated in any further protocol headers asthey transit the Autonomous System. OSPF is a dynamic routing protocol.It quickly detects topological changes in the AS (such as routerinterface failures) and calculates new loop-free routes after a periodof convergence. This period of convergence is short and involves aminimum of routing traffic.In an SPF-based routing protocol, each router maintains a databasedescribing the Autonomous System's topology. Each participating routerhas an identical database. Each individual piece of this database is aparticular router's local state (e.g., the router's usable interfacesand reachable neighbors). The router distributes its local statethroughout the Autonomous System by flooding.All routers run the exact same algorithm, in parallel. From thetopological database, each router constructs a tree of shortest pathswith itself as root. This shortest-path tree gives the route to eachdestination in the Autonomous System. Externally derived routinginformation appears on the tree as leaves.OSPF calculates separate routes for each Type of Service (TOS). Whenseveral equal-cost routes to a destination exist, traffic is distributedequally among them. The cost of a route is described by a singledimensionless metric.OSPF allows sets of networks to be grouped together. Such a grouping is[Moy] [Page 2] RFC 1247 OSPF Version 2 July 1991called an area. The topology of an area is hidden from the rest of theAutonomous System. This information hiding enables a significantreduction in routing traffic. Also, routing within the area isdetermined only by the area's own topology, lending the area protectionfrom bad routing data. An area is a generalization of an IP subnettednetwork.OSPF enables the flexible configuration of IP subnets. Each routedistributed by OSPF has a destination and mask. Two different subnetsof the same IP network number may have different sizes (i.e., differentmasks). This is commonly referred to as variable length subnets. Apacket is routed to the best (i.e., longest or most specific) match.Host routes are considered to be subnets whose masks are "all ones"(0xffffffff).All OSPF protocol exchanges are authenticated. This means that onlytrusted routers can participate in the Autonomous System's routing. Avariety of authentication schemes can be used; a single authenticationscheme is configured for each area. This enables some areas to use muchstricter authentication than others.Externally derived routing data (e.g., routes learned from the ExteriorGateway Protocol (EGP)) is passed transparently throughout theAutonomous System. This externally derived data is kept separate fromthe OSPF protocol's link state data. Each external route can also betagged by the advertising router, enabling the passing of additionalinformation between routers on the boundaries of the Autonomous System.1.2 Definitions of commonly used termsHere is a collection of definitions for terms that have a specificmeaning to the protocol and that are used throughout the text. Thereader unfamiliar with the Internet Protocol Suite is referred to [RS-85-153] for an introduction to IP.Router A level three Internet Protocol packet switch. Formerly called a gateway in much of the IP literature.Autonomous System A group of routers exchanging routing information via a common routing protocol. Abbreviated as AS.Internal Gateway Protocol The routing protocol spoken by the routers belonging to an Autonomous system. Abbreviated as IGP. Each Autonomous System has[Moy] [Page 3] RFC 1247 OSPF Version 2 July 1991 a single IGP. Different Autonomous Systems may be running different IGPs.Router ID A 32-bit number assigned to each router running the OSPF protocol. This number uniquely identifies the router within an Autonomous System.Network In this paper, an IP network or subnet. It is possible for one physical network to be assigned multiple IP network/subnet numbers. We consider these to be separate networks. Point-to-point physical networks are an exception - they are considered a single network no matter how many (if any at all) IP network/subnet numbers are assigned to them.Network mask A 32-bit number indicating the range of IP addresses residing on a single IP network/subnet. This specification displays network masks as hexadecimal numbers. For example, the network mask for a class C IP network is displayed as 0xffffff00. Such a mask is often displayed elsewhere in the literature as 255.255.255.0.Multi-access networks Those physical networks that support the attachment of multiple (more than two) routers. Each pair of routers on such a network is assumed to be able to communicate directly (e.g., multi-drop networks are excluded).Interface The connection between a router and one of its attached networks. An interface has state information associated with it, which is obtained from the underlying lower level protocols and the routing protocol itself. An interface to a network has associated with it a single IP address and mask (unless the network is an unnumbered point-to-point network). An interface is sometimes also referred to as a link.Neighboring routers Two routers that have interfaces to a common network. On multi- access networks, neighbors are dynamically discovered by OSPF's Hello Protocol.Adjacency A relationship formed between selected neighboring routers for the purpose of exchanging routing information. Not every pair of neighboring routers become adjacent.[Moy] [Page 4] RFC 1247 OSPF Version 2 July 1991Link state advertisement Describes to the local state of a router or network. This includes the state of the router's interfaces and adjacencies. Each link state advertisement is flooded throughout the routing domain. The collected link state advertisements of all routers and networks forms the protocol's topological database.Hello protocol The part of the OSPF protocol used to establish and maintain neighbor relationships. On multi-access networks the Hello protocol can also dynamically discover neighboring routers.Designated Router Each multi-access network that has at least two attached routers has a Designated Router. The Designated Router generates a link state advertisement for the multi-access network and has other special responsibilities in the running of the protocol. The Designated Router is elected by the Hello Protocol. The Designated Router concept enables a reduction in the number of adjacencies required on a multi-access network. This in turn reduces the amount of routing protocol traffic and the size of the topological database.Lower-level protocols The underlying network access protocols that provide services to the Internet Protocol and in turn the OSPF protocol. Examples of these are the X.25 packet and frame levels for PDNs, and the ethernet data link layer for ethernets.1.3 Brief history of SPF-based routing technologyOSPF is an SPF-based routing protocol. Such protocols are also referredto in the literature as link-state or distributed-database protocols.This section gives a brief description of the developments in SPF-basedtechnology that have influenced the OSPF protocol.The first SPF-based routing protocol was developed for use in theARPANET packet switching network. This protocol is described in[McQuillan]. It has formed the starting point for all other SPF-basedprotocols. The homogeneous Arpanet environment, i.e., single-vendorpacket switches connected by synchronous serial lines, simplified thedesign and implementation of the original protocol.Modifications to this protocol were proposed in [Perlman]. Thesemodifications dealt with increasing the fault tolerance of the routingprotocol through, among other things, adding a checksum to the link[Moy] [Page 5] RFC 1247 OSPF Version 2 July 1991state advertisements (thereby detecting database corruption). The paperalso included means for reducing the routing traffic overhead in anSPF-based protocol. This was accomplished by introducing mechanismswhich enabled the interval between link state advertisements to beincreased by an order of magnitude.An SPF-based algorithm has also been proposed for use as an ISO IS-ISrouting protocol. This protocol is described in [DEC]. The protocolincludes methods for data and routing traffic reduction when operatingover broadcast networks. This is accomplished by election of aDesignated Router for each broadcast network, which then originates alink state advertisement for the network.The OSPF subcommittee of the IETF has extended this work in developingthe OSPF protocol. The Designated Router concept has been greatlyenhanced to further reduce the amount of routing traffic required.Multicast capabilities are utilized for additional routing bandwidthreduction. An area routing scheme has been developed enablinginformation hiding/protection/reduction. Finally, the algorithm hasbeen modified for efficient operation in the internet environment.1.4 Organization of this documentThe first three sections of this specification give a general overviewof the protocol's capabilities and functions. Sections 4-16 explain theprotocol's mechanisms in detail. Packet formats, protocol constants,configuration items and required management statistics are specified inthe appendices.Labels such as HelloInterval encountered in the text refer to protocolconstants. They may or may not be configurable. The architecturalconstants are explained in Appendix B. The configurable constants areexplained in Appendix C.The detailed specification of the protocol is presented in terms of datastructures. This is done in order to make the explanation more precise.Implementations of the protocol are required to support thefunctionality described, but need not use the precise data structuresthat appear in this paper.2. The Topological DatabaseThe database of the Autonomous System's topology describes a directedgraph. The vertices of the graph consist of routers and networks. Agraph edge connects two routers when they are attached via a physicalpoint-to-point network. An edge connecting a router to a network[Moy] [Page 6] RFC 1247 OSPF Version 2 July 1991indicates 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, trafficthat is neither locally originated nor locally destined. Vertices thatcan carry transit traffic are indicated on the graph by having bothincoming 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 1991The neighborhood of each network node in the graph depends on whetherthe network has multi-access capabilities (either broadcast or non-broadcast) and, if so, the number of routers having an interface to thenetwork. The three cases are depicted in Figure 1. Rectangles indicaterouters. Circles and oblongs indicate multi-access networks. Routernames are prefixed with the letters RT and network names with N. Routerinterface names are prefixed by I. Lines between routers indicatepoint-to-point networks. The left side of the figure shows a networkwith its connected routers, with the resulting graph shown on the right.Two routers joined by a point-to-point network are represented in thedirected graph as being directly connected by a pair of edges, one ineach direction. Interfaces to physical point-to-point networks need notbe assigned IP addresses. Such a point-to-point network is calledunnumbered. The graphical representation of point-to-point networks isdesigned so that unnumbered networks can be supported naturally. Wheninterface addresses exist, they are modelled as stub routes. Note thateach router would then have a stub connection to the other router'sinterface address (see Figure 1).When multiple routers are attached to a multi-access network, thedirected graph shows all routers bidirectionally connected to thenetwork vertex (again, see Figure 1). If only a single router isattached to a multi-access network, the network will appear in thedirected graph as a stub connection.Each network (stub or transit) in the graph has an IP address andassociated network mask. The mask indicates the number of nodes on thenetwork. Hosts attached directly to routers (referred to as hostroutes) appear on the graph as stub networks. The network mask for ahost route is always 0xffffffff, which indicates the presence of asingle node.Figure 2 shows a sample map of an Autonomous System. The rectanglelabelled H1 indicates a host, which has a SLIP connection to routerRT12. 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 1991routers indicate physical point-to-point networks. The only point-to-point network that has been assigned interface addresses is the onejoining routers RT6 and RT10. Routers RT5 and RT7 have EGP connectionsto other Autonomous Systems. A set of EGP-learned routes have beendisplayed 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 thecost, the more likely the interface is to be used to forward datatraffic. Costs are also associated with the externally derived routingdata (e.g., the EGP-learned routes).The directed graph resulting from the map in Figure 2 is depicted inFigure 3. Arcs are labelled with the cost of the corresponding routeroutput interface. Arcs having no labelled cost have a cost of 0. Notethat arcs leading from networks to routers always have cost 0; they aresignificant nonetheless. Note also that the externally derived routingdata appears on the graph as stubs.The topological database (or what has been referred to above as thedirected graph) is pieced together from link state advertisementsgenerated by the routers. The neighborhood of each transit vertex isrepresented in a single, separate link state advertisement. Figure 4shows graphically the link state representation of the two kinds oftransit 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 1991interface to two broadcast networks and a SLIP line to a host. NetworkN6 is a broadcast network with three attached routers. The cost of alllinks from network N6 to its attached routers is 0. Note that the linkstate advertisement for network N6 is actually generated by one of theattached routers: the router that has been elected Designated Router forthe network.2.1 The shortest-path treeWhen no OSPF areas are configured, each router in the Autonomous Systemhas an identical topological database, leading to an identical graphicalrepresentation. A router generates its routing table from this graph bycalculating a tree of shortest paths with the router itself as root.Obviously, the shortest-path tree depends on the router doing thecalculation. The shortest-path tree for router RT6 in our example isdepicted 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 forwardingprocess. Note also that the best route to any router has also beencalculated. For the processing of external data, we note the next hopand distance to any router advertising external routes. The resultingrouting table for router RT6 is pictured in Table 2. Note that there isa 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 asdashed lines on the shortest path tree in Figure 5. Use of thisexternally derived routing information is considered in the nextsection. ______________________________________ (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 informationAfter the tree is created the external routing information is examined.This external routing information may originate from another routingprotocol such as EGP, or be statically configured (static routes).Default routes can also be included as part of the Autonomous System'sexternal routing information.External routing information is flooded unaltered throughout the AS. Inour example, all the routers in the Autonomous System know that routerRT7 has two external routes, with metrics 2 and 9.OSPF supports two types of external metrics. Type 1 external metricsare equivalent to the link state metric. Type 2 external metrics aregreater than the cost of any path internal to the AS. Use of Type 2external metrics assumes that routing between AS'es is the major cost ofrouting a packet, and eliminates the need for conversion of externalcosts to internal link state metrics.Here is an example of Type 1 external metric processing. Suppose thatthe routers RT7 and RT5 in Figure 2 are advertising Type 1 externalmetrics. For each external route, the distance from Router RT6 iscalculated as the sum of the external route's cost and the distance from[Moy] [Page 11] RFC 1247 OSPF Version 2 July 1991Router RT6 to the advertising router. For every external destination,the router advertising the shortest route is discovered, and the nexthop to the advertising router becomes the next hop to the destination.Both Router RT5 and RT7 are advertising an external route to destinationnetwork N12. Router RT7 is preferred since it is advertising N12 at adistance 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 tablewhen external routes are examined: Destination Next Hop Distance __________________________________ N12 RT10 10 N13 RT5 14 N14 RT5 14 N15 RT10 17 Table 3: The portion of router RT6's routing table listing external destinations.Processing of Type 2 external metrics is simpler. The AS boundaryrouter advertising the smallest external metric is chosen, regardless ofthe internal distance to the AS boundary router. Suppose in our exampleboth router RT5 and router RT7 were advertising Type 2 external routes.Then all traffic destined for network N12 would be forwarded to routerRT7, since 2 < 8. When several equal-cost Type 2 routes exist, theinternal distance to the advertising routers is used to break the tie.Both Type 1 and Type 2 external metrics can be present in the AS at thesame time. In that event, Type 1 external metrics always takeprecedence.This section has assumed that packets destined for external destinationsare always routed through the advertising AS boundary router. This isnot always desirable. For example, suppose in Figure 2 there is anadditional router attached to network N6, called Router RTX. Supposefurther that RTX does not participate in OSPF routing, but does exchangeEGP information with the AS boundary router RT7. Then, router RT7 wouldend up advertising OSPF external routes for all destinations that shouldbe routed to RTX. An extra hop will sometimes be introduced if packetsfor these destinations need always be routed first to router RT7 (theadvertising router).To deal with this situation, the OSPF protocol allows an AS boundary[Moy] [Page 12] RFC 1247 OSPF Version 2 July 1991router to specify a "forwarding address" in its external advertisements.In the above example, Router RT7 would specify RTX's IP address as the"forwarding address" for all those destinations whose packets should berouted directly to RTX.The "forwarding address" has one other application. It enables routersin the Autonomous System's interior to function as "route servers". Forexample, in Figure 2 the router RT6 could become a route server, gainingexternal routing information through a combination of staticconfiguration and external routing protocols. RT6 would then startadvertising itself as an AS boundary router, and would originate acollection of OSPF external advertisements. In each externaladvertisement, router RT6 would specify the correct Autonomous Systemexit point to use for the destination through appropriate setting of theadvertisement's "forwarding address" field.2.3 Equal-cost multipathThe above discussion has been simplified by considering only a singleroute to any destination. In reality, if multiple equal-cost routes toa destination exist, they are all discovered and used. This requires noconceptual changes to the algorithm, and its discussion is postponeduntil we consider the tree-building process in more detail.With equal cost multipath, a router potentially has several availablenext hops towards any given destination.2.4 TOS-based routingOSPF can calculate a separate set of routes for each IP Type of Service.The IP TOS values are represented in OSPF exactly as they appear in theIP packet header. This means that, for any destination, there canpotentially be multiple routing table entries, one for each IP TOS.Up to this point, all examples shown have assumed that routes do notvary on TOS. In order to differentiate routes based on TOS, separateinterface costs can be configured for each TOS. For example, in Figure2 there could be multiple costs (one for each TOS) listed for eachinterface. A cost for TOS 0 must always be specified.When interface costs vary based on TOS, a separate shortest path tree iscalculated for each TOS (see Section 2.1). In addition, external costscan vary based on TOS. For example, in Figure 2 router RT7 couldadvertise a separate type 1 external metric for each TOS. Then, whencalculating the TOS X distance to network N15 the cost of the shortestTOS X path to RT7 would be added to the TOS X cost advertised by RT7[Moy] [Page 13] RFC 1247 OSPF Version 2 July 1991(see Section 2.2).All OSPF implementations must be capable of calculating routes based onTOS. However, OSPF routers can be configured to route all packets onthe TOS 0 path (see Appendix C), eliminating the need to calculate non-zero TOS paths. This can be used to conserve routing table space andprocessing resources in the router. These TOS-0-only routers can bemixed with routers that do route based on TOS. TOS-0-only routers willbe avoided as much as possible when forwarding traffic requesting anon-zero TOS.It may be the case that no path exists for some non-zero TOS, even ifthe router is calculating non-zero TOS paths. In that case, packetsrequesting that non-zero TOS are routed along the TOS 0 path (seeSection 11.1).3. Splitting the AS into AreasOSPF allows collections of contiguous networks and hosts to be groupedtogether. Such a group, together with the routers having interfaces toany one of the included networks, is called an area. Each area runs aseparate copy of the basic SPF routing algorithm. This means that eacharea has its own topological database and corresponding graph, asexplained in the previous section.The topology of an area is invisible from the outside of the area.Conversely, routers internal to a given area know nothing of thedetailed topology external to the area. This isolation of knowledgeenables the protocol to effect a marked reduction in routing traffic ascompared to treating the entire Autonomous System as a single SPFdomain.With the introduction of areas, it is no longer true that all routers inthe AS have an identical topological database. A router actually has aseparate topological database for each area it is connected to.(Routers connected to multiple areas are called area border routers).Two routers belonging to the same area have, for that area, identicalarea topological databases.Routing in the Autonomous System takes place on two levels, depending onwhether the source and destination of a packet reside in the same area(intra-area routing is used) or different areas (inter-area routing isused). In intra-area routing, the packet is routed solely oninformation obtained within the area; no routing information obtainedfrom outside the area can be used. This protects intra-area routingfrom the injection of bad routing information. We discuss inter-arearouting in Section 3.2.[Moy] [Page 14] RFC 1247 OSPF Version 2 July 19913.1 The backbone of the Autonomous SystemThe backbone consists of those networks not contained in any area, theirattached routers, and those routers that belong to multiple areas. Thebackbone must be contiguous.It is possible to define areas in such a way that the backbone is nolonger contiguous. In this case the system administrator must restorebackbone connectivity by configuring virtual links.Virtual links can be configured between any two backbone routers thathave an interface to a common non-backbone area. Virtual links belongto the backbone. The protocol treats two routers joined by a virtuallink as if they were connected by an unnumbered point-to-point network.On the graph of the backbone, two such routers are joined by arcs whosecosts are the intra-area distances between the two routers. The routingprotocol traffic that flows along the virtual link uses intra-arearouting only.The backbone is responsible for distributing routing information betweenareas. The backbone itself has all of the properties of an area. Thetopology of the backbone is invisible to each of the areas, while thebackbone itself knows nothing of the topology of the areas.3.2 Inter-area routingWhen routing a packet between two areas the backbone is used. The paththat the packet will travel can be broken up into three contiguouspieces: an intra-area path from the source to an area border router, abackbone path between the source and destination areas, and then anotherintra-area path to the destination. The algorithm finds the set of suchpaths that have the smallest cost.Looking at this another way, inter-area routing can be pictured asforcing a star configuration on the Autonomous System, with the backboneas hub and and each of the areas as spokes.The topology of the backbone dictates the backbone paths used betweenareas. The topology of the backbone can be enhanced by adding virtuallinks. This gives the system administrator some control over the routestaken by inter-area traffic.The correct area border router to use as the packet exits the sourcearea is chosen in exactly the same way routers advertising externalroutes are chosen. Each area border router in an area summarizes forthe area its cost to all networks external to the area. After the SPFtree is calculated for the area, routes to all other networks are[Moy] [Page 15] RFC 1247 OSPF Version 2 July 1991calculated by examining the summaries of the area border routers.3.3 Classification of routersBefore the introduction of areas, the only OSPF routers having aspecialized function were those advertising external routinginformation, such as router RT5 in Figure 2. When the AS is split intoOSPF areas, the routers are further divided according to function intothe following four overlapping categories:Internal routers A router with all directly connected networks belonging to the same area. Routers with only backbone interfaces also belong to this category. These routers run a single copy of the basic routing algorithm.Area border routers A router that attaches to multiple areas. Area border routers run multiple copies of the basic algorithm, one copy for each attached area and an additional copy for the backbone. Area border routers condense the topological information of their attached areas for distribution to the backbone. The backbone in turn distributes the information to the other areas.Backbone routers A router that has an interface to the backbone. This includes all routers that interface to more than one area (i.e., area border routers). However, backbone routers do not have to be area border routers. Routers with all interfaces connected to the backbone are considered to be internal routers.AS boundary routers A router that exchanges routing information with routers belonging to other Autonomous Systems. Such a router has AS external routes that are advertised throughout the Autonomous System. The path to each AS boundary router is known by every router in the AS. This classification is completely independent of the previous classifications: AS boundary routers may be internal or area border routers, and may or may not participate in the backbone.3.4 A sample area configurationFigure 6 shows a sample area configuration. The first area consists ofnetworks N1-N4, along with their attached routers RT1-RT4. The secondarea consists of networks N6-N8, along with their attached routers RT7,[Moy] [Page 16] RFC 1247 OSPF Version 2 July 1991RT8, RT10, RT11. The third area consists of networks N9-N11 and hostH1, along with their attached routers RT9, RT11, RT12. The third areahas been configured so that networks N9-N11 and host H1 will all begrouped into a single route, when advertised external to the area (seeSection 3.5 for more details).In Figure 6, routers RT1, RT2, RT5, RT6, RT8, RT9 and RT12 are internalrouters. Routers RT3, RT4, RT7, RT10 and RT11 are area border routers.Finally as before, routers RT5 and RT7 are AS boundary routers.Figure 7 shows the resulting topological database for the Area 1. Thefigure completely describes that area's intra-area routing. It alsoshows the complete view of the internet for the two internal routers RT1and RT2. It is the job of the area border routers, RT3 and RT4, toadvertise into Area 1 the distances to all destinations external to thearea. These are indicated in Figure 7 by the dashed stub routes. Also,RT3 and RT4 must advertise into Area 1 the location of the AS boundaryrouters RT5 and RT7. Finally, external advertisements from RT5 and RT7are flooded throughout the entire AS, and in particular throughout Area1. These advertisements are included in Area 1's database, and yieldroutes to networks N12-N15.Routers RT3 and RT4 must also summarize Area 1's topology fordistribution to the backbone. Their backbone advertisements are shownin Table 4. These summaries show which networks are contained in Area 1(i.e., networks N1-N4), and the distance to these networks from therouters RT3 and RT4 respectively.The topological database for the backbone is shown in Figure 8. The setof routers pictured are the backbone routers. Router RT11 is a backbonerouter because it belongs to two areas. In order to make the backboneconnected, a virtual link has been configured between routers R10 andR11. __________________________________________ (Figure not included in text version.) Figure 6: A sample OSPF area configuration __________________________________________[Moy] [Page 17] RFC 1247 OSPF Version 2 July 1991 Network RT3 adv. RT4 adv. _____________________________ N1 4 4 N2 4 4 N3 1 1 N4 2 3 Table 4: Networks advertised to the backbone by routers RT3 and RT4. ______________________________________ (Figure not included in text version.) Figure 7: Area 1's Database Figure 8: The backbone database ______________________________________Again, routers RT3, RT4, RT7, RT10 and RT11 are area border routers. Asrouters RT3 and RT4 did above, they have condensed the routinginformation of their attached areas for distribution via the backbone;these are the dashed stubs that appear in Figure 8. Remember that thethird area has been configured to condense networks N9-N11 and Host H1into a single route. This yields a single dashed line for networks N9-N11 and Host H1 in Figure 8. Routers RT5 and RT7 are AS boundaryrouters; their externally derived information also appears on the graphin Figure 8 as stubs.The backbone enables the exchange of summary information between areaborder routers. Every area border router hears the area summaries fromall other area border routers. It then forms a picture of the distanceto all networks outside of its area by examining the collectedadvertisements, and adding in the backbone distance to each advertisingrouter.Again using routers RT3 and RT4 as an example, the procedure goes asfollows: They first calculate the SPF tree for the backbone. This givesthe distances to all other area border routers. Also noted are thedistances to networks (Ia and Ib) and AS boundary routers (RT5 and RT7)that belong to the backbone. This calculation is shown in Table 5.Next, by looking at the area summaries from these area border routers,RT3 and RT4 can determine the distance to all networks outside their[Moy] [Page 18] RFC 1247 OSPF Version 2 July 1991 Area border dist from dist from router RT3 RT4 ______________________________________ to RT3 * 21 to RT4 22 * to RT7 20 14 to RT10 15 22 to RT11 18 25 ______________________________________ to Ia 20 27 to Ib 15 22 ______________________________________ to RT5 14 8 to RT7 20 14 Table 5: Backbone distances calculated by routers RT3 and RT4.area. These distances are then advertised internally to the area by RT3and RT4. The advertisements that router RT3 and RT4 will make into Area1 are shown in Table 6. Note that Table 6 assumes that an area rangehas been configured for the backbone which groups I5 and I6 into asingle advertisement.The information imported into Area 1 by routers RT3 and RT4 enables aninternal router, such as RT1, to choose an area border routerintelligently. Router RT1 would use RT4 for traffic to network N6, RT3for traffic to network N10, and would load share between the two for Destination RT3 adv. RT4 adv. _________________________________ Ia,Ib 15 22 N6 16 15 N7 20 19 N8 18 18 N9-N11,H1 19 26 _________________________________ RT5 14 8 RT7 20 14 Table 6: Destinations advertised into Area 1 by routers RT3 and RT4.[Moy] [Page 19] RFC 1247 OSPF Version 2 July 1991traffic to network N8.Router RT1 can also determine in this manner the shortest path to the ASboundary routers RT5 and RT7. Then, by looking at RT5 and RT7'sexternal advertisements, router RT1 can decide between RT5 or RT7 whensending to a destination in another Autonomous System (one of thenetworks N12-N15).Note that a failure of the line between routers RT6 and RT10 will causethe backbone to become disconnected. Configuring another virtual linkbetween routers RT7 and RT10 will give the backbone more connectivityand more resistance to such failures. Also, a virtual link between RT7and RT10 would allow a much shorter path between the third area(containing N9) and the router RT7, which is advertising a good route toexternal network N12.3.5 IP subnetting supportOSPF attaches an IP address mask to each advertised route. The maskindicates the range of addresses being described by the particularroute. For example, a summary advertisement for the destination128.185.0.0 with a mask of 0xffff0000 actually is describing a singleroute to the collection of destinations 128.185.0.0 - 128.185.255.255.Similarly, host routes are always advertised with a mask of 0xffffffff,indicating the presence of only a single destination.Including the mask with each advertised destination enables theimplementation of what is commonly referred to as variable-length subnetmasks. This means that a single IP class A, B, or C network number canbe broken up into many subnets of various sizes. For example, thenetwork 128.185.0.0 could be broken up into 64 variable-sized subnets:16 subnets of size 4K, 16 subnets of size 256, and 32 subnets of size 8.Table 7 shows some of the resulting network addresses together withtheir masks: Network address IP address mask Subnet size _______________________________________________ 128.185.16.0 0xfffff000 4K 128.185.1.0 0xffffff00 256 128.185.0.8 0xfffffff8 8 Table 7: Some sample subnet sizes.[Moy] [Page 20] RFC 1247 OSPF Version 2 July 1991There are many possible ways of dividing up a class A, B, and C networkinto variable sized subnets. The precise procedure for doing so isbeyond the scope of this specification. The specification howeverestablishes the following guideline: When an IP packet is forwarded, itis always forwarded to the network that is the best match for thepacket's destination. Here best match is synonymous with the longest ormost specific match. For example, the default route with destination of0.0.0.0 and mask 0x00000000 is always a match for every IP destination.Yet it is always less specific than any other match. Subnet masks mustbe assigned so that the best match for any IP destination isunambiguous.The OSPF area concept is modelled after an IP subnetted network. OSPFareas have been loosely defined to be a collection of networks. Inactuality, an OSPF area is specified to be a list of address ranges (seeSection C.2 for more details). Each address range is defined as an[address,mask] pair. Many separate networks may then be contained in asingle address range, just as a subnetted network is composed of manyseparate subnets. Area border routers then summarize the area contents(for distribution to the backbone) by advertising a single route foreach address range. The cost of the route is the minimum cost to any ofthe networks falling in the specified range.For example, an IP subnetted network can be configured as a single OSPFarea. In that case, the area would be defined as a single addressrange: a class A, B, or C network number along with its natural IP mask.Inside the area, any number of variable sized subnets could be defined.External to the area, a single route for the entire subnetted networkwould be distributed, hiding even the fact that the network is subnettedat all. The cost of this route is the minimum of the set of costs tothe component subnets.3.6 Supporting stub areasIn some Autonomous Systems, the majority of the topological database mayconsist of external advertisements. An OSPF external advertisement isusually flooded throughout the entire AS. However, OSPF allows certainareas to be configured as "stub areas". External advertisements are notflooded into/throughout stub areas; routing to AS external destinationsin these areas is based on a (per-area) default only. This reduces thetopological database size, and therefore the memory requirements, for astub area's internal routers.In order to take advantage of the OSPF stub area support, defaultrouting must be used in the stub area. This is accomplished as follows.One or more of the stub area's area border routers must advertise adefault route into the stub area via summary advertisements. These[Moy] [Page 21] RFC 1247 OSPF Version 2 July 1991summary defaults are flooded throughout the stub area, but no further.(For this reason these defaults pertain only to the particular stubarea). These summary default routes will match any destination that isnot explicitly reachable by an intra-area or inter-area path (i.e., ASexternal destinations).An area can be configured as stub when there is a single exit point fromthe area, or when the choice of exit point need not be made on a per-external-destination basis. For example, area 3 in Figure 6 could beconfigured as a stub area, because all external traffic must travelthough its single area border router RT11. If area 3 were configured asa stub, router RT11 would advertise a default route for distributioninside area 3 (in a summary advertisement), instead of flooding theexternal advertisements for networks N12-N15 into/throughout the area.The OSPF protocol ensures that all routers belonging to an area agree onwhether the area has been configured as a stub. This guarantees that noconfusion will arise in the flooding of external advertisements.There are a couple of restrictions on the use of stub areas. Virtuallinks cannot be configured through stub areas. In addition, AS boundaryrouters cannot be placed internal to stub areas.3.7 Partitions of areasOSPF does not actively attempt to repair area partitions. When an areabecomes partitioned, each component simply becomes a separate area. Thebackbone then performs routing between the new areas. Some destinationsreachable via intra-area routing before the partition will now requireinter-area routing.In the previous section, an area was described as a list of addressranges. Any particular address range must still be completely containedin a single component of the area partition. This has to do with theway the area contents are summarized to the backbone. Also, thebackbone itself must not partition. If it does, parts of the AutonomousSystem will become unreachable. Backbone partitions can be repaired byconfiguring virtual links (see Section 15).Another way to think about area partitions is to look at the AutonomousSystem graph that was introduced in Section 2. Area IDs can be viewedas colors for the graph's edges.[1] Each edge of the graph connects to anetwork, or is itself a point-to-point network. In either case, theedge is colored with the network's Area ID.A group of edges, all having the same color, and interconnected byvertices, represents an area. If the topology of the Autonomous System[Moy] [Page 22] RFC 1247 OSPF Version 2 July 1991is intact, the graph will have several regions of color, each colorbeing a distinct Area ID.When the AS topology changes, one of the areas may become partitioned.The graph of the AS will then have multiple regions of the same color(Area ID). The routing in the Autonomous System will continue tofunction as long as these regions of same color are connected by thesingle backbone region.[Moy] [Page 23] RFC 1247 OSPF Version 2 July 19914. Functional SummaryA separate copy of OSPF's basic routing algorithm runs in each area.Routers having interfaces to multiple areas run multiple copies of thealgorithm. A brief summary of the routing algorithm follows.When a router starts, it first initializes the routing protocol datastructures. The router then waits for indications from the lower-levelprotocols that its interfaces are functional.A router then uses the OSPF's Hello Protocol to acquire neighbors. Therouter sends Hello packets to its neighbors, and in turn receives theirHello packets. On broadcast and point-to-point networks, the routerdynamically detects its neighboring routers by sending its Hello packetsto the multicast address AllSPFRouters. On non-broadcast networks, someconfiguration information is necessary in order to discover neighbors.On all multi-access networks (broadcast or non-broadcast), the HelloProtocol also elects a Designated router for the network.The router will attempt to form adjacencies with some of its newlyacquired neighbors. Topological databases are synchronized betweenpairs of adjacent routers. On multi-access networks, the DesignatedRouter determines which routers should become adjacent.Adjacencies control the distribution of routing protocol packets.Routing protocol packets are sent and received only on adjacencies. Inparticular, distribution of topological database updates proceeds alongadjacencies.A router periodically advertises its state, which is also called linkstate. Link state is also advertised when a router's state changes. Arouter's adjacencies are reflected in the contents of its link stateadvertisements. This relationship between adjacencies and link stateallows the protocol to detect dead routers in a timely fashion.Link state advertisements are flooded throughout the area. The floodingalgorithm is reliable, ensuring that all routers in an area have exactlythe same topological database. This database consists of the collectionof link state advertisements received from each router belonging to thearea. From this database each router calculates a shortest-path tree,with itself as root. This shortest-path tree in turn yields a routingtable for the protocol.4.1 Inter-area routingThe previous section described the operation of the protocol within asingle area. For intra-area routing, no other routing information is[Moy] [Page 24] RFC 1247 OSPF Version 2 July 1991pertinent. In order to be able to route to destinations outside of thearea, the area border routers inject additional routing information intothe area. This additional information is a distillation of the rest ofthe Autonomous System's topology.This distillation is accomplished as follows: Each area border router isby definition connected to the backbone. Each area border routersummarizes the topology of its attached areas for transmission on thebackbone, and hence to all other area border routers. A area borderrouter then has complete topological information concerning thebackbone, and the area summaries from each of the other area borderrouters. From this information, the router calculates paths to alldestinations not contained in its attached areas. The router thenadvertises these paths to its attached areas. This enables the area'sinternal routers to pick the best exit router when forwarding traffic todestinations in other areas.4.2 AS external routesRouters that have information regarding other Autonomous Systems canflood this information throughout the AS. This external routinginformation is distributed verbatim to every participating router.There is one exception: external routing information is not flooded into"stub" areas (see Section 3.6).To utilize external routing information, the path to all routersadvertising external information must be known throughout the AS(excepting the stub areas). For that reason, the locations of these ASboundary routers are summarized by the (non-stub) area border routers.4.3 Routing protocol packetsThe OSPF protocol runs directly over IP, using IP protocol 89. OSPFdoes not provide any explicit fragmentation/reassembly support. Whenfragmentation is necessary, IP fragmentation/reassembly is used. OSPFprotocol packets have been designed so that large protocol packets cangenerally be split into several smaller protocol packets. This practiceis recommended; IP fragmentation should be avoided whenever possible.Routing protocol packets should always be sent with the IP TOS field setto 0. If at all possible, routing protocol packets should be givenpreference over regular IP data traffic, both when being sent andreceived. As an aid to accomplishing this, OSPF protocol packets shouldhave their IP precedence field set to the value Internetwork Control(see [RFC 791]).[Moy] [Page 25] RFC 1247 OSPF Version 2 July 1991All OSPF protocol packets share a common protocol header that isdescribed in Appendix A. The OSPF packet types are listed below inTable 8. Their formats are also described in Appendix A. Type Packet name Protocol function __________________________________________________________ 1 Hello Discover/maintain neighbors 2 Database Description Summarize database contents 3 Link State Request Database download 4 Link State Update Database update 5 Link State Ack Flooding acknowledgment Table 8: OSPF packet types.OSPF's Hello protocol uses Hello packets to discover and maintainneighbor relationships. The Database Description and Link State Requestpackets are used in the forming of adjacencies. OSPF's reliable updatemechanism is implemented by the Link State Update and Link StateAcknowledgment packets.Each Link State Update packet carries a set of new link stateadvertisements one hop further away from their point of origination. Asingle Link State Update packet may contain the link stateadvertisements of several routers. Each advertisement is tagged withthe ID of the originating router and a checksum of its link statecontents. The five different types of OSPF link state advertisementsare listed below in Table 9.LS Advertisement Advertisement descriptiontype name____________________________________________________________________________1 Router links advs. Originated by all routers. This advs. advertisement describes the collected states of the router's interfaces to an area. Flooded throughout a single area only.____________________________________________________________________________2 Network links Originated for multi-access networks by advs. the Designated Router. This advertisement contains the list of routers connected to the network. Flooded throughout a single area only.[Moy] [Page 26] RFC 1247 OSPF Version 2 July 1991LS Advertisement Advertisement descriptiontype name________________________________________________________________________________________________________________________________________________________3,4 Summary link Originated by area border routers, and advs. flooded throughout their associated area. Each summary link advertisement describes a route to a destination outside the area, yet still inside the AS (i.e., an inter-area route). Type 3 advertisements describe routes to networks. Type 4 advertisements describe routes to AS boundary routers.____________________________________________________________________________5 AS external Originated by AS boundary routers, and link advs. flooded throughout the AS. Each external advertisement describes a route to a destination in another Autonomous System. Default routes for the AS can also be described by AS external advertisements. Table 9: OSPF link state advertisements.As mentioned above, OSPF routing packets (with the exception of Hellos)are sent only over adjacencies. Note that this means that all protocolpackets travel a single IP hop, except those that are sent over virtualadjacencies. The IP source address of an OSPF protocol packet is oneend of a router adjacency, and the IP destination address is either theother end of the adjacency or an IP multicast address.4.4 Basic implementation requirementsAn implementation of OSPF requires the following pieces of systemsupport:Timers Two different kind of timers are required. The first kind, called single shot timers, fire once and cause a protocol event to be processed. The second kind, called interval timers, fire at continuous intervals. These are used for the sending of packets at regular intervals. A good example of this is the regular broadcast of Hello packets (on broadcast networks). The granularity of both kinds of timers is one second. Interval timers should be implemented to avoid drift. In some[Moy] [Page 27] RFC 1247 OSPF Version 2 July 1991 router implementations, packet processing can affect timer execution. When multiple routers are attached to a single network, all doing broadcasts, this can lead to the synchronization of routing packets (which should be avoided). If timers cannot be implemented to avoid drift, small random amounts should be added to/subtracted from the timer interval at each firing.IP multicast Certain OSPF packets use IP multicast. Support for receiving and sending IP multicasts, along with the appropriate lower-level protocol support, is required. These IP multicast packets never travel more than one hop. For information on IP multicast, see [RFC 1112].Lower-level protocol support The lower level protocols referred to here are the network access protocols, such as the Ethernet data link layer. Indications must be passed from from these protocols to OSPF as the network interface goes up and down. For example, on an ethernet it would be valuable to know when the ethernet transceiver cable becomes unplugged.Non-broadcast lower-level protocol support Remember that non-broadcast networks are multi-access networks such as a X.25 PDN. On these networks, the Hello Protocol can be aided by providing an indication to OSPF when an attempt is made to send a packet to a dead or non-existent router. For example, on a PDN a dead router may be indicated by the reception of a X.25 clear with an appropriate cause and diagnostic, and this information would be passed to OSPF.List manipulation primitives Much of the OSPF functionality is described in terms of its operation on lists of link state advertisements. For example, the advertisements that will be retransmitted to an adjacent router until acknowledged are described as a list. Any particular advertisement may be on many such lists. An OSPF implementation needs to be able to manipulate these lists, adding and deleting constituent advertisements as necessary.Tasking support Certain procedures described in this specification invoke other procedures. At times, these other procedures should be executed in-line, that is, before the current procedure is finished. This is indicated in the text by instructions to execute a procedure. At other times, the other procedures are to be executed only when the current procedure has finished. This is indicated by instructions to schedule a task.[Moy] [Page 28] RFC 1247 OSPF Version 2 July 19914.5 Optional OSPF capabilitiesThe OSPF protocol defines several optional capabilities. A routerindicates the optional capabilities that it supports in its OSPF Hellopackets, Database Description packets and in its link stateadvertisements. This enables routers supporting a mix of optionalcapabilities to coexist in a single Autonomous System.Some capabilities must be supported by all routers attached to aspecific area. In this case, a router will not accept a neighbor'sHello unless there is a match in reported capabilities (i.e., acapability mismatch prevents a neighbor relationship from forming). Anexample of this is the external routing capability (see below).Other capabilities can be negotiated during the database synchronizationprocess. This is accomplished by specifying the optional capabilitiesin Database Description packets. A capability mismatch with a neighboris this case will result in only a subset of link state advertisementsbeing exchanged between the two neighbors.The routing table build process can also be affected by thepresence/absence of optional capabilities. For example, since theoptional capabilities are reported in link state advertisements, routersincapable of certain functions can be avoided when building the shortestpath tree. An example of this is the TOS routing capability (seebelow).The current OSPF optional capabilities are listed below. See SectionA.2 for more information.External routing capability Entire OSPF areas can be configured as "stubs" (see Section 3.6). AS external advertisements will not be flooded into stub areas. This capability is represented by the E-bit in the OSPF options field (see Section A.2). In order to ensure consistent configuration of stub areas, all routers interfacing to such an area must have the E-bit clear in their Hello packets (see Sections 9.5 and 10.5).TOS capability All OSPF implementations must be able to calculate separate routes based on IP Type of Service. However, to save routing table space and processing resources, an OSPF router can be configured to ignore TOS when forwarding packets. In this case, the router calculates routes for TOS 0 only. This capability is represented by the T-bit in the OSPF options field (see Section A.2). TOS-capable routers will attempt to avoid non-TOS-capable routers when calculating non-[Moy] [Page 29] RFC 1247 OSPF Version 2 July 1991 zero TOS paths.5. Protocol Data StructuresThe OSPF protocol is described in this specification in terms of itsoperation on various protocol data structures. The following listcomprises the top-level OSPF data structures. Any initialization thatneeds to be done is noted. Areas, OSPF interfaces and neighbors alsohave associated data structures that are described later in thisspecification.Router ID a 32-bit number that uniquely identifies this router in the AS. One possible implementation strategy would be to use the smallest IP interface address belonging to the router.Pointers to area structures Each one of the areas to which the router is connected has its own data structure. This data structure describes the working of the basic algorithm. Remember that each area runs a separate copy of the basic algorithm.Pointer to the backbone structure The basic algorithm operates on the backbone as if it were an area. For this reason the backbone is represented as an area structure.Virtual links configured The virtual links configured with this router as one endpoint. In order to have configured virtual links, the router itself must be an area border router. Virtual links are identified by the Router ID of the other endpoint -- which is another area border router. These two endpoint routers must be attached to a common area, called the virtual link's transit area. Virtual links are part of the backbone, and behave as if they were unnumbered point-to-point networks between the two routers. A virtual link uses the intra- area routing of its transit area to forward packets. Virtual links are brought up and down through the building of the shortest-path trees for the transit area.List of external routes These are routes to destinations external to the Autonomous System, that have been gained either through direct experience with another routing protocol (such as EGP), or through configuration information, or through a combination of the two (e.g., dynamic external info. to be advertised by OSPF with configured metric). Any router having these external routes is called an AS boundary[Moy] [Page 30] RFC 1247 OSPF Version 2 July 1991 router. These routes are advertised by the router to the entire AS through AS external link advertisements.List of AS external link advertisements Part of the topological database. These have have originated from the AS boundary routers. They comprise routes to destinations external to the Autonomous System. Note that, if the router is itself an AS boundary router, some of these AS external link advertisements have been self originated.The routing table Derived from the topological database. Each destination that the router can forward to is represented by a cost and a set of paths. A path is described by its type and next hop. For more information, see Section 11.TOS capability This item indicates whether the router will calculate separate routes based on TOS. This is a configurable parameter. For more information, see Sections 4.5 and 16.9.Figure 9 shows the collection of data structures present in a typicalrouter. The router pictured is RT10, from the map in Figure 6. Notethat router RT10 has a virtual link configured to router RT11, with Area2 as the link's transit area. This is indicated by the dashed line inFigure 9. When the virtual link becomes active, through the building ofthe shortest path tree for Area 2, it becomes an interface to thebackbone (see the two backbone interfaces depicted in Figure 9).6. The Area Data StructureThe area data structure contains all the information used to run thebasic routing algorithm. Remember that each area maintains its owntopological database. Router interfaces and adjacencies belong to a _______________________________________ (Figure not included in text version.) Figure 9: Router RT10's Data Structures _______________________________________[Moy] [Page 31] RFC 1247 OSPF Version 2 July 1991single area.The backbone has all the properties of an area. For that reason it isalso represented by an area data structure. Note that some items in thestructure apply differently to the backbone than to areas.The area topological (or link state) database consists of the collectionof router links, network links and summary links advertisements thathave originated from the area's routers. This information is floodedthroughout a single area only. The list of AS external advertisementsis also considered to be part of each area's topological database.Area ID A 32-bit number identifying the area. 0 is reserved for the area ID of the backbone. If assigning subnetted networks as separate areas, the IP network number could be used as the Area ID.List of component address ranges The address ranges that define the area. Each address range is specified by an [address,mask] pair. Each network is then assigned to an area depending on the address range that it falls into (specified address ranges are not allowed to overlap). As an example, if an IP subnetted network is to be its own separate OSPF area, the area is defined to consist of a single address range - an IP network number with its natural (class A, B or C) mask.Associated router interfaces This router's interfaces connecting to the area. A router interface belongs to one and only one area (or the backbone). For the backbone structure this list includes all the virtual adjacencies. A virtual adjacency is identified by the router ID of its other endpoint; its cost is the cost of the shortest intra-area path that exists between the two routers.List of router links advertisements A router links advertisement is generated by each router in the area. It describes the state of the router's interfaces to the area.List of network links advertisements One network links advertisement is generated for each transit multi-access network in the area. It describes the set of routers currently connected to the network.List of summary links advertisements Summary link advertisements originate from the area's area border routers. They describe routes to destinations internal to the[Moy] [Page 32] RFC 1247 OSPF Version 2 July 1991 Autonomous System, yet external to the area.Shortest-path tree The shortest-path tree for the area, with this router itself as root. Derived from the collected router links and network links advertisements by the Dijkstra algorithm.Authentication type The type of authentication used for this area. Authentication types are defined in Appendix E. All OSPF packet exchanges are authenticated. Different authentication schemes may be used in different areas.External routing capability Whether AS external advertisements will be flooded into/throughout the area. This is a configurable parameter. If AS external advertisements are excluded from the area, the area is called a "stub". Internal to stub areas, routing to external destinations will be based solely on a default summary route. The backbone cannot be configured as a stub area. Also, virtual links cannot be configured through stub areas. For more information, see Section 3.6.StubDefaultCost If the area has been configured as a stub area, and the router itself is an area border router, then the StubDefaultCost indicates the cost of the default summary link that the router should advertise into the area. There can be a separate cost configured for each IP TOS. See Section 12.4.3 for more information.Unless otherwise specified, the remaining sections of this documentrefer to the operation of the protocol in a single area.7. Bringing Up AdjacenciesOSPF creates adjacencies between neighboring routers for the purpose ofexchanging routing information. Not every two neighboring routers willbecome adjacent. This section covers the generalities involved increating adjacencies. For further details consult Section 10.7.1 The Hello ProtocolThe Hello Protocol is responsible for establishing and maintainingneighbor relationships. It also ensures that communication betweenneighbors is bidirectional. Hello packets are sent periodically out all[Moy] [Page 33] RFC 1247 OSPF Version 2 July 1991router interfaces. Bidirectional communication is indicated when therouter sees itself listed in the neighbor's Hello Packet.On multi-access networks, the Hello Protocol elects a Designated Routerfor the network. Among other things, the Designated Router controlswhat adjacencies will be formed over the network (see below).The Hello Protocol works differently on broadcast networks, as comparedto non-broadcast networks. On broadcast networks, each routeradvertises itself by periodically multicasting Hello Packets. Thisallows neighbors to be discovered dynamically. These Hello Packetscontain the router's view of the Designated Router's identity, and thelist of routers whose Hellos have been seen recently.On non-broadcast networks some configuration information is necessaryfor the operation of the Hello Protocol. Each router that maypotentially become Designated Router has a list of all other routersattached to the network. A router, having Designated Router potential,sends hellos to all other potential Designated Routers when itsinterface to the non-broadcast network first becomes operational. Thisis an attempt to find the Designated Router for the network. If therouter itself is elected Designated Router, it begins sending hellos toall other routers attached to the network.After a neighbor has been discovered, bidirectional communicationensured, and (if on a multi-access network) a Designated Router elected,a decision is made regarding whether or not an adjacency should beformed with the neighbor (see Section 10.4). An attempt is always madeto establish adjacencies over point-to-point networks and virtual links.The first step in bringing up an adjacency is to synchronize theneighbors' topological databases. This is covered in the next section.7.2 The Synchronization of DatabasesIn an SPF-based routing algorithm, it is very important for all routers'topological databases to stay synchronized. OSPF simplifies this byrequiring only adjacent routers to remain synchronized. Thesynchronization process begins as soon as the routers attempt to bringup the adjacency. Each router describes its database by sending asequence of Database Description packets to its neighbor. Each DatabaseDescription Packet describes a set of link state advertisementsbelonging to the database. When the neighbor sees a link stateadvertisement that is more recent than its own database copy, it makes anote that this newer advertisement should be requested.This sending and receiving of Database Description packets is called the"Database Exchange Process". During this process, the two routers form[Moy] [Page 34] RFC 1247 OSPF Version 2 July 1991a master/slave relationship. Each Database Description Packet has asequence number. Database Description Packets sent by the master(polls) are acknowledged by the slave through echoing of the sequencenumber. Both polls and their responses contain summaries of link statedata. The master is the only one allowed to retransmit DatabaseDescription Packets. It does so only at fixed intervals, the length ofwhich is the configured constant RxmtInterval.Each Database Description contains an indication that there are morepackets to follow --- the M-bit. The Database Exchange Process is overwhen a router has received and sent Database Description Packets withthe M-bit off.During and after the Database Exchange Process, each router has a listof those link state advertisements for which the neighbor has more up-to-date instances. These advertisements are requested in Link StateRequest Packets. Link State Request packets that are not satisfied areretransmitted at fixed intervals of time RxmtInterval. When theDatabase Description Process has completed and all Link State Requestshave been satisfied, the databases are deemed synchronized and therouters are marked fully adjacent. At this time the adjacency is fullyfunctional and is advertised in the two routers' link stateadvertisements.The adjacency is used by the flooding procedure as soon as the DatabaseExchange Process begins. This simplifies database synchronization, andguarantees that it finishes in a predictable period of time.7.3 The Designated RouterEvery multi-access network has a Designated Router. The DesignatedRouter performs two main functions for the routing protocol:o The Designated Router originates a network links advertisement on behalf of the network. This advertisement lists the set of routers (including the Designated Router itself) currently attached to the network. The Link State ID for this advertisement (see Section 12.1.4) is the IP interface address of the Designated Router. The IP network number can then be obtained by using the subnet/network mask.o The Designated router becomes adjacent to all other routers on the network. Since the link state databases are synchronized across adjacencies (through adjacency bring-up and then the flooding procedure), the Designated Router plays a central part in the synchronization process.[Moy] [Page 35] RFC 1247 OSPF Version 2 July 1991The Designated Router is elected by the Hello Protocol. A router'sHello Packet contains its Router Priority, which is configurable on aper-interface basis. In general, when a router's interface to a networkfirst becomes functional, it checks to see whether there is currently aDesignated Router for the network. If there is, it accepts thatDesignated Router, regardless of its Router Priority. (This makes itharder to predict the identity of the Designated Router, but ensuresthat the Designated Router changes less often. See below.) Otherwise,the router itself becomes Designated Router if it has the highest RouterPriority on the network. A more detailed (and more accurate)description of Designated Router election is presented in Section 9.4.The Designated Router is the endpoint of many adjacencies. In order tooptimize the flooding procedure on broadcast networks, the DesignatedRouter multicasts its Link State Update Packets to the addressAllSPFRouters, rather than sending separate packets over each adjacency.Section 2 of this document discusses the directed graph representationof an area. Router nodes are labelled with their Router ID. Broadcastnetwork nodes are actually labelled with the IP address of theirDesignated Router. It follows that when the Designated Router changes,it appears as if the network node on the graph is replaced by anentirely new node. This will cause the network and all its attachedrouters to originate new link state advertisements. Until thetopological databases again converge, some temporary loss ofconnectivity may result. This may result in ICMP unreachable messagesbeing sent in response to data traffic. For that reason, the DesignatedRouter should change only infrequently. Router Priorities should beconfigured so that the most dependable router on a network eventuallybecomes Designated Router.7.4 The Backup Designated RouterIn order to make the transition to a new Designated Router smoother,there is a Backup Designated Router for each multi-access network. TheBackup Designated Router is also adjacent to all routers on the network,and becomes Designated Router when the previous Designated Router fails.If there were no Backup Designated Router, when a new Designated Routerbecame necessary, new adjacencies would have to be formed between therouter and all other routers attached to the network. Part of theadjacency forming process is the synchronizing of topological databases,which can potentially take quite a long time. During this time, thenetwork would not be available for transit data traffic. The BackupDesignated obviates the need to form these adjacencies, since theyalready exist. This means the period of disruption in transit trafficlasts only as long as it take to flood the new link state advertisements(which announce the new Designated Router).[Moy] [Page 36] RFC 1247 OSPF Version 2 July 1991The Backup Designated Router does not generate a network linksadvertisement for the network. (If it did, the transition to a newDesignated Router would be even faster. However, this is a tradeoffbetween database size and speed of convergence when the DesignatedRouter disappears.)The Backup Designated Router is also elected by the Hello Protocol.Each Hello Packet has a field that specifies the Backup DesignatedRouter for the network.In some steps of the flooding procedure, the Backup Designated Routerplays a passive role, letting the Designated Router do more of the work.This cuts down on the amount of local routing traffic. See Section 13.3for more information.7.5 The graph of adjacenciesAn adjacency is bound to the network that the two routers have incommon. If two routers have multiple networks in common, they may havemultiple adjacencies between them.One can picture the collection of adjacencies on a network as forming anundirected graph. The vertices consist of routers, with an edge joiningtwo routers if they are adjacent. The graph of adjacencies describesthe flow of routing protocol packets, and in particular Link StateUpdates, through the Autonomous System.Two graphs are possible, depending on whether the common network ismulti-access. On physical point-to-point networks (and virtual links),the two routers joined by the network will be adjacent after theirdatabases have been synchronized. On multi-access networks, both theDesignated Router and the Backup Designated Router are adjacent to allother routers attached to the network, and these account for alladjacencies.These graphs are shown in Figure 10. It is assumed that router RT7 hasbecome the Designated Router, and router RT3 the Backup DesignatedRouter, for the network N2. The Backup Designated Router performs alesser function during the flooding procedure than the Designated Router(see Section 13.3). This is the reason for the dashed lines connectingthe Backup Designated Router RT3.8. Protocol Packet ProcessingThis section discusses the general processing of routing protocolpackets. It is very important that the router topological databases[Moy] [Page 37] RFC 1247 OSPF Version 2 July 1991remain synchronized. For this reason, routing protocol packets shouldget preferential treatment over ordinary data packets, both in sendingand receiving.Routing protocol packets are sent along adjacencies only (with theexception of Hello packets, which are used to discover the adjacencies).This means that all protocol packets travel a single IP hop, exceptthose sent over virtual links.All routing protocol packets begin with a standard header. The sectionsbelow give the details on how to fill in and verify this standardheader. Then, for each packet type, the section is listed that givesmore details on that particular packet type's processing.8.1 Sending protocol packetsWhen a router sends a routing protocol packet, it fills in the fields ofthat standard header as follows. For more details on the header formatconsult Section A.3.1:Version # Set to 2, the version number of the protocol as documented in this specification.Packet type The type of OSPF packet, such as Link state Update or Hello Packet.Packet length The length of the entire OSPF packet in bytes, including the standard header.Router ID The identity of the router itself (who is originating the packet). ______________________________________ (Figure not included in text version.) Figure 10: The graph of adjacencies Figure 11: Interface state changes ______________________________________[Moy] [Page 38] RFC 1247 OSPF Version 2 July 1991Area ID The area that the packet is being sent into.Checksum The standard IP 16-bit one's complement checksum of the entire OSPF packet, excluding the 64-bit authentication field. This checksum should be calculated before handing the packet to the appropriate authentication procedure.Autype and Authentication Each OSPF packet exchange is authenticated. Authentication types are assigned by the protocol and documented in Appendix E. A different authentication scheme can be used for each OSPF area. The 64-bit authentication field is set by the appropriate authentication procedure (determined by Autype). This procedure should be the last called when forming the packet to be sent. The setting of the authentication field is determined by the packet contents and the authentication key (which is configurable on a per-interface basis).The IP destination address for the packet is selected as follows. Onphysical point-to-point networks, the IP destination is always set tothe the address AllSPFRouters. On all other network types (includingvirtual links), the majority of OSPF packets are sent as unicasts, i.e.,sent directly to the other end of the adjacency. In this case, the IPdestination is just the neighbor IP address associated with the otherend of the adjacency (see Section 10). The only packets not sent asunicasts are on broadcast networks; on these networks Hello packets aresent to the multicast destination AllSPFRouters, the Designated Routerand its Backup send both Link State Update Packets and Link StateAcknowledgment Packets to the multicast address AllSPFRouters, while allother routers send both their Link State Update and Link StateAcknowledgment Packets to the multicast address AllDRouters.Retransmissions of Link State Update packets are ALWAYS sent asunicasts.The IP source address should be set to the IP address of the sendinginterface. Interfaces to unnumbered point-to-point networks have noassociated IP address. On these interfaces, the IP source should be setto any of the other IP addresses belonging to the router. For thisreason, there must be at least one IP address assigned to the router.[2]Note that, for most purposes, virtual links act precisely the same asunnumbered point-to-point networks. However, each virtual link doeshave an interface IP address (discovered during the routing table buildprocess) which is used as the IP source when sending packets over thevirtual link.[Moy] [Page 39] RFC 1247 OSPF Version 2 July 1991For more information on the format of specific packet types, consult thesections listed in Table 10. Type Packet name detailed section (transmit) _________________________________________________________ 1 Hello Section 9.5 2 Database description Section 10.8 3 Link state request Section 10.9 4 Link state update Section 13.3 5 Link state ack Section 13.5 Table 10: Sections describing packet transmission.8.2 Receiving protocol packetsWhenever a protocol packet is received by the router it is marked withthe interface it was received on. For routers that have virtual linksconfigured, it may not be immediately obvious which interface toassociate the packet with. For example, consider the router RT11depicted in Figure 6. If RT11 receives an OSPF protocol packet on itsinterface to network N8, it may want to associate the packet with theinterface to area 2, or with the virtual link to router RT10 (which ispart of the backbone). In the following, we assume that the packet isinitially associated with the non-virtual link.[3]In order for the packet to be accepted at the IP level, it must pass anumber of tests, even before the packet is passed to OSPF forprocessing:o The IP checksum must be correct.o The packet's IP destination address must be the IP address of the receiving interface, or one of the IP multicast addresses AllSPFRouters or AllDRouters.o The IP protocol specified must be OSPF (89).o Locally originated packets should not be passed on to OSPF. That is, the source IP address should be examined to make sure this is not a multicast packet that the router itself generated.[Moy] [Page 40] RFC 1247 OSPF Version 2 July 1991Next, the OSPF packet header is verified. The fields specified in theheader must match those configured for the receiving interface. If theydo not, the packet should be discarded:o The version number field must specify protocol version 2.o The 16-bit checksum of the OSPF packet's contents must be verified. Remember that the 64-bit authentication field must be excluded from the checksum calculation.o The Area ID found in the OSPF header must be verified. If both of the following cases fail, the packet should be discarded. The Area ID specified in the header must either: (1) Match the Area ID of the receiving interface. In this case, the packet has been sent over a single hop. Therefore, the packet's IP source address must be on the same network as the receiving interface. This can be determined by comparing the packet's IP source address to the interface's IP address, after masking both addresses with the interface mask. (2) Indicate the backbone. In this case, the packet has been sent over a virtual link. The receiving router must be an area border router, and the router ID specified in the packet (the source router) must be the other end of a configured virtual link. The receiving interface must also attach to the virtual link's configured transit area. If all of these checks succeed, the packet is accepted and is from now on associated with the virtual link (and the backbone area).o Packets whose IP destination is AllDRouters should only be accepted if the state of the receiving interface is DR or Backup (see Section 9.1).o The Authentication type specified must match the authentication type specified for the associated area.Next, the packet must be authenticated. This depends on theauthentication type specified (see Appendix E). The authenticationprocedure may use an Authentication key, which can be configured on aper-interface basis. If the authentication fails, the packet should bediscarded.If the packet type is Hello, it should then be further processed by theHello Protocol (see Section 10.5). All other packet types aresent/received only on adjacencies. This means that the packet must have[Moy] [Page 41] RFC 1247 OSPF Version 2 July 1991been sent by one of the router's active neighbors. If the receivinginterface is a multi-access network (either broadcast or non-broadcast)the sender is identified by the IP source address found in the packet'sIP header. If the receiving interface is a point-to-point link or avirtual link, the sender is identified by the Router ID (source router)found in the packet's OSPF header. The data structure associated withthe receiving interface contains the list of active neighbors. Packetsnot matching any active neighbor are discarded.At this point all received protocol packets are associated with anactive neighbor. For the further input processing of specific packettypes, consult the sections listed in Table 11. Type Packet name detailed section (receive) ________________________________________________________ 1 Hello Section 10.5 2 Database description Section 10.6 3 Link state request Section 10.7 4 Link state update Section 13 5 Link state ack Section 13.7 Table 11: Sections describing packet reception.9. The Interface Data StructureAn OSPF interface is the connection between a router and a network.There is a single OSPF interface structure for each attached network;each interface structure has at most one IP interface address (seebelow). The support for multiple addresses on a single network is amatter for future consideration.An OSPF interface can be considered to belong to the area that containsthe attached network. All routing protocol packets originated by therouter over this interface are labelled with the interface's Area ID.One or more router adjacencies may develop over an interface. Arouter's link state advertisements reflect the state of its interfacesand their associated adjacencies.The following data items are associated with an interface. Note that anumber of these items are actually configuration for the attachednetwork; those items must be the same for all routers connected to thenetwork.[Moy] [Page 42] RFC 1247 OSPF Version 2 July 1991Type The kind of network to which the interface attaches. Its value is either broadcast, non-broadcast yet still multi-access, point-to- point or virtual link.State The functional level of an interface. State determines whether or not full adjacencies are allowed to form over the interface. State is also reflected in the router's link state advertisements.IP interface address The IP address associated with the interface. This appears as the IP source address in all routing protocol packets originated over this interface. Interfaces to unnumbered point-to-point networks do not have an associated IP address.IP interface mask This indicates the portion of the IP interface address that identifies the attached network. This is often referred to as the subnet mask. Masking the IP interface address with this value yields the IP network number of the attached network.Area ID The Area ID to which the attached network belongs. All routing protocol packets originating from the interface are labelled with this Area ID.HelloInterval The length of time, in seconds, between the Hello packets that the router sends on the interface. Advertised in Hello packets sent out this interface.RouterDeadInterval The number of seconds before the router's neighbors will declare it down, when they stop hearing the router's hellos. Advertised in Hello packets sent out this interface.InfTransDelay The estimated number of seconds it takes to transmit a Link State Update Packet over this interface. Link state advertisements contained in the update packet will have their age incremented by this amount before transmission. This value should take into account transmission and propagation delays; it must be greater than zero.Router Priority An 8-bit unsigned integer. When two routers attached to a network both attempt to become Designated Router, the one with the highest[Moy] [Page 43] RFC 1247 OSPF Version 2 July 1991 Router Priority takes precedence. A router whose Router Priority is set to 0 is ineligible to become Designated Router on the attached network. Advertised in Hello packets sent out this interface.Hello Timer An interval timer that causes the interface to send a Hello packet. This timer fires every HelloInterval seconds. Note that on non- broadcast networks a separate Hello packet is sent to each qualified neighbor.Wait Timer A single shot timer that causes the interface to exit the Waiting state, and as a consequence select a Designated Router on the network. The length of the timer is RouterDeadInterval seconds.List of neighboring routers The other routers attached to this network. On multi-access networks, this list is formed by the Hello Protocol. Adjacencies will be formed to some of these neighbors. The set of adjacent neighbors can be determined by an examination of all of the neighbors' states.Designated Router The Designated Router selected for the attached network. The Designated Router is selected on all multi-access networks by the Hello Protocol. Two pieces of identification are kept for the Designated Router: its Router ID and its interface IP address on the network. The Designated Router advertises link state for the network. The network link state advertisement is labelled with the Designated Router's IP address. This item is initialized to 0, which indicates the lack of a Designated Router.Backup Designated Router The Backup Designated Router is also selected on all multi-access networks by the Hello Protocol. All routers on the attached network become adjacent to both the Designated Router and the Backup Designated Router. The Backup Designated Router becomes Designated Router when the current Designated Router fails. Initialized to 0 indicating the lack of a Backup Designated Router.Interface output cost(s) The cost of sending a packet on the interface, expressed in the link state metric. This is advertised as the link cost for this interface in the router links advertisement. There may be a separate cost for each IP Type of Service. The cost of an interface must be greater than zero.[Moy] [Page 44] RFC 1247 OSPF Version 2 July 1991RxmtInterval The number of seconds between link state advertisement retransmissions, for adjacencies belonging to this interface. Also used when retransmitting Database Description and Link State Request Packets.Authentication key This configured data allows the authentication procedure to generate and/or verify the authentication field in the OSPF header. The authentication key can be configured on a per-interface basis. For example, if the authentication type indicates simple password, the authentication key would be a 64-bit password. This key would be inserted directly into the OSPF header when originating routing protocol packets, and there could be a separate password for each network.9.1 Interface statesThe various states that router interface may attain is documented inthis section. The states are listed in order of progressingfunctionality. For example, the inoperative state is listed first,followed by a list of intermediate states before the final, fullyfunctional state is achieved. The specification makes use of thisordering by sometimes making references such as "those interfaces instate greater than X".Figure 11 shows the graph of interface state changes. The arcs of thegraph are labelled with the event causing the state change. Theseevents are documented in Section 9.2. The interface state machine isdescribed in more detail in Section 9.3.Down This is the initial interface state. In this state, the lower-level protocols have indicated that the interface is unusable. No protocol traffic at all will be sent or received on such a interface. In this state, interface parameters should be set to their initial values. All interface timers should be disabled, and there should be no adjacencies associated with the interface.Loopback In this state, the router's interface to the network is looped back. The interface may be looped back in hardware or software. The interface will be unavailable for regular data traffic. However, it may still be desirable to gain information on the quality of this interface, either through sending ICMP pings to the interface or through something like a bit error test. For this reason, IP[Moy] [Page 45] RFC 1247 OSPF Version 2 July 1991 packets may still be addressed to an interface in Loopback state. To facilitate this, such interfaces are advertised in router links advertisements as single host routes, whose destination is the IP interface address.[4]Waiting In this state, the router is trying to determine the identity of the Backup Designated Router for the network. To do this, the router monitors the Hellos it receives. The router is not allowed to elect a Backup Designated Router nor Designated Router until it transitions out of Waiting state. This prevents unnecessary changes of (Backup) Designated Router.Point-to-point In this state, the interface is operational, and connects either to a physical point-to-point network or to a virtual link. Upon entering this state, the router attempts to form an adjacency with the neighboring router. Hellos are sent to the neighbor every HelloInterval seconds.DR Other The interface is to a multi-access network on which another router has been selected to be the Designated Router. In this state, the router itself has not been selected Backup Designated Router either. The router forms adjacencies to both the Designated Router and the Backup Designated Router (if they exist).Backup In this state, the router itself is the Backup Designated Router on the attached network. It will be promoted to Designated Router when the present Designated Router fails. The router establishes adjacencies to all other routers attached to the network. The Backup Designated Router performs slightly different functions during the Flooding Procedure, as compared to the Designated Router (see Section 13.3). See Section 7.4 for more details on the functions performed by the Backup Designated Router.DR In this state, this router itself is the Designated Router on the attached network. Adjacencies are established to all other routers attached to the network. The router must also originate a network links advertisement for the network node. The advertisement will contain links to all routers (including the Designated Router itself) attached to the network. See Section 7.3 for more details on the functions performed by the Designated Router.[Moy] [Page 46] RFC 1247 OSPF Version 2 July 19919.2 Events causing interface state changesState changes can be effected by a number of events. These events arepictured as the labelled arcs in Figure 11. The label definitions arelisted below. For a detailed explanation of the effect of these eventson OSPF protocol operation, consult Section 9.3.Interface Up Lower-level protocols have indicated that the network interface is operational. This enables the interface to transition out of Down state. On virtual links, the interface operational indication is actually a result of the shortest path calculation (see Section 16.7).Wait Timer The Wait timer has fired, indicating the end of the waiting period that is required before electing a (Backup) Designated Router.Backup seen The router has detected the existence or non-existence of a Backup Designated Router for the network. This is done in one of two ways. First, a Hello Packet may be received from a neighbor claiming to be itself the Backup Designated Router. Alternatively, a Hello Packet may be received from a neighbor claiming to be itself the Designated Router, and indicating that there is no Backup. In either case there must be bidirectional communication with the neighbor, i.e., the router must also appear in the neighbor's Hello Packet. This event signals an end to the Waiting state.Neighbor Change There has been a change in the set of bidirectional neighbors associated with the interface. The (Backup) Designated Router needs to be recalculated. The following neighbor changes lead to the Neighbor Change event. For an explanation of neighbor states, see Section 10.1. o Bidirectional communication has been established to a neighbor. In other words, the state of the neighbor has transitioned to 2-Way or higher. o There is no longer bidirectional communication with a neighbor. In other words, the state of the neighbor has transitioned to Init or lower. o One of the bidirectional neighbors is newly declaring itself as either Designated Router or Backup Designated Router. This is detected through examination of that neighbor's Hello Packets.[Moy] [Page 47] RFC 1247 OSPF Version 2 July 1991 o One of the bidirectional neighbors is no longer declaring itself as Designated Router, or is no longer declaring itself as Backup Designated Router. This is again detected through examination of that neighbor's Hello Packets. o The advertised Router Priority for a bidirectional neighbor has changed. This is again detected through examination of that neighbor's Hello Packets.Loop Ind An indication has been received that the interface is now looped back to itself. This indication can be received either from network management or from the lower level protocols.Unloop Ind An indication has been received that the interface is no longer looped back. As with the Loop Ind event, this indication can be received either from network management or from the lower level protocols.Interface Down Lower-level protocols indicate that this interface is no longer functional. No matter what the current interface state is, the new interface state will be Down.9.3 The Interface state machineA detailed description of the interface state changes follows. Eachstate change is invoked by an event (Section 9.2). This event mayproduce different effects, depending on the current state of theinterface. For this reason, the state machine below is organized bycurrent interface state and received event. Each entry in the statemachine describes the resulting new interface state and the required setof additional actions.When an interface's state changes, it may be necessary to originate anew router links advertisement. See Section 12.4 for more details.Some of the required actions below involve generating events for theneighbor state machine. For example, when an interface becomesinoperative, all neighbor connections associated with the interface mustbe destroyed. For more information on the neighbor state machine, seeSection 10.3. State(s): Down[Moy] [Page 48] RFC 1247 OSPF Version 2 July 1991 Event: Interface UpNew state: Depends on action routine Action: Start the interval Hello Timer, enabling the periodic sending of Hello packets out the interface. If the attached network is a physical point-to-point network or virtual link, the interface state transitions to Point-to-Point. Else, if the router is not eligible to become Designated Router the interface state transitions to DR other. Otherwise, the attached network is multi-access and the router is eligible to become Designated Router. In this case, in an attempt to discover the attached network's Designated Router the interface state is set to Waiting and the single shot Wait Timer is started. If in addition the attached network is non-broadcast, examine the configured list of neighbors for this interface and generate the neighbor event Start for each neighbor that is also eligible to become Designated Router. State(s): Waiting Event: Backup SeenNew state: Depends upon action routine. Action: Calculate the attached network's Backup Designated Router and Designated Router, as shown in Section 9.4. As a result of this calculation, the new state of the interface will be either DR other, Backup or DR. State(s): Waiting Event: Wait TimerNew state: Depends upon action routine. Action: Calculate the attached network's Backup Designated Router and Designated Router, as shown in Section 9.4. As a result of this calculation, the new state of the interface will be either DR other, Backup or DR. State(s): DR Other, Backup or DR[Moy] [Page 49] RFC 1247 OSPF Version 2 July 1991 Event: Neighbor ChangeNew state: Depends upon action routine. Action: Recalculate the attached network's Backup Designated Router and Designated Router, as shown in Section 9.4. As a result of this calculation, the new state of the interface will be either DR other, Backup or DR. State(s): Any State Event: Interface DownNew state: Down Action: All interface variables are reset, and interface timers disabled. Also, all neighbor connections associated with the interface are destroyed. This is done by generating the event KillNbr on all associated neighbors (see Section 10.2). State(s): Any State Event: Loop IndNew state: Loopback Action: Since this interface is no longer connected to the attached network the actions associated with the above Interface Down event are executed. State(s): Loopback Event: Unloop IndNew state: Down Action: No actions are necessary. For example, the interface variables have already been reset upon entering the Loopback state. Note that reception of an Interface Up event is necessary before the interface again becomes fully functional.[Moy] [Page 50] RFC 1247 OSPF Version 2 July 19919.4 Electing the Designated RouterThis section describes the algorithm used for calculating a network'sDesignated Router and Backup Designated Router. This algorithm isinvoked by the Interface state machine. The initial time a router runsthe election algorithm for a network, the network's Designated Routerand Backup Designated Router are initialized to 0.0.0.0. This indicatesthe lack of both a Designated Router and a Backup Designated Router.The Designated Router election algorithm proceeds as follows: Call therouter doing the calculation Router X. The list of neighbors attachedto the network and having established bidirectional communication withRouter X is examined. This list is precisely the collection of RouterX's neighbors (on this network) whose state is greater than or equal to2-Way (see Section 10.1). Router X itself is also considered to be onthe list. Discard all routers from the list that are ineligible tobecome Designated Router. (Routers having Router Priority of 0 areineligible to become Designated Router.) The following steps are thenexecuted, considering only those routers that remain on the list:(1) Note the current values for the network's Designated Router and Backup Designated Router. This is used later for comparison purposes.(2) Calculate the new Backup Designated Router for the network as follows. Only those routers on the list that have not declared themselves to be Designated Router are eligible to become Backup Designated Router. If one or more of these routers have declared themselves Backup Designated Router (i.e., they are currently listing themselves as Backup Designated Router, but not as Designated Router, in their Hello Packets) the one having highest Router Priority is declared to be Backup Desi | |
