Flooding and Link-State Database Synchronization

Link-state routing protocols, such as IS-IS and the OSPF Protocol, operate on the premise that all nodes in an area obtain the same description or view of the area through the exchange of link-state information (LSPs in the case of IS-IS). The LSPs, which are stored in the Link-State database, are then fed as input to the route calculation algorithm (SPF algorithm), to determine the shortest path to any node in the area. A consistent view of the area's topology allows all routers in the area to independently calculate optimal and loop-free routes to all destinations within the area. Each IS-IS router assembles information about its immediate surrounding , such as its own SysID and those of neighbors, directly connect IP subnets, and so on, into an LSP. The LSP is then advertised to directly connected neighbors and eventually reaches all nodes in the area by means of a mechanism known as flooding. Under stable conditions, the Level 1 Link-State database is identical on all routers in the area. The local route calculation algorithm at each node sews the LSPs together into the topology of the entire area, just like putting the pieces of a jigsaw puzzle together. Figure 5-13 shows how a router assembles the LSPs from every node in the area to represent the area's topology. It is necessary for all routers in the area to obtain the same and consistent view of the area's physical and addressing layout to achieve efficient and loop-free forwarding within the area. The flooding process is complemented with auxiliary mechanisms, referred to as database synchronization , to guarantee exact replication of the area database at every node.

Figure 5-13. LSPs in an area Link-State database.

Chapter 2 discussed the key processes underlying the IS-IS protocol (receive, update, decision, and forward processes). The update process is responsible for flooding. The individual update processes running on the IS-IS routers in an area work collaborativelyto achieve the same Link-State databases on all the routers in the area. The interrelated processes ”flooding and database synchronization ”are the subject matter of the subsequent sections in this chapter.

When fed with the Link-State database, the SPF algorithm organizes the various network destinations in the LSPs into the shortest-path tree with the calculating router at the root. This is achieved by using available metric information to compute the paths with the lowest cumulative metric to all known destinations. These best routes are then fed into the forwarding database. The SPF algorithm is discussed in detail in Chapter 6.

Even though Level 1 routing within an area is mainly cited to explain flooding and database synchronization, similar and independent flooding also occurs within the backbone between the Level 2 routers that interconnect areas. When routing converges, the Level 1 routers attain a complete topological view of their respective areas, whereas Level 2 routers attain a complete map of the topological relationship between areas.

Like all link-state routing protocols, IS-IS uses a suite of timers and flags to manage processes, such as flooding and operation of the SPF algorithm. The timers and flags provide control and event management that ensure stability in the routing environment. The timers help optimize use of system resources, such as processing capacity, memory, and link bandwidth. Timers are also a major factor in achieving optimal routing convergence during significant changes in the network. The following section discusses two important flags: the Send Routing Message (SRM) flag and the Send Sequence Number (SSN) flag. Database maintenance- related timers, such as maxage, regeneration, and retransmission timers,are then discussed.

SRM and SSN Flags

SRM and SSN flags play important roles in flooding and database synchronization. The update process uses the SRM flag to control delivery of LSPs to adjacent neighbors. The SSN flag is used in the following two ways:

• To acknowledge LSPs received in reliable flooding over point-to-point links

• To request complete LSP information during database synchronization over broadcast links

The SRM and SSN flags essentially provide a means to enforce efficient queuing of LSPs and PSNPs by decoupling LSP forwarding and acknowledgment to achieve optimized utilization of processing and link bandwidth resources. The relevance of these flags is discussed further in the following sections.

Flooding

Flooding is the vehicle for replication and distribution of the Link-State databases within a network, a phenomenon that is critical to the operation of link-state routing protocols. An IS-IS router generates an LSP, which it floods out to all adjacent neighbors over its IS-IS-enabled interfaces. The IS-IS router also receives and processes LSPs flooded by other neighbors. When a router receives an LSP from a neighbor, it keeps a copy in the corresponding local Link-State database (Level 1 or Level 2) and also floods copies over all IS-IS interfaces other than the one on which the LSP was received. To flood out an LSP, the router first sets the SRM flag individually for target interfaces and clears the flags when the specific LSP has been successfully transmitted. On point-to-point links, successful transmission is confirmed by receipt of a PSNP acknowledgment. No acknowledgment is required on broadcast links. When LSPs that are duplicates of already known versions are received, they are dropped.

