Способ неблокируемой маршрутизации

Способ неблокируемой маршрутизации

Иллюстрации

Показать все

Реферат

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

Известен способ построения системы оптической связи (см., например, Фриман Р. Волоконно-оптические системы связи. М.: Техносфера, 2006, с.407-411, 425-428), заключающийся в установке на узлах связи аппаратуры оптической коммутации, мультиплексирования, усиления и соединения их волоконно-оптическими линиями связи.

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

Наиболее близким по своей технической сущности к заявляемому способу неблокируемой маршрутизации для построения системы оптической связи является способ построения по патенту CN №1284804 от 21.02.2001, МПК 7 Н04В 10/02 (приоритетная заявка GB 1999016577 от 1999.07.15).

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

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

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

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

1) узел-получатель должен быть достижим всеми остальными узлами, то есть ;

2) каждый узел, кроме узла-получателя, должен иметь степень выхода не менее чем 2, то есть ;

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

;

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

;

5) если два узла ν_i и ν_k взаимно достижимы в G, то они являются соседями, а связь между ними - это резервная дуга, то есть

и

Заявленный способ расширяет арсенал средств данного назначения.

Поставленная цель достигается тем, что в известном способе построения системы оптической связи, содержащей N≥2 узлов связи, объединенных М≥1 ребрами оптических трактов, заключающемся в том, что на передающем конце узла связи устанавливают множество источников света и терминалы спектрального уплотнения, а на его приемном конце - множество фотодетекторов и терминалы спектрального уплотнения, согласно изобретению в системе оптической связи предварительно выделяют узел-получатель ν_j, для которого составляют граф неблокируемой маршрутизации Процесс построения графа неблокируемой маршрутизации включает в себя четыре этапа. На первом этапе классифицируют все ребра на прямые, кольцевые и обратные при помощи алгоритма поиска в ширину и добавляют все прямые ребра в Таким образом, после первого этапа граф маршрутизации содержит только прямые дуги к узлу-получателю ν_j. На втором этапе находят все узлы ν_i с исходящей степенью , имеющих максимальную разницу между исходящей и входящей степенями узла в графе маршрутизации и удаляют прямые ребра (ν_i;ν_k), для которых узел ν_k выбирают в соответствии со следующими условиями (в порядке значимости): ν_k≠ν_j, минимальная исходящая степень узла , максимальное число ребер от узла ν_k до узла ν_j в графе максимальная входящая степень узла Таким образом, после второго этапа каждый узел, кроме ν_j, имеет одно или два исходящих ребра. На третьем этапе добавляют все узлы ν_i с исходящей степенью в список L_O1. Выбирают из списка L_O1 ” самые ненадежные ” узлы ν_i с и для каждого из таких узлов находят ребра (ν_i;ν_k) к узлам ν_k, таким, что не существует пути в от ν_k до ν_i, разница между исходящей и входящей степенями узла ν_k максимальна, , число ребер от узла ν_k до узла ν_j минимально , исходящая степень узла (если возможно). При этом если невозможно обеспечить связь от узла обычным ребром, то используют резервное. Резервным ребром является двунаправленное ребро ν_iν_k, для которого (ν_i,ν_k) и (ν_k,ν_i) принадлежат множеству ребер графа маршрутизации Добавляют все найденные ребра в граф маршрутизации и список L_O2. Таким образом, в ходе третьего этапа к узлам, имеющим степень выхода , добавляют по одному дополнительному ребру (если это возможно), обеспечивая тем самым для каждого из них исходящую степень На четвертом этапе выбирают узлы ν_i с , для которых возможно обеспечить , добавив третье исходящее ребро (ν_i,ν_k), и добавляют третье ребро из списка L_O2. Из трех исходящих ребер удаляют ребро (ν_i;v_l), являющееся частью резервного ребра. Если нет такого ребра, то удаляют ребро (ν_i;ν_m) к самому "ненадежному" узлу ν_m с в графе маршрутизации Если нет таких ребер, то удаляют ребро (ν_i,ν_n) к узлу ν_n с . Исключают удаленные ребра из списка L_O2 до тех пор, пока список не окажется пуст. Таким образом, в ходе четвертого этапа перебирают все ребра в графе так, чтобы исходящие степени узлов оставались неизменными, а число резервных ребер и длина пути при этом уменьшались. При этом на передающем конце узла связи ν_i устанавливают источники света и терминалы спектрального уплотнения в количестве, равном исходящей степени узла , а на его приемном конце - фотодетекторы и терминалы спектрального уплотнения в количестве, равном входящей степени в графе маршрутизации

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

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

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

