Title :
Oblivious routing schemes in extended generalized Fat Tree networks
Author :
Rodriguez, German ; Minkenberg, Cyriel ; Beivide, Ramon ; Luijten, Ronald P. ; Labarta, Jesus ; Valero, Mateo
Author_Institution :
Barcelona Supercomput. Center, Nexus II, Barcelona, Spain
fDate :
Aug. 31 2009-Sept. 4 2009
Abstract :
A family of oblivious routing schemes for fat trees and their slimmed versions is presented in this work. First, two popular oblivious routing algorithms, which we refer to as S-mod-k and D-mod-k, are analyzed in detail. S-mod-k is the default routing algorithm given as an example in the first works formally describing fat tree networks. D-mod-k has been independently proposed and investigated by several authors, who conclude in their evaluations that it achieves better performance than a random or adaptive routing approach. First, we identify the reasons why these algorithms perform well. Using this insight we extend these algorithms, originally intended for full bisection networks, to slimmed networks. Based on the lessons learned we propose a new generalized family of algorithms that provides a better oblivious solution than the existing ones for this class of networks. Moreover, this family extends the previous work from k-ary n-trees to the more general class of extended generalized fat trees.
Keywords :
algorithm theory; trees (mathematics); D-mod-k; S-mod-k; adaptive routing approach; extended generalized fat tree networks; oblivious routing schemes; Algorithm design and analysis; Availability; Costs; High performance computing; Laboratories; Proposals; Routing; Switches; System recovery; Telecommunication traffic;
Conference_Titel :
Cluster Computing and Workshops, 2009. CLUSTER '09. IEEE International Conference on
Conference_Location :
New Orleans, LA
Print_ISBN :
978-1-4244-5011-4
Electronic_ISBN :
1552-5244
DOI :
10.1109/CLUSTR.2009.5289145