RIP, OSPF and BGP overview

Why it exists

The Internet is a network of networks run by different organisations, and one routing algorithm cannot serve all of them. Inside one organisation (an autonomous system, AS) the goal is the best path, and everyone cooperates: an intra-domain or interior gateway protocol (IGP) such as RIP or OSPF. Between organisations the goal is also policy (who may carry whose traffic, at what price), so a different protocol, BGP, runs between ASes. GATE asks which protocol uses which algorithm, which transport carries it, what metric it uses, and a few numbers.

Prerequisites

You need the two algorithms behind them: distance vector routing (Bellman-Ford, with the count to infinity and its fixes) and link state routing (flooding and Dijkstra).

Precise definitions

Autonomous system. A set of networks and routers under one administration with one routing policy, identified by an AS number. Routing inside an AS uses an interior protocol (RIP, OSPF, IS-IS); routing between ASes uses the exterior protocol BGP.

RIP (Routing Information Protocol). A distance vector protocol.

• Metric: hop count; every link costs 1; 16 means infinity (unreachable), so a RIP network can be at most 15 hops across, which also limits the count to infinity.
• Each router sends its whole table to its neighbours about every 30 seconds in UDP datagrams to port 520 (so RIP is an application of UDP). A message has a 4-byte header and up to 25 routes of 20 bytes each: 504 bytes of data.
• A route not heard for 180 seconds is marked unreachable and removed after a further 120 seconds.
• Uses split horizon (with poisoned reverse) and triggered updates against the count to infinity (see the distance vector page). Slow convergence; simple; suited to small networks.

OSPF (Open Shortest Path First). A link state protocol.

• Each router describes its own links and costs in a link state advertisement (LSA), which is flooded to all routers of its area; every router then holds the same map and runs Dijkstra's algorithm on it to build its routing table.
• Metric: a cost per interface, set by the administrator, often derived from the bandwidth: many routers use $\text{cost} = \lfloor 10^8 / \text{bandwidth in bit/s} \rfloor$, at least 1 (10 Mbps: 10; 100 Mbps and faster: 1). A path costs the sum of the costs of its links.
• Messages are carried directly in IP datagrams (protocol number 89): not TCP, not UDP. Neighbours exchange Hello packets (every 10 s on a broadcast network; a neighbour silent for 40 s is dead).
• Hierarchy: a large AS is divided into areas, all joined by the backbone area 0, to limit the flooding. Routers between areas summarise.
• On a broadcast LAN the routers elect a designated router (DR) and a backup (BDR): highest priority wins, ties go to the highest router ID, priority 0 is never elected. Every other router forms an adjacency only with the DR and the BDR, so n routers have $2n - 3$ adjacencies instead of $n(n-1)/2$.
• Faster convergence than RIP, no count to infinity (every router knows the whole map), supports CIDR and several equal-cost paths; more memory and computation.

BGP (Border Gateway Protocol). The inter-domain protocol, a path vector protocol.

• Neighbouring routers (peers) keep a TCP connection on port 179 and send updates over it: BGP is reliable by using TCP.
• A route to a prefix carries the AS path: the list of ASes it has crossed. A router adds its own AS number when it passes a route on and rejects any route whose AS path already contains its own number: that prevents loops (the way the count to infinity is avoided).
• Policy first. A router does not simply take the shortest path. Typically an AS prefers a route through a customer (who pays) to one through a peer (free) to one through a provider (costs money), and then the shortest AS path; and it advertises routes learned from a peer or provider only to customers, so that it does not carry traffic for free. The attributes (local preference, AS path length, and others) decide.
• eBGP runs between ASes, iBGP between routers inside one AS. BGP routes CIDR prefixes and can aggregate them. It converges slowly and values stability.

How it works

RIP's message size. A table of $n$ routes needs $\lceil n/25 \rceil$ messages of at most 504 bytes.

OSPF's cost. The 100 Mbps reference makes every fast interface cost 1.

The metric matters. One network, two metrics: RIP counts hops, OSPF adds up costs. To R4 the two-hop path through two slow 10 Mbps links wins for RIP; the three-hop path over fast links wins for OSPF.

Electing the designated router.

BGP as a path vector. Round by round the best AS path to the prefix of AS 5 spreads outward; every AS puts its own number in front, and a path that already contains the number of the receiver would be refused.

Policy beats length. AS 3 prefers the longer route through its customer to the shorter one through its peer.

Worked examples

#include <stdio.h>
 
#define N 5
#define INF 1000000
 
