Improved Scheduling Algorithms for Single-Path Multiple Bandwidth Reservation Requests

摘要

Colossal amounts of data are being generated in extreme-scale e-Sciences with the advent of new computation tools and experimental infrastructures. Such extremely large and complex data sets normally need to be transferred remotely for data storage and analysis. Reserving bandwidth as needed along selected paths in high-performance networks (HPNs) has proved to be an effective way to satisfy the high-demanding requirements of such data transfer. The most common data transfer requirement from users is the data transfer deadline. However, users oftentimes want to achieve other data transfer performance parameters, such as the earliest completion time (ECT) and the shortest duration (SD). For the bandwidth reservation service provider, all bandwidth reservation requests (BRRs) in one batch should be scheduled for high scheduling efficiency and system throughput. In this paper, we study the problem of scheduling all BRRs in one batch while achieving their best average transfer performance on one reservation path in an HPN. Two data transfer performance parameters, ECT and SD, are specifically considered. Because of the limited bandwidth resources of the reservation path, the problems of scheduling all BRRs in one batch on one reservation path while achieving their best average ECT and SD are converted into the problems of scheduling as many BRRs as possible while achieving the average ECT and SD of scheduled BRRs, respectively. We prove these two converted problems as NP-complete problems, and improve two existing heuristic algorithms proposed previously for similar problems. Extensive simulation experiments show the superior scheduling performance of these improved algorithms in terms of several performance metrics.