Лавинный алгоритм без периодических обновлений

Простая схема предложения П. Умбле повышает надежность основной идеи использования порядковых номеров посредством введения некоторого механизма борьбы с последствиями выхода из строя узлов и ошибок при передаче. Но она требует, чтобы поле порядковых номеров было достаточно простым, т.е. никогда не происходило переполнение. Идея состоит в изменении лавинного алгоритма таким образом, чтобы удобнее было преодолевать трудности, возникающие после воссоединения несвязных компонентов сети.

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

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

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

Чтобы схема работала правильно, в лавинном алгоритме изменим правила, когда обновляющее сообщение сбрасывается. Для этого для каждого узла i упорядочим обновляющие сообщения о топологии, генерируемые в узле i. О двух таких сообщениях А и В говорят, что А>В, если порядковый номер А больше чем В или сети порядковые номера у А и В совпадают, но содержимое А больше содержимого В в соответствии с некоторым лексикографическим правилом. Т.о., любые два сообщения А и В, генерированные в одном и том же узле, можно сравнивать между собой, чтобы определить А>B, B>A или А=В. Последнее соотношение имеет место только тогда, и порядковые номера, и содержимое А и В идентичны.

Предположим, что узел J получил обновляющие сообщения А, генерированное в узле i, а в это время в памяти узла J хранится генерированное в узле i сообщение В. Сообщение А сбрасывается, если А<В или А=В. Если А>В то, лавинный алгоритм руководствуется теперь следующим правилом:

1. Если J != i , то узел J записывает А вместо В в своей памяти и пересылает копию А по всем своим смежным линиям, за исключением той, по которой пришло А.
2. Если J=i (т.е. узел i получил сообщение которое он сам генерировал ранее), то узел i посылает всем своим соседям обновляющее сообщение, содержащее текущий статус всех своих уходящих линий вместе с порядковым номером, превышающим порядковый номер А на 1.

Чтобы увидеть, почему необходимо сравнивать содержимое А и В в случае, когда их порядковые номера совпадают.

Рассмотрим пример: Пусть три узла 1,2 и 3 соединены в тандем с двумя (неориентированными) линиями (1,2) и (2,3). Предположим, что в начале обе линии функционируют исправно и сообщения, хранящиеся в памяти всех узлов, содержат правильную информацию о статусе линий и имеют порядковые номера равные 0. Пусть выходит из строя линия ( 2,3), затем линия (1,2), а после этого линия (2,3) восстанавливается и узел 2 устанавливает свой порядковый номер равный 0. В этих условиях узлы 2 и 3 обмениваются своими (противоречивыми) сведениями о статусе ориентированных линий (1,2) и (2,1). Но если бы использовался прежний лавинный алгоритм, то оба узла сбросили бы эти обновляющие сообщения, полученные друг от друга, т.к. у этих сообщений нулевые порядковые номера, т.е. такие же, как у сообщений, хранящихся в их памяти.

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

Рассмотренный алгоритм имеет недостаток: он чувствителен к ошибкам, возникающим в памяти и при передаче. Если, например, порядковый номер в результате ошибки при передаче или хранении в памяти изменился и стал очень большим, то может случится так, что все последующие генерируемые узлом сообщения будут игнорироваться, пока их порядковые номера не превысят ошибочный номер, хранящийся в памяти некоторых узлов. Этот недостаток устраняется путем модификации, суть которой в том, что если узел J получает А, а в его памяти хранится В, такое, что А<В, то сообщение А, как и раньше, сбрасывается, но в дополнение к этому узел посылает сообщение В обратно тому соседу, от которого было получено сообщение А (сосед затем разошлет В дальше по сети). Пусть теперь узел разослал обновляющее сообщение с порядковым номером, меньшим, чем порядковый номер, хранящийся на некотором другом узле. Тогда благодаря только что описанной модификации, если два узла можно соединить путем из действующих линий, то больший порядковый номер (скажем к) обязательно вернется в узел, сгенерировавший его, который сможет затем сгенерировать обновляющее сообщение с порядковым номером к+1 в соответствии с описанным выше правилом 2. но остается проблема, связанная с возможностью переполнения поля порядкового номера (например, если к является максимальным числом, которое можно записать в поле порядкового номера). Остается и проблема, связанная с искажением обновляющих сообщений (а не только его порядкового номера) в результате ошибок при передаче или хранении в памяти. Простым способом решения этой проблемы является применение специально предназначенных для устранения подобных ошибок схем, использующих поле возраста и периодические обновления.