JPH0817385B2 - 高速メッシュ接続式ローカルエリアネットワーク用再構成システム - Google Patents

Description

【発明の詳細な説明】 本発明は一般にコンピュータを相互接続するためのコ
ンピュータ通信ネットワークに関し、特に、コンピュー
タ相互間で情報パケットを経路指定するためのメッシュ
接続式ローカルエリアネットワークに関する。

〔従来の技術〕

ローカルエリアネットワーク（LAN）は一般に比較的
近接配置されたコンピュータ相互間でメッセージを伝達
するために用いられている。第1A図、第1B図及び第２図
について説明すると、少なくとも３つの基本型式のLAN
のための組織アーキテクチャ、即ち、線形（第1A図）、
リング形（第1B図）及びメッシュ形（第２図）のアーキ
テクチャがある。例えば、エサーネットはコンピュータ
ワークステーション、メインフレーム及びミニコンピュ
ータを相互接続するために広く用いられている線形LAN
である。

以下の説明のために、線形LANを、ネットワーク上の
全てのホスト（Ｈ）によって聞き取られるようにメッセ
ージが同報通信される単一チャネルLANと定義する。但
し、通例は、このメッセージを聞き取ろうとするのはパ
ケットによってアドレス指定されたホストだけである。

本発明は、相互接続された多数のホストコンピュータ
間の信頼性ある高速通信をメッシュ接続式LANが提供す
ることを従来は妨げていた主な問題を解決しようとする
ものである。以下の説明に対し、「メッシュ接続式ネッ
トワーク」とは、任意の形態に接続されたスイッチのネ
ットワークを意味する。

本発明が解決しようとするこの問題の意義を説明する
前に、メッシュ接続式ローカルエリアネットワークと線
形ネットワーク及びリング形ネットワークとの間の差
異、並びにメッシュ接続式ネットワークを敢えて構築し
ようとする動機について考察する。即ち、メッシュ接続
式ネットワークは一般に線形及びリング形のLANよりも
高価且つ複雑なのである。

線形及びリング形LANは、アーキテクチャが簡単であ
り、商業的適用のために要求される問題の大部分に対す
る解決法がよく解っており、信頼性についての定評があ
る。しかし、線形及びリング形LANには少なくとも２つ
の大きな技術上の制限がある。即ち、ホスト（即ち、ワ
ークステーション及び他のコンピュータ）の数、及びか
かるLANを通じて伝送することのできるデータの量が、
いずれも、利用可能なデータ伝送路が唯１つしかないと
いうことによって制限される。線形またはリング形LAN
に付け加えられるホストが多くなるにつれ、単一データ
通路上のトラフィックの量が増し、各ホストがメッセー
ジを送る際に待たなければならない平均時間も増加す
る。結局、十分に多くのホストが単一のLANを共用した
としても、この遅延は許容し難いものとなる。

線形及びリング形LAN上のデータ伝送速度を単に増大
させるだけでは、このネットワーク混雑の問題を完全に
は解決することができない。即ち、かかるネットワーク
における遅延のうちの若干は、メッセージがネットワー
クの長さを通過するのに要する時間の長さに関係するか
らである。即ち、若干の遅延は、データ伝送速度のいか
んにかかわらず、ネットワークの物理的長さに比例する
のである。

例えば、線形LANにおける使用可能最大データ伝送速
度はネットワークの物理的長さに反比例する。その結
果、実用的な線形LANとしては、エサーネットによって
現在使用されている10メガボーの速度よりも余り高いデ
ータ伝送速度を使用することはできない。即ち、相当に
高いデータ速度はネットワークの長さを制限することに
なるからである。更にまた、線形LANには、一度に１つ
のデータパケットしか送れないので、誰（即ち、LANに
おけるどのホスト）が何時もLANを管理しているかとい
うことを決定するための機構がなければならない。光速
によって加えられる信号速度の制限について簡単に考え
ると、線形LANの長さはかなり（例えば数キロメートル
に）制限されることになり、そして、ネットワークの性
能は、LANの制御に対するコンテンションのため、LANに
付け加えられるホストが多くなるほど劣化することにな
る。

リング形LANは任意の高いデータ速度で実行すること
が可能であるが、リング形LANは高い待ち時間、即ち、
メッセージの伝送と受信との間の遅延の影響を受けるの
であり、この遅延は、ネットワークの長さ及び通過すべ
きノードの数に比例する。リング形LANはまた余りフォ
ールトトレラントではなく、またその構成について非常
に制限される。

〔発明が解決しようとする課題〕

線形及びリング形のLANについての前述の問題は、今
まではその有用性を過度に阻害するものではなかった
が、数百のホストを持っているLAN、及び１秒当たり100
メガビットの範囲にあるデータ伝送速度に対する要求が
高まるにつれ、これは現存の線形及びリング形LANの能
力を越えることになってきている。

メッシュ接続式LANを使用することの主な利点は多数
の並列通信路が使用可能となるということである。これ
により、ネットワークホストの相異なる対間のメッセー
ジの同時伝送が可能となる。即ち、メッシュ接続式ネッ
トワークは、ネットワークのスループットがネットワー
クのリンクのスループット制限によって制限されるとい
うことがないので、類似の線形またはリング形のネット
ワークよりも遥かに高い帯域幅を得ることができる。

リング形LANに対するメッシュ接続式ネットワークの
他の利点は、メッシュ式ネットワークの待ち時間が比較
的低くなるということである。待ち時間は、メッセージ
パケットを受信及び再伝送しなければならないノードの
数にほぼ比例する。良好に設計されたメッシュ式LANに
おいては、同様数のホストを有するリング形LANに比
べ、ホストのうちの選択された全ての対間のノードの数
が比較的少なくなる。

メッシュ接続式ネットワークの更に他の利点は、良好
に設計されたメッシュ接続式ネットワークにおいては、
ホストのうちの選択された全ての対間にいくつかの可能
性ある通信路が提供され、これにより、ホストがメッセ
ージを伝送する前に平均として待たなければならない時
間が減少するということである。換言すれば、多くのホ
ストがネットワークを同時に使用することができるの
で、ネットワークの使用のためのコンテンションが大幅
に低減するのである。

従来、メッシュ式ネットワークはコンピュータ科学文
献及び若干の特許明細書において説明されているが、メ
ッシュ式ネットワークは、いくつかの周知且つ処理困難
な問題のため、商業的成功を得るに至ってなかった。特
に、最も困難な問題として、（１）デッドロック、
（２）同報通信メッセージの取扱、（３）ネットワーク
構成部材が故障した場合にネットワークをどのように再
構成するかということ、及び（４）ネットワークを通る
メッセージの経路指定を、このネットワークのスループ
ットが単一リンクのスループットを越えるように、どの
ように編成するかということ、がある。

本発明はメッシュ式ネットワークについての前記従来
の問題を解決することを目的とする。

〔課題を解決するための手段〕

概略説明すると、本発明は高速メッシュ接続式ネット
ワークに関するものであり、このネットワークはホスト
間帯域幅が高く、ホスト間待ち時間が低く、集合体帯域
幅が高い。このメッシュ接続式ネットワークは相互接続
された複数のスイッチから成っており、これらスイッチ
は、ローカルネットワークの構成要素であるホストに順
々に接続されている。これらスイッチはカットスルー
（cutthrough）非ブロック化スイッチであり、複数の二
点間リンクによって互いに及びホストに接続されてい
る。

前記スイッチはスパニングツリーとして編成され、一
つのスイッチはこのツリーの根ノードと呼ばれる。後述
するノード整列規則を用い、全てのスイッチは、このス
イチが根ノードにどのように「近い」かということの見
地から整列させられる。

ネットワーク内の全てのリンクは、一つの方向では
「アップ」リンクと呼ばれ、他の方向では「ダウン」リ
ンクと呼ばれる。アップ方向とは、リンクの一端部にあ
るスイッチがリンクの他端部にあるスイッチよりも根に
近いという方向である。

また、各スイッチは、受信したメッセージパケットを
その目標ホストの方へ自動的に経路指定するための経路
指定機構を有す。詳述すると、本発明における経路指定
機構は、複数のパケットをネットワークを通って同時に
経路指定することを可能にし、そして、全てのメッセー
ジパケットが１つまたは複数のアップリンクの順序に従
い、その後に１つまたは複数のダウンリンクが続くとい
うことを確実にすることによりデッドロックを防止す
る。単一のダウンリンクであるにしても、メッセージパ
ケットがダウン方向に経路指定された後に通過させられ
るアップリンクはない。

多数のデータパケットをネットワークを通して同時に
経路指定することにより、高い集合体帯域幅が得られ
る。一部は、パケットの再伝送（即ち、前送り）をこれ
らパケットの終わりの受信よりも十分に前に開始するス
イッチを設けることにより、低い待ち時間が得られる。
これはカットスルースイッチングとして知られてい
る。。

パケットバッファリング機構により、ノードの枯渇が
防止され、同報通信メッセージの経路指定が可能にな
る。また、本発明におけるフロー制御及びデータバッフ
ァリングにより、相隣るスイッチ間の全ての不整合が補
償される。

本発明においては、メッシュ接続式ネットワークの商
業的適用を従来妨げておった問題を克服するいくつかの
自己管理特徴がある。ネットワーク内のスイッチは、ス
イッチ及びリンクの追加及びネットワーク構成部材の取
り外しまたは故障のようなネットワークの構成の全ての
変化を自動的に検出する。ネットワーク構成の変化が検
出されると、全てのスイッチは分散再構成処理に参画
し、ネットワークを通してメッセージパケットを経路指
定するための全ての合法的通路を再計算することによっ
てネットワークを自動的且つ迅速に再構成する。この再
構成処理は十分に速く、ネットワークの性能及び動作に
与える影響は最小限となる。

この再構成処理の重要な態様として、スパニングツリ
ーの根の自動識別及び分散再構成処理の完了についての
自動検出がある。

本発明の他の目的及び特徴は以下に図面を参照して行
う本発明の実施例についての詳細な説明から明らかにな
る。

〔実施例〕

第２図は本発明にかかるメッシュ接続式ローカルエリ
アネットワークの概念を示すものである。但し、本発明
の多くの重要な特徴はこの図には示してない。従来のメ
ッシュ式ネットワークと異なり、本発明のネットワーク
においては、ノードの格別の階層はなく、また、どのよ
うにしてネットワークのノードを相互接続するかについ
ての必要条件もない。本発明のネットワークのノードは
ランダムに相互接続してよく、それでもこのネットワー
クは適正に機能する。但し、よく考えられた様式の相互
接続があれば、何等かの更に良い性能が得られるであろ
う。

第２図において、このネットワークを用いるホストコ
ンピュータを記号Ｈで示してあり、このローカルエリア
ネットワーク（LAN）を構成するノードをスイッチと呼
び、記号Ｓで示してある。この概念図においては、16個
のスイッチを用いて約80個のホストを相互接続してい
る。スイッチＳはマルチポート形のカットスルー非ブロ
ック化スイッチであり、複数の受信リンクを選択された
種々の発信リンクに同時に接続することができる。これ
らスイッチにより、数多くのデータパケットをネットワ
ークを通して同時に経路指定することができる。

用語 以下の説明を明瞭にするため、用語の定義を次に掲げ
る。

「チャネル」は、次に定義するように、リンクの２分
の１について用いる語である。一般に、各チャネルは単
方向通信チャネルであり、データパケットをネットワー
クの２つの構成要素間で伝送する。場合により、チャネ
ルは、該チャネル内のデータフローの方向を識別するた
め、「アップリンク」または「ダウンリンク」と呼ばれ
る。

「ホスト」は、ネットワークに接続されておってメッ
セージの送信及び受信に用いることのできる任意のコン
ピュータまたはワークステーションである。

「ネットワークの構成要素」または「ネットワーク構
成要素」は、ホストまたはスイッチのいずれかである。

「メッシュ接続式ネットワーク」は、任意の形態に接
続されたスイッチのネットワークである。

「メッセージ」は、ネットワークの一つの構成要素か
ら他の構成要素へ伝送される任意のセットである。後で
詳述するように、大部分のメッセージは一つのホストか
ら他のホストへ送られるが、時としては、ネットワーク
制御メッセージが一つのスイッチから他のスイッチへ送
られる。

「パケット」、「データパケット」及び「メッセージ
パケット」は、全て、ネットワークを通って伝送される
情報の基本ユニットを意味する。基本的には、ネットワ
ークを通って送られる情報の全てのセットは、先ず、１
つまたは複数のパケットに実装される。各パケットは、
パケットの宛先を特定するヘッダ、及び、パケットの終
わりを宣言するテールを含んでいる。即ち、短いメッセ
ージ（例えば、10,000バイト未満）は一般に単一のパケ
ットとして伝送され、長いメッセージ（例えば、長い書
類またはデータファイル）は連続的に伝送されるパケッ
トのストリームに分割される。

パケットを「再伝送する」とは、スイッチによって受
信または部分的に受信されたパケットを送り出すことで
ある。

「ポート」は、スイッチ（またはホスト）をリンクに
接続する該スイッチ（またはホスト）内の回路である。

「スイッチ」は、パケットを受信してネットワークを
通って経路指定する物理的装置である。本発明実施例に
おいては、スイッチを少なくとも１ダースのホスト及び
／又は他のスイッチに接続することができる。第２図に
おける各円には、１つのスイッチを示す記号「Ｓ」を付
してある。

「リンク」は、ネットワークの任意の２つの構成要素
を物理的に接続する装置である。第２図において、ホス
トＨとスイッチＳとの間、または２つのスイッチの間の
各直線はリンクを表す。本発明の説明において、２つの
ネットワーク構成要素間の各リンクは全二重、双方向チ
ャネルであり、これにより、両方向の同時通信が可能に
なる。各リンクの両端は、「ポート」とも呼ばれる「リ
ンク回路」で終わっている。

「ネットワークアドレス」は、各ネットワーク構成要
素に割り当てられ、「経路指定テーブル」内にアドレス
するのに用いられる値である。ネットワークアドレスに
よって特定される経路指定テーブル内のエントリは、ネ
ットワークを通ってネットワーク構成要素へ至る合法的
経路に対応する情報を提供する。

「再構成」は、ネットワークによって伝送されるデー
タパケットに対する全ての合法的データ伝送路を決定す
る処理である。新しいスイッチまたはリンクがネットワ
ークに付け加えられる度毎に、及びスイッチまたはリン
クがネットワークから取り外されるかまたは適正に働か
なくなった度毎に、ネットワーク再構成が行われる。本
発明の一つの重要な特徴として、２つのホスト間の物理
的マルチリンク通路の全てが合法的伝送通路であるとい
うわけではない。

本明細書における「スパニングツリー」とは、メッシ
ュ接続式ネットワーク内のスイッチ間相互接続の表示を
意味する。技術的には、スパニングツリーは、ホストコ
ンピュータ及びスイッチ間の若干のリンクを除き、ネッ
トワークの一部を表す非循環接続サブグラフである。前
記除かれたリンクはネットワークを、ツリーとせずに、
非環式グラフとなす。即ち、スパニングツリーのノード
はこのグラフの各レベル内で相互接続を持つことができ
るからである。

「ネットリスト」は、ネットワーク内のスイッチ相互
間のスイッチ及びリンクを表示するものである。

ネットワークの「根」、「根ノード」または「根スイ
ッチ」は、ネットワークのスパニングツリーの根として
指定されるスイッチＳである。根ノードは、ネットワー
クの再構成中に、また、同報通信メッセージ、即ち、ネ
ットワーク内の全てのホストへ送られるメッセージを再
伝送するために、いくつかの特別の応答性を持つ。

ネットワークの接続及び経路指定 第３図に本発明にかかるメッシュ接続式ネットワーク
の１つのセクションを示す。本実施例においては、ネッ
トワーク内の各ホスト120は、ホスト120を別々のスイッ
チ（例えば、ホスト120の場合にはスイッチ124及び12
6）に接続する制御器122を有す。ホスト120をスイッチ1
24及び126に接続する２つのリンク128及び130は同構造
である。但し、これら２つのリンクのうちの一方だけは
常に活性的である。それで、リンク130を破線で示し、
これが非活性的であるということを示す。

ホストコンピュータとスイッチとの間の活性リンクが
故障すると、このホストのネットワーク制御器122が自
動的に他のリンクを活性化し、このホストをネットワー
クに再接続する。また、各ホストに対する２つのリンク
128及び130を２つの異なるスイッチに接続しておくこと
が極めて好ましい。即ち、このようにしておけば、一つ
のスイッチ全体が故障しても、このスイッチに接続され
ている全てのホストはネットワークへの代替え通路を持
つことになるからである。一般に、各ホストからネット
ワークへの２つの代替え通路またはチャネルを設ければ
十分な冗長度が与えられ、一つのハードウェアが故障し
てもホストをネットワークから隔離するということがな
い。

ネットワーク構成要素間の各「リンク」は、事実上、
データを互いに反対方向に同時に運ぶ２つの通信チャネ
ルである。本実施例においては、ネットワーク内の各リ
ンク128は、同軸ケーブルを用いる場合には長さが100メ
ートルまであってもよく、また、光ファイバ布線を用い
る場合には長さが２キロメートルまであってもよい。

同軸ケーブルを用いると、ケーブルの単線を用いて信
号をリンク上で双方向に伝送することにより、ネットワ
ークに必要な配線の量を減らすことができる。ケーブル
の各端部には送信器及び検出器がある。この検出器は、
ケーブルの他端部にある送信器によって送られた信号
を、ケーブルの同じ端部にある送信器の出力を、ケーブ
ルのその端部にある検出器によって受信された信号から
減算することにより、再表示する。このような全二重単
線式通信チャネルは周知であり、本発明の実施に不可欠
なものではない。

数多くのデータパケットをネットワークを通して同時
に伝送することができる。一例を挙げると、第１のパケ
ットをホスト132からホスト134へ送りながら第２のパケ
ットをホスト136からホスト138へ送る。第３図に示す経
路P1は、２つのリンクで接続された３つのリンクを具備
しており、これを用いて第１のパケットをホスト132か
らホスト134へ送ることができる。第３図に示す経路P2
を同時に用いて第２のパケットをホスト136からホスト1
38へ送ることができる。本例においては、両方のデータ
パケットをスイッチ140を通じて同時に送る。これが可
能であるのは、本発明において用いるスイッチがマルチ
ポート形非ブロック化スイッチであるからである。各ス
イッチは、複数の受信リンクを別々の発振リンクに同時
に接続することのできるクロスバー回路を有している。

パケットは一般にネットワーク内のホストＨから他の
ホストＨへ送られるが、ネットワークの再構成中は、デ
ータパケットはスイッチ自体内のコンピュータへ送られ
る。データパケット経路指定のこの態様については「経
路指定テーブル」及び「再構成処理」の項において後で
説明する。

デッドロック 本発明の一つの特徴として、「デッドロック」の影響
を受けることのないメッシュ接続式ネットワークが提供
される。ネットワークにおけるデッドロックは、トラフ
ィック交叉部におけるグリッドロックに類似の電子回路
と考えることができる。第４図に、４つのホストコンピ
ュータＡ、Ｂ、Ｃ及びＤ並びに４つのスイッイＳを示
す。各ホストは、データパケット148を、２つのスイッ
チでこの送信ホストから分離されている他のホストへ送
ろうとする。各パケットの宛先は、このパケットを表す
枠148内の記号で示されている。例えば、ホストＡによ
って送られるパケット148はホストＣの宛先を有す。

本例に対し、送信中のデータパケットはスイッチ内の
データバッファよりも大きく、従って、このデータパケ
ットは、パケットの送信中、２つまたはそれ以上のリン
クのチェインを占めるものと仮定する。第４図に示すよ
うに、各データパケットの進行は、送信の次のステップ
に必要なリンクが前記パケットのうちの他のものによっ
て阻止されるので、阻止される。

当業者は解るように、デットロックはまた小さいデー
タパケットについても生ずる可能性がある。詳述する
と、スイッチ内のデータバッファは２つまたはそれ以上
のデータパケットで一杯になる可能性があり、そのた
め、この一杯になったデータバッファに接続されている
リンクを通じてそれ以上のデータを送ることを妨げる。
即ち、第４図において、阻止された各パケット148は２
つまたはそれ以上のパケットの連なりで置き替えること
ができ、その最初のものは、その経路における次のステ
ップに必要なリンクがパケットのうちの他のもので阻止
されるので、阻止されている。

明らかに、デッドロック状態はしばしば生ずるという
ものではない。即ち、それには、新しいデータパケット
の送信を事実上同時に開始するために４つのホストが必
要であるからである。しかし、デッドロックが生ずると
いうことは許容不能である。即ち、デッドロックはネッ
トワークを「クラッシュ」させ、メッセージを失わせ
る。

アップ／ダウン経路指定 本発明は、メッセージを互いにデッドロックすること
のないように自動的に経路指定するという新ししい型式
の経路指定手続きを用いることにより、デッドロックを
完全に防止するものである。再び第４図について説明す
ると、図示のデータ通路は、データパケットが４つのス
イッチを通る無端ループ内に送られるという「サイク
ル」が生ずることが、少なくとも理論的には可能である
ということを含意している。サイクルは、それ自体は、
通例は問題とならないが、サイクルを形成するデータ通
路の可用性は、デッドロックの被害を受ける可能性のあ
るメッシュ式ネットワークの兆候である。

第５図に、スイッチS1からスイッチS10へ至る10ノー
ドネットワークの若干複雑な例を示す。スイッチ間の全
ての線路は双方向性リンクを示している。

後で説明する理由のため、スイッチ間の全てのリンク
は、リンク上の矢印で示すように、一方向に割り当てら
れている。このリンク上の矢印は、ネットワークの根ノ
ードへ向かう「アップ」を指示するものと言われてい
る。詳述すると、データパケットがリンク上の矢印と同
じ方向にリンクを通って送られる場合、このデータパケ
ットは、「アップリンク」、または更に正確には「アッ
プチャネル」を進みつつあると言われる。データパケッ
トがリンク上の矢印と反対方向にリンクを通って送られ
る場合、このデータパケットは「ダウンリンク」または
「ダウンチャネル」を進みつつあると言われる。

本発明において用いる基本的経路指定規則は、データ
パケットに対する全ての合法的経路はゼロまたはそれ以
上のアップチャネルを具備し、その後にゼロまたはそれ
以上のダウンチャネルが続くということである。データ
パケットがダウンチャネルを通って送られると、このデ
ータパケットはアップチャネルを通って送られるという
ことはない。

前述の基本的経路指定規則は、「大域的見解」から、
即ち、ネットワークを全体として考察する者の観点か
ら、パケットに対する合法的経路を定義する。単一スイ
ッチについての見解から、パケットがこのスイッチへ向
かって「アップリンク」を進む場合、このパケットはダ
ウンリンクで受信される。即ち、「ローカルスイッチの
見解」から、「ダウンリンク」で受信されたパケットは
アップまたはダウンのどちらのリンクへも進ませられる
ことが可能であり、「アップリンク」で受信されたパケ
ットはダウンリンクへしか進ませられない。

