Section 5.1. Flooding Components
5.1. Flooding ComponentsRecall from Chapter 2 that flooding is the mechanism by which the topological information originated by an OSPF or IS-IS router is received by all other routers in an area, so that the routers can add the information to their link state databases. Also recall from Chapter 2 that for a link state protocol to operate correctly, the link state databases of every router in an area must be identical. Therefore, flooding requires not just a transport mechanism but also reliability features. Given these requirements, both OSPF and IS-IS flooding use the following components:
5.1.1. OSPF FloodingYou already know that OSPF's basic unit of topological information comprising its link state database is an LSA. OSPF uses an Update packet (Figure 5.1) to send LSAs from one router to another during the flooding process. Whereas LSAs are flooded throughout an area, Update packets are exchanged only between directly connected routers. That is, their scope is the local link. If an LSA received in an Update packet must be forwarded to another router, it is put into a new Update packet for the next hop. This is in keeping with the fact that none of the five OSPF message types are forwarded beyond the local link. Figure 5.1. The OSPF Update message format. You can see from Figure 5.1 that the Update (OSPF message type 4) payload is one or more LSAs, preceded by a field specifying how many LSAs are contained in the packet. Any one of the following events causes a router to send an LSA to one or more neighbors:
The first three events are a part of routine maintenance of the link state database, and are discussed in this section. The fourth event is the normal routing protocol procedure of communicating network information. The last event, sending an LSA in response to a Link State Request message, is part of the database synchronization process and is discussed in Chapter 6. The manner in which the Update is sent depends on the type of network link over which it is transmitted:
5.1.1.1. Acknowledgment of LSAsWhenever an Update message is sent, the LSAs it contains must be acknowledged by the receiving neighbors to ensure reliable flooding. So when a router floods an LSA on a link, it adds the LSA to a retransmit list and sets a retransmit timer. Every time the retransmit timer expires, the router retransmits the LSA. When the LSA is acknowledged, it is removed from the retransmit list. The retransmit timer is configurable to between 1 and 65,535 seconds, with a typical default of 5 seconds. This is a long enough interval that on normal networks an LSA should almost always be acknowledged and removed from the retransmit list before the retransmit timer expires. A good OSPF implementation might also include a mechanism for "windowing" the retransmission rate so as not to overwhelm a slow neighbor, and a mechanism for handling a case where a neighbor never acknowledges an LSA, such as removing the LSA from the retransmit list and logging a flooding error message. If an LSA is flooded on a broadcast link, and all the neighbors except one acknowledge the LSA, you do not want to retransmit the LSA to every neighbor. Rather, you want to retransmit only to the neighbor that did not acknowledge its receipt. Therefore Update messages carrying retransmitted LSAs are always unicast, regardless of the network type. There are two things to know about the way OSPF acknowledges the receipt of an LSA:
An explicit acknowledgment of an LSA is accomplished by sending an OSPF Acknowledgment message to the neighbor that sent the Update. The Acknowledgment message, shown in Figure 5.2, carries the headers of one or more LSAs. The LSA header contains all the information needed to acknowledge a specific LSA and a specific instance of that LSA. Figure 5.2. The OSPF Acknowledgment message format. An implicit acknowledgment occurs when a router that sent an LSA to a neighbor receives an Update from that same neighbor, containing the same instance of the same LSA. In this situation the router knows the neighbor has a copy of the LSA, and removes the LSA from its retransmit list just as it would if an explicit acknowledgment had been made. Implicit acknowledgments are most likely to occur during the database synchronization process when Update packets are being sent between neighbors simultaneously, or during flooding where two neighbors each receive a copy of the LSA from other neighbors and then send Updates to each other more or less simultaneously. A delayed acknowledgment means that an OSPF router waits some specified amount of time before sending an Acknowledgment message. There are several benefits to delaying an acknowledgment:
If an acknowledgment is delayed too long, however, the neighbor's retransmit timer will expire and retransmits will occur unnecessarily. Therefore, the acknowledgment delay should be less than the typical retransmit period. A direct acknowledgment means an LSA is acknowledged immediately upon receipt, and the Acknowledgment packet is unicast directly to the sender. Delayed acknowledgments are preferred, but there are two cases in which a direct acknowledgment must be sent as soon as an LSA is received:
5.1.1.2. The LSA Header FormatAn Acknowledgment message carries just the LSA header, rather than the entire LSA, because everything needed to completely identify an LSA is in the header. All OSPF LSAs use the same header format, shown in Figure 5.3. The Type, Link State ID, and Advertising Router fields together identify a specific LSA. The Age, Sequence Number, and Checksum fields together identify a specific instance of that LSA, so that when multiple instances exist in a network the most recent can be determined. The Length field specifies the length, including the header length, of the LSA. Figure 5.3. The OSPF LSA header format.
5.1.1.3. Multiple Copies of an LSAAs a single instance of an LSA is flooded throughout an area, a router might receive multiple copies of the LSA with different age values. Figure 5.4 shows how this might happen. After an LSA is received by R1, it is replicated and flooded to two neighbors. The two copies of the LSA both reach R5; because there are a different number of router hops along the two paths, however, the age is incremented differently. As a result, the two copies of the LSA have the same sequence number but different ages. Assuming the router has already accepted one of the copies, it would be inefficient for it to assume incorrectly that the second copy is newer. To remedy such a situation, OSPF defines a constant called MaxAgeDiff, which is 15 minutes. If two copies of an LSA have ages that differ by less than MaxAgeDiff, but are otherwise identical, they are assumed to be the same instance. Figure 5.4. A router can receive multiple copies of the same LSA instance but with different ages. Figure 5.5 shows a summary display of an OSPF link state database. As you can see, all the LSAs in the database are fully described by displaying the values of the header fields.
When multiple LSAs are received with identical Type, Link State ID, and Advertising Router values, the Age, Sequence Number, and Checksum fields of the LSAs are compared to determine which of the LSAs is the most recentand hence, the one that should be accepted. The steps for comparing these three fields is as follows:
5.1.1.4. Limitations on OSPF FloodingWhen an LSA is received, its checksum indicates that it is valid, and the LSA is either new or a more recent instance of a known LSA, the router must determine which interfaces the LSA must be flooded out. Essentially, the LSA is flooded out the same interface from which it was received only if the connected network is broadcast or NBMA and the router is the DR. Otherwise, the LSA is not sent on the same interface from which it was received. Another limitation on flooding is the area to which the interface belongs. If the scope of the LSA type is limited to a single area, it is not flooded out interfaces belonging to a different area from the area of the interface from which it was received. With these rules, the flooding of the LSA will, even in complex topologies, end when the LSA has reached all routers within the flooding scope. 5.1.2. IS-IS FloodingA source of confusion for people trying to learn IS-IS is in trying to correlate IS-IS LSPs to an OSPF entity. Does the LSP serve an equivalent function to an OPSF Update message? Like Updates, it is the "package" by which information is sent from one router to another. But unlike Updates, LSPs are not limited in scope to a single link. They are flooded intact throughout an area. And also unlike Updates, the information contained in a single LSP pertains only to the router that originated it. Perhaps we can say, then, that an LSP is more like an OSPF LSA. Just as LSAs are the basic data structures that the OSPF link state database is built from, LSPs are the basic data structures of the IS-IS link state database. But you saw in the previous section, and will see in greater detail later in this chapter, that there are a number of different LSA types providing a number of different kinds of information. There is, in contrast, only a single LSP for each adjacency type (L1 or L2). The kinds of information carried in different LSAs are carried in a single LSP, by different TLVs. So, then, can we say that the real parallel is between IS-IS TLVs and OSPF LSAs? We cannot, because LSAs are more self-contained than TLVs. They have their own ages, checksums, and sequence numbers, whereas TLVs do not. LSAs also provide a complete set of functional information (about, for instance, a router, a pseudonode, or an external destination), whereas the information in a TLV (such as a list of addresses or neighbors, or authentication information) is intended to be used in conjunction with information in other TLVs. The bottom line is that you cannot always draw a direct correlation between OSPF and IS-IS. The most you can say here is that LSPs, like OSPF LSAs, are the basic data units produced and flooded by individual routers for building link state databases. Because IS-IS runs over the data link level rather than the network level, LSPs are themselves packets and do not require a separate means of transport the way LSAs require Update packets. Any of the following events causes an IS-IS router to generate and flood a new LSP:
5.1.2.1. The LSP FormatA router generates separate LSPs for L1 and L2 adjacencies. On broadcast networks, L1 LSPs are sent to the multicast address AllL1IS (0180.c200.0014), and L2 LSPs are sent to multicast address AllL2IS (0180.c200.0015). Figure 5.6 shows the format of the IS-IS LSP. Figure 5.6. The IS-IS Link State PDU.
Given the rule that sequence numbers must start at 1, the value of 0 becomes handy. Because it is always less than any normally incremented sequence number, a router that wants to receive the latest copy of a known LSP from a neighbor can set the sequence number of the LSP to 0 and flood it. The neighbor, having a copy of the LSP with a higher (and therefore newer) sequence number will send this LSP to the originator. As with OSPF, IS-IS can increase an LSP's sequence number more than 1 in some situations. The most common case is a restarted router that discovers that an LSP it generated before the restart still exists in other routers' databases. The router will increment the LSP's sequence number one beyond the existing sequence number and reflood the LSP. There is the remote possibility that a restarted router can flood an LSP while a previously generated LSP still exists in other routers' databases, and that the two LSPs contain different information but the same sequence numbers. In such a case, the routers receiving the flooded LSP and noting the differing checksums will install the new LSP in their databases but with a remaining lifetime value of 0 (expired) and reflood the LSP. IS-IS uses the following procedure when comparing two copies of the same LSP to determine which is more recent:
The LSP ID consists of three fields which together identify a particular LSP:
Figure 5.7 shows five LSP IDs from an IS-IS LS database, along with their associated sequence numbers, checksums, and remaining lifetimes. The structure of the LSP ID is the Source ID followed by a period, then the Pseudonode ID followed by a dash, and then the LSP number. In the display the Source ID (SysID) is represented as the router's host name, thanks to the wonders of Dynamic Hostname Exchange.
An internal flag, called the Send Routing Message (SRM) flag, is used in the transmission of LSPs. For each LSP in its LS database, IS-IS creates a set of SRMsone per link. That is, if a router has 20 LSPs in its LS database and 5 interfaces, 5 SRMs will be associated with each of the LSPs for a total of 100 SRMs. When IS-IS determines that an LSP needs to be sent on a particular link, it sets the LSP's SRM flag for that interface. At a set interval, known as the minimum LSP transmission interval, the LS database is scanned. On point-to-point links, all LSPs that have the SRM for that link set are sent. On broadcast links, the behavior is more interesting: The LS database is scanned once every minimum LSP transmission interval, and out of the set of LSPs with their SRMs set for that interface, one[5] is randomly chosen and sent. The reason for this behavior on broadcast networks has to do with the way IS-IS LS databases are synchronized on such networks, and so is explained in detail in Section 6.2.2. But in a nutshell, this randomization reduces the chance of multiple routers sending the same LSP to the DIS at the same time.
ISO 10589 recommends a minimum LSP transmission interval value of 5 seconds. This interval, like many IS-IS timers, has a random jitter of up to 25 percent added to prevent timer synchronization. 5.1.2.2. Acknowledgment of LSPsThe receipt of an LSP is acknowledged between adjacent neighbors to ensure reliable flooding. But there is no distinct acknowledgment message as there is with OSPF. Instead, IS-IS uses two PDUs called the Partial Sequence Number PDU (PSNP) and Complete Sequence Number PDU (CSNP). These PDUs, which are normally used for LS database synchronization, are detailed in Section 6.2.1. But for the purposes of discussing LSP acknowledgment, suffice it to say that both PDUs (collectively called Sequence Number PDUs) carry descriptions of one or more LSPs by listing their Remaining Lifetime, LSP ID, Sequence Number, and Checksum fields. The difference between the two is that CSNPs describe all LSPs in the originator's LS database, whereas PSNPs carry only a subset of the LSPs in the originator's LS database. Explicit and implicit acknowledgments are used by IS-IS, but differently than the way they are used by OSPF. The receipt of an LSP on a point-to-point link is always explicitly acknowledged by sending a PSNP to the sender identifying the LSP. More than one LSP can be acknowledged in a single PSNP. If the receiver has a newer instance of the LSP in its LS database than the one it received, it sends a copy of the newer LSP back to the neighbor rather than sending a PSNP acknowledgment. When an LSP is sent on a point-to-point link, the LSP's SRM for that link is not cleared until an acknowledgment is received, either in the form of a PSNP or a newer or same-aged LSP. This creates a behavior similar to the OSPF retransmission list. If the LSP is not acknowledged, it is sent again at the next minimum LSP transmission interval. Receipt of an LSP on a broadcast link is always implicitly acknowledged. The mechanism for acknowledging LSPs is a part of the LS database synchronization and maintenance procedures, and so is described in Section 6.2.4. But in brief, the mechanism works as follows: The DIS periodically (every 10 seconds) multicasts a CSNP on the broadcast link, which describes the LSPs in its LS database. When a router sends an LSP on the broadcast link, the LSP should be included in subsequent CSNPs. If it is not, the originating router will resend the LSP. Unlike point-to-point links, an LSP's SRM for a broadcast link is cleared as soon as the LSP is sent. This is because of the implicit acknowledgment via the CSNP. If the new instance of the LSP is not indicated in subsequent CSNPs, the sending router resets the SRM and retransmits the LSP at the appropriate time. |
Age Opt Cksum Len Router 192.168.254.5 192.168.254.5 0x80001802 
EAN: 2147483647
Pages: 111