Компьютерные сети. 6-е изд.

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

На илл. 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). Существует несколько методов ее реализации.

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