research-article

Free access

Finishing flows quickly with preemptive scheduling

Authors:

Matthew Caesar,

P. Brighten GodfreyAuthors Info & Claims

SIGCOMM '12: Proceedings of the ACM SIGCOMM 2012 conference on Applications, technologies, architectures, and protocols for computer communication

Pages 127 - 138

https://doi.org/10.1145/2342356.2342389

Published: 13 August 2012 Publication History

Abstract

Today's data centers face extreme challenges in providing low latency. However, fair sharing, a principle commonly adopted in current congestion control protocols, is far from optimal for satisfying latency requirements.

We propose Preemptive Distributed Quick (PDQ) flow scheduling, a protocol designed to complete flows quickly and meet flow deadlines. PDQ enables flow preemption to approximate a range of scheduling disciplines. For example, PDQ can emulate a shortest job first algorithm to give priority to the short flows by pausing the contending flows. PDQ borrows ideas from centralized scheduling disciplines and implements them in a fully distributed manner, making it scalable to today's data centers. Further, we develop a multipath version of PDQ to exploit path diversity.

Through extensive packet-level and flow-level simulation, we demonstrate that PDQ significantly outperforms TCP, RCP and D³ in data center environments. We further show that PDQ is stable, resilient to packet loss, and preserves nearly all its performance gains even given inaccurate flow information.

Supplementary Material

JPG File (sigcomm-iii-02-finishingflowsquicklywithpreemptivescheduling.jpg)

Download
25.01 KB

MP4 File (sigcomm-iii-02-finishingflowsquicklywithpreemptivescheduling.mp4)

Download
83.10 MB

References

[1]

Bro network security monitor. http://www.bro-ids.org.

[2]

M. Al-Fares, A. Loukissas, and A. Vahdat. A scalable, commodity data center network architecture. In SIGCOMM, 2008.

Digital Library

[3]

M. Alizadeh, A. Greenberg, D. A. Maltz, J. Padhye, P. Patel, B. Prabhakar, S. Sengupta, and M. Sridharan. Data center TCP (DCTCP). In SIGCOMM, 2010.

Digital Library

[4]

N. Bansal and M. Harchol-Balter. Analysis of SRPT scheduling: Investigating unfairness. In SIGMETRICS, 2001.

Digital Library

[5]

N. Bansal and M. Harchol-Balter. End-to-end statistical delay service under GPS and EDF scheduling: A comparison study. In INFOCOM, 2001.

[6]

T. Benson, A. Akella, and D. A. Maltz. Network traffic characteristics of data centers in the wild. In IMC, 2010.

Digital Library

[7]

J. Brutlag. Speed matters for Google web search, 2009.

[8]

A. R. Curtis, J. C. Mogul, J. Tourrilhes, P. Yalagandula, P. Sharma, and S. Banerjee. DevoFlow: Scaling flow management for high-performance networks. In SIGCOMM, 2011.

Digital Library

[9]

N. Dukkipati, Y. Ganjali, and R. Zhang-Shen. Typical versus worst case design in networking. In HotNets, 2005.

[10]

N. Dukkipati and N. McKeown. Why flow-completion time is the right metric for congestion control. SIGCOMM Comput. Commun. Rev., 2006.

Digital Library

[11]

M. R. Garey and D. S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., 1990.

Digital Library

[12]

A. Greenberg, J. R. Hamilton, N. Jain, S. Kandula, C. Kim, P. Lahiri, D. A. Maltz, P. Patel, and S. Sengupta. VL2: A scalable and exible data center network. In SIGCOMM, 2009.

Digital Library

[13]

C. Guo, G. Lu, D. Li, H. Wu, X. Zhang, Y. Shi, C. Tian, Y. Zhang, and S. Lu. BCube: A high performance, server-centric network architecture for modular data centers. In SIGCOMM, 2009.

Digital Library

[14]

C.-Y. Hong, M. Caesar, and P. B. Godfrey. Finishing flows quickly with preemptive scheduling. Technical report. http://arxiv.org/abs/1206.2057, 2012.

