IP networks communicate with each other using L3 devices named routers. A router has a table that tells itself how to reach a given network; i.e., if it has to communicate with another router or if it is directly attached to it. Obviously, these tables need to be filled with accurate information, a thing that can be done in two ways:
  • Static routing: The network administrator manually fills in the required data in each router and/or host. This is tedious to do but is enough on (very) little networks. For bigger networks, this does not scale.
  • Dynamic routing: The routing tables are automatically filled in by routing protocols, which are executed by the routers themselves. These are what concerns us in this post, which aims to provide a little overview of their classification.
A routing protocol defines a set of rules and messages — in the typical sense of a network protocol — that allow routers to communicate with each other and make them automatically adapt to topology changes in the network. For example, when a new network is added, all routers will be notified to add an appropriate entry to their routing table, so that they can reach it; imagine something similar when a network becomes unavailable.

We can classify these routing protocols in two major groups:
  • Distance vector protocols: As the name implies, this protocol calculates a distance between two given routers. The metric used in this measure depends on the protocol used. For example, RIP counts the number of hops between nodes. (This contrasts withe OSPF, which uses a per-link cost which might be related to, e.g., its speed. Please note that OSPF is not a distance vector protocol; I'm mentioning it here to show that this difference in metrics can cause problems if you reinject routes between networks that use different protocols.)

    Another thing that differentiates these protocols is that the routers periodically send status messages to their neighbours. On some special cases, they may send a message as a result of an event without waiting for the specified interval to pass.
  • Link state protocols: These protocols monitor the status of each link attached to the router and send messages triggered by these events, flooding the whole network. Another difference is that each router keeps a database that represents the whole network; from this database, it's then able to generate the routing table using an appropriate algorithm (such as Bellman-Ford or Dijkstra) to determine the best path. These include OSPF, BGP and IS-IS.
At last, we can also classify these protocols in two more groups:
  • Interior routing protocols: These are used inside autonomous system (AS) to maintain the tables of their internal routers. These protocols include OSPF and RIP.
  • Exterior routing protocols: Contrary to the previous ones, these are used to communicate routing rules between different ASs. And why are they not the same as the previous ones? Because they use very different metrics to construct the routing table: they rely on contracts between the ASs to decide where to send packets, something that cannot be taken into account with interior protocols. We can include BGP in this group.
Edit (23:47): As Pavel Cahyna kindly points out, OSPF is not a distance vector protocol. The error has splipped in because I wanted to state something but that confused me and didn't put it in the correct group. The paragraph has been reworded.