Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
ОТВЕТЫ НА КОНТР,РАБ, ПО ВЫЧИСЛ-НОЙ МАШИНЕ.docx
Скачиваний:
0
Добавлен:
01.07.2025
Размер:
618 Кб
Скачать
☆

5.2.5. Маршрутизация с учетом состояния линий

Маршрутизация на основе векторов расстояний использовалась в сети ARPANET вплоть до 1979 года, когда ее сменил алгоритм маршрутизации с учетом состояния линий. Отказаться от прежнего алгоритма пришлось в первую очередь потому, что при изменении топологии сети алгоритм слишком долго приходил к устойчивому состоянию (вследствие проблемы счета до бесконечности). В результате он был заменен на совершенно новый алгоритм, ныне называемый маршрутизацией с учетом состояния линий (link state routing). Сейчас в крупных сетях и сети Интернет используются его варианты — алгоритмы маршрутизацииIS-ISи OSPF.

Воснове алгоритма лежит относительно простая идея, ее можно изложить впяти требованиях к маршрутизатору. Каждый маршрутизатор должен:

1)обнаруживать своих соседей и узнавать их сетевые адреса;

2)задавать метрику расстояния или стоимости связи с каждым из своих соседей;

3)создавать пакет, содержащий всю собранную информацию;

4)посылать этот пакет всем маршрутизаторам и принять все пакеты, отправленные другими маршрутизаторами;

5)вычислять кратчайший путь ко всем маршрутизаторам.

Врезультате каждому маршрутизатору высылается полная топология. После этого для обнаружения кратчайшего пути ко всем остальным маршрутизаторам каждый маршрутизатор может использовать алгоритм Дейкстры. Ниже мы рассмотрим каждый из этих пяти этапов более подробно.

Знакомство с соседями

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

404 Глава 5. Сетевой уровень

что три маршрутизатора являются соседями маршрутизатора F, то не должно возникать разночтений по поводу того, один и тот же маршрутизаторF имеется в виду или нет.

Когда два или более маршрутизаторов соединены с помощью широковещательной связи (например, коммутатора, кольцевой сети или классической сети Ethernet), си- туация несколько усложняется. На рис. 5.9,аизображена широковещательная ЛВС, к которой напрямую подключены три маршрутизатора:A,C иF. Каждый из них, как показано на рисунке, соединен также с одним или несколькими дополнительными маршрутизаторами.

Рис. 5.9. Широковещательная ЛВС:а — девять маршрутизаторов и широковещательная локальная сеть;б — графовая модель той же системы

Широковещательная ЛВС обеспечивает связь между каждой парой подключенных маршрутизаторов. Однако моделирование такой сети в виде системы связей «точкаточка» существенно увеличивает размер топологии и приводит к нерациональной передаче сообщений. Более подходящий способ моделирования локальной сети состоит в том, что ЛВС рассматривается в виде узла графа, как и маршрутизаторы. Это показано на рис. 5.9, б. На рисунке сеть изображена в виде искусственного узлаN, с которым соединены маршрутизаторыA,C иF. Для исполнения ролиN в протоколе маршрутизации выбирается один из маршрутизаторов сети, который называетсяотмеченным маршрутизатором (designated router). Возможность передачи пакетов отA кC по локальной сети отражается здесь наличием путиANC.

Задание стоимости связи

Алгоритм маршрутизации с учетом состояния линии требует, чтобы каждая связь обладала метрикой расстояния или стоимости, необходимой для вычисления кратчайшего пути. Стоимость пути до соседних маршрутизаторов может быть задана автоматически или определена оператором сети. Чаще всего стоимость обратно пропорциональна пропускной способности связи. Так, сеть Ethernet со скоростью 1 Гбит/с

может иметь стоимость 1, а Ethernet со скоростью 100 Мбит/с — стоимость 10. Бла-

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

5.2. Алгоритмы маршрутизации 405

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

Создание пакетов состояния линий

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

Рис. 5.10. Сеть (а); пакеты состояния линий для этой сети (б)

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

406 Глава 5. Сетевой уровень

Распространение пакетов состояния линий

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