Digital Library

[15]

D. Katabi, M. Handley, and C. Rohrs. Congestion control for high bandwidth-delay product networks. In SIGCOMM, 2002.

Digital Library

[16]

M. L. Pinedo. Scheduling: Theory, Algorithms, and Systems. Springer, 2nd edition, 2002.

Digital Library

[17]

C. Raiciu, S. Barre, C. Pluntke, A. Greenhalgh, D. Wischik, and M. Handley. Improving datacenter performance and robustness with multipath TCP. In SIGCOMM, 2011.

Digital Library

[18]

A. Singla, C.-Y. Hong, L. Popa, and P. B. Godfrey. Jellyfish: Networking data centers randomly. In NSDI, 2012.

Digital Library

[19]

V. Vasudevan, A. Phanishayee, H. Shah, E. Krevat, D. G. Andersen, G. R. Ganger, G. A. Gibson, and B. Mueller. Safe and effective fine-grained TCP retransmissions for datacenter communication. In SIGCOMM, 2009.

Digital Library

[20]

C. Wilson, H. Ballani, T. Karagiannis, and A. Rowstron. Better never than late: Meeting deadlines in datacenter networks. In SIGCOMM, 2011.

Digital Library

[21]

D. Wischik, C. Raiciu, A. Greenhalgh, and M. Handley. Design, implementation and evaluation of congestion control for multipath TCP. In NSDI, 2011.

Digital Library

[22]

H. Wu, Z. Feng, C. Guo, and Y. Zhang. ICTCP: Incast congestion control for TCP in data center networks. In CoNEXT, 2010.

Digital Library

[23]

D. Zats, T. Das, and R. H. Katz. DeTail: Reducing the flow completion time tail in datacenter networks. Technical report, Oct 2011.

Cited By

Li ZLi DChen YChen KZhang Y(2024)Decentralized Scheduling for Data-Parallel Tasks in the CloudACM Transactions on Parallel Computing10.1145/365185811:2(1-23)Online publication date: 8-Jun-2024
https://dl.acm.org/doi/10.1145/3651858
Gupta JKant KPal ABiswas J(2024)Configuring and Coordinating End-to-end QoS for Emerging Storage InfrastructureACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/36316069:1(1-32)Online publication date: 15-Jan-2024
https://dl.acm.org/doi/10.1145/3631606
Xu RLi WLi K(2024)Efficient Multi-tunnel Flow Scheduling for Traffic EngineeringAlgorithms and Architectures for Parallel Processing10.1007/978-981-97-0859-8_27(456-473)Online publication date: 27-Feb-2024
https://doi.org/10.1007/978-981-97-0859-8_27
Show More Cited By

Index Terms

Finishing flows quickly with preemptive scheduling
1. Networks
  1. Network protocols

Recommendations

Finishing flows quickly with preemptive scheduling
Special october issue SIGCOMM '12

Today's data centers face extreme challenges in providing low latency. However, fair sharing, a principle commonly adopted in current congestion control protocols, is far from optimal for satisfying latency requirements.

We propose Preemptive ...
Scheduling Mix-flows in Commodity Datacenters with Karuna
SIGCOMM '16: Proceedings of the 2016 ACM SIGCOMM Conference

Cloud applications generate a mix of flows with and without deadlines. Scheduling such mix-flows is a key challenge; our experiments show that trivially combining existing schemes for deadline/non-deadline flows is problematic. For example, prioritizing ...
Preemptive Hadoop Jobs Scheduling under a Deadline
SKG '12: Proceedings of the 2012 Eighth International Conference on Semantics, Knowledge and Grids

MapReduce has become the dominant programming model in a cloud-based data processing environment, such as Hadoop. First In First Out (FIFO) is the default job scheduling policy of Hadoop, but it cannot guarantee that the job will be completed by a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGCOMM '12: Proceedings of the ACM SIGCOMM 2012 conference on Applications, technologies, architectures, and protocols for computer communication

