Max-Min公平性

Max-Min公平性由Hayden在文章（Round-Robin Scheduling for Max-Min Fairness in Data Networks）中提出，旨在评估队列调度机制的公平性。

首先，定义几个术语。速率分配γ，用来指示为每个会话（队列）分配的与其请求及链路容量相关的一个速率函数，γ表示为速率份额。例如，对于每个会话x， 有0<= γ(x) <= λ(x)，对于所有使用链路L的会话，有以下等式：

$$\sum _{x\ni l}\gamma (x)<=1$$

即所有会话占用的带宽份额小于总的带宽量，这里总带宽量表示为1。

如果某个会话（session）获得了其所请求的速率，表明满足其需求。但是如果链路L的容量全部分配给了使用它的会话，并且某个会话获得了不低于所有其它所有使用链路L的会话的速率，表明网络的瓶颈为链路L的容量。分配函数γ生成的速率列表组成为一个唯一的向量，其包含分配给每个会话x的速率份额：γ(x)。如果为k个不同的会话分配了相同的速率，则在速率列表中此速率将出现k次。速率列表表示为一个递增的序列。

以下定义所谓公平。γ分配满足Max-Min标准，即不存在其它的分配方法，使的新的速率列表依次高于γ分配的速率列表中的值。简单的说，γ分配给某个会话的最小速率已经是尽可能的大，并且，分配出去的倒数第二小的速率也是尽可能的大了，以此类推。

由此Max-Min分配给会话x的速率，称之为公平速率R_F(x)。会话x的拥塞指数（Congestion Index）：I(x)表示其公平速率与其它会话的公平速率的比值，所有使用最小公平速率的会话的拥塞指数都为1，所有使用倒数第二小公平速率的会话的拥塞指数为2，以此类推。

不难证明，仅当每个速率得不到满足的会话至少有一个瓶颈链路时，才会具有满足Max-Min标准的分配方案，基于此，很容易看到，为何轮询调度器有可能达到Max-Min的公平速率。考虑一个会话，其请求超过其吞吐的带宽，此会话的报文将集聚在其最拥塞链路的入口处，因此，其永远不会错过此链路的发送轮询。

这保证了其平均吞吐至少与此链路中其竞争者的吞吐相同，并且，保证链路保持繁忙。因此，此链路应为以上所讨论会话的瓶颈链路。每一个会话，如果不是被其自身带宽需求所限，就存在这样一个瓶颈链路，所以，最终的平均吞吐应与Max-Min平均速率相同。当然，这里简要表述的合理性并不能提供确凿证据。

以下介绍中，瓶颈(bottleneck)用于表示相对于Max-Min分配的瓶颈，换句话说，如果R_F(x) > R_F(y)对于所有使用链路L的会话y都成立，并且：

$$\sum _{y\ni l}{R}_F(y)=1$$

称链路L是使用此链路的会话x的瓶颈。举例来说，如果满足R_F(x)=γ(x)的条件，第0跳链路即为会话x的瓶颈链路。每个会话至少有一个瓶颈链路（如：跳数为h的链路），h的范围为： 0<=h<H(x)，（第H(x)+1跳链路不为瓶颈）。

如下图所示，会话x₄的请求为1/6速率，会话x₆的请求为1/3速率，其余会话的速率请求为1，因此，会话x₄的Max-Min公平速率为1/6，会话x₅的公平速率为1/2，其它会话的公平速率为1/3。会话x₄的拥塞指数（Congestion Index）为1，会话x₅的拥塞指数为3，其它会话的拥塞指数为2。Max-Min分配的速率列表为： (1/6 , 1/3 , 1/3 , 1/3 , 1/3 , 1/3 , 1/2)。会话x₁和x₂以链路L1为瓶颈链路。会话x₃有两个瓶颈链路–L1和L4。会话x₄的瓶颈调数为0 – 其请求。链路L3是会话x₅的瓶颈链路。会话x₆，的瓶颈为L4.链路L4也是会话x₇的瓶颈链路。链路L2不是任何会话的瓶颈，其还有未使用的链路容量。

x1 ------------> x4 ------------> x6 ------------> x2 -----------------------------------> x5 ------------> x7 ------------> x3----------------------------------------------------------------------------------> O----------------------O----------------------O----------------------O----------------------O L1 L2 L3 L4