Prioritized Treatment of Specific OSPF Version 2 Packets and Congestion Avoidance
RFC 4222 описывает рекомендуемые методы повышения масштабируемости и устойчивости крупных сетей с OSPFv2 при перегрузке управляющего трафика, в частности во время «штормов» LSA. Основная рекомендация состоит в приоритетной обработке пакетов Hello и подтверждений Link State Acknowledgement по сравнению с прочими пакетами OSPF с учётом ограничений криптографической аутентификации. Документ также предлагает альтернативный сброс таймера неактивности, экспоненциальную задержку повторных передач LSA, неявное выявление перегрузки у соседей и ограничение числа одновременно поднимаемых смежностей. Эти меры направлены на сокращение повторных передач, предотвращение потери смежностей из-за задержки Hello и управляемый выход из состояния перегрузки.
Рабочая группа сети G. Choudhury, ред.
Запрос комментариев: 4222 AT&T
BCP: 112 Октябрь 2005
Категория: Лучшая современная практика
Приоритетная обработка отдельных пакетов OSPF версии 2
и предотвращение перегрузки
Статус настоящего меморандума
Этот документ определяет Internet Best Current Practices для
интернет-сообщества и запрашивает обсуждение и предложения по
улучшению. Распространение этого меморандума не ограничено.
Уведомление об авторских правах
Авторское право (C) The Internet Society (2005).
Аннотация
Этот документ рекомендует методы, предназначенные для улучшения
масштабируемости и стабильности крупных сетей, использующих протокол
Open Shortest Path First (OSPF) версии 2. Эти методы включают обработку
пакетов OSPF Hello и подтверждений Link State Advertisement (LSA) с более
высоким приоритетом по сравнению с другими пакетами OSPF, а также другие
процедуры предотвращения перегрузки.
Содержание
1. Введение.......................................................2
2. Рекомендации...................................................3
3. Вопросы безопасности...........................................6
4. Благодарности..................................................6
5. Нормативные ссылки.............................................6
6. Информативные ссылки...........................................7
Приложение A. Шторм LSA: причины и влияние.......................8
Приложение B. Список переменных и значений......................10
Приложение C. Другие рекомендации и предложения.................11
Choudhury, ред. Лучшая современная практика [Страница 1]
RFC 4222 Приоритетная обработка Октябрь 2005
1. Введение
В настоящем документе OSPF означает OSPFv2 [Ref1]. Описанные здесь методы
улучшения масштабируемости и стабильности также могут применяться к
OSPFv3 [Ref2], но для этого потребуются дальнейшее изучение и опыт
эксплуатации.
В крупной сети, работающей по протоколу OSPF, иногда может происходить
одновременное или почти одновременное обновление большого числа объявлений
о состоянии канала, или LSA. Это особенно характерно при использовании
расширения OSPF для управления трафиком [Ref3], которое может значительно
увеличить число LSA в сети. Мы называем такое событие штормом LSA; оно
может быть вызвано незапланированным отказом или плановым событием
технического обслуживания. Отказ может иметь аппаратный, программный или
процедурный характер.
Шторм LSA приводит к высокой загрузке процессора и памяти на маршрутизаторе,
вследствие чего входящие пакеты задерживаются или отбрасываются. Задержанные
подтверждения (сверх значения таймера повторной передачи) приводят к
повторным передачам, а задержанные пакеты Hello (сверх интервала
router-dead) приводят к объявлению смежностей с соседями неработоспособными.
Повторные передачи и дополнительное создание LSA приводят к дальнейшему
потреблению процессора и памяти, по существу вызывая петлю положительной
обратной связи, которая в предельном случае может привести сеть в
нестабильное состояние.
Значение по умолчанию для таймера повторной передачи составляет 5 секунд,
а для интервала router-dead — 40 секунд. Однако в последнее время возник
большой интерес к существенному сокращению времени сходимости OSPF. В рамках
этого плана были предложены гораздо более короткие (менее секунды) интервалы
Hello и router-dead [Ref4]. В таком сценарии будет более вероятно, что
пакеты Hello будут задерживаться сверх интервала router-dead во время
перегрузки сети, вызванной штормом LSA.
Для улучшения масштабируемости и стабильности сетей мы рекомендуем меры по
приоритизации критически важных пакетов OSPF и предотвращению перегрузки.
Подробности рекомендаций приведены в разделе 2. В [Ref13] описано
имитационное исследование, количественно характеризующее явление перегрузки
и его влияние. В нём также исследуются несколько рекомендаций и показано,
что они действительно улучшают масштабируемость и стабильность сетей,
использующих протокол OSPF. [Ref13] предоставляется по запросу при
обращении к редактору или одному из авторов.
Choudhury, ред. Лучшая современная практика [Страница 2]
RFC 4222 Приоритетная обработка Октябрь 2005
В приложении A более подробно объясняются сценарии шторма LSA, их влияние,
а также приводится несколько реальных примеров штормов управляющих
сообщений. Приложение B содержит список переменных, используемых в
рекомендациях, и их примеры значений. Приложение C содержит несколько
дополнительных рекомендаций и предложений со сходными целями.
2. Рекомендации
Приведённые ниже рекомендации предназначены для улучшения масштабируемости
и стабильности крупных сетей, использующих протокол OSPF. В периоды
перегрузки сети они уменьшили бы количество повторных передач,
предотвратили бы объявление смежности неработоспособной из-за задержки
пакетов Hello сверх RouterDeadInterval и предприняли бы другие меры по
предотвращению перегрузки. Рекомендации не упорядочены, кроме того, что
рекомендацию 2 следует реализовывать только в случае, если рекомендация 1
не реализована.
(1) Классифицируйте все пакеты OSPF на два класса: класс «высокого
приоритета», включающий пакеты OSPF Hello и пакеты Link State
Acknowledgement, и класс «низкого приоритета», включающий все прочие
пакеты. Классификация выполняется путём изучения заголовка пакета OSPF.
При приёме пакета от соседа и при передаче пакета соседу старайтесь
обработать пакет «высокого приоритета» раньше пакета «низкого
приоритета».
Приоритетная обработка при передаче может привести к тому, что пакеты
OSPF от соседа будут приняты не по порядку. Если используется
Cryptographic Authentication (AuType = 2) (как определено в [Ref1]),
то последовательные принятые действительные пакеты OSPF от соседа
должны иметь неубывающий «Cryptographic sequence number». Для
соблюдения этого требования мы рекомендуем, чтобы при использовании
Cryptographic Authentication (AuType = 2) [Ref1] приоритетная обработка
не выполнялась у передатчика. Это позволит избежать прибытия пакетов к
приёмнику не по порядку. Однако после завершения обработки безопасности
у приёмника (включая проверку номера последовательности) пакеты OSPF
могут помещаться в очередь «высокого приоритета» или очередь «низкого
приоритета» в зависимости от их класса и обрабатываться
соответствующим образом. Польза от приоритетной обработки явно выше при
отсутствии Cryptographic Authentication, поскольку в таком случае
приоритизация может быть реализована как у передатчика, так и у
приёмника. Однако даже при Cryptographic Authentication будет полезно
иметь приоритизацию только у приёмника (после обработки безопасности).
(2) Если рекомендация 1 не может быть реализована, то сбрасывайте таймер
неактивности для смежности всякий раз, когда по этой смежности получен
любой одноадресный пакет OSPF или любой пакет OSPF, отправленный на
AllSPFRouters по двухточечной линии связи, вместо сброса таймера
неактивности только при получении пакета Hello. Таким образом, OSPF
объявлял бы смежность неработоспособной, только если в течение периода,
равного или превышающего RouterDeadInterval, по этой смежности не было
получено одноадресных пакетов OSPF или пакетов OSPF, отправленных на
AllSPFRouters по двухточечной линии связи. Причина, по которой это
предложение не рекомендуется совместно с рекомендацией 1, состоит в
предотвращении возможных нежелательных побочных эффектов. Одним из
таких эффектов является задержка обнаружения неработоспособного
состояния смежности в случае, когда пакеты Hello высокого приоритета не
принимаются, но таймер неактивности сбрасывается другими устаревшими
пакетами в очереди низкого приоритета.
(3) Используйте алгоритм экспоненциальной отсрочки для определения значения
интервала повторной передачи LSA (RxmtInterval). Пусть R(i)
представляет значение RxmtInterval, используемое при i-й повторной
передаче LSA. Используйте следующий алгоритм для вычисления R(i).
R(1) = Rmin
R(i+1) = Min(KR(i),Rmax) for i>=1
где K, Rmin и Rmax — константы, а функция Min(.,.) представляет
минимальное значение двух своих аргументов. Примерами значений K, Rmin
и Rmax могут быть соответственно 2, 5 и 40 секунд. Обратите внимание,
что пример значения Rmin, начального интервала повторной передачи,
совпадает с примером значения RxmtInterval в [Ref1].
Эта рекомендация основана на наблюдении, что во время события перегрузки
сети, вызванного управляющими сообщениями, одним из главных источников
поддержания перегрузки являются повторные передачи LSA. Использование
алгоритма экспоненциальной отсрочки для интервала повторной передачи
LSA снижает частоту повторных передач LSA, пока сеть испытывает
перегрузку (во время которой более вероятны многократные повторные
передачи одного и того же LSA). Это, в свою очередь, помогает сети
выйти из состояния перегрузки.
(4) Неявное обнаружение перегрузки и действия на его основе: если на
маршрутизаторе имеется перегрузка управляющими сообщениями, его соседи
не знают об этом явно. Однако они могут неявно обнаружить её по числу
неподтверждённых LSA, направленных этому маршрутизатору. Если это число
превышает определённую «верхнюю отметку», то частоту, с которой LSA
отправляются этому маршрутизатору, следует постепенно снижать с помощью
механизма экспоненциальной отсрочки, но не ниже определённой минимальной
частоты. В дальнейшем, если число неподтверждённых LSA, направленных
этому маршрутизатору, опустится ниже определённой «нижней отметки», то
частоту отправки LSA этому маршрутизатору следует постепенно повышать,
вновь с помощью механизма экспоненциальной отсрочки, но не выше
определённой максимальной частоты. Полный алгоритм приведён ниже.
Обратите внимание, что этот алгоритм применяется независимо к каждому
соседу и только для одноадресных LSA, отправляемых соседу, либо LSA,
отправляемых на AllSPFRouters по двухточечной линии связи.
Пусть:
U(t) = Число неподтверждённых LSA, направленных соседу в момент времени t.
H = Верхняя отметка (в единицах числа неподтверждённых
LSA).
L = Нижняя отметка (в единицах числа неподтверждённых LSA).
G(t) = Интервал между отправкой последовательных LSA соседу в момент
времени t.
F = Коэффициент, на который указанный выше интервал увеличивается во
время перегрузки и уменьшается после выхода из перегрузки.
T = Минимальное время, которое должно пройти, прежде чем существующий
интервал будет рассматриваться для изменения.
Gmin = Минимально допустимое значение интервала.
Gmax = Максимально допустимое значение интервала.
Приведённое ниже уравнение показывает, как должен изменяться интервал
после истечения времени T с момента последнего изменения:
_
|
| Min(FG(t),Gmax) if U(t+T) > H
G(t+T) = | G(t) if H >= U(t+T) >= L
| Max(G(t)/F,Gmin) if U(t+T) < L
|_
Min(.,.) и Max(.,.) представляют соответственно минимальное и
максимальное значения двух аргументов.
Примеры значений различных параметров алгоритма таковы: H = 20, L = 10,
F = 2, T = 1 секунда, Gmin = 20 ms, Gmax = 1 секунда.
Рекомендации 3 и 4 обе замедляют отправку LSA перегруженным соседям на
основе неявного обнаружения перегрузки, но имеют существенные различия.
Рекомендация 3 постепенно замедляет последовательные повторные передачи
одного и того же LSA, тогда как рекомендация 4 постепенно замедляет все
LSA (новые или повторно передаваемые), направляемые перегруженному
соседу.
(5) Ограничение числа одновременно устанавливаемых смежностей: если
маршрутизатор пытается одновременно установить смежность с большим
числом своих соседей, то это может вызвать серьёзную перегрузку из-за
действий по синхронизации базы данных и рассылке LSA. Рекомендуется,
чтобы в такой ситуации одновременно устанавливалось не более «n»
Choudhury, ред. Лучшая современная практика [Страница 5]
RFC 4222 Приоритетная обработка Октябрь 2005
смежностей. После успешного установления подмножества смежностей могут
устанавливаться новые смежности, если число одновременно устанавливаемых
смежностей не превышает «n». Подходящее значение «n» будет зависеть от
вычислительной мощности маршрутизатора, общей полосы пропускания,
доступной для трафика плоскости управления, и задержки распространения.
Значение «n» следует сделать настраиваемым.
При наличии ограничения важным вопросом является порядок формирования
смежностей. Мы рекомендуем политику First Come First Served (FCFS),
основанную на порядке поступления запросов на формирование смежности.
Запросы могут поступать от соседей либо генерироваться самим
маршрутизатором. Среди самостоятельно сгенерированных запросов для
определения порядка, в котором должны выполняться запросы, может
использоваться список приоритетов. Однако после начала процесса
формирования смежности он не должен прерываться, за исключением
необычных обстоятельств, таких как ошибки или истечение времени
ожидания. В некоторых приведённых выше рекомендациях мы ссылаемся на соединения
точка-точка. Эти ссылки также должны включать случаи, когда широковещательная
сеть должна рассматриваться как соединение точка-точка с точки зрения
IP-маршрутизации [Ref5]
3. Соображения безопасности
Эта памятка не создаёт никаких новых проблем безопасности для протокола
OSPF.
4. Благодарности
Мы хотели бы выразить признательность за поддержку и полезные замечания
председателям рабочей группы OSPF Rohit Dube, Acee Lindem и John Moy;
директорам области маршрутизации Alex Zinin и Bill Fenner; а также
рецензентам IESG. Мы выражаем признательность Vivek Dube, Mitchell Erblich,
Mike Fox, Tony Przygienda и Krishna Rao за замечания к предыдущим версиям
документа. Мы также выражаем признательность Margaret Chiosi, Elie Francis,
Jeff Han, Beth Munson, Roshan Rao, Moshe Segal, Mike Wardlow и Pat Wirth за
сотрудничество и поддержку в наших усилиях по повышению масштабируемости
сетей на основе протоколов состояния каналов.
5. Нормативные ссылки
[Ref1] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
[Ref2] Coltun, R., Ferguson, D., and J. Moy, "OSPF for IPv6", RFC
2740, December 1999.
Choudhury, Ed. Лучшая современная практика [Страница 6]
RFC 4222 Приоритетная обработка Октябрь 2005
6. Справочные ссылки
[Ref3] Katz, D., Kompella, K., and D. Yeung, "Traffic Engineering
(TE) Extensions to OSPF Version 2", RFC 3630, September 2003.
[Ref4] C. Alaettinoglu, V. Jacobson and H. Yu, "Towards Millisecond
IGP Convergence", Work in Progress.
[Ref5] N. Shen, A. Lindem, J. Yuan, A. Zinin, R. White and S.
Previdi, "Point-to-point operation over LAN in link-state
routing protocols", Work in Progress.
[Ref6] Pappalardo, D., "AT&T, customers grapple with ATM net
outage", Network World, February 26, 2001.
[Ref7] "AT&T announces cause of frame-relay network outage," AT&T
Press Release, April 22, 1998.
[Ref8] Cholewka, K., "MCI Outage Has Domino Effect", Inter@ctive
Week, August 20, 1999.
[Ref9] Jander, M., "In Qwest Outage, ATM Takes Some Heat", Light
Reading, April 6, 2001.
[Ref10] A. Zinin and M. Shand, "Flooding Optimizations in Link-State
Routing Protocols", Work in Progress.
[Ref11] Pillay-Esnault, P., "OSPF Refresh and Flooding Reduction in
Stable Topologies", RFC 4136, July 2005.
[Ref12] G. Ash, G. Choudhury, V. Sapozhnikova, M. Sherif, A. Maunder,
V. Manral, "Congestion Avoidance & Control for OSPF
Networks", Work in Progress.
[Ref13] G. Choudhury, G. Ash, V. Manral, A. Maunder and V.
Sapozhnikova, "Prioritized Treatment of Specific OSPF Packets
and Congestion Avoidance: Algorithms and Simulations", AT&T
Technical Report, August 2003.
[Ref14] Nichols, K., Blake, S., Baker, F., and D. Black, "Definition
of the Differentiated Services Field (DS Field) in the IPv4
and IPv6 Headers", RFC 2474, December 1998.
Choudhury, Ed. Лучшая современная практика [Страница 7]
RFC 4222 Приоритетная обработка Октябрь 2005
Приложение A. Шторм LSA: причины и воздействие
Шторм LSA может быть инициирован по многим причинам. Ниже приведены
некоторые примеры:
(a) один или несколько отказов каналов вследствие обрывов волоконно-оптических
линий,
(b) один или несколько отказов маршрутизаторов по некоторой причине, например
из-за сбоя программного обеспечения или некоторого типа бедствия (включая
отключение электроэнергии) в офисном комплексе, где размещено много
маршрутизаторов,
(c) неустойчивость состояния канала/маршрутизатора,
(d) необходимость отключить, а позднее вернуть в работу много маршрутизаторов
во время обновления программного/аппаратного обеспечения,
(e) почти синхронное периодическое обновление LSA с периодом 1800 секунд для
подмножества LSA,
(f) обновление всех LSA в системе при изменении версии программного
обеспечения,
(g) введение в OSPF большого числа внешних маршрутов вследствие процедурной
ошибки,
(h) изменения Router ID, вызывающие повторное создание большого числа LSA
(возможно, также удаление LSA в зависимости от реализации).
В дополнение к LSA, созданным непосредственно в результате отказов
канала/маршрутизатора, могут существовать и другие косвенные LSA. Одним из
примеров в сетях MPLS являются LSA инженерии трафика [Ref3], создаваемые на
других каналах вследствие существенных изменений зарезервированной полосы
пропускания. Они возникают вследствие перенаправления Label Switched Paths
(LSP), которые отказали во время отказа канала/маршрутизатора. Шторм LSA
вызывает высокую загрузку процессора и памяти процессора маршрутизатора,
из-за чего входящие пакеты задерживаются или отбрасываются. Задержанные
подтверждения (сверх значения таймера повторной передачи) приводят к
повторным передачам, а задержанные пакеты Hello (сверх интервала Router-Dead)
приводят к объявлению каналов неработающими. Событие отказа магистрального
канала вызывает создание router LSA его оконечными маршрутизаторами. Если
LSA инженерии трафика используются для каждого канала, то LSA этого типа
также будут создаваться оконечными маршрутизаторами и, возможно, также в
других местах вследствие существенных изменений зарезервированных полос
пропускания на других каналах, вызванных отказом и перенаправлением LSP,
первоначально использовавших отказавшую магистраль. В конечном счёте, когда
канал восстановится, это также вызовет дополнительные router LSA и LSA
инженерии трафика.
Choudhury, Ed. Лучшая современная практика [Страница 8]
RFC 4222 Приоритетная обработка Октябрь 2005
Повторные передачи и дополнительное создание LSA приводят к дальнейшему
использованию процессора и памяти, по сути образуя петлю положительной
обратной связи. Мы определяем размер шторма LSA как число LSA в исходном
шторме, не учитывая дополнительные LSA, возникающие из-за описанной выше
петли обратной связи. Если шторм LSA слишком велик, то упомянутая выше петля
положительной обратной связи может быть достаточно большой, чтобы
неопределённо долго поддерживать высокую загрузку процессора и памяти на
многих маршрутизаторах в сети, тем самым приводя сеть в неустойчивое
состояние. В прошлом сообщалось о событиях отказа сети в IP- и ATM-сетях,
использующих протоколы состояния каналов, такие как OSPF, Intermediate System
to Intermediate System (IS-IS), Private Network-Network Interface (PNNI) или
некоторые проприетарные варианты. См., например, [Ref6-Ref9]. Во многих из
этих примеров крупномасштабное распространение LSA или других аналогичных
управляющих сообщений (либо естественное, либо вызванное некоторой ошибкой
или ненадлежащей процедурой) было частично или полностью ответственным за
неустойчивость и отказ сети.
В [Ref13] используется имитационная модель, показывающая, что существует
определённый порог размера шторма LSA, выше которого сеть может проявлять
неустойчивое поведение, вызванное большим числом повторных передач, отказами
каналов вследствие пропущенных пакетов Hello и последующими восстановлениями
каналов. Также показано, что размер шторма LSA, вызывающий неустойчивость,
может быть существенно увеличен путём предоставления приоритетной обработки
пакетам Hello и LSA Acknowledgment, а также с помощью алгоритма экспоненциальной
задержки для определения интервала повторной передачи LSA. Если невозможно
установить приоритет пакетов Hello, то сброс таймера неактивности при получении
любых допустимых пакетов OSPF также может обеспечить тот же эффект. Кроме
того, если мы устанавливаем приоритет пакетам Hello, то даже когда сеть
работает несколько выше порога устойчивости, каналы не объявляются
неработающими вследствие пропущенных пакетов Hello. Это означает, что, хотя
из-за большого числа повторных передач имеется перегрузка плоскости управления,
плоскость данных остаётся работоспособной и новые LSA не создаются (помимо
LSA в исходном шторме и обновлений). Эти наблюдения подтверждают первые три
рекомендации в разделе 2. Авторы этого документа также провели моделирование,
чтобы подтвердить, что другие рекомендации в разделе 2 помогают избежать
перегрузки и обеспечивают плавный выход из перегруженного состояния.
Можно утверждать, что проблему масштабируемости крупных сетей следует решать
исключительно иерархическим разделением сети на несколько областей, чтобы
распространение LSA оставалось локализованным внутри областей. Однако этот
подход увеличивает сложность управления и проектирования сети и может привести
к менее оптимальной маршрутизации между областями. Кроме того, Autonomous
System External (ASE) LSA распространяются по всей AS, и это может быть
проблемой при их большом количестве. Более того, через области может
потребоваться распространять большое число summary LSA, и их количество
значительно увеличилось бы, если бы
Choudhury, Ed. Лучшая современная практика [Страница 9]
RFC 4222 Приоритетная обработка Октябрь 2005
для обеспечения надёжности использовалось несколько Area Border Routers.
Следовательно, важно позволить сети увеличиваться до настолько большого
размера, насколько возможно в пределах одной области.
Рекомендации в документе синергичны с более широким набором предложений по
повышению масштабируемости и устойчивости. [Ref10] предлагает уменьшение
накладных расходов распространения в случае, когда более одного интерфейса
подключается к одному и тому же соседу. [Ref11] предлагает механизм для
значительного сокращения обновлений LSA в стабильных топологиях.
[Ref12] предлагает широкий набор механизмов управления перегрузкой и
восстановления после отказов (некоторые из этих идей рассматриваются в этом
документе, но [Ref12] содержит и другие идеи, не рассмотренные здесь).
Приложение B. Список переменных и значений
F = Коэффициент, на который увеличивается интервал между отправкой
последовательных LSA соседу во время перегрузки и уменьшается после
выхода из перегрузки (используется в рекомендации 4). Пример значения: 2.
G(t) = Интервал между отправкой последовательных LSA соседу в момент времени t
(используется в рекомендации 4).
Gmax = Максимально допустимое значение интервала между отправкой
последовательных LSA соседу (используется в рекомендации 4). Пример
значения: 1 секунда.
Gmin = Минимально допустимое значение интервала между отправкой
последовательных LSA соседу (используется в рекомендации 4). Пример
значения: 20 мс.
H = Верхняя отметка (в единицах числа неподтверждённых LSA). Превышение
этой отметки вызвало бы возможное увеличение интервала между отправкой
последовательных LSA соседу. (используется в рекомендации 4). Пример
значения: 20.
K = Мультипликативная константа, используемая при увеличении значения
RxmtInterval, применяемого во время последовательных повторных передач
одного и того же LSA (используется в рекомендации 3). Пример значения: 2.
L = Нижняя отметка (в единицах числа неподтверждённых LSA). Падение ниже
этой отметки вызвало бы возможное уменьшение интервала между отправкой
последовательных LSA соседу. (используется в рекомендации 4). Пример
значения: 10.
n = Верхний предел числа смежностей, одновременно переводимых в состояние
установления (используется в рекомендации 5).
Choudhury, Ed. Лучшая современная практика [Страница 10]
RFC 4222 Приоритетная обработка Октябрь 2005
R(i) = Значение RxmtInterval, используемое при i-й повторной передаче LSA
(используется в рекомендации 3).
Rmax = Максимально допустимое значение RxmtInterval (используется в
рекомендации 3). Пример значения: 40 секунд.
Rmin = Минимально допустимое значение RxmtInterval (используется в
рекомендации 3). Пример значения: 5 секунд.
T = Минимальное время, которое должно пройти, прежде чем существующий
интервал между отправкой последовательных LSA соседу будет рассмотрен
для изменения (используется в рекомендации 4). Пример значения: 1
секунда.
U(t) = Число неподтверждённых LSA для соседа в момент времени t (используется
в рекомендации 4).
Приложение C. Другие рекомендации и предложения
(1) Явная маркировка: В разделе 2 мы рекомендовали классифицировать пакеты
OSPF в классы приоритета "high" и "low" на основе проверки заголовка
пакета OSPF. В некоторых случаях (в частности, у получателя) эта проверка
может быть вычислительно затратной. Альтернативой было бы использование
различных настроек полей TOS/Precedence для двух классов приоритета.
[Ref1] рекомендует устанавливать поле TOS в 0, а поле Precedence — в 6
для всех пакетов OSPF. Мы рекомендуем те же настройки для пакетов OSPF
с приоритетом "low" и другие настройки для пакетов OSPF с приоритетом
"high", чтобы иметь возможность классифицировать их раздельно без
необходимости проверять заголовок пакета OSPF. Ниже приведены два примера:
Пример 1: Для пакетов с приоритетом "low" установить поле TOS в 0,
а поле Precedence — в 6; для пакетов с приоритетом "high"
установить поле TOS в 4, а поле Precedence — в 6.
Пример 2: Для пакетов с приоритетом "low" установить поле TOS в 0,
а поле Precedence — в 6; для пакетов с приоритетом "high"
установить поле TOS в 0, а поле Precedence — в 7.
Обратите внимание, что биты TOS/Precedence были переопределены Diffserv
(RFC 2474, [Ref14]). Также обратите внимание, что предложенные выше
различные настройки полей TOS/Precedence должны быть согласованы только
между системами на канале. Эту рекомендацию не требуется выполнять, если
заголовок пакета OSPF легко проверить и тем самым отдельно классифицировать
пакеты с приоритетами "high" и "low".
Choudhury, Ed. Лучшая современная практика [Страница 11]
(2) Дальнейшая приоритизация пакетов OSPF: Помимо пакетов,
обозначенных как имеющие «высокий» приоритет в Рекомендации 1
раздела 2, может возникнуть потребность в дальнейшем разделении
приоритетов среди пакетов OSPF с «низким» приоритетом. Мы
рекомендуем использовать три класса приоритета: «высокий»,
«средний» и «низкий». При получении пакета от соседа и при
передаче пакета соседу старайтесь обрабатывать пакет «высокого
приоритета» раньше пакетов «среднего» и «низкого» приоритета, а
пакет «среднего» приоритета — раньше пакетов «низкого»
приоритета. Пакеты «высокого» приоритета определены в
Рекомендации 1 раздела 2. Ниже мы приводим два возможных примера
пакетов «среднего» приоритета. Все пакеты OSPF, не отнесённые к
«высокому» или «среднему» приоритету, имеют «низкий» приоритет.
Если используется криптографическая аутентификация (AuType = 2)
(как определено в [Ref1]), то приоритетная обработка должна
предоставляться только на стороне получателя и после обработки
безопасности, но не на стороне отправителя, поскольку это может
привести к поступлению пакетов не по порядку и нарушить
требования «Autype = 2».
Один пример пакета «среднего» приоритета — пакет Database
Description (DBD) от ведомого маршрутизатора (во время процесса
синхронизации базы данных), используемый как подтверждение.
Второй пример — LSA, содержащий информацию об изменении
топологии внутри области (это может инициировать вычисление SPF
и перемаршрутизацию Label Switched Paths, поэтому быстрая
обработка этого пакета может улучшить время сходимости
OSPF/Label Distribution Protocol (LDP)). Однако, если стоимость
обработки для идентификации и отдельной постановки в очередь LSA
в этом примере считается высокой, то реализатор может принять
решение не делать этого.
(3) Обработка большого количества очисток LSA: Иногда некоторые
события в сети, например изменения идентификатора маршрутизатора,
могут приводить к большому количеству повторных порождений LSA и
очисток LSA. В таком сценарии можно рассмотреть обработку LSA в
другом порядке, например обработку очисток LSA раньше порождений
LSA. Однако мы не рекомендуем обработку LSA не по порядку по
нескольким причинам. Во-первых, определение типа LSA до
постановки в очередь может быть вычислительно затратным.
Обработка не по порядку также может вызвать трудноуловимые
ошибки. Мы не хотим рекомендовать существенное изменение
парадигмы обработки LSA для относительно редкого события, такого
как изменение идентификатора маршрутизатора. Однако маршрутизатор
с изменяющимся идентификатором может постепенно очищать старые
LSA, не вызывая шторма.
Choudhury, Ed. Лучшая современная практика [Страница 12]
RFC 4222 Приоритетная обработка Октябрь 2005
Авторы, внесшие вклад, и их адреса
Помимо редактора, в подготовке этого документа участвовало несколько
человек. Имена и контактная информация всех авторов приведены ниже.
Anurag S. Maunder
Erlang Technology
2880 Scott Boulevard
Santa Clara, CA 95052
USA
Phone: (408) 420-7617
EMail: anuragm@erlangtech.com
Gerald R. Ash
AT&T
Room D5-2A01
200 Laurel Avenue
Middletown, NJ, 07748
USA
Phone: (732) 420-4578
EMail: gash@att.com
Vishwas Manral
Sinett Corp,
2/1 Embassy Icon Annex,
Infantry Road,
Bangalore 560 001
India
Phone: +91-(805)-137-7023
EMail: vishwas@sinett.com
Vera D. Sapozhnikova
AT&T
Room C5-2C29
200 Laurel Avenue
Middletown, NJ, 07748
USA
Phone: (732) 420-2653
EMail: sapozhnikova@att.com
Choudhury, Ed. Лучшая современная практика [Страница 13]
RFC 4222 Приоритетная обработка Октябрь 2005
Адрес редактора
Gagan L. Choudhury
AT&T
Room D5-3C21
200 Laurel Avenue
Middletown, NJ, 07748
USA
Phone: (732) 420-3721
EMail: gchoudhury@att.com
Choudhury, Ed. Лучшая современная практика [Страница 14]
RFC 4222 Приоритетная обработка Октябрь 2005
Полное заявление об авторских правах
Авторское право (C) The Internet Society (2005).
На этот документ распространяются права, лицензии и ограничения,
содержащиеся в BCP 78, и, за исключением предусмотренного в нём,
авторы сохраняют все свои права.
Этот документ и содержащаяся в нём информация предоставляются по
принципу «КАК ЕСТЬ», И УЧАСТНИК, ОРГАНИЗАЦИЯ, КОТОРУЮ ОН/ОНА
ПРЕДСТАВЛЯЕТ ИЛИ КОТОРОЙ ОН/ОНА СПОНСИРУЕТСЯ (ЕСЛИ ТАКОВАЯ ИМЕЕТСЯ),
THE INTERNET SOCIETY И THE INTERNET ENGINEERING TASK FORCE
ОТКАЗЫВАЮТСЯ ОТ ВСЕХ ЯВНЫХ ИЛИ ПОДРАЗУМЕВАЕМЫХ ГАРАНТИЙ, ВКЛЮЧАЯ,
ПОМИМО ПРОЧЕГО, ЛЮБУЮ ГАРАНТИЮ ТОГО, ЧТО ИСПОЛЬЗОВАНИЕ СОДЕРЖАЩЕЙСЯ
ЗДЕСЬ ИНФОРМАЦИИ НЕ НАРУШИТ КАКИХ-ЛИБО ПРАВ, А ТАКЖЕ ЛЮБЫЕ
ПОДРАЗУМЕВАЕМЫЕ ГАРАНТИИ ТОВАРНОЙ ПРИГОДНОСТИ ИЛИ ПРИГОДНОСТИ ДЛЯ
ОПРЕДЕЛЁННОЙ ЦЕЛИ.
Интеллектуальная собственность
IETF не занимает позиции относительно действительности или объёма
каких-либо прав интеллектуальной собственности либо иных прав,
которые могут заявляться как относящиеся к реализации или
использованию технологии, описанной в этом документе, или
относительно того, может ли какая-либо лицензия по таким правам быть
доступна или не быть доступна; также IETF не заявляет, что предприняла
какие-либо независимые усилия для выявления таких прав. Информацию о
процедурах в отношении прав в документах RFC можно найти в BCP 78 и
BCP 79.
Копии раскрытий IPR, сделанных Секретариату IETF, и любые заверения о
лицензиях, которые будут предоставлены, либо результат попытки
получить общую лицензию или разрешение на использование таких
имущественных прав реализаторами или пользователями этой
спецификации можно получить в онлайновом репозитории IPR IETF по
адресу http://www.ietf.org/ipr.
IETF предлагает любой заинтересованной стороне довести до её сведения
любые авторские права, патенты или заявки на патенты либо иные
имущественные права, которые могут охватывать технологию, которая
может потребоваться для реализации этого стандарта. Просьба направлять
информацию в IETF по адресу ietf-
ipr@ietf.org.
Благодарность
Финансирование функции редактора RFC в настоящее время обеспечивается
The Internet Society.
Choudhury, Ed. Лучшая современная практика [Страница 15]
Network Working Group G. Choudhury, Ed.
Request for Comments: 4222 AT&T
BCP: 112 October 2005
Category: Best Current Practice
Prioritized Treatment of Specific OSPF Version 2
Packets and Congestion Avoidance
Status of This Memo
This document specifies an Internet Best Current Practices for the
Internet Community, and requests discussion and suggestions for
improvements. Distribution of this memo is unlimited.
Copyright Notice
Copyright (C) The Internet Society (2005).
Abstract
This document recommends methods that are intended to improve the
scalability and stability of large networks using Open Shortest Path
First (OSPF) Version 2 protocol. The methods include processing OSPF
Hellos and Link State Advertisement (LSA) Acknowledgments at a higher
priority compared to other OSPF packets, and other congestion
avoidance procedures.
Table of Contents
1. Introduction...................................................2
2. Recommendations................................................3
3. Security Considerations........................................6
4. Acknowledgments................................................6
5. Normative References...........................................6
6. Informative References.........................................7
Appendix A. LSA Storm: Causes and Impact..........................8
Appendix B. List of Variables and Values.........................10
Appendix C. Other Recommendations and Suggestions................11
Choudhury, Ed. Best Current Practice [Page 1]
RFC 4222 Prioritized Treatment October 2005
1. Introduction
In this document, OSPF refers to OSPFv2 [Ref1]. The scalability and
stability improvement techniques described here may also apply to
OSPFv3 [Ref2], but that will require further study and operational
experience.
A large network running OSPF protocol may occasionally experience the
simultaneous or near-simultaneous update of a large number of link
state advertisements, or LSAs. This is particularly true if OSPF
traffic engineering extension [Ref3] is used that may significantly
increase the number of LSAs in the network. We call this event an
LSA storm and it may be initiated by an unscheduled failure or a
scheduled maintenance event. The failure may be hardware, software,
or procedural in nature.
The LSA storm causes high CPU and memory utilization at the router
causing incoming packets to be delayed or dropped. Delayed
acknowledgments (beyond the retransmission timer value) result in
retransmissions, and delayed Hello packets (beyond the router-dead
interval) result in neighbor adjacencies being declared down. The
retransmissions and additional LSA originations result in further CPU
and memory usage, essentially causing a positive feedback loop,
which, in the extreme case, may drive the network to an unstable
state.
The default value of the retransmission timer is 5 seconds and that
of the router-dead interval is 40 seconds. However, recently there
has been a lot of interest in significantly reducing OSPF convergence
time. As part of that plan, much shorter (sub-second) Hello and
router-dead intervals have been proposed [Ref4]. In such a scenario,
it will be more likely for Hello packets to be delayed beyond the
router-dead interval during network congestion caused by an LSA
storm.
In order to improve the scalability and stability of networks, we
recommend steps for prioritizing critical OSPF packets and avoiding
congestion. The details of the recommendations are given in Section
2. A simulation study is reported in [Ref13] that quantifies the
congestion phenomenon and its impact. It also studies several of the
recommendations and shows that they indeed improve the scalability
and stability of networks using OSPF protocol. [Ref13] is available
on request by contacting the editor or one of the authors.
Choudhury, Ed. Best Current Practice [Page 2]
RFC 4222 Prioritized Treatment October 2005
Appendix A explains in more detail LSA storm scenarios, their impact,
and points out a few real-life examples of control-message storms.
Appendix B provides a list of variables used in the recommendations
and their example values. Appendix C provides some further
recommendations and suggestions with similar goals.
2. Recommendations
The recommendations below are intended to improve the scalability and
stability of large networks using OSPF protocol. During periods of
network congestion, they would reduce retransmissions, avoid an
adjacency to be declared down due to Hello packets being delayed
beyond the RouterDeadInterval, and take other congestion avoidance
steps. The recommendations are unordered except that Recommendation
2 is to be implemented only if Recommendation 1 is not implemented.
(1) Classify all OSPF packets in two classes: a "high priority" class
comprising OSPF Hello packets and Link State Acknowledgement
packets, and a "low priority" class comprising all other packets.
The classification is accomplished by examining the OSPF packet
header. While receiving a packet from a neighbor and while
transmitting a packet to a neighbor, try to process a "high
priority" packet ahead of a "low priority" packet.
The prioritized processing while transmitting may cause OSPF
packets from a neighbor to be received out of sequence. If
Cryptographic Authentication (AuType = 2) is used (as specified
in [Ref1]), then successive received valid OSPF packets from a
neighbor need to have a non-decreasing "Cryptographic sequence
number". To comply with this requirement, we recommend that in
case Cryptographic Authentication (AuType = 2) is used [Ref1],
prioritized processing not be done at the transmitter. This will
avoid packets arriving at the receiver out of sequence. However,
after security processing at the receiver (including sequence
number checking) is complete, the OSPF packets may be kept in a
"high priority" queue or a "low priority" queue based on their
class and processed accordingly. The benefit of prioritized
processing is clearly higher in the absence of Cryptographic
Authentication since in that case prioritization can be
implemented both at the transmitter and at the receiver.
However, even with Cryptographic Authentication it will be
beneficial to have prioritization only at the receiver (following
security processing).
(2) If Recommendation 1 cannot be implemented, then reset the
inactivity timer for an adjacency whenever any OSPF unicast
packet or any OSPF packet sent to AllSPFRouters over a point-to-
point link is received over that adjacency instead of resetting
Choudhury, Ed. Best Current Practice [Page 3]
RFC 4222 Prioritized Treatment October 2005
the inactivity timer only on receipt of the Hello packet. So
OSPF would declare the adjacency to be down only if no OSPF
unicast packets or no OSPF packets sent to AllSPFRouters over a
point-to-point link are received over that adjacency for a period
equaling or exceeding the RouterDeadInterval. The reason for not
recommending this proposal in conjunction with Recommendation 1
is to avoid potential undesirable side effects. One such effect
is the delay in discovering the down status of an adjacency in a
case where no high priority Hello packets are being received but
the inactivity timer is being reset by other stale packets in the
low priority queue.
(3) Use an exponential backoff algorithm for determining the value of
the LSA retransmission interval (RxmtInterval). Let R(i)
represent the RxmtInterval value used during the i-th
retransmission of an LSA. Use the following algorithm to compute
R(i).
R(1) = Rmin
R(i+1) = Min(KR(i),Rmax) for i>=1
where K, Rmin, and Rmax are constants and the function Min(.,.)
represents the minimum value of its two arguments. Example
values for K, Rmin, and Rmax may be 2, 5, and 40 seconds,
respectively. Note that the example value for Rmin, the initial
retransmission interval, is the same as the sample value of
RxmtInterval in [Ref1].
This recommendation is motivated by the observation that during a
network congestion event caused by control messages, a major
source for sustaining the congestion is the repeated
retransmission of LSAs. The use of an exponential backoff
algorithm for the LSA retransmission interval reduces the rate of
LSA retransmissions while the network experiences congestion
(during which it is more likely that multiple retransmissions of
the same LSA would happen). This in turn helps the network get
out of the congested state.
(4) Implicit Congestion Detection and Action Based on That: If there
is control message congestion at a router, its neighbors do not
know about that explicitly. However, they can implicitly detect
it based on the number of unacknowledged LSAs to this router. If
this number exceeds a certain "high-water mark", then the rate at
which LSAs are sent to this router should be reduced
progressively using an exponential backoff mechanism but not
below a certain minimum rate. At a future time, if the number of
unacknowledged LSAs to this router falls below a certain "low-
water mark", then the rate of sending LSAs to this router should
Choudhury, Ed. Best Current Practice [Page 4]
RFC 4222 Prioritized Treatment October 2005
be increased progressively, again using an exponential backoff
mechanism but not above a certain maximum rate. The whole
algorithm is given below. Note that this algorithm is to be
applied independently to each neighbor and only for unicast LSAs
sent to a neighbor or LSAs sent to AllSPFRouters over a point-
to-point link.
Let,
U(t) = Number of unacknowledged LSAs to neighbor at time t.
H = A high-water mark (in units of number of unacknowledged
LSAs).
L = A low-water mark (in units of number of unacknowledged LSAs).
G(t) = Gap between sending successive LSAs to neighbor at time t.
F = The factor by which the above gap is to be increased during
congestion and decreased after coming out of congestion.
T = Minimum time that has to elapse before the existing gap
is considered for change.
Gmin = Minimum allowed value of gap.
Gmax = Maximum allowed value of gap.
The equation below shows how the gap is to be changed after a
time T has elapsed since the last change:
_
|
| Min(FG(t),Gmax) if U(t+T) > H
G(t+T) = | G(t) if H >= U(t+T) >= L
| Max(G(t)/F,Gmin) if U(t+T) < L
|_
Min(.,.) and Max(.,.) represent the minimum and maximum values of
the two arguments, respectively.
Example values for the various parameters of the algorithm are as
follows: H = 20, L = 10, F = 2, T = 1 second, Gmin = 20 ms, Gmax
= 1 second.
Recommendations 3 and 4 both slow down LSAs to congested
neighbors based on implicitly detecting the congestion, but they
have important differences. Recommendation 3 progressively slows
down successive retransmissions of the same LSA, whereas
Recommendation 4 progressively slows down all LSAs (new or
retransmission) to a congested neighbor.
(5) Throttling Adjacencies to Be Brought Up Simultaneously: If a
router tries to bring up a large number of adjacencies to its
neighbors simultaneously, then that may cause severe congestion
due to database synchronization and LSA flooding activities. It
is recommended that during such a situation no more than "n"
Choudhury, Ed. Best Current Practice [Page 5]
RFC 4222 Prioritized Treatment October 2005
adjacencies should be brought up simultaneously. Once a subset
of adjacencies has been brought up successfully, newer
adjacencies may be brought up as long as the number of
simultaneous adjacencies being brought up does not exceed "n".
The appropriate value of "n" would depend on the router
processing power, total bandwidth available for control plane
traffic, and propagation delay. The value of "n" should be
configurable.
In the presence of throttling, an important issue is the order in
which adjacencies are to be formed. We recommend a First Come
First Served (FCFS) policy based on the order in which the
request for adjacency formation arrives. Requests may either be
from neighbors or self-generated. Among the self-generated
requests, a priority list may be used to decide the order in
which the requests are to be made. However, once an adjacency
formation process starts it is not to be preempted except for
unusual circumstances such as errors or time-outs.
In some of the recommendations above, we refer to point-to-point
links. Those references should also include cases where a broadcast
network is to be treated as a point-to-point connection from the
standpoint of IP routing [Ref5]
3. Security Considerations
This memo does not create any new security issues for the OSPF
protocol.
4. Acknowledgments
We would like to acknowledge the support and helpful comments from
OSPF WG chairs Rohit Dube, Acee Lindem, and John Moy; Routing Area
directors Alex Zinin and Bill Fenner; and IESG reviewers. We
acknowledge Vivek Dube, Mitchell Erblich, Mike Fox, Tony Przygienda,
and Krishna Rao for comments on previous versions of the document.
We also acknowledge Margaret Chiosi, Elie Francis, Jeff Han, Beth
Munson, Roshan Rao, Moshe Segal, Mike Wardlow, and Pat Wirth for
collaboration and encouragement in our scalability improvement
efforts for Link State Protocol-based networks.
5. Normative References
[Ref1] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
[Ref2] Coltun, R., Ferguson, D., and J. Moy, "OSPF for IPv6", RFC
2740, December 1999.
Choudhury, Ed. Best Current Practice [Page 6]
RFC 4222 Prioritized Treatment October 2005
6. Informative References
[Ref3] Katz, D., Kompella, K., and D. Yeung, "Traffic Engineering
(TE) Extensions to OSPF Version 2", RFC 3630, September 2003.
[Ref4] C. Alaettinoglu, V. Jacobson and H. Yu, "Towards Millisecond
IGP Convergence", Work in Progress.
[Ref5] N. Shen, A. Lindem, J. Yuan, A. Zinin, R. White and S.
Previdi, "Point-to-point operation over LAN in link-state
routing protocols", Work in Progress.
[Ref6] Pappalardo, D., "AT&T, customers grapple with ATM net
outage", Network World, February 26, 2001.
[Ref7] "AT&T announces cause of frame-relay network outage," AT&T
Press Release, April 22, 1998.
[Ref8] Cholewka, K., "MCI Outage Has Domino Effect", Inter@ctive
Week, August 20, 1999.
[Ref9] Jander, M., "In Qwest Outage, ATM Takes Some Heat", Light
Reading, April 6, 2001.
[Ref10] A. Zinin and M. Shand, "Flooding Optimizations in Link-State
Routing Protocols", Work in Progress.
[Ref11] Pillay-Esnault, P., "OSPF Refresh and Flooding Reduction in
Stable Topologies", RFC 4136, July 2005.
[Ref12] G. Ash, G. Choudhury, V. Sapozhnikova, M. Sherif, A. Maunder,
V. Manral, "Congestion Avoidance & Control for OSPF
Networks", Work in Progress.
[Ref13] G. Choudhury, G. Ash, V. Manral, A. Maunder and V.
Sapozhnikova, "Prioritized Treatment of Specific OSPF Packets
and Congestion Avoidance: Algorithms and Simulations", AT&T
Technical Report, August 2003.
[Ref14] Nichols, K., Blake, S., Baker, F., and D. Black, "Definition
of the Differentiated Services Field (DS Field) in the IPv4
and IPv6 Headers", RFC 2474, December 1998.
Choudhury, Ed. Best Current Practice [Page 7]
RFC 4222 Prioritized Treatment October 2005
Appendix A. LSA Storm: Causes and Impact
An LSA storm may be initiated due to many reasons. Here are some
examples:
(a) one or more link failures due to fiber cuts,
(b) one or more router failures for some reason, e.g., software crash
or some type of disaster (including power outage) in an office
complex hosting many routers,
(c) link/router flapping,
(d) requirement of taking down and later bringing back many routers
during a software/hardware upgrade,
(e) near synchronization of the periodic 1800-second LSA refreshes of
a subset of LSAs,
(f) refresh of all LSAs in the system during a change in software
version,
(g) injecting a large number of external routes to OSPF due to a
procedural error,
(h) Router ID changes causing a large number of LSA re-originations
(possibly LSA purges as well depending on the implementation).
In addition to the LSAs originated as a direct result of link/router
failures, there may be other indirect LSAs as well. One example in
MPLS networks is traffic engineering LSAs [Ref3] originated at other
links as a result of significant changes in reserved bandwidth.
These result from rerouting of Label Switched Paths (LSPs) that went
down during the link/router failure. The LSA storm causes high CPU
and memory utilization at the router processor causing incoming
packets to be delayed or dropped. Delayed acknowledgments (beyond
the retransmission timer value) results in retransmissions, and
delayed Hello packets (beyond the Router-Dead interval) results in
links being declared down. A trunk-down event causes router LSA
origination by its end-point routers. If traffic engineering LSAs
are used for each link, then that type of LSA would also be
originated by the end-point routers and potentially elsewhere as well
due to significant changes in reserved bandwidths at other links
caused by the failure and reroute of LSPs originally using the failed
trunk. Eventually, when the link recovers that would also trigger
additional router LSAs and traffic engineering LSAs.
Choudhury, Ed. Best Current Practice [Page 8]
RFC 4222 Prioritized Treatment October 2005
The retransmissions and additional LSA originations result in further
CPU and memory usage, essentially causing a positive feedback loop.
We define the LSA storm size as the number of LSAs in the original
storm, not counting any additional LSAs resulting from the feedback
loop described above. If the LSA storm is too large, then the
positive feedback loop mentioned above may be large enough to
indefinitely sustain a large CPU and memory utilization at many
routers in the network, thereby driving the network to an unstable
state. In the past, network outage events have been reported in IP
and ATM networks using link-state protocols such as OSPF,
Intermediate System to Intermediate System (IS-IS), Private Network-
Network Interface (PNNI), or some proprietary variants. See for
example [Ref6-Ref9]. In many of these examples, large-scale flooding
of LSAs or other similar control messages (either naturally or
triggered by some bug or inappropriate procedure) have been partly or
fully responsible for network instability and outage.
In [Ref13], a simulation model is used to show that there is a
certain LSA storm size threshold above which the network may show
unstable behavior caused by a large number of retransmissions, link
failures due to missed Hello packets, and subsequent link recoveries.
It is also shown that the LSA storm size causing instability may be
substantially increased by providing prioritized treatment to Hello
and LSA Acknowledgment packets and by using an exponential backoff
algorithm for determining the LSA retransmission interval. If it is
not possible to prioritize Hello packets, then resetting the
inactivity timer on receiving any valid OSPF packets can also provide
the same benefit. Furthermore, if we prioritize Hello packets, then
even when the network operates somewhat above the stability
threshold, links are not declared down due to missed Hellos. This
implies that even though there is control plane congestion due to
many retransmissions, the data plane stays up and no new LSAs are
originated (besides the ones in the original storm and the
refreshes). These observations support the first three
recommendations in Section 2. The authors of this document have also
done simulations to verify that the other recommendations in Section
2 help avoid congestion and allow a graceful exit from a congested
state.
One might argue that the scalability issue of large networks should
be solved solely by dividing the network hierarchically into multiple
areas so that flooding of LSAs remains localized within areas.
However, this approach increases the network management and design
complexity and may result in less optimal routing between areas.
Also, Autonomous System External (ASE) LSAs are flooded throughout
the AS, and it may be a problem if there are large numbers of them.
Furthermore, a large number of summary LSAs may need to be flooded
across areas, and their numbers would increase significantly if
Choudhury, Ed. Best Current Practice [Page 9]
RFC 4222 Prioritized Treatment October 2005
multiple Area Border Routers are employed for the purpose of
reliability. Thus, it is important to allow the network to grow
towards as large a size as possible under a single area.
The recommendations in the document are synergistic with a broader
set of scalability and stability improvement proposals. [Ref10]
proposes flooding overhead reduction in case more than one interface
goes to the same neighbor. [Ref11] proposes a mechanism for greatly
reducing LSA refreshes in stable topologies.
[Ref12] proposes a wide range of congestion control and failure
recovery mechanisms (some of those ideas are covered in this
document, but [Ref12] has other ideas not covered here).
Appendix B. List of Variables and Values
F = The factor by which the gap between sending successive LSAs to
a neighbor is to be increased during congestion and decreased
after coming out of congestion (used in Recommendation 4).
Example value is 2.
G(t) = Gap between sending successive LSAs to a neighbor at time t
(used in Recommendation 4).
Gmax = Maximum allowed value of gap between sending successive LSAs
to a neighbor (used in Recommendation 4). Example value is 1
second.
Gmin = Minimum allowed value of gap between sending successive LSAs
to a neighbor (used in Recommendation 4). Example value is 20
ms.
H = A high-water mark (in units of number of unacknowledged LSAs).
Exceeding this mark would trigger a potential increase in the
gap between sending successive LSAs to a neighbor. (used in
Recommendation 4). Example value is 20.
K = A multiplicative constant used in increasing the RxmtInterval
value used during successive retransmissions of the same LSA
(used in Recommendation 3). Example value is 2.
L = A low-water mark (in units of number of unacknowledged LSAs)
Dropping below this mark would trigger a potential decrease in
the gap between sending successive LSAs to a neighbor. (used
in Recommendation 4). Example value is 10.
n = Upper limit on the number of adjacencies to be brought up
simultaneously (used in Recommendation 5).
Choudhury, Ed. Best Current Practice [Page 10]
RFC 4222 Prioritized Treatment October 2005
R(i) = RxmtInterval value used during the i-th retransmission of an
LSA (used in Recommendation 3).
Rmax = The maximum allowed value of RxmtInterval (used in
Recommendation 3). Example value is 40 seconds.
Rmin = The minimum allowed value of RxmtInterval (used in
Recommendation 3). Example value is 5 seconds.
T = Minimum time that has to elapse before the existing gap
between sending successive LSAs to a neighbor is considered
for change (used in Recommendation 4). Example value is 1
second.
U(t) = Number of unacknowledged LSAs to a neighbor at time t (used in
Recommendation 4).
Appendix C. Other Recommendations and Suggestions
(1) Explicit Marking: In Section 2, we recommended that OSPF packets
be classified to "high" and "low" priority classes based on
examining the OSPF packet header. In some cases (particularly in
the receiver), this examination may be computationally costly.
An alternative would be the use of different TOS/Precedence field
settings for the two priority classes. [Ref1] recommends setting
the TOS field to 0 and the Precedence field to 6 for all OSPF
packets. We recommend this same setting for the "low" priority
OSPF packets and a different setting for the "high" priority OSPF
packets in order to be able to classify them separately without
having to examine the OSPF packet header. Two examples are given
below:
Example 1: For "low" priority packets, set TOS field to 0 and
Precedence field to 6, and for "high" priority packets
set TOS field to 4 and Precedence field to 6.
Example 2: For "low" priority packets, set TOS field to 0 and
Precedence field to 6, and for "high" priority packets
set TOS field to 0 and Precedence field to 7.
Note that the TOS/Precedence bits have been redefined by Diffserv
(RFC 2474, [Ref14]). Also note that the different TOS/Precedence
field settings suggested above only need to be agreed among the
systems on the link. This recommendation is not needed to be
followed if it is easy to examine the OSPF packet header and
thereby separately classify "high" and "low" priority packets.
Choudhury, Ed. Best Current Practice [Page 11]
RFC 4222 Prioritized Treatment October 2005
(2) Further Prioritization of OSPF Packets: Besides the packets
designated as "high" priority in Recommendation 1 of Section 2,
there may be a need for further priority separation among the
"low" priority OSPF packets. We recommend the use of three
priority classes: "high", "medium" and "low". While receiving a
packet from a neighbor and while transmitting a packet to a
neighbor, try to process a "high priority" packet ahead of
"medium" and "low" priority packets and a "medium" priority
packet ahead of "low priority" packets. The "high" priority
packets are as designated in Recommendation 1 of Section 2. We
provide below two candidate examples for "medium" priority
packets. All OSPF packets not designated as "high" or "medium"
priority are "low" priority. If Cryptographic Authentication
(AuType = 2) is used (as specified in [Ref1]), then prioritized
treatment is to be provided only at the receiver and after
security processing, but not at the transmitter since that may
cause packets to arrive out of sequence and violate the
requirements of "Autype = 2".
One example of "medium" priority packet is the Database
Description (DBD) packet from a slave (during the database
synchronization process) that is used as an acknowledgment.
A second example is an LSA carrying intra-area topology change
information (this may trigger SPF calculation and rerouting of
Label Switched Paths, so fast processing of this packet may
improve OSPF/Label Distribution Protocol (LDP) convergence
times). However, if the processing cost of identifying and
separately queueing the LSA in this example is deemed to be high,
then the implementer may decide not to do it.
(3) Processing a Large Number of LSA Purges: Occasionally, some
events in the network, such as router ID changes, may result in a
large number of LSA re-originations and LSA purges. In such a
scenario, one may consider processing LSAs in different order,
e.g., processing LSA purges ahead of LSA originations. We,
however, do not recommend out-of-order LSA processing for several
reasons. First, detecting the LSA type ahead of queueing may be
computationally expensive. Out-of-order processing may also
cause subtle bugs. We do not want to recommend a major change in
the LSA processing paradigm for a relatively rare event such as
router ID change. However, a router with a changing ID may flush
the old LSAs gradually without causing a storm.
Choudhury, Ed. Best Current Practice [Page 12]
RFC 4222 Prioritized Treatment October 2005
Contributing Authors and Their Addresses
In addition to the editor, several people contributed to this
document. The names and contact information of all authors are given
below.
Anurag S. Maunder
Erlang Technology
2880 Scott Boulevard
Santa Clara, CA 95052
USA
Phone: (408) 420-7617
EMail: anuragm@erlangtech.com
Gerald R. Ash
AT&T
Room D5-2A01
200 Laurel Avenue
Middletown, NJ, 07748
USA
Phone: (732) 420-4578
EMail: gash@att.com
Vishwas Manral
Sinett Corp,
2/1 Embassy Icon Annex,
Infantry Road,
Bangalore 560 001
India
Phone: +91-(805)-137-7023
EMail: vishwas@sinett.com
Vera D. Sapozhnikova
AT&T
Room C5-2C29
200 Laurel Avenue
Middletown, NJ, 07748
USA
Phone: (732) 420-2653
EMail: sapozhnikova@att.com
Choudhury, Ed. Best Current Practice [Page 13]
RFC 4222 Prioritized Treatment October 2005
Editor's Address
Gagan L. Choudhury
AT&T
Room D5-3C21
200 Laurel Avenue
Middletown, NJ, 07748
USA
Phone: (732) 420-3721
EMail: gchoudhury@att.com
Choudhury, Ed. Best Current Practice [Page 14]
RFC 4222 Prioritized Treatment October 2005
Full Copyright Statement
Copyright (C) The Internet Society (2005).
This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors
retain all their rights.
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Intellectual Property
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be
found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at ietf-
ipr@ietf.org.
Acknowledgement
Funding for the RFC Editor function is currently provided by the
Internet Society.
Choudhury, Ed. Best Current Practice [Page 15]