автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Математические модели протоколов случайного доступа в сетях передачи данных

Белорусский государственный университет

УДК 619.872:681.03

Хомичков Иван Иванович

МАТЕМАТИЧЕСКИЕ МОДЕЛИ ПРОТОКОЛОВ СЛУЧАЙНОГО ДОСТУПА В СЕТЯХ ПЕРЕДАЧИ ДАННЫХ

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

АВТОРЕФЕРАТ

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

Минск - 1997

Работа выполнена в Белорусском государственном университете

Официальные оппоненты:

Доктор физико-математических наук Малинковский Ю.В. (г. Гомель). Доктор физико-математических наук Рыков В.В. (г. Москва). Доктор физико-математических паук Харин Ю.С. (г. Минск)

Оппонирующая организация: Российский университет дружбы народов (г. Москва).

Защита состоится "27" июня 1997 г. в 10 часов на заседании совета по защите диссертаций Д 02.01.14 при Белорусском государственном университете ( 220050, г. Минск, пр. Ф. Скорины, 4,Главный корпус, ауд. 206).

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

Автореферат разослан ■¿Я » мая 1997 г. Ученый сехретарь совета

по защите диссертаций,

профессор

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

Актуальность темы диссертации.

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

Компьютерные сети представляют собой сложные технические системы, эффективное функционирование•которых в значительной степени зависит от многих стуктурггых и нагрузочных параметров, от используемых на разных уровнях иерархии протоколов доступа к общим ресурсам. Анализ ВС с целью определения и оптимизации вероятностно-временных характеристик, таких как пропускная способность, время и вероятность доставки сообщений, является актуальной проблемой, которую приходится решать на этапах разработки и эксплуатации ВС. Одним из наиболее распространенных методов анализа ВС является математическое моделирование, в частности, методами теории массового обслуживания. Однако, классические системы массового обслуживания с ожиданием и потерями не могут служить адекватными моделями сложпых процессов передачи информации в компьютерных сетях, имеющих многоуровневую иерархическую структуру с различными протоколами доступа! Это послужило стимулом к рассмотрению новых классов систем массового обслуживания и, соответственно, к разработке математических методов расчета их вероятностно-временных характеристик. Одним из таких классов математических моделей, активно исследуемых в последнее время, является класс систем массового обслуживания с повторными вызовами. Особенностью данных систем обслуживания является то, что заявки поступившие в систему и обнаружившие прибор занятым не теряются (как в системах с потерями) и ае становятся в очередь-(как в системах с ожиданием), а через случайные промежутки времени неоднократно поступают на прибор пока не застанут его свободным. Традиционные системы массового обслуживания с повторными вызовами, рассмотренные впервые в 50-60 годах и активно исследуемые в послед-гае годы, возникли как модели узлов коммутаций телефонных линий. Но, <ак оказалось, они могут служить адекватными математическими моделями чоноканалышх сетей передачи данных с протоколами случайного доступа.

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

являются абонентские станции (АС), подключенные через адаптеры сети к моноканалу и осуществляющие приём, храпение и передачу информации в виде Пакетов данных. В качестве АС могут быть персональные компьютеры, средние и большие ЭВМ, любое другое микропроцессорное оборудование. Каналом связи физически может быть кабель (телефонный, коаксиальный, оптоволоконный) или радиовфир в случае радио или спутниковой сети связи. Количество АС в сети всегда конечно, однако, иногда их число может быть достаточно большим или неизвестным, например, когда станции работают па одной час* тоте в радиоэфире. В в тих случаях принято полагать, что число станций в сети бесконечно, и исходящий от них суммарный поток нагрузки характеризуется фиксированной интенсивностью. Моменты появления пакетов у абонентских станций, а также длительности передачи пакетов в канал являются случайными. Поэтому не исключены ситуации, когда несколько АС одновременно претендуют на использование единственного канала связи. Это приводит к разрушению передаваемых пакетов. Проблема состоит в разделении между станциями единственного ресурса — канала связи. Алгоритм распределения канального ресурса между АС сети принято называть протоколом множественного доступа. Одна из основных задач, которую приходится решать разработчикам сети, состоит в выборе известных или разработке новых протоколов доступа, которые обеспечивали бы заданные основные вероятностно-временные характеристики (ВВХ) сети, такие как производительность, пропускная способность, средняя задержка пакетов, вероятность их доставки и др. Решение данной технической задачи предполагает проведение расчетов ВВХ существующих или разрабатываемых протоколов, что, в свою очередь, связано с проблемами построения их математических моделей и разработкой математических методов анализа втих моделей.

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

'Быи&рил Г.П., Ефииушхии В.А. Методы ыииина лохмымх ивфорищиовяо-вычислитель-кш сетей Ц Итоги науки и техяики. Сер. Связь. Т.2: Сети связи. М.: ВИНИТИ, 1988. - С. 60 - 109.

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

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

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

Данная диссертационная работа посвящена проблемам разработки математических методов исследования нетрадиционных систем массового обслужи-

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

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

В течение 1989-1993 годов работа выполнялась в рамках научно-исследовательской программы Белоруссии "Информатика". Подпрограмма: 06. "Локальные и региональные информационно-вычислительные сети". Пункт программы: 06.02.01 "Разработка математических методов и программного обеспечения для определения и анализа вероятностно-ипформационво-временных характеристик вычислительных сетей".

Результаты работы внедрены в части ОКР-365, проводимой ОКБ "Квант" НПО "Грешат" (г.Минск) в 1990 году по теме: "Моделирование ЛВС па основе случайного множественного доступа".

Цель и задачи исследования.

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

Сформулированная цель достигается решением следующих задач:

• определение ВВХ систем с двухатапным обслуживанием и сдвоенными соединениями на первом этапе и иа интервале уязвимости заявок;

• определение ВВХ систем обслуживания с уходом заявок при сдвоенных соединениях;

• определение ВВХ систем обслуживания с непастойчивыми, 1- и р-настой-чивьши заявками;

• разработка комплекса программных средств, реализующих алгоритмы расчета ВВХ перечисленных классов систем обслуживания;

• проведение численных экспериментов расчета ВВХ моделей и проведение исследований по численной оптимизации и сравнению результатов расчета характеристик моделей с измерениями в реальны!

