Movatterモバイル変換

Network Working Group                                             J. MoyRequest for Comments: 1247                                 Proteon, Inc.Obsoletes: RFC1131                                            July 1991OSPF 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 inRFC 1131.  Thedifferences between the two versions are explained inAppendix 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.  Sections4-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 inAppendix B.  The configurable constants areexplained inAppendix 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 (seeSection 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(seeSection 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 (seeAppendix 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 inSection 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 (seeSection 15).Another way to think about area partitions is to look at the AutonomousSystem graph that was introduced inSection 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 (seeSection 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 inAppendix A.  The OSPF packet types are listed below inTable 8.  Their formats are also described inAppendix 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" (seeSection 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 Sections9.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,    seeSection 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 Sections4.5 and16.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 inAppendix 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, seeSection3.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.  SeeSection 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 consultSection 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 (seeSection 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 (seeSection12.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 inSection 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.  SeeSection 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(seeSection 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 inAppendix 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 (seeSection 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 descriptionSection 10.8         3      Link state requestSection 10.9         4      Link state updateSection 13.3         5      Link state ackSection 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 (seeSection9.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 (seeAppendix 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 (seeSection 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      HelloSection 10.5          2      Database descriptionSection 10.6          3      Link state requestSection 10.7          4      Link state updateSection 13          5      Link state ackSection 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 inSection 9.2.  The interface state machine isdescribed in more detail inSection 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    (seeSection 13.3).  SeeSection 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.  SeeSection 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, consultSection 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 (seeSection16.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, seeSection 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.  SeeSection 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 inSection 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 inSection 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 inSection 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 (seeSection10.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 (seeSection 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 Designated Router.  In case    of a tie, the one having the highest Router ID is chosen.  If no    routers have declared themselves Backup Designated Router, choose    the router having highest Router Priority, (again excluding those    routers who have declared themselves Designated Router), and again    use the Router ID to break ties.(3) Calculate the new Designated Router for the network as follows.  If    one or more of the routers have declared themselves Designated    Router (i.e., they are currently listing themselves as Designated    Router in their Hello Packets) the one having highest Router    Priority is declared to be Designated Router.  In case of a tie, the    one having the highest Router ID is chosen.  If no routers have    declared themselves Designated Router, promote the new Backup    Designated Router to Designated Router.[Moy]                                                          [Page 51]

RFC 1247                     OSPF Version 2                    July 1991(4) If Router X is now newly the Designated Router or newly the Backup    Designated Router, or is now no longer the Designated Router or no    longer the Backup Designated Router, repeat steps 2 and 3, and then    proceed to step 5.  For example, if Router X is now the Designated    Router, when step 2 is repeated X will no longer be eligible for    Backup Designated Router election.  Among other things, this will    ensure that no router will declare itself both Backup Designated    Router and Designated Router.[5](5) As a result of these calculations, the router itself may now be    Designated Router or Backup Designated Router.  See Sections7.3 and    7.4 for the additional duties this would entail.  The router's    interface state should be set accordingly.  If the router itself is    now Designated Router, the new interface state is DR.  If the router    itself is now Backup Designated Router, the new interface state is    Backup.  Otherwise, the new interface state is DR Other.(6) If the attached network is non-broadcast, and the router itself has    just become either Designated Router or Backup Designated Router, it    must start sending hellos to those neighbors that are not eligible    to become Designated Router (seeSection 9.5.1).  This is done by    invoking the neighbor event Start for each neighbor having a Router    Priority of 0.(7) If the above calculations have caused the identity of either the    Designated Router or Backup Designated Router to change, the set of    adjacencies associated with this interface will need to be modified.    Some adjacencies may need to be formed, and others may need to be    broken.  To accomplish this, invoke the event AdjOK?  on all    neighbors whose state is at least 2-Way.  This will cause their    eligibility for adjacency to be reexamined (see Sections10.3 and    10.4).The reason behind the election algorithm's complexity is the desire foran orderly transition from Backup Designated Router to DesignatedRouter, when the current Designated Router fails.  This orderlytransition is ensured through the introduction of hysteresis: no newBackup router can be chosen until the old Backup accepts its newDesignated Router responsibilities.If Router X is not itself eligible to become Designated Router, it ispossible that neither a Backup Designated Router nor a Designated Routerwill be selected in the above procedure.  Note also that if Router X isthe only attached router that is eligible to become Designated Router,it will select itself as Designated Router and there will be no BackupDesignated Router for the network.[Moy]                                                          [Page 52]

RFC 1247                     OSPF Version 2                    July 19919.5 Sending Hello packetsHello packets are sent out each functioning router interface.  They areused to discover and maintain neighbor relationships.[6] On multi-accessnetworks, hellos are also used to elect the Designated Router and BackupDesignated Router, and in that way determine what adjacencies should beformed.The format of a Hello packet is detailed in Section A.3.2.  The HelloPacket contains the router's Router Priority (used in choosing theDesignated Router), and the interval between Hello broadcasts(HelloInterval).  The Hello Packet also indicates how often a neighbormust be heard from to remain active (RouterDeadInterval).  BothHelloInterval and RouterDeadInterval must be the same for all routersattached to a common network.  The Hello packet also contains the IPaddress mask of the attached network (Network Mask).  On unnumberedpoint-to-point networks and on virtual links this field should be set to0.The Hello packet's Options field describes the router's optional OSPFcapabilities.  There are currently two optional capabilities defined(see Sections4.5 and A.2).  The T-bit of the Options field should beset if the router is capable of calculating separate routes for each IPTOS.  The E-bit should be set if and only if the attached area iscapable of processing AS external advertisements (i.e., it is not a stubarea).  If the E-bit is set incorrectly the neighboring routers willrefuse to accept the Hello Packet (seeSection 10.5).  The rest of theHello Packet's Options field should be set to zero.In order to ensure two-way communication between adjacent routers, theHello packet contains the list of all routers from which hellos havebeen seen recently.  The Hello packet also contains the router's currentchoice for Designated Router and Backup Designated Router.  A value of 0in these fields means that one has not yet been selected.On broadcast networks and physical point-to-point networks, Hellopackets are sent every HelloInterval seconds to the IP multicast addressAllSPFRouters.  On virtual links, Hello packets are sent as unicasts(addressed directly to the other end of the virtual link) everyHelloInterval seconds.  On non-broadcast networks, the sending of Hellopackets is more complicated.  This will be covered in the next section.9.5.1 Sending Hello packets on non-broadcast networksStatic configuration information is necessary in order for the HelloProtocol to function on non-broadcast networks (see Section C.5).  Everyattached router which is eligible to become Designated Router has a[Moy]                                                          [Page 53]

RFC 1247                     OSPF Version 2                    July 1991configured list of all of its neighbors on the network.  Each listedneighbor is labelled with its Designated Router eligibility.The interface state must be at least Waiting for any hellos to be sent.Hellos are then sent directly (as unicasts) to some subset of a router'sneighbors.  Sometimes an hello is sent periodically on a timer; at othertimes it is sent as a response to a received hello.  A router's hello-sending behavior varies depending on whether the router itself iseligible to become Designated Router.If the router is eligible to become Designated Router, it mustperiodically send hellos to all neighbors that are also eligible.  Inaddition, if the router is itself the Designated Router or BackupDesignated Router, it must also send periodic hellos to all otherneighbors.  This means that any two eligible routers are alwaysexchanging hellos, which is necessary for the correct operation of theDesignated Router election algorithm.  To minimize the number of hellossent, the number of eligible routers on a non-broadcast network shouldbe kept small.If the router is not eligible to become Designated Router, it mustperiodically send hellos to both the Designated Router and the BackupDesignated Router (if they exist).  It must also send an hello in replyto an hello received from any eligible neighbor (other than the currentDesignated Router and Backup Designated Router).  This is needed toestablish an initial bidirectional relationship with any potentialDesignated Router.When sending Hello packets periodically to any neighbor, the intervalbetween hellos is determined by the neighbor's state.  If the neighboris in state Down, hellos are sent every PollInterval seconds.Otherwise, hellos are sent every HelloInterval seconds.10. The Neighbor Data StructureAn OSPF router converses with its neighboring routers.  Each separateconversation is described by a "neighbor data structure".  Eachconversation is bound to a particular OSPF router interface, and isidentified either by the neighboring router's OSPF router ID or by itsNeighbor IP address (see below).  Thus if the OSPF router and anotherrouter have multiple attached networks in common, multiple conversationsensue, each described by a unique neighbor data structure.  Eachseparate conversation is loosely referred to in the text as being aseparate "neighbor".The neighbor data structure contains all information pertinent to theforming or formed adjacency between the two neighbors.  (However,[Moy]                                                          [Page 54]

RFC 1247                     OSPF Version 2                    July 1991remember that not all neighbors become adjacent.)  An adjacency can beviewed as a highly developed conversation between two routers.State    The functional level of the neighbor conversation.  This is    described in more detail inSection 10.1.Inactivity Timer    A single shot timer whose firing indicates that no Hello Packet has    been seen from this neighbor recently.  The length of the timer is    RouterDeadInterval seconds.Master/Slave    When the two neighbors are exchanging databases, they form a Master    Slave relationship.  The Master sends the first Database Description    Packet, and is the only part that is allowed to retransmit.  The    slave can only respond to the master's Database Description Packets.    The master/slave relationship is negotiated in state ExStart.Sequence Number    A 32-bit number identifying individual Database Description packets.    When the neighbor state ExStart is entered, the sequence number    should be set to a value not previously seen by the neighboring    router.  One possible scheme is to use the machine's time of day    counter.  The sequence number is then incremented by the master with    each new Database Description packet sent.  The slave's sequence    number indicates the last packet received from the master.  Only one    packet is allowed outstanding at a time.Neighbor ID    The OSPF Router ID of the neighboring router.  The neighbor ID is    learned when Hello packets are received from the neighbor, or is    configured if this is a virtual adjacency (see Section C.4).Neighbor priority    The Router Priority of the neighboring router.  Contained in the    neighbor's Hello packets, this item is used when selecting the    Designated Router for the attached network.Neighbor IP address    The IP address of the neighboring router's interface to the attached    network.  Used as the Destination IP address when protocol packets    are sent as unicasts along this adjacency.  Also used in router    links advertisements as the Link ID for the attached network if the    neighboring router is selected to be Designated Router (seeSection12.4.1).  The neighbor IP address is learned when Hello packets are    received from the neighbor.  For virtual links, the neighbor IP[Moy]                                                          [Page 55]

RFC 1247                     OSPF Version 2                    July 1991    address is learned during the routing table build process (seeSection 15).Neighbor Options    The optional OSPF capabilities supported by the neighbor.  Learned    during the Database Exchange process (seeSection 10.6).  The    neighbor's optional OSPF capabilities are also listed in its Hello    packets.  This enables received Hellos to be rejected (i.e.,    neighbor relationships will not even start to form) if there is a    mismatch in certain crucial OSPF capabilities (seeSection 10.5).    The optional OSPF capabilities are documented inSection 4.5.Neighbor's Designated Router    The neighbor's idea of the Designated Router.  If this is the    neighbor itself, this is important in the local calculation of the    Designated Router.  Defined only on multi-access networks.Neighbor's Backup Designated Router    The neighbor's idea of the Backup Designated Router.  If this is the    neighbor itself, this is important in the local calculation of the    Backup Designated Router.  Defined only on multi-access networks.The next set of variables are lists of link state advertisements.  Theselists describe subsets of the area topological database.  There can befive distinct types of link state advertisements in an area topologicaldatabase: router links, network links, and type 3 and 4 summary links(all stored in the area data structure), and AS external links (storedin the global data structure).Link state retransmission list    The list of link state advertisements that have been flooded but not    acknowledged on this adjacency.  These will be retransmitted at    intervals until they are acknowledged, or until the adjacency is    destroyed.Database summary list    The complete list of link state advertisements that make up the area    topological database, at the moment the neighbor goes into Database    Exchange state.  This list is sent to the neighbor in Database    Description packets.Link state request list    The list of link state advertisements that need to be received from    this neighbor in order to synchronize the two neighbors' topological    databases.  This list is created as Database Description packets are    received, and is then sent to the neighbor in Link State Request[Moy]                                                          [Page 56]

RFC 1247                     OSPF Version 2                    July 1991    packets.  The list is depleted as appropriate Link State Update    packets are received.10.1 Neighbor statesThe state of a neighbor (really, the state of a conversation being heldwith a neighboring router) is documented in the following sections.  Thestates are listed in order of progressing functionality.  For example,the inoperative state is listed first, followed by a list ofintermediate states before the final, fully functional state isachieved.  The specification makes use of this ordering by sometimesmaking references such as "those neighbors/adjacencies in state greaterthan X".  Figures 12 and 13 show the graph of neighbor state changes.The arcs of the graphs are labelled with the event causing the statechange.  The neighbor events are documented inSection 10.2.The graph in Figure 12 show the state changes effected by the HelloProtocol.  The Hello Protocol is responsible for neighbor acquisitionand maintenance, and for ensuring two way communication betweenneighbors.The graph in Figure 13 shows the forming of an adjacency.  Not every twoneighboring routers become adjacent (seeSection 10.4).  The adjacencystarts to form when the neighbor is in state ExStart.  After the tworouters discover their master/slave status, the state transitions toExchange.  At this point the neighbor starts to be used in the floodingprocedure, and the two neighboring routers begin synchronizing theirdatabases.  When this synchronization is finished, the neighbor is instate Full and we say that the two routers are fully adjacent.  At thispoint the adjacency is listed in link state advertisements.For a more detailed description of neighbor state changes, together withthe additional actions involved in each change, seeSection 10.3.         _____________________________________________________                (Figures not included in text version.)          Figure 12: Neighbor state changes (Hello Protocol)         Figure 13: Neighbor state changes (Database Exchange)         _____________________________________________________[Moy]                                                          [Page 57]

RFC 1247                     OSPF Version 2                    July 1991Down    This is the initial state of a neighbor conversation.  It indicates    that there has been no recent information received from the    neighbor.  On non-broadcast networks, Hello packets may still be    sent to "Down" neighbors, although at a reduced frequency (seeSection 9.5.1).Attempt    This state is only valid for neighbors attached to non-broadcast    networks.  It indicates that no recent information has been received    from the neighbor, but that a more concerted effort should be made    to contact the neighbor.  This is done by sending the neighbor Hello    packets at intervals of HelloInterval (seeSection 9.5.1).Init    In this state, an Hello packet has recently been seen from the    neighbor.  However, bidirectional communication has not yet been    established with the neighbor (i.e., the router itself did not    appear in the neighbor's Hello packet).  All neighbors in this state    (or higher) are listed in the Hello packets sent from the associated    interface.2-Way    In this state, communication between the two routers is    bidirectional.  This has been assured by the operation of the Hello    Protocol.  This is the most advanced state short of beginning    adjacency establishment.  The (Backup) Designated Router is selected    from the set of neighbors in state 2-Way or greater.ExStart    This is the first step in creating an adjacency between the two    neighboring routers.  The goal of this step is to decide which    router is the master, and to decide upon the initial sequence    number.  Neighbor conversations in this state or greater are called    adjacencies.Exchange    In this state the router is describing its entire link state    database by sending Database Description packets to the neighbor.    Each Database Description Packet has a sequence number, and is    explicitly acknowledged.  Only one Database Description Packet is    allowed outstanding at any one time.  In this state, Link State    Request Packets may also be sent asking for the neighbor's more    recent advertisements.  All adjacencies in Exchange state or greater    are used by the flooding procedure.  In fact, these adjacencies are    fully capable of transmitting and receiving all types of OSPF    routing protocol packets.[Moy]                                                          [Page 58]

RFC 1247                     OSPF Version 2                    July 1991Loading    In this state, Link State Request packets are sent to the neighbor    asking for the more recent advertisements that have been discovered    (but not yet received) in the Exchange state.Full    In this state, the neighboring routers are fully adjacent.  These    adjacencies will now appear in router links and network links    advertisements.10.2 Events causing neighbor state changesState changes can be effected by a number of events.  These events areshown in the labels of the arcs in Figures 12 and 13.  The labeldefinitions are as follows:Hello Received    A Hello packet has been received from a neighbor.Start    This is an indication that Hello Packets should now be sent to the    neighbor at intervals of HelloInterval seconds.  This event is    generated only for neighbors associated with non-broadcast networks.2-Way Received    Bidirectional communication has been realized between the two    neighboring routers.  This is indicated by this router seeing itself    in the other's Hello packet.NegotiationDone    The Master/Slave relationship has been negotiated, and sequence    numbers have been exchanged.  This signals the start of the    sending/receiving of Database Description packets.  For more    information on the generation of this event, consultSection 10.8.Exchange Done    Both routers have successfully transmitted a full sequence of    Database Description packets.  Each router now knows what parts of    its link state database are out of date.  For more information on    the generation of this event, consultSection 10.8.BadLSReq    A Link State Request has been received for a link state    advertisement not contained in the database.  This indicates an    error in the synchronization process.[Moy]                                                          [Page 59]

RFC 1247                     OSPF Version 2                    July 1991Loading Done    Link State Updates have been received for all out-of-date portions    of the database.  This is indicated by the Link state request list    becoming empty after the Database Description Process has completed.AdjOK?    A decision must be made (again) as to whether an adjacency should be    established/maintained with the neighbor.  This event will start    some adjacencies forming, and destroy others.The following events cause well developed neighbors to revert to lesserstates.  Unlike the above events, these events may occur when theneighbor conversation is in any of a number of states.Seq Number Mismatch    A Database Description packet has been received that either a) has    an unexpected sequence number, b) unexpectedly has the Init bit set    or c) has an Options field differing from the last Options field    received in a Database Description packet.  Any of these conditions    indicate that some error has occurred during adjacency    establishment.1-Way    An Hello packet has been received from the neighbor, in which this    router is not mentioned.  This indicates that communication with the    neighbor is not bidirectional.KillNbr    This  is  an  indication that  all  communication  with  the    neighbor  is now  impossible,  forcing  the  neighbor  to  revert    to  Down  state.Inactivity Timer    The inactivity Timer has fired.  This means that no Hello packets    have been seen recently from the neighbor.  The neighbor reverts to    Down state.LLDown    This is an indication from the lower level protocols that the    neighbor is now unreachable.  For example, on an X.25 network this    could be indicated by an X.25 clear indication with appropriate    cause and diagnostic fields.  This event forces the neighbor into    Down state.[Moy]                                                          [Page 60]

RFC 1247                     OSPF Version 2                    July 199110.3 The Neighbor state machineA detailed description of the neighbor state changes follows.  Eachstate change is invoked by an event (Section 10.2).  This event mayproduce different effects, depending on the current state of theneighbor.  For this reason, the state machine below is organized bycurrent neighbor state and received event.  Each entry in the statemachine describes the resulting new neighbor state and the required setof additional actions.When an neighbor's state changes, it may be necessary to rerun theDesignated Router election algorithm.  This is determined by whether theinterface Neighbor Change event is generated (seeSection 9.2).  Also,if the Interface is in DR state (the router is itself DesignatedRouter), changes in neighbor state may cause a new network linksadvertisement to be originated (seeSection 12.4).When the neighbor state machine needs to invoke the interface statemachine, it should be done as a scheduled task (seeSection 4.4).  Thissimplifies things, by ensuring that neither state machine will beexecuted recursively. State(s):  Down    Event:  StartNew state:  Attempt   Action:  Send an hello to the neighbor (this neighbor is always            associated with a non-broadcast network) and start the            inactivity timer for the neighbor.  The timer's later firing            would indicate that communication with the neighbor was not            attained. State(s):  Attempt    Event:  Hello ReceivedNew state:  Init   Action:  Restart the inactivity timer for the neighbor, since the            neighbor has now been heard from. State(s):  Down[Moy]                                                          [Page 61]

RFC 1247                     OSPF Version 2                    July 1991    Event:  Hello ReceivedNew state:  Init   Action:  Start the inactivity timer for the neighbor.  The timer's            later firing would indicate that the neighbor is dead. State(s):  Init or greater    Event:  Hello ReceivedNew state:  No state change.   Action:  Restart the inactivity timer for the neighbor, since the            neighbor has again been heard from. State(s):  Init    Event:  2-Way ReceivedNew state:  Depends upon action routine.   Action:  Determine whether an adjacency should be established with            the neighbor (seeSection 10.4).  If not, the new neighbor            state is 2-Way.            Otherwise (an adjacency should be established) the neighbor            state transitions to ExStart.  Upon entering this state, the            router increments the sequence number for this neighbor.  If            this is the first time that an adjacency has been attempted,            the sequence number should be assigned some unique value            (like the time of day clock).  It then declares itself            master (sets the master/slave bit to master), and starts            sending Database Description Packets, with the initialize            (I), more (M) and master (MS) bits set.  This Database            Description Packet should be otherwise empty.  This Database            Description Packet should be retransmitted at intervals of            RxmtInterval until the next state is entered (seeSection10.8). State(s):  ExStart    Event:  NegDone[Moy]                                                          [Page 62]

RFC 1247                     OSPF Version 2                    July 1991New state:  Exchange   Action:  The router must list the contents of its entire area link            state database in the neighbor Database summary list.  The            area link state database consists of the router links,            network links and summary links contained in the area            structure, along with the AS external links contained in the            global structure.  AS external link advertisements are            omitted from a virtual neighbor's Database summary list.  AS            external advertisements are omitted from the Database            summary list if the area has been configured as a stub (seeSection 3.6).  Advertisements whose age is equal to MaxAge            are instead added to the neighbor's Link state            retransmission list.  A summary of the Database summary list            will be sent to the neighbor in Database Description            packets.  Each Database Description Packet has a sequence            number, and is explicitly acknowledged.  Only one Database            Description Packet is allowed outstanding at any one time.            For more detail on the sending and receiving of Database            Description packets, see Sections10.8 and10.6. State(s):  Exchange    Event:  Exchange DoneNew state:  Depends upon action routine.   Action:  If the neighbor Link state request list is empty, the new            neighbor state is Full.  No other action is required.  This            is an adjacency's final state.            Otherwise, the new neighbor state is Loading.  Start (or            continue) sending Link State Request packets to the neighbor            (seeSection 10.9).  These are requests for the neighbor's            more recent advertisements (which were discovered but not            yet received in the Exchange state).  These advertisements            are listed in the Link state request list associated with            the neighbor. State(s):  Loading    Event:  Loading DoneNew state:  Full[Moy]                                                          [Page 63]

RFC 1247                     OSPF Version 2                    July 1991   Action:  No action required.  This is an adjacency's final state. State(s):  2-Way    Event:  AdjOK?New state:  Depends upon action routine.   Action:  Determine whether an adjacency should be formed with the            neighboring router (seeSection 10.4).  If not, the neighbor            state remains at 2-Way.  Otherwise, transition the neighbor            state to ExStart and perform the actions associated with the            above state machine entry for state Init and event 2-Way            Received. State(s):  ExStart or greater    Event:  AdjOK?New state:  Depends upon action routine.   Action:  Determine whether the neighboring router should still be            adjacent.  If yes, there is no state change and no further            action is necessary.            Otherwise, the (possibly partially formed) adjacency must be            destroyed.  The neighbor state transitions to 2-Way.  The            Link state retransmission list, Database summary list and            Link state request list are cleared of link state            advertisements. State(s):  Exchange or greater    Event:  Seq Number MismatchNew state:  ExStart   Action:  The (possibly partially formed) adjacency is torn down, and            then an attempt is made at reestablishment.  The neighbor            state first transitions to ExStart.  The Link state            retransmission list, Database summary list and Link state            request list are cleared of link state advertisements.  Then            the router increments the sequence number for this neighbor,            declares itself master (sets the master/slave bit to            master), and starts sending Database Description Packets,[Moy]                                                          [Page 64]

RFC 1247                     OSPF Version 2                    July 1991            with the initialize (I), more (M) and master (MS) bits set.            This Database Description Packet should be otherwise empty            (seeSection 10.8). State(s):  Exchange or greater    Event:  BadLSReqNew state:  ExStart   Action:  The action for event BadLSReq is exactly the same as for the            neighbor event SeqNumberMismatch.  The (possibly partially            formed) adjacency is torn down, and then an attempt is made            at reestablishment.  For more information, see the neighbor            state machine entry that is invoked when event            SeqNumberMismatch is generated in state Exchange or greater. State(s):  Any state    Event:  KillNbrNew state:  Down   Action:  The Link state retransmission list, Database summary list            and Link state request list are cleared of link state            advertisements.  Also, the inactivity timer is disabled. State(s):  Any state    Event:  LLDownNew state:  Down   Action:  The Link state retransmission list, Database summary list            and Link state request list are cleared of link state            advertisements.  Also, the inactivity timer is disabled. State(s):  Any state    Event:  Inactivity TimerNew state:  Down[Moy]                                                          [Page 65]

RFC 1247                     OSPF Version 2                    July 1991   Action:  The Link state retransmission list, Database summary list            and Link state request list are cleared of link state            advertisements. State(s):  2-Way or greater    Event:  1-Way ReceivedNew state:  Init   Action:  The Link state retransmission list, Database summary list            and Link state request list are cleared of link state            advertisements. State(s):  2-Way or greater    Event:  2-Way receivedNew state:  No state change.   Action:  No action required. State(s):  Init    Event:  1-Way receivedNew state:  No state change.   Action:  No action required.10.4 Whether to become adjacentAdjacencies are established with some subset of the router's neighbors.Routers connected by point-to-point networks and virtual links alwaysbecome adjacent.  On multi-access networks, all routers become adjacentto both the Designated Router and the Backup Designated Router.The adjacency-forming decision occurs in two places in the neighborstate machine.  First, when bidirectional communication is initiallyestablished with the neighbor, and secondly, when the identity of theattached network's (Backup) Designated Router changes.  If the decisionis made to not attempt an adjacency, the state of the neighborcommunication stops at 2-Way.[Moy]                                                          [Page 66]

RFC 1247                     OSPF Version 2                    July 1991An adjacency should be established with a (bidirectional) neighbor whenat least one of the following conditions holds:o   The underlying network type is point-to-pointo   The underlying network type is virtual linko   The router itself is the Designated Routero   The router itself is the Backup Designated Routero   The neighboring router is the Designated Routero   The neighboring router is the Backup Designated Router10.5 Receiving Hello packetsThis section explains the detailed processing of a received Hellopacket.  (See Section A.3.2 for the format of Hello packets.)  Thegeneric input processing of OSPF packets will have checked the validityof the IP header and the OSPF packet header.  Next, the values of theNetwork Mask, HelloInt, and DeadInt fields in the received Hello packetmust be checked against the values configured for the receivinginterface.  Any mismatch causes processing to stop and the packet to bedropped.  In other words, the above fields are really describing theattached network's configuration.  Note that the value of the NetworkMask field should not be checked in Hellos received on unnumbered seriallines or on virtual links.The receiving interface attaches to a single OSPF area (this could bethe backbone).  The setting of the E-bit found in the Hello Packet'soption field must match this area's external routing capability.  If ASexternal advertisements are not flooded into/throughout the area (i.e,the area is a "stub") the E-bit must be clear in received hellos,otherwise the E-bit must be set.  A mismatch causes processing to stopand the packet to be dropped.  The setting of the rest of the bits inthe Hello Packet's option field should be ignored.At this point, an attempt is made to match the source of the HelloPacket to one of the receiving interface's neighbors.  If the receivinginterface is a multi-access network (either broadcast or non-broadcast)the source is identified by the IP source address found in the Hello'sIP header.  If the receiving interface is a point-to-point link or avirtual link, the source is identified by the Router ID found in theHello's OSPF packet header.  The interface's current list of neighborsis contained in the interface's data structure.  If a matching neighbor[Moy]                                                          [Page 67]

RFC 1247                     OSPF Version 2                    July 1991structure cannot be found, (i.e., this is the first time the neighborhas been detected), one is created.  The initial state of a newlycreated neighbor is set to Down.When receiving an Hello Packet from a neighbor on a multi-access network(broadcast or non-broadcast), set the neighbor structure's Neighbor IDequal to the Router ID found in the packet's OSPF header.  Whenreceiving an Hello on a point-to-point network (but not on a virtuallink) set the neighbor structure's Neighbor IP address to the packet'sIP source address.Now the rest of the Hello Packet is examined, generating events to begiven to the neighbor and interface state machines.  These statemachines are specified either to be executed or scheduled (seeSection4.4).  For example, by specifying below that the neighbor state machinebe executed in line, several neighbor state transitions may be effectedby a single received Hello:o   Each Hello Packet causes the neighbor state machine to be executed    with the event Hello Received.o   Then the list of neighbors contained in the Hello Packet is    examined.  If the router itself appears in this list, the neighbor    state machine should be executed with the event 2-Way Received.    Otherwise, the neighbor state machine should be executed with the    event 1-Way Received, and the processing of the packet stops.o   Next, the Hello packet's Router Priority field is examined.  If this    field is different than the one previously received from the    neighbor, the receiving interface's state machine is scheduled with    the event NeighborChange.  In any case, the Router Priority field in    the neighbor data structure should be set accordingly.o   Next the Designated Router field in the Hello Packet is examined.    If the neighbor is both declaring itself to be Designated Router    (Designated Router field = neighbor IP address) and the Backup    Designated Router field in the packet is equal to 0.0.0.0 and the    receiving interface is in state Waiting, the receiving interface's    state machine is scheduled with the event BackupSeen.  Otherwise, if    the neighbor is declaring itself to be Designated Router and it had    not previously, or the neighbor is not declaring itself Designated    Router where it had previously, the receiving interface's state    machine is scheduled with the event NeighborChange.  In any case,    the Designated Router item in the neighbor structure is set    accordingly.[Moy]                                                          [Page 68]

RFC 1247                     OSPF Version 2                    July 1991o   Finally, the Backup Designated Router field in the Hello Packet is    examined.  If the neighbor is declaring itself to be Backup    Designated Router (Backup Designated Router field = neighbor IP    address) and the receiving interface is in state Waiting, the    receiving interface's state machine is scheduled with the event    BackupSeen.  Otherwise, if the neighbor is declaring itself to be    Backup Designated Router and it had not previously, or the neighbor    is not declaring itself Backup Designated Router where it had    previously, the receiving interface's state machine is scheduled    with the event NeighborChange.  In any case, the Backup Designated    Router item in the neighbor structure is set accordingly.10.6 Receiving Database Description PacketsThis section explains the detailed processing of a received DatabaseDescription packet.  The incoming Database Description Packet hasalready been associated with a neighbor and receiving interface by thegeneric input packet processing (Section 8.2).  The further processingof the Database Description Packet depends on the neighbor state.  Ifthe neighbor's state is Down or Attempt the packet should be ignored.Otherwise, if the state is:Init    The neighbor state machine should be executed with the event 2-Way    Received.  This causes an immediate state change to either state 2-    Way or state Exstart.  The processing of the current packet should    then continue in this new state.2-Way    The packet should be ignored.  Database description packets are used    only for the purpose of bringing up adjacencies.[7]ExStart    If the received packet matches one of the following cases, then the    neighbor state machine should be executed with the event    NegotiationDone (causing the state to transition to Exchange), the    packet's Options field should be recorded in the neighbor    structure's Neighbor Options field and the packet should be accepted    as next in sequence and processed further (see below).  Otherwise,    the packet should be ignored.    o   The initialize(I), more (M) and master(MS) bits are set, the        contents of the packet are empty, and the neighbor's Router ID        is larger than the router's own.  In this case the router is now        Slave.  Set the master/slave bit to slave, and set the sequence        number to that specified by the master.[Moy]                                                          [Page 69]

RFC 1247                     OSPF Version 2                    July 1991    o   The initialize(I) and master(MS) bits are off, the packet's        sequence number equals the router's own sequence number        (indicating acknowledgment) and the neighbor's Router ID is        smaller than the router's own.  In this case the router is        Master.Exchange    If the state of the MS-bit is inconsistent with the master/slave    state of the connection, generate the neighbor event Seq Number    Mismatch and stop processing the packet.  Otherwise:    o   If the initialize(I) bit is set, generate the neighbor event Seq        Number Mismatch and stop processing the packet.    o   If the packet's Options field indicates a different set of        optional OSPF capabilities than were previously received from        the neighbor (recorded in the Neighbor Options field of the        neighbor structure), generate the neighbor event Seq Number        Mismatch and stop processing the packet.    o   If the router is master, and the packet's sequence number equals        the router's own sequence number (this packet is the next in        sequence) the packet should be accepted and its contents        processed (below).    o   If the router is master, and the packet's sequence number is one        less than the router's sequence number, the packet is a        duplicate.  Duplicates should be discarded by the master.    o   If the router is slave, and the packet's sequence number is one        more than the router's own sequence number (this packet is the        next in sequence) the packet should be accepted and its contents        processed (below).    o   If the router is slave, and the packet's sequence number is        equal to the router's sequence number, the packet is a        duplicate.  The slave must respond to duplicates by repeating        the last Database Description packet that it sent.    o   Else, generate the neighbor event Seq Number Mismatch and stop        processing the packet.Loading or Full    In this state, the router has sent and received an entire sequence    of Database Descriptions.  The only packets received should be    duplicates (see above).  In particular, the packet's Options field    should match the set of optional OSPF capabilities previously    indicated by the neighbor (stored in the neighbor structure's[Moy]                                                          [Page 70]

RFC 1247                     OSPF Version 2                    July 1991    neighbor Options field).  Any other packets received, including the    reception of a packet with the Initialize(I) bit set, should    generate the neighbor event Seq Number Mismatch.[8] Duplicates    should be discarded by the master.  The slave must respond to    duplicates by repeating the last Database Description packet that it    sent.When the router accepts a received Database Description Packet as thenext in sequence the packet contents are processed as follows.  For eachlink state advertisement listed, the advertisement's LS type is checkedfor validity.  If the LS type is unknown (e.g., not one of the LS types1-5 defined by this specification), or if this is a AS externaladvertisement (LS type = 5) and the neighbor is associated with a stubarea, generate the neighbor event Seq Number Mismatch and stopprocessing the packet.  Otherwise, the router looks up the advertisementin its database to see whether it also has an instance of the link stateadvertisement.  If it does not, or if the database copy is less recent(seeSection 13.1), the link state advertisement is put on the Linkstate request list so that it can be requested (immediately or at somelater time) in Link State Request Packets.When the router accepts a received Database Description Packet as thenext in sequence, it also performs the following actions, depending onwhether it is master or slave:Master    Increments the sequence number.  If the router has already sent its    entire sequence of Database Descriptions, and the just accepted    packet has the more bit (M) set to 0, the neighbor event Exchange    Done is generated.  Otherwise, it should send a new Database    Description to the slave.Slave    Sets the sequence number to the sequence number appearing in the    received packet.  The slave must send a Database Description in    reply.  If the received packet has the more bit (M) set to 0, and    the packet to be sent by the slave will have the M-bit set to 0    also, the neighbor event Exchange Done is generated.  Note that the    slave always generates this event before the master.10.7 Receiving Link State Request PacketsThis section explains the detailed processing of received Link StateRequest packets.  Received Link State Request Packets specify a list oflink state advertisements that the neighbor wishes to receive.  Link[Moy]                                                          [Page 71]

RFC 1247                     OSPF Version 2                    July 1991state Request Packets should be accepted when the neighbor is in statesExchange, Loading, or Full.  In all other states Link State RequestPackets should be ignored.Each link state advertisement specified in the Link State Request packetshould be located in the router's database, and copied into Link StateUpdate packets for transmission to the neighbor.  These link stateadvertisements should NOT be placed on the Link state retransmissionlist for the neighbor.  If a link state advertisement cannot be found inthe database, something has gone wrong with the synchronizationprocedure, and neighbor event BadLSReq should be generated.10.8 Sending Database Description PacketsThis section describes how Database Description Packets are sent to aneighbor.  The router's optional OSPF capabilities (seeSection 4.5) aretransmitted to the neighbor in the Options field of the DatabaseDescription packet.  The router should maintain the same set of optionalcapabilities throughout the Database Exchange and flooding procedures.If for some reason the router's optional capabilities change, theDatabase Exchange procedure should be restarted by reverting to neighborstate ExStart.  There are currently two optional capabilities defined.The T-bit should be set if and only if the router is capable ofcalculating separate routes for each IP TOS.  The E-bit should be set ifand only if the attached network belongs to a non-stub area.  The restof the Options field should be set to zero.The sending of Database Description packets depends on the neighbor'sstate.  In state ExStart the router sends empty Database Descriptionpackets, with the initialize (I), more (M) and master (MS) bits set.These packets are retransmitted every RxmtInterval seconds.In state Exchange the Database Description Packets actually containsummaries of the link state information contained in the router'sdatabase.  Each link state advertisement in the area's topologicaldatabase (at the time the neighbor transitions into Exchange state) islisted in the neighbor Database summary list.  When a new DatabaseDescription Packet is to be sent, the packet's sequence number isincremented, and the (new) top of the Database summary list is describedby the packet.  Items are removed from the Database summary list whenthe previous packet is acknowledged.In state Exchange, the determination of when to send a packet depends onwhether the router is master or slave:[Moy]                                                          [Page 72]

RFC 1247                     OSPF Version 2                    July 1991Master    Packets are sent when either a) the slave acknowledges the previous    packet by echoing the sequence number or b) RxmtInterval seconds    elapse without an acknowledgment, in which case the previous packet    is retransmitted.Slave    Packets are sent only in response to packets received from the    master.  If the packet received from the master is new, a new packet    is sent, otherwise the previous packet is resent.In states Loading and Full the slave must resend its last packet inresponse to duplicate packets received from the master.  For this reasonthe slave must wait RouterDeadInterval seconds before freeing the lastpacket.  Reception of a packet from the master after this interval willgenerate a Seq Number Mismatch neighbor event.10.9 Sending Link State Request PacketsIn neighbor states Exchange or Loading, the Link state request listcontains a list of those link state advertisements that need to beobtained from the neighbor.  To request these advertisements, a routersends the neighbor the beginning of the Link state request list,packaged in a Link State Request packet.When the neighbor responds to these requests with the proper Link StateUpdate packet(s), the Link state request list is truncated and a newLink State Request packet is sent.  This process continues until thelink state request list becomes empty.  Unsatisfied Link State Requestsare retransmitted at intervals of RxmtInterval.  There should be at mostone Link State Request packet outstanding at any one time.When the Link state request list becomes empty, and the neighbor stateis Loading (i.e., a complete sequence of Database Description packetshas been received from the neighbor), the Loading Done neighbor event isgenerated.10.10 An ExampleFigure 14 shows an example of an adjacency forming.  Routers RT1 and RT2are both connected to a broadcast network.  It is assumed that RT2 isthe Designated Router for the network, and that RT2 has a higher RouterID that router RT1.The neighbor state changes realized by each router are listed on the[Moy]                                                          [Page 73]

