Monday, March 12, 2012

IS-IS Link-State Database Synchronization

An IS-IS update process is responsible for flooding the LSPs throughout an IS-IS domain. An LSP is flooded to all adjacent neighbors except the neighbor from which it was received. An L1 LSP is flooded to all routers within an area; it lists the adjacencies to other L1 routers. An L2 LSP is flooded throughout the backbone to all L2 routers in the routing domain; it lists the adjacencies to other L2 routers and the areas that attached to the originating router. An IS-IS router maintains the L1 and L2 LSPs in separate L1 and L2 LSDBs.

IS-IS ignores and flooded unrecognized LSPs; OSPF ignores and discards unrecognized LSAs. An LSP is flooded to neighbors upon an adjacency up / down event, an interface changes state or is assigned with a new metric, or a change upon the routing table due to route redistribution.

Each IS originates its own L1 and/or L2 LSPs. These LSPs are identified by the System ID of the originator and an LSP Number (or Fragment ID) starting at 0. When an LSP exceeds the MTU, it is fragmented into several LSPs with Fragment IDs numbered with 1, 2, 3, and so on. L1 and L2 LSPs can share the same format, as they express routing info using different TLVs.
Note: IS-IS which runs over the data link layer unable to utilize the fragmentation service provided by the network layer; fragmentation is performed by itself to make sure that the size of any LSP does not exceed the MTU of any segment.

When an IS receive an invalid LSP which failed the checksum, the IS would discard it and flood it as an expired LSP with a lifetime of 0. If a valid LSP is newer than the entry in the LSDB, it is retained, acknowledged, and refreshed with a lifetime of 1200 seconds. The LSP lifetime is decremented every second until it reaches 0, the point that it is considered expired. As soon as an LSP expires, it is kept for an additional 60 seconds before it is being flooded as an expired LSP. The IS-IS refresh interval is 15 minutes (900 seconds) minus a random jitter of up to 25%.
The lsp-refresh-interval {sec} IS-IS router subcommand sets the LSP refresh interval.

Sequence Number PDUs (SNPs) are used to acknowledge the receipt of LSPs and maintain LSDB synchronization. There are 2 types of SNPs – Complete Sequence Number PDU (CSNP) and Partial Sequence Number PDU (PSNP). The usage of SNPs differs between broadcast networks and point-to-point links.

CSNPs and PSNPs share the same format and carry summarized LSP information. The main difference between them is that CSNPs contain summaries of all LSPs in the LSDB; whereas PSNPs contain only a subset of LSP entries. Specific L1 and L2 CSNPs and PSNPs are being used for L1 and L2 routing. SNPs are never flooded but only sent between neighbors.

Adjacent IS-IS routers exchange CSNPs to compare their LSDB. On broadcast networks, only the DIS transmits CSNPs. All adjacent neighbors compare the summary of LSPs received in the CSNP with the contents of their local LSDBs to determine whether their LSDBs are synchronized and have all the same LSPs as other routers for the appropriate levels and areas. Multicast CSNPs are sent periodically every 10 seconds by the DIS to ensure LSDB accuracy. (*TBC*) Adjacent IS-IS routers send PSNPs to request transmission of missing or newer LSPs. DIS and all ISs don’t send explicit ACKs for each LSP.

If there are too many LSPs to include in a single CSNP, they are sent in ranges. The CSNP header indicates the starting and ending LSP ID in the range. If all LSPs in the LSDB can be fit into a single CSNP, the range is set to default values – Start LSP ID (0x0000.0000.0000.00-00) and End LSP ID (0xFFFF.FFFF.FFFF.FF-FF).

On a LAN, the DIS periodically (every 10 seconds) multicasts CSNPs that list the LSPs in its LSDB to all L1 or L2 IS-IS routers on the LAN – the DIS is continually performing full LSDB synchronization with all IS-IS routers on the LAN. The DIS is responsible for flooding LSPs to all IS-IS routers on the LAN; having only the DIS to send LSPs minimizes the amount of traffic upon synchronizing the LSDBs.
Note: Unlike OSPF, IS-IS does not explicitly acknowledge LSPs flooded over a LAN.

IS-IS LSDB Synchronization on a Broadcast Network

