Bandwidth reservation for data transfers through multiple disjoint paths of dynamic HPNs

Liudong Zuo, Michelle Zhu, Chase Wu, Aiqin Hou, Lei Cao

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

Abstract

Bandwidth reservation was initially designed to provide QoS for real-time multimedia applications, and has been widely used since because of its proved high efficiency and effectiveness. It was recently started being used for big data transfers in high-performance networks from the data generation center to remotely located collaborating sites for data storage, mining and analysis. Most existing work on big data transfer using bandwidth reservation service focuses on addressing various data transfer problems on one or two network paths. In this paper, we study three important problems regarding data transfers using bandwidth reservation through multiple (node-and edge-)disjoint paths in dynamic high-performance networks: (i) achieve the earliest completion time for a given data transfer request through multiple variable disjoint paths, (ii) achieve the earliest completion time for a given data transfer request through multiple fixed disjoint paths with fixed bandwidths, and (iii) achieve the minimum number of fixed disjoint paths with fixed bandwidths to finish the given data transfer by its deadline. We prove all of these problems to be NP-complete and then propose one heuristic algorithm for each. We compare the heuristic algorithms with existing scheduling algorithms, and conduct extensive simulations. The simulation results show that our proposed heuristic algorithms have much better overall scheduling performance.

Original languageEnglish (US)
Title of host publicationProceedings - 21st IEEE International Conference on High Performance Computing and Communications, 17th IEEE International Conference on Smart City and 5th IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2019
EditorsZheng Xiao, Laurence T. Yang, Pavan Balaji, Tao Li, Keqin Li, Albert Zomaya
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2455-2460
Number of pages6
ISBN (Electronic)9781728120584
DOIs
StatePublished - Aug 2019
Event21st IEEE International Conference on High Performance Computing and Communications, 17th IEEE International Conference on Smart City and 5th IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2019 - Zhangjiajie, China
Duration: Aug 10 2019Aug 12 2019

Publication series

NameProceedings - 21st IEEE International Conference on High Performance Computing and Communications, 17th IEEE International Conference on Smart City and 5th IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2019

Conference

Conference21st IEEE International Conference on High Performance Computing and Communications, 17th IEEE International Conference on Smart City and 5th IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2019
CountryChina
CityZhangjiajie
Period8/10/198/12/19

Fingerprint

Data transfer
Bandwidth
Heuristic algorithms
Network performance
Reservation
Scheduling algorithms
Quality of service
Scheduling
Data storage equipment
Heuristic algorithm

All Science Journal Classification (ASJC) codes

  • Information Systems and Management
  • Artificial Intelligence
  • Information Systems
  • Energy Engineering and Power Technology
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computer Science Applications

Keywords

  • bandwidth reservation
  • bandwidth scheduling
  • disjoint paths
  • dynamic provisioning
  • QoS

Cite this

