Просмотр кода страницы ALOHAnet

'''ALOHAnet''' — первая компьютерная [[Вычислительная сеть|сеть]] передачи данных с [[Коммутация пакетов|пакетной коммутацией]], использовавшая в качестве среды доступа к ней беспроводную технологию. Была разработана и введена в эксплуатацию в 1968—1970-х годах группой учёных [[Гавайский университет|Гавайского университета]] под руководством {{Не переведено 5|  Абрамсон, Норман| Нормана Абрамсона|4 = Norman Abramson}} в рамках исследовательского проекта THE ALOHA SYSTEM, основной целью которого было изучение возможностей использования радиопередачи как альтернативы проводным коммуникациям. Концептуальные наработки и решения, реализованные в ходе этого проекта, во многом легли в основу таких технологий и протоколов как [[Ethernet]], [[Wi-Fi]] и [[Сотовая сеть|сотовые сети]]{{sfn|Schwartz, Abramson|2009}}[[Сотовая сеть|.]] В 1973 году в сеть с использованием спутниковых каналов связи [[НАСА|NASA]] {{Не переведено 5|ATS-1|4 = ATS-1}} были объединены вычислительные центры Гавайского университета, [[Исследовательский центр Эймса|Исследовательского центра Эймса]] (NASA), {{Нп5|Университет Аляски (Анкоридж)|Университета Аляски|4 = University of Alaska Anchorage}}, [[Университет Тохоку|Университета Тохоку]], [[Университет электрокоммуникаций|Университета электрокоммуникаций (Токио)]] и [[Сиднейский университет|Сиднейского университета]]<ref>{{cite web|title=2011 Recipients of C&C Prize|url=http://www.candc.or.jp/en/2011/group_b.html|publisher=NEC C&C Foundation|accessdate=2016-01-03|archive-date=2015-06-04|archive-url=https://web.archive.org/web/20150604110904/http://www.candc.or.jp/en/2011/group_b.html|deadlink=no}}</ref>.

== История ==
В 1968 году профессор [[Стэнфордский университет|Стэнфордского университета]] Норман Абрамсон начал работать в Гавайском университете, где возглавил команду исследователей, в которую входили Томас Гаардер ({{Lang-en|Thomas Gaarder}}), Франклин Куо ({{Lang-en|Franklin Kuo}}), Чу Линь ({{Lang-en|Shu Lin}}), {{Не переведено 5|Питерсон, Уэсли|Уэсли Питерсон|4 = W. Wesley Peterson}} и Эдвард Уэлдон ({{Lang-en|Edward Weldon}}), которая начала исследования по программе The Aloha System — возможности использования радиосвязи для взаимодействия пользователей больших компьютерных систем вместо [[Провод|проводных соединений]]{{sfn|Schwartz, Abramson|2009}}. Первоначально предполагалось объединить в одну сеть главный кампус Гавайского университета, расположенный в долине Маноа — неподалёку от [[Гонолулу]], с колледжем в [[Хило]] и колледжами на островах [[Оаху]], [[Кауаи]], [[Мауи]] и [[Гавайи]]. Все они располагались на расстоянии около 300 км от вычислительного центра. В перспективе предполагалось использовать сеть в масштабах страны{{sfn|Schwartz, Abramson|2009}}{{sfn|Kuo|1995}}.

Вычислительный центр главного кампуса университета состоял из [[Компьютер|ЭВМ]] [[IBM System/360|IBM 360/65]] с 750 [[Килобайт|КБ]] [[Оперативная память|оперативной памяти]] и нескольких машин меньшей производительности. Для взаимодействия с ними машин колледжей планировалось использование [[Дециметровые волны|дециметрового диапазона радиочастот]] в качестве среды передачи данных. Разработка экспериментальной компьютерной сети началась в сентябре 1968 года, а в 1971 году ALOHAnet начала работать{{sfn|Schwartz, Abramson|2009}} (слово «[[Алоха|aloha]]» на [[Гавайский язык|гавайском языке]] означает приветствие)<ref>{{публикация|книга|автор=Семенов Ю.А.|заглавие=Telecommunication technologies - Телекоммуникационные технологии|часть=Беспроводные (радио) каналы и сети|ссылка часть=http://book.itep.ru/3/radio_33.htm#aloha|год=2014}}</ref>.

== Технология ALOHAnet ==

В сети ALOHAnet для соединения компьютеров с главным вычислительным центром использовалось радиосоединение в дециметровом диапазоне волн{{sfn|Kuo|1995}}. Было выделено два радиоканала шириной 100 [[Герц (единица измерения)|КГц]]{{sfn|Schwartz, Abramson|2009}} со скоростью передачи данных по ним 24 000 [[бод]]{{sfn|Kuo|1995}}. Один радиоканал на частоте 407,350 МГц{{sfn|Schwartz, Abramson|2009}} использовался для передачи данных от терминалов к центральному компьютеру{{sfn|Binder, Abramson, Kuo et al.|1975}} в Гонолулу, а второй канал на частоте 413,475 МГц{{sfn|Schwartz, Abramson|2009}} использовался для рассылки [[Широковещательный канал|широковещательных]] сообщений от центрального компьютера терминалам{{sfn|Binder, Abramson, Kuo et al.|1975}} (для этого возле центрального компьютера была установлена широковещательная [[антенна]], а на удалённых островах — [[Диаграмма направленности|направленные антенны]], не позволявшие принимать сообщения друг от друга — в системе ALOHA использовалась [[сетевая топология]] звезда){{sfn|Таненбаум, Уэзеролл|2012}}.

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

=== Чистая ALOHA ===

[[Файл:Pure ALOHA1 ru.svg|мини|Чистая система ALOHA. Светлыми прямоугольниками изображены успешно переданные кадры, тёмными — попавшие в коллизию]]

Первую версию ''ALOHA random access'' также называют чистой ALOHA ({{Lang-en|pure ALOHA}}). При использовании этого метода доступа к каналу пользовательские компьютеры начинают передавать центральному пакеты данных сразу же после появления предназначенной для пересылки информации. Если передача двух или большего числа станций совпадают по времени (хотя бы частично), то центральный компьютер не может корректно принять данные. Чтобы дать отправителям возможность обнаружить коллизию, центральный компьютер рассылает полученный пакет данных после приёма. Сравнивая переданный пакет и принятый, отправитель может понять, были ли его данные приняты корректно или с ошибками. Если данные были переданы некорректно, отправитель выжидает случайный интервал времени и совершает повторную попытку передачи{{sfn|Таненбаум, Уэзеролл|2012}}.

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

[[Файл:PureALOHA2.svg|мини|Для того, чтобы красный кадр попал в коллизию, необходимо начать передачу синего кадра в течение интервала времени длительностью <math>2 \tau</math>]]

Оценка пропускной способности чистой системы ALOHA определяется при следующих предположениях{{sfn|Таненбаум, Уэзеролл|2012}}{{sfn|Abramson|1970}}:

* Пользовательские данные, предназначенные для передачи, поступают на терминалы случайно, образуя [[Процесс Пуассона|пуассоновский поток]];
* Отброшенные из-за ошибок передачи пакеты передаются повторно, образуя также пуассоновский поток;
* Все пакеты данных имеют одинаковую длину и передаются одинаковое время <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|Таненбаум, Уэзеролл|2012}}.

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

[[Файл:Slotted ALOHA ru.svg|мини|Слотированная система ALOHA. Пунктирные линии означают границы слотов]]

В 1972 году [[Робертс, Лоуренс|Лоуренс Робертс]] предложил другую версию системы ALOHA, названную слотированной ALOHA ({{Lang-en|slotted ALOHA}}){{sfn|Roberts|1975}}. Основным отличием слотированной ALOHA от чистой являлась идея разделения оси времени на дискретные интервалы равной длительности <math>\tau</math>, названные слотами. Каждый терминал последовательно отмерял границы слотов. Для синхронизации границ слотов использовался специальный синхронизирующий сигнал, передаваемый с широковещательной антенны всем терминалам. При появлении предназначенных для передачи пакетов данных терминал задерживал передачу до начала следующего слота. Длительность слотов выбиралась так, чтобы за время одного слота терминал успел передать свой пакет данных и получить от центрального компьютера подтверждение успешной передачи{{sfn|Таненбаум, Уэзеролл|2012}}.

==== Оценка пропускной способности слотированной 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|Таненбаум, Уэзеролл|2012}}.

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

