2.6 多元接続ネットワーク

Xerox の PARC (Palo Alto Research Center, パロアルト研究所) で 1970 年代中ごろに開発されたイーサネット (Ethernet) は、多くの競合テクノロジに打ち勝って現在ローカルエリアネットワークにおける支配的なテクノロジとなった。イーサネットと唯一競合するテクノロジとして無線ネットワーク用の IEEE 802.11 があるものの、イーサネットはキャンパスネットワークやデータセンターで圧倒的によく利用される。イーサネットの裏にある技術には CSMA/CD (Carrier Sense Multiple Access/Collision Detect, 搬送波感知多元接続/衝突検出) という一般的な名前が付いている。

CSMA/CD の「MA (Multiple Access, 多元接続)」からも分かるように、イーサネットは多元接続ネットワークである。つまり、いくつかのノードの集合が共有のリンクを通してフレームの送受信を行う。そのためイーサネットは複数の基地が接続されたバスだと考えることができる。CSMA/CD の「CS (Carrier Sense, キャリア感知)」はリンクがアイドルなのかビジーなのかを全てのノードが確認できることを意味する。また「CD (Collision Detect, 衝突検出)」はノードがフレームの転送を行うときに信号の確認も同時に行い、自身が転送しているフレームと他のノードが転送するフレームの干渉 (衝突) を検出できることを意味する。

イーサネットはハワイ諸島の間でコンピューター通信を行うためにハワイ大学で開発された Aloha と呼ばれる初期の無線パケット通信ネットワークにルーツを持つ。Aloha とイーサネットが解決しなければならなかったのは、共有された媒体に対するアクセスを公平かつ効率良く調停するという基礎的な問題だった (媒体は Aloha では大気、初期のイーサネットでは同軸ケーブルである)。Aloha とイーサネットはどちらも、アルゴリズムを使って各ノードが転送できる時間を制御するという考え方が中心にある。

現代のイーサネットリンクはほとんどがポイントツーポイントリンクである。つまり、イーサネットリンクはホストとイーサネットスイッチを接続するか、イーサネットスイッチ同士を相互接続するために使われることが多い。そのため「多元接続」アルゴリズムは現代の有線イーサネットではあまり使われていない。しかし多元接続アルゴリズムの変種は IEEE 802.11 ネットワーク (通称 Wi-Fi) などの無線ネットワークで利用されているので、ここで古典的なアルゴリズムを説明しておく。イーサネットスイッチについては別に議論することにして、本節では単一のイーサネットリンクの動作に焦点を当てる。

1978 年、10 Mbps イーサネットの規格を策定するための議論を DEC, Intel, Xerox の三社が開始した。こうして策定された 10 Mbps イーサネット規格を基礎として、1983 年には IEEE 802.3 規格が策定された。IEEE 802.3 では 100 Mbps, 1 Gbps, 10 Gbps, 40 Gbps, 100 Gbps といったバージョンのイーサネットを動作させるための非常に幅広い物理媒体が定義される。

2.6.1 物理的な特徴

オリジナルのイーサネットでは、一つのセグメントが最大 500 m の同軸ケーブルを使って実装される (現代のイーサネットではたいてい「カテゴリ 5」と呼ばれる銅製のツイストケーブルあるいは光ファイバーケーブルが利用され、その長さは 500 m よりはるかに長くなる場合がある)。この同軸ケーブルはケーブルテレビで使われるものに似ている。イーサネットセグメントにホストを接続するときは、「タップ」と呼ばれるデバイスをケーブルに差し込む。タップにはリンクがアイドルかどうかの検出や信号の送受信を行うトランシーバー (transceiver, 送受信機) と呼ばれる小さなデバイスが内蔵される。このトランシーバーはイーサネットアダプターと接続され、イーサネットアダプターがホストと接続される。以上の構成を図 39 に示す。

