Researches On Fairness-oriented Flow Scheduling Technology In Data Centers

In recent years, with the rise of cloud computing, more and more interactive appli-cations are deployed to data centers in a distributed manner. These applications tend to have strict latency requirements for the need of user-friendliness. However, the grim fact is that currently there is a serious latency issues in data centers. Since there are large-scale multi-task concurrent communications between servers in data centers, that’s a great challenge to the current flow scheduling technologies. And applications in data centers usually adopt the partition/aggregate work pattern, the final response relies on the latest flow. Therefore, there is a significant impact of the tail latency to the response time of user requests. Therefore, how to reduce latency in data centers, especially the tail latency, attracts great attention of the industry.Currently, the flow scheduling technologies in data centers include three cate-gories:fair sharing scheduling policy, priority-based scheduling policy and multi-path flow scheduling. The first category of these works adopt the fair share scheduling pol-icy, trying to achieve short delay by reducing the switch queue length. Another type of works schedule flow with strict latency requirements requirements first to improve the performance of flow scheduling. Specially, the deadline-based flow scheduling sched-ules flows with the earliest deadline first to minimize the number of delayed flows, and size-based flow scheduling attempts to accelerate tasks by reducing the average flow completion time, assuming that short flows usually have more strict latency re-quirements. In face of the multi-path nature in data centers, those works on multi-path flow scheduling target to achieve load balancing. They distribute the load as much as possible through various equal-cost paths, which could effectively reduce the level of congestion in the core and aggregation layers.Traditional flow scheduling protocols use the fair share scheduling policy to share the throughput of congestion links, which results in blocking of long flows. Even though the shortest remaining processing time scheduling policy can minimize the av-erage flow completion time, it may cause starvation of long flows. Thus, by analyzing the communication pattern in data centers, we proposed a metric called expansion ra-tio representing the ratio of actual flow completion time to optimal completion time, which can efficiently resolve the inherent contradiction between the average latency and tail latency. Furthermore, we propose a central scheduling algorithm to reduce the expansion ratio of completed flows. In this algorithm, short flows are usually sched-uled before long flows, and the priority of long flows become higher with the increase of waiting time.In order to minimize the expansion ratio of flows, we design a distributed rate control strategy. This strategy defines different kinds of sending packets and acknowl-edgement packets, and uses these packets to carry information about flow state and rate control. On this basis, we design the MERP sender, the MERP receiver and the MERP switch to achieve a priority-based flow scheduling by using the explicit rate control. Through a large scale of ns2 simulation, the results show that the rate control strategy based on minimizing the expansion ratio of flows can effectively reduce the completion time of the tail, with a negligible increase of the average flow complete time.Currently, the data centers typically use the Equal-Cost Multipath Routing Mech-anism to reduce the degree of congestion in the core and aggregation layer. It may cause problems of hash collisions, sensibility of flow distribution, lacks of upward feedback. And existing related works of load balancing mainly target to achieve high utilization of link capacity by distributing the load to equal-cost paths. However, high throughput doesn’t essentially result to low latency, therefore we believe that we can only minimize the latency by the combination of the transport control strategy and the load balancing strategy. And, we design a multi-path strategy to reduce latency by greedily reducing the expansion ratio of new flows. Simulation results show that this strategy can both reduce the average flow completion time and the completion time of the tail under different load and the condition of link failure.Finally, we summarize the work of this paper and propose the prospect of future work according to related works.