Как доказать справедливость AIMD в ПТС?
В настоящее время я изучаю метод аддитивного увеличения, мультипликативного уменьшения, используемый в TCP в качестве метода предотвращения перегрузки. Если у нас K сеансов TCP, совместно использующих общую линию пропускной способности R, говорят, что этот метод гарантирует справедливость для всех сеансов, то есть каждый сеанс будет иметь пропускную способность R/K.
Теперь я хотел бы доказать эту справедливость математически (делая вывод, что, независимо от начальных значений пропускной способности каждого сеанса, все они в конечном итоге будут стремиться к R/K).
Спасибо!
2 ответа
Очень интуитивный ответ проиллюстрирован в статье "Чиу-джайн". Оттуда вы можете легко увидеть некий общий аргумент для 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 = 5 а также y = 3,
Чтобы доказать это для более чем 2 потоков, вы можете взять потоки с наибольшей и наименьшей начальной долей полосы пропускания. Все остальные находятся между ними, поэтому доказательство должно быть простым. Конвергенция, о которой мы здесь говорим, - это конвергенция к справедливости, а не конвергенция к R/K потому что в действительности система будет колебаться между R/2K а также R/K навсегда.
Если вам нужна обратная связь на научном уровне, я рекомендую поискать scholar.google.com. Один из них, озаглавленный "Записка о справедливости аддитивного увеличения и мультипликативного снижения" с причудливой математикой, может оказаться прямо в вашем переулке.