СПОСОБ МАРШРУТИЗАЦИИ ВИРТУАЛЬНЫХ СОЕДИНЕНИЙ В СЕТИ С КОММУТАЦИЕЙ КАДРОВ С ГАРАНТИРОВАННЫМ ДЕТЕРМИНИЗМОМ Российский патент 2011 года по МПК H04L12/56 

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

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

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

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

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

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

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

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

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

На фиг.1 схематично иллюстрируется сеть АПДК, содержащая терминалы T₁-T₆, и коммутаторы SW₁, SW₂ кадров. Можно видеть, что виртуальное соединение VL₃, соединяющее терминал T₃ с терминалом T₂, представляет собой соединение типа из точки в точку, тогда как виртуальное соединение VL₂, обслуживающее T₂ и T₃, и VL₁, обслуживающее T₃-T₅, представляют собой соединение многоточечного типа.

На фиг.2 схематично иллюстрируется коммутатор в сети АПДК. Он содержит множество входных буферов 210 типа FIFO (ПППО, "первым пришел - первым обслужен"), средство 220 фильтрации кадра, средство 230 мультиплексирования и выходные буферы 240 типа ПППО. Входящие кадры сохраняют в различных входных буферах, причем каждый буфер соединен с входным портом e_i. Средство 220 фильтрации удаляет кадры, соответствующие нераспознанному виртуальному соединению, кадры с ошибками и кадры, ведущие к нарушениям характеристик соединения. Средство 230 мультиплексирования направляет кадры в направлении к различным выходным буферам 240, в зависимости от идентификаторов виртуальных соединений, которые они содержат, и от таблицы коммутации. Выходные буферы передают кадры через физические соединения, причем каждый буфер соединен с выходным портом p_i.

Маршрутизация виртуальных соединений в сети АПДК состоит из определения таблиц коммутации различных коммутаторов сети. Маршрутизацию выбирают так, чтобы соблюдать ограничения полосы пропускания различных соединений. Для заданного решения маршрутизации проверяют, что сеть в действительности является детерминированной, то есть значение времени передачи по различным соединениям намного меньше, чем гарантированные границы задержки. С этой целью обычно используют алгоритм вычисления, обозначенный как "исчисление сети", описание которого можно найти в статьях автора Rene L. Cruz под названием "A calculus for network delay, Part I: network elements in isolation" and "Calculus for network delay, Part II: network analysis", published in IEEE Transactions on Information Theory, Vol.37, No.1, January 1991, страницы 114-141. Этот алгоритм оценивает с использованием невероятностного способа для каждого элемента сети максимальную мгновенную пропускную способность для данных на выходе соответствующего элемента. Трафик, передаваемый терминалом источника через виртуальное соединение L_i, моделируют с помощью функции максимальной скорости трафика, которая все еще называется функцией R_i(t) огибающей потока, зависящей от максимальной длины кадров и от минимального интервала времени, разделяющего два кадра соединения, то есть:

в котором S_max представляет собой максимальный размер кадра и BAG представляет собой величину, называемую зазором выделения полосы пропускания соединения, другими словами, BAG представляет собой минимальный интервал времени, разделяющий два кадра упомянутого соединения. Количество данных, генерируемых по соединению во время временного интервала [t₀, t₁], затем просто выражают как

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

Описание применения алгоритма "сетевого исчисления" для расчета времени задержки можно найти в тезисе автора J. Grieu под названием "Analyse et évaluation de techniques de commutation Ethernet pour 1'interconnexion des systémes avioniques" (Analysis and evaluation of Ethernet switching techniques for interconnecting avionic systems) 24 сентября 2004 г.

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

