# Priority Queues with Fractional Service for Tiered Delay QoS
###### Abstract  
Packet scheduling is key to quality of service (QoS) capabilities of broadband wired and wireless networks. In a heterogeneous traffic environment, a comprehensive QoS packet scheduler must strike a balance between flow fairness and access delay. Many advanced packet scheduling solutions have targeted fair bandwidth allocation while protecting delay-constrained traffic by adding priority queue(s) on top of a fair bandwidth scheduler. Priority queues are known to cause performance uncertainties and, thus, various modifications have been proposed. In this paper, we present a packet queueing engine dubbed Fractional Service Buffer (FSB), which, when coupled with a configurable flow scheduler, can achieve desired QoS objectives, such as fair throughputs and differentiated delay guarantees. Key performance metrics, such as delay limit and probability of delay limit violation, are derived as a function of key FSB parameters for each delay class in the packet queueing engine using diffusion approximations. OPNET simulations verify these analytical results.  
quality of service; modeling; simulation; diffusion approximation; broadband routers +
Footnote †: journal:  
0000-0001-4500-559X/0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-00000-00000-0000-00000-0000-00000-0  
protections, every delay class must receive a certain fraction of service relative to the higher-priority classes to prevent starvation when higher priority classes present heavy loads. This notion of fractional service is the main motive of this work.  
We shall present a two-stage packet scheduling architecture that can be tailored to satisfy both flow-level throughput fairness and packet-level delay protections. The first stage is a buffer-less flow scheduler of which the responsibility is to classify packets based on their flow QoS. No specific flow QoS strategies will be assumed except that each classified packet is given a delay limit associated with its assigned delay class. The second stage is a packet queueing engine that uses as many buffers as delay classes to queue classified packets. Its responsibility is to protect the delay guarantee of each delay class such that it is met with a sufficiently high probability. This paper focuses on the second stage: the packet queueing engine. We shall present and analyze the packet queueing engine dubbed Fractional Service Buffer (FSB) that allows a fraction of lower-priority (higher-delay-limit) traffic class to advance their queueing priority at every higher-priority packet arrival. The fraction, in conjunction with the buffer size, determines a delay limit and a delay-violation probability associated with each delay class. Basically, our approach adds a fair queueing component to the conventional static priority queues, such that the lower-priority traffic may improve their priority over time and thus will not be shut out by higher-priority traffic.  
The rest of this paper is organized as follows. In Section 2, we cite some related literatures in flow scheduling and priority-queueing schemes. In Section 3, we present the two-stage FSB architecture and its fractional service algorithm. In Section 4, we analyze the FSB under heavy traffic conditions using a combination of queue aggregation technique and diffusion approximations. In Section 5, we demonstrate the accuracy of our analytical results from Section 4 using simulations. In Section 6, we discuss the relationship between the system parameters and desired QoS levels and how tradeoffs between different QoS levels can be achieved. In Section 7, we provide a concrete design example on tuning the FSB system parameters.