СПОСОБ РАСПРЕДЕЛЕНИЯ ПАКЕТОВ В ЦИФРОВОЙ СЕТИ СВЯЗИ С НЕОДНОРОДНОЙ ТОРОИДАЛЬНОЙ ТОПОЛОГИЧЕСКОЙ СТРУКТУРОЙ
METHOD OF DISTRIBUTING PACKETS IN DIGITAL COMMUNICATION NETWORK WITH HETEROGENEOUS TOROIDAL TOPOLOGICAL STRUCTURE

Изобретение относится к области связи и может быть использовано для построения цифровых сетей связи (ЦСС) с коммутацией пакетов, в системах коммутации для построения коммутационных полей АТС, сетей ЭВМ, микропроцессорных систем, суперкомпьютеров и т.п.
Известны способы распределения пакетов, реализованные в протоколах маршрутизации RIP и OSPF и использующие алгоритмы Беллмана-Форда и Дейкстры, соответственно [Олифер В., Олифер Н. Компьютерные сети. Принципы, технологии, протоколы: Учебник для вузов. 5-е изд. - СПб.: Питер, 2016. - 992 с]. Данные способы предполагают определение маршрутов передачи исходя из результатов определения кратчайших путей, учитывающих количество транзитных участков (RIP) и состояние связей, из которых в первую очередь используется информация о пропускных способностях каналов связи. Недостатками данных протоколов является необходимость регулярного обмена маршрутной информацией между узлами, отсутствии учета при определении маршрутов требований по задержке передаче пакетов, что приводит к нерациональному использованию пропускных способностей каналов связи ЦСС.
Данный недостаток отсутствует в способах распределения пакетов в сетях с однородными топологическими структурами, в которых обмен служебной информацией отсутствует полностью.
Наиболее близким по технической сущности к заявляемому способу является способ распределения пакетов в сетях с тороидальной топологической структурой ([Baransel, С. Routing in Multihop Packet Swithing networks: Gb/s Challenge / C. Baransel, W. Dobosiewicz, P. Grurzynski // IEEE Network. -1995. - May/June. - P. 38-61], основанный на одном из методов маршрутизации в регулярных топологиях - ортогональном или диагональном. При использовании ортогональной маршрутизации для обрабатываемого пакета определяется расстояние между текущим узлом и узлом-адресатом по одному (основному) измерению; сравнивается полученное значение с нулем, если оно не равно нулю, то осуществляется передача пакета через выходной порт данного измерения; в противном случае вычисляется расстояние между текущим узлом и узлом-адресатом по второму измерению; в случае, если полученное расстояние не равно нулю, то осуществляется передача пакета через порт второго измерения. При использовании диагональной маршрутизации обрабатываемый пакет сначала передается через узлы в одном направлении, пока не совпадут расстояния между текущим узлом и узлом-адресатом по первому и второму измерениям; затем пакет поочередно направляется через порты первого и второго измерений, с сохранением равенства расстояний между текущим узлом и узлом-адресатом по первому и второму измерениям, пока не будет принят узлом-адресатом. Существенным недостатком таких способов являются большие значения задержек при передаче разнородного трафика.
Техническим результатом изобретения является уменьшение времени задержки передачи пакетов в ЦСС с неоднородной тороидальной топологической структурой и повышение эффективности использования пропускных способностей каналов связи однородных ЦСС при обслуживании неоднородного трафика.
Указанный результат достигается тем, в известном способе распределения пакетов в узлах коммутации цифровой сети связи с неоднородной тороидальной топологической структурой, заключающемся в приеме текущим узлом коммутации из канала связи пакета, извлечении из заголовка пакета служебной информации, вычислении расстояния от текущего узла до узла-адресата и передачи пакета текущим узлом в канале связи подсети L, согласно изобретению проверяют в извлеченной служебной информации наличие требования обеспечения передачи пакета с минимальной задержкой, при наличии такого требования обрабатываемый пакет передают в подсети L, для которой расстояние между соседними узлами будет наибольшим из всех подсетей и не превышать вычисленное расстояние между текущим узлом и узлом-адресатом по каждому измерению.
Сущность изобретения заключается в том, что проверяют в извлеченной служебной информации наличие требования обеспечения передачи пакета с минимальной задержкой, при наличии такого требования обрабатываемый пакет передают в подсети L, для которой расстояние между соседними узлами будет наибольшим из всех подсетей и не превышать вычисленное расстояние между текущим узлом и узлом-адресатом по каждому измерению.
1
1
2
2
3
3
1
2
1
2
1
2
Способ может быть реализован в узлах коммутации с неоднородной тороидальной топологической структурой ЦСС. На фиг. 1 изображена трехуровневая неоднородная тороидальная структура ЦСС, состоящая из трех взаимосвязанных (вложенных) тороидальных однородных структур, образованных узлами коммутации (УК) различного типа. Тип УК зависит от состава используемой аппаратуры связи и пропускной способности образуемых ею каналов связи (КС). В свою очередь, тип УК определяется положением в структуре и степенью вершины (количеством линий связи инцидентных УК). На фиг. 2а представлена топологическая структура первой подсети, в которую входят все УК, связанные низкоскоростными КС, и она характеризуется расстоянием между соседними узлами Δ=Δ=1. На фиг. 2б представлена топологическая структура второй подсети, которая имеет ширину структуры, равную шести, образована УК, связанными КС большей пропускной способности, чем в первой подсети, и характеризуется расстоянием между соседними узлами Δ=Δ=2. На фиг. 2в представлена топологическая структура третьей подсети, которая имеет ширину структуры, равную трем, образована девятью УК, связанными КС с максимально возможными пропускными способностями, и характеризуется расстоянием между соседними узлами Δ=Δ=4.
Способ может быть реализован по следующему алгоритму.
Шаг 1. Принимают пакет для обработки и передачи.
Шаг 2. Из заголовка пакета извлекают служебную информацию.
Шаг 3. В случае если обеспечивать минимальную задержку не следует, то для передачи назначается подсеть L=1 и переходят к шагу 5.
Шаг 4. В случае, если необходимо обеспечить минимальную задержку, то определяют подсеть для передачи в следующей последовательности:
d
1
d
2
d
Шаг 4.1. Из заголовка пакета определяют адрес узла-адресата x по каждому измерению δ(x), δ(x).
c
d
Шаг 4.2. Рассчитывают расстояние между текущим узлом x и узлом-адресатом x:
1
d
2
d
d
1
c
2
c
с
1
2
d
c
где операция вычитания осуществляется по модулю К; К - значение ширины структуры топологии подсети L=1; δ(x), δ(x) - адрес узла назначения x по первому и второму измерениям; δ(x), δ(x) - адрес текущего узла x по первому и второму измерениям, d, d - расстояние между адресом узла-назначения x и адресом текущего узла x по первому и второму измерениям.
1
2
c
d
Шаг 4.3. Определяют подсеть L, для которой расстояния между соседними узлами  и  будут наибольшими из всех подсетей, но не превышать вычисленное расстояние d и d между текущим узлом x и узлом-адресатом x по каждому измерению:
где N - множество подсетей, входящих в состав неоднородной тороидальной ЦСС. Данная операция может быть реализована путем сравнения расстояний между соседними узлами каждой подсети с вычисленным расстоянием по каждому измерению.
Шаг 5. Определение измерения для передачи в подсети L.
Шаг 6. Передача пакета в выбранной подсети L и по выбранному измерению.
Способ может быть реализован, например, с помощью устройства, схема которого приведена на фиг. 3, где обозначены 1 - устройства приема, 2 - устройства передачи, 3 - блок извлечения служебной информации, 4 - коммутационное устройство (коммутационная матрица), 5 - блок анализа служебной информации, 6 - блок расчета расстояния до узла-адресата, 7 - блок определения подсети L, 8 - блок определения измерения передачи, 9 - блок управления.
Блок определения подсети 7 предназначен для определения подсети L, с использованием информации о расстоянии между текущим узлом и узлом-адресатом, ширины топологической структуры и наличием требования о необходимости обеспечения минимальной задержки для обслуживаемого пакета. Блок определения измерения передачи 8 предназначен для определения номера измерения, по которому будет передаваться пакет на основе используемого способа отклоняющей маршрутизации - диагональной или ортогональной. Блок управления 9 предназначен для формирования управляющих сигналов коммутации для коммутационного устройства, на основе номера подсети и номера измерения для передачи.
Устройство может быть реализовано на элементах, широко распространенных в области электронной и электротехники или в программной форме, на основе используемых в сетевых элементах процессорах.
1
d
2
d
1
d
2
d
1
2
Устройство реализации работает следующим образом. Устройство приема 1 из канала связи принимает пакет и передает его в блок извлечения служебной информации 3. В блоке извлечения служебной информации 3 из принятого пакета выделяют служебную часть и отправляют ее в блок анализа служебной информации 5. В блоке анализа служебной информации 5 выделяют информацию об адресе узла получателя δ(x), δ(x) и информацию о необходимости обеспечения минимальной задержки передачи пакета. Данная информация является типовой для широкого круга сетевых протоколов [Олифер В., Олифер Н. Компьютерные сети. Принципы, технологии, протоколы: Учебник для вузов. 5-е изд. - СПб.: Питер, 2016. - 992 с]. Адрес узла-адресата δ(x), δ(x) передают на вход блока расчета расстояния до узла-адресата 6, а информацию о необходимости обеспечения минимальной задержки - на первый вход блока определения подсети 7. В блоке расчета расстояния до узла-адресата 6 рассчитывают расстояние от текущего узла до узла-адресата по обоим направлениям d, d с помощью выражения (1) и передают ее на второй вход блока определения подсети 7, а также на вход блока определения номера измерения передачи 8. В блоке определения подсети 7 определяют значение подсети L, для которой расстояние между соседними узлами будет наибольшим из всех подсетей и не превышать вычисленное расстояние между текущим узлом и узлом-адресатом по каждому измерению. Процедура определения основана на последовательном сравнении расстояний между соседними узлами каждой подсети с вычисленным расстоянием по каждому измерению. Далее полученное значение L передают на первый вход блока 9. В блоке определения измерения для передачи 8 при использовании диагональной маршрутизации номер измерения для передачи  k определяют, исходя из следующих выражений:
При ортогональной маршрутизации номер измерения для передачи k определяют исходя из:
Полученные значения номера измерения k передают на второй вход блока управления 9. В блоке управления 9 на основе полученных значений номера подсети L и номера измерения k формируют управляющие сигналы для коммутации выхода i-го блока извлечения служебной информации 3 и входа j-го устройства передачи, соответствующего рассчитанным значениям L и k.
Проведенные исследования информационного обмена в ЦСС с использованием имитационных моделей, в которых реализован предлагаемый способ, показали повышение пропускной способности ЦСС при передаче неоднородного трафика на 10-15% относительно алгоритмов самомаршрутизации в тороидальных ЦСС [Головченко Е.В. Алгоритм маршрутизации в цифровых сетях связи с тороидальной топологией. Телекоммуникации, №10, 2012 г., стр. 12-18].