Source-linked AI summary
Finishing Flows Quickly with Preemptive Scheduling
Chi-Yao Hong, Matthew Caesar, P. Brighten Godfrey
TL;DR
Data-center applications require low latency, but fair sharing is poorly suited to minimizing completion time and deadline misses. The paper introduces PDQ, a distributed preemptive flow scheduler that approximates scheduling disciplines, and simulations show lower completion times and greater deadline-constrained concurrency than existing protocols.
Problem
Fair-sharing transport protocols do not minimize flow completion time or the number of deadline-missing flows, despite demanding data-center latency requirements.
Method
PDQ is a distributed flow-scheduling layer that uses preemption and relative flow priorities to approximate scheduling disciplines.
Results
∼30% lower average flow completion time than TCP, RCP and D3, and 3× as many concurrent senders as D3 while meeting flow deadlines.
Takeaways & Limitations
PDQ retains nearly all its performance gains with inaccurate flow information, remains resilient to packet loss, and M-PDQ adds performance and reliability gains.
Takeaways & Limitations
PDQ’s discussion assumes reasonably small receiver buffers when explaining how it backs off for receiver-limited applications.
Abstract
from arXiv · showhide
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.
1. INTRODUCTION
Data-center latency requirements expose the limits of fair sharing, which does not minimize flow completion time or deadline misses. PDQ addresses this with distributed, preemptive scheduling and achieves substantial gains in simulations.
- Motivation: Data-center applications have stringent latency requirements, especially when services wait for the slowest back-end flow.Congestion delays can reduce user experience and the quality of aggregated results.
- Motivation: Current transport protocols approximate fair sharing, which is far from optimal for minimizing flow completion time and deadline-missing flows.A production study reported 7 −25% of flow deadlines missed across three data centers.
- Approach: PDQ is a distributed flow-scheduling layer that can approximate multiple scheduling disciplines using flow preemption and relative priorities.Its design adapts centralized scheduling ideas while allowing switches to collaboratively make allocation decisions.
- Approach: PDQ-based scheduling disciplines target mean flow completion time and the number of deadline-missing flows.The paper describes EDF and SJF as the disciplines used for these objectives.
- Results: ∼30% lower average flow completion time and 3× as many concurrent senders as D3 demonstrate PDQ’s gains while meeting flow deadlines.The comparison is reported against TCP, RCP and D3 for completion time, and against D3 for concurrent senders.
- Results: PDQ remains stable and resilient to packet loss or inaccurate flow information, while its multipath variant provides further performance and reliability gains.The paper evaluates M-PDQ as a path-striping extension of PDQ.
2. OVERVIEW
A motivating example contrasts fair sharing and arrival-order-based D3 with SJF and EDF, illustrating why preemption and decentralized scheduling are needed. PDQ uses sender-side flow pausing and switch coordination to approximate these disciplines.
- Motivating Example: For three concurrent flows without deadlines, SJF reduces average completion time from 4.67 under fair sharing to 3.33.Fair sharing finishes the flows at times 3, 5, and 6; SJF finishes them at cumulative times 1, 3, and 6.
- Motivating Example: With deadlines, fair sharing misses two flows, whereas EDF schedules every flow before its deadline.The example uses the same three-flow bottleneck scenario.
- Motivating Example: D3’s outcome depends strongly on flow arrival order because it allocates rates in arrival order during congestion.For arrival order fB;fA;fC, fB meets its deadline but fA does not; five of six permutations miss some deadline.
- Design Challenges: Centralized EDF and SJF require global flow knowledge and can create initialization overhead and a congestive coordinator hot spot.These challenges are especially severe when most data-center flows are mice.
- Design Challenges: PDQ controls sending rates and pauses low-priority flows, requiring only per-link FIFO tail-drop queues at switches.This flow-pausing strategy avoids requiring many switch priority classes.
3. PROTOCOL
PDQ combines distributed scheduling, flow preemption, and rate control to prioritize critical flows while using lightweight switch state and reduced probing overhead.
- Centralized Algorithm: PDQ first presents an idealized centralized scheduler that orders flows by increasing expected transmission time and allocates rates along their paths.Expected transmission time is remaining flow size divided by maximal sending rate.
- Distributed Algorithm: PDQ distributes scheduling by propagating flow information through packet headers and returning switch feedback in ACKs.Senders maintain flow state and communicate it to intermediate switches through scheduling headers.
- Deadline Handling: Early Termination sends TERM when a deadline has passed or remaining transmission time exceeds the time to deadline.The heuristic addresses infeasible demand by terminating flows that cannot meet their deadlines.
- Flow Prioritization: PDQ uses deadlines first and expected transmission time second to emulate EDF and SJF, while allowing operators to override the comparator.EDF prioritizes smaller deadlines; flows without deadlines are ordered by smaller expected transmission time.
- Switch Scheduling: Preemption lets critical flows achieve their highest possible sending rate while switches resolve contention using flow and rate controllers.Switches maintain state for the most critical 2κ flows and retain additional information to unpause another flow after completion.
- Probing and Rate Control: Suppressed Probing estimates a lower bound on waiting time to reduce probing overhead based on flow-list position and network load.The switch sets inter-probing time using X × Index(ℓ), and the sender probes at the resulting rate.
- Probing and Rate Control: The rate controller updates C to max{0, rPDQ −q/(2 × RTT)} using queue size and aggregate PDQ traffic.The configured rPDQ can equal link rate when all traffic uses PDQ, allowing PDQ flows to send at their highest possible rate.
4. FORMAL PROPERTIES
PDQ’s formal analysis establishes deadlock-freedom and finite convergence time under simplifying assumptions, with additional latency when packet loss or flow dampening occurs.
- Formal Properties: The formal properties analyzed for PDQ are deadlock-freedom and finite convergence time.The analysis assumes no packet loss and no pauses caused by flow dampening.
- Definitions: PDQ defines competing, precedential, and driver flows to characterize priority relationships among flows sharing links.A precedential flow is more critical than a competing flow, while a driver satisfies a stated criticality condition among competitors.
5. PDQ PERFORMANCE
PDQ is evaluated with packet-level and flow-level simulations across deadline-constrained and unconstrained workloads. It achieves near-optimal performance while outperforming existing transport schemes as load and flow counts vary.
- Evaluation setting: The evaluation uses deadline-constrained flows with sizes uniformly distributed from [2 KByte, 198 KByte] and deadlines exponentially distributed with mean 20 ms.The workload represents query traffic and delay-sensitive short messages.
- Query aggregation: PDQ achieves near-optimal application throughput across a wide range of loads.The comparison includes an omniscient scheduler that sorts flows by EDF and discards the minimum number of infeasible flows.
- Query aggregation: Early Start substantially improves short-flow throughput by reducing downtime during flow switching.PDQ(Basic) performs much worse under heavy load because of long switching downtime, while Early Termination further improves deadline performance.
- Deadline-constrained flows: >3 times more concurrent flows can be supported by PDQ than D3 at 99% application throughput.The advantage increases as the mean flow deadline increases.
- Deadline-unconstrained flows: PDQ effectively approximates optimal flow completion time when deadlines are unconstrained.RCP’s completion time grows as the number of flows increases, while the largest PDQ gap occurs with one flow because of initialization latency.
5.3 Impact of Traffic Workload
PDQ retains its benefits across realistic workloads, traffic dynamics, bursty arrivals, and scalable topologies. Its mechanisms maintain utilization while reducing completion time and queue sizes.
- Realistic workloads: PDQ supports a significantly higher flow arrival rate than other protocols under the production workload.Suppressed Probing is especially important when many flows are paused because it reduces probing overhead.
- Realistic workloads: PDQ outperforms other schemes on a workload collected from a university data center with 500 servers.The ten-minute packet trace was converted into flow-level summaries before simulation.
- Traffic dynamics: 91.7% average link utilization is maintained during preemption of 50 short flows arriving together.PDQ adapts quickly to the burst while keeping only 5 to 10 packets in the queue.
- Network scale: About 40% of flow completion times are reduced by at least 50% versus RCP across Fat-tree, BCube, and Jellyfish topologies.Only 5−15% of flows take longer under PDQ, and no more than 0.9% take 2× longer.
5.6 PDQ Resilience
PDQ remains effective despite packet loss and inaccurate flow-size information. Its explicit rate control compensates for lossy feedback, while periodic criticality updates preserve performance under estimation error.
- Packet loss: PDQ is more resilient to packet loss than TCP in both forward and reverse directions.The evaluation randomly drops data and acknowledgment packets at the bottleneck link.
- Packet loss: At 3% packet loss in each direction, PDQ performance is not significantly affected.This corresponds to an approximately 5.9% round-trip packet loss rate, and the controller compensates using explicit rate control.
- Inaccurate flow information: The resilience evaluation uses a query-aggregation workload with 10 deadline-unconstrained flows averaging 100 KByte.Flow-level simulation is used for the inaccurate-information experiment.
- Inaccurate flow information: Without flow-size information, PDQ updates flow criticality every 50 KByte sent.Flows with smaller estimated remaining size are treated as more critical, but random criticality can cause large completion times for heavy-tailed sizes.
6. MULTIPATH PDQ
Multipath PDQ stripes one flow across multiple paths to exploit path diversity. In BCube simulations, it reduces completion time under light load and improves performance under stressed networks.
- Design: M-PDQ enables a single flow to be striped across multiple network paths.The switch requires only ECMP support, while the sender shifts load from paused subflows toward the subflow with minimal remaining load.
- Performance: A factor-of-two reduction in flow completion time is achieved by M-PDQ under light loads with three subflows.The evaluation uses BCube with random permutation traffic.
- Performance: 97% of full potential is reached with about four subflows at 100% workload.Using all four server interfaces provides a significant improvement over single-path PDQ, which uses only one.
7. DISCUSSION
PDQ’s scheduling flexibility can improve completion times without broadly harming flows, while aging can prevent starvation and implementation remains feasible on modern switches.
- Fairness: At least 99% of jobs have smaller completion times under SJF than under fair sharing.This percentage increases further when traffic load is less than half.
- Fairness: 85–95% of PDQ flows complete sooner than RCP flows, while the worst PDQ flow has only a 2.57 completion-time inflation factor.The comparison covers complex data center networks with thousands of concurrent flows and multiple bottlenecks.
- Fairness: Aging reduces flow criticality’s threshold by a factor of 2^αt, helping prevent less critical flows from starvation and shortening their completion time.Here, α controls aging rate and t is waiting time measured in units of 100 ms.
- Deployment: PDQ hides preemption in the transport layer, so applications remain unchanged while paused flows retain their transport connections.From the application’s perspective, preemption is equivalent to TCP becoming temporarily slower.
- Deployment: PDQ can be implemented with switch hardware and software, using O(κ) per-packet time for the top κ flows and O(1) for the rest.Per-packet header modification can use existing hardware, while rate aggregation and flow-list updates can run in software.
8. RELATED WORK
PDQ differs from related approaches by combining explicit rate control with flow resequencing and preemption, avoiding limitations of arrival-order and coarse-priority scheduling.
- D3: Unlike PDQ, D3 neither resequences flow transmission order nor preempts flows, so it serves flows according to arrival order.This can let flows with large deadlines occupy bottleneck bandwidth and block later short flows.
- Fair Sharing: TCP, RCP, and DCTCP emulate fair sharing, which produces suboptimal flow completion time.The passage contrasts this with PDQ’s scheduling approach.
- TCP/RCP with Priority Queueing: Two-level priority queuing with TCP or RCP suffers losses and falls behind D3, while four priority classes provide little improvement.Flows can have widely varying deadlines, but switches typically offer no more than ten priority classes.
- ATM: ATM offers QoS priority control but classifies traffic into only two priority classes.The passage presents this as a limitation for representing diverse flow priorities.
9. CONCLUSION
The paper concludes that PDQ distributes priority-based flow scheduling and substantially improves completion time and deadline capacity, with multipath PDQ adding further gains.
- Conclusion: PDQ approximates a range of priority-based scheduling disciplines through a distributed algorithm, targeting mean flow completion time and deadline misses.The evaluation uses packet-level and flow-level simulation across workloads, traffic patterns, topologies, and network sizes.
- Conclusion: PDQ reduces average flow completion time by ∼30% compared with TCP, RCP, and D3.This is the paper’s reported comparison across existing schemes.
- Conclusion: PDQ supports 3× as many concurrent senders as D3 while meeting flow deadlines.The result is reported alongside PDQ’s average flow-completion-time reduction.
- Conclusion: M-PDQ splits a single flow into multiple subflows and achieves further performance and reliability gains across varied settings.The multipath design exploits multiple paths through flow-level subflows.
Appendix A. Deadlock-freedom
PDQ avoids deadlock by requiring path-wide acceptance before a flow is accepted, eliminating the hold-and-wait condition.
- Deadlock-freedom: PDQ has no deadlock because a flow is accepted only after every switch along its routing path accepts it.Thus, a flow cannot be accepted by some switches while paused by others, which would constitute hold and wait.
Appendix B. Bounding the Convergence Time
PDQ converges under stable workloads by prioritizing driver flows and pausing less critical competing flows. The convergence bound depends on the maximum number of precedential flows.
- PDQ defines a driver as a flow that is more critical than all competitors or whose more-critical competitors are non-drivers.
- When all precedential flows are paused, or none exist, a flow is accepted within one RTT; otherwise, it is paused within one RTT after a precedential flow is accepted.
- PDQ converges to equilibrium in Pmax + 1 RTTs for stable workloads, where Pmax is the maximum number of precedential flows for any flow.
- At equilibrium, all drivers are accepted while the remaining flows are paused.
- The convergence proof inductively shows that a flow with n more-critical flows is accepted or paused within at most n + 1 RTTs.