Link state database
A link state database (LSDB) is the name given to the data structure located on a router that stores the link state advertisements (LSA) produced by a link state routing protocol such as Open Shortest Path First (OSPF) or Intermediate System to Intermediate System (IS-IS).
Link state routing protocols operate by exchanging link status information between routers. The information is flooded to all of the routers that share the same routing protocol in a given part of the network, often called an area. Each router, then, should receive identical information when an update is sent, and if each router stores that information in a local LSDB, the implication is that each router in that area has an identical copy of this LSDB.
The link state information describes the various links that exist within the network. Indeed, a link state routing protocol models the topology of the network as a connected graph: a set of dots connected by lines. In general, each network and each router in the internetwork is a dot. The interface that connects a particular router to a particular network is the link connecting those dots. The link state database contains information about every dot (network, router) and every link. Routers are identified by an number. Links are identified by cost, type, address, and perhaps even transmission rate. Networks are identified by type.
The database, therefore, contains enough information to draw a detailed, if somewhat abstract, diagram of the network. It is based on this abstract model that each router calculates its best cost routes to every possible destination in the internetwork using a shortest path first (SPF) algorithm.
Areas and LSDBs
In a link state routing protocol, as an area becomes increasingly large, the LSDB likewise grows. As it does so, the calculations to build the routing table become more involved and more processor intensive. Furthermore, if there are thousands of routers within an area, the number of changes being advertised scale geometrically. Since these are flooded, they consume more bandwidth and cause route recalculation more frequently.
To control this, link state routing protocols support the division of an internetwork into multiple areas. Routers only exchange LSAs with other routers within the same area. This keeps the size of the LSDB under control, route recalculation is minimized, and network stability is enhanced.
Clearly, however, if the network were partitioned into areas with no communication of routing information between areas, no one would ever be able to send a packet outside of the local area. To address this, some routers in the network play a special function by sitting at the boundary between areas. These routers will have multiple LSDBs, one for each area they participate in. They will summarize routes from one area into another area to ensure routers within that area build complete routing tables.
Because the routing tables in a router running a link state routing protocol are based on the LSDB, it is critical that all of the routers in a given area have identical copies of the LSDB. As soon as one router has an LSDB that is out of sync, it can calculate routes incorrectly and create routing loops or otherwise cause routing to fail.
This is why link state routing protocols work so hard to ensure database synchronization. When a router is initialized, it locates a neighbor and retrieves a complete copy of the local LSDB from that system. It builds relationships called adjacencies with other local routers and periodically verifies that its local database is still aligned with that in other routers. And LSA, when sent, are acknowledged to ensure they have been accurately received.
|<mp3>http://podcast.hill-vt.com/podsnacks/2008q2/X.mp3%7Cdownload</mp3> | Link state database (LSDB)|