アロハネット

ALOHAnetはALOHAシステム[ ^{1] [2] [3]}または単にALOHAとしても知られ、ハワイ大学で開発された先駆的なコンピュータネットワークシステムでした。ALOHAnetは1971年6月に運用を開始し、無線パケットデータネットワークの最初の公開デモンストレーションを提供しました。^{[4] [5]}

ALOHAnet は、 ALOHA ランダム アクセスと呼ばれる新しいメディア アクセス方法と、実験的な極超短波(UHF) を使用して動作しました。最も単純な形式 (後に Pure ALOHA として知られるようになりました) では、リモート ユニットは 2 つの別々の無線周波数 (それぞれ着信用と発信用) を介して基地局 (Menehune) と通信しました。ノードは、送信前にチャネルが空くのを待たずに、メッセージが正常に受信されたことの確認応答を待ち、受信されなかった場合は再送信しました。ノードは、送信中に他のメッセージを検出した場合も、データを停止して再送信しました。実装は簡単ですが、これでは効率はわずか 18.4% になります。その後の進歩である Slotted ALOHA では、衝突の可能性が減ってプロトコルの効率が向上し、スループットが 36.8% に向上しました。

ALOHA はその後1970 年代にイーサネットケーブル ベースのネットワークで採用され、1980 年代初頭の規制の進展に伴い、 Wi-Fiと携帯電話ネットワークの両方で ALOHA ランダム アクセス技術を使用できるようになりました。ALOHA チャネルは 1980 年代に1G携帯電話でシグナリングと制御の目的で限定的に使用されていました。1980 年代後半には、汎欧州デジタル移動通信システム GSM に取り組んでいた欧州標準化グループGSM が、携帯電話の無線チャネルへのアクセスに ALOHA チャネルの使用を大幅に拡大しました。2000 年代初頭には、 GPRS ( General Packet Radio Service ) が広く導入されたことで、2.5G および 3G 携帯電話に追加の ALOHA チャネルが追加されました。これは、 BBN Technologiesのグループが初めて分析した Reservation ALOHA 方式のバージョンと組み合わせたスロット ALOHA ランダム アクセス チャネルを使用したものです。

初期のコンピュータネットワーク設計の 1 つである ALOHA ネットワークの開発は、1968 年 9 月にハワイ大学でノーマン エイブラムソンとフランクリン クオのリーダーシップの下、トーマス ガーダー、シュ リン、ウェズリー ピーターソン、エドワード (「ネッド」) ウェルドンとともに開始されました。目標は、低価格の商用無線機器を使用して、オアフ島と他のハワイ諸島のユーザーをオアフ島のメイン キャンパスにある中央タイムシェアリング コンピュータに接続することでした。最初のパケット ブロードキャスト ユニットは 1971 年 6 月に運用を開始しました。端末は、9600 ビット/秒のRS-232 を使用して、専用の端末接続ユニットに接続されました。 ^[6]

ALOHAはもともと、Additive Links On-line Hawaii Area（ハワイのコミュニティのためのオンライン・ネットワーキング・サービス）の頭字語として考案されました。 ^[7]

ALOHA のオリジナル バージョンでは、ハブ構成で 2 つの異なる周波数が使用され、ハブ マシンは送信チャネルで全員にパケットをブロードキャストし、さまざまなクライアント マシンは受信チャネルでハブにデータ パケットを送信していました。ハブでデータが正しく受信されると、短い確認パケットがクライアントに送信され、クライアント マシンが短い待機時間後に確認を受信しなかった場合は、ランダムに選択された時間間隔を待機した後、データ パケットが自動的に再送信されます。この確認メカニズムは、 2 つのクライアント マシンが同時にパケットを送信しようとしたときに発生する衝突を検出して修正するために使用されました。

ALOHAnet の主な重要性は、クライアントの送信に共有メディアを使用していることです。各ノードが有線または衛星回線の反対側にある 1 つのノードとしか通信できないARPANETとは異なり、ALOHAnet ではすべてのクライアント ノードが同じ周波数でハブと通信します。つまり、誰がいつ通信できるかを制御する何らかのメカニズムが必要でした。ALOHAnet のソリューションは、各クライアントがデータの送信タイミングを制御せずにデータを送信できるようにし、衝突に対処するための確認/再送信スキームを実装することでした。このアプローチにより、ノードが誰が通信できるかを 交渉する必要がなくなるため、プロトコルとネットワーク ハードウェアの複雑さが大幅に軽減されました。

