Способ маршрутизации виртуальных соединений в сети с коммутацией кадров

Изобретение относится к области маршрутизации в сети с коммутацией кадров, а именно к сетям AFDX, и может быть использовано для маршрутизации виртуальных соединений в сети с коммутацией кадров. Техническим результатом является предоставление систематического и автоматического процесса маршрутизации, в котором учитываются все ограничения маршрутизации и которые позволяют безопасно использовать оптимизируемую сеть. Способ маршрутизации виртуальных соединений в сети с коммутацией кадров, включающий в себя множество терминалов источника и/или назначения упомянутых кадров, в котором коммутаторы кадра соединены друг с другом с помощью физических соединений, при этом каждое виртуальное соединение определено для типа из точки в точку с помощью пути через упомянутую сеть между терминалом источника и терминалом назначения и для многоточечного типа с использованием множества путей через упомянутую сеть между терминалом источника и множеством терминалов назначения, и выполняет маршрутизацию соединений, путем минимизации, по меньшей мере, одной функции стоимости по набору решений, удовлетворяющих, по меньшей мере, одному заданному топологическому ограничению. 24 з.п. ф-лы, 15 ил.

 

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

Изобретение относится к области маршрутизации в сети с коммутацией кадров и, более конкретно, к сети AFDX (АПДК).

Уровень техники

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

В коммутируемой сети Ethernet каждый терминал источника или назначения соединен индивидуально с коммутатором кадра, и эти коммутаторы соединены друг с другом с помощью физических соединений. Более конкретно, каждый коммутатор имеет множество портов, соединенных с портами других коммутаторов или соединителей терминала. Виртуальное соединение между терминалом источника и терминалом назначения определено как путь через сеть, по которому из терминала источника передают кадры, предназначенные для терминала назначения. Аналогично, виртуальное соединение определено по списку коммутаторов, через которые эти кадры пропускают. Для каждого коммутатора, через который пропускают кадры, выполняют коммутацию кадров на основе адреса назначения с использованием заранее установленной таблицы коммутации. Такая таблица коммутации является очень простой, поскольку в ней обозначен, на основе входного порта коммутатора и адреса назначения кадра, соответствующий выходной порт.

Другой хорошо известный пример сети с коммутацией кадров представляет собой сеть ATM (АРП, протокол асинхронного режима передачи данных), в которой может быть установлено соединение по виртуальному каналу (VCC, CBK) для направления основных кадров или ячеек между терминалами источника и назначения.

Здесь используется термин "виртуальное соединение" для обозначения полного соединения уровня 2 в сети с коммутацией кадров, такого как виртуальное соединение в коммутируемой сети Ethernet или соединение виртуальных каналов в сети АРП. В сети с коммутацией кадров виртуальные соединения направляют через сеть, либо административно, или используя сигналы с планом управления. Маршрутизация соединений состоит в определении и программировании таблиц коммутации различных коммутаторов в сети. В общем, такие таблицы коммутации могут быть статичными (административная маршрутизация) или динамичными (маршрутизация по сигналам).

В некоторых случаях возможно получить определенную гарантию или услугу с помощью виртуального соединения. Например, в сети АРП, класс услуги CBR (ПСБ, постоянная скорость передачи битов) обеспечивает постоянную полосу пропускания и минимальную скорость потока, которые зарезервированы для соединения. Однако, поскольку коммутаторы могут поддерживать только определенную максимальную скорость потока, гарантия этой услуги накладывает ограничения на маршрутизацию соединения.

Аналогично, сеть AFDX (АПДК, Авиационная полнодуплексная коммутируемая Ethernet), разработанная для применения в авиации, представляет собой коммутируемую сеть Ethernet, в которой возможно резервировать полосу пропускания для виртуального соединения. Более конкретно, каждое виртуальное соединение ассоциировано с минимальным интервалом между кадрами, а также с максимальным размером кадра. Кроме того, для каждого виртуального соединения гарантируется максимальное время маршрутизации кадров или время ожидания. Учитывая, что коммутаторы могут обеспечить только определенную скорость потока на каждый выходной порт, гарантия характеристик виртуального соединения снова подвергается ограничениям маршрутизации.

В настоящем изобретении предпочтительно, но не исключительно, применяют сети АПДК. Подробное описание этой сети можно найти в документе под названием "AFDX protocol tutorial", доступном на веб-сайте www.condoreng.com, а также в заявке на патент FR-A-2832011, поданной от имени настоящего заявителя. Ее основные характеристики будут просто в краткой форме представлены ниже.

Как упомянуто выше, сеть АПДК основана на коммутируемой сети Ethernet. Она также представляет собой полнодуплексную сеть, в которой каждый терминал может одновременно передавать и принимать кадры по различным виртуальным соединениям. Сеть АПДК также является детерминированной, в том смысле, что виртуальные соединения имеют гарантированные характеристики в том, что касается времени задержки, физической сегрегации потоков, полосы пропускания и скорости потока. Каждое виртуальное соединение, таким образом, имеет путь, зарезервированный для полного пути, времени фрагментации на интервалы передачи (называемые BAG (ЗВП) или зазор выделения полосы пропускания), и с максимальным размером кадра. Кадры передают в начале каждого интервала передачи с заданным допуском на флуктуации. В конечном итоге сеть АПДК получается избыточной, в том смысле, что она дублирована по причинам ее доступности.

Данные передают в форме IP (МП, межсетевой протокол) пакетов, инкапсулировавших в кадры Ethernet. В отличие от классической коммутации Ethernet (с использованием адреса назначения Ethernet), для коммутации кадров в сети АПДК используют виртуальный идентификатор соединения, соединенный с заголовком кадра. Когда коммутатор принимает кадр в одном из своих входных портов, он считывает виртуальный идентификатор соединения и определяет на основе его таблицы коммутации выходной порт (порты), через который его следует передать. Во время полета коммутаторы проверяют целостность передаваемых кадров, но не запрашивают повторную передачу, если кадр будет неправильным: кадры, детектируемые как неправильные, удаляют. Кадры, передаваемые по виртуальному соединению, нумеруют по порядку следования. После приема терминал назначения проверяет целостность последовательности кадров.

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

