Протокол ALOHA

ALOHA — это протокол множественного доступа к среде передачи данных, предназначенный для организации связи в сетях с общей средой (например, радиоканале), где несколько станций передают данные асинхронно без централизованного управления. Основная идея протокола заключается в том, что любая станция может начать передачу в произвольный момент времени, а в случае коллизии (одновременной передачи двух или более станций) данные повторно отправляются после случайной задержки. Протокол был разработан в 1970 году в Гавайском университете (США) для радиосети ALOHAnet, обеспечивающей связь между компьютерами на островах. ALOHA стал основой для более поздних протоколов, таких как CSMA/CD (используемый в Ethernet), и оказал значительное влияние на развитие беспроводных и спутниковых систем связи.

История

Протокол ALOHA был создан в 1970 году под руководством Нормана Абрамсона (Norman Abramson) в рамках проекта ALOHAnet, финансируемого Управлением перспективных исследовательских проектов Министерства обороны США (DARPA). Целью проекта было обеспечение радиосвязи между компьютерами на Гавайских островах, где прокладка кабелей была затруднена из-за географических особенностей. Первая версия сети, получившая название Pure ALOHA, была запущена в 1971 году и использовала два частотных канала: один для передачи данных от станций к центральному узлу (uplink), другой — для обратной связи (downlink). В 1972 году была разработана улучшенная версия — Slotted ALOHA, которая повысила эффективность за счёт синхронизации времени передачи.

В 1973 году ALOHAnet была расширена до 7 станций, а в 1975 году — до 12. Протокол продемонстрировал свою работоспособность в условиях высоких задержек (до 0,5 секунды из-за спутниковой связи), что привлекло внимание исследователей. В 1970-х годах ALOHA был адаптирован для спутниковых систем связи, а в 1980-х — для локальных вычислительных сетей (LAN). В 1990-х годах принципы ALOHA легли в основу протокола CSMA/CA, используемого в Wi-Fi (стандарт IEEE 802.11). В России исследования по ALOHA проводились в рамках разработки систем связи для удалённых регионов, например, в проекте «Сеть-1» (1970-е годы), но широкого распространения не получили.

Принцип работы

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

Pure ALOHA (чистый ALOHA)

В версии Pure ALOHA станция передаёт данные в любой момент времени. Вероятность успешной передачи (пропускная способность) определяется по формуле:

\[ S = G \cdot e^{-2G} \]

где \( S \) — пропускная способность (доля успешных передач), \( G \) — нагрузка на сеть (среднее количество попыток передачи за время передачи одного пакета). Максимальная пропускная способность Pure ALOHA составляет около 18,4 % от пропускной способности канала, что достигается при \( G = 0,5 \). Это означает, что при высокой нагрузке (например, \( G = 1 \)) пропускная способность падает до 13,5 %, а при \( G = 2 \) — до 3,7 %.

Slotted ALOHA (слотированный ALOHA)

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

\[ S = G \cdot e^{-G} \]

Максимум достигает 36,8 % при \( G = 1 \). Таким образом, Slotted ALOHA в два раза эффективнее Pure ALOHA, но требует синхронизации времени между станциями, что усложняет реализацию.

Алгоритм повторной передачи

При обнаружении коллизии станция ожидает случайное время (backoff), которое вычисляется по алгоритму экспоненциальной задержки: после каждой неудачной попытки диапазон случайных чисел увеличивается (например, от 0 до \( 2^k - 1 \), где \( k \) — номер попытки). Это предотвращает перегрузку сети при большом числе станций.

Классификация

Протокол ALOHA относится к классу протоколов случайного доступа (random access protocols), которые не требуют централизованного управления. В зависимости от синхронизации и механизма обнаружения коллизий выделяют следующие разновидности:

• Pure ALOHA — асинхронный доступ, передача в любой момент.
• Slotted ALOHA — синхронизированный доступ, передача в начале слота.
• Reservation ALOHA — гибридный протокол, где станции резервируют слоты для передачи (используется в спутниковых системах).
• CSMA/ALOHA — комбинация с протоколом CSMA (Carrier Sense Multiple Access), где станция сначала проверяет, свободен ли канал, а затем передаёт по правилам ALOHA.

