Оптимизация SPF в OSPF.

Как известно, в OSPF для нахождения кратчайших intra-area маршрутов используется алгоритм Дейкстры. Он же используется и в IS-IS, тем не менее эти протоколы по разному реагируют на изменения топологии. Так, добавление нового stub-роутера или изменение/добавление ip-адреса, приводит в случае OSPF (имеем в виду v2 если не указано обратное) к полному пересчету SPT. Однако, в случае IS-IS такого не происходит. Отчего и почему рассмотрим далее.

Подобное преимущество в IS-IS достигается за счет раздельной обработки информации о топологии и IP-префиксах живущих поверх неё. Так, в IS-IS данные о IP-сетях передается в TLV 128 и TLV 130, а вся необходимая для расчета SPT в TLV 2 (IIS Neighbors). Благодаря этому IP-адреса и сети являются листьями SPT и только падение транзитного линка вызывает его перерасчет, а добавление сети влечет за собой лишь изменение в RIB. Данный механизм IS-IS называется PRC (Partial Route Calculation).

OSPF в отличии от IS-IS не разделяет информацию о сетях и топологии, передавая её совместно в LSA 1 и LSA 2. По этой причине все IP-сети внутри области считаются узлами SPF-дерева, изменение которых приводит к полному перерасчету его структуры. Если говорить о взаимодействиях с помощью LSA 3, 5, 7 - то изменения в соседних областях не вызывают перестроение SPT, а приводят только к модификации RIB. Довольно похоже на IS-IS не так ли? Всё согласно RFC 2328 (пункты 16.5 и 16.6). Cisco называет это Partial SPF.

Есть ли способ уменьшить зависимость OSPF от незначительных изменений в топологии приводящих к её полному перерасчету? Ведь в случае очень больших областей это может приводить к негативным последствиям. Одна из хитростей - объявлять наши сети через redistribute connected, что позволит механизму Partial SPF работать более эффективно. Но придется мириться с увеличением количества LSA 5 во всех областях.

Наиболее же грамотное и комплексное решение - включение iSPF (Incremental SPF) на маршрутизаторах сети. iSPF - алгоритм разработанный в 1978 году Эриком Росеном (Eric C. Rosen), позволяющий заместо полного перестроения SPT производить перерасчет только непосредственно затронутых изменением участков. Ситуациями в которым iSPF полезен, являются:

1. Добавление нового роутера, который будет являться листом по отношению к сохраненному дереву.
2. Падение линка не имеющего места в текущем дереве.
3. Падение транзитного линка приведет к частичному перерасчету SPT.

Для реализации iSPF требуется больше информации, теперь каждая нода должна хранить списки родительских и дочерних узлов. Алгоритм наиболее эффективен при изменениях в дали от вершины дерева, т.к. они затрагивают значительно меньше узлов. Однако, при падении линка вблизи к вершине - время выполнения iSPF может быть даже несколько больше чем SPF. Тем не менее, для больших сетей эффективность iSPF очень высока, его преимущество достигает 90%.