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

РОССИЙСКАЯ АКАДЕМИЯ НАУК ИНСТИТУТ ПРОБЛЕМ ПЕРЕДАЧИ ИНФОРМАЦИИ . МОСКОВСКИЙ ФИЗИКО-ТЕХНИЧЕСКНЙ ИНСТИТУТ

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

РЫЛЕЕВА НАТАЛЬЯ АНАТОЛЬЕВНА

УДК 621.394.74

УПРАВЛЕНИЕ ДОСТУПОМ СТАНЦИЙ В СИСТЕМАХ СВЯЗИ С КОЛЛЕКТИВНО ИСПОЛЬЗУЕМЫМ ШИРОКОВЕЩАТЕЛЬНЫМ КАНАЛОМ

специальность 05.13.01 " Управление в технических системах "

АВТОРЕФЕРАТ

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

МОСКВА ■ < 1994

Работа выполнена в Институте проблей передачи пнформащш Российской академии науж.

Научные руководители: доктор технических наук

профессор Б.С. Цыбаков;

кандидат технических наук С.П. Федорцов

Официальные оппоненты: доктор технических наук

А.Д. Харкевпч

кандидат технических наук A.M. Тгаряиков

Ведущая организация: Институт проблем управления РАН

(г.Москва)

Защита состоится Н&^ШьЯ- 1994 г. в часов на заседании спепиалшзированвого совета Д.003.29.01 в Институте проблем передачи информации РАН по адресу • 101447, Москва, РСП-4, ул. Ермоловой 19.

С диссертацией можно ознакомиться в библиотеке ИППИ РАН.

Автореферат разослан г.

Ученый секретарь специализированного совета

доктор технических наук „ С.Н.Степанов

•V

■Актуальность проблемы

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

В диссертации рассматриваются методы множественного доступа ЛД), которые используются в локальных проводных сетях связи, ра-юсетях и системах со спутниковыми каналами связи. Модель снсте-ы МД состоит по некоторого числа станций, подсоединенных к обще-у каналу свяоп. Каждый пользователь такой системы передает своп акеты в канат связи в соответствии с алгоритмом доступа. Некото-ые алгоритмы прп передаче допускают возникновение конфликтов, т.е. аложение двух или более пакетов". В этом случае сообщения мешают руг другу правильно передаваться. Как правило, ни одно из еих не остпгает адресата п вынуждено передаваться вновь. Для разделения аложпвшнхся пакетов (разрешения конфликтов) существуют разлитые методы. Необходимо отметлть, что для каждого метода имеются ,папазоны нагрузок, где его применение является более эффективным го сравнению с другими методами. Прп слабой п средней нагрузке ;ля организации работы сетей удо бно использовать методы случайного /тожественного доступа (СМД), прп которых конфликты раарешают-■я с помощью датчиков случайных чисел. Методы СМД предполагают галлчие в системе обратной связи, с помощью которой пользователи узнают о том, какое событие произошло в канале. При разрешении конфликтов пользователи в своих действиях руководствуются совокупностью правил, которые составляют основную часть алгоритма случайного множественного доступа.

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

пакетов пропсходпт почти сразу. При больших нагрузках в системам СМД большую часть времени занимает разрешение конфликтов.

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

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

Целью работы является:

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

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

3. Оценивание задержки передачи пакета в алгоритме дробления.

4. Анализ стек-алгоритма СМД с конечным стеком и пропадание?, пакетов, выходящих за его пределы. Исследование поведения скоростз передачи н средней задержки пакета при изменении глубины стека.

, Методика исследования

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

Основные научные результаты

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

:следуются четыре варианта алгоритма.

2. Исследована, зависимость скорости передата стек-алгоритма для «альноп сети от параметра несбалансированности генератора слу-1Йпых чисел.

3. С помощью метода барьеров найдены условия существования и ;ппственностп решения системы уравнений, описывающей алгоритм.

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

5. Рассчитаны скорость передачи н средняя задержка палета в стек-хгоритме с конечным стеком и пропаданием пакетов. Исследовано шшше увеличения глубины стека на характеристики алгоритма. Порченные результаты находятся в соответствии с результатами для юовоп модели стек-алгоритма СМД.

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

1. Отыскание аналитического выражения и получение численных езулътатов для средней задержки пакета алгоритма с разрешением энфлпктов по номерам станпип.

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

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

