@article {23944,
	title = {Compact Network Reconfiguration in Fat-Trees},
	journal = {The Journal of Supercomputing},
	volume = {72},
	year = {2016},
	pages = {4438{\textendash}4467},
	publisher = {Springer},
	author = {Zahid, Feroz and Ernst Gunnar {Gran} and Bogdanski, Bartosz and Bj{\o}rn Dag {Johnsen} and Skeie, Tor and Tasoulas, Evangelos}
}
@article {23945,
	title = {Efficient Network Isolation and Load Balancing in Multi-Tenant HPC Clusters},
	journal = {Journal of Future Generation Computer Systems},
	year = {2016},
	month = {04/2016},
	publisher = {Elsevier},
	doi = {http://dx.doi.org/10.1016/j.future.2016.04.003},
	author = {Zahid, Feroz and Ernst Gunnar {Gran} and Bogdanski, Bartosz and Bj{\o}rn Dag {Johnsen} and Skeie, Tor}
}
@misc {24958,
	title = {System and method for efficient network reconfiguration in fat-trees},
	number = {US15/073,022},
	year = {2016},
	month = {03/2016},
	type = {Pending},
	abstract = {Systems and methods are provided for supporting efficient reconfiguration of an interconnection network having a pre-existing routing comprising. An exemplary method can provide, a plurality of switches, the plurality switches comprising at least one leaf switch, wherein each of the one or more switches comprise a plurality of ports, and a plurality of end nodes, wherein the plurality of end nodes are interconnected via the one or more switches. The method can detect, by a subnet manager, a reconfiguration triggering event. The method can compute, by the subnet manager, a new routing for the interconnection network, wherein the computing by the subnet manager of the new routing for the interconnection network takes into consideration the pre-existing routing and selects the new routing for the interconnection network that is closest to the pre-existing routing. The method can reconfigure the interconnection network according to the new routing.},
	author = {Bogdanski, Bartosz and Bj{\o}rn Dag {Johnsen} and Zahid, Feroz and Ernst Gunnar {Gran}}
}
@misc {24899,
	title = {System and method for efficient network reconfiguration in fat-trees},
	number = {US14927085},
	year = {2016},
	month = {05/2016},
	type = {Pending},
	abstract = {Systems and methods are provided for supporting efficient reconfiguration of an interconnection network having a pre-existing routing. An exemplary method can provide a plurality of switches, a plurality of end nodes, and one or more subnet managers, including a master subnet manager. The method can calculate, via the master subnet manager, a first set of one or more leaf-switch to leaf-switch multipaths. The method can store this first set of one or more leaf-switch to leaf-switch multipaths at a metabase. The method can detect a reconfiguration triggering event, and call a new routing for the interconnection network. Finally, the method can reconfigure the network according to the new routing for the interconnection network.},
	author = {Zahid, Feroz and Ernst Gunnar {Gran} and Bogdanski, Bartosz and Bj{\o}rn Dag {Johnsen}}
}
@misc {24634,
	title = {System and method for supporting efficient load-balancing in a high performance computing (HPC) environment},
	number = {US14792070},
	year = {2016},
	note = {Date Filed: October 19, 2015,\&nbsp;Published Online: Jan\&nbsp;14, 2016.},
	month = {01/16},
	type = {Pending},
	abstract = {Methods and systems for supporting efficient load balancing among a plurality of switches and a plurality of end nodes arranged in a tree topology in a network environment. The methods and systems can sort the plurality of end nodes, wherein the plurality of end nodes are sorted in a decreasing order of a receive weight. The method and system may further route, in the decreasing order of receive weights, the plurality of end nodes, wherein the routing comprises selecting at least one down-going port and at least one up-going port. Further, the method and system can increase an accumulated downward weight on each selected down-going port by the receive weight of the routed end node, and increase an accumulated upward weight on each selected up-going port by the receive weight of the routed end node},
	author = {Zahid, Feroz and Ernst Gunnar {Gran} and Bogdanski, Bartosz and Bj{\o}rn Dag {Johnsen}}
}
@misc {24635,
	title = {System and method for supporting partition-aware routing in a multi-tenant cluster environment},
	number = {US14927085},
	year = {2016},
	note = {Date Filed: July 6, 2015,\&nbsp;Published Online: May 5, 2016.},
	month = {05/2016},
	type = {Pending},
	abstract = {A system and method can support partition-aware routing in a multi-tenant cluster environment. An exemplary method can support one or more tenants within the multi-tenant cluster environment. The method can associate each of the one or more tenants with a partition of a plurality of partitions. The method can then associate each of the plurality of partitions with one or more nodes of a plurality of nodes, each of the plurality of nodes being associated with a leaf switch of a plurality of switches, the plurality of switches comprising a plurality of leaf switches and a plurality of root switches. Finally, the method can generate one or more linear forwarding tables, the one or more linear forwarding tables providing isolation between the plurality of partitions, wherein each of the plurality of nodes is associated with a partitioning order.},
	author = {Zahid, Feroz and Ernst Gunnar {Gran} and Bogdanski, Bartosz and Bj{\o}rn Dag {Johnsen}}
}
@inproceedings {19134,
	title = {Partition-aware routing to improve network isolation in InfiniBand based multi-tenant clusters},
	journal = {15th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid)},
	year = {2015},
	month = {07/2015},
	pages = {189-198},
	publisher = {ACM/IEEE},
	address = {Shenzhen, China},
	abstract = {InfiniBand (IB) is a widely used network interconnect for modern high-performance computing systems.\&nbsp;In large IB fabrics, network isolation is provided through partitioning.\&nbsp;However, routing is oblivious to the partitions in the network. Hence, physical links\&nbsp;share flows from different partitions. This sharing of the intermediate links creates\&nbsp;interference, which is particularly critical to avoid in multi-tenant environments, like cloud\&nbsp;computing. In such systems, each tenant needs predictable network performance, unaffected by the workload of\&nbsp;the other tenants. In addition, using the current routing schemes, despite that the links connecting nodes outside\&nbsp;partitions are never used, they are routed the same way as the other functional links. This may result in\&nbsp;degraded load-balancing.In this paper, we present an implementation of a partition-aware fat-tree routing algorithm, pFTree. The pFTree\&nbsp;utilizes a multifold mechanism to provide performance isolation among partitions belonging to the different tenant groups.\&nbsp;Given the available network resources, pFTree starts isolating partitions\&nbsp;at the physical link level, and then it moves on to utilize virtual lanes when needed. Our\&nbsp;experiments and simulations show that pFTree is able to significantly reduce the affect of\&nbsp;inter-partition interference effectively without any additional functional overhead. Furthermore, pFTree also provides\&nbsp;improved load-balancing over the state-of-the-art fat-tree routing algorithm.},
	isbn = {978-1-4799-8006-2},
	doi = {10.1109/CCGrid.2015.96},
	author = {Zahid, Feroz and Ernst Gunnar {Gran} and Bogdanski, Bartosz and Bj{\o}rn Dag {Johnsen} and Skeie, Tor}
}
@inproceedings {23558,
	title = {SlimUpdate: Minimal Routing Update for Performance-based Reconfigurations in Fat-Trees},
	journal = {1st IEEE International Workshop on High-Performance Interconnection Networks Towards the Exascale and Big-Data Era (HiPINEB 2015)},
	year = {2015},
	month = {10/2015},
	pages = {849-856},
	publisher = {IEEE Computer Society},
	abstract = {As the size of high-performance computing systems grows, the number of events requiring a network\&nbsp;reconfiguration, as well as the complexity of each reconfiguration, is likely to increase.\&nbsp;In large systems, the probability of component failure is high. At the same time, with more\&nbsp;network components, ensuring high utilization of network resources becomes challenging.\&nbsp;Reconfiguration in interconnection networks,\&nbsp;like InfiniBand (IB), typically involves computation and distribution of a new set of routes in order\&nbsp;to maintain connectivity and performance. In general, current routing algorithms do not consider the\&nbsp;existing routes in a network when calculating new ones. Such configuration-oblivious routing\&nbsp;might result in substantial modifications to the existing paths, and the reconfiguration\&nbsp;becomes costly as it potentially involves a large number of source-destination pairs.\&nbsp;In this paper, we propose a novel routing algorithm for IB based fat-tree topologies, SlimUpdate.\&nbsp;SlimUpdate employs techniques to preserve existing forwarding entries in switches to ensure a minimal\&nbsp;routing update, without any performance penalty, and with minimal computational overhead.\&nbsp;We present an implementation of SlimUpdate in OpenSM,\&nbsp;and compare it with the current de facto fat-tree routing algorithm. Our experiments and simulations show\&nbsp;a decrease of up to 80\% in the number of total path modifications when using SlimUpdate routing, while achieving\&nbsp;similar or even better performance than the fat-tree routing in most reconfiguration scenarios.},
	isbn = {978-1-4673-6598-7},
	doi = {10.1109/CLUSTER.2015.142},
	author = {Zahid, Feroz and Ernst Gunnar {Gran} and Bogdanski, Bartosz and Bj{\o}rn Dag {Johnsen} and Skeie, Tor}
}
@inproceedings {19102,
	title = {A weighted fat-tree routing algorithm for efficient load-balancing in InfiniBand enterprise clusters},
	journal = {Proceedings of the 23rd Euromicro International Conference on Parallel, Distributed Network-based Processing (PDP 2015)},
	year = {2015},
	month = {03/2015},
	pages = {35-42},
	publisher = {IEEE},
	address = {Turku, Finland},
	abstract = {InfiniBand (IB) has become a popular network interconnect for\&nbsp;high-performance computing (HPC) systems. Many of the large\&nbsp;IB-based HPC systems use some variant of the fat-tree topology to take advantage\&nbsp;of the useful properties fat-trees offer. The fat-tree routing algorithm\&nbsp;is one of the most efficient deterministic routing\&nbsp;algorithms for fat-tree topologies.\&nbsp;The algorithm ensures that the number of routes assigned to each link are balanced across the fabric. However,\&nbsp;one problem with its load-balancing technique is that it assumes\&nbsp;uniform traffic distribution in the network. When routes towards nodes that mainly consume\&nbsp;large amount of data are assigned to share links in the fabric while alternative links are underutilized,\&nbsp;sub-optimal network throughput is obtained. Also, as the fat-tree algorithm routes\&nbsp;nodes according to the indexing order, the performance may differ\&nbsp;for two systems cabled in the exact same way.In this paper, we propose wFatTree, a novel fat-tree routing algorithm, which considers node traffic characteristics to balance load\&nbsp;across the network links more evenly, and with predictable network performance. Our experiments\&nbsp;and simulations show an improvement of up to 60\% in total network throughput on large\&nbsp;fat-tree installations when using wFatTree routing. Furthermore, wFatTree can also be used to prioritize traffic flowing towards\&nbsp;the critical nodes in the network.},
	keywords = {fat-tree networks, InfiniBand, Load-balancing, Routing algorithms},
	issn = {1066-6192},
	doi = {10.1109/PDP.2015.111},
	author = {Zahid, Feroz and Ernst Gunnar {Gran} and Bogdanski, Bartosz and Bj{\o}rn Dag {Johnsen} and Skeie, Tor}
}
@inproceedings {Simula.simula.2226,
	title = {Multi-Homed Fat-Tree Routing With InfiniBand},
	journal = {22nd Euromicro International Conference on Parallel, Distributed and Network-based Processing},
	year = {2014},
	month = {02/2014},
	pages = {122-129},
	publisher = {IEEE Computer Society},
	type = {Conference},
	abstract = {For clusters where the topology consists of a fat-tree or more than one fat-tree combined into one subnet, there are several properties that the routing algorithms should support, beyond what exists today. One of the missing properties is that current fat-tree routing algorithm does not guarantee that each port on a multi-homed node is routed through redundant spines, even if these ports are connected to redundant leaves. As a consequence, in case of a spine failure, there is a small window where the node is unreachable until the subnet manager has rerouted to another spine. In this paper, we discuss the need for independent routes for multi-homed nodes in fat-trees by providing real-life examples when a single point of failure leads to complete outage of a multi-port node. We present and implement the methods that may be used to alleviate this problem and perform simulations that demonstrate improvements in performance, scalability, availability and predictability of InfiniBand fat-tree topologies. We show that our methods not only increase the performance by up to 52.6\%, but also, and more importantly, that there is no downtime associated with spine switch failure.},
	issn = {1066-6192},
	doi = {http://dx.doi.org/10.1109/PDP.2014.22},
	author = {Bogdanski, Bartosz and Reinemo, Sven-Arne and Bj{\o}rn Dag {Johnsen}}
}
@phdthesis {Simula.simula.3042,
	title = {Optimized Routing for Fat-Tree Topologies},
	year = {2014},
	school = {University of Oslo},
	type = {phd},
	author = {Bogdanski, Bartosz}
}
@inproceedings {Simula.simula.1996,
	title = {Making the Network Scalable: Inter-Subnet Routing in InfiniBand},
	journal = {Proceedings from the 19th International Euro-Par Conference on Parallel Processing},
	volume = {8097},
	year = {2013},
	month = {August},
	pages = {685-698},
	publisher = {Springer Berlin Heidelberg},
	type = {Conference},
	abstract = {As InfiniBand clusters grow in size and complexity, the need arises to segment the network into manageable sections. Up until now, InfiniBand routers have not been used extensively and little research has been done to accommodate them. However, the limits imposed on local addressing space, inability to logically segment fabrics, long reconfiguration times for large fabrics in case of faults, and, finally, performance issues when interconnecting large clusters, have rekindled the industry\&$\#$39;s interest into IB-IB routers. In this paper, we examine the routing problems that exist in the current implementation of OpenSM and we introduce two new routing algorithms for inter-subnet IB routing. We evaluate the performance of our routing algorithms against the current solution and we show an improvement of up to 100 times that of OpenSM.},
	keywords = {Conference},
	isbn = {978-3-642-40046-9},
	doi = {10.1007/978-3-642-40047-6\_69},
	author = {Bogdanski, Bartosz and Bj{\o}rn Dag {Johnsen} and Reinemo, Sven-Arne and Flich, Jos{\'e}},
	editor = {Bernd Mohr Felix {Wolf} and Dieter an {Mey}}
}
@inproceedings {Simula.simula.1554,
	title = {Discovery and Routing of Degraded Fat-Trees},
	journal = {2012 13th International Conference on Parallel and Distributed Computing, Applications and Technologies},
	year = {2012},
	month = {December},
	pages = {689-694},
	publisher = {IEEE Computer Society},
	type = {Conference},
	address = {Los Alamitos},
	abstract = {The fat-tree topology has become a popular choice for InfiniBand enterprise systems due to its deadlock freedom, fault-tolerance and full bisection bandwidth. In the HPC domain, InfiniBand fabric is used in almost 42\% of the systems on the latest Top 500 list, and many of those systems are based on the fat-tree topology. Despite the popularity of the fat-tree topology, little research has been done to compare the behavior of InfiniBand routing algorithms on degraded fat-tree topologies. In this paper, we identify the weaknesses of the current fat-tree routing and propose enhancements that liberalize the restrictions imposed on the routed fabric. Furthermore, we present a thorough analysis of non-proprietary routing algorithms that are implemented in the InfiniBand Open Subnet Manager. Our results show that even though the performance of a fat-tree routed network deteriorates predictably with the number of failed links, fat-tree routing algorithm is still the best choice for severely degraded fat-tree fabrics.},
	keywords = {Conference},
	author = {Bogdanski, Bartosz and Bj{\o}rn Dag {Johnsen} and Reinemo, Sven-Arne and Frank Olaf {Sem-Jacobsen}},
	editor = {Shen, Hong and Sang, Yingpeng and Li, Yidong and Qian, Depai and Albert Y. {Zomaya}}
}
@article {Simula.simula.864,
	title = {SFtree: a Fully Connected and Deadlock Free Switch-to-Switch Routing Algorithm for Fat-Trees},
	journal = {ACM Transactions on Architecture and Code Optimization},
	volume = {8},
	number = {4},
	year = {2012},
	month = {January},
	publisher = {ACM},
	abstract = {Existing fat-tree routing algorithms fully exploit the path diversity of a fat-tree topology in the context of compute node traffic, but they lack support for deadlock free and fully connected switch-to-switch communication. Such support is crucial for efficient system management, for example in InfiniBand (IB) systems. With the general increase in system management capabilities found in modern InfiniBand switches, the lack of deadlock free switch-to-switch communication is a problem for fat-tree based IB installations because management traffic might cause routing deadlocks that bring the whole system down. This lack of deadlock free communication affects all system management and diagnostic tools using LID routing. In this paper, we propose the sFtree routing algorithm that guarantees deadlock free and fully connected switch-to-switch communication in fat-trees while maintaining the properties of the current fat-tree algorithm. We prove that the algorithm is deadlock free and we implement it in OpenSM for evaluation. We evaluate the performance of the sFtree algorithm experimentally on a small cluster and we do a large-scale evaluation through simulations. The results confirm that the sFtree routing algorithm is deadlock free and show that the impact of switch-to-switch management traffic on the end-node traffic is negligible.},
	doi = {http://dx.doi.org/10.1145/2086696.208673},
	author = {Bogdanski, Bartosz and Reinemo, Sven-Arne and Frank Olaf {Sem-Jacobsen} and Ernst Gunnar {Gran}}
}
@misc {Simula.simula.824,
	title = {VFtree - a Fat-Tree Routing Algorithm Using Virtual Lanes to Alleviate Congestion},
	howpublished = {Invited talk at the HPC Advisory Council Switzerland Workshop 2011, Lugano, Switzerland.},
	year = {2011},
	month = {March},
	abstract = {A large number of clusters using InfiniBand is based on fat-tree topologies that can be routed deadlock-free using only one virtual lane. Consequently, all the remaining virtual lanes are left unused. In this talk we present an enhancement to the fat-tree algorithm that utilizes virtual lanes to improve performance when hot-spots are present. In a congested environment, results show that we are able to achieve throughput increases up to 38\% on a small cluster and from 221\% to 757\% depending on the hot-spot scenario for a 648-port simulated cluster.},
	author = {Reinemo, Sven-Arne and Wei Lin {Guay} and Bogdanski, Bartosz and Lysne, Olav and Skeie, Tor}
}
@inproceedings {Simula.simula.184,
	title = {VFtree - a Fat-Tree Routing Algorithm Using Virtual Lanes to Alleviate Congestion},
	journal = {Proceedings of the 25th IEEE International Parallel \& Distributed Processing Symposium},
	year = {2011},
	pages = {197-208},
	publisher = {IEEE Computer Society Press},
	type = {Conference},
	abstract = {It is a well known fact that multiple virtual lanes can improve performance in interconnection networks, but this knowledge has had little impact on real clusters. Currently, a large number of clusters using InfiniBand is based on fat-tree topologies that can be routed deadlock-free using only one virtual lane. Consequently, all the remaining virtual lanes are left unused. In this paper we suggest an enhancement to the fat-tree algorithm that utilizes virtual lanes to improve performance when hot-spots are present. Even though the bisection bandwidth in a fat-tree is constant, hot-spots are still possible and they will degrade performance for flows not contributing to them due to head-of-line blocking. Such a situation may be alleviated through adaptive routing or congestion control, however, these methods are not yet readily available in InfiniBand technology. To remedy this problem, we have implemented an enhanced fat-tree algorithm in OpenSM that distributes traffic across all available virtual lanes without any configuration needed. We evaluated the performance of the algorithm on a small cluster and done a large-scale evaluation through simulations. In a congested environment, results show that we are able to achieve throughput increases up to 38\% on a small cluster and from 221\% to 757\% depending on the hot-spot scenario for a 648-port simulated cluster.},
	isbn = {978-1-61284-372-8},
	author = {Wei Lin {Guay} and Bogdanski, Bartosz and Reinemo, Sven-Arne and Lysne, Olav and Skeie, Tor},
	editor = {Xin, Yuan}
}
@inproceedings {Simula.netsys.16,
	title = {Achieving Predictable High Performance in Imbalanced Fat Trees},
	journal = {Proceedings of the 16th IEEE International Conference on Parallel and Distributed Systems},
	year = {2010},
	month = {December},
	pages = {381-388},
	publisher = {IEEE Computer Society},
	type = {Conference},
	abstract = {Abstract-The fat-tree topology has become a popular choice for InfiniBand fabrics due to its inherent deadlock freedom, fault-tolerance and full bisection bandwidth. InfiniBand is used by more than 40\% of the systems on the latest Top 500 list, and many of these systems are based on a fat-tree topology. However, the current InfiniBand fat-tree routing algorithm suffers from flaws that reduce its scalability and flexibility. Counter-intuitively, the achievable throughput per node deteriorates both when the number of nodes in a tree decreases or when the node distribution among leaves is nonuniform. In this paper, we identify the weaknesses of the current enhanced fat-tree routing algorithm in OpenFabrics Enterprise Distribution and we propose extensions to it that alleviate all performance problems related to node distribution. The new algorithm is implemented in OpenSM for real world evaluation and for future contribution to the OpenFabrics community. We demonstrate that our solution allows to achieve a predictable high throughput regardless of the number of nodes and their distribution. Furthermore, the simulations show that our extensions improve throughput up to 30\% depending on topology size and node distribution.},
	isbn = {978-0-7695-4307-9},
	author = {Bogdanski, Bartosz and Frank Olaf {Sem-Jacobsen} and Reinemo, Sven-Arne and Skeie, Tor and Holen, Line and Lars Paul {Huse}},
	editor = {Huang, Xiaoxia}
}
@misc {Simula.netsys.14,
	title = {VFtree- Fat Tree Routing With Virtual Lanes in InfiniBand},
	howpublished = {Poster, HiPEAC ACACES, Barcelona, Spain},
	year = {2010},
	abstract = {Even though the bisectional bandwidth in a fat-tree is constant, hot spots are still possible. Such a situation may be alleviated through adaptive routing or congestion control, however, these methods are not fully supported in InfiniBand technology. We propose an inexpensive approach for reducing the hot-spot problem in fat-trees, which is based on the application of virtual lanes.},
	author = {Wei Lin {Guay} and Bogdanski, Bartosz and Reinemo, Sven-Arne and Lysne, Olav}
}
