Routing architecture
A routing architecture is the system of how paths across communication networks are decided.
There are 3 basic approaches:
- Manual - a human configures the switching nodes
- Centralized - an algorithm running on a central computer in the network control center does path selection for all source-destination pairs, and installs them in the switching nodes
- Distributed - the switching nodes cooperate to select paths
Generally, especially in a large network, the latter is the only one which will scale, and it is now used everywhere (although the telephone network started with manual path selection).
Characterization of Distributed Routing Architectures
There are two orthogonal fundamental axes which can be used to characterize distributed routing architectures.
The first is 'path selection', which describes how paths are selected; this is actually a spectrum, along which are a large number of more complex alternatives to the approaches on each end. Paths can be selected either:
- Fully distributed - each node along the path makes a completely independent decision as to which node user traffic will go through next; this is sometimes called hop-by-hop (HbH) path selection.
- Explicit: one node selects the entire path.
The term source routing is sometimes used for one form of the latter, in which the host sending the packet computes the entire route, which is then included in every packet.
The second major axis is 'data types', which described what kind of data is being passed between the nodes:
- Destination Vector (DV) - nodes pass sets of (destination, information) n-tuples (i.e. basically, routing tables) to immediate neighbours.
- Map Distribution (MD) - nodes distribute information about their immediate surroundings through the network; this information is used to construct maps of the network.
Destination Vector used to be called Distance Vector, but it was changed after the invention of Path Vector as a method for preventing routing loops; the new term was picked to allow retention of the acronym.
Classification of Distributed Routing Architectures
These two orthogonal axes define a 4-way classification of routing architectures, one which is not, however, fully populated. The three main classes of routing architecture (along with examples of each), are:
DV-HbH - the classic initial routing architecture; used in:
MD-HbH - a newer routing architecture, used in:
MD-E - the direction of past research in advanced routing, and the likely future direction of routing work. Some examples include:
- IDPR (RFC-1478, 1993) - The first MD-E routing architecture, mostly for Inter-AS (EGP) applications.
- Nimrod (RFC-1992, 1996) - A follow-on to IDPR, enhanced to take over both the EGP and IGP functionality, and with better tools for doing and managing abstraction.
- PNNI - For ATM, based on Nimrod.
