Improved scheduling algorithms for single-path multiple bandwidth reservation requests

Liudong Zuo, Michelle Zhu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationProceedings - 15th IEEE International Conference on Trust, Security and Privacy in Computing and Communications, 10th IEEE International Conference on Big Data Science and Engineering and 14th IEEE International Symposium on Parallel and Distributed Processing with Applications, IEEE TrustCom/BigDataSE/ISPA 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1692-1699
Number of pages8
ISBN (Electronic)9781509032051
DOIs
StatePublished - 1 Jan 2016
EventJoint 15th IEEE International Conference on Trust, Security and Privacy in Computing and Communications, 10th IEEE International Conference on Big Data Science and Engineering and 14th IEEE International Symposium on Parallel and Distributed Processing with Applications, IEEE TrustCom/BigDataSE/ISPA 2016 - Tianjin, China
Duration: 23 Aug 201626 Aug 2016

Other

OtherJoint 15th IEEE International Conference on Trust, Security and Privacy in Computing and Communications, 10th IEEE International Conference on Big Data Science and Engineering and 14th IEEE International Symposium on Parallel and Distributed Processing with Applications, IEEE TrustCom/BigDataSE/ISPA 2016
CountryChina
CityTianjin
Period23/08/1626/08/16

Fingerprint

Scheduling algorithms
Bandwidth
Data transfer
Scheduling
Network performance
Heuristic algorithms
Computational complexity
Throughput
Data storage equipment

Keywords

  • Bandwidth reservation
  • Bandwidth scheduling
  • Big data
  • High-performance networks
  • QoS

Cite this

Zuo, L., & Zhu, M. (2016). Improved scheduling algorithms for single-path multiple bandwidth reservation requests. In Proceedings - 15th IEEE International Conference on Trust, Security and Privacy in Computing and Communications, 10th IEEE International Conference on Big Data Science and Engineering and 14th IEEE International Symposium on Parallel and Distributed Processing with Applications, IEEE TrustCom/BigDataSE/ISPA 2016 (pp. 1692-1699). [7847142] Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/TrustCom.2016.0259
Zuo, Liudong ; Zhu, Michelle. / Improved scheduling algorithms for single-path multiple bandwidth reservation requests. Proceedings - 15th IEEE International Conference on Trust, Security and Privacy in Computing and Communications, 10th IEEE International Conference on Big Data Science and Engineering and 14th IEEE International Symposium on Parallel and Distributed Processing with Applications, IEEE TrustCom/BigDataSE/ISPA 2016. Institute of Electrical and Electronics Engineers Inc., 2016. pp. 1692-1699
@inproceedings{4d89bc8c4b5d491fb414d109fdb069e9,
title = "Improved scheduling algorithms for single-path multiple bandwidth reservation requests",
abstract = "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.",
keywords = "Bandwidth reservation, Bandwidth scheduling, Big data, High-performance networks, QoS",
author = "Liudong Zuo and Michelle Zhu",
year = "2016",
month = "1",
day = "1",
doi = "10.1109/TrustCom.2016.0259",
language = "English",
pages = "1692--1699",
booktitle = "Proceedings - 15th IEEE International Conference on Trust, Security and Privacy in Computing and Communications, 10th IEEE International Conference on Big Data Science and Engineering and 14th IEEE International Symposium on Parallel and Distributed Processing with Applications, IEEE TrustCom/BigDataSE/ISPA 2016",
publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

Zuo, L & Zhu, M 2016, Improved scheduling algorithms for single-path multiple bandwidth reservation requests. in Proceedings - 15th IEEE International Conference on Trust, Security and Privacy in Computing and Communications, 10th IEEE International Conference on Big Data Science and Engineering and 14th IEEE International Symposium on Parallel and Distributed Processing with Applications, IEEE TrustCom/BigDataSE/ISPA 2016., 7847142, Institute of Electrical and Electronics Engineers Inc., pp. 1692-1699, Joint 15th IEEE International Conference on Trust, Security and Privacy in Computing and Communications, 10th IEEE International Conference on Big Data Science and Engineering and 14th IEEE International Symposium on Parallel and Distributed Processing with Applications, IEEE TrustCom/BigDataSE/ISPA 2016, Tianjin, China, 23/08/16. https://doi.org/10.1109/TrustCom.2016.0259

Improved scheduling algorithms for single-path multiple bandwidth reservation requests. / Zuo, Liudong; Zhu, Michelle.

Proceedings - 15th IEEE International Conference on Trust, Security and Privacy in Computing and Communications, 10th IEEE International Conference on Big Data Science and Engineering and 14th IEEE International Symposium on Parallel and Distributed Processing with Applications, IEEE TrustCom/BigDataSE/ISPA 2016. Institute of Electrical and Electronics Engineers Inc., 2016. p. 1692-1699 7847142.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Improved scheduling algorithms for single-path multiple bandwidth reservation requests

AU - Zuo, Liudong

AU - Zhu, Michelle

PY - 2016/1/1

Y1 - 2016/1/1

N2 - 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.

AB - 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.

KW - Bandwidth reservation

KW - Bandwidth scheduling

KW - Big data

KW - High-performance networks

KW - QoS

UR - http://www.scopus.com/inward/record.url?scp=85015159104&partnerID=8YFLogxK

U2 - 10.1109/TrustCom.2016.0259

DO - 10.1109/TrustCom.2016.0259

M3 - Conference contribution

AN - SCOPUS:85015159104

SP - 1692

EP - 1699

BT - Proceedings - 15th IEEE International Conference on Trust, Security and Privacy in Computing and Communications, 10th IEEE International Conference on Big Data Science and Engineering and 14th IEEE International Symposium on Parallel and Distributed Processing with Applications, IEEE TrustCom/BigDataSE/ISPA 2016

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

Zuo L, Zhu M. Improved scheduling algorithms for single-path multiple bandwidth reservation requests. In Proceedings - 15th IEEE International Conference on Trust, Security and Privacy in Computing and Communications, 10th IEEE International Conference on Big Data Science and Engineering and 14th IEEE International Symposium on Parallel and Distributed Processing with Applications, IEEE TrustCom/BigDataSE/ISPA 2016. Institute of Electrical and Electronics Engineers Inc. 2016. p. 1692-1699. 7847142 https://doi.org/10.1109/TrustCom.2016.0259