This blog post describes the process of building a simple network topology using the information derived from the “show ip ospf database” command. This is an interesting exercise to understand how to read the information contained in the different LSA types and how they are linked together like a puzzle.

We will begin the process using a sample topology that consists of three routers configured using single area OSPFv2. Therefore, we will review only Type-1 and Type-2 LSAs. In a later blog post, I will repeat the same exercise but using IPv6 and OSPFv3.

The goal of this exercise is to reconstruct the same topology using only the information from the Link State Database (LSDB). Let’s start by examining the output of the “show ip ospf database router self-originate” command in router R1:

The previous command shows the detailed information about the Router LSA (Type-1 LSA) originated from R1. From the previous output, I want to highlight the following information:

  • Link State ID: 1.1.1.1
  • Advertising Router: 1.1.1.1
  • Number of links: 5

The Link State ID identifies a node in the OSPF graph. In a Type-1 LSA, the Link State ID value is the Router ID (RID) of the advertising router. The Link State ID is the key used to search in the LSDB in order to link the different LSAs together. The final OSPF graph is used by the routers to calculate the shortest path using the Shortest Path First (SPF) algorithm (Dijkstra algorithm).

The output shows a total number of 5 links in R1 instead of 3. This is due to the way that point-to-point links are described in OSPFv2. When addressing information is assigned to the interfaces in a point-to-point link, it is modeled as if it were a stub network attached to the router. This extra node is used in SPF calculations only when the traffic goes to the network assigned to the point-to-point link (for example, if the destination is one of the serial interfaces). For simplicity, we will ignore those two extra stub networks associated with the serial links on R1 and consider only the point-to-point links and the real stub network where PC1 is attached.

The first connection described in the output of the previous command corresponds to the point-to-point connection between R1 and R3:

It can be read as node 1.1.1.1 is connected to node 3.3.3.3 through a link that has an associated IP of 10.0.13.1 and a cost of 64. The Link ID field points to the Link State ID of the Router LSA generated by R3. This relationship between R1 and R3 can be represented as follows:

The second connection corresponds to the additional stub network associated with the addressing information assigned to the previous serial link between R1 and R3, so we will ignore it when building the topology.

The third connection corresponds to the point-to-point connection between R1 and R2:

This information allows us to add another node to the previous graph:

The next connection is the other extra stub network associated with the serial link between R1 and R2, so we will skip it. The final connection corresponds to the real stub network associated with the network segment where PC1 is attached:

In this case, the Link State ID corresponds to the subnet ID (192.168.10.0) and the Link Data field carry the subnet mask information (255.255.255.0). The cost to reach this network is also specify. With that information, we can add another piece to the graph:

At this point, we have two choices to continue the reconstruction of the topology. The R1’s Router LSA is connected to the R2 and R3’s Router LSAs through the Link ID fields. For example, the serial link between R1 and R2 has a Link ID of 2.2.2.2. This value can be used by R1 as a key to look for the R2’s Router LSA in the LSDB:

The first connection described in the R2’s Router LSA is the serial connection to R1:

The Link ID 1.1.1.1 points to the R1’s Router LSA, which allows us to place the two pieces of the puzzle together. Notices that the Link Data field corresponds to the IP address of R2’s serial interface. This IP can be used by R1 as the next-hop address when computing routes through R2. The interface cost value of 64 is used by R2 when computing routes using its serial interface as the outgoing interface.

Before examining the third connection described in the R2’s Router LSA, let’s have a look at the output associated with R3’s Router LSA:

In this LSA, the first connection corresponds to the serial connection between R1 and R3. At this point, we can add the costs and IPs associated with the point-to-point links connecting R1 to R2 and R3:

In order to complete the final topology, let’s analyze the link to the transit network described in the Router LSAs of R2 and R3. The transit network corresponds to the Ethernet segment that connects routers R2 and R3 through the switch SW1. Ethernet networks are modeled in OSPF by adding a pseudonode to the topology. In multiaccess networks like Ethernet, more than two routers can be attached to the same network segment. In order to simplify the complexity and reduce the size of the LSDB, instead of creating a single connection between every possible pair of routers in the LSDB, an extra node is created (the pseudonode) and it is used as a vertex in the graph to which all the other routers connect.

The pseudonode is described by the Type-2 LSA created by the Designated Router (DR), which is R3 in this topology:

The Link State ID of the Type-2 LSA corresponds to the IP address of the DR (192.168.20.2). The network mask is also specified in the LSA, which can be used to calculate the network address using the IP of the DR. Finally, the Type-2 LSA stores a list of RIDs associated with all the routers connected to the transit network. This RIDs can be used as keys to search in the LSDB for the corresponding Router LSAs, in order to find all the possible paths in the graph.

We can conclude the process of building the topology by adding the information provided by the Type-2 LSA, resulting in the following diagram:

In the next post, I will repeat the same process but using IPv6 and OPSFv3 to discuss the differences.