Link-State Routing

In distance-vector routing, the information about the topology of the network is distributed among the routers, which achieves efficiency but also creates problems.

An alternate approach, used in link-state routing, is to give each router complete information about the graph of the network. Then, each router independently computes the optimal path to every destination.

Thus, the main questions to be answered in order to make this approach work are:

1. How will knowledge of the network's topology be distributed to every router in the network?
2. Once the topology has been disseminated, how will the shortest paths be computed?

Topology Dissemination

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.

(Every router thus will send a quantity of LSPs equal to the number of neighbors it has.)

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.

What do you think are some of the network conditions under which the strategy just described might fail? Jot down a few on a piece of paper. Choose the one which you think is the most serious before going on to the next page.