このソリューションは純粋なALOHA、つまりランダムアクセスチャネルとして知られるようになり、その後のイーサネット開発とWi-Fiネットワークの基礎となりました。^[5] ALOHAプロトコルのさまざまなバージョン（スロットALOHAなど）も後に衛星通信に登場し、 ARDIS、Mobitex、CDPD、GSMなどの無線データネットワークで使用されました。

アロハネットワークはランダム化多重アクセスのメカニズムを導入しました。これは、確認応答がない場合はすぐにパケットを送信し、確認応答が受信されない場合はランダムな待機時間後に送信を繰り返すことで、デバイスの送信衝突を解決しました。^[8]受信確認されていないパケットの再送信のこのランダムな待機時間の確率分布は、アロハタイプの通信システムの安定性にとって非常に重要です。再送信の平均待機時間は通常、同じクライアントノードからの新しいパケットの生成の平均時間よりも短いですが、ネットワークの安定性を損ない、全体的なスループットの崩壊を引き起こすほど短くしてはなりません。^[9]

また、ALOHAnet がハブの送信チャネルを使用して、2 番目の共有周波数ですべてのクライアントに直接パケットをブロードキャストし、各パケット内のアドレスを使用して各クライアント ノードで選択的に受信できるようにしたことも重要でした。^[4]ハブへの受信と送信の通信には別々の周波数が使用されたため、デバイスは送信に関係なく確認応答を受信できました。

プロトコルの元のバージョン (現在は Pure ALOHA と呼ばれ、ALOHAnet に実装されているもの) は非常にシンプルでした。

• 送信するデータがある場合は、データを送信してください
• データを送信中に別のステーションからデータを受信した場合、メッセージの衝突が発生しています。すべての送信ステーションは後で再送信を試みる必要があります。

純粋な ALOHA では、送信前にチャネルがビジーかどうかをチェックしません。衝突が発生し、データを再送信する必要がある場合があるため、ALOHA では通信チャネルの容量を 100% 効率的に使用することはできません。ステーションが再送信するまでの待機時間と衝突が発生する可能性は相互に関連しており、どちらもチャネルを効率的に使用できるかどうかに影響します。つまり、後で再送信するという概念は重要な側面です。選択されたバックオフ スキームの品質は、プロトコルの効率、最終的なチャネル容量、およびその動作の予測可能性に大きく影響します。

Pure ALOHAを評価するには、スループット、つまりフレームの（成功した）送信率を予測する必要があります。^[10]まず、いくつかの単純化した仮定を立てます。

• すべてのフレームの長さは同じです。
• ステーションは、送信中または送信しようとしている間はフレームを生成することはできません。つまり、ステーションがフレームを送信中または再送信しようとしている間は、送信するフレームをさらに生成することはできません。
• 送信（新規送信と再送信の両方）を試行するステーションの集団はポアソン分布に従います。

T はチャネル上で 1 つのフレームを送信するのに必要な時間を指し、フレーム時間は T に等しい時間の単位として定義されます。Gは、送信試行量に対するポアソン分布で使用される平均を指します。つまり、平均すると、フレーム時間あたりG 回の送信試行があります。

フレームを正常に送信するために何が必要かを考えてみましょう。t はフレームを送信する予定の時刻を指します。tから始まる 1 フレーム時間の間チャネルを使用し、その間は他のすべてのステーションが送信を控えることが望ましいです。

任意のフレーム時間について、そのフレーム時間中に k 回の送信試行が行われる確率は次のとおりです。

${\displaystyle {\frac {G^{k}e^{-G}}{k!}}}$

連続する 2 つのフレーム時間における送信試行の平均回数は2Gです。したがって、連続する 2 つのフレーム時間のうち任意の 2 つについて、その 2 つのフレーム時間中にk 回の送信試行が行われる確率は次のようになります。

${\displaystyle {\frac {(2G)^{k}e^{-2G}}{k!}}}$

したがって、 tTとt+Tの間に送信試行がゼロになる確率 ( ) (つまり送信が成功する確率) は次のようになります。 ${\displaystyle Prob_{pure}}$

${\displaystyle Prob_{pure}=e^{-2G}}$

スループットは、送信試行の速度に成功確率を掛けて計算することができ、スループット（）は次のようになると結論付けられます。 ${\displaystyle S_{pure}}$

${\displaystyle S_{pure}=Ge^{-2G}}$

最大スループットはフレーム時間あたり0.5/eフレーム (のときに到達) で、これはフレーム時間あたり約 0.184 フレームです。つまり、Pure ALOHA では、正常な送信に使用される時間は全体の約 18.4% のみです。 ${\displaystyle G=0.5}$

