Introduction

The main function of the IP network layer is routing packets from the source machine to the destination machine. In most subnets, packets will require multiple hops to make the journey. The algorithms that choose the most optimum route to forward a packet on, and the data structures that they use, are a major area of network layer design.

The figure below shows a typical subnet structure, or topology. The nodes are the individual hosts on the network.

Subnet array

Figure 1: Subnet array

A routing algorithm is the part of the network layer software responsible for deciding which outgoing port an incoming packet should be transmitted on. If the subnet uses datagrams internally, this decision must be made anew for every arriving data packet since the best route may have changed since last time. If however virtual circuits are being used, routing decisions are made only when new virtual circuits are set up.



Regardless of the case, there are certain properties that are desirable in a routing algorithm: correctness, simplicity, robustness, stability, fairness and optimality.

  • Correctness and simplicity mean that the algorithm should be conceptually simple and error-free.
  • Robustness implies that the algorithm should work irrespective of any change in the topology of the network or the failure of any network device.
  • Stability means that the algorithm should not turn unstable no matter how complicated the routing equation.
  • Fairness and optimality means that the algorithm should be non-discriminatory towards traffic of any particular type(s) or originating from any particular source(s), while at the same time taking efficient routing decisions that extract the best throughput from the network.

Routing algorithms can be grouped into two major classes: non-adaptiveand adaptive. Non-adaptive algorithms do not base their routing decision on measurements or estimates of the current traffic and topology. Instead, the choice of the route to use to get from node I to node J (for all I and J) is computed off-line in advance and downloaded to the routers when the network is booted, and remains static as long as the router is up.

Adaptive algorithms, in contrast, change their routing decisions according to changes in the topology, and usually the traffic as well. Adaptive algorithms differ in where they get their information from (i.e. from only neighbouring routers or from all routers), when they change the routes (i.e. with change in traffic load or with change in topology), and what metric is used for optimization (e.g. distance, number of hops, transit time etc.).