Рис. 5.20. Временные шкалы подходов к борьбе с перегрузкой
Самый простой способ избежать перегрузки — построить такую сеть, которая лучше всего соответствует передаваемому по ней трафику. Если часть пути, по которому обычно пересылаются большие объемы данных, обладает низкой пропускной способностью, возникновение перегрузки очень вероятно. Иногда при возникновении перегрузки возможно динамическое добавление ресурсов, например подключение свободных маршрутизаторов или резервных линий (обеспечивающих отказоустойчивость системы), или же приобретение дополнительной пропускной способности на свободном рынке. Как правило, наиболее загруженные связи и маршрутизаторы обновляются при первой возможности. Этот процесс называется обеспечением (provisioning) и использует временную шкалу месяцев, основываясь на долгосрочных данных о динамике трафика.
Чтобы максимально эффективно использовать пропускную способность сети, маршруты могут строиться в соответствии со специальными схемами трафика, которые меняются в течение суток по мере того, как пользователи просыпаются и ложатся спать в различных временных зонах. Можно, например, отвести трафик от загруженных линий, изменив весовые коэффициенты кратчайшего пути. Некоторые радиостанции используют вертолеты, чтобы получить сведения о перегрузках на дорогах и передать их радиослушателям, которые благодаря этому смогут объехать «горячие точки». Это называется маршрутизацией с учетом состояния трафика (traffic-aware routing). В таком случае полезно также разделять трафик, направляя его по разным линиям.
Но иногда увеличение пропускной способности оказывается невозможным. Тогда единственным средством борьбы с перегрузкой является снижение нагрузки. В сети виртуальных каналов новые соединения могут быть отклонены, если они приведут к перегрузке сети. Это называется управлением доступом (admission control).
Возможен и более сложный вариант: когда перегрузка неизбежна, сеть может послать сообщение обратной связи тому отправителю, чей трафик вызывает проблему. Сеть может попросить отправителя уменьшить трафик или же сделать это сама.
Этот подход (регулирование трафика — traffic throttling) требует ответа на два вопроса: как обнаружить зарождающуюся перегрузку и как сообщить об этом отправителю, который должен замедлить трафик. Решить первую проблему можно, если маршрутизаторы будут следить за средней нагрузкой на сеть, временем ожидания в очереди и числом утерянных пакетов. В любом случае увеличение значений параметров сигнализирует о приближении к перегрузке.
Для решения второй проблемы необходимо, чтобы маршрутизаторы входили в петлю обратной связи с отправителями. Чтобы данная схема работала, необходимо тщательно настроить временные параметры. Если каждый раз, когда два пакета приходят одновременно, какой-нибудь нервный маршрутизатор будет кричать «Стоп!», а простояв без работы 20 мкс, он же будет давать команду «Давай!», система будет находиться в состоянии постоянных незатухающих колебаний. С другой стороны, если маршрутизатор для большей надежности станет ждать 30 минут, прежде чем что-либо сообщить, то механизм борьбы с перегрузкой будет реагировать слишком медленно, чтобы приносить вообще какую-либо пользу. Своевременная доставка сообщений обратной связи — не такая уж простая задача. Кроме того, необходимо добиться того, чтобы маршрутизаторы отправляли больше сообщений, если сеть уже перегружена.
Наконец, если все остальные методы не работают, сеть вынуждена удалить пакеты, которые она не может доставить. Для этого используется общий термин сброс нагрузки (load shedding). Если правильно выбрать удаляемые пакеты, можно предотвратить затор.
5.3.2. Маршрутизация с учетом состояния трафика
Первый подход, который мы рассмотрим, называется маршрутизацией с учетом состояния трафика. Схемы, рассмотренные нами в разделе 5.2, используют фиксированные весовые коэффициенты связей. Эти схемы могут адаптироваться к изменению топологии, но не к изменению нагрузки. Причина, по которой при вычислении маршрутов нагрузку следует принимать во внимание, состоит в том, что благодаря этому можно будет отвести поток трафика от «горячих точек», в которых в первую очередь возникает перегрузка.
Наиболее простой способ — сделать весовой коэффициент связи функцией от (фиксированной) пропускной способности связи и задержки распространения, а также (переменной) измеренной нагрузки или среднего времени ожидания в очереди. В результате пути с наименьшим весом будут при прочих равных параметрах наименее нагруженными.
Маршрутизация с учетом состояния трафика использовалась на ранних этапах развития сети Интернет в рамках этой модели (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.
