Тема 6 (часть 2) (Материалы лекций)

11.3. Алгоритмы доступа 11.3.1. А1 ОНА В 1971 году Гавайский университет разработал и начал использовать систему АЬОНА. Спутник применялся для связи нескольких университетских компьютеров посредством протокола произвольного доступа 13-7). Принцип работы системы чрезвычайно прост и включает в себя следующие режимы.

1. Резким передачи. Пользователи передают данные в любой момент времени, кодируя свои сообщения с помощью кода обнаружения ошибок. 2. Режим ожидания. После передачи сообщения пользователь ожидает от приемника подтверждения (ас)азот1едяшепг — АСК) приема данных. Иногда передачи различных пользователей перекрываются во времени, что приводит к возникновению ошибок в каждой передаче. В таком случае сообщения пользователей называют конфликтующими. Ошибки обнаруживаются, после чего пользователи получают отрицательное подтверждение приема (пейабче ас1шов4едагпепг — МАК). 3. Режим повторной передачи. После получения сообщения МАК информация передается повторно.

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

Вследствие конфликтных ситуаций некоторые из сообщений не будут получены либо будут отклонены. Следовательно, общую частоту поступления сообщений Х, можно определить как сумму частоты успешного поступления сообщений Х и частоты отклонения данных Х,. Х, =2,+Х,. (11,16) Обозначим размер сообщения или пакета через Ь бит. Тогда средний объем успешно переданных данных, иначе говоря пропускную способность канала, р', можно представить следующим образом: р'=ЬХ бит/с. (11. 17) Также можно определить полный информационный обмен канапа, О'.

С'=ЬХ, бит/с (11.18) Если считать максимальную скорость передачи битов (емкость канала) равной й бит/с, нормированную пропускную способность можно записать следующим образом: (11.19) 697 1 1.3. Алгооитмы достчпа Также можем записать нормированный полный нн4ормационный обмен.

ЬА, гг= — ' й (11.20) Ь г = — секунд(пакет. К (11.21) Подставляя уравнение (11.21) в (11.19) и (11.20), можем записать следующее: р=~т (11.22) и б= 1,т. (11.23) Пользователь может успешно передавать данные, если ни один из пользователей не начал передачу в течение предЫдущих т секунд или не начнет ее в течение следующих т секунд. В противном случае возникнет конфликт.

Поэтому для успешной передачи каждого сообщения требуется 2т секунд. Статистика получения сообщений независимыми пользователями системы связи часто моделируется пуассоновским процессом. Вероятность поступления К новых сообщений в течение т секунд описывается распределением Пуассона [8) )х -л. Р(К)= К>0, К! (11.24) где Х вЂ” средняя часппа поступления сообщений.

Поскольку в системе АЕОНА пользователи передают данные независимо друг от друга, приведенное выше выражение может быть использовано для вычисления вероятности события, когда в течение временного интервала 2т будет получено точно К= 0 других сообщений. Таким образом, получаем Р, — вероятность успешной (бесконфликтной) передачи пользовательского сообщения. Для вычисления Р, предположим, что информационный обмен описывается распределением Пуассона, после чего подставим в уравнение (11.24) значения )ь и 2т. Р, = Р(К = 0) = = е (га,) е (11.25) В уравнении (11.1б) общая частота поступления сообщений Х, определялась как сумма частоты успешного поступления сообщений Х и частоты отклонения данных Х,.

Тогда, по определению, вероятность успешного получения пакета может быть выражена в следующем виде: (11.26) гвввв з1 Чппомвамва и множественный лостчн Нормированная пропускная способность р выражает пропускную способность как часть (0 < р < 1) емкости канала. Нормированный полный информационный обмен б выражает полный информационный обмен как часть (О < 6 < ) емкости канала. Следует отметить, что 6 может иметь значения, превышающие 1. Время передачи пакета может быть выражено в следующем виде: Объединяя уравнения (11.25) и (11.2б), получаем следующее: е-за, ! (11.27) Подставив в формулу (11.27) выражения (11.22) и (11.23), можно записать р = Се (11.28) Уравнение (11.28) связывает нормированную пропускную способность р и нормированный полный информационный обмен С при использовании канала системы АЬОНА.

График данной зависимости отмечен на рис. 11.20 как "чистый алгоритм А1.0НА". По мере роста сг увеличивается и р до тех пор, пока большое количество конфликтных ситуаций не приведет к снижению пропускной способности. Максимум р, равный 1!2е = 0,18, достигается при 0 = 0,5. Таким образом, в канале с чистым алгоритмом АЬОНА может быть использовано лишь 18% ресурса связи.

