JPH0332252A - 高速メッシュ接続式ローカルエリアネットワーク - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

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

〔従来の技術〕

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

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

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

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

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

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

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

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

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

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

メッシュ接続式ＬＡＮを使用することの主な利点は多数
の並列通信路が使用可能となるというこ２ とである。これにより、ネットワークホストの相異なる
対間のメッセージの同時伝送が可能となる。

即ち、メッシュ接続式ネットワークは、ネットワークの
スルーブツトがネットワークのリンクのスループソト制
限によって制限されるということがないので、類似の線
形またはリング形のネットワークよりも遥かに高い帯域
幅を得ることができる。

リング形ＬＡＮに対するメッシュ接続式ネットワークの
他の利点は、メッシュ式ネットワークの待ち時間が比較
的低くなるということである。待ち時間は、メッセージ
パケットを受信及び再伝送しなければならないノードの
数にほぼ比例する。

良好に設計されたメッシュ式ＬＡＮにおいては、同様数
のホストを有するリング形ＬＡＮに比べ、ホストのうち
の選択された全ての対間のノードの数が比較的少なくな
る。

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

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

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

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

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

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

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

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

単一のダウンリンクであるにしても、メッセージパケッ
トがダウン方向に経路指定された後に通過させられるリ
ンクはない。

多数のデータパケットをネットワークを通して同時に経
路指定することにより、高い集合体帯域幅が得られる。

一部は、パケットの再伝送（即ち、前送り）をこれらパ
ケットの終わりの受信よりも６ 十分に前に開始するスイッチを設けることにより、低い
待ち時間が得られる。これはカソトスルースイッチング
として知られている。。

パケツトバッファリング機構により、ノードの枯渇が防
止され、同報通信メッセージの経路指定が可能になる。

また、本発明におけるフロー制御及びデータバッファリ
ングにより、相隣るスイッチ間の全ての不整合が補償さ
れる。

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

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

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

〔実施例〕

第２図は本発明にかかるメツシュ接続式ローカルエリア
ネットワークの概念を示すものである。

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

８ 第２図において、このネットワークを用いるホストコン
ピュータを記号Ｈで示してあり、このローカルエリアネ
ットワーク（ＬＡＮ）を構成するノードをスイッチと呼
び、記号Ｓで示しである。

この概念図においては、１６個のスイッチを用いて約８
０個のホストを相互接続している。スイッチＳはマルチ
ポート形のカットスルー非ブロック化スイッチであり、
複数の受信リンクを選択された種々の発信リンクに同時
に接続することができる。これらスイッチにより、数多
くのデータパケツトをネットワークを通して同時に経路
指定することができる。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ネットワークの「根」、「根ノート」または「根スイッ
チ」は、ネットワークのスパニングツリーーの根として
指定されるスイッチＳである。

根ノードは、ネットワークの再構成中に、また、同報通
信メッセージ、即ち、ネットワーク内の全てのホストへ
送られるメッセージを再伝送するために、いくつかの特
別の応答性を持つ。

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

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

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

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

数多くのデータパケットをネットワークを通して同時に
伝送することができる。−例を挙げると、第１のパケッ
トをホスト１３２からホスト１３４へ送りながら第２の
パケットをホスト１３６からホスト１３８へ送る。第３
図に示す経路Ｐｌは、２つのリンクで接続された３つの
リンクを具備しており、これを用いて第１のパケットを
ホスト１３２からホスト１３４へ送ることができる。第
６ ３図に示す経路Ｐ２を同時に用いて第２のパケットをホ
スｌ−１３６からホス１〜１３８へ送ることができる。

本例においては、両方のデータパケツトをスイッチ１４
０を通じて同時に送る。これが可能であるのは、本発明
において用いるスイッチがマルチポート形非ブロック化
スイッチであるからである。各スイッチは、複数の受信
リンクを別々の発振リンクに同時に接続することのでき
るクロスバ−回路を有している。

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

デッドロック 本発明の一つの特徴として、「デッドロック」の影響を
受けることのないメッシュ接続式ネットワークが提供さ
れる。ネットワークにおけるデッドロックは、トラフィ
ソク交叉部におけるグリソ７ ドロソクに類似の電子回路と考えることができる。

第４図に、４つのホストコンピュータＡ、Ｂ、Ｃ及びＤ
並びに４つのスイッチＳを示ず。各ホストは、データパ
ケット１４８を、２つのスイッチでこの送信ホストから
分離されている他のホストへ送ろうとする。各パケット
の宛先は、このパケットを表す枠１４８内の記号で示さ
れている。例えば、ホストＡによって送られるパケット
１４８はホストＣの宛先を有す。

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

当業者は解るように、デッドロックはまた小さいデータ
パケツトについても生ずる可能性がある。

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

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

アップ／ダウン経路指定 木発門は、メッセージを互いにデッドロックすることの
ないように自動的に経路指定するという新ししい型式の
経路指定手続きを用いることによ９ す、デッドロックを完全に回正するものである。

再び第４図について説明すると、図示のデータ通路は、
データパケットが４つのスイッチを通る７ｑ４端ループ
内に送られるという「サイクル」が生ずることが、少な
くとも理論的には可能であるということを含意している
。サイクルは、それ自体は、通例は問題とならないが、
サイクルを形成するデータ通路の可用性は、デソトロノ
クの被害を受↓ノる可能性のあるメッシュ式ネノトワー
クの兆候である。

第５図に、スイ・フチＳ１からスイッチ３１０へ至る１
０ノードネソＩ−ワークの若干複雑な例を示す。スイッ
チ開の全ての線路は双方向性リンクを示している。

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

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

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

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

次に、スイッチＳ１、Ｓ３、Ｓ５及びＳＩＯがある第５
図の左下部分を用い、何故にデソド’＋：Ｉノ２ りがアップ／ダウン経路指定機構を用いて不可能である
かを示す。第４図から第５図内のこれらスイッチ上への
データｉＪＴ回路を用いようとすると、第４図内の全て
のデータ通路は、１つのデータ通路を除き、合法的であ
るということが解る。即ち、スイッチＳ３．３５次いで
ＳＩＯを通ってホストＢからホストＤへ至るデータ通路
は合法的でない。

その理由は、Ｓ３から３５へ至る通路はダウンチャネル
であり、Ｓ５からＳＩＯへ至る通路はアップチャネルで
あるからである。これは、アップチャネルはダウンチャ
ネルの後で使用できないという規則に反する。その解決
法としては、ホストＢからホストＤへ至るメノセージを
先ずＳ３からＳｌへ進まセ（これはアップチャネルであ
る〉、次いで、ＳｌからＳＩＯへ進ませる（これはダウ
ンチャネルである）。

このネットワークにおけるスイッチ開の各リンクの指向
性は次のようにして決定される。全てのスイッチ（及び
ホストコンピュータ）は、ＵＩＤと呼ばれる一意的４８
ビソト識別子を永久的に割３ り当てられている。かかるＵＩＤはエサーネソ１−にお
いて用いられ、ネノトｌノークの全ての構成要素を一意
的に識別する。後で説明するように、不ソＩ〜ワーク内
の全てのスイッチは７ビソｌ−５ＩＩＯ１？ＴＩＤを割
り当てられ、全てのホストコンピュータは１１ヒ・７ト
・ネットワークアドレスを害りり当てられている。

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

第５図において、各スイッチはその基準数に等しいＵＩ
Ｄを割り当てられているものとする。即ち、Ｓｌはｌの
ＵＩＤを害りり当てられ、Ｓ２は２のＵＩＤを割り当て
られ、以下同様になっている。

即ち、スイッチ３１は根であり、スイッチＳ２、Ｓ３、
Ｓ９及びＳＩＯからＳｌへ至るリンクはスイッチＳ１へ
向かって上方へ方向づけされる。

４ 第２の規則は、スイッチはスイッチと根との間のリンク
の最小数に基づく不ソトワークレヘルを割り当てられる
ということ、及び異なるネノトヮークレヘルにあるスイ
ッチ開のリンクは低い方のネットワークレヘルヘ向かっ
て上方へ方向づけされるということである。例えば、ス
イッチＳ３ばネノトワークレヘル１にあり、スイッチＳ
８はネットワークレ・＼ル２にあり、従って、Ｓ８から
Ｓ３まてのリンク↓上Ｓ３−＼）ｉｉＪかって」ニガへ
方向づけされる。

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

ネットワークを通る合法的経路についての他の例は次の
通りである。即ち、バゲノトをホス＋−Ｃからホスｉ　
Ｅへ送り、このパケットは通路Ｐ３ま５ たばＰ４を通って進むことができる。スイッチＳ５、Ｓ
３、Ｓ８及びＳ９を通って進むｉＪｌ路Ｉ）３は、アッ
プチャネルに従い、次いでダウンチャネルに従うから、
合法的である。スイッチＳ５．３７次いでＳ８を通って
進む通路Ｐ４は、２つのダウンチャネルに従うから、合
法的である。

通ｉＰ４は通路Ｐ３よりも短いが、Ｐ４の最初のリンク
が阻止されておって通路Ｐ３内の最初のリンクが可用で
ある場合にばＰ３の方が好ましくなる。即ち、ネットワ
ークを通るこの好ましい通路は、どのリンクが他のデー
タバゲノ１〜によって既に使用されているかに４衣存す
るのであり、そしてこの好ましい通路は必ずしも最短の
合法的通路であるとばト艮らない。

ホストＦからホストＧへ送られるパケットに対する非合
法経路の例としては、スイッチＳ７から３６へ至り　（
ダウンリンク）、その後に３６から３８へ至るもの（ア
ップリンク）が続くとい・うものがある。この経路は、
ダウンリンク　（３７から３６へ）の後にアノプリンク
　（Ｓ６から３８へ）６ を有しており、これは許されないので、非合法である。

ＦからＧまでの合法的経路は、Ｓ７から３５へ（アップ
）、Ｓ５から３３へ（アップ）及びＳ３から３８へ（ダ
ウン）進む。

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

パケットフロー制御 本発明実施例の多くの特徴を理解するため、どのように
して「フロー制御」が働くかということを理解するが先
ず必要である。第３図を参照し、ホスト１３２からホス
ト１３４へ送られつつある１６．０００バイト・パケッ
トの例を考えてみる。

この例に対し、各スイッチポートは、受信データパケッ
トの一部を一時的に記憶するための４にハイｌ−Ｆ　Ｉ
　Ｆ　Ｏバッファを有しているものとする。

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

本実施例においては、データは、ボスト１３２とスイッ
チ１４２との間のリンク１４６のような全てのリンク上
で両方向に連続的に送られる。送信すべきデータがない
場合には、同期パイ１〜が送られる。同期ハイ１−は単
なる空データである。

データが伝送されるのと同時に、フローコマンド信号も
単純型式の時多重化によって送られる。

即ち、伝送される２５６番目ごとのハイドがフロー制御
コマンドである。フローコマンドの伝送はパケット境界
と同期しない。即ち、フローコマンドは、リンクがどの
ようなデータを運んでいるかとは関係なしに、２５６ハ
イトザイクルごとに１回、リンク上にある。即ち、７０
０ハイド・メソ８ セージがリンク上で送られている場合には、このメッセ
ージを表すデータストリームは次のように見える。即ち
、メッセージの最初の２００バイトの後に１ハイド・フ
ローコマンドが続き、その後にメッセージの次の２５５
ハイドが続き、その後に第２の１ハイド・フローコマン
ドが続き、次いでメッセージの残りの２４５バイトが続
く。パケットの終わりの後に１０同期ハイドが続き、次
いで他のフローコマンドが続く。

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

９ 本実施例においては、スイッチ内で用いられる９ビソト
・データ／コマンド値がコード化され、標準のＴＡＸＩ
送信器及び受信器アップ（アドバンスト・マイクロ・デ
パ′イシーズ（ＡｄｖａｎｃｅｄＭｉｃｒｏ　Ｄｅｖｉ
ｃｅｓ　）社製のＡｍ７９６８型及びＡｍ７０６９型集
積回路）によって直列に伝送される。

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

第６図は、ホスト１３２によってリンク１４６上で送信
（ＴＸ）及び受信（ＲＸ）されつつある信号を示すもの
である。前述したように、ネットワーク構成要素相互間
の各リンクは、事実上は、互いに反対方向にデータを同
時に運ぶ２つの通信チャネルである。それで、第６図に
２つのデータストリームを示しである。例えば、第３図
を参照して説明すると、これらデータストリームはホス
ト１３２とスイッチ１４２との間のデータストリームで
ある。本例において、ホスＬ　１３２によっ０ て送信される′ＦＸデータストリームはがなり長いメッ
セージパケットを含んでおり、その始まり及び終わりを
「Ｉ３」ハイド及びｒＥＪハイドで示しである。ｒＢＪ
バイトはそれぞれのパケットに先行する「ビギンパケッ
トコマンド”Ｊ　　（ｂｅＢｉｎｐａｃｋｅｔ　ｃｏｍ
ｍａｎｄ）を示し、「Ｅ」ハイドはそれぞれのパケット
の後に続く「エンドパケットコマンドＪ　　（ｅｎｄ　
ｐａｃｋｅｔ　ｃｏｍｍａｎｄ）を示す。

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

スイッチ１４２によってホスト１３２へ送られるＲＸデ
ークスＩ・リームは、ホスト１３２によって送られつつ
あるパケットの流れを制御するためのフロ−１ｉ１Ｊ御
信号Ｓ（開始のための）及びＸ（停止のための）を含ん
でいる。スイッチ１４２によって送られるストソプコマ
ンドはホストによって送られつつあるパケットの流れを
一時的に停止させ、スイッチ１４２によって送られるス
タートコ■ マントはホスト１３２にパケットの送信を再開させる。

スイッチ１４２によって送られるＲＸテークストリーム
はまた、パケットの如まり及び終わりにおいてｒＢＪバ
イト及びｒＥＪハイドで示されるような小さいデータパ
ケットを有す。

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

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

ホストａ制御器１２２ば、ホスト制御器１２２が「スト
ップフロー」コマンドを送り出すことはないという点を
除き、スイッチと同しフロー制御機構を使用する。即ち
、ホスト制御器は、スイッチに、該スイッチが接続され
る（即ち、２５６番目のハイドごとに）という「スター
トフロー」制御信号を常に送り出す。その−例を第６図
に示してあり、］゛ＸデＸデークスＩムは「スタートフ
ロー」３ 制御信号１５６．１５８及び１６０を有している。

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

第７図に、１つのホストコンピュータ１２０に対するネ
ットワーク制御器１２２のブロック線図を示す。機能的
には、ネットワーク制御器１２２はホストコンピュータ
をネットワークに接続するためのホストコンピュータ上
のポートである。この制御器は「Ｑ２２−ハス制御プロ
トコル」として知られているものを採用しており、Ｑハ
ス制御回路１６１を用いてホストコンピュータを制御器
１２２に接続する。Ｑ２２−ハスプロトコルの説明は、
ディジタル・エキソプメント社（１）ｉｇｉｔａｌｌＥ
ｑｕｉｐｍｅｎｔ　Ｃｏｒｐｏｒａｔｉｏｎ　）発行（
１９８５年）の「マイクロシステムズ・ハンドブック」
（Ｍｉｃｒ。

ｓｙｓｔｅｍｓ　Ｈａｎｄｂｏｏｋ）　、付録Ａに記載
されている。

４ 他のコンピュータハスを用いるホストコンピュータに対
しては、異なるハスインタフェース回路が用いられる。

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

５ データバス１６８にはデータ送信回路１７０及びデータ
受信回路１７２が接続されている。データ送信回路１７
０ば、パケノ１〜全体を送信前に記憶するために用いら
れるパケソ１−バッファ１７４を有ず。バッファ１７４
内のバケソ１−は、送信器１７８によってリンクセレク
タ１８２を介してリンクインタフェース回路１８０へ伝
送される前にｌｋハイドＦＩＦＯ（先入れ先出し）バッ
ファ回路１７６へ転送される。

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

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

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

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

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

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

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

受信回路は、データ受（８器１９０、大型（例え９ ば４にハイド）ＦＩＦ○バッファ１９２、及びその後に
続く受信パケットバッファ１９４を含んでいる。データ
バケソｉ・が活性リンクから受信されるにつれ、このデ
ータは最初ＦＩＦＯバッファ１９２に記憶される。多く
の小型パケットを保持することのできるＦＩＦＯバッフ
ァ１９２から、データはパケットバッファ１９４内に転
送される。

全体パケットの終わりが検出されると、バッファ１９４
内のパケットは次いで処理され（即ち、ホストコンピュ
ータへ転送され）、そしてパケットバッファ１９４から
クリアされる。

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

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

リンクインタフェース回路１８０の主要な構成要素は２
つのｒＴＡ）Ｍｌチアン１９６及び１９８であり（送信
Ｈ１９６のためのＡｍ７９６８型チソプ、及び受信器１
９８のためのＡｍ７−９６９型チツプであり、いずれも
アドバンスト・マイクロ・デバイシーズ（＾ｄｖａｎｃ
ｅｄ　Ｍｉｃｒｏ　ｄｅｖｉｃｅｓ）社製の集積回路で
ある）、これらは標準の「透過」非同１ 期送信器及び受信器インタフェース回路である。

これらの回路は、点間リンクにわたる高速データ伝送を
取り扱い、従って、本実施例において用いる１００メガ
ビツト・データ伝送速度に好適する。

検出器２００は単一ブースタであり、受信回路１９８が
弱い人力信号を取り扱うのを助ける。

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

本発明のネットワークを制御する中央制御器または知能
はない。このネットワークの知能及び中央ロジソクは、
経路指定決定をなし、及び他の種々のネノトワーク管理
タスクを行うものであり、ネノトヮーク内の全てのスイ
ッチにわたって分布２ されている。例えば、各スイッチは、各データパケット
を伝送するのに用いられた前のリンクについての知識な
しに、経路指定決定を独立に行う。

しかし、これらスイッチは、各々がパケットの効率的且
つエラーなし経路指定を容易にするように設計されてい
る。

