Русская Википедия:ALOHAnet
ALOHAnet — первая компьютерная сеть передачи данных с пакетной коммутацией, использовавшая в качестве среды доступа к ней беспроводную технологию. Была разработана и введена в эксплуатацию в 1968—1970-х годах группой учёных Гавайского университета под руководством Шаблон:Не переведено 5 в рамках исследовательского проекта THE ALOHA SYSTEM, основной целью которого было изучение возможностей использования радиопередачи как альтернативы проводным коммуникациям. Концептуальные наработки и решения, реализованные в ходе этого проекта, во многом легли в основу таких технологий и протоколов как Ethernet, Wi-Fi и сотовые сетиШаблон:Sfn. В 1973 году в сеть с использованием спутниковых каналов связи NASA Шаблон:Не переведено 5 были объединены вычислительные центры Гавайского университета, Исследовательского центра Эймса (NASA), Шаблон:Нп5, Университета Тохоку, Университета электрокоммуникаций (Токио) и Сиднейского университета[1].
История
В 1968 году профессор Стэнфордского университета Норман Абрамсон начал работать в Гавайском университете, где возглавил команду исследователей, в которую входили Томас Гаардер (Шаблон:Lang-en), Франклин Куо (Шаблон:Lang-en), Чу Линь (Шаблон:Lang-en), Шаблон:Не переведено 5 и Эдвард Уэлдон (Шаблон:Lang-en), которая начала исследования по программе The Aloha System — возможности использования радиосвязи для взаимодействия пользователей больших компьютерных систем вместо проводных соединенийШаблон:Sfn. Первоначально предполагалось объединить в одну сеть главный кампус Гавайского университета, расположенный в долине Маноа — неподалёку от Гонолулу, с колледжем в Хило и колледжами на островах Оаху, Кауаи, Мауи и Гавайи. Все они располагались на расстоянии около 300 км от вычислительного центра. В перспективе предполагалось использовать сеть в масштабах страныШаблон:SfnШаблон:Sfn.
Вычислительный центр главного кампуса университета состоял из ЭВМ IBM 360/65 с 750 КБ оперативной памяти и нескольких машин меньшей производительности. Для взаимодействия с ними машин колледжей планировалось использование дециметрового диапазона радиочастот в качестве среды передачи данных. Разработка экспериментальной компьютерной сети началась в сентябре 1968 года, а в 1971 году ALOHAnet начала работатьШаблон:Sfn (слово «aloha» на гавайском языке означает приветствие)[2].
Технология ALOHAnet
В сети ALOHAnet для соединения компьютеров с главным вычислительным центром использовалось радиосоединение в дециметровом диапазоне волнШаблон:Sfn. Было выделено два радиоканала шириной 100 КГцШаблон:Sfn со скоростью передачи данных по ним 24 000 бодШаблон:Sfn. Один радиоканал на частоте 407.350 МГцШаблон:Sfn использовался для передачи данных от терминалов к центральному компьютеруШаблон:Sfn в Гонолулу, а второй канал на частоте 413.475 МГцШаблон:Sfn использовался для рассылки широковещательных сообщений от центрального компьютера терминаламШаблон:Sfn (для этого возле центрального компьютера была установлена широковещательная антенна, а на удалённых островах — направленные антенны, не позволявшие принимать сообщения друг от друга — в системе ALOHA использовалась сетевая топология звезда)Шаблон:Sfn.
Поскольку при одновременной попытке передачи по одному частотному диапазону с нескольких станций происходили коллизии, приводившие к искажению передаваемых данных, было принято инновационное решение использовать метод случайного доступа к каналу, позже названным ALOHA random access, который стал ключевым нововведением технологииШаблон:Sfn, а также впервые передаваемую информацию было решено разбить на «пакеты» (по 704 бита: 80 8-битных символов + 64 бита управляющих)Шаблон:Sfn.
Чистая ALOHA
Первую версию ALOHA random access также называют чистой ALOHA (Шаблон:Lang-en). При использовании этого метода доступа к каналу, пользовательские компьютеры начинают передавать центральному пакеты данных сразу же после появления предназначенной для пересылки информации. Если передача двух или большего числа станций совпадают по времени (хотя бы частично), то центральный компьютер не может корректно принять данные. Чтобы дать отправителям возможность обнаружить коллизию, центральный компьютер рассылает полученный пакет данных после приёма. Сравнивая переданный пакет и принятый, отправитель может понять, были ли его данные приняты корректно или с ошибками. Если данные были переданы некорректно, отправитель выжидает случайный интервал времени и совершает повторную попытку передачиШаблон:Sfn.
Оценка пропускной способности чистой ALOHA
Оценка пропускной способности чистой системы ALOHA определяется при следующих предположенияхШаблон:SfnШаблон:Sfn:
- Пользовательские данные, предназначенные для передачи, поступают на терминалы случайно, образуя пуассоновский поток;
- Отброшенные из-за ошибок передачи пакеты передаются повторно, образуя также пуассоновский поток;
- Все пакеты данных имеют одинаковую длину и передаются одинаковое время <math>\tau</math>;
- В сети находится бесконечное число удалённых терминалов (то есть если некий терминал уже передаёт данные, это никак не влияет на вероятность передачи данных другими терминалами).
При сделанных выше предположениях совокупный поток пакетов на терминалы является пуассоновским. Пусть среднее число появившихся на всех терминалах за время <math>\tau</math> пакетов (в т.ч. и передающихся повторно) равно <math>G</math>. Соответственно, средний интервал времени между моментами поступления последовательных пакетов равен <math>\frac{\tau}{G}</math>.
Рассмотрим передачу некоего выделенного кадра данных. Пакет принимается некорректно если в момент начала его трансляции передавала другая станция, либо если до конца трансляции начала передавать ещё одна станция. Таким образом, для успешной передачи любого выделенного блока данных необходимо, чтобы в течение интервала времени <math>2 \tau</math> ни одна другая станция не начала передачу. Вероятность этого события есть <math>\mathbb{P}_\mathrm{suc} = e^{-2 G}</math>. Среднее число успешно переданных за время <math>\tau</math> пакетов, то есть пропускная способность сети, составляет <math>\lambda_{pure}(G) = G \mathbb{P}_\mathrm{suc} = G e^{-2 G}</math>Шаблон:Sfn.
Слотированная ALOHA
В 1972 году Лоуренс Робертс предложил другую версию системы ALOHA, названную слотированной ALOHA (Шаблон:Lang-en)Шаблон:Sfn. Основным отличием слотированной ALOHA от чистой являлась идея разделения оси времени на дискретные интервалы равной длительности <math>\tau</math>, названные слотами. Каждый терминал последовательно отмерял границы слотов. Для синхронизации границ слотов использовался специальный синхронизирующий сигнал, передаваемый с широковещательной антенны всем терминалам. При появлении предназначенных для передачи пакетов данных терминал задерживал передачу до начала следующего слота. Длительность слотов выбиралась так, чтобы за время одного слота терминал успел передать свой пакет данных и получить от центрального компьютера подтверждение успешной передачиШаблон:Sfn.
Оценка пропускной способности слотированной ALOHA
При приведённых ранее допущениях оценка пропускной способности слотированной ALOHA определяется следующим образом. Так как пакеты данных передаются исключительно в границах слотов, для того, чтобы несколько терминалов начали передавать одновременно, они должны получить данные для передачи в течение одного и того же слота. Вероятность этого события составляет <math>\mathbb{P}_\mathrm{fail} = 1 - e^{-G}</math>. Тогда вероятность успешно передать пакет данных есть <math>\mathbb{P}_\mathrm{suc} = e^{-G}</math>, а пропускная способность сети равна <math>\lambda_{slot}(G) = G \mathbb{P}_\mathrm{suc} = G e^{-G}</math>Шаблон:Sfn.
Сравнение пропускной способности
На следующем графике изображены зависимости пропускной способности чистой и слотированной систем ALOHA от поступающего на терминалы трафика <math>G</math>.
Пропускная способность чистой и слотированной ALOHA
Максимальная же пропускная способность системы ALOHA определяется следующим образом:
Шаблон:Вывод = e^{-2 G^*_{pure}} - 2 G^*_{pure} e^{-2 G^*_{pure}} = 0 \Rightarrow G^*_{pure}=\frac{1}{2}</math>.
<math>\lambda_{pure}(G^*_{pure}) = \frac{1}{2 e} \approx 0.18393972...</math>.
Для слотированной ALOHA пропускная способность зависит от нагрузки как:
<math>\lambda_{slot}(G) = G e^{-G}</math>.
<math>G^*_{slot}= \arg\max_{G \in \R^+}~{\lambda_{slot}(G)}</math>.
<math>\lambda_{slot}(0)=\lim_{G \to +\infty}{\lambda_{slot}(G)} = 0</math>.
<math>\frac{d\lambda_{slot}(G)}{dG} = e^{-G} - G e^{-G}</math>.
<math>\Bigl. \frac{d\lambda_{slot}(G)}{dG} \Bigr|_{G^*_{slot}} = e^{-G^*_{slot}} - G^*_{slot} e^{-G^*_{slot}} = 0 \Rightarrow G^*_{slot}=1</math>.
<math>\lambda_{slot}(G^*_{slot}) = \frac{1}{e} = 2 \lambda_{pure}(G^*_{pure}) \approx 0.36787944...</math>.
}}
Таким образом, использование слотированной ALOHA вместо чистой позволило увеличить максимальную пропускную способность сети в два раза. Как видно из графиков, пока значение нагрузки меньше той критической величины, при которой достигается максимум, пропускная способность сети растёт с увеличением трафика — система не используется на 100 %. Однако после превышения критической величины нагрузки, пропускная способность системы падает — слишком много пакетов попадает в коллизии и передаётся с ошибками.
Для чистой ALOHA критическая величина нагрузки составляет <math>G^*=\frac{1}{2}</math>, то есть один пакет данных появляется в среднем за время <math>2 \tau</math>. Для слотированной ALOHA критическая величина нагрузки составляет <math>G^*=1</math>, то есть один кадр данных появляется в среднем за время <math>\tau</math>Шаблон:Sfn.
Развитие и применение
Появление в сети ALOHAnet радиоретрансляторов позволило расширить и упорядочить её структуруШаблон:Sfn. В 1973 году ALOHAnet была подсоединена к сети ARPAnet с использованием спутникового канала связиШаблон:Sfn.
Как развитие идеи случайного конкурентного доступа к каналу связи, впервые применённой в системе ALOHA, был создан метод CSMA. Модификации этого метода CSMA/CA и CSMA/CD легли в основу протоколов канального уровня сетей Ethernet и Wi-FiШаблон:Sfn.
ALOHA random access используется в мобильных голосовых и пакетных сетях. В частности, при установлении голосового, СМС или интернет-соединения, первый пакет отправляется мобильным устройством с использованием ALOHA random access. ALOHA random access также был использован в спутниковых сетяхШаблон:Sfn.
Сильно модифицированная версия слотированной ALOHA используется при коммуникации нескольких RFID меток с одним считывателемШаблон:Sfn.
Примечания
Литература
Ссылки