На фиг.1 схематично представлена сеть АПДК, включающая в себя терминалы LRU1-LRU5 и коммутаторы SW1, SW2 кадров. Можно видеть, что виртуальное соединение VL₃, соединяющее терминал LRU3 с LRU2, представляет собой соединение двухточечного типа, в то время как виртуальное соединение VL₂, обслуживающее LRU2 и LRU3, а также VL1, которое обслуживает LRU3-LRU5, представляют собой соединения многоточечного типа.

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

Сети с коммутацией кадров, которые предлагают гарантию услуги, такие как сети АРП и АПДК, требуют наложения ограничений маршрутизации по виртуальным каналам. Кроме того, бортовые приложения, в частности приложения для аэронавтики, требуют, чтобы были предприняты дополнительные меры предосторожности, что, в свою очередь, приводит к ограничениям маршрутизации.

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

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

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

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

(b) определяют среди упомянутого поднабора пути для виртуального соединения из точки в точку, или множество путей для многоточечного виртуального соединения, минимизацию, по меньшей мере, одной заданной функции стоимости;

(c) выполняют маршрутизацию упомянутого виртуального соединения в соответствии с путем (путями), определенным таким образом.

В соответствии с первой альтернативой, когда упомянутое виртуальное соединение представляет собой соединение из точки в точку, и сеть разделена на отдельные зоны, упомянутое топологическое ограничение, предпочтительно, выражено как ограничение, запрещающее переход между зонами, если коммутаторы, соединенные, соответственно, с терминалом источника и терминалом назначения, принадлежат одной и той же зоне, и, в противном случае, представляет собой ограничение, позволяющее один переход между зонами, принадлежащими, соответственно, упомянутым терминалам источника и назначения. На этапе выбора можно учитывать дополнительные топологические ограничения сегрегации и/или совместного размещения возможных путей относительно виртуальных соединений, маршрут по которым уже проложен или будет проложен одновременно с упомянутым соединением, или коммутаторами упомянутой сети. В качестве альтернативы, или совместно с этим, этап выбора может учитывать дополнительные топологические ограничения, в которых каждое дополнительное топологическое ограничение относится к группе путей, формирующих набор виртуальных соединений, маршрут по которым должен быть проложен одновременно, в котором упомянутую группу составляют из множества N_sg подгрупп упомянутых путей, и упомянутое дополнительное ограничение выражает, что, самое большее, количество n_sg подгрупп, такое, что 0≤n_sg<N_sg, может быть сделано недействительным, при этом подгруппу делают недействительной, если на все пути, принадлежащие ей, влияет отказ одного и того же коммутатора упомянутой сети.

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

В соответствии со второй альтернативой, когда упомянутое виртуальное соединение представляет собой соединение многоточечного типа, и сеть разделена на отдельные зоны, ограничения, запрещающие переход между зонами, предпочтительно применяют к каждому возможному пути между упомянутым терминалом источника и терминалом назначения упомянутого соединения, если коммутаторы, соединенные, соответственно, с терминалом источника и с упомянутым терминалом назначения, принадлежат одной зоне, и, в противном случае, применяют ограничение, позволяющее одиночный переход между зонами, принадлежащими, соответственно, упомянутым терминалам источника и назначения. Как упомянуто выше, для каждого из возможных путей между упомянутым терминалом источника и терминалом назначения упомянутого соединения возможно применять дополнительные топологические ограничения сегрегации и/или совместного размещения этих путей относительно виртуальных соединений, маршрут по которым уже проложен или будет проложен одновременно с упомянутым соединением или коммутаторами. В качестве альтернативы, или совместно с этим, на этапе выбора можно учитывать дополнительные топологические ограничения, в которых каждое дополнительное топологическое ограничение относится к группе путей, формирующих набор виртуальных соединений, маршрут по которым должен быть проложен одновременно, в котором упомянутую группу составляют из множества N_sg подгрупп упомянутых путей, и упомянутые дополнительные ограничения выражают то, что, самое большее, количество n_sg подгрупп такое, что 0≤n_sg<N_sg, может быть сделано недействительным, при этом подгруппу делают недействительной, если на все пути, принадлежащие ей, влияет отказ одного и того же коммутатора упомянутой сети.

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

В соответствии с третьей альтернативой, по меньшей мере, для одной группы соединений, вовлеченных в выполнение одной и той же функции, называемой связкой соединений, причем каждое соединение представляет собой соединение из точки в точку, и сеть разделена на отдельные зоны, применяют ограничение, запрещающее переход между зонами, для каждого из соединений упомянутой связки, для каждого возможного пути между терминалом источника и терминалом назначения упомянутого соединения, если коммутаторы, соединенные, соответственно, с терминалом источника и терминалом назначения, принадлежат одной и той же зоне, и, в противном случае, применяют ограничение, разрешающее один переход между зонами, принадлежащими, соответственно, упомянутым терминалам источника и назначения. Как упомянуто выше, возможно применять для каждого виртуального соединения и для каждого из возможных путей между терминалом источника и терминалом назначения упомянутого соединения дополнительные топологические ограничения сегрегации и/или совместного размещения этих путей относительно виртуальных соединений, маршрут по которым уже проложен или будет проложен одновременно с упомянутым соединением или коммутаторами. В качестве альтернативы, или совместно с этим, этап выбора может учитывать дополнительные топологические ограничения, в которых каждое дополнительное топологическое ограничение относится к группе путей, формирующих набор виртуальных соединений, маршруты по которым должны быть проложены одновременно, в котором упомянутая группа составлена из множества N_sg подгрупп упомянутых путей, и упомянутое дополнительное ограничение выражает то, что, самое большее, количество n_sg подгрупп такое, что 0≤n_sg<N_sg может быть сделано недействительным, причем подгруппу делают не действительной, если на все пути, принадлежащие ей, влияет отказ одного и того же коммутатора упомянутой сети.

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

