The information available to a distance vector router has been compared to the information available from
a road sign. Link state routing protocols are like a road map. A link state router cannot be fooled as easily
into making bad routing decisions, because it has a complete picture of the network. The reason is that
unlike the routing-by-rumor approach of distance vector, link state routers have firsthand information
from all their peer[7] routers. Each router originates information about itself, its directly connected links,
and the state of those links (hence the name). This information is passed around from router to router,
each router making a copy of it, but never changing it. The ultimate objective is that every router has
identical information about the internetwork, and each router will independently calculate its own best
paths.
[7] That is, all routers speaking the same routing protocol.
Link state protocols, sometimes called shortest path first or distributed database protocols, are built
around a well-known algorithm from graph theory, E. W. Dijkstra'a shortest path algorithm. Examples of
link state routing protocols are:
Open Shortest Path First (OSPF) for IP
The ISO's Intermediate System to Intermediate System (IS-IS) for CLNS and IP
DEC's DNA Phase V
Novell's NetWare Link Services Protocol (NLSP)
Although link state protocols are rightly considered more complex than distance vector protocols, the
basic functionality is not complex at all:
NOTE
Link state advertisement
1. Each router establishes a relationship—an adjacency—with each of its neighbors.
2. Each router sends link state advertisements (LSAs), sometimes called link state packets (LSPs), to
each neighbor. One LSA is generated for each of the router's links, identifying the link, the state of
the link, the metric cost of the router's interface to the link, and any neighbors that may be
connected to the link. Each neighbor receiving an advertisement in turn forwards (floods) the
advertisement to its own neighbors.
3. Each router stores a copy of all the LSAs it has seen in a database. If all works well, the databases
in all routers should be identical.
4. The completed topological database, also called the link state database, describes a graph of the
internetwork. Using the Dijkstra algorithm, each router calculates the shortest path to each
network and enters this information into the route table.