Диана Ильенко

задавать метрику расстояния или стоимости связи с каждым из своих соседей; 3)    создавать пакет, содержащий всю собранную информацию; 4)    посылать этот пакет всем маршрутизаторам и принять все пакеты, отправленные другими маршрутизаторами; 5)    вычислять кратчайший путь ко всем маршрутизаторам. В результате каждому маршрутизатору высылается полная топология. После этого для обнаружения кратчайшего пути ко всем остальным маршрутизаторам каждый маршрутизатор может использовать алгоритм Дейкстры. Ниже мы рассмотрим каждый из этих пяти этапов более подробно. Знакомство с соседями Когда маршрутизатор загружается, его первая задача состоит в получении информации о своих соседях...

единицу превышающее минимальное значение этого расстояния, хранящееся у его соседей. Таким образом, все маршрутизаторы будут до бесконечности увеличивать значение расстояния до выключенного маршрутизатора. Количество необходимых для завершения этого процесса обменов векторами можно ограничить, если установить значение этой «бесконечности» равным длине самого длинного пути плюс 1. Неудивительно, что эта проблема называется счетом до бесконечности (count-to-infinity). Было сделано много попыток решить ее, например можно запретить маршрутизатору сообщать о своих кратчайших путях соседям, от которых...

Проблема счета до бесконечности Когда в сети появляется A, остальные маршрутизаторы узнают об этом с помощью обмена векторами. Для простоты будем предполагать, что где-то в сети имеется гигантский гонг, в который периодически ударяют, чтобы инициировать одновременный обмен векторами. После первого обмена B узнает, что у его соседа слева нулевая задержка при связи с A, а B помечает в своей таблице маршрутов, что A находится слева на расстоянии одного транзитного участка. Все остальные маршрутизаторы в этот момент еще полагают, что A выключен. Значения задержек для A в таблицах на этот момент показаны во второй строке на рис...

Установление маршрутов, соответствующих кратчайшим путям, в сети называется конвергенцией (convergence). Алгоритм маршрутизации по вектору расстояний — простой метод, позволяющий маршрутизаторам совместно вычислять кратчайшие пути. Однако на практике он обладает серьезным недостатком: хотя правильный ответ в конце концов и находится, процесс его поиска может занять довольно много времени. В частности, такой алгоритм быстро реагирует на хорошие новости и очень лениво — на плохие. Рассмотрим маршрутизатор, для которого расстояние до маршрутизатора X достаточно велико. Если при очередном обмене векторами...

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

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

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

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

Теперь мы повторяем ту же процедуру с узлом B, исследуя все его соседние узлы. Если сумма расстояния от узла B и значения отметки в узле B (расстояния от A до B) оказывается меньше, чем отметка у исследуемого узла (уже найденное другим путем расстояние от A), это значит, что найден более короткий путь, поэтому пометка узла изменяется. После того как все соседние с рабочим узлы исследованы и временные отметки при необходимости изменены, по всему графу ищется узел с наименьшей временной отметкой. Этот узел помечается как постоянный и становится текущим рабочим узлом. На рис. 5.6 показаны первые шесть этапов работы алгоритма...

Первые шесть шагов вычисления кратчайшего пути от A к D. Стрелка указывает на рабочий узел Известно несколько алгоритмов вычисления кратчайшего пути между двумя узлами графа. Один из них был создан знаменитым Дейкстрой (Dijkstra) в 1959 году. Он находит кратчайшие пути между отправителем и всеми возможными адресами назначения в данной сети. Каждый узел помечается (в скобках) расстоянием до него от узла отправителя по наилучшему известному пути. Эти расстояния должны быть неотрицательными; если они основаны на реальных величинах — таких как пропускная способность и время задержки, — это условие будет выполнено...