static const long bw[N][N] = {                       /* bit/s, 0 = no link; routers R1..R5 are 0..4 */
    {0, 10000000, 1000000000, 0, 0},
    {10000000, 0, 0, 10000000, 0},
    {1000000000, 0, 0, 0, 100000000},
    {0, 10000000, 0, 0, 100000000},
    {0, 0, 100000000, 100000000, 0}};
 
static long cost_of(long b) { long c = 100000000L / b; return c < 1 ? 1 : c; }   /* reference bandwidth 100 Mbps, at least 1 */
 
static void shortest(int hops) {
    long dist[N], prev[N];
    int done[N] = {0};
    for (int i = 0; i < N; i++) { dist[i] = INF; prev[i] = -1; }
    dist[0] = 0;
    for (int round = 0; round < N; round++) {
        int u = -1;
        for (int i = 0; i < N; i++)
            if (!done[i] && (u < 0 || dist[i] < dist[u])) u = i;
        done[u] = 1;
        for (int v = 0; v < N; v++) {
            if (!bw[u][v]) continue;
            long w = hops ? 1 : cost_of(bw[u][v]);
            if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; prev[v] = u; }
        }
    }
    int path[N], len = 0;
    for (int x = 3; x >= 0; x = (int)prev[x]) path[len++] = x;
    printf("%s: R1 to R4 costs %ld via", hops ? "RIP (hops)" : "OSPF (cost)", dist[3]);
    for (int i = len - 1; i >= 0; i--) printf(" R%d", path[i] + 1);
    printf("\n");
}
 
int main(void) {
    printf("OSPF costs: 10 Mbps %ld, 100 Mbps %ld, 1 Gbps %ld, T1 (1.544 Mbps) %ld\n", cost_of(10000000), cost_of(100000000), cost_of(1000000000), cost_of(1544000));
    shortest(1);
    shortest(0);
    return 0;
}

OSPF costs: 10 Mbps 10, 100 Mbps 1, 1 Gbps 1, T1 (1.544 Mbps) 64
RIP (hops): R1 to R4 costs 2 via R1 R2 R4
OSPF (cost): R1 to R4 costs 3 via R1 R3 R5 R4

#include <stdio.h>
 
int main(void) {
    int routes[4] = {10, 25, 26, 60};
    for (int i = 0; i < 4; i++) {
        int n = routes[i], messages = (n + 24) / 25, bytes = 4 * messages + 20 * n;
        printf("%3d routes: %d message%s, %d bytes of RIP data in all; the last message has %d bytes\n", n, messages, messages > 1 ? "s" : "", bytes, 4 + 20 * (n - 25 * (messages - 1)));
    }
    return 0;
}

 10 routes: 1 message, 204 bytes of RIP data in all; the last message has 204 bytes
 25 routes: 1 message, 504 bytes of RIP data in all; the last message has 504 bytes
 26 routes: 2 messages, 528 bytes of RIP data in all; the last message has 24 bytes
 60 routes: 3 messages, 1212 bytes of RIP data in all; the last message has 204 bytes

Cheat box

Traps and GATE patterns

Connections

RIP is distance vector routing made into a protocol (and an application of UDP); OSPF is link state routing; BGP rides on TCP and routes the aggregated prefixes of CIDR. The count to infinity that limits RIP to 15 hops is why BGP carries paths instead of distances.

PYQs

Consider the routing protocols given in List-I and the
names given in List-II:

List-I
List-II
(i) Distance vector routing (a) Bellman-Ford
(ii) Link state routing
(b) Dijkstra

For matching of items in List-I with those in List-II,
which ONE of the following options is CORRECT?

A machine receives an IPv4 datagram. The
protocol field of the IPv4 header has the protocol
number of a protocol X.
Which ONE of the following is NOT a possible
candidate for X?

Which
of
the
following
statements
is/are
INCORRECT about the OSPF (Open Shortest Path
First) routing protocol used in the Internet?

Consider the following statements about the
functionality of an IP-based router.
I. A router does not modify the IP packets during
forwarding.
II. It is not necessary for a router to implement any
routing protocol.
III. A router should reassemble IP fragments if the
MTU of the outgoing link is larger than the size of
the incoming IP packet.

Which of the above statements is/are TRUE?

Consider the following statements about the
routing protocols, Routing Information Protocol
(RIP) and Open Shortest Path First (OSPF) in an IPv4
network.

I. RIP uses distance vector routing
II. RIP packets are sent using UDP
III. OSPF packets are sent using TCP
IV. OSPF operation is based on link-state routing
protocol

Which of the statements above are CORRECT?

Which one of the following is TRUE about the
interior gateway routing protocols - Routing
Information Protocol (RIP) and Open Shortest Path
First (OSPF)?

Packets of the same session may be routed through
different paths in:

Self-check

Revision card

References