На фиг.3 иллюстрирует ситуацию сети АПДК, содержащей замкнутый контур с тремя коммутаторами: SW₁, SW₂, SW₃. Каждый коммутатор имеет три физических порта, каждый порт состоит из входного порта и выходного порта. Выходной порт, p₁ коммутатора SW₁ соединен со входным портом e₃ коммутатора SW₃. Выходной порт p₃ коммутатора SW₃ соединен со входным портом e₂ коммутатора SW₂. выходной порт p₂ коммутатора SW₂ соединен со входным портом e₁ коммутатора SW₁. Путь C, проходящий через порты p₁, e₃, p₃, e₂, p₂, e₁, формирует ориентированный замкнутый контур в сети. Огибающая потока по выходному порту p₁ зависит от огибающей потока в e₁, то есть от p₂ соединения VL₁ (на входе SW₁). Аналогично огибающая потока в p₂, в свою очередь, зависит от огибающей потока в p₃ и от огибающей потока соединения VL₃. Наконец, огибающая потока в p₃, в свою очередь, зависит от огибающей потока в p₁ и от соединения VL₂. Можно видеть, что существует взаимосвязь круговой зависимости, которая делает оценку огибающей потока и поэтому времени задержки невозможной.

На фиг.4 иллюстрируется ситуация в сети АПДК, содержащей замкнутый контур, с четырьмя коммутаторами: SW₁, SW₂, SW₃, SW₄. Каждый из коммутаторов имеет четыре физических порта, каждый порт состоит из входного порта и выходного порта. Следует отметить, что четыре виртуальных соединения VL₁-VL₄ были маршрутизированы в сети.

Огибающая потока выходного порта 23 SW₁ зависит от огибающей потока выходного порта 5 SW₃ и от соединения VL1. Огибающая потока выходного порта 5 SW₃ зависит от огибающей потока выходного порта 23 в SW₄ и от огибающей потока соединения VL₃. Огибающая потока выходного порта 23 из SW₄ зависит от огибающей потока выходного порта 24 SW₂ и от огибающей потока соединения VL₄. Наконец, огибающая потока выходного порта 24 SW₂ зависит от огибающей потока выходного порта 23 SW₁ и от огибающей потока VL₂.

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

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

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

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

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

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

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

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

(d) проверяют детерминизм сети на основе маршрутизированных таким образом виртуальных соединений.

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

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

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

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

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

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

В предпочтительном варианте воплощения сеть с коммутацией кадров представляет собой сеть АПДК.

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

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

На фиг.1 схематично иллюстрируется примерная сеть АПДК;

на фиг.2 схематично иллюстрируется конструкция коммутатора в сети АПДК;

на фиг.3 иллюстрируется ситуация сети АПДК, содержащая замкнутый контур с тремя коммутаторами;

на фиг.4 иллюстрируется ситуация сети АПДК, содержащая замкнутый контур с четырьмя коммутаторами;

на фиг.5 А и 5 В иллюстрируется принцип работы изобретения;

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

на фиг.7 иллюстрируется упрощенный пример сети АПДК для применения способа маршрутизации в соответствии с изобретением.

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

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

В дальнейшем любая упорядоченная последовательность l узлов или коммутаторов сети l=SW₁, SW₂, ..., SW_N при N≥3 так, что SW_i+1 G (SW_i), для i=1, ..., N-l и SW₁ G (SWm) будет описана как ориентированный замкнутый контур, в котором G представляет собой приложение, которое устанавливает соответствие каждого коммутатора, SW с набором его преемников, то есть набором коммутаторов, непосредственно соединенных с выходным портом SW. В дуплексной сети, где каждый физический порт содержит входной порт и выходной порт, следует понимать, что если в сети существует ориентированный замкнутый контур SW₁,SW₂, ...,SW_N, тогда SW_N, SW_N-1, ...,SW₁ также представляет собой ориентированный замкнутый контур, но в противоположном направлении.

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

После идентификации ориентированные замкнутые контуры сортируют по количеству пересекаемых коммутаторов. Рассмотрим такой ориентированный замкнутый контур, представленный на фиг.5A. Здесь он соответствует физическому замкнутому контуру из шести коммутаторов SW₁-SW₆. Виртуальный замкнутый контур VL, который проникает в замкнутый контур коммутатора SW_i и появляется возле следующего коммутатора SW_i+1, не способен индуцировать взаимосвязь круговой зависимости в замкнутом контуре, независимо от количества уже маршрутизированных виртуальных соединений по замкнутому контуру и количества коммутаторов, которые последний совместно использует с ним. Действительно, поскольку соответствующее соединение VL не пересекает два выходных порта последовательных коммутаторов, оно не индуцирует какую-либо взаимосвязь между огибающими потоками на выходе этих коммутаторов.

