LANに見るEthernetとトークンリング

Ethernetとトークンリング

ちょっと回り道であるが、歴史的な発展の経緯として、近距離にあるコンピュータ同志の通信網(Local Area Network:LAN)を見てみよう。

1972年から1973年にかけてXeroxのパロアルト研究所(PARC)でEthernetが開発された。Ethernetでは、宛先のアドレスや自分のアドレス、送信するデータ、最後にエラー検出用のCRCなどを付けた一定の形式の信号を送受する。この信号の塊りをパケットと呼ぶ。

Ethernetは本質的に共通バスであり、1つのEthernetに繋がっている全装置はバスの状態を常に監視している。そして、誰もデータを送信していない期間がある長さ以上続くと、データを送りたい装置は、データをバスに載せる。この時、送信する装置が1つであれば問題ないが、2つ以上の装置が同時に送信を始めてしまうと、信号が共通バス上で重畳して混線してしまう。

監視しているバス上の信号が自分が送信したものと違う場合は送信のぶつかりが起こっているので、送信を始めた装置は送信を中止する。そして、乱数を発生して装置ごとに異なる待ち時間を決め、待ち時間後に送信を再トライする。結果として、一番早く送信をトライした装置がデータを送り始め、待ち時間の長かった装置が送信をトライするときにはバスが使用状態であるので、バスが空くまで待つことになる。このように装置ごとに乱数を発生して待ち時間を決める方式をランダムバックオフ(Random Back Off)という。

なお、チップ内やプリント基板内という短い距離の場合は、アービタでバス上の信号の衝突が起こらないようにする。アービタ方式では、各コンピュータとアービタとの間でRQ、GT線が必要となるが、LANの場合はこのような配線を持たせるのは現実的ではない。このため、Ethernetではランダムバックオフという手法で衝突を解決しているのである。

Ethernetの共通バスの使用率が低い場合には、送信待ちになっている装置は殆どの場合1つで衝突は発生しない。たまたま2つの装置の送信が衝突してもランダムバックオフで解決でき、問題は発生しない。しかし、Ethernetの使用率が高くなってくると、送信待ちになっている装置が多くなり、衝突、ランダムバックオフが頻発してなかなか送信できず、交通渋滞のような状態になって、データ伝送性能が大幅に低下してしまうという問題が発生する。

このような共通バス方式の問題の無い方式として、IBMは1980年ころにリング状の接続を行うトークンリング(Token Ring)という方式のLANを開発した。トークンリングでは、通信を行う全ての装置(ノードと呼ぶ)をリング状に接続し、順にバケツリレー式にデータを送るという方法が使われている。

そして、リングにトークンと呼ぶ特別なビット列を持つパケットを周回させる。そして、トークンを持っているノードだけが、データの送信権を持つということにする。このトークンはリング上に1個だけ存在し、最初は特別なノードがトークンを生成し、図4.7の(1)のようにトークンを次のノードに送る。受け取ったノードは、送信するデータが無ければ、(2)でトークンをそのまま次のノードに送る。つまり、どのノードにも送信するデータが無い場合は、トークンはリング上のノードを順に周回する。

一方、送信すべきデータがあるノードは、トークンを受け取ると、トークンを自分のノードに保持して、(3)で自分の送信データを次のノードに送り始める。このパケットの先頭には、パケットの種別がトークンではなくデータであることを示す情報、宛先ノード、データの長さなどの情報が含まれている。そして、送信するデータとエラーチェックビット(CRC)などが続いている。

データパケットを受け取ったノードは、宛先ノード番号を調べ、自分宛てでない場合は(4)、(5)、(6)、(7)と次々にデータパケットをバケツリレーで送っていく。なお、各ノードはパケットの先頭データを見て自分宛てでないことが分かると次のノードへの転送を始めるので、(3)が終わってから(4)が始まるという転送ではなく、送信データが長い場合には、(7)で宛先ノードにパケットの先頭が到着した時点では、送信元ノードは、まだ、後の方の送信データを送っている最中という状態になる。

各ノードのリングインタフェース部は図4.8のような構造になっている。

リングは1本のデータ線からなり、1サイクルに1ビットのデータを伝送するものでも良いが、複数の線からなり複数のビットを並列に伝送するものでも良い。

図4.8でRegと書かれているのはリングで1サイクルに伝送されるビット数分のデータを記憶するFlip Flopである。この図では、図を簡単にするため、トークンとデータの区別、宛先ノード番号などの情報は1サイクルで並列に伝送され、1つのRegに格納できるとしている。そして、図4.8の構造ではリング入力からリング出力までに2つのレジスタがあり、2サイクルの遅延が入るが、トークンや宛先の判定ロジックを速くして、1サイクルで通過できるというものもある。

Token/宛先検出回路で入力がトークンであることが検出されると、送信バッファにデータが入っていない場合は、MPXの選択をリング入力側としてトークンを通過させる。一方、送信バッファにデータがある場合はMPXを送信バッファ側に切り替えて、送信バッファのシフトレジスタの内容を、順次、次のノードに送り出す。

このデータパケットを受け取ったノードは、パケットが自分宛てでなければ、そのまま、次のノードに送り出す。一方、パケットが自ノード宛てであることが検出されると、パケットを受信バッファに取り込み、リング出力には送らない。これでリング上からこのパケットは消えることになる。受け取りノードはCRCをチェックして、正常に受信できたかエラーが発生したかなどの情報を送信元に知らせる応答パケットを送る。このパケットがリングを周回し、送信元のノードに到着すると、送信データが正しく受け取られたか、誤りがあったかが分かる。ここで誤りがあったことが分かると送信元のノードは、そのデータを再送してエラー訂正を行うが、この詳細は省略する。

そして、送信元のノードは自分のデータを送り終わると、Regに止めて置いたトークンを次のノードに送り、次のノードに送信権を渡す。このようにして、リング上に、再度、トークンが存在する状態になる。

なお、宛先ノードが故障して、パケットが正常に受け取り、消去が行われないと、そのパケットが永遠にリングを周回してしまう。また、ノードのエラーでトークンが消失して、どのノードも送信ができないということも起こり得る。このような事態に対処するため、トークンリングでは特別なノードを設け、1周以上回っているパケットを監視してそのパケットを除去したり、トークンが一定以上の時間回ってこない場合はトークンを再生したりするというような機能が設けられている。また、リングでは、故障したノードを切り離すため、リング入力とリング出力を直結して故障ノードをバイパスする機能を備えている。

トークンリングでは、送信待ちのノードが複数あっても、トークンを受け取ったノードだけが送信権を持つので送信の衝突は発生しない。また、トークンリングが開発された時代にはデータの伝送速度が遅く、1つデータの長さがリング1周の時間より長いという状況で、リングの空き時間も問題にならなかった。このように、トークンリングでは衝突とランダムバックオフのようなムダが発生せず、Ethernetに比べて性能や安定性が高いというメリットがある。

しかし、その後、ムーアの法則でトランジスタの値段が下がり、スイッチングハブなどが安価に出回るようになるとEthernetの問題も軽減され、結果としてLANの分野ではEthernetが全盛という状況になっている。