Чистая Алоха

Эта схема сначала была применена для доступа к общему каналу сотрудниками Гавайского университета в начале 1970-х годов. По этой схеме пользователь, желающий передать сообщение, делает это когда угодно. В результате могут наложиться во времени два или несколько сообщений, вызвав столкновение (коллизию).

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

Стратегия доступа типа Чистой Алохи позволяет добиться производительности самое большее 1/2e» 0,18 пропускной способности канала. Введем сначала некоторые определения. За доступ к каналу состязаются N станций. Станция передает, в среднем, l пакетов в секунду (интенсивность обращений к сети). Величина 1/m представляет собой пропускную способность канала (m) в передаваемых пакетах в секунду. Рассмотрим теперь частный случай, при котором все передаваемые сообщения (пакеты) имеют среднюю длину t, соответствующую m единицам времени передачи. Будем считать, что интенсивность нагрузки S (эквивалентно r - нормированной по m нагрузке) характеризует использование канала вновь поступающими пакетами

(1)

Величина 1/τ, которая обозначается µ, представляет собой пропускную способность канала в передаваемых пакетах в секунду. Таким образом, Nλ/µ = Nλm - относительное использование канала, или производительность, нормированная относительно каждого компьютера одинакова. Общая интенсивность пакетов, передаваемых в канал, включая вновь генерируемые и передаваемые повторно, имеет некоторое значение λ' > λ. Это происходит, потому что из-за коллизий от каждого компьютера будет передаваться больше сообщений из-за необходимости возобновлять поток. Тогда фактическая интенсивность нагрузки, или использование канала, является параметром G, который равен:

(2)

Рассмотрим типичное сообщение длительностью с, показанное на рис. 2.2.

Рисунок 2.2. Столкновение двух сообщений

Оно подвергается столкновению с другим сообщением, если эти два сообщения будут наложены одно на другое в любой точке. Легко заметить, передвигая пунктирное сообщение во времени, что столкновение может произойти в промежутке времени продолжительностью 2τс. Вероятность того, что в промежутке 2τ с не произойдет столкновения, равна

(3)

Отношение S/G представляет долю сообщений из числа передаваемых в канал, которые проходят успешно. Это число должно быть равно вероятности отсутствия столкновений. Таким образом, уравнение производительности для чистой Алохи:

(4)

Здесь S - нормированная производительность (средняя скорость поступления пакетов, деленная на максимальную производительность 1/m), а G - нормированная пропущенная нагрузка. Таким образом, S – независимая переменная, а G - ее функция. График зависимости G от S имеет вид двузначной кривой (рисунок 2.3).

Рисунок 2.3. Характеристика производительности. Чистая Алоха

Отметим, что S имеет максимум S = 0,5e-1» 0,18 при G = 0.5. Судя по формуле (4) или кривой при малой поступающей нагрузке S столкновения происходят редко, и G à S. Когда S начинает расти, приближаясь к максимальному значению 0.18, число столкновений быстро увеличивается, что ведет в свою очередь к росту вероятности столкновения. Система теряет устойчивость, S падает, а G увеличивается до больших значений.