- Routing protocols may use two main classes of routing protocols, Distance-Vector Routing protocol and Link-State Routing protocol used in packet-switched networks for computer communications. Examples of link-state routing protocols include OSPF and IS-IS.
- The link-state protocol is performed by every switching node in the network. The basic concept of link-state routing is that every node constructs a map of the connectivity of the network, in the form of a graph showing which nodes are connected to which other nodes.
- Each node then independently calculates the best next hop from it for every possible destination in the network. The collection of best next hops forms the routing table for the node.
Determining the neighbor node
First, each node needs to determine what other ports it is connected to, over fully-working links; it does this using a simple reachability protocol which it runs separately with each of its directly-connected neighbors.
Distributing the information for the map
Next, each node periodically makes up a short message, the link-state advertisement, which:
- Identifies the node which is producing it.
- Identifies all the other nodes to which it is directly connected.
- Includes a sequence number, which increases every time the source node makes up a new version of the message.
This message is then flooded throughout the network. Each node in the network remembers, for every other node in the network, the sequence number of the last link-state message which it received from that node. Starting with the node which originally produced the message, it sends a copy to all of its neighbors. When a link-state advertisement is received at a node, the node looks up the sequence number it has stored for the source of the link-state message. If this message is newer (i.e. has a higher sequence number), it is saved, and a copy is sent in turn to each of that node’s neighbors.
Calculating Shortest Path
Each node independently runs an algorithm over the map to determine the shortest path from itself to every other node in the network; generally some variant of Dijkstra’s algorithm.
Contrast with Distance-vector
Distance vector routing protocols which work by having each node share its routing table with its neighbors. In a link-state protocol, the only information passed between the nodes is information used to construct the connectivity maps.
Effectiveness of Link-State
Link-state routing responds faster to broken links or the addition of links. Routes can be based on the avoidance of congested areas, the speed of a line, the cost of using a line, or various priorities. OSPF (Open Shortest Path First) is the most common routing protocol to use the link-state algorithm.