Figure above shows IS-IS LSDB synchronization over a LAN. RT4 compares the LSPs in the CSNP sent by the DIS with its LSDB. If its LSDB has a newer version of the LSP in the CSNP, or the CSNP does not include an LSP in its LSDB, it would multicast the LSP onto the LAN. In this case, RT4 is missing an LSP – LSP2. It sends a PSNP to the DIS (RT1) to request the missing LSP. Although the PSNP is a multicast packet, only the DIS will take action and reissue the missing LSP – LSP2 to RT4. Finally RT4 acknowledges it with a PSNP.
Caution: This scenario might be inaccurate, because no PSNPs were seen on LAN environments yet.

CSNPs are not being periodically sent out on point-to-point links as on broadcast networks. A CSNP is sent only once upon a point-to-point link first comes up to synchronize the LSDB. After that, an LSP is sent upon topology change or IS-IS refresh, and it is being acknowledged using a PSNP.

When an adjacency is established over a point-to-point link, each end router sends a CSNP that summarizes the LSP entries (LSP-ID, Sequence Number, Remaining Lifetime, and Checksum) in its LSDB to another router. When a router has an LSP in its LSDB that is not listed in the CSNP received from the other end, it would send the missing LSP to the other router; when a router realizes that its LSDB is missing any LSP as listed in the received CSNP, it would send a PSNP to request the full LSP. The LSP is then acknowledged via a PSNP. The minimumLSPTransmissionInterval timer (default 5 seconds) it set upon sending an LSP. The LSP is resent if the explicit PSNP acknowledge is not received before the timer expires.

IS-IS LSDB Synchronization over a Point-to-Point Link upon a Link Failure

Figure above shows IS-IS LSDB synchronization over a point-to-point link upon a link failure.
  1. The link between RT2 and RT3 fails.
  2. RT2 notices the link failure and issues a new LSP describing the topology change.
  3. RT1 receives the LSP, stores it in its LSDB, and sends a PSNP back to RT2 to acknowledge the receipt of the LSP.

IS-IS routers use the following processes to build the OSI forwarding database (or the CLNS routing table) to select the best path to a destination.
  • Performs SPF calculation twice upon the information in both L1 and L2 LSDBs to build the SPTs to OSI L1 and L2 devices (NETs).
  • Calculates ES reachability using Partial Route Computation (PRC) based on the L1 and L2 SPTs. There are no ESs in a pure IP Integrated IS-IS environment.
  • Inserts the best paths in the OSI forwarding database (or the CLNS routing table).
Integrated IS-IS includes IP prefix reachability information in the LSPs, treating it as if it were ES information. IP subnets are treated the leaf objects of the IS-IS SPT. Therefore, processing IP reachability info requires only a PRC, similar to ES reachability.

The PRC generates best-path for IP subnets and offers the routes to the IP routing table, where they are accepted based on normal administrative distance rule of IP routing table. IS-IS IP routes are shown as i L1 or i L2 routes accordingly in the IP routing table.

The separation of IP reachability from the core IS-IS network architecture makes Integrated IS-IS much scalable than OSPF.
  • OSPF sends LSAs for individual IP subnets. An LSA will be flooded throughout the network upon an IP subnet failure, which all routers must run a full CPU-intensive SPF calculation upon the convergence process.
  • Integrated IS-IS builds the SPT using CLNS information. Since IP subnets are treated as leaf objects of the IS-IS SPT, the loss of an IP subnet does not affect the underlying CLNS architecture – the SPT is unaffected, and hence only required to perform a PRC. Any time an internal link between routers or a router fails, a full SPF calculation must be performed for that area.

The routing process for IS-IS is divided into 4 stages:
  • Update. Routers forms neighbor relationship and exchange routing information between them using IIHs, LSPs, and SNPs prior to forwarding packets.
  • Decision. After the LSDBs have been synchronized, each router builds SPTs by placing itself at the root of the trees, and uses its LSDB to calculate the shortest paths to all devices within the same L1 area as well as to other L1 areas through the L2 backbone.
  • Forwarding. The forwarding database can then be built after the SPT has been built during the decision process. The forwarding table is essentially a lookup table for the longest match to forward and load balance packets multiple equal-cost paths. The forwarding table for Integrated IS-IS is more relevant to CLNS than to IP because the IP routing information is entered directly into the IP routing table, where IP routes are leaves on the IS-IS SPT.
  • Receive. If the frame is valid, the receive process passes user data and error reports to the forwarding process, whereas routing information Hellos, LSPs, and SNPs are sent to the update process. The receive process is not described in depth here because it is mainly applicable for CLNS routing. A detailed description is given in the ISO 10589 standards document.