Научная новизна получению результатов Все результаты, изложенные в диссертации получены впервые. В отличие от исследуемых ранее моделей протоколов случайного доступа, рассматриваемых, как правило, в виде систем обслуживания с потерями или с ожиданием и не учитывающих повторную передачу искаженных пакетов, н диссертации разнит иной подход: исследуются системы обслуживания с повторными вызовами, учитывающие ату особенность. Для втих целей введены повые классы систем с повторными вызовами и дисциплинами обслуживания, учитывающих особенности случайных протоколов. В частности, введены новые классы систем с повторными вызовами, моделирующих 1- и р-настойчивые протоколы СБМА/СЕ, обобщепы ранее известные результаты для пеиастойчивого протокола СЭМА/СБ на случай произвольного вида распреде-легат вероятностных параметров моделей, решены задачи расчета стационарного распределения СМО с повторными вызовами и сдвоенными соединениями, р&вее исследуемые только асимптотическими методами.

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

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

- однородным дифференциальным уравнениям второго порядка класса Фукса с регулярными особыми точками, решения которых находятся в виде специальных функций или степенных рядов;

- интегральным уравнениям типа Вольтерра второго рода, приближенное решение которых находится численными методами;

- лилейным однородным дифференциальным уравнениям в частпых производных.

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

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

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

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

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

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

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

• Все полученные результаты реализованы на языке Turbo Pascal для персональных компьютеров типа PC

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

Экономическая значимость полученных результатов. Комплекс программ, написанных па языке ТигЬо-Раяса1 для РС ЛТ и реализующих все теоретические результаты диссертации, представляет интерес для организаций, занимающихся проектированием, созданием, внедрением и эксплуатацией локальных, радио и спутниковых сетей на основе протоколов случайного множественного доступа. О помощью в тих программ можно прогнозировать характеристики сетей, производить настройку параметров протоколов доступа, исследовать влияние на характеристики существующих сетей значений различных параметров (числа станций, длины кабеля, роста нагрузка и др.), использовать в качестве подмоделей при расчете характеристик протоколов более высокого уровня.

Основные положения диссертации, выносимые на защиту.

На защиту выносятся:

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

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

3. Модели широко используемых в локальных сетях типа ETHER.NET 1-настойчивых протоколов СБМА/СЭ в виде систем обслуживания с 1-настойчивымн заявками, адекватность которых доказывается совпадением рассчитанных с помощью моделей характернее« с данными измерений в реальной сети.

4. Модели р-иастойчивых протоколов СЭМА/СО. Показано, что практически во всей области параметров сети р- настойчивый протокол имеет преимущество по сравнению с широко распространенным 1 -настойчивым протоколом.

Личный вклад соискателя.

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

Апробация результатов диссертации.

Результаты диссертации представлялись и докладывались на:

• Конференции ученых социалистических стран "ЛОКСЕТЬ'86,'90" (Рига, 1986,1990),

• V Всесоюзной конференции "КОМПАКТ" (Рига, 1987),

• Республиканском научно-техническом семинаре "Совершенствование методов исследования потоков событий и систем массового обслуживания" (Киев, 1989),

• I, II Всесоюзных конференциях по информационным системам множественного доступа (Минск, 1989, 1991),

• XIV, XV, XVII Всесоюзных шхол&х-семинарах по вычислительным сетям (Минск, 1989, Ленинград, 1990, Алма-Ата, 1992),

• Республиканской научно-технической школе-семинаре "Анализ и синтез систем массового обслуживания и сетей ЭВМ" (Одесса, 1990),

• Всесоюзном научно-техническом совещании-семинаре "Микропроцессорные системы управления технологическими процессами в ГПС" (Одесса, 1990),

• III, V Всесоюзном совещании по распределенным вычислительным системам и сетям (Винница, 1990, Калиниград, 1992),

• Всесоюзной научно-технической конференции "МИКРОСИСТЕМАМ,'93й (Калининград, 1992, Москва, 1993),

• IV Международном семинаре по теории телетрафика и компьютерному моделированию (Москва, 1992),

• II Конференции цо информационным сетям и системам КИСС'93 (Санкт-Петербург, 1993),

• Математической конференции "Проблемы прикладной математики и информатики" (Гомель, 1994),

в I- XII Белорусских зимних школах-семинарах по теории- массового обслуживания (Гродно, 1985, 1987-1989, 1991, Гомель, 1986, Витебск, 1990, Брест, 1992, Мотек, 1993-1995, Гродно, 1996, Минск, 1997).

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

Основные используемые в диссертации методы и полученные результаты опубликованы в 46 научных работах. Из них 16 статей и сообщений в научных журналах, одна статья в сборнике научных работ н двадцать девять тезисов научных конференций.

Структура и объём диссертации.

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

Общий объём диссертации составляет 253 страницы.

Общее количество иллюстраций - 77, занимающих 36 страниц.

Общее число используемых источников равно 218. Они занимают 22 страницы.

ОСНОВНОЕ СОДЕРЖАНИЕ

В первой главе диссертации даётся описание наиболее известных протоколов случайного множественного доступа: ALOHA, ненвстойчивого, 1-и р-настойчивых протоколов CSMA и CSMA/CD. Приводится обзор работ, посвященных исследованию моделей сетей передачи данных с этими протоколами.

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

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

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