また、ホストとスイッチとの間の全てのリンクに対
し、アップ方向はこのスイッチの方へ向かう方向であ
る。ホストコンピュータからスイッチへ至るチャネルは
常にアップリンクまたはアップチャネルであり、スイッ
チからホストコンピュータへ至るチャネルは常にダウン
リンクまたはダウンチャネルである。即ち、ホストコン
ピュータがデータパケットを送信する場合、このデータ
パケットが進む最初のチャネルは常にアップチャネルで
ある。同様に、データパケットがホストコンピュータに
受信されるときにこのデータパケットが進む最後のチャ
ネルは常にダウンチャネルである。

次に、スイッチS1、S3、S5及びS10がある第５図の左
下部分を用い、何故にデッドロックがアップ／ダウン経
路指定機構を用いて不可能であるかを示す。第４図から
第５図内のこれらスイッチ上へのデータ通路を用いよう
とすると、第４図内の全てのデータ通路は、１つのデー
タ通路を除き、合法的であるということが解る。即ち、
スイッチS3、S5次いでS10を通ってホストＢからホスト
Ｄへ至るデータ通路は合法的でない。その理由は、S3か
らS5へ至る通路はダウンチャネルであり、S5からS10へ
至る通路はアップチャネルであるからである。これは、
アップチャネルはダウンチャネルの後で使用できないと
いう規則に反する。その解決法としては、ホストＢから
ホストＤへ至るメッセージを先ずS3からS1へ進ませ（こ
れはアップチャネルである）、次いで、S1からS10へ進
ませる（これはダウンチャネルである）。

このネットワークにおけるスイッチ間の各リンクの指
向性は次のようにして決定される。全てのスイッチ（及
びホストコンピュータ）は、UIDと呼ばれる一意的48ビ
ット識別子を永久的に割り当てられている。かかるUID
はエサーネットにおいて用いられ、ネットワークの全て
の構成要素を一意的に識別する。後で説明するように、
ネットワーク内の全てのスイッチは７ビットSHORT IDを
割り当てられ、全てのホストコンピュータは11ビット・
ネットワークアドレスを割り当てられている。

第１の規則は、全ネットワーク内の最低UIDを有する
スイッチは根ノードと呼ばれ、ゼロのネットワークレベ
ルを割り当てられるということである。この第１の規則
は必然的結果として、根ノードに対する全てのリンクは
根へ向かって上方へ方向づけされる。

第５図において、各スイッチはその基準数に等しいUI
Dを割り当てられているものとする。即ち、S1は１のUID
を割り当てられ、S2は２のUIDを割り当てられ、以下同
様になっている。即ち、スイッチS1は根であり、スイッ
チS2、S3、S9及びS10からS1へ至るリンクはスイッチS1
へ向かって上方へ方向づけされる。

第２の規則は、スイッチはスイッチと根との間のリン
クの最小数に基づくネットワークレベルを割り当てられ
るということ、及び異なるネットワークレベルにあるス
イッチ間のリンクは低い方のネットワークレベルへ向か
って上方へ方向づけされるということである。例えば、
スイッチS3はネットワークレベル１にあり、スイッチS8
はネットワークレベル２にあり、従って、S8からS3まで
のリンクはS3へ向かって上方へ方向づけされる。

リンクに指向性を割り当てるための第３の最後の規則
は、同じネットワークレベルにあるスイッチ間のリンク
は低い方のUIDを有するスイッチへ向かって上方へ方向
づけされるということである。即ち、スイッチS2及びS3
はいずれもネットワークレベル１にあるから、これらの
間のリンクはS2へ向かって上方へ方向づけされる。

ネットワークを通る合法的経路についての他の例は次
の通りである。即ち、パケットをホストＣからホストＥ
へ送り、このパケットは通路P3またはP4を通って進むこ
とができる。スイッチS5、S3、S8及びS9を通って進む通
路P3は、アップチャネルに従い、次いでダウンチャネル
に従うから、合法的である。スイッチS5、S7次いでS8を
通って進む通路P4は、２つのダウンチャネルに従うか
ら、合法的である。

通路P4は通路P3よりも短いが、P4の最初のリンクが阻
止されておって通路P3内の最初のリンクが可用である場
合にはP3の方が好ましくなる。即ち、ネットワークを通
るこの好ましい通路は、どのリンクが他のデータパケッ
トによって既に使用されているかに依存するのであり、
そしてこの好ましい通路は必ずしも最短の合法的通路で
あるとは限らない。

ホストＦからホストＧへ送られるパケットに対する非
合法経路の例としては、スイッチS7からS6へ至り（ダウ
ンリンク）、その後にS6からS8へ至るもの（アップリン
ク）が続くというものがある。この経路は、ダウンリン
ク（S7からS6へ）の後にアップリンク（S6からS8へ）を
有しており、これは許されないので、非合法である。Ｆ
からＧまでの合法的経路は、S7からS5へ（アップ）、S5
からS3へ（アップ）及びS3からS8へ（ダウン）進む。

ネットワーク内のリンクに方向性を割り当てるという
こと、及びネットワークを通る合法的経路を定義すると
いうことの前述の方法は本発明者等が見いだしたもので
あり、後で詳述するように、デッドロック問題を除去す
るのみでなく、更に、同報通信メッセージパケットを取
り扱うための便利な機構を提供する。

パケットフロー制御 本発明実施例の多くの特徴を理解するため、どのよう
にして「フロー制御」が働くかということを理解するこ
とが先ず必要である。第３図を参照し、ホスト132から
ホスト134へ送られつつある16,000バイト・パケットの
例を考えてみる。この例に対し、各スイッチポートは、
受信データパケットの一部を一時的に記憶するための4k
バイトFIFOバッファを有しているものとする。

先ず、パケットをスイッチ142への通路P1に沿ってホ
スト132によって伝送する。リンク144が他のデータパケ
ット伝送のために既に使用されている場合には、ホスト
132に命令してこのデータパケットの伝送を一時的に停
止させない限り、スイッチ142内の4kバッファは間もな
くあふれる。

本実施例においては、データは、ホスト132とスイッ
チ142との間のリンク146のような全てのリンク上で両方
向に連続的に送られる。送信すべきデータがない場合に
は、同期バイトが送られる。同期バイトは単なる空デー
タである。

データが伝送されるのと同時に、フローコマンド信号
も単純型式の時多重化によって送られる。即ち、伝送さ
れる256番目ごとのバイトがフロー制御コマンドであ
る。フローコマンドの伝送はパケット境界と同期しな
い。即ち、フローコマンドは、リンクがどのようなデー
タを運んでいるかとは関係なしに、256バイトサイクル
ごとに１回、リンク上にある。即ち、700バイト・メッ
セージがリンク上で送られている場合には、このメッセ
ージを表すデータストリームは次のように見える。即
ち、メッセージの最初の200バイトの後に１バイト・フ
ローコマンドが続き、その後にメッセージの次の255バ
イトが続き、その後に第２の１バイト・フローコマンド
が続き、次いでメッセージの残りの245バイトが続く。
パケットの終わりの後に10同期バイトが続き、次いで他
のフローコマンドが続く。

コマンドからデータを識別するため、８ビットごとの
バイトを、９ビットを用いて、ネットワークのスイッチ
内で論理的にコード化する。９番目のビットは、このバ
イトがデータであるかコマンドであるかを示すフラグで
ある。前述したように、通例唯１つのコマンドが256バ
イトごとに送られるだけである。ネットワークの正常動
作中、２つの頻繁に用いられるフローコマンドがある。
即ち、ストップデータフロー及びスタートデータフロー
がある。ある状況中では、データの正常なフローは他の
コマンドで中断される。

本実施例においては、スイッチ内で用いられる９ビッ
ト・データ／コマンド値がコード化され、標準のTAXI送
信器及び受信器チップ（アドバンスド・マイクロ・デバ
イセズ（Advanced Micro Devices）社製のAm7968型及び
Am7069型集積回路）によって直列に伝送される。

第３の頻繁に使用される「コマンド」は「同期バイ
ト」と呼ばれる。同期バイトは単に空データであり、送
信されるデータがないということを受信側に知らせる
「コマンド」であると考えられる。

第６図は、ホスト132によってリンク146上で送信（T
X）及び受信（RX）されつつある信号を示すものであ
る。前述したように、ネットワーク構成要素相互間の各
リンクは、事実上は、互いに反対方向にデータを同時に
運ぶ２つの通信チャネルである。それで、第６図に２つ
のデータストリームを示してある。例えば、第３図を参
照して説明すると、これらデータストリームはホスト13
2とスイッチ142との間のデータストリームである。本例
において、ホスト132によって送信されるTXデータスト
リームはかなり長いメッセージパケットを含んでおり、
その始まり及び終わりを「Ｂ」バイト及び「Ｅ」バイト
で示してある。「Ｂ」バイトはそれぞれのパケットに先
行する「ビギンパケットコマンド」（begin packet com
mand）を示し、「Ｅ」バイトはそれぞれのパケットの後
に続く「エンドパケットコマンド」（end packet comma
nd）を示す。

「Ｄ」バイトはメッセージパケット内のデータを示
し、「０」バイトは、送信すべきデータがないか、また
はパケットの流れが一時的に中止された場合に送られる
同期バイトを示す。

スイッチ142によってホスト132へ送られるRXデータス
トリームは、ホスト132によって送られつつあるパケッ
トの流れを制御するためのフロー制御信号Ｓ（開始のた
めの）及びＸ（停止のための）を含んでいる。スイッチ
142によって送られるストップコマンドはホストによっ
て送られつつあるパケットの流れを一時的に停止させ、
スイッチ142によって送られるスタートコマンドはホス
ト132にパケットの送信を再開させる。スイッチ142によ
って送られるRXデータストリームはまた、パケットの始
まり及び終わりにおいて「Ｂ」バイト及び「Ｅ」バイト
で示されるような小さいデータパケットを有す。

第６図に示すように、最初のスタートフローコマンド
150がスイッチ142によって送り出された若干時間後（RX
データストリームにおいて）、ホストはそのデータパケ
ットを送信し始める。ホストは、ストップフローコマン
ドX152が受信されるまでデータパケットを送信し続け
る。後で「スイッチフロー制御」の項で詳述するよう
に、これが生ずる主な理由は、スイッチの受信ポートに
おけるデータバッファがあふれることを防ぐためであ
る。スイッチは、もっと多くのデータを受信する準備が
できると、スタートフローコマンドＳ 154を送り出
し、ホストはこれに応答してデータパケットの送信を再
開する。

256番目のバイトごとに送り出されるフロー制御信号
は、「スタートフロー」コマンドを送り出しているネッ
トワーク構成要素内のパケットバッファに残っている自
由スペースが或る量よりも少なくなる（これは、データ
のフローを停止しないとバッファがあふれる危険がある
ということを意味する）ことのない限り、通例は「スタ
ートフロー」コマンドである。即ち、或る特定のリンク
上のスイッチによって受信されるデータがない場合、こ
のスイッチは「スタートフロー」信号を送り出し続け
る。各スイッチは、隣のスイッチによって使用されるフ
ロー制御タイムスロットとは関係のない或る特定のタイ
ムスロットにおいて、フロー制御信号を送り出す。

ホスト制御器122は、ホスト制御器122が「ストップフ
ロー」コマンドを送り出すことはないという点を除き、
スイッチと同じフロー制御機構を使用する。即ち、ホス
ト制御器は、スイッチに、該スイッチが接続される（即
ち、256番目のバイトごとに）という「スタートフロ
ー」制御信号を常に送り出す。その一例を第６図に示し
てあり、TXデータストリームは「スタートフロー」制御
信号156、158及び160を有している。

ホストネットワーク制御器 次に、ネットワークの主要なハードウェア構成要素、
即ち、ホストコンピュータをネットワークに接続するホ
スト制御器、及びデータパケットの経路指定を取り扱う
スイッチについて詳細に説明する。

第７図に、１つのホストコンピュータ120に対するネ
ットワーク制御器122のブロック線図を示す。機能的に
は、ネットワーク制御器122はホストコンピュータをネ
ットワークに接続するためのホストコンピュータ上のポ
ートである。この制御器は「Q22−バス制御プロトコ
ル」として知られているものを採用しており、Ｑバス制
御回路161を用いてホストコンピュータを制御器122に接
続する。Q22−バスプロトコルの説明は、ディジタル・
エキップメント社（Digital Equipment Corporation）
発行（1985年）の「マイクロシステムズ・ハンドブッ
ク」（Microsystems Handbook）、付録Ａに記載されて
いる。他のコンピュータバスを用いるホストコンピュー
タに対しては、異なるバスインタフェース回路が用いら
れる。

マイクロプロセッサ162、コード化回路164及びエラー
補正回路166が、メッセージをコード化するため及びエ
ラー補正コードを発生するために通例の仕方で用いられ
る。制御器122のこれら構成部材の全ては共通データバ
ス168に接続されている。一般に、マイクロプロセッサ1
62はホスト120から受信したデータパケットをＱバスイ
ンタフェース161を介してパケットバッファ174内に保存
する。このホストからのデータパケットは、パケットを
どのように取り扱うかを制御器122内のマイクロプロセ
ッサ162に命令する。詳述すると、制御器122は、このパ
ケットをコード化回路164を用いて指定のコード化キー
でコード化するように命令される。更に、エラー補正コ
ードがCRC回路、即ちエラー補正回路166を用いて計算さ
れ、バッファ174内のパケットの終わりに付加される。

データバス168にはデータ送信回路170及びデータ受信
回路172が接続されている。データ送信回路170は、パケ
ット全体を送信前に記憶するために用いられるパケット
バッファ174を有す。バッファ174内のパケットは、送信
器178によってリンクセレクタ182を介してリンクインタ
フェース回路180へ伝送される前に1kバイトFIFO（先入
れ先出し）バッファ回路176へ転送される。

リンクセレクタ182はリンクインタフェース回路180ま
たはリンクインタフェース回路184のいずれかを選択的
に活性化する。本実施例においては、リンク制御回路18
6の制御の下にあるリンクセレクタ182は、２つのリンク
インタフェース回路のうちの所定のもの、例えば回路18
0を、この回路に接続されているリンクが働いていない
ということ（即ち、このリンクに受信されるフロー制御
コマンドがない場合）が解らない限り、自動的に選択す
る。正常に選択されたリンクが働いていない場合には、
リンク制御回路186はセレクタ182をして他のリンクイン
タフェース回路184をイネーブルさせる。

詳述すると、リンク制御回路186は、受信回路172に受
信されたフローコマンドをモニタし、フローコマンドが
ネットワークから規則的に受信されていない場合にフロ
ー制御コマンドの不存在を検出する。回路186はフロー
制御コマンドの欠如をマイクロプロセッサ162に知ら
せ、そしてマイクロプロセッサ162は、ネットワークへ
の制御器の接続の再確立を試みるために複数のステップ
を行う。これらの処置が有効に作用しない場合には、マ
イクロプロセッサ162は制御器の他のリンクインタフェ
ース回路を試みるために信号をリンク制御回路186へ送
る。

活性リンクとしてリンクインタフェース180または184
を選択するために各ホスト制御器122によってフロー制
御信号がどのように用いられるかを次に簡単に説明す
る。この過程についての詳細な説明は、後で「再構成フ
ェーズ１」の項において行う。

賦勢されると、ホスト制御器122は、最初に選択され
たリンク上に同期信号を送信し始め、そして、フロー制
御信号の受信について前記最初に選択されたリンクをモ
ニタする。所定の期間中にフロー制御信号が受信されな
い場合には、セレクタ182は他の可用リンクを選択する
ように命令される。現在選択されているリンク上でフロ
ー制御信号を探し、そして何も検出されない場合にリン
クを切り換えるという過程は、フロー制御信号が２つの
リンクの一方に確実に受信されるまで継続する。

リンク制御回路186は、現在活性となっているリンク
インタフェース180または184に受信されるフロー制御信
号をモニタする。この最初の説明のため、フロー制御信
号には２つの型、即ち、ストップコマンド信号及びスタ
ートコマンド信号しかないものとする。スタートコマン
ド信号が受信されると、送信器178はイネーブルされ、
そして、パケットバッファ174に記憶されているデータ
が、パケットバッファ174が空になるか、またはストッ
プコマンド信号が受信されるかするまで、送信される。
ストップコマンド信号が受信されると、リンク制御回路
186は送信器178を「使用禁止」となし、これにより、同
期信号（即ち、空データコマンド）が、新しいデータの
代わりに、パケットバッファ174から送信される。

本実施例においては、制御器122によって一旦パケッ
トの送信が開始されると、ホスト制御器122は要求に応
じてパケット内の全てのデータを送信するという準備が
常にできているということになる。本実施例において
は、パケットは、約10バイト程度に小さい場合も、1600
0バイト程度に大きい場合もある。

送信されるべきパケット全体は、このパケットの送信
が始まる前に、先ずパケットバッファ174に記憶され
る。次いで、リンク制御回路186が、前述したように、
活性リンクに受信されたフロー制御信号に従って、パケ
ットの送信を可能にする。

受信回路は、データ受信器190、大型（例えば4kバイ
ト）FIFOバッファ192、及びその後に続く受信パケット
バッファ194を含んでいる。データパケットが活性リン
クから受信されるにつれ、このデータは最初FIFOバッフ
ァ192に記憶される。多くの小型パケットを保持するこ
とのできるFIFOバッファ192から、データはパケットバ
ッファ194内に転送される。全体パケットの終わりが検
出されると、バッファ194内のパケットは次いで処理さ
れ（即ち、ホストコンピュータへ転送され）、そしてパ
ケットバッファ194からクリアされる。

本実施例においては、ホスト制御器122は、ストップ
フロー信号を送り出すことはなく、そして一続きのいく
つかのパケットを受信するように準備させられるように
なっている。バッファ194内の一つのパケットが処理さ
れている間、他のパケットが同じバッファ194に受信及
び記憶されることができる。即ち、バッファ194は大型
のデュアルポート形循環バッファであり、いくつかの大
型パケットを保持するための十分な容量（例えば128kバ
イト）を有す。データはバッファ194の一つのポートを
通じて読み出され、マイクロプロセッサ162によって処
理されてホスト120へ転送される。そして新しいデータ
パケットがバッファ194の他のポートを介して読み込ま
れる。

大型のFIFOバッファ192の使用は一般に好ましいもの
である。即ち、ホスト制御器による遅い処理のためにパ
ケットが失われるということがない。FIFOバッファ192
があふれてパケットが失わせられると、受信済みパケッ
トの肯定応答を要求するより高いレベルのプロトコルが
前記失われたパケットを再送信させる。

リンクインタフェース回路180の主要な構成要素は２
つの「TAXI」チップ196及び198であり（送信器196のた
めのAm7968型チップ、及び受信器198のためのAm7969型
チップであり、いずれもアドバンスド・マイクロ・デバ
イセズ（Advanced Micro devices）社製の集積回路であ
る）、これらは標準の「透過」非同期送信器及び受信器
インタフェース回路である。これらの回路は、点間リン
クにわたる高速データ伝送を取り扱い、従って、本実施
例において用いる100メガビット・データ伝送速度に好
適する。

検出器200は単一ブースタであり、受信回路198が弱い
入力信号を取り扱うのを助ける。

カットスルー非ブロック化スイッチ 第８図及び第９図に示すスイッチ210は全体的ネット
ワークの重要な構成要素である。スイッチ210は、いく
つかの対の選択されたリンクを同時に相互接続すること
ができるので、非ブロック化スイッチと呼ばれる。これ
はまた、パケット全体が受信される前にデータパケット
の再伝送（即ち、送り出し）を開始することができるの
で、カットスルースイッチとも呼ばれる。

本発明のネットワークを制御する中央制御器または知
能（インテリジェント）は存在しない。このネットワー
クの知能及び論理ロジックは、経路指定決定をなし、及
び他の種々のネットワーク管理タスクを行うものであ
り、ネットワーク内の全てのスイッチにわたって分布さ
れている。例えば、各スイッチは、各データパケットを
伝送するのに用いられた前のリンクについての知識なし
に、経路指定決定を独立に行う。しかし、これらスイッ
チは、各々がパケットの効率的且つエラーなし経路指定
を容易にするように設計されている。

先ず第８図のブロック線図について説明すると、スイ
ッチ210の主要な構成要素は、非ブロック化クロスバー
スイッチ212、リンク制御装置214と呼ばれる複数（本例
においては12）のスイッチポート214、スイッチ制御プ
ロセッサ（SCP）216、及び経路指定論理回路218とも呼
ばれるルータ218である。また、SCP216をクロスバース
イッチ212に接続するための特別のリンク回路214aがあ
る。

各リンク装置214はクロスバースイッチ212を１つの全
二重リンク215に接続する。各リンク215は２つのデータ
チャネルを有し、従って、データをリンク215上で双方
向に同時に伝送することができる。即ち、各リンク装置
214は２つの構成要素、即ち、入力リンク装置220（Rx）
及び出力リンク装置222（Tx）を有す。

新しいデータパケットがスイッチ210に受信される
と、このデータパケットを受信する入力リンク装置220
はクロスバースイッチ212によって出力リンク装置222A
に（入力リンクと異なるリンクに対し）接続される。出
力リンク装置222は前記受信されたデータパケットを他
のリンク上で伝送し、このパケットをその宛先へ送り出
す。

第９図について後で更に詳細に説明するように、クロ
スバースイッチ212は、入力リンク装置220のうちの任意
のものまたは全部を出力リンク装置222の別々のセット
に同時に接続することのできるように設計されている。

ルータ218の目的は、どの出力リンク装置222を各入力
リンク装置220に接続すべきかを決めることである。新
しいデータパケットが入力リンク装置220に受信される
と、入力リンク装置220は経路指定要求をルータ218へ送
る。この経路指定要求はこのパケットの宛先及び入力リ
ンク装置の識別を特定する。第８図に示すように、リン
ク装置220はこのパケットの宛先アドレスをバス230上で
ルータ218へ送る。

パケットの宛先は、各パケットの始まりにおいて、こ
のパケットの送り先のネットワーク構成要素を特定する
数バイトとして記憶される。

ルータバス232はリンクマスクを含んでおり、このリ
ンクマスクは、リンク装置の各々に対応する１ビット、
並びに、４ビット・リンクインデックス、同報通信ビッ
ト及び有効フラグを有す。バス232のリンクマスク部の
線路の各々は、ルータ218とリンク装置214のうちの一つ
との間の単ビット通信線と考えることができる。

可用性フラグが各リンク装置222によってルータ218へ
周期的に送られる。可用性フラグは、出力リンクが使用
中でなく、「閉塞されてなく」、従って新しいデータパ
ケットを経路指定するのに使用可能であるときにオンと
なる。出力リンク装置は、リンク（即ち、出力リンクに
接続されているリンク）装置の他端部にあるスイッチが
ストップフローコマンドを送ったときに、閉塞される。
ストップフローコマンドは、リンクの他の側にあるスイ
ッチがこれ以上のデータを受信する準備ができていな
い、ということを示す。出力リンク装置222が使用中で
あるかまたは閉塞されているときには、その可用性マス
クはオフとなる。出力リンク装置からの13の可用性マス
クビットがルータ218によって周期的にサンプリングさ
れ、経路選択を行うために用いられる。

