Toward end-to-end fairness: a framework for the allocation of multiple prioritized resources in switches and routers

As flows of traffic traverse a network, they share with other flows a variety of resources such as links, buffers and router CPUs in their path. Fairness is an intuitively desirable property in the allocation of resources in a network shared among flows of traffic from different users. While fairness in bandwidth allocation over a shared link has been extensively studied, overall end-to-end fairness in the use of all the resources in the network is ultimately the desired goal. End-to-end fairness becomes especially critical when fair allocation algorithms are used as a component of the mechanisms used to provide end-to-end quality-of-service guarantees. This paper seeks to answer the question of what is fair when a set of traffic flows share multiple resources in the network with a shared order of preference for the opportunity to use these resources. We present the Principle of Fair Prioritized Resource Allocation or the FPRA principle, a powerful extension of any of the classic notions of fairness such as max–min fairness, proportional fairness and utility max–min fairness defined over a single resource. We illustrate this principle by applying it to a system model with a buffer and an output link shared among competing flows of traffic. To complete our illustration of the applicability of the FPRA principle, we propose a measure of fairness and evaluate representative buffer allocation algorithms based on this measure. Besides buffer allocation, the FPRA principle may also be used in other contexts in data communication networks and operating system design.