Заявленный способ поясняется чертежами, на которых показано:

фиг.1 - исходная топология системы оптической связи;

фиг.2 - состав и соединение оборудования на узлах связи;

фиг.3 - структура системы оптической связи после реализации первого этапа;

фиг.4 - структура системы оптической связи после реализации второго этапа;

фиг.5 - структура системы оптической связи после реализации третьего этапа;

фиг.6 - структура системы оптической связи после реализации четвертого этапа.

Реализация заявленного способа объясняется следующим образом.

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

Реализация заявляемого способа рассмотрена на примере системы оптической связи, показанной на фиг.1. Система оптической связи состоит из узлов связи 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, соединенных соответствующими им двунаправленными ребрами 1-2, 1-3, 1-4, 2-4, 2-5, 2-8, 3-6, 3-7, 4-6, 4-7, 5-7, 5-8, 6-7, 6-9, 7-8, 7-9, 7-10, 8-10, 9-10. В общем случае на каждом узле системы оптической связи (например, на 1-м и 2-м узле) установлены (фиг.2):

- мультиплексоры ввода-вывода 1.1', 1.1” и 2.1', 2.1”;

- источники света 1.2', 1.2” и 2.2', 2.2”;

- фотодетекторы 1.3', 1.3” и 2.3', 2.3”;

- терминалы спектрального уплотнения 1.4 и 2.4.

Выходы мультиплексоров ввода-вывода 1.1', 1.1”, 2.1', 2.1” соединены с входами соответствующих источников света 1.2', 1.2”, 2.2', 2.2” и выходами фотодетекторов 1.3', 1.3”, 2.3', 2.3”. Выходы источников света 1.2', 1.2”, 2.2', 2.2” и входы фотодетекторов 1.3', 1.3”, 2.3', 2.3” соединены с входами соответствующих терминалов спектрального уплотнения 1.4, 2.4, выходы которых соединены с волокном оптического кабеля 11.

Порядок реализации заявленного способа рассмотрен на примере системы оптической связи с числом узлов N=10 и ребер М=38, показанной на фиг.1. В системе оптической связи предварительно выделяем узел-получатель ν₂, для которого составляем граф неблокируемой маршрутизации . На первом этапе классифицируем все ребра на прямые, кольцевые и обратные при помощи алгоритма поиска в ширину и добавляем все прямые ребра в . Таким образом, после первого этапа граф маршрутизации содержит только прямые дуги к узлу-получателю ν₂ (фиг.3). На втором этапе находим узлы с исходящей степенью больше двух, имеющих максимальную разницу между исходящей и входящей степенями узла. Таким узлом в графе маршрутизации является ν₇. Удаляем ребро (ν₇;ν₈), так как при прочих равных условиях узел ν₈ имеет максимальное число ребер до узла-получателя ν₂ . Таким образом, после второго этапа каждый узел кроме ν₂ имеет одно или два исходящих ребра (фиг.4). На третьем этапе добавляем все узлы с исходящей степенью, равной единице в список L_O1. Такими узлами в системе оптической связи являются: ν₁, ν₃, ν₄, ν₅, ν₆, ν₈, ν₁₀. Выбираем из списка L_O1 ”самый ненадежный” узел ν₈ с минимальной разницей между исходящей и входящей степенями узла и добавляем к нему в соответствии с требованиями еще одно исходящее ребро (ν₈;ν₅). Аналогичным образом добавляем по одному исходящему ребру ко всем остальным узлам из списка L_O1: к узлу ν₁ добавляем ребро (ν₁,ν₄), к узлу ν₄ добавляем ребро (ν₄;ν₁), к узлу ν₅ добавляем ребро (ν₅;ν₇), к узлу ν₃ добавляем ребро (ν₃;ν₆), к узлу ν₆ добавляем ребро (ν₆;ν₉), к узлу ν₁₀ добавляем ребро (ν₁₀;ν₉). Добавляем все вышеуказанные ребра в список L_O2. Таким образом, после третьего этапа все узлы графа маршрутизации имеют исходящую степень, равную двум. При этом узлы ν₁ и ν₄, а также ν₅ и ν₇ соединены между собой с помощью резервных ребер ν₁ν₄ и ν₅ν₇ соответственно. С целью уменьшения числа резервных ребер на четвертом этапе выбираем в графе маршрутизации узлы с минимальным числом ребер до узла-получателя, для которых возможно обеспечить исходящую степень, равную трем, добавив третье исходящее ребро из списка L_O2. Таким узлом является ν₇, к которому добавляем третье исходящее ребро (ν₇;ν₃). Из трех исходящих ребер удаляем ребро (ν₇;ν₅), являющееся частью резервного ребра. Таким образом, после четвертого этапа исходящие степени узлов остаются неизменными, равные двум, а число резервных ребер сокращается на одно.

