Показаны сообщения с ярлыком маршрутизация. Показать все сообщения
Показаны сообщения с ярлыком маршрутизация. Показать все сообщения

вторник, 14 октября 2014 г.

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-сетях.

понедельник, 1 апреля 2013 г.


Возможная структура управления в самоорганизующихся системах связи

Исходя из приведенного примера, можно сделать следующие выводы:
1) Свойства и характеристики системы и её окружающей среды могут изменяться во времени, причём законы, по которым они изменяются, далеко не всегда поддаются прогнозу. Тем не менее, управление системой без знаний о её состоянии и состоянии среды (и, самое главное - имеющихся ресурсов) практически невозможно.

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

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

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

Действительно, система может требовать не оптимального, а лишь достаточно хорошего (рационального) управления. Например, управление системой, может быть основано на использовании относительно небольшого числа «шаблонных» решений.

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

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


Возможный подход к решению задач управления и «самоорганизации».


1) Задача управления системой разбивается на несколько подзадач или слоев:
● управление ресурсами канального и физического уровней;
 управление ресурсами сетевого уровня;
 управление безопасностью;
● прочие

2) Каждая из этих подзадач решается в какой-то степени автономно, однако все подзадачи должны быть подчинены одной и той же цели - поддержке высокого уровня надёжности и живучести системы. Эти задачи взаимосвязаны и взаимозависимы: например, несоответствие радиочастот и маршрутов у абонентов одного и того же канала приведёт к невозможности передачи/приёма пакетов по этому каналу, использование топологии системы, в составе которой указаны «неорганизованные» каналы приведёт к неверному расчету маршрутов.

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

4) Управление ресурсами системы должно осуществляться централизовано: администратором системы со специально выделенного автоматизированного рабочего места (АРМ). Для эффективного управления системой, АРМ должно обеспечивать:
наглядную интерпретацию текущей топологии системы и её ресурсов;
оценку возможности дистанционной доставки служебной (настроечной) информации оборудованию при осуществлении манёвров частотами, каналами и т.д.;
оценку последствий возможных решений администратора системы (потери/восстановления топологической связности и т.п.);
оповещение администратора о возникновении нештатных ситуаций, требующих вмешательства соответствующего технического персонала (ремонтных бригад, экспедиторов и т.п.);

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

четверг, 28 марта 2013 г.



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

Рисунок 1

Предположим, что в этой системе используется статическая маршрутизация, (сеть типа ad hoc) то есть маршруты заданы таким образом, что каждой паре абонентов Xi и Xj соответствует единственный (непосредственный) маршрут Xi - Xj. При таких условиях подсистема Z** может находиться в единственном состоянии и, следовательно, H(Z**)=0. Если в процессе эксплуатации системы, условия радиослышимости в канале меняются, то H(Z*)>0. Но подсистема Z** никак не реагирует на эти изменения, поэтому H0=H1, и R=H0-H1=0. Следовательно, система предельно неорганизованна.

Допустим теперь, что подсистема Z** построена таким образом, что каждому непосредственному маршруту Xi - Xj, (кроме маршрутов от Xk) ставиться в «жесткое» соответствие единственный обходной маршрут вида XiXk - Xj (Xk – некая общая «точка доступа», вариант построения сети ad hoc):

Рисунок 2

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

Попытаемся оценить уровень организации такой системы. Действуем поэтапно, в соответствии с выражениями (3.2) – (3.6).
1) Будем считать, что вероятность отказа любого радиолуча в канале равна P. Тогда
H(Z*)= - Cmj {Pj (1- P)m-j log2[ Pj (1- P)m-j]

(3.1)
где
m – общее число радиолучей в радиосети, равное

m = n(n-1)/2
(3.2)
n – общее число маршрутизаторов, включая «точку доступа».

2) Если считать, что каждый маршрутизатор (кроме точки доступа) выбирает обходной или основной маршрут с равной вероятностью (по принципу «орёл – решётка»), то
H(Z**) = log2 2(n-1)(n-2)/2 = (n-1)(n-2)/2
(3.3)

3) Общее число ситуаций в Z*, которым соответствует однозначная реакция подсистемы Z**, ограничено. Действительно (см. рисунок 2), если абонент Xi намерен передать пакет Xj, то он воспользуется обходным маршрутом XiXk - Xj только в том случае, если вышел из строя радиолуч Xi - Xj. Аналогичным образом, абонент Xj воспользуется обходным маршрутом XjXkXi только при отказе радиолуча Xi - Xj и т.д.

И вообще, однозначное соответствие состояния подсистемы Z**состоянию сети Z* возможно только тогда, когда изменения состояний радиолучей будут происходить только в пределах подмножества E1 (на рисунке 2 эти лучи выделены жирными линиями). Причем в любой из таких ситуаций P(Zj*|Zk**)=1.

Изменения структуры вне E1 на поведение системы не влияют, так как любая неудачная попытка передачи пакета по основному маршруту между любыми XiE1 всегда приводит к передаче того же пакета по обходному маршруту (независимо от состояния радиолуча Xi - Xk) Поэтому:
H (Z*|Z**) =CLk Pk(1-P)L-k {-Cn-1j Pj(1-P)n-(j+1) log2 [Pj(1-P)n-(j+1))]}

(3.4)
где L = (n-1)(n-2)/2 – число радиолучей в E1.

Графики зависимостей Н(Z*) и R от величины P (для сети, включающей в себя 8 маршрутизаторов), приведены на рисунке 3.
Рассматривая эти графики, нетрудно заметить, что рассматриваемая система далека от совершенства: RН(Z*) только при весьма надежных каналах связи (P0.05).
Рисунок 3

Но, при определённых условиях, уровень организации такой системы может быть признан достаточно высоким. Например, если радиолучи, связывающие абонентов сети с общей «точкой доступа», обладают достаточно высокой надежностью – с вероятностью отказа =0.15, а остальные каналы менее надежны – с P0.5, то
H(Z*)= -CLk Pk log2[Pk(1-P)L-k] - Cn-1j j(1-)n-(j+1) log2[ j(1-)n-(j+1)]

(3.5)
H (Z*|Z**) =CLk Pk(1-P)L-k {-Cn-1j j(1-)n-(j+1) log2 [j(1-)n-(j+1))]}

(3.6)
и величина R сопоставима с H(Z*) даже при P=0.5 (см. рисунок 4).

Отметим что в данном случае, степень организации системы увеличивается за счёт уменьшения энтропии H(Z*), которое, в свою очередь, достигается за счёт повышения надежности части радиолучей. Очевидно, что при их стопроцентной надёжности (то есть при =0) величина H(Z*) станет равной R, и уровень организации в системе может считаться идеальным.

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

Рисунок 4

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

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

Поэтому, есть основания предполагать, что высокоорганизованные протоколы маршрутизации могут найти применение только в высокоскоростных сетях (типа wi-fi). В низкоскоростных УКВ-сетях более целесообразна реализация алгоритмов типа ad-hoc.