Базовым критерием обеспечения принципа «справедливого распределения ресурсов» в сетевом мире считается критерий max-min. Он был введен и сформулирован в 1981 году в [Jaffe81]: «пропускная способность для каждого потока должна быть как минимум равна пропускной способности каждого другого потока, проходящего через тот же критический ресурс» (each user’s throughput is at least as large as that of all other users which have the same bottleneck). Для каждого потока ресурсы могут быть распределены справедливо как на всем пути, так и локально в рамках каждого сетевого узла. Для того чтобы можно было говорить о «справедливом распределении ресурсов» на всем пути прохождения потока, необходимо и достаточно, чтобы этот принцип был реализован локально в каждом сетевом узле маршрута.

Формально критерий max-min может быть определен следующим образом. Пусть существует множество пользователей N и вектор х - (х_п; х_п> 0; п е N), где х_п- относительная величина размера полосы пропускания, предоставляемой пользователю п. Отметим, что в данном случае подразумевается, что один пользователь может инициировать один поток. Вектор х называется выполнимым, если сумма запрашиваемых полос пропускания не превышает емкость выходного канала (т.е. единицу)^{и не}Р^авеннулю.

Критерий max-min нашел широкое применеие в сетевых технологиях для определения справедливого распредления ресурсов в связи с тем, что требования к ресурсам (в данном случае конкретно к полосе пропускания) у всех потоков разные. Поэтому есть необходимость «защищать слабых» и «не дать зарваться сильным». 1ETF и ATM Forum сформулировали ряд правил по справедливому выделению ресурсов конкурирующим потокам:

• ресурсы выделяются в соответствии с очередностью поступления запросов;

• пользователю никогда не выделяется ресурсов больше чем им запрошено;

• всем пользователям с неудовлетворенными запросами выделяется одинаковое количество ресурсов.

Изначально количество ресурсов, которое получает каждый новый пользователь в соответствии с критерием тах-пип, равно количеству ресурсов, занимаемых пользователем с минимальными запросами, остальные ресурсы распределяются равномерно среди пользователей с неудовлетворенными запросами. Такой принцип обеспечения справедливого распределения ресурсов использует простой факт: для нового потока в нагруженном узле ресурсы могут быть выделены только путем отбора от существующих потоков. Поэтому считается, что безопаснее забрать ресурсы у потока с неудовлетворенным запросом, нежели у потока, который и так занимает минимальное количество ресурсов. Формально критерий можно описать следующим образом [Ке11у97]. Вектор х соответствует критерию тах-тл.п, если он является выполнимым и для каждого потока п е N значение х_пне может быть увеличено (соблюдая свойство выполнимости вектора) без уменьшения полосы пропускания х . для некоторого потока п* для которого х . < х_п. Критерий шах-т!п дает абсолютный приоритет потокам с маленькими запросами, т.е. если х^. <х_п, то х_пне получает увеличения количества ресурсов независимо от того много или мало он просит. Рис. 2.6 иллюстрирует представленную концепцию.

Рассмотрим пример, каким образом динамически будет возрастать нагрузка и как будет обеспечен принцип «справедливого распределения ресурсов» в соответствии с критерием max-min в некоторой гипотетической сети. Пусть существует сеть, состоящая из пяти маршрутизаторов, соединенных каналами разной емкости в соответствии с рис. 2.7. Обратим внимание, что каналы 2, 3 и 4 имеют пропускную способность 100 Мбит/с, а канал 1 - только 34 Мбит/с. Далее предположим, что существует восемь пар нагрузки TCP источник-приемник Sn-Dn (source-destination). Для того, чтобы обеспечить принцип «справедливого распределения ресурсов» в соответствии с критерием max-min, для начала необходимо дать как можно большую полосу пропускания соединениям, которые заведомо получат малую полосу пропускания. Предположим, что все источники Sn начинают передавать информацию в соответствии с алгоритмом TCP «медленный старт», т.е. скорость передачи постепенно растет. Будем повышать скорость передачи до тех пор, пока один из каналов не будет перегружен.

Очевидно, что каналом, который будет перегружен, является канал 1, через который установлены соединения S3-D3 и S4-D4. Т.е. каждому из этих двух соединений будет выделено примерно по 17 Мбит/с, и ни одно из двух соединений не сможет получить большую полосу пропускания, пока другое соединение также передает данные. Соединения S3-D3 и S4-D4 блокированы. Продолжим рассмотрение нагрузки на сети. Рассмотрим нагрузку в каждом канале:

• канал 2 используется четырьмя соединениями, причем максимальная скорость двух из них ограничена 17 Мбит/с;

• канал 3 используется четырьмя соединениями, причем максимальная скорость ни одного из них пока не ограничена;

• канал 4 используется пятью соединениями, причем максимальная скорость одного из них ограничена 17 Мбит/с.

Следующим каналом, который будет перегружен, является канал 4. Остаточная полоса пропускания канала 4, с учетом ограниченного по скорости соединения S4-D4 (17 Мбит/с), равняется 83 Мбит/с, которая, в свою очередь, делится поровну между четырьмя соединениями S2-D2, S6-D6, S7-D7 и S8-D8. Т.е. каждое из этих соединений получит примерно по 20.75 Мбит/с. Таким образом, на оставшихся неперегруженных каналах имеем:

• канал 2 используется четырьмя соединениями, причем максимальная скорость двух из них ограничена 17 Мбит/с, а еще одного 20.75 Мбит/с;

• канал 3 используется четырьмя соединениями, причем максимальная скорость гб-об, 37-07 и 38-08 ограничена 20.75 Мбит/с.

Очередным каналом, который подвергнется перегрузке, будет канал 3. Остаточная полоса пропускания канала 3, с учетом ограниченных по скорости соединений, равняется 37.75 Мбит/с, которая, в свою очередь, полностью отдается соединению Э5-05. Для рассмотрения остается только канал 2, который будет перегружен последним. Остаточная полоса пропускания канала 2, с учетом ограниченных по скорости соединений 32-02, ЭЗ-ОЗ и 34-04, равняется 45.25 Мбит/с, которая, в свою очередь, полностью отдается соединению 31-01.

Рис. 2.7. Распределение ресурсов по критерию max-min

⇐Tcp и принцип «справедливого распределения ресурсов» | Управление трафиком и качество обслужевания в сети | Критерий «взвешенный max-min»⇒