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

5.2.7. Широковещательная маршрутизация

В некоторых приложениях хостам требуется посылать сообщения на множество хостов или даже на все сразу. Можно привести такие примеры, как распространение прогнозов погоды, обновление биржевых курсов ценных бумаг, радиопрограммы в прямом эфире. Эффективнее всего отправлять соответствующие данные широковещательным способом, предоставляя возможность получить их всем заинтересованным хостам. Итак, широковещанием (broadcasting) называется рассылка пакетов по всем пунктам назначения одновременно. Для ее реализации применяются разнообразные методы.

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

Один из более совершенных алгоритмов называется многоадресной маршрутизацией (multidestination routing), при которой в каждом пакете содержится либо список адресатов, либо битовая карта, показывающая предпочитаемые хосты назначения. Когда такой пакет прибывает в маршрутизатор, последний проверяет список, содержащийся в пакете, определяя набор выходных линий, которые потребуются для дальнейшей рассылки. (Линия может потребоваться в том случае, если она входит в оптимальный путь к какому-то из адресатов списка.) Маршрутизатором создается копия пакета для каждой из используемых исходящих линий. В нее включаются только те адресаты, для доступа к которым требуется данная линия. Таким образом, весь список рассылки распределяется между исходящими линиями. После определенного числа пересылок каждый из пакетов будет содержать только один адрес назначения, как и обычный пакет. Многоадресная маршрутизация подобна использованию индивидуально адресуемых пакетов с той разницей, что в первом случае из нескольких пакетов, следующих по одному и тому же маршруту, только один «платит полную стоимость», а остальные едут бесплатно. В таком случае пропускная способность используется более эффективно. Однако этот метод все же требует начальных сведений обо всех адресах назначения, и, кроме того, чтобы понять, куда отправить один многоадресный пакет, маршрутизатор должен выполнить столько же действий, сколько и при отправке набора отдельных пакетов.

Мы уже знакомы с еще одним методом широковещательной маршрутизации: заливкой. Если заливка реализована с помощью порядковых номеров, она эффективно работает с каналами связи, поскольку маршрутизаторы используют относительно простое правило принятия решения. Хотя этот метод плохо подходит для обычных двухточечных соединений, он может быть хорошим претендентом для широковещания. Но оказывается, что ситуация может быть еще лучше, если кратчайшие пути для стандартных пакетов уже вычислены.

Идея продвижения по встречному пути (reverse path forwarding) замечательно проста и изящна (Dadal, Metcalfe, 1978). Когда прибывает широковещательный пакет, маршрутизатор проверяет, используется ли та связь, по которой он прибыл, для нормальной передачи пакетов источнику широковещания. В случае положительного ответа велика вероятность того, что широковещательный пакет прибыл по наилучшему маршруту и является, таким образом, первой копией, прибывшей на маршрутизатор. Тогда маршрутизатор рассылает этот пакет по всем связям, кроме той, по которой он прибыл. Однако если широковещательный пакет прибывает от того же источника по другой связи, он отвергается как вероятный дубликат.

Рис. 5.13. Продвижение по встречному пути: а — сеть; б — входное дерево; в — дерево, построенное методом продвижения по встречному пути

Пример работы алгоритма продвижения по встречному пути показан на рис. 5.13. Слева изображена сеть, посередине — входное дерево для маршрутизатора I этой сети. На первом транзитном участке маршрутизатор I посылает пакеты маршрутизаторам F, H, J и N, являющимся вторым ярусом дерева. Все эти пакеты прибывают к ним по предпочитаемым линиям до I (по пути, совпадающему с входным деревом), что обозначается кружками вокруг символов на рис. 5.13, в. На втором этапе пересылки формируются восемь пакетов — по два каждым маршрутизатором, получившим пакет после первой пересылки. Все восемь пакетов попадают к маршрутизаторам, не получавшим ранее пакетов, а пять из них приходят по предпочитаемым линиям. Из шести пакетов, формируемых на третьем транзитном участке, только три прибывают по предпочитаемым линиям (на маршрутизаторы C, E и K). Остальные оказываются дубликатами. После пяти транзитных участков широковещание заканчивается с общим количеством переданных пакетов, равным 23, тогда как при использовании входного дерева потребовалось бы 4 транзитных участка и 14 пакетов.