Меры справедливости TCP

Мера справедливости — отличный инструмент для определения того, получают ли все потоки TCP справедливую долю доступной пропускной способности сети. Доступны различные протоколы транспортного уровня, справедливость TCP требует, чтобы новый протокол TCP не влиял на производительность других доступных протоколов или изменения самого TCP. Допустим, в сети 5 потоков: 1 TCP Cubic, 1 Reno, 1 NewReno, 1 UDP и 1 BBR. Доступная пропускная способность сети составляет 10 Мбит/с. В идеале все эти 5 потоков должны иметь одинаковую полосу пропускания, т.е. 2 Мбит/с. Но BBR занимает 3 МБ/с, Reno и NewReno — 2 МБ/с, CUBIC — 1 МБ/с, а UDP — 3 МБ/с. В этом сценарии BBR влияет на другие потоки TCP, например Cubic. Соотношение пропускной способности сети, используемой TCP BBR и Cubic, составляет 3:1, что в нормальном случае должно быть 1:1. В литературе существует множество мер справедливости.

Необходимость измерения справедливости TCP:

С момента появления Интернета транспортные протоколы претерпели значительные изменения. Первоначальный RFC 793 был очень простым протоколом TCP. Сегодня в литературе существуют сотни протоколов TCP. Различные устройства используют собственный выбор протокола TCP. Основная цель меры справедливости — проверить совместимость вновь разработанного протокола TCP с другими существующими протоколами TCP. Справедливость — это относительная производительность других TCP, когда этот недавно разработанный, тестируемый TCP используется в той же сети. Если производительность других потоков TCP не страдает из-за этого нового TCP, то он считается хорошим. Затем будут протестированы его новые оптимизации и новые функции, а затем будет рассмотрен только его потенциал превзойти другие TCP. Если новый TCP сильно повредит другим потокам, то нет смысла использовать этот протокол в наших устройствах, потому что он сильно повредит другим. Вот почему измерение справедливости имеет важное значение для сертификации любого недавно разработанного TCP.

Существует очень популярный индекс справедливости, называемый индексом справедливости Раджа Джейна.

Индекс справедливости Джейна

Этот индекс был введен Раджем Джейном, выпускником IISC и Гарвардского университета. В настоящее время он является профессором CSE в Вашингтонском университете.

Если в сети имеется n TCP-потоков, то их пропускная способность обозначается как x1, x2, …, xn. Пропускная способность — это скорость успешной доставки пакетов/сообщений по установленному сетевому соединению. Его также можно представить как пропускную способность, используемую конкретным узлом. Затем индекс Джейна рассчитывается в соответствии с данным уравнением.

Jain Index = Square of the sum of all throughputs/
             (N x sum of squares of all throughputs) 
           = Square of average throughput/
             Average of squared throughput

Если J=1 , то экспериментальный TCP совершенно совместим с другими потоками TCP. Можно предположить, что TCP не вредит другим потокам TCP в сети. Любой новый алгоритм TCP, разработанный сегодня, должен доказать свою эффективность с точки зрения меры справедливости TCP. BBR использовал индекс Джейна в качестве инструмента измерения справедливости и потерпел неудачу. Индекс Джейна учитывает общую пропускную способность всех узлов, но не учитывает пропускную способность их временных рядов.

Предположим, есть два потока TCP F1 и F2. Пропускная способность составляет 10 Мбит/с, и соединение остается активным в течение 100 секунд.

For first 50 seconds, F1: 8 MBPS and F2: 2 MBPS
For next 50 seconds,  F1: 2 MBPS and F2: 8 MBPS,
[Jain"s index takes the average throughput of both the TCP flows] 
Hence T1=T2=5 MBPS, where T= Throughput
J(F1, F2) = (25/25) = 1

В этом случае индекс равен 1, что означает, что оба потока получили равную/справедливую долю полосы пропускания на протяжении всей продолжительности, но это не так. Если мы построим график временного ряда для пропускной способности, то он будет совсем другим. Это ограничение Jain's Index, поэтому BBR не смог стать стандартным RFC из-за этого отставания.

Макс-мин справедливость

Это не показатель измерения, а алгоритм обеспечения справедливости. Этот алгоритм обеспечивает справедливость в сети.

Алгоритм:

1. Это работает обратимо.
2. Рассчитайте справедливую долю для каждого неудовлетворенного потока.
3. Назначьте справедливую долю каждому неудовлетворенному потоку.
4. Если какому-то узлу назначается больше, чем его требование, то он называется переназначенным.
5. Заберите обратно все переназначенные доли, это называется остаточной суммой.
6. Повторно присвойте эту остаточную сумму неудовлетворенным потокам.

Предположим, что по узкому каналу проходит 4 потока с общей доступной пропускной способностью 12 Мбит/с.

Спрос этих потоков A=2.4, B=3, C=4, D=5 Мбит/с.

Шаг 1: Справедливая доля всех 4 потоков = 12/4 = 3 Мбит/с. Сначала назначьте каждому потоку 3 Мбит/с.

Flow A: Assigned 3 MBPS, Demand = 2.4, Over-assigned 0.6 MBPS. 
Flow A is completely satisfied.
Flow B: Assigned 3 MBPS, Demand = 3, Completely satisfied.
Flow C: Assigned 3 MBPS, Demand = 4, Unsatisfied
Flow D: Assigned 3 MBPS, Demand = 5, Unsatisfied

Шаг 2: Вычислите справедливую долю оставшихся неудовлетворенных потоков, используя остаточный поток.

Fair share = 0.6/2 = 0.3
Assign 0.3 MBPS to flow C and D, because they are not yet satisfied
Flow C: Assigned 3.3 MBPS, Demand = 4, Unsatisfied
Flow D: Assigned 3.3 MBPS, Demand = 5, Unsatisfied
Residual amount = 0

Таким образом, все 4 потока получили максимально возможную долю. Потоки A и B удовлетворены, тогда как C и D не удовлетворены.

Если сеть обеспечивает максимально-минимальную справедливость, то она может наказывать те потоки, которые передают больше, чем самая высокая назначенная им доля. Предположим, что потоки C и D являются UDP и поэтому не получают ACK от получателя. Они продолжают посылать в сеть пакеты данных со скоростью 4 и 5 Мбит/с. Максимальная доля, назначенная им сетью, составляет 3,3 Мбит/с. Следовательно,

discard 4 - 3.3 = 0.7 MBPS from flow C
discard 5 - 3.3 = 1.7 MBPS from flow D

Есть одно преимущество максимально-минимальной честности. Если сеть обеспечивает справедливость, то ни один поток не будет нарушен, в противном случае она будет отбрасывать пакеты сети с плохим потоком. Таким образом, эти потоки не смогут навредить другим потокам, которые ведут себя хорошо.

Другие меры справедливости:

Справедливость QoE: это означает качество опыта. Он определяется как функция линейного преобразования. . Система называется абсолютно справедливой , когда все N пользователей получают одинаковое значение QoE. Он не измеряется на шкалах отношений. Используется в интервальных шкалах. Этот индекс ограничен в интервале [0-1]. 0 означает самое низкое QoE. 1 означает идеальную справедливость QoE. Значение 0,5 означает, что половина пользователей получает 0 QoE, а другая половина пользователей получает 1 QoE.

G's Fairness index: Этот индекс справедливости в основном используется интернет-провайдерами в контексте распределения пропускной способности. Индекс справедливости k ^-го порядка G задается как:

Индекс G дает меньшие значения по сравнению с индексом Джейна. Меньшие значения более чувствительны к несправедливому распределению пропускной способности, и их значение может достигать 0, что указывает на очень несправедливое распределение. Индекс Джайна является очень средним индексом, в то время как индекс G больше фокусируется на равенстве.

Например:

distribution: {20, 20, 20, 0}
Jain"s index = 0.75
G"s index = 0

Таким образом, индекс Джайна очень неоднозначен, в то время как индекс Г дает более подробные сведения о распределении пропускной способности.