research-article

On design of bandwidth scheduling algorithms for multiple data transfers in dedicated networks

Authors:

Qishi WuAuthors Info & Claims

ANCS '08: Proceedings of the 4th ACM/IEEE Symposium on Architectures for Networking and Communications Systems

Pages 151 - 160

https://doi.org/10.1145/1477942.1477970

Published: 06 November 2008 Publication History

Abstract

The significance of high-performance dedicated networks has been well recognized due to the rapidly increasing number of large-scale applications that require high-speed data transfer. Efficient algorithms are needed for path computation and bandwidth scheduling in dedicated networks to improve the utilization of network resources and meet diverse user requests. We consider two periodic bandwidth scheduling problems: multiple data transfer allocation (MDTA) and multiple fixed-slot bandwidth reservation (MFBR), both of which schedule a number of user requests accumulated in a certain period. MDTA is to assign multiple data transfer requests on several pre-specified network paths to minimize the total data transfer end time, while MFBR is to satisfy multiple bandwidth reservation requests, each of which specifies a bandwidth and a time slot. For MDTA, we design an optimal algorithm and provide its correctness proof; for MFBR, we prove it to be NP-complete and propose a heuristic algorithm, Minimal Bandwidth and Distance Product Algorithm (MBDPA). Extensive simulation results illustrate the performance superiority of the proposed MBDPA over a greedy heuristic approach and provide valuable insight into the advantage of periodic bandwidth scheduling over instant bandwidth scheduling.

References

[1]

Terascale Supernova Initiative (TSI). http://www.phy.ornl.gov/tsi.

[2]

Terascale High-Fidelity Simulations of Turbulent Combustion with Detailed Chemistry. http://scidac.psc.edu.

[3]

National Leadership Computing Facility (NLCF). http://www.ccs.ornl.gov/nlcf.

[4]

UCLP: User Controlled LightPath Provisioning. http://phi.badlab.crc.ca/uclp.

[5]

Enlightened Computing. http://www.enlightenedcomputing.org.

[6]

DRAGON: Dynamic Resource Allocation via GMPLS Optical Networks. http://dragon.maxgigapop.net.

[7]

JGN II: Advanced Network Testbed for Research and Development. http://www.jgn.nict.go.jp.

[8]

Geant2. http://www.geant2.net.

[9]

OSCARS: On-demand Secure Circuits and Advance Reservation System. http://www.es.net/oscars.

[10]

HOPI: Hybrid Optical and Packet Infrastructure. http://networks.internet2.edu/hopi.

[11]

GENI: Global Environment for Network Innivations. http://www.geni.net.

[12]

bbcp. http://www.slac.stanford.edu/~abh/bbcp.

[13]

Tsunami. http://newsinfo.iu.edu/news/page/normal/588.html.

[14]

Z. Cao, Z. Wang, and E. Zegura. Performance of hashing-based schemes for internet load balancing. volume 1, pages 332--341 vol. 1, 2000.

[15]

C. Cetinkaya and E. Knightly. Opportunistic traffic scheduling over multiple network paths. volume 3, pages 1928--1937 vol. 3, Mar. 2004.

[16]

CHEETAH: Circuit-switched High-speed End-to-End Transport ArcHitecture, http://www.ece.virginia.edu/cheetah.

[17]

R. Cohen, N. Fazlollahi, and D. Starobinski. Graded channel reservation with path switching in ultra high capacity networks. In Proc. of Broadnets, San Jose, CA, 2006.

[18]

S. Floyd. Highspeed tcp for large congestion windows, Feb., 2003. Internet Draft.

Digital Library

[19]

S. Ganguly, A. Sen, G. Xue, B. Hao, and B. Shen. Optimal routing for fast transfer of bulk data files in time-varying networks. In Proc. of IEEE Int. Conf. on Communications, 2004.

[20]

M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman and Company, New York, 1979.

Digital Library

[21]

S. Gorinsky and N. Rao. Dedicated channels as an optimal network support for effective transfer of massive data. In INFOCOM 2006 Workshop on High-Speed Networks, 2006.

[22]

W. Grimmell and N. Rao. On source-based route computation for quickest paths under dynamic bandwidth constraints. Int. J. on Foundations of Computer Science, 14(3):503--523, 2003.

[23]

Y. Gu, X. Hong, M. Mazzucco, and R. L. Grossman. SABUL: A high performance data transfer protocol, 2004. submitted to IEEE Communications Letters.

[24]

R. Guerin and A. Orda. Networks with advance reservations: the routing perspective. In Proc. of the 19th IEEE INFOCOM, 2000.

[25]

E. He, J. Leigh, O. Yu, and T. DeFanti. Reliable blast udp: predictable high performance bulk data transfer. In IEEE Int. Conf. on Cluster Computing, Chicago, Illinois, Sep. 23--26 2002.