RFC 1247                     OSPF Version 2                    July 1991sides of the figure.At the beginning of Figure 14, router RT1's interface to the networkbecomes operational.  It begins sending hellos, although it doesn't knowthe identity of the Designated Router or of any other neighboringrouters.  Router RT2 hears this hello (moving the neighbor to Initstate), and in its next hello indicates that it is itself the DesignatedRouter and that it has heard hellos from RT1.  This in turn causes RT1to go to state ExStart, as it starts to bring up the adjacency.RT1 begins by asserting itself as the master.  When it sees that RT2 isindeed the master (because of RT2's higher Router ID), RT1 transitionsto slave state and adopts its neighbor's sequence number.  DatabaseDescription packets are then exchanged, with polls coming from themaster (RT2) and responses from the slave (RT1).  This sequence ofDatabase Description Packets ends when both the poll and associatedresponse has the M-bit off.In this example, it is assumed that RT2 has a completely up to datedatabase.  In that case, RT2 goes immediately into Full state.  RT1 willgo into Full state after updating the necessary parts of its database.This is done by sending Link State Request Packets, and receiving LinkState Update Packets in response.  Note that, while RT1 has waited untila complete set of Database Description Packets has been received (fromRT2) before sending any Link State Request Packets, this need not be thecase.  RT1 could have interleaved the sending of Link State RequestPackets with the reception of Database Description Packets.11. The Routing Table StructureThe routing table data structure contains all the information necessaryto forward an IP data packet toward its destination.  Each routing tableentry describes the collection of best paths to a particulardestination.  When forwarding an IP data packet, the routing table entryproviding the best match for the packet's IP destination is located.                ________________________________________                 (Figure not included in text version.)                Figure 14: An adjacency bring-up example                ________________________________________[Moy]                                                          [Page 74]

RFC 1247                     OSPF Version 2                    July 1991The matching routing table entry then provides the next hop towards thepacket's destination.  OSPF also provides for the existence of a defaultroute (Destination ID = DefaultDestination).  When the default routeexists, it matches all IP destinations (although any other matchingentry is a better match).  Finding the routing table entry that bestmatches an IP destination is further described inSection 11.1.There is a single routing table in each router.  Two sample routingtables are described in Sections11.2 and11.3.  The building of therouting table is discussed inSection 16.The rest of this section defines the fields found in a routing tableentry.  The first set of fields describes the routing table entry'sdestination.Destination Type    The destination can be one of three types.  Only the first type,    Network, is actually used when forwarding IP data traffic.  The    other destinations are used solely as intermediate steps in the    routing table build process.    Network        A range of IP addresses, to which IP data traffic may be        forwarded.  This includes IP networks (class A, B, or C), IP        subnets, and single IP hosts.  The default route also falls in        this category.    Area border router        Routers that are connected to multiple OSPF areas.  Such routers        originate summary link advertisements.  These routing table        entries are used when calculating the inter-area routes (seeSection 16.2).  These routing table entries may also be        associated with configured virtual links.    AS boundary router        Routers that originate AS external link advertisements.  These        routing table entries are used when calculating the AS external        routes (seeSection 16.4).Destination ID    The destination's identifier or name.  This depends on the    destination's type.  For networks, the identifier is their    associated IP address.  For all other types, the identifier is the    OSPF Router ID.[9]Address Mask    Only defined for networks.  The network's IP address together with[Moy]                                                          [Page 75]

RFC 1247                     OSPF Version 2                    July 1991    its address mask defines a range of IP addresses.  For IP subnets,    the address mask is referred to as the subnet mask.  For host    routes, the mask is "all ones" (0xffffffff).Optional Capabilities    When the destination is a router (either an area border router or an    AS boundary router) this field indicates the optional OSPF    capabilities supported by the destination router.  The two optional    capabilities currently defined by this specification are the ability    to route based on IP TOS and the ability to process AS external    advertisements.  For a further discussion of OSPF's optional    capabilities, seeSection 4.5.The set of paths to use for a destination may vary based on IP Type ofService and the OSPF area to which the paths belong.  This means thatthere may be multiple routing table entries for the same destination,depending on the values of the next two fields.Type of Service    There can be a separate set of routes for each IP Type of Service.    The encoding of TOS in OSPF link state advertisements is described    inSection 12.3.Area    This field indicates the area whose link state information has led    to the routing table entry's collection of paths.  This is called    the entry's associated area.  For sets of AS external paths, this    field is not defined.  For destinations of type "area border    router", there may be separate sets of paths (and therefore separate    routing table entries) associated with each of several areas.  This    will happen when two area border routers share multiple areas in    common.  For all other destination types, only the set of paths    associated with the best area (the one providing the shortest route)    is kept.The rest of the routing table entry describes the set of paths to thedestination.  The following fields pertain to the set of paths as awhole.  In other words, each one of the paths contained in a routingtable entry is of the same path-type and cost (see below).Path-type    There are four possible types of paths used to route traffic to the    destination, listed here in order of preference: intra-area, inter-    area, type 1 external or type 2 external.  Intra-area paths indicate[Moy]                                                          [Page 76]

RFC 1247                     OSPF Version 2                    July 1991    destinations belonging to one of the router's attached areas.    Inter-area paths are paths to destinations in other OSPF areas.    These are discovered through the examination of received summary    link advertisements.  AS external paths are paths to destinations    external to the AS.  These are detected through the examination of    received AS external link advertisements.Cost    The link state cost of the path to the destination.  For all paths    except type 2 external paths this describes the entire path's cost.    For Type 2 external paths, this field describes the cost of the    portion of the path internal to the AS.  This cost is calculated as    the sum of the costs of the path's constituent links.Type 2 cost    Only valid for type 2 external paths.  For these paths, this field    indicates the cost of the path's external portion.  This cost has    been advertised by an AS boundary router, and is the most    significant part of the total path cost.  For example, an external    type 2 path with type 2 cost of 5 is always preferred over a path    with type 2 cost of 10, regardless of the cost of the two paths'    internal components.Link State Origin    Valid only for intra-area paths, this field indicates the link state    advertisement (router links or network links) that directly    references the destination.  For example, if the destination is a    transit network, this is the transit network's network links    advertisement.  If the destination is a stub network, this is the    router links advertisement for the attached router.  The    advertisement is discovered during the shortest-path tree    calculation (seeSection 16.1).  Multiple advertisements may    reference the destination, however a tie-breaking scheme always    reduces the choice to a single advertisement.    This field is for informational purposes only.  The advertisement    could be used as a root for an SPF calculation when building a    reverse path forwarding tree.  This is beyond the scope of this    specification.When multiple paths of equal path-type and cost exist to a destination(called elsewhere "equal-cost" paths), they are stored in a singlerouting table entry.  Each one of the "equal-cost" paths isdistinguished by the following fields:[Moy]                                                          [Page 77]

RFC 1247                     OSPF Version 2                    July 1991Next hop    The outgoing router interface to use when forwarding traffic to the    destination.  On multi-access networks, the next hop also includes    the IP address of the next router (if any) in the path towards the    destination.  This next router will always be one of the adjacent    neighbors.Advertising router    Valid only for inter-area and AS external paths.  This field    indicates the Router ID of the router advertising the summary link    or AS external link that led to this path.11.1 Routing table lookupWhen an IP data packet is received, an OSPF router finds the routingtable entry that best matches the packet's destination. This routingtable entry then provides the outgoing interface and next hop router touse in forwarding the packet. This section describes the process offinding the best matching routing table entry. The process consists of anumber of steps, wherein the collection of routing table entries isprogressively pruned. In the end, the single routing table entryremaining is the called best match.Note that the steps described below may fail to produce a best matchrouting table entry (i.e., all existing routing table entries are prunedfor some reason or another). In this case, the packet's IP destinationis considered unreachable. Instead of being forwarded, the packet shouldbe dropped and an ICMP destination unreachable message should bereturned to the packet's source.(1) Select the complete set of "matching" routing table entries from the    routing table.  Each routing table entry describes a (set of)    path(s) to a range of IP addresses. If the data packet's IP    destination falls into an entry's range of IP addresses, the routing    table entry is called a match. (It is quite likely that multiple    entries will match the data packet.  For example, a default route    will match all packets.)(2) Suppose that the packet's IP destination falls into one of the    router's configured area address ranges (seeSection 3.5), and that    the particular area address range is active. This means that there    are one or more reachable (by intra-area paths) networks contained    in the area address range. The packet's IP destination is then    required to belong to one of these constituent networks. For this    reason, only matching routing table entries with path-type of    intra-area are considered (all others are pruned). If no such[Moy]                                                          [Page 78]

RFC 1247                     OSPF Version 2                    July 1991    matching entries exist, the destination is unreachable (see above).    Otherwise, skip to step 4.(3) Reduce the set of matching entries to those having the most    preferential path-type (seeSection 11). OSPF has a four level    hierarchy of paths. Intra-area paths are the most preferred,    followed in order by inter-area, Type 1 external and Type 2 external    paths.(4) Select the remaining routing table entry that provides the longest    (most specific) match. Another way of saying this is to choose the    remaining entry that specifies the narrowest range of IP    addresses.[10] For example, the entry for the address/mask pair of    (128.185.1.0, 0xffffff00) is more specific than an entry for the    pair (128.185.0.0, 0xffff0000). The default route is the least    specific match, since it matches all destinations.(5) At this point, there may still be multiple routing table entries    remaining. Each routing entry will specify the same range of IP    addresses, but a different IP Type of Service. Select the routing    table entry whose TOS value matches the TOS found in the packet    header. If there is no routing table entry for this TOS, select the    routing table entry for TOS 0. In other words, packets requesting    TOS X are routed along the TOS 0 path if a TOS X path does not    exist.11.2 Sample routing table, without areasConsider the Autonomous System pictured in Figure 2.  No OSPF areas havebeen configured.  A single metric is shown per outbound interface,indicating that routes will not vary based on TOS.  The calculationrouter RT6's routing table proceeds as described inSection 2.1.  Theresulting routing table is shown in Table 12.  Destination types areabbreviated: Network as "N", area border router as "BR" and AS boundaryrouter as "ASBR".There are no instances of multiple equal-cost shortest paths in thisexample.  Also, since there are no areas, there are no inter-area paths.Routers RT5 and RT7 are AS boundary routers.  Intra-area routes havebeen calculated to routers RT5 and RT7.  This allows external routes tobe calculated to the destinations advertised by RT5 and RT7 (i.e.,networks N12, N13, N14 and N15).  It is assumed all AS externaladvertisements originated by RT5 and RT7 are advertising type 1 externalmetrics.  This results in type 1 external paths being calculated todestinations N12-N15.[Moy]                                                          [Page 79]

RFC 1247                     OSPF Version 2                    July 199111.3 Sample routing table, with areasConsider the previous example, this time split into OSPF areas.  An OSPFarea configuration is pictured in Figure 6.  Router RT4's routing tablewill be described for this area configuration.  Router RT4 has aconnection to Area 1 and a backbone connection.  This causes Router RT4to view the AS as the concatenation of the two graphs shown in Figures 7and 8.  The resulting routing table is displayed in Table 13.Again, routers RT5 and RT7 are AS boundary routers.  Routers RT3, RT4,RT7, RT10 and RT11 are area border routers.  Note that there are tworouting entries (in this case having identical paths) for router RT7, inits dual capacities as an area border router and an AS boundary router.Note also that there are two routing entries for the area border routerRT3, since it has two areas in common with RT4 (Area 1 and thebackbone).Backbone paths have been calculated to all area border routers (BR).These are used when determining the inter-area routes.  Note that all ofType   Dest   Area   Path  Type        Cost   Next Hop(s)   Adv. Router(s)__________________________________________________________________________N      N1     0      intra-area        10     RT3           *N      N2     0      intra-area        10     RT3           *N      N3     0      intra-area        7      RT3           *N      N4     0      intra-area        8      RT3           *N      Ib     0      intra-area        7      *             *N      Ia     0      intra-area        12     RT10          *N      N6     0      intra-area        8      RT10          *N      N7     0      intra-area        12     RT10          *N      N8     0      intra-area        10     RT10          *N      N9     0      intra-area        11     RT10          *N      N10    0      intra-area        13     RT10          *N      N11    0      intra-area        14     RT10          *N      H1     0      intra-area        21     RT10          *ASBR   RT5    0      intra-area        6      RT5           *ASBR   RT7    0      intra-area        8      RT10          *__________________________________________________________________________N      N12    *      type 1 external   10     RT10          RT7N      N13    *      type 1 external   14     RT5           RT5N      N14    *      type 1 external   14     RT5           RT5N      N15    *      type 1 external   17     RT10          RT7   Table 12: The routing table for Router RT6 (no configured areas).[Moy]                                                          [Page 80]

RFC 1247                     OSPF Version 2                    July 1991the inter-area routes are associated with the backbone; this is alwaysthe case when the router is itself an area border router.  Routinginformation is condensed at area boundaries.  In this example, we assumethat Area 3 has been defined so that networks N9-N11 and the host routeto H1 are all condensed to a single route when advertised to thebackbone (by router RT11).  Note that the cost of this route is theminimum of the set of costs to its individual components.There is a virtual link configured between routers RT10 and RT11.Without this configured virtual link, RT11 would be unable to advertisea route for networks N9-N11 and host H1 into the backbone, and therewould not be an entry for these networks in router RT4's routing table.In this example there are two equal-cost paths to network N12.  However,they both use the same next hop (Router RT5).Router RT4's routing table would improve (i.e., some of the paths in therouting table would become shorter) if an additional virtual link wereconfigured between router RT4 and router RT3.  The new virtual linkwould itself be associated with the first entry for area border routerRT3 in Table 13 (an intra-area path through Area 1).  This would yield acost of 1 for the virtual link.  The routing table entries changes thatwould be caused by the addition of this virtual link are shown in Table14.12. Link State AdvertisementsEach router in the Autonomous System originates one or more link stateadvertisements.  There are five distinct types of link stateadvertisements, which are described inSection 4.3.  The collection oflink state advertisements forms the link state or topological database.Each separate type of advertisement has a separate function.  Routerlinks and network links advertisements describe how an area's routersand networks are interconnected.  Summary link advertisements provide away of condensing an area's routing information.  AS externaladvertisements provide a way of transparently advertising externally-derived routing information throughout the Autonomous System.Each link state advertisement begins with a standard 20-byte header.This link state header is discussed below.[Moy]                                                          [Page 81]

RFC 1247                     OSPF Version 2                    July 1991Type   Dest        Area   Path  Type        Cost   Next Hop(s)   Adv. Router(s)_______________________________________________________________________________N      N1          1      intra-area        4      RT1           *N      N2          1      intra-area        4      RT2           *N      N3          1      intra-area        1      *             *N      N4          1      intra-area        3      RT3           *BR     RT3         1      intra-area        1      *             *_______________________________________________________________________________N      Ib          0      intra-area        22     RT5           *N      Ia          0      intra-area        27     RT5           *BR     RT3         0      intra-area        21     RT5           *BR     RT7         0      intra-area        14     RT5           *BR     RT10        0      intra-area        22     RT5           *BR     RT11        0      intra-area        25     RT5           *ASBR   RT5         0      intra-area        8      *             *ASBR   RT7         0      intra-area        14     RT5           *_______________________________________________________________________________N      N6          0      inter-area        15     RT5           RT7N      N7          0      inter-area        19     RT5           RT7N      N8          0      inter-area        18     RT5           RT7N      N9-N11,H1   0      inter-area        26     RT5           RT11_______________________________________________________________________________N      N12         *      type 1 external   16     RT5           RT5,RT7N      N13         *      type 1 external   16     RT5           RT5N      N14         *      type 1 external   16     RT5           RT5N      N15         *      type 1 external   23     RT5           RT7     Table 13: Router RT4's routing table in the presence of areas.Type   Dest        Area   Path  Type   Cost   Next Hop(s)   Adv. Router(s)__________________________________________________________________________N      Ib          0      intra-area   16     RT3           *N      Ia          0      intra-area   21     RT3           *BR     RT3         0      intra-area   1      *             *BR     RT10        0      intra-area   16     RT3           *BR     RT11        0      intra-area   19     RT3           *__________________________________________________________________________N      N9-N11,H1   0      inter-area   20     RT3           RT11      Table 14: Changes resulting from an additional virtual link.12.1 The Link State Header[Moy]                                                          [Page 82]

RFC 1247                     OSPF Version 2                    July 1991The link state header contains the LS type, Link State ID andAdvertising Router fields.  The combination of these three fieldsuniquely identifies the link state advertisement.There may be several instances of an advertisement present in theAutonomous System, all at the same time.  It must then be determinedwhich instance is more recent.  This determination is made be examiningthe LS sequence, LS checksum and LS age fields.  These fields are alsocontained in the 20-byte link state header.Several of the OSPF packet types list link state advertisements.  Whenthe instance is not important, an advertisement is referred to by its LStype, Link State ID and Advertising Router (see Link State RequestPackets).  Otherwise, the LS sequence number, LS age and LS checksumfields must also be referenced.A detailed explanation of the fields contained in the link state headerfollows.12.1.1 LS ageThis field is the age of the link state advertisement in seconds.  Itshould be processed as an unsigned 16-bit integer.  It is set to 0 whenthe link state advertisement is originated.  It must be incremented byInfTransDelay on every hop of the flooding procedure.  Link stateadvertisements are also aged as they are held in each router's database.The age of a link state advertisement is never incremented past MaxAge.Advertisements having age MaxAge are not used in the routing tablecalculation.  When an advertisement's age first reaches MaxAge, it isreflooded.  A link state advertisement of age MaxAge is finally flushedfrom the database when it is no longer contained on any neighbor Linkstate retransmission lists.  This indicates that it has beenacknowledged by all adjacent neighbors.  For more information on theaging of link state advertisements, consultSection 14.Ages are examined when a router receives two instances of a link stateadvertisement, both having identical sequence numbers and checksums.  Aninstance of age MaxAge is then always accepted as most recent; thisallows old advertisements to be flushed quickly from the routing domain.Otherwise, if the ages differ by more than MaxAgeDiff, the instancehaving the smaller age is accepted as most recent.[11] SeeSection 13.1for more details.[Moy]                                                          [Page 83]

RFC 1247                     OSPF Version 2                    July 199112.1.2 OptionsThe options field in the link state header indicates which optionalcapabilities are associated with the advertisement.  OSPF's optionalcapabilities are described inSection 4.5.  There are currently twooptional capabilities defined; they are represented by the T-bit and E-bit found in the options field.  The rest of the options field should beset to zero.The E-bit represents OSPF's external routing capability.  This bitshould be set in all advertisements associated with the backbone, andall advertisements associated with non-stub areas (seeSection 3.6).  Itshould also be set in all AS external advertisements.  It should bereset in all router links, network links and summary link advertisementsassociated with a stub area.  For all link state advertisements, thesetting of the E-bit is for informational purposes only; it does notaffect the routing table calculation.The T-bit represents OSPF's TOS routing capability.  This bit should beset in a router links advertisement if and only if the router is capableof calculating separate routes for each IP TOS (seeSection 2.4).  TheT-bit should always be set in network links advertisements.  It shouldbe set in summary link and AS external link advertisements if and onlyif the advertisement describes paths for all TOS values, instead of justthe TOS 0 path.  Note that, with the T-bit set, there may still be onlya single metric in the advertisement (the TOS 0 metric).  This wouldmean that paths for non-zero TOS exist, but are equivalent to the TOS 0path.  A link state advertisement's T-bit is examined when calculatingthe routing table's non-zero TOS paths (seeSection 16.9).12.1.3 LS typeThe LS type field dictates the format and function of the link stateadvertisement.  Advertisements of different types have different names(e.g., router links or network links).  All advertisement types, exceptthe AS external link advertisements (LS type = 5), are floodedthroughout a single area only.  AS external link advertisements areflooded throughout the entire Autonomous System, excluding stub areas(seeSection 3.6).  Each separate advertisement type is brieflydescribed below in Table 15.           LS Type   Advertisement description           __________________________________________________           1         These are the router links                     advertisements. They describe the[Moy]                                                          [Page 84]

RFC 1247                     OSPF Version 2                    July 1991           LS Type   Advertisement description           __________________________________________________                     collected states of the router's                     interfaces. For more information,                     consultSection 12.4.1.           __________________________________________________           2         These are the network links                     advertisements. They describe the set                     of routers attached to the network. For                     more information, consultSection 12.4.2.           __________________________________________________           3 or 4    These are the summary link                     advertisements. They describe                     inter-area routes, and enable the                     condensation of routing information at                     area borders. Originated by area border                     routers, the Type 3 advertisements                     describe routes to networks while the                     Type 4 advertisements describe routes to                     AS boundary routers.           __________________________________________________           5         These are the AS external link                     advertisements. Originated by AS                     boundary routers, they describe routes                     to destinations external to the                     Autonomous System. A default route for                     the Autonomous System can also be                     described by an AS external link                     advertisement.               Table 15: OSPF link state advertisements.12.1.4 Link State IDThis field identifies the piece of the routing domain that is beingdescribed by the advertisement.  Depending on the advertisement's LStype, the Link State ID takes on the values listed in Table 16.[Moy]                                                          [Page 85]

RFC 1247                     OSPF Version 2                    July 1991   LS Type   Link State ID   ______________________________________________________________________   1         The originating router's Router ID.   2         The IP interface address of the network's Designated Router.   3         The destination network's IP address.   4         The Router ID of the described AS boundary router.   5         The destination network's IP address.                Table 16: The advertisement's Link State ID.When the link state advertisement is describing a network, the LinkState ID is either the network's IP address (as in type 3 summary linkadvertisements and in AS external link advertisements) or the network'sIP address is easily derivable from the Link State ID (note that maskinga network links advertisement's Link State ID with the network's subnetmask yields the network's IP address).  When the link stateadvertisement is describing a router, the Link State ID is always thedescribed router's OSPF Router ID.When an AS external advertisement (LS Type = 5) is describing a defaultroute, its Link State ID is set to DefaultDestination (0.0.0.0).12.1.5 Advertising RouterThis field specifies the OSPF Router ID of the advertisement'soriginator.  For router links advertisements, this field is identical tothe Link State ID field.  Network link advertisements are originated bythe network's Designated Router.  Summary link advertisements areoriginated by area border routers.  Finally, AS external linkadvertisements are originated by AS boundary routers.12.1.6 LS sequence numberThe sequence number field is a signed 32-bit integer.  It is used todetect old and duplicate link state advertisements.  The space ofsequence numbers is linearly ordered.  The larger the sequence number(when compared as signed 32-bit integers) the more recent theadvertisement.  To describe to sequence number space more precisely, letN refer in the discussion below to the constant 2**31.The sequence number -N (0x80000000) is reserved (and unused).  Thisleaves -N + 1 (0x80000001) as the smallest (and therefore oldest)sequence number.  A router uses this sequence number the first time it[Moy]                                                          [Page 86]