入力リンク装置220によって送られた情報を用い、ル
ータ218は、どの出力リンク装置222を用いてデータパケ
ットを再伝送すべきかを決める。ルータ218が行った経
路選択はルータバス232上でリンク装置214及びクロスバ
ースイッチ212へ伝送され、これらはこの経路選択を用
いてクロスバースイッチ212内の適切な接続をセットア
ップする。

ルータ218については、第13図ないし第16図について
後で更に詳細に説明する。ルータ218のための回路の実
施例が、米国特許第5179558号に記載される。

この最初の実施例には12のスイッチポート（即ち、リ
ンク装置）214しかないが、将来の装置はもっと多くの
かかるポートを有するであろうことが考えられる。

SCP 216は標準のマイクロプロセッサであり（例え
ば、モトローラ（Motorola）社製の68010型マイクロプ
ロセッサが本実施例に用いられている）、これは、スイ
ッチ210が賦製またはリセットされるとルータ218を初期
設定するように、及びネットワークの構成要素が故障す
るかまたは新しい構成要素がネットワークに付け加えら
れると再構成プログラムを行うように、プログラムされ
ている。SCPはSCPバス225によって全てのリンク装置214
に接続され、SCPがリンク装置の状態をモニタし、リン
クに接続されてない装置及び誤差動する装置を識別する
ことのできるようになっている。

リンク装置214aはスイッチ制御プロセッサ（SCP）216
をクロスバースイッチに接続し、従って、SCP 216はネ
ットワーク内のホストコンピュータと同じ通信機構を用
いてクロスバースイッチ212を介してデータパケットを
送受することができる。ネットワークの再構成中、SCP
216は隣のスイッチ内のSCPへデータパケットを送って
ネットワークの形態を決定し、及びネットワークのスイ
ッチ内のルータ218に対する経路指定テーブルの新しい
セットを発生する。

入力リンク装置220と出力リンク装置との間の接続は
クロスバースイッチ212によって次のようにして行われ
る。一般に、ルータ218が新しいリンク選択を発行する
たびごとに、クロスバースイッチ内の２つのマルチプレ
クサがセットされ、選択された入力リンク装置が選択さ
れた出力リンク装置に接続されるようになっている。２
つのマルチプレクサが必要である。即ち、一方はデータ
を入力リンク装置から出力リンク装置へ伝送し、他方の
マルチプレクサはフロー制御信号を入力リンク装置へ送
り返すのである。同報通信パケットを伝送する場合に
は、リンク選択信号によってセットアップされるマルチ
プレクサの数は使用される出力リンクの数に応じて定ま
る。

クロスバー回路 第９図において、各リンク装置の入力部220と出力部2
22とを分離し、クロスバースイッチ212に対するこれら
の関係を示すようにしてある。図では、入力リンク装置
220はクロスバースイッチ212の左側に添い、出力リンク
装置222はクロスバースイッチ212の下部に添って配置さ
れている。しかし、後で説明するように、これら２つの
装置220及び222の回路は相互接続され、これら２つの装
置に対する制御ロジックは完全に分離されてはいない。
また、この図においては、後で説明する理由で、各リン
ク装置220をクロスバースイッチ212の下部に再度示して
ある。

第９図に示すように、各入力リンク装置は９ビット幅
データ通路234及び１ビット幅フロー制御線236に接続さ
れている。データ通路234はデータパケットからデータ
を運び、フロー制御線236はフロー制御情報を運ぶ。

クロスバースイッチ212は各リンク装置214に対する２
つのマルチプレクサ（MUX）240及び242を有す。第１の
マルチプレクサ240は、データ伝送マルチプレクサと呼
ばれ、対応の出力リンク装置222をデータ通路234のうち
の選択されたものに接続する。リンク装置214と同数の
データ伝送マルチプレクサ240があるので、出力リンク
装置222のうちのいくつかまたは全数を入力リンク装置2
20のうちの対応する選択されたものに同時に接続するこ
とができる。換言すれば、スイッチ212は非ブロック化
スイッチであり、多くのパケットを同時に経路指定する
ことができる。

また、２つまたはそれ以上の送信リンク装置222を、
単にそれらのデータ伝送マルチプレクサ240をして同じ
データ通路234を選択させることにより、同じデータ通
路234に接続することができる。この後者の能力は、デ
ータパケットをネットワーク上の全てのホストへ同報通
信する場合に用いられる。

第２のマルチプレクサ242は、フロー制御マルチプレ
クサと呼ばれ、対応する入力リンク装置220をフロー制
御線236のうちの選択されたものに接続する。換言すれ
ば、一つの入力リンク装置220が受信したフロー制御コ
マンドはクロスバースイッチ212を介して入力リンク装
置のうちの他のもの内の制御回路に接続される。リンク
装置214と同数のフロー制御マルチプレクサ242があるか
ら、各入力リンク装置220を他のリンク装置214のうちの
選択された対応のものに同時に接続することができる。

各マルチプレクサ240及び242は付属の選択レジスタ
（図示せず）を有しており、このレジスタは、ルータ21
8によってこれに送られる４ビット選択値を記憶するの
に用いられる。この選択値は、どのデータ通路及びフロ
ー制御線をリンク装置の各々に接続するかを決定する。

要約すると、クロスバースイッチはフロー制御コマン
ドを入力及び出力リンク装置220及び222の各々へ導くた
めのマルチプレクサ240または242を有す。

マルチプレクサ240及び242に対する選択信号が発生さ
れ、ルータ218によってルータバス232上に出力される。
新しいパケットの始まりが入力リンク装置220内のFIFO
バッファの前部に到達する度毎に、入力リンク装置220
は経路指定要求をバス路線230を介してルータ218へ送
る。ルータは経路指定要求に応答し、マルチプレクサ制
御信号を発生してルータバス232上で伝送する。ルータ
バス232は次の構成部材を有す。即ち、 リンクマスク リンクインデックス 同報通信フラグ ルータバス有効フラグ ルータ218の動作及びこれがどのようにしてこれら値
を発生するかについては「ルータ回路」の項において後
で説明する。

出力リンクマスクは出力リンク装置222の各々に対す
る別々のオン／オフ・フラグを有す。「１」の値付きの
マスクフラグを有する各出力リンク222は特定の入力リ
ンク装置に接続される。同報通信フラグは、同報通信パ
ケットが複数の複数のネットワーク構成要素へ同時に経
路指定されているときにセットされる。ルータバス有効
フラグは、ルータ218がバス232上で経路選択を主張して
いるとセットされ、さもないときにはリセットされる。

ルータバス232のリンクマスク部は選択された出力リ
ンクに対応するビットを送り出すのに用いられ、リンク
インデックスは入力リンク装置を識別する４ビット値で
ある。クロスバースイッチは、この４ビット・リンクイ
ンデックスを、前記選択された出力リンク装置に接続さ
れたデータ伝送マルチプレクサ240に対するマルチプレ
クサ選択信号として用いる。例えば、リンクマスクが出
力リンク装置５に対する「１」フラグを有し、入力リン
ク選択が0011（即ち３）の値を有している場合には、値
0011は、第５の出力リンク装置222に関連するマルチプ
レクサ240に対する選択信号として用いられる。出力リ
ンクマスクがいくつかの出力リンク装置に対する「１」
フラグを有している場合には、前記入力リンク選択値は
各対応のマルチプレクサに対して用いられる。

ルータ218によって送り出されるリンクインデックス
値はまたフロー制御マルチプレクサ242をセットアップ
するために用いられる。これを行うため、有効ビットが
オンとなっているときに、クロスバースイッチ212は、
ルータ218によって送られたリンクマスク及びリンクイ
ンデックスを思い出し、次いで、このリンクインデック
ス値によって特定された入力リンクに対してフロー制御
マルチプレクサ242をセットアップする。ルータバス上
の同報通信ビットがオフとなっている場合には、フロー
制御マルチプレクサ242にロードされる選択値は前記バ
スのリンクマスク部上で識別される出力リンクに対応す
る。

入力リンク装置220に受信されたデータパケットが複
数の出力リンクマスクへ同報通信されている場合には、
ルータバス上の同報通信ビットはオンとなり、フロー制
御マルチプレクサ242にロードされる選択値は特定値
（例えば15）となる。これにより、入力リンク装置は、
正常の制御信号の代わりに、Clk256と呼ばれるクロック
ジェネレータ246からの特定クロック信号を使用させら
れる。前述したように、正常フロー制御信号とは無関係
に同報通信パケットが伝送される。

要約すると、ルータ218はリンク選択値を、クロスバ
ー回路のマルチプレクサ240及び242の選択レジスタ内に
対応の値を記憶させるためにクロスバー回路212によっ
て用いられるバス232上で伝送し、これにより、クロス
バー回路を、選択された入力及び出力リンク装置に接続
させる。

ルータバス232上で送られるリンク選択値も入力及び
出力リンク装置によってモニタされ、これにより、クロ
スバースイッチ212を通って次いで出力リンク装置を通
って他のネットワーク構成要素へ行くデータパケットの
伝送を調整する。

ルータ218の動作及びルータバス232上で用いられる信
号プロトコルについては第13図ないし第15図について後
で詳細に説明する。

スイッチフロー制御 第10図について説明すると、スイッチ相互間、及びス
イッチとホストとの間のフロー制御のための基本的機構
は次の通りである。各入力リンク装置は、受信したデー
タを一時的に記憶するために用いられる内部FIFOバッフ
ァを有す。理想的には、データは、これが記憶されるの
と同じくらいに速くFIFOバッファから読み出されるべき
である。しかし、閉塞された（即ち、使用中である）リ
ンクのような種々の要因のため、データはFIFOバッファ
内にバックアップさせられる。FIFOバッファが或る程度
一杯になると、該バッファは、これにデータを送りつつ
あるネットワーク構成要素（「送信器」）へストップフ
ローコマンドを送り出す。この送信器がストップフロー
コマンドを受信すると、該送信器は、スタートフローコ
マンドが受信されるまで、データを送ることを一時的に
停止する。受信用FIFOバッファは、このFIFOバッファか
ら十分なデータが読み出されてその量が所定の充満量よ
りも少なくなると、スタートフローコマンドを送り出
す。

どのチャネルに対するフローコマンドも、同じリンク
の逆チャネルと反対の方向に伝送され、この逆チャネル
上で伝送されるデータと多重化される。

いうまでもなく、ストップフローコマンドがスイッチ
に受信されると、また、データはこのスイッチ内のFIFO
バッファ内でバックアップを開始する。即ち、スイッチ
のチェインの各々内のFIFOバッファが一杯になるにつれ
て発生されるストップフローコマンドのチェイン反作用
がある。結局、データパケットが十分に長いならば、パ
ケットを送り出しているホストはストップフローコマン
ドを受信し、パケットの残りを送り出すことを一時的に
停止する。

また、ログジャムの原因がなくなり、最初のストップ
フローコマンドを発生したFIFOバッファが該バッファが
記憶しているデータを伝送することができるようになる
ときに発生されるスタートフローコマンドのチェイン反
作用がある。

第10図は、本実施例において用いられ、ネットワーク
を通るデータパケットの流れに特に適切であるリンク装
置の細部の若干を示すものである。第10図には、２つの
スイッチ300及び302の連なりを通るホストコンピュータ
120からのデータパケットの流れを示してある。データ
パケットがスイッチ300内のリンク装置ｉに受信される
と、該スイッチは、入力リンク装置ｉをそのクロスバス
イッチを介して出力リンク装置TXjに接続することによ
り、前記パケットを経路指定する。このデータパケット
は、次いで、第２のスイッチ302を通過し、該スイッチ
はこのパケットを再び経路指定する。どれかのRxリンク
装置内のFIFOバッファ310、340が半ば一杯になると、該
バッファは、このFIFOバッファ内に既にあるデータが処
理されるまで、データ伝送チェイン内にある前のネット
ワーク構成要素にデータ伝送を停止させる。

ホストがデータパケットをリンク306上で伝送開始す
るにつれ、スイッチ300内の入力リンク装置308は受信し
たデータをFIFOバッファ310に一時的に記憶する。パケ
ットのヘッダ（図示せず）内のデータを用い、スイッチ
300は、そのリンクのうちのどれがデータパケットをそ
の宛先へ送り出すのに適切なリンクであるかを決定す
る。本例においては、リンク312が選択される。

リンク312が使用中でない場合には、スイッチは入力
リンク装置308を、選択されたリンク312に接続されてい
る出力リンク装置322に、クロスバースイッチ320を通じ
て接続する。通例、スイッチ300は出力スイッチを選択
することができ、及び入力リンク装置308を出力リンク
装置322に、データパケットの最初の25バイトを受信す
るのに要するよりも短い時間で、接続することができ
る。

しかし、リンク312が使用中でない場合には、スイッ
チ300はデータパケットをFIFOバッファ310内に記憶し続
け、適当するリンクが使用可能となるのを待つ。本実施
例においては、FIFOバッファ310は、4kバイトのパケッ
トデータを記憶することができ、そして、バッファが少
なくともハーフフル（half full）になると線路324上に
ハーフフルフラグを発生する組込み回路を有している。
FIFOバッファ310がハーフフル未満である場合には、こ
のフラグは「スタートフロー」コマンドと解釈される。
FIFOバッファがハーフフルを越えている場合には、この
フラグは「ストップフロー」コマンドと解釈される。

FIFOバッファ310からのハーフフルフラグの現在値
は、リンク306に接続されている出力リンク装置326によ
り、フロー制御値としてホスト120へ送り戻される。フ
ロー制御値が「０」となると、ホスト内のデータ「スロ
ットル」（即ち、第７図におけるリンク制御回路）が、
ホスト120によるデータパケットの伝送を可能にする。
しかし、FIFOバッファ310がハーフフルに到達すると、
このFIFOバッファによって発生される「ストップフロ
ー」コマンドが、ホストコンピュータ120内のスロット
ル186をして、ホストによるデータの伝送を一時的に停
止させる。スイッチ300が、FIFOバッファ310がハーフフ
ル未満になるのに十分なデータを伝送すると、FIFOバッ
ファ310は「スタートフロー」コマンドを送り出し、こ
のコマンドはホストのスロットル186がデータパケット
伝送を再開することを可能にする。

第11図について後で説明するように、若干の組込み伝
送遅延及びパケット取扱要求があり、そのため、FIFOバ
ッファ310が最初「ストップフロー」コマンドを発生す
るときに該バッファ内に約2kバイトの余地を持っている
ことが必要となる。一般に、最小限要求されるFIFOバッ
ファ310の大きさは最大リンク長及び最大同報通信パケ
ットの大きさの関数である。その結果、例えばIDT 720
4型のような、4k ｘ 9FIFOバッファを用いるのが便利
であるというが認められた。前記IDT 7204型は、FIFO
バッファが空であるかどうかを、及び少なくともハーフ
フルになっているかどうかを示すフラグを発生する回路
を既に含んでいる。

第10図に示すように、第１のスイッチ300がデータパ
ケットをリンク312上に経路指定するとき、このデータ
パケットは他のスイッチ302に受信される。ここで、こ
のデータパケットは入力リンク装置342内のFIFOバッフ
ァ340に再び記憶され、一方、このスイッチはこのパケ
ットをどこへ経路指定するかを決定する。データパケッ
トを経路指定することのできる可用リンクがない場合に
は、FIFOバッファ340は、これがハーフフルとなると、
線路344上に「ストップフロー」コマンドを発生する。
このストップフローコマンドはリンク312上でスイッチ
１へ送られる。詳述すると、このストップフローコマン
ドはスイッチ300の入力装置330に受信され、次いで、こ
のフローコマンドは、出力リンク装置332を、次いでク
ロスバースイッチ320を通じて、データパケットを受信
しつつある入力リンク装置308へ経路指定される。そこ
で、このフローコマンドはスロットル回路、即ち出力リ
ンク装置332を制御し、この回路は、スタートフローコ
マンドを受信するとFIFOバッファ310に記憶されている
データの伝送を可能にし、ストップフローコマンドを受
信すると伝送を不能にする。

リンク346が使用可能となると、スイッチ302はFIFOバ
ッファ340内のデータを出力リンク装置348を介してリン
ク346上へ伝送し始める。FIFOバッファ340がハーフフル
未満となると、該バッファはスタートフローコマンドを
線路344上へ送り出し、スイッチ300がデータパケットの
伝送を再開することを可能にする。

リンク装置 第11図は第10図に示したスイッチ300の入力及び出力
リンク装置を更に詳細に示すものである。各入力リンク
装置308及び310はTAXI受信器チップ350を有し、このチ
ップは受信リンク306または312上で受信したビット直列
データを９ビット並列信号に変換し、この信号は９ビッ
ト幅バス上でデマルチプレクサ（DMUX）352へ送られ
る。データの各バイトは、このバイトがデータであるか
コマンドであるかを示すデータ型フラグを有し、このフ
ラグは各バイトの９番目のビットを構成する。

デマルチプレクサ352はTAXI Rx回路350から受信した
信号の型フラグをモニタし、データからのデータストリ
ーム内のコマンドを分割する。データ信号、及びパケッ
ト「コマンドバイト」の終わりはFIFOバッファ310に記
憶される。リンク306上で受信されたフロー制御コマン
ドはオン／オフ（即ち、1/0）２進信号に変換され、こ
の信号は線路354上で伝送される。線路354上のフロー制
御コマンドはラッチ356にラッチされ、このラッチは対
応の出力リンク装置322の伝送クロックClk256でクロッ
クされる。ラッチされたフロー制御信号は、次いで、AN
Dゲート358によって伝送クロックClk256とAND処理さ
れ、その結果の信号はクロスバースイッチ320を通って
送り出されて他の入力リンク装置308へ伝送される。AND
ゲート358の出力は、クロスバースイッチ320により、入
力リンク装置308内のスロットル制御線360へ接続され
る。

ラッチ356及びANDゲート358は、入力リンク装置308へ
送られたフロー制御信号を出力リンク装置322の伝送ク
ロックと同期させる。また、ANDゲート358は、伝送済み
フローコマンドを256バイト毎に１回オフとなしてクロ
スバースイッチ320を通るデータの伝送を１バイト間停
止させる。この間、出力リンク装置322はデータの代わ
りにフロー制御信号を送り出す。要するに、出力リンク
装置322は、クロックClk256で定まる256バイトサイクル
毎に「ストップフロー」コマンドをスロットル制御線上
に送り出し、従って、対応のFIFOバッファ310のスロッ
トル332は、スイッチのフロー制御サイクル中はデータ
を送り出すことがない。

前述したように、入力リンク装置に受信されたフロー
制御信号は、ラッチされ、次いで、その出力リンク装置
を通るデータの流れを開始及び停止するのに用いられ
る。

各出力リンク装置322はクロスバースイッチ320から受
信した９ビット並列信号をビット直列信号に変換し、こ
の直列信号は出力リンク312上で伝送される。詳述する
と、出力リンク装置322はマルチプレクサ362を有す。マ
ルチプレクサ362はクロックClk256に接続され、このク
ロックは、線路364からのデータの伝送を255データバイ
トサイクルずつ交互に可能にし、次いで１フローコマン
ドバイトの伝送を可能にする。Clk256と同じ周期を持つ
クロックがデマルチプレクサ352に接続されており、従
って、FIFOバッファ310は、平均として、空になるより
も速く一杯になることはない。

マルチプレクサ362は、これが送り出すフローコマン
ドを、路線366の状態から導出する。線路366は、入力リ
ンク装置330内のFIFOバッファ310によって発生されるハ
ーフフルフラグを運ぶ。一般に、FIFOバッファ310が少
なくともハーフフルになると、オン（即ち、ストップ）
信号が線路366上で送られ、さもない場合にはオフ（即
ち、スタート）信号が線路366上で送られる。線路366上
の信号はエンコーダ回路368によって９ビット「ストッ
プフロー」または「スタートフロー」コマンドに変換さ
れ、Taxi Tx回路370によって伝送される。

マルチプレクサ362によって出力されたデータ及びフ
ローコマンドはTAXI送信器370によってビット直列デー
タストリームに変換され、この送信器は多重化されたデ
ータ及びコマンドをリンク312上で伝送する。

第12図はリンク装置回路の細部を更に示すものであ
る。第11図に示す入力リンク装置308内のデマルチプレ
クサ352は、第12図では、パイプラインレジスタ380、状
態レジスタ382及び制御ロジック384を用いて実現されて
いる。受信された全てのデータは、１バイトサイクル
間、パイプラインレジスタ380に記憶され、これは、各
バイトをFIFOバッファ310にロードすべきかどうかを決
めるための時間を制御ロジック384に与える。フローコ
マンドはデコードされ、状態レジスタ382に記憶され
る。制御ロジック384は、受信中のデータと同期させら
れる線路385上のクロック信号を受信する。このクロッ
ク信号はTAXI Rx回路350によって発生される。制御ロ
ジック384は状態レジスタ382を読み出し、或るコマンド
が受信されると、FIFOバッファ310内へのデータのロー
ディングを不能にする。もっと一般的には、制御ロジッ
ク384は１セットのクロック信号を発生する有限状態マ
シンであり、この信号は、入力リンク装置の一部を通っ
てFIFOバッファ310の入力ポートにまで至ってこれを含
むデータの流れを制御するのに用いられる。

FIFOバッファ310の入力側は、TAXI Rx回路350に受信
されるデータで同期化され、FIFOバッファ310の出力側
はスイッチ内の独立クロック回路によって発生される異
なるクロック信号によってクロックされる。これら２つ
のクロック速度は約0.02％以内でほぼ等しいが、同期は
させられない。

FIFOバッファ310の出力部にパイプラインレジスタ390
を連続させることにより、第２の制御ロジック回路392
は各新パケットの始まりを識別することができる。この
新パケットはパケットの宛先アドレスを含んでいる。こ
のパケットの宛先アドレスはバッファ394を介してルー
タへ送られる。

第11図に示すスロットル332は、FIFOバッファ310に対
する出力クロック信号を発生する制御ロジック392、及
びパイプラインレジスタ392によって実現される。制御
ロジック392は線路354からフロー制御信号を受信する。
この受信されたフロー制御信号は他の入力リンク装置に
よってクロスバースイッチを通って伝送されたものであ
る。ストップフローコマンドが受信されると、制御ロジ
ック392はFIFOバッファ310及びパイプラインレジスタ39
0に対する出力クロック信号を単に使用禁止となし、こ
れにより、FIFOバッファ310からのデータの流れを停止
させる。

制御ロジック392はまた、データの各９ビット・バイ
トのデータ／コマンド・ビットがFIFOバッファ310から
読み出されるときにこれをモニタし、各パケットの終わ
りを識別する。データ及びパケットコマンドバイトの終
りだけがFIFOバッファ310に記憶される。従って、イネ
ーブルされたコマンドビットがFIFOバッファ310から読
み出されと、パケットの終りが制御ロジック392によっ
て検出される。各パケットの終りの後、制御ロジック39
2は、現在パケットがパイプラインをクリアするまで待
ち、次いで、送り出すべき新しいデータパケットを探し
始める。