Digital Library

[26]

E. He, P. Primet, and M. Welzl. A survey of transport protocols other than "standard" tcp. Global Grid Form Report GFD-I.055.

[27]

Y. Lin, Q. Wu, N. Rao, and M. Zhu. On design of scheduling algorithms for advance bandwidth reservation in dedicated networks. In The 2008 INFOCOM High-Speed Networks Workshop, Phoenix, Arizona, Apr. 13 2008.

Digital Library

[28]

M. H. Phùng, K. C. Chua, G. Mohan, M. Motani, T. C. Wong, and P. Y. Kong. On ordered scheduling for optical burst switching. Computer Networks, 48(6):891--909, 2005.

Digital Library

[29]

N. Rao, W. Wing, S. Carter, and Q. Wu. Ultrascience net: Network testbed for large-scale science applications. IEEE Communications Magazine, 43(11):s12--s17, 2005. An expanded version available at www.csm.ornl.gov/ultranet.

Digital Library

[30]

N. Rao, Q. Wu, S. Carter, W. Wing, D. G. A. Banerjee, and B. Mukherjee. Control plane for advance bandwidth scheduling in ultra high-speed networks. In INFOCOM 2006 Workshop on Terabits Networks, 2006.

[31]

S. Sahni, N. Rao, S. Ranka, Y. Li, E. Jung, and N. Kamath. Bandwidth scheduling and path computation algorithms for connection-oriented networks. In Proc. of Int. Conf. on Networking, 2007.

Digital Library

[32]

B. Shen, B. Hao, and A. Sen. On multipath routing using widest pair of disjoint paths. In Proc. of Workshop on High Performance Switching and Routing, pages 134--140, 2004.

[33]

R. Stewart and Q. Xie. Stream control transmission protocol. www.ietf.org/rfc/rfc2960.txt, Oct. 2000. IETF RFC 2960.

Digital Library

[34]

M. Veeraraghavan, H. Lee, E. Chong, and H. Li. A varying-bandwidth list scheduling heuristic for file transfers. In Proc. of IEEE Int. Conf. on Communications, 2004.

[35]

Q. Wu and N. Rao. A class of reliable udp-based transport protocols based on stochastic approximation. In Proc. of the 24th IEEE INFOCOM, Miami, Florida, Mar. 13--17 2005.

[36]

Q. Wu and N. Rao. Protocol for high-speed data transport over dedicated channels. In Proc. of the 3rd Int. Workshop on Protocols for Fast Long-Distance Networks, pages 155--162, Feb. 3--4 2005.

[37]

Y. Xiong, M. Vandenhoute, and H. Cankaya. Control architecture in optical burst-switched wdm networks. IEEE J. on Selected Areas in Communications, 18(10):1838--1851, Oct 2000.

Digital Library

[38]

Z. Zhang, Z. Duan, and Y. Hou. Decoupling qos control from core routers: A novel bandwidth broker architecture for scalable support of guaranteed services. In Proc. of ACM SIGCOMM, 2000.

Digital Library

[39]

X. Zheng, A. Mudambi, and M. Veeraraghavan. Frtp: Fixed rate transport protocol -- a modified version of sabul for end-to-end circuits. In Proc. of Broadnets, 2004.

Cited By

Huo KWang YJi CYue CWu CZhu M(2023)On multi-path bandwidth scheduling for multiple fixed-slot reservations in high-performance networksComputer Communications10.1016/j.comcom.2023.09.023Online publication date: Sep-2023
https://doi.org/10.1016/j.comcom.2023.09.023
Hou AWu CDuan QQuan DZuo LLi YZhu MFang D(2021)SDN-based bandwidth scheduling for prioritized data transfer between data centersCluster Computing10.1007/s10586-021-03364-725:4(3019-3034)Online publication date: 19-Aug-2021
https://doi.org/10.1007/s10586-021-03364-7
Zuo L(2020)Intelligent and Flexible Bandwidth Scheduling for Data Transfers in Dedicated High-Performance NetworksIEEE Transactions on Network and Service Management10.1109/TNSM.2020.301288817:4(2364-2379)Online publication date: Dec-2020
https://doi.org/10.1109/TNSM.2020.3012888
Show More Cited By

Index Terms

On design of bandwidth scheduling algorithms for multiple data transfers in dedicated networks
1. Networks
  1. Network architectures
  2. Network properties
    1. Network range
      1. Local area networks
      2. Wide area networks

Recommendations

Advance Bandwidth Scheduling Algorithms in Dedicated Networks

