5.2.6. Иерархическая маршрутизация
Размер таблиц маршрутов, поддерживаемых маршрутизаторами, увеличивается пропорционально увеличению размеров сети. При этом требуется не только большее количество памяти для хранения этой таблицы, но и большее время центрального процессора для ее обработки. Кроме того, возрастает размер служебных пакетов, которыми обмениваются маршрутизаторы, что увеличивает нагрузку на линии. В определенный момент сеть может вырасти до таких размеров, при которых перестанет быть возможным хранение на маршрутизаторах записей обо всех остальных маршрутизаторах. Поэтому в больших сетях маршрутизация должна осуществляться иерархически, как это делается в телефонных сетях.
При использовании иерархической маршрутизации маршрутизаторы разбиваются на отдельные так называемые регионы (regions). Каждый маршрутизатор знает все детали выбора маршрутов в пределах своей области, но ему ничего не известно о внутреннем строении других регионов. При объединении нескольких сетей естественно рассматривать их как отдельные регионы, при этом маршрутизаторы одной сети освобождаются от необходимости знать топологию других сетей.
В очень больших сетях двухуровневой иерархии может оказаться недостаточно. Может потребоваться группировать регионы в кластеры, кластеры в зоны, зоны в группы и т. д., пока у нас не иссякнет фантазия на названия для новых образований. В качестве примера многоуровневой иерархии рассмотрим маршрутизацию пакета, пересылаемого из университета Беркли (Berkeley), штат Калифорния в Малинди (Malindi) в Кении. Маршрутизатор в Беркли знает детали топологии в пределах Калифорнии, но трафик, направляющийся за пределы штата, он посылает маршрутизатору в Лос-Анджелесе. Маршрутизатор в Лос-Анджелесе может выбрать прямой маршрут для трафика в пределах США, но все пакеты, направляемые за рубеж, переправляет в Нью-Йорк. Нью-йоркский маршрутизатор направит трафик на маршрутизатор страны назначения, ответственный за прием трафика из-за границы. Он может располагаться, например, в Найроби. Наконец, направляясь вниз по дереву иерархии уже в пределах Кении, пакет попадет в Малинди.
На рис. 5.12 приведен количественный пример маршрутизации в двухуровневой иерархии с пятью регионами. Полная таблица маршрутизатора 1A, как показано на рис. 5.12, б, состоит из 17 записей. При использовании иерархической маршрутизации, как показано на рис. 5.12, в, таблица, как и прежде, содержит сведения обо всех локальных маршрутизаторах, но записи обо всех остальных регионах концентрируются в пределах одного маршрутизатора, поэтому трафик во второй регион по-прежнему пойдет по линии 1B-2A, а во все остальные регионы — по линии 1C-3B. При иерархической маршрутизации размер таблицы маршрутов уменьшается с 17 до 7 строк. Чем крупнее выбираются регионы, тем больше экономится места в таблице.
Рис. 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 маршрутизаторов, равно ln N. При этом потребуется e ln N записей для каждого маршрутизатора. Они также показали, что увеличение длины эффективного среднего пути, вызываемое иерархической маршрутизацией, довольно мало и обычно является приемлемым.
5.2.7. Широковещательная маршрутизация
В некоторых приложениях хостам требуется посылать сообщения на множество хостов или даже на все сразу. Можно привести такие примеры, как распространение прогнозов погоды, обновление биржевых курсов ценных бумаг, радиопрограммы в прямом эфире. Эффективнее всего отправлять соответствующие данные широковещательным способом, предоставляя возможность получить их всем заинтересованным хостам. Итак, широковещанием (broadcasting) называется рассылка пакетов по всем пунктам назначения одновременно. Для ее реализации применяются разнообразные методы.
Один из методов широковещательной маршрутизации не требует никаких особых способностей от сети и используется просто для того, чтобы рассылать отдельные пакеты по всем направлениям. Он не только является медленным и неэффективным с точки зрения пропускной способности, но и требует, чтобы у источника пакета был полный список всех хостов. На практике такой метод является нежелательным, хотя и отличается широким применением.
Один из более совершенных алгоритмов называется многоадресной маршрутизацией (multidestination routing), при которой в каждом пакете содержится либо список адресатов, либо битовая карта, показывающая предпочитаемые хосты назначения. Когда такой пакет прибывает в маршрутизатор, последний проверяет список, содержащийся в пакете, определяя набор выходных линий, которые потребуются для дальнейшей рассылки. (Линия может потребоваться в том случае, если она входит в оптимальный путь к какому-то из адресатов списка.) Маршрутизатором создается копия пакета для каждой из используемых исходящих линий. В нее включаются только те адресаты, для доступа к которым требуется данная линия. Таким образом, весь список рассылки распределяется между исходящими линиями. После определенного числа пересылок каждый из пакетов будет содержать только один адрес назначения, как и обычный пакет. Многоадресная маршрутизация подобна использованию индивидуально адресуемых пакетов с той разницей, что в первом случае из нескольких пакетов, следующих по одному и тому же маршруту, только один «платит полную стоимость», а остальные едут бесплатно. В таком случае пропускная способность используется более эффективно. Однако этот метод все же требует начальных сведений обо всех адресах назначения, и, кроме того, чтобы понять, куда отправить один многоадресный пакет, маршрутизатор должен выполнить столько же действий, сколько и при отправке набора отдельных пакетов.
Мы уже знакомы с еще одним методом широковещательной маршрутизации: заливкой. Если заливка реализована с помощью порядковых номеров, она эффективно работает с каналами связи, поскольку маршрутизаторы используют относительно простое правило принятия решения. Хотя этот метод плохо подходит для обычных двухточечных соединений, он может быть хорошим претендентом для широковещания. Но оказывается, что ситуация может быть еще лучше, если кратчайшие пути для стандартных пакетов уже вычислены.
Идея продвижения по встречному пути (reverse path forwarding) замечательно проста и изящна (Dadal, Metcalfe, 1978). Когда прибывает широковещательный пакет, маршрутизатор проверяет, используется ли та связь, по которой он прибыл, для нормальной передачи пакетов источнику широковещания. В случае положительного ответа велика вероятность того, что широковещательный пакет прибыл по наилучшему маршруту и является, таким образом, первой копией, прибывшей на маршрутизатор. Тогда маршрутизатор рассылает этот пакет по всем связям, кроме той, по которой он прибыл. Однако если широковещательный пакет прибывает от того же источника по другой связи, он отвергается как вероятный дубликат.
