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

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

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

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

На рис. 5.13 приведен количественный пример маршрутизации в двухуровне­вой иерархии с пятью регионами. Полная таблица маршрутизатора 1А, как пока­зано на рис. 5.13, б, состоит из 17 записей. При использовании иерархической маршрутизации, как показано на рис. 5.13, в, таблица, как и прежде, содержит сведения обо всех локальных маршрутизаторах, но записи обо всех остальных регионах концентрируются в пределах одного маршрутизатора, поэтому трафик во второй регион по-прежнему пойдет по линии 1В — 2А, а во все остальные ре­гионы — по линии 1С — ЗВ. При иерархической маршрутизации размер таблицы маршрутов уменьшается с 17 до 7 строк. Чем крупнее выбираются регионы, тем больше экономится места в таблице.

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

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

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