Сначала мы опишем основной алгоритм распространения. Затем расскажем о некоторых улучшениях. Основная идея алгоритма отправки пакетов состояния линии на все маршрутизаторы состоит в использовании алгоритма заливки. Чтобы держать этот процесс под контролем, в каждый пакет помещают порядковый номер, увеличивающийся на единицу для каждого следующего пакета. Маршрутизаторы записывают все пары (источник, порядковый номер), которые им попадаются. Когда приходит новый пакет состояния линий, маршрутизатор ищет адрес его отправителя и порядковый номер пакета в своем списке. Если это новый пакет, он рассылается дальше по всем линиям, кроме той, по которой он пришел. Если же это дубликат, он удаляется. Если порядковый номер прибывшего пакета меньше, чем номер уже полученного пакета от того же отправителя, то такой пакет также удаляется как устаревший, поскольку очевидно, что у маршрутизатора есть более свежие данные.

С этим алгоритмом связано несколько проблем, но с ними можно справиться. Вопервых, если последовательный номер, достигнув максимально возможного значения числа, обнулится, возникнет путаница. Решение состоит в использовании32-битныхпорядковых номеров. Даже если рассылать каждую секунду по пакету, то для переполнения4-байтовогоцелого числа понадобится 137 лет.

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

В-третьих,может произойти искажение порядкового номера — например, вместо номера 4 будет принято число 65 540 (ошибка в одном бите); в этом случае пакеты с5-гопо 65540-йбудут игнорироваться некоторыми маршрутизаторами как устаревшие.

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

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

5.2. Алгоритмы маршрутизации 407

рый пакет удаляется. Если номера одинаковые, то удаляется дубликат. Для защиты от ошибок на линиях связи получение всех пакетов состояния линий подтверждается. Структура данных, используемая маршрутизатором B для работы с сетью, изображенной на рис. 5.10,а, показана на рис. 5.11. Каждая строка здесь соответствует недавно полученному, но еще не полностью обработанному пакету состояния линий. В таблице записываются адрес отправителя, порядковый номер, возраст и данные. Кроме того, в таблице содержатся флаги рассылки и подтверждений для каждой из трех линий маршрутизатораB (кA,C иF, соответственно). Флаги отсылки означают, что этот пакет следует отослать по соответствующей связи. Флаги подтверждений означают, что нужно подтвердить получение этого пакета по данной линии.

Рис. 5.11. Буфер пакетов маршрутизатора B c рисунка 5.10

Как видно из рис. 5.11, пакет состояния линий от маршрутизатора A пришел напрямую, поэтому он должен быть отправлен маршрутизаторамC иF, а подтверждение о его получении следует направить маршрутизаторуA, что и показывают флаговые биты. Аналогично, пакет отF следует переслать маршрутизаторамA иC, аF отослать подтверждение.

Однако ситуация с третьим пакетом, полученным от маршрутизатора E, отличается. Он приходит дважды, по линиямEAB иEFB. Следовательно, его нужно отослать толькоC, но подтверждения необходимо выслать иA иF, как указывают биты.

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

Вычисление новых маршрутов

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

408 Глава 5. Сетевой уровень

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

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

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

стояния линий IS-IS(Intermediate System to Intermediate System— связь между промежуточными системами) (Oran, 1990). Он был разработан достаточно давно для сети DECnet и был впоследствии принят Международной организацией по стандартизации ISO для использования вместе с протоколами OSI. После этого он был модифицирован для поддержки также и других протоколов, в частности, IP. Еще один из наиболее известных протоколов маршрутизации с учетом состояния линий — OSPF

(Open Shortest Path First— открытый алгоритм предпочтительного выбора кратчай-

шего маршрута). Он был разработан Специальной комиссиейинтернет-разработок(IETF) через несколько лет послеIS-ISи включал многие новшества, применявшиеся при созданииIS-IS.К этим новшествам относятся метод саморегуляции лавинного потока обновлений информации о состоянии линий, концепция отмеченного маршрутизатора в локальной сети, а также метод вычисления и поддержки расщепления пути

иумножения метрик. Соответственно, между протоколами IS-ISи OSPF нет почти никакой разницы. Наиболее существенное различие между ними заключается в том, что вIS-ISвозможна одновременная поддержка нескольких протоколов сетевого уровня (например, IP, IPX и AppleTalk). OSPF не обладает таким свойством, и это оказывается преимуществом в больших многопротокольных средах. Более подробно о протоколе OSPF будет рассказано в разделе 5.6.6.

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

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

Иерархическая маршрутизация

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

