IS-IS Link-State Database

As a link-state protocol, IS-IS works by gathering reliable and complete information about the routing environment through the use of special packets known as Link State Protocol Data Units ( LSPs ). A protocol data unit ( PDU ) also means a packet. Each router generates an LSP, which captures local link-state information describing connected links, neighbor routers, IP subnets, related metric information, and so forth. Copies of the LSP are distributed to all routers in a specific area through a process referred to as flooding. Ultimately, all routers in an area obtain every other router's LSP and synchronize their databases. Because the area link-state database is used for only intra-area routing (also referred to as Level 1 routing), it is called the Level 1 link-state database. The Level 2 routers interconnected into the backbone similarly maintain a Level 2 link-state database through the exchange of Level 2 LSPs. Best paths though the network are resolved by running the SPF algorithm over the information in the Level 1 and Level 2 databases separately. The sections that follow address the following subtopics:

• Overview of the IS-IS link-state database

• Flooding and database synchronization

• The SPF algorithm and route calculation

The first section provides a high-level overview of the IS-IS link-state database. The next section discusses the flooding process through which database synchronization is achieved, and the last section tops the earlier discussions with an overview of the SPF algorithm, also known as the Dijkstra algorithm.

Overview of the IS-IS Link-State Database

The operation of a link-state protocol requires each node in an area to have a complete view of the entire area and, using that knowledge, calculate the best paths to each destination in the area, starting with itself. As indicated previously, LSPs are the vehicles for propagating each router's limited view of its immediate surroundings; therefore, the assembly of LSPs by routers to obtain the complete routing picture of the network frequently has been compared to the process of solving a jigsaw puzzle. The solved puzzle represents the entire picture of the network or its complete topology. Each of the unique Level 1 databases represents the state of adjacencies within a specific area, while the Level 2 database represents the interconnections among the various areas in the domain. On Cisco routers, the command show isis database [ detail level-1 level-2 ] [ lspid ] can be used to view the LSPs in the Level 1 or Level 2 databases. Exercising the detail option of the command displays details about elements in all known LSPs or a specific LSP. Figure 10-11 shows the format of an LSP.

Figure 10-11. Link-State PDU Format

The LSP header features generic fields that have already been discussed in this chapter. The following are some of the fields specific to the LSP header:

• Remaining Lifetime ‚ This is the time interval until expiration of an LSP. An LSP ages from the time that it is generated. If it is not refreshed before its maximum age (Maxage) is reached, it expires and it is then subsequently deleted from the LSP database. The default value of Maxage is 20 minutes.

• LSP Identifier ‚ The LSP identifier (LSPID) obviously is used for identification purposes and indicates the owner of the LSP. The LSPID format, as shown in Figure 10-12, consists of three components .

  Figure 10-12. LSP Identifier

  

  - System identifier (SysID) ‚ This is the system ID of the originating router or the designated router (DIS), in the case of a pseudonode LSP.
  
  

  - Pseudonode identifier ‚ This is 0 for a non-PSN LSP and nonzero for a PSN LSP.
  
  

  - LSP number ‚ This denotes LSP fragments .
  
  

• Sequence Number ‚ A router tags the LSP that it generates with a sequence number to differentiate newer copies from older ones. The LSP sequence number is increased by 1 whenever the router generates a new LSP to replace an outdated version. New LSPs are issued when changes occur in local surroundings of the router that need to be reported to the rest of the network. An IS-IS router periodically issues a new LSP with the same information as the previous LSP, just to refresh an LSP before it expires. The default refresh interval is 15 minutes.

• Checksum ‚ This maintains the integrity of an LSP during storage or when the LSP is in flight during flooding. The checksum value is inserted into the LSP by the originating router and is verified by any router that receives a copy. If an LSP fails a checksum valid-ation, it is considered as corrupted and should not be used in routing calculations or flooded to other parts of the network. As a precaution, when a router determines an LSP is corrupted, it attempts to purge the LSP from the network by setting its remaining lifetime to 0 and flooding copies to all its neighbors.

Other interesting fields in the LSP header, as shown in Figure 10-11, are as follows :

• Partition Bit (P) ‚ Bit 8. Set to indicate whether the originator of the LSP supports partition repair. This capability currently is not supported in Cisco IOS Software.

