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

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

Чтобы предотвратить неограниченный рост размера списка, можно снабдить все списки счетчиком k, показывающим, что все порядковые номера вплоть до k уже встречались. И когда приходит пакет, можно очень легко проверить, был ли он уже передан, сравнивая его порядковый номер с k; при положительном ответе такой пакет отвергается. Кроме того, не нужно хранить весь список до k, поскольку этот счетчик очень действенно подытоживает его.

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

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

5.2.4. Маршрутизация по вектору расстояний

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

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

Алгоритм маршрутизации по вектору расстояний иногда называют по именам его создателей распределенным алгоритмом Беллмана—Форда (Bellman-Ford) (Bellman, 1957; Ford и Filkerson, 1962). Этот алгоритм изначально применялся в сети ARPANET и в Интернете был известен под названием RIP.

При маршрутизации по вектору расстояний таблицы, с которыми работают и которые обновляют маршрутизаторы, содержат записи о каждом маршрутизаторе сети. Каждая запись состоит из двух частей: предпочитаемый номер линии для данного получателя и предполагаемое расстояние или время прохождения пакета до этого получателя. В качестве меры расстояния можно использовать число транзитных участков или другие единицы измерения (о которых мы говорили при обсуждении длины кратчайшего пути).