OSPF

Introduction


When boiled down to its basic parts, OSPF’s LSDB is much more simple than it appears. In reality, the LSDB is merely a listing of nodes and a description of the relationship between those nodes described using LSAs. Type-1 Router LSAs describe the router nodes in the network and their relationship to other nodes. Type-2 Network LSAs describe segments on the network where multiple routers share a relationship. Type-3 Summary LSAs are used to provide routing to prefixes between areas. Type-4 ASBR Summary LSAs inject topology information into an area about an ASBR from another area that is flooding Type-5 External LSAs into the domain.

 

Each LSA type acts as a single piece of the puzzle that, when put together, creates a graph of the full network topology. OSPF uses this graph to run SPF and calculate an SPT for each router in the topology.

 

This blog will attempt to explain these concepts as simply as possible. As such, some examples have been contrived or overly simplified in order to convey the overall idea.


LSDB as a Graph


To understand the LSDB better, it helps to think of it as a graph. Graphs are mathematical structures made up of a set of objects that are in some way related to each other. Each object is called a vertex or node. A relationship between two nodes is called an edge. They are usually diagrammatically depicted as follows:

1.png

In the above we have nodes A through E. The relationship between nodes A and B, A and C, and so on forms an edge. It is possible by following the edges between nodes to plot a path between any two nodes without passing through any node twice. For instance, to reach Node D from Node A, one could follow the A-B-C-D path. Notice there are several other paths through which A could reach D. The challenge is deciding on a criteria that makes one path preferred over another.

 

OSPF uses Dijkstra’s shortest path first algorithm to find the shortest paths between points on the graph. In order for the algorithm to work, there needs to be a weight or cost assigned to each edge on the graph as follows:

2.png

The SPF algorithm adds up the total weight of each available path, the path with the lowest total weight becomes the best path. In the example above, the path A-C-D is considered the best path because the collective weights of the edges is lowest among all other available paths.   

 

Networks can easily be expressed in the same terms. Each network segment or networking device is a node. The relationship between those nodes form an edge, or link. These links have different characteristics, such as bandwidth, delay, monetary cost, or reliability. These characteristics can be used as weights on the graph. Routers describe these relationships using Link State Advertisements (LSAs), creating a different type of LSA for each type of relationship.

 

The Link State Database is a collection of these LSAs, containing a list of all of the nodes in the network and the relationship between those nodes. The SPF algorithm is run against the LSDB to find the shortest path between related nodes to reach all nodes in the topology.

 

When represented in such a way, it is a simple task to use this graph as input for the SPF algorithm to determine the shortest paths. Each router does this by first setting itself as the root of a tree and finding the shortest paths from it to every other node in the network. The result is a Shortest Path Tree (SPT) that spans from the calculating router to every other node.


Link State Advertisements


As stated earlier, LSAs are the building blocks of the LSDB each describing a relationship and therefore a different piece of the overall network topology. There are several different types of LSAs. This blog will explain LSA Types 1 through 5 as they are the most common LSA types encountered when first learning about OSPF.

 

All LSAs regardless of type have an LSA header, which identifies important pieces of information about the LSA. For example, the Type-1 Router LSA Header is as follows:

 

LS age: 36

Options: (No TOS-capability, DC)

LS Type: Router Links

Link State ID: 1.1.1.1

Advertising Router: 1.1.1.1

LS Seq Number: 80000004

Checksum: 0x2B0B


From top to bottom:

 

  1. The LSA’s age in seconds. Once an LSA reaches Max Age or 3600s, it is removed from the database.
  2. LSA Options that control how OSPF routers treat the LSA
  3. The LSA Type. In this case it is a Type-1 Router LSA
  4. An Identifier for the LSA called the Link State ID. In this case, 1.1.1.1
  5. The router that originally advertised the LSA. Only this router can modify or prematurely remove the LSA from the LSDB. For this LSA, 1.1.1.1 is the advertising router and is the only router that can modify or prematurely age out the LSA.
  6. Sequence number which is used to identify newer copies of an LSA
  7. Checksum that is used to detect corruption in the LSA.

 

This header can also be referenced in the show ip ospf database output. The output however refers to the Link State ID as Link ID which is inaccurate. A Link ID identifies a single link whereas a Link State ID identifies an LSA that may contain many links.


R1#sh ip ospf database

          OSPF Router with ID (1.1.1.1) (Process ID 1)

              Router Link States (Area 0)

Link ID        ADV Router     Age        Seq#      Checksum Link count

1.1.1.1        1.1.1.1        858        0x80000009 0x00949E 4


A key topic for understanding is that the Link State ID (or Link ID from the show ip ospf database output) is not an IP address. In the above, the presence of 1.1.1.1 as a Link ID does not mean there is network connectivity to ip address 1.1.1.1/32. Instead, it signals that there is a router node called 1.1.1.1 on the graph in the LSDB.

 

The next sections describe how LSAs are used to describe the relationships between nodes in the LSDB graph. To better understand the function of each LSA, a reference topology will be built piece-by-piece as new LSAs are introduced.The first LSA discussed is the Router LSA.

Type-1 Router LSAs


The most important LSA is the Router LSA or Type-1 LSA. It is the LSA to which all other LSAs attach. This LSA describes a router node itself and all of its relationships or link adjacencies to other nodes. It is originated by every router in the topology and flooded to all routers in a single area. OSPF identifies four types of link adjacencies using Type-1 Router LSAs:

 

  1. Stub Network
  2. Point-to-Point links
  3. Link to a multiaccess network
  4. Virtual Links

 

NOTE: There is a distinction between an “interface” and a “link”. An interface describes a physical or logical interface on the router (i.e. loopback interfaces, ethernet ports). A link describes a relationship on the graph between two nodes. Virtual links are good examples of this concept. A virtual link describes a logical connection to another OSPF router, however, the physical interfaces used to make up the path may change dynamically depending on network conditions.


Let’s examine how the fields in the Type-1 Router LSAs are populated to describe R1’s adjacencies from the reference diagram.

3.png

R1 has three links in this network: one to R2 , one to another network segment, and one on the network segment 192.168.1.0/24. R1’s job is now to describe these links in a Type-1 Router LSA and advertise them to R2. R1 will supply three pieces of information to R2 and any other router in the OSPF domain:

 

  1. An ID to identify itself as a node on the graph
  2. A listing of its link adjacencies
  3. The relationship to other nodes connected to those links (if applicable)

 

