Finishing flows quickly with preemptive scheduling

By C. Hong, Matthew C. Caesar, Brighten Godfrey. CCRV, 2012

557 citations recorded by the source corpus.

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.

Subfields: Computer Networks and Communications, Information Systems

View Paper: https://www.semanticscholar.org/paper/766a2be3159cd1402194fa6392d0dc7e061d0458

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Information Systems

Citations in the corpus

Swift: Delay is Simple and Effective for Congestion Control in the Datacenter (2020, background): “PDQ [24] requires switches to maintain per-flow state.”
Coflow: a networking abstraction for cluster applications (2012, unknown): “…Systems Cloud Computing General Terms Design Keywords Cluster Networking, Co.ow, Data-Intensive Applications, Datacenter Networks, Cloud Computing 1 Introduction Cluster computing applications serve diverse computing requirements, and they expect a broad spectrum of services from the network.”
pFabric: minimal near-optimal datacenter transport (2013, methodology): “PDQ was the first to point out that minimizing FCTs requires preemptive flow scheduling and attempts to approximate the same ideal flow scheduling algorithm as pFabric to minimize average FCT or missed deadlines (§3).”
Efficient coflow scheduling with Varys (2014, unknown): “…[15]; but for multiple coﬂows, it minimizes the completion time across all coﬂows and increases the average CCT. Recently proposed shortest-ﬂow-ﬁrst prioritization mechanisms [8,25] (Figure 2b) decrease average FCT, but they increase the average CCT by interleaving ﬂows from different coﬂows.”
Re-architecting datacenter networks and stacks for low latency and high performance (2017, background): “There is a large body of work aiming to tackle various aspects of datacenter transport: most focuses on either achieving low latency [5, 6, 16, 22, 28, 30] or high throughput [2, 12, 31].”
Decentralized task-aware scheduling for data center networks (2014, methodology): “, priority queues, pFabric [5], PDQ [17], etc) at the switches and end-points.”
Low Latency Geo-distributed Data Analytics (2015, background): “3) Optimizing communication patterns: Flow schedulers like D3 [55], PDQ [35], DeTail [62], and D2TCP [51] aim to improve ﬂow completion times or guarantee dead-lines.”
Efficient Coflow Scheduling Without Prior Knowledge (2015, background): “Yet, until recently, researchers and practitioners have largely overlooked application-level requirements when improving network-level metrics like flow-level fairness and flow completion time (FCT) [29, 10, 16, 8, 14].”
Packet Transactions: High-Level Programming for Line-Rate Switches (2015, background): “This rigidity affects many stakeholders adversely: vendors [7, 9, 4] building network switches with merchantsilicon chips [13, 14, 21], network operators deploying switches [85, 80, 58], and researchers developing new switch algorithms [64, 74, 96, 99, 60].”
CONGA: distributed congestion-aware load balancing for datacenters (2015, methodology): “Similar to prior work [20, 5, 13], we use the flow completion time (FCT) as our main performance metric.”
AuTO: scaling deep reinforcement learning for datacenter-scale automatic traffic optimization (2018, background): “The main di erence between the two is that SJF schemes [1, 4, 29] require ow size at the start of a ow, while LAS schemes [8, 14, 43] do not.”