Link-state routing protocols are also known as shortest path first protocols and are built around Edsger Dijkstra’s shortest path first (SPF) algorithm. There are two link-state routing protocols for IP: OSPF (Open Shortest Path First) and IS-IS (Intermediate-System-to-Intermediate-System).
The link-state process can be summarized as follows:
1. Each router learns about its own directly connected networks.
2. Each router is responsible for “saying hello” to its neighbors on directly connected networks.
3. Each router builds a Link-State Packet (LSP) containing the state of each directly connected link.
4. Each router floods the LSP to all neighbors, who then store all LSPs received in a database.
5. Each router uses the database to construct a complete map of the topology and computes the best path to each destination network.
A link is an interface on the router. A link-state is the information about that interface including its IP address and subnet mask, the type of network, the cost associated with the link, and any neighbor routers on that link.
Each router determines its own link-states and floods the information to all other routers in the area. As a result, each router builds a link-state database (LSDB) containing the link-state information from all other routers. Each router will have identical LSDBs. Using the information in the LSDB, each router will run the SPF algorithm. The SPF algorithm will create an SPF tree, with the router at the root of the tree. As each link is connected to other links, the SPF tree is created. Once the SPF tree is completed, the router can determine on its own the best path to each network in the tree. This best path information is then stored in the router’s routing table.
Link-state routing protocols build a local topology map of the network that allows each router to determine the best path to a given network. A new LSP is sent only when there is a change in the topology. When a link is added, removed or modified, the router will flood the new LSP to all other routers. When a router receives the new LSP, it will update is LSDB, rerun the SPF algorithm, create a new SPF tree, and update its routing table.
Link-state routing protocols tend to have a faster convergence time than distance vector routing protocols. A notable exception is EIGRP. However, link-state routing protocols do require more memory and processing requirements. This is usually not an issue with today’s newer routers.
Link state routing protocols use the shortest path first (SPF) algorithm, aka Dijkstra’s algorithm
In link state terminology, a link is an interface on a router
A link state is the information regarding that link. This can include the routers IP address, the type of network, the cost of the link, and if there are any neighbouring routers on that link
A neighbor is a router tha shares a link, a directly connected network with another router. Routers discover their neighbors by using the hello packets of a specific routing protocol
Routers store LSPs in link state databases also known as topological databases. The SPF algorithm is run using these LSPs to create the SPF tree and determine the shortest path to each network
Link state routing protocols do not send out typical peroidic updates like rip or IGRP. OSPF routers do send out their own LSPs every 30 minutes, however this is used differentlly than a periodic update.
Link state advantages are;
- use of a topological map, SPF tree of the network
- Faster convergence (EIGRP is an exception)
- No periodic updates unlike some distance vector routing protocols
- Specific LSP flooded only when there is a change in the topology
The requirements for using a link state routing protocol are;
- More memory for link state database
- More CPU processionf for the SPF algorithm
- More bandwidth for flooding of LSPs
Two common link state routing protocols used today are OSPF and IS-IS
