After reading this article you will learn about the function and requirement of routing.
Function of Routing:
The function of a router is to switch messages. Router, which is a generic term used in Wide Area Networks, aids in transferring messages. Routers are specialised computers used to connect two or more transmission lines. When data arrives on an incoming line the switching device must select the outgoing line on which to forward the incoming messages.
Packet-switching nodes and data-switching exchanges are some of the names by which routers are also referred to as.
Routing algorithm is a network layer software responsible for deciding on which output line the incoming packet should be transmitted. If the subnet uses datagram then the decision as to which route to use must be made every time a packet is to be transmitted since the best route may have changed since the last transmission.
ADVERTISEMENTS:
If the subnet uses virtual circuits, the decision needs to be made only when a new virtual circuit is set up, therefore, the subsequent data packets follow the route established for the original packet dispatch. This procedure is sometimes known as session routing because the route remains established for an entire log-in session.
However, regardless of whether a route is selected separately for each packet or for the entire session, there are certain characteristics that remain desirable for all routing algorithms. These are: simplicity, correctness, robustness, stability, fairness and optimality.
Once a major network comes on the air, it is expected to run continuously for several years without system wide failures. During such a long period, there are bound to be hardware and software failures of all kinds. The routing algorithm should be capable of handling changes in topology and traffic without requiring all jobs in all hosts to be aborted and the network to be rebooted whenever some router crashes.
Stability is another important consideration when considering an efficient routing algorithm. There are some routing algorithms that never converge to equilibrium, no matter how long they run. Fairness and optimality, it seems, are goals which are often conflicting and often require compromise so that the result of the routing algorithm may often end up by being sub-optimal.
ADVERTISEMENTS:
Routing algorithms can be of two types:
Non-adaptive algorithms and adaptive algorithms. Non-adaptive algorithms do not base their routing decisions on measurements or estimates of current traffic and topology. Instead the choice of the route to use is computed in advance, off-line, and downloaded to the routers when the network is booted. This sometimes called static routing.
Adaptive algorithms, on the other hand, change their routing decisions, normally, to reflect changes in the topology and traffic.
Adaptive algorithms differ in where they get their information from locally, from adjacent routers or from all routers in the network when they change the routes, that is, every time interval or when the load changes, and what metric is used for optimization; for example, distance, number of hops or estimated transit time. Routing by Adaptive algorithms is sometimes referred to as dynamic routing.
ADVERTISEMENTS:
Routing, normally done in circuit-switched networks, is traditionally static routing strategy using alternate paths to counter increased loads. Modern routing strategies provide more adaptive and flexible algorithms. Routing may be required, however, for packet-switching, frame relay and ATM networks as well.
Requirements of Routing:
Routing in Circuit-Switched Networks:
In large circuit-switching networks such as in long-distance telephone systems, there will be many circuit paths and they will invariably be through more than a single switch. When a call is made, a path through the network between the caller and the recipient must be devised by the network.
This path may pass through many trunks and switches, and it is the function of the network to find a path between the caller and the receiver.
ADVERTISEMENTS:
The main requirements of the strategy for establishing this route are efficiency and resilience. It is important to keep the requirements of the equipment such as switches and trunks at a minimum. But it must be remembered that the equipment must be able to handle the ‘busy hour’ traffic.
The traffic may occasionally overshoot even the peak load and at times there may be a failure of some equipment’s and it is desirable that the network should be available even under some such dire situations. Therefore, the switching strategy may have to be a trade-off between efficiency and resilience.
Traditionally in public telecommunications networks switches were organised in tree structures. A path would be created by starting at the calling subscriber and looking up the nearest tree structure and locating the first common node and then going down the tree to the node that connects to the called subscriber.
In order to create resilience high usage trunks were added that connected exchanges that handled high traffic volumes. This provided both resilience and redundancy.
ADVERTISEMENTS:
However, to cope with high demands the systems have moved away from static routing to dynamic routing. In dynamic routing, routing decisions take care of current traffic conditions.
Typically, circuit- switching nodes have a peer to peer relationship with each other since all nodes are capable of performing identical functions. This makes routing both more complex as well as more flexible. If there are several routes predefined between the caller and each destination, it becomes a function of the originating switch to select appropriate routes for each call.
If there is only one routing sequence defined between each source-destination pair, the scheme is known as a fixed alternate routing scheme. However, generally a dynamic alternate scheme is used. In this case different routing schemes are used for different times of the day because of different traffic conditions.
A simple example of this is shown in Fig. 8.1:
Routing Packet-Switched Networks:
In Packet-Switching Networks, the design of ‘routing’ is an issue of utmost importance. The principles used are also applicable to internetwork routing. The main function of a packet-switched network is to ensure that packets accepted from a source station are delivered to the destination station.
In order to achieve this end, a proper route through the network must be determined and established. Usually several routes are possible and therefore, a routing function must be performed.
The standard requirements to achieve successful routing are:
1. Correctness
2. Simplicity
3. Fairness
4. Optimality
5. Robustness
6. Stability
7. Efficiency
Correctness and Simplicity are self-explanatory. Robustness deals with the requirement that the router must be able to deliver packets in spite of some localised failure—may be through an alternate route.
Normally, the network should be able to take care of situations without losing the packet and/or without breaking the virtual circuit that has been established. Robustness must again be finely balanced against stability since the two requirements may be in competition and the improvement in one may be at the cost of the other. Similarly, a trade-off may have to be made between optimality and fairness.
Several routing techniques involve some processing as well as transmission overheads at each node, thereby affecting network efficiency. Taking these qualities into consideration, we can now note the important elements of routing techniques in Packet-switched networks that must be taken into account while designing the routing strategy.
These elements are:
1. Performance Criteria
2. Decision Time
3. Decision Place
4. Network Information Source
5. Network Information Update Timing
We can now proceed to discuss some salient points about some of these elements.
Performance Criteria:
An important consideration in route selection is often to choose the route that passes through the minimum number of nodes, often called the minimum-hop route. We are trying to avoid this nomenclature so that the student does not get confused with the “double hop” technique used in VSATs.
This is an easily measured criterion and will, obviously, minimise the usage of network resources. A generalisation of this is the least cost route. An example is given in Fig. 8.2.
As an example, the cost could be inversely related to the data rate since ‘the higher the data rate, the lower the cost of the link’.
The least cost could maximise the throughput and therefore, could minimise the delay. In either approach—that is, the minimum hop or least cost—the algorithm for determining the optimum route is reasonably simple and therefore, the processing time for the computation is approximately the same.
But the least cost criterion is more flexible and is, therefore, more commonly, used compared to the minimum hop criteria. Several least routing cost algorithms are in common use. The shortest path from node 1 to node 6 is 1-3-6 where the cost is 5 + 5 = 10, but the least cost path is 1-4-5-6 where the cost is 1 + 1 + 2 = 4. Costs are assigned to each link to achieve some design objective.
Decision Time and Place:
Decision time will depend upon whether the routing decision is to be made on routing a packet or on deciding on a virtual circuit in use. If it is the case of routing a datagram, the routing decision is made individually for a packet. In case of a virtual circuit, the routing decision is made at the time of establishing the virtual circuit.
In simple cases, all subsequent packets using this virtual circuit follow the route used by the earlier packets. In sophisticated networks, the route may be dynamically altered for a virtual circuit depending upon changing conditions—such as a failure of a portion of the network or even an overload.
Decision place is an independent design variable for design of the routing scheme. It refers to the nodes in the network responsible for routing decisions.
In “Distributed Routing“—very commonly used—each node has the responsibility of selecting an output link an output line for forwarding packets as they arrive. In case of centralised routing, the decision is made by only some designated node such as a network control centre.
There are obvious advantages as well as disadvantages of the centralised routing scheme, the prominent one being the fact that the loss of the network control centre may block the operations of the entire network and therefore, it does not have adequate fault tolerance.
Consider once again Fig. 8.2 and assume that distributed routing is used and the values of costs are as shown in the figure at any given instant. But costs may change and if a packet is to be sent from node 1 to node 6, the route 1-4-5-6 may be used with each leg of the route being determined locally by the transmitting node.
Now if the values change, 1-4-5-6 may no longer be the best route. In a datagram packet, the next packet may follow a different route determined by each local node. In case of a virtual circuit network, the previous route is remembered by each node and that will continue to be followed.
Network Information Source and Update Timing:
It must be obvious by now that knowledge of the topology of the network, link cost and the traffic load appear necessary for the router to operate efficiently. However, there are some strategies that operate without this knowledge and still manage to push packets through. Flooding and a few other strategies belong to this class.
Where decisions are made by each node, such as in distributed routing, the node uses only local information—for example, the cost of each outgoing link. Some information might also be collected from adjacent nodes, particularly about the congestion at the adjacent load.
There are also algorithms’ that obtain information from all likely nodes in the prospective route. In case of centralised routing, the master central node makes use of information from all the available nodes. Another important concept is that of the timing of information update.
If no information is to be used, this concept obviously does not matter. If only local information is to be used, the update is a continuous process. For all other information sources, update timing will depend upon what routing strategy is being used. In case the strategy is of fixed routing, the information is never updated.
In case the routing strategy is adaptive, the information requires to be updated more frequently so that the routing decision can be adapted to changing conditions. Obviously, the more the information available, the more will be the frequency of the update and the better will be the routing decision.