複数のイーサネットセグメントはリピーター (repeater) でつなげることができる (リピーターを複数ポートに対応させたものを ハブ (hub) と呼ぶが、ハブを使っても同じことが行える)。リピーターはデジタル信号を転送するデバイスであり、アナログ信号を転送するアンプに似ていると言える。ホストの組の間に存在できるリピーターは 4 個までと定められているので、古典的なイーサネットは 2500 m より遠くの相手と通信ができない。なお、例えば任意のホストの組の間に存在するリピーターを二つだけにしたとしても、図 40 のような構成をサポートできる。これは建物の各階に設置されたセグメントと垂直方向に設置されたセグメントが接続される構成である。

イーサネットに送信された信号はネットワーク全体にブロードキャストされる。つまり、信号は両方向に伝播され、リピーターとハブは信号がやってきたセグメント以外の全てセグメントに向かって信号を転送する。各セグメントの終端にはターミネーター (terminator) と呼ばれる信号を吸収するための機器が取り付けられ、反射した信号が信号の後ろの部分と干渉を起こさないようになっている。オリジナルのイーサネットはマンチェスター符号を利用したものの、それより高速になった現代のイーサネットは 4B5B 符号 (もしくはそれに似た 8B10B 符号) を利用している。符号化については第 2.2 節で説明した。

考えているイーサネットが単一のセグメントからなるのか、いくつかのセグメントをリピーターで一直線に接続したものなのか、いくつかのセグメントをスター型に接続したものなのかに関係なく、イーサネットでは任意のホストによって送信されたデータが他の全てのホストに到達することを理解するのは重要である。これが良いニュースなのは間違いない。しかし全てのホストが同じリンクへのアクセスを奪い合うので悪いニュースでもある。一つのイーサネットで接続されたホストは同じ衝突ドメイン (collision domain) に含まれると言う。単一の衝突ドメイン内で発生するリンクの奪い合いへの対処がイーサネットの多元接続に関する話題の全てである。

2.6.2 アクセスプロトコル

それでは、共有されたイーサネットリンクへのアクセスを制御するアルゴリズムへと話題を移そう。このアルゴリズムはイーサネットの MAC (media access control, 媒体アクセス制御) と呼ばれ、通常はネットワークアダプター内のハードウェアで実装される。ここではネットワークアダプター自体の説明はせずに、それが実装するアルゴリズムに焦点を当てる。ただまずは、イーサネットのフレームとアドレスを説明しよう。

フレームフォーマット

イーサネットのフレームフォーマットを図 41に示す。先頭 64 ビットの Preamble フィールドは受信側が信号と同期できるようにするために存在するプリアンブルであり、0 と 1 が交互に並ぶ。Dest addr フィールドと Src addr フィールドはそれぞれ宛先ホストと送信元ホストを 48 ビットのアドレスで特定する。パケットの種類を表す Type フィールドは逆多重化鍵として使われ、大量にある上位プロトコルのどれにこのフレームを届けるべきかを指定する。フレームは最大 1500 バイトのデータを保持できる。フレームは最低でも 46 バイトのデータを保持しなければならず、データがこれより少ない場合はホストが転送前にパディングをフレームに入れる必要がある。フレームサイズに下限があるのは、フレームが短いと衝突を検出できないためである (後述)。最後に、フレームは 32 ビットの CRC を持つ。第 2.3.2 項で説明した HDLC プロトコルと同様に、イーサネットはビット指向のプロトコルである。なお、ホストの視点からはイーサネットフレームのヘッダーは 14 バイトとみなせる点に注意してほしい: 6 バイトのアドレスが 2 つと、2 バイトのタイプフィールドである。プリアンブルと CRC は送信側のアダプターによって送信前に取り付けられ、受信側のアダプターによって受信前に取り外される。

アドレス

