Routing protocols under the hood: Link State and Distance Vector

When you are studying for your CCNA or CCNP you will encounter routing protocols. A CCNA will encounter OSPF, CCNP students will additionally encounter EIGRP, RIP and BGP. What’s the difference between these routing protocols, and why are there so many?

Each routing protocol has its own benefits, but each routing protocol will (primarily) be categorized in one of the following types, though some protocols will have a little of both in them:

Distance Vector
Link state

Distance Vector routing protocols

Distance Vector protocols were the first routing protocols to be developed. These were fairly simple (at least back then) and worked on a principle of pointing in a direction and stating how far away the destination was. This is comparable to a signpost on an intersection. It tells you which way to go, and how far it is.

Routing protocols under the hood: Distance Vector

Distance vector protols work by routers telling other routers that they know the way to a specific destination. They tell the other router the distance to that destination and let the other router decide what to do with that information. It might be that this router will use this information to tell travelers which way to go, but it might also be discarded because the router knows of another, better route.

Let’s look at the following example. Let’s say we have a destination network connected to Amsterdam and we want to get there from router Dublin. Dublin knows it’s not connected to that network locally, so it needs to route. Based on information it got from Berlin and Copenhagen it can go two ways. Berlin tells Dublin that Amsterdam is a distance of 10 away from it. Copenhagen tells Dublin that it’s distance to Amsterdam is 15. That means that Dublin has to know the distance between it and Berlin and Copenhagen respectively. Depending on that distance Dublin will make a decision. In this case it will send traffic to Berlin since the total distance via Berlin is the shortest.

What Dublin doesn’t know is what’s between Berlin and the destination. There might be more routers between it and the destination, or there might not. The only thing it knows is that the distance between Berlin and Amsterdam is 10. For Dublin everything behind its directly connected neighbors is a mystery.

Link state routing protocols

Link state protocols work differently from Distance Vector. A real world anology would be somebody with a map of the city. That person can work out the best way to get from A to B.

Routing protocols under the hood: Link State

In the case of link state protocols a router has a complete overview of the network. It knows which routes there are, but also knows their state and cost. This means that a router knows when a specific link has failed and will use that information to select a different path to the destination.

This also means that a router needs to know of all possible destinations, links and routers within a network, otherwise it could never make those decisions. It also requires this information to be the same on all routers, as it is possible when two routers have different information they might send traffic between each other.

For example, both routers Amsterdam and Berlin have a direct connection to router Copenhagen, behind which network A is connected. Because the link between Berlin and Copenhagen is slow, Berlin chooses to send traffic destined to Copenhagen via Amsterdam. Now the link between Amsterdam and Copenhagen fails. Amsterdam knows about the alternative route via Berlin, so starts sending traffic to Berlin. Berlin however, not having heard about the failure of the Amsterdam – Copenhagen link, might still send the traffic back to Amsterdam. This is why link state protocols need to have very robust and fast ways to synchronize information between them.

Which type of routing protocol should I use?

Whenever you have two types of protocols the question which of the two is better immediately arises. Is Link State better than Distance Vector? In some cases yes, in other cases no. It always depends. However, when looking at the current state of affairs in the routing world we see that Link State protocols tend to be used more often. OSPF is probably the most implemented protocol in enterprise networks nowadays.

Advantages and disadvantages of Distance Vector

Distance Vector protocols have the following benefits:

fairly simple protocols
Possibility to apply summarization (information hiding) at any point in the network
Requires less processing power
Often very scalable

The following are some of the disadvantages of Distance Vector:

Converges slowly
Older Distance Vector protocols had issues concerning long (permanently) lived loops

Advantages and disadvantages of Link State

Link state protocols have their own benefits:

Very fast failover (because of complete view of the network)
Scalable (when using routers with sufficient processing power)

The disadvantages of Link state protocols are:

Requires a lot of processing power
Requires more bandwidth in the network due to updating the link state information
More complex

Summary

