Two categories of protocol exist at the network layer: routed and routing.
A routed protocol is a Network Layer protocol that is used to move traffic between networks. Routed protocols allow a host on one network to communicate with a host on another, with routers forwarding traffic between the source and destination networks. IP, IPX, and AppleTalk are all examples of routed protocols.
Routing protocols let routers route routed protocols after a path has been determined. RIP, IGRP, EIGRP, OSPF, IS-IS, BGP are all examples of routing protocols.
The routing protocols can be classified in 2 ways:
- Based on the algorithms: Distance vector or Link-state
- Based on the “extension“: IGP or EGP
Distance vector versus link state
Distance vector algorithms use the Bellman-Ford algorithm. This approach assigns a number, the cost, to each of the links between each node in the network. Nodes will send information from point A to point B via the path that results in the lowest total cost (i.e. the sum of the costs of the links between the nodes used).
The algorithm operates in a very simple manner. When a node first starts, it only knows of its immediate neighbours, and the direct cost involved in reaching them. Each node, on a regular basis, sends to each neighbour its own current idea of the total cost to get to all the destinations it knows of. The neighbouring node(s) examine this information, and compare it to what they already ‘know’; anything which represents an improvement on what they already have, they insert in their own routing table(s). Over time, all the nodes in the network will discover the best next hop for all destinations, and the best total cost.
When one of the nodes involved goes down, those nodes which used it as their next hop for certain destinations discard those entries, and create new routing-table information. They then pass this information to all adjacent nodes, which then repeat the process. Eventually all the nodes in the network receive the updated information, and will then discover new paths to all the destinations which they can still “reach”. Examples of distance vector protocols are RIP, IGRP, EIGRP.
When applying link state algorithms, each node uses as its fundamental data a map of the network in the form of a graph. To produce this, each node floods the entire network with information about what other nodes it can connect to, and each node then independently assembles this information into a map.
Using this map, each router then independently determines the least-cost path from itself to every other node using a standard shortest paths algorithm such as Dijkstra’s algorithm. The result is a tree rooted at the current node such that the path through the tree from the root to any other node is the least-cost path to that node. This tree then serves to construct the routing table, which specifies the best next hop to get from the current node to any other node. An example of link state protocol is OSPF.
IGP versus EGP
An IGP (Interior Gateway Protocol) is a protocol for exchanging routing information between gateways within an autonomous network. RIP, EIGRP, OSPF are examples of IGPs.
Exterior Gateway Protocol (EGP) is a protocol for exchanging routing information between two neighbor gateway hosts in a network of autonomous systems. EGP is commonly used on the Internet to exchange routing table information. The most important EGP is BGP. The Border Gateway Protocol (BGP) is the core routing protocol of the Internet. It works by maintaining a table of IP networks or ‘prefixes’ which designate network reachability among autonomous systems (AS).