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

Этот алгоритм может оказаться полезным в крупных гетерогенных корпоративных сетях, где самые старые и медленные маршрутизаторы заставляют других ждать, пока они получат обновления и учтут их в своих таблицах маршрутов. Алгоритм Approximate Link State (XL) ограничивает обновления таким образом, что их получают только те маршрутизаторы, которым эти обновления действительно нужны. Об этом сообщил профессор Стивен Севедж, вместе с учеными Калифорнийского университета в Сан-Диего разработавший данный алгоритм. Недавно Севедж представил статью, посвященную XL, на конференции Association for Computing Machinery, ознакомив с ней слушателей в процессе работы секции Special Interest Group on Data Communications.

Без алгоритма XL маршрутизаторы, как правило, существенно увеличивают объем трафика в сети за счет рассылки сообщений об обновлениях всех маршрутов, поскольку все они получают каждое такое обновление. В очень крупных сетях, где установлено значительное число маршрутизаторов, постоянная рассылка и обработка изменений периодически тормозит их работу.

"Такие обновления могут относиться лишь к отдельным сегментам сети", - отметил Севедж. Воспользовавшись аналогией с географической картой, чтобы проиллюстрировать свою точку зрения, он пояснил, что водителя на Восточном побережье мало заботит тот факт, что на трассе № 5 в городе Портленд штата Орегон возникла пробка. "Но если прибегать к этой метафоре, мы должны сообщить о подобном событии всем компонентам сети", - пояснил Севедж.

Чтобы решить подобную проблему, в крупных сетях вручную создаются выделенные области, изолированные группы маршрутизаторов, ограничивающие число устройств, которым нужно передавать такую информацию. Маршрутизаторы по-прежнему ее получают, но только в пределах своих областей.

По мнению Севеджа, алгоритм XL способен избавить от необходимости вручную конфигурировать такие области. Более того, каждый маршрутизатор может автоматически определить, какие именно другие маршрутизаторы ему нужны в рамках обновлений, как связаться со всеми адресатами и избежать возникновения петель, формирующих "черные дыры" для пакетов.

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

Если не нужно, то маршрутизатор "вычеркивает" такое обновление и не транслирует его. В результате обновления пересылаются только в те ближайшие области, на которые оказывает влияние изменение топологии, а распространение служебной информации становится менее обременительным для трафика.

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

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

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

Новый алгоритм совместим с технологиями маршрутизации Intermediate System-to-Intermediate System и Open Shortest Path First. А это значит, что поддерживающее его программное обеспечение можно устанавливать в масштабах всей сети постепенно и что оно будет работать с существующими протоколами маршрутизации. Самое главное, по словам Севеджа, - оптимизировать маршруты на основе таких заданных параметров, как время задержки или полоса пропускания.

Для широкого распространения и практического внедрения алгоритма XL необходимо, чтобы производители маршрутизаторов интегрировали его в свое программное обеспечение. "Нужно, чтобы XL одобрили производители. Если его выберет Cisco, это окажет на всех заметное влияние", - считает Севедж.

Он уже представил описание алгоритма компании Cisco, которая помогала финансировать его исследования через Center for Network Systems.