• Attached Bit (ATT) ‚ Bits 4 to 7. Any of these bits is set to indicate that the node is attached to another area or the Level 2 backbone. These bits are set in the Level 1 LSPs generated by Level 1 ‚ 2 routers. The one specific bit set indicates the type of metric used in the backbone. The bits are defined as follows:

  - Bit 4 ‚ Default metric

  - Bit 5 ‚ Delay metric

  - Bit 6 ‚ Expense metric

  - Bit 7 ‚ Error metric

  Only bit 4 is set on Cisco routers because the default metric is the only supported metric type.

• LSP Database Overload Bit (O) ‚ Bit 3. This is set to indicate that the origin router is overloaded and could be experiencing resource (memory or processing) starvation prob-lems. No paths should be calculated through the origins of LSP with the overload bit set. The Cisco IOS Software command set-overload-bit can manually set the overload bit for administrative and resource-management purposes. The overload bit is also known as the hippity bit.

• IS Type ‚ Bits 1 and 2. This field indicates the type of router issuing the LSP. Bit 1 only is set for a Level 1 router, and both bits are set for a Level 2 router. The other combinations are unused. Obviously, if the IS type is set for a Level 2 router in a Level 1 LSP, the source is a Level 1 ‚ 2 router.

Example 10-1 shows the output of the Cisco IOS Software command show isis database detail. As mentioned previously, the key elements of an LSP are captured in this output. This is a very useful command for troubleshooting IS-IS routing problems involving missing routes.

Example 10-1 Displaying Details of an LSP on a Cisco Router

 GSR2#  show isis database level-2 detail RTA.00-00  IS-IS Level-2 LSP RTA.00-00 LSPID             LSP Seq Num    LSP Checksum     LSP Holdtime      ATT/P/OL  GSR2.00-00      * 0x0000000E     0x08B5           986                0/0/0  Area Address: 49.0001   NLPID:        0xCC   Hostname: RTA   IP Address:   13.1.1.2   Metric: 10         IS RTA.02   Metric: 10         IS RTB.01   Metric: 10         IS RTC.00   Metric: 10         IP 10.1.1.0 255.255.255.252   Metric: 10         IP 12.1.1.0 255.255.255.0   Metric: 10         IP 13.1.1.2 255.255.255.255 

Flooding and Database Synchronization

The IS-IS functional process responsible for maintaining the link-state database (that is, generating local LSPs, receiving and advertising LSPs to neighbors) is referred to as the update process. The update process plays an important role in IS-IS routing by making sure that routers in the domain receive timely , reliable, and complete information about the routing environment. This information is necessary for determination of optimal paths to various destinations throughout the network. The process by which LSPs are advertised and distributed between routers in a domain is known as flooding. When a router receives LSPs from its neighbors, it stores copies in its local database and then forwards copies to neighbors on links other than those on which the LSPs were received. All L1 routers in the same area ultimately build identical collections of Level 1 LSPs in their Level 1 database. The same thing applies to the Level 2 routers that are connected to the backbone. Under stable conditions, the Level 2 routers in the domain have the same set of LSPs in their Level 2 link-state databases just as Level 1 routers in the same area have the same set of LSPs in their Level 1 databases. The process of ensuring that every router receives all known LSPs in the Level 1 or Level 2 databases is referred to as database synchronization. Other auxiliary functions carried out by the update process ensure database synchronization.

Various timers and control mechanisms are employed to guarantee effectiveness of the update process in carrying out flooding and database synchronization. Sequence Number PDUs ( SNPs ) provide control of the synchronization process. Actually, there are two types of SNPs:

• Complete sequence number PDUs (CSNP) ‚ Contain summaries of all LSPs known by the issuing router

• Partial sequence number PDUs (PSNP) ‚ Contain summaries of only a subset of known LSPs and solicit newer versions of a complete LSP or acknowledge receipt of LSPs

Each LSP summary in a CSNP or PSNP consists of the following attributes from the header of the original LSP:

• Remaining lifetime

• LSP ID

• LSP sequence number

• LSP checksum

Figure 10-13 elaborates how CSNPs and PSNPs are used for LS database synchronization. The complete formats of CSNP and PSNP are provided at the end of the chapter in the section titled "Additional IS-IS Packet Information."

Figure 10-13. LSP Flooding and Synchronization

