Механизмы коллективного доступа в сетях 802.11

Сергей Пахомов

Функция распределенной координации DCF

Функция централизованной координации PCF

Расширенная функция распределенной координации EDCF

Гибридная функция координации HCF

В статье «Протоколы беспроводных локальных сетей», с которой можно ознакомиться в этом номере журнала, подробно рассмотрен физический (PHY) уровень беспроводных протоколов семейства 802.11. На физическом уровне определяются механизмы, которые используются для преобразования данных, для обеспечения требуемой скорости передачи в зависимости от среды передачи данных. Таким образом, физический уровень определяет методы кодирования/декодирования и модуляции/демодуляции сигнала при его передачи и приеме.

акие вопросы, как регулирование совместного использования среды передачи данных, определяются не на физическом, а на более высоком уровне — уровне доступа к среде передачи данных, который называют МАС-уровнем (Media Access Control). Именно на MAC-уровне устанавливаются правила совместного использования среды передачи данных одновременно несколькими узлами беспроводной сети.

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

На MAC-уровне протокола 802.11 определяются два типа коллективного доступа к среде передачи данных: функция распределенной координации (Distributed Coordination Function, DCF) и функция централизованной координации (Point Coordination function, PCF). Рассмотрим более подробно каждый из этих механизмов.

Функция распределенной координации DCF

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

Одним из вариантов организации равноправного доступа к среде передачи данных является функция распределенной координации (DCF). Эта функция основана на методе коллективного доступа с обнаружением несущей и механизмом избежания коллизий (Carrier Sense Multiple Access/Collision Avoidance, CSMA/CA). При такой организации каждый узел, прежде чем начать передачу, как бы прослушивает среду, пытаясь обнаружить несущий сигнал, и только при условии, что среда свободна, может начать передачу данных.

Однако, как мы уже отмечали, в этом случае велика вероятность возникновения коллизий: когда два или более узлов сети одновременно (или почти одновременно) решат, что среда свободна, и начнут предавать данные. Для того чтобы снизить вероятность возникновения подобных ситуаций, используется механизм избежания коллизий (Collision Avoidance, CA). Суть данного механизма заключается в следующем. Каждый узел сети, убедившись, что среда свободна, прежде чем начать передачу, выжидает в течение определенного промежутка времени. Этот промежуток является случайным и складывается из двух составляющих: обязательного промежутка DIFS (DCF Interframe Space) и выбираемого случайным образом промежутка обратного отсчета (Backoff time). В результате каждый узел сети перед началом передачи выжидает в течение случайного промежутка времени, что значительно снижает вероятность возникновения коллизий, поскольку вероятность того, что два узла сети будут выжидать в течение одного и того же промежутка времени, чрезвычайно мала.

Для того чтобы гарантировать всем узлам сети равноправный доступ к среде передачи данных, необходимо соответствующим образом определить алгоритм выбора длительности промежутка обратного отсчета (Backoff time). Промежуток обратного отсчета хотя и является случайным, но в то же время определяется на основании множества некоторых дискретных промежутков времени, то есть равен целому числу элементарных временных промежутков, называемых тайм-слотами (SlotTime). Для выбора промежутка обратного отсчета каждый узел сети формирует так называемое окно конкурентного доступа (Contention Window, CW), использующееся для определения количества тайм-слотов, в течение которых станция выжидала перед передачей. Фактически окно CW — это диапазон для выбора количества тайм-слотов, причем минимальной размер окна определяется в 31 тайм-слот, а максимальный размер — в 1023 тайм-слота. Промежуток обратного отсчета определяется как количество тайм-слотов, определяемое исходя из размера окна CW:

Backoff time = (Random[CWmin, CWmax]ЅSlotTime.

Когда узел сети пытается получить доступ к среде передачи данных, то после обязательного промежутка ожидания DIFS запускается процедура обратного отсчета, то есть включается обратный отсчет счетчика тайм-слотов начиная от выбранного значения окна CW. Если в течение всего промежутка ожидания среда оставалась свободной (счетчик обратного отсчета равен нулю), то узел начинает передачу.

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

Рис. 1. Реализация равноправного доступа к среде передачи данных в методе DCF

Рассмотренный алгоритм реализации коллективного доступа к среде передачи данных гарантирует равноправный доступ всех узлов сети к среде. Но при таком подходе вероятность возникновения коллизий хотя и мала, но все-таки существует. Понятно, что снизить вероятность возникновения коллизий можно путем увеличения максимального размера формируемого окна CW. Однако это увеличит времена задержек при передачи и тем самым снизит производительность сети. Поэтому в методе DCF для минимизации коллизий используется следующий алгоритм. После каждого успешного приема кадра принимающая сторона через короткий промежуток SIFS (Short Interframe Space) подтверждает успешный прием, посылая ответную квитанцию — кадр ACK (ACKnowledgement) (рис. 2). Если в процессе передачи данных возникла коллизия, то передающая сторона не получает кадр ACK, свидетельствующий об успешном приеме. В этом случае размер CW-окна для передающего узла увеличивается почти вдвое. Так, если для первой передачи размер окна равен 31 слоту, то для второй попытки передачи он уже составляет 63, для третьей — 127, для четвертой — 255, для пятой — 511, а для всех последующих  — 1023 слота. Таким образом, для каждой i-й передачи (если все предыдущие оказались безуспешными) размер CW-окна увеличивается по следующему правилу:

CWi=CWi-1+1.

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

Рис. 2. Кадры квитанции, отсылаемые в случае успешной передачи данных

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

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

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

Для того чтобы разрешить проблему скрытых узлов, функция DCF опционально предусматривает возможность использования алгоритма RTS/CTS.

В соответствии c алгоритмом RTS/CTS каждый узел сети, перед тем как послать данные «в эфир», сначала отправляет специальное короткое сообщение, которое называется RTS (Ready To Send) и означает готовность этого узла к отправке данных. Такое RTS-сообщение содержит информацию о продолжительности предстоящей передачи и об адресате и доступно всем узлам в сети (если только они не скрыты от отправителя). Это позволяет другим узлам задержать передачу на время, равное объявленной длительности сообщения. Приемная станция, получив сигнал RTS, отвечает посылкой сигнала CTS (Clear To Send), свидетельствующего о готовности станции к приему информации. После этого передающая станция посылает пакет данных, а приемная станция должна передать кадр ACK, подтверждающий безошибочный прием. Последовательность отправки кадров между двумя узлами сети показана на рис. 3.

Рис. 3. Взаимодействие между двумя узлами сети в соответствии с алгоритмом RTS/CTS

Теперь рассмотрим ситуацию, когда сеть состоит из четырех узлов: A, B, C и D (рис. 4). Предположим, что узел C находится в зоне досягаемости только узла A, узел A находится в зоне досягаемости узлов C и B, узел B находится в зоне досягаемости узлов A и D, а узел D находится в зоне досягаемости только узла B. В такой сети имеются скрытые узлы: узел C скрыт от узлов B и D, а узел A скрыт от узла D.

Рис. 4. Решение проблемы скрытых узлов в алгоритме RTS/CTS

В подобной сети алгоритм RTS/CTS позволяет справиться с проблемой возникновения коллизий, которая не решается посредством рассмотренного базового способа организации коллективного доступа в DCF. Действительно, когда узел A пытается передать данные узлу B, то для этого он посылает сигнал RTS, который, помимо узла B, получает также узел C, но не получает узел D. Узел C, получив данный сигнал, блокируется, то есть приостанавливает попытки передавать сигнал до момента окончания передачи между узлами A и B. Узел B в ответ на полученный сигнал RTS посылает кадр CTS, который получают узлы A и D. Узел D, получив данный сигнал, также блокируется на время передачи между узлами A и B.

У алгоритма RTS/CTS имеются свои подводные камни, которые в определенных ситуациях могут приводить к снижению эффективности использования среды передачи данных. Например, в некоторых ситуациях возможно такое явление, как распространение эффекта ложных блокировок узлов, что в конечном счете может привести к ступору сети.

Рассмотрим, к примеру, сеть, показанную на рис. 5. Пусть узел B пытается передать данные узлу A, посылая ему кадр RTS. Поскольку этот кадр получает также и узел C, то он блокируется на время передачи между узлами A и B. Узел D, пытаясь передать данные узлу C, посылает кадр RTS, но поскольку узел C заблокирован, то он не получает ответа и начинает процедуру обратного отсчета с увеличенным размером окна. В то же время кадр RTS, посланный узлом D, получает и узел E, который, ложно предполагая, что за этим последует сеанс передачи данных от узла D к узлу С, блокируется. Однако это ложная блокировка, поскольку реально между узлами D и C передачи нет. Более того, если узел F попытается передать данные ложно заблокированному узлу E и пошлет свой кадр RTS, то он ложно заблокирует узел G.

Рис. 5. Возникновение ложных блокировок узлов сети

Описанное явление ложной блокировки узлов может приводить к кратковременному ступору всей сети.

Функция централизованной координации PCF

ассмотренный выше механизм распределенной координации DCF является базовым для протоколов 802.11 и может использоваться как в беспроводных сетях, функционирующих в режиме Ad-Hoc, так и в сетях, функционирующих в режиме Infrastructure, то есть в сетях, инфраструктура которых включает точку доступа (Access Point, AP).

Однако для сетей в режиме Infrastructure более естественным является несколько иной механизм регламентирования коллективного доступа, известный как функция централизованной координации (Point Coordination Function, PCF). Отметим, что механизм PCF является опциональным и применяется только в сетях с точкой доступа.

В случае задействования механизма PCF один из узлов сети (точка доступа) является центральным и называется центром координации (Point Coordinator, PC). На центр координации возлагается задача управления коллективным доступом всех остальных узлов сети к среде передачи данных на основе определенного алгоритма опроса или исходя из приоритетов узлов сети. Таким образом, координации опрашивает все узлы сети, внесенные в его список, и на основании этого опроса организует передачу данных между всеми узлами сети. Важно отметить, что такой подход полностью исключает конкурирующий доступ к среде (как в случае механизма DCF) и делает невозможным возникновение коллизий, а для времезависимых приложений гарантирует приоритетный доступ к среде. Таким образом, PCF может использоваться для организации приоритетного доступа к среде передачи данных.

Функция централизованной координации не отрицает функцию распределенной координации, а скорее дополняет ее, накладываясь поверх нее. Фактически в сетях с механизмом PCF реализуется как механизм PCF, так и традиционный механизм DCF. В течение определенного промежутка времени реализуется механизм PCF, затем — DCF, а потом все повторяется заново.

Для того чтобы иметь возможность чередовать режимы PCF и DCF, необходимо, чтобы точка доступа, выполняющая функции центра координации и реализующая режим PCF, имела приоритетный доступ к среде передачи данных. Это можно сделать, если использовать конкурентный доступ к среде передачи данных (как и в методе DCF), но для центра координации разрешить использовать промежуток ожидания, меньший DIFS. В этом случае если центр координации пытается получить доступ к среде, то он ожидает (как и все остальные узлы сети) окончания текущей передачи и, поскольку для него определяется минимальный режим ожидания после обнаружения «тишины» в эфире, первым получает доступ к среде. Промежуток ожидания, определяемый для центра координации, называется PIFS (PCF PCF Interframe Space), причем SIFS<PIFS<DIFS.

Режимы DCF и PCF объединяются в так называемом суперфрейме, который образуется из PCF-промежутка бесконкурентного доступа к среде, называемого CFP (Contention-Free Period), и следующего за ним DCF-промежутка CP (Contention Period) конкурентного доступа к среде (рис. 6). Длительность CP-промежутка должна быть достаточной для того, чтобы обеспечить возможность передать хотя бы один кадр с использованием DCF-механизма.

Рис. 6. Объединение режимов PCF и DCF в одном суперфрейме

Суперфрейм начинается с кадра-маячка (Beacon), получив который все узлы сети приостанавливают попытки передавать данные на время, определяемое периодом CFP. Кадры-маячки несут служебную информацию о продолжительности CFP-промежутка и позволяют синхронизировать работу всех узлов сети.

Во время режима PCF точка доступа опрашивает все узлы сети о кадрах, которые стоят в очереди на передачу, посылая им служебные кадры CF_POLL.

Опрашиваемые узлы в ответ на получение кадров CF_POLL посылают подтверждение СF_ACK. Если подтверждения не получено, то точка доступа переходит к опросу следующего узла.

Кроме того, чтобы иметь возможность организовать передачу данных между всеми узлами сети, точка доступа может передавать кадр данных (DATA) и совмещать кадр опроса с передачей данных (кадр DATA+CF_POLL). Аналогично узлы сети могут совмещать кадры подтверждения с передачей данных DATA+CF_ACK (рис. 7).

Рис. 7. Организация передачи данных между узлами сети в режиме PCF

Допускаются следующие типы кадров во время режима PCF:

• DATA — кадр данных;

• CF_ACK — кадр подтверждения;

• CF_POLL — кадр опроса;

• DATA+CF_ACK — комбинированный кадр данных и подтверждения;

• DATA+CF_POLL — комбинированный кадр данных и опроса;

• DATA+CF_ACK+CF_POLL — комбинированный кадр данных, подтверждения и опроса;

• CF_ACK+CF_POLL — комбинированный кадр подтверждения и опроса.

Расширенная функция распределенной координации EDCF

ак уже отмечалось при рассмотрении функции распределенной координации DCF, благодаря конкурентному механизму получения доступа к среде передачи данных, все узлы сети являются равноправными, то есть ни один из узлов сети не имеет приоритета перед другими узлами по передача данных. Именно невозможность осуществления приоритетного доступа ограничивает использование DCF для обеспечения качества обслуживания (Quality of Service, QoS).

Для того чтобы реализовать качество обслуживания QoS, в протоколе 802.11e, в котором рассматривается MAC-уровень беспроводных сетей, предусматривается расширение функции распределенной координации (Enhanced DCF, EDCF).

Механизм EDCF подобен механизму DCF, однако для того, чтобы гарантировать приоритетный доступ различного типа приложениям к среде передачи данных, вводятся некоторые изменения, касающиеся размера CW-окна и промежутка ожидания.

В случае реализации механизма EDCF рассматриваются различные категории трафика (Traffic Categories, TC), которые отличаются друг от друга степенью приоритета относительно доступа к среде передачи данных. При этом сам механизм доступа к среде остается таким же, как и в случае DCF, то есть основанным на конкуренции.

Каждый узел сети, убедившись, что среда свободна, прежде чем начать передачу, выжидает в течение промежутка времени AIFS (Arbitration Interframe Space), после чего приступает к процедуре обратного отсчета. Длительность промежутка обратного отсчета определяется как случайное целое число тайм-слотов из диапазона [1, CW(TC)+1], где CW(TC) — размер окна для трафика заданной категории.

Различный приоритет трафиков разных категорий обеспечивается за счет использования различных значений минимального и максимального размеров CW-окна и AIFS-промежутков. Так, минимальный размер AIFS-промежутка всегда равен длительности DIFS-промежутка, но может быть увеличен в зависимости от приоритета трафика.

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

newCW=2•oldCW-1.

Для механизма EDCF размер нового CW-окна рассчитывается по следующему правилу:

newCW[TC] = ((oldCW[TC]+1)•PF[TC])-1,

где PF — это постоянная масштабирования окна, значение которой зависит от категории трафика. В случае DCF можно считать, что PF=2.

Таким образом, приоритезация трафика различных категорий задается в методе EDCF за счет вариации следующих значений: CWmin, CWmax, AIFS, PF.

Принцип реализации механизма EDCF показан на рис. 8.

Рис. 8. Приоритезация различных категорий трафика в EDCF

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

Рис. 9. Использование планировщика во избежание виртуальных коллизий

Гибридная функция координации HCF

роме расширенной функции распределенной координации EDCF в протоколе MAC-уровня 802.11e предусмотрен альтернативный режим гибридной функции координации (Hybrid Coordination Function, HCF). Аналогично тому, как EDCF является развитием механизма DCF, HCF является развитием централизованной функции координации PCF. И если PCF реализовывался поверх DCF, то HCF реализуется поверх EDCF.

В случае HCF точка доступа является центром координации (HC) и управляет коллективным доступом всех узлов сети к среде передачи данных, для чего опрашивает все узлы сети, внесенные в ее список, и на основании этого опроса организует передачу данных между всеми узлами сети.

В сетях с механизмом HCF в течение определенного промежутка времени CFP реализуется механизм бесконкурентного доступа, когда доступ к среде контролируется точкой доступа, затем следует промежуток конкурентного доступа CP с механизмом EDCF. Чередующиеся режимы бесконкурентного и конкурентного доступа образуют суперфрейм.

Для того чтобы иметь возможность чередовать режимы HCF и ЕDCF, необходимо, чтобы точка доступа имела бы самый высокий приоритет по доступу к среде передачи данных. Для этого используется тот же прием, что и в случае PCF: промежуток ожидания для точки доступа (PIFS) меньше, чем для всех остальных узлов сети (PIFS<DIFS<AIFS). Это позволяет точке доступа агрессивно захватывать среду передачи данных.

В отличие от рассмотренного выше метода EDCF, в период конкурентного доступа CP на основе механизма EDCF точка доступа также может получать внеочередной доступ к среде, образуя так называемые периоды CAP (Controlled Access Periods) (рис. 10). Эти промежутки используются точкой доступа для опроса узлов сети, а промежутки CFP используются его для инициирования обмена данными между узлами сети, а также для опроса узлов сети. Такой механизм более эффективно обеспечивает качество обслуживания (QoS) и гарантирует времезависимым приложениям своевременный доступ к среде передачи данных.

Рис. 10. Реализация механизма HCF

Для опроса узлов сети используются служебные кадры QoS CF_POLL, а узлы отвечают на запросы кадрами подтверждениями QoS CF_ACK.

Кроме того, точка доступа может передавать кадры данных (QoS DATA), комбинированные кадры опроса и данных (QoS DATA+CF_POLL), комбинированные кадры опроса и подтверждения (QoS CF_ACK+CF_POLL) и комбинированные кадры опроса, подтверждения и данных (QoS DATA+CF_ACK+CF_POLL). Аналогично и узлы сети могут помимо кадров данных совмещать кадры подтверждения с передачей данных (DATA+CF_ACK).

КомпьютерПресс 5'2004