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

Алгоритм 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) будет уменьшено.

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

Имитационная модель канала коллективного доступа

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

Имитация процессов передачи и приёма кадра

1.1. В упрощенном виде, процесс передачи кадра по радиолучу (X_i, X_j) может быть представлен, как поведение композиции конечных автоматов, которая изображена на рисунке 1:

Рисунок 1

1.2. Изображённый на рисунке 1 «Таймер» X_i предназначен для определения моментов времени, соответствующих:

1) времени отсрочки начала передачи очередного пакета (кадра);

2) времени завершения передачи;

3) времени ожидания «квитанции».

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

1.3. «Таймер» X_j – определяет момент начала и завершения передачи квитанции, причём поведение этого таймера всегда детерминировано. Следует отметить, что, как «Таймер» X_i, так и «Таймер» X_i, ведут отсчёт интервалов времени в особых условных единицах – «тиках».

Предположительно, один «тик» имитирует интервал времени, соответствующий длительности одного «слота».

1.4. Автомат, который имитирует процесс управления передачей кадра по радиолучу (X_i, X_j) фактически выполняет функции «диспетчера», взаимодействующим со своим «окружением» с помощью следующих сигналов:

1) сигналов S_тр⁽ⁱ⁾ и S_обс⁽ⁱ⁾, обеспечивающих взаимодействие с протоколом «высшего» уровня, который «поставляет» кадры для передачи, причём:

- сигнал S_тр⁽ⁱ⁾ соответствует поступлению очередного требования на передачу кадра;

- сигнал S_обс⁽ⁱ⁾, который соответствует запросу очередного требования на обслуживание, когда предыдущая заявка на обслуживание уже выполнена.

2) сигналов S_T⁽ⁱ⁾ и S_⁽ⁱ⁾, первый из которых определяет тип интервала времени, а именно:

- времени отсрочки передачи пакета;

- времени завершения передачи пакета;

- времени ожидания квитанции,

а второй – S_⁽ⁱ⁾ – завершению отсчёта заданного интервала.

3) сигналов S_прд⁽ⁱ⁾ и S_кв^(j), обеспечивающих имитацию взаимодействия с «приёмной стороной» (автоматом «Управление приёмом в X_j»). При этом сигнал S_прд⁽ⁱ⁾ = 1 оповещает все «станции» X_j о том, что передатчик X_i находится в состоянии передачи. 

4) и, наконец, сигнала S_зан, запрещающего выход в эфир, формируемого «анализатором занятости канала». Данный анализатор представляет собой тривиальный автомат, реализующий булеву функцию (1):

Sзан = A1i Sпрд(1) v A2i Sпрд(2) v . . . v ANi Sпрд(N)

(1)

где

- A_ki (k=1, 2, . . . , N) – элементы матрицы смежности A=║A_ij║, описывающей граф G=(E,Г), соответствующий текущему состоянию сети;

- S_прд^(k) (k=1, 2, . . . , N) – значения сигналов, соответствующих состояниям конкурирующих станций: если конкурент X_k ведёт передачу, то S_прд^(k) =1.

- N – число узлов в сети.

Следует отметить, что функция (1) может быть использована только в том случае, если все узлы сети работают на одной и той же частоте. Если же это условие не выполняется, то функция (1) должна быть дополнена действием (2):

Sпрд(k) : = 0, если Xiwi, Xjwi, но Xkwi

(2)

1.5. Хотя функции (1) и (2) и тривиальны, но, по-видимому, требуют пояснений. Для этого рассмотрим следующий пример. Пусть условия радиослышимости описываются графом, который изображён на рисунке 2:

Рисунок 2

Такому графу будет соответствовать матрица A=║A_ij║, которая представлена на рисунке 3:

	Xi	Xj	Xb	Xc	Xd
Xi	0	1	1	1	1
Xj	1	0	0	1	1
Xb	1	0	0	1	0
Xc	1	1	1	0	1
Xd	0	1	0	1	0

Рисунок 3