Пусть па прибор однолинейной СМО поступает пуассоновский поток заявок с интенсивностью Л > 0. Прибор может находиться в одном из трех состояний: свободен, занят обслуживанием заявки и блокирован. Если в момент поступления заявки прибор свободен, то начинается её обслуживание; если прибор занят, то обслуживание прерывается, обе заявки немедленно покидают прибор и становятся повторными, а прибор блокируется па случайное время Т с функцией распределения (ФР) С(х) = Р{Г < г}; если при поступлении в систему заявки прибор блокирован, то она сразу становится повторной, а состояние прибора не меняется. Длительность обслуживания заявок без учета прерываний является случайной величиной В с ФР В{х) = Р{В < г}. Обслуженные без прерываний заявки покидают систему. Каждая повторная заявка, число которых в системе не ограничено, снова поступает на прибор в произвольном промежутке времени [t,t + At], Л{ 0, с вероятностью i^At + о(Д£), где интенсивность vn > 0, произвольным образом зависит от числа повторных заявок п в системе в момент времени i (f0 = 0). Дисциплина обслуживания повторных заявок точно такая же, как и у заявок из входящего потока.

Описанная СМО является адекватной моделью функционирования канального уровня спутниковой сети связи с протоколом случайного множественного

доступа с оповещением о конфликте.

Пусть §{») - преобразование Лапласа-Отилтьеса ФР В(х), mj =¡ f™ xdB(z)t mc = f™xdC(x), - первые моменты ФР J3(i), С(х) ссютветсгвеппо.

Свяжем с функционированием СМО случайный процесс (»(, гц), t > О, где компоненты имеют следующий физический смысл: it - состояние прибора в момент времени ti i( = 0 - прибор свободен; tt = 1 - прибор занят обслуживанием заявки; ц = 2 - прибор блокирован; тц - число заявок в СМО в момент времени t.

В первом параграфе получены достаточные условия, при которых процесс u>t = (*f, n¡), t > 0, имеет единственное стационарное распределение

Pi(n) = P{t, = ¡, n, = n} > 0, (i, n) € Q, £ P¡(") = l>

(•»en

где íí = {(», n): i = 0,1,2; n = í,oo} - множество состояний процесса ut = (»,, гц). Теорема 3.1 ifyemt 0 < m0 < оо, mj < оо « выявляемо одно «э

f СЛОвыХ.

1. ¡/п~* У > 0, яре П 00 «

л' = Лтв—. ^ < 1.

2. мл а < оо, »у» п оо «

к = (1 -0(Л + о))^- (1 +Лте + < 1.

Тогда процесс а>( = (**, > 0, шит tд^нcmat}^нot ет*ч«ока;кос распределен*«.

Из доказанной теоремы следует, что в случае -* V при п —♦ оо стационарный режим в системе существует только тогда, когда В(0+) = /?(-Н») > 0. Или другими словами, стационарный режим в СМ О существует только в том случае, если с положительной вероятностью В(0+) > 0 .обслуживание заявок будет мгновенным.

Во втором параграфе в Теореме 3.2 получен алгоритм расчета стационарного распределения вероятностей состояний линейчатого процесса = (»<> 6)I * > гДе дополнительная компонента (( имеет следующий смысл:

6 = 0, если прибор свободен (¿, = 0); & ~ промежуток времени с момента начала обслуживания заявки до момента ¿, если Ч = 1; & - промежуток времени с момента начала блокировки до момента если «'( = 2.

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

Теорема 3.3 Еел* к' < 1 пр« уп-*1/,п~*<х> «м* к < 1 прп пил -*с,п-* оо, те рекуррентные соотнохиенщ приведенные а теореме 3.2, з*дихт распределение вероятностей. Если к' > 1 *л* к > 1, то ж? ти соаткошех*? следует р((п) = 0,

. («>)€П.

Из доказанной теоремы следует, что условие < 1 в случае 1/п V, п оо и условие к < 1 в случае ги/Л-» <7, г» -+ оо являются необходимыми для существования стационарного распределения процесса

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

1 + __аШ_

\ щ ) ~ 1С ■Ьаггц + (С + ащ)Сть!т '

где те, щ - первые моменты ФР С(х), В(х) соответственно. Произведен численных расчет пропускной способности С для различных видов распределений: экспоненциального, детерминированного и равномерного. Показано, что пропускная способность системы зависит от вида распределения длительности обслуживания и от среднего значения длительности блокировки. Предельные значения пропускной способности СМО при различных распределениях времени обслуживания равны: 0.6 - для вкспоненциальпого; 0.231 - для детерминированного; 0.282 - для равномерного.

Исследована зависимость среднего времени пребывания заявок в системе V для СМО с пороговой интенсивностью повторения: 1>п = I/, п = 1,/Г — 1, ип = а/п, п = #,оо. Показано, что существует единственное оптимальное значение параметров V, о,N пороговой интенсивности, минимизирующее среднее время пребывания заяврк в системе.

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

со

Ж*) = £«(«) Л ¿«0,1,2, м<1.

nsci

Имеет место следующая теорема.

Теорема 3.4 iTjem» пуа = <7, п = 1,оо, « выполнено условие стационарное т«. Тогда производлщпе функции стационарного распределен»! *Mtvm вид:

Р,(*) = Ро(0)Д_1(') [лгС3(2) + Az(\ + (Л* + о)1 ~ С*(г)

AW = (Ax + c)Î-^^P0(x) + p0(0)Cl(x), А + о

Р,(г) = (Л*-Кг)1 '^'^Р^ + кти, А-Ах

где функции D(x),Ci(x)t » = 0,1,2, определены следующим образом:

A-ß[A+a)

D{i) = a-{Ax + a)-

Л + (Г

Л + а + Л* + At(\x + о)1 ~ ~

А —Ах

ЭД = ЖТ^(Л) ~ ял + <r)) - cß(A + а),

„, . Аг

см-т

l-ß{A 1 - ß(A + а)

А Л + <г

1-^А + а) ■ <т~

Л + а

Сз(г)=-аг-т~- л-л, •

e etfosmnocm ро(0) etm&uemc* по формуле:

О = ЛСа(1) + Л(1 + (А + «гЮа, (1) - С?о(1).

В четвертой главе исследуется СМО с дополнительным предположением, что при столкновении каждая заявка с вероятностью 1 - р покидает систему, а с вероятностью р остается в системе и через случайное время, распределённое по экспоненциальному закону с параметром с, снова поступает на прибор.

В первом параграфе рассматривается случай, когда время блокировки прибора после столкновения заявок равно нулю. Свяжем с функционированием СМО процесс <1/^ = 0<| п0> первая компонента которого будет иметь только два состояния: «| = 0 - прибор свободен, ^ — 1 - прибор занят обслуживанием заявки, и по-прежнему щ - число заявок в системе в момент времени (.

В случае произвольного вида распределения длительности обслуживания В(х) достаточное условие существования стационарного режима имеет вид.

Теорема 4.1 Буст* р < 1, тог9л ярсцесс имеет единственное ста-щиоялрмое распределение.

Определим стационарное распределение процесса и^

р,(п) = Р{», = », гц = п}, { = 0,1, «, оо.

и введем производящие функции

м «о

п=0

П=1

В случае вкспоненциального распределения длительности обслуживания имеет место следующая теорема.

Теорема 4.2 Пуст* В(s) = 1 - е-'", р < 1, тогда производящие функции

сгмщионирною f яспределснш* процесса u/j1' шмект вид:

Р,{х) = Се" (¿1 + (Л + аи)( 1 - р)3 - + avz{\ -р3)) F(a; t;рг + d)+

+ - p) (l - p + +p)) 7^(0 +1 ; fr +1 ; +d),

b

PM^CS'Fia-Mz + d), tdt F(a", b; г)-вщожденная еиперееометрп\сехля функция KfMMtp»

vt i x f«((i + l)'"(a + i-l) «* ..

= + D'à' W<°°*

0 = Ae"e(l+p)ix X (biji + 2Л(1 - p))F(a;i; fi-fd) + 4ApeF(a +1; 6+1; fi + d))"1,

A P

" "(1+P)' . 2Лр

в = 0.5 (14 , ^ . 44 , A „), Ц1+Р)'

Во втором параграфе рассматривается СМО с произвольным видом ФР длительности обслуживания В(я). Для нахождения стационарного распределения процесс = (¡(, rit)i 1Z дополняется до марковского компонентой ((: (( = 0, если t'i = 0; (t - время прошедшее с момента начала обслуживания, находящейся па приборе заявки в момент t, до момента t. Введем дополнительно, к определенным ранее стационарным вероятностям р;(п), » = 0,1, стационарную плотпость

Pi(n, x)dx - P{i, = », n» = n, г < < х + ¿s}, n = 1, оо, s > О, и производящую функцию

«

о» л=1

Тогда имеет место теорема

Теорема 4.3 Пуст* р < 1, тогда пуоизводдцле функ^«« стсцпэнаукс;. распределения имеют вид:

ОД = Ро(0) (е* + Ц' е^">г(и)Ли) , '

ДМ = Ро(0) (1 - 5(х)) е-% («-"),

л(0) = (г* + (1-£(-;1ви)) +<Г'(1~")) 1.

где фунхцжя д(г) является решением интегрального уравнения д(х) = А?0(*) + / (?(*, «М«)«*«, 0 < г < 1,

* Л

и) = +-я« (-)'"1 В' (--ь-) ■

V VI х2/ \ V X/

ге »

го(») =

М*) =

(1_р)(1_р+(1+р),)'

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

В третьей параграфе исследуется СМО, в которой после столкновения запвоЕ; каждая из ш с вероятностью 1 - р покидает систему» а прибор блокируется на случайное время с функцией распределения 0(х). Заявки (первичные или повторные), поступающие на прибор в течение его блокировки, становятся повторными. После истечет« времени блокировки, прибор снова готов к обслуживанию заявок. Итак, пусть В(х) - функция распределения длительности обслуживания заявок на приборе, Л > 0 -интенсивность входящего потока первичных заявок, 0 < у < со - интенсивность повторного обслуживания, р < 1 - вероятность того, что после столкновения заявки остаются в системе; тс, ть -первые моменты распределений С(х), В (г) соответственно. Рассматривается случайный процесс = («(>"()) * > 0. Здесь компоненты процесса имеют следующий смысл: ц - состояние прибора в момент 4: 1( = 0 - прибор свободен; и ~ 1 - прибор занят обслуживанием заявки; {, = 2 - прибор блокирован; п( - число заявок в системе.

Теорема 4.4 Пуст ть < оо, * выполнено неравенство

тогда процесс V, имеет единственное стационарное распределение.

В случае марковской СМО с $Р длительности обслуживания В(х) = 1 -е_м,!| г > 0, и длительности блокировки С (г) = 1 - е"*1", х > 0, тв = 7-1, производящие функции стационарного распределения

СО ОО ОС

>1=0 п=1 п=0

определяются следующей теоремой.

Теорема 4.5 В случае экспоненцчалтом распределения длительностей обслужгвлния а блокировки, *р% выполнении условия существования единственного стационарного распределения

р<1>

производящее функции РДг) ъмют впд:

со в=0

со

nal

«de

. Д (*) = A-'W (A*a + A(1 - P)(l - P + (H M).

Д(г) = (1-р)7(1-р + (1+р)«)-Л^ a ко«^к1)кеятм dj^, « — 0,3, n = 0,oo, определяйте* по рекуррентным формулам:

4),о = i.

Dt,

j S0D<>) +Si¿-iBo -—

, - Л>) + Sijl-lCi) , --

= k(k-AB-Da) >k=h00>

»»0

¿«0

, tu + r^On •> il3 + r¿Oai2 + Al = ___i ^ =----(

iai + r^ox bn + гЩап —— » t

rHi ' Ai = fJ.fi ' O.oo, = J-íit

где

Л7(1+Р) '

наконец,

о» = (Л + 7?2)М &ц = 2о(Л(1 ~ го) +

с12 = ту3/»'» <»» = Л2р(1 + рг0 - р)/" - я(А + "У?5)/(Лу ), 6а = *о (Лга(Л + р + У) - МЛ + 7) - Л7(1 - р)1) /(Ли), 021 = -Л/г, = ¡>ц/г0, ои = (Л + V + У)/", Ь» = ¿«/«о-Из доказательства данной теоремы следует, что условие

Л

является необходимым для существования стационарного распределения у процесса = (¿,, п,), { > 0.

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

Подобные системы обслуживания возникают при моделировании сетей передачи данных с протоколом случайного множественного доступа, контролем песухцей и обнаружением конфликтов (ненастойчивый протокол СБЫЛ/СБ). Передача пакетов п сети с данным протоколом происходит следующим образом. При возникновении пакета АС проверяет состояние моноканала. Бели капал занят, то после случайной задержки станция снова повторяет проверку состояния канала. Если моноканал свободен, то начинается передача пакета. Из-за задержки распространения сигнала по передающей среде, существует интервал времени с момента начала передачи пакета, в течение которого капал

для остальных АС по-прежнему остается свободным и поэтому станции могут начать передачу своих пакетов. В атом случаи происходит наложение передач пакетов от нескольких станций. Каждая передающая станция во время передачи своего пакета "прослушивает" капал и при обнаружении искаженного сигнала ЛС прекращает передачу пакета. При атом в канал выдается специальный пакет, приняв который остальные АС также прекращают передачу. Иопавш Ьие в конфликт станции через некоторое случайное время снова повторяют попытку "захвата* моноканала. Если же за время распространения сигнала по среде другие АС не начнут передачу, то далее пакет передается без прерываний, так как к этому времени остальные АС получат сигнал о занятии канала. Пакет, переданный без прерываний, покидает сеть.

В качестве математической модели описанной сети рассмотрим следующую систему массового обслуживания с повторными вызовами. Имеется однолинейная СМО с мгновенной интенсивностью Лт = Х(М - т) пуассоповско-го входящего потока первичных заявок, где М - число источшасов нагрузки (каждый источник может находиться в одном из двух состояний: свободен или занят; в свободном состоянии источник генерирует единственную заявку, переходя в занятое состояние; в занятом состоянии источник находится до момента завершения успешного обслуживания сгенерированной заявки, переходя при »том в свободное состояние), т - число заявок в системе в текущий момент времени, А - параметр экспоненциального распределения времени генерирования источником новой заявки. Каждая заявка характеризуется длительностью обслуживания па приборе В и длительностью интервала уязвимости Л, начало которого совпадает с началом обслуживания заявки. Предполагается, что длительности обслуживания и интервала уязвимости являются независимыми случайными величинами с функциями распределения В(г) — P{jB < ж}, А(х) = Р{Л < г} соответственно. Если за время интервала уязвимости на прибор не поступят другие заявки, то в течение остатка времени тах(0, В — А} обслуживание происходит без прерываний (бесконфликтное обслуживание), и после его завершения заявка покидает систему. Если в течение интервала уязвимости на прибор поступает другая заявка, то в втот момент прибор блокируется на случайное время Т с ФР С(г) = Р{Т < х}, а обе заявки покидают прибор и становятся повторными. После истечения времени блокировки прибор освобождается. Если в момент поступления заявки в систему прибор занят бесконфликтным обслуживанием заявки или находится в блокированном состоянии, то состояние прибора не меняется, а поступившая заявка становится повторной. Каждая повторная заявка независимо от остальных поступает свова

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

Заметим, что в данной системе обслуживания длительность обслуживания заявки В может быть меньше интервала уязвимости А далной заявки, если Р{2? < Л} > 0. Физически а то означает, что время передачи пакета меиыяе времени распространения сигнала в сети. Это может наблюдаться, например, в радиосетях при передаче очень короткого пакета данных. В случае, если обслуживание заявки завершилось, а интервал уязвимости не истек и в это время на прибор поступает другая заявка, то обслуженная заявка все равно становится повторной. Физически ата ситуация возможна в том случае, если короткий пакет, переданный в моноканал еще не достиг остальных АС и в вто время начинает передачу пакета другая станция.

В первом параграфе рассматривается СМО, в которой число АС М является сколь угодно большим М > 1, а А < 1, причем MX = А. Входящий поток первичных заявок будем считать пуассоновским с параметром А. Введем следующие состояния системы обслуживания для произвольного момента времени t: П( - число заявок в системе; t< - состояние прибора: г{ = 0 - прибор свободен, »( = 0„ - прибор свободен, интервал уязвимости не истек, i( = 1 ~ прибор занят бесконфликтным обслуживанием заявки, ц = 1» - прибор занят обслуживанием заявки, интервал уязвимости не истек, it — 2 - прибор блокировал. Рассмотрим случайный процесс £>( = (i(, n,), i > 0, с фазовым пространством:

Й ={(»>), п = »€/„}

где /0 = {0}, /, = {0,0,, 1,Ь} 1п = /, п > 2, / = {0,0,, 1,1«2). Введем обозначения <*(«) = J™e~"dA(x), - преобразования Лапласа-Стилтьеса ФР А(г),

ть, mcl -первые моменты ФР В(х), С(х).

Имеет место следующая теорема.

Теорема 5.1 Пуст* тс > 0, тогда достаточные условия существования единственного стационарного распределения процесса = (»(,»»<), t > 0, «м«ют

вид:

(1 - £(<))e~"<ä e'"dA(x), з > 0, в > 0,

1. Еслч lim ~ а, то

ft-»CC

K ~ S0(A + <t) '

где

с,ч _xa(s)mb_

S0(i) =--г. ® > 0.

2. Есл* lim vn - v > 0, то

, 1тИ(0+) + те(1-Л(0+)) _ к = А-—г-< 1.

Л(0+)

Из доказанной теоремы следует, что в случае v при п —► оо в системе существует стационарный режим, если Л(+0) > 0, т.е. с положительной вероятностью интервал уязвимости заявки должен быть равен нулю. Применительно к сетям передачи данных ато означает, что если интенсивность повторных передач пакетов не зависит от числа накопленных в сети пакетов, то в сети с большим числом станций не существует стационарного режима.

Далее в Теореме 5.2 приводятся рекуррентные соотношения для расчета стационарного распределения процесса = (<(,п(), i > 0. Полученные соотношения используются для определения характеристик СМО и проведения численного ана.1кзз этих характеристик.

Во втором параграфе пятой главы получены в явном виде производящие функции стационарного распределения для случая, когда vn - а ¡п.

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

В шестой главе исследуется система обслуживания, являющаяся моделью сети передачи данных с 1-настойчивым протоколом CSMA/CD). Напомним, что согласно ненастойчивого протокола CSMA/CD, каждая абонентская станция (АС), при возникновении пакета, перед началом его передачи проверяет состояние хавала. Если канал свободен, то начинается передача, если канал занят, то передача откладывается на некоторое случайное время. После случайной задержки попытка "захвата* канала повторяется. Однако, наиболее известным является 1-настойчивый протокол CSMA/CD. Его отличие от ненастойчивого состоит в следующем. При обнаружении канала занятым, АС не откладывает передачу на потом, а следит за состоянием канала и при его освобождении

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

Данный протокол получил название 1-нестойчивый протокол случайного множественного доступа с контролем несущей и обнаружением конфликтов (1-настойчивый CSMA/CD). Он известен как протокол канального уровня широко распространенной локальной сети (ЛС) ETHERNET.

В качестве модели данной сети рассмативается следующая СМО. Пусть имеется однолинейная система массового обслуживания с входящим примитивным, потоком с мгновенной интенсивностью А„, = А(М — т), где т - число заявок в системе в данный момент времени, М - число источников нагрузки (число станций в ЛС), А - интенсивность генерирования заявки свободным источником. Прибор системы может находиться в одном из четырех состояний: свободен, занят обслуживанием заявки на первом и втором этапах, блокирован. При поступлении заявки из входящего потока в системе происходят следующие изменения в зависимости от состояний прибора.

• Если прибор свободен, то начинается первый втап обслуживания со случайной длительностью с функцией распределения А{х).

• Если прибор находится на первом этапе обслуживания, то обслуживание прерывается, обе заявки становятся повторными, а прибор блокируется на случайное время с функцией распределения С(х). Каждая такая повторная заявка снова поступит на прибор через случайное время, распределенное по экспоненциальному закону с параметром v. Назовем эти повторные заявки ненастойчивыми повторными заявками.

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

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

покидает систему. .

• Прибор блокирован. Аналогично предыдущему случаю заявка становится

1-настойчивой и ожидает освобождения капала.

Дисциплина обслужив алия 1-настойчивых повторных заявок следующая. Пусть в момент окончания второго этапа обслуживания (блокировки) в системе имеется / > 0 1-настойчивых повторных заявок. Тогда, если; = 0, то в этот момент прибор освобождается, если / = 1, то единственная 1-настойчивая заявка поступает на первый этан обслуживания, если ; > 2, то все ; 1-настойчивые заявки становятся ненастойчивыми, а прибор блокируется.

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

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

В третьем параграфе исследуется СМО с пуассоновским входящим потоком может рассматриваться как модель локальной сети с бесконечно большим числом источников нагрузки М -* оо, при условии, что интенсивность генерирования заявок отдельной станцией А -+ О, причем так, что АМ К.

Введем следующие обозначения:

где /?(*), 7(3) -преобразования Лапласа-Стилтьеса функций распределения ■В(х), С (г) соответственно, а пц,, т( их первые моменты.

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

функцию распределения В(х). После его завершения, обслуженная заявка

Ч»)=р(>)+*№, ссС*) = тМ+

¿И») = "1Ьз + Р(з), с^а) = тс> + 7(3),

Теорема 6.3 1. Если П1/Л —» а <. со при п —» оо, то при выполнекнп условия

Ami <Si{Л + с)

процесс »Metro единственное croaquoKopNO« ^аеп^едеиеияе, г^е

2. Если irn V > 0 njm п —» оо, то процесс wt имеет единственное стационарное распределение при выполнена» условия

_тьЛ(0+)С(0+)_

тЬ < тьС{П)А(Ъ+) + тс{ 1 - Л(0+)) 5(0+)'

В Теореме 6.4 получены в явном виде производящие функции ста-ционарпого распределения для случая ил = <г/п. Из доказанной теоремы следует, что условие

Ami<5i(A + cr)

является необходимым и достаточным для существования единственного стационарного распределения в случае nvn = с.

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

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

отличие от 1-настойчивого протокола состоит в следующем. Обнаружив канал свободным, станция либо начинает передачу пакета с вероятностью р, либо с . дополнительной вероятностью 1 — р откладывает ее на некоторый промежуток времени г, после чего процедура "захвата* канала повторяется". Длительность отсрочка передачи пакета г предполагается больше времени распространения сигнала по передающей среде. Таким образом, если в момент освобождения какала имелось несколько готовых станций, а начала передачу только одна из них, то через время'г остальные станции обнаружат канал занятым и их мередачи будут отложены, т.е. конфликта, в отличие от 1-настойчивого протокола, в данном случае не будет. Очевидно, представляет интерес выбор вероятности р и длительности промежутка г с целью оптимизации характеристик сети с р-настойчивым протоколом. Действительно, чем больше вероятность р, тем больше вероятность конфликта, что приводит к падению пропускной способности и увеличению задержки передачи пакетов. С другой стороны, уменьшение вероятности р приводит к многократному отказу от передачи и накоплению пакетов в сети, что также отрицательно влияет на характеристики сети. Поэтому представляет интерес построение адекватных моделей сетей с р-настойчивым протоколом, с помощью которых решаются подобные задачи оптимизации параметров протокола. .Исследованию .таких моделей посвящена седьмая глава диссертации.

В качестве модели сети с р-настойчивым протоколом СЭМА/СО рассмотрим следующую систему массового обслуживания. Имеется однолинейная система с повторными вызовами. В систему поступает примитивный поток заявок с мгновенной интенсивностью А„ = А(М-п), где М и X определены выше, а п - число заявок в системе в данный момент времени. Прибор системы может находится в одном из трех состояний: свободен, занят обслуживанием заявки и блокирован. При поступлении в систему новой заявки происходят следующие действия. Если прибор свободен, то начинается обслуживание поступившей заявки. Если прибор занят обслуживанием или блокирован, то поступившая заявка становится р-пастойчивой. В момент освобождения канала, который обозначим через каждая из имеющихся в системе р-вастойчивых заявок с вероятностью р < 1 поступает на прибор, а с дополнительной вероятностью 1 -р не совершает никаких действий, оставаясь р-настойчивой заявкой. Пусть ;-число р-настойчивых заявок, поступающих на прибор в момент ¿0-

• Если ; = 0, т.е. ни одна из заявок на прибор не поступила, то в момент ¿о прибор освобождается, а через промежуток времени г, т.е. в момент г, процедура поступления р-настойчивых заявок на прибор повторяется,

если, копечно, прибор в »тот момент еще будет свободным.

• Если j = 1, то в момент i0 начинается обслуживание в течение случайного времени с функцией распределения В(г) единственной заявки, поступившей на прибор. Обслуживание пе прерывается и после его завершения заявка покидает систему.

• Если / > 1, то поступившие па прибор заявки становятся ненастойчивыми повторными заявками, а прибор блокируется на случайпое время с функцией распределения С(х).

Каждая пенастойчивая заявка через случайное время, распределенное по экспоненциальному закону с параметром р> снова поступает на прибор. Её обслуживание происходит по такому же алгоритму, как и для заявок из входящего потока.

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

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

В третьем параграфе рассматривается модель сети с учетом времени распространения сигнала по передающей среде. Считается, что обслуживание заявок па приборе состоит из двух этапов. Первый этан соответствует времени распространения сигнала в передающей среде, второй втап -времени бесконфликтной передачи пакета. Соответственно, па первом этапе обслуживание может быть прервано, если на прибор поступит другая заявка. На втором этапе обслуживание происходит без прерываний. После зввершешм второго этана обслуживания заявка покидает систему. Пусть A(z), £(х) функции распределения длительностей первого и второго этапов обслуживания, а <7(г)-фушщия распределения дительности блокировки прибора. В систему поступает примитивный ноток заявок с мгповешюй интенсивностью Л„ = А(М —п), где п -число заявок в системе в данный момент времени. Прибор системы может находиться в одном из четырех состояний: свободен, занят обслуживанием заявки на первом или втором этапах, блокирован. При поступлении в систему первичной заявки её

обслуживание происходит следующим образом. Бели прибор свободен, то с вероятностью р < 1 начинается первый этап обслуживания, или с вероятностью 1 - р заявка становится р-ластойчивой. Если прибор занят обслуживанием па первом этапе, то с вероятностью р < 1 заявка поступает на прибор, а с вероятностью 1 — р становится р-настойчивой. Поступившая im прибор заявка прерывает текущее обслуживание, при этом обе заявки немедленно покидают прибор и становятся ненастойчивыми заявками, а прибор блокируется. Если же прибор занят обслуживанием заявки на втором этапе или блокирован, то поступившая заявка становится р-пастойчивой, а состояние прибора не меняется. После истечения времени второго этапа обслуживания или времени блокировки

каждая из имеющихся в системе р- настойчивых заявок с вероятностью р < 1

ы

поступает на прибор немедленно, а с дополнительной вероятностью 1 - р поступает на прибор через экспоненциальное время с параметром а, при этом дисциплина их обслуживания совпадает с дисциплиной обслуживания заявок из входящего потока. Пусть ¿'-число р-настойчивых заявок поступивших па прибор сразу после его освобождения. Если j = 0, то прибор освобождается. Если У = 1, то единственная поступившая на прибор заявка следует па обслуживание. Если j > 1, то поступившие на прибор заявки немедленно становятся ненастойчивыми повторными заявками, а прибор блокируется. Каждая ненастойчивая заявка через случайное время, распределенное по экспоненциальному закону с параметром v, снова поступает на прибор. Дисциплина обслуживания ненастойчивых заявок такая же, как у заявок из входящего потока.

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

выводы

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

1. Развита теория систем обслуживания с повторными вызовами и сдвоешш-ми соединениями, являющихся моделями протоколов типа ALOHA. Решены

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

2. Исследован класс систем обслуживания с повторными вызовами, моделирующих ненастойчивый протокол СЭМА/СВ. Получены обобщения ранее известных результатов на случай произвольного вида функций распределения основных вероятностных параметров модели. Исследованы зависимости характеристик СМО от ее параметров. Доказано о существовании и получены численные значепия оптимальных параметров пороговой стратегии повторного обслуживания.

3. Введен новый класс систем обслуживания с повторными вызовами и дис-циилинами обслуживания, моделирующими 1-пастойчивый протокол С5-МА/С1). Исследованы системы с пуассоновским и примитивным входящими потоками нагрузки при общих предположениях относительно распределений основных параметров СМО. Исследовано влияние на характеристики СМО числа источников нагрузки, интенсивности повторных передач. Сравнение результатов моделирования с измерениями в реальной сети подтвердило адекватность рассматриваемых моделей.

4. Введен новый класс систем обслуживания с повторными вызовами, моделирующих моноканал с р-настойчивым протоколом СБМА/СБ. Исследованы СМО типа Л/1(3|1 без интервала уязвимости заявок и типа М\М\\ с учетом его длительности. Доказано существование оптимальных зпачениЙ параметров протокола. Проведен сравнительный анализ характеристик 1- и р-настойчивых протоколов.

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

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ

1. Хомичков И.И. Последовательно соединенные системы массового обслуживания с "разогревом"// Вести АН БССР. Серия физ.-мат. наук.- 1985.4. - С. 113-114.

2. Хомичков И.И. Модель маршрута сети коммутации каналов с повторными вызовами // Математическое и программное обеспечение САПР сетевых систем: Межвуз. сборник. - Йошкар-Ола, 1985. - С. 41 - 46.

3. Хомичков И.И. Расчет характеристик модели локальной сети с протоколом доступа МДПН/РК // Локальные вычислительные сети. Конференция ученых социалистических стран. Тез. докл. кояф. - Рига, 1986. - С. 150 - 155.

4. Хомичков И.И. О стационарном распределении числа требований в системе Л/[<?|1 \М\\\КЦ Вести АН БССР. Серия физ.-мат. наук.-1986-21- С. 119-120.

5. Хомичков И.И. Производящие функции вероятностей состояний однолинейной системы с повторными вызовами // Вестник Б ГУ. Серия 1. -1087.- 1. - С. 51 - 55.

6. Хомичков И.И. Модель локальной вычислительной сети со случайным множественным доступом // Автоматика и вычислительная техника. -

1987. - 1. - С. 58 - 62.

7. Хомичков И.И. Модель для исследования локальной сети передачи данных // Вычислительные сети коммутации пакетов. V Всесоюзная конференция "КОМПАКТ". Тез. докл. конф - Рига, 1987, - С. 209 -213.

8. Хомичков И,И. О системе обслуживания с ненадежным прибором при наличии повторных вызовов // Вести АН БССР. Серия физ.-мат. наук.

1988,- Б.- С. 119-120.

9. Хомичков И.И. Система обслуживания с повторными вызовами, предварительным обслуживанием и блокировками // Известия АН СССР. Техническая кибернетика. - 1988. - 1. - С. 188.

10. Хомичков И.И. Однолинейная система с повторными вызовами и входящим потоком Кокса второго порядка // Вестник ВГУ. Серия 1. - 1988. - 3. -С. 70 - 71.

11. Хомичков И.И. Расчет характеристик системы массового обслуживания с повторными требованиями при сдвоеппых соединениях // Автоматика л телемехапика. - 1988. - 4. - С. 77 - 84.

12. Хомичков И,И. Модель локальной сети с протоколом доступа CSMA/CD // Автоматика и вычислительная техника. - 1988. - 5. - С. 53 - 58.

13. Хомичков И.И, Анализ характеристик CSMA/CD сети с конечным числом станций // Автоматика и вычислительная техника. - 1990. - 1. - С. 39 -

48.

14. Хомичков И.И. Система М|М|1 с повторными вызовами и очередью перед прибором // III Всесоюзное совещание по распределенным автоматизированным системам массового обслуживания. Тез. докл. копф. - М.,

1990. - С. 187 - 188.

16. Хомичков И.И. Расчет характеристик модели ЛВС с 1-пастойчивым протоколом CSMA/CD // XV Всесоюзный семинар по вычислительным сетям. Тез. докл. конф. - Ленинград, 1990. - С. 260 - 265.

1(5. Хомичков И.И. Модель ЛВС с 1-настойчивым протоколом CSMA/CD // Автоматика и вычислительная техника. - 1991. - 6. - О. 41 - 61.

17. Хомичков И.И. Об оптимальном управлении о сети передачи данных со случайным множественным доступом Ц Автоматика и телемеханика. -

1991. - 8. - С. 176 - 188.

18. Хомичков И.И. Модель ЛВС с 1-настойчивым протоколом CSMA/CD }j Материалы Всесоюзной паучно-технической конференции "МИКРОСИСТЕМАМ". Тез. докл. конф. - Калининград, 1992. - С. 176 - 178.

19. Хомичков И.И. Моделирование ненастойчивого, 1- и р-настойчивых протоколов CSMA/CD // IV Международный семинар по теории телетрафика и компьютерному моделированию, - М., 1992. - С. 182 - 192.

20. Хомичков И,И. Исследование моделей локальной сети с 1-настойчивым протоколом CSMA/CD // Автоматика и телемеханика. - 1993. - 12, - С.

89 - 100.

21. Хомичков И.И. Расчет характеристик локальной сети с р-настойчивым протоколом множественного доступа //II Конференция информационные сети и системы. - Санкт-Петербург, 1993. - С. 108 - 109.

22. Хомичков И.И. Модель локальной сети с р-настойчивым протоколом случайного множественного доступа // Научно-техническая конференция "МИКРОСИСТЕМАМ". Тез. докл. коиф. - М., 1993. - С. 12 - 16.

23. Хомичков И,И. Моделирование локальной сети с р-настойчивым протоколом CSMA/CD // Автоматика и вычислительная техника. - 1993. -4. - С. 43-61.

24. Хомичков И.И. Анализ модели р-настойчивого протокола CSMA/CD // Вестник БГУ. Серия 1. - 1994. - 1. - С. 54 - 58.

25. Хомичков И.И. Расчет характеристик локальной сети с р-настойчивым протоколом случайного множественного доступа // Автоматика и телемеханика. - 1995. - 2. - С. 67 -80.

26. Kbomichkov I.I. Study of models of local networks with multiple- access protocols// Automation and Remote Control 1993. Vol. 54,'N 12. P. 1801-1811.

27. Khomichkov I.I. Calculation of tbe characteristics of local area network with p-pereiatent protocol of multiple random access// Automation and Remote Control. 1995. Vol. 56, N 2. P. 208-218.

РЕЗЮМЕ

Хомичков Иван Иванович

МАТЕМАТИЧЕСКИЕ МОДЕЛИ ПРОТОКОЛОВ СЛУЧАЙНОГО ДОСТУПА В СЕТЯХ ПЕРЕДАЧИ ДАННЫХ

Ключевые слова: система массового обслуживания, повторный вызов, про-.

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

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

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

В диссертации изучены системы массового обслуживания типа М\С\\ с пов- -торными вызовами и блокировками прибора при сдвоенных соединениях. Исследованы системы типа М|С|1 с повторными вызовами с потерями заявок при сдвоенных соединениях, Данные системы являются адекватными моделями протоколов случайного доступа с оповещением о конфликте.

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

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

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

SUMMARY

Homitchkov Ivan I.

MATHEMATICAL MODELS OF RANDOM ACCESS PROTOCOLS IN ¡DATA TRANSMISSION NETWORKS

Keywords: queueing system, repeated call, service process, steady distribution, model, random access protocol, monochanriei network.

The object of the thesis research is a class of queueing systems with repeated calls, Which serve as models for monochannei data transmission networks with asynchronous random multiple-access protocols.

The primary aim of the paper is developing and perfection of analytical methods for calculating of probabilistic characteristics of being studied queueing systems, analysis and optimization of characteristics of models.

Queueing systems of M | G11 type with retrials and locks of the server with twin connections are studied in the thesis. Systems of m)g| 1 type with repeated calls, losses and twin connections are investigated. These systems are adequate models of random access protocols with collision detection.

Classes of retrial queues with finite and infinite number of sources, which disciplines of service take into account features of nonpersistent, 1- and /^-persistent carrier-sense random access protocols with collision detection, are introduced and studied.

A complex of programs for calculating characteristics of studied queues is developed. Numerical analysis of characteristics of systems is performed.

Results of Che thesis provide effective investigating of characteristics of existent arid prospective data transmission networks with random access protocols.

35

РЭЗЮМЕ

Хахичкоу 1ван 1ванав1ч

матэматыч1шя мадэл1 пратакола? выпадковага доступу 9 сетках перадачы длдзеных

Ключавыя словы: астэма масавага абслугоування, паУторны выклЬс.

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

Аб'ектам даследаванняу дысертацыйнай працы з'яуляецца хлас с!стэм масавага абслугоування з пауторным! выюпхам!, ях5я з'яуляюцца мадэлям! монаканальных сетах перадачы дадэсных з асшхронным! пратаколам! выпадковага множнага доступу.

Асноуная мэта працы заключаецца у распрацорцы 1 Удасханаленн! аналогичных метадау разл1ку ¡мавернасных характеристик вывучаемых остом абслуго$гвания, анализ) аптым1зацыя харахтарысгых маделяу.

У дысертацы! вывучаны асггэмы масавага абслугоування тыпу мк! 1 з наборным! выкл)кам1 I блаюроукам! прибора пры здвоеных злучэннях. Даследаваны астэмы тыпу М1011 э пауторным! выкл)кам1 са стратай заявак пры здвоеных злучэннях. Гэтыя астомы з'*Уляюцца алэкватным! маделям! пратаколау выпадковага доступу з алавяшчэннем аб канфл1кце.

Уведоены ! вывучаны класы йсгэм масавага абслугоУвання э пауторпым1 выюикам! з канечнай 1 бясконцан колькасцю крышц нагрузк!, дысцыпл'шы абслугоування яюх улсчваюць асабл>васщ ненастойшвых, I- I р-настойл!вых пратаколау выпадковага доступу э кшггролем нясучай 1 выкрыццём канфл1ктау.

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

Вышю дысертацы1 дазваляюць эфехтыуна даследаваць характарыстык! ¡сиуючых 1 перспектыуных сетах перадачы двдзеных з протоколам! выпадковага доступу.

с