text

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

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

В подсети, состоящей из п маршрутизаторов, у каждого из которых k соседей, количество памяти, необходимой для хранения входной информации, пропор­ционально kn. Кроме того, может потребоваться много времени на обработку ин­формации. В больших подсетях это может составлять проблему. Тем не менее, во многих практических ситуациях маршрутизация с учетом состояния линий работает вполне удовлетворительно.

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

Маршрутизация с учетом состояния линий широко применяется в современ­ных сетях, поэтому следует сказать несколько слов о некоторых примерах прото­колов, использующих данный алгоритм. Одним из таких протоколов является протокол OSPF, все чаще применяемый в Интернете, о котором будет рассказа­но в разделе «Протокол внутреннего шлюза OSPF».

Другим важным протоколом с учетом состояния линий является IS-IS (Intermediate System to Intermediate System — связь между промежуточными сис­темами) — протокол, разработанный для сети DECnet и принятый впоследствии Международной организацией по стандартизации ISO для использования вме­сте с протоколом сетевого уровня CLNP, не требующим соединений. С тех пор он был модифицирован для поддержки также и других протоколов, в частности IP. Протокол IS-IS используется в некоторых магистралях сети Интернет (включая старую магистраль NSFNET) и в некоторых цифровых сотовых системах, напри­мер, в CDPD. В сети Novell NetWare применяется разновидность протокола IS­IS (NLSP) для маршрутизации IPX-пакетов.

В основе работы протокола IS-IS лежит распространение картины топологии маршрутизаторов, по которой рассчитываются кратчайшие пути. Каждый мар­шрутизатор сообщает в информации о состоянии линий доступные ему напря­мую адреса сетевого уровня. Эти адреса могут быть адресами IP, IPX, AppleTalk или другими. Протокол IS-IS может даже осуществлять одновременную поддерж­ку нескольких протоколов сетевого уровня.

Многие новшества, разработанные для протокола IS-IS, были приняты несколь­ко лет спустя при разработке протокола OSPF. К ним относятся метод саморегу­ляции лавинного потока обновлений информации о состоянии линий, концеп­ция выделенного маршрутизатора в локальной сети, а также метод вычисления и поддержки расщепления пути и умножения метрик. Соответственно, между про­токолами IS-IS и OSPF нет почти никакой разницы. Наиболее существенное различие между ними заключается в том, что способ кодирования в протоколе IS-IS, в отличие от OSPF, облегчает одновременную поддержку нескольких се­тевых протоколов. Это свойство особенно важно в больших многопротокольных средах.

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

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

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

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

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

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

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

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

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

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

Поскольку узлы могут перемещаться и выключаться, топология сети может из­меняться совершенно спонтанно. Например, если на рис. 5.18 узел G выключит­ся, А не поймет, что путь к I (ADGI) больше не может быть реализован. Алгорит­му нужно как-то с этим бороться. Периодически все узлы рассылают сообщение приветствия Hello. Ожидается, что все узлы, будучи истинными джентльменами, ответят на него. Если ответ не приходит, значит, сосед вышел из зоны действия и больше не связан с данным узлом. Аналогичным образом, если он пытается по­слать пакет соседу, который не отвечает, он узнает, что связь с ним недоступна.

Эта информация используется для удаления нерабочих путей. Для каждого из возможных адресатов каждый узел Охранит историю о том, какие соседи снаб­жали узел пакетами для данных адресатов в течение последних ДГ секунд. Такие соседи называются активными соседями узла N для данного адресата. Узел N осуществляет сбор подобных сведений с помощью таблицы маршрутизации, ко­торая, как известно, в качестве индекса использует адрес назначения. В этой таб­лице указан тот узел, на который нужно переслать пакет, чтобы он мог дойти до адресата. Кроме того, в ней имеются сведения об оставшемся числе переходов, последнем порядковом номере получателя, а также об активных соседях данного адресата. Вид возможной таблицы маршрутизации для узла D при топологии, рассматриваемой в нашем примере, показан на рис. 5.21, а.

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

