ALOHAnet

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

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

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

Технология ALOHAnet

[править | править код]

В сети ALOHAnet для соединения компьютеров с главным вычислительным центром использовалось радиосоединение в дециметровом диапазоне волн[3]. Было выделено два радиоканала шириной 100 КГц[1] со скоростью передачи данных по ним 24 000 бод[3]. Один радиоканал на частоте 407,350 МГц[1] использовался для передачи данных от терминалов к центральному компьютеру[5] в Гонолулу, а второй канал на частоте 413,475 МГц[1] использовался для рассылки широковещательных сообщений от центрального компьютера терминалам[5] (для этого возле центрального компьютера была установлена широковещательная антенна, а на удалённых островах — направленные антенны, не позволявшие принимать сообщения друг от друга — в системе ALOHA использовалась сетевая топология звезда)[6].

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

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

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

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

[править | править код]
Для того, чтобы красный кадр попал в коллизию, необходимо начать передачу синего кадра в течение интервала времени длительностью

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

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

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

Рассмотрим передачу некоего выделенного кадра данных. Пакет принимается некорректно, если в момент начала его трансляции передавала другая станция, либо если до конца трансляции начала передавать ещё одна станция. Таким образом, для успешной передачи любого выделенного блока данных необходимо, чтобы в течение интервала времени ни одна другая станция не начала передачи. Вероятность этого события есть . Среднее число успешно переданных за время пакетов, то есть пропускная способность сети, составляет [6].

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

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

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

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

[править | править код]

При приведённых ранее допущениях оценка пропускной способности слотированной ALOHA определяется следующим образом. Так как пакеты данных передаются исключительно в границах слотов, для того, чтобы несколько терминалов начали передавать одновременно, они должны получить данные для передачи в течение одного и того же слота. Вероятность этого события составляет . Тогда вероятность успешно передать пакет данных есть , а пропускная способность сети равна [6].

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

[править | править код]

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

Пропускная способность чистой и слотированной ALOHA

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

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

Для чистой ALOHA критическая величина нагрузки составляет , то есть один пакет данных появляется в среднем за время . Для слотированной ALOHA критическая величина нагрузки составляет , то есть один кадр данных появляется в среднем за время [6].

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

[править | править код]

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

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

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

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

Примечания

[править | править код]
  1. 1 2 3 4 5 6 7 8 9 10 Schwartz, Abramson, 2009.
  2. 2011 Recipients of C&C Prize. NEC C&C Foundation. Дата обращения: 3 января 2016. Архивировано 4 июня 2015 года.
  3. 1 2 3 4 Kuo, 1995.
  4. Семенов Ю.А. Беспроводные (радио) каналы и сети // Telecommunication technologies - Телекоммуникационные технологии. — 2014.
  5. 1 2 3 Binder, Abramson, Kuo et al., 1975.
  6. 1 2 3 4 5 6 7 8 Таненбаум, Уэзеролл, 2012.
  7. 1 2 Abramson, 1970.
  8. Roberts, 1975.

Литература

[править | править код]
  • 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.