Dynamic embedding of workflow requests for bandwidth efficiency in data centers

In this paper, we address the problem of embedding dynamically-arriving workflow requests in data centers. Workflows pose challenges due to data precedence and time disjointness among tasks, thus driving the need for intelligent methods to embed workflows in data centers while improving the bandwidth efficiency as well as guaranteeing the application performance. We first formulate an integer programming optimization model for the embedding problem that minimizes the amount of bandwidth required for workflow execution. We then develop two algorithms namely Critical Path Workflow Embedding (CPWE) and Edge Priority Workflow Embedding (EPWE) to solve this problem. We consider two data center network architectures: packet switching electrical networks and circuit switching optical wavelength division multiplexed (WDM) networks. While WDM-based optical networks have much larger bandwidth capacity to meet the ever-growing traffic demand in data centers, they pose challenges due to wavelength continuity constraint and the nature of circuit switching. We thus additionally propose methods for selecting appropriate Top-of-the-Rack (ToR) switches and wavelengths during the embedding process so as to increase the chance of accommodating many requests that span over multiple ToRs. We evaluate CPWE and EPWE through comprehensive simulations. The results show that CPWE and EPWE significantly reduce the bandwidth required for a workflow request by up to 66% for random workflows and 80% for realistic-application workflows compared to baseline algorithms. The results also show that the proposed methods for ToR selection and wavelength selection in optical data centers outperform other methods by reducing the rejection ratio by up to 47% with dynamic reconfiguration of lightpaths and 40% with incremental configuration of lightpaths.