4. Получение выражений и численных результатов для средней ско-остп и средней задержки передачи пакета в сгек-алгорптме СМД с ропаданием пакетов и конечной глубиной стека.

Практическая значимость работы

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

Результаты работы используются в Институте проблем передачи нформапип Российской академии наук, в ВЦКБ "Полюс" (г. Воро-:еж). Практическая значимость подтверждена актом внедрения.

Аппробаддя работы

Материалы диссертационной работы докладывались на научных конференциях Мосювского физико-технического института' (1991, 1992), на лабораторных семинарах, на Конференциях молодых ученых НПГО1 РАН (1991,1992, 1993), на Международной Конференции по Теории информации 1ЛУ1Т-Э4.

Публикации

Основное содержание диссертации опубликовано в четырех работах.

Структура и объем ддссертащш

Диссертация состоит но введения, 'четырех глав, заключения и приложения. Содержит 120 страниц текста л список литературы но 96 наименований.

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

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

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

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

В данной главе предлагается алгоритм доступа с разрешением конфликтов поиомерам сташшй. Для'простоты он рассматривается для системы, в которой число станций М является степенью числа 2. Каждая станш имеет номер, двоичное представление которого состоит из 1од2(М) бит. Значения битов, начзшая-с самого старшего, пспольт зуются при разрешении конфликтов. При возникновении конфликта в некотором окне 4 станции, в него вступившие, разбиваются на два под-

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

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

Рассматриваются два модифицированных (1М, 2М) и два немодп-пппроваиных алгоритма (liV, 2JV). В каждой из этпх пар алгоритмы отчаются тем, как оканчивается серия успешных передач от одной ганции. В одном случае окончание серии определяется прослушнваю-ей канал станцией по значению некоторого бита пакета (2N, 2М), а з втором - по отсутствию передачи по каналу (IN, 1М).

В рассматриваемой системе станции объединяются общим каналом, )торый используется для передачи информационных пакетов. На ка-:дую станцию говне поступает дискретный по времени пуассоновскпй эток с интенсивностью А/М пакетов в единицу времени. Пакеты пме-т одинаковую длину, которая принимается за единицу измерения вре-епи. Система синхронная, при этом вся ось времени делится на пн-ерзалы равной длины [t,f + 1), t G Ti} называемые окнами. Здесь и шее используется обозначение Ij — {},] + I,—}.- Станции начинают зредачу своих пакетов только в моменты времени t = 1,2,3,....

Новые пакеты поступают в буфер станции и выбираются пз него в зответствип с дисциплиной FIFO.

В системе имеется обратная связь, посредством которой станции знают о состоянии общего канала. В каждом окне канал может нахо-зться в одном из трех состояний: (У) успешная передача пакета; (П) зободный канал или пустое окно; и (К) конфликт, т.е. одновремен-ая передача двух ппп более пакетов. Обозначим через 9t £ {У, П,К} эстояние канала в окне i. К концу окна t все гулянии и, прослушивая шал, узнают значение 0t. Кратностью конфликта называется число :тутптпших в конфликт пакетов.

Дм описания алгоритма вводится понятие сеанса. Первый сеанс на-анается в момент времени i = 0. Когда он заканчивается, начинается горой сеанс и т.д. Момент окончания сеанса определяется с помощью

меткп. Пусть в ысиент времени t начинается сеанс с номером п. В начале сеанса метка помещаемся 'на первый уровень стека. "Далее'метка движется по "стеку аналогично пакету. Момент времени, когда метка впервые выходит на уровень 0 стека, является моментом окончания сеанса. Длина сеанса с номером V обозначается через г„.

Сташдап отслеживают состояние канала и определяют моменты начала сеансов. Перенумеруем все порядковые сеансы в порядке их наступления числами и € -Гь При передаче пакетов используется блокированный алгоритм. Это означает, что в течение сеанса с номером V получают успешную передачу пакеты, которые возникли на станциях во время сеанса с номером V — 1.

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

ичное представление номера станции N. Последовательность (0...00) соответствует станции с N = 0, последовательность (0...01) - Сталина с N = 1 и т.д. Рассматриваемый алгоритм доступа описывается с помощью целочисленных переменных щ и которые называются. номером позиции и уровнем стека соответственно. Если ¿г = 0, то станция передает первый пакет из буферной очереди. Пусть £; обозначает момент начала некоторого порядкового сеанса. Все станции, на которых- имеются пакеты, производят -установку начальных- значении-п^ = т, = 0. В последующих окнах сеанса значения; щ, Ь1 изменяются в соответствии с инструкциями алгоритмов.