На следующем графике изображены зависимости пропускной способности чистой и слотированной систем ALOHA от поступающего на терминалы [[Сетевой трафик|трафика]] <math>G</math>.

[[Файл:ALOHAthr.png|border|Пропускная способность чистой и слотированной ALOHA]]

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

{{Вывод|title = Вывод максимума пропускной способности для чистой и слотированной ALOHA|expanded=1|

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

<math>\lambda_{pure}(G) = G e^{-2 G}</math>

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

<math>G^*_{pure}= \arg\max_{G \in \R^+}~{\lambda_{pure}(G)}</math>.

<math>\lambda_{pure}(0)=\lim_{G \to +\infty}{\lambda_{pure}(G)} = 0</math>.

<math>\frac{d\lambda_{pure}(G)}{dG} = e^{-2 G} - 2 G e^{-2 G}</math>.

<math>\Bigl. \frac{d\lambda_{pure}(G)}{dG} \Bigr|_{G^*_{pure}} = 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|Таненбаум, Уэзеролл|2012}}.

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

Появление в сети ALOHAnet [[Ретранслятор|радиоретрансляторов]]  позволило расширить и упорядочить её структуру{{sfn|Binder, Abramson, Kuo et al.|1975}}. В 1973 году ALOHAnet была подсоединена к сети [[ARPANET|ARPAnet]] с использованием спутникового канала связи{{sfn|Kuo|1995}}.

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

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