制御ロジック392はルータバス232を介してルータ218
と会話する。新しいパケットの始まりが検出されると、
制御ロジック392は、ルータバス232のリンクマスク部上
で経路指定要求を送り出し、そして、その後のタイムス
ロット中に、ルータバスの同じリンクマスク部上の「グ
ラント」（grant）信号を受け取る。グラント信号が受
け取られると、前記新しいパケットに対するパケットの
宛先アドレスがバス230上のバッファ394によって主張さ
れる。制御ロジック392はまた、新しいパケットの伝送
を、バス232上のルータによって送られる経路指定選択
信号と同期させる。

両方のロジック回路384及び392は、入力リンク装置30
8の現在状態を示す状態信号を状態レジスタ382に記憶さ
せる。スイッチ制御プロセッサ（SPC）は、状態レジス
タ382に記憶されている状態値のうちの若干を周期的に
読み出し、どのリンク装置が生きているリンクに接続さ
れているか、及びどのリンク装置が適正に働いているか
を測定する。

第12図に示す出力リンク装置326は、パイプラインレ
ジスタ402、デコーダ404、有限状態マシン（FSM）406、
及びTAXI送信器370から成っている。クロスバースイッ
チからのデータは、１クロックサイクル間、パイプライ
ンレジスタ402内に保持され、TAXIタイミング仕様によ
って要求されるデコーダ404のセットアップを許す。パ
ケットコマンドバイトの終りがパイプラインレジスタ40
2に受信されると、FSM 406はこのコマンドを認識し、
そしてその内部状態を変更する。その後、対応の出力リ
ンクが、入力リンク装置308によって受信されたストッ
プ（STOP）フロー制御信号によって阻止されていないな
らば、FMS 406は「リンク可用」信号をルータ218へ送
り出し、そこでルータは、このリンクが新しいパケット
を経路指定するために使用可能であるということを知
る。FMS 406はまた、パケットコマンドバイトの終りを
送り出すことをTAXI Tx回路370に指令し、次いで、ル
ータ218が他のパケットの伝送のために出力リンク装置3
26を入力リンクに再接続するまで、同期化バイトを送り
出すことをTAXI 370に指令する。

デコーダ404はFSM 406とともに、第１図のマルチプ
レクサ362として働く。詳述すると、FSM 406はClk256
クロック信号を用い、何時TAXIがクロスバースイッチか
らデータを伝送するか、及び何時該TAXIがフローコマン
ドを伝送するかを測定する。デコーダ404は入力リンク
装置からFIFOハーフフル状態信号を受け取る。フロー制
御信号を伝送するための各期間中、デコーダ404はFIFO
ハーフフル信号をデコードし、TAXI 370に対する適切
なコマンドを形成する。各パケットの始まりにおいて該
パケットはビギン（BEGIN）コマンドを形成し、各パケ
ットの終りにおいてデコーダ404はエンド（END）コマン
ドを形成する。出力リンク装置がストップフローコマン
ドによって阻止されている場合、または出力リンク装置
がアイドルとなっている場合には、デコーダ404はSYNK
コマンドを形成する。他の全ての期間中は、デコーダ40
4は「データ伝送」コマンドをTAXI 370へ送る。FSM 4
06は、出力リンク装置326の状態、及びどのコマンドを
デコーダ404がTAXI 370へ送るべきかを決定する。

出力リンクFSM 406はまた、新しいデータパケットの
伝送を、バス232上のルータによって送られる経路指定
選択信号と同期させる。同じ経路指定選択信号をクロス
バースイッチ内の経路選択ロジック408が用い、特定の
入力リンク装置を１つまたは複数の特定の出力リンク装
置に接続するためのデータ及びフローマルチプレクサを
セットアップする。

同報通信パケットに対するフロー制御 同報通信の項において後で説明するように、同報通信
パケットの伝送をパケットの中間で停止させることはで
きない。同報通信パケットに対しては所定の最大大きさ
があるから（例えば、1528バイト）、FIFOバッファ310
（第11図）には、パケットを受信しているスイッチによ
ってフローコマンドが発生させられるときに丁度送り出
されつつある同報通信パケット全体を吸収するための余
地がある。

全同報通信パケットを受信することのできるために、
FIFOバッファ310がストップフローコマンドを送り出す
ときに該バッファ内に残っているべき余地の量を測定す
るには、次の因子がある。即ち、ストップフローコマン
ドが送り出される前の最大遅延、伝送用ネットワーク構
成要素がストップコマンドを受信してこれに対して働く
ときに既に伝送されてしまっているデータの最大量、及
び、同報通信パケットの最大大きさ、がある。また、10
0メガビット／秒の伝送速度を持つ２キロメートルの光
ファイバケーブルに対しては、伝送用ネットワーク構成
要素がストップコマンドを受信するときに既に伝送され
てしまっているデータの量は約260バイトである。前記
遅延因子に加え、FIFOバッファ310は、送り出されよう
としている同報通信パケットを該パケット内のデータを
何も失うことなしに該バッファが吸収することのできる
ようにするため、該バッファがストップフローコマンド
を発生するときに少なくとも2044（256＋260＋1528）バ
イトの未使用記憶装置を必要とする。その他の遅延に備
え、及び追加の安全マージンを提供するため、FIFOバッ
ファ310は、これが残りの記憶装置の2k（即ち（204
8））バイトを持つときにストップフローコマンドを発
生する。

本実施例においては、各入力FIFOバッファ310は4kバ
イトのデータを記憶するのに十分な大きさである。これ
らFIFOバッファ310は、ハーフフル未満（即ち、2kより
も多くのバイトが未使用のまま残っている）である限り
スタートフローコマンドを発生するように、及び、これ
らが少なくともハーフフル（即ち、未使用のバイトが2k
またはそれ以下）となるとストップコマンドを発生する
ように設計されている。

パケット連続性 メッセージを部分的に伝送したスイッチが、その前の
スイッチから更に多くのメッセージを受信する準備がで
きているが、該その前のスイッチはメッセージの残りを
伝送する準備ができていない場合に、パケットまたはデ
ータアンダーランが生ずる。本発明の特徴として、パケ
ットアンダーランを不可能にする特徴がある。第10図の
回路においては、これら特徴は、パケットの終りが受信
されるまでは、伝送されるべきデータが常にFIFOバッフ
ァ310内にあることを保証するように設計されている。

第１に、第７図のホスト制御器は、全パケットがパケ
ットバッファ174内に記憶されるまではパケットの伝送
が開始されないようにプログラムされている。これによ
り、ホスト制御器は要求に応じてパケットの残りを伝送
することができるようになる。

第２に、第８図について説明すると、スイッチが新し
いデータパケットを受信すると、該スイッチは、このデ
ータパケットに対する経路指定要求を処理するため、及
び、どの出力リンクを用いてこのパケット再伝送するか
を決めるための時間を必要とする。ルータ218がこれに
対して働いている時間中、少なくとも25バイトのデータ
がFIFOバッファ310に記憶される。

パケットアンダーランを防止するための唯一の残りの
要件は、FIFOバッファ310にその前のネットワーク構成
要素から更に多くのデータが到達する前には、該バッフ
ァ内の全てのデータを読み出すことが不可能でなければ
ならないということである。基本的には、これは、各ス
イッチ内のデータ送信器に対するクロック速度不整合の
量に対する限界があるということを意味する。例えば、
スイッチ内の送信器がその前のネットワーク構成要素内
の送信器よりも若干速い場合には、FIFOバッファ310内
のデータの量は、パケットがスイッチを横切るにつれて
ゆっくりと減ることになる。従って、パケットアンダー
ランを防止するためには、最大の合法的データパケット
を伝送するのに要する時間の最大量に最大クロック速度
食違いを乗じたものが、新しいパケットの伝送がイネー
ブルされる前にFIFOバッファ310に記憶されているデー
タの量よりも小さい、ということが必要である。

本実施例においては、最大長パケットは長さ16kバイ
トであり、最大クロックスキューは約0.02％である。そ
の結果、パケットアンダーランを防止するためにFIFOバ
ッファ310に最初に記憶させることが必要なデータの量
は約４バイトである。本実施例においては、経路選択を
行なうにはルータ218は少なくとも25バイトサイクル（1
00メガビット／秒において）を要し、入力リンク装置を
選択済み出力リンク装置に接続するためにはスイッチは
少なくとも更に１バイトサイクルを要する。即ち、パケ
ットの再伝送開始ができるようになる前に、少なくとも
25バイトがFIFOバッファ310に記憶されることになる。

本発明において用いられるフロー制御装置の一つの利
点は、入力リンク装置内の制御ロジック392がFIFOバッ
ファ310を検査してパケットアンダーランを検出すると
いう必要がなくなり、従って、FIFOバッファ310の出力
側を入力側と同期させるという必要がなくなるというこ
とである。同期化済みFIFOアクセス回路は従来からあ
り、スイッチ相互間の全てのクロック速度不整合を解決
することができるが、かかる回路は本発明のバッファリ
ング手段よりも遥かに高価である。

ルータ回路 ネットワーク内の全てのスイッチにはその48ビットUI
Dに加え、一意的７ビットSHORT IDが割り当てられてい
る。SHORT IDはネットワークの構成中に割り当てら
れ、何等かの特定のスイッチに対するSHORT IDはネッ
トワークが再構成されるときに変化する。各ホストコン
ピュータには11ビット「ネットワークアドレス」が割り
当てられる。ホストコンピュータのネットワークアドレ
スは、そのスイッチのSHORT IDを、このホストをスイ
ッチに接続しているリンクポートの４ビット値と連結す
ることによって発生される。各スイッチのネットワーク
アドレスは、そのSHORT IDに、SCPリンク装置のリンク
番号に対応する所定の４ビット値（例えば、ゼロ）を加
えたものである。

ネットワークアドレスは、ネットワークを通って伝送
されるパケットの宛先を特定するのに用いられるアドレ
ス値である。

各ネットワーク構成要素にネットワークアドレス及び
UIDが割り当てられるという理由は、ネットワークを通
るパケットの経路指定を容易にするためにはなるべく短
い値が必要であったからである。７ビットSHORT IDは1
28個までのスイッチを考慮したものである。各スイッチ
は多くとも12の外部ポートしか有しておらず、そのうち
の少なくとも一つを用いてネットワーク内のスイッチを
他のスイッチに接続することが必要であるから、多くと
も1408のホストしかありえない。これは、本発明の予想
される全ての用途に対して十二分であると考えられる。
いうまでもなく、12ビット・ネットワークアドレスをも
用いることにより、ネットワーク構成要素の許容数を簡
単に倍増することができる。

データパケットを初めて伝送するとき、このデータパ
ケットが送られるネットワーク構成要素のネットワーク
アドレスはパケットの最初の数バイトに記憶される。ル
ータ218は、ショートアドレス（short address）の値、
及びパケットを受信する入力リンクを用い、どの出力リ
ンクを用いてデータパケットを再伝送すべかを決定す
る。

一般に、ルータ218の目的は、システム資源（即ち、
出力リンク）を公正且つ正当にデータパケットに割り当
てることである。パケット枯渇を防止することもルータ
218のジョブである。ルータは、先着先行的経路指定優
先順序を用い、資源に対する要求を、該要求が受け取ら
れた順序で利用可能資源のセットと比較する。利用可能
資源に整合すべき最初の要求を選択し、これが必要とす
る資源を割り当てる。この処理を繰り返す。

先着先行的経路指定秩序を用いると、割当てが、早く
来た要求の必要性と衝突することのないかぎり、この早
く来た要求の前に、遅く来た要求に資源が割当てられ
る。この経路指定秩序により、利用可能資源が資源要求
者に割当てられる速度が最大となる。同報通信データパ
ケットに対して、この経路指定秩序は、要求された資源
が同報通信要求によって留保されるということを意味
し、遅く来た要求が同報通信データパケットの進行を妨
げるということがない。

第13図は本実施例において用いるルータ回路218の基
本的構成部材を示すものである。第９図に示すように、
ルータ218はバス230上でパケット宛先アドレスを受信す
る。経路指定要求及び出力リンク可用信号は、ルータバ
ス232上で、ルータ218によるリンク選択値の伝送ととも
に時多重化される。

各「経路指定アドレス」は11ビット・パケットアドレ
ス及び４ビット入力リンク番号を有す。経路指定アドレ
スはレジスタ420に記憶される。経路指定テーブル422は
経路指定アドレス値によってインデックスされるルック
アップテーブルである。経路指定テーブル422は、可能
性ある全ての経路指定アドレス値に対するエントリを含
んでおり、これは、経路指定アドレスに対応するパケッ
トを経路指定するために用いられる可能性ある出力リン
クを特定する。

入力リンク装置がそのFIFOバッファの出力部における
新しいパケットの受信を検出すると、該装置はリンクマ
スク部232A上に要求信号を送る。

経路指定選択回路424がバス232Aをモニタし、何等か
の経路指定要求が主張されているかどうかを調べる。ど
れか一つの経路指定エンジンサイクル中に１つまたは複
数の経路指定要求が主張されている場合には、選択回路
424が要求のうちの一つを選択する。選択された要求
は、選択されたリンク装置へ適切な時にバス232A上でオ
ン信号を送ることにより、肯定応答される。この肯定応
答信号は、前記信号を送られたリンク装置がその経路指
定要求をバス230上で伝送するように選択されたという
ことを、該リンク装置に知らせ、次いで、この選択され
た入力リンク装置は、その経路指定要求に対するパケッ
ト宛先アドレスをバス230を介してバッファ、即ち、レ
ジスタ420へ送る。

要求選択回路424は循環優先順位エンコーダであり、
要求が選択された最後のリンク装置上で競合する要求の
なかから選択するための優先順位に基礎を置く。これに
より、全ての要求が短時間内に受容され、パケット枯渇
防止を助ける。

各経路指定テーブルアドレスは、線路230上で受信さ
れる11ビット・パケット宛先アドレス、及び要求選択回
路424によって提供される付属の４ビット入力リンク番
号を含んでいる。経路指定テーブルアドレスはレジスタ
420に記憶され、経路指定テーブルによって用いられ
る。経路指定テーブル422はランダムアクセスメモリに
記憶され、レジスタ420内の15ビット値が経路指定テー
ブル422から一つの値（経路指定マスクと呼ばれる）を
検索するためのアドレスとして用いられる。経路指定テ
ーブル422によって出力される選択済み経路指定マスク
は、後で詳細に説明するように、次の経路指定エンジン
サイクルの始まりにおいて経路指定エンジン430によっ
てラッチされる。

第14図は、線路230によって送らるるパケットアドレ
スがどのようにして到来パケットの最初の２つのデータ
バイトから引き出されるか、及び、このデータが、要求
選択回路424によって発生される入力リンク番号とどの
ようにして結合されるかを示すものである。なお、第12
図をも参照されたい。本実施例においては、パケットア
ドレスは長さ15ビットである。将来は、パケットアドレ
スまたは入力リンク番号に対して用いられるビット数が
増す可能性がある。

経路指定テーブル422は可能性ある全ての経路指定ア
ドレスのためのエントリ426を有す。換言すれば、該テ
ーブルは、４ビット入力リンク番号と11ビット・パケッ
トアドレスとの可能性ある全ての組合せのためのエント
リを有す。これら２つの値は15ビットを占めるから、テ
ーブル422内のエントリの数は2¹⁵、または32,768とな
る。各エントリは記憶装置の２バイトを占め、従ってテ
ーブル422は65,536バイトの記憶装置を必要とする。一
般に、経路指定テーブル内のエントリのうちの少数だけ
が「合法的」経路指定要求を表し、他の全てのものは、
改悪されたかまたは違法な要求値を表す。違法要求に対
するテーブルエントリはBC＝１であり、マスクの残りの
部分は全てゼロに等しい。データパケットが違法経路指
定要求を発生する場合には、このデータパケットはスイ
ッチから追い出される。

経路指定テーブル422が入力リンク番号及びネットワ
ークアドレスによってインデックスされ、ネットワーク
アドレスのみによってはインデックスされないという理
由は次の通りである。パケット内のネットワークアドレ
スが改悪されているということがないならば、経路指定
テーブルをネットワークアドレスによってインデックス
することができる。経路指定テーブル内のエントリは、
なお、アップ／ダウン経路指定規則に従っている。これ
が可能であるのは、ネットワーク内の任意の所定位置か
ら特定ネットワークアドレスまでの少なくとも１つの通
路が常にあるからであり、これは、パケットがネットワ
ーク内のその現在位置への合法的経路上を進むものと仮
定すると、アップ／ダウン経路指定規則に違反しない。
この合法的通路は、ネットワークアドレスのみによって
インデックスされるスイッチ経路指定テーブルに記憶さ
せることが可能である。しかし、パケット内のネットワ
ークアドレスが改悪されており、経路指定テーブルが入
力リンク番号によってインデックスされないとすると、
デッドロックを持つ可能性がある。これは、パケット
が、その宛先ネットワークアドレスが改悪された後に
「間違った順番をとる」可能性があるからである。

80のネットワーク構成要素を持つネットワークにおい
ては、81程度の合法的パケットアドレスがあるに過ぎ
ず、これには、各ネットワーク構成要素に対する１つの
アドレス、及びパケットをネットワーク上の全てのホス
トへ送るための１つまたは複数の「同報通信」アドレス
が含まれている。また、入力リンク番号とパケットアド
レスとの若干の組合せは違法となる。即ち、これらは、
パケットをその宛先から遠ざける経路に対応している
か、またはデッドロックを生じさせる可能性があるから
である。従って、80構成要素ネットワークにおいては、
任意の特定スイッチに対する経路指定テーブルは320か
ら750までの合法的エントリを持つのが普通である。

経路指定テーブル内の各エントリは、経路指定マスク
とも呼ばれるリンクベクトルを含んでいる。経路指定マ
スクの一例を次に示す。

経路指定テーブル内の各アドレスは、入力リンクから
受け取られる可能性のある経路指定要求値のうちの一つ
を表し、従って、ここでは、入力リンク番号とパケット
アドレスとの連結によって表されている。

各経路指定テーブルエントリ426内の経路指定マスク
は13のマスクビットを含んでおり、SCP含むスイッチの
出力リンクの各々に対して１つのビットがある。オン
（即ち、「１」に等しい）となっている各マスクビット
は、パケットの経路指定に用いられる出力リンクを表
す。経路指定マスクも同報通信ビットBCを含んでおり、
これは、パケットアドレスが同報通信アドレスである
か、通常アドレスであるかを示す。経路指定マスク428
の一例を第14図に示してあり、これも、以下に説明する
理由で、経路指定マスク上の有効ビット及びその下のリ
ンク番号を示している。

同報通信ビットBCがオン（即ち、「１」に等しい）と
なっている場合には、このパケットは同報通信パケット
と呼ばれる。同報通信パケットは、経路指定マスクによ
って特定される全ての出力リンクへ必ず同時に送り出さ
れる。

同報通信ビットBCがオン（即ち、「０」に等しい）と
なっている場合には、このパケットは非同報通信パケッ
トと呼ばれる。非同報通信パケットに対しては、経路指
定マスクは各出力リンクに対して「１」に等しいマスク
ビットを有し、これは、パケットをその宛先へ経路指定
するのに用いられる（即ち、パケットは、経路指定マス
クによって特定される出力リンクのうちの任意の単一の
もの上で経路指定される）。多くの場合、いくつかの異
なる交互出力リンクを用いてパケットをその宛先へ経路
指定することができる。これはメッシュ接続式ネットワ
ークの一つの利点である。経路指定エンジン430は、パ
ケットを経路指定するための経路指定マスクによって特
定される出力リンクのうちの適正のものを選択する。

各経路指定テーブルエントリ426の経路指定マスク内
のビット値は、前述のアップ／ダウン経路指定規則によ
って決定される。アップ／ダウン経路指定規則によれ
ば、データパケットに対する合法的経路のセットは、使
用された最後のリンク（即ち、現在スイッチを取るため
に使用されたリンク）がアップリンクであったかダウン
リンクであったかによって定まる。前のスイッチがパケ
ットをダウンリンク上で伝送していた場合には、ダウン
リンクのみが次のスイッチによって用いられる。しか
し、前のスイッチがアップリンクを使用していた場合に
は、アップ及びダウンの両方のリングが次のスイッチに
よって合法的に使用される。また、各経路指定マスク内
に示される使用可能リンクのセットは、データパケット
を移動させてその宛先へ近付けるリンクを含んでいるだ
けである。

第14図は、経路指定エンジン430に読み込まれるとき
の「経路指定要求」、即ち、経路指定マスク428のフォ
ーマットを示すものである。有効フラグと呼ばれる最上
位のビットは、経路指定要求が経路指定エンジンにロー
ドされつつあるときには「１」にセットされ、処理され
つつある新しい経路指定要求がないときには「０」にリ
セットされる。次の14ビットは、前述したように、経路
指定テーブル422のうちの選択されたエントリから得ら
れるリンクベクトルである。最後の４ビットは経路指定
中のパケットに対する入力リンク番号である。

経路指定エンジン430は、現在使用可能な出力リンク
を表すリンク可用マスクを経路指定要求と比較する。詳
述すると、経路指定エンジン430の目的は、各新しいパ
ケットの出力リンク必要性をスイッチの可用出力リンク
と整合させることである。経路指定エンジン430によっ
て発生される経路指定選択値はクロスバースイッチ212
（例えば第８図及び第９図に示す）によって使用されて
そのマルチプレクサをセットアップし、これにより、特
定の入力リンクを１つまたは複数の特定の出力リンクに
接続する。経路指定エンジンは、米国特許第5179558号
の主題である。

第12図について前述したように、各出力リンク装置32
6は「リンク可用」信号を伝送し、これは、この出力リ
ンクが経路指定のために利可用能であるか、または既に
使用または阻止されているかを示す。バス232は全ての
出力リンクからのリンク可用信号線を持っている。経路
指定エンジン430は、各新しい経路指定エンジンサイク
ルの始まりにおいてバス232上のリンク可用信号をサン
プリングする。次いで、経路指定エンジン430は可用リ
ンクマスクを用いて経路指定選択を行なう。

経路指定エンジン430は、１つまたは複数の可用リン
クをもって経路指定要求に整合することのできるように
なると、該エンジンは経路指定選択値を発生し、これを
バス232上に出力する。この経路指定選択値は、４ビッ
ト入力リンク番号、充足された経路指定要求からの同報
通信ビット及び有効ビット、並びに、入力リンクに接続
されるべき出力リンクを識別する出力リンクマスクから
成っている。前記の入力リンク番号、同報通信ビット及
び有効ビットはルータバスの部分232B上で伝送され、出
力リンクマスクはルータバスの部分232A上で伝送され
る。ルータバス233上で伝送される経路選択値は、入力
リンク装置220及び出力リンク装置222並びにクロスバー
スイッチ212（第９図）によって用いられ、特定入力リ
ンクを１つまたは複数の特定出力リンクに接続する。

「有効」出力ビットは、経路指定エンジン430が新し
い経路選択を出力しているサイクル中にのみオンとな
る。従って、経路指定エンジン430によって出力される
「有効」ビットは、経路指定エンジン430がいずれの未
決定経路指定要求をも可用出力リンクと整合させること
のできないサイクル中は、オフとなる。