オリジナルのALOHAプロトコルの改良版がスロットALOHAで、離散的なタイムスロットを導入し、最大スループットを向上しました。^[11]ステーションはタイムスロットの開始時にのみ送信を開始できるため、衝突が削減されます。この場合、衝突は各タイムスロットでのみ発生するため、1フレーム時間内の送信試行のみを考慮する必要があり、2つの連続したフレーム時間を考慮する必要はありません。したがって、1つのタイムスロットで他のステーションによる送信試行がゼロになる確率は次のとおりです。

${\displaystyle Prob_{slotted}=e^{-G}}$

送信にちょうどk回の試行が必要な確率は（k-1回の衝突と1回の成功）である：^[10]

${\displaystyle Prob_{slotted}k=e^{-G}(1-e^{-G})^{k-1}}$

スループットは次のとおりです。

${\displaystyle S_{slotted}=Ge^{-G}}$

最大スループットはフレーム時間あたり1/eフレーム ( G = 1 の場合に到達) で、これはフレーム時間あたり約 0.368 フレーム、つまり 36.8% になります。

スロット ALOHA は、軍隊による低データレートの戦術衛星通信ネットワーク、加入者ベースの衛星通信ネットワーク、携帯電話の通話セットアップ、セットトップ ボックス通信、および非接触RFIDテクノロジで使用されます。

予約ALOHA（R-ALOHA）は、スロットALOHAの効率性を向上させる取り組みです。予約ALOHAの改善点は、遅延が大幅に短縮され、より高いレベルの利用率を効率的にサポートできることです。効率性の比較として、シミュレーションでは、予約ALOHAは利用率80%で、利用率20～36%のスロットALOHAよりも遅延が少ないことが示されています。^[12]

スロット ALOHA と予約 ALOHA の主な違いは、スロット ALOHA では、以前の使用状況に関係なく、どのスロットでも利用できるという点です。予約 ALOHA の競合ベースの予約スキーマでは、スロットは、それを正常に使用したステーションによって一時的に「所有」されていると見なされます。さらに、予約 ALOHA では、ステーションが送信を完了すると、データの送信が停止されます。原則として、アイドル スロットはすべてのステーションで利用可能であると見なされ、競合ベースでスロットを暗黙的に予約 (利用) できます。

パケット予約多重アクセス (PRMA) は暗黙の予約方式です。一定数のスロットがフレームを形成します。各フレームの後、衛星は前のフレームの各スロットの状態をブロードキャストします。これは、次のフレームの対応するスロットの予約状態を示します。送信を希望するすべての地上局は、次のフレームの「空きスロット」の間 (つまり、前のフレームのそのスロットで誰も送信しなかったか、前のフレームのそのスロットで複数の地上局が送信したときに衝突があった)、スロット ALOHA とまったく同じように競合します。「空きスロット」中に 1 つの地上局が送信した場合、その地上局はフレームのそのスロットを予約することに成功します。つまり、対応するスロットは、将来のすべてのフレームで暗黙的に予約されます。それ以降、衛星は、その特定の地上局がフレームのそのスロットを予約したことをブロードキャストし、その地上局はフレームのそのスロット中に保証されたデータ レートで送信を継続できます。他の地上局はフレームのそのスロット中に送信しないように注意するため、予約されたスロット中に衝突は発生しません。予約スロットを持つ地上局は、送信するものがない場合は送信を停止し、予約を放棄する。衛星は、あるフレームで予約スロットがアイドル状態であることを認識し、その事実をブロードキャストする。これは、そのスロットが次のフレームで「空きスロット」になることを示す。^{[13] [14]}

スロットALOHAの最大チャネル効率は36%であるが、PRMAでは最大チャネル効率が80%に向上する。^[14]

要求割り当て多重アクセス (DAMA) は、予約 ALOHA とも呼ばれ、衛星通信でよく使用される明示的な予約方式です。DAMA は 2 つのフェーズを交互に実行します。フレームの予約フェーズでは、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 は、イーサネットの初期バージョンで使用されています。

ALOHA およびその他のランダム アクセス プロトコルには、スループットと遅延パフォーマンス特性に固有の変動性があります。このため、非常に決定論的な負荷動作を必要とするアプリケーションでは、競合システムの代わりに、マスター/スレーブ方式またはトークン パッシング方式 (トークン リングやARCNETなど)を使用する場合があります。

