нагрузка

Большинство алгоритмов маршрутизации пытаются искать наилучшие пути для каждого адресата и направлять весь трафик по оптимальному пути.

Альтернатив­ный подход, позволяющий повысить качество обслуживания, состоит в разделе­нии трафика для одного и того же адресата между несколькими маршрутами. По­скольку маршрутизаторы обычно не следят за нагрузкой на всю сеть в целом, остается лишь один способ разделения трафика — на основе доступной локаль­ной информации. Одним из простых методов является маршрутизация, пропор­циональная или эквивалентная емкостям исходящих связей. Однако существуют и более сложные алгоритмы (Nelakuditi и Zhang, 2002).

Возможность управления трафиком — это неплохой начальный шаг в деле обес­печения гарантированного качества обслуживания. Однако на самом деле исполь­зование этих методов неявно означает, что все пакеты в потоке должны следовать по одному и тому же пути. При распределении их случайным образом между не­сколькими маршрутизаторами невозможно что-либо гарантировать. Следовательно, между источником и приемником должно быть установлено нечто вроде вир­туального канала, и все пакеты, принадлежащие данному потоку, должны следо­вать по указанному маршруту.

Раз у нас есть особый путь, по которому направляется поток, становится воз­можным резервирование ресурсов вдоль этого пути, что позволяет гаранти­ровать доступность необходимой емкости. Резервироваться могут три типа ре­сурсов:

1. Пропускная способность.
2. Буферное пространство.
3. Время центрального процессора.
   

Наиболее очевидно резервирование пропускной способности. Если потоку не­обходима скорость 1 Мбит/с, а исходящая линия может работать со скоростью 2 Мбит/с, то направить три потока с такими параметрами по этой линии не уда­стся. То есть резервирование пропускной способности означает предотвращение предоставления канала большему числу абонентов, чем канал может обработать.

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

Наконец, время центрального процесса — это еще один очень ценный ресурс. На что расходуется время работы процессора в маршрутизаторе? На обработку Пакетов. Поэтому существует предельная скорость, с которой маршрутизатор •Может обрабатывать пакеты. Необходимо быть уверенным в том, что процессор Не перегружен, — это залог своевременной обработки каждого пакета.

На первый взгляд кажется, что если на обработку пакета уходит, скажем, 1 мкс, то маршрутизатор способен управиться с миллионом пакетов за секунду. Одна­ко это предположение ошибочно, так как при доставке потока всегда есть про­межутки времени, в течение которых ничего не передается. Если центральному процессору для совершения своей работы важен каждый отдельный такт, то про­пуск нескольких тактов из-за молчания на линии приведет к накоплению невы­полненных заказов, от которых невозможно избавиться.

Однако даже если нагрузка несколько меньше теоретической емкости, все равно могут образовываться очереди и возникать задержки. Рассмотрим ситуа­цию, когда пакеты прибывают нерегулярно со средней скоростью прибытия X пакетов в секунду. Время, необходимое процессору на обработку каждого паке­та, также меняется, но в среднем составляет ц пакетов в секунду. Предположим, что как скорость прибытия, так и скорость обслуживания имеют пуассоновское распределение.

Алгоритм маршрутизации с учетом состояния линии требует от каждого мар­шрутизатора знания или хотя бы обоснованной оценки задержки для всех линий связи со своими соседями. Наиболее прямой способ определить эту задержку за­ключается в посылке по линии специального пакета ECHO, на который другая сто­рона обязана немедленно ответить. Измерив время двойного оборота этого паке­та и разделив его на два, отправитель получает приемлемую оценку задержки. Чтобы получить более точный результат, это действие можно повторить несколько раз, после чего вычислить среднее арифметическое. Конечно, такой метод пред­полагает, что задержки являются симметричными, что не всегда так.

Возникает интересный вопрос: надо ли учитывать нагрузку на линию во вре­мя измерения задержки? Чтобы учесть загруженность линии, таймер должен включаться при отправке пакета ECHO. Чтобы игнорировать загрузку, таймер сле­дует включать, когда пакет ECHO достигает начала очереди.

Оба способа могут быть аргументированы. Учет трафика в линии при изме­рении задержки означает, что когда у маршрутизатора есть выбор между двумя линиями с одинаковой пропускной способностью, маршрут по менее загружен­ной линии рассматривается как более короткий. Такой выбор приведет к более сбалансированному использованию линий связи и, следовательно, к более эф­фективной работе системы.