Looking at the benefits of each of the protocols you would expect Distance Vector protocols to be in the lead. They clearly have more benefits. However, the benefits of Link State, and especially the speed factor, are big enough that Link State protocols are used more often. We should add a footnote here however. Both OSPF and IS-IS, the best known Link State protocols use Distance Vector logic to be able to achieve larger scale. Routing between area’s in these protocols use Distance Vector technology.

Introduction in Networking: ARP, the Address Resolution Protocol

Different layers of the networking stack have different functions, as can be read in another blog of this series. Introduction in Networking: The OSI model and TCP IP model explored. Layer 2 in networking is responsible for local communication. Layer 3 is responsible for global communication. Both layers have their own specific addressing schema. ARP is the protocol that enables network devices to create a translation between the layer 3 address and the layer 2 address.

Any device connected on an ethernet network will have a network interface card (NIC). This NIC will have a specific address. These addresses are configured by the factory who made the NIC. This address is called the MAC address. MAC stands for Media Access Control. It is also called the physical address or the BIA (Burned In Address). The MAC address is what is used to send data on locally connected networks. That means that when you send something on an ethernet network you will use the MAC address. You can see that happening in the screenshot below. This is part of a traffic capture of traffic on my Apple iMac.

Something you should also notice in that screenshot is that the capture actually says it’s an Apple device. It is sending the traffic to a device called Arcadyan, which is my home router. You can see the frame (on layer 2 we talk about frames instead of packets) has a source and destination address. The first three octets can be used to figure out the manufacturer of the device. There are many sites where you can do this. I often use the wireshark website to do this. These first three octets are also called the Organisationally Unique Identifier (OUI). Try it out for your computer. If you have a Windows machine use the command “ipconfig /all” in a cmd window. On a Mac and Linux system you can use the “ifconfig” command in a terminal window.

The word octet in networking refers to 8 bits. You might wonder why it’s not just called a byte then. Well, that’s because of history. Historically a byte refers to the smallest addressable unit in computer memory. Some systems had bytes that were either smaller or bigger than 8 bits. An octet is always, per definition, 8 bits.

MAC addresses are in hexadecimal format. That means each character represents 4 bits. So a single octet consists of two characters. When looking at the mac address 4c:09:d4:cd:dc:3c all octets are separated by colons.

How does ARP work?

So, let’s zoom in to ARP a bit more. What does it do and how does it do it? To be able to send something to somebody you need to know its address. ARP is there to help you get that address. A device uses arp to ask about the address of another device. It knows the IP address it wants to send something to, but it doesn’t know the hardware address. Because of that it will ask around who has a specific IP address. The device owning that IP address will respond to the request. That way the requestor will get its answer and be able to send traffic to the intended destination.

But wait, how can we ask who owns a specific IP address if we don’t have a physical address to begin with? Don’t we need one? Yes we do, we need a physical address. But the address used in this instance is the broadcast address. Aside from listening to its own address, a NIC will also listen to the broadcast address. That means that when it sees a frame addressed to the broadcast address it will process it as if it was addressed to that specific NIC.

Let’s look at the actual packets being sent. In the wireshark overview we can already see clearly that somebody asks ‘who has 192.168.2.11? Tell 192.168.2.3’. This is actually what ARP is all about. Ask who has the address and give the information who to tell.

When we zoom in a bit further we can see several fields defined in the request. The most important for now is the Target MAC address. Which is all zeroes. The all zero MAC address is the broadcast MAC address. Here’s a list of all fields and what they represent.

