Packet Clustering for Efficient Flow Scheduling
"Discover how packet clustering optimizes flow scheduling, enhancing user experience by determining packet forwarding sequences. Explore various scheduling problems and existing solutions to overcome limitations in this insightful overview of QCluster methodology. Design goals aim for a practical, generic, and traffic-agnostic framework to improve flow scheduling efficiency."
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Qcluster: Clustering Packets for Flow Scheduling
Background Flow scheduling is to decide the forwarding sequences of packets for some optimization goals Flow scheduling directly influences user experience of applications!!
Background Four typical kinds of scheduling problems SRPT: Shortest Remaining Processing Time first LAS: Least Attained Service first Fair Queueing Deadline-Aware Scheduling
Background An example for SRPT
Background Switches can only support FIFO (First in First out) queues currently. Can hardly schedule flows with only one FIFO queue Incoming packets Outgoing packets FIFO
Background Switches have multiple FIFO queues Switches support priority queues Providing basis for flow scheduling!! Incoming packets Outgoing packets Enqueue Dequeue
Background Existing solutions: SRPT: pFabric LAS: PIAS, AuTO Fair Queueing: Nagle, BR, AFQ Deadline-Aware Scheduling: pFabric-EDF, PDQ, Karuna
Background Limitations: Not generic Not practical Traffic-aware
Design Goal Devise a framework overcoming all limitations Generic: can be applied to all existing scheduling problems Practical: can work with limited k FIFO queues (e.g., k = 8) Traffic-agnostic: work without measurement in advance
Insight Flow scheduling is essentially a queue clustering problem Clustering packets with similar weights or properties into the same queue Packet weight is specific to flow scheduling problems 10
QCluster Overview 3-step workflow 11
The Scheduling Count-Min Sketch We need three kinds of per-flow information 1. The number of bytes sent (packet weight) 2. The arriving time of the last packet (message/flowlet split) 3. The queue that the last packet was sent into (packet disorder) 12
Choosing Queues Queue weight is calculated as the average of all packets in it Every packet chooses the queue with the smallest distance Different distance definition for different flow scheduling problem Already enqueued Average = 3.17 14
Same Cluster Size Fair Queueing needs same-sized cluster Number of Flows is inversely proportional to queue weight Weighted round-robin in dequeueing 15
Same Cluster Size Currently, Technique: Adaptative threshold ? ????= ?? + ??+1 1 , = ??/(??+ ??+1) increases/decreases according to ??and ??+1 16
Proportional Cluster Size As a large number of flows only contain a small number of packets, same-sized cluster will lead large flows to block small flows For LAS, SRPT, and DDL-aware, we need to let the cluster size proportional to queue weight. Similarly, we can use Adaptative threshold 17
Packet Disorder Avoidance Latter packets could be sent to higher-priority queues while the former packets of the same flow are still in a congested low- priority queue Packet disorder happens!! 18
Packet Disorder Avoidance Assumption: all packets in a flowlet will dequeue before next flowlet arrives. Leveraging the SCM sketch, we can identify the beginning of a flowlet, and record the queue ID where packets enqueue. 19
Packet Disorder Avoidance Fair Queueing: all packets in a flowlet must enqueue the same queue as the beginning LAS/SRPT/DDL-aware: every packet in a flowlet must enqueue a queue with lower or equal priority compared to the last packet 20
Applications 21
Experimental Results Testbed Tofino Wedge 100BF-32X switch ConnectX-3 40GbE Enable ECN 6 sender to 1 receiver NS-2 simulation 6 sender to 1 receiver 22
Thank you! 27