制御回路435は経路指定エンジン430及び要求選択回路
424に対するクロック信号を発生する。これらクロック
信号はまたパケットアドレスバス230及びルータバス232
の使用を制御する。そのタイミングプロトコルについて
は第16図について後で説明する。

制御ロジック435はまたSCP216によって用いられ、ネ
ットワークの再構成中に経路指定テーブル428を再ロー
ドし、ルータ218の状態のトラックを保持し、及び、ス
イッチ全体が賦勢またはリセットされると或るファーム
ウェアを経路指定エンジン430にロードする。

経路指定エンジン 第15図は経路指定エンジン430の実施例を示すもので
ある。本実施例においては、経路指定エンジンは計算構
成部材のアレイ450で形成されており、該部材の各々を
第15図においてボックスで表してある。図示のアレイ
は、ザイリンクス（Xilinx）社製のザイリンクス3090型
と呼ばれるプログラマブルゲートアレイを表している。
ザイリンクス3090型アレイは16の桁を有しており、各桁
には12の組合せ論理ブロック（CLB）がある。CLBは、種
々の論理及び記憶の機能を行なうように電気的にプログ
ラムされる。各CLBは２つのフリップフロップ及び２つ
の機能装置を有す。各機能装置は４つの入力変数までの
すべてのブール関数を計算することができる。CLBは、
機能ブロックまたはフリップフロップから直接に来るこ
とができる２つの出力を発生する。また、各CLBの近く
には２つのトライステートドライバがある。これらドラ
イバは、チップを横切る水平の金属トレースに接続さ
れ、バスを構成することができる。プログラマブルロジ
ックを提供するほかに、ザイリンクス3090型アレイは、
相隣るCLB間、及び該アレイの外側の回路に対するイン
タフェースを提供する複数のパッドセル間のプログラマ
ブル相互接続を提供する。即ち、このアレイの挙動及び
機能は、外部転送元（例えば、各スイッチ内のSCP）か
ら該アレイにロードされる制御ビットのパターンによっ
て決定される。チップ製造の一部としてカスタマイゼー
ション（customization）は行なわれない。

経路指定エンジンアレイ450は13の桁451〜463を用
い、その各々には19の論理ブロックがある。これら桁45
1〜463の各々は単一の経路指定要求を記憶及び処理す
る。また、アレイの右側には、13のレディ信号ジェネレ
ータ（RG）の桁465及び13の出力信号ジェネレータ
（Ｏ）の桁468がある。

経路指定要求はアレイの左側で受け取られる。アレイ
の左側に示してある信号記号は第14図に示す経路指定要
求のフォーマットに整合する。

出力リンク可用マスクはアレイ450の右側で受け取ら
れる。出力リンク可用マスクを記号RDYOないしRDY12で
表してあり、これは、第13図に示すようにバッファ440
から受け取られる。

アレイ450からの出力は、経路指定エンジンによって
作られる経路指定選択であり、アレイの右側からバス47
0上に現われる。第13図について前述したように、経路
指定選択は、19ビット、即ち、経路指定選択がなされた
ということを示す有効ビット、13ビット出力マスク、並
びに経路指定要求からの同報通信ビット及び４ビット入
力リンク番号を含んでいる。

アレイの13の桁451〜463はルータの先着先行的秩序を
実行する行列として働く。行列の右側にある桁は古い未
充足の経路指定要求を保持し、左側の桁はもっと新しい
要求を保持する。

全アレイは周期的クロックサイクルで働く。経路指定
エンジンはクロックサイクル当り１つの経路指定要求を
受け入れ、各クロックサイクル中に経路指定選択を行な
おうと１回試みる。

第16図について説明すると、各クロックサイクルは６
つの位相T0〜T5を有す。各位相は80ナノ秒継続し、総計
クロックサイクルは480ナノ秒になる。ルータクロック
サイクルは、クロック信号T03で示す２つの主な副位相
を有す。第１の副位相中はT03＝１であり、第２の副位
相中はT03＝０である。

後で説明するように、経路指定要求をルータ218へ送
り、この要求を処理し、次いで経路指定選択をリンク装
置及びクロスバースイッチへ送るには３ルータサイクル
がかかる。

経路指定要求は次のようにしてルータ218へ送られ
る。T4中、ルータへ送られることを必要とする経路指定
要求を有する各入力リンク装置は、ルータバス232のそ
の対応の線路上でオン信号を主張する。経路指定選択回
路424はT4中にルータバス232をモニタし、何等かの経路
指定要求が主張されているかどうかを調べる。唯１つの
要求が主張されている場合には、これは肯定応答され
る。いずれか１つのクロックサイクル中に複数の経路指
定要求が主張されている場合には、経路指定選択回路42
4は、前述したように、これら要求のうちの１つだけを
選択する。

選択された要求は、次のルータサイクルのT3中、選択
されたリンク装置へバス232上でオン信号を送ることに
よって肯定応答される。この肯定応答信号は、信号を送
られたリンク装置に、該装置がその経路指定要求をバス
230上で伝送するように選択された、ということを知ら
せる。クロック位相T3〜T5中、選択された前記リンク装
置はその経路指定要求に対するパケットアドレスをバッ
ファ420を介して経路指定テーブル422へ送る。位相T3〜
T5中、経路指定テーブル422はアクセスされ、前記経路
指定要求に対応するリンクベクトルは、T5の終りまで
に、その出力部においてレディ状態となる。

位相T5中、全ての出力リンク装置はその可用フラグ値
をルータバス232上で主張し、これにより、これら信号
は次のルータサイクルの始まりにおいて経路指定エンジ
ンに対してレディ状態となる。

T0の始まりにおいて、経路指定エンジン430は、ルー
タバス232からの可用フラグを、及び現在経路指定要求
がある場合にはこれを、リンク内にラッチする。現在経
路指定要求は、経路指定テーブル422によって出力され
るリンクベクトル、並びに要求選択回路424によって出
力されるリンク番号及び有効ビットを含んでいる。

ルータサイクルT0〜T5は残り部分中、経路指定エンジ
ン430はリンク内にラッチされた可用データを、経路指
定エンジン430のデータ桁内に記憶されている全ての未
充足の経路指定要求と比較する。この比較の結果は、T5
の終りにおいて、経路指定エンジンの出力桁468内にラ
ッチされる。しかし、経路指定エンジンによって発生さ
れた経路指定選択は、次ぎに続くルータサイクルのT1ま
では、ルータバス232上に主張されない。このルータサ
イクルのT1〜T5中、経路指定選択のビットがオンとなっ
ている場合には、リンク装置及びクロスバースイッチは
経路指定選択出力を処理し、これにより、特定入力リン
ク装置を特定出力リンク装置と接続する。これらリンク
装置はまた、前記特定入力リンク装置のFIFOバッファ31
0内のデータを伝送開始する準備をする。

このルータサイクルのT3中、クロスバー回路212は、
経路指定エンジン及び特定出力リンクによって主張され
た入力リンク番号を覚えているのであり、出力リンク番
号をルータバスのリンクインデックス部上で主張し、こ
の特定入力リンクマ番号に対応するフロー制御マルチプ
レクサをセットアップする。しかし、経路指定選択内の
同報通信ビットがオンとなっている場合には、T3中に主
張された出力リンク番号は所定の番号（例えば、15また
はＦ）にセットされる。

要約すると、ルータ218の各部分は各６分の１ルータ
サイクル中に個別のタスクを行なう。また、ルータバス
232は時多重化されて、経路指定要求を経路指定要求選
択回路424へ送り、及び、経路指定選択をリンク装置へ
送る。

１段当り６つの80nsクロックサイクルが３段パイプラ
インにおいて用いると、ルータ218は１秒当り２百万を
若干越えるパケットを経路指定することができ、そして
１スイッチ当り約1.44ミリ秒の待ち時間を各パケットの
通路内に加える。このルータパイプラインの３つの段
は、（１）経路指定要求マスクを発生するための入力リ
ンク選択及び経路指定テーブル索引、（２）経路指定エ
ンジンサイクル、及び（３）クロスバースイッチ212及
びリンク装置への経路指定選択の伝送である。

ルータサイクルの各位相中の経路指定エンジンの動作
について次に更に詳細に説明する。各ルータサイクルの
始まりに、T0の始まりにおいて、経路指定要求及び可用
出力リンクマスクが読み込まれる。経路指定要求はアレ
イ451の左端桁にラッチされ、リンク可用マスク（RDY0
〜RDY12）はレデイ信号桁465にラッチされる。また、ア
レイに既に記憶されている各未充足経路指定要求は、ア
レイ内の右に、未充足要求によって占められていない少
なくとも１つの桁がある場合には、アレイ内で右へ１桁
シフトされる。

ルータサイクルの最初の副位相中、いくつかのセット
の信号がアレイを横切って伝播する。先ず、リンク可用
マスクが右から左へアレイを横切って伝播する。要求取
扱い桁451〜463の各々における回路はその桁に記憶され
ている経路指定要求をリンク可用マスクと比較する。非
同報通信要求（BD＝０となっている）を記憶している桁
において、少なくとも１つの使用可能MASKビットが使用
可能RDYビットと整合する場合にMATCH信号が発生され
る。

同報通信要求（BC＝１となっている）を記憶している
桁において、全ての使用可能MASKビットが対応のRDYビ
ットに整合する場合にのみ（即ち、この要求が必要とす
る全ての出力リンクが使用可能である場合にのみ）、MA
TCH信号が発生される。

同報通信信号要求（BD＝１の）を記憶している桁はま
た、この同報通信要求のMASKビットに整合するRDY信号
の伝播を阻止する。事実、同報通信要求は、この要求が
必要とする可用出力リンクを「リザーブ」（reserve）
する。これが行なわれないと、同報通信パケットの経路
指定は、同報通信パケットが必要とする出力リンクの個
々のものに整合してこれを使用する後続の要求によって
永久に妨害される可能性がある。

MATCH信号は、整合が見いだされる桁を通って上方へ
伝播される。即ち、MATCH信号は、クロックサイクルの
最初の位相中に伝播する第２のセットの信号である。

２つまたはそれ以上の桁がMATCH信号を発生すること
は完全に可能である。最も古い未充足要求に最初の考慮
を与えるためには、整合が見いだされた右端桁を選択す
ることが必要である。これを行なうため、ANSWEREDと呼
ばれる信号が、アレイの最上位にあるC1セルを通ってア
レイの右側から左へ伝播する。ANSWERED信号は、これ
が、使用可能MATCH信号を持つ有効桁（即ち、VALID＝
“1"）に出会うまで、「０」の値を有し、この時点でAN
SWEREDは「１」に等しくセットされる。

ANSWERED信号は、ルータサイクルの最初の副位相中に
伝播する第３の型の信号である。

T3の終りにおいて、出力イネーブル信号ND_ENABLE
が、右隣の桁から「０」のANSWERED信号を受け取る使用
可能MATCH信号を持つ右端桁に対して発生される。いう
までもなく、多くのクロックサイクル中は、可用リンク
マスクに整合する桁はなく、また、出力イネーブル信号
は発生されない。さしあたりは、出力イネーブル信号が
１つの選択された桁に対して発生される場合について考
える。

多くとも、唯１つの桁が、全ての１クロックサイクル
中に、使用可能ND_ENABLE信号を有しているだけであ
る。使用可能ND_ENABLE信号を有している桁が無い場合
には、これは、経路指定エンジンが、可用出力リンクに
整合した経路指定要求を見付けることに失敗した、とい
うことを意味する。

ルータサイクルの第２の副位相中、使用可能ND_ENABL
E信号を持つ桁からの次のデータ値が、即ち、全ての整
合済み経路指定マスクビット（即ち、可用出力リンクが
ある使用可能マスクビット）、同報通信ビット、リンク
番号ビット、及び有効ビットが、アレイの出力桁468へ
伝播される。

出力桁468における回路は次のように働く。非同報通
信要求（BC＝０）に対しては、使用可能マスクビットの
うちの最下位のものが出力されるだけであり、他の全て
のビットは使用禁止となる。同報通信要求（BC＝１）に
対しては、全ての使用可能マスクビットが出力される。
両方の型の要求に対しては、同報通信ビット、リンク番
号ビット、及び有効ビットも出力桁468によって出力さ
れる。

その結果の経路指定選択値は、使用可能有効ビット、
１つの使用可能マスクビット（同報通信パケットでない
限り）、並びに経路指定要求の同報通信ビット及び入力
リンク番号を持つ。

明らかに考えられるように、パケットが必要とする出
力リンクが使用中である場合がしばしばあるので、或る
パケットを即時に経路指定することのできない場合があ
る。従って、経路指定エンジンアレイ450の桁451〜463
は、未充足経路指定要求が記憶されて可用出力リンクと
周期的に比較される行列として働く。

経路指定エンジンが可用出力リンクをいずれかの未充
足経路指定要求と整合させることに失敗すると、アレイ
によって出力されるデータは使用禁止VALIDビットを持
つ。スイッチ内のリンク装置及びクロスバー回路は、VA
LIDビットが使用禁止となるサイクル中には経路指定エ
ンジンの出力を無視する。

新しい要求がアレイ450に入力されるにつれ、未充足
または無効要求を含んでいる要求取扱い桁は、この新し
い経路指定要求のための余地を作るために、右へシフト
することが必要である。アレイ内の全ての要求取扱い桁
451〜463は、未充足要求を保持しているアレイ右側にあ
る桁を除き、各サイクル中に右へシフトされる。

詳述すると、各桁451〜463は、次のような或る条件が
満たされる場合、桁からその左へデータをロードする
（左端桁は経路指定要求バッファ428からロードす
る）。即ち、 （１）桁が無効要求を含んでいる場合にこの桁が該桁か
ら左へデータを重ね書きされる場合、または、 （２）右にある少なくとも１つの桁が該桁からその左へ
データをロードする場合、または、 （３）桁内の経路指定要求が既に充足され、出力するよ
うに選択されている場合、 である。

桁が結果を供給し、そして右へシフトする桁がない場
合、要求は桁の内容でその左へ重ね書きされる。他方、
アレイが、結果を供給する桁の右へ無効要求を含んでい
る場合には、既に充足された要求は右へ１桁シフトして
アレイ内に留まる。

このような要求が後続のサイクルにおいて結果を供給
することのないようにするには、各桁内にBC及びVALIED
値を記憶しているレジスタの入力を、桁から左へ、NO_E
NABLE信号とAND処理する。これは、桁が結果を供給して
同じサイクル内でシフトする場合、要求は、これが次の
桁内に右へシフトすると、無効化され、そしてそのBCビ
ットはクリアされると、いうことを意味する。

出力桁468によって発生される最後の出力は、各サイ
クルの終りにおいて出力桁468内のラッチ（図示せず）
に記憶される。この出力桁に記憶された出力信号は、次
の経路指定エンジンサイクルのT1サブサイクル中にルー
タバス232上で伝送される。

サブシステムをモニタする出力リンクによって（即
ち、第13図におけるラッチングバッファ440を介して）
供給されるRDY信号は、経路指定エンジンによって直接
使用することができない。これは、ルータ218がパイプ
ライン回路の一部であるからである。経路指定エンジン
430が、特別の出力リンクを使用する出力を供給する場
合には、この出力リンクを、ルータの後続のクロックサ
イクル中の使用にレディ状態となっていない（即ち、使
用可能でない）ように見えさせることが必要である。こ
れは、受信RDYマスクを出力マスクの補数とAND処理し、
その後、これを、経路指定エンジンの桁451〜463内の経
路指定要求の行列へ送り出すことによって、行なうこと
ができる。

同報通信パケット取扱い 同報通信パケットは、一般に、１つのホストコンピュ
ータによってネットワーク内の他の全てのホストへ送ら
れるメッセージである。スイッチによって始動される同
報通信パケット及び限定配布先同報通信を含む他の型の
同報通信パケットも使用可能であるが、同じ経路指定及
び枯渇防止の配慮を全ての型の同報通信パケットに適用
する。

同報通信パケットは、多数のネットワーク−リンク上
で同報通信メッセージを同時に伝送することが必要であ
るので、一般に、メッシュ接続式ネットワークにおいて
取り扱うのに最も難しい型のパケットである。また、同
報通信パケットを全ての宛先へ迅速に確実に進ませるこ
とが必要である。即ち、これは同報通信パケットによっ
て与えられる重要な機能であるからである。

同報通信パケットの典型的な使用は次の通りである。
ホストＡはホストＢへメッセージを送りたいと欲する。
しかし、ホストＡはホストＢのネットワークアドレス
を、即ち、各パケットの最初の２バイトに記憶されてい
る11ビット・アドレスを知っていない。そこで、ホスト
Ａは、ホストＢのネットワークアドレスを得るための機
構が必要になる。これは、周知の解決手段を持っている
ローカルエリアネットワークにおける周知の問題であ
る。この解決手段は、「同報通信メッセージ」またはパ
ケットをシステム内の全てのホストへ送ることである。
この同報通信メッセージの内容は、「ホストＢ、あなた
のネットワークアドレスを含んでいるメッセージをネッ
トワークアドレスＸにおけるホストＡへ送ってくださ
い」というものである。この同報通信メッセージはネッ
トワーク内の全てのホストコンピュータへ送られる。し
かし、ホストＢだけが（Ｂが居る場合）これに応答し
て、要求された情報をホストＡへ送る。そこで、ホスト
ＡはそのメッセージをホストＢへ送ることができる。良
好に設計されたローカルエリアネットワークにおいて
は、この伝送全体に要する時間は、一般に、１秒のうち
の極めて小さな部分である。

同報通信メッセージが用いられる他の場合は、ホスト
ＡがホストＢへパケットを送ろうとするが、ホストＢが
このパケットの受信を肯定応答しない場合である。この
状態に対する一般的なプロトコルは、ホストＡがパケッ
トを再び送ることである。それでも肯定応答が受信され
ない場合には、ホストＡは、このパケットがホストＢに
対する正しいアドレスを持っていないものと結論する
（例えば、アドレスが転化したため、または、ホストＡ
は知らないでいたが、ホストＢのアドレスが変更されて
いたため）。そこで、ホストＡは前述の同報通信パケッ
トプロトコルを用いてホストＢの現在のネットワークア
ドレスを見付ける。

同報通信パケットが有用であるという多くの状態は周
知であるが、メッシュ接続式ネットワークにおいてどの
ようにして同報通信パケットを経路指定するかというこ
とはよく知られていない。次ぎに、これを本発明におい
てどのようにして行なうかを説明する。

第17図にメッシュ接続式ネットワーク700を略示す
る。このネットワークは16のスイッチ710〜740、及び27
のホストH1〜H27を有す。スイッチ710は、後で説明する
理由で、ネットワークの根ノードと呼ばれる。第17図
は、主として、スイッチ間のリンクが次の２つの特徴を
割り当てられているという点において、第２図とは異な
る。即ち、（１）「アップ」として知られている主方
向、及び（２）いわゆる「スパニングツリー」リンクが
「追加」線よりも太い実線で示されている、という点で
ある。スイッチ710〜740及びスパニングツリーリンクが
全体で「スパニングツリー」を形成する。

ホストH19で始まる同報通信パケットが後に続く通路
について考えてみる。このパケットには「8FF」のよう
な一意的11ビット「同報通信パケットアドレス」が与え
られている。最初、このパケットはスイッチ732、724、
712、次いで710を通ってネットワークツリーを上方へ移
動して根に至る。これを行なうため、これらスイッチの
各々内の経路指定テーブルは、使用される入力リンクに
対応するリンクベクトルエントリ及び同報通信パケット
アドレスを有す。スイッチ732、724及び712の各々内の
リンクベクトルは、パケットに使用可能な経路のみが、
パケットをツリー710の根の方へ上方へ移動させるリン
クに沿っている、ということを示す。

パケットが根スイッチ710に到達すると、同報通信パ
ケットはネットワーク内の全てのホストへ向かって全て
のスパニングツリーリンク（第17図において追加リンク
よりも太い実線で示す）を通って下方へ再経路指定され
る。根内の経路指定テーブルは、同報通信パケットが到
達する入力リンクとは関係なしに、同報通信パケットに
対する同じ同報通信リンクベクトル値を有す。詳述する
と、同報通信リンクベクトルは、受信された同報通信パ
ケットが、スイッチに接続された全てのスパニングツリ
ーリンク上で同時に伝送される、ということを特定す
る。これは、受信されたデータパケットが、これが受信
されたと同じリンク上で再伝送される、という唯一の場
合である。

第17図に示すネットワーク700においては、同報通信
パケットは根パケット710からスイッチ712、714、716、
718及び720へ同時に伝送される。また同時に、同報通信
パケットは、根スイッチに接続された全てのホスト（第
17図には示していない）へ送られる。この伝送は、要求
された全てのリンクが使用可能となると生ずる。

受信スイッチの各々において、同報通信パケットは、
（１）スイッチに接続された全てのホストへ、及び
（２）ダウンスパニングツリーリンクによって送信スイ
ッチに接続された全ての相隣るスイッチへ、再伝送され
る。換言すれば、同報通信パケットは、ネットワーク内
の全てのホストが同報通信パケットを受け取るまで、ス
パニングツリーを下方へ通って送られる。

要するに、同報通信パケットは、先ず、ネットワーク
のスパニングツリーを上方へ通って根へ経路指定され、
次いで、該ツリーを下方へ通ってネットワーク内の全て
のホストへ伝送される。

どのリンクが「スパニングツリー」であるかを決定
し、ネットワークの根ノードを識別し、及びスイッチに
対する経路指定テーブルを発生する、というプロセスに
ついては以下に説明する。

再構成プロセス 本発明の再構成プロセスは、３つのフェーズを有する
分散プロセスである。このプロセスの第１のフェーズ
は、何時ネットワーク再構成が必要となるかを決定す
る。第２のフェーズはネットワークの現在トポロジを識
別する。即ち、ネットワーク内の全ての機能スイッチ、
リンク及びホストを識別する。フェーズ３においては、
ネットワーク内のスイッチは、ネットワーク内のデータ
パケットに対する全ての合法的経路を定義する経路指定
テーブルを生成する。

故障したネットワーク構成部材の取扱い メッシュ接続式ネットワークにある潜在的問題とし
て、故障したスイッチまたはリンクのために１つまたは
複数のホストがネットワークから隔離させられるという
可能性がある。本発明は、ホストがネットワークから隔
離させられることを防止するための機構を提供するもの
である。第１に、第３図に示すように、全てのホストの
それぞれを別々のリンクで２つのスイッチに接続する。
一つのリンクに接続されたリンクまたはスイッチのうち
の一つが故障しても、他のリンクを賦勢することができ
る。同様に、全てのスイッチのそれぞれを少なくとも２
つのリンクによってネットワークの残部に接続すること
が好ましく、これにより、１つのリンクが故障しても、
ネットワークのブランチ全体がネットワークの残部から
隔離されることのないようにする。