Не модифицированные алгоритмы Ш, 2К Г гц — 1, если 61 = К и X* = О,

пИ1 = \

[ щ во всех остальных случаях.

N.1. Если = 0 и = К, то Х<+1 = и>„(.

■ N.2. Если Ц > 1 и.04 = К, то = Ьг +1.

N.3. ЕслиА, = У, то 11+1 =

N.4. Если — 0 и = 0, то все пакеты переданы и станция замолкает по крайней мере до следующего сеанса..

N.5. Если > 1 и = 0 либо = П, то £1+1 = ¿1 - 1.

Состояние = 0 соответствует концевому окну.

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

"орптмамп 1ЛГ и 2N иногда возникают моменты, когда сташши, передающие пакеты в момент 1, заранее знают, что в следующей момент зременп I +1-произойдет конфликт. Такая ситуация возникает каждый раз, когда (?( = 0, б(_х = К. В случае модифицированного алгоритма :таяцнп не повторяют очевидный конфликт, а сразу пристукают к его разрешению.

Из описания алгоритма видно, что последовательность длин сеансов г„, V £ /ь образует однородную неприводимую апериодическую пепь Маркова. Предполагается, что начальное состояние цепи имеет стационарное распределение. •

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

В работе находится условие эргодичности цепи Маркова т,. Доказательство эргодичности состоит в проверке условия Фостера. При Л < 1 пепь Маркова для т„ имеет стационарное распределение 7г„, п. 6 1\-

Далее исследуется виртуальная задержка передачи пакета. Ее определение дается с помощью дополнительного (пробного) пакета, который. . помещается в некоторый момент Т, Т € [0, оо), на случайно выбранную станцию системы. Задержкой пробного пакета ¿г изливается время, прошедшее от момента Г до момента начата успешной передачи пробного пакета. Средней виртуальной задержкой называется предел • D = йтт-.оз Е6т> если он существует.

Анализ средней задержки выполняется в предположении, что Л < 1 и начальное состояние цепи г„ имеет стационарное распределение.

Выражение для средней задержки получается с помощью теории полумарковского процесса. Задержка 6т состоит нз двух частей. Первая из них ¿1?' - зто время, прошедшее от момента Т до момента окончания текущего порядкового сеанса (время ожидания), вторая часть - это время, прошедшее от момента начала следующего порядкового сеанса до начала успешной передачи пробного пакета (время выхода).

Разбиение сеанса на конфликтную и бесконфликтную составляющие

влечет соответствующее разбиение времени выхода.

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

В конце главы приводятся результаты расчетов средней задержки для систем МД с числом станций М = 2,4,8 и алгоритмами 1N, IM, 2N, IM при различных значениях интенсивности А. Сравнивая значения задержек алгоритма в системах с различным числом станций, приходим к выводу, что задержка монотонно возрастает с увеличением М. При любой фиксированной интенсивности X имеет место естественное соотношение между задержками алгоритмов: Ajv > Diu, D-2N > Дш и D1N > BiN, DlM > D2m- Заметим, что задержки модифицированного и немодифицированного алгоритмов совпадают только в частном случае М = 2. Здесь для примера приводится таблица значений задержек для сети с М = 8.

А I jDxjv DIM d2N Djm

0.1 0.521 0.474 0.255 0.221

0.2 J 1.748 1.556 0.662 0.563

0.3 I 5.102 4.532 1.396 1.266

0.4. 13.169 12.355 2.852 2.366

0.5 J 24.285 23.985 . 5.897 5.035

Основными результатами первой главы являются: построение четырех эффективных алгоритмов МД, которые для разрешения конфликтов испопкзуюг номера станций; нахождение выражения для средней задержки пакета для предлагаемых алгоритмов МД; сравнение алгоритмов по задержке. Материалы первой главы опубликованы в [1,2].

Во второй главе диссертации описывается вариант стек-алгоритма для локальной сети. Находится условие устойчивости построенной системы. Исследуется зависимость скорости передачи алгоритма от параметра несбалансированности генератора случайных чисел.

В работе рассматривается немодпфпцпрованнып стек-алгсрптм, прп котором попавшпе 'в конфликт пакеты с вероятностью р повторяют передачу п с вероятностью (1 — р) откладывают ее. Скорость передачи км функция р ранее исследовалась для базовой модели СМД, в которой длительности конфликтной п успешной передач равны п совпадают с длиной такта (окна) синхронной системы. Скорость алгоритма в басовой модели быстро убывает прп отклонении р от точки р = 1/2, в которой она максимальна. Из этого можно сделать вывод, что генератор случайных чисел, задающий момент повторной передача, должен быть сбалансированным, т.е. иметь равные частоты появления нулей и единиц на своем выходе. Результаты, полученные в данной работе, показывают, что в локальной сетп можно использовать несбалансированный генератор случайных чисел. Падение скорости передачи .при* этом пренебрежимо мало.

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

Исследуется локальная сеть, состоящая из большого числа станций и обшего канала. В сетп имеется синхровзгоащы. Интервал времени [£,4 +1) называется окном . . , • . '

О событиях, пропоошедшлх в канале в течение окна I сещцпп узнают с помощью канала троичной обратной связи. Обозначим через & число пакетов, передающихся в окне В канале в каждом огне происходит одно из трех событий: У - Успешная передача — 1); И - Пустое окно — 0); К - Конфликт > 2). Число пакетов, вступивших в конфликт, называется его кратностью.

