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

РГ6 ОА .

I о ^бсСИЙСКАЯ АКАДЕМИЯ НАУК ИНСТИТУТ ПРОБЛЕМ ПЕРЕДАЧИ ИНФОРМАЦИИ ЮСКОВСКИЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ

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

ПРИВАЛОВ АЛЕКСАНДР ЮРЬЕВИЧ

УДК 621.394.74

УПРАВЛЕНИЕ МНОЖЕСТВЕННЫМ ДОСТУПОМ ПРИ ПЕРЕДАЧЕ ПАКЕТОВ В СЕТЯХ СВЯЗИ специальность 05.13.01 п Управление в технических системах

АВТОРЕФЕРАТ

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

МОСКВА 1993

Работа выполнена в Институте проблем передачи информации

Российской академии наук.

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

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

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

профессор П.П.Бочаров кандидат технических наук Н.Я.Паршенков

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

(г.Москва)

Защита состоится "_" __ 1993 г. в _часов на

заседании специализированного совета Д.003.29.01 в Институте проблем передачи информации РАН по адресу 101447, Москва, ГСП-4, ул. Ермоловой, .19.

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

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

Ученый секретарь специализированного совета доктор технических наук • С.Н.Степанов

ОБШАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы.

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

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

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

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

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

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

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

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

ются две противоположно-направленные шины, вместе *

образующие дуальную шину.

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

1.Исследование работы стек-алгоритма случайного множественного доступа в канале с К-конфликтом. Канал с ^конфликтом может служить моделью канала с кодовым разделением или расширением спектра.

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

3.Исследование работы-протокола В<ЗБВ — "дуальная шина с распределенной очередью", предназначенного для оптических сетей множественного доступа с дуальной шиной.

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

1. Найдена скорость передачи стек-алгоритма с Спичным разбросом пакетов в канале с М-конфликтом. Результаты расчетов позволили для ряда значений Г*/ найти

максимизирующее скорость передачи.

Для N=2 оптимальное <3=3, при этом А0 = 0.4016,* что согласуется с ранее известными результатами; для N=3 оптимальное <3=4, Цри этом А0 = 0.8784; для N=4 оптимальное <3=5, при этом Ао = 1.4084; для N=5 оптимальное <3=5, при этом А0 = 1.979; для N=6 оптимальное <3=6, при этом А0 = 2.579. Похоже, что при 5 оптимальное значение <3 есть N.

2. Найдена зависимость средней длины сеанса стек-алгоритма с <3-ичным разбросом пакетов от интенсивно- • сти входного потока в канале с М-конфликтом.

3. Для канала с И-конфликтом и ошибками, найдены две нижние границы ;'для средней задержки передачи пакета в таком канале. Проведены численные расчеты при N — 2 для различных вероятностей ошибок.

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

4. Получены достаточные условия устойчивой работы станции, подчиняющейся протоколу ОС^ОВ для двух модификаций протокола.

5. Найдена зависимость средней задержки передачи пакета от интенсивности входного потока в сети с протоколом ВС^БВ. Рассмотрены две модификации протокола. Проведены численные расчеты для сетей с разным количеством станций. Эти результаты показывают, что за- ® держка является приемлемо малой в широком диапазоне интенсивностей, примерно до 1.4

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

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

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

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

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

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

к

лом

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

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

Результаты работы используются в Институте проблем передачи информации Российской акдемии наук. Практическая значимость работы подтверждена актом внедрения. '

Апробация работы.

Результаты диссертации докладывались на научных конференциях Московского физико-технического института (1990, 1991, 1992 )', на 2-ой Всесоюзной конференции по информационным системам множественного доступа (г. Минск, 1991), на конфереции молодых ученых ИППИ РАН (1992 ). •

Публикациии.

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

Структура диссертации.'

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

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

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

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

Канал с ЛГ-конфликтом является обобщением обычного канала случайного множественного доступа (СМД). В канале с /^-конфликтом конфликт возникает при одновременной передаче N или более пакетов, где N > 1 - заданное целое число., Если передается менее N пакетов одновременно, то все они передаются успешно. Таким образом, обычный канал СМД есть частный случай канала с ЛГ-конфликтом при N—2.

Этот канал совместно используется бесконечным числом пользователей для передачи информационных пакетов. Суммарный поток новых пакетов, возникающий на всех станциях, является пуассоновским с интенсивностью Л. Длины пакетов одинаковы и принимаются за единицу. Система синхронная, то есть время в системе разделено на окна + 1), t £ /о, длина которых равна длине пакета, и станции могут начинать передачу только в начале окна (здесь и далее I, = {3,3 +-1,—}).