中央ノードの通信プロセッサは、ハワイ語で小人を意味するメネフネと呼ばれるHP 2100ミニコンピュータでした^[18]。これは、ほぼ同時期に導入されていたオリジナルのARPANETインターフェース メッセージ プロセッサ(IMP) と同様の役割から名付けられました。オリジナルのシステムでは、メネフネは受信したユーザー データを正しく UH 中央コンピュータ ( IBM System 360/65タイム シェアリング システム) に転送しました。360 から送信されるメッセージはメネフネによってパケットに変換され、キューに入れられて 9600 ビット/秒のデータ レートでリモート ユーザーにブロードキャストされました。ユーザー TCU の半二重無線とは異なり、メネフネは全二重無線機器を使用して無線チャネルに接続されました^{[19] 。}

システム用に開発された元のユーザー インターフェイスは、ALOHAnet 端末制御ユニット (TCU) と呼ばれる全ハードウェア ユニットで、端末を ALOHA チャネルに接続するために必要な唯一の装置でした。TCU は、UHF アンテナ、トランシーバー、モデム、バッファー、および制御ユニットで構成されていました。バッファーは 80 文字のフル ライン長用に設計されており、システム用に定義された 40 文字と 80 文字の固定長パケットの両方を処理できました。元のシステムの一般的なユーザー ターミナルは、標準のRS-232インターフェイスを使用して TCU に接続されたテレタイプ モデル 33またはダム CRT ユーザー ターミナルでした。元の ALOHA ネットワークが運用を開始して間もなく、TCU は最初の Intel マイクロプロセッサーの 1 つを使用して再設計され、その結果得られたアップグレードはプログラマブル制御ユニット (PCU) と呼ばれました。

TCU と PCU によって実行される追加の基本機能には、パケット エラー検出を目的とした巡回パリティ チェック コード ベクトルの生成と受信パケットのデコード、および単純なランダム間隔ジェネレータを使用したパケット再送信の生成があります。規定回数の自動再送信後に Menehune から確認応答が受信されなかった場合、点滅するライトが人間のユーザーへのインジケータとして使用されました。また、TCU と PCU は Menehune に確認応答を送信しなかったため、受信パケットでエラーが検出されると、人間のユーザーに対して点灯した警告ライトが表示されました。TCU の初期設計と PCU には、人間のユーザーをネットワークにインターフェイスするための大幅な簡素化が組み込まれました。

システムの後のバージョンでは、オアフ島のメインネットワークをハワイの他の島に接続するために単純な無線リレーが運用され、メネフネルーティング機能が拡張され、ユーザーノードが他のユーザーノード、ARPANET、実験的な衛星ネットワークとパケットを交換できるようになりました。^[4]

ALOHAnet の設計の大部分を決定づけた 2 つの基本的な選択は、ネットワークの 2 チャネル スター構成と、ユーザー送信用のランダム アクセスの使用でした。

2 チャネル構成が主に選択されたのは、中央のタイムシェアリング コンピュータからユーザーに返される比較的密度の高いトラフィック ストリーム全体を効率的に送信できるようにするためです。スター構成が選択されたもう 1 つの理由は、各ユーザー ノードの元の全ハードウェア端末制御ユニット (TCU) のコストを最小限に抑えるために、できるだけ多くの通信機能を中央ネットワーク ノード (Menehune) に集中させたいと考えたためです。

ユーザーと Menehune 間の通信用のランダム アクセス チャネルは、インタラクティブ コンピューティングのトラフィック特性に合わせて特別に設計されました。従来の通信システムでは、周波数分割多重アクセスまたは時分割多重アクセスのいずれかに基づいて、チャネルの一部がユーザーに割り当てられる場合があります。タイム シェアリング システム (1970 年頃) では、コンピューターとユーザーのデータがバースト的であることがよく知られていたため、このような固定割り当ては、トラフィックの特性であるピーク対平均データ レートが高いため、一般的に帯域幅の無駄になります。

バースト トラフィックの帯域幅をより効率的に使用するために、ALOHAnet は、純粋な ALOHAチャネルとして知られるようになったランダム アクセス パケット スイッチング方式を開発しました。このアプローチでは、前述の確認応答と再送信メカニズムを使用して、時折発生するアクセス衝突に対処し、送信するデータを持つユーザーに帯域幅を即座に動的に割り当てます。衝突率を低く維持するには、平均チャネル負荷を約 10% 未満に抑える必要がありますが、それでもバースト トラフィックのコンテキストで固定割り当てを使用する場合よりも帯域幅の効率が向上します。