An increasing number of high performance research network testbeds and production networks have the capability of provisioning dedicated channels for high speed data transfer in support of large scale scientific applications. Each dedicated channel in ...
Fast and Efficient Bandwidth Reservation Algorithms for Dynamic Network Provisioning

Large-scale collaborative e-science requires fast and reliable data transfer with guaranteed performance, which is made possible by reserving bandwidth as needed in advance in high-performance networks. In scientific applications, users typically know ...
Fault-tolerant bandwidth reservation strategies for data transfers in high-performance networks

Many next-generation e-science applications require fast and reliable transfer of large volumes of data with guaranteed performance, which is typically enabled by the bandwidth reservation service in high-performance networks. One prominent issue in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ANCS '08: Proceedings of the 4th ACM/IEEE Symposium on Architectures for Networking and Communications Systems

November 2008

191 pages

ISBN:9781605583464

DOI:10.1145/1477942

General Chair:
Mark Franklin
Washington University in St. Louis
,
Program Chairs:
D. K. Panda
Ohio State University
,
Dimitri Stiliadis
Bell Laboratory

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 November 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

ANCS '08

Sponsor:

ANCS '08: Symposium on Architecture for Networking and Communications Systems

November 6 - 7, 2008

California, San Jose

Acceptance Rates

ANCS '08 Paper Acceptance Rate 17 of 67 submissions, 25%;

Overall Acceptance Rate 88 of 314 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
310
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 29 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Huo KWang YJi CYue CWu CZhu M(2023)On multi-path bandwidth scheduling for multiple fixed-slot reservations in high-performance networksComputer Communications10.1016/j.comcom.2023.09.023Online publication date: Sep-2023
https://doi.org/10.1016/j.comcom.2023.09.023
Hou AWu CDuan QQuan DZuo LLi YZhu MFang D(2021)SDN-based bandwidth scheduling for prioritized data transfer between data centersCluster Computing10.1007/s10586-021-03364-725:4(3019-3034)Online publication date: 19-Aug-2021
https://doi.org/10.1007/s10586-021-03364-7
Zuo L(2020)Intelligent and Flexible Bandwidth Scheduling for Data Transfers in Dedicated High-Performance NetworksIEEE Transactions on Network and Service Management10.1109/TNSM.2020.301288817:4(2364-2379)Online publication date: Dec-2020
https://doi.org/10.1109/TNSM.2020.3012888
Hou AWu CZuo LQuan DLi YZhu MDuan QFang D(2019)Co-Scheduling of Advance and Immediate Bandwidth Reservations for Inter-Data Center Transfer2019 IEEE/ACM Innovating the Network for Data-Intensive Science (INDIS)10.1109/INDIS49552.2019.00009(25-35)Online publication date: Nov-2019
https://doi.org/10.1109/INDIS49552.2019.00009
Lin CBi YHan GYang JZhao HLiu Z(2018)Scheduling for Time-Constrained Big-File Transfer Over Multiple Paths in Cloud ComputingIEEE Transactions on Emerging Topics in Computational Intelligence10.1109/TETCI.2017.27556922:1(25-40)Online publication date: Feb-2018
https://doi.org/10.1109/TETCI.2017.2755692
Hou AWu CFang DWang YWang M(2017)Bandwidth scheduling for big data transfer using multiple fixed node-disjoint pathsJournal of Network and Computer Applications10.1016/j.jnca.2016.12.01185:C(47-55)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1016/j.jnca.2016.12.011
Zuo LZhu M(2016)Improved Scheduling Algorithms for Single-Path Multiple Bandwidth Reservation Requests2016 IEEE Trustcom/BigDataSE/ISPA10.1109/TrustCom.2016.0259(1692-1699)Online publication date: Aug-2016
https://doi.org/10.1109/TrustCom.2016.0259
Hou AWu CFang DWang YWang MWang TZhang X(2016)Bandwidth scheduling with multiple variable node-disjoint paths in high-performance networks2016 IEEE 35th International Performance Computing and Communications Conference (IPCCC)10.1109/PCCC.2016.7820600(1-4)Online publication date: Dec-2016
https://doi.org/10.1109/PCCC.2016.7820600
Liudong Zuo Zhu M(2015)Concurrent Bandwidth Reservation Strategies for Big Data Transfers in High-Performance NetworksIEEE Transactions on Network and Service Management10.1109/TNSM.2015.243035812:2(232-247)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1109/TNSM.2015.2430358
Wang YWu CHou APeng WXu SShi M(2015)On periodic scheduling of fixed-slot bandwidth reservations for big data transferProceedings of the 2015 IEEE 40th Conference on Local Computer Networks (LCN 2015)10.1109/LCN.2015.7366374(587-594)Online publication date: 26-Oct-2015
https://dl.acm.org/doi/10.1109/LCN.2015.7366374
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents