Optimal routeing in the Internet
Computer networking is the most happening area in the so-called digital era that we are living. Devices and drivers are becoming obsolete in the wink of an eye, and there is everlasting thirst for evolution and keep ourselves updated.
Optimisation of the routeing process is one such aspect which can enhance the performance and reduce the cost of networking, thereby assuring a pleasant experience to its users. Switches and routers are the keys to form a good network.
This article explores various aspects about the routeing optimisation.
Routeing: A router is a decision-making device/software, as to where the data packets need to be forwarded through various links, towards their destination, based on its routeing table and algorithms. In addition to selecting an optimal path, a router is also concerned with securely transmitting the data to its next node.
The routeing function is associated with the layer-3 of standard OSI network model and has ample contribution it's performance.
Some of the performance criteria that need to be optimised are throughput, delay, simplicity, low overhead, reliability/stability, and flexibility.
Shortcomings of existing routeing schemes: Current routeing methods such as Dijkstra's Algorithm, Distance Vector algorithm, Hierarchical routeing in the IP backbone are not up to the mark in the sense that, many of them use hop-counts and artificial weights given to the links in for deriving the routeing tables. These techniques being artificial in nature hamper the optimisation process. Most algorithms suffer from drawbacks such as possible oscillations, computational complexity, and convergence problems and are unable to perform when router malfunctions. On the other hand, studies reveal that some routeing protocols (like BGP: Border Gateway Protocol) are prone to failures in communication links and need several minutes to converge.
In general, we model a network as a set of nodes interconnected by links. A node can have multiple links to one another. The cost factor for any network is determned based on certain factors such as bandwidth and power consumption.In 1974, Cantor and Gerla proposed this as a convex optimisation problem and used separation techniques to overcome them. In 1977, Gallager proved the necessary and sufficient conditions for having a minimum-delay routeing and introduced a distributed multi-path routeing. None of these methods are used because of their complexity, low performance of processors and low link capacity at the time these methods were proposed
Ways of achieving optimal routeing: The ideas mentioned here are with the assumption that the reader is familiar with some basic routeing algorithms and quantitative descriptions of various performance measures. The mathematical descriptions of the algorithms are too detailed to describe within the scope of this article. However a brief idea is presented.
1. HALO: Hop-by-Hop Adaptive Link-State Optimal Routeing [2]: This first link-state, hop-by-hop routeing algorithm which addresses the traffic engineering problem for intradomain routeing on the Internet. Furthermore, based on feedback information from the link-state updates, the protocol automatically adjusts to input data traffic. The router split ratio adjusts accordingly.
2. Optinets [3]: This architecture takes into consideration all entities involved in a network mobility and attempts to decentralize the mobility management efforts, instead of putting the burden on a single entity of the architecture. It provides means for all type of mobile network node to transmit data to corresponding nodes using optimal routes.
3. Cut-through routeing [4]: The cut-through routeing deals with the concept of message splitting to a maximum extent. In doing so, a node can convey the part of the data without waiting for the entire packet to be received. If there is no additional traffic on the path, the delay of packet delay is equal to the sum of propagation delay and time taken for slowest link data transmission, no matter how many links are present on the path. Thus, delay can be reduced by as much as a factor of n on a path with n links.
4. Hot potato (deflection) routeing schemes [4]. In limited space networks, it is important to modify the routeing algorithm to minimise buffer overflow and the attendant loss of packets. The idea here is for nodes to send their stored packets as soon as possible, transmitting them on idle channel even if it is not close to destination thus reducing the delay in transmission.
5. Optimal trafficking [5].
Another way of optimisation can result if the information flow results along the minimum first derivative length [MFDL] [4]. Thus the currently existing sub-optimal routeing is brought to the next level by shifting the flow of an MFDL path from other paths for each OD pair, thereby the cost function decrements through incremental changes in path flow.
The methods proposed in this regard are:
1. Frank-Wolfe flow deviation method [4]
2. Projection method. [4]: This calculates increment of flow change for each path considering the relative magnitudes of the path lengths and also makes use of the second derivatives of the cost function. The path flow is simply set to zero if the increment is large enough to make the path flow negative (i.e., it is "projected" back onto the positive orthant).
Conclusion:
The excessive dependence on computer networks makes it inevitable for optimisation. The study of various aspects of routeing reveals that there is no clear cut policy in selecting the optimisation process but instead depends on the circumstances viz., which criteria needs to be optimised in particular and under what conditions. The enhancement of one measure may deteriorate the other.
Thus routeing optimisation is a complex and sophisticated mechanism that necessitates the coordination of various network nodes for effective communication.
Overall the article attempts in giving some insight into the routeing optimisation world. The methods mentioned are both heuristic and exact, which can be used suitably to address the issue.