12. Link State Advertisements Each router in the Autonomous System originates one or more link state advertisements. There are five distinct types of link state advertisements, which are described in Section 4.3. The collection of link state advertisements forms the link state or topological database. Each separate type of advertisement has a separate
Type Dest Area Path Type Cost Next Adv. Hop(s) Router(s) ________________________________________________________________ N Ib 0 intra-area 16 RT3 * N Ia 0 intra-area 21 RT3 * BR RT3 0 intra-area 1 * * BR RT10 0 intra-area 16 RT3 * BR RT11 0 intra-area 19 RT3 * ________________________________________________________________ N N9-N11,H1 0 inter-area 20 RT3 RT11 Table 14: Changes resulting from an additional virtual link. function. Router links and network links advertisements describe how an area's routers and networks are interconnected. Summary link advertisements provide a way of condensing an area's routing information. AS external advertisements provide a way of transparently advertising externally-derived routing information throughout the Autonomous System. Each link state advertisement begins with a standard 20-byte header. This link state advertisement header is discussed below. 12.1. The Link State Advertisement Header The link state advertisement header contains the LS type, Link State ID and Advertising Router fields. The combination of these three fields uniquely identifies the link state advertisement. There may be several instances of an advertisement present in the Autonomous System, all at the same time. It must then be determined which instance is more recent. This determination is made by examining the LS sequence, LS checksum and LS age fields. These fields are also contained in the 20-byte link state advertisement header. Several of the OSPF packet types list link state advertisements. When the instance is not important, an advertisement is referred to by its LS type, Link State ID and Advertising Router (see Link State Request Packets). Otherwise, the LS sequence number, LS age and LS checksum fields must also be referenced.
A detailed explanation of the fields contained in the link state advertisement header follows. 12.1.1. LS age This field is the age of the link state advertisement in seconds. It should be processed as an unsigned 16-bit integer. It is set to 0 when the link state advertisement is originated. It must be incremented by InfTransDelay on every hop of the flooding procedure. Link state advertisements are also aged as they are held in each router's database. The age of a link state advertisement is never incremented past MaxAge. Advertisements having age MaxAge are not used in the routing table calculation. When an advertisement's age first reaches MaxAge, it is reflooded. A link state advertisement of age MaxAge is finally flushed from the database when it is no longer needed to ensure database synchronization. For more information on the aging of link state advertisements, consult Section 14. The LS age field is examined when a router receives two instances of a link state advertisement, both having identical LS sequence numbers and LS checksums. An instance of age MaxAge is then always accepted as most recent; this allows old advertisements to be flushed quickly from the routing domain. Otherwise, if the ages differ by more than MaxAgeDiff, the instance having the smaller age is accepted as most recent. See Section 13.1 for more details. 12.1.2. Options The Options field in the link state advertisement header indicates which optional capabilities are associated with the advertisement. OSPF's optional capabilities are described in Section 4.5. There are currently two optional capabilities defined; they are represented by the T-bit and E-bit found in the Options field. The rest of the Options field should be set to zero. The E-bit represents OSPF's ExternalRoutingCapability. This bit should be set in all advertisements associated with the backbone, and all advertisements associated with non-stub areas (see Section 3.6). It should also be set in all AS external link advertisements. It should be reset in all
router links, network links and summary link advertisements associated with a stub area. For all link state advertisements, the setting of the E-bit is for informational purposes only; it does not affect the routing table calculation. The T-bit represents OSPF's TOS routing capability. This bit should be set in a router links advertisement if and only if the router is capable of calculating separate routes for each IP TOS (see Section 2.4). The T-bit should always be set in network links advertisements. It should be set in summary link and AS external link advertisements if and only if the advertisement describes paths for all TOS values, instead of just the TOS 0 path. Note that, with the T-bit set, there may still be only a single metric in the advertisement (the TOS 0 metric). This would mean that paths for non-zero TOS exist, but are equivalent to the TOS 0 path. A link state advertisement's T-bit is examined when calculating the routing table's non-zero TOS paths (see Section 16.9). 12.1.3. LS type The LS type field dictates the format and function of the link state advertisement. Advertisements of different types have different names (e.g., router links or network links). All advertisement types, except the AS external link advertisements (LS type = 5), are flooded throughout a single area only. AS external link advertisements are flooded throughout the entire Autonomous System, excepting stub areas (see Section 3.6). Each separate advertisement type is briefly described below in Table 15. 12.1.4. Link State ID This field identifies the piece of the routing domain that is being described by the advertisement. Depending on the advertisement's LS type, the Link State ID takes on the values listed in Table 16. Actually, for Type 3 summary link (LS type = 3) advertisements and AS external link (LS type = 5) advertisements, the Link State ID may additionally have one or more of the destination network's "host" bits set. For example, when originating an AS external link for the network 10.0.0.0 with mask of 255.0.0.0, the Link State ID
LS Type Advertisement description __________________________________________________ 1 These are the router links advertisements. They describe the collected states of the router's interfaces. For more information, consult Section 12.4.1. __________________________________________________ 2 These are the network links advertisements. They describe the set of routers attached to the network. For more information, consult Section 12.4.2. __________________________________________________ 3 or 4 These are the summary link advertisements. They describe inter-area routes, and enable the condensation of routing information at area borders. Originated by area border routers, the Type 3 advertisements describe routes to networks while the Type 4 advertisements describe routes to AS boundary routers. __________________________________________________ 5 These are the AS external link advertisements. Originated by AS boundary routers, they describe routes to destinations external to the Autonomous System. A default route for the Autonomous System can also be described by an AS external link advertisement. Table 15: OSPF link state advertisements.
LS Type Link State ID _______________________________________________ 1 The originating router's Router ID. 2 The IP interface address of the network's Designated Router. 3 The destination network's IP address. 4 The Router ID of the described AS boundary router. 5 The destination network's IP address. Table 16: The advertisement's Link State ID. can be set to anything in the range 10.0.0.0 through 10.255.255.255 inclusive (although 10.0.0.0 should be used whenever possible). The freedom to set certain host bits allows a router to originate separate advertisements for two networks having the same address but different masks. See Appendix F for details. When the link state advertisement is describing a network (LS type = 2, 3 or 5), the network's IP address is easily derived by masking the Link State ID with the network/subnet mask contained in the body of the link state advertisement. When the link state advertisement is describing a router (LS type = 1 or 4), the Link State ID is always the described router's OSPF Router ID. When an AS external advertisement (LS Type = 5) is describing a default route, its Link State ID is set to DefaultDestination (0.0.0.0). 12.1.5. Advertising Router This field specifies the OSPF Router ID of the advertisement's originator. For router links advertisements, this field is identical to the Link State ID field. Network link advertisements are originated by the network's Designated Router. Summary link advertisements are originated by area border routers. AS external link advertisements are originated by AS boundary routers. 12.1.6. LS sequence number The sequence number field is a signed 32-bit integer. It is used to detect old and duplicate link state advertisements.
The space of sequence numbers is linearly ordered. The larger the sequence number (when compared as signed 32-bit integers) the more recent the advertisement. To describe to sequence number space more precisely, let N refer in the discussion below to the constant 2**31. The sequence number -N (0x80000000) is reserved (and unused). This leaves -N + 1 (0x80000001) as the smallest (and therefore oldest) sequence number. A router uses this sequence number the first time it originates any link state advertisement. Afterwards, the advertisement's sequence number is incremented each time the router originates a new instance of the advertisement. When an attempt is made to increment the sequence number past the maximum value of N - 1 (0x7fffffff), the current instance of the advertisement must first be flushed from the routing domain. This is done by prematurely aging the advertisement (see Section 14.1) and reflooding it. As soon as this flood has been acknowledged by all adjacent neighbors, a new instance can be originated with sequence number of -N + 1 (0x80000001). The router may be forced to promote the sequence number of one of its advertisements when a more recent instance of the advertisement is unexpectedly received during the flooding process. This should be a rare event. This may indicate that an out-of-date advertisement, originated by the router itself before its last restart/reload, still exists in the Autonomous System. For more information see Section 13.4. 12.1.7. LS checksum This field is the checksum of the complete contents of the advertisement, excepting the LS age field. The LS age field is excepted so that an advertisement's age can be incremented without updating the checksum. The checksum used is the same that is used for ISO connectionless datagrams; it is commonly referred to as the Fletcher checksum. It is documented in Annex B of [RFC 905]. The link state advertisement header also contains the length of the advertisement in bytes; subtracting the size of the LS age field (two bytes) yields the amount of data to checksum. The checksum is used to detect data corruption of an advertisement. This corruption can occur while an advertisement is being flooded, or while it is being held in a router's memory. The LS checksum field cannot take on the value of zero; the occurrence of such a value should be
considered a checksum failure. In other words, calculation of the checksum is not optional. The checksum of a link state advertisement is verified in two cases: a) when it is received in a Link State Update Packet and b) at times during the aging of the link state database. The detection of a checksum failure leads to separate actions in each case. See Sections 13 and 14 for more details. Whenever the LS sequence number field indicates that two instances of an advertisement are the same, the LS checksum field is examined. If there is a difference, the instance with the larger LS checksum is considered to be most recent. See Section 13.1 for more details. 12.2. The link state database A router has a separate link state database for every area to which it belongs. The link state database has been referred to elsewhere in the text as the topological database. All routers belonging to the same area have identical topological databases for the area. The databases for each individual area are always dealt with separately. The shortest path calculation is performed separately for each area (see Section 16). Components of the area topological database are flooded throughout the area only. Finally, when an adjacency (belonging to Area A) is being brought up, only the database for Area A is synchronized between the two routers. The area database is composed of router links advertisements, network links advertisements, and summary link advertisements (all listed in the area data structure). In addition, external routes (AS external advertisements) are included in all non-stub area databases (see Section 3.6). An implementation of OSPF must be able to access individual pieces of an area database. This lookup function is based on an advertisement's LS type, Link State ID and Advertising Router. There will be a single instance (the most up-to- date) of each link state advertisement in the database. The database lookup function is invoked during the link state flooding procedure (Section 13) and the routing table calculation (Section 16). In addition, using this lookup function the router can determine whether it has itself ever
originated a particular link state advertisement, and if so, with what LS sequence number. A link state advertisement is added to a router's database when either a) it is received during the flooding process (Section 13) or b) it is originated by the router itself (Section 12.4). A link state advertisement is deleted from a router's database when either a) it has been overwritten by a newer instance during the flooding process (Section 13) or b) the router originates a newer instance of one of its self-originated advertisements (Section 12.4) or c) the advertisement ages out and is flushed from the routing domain (Section 14). Whenever a link state advertisement is deleted from the database it must also be removed from all neighbors' Link state retransmission lists (see Section 10). 12.3. Representation of TOS All OSPF link state advertisements (with the exception of network links advertisements) specify metrics. In router links advertisements, the metrics indicate the costs of the described interfaces. In summary link and AS external link advertisements, the metric indicates the cost of the described path. In all of these advertisements, a separate metric can be specified for each IP TOS. The encoding of TOS in OSPF link state advertisements is specified in Table 17. That table relates the OSPF encoding to the IP packet header's TOS field (defined in [RFC 1349]). The OSPF encoding is expressed as a decimal integer, and the IP packet header's TOS field is expressed in the binary TOS values used in [RFC 1349].
OSPF encoding RFC 1349 TOS values ___________________________________________ 0 0000 normal service 2 0001 minimize monetary cost 4 0010 maximize reliability 6 0011 8 0100 maximize throughput 10 0101 12 0110 14 0111 16 1000 minimize delay 18 1001 20 1010 22 1011 24 1100 26 1101 28 1110 30 1111 Table 17: Representing TOS in OSPF. Each OSPF link state advertisement must specify the TOS 0 metric. Other TOS metrics, if they appear, must appear in order of increasing TOS encoding. For example, the TOS 8 (maximize throughput) metric must always appear before the TOS 16 (minimize delay) metric when both are specified. If a metric for some non-zero TOS is not specified, its cost defaults to the cost for TOS 0, unless the T-bit is reset in the advertisement's Options field (see Section 12.1.2 for more details). 12.4. Originating link state advertisements Into any given OSPF area, a router will originate several link state advertisements. Each router originates a router links advertisement. If the router is also the Designated Router for any of the area's networks, it will originate network links advertisements for those networks. Area border routers originate a single summary link advertisement for each known inter-area destination. AS boundary routers originate a single AS external link advertisement for each known AS external destination. Destinations are advertised one at a time so that the change in any single route can be flooded without reflooding the entire
collection of routes. During the flooding procedure, many link state advertisements can be carried by a single Link State Update packet. As an example, consider Router RT4 in Figure 6. It is an area border router, having a connection to Area 1 and the backbone. Router RT4 originates 5 distinct link state advertisements into the backbone (one router links, and one summary link for each of the networks N1-N4). Router RT4 will also originate 8 distinct link state advertisements into Area 1 (one router links and seven summary link advertisements as pictured in Figure 7). If RT4 has been selected as Designated Router for Network N3, it will also originate a network links advertisement for N3 into Area 1. In this same figure, Router RT5 will be originating 3 distinct AS external link advertisements (one for each of the networks N12-N14). These will be flooded throughout the entire AS, assuming that none of the areas have been configured as stubs. However, if area 3 has been configured as a stub area, the external advertisements for networks N12-N14 will not be flooded into area 3 (see Section 3.6). Instead, Router RT11 would originate a default summary link advertisement that would be flooded throughout area 3 (see Section 12.4.3). This instructs all of area 3's internal routers to send their AS external traffic to RT11. Whenever a new instance of a link state advertisement is originated, its LS sequence number is incremented, its LS age is set to 0, its LS checksum is calculated, and the advertisement is added to the link state database and flooded out the appropriate interfaces. See Section 13.2 for details concerning the installation of the advertisement into the link state database. See Section 13.3 for details concerning the flooding of newly originated advertisements. The ten events that can cause a new instance of a link state advertisement to be originated are: (1) The LS age field of one of the router's self-originated advertisements reaches the value LSRefreshTime. In this case, a new instance of the link state advertisement is originated, even though the contents of the advertisement (apart from the link state advertisement header) will be the same. This guarantees periodic originations of all link state advertisements. This periodic updating of link state
advertisements adds robustness to the link state algorithm. Link state advertisements that solely describe unreachable destinations should not be refreshed, but should instead be flushed from the routing domain (see Section 14.1). When whatever is being described by a link state advertisement changes, a new advertisement is originated. However, two instances of the same link state advertisement may not be originated within the time period MinLSInterval. This may require that the generation of the next instance be delayed by up to MinLSInterval. The following events may cause the contents of a link state advertisement to change. These events should cause new originations if and only if the contents of the new advertisement would be different: (2) An interface's state changes (see Section 9.1). This may mean that it is necessary to produce a new instance of the router links advertisement. (3) An attached network's Designated Router changes. A new router links advertisement should be originated. Also, if the router itself is now the Designated Router, a new network links advertisement should be produced. If the router itself is no longer the Designated Router, any network links advertisement that it might have originated for the network should be flushed from the routing domain (see Section 14.1). (4) One of the neighboring routers changes to/from the FULL state. This may mean that it is necessary to produce a new instance of the router links advertisement. Also, if the router is itself the Designated Router for the attached network, a new network links advertisement should be produced. The next four events concern area border routers only: (5) An intra-area route has been added/deleted/modified in the routing table. This may cause a new instance of a summary links advertisement (for this route) to be originated in each attached area (possibly including the backbone). (6) An inter-area route has been added/deleted/modified in the routing table. This may cause a new instance of a summary
links advertisement (for this route) to be originated in each attached area (but NEVER for the backbone). (7) The router becomes newly attached to an area. The router must then originate summary link advertisements into the newly attached area for all pertinent intra-area and inter- area routes in the router's routing table. See Section 12.4.3 for more details. (8) When the state of one of the router's configured virtual links changes, it may be necessary to originate a new router links advertisement into the virtual link's transit area (see the discussion of the router links advertisement's bit V in Section 12.4.1), as well as originating a new router links advertisement into the backbone. The last two events concern AS boundary routers (and former AS boundary routers) only: (9) An external route gained through direct experience with an external routing protocol (like EGP) changes. This will cause an AS boundary router to originate a new instance of an AS external link advertisement. (10) A router ceases to be an AS boundary router, perhaps after restarting. In this situation the router should flush all AS external link advertisements that it had previously originated. These advertisements can be flushed via the premature aging procedure specified in Section 14.1. The construction of each type of link state advertisement is explained in detail below. In general, these sections describe the contents of the advertisement body (i.e., the part coming after the 20-byte advertisement header). For information concerning the building of the link state advertisement header, see Section 12.1. 12.4.1. Router links A router originates a router links advertisement for each area that it belongs to. Such an advertisement describes the collected states of the router's links to the area. The advertisement is flooded throughout the particular area, and no further.
.................................... . 192.1.2 Area 1 . . + . . | . . | 3+---+1 . . N1 |--|RT1|-----+ . . | +---+ . . | _______N3 . . + / . 1+---+ . * 192.1.1 *------|RT4| . + /_______/ . +---+ . | / | . . | 3+---+1 / | . . N2 |--|RT2|-----+ 1| . . | +---+ +---+8 . 6+---+ . | |RT3|----------------|RT6| . + +---+ . +---+ . 192.1.3 |2 . 184.108.40.206|7 . | . | . +------------+ . . 192.1.4 (N4) . .................................... Figure 15: Area 1 with IP addresses shown The format of a router links advertisement is shown in Appendix A (Section A.4.2). The first 20 bytes of the advertisement consist of the generic link state advertisement header that was discussed in Section 12.1. Router links advertisements have LS type = 1. The router indicates whether it is willing to calculate separate routes for each IP TOS by setting (or resetting) the T-bit of the link state advertisement's Options field. A router also indicates whether it is an area border router, or an AS boundary router, by setting the appropriate bits (bit B and bit E, respectively) in its router links advertisements. This enables paths to those types of routers to be saved in the routing table, for later processing of summary link advertisements and AS external link advertisements. Bit B should be set whenever the router is actively attached to two or more areas, even if the router is not currently attached to the OSPF backbone area. Bit E should never be set in a router links advertisement for a stub area (stub areas cannot contain AS boundary routers). In addition, the router sets bit V in its router links
advertisement for Area A if and only if it is the endpoint of an active virtual link using Area A as its Transit area. This enables the other routers attached to Area A to discover whether the area supports any virtual links (i.e., is a transit area). The router links advertisement then describes the router's working connections (i.e., interfaces or links) to the area. Each link is typed according to the kind of attached network. Each link is also labelled with its Link ID. This Link ID gives a name to the entity that is on the other end of the link. Table 18 summarizes the values used for the Type and Link ID fields. Link type Description Link ID __________________________________________________ 1 Point-to-point Neighbor Router ID link 2 Link to transit Interface address of network Designated Router 3 Link to stub IP network number network 4 Virtual link Neighbor Router ID Table 18: Link descriptions in the router links advertisement. In addition, the Link Data field is specified for each link. This field gives 32 bits of extra information for the link. For links to transit networks, numbered links to routers and virtual links, this field specifies the IP interface address of the associated router interface (this is needed by the routing table calculation, see Section 16.1.1). For links to stub networks, this field specifies the network's IP address mask. For unnumbered point-to-point networks, the Link Data field should be set to the unnumbered interface's MIB-II [RFC 1213] ifIndex value. Finally, the cost of using the link for output (possibly specifying a different cost for each Type of Service) is specified. The output cost of a link is configurable. It must always be non-zero. To further describe the process of building the list of link
descriptions, suppose a router wishes to build a router links advertisement for Area A. The router examines its collection of interface data structures. For each interface, the following steps are taken: o If the attached network does not belong to Area A, no links are added to the advertisement, and the next interface should be examined. o Else, if the state of the interface is Down, no links are added. o Else, if the state of the interface is Point-to-Point, then add links according to the following: - If the neighboring router is fully adjacent, add a Type 1 link (point-to-point) if this is an interface to a point-to-point network, or add a Type 4 link (virtual link) if this is a virtual link. The Link ID should be set to the Router ID of the neighboring router. For virtual links and numbered point-to- point networks, the Link Data should specify the IP interface address. For unnumbered point-to-point networks, the Link Data field should specify the interface's MIB-II [RFC 1213] ifIndex value. - If this is a numbered point-to-point network (i.e, not a virtual link and not an unnumbered point-to- point network) and the neighboring router's IP address is known, add a Type 3 link (stub network) whose Link ID is the neighbor's IP address, whose Link Data is the mask 0xffffffff indicating a host route, and whose cost is the interface's configured output cost. o Else if the state of the interface is Loopback, add a Type 3 link (stub network) as long as this is not an interface to an unnumbered serial line. The Link ID should be set to the IP interface address, the Link Data set to the mask 0xffffffff (indicating a host route), and the cost set to 0. o Else if the state of the interface is Waiting, add a Type 3 link (stub network) whose Link ID is the IP network number of the attached network and whose Link Data is the attached network's address mask.
o Else, there has been a Designated Router selected for the attached network. If the router is fully adjacent to the Designated Router, or if the router itself is Designated Router and is fully adjacent to at least one other router, add a single Type 2 link (transit network) whose Link ID is the IP interface address of the attached network's Designated Router (which may be the router itself) and whose Link Data is the router's own IP interface address. Otherwise, add a link as if the interface state were Waiting (see above). Unless otherwise specified, the cost of each link generated by the above procedure is equal to the output cost of the associated interface. Note that in the case of serial lines, multiple links may be generated by a single interface. After consideration of all the router interfaces, host links are added to the advertisement by examining the list of attached hosts. A host route is represented as a Type 3 link (stub network) whose Link ID is the host's IP address and whose Link Data is the mask of all ones (0xffffffff). As an example, consider the router links advertisements generated by Router RT3, as pictured in Figure 6. The area containing Router RT3 (Area 1) has been redrawn, with actual network addresses, in Figure 15. Assume that the last byte of all of RT3's interface addresses is 3, giving it the interface addresses 220.127.116.11 and 18.104.22.168, and that the other routers have similar addressing schemes. In addition, assume that all links are functional, and that Router IDs are assigned as the smallest IP interface address. RT3 originates two router links advertisements, one for Area 1 and one for the backbone. Assume that Router RT4 has been selected as the Designated router for network 22.214.171.124. RT3's router links advertisement for Area 1 is then shown below. It indicates that RT3 has two connections to Area 1, the first a link to the transit network 126.96.36.199 and the second a link to the stub network 188.8.131.52. Note that the transit network is identified by the IP interface of its Designated Router (i.e., the Link ID = 184.108.40.206 which is the Designated Router RT4's IP interface to 220.127.116.11). Note also that RT3 has indicated that it is capable of calculating separate routes based on IP TOS, through setting the T-bit in the Options field. It has also indicated that it is an area border router.
; RT3's router links advertisement for Area 1 LS age = 0 ;always true on origination Options = (T-bit|E-bit) ;TOS-capable LS type = 1 ;indicates router links Link State ID = 18.104.22.168 ;RT3's Router ID Advertising Router = 22.214.171.124 ;RT3's Router ID bit E = 0 ;not an AS boundary router bit B = 1 ;area border router #links = 2 Link ID = 126.96.36.199 ;IP address of Desig. Rtr. Link Data = 188.8.131.52 ;RT3's IP interface to net Type = 2 ;connects to transit network # other metrics = 0 TOS 0 metric = 1 Link ID = 184.108.40.206 ;IP Network number Link Data = 0xffffff00 ;Network mask Type = 3 ;connects to stub network # other metrics = 0 TOS 0 metric = 2 Next RT3's router links advertisement for the backbone is shown. It indicates that RT3 has a single attachment to the backbone. This attachment is via an unnumbered point-to- point link to Router RT6. RT3 has again indicated that it is TOS-capable, and that it is an area border router. ; RT3's router links advertisement for the backbone LS age = 0 ;always true on origination Options = (T-bit|E-bit) ;TOS-capable LS type = 1 ;indicates router links Link State ID = 220.127.116.11 ;RT3's router ID Advertising Router = 18.104.22.168 ;RT3's router ID bit E = 0 ;not an AS boundary router bit B = 1 ;area border router #links = 1 Link ID = 22.214.171.124 ;Neighbor's Router ID Link Data = 0.0.0.3 ;MIB-II ifIndex of P-P link Type = 1 ;connects to router # other metrics = 0 TOS 0 metric = 8 Even though Router RT3 has indicated that it is TOS-capable in the above examples, only a single metric (the TOS 0 metric) has been specified for each interface. Different metrics can be specified for each TOS. The encoding of TOS
in OSPF link state advertisements is described in Section 12.3. As an example, suppose the point-to-point link between Routers RT3 and RT6 in Figure 15 is a satellite link. The AS administrator may want to encourage the use of the line for high bandwidth traffic. This would be done by setting the metric artificially low for the appropriate TOS value. Router RT3 would then originate the following router links advertisement for the backbone (TOS 8 = maximize throughput): ; RT3's router links advertisement for the backbone LS age = 0 ;always true on origination Options = (T-bit|E-bit) ;TOS-capable LS type = 1 ;indicates router links Link State ID = 126.96.36.199 ;RT3's Router ID Advertising Router = 188.8.131.52 bit E = 0 ;not an AS boundary router bit B = 1 ;area border router #links = 1 Link ID = 184.108.40.206 ;Neighbor's Router ID Link Data = 0.0.0.3 ;MIB-II ifIndex of P-P link Type = 1 ;connects to router # other metrics = 1 TOS 0 metric = 8 TOS = 8 ;maximize throughput metric = 1 ;traffic preferred 12.4.2. Network links A network links advertisement is generated for every transit multi-access network. (A transit network is a network having two or more attached routers). The network links advertisement describes all the routers that are attached to the network. The Designated Router for the network originates the advertisement. The Designated Router originates the advertisement only if it is fully adjacent to at least one other router on the network. The network links advertisement is flooded throughout the area that contains the transit network, and no further. The networks links advertisement lists those routers that are fully adjacent to the Designated Router; each fully adjacent router is identified by its OSPF Router ID. The Designated Router
includes itself in this list. The Link State ID for a network links advertisement is the IP interface address of the Designated Router. This value, masked by the network's address mask (which is also contained in the network links advertisement) yields the network's IP address. A router that has formerly been the Designated Router for a network, but is no longer, should flush the network links advertisement that it had previously originated. This advertisement is no longer used in the routing table calculation. It is flushed by prematurely incrementing the advertisement's age to MaxAge and reflooding (see Section 14.1). In addition, in those rare cases where a router's Router ID has changed, any network links advertisements that were originated with the router's previous Router ID must be flushed. Since the router may have no idea what it's previous Router ID might have been, these network links advertisements are indicated by having their Link State ID equal to one of the router's IP interface addresses and their Advertising Router not equal to the router's current Router ID (see Section 13.4 for more details). As an example of a network links advertisement, again consider the area configuration in Figure 6. Network links advertisements are originated for Network N3 in Area 1, Networks N6 and N8 in Area 2, and Network N9 in Area 3. Assuming that Router RT4 has been selected as the Designated Router for Network N3, the following network links advertisement is generated by RT4 on behalf of Network N3 (see Figure 15 for the address assignments): ; network links advertisement for Network N3 LS age = 0 ;always true on origination Options = (T-bit|E-bit) ;TOS-capable LS type = 2 ;indicates network links Link State ID = 220.127.116.11 ;IP address of Desig. Rtr. Advertising Router = 18.104.22.168 ;RT4's Router ID Network Mask = 0xffffff00 Attached Router = 22.214.171.124 ;Router ID Attached Router = 126.96.36.199 ;Router ID Attached Router = 188.8.131.52 ;Router ID Attached Router = 184.108.40.206 ;Router ID
12.4.3. Summary links Each summary link advertisement describes a route to a single destination. Summary link advertisements are flooded throughout a single area only. The destination described is one that is external to the area, yet still belonging to the Autonomous System. Summary link advertisements 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 link advertisements. If the routing table entry's Destination Type is area border router, examine the next routing table entry. o AS external routes are never advertised in summary link advertisements. If the routing table entry has Path- type 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 link advertisement 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 link advertisement 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 link advertisement cannot be generated for this route. o Else, if the destination of this route is an AS boundary router, generate a Type 4 link state advertisement for
the destination, with Link State ID equal to the AS boundary router's Router ID and metric equal to the routing table entry's cost. These advertisements should not be generated if Area A has been configured as a stub area. o Else, the Destination type is network. If this is an inter-area route, generate a Type 3 advertisement for the destination, with Link State ID equal to the network's address (if necessary, the Link State ID can also have one or more of the network's host bits set; see Appendix F 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 link advertisements. Remember that an area has been defined as a 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 advertisement is made for each range. When the range's status indicates Advertise, a Type 3 advertisement 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 F for details) and cost equal to the smallest cost of any of the component networks. When the range's status indicates DoNotAdvertise, the Type 3 advertisement 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 advertisement 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 F for details) and metric equal to the network's routing table cost. If virtual links are being used to provide/increase connectivity of the backbone, routing information concerning the backbone networks should not be condensed before being summarized into the virtual links' Transit areas. 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 links into Transit areas. The existence of virtual links is determined during the shortest path calculation for the Transit areas (see Section 16.1). If a router advertises a summary advertisement for a destination which then becomes unreachable, the router must then flush the advertisement 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 advertisement should also be flushed from the routing domain. For an example of summary link advertisements, 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 link advertisements. Consider in particular Router RT4. Its routing table was calculated as the example in Section 11.3. RT4 originates summary link advertisements into both the backbone and Area 1. Into the backbone, Router RT4 originates separate advertisements for each of the networks N1-N4. Into Area 1, Router RT4 originates separate advertisements for networks N6-N8 and the AS boundary routers RT5,RT7. It also condenses host routes Ia and Ib into a single summary link advertisement. Finally, the routes to networks N9,N10,N11 and Host H1 are advertised by a single summary link advertisement. This condensation was originally performed by the router RT11. These advertisements are illustrated graphically in Figures 7 and 8. Two of the summary link advertisements originated by Router RT4 follow. The actual IP addresses for the networks and routers in question have been assigned in Figure 15. ; summary link advertisement for Network N1, ; originated by Router RT4 into the backbone LS age = 0 ;always true on origination Options = (T-bit|E-bit) ;TOS-capable LS type = 3 ;summary link to IP net Link State ID = 220.127.116.11 ;N1's IP network number Advertising Router = 18.104.22.168 ;RT4's ID
TOS = 0 metric = 4 ; summary link advertisement for AS boundary router RT7 ; originated by Router RT4 into Area 1 LS age = 0 ;always true on origination Options = (T-bit|E-bit) ;TOS-capable LS type = 4 ;summary link to ASBR Link State ID = Router RT7's ID Advertising Router = 22.214.171.124 ;RT4's ID TOS = 0 metric = 14 Summary link advertisements pertain to a single destination (IP network or AS boundary router). However, for a single destination there may be separate sets of paths, and therefore separate routing table entries, for each Type of Service. All these entries must be considered when building the summary link advertisement for the destination; a single advertisement must specify the separate costs (if they exist) for each TOS. The encoding of TOS in OSPF link state advertisements is described in Section 12.3. Clearing the T-bit in the Options field of a summary link advertisement indicates that there is a TOS 0 path to the destination, but no paths for non-zero TOS. This can happen when non-TOS-capable routers exist in the routing domain (see Section 2.4). 12.4.4. Originating summary links 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 link advertisements into the area according to the above Section's algorithm, or can choose to originate only a subset of the advertisements, possibly under configuration control. The fewer advertisements originated, the smaller the stub area's link state database, further reducing the demands on its routers' resources. However, omitting advertisements may also lead to sub- optimal inter-area routing, although routing will continue to function. As specified in Section 12.4.3, Type 4 link state advertisements (ASBR summary links) are never originated into stub areas.
In a stub area, instead of importing external routes each area border router originates a "default summary link" into the area. The Link State ID for the default summary link 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. 12.4.5. AS external links AS external link advertisements describe routes to destinations external to the Autonomous System. Most AS external link advertisements describe routes to specific external destinations; in these cases the advertisement'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 F for details). However, a default route for the Autonomous System can be described in an AS external link advertisement by setting the advertisement's Link State ID to DefaultDestination (0.0.0.0). AS external link advertisements are originated by AS boundary routers. An AS boundary router originates a single AS external link advertisement for each external route that it has learned, either through another routing protocol (such as EGP), or through configuration information. In general, AS external link advertisements are the only type of link state advertisements that are flooded throughout the entire Autonomous System; all other types of link state advertisements are specific to a single area. However, AS external link advertisements 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. As with summary link advertisements, if separate paths exist based on TOS, separate TOS costs can be included in the AS external link advertisement. The encoding of TOS in OSPF link state advertisements is described in Section 12.3. If the T-bit of the advertisement's Options field is clear, no non-zero TOS paths to the destination exist. If a router advertises an AS external link advertisement for
a destination which then becomes unreachable, the router must then flush the advertisement from the routing domain by setting its age to MaxAge and reflooding (see Section 14.1). For an example of AS external link advertisements, consider once again the AS pictured in Figure 6. There are two AS boundary routers: RT5 and RT7. Router RT5 originates three external link advertisements, for networks N12-N14. Router RT7 originates two external link advertisements, for networks N12 and N15. Assume that RT7 has learned its route to N12 via EGP, and that it wishes to advertise a Type 2 metric to the AS. RT7 would then originate the following advertisement for N12: ; AS external link advertisement for Network N12, ; originated by Router RT7 LS age = 0 ;always true on origination Options = (T-bit|E-bit) ;TOS-capable LS type = 5 ;indicates AS external link Link State ID = N12's IP network number Advertising Router = Router RT7's ID bit E = 1 ;Type 2 metric TOS = 0 metric = 2 Forwarding address = 0.0.0.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 EGP information with the non-OSPF router RTX. RTA must then originate AS external link advertisements for those destinations it has learned from RTX. By using the AS external link advertisement'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 EGP peer RTX. The resulting AS external link advertisement 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 = (T-bit|E-bit) ;TOS-capable LS type = 5 ;indicates AS external link Link State ID = DefaultDestination ; default route Advertising Router = Router RTA's ID bit E = 1 ;Type 2 metric TOS = 0 metric = 1 Forwarding address = RTX's IP address In figure 16, suppose instead that both RTA and RTB exchange EGP information with RTX. In this case, RTA and RTB would originate the same set of AS external link advertisements. These advertisements, 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 external advertisements, 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 advertisements (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 advertisements (i.e., same destination, cost and non-zero forwarding address), then the advertisement originated by the router having the highest OSPF Router ID is used. The router having the lower OSPF Router ID can then flush its advertisement. Flushing a link state advertisement is discussed in Section 14.1.