Курсовые и лабораторные работы Математика решение задач Электротехника Лабораторные работы по электронике Физика Информатика На главную
Реализация сервиса виртуальные каналы Алгоритмы маршрутизации Метод заливки Маршрутизация Иерархическая маршрутизация Широковещательная маршрутизация Многоадресная рассылка Борьба с флуктуациями

Этот алгоритм приведен в листинге 5.1. Глобальные переменные n и dist описывают граф и инициализируются раньше, чем вызывается shortest_path. Единственное отличие программы от описанного выше алгоритма заключается в том, что вычисление кратчайшего пути в программе начинается не от узла-источника s, а от конечного узла t. Поскольку в однонаправленном графе кратчайший путь от t к s тот же самый, что и от s к t, не имеет значения, с какого конца начинать. (Если только не существует несколько кратчайших путей. В таком случае, двигаясь в противоположном направлении, мы можем обнаружить другой путь.) Причина поиска пути в обратном направлении заключается в том, что каждый узел помечается предшествующим узлом, а не следующим. Когда найденный путь копируется в выходную переменную path, он инвертируется. С помощью реверсивного поиска убирается неправильность направления поиска, и мы получаем путь, идущий в нужную сторону.

Заливка

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


Общие сведения о пересечении поверхности плоскостью
Сетевой уровень Управление доступом У каждого хоста и маршрутизатора в Интернете есть IP-адрес