ALOHAnet

ALOHAnet（アロハネット）とは

ALOHAnet、または単にALOHAは、1970年にハワイ大学で開発された初期のコンピュータネットワークシステムです。このシステムは、分散したキャンパス間を無線通信で接続するという革新的なアイデアに基づき、低コストでネットワークを構築することを目指しました。今日では、その技術自体は使われていませんが、その中核となるコンセプトは、現代のイーサネットの基礎を築いたとして、コンピュータネットワーク史において重要な位置を占めています。

ALOHAnetの概要

ALOHAnetは、ハワイ大学のノーマン・アブラムソンらによって1970年に開発されました。その目的は、ハワイ大学の各キャンパスを、アマチュア無線のような低コストのシステムを使って結びつけることでした。初期のバージョンでは、ハブを中心としたスター型の構成が採用され、ハブから各ノードへの送信と、各ノードからハブへの送信にそれぞれ異なる周波数が使われました。

データを送信したノードは、ハブから送り返されるデータを受信することで、送信が正しく行われたかを確認できます。もしデータが破損している場合、ノードは短い時間待ってからデータを再送します。この仕組みは、複数のノードが同時にデータを送信しようとした際に発生する衝突を検出し、対処するためにも利用されました。

ALOHAは、共有媒体を利用した最初のネットワークシステムの1つとして、ARPANETと同程度の重要性を持っています。このシステムによって、イーサネットで使用されるCSMA/CD|CSMA_CDのような、より現代的な媒体アクセス制御の必要性が明らかになりました。有線による2点間接続で構成されるARPANETとは異なり、ALOHAではすべてのノードが同じ周波数を使って通信します。そのため、どのノードがいつ送信できるかを制御するシステムが必要となりました。ALOHAが直面した課題は、現代のスイッチがないイーサネットやWi-Fiネットワークが抱える問題とよく似ています。

ALOHAのシンプルな手法は、他の研究者たちも注目しました。当時のデータ送信はテレタイプで行われていたため、データレートは80文字/秒を超えることはほとんどありませんでした。もし2つのノードが同時に送信しようとすると、混信によってデータが破壊され、手動での再送が必要でした。ALOHAは、この問題に対する解決策が必要であることを示し、パロアルト研究所のロバート・メトカーフらがイーサネットプロトコルを開発するきっかけとなりました。

ALOHAプロトコル

ALOHAプロトコルは、ブロードキャスト型ネットワーク構成のLANのためのデータリンク層（OSI第2層）通信プロトコルです。初期バージョンでは、以下のような基本的な手順に従っていました。

1. 送信したいデータがある場合、すぐに送信を開始します。
2. もし他のノードの送信と衝突が発生した場合、少し時間をおいてから再送を試みます。

この「少し時間をおく」という部分が、プロトコルの効率や伝送路容量、予測可能性に大きな影響を与えます。研究者たちは、この部分の戦略について多くの研究を行ってきました。

ALOHAとイーサネットの主な違いは、イーサネットが衝突発生時にジャミング信号を送信するCSMA/CD|CSMA_CDを採用している点です。ジャミング信号は、接続されている全てのコンピュータにパケットの破棄を指示します。伝送遅延が伝播遅延よりも大きい場合、ジャミング信号は伝送媒体を素早く解放でき、多くのイーサネット環境に適しています。一方で、ALOHAは無線システムのため、小規模LANでうまく機能するプロトコルが必ずしも有効とは限りません（隠れ端末問題など）。ハワイ諸島のネットワークでは、通信範囲が直径400kmにも及び、伝播遅延が伝送遅延よりも小さいため、プロトコルは十分な頑健性を持つ必要がありました。

Pure ALOHAの最大スループットは約18.4%であり、これは全帯域幅の約81.6%がパケットの衝突によって無駄になっていることを意味します。Pure ALOHAの効率を改善したのがSlotted ALOHAで、時間をスロットに区切ることで最大スループットを36.8%まで改善しました。各ノードは時間スロットの開始時のみ送信できるようになり、衝突の可能性を低減させました。

ALOHAの特性は、今日のWi-Fiとよく似ています。どちらも本質的に非効率性を抱えています。例えば、802.11bの理論上の最大スループットは11Mbit/sですが、少数のノードで運用しても実スループットは2Mbit/sから4Mbit/s程度です。ノード数が増加するとスループットは劇的に低下し、メッセージのバースト性が増大してもスループットは低下します。このため、遅延の予測性が重要なシステムでは、コンテンション方式よりもトークンリングなどのトークンパッシング方式が好まれます。しかし、コンテンション方式は管理が容易で、通信開始時の速度が高いという利点があります。

