1

I am currently studying the Additive Increase Multiplicative Decrease method, used in TCP as congestion avoidance technique. If we have K TCP sessions sharing a common link of bandwidth R, it is said that this technique guarantees fairness for all the sessions, i.e, each session will have a throughput of R/K.

Now, I'd like to prove this fairness mathematically (reaching the conclusion that, regardless of the initial values of the throughput of each session, they will all eventually tend to R/K).

Thanks !

4

2 回答 2

1

Chiu-Jain 的论文给出了一个非常直观的答案。从那里，您可以轻松地看到一种可以进一步形式化的 AIMD 的一般论点。你真正需要的只是在那张纸上。

如果你坚持用字母证明而不是用图表证明，你可以这样推理：

假设x, y是带宽的初始份额，即R。为方便起见2d = R。

窗口大小比率的顺序演变如下：

(init) x/y -> 
(MD) (x/2)/(y/2) = x/y -> 
(AI) (x + d)/(y + d) -> 
(MD) ((x + d)/2)/((y + d)/2) -> 
(AI) ((x + d)/2 + d) / ((y + d) /2 + d) = (x + d + 2d)/(y + d + 2d)

这最后一个是(x + d + 2d)/(y + d + 2d)。你可以看看你是否把它写下来之后它会如何发展。

一般来说， (x + k /y + k) -> 1随着k增长，在我们的特定情况下，收敛甚至是指数级的，因为 k 随着时间呈指数级增长。这就是从和的起点收敛到公平的样子。x = 5y = 3

为了证明超过 2 个流，您可以采用具有最大和最小起始带宽份额的流。其他人都介于两者之间，所以证明应该仍然很简单。我们在这里谈论的收敛是向公平的收敛，而不是向公平的收敛，R/K因为实际上系统将在R/2K和R/K永远之间摇摆不定。

于 2014-09-01T08:28:54.523 回答
0

如果您想要学术水平的反馈，我建议您搜索 Academic.google.com。题为“关于加法增加和乘法减少的公平性的注释”以及看起来很漂亮的数学可能就在你的小巷里。

于 2014-07-14T22:27:12.410 回答