Модели оценки производительности

многофункциональных систем обмена

трафиком на примере беспроводных сетей доступа

 Wi-Fi, Wireless MAN и WiMAX

В.Л. Широков

(Москва)

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

Для подключения вычислительных средств используют стандартные интерфейсы и технологии доступа к беспроводной передающей среде.  Для связи в беспроводных распределенных локальных, городских и региональных сетях, как правило, используются технологии радио Ethernet (Wi-Fi) и DOCSIS+wireless (WiMAX) [1-2].  Предпринимались и предпринимаются многочисленные попытки реализации интерфейсов связи, обеспечивающих формально высокие скорости обмена данными между вычислительными узлами.  Эти решения в основном сводятся к повышению тактовой частоты и скорости работы интерфейсов. 

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

Как показано в [3-4], наибольшая скорость формального обмена данными может быть обеспечена в мультисистеме, в которой машины взаимодействуют через канал, реализующий идеальную общую память (конфликты и задержки доступа к которой отсутствуют).  На практике реализовать такой канал невозможно.   Там же показано, что лучший результат обеспечивает мультисистема, построенная по принципу общей виртуальной памяти (сокращенно ОВП).  В дальнейшем применительно к мультисистеме целесообразно использовать термин общий виртуальный канал (ОВК).

Поскольку в реальных системах типа радио Ethernet (Wi-Fi) реализуется неидеальный канал, задержками доступа к общему каналу пренебрегать нельзя.  В такой системе производительность снижается уже при двух узлах, взаимодействующих через общий канал, а при нагрузке 5-7 и более узлов радиосистема Wi-Fi становится неработоспособной.  Это объясняется тем, что в Wi-Fi системе реализуется общий неидеальный (с конфликтами доступа) канал (сокращенно ОНК).

Модель типа ОВК хорошо описывает многофункциональную систему обмена трафиком типа DOCSIS+wireless (прототип новой беспроводной технологии WiMAX).

В [3-4] также разработаны формальная, общая аналитическая и программная модели абстрактного интерфейса, работающего по принципу ОВП (ОВК).  Этот интерфейс рассматривался для связи двух микроЭВМ.  В данной статье предлагается и рассматривается сетевая модель ОВК.

Ранее полученные результаты (см.[5]) говорят, что существует зависимость интенсивности λ только от двух ресурсно-временных характеристик L и ρ межмашинного обмена трафиком: 

λ = F(L,ρ), где ρ = Tс/T – временной ресурс транзакции, т.е. времени Тс ее активности за период Т ее существования в узле, L – среднее количество слов (мини-пакетов, кадров) в одной передаче, которое ограничивает и определяет, в конечном счете, объем буфера, необходимого данной транзакции. 

Там же получено точное выражение, что λ = (1 – ρ)/(tO/L + t1)                                     (1), 

где tO, t1 – постоянные, определяемые временными характеристиками реализации межмашинного интерфейса на канальном уровне (tO – по выводу из источника, t1 – по вводу в приемник), L – длина передаваемого пакета.

Из выражения (1) следует, что максимальная скорость передачи, при прочих равных условиях, получается при L = 1, т.е. при передаче отдельными мини-пакетами (кадрами). 

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

Общий анализ характеристик канальных интерфейсов, реализующих обмен, предлагается проводить по следующей методике (см.[4]):

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

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

3)      Для вычисления ресурсно-временных затрат подсчитать количество программно- аппаратных тактов, или обращений к каналу и количество ячеек памяти, необходимых при обмене данными, используя выражения, приведенные в [4].

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

5)      Вычислить фактически достижимую (максимальную) интенсивность межмашинного асинхронного обмена по формуле (1) для ее проверки в разных режимах ввода-вывода.

6)      Сравнить полученные значения с эталоном или с имеющимися паспортными характеристиками интерфейса (канала передачи данных).

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

1)      hik – время, требующееся i-му узлу для подготовки k-го кадра.  Усредненно hik не должно сильно различаться в зависимости от k; поэтому в модели принято, что конечное ненулевое время hik = hi для любого k = 1, 2, …, N;