При использовании иерархической маршрутизации маршрутизаторы разбиваются на отдельные так называемые регионы (regions). Каждый маршрутизатор знает все детали выбора маршрутов в пределах своей области, но ему ничего не известно о внутреннем строении других регионов. При объединении нескольких сетей естественно рассматривать их как отдельные регионы, при этом маршрутизаторы одной сети освобождаются от необходимости знать топологию других сетей.

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

вгруппы и т. д., пока у нас не иссякнет фантазия на названия для новых образований. В качестве примера многоуровневой иерархии рассмотрим маршрутизацию пакета, пересылаемого из университета Беркли (Berkeley), штат Калифорния в Малинди (Malindi) в Кении. Маршрутизатор в Беркли знает детали топологии в пределах Калифорнии, но трафик, направляющийся за пределы штата, он посылает маршрутизатору

вЛос-Анджелесе.Маршрутизатор вЛос-Анджелесеможет выбрать прямой маршрут для трафика в пределах США, но все пакеты, направляемые за рубеж, переправляет

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

впределах Кении, пакет попадет в Малинди.

На рис. 5.12 приведен количественный пример маршрутизации в двухуровневой иерархии с пятью регионами. Полная таблица маршрутизатора 1A, как показано на рис. 5.12,б, состоит из 17 записей. При использовании иерархической маршрутизации, как показано на рис. 5.12,в, таблица, как и прежде, содержит сведения обо всех локальных маршрутизаторах, но записи обо всех остальных регионах концентрируются в пределах одного маршрутизатора, поэтому трафик во второй регионпо-прежнемупойдет по линии1B-2A,а во все остальные регионы — по линии1C-3B.При иерархической маршрутизации размер таблицы маршрутов уменьшается с 17 до 7 строк. Чем крупнее выбираются регионы, тем больше экономится места в таблице.

410 Глава 5. Сетевой уровень

Рис. 5.12. Иерархическая маршрутизация

К сожалению, этот выигрыш памяти не достается бесплатно. Платой является увеличение длины пути. Например, наилучший маршрут от 1A до5C проходит через регион 2, однако при использовании иерархической маршрутизации весь трафик в регион 5 направляется через регион 3, поскольку так лучше для большинства адресатов в регионе 5.

Когда единая сеть становится очень большой, возникает интересный вопрос: сколько уровней должна иметь иерархия? Для примера рассмотрим сеть с 720 маршрутизаторами. Если иерархии нет, то каждому маршрутизатору необходимо поддерживать таблицу из 720 строк. Если сеть разбить на 24 региона по 30 маршрутизаторов

вкаждом регионе, тогда каждому маршрутизатору потребуется 30 локальных записей плюс 23 записи об удаленных регионах, итого 53 записи. При выборе трехуровневой иерархии, состоящей из 8 кластеров по 9 регионов из 10 маршрутизаторов, каждому маршрутизатору понадобится 10 строк в таблице для локальных маршрутизаторов, 8 строк для маршрутизации в другие регионы в пределах своего кластера, плюс 7 строк для удаленных кластеров, итого 25 строк. Камоун (Kamoun) и Кляйнрок (Kleinrock)

в1979 году показали, что оптимальное количество уровней иерархии для сети, состоящей из N маршрутизаторов, равно lnN. При этом потребуетсяe lnN записей для каждого маршрутизатора. Они также показали, что увеличение длины эффективного среднего пути, вызываемое иерархической маршрутизацией, довольно мало и обычно является приемлемым.

5.2. Алгоритмы маршрутизации 411

5.2.7. Широковещательная маршрутизация

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

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

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

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

Идея продвижения по встречному пути(reverse path forwarding) замечательно проста и изящна (Dadal, Metcalfe, 1978). Когда прибывает широковещательный пакет, маршрутизатор проверяет, используется ли та связь, по которой он прибыл, для нормальной передачи пакетов источнику широковещания. В случае положительного от-

412 Глава 5. Сетевой уровень

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

Рис. 5.13. Продвижение по встречному пути:а — сеть;б — входное дерево;в— дерево, построенное методом продвижения по встречному пути

