tanenbaum_seti_all.pages (525408), страница 113
Текст из файла (страница 113)
Флаги отсылки означают, что этот пакет следует отослать по соответствующей линии. Флаги подтверждений означают, что нужно подтвердить получение этого пакета по данной линии, Фпвпз Фпад отсыпки подтвермдення Порядковый Источник номер Возраст А С Е А С Данные Рно. В,12. Буфер пакетов мврозрутизвторе В с рисунка Б.! 1 Как видно из рис, 5.12, пакет состояния линий от маршрутизатора А пришел напрямую, поэтому он должен быть отправлен маршрутизаторам С и Р, а подтверждение о его получении следует направить маршрутизатору А, что и показывают флаговые биты. Аналогично, пакет от Г следует переслать маршрутизаторам А и С, а Готослать подтверждение.
Однако ситуация с третьим пакетом, полученным от маршрутизатора Е, отличается. Он был получен дважды, по линиям ЕАВ и ЕГВ. Следовательно, его нужно отослать только С, но подтверждения выслать и А, и Г, как указывают биты. Если в то время, когда оригинал еще находится в буфере, прибывает дубликат пакета, значение битов должно быть изменено. Например, если копия состояния маршрутизатора С прибудет от Г прежде, чем четвертая строка таблицы будет разослана, шесть флаговых битов примут значение 100011, и это будет означать, что следует подтвердить получение пакета от Е, но не пересылать его Е Алгоритмы маршрутизации 423 Вычисление новых маршрутов Собрав полный комплект пакетов состояния линий, маршрутизатор может построить полный граф подсети, так как он располагает данными обо всех линиях На самом деле, каждая линия представлена даже дважды, по одному значению для каждого направления.
Эти два значения могут усредняться или использоваться по отдельности. Теперь для построения кратчайшего пути ко всем возможным адресатам может быть локально применен алгоритм Дейкстры. Результат вычислений может быть установлен в таблицах маршрутов, после чего можно возобновить нормальную работу маршрутизатора. В подсети, состоящей из п маршрутизаторов, у каждого из которых я соседей, количество памяти, необходимой для хранения входной информации, пропорционально яж Кроме того, может потребоваться много времени на обработку информации. В больших подсетях это может составлять проблему.
Тем не менее, во многих практических ситуациях маршрутизация с учетом состояния линий работает вполне удовлетворительно, Однако неисправности оборудования или программного обеспечения могут привести к очень серьезным проблемам при использовании данного алгоритма (а также других алгоритмов). Например, если маршрутизатор заявит о существовании линии, которой у него в действительности нет, или наоборот, забудет о существовании имеющейся у него линии, граф подсети окажется неверным, Если маршрутизатор не сможет переслать пакеты или повредит их при пересылке, также возникнет проблема. Наконец, если у маршрутизатора закончится свободная память или он ошибется в расчетах маршрутов, также возможны различные неприятности.
При увеличении размера подсети до нескольких десятков или сотен тысяч маршрутизаторов вероятность выхода из строя одного из них перестает быть пренебрежимо малой. Все, что можно здесь сделать, — это попытаться ограничить вред, наносимый практически неизбежным выходом из строя оборудования. Эти проблемы и методы их разрешения подробно обсуждаются в (Рег!шап, 1988).
Маршрутизация с учетом состояния линий широко применяется в современных сетях, поэтому следует сказать несколько слов о некоторых примерах протоколов, использующих данный алгоритм. Одним из таких протоколов является протокол ОБРЕ, все чаще применяемый в Интернете, о котором будет рассказано в разделе «Протокол внутреннего шлюза ОБРЕ», Другим важным протоколом с учетом состояния линий является 1$-1Я (1пгеппейате Бузтет то 1пгеппеййаге Зузсет — связь между промежуточными системами) — протокол, разработанный для сети 1)ЕСпес и принятый впоследствии Международной организацией по стандартизации 150 для использования вместе с протоколом сетевого уровня С(.ХР, не требующим соединений.
С тех пор он был модифицирован для поддержки также и других протоколов, в частности 1Р. Протокол 13-13 используется в некоторых магистралях сети Интернет (включая старую магистраль ХЗГХЕТ) и в некоторых цифровых сотовых системах, например, в С1)Р1). В сети Хоче!! ХейЧаге применяется разновидность протокола 15- 18 (Х15Р) для маршрутизации 1РХ-пакетов. 424 Глава 5. Сетевой уровень В основе работы протокола 13-13 лежит распространение картины топологии маршрутизаторов, по которой рассчитываются кратчайшие пути, Каждый маршрутизатор сообщает в информации о состоянии линий доступные ему напрям)но адреса сетевого уровня. Эти адреса могут быть адресами 1Р, 1РХ, Арр!еТа1к или другими. Протокол 18-1Б может даже осуществлять одновременную поддержку нескольких протоколов сетевого уровня.
Многие новшества, разработанные для протокола 13-15, были приняты несколько лет спустя при разработке протокола ОБРК К ним относятся метод саморегуляции лавинного потока обновлений информации о состоянии линий, концепция выделенного маршрутизатора в локальной сети, а также метод вычисления и поддержки расщепления пути и умножения метрик.
Соответственно, между протоколами 1Б-15 и ОБРР нет почти никакой разницы. Наиболее существенное различие между ними заключается в том, что способ кодирования в протоколе 15-1$, в отличие от ОЯРР, облегчает одновременную поддержку нескольких сетевых протоколов. Это свойство особенно важно в больших многопротокольных средах. Иерархическая маршрутизация Размер таблиц маршрутов, поддерживаемых маршрутизаторами, увеличивается пропорционально увеличению размеров сети. При этом требуется не только большее количество памяти для хранения этой таблицы, но и большее время центрального процессора для ее обработки. Кроме того, возрастает размер служебных пакетов, которыми обмениваются маршрутизаторы, что увеличивает нагрузку на линии.
В определенный момент сеть может вырасти до таких размеров, при которых перестанет быть возможным хранение на маршрутизаторах записи обо всех остальных маршрутизаторах. Поэтому в больших сетях маршрутизация должна осуществляться иерархически, как зто делается в телефонных сетях. При использовании иерархической маршрутизации маршрутизаторы разбиваются на отдельные так называемые регионы. Каждый маршрутизатор знает все детали выбора маршрутов в пределах своей области, но ему ничего не известно о внутреннем строении других регионов, При объединении нескольких сетей естественно рассматривать их как отдельные регионы, прн этом маршрутизаторы одной сети освобождаются от необходимости знать топологию других сетей.
В очень больших сетях двухуровневой иерархии может оказаться недостаточно. Может потребоваться группировать регионы в кластеры, кластеры в эоны, зоны в группы, и т. д., пока у нас не иссякнет фантазия на названия для новых образований. В качестве примера многоуровневой иерархии рассмотрим маршрутизацию пакета, пересылаемого из университета Беркли (Ветке!еу), штат Калифорния, в Малннди (Ма11пй) в Кении.
Маршрутизатор в Берклн знает детали топологии в пределах Калифорнии, но график, направляющийся за пределы штата, он посылает маршрутизатору в Лос-Анджелесе. Маршрутизатор в Лос-Анджелесе может выбрать маршрут для графика в пределах США, но все пакеты, направляемые за рубеж, переправляет в Нью-йорк. Нью-йоркский маршрутизатор направит трафнк на маршрутизатор страны назначения, ответственный за прием Алгоритмы маршрутизации 426 Полнея таблица для 1А Иерархическая таблица для 1А Транзитные Транзитные Назначение Линия участки Назначение Линия участки Регион 1 Регион 2 1А 1В 1С 2А 2В 2С 20 ЗА ЗВ 4А 4В 4С 5А 5В 5С 50 5Е 1А 1В 1С 2 3 4 5 В', 20 5С ', 5Е.х 50 Ретион4 Ретионб Релюн 3 Рис. б.! 3. Иерархическая маршрутизация К сожалению, этот выигрыш памяти ие достается бесплатно.
Платой за уменьшение размеров таблицы маршрутов является увеличение длины пути. Например, наилучший маршрут от 1А до 5С проходит через регион 2, однако при использовании иерархической маршрутизации весь трафик в регион 5 направляется через регион З,поскольку так лучше для большинства адресатов в регионе 5. Когда единая сеть становится очень большой, возникает интересный вопрос: сколько уровней должна иметь иерархия7 для примера рассмотрим подсеть с 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е(пгоск) в 1979 году показали, что оптимальное количество уровней иерархии для подсети, состоящей из Умаршрутизаторов, равно 1п Ж, При этом потребуется е 1п дозаписей для каждого маршрутизатора.
Они также показали, что увеличение длины эффективного среднего пути, вызываемое иерархической маршрутизацией, довольно мало и обычно является приемлемым. Широковещательная маршрутизация В некоторых приложениях хостам требуется посылать сообщения на множество хостов или даже на все сразу. Можно привести такие примеры, как распространение прогнозов погоды, обновление биржевых курсов ценных бумаг, радиопрограммы в прямом эфире. Эффективнее всего распространять соответствующие данные широковещательным способом, предоставляя возможность всем заинтересованным хостам получить их. Итак, широковещанием называется рассылка пакетов по всем пунктам назначения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
