Главная
Новости
Строительство
Ремонт
Дизайн и интерьер

















Яндекс.Метрика





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

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

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

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

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

Рассмотрим передачу некоего выделенного кадра данных. Пакет принимается некорректно если в момент начала его трансляции передавала другая станция, либо если до конца трансляции начала передавать ещё одна станция. Таким образом, для успешной передачи любого выделенного блока данных необходимо, чтобы в течение интервала времени 2 τ {displaystyle 2 au } ни одна другая станция не начала передачу. Вероятность этого события есть P s u c = e − 2 G {displaystyle mathbb {P} _{mathrm {suc} }=e^{-2G}} . Среднее число успешно переданных за время τ {displaystyle au } пакетов, то есть пропускная способность сети, составляет λ p u r e ( G ) = G P s u c = G e − 2 G {displaystyle lambda _{pure}(G)=Gmathbb {P} _{mathrm {suc} }=Ge^{-2G}} .

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

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

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

При приведённых ранее допущениях оценка пропускной способности слотированной ALOHA определяется следующим образом. Так как пакеты данных передаются исключительно в границах слотов, для того, чтобы несколько терминалов начали передавать одновременно, они должны получить данные для передачи в течение одного и того же слота. Вероятность этого события составляет P f a i l = 1 − e − G {displaystyle mathbb {P} _{mathrm {fail} }=1-e^{-G}} . Тогда вероятность успешно передать пакет данных есть P s u c = e − G {displaystyle mathbb {P} _{mathrm {suc} }=e^{-G}} , а пропускная способность сети равна λ s l o t ( G ) = G P s u c = G e − G {displaystyle lambda _{slot}(G)=Gmathbb {P} _{mathrm {suc} }=Ge^{-G}} .

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

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

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

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

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

λ p u r e ( G ) = G e − 2 G {displaystyle lambda _{pure}(G)=Ge^{-2G}}

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

G p u r e ∗ = arg ⁡ max G ∈ R +   λ p u r e ( G ) {displaystyle G_{pure}^{*}=arg max _{Gin mathbb {R} ^{+}}~{lambda _{pure}(G)}} .

λ p u r e ( 0 ) = lim G → + ∞ λ p u r e ( G ) = 0 {displaystyle lambda _{pure}(0)=lim _{G o +infty }{lambda _{pure}(G)}=0} .

d λ p u r e ( G ) d G = e − 2 G − 2 G e − 2 G {displaystyle {frac {dlambda _{pure}(G)}{dG}}=e^{-2G}-2Ge^{-2G}} .

d λ p u r e ( G ) d G | G p u r e ∗ = e − 2 G p u r e ∗ − 2 G p u r e ∗ e − 2 G p u r e ∗ = 0 ⇒ G p u r e ∗ = 1 2 {displaystyle {Bigl .}{frac {dlambda _{pure}(G)}{dG}}{Bigr |}_{G_{pure}^{*}}=e^{-2G_{pure}^{*}}-2G_{pure}^{*}e^{-2G_{pure}^{*}}=0Rightarrow G_{pure}^{*}={frac {1}{2}}} .

λ p u r e ( G p u r e ∗ ) = 1 2 e ≈ 0.18393972... {displaystyle lambda _{pure}(G_{pure}^{*})={frac {1}{2e}}approx 0.18393972...} .

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

λ s l o t ( G ) = G e − G {displaystyle lambda _{slot}(G)=Ge^{-G}} .

G s l o t ∗ = arg ⁡ max G ∈ R +   λ s l o t ( G ) {displaystyle G_{slot}^{*}=arg max _{Gin mathbb {R} ^{+}}~{lambda _{slot}(G)}} .

λ s l o t ( 0 ) = lim G → + ∞ λ s l o t ( G ) = 0 {displaystyle lambda _{slot}(0)=lim _{G o +infty }{lambda _{slot}(G)}=0} .

d λ s l o t ( G ) d G = e − G − G e − G {displaystyle {frac {dlambda _{slot}(G)}{dG}}=e^{-G}-Ge^{-G}} .

d λ s l o t ( G ) d G | G s l o t ∗ = e − G s l o t ∗ − G s l o t ∗ e − G s l o t ∗ = 0 ⇒ G s l o t ∗ = 1 {displaystyle {Bigl .}{frac {dlambda _{slot}(G)}{dG}}{Bigr |}_{G_{slot}^{*}}=e^{-G_{slot}^{*}}-G_{slot}^{*}e^{-G_{slot}^{*}}=0Rightarrow G_{slot}^{*}=1} .

λ s l o t ( G s l o t ∗ ) = 1 e = 2 λ p u r e ( G p u r e ∗ ) ≈ 0.36787944... {displaystyle lambda _{slot}(G_{slot}^{*})={frac {1}{e}}=2lambda _{pure}(G_{pure}^{*})approx 0.36787944...} .

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

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

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

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

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

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

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