Better to know some
... than all
Routing is the task of selecting a path for the transport of packets across the network, and is one of the most important functions of the network layer. Routing is generally viewed as an optimization problem with the objective of choosing an optimal path according to certain criteria:
* Transmission cost (measured in terms of tied up network resources).
* Transmission delay (measured as the delay involved in delivering each packet).
* Throughput (measured as the total number of packets delivered per unit of time).
The overall cost depends on all these three, and an optimal route is one that minimizes the overall cost. This can be represented by a weighted network, where an abstract cost figure is associated with each link. The cost of a route is the sum of the cost of its links. There are three classes of routing algorithms:
* Static Routing
* Dynamic Routing
Of these, only dynamic routing makes any serious optimization attempts. In flooding, every possible path between the source and the destination station are exercised. Each node, upon receiving a packet, forwards copies of it to all its neighboring nodes (except the one from which it received the packet). Flooding is a highly robust technique since it offers the best chance of at least one packet copy reaching the destination. Its major disadvantage, however, is that it quickly congests the network. To avoid packets being indefinitely copied, each packet is assigned a limited lifetime which when expired will cause it to be destroyed.
Because of its limitations, use of flooding is confined to specialized applications that require very high levels of robustness (e.g., military networks). Flooding is only suited to the datagram approach.
In static routing, a fixed routing directory is used to guide the selection of a route which remains unchanged for the duration of the connection. The directory consists of a table which for each node pair (p,q) in the network suggests a partial path by nominating the first intermediate node, r, along the path. This should be interpreted as 'to get from p to q, first go to r'. The path can then be continued by looking at the entry for the pair (r, q), etc., until q is reached.
The route directory is tied to the network topology and remains unchanged unless the network topology changes. The route directory may be stored in a central location or distributed amongst the nodes (each node requires its corresponding row only). The directory should remain accessible to network administrators for manual updates. The advantages of static routing are its simplicity and ease of implementation. Its disadvantage is lack of flexibility in face of possible variations within the network. Static routing can be used with both the datagram and the virtual circuit approach. Although static routing takes some form of cost into account, these cost measures are fixed and predetermined. Variations in traffic load have no impact on route selection, which makes this method unsuitable for large networks with significant traffic fluctuations. For small networks with relatively constant traffic, however, static routing can be very effective.
Dynamic routing attempts to overcome the limitations of static routing by taking network variations into account when selecting a route. Each node maintains a route directory which describes the cost associated with reaching any other node via a neighboring node. The nodes periodically calculate estimates for the costs of the links to their neighboring nodes according to the statistical data that they have collected (queue lengths, packet delays, traffic load, etc.), and share these estimates with other nodes. This enables the nodes to update their route directories in an objective manner so that they reflect the current state of the network. To select a route between two stations, dynamic routing employs a graph optimization algorithm to find an optimal (or close to optimal).
The advantage of dynamic routing is its potential to improve performance and reduce congestion by choosing more optimal routes. Its disadvantage is its inherent complexity. Nevertheless, dynamic routing algorithms enjoy widespread use because they have proved to be generally more effective than other algorithms. Like static routing, dynamic routing can be used with both the datagram and the virtual circuit approach.
The contents of the fields with darker shading vary according to the Packet Type, and may be altogether absent from some packets.
Because packet headers may vary in length, the Header Length field is needed to indicate where User Data starts. Each packet is assigned a limited lifetime denoted by the Lifetime field. This is an integer quantity and is decreased in value by the nodes that handle the packet. When this value reaches zero, the packet is discarded. This is intended as a measure against congestion by packets that aimlessly circulate the network.