先ず第８図のブロック線図について説明すると、スイッ
チ２１０の主要な構成要素は、非ブロック化りロスハー
スイッチ２１２、リンク制御装置２１４と呼ばれる複数
（本例においては１２）のスイッチボー１２１４、スイ
ッチ制御卸▽プロセッサ（ＳＣＰ）２１６、及び経路指
定論理回路２１８とも呼ばれる！レータ２１８である。

また、５ＣＰ２１６をクロスバ−スイッチ２１２に接続
するための特別のリンク回路２１４ａがある。

各リンク装置２１４はクロスハースイ、チ２１２を１つ
の全二重リンク２１５に接続する。各リンク２１５は２
つのデータチャネルを有し、従って、データをリンク２
１５上で双方向に同時に伝送することができる。即し、
各リンク装置２１４は２つの構成要素、即ち、入力リン
ク装置２２０（Ｒｘ）及び出力リンク装置２２２（Ｔｘ
）を任ず。

新しいデータパケット▽がスイッチ２１０に受信される
と、このデータパケットを受信する入力リンク装置２２
０はりしスハースイッチ２１２によって出力リンク装置
２２２Δに（人力リンクと異なるリンクに対し）接続さ
れる。出力リン、り装置２２２は前記受信されたデータ
パケットを他のリンク上で伝送し、このパケット▽をそ
の宛先・＼送り出す。

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

ルータ２１８の目的は、どの出力リンク装置２２２を各
入力リンク装置２２０に接続ずべきかを決めることであ
る。新しいデータパケットが入力リンク装置２２０に受
信されると、入力リンク▽３ ▽４ 装置２２０は経路指定要求をルータ２１８へ送る。

この経路指定要求はこのパケットの宛先及び人力リンク
装置の識別を特定する。第８同に示すように、リンク装
Ｈ２２０ばこのパケットの宛先アドレスをバス２３０上
でルータ２１８へ送ル。

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

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

可用性フラグが各リンク装置２２２によってルタ２１８
へ周期的に送られる。可用性フラグは、出力リンクが使
用中でなく、「閉塞されてなく」、従って新しいデータ
パケット▽を経路指定するのに使用可能であ不ときにオ
ンとなる。出力リンク装置は、リンク（即ち、出力リン
クに接続されているリンク）装置の他端部にあるスイッ
チがストップ▽フローコマンドを送ったときに、閉塞さ
れる。

スト▽ップフローコマンドは、リンクの他の側にあるス
イッチがこれ以上のデータを受信する準備ができていな
い、とい・うごとを示す。出力リンク装置２２２が使用
中であるかまたは閉塞されているときには、その可用性
マスクはオフとなる。出力リンク装置からの１３の可用
性マスクビットがルータ２１８によって周期的にサンプ
リングされ、経路選択を行うために用いられる。

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

ルータ２１８については、第１３図ないし第▽５ ▽６ １６図について後で更に詳細に説明する。ルータ２１８
のための回路の実施例が、本発明の米国特許出願と同■
、！出願の「高速メ・７シユ接続式ロー力ルエリア不ソ
トワークのための経路指定の装置及び方法」なる名称の
米国特許出願第　　　　　号に記載されている。その内
容を木明細書において一参照として説明する。

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

ＳＣＰ　　２１６は標準のマイクＩコブロセソサであり
（例えば、モトローラ（ＭＯｔｏｒｏｌａ）社製の６８
０１０型マイクロプロセノサが本実施例に用いられてい
る）、これは、スイッチ２１０が状勢またはりセットさ
れるとルータ２１８を初期設定するように、及びネット
ワークの構成要素が故障するかまたは新しい構成要素が
ネットワークに付は加えられると再構成プログラムを行
うように、プログラムされている。ＳＣＰはＳＣＰパス
２２５７ によって全てのリンク装置２１４に接続され、ＳＣＰが
リンク装置の状態をモニタし、リンクに接続されてない
装置及び誤差動する装置を識別することのできるように
なっている。

リンク装置２１４ａはスイッチ制御Ｗ１１プロセノづ−
（ＳＣＰ）２１．６をクロスバースイッチに接続し、従
って、ＳＣＰ　　２１６はネソトマノーク内のホストコ
ンピュータと同し通信機構を用いてクロスバースインチ
２１２を介してデータパケットを送受することができる
。ネットワークの再構成中、ＳＣＰ　　２１６は隣のス
イチイ内のＳＣＰへデータパケットを送ってネットワー
クの形態を決定し、及びネットワークのスイッチ内のル
ータ２１８に対する経路指定テーブルの新しいセノトを
発生する。

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

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

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

クロスバ−スイッチ２１２は各リンク装置２１４に対す
る２つのマルチプレクサ（ＭＵＸ＞２４０及び２４２を
有す。第１のマルチプレクサ２４０は、データ伝送マル
チプレクサと呼ばれ、対応の出力リンク装置２２２をデ
ータ通路２３４のうちの選択されたものに接続する。リ
ンク装置２１４と同数のデータ伝送マルチプレクサ２４
０があるので、出力リンク装置２２２のうちのいくつか
または全数を入力リンク装置２２０のうちの対応する選
択されたものに同時に接続することができる。

換言すれば、スイッチ２１２は非ブロック化スイッチで
あり、多くのバゲノＩ・を同時に経路指定す０ ることかできる。

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

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

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

要約すると、クロスハースイッチはフロー制御コマンド
を人力及び出力リンク装置２２０及び２２２の各々へ導
くためのマルチプレクサ２４０または２４２を有ず。

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

出力リンクマスクは出力リンク装置２２２の各々に対す
る別々のオン／オフ・フラグを有す。

「１」の値付きのマスクフラグを存する各出力リンク２
２２は特定の人力リンク装置ね接続される。

同報通信フラグは、同報通信パケットが複数の複数のネ
ットワーク構成要素へ同時に経路指定されているときに
セソトされる。ルータバス有効フラグば、ルータ２１８
がバス２３２上で経路選択を主張しているとセソトされ
、さもないときにはりセノトされる。

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

ルータ２１８によって送り出されるリンクインデツクス
イ直はまたフロー制御卸マルチブレクザ２４２をセノＩ
・アソプするために用いられる。これを行゛うため、有
効ヒントがオンとなっているときに、クロスハースイン
チ２１２は、ルータ２１８によって送られたリンクマス
ク及びリンクインデックスを思い出し、次いで、このリ
ンクインデソクス４ 値によって特定された入力リンクに対してフロー’＋ｌ
１ｌｌ　ｊ卸マルチブレクザ２４２をセノトアノブする
。

ルータハス」二の同報通信ビットがオフとなっている場
合には、フＩコー制御マルチプレクサ２４２にロートさ
れる選択値は前記ハスのリンクマスク部上で識別される
出力リンクに対応する。

人力リンク装置２２０に受信されたデータパケットが複
数の出力リンクマスクへ同報通信されている場合には、
ルータハス上の同報通信ビットはオンとなり、フ１コー
制御マルチプレクザ２５にロートされる選択値は特定値
（例えば１５）となる。

これにより、人力リンク装置は、正常の制御信号の代わ
りに、ＣＩｋ２５６と呼ばれるクロックジェネレータ２
４６からの特定クロソク信号を使用さセられる。前述し
たように、正常フローＢｉｌ制御信号とは無関係に同報
通信パケットが伝送される。

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

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

ルータ２１８の動作及びルータハス２３２上で用いられ
る信−弓プＩコトフルについては第１３図ないし第１５
図について後で詳細に説明する。

スイッチフロー制御１１ 第１０図について説明すると、スイッチ相互間、及びス
イッチとホストとの間のフロー制御のための基本的機構
は次の通りである。各入力リンク装置は、受信したデー
タを一時的に記憶するために用いられる内部ＦＩＦＯハ
ノファを有す。理想的には、データは、これが記憶され
るのと同しくらいに速＜　Ｆ　Ｉ　Ｆ○ハノファから読
み出されるべきである。しかし、閉塞された（即ち、使
用中であり６ る）リンクのような種々の要因のため、データはＦＩＦ
Ｏハノファ内にパノクアノブさセられる。

ＦＩＦＯハ、ファが成る程度−杯になると、該バッファ
は、これにデータを送りつつあるネットワーク構成要素
（「送信器」）へストツブフローコマンドを送り出す。

この送信器がストツプフローコマンド、を受信すると、
該送信器は、スタートフローコマンドが受信されるまで
、データを送ることを一時的に停止する。受信用ＰＩＦ
○ハノファは、このＦＩＦ○バッファから十分なデータ
が読み出されてその量が所定の充満量よりも少なくなる
と、スター１−フーコーコマンドを送り出す。

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

いうまでもなく、スト・ツブフローコマンドがスイッチ
に受信されると、また、データはこのスイッチ内のＦＩ
ＦＯバッファ内でハソクアソブを開始する。Ｉｌｌら、
スイッチのヂエインの各々内の７ ＦＩＦ○バッファが一杯になるにつれて発生されルスト
ノプフｌ’ｍｌ−：：Ｉマントのチエイン反作用がある
。結局、データパケットが十分に長いならば、パケット
を送り出しているホストはスト・ツブフローコマンドを
受信し、パケットの残りを送り出すことを一時的に停止
する。

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

第１０図は、本実施例において用いられ、ネットワーク
を通るデータパケットの漬れに特に適切であるリンク装
置の細部の若干を示すものである。

第１０図には、２つのスイッチ３００及び３０２の連な
りを通るホス１〜コンピユータ１２０からのデータパケ
ットの流れを示しである。データパケットがスイッチ３
００内のリンク装置ｉに受信されると、該スイッチは、
人力リンク装置ｉをそのクロスバスイッチを介して出力
リンク装置ＴＸｊ８ に接続すること↓こより、前記バケノＩ−を経路指定す
る。このデータパケットは、次いで、第２のスイッチ３
０２をｉＪ１過し、該スイッチはこのパケットを再び経
路指定する。どれかのＲ，ｘリンク装置内のＦ　Ｉ　Ｆ
Ｏハノファ３１０．３４０が半ば一杯になると、該バッ
ファは、このＦＩＦＯバッファ内に既にあるデータが処
理されるまで、データ伝送チエイン内にある前のネット
ワーク構成要素にデータ伝送を停止させる。

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

リンク３１２が使用中でない場合には、スイッチは入力
リンク装置３０８を、選択されたリンク９ ３１２に接続されている出力リンク装置３２２に、クロ
スバ−スイッチ３２０を通して接続する。通例、スイッ
チ３００は出カスインチを選択することができ、及び人
力リンク装置３０８を出力リンク装Ｆ？　３２２に、デ
ータパケノ［・の最初の２５ハイ１−を受信するのに要
するよりも短い時間で、接続することができる。

しかし、リンク３１２が使用中でない場合には、スイッ
チ３００はデータパケットをＦＩＦ○バッファ３］０内
に記憶し続け、適当するリンクが使用可能となるのを待
つ。本実施例においては、Ｆ　ｌ’　Ｆ○バッファ３１
０は、４にバイトのパケットデータを記憶することがで
き、そして、バッファが少なくともハーフフル（ｈａｌ
、ｆ　ｆｕｌｌ　）になると線路３２４上にハーフフル
フラグを発生ずる組込み回路を有している。ＦＩＦＯバ
ッファ３１０がハーフフル未満である場合には、このフ
ラグは「スタートフロー１コマンドと解釈される。Ｔｉ
１ＦＯバソフアがハーフフルを越えている場合には、こ
のフラグは「ストップフロー」コマンドと解釈さ　００ れる。

ＦＩＦＯバッファ３１０からのハーフフルフラグの現在
値は、リンク３０６に接続されている出力リンク装置３
２６により、フロー制御値としてホスト１２０へ送り戻
される。フロー制御値がｒＯＪとなると、ホスト内のデ
ータ「スロソトル」（即ち、第７図におけるリンク制御
回ＦＩ！ｆｒ）が、ホスト１２０によるデータパケット
の伝送を可能にする。しかし、ＦＩＦ○バッファ３１０
がハーフフルに到達すると、このＦＩＦＯバッファによ
って発生される「ストノブフロー」コマンドが、ホスト
コンピュータ１２０内のスロットル１８６をして、ホス
トによるデータの伝送を一時的に停止させる。スイッチ
３００が、ＦＩＦＯバッファ３１０がハーフフル未満に
なるのに十分なデータを伝送すると、ＦＩＦＯバッファ
３１０は「スタートフロー」コマンドを送り出し、この
コマンドはホストのスロットル１８６がデータパケット
伝送を再開することを可能にする。

第１１図について後で説明するように、若干の　０１ 組込み伝送遅延及びパケット取扱要求があり、そのため
、ＦＩＦＯバッファ３１０が最初「ストノブフロー」コ
マンドを発生するときに該バッファ内に約２にバイトの
余地を持っていることが必要となる。一般に、最小限要
求されるＦＩＦＯハノファ３１０の大きさは最大リンク
長及び最大同報通信パケットの大きさの関数である。そ
の結果、例えばＩＤＴ　　７２０４型のような、４ｋ　
　ｘ　　９ＦＩＦＯハソフアを用いるのが便利であると
いうが認められた。前記ＩＤＴ　　７２０４型は、Ｆ　
Ｉ　＋ｉ　０バソフアが空であるかどうかを、及び少な
くともハーフフルになっているかどうかを示すフラグを
発生する回路を既に含んでいる。

第１０図に示すように、第１のスイッチ３００がデータ
パケットをリンク３１２上に経路指定するとき、このデ
ータパケットは他のスイッチ３０２に受信される。ここ
で、このデータパケットは入力リンク装置３４２内のＦ
ＩＦＯバッファ３４０に再び記憶され、一方、このスイ
ッチはこのパケットをどこへ経路指定するかを決定する
。データ　０２ パケ／１・を経路指定することのてきる可用リンクがな
い場合には、ＦＩＦＯバッファ３４．０は、これがハー
フフルとなると、線路３４４」二に「ストップフロー」
コマンドを発生する。このスＩ・ノブフローコマンドは
リンク３１２上でスイッチ１へ送られる。詳述すると、
このス１〜ノブフローコマンドはスイッチ３００の入力
装置３３０に受信され、次いで、このフローコマンドは
、出力リンク装置３３２を、次いでりＩコスハースイッ
チ３２０を通して、データパケットを受信しつつある入
力リンク装置３０８へ経路指定される。そこで、このフ
ローコマンドはスロ、トル回路、即ち出力リンク装置３
３２を制御し、この回路は、スタート７ｏ−コマンドを
受１言するとＦＩＦＯバッファ３１０に記憶されている
データの伝送を可能にし、ストノブフローコマンドを受
信すると伝送を不能にする。

リンク３４６が使用可能となると、スイッチ３０２はＦ
ＩＦＯバッファ３４０内のデータを出力リンク装置３４
８を介してリンク３４６上へ伝０３ 送し始める。Ｆ　Ｉ　Ｆ○バッファ３４０がハーフフル
未満となると、該バッファはスターＩ・フローコマン１
を線路３４４上へ送り出し、スイッチ３００がデータパ
ケットの伝送を再開することを可能にする。

リンク装置 第１１図は第１０図に示したスイッチ３００の入力及び
出力リンク装置を更に詳細に示すものである。各人力リ
ンク装置３０８及び３１０はＴＡＸＩ受信器チソプ３５
０を有し、このチップは受信リンク３０６またば３１２
上で受信したビット直列データを９ビン１〜並列信号に
変換し、この信号は９ビット幅バス上でデマルチプレク
サ（ＤＭＵＸ）３５２へ送られる。データの各ハイドは
、このハイドがデータであるかコマンドであるかを示す
データ型フラグを有し、このフラグは各ハイドの９番目
のビツトを構成する。

デマルチプレクサ３５２はＴＡＸＩ　　Ｒｘ回路３５０
から受信した信号の型フラグをモニタし、データからの
データストリーム内のコマンドを分　０４ 割する。データ信号、及びパケット「コマンドハイド」
の終わりはＦＩＦ○バッファ３１０に記憶される。リン
４３０６上で受信されたフロー制御コマンドはオン／オ
フ（即ち、ｌ１０）２進信号に変換され、この信号は線
路３５４上で伝送される。線路３５４上のフロー制御コ
マンドはう・７チ３５６にランチされ、このランチは対
応の出力リンク装置３２２の伝送りロックＣ１ｋ２５６
でクロメノされる。ランチされたフロー制御信号は、次
いで、ＡＮＤケート３５８によって伝送りロックＣ１ｋ
２５６とＡＮＤ処理され、その結果の信号はクロスハー
スインチ３２０を通って送り出されて他の人力リンク装
置３０８へ伝送される。

ＡＮＤ’）’−１３５８の出力は、クロスバ−スイッチ
３２０により、入力リンク装置３０８内のスロソトル制
御線３６０−・接続される。

ラッチ３５６及びＡＮＤゲー１−３５８は、入力リンク
装置３０８へ送られたフロー制御信号を出力リンク装置
３２２の伝送りロソクと同期させる。

また、ＡＮＤゲート３５８は、伝送済みフローコニ　０
５ マントを２５６パイト毎に１回オフとなしてり１コスハ
ースイッチ３２０を通るデータの伝送を１ハイド間停止
させる。この間、出力リンク装置３２２はデータの代わ
りにフロー制御信号を送り出す。

要するに、出力リンク装置３２２は、りロックＣ１ｋ２
５６で定まる２５６ハイトザイクル毎に「ストップフロ
ー」コマンドをスロソトル制御線上に送り出し、従って
、対応のＦＩＦＯバッファ３１０のスロットル３３２は
、スイッチのフロ制ｆｆｆｌｌザイクル中はデータを送
り出すことがない。

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