Hardware Type: The predominant hardware type is Ethernet. ARP was created to support multiple hardware types, but since ethernet is virtually the only remaining L2 protocol, you will likely only see Ethernet here. The idea however was that the upper layer protocols would be able to interpret the other fields based on the layer 2 protocol defined in this field.
Protocol Type: This will likely also always be IPv4 as it is in this example. IPv6 could have used ARP, but for IPv6 the Neighbor Discovery (ND) protocol was defined.
Hardware size: This defines the amount of octets that are needed to describe a hardware address. If ever they introduce longer hardware addresses like 64 bits instead of 48 the idea is that ARP can cater to that. This also works for protocols other than Ethernet. Maybe some other protocol uses a different physical address size.
Protocol size: This is exactly the same, but for the higher level protocol. If they were to use ARP for IPv6 the size would be listed as 16 instead of 4.
Opcode: This is the operation requested of ARP. In these examples we will see opcodes 1 and 2 (request and reply). Most other opcodes aren’t used anymore, but special note goes to code 3 and 4 which are reverse ARP request and Replies. We will go into reverse ARP shortly.
Sender MAC address, Sender IP address, Target MAC address and Target IP address: These fields are the most important, but also the most self explanatory fields. This is what makes ARP ARP.

The ARP reply is exactly the same message. The only difference between the two is that the sender and receiver are reversed. Of course, this time no broadcast MAC address is used because the actual MAC addresses are known.

Reverse ARP

ARP itself was defined in 1982, almost 40 years ago. At that time there was no way to automatically assign IP addresses to devices. All devices needed to be statically configured. In the years after the introduction of IP people started noticing this was cumbersome. What they needed was a way to automatically (not necessarily dynamically) assign IP addresses. The first attempt at that was Reverse ARP. That way a system, knowing its own MAC address could send out a reverse ARP request to get the IP address that belonged to that MAC address.

Reverse ARP was defined in 1984, but since it was very limited it was quickly succeeded by the BOOTP protocol, which in its turn was eventually replaced by DHCP.

Introduction in Networking: The OSI-Model and TCP/IP model explored

To explain the OSI-model, let’s start with an example. Bob wants to send stroopwafels to Alice. Bob (of course) lives in the Netherlands. Alice lives in the USA. For the stroopwafels to arrive at Alice, Bob needs to package them. He puts them in a box and puts a label with an address on the box. The address is formatted according to international agreements. Bob brings the package to the post office. Here he gets the option to either choose for reliable delivery, or unreliable delivery. Once the postal service has the package they can choose to send the package by plane or by boat to the USA. After a while in transit the package is delivered to Alice. She verifies that her name and address are on the package and opens it.

The story of Bob and Alice looks a bit like an application that wants to send a message across the network. It doesn’t matter to Bob whether the package is sent by plane or by boat (though it would be a shame if the stroopwafels pass their expiry date). Bob just wants to know for sure that the package arrived. Real world examples are always a bit simplistic, but the interfaces between these layers are there in the story too. Bob has to make a decision whether to send the package in a reliable way or not. He does not care how the postal service realises this. He also doesn’t care whether the package is delivered by UPS, USPS or Fed-Ex once it is in the USA.

Network applications work a bit like this example. The application has something it needs delivered to another system, so it asks the network to take care of this. Before the OSI and TCP/IP models existed a programmer needed a lot of intimate knowledge of networking to get the application to do this. That’s why these models were defined. This way the programmer doesn’t need to know how to send data on a radio link versus a wired link. It doesn’t matter whether the network is IPv4 or IPv6, etc.

The ISO OSI model

Back in the seventies there weren’t any models that would define these layers and interfaces between the layers. The International Standards Organisation set out to define a model for this. The model became the OSI model, which stands for Open Systems Interconnection. This model consists of seven distinct layers and interfaces between these layers. The image below shows these layers.

Layer 7, Application: This is where the application itself resides. This is the layer that takes care of the interaction with the user of the system. User in this case does not need to be a human.
Layer 6, Presentation: The presentation layer is a layer that is often misunderstood. It is the layer that defines the way the date should be interpreted. That means that it defines things like data compression and decompression and data formats like XML and JSON.
Layer 5, Session: This layer keeps track of sessions in the datacommunication. This is also a often misunderstood layer. The reason for this is that this layer (and the presentation layer) doesn’t exist in the TCP/IP model and sessions are therefore managed by different layers in the model. Something that could happen in a session layer is neighbor adjacency status tracking for a routing protocol
Layer 4, Transport: This is often compared with the TCP and UDP options within the TCP/IP model. The transport layer defines things like reliability, flow control and error control.
Layer 3, Network: This layer concerns itself mostly with addressing and finding the destination in global networks. This means routing in larger networks.
Layer 2, Data-link: Datalink is used for system to system communications. So transporting data within a segment. For this it manages the different protocols that can exist for communication between two systems, such as Ethernet and ATM. But also WiFi lives for a large part in this layer.
Layer 1, Physical: The physical layer concerns itself with the way bits are transported on the wire. It governs things like voltages and timing between bits.