RFC 1247                     OSPF Version 2                    July 1991originates any link state advertisement.  Afterwards, theadvertisement's sequence number is incremented each time the routeroriginates a new instance of the advertisement.  When an attempt is madeto increment the sequence number past the maximum value of of N - 1(0x7fffffff), the current instance of the advertisement must first beflushed from the routing domain.  This is done by prematurely aging theadvertisement (seeSection 14.1) and reflooding it.  As soon as thisflood has been acknowledged by all adjacent neighbors, a new instancecan be originated with sequence number of -N + 1 (0x80000001).The router may be forced to promote the sequence number of one of itsadvertisements when a more recent instance of the advertisement isunexpectedly received during the flooding process.  This should be arare event.  This may indicate that an out-of-date advertisement,originated by the router itself before its last restart/reload, stillexists in the Autonomous System.  For more information seeSection 13.4.,uh "12.1.7 LS checksum"This field is the checksum of the complete contents of theadvertisement, excepting the age field.  The age field is excepted sothat an advertisement's age can be incremented without updating thechecksum.  The checksum used is the same that is used for ISOconnectionless datagrams; it is commonly referred to as the Fletcherchecksum.  It is documented in Annex C of [RFC 994].  The link stateheader also contains the length of the advertisement in bytes;subtracting the size of the age field (two bytes) yields the amount ofdata to checksum.The checksum is used to detect data corruption of an advertisement.This corruption can occur while an advertisement is being flooded, orwhile it is being held in a router's memory.  The LS checksum fieldcannot take on the value of zero; the occurrence of such a value shouldbe considered a checksum failure.  In other words, calculation of thechecksum is not optional.The checksum of a link state advertisement is verified in two cases: a)when it is received in a Link State Update Packet and b) at times duringthe aging of the link state database.  The detection of a checksumfailure leads to separate actions in each case.  See Sections13 and14for more details.Whenever the LS sequence number field indicates that two instances of anadvertisement are the same, the LS checksum field is examined.  If thereis a difference, the instance with the larger checksum is considered tobe most recent.[12] SeeSection 13.1 for more details.[Moy]                                                          [Page 87]

RFC 1247                     OSPF Version 2                    July 199112.2 The link state databaseA router has a separate link state database for every area to which itbelongs.  The link state database has been referred to elsewhere in thetext as the topological database.  All routers belonging to the samearea have identical topological databases for the area.The databases for each individual area are always dealt with separately.The shortest path calculation is performed separately for each area (seeSection 16).  Components of the area topological database are floodedthroughout the area only.  Finally, when an adjacency (belonging to AreaA) is being brought up, only the database for Area A is synchronizedbetween the two routers.The area database is composed of router links advertisements, networklinks advertisements, and summary link advertisements (all listed in thearea data structure).  In addition, external routes (AS externaladvertisements) are included in all non-stub area databases (seeSection3.6).An implementation of OSPF must be able to access individual pieces of anarea database.  This lookup function is based on an advertisement's LStype, Link State ID and Advertising Router.[13] There will be a singleinstance (the most up-to-date) of each link state advertisement in thedatabase.  The database lookup function is invoked during the link stateflooding procedure (Section 13) and the routing table calculation(Section 16).  In addition, using this lookup function the router candetermine whether it has itself ever originated a particular link stateadvertisement, and if so, with what LS sequence number.A link state advertisement is added to a router's database when eithera) it is received during the flooding process (Section 13) or b) it isoriginated by the router itself (Section 12.4).  A link stateadvertisement is deleted from a router's database when either a) it hasbeen overwritten by a newer instance during the flooding process(Section 13) or b) the router originates a newer instance of one of itsself-originated advertisements (Section 12.4) or c) the advertisementages out and is flushed from the routing domain (Section 14).  Whenevera link state advertisement is deleted from the database it must also beremoved from all neighbors' Link state retransmission lists (seeSection10).12.3 Representation of TOSAll OSPF link state advertisements (with the exception of network linksadvertisements) specify metrics.  In router links advertisements, themetrics indicate the costs of the described interfaces.  In summary link[Moy]                                                          [Page 88]

RFC 1247                     OSPF Version 2                    July 1991and AS external link advertisements, the metric indicates the cost ofthe described path.  In all of these advertisements, a separate metriccan be specified for each IP TOS.  TOS is encoded in an OSPF link stateadvertisement as the following mapping of the Delay (D), Throughput (T)and Reliability (R) flags found in the IP packet header's TOS field (see[RFC 791]).                         OSPF encoding   D   T   R                         _________________________                         0               0   0   0                         4               0   0   1                         8               0   1   0                         12              0   1   1                         16              1   0   0                         20              1   0   1                         24              1   1   0                         28              1   1   1                    Table 17: Representing TOS in OSPF.Each OSPF link state advertisement must specify the TOS 0 metric.  OtherTOS metrics, if they appear, must appear in order of increasing TOSencoding.  For example, the TOS 8 (high throughput) metric must alwaysappear before the TOS 16 (low delay) metric when both are specified.  Ifa metric for some non-zero TOS is not specified, its cost defaults tothe cost for TOS 0, unless the T-bit is reset in the advertisement'soptions field (seeSection 12.1.2 for more details).Note that if more TOS types are defined in a future IP architecture,OSPF's TOS encoding can be extended in a straightforward manner.12.4 Originating link state advertisementsA router may originate many types of link state advertisements.  Arouter originates a router links advertisement for each area to which itbelongs.  If the router is also the Designated Router for any of itsattached networks, it will originate a network links advertisement forthat network.Area border routers originate a single summary links advertisement foreach known inter-area destination.  AS boundary routers originate asingle AS external links advertisement for each known AS externaldestination.  Destinations are advertised one at a time so that the[Moy]                                                          [Page 89]

RFC 1247                     OSPF Version 2                    July 1991change in any single route can be flooded without reflooding the entirecollection of routes.  During the flooding procedure, many link stateadvertisements can be carried by a single Link State Update packet.As an example, consider router RT4 in Figure 6.  It is an area borderrouter, having a connection to Area 1 and the backbone.  Router RT4originates 5 distinct link state advertisements into the backbone (onerouter links, and one summary link for each of the networks N1-N4).Router RT4 will also originate 8 distinct link state advertisements intoArea 1 (one router links and seven summary link advertisements aspictured in Figure 7).  If RT4 has been selected as Designated Routerfor network N3, it will also originate a network links advertisement forN3 into Area 1.In this same figure, router RT5 will be originating 3 distinct ASexternal link advertisements (one for each of the networks N12-N14).These will be flooded throughout the entire AS, assuming that none ofthe areas have been configured as stubs.  However, if area 3 has beenconfigured as a stub area, the external advertisements for networksN12-N14 will not be flooded into area 3 (seeSection 3.6).  Instead,router RT11 would originate a default summary link advertisement thatwould be flooded throughout area 3 (seeSection 12.4.3).  This instructsall of area 3's internal routers to send their AS external traffic toRT11.Whenever a new instance of a link state advertisement is originated, itsLS sequence number is incremented, its LS age is set to 0, its LSchecksum is calculated, and the advertisement is added to the link statedatabase and flooded out the appropriate interfaces.  SeeSection 13.2for details concerning the installation of the advertisement into thelink state database.  SeeSection 13.3 for details concerning theflooding of newly originated advertisements.The eight events that cause a new instance of a link state advertisementto be originated are:(1) The LS refresh timer firing.  There is a LS refresh timer for each    link state advertisement that the router has originated.  The LS    refresh timer is an interval timer, with length LSRefreshTimer.  The    LS refresh timer guarantees periodic originations regardless of any    other events that cause new instances.  This periodic updating of    link state advertisements adds robustness to the link state    algorithm.  Link state advertisements that solely describe    unreachable destinations should not be refreshed, but should instead    be flushed from the routing domain (seeSection 14.1).[Moy]                                                          [Page 90]

RFC 1247                     OSPF Version 2                    July 1991When whatever is being described by a link state advertisement changes,a new advertisement is originated.  Two instances of the same link stateadvertisement may not be originated within the time periodMinLSInterval.  This may require that the generation of the nextinstance to be delayed by up to MinLSInterval.  The following changesmay cause a router to originate a new instance of an advertisement.These changes should cause new originations only if the contents of thenew advertisement would be different.(2) An interface's state changes (seeSection 9.1).  This may mean that    it is necessary to produce a new instance of the router links    advertisement.(3) An attached network's Designated Router changes.  A new router links    advertisement should be originated.  Also, if the router itself is    now the Designated Router, a new network links advertisement should    be produced.(4) One of the neighboring routers changes to/from the FULL state.  This    may mean that it is necessary to produce a new instance of the    router links advertisement.  Also, if the router is itself the    Designated Router for the attached network, a new network links    advertisement should be produced.The next three events concern area border routers only.(5) An intra-area route has been added/deleted/modified in the routing    table.  This may cause a new instance of a summary links    advertisement (for this route) to be originated in each attached    area (this includes the backbone).(6) An inter-area route has been added/deleted/modified in the routing    table.  This may cause a new instance of a summary links    advertisement (for this route) to be originated in each attached    area (but NEVER for the backbone).(7) The router becomes newly attached to an area.  The router must then    originate summary link advertisements into the newly attached area    for all pertinent intra-area and inter-area routes in its routing    table.  SeeSection 12.4.3 for more details.The last event concerns AS boundary routers only.[Moy]                                                          [Page 91]

RFC 1247                     OSPF Version 2                    July 1991(8) An external route gained through direct experience with an external    routing protocol (like EGP) changes.  This will cause the AS    boundary router to originate a new instance of an external links    advertisement.The construction of each type of the link state advertisement isexplained below.  In general, these sections describe the contents ofthe advertisement body (i.e., the part coming after the 20-byteadvertisement header).  For information concerning the building of thelink state advertisement header, seeSection 12.1.12.4.1 Router linksA router originates a router links advertisement for each area that itbelongs to.  Such an advertisement describes the collected states of therouter's links to the area.  The advertisement is flooded throughout theparticular area, and no further.The format of a router links advertisement is shown inAppendix A(Section A.4.2).  The first 20 bytes of the advertisement consist of thegeneric link state header that was discussed inSection 12.1.  Routerlinks advertisements have LS type = 1.  The router indicates whether itis willing to calculate separate routes for each IP TOS by setting (orresetting) the T-bit of the link state advertisement's Options field.A router also indicates whether it is an area border router, or an ASboundary router, by setting the appropriate bits in its router linksadvertisements.  This enables paths to those types of routers to besaved in the routing table, for later processing of summary linkadvertisements and AS external link advertisements.The router links advertisement then describes the router's workingconnections (links) to the area.  Each link is typed according to the               _________________________________________                (Figure not included in text version.)               Figure 15: Area 1 with IP addresses shown                 Figure 16: Forwarding address example               _________________________________________[Moy]                                                          [Page 92]

RFC 1247                     OSPF Version 2                    July 1991kind of attached network.  Each link is also labelled with its Link ID.This ID gives a name to the entity that is on the other end of the link.Table 18 summarizes the values used for the type and Link ID fields.Link type   Description               Link ID____________________________________________________________________________1           Point-to-point link     Neighbor Router ID2           Link to transit network Interface address of Designated Router3           Link to stub network    IP network number4           Virtual link            Neighbor Router ID       Table 18: Link descriptions in the router links advertisement.In addition, the Link Data field is specified for each link.  This fieldgives 32 bits of extra information for the link.  For links to routersand transit networks, this field specifies the IP interface address ofthe associated router interface (this is needed by the routing tablecalculation, seeSection 16.3).  For links to stub networks, this fieldspecifies the network's IP address mask.Finally, the cost of using the link for output (possibly specifying adifferent cost for each type of service) is specified.  The output costof a link is configurable.  It must always be non-zero.To further describe the process of building the list of link records,suppose a router wishes to build router links advertisement for an AreaA.  The router examines its collection of interface data structures.For each interface, the following steps are taken:o   If the attached network does not belong to Area A, no links are    added to the advertisement, and the next interface should be    examined.o   Else, if the state of the interface is Down, no links are added.o   Else, if the state of the interface is Point-to-Point, then add    links according to the following:    -   If the neighboring router is fully adjacent, add a Type 1 link        (point-to-point) if this is an interface to a point-to-point        network, or add a type 4 link (virtual link) if this is a        virtual link.  The Link ID should be set to the Router ID of the        neighboring router, and the Link Data should specify the[Moy]                                                          [Page 93]

RFC 1247                     OSPF Version 2                    July 1991        interface IP address.    -   If this is a numbered point-to-point network (i.e, not a virtual        link and not an unnumbered point-to-point network) and the        neighboring router's IP address is known, add a Type 3 link        (stub network) whose Link ID is the neighbor's IP address, whose        Link Data is the mask 0xffffffff indicating a host route, and        whose cost is the interface's configured output cost.o   Else if the state of the interface is Loopback, add a Type 3 link    (stub network) as long as this is not an interface to an unnumbered    serial line.  The Link ID should be set to the IP interface address,    the Link Data set to the mask 0xffffffff (indicating a host route),    and the cost set to 0.o   Else if the state of the interface is Waiting, add a Type 3 link    (stub network) whose Link ID is the IP network number of the    attached network and whose Link Data is the attached network's    address mask.o   Else, there has been a Designated Router selected for the attached    network.  If the router is fully adjacent to the Designated Router,    or if the router itself is Designated Router and is fully adjacent    to at least one other router, add a single Type 2 link (transit    network) whose whose link ID is the IP interface address of the    attached network's Designated Router (which may be the router    itself) and whose Link Data is the interface IP address.  Otherwise,    add a link as if the interface state were Waiting (see above).Unless otherwise specified, the cost of each link generated by the aboveprocedure is equal to the output cost of the associated interface.  Notethat in the case of serial lines, multiple links may be generated by asingle interface.After consideration of all the router interfaces, host links are addedto the advertisement by examining the list of attached hosts.  A hostroute is represented as a Type 3 link (stub network) whose link ID isthe host's IP address and whose Link Data is the mask of all ones(0xffffffff).As an example, consider the router links advertisements generated byrouter RT3, as pictured in Figure 6.  The area containing router RT3(Area 1) has been redrawn, with actual network addresses, in Figure 15.Assume that the last byte of all of RT3's interface addresses is 3,giving it the interface addresses 192.1.1.3 and 192.1.4.3, and that theother routers have similar addressing schemes.  In addition, assume thatall links are functional, and that Router IDs are assigned as the[Moy]                                                          [Page 94]

RFC 1247                     OSPF Version 2                    July 1991smallest IP interface address.RT3 originates two router links advertisements, one for Area 1 and onefor the backbone.  Assume that router RT4 has been selected as theDesignated router for network 192.1.1.0.  RT3's router linksadvertisement for Area 1 is then shown below.  It indicates that RT3 hastwo connections to Area 1, the first a link to the transit network192.1.1.0 and the second a link to the stub network 192.1.4.0.Notethat the transit network is identified by the IP interface of itsDesignated Router (i.e., the Link ID = 192.1.1.4 which is the DesignatedRouter RT4's IP interface to 192.1.1.0).  Note also that RT3 hasindicated that it is capable of calculating separate routes based on IPTOS, through setting the T-bit in the Options field.  It has alsoindicated that it is an area border router.       ; RT3's router links advertisement for Area 1       LS age = 0                     ;always true on origination       Options = (T-bit|E-bit)        ;TOS-capable       LS type = 1                    ;indicates router links       Link State ID = 192.1.1.3      ;RT3's Router ID       Advertising Router = 192.1.1.3 ;RT3's Router ID       bit E = 0                      ;not an AS boundary router       bit B = 1                      ;RT3 is an area border router       #links = 2               Link ID = 192.1.1.4    ;IP address of Designated Router               Link Data = 192.1.1.3  ;RT3's IP interface to net               Type = 2               ;connects to transit network               # other metrics = 0               TOS 0 metric = 1               Link ID = 192.1.4.0    ;IP Network number               Link Data = 0xffffff00 ;Network mask               Type = 3               ;connects to stub network               # other metrics = 0               TOS 0 metric = 2Next RT3's router links advertisement for the backbone is shown.  Itindicates that RT3 has a single attachment to the backbone.  Thisattachment is via an unnumbered point-to-point link to router RT6.  RT3has again indicated that it is TOS-capable, and that it is an areaborder router.       ; RT3's router links advertisement for the backbone       LS age = 0                     ;always true on origination       Options = (T-bit|E-bit)        ;TOS-capable       LS type = 1                    ;indicates router links[Moy]                                                          [Page 95]

RFC 1247                     OSPF Version 2                    July 1991       Link State ID = 192.1.1.3      ;RT3's router ID       Advertising Router = 192.1.1.3 ;RT3's router ID       bit E = 0                      ;not an AS boundary router       bit B = 1                      ;RT3 is an area border router       #links = 1               Link ID = 18.10.0.6    ;Neighbor's Router ID               Link Data = 0.0.0.0    ;Interface to unnumbered SL               Type = 1               ;connects to router               # other metrics = 0               TOS 0 metric = 8Even though router RT3 has indicated that it is TOS-capable in the aboveexamples, only a single metric (the TOS 0 metric) has been specified foreach interface.  Different metrics can be specified for each TOS.  Theencoding of TOS in OSPF link state advertisements is described inSection 12.3.As an example, suppose the point-to-point link between routers RT3 andRT6 in Figure 15 is a satellite link.  The AS administrator may want toencourage the use of the line for high bandwidth traffic.  This would bedone by setting the metric artificially low for that TOS.  Router RT3would then originate the following router links advertisement for thebackbone (IP TOS 8 = high bandwidth):       ; RT3's router links advertisement for the backbone       LS age = 0                  ;always true on origination       Options = (T-bit|E-bit)     ;TOS-capable       LS type = 1                 ;indicates router links       Link State ID = 192.1.1.3   ;RT3's Router ID       Advertising Router = 192.1.1.3       bit E = 0                   ;not an AS boundary router       bit B = 1                   ;RT3 is an area border router       #links = 1               Link ID = 18.10.0.6 ; Neighbor's Router ID               Link Data = 0.0.0.0 ;Interface to unnumbered SL               Type = 1            ;connects to router               # other metrics = 1               TOS 0 metric = 8                       TOS = 8     ;High bandwidth                       metric = 1  ;traffic preferred12.4.2 Network linksA network links advertisement is generated for every transit multi-access network.  (A transit network is a network having two or moreattached routers).  The network links advertisement describes all the[Moy]                                                          [Page 96]

RFC 1247                     OSPF Version 2                    July 1991routers that are attached to the network.The Designated Router for the network originates the advertisement.  TheDesignated Router originates the advertisement only if it is fullyadjacent to at least one other router on the network.  The network linksadvertisement is flooded throughout the area that contains the transitnetwork, and no further.  The networks links advertisement lists thoserouters that are fully adjacent to the Designated Router; each fullyadjacent router is identified by its OSPF Router ID.  The DesignatedRouter includes itself in this list.The Link State ID for a network links advertisement is the IP interfaceaddress of the Designated Router.  This value, masked by the network'saddress mask (which is also contained in the network linksadvertisement) yields the network's IP address.A router that has formerly been the Designated Router for a network, butis no longer, should flush the network links advertisement that it hadpreviously originated.  This advertisement is no longer used in therouting table calculation.  It is flushed by prematurely incrementingthe advertisement's age to MaxAge and reflooding (seeSection 14.1).As an example of a network links advertisement, again consider the areaconfiguration in Figure 6.  Network links advertisements are originatedfor network N3 in Area 1, networks N6 and N8 in Area 2, and network N9in Area 3.  Assuming that router RT4 has been selected as the DesignatedRouter for network N3, the following network links advertisement isgenerated by RT4 on behalf of network N3 (see Figure 15 for the addressassignments):       ; network links advertisement for network N3       LS age = 0                     ;always true on origination       Options = (T-bit|E-bit)        ;TOS-capable       LS type = 2                    ;indicates network links       Link State ID = 192.1.1.4      ;IP address of Designated Router       Advertising Router = 192.1.1.4 ;RT4's Router ID       Network Mask = 0xffffff00               Attached Router = 192.1.1.4    ;Router ID               Attached Router = 192.1.1.1    ;Router ID               Attached Router = 192.1.1.2    ;Router ID               Attached Router = 192.1.1.3    ;Router ID12.4.3 Summary linksEach summary link advertisement describes a route to a singledestination.  Summary link advertisements are flooded throughout a[Moy]                                                          [Page 97]

RFC 1247                     OSPF Version 2                    July 1991single area only.  The destination described is one that is external tothe area, yet still belonging to the Autonomous System.The DefaultDestination can also be specified in summary linkadvertisements.  This is used when implementing OSPF's stub areafunctionality (seeSection 3.6).  In a stub area, instead of importingexternal routes each area border router originates a "default summarylink" (Link State ID = DefaultDestination) into the area.Summary link advertisements are originated by area border routers.  Theprecise summary routes to advertise into an area are determined byexamining the routing table structure (seeSection 11).  Only intra-arearoutes are advertised into the backbone.  Both intra-area and inter-arearoutes are advertised into the other areas.To determine which routes to advertise into an attached Area A, eachrouting table entry is processed as follows:o   Only Destination types of network and AS boundary router are    advertised in summary link advertisements.  If the routing table    entry's Destination type is area border router, examine the next    routing table entry.o   AS external routes are never advertised in summary link    advertisements.  If the routing table entry has Path-type type 1    external or type 2 external, examine the next routing table entry.o   Else, if the area associated with this set of paths is the Area A    itself, do not generate a summary link advertisement for the    route.[14]o   Else, if the destination of this route is an AS boundary router,    generate a Type 4 link state advertisement for the destination, with    Link State ID equal to the AS boundary router's ID and metric equal    to the routing table entry's cost.  These advertisements should not    be generated if area A has been configured as a stub area.o   Else, the Destination type is network.  If this is an inter-area    route, generate a Type 3 advertisement for the destination, with    Link State ID equal to the network's address and metric equal to the    routing table cost.o   The one remaining case is an intra-area route to a network.  This    means that the network is contained in one of the router's directly    attached areas.  In general, this information must be condensed    before appearing in summary link advertisements.  Remember that an    area has been defined as a list of address ranges, each range[Moy]                                                          [Page 98]

