research-article

Public Access

An elegant sufficiency: load-aware differentiated scheduling of data transfers

Authors:

Rajkumar Kettimuthu,

Gayane Vardoyan,

Ian FosterAuthors Info & Claims

SC '15: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis

Article No.: 46, Pages 1 - 12

https://doi.org/10.1145/2807591.2807660

Published: 15 November 2015 Publication History

Abstract

We investigate the file transfer scheduling problem, where transfers among different endpoints must be scheduled to maximize pertinent metrics. We propose two new algorithms that exploit the fact that the aggregate bandwidth obtained over a network or at a storage system tends to increase with the number of concurrent transfers---but only up to a certain limit. The first algorithm, SEAL, uses runtime information and data-driven models to approximate system load and adapt transfer schedules and concurrency so as to maximize performance while avoiding saturation. We implement this algorithm using GridFTP as the transfer protocol and evaluate it using real transfer logs in a production WAN environment. Results show that SEAL can improve average slowdowns and turnaround times by up to 25% and worst-case slowdown and turnaround times by up to 50%, compared with the best-performing baseline scheme. Our second algorithm, STEAL, further leverages user-supplied categorization of transfers as either "interactive" (requiring immediate processing) or "batch" (less time-critical). Results show that STEAL reduces the average slowdown of interactive transfers by 63% compared to the best-performing baseline and by 21% compared to SEAL. For batch transfers, compared to the best-performing baseline, STEAL improves by 18% the utilization of the bandwidth unused by interactive transfers. By elegantly ensuring a sufficient, but not excessive, allocation of concurrency to the right transfers, we significantly improve overall performance despite constraints.

References

[1]

K. Aida, H. Kasahara, and S. Narita. Job scheduling scheme for pure space sharing among rigid jobs. In Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, IPPS/SPDP '98, pages 98--121, London, UK, 1998. Springer-Verlag.

Digital Library

[2]

W. Allcock. GridFTP protocol specification (Global Grid Forum recommendation GFD.20), 2003.

[3]

W. Allcock, J. Bresnahan, R. Kettimuthu, M. Link, C. Dumitrescu, I. Raicu, and I. Foster. The Globus Striped GridFTP Framework and Server. In Proceedings of the 2005 ACM/IEEE Conference on Supercomputing, SC '05, pages 54--, Washington, DC, USA, 2005. IEEE Computer Society.

Digital Library

[4]

B. Allen, J. Bresnahan, L. Childers, I. Foster, G. Kandaswamy, R. Kettimuthu, J. Kordas, M. Link, S. Martin, K. Pickett, and S. Tuecke. Software as a service for data scientists. Commun. ACM, 55(2):81--88, Feb. 2012.

Digital Library

[5]

BaBar Copy. http://slac.stanford.edu/~abh/bbcp/.

[6]

G. Bell and M. Ernst. HEP Community Summer Study 2013 Computing Frontier: Networking. In Snowmass'2013.

[7]

Belle-II Experiment Network Requirements, Oct. 2012. http://www.osti.gov/scitech/servlets/purl/1171367.

[8]

Biological and Environmental Research Network Requirements, Nov. 2012. http://www.es.net/assets/pubs_presos/BER-Net-Req-Review-2012-Final-Report.pdf.

[9]

K. Bergman, V. Chan, D. Kilper, I. Monga, G. Porter, and K. Rauschenbach. Scaling terabit networks: Breaking through capacity barriers and lowering cost with new architectures and technologies. NSF Workshop, 2013.

[10]

User facilities of the Office of Basic Energy Sciences, 2009. http://science.energy.gov/~/media/bes/suf/pdf/BES_Facilities.pdf.

[11]

Basic Energy Sciences Network Requirements Workshop, September 2010 - Final Report. http://www.es.net/assets/Uploads/BES-Net-Req-Workshop-2010-Final-Report.pdf.

[12]

Office of Science and Technology Policy, Executive Office of the President. Fact Sheet: Big Data Across the Federal Government. Washington, D.C., Mar. 29, 2012. https://www.whitehouse.gov/sites/default/files/microsites/ostp/big_data_fact_sheet_final.pdf.

