Abstract : Many large-scale applications in broad science, engineering,and business domains are generating big data, which must betransferred to remote sites for various storage and analysis purposes.Bandwidth reservation services that discover feasible routingoptions over dedicated paths in high-performance networkshave proved to be effective for such big data transfer. In thispaper, we formulate a generic problem of bandwidth schedulingwith two variable node-disjoint paths (BS-2VNDP) by exploringthe flexibility and capacity of multiple data transfer paths. We furtherconsider two variable paths of either fixed or variable bandwidthwith negligible or non-negligible path switching delay, referredto as 2VPFB-0/1 and 2VPVB-0/1, respectively.We prove thatall of these four scheduling problems are NP-complete, and thenpropose a heuristic algorithm for each. For performance comparison,we also design several other heuristic algorithms based on agreedy strategy. These scheduling algorithms are implemented andtested in both simulated and real-life networks, and extensive resultsshow that the proposed heuristic algorithms significantly outperformother algorithms in comparison.
Index terms : Bandwidth scheduling, high-performance networks, node-disjoint paths, switching delay, variable paths.