2)      узлы передают выходные данные в произвольном порядке, не зависящем от k.  Поэтому, без ограничения общности, можно считать, что передача происходит упорядченно, т.е. 1, 2, …, N;

3)      общая интенсивность λ обмена данными определяется как

                                                                                                    K

      (T передач по интерфейсу) / (T подготовки кадра)  =  ∑ (to + τi + t1)/hi

                                                                                                    i=1

4)      полный цикл передачи одного кадра требует некоторого целого количества системных тактов:  t = to + τi + t1.  При этом первый такт to всегда является тактом запроса, а все последующие: τi и t1 – тактами передачи по интерфейсу и тактами ввода данных в память приемника.  Причем средний период «опроса» (сканирования) всех интерфейсов составляет K/2 тактов, где K – количество вычислительных элементов (соответственно и сетевых контроллеров) в системе:

                   tm – при передаче данных по умолчанию,

      t1  =      2tm – при передаче данных с флагом (уведомлением),

                   tm + tin – при передаче данных с прерыванием,

      где tm – время доступа к приемнику, tin – время обслуживания прерывания.

5)      вероятность Q того, что некоторый интерфейс IS источника не запрашивает обмен с одним из приемников, составляет:

      Q  =  (1 – λ1)*t/((1 – λ1)*t + λ1),

      где  λ1 = λ/(K – 1)   – интенсивность (вероятность) обращения к одному из остальных K–1 приемников.

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

У т в е р ж д е н и е.   Временные характеристики  Yt  обмена данными в системе: производительность P и задержка τ, – являются функциями только трех переменных λ, K и M, т.е. Yt = U (λ,K,M), где M – программно-аппаратная характеристика интерфейса.

Доказательство. Пусть рассматриваемая модель характеризуется следующими параметрами:

-         количеством тактов M, которое требуется на выполнение передачи, при количестве l (эль малое) одновременных запросов к одному приемнику, причем

M = K/2 + M1,   где   Ml = to + t1;

-         задержкой τ  вычислений (обработки данных) в системе, причем

τ  =  (t параллельных вычислений в системе)/(t параллельных вычислений без задержки) – 1;                                      (2)

-         производительностью P системы

P  =  (t последовательных вычислений)/(t параллельных вычислений в системе).                                                     (3)

Поскольку время последовательных вычислений пропорционально K, а числитель (2) равен знаменателю (3), то путем преобразований можно показать, что

P  =  K/(τ + 1).                                                                                                                        (4)

Доказательство (4).  Уменьшение производительности системы является результатом задержки передаваемых данных, поэтому

P  =  K2 /(K + Kτ),                                                                                                                   (5)

где Kτ – среднее число рабочих элементов (процессоров), у которых передача испытала задержку.

Кроме того, очевидно, что

τ = (K + Kτ)/K – 1 = Kτ/K,                                                                                                     (6)

После исключения Kτ получится искомое выражение (4).

Из (4) можно сделать вывод, что производительность Р фактически зависит только от временной задержки τ.

Далее продолжим построение модели ОВП.

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

Для определения значения Kτ определим Ta – среднюю продолжительность активных периодов, когда один или более источников посылают данные через канал одному приемнику и Tz – пассивных, когда запросы отсутствуют.

Так как процессоры системы могут находиться только в одном из двух состояний, то производительность системы

P = Ta/λl(Ta + Tz).                                                                                                                    (7)

С учетом (4) имеем

τ  =  K/Р – 1 = λl(K – 1)*(Ta + Tz)/Ta – 1.                                                                               (8)

Поскольку источники независимы, то вероятность того, что при обращении к одному приемнику текущий и следующий такты свободны (период пассивен), равна QK-1.

Если Р(n) – вероятность пассивного состояния источников в последующие не менее  n  тактов, то вероятность того, что по крайней мере  n+1  тактов свободны, равна произведению