В случае использования способа-прототипа с 10 узлами необходимо на узлах связи разместить 46 терминалов спектрального уплотнения, по 184 источника света и фотодетектора. В заявленном решении для обеспечения неблокируемой маршрутизации достаточно использовать 33 терминала спектрального уплотнения, 72 источника света и 76 фотодетекторов.

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

Способ неблокируемой маршрутизации для построения системы оптической связи, содержащей N≥2 узлов связи, объединенных М≥1 ребрами оптических трактов, заключающийся в том, что на передающем конце узла связи устанавливают множество источников света и терминалы спектрального уплотнения, а на его приемном конце - множество фотодетекторов и терминалы спектрального уплотнения, отличающийся тем, что предварительно в системе оптической связи выделяют узел-получатель, для которого составляют граф неблокируемой маршрутизации, классифицируют все ребра на прямые, кольцевые и обратные при помощи алгоритма поиска в ширину и добавляют все прямые ребра в граф маршрутизации, затем находят все узлы с исходящей степенью больше двух, имеющих максимальную разницу между исходящей и входящей степенями узла в графе маршрутизации, и удаляют прямые ребра от данных узлов к узлам, имеющим минимальную исходящую степень, максимальное число ребер до узла-получателя в графе маршрутизации и максимальную входящую степень, добавляют все узлы с исходящей степенью, равной единице в список L_O1, выбирают из списка L_O1 узлы с минимальной разницей между исходящей и входящей степенями узла, затем для каждого из таких узлов находят не являющиеся резервными ребра к узлам, для которых не существует пути в графе маршрутизации до исходного узла, имеющих максимальную разницу между исходящей и входящей степенями, минимальное число ребер до узла-получателя и исходящую степень больше единицы, добавляют все найденные ребра в граф маршрутизации и список L_O1, выбирают узлы с минимальным числом ребер до узла-получателя, для которых возможно обеспечить исходящую степень, равную трем, добавив третье исходящее ребро из списка L_O2, и добавляют к данным узлам третье исходящее ребро, из трех исходящих ребер удаляют ребро, являющееся частью резервного ребра или, если нет таких ребер, то удаляют ребро к узлу с минимальной разницей между исходящей и входящей степенями узла или, если нет таких ребер, то удаляют ребро к узлу с максимальным числом ребер до узла-получателя в графе маршрутизации, исключают удаленные ребра из списка L_O2 до тех пор, пока список не окажется пуст, таким образом, перебирают все ребра в графе маршрутизации так, чтобы исходящие степени узлов оставались неизменными, а число резервных ребер и длина пути при этом уменьшались, при этом на передающем конце узлов связи устанавливают источники света и терминалы спектрального уплотнения в количестве, равном исходящей степени, а на их приемном конце - фотодетекторы и терминалы спектрального уплотнения в количестве, равном входящей степени узлов в графе маршрутизации.