К сожалению, можно привести аргумент и против учета загруженности ли­нии при расчете задержек. Рассмотрим подсеть, показанную на рис. 5.10. Ока разделена на две части — восточную и западную, которые соединены двумя ли­ниями, CF и EI.

Предположим, что основная часть потока данных между востоком и западом использует линию CF. В результате эта линия оказывается сильно загруженной и с большими задержками. Учет времени стояния пакета в очередях при подсче­те кратчайшего пути сделает линию EI более привлекательной. После установки Новых таблиц маршрутизации большая часть потока данных между востоком и западом переместится на линию EI, и ситуация повторится с точностью до сме­ны одной линии на другую. Аналогично, после еще одного обновления уже ли­ния CF окажется более привлекательной. В результате таблицы маршрутизации будут страдать от незатухающих колебаний, что сильно снизит эффективность
работы системы. Если же нагрузку не учитывать, то эта проблема не возникнет. Можно поступать по-другому: распределять нагрузку между двумя линиями. Однако такое решение приведет к неполному использованию наилучшего пути. Тем не менее, во избежание колебаний системы при выборе оптимального пути, по-видимому, лучше всего распределять нагрузку между несколькими линиями, пуская определенные части трафика по каждой из них.

Начнем изучение методов борьбы с перегрузкой с систем без обратной связи. Эти системы разработаны в первую очередь для предотвращения перегрузки, а не для борьбы с уже имеющей место перегрузкой. Они пытаются достичь своей цели, используя соответствующие стратегии на разных уровнях. В табл. 5.2 показаны различные стратегии уровней передачи данных, сетевого и транспортного, спо­собные влиять на перегрузку.

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

Стратегия подтверждений также влияет на перегрузку. Если каждый пакет немедленно подтверждается получателем, то пакеты с подтверждениями образу­ют дополнительный трафик. Однако если подтверждения добираются обратно «верхом» на попутном потоке кадров, то количество трафика в сети снижается, зато увеличивается среднее время получения подтверждений, что может, в свою очередь, вызвать увеличение повторно переданных пакетов вследствие истече­ния времени ожидания подтверждений. Более жесткая схема управления пото­ком (например, с небольшим размером окна) уменьшает скорость передачи дан­ных и помогает бороться с перегрузкой.

Существует также зависимость перегрузки от того, является ли сетевой уро­вень дейтаграммным или он основан на виртуальных каналах, так как многие алго­ритмы борьбы с перегрузкой работают только в подсетях с виртуальным каналами. Политика очередей пакетов и обслуживания определяет количество очередей у каждого маршрутизатора — например, одна общая очередь для всех линий, или по очереди для каждой линии, или какой-нибудь комбинированный вариант. Она также определяет порядок обработки пакетов (например, поочередно или в порядке приоритетов). Политика игнорирования пакетов является правилом, определяющим набор пакетов, подлежащих отвержению, когда не хватает памя­ти. Хорошо продуманная стратегия может облегчить симптомы перегрузки, то­гда как неудачная политика может даже ухудшить ситуацию.

Хороший алгоритм выбора маршрута может помочь избежать локальной пе­регрузки, перераспределяя трафик по всем линиям, тогда как неудачный алго­ритм может направить слишком большое количество пакетов по одной линии и вызвать затор. Наконец, управление временем жизни пакетов, определяет, как Долго пакет может перемещаться по сети, прежде чем он будет проигнорирован очередным маршрутизатором. Если это время слишком велико, то потерянные пакеты могут засорять собою сеть, однако если время жизни пакета слишком ма­ло, то пакеты не будут успевать достичь адресата, что приведет к необходимости повторных передач.

На транспортном уровне применяются те же стратегии, что и на уровне переда­чи данных, но к ним добавляется еще и проблема определения времени ожидания подтверждения, что на транспортном уровне осуществить значительно сложнее, Воскольку время пересечения всей сети предсказать значительно сложнее, чем время передачи пакета от какого-либо маршрутизатора до его соседа. Если этот Интервал слишком короток, будут высылаться излишние повторные пакеты,
а если слишком велик — перегрузка снизится, но увеличится задержка в случае потери пакета.