RFC 1247                     OSPF Version 2                    July 1991    consisting of an [address,mask] pair.  A single Type 3 advertisement    must be made for each range, with Link State ID equal to the range's    address and cost equal to the smallest cost of any of the component    networks.    If virtual links are being used to provide/increase connectivity of    the backbone, routing information concerning the backbone networks    should not be condensed before being summarized into the virtual    links' transit areas.  In other words, the backbone ranges should be    ignored when originating summary links into these areas.  The    existence of virtual links can be determined during the shortest    path calculation for the backbone (seeSection 16.1).In addition, if area A has been configured as a stub area and the routeris an area border router, it should advertise a default summary linkinto Area A.  The Link State ID for the advertisement should be set toDefaultDestination, and the metric set to the (per-area) configurableparameter StubDefaultCost.If a router advertises a summary advertisement for a destination whichthen becomes unreachable, the router must then flush the advertisementfrom the routing domain by setting its age to MaxAge and reflooding (seeSection 14.1).  Also, if the destination is still reachable, yet can nolonger be advertised according to the above procedure (e.g., it is nowan inter-area route, when it used to be an intra-area route associatedwith some non-backbone area; it would thus no longer be advertisable tothe backbone), the advertisement should also be flushed from the routingdomain.For an example of summary link advertisements, consider again the areaconfiguration in Figure 6.  Routers RT3, RT4, RT7, RT10 and RT11 are allarea border routers, and therefore are originating summary linksadvertisements.  Consider in particular router RT4.  Its routing tablewas calculated as the example inSection 11.3.  RT4 originates summarylink advertisements into both the backbone and Area 1.  Into thebackbone, router RT4 originates separate advertisements for each of thenetworks N1-N4.  Into Area 1, router RT4 originates separateadvertisements for networks N6-N8 and the AS boundary routers RT5,RT7.It also condenses host routes Ia and Ib into a single summaryadvertisement.  Finally, the routes to networks N9,N10,N11 and host H9are advertised by a single summary link.  This condensation wasoriginally performed by the router RT11.These advertisements are illustrated graphically in Figures 7 and 8.Two of the summary link advertisements originated by router RT4 follow.The actual IP addresses for the networks and routers in question havebeen assigned in Figure 15.[Moy]                                                          [Page 99]

RFC 1247                     OSPF Version 2                    July 1991       ; summary link advertisement for network N1,       ; originated by router RT4 into the backbone       LS age = 0                  ;always true on origination       Options = (T-bit|E-bit)     ;TOS-capable       LS type = 3                 ;indicates summary link to IP net       Link State ID = 192.1.2.0   ;N1's IP network number       Advertising Router = 192.1.1.4       ;RT4's ID               TOS = 0               metric = 4       ; summary link advertisement for AS boundary router RT7       ; originated by router RT4 into Area 1       LS age = 0                  ;always true on origination       Options = (T-bit|E-bit)     ;TOS-capable       LS type = 4                 ;indicates summary link to ASBR       Link State ID = router RT7's ID       Advertising Router = 192.1.1.4       ;RT4's ID               TOS = 0               metric = 14Summary link advertisements pertain to a single destination (IP networkor AS boundary router).  However, for a single destination there may beseparate sets of paths, and therefore separate routing table entries,for each Type of Service.  All these entries must be considered whenbuilding the summary link advertisement for the destination; a singleadvertisement must specify the separate costs (if they exist) for eachTOS.  The encoding of TOS in OSPF link state advertisements is describedinSection 12.3.Clearing the T-bit in the Options field of a summary link advertisementindicates that there is a TOS 0 path to the destination, but no pathsfor non-zero TOS.  This can happen when non-TOS capable routers exist inthe routing domain (seeSection 2.4).12.4.4 AS external linksAS external link advertisements describe routes to destinations externalto the Autonomous System.  Most AS external link advertisements describeroutes to specific external destinations.  However, a default route forthe Autonomous System can be described in an AS external advertisementby setting the advertisement's Link State ID to DefaultDestination(0.0.0.0).  AS external link advertisements are originated by ASboundary routers.  An AS boundary router originates a single AS externallink advertisement for each external route that it has learned, eitherthrough another routing protocol (such as EGP), or through configuration[Moy]                                                         [Page 100]

RFC 1247                     OSPF Version 2                    July 1991information.In general, AS external link advertisements are the only type of linkstate advertisements that are flooded throughout the entire AutonomousSystem; all other types of link state advertisements are specific to asingle area.  However, AS external advertisements are not floodedinto/throughout stub areas (seeSection 3.6).  This enables a reductionin link state database size for routers internal to stub areas.The metric that is advertised for an external route can be one of twotypes.  Type 1 metrics are comparable to the link state metric.  Type 2metrics are assumed to be larger than the cost of any intra-AS path.  Aswith summary link advertisements, if separate paths exist based on TOS,separate TOS costs can be included in the AS external linkadvertisement.  The encoding of TOS in OSPF link state advertisements isdescribed inSection 12.3.  If the T-bit of the advertisement's Optionsfield is clear, no non-zero TOS paths to the destination exist.If a router advertises an AS external link advertisement for adestination which then becomes unreachable, the router must then flushthe advertisement from the routing domain by setting its age to MaxAgeand reflooding (seeSection 14.1).For an example of AS external link advertisements, consider once againthe AS pictured in Figure 6.  There are two AS boundary routers: RT5 andRT7.  Router RT5 originates three external link advertisements, fornetworks N12-N14.  Router RT7 originates two external linkadvertisements, for networks N12 and N15.  Assume that RT7 has learnedits route to N12 via EGP, and that it wishes to advertise a Type 2metric to the AS.  RT7 would then originate the following advertisementfor N12:       ; AS external link advertisement for network N12,       ; originated by router RT7       LS age = 0                  ;always true on origination       Options = (T-bit|E-bit)     ;TOS-capable       LS type = 5                 ;indicates AS external link       Link State ID = N12's IP network number       Advertising Router = Router RT7's ID               bit E = 1           ;Type 2 metric               TOS = 0               metric = 2               Forwarding address = 0.0.0.0In the above example, the forwarding address field has been set to0.0.0.0, indicating that packets for the external destination should beforwarded to the advertising OSPF router (RT7).  This is not always[Moy]                                                         [Page 101]

RFC 1247                     OSPF Version 2                    July 1991desirable.  Consider the example pictured in Figure 16.  There are threeOSPF routers (RTA, RTB and RTC) connected to a common network.  Only oneof these routers, RTA, is exchanging EGP information with the non-OSPFrouter RTX.  RTA must then originate AS external link stateadvertisements for those destinations it has learned from RTX.  By usingthe AS external advertisement's forwarding address field, RTA canspecify that packets for these destinations be forwarded directly toRTX.  Without this feature, routers RTB and RTC would take an extra hopto get to these destinations.Note that when the forwarding address field is non-zero, it should pointto a router belonging to another Autonomous System.A forwarding address can also be specified for the default route.  Forexample, in figure 16 RTA may want to specify that all externally-destined packets should by default be forwarded to its EGP peer RTX.The resulting AS external link advertisement is pictured below.  Notethat the Link State ID is set to DefaultDestination.       ; Default route, originated by router RTA       ; Packets forwarded through RTX       LS age = 0                  ;always true on origination       Options = (T-bit|E-bit)     ;TOS-capable       LS type = 5                 ;indicates AS external link       Link State ID = DefaultDestination  ; default route       Advertising Router = Router RTA's ID               bit E = 1           ;Type 2 metric               TOS = 0               metric = 1               Forwarding address = RTX's IP addressIn figure 16, suppose instead that both RTA and RTB exchange EGPinformation with RTX.  In this case, RTA and RTB would originate thesame set of external advertisements.  These advertisements, if theyspecify the same metric, would be functionally equivalent since theywould specify the same destination and forwarding address (RTX).  Thisleads to a clear duplication of effort.  If only one of RTA or RTBoriginated the set of external advertisements, the routing would remainthe same, and the size of the link state database would decrease.However, it must be unambiguously defined as to which router originatesthe advertisements (otherwise neither may, or the identity of theoriginator may oscillate).  The following rule is thereby established:if two routers, both reachable from one another, originate functionallyequivalent AS external advertisements (i.e., same destination, cost andnon-zero forwarding address), then the advertisement originated by therouter having the highest OSPF Router ID is used.  The router having thelower OSPF Router ID can then flush its advertisement.  Flushing a link[Moy]                                                         [Page 102]

RFC 1247                     OSPF Version 2                    July 1991state advertisement is discussed inSection 14.1.13. The Flooding ProcedureLink State Update packets provide the mechanism for flooding link stateadvertisements.  A Link State Update packet may contain several distinctadvertisements, and floods each advertisement one hop further from itspoint of origination.  To make the flooding procedure reliable, eachadvertisement must be acknowledged separately.  Acknowledgments aretransmitted in Link State Acknowledgment packets.  Many separateacknowledgments can be grouped together into a single packet.The flooding procedure starts when a Link State Update packet has beenreceived.  Many consistency checks have been made on the received packetbefore being handed to the flooding procedure (seeSection 8.2).  Inparticular, the Link State Update packet has been associated with aparticular neighbor, and a particular area.  If the neighbor is in alesser state than Exchange, the packet should be dropped without furtherprocessing.All types of link state advertisements, other than AS external links,are associated with a specific area.  However, link state advertisementsdo not contain an area field.  A link state advertisement's area must bededuced from the Link State Update packet header.For each link state advertisement contained in the packet, the followingsteps are taken:(1) Validate the advertisement's link state checksum.  If the checksum    turns out to be invalid, discard the advertisement and get the next    one from the Link State Update packet.(2) Examine the link state advertisement's LS type.  If the LS type is    unknown, discard the advertisement and get the next one from the    Link State Update Packet.  This specification defines LS Types 1-5    (seeSection 4.3).(3) Else if this is a AS external advertisement (LS type = 5), and the    area has been configured as a stub area, discard the advertisement    and get the next one from the Link State Update Packet.  AS external    advertisements are not flooded into/throughout stub areas (seeSection 3.6).(4) Else if the advertisement's age is equal to MaxAge, and there is    currently no instance of the advertisement in the router's link    state database, then take the following actions:[Moy]                                                         [Page 103]

RFC 1247                     OSPF Version 2                    July 1991    (a) Acknowledge the receipt of the advertisement by sending a Link        State Acknowledgment packet back to the sending neighbor (seeSection 13.5).    (b) Purge all outstanding requests for equal or previous instances        of the advertisement from the sending neighbor's Link State        Request list (seeSection 10).    (c) If the sending neighbor is in state Exchange or in state        Loading, then install the MaxAge advertisement in the link state        database.  Otherwise, simply discard the advertisement.  In        either case, examine the next advertisement (if any) listed in        the Link State Update packet.(5) Otherwise, find the instance of this advertisement that is currently    contained in the router's link state database.  If there is no    database copy, or the received advertisement is more recent than the    database copy (seeSection 13.1 below for the determination of which    advertisement is more recent) the following steps must be performed:    (a) If there is already a database copy, and if the database copy        was installed less than MinLSInterval seconds ago, discard the        new advertisement (without acknowledging it) and examine the        next advertisement (if any) listed in the Link State Update        packet.    (b) Otherwise immediately flood the new advertisement out some        subset of the router's interfaces (seeSection 13.3).  In some        cases (e.g., the state of the receiving interface is DR and the        advertisement was received from a router other than the Backup        DR) the advertisement will be flooded back out the receiving        interface.  This occurrence should be noted for later use by the        acknowledgment process (Section 13.5).    (c) Remove the current database copy from all neighbors' Link state        retransmission lists.    (d) Install the new advertisement in the link state database        (replacing the current database copy).  This may cause the        routing table calculation to be scheduled.  In addition,        timestamp the new advertisement with the current time (i.e., the        time it was received).  The flooding procedure cannot overwrite        the newly installed advertisement until MinLSInterval seconds        have elapsed.  The advertisement installation process is        discussed further inSection 13.2.    (e) Possibly acknowledge the receipt of the advertisement by sending        a Link State Acknowledgment packet back out the receiving[Moy]                                                         [Page 104]

RFC 1247                     OSPF Version 2                    July 1991        interface.  This is explained below inSection 13.5.    (f) If this new link state advertisement indicates that it was        originated by this router itself, the router must advance the        advertisement's link state sequence number, and issue a new        instance of the advertisement (seeSection 13.4).(6) Else, if there is an instance of the advertisement on the sending    neighbor's Link state request list, an error has occurred in the    Database Description process.  In this case, restart the Database    Description process by generating the neighbor event BadLSReq for    the sending neighbor and stop processing the Link State Update    packet.(7) Else, if the received advertisement is the same instance as the    database copy (i.e., neither one is more recent) the following two    steps should be performed:    (a) If the advertisement is listed in the Link state retransmission        list for the receiving adjacency, the router itself is expecting        an acknowledgment for this advertisement.  The router should        treat the received advertisement as an acknowledgment, by        removing the advertisement from the Link state retransmission        list.  This is termed an "implied acknowledgment".  Its        occurrence should be noted for later use by the acknowledgment        process (Section 13.5).    (b) Possibly acknowledge the receipt of the advertisement by sending        a Link State Acknowledgment packet back out the receiving        interface.  This is explained below inSection 13.5.(8) Else, the database copy is more recent.  Note an unusual event to    network management, discard the advertisement and process the next    link state advertisement contained in the packet.13.1 Determining which link state is newerWhen a router encounters two instances of a link state advertisement, itmust determine which is more recent.  This occurred above when comparinga received advertisement to the database copy.  This comparison mustalso be done during the database exchange procedure which occurs duringadjacency bring-up.A link state advertisement is identified by its LS type, Link State IDand Advertising Router.  For two instances of the same advertisement,the LS sequence number, LS age, and LS checksum fields are used todetermine which instance is more recent:[Moy]                                                         [Page 105]

RFC 1247                     OSPF Version 2                    July 1991o   The advertisement having the newer LS sequence number is more    recent.  SeeSection 12.1.6 for an explanation of the LS sequence    number space.  If both instances have the same LS sequence number,    then:o   If the two instances have different LS checksums, then the instance    having the larger LS checksum (when considered as a 16-bit unsigned    integer) is considered more recent.o   Else, if only one of the instances is of age MaxAge, the instance of    age MaxAge is considered to be more recent.o   Else, if the ages of the two instances differ by more than    MaxAgeDiff, the instance having the smaller (younger) age is    considered to be more recent.o   Else, the two instances are considered to be identical.13.2 Installing link state advertisements in the databaseInstalling a new link state advertisement in the database, either as theresult of flooding or a newly self originated advertisement, may causethe routing table structure to be recalculated.  The contents of the newadvertisement should be compared to the old instance, if present.  Ifthere is no difference, there is no need to recalculate the routingtable.  (Note that even if the contents are the same, the LS checksumwill probably be different, since the checksum covers the LS sequencenumber.)If the contents are different, the following pieces of the routing tablemust be recalculated, depending on the LS type field:Router links, network links    The entire routing table must be recalculated, starting with the    shortest path calculations for each area (not just the area whose    topological database has changed).  The reason that the shortest    path calculation cannot be restricted to the single changed area has    to do with the fact that AS boundary routers may belong to multiple    areas.  A change in the area currently providing the best route may    force the router to use an intra-area route provided by a different    area.[15]Summary link    The best route to the destination described by the summary link    advertisement must be re-examined (seeSection 16.5).  If this    destination is an AS boundary router, it may also be necessary to[Moy]                                                         [Page 106]

RFC 1247                     OSPF Version 2                    July 1991    re-examine all the AS external link advertisements.AS external link    The best route to the destination described by the AS external link    advertisement must be re-examined (seeSection 16.6).Also, any old instance of the advertisement must be removed from thedatabase when the new advertisement is installed.  This old instancemust also be removed from all neighbors' Link state retransmission lists(seeSection 10).13.3 Next step in the flooding procedureWhen a new (and more recent) advertisement has been received, it must beflooded out some set of the router's interfaces.  This section describesthe second part of flooding procedure (the first part being theprocessing that occurred inSection 13), namely, selecting the outgoinginterfaces and adding the advertisement to the appropriate neighbors'Link state retransmission lists.  Also included in this part of theflooding procedure is the maintenance of the neighbors' Link staterequest lists.This section is equally applicable to the flooding of an advertisementthat the router itself has just originated (seeSection 12.4).  Forthese advertisements, this section provides the entirety of the floodingprocedure (i.e., the processing ofSection 13 is not performed, since,for example, the advertisement has not been received from a neighbor andtherefore does not need to be acknowledged).Depending upon the advertisement's LS type, the advertisement can beflooded out only certain interfaces.  These interfaces, defined by thefollowing, are called the eligible interfaces:AS external links (LS Type = 5)    AS external links are flooded throughout the entire AS, with the    exception of stub areas (seeSection 3.6).  The eligible interfaces    are all the router's interfaces, excluding virtual links and those    interfaces attaching to stub areas.All other types    All other types are specific to a single area (Area A).  The    eligible interfaces are all those interfaces attaching to the Area    A.  If Area A is the backbone, this includes all the virtual links.[Moy]                                                         [Page 107]

RFC 1247                     OSPF Version 2                    July 1991Link state databases must remain synchronized over all adjacenciesassociated with the above eligible interfaces.  This is accomplished byexecuting the following steps on each eligible interface.  It should benoted that this procedure may decide not to flood a link stateadvertisement out a particular interface, if there is a high probabilitythat the attached neighbors have already received the advertisement.However, in these cases the flooding procedure must be absolutely surethat the neighbors eventually do receive the advertisement, so theadvertisement is still added to each adjacency's Link stateretransmission list.  For each eligible interface:(1) Each of the neighbors attached to this interface are examined, to    determine whether they must receive the new advertisement.  The    following steps are executed for each neighbor:    (a) If the neighbor is in a lesser state than Exchange, it does not        participate in flooding, and the next neighbor should be        examined.    (b) Else, if the adjacency is not yet full (neighbor state is        Exchange or Loading), examine the Link state request list        associated with this adjacency.  If there is an instance of the        new advertisement on the list, it indicates that the neighboring        router has an instance of the advertisement already.  Compare        the new advertisement to the neighbor's copy:        o   If the new advertisement is less recent, then try the next            neighbor.        o   If the two copies are the same instance, then delete the            advertisement from the Link state request list, and try the            next neighbor.[16]        o   Else, the new advertisement is more recent.  Delete the            advertisement from the Link state request list.    (c) If the new advertisement was received from this neighbor, try        the next neighbor.    (d) At this point we are not positive that the new neighbor has an        up-to-date instance of this new advertisement.  Add the new        advertisement to the Link state retransmission list for the        adjacency.  This ensures that the flooding procedure is        reliable; the advertisement will be retransmitted at intervals        until an acknowledgment is seen from the neighbor.[Moy]                                                         [Page 108]

RFC 1247                     OSPF Version 2                    July 1991(2) The router must now decide whether to flood the new link state    advertisement out this interface.  If in the previous step, the link    state advertisement was NOT added to any of the Link state    retransmission lists, there is no need to flood the advertisement    and the next interface should be examined.(3) If the new advertisement was received on this interface, and it was    received from either the Designated Router or the Backup Designated    Router, chances are all the neighbors have received the    advertisement already.  Therefore, examine the next interface.(4) If the new advertisement was received on this interface, and the    interface state is Backup (i.e., the router itself is the Backup    Designated Router), examine the next interface.  The Designated    Router will do the flooding on this interface.  If the Designated    Router fails, this router will end up retransmitting the updates.(5) If this step is reached, the advertisement must be flooded out the    interface.  Send a Link State Update packet (with the new    advertisement as contents) out the interface.  The advertisement's    LS age must be incremented by InfTransDelay (which must be > 0) when    copied into the outgoing packet (until the LS age field reaches its    maximum value of MaxAge).    On broadcast networks, the Link State Update packets are multicast.    The destination IP address specified for the Link State Update    Packet depends on the state of the interface.  If the interface    state is DR or Backup, the address AllSPFRouters should be used.    Otherwise, the address AllDRouters should be used.    On non-broadcast, multi-access networks, separate Link State Update    packets must be sent, as unicasts, to each adjacent neighbor (i.e.,    those in state Exchange or greater).  The destination IP addresses    for these packets are the neighbors' IP addresses.13.4 Receiving self-originated link stateIt is a common occurrence to receive a self-originated link stateadvertisement via the flooding procedure.  If the advertisement receivedis a newer instance than the last instance that the router actuallyoriginated, the router must take special action.The reception of such an advertisement indicates that there are linkstate advertisements in the routing domain that were originated beforethe last time the router was restarted.  In this case, the router mustadvance the sequence number for the advertisement one past the receivedsequence number, and originate a new instance of the advertisement.[Moy]                                                         [Page 109]

RFC 1247                     OSPF Version 2                    July 1991Note also that if the type of the advertisement is Summary link or ASexternal link, the router may no longer have an (advertisable) route tothe destination.  In this case, the advertisement should be flushed fromthe routing domain by incrementing the advertisement's LS age to MaxAgeand reflooding (seeSection 14.1).13.5 Sending Link State Acknowledgment packetsEach newly received link state advertisement must be acknowledged.  Thisis usually done by sending Link State Acknowledgment packets.  However,acknowledgments can also be accomplished implicitly by sending LinkState Update packets (see step 7a ofSection 13).Many acknowledgments may be grouped together into a single Link StateAcknowledgment packet.  Such a packet is sent back out the interfacethat has received the advertisements.  The packet can be sent in one oftwo ways: delayed and sent on an interval timer, or sent directly (as aunicast) to a particular neighbor.  The particular acknowledgmentstrategy used depends on the circumstances surrounding the receipt ofthe advertisement.Sending delayed acknowledgments accomplishes several things: itfacilitates the packaging of multiple acknowledgments in a singlepacket; it enables a single packet to indicate acknowledgments toseveral neighbors at once (through multicasting); and it randomizes theacknowledgment packets sent by the various routers attached to a multi-access network.  The fixed interval between a router's delayedtransmissions must be short (less than RxmtInterval) or needlessretransmissions will ensue.Direct acknowledgments are sent to a particular neighbor in response tothe receipt of duplicate link state advertisements.  Theseacknowledgments are sent as unicasts, and are sent immediately when theduplicate is received.The precise procedure for sending Link State Acknowledgment packets isdescribed in Table 19.  The circumstances surrounding the receipt of theadvertisement are listed in the left column.  The acknowledgment actionthen taken is listed in one of the two right columns.  This actiondepends on the state of the concerned interface; interfaces in stateBackup behave differently from interfaces in all other states.                                     Action taken in state     Circumstances          Backup               All other states     ______________________________________________________________[Moy]                                                         [Page 110]

RFC 1247                     OSPF Version 2                    July 1991                                     Action taken in state     Circumstances          Backup               All other states     ______________________________________________________________Advertisement  has     No  acknowledgment   No  acknowledgmentbeen  flooded back     sent.                sent.out receiving  in-terface  (see Sec-tion 13, step 5b).______________________________________________________________Advertisement   is     Delayed       ack-   Delayed       ack-more  recent  than     nowledgment   sent   nowledgment sent.database copy, but     if   advertisementwas   not  flooded     received  from DR,back out receiving     otherwise do noth-interface              ing______________________________________________________________Advertisement is a     Delayed       ack-   No  acknowledgmentduplicate, and was     nowledgment   sent   sent.treated as an  im-     if   advertisementplied  acknowledg-     received  from DR,ment (see  Section     otherwise do noth-13, step 7a).          ing______________________________________________________________Advertisement is a     Direct acknowledg-   Direct acknowledg-duplicate, and was     ment sent.           ment sent.not treated as  animplied       ack-nowledgment.______________________________________________________________Advertisement's age    Direct acknowledg-   Direct acknowledg-is equal to MaxAge,    ment sent.           ment sent.and there is nocurrent instance ofthe advertisement inthe link statedatabase (seeSection 13, step 4).             Table 19: Sending link state acknowledgements.Delayed acknowledgments must be delivered to all adjacent routersassociated with the interface.  On broadcast networks, this isaccomplished by sending the delayed Link State Acknowledgment packets asmulticasts.  The Destination IP address used depends on the state of theinterface.  If the state is DR or Backup, the destination AllSPFRoutersis used.  In other states, the destination AllDRouters is used.  Onnon-broadcast networks, delayed acks must be unicast separately over[Moy]                                                         [Page 111]

RFC 1247                     OSPF Version 2                    July 1991each adjacency (neighbor whose state is >= Exchange).The reasoning behind sending the above packets as multicasts is bestexplained by an example.  Consider the network configuration depicted inFigure 15.  Suppose RT4 has been elected as DR, and RT3 as Backup forthe network N3.  When router RT4 floods a new advertisement to networkN3, it is received by routers RT1, RT2, and RT3.  These routers will notflood the advertisement back onto net N3, but they still must ensurethat their topological databases remain synchronized with their adjacentneighbors.  So RT1, RT2, and RT4 are waiting to see an acknowledgmentfrom RT3.  Likewise, RT4 and RT3 are both waiting to see acknowledgmentsfrom RT1 and RT2.  This is best achieved by sending the acknowledgmentsas multicasts.The reason that the acknowledgment logic for Backup DRs is slightlydifferent is because they perform differently during the flooding oflink state advertisements (seeSection 13.3, step 4).13.6 Retransmitting link state advertisementsAdvertisements flooded out an adjacency are placed on the adjacency'sLink state retransmission list.  In order to ensure that flooding isreliable, these advertisements are retransmitted until they areacknowledged.  The length of time between retransmissions is aconfigurable per-interface value, RxmtInterval.  If this is set too lowfor an interface, needless retransmissions will ensue.  If the value isset too high, the speed of the flooding, in the face of lost packets,may be affected.Several retransmitted advertisements may fit into a single Link StateUpdate packet.  When advertisements are to be retransmitted, only thenumber fitting in a single Link State Update packet should betransmitted.  Another packet of retransmissions can be sent when some ofthe advertisements are acknowledged, or on the next firing of theretransmission timer.Link State Update Packets carrying retransmissions are always sent asunicasts (directly to the physical address of the neighbor).  They arenever sent as multicasts.  Each advertisement's LS age must beincremented by InfTransDelay (which must be > 0) when copied into theoutgoing packet (until the LS age field reaches its maximum value ofMaxAge).If the adjacent router goes down, retransmissions may occur until theadjacency is destroyed by OSPF's Hello Protocol.  When the adjacency isdestroyed, the Link state retransmission list is cleared.[Moy]                                                         [Page 112]

RFC 1247                     OSPF Version 2                    July 199113.7 Receiving link state acknowledgmentsMany consistency checks have been made on a received Link StateAcknowledgment packet before it is handed to the flooding procedure.  Inparticular, it has been associated with a particular neighbor.  If thisneighbor is in a lesser state than Exchange, the packet is discarded.Otherwise, for each acknowledgment in the packet, the following stepsare performed:o   Does the advertisement acknowledged have an instance on the Link    state retransmission list for the neighbor?  If not, examine the    next acknowledgment.  Otherwise:o   If the acknowledgment is for the same instance that is contained on    the list, remove the item from the list and examine the next    acknowledgment.  Otherwise:o   Log the questionable acknowledgment, and examine the next one.14. Aging The Link State DatabaseEach link state advertisement has an age field.  The age is expressed inseconds.  An advertisement's age field is incremented while it iscontained in a router's database.  Also, when copied into a Link StateUpdate Packet for flooding out a particular interface, theadvertisement's age is incremented by InfTransDelay.An advertisement's age is never incremented past the value MaxAge.Advertisements having age MaxAge are not used in the routing tablecalculation.  As a router ages its link state database, anadvertisement's age may reach MaxAge.[17] At this time, the router mustattempt to flush the advertisement from the routing domain.  This isdone simply by reflooding the MaxAge advertisement just as if it was anewly originated advertisement (seeSection 13.3).When a Database summary list for a newly adjacent neighbor is formed,any MaxAge advertisements present in the link state database are addedto the neighbor's Link state retransmission list instead of theneighbor's Database summary list.  SeeSection 10.3 for more details.A MaxAge advertisement is removed entirely from the router's link statedatabase when a) it is no longer contained on any neighbor Link stateretransmission lists and b) none of the router's neighbors are in statesExchange or Loading.[Moy]                                                         [Page 113]

