Definition of link state routing algorithm in Network Encyclopedia.
What is Link State Routing Algorithm?
Link State Routing Algorithm is a routing method used by dynamic routers in which every router maintains a database of its individual autonomous system (AS) topology. The Open Shortest Path First (OSPF) routing protocol uses the link state routing algorithm to allow OSPF routers to exchange routing information with each other.
How it works
An AS or routing domain is a group of networks that use the same routing protocol and are under a common administration. All routers in an AS have identical link state databases, which contain information about each router’s local state. Routers distribute their local state by using link state advertisements (LSAs), which contain information about neighbors and route costs. From these LSAs, each router builds a hierarchical tree containing least-cost paths to other networks, with the router itself as the root of the tree. Least-cost paths are determined by preassigned factors such as the number of hops between routers, the speeds of the network links connecting them, and traffic flow patterns.
The link state routing algorithm used by the OSPF protocol offers the following advantages over the distance vector routing algorithm used by the Routing Information Protocol (RIP):
RIP routers exchange their entire routing table on a periodic basis, adding to overall network traffic, while OSPF routers exchange only routing table updates.
RIP routers use only the single metric hop count to create their routing tables, while OSPF routers can also use link speeds and traffic patterns to establish cost values for routing traffic.
On the other hand, OSPF requires considerably more processing on the part of the router, making it more expensive to implement. OSPF is also more complex to configure than RIP.
Link-State Routing Sends Changed Data Only When There Is a Change
A network that uses a link-state protocol triggered updates, which include data on the state of only links that have changed, are sent in this network. In link-state protocols, the information about connected links (including the subnets on those links) on all routers is flooded throughout the network or to a specific area of the network. Therefore, all routers in the network have detailed knowledge of the entire network. In contrast, routers running a distance vector routing protocol receive knowledge about only the best routes from their neighbors.
Optimized Link State Routing Protocol
The Optimized Link State Routing Protocol (OLSR) is a link-state routing protocol optimized for mobile ad hoc networks (which can also be used on other wireless ad hoc networks). OLSR is proactive, it uses Hello and Topology Control (TC) messages to discover and disseminate link state information into the mobile ad hoc network.
Using Hello messages each node discovers 2-hop neighbor information and elects a set of multipoint relays (MPRs). MPRs makes OLSR unique from other link state routing protocols. Individual nodes use the topology information to compute next hop paths regard to all nodes in the network using shortest hop forwarding paths.
Distance Vector and Link State Protocols
In this video, we talk about the two classes of routing protocols. The advantages and drawbacks of the Distance Vector and Link State Protocols.
Link-State Versus Distance Vector
Link-state algorithms (also known as shortest path first algorithms) flood routing information to all nodes in the internetwork. Each router, however, sends only the portion of the routing table that describes the state of its own links. In link-state algorithms, each router builds a picture of the entire network in its routing tables. Distance vector algorithms (also known as Bellman-Ford algorithms) call for each router to send all or some portion of its routing table, but only to its neighbors. In essence, link-state algorithms send small updates everywhere, while distance vector algorithms send larger updates only to neighboring routers. Distance vector algorithms know only about their neighbors.
Because they converge more quickly, link-state algorithms are somewhat less prone to routing loops than distance vector algorithms. On the other hand, link-state algorithms require more CPU power and memory than distance vector algorithms. Link-state algorithms, therefore, can be more expensive to implement and support. Link-state protocols are generally more scalable than distance vector protocols.
External references:
- CISCO MANUAL – Routing Basics manual Routing Manual
- BOOK -Routing Protocols Companion Guide, published Feb 24, 2014 by Cisco Press. Part of the Companion Guide series. Check it on Amazon
- PAPER – Rbridges: Transparent Routing by Radia Perlman Rbridges