ALOHAnetの歴史

ノーマン・アブラムソンは、スタンフォード大学の工学教授であり、熱心なサーファーでもありました。1969年にハワイを訪れた際、彼はハワイ大学に職を求め、1970年にハワイ大学の職員となりました。彼は、ハワイ諸島間を結ぶ無線データ通信システムの開発に取り組み、ローレンス・ロバーツの協力を得ました。

1970年末には、システムは実用段階に入り、世界初の無線パケット交換ネットワークとなりました。1972年には、アブラムソンはロバーツからIMPを入手し、アメリカ本土のARPANETに接続しました。これは、ARPANETに他のネットワークが接続された最初の例であり、その後のネットワーク間接続の急増につながりました。

ALOHAプロトコルの変種（Slotted ALOHAなど）は、その後、ARDIS、Mobitex、CDPD、GSMなどの無線データネットワークの無線プロトコルとして採用されました。

ALOHAnetの解説

ALOHAnet以前のコンピュータ間通信では、データをモデムでアナログ信号に変換し、電話線などの既存の回線を通じて送信していました。これらの回線はポイントツーポイントで、手動で設定する必要がありました。対照的に、ALOHAnetは真のネットワークであり、接続されたすべてのコンピュータが、いつでも、複数のコンピュータと同時にデータを送受信できました。無線媒体を使用するため、通信路のコストはかからず、自由に利用できました。

この方式には、2つのノードが同時に送信しようとした場合に信号が衝突し、破壊されてしまうという問題がありました。この問題を解決するために、さまざまな対策が考えられました。1つの対策は、各ノードが別の周波数を使う「周波数分割多重化」でしたが、そのためには各ノードが多数の周波数帯を受信する必要があり、コストが高くなりました。別の対策として、各ノードに送信が許される時間スロットを割り当てる「時分割多重化」がありましたが、使用しないスロットが無駄になるという問題がありました。

ALOHAnetは、これらの方法とは異なるアプローチを採用しました。この方法は、後に標準化され、Carrier Sense Multiple Access（CSMA）となりました。ALOHAシステムでは、各ノードは送信すべきフレームがある場合、即座にそれを送信します。通常、無線信号が発信されると、他のノードはその送信が終わるまで送信を控えます。この問題を回避するため、ALOHAnetではメッセージを小さなパケットに分割し、パケット間に少し時間を空けて送信しました。これにより、他のノードがパケットを送信する余地が生まれ、同時に媒体を共有できるようになりました。

ただし、2つのノードが同時にブロードキャストを開始しようとした場合、やはり信号の衝突が発生します。ALOHAnetでは、送信したパケットがハブから戻ってこなかった場合、衝突が発生したと判断し、ランダムな時間だけ待ってから再送するという方法を採用しました。この衝突回避システムでは、他のノードが通信していない状況では、ネットワークの全容量を1つのノードが利用でき、事前設定も不要であるという利点がありました。しかし、ネットワークが混雑すると衝突が急増し、全体のデータスループットが低下する「輻輳崩壊」という現象が発生しました。

Slotted ALOHAでは、ハブが定期的にクロックパケットを送信し、各ノードはクロックパケットを受信した直後のみパケットを送信できます。この方式では、衝突する確率が低減し、チャンネル利用率が向上しました。ロバート・メトカーフは、このシステムを修正して有線ネットワークを開発し、これがイーサネットとなりました。現在では、これをCSMA/CD|CSMA_CD（Carrier Sense, Multiple Access, Collision Detection）と呼んでいます。

有線システムでは衝突を検出して壊れたパケットを伝送しないようにできますが、無線システムでは実装が難しいです。そのため、ALOHAnetでは衝突をチェックしていませんでした。ALOHAnetは、ハワイ州全土で9600baudの無線モデムを使って運用され、2つの100kHzのチャンネルを使用しました。ネットワークはスター型で、ハブとなるコンピュータがランダムアクセスチャネルを受信し、ブロードキャストチャネルで全体のノードに送信しました。その後、リピーターが追加され、通信可能範囲が拡大しました。パケットにはヘッダ、データ本体、パリティチェックが含まれていました。

参考文献

Kuo, Franklin F (1973年). "The ALOHA system" in Computer Networks. Prentice-Hall. pp. 501-518
Kuo, Franklin F (1995年). “The ALOHA system”. ACM Computer Communication Review: 25.

外部リンク

Dynamic Sharing of Radio Spectrum: A Brief History
ALOHA PROTOCOL
ALOHA Packet Broadcasting: A Retrospect
Norman Abramson, Lecture

もう一度検索