The OSI model is used as a reference model. It is primarily a study source, but very helpful to understand layers in networking. The layers might not be implemented in a 1:1 manner, but being aware of these layers is very helpful.

The TCP/IP model

The TCP/IP model is what is actually implemented at this moment. It could have been the other way around, but because IP became the most popular protocol, the accompanying model also became the de facto model.

The model is very similar to the OSI model, but differs in some slight ways. Look at the image for this.

As you can see the TCP/IP model has an application layer like the OSI model. However, this model spans the Presentation and Session layers as well. That means that anybody wanting to create an application based on the TCP/IP model must implement session and presentation functions in the application itself. Luckily you can use libraries for this, but it is the responsibility of the application programmer to do this.

The Transport layer is the same as in the OSI model. This is where TCP and UDP live. The network layer is called the internet layer in the TCP/IP model, but their functions are the same. The TCP/IP model combined the physical and data-link layers.

This is also where the OSI model returns to our daily lives. When you troubleshoot a network, or when you are configuring switching you will discuss ‘Layer 2’. In the TCP/IP model, layer 2 would refer to the Internet layer, but that’s not what we mean with layer 2. Whenever somebody refers to a layer with a number they are referring to the OSI model and not the TCP/IP layer.

In fact, it’s a good idea to learn both layers, but on a day to day basis you will likely discuss OSI model layers more often than TCP/IP model layers.

Layers in action

The image below is a traffic capture of a HTTP request packet. You should notice right away the amount of lines you see. Five of them in total. The TCP/IP model covers 4 layers and the OSI model covers 7. So 5 differs from both of them. This immediately shows the difference between models and real life. What you see here are the Physical, Data-Link, Network, Transport and Application layers. So a combination of both OSI and TCP/IP models.

Physical layer

Let’s first zoom in to the physical layer. What can we see here?

Not too much information. The reason for this is that when you capture this data most of the real physical level stuff has already been processed. We won’t be able to see things like codecs that govern bit patterns, voltages and the like. What we can see is that the physical layer refers to Ethernet. Which is the protocol used on layer 2. So let’s zoom in to layer 2 next.

Data-Link layer

The data-link layer gives us a bit more information. We can see the source and destination mac addresses of the connection. This traffic is directed from my Apple iMac to my modem. The server itself is out on the Internet, but data-link layer communication is always local. Again we can see the next layer protocol, which is IPv4 in this case.

Network layer

On the network layer we can see a lot more. We can see a source IP address and a destination IP address. We can also see things like the Differentiated Services Code Field, which is used for Quality of Service. There are several flags and a Time to Live. This ensures that the packet will be discarded in the end if it fails to reach its destination in 64 ‘hops’. Again the next layer is defined, being TCP in this case.

Transport layer

The transport layer in this case is TCP. That means that the application requested a reliable delivery. We can see a source and destination port. These are used to establish sessions, which in the OSI world would have been done by the session layer. We can see sequence numbers and acknowledgements. These are used to provide the reliable transport. Same goes for the checksum, which is used to verify whether the received frame was not modified in transit.

You might notice it does not refer to an upper layer protocol. That’s because TCP does not know about any upper layer protocols. It also doesn’t matter for TCP, as the end system will handle that based on the destination port. These ports are mapped to applications, so it will cause the packet to be delivered to the right application.

Application layer

The application layer contains the application specific information. This can be anything a programmer thought of. In this case the application is HTTP. It contains information required to process the HTTP request on the server.