На правах рукописи

Михеев Павел Андреевич

РАЗРАБОТКА И ИССЛЕДОВАНИЕ

МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ

АГРЕГИРОВАНИЯ И РАСЩЕПЛЕНИЯ ТРАФИКА

ЗВЕЗДООБРАЗНОГО ФРАГМЕНТА СЕТИ

Специальность 05.13.11 Математическое и программное обеспечение

вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Томск 2011

Работа выполнена на факультете информатики Федерального государственного бюджетного образовательного учреждения высшего профессионального образования Национальный исследовательский Томский государственный университет

Научный руководитель: доктор технических наук, профессор Сущенко Сергей Петрович

Официальные оппоненты: доктор технических наук, профессор Назаров Анатолий Андреевич (Томский государственный университет) кандидат технических наук, доцент Замятин Александр Владимирович (Томский политехнический университет)

Ведущая организация: Сибирский государственный университет телекоммуникаций и информатики (г. Новосибирск)

Защита состоится 26 января 2012 г. в 10.30 на заседании диссертационного совета Д 212.267.08 при Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования Национальный исследовательский Томский государственный университет по адресу: 634050, г. Томск, пр. Ленина, 36, корп. 2, ауд. 102.

Отзывы на автореферат (в двух экземплярах), заверенные гербовой печатью организации, просим направлять по адресу: 634050, г. Томск, пр. Ленина, 36, ученому секретарю ТГУ Буровой Н. Ю.

С диссертацией можно ознакомиться в Научной библиотеке Томского государственного университета.

Автореферат разослан 16 декабря 2011 г.

Ученый секретарь диссертационного совета Д 212.267. доктор технических наук, профессор А. В. Скворцов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Для описания процессов информационного переноса и анализа различных характеристик в сетях передачи данных используются методы теории вероятностей, теории массового обслуживания, теории Марковских цепей, а также методы имитационного моделирования. Значительный вклад в развитие данной области внесли зарубежные и российские ученые: L. Kleynrock, F. Baccelli, G. Bianchi, J. Jangeun, D. Towsley Г. П. Башарин, П. П. Бочаров, В. М. Вишневский, А. И. Ляхов, А. А. Назаров, С. П. Сущенко, К. Е. Самуйлов и некоторые другие.

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

Звездообразный фрагмент является важнейшим структурным элементом сети. Моделирование звездообразной конфигурации обычно выполняется многолинейной системой массового обслуживания с независимыми простейшими потоками и экспоненциальными длительностями обслуживания (L. Kleynrock, F. Baccelli, Г. П. Башарин). Однолинейная система массового обслуживания с дискретным временем и конечным накопителем рассматривалась группой исследователей во главе с Г. П. Башариным и П. П. Бочаровым.

Беспроводные сети, в основе которых лежит случайный множественный доступ с контролем несущей и предотвращением коллизий в ранних работах изучались экспериментально и путем упрощенного моделирования. Впервые аналитический метод оценки пропускной способности беспроводной локальной сети стандарта 802.11 в условиях высокой нагрузки предложен итальянским ученым Джузеппе Бьянки. Существенный вклад в развитие математических моделей беспроводных сетей стандарта 802. принадлежит группе российских ученых во главе с В. М. Вишневским и А. И. Ляховым. Тем не менее существующие модели не учитывают эффект захвата среды передачи данных и ситуации с конфликтами с участием более двух соперников.

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

';

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

Для достижения намеченной цели поставлены и решены следующие задачи:

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

2. Разработка модели агрегирования трафика с возможностью совместного учета совокупности параметров сетевого фрагмента.

3. Разработка модели случайного множественного доступа с контролем несущей и предотвращением коллизий.

4. Разработка методики расчета технических параметров сетей уровня 5. Разработка программного комплекса для расчета операционных характеристик звездообразного фрагмента сети.

Научная новизна работы состоит в следующем:

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

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

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

