IP routing (part three)

In this post I dive into routing, which I previously knew almost nothing of. There's quite a lot of history in routing, and in researching this topic I was quite suprised at how facinating it is. I think I had wrongly assumed that routing was a boring topic ;)

This bulk of this post is on the differences between interior and exterior routing, which I'll get into without further ado.

Network routing

A network consists of nodes, and routing describes the particular route a signal in the network will take to reach its final destination. Routing happens in all types of networks, going back to circuit-switched telephone networks to the packet-switching networks of IP. The core nature of routing is to select the best path for network traffic, either for traffic happening within a single network, or between multiple networks. In IP networks, routers try to make the best choice on where they should forward packets to get the packets to their destination network address.

The most common type of routing on the internet is dynamic routing, handled by routers that maintain updated routing tables reflecting the topology of the network. A basic routing table contains information as a list of routes to particular network destinations. More advanced routing protocols might also include distances or other values associated with those routes. The flexibility of routers to constantly update and broadcast their updates to their neighbors is what enables the flexibility and resiliancy of a massively decentralized and fluctuating internet network.

IP routing assumes that network addresses are structured, which means that similar addresses imply proximity witin the network. If an IP packet has a destination outside of a specific subnet mask, the router forwards the packet to the nearest network gateway, which is responsible for interoperability between networks. Different networks are expressed as autonomous systems (AN), with individual autonomous system numbers (ASN).

It's helpful (at least to me) to think of an autonomous system as a "layer two" hierarchy for routing in the internet. A large entity such as a ISP, university, or company that maintains a collection of routers all sharing assigned network address prefixes and routing policies.

Routing protocol specifies how routers communicate with each other. Within IP networks, there are three major classes of routing protocols:

  • Interior Gateway Protocols (distance-vector routing within autonomous systems, ie: RIP)
  • Internet Gateway Protocols (link-state routing within autonomous systems, ie: OSPF)
  • Exterior Gateway Protocols (path-vector routing between autonomous systems, ie: BGP)

There are also different routing schemes, which affect how routers deliver messages:

  • unicast delivers messages to a a single specific node
  • broadcast delivers messages to all nodes in the network
  • multicast delivers messages to a group of interested nodes
  • anycast delivers delivers messages to any one out of a group of nodes
  • geocast delivers message to a group of nodes based on geographic location

Outside of router broadcasting changes to route tables, the most popular schemes for IP networking is unicast (as TCP is unicast oriented, used for www) and multicast (as UDP is multicast oriented, and used for streaming).

Routing Information Protocol (RIP)

RIP is one of the oldest interior protocols, and as such has formed what we consider the standard for local area networks. RIP provides network stability, guaranteeing that the network can adapt to disruption, by using a distance-vector routing algorithm (using a max hop-count) to determine the best path for forwarding packets. Updates to the route table are then broadcast to all neighbors, letting them know of the change. RIP uses UDP as the transport protocol on a reserved port of 520. RIP version 2 (developed in 1993 and adopted as an internet standard in 1998) was a much-needed update which included the ability to use subnet information as well as switching from broadcasting to multicasting the routing table to adjacent routers.

Open Shortest Path First (OSPF)

OSPF is faster than RIP, but also more complex. Instead of a hop count, it uses a link-state routing protocol which is similar to Dijkstra's algorithm in it's calculation of shortest path. This means that instead of only knowing about hops and adjacent routers, OSPF maintains a complete topological database of all connections in the local network. When sharing information OSPF describes connections with neighbors, enabling all neighbors to update link states in their topological network map, enabling each OSPF to construct their own routing table from their calculation of best paths, according to this new data. This is in contrast to RIP, in which the routing tables are directly shared between adjacent nodes.

Border Gateway Protocol (BGP)

BGP is the backbone interoperability protocol. Originally created for Cisco routers They are used to get data from one autonomous system to another, and rely on IPG routers to resolve routes within an autonomous system. BGP routers decide which networks are best suited for forwarding packets to their destination. If an network is congested, BGP routers can send the packet on a detour through a different network, for example.

BGP is similar to RIP in that when a BPG router initially boots up, it first downloads the entire routing table of each neighboring router. If a BPG router decides to update it's own table because it has determined that a new path is better, it will then share this information with all neighboring BGP routers using TCP on reserved port 179. The use of TCP ensures BPG can transmit data securely, which is important since it's not operating within a single autonomous system.