In order to identify a node on the graph, OSPF uses a 32-bit number as the Node Identifier in the LSDB, called the router ID (RID). By default, OSPF chooses the highest IP address on an up loopback interface first and then the highest IP address on any up interface second as its RID. The RID can also be statically defined with the router-id command in OSPF configuration mode.

 

When R1 creates its Type-1 Router LSA, it will use its RID (1.1.1.1) as the Link State ID and advertising router field of the LSA header as follows:

 

R1#show ip ospf database router self-originate

          OSPF Router with ID (1.1.1.1) (Process ID 1)

              Router Link States (Area 0)

LS age: 835

Options: (No TOS-capability, DC)

LS Type: Router Links

Link State ID: 1.1.1.1

Advertising Router: 1.1.1.1

 

The next section details on one of the four types of link adjacencies carried in the Type-1 Router LSA, Stub Networks.

Describing Stub Networks


R1 is the only router on the network segment 192.168.1.0/24 in the above topology. Such links are classified as stub networks by OSPF because the segment does not include another OSPF router. Since there is only one router connected, traffic will be routed to or from the segment, but never through it. In other words, the segment 192.168.1.0/24 will not be used as a transit segment.

 

R1 models this link in its Type-1 Router LSA as if it were a link to another node using the network prefix as the Link ID and the subnet mask as the Link Data. In this way, the network appears as a node directly connected to R1. Out of all of the link adjacencies described by a Type-1 Router LSA, the stub network link description is the only one that carries network layer addressing information. The following is R1’s link description for the stub network 192.168.1.0/24.

 

R1#show ip ospf database router self-originate

          OSPF Router with ID (1.1.1.1) (Process ID 1)

              Router Link States (Area 0)

LS age: 835

Options: (No TOS-capability, DC)

LS Type: Router Links

Link State ID: 1.1.1.1

Advertising Router: 1.1.1.1

 

  Link connected to: a Stub Network

    (Link ID) Network/subnet number: 192.168.1.0

    (Link Data) Network Mask: 255.255.255.0

    Number of MTID metrics: 0

        TOS 0 Metrics: 1

 

This concludes R1’s description of its stub network. Next, R1 needs to model the link between itself and R2.

Describing Point-to-Point Links


In OSPF, a point-to-point link adjacency is a link that connects to only one other OSPF router. In the above, R1’s 12.1.1.1 link only connects to R2 and is expressed as a point-to-point link in OSPF. OSPF exhibits what may seem to be odd behavior when it comes to point-to-point links. When modeling a point-to-point link, OSPF will assume the link is unnumbered.

 

An unnumbered point-to-point link, is a point-to-point link to which no network layer addressing information is applied. Network layer addressing information is not needed on a point-to-point link because there are only two devices on the link (i.e. between R1 and R2 in the above). Traffic for such links will always be routed through the link and never destined to the link. Nothing is gained from assigning an address to each interface in this scenario.

 

However, on Cisco IOS an interface cannot forward IP traffic unless an IP address is assigned to it. For unnumbered point-to-point links, the ip unnumbered command allows a point-to-point interface to borrow an IP address from another interface on the router. This enables the IP protocol stack to run on the interface, allowing the forwarding of control and transit IP traffic over the point-to-point interface.

 

On R1, OSPF models this point-to-point link as follows:

 

Link connected to: another Router (point-to-point)

    (Link ID) Neighboring Router ID: 2.2.2.2

    (Link Data) Router Interface address: 12.1.1.1

    Number of MTID metrics: 0

        TOS 0 Metrics: 10

 

The point-to-point link describes the direct link to R2. The Link ID is set to the RID of the neighboring router R2 (2.2.2.2). The Link ID provides a key in the LSDB to R2’s Type-1 Router LSA. The Link Data is the IP address of the physical interface. The Link Data is used as an identifier and not as addressing information. If the interface is configured with ip unnumbered command, the Link Data instead will be set to the SNMP MIB-II interface address. The link description above can be read as:

 

“Node 1.1.1.1 has a link called 12.1.1.1 that is connected to node 2.2.2.2”.

 

NOTE: Some versions of Cisco IOS will set the Link Data for ip unnumbered interfaces to a random internal value. The engineer must configure the interface-id snmp-if-index command under OSPF configuration mode to enable the use of the SNMP interface ID for Link Data in the Type-1 Router LSA.

 

Virtual Links, links between two nodes on the graph used to connect to the backbone, are expressed as unnumbered point-to-point links as well. Because virtual-link adjacencies are also described by the Type-1 Router LSA in the same manner, they are not going to be expounded upon in this blog.

 

If addressing information is assigned to to the point-to-point link, OSPF will model this separately from the point-to-point link description as if it were a stub network attached to the router. The link between R1 and R2 has been assigned the 12.1.1.0/24 subnet. OSPF attaches this subnet off R1 using a second stub link description:

 

  Link connected to: a Stub Network

  (Link ID) Network/subnet number: 12.1.1.0

    (Link Data) Network Mask: 255.255.255.0

    Number of MTID metrics: 0

        TOS 0 Metrics: 1

 

With this link description, R1 is identifying that it is also connected to a network node 12.1.1.0/24.

The OSPF Lie


It may appear as if OSPF is lying when it advertises a stub network along with the point-to-point link, especially given our previous understanding of stub networks. A stub network is not supposed to connect to another router and it is not supposed to be used for transit traffic. However, in the point-to-point link to R2 above, this is not true. It appears as if transit traffic will cross the stub network 12.1.1.0/24.

 

In order to reconcile this inconsistency, one must understand that logically R1 considers R2 and the stub network 12.1.1.0/24 as two different nodes in the network. This distinction is key. Each link to these nodes is used as independent relationships in the graph when computing shortest paths.

 

When R1 describes a point-to-point link, it first models the link to node R2 as described in the section above. Then it describes the link to the stub network node 12.1.1.0/24, which is assigned to the point-to-point link. Each link is considered separately when performing SPF computations. From a graphical point of view, this makes sense. The graphical relationship between R1, R2, and the stub network node is as follows:

4.png

