Joint optimization of task mapping and routing for service provisioning in distributed datacenters

Service provisioning has been widely regarded as a critical issue to quality-of-service (QoS) of cloud services in datacenters. Conventional studies on service provisioning mainly focus on task mapping, i.e., how to distribute the service-oriented tasks onto the servers to achieve different goals, e.g., makespan minimization. In distributed datacenters, a task is usually routed from its generation point (i.e., control room) to the designated server within a datacenter network. Since the routing delay also has a deep influence on the task makespan, we are motivated to study how to minimize the maximum makespan of all tasks in a duty period by joint optimization of both task mapping and routing. It is formulated as an integer programming with quadratic constraints (IPQC) problem and proved as NP-hard. To tackle the computational complexity of solving IPQC, a heuristic algorithm with polynomial time is proposed. Extensive simulation results show that it performs close to the optimal one and outperforms existing algorithms significantly.