Zuo, L., Zhu, M., Wu, C., Hou, A., & Cao, L. (2019). Bandwidth reservation for data transfers through multiple disjoint paths of dynamic HPNs. In Z. Xiao, L. T. Yang, P. Balaji, T. Li, K. Li, & A. Zomaya (Eds.), Proceedings - 21st IEEE International Conference on High Performance Computing and Communications, 17th IEEE International Conference on Smart City and 5th IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2019 (pp. 2455-2460). [8855448] (Proceedings - 21st IEEE International Conference on High Performance Computing and Communications, 17th IEEE International Conference on Smart City and 5th IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2019). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/HPCC/SmartCity/DSS.2019.00343
Zuo, Liudong ; Zhu, Michelle ; Wu, Chase ; Hou, Aiqin ; Cao, Lei. / Bandwidth reservation for data transfers through multiple disjoint paths of dynamic HPNs. Proceedings - 21st IEEE International Conference on High Performance Computing and Communications, 17th IEEE International Conference on Smart City and 5th IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2019. editor / Zheng Xiao ; Laurence T. Yang ; Pavan Balaji ; Tao Li ; Keqin Li ; Albert Zomaya. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 2455-2460 (Proceedings - 21st IEEE International Conference on High Performance Computing and Communications, 17th IEEE International Conference on Smart City and 5th IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2019).
@inproceedings{2075a33c467649709f148ae4f08d9728,
title = "Bandwidth reservation for data transfers through multiple disjoint paths of dynamic HPNs",
abstract = "Bandwidth reservation was initially designed to provide QoS for real-time multimedia applications, and has been widely used since because of its proved high efficiency and effectiveness. It was recently started being used for big data transfers in high-performance networks from the data generation center to remotely located collaborating sites for data storage, mining and analysis. Most existing work on big data transfer using bandwidth reservation service focuses on addressing various data transfer problems on one or two network paths. In this paper, we study three important problems regarding data transfers using bandwidth reservation through multiple (node-and edge-)disjoint paths in dynamic high-performance networks: (i) achieve the earliest completion time for a given data transfer request through multiple variable disjoint paths, (ii) achieve the earliest completion time for a given data transfer request through multiple fixed disjoint paths with fixed bandwidths, and (iii) achieve the minimum number of fixed disjoint paths with fixed bandwidths to finish the given data transfer by its deadline. We prove all of these problems to be NP-complete and then propose one heuristic algorithm for each. We compare the heuristic algorithms with existing scheduling algorithms, and conduct extensive simulations. The simulation results show that our proposed heuristic algorithms have much better overall scheduling performance.",
keywords = "bandwidth reservation, bandwidth scheduling, disjoint paths, dynamic provisioning, QoS",
author = "Liudong Zuo and Michelle Zhu and Chase Wu and Aiqin Hou and Lei Cao",
year = "2019",
month = "8",
doi = "https://doi.org/10.1109/HPCC/SmartCity/DSS.2019.00343",
language = "English (US)",
series = "Proceedings - 21st IEEE International Conference on High Performance Computing and Communications, 17th IEEE International Conference on Smart City and 5th IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2019",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "2455--2460",
editor = "Zheng Xiao and Yang, {Laurence T.} and Pavan Balaji and Tao Li and Keqin Li and Albert Zomaya",
booktitle = "Proceedings - 21st IEEE International Conference on High Performance Computing and Communications, 17th IEEE International Conference on Smart City and 5th IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2019",
address = "United States",

}

Zuo, L, Zhu, M, Wu, C, Hou, A & Cao, L 2019, Bandwidth reservation for data transfers through multiple disjoint paths of dynamic HPNs. in Z Xiao, LT Yang, P Balaji, T Li, K Li & A Zomaya (eds), Proceedings - 21st IEEE International Conference on High Performance Computing and Communications, 17th IEEE International Conference on Smart City and 5th IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2019., 8855448, Proceedings - 21st IEEE International Conference on High Performance Computing and Communications, 17th IEEE International Conference on Smart City and 5th IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2019, Institute of Electrical and Electronics Engineers Inc., pp. 2455-2460, 21st IEEE International Conference on High Performance Computing and Communications, 17th IEEE International Conference on Smart City and 5th IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2019, Zhangjiajie, China, 8/10/19. https://doi.org/10.1109/HPCC/SmartCity/DSS.2019.00343

Bandwidth reservation for data transfers through multiple disjoint paths of dynamic HPNs. / Zuo, Liudong; Zhu, Michelle; Wu, Chase; Hou, Aiqin; Cao, Lei.

Proceedings - 21st IEEE International Conference on High Performance Computing and Communications, 17th IEEE International Conference on Smart City and 5th IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2019. ed. / Zheng Xiao; Laurence T. Yang; Pavan Balaji; Tao Li; Keqin Li; Albert Zomaya. Institute of Electrical and Electronics Engineers Inc., 2019. p. 2455-2460 8855448 (Proceedings - 21st IEEE International Conference on High Performance Computing and Communications, 17th IEEE International Conference on Smart City and 5th IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2019).

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

TY - GEN

T1 - Bandwidth reservation for data transfers through multiple disjoint paths of dynamic HPNs

