<<
>>

Система ALOHA

В 70-х годах Норман Абрамсон (Norman Abramson) и его коллеги из Гавайского университета разработали новый элегантный метод решения проблемы распределения каналов. Их труды впоследствии стали основой многих исследований

(Abramson, 1985).

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

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

Чистая система ALOHA

В основе системы ALOHA лежит простая идея: разрешить пользователям передачу, как только у них появляются данные для отсылки. Конечно, при этом будут столкновения, и столкнувшиеся кадры будут разрушены.

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

На рис. 4.1 показан пример формирования кадров в системе ALOHA. Все кадры на нашем рисунке имеют один размер, так как при этом пропускная способность системы сделана максимальной именно за счет фиксированного размера кадров.

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

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

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

Пусть «время кадра» означает интервал времени, требующийся для передачи стандартного кадра фиксированной длины (то есть длину кадра, деленную на скорость передачи данных). На данный момент мы предполагаем, что бесконечное количество пользователей порождает новые кадры, распределенные по Пуассону со следующим средним значением: N кадров за время кадра. (Допущение о бесконечном количестве пользователей необходимо для того, чтобы гарантировать, что величина N не станет уменьшаться по мере блокирования пользователей.) Если N> 1, это означает, что сообщество пользователей формирует кадры с большей скоростью, чем может быть передано по каналу, и почти каждый кадр будет страдать от столкновений.

Мы будем предполагать, что О N. При малой загрузке канала (то есть при N* 0) столкновений будет мало, поэтому мало будет и повторных передач, то есть G&N. При большой загрузке канала столкновений будет много, а следовательно, G> N. Какая бы ни была нагрузка, производительность канала S будет равна предлагаемой загрузке G, умноженной на вероятность успешной передачи, то есть S = GPQ, где Р0 — вероятность того, что кадр не пострадает в результате коллизии.

Кадр не пострадает от коллизии в том случае, если в течение интервала времени его передачи не будет послано больше ни одного кадра, как показано на рис. 4.2. При каких условиях затененный кадр будет передан без повреждений? Пусть t — это время, требуемое для передачи кадра. Если какой-либо пользователь сформирует кадр в интервале времени между £0 и £0 + t, то конец этого кадра столкнется с началом затененного кадра. При этом судьба затененного кадра предрешена еще до того, как будет послан его первый бит, однако, поскольку в чистой системе ALOHA станции не прослушивают канал до начала передачи, у них нет способа узнать, что канал занят и по нему уже передается кадр. Аналогичным образом любой другой кадр, передача которого начнется в интервале от £0 +1 до £0 + 2£, столкнется с концом затененного кадра.

Рис. 4.2. Опасный интервал времени для затененного кадра

Вероятность того, что в течение времени кадра будет сформировано k кадров, можно вычислить по формуле распределения Пуассона:

(4.2)

Таким образом, вероятность формирования нуля кадров в течение этого интервала времени равна e~G. Среднее количество кадров, сформированных за интервал времени длиной в два кадра, равно 2G. Вероятность того, что никто не начнет передачу в течение всего опасного периода, равна Р0 = е~. Учитывая, что 5 = GP0, получаем:

Зависимость производительности канала от предлагаемого трафика показана на рис. 4.3. Максимальная производительность достигает значения 5=1 /2е, что приблизительно равно 0,184 при G = 0,5. Другими словами, лучшее, на что мы можем надеяться, — это использовать канал на 18 %. Этот результат несколько разочаровывает, однако в случае, когда каждый передает, когда хочет, трудно ожидать стопроцентного успеха.

<< | >>
Источник: Э. ТАНЕНБАУМ. КОМПЬЮТЕРНЫЕ СЕТИ 4-Е ИЗДАНИЕ. 2003

Еще по теме Система ALOHA:

  1. § 39 Классификация договоров в отдельных видах. – Римская классификация. – Система прусского закона, французского и австрийского кодекса. – Система русского свода. – Система настоящего изложения.
  2. Тема 15 Правова система і система права. Система законодавства та систематизація нормативно-правових актів
  3. Глава 4. Система права и система законодательства
  4. §5. Система военных судов в РФ как часть системы судов общей юрисдикции
  5. Единство и взаимосвязь правовой системы и системы правового общества
  6. § 1.3. Система трудового права і система трудового законодавства
  7. § 33 Общее правило о переходе наследства к детям. – Отличие отделенных от неотделенных. – Право представления. – Право родительское. – Право боковых родственников. – Римская система определения прав по классам и степеням. – Германская система определения прав по линиям и коленам.
  8. § 14 Отношения супругов по имуществу. – Германское начало общения имуществ в браке и римская система приданого. – Особое имущество жены. – Разнообразные системы западных законодательств. – Раздел имуществ по прекращении брака. – Ограничения брачных договоров и сделок между супругами. – Английский закон об отношениях супругов по имуществу.
  9. § 34 Смешанные системы в новейших законодательствах. – Происходящее от различия сих систем различие в порядке раздела и в допущении права представления. – Ограничение наследственного права пределами родства. – Ограничение женщин. – Разделение наследства между родами. – Возвращение подаренного родителями. – Наследование супругов и незаконных детей и родителей. – Закон наследования в Англии.
  10. СИСТЕМА
  11. СИСТЕМА НЕРВНАЯ
  12. Тема 20. Смешанные правовые системы
  13. СИСТЕМА ТЕЙЛОРА
  14. 3. Система законодавства
  15. СИСТЕМА ЭРРАТИЧЕСКАЯ
  16. СИСТЕМА ИНДИКАЦИИ
  17. СИСТЕМА ВЕСТИБУЛЯРНАЯ