Пример работы алгоритма продвижения по встречному пути показан на рис. 5.13. Слева изображена сеть, посередине — входное дерево для маршрутизатора I этой сети. На первом транзитном участке маршрутизаторI посылает пакеты маршрутизаторамF,H,JиN, являющимся вторым ярусом дерева. Все эти пакеты прибывают к ним по предпочитаемым линиям доI (по пути, совпадающему с входным деревом), что обозначается кружками вокруг символов на рис. 5.13,в. На втором этапе пересылки формируются восемь пакетов — по два каждым маршрутизатором, получившим пакет после первой пересылки. Все восемь пакетов попадают к маршрутизаторам, не получавшим ранее пакетов, а пять из них приходят по предпочитаемым линиям. Из шести пакетов, формируемых на третьем транзитном участке, только три прибывают по предпочитаемым линиям (на маршрутизаторыC,E иK). Остальные оказываются дубликатами. После пяти транзитных участков широковещание заканчивается с общим количеством переданных пакетов, равным 23, тогда как при использовании входного дерева потребовалось бы 4 транзитных участка и 14 пакетов.

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

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

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

5.2.8. Многоадресная рассылка

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

Передача сообщения членам такой группы называется многоадресной рассылкой(multicasting), а использующийся при этом алгоритм —многоадресной маршрутизацией(multicast routing). Любая схема многоадресной рассылки предполагает возможность создания и удаления групп и определения списка маршрутизаторов, являющихся членами данной группы. Реализация данных задач, однако, не интересует алгоритм маршрутизации. Пока мы будем считать, что каждая группа определяется адресом рассылки и что каждый маршрутизатор знает, в какие группы он входит. Мы вернемся к вопросу принадлежности к группам, когда будем говорить о сетевом уровне Интернета в разделе 5.6. Схемы многоадресной рассылки основываются на принципах широковещательной маршрутизации, о которой мы уже говорили: пакеты, предназначенные членам группы, пересылаются по связующему дереву, и при этом ставится задача эффективного использования пропускной способности сети. Однако выбор наилучшего связующего дерева зависит от того, является ли группа плотной (когда получатели занимают большую часть всей сети) или разреженной (когда большая часть сети не принадлежит группе). В этом разделе мы рассмотрим оба случая.

Если группа является плотной, применение широковещания является неплохой идеей, поскольку в результате пакет будет успешно отправлен во все части сети. Однако минус этого алгоритма в том, что пакет получат и те маршрутизаторы, которые не являются членами группы. Решение, предложенное Дирингом и Черитоном (Deering, Cheriton, 1990), состоит в том, чтобы удалить из связующего дерева ветви,

414 Глава 5. Сетевой уровень

не ведущие к членам группы. В результате получается эффективное многоадресное связующее дерево.

Для примера рассмотрим две группы, 1 и 2, в сети, изображенной на рис. 5.14, а. Как показано на рисунке, некоторые маршрутизаторы соединены с хостами, принадлежащими к одной или обеим группам. Связующее дерево для самого левого маршрутизатора показано на рис. 5.14,б. Такое дерево может быть использовано для широковещания, однако (как это видно на примере двух усеченных вариантов дерева, приведенных далее) для многоадресной рассылки оно оказывается избыточным. На рис. 5.14,в удалены все связи, не ведущие к хостам, являющимся членами группы 1. В результате получается многоадресное связующее дерево, по которому самый левый маршрутизатор может отправлять пакеты группе 1. Пакеты передаются исключительно по такому дереву — этот способ оказывается гораздо более экономичным, чем широковещание: новое дерево использует 7 связей вместо 10. На рис. 5.14,г показано усеченное многоадресное связующее дерево для группы 2. Оно использует 5 связей, что доказывает его эффективность. Следует обратить внимание на то, что для разных групп используются разные связующие деревья.

Рис. 5.14. Многоадресная рассылка:а — сеть;б — связующее дерево для самого левого маршрутизатора;в — многоадресное дерево для группы 1;г — многоадресное дерево для группы 2

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

5.2. Алгоритмы маршрутизации 415

а затем удалив из него все связи, не соединяющие входной (корневой) узел с членами данной группы. Одним из протоколов маршрутизации с учетом состояния линий, работающих по такому принципу, является MOSPF (Multicast OSPPF —много-

адресный OSPF) (Moy, 1994).

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

DVRMP (Distance Vector Multicast Routing Protocol— протокол многоадресной маршрутизации по вектору расстояний) (Waitzman и др., 1988).

