Before you start
Objectives: learn what is routing protocol and which characteristics can a routing protocol have.
Prerequisites: you have to know what a router is, and how to subnet an IPv4 address.
Key terms: routing, routers, network, information, protocol, link, method, metric, router, path, subnet
Routing Protocol Definition
Routing protocols are used by routers to learn and share information about routes from neighboring routers. There are several different routing protocols that can be used today, each working in specific way which has its strengths and weaknesses. Because of that we usually classify routing protocols based on their characteristics.
Routing Protocol Characteristics
Scope
One of the characteristic of the routing protocol is the scope. The scope identifies how much information about our network is shared and remembered by our routers. To understand this we have to know what the term Autonomous System means. In networking Autonomous System (AS) is usually a private network or multiple connected networks managed by one or multiple organizations which have a common routing policy to the Internet. The autonomous system is practically independent from the internet, and the only thing that is shared is one common link into the Internet. Each organization that has been assigned a network address from an ISP is considered an Autonomous System. Different organizations which are connected to the Internet each have a different autonomous system number, which has to be registered. The autonomous system might also be identified by the ISP.
Autonomous Systems
The scope ot the routing protocol identifies boundaries of information sharing. When talking about scope, routing protocols can be classified based on whether they are routing traffic within or between autonomous systems. For example, an Interior Gateway Protocol or IGP is used within an autonomous system. This means that we can use this protocol within our private network to share information between routers. On the other hand we also have an Exterior Gateway Protocol or EGP. EGP is used to share routing information between autonomous systems. So, EGP can be used to route data between routers on the Internet and to route data into autonomous systems. As network administrators we will usually work with IGP routing protocols.
Metric
Another characteristic of a routing protocol is the metric value which is assigned to each route in routing table. The metric indicates the distance or the cost to the remote network. It is used to determine the best route to a destination network, if multiple routes to the destination exist. The lower the metric, the more preferred the route is.
Metric can be expressed in different ways, and one of the way is the hop count. The hop count is the number of routers that must be passed to get to the destination network. Let’s see that on the example. We have Network 1 and Network 2. On one route between those two networks we have to pass one router, on the second we have to pass two routers, and on the third we have to pass 3 routers.
Different Paths
So for example, if we have a message that needs to be send from Network 1 to Network 2, there are 3 paths that the router can take. If the router takes the path with three routers in between, the packet will have to pass 4 routers in order to get to Network 2. If it takes the path with three routers, the packet will pass 3 routers in order to get to Network 2. In the last case, the packet will have to pass two routers (two hops).
Number of Hops
In general, if we use some routing protocol which uses hop count as its metric, that routing protocol will use the path with the lowest hop count to get to the destination. In our case it would use the path with only two routers between networks.
Another type of metric that can be used in routing protocols is a metric based on the bandwidth or delay. Delay is the time it takes to reach the destination network. Both bandwidth and delay give us information about the speed of the link between two routers. In our example, we have links with different speeds between our routers. One path has dial-up links, other has 100 Mbps links, and the last has 1 Gbps links.
Speed of Links
In this case, if we use some routing protocol which takes into consideration the bandwidth of the links to form the metric, it would use the path which has 1 Gbps links because it is the fastest path, in spite of bigger number of routers. On the other hand, if we use some routing protocol which uses hop count as its metric, it would use the path with dial-up links because that’s the path with lowest number of routers in the path. As we can see, it would prefer a route which is actually slower. When using the bandwidth or delay as a metric, each link is assigned a relative cost value. Let’s see this on our example. Let’s say that dial-up links have a relative cost value of 1000, 100 Mbps links have a cost value of 100, and 1 Gbps links have a cost value of 10.
Link Cost
As we can see in our case, the total cost to get from Network 1 to Network 2 using the 1 Gbps links is 40. If we use the 100 Mbps links the total cost is 200. If we use dial-up links, total cost is 2000. In this case again, the lower metric wins so our routing protocol would use the path with 1 Gbps links. The values of relative cost for links are assigned based on bandwidth or delay, and are dependant on the routing protocol. Some protocols will even use more complex computations which take into account various criteria when sending real data between two routers. The thing to remember is that routers in this case calculate the value based on the bandwidth or delay to assign the link a specific value. That value is then use as a metric which helps to determine the optimal path through the network.
Another metric that can be used is a relative value. In this case the routing protocol will assign a default value to each link on the network. Network administrators can change those values and in that way determine the path for traffic to flow. If all links have the same value, the routing protocol will use the hop count to determine the best path. This relative value that is assigned is called a link cost. Link cost can for example relate to the actual cost of using a link.
Methods of Information Sharing
Routing protocols can use different methods to share information between routers. The first method that we will talk about is the Distance Vector Method. With this method every router shares its entire routing table with its immediate neighbors. Routing information is shared by routers at periodic intervals. Before the routing protocol starts to work, each router would have only the directly connected networks in its routing table. At the first interval of sharing, routers actually exchange information about their directly connected networks. Routers receives information and compares it with the information in its own routing table. If it doesn’t have information about received networks, it will add them to its routing table. If the routing protocol is using the hop count as the metric, it will also send that information with the routes. All directly connected networks have the hop count value of 0. When the router receives the route from another router, it will increment the hop count by 1 to indicate the number of routers that have to be traversed in order to reach the destination network. All routers on the network share information from their routing table with the neighbours on regular intervals. With each update there are more routes in each routing table. Routers will get routes from other routers and continue to share that information with other routers on the network. In other words, routes learned from neighboring routers are added to the routing table, and then shared with other neighbor routers. The routing tables will continue to populate until all routes are learned by all routers in the network. When all routes are learned by all routers we say that the network converged. When this happens, all routers have a consistent view of the network. Remember that with the distance vector method every router shares its entire routing table with its neighbors at every update interval.
Another method of sharing information between routers is the Link State Method. With this method routers only share information about their directly connected networks. It uses special messages called Link State Advertisements (LSA) and Link State Packets (LSP) to share information. When a router receives an advertisements from another router, it records the information in its own routing table, and then forwards that same information to other routers within the network. In that way the same information from one router is read by all routers on the network. The process of sending LSAs and LSPs is called flooding, because a single packet is forwarded throughout the entire network. Routers use those advertisements to build a topology of the network within its own routing table. By using this method each router will learn about every other network over some time. After the convergence occurs, advertisements will only contain changes instead of all directly connected networks. And that’s where the main difference between the distance vector and the link state method is. With the link state method routers only share information about their own routes with their neighbors, and these updates are passed along between routers. Once the convergence is reached, routers only share information about changes, not all known networks at every update.
The last method used to share information is a hybrid method. This methods combines the distance vector and link state methods. In reality, this is a distance vector method which has advanced features such as sharing only routing changes after the convergence. It shares its full routing table at startup.
In general the distance vector method is simpler. Because of that it requires less processing time. However, they do use more bandwidth so they are recommended for small networks. The link state method uses less network traffic and it converges faster. Because of that Link state methods are more suited for larger networks or for sharing routes over WAN links.
Hybrid methods combine benefits of both mentioned methods.
Variable Length Subnet Mask
Older routing protocols did not support variable length subnet masks (VLSM). With VLSM routers can use subnet masks that are different from the default ones. This feature is called Classless Inter-Domain Routing (CIDR). For example, let’s say that we have an address of 172.16.0.0, which has the default subnet mask of 255.255.0.0. This mask uses 16 bits in the subnet mask. With VLSM we can use a custom mask and subdivide this address into multiple subnets. For example, we can create networks 172.16.1.0/24 (24 bits used in subnet mask), 172.16.2.0/24, and so on. In this way with a non-default mask we create smaller subnets.
Older routing protocols only used the default subnet mask when sending routing information. Well, actually they would only advertise the network, and receiving router would imply the subnet mask based on the address class. This can cause problems if we use VLSM on our network, and the routers use the routing protocol which doesn’t support VLSM. With VLSM support routers are able to advertise the subnet mask along with the subnet address. This is very important if we use VLSM on our network. Well, this is not a big problem any more since virtually all routing protocols today support VLSM. Only older protocols use the default address class. Routing protocols that do not support VLSM are called classful routing protocols. In that case routing protocols use the address class to identify the subnet mask. Routers that do support VLSM are called classless routing protocols. In that case the address class is ignored and the subnet mask is included with the routing information.