Равнодоступность по максиминному критерию
Пока мы еще не говорили о том, как распределять пропускную способность между несколькими отправителями. Кажется, что ответ очень прост: можно разделить пропускную способность между ними поровну. Однако на самом деле этот вопрос требует некоторых уточнений.
Во-первых, зададимся вопросом: какое отношение эта проблема имеет к контролю нагрузки? В конце концов, если сеть предоставляет отправителю некоторое количество пропускной способности, он должен просто использовать то, что у него есть. Однако на практике сети часто не резервируют строго ограниченное количество пропускной способности для потока или соединения. Конечно, для некоторых потоков они могут это делать (если есть поддержка качества обслуживания), но, как правило, многие соединения стремятся использовать максимум доступной пропускной способности; также возможен вариант, при котором сеть выделяет ресурсы для совместного использования группой соединений. К примеру, дифференцированное обслуживание IETF разделяет трафик на два класса, и соединения конкурируют друг с другом в пределах каждого из этих классов. Часто все соединения одного IP-маршрутизатора используют общую пропускную способность. В таких случаях распределение пропускной способности между конкурирующими соединениями должно осуществляться за счет механизмов контроля нагрузки.
Во-вторых, не совсем ясно, что такое равноправие потоков в сети. Если N потоков используют один канал, то решение довольно просто: каждому из них выделяется 1/N пропускной способности (в случае импульсного трафика эта величина по соображениям эффективности будет немного меньше). Но что если потоки используют разные, но пересекающиеся пути? К примеру, если один поток проходит по трем каналам, а остальные потоки — по одному? Очевидно, что поток, проходящий по трем каналам, потребляет больше сетевых ресурсов. Поэтому в некотором смысле справедливее было бы выделить ему меньше пропускной способности, чем остальным потокам (проходящим по одному каналу). Кроме того, неплохо было бы обеспечить возможность добавления новых одноканальных потоков за счет уменьшения пропускной способности трехканального. Как показывает этот пример, между равноправием и эффективностью всегда существуют противоречия.
Однако здесь мы будем использовать такое определение равноправия, в котором оно не зависит от длины сетевого пути. Даже в такой простой модели разделение пропускной способности поровну между соединениями является достаточно сложной задачей, так как разные соединения будут использовать разные пути, а эти пути, в свою очередь, будут обладать разной пропускной способностью. Это может привести к тому, что в нисходящем канале какого-то из потоков возникнет узкое место, и такой поток получит меньший «кусок» восходящего канала, чем другие. В таком случае уменьшение пропускной способности, выделяемой другим потокам, лишь замедлит их работу, но не исправит ситуацию с «застрявшим» потоком.
Часто в сетях удобнее использовать форму равноправия, которая называется равнодоступностью по максиминному критерию. Это значит, что увеличение пропускной способности одного потока невозможно без уменьшения пропускной способности какого-либо другого потока с меньшей или равной пропускной способностью. Иными словами, от увеличения пропускной способности потока страдают менее «обеспеченные» потоки.
Рассмотрим пример. На рис. 6.17 показано распределение пропускной способности по максиминному критерию в сети с четырьмя потоками A, B, C и D. Все каналы, соединяющие маршрутизаторы, обладают одинаковой пропускной способностью, принятой за 1 (хотя на практике это обычно не так). На пропускную способность канала, расположенного слева внизу (между маршрутизаторами R4 и R5), претендуют три потока. Поэтому каждый из них получает по 1/3. Оставшийся поток, A, конкурирует с B на участке от R2 до R3. Поскольку для B уже выделена 1/3 пропускной способности канала, A получает оставшееся количество, 2/3. Как видно из рисунка, на остальных каналах часть пропускной способности не используется. Но эти ресурсы нельзя отдать какому-либо потоку, не снизив пропускную способность другого, более медленного потока. К примеру, если на участке от R2 до R3 выделить потоку B больше пропускной способности, то потоку A достанется меньше. Это логично, поскольку на данный момент у A пропускной способности больше. Но для того чтобы обеспечить большую пропускную способность для потока B, придется снизить пропускную способность C или D (или обоих), и тогда его (или их) пропускная способность станет меньше пропускной способности B. Таким образом, данное распределение соответствует максиминному критерию.
Рис. 6.17. Распределение пропускной способности по максиминному критерию
для четырех потоков
Распределение пропускной способности по максиминному критерию можно вычислить на основе данных обо всей сети. Чтобы наглядно это себе представить, предположим, что скорость всех потоков медленно возрастает, начиная от 0. Как только у одного из потоков возникает узкое место, его скорость перестает расти. Далее скорость остальных потоков продолжает увеличиваться (при этом доступная пропускная способность делится поровну), пока каждый из них не дойдет до своего узкого места.
В-третьих, не очень понятно, на каком уровне рассматривать равноправие. Сеть может обеспечивать равноправие потоков на уровне соединений, соединений между парой хостов или всех соединений одного хоста. Эту проблему мы обсуждали, когда говорили о взвешенном справедливом обслуживании (см. раздел 5.4): выяснилось, что с каждым из этих вариантов связаны определенные трудности. К примеру, если считать равноправными все хосты, активно работающий сервер будет получать не больше ресурсов, чем обычный мобильный телефон; если же равноправными считать все соединения, хостам будет выгодно открывать дополнительные новые соединения. Поскольку на этот вопрос нет однозначного ответа, равноправие часто рассматривается применительно к соединениям, однако такое равноправие совсем не обязано быть точным. В первую очередь важно, чтобы ни одно соединение не осталось без пропускной способности. На самом деле, TCP позволяет открывать множественные соединения, что вызывает более жесткую конкуренцию. Эта тактика подходит для приложений, особенно требовательных к возможностям сети. Например, ее использует BitTorrent для однорангового совместного использования файлов.
Сходимость
Последний критерий состоит в том, что алгоритм контроля нагрузки должен быстро сходиться к справедливому и эффективному распределению пропускной способности. При обсуждении выбора рабочего режима мы исходили из того, что сетевая среда является статической. Однако на практике соединения то появляются, то исчезают, а пропускная способность, требующаяся каждому отдельному соединению, изменяется со временем — так, например, пользователь может долго просматривать веб-страницу, а затем вдруг начать загрузку большого видеофайла.
Такое непостоянство требований к сети приводит к тому, что идеальный рабочий режим постоянно меняется. Хороший алгоритм контроля нагрузки должен быстро сходиться к идеальному рабочему режиму и следить за его изменением с течением времени. Если алгоритм будет сходиться слишком медленно, он не будет успевать за изменениями рабочего режима. Если алгоритм будет нестабильным, в некоторых случаях он не будет сходиться к нужной точке или будет долго колебаться вокруг нее.
На рис. 6.18 показан пример распределения пропускной способности, которая изменяется со временем и быстро сходится. Изначально поток 1 получает всю пропускную способность. Через секунду начинает работать поток 2. Ему тоже нужна пропускная способность. Поэтому распределение быстро меняется, так чтобы оба потока получали по 1/2. Еще через три секунды появляется третий поток. Но он использует только 20 % пропускной способности — меньше, чем то, что ему полагается исходя из идеи равноправия (1/3). Потоки 1 и 2 быстро реагируют на изменение ситуации, и каждый из них получает 40 %. В момент времени 9 с второй поток отключается, а третий продолжает работать без изменений. Поток 1 быстро занимает 80 % пропускной способности. В каждый момент времени суммарная пропускная способность приблизительно равна 100 %, то есть возможности сети используются полностью; при этом все конкурирующие потоки оказываются в равных условиях (но не используют больше пропускной способности, чем им нужно).