各出力リンク装置３２２はクロスバ−スイッチ３２０か
ら受信した９ビツト並列信号をビツト直列信号に変換し
、この直列信号は出力リンク３１２上で伝送される。詳
述すると、出力リンク装置３２２はマルチプレクサ３６
２を有す。マルチプレクサ３６２はクロソクＣＩｋ２５
６に接続され、　０６ このクロソクは、線路３６４からのデータの伝送を２５
５データバイトサイクルずつ交互に可能にし、次いで１
フローコマンドハイドの伝送を可能にする。ＣＩｋ２５
５と同し周期を持つクロソクがデマルチプレクサ３５２
に接続されており、従って、ＦＩＦＯバッファ３１０は
、平均として、空になるよりも速く一杯になることはな
い。

マルチプレクサ３６２は、これが線路３６６の状態から
送るフローコマンドを引き出す。線路３６６は、人力リ
ンク装置３３０内のＦＩＦＯバッファ３１０によって発
生されるハーフフルフラグを運ぶ。一般に、ＦＩＦＯバ
ッファ３１０が少なくともハーフフルになると、オン（
即ち、ストノブ）信号が線路３６６上で送られ、さもな
い場合にはオフ（即ち、入り−ト）信号が線路３６６上
で送られる。線路３６６」二の信号はエンコーダＩｊｌ
ｉｌ路３６８によって９ビノト「スト７ブフロー」また
は「スタートフロー」コマンドに変換され、ＴａｘｉＴ
ｘ回路３７０によって伝送される。

マルチプし・フサ３６２によって出力されたデー　０７ り及びフローコマンドはＴＡＸＩ送信器３７０によって
ビット直列データスＩ・ソー１、に変換され、この送信
器は多重化されたデータ及びコマンドをリンク３１２上
で伝送する。

第１２図はリンク装置回路の細部を更に示すものである
。第１Ｉ図に示す入力リンク装置３０８内のデマルチプ
レクサ３５２は、第１２図では、パイプラインレジスタ
３８０、状態レジスタ３８２及び制御ａジンク３８４を
用いて実現されている。

受信された全てのデータは、ｌハイトザイクル間、パイ
プラインレジスタ３８０に記憶され、これは、各ハイド
をＦＩＦＯバッファ３１０にロードずべきかどうかを決
めるための時間を制御ロジック３８４に与える。フロー
コマンドはデコートされ、状態レジスタ３８２に記憶さ
れる。制御ロジノク３８４は、受信中のデータと同期さ
せられる線路３８５」二のクロック信号を受信する。こ
のクロック信号はＴＡＸＴ　　Ｒｘ回路３５０によって
発生される。制御ロジック３８４は状態レジスタ３８２
を読み出し、成るコマンドが受信されると、ＰＩＦＯ０
８ バッファ３１０内へのデータのローディングを不能にす
る。もっと−船釣には、制御ロジック３８４は１セット
のクロック信号を発生する有限状態マシンであり、この
信号は、人力リンク装置の一部を通ってＦＩＦＯバッフ
ァ３１０の人力ポートにまで至ってこれを含むデータの
流れを制御するのに用いられる。

ＦＩＦＯバッファ３１０の入力側は、ＴＡＸＩＲｘ回路
３５０に受信されるデータで同期化され、ＦＩＦ○バッ
ファ３１０の出力イ則はスイッチ内の独立クロック回路
によって発生される異なるクロック信号によってクロソ
クされる。これら２つのクロツク信号は約０．０２％以
内でほぼ等しいが、同期はさせられない。

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

第１１図に示すスロットル３３２は、ＦＩＦＯバッファ
３１０に対する出力クロック信号を発生する制御ロジッ
ク３９２、及びパイプラインレジスタ３９２によって実
現される。制御ロジック３９２ば線路３５４からフロー
制御信号を受信する。この受信されたフロー制御信号は
他の人力リンク装置によってクロスバースイッチを通っ
て伝送されたものである。ストップフローコマンドが受
信されると、制御ロジック３９２はＦＩＦ○バッファ３
１０及びパイプラインレジスタ３９０に対する出力クロ
ック信号を単に使用禁止となし、これにより、ＦＩＦＯ
バッファ３１０からのデータの流れを停止さセる。

制御ロジック３９２はまた、データの各９ピント・バイ
トのデータ／コマンド・ビットがＦＩＦＯバッファ３１
０から読み出されるときにこれをモニタし、各パケット
の終わりを識別する。データ及びパケツトコマンドハイ
トの終りだけがＰＩＦ○バッファ３１０に記憶される。

従って、イネーブ１０ ルされたコマンドビソトがＦ　Ｉ　Ｆ○バッファ３１０
から読め出されと、パゲソ１〜の終りが制？ｆｆ１ｌ　
ｌ：′Ｉジソク３９２によって検出される。各パケット
の終りの後、制御ロジック３９２ば、現在パケットがパ
イプラインをクリアするまで待ち、次いで、送り出すべ
き新しいデータパケ・ノドを探し始める。

制御ロシソク３９２ばルータハス２３２を介してルータ
２１８と会話する。新しいパケットの始まりが検出され
ると、制御ロジック３９２ば、ルータハス２３２のリン
クマスク部上で経路指定要求を送り出し、そして、その
後のタイムス日ソ１へ中に、ルータハスの同しリンクマ
スク部上の「グランｋｌ　　（ｇｒａｎＬ　）信号を受
け取る。グランド信号が受け取られると、前記新しいパ
ケットに対するパケットの宛先アドレスがハス２３０上
のバッファ３９４によって主張される。制御ロジック３
９２はまた、新しいパケットの伝送を、ハス２３２上の
ルータによって送られる経路指定選択信号と同期させる
。

両方のロジソク回路３８４及び３９２は、人力■ ■ リンク装置３０８の現在状態を示す状態信号を状態レジ
スタ３８２に記憶させる。スイッチ制御卸プロセソザ（
３１）Ｃ）は、状態レジスタ３８２にδ己憶されている
状態値のうちの若干を周期的に読み出し、どのリンク装
置が生きているリンクに接続されているか、及びどのリ
ンク装置が適正に働いているかを測定する。

第１２図に示す出力リンク装置３２６は、パイプライン
レジスタ４０２、デコーダ４０４、有限状態マシン（Ｆ
ＳＭ）４０６、及びＴＡＸＩ送信器３７０から戒ってい
る。クロスハースイッチからのデータは、１クロソクサ
イクル間、パイプラインレジスタ４０２内に保持され、
ＴＡＸＩタイごング仕様によって要求されるデコーダ４
０４のセソＩ−アソブを許す。パケントコーンンドハ′
イトの終りがパイプラインレジスタ４０２に受信される
と、ＦＳＭ　　／１０６はこのコマンドを認識し、そし
てその内部状態を変更する。その後、対応の出力リンク
が、入力リンク装Ｗ３０８によって受信されたストツプ
（ＳＴＯＰ）フロー制御信号によ■ って阻止されていないならば、ＦＭＳ　　４０６は「リ
ンク可用」信号をルータ２１８へ送り出し、そこでルー
タは、このリンクが新しいパケットを経路指定するため
に使用可能であるということを知る。ＦＭＳ　　４０６
はまた、パケットコマンドバイトの終りを送り出すこと
をＴＡＸＩ　　Ｔｘ回路３７０に指令し、次いで、ルー
タ２１８が他のパケットの伝送のために出力リンク装置
３２６を人力リンクに再接続するまで、同期化バイトを
送り出すことをＴＡＸＩ　　３７０に指令する。

デコーダ４０４はＦＳＭ　　４０６とともに、第１図の
マルチプレクサ３６２として働く。詳述すると、ＦＳＭ
　　４０６はＣＩｋ２５６クロソク信号を用い、何時Ｔ
ＡＸＩがクロスバースイッチからデータを伝送するか、
及び何時該ＴＡＸＩがフローコマンドを伝送するかを測
定する。デコーダ４０４は人力リンク装置からＦＩＦＯ
ハーフフル状態信号を受け取る。フロー制御信号を伝送
するための各期間中、デコーダ４０４はＦＩＦＯハーフ
フル信号をデコードし、ＴＡＸＩ　　３７０に対　１３ する適切なコマンドを形成する。各パケットの始マリに
おいて該パケットはビギン（肝ＧＩＮ　）コマンドを形
成し、各パケットの終りにおいてデコダ４０４はエンド
（ＥＮＤ　）コマンドを形成する。

出力リンク装置がスＩ・ツブフローコマンドによって阻
止されている場合、または出力リンク装置がアイドルと
なっている場合には、デコーダ４０４は５ＹＮＫコマン
ドを形成する。他の全ての期間中は、デコーダ４０４は
「データ伝送」コマンドをＴＡＸＩ　　３７０へ送る。

ＦＳＭ　　４０６は、出力リンク装置３２６の状態、及
びどのコマンドをデコーダ４０４が’Ｔ”ＡＸＩ　　３
７０へ送るべきかを決定する。

出力リンクＦＳＭ　　４０６はまた、新しいデタパケッ
トの伝送を、ハス２３２上のルータによって送られる経
路指定選択信号と同期させる。同し経路指定選択信号を
クロスハースイッチ内の経路選択ロジック４０８が用い
、特定の入力リンク装置を１つまたは複数の特定の出力
リンク装置に接続するためのデータ及びフローマルチプ
レクサ　１４ をセソＩ・アソプする。

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

全同報通信パケツトを受信することのできるために、Ｆ
ＴＦＯバッファ３１０がストソプフロ−コマンドを送り
出すときに該バッファ内に残っているべき余地の量を測
定するには、次の因子がある。即ち、ストップフローコ
マンドが送り出される前の最大遅延、伝送用ネットワー
ク構成要素がストソブコマンドを受信してこれに対して
働くときに既に伝送されてしまっているデータの最大量
、及び、同報通信パケットの最大大きさ、がある。

■ ５ また、１００メガビソト／秒の伝送速度を持つ２キロメ
ートルの光フアイバケーブルに対しては、伝送用イ、ソ
Ｉ・ワーク構成要素がストソブコマントを受信するとき
に既に伝送されてしまっているデータの量は約２６０ハ
イドである。前記遅延因子に加え、ＰＩＦ○バッファ３
１０ば、送り出されようとしている同報通信パケットを
該パケソ［・内のデータを何も失うことなしに該バッフ
ァが吸収することのできるようにするため、該バッファ
がストップフローコマンドを発生ずるときに少なくとも
２０４４　（２５６＋２６０　＋］　５２８　）ハイド
の未使用記憶装置を必要とする。その他の遅延に備え、
及び追加の安全マージンを提供するため、ＦＴＦＯバッ
ファ３１０は、これが残りの記憶装置の２に、（即ち（
２０４，８）ハイドを持つときに、スＩ・ソプフローコ
マンドを発生ずる。

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

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

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

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

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

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

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

ルータ回路 ネットワーク内の全てのスイッチにばその４８ビソトＵ
ＩＤに加え、一意的７ビソト５ＨＯＲＴＩＤが害りり当
てられている。５ＨＯＲＴ　　ＩＤはネットワークの構
成中に割り当てられ、何等かの　２０ 特定のスイッチに対する５ＨＯＲＴ　　ＩＤはネットワ
ークが再構成されるときに変化する。各ホストコンピュ
ータには１１ビツト「ネットワークアドレス」が割り当
てられる。ホストコンピュータのネットワークアドレス
は、そのスイッチの５ＨＯＰＴ　　ＩＤを、このホスト
をスイッチに接続しているリンクポートの４ピント値と
連結することによって発生される。各スイッチのネット
ワークアドレスは、（−（７１）ＳＨＯＲＴ　　ＩＤに
、ｓｅｐリンク装置のリンク番号に対応する所定の４ビ
ツト値（例えば、ゼロ）を加えたものである。

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

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

データパケットを初めて伝送するとき、このデータパケ
ットが送られるネットワーク構成要素のネットワークア
ドレスはパケットの最初の数ハイドに記憶される。ルー
タ２１８は、ショートアドレス（ｓｈｏｒｔ　ａｄｄｒ
ｅｓｓ）の値、及びパケットを受信する人力リンクを用
い、どの出力リンクを用いてデータパケットを再伝送す
べかを決定する。

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

先着先行的経路指定秩序を用いると、割当てが、早く来
た要求の必要性と衝突することのないかぎり、この早く
来た要求の前に、遅く来た要求に資源が割当てられる。

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

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

各「経路指定アドレス」は１１ビソ［・・パゲソトアド
レス及び４ビソト入力リンク番号を有す。

経路指定ア１−レスυよレジスタ４２０に記憶される。

経路指定テーブル４２２は経路指定ア１−レス埴によっ
てインデソクスされるルックアップテーブルである。経
路指定テーブル４２２は、可能性ある全ての経路指定ア
ドレス値に対するエントりを含んでおり、これは、経路
指定アｌ−レスに対応するバゲソＩ・を経路指定するた
めに用いられる可能１生ある出力リンクを特定する。

人カリンクＷｊＭがそのＦ　Ｉ　Ｆ　Ｏバッファの１１
ｊ力部におレノる新しいパケットの受信を検出すると、
該装置はリンクマスク部２３２Ａ上に要求信７Ｊ−を送
る。

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

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

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

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

経路指定テーブル４２２は可能性ある全ての経路指定ア
ドレスのためのエン［・す４２６を有ず。

換言すれば、該テーブルは、４ビツト人力リンク番号と
１１ビノト・パケツトアドレスとの可能性ある全ての組
合せのためのエントリを有す。これら２つのイ直は１５
ビツトを占めるから、テーブル４２２内のエンＩ・りの
数は２１５、またば３２．７６８となる。各エントリは
記憶装置の２ハイドを占め、従ってテーブル４２２は６
５，５３６ハイトの記憶装置を必要とする。一般に、経
路指定テーブル内のエントリのうちの少数だけが「合法
的」経路指定要求を表し、他の全てのものは、改悪され
たかまたは違法な要求値を表す。違法要求に対するテブ
ルエントリはＢＣ＝１であり、マスクの残りの部分は全
てゼロに等しい。データパケットが違法経路指定要求を
発生ずる場合には、このデータパケットはスイッチから
追い出される。

経路指定テーブル４２２が人力リンク番号及びネットワ
ークアドレスによってインデソクスされ、　２７ ネソ；ワークアドレスのみによってはインデソクスされ
ないという理由は次の通りである。バゲソト内の不ソト
ワークアＩ・レスが改悪されているということがないな
らば、経路指定テーブルをネットワークアドレスによっ
てインデソクスすることができる。経路指定チーフル内
のエントリは、なお、アップ／ダウン経路指定規則に従
っている。

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

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

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

経路指定マスクの一例を次に示す。

　２９ アドレス（直　　　　　　　経路指定マスク人力リンク
、パケットアドレス　　　ＢＣ１０１２３４５６７８９
八Ｂ（リンク番号）０１１．０　１１００１１００１１
０　　０　　００１．１１０００００００経路指定テー
ブル内の各アドレスは、入力リンクから受け取られる可
能性のある経路指定要求値のうちの一つを表し、従って
、ここでは、人力リンク番号とパケツトアドレスとの連
結によって表されている。

各経路指定テーブルエンｌ−ＩＪ　４２６内の経路指定
マスクは１３のマスクビツトを含んでおり、ＳＣＰ含む
スイッチの出力リンクの各々に対して１つのビットがあ
る。オン（即ち、「１」に等しい）となっている各マス
クビｙ　ｈば、パケット・の経路指定に用いられる出力
リンクを表す。経路指定マスクも同報通信ビツトＢＣを
含んでおり、これば、パケット・アドレスが同報通信ア
ドレスであるか、通常アドレスであるかを示す。経路指
定マスク４２８の一例を第１４図に示してあり、これも
、以下に説明する理由で、経路指定マスク上の有効ビッ
ト及びその下のリンク番号を示している。

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

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

３ 各経路指定テーブルエンｌ−１，１４２６の経路指定マ
スク内のビット値は、前述のアップ／ダウン経路指定規
則によって決定される。アップ／ダウン経路指定規則に
よれば、データバゲｙ　Ｉ・に幻する合法的経路の七ソ
トは、使用された最後のリンク（即ち、現在スイッチを
取るために使用されたリンク）がアップリンクであった
かダウンリンクであったかによって定まる。前のスイッ
チがパケットをダウンリンク上で伝送していた場合には
、ダウンリンクのみが次のスイッチによって用いられる
。しかし、前のスイッチがアップリンクを使用していた
場合には、アップ及びダウンの両方のリンクが次のスイ
ッチによって合法的に使用される。

また、各経路指定マスク内に示される使用可能リンクの
セットは、データパケットを移動させてその宛先へ近付
けるリンクを含んでいるだけである。

第１４図は、経路指定エンジン４３０に読み込まれると
きの「経路指定要求」、即ち、経路指定マスク４２８の
フォーマツ１−を示すものである。

有効フラグと呼ばれる最上位のビットは、経路指　３２ 定要求が経路指定エンジンにロードされつつあるときに
は「１」にセットされ、処理されつつある新しい経路指
定要求がないどきには「０」にリセットされる。次の１
４ビツトは、前述したように、経路指定テーブル４２２
のうちの選択されたエントリから得られるリンクベクト
ルである。最後の４ビツトは経路指定中のパケットに対
する入力リンク番号である。

経路指定エンジン４３０は、現在使用可能な出力リンク
を表すリンク可用マスクを経路指定要求と比較する。詳
述すると、経路指定エンジン４３０の目的は、各新しい
パケットの出力リンク必要性をスイ、ソチの可屈出力リ
ンクと整合させることである。経路指定エンジン４３０
によって発生される経路指定選択値はクロスバ−スイッ
チ２１２（例えば第８図及び第９図に示す〉によって使
用されてそのマルチプレクサをセットアップし、これに
より、特定の人力リンクを１つまたは複数の特定の出力
リンクに接続する。経路指定エンジンは、本発明の米国
特許出願と同時出願の発明の名　３３ 称「高速メッシュ接続式ローカルエリアネットワークの
ための経路指定装置及び方法Ｊ　（ＲＯＵＴＩＮＧＡＰ
ＰＡＲＡＴＵＳ　　ＡＮＤ　　ＭＥＴＩＩＯＤ　　ｌ１
Ｏ１？　　＋１１Ｇ１１−５Ｉ”Ｉｉｌミ１〕　阿ＩＥ
ｓＩ＋Ｃ０ＮＮＥＣＴＥＤ　ＬＯＣＡＬ　ＥＲＨＡ　Ｎ
ＥＴＷＯＩ’ｌＫ）なる米国特許出願第　　　号の主題
である。