Р(n)*Р(n+1-й такт свободен), что дает:

Р(n+1) = Q*Р(n), а так как Р(0) = 1, то Р(n) = (QK-1)n.

Отсюда находится вероятность Р(=n), что ровно n тактов свободны:

Р(=n) = Р(n)*Р(n+1-й такт занят) = (QK-1)n*(1 – QK-1).

Таким образом, время пассивного состояния, т.е. время обработки данных (“обдумывания” информации, тайм-аута) в каждом источнике, составит

Тz = (QK-1) / (1 – QK-1).                                                                                                           (9)

Это геометрическое распределение с параметром, равным Тz.

Активный период (обмен данными) начинается в такте, в котором какой-либо источник посылает кадр в сетевой интерфейс.

В этом такте послать запрос к одному приемнику могут одновременно до К-1 источников.  Поэтому время Та активного периода может быть найдено как

               K-1

Tа   =   ∑  Pl * Tl,                                                                                                                  (10)

                         l=1

где Pl – вероятность того, что в активный период поступило l запросов к одному приемнику, Tl – средняя продолжительность активного периода, начавшегося l одновременными запросами, причем

Pl = P(l источников из K-1 послали запросы)*P(1 источник послал запрос), или

Pl = СlK-l*QK-l-1*(1 - Ql) / (1 - QK-1).                                                                                     (11)

Средняя продолжительность активного периода (время обмена):

                   K-l-1

Tl   =   t  +  ∑   Ckk-l-1 *(Qt-1)K-l-k-1 *(1 – Qt-1)*tkK-1,l+k-1 * Pl * Tl,                                               (12)

                               k=0

Для определения  Tl  требуется вычислять  tK-1,j   –  среднее  число тактов до конца активного периода, если имеется K рабочих элементов в системе и j источников послали запрос на передачу в один приемник.

Можно показать, что

tK-1,j    =   tK-1,1   +   tK-2,1  +  …  +  tK-j,1, причем

tK-1,1   =  t *    1 + С1K-2(q-t – 1) +  + С2K-2(q-t – 1) (q-2t – 1)  +  …

                            … + СK-2K-2(q-t – 1)*(q-2t – 1)  …   (q-(K-2)t – 1)    .                                                   (13)

Таким образом, очевидно, что условия утверждения выполняются, поскольку все временные характеристики системы зависят только от λ, K и М.

Что и требовалось доказать.

Далее, возможны два режима функционирования сетевой магистрали системы:

1)      Сетевая магистраль недогружена, т.е.  существуют интервалы времени, в течение которых она свободна.  В этом режиме справедливы неравенства

         hi   -  ∑ τj  >  0     для некоторого   i Є {1, 2,  … , K},

      j≠i

         hm   - ∑ τj  >  0,   где hm + τm  = maxi (hi + τi),   i = 1, 2,  … , K;

      j≠i

2)      Сетевая магистраль загружена, т.е. постоянно занята.  В этом режиме справедливы обратные неравенства

         hi   -  ∑ τj  ≤  0     для всех   i Є {1, 2,  … , K},

      j≠i

         hm   - ∑ τj  ≤  0,   где hm + τm  = maxi (hi + τi),   i = 1, 2,  … , K.

      j≠i

Тогда максимальный период функционирования магистрали системы может составить не более

             τm   =  maxi τi   =   tK,K-1  =  (K – 1)*t1

Следовательно, время вычисления отдельных параметров, подготовки кадров в системе, ограничивается неравенством вида

             hi  ≥  (K – 1)*t1    для любого    i = 1, 2,  …  , K.

Общая магистраль системы простаивает после обработки данных i-тым процессором, если существует интервал времени bi, который находится посредством уравнения

             di = hi  –  ∑ τj  –  ∑ bj ≤  0     при условии, что

                            j≠i               j≠i

bi =
 
                         0,   если   di  ≤  0,    i = 1, 2, … , K,

                         di,   если   di  >  0,    i = 1, 2, … , K,