Характеристики

Основные параметры протокола ALOHA:

• Пропускная способность (S) — доля времени, в течение которого канал успешно передаёт данные. Для Pure ALOHA — до 18,4 %, для Slotted ALOHA — до 36,8 %.
• Задержка передачи — время от момента отправки до получения подтверждения. Зависит от нагрузки и числа повторных попыток. При низкой нагрузке задержка минимальна, при высокой — может достигать нескольких секунд.
• Вероятность коллизии — растёт с увеличением числа станций и нагрузки. Для Pure ALOHA при \( G = 1 \) вероятность коллизии составляет 86,5 %, для Slotted ALOHA — 63,2 %.
• Устойчивость к перегрузкам — при высокой нагрузке (например, \( G > 2 \)) протокол становится неэффективным, так как большая часть попыток приводит к коллизиям.

Применение

Протокол ALOHA и его модификации используются в различных системах связи:

• Спутниковая связь — в системах с большим числом абонентов (например, VSAT — Very Small Aperture Terminal), где централизованное управление затруднено из-за высоких задержек. Пример: система Inmarsat (Великобритания) использует Slotted ALOHA для передачи коротких сообщений.
• Беспроводные сети — в стандарте IEEE 802.11 (Wi-Fi) протокол CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance) включает элементы ALOHA, такие как случайная задержка перед передачей (backoff). В России Wi-Fi широко используется в сетях общего доступа (например, в аэропортах, кафе).
• Локальные вычислительные сети — в ранних версиях Ethernet (до внедрения CSMA/CD) использовались принципы ALOHA. В современных сетях ALOHA применяется в системах с низкой нагрузкой, например, в датчиках Интернета вещей (IoT).
• Радиосвязь в удалённых регионах — в России протокол ALOHA тестировался в 1970-х годах для связи между труднодоступными населёнными пунктами (например, в Якутии), но был вытеснен более эффективными протоколами.

Критика

Основные недостатки протокола ALOHA:

• Низкая пропускная способность — при высокой нагрузке эффективность падает до нескольких процентов, что делает протокол непригодным для сетей с большим трафиком.
• Нестабильность при перегрузках — при увеличении числа станций вероятность коллизий растёт, что приводит к лавинообразному росту повторных передач и полной блокировке сети (эффект «коллапса»).
• Отсутствие приоритетов — все станции равны, что не позволяет выделить критически важные передачи (например, в системах экстренной связи).
• Зависимость от синхронизации — Slotted ALOHA требует точной синхронизации времени, что усложняет реализацию в распределённых системах.

В ответ на эти недостатки были разработаны более совершенные протоколы, такие как CSMA/CD (Ethernet), CSMA/CA (Wi-Fi) и TDMA (Time Division Multiple Access). Однако ALOHA остаётся важным теоретическим примером и используется в специализированных областях, где простота реализации важнее эффективности.

Интересные факты

• Название «ALOHA» происходит от гавайского приветствия, что отражает место разработки протокола.
• В 1973 году ALOHAnet была одной из первых сетей, использующих пакетную коммутацию (пакетная передача данных), что предвосхитило развитие Интернета.
• В 1980-х годах протокол ALOHA был адаптирован для мобильной связи (например, в системе AMPS — Advanced Mobile Phone System), но позже вытеснен цифровыми стандартами.
• В России в 1990-х годах протокол ALOHA использовался в экспериментальных спутниковых системах связи для Крайнего Севера, но проекты не были завершены из-за недостатка финансирования.

Источники

• Abramson, N. (1970). «The ALOHA System — Another Alternative for Computer Communications». AFIPS Conference Proceedings.
• Tanenbaum, A. S. (2003). «Computer Networks». 4th Edition. Prentice Hall.
• Stallings, W. (2007). «Data and Computer Communications». 8th Edition. Pearson.
• Олифер, В. Г., Олифер, Н. А. (2008). «Компьютерные сети. Принципы, технологии, протоколы». 4-е издание. Питер.