From OSPF’s perspective, these relationships are independent. There is a point-to-point relationship between R1 and R2 and both routers have a network node 12.1.1.0/24 attached. The SPF calculation behaves in the following way regarding these two descriptions:

 

  • When calculating the path between Nodes 1.1.1.1. and 2.2.2.2, OSPF uses the point-to-point link description.
  • When calculating the path to the 12.1.1.0/24 network, OSPF uses the stub network link description.

 

Understanding this, it is clear OSPF has not lied. It is not using the 12.1.1.0/24 network node to transit traffic. It is using the point-to-point link description. Only traffic destined to 12.1.1.0/24 will be routed using the stub network link description. Traffic destined to other remote network nodes will be routed across the point-to-point link which has no addressing information attached to it.

 

Addressing information for the point-to-point link does not have to be modeled in the Type-1 Router LSA. Advertising this information facilitates routing directly to those interfaces. If direct connectivity to the interfaces is not required, this addressing information can be suppressed using the ip ospf prefix-suppression command in interface configuration mode. With this configuration, the addressing information for the point-to-point link (the 12.1.1.0/24 subnet) will not be modeled in the Type-1 Router LSA, eliminating it from the LSDB.

 

The basics of Type-1 Router LSAs as far as stub and point-to-point links are concerned have been covered. To explain the next type of link described by Type-1 Router LSAs, we need to add a new section to the topology and introduce a new LSA type.

Type-2 Network LSAs


The below shows an example of a multiaccess network. R1 has an interface on a multiaccess network shared with R3 and R4. Multiaccess networks allow multiple devices to connect to the same network segment. This is achieved by transparently bridging traffic between each device connected to the segment. For OSPF, this transparent bridging creates a situation where a single OSPF router can have several OSPF routers connected to one link.

 

5.png

How would R1 model the relationship with R3 and R4 on the multiaccess segment using a Type-1 Router LSA alone? A point-to-point link description only describes a link to a single router. For this reason, R1 can not describe its relationship to both R3 and R4 in a single point-to-point link description. R1 would have to use multiple point-to-point link descriptions to describe these relationships. R3 and R4 would have to do the same, leading to the following graphical topology:


6.png

If the graph above were described using words, the following would be stated:

 

“Node 1.1.1.1 is connected to Node 3.3.3.3 and Node 4.4.4.4. Node 3.3.3.3 is connected to Node 1.1.1.1 and Node 4.4.4.4. Node 4.4.4.4 is connected to Node 1.1.1.1 and Node 3.3.3.3.”

 

Stating the relationships in this way is cumbersome, not only when spoken but also in the LSDB. It takes up a lot of space. In OSPF terms, this “space” translates to the overall size of the LSDB. A Large LSDB increases how long it takes to calculate shortest paths during an SPF run and consumes more router memory.

 

Another way of expressing this information is to create a node that represents the multiaccess segment and have each router on the segment advertise their relationship to the new node. The result is the following graphical representation:

7.png

If the graph above were described using words, the following would be stated:

 

“Nodes 1.1.1.1, 3.3.3.3, and 4.4.4.4 are all connected to Transit Network Node 134.1.1.4.”

 

This is a simpler statement that takes up less space. OSPF assumes this network node provides connectivity to the routers to which it is attached, treating the network node as if it were another OSPF router on the graph. By solving the path to the network node, OSPF also solves the path to each router connected to the network node. This node is typically referred to as a pseudo node, because it does not physically exist in the network. It is a logical construct to help define the relationship between nodes on a multiaccess segment.

 

One router from the segment, called the Designated Router, is elected to create the pseudo node using a Type-2 Network LSA. In the example topology, R4 is acting as the DR on the segment and generates the Type-2 Network LSA with the following information:

 

  1. R4 uses its interface IP address on the segment as the Link State ID of the pseudo node in the Type-2 Network LSA header.
  2. The Type-2 Network LSA generated by R4 contains a list of all router nodes attached to the pseudo node.

 

The following is the Type-2 Network LSA generated by R4 identifying the pseudo node 134.1.1.4 and its attached nodes 4.4.4.4, 1.1.1.1, and 3.3.3.3.

 

R1# show ip ospf database network

--- omitted ---

Options: (No TOS-capability, DC)

LS Type: Network Links

Link State ID: 134.1.1.4 (address of Designated Router)

Advertising Router: 4.4.4.4

LS Seq Number: 80000001

Checksum: 0x9CDC

Length: 36

Network Mask: /24

    Attached Router: 4.4.4.4

      Attached Router: 1.1.1.1

      Attached Router: 3.3.3.3

 

R1, as a router connected to the segment, uses a transit network link description in its Type-1 Router LSA to describe its link to the pseudo node. The transit link description has the Link ID of 134.1.1.4, which is both the DR’s interface address on the segment and the Link State ID of the pseudo node. Next, the Link data for the transit link description is set to R1’s interface address on the segment.

 

R1# show ip ospf database router self-originate

--- omitted ---

Options: (No TOS-capability, DC)

LS Type: Router Links

Link State ID: 1.1.1.1

Advertising Router: 1.1.1.1

--- omitted ---

  Link connected to: a Transit Network

    (Link ID) Designated Router address: 134.1.1.4

    (Link Data) Router Interface address: 134.1.1.1

    Number of MTID metrics: 0

      TOS 0 Metrics: 10

 

Compared to a point-to-point link description, the Link ID for the transit link description is a pseudo node identifier, while in the point-to-point link description, the Link ID is the RID of a neighboring router.

 

The transit network link description in R1’s Type-1 Router LSA does not include network layer information. In order to derive network layer information, the Type-2 Network LSA contains the netmask for the segment:

 

R1# show ip ospf database network

--- omitted ---

Options: (No TOS-capability, DC)

LS Type: Network Links

Link State ID: 134.1.1.4 (address of Designated Router)

Advertising Router: 4.4.4.4

LS Seq Number: 80000001

Checksum: 0x9CDC

Length: 36

Network Mask: /24

 

Because the Link State ID of the Type-2 Network LSA is the address of the DR, other routers in the topology can find the network address by applying the mask to the Link State ID of the Type-2 Network LSA. In the above, the network address of the network node is 134.1.1.0/24.

 

The combination of these two LSAs spells out R1’s link as follows

 

