The subject of study in this paper is a generalized fat tree. It has n levels of switch and each switch can have different number of downstream and upstreams. A regular fat tree, \(k\)-ary \(n\)-tree, has each switch connects to \(k\) downstreams.
Route a communication in fat tree is equivalent to choosing one of the nearest common ancestor (NCA) in the fat tree. Three different routing schemes are evaluated, they are namely, random, S-mod-k and D-mod-k. Random is to choose the NCA randomly. S-mod-k and D-mod-k choose the NCA by taking modulus on the source and destination address.
The paper found the following:
- S-mod-k and D-mod-k are merely equivalent
- There are cases that random does better than S-mod-k/D-mod-k and some cases that it does worse
According to the analysis, the paper propose that a better oblivious algorithms satisfies the following:
- Concentrate the endpoint contention. This is why S-mod-k/D-mod-k do better than random if there are endpoint contention
- Distribute load amongst roots. This is why random does better if there is no endpoint contention
- Break down the regular dependencies of typical applications’ patterns
The paper suggest a relabeling of nodes and then apply S-mod-k/D-mod-k. The relabeling is like a randomization, but preserves the locality such that endpoint contention can be identified. Then the S-mod-k or D-mod-k can effectively distribute load to roots.
Bibliographic data
@inproceedings{
title = "Oblivious Routing Schemes in Extended Generalized Fat Tree Networks",
author = "German Rodriguez and Cyriel Minkenberg and Ramon Beivide and Ronald P. Luijten and Jesus Labarta and Mateo Valero",
booktitle = "Proc. IEEE International Conference on Cluster Computing and Workshops",
howpublished = "CLUSTER'09",
pages = "1--8",
month = "Aug 31-Sep 4",
year = "2009",
address = "New Orleans, LA",
}