В соответствии с четвертой альтернативой, по меньшей мере, для одной группы соединений, вовлеченных в выполнение одной и той же функции, называемой связкой соединений, причем каждое соединение представляет собой соединение многоточечного типа, и сеть разделена на отдельные зоны, применяют ограничения, запрещающие переход между зонами для каждого из соединений упомянутой связки, для каждого возможного пути между терминалом источника и терминалом назначения упомянутого соединения, если коммутаторы, подключенные, соответственно, к терминалу источника и к терминалу назначения, принадлежат одной зоне, и, в противном случае, применяют ограничение, разрешающее один переход между зонами, принадлежащими соответственно упомянутым терминалам источника и назначения. Как упомянуто выше, возможно применять для каждого виртуального соединения и для каждого из возможных путей между терминалом источника и терминалом назначения упомянутого соединения дополнительные топологические ограничения сегрегации и/или совместного размещения этих путей относительно виртуальных соединений, по которым уже был проложен маршрут или по которым должен быть проложен маршрут одновременно с упомянутым соединением или коммутаторами упомянутой сети. В качестве альтернативы, или совместно с этим, этап выбора может учитывать дополнительные топологические ограничения, в которых каждое дополнительное топологическое ограничение относится к группе путей, формирующих набор виртуальных соединений, маршрут по которым должен быть проложен одновременно, в котором упомянутую группу составляют из множества N_sg подгрупп упомянутых путей, и упомянутое дополнительное ограничение выражает, что, самое большее, количество n_sg подгрупп такое, что 0≤n_sg<N_sg, может быть сделано недействительными, при этом подгруппу делают недействительной, если на все пути, принадлежащие ей, влияет отказ одного и того же коммутатора упомянутой сети.

Упомянутую функцию стоимости можно выбрать так, чтобы она равнялась количеству коммутаторов, которые пересекает путь, и будет минимизирована для каждого из соединений упомянутой связки по каждому набору возможных путей между терминалом источника и терминалом назначения упомянутого соединения, для обеспечения, по меньшей мере, одного пути-кандидата на соединение и на терминал назначения. Предпочтительно, формируют комбинации K₁+K₂+…+K_N путей-кандидатов, где K_i, 1<i≤N - представляют собой номера соответствующих путей среди N соединений упомянутой связки, при этом каждая комбинация соответствует возможному решению прокладки маршрута в упомянутой связке, и четвертую функцию стоимости минимизируют по набору упомянутых возможных решений, полученных таким образом. Четвертая функция стоимости оценивает для каждого возможного решения маршрутизации связки количество коммутаторов, которые пересекают соединения связки, соответствующей этому решению.

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

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

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

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

на фиг.1 схематично показан пример сетей АПДК;

на фиг.2 схематично показана блок-схема организации способа маршрутизации виртуального соединения в соответствии с вариантом воплощения настоящего изобретения;

на фиг.3A-3E показан механизм минимизации функции стоимости в случае многоточечного виртуального соединения;

на фиг.4 показан пример маршрутизации для виртуального соединения из точки в точку;

на фиг.5 показан пример маршрутизации для многоточечного виртуального соединения;

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

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

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

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

на фиг.10A и 10B, соответственно, показаны приемлемая конфигурация маршрутизации и неприемлемая конфигурация маршрутизации.

Подробное описание изобретения

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

На фиг.2 представлен принцип способа маршрутизации в соответствии с изобретением.

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

- файл 210, описывающий топологию сети, а именно конечные узлы (терминалы), коммутирующие узлы и физические соединения между узлами;

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

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

- файл 240, устанавливающий топологические ограничения, который будет подробно описан ниже.

Алгоритм предполагает, на первом этапе 250, выбор путей между терминалом источника и терминалом назначения, которые удовлетворяют ограничению или множеству топологических ограничений, обозначенных в 240.

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

Если минимизация функции (функций) стоимости дает множество эквивалентных решений, одно решение выбирают из них произвольно. Решение в конце этапа 260 предоставляет путь (режим из точки в точку) или пути (многоточечный режим), позволяющие проложить маршрут по виртуальному соединению. На этапе 270 обновляют файл состояния сети 220. Алгоритм итерационно продолжается до тех пор, пока не закончатся виртуальные соединения, которые требуют маршрутизации.

На этапе 280 проверяют, что все виртуальные соединения маршрутизированы, и, если это так, в соответствии с вариантом воплощения, на этапе 290 выполняют этап проверки детерминизма сети. Этим этапом управляют с помощью алгоритма, называемого "сетевым исчислением", известного из предшествующего уровня техники, например, из статьи автора Jean-Yves Le Boudec, под названием "Application of network calculus to guaranteed service networks", published in IEEE Trans, on Information Theory, Vol.44, n°3, May 1998. Этот алгоритм вычисляет на основе огибающей трафика во всех точках сети терминалы латентности и размеры очередей для каждого элемента сети. Детерминизм гарантирован для связанной латентности и правильного определения размеров очередей каждого элемента сети.

Наконец, таблицы коммутации коммутаторов кадра обновляют на этапе 295. Эти таблицы коммутации однозначно устанавливают маршрут соединений по сети.

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

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

Абсолютные ограничения взвешивают маршруты виртуального соединения, независимо от присутствия других соединений в сети. Например, в случае сети АПДК на борту самолета, "левая" и "правая" "стороны" сети, соответствующие "левой" и "правой" сторонам самолета, получают питание по разным шинам питания. Таким образом, что отказ одного источника питания не представляет опасности для всей сети, при этом накладываются следующие топологические ограничения:

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

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

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

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

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

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