第１２図について前述したように、各出力リンク装置３
２６は「リンク曲用」信号を伝送し、これは、この出力
リンクが経路指定のために利用可能であるか、または既
に使用または阻止されているかを示す。バス２３２は全
ての出力リンクからのリンク可用信号線を持っている。

経路指定エンジン４３０は、各新しい経路指定エンジン
サイクルの始まりにおいてバス２３２上のリンク可用信
号をサンプリングする。次いで、経路指定エンジン４３
０は曲用リンクマスクを用いて経路指定選択を行なう。

経路指定エンジン４３０が、１つまたは複数の曲用リン
クをもって経路指定要求に整合することのできるように
なると、該エンジンは経路指定選択値を発生し、これを
ハス２３２上に出力する。

　３４ この経路指定選択値は、４ビソ１へ人力リンク番号、充
足された経路指定要求からの同報通信ビット及び有効ビ
ット、並びに、入力リンクに接続されるべき出力リンク
を識別する出力リンクマスクから戒ってい′る。前記の
大力リンク番号、同報通信ビット及び右動ビ・７トはル
ータハスの部分２３２Ｂ上で伝送され、出力リンクマス
クはルータハスの部分２３２Ａ−１＝で伝送される。ル
ータハス２３３上で伝送される経路選択値は、人力リン
ク装置２２０及び出力リンク装置２２２並びにクロスノ
＼−スイッチ２１２（第９図）によって用いられ、特定
人力リンクを１つまたは複数の特定出力リンクに接続す
る。

「有効］白カビ、ｌ・は、経路指定エンジン４３０が新
しい経路選択を出力しているサイクル中にのみオンとな
る。従って、経路指定エンジン４３０によって出力され
る「有効」ビノトは、経路指定エンジン４３０がいずれ
の東決定経路指定要求をも可屈出力リンクと整合さセる
ことのできないサイクル中は、オフとなる。

　３５ 制御回路４３５は経路指定エンジン４３０及び要求選択
回路４２４に対するりに１ソク信号を発生ずる。これら
クロソク信号はまたバケツ１〜アドレスバス２３０及び
ルータハス２３２の使用を制御する。そのタイミングプ
ロトコルについては第１６図について後で説明する。

制御卸ロジソク４３５はまた５ＣＩ）２１６によって用
いられ、不ソトワークの再構成中に経路指定テーブル４
２８を再ロードし、ルータ２１８の状態のトランクを保
持し、及び、スイッチ全体が敵勢またはリセ・ントされ
ると成るファームウェアを経路指定エンジン４３０にロ
ートする。

径羅框是主ｌ之Ｚ 第１５図は経路指定エンジン４３０の実施例を示すもの
である。本実施例においては、経路指定エンジンは計算
構成部材のアレイ４５０で形成されており、該部材の各
々を第１５図においてポソクスで表しである。図示のア
レイは、ザイリンクス（Ｘｉｌｉｎｘ）社製のザイリン
クス３０９０型と呼ばれるプログラマブルゲートアレイ
を表している。

　３６ ザイリンクス３０９０型アレイは１６の桁を有しており
、各桁にば１２の組合せ論理ブロック（ＣＬＢ）がある
。ＣＬ　Ｂば、種々の論理及び記憶の機能を行なうよう
に電気的にプログラムされる。各ＣＬＢは２つのフリツ
プフロツプ及び２つの機能装置を有す。各機能装置は４
つの入力変数までのすべてのプール関数を計算すること
ができる。ＣＬＢは、機能ブロックまたはフリツプフロ
ツプから直接に来ることができる２つの出力を発生する
。また、各ＣＬ　Ｂの近くには２つのトライステートド
ライバがある。これらＩ・ライバは、チソプを横切る水
平の金属トレースに接続され、ハスを構成することがで
きる。プログラマブルロジックを提供するほかに、ザイ
リンクス３０９０型アレイは、相隣るＣＬＢ間、及び該
アレイの外側の回路に対するインタフェースを提供する
複数のバットセル間のプログラマブル相互接続を提供す
る。即ち、このアレイの挙動及び機能は、外部転送元（
例えば、各スイッチ内の５ＣＰ）から該アレイにロード
される制御ビットのパターンによって決定される。

　３７ チップ製造の一部としてカスタマイゼーション（ｃｕｓ
ｔｏｍｉｚａｔｉｏｎ）は行なわれない。

経路指定エンジンアレイ４５０は１３の桁４５１〜４６
３を用い、その各々には１９の論理ブロックがある。こ
れら桁４５１〜４６３の各々は単一の経路指定要求を記
憶及び処理する。また、アレイの右側には、１３のレデ
ィ信号ジェネレータ（ＲＧ）の桁４６５及び１３の出力
信号シェイ、レーク（０）の桁４６８がある。

経路指定要求はアレイの左側で受け取られる。

アレイの左側に示しである信号記号は第１４図に示す経
路指定要求のフォーマソトに整合する。

出力リンク曲用マスクはアレイ４５０の右側で受け取ら
れる。出力リンク曲用マスクを記号ＲＤＹＯないしＲＤ
Ｙ１２で表してあり、これは、第１３図に示すようにバ
ッファ４４０から受け取られる。

アレイ４５０からの出力は、経路指定エンジンによって
作られる経路指定選択であり、アレイの右側からバス４
７０上に現われる。第１３図について前述したように、
経路指定選択は、１９ビソ　３８ ト、即ち、経路指定選択がなされたということを示ず有
効ビツト、１３ビ７　Ｌ出力マスク、並び↓こ経路指定
要求からの同報通信ビ・ノド及び４ビソＩ・人力リンク
番号を含んでいる。

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

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

第１６図について説明すると、各クロソクサイクルは６
つの位相ＴＯ〜Ｔ５を有す。各位相は８０ナノ秒継続し
、総計クロソクサイクルは４８０ナノ秒になる。ルータ
クロソクサイクルは、クロソク信号ＴＯ３で示す２つの
主な副位相を有す。

第１の側位相中ばＴＯ３＝１であり、第２の側位相中は
ＴＯ３＝Ｏである。

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

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

選択された要求は、次のルークサイクルのＴ３中、選択
されたリンク装置へハス２３２」二でオン信号を送るこ
とによって肯定応答される。この冑゛定応答信号は、信
号を送られたリンク装置に、該装置がその経路指定要求
をバス２３０Ｊ：で伝送す４０ るように４尺された、ということを知らせる。クロノク
位相′■゛３〜Ｔ５中、選択された前記リンク装置はそ
の経路指定要求に対するパケットアドレスをパソファ４
２０を介して経路指定テーブル４２２へ送る。位相Ｔ３
〜Ｔ５中、経路指定テーブル４２２はアクセスされ、前
記経路指定要求に対応するリンクベクトルは、Ｔ５の終
りまでに、その出力部においてレディ状態となる。

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

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

４１ ルータサイクルＴＯ〜Ｔ５の残り部分中、経路指定エン
ジン４３０はリンク内にラソチされた可屈データを、経
路指定エンジン４３０のデータ桁内に記憶されている全
ての未充足の経路指定要求と比較する。この比較の結果
は、Ｔ５の終りにおいて、経路指定エンジンの出力桁４
６８内にランチされる。しかし、経路指定エンジンによ
って発生された経路指定選択は、次ぎに続くルータサイ
クルのＴ１までは、ルータバス２３２上に主張されない
。このルークサイクルのＴ１〜Ｔ５中、経路指定選択の
ビツトがオンとなっている場合には、リンク装置及びク
ロスバ−スイッチは経路指定選択出力を処理し、これに
より、特定入力リンク装置を特定出力リンク装置と接続
する。これらリンク装置はまた、前記特定人力リンク装
置のＦ　Ｉ　１７０ハソフア３１０内のデータを伝送開
始する準備をする。

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

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

１段当り６つの８０ｎｓクロソクサイクルが３段パイプ
ラインにおいて用いると、ルータ２１８は１秒当り２百
万を若干越えるパケットを経路指定することができ、モ
して１スイッチ当り約１．４４ξり秒の待ち時間を各パ
ケットの１ｆｆｌ　路内に加える。

このルータパイプラインの３つの段は、（１）経路指定
要求マスクを発生するための人力リンク選択及び経路指
定テーブル索引、（２）経路指定選択　４３ ンジンサイクル、及び（３）クロスハースインチ２１２
及びリンク装置への経路指定選択の伝送である。

ルータサイクルの各位相中の経路指定エンジンの動作に
ついて次に更に詳細に説明する。各ルータサイクルの始
まりに、ＴＯの始まりにおいて、経路指定要求及び可用
出力リンクマスクが読み込まれる。経路指定要求ばアレ
イ４５１の左端術↓こランチされ、リンク可用マスク（
ＲＤ　Ｙ　Ｏ−Ｒ１）Ｙ１２）はレディ信号桁４６５に
ランチされる。また、アレイに既に記憶されている各未
充足経路指定要求は、アレイ内の右に、未充足要求によ
って占められていない少なくとも１つの桁がある場合に
は、アレイ内で右へ１桁シフｌされる。

ルータサイクルの最初の態位相中、いくつかのセットの
信号がアレイを横切って伝播する。先ず、リンク可用マ
スクが右から左ヘアレイを横切って伝播する。要求取扱
い桁４５１〜４６３の各々における回路はその桁に記憶
されている経路指定要求をリンク可用マスクと比較する
。非同報通信要　４４ 求（ＢＤ＝０となっている）を記憶している桁において
、少なくとも１つの使用可能ＭＡＳＫビットが使用可能
ＲＤＹビソビツ整合する場合にＭＡＴＣ）Ｉ信号が発生
される。

同報通信要求（ＢＣ＝１となっている）を記憶している
桁において、全ての使用可能ＭＡＳＫビットが対応のＲ
ＤＹビソビツ整合する場合にのみ（即ち、この要求が必
要とする全ての出力リンクが使用可能である場合にのみ
）　、ＭＡＴＣＨ信号が発生される。

同報通信信号要求（ＢＤ＝１の）を記憶している桁はま
た、この同報通信要求のＭＡＳＫビソトビツ合するＲＤ
Ｙ信号の伝播を阻止する。事実、同報通信要求は、この
要求が必要とする可用出力リンクを「リザーブＪ　（ｒ
ｅｓｅ？ｖｅ）する。これが行なわれないと、同報通信
パケットの経路指定は、同報通信パケットが必要とする
出力リンクの個々のものに整合してこれを使用する後続
の要求によって永久に妨害される可能性がある。

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

２つまたはそれ以上の桁がＭＡＴＣＨ信号を発生するこ
とは完全に可能である。最も古い未充足要求に最初の考
慮を与えるためには、整合が見いだされた右端桁を選択
することが必要である。これを行なうため、ＡＮＳＷＥ
ＲＥＤと呼ばれる信号が、アレイの最上位にあるＣＩ全
セル通ってアレイの右側から左へ伝播する。ＡＮＳＷＥ
ＲＥＤ信号は、これが、使用可能Ｍ　Ａ　Ｔ　ＣＨ信号
を持つ有効桁（即ち、ＶＡＬｒＤ＝”１”）に出会うま
で、「０」の値を有し、この時点でＡＮＳＷＥＲＥＤは
ｒｌＪに等しくセットされる。

ＡＮＳＷＥＲＥＤ信号は、ルータサイクルの最初の態位
相中に伝播する第３の型の信号である。

Ｔ３の終りにおいて、出力イネーブル信号ＮＤＥＮＡＢ
ＬＥが、右隣の桁から「０」のＡＮＳＷＥＲＥＤ信号を
受け取る使用可能ＭＡＴＣＨ信号を持つ右端桁に対して
発生される。いうまでもなく、多く　４６ のクロソクサイクル中は、可屈リンクマスクに整合する
桁はなく、また、出力イネーブル信号は発生されない。

さしあたりは、出力イネーブル信号が１つの選択された
桁に対して発生される場合について考える。

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

ルータサイクルの第２の側位相中、使用可能ＮＤ　　Ｅ
ＮＡＢＬＥ信号を持つ桁からの次のデータ値が、即ち、
全ての整合済み経路指定マスクビット（即ち、曲用出力
リンクがある使用可能マスクビット）、同報通信ビット
、リンク番号ビツト、及び有効ビソＩ・が、アレイの出
力桁４６８へ伝播される。

出力桁４６８における回路は次のように働く。

　４７ 非同報通信要求（ＢＣ＝０）に対しては、使用可能マス
クビソＩ・のうちの最下位のものが出力されるだけであ
り、他の全てのビソＩ〜は使用禁止となる。同報通信要
求（ＢＣ＝１＞に対しては、全ての使用可能マスクビノ
トが出力される。両方の型の要求に対しては、同報通信
ビノト、リンク番号ビット、及び有効ビソＩ〜も出力桁
４６８によって出力される。

その結果の経路指定選択値ＩＬ、使用可能右動ヒント、
１つの使用可能マスクビツト（同報通信パケットでない
限り〉、並びに経路指定要求の同報通信ビン１〜及び人
力リンク番−冒を持つ。

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

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

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

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

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

このような要求が後続のサイクルにおいて結果を供給す
ることのないようにするには、各桁内にＢＣ及びＶ、Ａ
　Ｌ　Ｉ　Ｅ　Ｄ値を記憶しているレジスタの入力を、
桁から左へ、ＮＤ　　ＥＮＡＢＬＥ信号とＡＮＤ処理す
る。これは、桁が結果を供給して同しサイクル内でシフ
ト・する場合、要求は、これが次の桁内に右へシフトす
ると、無効化され、そしてそのＢＣビソｌ〜はクリアさ
れると、いうことを意味する。

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

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

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

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

即ち、これは同報通信パケットによって与えられる重要
な機能であるからである。

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

同報通信メッセージが用いられる他の場合は、　５３ ホストＡがホストＢヘパケットを送ろうとするが、ホス
トＢがこのパケットの受信を肯定応答しない場合である
。この状態に対する一般的なプロトコルは、ホストＡが
パケットを再び送ることである。

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

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

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

ホストｉ（１９で始まる同報通信パケットが後に続く通
路について考えてみる。このパケットにはｒ８ＦＦＪの
ような一意的１１ビツト「同報通信パケットアトレス」
が与えられている。最初、このパケソ［・はスイッチ７
３２．７２４．７１２、次いで７１０を通ってネットワ
ークツリーを上方へ移動して根に至る。これを行なうた
め、これらスイッチの各々内の経路指定テーブルは、使
用される入力リンクに対応するリンクへりドルエンドす
及び同報通信パケットアドレスを有す。スイッチ７３２
、７２４及び７１２の各々内のリンクヘクトルば、パケ
ットに使用可能な経路のみが、パケットをツリー７１０
の根の方へ上方へ移動さ一已るリンクに沿っている、と
いうことを示す。

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

第１７図に示ずネットワーク７００においては、　５　
６ 同報通信パケット・は根パケット７１０からスイッチ７
１２、７１４、７１６、７１８及び７２０へ同時に伝送
される。また同時に、同報通信パケットは、根スイッチ
に接続された全てのホスト（第１７図には示していない
）へ送られる。この伝送は、要求された全てのリンクが
使用可能となると生ずる。

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

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

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

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

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

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

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

　６０ 第１７図に示すように、ホスト相互間はスイッチ７１６
に対する第２のリンクを有し、ホスト付１２はスイッチ
７２８に対する第２のリンクを有す。スイッチ７２６が
故障するかまたは取り去られると、ホスｌ−１（１１及
び■１１２はそれらの２次リンクを賦勢する。その結果
、ネットワークが再構成された後、これらホストは新し
いネットワークアドレスを持つことになる。

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

第１８図について説明すると、ネットワークの構成にお
ける変化を検出するためのプロセスは次のように働く。

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

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

リンク状態検査プロセスは多重レベルプロセスであり、
各レベルはその結果を階層を上方へ次のレヘルヘ送る。

状Ｍ　検査プロセス８００のレベルば次の通りである。

ハードウェア調査レベル８０２は各リンク装置における
ハードウェアによって実行されるエラー検査プロセスで
ある。ハードウェアポーリングレベル８０４は各スイッ
チにおけるルーチンであり、ハードウェア調査レベル８
０２の出力を周期的に読取り、データ及びフロー制御　
６２ 信号が成る特定のリンク上で両方向に間違いなく送られ
ているかどうかを測定する。

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

状態変化フィルタ８０８は、リンク装置の状態がＤＥＡ
ＤからＡＬＩＶＥへ余りに頻繁に変化することを妨げる
。

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

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

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

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

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

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

フロー制御の項で前述したように、フロー制御コマンド
は、２５６バイトサイクル毎に１回、各出力リンク装置
によって伝送される。これは、このリンク装置のための
リンクに接続されたネットワーク構成部材が存在してい
なくとも、生ずる。

その結果、各人力リンク装置のハードウェアは、２５６
バイトサイクル毎に１回、有効フロー制御コマンドを受
信することを期待する。この有効フローコマンドのセッ
トは、スイッチからのスタート及びストップフローコマ
ンド、及びホストからのスタート及びストップフローコ
マンドを含んでいる。ホストに対するスタートフローコ
マンドはスイッチから受信されるものとは別個のもので
あ　６６ る。他のフローコマンドはＴ　Ｄ　ＨＹ（”　Ｉ　ｄｏ
ｎ’ｔｈｅａｒ　ｙｏｕ）　　と呼ばれる。これらのコ
マンド及びハードウェア調査レヘルによるそれらの使用
については次に説明する。

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

往復フロー制御検査は次のように働く。リンク装置が、
受信中のデータにおけるコード違反を確実に検出するか
、またはフロー制御コマンドの受信に失敗すると、この
リンク装置はＩ　Ｄ　Ｉ−Ｉ　Ｙコマンドと呼ばれる特
別のフローコンマドを伝送する。