RFC 1247                     OSPF Version 2                    July 1991When, in the process of aging the link state database, anadvertisement's age hits a multiple of CheckAge, its checksum should beverified.  If the checksum is incorrect, a program or memory error hasbeen detected, and at the very least the router itself should berestarted.14.1 Premature aging of advertisementsA link state advertisement can be flushed from the routing domain bysetting its age to MaxAge and reflooding the advertisement.  Thisprocedure follows the same course as flushing an advertisement whose agehas naturally reached the value MaxAge (seeSection 14).  In particular,the MaxAge advertisement is removed from the router's link statedatabase as soon as a) it is no longer contained on any neighbor Linkstate retransmission lists and b) none of the router's neighbors are instates Exchange or Loading.  We call the setting of an advertisement'sage to MaxAge premature aging.Premature aging is used when it is time for a self-originatedadvertisement's sequence number field to wrap.  At this point, thecurrent advertisement instance (having LS sequence number of 0x7fffffff)must be prematurely aged and flushed from the routing domain before anew instance with sequence number 0x80000001 can be originated.  SeeSection 12.1.6 for more information.Premature aging can also be used when, for example, one of the router'spreviously advertised external routes is no longer reachable.  In thiscircumstance, the router can flush its external advertisement from therouting domain via premature aging.  This procedure is preferable to thealternative, which is to originate a new advertisement for thedestination specifying a metric of LSInfinity.A router may only prematurely age its own (self-originated) link stateadvertisements.  These are the link state advertisements having therouter's own OSPF Router ID in the Advertising Router field.15. Virtual LinksThe single backbone area (Area ID = 0) cannot be disconnected, or someareas of the Autonomous System will become unreachable.  Toestablish/maintain connectivity of the backbone, virtual links can beconfigured through non-backbone areas.  Virtual links serve to connectseparate components of the backbone.  The two endpoints of a virtuallink are area border routers.  The virtual link must be configured inboth routers.  The configuration information in each router consists ofthe other virtual endpoint (the other area border router), and the non-[Moy]                                                         [Page 114]

RFC 1247                     OSPF Version 2                    July 1991backbone area the two routers have in common (called the transit area).Virtual links cannot be configured through stub areas (seeSection 3.6).The virtual link is treated as if it were an unnumbered point-to-pointnetwork (belonging to the backbone) joining the two area border routers.An attempt is made to establish an adjacency over the virtual link.When this adjacency is established, the virtual link will be included inbackbone router links advertisements, and OSPF packets pertaining to thebackbone area will flow over the adjacency.  Such an adjacency has beenreferred to as a "virtual adjacency".In each endpoint router, the cost and viability of the virtual link isdiscovered by examining the routing table entry for the other endpointrouter.  (The entry's associated area must be the configured transitarea).  Actually, there may be a separate routing table entry for eachType of Service.  These are called the virtual link's correspondingrouting table entries.  The Interface Up event occurs for a virtual linkwhen its corresponding TOS 0 routing table entry becomes reachable.Conversely, the Interface Down event occurs when its TOS 0 routing tableentry becomes unreachable.[18] In other words, the virtual link'sviability is determined by the existence of an intra-area path, throughthe transit area, between the two endpoints.  The other detailsconcerning virtual links are as follows:o   AS external links are NEVER flooded over virtual adjacencies.  This    would be duplication of effort, since the same AS external links are    already flooded throughout the virtual link's transit area.  For    this same reason, AS external link advertisements are not summarized    over virtual adjacencies during the database exchange process.o   The cost of a virtual link is NOT configured.  It is defined to be    the cost of the intra-area path between the two defining area border    routers.  This cost appears in the virtual link's corresponding    routing table entry.  When the cost of a virtual link changes, a new    router links advertisement should be originated for the backbone    area.o   Just as the virtual link's cost and viability are determined by the    routing table build process (through construction of the routing    table entry for the other endpoint), so are the IP interface address    for the virtual interface and the virtual neighbor's IP address.    These are used when sending protocol packets over the virtual link.o   In each endpoint's router links advertisement for the backbone, the    virtual link is represented as a link having link type 4, Link ID    set to the virtual neighbor's OSPF Router ID and Link Data set to    the virtual interface's IP address.  SeeSection 12.4.1 for more    information.  Also, it may be the case that there is a TOS 0 path,[Moy]                                                         [Page 115]

RFC 1247                     OSPF Version 2                    July 1991    but no non-zero TOS paths to the other endpoint router.  In this    case, non-zero TOS costs must be set to LSInfinity in the router    links advertisement.o   When virtual links are configured for the backbone, information    concerning backbone networks should not be condensed before being    summarized for the transit areas.  In other words, each backbone    network should be advertised in a separate summary link    advertisement, regardless of the backbone's configured area address    ranges.  SeeSection 12.4.3 for more information.o   The time between link state retransmissions, RxmtInterval, is    configured for a virtual link.  This should be well over the    expected round-trip delay between the two routers.  This may be hard    to estimate for a virtual link.  It is better to err on the side of    making it too large.16. Calculation Of The Routing TableThis section details the OSPF routing table calculation.  Using itsattached areas' link state databases as input, a router runs thefollowing algorithm, building its routing table step by step.  At eachstep, the router must access individual pieces of the link statedatabases (e.g., a router links advertisement originated by a certainrouter).  This access is performed by the lookup function discussed inSection 12.2.  The lookup process may return a link state advertisementwhose LS age is equal to MaxAge.  Such an advertisement should not beused in the routing table calculation, and is treated just as if thelookup process had failed.The OSPF routing table's organization is explained inSection 11.  Twoexamples of the routing table build process are presented in Sections11.2 and 11.3.This process can be broken into the following steps:(1) The present routing table is invalidated.  The routing table is    built again from scratch.  The old routing table is saved so that    changes in routing table entries can be identified.(2) The intra-area routes are calculated by building the shortest path    tree for each attached area.  In particular, all routing table    entries whose Destination type is "area border router" are    calculated in this step.  This step is described in two parts.  At    first the tree is constructed by only considering those links    between routers and transit networks.  Then the stub networks are    incorporated into the tree.[Moy]                                                         [Page 116]

RFC 1247                     OSPF Version 2                    July 1991(3) The inter-area routes are calculated, through examination of summary    link advertisements.  If the router is attached to multiple areas    (i.e., it is an area border router), only backbone summary link    advertisements are examined.(4) For those routing entries whose next hop is over a virtual link, a    real (physical) next hop is calculated.  The real next hop will be    on one of the router's directly attached networks.  This step only    concerns routers having configured virtual links.(5) Routes to external destinations are calculated, through examination    of AS external link advertisements.  The location of the AS boundary    routers (which originate the AS external link advertisements) has    been determined in steps 2-4.Steps 2-5 are explained in further detail below.  The explanationsdescribe the calculations for TOS 0 only.  It may also be necessary toperform each step (separately) for each of the non-zero TOS values.[19]For more information concerning the building of non-zero TOS routes seeSection 16.9.Changes made to routing table entries as a result of these calculationscan cause the OSPF protocol to take further actions.  For example, achange to an intra-area route will cause an area border router tooriginate new summary link advertisements (seeSection 12.4).  SeeSection 16.7 for a complete list of the OSPF protocol actions resultingfrom routing table table changes.16.1 Calculating the shortest-path tree for an areaThis calculation yields the set of intra-area routes associated with anarea (called hereafter Area A).  A router calculates the shortest-pathtree using itself as the root.[20] The formation of the shortest pathtree is done here in two stages.  In the first stage, only links betweenrouters and transit networks are considered.  Using the Dijkstraalgorithm, a tree is formed from this subset of the link state database.In the second stage, leaves are added to the tree by considering thelinks to stub networks.The procedure will be explained using the graph terminology that wasintroduced inSection 2.  The area's link state database is representedas a directed graph.  The graph's vertices are routers, transit networksand stub networks.  The first stage of the procedure concerns only thetransit vertices (routers and transit networks) and their connectinglinks.  Throughout the shortest path calculation, the following data isalso associated with each transit vertex:[Moy]                                                         [Page 117]

RFC 1247                     OSPF Version 2                    July 1991Vertex (node) ID    A 32-bit number uniquely identifying the vertex.  For router    vertices this is the OSPF Router ID.  For network vertices, this is    the IP address of the network's Designated Router.A link state advertisement    Each transit vertex has an associated link state advertisement.  For    router vertices, this is a router links advertisement.  For transit    networks, this is a network links advertisement (which is actually    originated by the network's Designated Router).  In any case, the    advertisement's Link State ID is always equal to the above Vertex    ID.List of next hops    The list of next hops for the current shortest paths from the root    to this vertex.  There can be multiple shortest paths due to the    equal-cost multipath capability.  Each next hop indicates the    outgoing router interface to use when forwarding traffic to the    destination.  On multi-access networks, the next hop also includes    the IP address of the next router (if any) in the path towards the    destination.Distance from root    The link state cost of the current shortest path(s) from the root to    the vertex.  The link state cost of a path is calculated as the sum    of the costs of the path's constituent links (as advertised in    router links and network links advertisements).  One path is said to    be "shorter" than another if it has a smaller link state cost.The first stage of the procedure can now be summarized as follows.  Ateach iteration of the algorithm, there is a list of candidate vertices.The shortest paths from the root to these vertices have not(necessarily) been found.  The candidate vertex closest to the root isadded to the shortest-path tree, removed from the candidate list, andits adjacent vertices are examined for possible addition to/modificationof the candidate list.  The algorithm then iterates again.  Itterminates when the candidate list becomes empty.The following steps describe the first stage in detail.  Remember thatwe are computing the shortest path tree for Area A.  All references tolink state database lookup below are from Area A's database.(1) Initialize the algorithm's data structures.  Clear the list of    candidate vertices.  Initialize the shortest-path tree to only the    root (which is the router doing the calculation).[Moy]                                                         [Page 118]

RFC 1247                     OSPF Version 2                    July 1991(2) Call the vertex just added to the tree vertex V.  Examine the link    state advertisement associated with vertex V.  This is a lookup in    the area link state database based on the Vertex ID.  Each link    described by the advertisement gives the cost to an adjacent vertex.    For each described link, (say it joins vertex V to vertex W):    (a) If this is a link to a stub network, examine the next link in        V's advertisement.  Links to stub networks will be considered in        the second stage of the shortest path calculation.    (b) Otherwise, W is a transit vertex (router or transit network).        Look up the vertex W's link state advertisement (router links or        network links) in Area A's link state database.  If the        advertisement does not exist, or its age is equal to MaxAge, or        it does not have a link back to vertex V, examine the next link        in V's advertisement.  Both ends of a link must advertise the        link before it will be used for data traffic.[21]    (c) If vertex W is already on the shortest-path tree, examine the        next link in the advertisement.    (d) If the cost of the link (from V to W) is LSInfinity, the link        should not be used for data traffic.  In this case, examine the        next link in the advertisement.    (e) Calculate the link state cost D of the resulting path from the        root to vertex W.  D is equal to the sum of the link state cost        of the (already calculated) shortest path to vertex V and the        advertised cost of the link between vertices V and W.  If D is:        o   Greater than the value that already appears for vertex W on            the candidate list, then examine the next link.        o   Equal to the value that appears for vertex W on the the            candidate list, calculate the set of next hops that result            from using the advertised link.  Input to this calculation            is the destination (W), and its parent (V).  This            calculation is shown inSection 16.1.1.  This set of hops            should be added to the next hop values that appear for W on            the candidate list.        o   Less than the value that appears for vertex W on the the            candidate list, or if W does not yet appear on the candidate            list, then set the entry for W on the candidate list to            indicate a distance of D from the root.  Also calculate the            list of next hops that result from using the advertised            link, setting the next hop values for W accordingly.  The            next hop calculation is described inSection 16.1.1; it[Moy]                                                         [Page 119]

RFC 1247                     OSPF Version 2                    July 1991            takes as input the destination (W) and its parent (V).(3) If at this step the candidate list is empty, the shortest-path tree    (of transit vertices) has been completely built and this stage of    the algorithm terminates.  Otherwise, choose the vertex belonging to    the candidate list that is closest to the root, and add it to the    shortest-path tree (removing it from the candidate list in the    process).(4) Possibly modify the routing table.  For those routing table entries    modified, the associated area will be set to Area A, the path type    will be set to intra-area, and the cost will be set to the newly    discovered shortest path's calculated distance.    If the newly added vertex is an area border router, a routing table    entry is added whose destination type is "area border router".  The    Options field found in the associated router links advertisement is    copied into the routing table entry's Optional capabilities field.    If the newly added vertex is an AS boundary router, the routing    table entry of type "AS boundary router" for the destination is    located.  Since routers can belong to more than one area, it is    possible that several sets of intra-area paths exist to the AS    boundary router, each set using a different area.  However, the AS    boundary router's routing table entry must indicate a set of paths    which utilize a single area.  The area leading to the routing table    entry is selected as follows: A set of intra-area paths having no    virtual next hops is always preferred over a set of intra-area paths    in which some virtual next hops appear[22] ; all other things being    equal the set of paths having lower cost is preferred.  Note that    whenever an AS boundary router's routing table entry is    added/modified, the Options found in the associated router links    advertisement is copied into the routing table entry's Optional    capabilities field.    If the newly added vertex is a transit network, the routing table    entry for the network is located.  The entry's destination ID is the    IP network number, which can be obtained by masking the Vertex ID    (Link State ID) with its associated subnet mask (found in the    associated network links advertisement).  If the routing table entry    already exists (i.e., there is already an intra-area route to the    destination installed in the routing table), multiple vertices have    mapped to the same IP network.  For example, this can occur when a    new Designated Router is being established.  In this case, the    current routing table entry should be overwritten if and only if the    newly found path is just as short and the current routing table    entry's Link State Origin has a smaller Link State ID than the newly    added vertex' link state advertisement.[Moy]                                                         [Page 120]

RFC 1247                     OSPF Version 2                    July 1991    If there is no routing table entry for the network (the usual case),    a routing table entry for the IP network should be added.  The    routing table entry's Link State origin should be set to the newly    added vertex' link state advertisement.(5) Iterate the algorithm by returning to Step 2.The stub networks are added to the tree in the procedure's second stage.In this stage, all router vertices are again examined.  Those that havebeen determined to be unreachable in the above first phase arediscarded.  For each reachable router vertex (call it V), the associatedrouter links advertisement is found in the link state database.  Eachstub network link appearing in the advertisement is then examined, andthe following steps are executed:(1) If the cost of the stub network link is LSInfinity, the link should    not be used for data traffic.  In this case, go on to examine the    next stub network link in the advertisement.(2) Otherwise, Calculate the distance D of stub network from the root.    D is equal to the distance from the root to the router vertex    (calculated in stage 1), plus the stub network link's advertised    cost.  Compare this distance to the current best cost to the stub    network.  This is done by looking up the network's current routing    table entry.  If the calculated distance D is larger, go on to    examine the next stub network link in the advertisement.(3) If this step is reached, the stub network's routing table entry must    be updated.  Calculate the set of next hops that would result from    using the stub network link.  This calculation is shown inSection16.1.1; input to this calculation is the destination (the stub    network) and the parent vertex (the router vertex).  If the distance    D is the same as the current routing table cost, simply add this set    of next hops to the routing table entry's list of next hops.  In    this case, the routing table already has a Link State origin.  If    this Link State origin is a router links advertisement whose Link    State ID is smaller than V's Router ID, reset the Link State origin    to V's router links advertisement.    Otherwise D is smaller than the routing table cost.  Overwrite the    current routing table entry by setting the routing table entry's    cost to D, and by setting the entry's list of next hops to the newly    calculated set.  Set the routing table entry's Link State origin to    V's router links advertisement.  Then go on to examine the next stub    network link.[Moy]                                                         [Page 121]

RFC 1247                     OSPF Version 2                    July 1991For all routing table entries added/modified in the second stage, theassociated area will be set to Area A and the path type will be set tointra-area.  When the list of reachable router links is exhausted, thesecond stage is completed.  At this time, all intra-area routesassociated with Area A have been determined.The specification does not require that the above two stage method beused to calculate the shortest path tree.  However, if another algorithmis used, an identical tree must be produced.  For this reason, it isimportant to note that links between transit vertices must bebidirectional in ordered to be included in the above tree.  It shouldalso be mentioned that algorithms exist for incrementally updating theshortest-path tree (see [BBN]).16.1.1 The next hop calculationThis section explains how to calculate the current set of next hops touse for a destination.  Each next hop consists of the outgoing interfaceto use in forwarding packets to the destination together with the nexthop router (if any).  The next hop calculation is invoked each time ashorter path to the destination is discovered.  This can happen ineither stage of the shortest-path tree calculation (seeSection 16.1).In stage 1 of the shortest-path tree calculation a shorter path is foundas the destination is added to the candidate list, or when thedestination's entry on the candidate list is modified (Step 2e of Stage1).  In stage 2 a shorter path is discovered each time the destination'srouting table entry is modified (Step 3 of Stage 2).The set of next hops to use for the destination may be recalculatedseveral times during the shortest-path tree calculation, as shorter andshorter paths are discovered.  In the end, the destination's routingtable entry will always reflect the next hops resulting from theabsolute shortest path(s).Input to the next hop calculation is a) the destination and b) itsparent in the current shortest path between the root (the calculatingrouter) and the destination.  The parent is always a transit vertex(i.e., always a router or a transit network).If there is at least one intervening router in the current shortest pathbetween the destination and the root, the destination simply inheritsthe set of next hops from the parent.  Otherwise, there are two cases.In the first case, the parent vertex is the root (the calculating routeritself).  This means that the destination is either a directly connectednetwork or directly connected router.  The next hop in this case issimply the OSPF interface connecting to the network/router; no next hoprouter is required.[Moy]                                                         [Page 122]

RFC 1247                     OSPF Version 2                    July 1991In the second case, the destination is a router, and its parent vertexis a network.  The list of next hops is then determined by examining thedestination's router links advertisement.  For each link in theadvertisement that points back to the parent network, the link's LinkData field provides the IP address of a next hop router.  The outgoinginterface to use can then be derived from the next hop IP address (or itcan be inherited from the parent network).16.2 Calculating the inter-area routesThe inter-area routes are calculated by examining summary linkadvertisements.  If the router has active attachments to multiple areas,only backbone summary link advertisements are examined.  Routersattached to a single area examine that area's summary links.  In eithercase, the summary links examined below are all part of a single area'slink state database (call it Area A).Summary link advertisements are originated by the area border routers.Each summary link advertisement in Area A is considered in turn.Remember that the destination described by a summary link advertisementis either a network (type 3 summary link advertisements) or an ASboundary router (type 4 summary link advertisements).  For each summarylink advertisement:(1) If the cost specified by the advertisement is LSInfinity, then    examine the next advertisement.(2) If the advertisement was originated by the calculating router    itself, examine the next advertisement.(3) If the collection of destinations described by the summary link    falls into one of the router's configured area address ranges (seeSection 3.5) and the particular area address range is active, the    summary link should be ignored.  Active means that there are one or    more reachable (by intra-area paths) networks contained in the area    range.  In this case, all addresses in the area range are assumed to    be either reachable via intra-area paths, or else to be unreachable    by any other means.(4) Else, call the destination described by the advertisement N, and the    area border originating the advertisement BR.  Look up the routing    table entry for BR having A as its associated area.  If no such    entry exists for router BR (i.e., BR is unreachable in Area A), do    nothing with this advertisement and consider the next in the list.    Else, this advertisement describes an inter-area path to destination    N, whose cost is the distance to BR plus the cost specified in the[Moy]                                                         [Page 123]

