Comparative analysis of Traffic Patterns on k-ary n-tree using adaptive algorithms based on Burton Normal Form

Abstract

k-ary n-trees are a particular type of Fat-Trees that belong to parametric family of topologies. In spite of their wide usage as an Interconnection Network topology, it has been quite unclear about the performance of Adaptive Routing Algorithms on them. In this paper, we consider a 4-ary 3-tree and analyze two Adaptive Routing Algorithms namely the Non-Minimal Adaptive Routing Algorithm and Minimal Adaptive Routing Algorithm. Specifically, the application of these algorithms on 4-ary 3-tree using various Traffic Patterns has been simulated. The six Traffic Patterns called BitTranspose, BitReversal, BitComplement, Uniform Distribution, k-shift and Ring are used as running examples throughout the paper. The simulation results show that the Network Latency for k-ary n-tree is much higher in case of the Non-Minimal Algorithm as compared to the Minimal Algorithm. However, in case of Ring Traffic, the results show a deviant behavior when compared to other patterns.