# Priority Queues with Fractional Service for Tiered Delay QoS
## 3 Fractional Service Buffers
Basically, Class-0 corresponds to the most delay-sensitive packets and Class-\(M\) the least delay-sensitive packets as determined by the flow scheduler. A Class-\(i\) packet has a delay limit \(\tau_{i}\) to be protected by the FSB, where \(\tau_{0}<\tau_{1}<\ldots<\tau_{M}\). Strict priority queues can be used to differentiate service qualities of multiple classes of traffic. However, strict priority queues, by itself, cannot protect the throughput or the delay of lower-priority classes when higher-priority classes present heavy traffic. Furthermore, the relative service level between traffic classes cannot be quantified or adjusted. The FSB serves its buffers in a strict priority order as well, but it employs a _fractional service algorithm_ (FSA) to \"move\" packets between buffers in a controlled fashion thus achieving delay guarantees. In the FSB, Class-0 has the highest service priority while Class-\(M\) the lowest. Buffer-\(i\) earns a unit fractional credit whenever there is a packet arrival from the flow scheduler at ANY of the higher-priority buffers, _i.e._, Buffer-0, Buffer-1,... Buffer-\((i-1)\). Once the credit accumulates to one full credit, the packet at the head of Buffer-\(i\) is \"moved\" to Buffer-\((i-1)\). The credit balance of Buffer-\(i\) is then reset to zero. While packet sizes may be used to determine flow fairness in the flow scheduler, packets of different sizes are treated equally by the FSB. We will elaborate on how the FSA moves packets between queues such that a lower-priority class effectively shares a fraction of service with its higher-priority counterpart. The FSB maintains a credit counter for each buffer except Buffer-0. For every packet arriving at Buffer-\(i\), each lower-priority buffer, Buffer-\((i+k)\), \(1\leqslant k\leqslant M-i\), receives a unit fractional credit of \(\eta_{i+k}=1/(m(i+k))\), regardless of the size of the arriving packet. In other words, Buffer-\(i\) receives a credit \(1/(mi)\) whenever a packet arrives at one of the buffers with a priority higher than \(i\) (_i.e._, Buffer-0, Buffer-1,..., Buffer-\((i-1)\)). The integer \(m\) is a configurable parameter used to control the unit fractional credit. When the credit accumulated by Buffer-\(i\) reaches unity, its leading packet is moved to Buffer-\((i-1)\) and is thus \"promoted\" to Class-\((i-1)\). A promoted packet is treated equally as any other newly arriving packets to that class. We note that unit fractional credits always accumulate to unity with no leftovers. This would avoid credit remainder issues and their associated analytical and  
Figure 1: Two-stage packet scheduling architecture. algorithmic complications. Similar to a strict priority queueing system, services are dedicated to a lower-priority buffer when all the higher-priority buffers are empty. To illustrate the idea behind unit fractional credits, let us consider the case \(m=1\). In this case, Buffer-1 will receive one full credit for every packet arriving at Buffer-0 from the flow scheduler. Buffer-2 will receive 1/2 of credit for every packet arriving at either Buffer-0 or Buffer-1, from the flow scheduler. Buffer-3 will receive 1/3 of credit for every packet arriving at Buffer-0, Buffer-1, or Buffer-2, from the flow scheduler, and so on. This harmonic descending of the fractional credit with respect to the queue index \(i\) is reasonable since the amount of higher-priority traffic included in generating the credit for Buffer-\(i\) increases linearly with \(i\). The configurable integer \(m\) controls the rate of promotion of the lower-priority traffic. It can be used as a tuning parameter in defining the QoS levels, in terms of delay limits, for the different traffic classes. A larger \(m\), which implies a slower rate of promotion for lower-priority classes, would favor higher-priority classes, and _vice versa_. Since packets in Buffer-1 are promoted to Buffer-0 where transmission takes place, Buffer-1 in effect receives \(1/(m+1)\) of bandwidth.