August 2012

474 pages

ISBN:9781450314190

DOI:10.1145/2342356

General Chairs:
Lars Eggert
NetApp, Germany
,
Jörg Ott
Aalto University, Finland
,
Program Chairs:
Venkat Padmanabhan
Microsoft Research, India
,
George Varghese
UCSD, USA

Copyright © 2012 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

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 August 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGCOMM '12

Sponsor:

SIGCOMM

SIGCOMM '12: ACM SIGCOMM 2012 Conference

August 13 - 17, 2012

Helsinki, Finland

Acceptance Rates

Overall Acceptance Rate 462 of 3,389 submissions, 14%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

302
Total Citations
View Citations
1,212
Total Downloads

Downloads (Last 12 months)133
Downloads (Last 6 weeks)23

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li ZLi DChen YChen KZhang Y(2024)Decentralized Scheduling for Data-Parallel Tasks in the CloudACM Transactions on Parallel Computing10.1145/365185811:2(1-23)Online publication date: 8-Jun-2024
https://dl.acm.org/doi/10.1145/3651858
Gupta JKant KPal ABiswas J(2024)Configuring and Coordinating End-to-end QoS for Emerging Storage InfrastructureACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/36316069:1(1-32)Online publication date: 15-Jan-2024
https://dl.acm.org/doi/10.1145/3631606
Xu RLi WLi K(2024)Efficient Multi-tunnel Flow Scheduling for Traffic EngineeringAlgorithms and Architectures for Parallel Processing10.1007/978-981-97-0859-8_27(456-473)Online publication date: 27-Feb-2024
https://doi.org/10.1007/978-981-97-0859-8_27
Suo LMa HJiao WLiu X(2023)Job-Deadline-Guarantee-Based Joint Flow Scheduling and Routing Scheme in Data Center NetworksSensors10.3390/s2401021624:1(216)Online publication date: 30-Dec-2023
https://doi.org/10.3390/s24010216
Reidys BXue YLi DSukhwani BHwu WChen DAsaad SHuang JDruschel PKaufmann AMace JFlinn JSeltzer M(2023)RackBlox: A Software-Defined Rack-Scale Storage System with Network-Storage Co-DesignProceedings of the 29th Symposium on Operating Systems Principles10.1145/3600006.3613170(182-199)Online publication date: 23-Oct-2023
https://dl.acm.org/doi/10.1145/3600006.3613170
Li ZHuang JHu JLi WZhang TLiu JWang JHe T(2023)REN: Receiver-Driven Congestion Control Using Explicit Notification for Data CenterIEEE Transactions on Cloud Computing10.1109/TCC.2021.313502711:2(1381-1394)Online publication date: 1-Apr-2023
https://doi.org/10.1109/TCC.2021.3135027
Gao CChu SXu HXu MYe KXu C(2023) Flash : Joint Flow Scheduling and Congestion Control in Data Center Networks IEEE Transactions on Cloud Computing10.1109/TCC.2021.312951111:1(1038-1049)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TCC.2021.3129511
Liu LGao CWang PHuang HLi JXu HZhang W(2023)Bottleneck-Aware Non-Clairvoyant Coflow Scheduling With FaiIEEE Transactions on Cloud Computing10.1109/TCC.2021.312836011:1(1011-1025)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TCC.2021.3128360
Piramuthu OCaesar M(2023)Drone-Hosted Computation for Emergency ResponseIEEE Internet of Things Journal10.1109/JIOT.2023.328404510:23(20408-20414)Online publication date: 1-Dec-2023
https://doi.org/10.1109/JIOT.2023.3284045
Li ZHuang JLi YWang J(2023)Traffic‐aware rate control for mix‐flow in datacenterIET Communications10.1049/cmu2.1268717:18(2132-2139)Online publication date: 6-Oct-2023
https://dl.acm.org/doi/10.1049/cmu2.12687
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents