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

Алгоритм DESYNC. Достоинства и недостатки

Алгоритм DESYNC. Достоинства и недостатки.
Часть 2. 

3.      Позитивные свойства  алгоритма и его недостатки

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

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

Это объясняется тем, что, при использовании алгоритма DESYNC, узлы сети определяют моменты передачи собственных синхросигналов автономно,  опираясь лишь на  показания собственных «часов», ход которых корректируется в моменты приёма «синхросигналов» от соседей. При этом  данный алгоритм игнорирует такие атрибуты узлов, как идентификаторы (адреса) соседних узлов, их число, статус и т.п.  

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

3.3. Использование данного алгоритма обеспечивает «справедливое» деление временных интервалов между узлами -  в стационарном режиме (в независимости от числа узлов) интервалы времени между передачами очередных синхросигналов – T / n будут распределены равномерно.

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

 3.4. Однако следует отметить, что использование рассматриваемого протокола эффективно только в том случае, если топология сети отвечает условию (9):

то есть сеть является «кликой».

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

Допустим, что сеть состоит из трёх узлов и её топология соответствует графу, который изображён на рисунке 2:

Рисунок 2

Представим себе, что в сети работают только два узла – X_a и X_b, и моменты выдачи «синхросигналов» этими узлами, соответствуют временному циклу, представленному на рисунке 3:

Рисунок 3

Теперь представим себе, что, после очередной коррекции фазы в узле X_b, к сети подключился узел X_с,  и следующий цикл T будет соответствовать рисунку 4:

Рисунок 4

Такая ситуация приведёт к сдвигу фазы узла X_b, причём «новая» фаза этого узла будет стремиться к середине интервала времени между выдачей «синхросигналов» от узла X_a (воспринимаемого как узел X_b-1) и X_с (воспринимаемого как узел X_b+1).

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

1)      узел X_c зафиксирует длину интервала Δ_с(t), воспринимая  X_b  как источник «синхросигнала» от  мнимого  узла X_c-1;

2)      узел X_a  зафиксирует либо длину интервала Δ_a(t), либо длину интервала Δ_a+1(t)  (в последнем случае процедуры коррекции фазы в узле X_a будут выполнены, но фаза этого узла практически не изменится).

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

- получив  следующий «синхросигнал» от X_b, узел X_с сдвинет свою фазу так, что момент выдачи «синхросигнала» X_c  в следующем цикле будет смещён в сторону X_a, (см. рисунок 5):

Рисунок 5

- если узел X_a воспринимает «синхросигнал» от X_b как сигнал от источника X_a+1, то он также сдвинет свою фазу, но в противоположенную сторону – навстречу X_с (см. рисунок 6):

Рисунок 6

- возникает коллизия, в результате чего узел X_b перестанет воспринимать сигналы от своих соседей и будет менять свою фазу только за счёт погрешности собственных «часов»;

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

Возможны другие (может и более благополучные) сценарии, но приведённого примера вполне достаточно, чтобы убедиться в том, что использование алгоритмов DESYNC в сетях, не отвечающих условию (9), не имеет смысла.

Алгоритм DESYNC. Достоинства и недостатки

Алгоритм DESYNC. Достоинства и недостатки.
Часть1.

Вашему вниманию предлагается оригинальный алгоритм (DESYNC: ftp://ftp.deas.harvard.edu/techreports/tr-18-06.pdf), который может быть использован для распределения нагрузки между группами узлов, подключенных к одному и тому же групповому каналу.

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

Экспериментальные исследования [1] показали ощутимое снижение потери сообщений в условиях конкурентной среды с 58% до 1%, так же как и 25% увеличение пропускной способности.

1.      Основные принципы.

1.1. Представим себе полносвязную сеть («клику»), которая включает в себя n узлов. Будем считать, что любой узел такой «клики» - X_i, может рассматриваться как некий генератор синхросигналов, выдаваемых с частотой - ω, которая определяется соотношением (1):

ω = 1 / T

(1)

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

Фаза, на которой находится каждый конкретный узел X_i, может быть определена величиной ϕ _i(t), которая может принимать значения от 0 до 1, причём значения ϕ_i(t) определяются
отдельно для каждой вершины, то есть число индексов i будет зависеть от числа вершин в «клике» и определяться неравенством (2):

  1.2. Вычисление величины ϕ_i(t) в каждом узле X_i, должно осуществляться автономно, с помощью собственных «внутренних часов», причём в момент времени, когда величина ϕ_i(t) достигнет единицы, узел X_i выдаёт в сеть синхросигнал, после чего приравнивает ϕ_i(t) нулю.

Значение величины ϕ_i(t) должно всегда соответствовать доле интервала времени T, которое прошло после установки ϕ_i(t) в ноль. Например, значение ϕ_i(t)=0.75 соответствует тому, что узел X_i отсчитал 75% времени T.

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

Более того, процедуры коррекции фаз должны стремиться к тому, чтобы интервал времени Δ_i(t) между выдачей синхросигнала любым узлом X_i-1 и выдачей синхросигнала следующим за ним узлом X_i – интервал Δ_i(t), равнялся интервалу Δ_i*(t), который определяется соотношением (3):

Δi*(t) = T / n

(3)

Если условие (3) выполняется для всех вершин «клики», то процесс коррекции фаз ϕ_i(t) может считаться завершённым. В противном случае – сеть должна считаться полностью или частично рассинхронизированной.

1.      Механизмы коррекции фазы.

1.1.Суть механизма коррекции фаз в DESYNC заключается в следующем:

1)      поскольку каждый узел «клики» - X_i способен установить факт передачи синхросигнала от любого узла X_jГ^-1X_i, то он способен получать информацию от узлов X_i-1 и X_i+1, первый из которых выдал синхросигнал перед синхросигналом от X_i, второй – вслед за синхросигналом от X_i;