実装されたシステムでは、実験用 UHF 帯域の 100 kHz チャネルが 2 つ使用されました。1 つはユーザーからコンピューターへのランダム アクセス チャネル用、もう 1 つはコンピューターからユーザーへのブロードキャスト チャネル用です。システムはスター ネットワークとして構成され、ランダム アクセス チャネルでの送信を中央ノードのみが受信できます。すべてのユーザー TCU は、ブロードキャスト チャネルで中央ノードによって行われた送信を受信しました。すべての送信は、9600 ビット/秒、データと制御情報はパケットにカプセル化されます。

各パケットは、32 ビットのヘッダーと 16 ビットのヘッダー パリティ チェック ワードで構成され、その後に最大 80 バイトのデータと、そのデータ用の 16 ビットのパリティ チェック ワードが続きます。ヘッダーには特定のユーザーを識別するアドレス情報が含まれているため、Menehune がパケットをブロードキャストすると、目的のユーザーのノードだけがそのパケットを受け入れます。

1970年代には、ALOHAランダムアクセスは初期のイーサネットケーブルベースのネットワーク^[20]で採用され、その後マリサット（現在のインマルサット）衛星ネットワーク^[21]で採用されました。

1980年代初頭にはモバイルネットワーク用の周波数が利用可能になり、1985年には米国でWi-Fiとして知られるようになったものに適した周波数が割り当てられました。 ^[22] これらの規制の進展により、Wi-Fiと携帯電話ネットワークの両方でALOHAランダムアクセス技術を使用することが可能になりました。

ALOHAチャネルは、1980年代に1G携帯電話でシグナリングと制御の目的で限定的に使用されていました。 ^[23] 1980年代後半、汎欧州デジタル移動通信システムGSMに取り組んでいた欧州標準化グループGSMは、携帯電話の無線チャネルへのアクセスにALOHAチャネルの使用を大幅に拡大しました。さらに、SMS メッセージのテキスト送信が2G携帯電話に実装されました。2000年代初頭には、GPRS（ General Packet Radio Service ）の普及に伴い、2.5Gおよび3G携帯電話に追加のALOHAチャネルが追加されました。これは、 BBN Technologiesのグループによって最初に分析されたReservation ALOHAスキームのバージョンと組み合わせたスロットALOHAランダムアクセスチャネルを使用しました。^[24]

• スタリングス、ウィリアム(1988)。データとコンピュータ通信(第 2 版)。マクミラン。pp. 296–302。ISBN 978-0-02-415451-4。
• R. メトカーフ、ゼロックス PARC メモ、ボブ メトカーフからアルト アロハ ディストリビューションへのイーサ買収に関するメモ、1973 年 5 月 22 日。
• R. Binder、「ALOHAnet プロトコル」、ALOHA システム技術レポート、ハワイ大学工学部、1974 年 9 月。
• R. Binder、WS Lai、M. Wilson、「ALOHAnet Menehune – バージョン II」、ALOHA システム技術レポート、ハワイ大学工学部、1974 年 9 月。
• N. アブラムソン、「ALOHA システム最終技術報告書」、高等研究計画局、契約番号 NAS2-6700、1974 年 10 月 11 日。
• N. Abramson「パケット ブロードキャスト チャネルのスループット」、IEEE Transactions on Communications、Vol 25 No 1、pp117–128、1977 年 1 月。
• M. Schwartz, Mobile Wireless Communications、ケンブリッジ大学出版局、2005年。
• KJ Negus、A. Petrick、「無認可帯域における無線ローカル エリア ネットワーク (WLAN) の歴史」、ジョージ メイソン大学ロー スクール カンファレンス、情報経済プロジェクト、米国バージニア州アーリントン、2008 年 4 月 4 日。
• H. Wu、C. Zhu、RJ La、X. Liu、Y. Zhang。「FASA: イベント駆動型 M2M 通信用アクセス履歴を使用した高速 S-ALOHA」(PDF) 。IEEE/ACM Transactions on Networking、2013 年。2015年 1 月 23 日にオリジナル(PDF)からアーカイブ。2015年 1 月 22 日に取得。

• 無線スペクトルの動的共有: Wayback Machineの簡単な歴史(2003-08-31 アーカイブ)
• 革命への資金提供: コンピューティング研究に対する政府の支援
• ALOHA to the Web、Norman Abramson、HICCS 特別講演、archive.today (2012-12-11 アーカイブ)
• ノーマン・エイブラムソンとALOHAnet