Efficient algorithms for scheduling multiple bulk data transfers in inter-datacenter networks

摘要

Bulk data transfers, such as backups and propagation of bulky updates, account for a large portion of the inter-datacenter traffic. These bulk transfers consume massive bandwidth and further increase the operational cost of datacenters. The advent of store-and-forward transfer mode offers the opportunity for cloud provider companies to transfer bulk data by utilizing dynamic leftover bandwidth resources. In this paper, we study the multiple bulk data transfers scheduling problem in inter-datacenter networks with dynamic link capacities. To improve the network utilization while guaranteeing fairness among requests, we employ the max-min fairness and aim at computing the lexicographically maximized solution. Leveraging the time-expanded technique, the problem in dynamic networks is formulated as a static multi-flow model. Then, we devise an optimal algorithm to solve it simultaneously from routing assignments and bandwidth allocation. To further reduce the computational cost, we propose to select an appropriate number of disjoint paths for each request. Extensive simulations are conducted on a real datacenter topology and prove that (i) benefiting from max-min fairness, the network utilization is significantly improved while honoring each individual performance; (ii) a small number of disjoint paths per request are sufficient to obtain the near optimal allocation within practical execution time. Copyright (c) 2013 John Wiley & Sons, Ltd.