Inversion impact of approximate PIFO to Start-Time Fair Queueing

Programmable packet schedulers have emerged in the context of Software-Defined Networking (SDN) and diverse service requirements in today's networks. With a programmable packet scheduler, network operators can apply different scheduling algorithms on the switches. To support a large variety of packet scheduling algorithms, the use of a packet scheduler like PIFO (Push-In First-Out) has been adopted, which serves packets based on their associated priority ranks. Recently, for the concern of priority rank scalability and implementation complexity, a new class of packet schedulers that closely approximate PIFO have been proposed. However, the approximate PIFO schemes may lead to a sub-optimal packet scheduling order and introduce packet inversions. In this paper, we evaluate the inversion impact on Start-Time Fair Queueing (STFQ), an efficient approximation of Weighted Fair Queueing to allocate bandwidth fairly and achieve low maximum delay, when it is used in the approximate PIFO schemes. Our analysis validates the deterioration on the performance goals of STFQ attributed to packet inversions and provides a theoretical bound for the discrepancy caused by these inversions in the fair and delay guarantees offered by STFQ. Based on our simulation results, we demonstrate that the packet inversions in approximate PIFO schemes impair the fairness of bandwidth allocation and the worst-case throughput difference in our simulation exhibits a bias of up to 34% of the total available bandwidth. We further show that the packet inversions result in a 3-fold increase in the maximum end-to-end packet delay in approximate PIFO schemes such as SP-PIFO and AFQ.