Теперь предположим, что на частоту w_i претендуют передатчик X_i и его конкуренты – станции X_b и X_d. Сравнивая пары значений A_ki S_прд^(k), получим картину, представленную на рисунке 4:

	Aki		Sпрд(k)
Xi	0	&	1	= 0
Xj	1	&	0	= 0
Xb	1	&	1	= 1
Xc	1	&	0	= 0
Xd	0	&	1	= 0

Рисунок 4

Это означает, что станция X_i способна уступить канал станции X_b, но никогда не обнаружит каких-либо признаков активности со стороны станции X_d. Но, это - особенность IEEE 802.11 ….

1.6. Поведение автомата «Управление передачей» может быть описано диаграммой состояний, представленной на рисунке 5:

Рисунок 5

Данный автомат может находиться в одном из восьми состояний:

1. St₀ – исходное состояние - ожидание заявки на передачу кадра;
2. St₁ – ожидание освобождения канала;
3. St₂ – запуск таймера, обеспечивающего отсчёт времени отсрочки начала передачи пакета, а также момента времени завершения его передачи;
4. St₃ – ожидание собственного «слота»;
5. St₄ – передача пакета в эфир;
6. St₅ – запуск таймера ожидания квитанции;
7. St₆ – ожидание квитанции;
8. St₇ – оповещение о факте неудачной попытке передачи кадра.

Переходы данного автомата из одного состояния в другое осуществляются под воздействием символов входного алфавита - _i, то есть под воздействием конкретных комбинаций входных сигналов. Эти комбинации приведены в таблице 1:

Таблица 1

Символ входного алфавита	Значения входных сигналов
	Sтр(i)	S(i)	Sкв(i)	Sзан(i)
λ0	0	x	x	x
λ1	1	x	x	x
λ2	x	x	x	1
λ3	x	x	x	0
λ4	x	0	x	0
λ5	x	1	x	x
λ6	x	0	x	x
λ7	x	1	x	x
λ8	x	0	0	0
λ9	x	0	1	0

Рассматривая таблицу 1, нетрудно заметить, что, практически во всех комбинациях _i, большинству значений сигналов поставлен в соответствие знак «×». Это означает, что при рассмотрении условий перехода под воздействием символа _i данный сигнал должен игнорироваться.

Кроме того, условия выполнения некоторых переходов не заданы. Например, в представленной на рисунке 5 диаграмме не определены условия перехода из состояния St₂ в состояние St₃. Это объясняется следующим образом. При построении данной диаграммы считалось, что подобные переходы безусловны (на рисунке 5 такие переходы выделены жирными линиями). Обозначим такие переходы символом *.

1.7. Показанная на рисунке 5 диаграмма состояний может быть формализована и представлена в виде таблицы переходов, которая изображена на рисунке 6:

Состояние	Символы входного алфавита
	λ0	λ1	λ2	λ3	λ4	λ5	λ6	λ7	λ8	λ9	λ*
St0	St0	St1	-	-	-	-	-	-	-	-	-
St1	-	-	St1	St2	-	-	-	-	-	-	-
St2	-	-	-	-	-	-	-	-	-	-	St3
St3	-	-	St1	-	St3	St4	-	-	-	-	-
St4	-	-	-	-	-	-	St4	St5	-	-	-
St5	-	-	-	-	-	-	-	-	-	-	St6
St6	-	-	St7	-	-	-	-	St7	St6	St0
St7	-	-	-	-	-	-	-	-	-	-	St0

Рисунок 6

Такое представление изучаемого процесса достаточно удобно для его имитации.

1.8. Реакции автомата на входные сигналы представляются в виде выходного алфавита, каждый символ которого - µ_k, соответствует конкретной комбинации выходных сигналов. Перечень всех возможных комбинаций µ_k может быть оформлен в виде таблицы выходов, в данном случае – таблицы 2:

Таблица 2

Символ выходного алфавита	Значения выходных сигналов
	Sобс(i)	ST(i)	Sпрд(i)
µ0	Sобс(i)=1- запрос очередного кадра	0	0
µ1	0	0	0
µ2	0	ST(i)=1 – время отсрочки передачи	0
µ3	0	0	1
µ4	0	ST(i)=2 – время ожидания квитанции	0
µ5	Sобс(i)=2 – оповещение о неудаче	0	0