Рассмотрим наш предыдущий пример, предположив, что G внезапно вык­лючился. Образовавшаяся в результате этого события топология показана на рис. 5.21, б. Когда D обнаруживает, что G ушел из сети, он просматривает свою таблицу маршрутизации и видит, что G стоял на пути к Е, G и I. Объединением активных соседей для данных адресатов является множество {А, В}. Другими словами, А и В содержат записи о маршрутах, проходящих через G, поэтому их нужно проинформировать о том, что эти маршруты больше не работают. D сооб­щает им об этом, посылая специальные пакеты, заставляющие их обновить свои таблицы соответствующим образом. Сам узел D удаляет записи для адресатов Е, G и / из таблицы маршрутизации.

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

AODV, впрочем, может также заниматься широковещательной и групповой маршрутизацией. Детали см. в (Perkins and Royer, 2001). Маршрутизация в спе­циализированных сетях — чрезвычайно популярная сегодня область исследова­ний. Вопросам, связанным с ней, посвящено большое количество материалов. Например, (Chen и др., 2002; Ни and Johnson, 2001; Li и др., 2001; Raju and Garcia-Luna-Aceves, 2001; Ramanathan and Redi, 2002; Royer and Toh, 1999; Spohn and Garcia-Luna-Aceves, 2001; Tseng и др., 2001; Zadeh и др., 2002).

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

Маршрутизатор, заваленный пакетами, может -выбирать пакеты просто слу­чайным образом, но обычно имеются более оптимальные варианты. Выбор пакета, который будет отвергнут, может зависеть от приложения, пересылающего этот пакет. Для передачи файла более старый пакет ценится выше нового, так как от­вержение пакета номер б и сохранение пакетов с номерами с 7-го по 10-й может привести к тому, что получатель запросит еще раз пакеты с 6-го по 10-й (если полу­чатель просто отвергает все пакеты, приходящие не в том порядке). В файле, со­стоящем из 12 пакетов, выбрасывание 6-го пакета может потребовать повторной передачи пакетов с 7-го по 12-й, тогда как выбрасывание пакета номер 10 может потребовать повторной передачи только пакетов с 10-го по 12-й. Для мультиме­дийных приложений, напротив, новый пакет важнее старого. Первую стратегию (старое лучше нового) часто называют винной стратегией, а вторую (новое луч­ше старого) — молочной стратегией.

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

Для реализации интеллектуальной стратегии выбрасывания части информа­ции приложения должны помечать свои пакеты классами приоритетов, соответ­ствующими их важности. В этом случае маршрутизаторы смогут сначала выбросить пакеты нижнего класса, затем следующего за ним и т. д. Конечно, при отсутствии стимула все будут помечать свои пакеты не иначе как ОЧЕНЬ ВАЖНО — НИ В КОЕМ СЛУЧАЕ НЕ ВЫБРАСЫВАТЬ.

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

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

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

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

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

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

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

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

Пример работы алгоритма продвижения по встречному пути показан на рис. 5.14. Слева изображена подсеть, посередине —входное дерево для маршру­тизатора I этой подсети. На первом транзитном участке маршрутизатор I посы­лает пакеты маршрутизаторам F, Н, J и N, являющимся вторым ярусом дерева. Все эти пакеты прибывают к I по предпочитаемым линиям (по пути, совпадаю­щему с входным деревом), что обозначается кружками вокруг символов на рис. 5.14, в. На втором этапе пересылки формируются восемь пакетов — по два каждым маршрутизатором, получившим пакет после первой пересылки. Все во­семь пакетов попадают к маршрутизаторам, не получавшим ранее пакетов, а пять из них приходят по предпочитаемым линиям. Из шести пакетов, формируемых на третьем транзитном участке, только три прибывают по предпочитаемым ли­ниям (на маршрутизаторы С, Е и К). Остальные оказываются дубликатами.

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

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

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

Один из способов моделирования локальной сети состоит в том, что ЛВС рас­сматривается в виде узла графа, как и маршрутизаторы. Это показано на рис. 5.9, б. На рисунке сеть изображена в виде искусственного узла N, с которым соединены маршрутизаторы А, С и F. Возможность передачи пакетов от Л к С по локальной сети отражается здесь наличием пути ANC.