Усечение позволяет строить эффективные связующие деревья, состоящие только из тех связей, которые необходимы для соединения с членами группы. Недостаток данного метода заключается в том, что он требует от маршрутизаторов выполнения большого количества операций, особенно в больших сетях. Предположим, что в сети есть n групп, каждая из которых в среднем состоит изm членов. На каждом маршрутизаторе и для каждой группы должно хранитьсяm усеченных связующих деревьев, то естьmn деревьев для всей сети. К примеру, на рис. 5.14,в изображено связующее дерево, по которому самый левый маршрутизатор отправляет пакеты группе 1. Связующее дерево, по которому самый правый маршрутизатор отправляет пакеты группе 1 (оно не показано на рисунке), будет выглядетьпо-другому,поскольку пакеты будут передаваться непосредственно членам группы, а не через узлы в левой части графа. А это значит, что выбор направления, в котором маршрутизаторы должны передавать пакеты для группы 1, зависит от того, какой узел является отправителем. При большом количестве групп и отправителей для хранения всех деревьев потребуется много памяти.

Альтернативный метод при построении отдельного связующего дерева для группы использует деревья с корнем в ядре (core-based trees)(Ballardie и др., 1993). Со-

гласно этому методу, все маршрутизаторы выбирают общий корень (также называемыйядром — core илиточкой встречи — rendezvouz point), а для построения дерева все члены группы отправляют в этот корень специальный пакет. Конечное дерево формируется из путей, пройденных этими пакетами. На рис. 5.15,а показано такое дерево с основанием в ядре, построенное для группы 1. Для пересылки пакета этой группе отправитель передает сообщение ядру, откуда оно уже рассылается по дереву. Пример такой работы алгоритма продемонстрирован на рис. 5.15,б для отправителя, расположенного в правой части сети. Однако производительность этого метода может быть улучшена: дело в том, что для многоадресной рассылки не обязательно, чтобы пакеты, предназначенные для группы, приходили в ядро. Как только пакет достигает дерева, он может быть передан как в направлении корня, так и в любом другом направлении. Так алгоритм работает для отправителя, расположенного вверху рис. 5.15,б.

416 Глава 5. Сетевой уровень

Рис. 5.15. Дерево с основанием в сердцевине для группы 1 (а); рассылка для группы 1 (б)

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

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

таких как PIM(Protocol Independent Multicast— многоадресная рассылка, не за-

висящая от протокола) (Fenner и др., 2006).

5.2.9. Произвольная маршрутизация

До сих пор мы рассматривали такие модели предоставления информации, в которых источник отправляет сообщение на один адрес (одноадресная рассылка — unicast), на все адреса (широковещание) или группе адресов (многоадресная рассылка). Иногда используется еще одна модель под названиемпроизвольная рассылка (anycast). При такой рассылке пакет отправляется ближайшему члену группы (Partridge и др., 1993). Методы нахождения соответствующих путей называютсяпроизвольной марш-

рутизацией (anycast routing).

Зачем нам может понадобиться произвольная рассылка? Иногда узлы предоставляют услугу (например, сообщают время суток или передают контент), для которой важно одно: чтобы информация была правильной; при этом не имеет значения, какой узел ее предоставил — с этой задачей справился бы любой узел. Пример использования свободной рассылки в сети Интернет — DNS, о которой мы поговорим в главе 7.

К счастью, нам не придется придумывать новые алгоритмы для произвольной маршрутизации: стандартные методы — маршрутизация по вектору расстояния и маршрутизация с учетом состояния линий — позволяют создавать маршруты для произвольной рассылки. Предположим, что нам нужно передать данные членам группы 1. Вместо различных адресов все члены группы получат одинаковый адрес — «1». Алгоритм маршрутизации по вектору расстояния распределит векторы обычным способом, и узлы выберут кратчайший путь к адресу 1. В результате узлы отправят данные на ближайшее устройство с адресом 1. Соответствующие маршруты показаны на рис. 5.16 а. Этот метод работает успешно потому, что протокол маршрутизации не знает о существовании нескольких устройств с адресом 1, а значит, он считает их всех одним узлом, как показано в топологии на рис. 5.16,б.

Рис. 5.16. Произвольная маршрутизация:а — маршруты для свободной рассылки;б— топология с точки зрения протокола маршрутизации

Такой метод будет работать и для маршрутизации с учетом состояния линий. Здесь, правда, следует добавить, что протокол маршрутизации не обязательно должен находить кажущиеся кратчайшими пути, проходящие чрез узел 1. Это привело бы к «прыжку через гиперпространство», потому что экземпляры узла 1 на самом деле расположены в различных частях сети. Однако сейчас протоколы маршрутизации с учетом состояния линий различают маршрутизаторы и хосты. Мы не говорили об этом раньше, поскольку в этом не было явной необходимости.

