Paper Info
Title
Transitively Deadlock-Free Routing Algorithms
Abstract
In exascale platforms, faults are likely to occur more and more frequently due to the huge number of components. To handle them, the BXI fabric management uses a generic architecture that specifies two distinct modes of operations: offline mode computes, validates and uploads nominal routing tables, while online mode reacts at runtime to failures and recoveries by computing small patches and by uploading them to the concerned switches. This design presented in a previous article, helps limiting both the computation time and the failure impact on the whole fabric. However, in wormhole switching such as with BXI, uploading new routing tables at runtime is known to be generally deadlock-prone. This paper thus introduces a new property of online routing algorithms called transitively deadlock-free and presents the formal description of two BXI online routing algorithms holding this property. It also shows that the combination of a deadlock-free offline routing algorithm with a transitively deadlock-free online one provides a fault-tolerant deadlock-free routing algorithm. The theory is flexible enough to be adapted to other routing algorithms and to other topologies.
Year
DOI
Venue
2016
10.1109/HIPINEB.2016.10
2016 2nd IEEE International Workshop on High-Performance Interconnection Networks in the Exascale and Big-Data Era (HiPINEB)
Keywords
Field
DocType
Deadlock-Free Routing,Fault-Tolerant Routing,BXI,Interconnect Management,High Performance Computing
Multipath routing,Link-state routing protocol,Dynamic Source Routing,Computer science,Static routing,Computer network,Real-time computing,Routing table,Distributed computing,Policy-based routing,Enhanced Interior Gateway Routing Protocol,Parallel computing,Destination-Sequenced Distance Vector routing
Conference
Citations 
PageRank 
References 
2
0.41
20
Authors
2
Name
Order
Citations
PageRank
Jean-Noël Quintin1284.11
P. Vignéras2132.54