これは、標準の「スタートフローＪコマンドの特別のバ
ージョンであると考えられる。

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

ＩＤＨＹフローコマンドが受信されると、この事がリン
ク装置に対する状態レジスタ３８２内に示される。

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

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

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

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

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

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

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

ＡＬＩＶＥであると表示されている他のスイッチに対す
るリンクに対しては、リンクの適正動作７ を検査するために「キープ・アライブ・メッセージＪ　
（ｋｅｅｐ　ａｌｉｖｅ　ｍｅｓｓａｇｅ）が用いられ
る。はぼ５秒毎に、「キープアライブメッセージ」がリ
ンクの他の側にある遠隔ネットワーク構成要素へ送られ
る。第１９図について説明すると、「キープアライブメ
ッセージ」８５０はテータパケットであり、このデータ
パケットは、伝送スイッチの［１１１］（即ち、一意的
４８ビソト識別子）８５Ｉ、リンクに対するポート番号
８５２、及び受信側がそれ自体を識別することによって
応答するということを示す回路フラグ８５９を示すもの
である。キプアライブメッセージはまた、リンクポート
ワクの他の側においてスイッチによって最後に報告され
たＵｒＤ　（ＲＵＩＤ８５６）　、及びこのスイッチに
よって最後に報告されたポート番号（ＲＰＯＲＴ８５８
）を含んでいる。

遠隔ネットワーク構成要素が真に生きている（ａｌｉｖ
ｅ）場合には、これは、キープアライブメッセージ８５
０と同じフォーマソトを用いる肯定応答メッセージをも
って応答する。即ち、この肯定　７９ 応答メッセージはそのＵｒＤ及びポート番号を示すだけ
でなく、更に、キープアライブメツセージ内に受信され
たＵＩＤ及びポート番号をエコーする。

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

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

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

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

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

扶簸変也７４ルタレヘル このレヘル８０８は、リンクがＡＬＴＶＢからＤＥＡＤ
への遷移を行なったということをメッセージ交換レベル
８０６が報告すると、直ちに再構成ルーチンを呼び出す
。

しかし、ＤＥＡＤからＡＬ　Ｉ　ＶＥへの遷移はフィル
タされる。詳述すると、状態変化フィルタレ　７５ ヘル８０８は、メッセージ交換レベル８０６からのＤＥ
ＡＤからＡ、　Ｌ　Ｉ　Ｖ　Ｅへの状態の変化を１５秒
毎に１回だけ受け入れる。このフィルタ作用は、間欠的
に働くネットワーク構成部制によって生ずる頻繁な再構
成をＩυｉ止することを助ける。

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

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

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

ヱ王二区童見塁奴 第１９図及び第２０図を参照し、再構成プロセスの第２
フエーズがどのように働くかを次に簡単に説明する。再
構成プロセス９００はフェーズ２及び３最中に３つの重
要なデータ構造９０２〜９０６を用いる。ポート情報ア
レイ９０２は、隣のもののＵＩＤ及び各隅のものによっ
て報知されるネットワーク内の位置のような、スイッチ
の直　７７ ぐ隣のものの各々に関する情報を記憶する。

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

ネットリス１ｉｎｅｔｌｉｓｔ）　　９０６は、不・７
トワークのトポロジの完全記述を構築するのに用いられ
、及び再構成プロセスのフェーズ２及びフェーズツリー
の両方において用いられる。

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

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

このメッセージを受信したスイッチは、この受信したエ
ポックを該スイッチが記憶していたエポソク番号と比較
する。前記受信したエポック番号の方が高い場合には、
前記スイッチは、ネットワークの構成について記憶して
いた全ての情報を削除し、そしてこの新しいエポック番
号を採用する。

前記スイッチはまた、前記受信したメッセージ内のｍｌ
を用い、ネットワークについての情報の新しいセットを
構築開始する。後述の所定基準のセットを用い、各スイ
ッチは、その既知の隣のものに対する「スパニングツリ
ー」内のその位置を決定することにより、「ツリー位置
」を開発する。

次いで、前記スイッチは全てのその隣のものヘメッセー
ジを送り、新しいエポック及びそのツリー位置において
報知する。スイッチが再構成メッセージを受け取る度毎
に、該スイッチは、ネソトワ７９ −クのトポロジについてのその情報を更新し、イ、ソ１
〜ワークについて今まで該スイッチが知っていることを
基礎としてそのツリー位置を更新する。

メッセージ内に何等かの新しい情報があった場合には、
スイッチはそれ自体及び全てのその隣のものへメッセー
ジを送り、その新しいツリー位置を知らせる。

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

再構成プロセスは「分散プロセス」と呼ばれる。

即ち、ネットワーク内の全てのスイッチは、結局はスパ
ニングツリーという共通の結果の発生へ通ずる計算を同
時に行なうからである。

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

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

データ構造 第１９図について説明すると、ネットワーク内　８１ のスイッチの「ツリー位置」をツリー位置アレイ９１０
で表しである。アレイ９１０の構成素子は、・ンリーの
享艮のＵＩＤ９１２、スパニング″ンリー内のスイッチ
の深さ９１４　（即ち、スイッチと根ノードとの間のリ
ンク数）、スイッチの親９１６、及び親スイッチに対す
るスイッチのアップリンク９１８のリンク番号である。

重要なこととして、再構成最中はスイッチはスパニング
ツリー内の該スイッチの真の位置を未だ知っておらず、
そして、ツリー位置アレイ９１０を用いて、スパニング
ツリー内のスイッチの位置についてのスイッチの現在の
所信を表す。また、ネットワーク内の根ノードは親９１
６をも、または親に対するアップリンク９１８をも有し
てない。

根ノートに対し、ツリー位置のこれら構成素子は特別の
「位置ホルダ」値を与えられる。

スイッチの「現在」のツリー位置は、ｃｐｏｓ９２０と
呼ばれるツリー位置アレイ内に記憶される。

スイッチは、該スイッチが全ての隣接スイッチ　８２ の同−性及び位置を知っているときに「安定」であると
みなされ、全ての隣接スイッチはスイッチのツリー位置
を知らされており、そして、（１）スパニングツリー内
のこのスイッチの下には隣接スイッチがないか、または
（２）スパニングツリー内のこのスイッチの下の全ての
隣接スイッチは安定である。スイッチの現在安定値はＣ
Ｓ　Ｔ”　Ｂ９２２と呼ばれ１．ＦＡＬＳＥまたは、Ｔ
ＲＵＥのいずれかに等しい。

ｒｓＪ９２４はスイッチのＵＩＤであり、５ＨＯＲＴＩ
Ｄ９２６はスイッチに前に割り当てられた７ビソトＳ　
ＨＯＲＴ　　Ｉ　Ｄである。スイッチＳがネットワーク
に追加されてターンオンされた場合には、このスイッチ
に前に割り当てられている５ＨＯＲＴ　　ＩＤはない。

ポート情報アレイ９０２はポート情報レコード９３０の
セットを有す。各ポート情報レコード９３０は、スイッ
チのポートの各々に接続されたネットワーク構成要素に
関する情報を記憶する。

前記レコードの各々は項ＩＮＦＯＣＰ）によって　８３ 識別される。ここに、ＩＩＮＦＯＪばポート悄孔アレイ
９０２の識別子であり、ｒ（１））Ｊは、Ｐに割り当て
られた値に従ってレコード９３０のうちの一つを識別す
る。各ポート・情報レコードの構成素子は次の通りであ
る。

ＴＮＦＯ，ＣＰ）ＴＹＰＥ９３２は、隣のものが、スイ
ッチ（ｒｓＪ）、ホストコンピュータ（ｒＨＪ）、また
はＤＥＡＤ　（ｒＤＪ）であるかどうかを識別する。Ｔ
ＹＰＥ（直はハードウェアポーリング層８０４によって
連続的に発生され、従って再構成プロセスのフェーズ２
に対して使用可能である。スイッチ及びホス（・は別々
のセットのフロー制御コマンドを使用する。第１８図に
ついて前述したハードウェア調査レベル８０２は、どの
フロー制御コマンドが受信されつつあるかを検出し、そ
してＴＹＰＥ値を状態レジスタ３８２に記憶し、リンク
によって接続されているものがスイッチであるかまたは
ホストコンピュータであるかを示す。ボーリンクがハー
ドウェアポーリングレベル８０４によってＡＬ　Ｉ　Ｖ
Ｅであると確認さ　８４ れると、このＴＹＰＥ値は、各ポートＰに対するポート
情報アレイ９０２のＩＮＦＯ〔Ｐ〕、ＴＹＰＥ構成素子
に記憶される。同様に、ＤＥＡＤリンクもアレイ９０２
のｒＮＦｏ　（Ｐ）、ＴＹＰＥ構成素子内に示される。

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

ポート情報アレイ９０２の他の構成素子は、スイッチに
接続されたポート、即ち、ＩＮＦＯＣＰ）ＴＹＰＥ−“
Ｓ”を有するポートに対してのみ用いられる。

ＩＮＦＯ（Ｐ）、ＲＰＯ３９３４はポー１−　Ｐ上のネ
ットワーク構成要素によって最後に報知されたツリー位
置である。「ツリー位置」は、常に、アレイ９１０内に
示される４つの値のセットである。

　８５ ＩＮＦＯＣＰ）、Ｅ　　ＰＯ３９３６は、ツリー位置が
ある場合には、ポートＰの隣のものが最後にスイッチに
エコーし返したツリー位置である。

この説明において、全ての「エコー済み」値は他のネッ
トワーク構成要素へ送られた値であり、これに対してネ
ットワーク構成要素は既に受信を肯定応答している。

ＩＮＦＯ（Ｐ）、Ｒ５ＴＢ９３８はポートＰの隣のもの
によって最後に報知された安定性値である。ＩＮＦＯＣ
Ｐ〕、Ｅ　　５ＴＢ９４０はポートＰの隣のものによっ
て最後にエコーされた安定性値である。

ＩＮＦＯ（Ｐ）、ＲＩＪＩＤ９４２はポートＰの隣のも
ののＵＩＤである。

ＩＮＦＯ（Ｐ）、ＲＰＯ３９３６は、隣のスイッチのポ
ートＰに接続されたこのスイッチのポートである。

ＩＮＦＯＣＰ）、ＮＢＷ９４６は、新しいといわれてい
る情報を持つメッセージがポートＰの隣のものから受信
されており、そしてこのメソセー　８６ ジがまだ肯定応答されていないときに、ＴＲＬＩＥとな
る。

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

メツセージデータ構造９０４は次の素子を含んでいる。

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

Ｍ、ＥＰＯＣＨ９５０はスイッチＳに知られているエポ
ソク番号（即ち、最後の構成バージョン番号）を表す。

Ｍ、Ｓ、　　　ＵＩＤ９５２はスイッチＳのＩＪＩＤで
ある。

Ｍ、Ｓ、　　　ＰＯ３９５６はスイッチＳの現在ツリー
位置である（即ち、ｃｐｏｓに等しい）。

Ｍ、Ｓ　　５ＴＢ９６０はスイッチＳの現在安定性　８
７ 値である（即ち、Ｃ３ＴＢに等しい）。

Ｍ、Ｅ　　ＰＯ３９５８は、このメッセージが送られつ
つあるスイッチによってｍｔ＆に報知されたツリー位置
であり、エコー済めツリー位置と呼ばれる。換言すれば
、Ｍ、Ｅｌ）Ｏ３は、メッセージが送られつつあるポー
トに対するＲ　　ＰＯ３９３２のコピーである。同様に
、Ｍ、ＥＳＴＢ９６２は、このメッセージが送られつつ
あるスイッチによって最後に報知された安定性値であり
（即ち、メッセージが送られつつあるポートに幻するＲ
３ＴＢに等しい〉、コ：コー済み安定性埴と呼ばれる。

Ｍ、ＮＥＷ９６／Ｉは、メノセーシＭ内の情報が「新し
い」と、即ち、新しい情報を含んでいると、考えられる
かどうかを示す。メッセージは、メッセージの目的が前
のメッセージの受信を肯定応答するためのみである場合
には、新しい情報を何も含まない。即ち、Ｍ、ＮＥＷは
、Ｍ、　　Ｓ、　　ｌＩＯ３がＩＮＦＯＣＰ）、Ｅ　　
ＰＯ，Ｓに等しくないか、】８８ ＳＴＢに等しくない場合に、真となる。

ＮＥＴＬ　Ｉ　ＳＴデータ構造９０６は、スパニングツ
リーーの少なくともブランチ内のネットワーク構成要素
及びネットワーク構成要素相互間接続を表す可変長構造
である。Ｎ　Ｅ′ｒ　ｔ、　ｒ　Ｓ　Ｔの各構成素子は
ｒＮＬＳＴ、素子」と表示される。

ＮＬＳＴ、ＣＯＭＰＬＥＴＥ９７０は、スパニングツリ
ーの根が識別され、そして不ノトワーク内の全てのスイ
ッチがその部分的ネットリストを根まで送ったときにの
み、ＴＲＵＥとなる。これば再構成プロセスのフェーズ
２の終わりに生ずる。

ＮＬＳＴ、ＮＮ９７２はＮＥＴＬＩＳＴ９０６にリスト
されるネットワーク構成要素（即ち、スイッチ及びホス
ト）の数である。

ＮＬＳＴ、Ｎ０ＤＥＩ、ｌ５Ｔ９７４はＮＥＴＬＩＳＴ
９０６内のネットワーク構成要素のリストであり、ＵＩ
Ｄ値によって分類される。ノードリスト９７４ばＮＮ個
の項目９７６を有す。ノードリスト内の各項目９７６は
、１つのネットワーク構成要素のＵＩＤ値、及び、前に
割り当てられている場合に、　８９ 前記構成要素のＳ　Ｈ○ＲＴＩＤを含む。

ＮＥＴＬ　Ｉ　ＳＴの残部はＮＮ個の接続リストである
。各接続リスト９７８は、１つのイ、ソトワーク構成要
素に対し、他のどのスイッチが第１のネットワーク構成
要素のポートの各々に接続されているかを識別する。新
しいＮＥＴＬＩＳＴが最初にスイッチによって発生され
るときに、ＮＥＴＬＩＳＴ９０６に含まれている唯一の
スイッチＩｉこのスイッチの直接隣のものであり、これ
はポート情報アレイ９０２によって識別される。部分的
ネツトリスト・が他のスイッチから受信されると、この
部分的ネットリスト内の情報はスイッチ自体のネツトリ
スト内の情報と併合され、より完全なネットリストを形
成する。

本実施例の接続リス１〜９７８内にはスイッチのみを表
示しであるが、本発明の他の実施例においてはホストに
対する接続を表示することもできる。

そこでホスト・に関する追加情報を用い、ネノトワク内
のスイッチ以外の全ての不ソ１−ワーク措或要素を含む
ネツトリストを開発することができる。

　９０ しかし、再構成プロセスの第３フエーズについて後で説
明するように、スイッチのみしか含んでいないネソトリ
ストば、スイッチが必要とする経路指定テーブルを発生
ずるのに十分である。

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

再構成プロセスのフェーズ１がネソ［・ワークの構成に
おるする変化を検出すると、この変化を検出したスイッ
チは次のアクションをとる（第２０図におけるボックス
１０００）。伺録６にば、再構成を開始するスイッチが
後に続（プロセスの疑似表示を記載しである。第１に、
これは、スイッチが伝送の過程にある全てのパケソＩ・
をクリアし、そして、このスイッチに接続されている全
てのボス１〜へ「スＩ・ノプフｌコー」信号を送るよう
にリンク装置をセットする。伝送の途中に割り込まれた
パケットは、再構成後に再伝送しなければならない。第
２に、再構成プログラムは、ＴＹＰＥ情報を除き、その
ポート情報アレイ９０２内の全ての情報をクリアする。

これは、このポートがスイッチまたはホストに接続され
ているか、またはＤ　ＩＥ　Ａ　＋１であるかのいずれ
であるかを示す。Ｔ　Ｙ　Ｉ）　Ｅ（直はスイッチによ
って局所的に発生され、従って、正確であると知られる
。

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

次に、再構成プログラムは、スイッチをスパニングツリ
ーの根ノートと定義する初期省略時ツリー位置ｃｐｏｓ
を七ソ１〜アップし、且つ、Ｃ３ＴＢを、スイッチが安
定でないということを示ずようにＦＡＵＳＥに等しく七
ソトアップする。次いで、このプログラムは、第１９図
に示すメッセージデータ構造９０４を用いて、このツリ
ー位置を報知する初期再構成メッセージをセットアップ
し、そしててこのメッセージ１００２をそのスイッチの
　９２ 全ての隣のものへ送る。

再構成プロセス最中に送られるメッセージはスイッチ相
互間で送られるのみである。ホストコンピュータは再構
成プロセスに参画しない。また、全ての再構成メッセー
ジに対して用いられる「汎用の所定ＳＣＰ不・ノドワー
クアドレス」がある。

この所定ＳＣＰアドレスは、メッセージがどのリンク上
で送られても、このリンクの他端にあるスイッチのＳＣ
Ｐヘメソメッセージ路指定するのに用いられる。

第２０図におジノる破線矢印は一つりのスイッチから他
のスイッチへのメッセージの伝送を示す。

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

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

エボソ３乞 先ず、受信スイッチは受信したエポック値を試験する。

Ｍ、ＥＰＯＣＨはそれ自体のエポック値を有す。受信し
たエポック値がそれ自体のエポック値よりも大きい場合
には、スイッチは回し除去処理を行い、次いでこのスイ
ッチは再構成プロセスを開始する。次いで、このスイッ
チはこの新しいエポック値をそれ自体のエポック値とし
て採用し、そして、それ０４本をスパニングツリーの机
と表示する初期ツリー位置をセットアップする。

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

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

　９４ 之世二１１１礼旧桧 −のスイッチがそのツリー位置を隣のスイッチに報知す
るとき、受信スイッチは、その隣のものによって報知さ
れたツリー位置がこのスイッチの現在ツリ一位置ｃｐｏ
ｓよりも「良い」かどうかを決めることが必要である。