5.2.10. Алгоритмы маршрутизации для мобильных хостов

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

418 Глава 5. Сетевой уровень

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

Здесь мы будем рассматривать модель мира, в которой у всех хостов есть постоянноедомашнее местоположение (home location), которое никогда не меняется. У каждого хоста также есть постоянный домашний адрес, которым можно воспользоваться для определения домашнего местоположения, аналогично тому, как телефонный номер1-212-5551212обозначает США (страна с кодом 1) и Манхеттен (212). Целью маршрутизации в системах с мобильными хостами является обеспечение возможности передачи пакетов мобильным хостам с помощью их постоянных домашних адресов. При этом пакеты должны эффективно достигать хостов, независимо от их расположения. Самое сложное здесь, конечно, — найти хост.

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

Еще один вариант — обеспечить мобильность над сетевым уровнем, как это, по сути, сейчас и происходит с переносными компьютерами. При изменении местоположения они получают новые сетевые адреса; при этом старый и новый адреса никак не связаны друг с другом — сеть даже не знает о том, что они принадлежат одному и тому же компьютеру. В этой модели с помощью переносного компьютера можно просматривать содержимое Сети, однако другие хосты не могут отправлять пакеты на данный компьютер (например, осуществлять входящий звонок) без выполнения процедуры адресации высокого уровня (например, повторного входа в Skype при смене местоположения). Более того, связь не будет поддерживаться, если хост движется: в таком случае придется устанавливать новые соединения. С этими проблемами может справиться мобильность на сетевом уровне.

В основе мобильной маршрутизации в сети Интернет и сетях сотовой связи лежит следующая идея: мобильный хост должен сообщать о том, где он находится, хосту, имеющему домашнее местоположение. Этот хост, выполняющий операции от имени мобильного хоста, называется внутренним агентом (home agent). Как только он узнает текущее местоположение мобильного хоста, он может перенаправлять пакеты, которые должны быть ему доставлены.

Рисунок 5.17 наглядно демонстрирует работу мобильной маршрутизации. Отправитель из северо-западногогорода Сиэтла хочет отправить пакет хосту, который обычно находится по другую сторону США, вНью-Йорке.Нас интересует ситуация, при которой мобильный хост располагается не дома. Временно он находится в СанДиего. Для работы в сети мобильный хост вСан-Диегодолжен получить локальный сетевой адрес. Это обычная процедура; о том, как она работает для сети Интернет, мы поговорим позже. Такой локальный адрес называетсяадресом для передачи (care of address). Как только мобильный хост узнает этот адрес, он может сообщить внутреннему агенту свое местонахождение. Для этого он отправляет внутреннему агенту регистрационное сообщение (этап 1), содержащее адрес для передачи. На рис. 5.17 это

5.2. Алгоритмы маршрутизации 419

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

Далее отправитель посылает пакет с данными на мобильный хост с помощью постоянного адреса (этап 2). Сеть передает этот пакет на домашнее местоположение хоста, так как именно ему принадлежит этот домашний адрес. В Нью-Йоркевнутренний агент перехватывает этот пакет, поскольку мобильный хост находится далеко от дома. Затем он формирует пакет с новым заголовком (инкапсулирует —encapsulates, или,

как иногда говорят, «заворачивает» — wraps) и отправляет все это на адрес для переда-

чи (этап 3). Такой прием называется туннелированием (tunneling). Поскольку он имеет важное значение в работе сети Интернет, далее мы поговорим о нем более подробно.

Когда этот пакет прибывает на адрес для передачи, мобильный хост разворачивает пакет и считывает данные, полученные от отправителя. Далее мобильный хост напрямую посылает отправителю ответный пакет (этап 4). Весь этот путь называется

треугольной маршрутизацией (triangle routing); он может быть непрямым, если удаленное местоположение расположено на большом расстоянии от домашнего местоположения. На этапе 4 отправитель может узнать текущий адрес для передачи. Последующие пакеты могут направляться напрямую на мобильный хост, передаваясь по туннелю на адрес для передачи (этап 5), полностью минуя домашний адрес мобильного пользователя. Если соединение будет прервано из-за перемещения мобильного устройства, для связи с ним всегда можно использовать домашний адрес.

Рис. 5.17. Маршрутизация пакетов мобильным хостам