Сильно модифицированная версия слотированной ALOHA используется при коммуникации нескольких [[RFID]] меток с одним считывателем{{sfn|Таненбаум, Уэзеролл|2012}}.

== Примечания ==
{{примечания|3}}

== Литература ==
* {{source|Q22116977|ref=Abramson|ref-year=1970}} <!-- THE ALOHA SYSTEM: another alternative for computer communications // AFIPS '70 (Fall) — 1970 -->
* {{source|Q22117499|ref=Roberts|ref-year=1975}} <!-- ALOHA Packet System with and Without Slots and Capture // SIGCOMM Comput. Commun. Rev. — 1975-->
* {{source|Q22116907|ref=Binder, Abramson, Kuo et al.|ref-year=1975}} <!-- ALOHA Packet Broadcasting: A Retrospect // AFIPS '75 — 1975 -->
* {{source|Q22117490|ref=Kuo|ref-year=1995}} <!-- The ALOHA System // SIGCOMM Comput. Commun. Rev. — 1995-->
* {{source|Q22116856|ref=Schwartz, Abramson|ref-year=2009}} <!-- The Alohanet — surfing for wireless data // IEEE Communications Magazine — 2009 -->
* {{source|Q22117187|ref=Таненбаум, Уэзеролл|ref-year=2012|pages=286—290}} <!-- Компьютерные сети -->

== Ссылки ==
* {{книга|автор=James Pelkey|часть=ALOHANET and Norm Abramson: 1966 - 1972|заглавие=Entrepreneurial Capitalism and Innovation: A History of Computer Communications 1968-1988|ссылка=|ссылка часть = http://www.historyofcomputercommunications.info/Book/4/4.10-ALOHANETNormAbramson-66-72.html}}
* {{cite web|title=2011 Recipients of C&C Prize|url=http://www.candc.or.jp/en/2011/group_b.html|publisher=NEC C&C Foundation|accessdate=2016-01-03}}
* {{Статья|автор = Аганесов Артур Валерьевич|заглавие = МОДЕЛЬ СЕТИ СПУТНИКОВОЙ СВЯЗИ НА ОСНОВЕ ПРОТОКОЛА СЛУЧАЙНОГО МНОЖЕСТВЕННОГО ДОСТУПА S-ALOHA|ссылка = http://cyberleninka.ru/article/n/model-seti-sputnikovoy-svyazi-na-osnove-protokola-sluchaynogo-mnozhestvennogo-dostupa-s-aloha|язык = |издание = Системы управления, связи и безопасности|тип = |год = 2015|месяц = |число = |том = |номер = 2|страницы = |issn = }}

{{Добротная статья|Компьютеры}}


[[Категория:Сетевые протоколы]]
[[Категория:Компьютерные сети]]