Принципы случайного доступа
Двумя основными способами доступа к общей среде передачи являются управляемый доступ с применением опроса и случайный доступ. В свою очередь существуют различные типы стратегий случайного доступа.
Методы случайного доступа полностью децентрализованы. Пользователь может передавать когда угодно, лишь с незначительными ограничениями, зависящими от метода доступа.
Из-за случайности моментов времени, в которые пользователи могут решить начать передачу, независимо от метода не исключена возможность того, что два или несколько пользователей могут выйти на связь в пересекающиеся промежутки времени. Это приводит к столкновениям (коллизиям), которые сначала должны быть распознаны, а затем разрешены. При увеличении нагрузки увеличивается и вероятность коллизий, что приводит к возможной неустойчивости работы рассматриваемых механизмов.
В результате производительность ограничивается некоторым максимальным значением, меньшим пропускной способности канала, и это значение в каждом случае зависит от первоначального механизма доступа и алгоритма разрешения коллизий.
Сначала методы случайного доступа были предложены для случаев, когда большое число пользователей пытаются довольно редко передать пачки сообщений или, когда друг с другом связываются небольшое число ЭВМ. Но применимо к производственным процессам, которые требуют строгого управления задержкой доступа, более предпочтителен управляемый доступ. Рассмотрим два простейших типа стратегии случайного доступа: чистую Алоху и синхроннуюАлоху.
Чистая Алоха.
Эта схема сначала была применена для доступа к общему каналу сотрудниками Гавайского университета в начале 1970-х годов. По этой схеме пользователь, желающий передать сообщение, делает это когда угодно. В результате могут наложится во времени два или несколько сообщений, вызвав столкновение (коллизию).
Распознавание коллизий и сообщение о них пострадавшим пользователям в первоначальной системе Алоха направлялись по радио на центральный пункт. Также это могло осуществляться путем применения положительгых подтверждений в сочетании с перерывом. При обнаружении столкновения пострадавшие станции предпринимают попытки повторной передачи потерянного сообщения, но они должны распределять время попыток случайным образом, следуя некоторому алгоритму столкновения нового конфликта.
Стратегия доступа типа Чистой Алохи позволяет добиться производительности самое большее 1/2e»0,18 пропускной способности канала. Введем сначала некоторые определения. За доступ к каналу состязаются N станций. Станция передает, в среднем, l пакетов в секунду (интенсивность обращений к сети). Величина 1/m представляет собой пропускную способность канала (m) в передаваемых пакетах в секунду. Рассмотрим теперь частный случай, при котором все передаваемые сообщения (пакеты) имеют среднюю длину t, соответствующую m единицам времени передачи. Будем считать, что интенсивность нагрузки S (эквивалентно r -нормированной по mнагрузке) характеризует использование канала вновь поступающими пакетами
S º r = Nlm.
Величина 1/t, которая обозначается m, представляет собой пропускную способность канала в передаваемых пакетах в секунду. Таким образом, Nl/m = Nlm - относительное использование канала, или производительность, нормированная относительно каждого компьютера одинакова. Общая интенсивность пакетов, передаваемых в канал, включая вновь генерируемые и передаваемые повторно, имеет некоторое значение l’ > l (из-за коллизий от каждого компьютера будет передаваться больше сообщений из-за необxодимости возобновлять поток). Тогда фактическая интенсивность нагрузки, или использование канала, является параметром G, который равен
G = Nl’t.
Рассмотрим типичное сообщение длительностью t с, показанное на рис.1.
Ошибка! Ошибка связи.
Рис. 1. Столкновение двух сообщений
Оно подвергается столкновению с другим сообщением, если эти два сообщения будут наложены одно на другое в любой точке. Легко заметить, передвигая пунктирное сообщение во времени, что столкновение может произойти в промежутке времени продолжительностью 2t с. Вероятность того, что в промежутке 2t с не произойдет столкновения, равна e-2Nl’m=e-2G.
Отношение S/G представляет долю сообщений из числа передаваемых в канал, которые проходят успешно. Это число должно быть равно вероятности отсутствия столкновений. Таким образом уравнение производительности для чистой Алохи:
S = Ge-2G (1).
Здесь S - нормированная производительность (средняя скорость поступления пакетов, деленная на максимальную производительность 1/m), а G - нормированная пропущенная нагрузка. Таким образом, S – независимая переменная, а G - ее функция. График зависимости G от S имеет вид двузначной кривой (рис. 2).
Рис.2. Характеристика производительности; Чистая Алоха
Отметим, что S имеет максимум S = 0,5e-1» 0,18 при G = 0.5. Судя по формуле (1) или кривой при малой постутающей нагрузке S столкновения происходят редко, и G » S. Когда S начинает расти, приближаясь к максимальному значению 0.18, число столкновений быстро увеличивается, что ведет в свою очередь к росту вероятности столкновения. Система теряет устойчивость, S падает, а G увеличивается до больших значений.
Синхронная Алоха.
Максимально возможная производительность схемы чистой Алохи может быть удвоена с помощью простого приема пазметки шкалы времени и разрешения пользователям начинать попытки передачи сообщений только в начале каждого временного интервала m (равного длительности сообщения). Эта схема требует, чтобы работа всех пользователей системы была синхронизирована во времени. Пример работы такой системы показан на рис. 3, на котором одно сообщение передано успешно, а с другим произошло столкновение.
Рис. 3. Передача при синхронной Алохе
Поскольку сообщения могут быть переданы только в размеченные промежутки времени, столкновения происходят лишь когда одна или несколько попыток передачи совершаются в том же промежутке.
Вероятность успешной передачи задается в виде e-G, а производительность для синхронной Алохи имеет вид
S = Ge-G.
Нормированная производительность S достигает максимального значения 1/e » 0,368 при G = 1. Зависимость пропущенной нагрузки от производительности для синхронной Алохи показана на рис. 4, где она сравнивается с соответствующей зависимостью для чистой Алохи.
Рис. 4. Характеристика производительности; Синхронная Алоха
Из приведенной характеристики очевидно, что ввиду двух возможных значений G при заданной производительности S, для этой системы доступа также характерна неустойчивость.
10. Контрольные вопросы
1. Сколько основных способов доступа вы знаете? Кратко опишите их суть.
а) 3.
Б) 2.
В) 4.
2. Что представляет собой коллизия?
а) столкновение, вызванное возможностью того, что два или несколько пользователей могут выйти на связь в пересекающиеся промежутки времени.
Б) отправка необработанного сигнала в очередь для ожидания последующей его обработки.
В) “зависание” связи из-за большого количества пользователей, вышедших на связь.
3. Какой максимальной производительности позволяет добиться стратегия доступа типа Чистой Алохи?
а) 1/3e»0,19 пропускной способности канала.
Б) 1/3e»0,18 пропускной способности канала.
В) 1/2e»0,18 пропускной способности канала.
10. Какая величина представляет собой пропускную способность канала (m) в передаваемых пакетах в секунду?
а) 1/m.
Б) 1/t.
В) l/m.
10. Какой формулой описывается интенсивность нагрузки S (эквивалентно r), характеризующая использование канала вновь поступающими пакетами?
а) Nl/m.
Б) Nl’t.
В) Nlm.
10. Чему равна фактическая интенсивность нагрузки, или использование канала G?
а) N’lt
б) N/l’t
в) Nl’t
7. Какова вероятность того, что в промежутке 2t с не произойдет столкновения?
а) e-2Gl’m
б) e-2Nl’m
в) e-2G
8. Каков вид уравнения производительности для чистой Алохи (это число должно быть равно вероятности отсутствия столкновений)?
à) Ge-2G
á) Ge-2l
â) te-2G
9. Каково максимальное значение нормированной производитльности S при G = 1 для синхронной Алохи?
а) 1/t » 0,378.
Б) 1/e » 0,368.
В) 1/e » 0,278.
10. Какой вид имеет производительность S для синхронной Алохи?
а) Ge-2lG
б) GeGt
в) Ge-G
Практические задания
· Проверить формулы пропускной способности канала в чистой и синхронной Алохе. Интервал времени, т.е. интервал повторения передачи взять согласно варианту.
· Проверить при заданной нагрузке зависимость истинной нагрузки G от этого интервала (см. выше). Значение нагрузки взять согласно варианту.
· Построить функцию G, а также зависимость числа коллизий от интервала времени для повторного вызова.
Варианты заданий.
| N варианта | Интервал времени | Нагрузка |
| 1…10t | 0,18 | |
| 1...20t | 0,17 | |
| 1…15t | 0,18 | |
| 1...12t | 0,16 | |
| 1…9t | 0,15 | |
| 1...7t | 0,11 | |
| 1...14t | 0,17 | |
| 1...10t | 0,14 | |
| 1...16t | 0,15 | |
| 1...8t | 0,18 | |
| 1...12t | 0,16 | |
| 1...11t | 0,13 | |
| 1...15t | 0,12 | |
| 1...10t | 0,17 | |
| 1...9t | 0,14 | |
| 1...16t | 0,18 | |
| 1...14t | 0,11 | |
| 1...18t | 0,12 | |
| 1...10t | 0,14 | |
| 1...9t | 0,15 |