ALOHAnet

ALOHAnet — первая компьютерная сеть передачи данных с пакетной коммутацией, использовавшая в качестве среды доступа к ней беспроводную технологию. Была разработана и введена в эксплуатацию в 1968—1970-х годах группой учёных Гавайского университета под руководством Нормана Абрамсона в рамках исследовательского проекта THE ALOHA SYSTEM, основной целью которого было изучение возможностей использования радиопередачи как альтернативы проводным коммуникациям. Концептуальные наработки и решения, реализованные в ходе этого проекта, во многом легли в основу таких технологий и протоколов как Ethernet, Wi-Fi и сотовые сети. В 1973 году в сеть с использованием спутниковых каналов связи NASA ATS-1 были объединены вычислительные центры Гавайского университета, Исследовательского центра Эймса (NASA), Университета Аляски, Университета Тохоку, Университета электрокоммуникаций (Токио) и Сиднейского университета.

История

В 1968 году профессор Стэнфордского университета Норман Абрамсон начал работать в Гавайском университете, где возглавил команду исследователей, в которую входили Томас Гаардер (англ. Thomas Gaarder), Франклин Куо (англ. Franklin Kuo), Чу Линь (англ. Shu Lin), Уэсли Питерсон и Эдвард Уэлдон (англ. Edward Weldon), которая начала исследования по программе The Aloha System — возможности использования радиосвязи для взаимодействия пользователей больших компьютерных систем вместо проводных соединений. Первоначально предполагалось объединить в одну сеть главный кампус Гавайского университета, расположенный в долине Маноа — неподалёку от Гонолулу, с колледжем в Хило и колледжами на островах Оаху, Кауаи, Мауи и Гавайи. Все они располагались на расстоянии около 300 км от вычислительного центра. В перспективе предполагалось использовать сеть в масштабах страны.

Вычислительный центр главного кампуса университета состоял из ЭВМ IBM 360/65 с 750 КБ оперативной памяти и нескольких машин меньшей производительности. Для взаимодействия с ними машин колледжей планировалось использование дециметрового диапазона радиочастот в качестве среды передачи данных. Разработка экспериментальной компьютерной сети началась в сентябре 1968 года, а в 1971 году ALOHAnet начала работать (слово «aloha» на гавайском языке означает приветствие).

Технология ALOHAnet

В сети ALOHAnet для соединения компьютеров с главным вычислительным центром использовалось радиосоединение в дециметровом диапазоне волн. Было выделено два радиоканала шириной 100 КГц со скоростью передачи данных по ним 24 000 бод. Один радиоканал на частоте 407.350 МГц использовался для передачи данных от терминалов к центральному компьютеру в Гонолулу, а второй канал на частоте 413.475 МГц использовался для рассылки широковещательных сообщений от центрального компьютера терминалам (для этого возле центрального компьютера была установлена широковещательная антенна, а на удалённых островах — направленные антенны, не позволявшие принимать сообщения друг от друга — в системе ALOHA использовалась сетевая топология звезда).

Поскольку при одновременной попытке передачи по одному частотному диапазону с нескольких станций происходили коллизии, приводившие к искажению передаваемых данных, было принято инновационное решение использовать метод случайного доступа к каналу, позже названным ALOHA random access, который стал ключевым нововведением технологии, а также впервые передаваемую информацию было решено разбить на «пакеты» (по 704 бита: 80 8-битных символов + 64 бита управляющих).

Чистая ALOHA

Чистая система ALOHA. Светлыми прямоугольниками изображены успешно переданные кадры, тёмными — попавшие в коллизию.

Первую версию ALOHA random access также называют чистой ALOHA (англ. pure ALOHA). При использовании этого метода доступа к каналу, пользовательские компьютеры начинают передавать центральному пакеты данных сразу же после появления предназначенной для пересылки информации. Если передача двух или большего числа станций совпадают по времени (хотя бы частично), то центральный компьютер не может корректно принять данные. Чтобы дать отправителям возможность обнаружить коллизию, центральный компьютер рассылает полученный пакет данных после приёма. Сравнивая переданный пакет и принятый, отправитель может понять, были ли его данные приняты корректно или с ошибками. Если данные были переданы некорректно, отправитель выжидает случайный интервал времени и совершает повторную попытку передачи.

Оценка пропускной способности чистой ALOHA

Для того, чтобы красный кадр попал в коллизию, необходимо начать передачу синего кадра в течение интервала времени длительностью $2\tau$

Оценка пропускной способности чистой системы ALOHA определяется при следующих предположениях:

• Пользовательские данные, предназначенные для передачи, поступают на терминалы случайно, образуя пуассоновский поток;
• Отброшенные из-за ошибок передачи пакеты передаются повторно, образуя также пуассоновский поток;
• Все пакеты данных имеют одинаковую длину и передаются одинаковое время $\tau$;
• В сети находится бесконечное число удалённых терминалов (то есть если некий терминал уже передаёт данные, это никак не влияет на вероятность передачи данных другими терминалами).

При сделанных выше предположениях совокупный поток пакетов на терминалы является пуассоновским. Пусть среднее число появившихся на всех терминалах за время $\tau$ пакетов (в т.ч. и передающихся повторно) равно $G$. Соответственно, средний интервал времени между моментами поступления последовательных пакетов равен ${\frac {\tau }{G}}$.

Рассмотрим передачу некоего выделенного кадра данных. Пакет принимается некорректно если в момент начала его трансляции передавала другая станция, либо если до конца трансляции начала передавать ещё одна станция. Таким образом, для успешной передачи любого выделенного блока данных необходимо, чтобы в течение интервала времени $2\tau$ ни одна другая станция не начала передачу. Вероятность этого события есть $\mathbb {P} _{\mathrm {suc} }=e^{-2G}$. Среднее число успешно переданных за время $\tau$ пакетов, то есть пропускная способность сети, составляет $\lambda _{pure}(G)=G\mathbb {P} _{\mathrm {suc} }=Ge^{-2G}$.

Слотированная ALOHA

Слотированная система ALOHA. Пунктирные линии означают границы слотов.

В 1972 году Лоуренс Робертс предложил другую версию системы ALOHA, названную слотированной ALOHA (англ. slotted ALOHA). Основным отличием слотированной ALOHA от чистой являлась идея разделения оси времени на дискретные интервалы равной длительности $\tau$, названные слотами. Каждый терминал последовательно отмерял границы слотов. Для синхронизации границ слотов использовался специальный синхронизирующий сигнал, передаваемый с широковещательной антенны всем терминалам. При появлении предназначенных для передачи пакетов данных терминал задерживал передачу до начала следующего слота. Длительность слотов выбиралась так, чтобы за время одного слота терминал успел передать свой пакет данных и получить от центрального компьютера подтверждение успешной передачи.

Оценка пропускной способности слотированной ALOHA

При приведённых ранее допущениях оценка пропускной способности слотированной ALOHA определяется следующим образом. Так как пакеты данных передаются исключительно в границах слотов, для того, чтобы несколько терминалов начали передавать одновременно, они должны получить данные для передачи в течение одного и того же слота. Вероятность этого события составляет $\mathbb {P} _{\mathrm {fail} }=1-e^{-G}$. Тогда вероятность успешно передать пакет данных есть $\mathbb {P} _{\mathrm {suc} }=e^{-G}$, а пропускная способность сети равна $\lambda _{slot}(G)=G\mathbb {P} _{\mathrm {suc} }=Ge^{-G}$.

Сравнение пропускной способности

На следующем графике изображены зависимости пропускной способности чистой и слотированной систем ALOHA от поступающего на терминалы трафика $G$.

Максимальная же пропускная способность системы ALOHA определяется следующим образом:

Вывод максимума пропускной способности для чистой и слотированной ALOHA

Для чистой ALOHA пропускная способность зависит от нагрузки как:

$\lambda _{pure}(G)=Ge^{-2G}$

Найдём такое $G$, при котором достигается максимум пропускной способности:

$G_{pure}^{*}=\arg \max _{G\in \mathbb {R} ^{+}}~{\lambda _{pure}(G)}$.

$\lambda _{pure}(0)=\lim _{G\to +\infty }{\lambda _{pure}(G)}=0$.

${\frac {d\lambda _{pure}(G)}{dG}}=e^{-2G}-2Ge^{-2G}$.

${\Bigl .}{\frac {d\lambda _{pure}(G)}{dG}}{\Bigr |}_{G_{pure}^{*}}=e^{-2G_{pure}^{*}}-2G_{pure}^{*}e^{-2G_{pure}^{*}}=0\Rightarrow G_{pure}^{*}={\frac {1}{2}}$.

$\lambda _{pure}(G_{pure}^{*})={\frac {1}{2e}}\approx 0.18393972...$.

Для слотированной ALOHA пропускная способность зависит от нагрузки как:

$\lambda _{slot}(G)=Ge^{-G}$.

$G_{slot}^{*}=\arg \max _{G\in \mathbb {R} ^{+}}~{\lambda _{slot}(G)}$.

$\lambda _{slot}(0)=\lim _{G\to +\infty }{\lambda _{slot}(G)}=0$.