Хорошо известно, что при борьбе с перегрузкой гораздо проще вовремя обнару­жить затор, чем дать ему развиться до критических размеров, а потом думать, что делать в сложившейся ситуации. Это соображение приводит к идее отвержения некоторых пакетов еще до того, как все буферное пространство будет заполнено скопившимися необработанными данными. Популярный алгоритм, реализующий данную идею, называется случайным ранним обнаружением (RED — Random Ear­ly Detection, Floyd и Jacobson, 1993). Некоторые транспортные протоколы (вклю­чая TCP) на потерю своих пакетов отвечают снижением трафика от источника, чего мы, в сущности, и добиваемся. Обоснование такой логики состоит в том, что TCP предназначен для проводных сетей, которые по сути своей являются очень надежными, и потеря пакетов в них чаще всего сигнализирует о переполнении буфера, а не об ошибках передачи. Этот факт и используется для уменьшения пе­регрузок.

Если заставить маршрутизаторы сознательно терять пакеты еще до того как ситуация станет безнадежной (именно такой момент зашифрован в слове «ран­нее» из названия подхода), то останется время на то, чтобы предпринять какие- то действия. Для определения условий, при которых следует начинать терять па­кеты, маршрутизаторы постоянно высчитывают скользящее среднее длин своих очередей. Когда средняя длина очереди на какой-либо линии превышает порого­вое значение, эта линия объявляется перегруженной и выполняются действия по предотвращению затора.

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

Но как маршрутизатор сообщит источнику о возникшей проблеме? Можно послать ему сдерживающий пакет, как описывалось ранее. Но это приведет к соз­данию дополнительной нагрузки на и так уже почти перегруженную сеть. Дру­гой подход заключается в том, чтобы просто потерять выбранный пакет и нико­му не сообщать об этом. Источник в конечном счете среагирует на отсутствие подтверждения. Поскольку он знает, что потеря пакетов обычно связана с пере­грузкой сети, он уменьшит скорость выдачи пакетов и не станет пытаться во что бы то ни стало пробиться к загруженному маршрутизатору. Такая неявная фор­ма обратной связи может применяться только тогда, когда источник знает, что на потерю пакетов надо реагировать снижением скорости передачи. В беспро­водных сетях, где большинство испорченных и потерянных пакетов обязано сво­им исчезновением шуму в эфире, такой подход не годится.

При больших скоростях передачи данных и при сильной удаленности хостов с отправкой сдерживающих пакетов возникают проблемы, поскольку реакция на них оказывается крайне запоздалой.

Рассмотрим, к примеру, хост в Сан-Франци­ско (маршрутизатор А на рис. 5.25), посылающий поток данных на хост, располо­женный в Нью-Йорке (маршутизатор D на рис. 5.25), со скоростью 155 Мбит/с. Если у нью-йоркского хоста станет кончаться буферная память, сдерживающему пакету потребуется около 30 мс на то, чтобы добраться обратно в Сан-Франциско и сообщить о том, что необходимо снизить объем трафика. Распространение сдер­живающего пакета схематично показано на второй, третьей и четвертой диаграм­мах рис. 5.25, а. За те 30 мс, пока этот пакет движется по сети, в сторону нью- йоркского маршрутизатора передается еще 4,6 Мбит данных, с которыми тоже надо как-то совладать. Только к седьмой диаграмме (рис. 5.25, а) маршрутизатор заметит начавшееся снижение потока.

Однако есть альтернативный метод, позволяющий бороться с этой пробле­мой. Он заключается в том, что сдерживающий пакет влияет на трафик каждого маршрутизатора, через который он проходит. Это показано на последовательно­сти диаграмм на рис. 5.25, б. Как только сдерживающий пакет достигает точки F, поток данных от F в сторону D должен быть уменьшен. Таким образом, F резер­вирует для потока большее количество буферной памяти: источник все еще про­должает заваливать это направление своими данными. Нагрузка на D мгновенно спадает, как головная боль у страдальца, рекламирующего по телевизору чудо­действенные пилюли.

На следующем шаге сдерживающий пакет, продолжая свой путь, достигает Е и приказывает уменьшить поток в сторону F. В результате в течение какого-то времени точке Е приходится выдерживать повышенную на­грузку, но зато мгновенно освобождается от своего бремени точка F. Наконец, победный марш сдерживающего пакета приводит его к источнику всех бед — точке А, и теперь поток снижается на самом деле.

Результатом применения метода сдерживания трафика на ретрансляционных Участках является максимально быстрое устранение перегрузки в самой горячей точке за счет использования большего объема буферной памяти промежуточных маршрутизаторов. Таким образом, перегрузка пресекается без потери пакетов. Эта идея обсуждается более подробно у (Mishra и Kanakia, 1992).