Hierarchical routing (iBGP, eBGP, OSPF, RIP)

Motivation

We communicate from our house to somewhere distant. In order for this to happen, we need to determine exactly which routers have to be trodden to get from our host to the other host. Routing algorithm determines the path. We also want the algorithm to provide the most efficient path to get from one host to another.

 

The easiest way to do this is to see the network as a single, giant graph, composed of nodes (routers, hosts) and edges (links with cost). Then, we can use our well-known algorithms such as dijkstra's algorithm and bellmanford algorithm to compute the path with the least cost to get from one node to another. However, this is not used for two reasons:

 

1. the graph is too big, hence there is a way too high overhead in communicating information (in dijkstra's algorithm, each router needs to know every link cost, as well as the topology of the whole graph, and bellmanford requires continual communication of distance vector). 

 

2. routers are owned by different network providers (Vodafone, 2Degrees...). When the algorithm computes efficient path between two hosts that are not customer of, say, Vodafone network provider, then Vodafone simply doesn't want to waste its bandwidth to serving customers of other network - it would want some way of saying 'no don't cross my routers'.

 

Solution - hierarchical routing

The solution to this is hierarchical routing. We can conceptualize it as routing mechanism that, instead of seeing the network as one giant graph, sees the network as a collection of router groups, that are thinly connected to each other. Each router group is called AS (autonomous systems).

How does this solve the two issues outlined above? We would firstly need to establish a few facts to answer that. So bear me a little before I get to that. Two important questions to raise here are: how do we compute the path from a router in one AS to another router in the same AS? how do we compute path from a router in one AS to another router in different AS?

 

Hierarchical routing mechanism

Question 1: how do we compute the path from a router in one AS to another router in the same AS?

Each router in one AS knows the least-cost path to any other router in the same AS. Each least-cost path is computed by bellman-ford or dijkstra's algorithm, and the messages to fascilitate this are carried through RIP and OSPF protocol. Note, this also means that each router has a forwarding table entries to routers in same AS. 

 

Question 2: how do we compute path from a router in one AS to another router in different AS?

Imagine that we have a router Y (1a in the diagram) in AS1 that wants to send a packet to a router called X in AS3.

First step: Y needs to know which AS it can forward its packet to in order to reach X. NOTE: this doesn't mean it needs to know the least cost path.

Before Y sends a packet to X, X needs to tell Y what AS's need to be trodden in order to get to AS3. BGP does this. Note BGP is not concerned with efficient path calculation - it's just an advertisement method. A gateway router (router at the edge of one AS) in AS3 can send a message [AS3, X] to a gateway router in AS2 to say that X is reachable through AS3. This advertisement between gateway routers is done through eBGP protocol.

 

Then, that AS2 gateway router needs to tell all the other routers in AS2 about this reachability fact [AS3,X]. This is done through iBGP protocol, whereby one router can send a message to any other router, directly in the same AS. AS2 gateway router that connects to AS1 gateway router will want to advertise to AS1 that it can relay packet to AS3, then in turn to X. Therefore, it sends [AS2, AS3, X] advertisement message to gateway router of AS1. AS1 gateway router now knows that if it sends a packet to AS2, a packet can be sent to X. AS1 gateway router then advertises this message [AS2, AS3, X] to every router via iBGP protocol, where Y is one of them to receive this message. Now, Y knows that it can reach X by forwarding packet to AS2! We call this 'advertisement message' as prefix.

 

Second step: Now that Y knows [AS2, AS3, X], it will send a packet to AS2

This requires transfer of packet from Y to gateway router of AS1. This has already been computed through OSPF or RIP (depends on policy of that AS), so we already know the least cost path from Y to AS1 gateway router.

- Then the packet just flies from AS1 gateway router to AS2 gateway router. 

- Then that left AS2 gateway router can forward packet to right AS2 gateway router following the least cost path computed by OSPF or RIP

 - ...so on until the packet gets to X.

Hierarchical routing mechanism - complication, and hot potato routing

What if a router that wants to send a packet to a router in a distant AS receives multiple prefixes? The answer is, use the prefix that requires least cost for packet to get to the gateway router. Below, imagine that 2d wants to send a message to X. 2d received two prefixes to X. 2d will choose to use [AS1,AS3,X] to get to X, just because the packet needs to travel with cost of 201, whereas the alternative will cost 263. This is called hot potato routing.

Circling back to our original motivation

The reason we even considered entering into this discussion were the following issues. Let's address how each issues have been addressed.

 

1. the graph is too big, hence there is a way too high overhead in communicating information 

Hierarchical routing saves table size, reduces update traffic, because these OSPF, RIP are constrained to local graph (AS).

 

2. routers are owned by different network providers (Vodafone, 2Degrees...). each provider network would want some way of saying 'no don't cross my routers'.

Simply don't advertise prefix to network that doesn't serve its customers. For example, below, A will advertise [A,W] to B. However, B won't advertise [B,A,W] to C, because its customer (X) can already use the network to communicate with W, and advertising prefix to C only helps Y to communicate with W, but that communication is obviously not the kind of traffic that it wants to waste its bandwith for.

 

Some explanation about RIP and OSPF

Thus far, we referred to RIP and OSPF as protocols that would have already computed least cost paths between any two routers in one AS. That's exactly right. But we can also learn how these are implemented. 

[TODO: add RIP/OSPF mechanism]