О событиях, происшедших в канале в течении окна {¿,4 4- 1) станции узнают с помощью безошибочного канала троичной обратной связи, значение которой обозначается 64+1:

= П означает, что в канале в окне 1) не

передавалось ни одного пакета;

— У означает, что передавалось менее N пакетов и все они успешно переданы;

= К означает, что одновременно передавалось

>

N или более пакетов и был конфликт.

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

В стек-алгоритме каждому пакету в начале каждого окна [£, £+1) присваивается целое неотрицательное число Ьи называемое уровнем пакета в стеке. Пакет передается по каналу в окне [<,£ + 1) тогда и только тогда, когда его уровень = 0. В рассматриваемом в работе стек-алгоритме меняется согласно следующим инструкциям:

1. Для пакета, возникшего в окне [Ь — 1,4), Ь% — 0.

2. Если £г(_ 1 = 0 и = У, то в момент Ь пакет покидает систему, как переданный успешно.

3. Если = 0 и — К, то с равными вероятностями р = 1/ф принимает значения 0,1,..., — 1..

4. Если Ьг-1 > 1 и ф /<", то Ьг = £<-1 — 1.

5. Если > 1 и в1 = К, то Ьг = Ьг-г + Я - 1.

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

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

После описания модели в работе формулируется определение скорости передачи стек-алгоритма, как такого А0, что при А < Л0 все средние длины сеансов меньше бесконечности, а при Л > Ао средние длины сеансов для кратностей к > N бесконечны.

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

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

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

В процессе интегрирования возникает сгстема из N -уравнений для N неизвестных констант интегрирования, . которые одновр' менно являются значениями Сг(г) и ее ноиэводных. при г — А.

Коэффициенты данной системы неявно зависят от А, причем так, что для А меньших некоторого А0 система имеет единственное конечное неотрицательное решение, а при А > А0 не имеет такового. При А = А0 главный детермииат системы равен нулю.

В работе получен результат о том, что Ао = А0 и,

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

Средняя длина сеанса получается, как первая компонента решения системы из N уравнений, то есть СУ(А) -это следует из определения экспоненциальной производящей функции.

В конце главы приводятся результаты расчетов скорости передачи для различных N и Q, а также зависимости средней длины, сеанса от А для различных N и ф. Сравнивал при заданном N скорости передачи для различных С}, находится оптимальное С} для каждого N.

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

Модель системы и канала аналогичны рассматриваемым в первой главе, за исключением того, что обратная связь считается Л^-ичной, то есть по обратной связи могут передаваться сигналы: 4

вг — 0 - пустое окно;

— *> 1 < г < N - успешная передача г пакетов;

= N - конфликт при одновременной передаче N или более пакетов.

Кроме того, канал обратной связи не является безошибочным, в результате происходящих в нем ошибок станции принимают сигнал который может не совпадать с вt■ В работе считается, что случайная величина не зависит'ни от чего, кроме при этом

Рг{е, = ЛГ"| 6(t — = N,e(t — 1)} = = Pr{e« = N | = W} = irN = 1

Pv{et = N\6(t~ 1)A = i,e(t - 1)} = = Pr{£t = N\et = i} = iri

■ a

Pr{£i = i | é>(t - 1), 0t = t, £(t - 1)} =

= Pr{£< = » | = »} = 1 - 7Г<

a другие типы, Ошибок в канале обратной связи не происходят.

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

d > A-1Z.

где d - задержка передачи пакета, L - среднее число пакетов в системе.

Этот результат является обобщением неравенства Литтла.

В работе рассматриваются алгоритмы СМД, удовлетворяющие двум условиям:

первое состоит в том, что с вероятностью единица

. L > lim ELt

i—оо

где Lt — число пакетов в системе в момент t:

а второе в том, что

lim EL? < oo

t-> OO 4

Эти условия выполняются для всех известных алгоритмов СМД.

С помощью первого условия получено следующее неравенство для задержки:

d > Л-1 lim ЕLt

<—»оо .

Далее эта глава посвящена оценке Пт^«,X*. После получения пекоторых вспомогательных результатов в рассмотрение вводится случайная величина

Ъ = X(t - mesD«) 4- qLt

. где Dt - просмотренное за t +1 окно множество,, q - некоторое число.

Доказывается, что для jt справедливо неравенство

BLt > (1 + ?)_1E7t

и производится оценка E7¿.

Таким образом находится первая граница для средней задержки. •

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

■ ч

at = giA(mesI?t — mesDt+i + 1) + — Lt),

