Э. Таненбаум - Компьютерные сети. (4-е издание) (DJVU) (1130092), страница 114
Текст из файла (страница 114)
Наиболее существенное различие между ними заключается в том, что способ кодирования в протоколе 1Б-1Б, в отличие от ОБРГ, облегчает одновременную поддержку нескольких сетевых протоколов. Это свойство особенно важно в больших многопротокольных средах. Иерархическая маршрутизация Размер таблиц маршрутов, поддерживаемых маршрутизаторами, увеличивается пропорционально увеличению размеров сети. При этом требуется не только большее количество памяти для хранения этой таблицы, но и большее время центрального процессора для ее обработки. Кроме того, возрастает размер служебных пакетов, которыми обмениваются маршрутизаторы, что увеличивает нагрузку на линии. В определенный момент сеть может вырасти до таких размеров, при которых перестанет быть возможным хранение на маршрутизаторах записи обо всех остэльных маршрутизаторах. Поэтому в больших сетях маршрутизация должна осуществляться иерархически, как это делается в телефонных сетях.
При использовании иерархической маршрутизации маршрутизаторы разбиваются на отдельные так называемые регионы. Каждый маршрутизатор знает все детали выбора маршрутов в пределах своей области, но ему ничего не известно о внутреннем строении других регионов. При объединении нескольких сетей естественно рассматривать их как отдельные регионы, при этом маршрутизаторы одной сети освобождаются от необходимости знать топологию других сетей.
В очень больших сетях двухуровневой иерархии может оказаться недостаточно. Может потребоваться группировать регионы в кластеры, кластеры в зоны, зоны в группы, и т. д., пока у нас не иссякнет фантазия на названия для новых образований. В качестве примера многоуровневой иерархии рассмотрим маршРутизацию пакета, пересылаемого из университета Беркли (Ветке!еу), штат Калифорния, в Мэлинди (Ма((щ(1) в Кении.
Маршрутизатор в Беркли знает детали топологии в пределах Калифорнии, но трафик, направляющийся за пределы штата, он посылает маршрутизатору в Лос-Анджелесе. Маршрутизатор в Лос-Анджелесе может выбрать маршрут для трафика в пределах США, но все пакеты, направляемые за рубеж, переправляет в Нью-йорк. Нью-йоркский маршрутизатор направит трафик на маршрутизатор страны назначения, ответственный за прием Алгоритмы маршрутизации 426 Полная таблица для 1А Иерархическая таблица для 1А Транзитные Назначение Линия участки Регион 2 1А В', 1В 1С 20 2В 2С 20 50 3А ЗВ '..
5Е .' 50 4А 4В Регион 4 Регион б в 5А 5В 5С 50 5Е Транзитные Назначение Линия участки Регион 1 1А 1В 1С 2 3 4 б /3 Регион 3 Рис. 5.13. Иерархическая маршрутизация К сожалению, этот выигрыш памяти не достается бесплатно. Платой за уменьшение размеров таблицы маршрутов является увеличение длины пути. Например наилучший маршрут от 1А до 5С проходит через регион 2, однако при использовании иерархической маршрутизации весь трафик в регион 5 направляется через регион 3, поскольку так лучше для большинства адресатов в регионе 5.
Когда единая сеть становится очень большой, возникает интересный вопрос: сколько уровней должна иметь иерархия? для примера рассмотрим подсеть с 720 маршрутизаторами. Если иерархии нет, то каждому маршрутизатору необхо- графика из-за границы. Он может располагаться, например, в Найроби. Наконец, направляясь вниз по дереву иерархии уже в пределах Кении, пакет попадет в Малинди. На рис.
5.13 приведен количественный пример маршрутизации в двухуровневой иерархии с пятью регионами. Полная таблица маршрутизатора 1А, как показано на рис. 5.13, б, состоит нз 17 записей. При использовании иерархической маршрутизации, как показано на рис. 5.13, в, таблица, как и прежде, содержит сведения обо всех локальных маршрутизаторах, но записи обо всех остальных регионах концентрируются в пределах одного маршрутизатора, поэтому трафик во второй регион по-прежнему пойдет по линии 1 — 2А, а во все остальные регионы — по линии 1С вЂ” ЗВ. При иерархической маршрутизации размер таблицы маршрутов уменьшается с 17 до 7 строк.
Чем крупнее выбираются регионы, тем больше экономится места в таблице. 426 Глава 5. Сетевой уровень димо поддерживать таблицу из 720 строк. Если подсеть разбить на 24 региона по 30 маршрутизаторов в каждом регионе, тогда каждому маршрутизатору потребуется 30 локальных записей плюс 23 записи об удаленных регионах, итого 53 записи. Прн выборе трехуровневой иерархии, состоящей из 8 кластеров по 9 регионов из 10 маршрутизаторов, каждому маршрутизатору понадобится 10 строк в таблице для локальных маршрутизаторов, 8 строк для маршрутизации в другие регионы в пределах своего кластера, плюс 7 строк для удаленных кластеров, итого 25 строк.
Камоун (Кашопп) и Кляйнрок (К1е1пгоск) в 1979 году показали, что оптимальное количество уровней иерархии для подсети, состоящей из )т'маршрутизаторов, равно 1п У. При этом потребуется е 1и )т'записей для каждого маршрутизатора. Они также показали, что увеличение длины эффективного среднего пути, вызываемое иерархической маршрутизацией, довольно мало и обычно является приемлемым, Широковещательная маршрутизация В некоторых приложениях хостам требуется посылать сообщения на множество хостов или даже на все сразу.
Можно привести такие примеры, как распространение прогнозов погоды, обновление биржевых курсов ценных бумаг, радиопрограммы в прямом эфире. Эффективнее всего распространять соответствуюшие данные широковещательным способом, предоставляя возможность всем заинтересованным хостам получить их. Итак, широковещанием называется рассылка пакетов по всем пунктам назначения. Для ее реализации применяются разнообразные методы, Один из методов широковещательной маршрутизации не требует никаких особых способностей от подсети и используется просто для того, чтобы рассылать отдельные пакеты по всем направлениям.
Он не только отнимает у подсети пропускную способность, но н требует, чтобы у источника пакета был полный список всех хостов, На практике это может быть единственная возможность, но такой метод является наименее желательным. Еще одним очевидным кандидатом является метод заливист. Хотя он плохо подходит для обычных двухточечных соединений, для широковещания это может быть серьезный претендент, особенно если нет возможности применить один из методов, описываемых ниже.
Проблема с применением заливки в качестве метоЛа широковеШания такая же, как с двухточечным алгоритмом маршрутизации: при заливке генерируется очень много пакетов и отнимается весьма существенная часть пропускной способности. Третий алгоритм называется многоадресной маршрутизацией. При использовании этого метода в каждом пакете содержится либо список адресатов, либо битовая карта, показывающая предпочитаемые хосты назначения.
Когда такой пакет прибывает на маршрутизатор, последний проверяет список, содержащийся в пакете, определяя набор выходных линий, которые потребуются для дальнейшей рассылки. (Линия может потребоваться в том случае, если она входит в оптимальный путь к какому-то из адресатов списка.) Маршрутизатором создается копия пакета для каждой из используемых исходящих линий. В нее включаются Алгоритмы маршрутизации 427 только те адресаты, для доступа к которым требуется данная линия. Таким образом, весь список рассылки распределяется между исходящими линиями. После определенного числа пересылок каждый из пакетов будет содержать только один адрес назначения и будет выглядеть как обычный пакет. Многоадресная маршрутизация подобна индивидуально адресуемым пакетам с той разницей, что в первом случае из нескольких пакетов, следующих по одному и тому же маршруту, только один зплатит полную стоимостьь, а остальные едут бесплатно.
Еще один, четвертый алгоритм широковещательной маршрутизации в явном виде использует корневое дерево или любое другое связующее дерево. Свяаующее дерево представляет собой подмножество подсети, включающее в себя все маршрутизаторы, но не содержащее замкнутых путей. Если каждый маршрутизатор знает, какие из его линий принадлежат связующему дереву, он может отправить приходящий пакет по всем линиям связующего дерева, кроме той, по которой пакет прибыл.
Такой метод оптимальным образом использует пропускную способность сети, порождая минимальное количество пакетов, требующихся для выполнения работы. Единственной проблемой этого метода является то, что каждому маршрутизатору необходимо обладать информацией о связующем дереве. Иногда такая информация доступна (например, в случае маршрутизации с учетом состояния линий), но иногда — нет (при маршрутизации по векторам расстояний), Последний алгоритм широковещания, который мы рассмотрим, представляет собой попытку приблизиться к поведению предыдущего алгоритма, даже когда маршрутизаторы ничего не знают о связующих деревьях.
Лежащая в основе данного алгоритма иден, называющаяся продвижением по встречному пути, замечательно проста. Когда прибывает широковещательный пакет, маршрутизатор проверяет, используется ли та линия, по которой он прибыл, для нормальной передачи пакетов источнизз1 широковещания, В случае положительного ответа велика вероятность того, что широковещательный пакет прибыл по наилучшему маршруту и является, таким образом, первой копией, прибывшей на маршрутизатор.
Тогда маршрутизатор рассылает этот пакет по всем линиям, кроме той, по которой он прибыл. Однако если пакет прибывает от того же источника гю другой линии, он отвергается как вероятный дубликат. Пример работы алгоритма продвижения по встречному пути показан на Рис. 5.14. Слева изображена подсеть, посередине — входное дерево для маршрутизатора 1 этой подсети, На первом транзитном участке маршрутизатор 1 посылает пакеты маршрутизаторам Г, Н, / и Х, являющимся вторым ярусом дерева. Все эти пакеты прибывают к 1 по предпочитаемым линиям (по пути, совпадающему с входным деревом), что обозначается кружками вокруг символов на Рис. 5.14, в.
На втором этапе пересылки формируются восемь пакетов — по два каждым маршрутизатором, получившим пакет после первой пересылки. Все восемь пакетов попадают к маршрутизаторам, не получавшим ранее пакетов, а пять иа них приходят по предпочитаемым линиям. Из шести пакетов, формируемых иа третьем транзитном участке, только три прибывают по предпочитаемым линиям (на маршрутизаторы С, Е и К). Остальные оказываются дубликатами.
После пяти транзитных участков широковещание заканчивается с общим количест- 428 Глава 5. Сетевой уровень вом переданных пакетов, равным 23, тогда как при использовании входного дерева потребовалось бы 4 транзитных участка и 14 пакетов. и с рис. 6.14. Продвижение по встречному пути: подсеть (е); связующее дерево (П); дерево, поотроенное методом продвижения по встречному пути (в) Принципиальное преимущество метода продвижения по встречному пути заключается в его вполне приемлемой эффективности при простоте реализации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
