ALOHAnet
 |
ALOHAnet または ALOHA は、ハワイ大学が開発した先駆的コンピュータネットワークシステム。1970年に開発された。この技術自体は既に使われておらず、歴史的存在となっているが、その中核となるコンセプトはイーサネットの基盤となった。
概要
[編集]初期のコンピュータネットワーク設計の1つとして、ALOHAネットワークはハワイ大学の Norman Abramson らが1970年に生み出した。それは、低価格のアマチュア無線のようなシステムを使って、同大学の分散して存在するキャンパス間を結び、コンピュータネットワークを形成するというものであった。ALOHAの最初のバージョンはハブを中心としたスター形の構成で、2つの周波数があり、ハブから他のノードへの送信に使うチャンネルと各クライアントからハブに向かっての送信に使うチャンネルが存在した。受信したデータを即座に再送することで、クライアントはデータ受信が正しく行われたかを判断できる。データが壊れていることに気づいたマシンは短時間待ってからパケットを再送する。この機構は衝突（2つのクライアントが同時にパケットを送ろうとした状態）を検出して対処するのにも使われた。
ALOHA は転送に共有媒体を使ったという点でARPANETと同程度に重要である。これによって、イーサネットで使われているCSMA/CDのようなより現代的な媒体アクセス制御の必要性が明らかになった。有線で繋がった二点間の通信から構成されるARPANETとは異なり、ALOHAは同じ周波数で全ノードが通信を行う。そのため、ある時点でどのノードが送信できるかという制御を行うシステムが必要となった。ALOHA の直面した問題は、（スイッチの無い）イーサネットや Wi-Fi ネットワークでの問題とよく似ていた。
この転送媒体共有システムは他からも興味をもたれるようになった。ALOHAの手法は非常に単純だった。データ送信はテレタイプで行われていたため、データレートは80文字/秒を越えることはめったになかった。2つの局が同時に送信しようとした場合、混信によってどちらも送信内容が破壊された。すると、手動でデータの再送を行う必要があった。ALOHA はこの問題を解決しないと便利なネットワークができないことを証明し、そのことが他者の興味を引き、特にパロアルト研究所のロバート・メトカーフらが注目した。メトカーフらはイーサネットプロトコルを生み出すことになった。
ALOHA プロトコル
[編集]
ALOHAプロトコルは、ブロードキャスト型ネットワーク構成のLANのためのデータリンク層（OSI第2層）通信プロトコルである。
当初のバージョンでは、基本的に次のようなプロトコルになっていた。
- 送信したいデータがある場合、それを送信する。
- 別の転送とそのメッセージが衝突した場合、「後で」再送を試みる。
多くの人々がこのプロトコルを研究してきた。最も重要なのは「後で」という部分である。この部分の戦略は、プロトコル全体の効率、伝送路容量、予測可能性に重大な影響を及ぼす。
ALOHAとイーサネットの違いは、イーサネットではCSMA/CDを採用しているという点である。これは衝突発生時に接続している全コンピュータにジャミング信号をブロードキャストし、各コンピュータに現在のパケットやフレームを捨てさせる。伝送遅延が伝播遅延に比べて支配的な場合、ジャミング信号を使うと伝送媒体を素早く解放でき、多くのイーサネットに適している。ALOHAは無線システムなので、小規模のLANではうまく機能するプロトコルでも常にうまく機能するとは限らないという問題もある（隠れ端末問題など）。ハワイ諸島のネットワークの通信範囲は直径400kmだったが、伝播遅延はほぼ確実に伝送遅延に比べて小さかったため、プロトコルは十分な頑健性を備えている必要があった。
Pure ALOHA の最大スループットは約18.4%であった。これは、全帯域幅の約81.6%がパケットの衝突によって無駄に費やされていたことを意味する。基本スループット計算は、2X秒間に平均で2G回の到着があり、全体としてポアソン分布に従うと仮定して行う。G = 0.5 のときピークとなり、最大スループットは 0.184 すなわち 18.4% となる。
Pure ALOHA を改良したのが Slotted ALOHA で、離散型時間スロットを導入して最大スループットを36.8%まで改善した。各局は時間スロットの開始時刻でのみ送信できるようにし、それによって衝突を削減した。この場合、2X秒間に最大G個の到着となる。最大スループットは G = 1 のときになる。
ALOHAの特性は、今日の Wi-Fi のそれとそれほど違わない。どちらも本質的な非効率性を有している。例えば、802.11bは理論上の最大スループットは11Mbit/sだが、少数の局で運用しても実スループットは2Mbit/sから4Mbit/sとなる。ユーザー数が増えるとネットワークのスループットは劇的に低下するし、メッセージのバースト性が増大してもスループットは低下する。このため、遅延の予測性が重視されるシステムでは、コンテンション方式よりもトークンリングなどのトークン・パッシング方式の方が好まれる。例えば、組み込み用途ではARCNETがよく使われる。それでもコンテンション方式にも利点があり、管理が容易で通信開始時の速度が高い。
歴史
[編集]Norman Abramson はスタンフォード大学の工学教授だったが、同時に熱心なサーファーでもあった。1969年にハワイ州を訪れると、彼はハワイ大学に職を求めた。1970年にハワイ大学職員になり、ハワイ諸島間をつなぐ無線データ通信システムの開発に携わった。これにはローレンス・ロバーツの援助があった。
1970年末にはシステムは実用に移行し、世界初の無線パケット交換ネットワークとなった。Abramson はロバーツからなんとかしてIMPを入手し、1972年にはアメリカ本土とARPANETで接続した。これはARPANETに初めて他のネットワークが接続された事例であり、その後急激にネットワーク間接続が増えていった。
ALOHAプロトコルの変種（Slotted ALOHA など）も後に登場し、無線データネットワーク用の無線プロトコルとして ARDIS、Mobitex、CDPD、GSM などが生み出された。
解説
[編集]ALOHAnet以前、多くのコンピュータ間通信は似たような機能を共有していた。送信すべきデータはモデムなどの機器を使ってアナログ信号に変換され、電話線などの既知のコネクション上を送信される。コネクションはポイントツーポイントであり、一般に手動制御で設定されていた。
それとは対照的にALOHAnetは真のネットワークであった。ALOHAnetに接続された全コンピュータは、オペレータが手をかけなくとも何時でもデータを送信でき、同時に複数のコンピュータがやりとりできる。媒体は無線であるため、通信路自体にはコストはかからず、いつでも好きなように使えた。
このような方式ではある重大な問題が生じる。2つのノードが同時に送信しようとしたとき、2つの信号が混信によって破壊されてしまう問題である。この問題に対処する何らかのシステムが必要となる。そして、対処方法は様々なものが考えられる。
1つの対策は、各ノードが別の周波数を使う方法である。これを「周波数分割多重化」と呼ぶ。しかし、そのためには各ノードが他のマシンの使っているあらゆる周波数帯を受信できなければならない。ネットワークが拡大していけば、周波数帯は数百にもなり、そのような多数の周波数帯を同時に受信できる機構は非常に高価になる。
別の対策は、各ノードに送信が許される「時間スロット」を割り当てる方法である。これを「時分割多重化」と呼ぶ。これは各ノードが同じ周波数帯を使い続けられるので、より実装が容易である。しかし、あるノードが送信すべきデータを持っていない場合、その時間スロットは無駄になるという問題がある。従って、ノード数が増えるとほとんどの時間スロットは全く使われず、送信データを持っているノードに割り当てられた時間スロットだけが使われ、しかも送信速度は非常に遅いという結果を招く。
ALOHAnet はこれらとは異なる方法を採用した。これが後に標準化され Carrier Sence Multiple Access (CSMA) となった。ALOHAシステムでは各ノードは送信すべきフレームがあるときは即座にそれを送信する。
通常これは、無線信号をどれかのノードが発し始めると、他のノードはそれが終わるまで送信できないことを意味する。この問題を避けるため、ALOHAnetではメッセージを小さなパケットに分割し、パケットとパケットの間に少し時間を空けて送信するようにした。これにより、他のノードがパケットを送信する余地が生じ、同時に媒体を共有できるようになる。
考慮すべき問題は残っている。2つのノードが同時にブロードキャストを開始しようとした場合、やはり混信によるデータ破壊が生じる。ALOHAnetでは非常に賢い対処法を発明した。パケットを送信した後、送信ノードは中央のハブがそのメッセージを送り返すのを待ち受ける。メッセージが戻ってきたら、次のパケットを送信する。
送信したパケットが戻ってこなかった場合、他のノードのパケットとの衝突など、何らかの問題が生じてそれがハブに到達しなかったと判断できる。その場合、ノードはランダムな時間だけ待ち、再送する。待ち時間はランダムなので、衝突を起こした複数のノードのうち1つが最初に再送を試み、他のノードは再送しようとしたときに別のノードがチャンネルを使っていることを知る。多くの状況では、これで衝突が避けられる。
このような衝突回避システムでは、他のノードが全く通信していない状況ではネットワークの全容量を1つのノードが利用できるという利点がある。また事前の設定も不要である。周波数と時間スロットがわかっていれば、ノードを追加して即座に通信を開始できる。
しかし、ネットワークが混雑してくると、衝突発生回数が急激に増加していく。ALOHAnetの最大チャンネル利用率は約18%であった。これ以上にネットワークを利用しようとすると衝突が増大し、全体としてのデータスループットは低下する。この現象を輻輳崩壊と呼ぶ。
Slotted ALOHA では、ハブが小さいクロックパケットを定期的に各局に送信する。各局はクロックパケットを受信した直後だけパケットを送信できる。1つの局だけがパケットを送信した場合、そのパケットでは衝突が発生しないことが保証される。2つ局が同時にパケットを送信した場合、常に衝突となり、次のクロックパケットまでの時間が無駄となる。この方式では従来と比較して衝突する確率が半分になり、全体としてチャンネル利用率が向上する。
利用率が低ければ、それだけ安価で済む。ロバート・メトカーフは、このシステムを若干修正した有線ネットワークを開発し、これがイーサネットになった。現在では、これをCSMA/CD (Carrier Sense, Multiple Access, Collision Detection) と呼んでいる。
衝突検出機構は有線システムに適しており、無線システムでは実装が難しい。そのため、ALOHAnetでは衝突をチェックすることもしていなかった。有線システムでは、衝突を検出して壊れたパケットを伝送しないようにでき、送信元にそれを通知することができる。無線システムではこれは適切な手法ではなく、ALOHAでも試みることはなかった。
ALOHAnet はハワイ州全土で9600baudの無線モデムを使って運用された。2つの100kHzのチャンネル（周波数帯）を使い、一方は413.475MHzの「ブロードキャスト・チャンネル」、もう一方は407.350MHzの「ランダムアクセス・チャンネル」とされた。ネットワークはスター形で、中心のハブとなるコンピュータ（HP 2100）がランダムアクセス・チャンネルを受信して全メッセージを受け取り、受け取ったメッセージをブロードキャスト・チャンネルで全体に送信（ブロードキャスト）する。ブロードキャスト・チャンネルに送信するのはハブだけなので、こちらでは衝突は発生しない。その後、ハブのように機能するリピータが追加され、通信可能範囲が広がり、ネットワークとしての利便性も向上した。
パケットには32ビットのヘッダと16ビットのパリティチェックがあり、その後に80バイトのデータ本体と16ビットのパリティチェックが続く。ARPANETと接続後、ALOHAがIPパケットを使ったのか、それともオアフ島の局で変換して従来からのパケット形式を使ったのかは不明である。
参考文献
[編集]- 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.