Research On Equal-Cost Multipath Based Short Flow Accelera- Tion Technique In Data Centers

In recent years, with the development of cloud computing, many interactive services are hosted in data centers, such as retail recommendation systems, web search and social networking. These services impose a strict requirement on latency and the speed of the response from these services has a critical impact on the user experience and the revenue of the services’provider.The interactive services in data centers mostly work in a partition/aggregation pattern, in which aggregation servers split a user request into many small tasks, deliver them to worker servers by short TCP connection, then gather results from these worker servers, and finally combine the results as response for users. Therefore, the completion time of short flows decides the delay users experience. Because latency in host-end is reduced heavily by many advanced optimization techniques, the completion time of short flows is up to their network delay. However, there exist many large TCP flows for tasks like data backup、data mining and virtual machine migration in data centers. These flows own large send window and can change the length of switch queue rapidly, leading to short flows’queuing delay going up quickly. Thus mean completion time of short flows may be 10 times larger than its ideal case.To reduce flow completion times of short flows in data centers, the community has proposed many methods. Some of them notify hosts of the network congestion level by explicit congestion notification in switches, and then adjust the send rate, reducing the queue length of switches; Some of them emulate traditional centralized resource scheduling algorithms in networks and assign higher priority to shorter flows; Some of them load balance the flows between several equal-cost paths; Some of them use two separate short flows to independently undertake the same small task to employ the equal-cost paths and stay away with elephant flows. As a typical replication based short flow acceleration method, RepFlow uses two separate short flows to transfer indepen-dently the data transferred by a short flow before. When either flow is completed, the data is transmitted successfully. Because there exists several equal-cost paths between hosts in data centers, the data transfer is less likely to be blocked by large flows than before.Though these methods achieve good results in reducing mice flows, most of them need modification to switches or host-end TCP stack, making them hard to deploy in data centers. RepFlow can be implemented in application layer, but it has two draw-backs:one is that ECMP (Equal-Cost Multipath Protocol) is likely to route the repli-cated flow and the original one to the same path (i.e., flow path hash collision), resulting in degradation of acceleration performance, the other is that RepFlow creates a replicat-ed flow constantly for each short flow regardless of flow size distribution and network load, which may brings massive bandwidth overhead.To overcome these limitations, we attempt to devise a short flow acceleration method that can be easily deployed by employing equal-cost paths existing in current data centers. In all, our work can be divided into the following two parts:● We propose a new short flow acceleration technique based on redundancy. In designing the SmartRep, we complete the following work:-Firstly, we analyse theoretically the limitations of existing replication based methods thoroughly:there exists path collisions between replicated flows, impairing the short flow acceleration, and constant number of replicated flows can not react to different flow size distribution and network load prop-erly.-Then, we design the path hash collision mechanism HCA. Similar to the traceroute command in linux, HCA sends packets with specified TCP/IP 5-tuple in advance to probe the path flows with the tuple will traverse, ac-cording to ECMP(Equal-Cost Multipath Protocol). After this, HCA selects suitable source ports for replicated flows by testing different source ports, making them traverse different paths.-Lastly, we design the replication assignment mechanism RepNumAssign. justs the total bytes generated by replicated flows by creating different num-ber of replicated flows for short flows with different size. Within the limit of total bytes of replicated flows, RepNumAssign assigns more replicated flows to the short flows contributing most to their completion times.The implementation of SmartRep requires no switch and host-end modification and extensive NS2 simulations show that SmartRep can significantly reduce both mean and tail flow completion times of short flows while keeping overhead quite low and avoiding negative impact on the elephant flows.● To reduce bandwidth overhead and simplify deployment further, we propose path delay probe based short flow acceleration methods PDP. PDP is based on a host-end path control mechanism which changes source ports of flows to manipulate their paths, like HCA. The implementation of this mechanism is transparent to TCP layer and does not require host-end modification. PDP consists of two path delay probe mechanisms:active and passive. The former requests building TCP connections on all the equal-cost paths in the handshaking phase of TCP, but complete the connection building in the path relying first. The latter, also called random rerouting, randomly select one of the other paths for the flow after one of its packet not being acknowledged within a predefined timeout. All of these mechanisms are enforced in the first 100Kb of every flow, so they do not need flow information from applications. Moreover, PDP do not need modification to switches, host-end TCP stack and even applications, so it is easier to deploy in data centers. Extensive NS2 simulations show PDP not only has lower overhead than replication based methods but also achieves similar even lower FCT of short flows than SmartRep.