“Node 1.1.1.1 has a transit link to pseudo node 134.1.1.4. Pseudo node 134.1.1.4 has netmask /24 and connects nodes 1.1.1.1, 3.3.3.3 and 4.4.4.4.”

 

At this point, Type-1 Router and Type-2 Network LSAs have been fully covered. The entire network topology can be modeled with these two LSAs alone. Doing so, however, can cause problems as the network grows larger. To deal with this, OSPF uses the concept of Areas.

LSDB and Areas


Left as it is, the LSDB will continue to grow in size as the network grows. Eventually, it can become so large that it increases the time it takes to run the SPF algorithm and the memory demand on the router. Another negative side effect of a large LSDB is that routing updates affect all routers and force a full recalculation of SPF. If a link goes down in one section of the network, the entire network will have to adjust their LSDBs and recalculate the shortest paths.

 

OSPF avoids these issues by allowing the network engineer to segment the network into Areas. Most of the computational overhead of SPF is spent calculating the shortest paths between Type-1 Router LSAs and Type-2 Network LSAs as they contain the most dense topology information. When a topology is split into different areas, these LSAs are not permitted across area boundaries, decreasing the size of the LSDB. Instead, this topology information is hidden by routers that sit between each area, termed Area Border Routers (ABRs).

 

With such an implementation, all OSPF routers in the topology will no longer have a synchronized LSDB, and therefore cannot arrive at the same outcome when running the SPF algorithm. Only routers in the same area will have synchronized LSDBs and can agree on the internal topology of the area. Therefore, full SPF computations are run separately within each area and not over the entire topology. Topology changes in one area will not cause a full SPF calculation in other areas.

 

In the topology below, routers in Area 1 will maintain a synchronized LSDB separate of routers in Area 0. SPF is run in Area 1 to determine the shortest paths within that area. A separate SPF calculation is performed in Area 0 to determine the shortest paths within that area.

8.png

NOTE: ABRs in the topology contain a separate LSDB for each area to which they are attached and will run SPF for each LSDB. In the above, ABR1 performs an SPF calculation for Area 1 and  a separate SPF calculation for Area 0.

 

ABRs rely on the Type-3 Summary LSA to advertise condensed topology information between areas.

Type-3 Summary LSAs


Instead of describing the details of what nodes exist in an area and how they are interconnected, Type-3 Summary LSAs only advertise prefixes. In a multi-area OSPF domain, there exists two different kinds of prefixes:

  • intra-area: prefixes from within a single area
  • inter-area: prefixes from outside a single area

 

An ABR will generate a Type-3 Summary LSA for all intra-area and inter-area prefixes from its routing table and flood them into the other areas to which it is attached. From the topology above, ABR1 would advertise all intra-area and inter-area prefixes from Area 1 to Area 0. Likewise it will advertise all intra-area and inter-area prefixes from Area 0 to Area 1. The same happens between Area 0 and Area 2.

 

In order to make the topology more resistant to loops, OSPF enforces a two-layer hierarchy. All areas must have a connection to the top layer of the hierarchy which is Area 0, also known as the backbone. Type-3 Summary LSAs are exchanged through the backbone down to the lower layer of the hierarchy where all other areas exist. This creates a hub-and-spoke topology like the below:

9.png

This organization also changes the ABR’s Type-3 Summary LSA flooding algorithm as follows:

 

  • Type-3 LSAs are generated for intra-area and inter-area prefixes from the backbone area and flooded to non-backbone areas.
  • Type-3 LSAs are generated only for intra-area routes in non-backbone areas and flooded into the backbone area.
  • An ABR only uses Type-3 LSAs from the Backbone area in the SPF calculation

 

For example, in the above, ABR1 will generate a Type-3 Summary LSA for all intra-area prefixes in Area 1 and flood them into Area 0. ABR1 will also generate a Type-3 Summary LSA for intra-area and inter-area prefixes from Area 0 and flood them into Area 1.

 

NOTE: The above algorithm implies that an ABR can only generate Type-3 Summary LSAs if it is connected to Area 0. This may differ among vendor implementations, however, this is how ABRs function in Cisco IOS.

 

To demonstrate these concepts, the reference topology is further built upon to create a multiarea OSPF domain.

 

10.png

The topology shows R1, R2, R3, and R4 belong to the backbone Area 0. R2, R3, and R4 are ABRs with links to other areas. R2 has a link in Area 256, R3 has a link in Area 37, and R4 has a link in area 489.

 

Looking at the LSDB on R2 for router LSAs yields this result:

 

R2#show ip ospf database

          OSPF Router with ID (2.2.2.2) (Process ID 1)

              Router Link States (Area 0)

Link ID        ADV Router      Age        Seq#      Checksum Link count

1.1.1.1        1.1.1.1        1576        0x80000004 0x0035FF 4

2.2.2.2        2.2.2.2        1329        0x80000003 0x006C6F 2

3.3.3.3        3.3.3.3        1359        0x80000003 0x009A5C 1

4.4.4.4        4.4.4.4        1255        0x80000004 0x00608A 1

            --- some output has been omitted ---

            Router Link States (Area 256)

Link ID        ADV Router      Age        Seq#      Checksum Link count

2.2.2.2        2.2.2.2        1319        0x80000002 0x007E34 2

5.5.5.5        5.5.5.5        1195        0x80000003 0x005688 4

6.6.6.6        6.6.6.6        743        0x80000004 0x0018B4 3

            --- some output has been omitted ---


Notice, R2 has separate Type-1 Router LSAs for the backbone area and Area 256. Also notice, the nodes 5.5.5.5 (R5) and 6.6.6.6 (R6) that belong to Area 256 are not listed in the Type-1 Router LSAs in Area 0. Likewise, nodes 1.1.1.1 (R1), 3.3.3.3 (R3), or 4.4.4.4 (R4) that belong to Area 0 are not listed in Type-1 Router LSAs for Area 256. The details of each area are kept hidden. This is evidenced by examining the router LSAs on R1 and R6:


R1#show ip ospf database

          OSPF Router with ID (1.1.1.1) (Process ID 1)

              Router Link States (Area 0)

Link ID        ADV Router      Age        Seq#      Checksum Link count

1.1.1.1        1.1.1.1        12          0x80000006 0x003102 4

2.2.2.2        2.2.2.2        53          0x80000004 0x006A70 2

