SDN: новые возможности управления потоками в mesh — сетях

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

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

Сказанное, в полной мере, относится и к mesh-сетям, где преобладают два подхода к маршрутизации – проактивный(например протокол OLSR) и реактивный (протокол AODV). Существуют и весьма производительные гибридные схемы.

OLSR (Optimized Link-State Routing) [1] основан на сборе и распространении служебной информации о состоянии сети. В результате обработки этой информации каждый узел может построить модель текущего состояния сети в виде формального описания графа, вершины которого ставятся в соответствие узлам сети, рёбра (или дуги) – линиям связи (линкам). Имея такой граф, любой узел может вычислить «длины» кратчайших путей до всех адресатов в сети и выбрать «оптимальный» маршрут, ведущий к любому конкретному узлу сети.

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

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

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

Наряду с протоколом OLSR, который обеспечивает предварительный (проактивный) расчёт маршрутов между всеми парами абонентов в пределах подсети, в mesh-сетях реализуется другой – реактивный протокол AODV ( Ad hoc On-Demand Distance Vector) [2]. Данный протокол предусматривает поиск и организацию маршрутов по мере их необходимости, и разрушение найденных маршрутов после их использования.

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

Тем не менее, оба протокола (в совокупности), в какой-то степени, соответствуют основным требованиям, которым должен удовлетворять «идеальный алгоритм» [3]. Эти требования можно сформулировать и прокомментировать следующим образом:

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

• Вычислительная простота. Реализация алгоритма AODV требует минимальных процессорных ресурсов. И, наоборот, алгоритм OLSR достаточно сложен.
• Устойчивость. Оба алгоритма стремятся к конкретному решению без резких осцилляций при незначительных изменениях состояний радиолучей.
• Справедливость. На первый взгляд, оба алгоритма предоставляют равноценные услуги всем пользователям сети. Но, вследствие своего топологического расположения в сети, отдельные пользователи могут захватить относительно большую долю ресурсов, чем им необходимо.
• Адаптивность к изменениям трафика и топологии. Оба алгоритма способны определить новое множество маршрутов при изменении топологии сети. Но и тот, и другой алгоритм статичен по отношению к внешнему трафику и распределению нагрузки.

Последний недостаток характерен для всех известных децентрализованных стратегий, за исключением стратегий кратчайшей очереди и смещения [3], при которых вес маршрута определяется как линейная функция от двух параметров: числа транзитных участков на пути к адресату и длинах очередей на направлениях выдачи, лежащих на маршруте (классический пример – Internet [3]). В протоколах mesh-сетей подобных стратегий нет, и, по-видимому, не будет, так как такая стратегия потребует сложных и трудоёмких вычислений на всех узлах и, вряд ли будет обладать свойством устойчивости – незначительные колебания нагрузки могут спровоцировать перерасчёт маршрутов.

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

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

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

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

Такой подход может быть реализован и в mesh-сетях, но он требует использования специализированных маршрутно-адресных таблиц, задающих соответствие направлений передачи пакетов не только адресам получателей, но и более специализированным признакам, например выделенным парам — «источник-получатель». В стандартных сетевых протоколах таких возможностей нет, но эта задача достаточно тривиально решается применением протокола OpenFlow.

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

• в стандартный стек протоколов встраиваются механизмы, позволяющие разделить обслуживаемый поток на части, причем одна из них может обслуживаться стандартными протоколами TCP/IP, остальные – с помощью оригинальных процедур;
• для сортировки могут использоваться служебные поля принимаемых пакетов, такие как IP-адреса отправителя и получателя, соответствующие им MAC-адреса, номера портов и т.д.
• для определения маршрутов «нестандартных» потоков могут использоваться таблицы потоков, задающие соответствие направлений передачи пакетов не только адресам получателей, но и на основании более сложной динамической логики — «источник-получатель», права доступа, загрузка серверов, приоритеты по обслуживанию и т. д.

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

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

Мы обновили сайт. Добро пожаловать!

Добро пожаловать на новую версию сайта www.smartnlg.ru

Анализ существующих протоколов TDMA

Анализ существующих протоколов TDMA
Часть 5

Описание графа G** = (U, Г**) может быть оформлено в виде матрицы U = ║U_ij║ размером N×N, где N – число дуг в исходном графе G = (E, Г). Столбцы и строки такой матрицы должны соответствовать дугам исходного графа, а элементы U_ij содержать следующую информацию:

Пример такой матрицы, составленной для приведённого на рисунке 2.2 исходного графа, представлен на рисунке 21:

Рисунок 21

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

Данной матрице соответствует граф G** = (U, Г**), показанный на рисунке 22:

 

Рисунок 22

Сравнивая приведённые на рисунках 14 и 22 графы, отметим, что описание графа G** = (U, Г**) более громоздко, чем описание графа G* = (E, Г*). Это объясняется тем, что в исходном графе G = (E, Г) число дуг превышает число вершин.

И, если функциональная избыточность сети достаточно высока – число вершин в графе G**=(U, Г**) будет очень велико, и число «красок» будет мало отличаться от числа дуг в исходном графе.  В предельном же случае, когда граф  G = (E, Г) будет представлять собой «клику», то есть отвечать условию (7):    

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

Число таких слотов будет определяться выражением (8):

где n – число вершин в графе G = (E, Г).

Если же отказаться от идеи распределения слотов по радиолучам, и распределять слоты по узлам, то число слотов будет равняться величине n. Так, если «клика» включает в себя 16 узлов, то при распределении слотов по радиолучам, необходимо предусмотреть организацию 240 слотов, а при распределении по узлам – всего 16.

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

Рисунок 23

По-видимому, этот вопрос требует более детального рассмотрения. И очевидно, что он тесно связан с алгоритмами решения задачи раскраски графов.

Анализ существующих протоколов TDMA

Анализ существующих протоколов TDMA
Часть 4

Следует отметить, что, в общем случае, граф коллизий G* = (E, Г*) может обладать семейством внутренне устойчивых подмножеств и не иметь таких подмножеств вообще – всё зависит от конфигурации исходного графа G = (E, Г).

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

Сказанное относится и к задаче «бесконфликтной» раскраске радиолучей. Только в данном случае должен быть построен граф коллизий иного вида – граф      G** = (U, Г**), причём множество вершин этого графа должно соответствовать дугам исходного графа - G = (E, Г), а отображения Г** – указывать на «конфликтные» радиолучи.

«Конфликтность» радиолучей может быть определена следующими правилами:

1)      каждый узел не должен осуществлять передачу информации одновременно по двум и более радиолучам;

2)      любой узел не может одновременно принимать информацию от двух и более узлов;

3)      ни один из узлов не способен к одновременной передаче и приёму пакетов.

Более точно, эти правила будут выглядеть следующим образом:

1)      «вершина» графа G** = (U, Г**), поставленная в соответствие дуге (X_i, X_j) должна считаться «конфликтной» для любой другой дуги G=(E, Г), если эти дуги исходят из одной и той же вершины X_i. Например, фрагменту исходного графа G = (E, Г), который изображён на рисунке 15

Рисунок 15

будет соответствовать фрагмент графа G** = (U, Г**), который представлен на рисунке 16:

Рисунок 16

2)      аналогичным образом, «вершина» графа G** = (U, Г**), поставленная в соответствие дуге (X_i, X_j) должна считаться «конфликтной» для любой другой дуги G = (E, Г), если эти дуги заходят в одну и ту же вершину X_j. Например, (см. рисунки 17 и 18), дуги (X₁, X₂), (X₃, X₂) и (X₄, X₂) будут также являться «конфликтными», и все соответствующие им вершины в графеG** = (U, Г**) должны считаться смежными.

Рисунок 17

Рисунок 18

3)      наконец, любая пара дуг (X_i, X_k) и (X_k, X_j), первая из которых заходит в вершину X_kисходного графа G = (E, Г), а вторая выходит из той же вершины того же графа, также должны считаться «конфликтными» - см. рисунки 19 и 20:

Рисунок 19

 

Рисунок 20

Мы продолжим обсуждение темы в следующей части.

Анализ существующих протоколов TDMA

Анализ существующих протоколов TDMA
Часть 3

Имея подобную информацию можно построить «матрицу коллизий» - C=║C_ij║, элементы которой могут принимать следующие значения:

Для этого достаточно:

1)  скорректировать матрицу A, воспользовавшись следующим
алгоритмом:
- поочерёдно просмотреть все строки матрицы A;
- если просматриваемая строка соответствует вершине X_j и состоит из сплошных нулей, то элемент A_jjматрицы A приравнивается нулю, если нет –единице. После выполнения данного алгоритма, нулевые элементы, которые расположены на главной диагонали матрицы A, будут соответствовать «нейтральным» вершинам графа (то есть отвечающим условию (2)). Пример такой матрицы показан на рисунке 11:

Рисунок 11

2) построить матрицу коллизий –C=║C_ij║, действуя следующим образом:

- поочерёдно просмотреть всестолбцы скорректированной матрицы A;

- при просмотре элементов каждого столбца этой матрицы, составить список вершин – E_j, отвечающих условию (4):

Aij= 1

(4)

например, (см. рисунок 2.11)  рассматривая столбец, поставленный в соответствие вершине X₁, будем иметь список (2.5):

E1= {X1, X2}

(5)

- каждой паре вершин этого списка поставить  в соответствие элемент C_ij=1.

(списку E₁ будут соответствовать элементы матрицы C, которые показаны на рисунке  12)

Рисунок 12

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

Рисунок 13

поскольку, исходя из содержания приведённой на рисунке 11 матрицы, будем иметь:

E1 = {X1, X2}

E2 = {X1, X2, X3, X5}

E3 = {X2, X3,}

E4 = {X1, X4}

E5 = {X4, X5}

E6 = {X3, X5}

Полученной таким образом матрице C=║C_ij║ будет соответствовать граф коллизий G*=(E, Г*), представленный на рисунке 14.

Рисунок 14

Построив подобный граф можно отыскать подмножества узлов, которые могут использовать один и тот же слот, не «мешая» друг другу.

В графе G*=(E, Г*) такие подмножества будут являться внутренне устойчивыми,  то есть отвечать условию (6):

 

Иными словами, никакие две вершины из S_k не смежны.

Если отбросить изолированную вершину X₆, то в представленном на рисунке 14 графе таких подмножеств - два:

1)      S₁= {X₂, X₄} –выделенное штриховыми линиями;

2)      S₂ = {X₃, X₄} – выделенное штрих-пунктирными линиями.

Исходя из этого, можно прийти к следующему выводу: вершины приведённого на рисунке 2  графа G=(E, Г) могут быть окрашены четырьмя цветами, причём возможно два равноценных решения: первое - с одинаковой окраской вершин X₂ и X₄, второе - с одинаковой окраской вершин X₃ и X₄.

Анализ существующих протоколов TDMA

Анализ существующих протоколов TDMA
Часть1. Постановка задачи и возможные подходы к её решению

При уплотнении с временным разделением (Time Division Multiplexing - TDM) распределение каналов идёт по времени, то есть передатчики передают или ретранслируют пакет на одной и той же частоте f в области s, но в различные промежутки времени t_i (циклически повторяющиеся через интервал ΔT).

Например, (см. рисунок 1) каждому потенциальному передатчику – узлу X_i может быть выделен конкретный интервал времени – слот  t_i, который не может быть использован другими конкурентными узлами.

Рисунок 1

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

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

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

Суть этой задачи заключается в следующем.Пусть сеть (или, точнее, её фрагмент, работающий на одной и той же частоте f) описывается ориентированным графом G=(E, Г), в котором

- Е – множество вершин, поставленных в соответствие узлам сети;

-  Г – однозначные соответствия между вершинами множества Е.

В качестве примера рассмотрим граф, изображенный на рисунке 2:

Рисунок 2

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

Например, (см. рисунки 2 и 3) вершины рассматриваемого графа могут быть раскрашены следующим образом:

Рисунок 3

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

-          узлам X₁, X₂ и X₅ должны соответствовать разные слоты;

-          узлыX₃ и X₄ могут использовать один и тот же слот;

-          узел X₆ не нуждается в слоте (поскольку этот узел никто «не слышит»).

Возможен и другой подход. Распределение слотов может быть основано на раскраске дуг (радиолучей). Например, на основании раскраски дуг, показанной на рисунке 4, расписание выхода в эфир может соответствовать временной диаграмме, которая представлена на рисунке 5.

Рисунок 4

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

1)  первый(«красный») слот может использоваться для передачи информации по радиолучам (X₁, X₄), (X₃, X₆) и (X₅, X₂);

2)      второй («зелёный») слот – для передачи по радиолучам (X₂, X₁) и (X₄, X₅);

3)      третий («жёлтый») слот – по радиолучу (X₂, X₃);

4)      четвёртый («синий») слот – по радиолучу (X₁, X₂);

5)      наконец, пятый («чёрный») слот может  использоваться для передачи информации по радиолучу (X₃, X₂).

Рисунок 5

Мы продолжим обсуждение темы в следующей части.