2)  наблюдая за эфиром, любой узел X_i может получить информацию о фактах передачи синхросигналов всеми узлами «клики»;

3) имея такую информацию узел X_i способен вычислить среднюю точку между выдачей синхросигнала узлом X_i-1 и выдачей синхросигнала узлом X_i+1; Для этого достаточно воспользоваться выражением  (4):

где Φ_i-1(t) и  Φ_i+1(t) – фазы приёма синхросигналов от узлов X_i-1 и X_i+1, по «местному времени» узла X_i;  

4)      после того, как значение Φ_mid(t) определено, узел X_i может скорректировать свою фазу, заменяя ϕ_i(t) на величину ϕ_i^*(t), которая определяется с помощью формулы (5):

где α – параметр, который отвечает неравенству (6):

Этот параметр позволяет ограничить  колебания фазы при её коррекции - чем ниже  значение α - тем незначительней «коррекционный эффект»;

5)      коррекция фазы осуществляется сразу после получения синхросигнала от X_i+1.

2.2.       В принципе, для вычисления Φ_mid(t), достаточно воспользоваться выражением (4).. Но, возможно и более  рациональное решение. Величина Φ_mid(t) может быть определена с помощью выражения (7):

где

- Δ_i – текущее значение величины ϕ_i(t)  в момент получения последнего синхросигнала от всех соседей X_i (до момента времени, когда ϕ_i(t)=1);

- Δ_i+1 - значение величины ϕ_i(t) в момент получения первого синхросигнала от любого соседнего узла, принятого после момента выдачи синхросигнала узлом X_i.

 2.3. Такое решение может быть проиллюстрировано следующими примерами.

Предположим, что последовательность выдачи синхросигналов узлами X_i-1 , X_i  и X_i+1 соответствует временной диаграмме, которая представлена на рисунке 1:

Рисунок 1

Допустим, что синхросигнал от узла X_i-1 принят в тот момент времени, когда «часы» узла X_i показывают ϕ_i(t)=0.7. Эта величина фиксируется в памяти узла X_i.  Тогда, в момент времени, когда узел X_i будет выдавать «собственный» синхросигнал, он может установить, что Δ_i(t)=0.7.

Аналогичным образом, после получения синхросигнала от X_i+1, может быть установлена величина Δ_i+1. Предположим, что Δ_i+1=0.3. Тогда, имея  Δ_i(t)=0.7 и Δ_i+1=0.3 с помощью выражения (8) можно получить:

Φ_mid(t) = ϕ_i(t) + {[Δ_i+1 - Δ_i(t)] / 2} = 1 + (0.3 – 0.7) / 2 = 1 – 0.2 = 0.8

Предположим, что заданный параметр α=0.5. В таком случае, пользуясь формулой (5), можно получить: 

ϕ_i^*(t) = (1- α) ϕ_i(t) + α Φ_mid(t) = 0.5x0.3 + 0.5x0.8 = 0.55

что соответствует  «подгону» фазы ϕ_i(t), - поскольку установка ϕ_i^*(t) будет осуществлена при ϕ_i(t)=Δ_i+1=0.3, то  текущее значение ϕ_i(t) будет увеличено.      

Аналогичным образом, может быть осуществлено «осаживание» фазы ϕ_i(t).

Такое событие произойдёт в том случае, если после измерения величин Δ_i и Δ_i+1 выяснится, что эти величины  отвечают неравенству (8):  

Δi+1 > Δi

(8)

Например, при Δ_i(t)=0.3, Δ_i+1=0.7 и α=5, будем иметь:  

Φ_mid(t) = 1 + (0.7 – 0.3) / 2 = 1.2

Округлив эту величину по модулю 1, получим Φ_mid(t) = 0.2, и, при α=0.5, будем  иметь:

ϕ_i^*(t) = (1- α) ϕ_i(t) + α Φ_mid(t) = 0.5x0.7 + 0.5 x 0.2 = 0.36

Таким образом, коррекция фазы будет осуществлена при ϕ_i(t)=Δ_i+1=0.7, следовательно, текущее значение ϕ_i(t) будет уменьшено.

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

Анализ существующих протоколов 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

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