Optimized Flow Scheduling for Low Latency Data Center Networks

Major cloud computing providers agree on denoting the flow completion time (FCT) as the primary goal to achieve in the design of a data center network (DCN). This is motivated by the fact that latency affects the performance of most cloud computer applications, such as web search, video streaming and social networking, with a direct impact on quality of experience as perceived by end users, hence ultimately on revenues. Many existing approaches in literature rely on prioritization mechanisms at flow or packet level and schedulers in the network to reduce the average FCT, albeit for some applications also tail latency is important. To this purpose, the Shortest Remaining Processing Time (SRPT) scheduling policy is proven to be optimal when the job size is known in advance. Unfortunately this information is rarely available, therefore some proposals emulate the complementary scheme that give service first to flows that have transmitted less (Least Attained Service), exploiting a finite number of priority levels. The effectiveness of these algorithms is largely improved augmenting the number of priorities. However, DCNs are usually realized with low cost commodity devices, where only few queues per port - typically two - are vacant. The contribution of this work is to investigate the feasibility and evaluate the performance of a design which exploits multi-pathing - offered by DCN Fat-Tree topologies - to intelligently route flows across the switching fabric depending on their priority, so as to better segregate latency demanding flows. In other words, load balancing and prioritization are jointly analyzed, in what multiple links together provide higher priority granularity than a port alone. Instead of treating flow scheduling with a scope limited to single bottleneck interfaces, the problem can be addressed at data center level considering the set of equal cost links as a whole. Hence, unlike aforementioned techniques the total number of priority levels achieved is given by the product of the number of priority queues per port and the number of equal cost links. With this approach load balancing directly depend on the flow priority. We refer to this concept as spatial diversity. First, an analytical queuing model is provided for the setting of optimal parameters. Then, it will be shown through numerical queueing experiments that the proposed strategy indeed it is helpful under the few priority queue regime, but that long flows can be excessively penalized. Finally, extensive large scale packet level simulations in a real data center topology are conducted with Omnet++ discrete-event simulator, in order to validate the results obtained in previous steps. We were able to show FCT performance gains that confirm the validity of our initial intuition. At the same time, we were able to identify downsides of this methodology and provide a possible strategy to overcome them.