Первоисточник: Бертсекас Д., Галлагер Р. Сети передачи данных: Пер с англ. – М.: Мир, 1989 г. - 544с.
Надёжное получение маршрутной информации в местах, где она необходима, в условиях, когда линии могут выходить из строя, сопряжено с рядом тонкостей.
Некоторые из них:
Информация о топологических изменениях должна передаваться по линиям, которые могут выходить из строя. В некоторых сетях необходимо уметь поддерживать их функционирование, даже когда некоторые части сети становятся несвязанными друг с другом. Например, централизованный алгоритм, в котором вся информация, касающаяся топологических изменений, передается в специальный узел, называемый центром управления сети (ЦУС). ЦУС хранит в памяти маршрутные таблицы всей системы и обновляет их после получения новой информации о топологических изменениях, используя некоторый алгоритм, которой сейчас не важен. После этого он приступает к передаче всей информации, необходимой для выполнения локальных операций по маршрутизации, всем узлам, которым эта информация адресована. Помимо основных задач сбора и распределения информации по линиям, которые могут выходить из строя, перед алгоритмом стоит ещё одна проблема – возможность выхода из строя ЦУС или потери его связи с какой-либо частью сети. В одних случаях удаётся за счёт избыточности сделать вероятность появления таких ситуаций очень малой. В других случаях стоит вообще отказаться от централизованного подхода и использовать распределённый алгоритм.
Приходится иметь дело с многократными топологическими изменениями (смена статуса линии с действующей на вышедшую из строя и обратно в течении короткого времени) и поэтому возникает проблема различения старой и новой информации об изменениях. Например, метод распространения среди всех узлов информации о топологических изменениях, называемый лавинным алгоритмом. Суть этого метода в том, что каждый узел следит за статусом всех уходящих от него линий и после обнаружения изменения статуса какой-либо линии посылает пакет всем своим соседям, сообщая им об этом изменении. Соседи, пересылают этот пакет своим соседям и т.д. Необходимо предпринять некоторые меры, для того чтобы этот обновляющий пакет не циркулировал по сети бесконечно долго. Лавинный алгоритм работает, когда имеется одно топологическое изменение, и может оказаться непригодным, когда возможны многократные изменения.
Обновляющая информация о топологических изменениях используется некоторым алгоритмом, вычисляющим новые маршрутные пути (например, алгоритмом отыскания кратчайшего пути). Возможно, что обновляющая информация о топологических изменениях поступит во время работы алгоритма. Тогда алгоритм должен суметь либо в ходе своей работы учитывать эти изменения, либо остановиться и заново начать действовать после получения новых данных.
В результате восстановления какой-либо линии, две несвязные части сети могут снова оказаться связанными. Каждая из частей, возможно, имеет устаревшую информацию о топологии другой части. Алгоритм должен гарантировать, что в конечном итоге обе части согласуются и им станет известна правильная топология сети.
Неправильная информация о перегрузках обычно имеет менее серьезные последствия, чем неправильная информация о топологи. Если в первом случае худшее, что можно ожидать – это не лучший выбор маршрутов, то во втором случае можно выбрать вообще несуществующие маршруты. Поэтому если алгоритм распространяет информацию о нагрузках, а не о топологии, то можно позволить допустить небольшой уровень ошибок, если это приведет к существенному упрощению алгоритма или уменьшает объем передач по сети.
Невозможно сделать так чтобы каждый узел в любой момент времени знал истинную топологию сети. Поэтому лучшее, что можно ожидать от алгоритма – это, что он сможет успешно справляться с любым конечным числом топологических изменений в течение конечного времени. Т.е. если до какого-либо момента времени произошло конечное число изменений и после этого никаких изменений не было, то все узлы каждой связной области сети должны узнать правильный статус каждой линии данной области в течении конечного интервала времени.
При обсуждении свойств различных схем в описанном выше смысле предлагается следующее:
По линиям сети сообщения передаются и с сохранением очередности. В узлах сообщения хранятся в памяти без искажений.
Выход из строя линий обнаруживается в обоих ее концевых узлах, хотя не обязательно одновременно, т.е. если какой-либо концевой узел объявляет, что линия вышла из строя, то второй концевой узел также объявляет, что данная линия снова вошла в строй.
Имеется некоторый протокол линий передачи данных для регистрации на концах вышедшей из строя линий момента времени, когда данная линия станет действовать снова. Если один из концевых узлов объявляет, что данная линия вошла в строй, то в течении конечного интервала времени либо противоположный концевой узел также объявит, что эта линия вошла в строй, либо первый узел объявит, что эта линия снова вышла из строя.
Узел может выйти из строя и в этом случае каждая из примыкающих к нему линий объявляется вышедшей из строя; это объявляется узлом на противоположном конце линии в течении конечного интервала времени.
В дополнении к анализу обычного случая, когда эти предположения выполняются, необходимо также учитывать последствия исключительного случая, когда эти предположения нарушаются. Обновление топологии является алгоритмом низкого уровня, на котором основывается правильная работа данных алгоритмов.
Алгоритм обновления топологии вместе с некоторым протоколом восстановления линий должен быть способен восстанавливать сети из состояния, в котором все линии вышли из строя.