Title
Ensuring Deadlock-Freedom in Low-Diameter InfiniBand Networks
Abstract
Lossless networks, such as InfiniBand use flow-control to avoid packet-loss due to congestion. This introduces dependencies between input and output channels, in case of cyclic dependencies the network can deadlock. Deadlocks can be resolved by splitting a physical channel into multiple virtual channels with independent buffers and credit systems. Currently available routing engines for InfiniBand assign entire paths from source to destination nodes to different virtual channels. However, InfiniBand allows changing the virtual channel at every switch. We developed fast routing engines which make use of that fact and map individual hops to virtual channels. Our algorithm imposes a total order on virtual channels and increments the virtual channel at every hop, thus the diameter of the network is an upper bound for the required number of virtual channels. We integrated this algorithm into the InfiniBand software stack. Our algorithms provide deadlock free routing on state-of-the-art low-diameter topologies, using fewer virtual channels than currently available practical approaches, while being faster by a factor of four on large networks. Since low-diameter topologies are common among the largest supercomputers in the world, to provide deadlock-free routing for such systems is very important.
Year
DOI
Venue
2016
10.1109/HOTI.2016.015
2016 IEEE 24th Annual Symposium on High-Performance Interconnects (HOTI)
Keywords
Field
DocType
low-diameter topology,deadlock free routing,InfiniBand software stack,fast routing engines,source nodes,destination nodes,routing engines,credit systems,independent buffers,multiple virtual channels,input-output channels,packet-loss avoidance,flow-control,lossless networks,low-diameter InfiniBand networks,deadlock-freedom
InfiniBand,Upper and lower bounds,Computer science,Deadlock,Computer network,Communication channel,Network topology,Input/output,Software,Virtual channel,Distributed computing
Conference
ISBN
Citations 
PageRank 
978-1-5090-2855-9
1
0.37
References 
Authors
10
3
Name
Order
Citations
PageRank
Timo Schneider131218.39
Otto Bibartiu210.37
Torsten Hoefler32197163.64