12.4.3. Summary-LSAs The destination described by a summary-LSA is either an IP network, an AS boundary router or a range of IP addresses. Summary-LSAs are flooded throughout a single area only. The destination described is one that is external to the area, yet still belongs to the Autonomous System. Summary-LSAs are originated by area border routers. The precise summary routes to advertise into an area are determined by examining the routing table structure (see Section 11) in accordance with the algorithm described below. Note that only intra-area routes are advertised into the backbone, while both intra-area and inter-area routes are advertised into the other areas. To determine which routes to advertise into an attached Area A, each routing table entry is processed as follows. Remember that each routing table entry describes a set of equal-cost best paths to a particular destination: o Only Destination Types of network and AS boundary router are advertised in summary-LSAs. 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-LSAs. If the routing table entry has Path-type of 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-LSA for the route. o Else, if the next hops associated with this set of paths belong to Area A itself, do not generate a summary-LSA for the route. This is the logical equivalent of a Distance Vector protocol's split horizon logic. o Else, if the routing table cost equals or exceeds the value LSInfinity, a summary-LSA cannot be generated for this route. o Else, if the destination of this route is an AS boundary router, a summary-LSA should be originated if and only if the routing table entry describes the preferred path to the AS boundary router (see Step 3 of Section 16.4). If so, a Type 4 summary-LSA is originated for the destination, with Link State ID equal to the AS boundary router's Router ID and metric equal to the routing table entry's cost. Note: these LSAs 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 summary-LSA for the destination, with Link State ID equal to the network's address (if necessary, the Link State ID can also have one or more of the network's host bits set; see Appendix E for details) 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-LSAs. Remember that an area has a configured list of address ranges, each range consisting of an [address,mask] pair and a status indication of either Advertise or DoNotAdvertise. At most a single Type 3 summary-LSA is originated for each range. When the range's status indicates Advertise, a Type 3 summary-LSA is generated with Link State ID equal to the
range's address (if necessary, the Link State ID can also have one or more of the range's "host" bits set; see Appendix E for details) and cost equal to the largest cost of any of the component networks. When the range's status indicates DoNotAdvertise, the Type 3 summary-LSA is suppressed and the component networks remain hidden from other areas. By default, if a network is not contained in any explicitly configured address range, a Type 3 summary- LSA is generated with Link State ID equal to the network's address (if necessary, the Link State ID can also have one or more of the network's "host" bits set; see Appendix E for details) and metric equal to the network's routing table cost. If an area is capable of carrying transit traffic (i.e., its TransitCapability is set to TRUE), routing information concerning backbone networks should not be condensed before being summarized into the area. Nor should the advertisement of backbone networks into transit areas be suppressed. In other words, the backbone's configured ranges should be ignored when originating summary-LSAs into transit areas. If a router advertises a summary-LSA for a destination which then becomes unreachable, the router must then flush the LSA from the routing domain by setting its age to MaxAge and reflooding (see Section 14.1). Also, if the destination is still reachable, yet can no longer be advertised according to the above procedure (e.g., it is now an inter-area route, when it used to be an intra-area route associated with some non-backbone area; it would thus no longer be advertisable to the backbone), the LSA should also be flushed from the routing domain. 22.214.171.124. Originating summary-LSAs into stub areas The algorithm in Section 12.4.3 is optional when Area A is an OSPF stub area. Area border routers connecting to a stub area can originate summary-LSAs into the area
according to the Section 12.4.3's algorithm, or can choose to originate only a subset of the summary-LSAs, possibly under configuration control. The fewer LSAs originated, the smaller the stub area's link state database, further reducing the demands on its routers' resources. However, omitting LSAs may also lead to sub- optimal inter-area routing, although routing will continue to function. As specified in Section 12.4.3, Type 4 summary-LSAs (ASBR-summary-LSAs) are never originated into stub areas. In a stub area, instead of importing external routes each area border router originates a "default summary- LSA" into the area. The Link State ID for the default summary-LSA is set to DefaultDestination, and the metric set to the (per-area) configurable parameter StubDefaultCost. Note that StubDefaultCost need not be configured identically in all of the stub area's area border routers. 126.96.36.199. Examples of summary-LSAs Consider again the area configuration in Figure 6. Routers RT3, RT4, RT7, RT10 and RT11 are all area border routers, and therefore are originating summary-LSAs. Consider in particular Router RT4. Its routing table was calculated as the example in Section 11.3. RT4 originates summary-LSAs into both the backbone and Area 1. Into the backbone, Router RT4 originates separate LSAs for each of the networks N1-N4. Into Area 1, Router RT4 originates separate LSAs for networks N6-N8 and the AS boundary routers RT5,RT7. It also condenses host routes Ia and Ib into a single summary-LSA. Finally, the routes to networks N9,N10,N11 and Host H1 are advertised by a single summary-LSA. This condensation was originally performed by the router RT11.
These LSAs are illustrated graphically in Figures 7 and 8. Two of the summary-LSAs originated by Router RT4 follow. The actual IP addresses for the networks and routers in question have been assigned in Figure 15. ; Summary-LSA for Network N1, ; originated by Router RT4 into the backbone LS age = 0 ;always true on origination Options = (E-bit) ; LS type = 3 ;Type 3 summary-LSA Link State ID = 188.8.131.52 ;N1's IP network number Advertising Router = 184.108.40.206 ;RT4's ID metric = 4 ; Summary-LSA for AS boundary router RT7 ; originated by Router RT4 into Area 1 LS age = 0 ;always true on origination Options = (E-bit) ; LS type = 4 ;Type 4 summary-LSA Link State ID = Router RT7's ID Advertising Router = 220.127.116.11 ;RT4's ID metric = 14 12.4.4. AS-external-LSAs AS-external-LSAs describe routes to destinations external to the Autonomous System. Most AS-external-LSAs describe routes to specific external destinations; in these cases the LSA's Link State ID is set to the destination network's IP address (if necessary, the Link State ID can also have one or more of the network's "host" bits set; see Appendix E for details). However, a default route for the Autonomous System can be described in an AS-external-LSA by setting the LSA's Link State ID to DefaultDestination (0.0.0.0). AS- external-LSAs are originated by AS boundary routers. An AS boundary router originates a single AS-external-LSA for each external route that it has learned, either through another routing protocol (such as BGP), or through configuration information.
AS-external-LSAs are the only type of LSAs that are flooded throughout the entire Autonomous System; all other types of LSAs are specific to a single area. However, AS-external- LSAs are not flooded into/throughout stub areas (see Section 3.6). This enables a reduction in link state database size for routers internal to stub areas. The metric that is advertised for an external route can be one of two types. Type 1 metrics are comparable to the link state metric. Type 2 metrics are assumed to be larger than the cost of any intra-AS path. If a router advertises an AS-external-LSA for a destination which then becomes unreachable, the router must then flush the LSA from the routing domain by setting its age to MaxAge and reflooding (see Section 14.1). 18.104.22.168. Examples of AS-external-LSAs Consider once again the AS pictured in Figure 6. There are two AS boundary routers: RT5 and RT7. Router RT5 originates three AS-external-LSAs, for networks N12-N14. Router RT7 originates two AS-external-LSAs, for networks N12 and N15. Assume that RT7 has learned its route to N12 via BGP, and that it wishes to advertise a Type 2 metric to the AS. RT7 would then originate the following LSA for N12: ; AS-external-LSA for Network N12, ; originated by Router RT7 LS age = 0 ;always true on origination Options = (E-bit) ; LS type = 5 ;AS-external-LSA Link State ID = N12's IP network number Advertising Router = Router RT7's ID bit E = 1 ;Type 2 metric metric = 2 Forwarding address = 0.0.0.0
In the above example, the forwarding address field has been set to 0.0.0.0, indicating that packets for the external destination should be forwarded to the advertising OSPF router (RT7). This is not always desirable. Consider the example pictured in Figure 16. There are three OSPF routers (RTA, RTB and RTC) connected to a common network. Only one of these routers, RTA, is exchanging BGP information with the non-OSPF router RTX. RTA must then originate AS- external-LSAs for those destinations it has learned from RTX. By using the AS-external-LSA's forwarding address field, RTA can specify that packets for these destinations be forwarded directly to RTX. Without this feature, Routers RTB and RTC would take an extra hop to get to these destinations. Note that when the forwarding address field is non- zero, it should point to a router belonging to another Autonomous System. A forwarding address can also be specified for the default route. For example, in figure 16 RTA may want to specify that all externally-destined packets should by default be forwarded to its BGP peer RTX. The resulting AS-external-LSA is pictured below. Note that 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 = (E-bit) ; LS type = 5 ;AS-external-LSA Link State ID = DefaultDestination ; default route Advertising Router = Router RTA's ID bit E = 1 ;Type 2 metric metric = 1 Forwarding address = RTX's IP address In figure 16, suppose instead that both RTA and RTB exchange BGP information with RTX. In this case,
RTA and RTB would originate the same set of AS- external-LSAs. These LSAs, if they specify the same metric, would be functionally equivalent since they would specify the same destination and forwarding address (RTX). This leads to a clear duplication of effort. If only one of RTA or RTB originated the set of AS-external-LSAs, the routing would remain the same, and the size of the link state database would decrease. However, it must be unambiguously defined as to which router originates the LSAs (otherwise neither may, or the identity of the originator may oscillate). The following rule is thereby established: if two routers, both reachable from one another, originate functionally equivalent AS-external-LSAs (i.e., same destination, cost and non-zero forwarding address), then the LSA originated by the router having the highest OSPF Router ID is used. The router having the lower OSPF Router ID can then flush its LSA. Flushing an LSA is discussed in Section 14.1. + | +---+.....|.BGP |RTA|-----|.....+---+ +---+ |-----|RTX| | +---+ +---+ | |RTB|-----| +---+ | | +---+ | |RTC|-----| +---+ | | + Figure 16: Forwarding address example
13. The Flooding Procedure Link State Update packets provide the mechanism for flooding LSAs. A Link State Update packet may contain several distinct LSAs, and floods each LSA one hop further from its point of origination. To make the flooding procedure reliable, each LSA must be acknowledged separately. Acknowledgments are transmitted in Link State Acknowledgment packets. Many separate acknowledgments can also be grouped together into a single packet. The flooding procedure starts when a Link State Update packet has been received. Many consistency checks have been made on the received packet before being handed to the flooding procedure (see Section 8.2). In particular, the Link State Update packet has been associated with a particular neighbor, and a particular area. If the neighbor is in a lesser state than Exchange, the packet should be dropped without further processing. All types of LSAs, other than AS-external-LSAs, are associated with a specific area. However, LSAs do not contain an area field. An LSA's area must be deduced from the Link State Update packet header. For each LSA contained in a Link State Update packet, the following steps are taken: (1) Validate the LSA's LS checksum. If the checksum turns out to be invalid, discard the LSA and get the next one from the Link State Update packet. (2) Examine the LSA's LS type. If the LS type is unknown, discard the LSA and get the next one from the Link State Update Packet. This specification defines LS types 1-5 (see Section 4.3). (3) Else if this is an AS-external-LSA (LS type = 5), and the area has been configured as a stub area, discard the LSA and get the next one from the Link State Update Packet. AS-external-LSAs are not flooded into/throughout stub areas (see Section 3.6). (4) Else if the LSA's LS age is equal to MaxAge, and there is currently no instance of the LSA in the router's link state database, and none of router's neighbors are in states Exchange
or Loading, then take the following actions: a) Acknowledge the receipt of the LSA by sending a Link State Acknowledgment packet back to the sending neighbor (see Section 13.5), and b) Discard the LSA and examine the next LSA (if any) listed in the Link State Update packet. (5) Otherwise, find the instance of this LSA that is currently contained in the router's link state database. If there is no database copy, or the received LSA is more recent than the database copy (see Section 13.1 below for the determination of which LSA is more recent) the following steps must be performed: (a) If there is already a database copy, and if the database copy was received via flooding and installed less than MinLSArrival seconds ago, discard the new LSA (without acknowledging it) and examine the next LSA (if any) listed in the Link State Update packet. (b) Otherwise immediately flood the new LSA out some subset of the router's interfaces (see Section 13.3). In some cases (e.g., the state of the receiving interface is DR and the LSA was received from a router other than the Backup DR) the LSA 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 LSA 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 LSA with the current time (i.e., the time it was received). The flooding procedure cannot overwrite the newly installed LSA until MinLSArrival seconds have elapsed. The LSA installation process is discussed further in Section 13.2. (e) Possibly acknowledge the receipt of the LSA by sending a Link State Acknowledgment packet back out the receiving interface. This is explained below in Section 13.5.
(f) If this new LSA indicates that it was originated by the receiving router itself (i.e., is considered a self- originated LSA), the router must take special action, either updating the LSA or in some cases flushing it from the routing domain. For a description of how self-originated LSAs are detected and subsequently handled, see Section 13.4. (6) Else, if there is an instance of the LSA on the sending neighbor's Link state request list, an error has occurred in the Database Exchange process. In this case, restart the Database Exchange process by generating the neighbor event BadLSReq for the sending neighbor and stop processing the Link State Update packet. (7) Else, if the received LSA 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 LSA is listed in the Link state retransmission list for the receiving adjacency, the router itself is expecting an acknowledgment for this LSA. The router should treat the received LSA as an acknowledgment by removing the LSA 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 LSA by sending a Link State Acknowledgment packet back out the receiving interface. This is explained below in Section 13.5. (8) Else, the database copy is more recent. If the database copy has LS age equal to MaxAge and LS sequence number equal to MaxSequenceNumber, simply discard the received LSA without acknowledging it. (In this case, the LSA's LS sequence number is wrapping, and the MaxSequenceNumber LSA must be completely flushed before any new LSA instance can be introduced). Otherwise, as long as the database copy has not been sent in a Link State Update within the last MinLSArrival seconds, send the database copy back to the sending neighbor, encapsulated within a Link State Update Packet. The Link State Update Packet should be sent directly to the neighbor. In so doing, do not put the
database copy of the LSA on the neighbor's link state retransmission list, and do not acknowledge the received (less recent) LSA instance. 13.1. Determining which LSA is newer When a router encounters two instances of an LSA, it must determine which is more recent. This occurred above when comparing a received LSA to its database copy. This comparison must also be done during the Database Exchange procedure which occurs during adjacency bring-up. An LSA is identified by its LS type, Link State ID and Advertising Router. For two instances of the same LSA, the LS sequence number, LS age, and LS checksum fields are used to determine which instance is more recent: o The LSA having the newer LS sequence number is more recent. See Section 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 has its LS age field set to MaxAge, the instance of age MaxAge is considered to be more recent. o Else, if the LS age fields of the two instances differ by more than MaxAgeDiff, the instance having the smaller (younger) LS age is considered to be more recent. o Else, the two instances are considered to be identical.
13.2. Installing LSAs in the database Installing a new LSA in the database, either as the result of flooding or a newly self-originated LSA, may cause the OSPF routing table structure to be recalculated. The contents of the new LSA should be compared to the old instance, if present. If there is no difference, there is no need to recalculate the routing table. When comparing an LSA to its previous instance, the following are all considered to be differences in contents: o The LSA's Options field has changed. o One of the LSA instances has LS age set to MaxAge, and the other does not. o The length field in the LSA header has changed. o The body of the LSA (i.e., anything outside the 20-byte LSA header) has changed. Note that this excludes changes in LS Sequence Number and LS Checksum. If the contents are different, the following pieces of the routing table must be recalculated, depending on the new LSA's LS type field: Router-LSAs and network-LSAs The entire routing table must be recalculated, starting with the shortest path calculations for each area (not just the area whose link-state 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. Summary-LSAs The best route to the destination described by the summary- LSA must be recalculated (see Section 16.5). If this destination is an AS boundary router, it may also be necessary to re-examine all the AS-external-LSAs.
AS-external-LSAs The best route to the destination described by the AS- external-LSA must be recalculated (see Section 16.6). Also, any old instance of the LSA must be removed from the database when the new LSA is installed. This old instance must also be removed from all neighbors' Link state retransmission lists (see Section 10). 13.3. Next step in the flooding procedure When a new (and more recent) LSA has been received, it must be flooded out some set of the router's interfaces. This section describes the second part of flooding procedure (the first part being the processing that occurred in Section 13), namely, selecting the outgoing interfaces and adding the LSA to the appropriate neighbors' Link state retransmission lists. Also included in this part of the flooding procedure is the maintenance of the neighbors' Link state request lists. This section is equally applicable to the flooding of an LSA that the router itself has just originated (see Section 12.4). For these LSAs, this section provides the entirety of the flooding procedure (i.e., the processing of Section 13 is not performed, since, for example, the LSA has not been received from a neighbor and therefore does not need to be acknowledged). Depending upon the LSA's LS type, the LSA can be flooded out only certain interfaces. These interfaces, defined by the following, are called the eligible interfaces: AS-external-LSAs (LS Type = 5) AS-external-LSAs are flooded throughout the entire AS, with the exception of stub areas (see Section 3.6). The eligible interfaces are all the router's interfaces, excluding virtual links and those interfaces attaching to stub areas. All other LS 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. Link state databases must remain synchronized over all adjacencies associated with the above eligible interfaces. This is accomplished by executing the following steps on each eligible interface. It should be noted that this procedure may decide not to flood an LSA out a particular interface, if there is a high probability that the attached neighbors have already received the LSA. However, in these cases the flooding procedure must be absolutely sure that the neighbors eventually do receive the LSA, so the LSA is still added to each adjacency's Link state retransmission list. For each eligible interface: (1) Each of the neighbors attached to this interface are examined, to determine whether they must receive the new LSA. 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 LSA on the list, it indicates that the neighboring router has an instance of the LSA already. Compare the new LSA to the neighbor's copy: o If the new LSA is less recent, then examine the next neighbor. o If the two copies are the same instance, then delete the LSA from the Link state request list, and examine the next neighbor. o Else, the new LSA is more recent. Delete the LSA from the Link state request list.
(c) If the new LSA was received from this neighbor, examine the next neighbor. (d) At this point we are not positive that the neighbor has an up-to-date instance of this new LSA. Add the new LSA to the Link state retransmission list for the adjacency. This ensures that the flooding procedure is reliable; the LSA will be retransmitted at intervals until an acknowledgment is seen from the neighbor. (2) The router must now decide whether to flood the new LSA out this interface. If in the previous step, the LSA was NOT added to any of the Link state retransmission lists, there is no need to flood the LSA out the interface and the next interface should be examined. (3) If the new LSA was received on this interface, and it was received from either the Designated Router or the Backup Designated Router, chances are that all the neighbors have received the LSA already. Therefore, examine the next interface. (4) If the new LSA 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. However, if the Designated Router fails the router (i.e., the Backup Designated Router) will end up retransmitting the updates. (5) If this step is reached, the LSA must be flooded out the interface. Send a Link State Update packet (including the new LSA as contents) out the interface. The LSA's LS age must be incremented by InfTransDelay (which must be > 0) when it is copied into the outgoing Link State Update packet (until the LS age field reaches the 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 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 LSAs It is a common occurrence for a router to receive self- originated LSAs via the flooding procedure. A self-originated LSA is detected when either 1) the LSA's Advertising Router is equal to the router's own Router ID or 2) the LSA is a network- LSA and its Link State ID is equal to one of the router's own IP interface addresses. However, if the received self-originated LSA is newer than the last instance that the router actually originated, the router must take special action. The reception of such an LSA indicates that there are LSAs in the routing domain that were originated by the router before the last time it was restarted. In most cases, the router must then advance the LSA's LS sequence number one past the received LS sequence number, and originate a new instance of the LSA. It may be the case the router no longer wishes to originate the received LSA. Possible examples include: 1) the LSA is a summary-LSA or AS-external-LSA and the router no longer has an (advertisable) route to the destination, 2) the LSA is a network-LSA but the router is no longer Designated Router for the network or 3) the LSA is a network-LSA whose Link State ID is one of the router's own IP interface addresses but whose Advertising Router is not equal to the router's own Router ID (this latter case should be rare, and it indicates that the router's Router ID has changed since originating the LSA). In all these cases, instead of updating the LSA, the LSA should be flushed from the routing domain by incrementing the received LSA's LS age to MaxAge and reflooding (see Section 14.1).
13.5. Sending Link State Acknowledgment packets Each newly received LSA must be acknowledged. This is usually done by sending Link State Acknowledgment packets. However, acknowledgments can also be accomplished implicitly by sending Link State Update packets (see step 7a of Section 13). Many acknowledgments may be grouped together into a single Link State Acknowledgment packet. Such a packet is sent back out the interface which received the LSAs. The packet can be sent in one of two ways: delayed and sent on an interval timer, or sent directly to a particular neighbor. The particular acknowledgment strategy used depends on the circumstances surrounding the receipt of the LSA. Sending delayed acknowledgments accomplishes several things: 1) it facilitates the packaging of multiple acknowledgments in a single Link State Acknowledgment packet, 2) it enables a single Link State Acknowledgment packet to indicate acknowledgments to several neighbors at once (through multicasting) and 3) it randomizes the Link State Acknowledgment packets sent by the various routers attached to a common network. The fixed interval between a router's delayed transmissions must be short (less than RxmtInterval) or needless retransmissions will ensue. Direct acknowledgments are sent directly to a particular neighbor in response to the receipt of duplicate LSAs. Direct acknowledgments are sent immediately when the duplicate is received. On multi-access networks, these acknowledgments are sent directly to the neighbor's IP address. The precise procedure for sending Link State Acknowledgment packets is described in Table 19. The circumstances surrounding the receipt of the LSA are listed in the left column. The acknowledgment action then taken is listed in one of the two right columns. This action depends on the state of the concerned interface; interfaces in state Backup behave differently from interfaces in all other states. Delayed acknowledgments must be delivered to all adjacent routers associated with the interface. On broadcast networks, this is accomplished by sending the delayed Link State Acknowledgment packets as multicasts. The Destination IP address used depends
Action taken in state Circumstances Backup All other states _________________________________________________________________ LSA has No acknowledgment No acknowledgment been flooded back sent. sent. out receiving in- terface (see Sec- tion 13, step 5b). _________________________________________________________________ LSA is Delayed acknowledg- Delayed ack- more recent than ment sent if adver- nowledgment sent. database copy, but tisement received was not flooded from Designated back out receiving Router, otherwise interface do nothing _________________________________________________________________ LSA is a Delayed acknowledg- No acknowledgment duplicate, and was ment sent if adver- sent. treated as an im- tisement received plied acknowledg- from Designated ment (see Section Router, otherwise 13, step 7a). do nothing _________________________________________________________________ LSA is a Direct acknowledg- Direct acknowledg- duplicate, and was ment sent. ment sent. not treated as an implied ack- nowledgment. _________________________________________________________________ LSA's LS Direct acknowledg- Direct acknowledg- age is equal to ment sent. ment sent. MaxAge, and there is no current instance of the LSA in the link state database, and none of router's neighbors are in states Exchange
or Loading (see Section 13, step 4). Table 19: Sending link state acknowledgements. on the state of the interface. If the interface state is DR or Backup, the destination AllSPFRouters is used. In all other states, the destination AllDRouters is used. On non-broadcast networks, delayed Link State Acknowledgment packets must be unicast separately over each adjacency (i.e., neighbor whose state is >= Exchange). The reasoning behind sending the above packets as multicasts is best explained by an example. Consider the network configuration depicted in Figure 15. Suppose RT4 has been elected as Designated Router, and RT3 as Backup Designated Router for the network N3. When Router RT4 floods a new LSA to Network N3, it is received by routers RT1, RT2, and RT3. These routers will not flood the LSA back onto net N3, but they still must ensure that their link-state databases remain synchronized with their adjacent neighbors. So RT1, RT2, and RT4 are waiting to see an acknowledgment from RT3. Likewise, RT4 and RT3 are both waiting to see acknowledgments from RT1 and RT2. This is best achieved by sending the acknowledgments as multicasts. The reason that the acknowledgment logic for Backup DRs is slightly different is because they perform differently during the flooding of LSAs (see Section 13.3, step 4). 13.6. Retransmitting LSAs LSAs flooded out an adjacency are placed on the adjacency's Link state retransmission list. In order to ensure that flooding is reliable, these LSAs are retransmitted until they are acknowledged. The length of time between retransmissions is a configurable per-interface value, RxmtInterval. If this is set
too low for an interface, needless retransmissions will ensue. If the value is set too high, the speed of the flooding, in the face of lost packets, may be affected. Several retransmitted LSAs may fit into a single Link State Update packet. When LSAs are to be retransmitted, only the number fitting in a single Link State Update packet should be sent. Another packet of retransmissions can be sent whenever some of the LSAs are acknowledged, or on the next firing of the retransmission timer. Link State Update Packets carrying retransmissions are always sent directly to the neighbor. On multi-access networks, this means that retransmissions are sent directly to the neighbor's IP address. Each LSA's LS age must be incremented by InfTransDelay (which must be > 0) when it is copied into the outgoing Link State Update packet (until the LS age field reaches the maximum value of MaxAge). If an adjacent router goes down, retransmissions may occur until the adjacency is destroyed by OSPF's Hello Protocol. When the adjacency is destroyed, the Link state retransmission list is cleared. 13.7. Receiving link state acknowledgments Many consistency checks have been made on a received Link State Acknowledgment packet before it is handed to the flooding procedure. In particular, it has been associated with a particular neighbor. If this neighbor is in a lesser state than Exchange, the Link State Acknowledgment packet is discarded. Otherwise, for each acknowledgment in the Link State Acknowledgment packet, the following steps are performed: o Does the LSA 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 Database Each LSA has an LS age field. The LS age is expressed in seconds. An LSA's LS age field is incremented while it is contained in a router's database. Also, when copied into a Link State Update Packet for flooding out a particular interface, the LSA's LS age is incremented by InfTransDelay. An LSA's LS age is never incremented past the value MaxAge. LSAs having age MaxAge are not used in the routing table calculation. As a router ages its link state database, an LSA's LS age may reach MaxAge. At this time, the router must attempt to flush the LSA from the routing domain. This is done simply by reflooding the MaxAge LSA just as if it was a newly originated LSA (see Section 13.3). When creating a Database summary list for a newly forming adjacency, any MaxAge LSAs present in the link state database are added to the neighbor's Link state retransmission list instead of the neighbor's Database summary list. See Section 10.3 for more details. A MaxAge LSA must be removed immediately from the router's link state database as soon as both a) it is no longer contained on any neighbor Link state retransmission lists and b) none of the router's neighbors are in states Exchange or Loading. When, in the process of aging the link state database, an LSA's LS age hits a multiple of CheckAge, its LS checksum should be verified. If the LS checksum is incorrect, a program or memory error has been detected, and at the very least the router itself should be restarted.
14.1. Premature aging of LSAs An LSA can be flushed from the routing domain by setting its LS age to MaxAge, while leaving its LS sequence number alone, and then reflooding the LSA. This procedure follows the same course as flushing an LSA whose LS age has naturally reached the value MaxAge (see Section 14). In particular, the MaxAge LSA is removed from the router's link state database as soon as a) it is no longer contained on any neighbor Link state retransmission lists and b) none of the router's neighbors are in states Exchange or Loading. We call the setting of an LSA's LS age to MaxAge "premature aging". Premature aging is used when it is time for a self-originated LSA's sequence number field to wrap. At this point, the current LSA instance (having LS sequence number MaxSequenceNumber) must be prematurely aged and flushed from the routing domain before a new instance with sequence number equal to InitialSequenceNumber can be originated. See Section 12.1.6 for more information. Premature aging can also be used when, for example, one of the router's previously advertised external routes is no longer reachable. In this circumstance, the router can flush its AS- external-LSA from the routing domain via premature aging. This procedure is preferable to the alternative, which is to originate a new LSA for the destination specifying a metric of LSInfinity. Premature aging is also be used when unexpectedly receiving self-originated LSAs during the flooding procedure (see Section 13.4). A router may only prematurely age its own self-originated LSAs. The router may not prematurely age LSAs that have been originated by other routers. An LSA is considered self- originated when either 1) the LSA's Advertising Router is equal to the router's own Router ID or 2) the LSA is a network-LSA and its Link State ID is equal to one of the router's own IP interface addresses.
15. Virtual Links The single backbone area (Area ID = 0.0.0.0) cannot be disconnected, or some areas of the Autonomous System will become unreachable. To establish/maintain connectivity of the backbone, virtual links can be configured through non-backbone areas. Virtual links serve to connect physically separate components of the backbone. The two endpoints of a virtual link are area border routers. The virtual link must be configured in both routers. The configuration information in each router consists of the other virtual endpoint (the other area border router), and the non-backbone area the two routers have in common (called the Transit area). Virtual links cannot be configured through stub areas (see Section 3.6). The virtual link is treated as if it were an unnumbered point-to- point network belonging to the backbone and 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 in backbone router-LSAs, and OSPF packets pertaining to the backbone area will flow over the adjacency. Such an adjacency has been referred to in this document as a "virtual adjacency". In each endpoint router, the cost and viability of the virtual link is discovered by examining the routing table entry for the other endpoint router. (The entry's associated area must be the configured Transit area). This is called the virtual link's corresponding routing table entry. The InterfaceUp event occurs for a virtual link when its corresponding routing table entry becomes reachable. Conversely, the InterfaceDown event occurs when its routing table entry becomes unreachable. In other words, the virtual link's viability is determined by the existence of an intra-area path, through the Transit area, between the two endpoints. Note that a virtual link whose underlying path has cost greater than hexadecimal 0xffff (the maximum size of an interface cost in a router-LSA) should be considered inoperational (i.e., treated the same as if the path did not exist). The other details concerning virtual links are as follows: o AS-external-LSAs are NEVER flooded over virtual adjacencies. This would be duplication of effort, since the same AS-
external-LSAs are already flooded throughout the virtual link's Transit area. For this same reason, AS-external-LSAs 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-LSA 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 OSPF protocol packets over the virtual link. Note that when one (or both) of the virtual link endpoints connect to the Transit area via an unnumbered point-to-point link, it may be impossible to calculate either the virtual interface's IP address and/or the virtual neighbor's IP address, thereby causing the virtual link to fail. o In each endpoint's router-LSA for the backbone, the virtual link is represented as a Type 4 link whose Link ID is set to the virtual neighbor's OSPF Router ID and whose Link Data is set to the virtual interface's IP address. See Section 12.4.1 for more information. o A non-backbone area can carry transit data traffic (i.e., is considered a "transit area") if and only if it serves as the Transit area for one or more fully adjacent virtual links (see TransitCapability in Sections 6 and 16.1). Such an area requires special treatment when summarizing backbone networks into it (see Section 12.4.3), and during the routing calculation (see Section 16.3). 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 table This section details the OSPF routing table calculation. Using its attached areas' link state databases as input, a router runs the following algorithm, building its routing table step by step. At each step, the router must access individual pieces of the link state databases (e.g., a router-LSA originated by a certain router). This access is performed by the lookup function discussed in Section 12.2. The lookup process may return an LSA whose LS age is equal to MaxAge. Such an LSA should not be used in the routing table calculation, and is treated just as if the lookup process had failed. The OSPF routing table's organization is explained in Section 11. Two examples of the routing table build process are presented in Sections 11.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. During the area's shortest-path tree calculation, the area's TransitCapability is also calculated for later use in Step 4. (3) The inter-area routes are calculated, through examination of summary-LSAs. If the router is attached to multiple areas (i.e., it is an area border router), only backbone summary-LSAs are examined.
(4) In area border routers connecting to one or more transit areas (i.e, non-backbone areas whose TransitCapability is found to be TRUE), the transit areas' summary-LSAs are examined to see whether better paths exist using the transit areas than were found in Steps 2-3 above. (5) Routes to external destinations are calculated, through examination of AS-external-LSAs. The locations of the AS boundary routers (which originate the AS-external-LSAs) have been determined in steps 2-4. Steps 2-5 are explained in further detail below. Changes made to routing table entries as a result of these calculations can cause the OSPF protocol to take further actions. For example, a change to an intra-area route will cause an area border router to originate new summary-LSAs (see Section 12.4). See Section 16.7 for a complete list of the OSPF protocol actions resulting from routing table changes. 16.1. Calculating the shortest-path tree for an area This calculation yields the set of intra-area routes associated with an area (called hereafter Area A). A router calculates the shortest-path tree using itself as the root. The formation of the shortest path tree is done here in two stages. In the first stage, only links between routers and transit networks are considered. Using the Dijkstra algorithm, a tree is formed from this subset of the link state database. In the second stage, leaves are added to the tree by considering the links to stub networks. The procedure will be explained using the graph terminology that was introduced in Section 2. The area's link state database is represented as a directed graph. The graph's vertices are routers, transit networks and stub networks. The first stage of the procedure concerns only the transit vertices (routers and transit networks) and their connecting links. Throughout the shortest path calculation, the following data is also associated with each transit vertex:
Vertex (node) ID A 32-bit number which together with the vertex type (router or network) uniquely identifies the vertex. For router vertices the Vertex ID is the router's OSPF Router ID. For network vertices, it is the IP address of the network's Designated Router. An LSA Each transit vertex has an associated LSA. For router vertices, this is a router-LSA. For transit networks, this is a network-LSA (which is actually originated by the network's Designated Router). In any case, the LSA's Link State ID is always equal to the above Vertex ID. List of next hops The list of next hops for the current set of 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 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. Distance from root The link state cost of the current set of shortest paths 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-LSAs and network-LSAs). One path is said to be "shorter" than another if it has a smaller link state cost. The first stage of the procedure (i.e., the Dijkstra algorithm) can now be summarized as follows. At each iteration of the algorithm, there is a list of candidate vertices. Paths from the root to these vertices have been found, but not necessarily the shortest ones. However, the paths to the candidate vertex that is closest to the root are guaranteed to be shortest; this vertex is added to the shortest-path tree, removed from the candidate list, and its adjacent vertices are examined for possible addition to/modification of the candidate list. The
algorithm then iterates again. It terminates when the candidate list becomes empty. The following steps describe the algorithm in detail. Remember that we are computing the shortest path tree for Area A. All references to link 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). Set Area A's TransitCapability to FALSE. (2) Call the vertex just added to the tree vertex V. Examine the LSA associated with vertex V. This is a lookup in the Area A's link state database based on the Vertex ID. If this is a router-LSA, and bit V of the router-LSA (see Section A.4.2) is set, set Area A's TransitCapability to TRUE. In any case, each link described by the LSA 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 LSA. 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 LSA (router-LSA or network-LSA) in Area A's link state database. If the LSA does not exist, or its LS age is equal to MaxAge, or it does not have a link back to vertex V, examine the next link in V's LSA. (c) If vertex W is already on the shortest-path tree, examine the next link in the LSA. (d) 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 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 in Section 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 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 in Section 16.1.1; it 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 procedure 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). Note that when there is a choice of vertices closest to the root, network vertices must be chosen before router vertices in order to necessarily find all equal-cost paths. This is consistent with the tie-breakers that were introduced in the modified Dijkstra algorithm used by OSPF's Multicast routing extensions (MOSPF). (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 or AS boundary router, a routing table entry is added whose destination type is "router". The Options field found in the associated router-LSA is copied into the routing table entry's Optional capabilities field. Call the newly added vertex Router X. If Router X is the endpoint of one of the calculating router's virtual links, and the virtual link uses Area A as Transit area: the virtual link is declared up, the IP address of the virtual interface is set to the IP address of the outgoing interface calculated above for Router X, and the virtual neighbor's IP address is set to Router X's interface address (contained in Router X's router-LSA) that points back to the root of the shortest- path tree; equivalently, this is the interface that points back to Router X's parent vertex on the shortest-path tree (similar to the calculation in Section 16.1.1). 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 body of the associated network-LSA). 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' LSA. 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' LSA. (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 have been determined to be unreachable in the above first phase are discarded. For each reachable router vertex (call it V), the associated router-LSA is found in the link state database. Each stub network link appearing in the LSA is then examined, and the following steps are executed: (1) 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 stub network's current routing table entry. If the calculated distance D is larger, go on to examine the next stub network link in the LSA. (2) 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 in Section 16.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-LSA whose Link State ID is smaller than V's Router ID, reset the Link State Origin to V's router-LSA. 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-LSA. Then go on to examine the next stub network link. For all routing table entries added/modified in the second stage, the associated area will be set to Area A and the path type will be set to intra-area. When the list of reachable router-LSAs is exhausted, the second stage is completed. At
this time, all intra-area routes associated with Area A have been determined. The specification does not require that the above two stage method be used to calculate the shortest path tree. However, if another algorithm is used, an identical tree must be produced. For this reason, it is important to note that links between transit vertices must be bidirectional in order to be included in the above tree. It should also be mentioned that more efficient algorithms exist for calculating the tree; for example, the incremental SPF algorithm described in [Ref1]. 16.1.1. The next hop calculation This section explains how to calculate the current set of next hops to use for a destination. Each next hop consists of the outgoing interface to use in forwarding packets to the destination together with the IP address of the next hop router (if any). The next hop calculation is invoked each time a shorter path to the destination is discovered. This can happen in either stage of the shortest-path tree calculation (see Section 16.1). In stage 1 of the shortest-path tree calculation a shorter path is found as the destination is added to the candidate list, or when the destination's entry on the candidate list is modified (Step 2d of Stage 1). In stage 2 a shorter path is discovered each time the destination's routing table entry is modified (Step 2 of Stage 2). The set of next hops to use for the destination may be recalculated several times during the shortest-path tree calculation, as shorter and shorter paths are discovered. In the end, the destination's routing table entry will always reflect the next hops resulting from the absolute shortest path(s). Input to the next hop calculation is a) the destination and b) its parent in the current shortest path between the root (the calculating router) 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 path between the destination and the root, the destination simply inherits the set of next hops from the parent. Otherwise, there are two cases. In the first case, the parent vertex is the root (the calculating router itself). This means that the destination is either a directly connected network or directly connected router. The outgoing interface in this case is simply the OSPF interface connecting to the destination network/router. If the destination is a router which connects to the calculating router via a Point-to-MultiPoint network, the destination's next hop IP address(es) can be determined by examining the destination's router-LSA: each link pointing back to the calculating router and having a Link Data field belonging to the Point-to-MultiPoint network provides an IP address of the next hop router. If the destination is a directly connected network, or a router which connects to the calculating router via a point-to-point interface, no next hop IP address is required. If the destination is a router connected to the calculating router via a virtual link, the setting of the next hop should be deferred until the calculation in Section 16.3. In the second case, the parent vertex is a network that directly connects the calculating router to the destination router. The list of next hops is then determined by examining the destination's router-LSA. For each link in the router-LSA that points back to the parent network, the link's Link Data field provides the IP address of a next hop router. The outgoing interface to use can then be derived from the next hop IP address (or it can be inherited from the parent network).