Bandwidth scheduling for big data transfer with two variable node-disjoint paths

Many large-scale applications in broad science, engineering, and business domains are generating big data, which must be transferred to remote sites for various storage and analysis purposes. Bandwidth reservation services that discover feasible routing options over dedicated paths in high-performance networks have proved to be effective for such big data transfer. In this paper, we formulate a generic problem of bandwidth scheduling with two variable node-disjoint paths (BS-2VNDP) by exploring the flexibility and capacity of multiple data transfer paths. We further consider two variable paths of either fixed or variable bandwidth with negligible or non-negligible path switching delay, referred to as 2VPFB-0/1 and 2VPVB-0/1, respectively. We prove that all of these four scheduling problems are NP-complete, and then propose a heuristic algorithm for each. For performance comparison, we also design several other heuristic algorithms based on a greedy strategy. These scheduling algorithms are implemented and tested in both simulated and real-life networks, and extensive results show that the proposed heuristic algorithms significantly outperform other algorithms in comparison.