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

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

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

 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 – ρ)/(t_O/L + t₁)                                     (1), 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

                                                                                                    K

      (T _{передач по интерфейсу}) / (T _{подготовки кадра})  =  ∑ (t_o + τ_i + t₁)/h_i

                                                                                                    ⁱ⁼¹

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

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

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

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

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

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

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

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

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

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

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

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

M = K/2 + M₁,   где   M_l = t_o + t₁;

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

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

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

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

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

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

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

P  =  K² /(K + K_τ),                                                                                                                   (5)

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

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

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

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

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

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

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

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

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

P = T_a/λ_l(T_a + T_z).                                                                                                                    (7)

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

τ  =  K/Р – 1 = λ_l(K – 1)_*(T_a + T_z)/T_a – 1.                                                                               (8)

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

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

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

Р(n+1) = Q_*Р(n), а так как Р(0) = 1, то Р(n) = (Q^K-1)ⁿ.

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

Р(=n) = Р(n)_*Р(n+1-й такт занят) = (Q^K-1)ⁿ_*(1 – Q^K-1).

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

Т_z = (Q^K-1) / (1 – Q^K-1).                                                                                                           (9)

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

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

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

               K-1

T_а   =   ∑  P_{l *} T_l,                                                                                                                  (10)

                         ^l=1

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

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

P_l = С^l_K-l*Q^K-l-1_*(1 - Q^l) / (1 - Q^K-1).                                                                                     (11)

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

                   K-l-1

T_l   =   t  +  ∑   C^k_{k-l-1 *}(Q^t-1)^K-l-k-1 _*(1 – Q^t-1)_*t^k_{K-1,l+k-1 *} P_{l *} T_l,                                               (12)

                               ^k=0

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

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

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

t_K-1,1   =  t _*    1 + С¹_K-2(q^-t – 1) +  + С²_K-2(q^-t – 1) (q^-2t – 1)  +  …

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

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

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

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

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

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

      ^j≠i

         h_m   - ∑ τ_j  >  0,   где h_m + τ_m  = max_i (h_i + τ_i),   i = 1, 2,  … , K;

      ^j≠i

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

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

      ^j≠i

         h_m   - ∑ τ_j  ≤  0,   где h_m + τ_m  = max_i (h_i + τ_i),   i = 1, 2,  … , K.

      ^j≠i

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

             τ_m   =  max_i τ_i   =   t_K,K-1  =  (K – 1)_*t₁

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

             h_i  ≥  (K – 1)_*t₁    для любого    i = 1, 2,  …  , K.

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

             d_i = h_i  –  ∑ τ_j  –  ∑ b_j ≤  0     при условии, что

                            ^{j≠i               j≠i}

bi =

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

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

h_i = t_i + t_o + t₁,

где   t_i,  t_o,  t₁   –   время обработки, вывода и ввода данных, которые были определены выше.

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

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

Использование выражений (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 с.