Положения выносимые на защиту:

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

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

3. Аналитическая вероятностно-временная модель процесса соперничества двух станций беспроводной локальной сети.

4. Имитационная модель процесса соперничества абонентов беспроводной локальной сети.

5. Методика расчета технических параметров сетей уровня доступа.

6. Программный комплекс для расчета операционных характеристик звездообразного фрагмента сети.

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

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

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

Внедрение результатов работы. Результаты исследований, выполненные численные расчеты, разработанный программный комплекс для расчета операционных характеристик звездообразного фрагмента сети и методика расчета технических параметров сетей уровня доступа внедрены в ООО Интант и используются для обоснования выбора технических параметров реализуемых сетевых проектов. Разработанные модели агрегирования и расщепления сетевого трафика и модель соперничества абонентов беспроводной сети WiFi используются в ООО Ф5 Нетворкс для расчета размеров буферной памяти проектируемых коммуникационных устройств с заданной производительностью и формирования предложений по управлению качеством обслуживания абонентов беспроводной сети. Кроме того, материалы исследований легли в основу раздела Модели подсетей абонентского доступа в магистральные сети курса Математические модели компьютерных сетей и используются при чтении лекций для магистрантов направления 010300 Фундаментальная информатика и информационные технологии и курса лекций Компьютерные сети для слушателей региональной сетевой академии Cisco при ТГУ, обучающихся по программе CCNP.

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на следующих научно-практических конференциях: IX Всероссийский симпозиум по прикладной и промышленной математике (весенняя сессия, Кисловодск, 2008); VII–X Всероссийские научно-практические конференции с международным участием Информационные технологии и математическое моделирование (АнджероСудженск, 2008–2011); X Всероссийский симпозиум по прикладной и промышленной математике (весенняя сессия, Санкт-Петербург, 2009); Международная научная конференция Современные вероятностные методы анализа и оптимизации информационно-телекоммуникационных сетей (21-я Белорусская школа-семинар по теории массового обслуживания BWWQT-2011) (Минск, 2011); XLII Международная научная конференция аспирантов и студентов Процессы управления и устойчивость (Санкт-Петербург, 2011); Международная научно-практическая конференция Актуальные проблемы науки (Тамбов, 2011); VII Международная научно-практическая конференция Dynamika naukowych badan 2011 (Przemysl, 2011); Международная конференция Современные проблемы математики, информатики и биоинформатики, посвященная 100-летию со дня рождения члена-корреспондента АН СССР Алексея Андреевича Ляпунова (Новосибирск, 2011); Российская научная конференция с участием зарубежных исследователей Моделирование систем информатики (Новосибирск, 2011).

Публикации. По результатам выполненных исследований опубликовано 15 печатных работ, в том числе 4 статьи в журналах, рекомендованных ВАК РФ.

Личный вклад. Основные научные результаты получены автором самостоятельно. Постановка задачи выполнена автором совместно с научным руководителем. Численные расчеты выполнялись автором самостоятельно и программа имитационного моделирования разработаны автором единолично.

Структура и объем работы. Работа состоит из введения, четырех глав, заключения и списка литературы из 153 наименований. Общий объем диссертации составляет 166 страниц, в том числе основной текст страниц.

СОДЕРЖАНИЕ РАБОТЫ

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

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

Во второй главе предложена модель звездообразного фрагмента сети с расщеплением входящего трафика по M исходящим направлениям.