Рассматривают набор виртуальных соединений, в котором одновременно выполняют маршрутизацию, поскольку их отдельные независимые маршруты не могут быть рассмотрены. Каждое из этих виртуальных соединений, в общем, включает в себя один (соединение из точки в точку) или больше (многоточечное соединение) путь (путей). Все пути, формирующие эти виртуальные соединения, ниже называемые группой виртуальных соединений, могут быть разделены на подгруппы, при этом путь может принадлежать множеству подгрупп. Обычно подгруппа соответствует экземпляру функции, предусмотренной упомянутым набором виртуальных соединений. Другими словами, различные подгруппы представляют определенную степень избыточности для рабочих характеристик при выполнении одной функции.

Если N_sg представляет собой количество подгрупп в группе путей, ослабленное ограничение сегрегации накладывают на упомянутый набор виртуальных соединений, в соответствии с которым, самое большее, n_sg подгрупп из N_sg, когда 0≤n_sg<N_sg, могут быть сделаны недействительными в результате отказа коммутатора. Случай n_sg=0 соответствует специфичной ситуации, в которой не допускается ни одной недействительной подгруппы. Под отказом коммутатора подразумевают либо работающий с ошибками, или отсутствующий коммутатор, или нарушение коммутируемых кадров. Под недействительными подгруппами подразумевают подгруппу, в которой на все пути влияет отказ одного и того же коммутатора.

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

Примеры ослабленных ограничений сегрегации представлены в приложении.

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

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

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

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

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

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

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

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

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

На фиг.3A-3E показан механизм для минимизации функции стоимости в случае многоточечного виртуального соединения.

Виртуальное соединение, по которому должен быть проложен маршрут, проходит из терминала E₁ источника и обслуживает терминалы R₁ и R₂ назначения. Оно предполагает, что пути, удовлетворяющие топологическим ограничениям, были предварительно выбраны. Минимизацию первой функции стоимости выполняют путем поиска среди каждого из возможных путей, соединяющих E₁ с R₁ и E₁ с R₂, для путей, которые пересекают минимальное количество коммутаторов. В этом случае минимальное количество равно 3 для пути E₁-R₁, а также для пути E₁-R₂. Оптимальные решения представлены на фиг.3A-3D. Однако следует отметить, что решение, показанное на фиг.3E, не является оптимальным: действительно, оно минимизирует количество коммутаторов по всему виртуальному соединению, но не в каждом из его составляющих путей (путь, соединяющий E₁-R₂, имеет стоимость 4).

Минимизация второй функции стоимости означает, что помимо четырех предыдущих решений оставляют те, которые показаны на фиг.3A, 3B и 3D. Действительно, для этих случаев, количество общих коммутаторов между двумя путями равно 1, в то время как оно равно 2 для фигуры 3C.

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

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

где b^T представляет собой вектор, представляющий линейную форму (функцию стоимости), x представляет собой вектор переменных принятия решения (положительные), A представляет матрицу ограничений, и с представляет постоянный вектор.

На практике, алгоритм маршрутизации использует в качестве входных данных список коммутаторов, отмеченный SS и, для каждой пары терминалов источника и назначения, список путей, позволяющих перейти из первого во второй, при этом каждый путь описан в виде упорядоченного списка коммутаторов, через которые он проходит. Ниже PP обозначает список индексированных путей. Предпочтительно, РР предварительно был уменьшен до списка путей, уже удовлетворяющих определенным абсолютным топологическим ограничениям, например путей, относящихся к разделению на независимые зоны.

Затем генерируют матрицы C_ps, C_fs, C_ls, C_pss, причем первые три имеют размеры PxS, и последние имеют размеры PxSxS, где P представляет собой общее количество путей, индексированных в файле, и S представляет собой общее количество коммутаторов в сети, при этом элементы этих матриц определены по:

C_ps (p, sw)=1, если sw принадлежит пути p, и c_ps (p, sw)=0, если нет;

C_fs (p, sw)=1, если sw представляет собой первый коммутатор p и C_fs (p, sw)=0, если нет;

C_1s (p, sw)=1, если sw представляет собой последний коммутатор p и c_1s (p, sw)=0, если нет;

C_pss (p, sw₁, sw₂)=1, если sw₁ и cw₂ представляют собой последовательные коммутаторы пути p и c_pss (p, sw₁, sw₂)=0, если нет;

где p представляет собой идентификатор пути между двумя терминалами, и где sw, sw₁, sw₂ представляют собой идентификаторы коммутаторов сети.

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

Связку f для FF определяют по ее атрибутам:

- f.profile обозначает, содержит ли связка f отдельное виртуальное соединение {f.profile=1) или нет (f.profile=0);

- f.ocs предоставляет идентификаторы списка виртуальных соединений, принадлежащих связке.

Виртуальное соединение vl связки f определено по его атрибутам:

- vl.f предоставляет идентификатор связки, которой принадлежит соединение;

- vl.cost обозначает стоимость с учетом трафика по виртуальному соединению; эта стоимость может быть выражена как трафик виртуального соединения; эта стоимость может быть выражена, например, как функция пары интервала передачи и максимальной длины кадра;

- vl.rted обозначает, был ли уже проложен маршрут по этому соединению (vLrted=1) или нет (vLrted=0);

vl.txsw задает идентификатор для коммутатора, подключенного к терминалу источника;

vl.rxsw задает идентификатор для коммутатора, подключенного к терминалу назначения (соединение из точки в точку), или идентификаторы или коммутаторы, соответственно, подключенные к терминалам назначения (многоточечное соединение).

Путь b, формирующий виртуальное соединение vl, определен по его атрибутам:

- b.vl идентификатор виртуального соединения, которому он принадлежит;

- b.swDest идентификатор коммутатора, подключенного к терминалу назначения, обслуживаемому упомянутым путем.

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

- атрибуту g.sgErrmax, обозначающему максимальное приемлемое количество подгрупп, сделанных недействительными в группе;

- списку его подгрупп g.sglist.

Наконец, SG обозначает список подгрупп, относящихся к различным группам GG. Каждая подгруппа sg из SG определена по:

- атрибуту sg.group, обозначающему группу, которой она принадлежит;