Простота управления в данном алгоритме достигается за счет снижения емкости канала (7, 9). .е 1 оа 3 о с о 8 о,е й. о с Огй и о м а 0,2 о о,о 'о,оч О,1 О,б 1 1О Нормированный полный информационный обмен, и Рис. 11.20. Пропускам способност~ каналов АЕОНА (зависимость дали успешных передач от их общего числа) 11.3.2.

АЬОНА с выделением временных интервалов Чистый ацоритм АЬОНА можно улучшить, если ввести небольшую координацию между станциями. Примером подобного алгоритма является система А1.0НА с выделением временных интервалов (з!опед А1.ОНА — Б-АЬОНА). Всем станциям передается последовательносп синхронизируюших импульсов. Как и в случае чистой системы А1.ОНА, размер пакетов является постоянным. Сообщения могут передаваться только в течение временного интервала между синхронизируюшими импульсами, а начало передачи пакета обязательно должно совпадать с началом интервала.

Внесение таких незначительных дополнений в алгоритм А1.ОНА позволяет вдвое снизить число конфликтных ситуаций, поскольку теперь конфликтовать могут только сообщения, передаваемые в течение одного времен- 699 11.3. Алгоритмы доступа и. мил ного интервала. Можно показать (9, 1О), что при использовании алгоритма Б-АЬОНА сокращение кон4ликтного лромемсутка с 2т до т дает следующее соотношение между нормиро н ванной пропускной способностью р и нормированным полным информационным обменом С. (11.29) р=Се График зависимости (11.29) приведен на рис.

11.20, где он отмечен как "система А1.0НА с вьшелением временных интервалов". В данном случае максимальное значение р равно 11е = 0,37, что в два раза больше аналогичного показателя чистого алгоритма А1.0НА Режим повторной передачи системы Б-АЬОНА отличается от соответствующего режима чистого алгоритма тем, что при получении пользователем отрицательного подтверждения (МАК) слелуюшая попытка производится после случайной паузы, длительность которой кратна протяженности временного интервала.

Работа алгоритма В-А1.0НА представлена на рис. 11.21. После успешной передачи пакета данных пользователь к получает со спутника подтверждение о получении. Также показаны пользователи и и л, которые одновременно начинают передачу пакетов, что приводит к конфликту, и спутник передает сигнал )ь)АК обоим пользователям. Для определения времени повторной передачи обе станции исполыуют генератор случайных чисел. Далее на рисунке показано возможное продолжение: повторная передача пользователями и и н после случайно выбранной паузы. Разумеется, существует вероятность повторения конфликтной ситуации сразу же после конфликта.

В этом случае после очередной случайной паузы будет предпринята еше одна попытка повторной передачи. Пользоввтельт Пользователь К Псльзсавтвлл т,п Польшалтвльп Рис. 11.21. Система лроизввльнога доступа: работа алгоритма АЕОНА с выделением арсменнык интервалов Пример 11.1. Процесс Пуассона Пусть передачу и повторную передачу пакетов мо:кно описать как пузссоновский процесс. Определите вероятность возникновения в процессе передачи пакета конфликта с вще одним лользователеи (используетсл алгоритм 3-АЬОНА).

Полная частота передачи пакетов равна )ь = 10 пакетов в секунду; длительность пакета т = 10 мс. Решение .„1 К -тЛ, Р(К=1)=~ =(10х0,01) е ел =0,1е ' =0,09 К! к=! 700 Глава 11. Уплотнение и множественный доступ 11.3.3. Алгоритм АЬОНА с использованием резервирования Работа систем А1.0НА была значительно улучшена в результате введения резервирования (гезегтаг)оп-АЬОНА — К-АЬОНА) [11). Системы К-АЬОНА могут использоваться в двух основных режимах.

Розням без резервирования гсостоянис никон) 1. Выделенный интервал времени разбивается на небольшие подынтервалы резервирования. 2. Эти подынтервалы используются для резервирования интервалов передачи сообщений. 3. После запроса резервирования пользователь ожидает подтверждения и распределения интервалов. Рознит с резервированием 1. Если не выполняется резервирование, временной интервал разбивается на М+ 1 интервалов.

2. Первые М интервалов используются для передачи сообщений. 3. Последний интервал разбивается на подынтервалы, которые используются для резервирования или передачи запросов. 4. Пользователи передают пакеты данных только в выделенных им элементах М интервалов. Рассмотрим пример использования схемы К-А1.0НА, представленный на рис. 11.22. В состоянии покоя время (с целью резервирования) разбивается на небольшие подынтервалы. После резервирования система конфигурируется так, что после М= 5 интервалов передачи сообщений следуют У= б подынтервалов резервирования; далее эта структура повторяется.