способ вычисления организации моста между состояниями каналов связи провайдера (plsb)

Формула изобретения

1. Способ вычисления многоадресных маршрутов в сети с управлением протоколом состояния канала связи, причем способ содержит этапы, на которых:

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

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

объединяют два или более из секторов, когда удовлетворяют предопределенному критерию;

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

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

3. Способ по п.2, в котором кратчайший путь является прямым каналом связи.

4. Способ по п.2, в котором кратчайший путь выбирают из набора двух или более путей равной стоимости между каждым из вовлеченных соседних узлов способом разрыва связей, который является симметричным и локально последовательным.

5. Способ по п.1, в котором первый сектор содержит соответствующий один из соседних узлов, и второй сектор является суперсектором, содержащим два или более из соседних узлов, и в котором предопределенный критерий заключается в том, что соответствующие кратчайшие пути между одним соседним узлом из первого сектора и двумя или более соседними узлами из второго сектора не проходят через первый узел.

6. Способ по п.5, в котором, по меньшей мере, один из кратчайших путей является прямым каналом связи.

7. Способ по п.5, в котором, по меньшей мере, один из кратчайших путей выбирают из набора двух или более путей равной стоимости между одним соседним узлом из первого сектора и одним из двух или более соседних узлов из второго сектора способом разрыва связей, который является симметричным и локально последовательным.

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

Описание изобретения к патенту

Перекрестная ссылка на родственные заявки

Это первая заявка, зарегистрированная для настоящего изобретения.

Микрофишное приложение

Не применяется.

Область техники, к которой относится изобретение

Настоящее изобретение относится к переадресации трафика в пакетных сетях, а более конкретно к способу вычисления организации моста между состояниями каналов связи провайдера (PLSB).

Уровень техники изобретения

Сетевые операторы и поставщики услуг связи разворачивают сети связи с коммутацией пакетов взамен сетей с коммутацией пакетов. В сетях с коммутацией пакетов, таких как сети с протоколом Интернет (IP), IP-пакеты маршрутизируют в соответствии с состоянием маршрутизации, хранимым в каждом IP-маршрутизаторе в сети. Аналогично, в сетях Ethernet, кадры Ethernet переадресовывают в соответствии с состоянием переадресации, хранимым в каждом коммутаторе Ethernet в сети. Настоящее изобретение применимо к сетям связи, использующим любую сеть, основанную на протокольном блоке данных (PDU), и в этом документе термины "пакет" и "сеть с коммутацией пакетов", "маршрутизация", "кадр" и "сеть на основе кадров", "переадресация" и родственные термины, предназначенные для покрытия любых PDU, сетей связи, использующих PDU, и избирательную передачу PDU из узла сети в узел сети.

Многоадресная переадресация пакетов данных (где пакеты посылают из узла источника в многочисленные узлы пунктов назначения более или менее одновременно) имеет возрастающую актуальность, так как растет требование к услугам, таким как телевидение по протоколу Интернет (IPTV) и видео по требованию (VoD).

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

В сетях Ethernet транспорт по магистрали провайдера (PBT), который так же известен как организация моста между магистралями провайдеров с формированием трафика (PBB-TE), как описано в патенте Великобритании № GB 2422508 заявителя, используется для обеспечения одноадресной транспортной технологии Ethernet. Организация моста между состояниями каналов связи провайдера (PLSB), как описано в совместно поданной заявителем заявке на патент США серийный номер 11/537,775, будет использоваться для обеспечения возможности многоадресного транспорта для сетей Ethernet, использующих IS-IS для установления как одноадресных путей, так и многоадресных деревьев в сети. Оба вышеприведенных патентных документа включены, таким образом, посредством ссылки.

Хотя настоящее изобретение не ограничено применением системы маршрутизации для организации моста Ethernet, технология Ethernet используется в этом раскрытии там, где это возможно. Поэтому, например, термин фильтрующая база данных (FDB) можно рассматривать взаимозаменяемым с любым термином для хранилища информации о переадресации пакетов, таких как информационная база переадресации или информационная база меток.