3.3.3.3        3.3.3.3        14          0x80000005 0x00965E 1

4.4.4.4        4.4.4.4        13          0x80000006 0x005C8C 1

 

R6#sh ip ospf database

          OSPF Router with ID (6.6.6.6) (Process ID 1)

              Router Link States (Area 256)

Link ID        ADV Router      Age        Seq#      Checksum Link count

2.2.2.2        2.2.2.2        582        0x80000002 0x007E34 2

5.5.5.5        5.5.5.5        457        0x80000003 0x005688 4

6.6.6.6        6.6.6.6        3          0x80000004 0x0018B4 3

 

R1, R6, R7, R8, and R9 only have interfaces in their respective areas, making them internal routers. As such, they only have detailed information about the topology within their area. R2, R3, and R4, as ABRs, have interfaces in multiple areas. They have detailed information about the topology of all areas to which they are connected.


To provide connectivity between areas, R2, as an ABR, performs the following:

 

  1. Looks in its RIB for all OSPF intra-area routes from Area 256.
  2. Advertises them as Type-3 Summary LSAs into the backbone Area 0.
  3. Looks into its RIB for all intra-area and inter-area prefixes from the backbone Area 0.
  4. Floods these prefixes into its non-backbone Area 256 as Type-3 Summary LSAs, excluding those routes that belong to Area 256.

 

Here is an example of R2’s routing table for the prefix 192.168.5.0/24:

 

R2#show ip route ospf | inc 192.168.5.0

O    192.168.5.0/24 [110/11] via 25.1.1.5, 00:11:53, Ethernet0/2

 

Notice it has an “O” next to it. This means it is a route to an intra-area prefix. R2 will take this prefix and advertise it in the following Type-3 Summary LSA into Area 0:

 

R2#show ip ospf database summary 192.168.5.0

          OSPF Router with ID (2.2.2.2) (Process ID 1)

              Summary Net Link States (Area 0)

LS age: 830

Options: (No TOS-capability, DC, Upward)

LS Type: Summary Links(Network)

Link State ID: 192.168.5.0 (summary Network Number)

Advertising Router: 2.2.2.2

LS Seq Number: 80000001

Checksum: 0xD2E8

Length: 28

Network Mask: /24

      MTID: 0        Metric: 11

 

R2 sets the Link State ID to the network number of the summary address and inserts its own RID as the advertising router. The netmask and metric are all encoded in this LSA as well. Finally, we can see this LSA has been flooded in Area 0.

 

Routers in Area 0 will perform the following:

  • Add this prefix to their routing tables
  • Solve the shortest path to the advertising router 2.2.2.2
  • Add the metric to their final route computation

 

This process results in the following inter-area prefix, denoted by “O IA” in the routing table:

 

R1#show ip route ospf | i 192.168.5.0

O IA  192.168.5.0/24 [110/21] via 12.1.1.2, 01:06:23, Ethernet0/1

 

Through this process, OSPF behaves no differently than a Distance Vector protocol. It simply advertises the network prefix, a direction (towards 2.2.2.2), and a cost (in this case Metric: 11). Doing so, full SPF calculations are not required when prefixes are added or removed between areas. The ABRs simply age out the Type-3 Summary LSAs and all other routers remove them from their respective LSDBs.

Dealing with External Information


External routing information is any information that has been injected into the OSPF process with the redistribute command. This information could originate from a different routing protocol or a different OSPF process. The routers configured to inject this external information into the OSPF domain are called the Autonomous System Border Router or ASBR and use Type-5 external LSAs to perform the flooding.

 

NOTE: Type-7 LSAs can also be used to inject external information into a not-so-stubby area. However the details behind this are outside the scope of this blog.

Type-5 External LSAs

 

In the below, the reference topology has been extended to include external prefixes. The external prefixes 172.16.56.0/24 and 172.16.65.0/23 are being injected into the OSPF domain by the ASBR R6 in Area 256. R6 generates an individual Type-5 External LSA for both of these prefixes. Type-5 External LSAs have a domain-wide flooding scope and as such do not belong to any specific area. As the Type-5 External LSA is flooded throughout the domain, no other router can modify the contents or regenerate the LSA.

 

11.png

The Type-5 External LSAs generated by R6 below contains three important pieces of information:

 

  • The Link State ID is always set the to the external network being flooded into the OSPF domain
  • The Advertising Router field is set to the RID of the ASBR, which is 6.6.6.6 in this case
  • The Forward Address is set to 0.0.0.0. This value indicates all OSPF routers should solve the path to the advertising router, R6, to reach the external prefix.

 

            Type-5 AS External Link States

LS age: 685

Options: (No TOS-capability, DC, Upward)

LS Type: AS External Link

Link State ID: 172.16.56.0 (External Network Number )

Advertising Router: 6.6.6.6

LS Seq Number: 80000001

Checksum: 0x4350

Length: 36

Network Mask: /24

      Metric Type: 2 (Larger than any link state path)

      MTID: 0

      Metric: 20

      Forward Address: 0.0.0.0

      External Route Tag: 0

 

LS age: 685

Options: (No TOS-capability, DC, Upward)

LS Type: AS External Link

Link State ID: 172.16.65.0 (External Network Number )

Advertising Router: 6.6.6.6

LS Seq Number: 80000001

Checksum: 0xDFAA

Length: 36

Network Mask: /24

      Metric Type: 2 (Larger than any link state path)

      MTID: 0

      Metric: 20

      Forward Address: 0.0.0.0

      External Route Tag: 0

 

The above can be translated as such:

 

“The external networks x.x.x.x can be reached via the node 6.6.6.6.”

 

Internal routers in Area 256, such as R5 or R2, can solve the path to the ASBR because they have the Type-1 Router LSA for the ASBR (6.6.6.6 or R6) in their LSDBs:

 

R5#sh ip ospf database

          OSPF Router with ID (5.5.5.5) (Process ID 1)

              Router Link States (Area 256)

Link ID        ADV Router      Age        Seq#      Checksum Link count

2.2.2.2        2.2.2.2        1527        0x80000002 0x007E34 2

5.5.5.5        5.5.5.5        1526        0x80000003 0x00FB64 5

6.6.6.6        6.6.6.6        1526        0x80000003 0x001AB3 3

 

