Max-min fair bandwidth allocation algorithms for packet switches

With the rapid development of broadband applications, the capability of networks to provide quality of service (QoS) has become an important issue. Fair scheduling al-gorithms are a common approach for switches and routers to support QoS. All fair scheduling algorithms are run-ning based on a bandwidth allocation scheme. The scheme should be feasible in order to be applied in practice, and should be efficient to fully utilize available bandwidth and allocate bandwidth in a fair manner. However, since a sin-gle input port or output port of a switch has only the band-width information of its local flows (i.e., the flows traversing itself), it is difficult to obtain a globally feasible and efficient bandwidth allocation scheme. In this paper, we show how to fairly allocate bandwidth in packet switches based on the max-min fairness principle. We first formulate the problem, and give the definitions of feasibility and max-min fairness for bandwidth allocation in packet switches. As the first step to solve the problem, we consider the simpler unicast scenarios, and present the max-min fair bandwidth alloca-tion algorithm for unicast traffic. We then extend the anal-ysis to the more general multicast scenarios, and present the max-min fair bandwidth allocation algorithm for multi-cast traffic. We prove that both algorithms achieve max-min fairness, and analyze their complexity. The proposed al-gorithms are universally applicable to any type of switches and scheduling algorithms.