イーサネットの各ホスト ── 実は、世界に存在する全てのイーサネットホスト ── は一意なイーサネットアドレスを持つ。正確に言うとアドレスが割り当てられるのはアダプターであり、ホストではない: たいていはアダプターの ROM にイーサネットアドレスが刻印される。イーサネットアドレスを人間が読める形式で書くときは、二桁の十六進数 6 つをコロンで区切って書く形式が使われる (各十六進数の先頭の 0 は省略される)。二桁の十六進数は 8 ビットの情報を持つので、6 つあれば 48 ビットの情報を表せる。例えば、8:0:2b:e4:b1:2 は次のイーサネットアドレスを人間に読みやすいように書いたものである:

00001000  00000000  00101011  11100100  10110001  00000010

全てのアダプターがユニークなアドレスを持つことを保証するために、イーサネットデバイスの全ての製造元には製造するアダプターのアドレスの先頭に付けなければならない異なる接頭部が割り振られている。例えば AMD (Advanced Micro Devices) には 24 ビットの接頭部 080020 (8:0:20) が割り当てられている。加えて、それぞれの製造元は自身が製造するアダプターに付けるイーサネットアドレスの接尾部が被らないことを保証する。

イーサネットを通じて転送される全てのフレームは、そのイーサネットに接続された全てのアダプターによって受信される。各アダプターは受信したフレームが自身のアドレスに宛てられたフレームかどうか識別し、自身に宛てられたフレームだけをホストに受け渡す。なお、アダプターを無差別モード (promiscuous mode) に設定すれば受信したフレームを全てホストに受け渡すようにもできるものの、これは通常のモードではない。

特定のホストに宛てて送信されるユニキャスト (unicast) アドレスとは別に、全てのビットが 1 のイーサネットアドレスはブロードキャスト (broadcast) アドレスとして予約されている。つまり全てのアダプターは ff:ff:ff:ff:ff:ff に宛てたフレームをホストに受け渡す。同様に、先頭のビット (最初のバイトの最下位ビット) が 1 でブロードキャストでないアドレスはマルチキャスト (multicast) アドレスとなる。各ホストは特定の範囲のマルチキャストアドレスを受け取るようにアダプターを設定できる。マルチキャストアドレスはイーサネットに存在するホストの一部 (例えば全てのファイルサーバー) にメッセージを送信するために利用される。

まとめると、イーサネットアダプターは全てのフレームを受信し、次のフレームを受け取る:

• 自身のアドレスに宛てられたフレーム

• ブロードキャストアドレスに宛てられたフレーム

• ホストから受け取るよう指示があったマルチキャストアドレスに宛てられたフレーム

• 無差別モードなら、全てのフレーム

アダプターは受け取ったフレームだけをホストに受け渡す。

転送アルゴリズム

ここまでの説明から分かるように、イーサネットプロトコルの受信側は簡単であり、賢い処理は全て送信側で起こる。イーサネットの転送アルゴリズムは次のように定義される。

アダプターが送信すべきフレームを持っていてリンクがアイドルなら、そのアダプターはフレームをすぐに転送する。このとき他のアダプターとの交渉は行われない。フレームのメッセージは最大で 1500 バイトなので、リンクはそれだけのデータを送る間だけ占有される。

アダプターが送信すべきフレームを持っていてリンクがビジー (利用中) なら、そのアダプターはリンクがアイドル (ビジーでない状態) になるまで待機して、アイドルになったらすぐにフレームを転送する (より正確に言うと、全てのアダプターは最後のフレーム転送が終了してから 9.6 μs 経過後にフレームの転送を開始する。この規則はフレームをちょうど送信し終えたノード、およびリンクがアイドルになるのを待機していたノードの両方に対して適用される)。イーサネットではビジーなリンクがアイドルになったときに送信すべきフレームを持っているアダプターが必ずフレームを転送するので、イーサネットは 1-持続的 (1-persistent) なプロトコルと呼ばれる。一般に、\(p\)-持続的 (\(p\)-persistent) なアルゴリズムはリンクがアイドルになったとき確率 \(p\) で転送を行い、確率 \(1 - p\) で転送を延期する (\(0 \le p \le 1\))。\(p \lt 1\) を選択する利点としては、ビジーなリンクがアイドルになるのを複数のアダプターが待っている状況でそれらが同時に転送を行うのを避けられることが挙げられる。例えば各アダプターが 33% の確率で転送をすぐに始めるなら、3 個のアダプターが待機している場合でもリンクがアイドルになったときに転送を始めるアダプターは 1 個となる可能性が高い。ただし、こういった利点があるにもかかわらずイーサネットのアダプターはリンクがアイドルになったのを確認すると必ずフレームを転送するようになっており、それでいて転送の効率は非常に高い。