Данные символы ставятся в соответствие состояниям автомата. Для рассматриваемого автомата это соответствие может быть задано таблицей 3:

Таблица 3

Состояние автомата	Выходная комбинация
St0	µ0
St1	µ1
St2	µ2
St3	µ1
St4	µ3
St5	µ4
St6	µ1
St7	µ5

1.9. Аналогичным образом может быть интерпретировано поведение приёмной стороны – автомата «Управление приёмом» (см. рисунок 1). Его поведение может быть описано диаграммой состояний, которая показана на рисунке 7:

Рисунок 7

Данный автомат может находиться в одном из пяти состояний:

1. St₀ – исходное состояние - ожидание очередного кадра;
2. St₁ –приём кадра;
3. St₂ – завершение приёма кадра; запуск таймера, отсчитывающего время передачи квитанции;
4. St₃ – передача квитанции;
5. St₄ – фиксация нарушения процесса приёма.

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

Таблица 4

Символ входного алфавита	Значения входных сигналов
	S*прд(i)	S(j)	Sош(j)	Sкол(j)
λ0	0	x	x	x
λ1	1	x	0	0
λ2	1	x	1	0
λ3	1	x	x	1
λ4	x	0	x	x
λ5	x	1	x	x

где S*_прд⁽ⁱ⁾ – определяется с помощью выражения (3)

S*прд(i) = Sпрд(i)Aij

(3)

1.10. Приведённой на рисунке 5 диаграмме состояний соответствует таблица переходов, которая представлена на рисунке 8:

Состояние	Символы входного алфавита
	λ0	λ1	λ2	λ3	λ4	λ5	λ*
St0	St0	St1	St4	St4	-	-	-
St1	St2	St1	St4	St4	-	-	-
St2	-	-	-	-	-	-	St3
St3	-	-	-	-	St3	-	-
St4	St0	-	St4	St4	-	-	-

Рисунок 8

1.11. Выходной алфавит автомата «Управление приёмом» может быть задан таблицей 5, а функция соответствия выходных символов состояниям данного автомата – таблицей 6:

Таблица 5

Символ выходного алфавита	Значения выходных сигналов
	Sкв(j)	ST(j)	Sтр(j)
µ0	0	0	0
µ1	0	1 – запуск таймера	1 – приём кадра
µ2	1- квитанция	0	0

Таблица 6

Состояние автомата	Выходная комбинация
St0	µ0
St1	µ0
St2	µ1
St3	µ2
St4	µ0

1.12. Рассмотренная модель управления процессом приёма кадра, хотя и проста, но всё же вполне адекватна поведению оригинала.

Это достигается тем, что в схему модели включён ещё один тривиальный автомат – «имитатор коллизий», суть работы которого заключается в следующем. Известно, что коллизии в канале могут возникнуть в следующих случаях:

1. если конкурирующая станция X_k не «слышит» передатчик X_i и может выйти в эфир, не дождавшись завершения процесса передачи кадра;
2. если станция X_k заняла тот же слот, что и X_i.

Очевидно, что, и в том, и другом случае, помешать успешной передаче кадра по радиолучу X_i – X_j может только та станция X_k, которая отвечает условию (4), что соответствует ситуации, когда станция X_j «слышит» X_k:

XkГ-1Xj

(4)

Условие возникновения подобного рода коллизий может быть сформулировано булевой функцией (5):

Sкол = A1j Sпрд(1) v A2j Sпрд(2) v . . . v ANj Sпрд(N)

(5)

где

- A_ki (k=1, 2, . . . , N) – элементы матрицы смежности A=║A_ij║, описывающей граф G=(E,Г), соответствующий текущему состоянию сети;

- S_прд^(k) (k=1, 2, . . . , N) – значения сигналов, соответствующих состояниям конкурирующих станций: если конкурент X_k ведёт передачу, то S_прд^(k) =1.