R6’s Type-1 Router LSA contains sufficient information to determine it has a point-to-point link to node 5.5.5.5 which is R5. R5 will have this information and, as a result, can solve the path to R6 in the topology.

 

R5#show ip ospf database router 6.6.6.6

          OSPF Router with ID (5.5.5.5) (Process ID 1)

              Router Link States (Area 256)

Routing Bit Set on this LSA in topology Base with MTID 0

LS age: 682

Options: (No TOS-capability, DC)

LS Type: Router Links

Link State ID: 6.6.6.6

Advertising Router: 6.6.6.6

LS Seq Number: 80000003

Checksum: 0x1AB3

Length: 60

AS Boundary Router

Number of Links: 3

  [--omitted--]

    Link connected to: another Router (point-to-point)

    (Link ID) Neighboring Router ID: 5.5.5.5

  (Link Data) Router Interface address: 56.1.1.6

    Number of MTID metrics: 0

    TOS 0 Metrics: 10

 

    Link connected to: a Stub Network

    (Link ID) Network/subnet number: 56.1.1.0

    (Link Data) Network Mask: 255.255.255.0

    Number of MTID metrics: 0

    TOS 0 Metrics: 10

 

Note: Here it is clearer that the OSPF RID is just a 32-bit identification of a node, and not an IP address. If the RID of 6.6.6.6 in the advertising field of the Type-5 LSA truly represented an IP address, R5 wouldn’t need to refer to a Type-1 Router LSA to solve reachability to the external prefixes. R5 could just perform a normal destination-based IP lookup for 6.6.6.6 in its routing table. This also stresses the point that just because a router has an LSA for a prefix or node, that does not mean it can reach that particular prefix or node.

 

We understand from above that, within the area the ASBR is located, a Type-1 Router LSA plays an important role in locating the ASBR on R5. However, for routers in other areas, such as R1 in Area 0, there is no entry in the LSDB for node 6.6.6.6:

 

R1#show ip ospf database

        OSPF Router with ID (1.1.1.1) (Process ID 1)

              Router Link States (Area 0)

Link ID        ADV Router      Age        Seq#      Checksum Link count

1.1.1.1        1.1.1.1        1247        0x80000005    0x00290C 4

2.2.2.2        2.2.2.2        1196        0x80000003    0x006C6F 2

3.3.3.3        3.3.3.3        1213        0x80000004    0x00411C 2

4.4.4.4        4.4.4.4        1217        0x80000004    0x006FD8 2

 

This is because topology information is lost between areas in favor of smaller LSDBs. R1 cannot solve the path to this node using a Type-1 Router LSA because it doesn’t have one in its LSDB to begin with. R1 will have to find summary information for another router in Area 0 that has a tree built to node 6.6.6.6.

 

This is where Type-4 ASBR Summary LSAs are added to the mix. Using Type-4 Summary LSAs, routers in a different area than the ASBR can solve the SPT to another router that has sufficient information to build a tree to the ASBR. These routers are the ABRs.

Type-4 ASBR Summary LSAs


Type-4 ASBR Summary LSAs are generated by ABRs and flooded into all of their attached areas. It serves two important purposes for areas in which the ASBR does not exist:

 

  1. Injects topology information about the ASBR back into the LSDBs of other areas
  2. Allows routers in other areas to make the best choice of entry point into the area the ASBR resides.

 

For the first point, Type-4 ASBR Summary LSAs simply alert all routers in other areas which router in their area has sufficient information to reach the ASBR. This allows the routers in other areas to perform an inter-area lookup to solve the path to the ASBR.

 

A case for the second point is made when there are multiple ABRs in an area with differing costs to reach the ASBR. When generating the Type-4 ASBR Summary LSA, the ABR lists its own cost to reach the ASBR. Without the Type-4 ASBR Summary LSA, the routers in other areas would not know which ABR to use as the best entry point into the area containing the ASBR.

 

In the reference topology, when R6 redistributes external prefixes into the OSPF routing domain, it sets a bit in its Type-1 Router LSA indicating that it is an ASBR

 

      LSA-type 1 (Router-LSA), len 60

            --- omitted ---

            Link State ID: 6.6.6.6

            Advertising Router: 6.6.6.6

            Sequence Number: 0x80000004

            Checksum: 0x18b4

            Length: 60

            Flags: 0x02 ((E) AS boundary router)

                .... .0.. = (V) Virtual link endpoint: No

                .... ..1. = (E) AS boundary router: Yes

                .... ...0 = (B) Area border router: No


This bit is called the External bit or the E-bit. Once set, it signals to the ABR (R2) that R6 is injecting external information into the OSPF domain. The same can be observed using the show ip ospf database router [RID of asbr] command.

 

R5#show ip ospf database router 6.6.6.6

            OSPF Router with ID (6.6.6.6) (Process ID 1)

                Router Link States (Area 256)

  LS age: 481

  Options: (No TOS-capability, DC)

  LS Type: Router Links

  Link State ID: 6.6.6.6

  Advertising Router: 6.6.6.6

  LS Seq Number: 80000004

  Checksum: 0x18B4

  Length: 60

  AS Boundary Router

  Number of Links: 3

 

The ABR will generate a Type-4 ASBR Summary LSA for the ASBR and flood the Type-4 Summary LSA into all other areas to which it is connected.

 

The following is the Type-4 ASBR Summary LSA generated by R2 for the ASBR R6 that is flooded into Area 0:

 

R2#show ip ospf database asbr-summary

          OSPF Router with ID (2.2.2.2) (Process ID 1)

              Summary ASB Link States (Area 0)

LS age: 0

Options: (No TOS-capability, DC, Upward)

LS Type: Summary Links(AS Boundary Router)

Link State ID: 6.6.6.6 (AS Boundary Router address)

Advertising Router: 2.2.2.2

LS Seq Number: 80000003

Checksum: 0xEE17

Length: 28

Network Mask: /0

      MTID: 0        Metric: 20

 

Note: It is not necessary to flood a Type-4 ASBR Summary LSA in the area the ASBR is located. As previously stated, the area the ASBR is located has sufficient information in its LSDB (specifically a Type-1 Router LSA) to recurse to the ASBR.

 