AU - Zuo, Liudong

AU - Zhu, Michelle

AU - Wu, Chase

AU - Hou, Aiqin

AU - Cao, Lei

PY - 2019/8

Y1 - 2019/8

N2 - Bandwidth reservation was initially designed to provide QoS for real-time multimedia applications, and has been widely used since because of its proved high efficiency and effectiveness. It was recently started being used for big data transfers in high-performance networks from the data generation center to remotely located collaborating sites for data storage, mining and analysis. Most existing work on big data transfer using bandwidth reservation service focuses on addressing various data transfer problems on one or two network paths. In this paper, we study three important problems regarding data transfers using bandwidth reservation through multiple (node-and edge-)disjoint paths in dynamic high-performance networks: (i) achieve the earliest completion time for a given data transfer request through multiple variable disjoint paths, (ii) achieve the earliest completion time for a given data transfer request through multiple fixed disjoint paths with fixed bandwidths, and (iii) achieve the minimum number of fixed disjoint paths with fixed bandwidths to finish the given data transfer by its deadline. We prove all of these problems to be NP-complete and then propose one heuristic algorithm for each. We compare the heuristic algorithms with existing scheduling algorithms, and conduct extensive simulations. The simulation results show that our proposed heuristic algorithms have much better overall scheduling performance.

AB - Bandwidth reservation was initially designed to provide QoS for real-time multimedia applications, and has been widely used since because of its proved high efficiency and effectiveness. It was recently started being used for big data transfers in high-performance networks from the data generation center to remotely located collaborating sites for data storage, mining and analysis. Most existing work on big data transfer using bandwidth reservation service focuses on addressing various data transfer problems on one or two network paths. In this paper, we study three important problems regarding data transfers using bandwidth reservation through multiple (node-and edge-)disjoint paths in dynamic high-performance networks: (i) achieve the earliest completion time for a given data transfer request through multiple variable disjoint paths, (ii) achieve the earliest completion time for a given data transfer request through multiple fixed disjoint paths with fixed bandwidths, and (iii) achieve the minimum number of fixed disjoint paths with fixed bandwidths to finish the given data transfer by its deadline. We prove all of these problems to be NP-complete and then propose one heuristic algorithm for each. We compare the heuristic algorithms with existing scheduling algorithms, and conduct extensive simulations. The simulation results show that our proposed heuristic algorithms have much better overall scheduling performance.

KW - bandwidth reservation

KW - bandwidth scheduling

KW - disjoint paths

KW - dynamic provisioning

KW - QoS

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

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

U2 - https://doi.org/10.1109/HPCC/SmartCity/DSS.2019.00343

DO - https://doi.org/10.1109/HPCC/SmartCity/DSS.2019.00343

M3 - Conference contribution

T3 - Proceedings - 21st IEEE International Conference on High Performance Computing and Communications, 17th IEEE International Conference on Smart City and 5th IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2019

SP - 2455

EP - 2460

BT - Proceedings - 21st IEEE International Conference on High Performance Computing and Communications, 17th IEEE International Conference on Smart City and 5th IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2019

A2 - Xiao, Zheng

A2 - Yang, Laurence T.

A2 - Balaji, Pavan

A2 - Li, Tao

A2 - Li, Keqin

A2 - Zomaya, Albert

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

Zuo L, Zhu M, Wu C, Hou A, Cao L. Bandwidth reservation for data transfers through multiple disjoint paths of dynamic HPNs. In Xiao Z, Yang LT, Balaji P, Li T, Li K, Zomaya A, editors, Proceedings - 21st IEEE International Conference on High Performance Computing and Communications, 17th IEEE International Conference on Smart City and 5th IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2019. Institute of Electrical and Electronics Engineers Inc. 2019. p. 2455-2460. 8855448. (Proceedings - 21st IEEE International Conference on High Performance Computing and Communications, 17th IEEE International Conference on Smart City and 5th IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2019). https://doi.org/10.1109/HPCC/SmartCity/DSS.2019.00343