IP Routing

Routing is a Layer 3 function of the OSI Network Stack. The device which performs routing is called a router. In essence, routing is a function performed using protocols by routers to forward information from one point to another within a network.

There are various routing protocols that exist for “transporting” packets from Router A to Router B. Routing is comprised of 3 steps:

• Path Calculation — Find a way(s) to get from point A to point B
• Path Selection — Select the best way to move from point A to point B
• Forwarding —Sending the packet on its path to victory!

Path Calculation

At the end of the day all a routing protocol does is take some kind of network information as input and convert it into a routing table which is essentially a set of IP routes with the “next hop” to take. The router would then use this routing table and insert it into its global routing table(which is formed by using these routes from all routing protocols running on the router).

Based on the kind of information a protocol uses to determine the output we can classify routing protocols as the following types:

• Distance Vector:
• Link State
• Path Vector

Distance Vector Routing Protocols

Individual routers don’t have visibility to the entire network topology. They only know of the routes reachable by their neighbors and simply add their distance to that route. For eg router A learns about route B from router C, this is how it will calculate its distance to route B( i.e. Bellman Ford algo).

d(A-B)= d(C-B) + d(A-B)
dmin(A-B)= min(d(A-B) via X) where X is all the neighbors

Once a router can calculate this distance it will then send this “vector” of distance and route information to its neighbors. Once the information is spread to all the routers in the network the routing protocol is said to have converged!

The main advantage of this protocol is that it's lightweight and needs less CPU and memory (Chrome users, LOL)!

An example of this routing protocol is RIP ( and as the name suggests is virtually RIP). The main reasons are as follows (called Cons):

• RIP scales very poorly since any network change will have to be propagated across all routers. We cannot have more than 15 hops in RIP.
• The notion of the cost was limited to “hop count” for RIP which is NOT AT ALL COOL! You may have a shitty 128 kbps line connecting two routers directly and a 1Gbps link connecting them via a 3rd router. Of course, you would want to use the 1Gbps!
• Routers running distance vector protocols are too chatty! They love sending updates to their neighboring routers hence they lead to less efficient bandwidth use.

Cisco is a cool company! They saw this and thought we need something better. So they came up with EIGRP(it's not exactly a distance-vector but it isn't link-state either). It's essentially RIP on steroids. The fact is I don't know EIGRP and I don't care! So let's move to Link State, Yay!

Link State Routing Protocols

In a Link State routing protocol, each router maintains and tracks the states of each link in the network. So routers have complete information on all other routers in the network. Think of it like a paper map. Once you have that laid out, you can use your amazing intuition to find the shortest path from point A to point B based on the distance, quality of road(prefer highways), or cost(avoid tolls). But routers not as intelligent as you they lack intuition, so we make algorithms for them.

One of the most popular link-state routing protocol is Open Shortest Path First(OSPF). It does what it sounds like, finds the shortest path, and puts it first(prefers it). It uses an algorithm called Dijkstra's shortest path algorithm to do that.

It gets rid of almost all the problems of distance vector protocols, we can now use customized cost functions, Less chatty routers, better scalability. This comes as one cost higher CPU utilization(so in a way OSPF is the Chrome for routers, it's amazing and everyone uses it).

Did you notice, I used “less” and “better” in the previous paragraph! No matter how amazing OSPF is there is a time when processing the entire network topology becomes too much. Sometimes, what we want is low and best! Hence we discuss the path vector protocols.

Read OSPF 101 for more info on OSPF.

Path Vector Routing Protocols

These protocols are just like Distance vector protocols however the notion for distance is changed to a “path attribute”, which can be anything ( organization, country, bandwidth). While the other routing protocols aim to find the most efficient path, path Vector protocols are best suitable for things that are more policy-based(like business reasons, regional politics, etc).

The beauty of path vector protocols is that they scale very well since they dont use any “shortest path” algorithms. One example of path-vector routing protocols is the Border Gateway Protocol(BGP). As a testament to its scalability, BGP scales so well that the internet is built on BGP and it supports more than 1Mn+ IPv4 prefixes currently.

Path Selection

Once various routing protocols have provided their outputs that is essentially a destination route prefix(an IP subnet) and the associated cost(or metric). The router then compares these routes from all protocols running on the router and pushes the best routes to a global routing table.

Now the terms I will use are a bit specific to Cisco but the idea remains the same. Cisco calls the global routing table the GRIB (Global Routing Information Base) hereafter referred to as the RIB. It is a list of paths that the router refers to while forwarding data packets through itself. The fight for a place on the RIB in on a per-prefix(each prefix fights its own battle) basis and is based on the following factors:

• Prefix length — The path corresponding to the most specific prefix length is chosen for e.g. 10.0.1.0/24 via gi0/0, 10.0.1.0/25 via gi0/1 are under consideration, and a packet with IP address 10.0.1.1 comes in it will exit via gi0/1 since /25 is more specific.
• Administrative Distance: Each routing protocol has a value of priority associated with it which determines its preference. A protocol with a lower AD is preferred(i.e. Static Route > eBGP > OSPF > RIP) . One should try to remember the AD major routing protocols like BGP and OSPF as well as that for connected and static routes.

• Metrics: IGPs will generally prefer routes with a lower cost to reach a particular destination. This can be different based on different IGPs. If the costs are the same some protocols like OSPF support equal-cost load balancing! This is very useful since it ensured better utilization of network resources. Protocols like EIGRP also support unequal cost load balancing.

Forwarding

Once the paths have been calculated and selected they are installed in the FIB(forwarding information base) . The FIB is similar to the RIB and has the following information.

• Destination prefix — A network subnet with a mask
• Next Hop IP address — The next-hop IP address

Whenever a packet comes the router will read its destination IP header and lookup at the FIB and find the next hop. Cisco does a neat trick called Cisco Express Forwarding to make this lookup fast and support low switching latency!