(57)【要約】階層的な複数のレベルの構造に相互接続された、複数のノード（１０２，１０４，１０６）を含むネットワークまたは相互接続構造。各々のノードのレベルは、前記構造内のノードの位置により決定され、データ・メッセージは、ノードからノードへ、起点のレベルから目的のレベルへ移動する。前記相互接続構造内の各々のノードは、他のノードからの入力ポートで、データ・メッセージ（１０８，１１０）を同時に受信することができ、受信ノードは、その出力ポートを通じて、各受信データ・メッセージを、相互接続構造内の別々ノード、受信ノードのレベルの下位の１以上のレベルへと転送することができる。
2004511992.tif 000002
【特許請求の範囲】
【請求項１】
相互接続構造であって、
区別可能なノードＡおよびノードＥを含む複数の相互接続されたノード、
前記相互接続されたノードの間を選択的にデータを経路制御する、前記ノードに関連付けられた経路制御ロジック、および
前記経路制御ロジックの一部に含まれ、前記ノードＥを通過するデータの経路制御に関する情報を使用して、前記ノードＡを通過してデータを発送する、前記ノードＡに関連付けられたロジック、を備え、
前記ノードＡは、複数のデータ入力ポート、複数のデータ出力ポートおよび複数のコントロール信号入力ポートを有し、
前記ノードＥは、複数のデータ入力ポート、複数のデータ出力ポートおよび複数のコントロール信号出力ポートを有し、および
前記ノードＡおよびＥが、ノードＡが前記ノードＥにデータを発送できず、前記ノードＥが前記ノードＡにデータを発送できず、かつ前記ノードＡおよび前記ノードＥの両方から発送されるデータを有するノードが相互接続内に存在しないように位置付けられた構造。
【請求項２】
相互接続された複数のノードが前記ノードＡおよびＥとは別のノードＦを含み、前記ノードＦは複数のデータ入力ポート、複数のデータ出力ポートおよび複数のコントロール信号出力ポートを有し、
前記ノードＡおよびＦが、前記ノードＡが前記ノードＦにデータを発送できず、前記ノードＦが前記ノードＡを通過してデータを発送できず、前記ノードＡおよび前記ノードＦの両方から発送されるデータを受信することができるノードが、相互接続内に存在しないように位置付けられ、および
かつ前記Ａに関連付けられたロジックが、前記ノードＦを通過するデータの経路制御に関する情報を使用して、前記ノードＡを通過してデータを発送する、請求項１に記載の相互接続構造。
【請求項３】
相互接続された複数のノードが前記ノードＡ、ＥおよびＦとは別のノードＢを含み、前記ノードＢは複数のデータ入力ポート、複数のデータ出力ポートおよび複数のコントロール信号出力ポートを有し、および
経路制御ロジックの一部として含まれノードＢに関連付けられたロジックが、前記ノードＡにコントロール信号ｚを送信することができ、前記コントロール信号ｚは、前記ノードＢ、ＦおよびＥを通過する経路制御の可能性に関する情報を含み、前記ノードＡを通過するデータを発送するために前記ノードＡに関連付けられた前記ロジックが、前記ノードＢ、ＦおよびＥを通過するデータの経路制御に関する情報の少なくとも一部分に依存する、請求項２に記載の相互接続構造。
【請求項４】
相互接続された複数のノードが前記ノードＡ、Ｂ、ＥおよびＦとは別のノードＣを含み、前記ノードＣが複数のデータ入力ポートおよび複数のデータ出力ポートを含み、
前記ノードＢが前記ノードＣにメッセージを送信し、
前記ノードＥが前記ノードＢにコントロール信号ｙを送信し、
前記ノードＦが前記ノードＢにコントロール信号ｘを送信し、
前記ノードＢに関連付けられた前記ロジックが、前記コントロール信号ｘ、ｙに基づいて、前記ノードＡに前記ノン・ブロッキング・コントロール信号ｚを送信し、
前記ノードＡが前記ノードＣにメッセージを送信し、および
前記ノードＣが、その入力ポート全てに同時にメッセージを受信する、ノード請求項３に記載の相互接続構造。
【請求項５】
相互接続構造であって
区別可能なノードＡ，ＢおよびＣを含む複数のノードであって、前記ノードＡおよび前記Ｂが両方とも前記ノードＣにデータを送信するように位置付けられているノード、
相互接続構造のノードを選択的に結合する複数の相互接続回線、
コントロール信号を前記ノードＡから前記ノードＢに搬送するために、前記ノードＢから前記ノードＡに接続されたコントロール信号搬送回線ＣＢＡ、および
前記ノードＣにデータを送信することが可能であり、前記ノードＡがノードＣにメッセージを送信することを許可されていることを、前記ノードＡに知らせるコントロール信号ｚを前記ノードＡに送信することが可能な、前記ノードＢに関連付けられた経路制御ロジック、を備えた構造。
【請求項６】
前記ノードＣが複数Ｎ個の入力ポートを有し、および
前記ノードＡおよびＢからのデータがノードＣに同時に到達し、そのために前記ノードＣのＮ個全ての入力ポートが並列にメッセージを受信する、請求項５に記載の相互接続構造。
【請求項７】
複数のノードが区別可能なノードＡ，Ｂ，Ｃ，Ｄ，Ｅ，ＦおよびＨを含み、および
前記ノードＣは、ノード前記Ａからのデータを前記ノードＤに送信することができ、および前記ノードＢからのデータを前記ノードＨにノードに送信することができる、請求項６に記載の相互接続構造。
【請求項８】
前記相互接続構造が階層になっており、
前記ノードＡが前記階層のあるレベルにあり、
前記ノードＢ、ＣおよびＤが、前記ノードＡのレベルのすぐ下の階層のレベルにあり、および
前記ノードＥ、ＦおよびＨが、前記ノードＢのレベルのすぐ下の階層のレベルにある、請求項７に記載の相互接続構造。
【請求項９】
区別可能なノードＡ，ＢおよびＣを含む複数のノードおよび前記ノードを選択的に結合する相互接続回線を備えた相互接続構造であって、
前記ノードＣが複数のメッセージ入力ポートを有し、前記ノードＡおよびＣが、ＡがＣにデータ・パケットを発送できるように前記構造内に位置付けられ、
前記ノードＢおよびＣが、ＢがＣにデータ・パケットを発送できるように前記構造内に位置付けられ、
前記ノードＡおよびＢが、ＢがＡにコントロール信号を送信できるようにネットワーク内に位置付けられ、
前記ノードＡにおけるロジックが、前記コントロール信号Ｂを使用してメッセージを発送し、
前記ノードＢがＣにメッセージＭＢを発送し、
前記ノードＡがＭＧと並列に到着するようにＣにメッセージＭＡを送信し、および
Ｃの全ての入力ポートが並列してメッセージを受信する、相互接続構造。
【請求項１０】
相互接続構造であって、
入力ポートＩＡおよびＩＢならびに出力ポートＯＨおよびＯＤを有するノードＣを含む相互接続された複数のノード、
入力ポートＩＢおよび出力ポートＯＨを有するノードＣにアクセス可能な複数の相互接続出力ポート、および
相互接続構造の中に含まれ、メッセージＭＡが入力ポートＩＡに到達し、同時にメッセージＭＢがＩＢに到達したとき、出力ポートＯＢを通過してメッセージＭＡの目標の目的地に至る経路および出力ポートＯＨを通過してメッセージＭＢの目標の目的地に至る経路を保証する経路制御ロジック、を備えた構造。
【請求項１１】
出力ポートＯＨを使用することをメッセージＭＢが阻止されておらず、および出力ポートＯＢを使用することをメッセージＭＡが阻止されていないことを、前記経路制御ロジックが保証する、請求項１０に記載の相互接続構造。
【請求項１２】
メッセージＭＡおよびＭＢの経路制御のための前記経路制御ロジックが、サービス品質基準に依存する、請求項１１に記載の相互接続構造。
【請求項１３】
相互接続構造であって、
ノードＡ，Ｂ，Ｃ，ＤおよびＨを含み、前記ノードＡ，Ｂ，Ｃ，ＤおよびＨの各々が複数の入力ポートおよび複数の出力ポートを有し、およびノードＣがＡおよびＢからメッセージを受信し、ＤおよびＨへメッセージを発送するように位置付けられている、相互接続された複数のノード、
出力ポートＰを含み、ＰがノードＨではなくノードＣからアクセス可能である複数の相互接続出力ポート、および
相互接続構造の中に含まれ、ノードＡがメッセージＭＡをノードＣに送信し、並列してノードＢがメッセージＭＢをノードＣに送信したとき、ノードＣがＤを通過してＭＡをＭＡの目標の相互接続出力ポートに発送することが可能であり、ノードＣがＨを通過してＭＢをＭＢの目標の相互接続出力ポートに発送することが可能な経路制御ロジック、を備えた構造。
【請求項１４】
前記経路制御ロジックが、メッセージＭＢがノードＨに阻止されておらず、メッセージＭＡがノードＤに阻止されていないことを保証する、請求項１３に記載の相互接続構造。
【請求項１５】
前記経路制御ロジックが、サービス品質基準に反応する、請求項１４に記載の相互接続構造。
【発明の詳細な説明】
【０００１】
（関連する特許および出願）
本出願は、１９９８年１月２０日に出願され、継続中の米国特許出願第０９／００９，７０３号に関連し、その全体を参照により組み入れるものとする。本出願はまた、米国特許第５，９９６，０２０号にも関連し、その全体を参照によりここに組み入れるものとする。
【０００２】
開示されるシステム及び動作方法は、次の同時係属特許出願において開示されている内容に関連し、それらの全体を参照によりここに組み入れるものとする。
【０００３】
１．“拡張可能な多系統ワームホール相互接続”と題され、発明者としてジョン・ヘッセが指定され、同日に出願された代理人整理番号Ｍ８１７５ＵＳである米国特許出願第○○／○○○，○○○号。
【０００４】
２．“並列コンピュータおよび並列メモリ・アクセスのための拡張可能な相互接続構造”と題され、発明者としてコーク・リードおよびジョン・ヘッセが指定され、同日に出願された代理人整理番号Ｍ−９０５１ＵＳである米国特許出願第○○／○○○，○○○号。
【０００５】
３．“サービス品質処理を用いた拡張可能な相互接続構造”と題され、発明者としてコーク・リードおよびジョン・ヘッセが指定され、同日に出願された代理人整理番号Ｍ９０５１ＵＳである米国特許出願第○○／○○○，○○○号。
【０００６】
４．“拡張可能なワームホール経路制御集配信装置”と題され、発明者としてジョン・ヘッセおよびコーク・リードが指定され、同日に出願された代理人整理番号Ｍ−９４５８ＵＳである米国特許出願第○○／○○○，○○○号。
【０００７】
（技術分野）
本発明は、コンピュータおよび通信システムの相互接続構造に関する。特に、本発明は、複数のノードを有し、各々のノードが他のノードにメッセージを送信し、各々のノードが複数の同時入力を受け入れ、特定のメッセージを送ったノードの下位の２以上のレベルに配置されたノードの検査を使用することによって、どこにメッセージを送信すればよいかを決定する、他レベル相互接続構造に関する。本発明はまた、制御ロジックの少ない増大のもと、後述する先行技術よりレイテンシが低いシステムを提供する。
【０００８】
（発明の背景）
インターネット、超並列コンピュータのような先進のコンピュータ・システムおよび先進の遠距離通信システムは、すべて低いレイテンシおよび高いスループットを提供すると同時に制御およびロジック回路を減少させる相互接続構造を必要とする。
【０００９】
このような１つのシステムは、１９９９年１１月３０日にコーク　Ｓ．リードに付与された米国特許第５，９９６，０２０号（“リード特許”）に記載され、その教示は参照によりここに組み入れられるものとする。リード特許は、ネットワークおよび、相互接続の全体にわたるメッセージ通信の時間調整および位置調整に基づくデータ・フロー技術を利用した相互接続構造を記載する。前記構造の複数のノードにわたって切替制御器が分配され、それにより、全体的なコントロール機能を提供する管理コントローラおよび複雑なロジック構造を不要としている。前記の相互接続構造は、“デフレクション”または“ホット・ポテト”システムとして動作し、処理および各々のノードにおけるストレージのオーバーヘッドが最小限に押さえられる。全体的なコントローラおよびノードにおけるバッファの除去は、メッセージ通信のスループットを増大させ、メッセージ通信のレイテンシを低くすると同時に、コントロール・コンポーネントおよびネットワーク・コンポーネント全体を単純化するために、相互接続構造における制御およびロジック構造の量を大幅に減少する。
【００１０】
特に、リード特許は、相互接続構造において、所望の出力ポートが利用可能になるまでパケットを保持するのではなく、追加出力ポートを通って同じレベルにあるノードへ至るメッセージ・パケットの経路を指定することにより、処理および各々のノードにおけるストレージのオーバーヘッドを大幅に減少させる設計を説明する。
【００１１】
リード特許の１つの態様によれば、相互接続構造は複数のノードおよび多重構造のノードを選択的に接続する複数の相互接続線を含み、そのレベルは十分に相互接続されたリングの集合を含んでいる。多重構造は、Ｊ＋１個の複数レベルを含んでおり、各々の階層には、Ｃ・２Ｋ個の複数ノードを含んでいる。Ｃは複数の角度の数の代表整数値である。制御情報は、相互接続構造における、データ通信衝突を解消するために送信され、各ノードは、隣接する外のレベルにあるノードに取って代わり、かつ同じレベルにあるノードの直接取って代わる。直接先行するノードからのメッセージ・データが優先権を持っている。制御情報は、あるレベルのノードから隣接する外のレベルに、衝突が差し迫っていることを警告するために送信される。
【００１２】
リード特許は、先行技術より実質的に進歩しているが、それは基本的に、メッセージがあるのと同じレベル、またはメッセージの終着目的地に近い低いレベルのノード入力ポートの効果に基づき、相互接続構造を通ってメッセージが進行する“ワンステップ進歩した”システムである。リード特許において、ノードは各々のノードの入力ポートにおいて、複数の同時メッセージを受け取ることが可能なようにすることができる。しかし、リード特許では、入力されたメッセージを送信することが可能なのは、１つの阻止されていない利用可能なノードのみであって、実際にはリード特許においては、同時に入力されたメッセージを受け取ることはできない。しかし、リード特許は、各々のノードがメッセージの現在のレベルより下位の２以上のレベルからの情報を考慮し、これによりネットワークのスループットを減らし、レイテンシの現象を実現することができることを教示した。
【００１３】
最適なネットワーク構造を実現する第２のアプローチは１９９８年１月２０日に出願されたジョン　Ｅ．　ヘッセの米国特許出願第０９／００９，７０３号（“ヘッセ特許”）に示され、記載されている。この特許出願は、本発明と同じ団体に譲渡され、その教示はまた参照によりその全体をここに取り入れられる。
【００１４】
ヘッセ特許は、リード特許で教示されるのと同様に、全ての形式のコンピュータ、ネットワークおよび通信システムに使用する、多階層最小ロジック相互接続構造の機能性を伸ばす拡張可能な低レイテンシ・スイッチを記載する。ヘッセ特許で記載されている拡張可能な低レイテンシ・スイッチを使用した相互接続構造は、ネットワークにメッセージを挿入する新規なプロシージャによって、ワームホール経路制御を実現する方法を採用する。前記拡張可能な低レイテンシ・スイッチは、アレイ状に配置された、たくさんの非常に単純なコントロール・セル（ノード）から構成される。１つのアレイ内のノードの数は、６４から１０２４の範囲の典型的な設計パラメータであり、通常は２の階乗である。アレイは、レベルおよびコラムに配列される。各々のノードは２つのデータ入力ポートおよび２つの出力ポートをもち、ノードは大きなユニットを形成するために結合する“ノード対”のように、さらに複雑な設計に構成することができる。
【００１５】
ヘッセ特許においては、複数のメッセージは、１つのアレイの外部シリンダー上の全ての阻止されていないノードに同時に挿入されることはないが、２つのコラムＡおよびＢの間に全部のメッセージが入る場合に限り、ＡおよびＢに同時に挿入される。この方法は、一方のメッセージの最初のビットが、既にスイッチの中にある他方のメッセージの内部ビットと衝突することを有利に防止する。したがって、所望の結果であるところの、相互接続構造内のたくさんのノードを通過するメッセージ・ワームホールにより、競合する２つのメッセージの最初のビット同士の争いを解決することにより、メッセージ全体同士の争いが処理される。
【００１６】
ヘッセ特許は、確かに先行技術に対する改良であるが、まだワームホール経路制御と組み合わせた“ワンステップ進歩した”システムである。低いレイテンシで高いスループットの相互接続構造を提供するさらなる改良が可能であり、本発明はそのような改良に向けられている。
【００１７】
したがって、リード特許およびヘッセ特許の利点を利用しつつ、それらの教示の改良を実現することにより、高いスループットで低いレイテンシの相互接続構造を提供すること、が本発明における我々の目的である。
【００１８】
さらに、リード特許およびヘッセ特許で示された相互接続構造を採用し、それら各々の発明に記載された“ワンステップ進歩した”システムを改良することにより、基本的な構造に追加することが本発明の目的である。
【００１９】
本発明の他の目的は、リード特許およびヘッセ特許の相互接続構造の中に記載されるように、各ノードがより効率的に機能することを可能にし、これによりレイテンシを減少させ、メッセージ・スループットを増大させることである。
【００２０】
さらに、各ノードが、ノード入力ポートにある複数の同時メッセージを、いずれのメッセージを阻止することなく、受け入れることを可能にすることにより、リード特許およびヘッセ特許の相互接続構造を改良することが本発明の目的である。
【００２１】
本発明のさらなる他の目的は、ある特定のノードに入力されたメッセージのあるレベルより下位の２以上のレベルにあるノードに関するコントロール情報を、ノードが受け取る“数ステップ進歩した”システムを提供することである。
【００２２】
（発明の概要）
本発明の１つの実施例によると、相互接続構造は、階層的な多重構造において、複数のノードとともに、選択的にノードを接続する複数の相互接続回線を備える。前記構造内におけるノードのレベルは、構造内のノードの位置により決定され、構造内において、データは起点レベルから目的地レベルへ移動するか、または代わりに多重構造のあるレベルに沿って進む。
【００２３】
本発明の特長は、各々のノードが、複数の入力ポートおよび複数の出力ポートを有する前記複数のノードを含み、各ノードがその２以上の入力ポートにある同時データ・メッセージを受信することができることである。
【００２４】
本発明のさらなる特長は、もし、前記ノードが前記相互接続構造内の別のノードおよび別のノードへの出力ポートを通じて、前記各々の受信データ・メッセージを転送できるのならば、各ノードが同時データ・メッセージを受信することができることである。
【００２５】
本発明のさらなる特長は、前記相互接続内のノードが、データ・メッセージを受信したノードより下位にある２以上のレベルにあるノードに関する情報を受信することである。
【００２６】
本発明のこれらのおよび他の目的および特長は、添付する図面と併せて、以下の詳細な説明を参照することにより、より完全に理解されるであろう。
【００２７】
（発明の詳細な説明）
本発明は、米国特許第５，９９６，０２０号（“リード特許”）および１９９８年１月２０日に出願された米国特許出願第０９／００９，７０３号（“ヘッセ特許”）に示される相互接続構造を、参照によって組み入れている。リード特許においてノードは円筒状の構成に配置され、ヘッセ特許においてノードはロウおよびコラムに配置される。両者の特許は、ともに本発明の相互接続構造に利用されうるノード配置の様々な形式を記載している。リード特許およびヘッセ特許のすべての実施例は、相互接続およびノード配置の両方において、本発明に適用されると理解されるべきである。
【００２８】
図１を参照すると、リード特許において説明されている程度の相互接続構造が示されている。図１には３つのノードが図解されている。２つのノード、Ａ１０２およびＢ１０４は、第３のノードＣ１０６に直接メッセージを送信する位置に位置付けられている。ノードＢおよびＣはネットワークのレベルＮにあり、ノードＡはノットワークのレベルＮ＋１にある。リード特許およびヘッセ特許に記載される通り、ノードＢはノードＡに対して、ノードＣにデータを送信する優先権を有している。ノードＢがノードＣに経路１１４によってメッセージＭＢを送信するとき、ノードＢはＣにＭＢを送信していることをＡに知らせるコントロール信号１２０を送信する。これによりメッセージＭＢと衝突しうる期間には、ＡはＣにメッセージＭＡを送信しない。もし、ＭＡのヘッダに指示されるように、ＣからＭＡの目標出力へ至る経路があり、ＢからＡへのブロッキング信号がなければ、Ａは経路１１２によってＣにＭＡを発送できる。もし、これらの条件のどちらも当てはまらなければ、Ａは、Ｃとは別のネットワークのレベルＮ＋１にある図示されないノードに送信する。
【００２９】
リード特許では、ノードＡおよびＢは異なるシリンダーの同じ角度にあると述べられている。ヘッセ特許では、ノードＡおよびＢは、異なるレベルの同じコラムにあると述べられている。
【００３０】
図２に４つのノードが説明されている。ノードＢ、ＣおよびＤは、ネットワークのレベルＮにあり、ノードＡのネットワークのレベルＮ＋１にある。ノードＢから到達しうる全てのネットワークの出力ポートは、またノードＣおよびＤからも到達しうる。Ａから到達しうる出力ポートには、Ｃから到達できないものがある。このため、メッセージがＡからＣに伝わるときは、メッセージが到達できる出力ポートの集合が減少する。ノードＣがノードＤと同じレベルにあるとき、Ｃは、ネットワークの全てのノードの中で、ノードＤにメッセージを送信するための最も高い優先権を有する。このため、所定の期間にただ１つのメッセージＭがノードＣに到達したとき、メッセージＭは常にノードＤに移動でき、そしてＤからＭの目標出力ポートへ至る経路が存在する。したがってノードＣにバッファを有する必要がなく、同じ理由により、他のいかなるノードでもバッファが使用されない。リード特許およびヘッセ特許においては、衝突するメッセージをＢがＣに送信しないということを、ノードＡに関連するロジックが知らされなければ、メッセージＭＡはＡからＣに移動することが許されない。ノードＣにデータを送信することについてのノードＡに対するノードＢの優先権は、ＢからＡへのコントロール信号によって実行される。この方法では、ＡがメッセージＭＡをＣに送信することを“欲し”、かつＢからＡへのコントロール信号によりメッセージＭＡをＣに送信することをＡが禁止されないならば、ＡはＭＡをＣに発送する。リード特許およびヘッセ特許または特許出願“拡張可能な多系統ワームホール相互接続” において、ネットワークの一部が記載される図２の場合では、ＣからＭＡのヘッダに指定されたＭＡの目標出力ポートへ至る経路が存在するときに、ＡがメッセージＭＡをＣに送信することを“欲する”。特許出願“拡張可能なワームホール経路制御集配信装置” においてネットワークの一部が教示される図２の場合では、ノードＡは常時、メッセージＭＡをＣに送信することを“欲し”ている。なぜなら集配信装置の場合では、出力の全てがＭＡ用の出力ポートに受け入れ可能であるからである。その代わりヘッセ特許は、ＡからＣへ至るメッセージに、ノードＢを通過してＣに移動することを許すことにより、所定の時間に、ただ一つのメッセージのみがノードＣに到達できるという事実を活用している。
【００３１】
図３Ａを参照すると、リード特許に教示される相互接続構造の一部が示されている。リート特許では、特定の時間間隔の間に、ただ一つのメッセージがＣに入ることができる。しかし以下に説明するとおり、前記特許発明では２つの同時のメッセージがノードＣに入ることが許されることがある。そのため、ＡからＣへのメッセージおよびＢからＣへのメッセージが同時にノードＣに入ることが許される。
【００３２】
図３Ｂはヘッセ特許で使用される相互接続構造の一部を説明する。データ経路３０６は、ＡまたはＢのいずれかからメッセージを受け入れ、単一のメッセージだけをＣに伝送することができる。図３Ｂのノードは、ＡおよびＢの両方のノードがＣに送信できるようにノードＢからＣへの追加経路３１６が追加された図３Ｃが説明するように修正することができる。しかし前記特許発明で可能である、リード特許と同様に同時に２つのメッセージを受け入れる特定のノードを、ヘッセ特許は許容しない。しかし本発明の改良点は、図３Ｂの実施例を図３Ｃの実施例に変更することにより、直ちにリード構成およびヘッセ構成に適用されることが可能である。
【００３３】
図４は、本発明の第１の実施例を説明する。
【００３４】
図４には５つのノードが図示されている。図２に示される４つのノードとは別に、レベルＮ−１にノードＨがある。ノードＣはノードＨにデータを送信することができる。ノードＢがメッセージＭＢをノードＣに送信し、ＣからＨへＭＢが移動するとき、ノードＡはメッセージＭＢと同時にＣに到達するメッセージＭＡをＣに送信することができる。その後、ＭＢがＣからＨに移動するのと同じ期間にメッセージＭＡはＣからＤに移動することができる。同時に２つのメッセージをノードが受け入れることができる能力が本発明の１つの利点であり、リード特許およびヘッセ特許に対する新規な改良点である。
【００３５】
ノードＣにはバッファがないため、２つのメッセージＭＡおよびＭＢが並列にＣに到達したとき、２つのメッセージのうち１つはＨに移動しなければならず、２つのメッセージのうち１つはＤに移動しなければならない。本実施例では、ＭＡがＤに移動することを許されている間、ＭＢは自由にＨに移動できる。２つのメッセージＭＡおよびＭＢが両方ともＣに移動する場合、ＣのロジックはＭＡおよびＭＢの１つをＨに発送し、ＭＡおよびＭＢの他方をＤに発送する。Ｃは、図６Ｂに説明されるように、ある方法によりＭＢをＣからＨ、ＭＡをＣからＤへ送信する。この方法は、常に可能であるため単純であり、そして構造上ＢがＡよりも低いレベルにあるため、ＭＢはたいていＭＡよりも長く構造内にある。もう一つの別の実施例では、Ｃによるメッセージの発送がサービス品質（ＱＯＳ）に依存することができる。この実施例では、ヘッダの一部がサービス品質情報を含むので、ＭＡおよびＭＢがＣに移動するとき、ＣがＭＢをＨにＭＡをＤに発送し、ＭＡのＱＯＳレベルがＭＢのＱＯＳレベルより高くない場合には、図６Ｃに説明するように、ＣがＭＡをＨにＭＢをＤに発送する。この方法では、より高いＱＯＳレベルのメッセージが、低いＱＯＳレベルのメッセージに対して優先権を得る。
【００３６】
リード特許およびヘッセ特許では、コントロール信号１２０（図１）がノードＢからＡに送信され、ＡがＣにメッセージを送信することを阻止されているか否かをＡに知らせる。もし、ＢがＣにメッセージを送信していなければ、この阻止が発生しないことが保証されている。リード特許およびヘッセ特許では、もしＢがＣにメッセージを同じ期間に送信していれば、ＡはＣにメッセージを送信することは許されない。本発明では、もし、ＢからＣへのメッセージがＣからＤへの回線を使用せず、代わりにＣからＨへの回線を使用することが保証されれば、ＢがＣにメッセージを送信しているのと同じ期間に、ＡがＣにメッセージを送信することが許される（図４参照）。
【００３７】
ノードＡに関連付けられたロジックは、メッセージＭＡをノードＣに発送することが可能である。図示されない少なくとも１つの追加ノードＮがあり、そのためノードＡに関連付けられたロジックはＭＡをＮに発送することが可能である。ＡがＭＡをＣに発送する場合、ノードＣに関連付けられたロジックは、ＭＡをノードＤおよびＨに発送することができる。この方法では、メッセージＭＡはＡからＤに移動することができ、メッセージＭＢはＢからＨに移動することができる。Ａに関連付けられたロジックは、ＭＡをＤまたはＨのどちらにも発送できない。同様にＢに関連付けられたロジックは、ＭＢをＢからＣに発送でき、Ｃに関連付けられたロジックは、ＭＢをノードＤまたはノードＨのどちらにも発送できる。そのため、メッセージＭＢがＢからＤまたはＢからＨに移動できる一方、ノードＢに関連付けられたロジックはメッセージＭＢをノードＤまたはノードＨのいずれにも発送することができない。
【００３８】
図５は、ヘッセ特許に記載されたネットワークの一部のブロック図である。ノードはアレイに配置される。ノード・アレイは、ロウおよびコラムに配置される。最も右側のコラムにあるノード・アレイは、同じレベルの最も左側のコラムにあるノード・アレイに接続されているため、たとえば、レベルＪ−１、コラムＫ−１の出力Ｂは、レベルＪ−１、コラム０の入力Ｂとなる。図４では、ノードＡはレベルＮ＋１、コラムＭのアレイにあるノードであり、ＢはレベルＮ、コラムＭのノード・アレイであり、ＣはレベルＮ、コラムＭ＋１のノード・アレイであり、ＤはレベルＮ、コラムＭ＋２のノード・アレイであり、そしてＨはレベルＮ―１、コラムＭ＋２のノード・アレイである。各々の図１，２，３，４，６，７および８は、図５で説明されたノード・アレイの要素である個々のノードの間の接続を示す。
【００３９】
図６Ａには、本発明の実施例のさらなる記載である８つのノードが図解されている。図４の５つのノードに加えて、レベルＮに追加ノードＥ、レベルＮ−１に追加ノードＦおよびＧがある。ＥはＧ、Ｆにメッセージを送信し、ＦはＧにメッセージを送信し、そしてＧはＨにメッセージを送信する。
【００４０】
リード特許の好適実施例では、ノードはヘッダ内の１つのアドレス・ビットだけを読む。メッセージＭＢがＢにあるとし、ＢがＭＢをＣに送信すると仮定する。すると、ＢおよびＣは同じレベルにあるため、ＣはＢが読むのと同じＭＢのヘッダ・アドレス・ビットを読む。ネットワークのトポロジーは、Ｂのロジックが、ＨがＭＢの目標へ至る経路上にあるかどうかを決定できるようになっている。これは、ＨがＭＢの目標へ至る経路上にあるかどうかをＭＢの単一のアドレス・ビットが決定し、そしてそのアドレス・ビットが、ノードＢのロジックによって読まれたビットと同じためである。それは、ＭＢがＣに到達したときに、ノードＣのロジックによって読まれるビットも同じビットである。もし、ＨがＭＢの目標へ至る経路上にあり、ＭＢがＨに到達するのと同じ時間に、Ｈに到達するＭＢとは別のメッセージがなければ、図６Ｂに示すように、ＭＢは、まずＢからＣ、その後ＣからＨに移動できる。ＭＢと到達するのと同じ時間にＨに到達するメッセージは、ＥまたはＦのいずれかから来なければならない。もし、ＥまたはＦに到達するようなメッセージＭがなければ、ＭＢはＢからＣそしてＣからＨに移動するのは確実である。
【００４１】
ＦからＧへ移動するメッセージの存否を示す、ＦからＥへのコントロール信号回線６０４がすでに存在する。本発明では、リード特許およびヘッセ特許にはない、ＥからＡへの追加コントロール回線６０２がある。
【００４２】
Ａにおけるロジックは次の通りである。メッセージＭＡはノードＡに到着する。ノードＡはＭＡの１つのヘッダ・ビットを読む。もし、そのヘッダ・ビットがＣからＭＡの目標へ至る経路があることを示していれば、下記のいずれかの条件を満たすとき、ＡはＣにＭＡを送信する。
【００４３】
１）ＢからＣへ送られた競合するメッセージがないこと、または
【００４４】
２）ＭＡがＣに到着したのと同じ期間にＣに到着したメッセージＭＢがあり、ＭＢはＣからＨに移動し、ＣからＤへのリンクを有利に使用しないことが保証されていること。
【００４５】
ＢからＡへのコントロール信号は、ＢがメッセージをＣに送信しているか否か、さらにＨからＭＢの目標出力ポートへ至る経路があるか否かを示す。
【００４６】
ＦからＥへのコントロール信号は、ＦがメッセージをＧに送信しているか否かを示す。ＥからＡへのコントロール信号は、ＥまたはＦがメッセージをＧに送信しているか否かを示す。ノードＡは、ＭＡをどこに送信するかを決定するの必要な全ての情報を有利に与えられる。具体的には
【００４７】
１）　もし、ＢからＡへのコントロール信号が、ＢからＣへ送信される競合するメッセージがなく、そしてＣからＭＡの目標へ至る経路があることを示すならば、ＡはＭＡをＣに送信する。または、
【００４８】
２）　もし、次の条件をみたすとき、ＡがＭＡをＣに送信する
【００４９】
・ＢからＡへのコントロール信号が、ＢにメッセージＭＢがあり、ＨからＭＢの目標出力へ至る経路があることを示し、
【００５０】
・ＥからＡへのコントロール信号が、ＥからＧまたはＦからＧに送信された競合するメッセージがないと示したため、ノードＡが、ＭＢのためにＣからＤへ至る経路を使わずにＭＢがＣからＨに移動できると判断し、および
【００５１】
・ＣからＭＡの目標出力ポートへ至る経路が存在する。
【００５２】
３）　さもなければＡは、Ａと同じレベルにあるＣとは別の図示されないノードにＭＡを送信する。
【００５３】
２つのメッセージＭＡおよびＭＡ’が同時にノードＡに到達したとき、２つのメッセージのうち１つが、上記のロジックにしたがってＣに送信され、残りのメッセージが図示されないＣとは別のノードに送信される。この方法によれが、リード特許およびハッセ特許ではレベルを落とされないが、本発明による有利に、メッセージのレベルを落とされるメッセージが存在する。上記のロジックの特長は、２つのメッセージが１つのノードに同時に到達したときはいつでも、これらのメッセージの少なくとも１つが、低いレベルに落ちることを許容することである。
【００５４】
複数ビットのメッセージが、バッファなしでノードＡを通過することに注意されたい。したがって最大時間Ｔが固定され、そのためにノードＡにあるどのメッセージも、Ａに到達してからＴ時間以内でＡを離れる。回線６０２により運ばれるコントロール信号（図６Ａ）が、ノードＥおよびＦと通過するメッセージの経路制御を含み、したがってノードＡに到着するメッセージにより決定されないことにもまた注目されたい。
【００５５】
図７は、図６Ａと同じノードを有しつつ、しかしＥからＡへのコントロール回線に代えて、ＦからＢへのコントロール回線ＣＦＢおよびＥからＢへのコントロール回線ＣＥＢを有している。コントロール回線ＣＦＢは、ＦからＢへ単一ビットｘの形で情報を送信する。ビットｘは、あるメッセージがＢからＨに移動するのと同じ期間に、Ｈに到着することができるＦからＧに送信されるメッセージがないとＦのロジックが判断したときに、ゼロに設定される。Ｆは下記のいずれかを満たすときｘをゼロに設定する。
【００５６】
１）　ＦからＧへ送信されるメッセージがないこと、または
【００５７】
２）　ＦからＧへ送信されるメッセージが、Ｇから図示されないＨとは別のノードＪに送信されること。
【００５８】
ＥからＢへのコントロール回線ＣＥＢは、ＥからＢへ単一ビットｙの形で情報を送信する。ビットｙは、あるメッセージがＢからＨに移動するのと同じ期間に、Ｈに到着することができるＥからＧに送信されるメッセージをＥが送信していないときに、ゼロに設定される。
【００５９】
ノードＢはメッセージをどこに送信するかを決定するために、ビットｘおよびｙを含む情報を使用しない。それは、その所有するメッセージをどこに送信するかを決定するために、図示されないレベルＮ−１にあるノードから出ている、さらに他のコントロール回線からの情報を使用する。ノードＢは、コントロール回線を使用してＡにコントロール信号を送信することを可能にするために、回線ＣＥＢおよびＣＦＢの情報を使用する。ノードＢは、コントロール回線ＣＢＡに単一ビットｚを送信する。あるメッセージＭＡがちょうどノードＡに到達したと仮定する。ビットｚがゼロであり、ＣがＭＡの目標へ至る経路にあるならば、ＭＡはノードＡからＣに送信される。ビットｚは、次のいずれかの条件を満たすときゼロに設定される。
【００６０】
１）　ＡからのメッセージＭＡと衝突を起こしうる期間に、ＢからＣにメッセージＭＢをＢが送信しないこと、または
【００６１】
２）　Ｂが、ＭＢのヘッダにあるｘおよびｙを含む情報に基づいてＣにメッセージＭＢを送信し、ＭＢがＣからＨに移動できるとＢのロジックが判断すること。
【００６２】
ノードＡは、ＭＡのヘッダおよび単一ビットｚの値に基づいて、入ってくるメッセージＭＡを発送することができる。同時にＡに到達する２つのメッセージＭＡおよびＭＡ’の場合では、上記のロジックにしたがって、２つのメッセージのうち１つがＣに送信され、他のメッセージは、図示されないＣとは別のノードに送信される。上記のロジックの特長は、２つのメッセージＭＡおよびＭＡ’のうち１つがＣに落ちることが許されることである。特にＭＡおよびＭＡ’は、Ａの同じ出力ポートに発送されない。
【００６３】
本実施例によるノードが、１つのヘッダ・アドレス・ビットおよびより低いレベルのコントロール・ビットに基づいてメッセージを発送できることは重要である。この方法における時間調整は、リード特許およびヘッセ特許における時間調整と同じである。図６のロジックを使用したノードＡがＣにメッセージを送信できず、代わりにＮ＋１レベルのノードにメッセージを送る場合でも、図７の実施例では、ノードＡはメッセージをＣに送信できる。
【００６４】
リード特許およびヘッセ特許、およびこれまでにそこで記載された器具では、ノードは、メッセージが存在することを示すヘッダのビットを読み、そしてそれらは追加ヘッダ・アドレス・ビットを読む。それらはサービス品質のような追加アドレス・ビットも読むこともある。本発明のさらなる実施例によれば、ノードは複数のアドレス・ビットも読むことになる。
【００６５】
図６Ａを参照する。代替実施例においては、ノードがメッセージ・ヘッダの２つのアドレス・ビットを読む。Ｈを含む目標経路を有する単一メッセージＭＡがＡに到達し、Ｈを含まない目標経路を有する単一メッセージＭＢがＢに到達し、ＢはＭＢをＣへ、その後Ｄへ送信しなければならないとする。図６Ａおよびそれより前の図おいて示される構造は、図６Ｃに図解されるように、ＭＡの経路がノードＡ，ＣおよびＨを通過し、そしてＭＢの経路がノードＢ、ＣおよびＤを通過するように、メッセージＭＡがノードＣにおいてメッセージＭＢを“乗り越える”ことを許容する。この実施例の目的は、メッセージＭＡが、同じ時間に共通のノードＣを通過する経路をもつ競合メッセージＭＢを、いつ乗り越えることを認めるかを決定するために必要な情報をノードに提供することにある。メッセージＭＡは、Ｃを通ってＭＡの目標へ至る経路があるか否かを示す１つのヘッダ・ビットを読むノードＡに到達する。ＥからＡへのコントロール信号は、ＭＡと同じ時間に、ＥからＦへのメッセージがＨにないことを保証する。ＢからＡへのコントロール信号は、ＭＡと同じ時間にＣに到達するメッサージＭＢがＢにあるかどうかを示し、もしあるならば、ＭＢがＨを通過しないことを保証されているかどうかを示す。これらのコントロール信号に基づき、下記の条件のうち少なくとも１つをみたすならば、ＡはメッセージＭＡを送信する。
【００６６】
１）　ＣからＤへ至る経路が使われていないことが知られており、およびＣを通過してＭＡの目標に至る経路があること、または
【００６７】
２）　ＣからＨへ至る経路が使われていないことが知られており、ＨからＭＡの目標に至る経路があり、およびＭＡがＨに到達するのと並列に、ＥまたはＦからＨに到達しうるメッサージがないこと。
【００６８】
上記の第１の条件（１）および第２の条件は、“乗り越える”事例に関係する。もし、上記の条件のいずれも満たされない場合は、ＡはＭＡをレベルＮ＋１にある図示されないＣ以外のノードに送信する。２つのメッセージＭＡおよびＭＡ’が同時にノードＡに現れた場合が上記記載で取り扱われている。２つのヘッダ・ビットの読み込みは、上記の条件（２）を発見することを可能にする。これはときどき、図６Ａの実施例以前において、Ａと同じレベルに留まるメッセージＭＡをＡからＣへ送信することを許容する。２つのヘッダ・アドレス・ビットの読み込みは、ここに、ならびにリード特許およびヘッセ特許に記載される、ネットワークのコントロール・ロジックおよびコントロール信号小さな修正を必要とする。そのような修正は、この発明の技術分野における当業者にとっては明らかであり、したがって、そのような修正についてのさらなる説明は、ここに提示しない。
【００６９】
図７において、ノードＦがノードＧ経由でノードＨにデータを送信できる間に、ノードＡがノードＣを経由してノードＨにデータを送信できることに注意されたい。コントロール信号ｘおよびｚは、ＡからＨへのデータを転送に対するＦからＨへのデータ転送の優先権を実行する。
【００７０】
図８を参照する。図８のノードＡおよびＨは、レベルＮ−１、コラムＫ＋２にある。ノードＢおよびＣは、ＡおよびＨに直接データを送信するようにレベルＮ、コラムＫ＋１に位置付けられる。ノードＵおよびＶは、Ｂに直接データを送信するようにレベルＮ＋１、コラムＫに位置付けられ、そしてノードＷおよびＸは、Ｃに直接データを送信するようにレベルＮ＋１、コラムＫに位置付けられる。ノードＢは、レベルＮにあるノードＤから直接データを受信し、そしてレベルＮにあるノードＬに直接データを送信する。ノードＣは、レベルＮにあるノードＥから直接データを受信し、そしてレベルＮにあるノードＭに直接データを送信する。図８に図示されないコラムＫにあるノードの集合Ｒがあり、Ｒの要素はノードＤおよびＥへのコントロール信号を送信することができる。ノードＤは図示されないＲ内のノードからの情報を使用し、そしてノードＥは、ノードＤからの同一の情報を使用する。Ｒ内のノードがノードＤが受信するコントロール情報は、ノードＢからノードＡおよびノードＨへ至る経路がノードＤが阻止されていないかどうかを判断することを可能にする。
【００７１】
図８は、所定のレベルＮ上の各々のノードＣがレベルＮ＋１上の２つのノードおよびレベルＮ上の１つのノードからデータを受信するように位置付けられ、レベルＮ−１上の２つのノードおよびレベルＮ上の１つのノードにデータを送信するようにも位置付けられた、データ相互接続構造の一部を説明する。このデータ相互接続構造を有するネットワークは、リード特許における次のレベルへの複数の相互接続の実施例として、およびヘッセ特許における均等レイテンシの実施例として参照される。コントロール相互接続は、リード特許およびヘッセ特許に記載され、その教示は参照によりここに組み込まれる。
【００７２】
本発明におけるデータ相互接続構造は、リード特許およびヘッセ特許に記載される通りであるが、ノードは、スループットを増大させ低いレイテンシを実現するために、さらなるコントロール情報を受信し、処理する点でより高度である。ノードがバッファを有しないため、ノードに入ったメッサージは、直ちにノードから離れ、目標出力へ至る経路にある他のノードに進むことが可能でなければならない。１つのノードから２つのメッセージが離れるときはいつでも、一方が同じレベルに沿って進み続け、他方はレベルを落とさなければならない。正しい動作は、コントロール信号により実行される優先規則に依存する。各々のノードが１つの目標のヘッダ・デスティネーション・ビットだけを読む場合を検討する。これは、レベルＮ上のどのノードも、レベルＮ＋１から２つのメッセージを同時に受信できないことを意味する。レベルＮ上のノードが２つのメッセージを受信したとき、同じレベルＮからの到着したメッセージがいつもレベルＮ−１上のノードに送信されることが可能で、および送信される場合であることも分かる。
【００７３】
ノードＢは、ノードＡおよびＨにデータを送信することについて、ノードＣに対する優先権を有する。ノードＤは、ノードＢにデータを送信することについて、ノードＵおよびＶに対する優先権を有し、そしてノードＵは、ノードＢにデータを送信することについて、ノードＶに対して優先権を有する。同様にノードＥは、ノードＣにデータを送信することについて、ノードＷおよびＸに対して優先権を有し、ノードＷは、ノードＣにデータを送信することについて、ノードＸに対して優先権を有する。本発明による他の例と同様の方法では、コントロール信号は、ある所定の期間においてコラムＫ上のノードからノードＤおよびＥに入る。同時にノードＤおよびＥにメッセージが入ることも可能である。ノードＤに入るメッセージおよびノードＤが受信するコントロール信号に基づいても、ノードＤはノードＢにメッセージを送るかどうか分からない。ノードＤは、適切な時期に、１）ノードＤからノードＢへ送信するメッセージがないこと、２）メッセージＭＤはＢに送信されており、ＭＤがノードＢに到達したとき、ノードＢはＭＤをノードＡに導くこと、３）メッセージＭＤはノードＢに送信されており、ＭＤがノードＢに到達したとき、ノードＢはＭＤをノードＨに送信すること、または４）メッセージＭＤはノードＢに送信されており、メッセージＭＤはノードＢからノードＬに移動することが可能であること、のいずれかを示すコントロール信号をＵおよびＥに送信する。１，２，および３の場合では、ノードＵに、ノードＢを通過してその目標に到達するようなメッセージＭＵがあれば、メッセージＭＵはノードＢに送信され、ノードＶからのメッセージはノードＢに移動することが許されない。もし、１，２または３の場合の１つが当てはまり、ノードＵがノードＢにメッセージを送信していなければ、ノードＶはノードＢにメッセージを送信するよう求められる。すなわち、もしノードＵがノードＢにメッセージを送信しなければ、ノードＵは、コントロール信号の手段によりノードＶにそう知らせ、そしてメッセージＭＶがノードＢを通過して、その目標に到達することができるノードＶにあれば、ノードＶはメッセージＭＶをノードＢに送信する。２の場合、すでに扱われたシングル・ダウンの場合のように、ＡにおいてメッセージＭＤを衝突する時間にＡに到達するメッセージがなく、そしてＡからＭＤの目標出力ポートへ至る経路があるという情報に基づいて、ノードＤはノードＢがメッージＭＤをＡに発送することを予測することができる。３の場合に同様の状況が存在する。本発明では、もし２または３の場合が当てはまり、ＵまたはＶのいずれかがＢにメッセージを送信するならば、Ｂは２つのメッセージを受信することができる。これは、所定の時間に１つのメッセージだけをＢに送信することができるリード特許およびヘッセ特許と、大きく異なる。
【００７４】
ノードＥに入るメッセージおよびＥが受信するコントロール信号に基づいても、ノードＥはノードＣにメッセージを送るかどうか分からない。ノードＤからノードＥへのコントロール信号は、ノードＥによるメッセージの経路制御に影響しないが、ノードＥがノードＷに送るコントロール信号に影響する。ノードＥに関連付けられたロジックは、適切な時期に以下の条件１）ノードＥからノードＣへ送信するメッセージがないこと、２）ＥがメッセージＭＥをＣに送信しており、ＭＥがＣに到達したとき、ＣはＭＥをＡに送信すること、３）ＥがメッセージＭＥはノードＣに送信しており、そしてＭＥがＣに到達したとき、ＣはＭＥをＨに送信すること、４）ＥがメッセージＭＤをＣに送信しており、ＣがノードＭにＭＥを発送する可能性が存在すること、の１つが当てはまっているかを確認する。ＤからＥへのコントロール信号は、ＣによるＭＥの経路制御を予測するために、Ｃに関連付けられたロジックによって使用される。これは、ＢおよびＣの両方ともノードＡに発送することが許されず、ＢおよびＣの両方ともノードＡに発送することもまた許されないからである。もし、１、２または３の条件が当てはまれば、ノードＥは、ノードＷにノン・ブロッキング・コントロール信号を送信し、ノードＣに発送することをＷに許可する。４の場合、ノードＥはＷにブロッキング・コントロール信号を送信し、Ｗはブロッキング・コントロール信号をＸに送信する。そしてＷまたはＸのいずれもＣにメッセージを送信しない。ノードＷがノン・ブロッキング・コントロール信号をＥから受信し、ＷがメッセージＭＷを正確な時間に受信し、Ｃを通過してＭＷの目標に至る経路が存在する場合は、ＷはＣにＭＷを送信し、かつＸにブロッキング・コントロール信号を送信して、ＸがＣにメッセージを送信することを禁止する。ノードＷがノン・ブロッキング・コントロール信号をＥから受信したが、ＷがＣにメッセージを送信しない場合には、Ｗがノン・ブロッキング・コントロール信号をＸに送信する。Ｗからのノン・ブロッキング・コントロール信号が存在する場合は、もしＸがメッセージＭＸを適切な時間に受信し、ＣからＭＸの目標出力へ至る経路が存在するならば、ＸはＣにＭＸを送信する。
【００７５】
リード特許およびヘッセ特許は、基本的に将来に向けた１つのステップを見た。本発明で示した２つの実施例は、将来に向けた２つのステップを見た。当該技術の当業者は、ここで示された技術を使用してさらに先の将来を展望ことができる。
【００７６】
ここには、いくつかのトレード・オフの関係がある。ノードがより複雑になり、ステップ単位のスループットが増大し、構造を通過するステップの平均全体が減少すると、チップに置くことができるノードが減少し、ステップあたりに要する時間が増加する可能性がある。ヘッセ特許は、ペイロードを運ぶ光学的スイッチを駆動するヘッダを運ぶ電気スイッチの設計を教示している。この発明において、それは、より電子装置のロジックに費やすことを意味し、従ってこの発明は、ヘッセ特許で開示されたスイッチを実装する代わりの方法として用いられることができる。
【００７７】
“拡張可能な多系統ワームホール相互接続”と題され、発明者としてジョン・ヘッセが指定され、同日に出願された代理人整理番号Ｍ８１７５ＵＳである米国特許出願第○○／○○○，○○○号は、メッセージ・ヘッダにあるサービス品質情報をいかに効率的に利用するかを教示する。米国特許出願第○○／○○○，○○○号の技術は、参照によりここに組み込まれる。前記技術は、その特許出願が本発明に効率的に適用されうることを教示し、したがって例えば、もしノードＤからのコントロール信号が、ノードＵおよびノードＶのうち１つがノードＢにメッセージを送信できることを、ノードＵおよびＶに知らせたら、ノードＵにおけるメッセージＭＵのサービス品質が低い場合を除き、上記規則を適用され、そのためノードＢからＭＵの目標出力ポートに至る経路あり、ノードＶにおけるメッセージＭＶのサービス品質が高く、それゆえＢには、ＢからＭＶの目標出力ポートに至る経路がある。この場合ＭＶはノードＢの送信され、ＭＵは、コラムＫ＋１にあるレベルＮ＋１のノードに送信される。サービス品質ヘッダ・ビットはノードＤおよびＥに到達するメッセージの優先権を判断するためにも使用することができる。
【００７８】
本発明は、より多くのコントロール情報およびより高度なノードを活用する２つの実施例を含んでおり、２つの好適実施例のパフォーマンスを向上させている。これらの技術を他の相互接続構造に適用することが可能なことは当該技術の当業者に明らかである。
【００７９】
ここに説明され、記載された相互接続構造は、本発明の実施例に好適であると同時に、本発明の精神を逸脱し、または添付した請求項の範囲により決定される本発明の利点を除外することなく、ノード構造および相互接続構造を変更することは可能であると解するべきである。
【図面の簡単な説明】
【図１】
本発明による相互接続構造の一部分を示す図である。
【図２】
本発明による相互接続構造の一部分を示す図である。
【図３Ａ】
本発明による代替的なノード接続を示す図である。
【図３Ｂ】
本発明による代替的なノード接続を示す図である。
【図３Ｃ】
本発明による代替的なノード接続を示す図である。
【図４】
本発明を利用して適用しうる相互接続の３つのレベルを示す図である。
【図５】
本発明の相互接続における様々なノードの相互接続を示す相互接続ブロック図である。
【図６Ａ】
様々なノード間のコントロールおよびメッセージ回線の相互接続を示す図である。
【図６Ｂ】
相互接続構造の一部におけるノード間の相互接続を説明し、ノードの１つを通るデータ経路を示す図である。
【図６Ｃ】
相互接続構造の一部におけるノード間の相互接続を説明し、ノードの１つを通るデータ経路を示す図である。
【図７】
様々なノード間のコントロールおよびメッセージ回線の相互接続を示す図である。
【図８】
本発明の１つの実施例による、セル・ノードの代替的な配置を示す図である。
【図１】
2004511992.tif 000003
【図２】
2004511992.tif 000004
【図３Ａ】
2004511992.tif 000005
【図３Ｂ】
2004511992.tif 000006
【図３Ｃ】
2004511992.tif 000007
【図４】
2004511992.tif 000008
【図５】
2004511992.tif 000009
【図６Ａ】
2004511992.tif 000010
【図７】
2004511992.tif 000011
【図８】
2004511992.tif 000012
【国際公開パンフレット】
2004511992.tif 000013
2004511992.tif 000014
2004511992.tif 000015
2004511992.tif 000016
2004511992.tif 000017
2004511992.tif 000018
2004511992.tif 000019
2004511992.tif 000020
2004511992.tif 000021
2004511992.tif 000022
2004511992.tif 000023
2004511992.tif 000024
2004511992.tif 000025
2004511992.tif 000026
2004511992.tif 000027
2004511992.tif 000028
2004511992.tif 000029
2004511992.tif 000030
2004511992.tif 000031
2004511992.tif 000032
2004511992.tif 000033
2004511992.tif 000034
2004511992.tif 000035
2004511992.tif 000036
2004511992.tif 000037
2004511992.tif 000038
2004511992.tif 000039
2004511992.tif 000040
2004511992.tif 000041
2004511992.tif 000042
2004511992.tif 000043
2004511992.tif 000044
2004511992.tif 000045
2004511992.tif 000046
2004511992.tif 000047
【国際調査報告】
2004511992.tif 000048