第２の故障取扱い機構は、全てのスイッチのSCP216内
に存在する再構成プログラムである。この再構成プログ
ラムはスイッチ内のリンク装置を絶えずモニタし、ネッ
トワークのいずれの部分の故障をも自動的に検出する。
故障が検出されると（または、新しいネットワーク構成
部材が検出されると）、全てのスイッチの再構成プログ
ラムが自動的にネットワークを再構成する。これは、ネ
ットワーク上のホスト相互間の全ての合法的通路が再計
算されてスイッチ内のルータに記憶される、ということ
を意味する。その結果、単一のハードウェア故障によっ
てホストがネットワークから隔離されるということがな
くなる。

再構成フェーズ１ 再構成開始 第17図について説明すると、スイッチまたはリンクが
ネットワーク700に追加されるかまたはこれから取り去
られると、ネットワークのスイッチ内の経路指定テーブ
ルはネットワークのトポロジを正しく反映しなくなる。
例えば、スイッチ726が故障するかまたはネットワーク
から取り去られると、ネットワーク内の全てのスイッチ
内の経路指定テーブルエントリは間違った値を持ち、ネ
ットワークの構成を正確に反映しなくなる。ネットワー
クを通ずる正しい経路指定を再確立するには、ネットワ
ークを「再構成」すること、即ち、ネットワークを通っ
て伝送されるパケットに対する合法的通路のセットを再
計算すること、が必要である。

第17図に示すように、ホストH11はスイッチ716に対す
る第２のリンクを有し、ホストH12はスイッチ728に対す
る第２のリンクを有す。スイッチ726が故障するかまた
は取り去られると、ホストH11及びH12はそれらの２次リ
ンクを賦勢する。その結果、ネットワークが再構成され
た後、これらホストは新しいネットワークアドレスを持
つことになる。

同様に、新しいスイッチまたはリンクがネットワーク
に追加された場合、全てのスイッチに対する経路指定テ
ーブルは再計算され、ネットワーク内に新しいネットワ
ーク構成要素及び新しい合法的通路を含むこととなる。

第18図について説明すると、ネットワークの構成にお
ける変化を検出するためのプロセスは次のように働く。
同じプロセスがネットワーク内の全てのスイッチにおい
て、及び各スイッチ内の全てのリンク装置に対して実行
される。その理由は、ネットワークのトポロジにおける
全ての変化はリンク装置の状態の変化によって反映され
るからである。即ち、ネットワークに対する追加はリン
ク装置に対する新しい接続として検出され、ネットワー
ク構成要素の取り去りはリンク装置に対する接続の損失
として検出される。第18図に示す流れ図は単一スイッチ
の単一リンク装置に対する状態の変化を測定するための
プロセスを表すものである。

変化を検出するためのプロセス（これは再構成プロセ
スのフェーズ１である）は、再構成プロセスのフェーズ
２及び３最中であっても、常に継続する。

リンク状態検査プロセスは多重レベルプロセスであ
り、各レベルはその結果を階層を上方へ次のレベルへ送
る。状態検査プロセス800のレベルは次の通りである。
ハードウェア調査レベル802は各リンク装置におけるハ
ードウェアによって実行されるエラー検査プロセスであ
る。ハードウェアポーリングレベル804は各スイッチに
おけるルーチンであり、ハードウェア調査レベル802の
出力を周期的に読取り、データ及びフロー制御信号が或
る特定のリンク上で両方向に間違いなく送られているか
どうかを測定する。

メッセージ交換レベル806は、ハードウェアポーリン
グレベル804によって測定されるように、リンクの状態
の変化に反応するソフトウェアルーチンである。リンク
が、ハードウェアポーリングにより、ALIVEである（即
ち、リンクの他端に他のネットワーク構成要素があり、
リンク上で信号を間違いなく送受している）と報告され
ると、メッセージ交換レベル806はリンク上で短いメッ
セージを周期的に送り、リンクが十分に良好な順序でメ
ッセージを送受していることを確認する。

状態変化フィルタ808は、リンク装置の状態がDEADか
らALIVEへ余りに頻繁に変化することを妨げる。

ハードウェア調査レベル 新しいネットワーク接続、及びネットワーク構成部材
の取り去りを検出するほかに、再構成プロセスの第１フ
ェーズは間欠的エラー及びランダムノイズの問題を取り
扱う。例えば、緩いリンク接続またはスイッチもしくは
ホスト制御器内の不適正に動作する構成部材は適正動作
と不適正動作との間で揺れる可能性がらう。また、ノイ
ズのために、ノイズがなければ、適正に働くはずのリン
ク上で伝送されるデータが転化される場合がある。

再構成プロセスの第２及び第３のフェーズは、これら
がネットワーク全体を、或る短い期間、停止させるの
で、比較的費用がかかる。再構成プロセスの第１フェー
ズの役目は、全再構成プロセスが必要な場合にのみ実行
されるということを確かめることである。

第12図について説明すると、各リンク装置及び対応の
制御ロジック384に対する状態レジスタ382は、ネットワ
ークの構成が何時変化したかを測定する際に重要な役目
をなす。各リンク装置内のハードウェアによって行なわ
れる３つの型の状態検査がある。即ち、コード違反検
査、フロー制御検査、及び往復フロー制御検査がある。
これら３つのハードウェア状態検査の結果は状態レジス
タ382に記憶される。

TAXI Rx350及びTAXI Tx370のチップは、データバイ
ト及びコマンドがスイッチ内で11ビットで表されている
にしても、事実上は、データのバイト毎に、及びフロー
制御毎に10ビットを伝送する。その理由は、リンク上に
アップ／ダウン遷移のない長いストリングの「ゼロ」を
持つことが許容されないからである。即ち、このように
なると、TAXI回路がリンク上のデータの流れと同期され
ない可能性があるからである。10ビットを用いることに
より、各10ビット中に少なくとも１つのアップ／ダウン
（または、0/1）遷移があることを確実にすることがで
きる。

各データバイト及びフロー制御コマンドを表すために
10ビットが使用されるにしても、256個の有効データ
値、及び16個の有効フロー制御コマンドが存在している
に過ぎない。その結果、272個の有効10ビット伝送コー
ド及び752個の無効伝送コードが存在する。無効伝送コ
ードが入力リンク装置に受信されると、これは、コーデ
ィング違反の受信を示すビットを状態レジスタ382内に
セットする。

明らかに解るように、単一コード違反の受信は、リン
クが故障したということを必ずしも意味しない。また、
逆に、単一有効コードの受信は、リンクが働いていると
いうことを必ずしも意味しない。

フロー制御の項で前述したように、フロー制御コマン
ドは、256バイトサイクル毎に１回、各出力リンク装置
によって伝送される。これは、このリンク装置のための
リンクに接続されたネットワーク構成部材が存在してい
なくとも、生ずる。その結果、各入力リンク装置のハー
ドウェアは、256バイトサイクル毎に１回、有効フロー
制御コマンドを受信することを期待する。この有効フロ
ーコマンドのセットは、スイッチからのスタート及びス
トップフローコマンド、及びホストからのスタート及び
ストップフローコマンドを含んでいる。ホストに対する
スタートフローコマンドはスイッチから受信されるもの
とは別個のものである。他のフローコマンドはIDHY
（“I don't hear you）と呼ばれる。これらのコマンド
及びハードウェア調査レベルによるそれらの使用につい
ては次に説明する。

いずれかの256バイトサイクル中に有効フローコマン
ドの受信に失敗したことは状態レジスタ382内に示され
る。

往復フロー制御検査は次のように働く。リンク装置
が、受信中のデータにおけるコード違反を確実に検出す
るか、またはフロー制御コマンドの受信に失敗すると、
このリンク装置はIDHYコマンドと呼ばれる特別のフロー
コマンドを伝送する。これは、標準の「スタートフロ
ー」コマンドの特別のバージョンであると考えられる。

リンク装置が有効コード及びフロー制御信号を受信し
ているが、何らかの理由で、転化した信号を送り出して
いる、という状態を考えてみる。例えば、そのTAXI Tx
回路が適正に働いていない。転化した信号を受信する
「遠隔」リンク装置はIDHYフロー制御信号を伝送し始
め、信号がリンク上で「往復」的に間違いなく送られて
はいない、ということをリンク装置に知らせる。即ち、
IDHYフローコマンドにより、リンク装置はこれが適正に
働いていないということを見付けることができる。

IDHYフローコマンドが受信されると、この事がリンク
装置に対する状態レジスタ382内に示される。

要約すると、ハードウェア調査レベルは、各リンク装
置内に、３つのエラーフラグをセットすることのできる
ハードウェアを具備している。何らかの無効コードが受
信されると、コード違反フラグがセットされ、256バイ
ト毎に１回、フロー制御コマンドが受信されないと、フ
ロー制御エラーフラグがセットされ、何らかのIDHYコマ
ンドが受信されると、往復エラーフラグがセットされ
る。

ハードウェア・ポーリング・レベル １ミリ秒毎にほぼ１回、各スイッチ内のSCP216はポー
リングし、リンク装置の各々に対する状態レジスタ382
内に３つのエラーフラグをセットする。ポーリング相互
間の時間は、好ましくは、正常動作中のフロー制御コマ
ンド相互間の間隔の10ないし25倍長くあるべきである。
各型の「エラー」が１つでもあると、対応のエラーフラ
グがセットされる。１つのリンク装置に対するポーリン
グプロセスは次の通りである。

付録１に、スイッチ内のリンク装置の各々に対するSC
Pによって実行されるハードウェア・ポーリング・ルー
チン（Hardware Polling Routine）の疑似コード表示を
記載してある。本明細書の末尾にある付録１〜９におけ
る疑似コードプログラムは、ユニバーサル・コンピュー
タ・プログラミング・コンベンションを用いて記載して
あり、当業者たる全てのコンピュータプログラマに理解
可能に設計してある。注釈及び実行不能ステートメント
は２重星印「＊＊」で始まっている。付録におけるこれ
ら疑似コードプログラムは再構成プログラム及びそのピ
ース相互間のインタラクションを図によるよりは詳細に
示す。

リンク装置に対する３つのエラーフラグが読み取られ
てリセットされる。その結果、リンク装置ハードウェア
は、各ポーリング期間毎に１回、改めてエラーに対する
サーチを開始する。また、ハードウェアポーリングレベ
ル804が何らかのアクションを取る間に、５ポーリング
期間にわたってフラグの値が集積される。５ポーリング
期間中の３期間内にコード違反がある場合、または５ポ
ーリング期間中の３期間内にフロー制御エラーがある場
合には、ポーリングルーチンはこのリンクをDEADと呼
ぶ。これはまたリンクの状態レジスタ内にフラグをセッ
トし、このリンク装置をして、正常フロー制御コマンド
の場所にIDHYコマンドを伝送させ、このリンクの他の側
にあるネットワーク構成要素に、これが有効信号を受信
しつつはないということを知らせる。

５ポーリング期間中の３期間内にIDHYコマンドが受信
されていた場合には、他のエラーフラグの状態とは関係
なしに、このリンクはハードウェアポーリングルーチン
によってDEADと呼ばれる。即ち、リンク上の信号の間違
いのない往復伝送を頑強に阻止する何らかの問題がある
と、ハードウェアポーリングルーチンはこのリンクをDE
ADと呼ぶ。

メッセージ交換レベル 有効モード及びフロー制御コマンドが受信されつつあ
る場合であっても、リンクの他の側にあるスイッチがメ
ッセージを受信してこれに応答することができないとい
う可能性がある。そうである場合には、このリンクは死
んでいる（dead）とみなされる。メッセージ交換レベル
806はスイッチに対してリンクを試験するだけである。
別々のスタートフローコマンドがホスト及びスイッチに
よって使用され、各リンクポートに接続されたネットワ
ーク構成要素の型はこのポートに受信されるスタートフ
ローコマンド型によって決定される。

付録２にはメッセージ交換ルーチンの疑似表示を記載
してある。

ALIVEであると表示されている他のスイッチに対する
リンクに対しては、リンクの適正動作を検査するために
「キープ・アライブ・メッセージ」（keep alive messa
ge）が用いられる。ほぼ５秒毎に、「キープアライブメ
ッセージ」がリンクの他の側にある遠隔ネットワーク構
成要素へ送られる。第19図について説明すると、「キー
プアライブメッセージ」850はデータパケットであり、
このデータパケットは、伝送スイッチのUID（即ち、一
意的48ビット識別子）851、リンクに対するポート番号8
52、及び受信側がそれ自体を識別することによって応答
するということを示す回路フラグ859を示すものであ
る。キープアライブメッセージはまた、リンクネットワ
ークの他の側におけるスイッチによって最後に報告され
たUID（R_UID856）、及びこのスイッチによって最後に
報告されたポート番号（R_PORT858）を含んでいる。

遠隔ネットワーク構成要素が真に生きている（aliv
e）場合には、これは、キープアライブメッセージ850と
同じフォーマットを用いる肯定応答メッセージをもって
応答する。即ち、この肯定応答メッセージはそのUID及
びポート番号を示すだけでなく、更に、キープアライブ
メッセージで受信されたUID及びポート番号をエコーす
る。

最後に、肯定応答メッセージが受信されると、スイッ
チは肯定応答メッセージを遠隔ネットワーク構成要素へ
送り出す。これにより、両方のスイッチはそのメッセー
ジが肯定応答されたことになる。即ち、ALIVEリンクの
状態を確認するためのメッセージ交換は１連の３つのメ
ッセージを用いる。これら３つのメッセージは各スイッ
チ内のSCPによって生成及び処理される。

肯定応答レコードが相応の時間内に受信されない場合
には、元のキープアライブメッセージが遠隔ネットワー
ク構成要素べ数回再伝送される。肯定応答がなおも受信
されない場合には、これは、遠隔ネットワーク構成要素
が存在していないか、またはこれが適正に働いていな
い、ということを意味する、そこでリンクはDEADである
と宣言される。

受信された肯定応答メッセージが、リンクが同じスイ
ッチの２つのリンクポートに接続されているということ
を示す場合には、かかるリンクは有効でないから、これ
らリンクの両方がDEADと表示される。

ハードウェアポーリングレベル804が、リンクがDEAD
であると報告した場合、この状態は状態変化フィルタレ
ベル808へ送られる。キープアライブメッセージは、DEA
Dであるリンク上では送られない。また、ハードウェア
ポーリングレベル804が、リンクがALIVEであると前に報
告しており、次いで、このリングがDEADであると報告す
る場合には、状態変化フィルタレベルは再構成ルーチン
の第２フェーズを直ちに開始する。即ち、死んでいるリ
ンクが新たに検出されると、ネットワークは直ちに再構
成される。

しかし、ハードウェアポーリングレベル804が、リン
クがDEADであると前に報告しており、次いで、このリン
クがALIVEであると報告する場合には、若干の予防措置
が取られる。詳述すると、メッセージ交換レベル806
は、ハードウェアポーリングレベル804からの、DEADか
らALIVEへの状態変化を、15秒毎に１回だけ受け入れ
る。従って、リンクがDEADからALIVEになり、DEADに戻
り、次いで再びALIVEになると、ALIVEへの最後の遷移
は、DEADからALIVEへの遷移が生じた最後の時から少な
くとも15秒経過するまでは、無視される。このフィルタ
作用が、間欠的に働くネットワーク構成部材によって生
ずる可能性のある頻繁な再構成を防止することを助け、
かかる不適正に働く構成部材がDEADである、と宣言する
に至る。

状態変化フィルタレベル このレベル808は、リンクがALIVEからDEADへの遷移を
行なったということをメッセージ交換レベル806が報告
すると、直ちに再構成ルーチンを呼び出す。

しかし、DEADからALIVEへの遷移はフィルタされる。
詳述すると、状態変化フィルタレベル808は、メッセー
ジ交換レベル806からのDEADからALIVEへの状態の変化を
15秒毎に１回だけ受け入れる。このフィルタ作用は、間
欠的に働くネットワーク構成部材によって生ずる頻繁な
再構成を防止することを助ける。

付録３には、状態変化フィルタルーチンの疑似コード
表示を記載してある。

再構成フェーズ２ スパニングツリー発生 本発明の説明においては、スパニングツリーは、ロー
カルエリアネットワーク全体にまたがるノード（即ち、
スイッチ）のツリーである。このスパニングツリーは、
各親ノードをその子につなぐのに必要であるリンクのみ
を含む。このスパニングツリー内のリンクを、本明細書
においては、スパニングツリーリンクと呼び、他の全て
のリンクを追加リンクと呼ぶ。

スパニングツリーリンクは、本発明においては、２つ
の特別の役目を有す。第１に、同報通信メッセージをス
パニングツリーリンク上で伝送し、これらメッセージが
予想どおりの効率的な仕方で伝送されることを確実にす
る。第２に、再構成中にスパニングツリーを用いて、ネ
ットワークのトポロジに関する上方をネットワークの根
まで伝送し、次いで根の下の全てのスイッチへ戻らせ
る。これら２つの特別機能のほかは、ネットワーク内の
全てのリンクは同じ機能をなす。異なる深さレベルにあ
るスイッチ相互間の並列リンク、及び同じ深さにあるス
イッチ相互間の追加のリンクは、ネットワークの動作を
増大させ、数多くのデータパケットを同時に伝送するた
めのネットワークの能力を拡大する。

フェーズ２の概観 第19図及び第20図を参照し、再構成プロセスの第２フ
ェーズがどのように働くかを次に簡単に説明する。再構
成プロセス900はフェーズ２及び３最中に３つの重要な
データ構造902〜906を用いる。ポート情報アレイ902
は、隣のもののUID及び各隣のものによって報知される
ネットワーク内の位置のような、スイッチの直ぐ隣のも
のの各々に関する情報を記憶する。

メッセージデータ構造904は、再構成プロセスのフェ
ーズ２最中に隣のスイッチに送られる情報を記憶するの
に用いられる。

ネットリスト（netlist）906は、ネットワークのトポ
ロジの完全記述を構築するのに用いられ、及び再構成プ
ロセスのフェーズ２及びフェーズ３の両方において用い
られる。

ネットワークの正常動作中は、全てのスイッチは、エ
ポック（Epoch）と呼ばれる同じ「再構成バージョン番
号」を記憶する。例えば、スイッチは全て1225のエポッ
ク値を記憶する。１つのスイッチまたはリンクがネット
ワークに追加されると、再構成後のエポック値は少なく
つも1226になる。

スイッチがネットワークの構成における変化を検出す
ると、該スイッチは、そのエポック番号を増加し、及び
全てのデータパケットの流れを停止することにより、新
しいエポックを宣言する。前記スイッチは、ネットワー
クの構成について記憶していた全ての情報を削除し、次
いで、新しいエポックが存在すること、及びこれがネッ
トワークの根であると考えられるということのメッセー
ジを、直ぐ隣の全てのスイッチへ送る。

このメッセージを受信したスイッチは、この受信した
エポックを該スイッチが記憶していたエポック番号と比
較する。前記受信したエポック番号の方が高い場合に
は、前記スイッチは、ネットワークの構成について記憶
していた全ての情報を削除し、そしてこの新しいエポッ
ク番号を採用する。前記スイッチはまた、前記受信した
メッセージ内の情報を用い、ネットワークについての情
報の新しいセットを構築開始する。後述の所定基準のセ
ットを用い、各スイッチは、その既知の隣のものに対す
る「スパニングツリー」内のその位置を決定することに
より、「ツリー位置」を開発する。次いで、前記スイッ
チは全てのその隣のものへメッセージを送り、新しいエ
ポック及びそのツリー位置について報知する。スイッチ
が再構成メッセージを受け取る度毎に、該スイッチは、
ネットワークのトポロジについてのその情報を更新し、
ネットワークについて今まで該スイッチが知っているこ
とを基礎としてそのツリー位置を更新する。メッセージ
内に何等かの新しい情報があった場合には、スイッチは
それ自体及び全てのその隣のものへメッセージを送り、
その新しいツリー位置を知らせる。

このようにして、新しいエポックについてのメッセー
ジはネットワーク全体に迅速に広がる。また、メッセー
ジは、全てのスイッチが、根ノードのIDについて、及び
ネットワーク内の全てのスイッチの位置を定義するスパ
ニングツリーリンクのセットについて合意するまで、隣
接のもの相互間で交換され続ける。これについては後で
詳細に説明する。

再構成プロセスは「分散プロセス」と呼ばれる。即
ち、ネットワーク内の全てのスイッチは、結局はスパニ
ングツリーという共通の結果の発生へ通ずる計算を同時
に行なうからである。

再構成プロセスはまた「競合プロセス」と呼ばれる。
即ち、ネットワーク内の全てのスイッチは、先ず、それ
自体をネットワーク根ノードと呼ぶことを試み、そし
て、それが根でないとその隣のものから情報を得るとそ
のツリー位置を変えるだけである。各スイッチは、該ス
イッチの主張したツリー位置を特定するメッセージをそ
の隣のものへ送り、次いで、各受信スイッチはこの情報
をそれ自体の情報と比較し、どのセットの情報が適正ス
パニングツリーに対する基準をよりよく満足するかを測
定する。

本発明の重要な態様は、再構成プロセスが何時完成す
るかを決定する再構成プロセスの能力である。換言すれ
ば、各スイッチ内の再構成プロセスは、再構成メッセー
ジをその隣のものへ送ることを何時停止するかを知って
おり、そして、根ノードは、このプロセスの第２フェー
ズが何時完成するかを知っている。これは本発明に独特
なものである。

データ構造 第19図について説明すると、ネットワーク内のスイッ
チの「ツリー位置」をツリー位置アレイ910で表してあ
る。アレイ910の構成素子は、ツリーの根のUID912、ス
パニングツリー内のスイッチの深さ914（即ち、スイッ
チと根ノードとの間のリンク数）、スイッチの親916、
及び親スイッチに対するスイッチのアップリンクのリン
ク番号918である。

重要なこととして、再構成最中はスイッチはスパニン
グツリー内の該スイッチの真の位置を未だ知っておら
ず、そして、ツリー位置アレイ910を用いて、スパニン
グツリー内のスイッチの位置についてのスイッチの現在
の状態を表す。また、ネットワーク内の根ノードは親91
6をも、または親に対するアップリンク918をも有してな
い。根ノードに対し、ツリー位置のこれら構成素子は特
別の「位置ホルダ」値を与えられる。

スイッチの「現在」のツリー位置は、CPOS920と呼ば
れるツリー位置アレイ内に記憶される。

スイッチは、次の場合に安定であるとみなされる。即
ち、該スイッチが全ての隣接スイッチのID及び位置を知
っており、全ての隣接スイッチは基のスイッチのツリー
位置を知らされており、そして、（１）スパニングツリ
ー内のこのスイッチの下には隣接スイッチがないか、ま
たは（２）スパニングツリー内のこのスイッチの下の全
ての隣接スイッチは安定である場合。スイッチの現在安
定値はCSTB922と呼ばれ、.FALSEまたは.TRUEのいずれか
に等しい。

「Ｓ」924はスイッチのUIDであり、SHORTID926はスイ
ッチに前に割り当てられた７ビットSHORT IDである。
スイッチＳがネットワークに追加されてターンオンされ
た場合には、このスイッチに前に割り当てられているSH
ORT IDはない。