[13]

TCP backing off due to burstiness. http://fasterdata.es.net/as sets/fasterdata/Using-tc-with-OSCARS-curcuits.pdf.

[14]

Z. Cai, V. Kumar, and K. Schwan. IQ-Paths: Self-regulating data streams across network overlays. In Proceedings of the 15th IEEE International Symposium on High Performance Distributed Computing, 2006.

[15]

C. Castillo, G. Rouskas, and K. Harfoush. On the design of online scheduling algorithms for advance reservations and QoS in Grids. In IEEE International Parallel and Distributed Processing Symposium (IPDPS 2007), pages 1--10, March 2007.

[16]

A. Clematis, A. Corana, D. D'Agostino, A. Galizia, and A. Quarati. Job-resource matchmaking on Grid through two-level benchmarking. Future Gener. Comput. Syst., 26(8):1165--1179, Oct. 2010.

Digital Library

[17]

E. G. Coffman, Jr., M. R. Garey, D. S. Johnson, and A. S. LaPaugh. Scheduling file transfers in a distributed network. In Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing, PODC '83, pages 254--266, New York, NY, USA, 1983. ACM.

Digital Library

[18]

B. Cohen. Incentives build robustness in bittorrent. In 1st International Workshop on Economics of P2P Systems, June 2003.

[19]

dcache GridFTP. http://trac.dcache.org/wiki/gridftp.

[20]

DOE data crosscutting requirements review, 2013. http://science.energy.gov/~/media/ascr/pdf/program-documents/docs/ASCR_DataCrosscutting2_8_28_13.pdf.

[21]

DOE High Performance Computing Operational Review, 2014. http://www.osti.gov/scitech/servlets/purl/1163236.

[22]

Data Transfer Nodes. http://fasterdata.es.net/science-dmz/DTN/.

[23]

ESnet Strategic Plan. http://www.es.net/assets/Uploads/ESnet-Strategic-Plan-March-2-2013.pdf.

[24]

D. G. Feitelson, L. Rudolph, and U. Schwiegelshohn. Parallel job scheduling -- a status report. In Proceedings of the 10th International Conference on Job Scheduling Strategies for Parallel Processing, JSSPP'04, pages 1--16, Berlin, Heidelberg, 2005. Springer-Verlag.

Digital Library

[25]

D. G. Feitelson, L. Rudolph, U. Schwiegelshohn, K. C. Sevcik, and P. Wong. Theory and practice in parallel job scheduling. In Proceedings of the Job Scheduling Strategies for Parallel Processing, IPPS '97, pages 1--34, London, UK, 1997. Springer-Verlag.

Digital Library

[26]

J. Feng, L. Cui, G. Wasson, and M. Humphrey. Toward seamless Grid data access: Design and implementation of GridFTP on .net. In Proceedings of the 6th IEEE/ACM International Workshop on Grid Computing, GRID '05, pages 164--171, Washington, DC, USA, 2005. IEEE Computer Society.

Digital Library

[27]

I. Foster, M. Fidler, A. Roy, V. Sander, and L. Winkler. End-to-end quality of service for high-end applications. Comput. Commun., 27(14):1375--1388, Sept. 2004.

Digital Library

[28]

A. Giersch, Y. Robert, and F. Vivien. Scheduling tasks sharing files from distributed repositories. In M. Danelutto, M. Vanneschi, and D. Laforenza, editors, Euro-Par 2004 Parallel Processing, volume 3149 of Lecture Notes in Computer Science, pages 246--253. Springer Berlin Heidelberg, 2004.

[29]

A. Goel, M. R. Henzinger, S. Plotkin, and E. Tardos. Scheduling data transfers in a network and the set scheduling problem. In Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing, STOC '99, pages 189--197, New York, NY, USA, 1999. ACM.

Digital Library

[30]

