# Priority Queues with Fractional Service for Tiered Delay QoS
## 2 Related Works  
In terms of providing better packet delay for each traffic flow, the scheduler in [5] separates traffic flows with substantially different bandwidth requirements into different groups. Then, a time-stamp based scheduler is used to schedule the service of each group while a round-robin scheduler is used to service flows within a group. However, due to its round-robin structure, there is an inherit dependency between the allocated bandwidth of a flow and the queueing delay of the flow's packets [6]. Furthermore, only the first packet of each flow can receive a delay protection.  
In [6], the authors presented a two-stage architecture that separates the dependencies between bandwidth allocations and packet delays. The first stage is a number of rate regulators that shape the traffic of each flow while the second stage is a number of strict priority queues that queue the regulated packets of each flow. Delay protections are achieved using an admission control policy that monitors the occupancy level at each priority queue. This implementation requires one buffer per flow to regulate each flow's packets, in additional to the priority queues. These flow buffers require a separate management algorithm to ensure efficient usages of the memory space [7].  
Class-based schedulers, on the other hand, have a far simpler approach in managing the memory space. In the Relative Differentiated service (RD) [8] framework, packets are grouped into \(M+1\) classes of service where Class-i packets receive better performance metrics than Class-\(i+1\) packets for all \(0\leqslant i<M\). One simple way of realizing RD is to use strict priority queues where the highest priority class is assigned to the highest priority queue and each queue is serviced in the order of their priority. However, such a method does not provide any means for adjusting the quality of each priority class and no delay protections can be offered to lower priority classes.  
In terms of overcoming the inflexibilities of strict priority queues, the authors of [8] presented a delay-ratio idea for determining service orders of each priority class. Specifically, they defined a delay ratio between every pair of service classes and the scheduler strives to maintain these service ratiosat their target levels. In this manner, the relative service quality in terms of packet delays between classes is maintained, regardless of the load of higher-priority classes. The authors also applied their delay-ratio idea to existing queueing disciplines, such as Generalized Processor Sharing [9] and Waiting-Time Priority [10], to deliver controllable service qualities. This approach only offers a single dimension in QoS provisioning, namely the delay-ratio between classes. Separate mechanisms are required to ensure the fairness and maximum delay of each traffic class [11].  
Other related literature, such as delay-dependent priority jumps [12], deals with this strict priority issue by prioritizing each packet based on its delay limit and tagging the packet with its entry time. The priority of a packet is increased if the maximum queueing delay of the packet in a priority queue is reached. This method requires tagging and updating timestamps of packets to accomplish priority increases.  
In [13], the authors presented several priority-jumping policies for systems with two priority classes. Each policy has a unique criterion for increasing the priority of lower priority packets. They concluded that each policy has its pros and cons and no single policy is a clear winner. The system that bases its priority increase criterion on the arrival of higher priority packets is the most \"self-adaptive\" to different traffic conditions. However, obtaining an exact analytical expression for this system is \"extremely difficult\".