ポート情報アレイ902はポート情報レコード930のセッ
トを有す。各ポート情報レコード930は、スイッチのポ
ートの各々に接続されたネットワーク構成要素に関する
情報を記憶する。前記レコードの各々は項INFO〔Ｐ〕に
よって識別される。ここに、「INFO」はポート情報アレ
イ902の識別子であり、「〔Ｐ〕」は、Ｐに割り当てら
れた値に従ってレコード930のうちの一つを識別する。
各ポート情報レコードの構成素子は次の通りである。

INFO,〔Ｐ〕TYPE932は、隣のものが、スイッチ
（「Ｓ」）、ホストコンピュータ（「Ｈ」）、またはDE
AD（「Ｄ」）であるかどうかを識別する。TYPE値はハー
ドウェアポーリング層804によって連続的に発生され、
従って再構成プロセスのフェーズ２に対して使用可能で
ある。スイッチ及びホストは別々のセットのフロー制御
コマンドを使用する。第18図について前述したハードウ
ェア調査レベル802は、どのフロー制御コマンドが受信
されつつあるかを検出し、そしてTYPE値を状態レジスタ
382に記憶し、リンクによって接続されているものがス
イッチであるかまたはホストコンピュータであるかを示
す。ポーリングがハードウェアポーリングレベル804に
よってALIVEであると確認されると、このTYPE値は、各
ポートＰに対するポート情報アレイ902のINFO〔Ｐ〕.TY
PE構成素子に記憶される。同様に、DEADリンクもアレイ
902のINFO〔Ｐ〕.TYPE構成素子内に示される。

TYPE情報は、再構成プロセスの第２フェーズ中は廃棄
されない。もっと一般的にいうと、再構成の始めにおい
て、スイッチ自体のポートに関する状態情報は留保さ
れ、他のスイッチの状態及びツリー位置に関して引き出
された情報だけが廃棄される。

ポート情報アレイ902の他の構成素子は、スイッチに
接続されたポート、即ち、INFO〔Ｐ〕.TYPE＝“S"を有
するポートに対してのみ用いられる。

INFO〔Ｐ〕.R_POS934はポートＰ上のネットワーク構
成素子によって最後に報知されたツリー位置である。
「ツリー位置」は、常に、アレイ910内に示される４つ
の値のセットである。

INFO〔Ｐ〕.E_POS936は、ツリー位置がある場合に
は、ポートＰの隣のものが最後にスイッチにエコーし返
したツリー位置である。この説明において、全ての「エ
コー済み」値は他のネットワーク構成要素へ送られた値
であり、これに対してネットワーク構成要素は既に受信
を肯定応答している。

INFO〔Ｐ〕.R_STB938はポートＰの隣のものによって
最後に報知された安定性値である。INFO〔Ｐ〕.E_STB94
0はポートＰの隣のものによって最後にエコーされた安
定性値である。

INFO〔Ｐ〕.R_UID942はポートＰの隣のもののUIDであ
る。

INFO〔Ｐ〕.R_PORT944は、隣のスイッチのポートＰに
接続されたこのスイッチのポートである。

INFO〔Ｐ〕.NEW946は、新しいといわれている情報を
持つメッセージがポートＰの隣のものから受信されてお
り、そしてこのメッセージがまだ肯定応答されていない
ときに、TRUEとなる。

要するに、ポート情報アレイ902は、再構成プロセス
のフェーズ２最中にこのプロセスに参加するためにスイ
ッチＳが必要とする全ての情報を含んでいる。

メッセージデータ構造904は次の素子を含んでいる。
メッセージの各素子は「M.素子」と呼ばれる。また、メ
ッセージデータ構造内の情報は、常に、或る一つのスイ
ッチからこのスイッチの或るポートの隣のものへ送られ
つつあるメッセージに対するものである。

M.EPOCH950はスイッチＳに知られているエポック番号
（即ち、最後の構成バージョン番号）を表す。

M.S._UID952はスイッチＳのUIDである。

M.S._POS956はスイッチＳの現在ツリー位置である
（即ち、CPOSに当しい）。

M.S_STB960はスイッチＳの現在安定性値である（即
ち、CSTBに等しい）。

M.E_POS958は、このメッセージが送られつつあるスイ
ッチによって最後に報知されたツリー位置であり、エコ
ー済みツリー位置と呼ばれる。換言すれば、M.E_POS
は、メッセージが送られつつあるポートに対するR_POS9
32のコピーである。同様に、M.E_STB962は、このメッセ
ージが送られつつあるスイッチによって最後に報知され
た安定性値であり（即ち、メッセージが送られつつある
ポートに対するR_STBに等しい）、エコー済み安定性値
と呼ばれる。

M.NEW964は、メッセージＭ内の情報が「新しい」と、
即ち、新しい情報を含んでいると、考えられるかどうか
を示す。メッセージは、メッセージの目的は前のメッセ
ージの受信を肯定応答するためのみである場合には、新
しい情報を何も含まない。即ち、M.NEWは、M.S._POSがI
NFO〔Ｐ〕.E_POSに等しくないか、またはM.S._STBがINF
O〔Ｐ〕.E_STBに等しくない場合に、真となる。

NETLISTデータ構造906は、スパニングツリーの少なく
ともブランチ内のネットワーク構成要素及びネットワー
ク構成要素相互間接続を表す可変長構造である。NETLIS
Tの各構成素子は「NLST.素子」と表示される。

NLST.COMPLETE970は、スパニングツリーの根が識別さ
れ、そしてネットワーク内の全てのスイッチがその部分
的ネットリストを根まで送ったときにのみ、TRUEとな
る。これは再構成プロセスのフェーズ２の終わりに生ず
る。

NLST.NN972はNETLIST906にリストされるネットワーク
構成要素（即ち、スイッチ及びホスト）の数である。

NLST.NODELIST974はNETLIST906内のネットワーク構成
要素のリストであり、UID値によって分類される。ノー
ドリスト974はNN個の項目976を有す。ノードリスト内の
各項目976は、１つのネットワーク構成要素のUID値、及
び、前に割り当てられている場合に、前記構成要素のSH
ORTIDを含む。

NETLISTの残部はNN個の接続リストである。各接続リ
スト978は、１つのネットワーク構成要素に対し、他の
どのスイッチが第１のネットワーク構成要素のポートの
各々に接続されているかを識別する。新しいNETLISTが
最初にスイッチによって発生されるときに、NETLIST906
に含まれている唯一のスイッチはこのスイッチの直接隣
のものであり、これはポート情報アレイ902によって識
別される。部分的ネットリストが他のスイッチから受信
されると、この部分的ネットリスト内の情報はスイッチ
自体のネットリスト内の情報と併合され、より完全なネ
ットリストを形成する。

本実施例の接続リスト978内にはスイッチのみを表示
してあるが、本発明の他の実施例においてはホストに対
する接続を表示することもできる。そこでホストに関す
る追加情報を用い、ネットワーク内のスイッチ以外の全
てのネットワーク構成要素を含むネットリストを開発す
ることができる。しかし、再構成プロセスの第３フェー
ズについて後で説明するように、スイッチのみしか含ん
でいないネットリストは、スイッチが必要とする経路指
定テーブルを発生するのに十分である。

フェーズ２の詳細な説明 フェーズ２において用いるデータ構造及びルーチンの
疑似表示を本明細書の末尾の付録４〜８に記載してあ
る。なお、第20図を参照されたい。

再構成プロセスのフェーズ１がネットワークの構成に
おける変化を検出すると、この変化を検出したスイッチ
は次のアクションをとる（第20図におけるボックス100
0）。付録６には、再構成を開始するスイッチが従うプ
ロセスの疑似表示を記載してある。第１に、これは、ス
イッチが伝送の過程にある全てのパケットをクリアし、
そして、このスイッチに接続されている全てのホストへ
「ストップフロー」信号を送るようにリンク装置をセッ
トする。伝送の途中に割り込まれたパケットは、再構成
後に再伝送しなければならない。第２に、再構成プログ
ラムは、TYPE情報を除き、そのポート情報アレイ902内
の全ての情報をクリアする。TYPE情報は、このポートが
スイッチまたはホストに接続されているか、またはDEAD
であるかのいずれであるかを示す。TYPE値はスイッチに
よって局所的に発生され、従って、正確であると知られ
る。

再構成プロセスはまたネットリスト906の古いバージ
ョンを消去する。フェーズ２が開始すると、外部情報源
から引き出されたネットワークのトポロジに関する全て
の情報は、不正確となる可能性があるので、廃棄され
る。

次に、再構成プログラムは、スイッチをスパニングツ
リーの根ノードと定義する初期省略時ツリー位置CPOSを
セットアップし、且つ、CSTBを、スイッチが安定でない
ということを示すようにFALSEに等しくセットアップす
る。次いで、このプログラムは、第19図に示すメッセー
ジデータ構造904を用いて、このツリー位置を報知する
初期再構成メッセージをセットアップし、そしてこのメ
ッセージ1002をそのスイッチの全ての隣のものへ送る。

再構成プロセス最中に送られるメッセージはスイッチ
相互間で送られるのみである。ホストコンピュータは再
構成プロセスに参画しない。また、全ての再構成メッセ
ージに対して用いられる「汎用の所定のSCPネットワー
クアドレス」がある。この所定SCPアドレスは、メッセ
ージがどのリンク上で送られても、このリンクの他端に
あるスイッチのSCPへメッセージを経路指定するのに用
いられる。

第20図における破線矢印は一つつのスイッチから他の
スイッチへのメッセージの伝送を示す。即ち、破線矢印
の始まりにおけるプロセスは、この破線矢印の終わりに
おけるプロセスとは異なるスイッチにおいて行なわれ
る。他方、実線矢印は、再構成プロセスの一つの部分か
らこのプロセスの次の部分までのスイッチによる進行を
示す。即ち、実線矢印の両端におけるプロセスは同じス
イッチによって実行される。

スイッチが再構成メッセージを他のスイッチから受け
取ると（ボックス1004）、次のプロセスが行なわれる。
付録７にはこのプロセスの疑似表示を記載してある。

エポック 先ず、受信スイッチは受信したエポック値を試験す
る。M.EPOCHはそれ自体のエポック値を有す。受信した
エポック値がそれ自体のエポック値よりも大きい場合に
は、スイッチは同じ除去処理を行い、次いでこのスイッ
チは再構成プロセスを開始する。次いで、このスイッチ
はこの新しいエポック値をそれ自体のエポック値として
採用し、そして、それ自体をスパニングツリーの根と表
示する初期ツリー位置をセットアップする。

受信したメッセージ内のエポック番号がスイッチ自体
のエポック番号よりも小さい場合には、該スイッチはこ
のメッセージ全体を無視する。

受信した再構成メッセージを処理するためのプロセス
の残部を理解するため、先ず、一つのツリー位置が他の
ものよりも良いかどうかを測定するためのプロセスにつ
いて説明する。

ツリー位置の比較 一のスイッチがそのツリー位置を隣のスイッチに報知
するとき、受信スイッチは、その隣のものによって報知
されたツリー位置がこのスイッチの現在ツリー位置CPOS
よりも「良い」かどうかを決めることが必要である。受
信した位置のほうが良い場合には、受信スイッチは、送
信スイッチをその「親」と識別し、及びメッセージを受
信したポートをその「アップリンク」と識別する。即
ち、比較プロセスは、事実上、受信スイッチが、これが
送信スイッチの「子」であるとしたら、CPOSよりも良い
ツリー位置を獲得するかどうかを決定することである。

受信メッセージにおいて報知されるツリー位置はM.S_
POSと表示される。次いで、受信ツリー位置M.S_POSを処
理する際の第１のステップは「導出ツリー位置」を計算
することであり、この導出ツリー位置は、受信スイッチ
が送信スイッチの子であるとした場合の受信スイッチの
ツリー位置である。導出ツリー位置は次のようにして計
算される。

T.根 ＝M.S_POS.根 T.深さ ＝M.S_POS.深さ＋１ T.親 ＝M.S_UID T.アップリンク＝Ｐ ここに、Ｐはメッセージを受信したポートである。

次のステップは、導出ツリー位置Ｔがスイッチの現在
ツリー位置CPOSよりも良いかまたは悪いかということを
調べることである。２つのツリー位置Ｔ及びCPOSを比較
するための基準は次の通りである。

（１）Ｔにおける根UID（即ち、T.根）がCPOSにおける
根UID（即ち、CPOS.根）よりも小さい場合には、Ｔがよ
り良いツリー位置である。CPOS.根＝T.根である場合に
は、第２の比較試験を用いる。

（２）Ｔの深さ（即ちT.深さ）がCPOSの深さ（即ち、CP
OS.深さ）よりも小さい場合には、Ｔがより良いツリー
位置である。CPOS.深さ＜T.深さである場合には、第３
の比較試験を用いる。

（３）Ｔの親UID（即ち、T.親）がCPOSの親UID（即ち、
CPOS.親）よりも小さい場合には、Ｔがより良いツリー
位置である。CPOS.親がT.親よりも小さい場合には、CPO
Sがより良いツリー位置である。CPOS.親＝T.親である場
合には、最後の比較試験を用いる。

（４）Ｔのアップリンク（即ち、T.アップリンク）がCP
OSのリンク（即ち、CPOS.アップリンク）よりも小さい
場合には、Ｔがより良いツリー位置である。CPOS.アッ
プリンクがT.アップリンクよりも小さい場合には、CPOS
がより良いツリー位置である。CPOS.アップリンク＝T.
アップリンクである場合には、これら２つのツリー位置
は同じ、即ち、等しい。

２つのツリー位置の比較は、本明細書においては、
「より小さい記号」（＜）及び「より大きい記号」
（＞）を用いて示してある。ツリー位置Ｔがツリー位置
CPOSよりも良い場合には、Ｔ＜CPOSとなる。換言すれ
ば、より良いツリー位置はより悪いツリー位置よりも小
さい。

この比較プロセスは自動的に「アップリンク」を選択
し、これは第17図に示すスパニングツリーリンクであ
る。スイッチ相互間に第17図におけるスイッチ726と714
との間の並列リンクのような２つまたはそれ以上の並列
リンクがある場合には、比較プロセスは、最低ポート番
号を持つリンクをアップリンク（即ち、スパニングツリ
ーリンク）として選択する。

他の重要な点は、各スイッチのツリー位置が再構成最
中に単調に改善されるということである。即ち、スイッ
チのツリー位置は、その現在位置よりも良いツリー位置
を採用するのみであるから、決して悪くならない。

メッセージの処理 先ず、受け取られたメッセージを検査し、このメッセ
ージがスイッチに対するALIVEリンク上に受け取られた
ということを確認する。DEADリンク及びホストコンピュ
ータに対するリンクからのメッセージは無視される。次
に、メッセージのエポック番号を検査し、新しいエポッ
クが隣のスイッチによって宣言されているかどうかを調
べる。

次に、送出し側のM.S_POSの報知されたツリー位置が
スイッチによってポートＰ上に報知された最後のツリー
位置よりも悪くないということを確認する。ツリー位置
は単調に改善されるので、より悪いツリー位置M.S_POS
は、隣のスイッチにおける転化されたメッセージまたは
再構成プログラムについての問題を示し、従ってこのメ
ッセージは無視される。同様に、エコー済みツリー位置
M.E_POSは、スイッチによってポートＰ上に最後に報知
されたエコー済みツリー位置INFO〔Ｐ〕.E_POSよりも悪
くなることはない。

次に、メッセージ内の全ての情報をポート情報アレイ
902に設定する。

即ち、 INFO〔Ｐ〕.R_UID＝M.S_UID INFO〔Ｐ〕.R_POS＝M.S_POS INFO〔Ｐ〕.E_POS＝M.E_POS INFO〔Ｐ〕.R_STB＝M.S_STB INFO〔Ｐ〕.E_STB＝M.E_STB INFO〔Ｐ〕.NEW＝M.NEW 次いで、受信スイッチが、報知されたツリー位置から
派生ツリー位置XPOSを発生する。派生ツリー位置を計算
するための前述の説明を参照されたい。XPOSがCPOSより
も良い場合には、XPOSをCPOSの新しい値として採用し、
そしてNEWと呼ばれる内部フラグをTRUEにセットする。
さもない場合には、NEWをFALSEにセットする。NEWは、
スイッチが新しいツリー位置を採用したかどうかを示
す。

安定性の評価 次に、スイッチはこれが「安定」であるかどうかを評
価する。安定性は次のように定義される。即ち、スイッ
チは、（１）スイッチの現在ツリー位置が、スイッチの
隣のものによって最後にエコーされた全ての位置に整合
するとき、及び（２）このスイッチの子である全ての隣
のもの（即ち、このスイッチが彼らの親であるとみなさ
れる）が安定であるときに、安定である。これらの基準
を基礎とし、スイッチが安定であるならばCSTBをTRUEに
セットし、これが安定でないならばFALSEにセットす
る。

以下に更に詳細に説明するように、根スイッチが安定
となると、根のプログラムは再構成プロセスの第２フェ
ーズが行なわれるということを知る。

安定となることを請求するスイッチは、後でこの請求
を取り消すことができる。これが生ずる可能性のあるの
は、安定性請求後に、スイッチが新しいメッセージを受
信することによってそのツリー位置を更新する場合であ
る。スイッチがそのツリー位置を更新すると、該スイッ
チは安定性に対する前の全ての請求を取り消し、そして
新しいメッセージをその全ての隣接スイッチへ送って該
スイッチが安定性を取り消したということを示す。

新しいメッセージの送り出し スイッチがメッセージを受け取ると、このメッセージ
を処理した後、該スイッチは、（１）スイッチのツリー
位置CPOSが変化したか、（２）スイッチの安定性値CSTB
が変化したか、または（３）受信済みメッセージが、新
しい情報といわれるものを含んでおり（M.NEWはTRUEで
あった）、従って肯定応答メッセージを要求する、とい
う場合に、メッセージ送り出しルーチンを実行する。

メッセージ送り出しルーチンは、呼び出されると、ス
イッチの現在ツリー位置（即ち、INFO〔Ｐ〕.E_POS＃CP
OS）を知っていないかまたは肯定応答してない全ての隣
のものへ再構成メッセージ（ボックス1006）を送る。肯
定応答メッセージは、最後のメッセージが送られた以後
に新しい情報を受信した該情報の送り出し元である全て
の隣のものへ送られる（即ち、INFO〔Ｐ〕.NEW＝TRU
E）。また、親INFO〔Ｐ〕.E_STBによってエコーされた
最後の安定性値がスイッチの現在安定性値CSTBに等しく
ない場合、メッセージがスイッチの親へ送られる。

メッセージのフォーマットは常に同じである。

M.EPOCH＝現在EPOCH M.S_UID＝Ｓ M.S_POS＝CPOS M.S_STB＝CSTB M.E_POS＝INFO〔Ｐ〕.R_POS M.E_STB＝INFO〔Ｐ〕.R_STB そして、CPOSまたはCSTBのいずれかが、メッセージが
送られつつあるスイッチからのエコー済み値に整合しな
い場合にはM.NEWがTRUEにセットされる。これらの値を
用い、メッセージＭをポートＰの隣接スイッチへ送る。

メッセージが隣のスイッチヘ送られた後、このスイッ
チに対するINFO〔Ｐ〕.NEW値がFALSEにセットされ、こ
のスイッチからの最後のメッセージが肯定応答されたと
いうことを示す。

次に、特別の「メッセージタイマ」を用い、新しい情
報を持つ全てのメッセージが受信且つ肯定応答されたと
いうことを確認する。これは、メッセージが逸失または
転化されることが時としてあるので、重要であり、この
場合には、メッセージを再度送ることが大切である。本
実施例においては、肯定応答すべきメッセージに対する
通例のターンアラウンドタイムは約１ミリ秒である。こ
のメッセージタイマはソフトウェアタイマであり、通例
のターンアラウンドタイムの２倍の周期、即ち、約２ミ
リ秒の周期を有す。

タイマは、該タイマが既に実行中でないかぎり、新し
い情報を持つメッセージが送られると始動させられる。
次いで、特別のメッセージタイミングルーチンが、前記
タイマが満了するのを待ち、この時点で、このルーチン
は、ここに説明する同じメッセージ送り出しルーチンを
呼び出す。メッセージタイマが既に始動している場合に
は、該タイマは新しい各メッセージで再始動させられな
い。メッセージ送り出しルーチンタイマルーチンによっ
て送り出されるときにメッセージがまだ肯定応答されて
いない場合には、メッセージを再度送り出し、メッセー
ジタイマを再度始動させる。

要約すると、スイッチがメッセージを受け取る度ごと
に、このメッセージがこのスイッチにそのツリー位置ま
たは安定性状態を変化させる場合には、このスイッチは
更新メーセージをその隣のものへ送る。その結果、全て
のスイッチが直接または間接に他の全てのスイッチから
聞くまで、メッセージの連鎖がネットワーク全体にわた
ってスイッチからスイッチへ迅速に送られる。

ネットリストの発生 スイッチ相互間を通過するメッセージが進行するにつ
れ、スイッチのうちの若干はスパニングツリーの最上位
にある位置に到達し、若干はスパニングツリーの最下位
にある位置に到達する。

最大深さを有してスパニングツリーの最下位にあるス
イッチは、安定性を「請求」する最初のものである。新
しい情報が後で受け取られてスイッチがその安定性の請
求を取り消させられる可能性があるので、安定性は「請
求」されるのみであるといわれる。

安定性を請求するための基準については「安定性の評
価」の項において前述した。

スイッチが安定性を請求し、そしてまだこの請求をそ
の親へ送っていないと、これは部分的ネットリストを親
まで送るためのルーチンを呼び出す。前述したように、
スイッチによって発生されたネットリストは、このスイ
ッチに既知となっている全てのスイッチのリストであ
り、スイッチ相互間の既知の全ての接続のリストを含
む。NETLISTデータ構造906についての前述の説明を参照
されたい。

付録８には、ネットリストを処理してスパニングツリ
ーを上下に送るルーチンの疑似コード表示を記載してあ
る。

スイッチが安定性を請求し、そしてネットリストをそ
の親まで送る準備ができると、次のプロセスが用いられ
る（ボックス1008）。先ず、スイッチがツリーの最下位
にある場合、該スイッチはそのポート情報アレイ内の情
報から部分的ネットリストを構築し、そしてこの部分的
ネットリストをその親へ送る。ツリーの最下位にない場
合には、スイッチは受信済みネットリストをそのポート
情報アレイ内の情報に追加し、次いで、その結果のネッ
トリストをその親へ送る。

ネットリストの受信 スイッチがその子のうちの一つからネットリストを受
け取ると（ボックス1010）、該スイッチは次のプロセス
を行なう。このスイッチが既に他の子からネットリスト
を受け取っていた場合には、該スイッチはこの受け取り
済みネットリストを前のネットリストに併合してより完
全なネットリストを作る。このスイッチはまた、ポート
情報アレイ902から知られる全ての新しい情報を追加す
る。

ネットリストを受け取るスイッチが安定でない場合に
は、このルーチンは単に終了し、そして、このネットリ
ストは、スイッチが安定となるまで記憶される。

