By default, routers send packets based on the destination IP address of packets. In small networks, this problem is easily solved through the use of statically telling the router where the next-hop of traffic is, but as the size of the network grows, it starts to be a large problem.
Figure 1
See Figure 1, this is an example of a SMB network that one may find at a gas station or store. It has a single router, one switch with the endpoints connected to the switch. It is very common to see the switch have a static route in its route table, that for all traffic not local to the switch, point all traffic to the router. The router in turn, will have a static route pointing to the upstream internet provider. For the size and complexity of this network, using static routes makes a lot of sense; however, see Figure 2. This has several more routers, an attached small DC environment, HQ location, and two internet providers.
Figure 2
Static routes can work here, but it would be substantially more complex to do so. Every router would need a static route for every destination IP that is not on its network. If there are 5 routers, and 5 networks attached to each router, it would be an n * (n-1) problem of just static routes. Moving networks between routers or adding new routes as the company grows would be prone to human error.
The solution to this problem is to use a dynamic routing algorithm that allows for network appliances to share routes between themselves without any human intervention. This is a very old solution that has been around since the ARPANET days in the 1970s. These algorithms share some common aspects with each other. First, they need to share route information without causing loops within a network. Loops are bad and can cripple a network. Below is an example of what a loop looks like as seen in a traceroute. Each router thinks that the best way to x destination, is through each other. When this occurs, the packets will keep being sent between the routers until the packets TTL expires. Due to this, there is a metric that the routers keep calculating loops. A distance vector like RIP uses hop count, BGP uses AS Path, and something like OSPF/IS-IS uses a distributed database that has a copy of the complete network. Secondly, they must be able to share routes quickly, and converge quickly. Convergence in dynamic routing means that all routes have been shared to every router and all routers share the same network topology. Thirdly, they need to scale well, whether that is scaling number of routers or number of routes that they can share. The original protocols utilized in the ARPANET/Internet had issues with the scalability as the size of the internet table grew and were replaced with more robust protocols.
Algorithm and Protocol Flavors
There are two main types of routing protocols that are utilized today and two types of algorithms within those. The main routing protocols are Exterior Gateway Protocols and Interior Gateway Protocols.
Exterior Gateway Protocols were designed to be utilized to communicate with networks outside of a company’s control, such as the internet. This protocol would run at the edge of the network with Internet Service Providers to exchange routes and information about those routes. The original Exterior Gateway Protocol was called EGP (Exterior Gateway Protocol). It was an ingenious name, and this EGP was used by the ARPANET way back when. While no longer used, its descendant that is utilized is called Border Gateway Protocol or BGP.
Interior Gateway Protocols or IGP is the opposite of an EGP. It is primarily used within a company and controls route sharing between a companies’ network equipment. IGP needs to be resilient during normal network events. Unlike the Internet, which never converges, a network under a single network administration (called an Autonomous System) must converge quickly. If a router goes offline, or a link goes down, the IGP should not have to wait 30-60 seconds to remove those routes from its table or to update what the new best route is.
Figure 4 (Autonomous system, with BGP running to Comcast and IGP locally).
There are two primary routing algorithms utilized: distance vector and link-state. Distance vector algorithm works that a router will advertise its attached networks to its neighbor. The neighbor will do some route loop verification, before passing that information to its neighbors with its connected routes. This information will propagate till every router has a route to every destination within a network. Distance vectors use some variation of a hop count as its metric and loop prevention. RIPv1/RIPv2 was the most common distance vector that was utilized which used hop counts to find the best path. The routes with the lowest hops from point A to point Z would be chosen as the best route. This is also known as “routing by rumor”. Z tells Y its routes, who in turn tells X those routes, until A finally hears about them. Z does not tell A directly what his routes are, but they propagated through the network until A finally gets that route update.
There are pros and cons to distance vector algorithms. They are easy to setup, easy to understand, and can quickly get a small network up and running. The problem with most of the pure distance-vector algorithms, such as RIPv2, is that the metrics that they use are simplistic, and convergence time is slow. Cisco EIGRP and BGP are distance-vector algorithms on steroids and use more than just a hop count to determine what the best route is. While hop count is an important metric to them, it isn’t the only metric a router uses to determine the best direction to send traffic.
Link-state utilizes a more complex algorithm that ensures a loop-free topology. Link-state algorithms, unlike distance vectors, will create a database that maps all routers and their links. All routers within a given environment must have the same information in this database. This database is a tree of the network, where every router knows how every other router is connected to each other. Once routers have the same copy of this database, they are then able to run some form of Graph Theory Algorithm against it to find what the best route is for any attached network. This completely ensures that every router knows about every destination. The metric that is used here is one of cost. Every link of a router that is running an algorithm is given some cost to every other router. The cost is based on the size of the interface that the router has. For instance, a 1G interface is slower than a 10G interface, therefore, the cost of the 1G interface would be higher than that of the 10G one. A lower cost is preferred.
The two main link-state algorithms are OSPF and IS-IS, which both utilize an algorithm called Dijkstra to determine the best cost. Dijkstras algorithm is a weighted graph theory that is computationally fast (https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/).
Like Distance vector, there are pros and cons to this as well. Distance Vector is easy to setup but more complicated to understand and troubleshoot. Each router having an exact copy of the database ensures loop free topologies (outside of potential micro-loops) and split-horizon errors.