GridFTP Usage Stats Collection. http://toolkit.globus.org/toolkit/docs/6.0/gridftp/admin/#gridftp-usage.

[31]

Y. Gu and R. L. Grossman. UDT: UDP-based data transfer for high-speed wide area networks. Comput. Netw., 51(7):1777--1799, May 2007.

Digital Library

[32]

C. Guok, D. Robertson, M. Thompson, J. Lee, B. Tierney, and W. Johnston. Intra and Interdomain Circuit Provisioning Using the OSCARS Reservation System. In 3rd International Conference on Broadband Communications, Networks, and Systems, 2006.

[33]

S. Habib, V. Morozov, H. Finkel, A. Pope, K. Heitmann, K. Kumaran, T. Peterka, J. Insley, D. Daniel, P. Fasel, N. Frontiere, and Z. Lukić. The universe at extreme scale: Multi-petaflop sky simulation on the bg/q. In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, SC '12, pages 4:1--4:11, Los Alamitos, CA, USA, 2012. IEEE Computer Society Press.

Digital Library

[34]

High Energy & Nuclear Physics Net. Req. Review, Aug. 2013. http://www.es.net/assets/Papers-and-Publications/HEP-NP-Net-Req-2013-Final-Report.pdf.

[35]

W. E. Johnston, E. Dart, M. Ernst, and B. Tierney. Enabling high throughput in widely distributed data management and analysis systems: Lessons from the LHC. In TERENA Networking Conference (TNC), 2013.

[36]

S. D. Kahn. On the future of genomic data. Science, 331(6018):728--729, 2011.

[37]

R. Kettimuthu et al. Lessons learned from moving earth system grid data sets over a 20 gbps wide-area network. In 19th ACM International Symposium on High Performance Distributed Computing, HPDC '10, pages 316--319, New York, NY, USA, 2010. ACM.

Digital Library

[38]

R. Kettimuthu, G. Vardoyan, G. Agrawal, and P. Sadayappan. Modeling and optimizing large-scale wide-area data transfers. 2014 14th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, 0:196--205, 2014.

[39]

T. Kosar and M. Livny. Stork: Making data placement a first class citizen in the Grid. In Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), ICDCS '04, pages 342--349, Washington, DC, USA, 2004. IEEE Computer Society.

Digital Library

[40]

J. Krallmann, U. Schwiegelshohn, and R. Yahyapour. On the design and evaluation of job scheduling algorithms. In Proceedings of the Job Scheduling Strategies for Parallel Processing, IPPS/SPDP '99/JSSPP '99, pages 17--42, London, UK, 1999. Springer-Verlag.

Digital Library

[41]

A. Kuzmanovic and E. W. Knightly. TCP-LP: Low-priority service via end-point congestion control. IEEE/ACM Trans. Netw., 2006.

Digital Library

[42]

N. Laoutaris, M. Sirivianos, X. Yang, and P. Rodriguez. Inter-datacenter bulk transfers with netstitcher. In Proceedings of the ACM SIGCOMM 2011 Conference, SIGCOMM '11, pages 74--85, New York, NY, USA, 2011. ACM.

Digital Library

[43]

LIGO Data Replicator. http://www.lsc-group.phys.uwm.edu/LDR/.

[44]

D. Lu, Y. Qiao, P. Dinda, and F. Bustamante. Characterizing and predicting TCP throughput on the wide area network. In Distributed Computing Systems, 2005. ICDCS 2005. Proceedings. 25th IEEE International Conference on, pages 414--424, June 2005.

Digital Library

[45]

M. Mehta and D. J. DeWitt. Dynamic memory allocation for multiple-query workloads. In Proceedings of the 19th International Conference on Very Large Data Bases, VLDB '93, pages 354--367, San Francisco, CA, USA, 1993. Morgan Kaufmann Publishers Inc.

Digital Library

[46]

A. W. Mu'alem and D. G. Feitelson. Utilization, predictability, workloads, and user runtime estimates in scheduling the IBM SP2 with backfilling. IEEE Trans. Parallel Distrib. Syst., 12(6):529--543, June 2001.