受信した位置のほうが良い場合には、受信スイッチは、
送信スイッチをその「親」と識別し、及びメツセージを
受信したポートをその「アップリンク」と識別する。即
ち、比較プロセスは、事実上、受信スイッチが、これが
送信スイッチの１子」であるとしたら、ｃｐｏｓよりも
良いツリー位置を獲得するかどうかを決定することであ
る。

受信メッセージにおいて報知されるツリー位置はＭ、５
ＰＯ３と表示される。次いで、受信ツリー位置Ｍ、５Ｐ
Ｏ３を処理する際の第１のステップは「派生ツリー位置
」を計算することであり、この派生ツリー位置は、受信
スイッチが送信スイッチの子であるとした場合の受信ス
イッチのツリー位置である。派生ツリー位置は次のよう
に　９５ して計算される。

１゛、根　　　−Ｍ、５Ｉ）Ｏ３，租 Ｔ、深さ　　　　−Ｍ、５ＰＯ３，深さ＋ＩＴ、親　　
　　　−Ｍ、５ＵＩＤ Ｔ、アツプリンターＰ ここに、Ｐはメッセージを受信したポートである。

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

（１）　Ｔにおける根ＵＩＤ（即ち、Ｔ、根）がｃｐｏ
ｓにおける根ＵＩＤ　（即ち、ＣＰＯ３，根）よりも小
さい場合には、Ｔがより良いツリー位置である。ｃｐｏ
ｓ、根−丁、根である場合には、第２の比較試験を用い
る。

（２）Ｔの深さ（即ちＴ、深さ）がｃｐｏｓの深さ（即
ち、ｃｐｏｓ、深さ）よりも小さい場合には、Ｔがより
良いツリー位置である。ｃｐｏｓ。

深さくＴ、深さである場合には、第３の比較試　０　Ｇ 験を用いる。

（３）Ｔの親ＵＩＤ（即ち、Ｔ、親）がｃｐｏｓの親Ｕ
ＩＤ　（即ち、ｃｐｏｓ、親）よりも小さい場合には、
Ｔがより良いツリー位置である。

ｃｐｏｓ、親がＴ、親よりも小さい場合には、ｃｐｏｓ
がより良いツリー位置である。ｃｐｏｓ。

親−Ｔ、親である場合には、最後の比較試験を用いる。

（４）Ｔのアップリンク（即ち、Ｔ、アップリンク）が
ｃｐｏｓのリンク（即ち、ｃｐｏｓ、アップリンク）よ
りも小さい場合には、Ｔがより良いツリー位置である。

ｃｐｏｓ、アップリンクがＴ、アップリンクよりも小さ
い場合には、ｃｐｏｓがより良いツリー位置である。ｃ
ｐｏｓ、アソブリンクーＴ、アソブリンクである場合に
は、これら２つのツリー位置は同し、即ち、等しい。

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

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

他の重要な点は、各スイッチのツリー位置が再構成最中
に単調に改善されるということである。

即ち、スイッチのツリー位置は、その現在位置よりも良
いツリー位置を採用するのみであるから、決して悪くな
らない。

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

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

次に、メッセージ内の全ての情報をポート情報アレイ９
０２に予権する。

即ち、 ＩＮＦＯ（Ｐ）、Ｒ▽▽▽ＰＯ３＝Ｍ、Ｓ　　　ＰＯ３
ＩＮＦＯ▽▽ＣＰ）、　　ＮＥＷ　　　　＝Ｍ、　　Ｎ
ＥＷ次いで、受信スイッチが、報知されたツリー位置か
ら派生ツリー位置ｘｐｏｓを発生する。派生ツリー位置
を計算するための前述の説明を参照されたい。ｘｐｏｓ
がＰＯ３よりも良い場合にしま、ｘｐｏｓをｃｐｏｓの
新しい値として採用し、そしてＮＥＷと呼ばれる内部フ
ラグをＴＲＵＥにセットする。さもない場合には、ＮＥ
ＷをＰＡＬＳＨにセットする。ＮＥＷは、スイッチが新
しいツリー位置を採用したかどうかを示す。

未定性少丘員 次に、スイッチはこれが「安定」であるかどうかを評価
する。安定性は次のように定義される。

即ち、スイッチは、（１）スイッチの現在ツリー位置が
、スイッチの隣のものによって最後にエコーされた全て
の位置に整合するとき、及び（２）▽　９▽９ ▽▽０▽０ このスイッチの子である全ての隣のもの（即ち、このス
イッチが彼らの親であるとみなされる）が安定であると
きに、安定である。これらの基準を基礎とし、スイッチ
が安定であるならばＣ３ＴＢをＴＲＵＥにセットし、こ
れが安定でないならばＦＡＬＳＥにセットする。

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

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

セージを処理した後、該スイッチは、（１）スイッチの
ツリー位置ｃｐｏｓが変化したか、（２）スイッチの安
定性値Ｃ３ＴＢが変化したか、または（３）受信済みメ
ッセージが、新しい情報といわれるものを含んでおり（
Ｍ、ＮＥＷはＴＲＵＥであった）、従って肯定応答メッ
セージを要求する、という場合に、メッセージ送り出し
ルーチンを実行する。

メッセージ送り出しルーチンは、呼び出されると、スイ
ッチの現在ツリー位置（即ち、ｒＮＦ。

（Ｐ）、Ｅ　　ＰＯ３＃ＣＰＯ３）を知っていないかま
たは肯定応答してない全ての隣のものへ再構成メッセー
ジ（ボックス１▽０▽０▽６）を送る。肯定応答メッセ
ージは、最後のメツセージが送られた以後に新しい情報
を受信した該情報の送り出し元である全ての隣のものへ
送られる（即ち、ＩＮＦＯＣＰ）、ＮＥＷ＝ＴＲＵＥ）
。また、親ＩＮＦＯＣＰ）、Ｅ　　ＳＴＢによってエコ
ーされた最後の安定性値がスイッチの現在安定性値Ｃ３
ＴＢに等しくない場合、メツセージがスイッチの親へ送
ら▽０１ ▽Ｏ▽２ れる。

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

Ｍ、ＥＰＯＣＨ−現在Ｅ　Ｐ　ＯＣＨ Ｍ、Ｓ　　ＵＩＤ＝Ｓ Ｍ、Ｓ　　ＰＯ３＝ＣＰＯ３ Ｍ、Ｓ　　５ＴＢ＝Ｃ３ＴＢ そして、ｃｐｏｓまたはＣ３ＴＢのいずれかが、メツセ
ージが送られつつあるスイッチからのエコー済み値に整
合しない場合にはＭ、ＮＥＷがＴＲＩＢＥへ送られる。

これらの値を用い、メッセージＭをポートＰの隣接スイ
ッチへ送る。

メツセージが隣のスイッチへ送られた後、このスイッチ
に対するＩＮＦＯ（Ｐ）、ＮＥＷ値がＦＡＬＳＥにセソ
トされ、このスイッチからの最後のメッセージが肯定応
答されたということを示す。

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

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

メッセージ送り出しルーチンがタイマルーチンによって
送り出されるときにメッセージがまだ肯定応答されてい
ない場合には、メッセージを再度法　０４ り出し、メッセージタイマを再度始動させる。

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

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

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

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

スイッチが安定性を請求し、そしてまだこの請求をその
親へ送っていないと、これは部分的ネットリストを親ま
で送るためのルーチンを呼び出す。

前述したように、スイッチによって発生されたネットリ
ストは、このスイッチに既知となっている全てのスイッ
チのリストであり、スイッチ相互間の既知の全ての接続
のリストを含む。ＮＥＴＬＩＳＴＥ−タ構造９０６につ
いての前述の説明を参照されたい。

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

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

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

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

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

再構成フェーズ３ 経路指定テーブルの発生 根スイッチがその子から最後の部分的ネットリストを受
け取って（該スイッチはこれを前に受け取った他の部分
的ネットリストと併合して完全なネットリストを作る）
安定になると、該スイッチはＮＥＴＬＩＳＴデータ構造
９０６内のＣＯＭＰＬＥＴＥフラグ９７０をＴＲＵＥに
セットし、次いで次の手続きを行なう。

先ず、根スイッチは７ビノト５ＨＯＲＴ　　ＩＤをネッ
トワーク内の全てのスイッチに割り当てる。

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

ツリー　　のネツトリスト　　　し 次いで、前記スイッチは、完全リストを、その全てのス
パニングツリー上でリンクを下方へ、該スイッチが親と
なっている相手のスイッチへ送る（即ち、これに対して
、ＩＮＦＯＣＰ）、ＲＰＯ３，ＵＰＬＩＮＫ＝ＩＮＦＯ
ＣＰ）、ＲＰＯＲＴとなる）。第１７図に例示のネット
ワークにおいては、根７１０は完全リストをスイッチ７
１２．７１４．７１６．７１８及び７２０へ送る。

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

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

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

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

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

再構成の第３フエーズ中に、新しい経路指定テーブルが
ＳＣＰの正規メモリ内に発生される。この新しい経路指
定テーブルが完成すると、これは経路指定テーブルメモ
リ４２２内にコピーされる。

経路指定テーブルを計算するための開始点はフェーズ２
の始まりに発生されるリセット経路指定テーブルである
。

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

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

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

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

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

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

入ノノアソプリンタに対しては、ベクトル内の「１」に
セットされるマスクビットが、そのスイッチに接続され
る全てのスパニングツリーダウンリンクに対するもので
ある。

根ノードに対しては、同報通信パケットはダウンリンク
からのみ受け取られ、そして全ての根の　１４ スパニングツリーー上をリンクを下方へ再伝送される。

従って、全ての入力ダウンリンクに対しては、リンクベ
クトル内の「１」にセットされるマスクビットが、その
スイッチに接続される全てのスパニングツリーダウンリ
ンクに対するものである。

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

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

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

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

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

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

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

〔発明の効果〕

要約すると、本発明の再構成手続きは極めて早く、そし
て従来なかった次のような特性を有す。

即ち、ネットワーク内には、再構成プロセスが何時完了
するかを知っているスイッチがあり、及びこのスイッチ
は他の全てのスイッチに知らせる。

その結果、ネットワーク内の全てのスイッチは再構成プ
ロセスが何時完了するかを知る。本発明の実施例におい
ては、再構成のための最長時間は２００くり秒以下であ
ると考えられ、これば、このシステムの利用者に不利を
与えることのない十分に短い時間であると考えられる。

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

付 録 １゜ ０ＯＰ ＣＬＥＡＩＩ　　ＩＮＴ　　ＣＶ、　　ｌＮ’ｒ　　Ｐ
Ｃ，ＩＮＴ　　ＩＩＴＦＯＩ？　　Ｎ　　＝　　ｌ　　
Ｔｏ　　５ＤＥＬＡＶ　　（１旧ｔ、　ｔ、　ｌ　Ｓ　
Ｅ　ＣＯＮ　１１　）ＮＤ Ｉト （ＩＮＴ　　ＣＶ 、ＧＥ 、　０１７　。

ＩＮＴ　　ＩｉＣ 、ＧＥ ３） イ」 録 ） ＲＥＡＩ）ｌｉＷ、１．ＩＮＫ ＳＴＡＴＵＳ　　ＦＲＯ閃 １１八ＲＤＷＡＲＩＥ　　Ｐｏｔ、１．ＩＮＧ　　ＲＯ
ＩＪＴＩＮＩＥ　Ｎ　Ｄ　Ｉ　Ｆ ＲＥ′ｒ［ＩＲＮ ＮＤ 　２１ ＮＤ ＮＤ １１ＥＴＩＪＲＮ Ｅ、、ＮＤ 　２２ （＝Ｊ 録 ３゜ 変化状態フィルタル チン（） Ｒ１ミ八Ｄ　閃ＩＥ、ＬＩＮＫ　　ＳＴ／ＩＴＵｓ　　
ＦＲ叶　ＭｌミＳＳ八へＥＩミＸＣＩＩＡＮＧＥＲＯＩ
ＪＴＩＮＩミ １ミＮ＋） Ｎｒｌ イｊ 録 ４゜ イｊ 録 ５゜ 　２５ 付 録 　２６ ＩＥＮＩ） ＲＥＴＵＲＮ 付 録 ７゜ ） ＩＦ　ＮＯＴ　ＬＩＶＥ（ｐ） ＴＨＥＮ　　ＲＥＴＵＥＮ。

ＥＮＤ。

ＰＡＣＫＥＴＳ ＮＤ ｐｏｓ ＮＵＬ　　ＰＯ３ 現在位置をクリア ＮＤ ＲＥＰＬＹ　　ＲＱ ｍ、ＮＥＷ ＮＤ ＯＬＤ　　Ｃ３ＴＢ　　＝　　Ｃ３ＴＢＣ８ＴＢ　　＝
　　、Ｔｌ１ｌＪＥ。

ＦＯＲＰ　　＝　　ＡＬＩ、　ＡＬＩ”ＶＥ　　ＬＩＮ
Ｋ　　ＰＯＲＴＳ　　Ｃ０ＩＪＰＬＥＤ　　ＴＯＩＦ　
　Ｃ３ＴＢ　　＃　　ＯＬＤ　　Ｃ３ＴＢＲＥＰＬＹ　
　ＲＱ　　＝　　、ＴＲＵＥ。

ＮＤ Ｍ、Ｓ、　　ＰＯ３＝　　ＣＰＯ３ 閃、５．　　ＳＴＢ　　＝　　Ｃ３ＴＢＯＲＰ ＡＬＬ　　ＡＬＴＶＢ　　ＬＩＮＫ ＷＩＴＣＨ Ｍ、ＮＥＷ　　−、ＦＡＬＳＥ。

ＰＯＲＴＳ　　Ｃ０ＵＰＬＥＤ　　Ｔｏ　　＾　２９ ＮＤ ＮＤ ＮＤ ３０ 付 録 ８゜ ＮＤ ＥＮｆ）ＲＥＣＥＩＶＥ　　ＮＥＴＩ、■ＳＴ付 録 ９゜ ＣＯＭＰＵＴＥ　ＲＯＵＴＥ　ＴＡＢＬＥ　　（）スイ
ッチ開の合法的経路を先ず計算： 　３３ ＊＊ｌｌ ビット ＬＳＣ ＊＊同報通信経路指定エントリを計算：ＰＯＲＥＶＥＲ
Ｙ　ＰＲＥＤＥＦＩＮＥＤ　Ｂｌ？０ＡＤＣＡＳＴ　Ａ
ＤＩ）ｌｌ［ｓｓ＊＊根ノード以外の全てのものに対す
る取扱い：ＩＦＣＰＯ３，ＲＯＯＴＩＳ ３４ ＥＮＤ ＩミＮＤ Ｆ、ＬｓＦ。

＊＊根ノートに対する特別処理 Ｆ　ＯＲＰ　Ｒ［Ｄ　Ｅ　Ｐ　Ｉ　Ｎ　ＩＥ　Ｄ’　Ｎ
ＥＩＣＩＩＢＯＩＩＩＮＧ　　５ＷＩＴＣＩＩ　　５Ｃ
ＰＡ　Ｄ　１〕＋１１ｉ　Ｓ　Ｓ　’ ＥＮＤ　　ＣＯＭＰ［ＩＴＥ　　ＲＯＵ’ｒｌＥ　　Ｔ
／ＩＩＩＬＥ

【図面の簡単な説明】

第１Ａ図は従来の線形ローカルエリア不ソトワークのブ
ロック線図、第１．８図は従来のリング形ローカルエリ
ア不・ノドワークのブロック線図、第２図は本発明の小
型のメッシュ接続式ロカールエリアネットワークのゾＩ
−Ｊンク腺図、第３図るｊ本発明のロー力ルエリアネッ
トワークの一つのセクションの詳細なブロック線図、第
４図はメソソユ接続式Ｌ　Ａ　Ｎにおけるデッドロック
の例を示す説明図、第５図はメ・ッシュ接続式Ｌ　Ａ、
　Ｎにおけるアップリンク及びダウンリンクの概念図、
第６図しよデータパケット及び対応の）１コ一制御信号
の伝送を示すタイミング線図、第７図は一つのホストコ
ンピュータに対するネットワーク制御器のブロック線図
、第８図は本発明実施例において用いられるスイッチの
プロ・ノク線図、第９図は本発明実施例において用いら
れるクロスハースイッチのブロック線図、第１０図は互
いに接続されたネットワーク構成要素のチエインに対す
るデータフロー制御回路のブロック線図、第１１図はス
イッチ内の互いに接続された２つのリンク装置のブロッ
ク線図、第１２図はリンク装置の詳細なブロック線図、
第１３図は第８図のスイッチにおいて用いられるルータ
のブロック線図、第１４図はネットワークアドレスをル
ソクアノブアドレスの一部として用いて経路指定テーブ
ルからリンクヘクトルを選択するプロセスを説明するた
めの略図、第１５図は第１３図におけるルータの経路選
択機構のブロック線図、第１６図は第１３図のルータに
対するタイミング線図、第１７図はメッシュ式ネットワ
ークをスパニングツリーとして示す図、第１８図はネッ
トワーク再構成プロセスの第１フエーズの流れ図、第１
９図はネットワーク再構成プロセスの第　３７ ２及び第３のフェーズ中に用いられる主データ構造を示
す図、第２０図は不ソトワーク再構成プ１１セスの第２
及び第３のフェースの流れ図である。 １２０．１３２〜１３８：ホスト １２２：ネットワーク制御１１器 １２４．１２６，１４０，１４２：スイッチ１２８．１
３０，１４４．１４６：リンク２１０：非ブロック化ス
イッチ ２１２：クロスハースイッチ ２１６：スイッチ制御ブロセソサ ２１８：経路指定回路 ３０８．３３０：入力リンク装置 ３２２．３２６：出力リンク装置 ３５０：ＴＡＸＩ受信器チップ 　３８

Claims (1)