Мы не уделили внимания еще одному важному аспекту: безопасности. Как правило, когда хост или маршрутизатор получает сообщение вида «Начиная с этого момента, пожалуйста, пересылайте мне всю почту, адресуемую Стефани», у него могут возникнуть вопросы — например, с кем он разговаривал, соглашаться или нет на данное предложение. Поэтому, для того чтобы достоверность сообщений можно было проверить с помощью криптографических протоколов (о которых мы поговорим в главе 8), в сообщения добавляется информация о безопасности.

Существует много различных схем мобильной маршрутизации. Алгоритм, представленный выше, основан на мобильности IPv6 — той форме мобильности, которая

420 Глава 5. Сетевой уровень

используется в сети Интернет (Джонсон и др., 2004), а также в IP-сетях сотовой свя- зи, таких как UMTS. Для простоты в нашем примере отправитель рассматривался как стационарный узел, однако алгоритм позволяет обоим узлам быть мобильными хостами. Или же хост может быть частью мобильной сети, например сети в самолете. Такое расширение базовой схемы не требует дополнительных действий со стороны хостов (Devarapalli и др., 2005).

В некоторых схемах используется внешний (то есть удаленный) агент — это то же самое, что и внутренний агент, только с внешним расположением; аналогом внешнего агента в сетях сотовой связи является VLR (Visitor Location Register, гостевой регистр местоположения). Однако в большинстве более новых схем внешний агент не требуется; мобильные хосты сами являются своими внешними агентами. В любом случае, знание временного местоположения мобильного хоста ограничивается небольшим числом хостов (например, мобильное устройство, внутренний агент и отправители), поэтому маршрутизаторам крупной сети не придется повторно вычислять маршруты.

Более подробную информацию о мобильной маршрутизации можно найти в рабо-

тах Perkins (1998, 2002) и Snoeren и Balakrishnan (2000).

5.2.11. Маршрутизация в произвольных сетях

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

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

(ad hoc networks) или мобильными произвольными сетями(MANET— Mobile Ad hoc NETworks). Давайте их вкратце рассмотрим. Более подробную информацию можно найти в книге (Perkins, 2001).

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

Известно множество алгоритмов выбора маршрута для произвольных сетей. Однако поскольку по сравнению с мобильными сетями произвольные сети пока не так широко используются на практике, не ясно, какие из этих протоколов наиболее удобны. Для примера рассмотрим один из наиболее популярных — алгоритм AODV (Ad hocOn-demand Distance Vector —маршрутизация по требованию в произвольных

5.2. Алгоритмы маршрутизации 421

сетях на основе вектора расстояний). Об этом можно прочитать у (Perkins и Royer, 1999). AODV является родственником метода векторов расстояний, адаптированным для работы в мобильной среде, где узлы обычно имеют ограниченную пропускную способность и время работы от автономных элементов питания. Давайте посмотрим, как этот алгоритм вычисляет маршруты и следит за их изменением.

Построение маршрута

В AODV маршруты к адресу назначения вычисляются «по требованию», то есть толь-

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

Для описания алгоритма рассмотрим недавно сформированную произвольную сеть, изображенную на рис. 5.18. Предположим, что процессу, запущенному на узле А, необходимо отправить пакет на узелI. Алгоритм AODV на каждом узле ведет таблицу векторов расстояния, доступ к которой осуществляется с помощью поля адреса. Таблица содержит информацию об адресате, в том числе адрес ближайшего соседа, которому необходимо переслать пакет, чтобы он мог достичь пункта назначения. СначалаАпросматривает эту таблицу и не находит записи дляI. Значит, нужно найти маршрут, ведущий к этому узлу. Итак, алгоритм начинает заниматься поисками маршрутов только тогда, когда они реально требуются. Это и делает его алгоритмом «по требованию».

Рис. 5.18. Произвольная сеть:а — зона широковещанияА;б — состояние после получения его узламиВ иD;в — состояние после получения его узламиC,F иG;г — состояние после получения его узламиE,H иI. Затененными кружочками обозначены новые получатели. Пунктиром показаны возможные обратные маршруты. Сплошными линиями показан построенный маршрут

422 Глава 5. Сетевой уровень

