Chi-Yao Hong
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 D3 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.
Supplemental Material
- Bro network security monitor. http://www.bro-ids.org.Google Scholar
- M. Al-Fares, A. Loukissas, and A. Vahdat. A scalable, commodity data center network architecture. In SIGCOMM, 2008. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- N. Bansal and M. Harchol-Balter. Analysis of SRPT scheduling: Investigating unfairness. In SIGMETRICS, 2001. Google ScholarDigital Library
- N. Bansal and M. Harchol-Balter. End-to-end statistical delay service under GPS and EDF scheduling: A comparison study. In INFOCOM, 2001.Google Scholar
- T. Benson, A. Akella, and D. A. Maltz. Network traffic characteristics of data centers in the wild. In IMC, 2010. Google ScholarDigital Library
- J. Brutlag. Speed matters for Google web search, 2009.Google Scholar
- 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. Google ScholarDigital Library
- N. Dukkipati, Y. Ganjali, and R. Zhang-Shen. Typical versus worst case design in networking. In HotNets, 2005.Google Scholar
- N. Dukkipati and N. McKeown. Why flow-completion time is the right metric for congestion control. SIGCOMM Comput. Commun. Rev., 2006. Google ScholarDigital Library
- M. R. Garey and D. S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., 1990. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- C.-Y. Hong, M. Caesar, and P. B. Godfrey. Finishing flows quickly with preemptive scheduling. Technical report. http://arxiv.org/abs/1206.2057, 2012. Google ScholarDigital Library
- D. Katabi, M. Handley, and C. Rohrs. Congestion control for high bandwidth-delay product networks. In SIGCOMM, 2002. Google ScholarDigital Library
- M. L. Pinedo. Scheduling: Theory, Algorithms, and Systems. Springer, 2nd edition, 2002. Google ScholarDigital Library
- C. Raiciu, S. Barre, C. Pluntke, A. Greenhalgh, D. Wischik, and M. Handley. Improving datacenter performance and robustness with multipath TCP. In SIGCOMM, 2011. Google ScholarDigital Library
- A. Singla, C.-Y. Hong, L. Popa, and P. B. Godfrey. Jellyfish: Networking data centers randomly. In NSDI, 2012. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- C. Wilson, H. Ballani, T. Karagiannis, and A. Rowstron. Better never than late: Meeting deadlines in datacenter networks. In SIGCOMM, 2011. Google ScholarDigital Library
- D. Wischik, C. Raiciu, A. Greenhalgh, and M. Handley. Design, implementation and evaluation of congestion control for multipath TCP. In NSDI, 2011. Google ScholarDigital Library
- H. Wu, Z. Feng, C. Guo, and Y. Zhang. ICTCP: Incast congestion control for TCP in data center networks. In CoNEXT, 2010. Google ScholarDigital Library
- D. Zats, T. Das, and R. H. Katz. DeTail: Reducing the flow completion time tail in datacenter networks. Technical report, Oct 2011.Google Scholar
Index Terms
- Finishing flows quickly with preemptive scheduling
Recommendations
Finishing flows quickly with preemptive scheduling
Special october issue SIGCOMM '12Today'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 ConferenceCloud 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 GridsMapReduce 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