If you've stumbled on this post, chances are that you might already be familiar with OSPF and/or IS-IS as the two most common link state routing protocols in use today. Unlike traditional distance-vector routing protocols, routers running link state routing protocols populate a link state database of the entire topology which they use to make routing decisions. It begs the question though, what even is a link state?

Defining link state

Despite all the documentation and content I've read on OSPF and IS-IS, I can't recall ever reading a definition of what a link state actually is.

Links as interfaces

The closest thing to a definition I've found comes from RFC 2328, on defining an OSPFv2 interface as:

The connection between a router and one of its attached
networks.  An interface has state information associated
with it, which is obtained from the underlying lower level
protocols and the routing protocol itself.  An interface to
a network has associated with it a single IP address and
mask (unless the network is an unnumbered point-to-point
network).  An interface is sometimes also referred to as a

Simply put, an interface or link in this context represents a router's connection to one of its attached networks. It's not referring to a physical interface or cable between routers, but a more abstract representation of the connection between a router and an attached network. It could be a physical or logical interface.

As a more concrete example, a logical loop-back interface has no physical link or cable connecting the router to the network associated the loop-back interface. However, from the context of a routing protocol, the network is still considered directly connected. That connection between the router and the attached network, would be the interface or link.

Links as graph edges

While I haven't found any information that directly supports this idea, the link in link state might also have its roots in graph theory. link state routing protocols use Dijkstra's algorithm to determine the shortest path to each destination in a network. In the mere 20 minutes it took Dijkstra to develop the algorithm, his intention wasn't to solve future computer networking problems (which in 1956 hadn't existed yet). His goal was to solve graph theory's shortest path problem to demonstrate the capabilities of a newly designed computer.

In graph theory, a graph is a structure of vertices which are connected by edges. A visual diagram of a graph looks very much like a network topology diagram. In fact, the term topology comes from the branch of mathematics by the same name. It shouldn't be surprising then that graphs are also called networks, vertices are also called nodes, and edges are also called links.

With the context of links referring to the edges in a graph, we can again see how a link again means a connection between a router and a network it's attached to. Consider this very simplified example of a network topology represented as a graph.

Diagram of 4 routers interconnected with 4 networks

Graphs can also be represented in tabular form (i.e. as a database). Here's the same graph represented as an adjacency list.

Node Links
R4, R1 R2, R3 R3, R4 R4, R2

Of course, things are always more complicated in practice. If we look at the individual OSPF Type 1 LSA output below, you can see that the links advertised from router have Link IDs that mean different things depending on the type of network they are connected to. Nevertheless, the concepts are the same. Each router uses this information to create a graph which it can then run the SPF algorithm against to find the best paths to every network.

R1#show ip ospf database router 

  LS age: 572
  Options: (No TOS-capability, DC)
  LS Type: Router Links
  Link State ID:
  Advertising Router:
  LS Seq Number: 80000007
  Checksum: 0xB603
  Length: 60
  Number of Links: 3

    Link connected to: a Stub Network
     (Link ID) Network/subnet number:
     (Link Data) Network Mask:
      Number of TOS metrics: 0
       TOS 0 Metrics: 1

    Link connected to: a Transit Network
     (Link ID) Designated Router address:
     (Link Data) Router Interface address:
      Number of TOS metrics: 0
       TOS 0 Metrics: 1

    Link connected to: a Stub Network
     (Link ID) Network/subnet number:
     (Link Data) Network Mask:
      Number of TOS metrics: 0
       TOS 0 Metrics: 1


A link state is a representation of connections between a router and the network it's attached to. In that context, a link isn't a physical or logical interface, but rather a conceptual interface between a router and a network. In Graph theory, links are the lines drawn between two nodes. So if we imagine the two nodes as a router and a connected network, a link would be a line drawn between them.

- Brian Brookman


comments powered by Disqus