As noted previously, various timers play significant roles in the flooding and database-synchronization process. Table 10-6 lists some key timers employed by the update process. Also featured are their default values in Cisco IOS Software, which mostly conform to values specified by ISO 10589. The right-most column of the table lists corresponding Cisco IOS Software commands for modifying the default timer values.

Table 10-6. Link-State Database Update Timers

Timer	Description	Default Value	Cisco IOS Software Command to Set Timer
Maxage	This interval refers to the maximum life span of an LSP. Upon generation of a new LSP at the source, its remaining lifetime or LSP holdtime is set to this value. The default is 1200 seconds (20 minutes). An LSP expires after this interval elapses, and it then is purged from the database. LSP expiration allows cleanup of stale information from the LS database.	1200 seconds (20 minutes)	isis max-lsp-interval seconds
LSP Refresh Interval	LSPs normally are replaced if there is any change in the routing environment of the originator. To purge the LS database of stale information because of rogue LSPs, each router periodically refreshes the network with a current copy of its LSP before it is due to expire.	900 seconds	isis refresh-interval seconds
LSP Transmission Interval	This timer specifies the minimum interval between consecutive transmissions of two LSPs by the same router.	33 ms	isis lsp-interval milliseconds
LSP Retransmit Interval	This timer sets the interval between retransmission of an LSP on a point-to-point link until a PSNP acknowledgment for the LSP is received.	5 seconds	isis retransmit-interval seconds
CSNP Interval	This interval specifies the periodic spacing between successive transmissions of CSNPs by the designated IS on a broadcast link.	10 seconds	isis csnp-interval seconds { level-1 level-2 }

Figure 10-13 shows a network with a point-to-point connection between RT1 and RT2. RT2 also is connected to RT3 and RT4 over a broadcast LAN. Also depicted is the process of LSP flooding over the point-to-point and LAN links. IS-IS uses a reliable flooding mechanism on point-to-point links in which LSPs flooded out an interface must be acknowledged with a PSNP by the node at the other end of the link. LSPs flooded over broadcast links, on the other hand, don't need to be acknowledged by the recipients. Synchronization of databases over broadcast links is carried out with the help of the designated intermediate system (DIS), which periodi-cally multicasts a summary of all known LSPs in a CSNP. Routers that notice any LSPs in the CSNP that they do not have then request the complete copies by using PSNPs. IS-IS Level 1 and Level 2 packets are advertised to the AllL1ISs and AllL2IS multidestination addresses, respectively.

In Figure 10-13, RT1 advertises an LSP (RT1.00-00) over the point-to-point connection to RT2, which acknowledges as expected with a PSNP. RT2 then saves a copy in its database and floods another copy over the LAN to RT3 and RT4. RT3 and RT4 do not acknowledge receipt of RT1.00-00. At the expiration of the CSNP timer, however, RT2, which is also the DIS on the LAN, advertises a CSNP with summaries of all known LSPs. Because RT4 obviously didn't receive a copy of RT1.00-00 transmitted by RT2, it notices that it is missing that LSP from the summary that it receives, and it requests a complete copy with a PSNP. The complete RT1.00-00 then is multicast again over the LAN by RT2.

Shortest Path First (SPF) Algorithm and IS-IS Route Calculation

The previous section discusses the link-state database and the various mechanisms for reliably populating it with LSPs. Even though LSPs are routing related information, they are not routes in themselves and need to be processed further to obtain the actual routes for forwarding data pac-kets. The IS-IS process responsible for converting the raw link-state information into routes is known as the decision process. The decision process uses the shortest path first (SPF) (Dijkstra) algorithm for calculating the paths to every known destination within an area or the backbone. Independent processes are run for Level 1 and Level 2 using the respective link-state databases as input.

The SPF algorithm ^{12 , 13} computes a shortest-path tree to all nodes in an area or the backbone with the calculating router at the root. The calculation is done in an iterative manner by using three sets:

• Unknown

• Tentative (TENT)

• Paths (PATH)

All nodes with the exception of the root initially are placed in the unknown set and are moved to the TENT set in turn , beginning with the nodes directly connected to the root. At each iteration, the node in the TENT set that is closest to the root is moved into the PATH list. The nodes directly connected to the most recent graduate from the TENT set are then moved into the TENT set if not already present. The costs of nodes in the TENT set are then adjusted for the next iteration. This continues until all nodes are in the PATH set and the shortest-path tree is completely built. Routes then are derived from the shortest-path tree.