Digital Library

[47]

Nuclear physics network requirements workshop, 2008. http://science.energy.gov/~/media/ascr/pdf/program-documents/docs/Np_net_req_workshop.pdf.

[48]

L. Ramakrishnan, C. Guok, K. Jackson, E. Kissel, D. M. Swany, and D. Agarwal. On-demand overlay networks for large scientific data transfers. In Proceedings of the 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing, CCGRID '10, pages 359--367, Washington, DC, USA, 2010. IEEE Computer Society.

Digital Library

[49]

Y. Ren, T. Li, D. Yu, S. Jin, T. Robertazzi, B. L. Tierney, and E. Pouyoul. Protocols for wide-area data-intensive applications: Design and performance issues. In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, SC '12, pages 34:1--34:11, Los Alamitos, CA, USA, 2012. IEEE Computer Society Press.

Digital Library

[50]

Y. Sun, S. Marru, and B. Plale. Experience with bursty workflow-driven workloads in LEAD science gateway. In Proceedings of TeraGrid Conference, 2008.

[51]

S. Vazhkudai and J. Schopf. Using regression techniques to predict large data transfers. Int. J. High Perf. Comp. Appl., 2003.

Digital Library

[52]

L. Wang, K. S. Park, R. Pang, V. Pai, and L. Peterson. Reliability and security in the codeen content distribution network. In Proceedings of the Annual Conference on USENIX Annual Technical Conference, ATEC '04, pages 14--14, Berkeley, CA, USA, 2004. USENIX Association.

Digital Library

[53]

D. Williams et al. Earth System Grid: Enabling access to multi-model climate simulation data. Bulletin of American Meteorological Society, 90(2), 2009.

[54]

R. Wolski. Dynamically forecasting network performance using the network weather service. Cluster Computing, 1(1):119--132, Jan. 1998.

Digital Library

[55]

XSEDE Report, 2013. http://ideals.illinois.edu/handle/2142/44872.

[56]

E. Yildirim and T. Kosar. End-to-end data-flow parallelism for throughput optimization in high-speed networks. Journal of Grid Computing, 10(3):395--418, 2012.

Digital Library

[57]

E. Yildirim, D. Yin, and T. Kosar. Prediction of optimal parallelism level in wide area data transfers. IEEE Trans. Parallel Distrib. Syst., 22(12):2033--2045, Dec. 2011.

Digital Library

Cited By

Zheng WKordas JSkluzacek TKettimuthu RFoster I(2024)Globus service enhancements for exascale applications and facilitiesThe International Journal of High Performance Computing Applications10.1177/1094342024128174438:6(658-670)Online publication date: 9-Sep-2024
https://doi.org/10.1177/10943420241281744
Jeong BKhan APark S(2019)Async-LCAMCluster Computing10.1007/s10586-018-2832-522:2(373-384)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s10586-018-2832-5
Song UJeong BPark SLee K(2019)Optimizing communication performance in scale-out storage systemCluster Computing10.1007/s10586-018-2831-622:2(335-346)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s10586-018-2831-6
Show More Cited By

Index Terms

Recommendations

Scheduling of deteriorating jobs with release dates to minimize the maximum lateness

In this paper, we consider the problem of scheduling n deteriorating jobs with release dates on a single (batching) machine. Each job's processing time is a simple linear function of its starting time. The objective is to minimize the maximum lateness. ...
Primary-secondary bicriteria scheduling on identical machines to minimize the total completion time of all jobs and the maximum T-time of all machines

In this paper, we study a new primary-secondary bicriteria scheduling problem on identical machines. The primary objective is to minimize the total completion time of all jobs and the secondary objective is to minimize the maximum T-time of all machines,...
EleGANt: Exquisite and Locally Editable GAN for Makeup Transfer
Computer Vision – ECCV 2022
Abstract
Most existing methods view makeup transfer as transferring color distributions of different facial regions and ignore details such as eye shadows and blushes. Besides, they only achieve controllable transfer within predefined fixed regions. This ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SC '15: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis

November 2015

985 pages

ISBN:9781450337236

DOI:10.1145/2807591

General Chair:
Jackie Kern
University of Illinois at Urbana-Champaign, Urbana, Illinois
,
Program Chair:
Jeffrey S. Vetter
Oak Ridge National Laboratory and Georgia Institute of Technology, Oak Ridge, Tennessee

Copyright © 2015 ACM.

Publication rights licensed to ACM. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of the United States government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 November 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

U.S. Department of Energy

Conference

SC15

Sponsor:

SIGHPC
SIGARCH
IEEE-CS

SC15: The International Conference for High Performance Computing, Networking, Storage and Analysis

November 15 - 20, 2015

Texas, Austin

Acceptance Rates

SC '15 Paper Acceptance Rate 79 of 358 submissions, 22%;

Overall Acceptance Rate 1,516 of 6,373 submissions, 24%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
418
Total Downloads

Downloads (Last 12 months)80
Downloads (Last 6 weeks)24

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zheng WKordas JSkluzacek TKettimuthu RFoster I(2024)Globus service enhancements for exascale applications and facilitiesThe International Journal of High Performance Computing Applications10.1177/1094342024128174438:6(658-670)Online publication date: 9-Sep-2024
https://doi.org/10.1177/10943420241281744
Jeong BKhan APark S(2019)Async-LCAMCluster Computing10.1007/s10586-018-2832-522:2(373-384)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s10586-018-2832-5
Song UJeong BPark SLee K(2019)Optimizing communication performance in scale-out storage systemCluster Computing10.1007/s10586-018-2831-622:2(335-346)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s10586-018-2831-6
Liu ZKettimuthu RBalaprakash PRao NFoster I(2019)Building a Wide-Area File Transfer Performance Predictor: An Empirical StudyMachine Learning for Networking10.1007/978-3-030-19945-6_5(56-78)Online publication date: 10-May-2019
https://doi.org/10.1007/978-3-030-19945-6_5
Yan FHe YRuwase OSmirni E(2018)Efficient Deep Neural Network Serving: Fast and FuriousIEEE Transactions on Network and Service Management10.1109/TNSM.2018.280835215:1(112-126)Online publication date: Mar-2018
https://doi.org/10.1109/TNSM.2018.2808352
Liu ZKettimuthu RFoster ILiu Y(2018)A Comprehensive Study of Wide Area Data Movement at a Scientific Computing Facility2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS.2018.00180(1604-1611)Online publication date: Jul-2018
https://doi.org/10.1109/ICDCS.2018.00180
Chen ZLuo LQuan WShi YYu JWen MZhang C(2018)Multiple CNN-based Tasks Scheduling across Shared GPU Platform in Research and Development Scenarios2018 IEEE 20th International Conference on High Performance Computing and Communications; IEEE 16th International Conference on Smart City; IEEE 4th International Conference on Data Science and Systems (HPCC/SmartCity/DSS)10.1109/HPCC/SmartCity/DSS.2018.00107(578-585)Online publication date: Jun-2018
https://doi.org/10.1109/HPCC/SmartCity/DSS.2018.00107
Li TRen YYu DJin S(2017)Analysis of NUMA effects in modern multicore systems for the design of high-performance data transfer applicationsFuture Generation Computer Systems10.1016/j.future.2017.04.00174:C(41-50)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1016/j.future.2017.04.001
Agnew WFischer MFoster IChard K(2016)An ensemble-based recommendation engine for scientific data transfersProceedings of the 7th International Workshop on Data-Intensive Computing in the Cloud10.5555/3018100.3018102(9-16)Online publication date: 13-Nov-2016
https://dl.acm.org/doi/10.5555/3018100.3018102
Yan FHe YRuwase OSmirni EWest J(2016)SERFProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.5555/3014904.3014939(1-12)Online publication date: 13-Nov-2016
https://dl.acm.org/doi/10.5555/3014904.3014939
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Figures

Tables

Media

View Table of Conten