Лекции 2010-го года (1130544), страница 62
Текст из файла (страница 62)
На рисунке 5-16 (b) показана полнаятаблица маршрутизации для маршрутизатора 1А без иерархии. На рисунке 5-16 (с) – та жетаблица при двухуровневой иерархии. Нетрудно видеть, что таблица маршрутизации вовтором случае резко сократилась.Рисунок 5-16. Иерархическая маршрутизацияОднако за эту экономию приходится платить эффективностью маршрутизации. Например,наилучший маршрут от 1А к 5С проходит через регион 2, однако в данном случае онпройдет через регион 3, поскольку большинство машин в регионе 5 действительноэффективнее достигнуть через регион 3.При построении иерархии возникает сразу несколько вопросов.
Один из них: сколькоуровней должно быть в иерархии при заданном размере сети? Например, если нашатранспортная среда содержит 920 маршрутизаторов, то без иерархии таблица каждогобудет иметь 920 строк. Если транспортную среду разбить на 40 регионов, то размертаблиц будет равен 23 строки для маршрутизации внутри региона плюс 40 длямаршрутизации между регионами. Если использовать трехуровневую иерархию иобъединить регионы в кластеры, то при 5 кластерах, по 8 регионов с 23маршрутизаторами в каждом у таблицы будет 23 входа для внутрикластерной21маршрутизации, плюс 7 входов для межкластерной, плюс 5 входов для межрегиональноймаршрутизации. Итого 35 входов.Клейнрок и Камоун показали, что оптимальное число уровней иерархии в транспортнойсреде при N узлах будет равняться lnN, при e*lnN строках в таблице маршрутизатора.5.2.8.
Маршрутизация для мобильного узлаМиллионы людей в наши дни путешествуют, находятся в командировках. Многим из нихпросто необходимо иметь доступ к своей электронной почте, файловой системе. Так мыприходим к проблеме мобильного узла, которую мы уже отмечали. Это относительноновая проблема, но, несмотря на это, она стоит довольно остро.На рисунке 5-17 показана модель WAN с мобильным узлом.
Всех пользователей мыможем разделить на две большие группы. Стационарные - это большая группа, ихкомпьютеры подключены к сети стационарными средствами (проводами, кабелями) иредко меняют свое место положение. Другая группа постоянно меняет своеместоположение и стремится поддерживать связь с сетью. Этих пользователей мы будемназывать мобильными.Рисунок 5-17. Модель WAN с мобильным узломПредполагается, что в сети каждый пользователь имеет постоянное домашнееместоположение, которое никогда не меняется. Проблема маршрутизации в этих условияхзаключается в том, чтобы посылать пакеты мобильному пользователю через его домашнееместоположение. При этом то, где находится сам пользователь, не имеет значения.
ВсяWAN на рисунке 5-17 разбивается на области. В каждой области есть агент визитеров,который знает о всех мобильных пользователях в своей области. В свою очередь, вкаждой области есть домашний агент, который знает обо всех стационарныхпользователях в своей области, которые в настоящий момент путешествуют.Как только мобильный узел подключается к местной, локальной сети, он регистрируется уагента визитеров.
Эта процедура примерно выглядит так:1.Периодически агент визитеров рассылает по своей области пакет, где указаноместоположение этого агента и его адрес. Если мобильный узел, подключившись ксети, долго не видит такого пакета, он рассылает свой пакет с просьбой агентувизитеров объявить свои координаты.222.Мобильный узел регистрируется у агента визитеров, указывая свое текущееместоположение, домашнее местоположение и определенную информацию,связанную с безопасностью передаваемых данных.3.Агент визитеров обращается через сеть к домашнему агенту домашнегоместоположения визитера, указывая, что один из его пользователей сейчас находитсяв его области, передавая конфиденциальную информацию, которая должна убедитьдомашнего агента, что это действительно его пользователь пытается соединиться сним.4.Домашний агент изучает конфиденциальные данные, время связи. Если эти данныесоответствуют той информации, что есть у домашнего агента об этом пользователе,он дает добро на связь.5.Агент визитеров, получив подтверждение от домашнего агента, заносит данные омобильном узле в свои таблицы и регистрирует его.В идеале пользователь, покидая область визита, должен закрыть свою временнуюрегистрацию.
Однако, как правило, закончив сеанс связи, пользователь просто выключаетсвой компьютер и все. Поэтому, если по прошествии некоторого времени пользователь необъявился вновь, агент визитеров считает его покинувшим область.Рассмотрим теперь, что происходит, когда кто-то посылает сообщения мобильному узлу(рисунок 5-18). Пакет поступает на адрес домашнего местоположения пользователя, гдеего перехватывает домашний агент. Домашний агент инкапсулирует этот пакет в свойпакет, который он отправляет по адресу агента визитеров той области, откуда последнийраз был сеанс связи с пользователем.
Одновременно с этим домашний агент посылаетсообщение отправителю пакета, чтобы он все последующие пакеты мобильному узлуинкапсулировал в сообщениях, направляемых по адресу агента визитеров. Такоймеханизм инкапсулирования одних пакетов в другие называется туннелированием, и мыего подробно рассмотрим позднее.Рисунок 5-18. Маршрутизация пакетов для мобильных пользователейЗдесь мы обрисовали лишь в общих чертах основную схему работы. Конкретных схемсуществует множество, которые различаются разными аспектами. Прежде всего тем, как23распределяется работа между маршрутизаторами и хостами, какой уровень в стекепротоколов хоста отвечает за реализацию соответствующих протоколов. Во-вторых, естьсхемы, где маршрутизаторы запоминают информацию о местонахождения мобильныхузлов и могут вмешиваться в диалог между агентом визитеров и домашним агентом, поразному маршрутизируя трафик.
В некоторых схемах мобильный узел получаетнекоторый уникальный адрес, в других это адрес агента, который отвечает замаршрутизацию всего трафика мобильных узлов. Кроме этого, схемы различаютсяразным уровнем безопасности передаваемой информации.5.2.9. Маршрутизация при вещанииВ некоторых приложениях возникает потребность переслать одно и то же сообщение всеммашинам. Например, прогноз погоды, биржевые сводки, новости и т.д. Такой режимпередачи называется вещанием. Есть несколько способов реализации такого режима.Первый способ: источник знает, кому надо послать, и генерирует столько сообщений,сколько получателей. Это одно из самых плохих решений. Оно не требует никакихспециальных средств, однако весьма накладно.
Тратится не только пропускнаяспособность каналов, но и память – ведь где-то кому-то надо хранить весь лист рассылки.Метод лавины – другое решение. Однако, как мы уже видели, он затратен для каналов«точка-точка». Он слишком сильно расходует пропускную способность.Третий подход – маршрутизация множественной доставки. Здесь каждый пакет должениметь либо лист рассылки, либо карту рассылки.
Каждый маршрутизатор, получив такойпакет, отправляет и дублирует его в соответствии с картой рассылки.Четвертый подход основан на использовании дерева захода, либо любого другогоподходящего дерева связей. Дерево захода позволяет избежать циклов и ненужногодублирования пакетов. Каждый маршрутизатор дублирует пакет вдоль линий,соответствующих дереву захода, кроме той, по которой пакет пришел. В этом подходеочень рационально используется пропускная способность каналов, генерируетсяабсолютный минимум пакетов при рассылке. Однако каждый маршрутизатор где-тодолжен иметь дерево захода, соответствующее случаю.Пятый подход основан на неявном использовании дерева связей.
Когда пакет поступает,маршрутизатор проверяет: если он поступил по линии, которая используется дляотправления пакетов источнику вещательного пакета, то вещательный пакет дублируетсяи рассылается по всем линиям, кроме той, по которой пакет пришел. Если нет, то онсбрасывается.Этот метод называется пересылкой вдоль обратного пути. На рисунке 5-19 показанпример работы этого алгоритма.
На рисунке 5-19 (a) показана топология транспортнойсреды. На рисунке 5-19 (b) показано дерево захода для вершины I, часть (c) показывает,как работает этот алгоритм. Сначала в вершине I было сгенерировано и разослано 4пакета. Во всех четырех вершинах (F, H, J, N), куда поступили эти пакеты, они поступилис предпочтительного для I направления.
Из восьми пакетов, сгенерированных наследующем этапе, дереву захода только пять поступили по предпочтительному для Iнаправлению. На третьем этапе из шести сгенерированных пакетов только три поступилипо предпочтительному направлению (G, D, N поступили дубликаты). После того, как пятьэтапов пройдены и сгенерированы 23 пакета, рассылка прекращается. Достоинством этогометода является простота и легкость в реализации.24Рисунок 5-19. Пересылка вдоль обратного пути (а) Подсеть; (b) Связующее дерево; (с)Дерево, построенное методом пересылки вдоль обратного пути5.2.10.