Таким образом, понимают, что круговая зависимость может быть индуцирована только, когда виртуальное соединение совместно использует, по меньшей мере, три последовательных коммутатора, то есть, по меньшей мере, два общих выходных порта с ориентированным замкнутым контуром. Если рассматривать виртуальные соединения, совместно использующие точно три коммутатора с ориентированным контуром по фиг.5A, следует отметить, что, по меньшей мере, шесть из этих соединений VL₁, ...,VL₆ требуется для получения закрывающей части замкнутого контура и, вследствие этого, круговой зависимости. В общем случае, для ориентированного замкнутого контура из N коммутаторов, зависимость может быть получена, по меньшей мере, с N соединениями, имеющими точно три коммутатора, общих с замкнутым контуром, и тем более для N соединений, имеющих более чем три коммутатора, общие с контуром. Для соединений, точно совместно использующих М>2 коммутаторов в ориентированном замкнутом контуре, по меньшей мере, таких соединений потребуется для получения взаимосвязи круговой взаимозависимости, где E(.) выражает целочисленное значение.

Предположим теперь, что для данного ориентированного замкнутого контура путь маршрутизации, соответствующий трем последовательным вершинам замкнутого контура, подавляется. Такая ситуация была проиллюстрирована на фиг.5B, где путь SW₁, SW₂, SW₃, представленный пунктирными линиями, запрещен для маршрутизации. В результате такого ограничения больше невозможно получить закрывающий элемент замкнутого контура с виртуальными соединениями, создающими круговую зависимость. Действительно, виртуальное соединение VL₁ больше не разрешено, и любое виртуальное соединение, соответствующее предписанному ограничению, содержит самое большее путь SW₁, SW₂ или путь SW₂, SW₃. Ни одно из виртуальных соединений и, в частности, ни VL₆, ни VL₂, не обеспечивают возможности индуцирования взаимозависимости между огибающими потока коммутаторов SW₁ и SW₃.

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

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

На фиг.6 иллюстрируется блок-схема последовательности операций способа маршрутизации в соответствии с изобретением. По описанию топологии сети 610 проводят инвентаризацию всех ориентированных замкнутых контуров сети в пределах круговых перестановок, на этапе 620. На этапе 630 их сортируют по количеству пересекаемых коммутаторов. Для каждого полученного таким образом ориентированного замкнутого контура, на этапе 640, затем идентифицируют все тройки последовательных коммутаторов контура. На этапе 650 выполняют поиск общих троек для нескольких замкнутых контуров. На этапе 660 выбирают одну тройку на замкнутый контур. Предпочтительно, используя порядок предпочтений, выбирают тройки, которые совместно используются как можно большим количеством замкнутых контуров. Выбранные тройки определяют запрещенные пути маршрутизации; в результате запрета маршрутизации через путь можно разорвать взаимосвязь круговой зависимости для замкнутого контура или контуров, которым он принадлежит.

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

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

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

На фиг.7 иллюстрируется упрощенный пример сети АПДК для иллюстрации способа маршрутизации в соответствии с изобретением.

Сеть содержит пять терминалов T₁-T₅(каждый из которых может быть источником или назначением, и четыре коммутатора SW₁-SW₄. Ориентированные замкнутые контуры сети идентифицированы в пределах круговой перестановки:

- для замкнутых контуров из 3 коммутаторов:

- для замкнутых контуров из 4 коммутаторов:

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

замкнутый контур

замкнутый контур

замкнутый контур

замкнутый контур

замкнутый контур

замкнутый контур

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

{SW₁, SW₂, SW₄}, общий для ℓ^cw ₁ и ℓ^cw ₃;

{SW₄, SW₂, SW₁}, общий для ℓ^ccw ₁ и ℓ^cw ₃;

{SW₁, SW₄, SW₃} для ℓ^cw ₂ и {SW₃, SW₄, SW₁} для ℓ^cw ₂;

будут выбраны в качестве примера.

Таким образом, будут запрещены только 4 пути вместо теоретически требуемых 6.

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

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

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

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

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

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

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

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

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

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

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

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

7. Способ маршрутизации по п.1, отличающийся тем, что сеть коммутации кадров представляет собой авиационную полнодуплексную коммутируемую сеть Ethernet (АПДК).