Обычно, многоадресные деревья в сети PLSB вычисляют с использованием алгоритма вычисления многоадресных маршрутов с кратчайшими путями между всеми парами, известного, например, из совместно поданной заявителем публикации заявки на патент США № 20070165657. В соответствии с этим способом, когда узел принимает или изменение многоадресной групповой принадлежности или изменение топологии сети (например, через блок данных протокола состояния канала связи (LSP), узел использует алгоритмы, такие как алгоритм Де'йкстры для вычисления как одноадресной связности, так и набора пар узлов сети, которые соединены кратчайшим путем, который проходит через вычислительный узел. Для этого набора пар узлов, узел определяет, где происходят пересечения многоадресной групповой принадлежности, и определяет требуемые вводы FDB, чтобы подвергнуть обработке, соответственно, свои участки многоадресных путей. Как Одноадресное, так и Многоадресное состояние переадресации, реализующие вычисленные пути, затем устанавливают в фильтрующей базе данных (FDB) узла для того, чтобы принятые пакеты можно было переадресовать в соответствующий выходной порт(ы) узла на основе адреса пункта назначения в кадре.

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

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

Сущность изобретения

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

Краткое описание чертежей

Дополнительные признаки и преимущества настоящего изобретения станут очевидны из нижеследующего подробного описания, представленного в сочетании с прилагаемым чертежами, на которых:

Фиг. 1 является блок-схемой последовательности операций способа, иллюстрирующей основные этапы способа, согласно образцовому варианту осуществления настоящего изобретения;

Фиг. 2а-е иллюстрируют этапы процесса (фиг. 1), реализуемые в образцовой сети.

Следует отметить, что на всех сопроводительных чертежах одинаковые признаки идентифицированы одинаковыми позициями.

ПОДРОБНОЕ ОПИСАНИЕ ПРЕДПОЧТИТЕЛЬНОГО ВАРИАНТА ОСУЩЕСТВЛЕНИЯ

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

В первую очередь, следует отметить, что способ настоящего изобретения применим для сетей, в которых вычисленные кратчайшие пути являются симметричными (то есть, сеть можно представить в виде неориентированного графа), и если два или более путей равной стоимости можно вычислить между любыми двумя узлами, то должен быть реализован способ разрыва связей, который будет выбирать один из путей равной стоимости, таким способом, чтобы выбранные "кратчайшие" пути были симметричными и локально последовательными. В этом отношении, "локально последовательный" означает, что любой субпуть пути равной стоимости, выбранный способом разрыва связей, должен непосредственно быть кратчайшим путем, который выбран способом разрыва связей. Образцовый способ разрыва связей, который можно использовать в сочетании со способами настоящего изобретения, известен из совместно поданной заявителем заявки на патент США № 11/964,478, которая была зарегистрирована 26 декабря 2007 года.

Фиг. 1 является блок-схемой последовательности операций способа, иллюстрирующей основные этапы в способе, согласно образцовому варианту осуществления настоящего изобретения, и фиг. 2а-е иллюстрируют этапы в процессе (фиг. 1), реализованные в образцовой сети.

В отношении первого фиг. 2а, образцовая сеть PLSB содержит множество узлов (отмеченных как узлы А-R), соединенных между собой каналами связи. Обычно в сети PLSB, каждый узел в сети (фиг.2а-е) подсоединен, по меньшей мере, к двум другим узлам, хотя это не существенно. Предпочтительно, способ настоящего изобретения будет реализован для исполнения в каждом узле по существу параллельно. В следующем ниже описании, в качестве примера описан способ, по которому идентифицируют кратчайшие пути, проходящие через узел "А".

Как показано на фиг. 1 и 2b, на первом этапе вычисляют связующее дерево от узла "А" до каждого другого узла в сети, например, с использованием известного алгоритма построения дерева кратчайших путей, такого как алгоритм Де'йкстры. Как видно на фиг. 2b, связующее дерево (указанное жирными линиями на фиг. 2b-е) содержит множество ветвей, проходящих от узла "А" до каждого из своих ближайших соседей (узлы В, С, D и Е). Благодаря построению все из узлов сети находятся на одной из этих ветвей. Таким образом, можно умозрительно разделить сеть на набор секторов, каждый из которых окружает соответствующую ветвь связующего дерева.

Поэтому после построения каждый сектор будет включать в себя соответствующий один из соседних узлов и все из узлов, которые противолежат этому соседнему узлу на связующем дереве. Для удобства описания на каждую ветвь/сектор можно сослаться с использованием идентификатора соответствующего соседнего узла, который служит в качестве корня этой ветви. Таким образом, на фиг. 2с четыре сектора идентифицированы как секторы "В", "С", "D" и "Е", следуя идентичности своих соответствующих корневых узлов.

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

Дополнительное уменьшение количества узлов, которые должны быть проверены, можно получить путем распознавания того, что кратчайший путь между любым узлом в одном секторе и любым узлом в любом другом секторе не будет проходить через узел "А", если и только если существует путь между соответствующими корневыми узлами вовлеченных секторов, которые короче двухскачкового пути через узел "А". Например, рассмотрен путь между узлами М и R в варианте осуществления (фиг. 2), которые соответственно расположены в секторах "D" и "Е". В этом примере будет только рассматриваться количество скачков в качестве критерия кратчайшего пути, хотя другие критерии применимы в равной степени. Проверка сети показывает, что корневые узлы "D" и "Е" непосредственно соединены каналом связи. Следовательно, кратчайший путь между узлами М и R проходит только через корневые узлы "D" и "Е" и не проходит через узел "А". Рассмотрение других узлов в секторах "D" и "Е" показывает, что хотя не все из кратчайших путей (между узлом в секторе "D" и узлом в секторе "Е") проходят через прямой канал связи между корневыми узлами "D" и "Е", наличие этого прямого канала связи гарантирует, что ни один из этих кратчайших путей не пройдет через узел "А". Соответственно, сектора "D" и "Е" можно объединить в один суперсектор "DE" с целью вычислений в "А".

Этот процесс идентификации кратчайших путей между парами корневых узлов в паре рассматриваемых секторов или суперсекторов и объединения секторов всякий раз, когда найдено достаточное количество кратчайших путей, можно повторять до тех пор, пока все из секторов не будут объединены в один суперсектор (который фактически окружает всю сеть, за исключением узла "А") или не будет больше пар секторов, для которых все корневые узлы были соединены между собой путями, которые были короче, чем двухскачковые пути через узел "А". Можно ли объединить два сектора, можно определить путем рассмотрения корневых узлов в предложенном объединенном секторе. В простом случае пара секторов, каждый из которых имеет один корневой узел, два сектора можно объединить, если и только если соответствующие корневые узлы двух секторов соединены более коротким путем, чем двухскачковый путь через узел "А". Для более сложного случая сектор, имеющий один корневой узел, и суперсектор, имеющий N (где N>1) корневых узлов, два сектора можно объединить вместе, если ни один из кратчайших путей между корневым узлом сектора и N корневыми узлами суперсектора не пройдет через узел "А".

Таким образом, продолжая рассматривать пример на фиг.2d и продолжая использовать количество скачков в качестве критерия кратчайшего пути, сектор "В" можно объединить с суперсектором "DE" (имеющим N=2 корневых узла) для получения суперсектора "BDE", так как корневой узел "В" непосредственно подсоединен к двум корневым узлам суперсектора "DE". Это гарантирует, что отсутствует кратчайший путь между любой парой из узлов в суперсекторе "BDE", который проходит через узел "А". С другой стороны и, ссылаясь на фиг. 2е, сектор "С" нельзя объединить с суперсектором "BDE", так как нет прямого канала связи между корневым узлом "С" и корневым узлом суперсектора "BDE". Действительно, сектор "С" нельзя объединить с сектором "Е" или любым суперсектором, включающим в себя сектор "Е".

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

Будет понятно, что преимущества, полученные за счет объединения секторов, зависят от топологии сети. В сценарии, в котором все секторы можно объединить в один суперсектор, который, следовательно, окружает всю сеть, количество узлов, которые должны быть проверены, равно нулю (после первоначальных затрат этапа секционирования). В более типичном сценарии, процесс объединения секторов приведет в результате к множеству секторов и/или суперсекторов. В особом случае, в котором узел "А" является узлом с двухсторонней связью, первоначальное количество секторов равно двум. Если эти два сектора можно успешно объединить, количество узлов, которые должны быть впоследствии проверены, уменьшается до нуля. В противном случае, в худшем случае, количество узлов, которые должны быть проверены, немного меньше половины количества узлов в сети, которая тем не менее имеет существенное усовершенствование по сравнению с известными способами.

Как известно в технике, способы вычисления маршрутов, такие как промежуточная система - промежуточная система (IS-IS), открой кратчайший путь первым (OSPF) и многоадресный OSPF, позволяют выполнить многочисленные пути равной стоимости между парами узлов. В таким случаях, вышеописанный способ объединения секторов можно использовать без модификации в случаях, где "стоимость" каждого пути пропорциональна количеству скачков или "стоимость" прямого канала связи между двумя секторами меньше "стоимости" двухскачкового пути через узел, представляющий интерес (узел "А" на примере фиг. 2).

Алгоритм разрыва связей должен быть использован для выбора "кратчайшего" пути или поднабора кратчайших путей среди набора путей равной стоимости между парой узлов. В таких случаях, вышеописанный способ объединения секторов можно использовать при условии, что "кратчайший" путь(и), выбранный алгоритмом разрыва связей, является симметричным и локально последовательным.

Например, в сети (фиг. 2) рассмотрен сценарий, в котором способы вычисления маршрутов приводят к трем путям равной стоимости между узлами "С" и "Е", и алгоритм разрыва связей используется для выбора одного из этих путей равной стоимости в качестве "кратчайшего" пути. В этом случае, вышеописанные способы можно использовать для объединения сектора "С" с суперсектором "BDE", если способ разрыва связей выбирает в качестве кратчайшего пути один из двух путей через узлы "В" или "D", но не путь через узел "А".

Как может быть оценено, эта одинаковая методология может быть расширена до случая, где алгоритм вычисления маршрутов вычисляет набор путей равной стоимости, и механизм разрыва связей работает для выбора поднабора двух или более из этих путей равной стоимости в качестве кратчайших путей. В этом случае, критерий для объединения двух секторов заключается в том, что ни один из выбранных кратчайших путей не проходит через рассматриваемый узел. Таким образом, например, механизм разрыва связей может потенциально выбирать любые два из путей между узлами "С" и "Е" в качестве набора кратчайших путей, и вышеописанные способы можно использовать для объединения сектора "С" с суперсектором "BDE", если этот набор кратчайших путей не включает в себя путь через узел "А".

Вариант(ы) осуществления изобретения, описанный(е) выше, предназначен(ы) только для примера. Поэтому имеется в виду объем изобретения, который будет ограничен только объемом прилагаемой формулы изобретения.