Peter Matheka

Definition

The cost/metric is based on number of hops, link speeds, traffic congestion, and other factors as determined by the network designer. Link state routers use Dijkstra's algorithm to calculate shortest (lowest cost) paths, and normally update other routers with whom they are connected only when their own routing tables change.

Link state routing is an improvement over distance-vector routing protocols such as RIP which normally use only a single metric (such as hop count) and which exchange all of their table information with all other routers on a regular schedule. Link state routing normally requires more processing but less transmission overhead.

Ref:

http://wombat.doc.ic.ac.uk/foldoc/foldoc.cgi?Link+State+Routing+Protocol

Link-state involves each router building up the complete topology of the entire internetwork (or at least of the partition on which the router is situated), thus each router contains the same information. With this method, routers only send information to all of the other routers when there is a change in the topology of the network. Link-state is also known as shortest path first. Typical link-state protocols are OSPF, BGP and EGP. The main problem with link-state is that routers require much more processing power to update the database, and more memory as routers require to build a database with details of all the routers on the network.

In contrast to the distance-vector routing protocol which works by sharing its knowledge of the entire network with its neighbors, link-state routing works by having the routers inform every router in the network about its nearest neighbors. The entire routing table is not distributed from any router but only the part of the table containing its neighbors.

1. The neighbor information is gathered continuously.
2. The neighbor information list is then broadcasted to every router that can answer to this protocol, a process known as flooding, which means that it sends the information to all of its neighbors who in turn send it to all of their neighbors and so on. Soon, all routers on the network have this information.
3. The neighbor information is flooded whenever there is a (routing-significant) change in the network.
4. As every router knows everything about the network by structuring the information from other routers, it can calculate the best path to any host on any destination network by using Dijkstra's algorithm.

Ref: Distributed Systems and Networks by William Buchanan Page 380

http://www.sciencedaily.com/encyclopedia/Link-state_routing_protocol

Link-state - Concepts                            

The link state algorithm (known as shortest path first) maintains a complex database on the topology of a network. Each router thus has the complete picture of the whole of the network and has knowledge of distant routers, and how they interconnect. The distance-vector, on the other hand, has non-specific information on distant networks, and no knowledge of distant routers.

The link-state algorithm uses link-state advertisements (LSAs) to advertise routing information from routers. From this each router builds-up a topological database with themselves at the top of the tree, and uses a shortest path first (SPF) algorithm to determine the best route to get to a destination. Initially on start-up, each router must discover the routes which it connects to. Next each router advertises its connection to all the other routers on the network. From this it builds a topology database with the information. There may be multiple routes to get to a destination, thus the SPF algorithm is used to determine the best route. It is this route that is then used in the topological database. All the routers on the network will thus have the same information. The link-state approach only sends routing information when there is a change in the topology of the network. This information floods to all the other routers in the network (the discovery process), thus all routers are updated with the new information.

In order for the link-state algorithm to work, a router must keep communicating with its neighbors to determine if they are still responding to communications, and if they have any changes in their link metrics. Each router only uses the most up-to-date information from LSA packets to build up the complete topological database.

The main problem with link-state, as opposed to distance-vector, is that the algorithm much more processing power, and also increased amount of memory to store up-to-date LSAs and the complete topological database. With Dijkstra's algorithm the processing task is proportional to the number of links in the internetwork multiplied by the number of routers in the network.

Ref: Distributed Systems and Networks by William Buchanan Page 384

The link-state algorithm periodically distributes link-state packets (LSPs), which are developed at every router participating in the network. The contents of an LSP include:

1. That router's ID.
2. The ID of one of the router's neighbors.
3. The cost of the link to that neighbor.

When a router receives an LSP, it tries to store it in its own LSP database. If the information contained in the LSP just received already exists in the database, no action is taken. Otherwise, the router stores it in its own database and forwards a copy of the LSP it just received to every neighboring router (except the one from which it just received the packet).

When every router in the network has a consistent LSP database, each router individually computes the optimal paths to all other network nodes. The algorithm used to do this usually is Dijkstra's algorithm.

Ref:

http://links.math.rpi.edu/devmodules/graph_networking/compat/page33.html

Problems                                               

The main problems with link-state are:

                                                                                                           References                                              

http://www.sce.umkc.edu/~beardc/ieeeNWmag-huang.pdf

http://www.usm.maine.edu/~houser/cos460/lecture_notes/link_state_routing_ospf.html

http://wombat.doc.ic.ac.uk/foldoc/foldoc.cgi?Link+State+Routing+Protocol

http://en2.wikipedia.org/wiki/Link-state_routing_protocol

http://www.freesoft.org/CIE/RFC/1583/4.htm

http://www.zvon.org/tmRFC/RFC2791/Output/chapter5.html