10.3. The Neighbor state machine A detailed description of the neighbor state changes follows. Each state change is invoked by an event (Section 10.2). This event may produce different effects, depending on the current state of the neighbor. For this reason, the state machine below is organized by current neighbor state and received event. Each entry in the state machine describes the resulting new neighbor state and the required set of additional actions.
When a neighbor's state changes, it may be necessary to rerun the Designated Router election algorithm. This is determined by whether the interface NeighborChange event is generated (see Section 9.2). Also, if the Interface is in DR state (the router is itself Designated Router), changes in neighbor state may cause a new network-LSA to be originated (see Section 12.4). When the neighbor state machine needs to invoke the interface state machine, it should be done as a scheduled task (see Section 4.4). This simplifies things, by ensuring that neither state machine will be executed recursively. State(s): Down Event: Start New state: Attempt Action: Send an Hello Packet to the neighbor (this neighbor is always associated with an NBMA 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: HelloReceived New state: Init Action: Restart the Inactivity Timer for the neighbor, since the neighbor has now been heard from. State(s): Down Event: HelloReceived New 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: HelloReceived New 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-WayReceived New state: Depends upon action routine. Action: Determine whether an adjacency should be established with the neighbor (see Section 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 DD sequence number in the neighbor data structure. If this is the first time that an adjacency has been attempted, the DD 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 (see Section 10.8). State(s): ExStart Event: NegotiationDone New 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-LSAs, network-LSAs and summary-LSAs contained in the area structure, along with the AS-external-
LSAs contained in the global structure. AS- external-LSAs are omitted from a virtual neighbor's Database summary list. AS-external-LSAs are omitted from the Database summary list if the area has been configured as a stub (see Section 3.6). LSAs 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 DD 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 Sections 10.8 and 10.6. State(s): Exchange Event: ExchangeDone New 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 (see Section 10.9). These are requests for the neighbor's more recent LSAs (which were discovered but not yet received in the Exchange state). These LSAs are listed in the Link state request list associated with the neighbor. State(s): Loading Event: Loading Done New state: Full 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 (see Section 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-WayReceived. 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 LSAs. State(s): Exchange or greater Event: SeqNumberMismatch New 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 LSAs. Then the router increments the DD sequence number in the neighbor data structure, 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 (see Section 10.8). State(s): Exchange or greater Event: BadLSReq New 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: KillNbr New state: Down Action: The Link state retransmission list, Database summary list and Link state request list are cleared of LSAs. Also, the Inactivity Timer is disabled. State(s): Any state Event: LLDown New state: Down Action: The Link state retransmission list, Database summary list and Link state request list are cleared of LSAs. Also, the Inactivity Timer is disabled.
State(s): Any state Event: InactivityTimer New state: Down Action: The Link state retransmission list, Database summary list and Link state request list are cleared of LSAs. State(s): 2-Way or greater Event: 1-WayReceived New state: Init Action: The Link state retransmission list, Database summary list and Link state request list are cleared of LSAs. State(s): 2-Way or greater Event: 2-WayReceived New state: No state change. Action: No action required. State(s): Init Event: 1-WayReceived New state: No state change. Action: No action required. 10.4. Whether to become adjacent Adjacencies are established with some subset of the router's neighbors. Routers connected by point-to-point networks, Point-to- MultiPoint networks and virtual links always become adjacent. On broadcast and NBMA networks, all routers become adjacent to both the Designated Router and the Backup Designated Router.
The adjacency-forming decision occurs in two places in the neighbor state machine. First, when bidirectional communication is initially established with the neighbor, and secondly, when the identity of the attached network's (Backup) Designated Router changes. If the decision is made to not attempt an adjacency, the state of the neighbor communication stops at 2-Way. An adjacency should be established with a bidirectional neighbor when at least one of the following conditions holds: o The underlying network type is point-to-point o The underlying network type is Point-to-MultiPoint o The underlying network type is virtual link o The router itself is the Designated Router o The router itself is the Backup Designated Router o The neighboring router is the Designated Router o The neighboring router is the Backup Designated Router 10.5. Receiving Hello Packets This section explains the detailed processing of a received Hello Packet. (See Section A.3.2 for the format of Hello packets.) The generic input processing of OSPF packets will have checked the validity of the IP header and the OSPF packet header. Next, the values of the Network Mask, HelloInterval, and RouterDeadInterval fields in the received Hello packet must be checked against the values configured for the receiving interface. Any mismatch causes processing to stop and the packet to be dropped. In other words, the above fields are really describing the attached network's configuration. However, there is one exception to the above rule: on point-to-point networks and on virtual links, the Network Mask in the received Hello Packet should be ignored. The receiving interface attaches to a single OSPF area (this could be the backbone). The setting of the E-bit found in the Hello Packet's Options field must match this area's ExternalRoutingCapability. If AS-external-LSAs are not flooded into/throughout the area (i.e, the area is a "stub") the E-bit must be clear in received Hello Packets, otherwise the E-bit must be set. A mismatch causes processing to stop and the packet to be dropped. The setting of the rest of the bits in the Hello Packet's Options field should be ignored.
At this point, an attempt is made to match the source of the Hello Packet to one of the receiving interface's neighbors. If the receiving interface connects to a broadcast, Point-to-MultiPoint or NBMA network the source is identified by the IP source address found in the Hello's IP header. If the receiving interface connects to a point-to-point link or a virtual link, the source is identified by the Router ID found in the Hello's OSPF packet header. The interface's current list of neighbors is contained in the interface's data structure. If a matching neighbor structure cannot be found, (i.e., this is the first time the neighbor has been detected), one is created. The initial state of a newly created neighbor is set to Down. When receiving an Hello Packet from a neighbor on a broadcast, Point-to-MultiPoint or NBMA network, set the neighbor structure's Neighbor ID equal to the Router ID found in the packet's OSPF header. When receiving an Hello on a point-to-point network (but not on a virtual link) set the neighbor structure's Neighbor IP address to the packet's IP source address. Now the rest of the Hello Packet is examined, generating events to be given to the neighbor and interface state machines. These state machines are specified either to be executed or scheduled (see Section 4.4). For example, by specifying below that the neighbor state machine be executed in line, several neighbor state transitions may be effected by a single received Hello: o Each Hello Packet causes the neighbor state machine to be executed with the event HelloReceived. 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- WayReceived. Otherwise, the neighbor state machine should be executed with the event 1-WayReceived, 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 updated 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 Neighbors' Designated Router item in the neighbor structure is updated accordingly. o 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 Neighbor's Backup Designated Router item in the neighbor structure is updated accordingly. On NBMA networks, receipt of an Hello Packet may also cause an Hello Packet to be sent back to the neighbor in response. See Section 9.5.1 for more details. 10.6. Receiving Database Description Packets This section explains the detailed processing of a received Database Description Packet. The incoming Database Description Packet has already been associated with a neighbor and receiving interface by the generic input packet processing (Section 8.2). Whether the Database Description packet should be accepted, and if so, how it should be further processed depends upon the neighbor state. If a Database Description packet is accepted, the following packet fields should be saved in the corresponding neighbor data structure under "last received Database Description packet": the packet's initialize(I), more (M) and master(MS) bits, Options field, and DD sequence number. If these fields are set identically in two consecutive Database Description packets received from the neighbor, the second Database Description packet is considered to be a "duplicate" in the processing described below.
If the Interface MTU field in the Database Description packet indicates an IP datagram size that is larger than the router can accept on the receiving interface without fragmentation, the Database Description packet is rejected. Otherwise, if the neighbor state is: Down The packet should be rejected. Attempt The packet should be rejected. Init The neighbor state machine should be executed with the event 2- WayReceived. This causes an immediate state change to either state 2-Way or state ExStart. If the new state is ExStart, the processing of the current packet should then continue in this new state by falling through to case ExStart below. 2-Way The packet should be ignored. Database Description Packets are used only for the purpose of bringing up adjacencies. 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 neighbor data structure's DD sequence number to that specified by the master. o The initialize(I) and master(MS) bits are off, the packet's DD sequence number equals the neighbor data structure's DD 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 Duplicate Database Description packets are discarded by the master, and cause the slave to retransmit the last Database Description packet that it had sent. Otherwise (the packet is not a duplicate): o If the state of the MS-bit is inconsistent with the master/slave state of the connection, generate the neighbor event SeqNumberMismatch and stop processing the packet. o If the initialize(I) bit is set, generate the neighbor event SeqNumberMismatch 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 SeqNumberMismatch and stop processing the packet. o Database Description packets must be processed in sequence, as indicated by the packets' DD sequence numbers. If the router is master, the next packet received should have DD sequence number equal to the DD sequence number in the neighbor data structure. If the router is slave, the next packet received should have DD sequence number equal to one more than the DD sequence number stored in the neighbor data structure. In either case, if the packet is the next in sequence it should be accepted and its contents processed as specified below. o Else, generate the neighbor event SeqNumberMismatch and stop processing the packet. Loading or Full In this state, the router has sent and received an entire sequence of Database Description Packets. 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 Neighbor Options field). Any other packets received, including the reception of a packet with the Initialize(I) bit set, should generate the neighbor event SeqNumberMismatch. Duplicates should be discarded by the master. The slave must respond to duplicates by repeating the last Database Description packet that it had sent.
When the router accepts a received Database Description Packet as the next in sequence the packet contents are processed as follows. For each LSA listed, the LSA's LS type is checked for validity. If the LS type is unknown (e.g., not one of the LS types 1-5 defined by this specification), or if this is an AS-external-LSA (LS type = 5) and the neighbor is associated with a stub area, generate the neighbor event SeqNumberMismatch and stop processing the packet. Otherwise, the router looks up the LSA in its database to see whether it also has an instance of the LSA. If it does not, or if the database copy is less recent (see Section 13.1), the LSA is put on the Link state request list so that it can be requested (immediately or at some later time) in Link State Request Packets. When the router accepts a received Database Description Packet as the next in sequence, it also performs the following actions, depending on whether it is master or slave: Master Increments the DD sequence number in the neighbor data structure. If the router has already sent its entire sequence of Database Description Packets, and the just accepted packet has the more bit (M) set to 0, the neighbor event ExchangeDone is generated. Otherwise, it should send a new Database Description to the slave. Slave Sets the DD sequence number in the neighbor data structure to the DD sequence number appearing in the received packet. The slave must send a Database Description Packet in reply. If the received packet has the more bit (M) set to 0, and the packet to be sent by the slave will also have the M-bit set to 0, the neighbor event ExchangeDone is generated. Note that the slave always generates this event before the master. 10.7. Receiving Link State Request Packets This section explains the detailed processing of received Link State Request packets. Received Link State Request Packets specify a list of LSAs that the neighbor wishes to receive. Link State Request Packets should be accepted when the neighbor is in states Exchange, Loading, or Full. In all other states Link State Request Packets should be ignored.
Each LSA specified in the Link State Request packet should be located in the router's database, and copied into Link State Update packets for transmission to the neighbor. These LSAs should NOT be placed on the Link state retransmission list for the neighbor. If an LSA cannot be found in the database, something has gone wrong with the Database Exchange process, and neighbor event BadLSReq should be generated. 10.8. Sending Database Description Packets This section describes how Database Description Packets are sent to a neighbor. The Database Description packet's Interface MTU field is set to the size of the largest IP datagram that can be sent out the sending interface, without fragmentation. Common MTUs in use in the Internet can be found in Table 7-1 of [Ref22]. Interface MTU should be set to 0 in Database Description packets sent over virtual links. The router's optional OSPF capabilities (see Section 4.5) are transmitted to the neighbor in the Options field of the Database Description packet. The router should maintain the same set of optional capabilities throughout the Database Exchange and flooding procedures. If for some reason the router's optional capabilities change, the Database Exchange procedure should be restarted by reverting to neighbor state ExStart. One optional capability is defined in this specification (see Sections 4.5 and A.2). The E-bit should be set if and only if the attached network belongs to a non- stub area. Unrecognized bits in the Options field should be set to zero. The sending of Database Description packets depends on the neighbor's state. In state ExStart the router sends empty Database Description packets, 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 contain summaries of the link state information contained in the router's database. Each LSA in the area's link-state database (at the time the neighbor transitions into Exchange state) is listed in the neighbor Database summary list. Each new Database Description Packet copies its DD sequence number from the neighbor data structure and then describes the current top of the Database summary list. Items are removed from the Database summary list when the previous packet is acknowledged. In state Exchange, the determination of when to send a Database Description packet depends on whether the router is master or slave:
Master Database Description packets are sent when either a) the slave acknowledges the previous Database Description packet by echoing the DD sequence number or b) RxmtInterval seconds elapse without an acknowledgment, in which case the previous Database Description packet is retransmitted. Slave Database Description packets are sent only in response to Database Description packets received from the master. If the Database Description packet received from the master is new, a new Database Description packet is sent, otherwise the previous Database Description packet is resent. In states Loading and Full the slave must resend its last Database Description packet in response to duplicate Database Description packets received from the master. For this reason the slave must wait RouterDeadInterval seconds before freeing the last Database Description packet. Reception of a Database Description packet from the master after this interval will generate a SeqNumberMismatch neighbor event. 10.9. Sending Link State Request Packets In neighbor states Exchange or Loading, the Link state request list contains a list of those LSAs that need to be obtained from the neighbor. To request these LSAs, a router sends 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 State Update packet(s), the Link state request list is truncated and a new Link State Request packet is sent. This process continues until the Link state request list becomes empty. Unsatisfied Link State Request packets are retransmitted at intervals of RxmtInterval. There should be at most one Link State Request packet outstanding at any one time. When the Link state request list becomes empty, and the neighbor state is Loading (i.e., a complete sequence of Database Description packets has been sent to and received from the neighbor), the Loading Done neighbor event is generated.
10.10. An Example Figure 14 shows an example of an adjacency forming. Routers RT1 and RT2 are both connected to a broadcast network. It is assumed that RT2 is the Designated Router for the network, and that RT2 has a higher Router ID than Router RT1. The neighbor state changes realized by each router are listed on the sides of the figure. At the beginning of Figure 14, Router RT1's interface to the network becomes operational. It begins sending Hello Packets, although it doesn't know the identity of the Designated Router or of any other neighboring routers. Router RT2 hears this hello (moving the neighbor to Init state), and in its next Hello Packet indicates that it is itself the Designated Router and that it has heard Hello Packets from RT1. This in turn causes RT1 to 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 is indeed the master (because of RT2's higher Router ID), RT1 transitions to slave state and adopts its neighbor's DD sequence number. Database Description packets are then exchanged, with polls coming from the master (RT2) and responses from the slave (RT1). This sequence of Database Description Packets ends when both the poll and associated response has the M-bit off. In this example, it is assumed that RT2 has a completely up to date database. In that case, RT2 goes immediately into Full state. RT1 will go into Full state after updating the necessary parts of its database. This is done by sending Link State Request Packets, and receiving Link State Update Packets in response. Note that, while RT1 has waited until a complete set of Database Description Packets has been received (from RT2) before sending any Link State Request Packets, this need not be the case. RT1 could have interleaved the sending of Link State Request Packets with the reception of Database Description Packets.
+---+ +---+ |RT1| |RT2| +---+ +---+ Down Down Hello(DR=0,seen=0) ------------------------------> Hello (DR=RT2,seen=RT1,...) Init <------------------------------ ExStart D-D (Seq=x,I,M,Master) ------------------------------> D-D (Seq=y,I,M,Master) ExStart <------------------------------ Exchange D-D (Seq=y,M,Slave) ------------------------------> D-D (Seq=y+1,M,Master) Exchange <------------------------------ D-D (Seq=y+1,M,Slave) ------------------------------> ... ... ... D-D (Seq=y+n, Master) <------------------------------ D-D (Seq=y+n, Slave) Loading ------------------------------> LS Request Full ------------------------------> LS Update <------------------------------ LS Request ------------------------------> LS Update <------------------------------ Full Figure 14: An adjacency bring-up example
11. The Routing Table Structure The routing table data structure contains all the information necessary to forward an IP data packet toward its destination. Each routing table entry describes the collection of best paths to a particular destination. When forwarding an IP data packet, the routing table entry providing the best match for the packet's IP destination is located. The matching routing table entry then provides the next hop towards the packet's destination. OSPF also provides for the existence of a default route (Destination ID = DefaultDestination, Address Mask = 0x00000000). When the default route exists, it matches all IP destinations (although any other matching entry is a better match). Finding the routing table entry that best matches an IP destination is further described in Section 11.1. There is a single routing table in each router. Two sample routing tables are described in Sections 11.2 and 11.3. The building of the routing table is discussed in Section 16. The rest of this section defines the fields found in a routing table entry. The first set of fields describes the routing table entry's destination. Destination Type Destination type is either "network" or "router". Only network entries are actually used when forwarding IP data traffic. Router routing table entries are used solely as intermediate steps in the routing table build process. A network is a range of IP addresses, to which IP data traffic may be forwarded. This includes IP networks (class A, B, or C), IP subnets, IP supernets and single IP hosts. The default route also falls into this category. Router entries are kept for area border routers and AS boundary routers. Routing table entries for area border routers are used when calculating the inter-area routes (see Section 16.2), and when maintaining configured virtual links (see Section 15). Routing table entries for AS boundary routers are used when calculating the AS external routes (see Section 16.4). Destination ID The destination's identifier or name. This depends on the Destination Type. For networks, the identifier is their associated IP address. For routers, the identifier is the OSPF Router ID.
Address Mask Only defined for networks. The network's IP address together with 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 this field indicates the optional OSPF capabilities supported by the destination router. The only optional capability defined by this specification is the ability to process AS-external-LSAs. For a further discussion of OSPF's optional capabilities, see Section 4.5. The set of paths to use for a destination may vary based on the OSPF area to which the paths belong. This means that there may be multiple routing table entries for the same destination, depending on the values of the next field. 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 "router", there may be separate sets of paths (and therefore separate routing table entries) associated with each of several areas. For example, this will happen when two area border routers share multiple areas in common. For destinations of type "network", only the set of paths associated with the best area (the one providing the preferred route) is kept. The rest of the routing table entry describes the set of paths to the destination. The following fields pertain to the set of paths as a whole. In other words, each one of the paths contained in a routing table 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 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-LSAs. AS external paths are paths to destinations external to the AS. These are detected through the examination of received AS-external-LSAs.
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, a type 2 external 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 LSA (router-LSA or network-LSA) that directly references the destination. For example, if the destination is a transit network, this is the transit network's network-LSA. If the destination is a stub network, this is the router-LSA for the attached router. The LSA is discovered during the shortest-path tree calculation (see Section 16.1). Multiple LSAs may reference the destination, however a tie-breaking scheme always reduces the choice to a single LSA. The Link State Origin field is not used by the OSPF protocol, but it is used by the routing table calculation in OSPF's Multicast routing extensions (MOSPF). When multiple paths of equal path-type and cost exist to a destination (called elsewhere "equal-cost" paths), they are stored in a single routing table entry. Each one of the "equal-cost" paths is distinguished by the following fields: Next hop The outgoing router interface to use when forwarding traffic to the destination. On broadcast, Point-to-MultiPoint and NBMA networks, the next hop also includes the IP address of the next router (if any) in the path towards the destination. Advertising router Valid only for inter-area and AS external paths. This field indicates the Router ID of the router advertising the summary-LSA or AS-external-LSA that led to this path.
11.1. Routing table lookup When an IP data packet is received, an OSPF router finds the routing table entry that best matches the packet's destination. This routing table entry then provides the outgoing interface and next hop router to use in forwarding the packet. This section describes the process of finding the best matching routing table entry. The process consists of a number of steps, wherein the collection of routing table entries is progressively pruned. In the end, the single routing table entry remaining is called the "best match". Before the lookup begins, "discard" routing table entries should be inserted into the routing table for each of the router's active area address ranges (see Section 3.5). (An area range is considered "active" if the range contains one or more networks reachable by intra-area paths.) The destination of a "discard" entry is the set of addresses described by its associated active area address range, and the path type of each "discard" entry is set to "inter-area". Note that the steps described below may fail to produce a best match routing table entry (i.e., all existing routing table entries are pruned for some reason or another), or the best match routing table entry may be one of the above "discard" routing table entries. In these cases, the packet's IP destination is considered unreachable. Instead of being forwarded, the packet should be discarded and an ICMP destination unreachable message should be returned 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) Reduce the set of matching entries to those having the most preferential path-type (see Section 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. (3) Select the remaining routing table entry that provides the most specific (longest) match. Another way of saying this is to choose the remaining entry that specifies the narrowest range of IP addresses. For example, the entry for the address/mask pair of (22.214.171.124, 0xffffff00) is more
specific than an entry for the pair (126.96.36.199, 0xffff0000). The default route is the least specific match, since it matches all destinations. 11.2. Sample routing table, without areas Consider the Autonomous System pictured in Figure 2. No OSPF areas have been configured. A single metric is shown per outbound interface. The calculation of Router RT6's routing table proceeds as described in Section 2.2. The resulting routing table is shown in Table 12. Destination types are abbreviated: Network as "N", Router as "R". There are no instances of multiple equal-cost shortest paths in this example. Also, since there are no areas, there are no inter-area paths. Routers RT5 and RT7 are AS boundary routers. Intra-area routes have been calculated to Routers RT5 and RT7. This allows external routes to be calculated to the destinations advertised by RT5 and RT7 (i.e., Networks N12, N13, N14 and N15). It is assumed all AS-external-LSAs originated by RT5 and RT7 are advertising type 1 external metrics. This results in type 1 external paths being calculated to destinations N12-N15. 11.3. Sample routing table, with areas Consider the previous example, this time split into OSPF areas. An OSPF area configuration is pictured in Figure 6. Router RT4's routing table will be described for this area configuration. Router RT4 has a connection to Area 1 and a backbone connection. This causes Router RT4 to view the AS as the concatenation of the two graphs shown in Figures 7 and 8. The resulting routing table is displayed in Table 13.
Type Dest Area Path Type Cost Next Adv. Hop(s) 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 * R RT5 0 intra-area 6 RT5 * R RT7 0 intra-area 8 RT10 * ____________________________________________________________ N N12 * type 1 ext. 10 RT10 RT7 N N13 * type 1 ext. 14 RT5 RT5 N N14 * type 1 ext. 14 RT5 RT5 N N15 * type 1 ext. 17 RT10 RT7 Table 12: The routing table for Router RT6 (no configured areas). Again, Routers RT5 and RT7 are AS boundary routers. Routers RT3, RT4, RT7, RT10 and RT11 are area border routers. Note that there are two routing entries for the area border router RT3, since it has two areas in common with RT4 (Area 1 and the backbone). Backbone paths have been calculated to all area border routers. These are used when determining the inter-area routes. Note that all of the inter-area routes are associated with the backbone; this is always the case when the calculating router is itself an area border router. Routing information is condensed at area boundaries. In this example, we assume that Area 3 has been defined so that networks N9-N11 and the host route to H1 are all condensed to a single route when advertised into the backbone (by Router RT11). Note that the cost of this route is the maximum 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 advertise a route for networks N9-N11 and Host H1 into the backbone, and there would 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). Type Dest Area Path Type Cost Next Adv. Hops(s) 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 * R RT3 1 intra-area 1 * * __________________________________________________________________ N Ib 0 intra-area 22 RT5 * N Ia 0 intra-area 27 RT5 * R RT3 0 intra-area 21 RT5 * R RT5 0 intra-area 8 * * R RT7 0 intra-area 14 RT5 * R RT10 0 intra-area 22 RT5 * R RT11 0 intra-area 25 RT5 * __________________________________________________________________ N N6 0 inter-area 15 RT5 RT7 N N7 0 inter-area 19 RT5 RT7 N N8 0 inter-area 18 RT5 RT7 N N9-N11,H1 0 inter-area 36 RT5 RT11 __________________________________________________________________ N N12 * type 1 ext. 16 RT5 RT5,RT7 N N13 * type 1 ext. 16 RT5 RT5 N N14 * type 1 ext. 16 RT5 RT5 N N15 * type 1 ext. 23 RT5 RT7 Table 13: Router RT4's routing table in the presence of areas. Router RT4's routing table would improve (i.e., some of the paths in the routing table would become shorter) if an additional virtual link were configured between Router RT4 and Router RT3. The new virtual link would itself be associated with the first entry for area border router RT3 in Table 13 (an intra-area path through Area 1). This would yield a cost of 1 for the virtual link. The routing table entries changes that would be caused by the addition of this virtual
link are shown in Table 14. 12. Link State Advertisements (LSAs) Each router in the Autonomous System originates one or more link state advertisements (LSAs). This memo defines five distinct types of LSAs, which are described in Section 4.3. The collection of LSAs forms the link-state database. Each separate type of LSA has a separate function. Router-LSAs and network-LSAs describe how an area's routers and networks are interconnected. Summary-LSAs provide a way of condensing an area's routing information. AS-external-LSAs provide a way of transparently advertising externally-derived routing information throughout the Autonomous System. Each LSA begins with a standard 20-byte header. This LSA header is discussed below. Type Dest Area Path Type Cost Next Adv. Hop(s) Router(s) ________________________________________________________________ N Ib 0 intra-area 16 RT3 * N Ia 0 intra-area 21 RT3 * R RT3 0 intra-area 1 * * R RT10 0 intra-area 16 RT3 * R RT11 0 intra-area 19 RT3 * ________________________________________________________________ N N9-N11,H1 0 inter-area 30 RT3 RT11 Table 14: Changes resulting from an additional virtual link. 12.1. The LSA Header The LSA header contains the LS type, Link State ID and Advertising Router fields. The combination of these three fields uniquely identifies the LSA. There may be several instances of an LSA present in the Autonomous System, all at the same time. It must then be determined which instance is more recent. This determination is made by examining the LS sequence, LS checksum and LS age fields. These fields are also contained in the 20-byte LSA header. Several of the OSPF packet types list LSAs. When the instance is not important, an LSA is referred to by its LS type, Link State ID and Advertising Router (see Link State Request Packets). Otherwise, the LS sequence number, LS age and LS checksum fields must also be
referenced. A detailed explanation of the fields contained in the LSA header follows. 12.1.1. LS age This field is the age of the LSA in seconds. It should be processed as an unsigned 16-bit integer. It is set to 0 when the LSA is originated. It must be incremented by InfTransDelay on every hop of the flooding procedure. LSAs are also aged as they are held in each router's database. The age of an LSA is never incremented past MaxAge. LSAs having age MaxAge are not used in the routing table calculation. When an LSA's age first reaches MaxAge, it is reflooded. An LSA of age MaxAge is finally flushed from the database when it is no longer needed to ensure database synchronization. For more information on the aging of LSAs, consult Section 14. The LS age field is examined when a router receives two instances of an LSA, both having identical LS sequence numbers and LS checksums. An instance of age MaxAge is then always accepted as most recent; this allows old LSAs to be flushed quickly from the routing domain. Otherwise, if the ages differ by more than MaxAgeDiff, the instance having the smaller age is accepted as most recent. See Section 13.1 for more details. 12.1.2. Options The Options field in the LSA header indicates which optional capabilities are associated with the LSA. OSPF's optional capabilities are described in Section 4.5. One optional capability is defined by this specification, represented by the E-bit found in the Options field. The unrecognized bits in the Options field should be set to zero. The E-bit represents OSPF's ExternalRoutingCapability. This bit should be set in all LSAs associated with the backbone, and all LSAs associated with non-stub areas (see Section 3.6). It should also be set in all AS-external-LSAs. It should be reset in all router-LSAs, network-LSAs and summary-LSAs associated with a stub area. For all LSAs, the setting of the E-bit is for informational purposes only; it does not affect the routing table calculation.
12.1.3. LS type The LS type field dictates the format and function of the LSA. LSAs of different types have different names (e.g., router-LSAs or network-LSAs). All LSA types defined by this memo, except the AS- external-LSAs (LS type = 5), are flooded throughout a single area only. AS-external-LSAs are flooded throughout the entire Autonomous System, excepting stub areas (see Section 3.6). Each separate LSA type is briefly described below in Table 15. 12.1.4. Link State ID This field identifies the piece of the routing domain that is being described by the LSA. Depending on the LSA's LS type, the Link State ID takes on the values listed in Table 16. Actually, for Type 3 summary-LSAs (LS type = 3) and AS-external-LSAs (LS type = 5), the Link State ID may additionally have one or more of the destination network's "host" bits set. For example, when originating an AS-external-LSA for the network 10.0.0.0 with mask of 255.0.0.0, the Link State ID can be set to anything in the range 10.0.0.0 through 10.255.255.255 inclusive (although 10.0.0.0 should be used whenever possible). The freedom to set certain host bits allows a router to originate separate LSAs for two networks having the same address but different masks. See Appendix E for details.
LS Type LSA description ________________________________________________ 1 These are the router-LSAs. They describe the collected states of the router's interfaces. For more information, consult Section 12.4.1. ________________________________________________ 2 These are the network-LSAs. They describe the set of routers attached to the network. For more information, consult Section 12.4.2. ________________________________________________ 3 or 4 These are the summary-LSAs. They describe inter-area routes, and enable the condensation of routing information at area borders. Originated by area border routers, the Type 3 summary-LSAs describe routes to networks while the Type 4 summary-LSAs describe routes to AS boundary routers. ________________________________________________ 5 These are the AS-external-LSAs. 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-LSA. Table 15: OSPF link state advertisements (LSAs). 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 LSA's Link State ID.
When the LSA is describing a network (LS type = 2, 3 or 5), the network's IP address is easily derived by masking the Link State ID with the network/subnet mask contained in the body of the LSA. When the LSA is describing a router (LS type = 1 or 4), the Link State ID is always the described router's OSPF Router ID. When an AS-external-LSA (LS Type = 5) is describing a default route, its Link State ID is set to DefaultDestination (0.0.0.0). 12.1.5. Advertising Router This field specifies the OSPF Router ID of the LSA's originator. For router-LSAs, this field is identical to the Link State ID field. Network-LSAs are originated by the network's Designated Router. Summary-LSAs originated by area border routers. AS-external-LSAs are originated by AS boundary routers. 12.1.6. LS sequence number The sequence number field is a signed 32-bit integer. It is used to detect old and duplicate LSAs. The space of sequence numbers is linearly ordered. The larger the sequence number (when compared as signed 32-bit integers) the more recent the LSA. To describe to sequence number space more precisely, let N refer in the discussion below to the constant 2**31. The sequence number -N (0x80000000) is reserved (and unused). This leaves -N + 1 (0x80000001) as the smallest (and therefore oldest) sequence number; this sequence number is referred to as the constant InitialSequenceNumber. A router uses InitialSequenceNumber the first time it originates any LSA. Afterwards, the LSA's sequence number is incremented each time the router originates a new instance of the LSA. When an attempt is made to increment the sequence number past the maximum value of N - 1 (0x7fffffff; also referred to as MaxSequenceNumber), the current instance of the LSA must first be flushed from the routing domain. This is done by prematurely aging the LSA (see Section 14.1) and reflooding it. As soon as this flood has been acknowledged by all adjacent neighbors, a new instance can be originated with sequence number of InitialSequenceNumber. The router may be forced to promote the sequence number of one of its LSAs when a more recent instance of the LSA is unexpectedly received during the flooding process. This should be a rare event. This may indicate that an out-of-date LSA, originated by the router itself before its last restart/reload, still exists in the Autonomous System. For more information see Section 13.4.
12.1.7. LS checksum This field is the checksum of the complete contents of the LSA, excepting the LS age field. The LS age field is excepted so that an LSA's age can be incremented without updating the checksum. The checksum used is the same that is used for ISO connectionless datagrams; it is commonly referred to as the Fletcher checksum. It is documented in Annex B of [Ref6]. The LSA header also contains the length of the LSA in bytes; subtracting the size of the LS age field (two bytes) yields the amount of data to checksum. The checksum is used to detect data corruption of an LSA. This corruption can occur while an LSA is being flooded, or while it is being held in a router's memory. The LS checksum field cannot take on the value of zero; the occurrence of such a value should be considered a checksum failure. In other words, calculation of the checksum is not optional. The checksum of an LSA is verified in two cases: a) when it is received in a Link State Update Packet and b) at times during the aging of the link state database. The detection of a checksum failure leads to separate actions in each case. See Sections 13 and 14 for more details. Whenever the LS sequence number field indicates that two instances of an LSA are the same, the LS checksum field is examined. If there is a difference, the instance with the larger LS checksum is considered to be most recent. See Section 13.1 for more details. 12.2. The link state database A router has a separate link state database for every area to which it belongs. All routers belonging to the same area have identical link state 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 (see Section 16). Components of the area link-state database are flooded throughout the area only. Finally, when an adjacency (belonging to Area A) is being brought up, only the database for Area A is synchronized between the two routers. The area database is composed of router-LSAs, network-LSAs and summary-LSAs (all listed in the area data structure). In addition, external routes (AS-external-LSAs) are included in all non-stub area databases (see Section 3.6).
An implementation of OSPF must be able to access individual pieces of an area database. This lookup function is based on an LSA's LS type, Link State ID and Advertising Router. There will be a single instance (the most up-to-date) of each LSA in the database. The database lookup function is invoked during the LSA flooding procedure (Section 13) and the routing table calculation (Section 16). In addition, using this lookup function the router can determine whether it has itself ever originated a particular LSA, and if so, with what LS sequence number. An LSA is added to a router's database when either a) it is received during the flooding process (Section 13) or b) it is originated by the router itself (Section 12.4). An LSA is deleted from a router's database when either a) it has been overwritten by a newer instance during the flooding process (Section 13) or b) the router originates a newer instance of one of its self-originated LSAs (Section 12.4) or c) the LSA ages out and is flushed from the routing domain (Section 14). Whenever an LSA is deleted from the database it must also be removed from all neighbors' Link state retransmission lists (see Section 10). 12.3. Representation of TOS For backward compatibility with previous versions of the OSPF specification ([Ref9]), TOS-specific information can be included in router-LSAs, summary-LSAs and AS-external-LSAs. The encoding of TOS in OSPF LSAs is specified in Table 17. That table relates the OSPF encoding to the IP packet header's TOS field (defined in [Ref12]). The OSPF encoding is expressed as a decimal integer, and the IP packet header's TOS field is expressed in the binary TOS values used in [Ref12].
OSPF encoding RFC 1349 TOS values ___________________________________________ 0 0000 normal service 2 0001 minimize monetary cost 4 0010 maximize reliability 6 0011 8 0100 maximize throughput 10 0101 12 0110 14 0111 16 1000 minimize delay 18 1001 20 1010 22 1011 24 1100 26 1101 28 1110 30 1111 Table 17: Representing TOS in OSPF.