где qi и - конечные действительные Зисла.

Используя Свойства этой случайней величины, длл Е71 , строится другая оценка, применение которой дает вторую нижнюю границу для средней задержки.

В диссертации даны результаты расчетов обеих границ для случал N = 2 для различных наборов тгЗдесь для примера приведем таблицу значений для обеих границ для Случал 7г0 = 0.1, 7Гх =>0,3:

А 0.1 0.2 0.3 0.35 0.4

di 0.388 0.626 1.347 2.542 9.429

d2 0.732 1.192 2.361 5.050 21.938

Третья глава посвящена исследованию двух вариантов протокола DQDB ( distributed queue dual bus - двойная шина с распределенной очередью ). Один из этих протоколов принят в качестве стандарта IEEE 802-6 для т.п. MAN ( metropolian area networks — городских сетей связи ). Его мы будем называть стандартным протоколом, а другой протокол будем называть вариантом протокола.

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

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

одновременно находится сотни пакетов.

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

Для удобства изложения рассматривается передача в одном направлении, которое называется прямым. Противоположное направление называется рбратным. Таким образом, рассматривается передача пакетов в прямом и передача запросов в обратном направлении.

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

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

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

Для варианта протокола, значение виртуального

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

После описания протоколов в диссертации строится модель станции, подчиняющейся какому-либо из этих протоколов. А именно: считается, что'поток транзитных лакетов мимо станции по прямой шине является бернул-лиевским с интенсивностью а, поток запросов по обратной шине — бернуллиевским с интенсивностью /?, поток новых пакетов, приходящих на станцию для передачи -пуассомовским с интенсивностью А, и все потоки считаются независимыми.

Станция имеет неограниченный буфер, так что новые пакеты не теряются.

После этого вводится последовательность 'fc, k,tk € /о, в которую входят все моменты окончания окон, в которых на станции не было пакетов для передачи, и все моменты окончания передачи пакета.

Далее в работе получены результаты о т^м, что для такой модели последовательность значений пары где v — длина очзреди в буфере станции, (i - значение виртуального счетчика, взятых в моменты tk, к 6 /о, образуют двумерную марковскую цепь -у*. Для обоих вариантов протокола выписываются переходные вероятности цепи 7к-

После этого методом функций Ляпунова находится необходимое условие существованич стационарного распределения ук. Для обоих протоколов оно имеет вид

а + р + А < 1.

Далее определяется полумарковский процесс, для которого является вложенной цепью, а ¿¿+1 — - временем жизни.

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

Далее, в работе предложен метод перехода от модели одной станции к модели сети в целом. Считается, что на каждую из N станций сети приходит пуа.ссоповский поток новых пакетов с интенсивностью Хо/Ы. Каждый пакет с равной вероятностью может быть адресован одной из других N — 1 станций.

Исходя из этой модели, по номеру станции на прямой шине (нумерация начинается с начала шины) вычисляются параметры а, ¡3 и А. Численные расчеты, хорошо согласующиеся с результатами других исследователей, демонстрируют "несправедливость" протокола, т. е. зависимость средней задержки от положения стг.д-ции на шине.

• Ао 0.2 0.6 1.0 1.4 1.8

Е<5х • 1.061 1.248 1.627 2.80 6.22

Е<53 1.117 1.541 2.881 9.66 49.6

Для примера Приведем таблицу значений средпей задержки для двух рассматриваемых протоколов для стан-„ ции номер 3 в сети из 10 ст^лций (Ао - суммарная ннтен-' сивность входного потока новых пакетов на все стапции т. е. нагрузка сети).

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

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

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

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

Основная часть содержания диссертации отражена в следующих публикациях:

1. Иыбаков B.C., Привалов А.Ю. Сток-алгоритм в канале с N-конфликтом. -Вторая всесоюзная конференция по информационным системам множественного доступа. Тез&сы докладов. Часть 2, с.104-108. Минск, 1991г.

2. Иыбаков B.C., Привалов А.Ю. Скорость передачи

стек-алгоритма в канале с N-конфликтоц. -Проблемы передачи информации, 1992, т.28, в.2, с.78-85.

3. Привалов А.Ю. Задержка передачи пакетов в системе СМД с N-конфликтамй и ошибками.- -Труды 27-ой конференции молодых ученых ИППИ РАН. с.32-35.

4. Цыбаков Б.С., Привалов А.Ю. Нижняя граница для задержки в системе СМД с N-конфликтами и ошибками. -Проблемы передачи информации, 1992, т.28, в.4, с.69-85.

ЦФТи 3/Y* уАз2 muf, {OOacj