Some of the material in is restricted to members of the community. By logging in, you may be able to gain additional access to certain collections or items. If you have questions about access or logging in, please use the form on the Contact Page.
The use of fat-tree topologies is a popular choice for high performance computing systems. Good routing algorithms are crucial to exploiting the high connectivity of the fat-tree topology. My research considers a family of fat-tree topologies known as the Extended Generalized Fat-tree Topology (XGFT) and focuses on two areas: (1) developing routing algorithms that optimize various performance metrics, and (2) investigating the performance gap for fat-trees with different routing schemes. In developing new routing algorithms, both single-path routing and multi-path routing are considered. The new single path routing schemes include one that optimizes for the oblivious performance ratio (OBR) and provides a worse-case performance guarantee, and another one that optimizes for worse-case permutation performance on any 2-level XGFT. For multi-path routing, it is shown that without limiting the number of paths used in multi-path routing, there exists a multi-path routing scheme that is optimal in terms of maximum link load for any traffic demand. A limited multi-path routing scheme is proposed to address the cases when the number of paths for each source destination (SD) pair that can be used is limited. The limited multi-path routing scheme gracefully improve routing performance as the number of paths used increases, and reach optimal when all shortest paths between each SD pair are used to route traffic. Finally, the potential performance gap for fat-tree topologies with different routing schemes is investigated. The results indicate that although a commonly used single path routing can perform orders of magnitude worse than the optimal routing scheme in the worst case, it can reach 65\% to 90\% of the optimal in the average case depending on the topologies, which indicates that the gap between different routing schemes on fat-trees, although noticeable, is not very large.
A Dissertation submitted to the Department of Computer Science in partial fulfillment of the requirements for the degree of Doctor of Philosophy.
Bibliography Note
Includes bibliographical references.
Advisory Committee
Xin Yuan, Professor Directing Dissertation; Kyle Gallivan, University Representative; Zhenhai Duan, Committee Member; Zhenghao Zhang, Committee Member.
Publisher
Florida State University
Identifier
FSU_migr_etd-8860
Use and Reproduction
This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s). The copyright in theses and dissertations completed at Florida State University is held by the students who author them.