Предполагается, что в узле-отправителе входящего канала всегда имеются пакеты для передачи в центральный транзитный узел. Обмен в каждом звене выполняется полными кадрами и организован в соответствии со стартстопным протоколом, согласно которому кадр считается принятым узлом-приемником, если в нем не обнаружены ошибки. При искажении информационного кадра или квитанции, подтверждающей правильность приема кадра получателем, происходит повторная передача. Входному каналу связи выделен специальный буфер для приема кадра и анализа его на наличие ошибок. В случае корректного приема кадра, содержащийся в нем пакет переписывается в свободный буфер буферного пула выходного канала связи, а в качестве специального выделяется другой из того же буферного пула. При отсутствии свободных буферов в пуле выходного канала связи прием полученного кадра не подтверждается, кадр сбрасывается и передается повторно. Полагаем, что все каналы связи имеют одинаковые физические скорости передачи данных, а узлыотправители и узлы-получатели одинаковое время обработки кадров при приеме и отправке. Тогда время полного цикла передачи кадра t будет одинаковым для всех звеньев рассматриваемого фрагмента. Кроме того, считается, что кадр, поступивший в транзитный узел в текущем цикле t, начнет передаваться по выходному каналу только в следующем цикле. Безошибочная передача кадра данных во входящем канале определяется вероятностью F, а в исходящих каналах вероятностями Fm, m = 1, M. Считаем также, что весь входящий в транзитный узел поток кадров одного канала распределяется в m-й выходной канал с вероятностью Bm, m=1 Bm = 1.

Для хранения пакетов в выходных очередях в транзитном узле выделен пул совместно используемой буферной памяти объема K. Размер очереди qm к каждому выходному каналу m ограничен предельной величиной Nm K, определяемой стратегией распределения буферной памяти между выходными каналами. Для каждого входящего пакета, направляемого в конкретный исходящий канал, выделяется буфер при условии, что выходная очередь qm данного направления не превышает максимального размера qm < Nm и, кроме того, для очередей к выходным каналам связи выполняется ограничение m=1 qm < K, соответствующее тому, что пул свободных буферов для хранения пакетов данных не пуст. Очевидно, что в каждом конкретном случае распределения пула буферов между выходными направлениями размер очереди к m-му каналу qm не превышает величины Qm, удовлетворяющей В общем случае различают три стратегии распределения буферной памяти между выходными каналами связи: равнодоступную (Nm = K), политику фиксированного разбиения (Nm = K/M для однородных выходных каналов связи) и промежуточную стратегию (K/M < Nm < K, m=1 Qm = K).

Поведение рассматриваемого сетевого фрагмента представимо в виде Марковской системы массового обслуживания (СМО) с дискретным временем, конечным накопителем и M обслуживающими приборами.

Входящий поток определяется качеством входящего канала F, а время обслуживания на каждом приборе СМО качеством m-го исходящего канала Fm. Распределение поступающих заявок СМО по M обслуживающим приборам задается вероятностями Bm, m = 1, M. Динамика очередей к выходным каналам связи данной СМО в стационарных условиях описывается цепью Маркова в M -мерном пространстве. Множество возможных состояний цепи Маркова по каждому измерению определяется политикой распределения буферной памяти между исходящими каналами и не превышает величины Nm + 1.

Для дискретной цепи Маркова с конечным числом состояний, описывающей рассматриваемую СМО в установившемся режиме, определим с учетом введенных предположений переходные вероятности I из состояния I в состояние J. Здесь I и J M -разрядные номера соответственно исходного и измененного состояний с областью значений каждого Вероятности состояний M -мерной цепи Маркова обозначены через Pi1,i2,...,iM, im = 0, Qm, m = 1, M. Очевидно, что запись Pi1,i2,...,iM эквивалентна записи PI. Важнейшей характеристикой СМО ограниченной емкости является пропускная способность. В рассматриваемом случае этот показатель интерпретируется как пропускная способность входящего звена передачи данных, нормированное значение которого определяется величиной пропущенного (обслуженного) потока:

где F = {F1,..., FM } вектор значений надежностей выходящих каналов Fm, m = 1, M, который в случае однородности всех выходящих направлений будем обозначать просто F, а B = {B1,..., BM } вектор значений вероятностей направления трафика в m-й канал Bm, m = 1, M.