Flooding over point-to-point links is described as reliable because LSPs transmitted over such links must be acknowledged with a PSNP by the router at the receiving end. On broadcast media, CSNPs are periodically transmitted by the Level 1- and Level 2-designated routers to assist other routers in synchronizing their databases. Any router on the medium that does not have all or current copies of the LSPs summarized in the CSNP uses a PSNP to request what it needs. Database synchronization is a dynamic activity in a network. Routers generate new LSPs when changes occur in their immediate routing environment. New LSPs are flooded with higher sequence numbers and new checksum values, and the SRM and SSN flags are used to effectively coordinate flooding and synchronization.

The command show isis database private can be used to check the status of SRM and SSN flags on Cisco routers (see Example 5-7).

Example 5-7 Status SSN and SRM Flags

 RB#  show isis database private  IS-IS Level-1 Link State Database: LSPID           LSP Seq Num  LSP Checksum  LSP Holdtime   ATT/P/OL RTA.00.00       0x00000068   0x18E2        909            0/0/0  Address 0x614846DC,length 360,max_length 360,on_paths  Root distance 10,index 13,parent index 1,parent count 1 RTA     Sc0/0      *HDLC*          Up    28    L1   IS-IS SRM bits set on no interfaces SSN bits set on no interfaces RTB.00-00       0x000007DF     0x1A73          721        0/0/0  Address 0x1391B),length 415,max)length 415,on_paths  Root distance 10,index 3,parent index 2,parent count 1  RTB    Sc0/0      *HDLC*         Up    27     L1   IS-IS  SRM bits set on no interfaces   SSN bits set on no interfaces  

Example 5-7 shows that no SRM and SSN flags have been set for any LSPs, meaning that there are no LSPs that are pending to be flooded or that need to be acknowledged for any interface. This command can be useful in troubleshooting situations of congestion resulting from relatively large volumes of traffic or lack of processing and bandwidth resources on routers in the network.

Flooding over Point-to-Point Links

As mentioned in the preceding section, IS-IS uses a reliable flooding mechanism on point-to-point links. This seems reasonable because on a point-to-point link, only one neighbor is on the other end, and it should be fairly straightforward to track explicit acknowledgment of LSPs from that single neighbor at almost insignificant bandwidth cost.

CSNPs simplify the synchronization process. They contain a summary of the router's Link-State database. CSNPs are exchanged only once on a point-to-point link, when adjacency is first established between the two connected routers. CSNPs provide a quick way to review and match the LSPs in each neighbor's database with the contents of the local database to determine missing or outdated copies of LSPs. The currency of LSPs is determined by sequence number comparison. PSNPs request current or missing copies of LSPs. A router also can proactively flood out LSPs that it determines the neighbor does not have. As indicated previously, SRM and SSN flags are at the heart of the reliable flooding process. Whereas the SRM flag is set on any links over which copies of a specific LSP need to be flooded out, the SSN flag is set on only point-to-point links over which LSPs have been received and flag the need to send out a PSNP acknowledgment. The flags are cleared after appropriate actions have occurred.

When a router transmits an LSP over a point-to-point link, it expects to have a PSNP acknowledgment back from the neighbor. If the acknowledgment is not received within a specified period, referred to as the retransmission interval , the LSP is assumed lost during transmission and is retransmitted. An LSP is continually retransmitted on a point-to-point link until it is acknowledged with a PSNP by the neighbor.

