An Efficient Distributed Minimal Routing Algorithm for Triplet-Based WK-recursive Network
Xu Chen, Feng Shi, Fei Yin, Zenghui Wei, Xiaojun Wang · 2018
The design of an efficient routing algorithm is an important task since it not only determines the path that each packet follows but also affects the network performance, cost and power consumption. In this paper, we focus on exploring a distributed minimal routing algorithm for triplet-based WK-recursive network. By fully taking advantage of the characteristics of the network, we employ the concept S3 group to establish a powerful coding system. Otherwise, a region-based data flow model is proposed to categorize message traffic as six types. To further improve the efficiency of computation, we leverage cyclic permutation of S_3 group to perform equivalent transformation between traffic models and hence the calculation is carried out in the same model. Using a extended cycle-accurate simulator Noxim, the experiment results show that our proposed design provides 18.6%-35.3% improvement in average network latency and 15.2%-21.8% improvement in average network throughput over the previous algorithm evaluated in this study.