前置

要证明tcp fairness 需要一些前置知识（注，本文大部分抄袭，很少原创）

 

假设

首先我们假设所有资源按时间片分配，那么第i个user 第t个时间段内所分配的资源为：

该用户所使用的全部资源为:

我们再来假设，用户只接受二进制控制用来表示用户是否需要扩大资源和减少资源

既当y = 0 时，表明正反馈需要x 升高资源既：

反之：

 

我们假设 x是成线性分布即：

所以：

其中AI, Bi 皆为y = 0是参数，n 为用户的个数。

可变形为：

同理 AD, BD为y=1时参数，

条件

1、资源恒定：

假设所有资源核定既

既超过Xgoal的用户将收到负反馈y=0使得该用户降资源，而小于Xgoal将收到正反馈y=1。

2、公平性

保障每个用户使用相同量的资源，这里我们需要一个衡量公平性的函数，具体为啥参考论文（R. Jain, D.M. Chiu and W. Hawe. A Quantitative Mea- sure of Fairness and Discrimination for Resource Alloc- ation in Shared Systems, Technical Report, Digital Equipment Corporation, DEC-TR-301, 1984.）

3、普遍性：

每个用户相互独立，只依赖于反馈调节

5、覆盖度

到达Xgoal 的时间我们称为responsiveness，而在Xgoal的范围我们称为smoothness

目标

 

有图克制efficiency line 为Xgoal，我们希望资源最大化则需要靠近这条直线(这里我们只考虑两个维度，即user 1 和user2)，fairness line为公平直线在这条直线上的所有点都是 x1 = x2，同时我们希望我们最终分配的点靠近这条线，两条线的交点既为最优点。

如图x0，x0在efficiency line 以下，所以出于低负载情况，会受到正反馈而增加负载。

 

证明

1、资源恒定

假定资源过载时系统必然受到负反馈，且负反馈必然降低该用户的资源。而资源富裕时必然受到正反馈而扩大该用户的资源，既当正反馈时函数单调递增，负反馈时函数单调递减。可得出以下等式：

 

这样可以保证资源狠定在Xgoal附近。

2、公平性保障

要保障公平性我们需要保障函数无线靠近公平线，即公平函数无线趋于1：

要保障函数单调递增，c必须大于等于0。如果c = 0 则函数为一条直线既f t + 1 = f t。所以我必须保证至少有一个反馈 会使得 朝着公平线方向推进即

联立3 8 9 不等式可以得出

该不等式保证了函数不断向公平线推进，并且在Xgoal 上下波动

3、普遍性：

上面不等式其实已经包含了普遍性，但是我们很可能由于缺乏历史记录，而不发准确的算出对应的sum(x(t))。所以我们需要给出一个更加通用的模型。既正反馈的前提下 x(t + i) > x(t) 反之亦然。

 

可以得出

我们可以把12引申为：

但是考虑到拐点的情况x t + 1 == x t，所以我们需要一个更严格的条件：

Nmax 为最大用户数，其中Xmax Xmin 为：

同时我们也保证了不会出现的情况。

这样我们最终得出了：

4、合并：

等式7 显示，F(t - 1) - F(t)是单调递增函数。 所以a越大b 约小 ，则收敛速度越快。考虑到我们无法对Nmax Xmin 和Xmax 进行衡量，我们可以假设Xmax和Nmax  为无穷大,  Xmin为0，则Ad = 0，BD则无关紧要。bi 最小为1。

所以当正反馈到来时做加法增，负反馈到来时做乘法减。

 

 

这些花了我一天时间了解论文，感觉真么啥意思，还是看看就好。听说某人说我写的是科普文，固弄一篇出来让他看不懂 oh yeah

 

reference

analysis of the Increase and Decreas,e Algorithms for Congestion Avoidance in Computer Networks 

Dah-Ming CHIU and Raj JAIN

Digital Equipment Corporation, 550 King Street (LKG1-2/,419), Littleton, MA 01460-1289, U.S.A.