Сравнение алгоритмов маршрутизации
Перед рассмотрением других алгоритмов маршрутизации дадим краткое сравнение некоторых характеристик алгоритма, основанного на состоянии линий, и дистанционно-векторного алгоритма.
□ Сложность сообщений. Как мы видели, алгоритм, основанный на состоянии линий, требует от каждого узла знания стоимости каждой линии сети. Для этого необходимо отправить 0(пЕ) сообщений, где п представляет собой количество узлов сети, а Е — число линий. Кроме того, каждый раз, когда стоимость линии изменяется, об этом следует известить все узлы. Дистанционно-векторный алгоритм требует обмена сообщениями только между напрямую соединенными узлами на каждой итерации. Как было показано, время, необходимое для схождения алгоритма, может зависеть от многих факторов. Когда изменяется стоимость линии, дистанционно-векторный алгоритм распространяет результаты только в том случае, если это изменение приводит к изменению пути с наименьшей стоимостью для одного из узлов, присоединенного к этой линии.
□ Скорость схождения. Как мы видели, количество вычислений в нашей реализации алгоритма, основанного на состоянии линий, растет пропорционально квадрату узлов сети, требуя передачи 0(пЕ) сообщений. Дистанционно-векторный алгоритм может сходиться медленно (в зависимости от относительной стоимости путей, как было показано в примере на рис. 4.10), и во время схождения могут образовываться маршрутные петли. Кроме того, дистанционно-векторный алгоритм страдает от «приступов» счета до бесконечности.
□ Живучесть. Что может случиться, если маршрутизатор выйдет из строя, «сойдет с ума» или объявит забастовку? В алгоритме маршрутизации, основанном на состоянии линий, маршрутизатор может передать всем остальным маршрутизаторам неверные сведения о стоимости одной из присоединенных к нему линий. Узел может также повредить или потерять один из широковещательных пакетов LS-алгоритма, который он получил. Но узел рассчитывает только собственную таблицу продвижения данных. Остальные узлы сами вычисляют свои таблицы. Это означает, что в алгоритме, основанном на состоянии линий, расчеты маршрутов выполняются в значительной степени раздельно, что предоставляет определенную степень живучести. В случае дистанционно-векторного алгоритма узел может передать другим узлам неверно сосчитанные им значения минимальной стоимости путей. (Такие ситуации встречаются на практике. В 1997 году неисправный маршрутизатор, принадлежащий небольшой компании, занимающейся предоставлением доступа в Интернет, снабжал маршрутизаторы национальной магистрали ошибочной информацией о маршрутах. Это привело к тому, что другие маршрутизаторы завалили трафиком неисправный маршрутизатор, в результате большие фрагменты Интернета в течение нескольких часов были отрезаны.) Обратите внимание, что в дистанционно-векторном алгоритме на каждой итерации результаты вычислений узла непосредственно передаются соседнему узлу, а затем на следующей итерации они попадают к соседу соседа и т. д. Таким образом, в дистанционно-векторном алгоритме некорректно вычисленные данные могут распространиться по всей сети.
В заключение скажем, что ни один алгоритм нельзя считать «победителем». Как мы увидим в разделе «Маршрутизация в Интернете», в Интернете применяются оба эти алгоритма.