Notice the advertising router field is set to 2.2.2.2 (R2) in the Type-4 ASBR Summary LSA. This indicates R1, R3, and R4 will solve the shortest path to R2 in order to reach the ASBR R6. Because the ABR sets itself as the advertising router for the Type-4 ASBR Summary LSA, these LSAs have an area-wide flooding scope and will not be flooded across the entire OSPF domain like a Type-5 External LSA.

 

Using the Type-4 ASBR Summary LSA, R2 is saying:

 

“I can be used to reach the ASBR 6.6.6.6 with a metric of 20.”

 

Other ABRs in the topology (R3 and R4) will generate a new Type-4 ASBR Summary LSA, setting themselves as the advertising router for the LSA. For example in Area 489, the Type-4 ASBR Summary LSA for the node 6.6.6.6 is as follows:

 

R4#sh ip ospf 1 489 data asbr-summary

          OSPF Router with ID (4.4.4.4) (Process ID 1)

              Summary ASB Link States (Area 489)

LS age: 31

Options: (No TOS-capability, DC, Upward)

LS Type: Summary Links(AS Boundary Router)

Link State ID: 6.6.6.6 (AS Boundary Router address)

Advertising Router: 4.4.4.4

LS Seq Number: 80000001

Checksum: 0x7F6C

Length: 28

Network Mask: /0

      MTID: 0        Metric: 40

 

Type-4 Summary LSAs contain only the following:

 

  • RID of the ASBR
  • The RID of the advertising ABR
  • Advertising ABR’s metric to reach the ASBR.

 

Type-4 ASBR Summary LSAs do not contain IP addressing information. They merely serve as pointers with information about how to reach an ASBR in the OSPF domain.

Connecting the LSAs


At this point it may seem like the LSDB is just a random array of LSAs with no real structure. In actuality, all of the LSAs in the database are linked by keys. These keys are Link State IDs, and Link IDs that are populated with RIDs, interface address, or other identifiers. Using these keys, the LSDB contains all of the information necessary to allow the SPF algorithm to discover the shortest path between any two nodes.

 

In order to get a good idea of how the different types of LSAs are connected in the LSDB, it helps to have an example or two to follow.

 

This section examines how the LSAs in the LSDB are used in R1’s calculation of the shortest path to reach the 192.168.8.0/24 network and to the external network 172.16.65.0/24. At each step, R1 uses a combination of Link State IDs and Link IDs as keys to discover its ultimate next hop along the path to reach the destination node.

 

To solve the path to the 192.168.8.0/24 network, R1 uses 192.168.8.0 as a key to look up information about the node:

 

R1#show ip ospf database summary 192.168.8.0

          OSPF Router with ID (1.1.1.1) (Process ID 1)

              Summary Net Link States (Area 0)

Routing Bit Set on this LSA in topology Base with MTID 0

LS age: 668

Options: (No TOS-capability, DC, Upward)

LS Type: Summary Links(Network)

Link State ID: 192.168.8.0 (summary Network Number)

Advertising Router: 4.4.4.4

LS Seq Number: 80000002

Checksum: 0x733C

Length: 28

Network Mask: /24

      MTID: 0        Metric: 11

 

R1 knows node 4.4.4.4 (R4) advertised the link to this network with a metric of 11. R1 uses 4.4.4.4 as a key to look up the next LSA with details of how to reach node 4.4.4.4. It matches 4.4.4.4’s Type-1 Router LSA:


R1#show ip ospf database router 4.4.4.4

          OSPF Router with ID (1.1.1.1) (Process ID 1)

              Router Link States (Area 0)

Routing Bit Set on this LSA in topology Base with MTID 0

LS age: 796

Options: (No TOS-capability, DC)

LS Type: Router Links

Link State ID: 4.4.4.4

Advertising Router: 4.4.4.4

LS Seq Number: 80000004

Checksum: 0x6FD8

Length: 48

Area Border Router

AS Boundary Router

Number of Links: 2

    Link connected to: a Stub Network

    (Link ID) Network/subnet number: 192.168.4.0

    (Link Data) Network Mask: 255.255.255.0

    Number of MTID metrics: 0

      TOS 0 Metrics: 1

    Link connected to: a Transit Network

  (Link ID) Designated Router address: 134.1.1.4

  (Link Data) Router Interface address: 134.1.1.4

    Number of MTID metrics: 0

      TOS 0 Metrics: 10

 

R4 has two links. The first link is a link to a stub network that will not transit R1’s traffic. The second link is a link to a transit network pseudo node 134.1.1.4 with a metric of 10. R1 uses 134.1.1.4 as a key to find out how to reach the pseudo network node in the LSDB. It finds the following Type-2 Network LSA:

 

R1#show ip ospf database network 134.1.1.4

          OSPF Router with ID (1.1.1.1) (Process ID 1)

              Net Link States (Area 0)

Routing Bit Set on this LSA in topology Base with MTID 0

LS age: 918

Options: (No TOS-capability, DC)

LS Type: Network Links

Link State ID: 134.1.1.4 (address of Designated Router)

Advertising Router: 4.4.4.4

LS Seq Number: 80000002

Checksum: 0x9ADD

Length: 36

Network Mask: /24

    Attached Router: 4.4.4.4

      Attached Router: 1.1.1.1

      Attached Router: 3.3.3.3

 

R1 discovers pseudo node 134.1.1.4 also has a link to node 1.1.1.1, which is R1 itself. R1 uses its own RID as the key to find its own Router LSA and discover which link it should use to reach the pseudo node:

 

R1#show ip ospf database router self-originate

          OSPF Router with ID (1.1.1.1) (Process ID 1)

              Router Link States (Area 0)

LS age: 1079

Options: (No TOS-capability, DC)

LS Type: Router Links

Link State ID: 1.1.1.1

Advertising Router: 1.1.1.1

LS Seq Number: 80000005

Checksum: 0x290C

Length: 72

Number of Links: 4

--- omitted ---

    Link connected to: a Transit Network

    (Link ID) Designated Router address: 134.1.1.4

    (Link Data) Router Interface address: 134.1.1.1

    Number of MTID metrics: 0

      TOS 0 Metrics: 10


R1 has verified it has also advertised a connection to this pseudo node. This verification finishes R1’s search. It can use the pseudo node to reach node 4.4.4.4, which can reach the network node 192.168.8.0/24 on R8. R1 uses R4’s interface address 134.1.1.4 as next hop, adds the cost up along the path to equal 21, and writes this in its RIB as the inter-area route below:

 

