An approximation to rate-equalization fairness with logarithmic complexity for QoS

Rate-guaranteed scheduling protocols ensure that packets from each input flow are forwarded at a rate no less than the rate reserved by the flow. WFQ is the classical example. Many of these protocols, including WFQ, provide both rate and fairness guarantees. In particular, they distribute unused capacity among among the flows in proportion to the reserved rate of each flow. In earlier work, we presented a scheduling algorithm that distributes unused capacity to flows whose reserved rate is the least. However, the per-packet complexity of this algorithm, known as rate-equalization fairness, is linear in the number of flows. Here, we present an algorithm that approximates rate-equalization fairness, but with only logarithmic complexity per packet.