ネットリストを受け取るスイッチが安定であり、そし
てそのツリー位置がそれ自体を根と識別する場合には、
再構成プロセスのフェーズ２は完了する。その理由は、
安定性の定義が、根を除く全てのスイッチが安定となっ
て、それ自体を根と識別するツリー位置を持つというこ
とを阻止するからである。

再構成フェーズ３ 経路指定テーブルの発生 根スイッチがその子から最後の部分的ネットリストを
受け取って（該スイッチはこれを前に受け取った他の部
分的ネットリストと併合して完全なネットリストを作
る）安定になると、該スイッチはNETLISTデータ構造906
内のCOMPLETEフラグ970をTRUEにセットし、次いで次の
手続きを行なう。

先ず、根スイッチは７ビットのSHORT IDをネットワ
ーク内の全てのスイッチに割り当てる。一般に、このス
イッチは受信済みネットリスト内のSHORT ID値を留保
し、前のエポックからのネットワークアドレスがなお有
効であるように試みる。しかし、スイッチがパワーを失
い、次いで最始動させられて順次続く２つの再構成を生
じさせると、その古いSHORT IDは失われ、そして該ス
イッチ及びこのスイッチに接続されている全てのホスト
は新しいネットワークアドレスを割り当てられる可能性
が生ずる。

ツリー下方のネットリスト送り出し 次いで、前記スイッチは、完全リストを、その全ての
スパニングツリー上でリンクを下方へ、該スイッチが親
となっている相手のスイッチへ送る（即ち、これに対し
て、INFO〔Ｐ〕.R_POS.UPLINK＝INFO〔Ｐ〕.R_PORTとな
る）。第17図に例示のネットワークにおいては、根710
は完全リストをスイッチ712、714、716、718及び720へ
送る。

最後に、根スイッチはスイッチの経路指定テーブルを
計算するためのルーチンを呼び出す（ボックス1014）。
これについては次に詳細に説明する。

親から完全ネットリストを受け取る各スイッチは（ボ
ックス1016）その古いネットリストをこの完全リストで
置き換え、そして、子がある場合には、この完全ネット
リストを子へ再伝送する（ボックス1012）。次いで、前
記スイッチはこのスイッチの経路指定テーブルを計算す
るためのルーチンを呼び出す（1014）。その結果、完全
リストはスパニングツリー全体を下方へ迅速に送られ、
そして全てのスイッチは新しい経路指定テーブルを計算
するためにほぼ同時に働く。

経路指定テーブルの計算 第14図は経路指定テーブル422の構造を示すものであ
る。付録９に、経路指定テーブル内のリンクベクトルを
計算するためのプロセスの疑似コード表示を記載する。

先ず、経路指定テーブル全体内の全てのエントリを違
法ネットワークアドレスに対する値にリセットする。即
ち同報通信ビットを「１」に等しくセットし、全てのリ
ンクマスクビットを「０」に等しくセットする。またス
イッチのSCPへ送られつつある再構成メッセージに対応
するエントリを、これらメッセージをSCPへ経路指定す
るようにセットアップする。再構成メッセージを隣接ス
イッチ間に送るための単一の所定アドレスがある。この
アドレスに対する（即ち、全てのALIVE入力リンクに対
する）リンクベクトルは単一マスクビットを有し、これ
はSCPに対するポートに対応し、「１」にセットされ
る。

経路指定テーブルメモリ422のリセットは、処理最中
の全てのホストパケットをスイッチから追い出すよう
に、再構成の第２フェーズの始まりに事実上行なわれ、
そして再構成メッセージが受信されたということを確認
する。

再構成の第３フェーズ中に、新しい経路指定テーブル
がSCPの正規メモリ内に発生される。この新しい経路指
定テーブルが完成すると、これは経路指定テーブルメモ
リ422内にコピーされる。経路指定テーブルを計算する
ための開始点はフェーズ２の始まりに発生されるリセッ
ト経路指定テーブルである。

経路指定テーブルのリンクベクトルを計算するとき、
次のプロセスが、このプロセスを実行しつつあるスイッ
チに対する生きている各入力リンクに対して繰り返され
る。即ち、完全ネットリストにおいて定義される各ネッ
トワークアドレスに対し、４ビット入力リンク番号と11
ビット・ネットワークアドレスとの連結によって定義さ
れるアドレスにおいてリンクベクトルが発生される。生
きている出力ポートに対応するリンクベクトル内の各マ
スクビットは、（１）アップ／ダウン経路指定規則に違
反することなしに出力リンクを介して特定ネットワーク
アドレスに到達することが可能な場合、及び（２）ポー
トを通る通路が、この特定ネットワークアドレスへ至る
最短経路よりも長くない場合に、「１」にセットされ
る。

このネットリストを用い、経路指定ルーチンは各リン
クがアップリンクであるかまたはダウンリンクであるか
を決定する。入力リンクがアップリンクである場合には
（これは、受信されたパケットがツリーを下方へ走行し
つつあることを意味する）、このリンクは、ダウンリン
クに対してのみイネーブルされたマスクビットを持つこ
とができる。

経路指定テーブルの計算は、先ず、スイッチ間でメッ
セージを送るための「サブネット」経路指定テーブルを
計算し、次いで、このサブネットを拡大して経路指定テ
ーブル全体を満たすことによって行われる。付録９を参
照されたい。

他の実施例においては、特定ネットワークアドレスへ
至る許容された通路は、同じスイッチからの最短通路よ
りも長いＮ個のリンクまでの通路を含む。ここにＮは特
定の整数である。他の実施例においては、他の基準を用
いて過度に長い通路を除去することができる。

次に、同報通信パケット及び再構成メッセージパケッ
トに対するリンクベクトルを経路指定テーブルに追加す
る。本実施例においては、単一の所定の11ビット・ネッ
トワークアドレスを全ての同報通信パケットに対して用
いてあるが、他の実施例においては（例えば、ネットワ
ーク内のホストの所定サブネットに対する部分的同報通
信に対しては）、複数のアドレスを用いることができ
る。

同報通信パケットに対しては、根スイッチに対し、他
のスイッチに対するとは異なるプロセスが用いられる。
根以外の全てのスイッチに対し、同報通信パケットはス
パニングツリーを上下両方向に走行することができ、走
行の方向は、パケットが受け取られる入力リンクによっ
て定まる。同報通信パケットがダウンリンク上に受け取
られると、該パケットはスパニングツリーを根へ向かっ
て上方へ走行する。同報通信パケットがアップリンク上
に受け取られると、該パケットはスパニングツリーを下
方へ走行する。即ち、入力ダウンリンクに対しては、リ
ンクベクトル内の「１」にセットされるマスクビットの
みがスイッチのその親に対するアップリンクである。入
力アップリンクに対しては、ベクトル内の「１」にセッ
トされるマスクビットが、そのスイッチに接続される全
てのスパニングツリーダウンリンクに対するものであ
る。

根ノードに対しては、同報通信パケットはダウンリン
クからのみ受け取られ、そして全ての根のスパニングツ
リー上をリンクを下方へ再伝送される。従って、全ての
入力ダウンリンクに対しては、リンクベクトル内の
「１」にセットされるマスクビットが、そのスイッチに
接続される全てのスパニングツリーダウンリンクに対す
るものである。

経路指定テーブルの計算完了後、この完成テーブルは
経路指定テーブルメモリ422内にコピーされる。この時
点で、このスイッチは「ビジネスのために開いて」い
る。即ち、データパケットは、排除されないで、経路指
定テーブルに従って送られるようになるからである。

本実施例におけるネットリストはネットワーク内のス
イッチ位置を定義するのみである。従って、他のスイッ
チに対応するネットワークアドレスに対するリンクベク
トルを発生するとき、前記他のスイッチに対する全数12
の経路指定テーブルエントリは同じ値で満たされること
になる。他方、経路指定テーブルを含んでいるスイッチ
に対応するネットワークアドレスに対するリンクベクト
ルを発生するとき、ポート情報アレイは、どのポートが
ALIVEであるか、及びどれがDEADであるかを特定する。D
EADポートに対する経路指定テーブルエントリは全てゼ
ロにセットされ、これにより、このアドレスへ送られる
全てのパケットは消去またはドロップされることにな
る。

これは、無効ネットワークアドレスを持つパケットは
スイッチへ送られ、これはDEADポートへアドレス指定さ
れているので、これが到達すると、メッセージを消去さ
せるのみになるという可能性がある、ということを意味
する。経路指定テーブルエントリをセットすることに
は、かかるパケットの伝送を全て阻止するという或る小
さな利点があるが、不法アドレスを持つのは極めて少数
のパケットしかないこと、及びかかるパケットを少数の
スイッチを通して伝送することによって生ずる害はない
ということが考えられる。ネットワーク内の全てのDEAD
リンクを考慮する経路指定テーブルを発生するには、ネ
ットリストは、ネットワーク内のホストコンピュータへ
の全ての接続、及びスイッチ相互間接続についての情報
を持つことが必要である。

自滅協定 エポック番号があふれる（即ち、2⁶⁴の値に到達す
る）時及び場合に、「次の」エポック値（即ち、エポッ
ク＝０またはエポック＝１）を持つメッセージは前のエ
ポックよりも小さいエポック値を持つので、若干の問題
がある。この問題を解決するには、全てのスイッチはエ
ポック値を所定の開始値（例えば、０または１）にリセ
ットすることが必要である。これを行なうため、スイッ
チがそのエポック番号を増してこの番号のあふれを検出
するとき、害スイッチは特別の再構成メッセージを全て
その隣接スイッチへ送り、これらスイッチにそれらのエ
ポック値をリセットすることを要求する。このメッセー
ジは、「自滅協定」と呼ばれ、次いで、全てのスイッチ
がメッセージを受け取るまで、これらスイッチにより、
これらの全ての隣のものへ送られる。この「自滅協定」
メッセージを受け取り及び再伝送した後、全てのスイッ
チは所定の時間（例えば、５秒間）待ち、その後、標準
の再構成プロセスを開始する。その結果、エポック機構
は全ての状態においてその保全を保有する。

多重ネットワーク変化 第２のネットワーク構成部材が再構成の最中に変化す
る場合、次のことが生ずる。この変化を検出するスイッ
チが、第１の変化を既に知っており、そして再構成プロ
グラムを実行しつつあった場合には、このスイッチは、
そのエポック番号をインクリメントし、且つ再構成プロ
セスのフェーズ２を再度開始することにより、「新しい
エポックを宣言する」。即ち、このスイッチは新しい再
構成メッセージをその隣のものへ送り、このエポックに
ついて報知する。この新しいより高いエポック番号はよ
り小さいエポック番号に打ち勝ち、そして再構成プロセ
スは前述のように進行する。

第２の変化を検出するスイッチが第１の変化について
まだ知っていなかった場合、該スイッチは、他のスイッ
チによって使用されているのと同じ新しいエポック番号
で再構成プロセスを独立に開始する。２つのセットの再
構成メッセージはネットワーク内の或る点において合流
し、そこで再構成プロセスは正規の仕方で進行する。

以上から解るように、短時間内に生ずるどんな数のネ
ットワーク変化も、第１の変化によって開始された再構
成プロセス内に編入される。

〔発明の効果〕

要約すると、本発明の再構成手続きは極めて早く、そ
して従来なかった次のような特性を有す。即ち、ネット
ワーク内には、再構成プロセスが何時完了するかを知っ
ているスイッチがあり、及びこのスイッチは他の全ての
スイッチに知らせる。その結果、ネットワーク内の全て
のスイッチは再構成プロセスが何時完了するかを知る。
本発明の実施例においては、再構成のための最長時間は
200ミリ秒以下であると考えられ、これは、このシステ
ムの利用者に不利を与えることのない十分に短い時間で
あると考えられる。

以上、本発明をその実施例について説明したが、これ
は本発明を例示するものであり、本発明は前記実施例に
限定されるものではない。当業者に解るように、本発明
においては、特許請求の範囲に記載のごとき本発明の精
神及び範囲を逸脱することなしに種々の変形を行なうこ
とができる。

【図面の簡単な説明】

第1A図は従来の線形ローカルエリアネットワークのブロ
ック線図、第1B図は従来のリング形ローカルエリアネッ
トワークのブロック線図、第２図は本発明の小型のメッ
シュ接続式ロカールエリアネットワークのブロック線
図、第３図は本発明のローカルエリアネットワークの一
つのセクションの詳細なブロック線図、第４図はメッシ
ュ接続式LANにおけるデッドロックの例を示す説明図、
第５図はメッシュ接続式LANにおけるアップリンク及び
ダウンリンクの概念図、第６図はデータパケット及び対
応のフロー制御信号の伝送を示すタイミング線図、愛７
図は一つのホストコンピュータに対するネットワーク制
御器のブロック線図、第８図は本発明実施例において用
いられるスイッチのブロック線図、第９図は本発明実施
例において用いられるクロスバースイッチのブロック線
図、第10図は互いに接続されたネットワーク構成要素の
チェインに対するデータフロー制御回路のブロック線
図、第11図はスイッチ内の互いに接続された２つのリン
ク装置のブロック線図、第12図はリンク装置の詳細なブ
ロック線図、第13図は第８図のスイッチにおいて用いら
れるルータのブロック線図、第14図はネットワークアド
レスをルックアップアドレスの一部として用いて経路指
定テーブルからリンクベクトルを選択するプロセスを説
明するための略図、第15図は第13図におけるルータの経
路選択機構のブロック線図、第16図は第13図のルータに
対するタイミング線図、第17図はメッシュ式ネットワー
クをスパニングツリーとして示す図、第18図はネットワ
ーク再構成プロセスの第１フェーズの流れ図、第19図は
ネットワーク再構成プロセスの第２及び第３のフェーズ
中に用いられる主データ構造を示す図、第20図はネット
ワーク再構成プロセスの第２及び第３のフェーズの流れ
図である。 120,132〜138:ホスト 122:ネットワーク制御器 124,126,140,142:スイッチ 128,130,144,146:リンク 210:非ブロック化スイッチ 212:クロスバースイッチ 216:スイッチ制御プロセッサ 218:経路指定回路 308,330:入力リンク装置 322,326:出力リンク装置 350:TAXI受信器チップ

フロントページの続き (72)発明者 レスリー ビー ランポート アメリカ合衆国 カリフォルニア州 94303 パロ アルト エルシノア ドラ イヴ 941 (72)発明者 トーマス エル ローデヘッファー アメリカ合衆国 カリフォルニア州 94040 マウンテン ヴィュー 231 デル メディオ アベニュー 141 (72)発明者 ケイ マニ シャンディー アメリカ合衆国 カリフォルニア州 91106 パサディナ アーデン ロード 1203

Claims (2)

【特許請求の範囲】
1. 【請求項１】複数のホストを相互接続するためのメッシ
   ュ接続式ローカルエリアネットワークであり、このロー
   カルエリアネットワークが、 ネットワークのホスト（120、132、134、136、138）間
   で複数のデータパケットを同時に配送する複数のスイッ
   チ手段（124、126、140、142、210）であり、前記ホス
   ト及び前記スイッチ手段が共にネットワーク部分を構成
   している、前記スイッチ手段、及び 前記ネットワーク内の前記スイッチ手段及び前記ホスト
   を相互接続するための複数の二点間リンク手段（128）
   であり、各二点間リンク手段（128）が２つの前記ネッ
   トワーク部分間での通信チャンネルを与え、前記複数の
   リンク手段がスパニングツリーリンク及び複数の追加リ
   ンクを含んでいる、前記二点間リンク手段を有し、 前記相互接続された複数のスイッチ手段及び前記スパニ
   ングツリーリンクが共にスパニングツリーを形成してお
   り、このスパニングツリーにおいて、前記スイッチ手段
   の一つが前記スパニングツリーの根に当てられ、 各スイッチ手段が前記スパニングツリー内の前記スイッ
   チの位置をきめるための再構成手段（900）を含み、こ
   の再構成手段が、 前記スパニングツリー内のツリー位置を示す位置指示手
   段（910）、 前記ツリー位置が安定であるか否かを示す安定性値を示
   す安定性指示手段（922）、 前記位置指示手段（910）に結合され、前記ツリー位置
   及び前記安全性値を含む構成メッセージ（1006）を前記
   スイッチ手段に隣接する各スイッチ手段に送るメッセー
   ジ送り手段（1000、1004）、及び 構成メッセージを隣接スイッチ手段から受け、各受信さ
   れた構成メッセージに於けるツリー位置の関数に従って
   導出されたツリー位置を発生し、そして前記位置指示手
   段によって指示されるツリー位置を、前記導出されたツ
   リー位置が前記位置指示手段によって示されるツリー位
   置よりも良い場合、前記導出されたツリー位置に置き換
   えるメッセージ受信手段（1004）を含み、 前記メッセージ送り手段が、前記位置指示手段によって
   示される前記ツリー位置が前記導出されたツリー位置に
   よって置き換えられる時、前記隣接するスイッチ手段に
   構成メッセージを送る手段を含み、 前記再構成手段（900）が、前記メッセージ受信手段及
   び前記安全性指示手段に結合した安定性評価手段（100
   4）を含み、この手段は、前記スイッチ手段が少なくと
   も一つの構成メッセージを各隣接するスイッチ手段へ送
   り且つこれから少なくとも一つの構成メッセージを受信
   した時に、前記ツリー位置が安定であることを示す前記
   安定性値を設定して、（１）前記隣接スイッチ手段の各
   々から受信された最後の構成メッセージが、前記位置指
   示手段によって指示される前記ツリー位置よりも良いツ
   リー位置を含むこと、又は（２）前記隣接するスイッチ
   手段の少なくとも１つから受信される最後の構成メッセ
   ージが前記位置指示手段によって指示される前記ツリー
   位置よりも悪いツリー位置を含み、悪いツリー位置を有
   する各隣接スイッチ手段から受信される最後の構成メッ
   セージ内のスイッチ安定性値が、前記隣接するスイッチ
   手段に対する安定ツリー位置を示していることを示し、 前記再構成手段（900）が、完了検出手段（1010）を含
   み、この手段は、前記ツリー位置が、前記スイッチ手段
   が前記スパニングツリーの根であることを示し、且つ前
   記安定性指示手段が、前記ツリー位置が安定であること
   を示している時を決める手段であり、且つ再構成完了メ
   ッセージを、前記隣接するスイッチ手段に送り、前記ス
   イッチ手段の全てが安定であることを示し、 前記ネットワークに於ける前記スイッチ手段が、前記ス
   パニングツリー内の相対的ツリー位置を決め、且つこれ
   らのツリー位置を決める工程が完了した時を決めること
   を特徴とする前記メッシュ接続式ローカルエリアネット
   ワーク。
2. 【請求項２】複数のホストを相互接続するためのメッシ
   ュ接続式ローカルエリアネットワークであり、このロー
   カルエリアネットワークが、 ネットワークのホスト（120、132、134、136、138）間
   で複数のデータパケットを同時に配送する複数のスイッ
   チ手段（124、126、140、142、210）であり、前記ホス
   ト及び前記スイッチ手段が共にネットワーク部分を構成
   している、前記スイッチ手段、及び 前記ネットワーク内の前記スイッチ手段及び前記ホスト
   を相互接続するための複数の二点間リンク手段（128）
   であり、各二点間リンク手段（128）が２つの前記ネッ
   トワーク部分間での通信チャンネルを与え、前記複数の
   リンク手段がスパニングツリーリンク及び複数の追加リ
   ンクを含んでいる、前記二点間リンク手段を有し、 前記相互接続された複数のスイッチ手段及び前記スパニ
   ングツリーリンクが共にスパニングツリーを形成してお
   り、このスパニングツリーにおいて、前記スイッチ手段
   の一つが前記スパニングツリーの根に当てられ、 各スイッチ手段が前記スパニングツリー内の前記スイッ
   チの位置をきめるための再構成手段（800、900）を含
   み、この再構成手段が、 前記スパニングツリー内のツリー位置を示す位置指示手
   段（910）、 前記ツリー位置が安定であるか否かを示す安定性値を示
   す安定性指示手段（922）、 前記スイッチ手段と前記ネットワーク部分の他のものの
   間の新たな接続の存在を検出し、且つ前記スイッチ手段
   と前記ネットワーク部分の他のものとの間の接続の破壊
   を検出するための手段（802、804）を含む、前記ネット
   ワークの構成の変化を検出するための構成変化検出手段
   （800）、 前記ネットワークの構成の変化が前記構成変化検出手段
   によって検出される時、前記スイッチ手段に隣接するス
   イッチ手段に再構成開始メッセージを送る、前記構成変
   化検出手段に結合された、再構成開始手段（1000）、及
   び 前記位置指示手段に結合しており、（Ａ）前記スイッチ
   手段に隣接するスイッチ手段間での構成メッセージの送
   受を行い、且つ（Ｂ）前記受信された構成メッセージか
   ら導かれたツリー位置を前記位置指示手段内に記憶する
   手段を含み、前記構成メッセージの各々が前記ツリー位
   置及び前記安定性値を含んでいる再構成計算手段（100
   4、1008、1010、1012、1014、1016）、を含み、 前記スイッチ手段が、少なくとも一つの構成メッセージ
   を各隣接するスイッチ手段へ送り且つこれからから少な
   くとも一つの構成メッセージを受信した時に、前記ツリ
   ー位置が安定であることを示す前記安定性値を設定し
   て、（１）前記隣接するスイッチ手段の各々から受信さ
   れた最後の構成メッセージが、前記位置指示手段によっ
   て指示される前記ツリー位置よりも良いツリー位置を含
   むこと、又は（２）前記隣接するスイッチ手段の少なく
   とも一つから受信された最後の構成メッセージが前記位
   置指示手段によって指示されるツリー位置よりも悪いツ
   リー位置を含み、悪いツリー位置を有する各隣接スイッ
   チ手段から受信される最後の構成メッセージ内のスイッ
   チの安定性値が、前記隣接するスイッチ手段に対する安
   定なツリー位置を示していることを示す安定性評価手段
   （1004）を含み、 前記再構成手段（800、900）が、完了検出手段（1010）
   を含み、この手段は、前記ツリー位置が、前記スイッチ
   手段が前記スパニングツリーの根であることを示し、且
   つ前記安定性指示手段が前記ツリー位置が安定であるこ
   とを示している時を決める手段であり、且つ再構成完了
   メッセージを前記隣接するスイッチ手段に送り、前記ス
   イッチ手段の全てが安定であることを示し、 前記複数のスイッチ手段が、前記スパニングツリー内の
   全ての前記スイッチ手段のツリー位置を指示するネット
   ワーク構成データを、前記スイッチ手段の全てに送信す
   るための手段（1012）を含み、 各スイッチ手段が、前記ネットワーク構成データ及び所
   定の経路選択基準に従って、特定のネットワーク部分
   へ、受信されたデータパケットの経路を指定するための
   経路選択手段（214、408）を含み、 ネットワークの構成の変化が、前記ネットワーク内のス
   イッチ手段に自動的に、前記スパニングツリー内のツリ
   ー位置を再度決めさせることを特徴とする前記メッシュ
   接続式ローカルエリアネットワーク。