M.Sc Thesis


M.Sc StudentAhmad Omary
SubjectSARD: Switch-based Adaptive Routing for Datacenters
DepartmentDepartment of Electrical Engineering
Supervisor Professor Keslassy Isaac


Abstract

Current datacenters are based on multi-path architectures with large bisectional capacities.  In order to service the increasingly wide range of deployed applications, they need to rely on a load-balancing algorithm that can handle workloads with significant skewness and inter-flow correlations. These workloads can quickly cause congestion in varying network points. Thus, the load-balancing algorithm should be able to adapt to congestion by rerouting traffic whenever an internal network point gets congested. At the same time, the load-balancing algorithm also needs to be scalable and grow with the fast-increasing network sizes and line rates. Thus, to find a suitable load-balancing algorithm, the datacenter designer needs to balance between the need to quickly adapt to congestion with potentially complex feedback mechanisms, and the need to provide a scalable algorithm with a simple implementation.
 

In this research we present SARD, a fully distributed switch based adaptive routing algorithm for multi-layer network topologies in datacenters. We argue that SARD is based on a minimalistic design to achieve both scalability and adaptability to congestion. We further analyze SARD in a Clos network topology with uniform flow sizes, and explain why its last step should achieve an expected convergence time that is linear with the network size for full-link bandwidth traffic, using a model based on random walks on a circle. In addition, we also develop a mathematical model for the behavior of SARD during the first steps. Finally, we evaluate its performance, and show that it performs better than current state-of-the-art scalable algorithms.