OPTIMAL PACKET ROUTING

Abstract-
The optimal routing is the determination of the optimal routing policy that is the set of routes on which packets need to be transmitted in order to reduce the delay, cost and throughput. The routing optimization problem is an important tool in the optimization of both the operational capabilities and the design of large scale commuter communications networks. Resource requirements are not taken into account for conventional routing algorithms. The problem of finding optimal routes in a packet switched computer can be done using non linear multi commodity flow problem. The mathematical programming technique which is applied for the solution of routing problem for large networks is inefficient output. By using Heuristic methods satisfactory results can be obtained. But using Heuristic technique the results are not always optimal and may have some limitations. To overcome all this we can use decomposition method which is very efficient for computation and results are nearly exact.
Introduction-
Routers are basically classified into two types- Oblivious and Adaptive. In oblivious routing the path is completely determined by the sources and destination. Whereas Deterministic routing is the same path is chosen between a source and destination. The nature of deterministic routing is distributed that is each node makes its routing decisions independent of others which make routing simple and fast and this is widely used in most of the networks. On the other hand in oblivious routing algorithms it is difficult because of certain traffic patterns that are many flows are routed through same link and generate heavy network congestion.
In adaptive routing, given sources and destination address the path taken by a particular packet is dynamically adjusted depending on the network congestion. Adaptive routing uses dynamic load balancing can achieve better throughput and latency when compared to oblivious routing. But with the adaptive the challenges may be faced are balancing the router complexity with capability to adapt.
Main Body- In this paper, we will discuss the application aware oblivious routing framework that statically determines the deadlock free routes considering applications communication characteristics Michel et. al [3].As the framework supports a variety of algorithms which can optimize various cost functions like channel load, latency of routes, or the combination. Band width sensitive oblivious routing, with static virtual channel allocation, produces deadlock-free routes gives rough estimates of bandwidth demands of all flows obtained through application program analysis and/or profiling. Using these estimates, an offline algorithm determines routes for the data transfers that maximize satisfaction of flow demand or minimize maximum channel load, while ensuring deadlock freedom. The network is then statically configured prior to runtime as processing elements are loaded with the computation code. This approach can achieve better throughput than traditional oblivious routing algorithms because routes are optimized based on the bandwidth demands. The routers used for these processes are kept simple as the routes are configured statically and they do not change at runtime.
Router Architecture- Fig. 1 shows typical virtual channel router architecture and its operation. It consists of data path of the router consisting a switch and a buffer The input buffer store flits while they are waiting to be forwarded to the next cycle. When the flit is ready to move the switch connects the input buffer to an appropriate channel. Data path is controlled using three control modules: a router, a virtual channel allocator and a switch allocator. The routing operations takes in four phases routing (RC), virtual channel allocation (VA), switch allocation (SA), and a switch traversal (ST). These represent one to four pipeline stages in modern virtual channel routers. At the input channel a head flit is arrived, the router stores the input in the buffer from the allocated virtual channel and determines the next hop for the packet (RC phase). The router then allocates a virtual channel in VA phase and finally flit comes SA phase and moves to the output port (ST phase).

a. Router Architecture
Routing Computation (RC) Switch Traversal (ST) Switch Allocation (SA)
Virtual Channel Allocation (VA)

b. Router Pipeline

Fig. 1. Typical virtual-channel router architecture. It indicates that the modules and routing step may be modified for our approach.
Application aware oblivious routing exploits application knowledge to provide deadlock freedom and efficient network resources. Two deadlock avoidance techniques, namely acyclic channel dependency routing and static virtual channel allocation.
The Bandwidth sensitive Oblivious routing algorithm targets only minimal routes and made the deadlock free. Bandwidth sensitive oblivious routing selects the routes to minimize the more number of channel load. A minimal route that heuristically minimizes the maximum channel load. A Heuristic method maintains the deadlock freedom by checking to see if rerouting introduces cycles. Palesi et al. [1],[2] provides framework and algorithms for application specific bandwidth aware deadlock free adaptive routing. For a given set of source destination pairs cycles are broken in such a way to minimize the impact on the average degree of adaptiveness. To spread traffic uniformly through the network the bandwidth requirements are taken into the account. For this Towles et al. [30] give a multicommodity flow linear programming formulation for router algorithm design. In oblivious routing schemes, the application is breached into different ways using adhoc schemes. Deadlock can be avoided by assuming that each flow has its own private channel.

Conclusion- An offline strategy to compute routes, it doesn’t require any significant modification to standard routers as it is based on the knowledge of applications data transfers to arrive at an application aware oblivious routing framework. Application performance can be improved by estimating the bandwidth demand of the applications data transfer. The main limitation is knowledge is required for processing. Heuristic algorithms are easier to code and require less memory space. They are quite close to optimum.
References-
[1] M. Palesi, R. Holsmark, S. Kumar, and V. Catania, “A Methodology for Design of Application Specific Deadlock-Free Routing Algorithms for NoC Systems,” Proc. Fourth Int’l Conf. Hardware/ Software Codesign and System Synthesis (CODES+ISSS ’06), Oct. 2006.
[2] M. Palesi, G. Longo, S. Signorino, R. Holsmark, S. Kumar, and V.Catania, “Design of Bandwidth Aware and Congestion Avoiding
Efficient Routing Algorithms for Networks-on-Chip Platforms,” Proc. ACM/IEEE Int’l Symp. Networks-on-Chip (NOCS), pp. 97-106,2008
[3] Michel A. Kinsy, Myong Hyon Cho, Keun Sup Shim, Mieszko Lis, G. Edward Suh,” Optimal and Heuristic Application-Aware Oblivious Routing” Proc.