Для поиска I узелА генерирует пакет запроса маршрутаROUTE REQUEST и распространяет его по сети методом заливки (см. раздел 5.2.3). На рис. 5.18,а показано, что этот пакет достигает узловB иD. Далее каждый узел повторно передает запрос, который в результате достигает узловF,G иC (рис. 5.18,в) и узловH,E иI (рис. 5.18,г). Чтобы избавиться от лишних копий пакета при заливке, используется порядковый номер. Так, например,D не принимает передачу отB (рис. 5.18,в), так как он уже передал запрос. Наконец запрос достигает узлаI, который создает пакетROUTE REPLY. Этот пакет пересылается отправителю по тому же пути, по которому он пришел. Чтобы это было возможно, каждый узел должен помнить, какой узел передал ему запрос. Информация об обратном маршруте, хранящаяся в памяти узлов, показана на рис. 5.18,б–г стрелками. При передаче запроса каждый узел также увеличивает значение счетчика транзитных участков. Это позволяет понять, насколько далеко от адреса назначения расположен узел. Ответы сообщают каждому отдельному узлу, какому из соседей следует передавать пакет, предназначенный для данного адреса: тому узлу, от которого пришел ответ. Во время обработки ответа узлыG иD записывают сведения о наилучшем маршруте в таблицы маршрутизации. Когда ответ достигает узлаA, появляется новый маршрут —ADGI.

В больших сетях алгоритмом генерируется много широковещательных пакетов даже для адресатов, расположенных достаточно близко друг к другу. Чтобы уменьшить издержки, область широковещания может быть ограничена полемВремя жизни (Time to live)IP-пакета.Это поле устанавливается отправителем и декрементируется при каждой пересылке. Когда его значение становится равным 0, пакет отвергается, а не распространяется дальше. При этом процесс поиска пути немного изменяется. Для обнаружения адресата отправитель рассылает пакет запроса маршрута соВременем жизни, равным 1. Если в течение разумного времени ответ не приходит, посылается еще один запрос соВременем жизни, равным 2. И так далее. Таким образом, поиск, начавшийся вкакой-толокальной области, все больше расширяет свой охват.

Обслуживание маршрута

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

Эта информация используется для удаления нерабочих путей. Для каждого из возможных адресатов каждый узел N хранит историю о том, какие активные соседи снабжали узел пакетами для данных адресатов в течение последнихT секунд.

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

5.2. Алгоритмы маршрутизации 423

пути больше нельзя использовать и их следует удалить из таблиц маршрутизации. В нашем примере D удаляет из своей таблицы маршрутизации записи для G и I и сообщает об этом A, который в свою очередь удаляет I. В общем случае активные соседи передают эти новости своим активным соседям и т. д., пока все пути, зависевшие от ушедшего узла, не будут удалены из всех таблиц.

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

Чтобы обеспечить быструю конвергенцию, маршрутам присваиваются порядковые номера, контролируемые получателем. Порядковый номер получателя — своего рода логические часы. Получатель увеличивает этот номер каждый раз при отправке нового пакета ROUTE REPLY. Чтобы запросить новый маршрут, отправитель добавляет в пакетROUTE REQUEST порядковый номер получателя для последнего использовавшегося маршрута: это может быть или порядковый номер только что удаленного маршрута, или 0, то есть исходное значение. Запрос будет передаваться широковещательным способом до тех пор, пока не будет найден маршрут с большим порядковым номером. Промежуточные узлы сохраняют маршруты, имеющие больший порядковый номер или меньшее число промежуточных узлов для текущего порядкового номера.

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

Пока мы рассмотрели только один маршрут: от A доI. Для большей экономии ресурсов построение и обслуживание пересекающихся маршрутов производится совместно. К примеру, еслиB тоже захочет отправлять пакеты вI, он выполнит вычисление маршрута. Но в таком случае запрос сначала достигнет узлаD, который уже знает о существовании маршрута, ведущего кI. И тогда узелD может отправитьB ответ, содержащий нужный маршрут, тем самым избежав лишних вычислений.

Существует множество других схем маршрутизации в произвольных сетях. Еще один известный алгоритм «по требованию» называется DSR (Dynamic Source Routing — динамическая маршрутизация от источника) ( Johnson и др., 2001). Дру-

гая стратегия, основанная на географии, используется в GPSR (Greedy Perimeter

Stateless Routing — «жадный» протокол маршрутизации по периметру без учета состояний). Если все узлы знают свое географическое местоположение, доставка пакета получателю может происходить без вычисления маршрута: пакет можно каждый раз отправлять в правильном направлении, возвращаясь назад в случае, если иначе путь приведет в тупик. Выбор протокола зависит в первую очередь от характеристик данной произвольной сети.