RFC 1247                     OSPF Version 2                    July 1991    advertisement.  Call the cost of this inter-area path IAC.(5) Next, look up the routing table entry for the destination N.  (The    entry's Destination type is either Network or AS boundary router.)    If no entry exists for N or if the entry's path type is "AS    external", install the inter-area path to N, with associated area A,    cost IAC, next hop equal to the list of next hops to router BR, and    advertising router equal to BR.(6) Else, if the paths present in the table are intra-area paths, do    nothing with the advertisement (intra-area paths are always    preferred).(7) Else, the paths present in the routing table are also inter-area    paths.  Install the new path through BR if it is cheaper, overriding    the paths in the routing table.  Otherwise, if the new path is the    same cost, add it to the list of paths that appear in the routing    table entry.16.3 Resolving virtual next hopsThis step is only necessary in area-border routers having configuredvirtual links.  In these routers, some of the routing table entries mayhave virtual next hops.  That is, one or more of the next hops installedin Sections16.1 and16.2 may be over a virtual link.  However, whenforwarding data traffic to a destination, the next hops must always beon a directly attached network.In this section, each virtual next hop is replaced by a real next hop.In the process a new routing table distance is calculated that may besmaller than the previously calculated distance.  In this case, the listof next hops is pruned so that only those giving rise to the newshortest distance are included, and the routing table entry's distanceis updated accordingly.                 ______________________________________                 (Figure not included in text version.)                 Figure 17: Resolving virtual next hops                 ______________________________________[Moy]                                                         [Page 124]

RFC 1247                     OSPF Version 2                    July 1991This resolution of virtual next hops is done only for Destination typesNetwork or AS Boundary router.  Suppose that one of a routing tableentry's next hops is a virtual link.  This is determined by thefollowing combination: the routing table entry's path type is eitherintra-area or inter-area, the area associated with the routing tableentry must be the backbone, yet the next hop belongs to a different area(the virtual link's transit area).Let N be the above entry's destination, and A the virtual link's transitarea.  The real next hop (and new distance) is calculated as follows.Let D be a distance counter, and set the real next hop NH to null.Then, look up all the summary link advertisements for N in area A'sdatabase, performing the following steps for each advertisement:[23](1) Call the border router that originated the advertisement BR.  If    there is no routing table entry for BR having A as associated area    (i.e., BR is unreachable through Area A), examine the next    advertisement.(2) Else, let X be the distance to BR via Area A.  If the cost    advertised by BR (call it Y) to the destination is LSInfinity,    examine the next summary link advertisement.  Else, the cost to    destination N through area border router BR is X+Y.(3) If next hop NH is null or X+Y is smaller is smaller than D, set D to    X+Y and set the next hop NH to the next hop specified in router BR's    routing table entry.At this point, the real next hop NH should be set, and the distance Dcalculated should be less than or equal to the cost originally specifiedin destination N's routing table entry.  This same calculation should bedone for all of N's virtual next hops, and then N's new cost set to theminimum calculated distance, with the its new set of next hops thatcombination of non-virtual and recalculated next hops that correspond tothis (possibly same as original) distance.The resolving of virtual next hops may produce unexpected results.After the virtual next hops are resolved, traffic that was originallyscheduled to go over the virtual link may instead take a different paththrough the virtual link's transit area.  In other words, virtual linksallow transit traffic to be forwarded through an area, but do notdictate the precise path that the traffic will take.As an example, consider the Autonomous System pictured in Figure 17.There is a single non-backbone area (Area 1) that physically divides thebackbone into two separate pieces.  To maintain connectivity of the[Moy]                                                         [Page 125]

RFC 1247                     OSPF Version 2                    July 1991backbone, a virtual link has been configured between routers RT1 andRT4.  On the right side of the figure, network N1 belongs to thebackbone.  The dotted lines indicate that there is a much shorterintra-area backbone path between router RT5 and network N1 (cost 20)than there is between router RT4 and network N1 (cost 100).  Both routerRT4 and router RT5 will inject summary link advertisements for networkN1 into Area 1.After the shortest-path tree has been calculated for the backbone,router RT1 (one end of the virtual link) will have selected router RT4as the virtual next hop for all data traffic destined for network N1.However, since router RT5 is so much closer to network N1, all routersinternal to Area 1 (e.g., routers RT2 and RT3) will forward theirnetwork N1 traffic towards router RT5, instead of RT4.  And indeed,after resolving the virtual next hop by the above calculation, routerRT1 will also forward network N1 traffic towards RT5.  So, in thisexample the virtual link enables network N1 traffic to be forwardedthrough the transit Area 1, but the actual path the data traffic takesdoes not follow the virtual link.16.4 Calculating AS external routesAS external routes are calculated by examining AS external linkadvertisements.  Each of the AS external link advertisements isconsidered in turn.  Most AS external advertisements describe routes tospecific IP destinations.  An AS external advertisement can alsodescribe a default route for the Autonomous System (destination =DefaultDestination).  For each AS external link advertisement:(1) If the cost specified by the advertisement is LSInfinity, then    examine the next advertisement.(2) If the advertisement was originated by the calculating router    itself, examine the next advertisement.(3) Call the destination described by the advertisement N.  Look up the    routing table entry for the AS boundary router (ASBR) that    originated the advertisement.  If no entry exists for router ASBR    (i.e., ASBR is unreachable), do nothing with this advertisement and    consider the next in the list.    Else, this advertisement describes an AS external path to    destination N.  Examine the forwarding address specified in the    external advertisement.  This indicates the IP address to which    packets for the destination should be forwarded.  If forwarding    address is set to 0.0.0.0, packets should be sent to the ASBR[Moy]                                                         [Page 126]

RFC 1247                     OSPF Version 2                    July 1991    itself.  Otherwise, look up the forwarding address in the routing    table.[24] An intra-area or inter-area path must exist to the    forwarding address.  If no such path exists, do nothing with the    advertisement and consider the next in the list.    Call the routing table distance to the forwarding address X (when    the forwarding address is set to 0.0.0.0, this is the distance to    the ASBR itself), and the cost specified in the advertisement Y.  X    is in terms of the link state metric, and Y is a Type 1 or 2    external metric.(4) Next, look up the routing table entry for the destination N.  If no    entry exists for N, install the AS external path to N, with next hop    equal to the list of next hops to the forwarding address, and    advertising router equal to ASBR.  If the external metric type is 1,    then the path-type is set to type 1 external and the cost is equal    to X+Y.  If the external metric type is 2, the the path-type is set    to type 2 external, the link state component of the route's cost is    X, and the Type 2 cost is Y.(5) Else, if the paths present in the table are not type 1 or type 2    external paths, do nothing (AS external paths have the lowest    priority).(6) Otherwise, compare the cost of this new AS external path to the ones    present in the table.  Type 1 external paths are always shorter than    Type 2 external paths.  Type 1 external paths are compared by    looking at the sum of the distance to the forwarding address and the    advertised Type 1 metric (X+Y).  Type 2 external paths are compared    by looking at the advertised Type 2 metrics, and then if necessary,    the distance to the forwarding addresses.    If the new path is shorter, it replaces the present paths in the    routing table entry.  If the new path is the same cost, it is added    to the routing table entry's list of paths.16.5 Incremental updates --- summary linksWhen a new summary link advertisement is received, it is not necessaryto recalculate the entire routing table.  Call the destination describedby the summary link advertisement N, and let A be the area to which theadvertisement belongs.Look up the routing table entry for N.  If the next hop to N is avirtual link through Area A (this means that the entry's associated areais the backbone, and the listed next hop does not belong to thebackbone, but instead belongs to Area A), the real next hop must again[Moy]                                                         [Page 127]

RFC 1247                     OSPF Version 2                    July 1991be resolved.  This means running the algorithm inSection 16.3 fordestination N only.Else, if there is an intra-area route to destination N nothing need bedone (intra-area routes always take precedence).  Otherwise, if Area Ais the router's sole attached area, or Area A is the backbone, theprocedure inSection 16.2 will have to be performed, but only for thosesummary link advertisements whose destination is N.  Before thisprocedure is performed, the present routing table entry for N should beinvalidated (but kept for comparison purposes).  If this procedure leadsto a virtual next hop, the algorithm inSection 16.3 will again have tobe performed in order to calculate the real next hop.If N's routing table entry changes, and N is an AS boundary router, theAS external links will have to be reexamined (Section 16.4).16.6 Incremental updates --- AS external linksWhen a new AS external link advertisement is received, it is notnecessary to recalculate the entire routing table.  Call the destinationdescribed by the AS external link advertisement N.  If there is alreadyan intra-area or inter-area route to the destination, no recalculationis necessary (these routes take precedence).Otherwise, the procedure inSection 16.4 will have to be performed, butonly for those AS external link advertisements whose destination is N.Before this procedure is performed, the present routing table entry forN should be invalidated.16.7 Events generated as a result of routing table changesChanges to routing table entries sometimes cause the OSPF area borderrouters to take additional actions.  These routers need to act on thefollowing routing table changes:o   The cost or path type of a routing table entry has changed.  If the    destination described by this entry is a Network or AS boundary    router, and this is not simply a change of AS external routes, new    summary link advertisements may have to be generated (potentially    one for each attached area, including the backbone).  SeeSection12.4.3 for more information.  If a previously advertised entry has    been deleted, or is no longer advertisable to a particular area, the    advertisement must be flushed from the routing domain by setting its    age to MaxAge and reflooding (seeSection 14.1).[Moy]                                                         [Page 128]

RFC 1247                     OSPF Version 2                    July 1991o   A routing table entry associated with a configured virtual link has    changed.  The destination of such a routing table entry is an area    border router.  The change indicates a modification to the virtual    link's cost or viability.    If the entry indicates that the area border router is newly    reachable (via TOS 0), the corresponding virtual link is now    operational.  An Interface Up event should be generated for the    virtual link, which will cause a virtual adjacency to begin to form    (seeSection 10.3).  At this time the virtual interface's IP address    and the virtual neighbor's IP address are also calculated.    If the entry indicates that the area border router is no longer    reachable (via TOS 0), the virtual link and its associated adjacency    should be destroyed.  This means an Interface Down event should be    generated for the associated virtual link.    If the cost of the entry has changed, and there is a fully    established virtual adjacency, a new router links advertisement for    the backbone must be originated.  This in turn may cause further    routing table changes.16.8 Equal-cost multipathThe OSPF protocol maintains multiple equal-cost routes to alldestinations.  This can be seen in the steps used above to calculate therouting table, and in the definition of the routing table structure.Each one of the multiple routes will be of the same type (intra-area,inter-area, type 1 external or type 2 external), cost, and will have thesame associated area.  However, each route specifies a separate next hopand advertising router.There is no requirement that a router running OSPF keep track of allpossible equal-cost routes to a destination.  An implementation maychoose to keep only a fixed number of routes to any given destination.This does not affect any of the algorithms presented in thisspecification.16.9 Building the non-zero-TOS portion of the routing tableThe OSPF protocol can calculate a different set of routes for each IPTOS (seeSection 2.4).  Support for TOS-based routing is optional.TOS-capable and non-TOS-capable routers can be mixed in an OSPF routingdomain.  Routers not supporting TOS calculate only the TOS 0 route toeach destination.  These routes are then used to forward all data[Moy]                                                         [Page 129]

RFC 1247                     OSPF Version 2                    July 1991traffic, regardless of the TOS indications in the data packet's IPheader.  A router that does not support TOS indicates this fact to theother OSPF routers by clearing the T-bit in the Options field of itsrouter links advertisement.The above sections detailing the routing table calculations handle theTOS 0 case only.  In general, for routers supporting TOS-based routing,each piece of the routing table calculation must be rerun separately forthe non-zero TOS values.  When calculating routes for TOS X, only TOS Xmetrics can be used.  Any link state advertisement may specify aseparate cost for each TOS (a cost for TOS 0 must always be specified).The encoding of TOS in OSPF link state advertisements is described inSection 12.3.An advertisement can specify that it is restricted to TOS 0 (i.e., non-zero TOS is not handled) by clearing the T-bit in the link stateadvertisement's Option field.  Such advertisements are not used whencalculating routes for non-zero TOS.  For this reason, it is possiblethat a destination is unreachable for some non-zero TOS.  In this case,the TOS 0 path is used when forwarding packets (seeSection 11.1).The following lists the modifications needed when running the routingtable calculation for a non-zero TOS value (called TOS X).  In general,routers and advertisements that do not support TOS are omitted from thecalculation.Calculating the shortest-path tree (Section  16.1).    Routers that do not support TOS-based routing should be omitted from    the shortest-path tree calculation.  These routers are identified as    those having the T-bit reset in their router links advertisements.    Such routers should never be added to the Dijktra algorithm's    candidate list, nor should their router links advertisements be    examined when adding the stub networks to the tree.Calculating the inter-area routes (Section  16.2).    Inter-area paths are the concatenation of a path to an area border    router with a summary link.  When calculating TOS X routes, both    path components must also specify TOS X.  In other words, only TOS X    paths to the area border router are examined, and the area border    router must be advertising a TOS X route to the destination.  Note    that this means that summary link advertisements having the T-bit    reset in their Options field are not considered.Resolving virtual next hops (Section 16.3).    This calculation again considers the concatenation of a path to an    area border router with a summary link.  As with inter-area routes,    only TOS X paths to the area border router are examined, and the[Moy]                                                         [Page 130]

RFC 1247                     OSPF Version 2                    July 1991    area border router must be advertising a TOS X route to the    destination.Calculating AS external routes (Section 16.4).    This calculation considers the concatenation of a path to a    forwarding address with an AS external link.  Only TOS X paths to    the forwarding address are examined, and the AS boundary router must    be advertising a TOS X route to the destination.  Note that this    means that AS external link advertisements having the T-bit reset in    their Options field are not considered.    In addition, the advertising AS boundary router must also be    reachable for its advertisements to be considered (seeSection16.4).  However, if the advertising router and the forwarding    address are not one in the same, the advertising router need only be    reachable via TOS 0.[Moy]                                                         [Page 131]

RFC 1247                     OSPF Version 2                    July 1991    [1]The graph's vertices represent either routers, transit networks,    or stub networks.  Since routers may belong to multiple areas, it is    not possible to color the graph's vertices.    [2]It is possible for all of a router's interfaces to be unnumbered    point-to-point links.  In this case, an IP address must be assigned    to the router.  This address will then be advertised in the router's    router links advertisement as a host route.    [3]Note that in these cases both interfaces, the non-virtual and the    virtual, would have the same IP address.    [4]Note that no host route is generated for, and no IP packets can    be addressed to, interfaces to unnumbered point-to-point networks.    This is regardless of such an interface's state.    [5]It is instructive to see what happens when the Designated Router    for the network crashes.  Call the Designated Router for the network    RT1, and the the Backup Designated Router RT2.  If router RT1    crashes (or maybe its interface to the network dies), the other    routers on the network will detect RT1's absence within    RouterDeadInterval seconds.  All routers may not detect this at    precisely the same time; the routers that detect RT1's absence    before RT2 does will, for a time, select RT2 to be both Designated    Router and Backup Designated Router.  When RT2 detects that RT1 is    gone it will move itself to Designated Router.  At this time, the    remaining router having highest Router Priority will be selected as    Backup Designated Router.    [6]On point-to-point networks, the lower level protocols indicate    whether the neighbor is up and running.  Likewise, existence of the    neighbor on virtual links is indicated by the routing table    calculation.  However, in both these cases, the Hello Protocol is    still used.  This ensures that communication between the neighbors    is bidirectional, and that each of the neighbors has a functioning    routing protocol layer.    [7]When the identity of the Designated Router is changing, it may be    quite common for a neighbor in this state to send the router a    Database Description packet; this means that there is some momentary    disagreement on the Designated Router's identity.    [8]Note that it is possible for a router to resynchronize any of its    fully established adjacencies by setting the adjacency's state back    to ExStart.  This will cause the other end of the adjacency to    process a Seq Number Mismatch event, and therefore to also go back    to ExStart state.[Moy]                                                         [Page 132]

RFC 1247                     OSPF Version 2                    July 1991    [9]The address space of IP networks and the address space of OSPF    Router IDs may overlap.  That is, a network may have an IP address    which is identical (when considered as a 32-bit number) to some    router's Router ID.    [10]It is assumed that, for two different address ranges matching    the destination, one range is more specific than the other. Non-    contiguous subnet masks can be configured to violate this    assumption. Such subnet mask configurations cannot be handled by the    OSPF protocol.    [11]MaxAgeDiff is an architectural constant.  It indicates the    maximum dispersion of ages, in seconds, that can occur for a single    link state instance as it is flooded throughout the routing domain.    If two advertisements differ by more than this, they are assumed to    be different instances of the same advertisement.  This can occur    when a router restarts and loses track of its previous sequence    number.  SeeSection 13.4 for more details.    [12]When two advertisements have different checksums, they are    assumed to be separate instances.  This can occur when a router    restarts, and loses track of its previous sequence number.  In this    case, since the two advertisements have the same sequence number, it    is not possible to determine which link state is actually newer.  If    the wrong advertisement is accepted as newer, the originating router    will originate another instance.  SeeSection 13.4 for further    details.    [13]There is one instance where a lookup must be done based on    partial information.  This is during the routing table calculation,    when a network links advertisement must be found based solely on its    Link State ID.  The lookup in this case is still well defined, since    no two network advertisements can have the same Link State ID.    [14]This clause covers the case: Inter-area routes are not    summarized to the backbone.  This is because inter-area routes are    always associated with the backbone area.    [15]By keeping more information in the routing table, it is possible    for an implementation to recalculate the shortest path tree only for    a single area.  In fact, there are incremental algorithms that allow    an implementation to recalculate only a portion of the shortest path    tree [BBN].  These algorithms are beyond the scope of this    specification.    [16]This is how the Link state request list is emptied, which    eventually causes the neighbor state to transition to Full.  SeeSection 10.9 for more details.[Moy]                                                         [Page 133]

RFC 1247                     OSPF Version 2                    July 1991    [17]It should be a relatively rare occurrence for an advertisement's    age to reach MaxAge.  Usually, the advertisement will be replaced by    a more recent instance before it ages out.    [18]Only the TOS 0 routes are important here.  This is because all    routing protocol packets are sent with TOS= 0.  SeeAppendix A.    [19]It may be the case that paths to certain destinations do not    vary based on TOS.  For these destinations, the routing calculation    need not be repeated for each TOS value.  In addition, there need    only be a single routing table entry for these destinations (instead    of a separate entry for each TOS value).    [20]Strictly speaking, because of equal-cost multipath, the    algorithm does not create a tree.  We continue to use the "tree"    terminology because that is what occurs most often in the existing    literature.    [21]This means that before data traffic will flow between a pair of    neighboring routers, their link state databases must be    synchronized.  Before synchronization (neighbor state < Full), a    router will not include the connection to its neighbor in its link    state advertisements.    [22]As a result of this clause, when a virtual link exists between    the calculating router and an AS boundary router, the intra-area    path through the virtual link's transit area is always preferred    over the virtual link itself.    [23]Note the similarity between this procedure and the calculation    of inter-area routes by a router internal to Area A.    [24]When the forwarding address is non-zero, it should point to a    router belonging to another Autonomous System.  SeeSection 12.4.4    for more details.[Moy]                                                         [Page 134]

RFC 1247                     OSPF Version 2                    July 1991References[BBN]       McQuillan, J.M., Richer, I.  and Rosen, E.C.  ARPANET            Routing Algorithm Improvements.  BBN Technical Report 3803,            April 1978.[DEC]       Digital Equipment Corporation.  Information processing            systems -- Data communications -- Intermediate System to            Intermediate System Intra-Domain Routing Protocol.  October            1987.[McQuillan] McQuillan, J.  et.al.  The New Routing Algorithm for the            Arpanet.  IEEE Transactions on Communications, May 1980.[Perlman]   Perlman, Radia.  Fault-Tolerant Broadcast of Routing            Information.  Computer Networks, Dec.  1983.[RFC 791]   Postel, Jon.  Internet Protocol.  September 1981[RFC 944]   ANSI X3S3.3 86-60.  Final Text of DIS 8473, Protocol for            Providing the Connectionless-mode Network Service.  March            1986.[RFC 1060]  Reynolds, J.  and Postel, J.  Assigned Numbers.  March 1990.[RFC 1112]  Deering, S.E.  Host extensions for IP multicasting.  May            1988.[RFC 1131]  Moy, J.  The OSPF Specification.  October 1989.[RS-85-153] Leiner, Dr.  Barry M., et.al.  The DARPA Internet Protocol            Suite.  DDN Protocol Handbook, April 1985.[Moy]                                                         [Page 135]

RFC 1247                     OSPF Version 2                    July 1991A. OSPF data formatsThis appendix describes the format of OSPF protocol packets and OSPFlink state advertisements.  The OSPF protocol runs directly over the IPnetwork layer.  Before any data formats are described, the details ofthe OSPF encapsulation are explained.Next the OSPF options field is described.  This field describes variouscapabilities that may or may not be supported by pieces of the OSPFrouting domain.  It is contained both in OSPF protocol packets and inOSPF link state advertisements.OSPF packet formats are detailed in Section A.3.  A description of OSPFlink state advertisements appears in Section A.4.A.1 Encapsulation of OSPF packetsOSPF runs directly over the Internet Protocol's network layer.  OSPFpackets are therefore encapsulated solely by IP and local networkheaders.OSPF does not define a way to fragment its protocol packets, and dependson IP fragmentation when transmitting packets larger than the networkMTU.  The OSPF packet types that are likely to be large (DatabaseDescription Packets, Link State Request, Link State Update, and LinkState Acknowledgment packets) can usually be split into several separateprotocol packets, without loss of functionality.  This is recommended;IP fragmentation should be avoided whenever possible.  Using thisreasoning, an attempt should be made to limit the sizes of packets sentover virtual links to 576 bytes.  However, if necessary, the length ofOSPF packets can be up to 65,535 bytes (including the IP header).The other important features of OSPF's IP encapsulation are:o   Use of IP multicast.  Some OSPF messages are multicast, when sent    over multi-access networks.  Two distinct IP multicast addresses are    used.  Packets destined to these multicast addresses should never be    forwarded.  Such packets are meant to travel a single hop only.  To    ensure that these packets will not travel multiple hops, their IP    TTL must be set to 1.    AllSPFRouters        This multicast address has been assigned the value 224.0.0.5.        All routers running OSPF should be prepared to receive packets        sent to this address.  Hello packets are always sent to this        destination.  Also, certain protocol packets are sent to this[Moy]                                                         [Page 136]

RFC 1247                     OSPF Version 2                    July 1991        address during the flooding procedure.    AllDRouters        This multicast address has been assigned the value 224.0.0.6.        Both the Designated Router and Backup Designated Router must be        prepared to receive packets destined to this address.  Certain        packets are sent to this address during the flooding procedure.o   OSPF is IP protocol number 89.  This number has been registered with    the Network Information Center.  IP protocol number assignments are    documented in [RFC 1060].o   Routing protocol packets are sent with IP TOS of 0.  The OSPF    protocol supports TOS-based routing.  Routes to any particular    destination may vary based on TOS.  However, all OSPF routing    protocol packets are sent with the DTR bits in the IP header's TOS    field (see [RFC 791]) set to 0.o   Routing protocol packets are sent with IP precedence set to    Internetwork Control.  OSPF protocol packets should be given    precedence over regular IP data traffic, in both sending and    receiving.  Setting the IP precedence field in the IP header to    Internetwork Control [RFC 791] may help implement this objective.[Moy]                                                         [Page 137]

RFC 1247                     OSPF Version 2                    July 1991A.2 The options fieldThe OSPF options field is present in OSPF Hello packets, DatabaseDescription packets and all link state advertisements.  The optionsfield enables OSPF routers to support (or not support) optionalcapabilities, and to communicate their capability level to other OSPFrouters.  Through this mechanism routers of differing capabilities canbe mixed within an OSPF routing domain.When used in Hello packets, the options field allows a router to rejecta neighbor because of a capability mismatch.  Alternatively, whencapabilities are exchanged in Database Description packets a router canchoose not to forward certain LSA types to a neighbor because of itsreduced functionality.  Lastly, listing capabilities in LSAs allowsrouters to route traffic around reduced functionality routers, byexcluding them from parts of the routing table calculation.Two capabilities are currently defined.  For each capability, the effectof the capability's appearance (or lack of appearance) in Hello packets,Database Description packets and link state advertisements is specifiedbelow.  For example, the external routing capability (below called theE-bit) has meaning only in OSPF Hello Packets.  Routers should reset(i.e.  clear) the unassigned part of the capability field when sendingHello packets or Database Description packets and when originating linkstate advertisements.Additional capabilities may be assigned in the future.  Routersencountering unrecognized capabilities in received Hello Packets,Database Description packets or link state advertisements should ignorethe capability and process the packet/advertisement normally.                           +-+-+-+-+-+-+-+-+                           | | | | | | |E|T|                           +-+-+-+-+-+-+-+-+                           The options fieldT-bit    This describes the router's TOS capability.  If the T-bit is reset,    then the router supports only a single TOS (TOS 0).  Such a router    is also said to be incapable of TOS-routing.  The absence of the T-    bit in a router links advertisement causes the router to be skipped    when building a non-zero TOS shortest-path tree (seeSection 16.9).    In other words, routers incapable of TOS routing will be avoided as    much as possible when forwarding data traffic requesting a non-zero    TOS.  The absence of the T-bit in a summary link advertisement or an    AS external link advertisement indicates that the advertisement is[Moy]                                                         [Page 138]

RFC 1247                     OSPF Version 2                    July 1991    describing a TOS 0 route only (and not routes for non-zero TOS).E-bit    AS external link advertisements are not flooded into/through OSPF    stub areas (seeSection 3.6).  The E-bit ensures that all members of    a stub area agree on that area's configuration.  The E-bit is    meaningful only in OSPF Hello packets.  When the E-bit is reset in    the Hello packet sent out a particular interface, it means that the    router will neither send nor receive AS external link state    advertisements on that interface (in other words, the interface    connects to a stub area).  Two routers will not become neighbors    unless they agree on the state of the E-bit.[Moy]                                                         [Page 139]

RFC 1247                     OSPF Version 2                    July 1991A.3 OSPF Packet FormatsThere are five distinct OSPF packet types.  All OSPF packet types beginwith a standard 24 byte header.  This header is described first.  Eachpacket type is then described in a succeeding section.  In thesesections each packet's division into fields is displayed, and then thefield definitions are enumerated.All OSPF packet types (other than the OSPF Hello packets) deal withlists of link state advertisements.  For example, Link State Updatepackets implement the flooding of advertisements throughout the OSPFrouting domain.  Because of this, OSPF protocol packets cannot be parsedunless the format of link state advertisements is also understood.  Theformat of Link state advertisements is described in Section A.4.The receive processing of OSPF packets is detailed inSection 8.2.  Thesending of OSPF packets is explained inSection 8.1.[Moy]                                                         [Page 140]

RFC 1247                     OSPF Version 2                    July 1991A.3.1 The OSPF packet headerEvery OSPF packet starts with a common 24 byte header.  This headercontains all the necessary information to determine whether the packetshould be accepted for further processing.  This determination isdescribed inSection 8.2 of the specification.    0                   1                   2                   3    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |   Version #   |     Type      |         Packet length         |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                          Router ID                            |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                           Area ID                             |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |           Checksum            |             Autype            |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                       Authentication                          |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                       Authentication                          |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Version #    The OSPF version number.  This specification documents version 2 of    the protocol.Type    The OSPF packet types are as follows.  The format of each of these    packet types is described in a succeeding section.                        Type   Description                        ________________________________                        1      Hello                        2      Database Description                        3      Link State Request                        4      Link State Update                        5      Link State Acknowledgment[Moy]                                                         [Page 141]

RFC 1247                     OSPF Version 2                    July 1991Packet length    The length of the protocol packet in bytes.  This length includes    the standard OSPF header.Router ID    The Router ID of the packet's source.  In OSPF, the source and    destination of a routing protocol packet are the two ends of an    (potential) adjacency.Area ID    A 32 bit number identifying the area that this packet belongs to.    All OSPF packets are associated with a single area.  Most travel a    single hop only.  Packets travelling over a virtual link are    labelled with the backbone area ID of 0.Checksum    The standard IP checksum of the entire contents of the packet,    excluding the 64-bit authentication field.  This checksum is    calculated as the 16-bit one's complement of the one's complement    sum of all the 16-bit words in the packet, excepting the    authentication field.  If the packet's length is not an integral    number of 16-bit words, the packet is padded with a byte of zero    before checksumming.AuType    Identifies the authentication scheme to be used for the packet.    Authentication is discussed inAppendix E of the specification.    ConsultAppendix E for a list of the currently defined    authentication types.Authentication    A 64-bit field for use by the authentication scheme.[Moy]                                                         [Page 142]

RFC 1247                     OSPF Version 2                    July 1991A.3.2 The Hello packetHello packets are OSPF packet type 1.  These packets are sentperiodically on all interfaces (including virtual links) in order toestablish and maintain neighbor relationships.  In addition, Hellos aremulticast on those physical networks having a multicast or broadcastcapability, enabling dynamic discovery of neighboring routers.All routers connected to a common network must agree on certainparameters (network mask, hello and dead intervals).  These parametersare included in Hello packets, so that differences can inhibit theforming of neighbor relationships.  A detailed explanation of thereceive processing for Hello packets is presented inSection 10.5.  Thesending of Hello packets is covered inSection 9.5.    0                   1                   2                   3    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |   Version #   |       1       |         Packet length         |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                          Router ID                            |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                           Area ID                             |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |           Checksum            |             Autype            |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                       Authentication                          |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                       Authentication                          |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                        Network Mask                           |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |         HelloInt              |    Options    |    Rtr Pri    |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                           DeadInt                             |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                      Designated Router                        |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                   Backup Designated Router                    |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                          Neighbor                             |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                              ...                              |[Moy]                                                         [Page 143]

RFC 1247                     OSPF Version 2                    July 1991Network mask    The network mask associated with this interface.  For example, if    the interface is to a class B network whose third byte is used for    subnetting, the network mask is 0xffffff00.Options    The optional capabilities supported by the router, as documented in    Section A.2.HelloInt    The number of seconds between this router's Hello packets.Rtr Pri    This router's Router Priority.  Used in (Backup) Designated Router    election.  If set to 0, the router will be ineligible to become    (Backup) Designated Router.Deadint    The number of seconds before declaring a silent router down.Designated Router    The identity of the Designated Router for this network, in the view    of the advertising router.  The Designated Router is identified here    by its IP interface address on the network.  Set to 0 if there is no    Designated Router.Backup Designated Router    The identity of the Backup Designated Router for this network, in    the view of the advertising router.  The Backup Designated Router is    identified here by its IP interface address on the network.  Set to    0 if there is no backup Designated Router.Neighbor    The Router IDs of each router from whom valid Hello packets have    been seen recently on the network.  Recently means in the last    DeadInt seconds.[Moy]                                                         [Page 144]

RFC 1247                     OSPF Version 2                    July 1991A.3.3 The Database Description packetDatabase Description packets are OSPF packet type 2.  These packets areexchanged when an adjacency is being initialized.  They describe thecontents of the topological database.  Multiple packets may be used todescribe the database.  For this purpose a poll-response procedure isused.  One of the routers is designated to be master, the other a slave.The master sends Database Description packets (polls) which areacknowledged by Database Description packets sent by the slave(responses).  The responses are linked to the polls via the packets'sequence numbers.The format of the Database Description packet is very similar to boththe Link State Request and Link State Acknowledgment packets.  The mainpart of all three is a list of items, each item describing a piece ofthe topological database.  The sending of Database Description Packetsis documented inSection 10.8.  The reception of Database Descriptionpackets is documented inSection 10.6.    0                   1                   2                   3    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |   Version #   |       2       |         Packet length         |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                          Router ID                            |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                           Area ID                             |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |           Checksum            |             Autype            |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                       Authentication                          |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                       Authentication                          |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |       0       |       0       |    Options    |0|0|0|0|0|I|M|MS   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                     DD sequence number                        |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                                                               |   +-                                                             -+   |                             A                                 |   +-                 Link State Advertisement                    -+   |                           Header                              |   +-                                                             -+   |                                                               |   +-                                                             -+   |                                                               |[Moy]                                                         [Page 145]

RFC 1247                     OSPF Version 2                    July 1991   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                              ...                              |0   These fields are reserved.They must be 0.Options    The optional capabilities supported by the router, as documented in    Section A.2.I-bit    The Init bit.  When set to 1, this packet is the first in the    sequence of database descriptions.M-bit    The More bit.  When set to 1, it indicates that more database    descriptions are to follow.MS-bit    The Master/Slave bit.  When set to 1, it indicates that the router    is the master during the database exchange process.  Otherwise, the    router is the slave.DD sequence number    Used to sequence the collection of database description packets.    The initial value (indicated by the Init bit being set) should be    unique.  The sequence number then increments until the complete    database description has been sent.The rest of the packet consists of a (possibly partial) list of thetopological database's pieces.  Each link state advertisement in thedatabase is described by its link state header.  The link state headeris documented in Section A.4.1.  It contains all the informationrequired to uniquely identify both the advertisement and theadvertisement's current instance.[Moy]                                                         [Page 146]

RFC 1247                     OSPF Version 2                    July 1991A.3.4 The Link State Request packetLink State Request packets are OSPF packet type 3.  After exchangingDatabase Description packets with a neighboring router, a router mayfind that parts of its topological database are out of date.  The LinkState Request packet is used to request the pieces of the neighbor'sdatabase that are more up to date.  Multiple Link State Request packetsmay need to be used.  The sending of Link State Request packets is thelast step in bringing up an adjacency.A router that sends a Link State Request packet has in mind the preciseinstance of the database pieces it is requesting (defined by LS sequencenumber, LS checksum, and LS age).  It may receive even more recentinstances in response.The sending of Link State Request packets is documented inSection 10.9.The reception of Link State Request packets is documented inSection10.7.    0                   1                   2                   3    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |   Version #   |       3       |         Packet length         |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                          Router ID                            |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                           Area ID                             |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |           Checksum            |             Autype            |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                       Authentication                          |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                       Authentication                          |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                          LS type                              |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                       Link State ID                           |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                     Advertising Router                        |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                              ...                              |Each advertisement requested is specified by its LS type, Link State ID,and Advertising Router.  This uniquely identifies the advertisement, butnot its instance.  Link State Request packets are understood to berequests for the most recent instance (whatever that might be).[Moy]                                                         [Page 147]

RFC 1247                     OSPF Version 2                    July 1991A.3.5 The Link State Update packetLink State Update packets are OSPF packet type 4.  These packetsimplement the flooding of link state advertisements.  Each Link StateUpdate packet carries a collection of link state advertisements one hopfurther from its origin.  Several link state advertisements may beincluded in a single packet.Link State Update packets are multicast on those physical networks thatsupport multicast/broadcast.  In order to make the flooding procedurereliable, flooded advertisements are acknowledged in Link StateAcknowledgment packets.  If retransmission of certain advertisements isnecessary, the retransmitted advertisements are always carried byunicast Link State Update packets.  For more information on the reliableflooding of link state advertisements, consultSection 13.    0                   1                   2                   3    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |   Version #   |       4       |         Packet length         |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                          Router ID                            |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                           Area ID                             |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |           Checksum            |             Autype            |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                       Authentication                          |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                       Authentication                          |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                      # advertisements                         |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                                                               |   +-                                                            +-+   |                  Link state advertisements                    |   +-                                                            +-+   |                              ...                              |# advertisements    The number of link state advertisements included in this update.The body of the Link State Update packet consists of a list of linkstate advertisements.  Each advertisement begins with a common 20 byte[Moy]                                                         [Page 148]

RFC 1247                     OSPF Version 2                    July 1991header, the link state advertisement header.  This header is describedin Section A.4.1.  Otherwise, the format of each of the five types oflink state advertisements is different.  Their formats are described inSection A.4.[Moy]                                                         [Page 149]

RFC 1247                     OSPF Version 2                    July 1991A.3.6 The Link State Acknowledgment packetLink State Acknowledgment Packets are OSPF packet type 5.  To make theflooding of link state advertisements reliable, flooded advertisementsare explicitly acknowledged.  This acknowledgment is accomplishedthrough the sending and receiving of Link State Acknowledgment packets.Multiple link state advertisements can be acknowledged in a singlepacket.Depending on the state of the sending interface and the source of theadvertisements being acknowledged, a Link State Acknowledgment packet issent either to the multicast address AllSPFRouters, to the multicastaddress AllDRouters, or as a unicast.  The sending of Link StateAcknowledgement packets is documented inSection 13.5.  The reception ofLink State Acknowledgement packets is documented inSection 13.7.The format of this packet is similar to that of the Data Descriptionpacket.  The body of both packets is simply a list of link stateadvertisement headers.    0                   1                   2                   3    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |   Version #   |       5       |         Packet length         |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                          Router ID                            |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                           Area ID                             |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |           Checksum            |             Autype            |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                       Authentication                          |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                       Authentication                          |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                                                               |   +-                                                             -+   |                             A                                 |   +-                 Link State Advertisement                    -+   |                           Header                              |   +-                                                             -+   |                                                               |   +-                                                             -+   |                                                               |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                              ...                              |[Moy]                                                         [Page 150]

RFC 1247                     OSPF Version 2                    July 1991Each acknowledged link state advertisement is described by its linkstate header.  The link state header is documented in Section A.4.1.  Itcontains all the information required to uniquely identify both theadvertisement and the advertisement's current instance.[Moy]                                                         [Page 151]

RFC 1247                     OSPF Version 2                    July 1991A.4 Link state advertisement formatsThere are five distinct types of link state advertisements.  Each linkstate advertisement begins with a standard 20-byte link state header.This header is explained in Section A.4.1.  Succeeding sections thendiagram the separate link state advertisement types.Each link state advertisement describes a piece of the OSPF routingdomain.  Every router originates a router links advertisement.  Inaddition, whenever the router is elected Designated Router, itoriginates a network links advertisement.  Other types of link stateadvertisements may also be originated (seeSection 12.4).  All linkstate advertisements are then flooded throughout the OSPF routingdomain.  The flooding algorithm is reliable, ensuring that all routershave the same collection of link state advertisements.  (SeeSection 13for more information concerning the flooding algorithm).  Thiscollection of advertisements is called the link state (or topological)database.From the link state database, each router constructs a shortest pathtree with itself as root.  This yields a routing table (seeSection 11).For the details of the routing table build process, seeSection 16.[Moy]                                                         [Page 152]

RFC 1247                     OSPF Version 2                    July 1991A.4.1 The Link State Advertisement headerAll link state advertisements begin with a common 20 byte header.  Thisheader contains enough information to uniquely identify theadvertisement (LS type, Link State ID, and Advertising Router).Multiple instances of the link state advertisement may exist in therouting domain at the same time.  It is then necessary to determinewhich instance is more recent.  This is accomplished by examining the LSage, LS sequence number and LS checksum fields that are also containedin the link state advertisement header.    0                   1                   2                   3    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |            LS age             |    Options    |    LS type    |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                        Link State ID                          |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                     Advertising Router                        |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                     LS sequence number                        |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |         LS checksum           |             length            |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+LS age    The time in seconds since the link state advertisement was    originated.Options    The optional capabilities supported by the described portion of the    routing domain.  OSPF's optional capabilities are documented in    Section A.2.LS type    The type of the link state advertisement.  Each link state type has    a separate advertisement format.  The link state types are as    follows (seeSection 12.1.3 for further explanation):[Moy]                                                         [Page 153]

RFC 1247                     OSPF Version 2                    July 1991                      LS Type   Description                      ___________________________________                      1         Router links                      2         Network links                      3         Summary link (IP network)                      4         Summary link (ASBR)                      5         AS external linkLink State ID    This field identifies the portion of the internet environment that    is being described by the advertisement.  The contents of this field    depend on the advertisement's LS type.  For example, in network    links advertisements the Link State ID is set to the IP interface    address of the network's Designated Router (from which the network's    IP address can be derived).  The Link State ID is further discussed    inSection 12.1.4.Advertising Router    The Router ID of the router that originated the link state    advertisement.  For example, in network links advertisements this    field is set to the Router ID of the network's Designated Router.LS sequence number    Detects old or duplicate link state advertisements.  Successive    instances of a link state advertisement are given successive LS    sequence numbers.  SeeSection 12.1.6 for more details.LS checksum    The Fletcher checksum of the complete contents of the link state    advertisement.  SeeSection 12.1.7 for more details.length    The length in bytes of the link state advertisement.  This includes    the 20 byte link state header.[Moy]                                                         [Page 154]

RFC 1247                     OSPF Version 2                    July 1991A.4.2 Router links advertisementsRouter links advertisements are the Type 1 link state advertisements.Each router in an area originates a router links advertisement.  Theadvertisement describes the state and cost of the router's links (orinterfaces) to the area.  All of the router's links to the area must bedescribed in a single router links advertisement.  For detailsconcerning the construction of router links advertisements, seeSection12.4.1.In router links advertisements, the Link State ID field is set to therouter's OSPF Router ID.  The T-bit is set in the advertisement's Optionfield if and only if the router is able to calculate a separate set ofroutes for each IP TOS.  Router links advertisements are floodedthroughout a single area only.    0                   1                   2                   3    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |            LS age             |     Options   |       1       |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                        Link State ID                          |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                     Advertising Router                        |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                     LS sequence number                        |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |         LS checksum           |             length            |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |      0    |E|B|        0      |            # links            |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                          Link ID                              |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                         Link Data                             |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |     Type      |     # TOS     |        TOS 0 metric           |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |      TOS      |        0      |            metric             |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                              ...                              |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |      TOS      |        0      |            metric             |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                          Link ID                              |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                         Link Data                             |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+[Moy]                                                         [Page 155]

RFC 1247                     OSPF Version 2                    July 1991   |                              ...                              |bit E    When set, the router is an AS boundary router (E is for external)bit B    When set, the router is an area border router (B is for border)# links    The number of router links described by this advertisement.  This    must be the total collection of router links to the area.The following fields are used to describe each router link.  Each routerlink is typed (see the below Type field).  The type field indicates thekind of link being described.  It may be a link to a transit network, toanother router or to a stub network.  The values of all the other fieldsdescribing a router link depend on the link's type.  For example, eachlink has an associated 32-bit data field.  For links to stub networksthis field specifies the network's IP address mask.  For the other linktypes the Link Data specifies the router's associated IP interfaceaddress.Type    A quick description of the router link.  One of the following.  Note    that host routes are classified as links to stub networks whose    network mask is 0xffffffff.               Type   Description               __________________________________________________               1      Point-to-point connection to another router               2      Connection to a transit network               3      Connection to a stub network               4      Virtual linkLink ID    Identifies the object that this router link connects to.  Value    depends on the link's type.  When connecting to an object that also    originates a link state advertisement (i.e., another router or a    transit network) the Link ID is equal to the other advertisement's[Moy]                                                         [Page 156]

RFC 1247                     OSPF Version 2                    July 1991    Link State ID.  This provides the key for looking up said    advertisement in the link state database.  SeeSection 12.2 for more    details.                     Type   Link ID                     ______________________________________                     1      Neighboring router's ID                     2      IP address of Designated Router                     3      IP network/subnet number                     4      Neighboring router's IDLink Data    Contents again depend on the link's Type field.  For connections to    stub network, it specifies the network mask.  For the other link    types it specifies the router's associated IP interface address.    This latter piece of information is needed during the routing table    build process, when calculating the IP address of the next hop.  SeeSection 16.1.1 for more details.#metrics    The number of different TOS metrics given for this link, not    counting the required metric for TOS 0.  For example, if no    additional TOS metrics are given, this field should be set to 0.TOS 0 metric    The cost of using this router link for TOS 0.For each link, separate metrics may be specified for each Type ofService (TOS).  The metric for TOS 0 must always be included, and wasdiscussed above.  Metrics for non-zero TOS are described below.  Theencoding of TOS in OSPF link state advertisements is described inSection 12.3.  Note that the cost for non-zero TOS values that are notspecified defaults to the TOS 0 cost.  Metrics must be listed in orderof increasing TOS encoding.  For example, the metric for TOS 16 mustalways follow the metric for TOS 8 when both are specified.TOS IP type of service that this metric refers to.  The encoding of TOS    in OSPF link state advertisements is described inSection 12.3.metric    The cost of using this outbound router link, for traffic of the[Moy]                                                         [Page 157]

RFC 1247                     OSPF Version 2                    July 1991    specified TOS.[Moy]                                                         [Page 158]

RFC 1247                     OSPF Version 2                    July 1991A.4.3 Network links advertisementsNetwork links advertisements are the Type 2 link state advertisements.A network links advertisement is originated for each transit network inthe area.  A transit network is a multi-access network that has morethan one attached router.  The network links advertisement is originatedby the network's Designated Router.  The advertisement describes allrouters attached to the network, including the Designated Router itself.The advertisement's Link State ID field lists the IP interface addressof the Designated Router.The distance from the network to all attached routers is zero, for alltypes of service.  This is why the TOS and metric fields need not bespecified in the network links advertisement.  For details concerningthe construction of network links advertisements, seeSection 12.4.2.    0                   1                   2                   3    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |            LS age             |      Options  |      2        |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                        Link State ID                          |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                     Advertising Router                        |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                     LS sequence number                        |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |         LS checksum           |             length            |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                         Network Mask                          |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                        Attached Router                        |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                              ...                              |Network Mask    The IP address mask for the network.  For example, a class A network    would have the mask 0xff000000.Attached Router    The Router IDs of each of the routers attached to the network.    Actually, only those routers that are fully adjacent to the    Designated Router are listed.  The Designated Router includes itself    in this list.  The number of routers included can be deduced from    the link state advertisement's length field.[Moy]                                                         [Page 159]

RFC 1247                     OSPF Version 2                    July 1991A.4.4 Summary link advertisementsSummary link advertisements are the Type 3 and 4 link stateadvertisements.  These advertisements are originated by area borderrouters.  A separate summary link advertisement is made for eachdestination (known to the router) which belongs to the AS, yet isoutside the area.  For details concerning the construction of summarylink advertisements, seeSection 12.4.3.Type 3 link state advertisements are used when the destination is an IPnetwork.  In this case the advertisement's Link State ID field is an IPnetwork number.  When the destination is an AS boundary router, a Type 4advertisement is used, and the Link State ID field is the AS boundaryrouter's OSPF Router ID.  (To see why it is necessary to advertise thelocation of each ASBR, consultSection 16.4.)  Other than the differencein the Link State ID field, the format of Type 3 and 4 link stateadvertisements is identical.For stub areas, type 3 summary link advertisements can also be used todescribe a (per-area) default route.  Default summary routes are used instub areas instead of flooding a complete set of external routes.  Whendescribing a default summary route, the advertisement's Link State ID isalways set to DefaultDestination (0.0.0.0) and the Network Mask is setto 0.0.0.0.Separate costs may be advertised for each IP Type of Service.  Theencoding of TOS in OSPF link state advertisements is described inSection 12.3.  Note that the cost for TOS 0 must be included, and isalways listed first.  If the T-bit is reset in the advertisement'sOption field, only a route for TOS 0 is described by the advertisement.Otherwise, routes for the other TOS values are also described; if a costfor a certain TOS is not included, its cost defaults to that specifiedfor TOS 0.    0                   1                   2                   3    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |            LS age             |     Options   |    3 or 4     |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                        Link State ID                          |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                     Advertising Router                        |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                     LS sequence number                        |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |         LS checksum           |             length            |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+[Moy]                                                         [Page 160]

RFC 1247                     OSPF Version 2                    July 1991   |                         Network Mask                          |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |     TOS       |                  metric                       |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                              ...                              |Network Mask    For Type 3 link state advertisements, this indicates the    destination's IP network mask.  For example, when advertising the    location of a class A network the value 0xff000000 would be used.    This field is not meaningful and must be zero for Type 4 link state    advertisements.For each specified type of service, the following fields are defined.The number of TOS routes included can be calculated from the link stateadvertisement's length field.  Values for TOS 0 must be specified; theyare listed first.  Other values must be listed in order of increasingTOS encoding.  For example, the cost for TOS 16 must always follow thecost for TOS 8 when both are specified.TOS The Type of Service that the following cost concerns.  The encoding    of TOS in OSPF link state advertisements is described inSection12.3.metric    The cost of this route.  Expressed in the same units as the    interface costs in the router links advertisements.[Moy]                                                         [Page 161]

RFC 1247                     OSPF Version 2                    July 1991A.4.5 AS external link advertisementsAS external link advertisements are the Type 5 link stateadvertisements.  These advertisements are originated by AS boundaryrouters.  A separate advertisement is made for each destination (knownto the router) which is external to the AS.  For details concerning theconstruction of AS external link advertisements, seeSection 12.4.3.AS external link advertisements usually describe a particular externaldestination.  For these advertisements the Link State ID field specifiesan IP network number.  AS external link advertisements are also used todescribe a default route.  Default routes are used when no specificroute exists to the destination.  When describing a default route, theLink State ID is always set to DefaultDestination (0.0.0.0) and theNetwork Mask is set to 0.0.0.0.Separate costs may be advertised for each IP Type of Service.  Theencoding of TOS in OSPF link state advertisements is described inSection 12.3.  Note that the cost for TOS 0 must be included, and isalways listed first.  If the T-bit is reset in the advertisement'sOption field, only a route for TOS 0 is described by the advertisement.Otherwise, routes for the other TOS values are also described; if a costfor a certain TOS is not included, its cost defaults to that specifiedfor TOS 0.    0                   1                   2                   3    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |            LS age             |     Options   |      5        |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                        Link State ID                          |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                     Advertising Router                        |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                     LS sequence number                        |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |         LS checksum           |             length            |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                         Network Mask                          |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |E|    TOS      |                  metric                       |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                      Forwarding address                       |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                      External Route Tag                       |   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   |                              ...                              |[Moy]                                                         [Page 162]

RFC 1247                     OSPF Version 2                    July 1991Network Mask    The IP network mask for the advertised destination.  For example,    when advertising a class A network the mask 0xff000000 would be    used.For each specified type of service, the following fields are defined.The number of TOS routes included can be calculated from the link stateadvertisement's length field.  Values for TOS 0 must be specified; theyare listed first.  Other values must be listed in order of increasingTOS encoding.  For example, the cost for TOS 16 must always follow thecost for TOS 8 when both are specified.bit E    The type of external metric.  If bit E is set, the metric specified    is a Type 2 external metric.  This means the metric is considered    larger than any link state path.  If bit E is zero, the specified    metric is a Type 1 external metric.  This means that is is    comparable directly (without translation) to the link state metric.Forwarding address    Data traffic for the advertised destination will be forwarded to    this address.  If the Forwarding address is set to 0.0.0.0, data    traffic will be forwarded instead to the advertisement's originator    (i.e., the responsible AS boundary router).TOS The Type of Service that the following cost concerns.  The encoding    of TOS in OSPF link state advertisements is described inSection12.3.metric    The cost of this route.  Interpretation depends on the external type    indication (bit E above).External Route Tag    A 32-bit field attached to each external route.  This is not used by    the OSPF protocol itself.  It may be used to communicate information    between AS boundary routers; the precise nature of such information    is outside the scope of this specification.[Moy]                                                         [Page 163]

RFC 1247                     OSPF Version 2                    July 1991B. Architectural ConstantsSeveral OSPF protocol parameters have fixed architectural values.  Theseparameters have been referred to in the text by names such asLSRefreshTimer.  The same naming convention is used for the configurableprotocol parameters.  They are defined inappendix C.The name of each architectural constant follows, together with its valueand a short description of its function.LSRefreshTime    The maximum time between distinct originations of any particular    link state advertisement.  For each link state advertisement that a    router originates, an interval timer should be set to this value.    Firing of this timer causes a new instance of the link state    advertisement to be originated.  The value of LSRefreshTime is set    to 30 minutes.MinLSInterval    The minimum time between distinct originations of any particular    link state advertisement.  The value of MinLSInterval is set to 5    seconds.MaxAge    The maximum age that a link state advertisement can attain.  When an    advertisement's age reaches MaxAge, it is reflooded.  It is then    removed from the database as soon as this flood is acknowledged,    i.e., as soon as it has been removed from all neighbor Link state    retransmission lists.  Advertisements having age MaxAge are not used    in the routing table calculation.  The value of MaxAge must be    greater than LSRefreshTime.  The value of MaxAge is set to 1 hour.CheckAge    When the age of a link state advertisement (that is contained in the    link state database) hits a multiple of CheckAge, the    advertisement's checksum is verified.  An incorrect checksum at this    time indicates a serious error.  The value of CheckAge is set to 5    minutes.MaxAgeDiff    The maximum time dispersion that can occur, as a link state    advertisement is flooded throughout the AS.  Most of this time is    accounted for by the link state advertisements sitting on router    output queues (and therefore not aging) during the flooding process.    The value of MaxAgeDiff is set to 15 minutes.[Moy]                                                         [Page 164]

RFC 1247                     OSPF Version 2                    July 1991LSInfinity    The link state metric value indicating that the destination is    unreachable.  It is defined to be the binary value of all ones.  It    depends on the size of the metric field, which is 16 bits in router    links advertisements, and 24 bits in both summary and AS external    links advertisements.DefaultDestination    The Destination ID that indicates the default route.  This route is    used when no other matching routing table entry can be found.  The    default destination can only be advertised in AS external link    advertisements and in type 3 summary link advertisements for stub    areas.  Its value is the IP address 0.0.0.0.[Moy]                                                         [Page 165]

RFC 1247                     OSPF Version 2                    July 1991C. Configurable ConstantsThe OSPF protocol has quite a few configurable parameters.  Theseparameters are listed below.  They are grouped into general functionalcategories (area parameters, interface parameters, etc.).  Sample valuesare given for some of the parameters.Some parameter settings need to be consistent among groups of routers.For example, all routers in an area must agree on that area'sparameters, and all routers attached to a network must agree on thatnetwork's IP network number and mask.Some parameters may be determined by router algorithms outside of thisspecification (e.g., the address of a host connected to the router via aSLIP line).  From OSPF's point of view, these items are stillconfigurable.C.1 Global parametersIn general, a separate copy of the OSPF protocol is run for each area.Because of this, most configuration parameters are defined on a per-areabasis.  The few global configuration parameters are listed below.Router ID    This is a 32-bit number that uniquely identifies the router in the    Autonomous System.  One algorithm for Router ID assignment is to    choose the largest or smallest IP address assigned to the router.    If a router's OSPF Router ID is changed, the router's OSPF software    should be restarted before the new Router ID takes effect.TOS capability    This item indicates whether the router will calculate separate    routes based on TOS.  For more information, see Sections4.5 and    16.9.C.2 Area parametersAll routers belonging to an area must agree on that area'sconfiguration.  Disagreements between two routers will lead to aninability for adjacencies to form between them, with a resultinghindrance to the flow of routing protocol traffic.  The following itemsmust be configured for an area:[Moy]                                                         [Page 166]

RFC 1247                     OSPF Version 2                    July 1991Area ID    This is a 32-bit number that identifies the area.  The Area ID of 0    is reserved for the backbone.  If the area represents a subnetted    network, the IP network number of the subnetted network may be used    for the area ID.List of address ranges    An OSPF area is defined as a list of [IP address, mask] pairs.  Each    pair describes a range of IP addresses.  Networks and hosts are    assigned to an area depending on whether their addresses fall into    one of the area's defining address ranges.  Routers are viewed as    belonging to multiple areas, depending on their attached networks'    area membership.  Routing information is condensed at area    boundaries.  External to the area, a single route is advertised for    each address range.    As an example, suppose an IP subnetted network is to be its own OSPF    area.  The area would be configured as a single address range, whose    IP address is the address of the subnetted network, and whose mask    is the natural class A, B, or C internet mask.  A single route would    be advertised external to the area, describing the entire subnetted    network.Authentication type    Each  area  can  be  configured  for  a  separate  type  of    authentication.    See Appendix  E  for  a  discussion  of  the    defined authentication  types.External routing capability    Whether AS external advertisements will be flooded into/throughout    the area.  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, seeSection 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.  SeeSection 12.4.3 for more information.[Moy]                                                         [Page 167]

RFC 1247                     OSPF Version 2                    July 1991C.3 Router interface parametersSome of the configurable router interface parameters (such as IPinterface address and subnet mask) actually imply properties of theattached networks, and therefore must be consistent across all therouters attached to that network.  The parameters that must beconfigured for a router interface are:IP interface address    The IP protocol address for this interface.  This uniquely    identifies the router over the entire internet.  An IP address is    not required on serial lines.  Such a serial line is called    "unnumbered".IP interface mask    This  denotes  the  portion  of  the  IP  interface  address  that    identifies  the  attached  network.   This  is  often  referred  to    as  the subnet  mask.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's router links advertisement.  There may be    a separate cost for each IP Type of Service.  The interface output    cost(s) must always be greater than 0.RxmtInterval    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.  This should be well over the expected round-trip delay    between any two routers on the attached network.  The setting of    this value should be conservative or needless retransmissions will    result.  It will need to be larger on low speed serial lines and    virtual links.  Sample value for a local area network: 5 seconds.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 must have their age incremented by    this amount before transmission.  This value should take into    account the transmission and propagation delays for the interface.    It must be greater than 0.  Sample value for a local area network: 1    second.Router Priority    An 8-bit unsigned integer.  When two routers attached to a network[Moy]                                                         [Page 168]

RFC 1247                     OSPF Version 2                    July 1991    both attempt to become Designated Router, the one with the highest    Router Priority takes precedence.  If there is still a tie, the    router with the highest Router ID takes precedence.  A router whose    Router Priority is set to 0 is ineligible to become Designated    Router on the attached network.  Router Priority is only configured    for interfaces to multi-access networks.HelloInterval    The length of time, in seconds, between the Hello packets that the    router sends on the interface.  This value is advertised in the    router's Hello packets.  It must be the same for all routers    attached to a common network.  The smaller the hello interval, the    faster topological changes will be detected, but more routing    traffic will ensue.  Sample value for a X.25 PDN network: 30    seconds.  Sample value for a local area network: 10 seconds.RouterDeadInterval    The number of seconds that a router's Hellos have not been seen    before its neighbors declare the router down.  This is also    advertised in the router's Hello Packets in the DeadInt field.  This    should be some multiple of the HelloInterval (say 4).  This value    again must be the same for all routers attached to a common network.Authentication key    This configured data allows the authentication procedure to generate    and/or verify the authentication field in the OSPF header.  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.  There could be a separate password for each    network.C.4 Virtual link parametersVirtual links are used to restore/increase connectivity of the backbone.Virtual links may be configured between any pair of area border routershaving interfaces to a common (non-backbone) area.  The virtual linkappears as an unnumbered point-to-point link in the graph for thebackbone.  The virtual link must be configured in both of the areaborder routers.A virtual link appears in router links advertisements (for the backbone)as if it were a separate router interface to the backbone.  As such, ithas all of the parameters associated with a router interface (seeSection C.3).  Although a virtual link acts like an unnumbered point-to-point link, it does have an associated IP interface address.  Thisaddress is used as the IP source in protocol packets it sends along the[Moy]                                                         [Page 169]

RFC 1247                     OSPF Version 2                    July 1991virtual link, and is set dynamically during the routing table buildprocess.  Interface output cost is also set dynamically on virtual linksto be the cost of the intra-area path between the two routers.  Theparameter RxmtInterval must be configured, and should be well over theexpected round-trip delay between the two routers.  This may be hard toestimate for a virtual link.  It is better to err on the side of makingit too large.  Router Priority is not used on virtual links.A virtual link is defined by the following two configurable parameters:the Router ID of the virtual link's other endpoint, and the (non-backbone) area through which the virtual link runs (referred to as thevirtual link's transit area).  Virtual links cannot be configuredthrough stub areas.C.5 Non-broadcast, multi-access network parametersOSPF treats a non-broadcast, multi-access network much like it treats abroadcast network.  Since there many be many routers attached to thenetwork, a Designated Router is selected for the network.  ThisDesignated Router then originates a networks links advertisement, whichlists all routers attached to the non-broadcast network.However, due to the lack of broadcast capabilities, it is necessary touse configuration parameters in the Designated Router selection.  Theseparameters need only be configured in those routers that are themselveseligible to become Designated Router (i.e., those router's whose DRPriority for the network is non-zero):List of all other attached routers    The list of all other routers attached to the non-broadcast network.    Each router is listed by its IP interface address on the network.    Also, for each router listed, that router's eligibility to become    Designated Router must be defined.  When an interface to a non-    broadcast network comes up, the router sends Hello packets only to    those neighbors eligible to become Designated Router, until the    identity of the Designated Router is discovered.PollInterval    If a neighboring router has become inactive (hellos have not been    seen for RouterDeadInterval seconds), it may still be necessary to    send Hellos to the dead neighbor.  These Hellos will be sent at the    reduced rate PollInterval, which should be much larger than    HelloInterval.  Sample value for a PDN X.25 network: 2 minutes.[Moy]                                                         [Page 170]

RFC 1247                     OSPF Version 2                    July 1991C.6 Host route parametersHost routes are advertised in network links advertisements as stubnetworks with mask 0xffffffff.  They indicate either router interfacesto point-to-point networks, looped router interfaces, or IP hosts thatare directly connected to the router (e.g., via a SLIP line).  For eachhost directly connected to the router, the following items must beconfigured:Host IP address    The IP address of the host.Cost of link to host    The cost of sending a packet to the host, in terms of the link state    metric.  There may be multiple costs configured, one for each IP    TOS.  However, since the host probably has only a single connection    to the internet, the actual configured cost(s) in many cases is    unimportant (i.e., will have no effect on routing).[Moy]                                                         [Page 171]

RFC 1247                     OSPF Version 2                    July 1991D. Required StatisticsAn OSPF implementation must provide a minimum set of statisticsindicating the operational state of the protocol.  These statistics mustbe accessible to the user; this will probably be accomplished throughsome sort of network management interface.It is hoped that these statistics will aid in the debugging of theimplementation, and in the analysis of the protocol's performance.The statistics can be broken into two broad categories.  The firstconsists of what we will call logging messages.  These are messagesproduced in real time, with generally a single message produced as theresult of a single protocol event.  Such messages are also commonlyreferred to as traps.The second category will be referred to as cumulative statistics.  Theseare counters whose value have collected over time, such as the count oflink state retransmissions over the last hour.  Also falling into thiscategory are dumps of the various routing data structures.D.1 Logging messagesA logging message should be produced on every significant protocolevent.  The major events are listed below.  Most of these eventsindicate a topological change in the routing domain.  However, somenumber of logging messages can be expected even when the routing domainremains intact for long periods of time.  For example, link stateoriginations will still happen due to the link state refresh timerfiring.Any of the messages that refer to link state advertisements should printthe area associated with the advertisement.  There is no area associatedwith AS external link advertisements.The following list of logging messages indicate topological changes inthe routing domain:T1  The state of a router interface changes.  Interface state changes    are documented inSection 9.3.  In general, they will cause new link    state advertisements to be originated.  The logging message produced    should include the interface's IP address (or other name), interface    type (virtual link, etc.)  and old and new state values (as    documented inSection 9.1).[Moy]                                                         [Page 172]

RFC 1247                     OSPF Version 2                    July 1991T2  The state of a neighbor changes.  Neighbor state changes are    documented inSection 10.3.  The logging message produced should    include the neighbor IP address, and old and new state values.T3  The (Backup) Designated Router has changed on one of the attached    networks.  SeeSection 9.4.  The logging message produced should    include the network IP address, and the old and new (Backup)    Designated Routers.T4  The router is originating a new instance of a link state    advertisement.  The logging message produced should indicate the LS    type, Link State ID and Advertising Router associated with the    advertisement (seeSection 12.4).T5  The router has received a new instance of a link state    advertisement.  The router receives these in Link State Update    packets.  This will cause recalculation of the routing table.  The    logging message produced should indicate the advertisement's LS    type, Link State ID and Advertising Router.  The message should also    include the neighbor from whom the advertisement was received.T6  An entry in the routing table has changed (seeSection 11).  The    logging message produced should indicate the Destination type,    Destination ID, and the old and new paths to the destination.The following logging messages may indicate that there is a networkconfiguration error:C1  A received OSPF packet is rejected due to errors in its IP/OSPF    header.  The reasons for rejection are documented inSection 8.2.    They include OSPF checksum failure, authentication failure, and    inability to match the source with an active OSPF neighbor.  The    logging message produced should include the IP source and    destination addresses, the router ID in the OSPF header, and the    reason for the rejection.C2  An incoming Hello packet is rejected due to mismatches between the    Hello's parameters and those configured for the receiving interface    (seeSection 10.5).  This indicates a configuration problem on the    attached network.  The logging message should include the Hello's    source, the receiving interface, and the non-matching parameters.C3  An incoming Database Description packet, Link State Request Packet,    Link State Acknowledgment Packet or Link State Update packet is    rejected due to the source neighbor being in the wrong state (see    Sections10.6,10.7,13.7 , and 13 respectively).  This can be[Moy]                                                         [Page 173]

RFC 1247                     OSPF Version 2                    July 1991    normal when the identity of the network's Designated Router changes,    causing momentary disagreements over the validity of adjacencies.    The logging message should include the source neighbor, its state,    and the packet's type.C4  A Database Description packet has been retransmitted.  This may mean    that the value of RxmtInterval that has been configured for the    associated interface is too small.  The logging message should    include the neighbor to whom the packet is being sent.The following messages can be caused by packet transmission errors, orsoftware errors in an OSPF implementation:E1  The checksum in a received link state advertisement is incorrect.    The advertisement is discarded (seeSection 13).  The logging    message should include the advertisement's LS type, Link State ID    and Advertising Router (which may be incorrect).  The message should    also include the neighbor from whom the advertisement was received.E2  During the aging process, it is discovered that one of the link    state advertisements in the database has an incorrect checksum.    This indicates memory corruption or a software error in the router    itself.  The router should be dumped and restarted.The following messages are an indication that a router has restarted,losing track of its previous LS sequence number.  Should these messagescontinue, it may indicate the presence of duplicate Router IDs:R1  Two link state advertisements have been seen, whose LS type, Link    State ID, Advertising Router and LS sequence number are the same,    yet with differing LS checksums.  These are considered to be    different instances of the same advertisement.  The instance with    the larger checksum is accepted as more recent (seeSection 12.1.7,    13.1).  The logging message should include the LS type, Link State    ID, Advertising Router, LS sequence number and the two differing    checksums.R2  Two link state advertisements have been seen, whose LS type, Link    State ID, Advertising Router, LS sequence number and LS checksum are    the same, yet can be distinguished by their LS age fields.  This    means that one of the advertisement's LS age is MaxAge, or the two    LS age fields differ by more than MaxAgeDiff.  The logging message    should include the LS type, Link State ID, Advertising Router, LS    sequence number and the two differing ages.[Moy]                                                         [Page 174]

RFC 1247                     OSPF Version 2                    July 1991R3  The router has received an instance of one of its self-originated    advertisements, that is considered to be more recent.  This forces    the router to originate a new advertisement (seeSection 13.4).  The    logging message should include the advertisement's LS type, Link    State ID, and Advertising Router along with the neighbor from whom    the advertisement was received.R4  An acknowledgment has been received for an instance of an    advertisement that is not currently contained in the router's    database (seeSection 13.7).  The logging message should detail the    instance being acknowledged and the database copy (if any), along    with the neighbor from whom the acknowledgment was received.R5  An advertisement has been received through the flooding procedure    that is LESS recent the the router's current database copy (seeSection 13).  The logging message should include the received    advertisement's LS type, Link State ID, Advertising Router, LS    sequence number, LS age and LS checksum.  Also, the message should    display the neighbor from whom the advertisement was received.The following messages are indication of normal, yet infrequent protocolevents.  These messages will help in the interpretation of some of theabove messages:N1  The Link state refresh timer has fired for one of the router's    self-originated advertisements (seeSection 12.4).  A new instance    of the advertisement must be originated.  The message should include    the advertisement's LS type, Link State ID and Advertising Router.N2  One of the advertisements in the router's link state database has    aged to MaxAge (seeSection 14).  At this point, the advertisement    is no longer included in the routing table calculation, and is    reflooded.  The message should list the advertisement's LS type,    Link State ID and Advertising Router.N3  An advertisement of age MaxAge has been flushed from the router's    database.  This occurs after the advertisement has been acknowledged    by all adjacent neighbors.  The message should list the    advertisement's LS type, Link State ID and Advertising Router.D.2 Cumulative statisticsThese statistics display collections of the routing data structures.They should be able to be obtained interactively, through some kind ofnetwork management facility.[Moy]                                                         [Page 175]

RFC 1247                     OSPF Version 2                    July 1991All the following statistics displays, with the exception of the arealist, routing table and the AS external links, are specific to a singlearea.  As noted inSection 4, most OSPF protocol mechanisms work on eacharea separately.The following statistics displays should be available:(1) A list of all the areas attached to the router, along with the    authentication type to use for the area, the number of router    interfaces attaching to the area, and the total number of nets and    routers belonging to the area.    For example, consider the router RT3 pictured in Figure 15.  It has    interfaces to two separate areas, Area 1 and the backbone (Area 0).    Table 20 then indicates that the backbone is using a simple password    for authentication, and that Area 1 is not using any authentication.    The number of nets includes IP networks, subnets, and hosts (this is    the reason for 2 backbone nets -- they are the host routes    corresponding to the serial line between backbone routers RT6 and    RT10).                 Area ID   # ifcs   AuType   # nets   # routers                 ______________________________________________                 0         1        1        2        7                 1         2        0        4        4                      Table 20: Sample OSPF area display.(2) A list of all the router's interfaces to an area, along with their    addresses, output cost, current state, the (Backup) Designated    Router for the attached network, and the number of neighbors    currently associated with the interface.  Some number of these    neighbors will have become adjacent, the number of these is noted in    the display also.    Again consider router RT3 in Figure 15.  Table 21 below indicates    that RT4 has been selected as Designated Router for network N3, and    router RT1 has been selected as Backup.  Adjacencies have been    established to both of these routers.  There are no routers besides    RT3 attached to network N4, so it becomes DR, yet still advertises    the network as a stub in its router links advertisements.[Moy]                                                         [Page 176]

RFC 1247                     OSPF Version 2                    July 1991   Ifc IP address   state      cost   DR          Backup      # nbrs   # adjs   __________________________________________________________________________   192.1.1.3        DR other   1      192.1.1.4   192.1.1.1   3        2   192.1.4.3        DR         2      192.1.4.3   none        0        0                    Table 21: Sample OSPF interface display.(3) The list of neighbors associated with a particular interface.  Each    neighbor's IP address, router ID, state, and the length of the three    link state advertisement queues (seeSection 10) to the neighbor is    displayed.    Suppose router RT4 is the Designated Router for network N3, and    router RT1 is the Backup Designated router.  Suppose also that the    adjacency between router RT3 and RT1 has not yet fully formed.  The    display of router RT3's neighbors (associated with its interface to    network N3) may then look like Table 22.  The display indicates that    RT3 and RT1 are still in the database exchange procedure, Router RT3    has more Database Description packets to send to RT1, and RT1 has at    least one link state advertisement that RT3 doesn't.  Also, there is    a single link state advertisement that has been flooded, but not    acknowledged, to each neighbor that participates in the flooding    procedure (state >= Exchng).  (In the following examples we assume    that a router's Router ID is assigned to be its smallest IP    interface address).  Nbr IP address   Router ID   state    LS rxmt len   DB summ len   LS req len  ____________________________________________________________________________  192.1.1.1        192.1.1.1   Exchng   1             10            1  192.1.1.2        192.1.1.2   2-Way    0             0             0  192.1.1.4        192.1.1.4   Full     1             0             0                    Table 22: Sample OSPF neighbor display.(4) A list of the area's link state database.  This is the same in all    of the routers attached to the area.  It is composed of that area's    router links, network links, and summary links advertisements.    Also, the AS external link advertisements are a part of all the    areas' databases.[Moy]                                                         [Page 177]

RFC 1247                     OSPF Version 2                    July 1991    The link state database for Area 1 in Figure 15 might look like    Table 23 (compare this with Figure 7).  Assume the the Designated    Router for network N3 is router RT4, as above.  Both routers RT3 and    RT4 are originating summary link advertisements into Area 1, since    they are area border routers.  Routers RT5 and RT7 are AS external    routers.  Their location must be described in summary links    advertisements.  Also, their AS external link advertisements are    flooded throughout the entire AS.    Router RT3 can locate its self-originated advertisements by looking    for its own router ID (192.1.1.3) in advertisements' Advertising    Router fields.    The LS sequence number, LS age, and LS checksum fields indicate the    advertisement's instance.  Their values are stored in the    advertisement's link state header; we have not bothered to make up    values for the example.LS type   Link State ID   Advertising Router   LS seq no   LS age   LS checksum_______________________________________________________________________________1         192.1.1.1     192.1.1.1            *           *        *1         192.1.1.2     192.1.1.2            *           *        *1         192.1.1.3     192.1.1.3            *           *        *1         192.1.1.4     192.1.1.4            *           *        *_______________________________________________________________________________2         192.1.1.4     192.1.1.4            *           *        *_______________________________________________________________________________3         Ia,Ib         192.1.1.3            *           *        *3         N6            192.1.1.3            *           *        *3         N7            192.1.1.3            *           *        *3         N8            192.1.1.3            *           *        *3         N9-N11,H1     192.1.1.3            *           *        *3         Ia,Ib         192.1.1.4            *           *        *3         N6            192.1.1.4            *           *        *3         N7            192.1.1.4            *           *        *3         N8            192.1.1.4            *           *        *3         N9-N11,H1     192.1.1.4            *           *        *4         RT5           192.1.1.3            *           *        *4         RT7           192.1.1.3            *           *        *4         RT5           192.1.1.4            *           *        *4         RT7           192.1.1.4            *           *        *_______________________________________________________________________________4         N12           RT5's ID             *           *        *4         N13           RT5's ID             *           *        *4         N14           RT5's ID             *           *        *4         N12           RT7's ID             *           *        *[Moy]                                                         [Page 178]

RFC 1247                     OSPF Version 2                    July 1991LS type   Link State ID   Advertising Router   LS seq no   LS age   LS checksum_______________________________________________________________________________4         N15           RT7's ID             *           *        *             Table 23: Sample OSPF link state database display.(5) The contents of any particular link state advertisement.  For    example, a listing of the router links advertisement for Area 1,    with LS type = 1 and Link State ID = 192.1.1.3 is shown inSection12.4.1.(6) A listing of the entire routing table.  Several examples are shown    inSection 11.  The routing table is calculated from the combined    databases of each attached area (seeSection 16).  It may be    desirable to sort the routing table by Type of Service, or by    destination, or a combination of the two.[Moy]                                                         [Page 179]

RFC 1247                     OSPF Version 2                    July 1991E. AuthenticationAll OSPF protocol exchanges are authenticated.  The OSPF packet header(see Section A.3.1) includes an authentication type field, and 64-bitsof data for use by the appropriate authentication scheme (determined bythe type field).The authentication type is configurable on a per-area basis.  Additionalauthentication data is configurable on a per-interface basis.  Forexample, if an area uses a simple password scheme for authentication, aseparate password may be configured for each network contained in thearea.Authentication types 0 and 1 are defined by this specification.  Allother authentication types are reserved for definition by the IANA(iana@ISI.EDU).  The current list of authentication types is describedbelow in Table 24.      AuType       Description      _______________________________________________________________      0            No authentication      1            Simple password      All others   Reserved for assignment by the IANA (iana@ISI.EDU)                    Table 24: OSPF authentication types.E.1 Autype 0 -- No authenticationUse of this authentication type means that routing exchanges in the areaare not authenticated.  The 64-bit field in the OSPF header can containanything; it is not examined on packet reception.E.2 Autype 1 -- Simple passwordUsing this authentication type, a 64-bit field is configured on a per-network basis.  All packets sent on a particular network must have thisconfigured value in their OSPF header 64-bit authentication field.  Thisessentially serves as a "clear" 64-bit password.This guards against routers inadvertently coming up in the area.  Theymust first be configured with their attached networks' passwords beforethey can join the routing domain.[Moy]                                                         [Page 180]

RFC 1247                     OSPF Version 2                    July 1991F. Version 1 differencesThis section documents the changes between OSPF version 1 and OSPFversion 2.  The impetus for these changes derives from comments receivedonRFC 1131 and recent field experience with the OSPF protocol.Unfortunately, the changes are not backward-compatible.  For thatreason, OSPF version 1 will not interoperate with OSPF version 2.However, the changes are small in scope and should not greatly affectany existing implementations.  In addition, some of the proposed changesshould enable future protocol additions to be made in a backward-compatible manner (see Section F.4).F.1 Protocol EnhancementsThe following enhancements were made to the OSPF protocol.F.1.1 Stub area supportIn many Autonomous Systems, the majority of the OSPF link state databaseconsists of AS external advertisements.  In these Autonomous Systems,some OSPF areas may be organized in such a way that externaladvertisements can be safely ignored, enabling a reduction of the area'sdatabase size.  This applies to OSPF areas where there is only a singleexit/entry that is used by all externally addressed packets, or to caseswhere some sub-optimality of external routing is acceptable.Therefore, an OSPF area configuration option has been added (seeSections3.6 and C.2) allowing the import of external advertisements tobe disabled for an area.  When this option is enabled, no AS externaladvertisements will be flooded into the area (Sections13,13.3 and10.3).  Instead, within the area all data traffic to externaldestinations will follow a (per-area) default route.  These areas arecalled "stub" areas.To implement this, all area border routers attached to stub areas willoriginate a default summary link advertisement for the area (Section12.4.3).  This will direct all internal routers to an area border routerwhen forwarding externally addressed packets.  In addition, to ensurethat stub areas are configured consistently, an Options field has beenadded to OSPF Hello packets (Sections A.2 and A.3.2).  A bit is reset inthe Options field indicating that the attached area is a stub area(Section 9.5).  A router will not accept a neighbor's hellos unless theyboth agree on the area's ability to process AS external advertisements(Section 10.5).  In this way, a system administrator will be able todiscover incorrectly configured routers, and data traffic will be routedaround them (in order to avoid potential looping situations) until their[Moy]                                                         [Page 181]

RFC 1247                     OSPF Version 2                    July 1991configuration can be repaired.F.1.2 Optional TOS supportIn OSPF there is conceptually a separate routing table for each TOS; thecalculations detailed in steps 1-5 ofSection 16 must be done separatelyfor each TOS.  (Note however that link and summary costs need not bespecified separately for each TOS; costs for unspecified TOS valuesdefault to the cost of TOS 0).In version 1 of the OSPF specification, all OSPF routers were requiredto route based on TOS.  However, producing a separate routing table foreach TOS may prove costly, both in terms of memory and processorresources.  For this reason, version 2 allows the system administratorto configure routers to calculate/use only a single routing table (theTOS 0 table).  When this is done, some traffic may take non-optimalroutes.  But all packets will still be delivered, and routing willremain loop free (seeSection 2.4).In order to avoid routing loops, a router (router X) using a singletable must communicate this information to its peers.  This is done byresetting the new TOS-capable bit in the router X's router linksadvertisement (Section 12.4.1).  Then, when its peers perform theDijkstra calculation (Section 16.1) for non-zero TOS values, they willomit router X from the calculation.  In effect, an attempt will be madeto bypass router X when forwarding non-zero TOS traffic.  Summary linkand AS external link advertisements can also indicate their non-availability for non-zero TOS traffic (Sections12.4.3 and12.4.4).The result may be that no route can be found for some non-zero value ofTOS.  When this happens, the packet is routed along the TOS 0 routeinstead (Section 11.1).It is still mandatory for all OSPF implementations to be able toconstruct separate routing tables for each TOS value, if desired by thesystem administrator.F.1.3 Preventing external extra-hopsIn some cases, version 1 of the OSPF specification will introduceextra-hops when calculating routes to external destinations.  This isbecause it is implicit in the format of AS external advertisements thatpackets should be forwarded through the advertising router.  However,consider the situation where multiple OSPF routers share a LAN with anexternal router (call it router Y) , and only one OSPF router (call itrouter X) exchanges routing information with Y.  The OSPF routers on the[Moy]                                                         [Page 182]

RFC 1247                     OSPF Version 2                    July 1991LAN other than X will forward packets destined for Y and beyond throughX, generating an extra hop (seeSection 2.2).To fix this, a new field has been added to AS external advertisements.This field (called the forwarding address) will indicate the routeraddress to which packets should be forwarded (Section 12.4.4).  In theabove example, router X will put Y's IP address into this field.  If thefield is 0, packets are (as before) forwarded to the originator of theadvertisement.  A different forwarding address can be specified for eachTOS value.Whenever possible, this new field should be set to 0.  This is becausesetting it to an actual router address incurs additional cost during therouting table build process (Section 16.4).Besides preventing extra-hops, there are two other applications for thisfield.  The first is for use by "route servers".  Using the forwardingaddress, a router in the middle of the Autonomous System can gatherexternal routing information and originate AS external advertisementsthat specify the correct exit route to use for each external destination(Section 2.2).The other application possibly enables the reduction of the number of ASexternal advertisements that need be imported.  Suppose in the exampleat the beginning of this section that there are two routers (X and Z)exchanging EGP information with the non-OSPF router Y.  It is thenlikely that both X and Z will originate the same set of external routes.Two AS external advertisements that specify the same (non-zero)forwarding address, destination and cost are obviously functionallyequivalent, regardless of their originators (advertising routers).  TheOSPF specification dictates that the advertisement originated by therouter with the largest Router ID will always be used.  This allows theother router to flush its equivalent advertisement (Section 12.4.4).F.2 Corrected problemsThe following problems in OSPF version 1 have been corrected in version2.F.2.1 LS sequence number space changesThe LS sequence number space has been changed from version 1's lollipopshape to a linear sequence space (Section 12.1.6).  Sequence numberswill now be compared as signed 32-bit integers.  Link stateadvertisements having larger sequence numbers will be considered morerecent.  The sequence number space will still begin at (-N+1) (where N =[Moy]                                                         [Page 183]

RFC 1247                     OSPF Version 2                    July 19912**31).  The value of -N remains reserved.  The LS sequence number ofsuccessive instances of an advertisement will continue to be incrementeduntil it reaches the maximum possible value: N-1.  At this point, when anew instance of the advertisement must be originated (due either totopological change of the expiration of the LS refresh timer) thecurrent instance must first be "prematurely aged".There will be a new section discussing premature aging (Section 14.1).This is a method for flushing a link state advertisement from therouting domain: the advertisement's age is set to MaxAge andadvertisement is reflooded just as if it were a newly receivedadvertisement.  As soon as the new flooding is acknowledged by all ofthe router's adjacent neighbors, the advertisement is flushed from thedatabase.Premature aging can also be used when, for example, a previouslyadvertised external route is no longer reachable.  In this circumstance,premature aging is preferable to the alternative, which is to originatea new advertisement for the destination specifying a metric ofLSInfinity.A router may only prematurely age its own (self-originated) link stateadvertisements.  These are the link state advertisements having therouter's own OSPF router ID in the Advertising Router field.F.2.2 Flooding of unexpected MaxAge advertisementsVersion 1 of the OSPF omitted the handling of a special case in theflooding procedure: the reception of a MaxAge advertisement that has nodatabase instance.  A paragraph has been added toSection 13 to dealwith this occurrence.  Without this paragraph, retransmissions of MaxAgeadvertisements could possibly delay their being flushed from the routingdomain.F.2.3 Virtual links and address rangesWhen summarizing information into a virtual link's transit area, version2 of the OSPF specification prohibits the collapsing of multiplebackbone IP networks/subnets into a single summary link.  Thisrestriction has been added to deal with certain anomalous OSPF areaconfigurations.  See Sections15 and12.4.3 for more information.[Moy]                                                         [Page 184]

RFC 1247                     OSPF Version 2                    July 1991F.2.4 Routing table lookup explainedWhen forwarding an IP data packet, a router looks up the packet's IPdestination in the routing table.  This determines the packet's nexthop.  A new section (Section 11.1) has been added describing the routingtable lookup (instead of just specifying a "best match").  This sectionclarifies OSPF's four level routing hierarchy (i.e., intra-area, inter-area, external type 1 and external type 2 routes).  It also specifiesthe effect of TOS on routing.F.2.5 Sending Link State Request packetsOSPF Version 2 eases the restrictions on the sending of Link StateRequest packets.  Link State Request packets can now be sent to aneighboring router before a complete set of Database Description packetshave been exchanged.  This enables a more efficient use of a router'smemory resources; an OSPF version 2 implementation may limit the size ofthe neighbor Link state request lists.  See Sections10.9,10.7 and10.3for more details.F.2.6 Changes to the Database description processThe specification has been modified to ensure that, when two routers aresynchronizing their databases during the Database Description process,none of the component link state advertisements can have their sequencenumbers decrease.  A link state advertisement's sequence numberdecreases when it is flushed from the routing domain via premature-aging, and then reoriginated with the smallest sequence number0x80000001 (seeSection 14.1).  So the specification now dictates thatan advertisement cannot be flushed from a router's database until botha) it no longer appears on any neighbor Link State Retransmission listsand b) none of the router's neighbors are in states Exchange or Loading.See Sections13 (step 4c) and 14.1 for more details.In addition, a new step has been added to the flooding procedure(Section 13) in order to make the Database Description process morerobust.  This step detects when a neighbor lists one instance of anadvertisement in its Database Description packets, but responds to LinkState Request packets by sending another (earlier) instance.  Thisbehavior now causes the event BadLSReq to be generated, which restartsthe Database Description process with the neighbor.  In OSPF version 1,the neighbor event BadLSReq erroneously did not restart the DatabaseDescription process.[Moy]                                                         [Page 185]

RFC 1247                     OSPF Version 2                    July 1991F.2.7 Receiving OSPF Hello packetsThe section detailing the receive processing of OSPF Hello packets(Section 10.5) has been modified to include the generation of theneighbor Backup Seen event.  In addition, the section detailing theDesignated Router election algorithm (Section 9.4) has been modified toinclude the algorithm's initial state.F.2.8 Network mask defined for default routeThe network mask for the default route, when it appears as thedestination in either an AS external link advertisement or in a summarylink advertisement, has been set to 0.0.0.0.  See Sections A.4.4 andA.4.5 for more details.F.2.9 Rate limit imposed on floodingWhen an advertisement is installed in the link state database, it istimestamped.  The flooding procedure is then not allowed to install anew instance of the advertisement until MinLSInterval seconds haveelapsed.  This enforces a rate limit on the flooding procedure; a newinstance can be flooded only once every MinLSInterval seconds.  Thisguards against routers that disregard the limit on self-originatedadvertisements (already present in OSPF version 1) of one originationevery MinLSInterval seconds.  For more information, seeSection 13.F.3 Packet format changesThe following changes have been made to the format of OSPF packets andlink state advertisements.  Some of these changes were required tosupport the added functionality listed above.  Other changes were madeto further simplify the parsing of OSPF packets.F.3.1 Adding a Capability bitfieldTo support the new "stub area" and "optional TOS" features, a bitfieldlisting protocol capabilities has been added to the Hello packet,Database Description packet and all link state advertisements.  Whenused in Hello packets, this allows a router to reject a neighbor becauseof a capability mismatch.  Alternatively, when capabilities areexchanged in Database Description packets a router can choose not toforward certain link state advertisements to a neighbor because of itsreduced functionality.  Lastly, listing capabilities in link stateadvertisements allows routers to route traffic around reduced[Moy]                                                         [Page 186]

RFC 1247                     OSPF Version 2                    July 1991functionality router, by excluding them from parts of the routing tablecalculation.  See Section A.2 for more details.F.3.2 Packet simplificationTo simplify the format of Database Description packets and Link StateAcknowledgment packets, their description of link state advertisementshas been modified.  Each advertisement is now be described by its 20-byte link state header (see Section A.4).  This does not consume anyadditional space in the packets.  The one additional piece ofinformation that will be present is the LS length.  However, this fieldneed not be used when processing the Database Description and Link StateAcknowledgment packets.F.3.3 Adding forwarding addresses to AS external advertisementsAs discussed in Section F.1.3, a forwarding address field has been addedto the AS external advertisement.F.3.4 Labelling of virtual linksVirtual links will be labelled as such in router links advertisements.This separates virtual links from unnumbered point-to-point links,allowing all backbone routers to discover whether any virtual links arein use.  SeeSection 12.4.1 for more details.F.3.5 TOS costs orderedWhen a link state advertisement specifies a separate cost depending onTOS, these costs must be ordered by increasing TOS value.  For example,the cost for TOS 16 must always follow the cost for TOS 8.F.3.6 OSPF's TOS encoding redefinedThe way that OSPF encodes TOS in its link state advertisements has beenredefined in version 2. OSPF's encoding of the Delay (D), Throughput (T)and Reliability (R) TOS flags defined by [RFC 791] is described inSection 12.3.[Moy]                                                         [Page 187]

RFC 1247                     OSPF Version 2                    July 1991F.4 Backward-compatibility provisionsAdditional functionality will probably be added to OSPF in the future.One example of this is a multicast routing capability, which iscurrently under development.  In order to be able to add such featuresin a backward-compatible manner, the following provisions have been madein the OSPF specification.New capabilities will probably involve the introduction of new linkstate advertisements.  If a router receives a link state advertisementof unknown type during the flooding procedure, the advertisement issimply ignored (Section 13.  The router should not attempt to furtherflood the advertisement, nor acknowledge it.  The advertisement shouldnot be installed into the link state database.  If the router receivesan advertisement of unknown type during the Database Descriptionprocess, this is an error (see Sections10.6 and10.3).  The DatabaseDescription process is then restarted.There is also an Options field in both the Hello packets, DatabaseDescription packets and the link state advertisement headers.Unrecognized capabilities found in these places should be ignored, andshould not affect the normal processing of protocol packets/link stateadvertisements (see Sections10.5 and10.6).  Routers will originatetheir Hello packets, Database Description packets and link stateadvertisements with unrecognized capabilities set to 0 (see Sections9.5,10.8 and12.1.2).[Moy]                                                         [Page 188]

RFC 1247                     OSPF Version 2                    July 1991Security ConsiderationsAll OSPF protocol exchanges are authenticated. This is accomplishedthrough authentication fields contained in the OSPF packet header. Formore information, see Sections8.1,8.2, andAppendix E.Author's AddressJohn MoyProteon, Inc.2 Technology DriveWestborough, MA 01581Phone: (508) 898-2800EMail: jmoy@proteon.com[Moy]                                                         [Page 189]