Research On Routing Algorithms In Interconnection Networks

Interconnection networks have recently found wide applications, from telephone networks, multi-processor system, distributed systems to switches/routers. And Direct Interconnection Network (DIN), one type of the Interconnection network, now serves as a good candidate for Terabit Router switching fabrics owing to its characteristics of good scalability and easy distribution control.The non-uniform traffic in DIN requires available routing algorithms to distribute the data flow evenly among all the physical links. However, the traditional routing algorithms in DIN, such as Dimension order routing algorithm (DOR), Duato's algorithm, GAL etc, do not balance the traffic very well. For example, DOR only provides one unchanged path for a certain source-destination pair so that packets can not bypass congested areas in the network; Duato's algorithm is a minimal algorithm with non-minimal paths unexploited; GAL was designed for the adversarial traffic and gives bad performance under the benign traffic.To solve this problem, two new routing algorithms were presented for DIN, GD (Gas Diffusion based routing algorithm) which was inspired from the gas diffusion phenomenon in the nature and FOA (Forward-only Agent routing algorithm) which is an intelligent algorithm based on swarm intelligence. Minimal adaptive routing is adopted and software-based recovery mechanism is used to detect and resolve deadlocks in both algorithms. In GD, packets are routed stochastically according to the congestion degree of a port which is measured by the number of packets which can not be sent out in a given period. As a result, fewer packets will be routed to the port which has higher congestion degree to balance the load. In FOA, only forward agents are used to update the routing information related to their source node while traveling to the destination. Besides, packets are routed randomly based on the goodness of a neighbor which is measured by not only the routing information recorded in the routing table but also the current link condition in order to reach load balance. Simulations were carried out with OPNET software in k-ary n-cube networks in which virtual cut through switching mechanism is used, and the results show that both algorithms achieve a better performance than other popular algorithms such as DOR, Duato's algorithm and GAL.