LSP is also called Shortest Path First or Distributed Database Protocols and is built on the E. W. Dijkstra’s shortest path algorithm. Examples of LSP include: OSPF, ISO’s ISIS for CLNP and IP, and Novell’s Netware Link Services Protocol (NLSP).
Dijkstra Algorithm is also called Shortest Path Tree (SPT) algorithm.
Functionality
- Determine neighbors
Each router (or node) must establish an adjacency with neighbors. Each router does so by announcing itself on the link through a Hello Protocol. Once the neighbor relationship is established, router can forward to exchange link information.
- Distribution of Link-State Information
Once adjacencies are established, each node sends a data unit called Link State Advertisement (LSA). An LSA on a very basic level includes:
- The identification of the node producing the LSA
- Identifies the neighbor attached
- The links attached to the node and associated metric
- The sequence number which increases every time a newer LSA is generated
FIGURE-1: Distribution of Link-State Information
This LSA is then flooded throughout the network. Each node receiving the LSA, in turn, floods to its adjacent neighbors.
- Creating IP Routing Table
Once each node has the complete view of the network, called the Link-State DataBase (LSDB), this information is used by SPT to create a graph of the network representing the shortest path to each router in the network. The IP routing table is then built from the LSDB. With link-state protocols, the best path is always the shortest path. Figure-2 shows the IP routing building process.
FIGURE-2: LSDB and IP Routing Table
This brings us to the end of this article in which we covered the operations of Link State Routing Protocols. As compared to Distance Vector Routing Protocols, Link State Routing Protocols are more complex to understand and implement but they are very scalable and that is the reason why they are widely deployed in all types and sizes of networks.