A priority-based balanced routing scheme for random broadcasting and routing in tori
Chi‐Hsiang Yeh, Emmanouel Varvarigos, Abdelhamid E. Eshoul · 2003
We propose a priority-based balanced routing scheme, called the priority STAR routing scheme, which leads to optimal throughput and average delay at the same time for random broadcasting and routing. In particular, the average reception delay for random broadcasting required in n/sub 1//spl times/n/sub 2//spl times/.../spl times/n/sub d/ tori with n/sub i/=O(1), n-ary d-cubes with n=O(1), or d-dimensional hypercubes is O(d+1/(1-/spl rho/)). We also study the case where multiple communication tasks for random 1-1 routing and/or random broadcasting are executed at the same time. When a constant fraction of the traffic is contributed by broadcast requests, the average delay for random 1-1 routing required in any d-dimensional hypercube, any n-ary d-cube with n = O(1), and most n/sub 1//spl times/n/sub 2//spl times/.../spl times/n/sub d/ tori with n/sub i/=O(1) are O(d) based on priority STAR. Our simulation results show that the priority-based balanced routing scheme considerably outperform the best previous routing schemes for these networks.