RFC 4271 — Протокол BGP-4

9.1.2.2. «Отбрасывание лишнего» (фаза 2)

В таблице Adj-RIBs-In узла BGP может храниться несколько маршрутов к одному адресату, имеющих одинаковый уровень предпочтения. Локальный узел может выбрать только один из таких маршрутов для включения в таблицу Loc-RIB. К рассмотрению принимаются все маршруты с одинаковым уровнем предпочтения, полученные как от внутренних, так и от внешних партнеров.

В описанной ниже процедуре предполагается, что для каждого маршрута-кандидата все узлы BGP в автономной системе могут определить стоимость пути (внутренняя дистанция) до адреса, указанного атрибутом NEXT_HOP в данном маршруте, и применяется один алгоритм выбора маршрутов.

Работа алгоритма tie-breaking начинается с рассмотрения всех маршрутов к одному множеству адресатов, имеющих одинаковый уровень предпочтения, и выбором маршрутов, которые будут исключаться из рассмотрения. Работа алгоритма завершается после того, как останется единственный маршрут. Критерии отбора должны применяться в указанном ниже порядке.

Некоторые критерии описаны с использованием псевдокода. Отметим, что выбор псевдокода был продиктован соображениями ясности, а не эффективности. Он не предназначен для конкретной реализации. Реализации протокола BGP могут использовать любой алгоритм, который будет давать такой же результат, как описано здесь.

• Исключаются из рассмотрения все маршруты, с числом номеров AS в атрибуте AS_PATH, большим минимального значения. Отметим, что при расчете этого значения AS_SET учитывается как 1, независимо от количества AS в данном наборе.

• Исключаются из рассмотрения все маршруты, для которых значение атрибута Origin превышает минимальное.

• Исключаются из рассмотрения маршруты с менее предпочтительными атрибутами MULTI_EXIT_DISC. Значения MULTI_EXIT_DISC можно сравнивать только для маршрутов, полученных из одной соседней AS (эта AS определяется из атрибута AS_PATH). Маршруты без атрибута MULTI_EXIT_DISC рассматриваются как маршруты с наименьшим возможным значением MULTI_EXIT_DISC.

  Описанный выше алгоритм можно представить в виде следующей процедуры:

  for m = число остающихся в рассмотрении маршрутов
      for n = число остающихся в рассмотрении маршрутов
          if (neighborAS(m) == neighborAS(n)) and (MED(n) < MED(m))
              исключить маршрут m из рассмотрения

  В приведенном выше псевдокоде функция MED(n) возвращает значение атрибута MULTI_EXIT_DISC для маршрута n. Если маршрут n не имеет атрибута MULTI_EXIT_DISC, функция возвращает минимальное из возможных значений MULTI_EXIT_DISC (т. е., 0).

  Функция neighborAS(n) возвращает номер соседней AS, из которой был получен маршрут n. Если маршрут получен через IBGP и другой узел IBGP не является исходной точкой этого маршрута, это будет номер соседней AS, из которой другой узел IBGP получил маршрут. Если маршрут получен через IBGP и другой узел IBGP (a) является исходной точкой маршрута или (b) создал маршрут путем агрегирования и атрибут AS_PATH агрегированного маршрута пуст или начинается с AS_SET, это локальная AS.

  Если атрибут MULTI_EXIT_DISC удаляется до повторного анонсирования маршрута в IBGP, можно провести сравнение с использованием полученного через EBGP атрибута MULTI_EXIT_DISC. Если реализация решает удалить MULTI_EXIT_DISC, тогда дополнительное сравнение MULTI_EXIT_DISC, если оно выполняется, должно учитывать только маршруты, полученные через EBGP. Наилучший маршрут от EBGP можно тогда сравнивать с маршрутами от IBGP после удаления атрибута MULTI_EXIT_DISC. Если атрибут MULTI_EXIT_DISC удаляется из подмножества маршрутов от EBGP и из выбранного «лучшего» маршрута от EBGP не будет удален атрибут MULTI_EXIT_DISC, тогда этот атрибут должен использоваться для сравнения с маршрутами от IBGP. Для полученных через IBGP маршрутов атрибут MULTI_EXIT_DISC должен использоваться при сравнении маршрутов, которые не исключены на предыдущих этапах выбора (Decision Process). Включение атрибута MULTI_EXIT_DISC маршрутов от EBGP в сравнение с маршрутами от IBGP с последующим удалением атрибута MULTI_EXIT_DISC и анонсированием маршрута будет предотвращать возникновение маршрутных петель.

• Если хотя бы один из маршрутов-кандидатов получен через EBGP, исключаются из рассмотрения все маршруты, полученные от IBGP.

• Исключаются из рассмотрения все маршруты с наименее предпочтительной внутренней стоимостью (interior cost). Внутренняя стоимость маршрута определяется путем расчета метрики до NEXT_HOP для маршрута с использованием таблицы маршрутизации. Если маршрутизатор NEXT_HOP для этого маршрута доступен, но стоимость пути невозможно определить, этот этап следует пропустить (возможно, рассматривая все маршруты, как равноценные).

  Описанный выше алгоритм можно представить псевдокодом:

  for m = число остающихся в рассмотрении маршрутов
      for n = число остающихся в рассмотрении маршрутов
          if (cost(n) < cost(m))
              исключить маршрут m из рассмотрения

  В приведенном псевдокоде функция cost(n) возвращает стоимость пути (внутренняя дистанция) до адреса, указанного в атрибуте NEXT_HOP рассматриваемого маршрута.

• Исключаются из рассмотрения все маршруты, кроме того, который был анонсирован узлом BGP с наименьшим значением BGP Identifier.

• Выбирается маршрут, полученный от партнера с наименьшим адресом.