A Framework for Evaluating Fairness in Input-Queued Switches: Fundamental Principles and Practical Strategies

摘要

Fairness in traffic management can improve the isolation between traffic streams, offer a more predictable performance, eliminate transient bottlenecks, mitigate the effect of certain kinds of denial-of-service attacks, and serve as a critical component of a quality-of-service strategy to achieve certain guaranteed services such as delay bounds and minimum bandwidths. Several research efforts have attempted to achieve fairness in input-queued switches by one measure or another. However, there has not been a unifying framework for evaluating these different fairness strategies against each other. In this paper, we formalize the notion of fairness in input-queued switches through a rigorous framework based on an extension of the max-min notion of fairness. Our framework permits the algorithmic determination of the fair rates to be allocated to the flows through the switch and also permits a quantitative evaluation of strategies that aim to achieve fairness in input-queued switches. We show that our algorithm can be implemented in a distributed fashion to dynamically determine flow rates. We further propose a practical scheduling strategy based on our algorithm. We present simulation results using real gateway traffic traces to evaluate the fairness of a variety of popular scheduling algorithms for input-queued switches. The results show that our scheduling strategy achieves better fairness than other known algorithms for input-queued switches.