In the previous articles, the basic concept about the IP routing protocol and guideline has been discussed. And a comprehensive knowledge about the basic concept of the distance vector routing has been discussed too. Distance vector routing is fine for small to medium sized networks. But for enterprise class sized networks, a more robust method is required. The link state method offers several advantages over the distance vector method.
Link-state and distance vectors share a common goal—filling the routing tables with the currently-best routes. They differ significantly in how they accomplish this task. The largest difference between the two is that distance vector protocols advertise sparse information. In fact, distance vector protocols know that other routers exist only if the other router broadcasts a routing update to them.
When a distance vector protocol in a router receives a routing update, the update says nothing about the routers beyond the neighboring router that sent the update. Conversely, link-state protocols advertise a large amount of topological information about the network, and the routers perform some CPU-intensive computation on the topological data. They even discover their neighbors before exchanging routing information.
The figure illustrates a graphical representation how the router advertises with a link-state protocol. Router B tells Router A the metric associated with every link in the network, rather than Router B’s telling Router A what the metric (or cost) for the route should be. Besides, router B also tells router A about all the routers in the network, including which subnets they are attached to and their status. It’s like a map of a mathematical model of the network based on the topology information.
The link-state protocol on Router A calculates the lowest-cost route to all subnets based on the topology information, including the route to subnet 10.1.1.0, mask 255.255.255.0. When more than one route to a subnet exists, the link-state routing protocol chooses the lowest metric. Packets traveling to 10.1.1.0 from Router A go through Router C because this route has the lower cost.
Unlike distance vector protocols, link-state protocols must calculate the metric instead of simply being told the metric in the received routing update. For instance, with distance vector protocols, Router B tells Router A something like “subnet 10.1.1.0, metric 3.” With link state protocols, the topology information learned by a router includes a cost associated with each link in the network. A router totals the cost associated with each link in each route to find the metric associated with the route.
For instance, Router A discovers two routes to subnet 10.1.1.10, with a metric of 220 for the route to 10.1.1.0 through Router C and a metric of 310 for the route to 10.1.1.0 through Router D. In both cases, Router A uses Router B as the next hop. Therefore, Router A puts a route to 10.1.1.0 in its routing table, using Router B’s interface IP address as the next hop. Similarly, Router B calculates routes to 10.1.1.0 through Router C and Router D and places the better route (through Router C) in Router B’s routing table.
The algorithm used to calculate routes with link-state protocols is called the Shortest Path First (SPF) algorithm or Dijkstra SPF algorithm.
Link-state protocols do not just start broadcasting topology information out every interface when the router first boots. Instead, link-state protocols first use a process by which they discover neighbors. (Neighbors can also be statically defined instead of being discovered.)
Neighbors are other routers, also running the same link-state protocol, that share a common subnet. As soon as routers know that they are neighbors, they can exchange their respective copies of the topology information—called the topology database—and then run SPF to calculate new routes.
After a router identifies a neighbor, they exchange the information in their topology databases. The routing updates sent by an OSPF router are called link-state updates (LSUs), and the items sent in an LSU include individual link-state advertisements (LSAs). For instance, a link LSA describes a subnet number and mask, the cost (metric), and other information about the subnet. Also, OSPF uses a reliable protocol to exchange routing information, ensuring that lost LSU packets are retransmitted.
Keep in mind the following information about the links state method:
- Routers broadcast LSPs to all routers (this process is known as flooding)
- Routers send information about only their own links
- LSPs are sent at regular intervals and when any of the following conditions occur:
- There is a new neighbor
- A neighbor has gone down
- The cost to a neighbor has changed
- Routers use LSPs to build their tables and calculate the best route
- Routers select routes based on the shortest route using an algorithm known as shortest path first (SPF)
- Network administrators have greatest flexibility in setting the metrics used to calculate routes
The link state method is less susceptible to routing loops, but requires more complicated routines to discover the network and calculate the best paths.
Links state problems and solutions
Although more stable than the distance vector method, the link state method has the following problems:
- It requires more router resources (processor power and memory)
- It generates high amount of traffic when LSPs are initially flooded through the network. however, after the initial configuration occurs, the traffic from the l inks state method is smaller than that from the distance vector method
- It is possible for LSPs to get delayed or lost, resulting in an inconsistent view of the network. This is particularly a problem for larger networks, if parts of the network come on line at different times, of if the bandwidth between links vary (i.e. LSPs travel faster through parts of the network than through others.
In particularly, the last problem is of the greatest concern. The following solutions are often implemented to overcome some of the effects of inconsistent LSP information.
- Slowing the LSP update rate keeps information more consistent
- Routers can be grouped into areas. Routers share information within the area, and routers on area borders share information between areas.
- LSPs can be identified with a time stamp, sequence or ID number, or aging timer to ensure proper synchronization.
- One router in each area is designated as the authoritative source of routing information (called a designated router). Each area router receives updates from the designated router.
Link State advantages and disadvantages
The link state method has the following advantages over the distance vector method
- Less convergence time (because updates are forwarded immediately)
- Not susceptible to routing loops
- Less susceptible to erroneous information (because only firsthand information is broadcast)
- Bandwidth requirements negligible for a typical LAN environment
Link state has the following disadvantages:
- The link state algorithm requires greater CPU and memory capability to calculate the network topology and select the route
- Increased network traffic when the topology changes
Link state routing protocols are typically used by enterprise networks which consist of many offices around the world, or used by ISPs.
