Routing Protocols

An Internet is a combination of networks connected by routers. When a datagram goes from a source to a destination, it will probably pass through many routers until it reaches the router attached to the destination network. A router chooses the route with the shortest metric. The metric assigned to each network depends on the type of protocol.

The Routing Information Protocol (RIP) is a simple protocol which treats each network as equals. The Open Shortest Path First (OSPF) protocol is an interior routing protocol that is becoming very popular. Border Gateway Protocol (BGP) is an inter-autonomous system routing protocol which first appeared in 1989.

Routing Information Protocol (RIP)

The Routing Information Protocol (RIP) is a protocol used to propagate routing information inside an autonomous system. Today, the Internet is so large that one routing protocol cannot handle the task of updating the routing tables of all routers. Therefore, the Internet is divided into autonomous systems.

An Autonomous System (AS) is a group of networks and routers under the authority of a single administration. Routing inside an autonomous system is referred to as interior routing. RIP and OSPF are popular interior routing protocols used to update routing tables in an AS.

Routing between autonomous systems is referred to as exterior routing. RIP is a popular protocol which belongs to the interior routing protocol. It is a very simple protocol based on distance vector routing, which uses the Bellman–Ford algorithm for calculating routing tables.

A RIP routing table entry consists of a destination network address, the hop count to that destination and the IP address of the next router. RIP uses three timers: the periodic timer controls the advertising of the update message, the expiration timer governs the validity of a route, and the garbage collection timer advertises the failure of a route. However, two shortcomings associated with the RIP protocol are slow convergence and instability.

Open Shortest Path First (OSPF)

The Open Shortest Path First (OSPF) is a new alternative to RIP as an interior routing protocol. It overcomes all the limitations of RIP. Link-state routing is a process by which each router shares its knowledge about its neighbourhood with every other router in the area.

OSPF uses link-state routing to update the routing tables in an area, as opposed to RIP which is a distance-vector protocol. The term distance-vector means that messages sent by RIP contain a vector of distances (hop counts). In reality, the important difference between two protocols is that a link-state protocol always converges faster than a distancevector protocol.

OSPF divides an autonomous system (AS) in areas, defined as collections of networks, hosts and routers. At the border of an area, area border routers summarise information about the area and send it to other areas. There is a special area called the backbone among the areas inside an autonomous system.

All the areas inside an AS must be connected to the backbone whose area identification is zero. OSPF defines four types of links: pointto- point, transient, stub and virtual. Point-to-point links between routers do not need an IP address at each end. Unnumbered links can save IP addresses.

A transient link is a network with several routers attached to it. A stub link is a network that is connected to only one router. When the link between two routers is broken, the administration may create a virtual link between them using a longer path that probably goes through several routers.

A simple authentication scheme can be used in OSPF. OSPF uses multicasting rather than broadcasting in order to reduce the load on systems not participating in OSPF. Distance-vector Multicast Routing Protocol (DVMRP) is used in conjunction with IGMP to handle multicast routing.

DVMRP is a simple protocol based on distance-vector routing and the idea of MBONE. Multicast Open Shortest Path First (MOSPF), an extension to the OSPF protocol, adds a new type of packet (called the group membership packet) to the list of link state advertisement packets. MOSPF also uses the configuration of MBONE and islands.

Border Gateway Protocol (BGP)

BGP is an exterior gateway protocol for communication between routers in different autonomous systems. BGP is based on a routing method called path-vector routing. Refer to RFC 1772 (1991) which describes the use of BGP in the Internet. BGP version 3 is defined in RFC 1267 (1991) and BGP version 4 in RFC 1467 (1993).

Path-vector routing is different from both distance-vector routing and link-state routing. Path-vector routing does not have the instability nor looping problems of distance-vector routing. Each entry in the routing table contains the destination network, the next router and the path to reach the destination.

The path is usually defined as an ordered list of autonomous systems that a packet should travel through to reach the destination. BGP is different from RIP and OSPF in that BGP uses TCP as its transport protocol. There are four types of BGP messages: open, update, keepalive and notification.

BGP detects the failure of either the link or the host on the other end of the TCP connection by sending a keepalive message to its neighbour on a regular basis.