Monday, December 12, 2011

OSPF Link-State Database

OSPF maintains a database with only the most recent and up to date link-state information or records with the use of MaxAge and LSRefreshTime timers, and LS sequence numbers.

The length of the LS Sequence Number field in an LSA header or an LSA is 32 bits. Beginning with the leftmost bit set, the first number is 0x80000001 and the last number is 0x7FFFFFFF. The sequence number is used to detect old or redundant LSA records. The larger the number, the more recent the LSA. An OSPF router would generate a new LSA upon a link-state change. One can notice which parts of the network are changing the most by looking at the LSDB – the parts that are described by LSAs whose have large LS sequence numbers and small LS ages.

An OSPF router refreshes its self-originated LSAs that it is responsible for every 30 minutes (the LSRefreshTime interval) to ensure all routers have an accurate link-state database, just in case an LSA has been lost from or corrupted in one of the databases of other routers. Every time a LSA record is flooded or refreshed, its sequence number is incremented by 1, and its aging timer is reset. An LSA will never remain in the database for more than 1 hour (MaxAge) without being refreshed; it is considered invalid (eg: the originating router has failed) and will be removed from the LSDB. This LSA validation method conserves more bandwidth than DV routing protocols, which send entire routing tables at short periodical intervals.

Since an invalid LSA may take as long as 1 hour for it to be removed from LSDBs and the LSA would certainly contain out-of-date (stale) information, OSPF requires the routers at both ends of a point-to-point link advertise the link before considering it during the route computation process.

It is theoretically possible for an LSA to exist in the database for very long periods of time, refreshed every 30 minutes, until a point where the sequence number rolls over to the beginning. When this occurs, the existing LSA must first be deleted by prematurely aged out (MaxAge is set to 1 hour) to allow other routers to accept the new LSA with sequence number of 0x80000001.
Note: A router is only allowed to update its self-originated LSAs at most once every 5 seconds. In the absence of errors, the 32-bit sequence number will require 680 years to roll over!

The OSPF premature aging process allows the deletion of an LSA from a routing domain by setting its LS Age to MaxAge and floods its without waiting for its aging timer to reach MaxAge, as sometimes a router may want to delete an LSA instead of updating its contents. In order to avoid possible thrashing in which a router originates an LSA while another router deletes it, a router is allowed to prematurely age (delete) only its self-originated LSAs.

The LS Age field of an LSA is also examined for other OSPF functions as below:

Constant Value Description
MinLSArrival 1 second Minimum rate at which a router will accept an LSA update.
MinLSInterval 5 seconds Minimum rate (rate limit) at which a router can update an LSA.
CheckAge 5 minutes The rate at which a router verifies the checksum of an LSA contained in its LSDB.
MaxAgeDiff 15 minutes 2 LSA instances are considered separate when they differ by more than 15 minutes. The LSA with the smaller LS Age is considered more recent and accepted.
LSRefreshTime 30 minutes The rate at which a router must refresh its self-originated LSAs.
MaxAge 1 hour The maximum age that an LSA is considered valid and being retained in the LSDB.

An OSPF router can easily identify its self-originated LSAs as the Advertising Router field in those LSAs is set to its own Router ID. An OSPF router is allowed to update and delete only its self-originated LSAs that it is responsible for. Knowing which router has originated a particular LSA allows a calculating router to decide whether the LSA should be used in route computation, and how it should be used.

LSA Operations upon Receiving an LSA

The show ip ospf database EXEC command displays the link-state database on a router.
RT1#sh ip ospf database

            OSPF Router with ID ( (Process ID 100)

                Router Link States (Area 0)

Link ID         ADV Router      Age         Seq#       Checksum Link count      21          0x80000002 0x000419 3      21          0x80000002 0x0039DE 3

                Net Link States (Area 0)

Link ID         ADV Router      Age         Seq#       Checksum      22          0x80000001 0x004E20

Link ID Indicates the Router ID of the source or originating router of a Router LSA, which is announced by every OSPF router for the status of its own interfaces.
ADV Router Indicates the Router ID of the source or originating OSPF router of an LSA.
Age Indicates the length of time in seconds since the LSA was last updated. The maximum age is 3600 seconds (1 hour).
Seq# Indicates the sequence number of an LSA.
Checksum Indicates the checksum of an LSA to ensure reliable receipt of the LSA.
Link count Used only in Router LSAs to indicate the total number of directly connected links, which include all point-to-point, transit, and stub links. Point-to-point serial links are count as 2 (as connections to another router and a stub network); all other links, including Ethernet, are count as 1.

No comments:

Post a Comment