16.3. Examining transit areas' summary links This step is only performed by area border routers attached to one or more transit areas. Transit areas are those areas supporting one or more virtual links; their TransitCapability parameter has been set to TRUE in Step 2 of the Dijkstra algorithm (see Section 16.1). They are the only non-backbone areas that can carry data traffic that neither originates nor terminates in the area itself. The purpose of the calculation below is to examine the transit areas to see whether they provide any better (shorter) paths than the paths previously calculated in Sections 16.1 and 16.2. Any paths found that are better than or equal to previously discovered paths are installed in the routing table. The calculation proceeds as follows. All the transit areas' summary link advertisements are examined in turn. Each such summary link advertisement describes a route through a transit area Area A to a Network N (N's address is obtained by masking the advertisement's Link State ID with the network/subnet mask contained in the body of the advertisement) or in the case of a Type 4 summary link advertisement, to an AS boundary router N. Suppose also that the summary link advertisement was originated by an area border router BR. (1) If the cost advertised by the summary link advertisement is LSInfinity, or if the advertisement's LS age is equal to MaxAge, then examine the next advertisement. (2) If the summary link advertisement was originated by the calculating router itself, examine the next advertisement. (3) Look up the routing table entry for N. If it does not exist, or if the route type is other than intra-area or inter-area, or if the area associated with the routing table entry is not the backbone area, then examine the next advertisement. In other words, this calculation only updates backbone intra-area routes found in Section 16.1 and inter-area routes found in Section 16.2. (4) Look up the routing table entry for the advertising router BR associated with the Area A. If it is unreachable, examine the next advertisement. Otherwise, the cost to destination N is the sum of the cost in BR's Area A routing table entry and the cost advertised in the advertisement. Call this cost IAC.
(5) If this cost is less than the cost occurring in N's routing table entry, overwrite N's list of next hops with those used for BR, and set N's routing table cost to IAC. Else, if IAC is the same as N's current cost, add BR's list of next hops to N's list of next hops. In any case, the area associated with N's routing table entry must remain the backbone area, and the path type (either intra-area or inter-area) must also remain the same. It is important to note that the above calculation never makes unreachable destinations reachable, but instead just potentially finds better paths to already reachable destinations. Also, unlike Section 16.3 of [RFC 1247], the above calculation installs any better cost found into the routing table entry, from which it may be readvertised in summary link advertisements to other areas. As an example of the calculation, consider the Autonomous System pictured in Figure 17. There is a single non-backbone area (Area 1) that physically divides the backbone into two separate pieces. To maintain connectivity of the backbone, a virtual link has been configured between routers RT1 and RT4. On the right side of the figure, Network N1 belongs to the backbone. The dotted lines indicate that there is a much shorter intra-area ........................ . Area 1 (transit) . + . . | . +---+1 1+---+100 | . |RT2|----------|RT4|=========| . 1/+---+********* +---+ | . /******* . | . 1/*Virtual . | 1+---+/* Link . Net|work =======|RT1|* . | N1 +---+\ . | . \ . | . \ . | . 1\+---+1 1+---+20 | . |RT3|----------|RT5|=========| . +---+ +---+ | . . | ........................ + Figure 17: Routing through transit areas
backbone path between router RT5 and Network N1 (cost 20) than there is between Router RT4 and Network N1 (cost 100). Both Router RT4 and Router RT5 will inject summary link advertisements for Network N1 into Area 1. After the shortest-path tree has been calculated for the backbone in Section 16.1, Router RT1 (left end of the virtual link) will have calculated a path through Router RT4 for all data traffic destined for Network N1. However, since Router RT5 is so much closer to Network N1, all routers internal to Area 1 (e.g., Routers RT2 and RT3) will forward their Network N1 traffic towards Router RT5, instead of RT4. And indeed, after examining Area 1's summary link advertisements by the above calculation, Router RT1 will also forward Network N1 traffic towards RT5. Note that in this example the virtual link enables Network N1 traffic to be forwarded through the transit area Area 1, but the actual path the data traffic takes does not follow the virtual link. In other words, virtual links allow transit traffic to be forwarded through an area, but do not dictate the precise path that the traffic will take. 16.4. Calculating AS external routes AS external routes are calculated by examining AS external link advertisements. Each of the AS external link advertisements is considered in turn. Most AS external link advertisements describe routes to specific IP destinations. An AS external link advertisement can also describe a default route for the Autonomous System (Destination ID = DefaultDestination, network/subnet mask = 0x00000000). For each AS external link advertisement: (1) If the cost specified by the advertisement is LSInfinity, or if the advertisement's LS age is equal to MaxAge, then examine the next advertisement. (2) If the advertisement was originated by the calculating router itself, examine the next advertisement. (3) Call the destination described by the advertisement N. N's address is obtained by masking the advertisement's Link State ID with the network/subnet mask contained in the body of the advertisement. Look up the routing table entry for the AS boundary router (ASBR) that originated the advertisement. If no entry exists for router ASBR (i.e., ASBR is unreachable), do nothing with this advertisement and consider the next in the list.
Else, this advertisement describes an AS external path to destination N. Examine the forwarding address specified in the AS external link advertisement. This indicates the IP address to which packets for the destination should be forwarded. If the forwarding address is set to 0.0.0.0, packets should be sent to the ASBR itself. Otherwise, look up the forwarding address in the routing table. An intra-area or inter-area path must exist to the forwarding address. If no such path exists, do nothing with the advertisement and consider the next in the list. Call the routing table distance to the forwarding address X (when the forwarding address is set to 0.0.0.0, this is the distance to the ASBR itself), and the cost specified in the advertisement Y. X is in terms of the link state metric, and Y is a type 1 or 2 external metric. (4) Next, look up the routing table entry for the destination N. If no entry exists for N, install the AS external path to N, with next hop equal to the list of next hops to the forwarding address, and advertising router equal to ASBR. If the external metric type is 1, then the path-type is set to type 1 external and the cost is equal to X+Y. If the external metric type is 2, the path-type is set to type 2 external, the link state component of the route's cost is X, and the type 2 cost is Y. (5) Else, if the paths present in the table are not type 1 or type 2 external paths, do nothing (AS external paths have the lowest priority). (6) Otherwise, compare the cost of this new AS external path to the ones present in the table. Type 1 external paths are always shorter than type 2 external paths. Type 1 external paths are compared by looking at the sum of the distance to the forwarding address and the advertised type 1 metric (X+Y). Type 2 external paths are compared by looking at the advertised type 2 metrics, and then if necessary, the distance to the forwarding addresses. If the new path is shorter, it replaces the present paths in the routing table entry. If the new path is the same cost, it is added to the routing table entry's list of paths.
16.5. Incremental updates -- summary link advertisements When a new summary link advertisement is received, it is not necessary to recalculate the entire routing table. Call the destination described by the summary link advertisement N (N's address is obtained by masking the advertisement's Link State ID with the network/subnet mask contained in the body of the advertisement), and let Area A be the area to which the advertisement belongs. There are then two separate cases: Case 1: Area A is the backbone and/or the router is not an area border router. In this case, the following calculations must be performed. First, if there is presently an inter-area route to the destination N, N's routing table entry is invalidated, saving the entry's values for later comparisons. Then the calculation in Section 16.2 is run again for the single destination N. In this calculation, all of Area A's summary link advertisements that describe a route to N are examined. In addition, if the router is an area border router attached to one or more transit areas, the calculation in Section 16.3 must be run again for the single destination. If the results of these calculations have changed the cost/path to an AS boundary router (as would be the case for a Type 4 summary link advertisement) or to any forwarding addresses, all AS external link advertisements will have to be reexamined by rerunning the calculation in Section 16.4. Otherwise, if N is now newly unreachable, the calculation in Section 16.4 must be rerun for the single destination N, in case an alternate external route to N exists. Case 2: Area A is a transit area and the router is an area border router. In this case, the following calculations must be performed. First, if N's routing table entry presently contains one or more inter-area paths that utilize the transit area Area A, these paths should be removed. If this removes all paths from the routing table entry, the entry should be invalidated. The entry's old values should be saved for later comparisons. Next the calculation in Section 16.3 must be run again for the single destination N. If the results of this calculation have caused the cost to N to increase, the complete routing table calculation must be rerun starting with the Dijkstra algorithm specified in Section 16.1. Otherwise, if the cost/path to an AS boundary router (as would be the case for a Type 4 summary link advertisement) or to any forwarding addresses has changed, all AS external link advertisements will have to be reexamined by rerunning
the calculation in Section 16.4. Otherwise, if N is now newly unreachable, the calculation in Section 16.4 must be rerun for the single destination N, in case an alternate external route to N exists. 16.6. Incremental updates -- AS external link advertisements When a new AS external link advertisement is received, it is not necessary to recalculate the entire routing table. Call the destination described by the AS external link advertisement N. N's address is obtained by masking the advertisement's Link State ID with the network/subnet mask contained in the body of the advertisement. If there is already an intra-area or inter- area route to the destination, no recalculation is necessary (internal routes take precedence). Otherwise, the procedure in Section 16.4 will have to be performed, but only for those AS external link advertisements whose destination is N. Before this procedure is performed, the present routing table entry for N should be invalidated. 16.7. Events generated as a result of routing table changes Changes to routing table entries sometimes cause the OSPF area border routers to take additional actions. These routers need to act on the following routing table changes: o The cost or path type of a routing table entry has changed. If the destination described by this entry is a Network or AS boundary router, and this is not simply a change of AS external routes, new summary link advertisements may have to be generated (potentially one for each attached area, including the backbone). See Section 12.4.3 for more information. If a previously advertised entry has been deleted, or is no longer advertisable to a particular area, the advertisement must be flushed from the routing domain by setting its LS age to MaxAge and reflooding (see Section 14.1). o A routing table entry associated with a configured virtual link has changed. The destination of such a routing table entry is an area border router. The change indicates a modification to the virtual link's cost or viability. If the entry indicates that the area border router is newly reachable (via TOS 0), the corresponding virtual link is now
operational. An InterfaceUp event should be generated for the virtual link, which will cause a virtual adjacency to begin to form (see Section 10.3). At this time the virtual link's IP interface address and the virtual neighbor's Neighbor IP address are also calculated. If the entry indicates that the area border router is no longer reachable (via TOS 0), the virtual link and its associated adjacency should be destroyed. This means an InterfaceDown event should be generated for the associated virtual link. If the cost of the entry has changed, and there is a fully established virtual adjacency, a new router links advertisement for the backbone must be originated. This in turn may cause further routing table changes. 16.8. Equal-cost multipath The OSPF protocol maintains multiple equal-cost routes to all destinations. This can be seen in the steps used above to calculate the routing table, and in the definition of the routing table structure. Each one of the multiple routes will be of the same type (intra-area, inter-area, type 1 external or type 2 external), cost, and will have the same associated area. However, each route specifies a separate next hop and Advertising router. There is no requirement that a router running OSPF keep track of all possible equal-cost routes to a destination. An implementation may choose to keep only a fixed number of routes to any given destination. This does not affect any of the algorithms presented in this specification. 16.9. Building the non-zero-TOS portion of the routing table The OSPF protocol can calculate a different set of routes for each IP TOS (see Section 2.4). Support for TOS-based routing is optional. TOS-capable and non-TOS-capable routers can be mixed in an OSPF routing domain. Routers not supporting TOS calculate only the TOS 0 route to each destination. These routes are then used to forward all data traffic, regardless of the TOS indications in the data packet's IP header. A router that does not support TOS indicates this fact to the other OSPF routers by clearing the T-bit in the Options field of its router links
advertisement. The above sections detailing the routing table calculations handle the TOS 0 case only. In general, for routers supporting TOS-based routing, each piece of the routing table calculation must be rerun separately for the non-zero TOS values. When calculating routes for TOS X, only TOS X metrics can be used. Any link state advertisement may specify a separate cost for each TOS (a cost for TOS 0 must always be specified). The encoding of TOS in OSPF link state advertisements is described in Section 12.3. An advertisement can specify that it is restricted to TOS 0 (i.e., non-zero TOS is not handled) by clearing the T-bit in the link state advertisement's Option field. Such advertisements are not used when calculating routes for non-zero TOS. For this reason, it is possible that a destination is unreachable for some non-zero TOS. In this case, the TOS 0 path is used when forwarding packets (see Section 11.1). The following lists the modifications needed when running the routing table calculation for a non-zero TOS value (called TOS X). In general, routers and advertisements that do not support TOS are omitted from the calculation. Calculating the shortest-path tree (Section 16.1). Routers that do not support TOS-based routing should be omitted from the shortest-path tree calculation. These routers are identified as those having the T-bit reset in the Options field of their router links advertisements. Such routers should never be added to the Dijktra algorithm's candidate list, nor should their router links advertisements be examined when adding the stub networks to the tree. In particular, if the T-bit is reset in the calculating router's own router links advertisement, it does not run the shortest-path tree calculation for non-zero TOS values. Calculating the inter-area routes (Section 16.2). Inter-area paths are the concatenation of a path to an area border router with a summary link. When calculating TOS X routes, both path components must also specify TOS X. In other words, only TOS X paths to the area border router are examined, and the area border router must be advertising a TOS X route to the destination. Note that this means that summary link advertisements having the T-bit reset in their Options field are not considered.
Examining transit areas' summary links (Section 16.3). This calculation again considers the concatenation of a path to an area border router with a summary link. As with inter-area routes, only TOS X paths to the area border router are examined, and the area border router must be advertising a TOS X route to the destination. Calculating AS external routes (Section 16.4). This calculation considers the concatenation of a path to a forwarding address with an AS external link. Only TOS X paths to the forwarding address are examined, and the AS boundary router must be advertising a TOS X route to the destination. Note that this means that AS external link advertisements having the T-bit reset in their Options field are not considered. In addition, the advertising AS boundary router must also be reachable for its advertisements to be considered (see Section 16.4). However, if the advertising router and the forwarding address are not one in the same, the advertising router need only be reachable via TOS 0.
Footnotes The graph's vertices represent either routers, transit networks, or stub networks. Since routers may belong to multiple areas, it is not possible to color the graph's vertices. It is possible for all of a router's interfaces to be unnumbered point-to-point links. In this case, an IP address must be assigned to the router. This address will then be advertised in the router's router links advertisement as a host route. Note that in these cases both interfaces, the non-virtual and the virtual, would have the same IP address. Note that no host route is generated for, and no IP packets can be addressed to, interfaces to unnumbered point-to-point networks. This is regardless of such an interface's state. It is instructive to see what happens when the Designated Router for the network crashes. Call the Designated Router for the network RT1, and the Backup Designated Router RT2. If Router RT1 crashes (or maybe its interface to the network dies), the other routers on the network will detect RT1's absence within RouterDeadInterval seconds. All routers may not detect this at precisely the same time; the routers that detect RT1's absence before RT2 does will, for a time, select RT2 to be both Designated Router and Backup Designated Router. When RT2 detects that RT1 is gone it will move itself to Designated Router. At this time, the remaining router having highest Router Priority will be selected as Backup Designated Router. On point-to-point networks, the lower level protocols indicate whether the neighbor is up and running. Likewise, existence of the neighbor on virtual links is indicated by the routing table calculation. However, in both these cases, the Hello Protocol is still used. This ensures that communication between the neighbors is bidirectional, and that each of the neighbors has a functioning routing protocol layer. When the identity of the Designated Router is changing, it may be quite common for a neighbor in this state to send the router a Database Description packet; this means that there is some momentary disagreement on the Designated Router's identity. Note that it is possible for a router to resynchronize any of its fully established adjacencies by setting the adjacency's state back to ExStart. This will cause the other end of the adjacency to
process a SeqNumberMismatch event, and therefore to also go back to ExStart state. The address space of IP networks and the address space of OSPF Router IDs may overlap. That is, a network may have an IP address which is identical (when considered as a 32-bit number) to some router's Router ID. It is assumed that, for two different address ranges matching the destination, one range is more specific than the other. Non- contiguous subnet masks can be configured to violate this assumption. Such subnet mask configurations cannot be handled by the OSPF protocol. MaxAgeDiff is an architectural constant. It indicates the maximum dispersion of ages, in seconds, that can occur for a single link state instance as it is flooded throughout the routing domain. If two advertisements differ by more than this, they are assumed to be different instances of the same advertisement. This can occur when a router restarts and loses track of the advertisement's previous LS sequence number. See Section 13.4 for more details. When two advertisements have different LS checksums, they are assumed to be separate instances. This can occur when a router restarts, and loses track of the advertisement's previous LS sequence number. In the case where the two advertisements have the same LS sequence number, it is not possible to determine which link state is actually newer. If the wrong advertisement is accepted as newer, the originating router will originate another instance. See Section 13.4 for further details. There is one instance where a lookup must be done based on partial information. This is during the routing table calculation, when a network links advertisement must be found based solely on its Link State ID. The lookup in this case is still well defined, since no two network links advertisements can have the same Link State ID. This clause covers the case: Inter-area routes are not summarized to the backbone. This is because inter-area routes are always associated with the backbone area. This clause is only invoked when Area A is a Transit area supporting one or more virtual links. For example, in the area configuration of Figure 6, Router RT11 need only originate a single summary link having the (collapsed) destination N9-N11,H1 into its connected Transit area Area 2, since all of its other eligible routes have next hops belonging to Area 2 (and as such only need be advertised by other area border routers; in this case, Routers RT10
and RT7). By keeping more information in the routing table, it is possible for an implementation to recalculate the shortest path tree only for a single area. In fact, there are incremental algorithms that allow an implementation to recalculate only a portion of a single area's shortest path tree [BBN]. However, these algorithms are beyond the scope of this specification. This is how the Link state request list is emptied, which eventually causes the neighbor state to transition to Full. See Section 10.9 for more details. It should be a relatively rare occurrence for an advertisement's LS age to reach MaxAge in this fashion. Usually, the advertisement will be replaced by a more recent instance before it ages out. Only the TOS 0 routes are important here because all OSPF protocol packets are sent with TOS = 0. See Appendix A. It may be the case that paths to certain destinations do not vary based on TOS. For these destinations, the routing calculation need not be repeated for each TOS value. In addition, there need only be a single routing table entry for these destinations (instead of a separate entry for each TOS value). Strictly speaking, because of equal-cost multipath, the algorithm does not create a tree. We continue to use the "tree" terminology because that is what occurs most often in the existing literature. Note that the presence of any link back to V is sufficient; it need not be the matching half of the link under consideration from V to W. This is enough to ensure that, before data traffic flows between a pair of neighboring routers, their link state databases will be synchronized. When the forwarding address is non-zero, it should point to a router belonging to another Autonomous System. See Section 12.4.5 for more details.
References [BBN] McQuillan, J., I. Richer and E. Rosen, "ARPANET Routing Algorithm Improvements", BBN Technical Report 3803, April 1978. [DEC] Digital Equipment Corporation, "Information processing systems -- Data communications -- Intermediate System to Intermediate System Intra- Domain Routing Protocol", October 1987. [McQuillan] McQuillan, J. et.al., "The New Routing Algorithm for the Arpanet", IEEE Transactions on Communications, May 1980. [Perlman] Perlman, R., "Fault-Tolerant Broadcast of Routing Information", Computer Networks, December 1983. [RFC 791] Postel, J., "Internet Protocol", STD 5, RFC 791, USC/Information Sciences Institute, September 1981. [RFC 905] McKenzie, A., "ISO Transport Protocol specification ISO DP 8073", RFC 905, ISO, April 1984. [RFC 1112] Deering, S., "Host extensions for IP multicasting", STD 5, RFC 1112, Stanford University, May 1988. [RFC 1213] McCloghrie, K., and M. Rose, "Management Information Base for network management of TCP/IP-based internets: MIB-II", STD 17, RFC 1213, Hughes LAN Systems, Performance Systems International, March 1991. [RFC 1247] Moy, J., "OSPF Version 2", RFC 1247, Proteon, Inc., July 1991. [RFC 1519] Fuller, V., T. Li, J. Yu, and K. Varadhan, "Classless Inter-Domain Routing (CIDR): an Address Assignment and Aggregation Strategy", RFC1519, BARRNet, cisco, MERIT, OARnet, September 1993. [RFC 1340] Reynolds, J., and J. Postel, "Assigned Numbers", STD 2, RFC 1340, USC/Information Sciences Institute, July 1992. [RFC 1349] Almquist, P., "Type of Service in the Internet Protocol Suite", RFC 1349, July 1992.
[RS-85-153] Leiner, B., et.al., "The DARPA Internet Protocol Suite", DDN Protocol Handbook, April 1985.
A. OSPF data formats This appendix describes the format of OSPF protocol packets and OSPF link state advertisements. The OSPF protocol runs directly over the IP network layer. Before any data formats are described, the details of the OSPF encapsulation are explained. Next the OSPF Options field is described. This field describes various capabilities that may or may not be supported by pieces of the OSPF routing domain. The OSPF Options field is contained in OSPF Hello packets, Database Description packets and in OSPF link state advertisements. OSPF packet formats are detailed in Section A.3. A description of OSPF link state advertisements appears in Section A.4. A.1 Encapsulation of OSPF packets OSPF runs directly over the Internet Protocol's network layer. OSPF packets are therefore encapsulated solely by IP and local data-link headers. OSPF does not define a way to fragment its protocol packets, and depends on IP fragmentation when transmitting packets larger than the network MTU. The OSPF packet types that are likely to be large (Database Description Packets, Link State Request, Link State Update, and Link State Acknowledgment packets) can usually be split into several separate protocol packets, without loss of functionality. This is recommended; IP fragmentation should be avoided whenever possible. Using this reasoning, an attempt should be made to limit the sizes of packets sent over virtual links to 576 bytes. However, if necessary, the length of OSPF packets can be up to 65,535 bytes (including the IP header). The other important features of OSPF's IP encapsulation are: o Use of IP multicast. Some OSPF messages are multicast, when sent over multi-access networks. Two distinct IP multicast addresses are used. Packets sent to these multicast addresses should never be forwarded; they are meant to travel a single hop only. To ensure that these packets will not travel multiple hops, their IP TTL must be set to 1. AllSPFRouters This multicast address has been assigned the value 188.8.131.52. All routers running OSPF should be prepared to receive packets sent to this address. Hello packets are always sent to this destination. Also, certain OSPF
protocol packets are sent to this address during the flooding procedure. AllDRouters This multicast address has been assigned the value 184.108.40.206. Both the Designated Router and Backup Designated Router must be prepared to receive packets destined to this address. Certain OSPF protocol packets are sent to this address during the flooding procedure. o OSPF is IP protocol number 89. This number has been registered with the Network Information Center. IP protocol number assignments are documented in [RFC 1340]. o Routing protocol packets are sent with IP TOS of 0. The OSPF protocol supports TOS-based routing. Routes to any particular destination may vary based on TOS. However, all OSPF routing protocol packets are sent using the normal service TOS value of binary 0000 defined in [RFC 1349]. o Routing protocol packets are sent with IP precedence set to Internetwork Control. OSPF protocol packets should be given precedence over regular IP data traffic, in both sending and receiving. Setting the IP precedence field in the IP header to Internetwork Control [RFC 791] may help implement this objective.
A.2 The Options field The OSPF Options field is present in OSPF Hello packets, Database Description packets and all link state advertisements. The Options field enables OSPF routers to support (or not support) optional capabilities, and to communicate their capability level to other OSPF routers. Through this mechanism routers of differing capabilities can be mixed within an OSPF routing domain. When used in Hello packets, the Options field allows a router to reject a neighbor because of a capability mismatch. Alternatively, when capabilities are exchanged in Database Description packets a router can choose not to forward certain link state advertisements to a neighbor because of its reduced functionality. Lastly, listing capabilities in link state advertisements allows routers to route traffic around reduced functionality routers, by excluding them from parts of the routing table calculation. Two capabilities are currently defined. For each capability, the effect of the capability's appearance (or lack of appearance) in Hello packets, Database Description packets and link state advertisements is specified below. For example, the ExternalRoutingCapability (below called the E-bit) has meaning only in OSPF Hello Packets. Routers should reset (i.e. clear) the unassigned part of the capability field when sending Hello packets or Database Description packets and when originating link state advertisements. Additional capabilities may be assigned in the future. Routers encountering unrecognized capabilities in received Hello Packets, Database Description packets or link state advertisements should ignore the capability and process the packet/advertisement normally. +-+-+-+-+-+-+-+-+ | | | | | | |E|T| +-+-+-+-+-+-+-+-+ The Options field T-bit This describes the router's TOS capability. If the T-bit is reset, then the router supports only a single TOS (TOS 0). Such a router is also said to be incapable of TOS-routing, and elsewhere in this document referred to as a TOS-0-only router. The absence of the T-bit in a router links advertisement causes the router to be skipped when building a non-zero TOS shortest- path tree (see Section 16.9). In other words, routers incapable
of TOS routing will be avoided as much as possible when forwarding data traffic requesting a non-zero TOS. The absence of the T-bit in a summary link advertisement or an AS external link advertisement indicates that the advertisement is describing a TOS 0 route only (and not routes for non-zero TOS). E-bit This bit reflects the associated area's ExternalRoutingCapability. AS external link advertisements are not flooded into/through OSPF stub areas (see Section 3.6). The E-bit ensures that all members of a stub area agree on that area's configuration. The E-bit is meaningful only in OSPF Hello packets. When the E-bit is reset in the Hello packet sent out a particular interface, it means that the router will neither send nor receive AS external link state advertisements on that interface (in other words, the interface connects to a stub area). Two routers will not become neighbors unless they agree on the state of the E-bit.
A.3 OSPF Packet Formats There are five distinct OSPF packet types. All OSPF packet types begin with a standard 24 byte header. This header is described first. Each packet type is then described in a succeeding section. In these sections each packet's division into fields is displayed, and then the field definitions are enumerated. All OSPF packet types (other than the OSPF Hello packets) deal with lists of link state advertisements. For example, Link State Update packets implement the flooding of advertisements throughout the OSPF routing domain. Because of this, OSPF protocol packets cannot be parsed unless the format of link state advertisements is also understood. The format of Link state advertisements is described in Section A.4. The receive processing of OSPF packets is detailed in Section 8.2. The sending of OSPF packets is explained in Section 8.1.
A.3.1 The OSPF packet header Every OSPF packet starts with a common 24 byte header. This header contains all the necessary information to determine whether the packet should be accepted for further processing. This determination is described in Section 8.2 of the specification. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version # | Type | Packet length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Router ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Area ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Checksum | AuType | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Version # The OSPF version number. This specification documents version 2 of the protocol. Type The OSPF packet types are as follows. The format of each of these packet types is described in a succeeding section. Type Description ________________________________ 1 Hello 2 Database Description 3 Link State Request 4 Link State Update 5 Link State Acknowledgment
Packet length The length of the protocol packet in bytes. This length includes the standard OSPF header. Router ID The Router ID of the packet's source. In OSPF, the source and destination of a routing protocol packet are the two ends of an (potential) adjacency. Area ID A 32 bit number identifying the area that this packet belongs to. All OSPF packets are associated with a single area. Most travel a single hop only. Packets travelling over a virtual link are labelled with the backbone Area ID of 0.0.0.0. Checksum The standard IP checksum of the entire contents of the packet, starting with the OSPF packet header but excluding the 64-bit authentication field. This checksum is calculated as the 16-bit one's complement of the one's complement sum of all the 16-bit words in the packet, excepting the authentication field. If the packet's length is not an integral number of 16-bit words, the packet is padded with a byte of zero before checksumming. AuType Identifies the authentication scheme to be used for the packet. Authentication is discussed in Appendix D of the specification. Consult Appendix D for a list of the currently defined authentication types. Authentication A 64-bit field for use by the authentication scheme.
A.3.2 The Hello packet Hello packets are OSPF packet type 1. These packets are sent periodically on all interfaces (including virtual links) in order to establish and maintain neighbor relationships. In addition, Hello Packets are multicast on those physical networks having a multicast or broadcast capability, enabling dynamic discovery of neighboring routers. All routers connected to a common network must agree on certain parameters (Network mask, HelloInterval and RouterDeadInterval). These parameters are included in Hello packets, so that differences can inhibit the forming of neighbor relationships. A detailed explanation of the receive processing for Hello packets is presented in Section 10.5. The sending of Hello packets is covered in Section 9.5. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version # | 1 | Packet length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Router ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Area ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Checksum | AuType | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Network Mask | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | HelloInterval | Options | Rtr Pri | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RouterDeadInterval | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Designated Router | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Backup Designated Router | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... |
Network mask The network mask associated with this interface. For example, if the interface is to a class B network whose third byte is used for subnetting, the network mask is 0xffffff00. Options The optional capabilities supported by the router, as documented in Section A.2. HelloInterval The number of seconds between this router's Hello packets. Rtr Pri This router's Router Priority. Used in (Backup) Designated Router election. If set to 0, the router will be ineligible to become (Backup) Designated Router. RouterDeadInterval The number of seconds before declaring a silent router down. Designated Router The identity of the Designated Router for this network, in the view of the advertising router. The Designated Router is identified here by its IP interface address on the network. Set to 0.0.0.0 if there is no Designated Router. Backup Designated Router The identity of the Backup Designated Router for this network, in the view of the advertising router. The Backup Designated Router is identified here by its IP interface address on the network. Set to 0.0.0.0 if there is no Backup Designated Router. Neighbor The Router IDs of each router from whom valid Hello packets have been seen recently on the network. Recently means in the last RouterDeadInterval seconds.
A.3.3 The Database Description packet Database Description packets are OSPF packet type 2. These packets are exchanged when an adjacency is being initialized. They describe the contents of the topological database. Multiple packets may be used to describe the database. For this purpose a poll-response procedure is used. One of the routers is designated to be master, the other a slave. The master sends Database Description packets (polls) which are acknowledged by Database Description packets sent by the slave (responses). The responses are linked to the polls via the packets' DD sequence numbers. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version # | 2 | Packet length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Router ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Area ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Checksum | AuType | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0 | 0 | Options |0|0|0|0|0|I|M|MS +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | DD sequence number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | +- -+ | A | +- Link State Advertisement -+ | Header | +- -+ | | +- -+ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | The format of the Database Description packet is very similar to both the Link State Request and Link State Acknowledgment packets. The main part of all three is a list of items, each item describing
a piece of the topological database. The sending of Database Description Packets is documented in Section 10.8. The reception of Database Description packets is documented in Section 10.6. 0 These fields are reserved. They must be 0. Options The optional capabilities supported by the router, as documented in Section A.2. I-bit The Init bit. When set to 1, this packet is the first in the sequence of Database Description Packets. M-bit The More bit. When set to 1, it indicates that more Database Description Packets are to follow. MS-bit The Master/Slave bit. When set to 1, it indicates that the router is the master during the Database Exchange process. Otherwise, the router is the slave. DD sequence number Used to sequence the collection of Database Description Packets. The initial value (indicated by the Init bit being set) should be unique. The DD sequence number then increments until the complete database description has been sent. The rest of the packet consists of a (possibly partial) list of the topological database's pieces. Each link state advertisement in the database is described by its link state advertisement header. The link state advertisement header is documented in Section A.4.1. It contains all the information required to uniquely identify both the advertisement and the advertisement's current instance.