Figure 5-14 illustrates the flooding process on a point-to-point link. RTB has a point-to-point connection to RTA and RTC. In this example, RTB receives an LSP from RTA with LSPID RTA.00-00 and sequence number (SEQ#) 100. It installs a copy of RTA.00-00 in the LS database, sets SSN on interface 2, and sets SRM on interface 3. RTB then forwards a copy of RTA.00-00 to RTC and a PSNP acknowledgment to RTA. Then RTA immediately clears the SSN flag on interface 2 but leaves the SRM flag on interface 3. RTC receives RTA.00-00 from RTB, installs it in the LS database, and sets an SSN flag on interface 4. RTC then sends a PSNP acknowledgment to RTB and clears the SSN flag on interface 4. When RTB receives the PSNP acknowledging RTA.00-00 from RTC, it then clears the SRM flag on interface 3.

Figure 5-14. Flooding over point-to-point links.

Initial CSNP exchange over point-to-point links helps speed up the synchronization process. Losing any of these CSNPs undoubtedly drags out the synchronization process. Figure 5-15 illustrates a scenario in which an initial CSNP is lost. RTC is already adjacent and synchronized to RTA and RTB. RTC, therefore, has its own LSP and those of RTA and RTB in its database. If the CSNP from RTC is lost in the process of synchronizing with the newly adjacent RTD on the point-to-point connection, RTD will not immediately know about LSPs from RTA and RTB. When RTC receives RTD's CSNP, however, it detects that RTD doesn't yet know about LSPs from RTA and RTB. Therefore, it proactively floods them out. This prolongs the time it takes RTD to know about all LSPs.

Figure 5-15. Loss of initial CSNP on a point-to-point link.

Flooding on Broadcast Links

On broadcast links, LSPs are flooded to Level 1 or Level 2 neighbors by using the applicable multicast address, allL1IS (01-80-C2-00-00-14) or allL2IS (01-80-C2-00-00-15), respectively. The flooding operation does not employ acknowledgment routines that guarantee reliable delivery of LSPs, as in the point-to-point case. Flooding on broadcast links is, therefore, described as best effort .

Reliable flooding simplifies the database synchronization process, removing any clear delineation between the flooding and synchronization processes. On the contrary, unreliable flooding requires a distinct mechanism to ensure database synchronization. To synchronize databases over broadcast links, IS-IS routers rely on periodic multicast of CSNPs from the DIS. Separate CSNPs for Level 1 and Level 2 that exist are advertised to allL1IS and allL2IS multicast addresses, respectively.

As discussed in Chapter 3, IS-IS models broadcast links, such as LANs, as pseudonodes, which are represented by DISs. The DIS controls only flooding and database synchronization on broadcast links. IS-IS routers on a broadcast link are not restricted to forming adjacencies with only the DIS. Hello packets are multicast out and routers become adjacent to each other after a three-way handshake, which essentially means each router has reported seeing the other. The CSNPs sent out by the DIS are not acknowledged either, and periodic flooding ensures that all routers receive copies, which they check against the contents of their Link-State database. By looking at the contents of CSNPs, LAN routers can identify missing or newer LSPs and subsequently request copies with a PSNP. The PSNP sent out is packed with summaries of requested LSPs. The requester then receives the complete LSPs from the DIS or other peers on the link. SRM flags also are set on broadcast links; however, they are immediately cleared after the corresponding LSPs are transmitted because no acknowledgment is expected. CSNPs are periodically advertised on broadcast links every CSNP interval, which is 10 seconds by default. Periodic CSNP advertisement can be expensive with regard to bandwidth consumption. This is, however, the tradeoff for a simpler scheme to achieve reliability on broadcast links. Such links were traditionally thought to be less expensive than point-to-point wide-area links, and this might have influenced the protocol design in this regard. Cisco IOS provides a command that allows the periodic interval for transmitting CSNPs to be modified to reduce transmission frequency.

Figure 5-16 is a simplified illustration of flooding on a broadcast link. In the scenario shown, RTC is the last to connect to the link. RTA and RTB are already connected, and RTA is the designated router (DIS). After forming adjacencies with RTA and RTB, RTC builds an LSP, RTC.00-00, stores a copy in its Link-State database, and floods another copy out of interface 3 onto the link. Later RTA, the DIS, advertises a CSNP by multicast over the link. RTC receives a copy of the CSNP, checks it against the local Link-State database, and notices three missing LSPs: RTA.00-00, RTA.01-00, and RTB.00-00. At this time, RTC has only its own LSP, RTC.00-00, in the local Link-State database. RTC then sends out a PSNP onto the link to obtain the complete copies of RTA.00-00, RTA.01-00, and RTB.00. RTA floods RTA.00-00, RTB.00-00, and the pseudo LSP RTA.01-00 through multicast, and RTC receives copies.

Figure 5-16. Flooding over broadcast links.

Flooding over NBMA Transport Media

In IS-IS, network links are either point-to-point or multipoint broadcast and no special provisions are made for nonbroadcast multiaccess (NMBA) media, such as Asynchronous Transfer Mode (ATM), Frame Relay, and Integrated Services Digital Network (ISDN). Although it is frequently recommended to use point-to-point subinterfaces for NBMA links, some practical situations might not lend themselves to this type of design. In this case, such NBMA links must be configured as broadcast multipoint links. However, this configuration requires all nodes connecting over the NBMA cloud to be fully meshed. In most cases, the virtual circuits in the NBMA cloud are not fully meshed, therefore, the most suited approach (adopted by most network operators) is to configure the ATM or Frame Relay permanent virtual circuits (PVCs) as point-to-point subinterfaces. Because an NBMA interface can have a large number of PVCs, an ATM or Frame Relay cloud can have a potentially high degree of meshed PVCs, leading to extreme levels of LSP flooding activity. This, in turn , can adversely impact network stability and scalability. You can limit excessive flooding over highly redundant NBMA PVC meshes by grouping a subset of subinterfaces into IS-IS mesh groups.

IS-IS Mesh Groups

IS-IS mesh groups help limit excessive and redundant flooding over NBMA clouds. During normal operations, IS-IS routers reflood any new LSPs over all other interfaces except the one on which the LSP was received. The concept of IS-IS mesh groups allows grouping of router interfaces, typically NBMA subinterfaces, together so that when an LSP is received from one of the subinterfaces in the group, it is not reflooded over other subinterfaces in the same group. The trick about mesh groups is that they assume a full mesh between all routers in the mesh and that every member router gets a copy of the original LSP that is not flooded to the group . Although this solves the problem of redundant flooding, some routers might not receive their copies of LSPs that are not to be flooded to the group if the full mesh is broken. Therefore, you might need alternative unrestricted flooding paths within the network to guarantee that all flooded LSPs reach every target node in the network. The concept of IS-IS mesh groups is elaborated in Figure 5-17, which shows a group of routers connected over an NBMA cloud with a partial PVC mesh.

Figure 5-17. IS-IS mesh groups.

A subset of the routers in Figure 5-17 (RTA, RTC, RTD, and RTF) form a fully meshed subcloud. RTB and RTE connect only to two neighbors each.

In this scenario, it is desirable to use point-to-point subinterfaces to interconnect the routers; however, the relatively high level of interconnectivity implies a lot of redundant flooding over this cloud. If RTA floods an LSP, for example, all the other routers in the fully meshed subcloud (RTC, RTD, RTF) receive copies of the original and subsequently reflood it to each other, even though they all received copies already. This evidently results in redundant flooding.

In a full mesh of n number of routers, a single LSP transmitted to ( n “ 1) nodes results in ( n “ 2) unnecessary transmissions of the same LSP at the expense of critical processing and bandwidth resources. Initially, one of the routers in the mesh floods an LSP to ( n “ 1) adjacent neighbors. Then the remaining ( n “ 2) neighbors flood copies of this LSP to each other, with copies on the same link crossing each other. After a specific LSP is received from a neighbor, the same LSP received secondhand from another neighbor is not flooded to the first neighbor. This is why the number of redundant transmissions is limited to( n “ 2). If all n nodes transmitted LSPs, there would be a total of n ( n “ 1) original LSP transmissions and ( n “ 1)( n “ 2) redundant transmissions.

Mesh groups can be used to limit the waste in bandwidth and processing resources resulting from redundant flooding. Because the operation of mesh groups assumes a full mesh of routers in the group, the likely candidates in Figure 5-17 for a mesh group setup are RTA, RTC, RTD, and RTF. RTB and RTE are left out of the mesh group and flooding is not restricted over their interfaces. In this scenario, RTB and RTE provide redundant paths for guaranteeing delivery of any LSP to every router in the network if any of the links in the mesh group fail. In this arrangement, any new LSP that RTA receives from a member of the mesh group is flooded to only nonmembers (RTB and RTE). If an LSP is received on a subinterface that is not in the mesh group, it is flooded over all other interfaces as usual.

The Cisco IOS interface command isis mesh-group [ num blocked ] configures mesh groups. You can use the optional keyword blocked to completely disable flooding on an interface or subinterface. Even though the IS-IS mesh group feature has been supported in Cisco IOS for a while, a draft proposal describing the mechanism was submitted only recently to the IETF IS-IS Working Group for consideration and adoption as a standard feature of Integrated IS-IS.