Longer Stay Less Priority: Flow Length Approximation Used in Information-Agnostic Traffic Scheduling in Data Center Networks-Chien Chen

Abstract

Numerous scheduling approaches have been proposed to improve user experiences in a data center network(DCN) by reducing flow completion time (FCT). Mimicking the shortest job first (SJF) has been proved to be the prominent way to improve FCT. To do so, some approaches require flow size or completion time information in advance, which is not possible in scenarios like HTTP chunk transfer or database query response. Some information-agnostic schemes require involving end-hosts for counting the number of bytes sent. We present Longer Stay Less Priority (LSLP), an information-agnostic flow scheduling scheme, like Multi-Level Feedback Queue (MLFQ) scheduler in operating systems, that aims to mimic SJF using P4 switches in a DCN. LSLP considers all the flows as short flows initially and assigns them to the highest priority queue, and flows get demoted to the lower priority queues over time. LSLP estimates the active time of a flow by leveraging the state-of-the-art P4 switch’s programmable nature. LSLP estimates the active time of a group of new flows that arrive during a time interval and assigns their packets to the highest priority. At the beginning of the next time interval, arriving packets of old flows are placed one priority lower except for those already in the lowest priority queue. Therefore, short flows can be completed in the few higher priority queues while long flows are demoted to lower priority queues. We have evaluated LSLP via a series of tests and shown that its performance is comparable to the existing scheduling schemes.

LSLP Mechanism

Beginning of new time slot

All new flows (during a time slot) are grouped in one version: Packets assigned same priority
All existing flows: Demoted by one level except already in lowest priority

Fig. 1: Overview of LSLP

Implementation In P4

Packet is matched to Time-version table

successful: get for TimeSlotID
match Priority table for Qid and submitted to Q

Packet is not matched to Time-version table

Submit to controller
Controller updates time-version and priority table

Fig. 2: Workflow of LSLP

Performance Evalluation

Overall average FCT at different load: (a) Web search workload, (b) Data mining workload

Web Search (Left) and Data Mining (Right) Workload FCT across different flow sizes (a)(0; 100KB] Avg. (b) (0; 100KB] 99th Percentile (c) (100KB; 10MB] (d)(10MB;∞]

Video Link: https://youtu.be/YUVZ-BGVoYo