hi = ti + to + t1,

где   ti,  to,  t1   –   время обработки, вывода и ввода данных, которые были определены выше.

Качественный анализ полученных выражений показывает, что в случае ОВП суммарная интенсивность обмена данными с разными приемниками уменьшается обратно пропорционально числу  К  рабочих элементов в системе.

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

Использование выражений (1)-(13) для вычисления системных характеристик является достаточно скрупулезной и трудоемкой задачей.  Однако эти вычисления могут быть выполнены на компьютере.

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

В заключение необходимо отметить, что в настоящее время существует и используется множество реализаций беспроводных городских сетей доступа Wireless MAN.  Однако большинство из них происходит от Wi-Fi, поэтому имеет определенные ограничения в применении, а именно:  они относятся к Wireless LAN и не могут считаться прототипом нового беспроводного городского стандарта WiMAX.

ВЫВОДЫ.

1.  Использовать сеть стандарта Wi-Fi в качестве городской многофункциональной сети Wireless MAN практически невозможно.  Сеть Wi-Fi воспроизводит неидеальную модель по принципу ОМП, поэтому она имеет существенные ограничения как на реально достижимую скорость обмена данными, так и на емкость сети (нагрузочные возможности отдельного сектора, или соты).  В условиях, когда требуется поддерживать высокую интенсивность обмена между узлами, производительность сети Wi-Fi резко падает, особенно с увеличением количества узлов и предоставляемых сервисных услуг.

2.  Действительным прототипом нового беспроводного стандарта WiMAX, как многофункциональной Wireless MAN является модель ОВП, моделирующая канальный и сетевой уровни технологии DOCSIS+wireless (см. [1-2]).  Технология DOCSIS+wireless положена в основу нового стандарта WiMAX.  В настоящее время она используется для создания открытых систем, отличающихся от WiMAX только на физическом уровне.

3.  Использование специально разработанных расчетных программ, применяемых при проектировании, системной интеграции оборудования, верификации и оптимизации структуры систем, позволяет подтвердить адекватность моделей и выводы 1-2.  Эти программы применяются при разработке реальных систем Wireless MAN, использующих DOCSIS+wireless,  и могут быть применимы в дальнейшем при разработке систем WiMAX.

4. Предложенные модели и программы используются для расчета параметров производительности городских (региональных) Wireless MAN по технологии DOCSIS+wireless на практике.  Расчетные значения подтверждают правильность результатов, получаемых на реально работающих системах.

Литература:

[1] – В.Л.Широков, В.А.Ярошенко: «Городские широкополосные беспроводные сети. Радиотехнология DOCSIS+ как прообраз Wireless MAN», «ТЕЛЕВИДЕНИЕ И РАДИОВЕЩАНИЕ “BROADCASTING”», № 3 (39), 2004 г., с.10-11.

[2] – В.Л.Широков, В.А.Ярошенко: »Мультисервисная беспроводная городская сеть доступа Wireless MAN», «ТЕЛЕВИДЕНИЕ И РАДИОВЕЩАНИЕ “BROADCASTING”», № 6 (42), 2004 г., с.10-11.

[3] – В.Л.Широков, Ю.М.Лысяков: "Временные задержки в сети микроЭВМ с шиной Q-bus // Локальные вычислительные сети: опыт реализации и перспективы развития. Тез. докл. Всесоюз. науч. семинара, Иваново, 13-16 мая 1986 г. – М.: МЦНТИ, 1986. – С. 84-86.

[4] – В.Л.Широков, Ю.М.Лысяков: "Исследование межзадачного обмена в локальных сетях", научно-технический отчет № 982-87-IX, номер ГР X 74524, п/я В-8759, 1987, 104 с.

[5] – В.Л.Широков: «Межмашинный интерфейс микроЭВМ с предельными временными характеристиками», «Управляющие системы и машины», 1989, с. 29-33.

[6] – Абросимов Л.И. Анализ и проектирование вычислительных сетей. М.: МЭИ, 2000, 52 с.