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

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

Для очень больших сетей двухуровневой иерархии может оказаться недостаточно. Тогда регионы объединяются в кластеры, кластеры в зоны, зоны в группы и т.д., пока не иссякнет фантазия на названия для новых образований. В качестве примера простой многоуровневой иерархии рассмотрим маршрутизацию пакета, пересылаемого из Университета Беркли, штат Калифорния, в Малинди (Кения). Маршрутизатор в Беркли знает детали топологии в пределах Калифорнии, но трафик, направляющийся за пределы штата, он передает в Лос-Анджелес. Маршрутизатор в Лос-Анджелесе работает в пределах США, но все пакеты, направляемые за рубеж, переправляет в Нью-Йорк. Нью-йоркский маршрутизатор отправит пакет на маршрутизатор страны назначения, ответственный за прием трафика из-за границы. Он может располагаться, например, в Найроби. Наконец, направляясь вниз по дереву иерархии уже в пределах Кении, пакет попадет в Малинди.

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

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

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

Когда единая сеть становится очень большой, возникает интересный вопрос: сколько уровней должна иметь иерархия? Для примера рассмотрим сеть с 720 маршрутизаторами. В системе без иерархии каждый из них должен поддерживать таблицу из 720 строк. Если сеть разбить на 24 региона по 30 маршрутизаторов, каждому из них потребуется 30 локальных записей плюс 23 записи об удаленных регионах, итого 53. При трехуровневой иерархии, состоящей из 8 кластеров по 9 регионов с 10 маршрутизаторами, каждому маршрутизатору понадобится 10 локальных записей, 8 — для других регионов в пределах своего кластера, плюс 7 для остальных кластеров, итого 25. Камоун и Клейнрок (Kamoun and Kleinrock) в 1979 году обнаружили, что оптимальное количество уровней иерархии для сети, состоящей из N маршрутизаторов, равно ln N. При этом потребуется e ln N записей для каждого маршрутизатора. Также они выяснили, что при иерархической маршрутизации эффективная средняя длина пути увеличивается незначительно и обычно остается в допустимых пределах.

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

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

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

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

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

Удивительно простая и изящная концепция пересылки в обратном направлении (reverse path forwarding) была впервые предложена в работе Далала и Меткалфа (Dalal and Metcalfe, 1978). Когда приходит широковещательный пакет, маршрутизатор проверяет, используется ли канал, по которому он прибыл, для обычной передачи данных источнику широковещания. Если это так, то, скорее всего, пакет пришел по наилучшему пути и является первой копией, полученной маршрутизатором. Тогда он рассылает этот пакет по всем линиям (кроме той, по которой он пришел). Но если пакет приходит от того же источника по другому каналу, он отвергается как вероятный дубликат.

Пример работы этого алгоритма представлен на илл. 5.15. Слева (а) изображена сеть, в центре (б) — входное дерево для маршрутизатора I этой сети, а справа (в)