# Priority Queues with Fractional Service for Tiered Delay QoS
## 3 Fractional Service Buffers
For example, in a 3-Buffer system with \(m=1\), Buffer-1 effectively receives 50% of bandwidth. It is important to note that Buffer-\(i\) carries not only Class-\(i\) packets from the flow scheduler, but packets promoted from lower-priority buffers. Packets in Buffer-0 (Buffer-1) may consist of packets from Class-1 (Class-2) that were promoted to Class-0 (Class-1) over time, via the FSA. Similarly, if \(m=2\), Class-1 and Class-2 packets jointly receive an effective service share of \(1/3\). If \(m=3\), Class-1 and Class-2 packets jointly receive an effective service share of \(1/4\), and so on. Thus, a large \(m\) damps the effective service share jointly received by the lower-priority classes thereby increases the delay experienced by these classes. Clearly, when there are many priority classes, a small \(m\) should be used to ensure that the lower-priority classes are not shut out from service under heavy traffic conditions. In order to achieve delay guarantee for each class of packets, we impose an upper limit on the queue length of each buffer. From the perspective of an incoming Class-\(i\) packet, the total queue length from Buffer-0 to Buffer-\(i\) affects its delay. Unless these higher-priority buffers become empty along the process, Class-\(i\) packets have to be promoted, one buffer at a time, from Buffer-\(i\) to Buffer-0, in order to receive service. Therefore, instead of constraining the queue lengths of individual buffers, we impose a threshold \(K_{i}\) on the _aggregate queue length_ of Buffer-0 to Buffer-\(i\). That is, the FSB algorithm prevents the total number of packets inside the lowest \(i\) buffers, denoted by \(Q_{i}\), from exceeding \(K_{i}\). As such, a Class-\(i\) packet can enter Buffer-\(i\) only if it does not result in \(Q_{i}>K_{i}\). Thus, a Class-\(i\) delay violation occurs when a Class-\(i\) packet arrives and finds \(Q_{i}=K_{i}\). We refer to this event as a packet overflow. An overflowed packet is no longer protected within the delay limit of its priority class originally determined by the flow scheduler. Once a packet overflows from Buffer-\(i\) to Buffer-\((i+1)\), it will be treated as Class-\((i+1)\) and, thus, receives the delay protection of Class-\((i+1)\). If Buffer-\((i+1)\) has also reached its threshold, the packet will be overflowed to Buffer-\((i+2)\) and so on. Figure 2 illustrates the packet management of the FSB for \(M+1\) buffers. Figure 2a shows that classified packets from the flow scheduler enter different buffers based on their assigned delay classes. Figure 2b shows packet movements between adjacent buffers based on the FSA, where a rightward arrow signifies packet promotion, while a leftward arrow signifies packet overflow. We note that without buffer capacity thresholds, the FSB becomes strict priority queues when \(m\)\(\rightarrow\)\(\infty\). An overflow could occur under two circumstances. To illustrate these scenarios, we label each packet with two integers, _ij_, where \(i\) represents the packet's current service class and \(j\) the position of the packet within the buffer of its class. As shown in Figure 3, we can logically view the buffers concatenated in the order of their priorities. In Figures 4 and 5 we illustrate how the FSB handles these two scenarios with a simple pointer management. The FSB maintains a memory pointer for the tail of each buffer. To illustrate, we assume \(m=1\) for a 3-buffer system with thresholds \(K_{0}=6\), \(K_{1}=12\), \(K_{2}=18\) for classes 0, 1, and 2 respectively. Figure 4 illustrates the first overflow scenario. In Figure 4a, the arriving Packet \(X\) is classified as Class-1 and is supposed to be admitted to Buffer-1. However, the threshold of Class-1 has already been reached (_i.e._, \(Q_{1}=K_{1}\)) at the time. Thus, \(X\) has to be overflowed to the _tail_ of Buffer-2 as shown in Figure 4b and counted as a delay violation. In this case, no service credit is awarded to Buffer-2 as a result of _X_'s arrival because \(X\) is not admitted to Buffer-1. Figure 5 illustrates the second overflow scenario.