Следует отметить, что при вычислении значения S_кол, необходимо рассматривать только те сигналы S_прд^(k) индекс которых - k, не равен i, (передатчик - «сам себе» не мешает).

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

Известно, что вероятность искажения пакета, в основном, зависит от уровня помех в эфире. Этот уровень описывается величиной SNR (Signal-to-Noise Ratio), или соотношением сигнал/шум, которое задаётся известной формулой (6):

SNR = 20 log10 (Ps / Pn)

(6)

где P_s и P_n – уровни сигнала и шума соответственно.

На основании этой величины может быть определена средняя вероятность искажения одного бита пакета - P_ош. В случае отсутствия механизмов защиты от ошибок, зависимость между P_ош и SNR определяется типом модуляции сигнала которая, формально может быть представлена, как некая нелинейная функция (7):

Pош = Q [SNR]

(7)

В случае же наличия таких механизмов, реальный уровень P_ош будет значительно ниже по причине того, что искажённая помехами информация может быть частично восстановлена на приёмной стороне. Поэтому более целесообразно, определять величину P_ош, базируясь на экспериментальных данных. Например, для определения величины могут быть использованы графики зависимости интенсивности радиопомех (BER) от отношения сигнал/шум (SNR), которые представлены на рисунке 9:

Рисунок 9

Имея подобный график (разумеется, представленный в табличной форме), а также длину пакета – L, можно вычислить вероятность искажения пакета – P(L).

Если исходить из предположения, что искажения разных битов одного и того же пакета происходят независимо друг от друга, то величина P(L) может быть вычислена с помощью выражения (8):

P(L) = 1 – (1 - Pош) L

(8)

Но если учитывать тот факт, что, в сетях IEEE 802.11, заголовок кадра передаётся на минимальной скорости – V_min, а данные (на MAC-уровне) на более высокой – V_i, то выражение (7) перепишется, и будет иметь вид (9):

P(L) = [1 – (1 - Pош (1)) h] [1 – (1 - Pош (i)) l]

(9)

где

- P_ош ⁽¹⁾ – вероятность ошибки при передаче заголовка;

- h – длина заголовка (константа);

- P_ош ⁽ⁱ⁾ – вероятность ошибки при передаче MAC-части кадра;

- l - длина MAC-части.

1.14. При использовании графиков, подобных тем, которые представлены на рисунке 9, необходимо иметь величину SNR. Если исходить из предположения, что единственной причиной затухания сигнала является потери в свободном пространстве [1], то эта величина может быть вычислена с помощью выражения (10):

SNR = 10 lg [(4π)2 D2 / Gt Gr λ2]

(10)

где

- D – расстояние между антеннами;

- G_t - коэффициент усиления передающей антенны;

- G_r - коэффициент усиления приёмной антенны;

- λ – длина волны несущей.

Имея величину SNP можно определить вероятность успешной попытки передачи пакета. Для этого достаточно:

1. определить значение функции P_ош = Q [SNR] (см. п. 1.13.);
2. с помощью выражения (9) определить вероятность доведения пакета.

1.15. Поскольку выражение (9) является функцией от величины P_ош и длины пакета, то при имитации процесса передачи пакета по радиолучу (в ситуации, когда канал уже захвачен) лучше всего использовать следующий алгоритм:

1) при «возникновении» события, соответствующего началу передачи кадра, определяется величина P(L);

2) генерируется случайное число 0 <  < 1;

3) проверяется условие (11):

P(L) > 

(11)

3. если условие (11) выполняется, то сигнал S_ош^(j) (см. п. 1.9) приравнивается единице, в противном случае - тот же сигнал приравнивается нулю.

1.16. Но возможен и другой подход. Если дисперсия средней длины пакета (точнее кадра) невелика, то величины P(L) для всех радиолучей могут быть вычислены заранее, ещё при подготовке данных для моделирования, и внесены в матрицу P=║P_ij║ (см. п. 2.2.1), которая «предвосхищает» результат попытки передачи пакета по соответствующему радиолучу. И ошибки в канале будут интерпретироваться как временные нарушения радиослышимости.

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

Следующая статья будет посвящена вопросам реализации модели канала.