- список sg.pathlist путей, формирующих эту подгруппу.

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

- vlPath[vl, p] равна 1, если путь p формирует виртуальное соединение vl, и равна 0, если нет. Следует отметить, что путь р формирует vl, если этот путь выходит из коммутатора, подключенного к терминалу vl.txsw, и поступает в один из коммутаторов vl.rxsw;

vlBrSw [vl, swDest, sw] равна 1, если путь, формирующий виртуальное соединение vl, оканчивающийся swDest, переходит через коммутатор sw, и равна 0, если нет;

vlBrPerSw [vl, sw] равна количеству путей, формирующих виртуальное соединение vl, проходящее через коммутатор sw;

comBrSw [vl, sw] равна 1, если множество путей, формирующих виртуальное соединение vl, проходит через коммутатор sw;

- vlSw [vl, sw] равна 1, если виртуальное соединение vl проходит через коммутатор sw, и равна 0, если нет;

- fvlPerSw [f, sw] равна количеству виртуальных соединений функциональной связки f, проходящей через коммутатор sw;

comfSw [f, sw] равна 1, если множество виртуальных соединений функциональной связки f проходит через коммутатор sw, и равна 0, если нет;

- fSw [f, sw] равна 1, если одно из виртуальных соединений функциональной связки f проходит через коммутатор sw, и равна 0, если нет;

- vlSwNb [vl, sw₁, sw₂] равна количеству путей, формирующих виртуальное соединение vl, проходящее последовательно через коммутаторы sw₁, sw₂;

- vlSw [vl, sw₁, sw₂] равна 1, если имеется путь, формирующий виртуальное соединение vl, проходящее последовательно через коммутаторы sw₁, sw₂;

- trfCst [sw₁, sw₂], представляет собой сумму trfCstPast [sw₁, sw₂] и стоимость трафика между коммутаторами sw₁, sw₂, накопленную по текущему поднабору виртуальных соединений для маршрутизации;

- fixvl [sw₁, sw₂] равна 1, если существует виртуальное соединение, по которому уже проложен маршрут из упомянутого текущего поднабора, проходящего последовательно через коммутаторы sw₁ и sw₂, и равна 0, если нет;

- sgSw [sg, sw] равна 1, если коммутатор sw является общим для всех путей, формирующих подгруппу sg, и равна 0, если нет.

Основное ограничение, которое накладывают на решение (или кандидат виртуального соединения) состоит в том, что путь (пути), формирующие решение, проходит из терминала источника и заканчивается в терминале назначения, то есть:

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

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

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

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

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

В качестве альтернативы, если ослабленные ограничения сегрегации используют, для какой-либо группы g∈GG, должны присутствовать пути, формирующие виртуальные соединения, к которым прикладывают такое ограничение:

в котором переменная sgSw [sg, sw] принятия решения определена следующими ограничениями:

и

при

Выражение (5'') фактически означает:

и

если нет.

Функции стоимости также выражены на основе упомянутых выше переменных принятия решения.

Например, первая функция CF₁ стоимости, предназначенная для минимизации количества коммутаторов, которые пересекают пути, формирующие виртуальное соединение, может быть выражена по:

где card (p) представляет собой количество элементов пронумерованного списка p, другими словами, количество коммутаторов, которые пересекают путь p.

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

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

Также возможно показать, что четвертая функция стоимости, предназначенная для минимизации количества коммутаторов, которые пересекают соединения функциональной связки, может быть просто выражена по:

Пятая функция стоимости предназначена для маршрутизации виртуальных соединений таким образом, чтобы они проходили через коммутаторы с самой меньшей нагрузкой. При этом на основе файла состояния сети и соединений для маршрутизации возможно определить стоимость трафика между двумя соседними коммутаторами. Термин "соседние коммутаторы" используют здесь для обозначения коммутаторов sw₁, sw₂, соединенных прямым физическим соединением. Более конкретно, вначале определяют, для каждой из пар соседних коммутаторов sw₁, sw₂, проходит ли, по меньшей мере, одно виртуальное соединение последовательно через них:

Переменная принятия решения vlSw [vl, sw₁, sw₂] выражена как функция vlSwNb [vl, sw₁, sw₂] с использованием следующих линейных ограничений:

Набор линейных ограничений фактически означает:

Аналогично переменная принятия решения fixvl [sw₁, sw₂] выражена как функция

суммы

с помощью следующих линейных ограничений:

при где

Этот набор линейных ограничений фактически означает:

Стоимость трафика выходного порта sw₁, соединенного с sw₂, затем оценивают для любой пары соседних коммутаторов:

где trfCstPast[sw₁,sw₂] представляет собой стоимость трафика между коммутаторами sw₁, sw₂, то есть, в выходном порту sw₁, подключенном к sw₂, накопленную для всех виртуальных соединений, по которым уже проложен маршрут.

Другими словами, расчет стоимости трафика выполняют для соединений, по которым уже проложен маршрут (vl.rted=1), и для соединений, по которым должен быть проложен маршрут (vl.rted=0). Значение trfCstPast [sw₁, sw₂] инициализируют по стоимости трафика, индуцированного фиксированными виртуальными соединениями, то есть для которых маршрутизация является однозначной. Оно может быть сохранено в файле состояния сети.

Пятая функция стоимости затем выражается следующим образом:

В результате наложения линейных ограничений:

;

при

Набор линейных ограничений действительно означает, для любой пары коммутаторов sw₁, sw₂:

Это позволяет рассматривать, в переменной trfCstw [sw₁, sw₂] принятия решения только вклад виртуальных соединений, по которым должен быть проложен маршрут, и среди них только те, которые проходят через sw₁, sw₂.

