ALOHAnet , также известная как система ALOHA , [1] [2] [3] или просто ALOHA , была пионерской компьютерной сетевой системой, разработанной в Гавайском университете . ALOHAnet начала работать в июне 1971 года, обеспечив первую публичную демонстрацию беспроводной пакетной сети передачи данных . [4] [5]
ALOHAnet использовал новый метод доступа к среде, называемый случайным доступом ALOHA , и экспериментальную сверхвысокую частоту (UHF) для своей работы. В своей простейшей форме, позже известной как Pure ALOHA, удаленные устройства связывались с базовой станцией (Menehune) по двум отдельным радиочастотам (для входящей и исходящей соответственно). Узлы не ждали, пока канал освободится перед отправкой, а вместо этого ждали подтверждения успешного получения сообщения и повторно отправляли его, если оно не было получено. Узлы также останавливались и повторно передавали данные, если они обнаруживали какие-либо другие сообщения во время передачи. Несмотря на простоту реализации, это приводит к эффективности всего 18,4%. Более позднее усовершенствование, Slotted ALOHA, повысило эффективность протокола, уменьшив вероятность коллизии, увеличив пропускную способность до 36,8%.
ALOHA впоследствии был использован в кабельной сети Ethernet в 1970-х годах, и после нормативных разработок в начале 1980-х годов стало возможным использовать методы случайного доступа ALOHA как в Wi-Fi , так и в сетях мобильной связи. Каналы ALOHA использовались ограниченно в 1980-х годах в мобильных телефонах 1G для сигнализации и управления. В конце 1980-х годов Европейская группа по стандартизации GSM, работавшая над общеевропейской цифровой системой мобильной связи GSM, значительно расширила использование каналов ALOHA для доступа к радиоканалам в мобильной телефонии. В начале 2000-х годов дополнительные каналы ALOHA были добавлены в мобильные телефоны 2.5G и 3G с широким внедрением службы пакетной радиосвязи общего пользования (GPRS), использующей канал случайного доступа ALOHA с интервалами в сочетании с версией схемы резервирования ALOHA, впервые проанализированной группой в BBN Technologies .
Один из ранних проектов компьютерных сетей, разработка сети ALOHA была начата в сентябре 1968 года в Гавайском университете под руководством Нормана Абрамсона и Франклина Куо , а также Томаса Гаардера, Шу Лина, Уэсли Петерсона и Эдварда («Неда») Уэлдона. Цель состояла в том, чтобы использовать недорогое коммерческое радиооборудование для соединения пользователей на Оаху и других гавайских островах с центральным компьютером с разделением времени в главном кампусе Оаху. Первый блок пакетного вещания был введен в эксплуатацию в июне 1971 года. Терминалы были подключены к специальному блоку терминального соединения с использованием RS-232 на скорости 9600 бит/с. [6]
Первоначально ALOHA была придуманной аббревиатурой , означающей Additive Links On-line Hawaii Area. [7]
Первоначальная версия ALOHA использовала две различные частоты в конфигурации концентратора, при этом концентратор транслировал пакеты всем на исходящем канале, а различные клиентские машины отправляли пакеты данных концентратору на входящем канале. Если данные были получены на концентраторе правильно, клиенту отправлялся короткий пакет подтверждения; если клиентская машина не получала подтверждение после короткого времени ожидания, она автоматически повторно передавала пакет данных после ожидания в течение случайно выбранного интервала времени. Этот механизм подтверждения использовался для обнаружения и исправления коллизий, возникающих, когда две клиентские машины пытались отправить пакет одновременно.
Главной важностью ALOHAnet было использование общей среды для клиентских передач. В отличие от ARPANET , где каждый узел мог общаться только с одним узлом на другом конце проводной или спутниковой линии, в ALOHAnet все клиентские узлы общались с концентратором на одной и той же частоте. Это означало, что требовался какой-то механизм для контроля того, кто мог говорить в какое время. Решение ALOHAnet состояло в том, чтобы позволить каждому клиенту отправлять свои данные без контроля того, когда они были отправлены, и реализации схемы подтверждения/повторной передачи для решения проблем с коллизиями. Такой подход радикально снизил сложность протокола и сетевого оборудования, поскольку узлам не нужно было договариваться, кому разрешено говорить.
Это решение стало известно как чистый ALOHA, или канал с произвольным доступом, и стало основой для последующего развития Ethernet и более поздних сетей Wi-Fi . [5] Различные версии протокола ALOHA (например, Slotted ALOHA) также появились позже в спутниковой связи и использовались в беспроводных сетях передачи данных, таких как ARDIS , Mobitex , CDPD и GSM .
Сеть Aloha представила механизм рандомизированного множественного доступа, который разрешал коллизии передачи устройств путем немедленной передачи пакета, если подтверждение отсутствует, а если подтверждение не получено, передача повторялась после случайного времени ожидания. [8] Распределение вероятностей этого случайного времени ожидания повторной передачи пакета, который не был подтвержден как полученный, критически важно для стабильности систем связи типа Aloha. Среднее время ожидания повторной передачи обычно короче среднего времени генерации нового пакета с того же клиентского узла, но оно не должно быть настолько коротким, чтобы поставить под угрозу стабильность сети, вызывая крах ее общей пропускной способности. [9]
Также важным было использование ALOHAnet исходящего канала концентратора для прямой трансляции пакетов всем клиентам на второй общей частоте и использование адреса в каждом пакете для обеспечения выборочного приема на каждом клиентском узле. [4] Для входящих и исходящих сообщений на концентратор использовались отдельные частоты, чтобы устройства могли получать подтверждения независимо от передач.
Первоначальная версия протокола (теперь называемая Pure ALOHA и реализованная в ALOHAnet) была довольно простой:
Чистый ALOHA не проверяет, занят ли канал перед передачей. Поскольку могут возникнуть коллизии и данные, возможно, придется отправлять снова, ALOHA не может эффективно использовать 100% пропускной способности канала связи. То, как долго станция ждет повторной передачи, и вероятность возникновения коллизии взаимосвязаны, и оба влияют на то, насколько эффективно может использоваться канал. Это означает, что концепция последующей повторной передачи является критическим аспектом; качество выбранной схемы отсрочки существенно влияет на эффективность протокола, конечную пропускную способность канала и предсказуемость его поведения.
Для оценки Pure ALOHA необходимо спрогнозировать его пропускную способность, скорость (успешной) передачи кадров. [10] Сначала сделаем несколько упрощающих предположений:
Пусть T относится ко времени, необходимому для передачи одного кадра по каналу, и определите время кадра как единицу времени, равную T. Пусть G относится к среднему значению, используемому в распределении Пуассона по количеству попыток передачи. То есть, в среднем на время кадра приходится G попыток передачи .
Рассмотрим, что должно произойти для успешной передачи кадра. Пусть t относится к времени, в которое предполагается отправить кадр. Предпочтительно использовать канал для одного времени кадра, начиная с t , а все остальные станции должны воздержаться от передачи в это время.
Для любого времени кадра вероятность того, что в течение этого времени будет k попыток передачи, равна:
Среднее количество попыток передачи для двух последовательных кадровых интервалов составляет 2G . Следовательно, для любой пары последовательных кадровых интервалов вероятность того, что в течение этих двух кадровых интервалов будет k попыток передачи, составляет:
Следовательно, вероятность ( ) того, что между tT и t+T не будет попыток передачи (и, следовательно, для нас передача будет успешной), равна:
Пропускную способность можно рассчитать как частоту попыток передачи, умноженную на вероятность успеха, и можно сделать вывод, что пропускная способность ( ) равна:
Максимальная пропускная способность составляет 0,5/e кадров за время кадра (достигается при ), что составляет приблизительно 0,184 кадров за время кадра. Это означает, что в Pure ALOHA только около 18,4% времени используется для успешных передач.
Улучшением оригинального протокола ALOHA стал Slotted ALOHA, который ввел дискретные временные интервалы и увеличил максимальную пропускную способность. [11] Станция может начать передачу только в начале временного интервала, и, таким образом, коллизии уменьшаются. В этом случае необходимо учитывать только попытки передачи в течение 1 кадра, а не 2 последовательных кадров, поскольку коллизии могут происходить только в течение каждого временного интервала. Таким образом, вероятность того, что в одном временном интервале будет ноль попыток передачи другими станциями, равна:
вероятность передачи, требующей ровно k попыток, равна (k-1 коллизий и 1 успех): [10]
Пропускная способность составляет:
Максимальная пропускная способность составляет 1/e кадров за время кадра (достигается при G = 1), что составляет приблизительно 0,368 кадров за время кадра или 36,8%.
Технология Slotted ALOHA используется в тактических спутниковых сетях связи с низкой скоростью передачи данных , используемых военными силами, в абонентских спутниковых сетях связи, при установлении вызовов мобильной телефонии, при подключении телевизионных приставок и в бесконтактных технологиях RFID .
Резервирование ALOHA, или R-ALOHA, является попыткой улучшить эффективность Slotted ALOHA. Улучшения с Reservation ALOHA заключаются в заметно более коротких задержках и способности эффективно поддерживать более высокие уровни использования. В качестве контраста эффективности, моделирование показало, что Reservation ALOHA демонстрирует меньшую задержку при 80% использовании, чем Slotted ALOHA при 20–36% использовании. [12]
Главное различие между Slotted и Reservation ALOHA заключается в том, что при Slotted ALOHA любой слот доступен для использования без учета предыдущего использования. Согласно схеме резервирования на основе конкуренции Reservation ALOHA , слот временно считается «принадлежащим» станции, которая успешно его использовала. Кроме того, Reservation ALOHA просто прекращает отправку данных после того, как станция завершила передачу. Как правило, свободные слоты считаются доступными для всех станций, которые затем могут неявно зарезервировать (использовать) слот на основе конкуренции.
Пакетный резервный множественный доступ (PRMA) — это неявная схема резервирования. Некоторое фиксированное количество слотов образует кадр. После каждого кадра спутник транслирует статус каждого слота из предыдущего кадра, который указывает на статус резервирования соответствующих слотов следующего кадра. Все наземные станции, желающие передавать, конкурируют точно так же, как слотовая ALOHA в течение любого «свободного слота» следующего кадра (т. е. либо никто не передавал в этом слоте предыдущего кадра, либо произошла коллизия, когда несколько наземных станций передавали в этом слоте предыдущего кадра). Если ровно одна наземная станция передает в течение «свободного слота», эта наземная станция успешно резервирует этот слот кадра — соответствующий слот неявно резервируется во всех будущих кадрах. С этого момента спутник транслирует, что эта конкретная наземная станция зарезервировала этот слот кадра, и эта наземная станция может продолжать передачу с гарантированной скоростью передачи данных в течение этого слота кадра; другие наземные станции стараются *не* передавать в течение этого слота кадра, поэтому во время зарезервированных слотов не происходит коллизий. Когда наземной станции с зарезервированным слотом нечего отправлять, она просто прекращает передачу, что приводит к отказу от резервирования; спутник замечает, что его зарезервированный слот свободен в одном кадре, и передает этот факт, что означает, что этот слот будет «свободным слотом» в следующем кадре. [13] [14]
Максимальная эффективность канала для слотированного ALOHA составляет 36%; PRMA повышает максимальную эффективность канала до 80%. [14]
Множественный доступ с назначением по требованию (DAMA), также называемый резервированием ALOHA, является схемой явного резервирования, часто используемой в спутниковой связи. DAMA чередуется между двумя фазами: во время фазы резервирования кадра DAMA действует как слотированный ALOHA для некоторого фиксированного количества коротких слотов, за исключением того, что вместо того, чтобы наземные станции отправляли полные пакеты, наземные станции отправляют только короткие запросы для последующей передачи. Спутник собирает все успешные запросы (т. е. те, которые не были уничтожены столкновением) и отправляет их обратно в виде списка резервирования, назначая определенные наземные станции определенным слотам TDM. Во время фазы TDM кадра наземные станции подчиняются списку резервирования, и каждая из них передает только в течение длинных слотов TDM, зарезервированных для нее. Коллизии могут происходить во время фазы резервирования, но не во время фазы TDM. [14] [15]
Максимальная эффективность канала для слотированного ALOHA составляет 36%; DAMA повышает максимальную эффективность канала до 80%. [14]
Использование канала с произвольным доступом в ALOHAnet привело к разработке множественного доступа с контролем несущей (CSMA), протокола произвольного доступа с прослушиванием перед отправкой , который может использоваться, когда все узлы отправляют и получают данные по одному и тому же каналу. CSMA в радиоканалах был тщательно смоделирован. [16] Протокол пакетной радиосвязи AX.25 основан на подходе CSMA с восстановлением после столкновений, [17] основанном на опыте, полученном в ALOHAnet. Разновидность CSMA, CSMA/CD, используется в ранних версиях Ethernet .
ALOHA и другие протоколы случайного доступа имеют присущую им изменчивость в характеристиках пропускной способности и задержки. По этой причине приложения, которым требуется высоко детерминированное поведение нагрузки, могут использовать схемы master/slave или token-passing (такие как Token Ring или ARCNET ) вместо систем состязаний .
Центральный узел связи процессора был HP 2100 миникомпьютер под названием Menehune, что является гавайским словом для карликовых людей, [18] и был назван из-за его схожей роли с оригинальным ARPANET Интерфейсный процессор сообщений (IMP), который был развернут примерно в то же время. В оригинальной системе Menehune пересылал правильно полученные пользовательские данные на центральный компьютер UH, систему разделения времени IBM System 360 /65. Исходящие сообщения от 360 преобразовывались в пакеты Menehune, которые ставились в очередь и транслировались удаленным пользователям со скоростью передачи данных 9600 бит/с. В отличие от полудуплексных радио в пользовательских TCU, Menehune был подключен к радиоканалам с помощью полнодуплексного радиооборудования. [19]
Первоначальный пользовательский интерфейс, разработанный для системы, представлял собой полностью аппаратный блок, называемый ALOHAnet Terminal Control Unit (TCU), и был единственным оборудованием, необходимым для подключения терминала к каналу ALOHA. TCU состоял из антенны UHF, трансивера, модема, буфера и блока управления. Буфер был разработан для полной длины строки в 80 символов, что позволяло обрабатывать как 40-, так и 80-символьные пакеты фиксированной длины, определенные для системы. Типичный пользовательский терминал в оригинальной системе состоял из телетайпа модели 33 или простого пользовательского терминала CRT, подключенного к TCU с помощью стандартного интерфейса RS-232 . Вскоре после того, как первоначальная сеть ALOHA вступила в эксплуатацию, TCU был перепроектирован с одним из первых микропроцессоров Intel, и полученное обновление было названо программируемым блоком управления (PCU).
Дополнительные базовые функции, выполняемые TCU и PCU, включали генерацию вектора кода циклической проверки четности и декодирование полученных пакетов для обнаружения ошибок пакетов, а также генерацию повторных передач пакетов с использованием простого генератора случайных интервалов. Если подтверждение не было получено от Menehune после предписанного количества автоматических повторных передач, мигающий свет использовался в качестве индикатора для пользователя-человека. Кроме того, поскольку TCU и PCU не отправляли подтверждения в Menehune, пользователю-человеку отображался постоянный предупреждающий свет, когда в полученном пакете была обнаружена ошибка. Значительное упрощение было включено в первоначальную конструкцию TCU, а также PCU для сопряжения пользователя-человека с сетью.
В более поздних версиях системы были введены в эксплуатацию простые радиорелейные устройства для соединения основной сети на острове Оаху с другими островами на Гавайях, а возможности маршрутизации Menehune были расширены, чтобы позволить узлам пользователей обмениваться пакетами с другими узлами пользователей, ARPANET и экспериментальной спутниковой сетью. [4]
Двумя основными решениями, во многом определившими конструкцию ALOHAnet, были двухканальная звездообразная конфигурация сети и использование произвольного доступа для пользовательских передач.
Двухканальная конфигурация была выбрана в первую очередь для обеспечения эффективной передачи относительно плотного общего потока трафика, возвращаемого пользователям центральным компьютером с разделением времени. Дополнительной причиной звездообразной конфигурации было желание централизовать как можно больше функций связи в центральном сетевом узле (Menehune) для минимизации стоимости исходного полностью аппаратного терминального блока управления (TCU) на каждом пользовательском узле.
Канал произвольного доступа для связи между пользователями и Menehune был разработан специально для характеристик трафика интерактивных вычислений. В обычной системе связи пользователю может быть назначена часть канала либо на основе множественного доступа с разделением по частоте , либо на основе множественного доступа с разделением по времени . Поскольку было хорошо известно, что в системах с разделением по времени (около 1970 г.) компьютерные и пользовательские данные являются пульсирующими, такие фиксированные назначения, как правило, являются расточительными по отношению к полосе пропускания из-за высоких скоростей передачи данных пик-среднее, которые характеризуют трафик.
Чтобы добиться более эффективного использования полосы пропускания для пульсирующего трафика, ALOHAnet разработал метод коммутации пакетов с произвольным доступом, который стал известен как чистый канал ALOHA . Этот подход эффективно динамически выделяет полосу пропускания немедленно пользователю, у которого есть данные для отправки, используя механизм подтверждения и повторной передачи, описанный ранее, для решения проблем с периодическими коллизиями доступа. Хотя средняя загрузка канала должна поддерживаться ниже примерно 10% для поддержания низкого уровня коллизий, это все равно приводит к лучшей эффективности полосы пропускания, чем при использовании фиксированных выделений в контексте пульсирующего трафика.
В реализованной системе использовались два канала 100 кГц в экспериментальном диапазоне УВЧ, один для канала произвольного доступа пользователь-компьютер и один для канала вещания компьютер-пользователь. Система была сконфигурирована как звездообразная сеть, позволяющая только центральному узлу принимать передачи в канале произвольного доступа. Все пользовательские TCU принимали каждую передачу, сделанную центральным узлом в канале вещания. Все передачи производились в пакетах в9600 бит/с , с данными и управляющей информацией, инкапсулированными в пакеты.
Каждый пакет состоял из 32-битного заголовка и 16-битного слова проверки четности заголовка, за которыми следовало до 80 байт данных и 16-битное слово проверки четности для данных. Заголовок содержал адресную информацию, идентифицирующую конкретного пользователя, так что когда Menehune транслировал пакет, только узел предполагаемого пользователя мог его принять.
В 1970-х годах случайный доступ ALOHA использовался в зарождающейся кабельной сети Ethernet [20] , а затем в спутниковой сети Marisat (теперь Inmarsat ). [21]
В начале 1980-х годов стали доступны частоты для мобильных сетей, а в 1985 году в США были выделены частоты, подходящие для того, что стало известно как Wi-Fi . [22] Эти нормативные разработки сделали возможным использование методов случайного доступа ALOHA как в Wi-Fi, так и в сетях мобильной телефонии.
Каналы ALOHA использовались ограниченно в 1980-х годах в мобильных телефонах 1G для сигнализации и управления. [23] В конце 1980-х годов Европейская группа стандартизации GSM , работавшая над общеевропейской цифровой системой мобильной связи GSM, значительно расширила использование каналов ALOHA для доступа к радиоканалам в мобильной телефонии. Кроме того, в мобильных телефонах 2G была реализована отправка текстовых сообщений SMS . В начале 2000-х годов дополнительные каналы ALOHA были добавлены в мобильные телефоны 2.5G и 3G с широким внедрением службы пакетной радиосвязи общего пользования (GPRS), используя канал случайного доступа ALOHA с интервалами в сочетании с версией схемы резервирования ALOHA, впервые проанализированной группой в BBN Technologies . [24]