Далее рассматривается поведение сетевого фрагмента при различных стратегиях разделения буферной памяти объема K между M выходными направлениями.

Для единичного буфера K = 1 и произвольного количества исходящих каналов (M 1) выражение (1) принимает вид:

Из соотношения (2) очевидно, что при абсолютно надежных каналах всех исходящих звеньев сетевого фрагмента (Fm = 1, m = 1, M ) пропущенный поток определяется достоверностью передачи данных во входящем канале связи: Z(M, 1, F, 1, B) = F. Для статистически однородных каналов связи всего сетевого фрагмента (Fm = F, m = 1, M ) выражение для пропускной способности звена передачи данных инвариантно к количеству выходных звеньев передачи данных и распределению по ним исходящего трафика: Z(M, 1, F, F, B) = F/(2 F ). В случае, когда все исходящие каналы имеют одинаковый уровень достоверности передачи данных (Fm = F, m = 1, M, F = F ) пропущенный поток инвариантен к тому, как расщепляется сетевой трафик в транзитном узле:

Для случая с двумя выходящими каналами (M = 2), поскольку B = {B1, 1 B1 }, функцию пропускной способности можно записать следующим соотношением: Z(2, K, F, F, B1 ).

Для равнодоступной стратегии разделения буферной памяти емкостью K = 2 (Nm = 2) при статистически однородном сетевом фрагменте (F = F1 = F2 ) пропускная способность входящего звена передачи данных остается зависимой от структуры расщепления трафика (Bm, m = 1, 2):

Z(2, 2, F, F, B1 ) = Нетрудно убедиться в том, что максимальный пропущенный поток в этом случае достигается при равномерном расщеплении трафика B1 = 1/2:

Рис. 1. Сравнительные кривые пропущенного потока от структуры расщепления трафика при различных объемах буферной памяти для равнодоступной (Zр ) и стратегии фиксированного разбиения (Zф ) Полагая, что весь входящий трафик направляется в один выходной канал (B1 = 1), получаем известную зависимость:

Для стратегии фиксированного разбиения буфера емкостью K = (Nm = 1) удалось найти оптимальное расщепление трафика между двумя выходными направлениями, максимизирующее объем пропущенного потока для произвольных F, Fm, m = 1, 2: B1 = F1 (1F2(1F2(1F1 ).

Кроме аналитических решений для двух исходящих каналов с буфером транзитного узла K = 2, численные решения получены для K = в случае двух исходящих каналов и для K = 3 в случае трех исходящих каналов для различных стратегий распределения буферной памяти.

Полученные результаты свидетельствуют о том, что ни одна из стратегий распределения буферной памяти не обеспечивает абсолютного превосходства над другими по показателю объема пропущенного потока на всей области изменения качества однородных исходящих каналов связи. В интервале F [0, F/M ] стратегия фиксированного разбиения обеспечивает преимущество перед равнодоступной стратегией, а при F [F/M, 1] имеет место обратная картина. Вместе с тем следует отметить, что с ростом объема буферного пула это различие нивелируется.

Кроме того, промежуточная политика на всей области изменения параметров выходных каналов связи Fm, m = 1, M, либо доминирует по индексу пропускной способности над конкурирующими стратегиями, либо незначительно уступает лучшей из них.

Численные исследования также показывают, что объем пропущенного потока в значительной мере определяется структурой распределения трафика по выходным каналам и имеет оптимальный набор параметров расщепления трафика Bm, m = 1, M вне зависимости от стратегии расщепления трафика. Причем, из рис. 1 нетрудно видеть, что при существенно неоднородном качестве выходных каналов связи пропущенный поток имеет ярко выраженный максимум от структуры расщепления (B1 ). Отметим также, что с ростом объема буферной памяти максимум пропущенного потока смещается в область расщепления трафика с увеличивающейся долей потока, направляемого в выходной канал худшего качества. Для однородных по качеству исходящих каналов связи максимум пропущенного потока достигается при равномерном распределении трафика.

В третьей главе рассмотрен фрагмент локальной компьютерной сети, включающий M клиентов, подключенных к серверу через сетевой узел (коммутатор или маршрутизатор). Считаем, что к M однородным по скорости приемо-передачи данных портам транзитного узла подключены абоненты, порождающие поток кадров равной длины к серверной платформе, подсоединенной к узлу через (M + 1)-й порт с быстродействием в S 1 раз превышающем быстродействие абонентских портов.

Полагаем также, что надежность абонентских соединений сетевого узла определяется вероятностями Fm, m = 1, M, а надежность серверного соединения вероятностью F. При этом все клиентские источники данных независимы и работают синхронно с периодом t. Длительность этого периода определяется быстродействием портов для подключения абонентов и накладными расходами, связанными с обработкой кадров в транзитном узле. Тогда за время полного цикла передачи кадра t по абонентским портам в серверный порт может быть отправлено 0 i S кадров.

Будем считать, кроме того, что транзитный узел работает в режиме полной промежуточной буферизации и кадр, поступивший в узел в текущем цикле t, начнет передаваться по выходному (серверному) порту только в следующем цикле. Полагаем, что на абонентских портах информационные кадры возникают в каждый период t с вероятностями Bm, m = 1, M. Предположим также, что для хранения кадров в выходной очереди сетевого узла к серверному порту выделен пул буферной памяти объема K M. Тогда поведение рассматриваемого сетевого фрагмента представимо в виде Марковской системы массового обслуживания (СМО) с дискретным временем, конечным накопителем, неординарным входящим потоком и одним прибором с групповым обслуживанием заявок. Неординарный входящий поток СМО определяется вероятностями появления кадров в абонентских портах Bm, m = 1, M и надежностью клиентских соединений с транзитным узлом Fm, m = 1, M, а число обслуженных заявок быстродействием серверного порта S и надежностью серверного соединения F. Динамика очереди к выходному каналу связи данной СМО описывается цепью Маркова. Множество возможных состояний цепи Маркова определяется размерами буферной памяти.

В качестве меры производительности системы вновь выступает объем пропущенного потока. В рассматриваемом случае данная операционная характеристика определяется как доля быстродействия серверного соединения, достигаемая в условиях агрегирования трафика от M клиентов:

где F = {F1,..., FM } вектор значений надежностей соединений абонентов с коммутатором Fm, m = 1, M, B = {B1,..., BM } вектор значений вероятностей Bm, m = 1, M, а Pk вероятности состояний цепи Маркова. В случае однородных по надежности клиентских каналов связи Fm = F, m = 1, M и/или равенства вероятностей появления абонентских кадров в портах коммутатора объем обслуженного потока обозначается как Z(S, M, K, F, F, B).

В п. 3.2 исследуется работоспособность звездообразного маршрутизируемого сетевого фрагмента, в котором каждый из абонентов всегда имеет пакеты для доступа через транзитный маршрутизатор в магистральную сеть все вероятности порождения клиентских потоков равны единице (Bm = 1, m = 1, M ). В этом случае в списке аргументов пропускной способности можно не указывать вектор интенсивностей B Z(S, M, K, F, F ).

Для маршрутизатора с однородными по быстродействию портами (S = 1) с двумя входящими каналами M = 2 и объеме буферной памяти K = 2 при статистически однородных абонентских каналах связи (F1 = F2 = F ) соотношение (4) принимает вид:

Для статистически однородного сетевого фрагмента (F = F1 = F2 ) вид пропускной способности упрощается до следующей зависимости:

Рис. 2. Сравнительные кривые пропущенного потока от достоверности передачи Если хотя бы одно из клиентских соединений абсолютно надежно, то объем пропущенного потока определяется только качеством серверного соединения звена передачи данных, причем это верно для произвольных K и M, удовлетворяющих условию K M : Z(1, M, K, F, F ) = F, при F = {1, F2 }, F = {F1, 1}, F = {1, 1}. В том случае если весь входящий трафик направляется по одному входящему каналу (F = {F1, 0}) получаем известную зависимость, которая совпадает с выражением (3).

Результаты исследования производительности маршрутизатора с быстродействием серверного соединения вдвое превышающем быстродействие клиентских портов свидетельствуют о снижении эффективности использования буферной памяти транзитного узла при F > m=1 Fm /2, в силу того, что на этом промежутке входящие каналы перестают обеспечивать быстрое серверное соединение должной нагрузкой (рис. 2). На указанном промежутке значений F вероятности состояний Pi, i = 2, K, которые обеспечивают полную загрузку исходящего направления, существенно падают, а вероятности состояний P0, оставляющие выходящий канал без нагрузки, и P1, лишь частично загружающие серверное соединение маршрутизатора, напротив возрастают. Наибольший прирост пропущенного потока с увеличением емкости буферной памяти наблюдается при выполнении равенства m=1 Fm = 2F. Численные исследования также показывают, что чем статистически однороднее клиентские потоки маршрутизатора (чем ближе друг к другу значения F1 и F2 ), тем больше значение пропускной способности на отрезке F m=1 Fm /2, 1. Наибольшее снижение эффективности использования буферной памяти на указанном промежутке наблюдается для статистически существенно неоднородных входящих каналов (например, при F1 = 1, F2 = 0). Исследование агрегирующего маршрутизатора с произвольным быстродействием магистрального канала, числом входящих линий и объемом буферного накопителя в ряде частных случаев показывает, что при абсолютной надежности хотя бы S M клиентских соединений (Fm = 1, m = 1, S) объем пропущенного потока инвариантен к числу агрегируемых каналов и емкости буферного накопителя, и определяется скоростью передачи и качеством выходящего звена переприема данных: Z(S, M, K, F, F ) = SF. Очевидно, что при F = 1 пропускную способность будет определять только физическое быстродействие серверного соединения S. Анализ численных результатов свидетельствует о том, что при построении сетей доступа абонентские линии к пограничному маршрутизатору следует выбирать близкими (однородными) по качеству, поскольку в области высоких достоверностей передачи данных в исходящем канале (F m=1 Fm /S, 1 ) такой выбор приводит к абсолютно лучшему показателю пропущенного потока. И хотя при низком качестве исходящего канала (F 0, m=1 Fm /S ) однородные по качеству абонентские линии дают минимум пропущенного потока, отклонение от потенциально достижимого уровня пропускной способности в этом диапазоне изменения F быстро сокращается с ростом емкости буферной памяти транзитного узла.

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

Вкратце цикл передачи кадра данных от станции отправителя к станции получателя беспроводной сети стандарта 802.11 выглядит следующим образом. Прежде всего, станция-отправитель прослушивает среду для определения ее незанятости. Далее по истечении межкадрового интервала запускается алгоритм случайной задержки для выбора номера слота, в котором можно начать передачу данных. Номер слота равновероятно выбирается из промежутка [0, Sn 1], где Sn размер конкурентного окна, измеренного в слотовых интервалах tc и определяемого соотношением:

Здесь N0 = 1, 10 начальное значение, задающее ширину конкурентного окна при первой попытке отправителя передать данные, а n 0 номер повторной передачи. Ширина конкурентного окна не может превышать максимального значения установленного стандартом.

Номер выбранного слота присваивается значению таймера отсрочки to, после чего начинают отсчитываться слотовые интервалы. В конце каждого слотового интервала таймер отсрочки уменьшается на единицу, при этом прослушивается среда передачи данных ( эфир ). Как только фиксируется занятость среды, таймер отсрочки замораживается до тех пор, пока не освободится среда передачи данных. После освобождения эфира таймер запускается со значения, зафиксированного непосредственно перед замораживанием. По истечении таймера отсрочки (to = 0) станция-отправитель начинает передачу кадра данных. По окончании передачи отправитель ждет квитанцию в течение времени tout, по завершении которого считается, что состоялся конфликт и станции, попавшие в него, увеличивают значение n на единицу, а действия, направленные на передачу данных, повторяются. После успешной передачи кадра ширина окна принимает начальное значение S0.

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

Кроме того, предполагается, что все станции обмениваются кадрами одинакового размера. Тогда согласно последовательности протокольных действий элементарный цикл отправки кадра получателю определится размером межкадрового промежутка tm, периодом случайной отсрочки to, длительностью заморозки таймера случайной отсрочки tz, временем передачи информационного кадра tk, а также величиной тайм-аута ожидания положительной квитанции tout, которая складывается из короткого межкадрового промежутка и времени передачи положительной квитанции.

В качестве меры быстродействия станции выбраны среднее время передачи кадра и пропускная способность. Среднее время передачи кадра T (K, N0 ) складывается из взвешенной суммы средних времен ожидания неудачных отправлений и успешную передачу:

Здесь t(N, K, N0 ) и (N, K, N0 ) средние условные времена до неудачной и успешной N -ой повторной попытки отправить кадр абонентом, а f (N, K, N0 ) функция вероятности продолжительности конкуренции между абонентами за эфир, которая определяется вероятностью успешной передачи кадра на N -ом повторном шаге после N 1 неудач:

Для беспроводной сети с двумя станциями (А и B) дано точное математическое описание процессу передачи кадра данных станцией А до получения положительной квитанции. Численные исследования среднего времени передачи кадра абонентом А показывают, что функция (5) имеет ярко выраженный минимум по параметру N0, определяющему начальный размер конкурентного окна и, как следствие, степень рассеяния станций по длительностям отсрочки перед началом процедуры соперничества.

Для двух соперничающих станций минимум достигается при N0 = 4.

Очевидно, что значение N0, минимизирующее среднее время передачи кадра, максимизирует индивидуальную пропускную способность.

Кроме того, уже на этапе формализации задачи стала очевидной возможность захвата среды передачи данных одним из абонентов. Особенно сильно этот эффект проявляется при малых значениях N0. Уже при первой попытке соперничества двух станций возможен захват среды передачи данных (например станцией В), вероятность которого определится вероятностями того, что у одной из станций (В) длительность отсрочки окажется меньше длительности отсрочки другой станции (А), а затем у успешной станции (В) будет выпадать отсрочка нулевой длительности, чередуясь с отсрочками меньшими, чем оставшееся значение таймера отсрочки станции (А):

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

Рис. 3. Сравнительные кривые минимального и максимального индивидуальных быстродействий, и общей пропускной способности Для снижения вероятности эффекта захвата эфира на неопределенно долгое время предложено во-первых зафиксировать размер конкурентного окна для первой и всех последующих передач, во-вторых длительность случайной отсрочки to выбирать на интервале от 1 до 2N0 1 слотовых периодов tc, исключив тем самым отсрочку нулевого размера и в-третьих применить фиксированный размер конкурентного окна без нулевой отсрочки. Далее проведен анализ предложенных мер ослабления эффекта захвата среды передачи данных аналитически для двух активных станций сети и имитационно для двух, трех, пяти, десяти и двадцати станций.

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

В заключении диссертации представлены основные результаты работы, изложенные в пунктах научной новизны, теоретической значимости и практической ценности.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

В журналах, рекомендованных ВАК России 1. Михеев П. А., Сущенко С. П. О быстродействии агрегирующего канала звездообразного сетевого фрагмента // Вестник Том. гос. ун-та.

Серия Управление, вычислительная техника и информатика. 2010.

№ 4(13). C. 97–105.

2. Михеев П. А., Сущенко С. П. Анализ загрузки агрегирующего порта коммутатора ЛВС // Вестник Том. гос. ун-та. Серия Управление, вычислительная техника и информатика. 2010. № 4(13). C. 106–115.

3. Михеев П. А., Сущенко С. П. Анализ агрегирующего порта маршрутизатора с однородными последовательными интерфейсами // Обозрение прикладной и промышленной математики. 2009. T. 16. Вып. 5.

C. 896–897.

4. Михеев П. А., Сущенко С. П. Анализ индексов производительности звездообразного фрагмента // Обозрение прикладной и промышленной математики. 2008. T. 15. Вып. 5. C. 909–910.

5. Михеев П. А. Индивидуальное быстродействие абонента беспроводной ЛВС стандарта 802.11 // Процессы управления и устойчивость: Труды 42-й международной науч. конф. аспирантов и студентов. СПб.: Издат. Дом С.-Петерб. гос. ун-та, 2011. C. 315–320.

6. Михеев П. А. Эффект захвата в беспроводных ЛВС стандарта 802. // Актуальные проблемы науки: сб. науч. тр. по мат-лам Междунар.

науч.-практ. конф. Тамбов: Изд-во ТРОО Бизнес-Наука-Общество, 2011. Ч. 3. C. 87–89.

7. Михеев П. А. Захват среды передачи данных одной из станций беспроводной ЛВС стандарта 802.11 // Materialy VII Miedzynarodowej naukowi-praktycznej konferencji Dynamika naukowych badan 2011.

Przemysl: Nauka i studia, 2011. C. 23–28.

8. Михеев П. А., Сущенко С. П. Влияние блокировок буферной памяти на пропускную способность звездообразного фрагмента сети // Вестник Том. гос. ун-та. Серия Управление, вычислительная техника и информатика. 2008. № 2(3). C. 22–34.

9. Михеев П. А., Сущенко С. П. О влиянии расщепления сетевого трафика на пропускную способность межузловых соединений // ИТММ-2008: Материалы VII Всерос. науч.-практич. конф. с международным участием. 2008. Ч. 2. C. 34–39.

10. Михеев П. А., Сущенко С. П. Анализ быстродействия мультиплексирующего магистрального канала маршрутизатора // ИТММ-2009:

Материалы VIII Всерос. науч.-практич. конф. с международным участием. 2009. Ч. 1. C. 188–194.

11. Михеев П. А., Сущенко С. П. Об индивидуальном быстродействии абонента беспроводной ЛВС, основанной на технологии WiFi // ИТММ-2010: Материалы IX Всерос. науч.-практич. конф. с международным участием. 2010. Ч. 1. C. 44–47.

12. Михеев П. А., Сущенко С. П. О быстродействии серверного соединения коммутируемой ЛВС // ИТММ-2010: Материалы IX Всерос. науч.-практич. конф. с международным участием. 2010. Ч. 1.

13. Михеев П. А., Сущенко С. П. О пропускной способности звездообразного фрагмента сети // Массовое обслуживание: потоки, системы, сети. Материалы международной науч. конф. Современные вероятностные методы анализа и оптимизации информационнотелекомуникационных сетей. 2011. C. 155–160.

14. Михеев П. А., Сущенко С. П. Об индивидуальном быстродействии абонентского беспроводного соединения // Материалы международной конф. Современные проблемы математики, информатики и биоинформатики, посвященной 100-летию со дня рождения членакорреспондента АН СССР Алексея Андреевича Ляпунова. 2011. С. 72.

15. Михеев П. А., Сущенко С. П. Имитационное моделирование беспроводной ЛВС, основанной на технологии WiFi // ИТММ-2011: Материалы X Всерос. науч.-практич. конф. с международным участием.

2011. Ч. 1. C. 65–69.

Подписано к печати 15.12.2011. Тираж 100 экз.

Бумага офсетная. Формат А-5. Печать RISO Лицензия Серия ПД № 12-0092 от 03.05.2001 г.