The Influence of Graph Strucure on Generalized Dimension Exchange

Generalized dimension exchange (GDE) has been proposed as a method of load balancing in interconnection networks. This paper examines the behavior of GDE over the family of binary Hamming graphs. A lower bound for the rate at which GDE converges to load balance is also given. Keywords: analysis of algorithms, distributed computing 1 Introduction This paper will examine the influence of graph structure on GDE, generalized dimension exchange, which has been proposed and studied as a method of load balancing in interconnection networks by Hosseini, Litow and Vairavan [4], Xu and Lau [9], and related research by Cybenko [3] and Boillat [2]. This paper's emphasis is on understanding the asymptotic behavior of GDE over graph families as the number of nodes goes to infinity. Issues related to the extent to which GDE can be used in real networks will not be explored here. However, results in [4, 9, 8] suggest that GDE can, with suitable modifications, be used quite effectively as a load bala..