OSPF Introduction

Link state protocols

Remember there are three components to what a dynamic routing protocol is: the databases, which we're going to talk about — the OSPF databases — the messages that are being sent back and forth, and then finally the algorithm it uses to determine what is going to be the best path.

The link state routing protocols are an interior gateway protocol, and some examples of this are OSPF version 2, version 3, IS-IS, and IS-IS for IPv6. Previously we talked about distance vector and how RIP sends the whole routing table back and forth, and that's how it transfers all of the routes, and all the route information gets from router to router. Link state works a little differently.

Link state is a little more complex in how it operates. The communication of course goes between all of the routers, but what's sent back and forth is information on the links, the state of the link. So if a link goes down, that information is then sent to all of the other routers. It operates quite a bit differently than sending the whole routing table.

Since link state is more complex, it has a lot more features and a lot more control over your network. However, it does have some disadvantages. When it initially converges it can be a little bit slower, because there's a lot more that's happening and a lot more communication that's happening. But once that communication is established, then any changes that happen after that converge really fast, versus distance vector, where it's still slow. So link state can have much faster updates once it's done its initial convergence.

From a scalability standpoint, it can scale to much larger networks. From a resource usage standpoint, it has to constantly communicate and constantly keep up to date, so it will use up more resources. And when it comes to implementation, link state can be a little more complex because there are a lot more features involved, and anytime there are features involved and anytime there's more complexity like that, it can be more complicated.

The OSPF databases

OSPF uses quite a few data sets for its algorithm, and it stores that data in databases. One of the examples here is the adjacency database. A database is a table, or multiple tables, that make up the database, so the table in question here is the neighbor table. The adjacency database has the neighbor table in it. The neighbor table is whatever the neighbors are to a router. The router will have other layer 3 devices that it's communicating with directly, so if it's directly communicating to other devices through OSPF, then that will be found in the neighbor table. It's a list of the neighbors, and it's unique to each router — each of the routers has its own set of neighbors. We can view that neighbor table by doing a show ip ospf neighbor.

Another database that is on OSPF routers is the link state database. The link state database essentially contains all the information needed to create the topology, so the table involved in the link state database is the topology table. It holds all of the links and the details about those links, so it's information about each of the links on the network. It contains all of the information of the links in the area. We'll talk specifically about areas, but when we set up OSPF we will define an area, and all of the routers, all of the links within that area are going to show up in our topology table. To see the topology table we would type in show ip ospf database.

Then we have the forwarding database. This is the routing table. The routing table has a list of all of the routes, and it is unique to each of the routers, and we do a show ip route to see that. One other thing to specify is that this topology table actually should be the same across all routers within the area.

Here's an example of a topology and what those databases look like. Each one of these routers is going to have a neighbor table in it, and that neighbor table is going to look different, because R2 is connected to different routers than R1 is connected to, so they are going to have different neighbors and those neighbor tables are going to look different.

The link state database is going to have all of the links within the area, so in this particular one it's going to have the links between each one of these routers, and it's going to be listed all on here. So the link state database, once this network is converged, is all going to look the same on each one of these routers, and the router will actually be able to determine the whole topology from this link state database.

Then we have the routing table. The routing table should have all of the networks in it, but it will have different next hops, so the routing table is also unique to each one of the devices.

OSPF packets

So how do all of the routers get the information needed to create all of these databases? The answer is it's sending packets back and forth. It's quite active, at least initially, in how it's communicating back and forth.

The first type of packet that we have is the hello packet. The hello message that's sent back and forth is what establishes these neighbor tables. It says yes, I am speaking OSPF, and I'm speaking OSPF for this area, so let's communicate and you are now my neighbor. It also makes sure that that neighbor is up, so it sends these hello packets out often just to check to make sure that neighbor is still up.

Then we have the database description. The database description is communication that happens to make sure that all the databases are synchronized, to make sure that there are no changes that need to be made and that everyone is speaking on this with the same revision number, essentially, of database.

Then we have the link state request. This is where, if one router needs to get an update, it can send a link state request to get an update, and the link state update is a reply to that. Then we have the link state acknowledgment, an acknowledgment that yes, I have received your link state update.

Dijkstra's algorithm

Each one of these routers is sending information back and forth. It's sending these hello packets back and forth, making sure that the routers are still up, and it's sending these link state updates back and forth to make sure that all of the devices have all the information they need. Now what that device has is information to create a whole topology of all of the networks in the area. So what does it do next?

It uses Dijkstra's algorithm to figure out what is the fastest way to get to the end destination, to get to a certain network within these networks. Dijkstra's algorithm has been around for a long time, a lot longer than packet switching has been around, and a lot longer than OSPF. Dijkstra's algorithm is a way to find out the shortest path to a location. It's been applied to OSPF, so OSPF uses Dijkstra's algorithm to figure out what is the fastest way to a location.

It takes all of this information and it creates an SPF tree, or shortest path first tree, and that tree is going to show all of the different ways to get to the end network. For instance, let's say we're talking about this end network right here, this 10.2.0.0, and it's coming from this layer 3 switch that's over here. To get to that network, what it's going to do is map out every single path to get to that location, figure out what the cost is to get to that location, and then based off of the cost it's going to choose the lowest cost, or the shortest path, to get there.

The SPF tree

The algorithm creates a shortest path first tree, an SPF tree, and what that looks like is this. This is our network over here, and R1 needs to decide how it's going to get to a network hanging off R6, the 192.168.0.0 network. It needs to get to that network, and it needs to figure out what is the shortest path, so it calculates all of the different ways it could get to that. It goes R1, R2, R3, R4, R6, and then it can get to that network. Or it could go R2, R3, R5, R6. You can see that it starts building this out — R2, R3, R4, R6, or R5, R6 — and creating this tree. This is the tree over here that it's creating. It also sees it can go R3, R4, R6, or go R1, R3, R5, R6 to get to the final destination, which is this 192.168.0.0. So this right here is the SPF tree that it creates.

In this example right here, our network that we've been creating, it's very simplistic. Let's say we want to get from switch one all the way to this network, 10.2.0.0. There is only one path, so we go from switch one to R1 to R2 to R3 and then to that network. So the tree is very simplistic — it's our sapling right here, it's just a single branch on here and it hasn't really branched out, because there's no redundancy within our network.

Here's another example, where let's say this network right here is trying to get to this network over here. This router can branch off into two routes here, and then it goes back down to a single router right here, so that tree is also fairly simple, because the redundancy within this network is fairly simple as well.

Cost

Once you have the full tree, it calculates it based off of bandwidth, so it needs to choose what is the lowest cost to get to this network. It does this by figuring out what the cost of this is, so maybe this is one, one, and this is 19. Now it can take that and put it on this list here, and it sees that it takes 20 to go this route and it only takes two to go this route, and so therefore it's going to choose the lower cost of the two.

In the rest of this module we're going to take a deeper dive into the databases, into the packets, and into the cost, so we will be covering this a little more in depth as we go along. For now, what we have covered is the link state protocols and what the differences are, some of the databases with OSPF and how it uses packets to pass information back and forth, the Dijkstra algorithm it uses to figure out what the SPF tree looks like — the shortest path first tree — and then we wrapped it up by talking about cost and how it calculates cost.