\(p < 1\) の \(p\)-持続的プロトコルに関してさらに話をしておくと、コイントスに負けた (転送を遅延させると判断した) 送信側がどれくらい待つのかという問題がある。この種のプロトコルを利用した初期の Aloha ネットワークは、時間を離散的なスロットに分割することでこの問題を解決した。それぞれのスロットは完全なフレームを送信するのにかかる時間に対応する。送信すべきフレームを持つノードが空 (アイドル) のスロットを検知したら、そのノードは確率 \(p\) でフレームを転送し、確率 \(1 - p\) でフレームの転送を遅延させる。もし次のスロットも空なら、ノードは同様の確率で転送もしくは遅延を行う。もしスロットが空でない (他の基地が転送を行っている) なら、ノードは次のアイドルなスロットまで待ち、同じアルゴリズムを繰り返す。

イーサネットの説明に戻ろう。イーサネットには中心的な制御が存在しないので、二つ以上のアダプターが同時にフレームの転送を開始することがあり得る。それらのアダプターはリンクがアイドルなことを検知したのかもしれないし、ビジーなリンクがアイドルになるのを待っていたのかもしれない。二つ以上のアダプターが同時にフレームを転送するとき、転送される二つ以上のフレームは衝突 (collide) すると言う。イーサネットは衝突検出をサポートするので、それぞれのアダプターは衝突が起こったかどうかを判定できる。自身が送信したフレームの衝突を検出したアダプターはまず 32 ビットのジャミング信号 (jamming sequence) を送信し、それからフレームの転送を中断する。つまり送信側は最低でも 64 ビットのプリアンブルと 32 ビットのジャミング信号を合わせた 96 ビットを衝突の際に送信する。

衝突を検出したときに送られることになるジャミング信号で終わるフレームをラントフレーム (runt frame) と呼ぶ¹。通信を行う二つのホストが近ければ、ラントフレームが最小の 96 ビットになる場合もある。しかしホスト同士が遠く離れていると衝突を検出するまでの時間が長くなり、それまでに送信されるビットも増える。最悪ケースは二つのホストがイーサネットの両端にあるときで、送信したフレームが他のフレームと衝突しないことを確認するために送信側は 512 ビットもの信号を送る必要がある。イーサネットフレームの長さが最低でも 512 ビット (14 バイトのヘッダー、46 バイトのデータ、4 バイトの CRC の合計 64 バイト) なのは偶然ではない。

イーサネットフレームの長さが最低 512 ビットなのはどうしてだろうか？ この質問はイーサネットに関して抱いたであろう次の質問と関連している: 長さが 2500 m に制限されているのはなぜだろうか？ 10 km や 1000 km でないのはなぜ？ こういった質問への解答には、二つのノードが離れればそれだけフレームをやり取りするのに時間がかかるようになり、その間は衝突を検出できなくなる事実が関係する。

最悪のシナリオを図 42 に示す。ホスト A とホスト B はネットワークの両端にあり、A がフレームの転送を時刻 \(t\) に始める (a)。このとき A のフレームはリンクのレイテンシ (\(d\) と表記する) だけ遅れて時刻 \(t + d\) に B に到着する (b)。A のフレームが到着する直前に B がフレームの転送を開始したとする (この瞬間に B が見ているリンクはアイドルである)。このとき B のフレームはすぐに A のフレームと衝突し、B は衝突を検出する (c)。このとき上述したように B は 32 ビットのジャミング信号を送信する (B のフレームはラントフレームとなる)。しかし残念ながら、A は衝突が起こったことを B からのフレームが到着する時刻 \(t + 2d\) まで検出できない (d)。言い換えれば、発生する可能性のある衝突を全て検出することを保証するために A は \(2d\) の間データを転送し続ける必要がある。

