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

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

Иллюстрации

Показать все

Реферат

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

Изобретение относится к области маршрутизации в сети с коммутацией кадров и, более конкретно, к сети 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 и, для каждой пары терминалов источника