Anonymity in packet scheduling under the max-min fairness criterion

Fairness is an important criterion in the design and evaluation of scheduling algorithms of data packets in networks. Ensuring fairness, however, limits the randomness in scheduling policies thus reducing the privacy of network activity from an eavesdropper. In this work, the design of max-min fair scheduling protocols is investigated from the perspective of achieving a desired degree of user anonymity. Specifically, the Fair Queueing algorithm, which is known to be max-min fair, is considered and a metric is proposed to compute the anonymity of this scheduling algorithm. It is found that the Fair Queueing algorithm does not achieve maximum anonymity even with unlimited buffer capacity. Consequently, a relaxation of the Fair Queueing algorithm is proposed, where the window of minimum fairness computation is expanded. It is shown that with sufficient relaxation, the modified fair queuing algorithm can achieve any desired degree of anonymity thus demonstrating the trade off between fairness and anonymity.