Advance bandwidth scheduling in high-speed dedicated networks
Qishi Wu, Yunyue Lin · 2011
An increasing number of high-performance networks provision dedicated connections through circuit switching or MPLS/GMPLS techniques to support large data transfer. The link bandwidths in such networks are typically shared by multiple users through advance reservation, resulting in varying bandwidth availability in future time. We investigate a comprehensive set of advance bandwidth scheduling problems that are categorized into the following four classes. 1) Basic bandwidth scheduling. We formulate four types of problems by exhausting the combinations of different path and bandwidth constraints: fixed/variable path with fixed/variable bandwidth (F/VP-F/VB) with the same objective to minimize the data transfer end time for a given date size. For VPFB and VPVB, we further consider two subcases where the path switching delay is negligible or non-negligible. We propose an optimal algorithm for each of these problems except for FPVB and VPVB with non-negligible path switching delay, which are proved to be NP-complete and non-approximable, and then tackled by heuristics. 2) Bandwidth scheduling in LCC-overlays. We investigate two problems in this class: fixed-bandwidth path (FBP) and varying-bandwidth path (VBP) with the same objective to minimize the data transfer end time for a given data size. We prove both problems to be NP-complete and non-approximable, and propose heuristic algorithms using a gradual relaxation procedure on the maximum number of links from each LCC allowed for path computation. 3) Distributed bandwidth scheduling. We propose distributed algorithms to meet four basic bandwidth scheduling requests: fixed bandwidth in a fixed slot, highest bandwidth in a fixed slot, first slot with fixed bandwidth and duration, and all slots with fixed bandwidth and duration. These algorithms are developed through a rigorous extension of the classical breadth first search and Bellman-Ford algorithms to a complete distributed manner. 4) Periodical bandwidth scheduling. We consider two problems in this class: multiple data transfer allocation (MDTA) and multiple fixed-slot bandwidth reservation (MFBR), both of which schedule multiple user requests accumulated in a certain time window. For MDTA, we design an optimal algorithmand provide its correctness proof; while forMFBR, we prove it to be NP-complete and propose a heuristic algorithm.