2005年10月13日

メトカフの3つの原理(EJ1695号)

 アロハ・システムの話を続けます。ホストのIBMシステム3
60は、ホノルルのハワイ大学に置かれており、端末はその半径
200マイルの広大な範囲に分散していたのです。こういう状況
では無線しか対応のしようがなかったのです。
 データの基本単位をパケットに分割し、それぞれのパケットに
は宛先を示すベッダをつけて、ホスト・コンピュータ(IBMシ
ステム360)に接続されているIMPというミニ・コンピュー
タに送り、IMP経由で目的のホストに到着、そこで再合体され
て元のデータになる――既にご説明したパケット交換システムで
すが、これを無線でやろうというのです。
 ところで、このミニ・コンピュータIMPには従来のマシンに
はなかった無線通信を使うなどの工夫が加えられたこともあって
エブラムソンはあえてIMP(インプ)とは呼ばず、「メナフー
ニ」という洒落た名前をつけたのです。メナフーニとは「ハワイ
の小鬼」という意味です。
 アロハ・システムは無線通信だけではなく、いつくか新機軸が
取り入れられていたのです。もともとは時分割処理システム――
端末を中央のコンピュータに繋げて多くの人がコンピュータを共
同で使うシステムなのですが、ハワイの島々に置かれていた遠隔
端末がちょうどミニ・コンピュータ――具体的にはDEC社のP
DP−8に置き換えられつつあったのです。そして、それぞれの
PDP−8がメナフーニをパケット交換機として使って、互いに
通信をはじめていたのです。
 つまり、遠隔端末を中央のIBMシステム360に繋げるだけ
ではなく、メナフーニを通して端末同士の通信が行われていたと
いうわけです。この場合、メナフーニをルータと考えれば、現代
の通信に非常に近いものになっていたことです。
 ロバート・メトカフがエブラムソンの論文で最も関心を持った
のは、無線のパケット通信方式の理論の部分だったのです。メト
カフは次のようにいっています。
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 アロハ・ネットワークが興味深いのは、メナフーニに入ってく
 るパケットが中央から制御されていないということだった。パ
 ケットは端末で発信の準備が出来たらそのまま発信されており
 パケットにどの端末から発信されたかという情報がつけられて
 いた。そしてもし、メナフーニに入る前に干渉されてしまった
 場合、メナフーニが受け取ったという信号を発信してこないた
 め、端末は再度、ランダムに選んだ間隔をおいてパケットを発
 信する。こうしてランダムに間隔が選ばれることによって、繰
 り返し干渉が起こることを避けるという仕組みになっていた。
 ―――喜多千草著、『起源のインターネット』より。青土社刊
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 少し解説する必要があると思います。エブラムソンのやったこ
とを簡単にいうと、次の3つにまとめられます。
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 1.パケットが届いたら、それを送信元に信号で知らせる
 2.パケットの着信信号が戻ってこないときは再送信する
 3.そのさい再送信するときの待ち時間はランダムにする
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 一番工夫が行われたのは3の部分です。ハワイの島々にある複
数の端末から同時にパケットを送信すると、同じ周波数の電波を
使っているので、どうしてもパケットの衝突(コリジョン)が起
こってしまうのです。
 コリジョンが起こるとパケットは使えなくなる――つまり、こ
の場合、届いたことを示す信号が戻ってこないので、それらのパ
ケットを再送信することになるのですが、各端末が同じタイミン
グで再送信すると再びコリジョンが発生するということになって
しまうのです。これを防ぐためにエブラムソンは各端末のパケッ
ト再送信のタイミングをランダムにして、コリジョンを減らすこ
とに成功したのです。
 「モデルがきれい過ぎる」――メトカフは、この3の部分の工
夫の素晴らしさを称えながらもこう考えたのです。エブラムソン
は、ポワッソンの待ち行列理論を単純に使っていたからです。な
ぜなら、このモデルであれば周波数帯の利用量が17%以上にな
ると、再送信がうまくいかなくなるからです。つまり、パケット
の通信量(トラフィック)が増えると、効率がダウンしてしまう
欠陥があったのです。
 メトカフはこの部分についてハワイにいる間にエブラムソンと
徹底的に議論しています。そして、PARCに戻ってからその解
決策を考案してまとめ、ハーバード大学に博士論文として提出し
たのです。この論文は受理され、メトカフは念願の博士号を手に
したのです。
 アロハ・システムの周波数帯における不安定性は、新しいモデ
ルによってパケット通信量を基礎にした再送信の率の制御を行え
ば、相当通信量が多くなっても周波数帯を安定させておくことが
できることがわかったのです。これは「バックオフ・アルゴリズ
ム」といわれています。
 このようにして、メトカフは、次の3つの基本原理なるものを
まとめます。後に「イーサネット」と呼ばれるネットワークの基
本原理となる3つの原理です。
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 1.キャリア・センス ・・・・・・・ CS
   ・ケーブル上に信号が流れているかどうかをチェック
 2.コリジョン検出システム ・・・・ CD
   ・コリジョンが発生したら、速やかにそれを検出する
 3.バックオフ・アルゴリズム ・・・ MA
   ・パケットの再送信する待ち時間をランダム化させる
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 この原理は現在では「CSMA/CD」と呼ばれ、イーサネッ
トの基本原理になっています。 ・・・・[インターネット35]


≪画像および関連情報≫
 ・ロバート・メトカフ開発の3つの基本原理

1695号.jpg
posted by 平野 浩 at 08:49| Comment(0) | TrackBack(0) | インターネットの歴史 | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前: [必須入力]

メールアドレス: [必須入力]

ホームページアドレス:

コメント: [必須入力]


この記事へのトラックバック
RDF Site Summary