A load-balancing adaptive routing algorithm in k-ary n-cube interconnection networks

We propose a new routing algorithm in k-ary n-cube interconnection networks which is adaptive, livelock-free, balances the load across the network, and preserves the sequence of packets belonging to the same flow. Our proposed routing algorithm is based on dimension-order routing, and utilizes the path diversity available in the network. Instead of choosing a deterministic route, however, it randomly selects a minimal path from a set of minimal routes available between source and destination. The randomization is carried out in such a way that the order of packets belonging to the same flow is preserved. Our routing algorithm is also adaptive in the sense that the link utilization is measured by the size of the queue feeding the link, and is periodically advertised to all nodes in the network.