${\frac {d\lambda _{slot}(G)}{dG}}=e^{-G}-Ge^{-G}$.

${\Bigl .}{\frac {d\lambda _{slot}(G)}{dG}}{\Bigr |}_{G_{slot}^{*}}=e^{-G_{slot}^{*}}-G_{slot}^{*}e^{-G_{slot}^{*}}=0\Rightarrow G_{slot}^{*}=1$.

$\lambda _{slot}(G_{slot}^{*})={\frac {1}{e}}=2\lambda _{pure}(G_{pure}^{*})\approx 0.36787944...$.

Таким образом, использование слотированной ALOHA вместо чистой позволило увеличить максимальную пропускную способность сети в два раза. Как видно из графиков, пока значение нагрузки меньше той критической величины, при которой достигается максимум, пропускная способность сети растёт с увеличением трафика — система не используется на 100 %. Однако после превышения критической величины нагрузки, пропускная способность системы падает — слишком много пакетов попадает в коллизии и передаётся с ошибками.

Для чистой ALOHA критическая величина нагрузки составляет $G^{*}={\frac {1}{2}}$, то есть один пакет данных появляется в среднем за время $2\tau$. Для слотированной ALOHA критическая величина нагрузки составляет $G^{*}=1$, то есть один кадр данных появляется в среднем за время $\tau$.

Развитие и применение

Появление в сети ALOHAnet радиоретрансляторов позволило расширить и упорядочить её структуру. В 1973 году ALOHAnet была подсоединена к сети ARPAnet с использованием спутникового канала связи.

Как развитие идеи случайного конкурентного доступа к каналу связи, впервые применённой в системе ALOHA, был создан метод CSMA. Модификации этого метода CSMA/CA и CSMA/CD легли в основу протоколов канального уровня сетей Ethernet и Wi-Fi.

ALOHA random access используется в мобильных голосовых и пакетных сетях. В частности, при установлении голосового, СМС или интернет-соединения, первый пакет отправляется мобильным устройством с использованием ALOHA random access. ALOHA random access также был использован в спутниковых сетях.

Сильно модифицированная версия слотированной ALOHA используется при коммуникации нескольких RFID меток с одним считывателем.

Литература

• Abramson N. THE ALOHA SYSTEM (англ.): Another Alternative for Computer Communications // AFIPS '70 (Fall): Proceedings of the November 17-19, 1970, Fall Joint Computer Conference — New York City: ACM, 1970. — P. 281—285. — doi:10.1145/1478462.1478502
• Roberts L. ALOHA Packet System with and Without Slots and Capture (англ.) // ACM SIGCOMM: Computer Communication Review — New York City: ACM, 1975. — Vol. 5, Iss. 2. — P. 28—42. — ISSN 0146-4833; 1943-5819 — doi:10.1145/1024916.1024920
• Binder R., Abramson N., Kuo F. F., Okinaka A., Wax D. ALOHA Packet Broadcasting: A Retrospect (англ.) // AFIPS '75: Proceedings of the May 19-22, 1975, national computer conference and exposition — New York City: ACM, 1975. — P. 203—215. — doi:10.1145/1499949.1499985
• Kuo F. F. The ALOHA System (англ.) // ACM SIGCOMM: Computer Communication Review — New York City: ACM, 1995. — Vol. 25, Iss. 1. — P. 41—44. — ISSN 0146-4833; 1943-5819 — doi:10.1145/205447
• Schwartz M., Abramson N. The Alohanet — surfing for wireless data (англ.): History of Communications // IEEE Communications Magazine — IEEE, 2009. — Vol. 47, Iss. 12. — P. 21—25. — ISSN 0163-6804; 1558-1896 — doi:10.1109/MCOM.2009.5350363
• Таненбаум Э., Уэзеролл Д. Компьютерные сети — 5-е изд. — СПб.: Питер, 2012. — С. 286—290. — 960 с. — ISBN 978-5-459-00342-0

Ссылки

• James Pelkey. ALOHANET and Norm Abramson: 1966 - 1972 // Entrepreneurial Capitalism and Innovation: A History of Computer Communications 1968-1988.
• 2011 Recipients of C&C Prize  (неопр.). NEC C&C Foundation. Дата обращения: 3 января 2016.
• Аганесов Артур Валерьевич. МОДЕЛЬ СЕТИ СПУТНИКОВОЙ СВЯЗИ НА ОСНОВЕ ПРОТОКОЛА СЛУЧАЙНОГО МНОЖЕСТВЕННОГО ДОСТУПА S-ALOHA // Системы управления, связи и безопасности. — 2015. — № 2.