IS-IS LSPs contain the following 3 fields that help to determine whether a received LSP is more recent than the entry held in the LSDB, and even if it is corrupted.
  • Remaining Lifetime. Used to age out expired LSPs. The IS-IS refresh interval is 15 minutes. If an LSP has been held in the LSDB for 20 minutes, it is assumed that the originating router is dead. When the lifetime expires, the LSP has the content removed, and leaving only the header. The lifetime is set to 0 and flooded through the network (to show that it is a new LSP). All receiving routers accept the incomplete LSP, recognize that the route is no longer valid, and purge the existing LSP from their LSDBs. IS-IS protects against flooding loops by decrementing the lifetime of an LSP by at least 1 at each flooding hop.
    The max-lsp-lifetime {sec} IS-IS router subcommand sets the maximum time that LSPs can remain in the LSDB without being refreshed. The value set for the lsp-refresh-interval command must be less than the value set for this command; otherwise, LSPs will time out before they are refreshed.
    If the LSP lifetime is misconfigured to be too low compared to the LSP refresh interval, Cisco IOS will reduce the LSP refresh interval to prevent the LSPs from timing out.
    Router(config-router)#max-lsp-lifetime 800
    % ISIS: max-lsp-lifetime should be greater than lsp-refresh-interval(900)
    % ISIS: Setting lsp-refresh-interval to 770
    Router(config-router)#do sh run | in lsp
     max-lsp-lifetime 800
     lsp-refresh-interval 770
  • Sequence Number. An unsigned 32-bit linear number. The 1st LSP is allocated the sequence number of 1, and subsequent LSPs are incremented by 1. Receiving a valid LSP that has the same sequence number as the one in the LSDB is simply ignored.
  • Checksum. Upon receiving an LSP that has an invalid checksum, the router would discard it and flood it as an expired LSP with a lifetime of 0. All routers purge the LSP, and the originating router resends a new LSP.

IS-IS ignores incomplete fragment PDUs, which often caused by packet loss or corruption. Any fragmented LSP received is ignored if the starting fragment is not being received. The sequence of fragmented PDUs are indicated using the LSP Number (or Fragment ID) in the LSP ID field of the IS-IS PDU header.
Below summarizes the technical differences between Integrated IS-IS and OSPF:
Integrated IS-IS
Areas Boundaries are defined on links.
A router can only be in one area.
Note: the multiarea IS-IS is mainly used during area migrations and transitions.
Boundaries are defined on routers.
Interfaces can be in different areas.
A router can be in many areas.
An Integrated IS-IS L1 area is similar to an OSPF stub area.
Designated Router (DR) A router with higher priority (or higher MAC address if the priority is same) will preempt and become the new DIS.
Adjacencies are created between the DIS with all routers on a LAN.
Each IS sends a multicast LSP to all ISs on the LAN. The LSP is unacknowledged.
A router with higher priority does not preempt the existing DR.
Adjacencies are formed with the DR and BDR only on a LAN.
All LSAs are acknowledged.
Encapsulation Runs on top of the data link layer.
A network layer protocol that defines its own Layer 3 PDUs.
Fragmentation is the responsibility of Integrated IS-IS.
OSPF is an IP application.
Has an OSPF header and encapsulated inside an IP packet.
Fragmentation is the responsibility of IP.
LAN Flooding All ISs maintain adjacencies with all other ISs on a LAN.
DIS sends CSNP to all ISs.
Periodic CSNPs (every 10 seconds) ensure the databases are synchronized.
Multicast updates and Hellos sent to the AllDRouters – DR and BDR.
Unicast acknowledgments sent from all routers to the AllDRouters – DR and BDR.
LSAs 2 types of LSP – L1 LSP and L2 LSP.
LSPs are TLV-encoded.
Ignores and floods unrecognized LSPs.
LSPs are always flooded across all media by the originating router.
7 types of LSA.
Discards and does not flood unrecognized LSAs.
Many small and separated LSAs for summary and external route updates.
Every router generates LSUs.

No comments:

Post a Comment