The main function of the 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 routes and the data structures that they use are a major area of network layer design.

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

The routing algorithm is that part of the network layer software responsible for deciding which line 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: nonadaptive and adaptive. Nonadaptive 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 in advance, off-line, and downloaded to the routers when the network is booted.

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 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.).