Эндрю Уэзеролл - Компьютерные сети. 5-е издание

Рис. 5.15. Дерево с основанием в сердцевине для группы 1 (а); рассылка для группы 1 (б)

Использование общего дерева не является оптимальным для всех источников. В примере на рис. 5.15, б пакет, передаваемый от отправителя, расположенного в правой части сети, правому верхнему члену группы не напрямую, а через ядро, требует трех переходов. Степень неэффективности зависит от взаимного расположения ядра и отправителей, но чаще всего разумно располагать ядро посередине между отправителями. Если отправитель всего один (как, например, при трансляции видеозаписи членам группы), оптимальной идеей является использовать в качестве ядра самого отправителя.

Следует также отметить, что использование общего дерева позволяет существенно снизить затраты на хранение информации, а также уменьшить число отправленных сообщений и объем вычислений. Для каждой группы маршрутизатор должен хранить не m деревьев, а лишь одно. Кроме того, маршрутизаторы, не являющиеся частью дерева, не участвуют в передаче сообщений группе. Поэтому алгоритмы на основе общих деревьев (в частности, деревьев с основанием в ядре) используются при широковещании для разреженных групп в сети Интернет, являясь частью популярных протоколов, таких как PIM (Protocol Independent Multicast — многоадресная рассылка, не зависящая от протокола) (Fenner и др., 2006).

5.2.9. Произвольная маршрутизация

До сих пор мы рассматривали такие модели предоставления информации, в которых источник отправляет сообщение на один адрес (одноадресная рассылка — unicast), на все адреса (широковещание) или группе адресов (многоадресная рассылка). Иногда используется еще одна модель под названием произвольная рассылка (anycast). При такой рассылке пакет отправляется ближайшему члену группы (Partridge и др., 1993). Методы нахождения соответствующих путей называются произвольной маршрутизацией (anycast routing).

Зачем нам может понадобиться произвольная рассылка? Иногда узлы предоставляют услугу (например, сообщают время суток или передают контент), для которой важно одно: чтобы информация была правильной; при этом не имеет значения, какой узел ее предоставил — с этой задачей справился бы любой узел. Пример использования свободной рассылки в сети Интернет — DNS, о которой мы поговорим в главе 7.

К счастью, нам не придется придумывать новые алгоритмы для произвольной маршрутизации: стандартные методы — маршрутизация по вектору расстояния и маршрутизация с учетом состояния линий — позволяют создавать маршруты для произвольной рассылки. Предположим, что нам нужно передать данные членам группы 1. Вместо различных адресов все члены группы получат одинаковый адрес — «1». Алгоритм маршрутизации по вектору расстояния распределит векторы обычным способом, и узлы выберут кратчайший путь к адресу 1. В результате узлы отправят данные на ближайшее устройство с адресом 1. Соответствующие маршруты показаны на рис. 5.16 а. Этот метод работает успешно потому, что протокол маршрутизации не знает о существовании нескольких устройств с адресом 1, а значит, он считает их всех одним узлом, как показано в топологии на рис. 5.16, б.

Рис. 5.16. Произвольная маршрутизация: а — маршруты для свободной рассылки; б — топология с точки зрения протокола маршрутизации

Такой метод будет работать и для маршрутизации с учетом состояния линий. Здесь, правда, следует добавить, что протокол маршрутизации не обязательно должен находить кажущиеся кратчайшими пути, проходящие чрез узел 1. Это привело бы к «прыжку через гиперпространство», потому что экземпляры узла 1 на самом деле расположены в различных частях сети. Однако сейчас протоколы маршрутизации с учетом состояния линий различают маршрутизаторы и хосты. Мы не говорили об этом раньше, поскольку в этом не было явной необходимости.

5.2.10. Алгоритмы маршрутизации для мобильных хостов

Миллионы людей пользуются компьютерами на ходу. Сюда относятся ситуации фактического передвижения, такие как использование беспроводных устройств в движущемся автомобиле, а также ситуации мобильного использования портативных компьютеров в нескольких разных местах. Термин мобильные хосты (mobile hosts) мы будем использовать для обозначения и тех, и других ситуаций, противопоставляя их стационарным, никогда не перемещающимся хостам. В последнее время люди все больше хотят оставаться в сети независимо от того, в какой части земного шара они находятся, и делать это так же легко, как дома. Такие мобильные хосты вызывают дополнительную сложность: чтобы направить пакет к мобильному хосту, сеть должна сначала найти его.

Здесь мы будем рассматривать модель мира, в которой у всех хостов есть постоянное домашнее местоположение( home location), которое никогда не меняется. У каждого хоста также есть постоянный домашний адрес, которым можно воспользоваться для определения домашнего местоположения, аналогично тому, как телефонный номер 1-212-5551212 обозначает США (страна с кодом 1) и Манхеттен (212). Целью маршрутизации в системах с мобильными хостами является обеспечение возможности передачи пакетов мобильным хостам с помощью их постоянных домашних адресов. При этом пакеты должны эффективно достигать хостов, независимо от их расположения. Самое сложное здесь, конечно, — найти хост.

Следует сказать несколько слов об этой модели. Существует такой вариант: можно заново вычислять маршруты каждый раз при смене местоположения хоста или при изменении топологии. Тогда можно было бы просто воспользоваться алгоритмами маршрутизации, описанными ранее в этом разделе. Однако, учитывая, насколько быстро увеличивается количество хостов, становится ясно: в результате вся сеть будет бесконечно занята вычислением новых маршрутов. Использование домашних адресов значительно упрощает задачу.

Еще один вариант — обеспечить мобильность над сетевым уровнем, как это, по сути, сейчас и происходит с переносными компьютерами. При изменении местоположения они получают новые сетевые адреса; при этом старый и новый адреса никак не связаны друг с другом — сеть даже не знает о том, что они принадлежат одному и тому же компьютеру. В этой модели с помощью переносного компьютера можно просматривать содержимое Сети, однако другие хосты не могут отправлять пакеты на данный компьютер (например, осуществлять входящий звонок) без выполнения процедуры адресации высокого уровня (например, повторного входа в Skype при смене местоположения). Более того, связь не будет поддерживаться, если хост движется: в таком случае придется устанавливать новые соединения. С этими проблемами может справиться мобильность на сетевом уровне.