Если требуется выполнить совместную минимизацию функций стоимости, формируют новую функцию , линейную комбинацию функций CF_i (со взвешивающими коэффициентами 0≤α_i≤1. В конечном итоге, это представляет собой поиск функции CF минимальной стоимости, которая предоставляет оптимальное решение в отношении прокладки маршрута в форме значений решения. Если существует множество оптимальных решений в описанном выше смысле, одно из них выбирают произвольным образом.

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

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

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

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

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

На фиг.4 схематично показан пример маршрутизации виртуального соединения из точки в точку (или связки с одним соединением) между терминалом E₁ источника и терминалом R₁ назначения.

На этапе 410 основное ограничение применяют для определения возможных путей между терминалом источника и терминалом назначения.

На этапе 420 применяют относительные топологические ограничения, учитывая виртуальные соединения, маршруты которых уже были проложены, если они существуют, тогда на этапе 430 определяют, находятся ли терминалы с одной и той же стороны сети. Если это так, на этапе 435 применяют ограничение запрета перехода (маршрутизации внутри зоны), и функцию CF₁ стоимости минимизируют по набору возможных решений с учетом предыдущих ограничений. Однако, если терминалы не находятся с одной стороны сети, на этапе 437 применяют ограничение перехода (один переход между зонами), и, так же как и для первого случая, функцию CF₁ стоимости минимизируют по набору возможных решений.

Если этапы 435 или 437 не обеспечивают решение с одним маршрутом, обработку продолжают путем минимизации на этапе 440, функции CF₅ стоимости по остальным решениям. Файл статуса сети обновляют в 450.

На фиг.5 схематично показан пример маршрутизации виртуального соединения с множеством точек (или связки с одним соединением), между терминалом E₁ источника и множеством K терминалов R₁, R₂, …, R_K назначения.

Для каждой пары терминалов (E₁, R_K), в 510₁, 510₂, …, 510_K применяют основные ограничения с тем, чтобы оставить только возможные пути между E₁ и R₁, R₂, …, R_K.

На этапах 520₁, 520₂, …, 520_K относительные топологические ограничения применяют индивидуально к различным путям, учитывая соединения, для которых уже проложены маршруты.

В каждом из К наборов возможных путей функцию CF₁ стоимости индивидуально минимизируют в 530₁, 530₂, …, 530_K, соответственно.

Затем в 540 все комбинации путей, заданные в 530₁, 530₂, …, 530_K, формируют соответственно. Таким образом получают набор возможных решений маршрутизации для данного виртуального соединения.

На этапе 550 функцию CF₁ стоимости затем минимизируют по набору этих возможных решений.

Если этап 550 не обеспечивает единственное решение, на этапе 560 минимизируют функцию CF₄ стоимости по набору оставшихся решений.

Если этап 560 все еще не обеспечивает одно решение, функцию CF₅ стоимости минимизируют в 570 для набора остальных решений, и файл статуса сети обновляют в 580.

На фиг.6 схематично показан пример маршрутизации связки N виртуальных соединений из точки в точку.

Каждое соединение продолжается от терминала Е_i источника и обслуживает терминал R_i назначения, 1<i≤N.

Для каждой пары терминалов (E_i, R_i) в 610_i применяют основное ограничение для сохранения только путей, возможных между E_i и R_i.

Этапы 620_i, 630_i и 640 являются эквивалентами этапов 520_K, 530к, 540, за исключением того, что на этапе 640 все возможные решения маршрутизации получают для связки соединений.

Затем, на этапе 650, функцию CF₃ стоимости минимизируют по набору возможных решений.

Если этап 650 не обеспечивает единственное решение, на этапе 660 минимизируют функцию CF₄ стоимости по набору оставшихся решений.

Если этап 660 все еще не обеспечивает единственное решение, функцию CF₅ стоимости минимизируют на этапе 670 по набору оставшихся решений, и файл статуса сети обновляют на этапе 680.

На фиг.7 схематично показан пример маршрутизации связки N многоточечных виртуальных соединений. Предполагают, что каждое виртуальное соединение VL_i продолжается от терминала Е_i источника и обслуживает K_i терминалов R_ik назначения, причем 1<i≤N и 1<k<К_i.

На этапе 710_i применяют основное ограничение для всех пар терминалов (E_i, R_ik), 1<k≤K_i, тогда на 720i применяют относительные топологические ограничения, как на фиг.5.

В конце этапа 720_i K_i наборов P_ik возможных путей получают для формирования виртуального соединения VL, с набором P_ik, которое относится к заданной паре (E_i, R_ik).

На этапе 730_i функцию CF₁ стоимости минимизируют для каждого из этих наборов, как на этапах 530₁-530_K по фиг.5.

На этапе 740 формируют все возможные комбинации всех путей, содержащихся на этапе 730_i, учитывая то, что для каждой комбинации выбирают только один путь на пару (E_i, R_ik). Каждая комбинация, таким образом, соответствует K₁+K₂+…+K_N сохраняемых путей. Таким образом, получают набор возможных решений маршрутизации для различных виртуальных соединений VL_i, то есть набор возможных решений для маршрутизации связки.

Остальная часть организационной блок-схемы идентична представленной на фиг.6, и этапы 750, 760, 770 и 780, соответственно, идентичны этапам 650, 660, 670 и 680.

ПРИЛОЖЕНИЕ

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

На фиг.8 такая группа путей показана символически.

Предполагается, что по трем виртуальным соединениям VL₁, VL₂, VL₃ требуется проложить маршруты одновременно, и что их составляющие пути представляют собой:

;

;

В показанном примере группа GG путей, подвергаемых ослабленному ограничению сегрегации, разделена на N_sg=4 подгрупп , , , .

Ослабленное ограничение сегрегации выражено максимальным количеством n_sg<N_sg подгрупп, которые могут быть сделаны недействительными в результате отказа одного коммутатора (например, отказ коммутатора влияет на пути P¹ ₁, Р¹ ₂ для sg₁). Другими словами, по меньшей мере, каждая из N_sg-n_sg подгрупп должна содержать, по меньшей мере, один путь, который не был нарушен в результате отказа коммутатора.

Пример применения ослабленного ограничения сегрегации приведен ниже. Рассматривают маршрутизацию виртуальных соединений между системами управления полетом (FMS, СУП) и модулем управления и направления полета (FCGU, МУНП). Первая представляет собой классическую систему, ответственную за помощь пилоту при навигации и при выполнении операций управления полетом. Вторая рассчитывает направление и расположение при управлении полетом.

Предполагается, что самолет включает в себя две системы СУП и четыре калькулятора МУНП, причем каждая система СУП находится в источнике (многоточечного) виртуального соединения, предназначенного для четырех калькуляторов МУНП, как показано на фиг.9. Показанная архитектура представляет собой архитектуру "перекрестного контроля": каждый калькулятор МУНП принимает параметры полета из двух систем СУП и выполняет сравнение. Если параметры, принятые одним калькулятором, отличаются, калькулятор обозначает ошибку и не выполняет обработку по параметру. Требования безопасности определяют, что ошибка по параметру не должна оставаться недетектированной более чем одним калькулятором. α обозначает параметр или даже кадр таких параметров, передаваемых системами СУП, если предполагается, что они правильные, и обозначает неправильный параметр, или даже неправильный кадр параметров, принятых калькулятором МУНП, в котором ошибка происходит из-за отказа коммутатора.

Как показано в фиг.10A и 10B, калькулятор может не детектировать ошибку в случае двустороннего нарушения (случай FCGU_1A на фиг.10A и FCGU_1A и FCGU_2A на фиг.10B), когда два неправильных параметра/неправильных кадра идентичны. Такая ситуация не должна возникать для более чем одного калькулятора. Таким образом, ситуация, показанная на фиг.10А (одна не детектированная ошибка), является приемлемой, в то время как на фиг.10B (две не детектированных ошибки), она является не приемлемой.

Группа GG рассматривается как состоящая из путей, формирующих два виртуальных соединения, для которых требуется проложить маршруты:

и группа GG разделена на такое количество подгрупп, сколько имеется калькуляторов МУНП, то есть sg₁ sg₂, sg₃, sg₄, при этом каждая подгруппа содержит два пути из систем СУП, предназначенных для рассматриваемого калькулятора. Затем требуется, чтобы отказ коммутатора делал недействительным не более чем одну подгруппу (n_sg=1) среди 4 (N_sg=4).

Такое ослабленное ограничение сегрегации позволяет обеспечить то, что не более чем один калькулятор МУНП потеряет диагностику ошибки из-за отказа коммутатора сети.

1. Способ маршрутизации виртуальных соединений в сети с коммутацией кадров, включающей в себя множество терминалов источника упомянутых кадров, в котором коммутаторы кадров соединены друг с другом с помощью физических соединений, при этом каждое виртуальное соединение определено для типа из точки в точку путем через упомянутую сеть между терминалом источника и терминалом назначения и для многоточечного типа по множеству путей через упомянутую сеть между терминалом источника и множеством терминалов назначения, причем упомянутый способ отличается тем, что, по меньшей мере, для одного виртуального соединения он включает в себя следующие этапы:
(a) выбирают (250) из набора возможных путей между терминалом источника и терминалом (терминалами) назначения поднабор путей, удовлетворяющих, по меньшей мере, одному заданному топологическому ограничению;
(b) определяют (260) среди упомянутого поднабора путей для виртуального соединения из точки в точку или множество путей для многоточечного виртуального соединения минимизацию, по меньшей мере, одной заданной функции стоимости;
(c) выполняют маршрутизацию (295) упомянутого виртуального соединения в соответствии с путем (путями), определенным таким образом.

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

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

4. Способ маршрутизации по п.1, отличающийся тем, что на этапе выбора учитывают дополнительные топологические ограничения, в которых каждое дополнительное топологическое ограничение относится к группе путей, формирующих набор виртуальных соединений, маршруты которых должны быть проложены одновременно, в котором упомянутая группа составлена из множества N_sg подгрупп упомянутых путей, и упомянутые дополнительные ограничения выражают, что самое большее число n_sg подгрупп такое, что 0≤n_sg<N_sg, может быть сделано недействительным, при этом подгруппу делают недействительной, если на все пути, принадлежащие ей, влияет отказ одного и того же коммутатора упомянутой сети.

5. Способ маршрутизации по пп.2, 3 или 4, отличающийся тем, что упомянутая функция (440) стоимости представляет количество коммутаторов, которые пересекают данный путь.

6. Способ маршрутизации по п.1, отличающийся тем, что, когда упомянутое виртуальное соединение представляет собой соединение многоточечного типа и сеть разделена на различные зоны, ограничение (520₁, …, 520_K) запрещающее переход между зонами, применяют для каждого возможного пути между упомянутым терминалом источника и терминалом назначения упомянутого соединения, если коммутаторы, подключенные соответственно к упомянутым терминалу источника и терминалу назначения, принадлежат одной и той же зоне, и в противном случае применяют ограничение, разрешающее однократный переход между зонами, принадлежащими соответственно упомянутым терминалам источника и назначения.

7. Способ маршрутизации по п.6, отличающийся тем, что на этапах (520₁, …, 520_K) для каждого из возможных путей между упомянутым терминалом источника и назначения упомянутого соединения применяют дополнительные топологические ограничения сегрегации и/или совместного размещения этих путей относительно виртуальных соединений, для которых уже проложены маршруты или которые должны быть проложены одновременно с упомянутым соединением или коммутаторами.

8. Способ маршрутизации по п.6, отличающийся тем, что на этапе выбора учитывают дополнительные топологические ограничения, в которых каждое дополнительное топологическое ограничение относится к группе путей, формирующих набор виртуальных соединений, для которых должны быть проложены маршруты одновременно, в котором упомянутая группа состоит из множества N_sg подгрупп упомянутых путей, и упомянутые дополнительные ограничения выражают, что самое большее количество n_sg подгрупп такое, что 0≤n_sg<N_sg, могут быть сделаны недействительными, причем подгруппу делают недействительной, если на все пути, принадлежащие ей, влияет отказ одного и того же коммутатора упомянутой сети.

9. Способ маршрутизации по пп.6, 7 или 8, отличающийся тем, что упомянутая функция стоимости представляет собой количество коммутаторов, через которые проложен путь, и ее минимизируют (530₁ …, 530_K) по каждому набору возможных путей между упомянутым терминалом источника и терминалом назначения упомянутого соединения для обеспечения, по меньшей мере, одного пути - кандидата на терминал назначения.

10. Способ маршрутизации по п.9, отличающийся тем, что формируют (540) комбинации K путей-кандидатов, в котором K представляет собой количество терминалов назначения соединения, и каждая комбинация соответствует возможному решению маршрутизации упомянутого многоточечного соединения, и вторую функцию стоимости минимизируют (550) по набору упомянутых возможных, полученных таким образом решений.

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

12. Способ маршрутизации по п.1, отличающийся тем, что, по меньшей мере, для одной группы соединений, используемых при выполнении одной и той же функции, которая называется связкой соединений, каждое соединение представляет собой соединение из точки в точку, и сеть разделена на различные зоны, при этом ограничения, запрещающие переход между зонами, применяют для каждого из соединений упомянутой связки (620₁, …, 620_N), для каждого возможного пути между терминалом источника и терминалом назначения упомянутого соединения, если коммутаторы, соединенные соответственно с терминалом источника и терминалом назначения, принадлежат той же зоне, и в противном случае накладывают ограничение, позволяющее однократный переход между зонами, принадлежащими соответственно упомянутым терминалам источника и назначения.

13. Способ маршрутизации по п.12, отличающийся тем, что для каждого виртуального соединения и для каждого из возможных путей между терминалом источника и терминалом назначения упомянутого соединения накладывают (620₁, …, 620_K) дополнительные топологические ограничения сегрегации и/или совместного размещения этих путей относительно виртуальных соединений, для которых уже проложен маршрут или для которых должен быть проложен маршрут одновременно с упомянутым соединением или коммутаторами.

14. Способ маршрутизации по п.12, отличающийся тем, что на этапе выбора учитывают дополнительные топологические ограничения, в которых каждое дополнительное топологическое ограничение относится к группе путей, формирующих набор виртуальных соединений, для которых должен быть проложен маршрут одновременно, в котором упомянутая группа состоит из множества N_sg подгрупп упомянутых путей, и упомянутые дополнительные ограничения выражают, что самое большее число n_sg подгрупп такое, что 0≤n_sg<N_sg, может быть сделано недействительными, причем подгруппу делают недействительной, если на все пути, принадлежащие ей, влияет отказ одного и того же коммутатора упомянутой сети.

15. Способ маршрутизации по пп.12, 13 или 14, отличающийся тем, что упомянутая функция стоимости представляет собой количество коммутаторов, через которые проложен путь, и ее минимизируют (630₁, …, 630_N) для каждого из соединений упомянутой связки по каждому набору возможных путей между терминалом источника и терминалом назначения упомянутого соединения для обеспечения, по меньшей мере, одного пути-кандидата на соединение.

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

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

18. Способ маршрутизации по п.1, отличающийся тем, что, по меньшей мере, для одной группы соединений, участвующих в выполнении одной и той же функции, которая называется связкой соединений, причем каждое соединение представляет собой соединение многоточечного типа и сеть разделена на отдельные зоны, применяют ограничение, запрещающее переход между зонами, для каждого из соединений упомянутой связки (720₁, …, 720_N), для каждого возможного пути между терминалом источника и терминалом назначения упомянутого соединения, если коммутаторы, соединенные соответственно с терминалом источника и с терминалом назначения, принадлежат одной и той же зоне, и в противоположном случае накладывают ограничение, разрешающее однократный переход между зонами, принадлежащими соответственно упомянутым терминалам источника и назначения.

19. Способ маршрутизации по п.18, отличающийся тем, что для каждого виртуального соединения и для каждого из возможных путей между терминалом источника и терминалом назначения упомянутого соединения применяют (720₁, …, 770_N) дополнительные топологические ограничения сегрегации и/или совместного размещения этих путей относительно виртуальных соединений, для которых уже был проложен маршрут или будет проложен маршрут, одновременно с упомянутым соединением или коммутаторами упомянутой сети.

20. Способ маршрутизации по п.18, отличающийся тем, что на этапе выбора учитывают дополнительные топологические ограничения, в которых каждое дополнительное топологическое ограничение относится к группе путей, формирующих набор виртуальных соединений, для которых маршруты должны быть проложены одновременно, в котором упомянутая группа состоит из множества N_sg подгрупп упомянутых путей, и упомянутые дополнительные ограничения выражают, что самое большее количество n_sg подгрупп такое, что 0≤n_sg<N_sg, могут быть сделаны недействительными, причем подгруппу делают недействительной, если на все пути, принадлежащие ей, влияет отказ одного и того же коммутатора упомянутой сети.

21. Способ маршрутизации по пп.18, 19 или 20, отличающийся тем, что упомянутая функция стоимости представляет собой количество коммутаторов, через которые проложен путь, и ее минимизируют (730₁ …, 730_N) для каждого из соединений упомянутой связки, по каждому набору возможных путей между терминалом источника и терминалом назначения упомянутого соединения для обеспечения, по меньшей мере, одного пути-кандидата на соединение и на терминал назначения.

22. Способ маршрутизации по п.21, отличающийся тем, что формируют (740) комбинации K₁+K₂+…+K_n путей-кандидатов, где K_i, 1<i≤N, представляют собой номера соответствующих путей N соединений упомянутой связки, причем каждая комбинация соответствует возможному решению маршрутизации упомянутой связки, и четвертую функцию стоимости минимизируют (750) по набору упомянутых возможных решений, полученных таким образом.

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

24. Способ маршрутизации по одному из пп.2, 6, 12 или 18, отличающийся тем, что упомянутые зоны сети получают питание от независимых источников питания.

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