Эндрю Уэзеролл - Компьютерные сети. 5-е издание

Наиболее простой способ — сделать весовой коэффициент связи функцией от (фиксированной) пропускной способности связи и задержки распространения, а также (переменной) измеренной нагрузки или среднего времени ожидания в очереди. В результате пути с наименьшим весом будут при прочих равных параметрах наименее нагруженными.

Маршрутизация с учетом состояния трафика использовалась на ранних этапах развития сети Интернет в рамках этой модели (Khanna и Zinky, 1989). Однако здесь есть небольшая опасность. Рассмотрим сеть, изображенную на рис. 5.21. Она разделена на две части — Восток и Запад, соединенные связями CF и EI. Предположим, что основной трафик между Западом и Востоком проходит по связи CF, в результате чего эта линия оказывается слишком нагруженной, что приводит к длительным задержкам. Учет времени ожидания в очереди при вычислении кратчайшего пути сделает связь EI более популярной. После внесения изменений в таблицы маршрутизации большинство трафика пойдет по связи EI, и она окажется слишком нагруженной. Поэтому при следующем обновлении таблиц кратчайшим путем снова станет CF. В конечном итоге значения в таблицах маршрутизации будут сильно колебаться, что приведет к ошибкам при выборе маршрутов и другим проблемам.

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

Если оставить в стороне нагрузку и учитывать только пропускную способность и задержку распространения, такая проблема не возникает. Попытки учесть нагрузку, используя узкий диапазон весовых значений, лишь замедляют колебания маршрутов. Удачное решение проблемы основывается на двух методах. Первый — это многопутевая маршрутизация, при которой между отправителем и получателем может существовать несколько путей. Применительно к нашему примеру это означает, что пакеты могут передаваться по обеим связям между Востоком и Западом. Второй метод состоит в следующем: схема маршрутизации должна перемещать трафик по маршрутам настолько медленно, чтобы она сходилась (так, например, работает схема Gallagher, 1977).

Из-за всех этих трудностей протоколы маршрутизации сети Интернет обычно не строят маршруты на основании нагрузки на сеть. Вместо этого перегрузки регулируются вне протокола маршрутизации за счет изменения входных данных. Это называется управлением трафиком( traffic engineering).

5.3.3. Управление доступом

Широко применяемым методом недопущения перегрузки в сетях виртуальных каналов является управление доступом. Идея этого метода проста: не нужно создавать новый виртуальный канал до тех пор, пока сеть не сможет обработать дополнительный трафик без перегрузки. То есть любые попытки добавить виртуальный канал могут закончиться неудачно. Это лучшее решение, поскольку если пустить в сеть, которая в данный момент занята, дополнительных пользователей, то ситуация только ухудшится. Аналогичная ситуация происходит в телефонных системах: когда коммутатор оказывается перегруженным, вы поднимаете трубку и не слышите гудка.

Преимущество этого подхода оказывается существенным в случае, если добавление нового виртуального канала приведет к перегрузке. В телефонных сетях эта задача решается просто благодаря фиксированной пропускной способности для вызовов (64 Кбит/с для несжатого аудио). Но в компьютерных сетях используются виртуальные каналы всевозможных типов. Поэтому если мы хотим прибегнуть к управлению доступом, каналы должны включать в себя определенные характеристики трафика.

Часто в качестве характеристик трафика выступают скорость и форма. Однако вопрос о том, как просто и осмысленно описать эти характеристики, достаточно трудный: трафик обычно неравномерен, и поэтому средняя скорость не является особенно показательной. Например, обеспечить поиск в Сети гораздо сложнее, чем просмотр потокового видео такого же объема, поскольку блоки трафика с большей вероятностью приводят к перегрузке маршрутизаторов сети. Этот эффект чаще всего называют дырявым ведром (leaky bucket) или маркерным ведром (token buket). Дырявое ведро использует два параметра, ограничивающих среднюю скорость и мгновенный выброс трафика. Алгоритм дырявого ведра широко используется для улучшения качества обслуживания, поэтому мы поговорим о нем более подробно в разделе 5.4.

Вооружившись характеристиками трафика, сеть принимает решение о добавлении нового виртуального канала. Чтобы перегрузка не произошла, сеть может, например, зарезервировать часть пропускной способности путей для каждого из виртуальных каналов. В таком случае характеристика трафика выступает в качестве договора об обслуживании, которое сеть обязуется предоставить пользователю. Мы предотвратили перегрузку, но слишком рано отклонились в сторону смежной темы качества обслуживания; к ней мы вернемся в следующем разделе.

Даже если сеть не берет на себя никаких обязательств, она может использовать характеристики трафика для управления доступом. В таком случае задача сводится к тому, чтобы оценить число виртуальных каналов, достаточное для обеспечения нужной пропускной способности сети и работы без перегрузок. Предположим, что все виртуальные каналы, способные передавать трафик со скоростью до 10 Мбит/с, используют один и тот же физический канал с пропускной способностью 100 Мбит/с. Сколько каналов можно использовать? Очевидно, что в случае 10 каналов нет никакого риска перегрузки, однако в нормальной ситуации это неэффективно, поскольку вряд ли все 10 каналов будут одновременно работать в полную силу. В действующих сетях для оценки числа возможных каналов используются статистические данные. Таким образом, за счет допустимого увеличения риска сеть выигрывает в производительности.

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

Предположим, что хост, соединенный с маршрутизатором A, хочет установить соединение с хостом, соединенным с маршрутизатором B. В нормальных условиях это соединение прошло бы через один из перегруженных маршрутизаторов. Чтобы этого избежать, сеть усекается, как показано на рис. 5.22, б. При этом из нее удаляются перегруженные маршрутизаторы и все их линии связи. Пунктирной линией показан

возможный маршрут виртуального канала в обход перегруженных маршрутизаторов. Подробное описание маршрутизации, чувствительной к нагрузке, можно найти в работе (Shaikh и др., 1999).