Число пакетов, возникших на стаядпях в течение окна t — 1, обозначается через Д. Случайные величины Д независимы и пмеют одинаковое распределение дг(п) = ¿МА — "}> п € ¡о- Поток р1 является потоком без последействия.

В соответствии с принятым масштабом времени пустое окно длится одно огно, успешная передача занимает пеяое число охон. Длина пакета является случайной величиной с распределением вероятностей К{1), I £ и средним V. Конфликтная передача длится несколько окон.

ное предполоасенпе а < V.

Алгоритм доступа таков, что каждая успелшая передача и каждый конфлпктГсопровождается пустым (оно называется концевым) окном.

Действия станцпи, имеющей готовый к передаче пакет, определяются инструкциями алгоритма. Для описания инструкций вводятся переменные 0( - состояние канала в окне Х( - уровень пакета в стеке в момент 4. Если ¡л-1 ф 0, а = 0, то станция в окне t начинает передачу пакета. В случае возникновения конфликта (0; — К) все станции, в него вступавшие, завершают передачу в момент 2 + а.

1. Если и=0, € {У,К}, то = 0.

2. Если Ьх — 0, 0(_1 = К, в( = П, то = 0 с вероятностью р и ¿и-1 = 1 с вероятностью 1 — р.

3. Если Ьг = 0, = У, <Эг = П, то пакет покидает систему.

4. Если It > 1, 0(-1 = П, 0* € {У,К}, то = £4 + 1.

5. Есяп > 1, 0(_! = 0г е {У,К}, то =

6. Если и > 1, 0(_1 ,= К, 04 = П, го. £(41 =1^1.

Т. Еспп и > 1, ©¡_, ф К, ©4 = П, то Ьш = - 1.

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

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

После приведения подобных членов уравнения системы переписывал ^ ются в обобщенном виде.

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

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

Далее доказывается единственность решения. Для этого вводится множество Т - множество всех вещественных последовательностей X = {е1, к € Го}, и рассматривается класс функппп

X, = {Х6Т : »«р*,,^ < оо}.

Показывается, что решение линейной системы уравнений единствен- ■ но в классе "Г}. При доказательстве используются результаты теории бесконечных систем линейных уравнений.

"Условие существования барьера позволило численно получить зависимость А^ - граяппы снизу для скорости передачи алгоритма -от вероятности р, а также исследовать влияние параметров а и V на скорость передачи алгорима. Полученные данные позволили рассчитать допустимый диапазон несбалансированности генератора случайных чисел. Здесь предлагается таблица, в которой параметр а = 5, средняя длина пакета принимает в первом случае значение V = 10, а во втором V ~ 100.

V V = 10 г; = 100

0.1 0.4700 - - 0.8682-

0.2 0.5010 0.9196

0.3 0.6226 0.9342

0.4 0.6416 0.9401

0.5 0.6474 0.9417

Основными результатами второй глады являются: исследование се- . тп связи, управляемой ^модифицированным не блокированным стек-алгоритмом с несбалансированным генератором случайных чисел; доказательство существования и единственности решения бесконечной линейной системы уравнений для средних длин сеансов заданной кратности; изучение зависимости скорости передачи от вероятности р, которая является показателем степени несбалансированности генератора случайных чисел. Материалы второй главы опубликованы в [3],[4] и [5].

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

При описании алгоритма дробления используются понятия временного сеанса (B-сеанса) п задолженности алгоритма. В начале В-сеанса (или простого сеалса) ось времени [0,оо) разбивается на три интервала: [0, £ — и), [£ — и, i) и [i,oo), где t обозначает момент начала сеанса. Интервал [0,f — и) является просмотренной частью оси времени. Это означает, что все пакеты, моменты вознтшоветтпя которых принадлежат [0, t—и), успешно переданы к моменту времени t. Интервал [t—u, t) содержит уже возникшие и еще не переданные пакеты. Величина -к называется задолженностью алгоритма. В окне [f, t + 1) передаются все пакеты с интервала [i — и, t - и + у), где 7 — min(u,s), константа s -параметр алгоритма. Интервал [t — u,i — и + 7) называется начальным интервалом сеанса, а число пакетов на нем - кратностью сеанса. Если кратность меньше двух, то сеанс состоит из одного окна. Сеанс кратности 2 жлп более длится случайное число окон л заканчивается посте появления в канале двух: идущих подряд окон с успешной передачей. Сеанс кратности 0 называется пустым сеансом.

Будем считать, что моменты возникновения пакетов образуют пуас-соновсыш процесс с интенсивностью X.

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

Совокупность пакетов, получающих успешную передачу в течение B-сеанса о ненулевой кратностью, называется пакетным сеансом (П-сеансом), соответствующим атому B-сеансу. Перенумеруем все П-сеавсы в порядке вознтлаювешш соответствующих В-сеалсов. Обозначим через число пакетов в П-сеансе с номером гг, а через %п - задолженность алгоритма в начале пустого B-сеанса с номером п. Пара случайных велпчш (Хг»>£п) образует двумерную цепь Маркова. Условные вероятности состоявнй этой цепи удовлетворяют равенству

•F4X«+1 = ».бн-i = 1\Хп = ^ = s) = P'ibHi = = v}Pr{xn+1 = V\Xn = u,£n = s}.

Перенумеруем все пакеты в порядке их возникновения числами та £ Je, где Ij = {j, j 4-1,...}. Пусть 17(m) обозначает задержку пакета с номером то, т.е. время, прошедшее с момента возникновения пакета до момента окончания его успешной передачи. Случайный процесс т](тп), ассоциированный с двумерной цепью Маркова (Хп,£п)> принадлежит к

классу случайных процессов, который является обобщением процесса регенерации п полумарковского процесса.

Последовательность Хп является вложенной цепью Маркова с пере- • ходивши вероятностями = Рг{х„+1 = •и|хп = ■"}•

Обозначим через тгц стационарную вероятность цепи х„, где и - величина задолженности, и Е [1,оо).

Величину ж назовем убылью задолженности за сеанс (ж = и — и). Для нахождения переходной вероятности цепи х* введем следующие условные вероятности:

р7(х\к) - условная вероятность убыли быть равной х при условии, что на интервале длиной 7 находится к пакетов;

р7(х) - это вероятность того, что убыль будет равна г. Для вероятностей р-,{р\к) выписывается рекуррентное уравнение. Вероятность р7(х) получается усреднением ру(х\к) по числу пакетов на интервале 7.

Переходные вероятности вложенной цепи Маркова для Хп удовлетворяют следующим равенствам:

« = 1, Ри,1 - Ер7(г) д„(»_г)(0), х<а-1,

V > 1, 34» = - V - гв + г)£(0)(1 - ?7(0)),

г=0 . ■

где а{у) = у~-\-'тах{т : т < (у — 1)/(« — 1)} для любого у >' 1,'д7(0) -вероятность того, что на интервале у нет пакетов.

Стационарные вероятности тги являются решением системы уравнений:

ЯЦ = X! £ 7ГЯ = 1,

чей че(г

где и - множество значений задолженности.

Далее вводится в рассмотрение средняя задержка'пакета в системе СМД с алгоритмом дробления. Средняя'задержка определяется как предел Б = Итт-,Х1'Ет){т),

где Е обозначает математическое ожидание.

Для вычисления I) использовались свойства случайного процесса, который является обобщением полумарковского процесса и процесса регенерации.

В работе формулируется следующая теорема.

Теорема. В стационарном режиме средняя задержка пакета дается выражением

х>= Е ^ЕОы/Е£п,

где Е£„ - математическое ожидание числа пакетов, переданных в сеансе, ЕПи - условное математическое ожидание суммы задержек пакетов, переданных в сеансе, при условия, что задолжность в начале этого сеанса равна и.

Чтобы выписать выражение для ЕГ1и, введем следующие величины:

.¡V - число пакетов, успешно переданных в течение сеанса; N

Ф = £ где у,- - интервал времени от момента возникновения г-го

пакета до конца исходного просматриваемого интервала; я

ш = Еч, где ш; - время, прошедшее от начала сеанса до момента *=1

окончания успешной передачи ¿-го пакета.

Пусть Аи обозначает событие { исходный интервал имеет длину у }, событие { на исходном интервале находится к пакетов }. В работе получены рекуррентные соотношения, которые позволяют вычислить условные средние величины С^, Щф\А*, С*] и Е[ш]Аи, С*]. По-

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

Е0„ = {и - т)Е[ЛГ|Аи] + Е{ф\А,] + Щш\Аи].

В конце главы приводятся результаты расчетов средней задержки в зависимости от интенсивности входного потока. Материалы третьей части опубликованы в [6].

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

Для рассматриваемого алгоритма находится скорость успешной

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

Прп описании алгоритма предполагается, что сеть спггап состоит по бесконечного числа станции и общего канала связи. Пакеты, возникающие на станциях, образуют иуассоновскпй поток с интенсивностью А. Предполагается, что на станции в любой момент времени может находиться не более одного пакета. Время передачи пакета принимается за единицу времени. В системе имеется спнхронизаппя. ' Интервал времени [i, i + 1) называется окном t.

Количество пакетов, возникающих на станциях в течение окна i, является случайной величиной. Обозначим ее через /3t) t 6 Д. Величины pt независимы и имеют одинаковое распределение Pr{pt ~ j] = g^j) со средним значением Л.

В каждом окне канал может находиться в одном из трех состояний: успешная передача (У); пустое окно (П); конфликт (К). В системе имеется обратная связь. В конце каждого окна сташпш узнают, какое событие, обозначим его через ©¡, произошло в канале в момент i.

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

Все уровни стека перенумерованы числами 0,1,..., d. В работе рассматривается случай d > 3. Случай с d= 2 требует особого описания. С практической точки зрения вариант стек-алгоритма с двухуровневым стеком не представляет особого интереса.

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

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

Сташпш, участвующие в передаче пакетов, отслеживают состояние канала п положение пакета в стеке в каждый момент времени i с помощью целочисленной переменной Lt, которая называется .уровнем пакета в стеке в момент времени t. Пусть it- - начало некоторого сеанса. В момент U все станлшг устанавливают Lt{ = 0. Датее в зависимости от

состояния канала значение поменяется в соответствии со сяедуюшп-"мп пнструкпцямп

1. Если с* - 1 > > 1, ©( = П или Л - 1 > ¿( > 1, = У, то ¿«+1 = 1^—1;

2. Если = 0 н 04 = У, то пакет передается успешно и покидает систему;

3. Если <1 - 2 > и > 1 и 0, = К, то 11+1 = ¿<4 1;

4. Если ¿4 — а — 1 п = К, то ¿4+] = й, и пакет теряется;

5. Еслп = 0 и 6( = К, то с вероятностью р = 1/2 пакет остается на нулевом уровне Ь1+1 = 0, а с вероятностью р = 1/2 оп переходит на уровень 1 = 1.

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

Прп дальнейшем: анализе алгоритма вводпгся кратность порядкового сеанса п £ 1у. Кратности порядковых сеансов образуют однородную непршзоддмую апериодическую цепь Маркова с-переходнымн вероятностями р^,. = Рг{^Т1+1 ~т | = к}.

Предполагается, что цепь Маркова для (п имеет стационарное распределение -л*., к £ II.

В работе исследуется средняя задержка пакета. Напомним, чио задержкой пакета называется время, прошедшее с момента возникновения пакета до момента начала его успешной передачи. Согласно описанию алгоритма часть поступающих пакетов теряется. Усреднение задержки, которая является случайной величиной, проводится по тем пакетам, которые получают успешную передачу. Анализ задержки пакетов, аналогично как и в третьей главе диссертации, основывается на применении результатов, полученных для лроцеса, который является обобщением полумарковского процесса я процесса регенерации. Так же, как и в третьей главе, перенумеруем все пакеты, получающие успешную передачу. Через г]{г) обозначается задержка 1-го паде-

та. Задержку пакета с номером г удобно представить в виде суммы ' 77(1) = 61 (г) 4- 62(1), где ¿1(1)' - время ожидания - время между моментом возникновения пакета г и моментом его первой передачи; а 62(г) - время выхода - время между моментом первой передачи пакета г и началом его успешной передачи.

Средней задержкой пакета в системе СМД со стек-алгоритмом называется предел

В ~ Ит^глф) = А +■ 1>2, где Д = гил;-,«^), £>2 = Ит^бгф.

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

получивших успешную передачу за сеанс при условии, что кратность этого сеанса равна к. Для Д(/г) выписывается равенство, где условные величины, составляющие ото выражение, усредняются по длине предшествующего сеанса и по кратности текущег«? сеанса. Для Д{к) с помощью инструкций алгоритма выписываются рекуррентные соотношения. В выражения для Д и Д входят величины Л^ - условное среднее число пакетов, получивших успешную передачу за сеанс при условии, что кратность этого сеанса равна к.

Численные расчеты выполнялись для средней задержки и скорости передачи алгоритма. Значения задержки и скорости передачи как функции А при разных значениях й приведены в таблице (для примера взяты лишь значения для Б и N при А < 0.4).

=3 ¿=6 6 = 8

А N В N Б N В

0.1 0.0999 0.8875 0.0999 0.9074 0.0999 0.9086

0.2 0.1987 1.6202 0.1987 1.6202 0.1999 1.8924

1 0.3 0.2891 3.0790 0.2978 5.7713 0.2996 6.8683

0.4 0.3506 5.5767 0.3549 26.3117 0.35 83.49

Основными результатами четвертой главы являются: исследование алгоритма СМД с конечным стеком и потерей пакетов; получение выражений для средней задержки п скорости передачи алгоритма. Материалы четвертой главы диссертации опубликованы в [7].

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

В приложении содержатся акты о внедрении результатов диссертации.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

1. В диссертации построен эффективный алгоритм МД, позволяющий разрешать конфликты с помощью номеров станций.

2. Найдены условия устойчивости предлагаемых алгоритмов.

3. Найдена и исследована средняя виртуальная задержка передачи пакета в системе МД.

4. Предложен вариант стеж-алгоритма для локальной сети.

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

6. Исследовано влияние изменения длины пакета и длины конфликтного окна на" скорость передачи в' локальлой'сети. '

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

8. Описал стек-алгоритм СМД с конечным стеком и потерей пакетов.

9. Получены выражения для скорости передачи и средней задержки алгоритма СМД с конечным стеком и потерей пакетов.

По теме диссертации опубликованы следующие работы:

1. Цыбашв B.C., Федорцов С.П., Рылеева H.A. Множественный доступ с разрешением конфликтов с помощью номеров станций. -ППИ, Т.28, 3,1992, с.27-39.

2. Рылеева H.A. Эффективный алгоритм, доступа станций в какал, связи. - Труды XXVI Конференции молодых ученых ИШШ АН. СССР, ■ М., 1991, с.11-15.

3. Федорцов С.П., Рылеева H.A. Скорость передачи в локальной

сети со стек-алгоритмом при использовании несбалансированного генератора случайных ■чисел. - ППИ, Т.ЗО, 2, 1994, с. 76-88.

4. Fedortsov S., Ryleeva N. Random. Access Algorithm with Unsymmetrical Splitting for Local Area Network Environment. - Proc. of IWIP-94, Moscow, July 3-8, 1994, pp.33-34.

5. Федорцов С.П., Рылеева H.A. Скорость передачи в локальной сети со стек-алгоритмом при использовании несбалансированного генератора случайных ■чисел. - Труды XXVIII Ковфер. молодых ученых ИППИ РАН, М. 1993, с. 15-18.

G. Рылеева H.A., Федорцов С.П. Метод расчета задержки алгоритма дроблена. - Труды XXVII Конфер. молодых ученых ИППИ РАН, М. 1992, с.24-27.

7. Федорцов С.П., Рылеева H.A. Алгоритм СМД с конечным стеком'' и потерей пакетов. - ППИ, Т.31, 1, 1995.