R1#show ip route ospf | i 192.168.8.0

O IA  192.168.8.0/24 [110/21] via 134.1.1.4, 00:53:42, Ethernet0/0

 

NOTE: R1 will also calculate R3’s path to reach the pseudo-node, but the cost value would be 31 vs the 21 of going directly to R4. This is because R1 would forward to R3, which would forward to R4. R4’s cost to the pseudo-node is not used in R1’s calculation, because it is the incoming interface and not the outgoing interface for the traffic. This leads to the cost of 21 instead of 31. In R3’s case, R3’s interface would be used to both receive R1’s packet and forward the packet to R4, which is why it is added in the total cost of the path.

 

To solve the path to the external network, R1 examines the Type-5 External LSA for 172.16.65.0/24:

 

R1#show ip ospf database external 172.16.65.0

          OSPF Router with ID (1.1.1.1) (Process ID 1)

              Type-5 AS External Link States

Routing Bit Set on this LSA in topology Base with MTID 0

LS age: 1624

Options: (No TOS-capability, DC, Upward)

LS Type: AS External Link

Link State ID: 172.16.65.0 (External Network Number )

Advertising Router: 6.6.6.6

LS Seq Number: 80000002

Checksum: 0xDDAB

Length: 36

Network Mask: /24

    Metric Type: 2 (Larger than any link state path)

      MTID: 0

      Metric: 20

      Forward Address: 0.0.0.0

      External Route Tag: 0

 

R1 notes the Metric of 20 to reach the external prefix. Since the redistributing router R6 belongs to an area that R1 does not belong to, R1 needs to build an SPT to someone in its area that already has an SPT built to the ASBR, R6. The listed forward address of 0.0.0.0 forces R1 to use the RID of the advertising router as a key to find the appropriate next hop for the prefix. It matches this Type-4 ASBR Summary LSA:


R1#show ip ospf database asbr-summary

          OSPF Router with ID (1.1.1.1) (Process ID 1)

              Summary ASB Link States (Area 0)

Routing Bit Set on this LSA in topology Base with MTID 0

LS age: 1754

Options: (No TOS-capability, DC, Upward)

LS Type: Summary Links(AS Boundary Router)

Link State ID: 6.6.6.6 (AS Boundary Router address)

Advertising Router: 2.2.2.2

LS Seq Number: 80000002

Checksum: 0xF016

Length: 28

Network Mask: /0

      MTID: 0        Metric: 20

 

Using this LSA, R1 knows node 2.2.2.2 (R2) can be used to reach the ASBR node 6.6.6.6. It notes the metric of 20 and uses 2.2.2.2 as a key to find out how to reach that node discovering node 2.2.2.2’s Type-1 Router LSA:

 

R1#show ip ospf database router 2.2.2.2

          OSPF Router with ID (1.1.1.1) (Process ID 1)

              Router Link States (Area 0)

Routing Bit Set on this LSA in topology Base with MTID 0

LS age: 1942

Options: (No TOS-capability, DC)

LS Type: Router Links

Link State ID: 2.2.2.2

Advertising Router: 2.2.2.2

LS Seq Number: 80000003

Checksum: 0x6C6F

Length: 48

Area Border Router

Number of Links: 2

    Link connected to: another Router (point-to-point)

    (Link ID) Neighboring Router ID: 1.1.1.1

    (Link Data) Router Interface address: 12.1.1.2

    Number of MTID metrics: 0

      TOS 0 Metrics: 10

 

    Link connected to: a Stub Network

    (Link ID) Network/subnet number: 12.1.1.0

    (Link Data) Network Mask: 255.255.255.0

    Number of MTID metrics: 0

      TOS 0 Metrics: 10

 

R1 finds a Type-1 Router LSA for node 2.2.2.2. Node 2.2.2.2 has a link to a stub network, which cannot transit R1’s traffic. It also has a link to node 1.1.1.1, which is R1 itself. R1 uses its own RID as the key to find its own Router LSA to find the appropriate link:

 

R1#show ip ospf database router self-originate

          OSPF Router with ID (1.1.1.1) (Process ID 1)

              Router Link States (Area 0)

LS age: 62

Options: (No TOS-capability, DC)

LS Type: Router Links

Link State ID: 1.1.1.1

Advertising Router: 1.1.1.1

LS Seq Number: 80000006

Checksum: 0x270D

Length: 72

Number of Links: 4

    Link connected to: a Stub Network

    (Link ID) Network/subnet number: 192.168.1.0

    (Link Data) Network Mask: 255.255.255.0

    Number of MTID metrics: 0

      TOS 0 Metrics: 1

 

    Link connected to: another Router (point-to-point)

    (Link ID) Neighboring Router ID: 2.2.2.2

    (Link Data) Router Interface address: 12.1.1.1

    Number of MTID metrics: 0

      TOS 0 Metrics: 10

 

    Link connected to: a Stub Network

  (Link ID) Network/subnet number: 12.1.1.0

    (Link Data) Network Mask: 255.255.255.0

    Number of MTID metrics: 0

      TOS 0 Metrics: 10


R1 verifies it is advertising a point-to-point link to 2.2.2.2 as well. It has now completed the path to reach the external network. In this case R1 does not add up the costs to reach the external prefix; it lists only the cost associated with the Type-5 External LSA of 20 and adds R2 as the next hop:

 

R1#show ip route ospf | i 172.16.65.0

O E2     172.16.65.0 [110/20] via 12.1.1.2, 01:10:10, Ethernet0/1

 

NOTE: R1 does record the total cost of the path in what’s known as a forward metric. The details of why R1 does this is outside the scope of this blog.

 

This example is a bit contrived, but is used to demonstrate how the different LSAs are linked in the LSDB. In reality, R1 uses a much more thorough approach to build its SPT, however, the details of this are outside the scope of this blog.

Summary


When first learning about OSPF’s LSDB, it helps to think of it as a graph. Graphs are collections of nodes connected by edges. For OSPF, these nodes are routers, transit networks, stub networks, and external networks described by LSAs. LSAs are linked through Link State IDs and Link IDs forming edges.

 

This graph creates a complete picture of the network topology from which OSPF can calculate the shortest path between these nodes.