イーサネットネットワークの最大長は 2500 m で、そのとき両端に置かれた二つのホストの間には 4 つのリピーターが存在する。ここから、イーサネットにおける最大レイテンシは 51.2 μs と見積もれる。この 51.2 μs が 10 Mbps イーサネットにおける 512 ビットに対応する。これを「イーサネットでアクセス調停に用いられるアルゴリズムを動作させるには、ネットワークの最大レイテンシを小さい値 (例えば 51.2 μs) に制限しなければならない」と捉えることもできる。

衝突を検出して転送を停止したアダプターは、一定の時間だけ待機してから転送処理をやり直す。そのときの待機時間は転送を試みて失敗するたびに二倍に増加する。この「再送ごとに待機時間を二倍にする」戦略を一般に指数バックオフ (exponential backoff) と呼ぶ。正確に言えば、最初の待機時間は 0 μs または 51.2 μs からランダムに選ばれ、次は 0, 51.2, 102.4, 153.6 μs (51.2\(k\) μs, \(k\) = 1, ..., 3) からランダムに選ばれる。その次の待機時間は 51.2\(k\) μs (\(k\) = 0, ..., 2³ - 2) から同様にランダムに選ばれる。一般に、指数バックオフアルゴリズムは 0 から2^\(n\)-1 の間にある \(k\) をランダムに選び、51.2\(k\) μs だけ待機する (\(n\) はこれまでの衝突回数)。アダプターは一定の回数失敗すると転送を諦め、ホストに転送エラーを報告する。イーサネットアダプターは 16 回失敗するまで転送を試みることが多く、そのとき上述の公式における \(n\) には衝突回数と 10 の小さい方を利用する。

2.6.3 イーサネットが生き残った理由

イーサネットはローカルエリアネットワーク用のテクノロジとして三十年以上に渡って支配的な地位を保ち続けている。現在イーサネットはタップの取り付けられた同軸ケーブルではなくポイントツーポイントリンクとして利用され、リンクの帯域は 10 Mbps ではなく 1 Gbps あるいは 10 Gbps であり、1500 バイトではなく 9000 バイトのデータを保持できるジャンボパケット (jumbo packet) が存在するものの、イーサネットは最初の規格との後方互換性をいまだに保ち続けている。このため、イーサネットを置き換えようとするテクノロジで模倣すべき特徴を理解するために、イーサネットがここまでの成功を収めた理由に関して少し言及しておく価値がある。

第一に、イーサネットは管理・運用が非常に容易である: 常に最新に保たなければならないルーティングあるいは構成用のテーブルは存在せず、ネットワークにホストを簡単に追加できる。イーサネットより管理が簡単なネットワークを想像するのは難しい。第二に、イーサネットは安価である: 同軸ケーブルあるいは光ファイバーケーブルは比較的低価格であり、それ以外には各ホストにネットワークアダプターを設置するコストしか必要にならない。こういった要因によってイーサネットの地位は揺るぎないものになった。イーサネットを置き換えようとしたスイッチベースのアプローチはどれも、アダプターのコストに加えてインフラストラクチャ (およびスイッチ) に追加の投資を必要とした。スイッチベースのイーサネットが多元接続のイーサネットを置き換えたのは事実だが、その理由としては段階的な配備が可能だった事実が大きい。一部のホストをポイントツーポイントリンクでスイッチに接続し、他のホストはこれまで通り同軸ケーブルに設置したタップを通してリピーターあるいはハブに接続する運用が可能であり、そのときネットワーク管理が複雑になることはなかった。