1. 【特許請求の範囲】 １、複数のホストを相互接続するためのメッシュ接続式
   ローカルエリアネットワークにおいて、前記ネットワー
   ク内のホスト相互間で複数のデータパケットを同時に経
   路指定するための複数のスイッチ手段を備え、各前記ス
   イッチ手段は、前記スイッチ手段を他のスイッチ手段及
   びホストに接続するための複数のポート手段と、前記ポ
   ート手段の選択された複数の対相互間でデータパケット
   を同時に接続及び経路指定するための非ブロック化クロ
   スバースイッチとを含み、前記ホスト及びスイッチ手段
   は共にネットワーク構成要素を構成しており、更に、 ネットワーク内の前記スイッチ手段及びホストを相互接
   続するための複数の二点間リンク手段を備えて成り、各
   前記二点間リンク手段は２つの前記ネットワーク構成要
   素間に通信チャネルを提供し、 各前記ポート手段は、前記ポート手段において前記スイ
   ッチ手段によって受信されたデータパケットを緩衝する
   ためのバッファ手段と、受信済みデータパケットを、前
   記受信済みデータパケットの終わりが受信される前に、
   前記非ブロック化クロスバスイッチを通して再伝送開始
   するためのカットスツー手段とを含んでいることを特徴
   とするメッシュ接続式ローカルエリアネットワーク。 ２、各データパケットは前記データパケットが送りつけ
   られつつある特定ホストを有し、 各スイッチ手段はネットワークを通る合法的データパケ
   ット伝送経路を所定の基準に従って定義するための経路
   指定手段を含み、前記経路指定手段は、受信済みデータ
   パケットが通過して再伝送させられ得る前記スイッチ手
   段のポート手段のサブセットを定義し、前記ポート手段
   のサブセットは、前記データパケットを受信する前記ス
   イッチのポート手段及び前記データパケットが送りつけ
   られつつあるホストの関数である請求項１記載のメッシ
   ュ接続式ローカルエリアネットワーク。 ３、複数のリンク手段はスパニングツリーリンクと複数
   の追加リンクとを含み、 相互接続された複数のスイッチ手段及び前記スパニング
   ツリーリンクは共にスパニングツリーを構成し、前記ス
   イッチ手段のうちの一つは前記スパニングツリーの根と
   呼ばれ、 各前記データパケットは前記データパケットが送りつけ
   られつつある特定ホストを有し、各前記スイッチ手段は
   ネットワークを通る合法的データパケット伝送経路を定
   義するための経路指定手段を含み、前記経路指定手段は
   ２つのスイッチ手段のうちのどれが前記スパニングツリ
   ー内のよりよい位置を有し及びどれがより悪い位置を有
   するかを定義するためのスイッチ配列手段を含んでおり
   、 前記経路指定手段は、ホストを前記スイッチに接続する
   各リンク手段をアップリンクと表示するため、前記スイ
   ッチを前記スパニングツリー内のより良い位置を持つ他
   のスイッチに接続する各リンク手段をアップリンクと表
   示するため、及び前記スイッチを前記スパニングツリー
   内のより悪い位置を持つ他のスイッチに接続する各リン
   ク手段をダウンリンクと表示するため、前記スイッチ配
   列手段に接続された構成手段を更に含んでおり、 前記経路指定手段は、前記アップリンクのいずれかに受
   信されたデータパケットを前記アップリンク及びダウの
   リンクのうちの選択されたものへ送るための手段と、前
   記ダウンリンクのいずれかに受信されたデータパケット
   を前記ダウンリンクのうちの選択されたものへ送るため
   の手段とを更に含んでおり、 もって、前記経路指定手段はメッシュ接続式ローカルエ
   リアネットワークを通るデータパケットのデッドロック
   なし経路指定を提供する請求項１記載のメッシュ接続式
   ローカルエリアネットワーク。 ４、複数のリンク手段はスパニングツリーリンクと複数
   の追加リンクとを含み、相互接続された複数のスイッチ
   手段及び前記スパニングツリーリンクは共にスパニング
   ツリーを構成し、前記スイッチ手段のうちの一つは前記
   スパニングツリーの根と呼ばれ、 前記スイッチ手段のうちのいずれか２つの特定されたも
   のに対し、前記特定スイッチのうちのどれが前記スパニ
   ングツリー内のよりよい位置を有し及びどれがより悪い
   位置を有するかを定義するためのスイッチ配列手段を更
   に含んでおり、 前記スイッチ手段のうちの２つを相互接続する各前記リ
   ンク手段は、前記スイッチ手段間で互いに反対の方向に
   データパケットを伝送するアップチャネル及びダウンチ
   ャネルを含み、前記アップチャネルはデータパケットを
   より悪い位置にあるスイッチ手段からよりよい位置にあ
   るスイッチ手段へ伝送するようになっており、各前記ス
   イッチ手段は、パケットをネットワークの構成要素のう
   ちの特定の一つへ送るための経路指定手段を含んでおり
   、もって、前記パケットをネットワークを通って伝送す
   る通路は、ゼロまたはそれ以上のダウンチャネルが後に
   続くゼロまたはそれ以上のアップチャネルを具備し、 もって、前記経路指定手段はメッシュ接続式ローカルエ
   リアネットワークを通るデータパケットのデッドロック
   なしの経路指定を提供する請求項１記載のメッシュ接続
   式ローカルエリアネットワーク。 ５、スイッチ手段は、ポート手段のうちのどれがデータ
   パケットを再伝送するのに利用可能であるかを表示する
   ためのポート状態手段を含んでおり、 経路指定手段は、受信済みデータパケットが通過して再
   伝送される得る前記スイッチ手段の前記ポート手段のサ
   ブセットを前記ポート状態手段と比較するため、及び前
   記受信済みデータパケットを、前記ポート手段のサブセ
   ットに含まれ且つデータパケットを再伝送するのに利用
   可能であるポート手段を通って経路指定するための経路
   選択手段を含んでいる請求項４記載のメッシュ接続式ロ
   ーカルエリアネットワーク。 ６、経路選択手段は、利用可能と表示されたポート手段
   のうちの一つが前記ポート手段のサブセットのうちの一
   つと整合するまで、受信済みデータパケットが通過して
   再伝送され得るスイッチ手段の前記ポート手段の前記サ
   ブセットをポート状態手段と周期的に比較し、次いで前
   記受信済みデータパケットを前記整合するポート手段を
   通って経路指定するための手段を含んでおり、 もって、前記スイッチ手段はデータパケットの低待ち時
   間再伝送を提供する請求項５記載のメッシュ接続式ロー
   カルエリアネットワーク。 ７、複数のリンク手段はスパニングツリーリンクと複数
   の追加リンクとを含んでおり、 相互接続された複数のスイッチ手段及び前記スパニング
   ツリーリンクは共にスパニングツリーを構成し、前記ス
   イッチ手段のうちの一つは前記スパニングツリーの根と
   呼ばれ、 データパケットは、ネットワーク内のホストのうちの特
   定された単一のものへ送られるデータパケットとネット
   ワーク内の全ての前記ホストへ送られるべき同報通信デ
   ータパケットとを含んでおり、 各前記スイッチ手段はネットワークを通る合法的データ
   パケット伝送経路を定義するための経路指定手段を含み
   、前記経路指定手段は、２つの同報通信パケット伝送経
   路を表示するための構成手段を含み、前記構成手段は、
   所定の基準に従い、前記スイッチ手段を前記スパニング
   ツリーの前記根に近いほうの他のスイッチ手段に接続す
   る前記スイッチ手段の１つのポート手段をアップリンク
   ポートと呼ぶための、及び前記スイッチ手段の他のもの
   のアップリンクポートに接続された各ポート手段をダウ
   ンリンクポートと表示するための手段を含んでおり、 各前記スイッチ手段の前記経路指定手段は、ネットワー
   クの前記根と呼ばれる前記スイッチ手段を除き、前記ア
   ップリンクポートによって受信された同報通信データパ
   ケットを全ての前記ダウンリンクポートへ経路指定する
   ための、及び前記アップリンクポート以外の何らかの前
   記ポート手段によって受信された同報通信データパケッ
   トを前記アップリンクポートへ経路指定するための経路
   選択手段を更に含んでいる請求項１記載のメッシュ接続
   式ローカルエリアネットワーク。 ８、ネットワークの根と呼ばれるスイッチ手段の経路指
   定手段は、前記スイッチ手段によって受信された全ての
   同報通信データパケットを全てのダウンリンクポートへ
   経路指定するための経路選択手段を更に含んでいる請求
   項７記載のメッシュ接続式ローカルエリアネットワーク
   。 ９、各スイッチ手段は、受信された同報通信データパケ
   ットを全てのダウンリンクポートを通って同時に再伝送
   するための手段を含んでいる請求項７記載のメッシュ接
   続式ローカルエリアネットワーク。 １０、データパケットは、ネットワーク内のホストのう
   ちの単一の特定のものへ送られるデータパケットと、ネ
   ットワーク内の全ての前記ホストへ送られるべき同報通
   信データパケットとを含み、前記同報通信データパケッ
   トは所定の最大大きさを有しており、 バッファ手段は、前記所定の最大大きさの同報通信デー
   タパケット全体を記憶するための十分以上の余地、及び
   何時前記バッファ手段が同報通信データパケット全体を
   受け取るのに十分な余地を持つかを示すための手段を有
   しており、ポート手段は、前記ポート手段に接続された
   ネットワーク構成要素へフロー制御信号を送るために前
   記バッファ手段に接続されたフロー制御手段を含み、前
   記フロー制御信号は、前記ポート手段へデータパケット
   を伝送することを停止することを前記ネットワーク構成
   要素に要求するストップフロー信号と、前記ポート手段
   へデータパケットを送ることを再開することを前記ネッ
   トワーク構成要素に許すスタートフロー信号とを含み、
   前記フロー制御手段は、前記バッファ手段が同報通信デ
   ータパケット全体を受け取るのに十分な余地を有すると
   きにのみスタートフロー信号を送るための手段を含んで
   いる請求項１記載のメッシュ接続式ローカルエリアネッ
   トワーク。 １１、ポート手段は、前記ポート手段に接続されたネッ
   トワーク構成要素によって送られるフロー制御信号を受
   信するための手段と、データパケットが同報通信パケッ
   トでない限り、ストップフロー信号が前記ネットワーク
   構成要素から受信されるときにデータパケットの伝送を
   停止させるための手段とを含んでいる請求項１記載のメ
   ッシュ接続式ローカルエリアネットワーク。 １２、複数のホストを相互接続するのためのメッシュ接
   続式ローカルエリアネットワークにおいて、前記ネット
   ワーク内のホスト相互間で複数のデータパケットを同時
   に経路指定するための複数のスイッチ手段を備え、各前
   記スイッチ手段は、前記スイッチ手段を他のスイッチ手
   段及びホストに接続するための複数のポート手段と、前
   記ポート手段の選択された複数の対相互間でデータパケ
   ットを同時に接続及び経路指定するための非ブロック化
   クロスバースイッチとを含み、前記ホスト及びスイッチ
   手段は共にネットワーク構成要素を構成しており、更に
   、 ネットワーク内の前記スイッチ手段及びホストを相互接
   続するための複数の二点間リンク手段を備えて成り、各
   前記二点間リンク手段は２つの前記ネットワーク構成要
   素間に通信チャネルを提供し、 各前記データパケットは前記データパケットが送りつけ
   られつつある特定ホストを有し、各前記スイッチ手段は
   ネットワークを通る合法的データパケット伝送経路を所
   定の基準に従って定義するための経路指定手段を含み、
   前記経路指定手段は、受信済みデータパケットが通過し
   て再伝送させられ得る前記スイッチ手段の前記ポート手
   段のサブセットを定義し、前記ポート手段のサブセット
   は、前記データパケットを受信する前記スイッチのポー
   ト手段及び前記データパケットが送りつけられつつある
   ホストの関数であるメッシュ接続式ローカルエリアネッ
   トワーク。 １３、複数のリンク手段はスパニングツリーリンクと複
   数の追加リンクとを含み、 相互接続された複数のスイッチ手段及び前記スパニング
   ツリーリンクは共にスパニングツリーを構成し、前記ス
   イッチ手段のうちの一つは前記スパニングツリーの根と
   呼ばれ、 各データパケットは前記データパケットが送りつけられ
   つつある特定ホストを有し、 経路指定手段は、所定の基準に従い、前記スイッチ手段
   を前記スパニングツリーの前記根に近いほうの他のスイ
   ッチ手段に接続する前記スイッチ手段の各ポート手段を
   アップポートと表示するための、及び前記スイッチ手段
   の他の全てのポート手段をダウンポートと表示するため
   の手段を含んでおり、 前記経路指定手段は、受信済みデータパケットが通過し
   て再伝送され得る前記スイッチ手段の前記ポート手段の
   サブセットを定義するための経路指定テーブル手段を更
   に含み、前記ポート手段のサブセットは、前記データパ
   ケットを受信する前記スイッチ手段のポート手段及び前
   記データパケットが送りつけられつつあるホストの関数
   であり、前記ポート手段のサブセットは、前記データパ
   ケットを受信する前記ポート手段がダウンポートと表示
   されるときに前記構成手段によってダウンポートと表示
   される前記ポート手段のうちの選択されたもののみを含
   み、もって、前記経路指定手段はメッシュ接続式ローカ
   ルエリアネットワークを通るデータパケットのデッドロ
   ックなしの経路指定を提供する請求項１２記載のメッシ
   ュ接続式ローカルエリアネットワーク。 １４、複数のリンク手段はスパニングツリーリンクと複
   数の追加リンクとを含んでおり、 相互接続された複数のスイッチ手段及び前記スパニング
   ツリーリンクは共にスパニングツリーを構成し、前記ス
   イッチ手段のうちの一つは前記スパニングツリーの根と
   呼ばれ、 前記スイッチ手段のうちのいずれか２つの特定されたも
   のに対し、前記特定スイッチのうちのどれが前記スパニ
   ングツリー内のよりよい位置を有し及びどれがより悪い
   位置を有するかを定義するためのスイッチ配列手段を更
   に含んでおり、 前記スイッチ手段のうちの２つを相互接続する各前記リ
   ンク手段は、前記スイッチ手段間で互いに反対の方向に
   データパケットを伝送するアップチャネル及びダウンチ
   ャネルを含み、前記アップチャネルはデータパケットを
   より悪い位置にあるスイッチ手段からよりよい位置にあ
   るスイッチ手段へ伝送するようになっており、各前記ス
   イッチ手段はパケットをネットワーク構成要素の特定の
   ものへ送るための経路指定手段を含み、もって、前記パ
   ケットがネットワークを通って伝送される通路は、ゼロ
   またはそれ以上のダウンチャネルが後に続くゼロまたは
   それ以上のアップチャネルを具備し、 もって、前記経路指定手段はメッシュ接続式ローカルエ
   リアネットワークを通るデータパケットのデッドロック
   なしの経路指定を提供する請求項１３記載のメッシュ接
   続式ローカルエリアネットワーク。 １５、スイッチ手段は、ポート手段のうちのどれがデー
   タパケットを再伝送するのに利用可能であるかを表示す
   るためのポート状態手段を含んでおり、 経路指定手段は、受信済みデータパケットが通過して再
   伝送される得る前記スイッチ手段の前記ポート手段のサ
   ブセットを前記ポート状態手段と比較するため、及び前
   記受信済みデータパケットを、前記ポート手段のサブセ
   ットに含まれ且つデータパケットを再伝送するのに利用
   可能であるポート手段を通って経路指定するための経路
   選択手段を含んでいる請求項１３記載のメッシュ接続式
   ローカルエリアネットワーク。 １６、経路選択手段は、利用可能と表示されたポート手
   段のうちの一つが前記ポート手段のサブセットのうちの
   一つと整合するまで、受信済みデータパケットが通過し
   て再伝送され得るスイッチ手段の前記ポート手段の前記
   サブセットをポート状態手段と周期的に比較し、次いで
   前記受信済みデータパケットを前記整合するポート手段
   を通って経路指定するための手段を含んでおり、 もって、前記スイッチ手段はデータパケットの低待ち時
   間再伝送を提供する請求項１５記載のメッシュ接続式ロ
   ーカルエリアネットワーク。 １７、複数のリンク手段はスパニングツリーリンクと複
   数の追加リンクとを含んでおり、 相互接続された複数のスイッチ手段及び前記スパニング
   ツリーリンクは共にスパニングツリーを構成し、前記ス
   イッチ手段のうちの一つは前記スパニングツリーの根と
   呼ばれ、 データパケットは、ネットワーク内のホストのうちの特
   定された単一のものへ送られるデータパケット及びネッ
   トワーク内の全ての前記ホストへ送られるべき同報通信
   データパケットを含んでおり、 経路指定手段は、２つの同報通信パケット伝送経路を表
   示するための構成手段を含み、前記構成手段は、所定の
   基準に従い、前記スイッチ手段を前記スパニングツリー
   の前記根に近いほうの他のスイッチ手段に接続する前記
   スイッチ手段の一つのポート手段をアップリンクポート
   と呼ぶための、及び前記スイッチ手段の他のもののアッ
   プリンクポートに接続された各ポート手段をダウンリン
   クポートと表示するための手段を含んでおり、 各前記スイッチ手段の前記経路指定手段は、ネットワー
   クの前記根と呼ばれる前記スイッチ手段を除き、前記ア
   ップリンクポートによって受信された同報通信データパ
   ケットを全ての前記ダウンリンクポートへ経路指定する
   ための、及び前記アップリンクポート以外の何らかの前
   記ポート手段によって受信された同報通信データパケッ
   トを前記アップリンクポートへ経路指定するための経路
   選択手段を更に含んでいる請求項１２記載のメッシュ接
   続式ローカルエリアネットワーク。 １８、ネットワークの根と呼ばれるスイッチ手段の経路
   指定手段は、前記スイッチ手段によって受信された全て
   の同報通信データパケットを全てのダウンリンクポート
   へ経路指定するための経路選択手段を更に含んでいる請
   求項１７記載のメッシュ接続式ローカルエリアネットワ
   ーク。 １９、各スイッチ手段は、受信された同報通信データパ
   ケットを全てのダウンリンクポートを通って同時に再伝
   送するための手段を含んでいる請求項１８記載のメッシ
   ュ接続式ローカルエリアネットワーク。 ２０、複数のホストを相互接続するためのメッシュ接続
   式ローカルエリアネットワークにおいて、前記ネットワ
   ーク内のホスト相互間で複数のデータパケットを同時に
   経路指定するための複数のスイッチ手段を備え、各前記
   スイッチ手段は、前記スイッチ手段を他のスイッチ手段
   及びホストに接続するための複数のポート手段と、前記
   ポート手段の選択された複数の対相互間でデータパケッ
   トを同時に接続及び経路指定するための非ブロック化ク
   ロスバースイッチとを含み、更に、 ネットワーク内の前記スイッチ手段及びホストを相互接
   続するための複数の二点間リンク手段を備えて成り、各
   前記二点間リンク手段は、前記ネットワーク内のスイッ
   チ手段及び前記ネットワーク内のホストから成るセット
   から選択された２つのネットワーク構成要素間に通信チ
   ャネルを提供し、 前記複数のリンク手段はスパニングツリーリンクと複数
   の追加リンクとを含んでおり、 前記相互接続された複数のスイッチ手段及び前記スパツ
   リーリンクは共にスパニングツリーを構成し、前記スイ
   ッチ手段のうちの一つは前記スパニングツリーの根と呼
   ばれ、 各前記データパケットは前記データパケットが送りつけ
   られつつある特定ホストを有し、各前記スイッチ手段は
   ネットワークを通る合法的データパケット伝送経路を定
   義するための経路指定手段を含み、前記経路指定手段は
   、所定の基準に従い、前記スイッチ手段を前記スパニン
   グツリーの前記根に近いほうの他のスイッチ手段に接続
   する前記スイッチ手段の各ポート手段をアップポートと
   表示するための、及び前記スイッチ手段の他の全てのポ
   ート手段をダウンポートと表示するための構成手段を含
   んでおり、 前記経路指定手段は、受信済みデータパケットが通過し
   て再伝送され得る前記スイッチ手段の前記ポート手段の
   サブセットを定義するための経路指定テーブル手段を更
   に含み、前記ポート手段のサブセットは、前記データパ
   ケットを受信する前記スイッチ手段のポート手段及び前
   記データパケットが送りつけられつつあるホストの関数
   であり、前記ポート手段のサブセットは、前記データパ
   ケットを受信する前記ポート手段がダウンポートと表示
   されるときに前記構成手段によってダウンポートと表示
   される前記ポート手段のうちの選択されたもののみを含
   み、もって、前記経路指定手段はメッシュ接続式ローカ
   ルエリアネットワークを通るデータパケットのデッドロ
   ックなしの経路指定を提供するメッシュ接続式ローカル
   エリアネットワーク。 ２１、各データパケットはネットワークアドレスを表示
   するためのアドレス手段を有し、 経路指定テーブル手段は、複数の所定のネットワークア
   ドレスの各々に対して、受信済みデータパケットが通過
   して再伝送され得るスイッチ手段のポート手段のサブセ
   ットを表示するための手段を含んでおり、 前記経路指定手段は、前記所定のネットワークアドレス
   の一つとは別のネットワークアドレスを表示するアドレ
   ス手段を有するデータパケットを廃棄するための手段を
   更に含んでおり、もって、不法のまたは転化したネット
   ワークアドレス値を持つデータパケットが廃棄される請
   求項２０記載のメッシュ接続式ローカルエリアネットワ
   ーク。 ２２、複数のホストを相互接続するためのメッシュ接続
   式ローカルエリアネットワークにおいて、前記ネットワ
   ーク内のホスト相互間で複数のデータパケットを同時に
   経路指定するための複数のスイッチ手段を備え、各前記
   スイッチ手段は、前記スイッチ手段を他のスイッチ手段
   及びホストに接続するための複数のポート手段と、前記
   ポート手段の選択された複数の対相互間でデータパケッ
   トを同時に接続及び経路指定するための非ブロック化ク
   ロスバースイッチとを含んでおり、更に、 ネットワーク内の前記スイッチ手段及びホストを相互接
   続するための複数の二点間リンク手段を備え、各前記二
   点間リンク手段は、前記ネットワーク内のスイッチ手段
   と前記ネットワーク内のホストとから成るセットから選
   択された２つのネットワーク構成要素間に双方向通信チ
   ャネルを提供し、前記複数のリンク手段はスパニングツ
   リーリンクと複数の追加リンクとを含んでおり、 前記相互接続された複数のスイッチ手段及び前記スパニ
   ングツリーリンクは共にスパニングツリーを構成し、前
   記スイッチ手段のうちの一つは前記スパニングツリーの
   根と呼ばれ、更に、各前記リンク手段にアップ方向及び
   ダウン方向を割り当てるための手段と、 データパケットを第１の特定ネットワーク構成要素から
   第２の特定ネットワーク構成要素へ伝送するための経路
   指定手段とを備えて成り、前記経路指定手段は、前記デ
   ータパケットを少なくとも１つの前記リンク手段上で前
   記アップ方向に伝送し、次いで前記データパケットを少
   なくとも１つの前記リンク手段上で前記ダウン方向に、
   前記第２の特定ネットワーク構成要素へ伝送するための
   手段を含んでおり、 もって、前記経路指定手段は前記メッシュ接続式ローカ
   ルエリアネットワークを通るデータパケットのデッドロ
   ックなしの経路指定を提供することを特徴とするメッシ
   ュ接続式ローカルエリアネットワーク。 ２３、データパケットは、ネットワーク内のホストのう
   ちの特定の単一のものへ送られるデータパケットと、ネ
   ットワーク内の全ての前記ホストへ送られるべき同報通
   信データパケットとを含んでおり、前記同報通信データ
   パケットは所定の最大大きさを有し、 各ポート手段は前記ポート手段においてスイッチ手段に
   よって受信されるデータパケットを緩衝するためのバッ
   ファ手段を含み、前記バッファ手段は、前記所定の最大
   大きさの同報通信データパケット全体を記憶するのに十
   分以上の余地と、何時前記バッファ手段が同報通信デー
   タパケット全体を受信するのに十分な余地を持つかを示
   すための手段とを有しており、 前記ポート手段は、前記ポート手段に接続されたネット
   ワーク構成要素へフロー制御信号を送るため、前記バッ
   ファ手段に接続されたフロー制御手段を含み、前記フロ
   ー制御信号は、前記ポート手段へデータパケットを伝送
   することを停止することを前記ネットワーク構成要素に
   要求するストップフロー信号と、前記ポート手段へデー
   タパケットを送ることを再開することを前記ネットワー
   ク構成要素に許すスタートフロー信号とを含み、前記フ
   ロー制御手段は、前記バッファ手段が同報通信データパ
   ケット全体を受信するのに十分な余地を持つときにのみ
   スタートフロー信号を送るための手段を含んでいる請求
   項２２記載のメッシュ接続式ローカルエリアネットワー
   ク。 ２４、ポート手段は、前記ポート手段に接続されたネッ
   トワーク構成要素によって送られるフロー制御信号を受
   信するための手段と、データパケットが同報通信パケッ
   トでない限り、ストップフロー信号が前記ネットワーク
   構成要素から受信されるときに前記データパケットの伝
   送を停止するための手段とを含んでいる請求項２３記載
   のメッシュ接続式ローカルエリアネットワーク。 ２５、複数のホストを相互接続するのためのメッシュ接
   続式ローカルエリアネットワークにおいて、前記ネット
   ワーク内のホスト相互間で複数のデータパケットを同時
   に経路指定するための複数のスイッチ手段を備え、各前
   記スイッチ手段は、前記スイッチ手段を他のスイッチ手
   段及びホストに接続するための複数のポート手段と、前
   記ポート手段の選択された複数の対相互間でデータパケ
   ットを同時に接続及び経路指定するための非ブロック化
   クロスバースイッチとを含み、前記ホスト及びスイッチ
   手段は共にネットワーク構成要素を構成しており、更に
   、 ネットワーク内の前記スイッチ手段及びホストを相互接
   続するための複数の二点間リンク手段を備えて成り、各
   前記二点間リンク手段は２つの前記ネットワーク構成要
   素間に通信チャネルを提供し、 前記複数のリンク手段はスパニングツリーリンクと複数
   の追加リンクとを含んでおり、 前記相互接続された複数のスイッチ手段及び前記スパニ
   ングツリーリンクは共にスパニングツリーを構成し、前
   記スイッチ手段のうちの一つは前記スパニングツリーの
   根と呼ばれ、 前記データパケットは、ネットワーク内の前記ホストの
   うちの特定された単一のものへ送られるデータパケット
   及びネットワーク内の全ての前記ホストへ送られるべき
   同報通信データパケットを含んでおり、 各前記スイッチ手段はネットワークを通る合法的データ
   パケット伝送経路を所定の基準に従って定義するための
   経路指定手段を含み、前記経路指定手段は、所定の基準
   に従い、前記スイッチ手段を前記スパニングツリーの前
   記根に近いほうの他のスイッチ手段に接続する前記スイ
   ッチ手段の一つのポート手段をアップリンクポートと呼
   ぶための、及び前記スイッチ手段の他のもののアップリ
   ンクポートに接続された各ポート手段をダウンリンクポ
   ートと表示するための手段を含んでおり、 各前記スイッチ手段の前記経路指定手段は、ネットワー
   クの前記根と呼ばれる前記スイッチ手段を除き、前記ア
   ップリンクポートによって受信された同報通信データパ
   ケットを全ての前記ダウンリンクポートへ経路指定する
   ための、及び前記アップリンクポート以外の何らかの前
   記ポート手段によって受信された同報通信データパケッ
   トを前記アップリンクポートへ経路指定するための経路
   選択手段を更に含んでいるメッシュ接続式ローカルエリ
   アネットワーク。 ２６、ネットワークの根と呼ばれるスイッチ手段の経路
   指定手段は、前記スイッチ手段によって受信された全て
   の同報通信データパケットを全てのダウンリンクポート
   へ経路指定するための経路選択手段を更に含んでいる請
   求項２５記載のメッシュ接続式ローカルエリアネットワ
   ーク。 ２７、各スイッチ手段は、受信済み同報通信データパケ
   ットを全てのダウンリンクポートを通して同時に再伝送
   するための手段を含んでいる請求項２６記載のメッシュ
   接続式ローカルエリアネットワーク。 ２８、複数のホストを相互接続するためのメッシュ接続
   式ローカルエリアネットワークにおいて、前記ネットワ
   ーク内のホスト相互間で複数のデータパケットを同時に
   経路指定するための複数のスイッチ手段を備え、前記ホ
   スト及びスイッチ手段は共にネットワーク構成要素を構
   成しており、更に、 ネットワーク内の前記スイッチ手段及びホストを相互接
   続するための複数の二点間リンク手段を備えて成り、各
   前記二点間リンク手段は２つの前記ネットワーク構成要
   素間に通信チャネルを提供し、 前記リンク手段によって互いに接続されたスイッチ手段
   は隣接スイッチ手段を構成し、 前記複数のリンク手段はスパニングツリーリンクと複数
   の追加リンクとを含んでおり、 前記相互接続された複数のスイッチ手段及び前記スパニ
   ングツリーリンクは共にスパニングツリーを構成し、前
   記スイッチ手段のうちの一つは前記スパニングツリーの
   根と呼ばれ、 各前記スイッチ手段は前記スパニングツリー内の前記ス
   イッチ手段の位置を決定するための再構成手段を含み、
   前記再構成手段は、 前記スパニングツリー内のツリー位置を表示するための
   位置表示手段と、 前記ツリー位置に付属のエポック値を表示するためのエ
   ポック表示手段と、 前記ネットワークの構成の変化を検出するための構成変
   化検出手段とを含み、前記検出手段は、前記スイッチ手
   段と前記ネットワーク構成要素の他の一つとの間の新し
   い接続の存在を検出するための、及び前記スイッチ手段
   と前記ネットワーク構成要素の他の一つとの間の接続の
   破断を検出するための手段を含んでおり、 前記構成変化検出手段は、前記ネットワークの構成の変
   化が検出されるときに前記エポック値をインクリメント
   するための手段を含んでおり、更に、 前記スイッチ手段に隣接する各スイッチ手段へ構成メッ
   セージを送るため、前記位置表示手段に接続されたメッ
   セージ送信手段を含み、前記構成メッセージは前記ツリ
   ー位置と前記エポック値とを含んでおり、更に、 各受信済み構成メッセージ内のツリー位置の関数である
   派生ツリー位置を発生するため、及び前記派生ツリー位
   置が前記位置表示手段によって表示されたツリー位置よ
   りも良い場合に前記位置表示手段によって表示されたツ
   リー位置を前記派生ツリー位置と置き換えるため、隣接
   スイッチ手段から構成メッセージを受信するためのメッ
   セージ受信手段を含んでおり、 前記メッセージ受信手段は、前記受信済み構成メッセー
   ジ内の前記エポック値が前記エポック表示手段によって
   表示されたエポック値よりも大きい場合に前記ツリー位
   置を前記派生ツリー位置と置き換え且つ前記エポック値
   を前記受信済み構成メッセージ内のエポック値と置き換
   えるための手段を含んでおり、 前記メッセージ送信手段は、前記位置表示手段によって
   表示された前記ツリー位置が前記派生ツリー位置によっ
   て置き換えられるときに前記隣接スイッチ手段へ構成メ
   ッセージを送るための手段を含んでおり、 もって、ネットワークの構成の変化が、自動的に、前記
   ネットワーク内のスイッチ手段をして前記スパニングツ
   リー内のそれらの関係するツリー位置を再決定せしめる
   ようになっていることを特徴とするメッシュ接続式ロー
   カルエリアネットワーク。 ２９、複数のホストを相互接続するためのメッシュ接続
   式ローカルエリアネットワークにおいて、前記ネットワ
   ーク内のホスト相互間で複数のデータパケットを同時に
   経路指定するための複数のスイッチ手段を備え、前記ホ
   スト及びスイッチ手段は共にネットワーク構成要素を構
   成しており、更に、 ネットワーク内の前記スイッチ手段及びホストを相互接
   続するための複数の二点間リンク手段を備えて成り、各
   前記二点間リンク手段は２つの前記ネットワーク構成要
   素間に通信チャネルを提供し、 前記複数のリンク手段はスパニングツリーリンクと複数
   の追加リンクとを含んでおり、 前記相互接続された複数のスイッチ手段及び前記スパニ
   ングツリーリンクは共にスパニングツリーを構成し、前
   記スイッチ手段のうちの一つは前記スパニングツリーの
   根と呼ばれ、 各前記スイッチ手段は前記スパニングツリー内の前記ス
   イッチ手段の位置を決定するための再構成手段を含み、
   前記再構成手段は、 前記スパニングツリー内のツリー位置を表示するための
   位置表示手段と、 前記ツリー位置に付属のエポック値を表示するためのエ
   ポック表示手段と、 前記ネットワークの構成の変化を検出するための構成変
   化検出手段とを含み、前記検出手段は、前記スイッチ手
   段と前記ネットワーク構成要素の他の一つとの間の新し
   い接続の存在を検出するための、及び前記スイッチ手段
   と前記ネットワーク構成要素の他の一つとの間の接続の
   破断を検出するための手段を含んでおり、 前記構成変化検出手段は、前記ネットワークの構成の変
   化が検出されるときに前記エポック値をインクリメント
   するための手段を含んでおり、更に、 前記スイッチ手段に隣接する各スイッチ手段へ構成メッ
   セージを送るため、前記位置表示手段に接続されたメッ
   セージ送信手段を含み、前記構成メッセージは前記ツリ
   ー位置と前記エポック値とを含んでおり、更に、 各受信済み構成メッセージ内のツリー位置の関数である
   派生ツリー位置を発生するため、及び前記派生ツリー位
   置が前記位置表示手段によって表示されたツリー位置よ
   りも良い場合に前記位置表示手段によって表示されたツ
   リー位置を前記派生ツリー位置と置き換えるため、隣接
   スイッチ手段から構成メッセージを受信するためのメッ
   セージ受信手段を含んでおり、 前記メッセージ受信手段は、前記受信済み構成メッセー
   ジ内の前記エポック値が前記エポック表示手段によって
   表示されたエポック値よりも大きい場合に前記ツリー位
   置を前記派生ツリー位置と置き換え且つ前記エポック値
   を前記受信済み構成メッセージ内のエポック値と置き換
   えるための手段を含んでおり、 前記メッセージ送信手段は、前記位置表示手段によって
   表示された前記ツリー位置が前記派生ツリー位置によっ
   て置き換えられるときに前記隣接スイッチ手段へ構成メ
   ッセージを送るための手段を含んでおり、 前記構成変化検出手段は、前記エポック値が所定のあふ
   れ値までインクリメントされるときにエポック値あふれ
   を検出するため、並びに、エポック値あふれが検出され
   るときに所定の自滅協定メッセージを前記隣接スイッチ
   手段へ送るため及び前記エポック値を所定の初期値にリ
   セットするための自滅協定手段を含んでおり、前記メッ
   セージ受信手段は、前記エポック値を前記所定の初期値
   にリセットし、前記所定の自滅協定メッセージを前記隣
   接スイッチ手段へ送り、所定の時間にわたって前記隣接
   スイッチ手段から受信した全ての後続の自滅協定メッセ
   ージを無視し、次いで構成メッセージを前記隣接スイッ
   チ手段へ送ることによって、前記自滅協定メッセージの
   受信に応答するための手段を含んでおり、 もって、ネットワークの構成の変化が、自動的に、前記
   ネットワーク内のスイッチ手段をして前記スパニングツ
   リー内のそれらの関係するツリー位置を再決定せしめる
   ようになっていることを特徴とするメッシュ接続式ロー
   カルエリアネットワーク。