JPH0332253A - 高速網状接続特定区域内情報通信網のための経路指定装置及び方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 本発明は、本発明と同時出Ｉ頭された一連番号３７０．
２１１５号“高速網状接続地域内情報通信組１°゛に関
連する。

〔発明の分野」 本発明しよ、−船内にはコンピュータを相互接続するた
めのコンピュータ通信回路５１７１に関し、特定的には
網状に接続された地域内情報通信網のための経路指定装
置及び方法に関する。

［発明の背量］ 地域内情報通信網（１、ＡＮ）は、比較的近接して位置
側けられているコンピュータ間でメンセジを伝送するた
めに広く用いられている。Ｌ　Ａ、　Ｎには少なくとも
３つの哉木の組織的アーキテクチャの型、即ち線形、環
状及び網状か７Ｊミ在する。例え↓よイーｌナネノトは
ごコンピュータ　ワークステジョン、本体及びミニコン
ピユータを和Ｊｌ−接続するために広く使用され′ζい
る線形Ｌ　Ａ　Ｎである。

本発明は網状に接続されている１、、　Ａ　Ｎのめに関
゛づる。

従来、網状接続Ｌ　Ａ　Ｎはコンピュータｆ」学文献及
び幾つかの！ｔ、′ｌＦ、’＋において検訓されてはい
たが、若干の公知の及び比較的処汐しにくい猪間弘のた
めに商業的に底切した例はなかった。これらの問題の１
つは、網状接続子、ｌ・ワークを通してメジセージを経
路指定する効率的なメカニズムが欠如していたことであ
る。理想的には、経路指定メカニズム１才、スイッチに
よって受信された各パゲントをその宛先により近く運ぶ
経路・＼ｉＢ速に経路指定できるべきである。また経路
指定メカニズム↓Ｊ、ネントＴノーク処理能力が単一・
リンクの処理能力を超えるように網状接続ネットワーク
内の数多い経路の有利（ソＩＥを取り入れるべきである
。

第１図において、オンＩ・ワーク１００内の各スイッチ
Ｓは、若干の異なる人力リンクからデークパゲシトを受
信してＩ或１まそれ以上の出力リンクへ経路指定しなけ
ればならない。従ってス・ｆソチば、各パケソト毎に正
しい出力リンクを選択するメカニズムをイ丁していな２
」れぽならない。品い処理１能力を達成するために、ネ
ントワークは柿りの入力リンクから異なる出力リンクへ
多くのパケントを向１．′ｌ′に経路指定できる非閉塞
スイッチを使用しなＬＪればならない。更に、スイッチ
は利用可能な出力リンクを公平にしかも迅速にデータ　
パゲッｌ−４，Ｚ割′″１１てることが好ましい。公平
な経路指定力性どは、−船内にパケンＩ・を受信した順
序に基いて経路指定優先順位をＩｊえる方法である。

（発明の１ａ要〕 要杓ずれば本発明は、高速網状接続１．　Ａ、　Ｎに使
用するためのパタン１〜経路指定装置である。網状接続
ホン１ワークは、■、ＡＮのメンバーであるホスト　コ
ンピュータに結合されている相互接続された複数のスイ
ッチからなる。スイッチは、互に結合された、及び複数
の二地点間リンクによってホストに粘合されたＪ「閉塞
スイッチである。

各スイッチは、受信したメジセージ　バゲントをその［
１的ホス１〜に１；１Ｊりて自動的に経路指定するため
の経路指定メカニズムを有する。即ら、本発明の径路指
定メカニズムＧこよれば、多くのパゲントをネッＩ〜ワ
ークを通して同時に経路指定することができる。受信し
た各パケンＩ−毎に、ルータ−先ずパゲットを再送する
即らバゲットをその宛りＬに向けて経路指定するために
使用できろ出力リンクを表わす経路指定マスクを生成す
る。経路指定マスクは同報通信ビットを含む。もし同報
通信ヒツトがオンであれば、パチン１−は経路指定マス
クによって規定された全゛この出力リンクに同＋１；’
１′に経路指定されなければならない。もし同報通信ヒ
ノＩ・かオフであれば、パゲソトは経路指定マスク６、
二よって指定されたリンクの何れか１つに経路指定され
得る。

利用可能な出力リンクの集合は、経路指定されるのを待
機中のパケンＩ・のための全ての経路指定マスクと周１
す１的に比較される。どのパリーツトもその宛先に向っ
て進行するのを保証するために、対応経路指定マスクを
待ち行列内に配置することによってパケソＩ・ばパケｙ
　Ｉ・の到着順に処理さヨ）５る。

”先着順配慮゛′経路指定規律を使用すると、利用可能
な出力リンクに整合する１、♂舅）行列内の’、＋’Ｅ
：　ｌａ経路指定マスクが選択される。次て対応パゲッ
１〜の０ ために経路指定選択が生成され、選択された経路指定マ
スクが待ち行列から除去される。

本発明の付加的な目的及び特色は添附図面に基く以下の
説明からより容易に理解されよう。

〔実施例〕

第１図は不発１！Ｊｌによる網状接続１−　Ａ　Ｎの概
念図である。従来の網状ネットワークとは異なり、ノー
ドの特定の階層は存在せず、またネットワークのノード
を如何に相互接続するかに関する要求も存在しない。ネ
ットワークのノードは無作為に相互接続可能であり、し
かも適正に機能する。但し、充分に配慮された相互接続
の集合は若干良好な性能を呈するであろう。

ネットワークを使用するホス１〜コンピユータはＨで示
してあり、ＬＡＮを構成するノードをスイッチと呼びＳ
で示しである。この概念図では約８０のホストを相互接
続するために（６のスイッチを使用している。スイッチ
Ｓは多重ポート付きカットスルー非閉塞スイッチであり
、多数の入リンクを種りの選択された出力リンクへ同時
に結合する■ ことができる。これらのスイッチは、ネツトワークを通
して多くのデータ　パケツトを同時に経路指定すること
ができる。

非閉塞スイッチ 第２図のブロック線図を参照する。各スイッチ２１０の
主成分は非閉塞りｉ：Ｉスハ　スイッチ２１２、リンク
制御ユニット２１４とも呼ばれる複数の（好ましい実施
例では２）スイッチ　ボート、スイッチ制御プロセッサ
（ＳＣＰ）２１６、及び経路指定論理回路とも呼ばれる
ルータ２１８である。

またスイッチ制御プロセッサ２１６と呼ばれるマイクロ
プロセッサをクロスバ２１２に粘合する特別なリンク　
ユニット２１４ａも存在している。

リンク　ユニ・ン１−２１４　ａは５ＣＰ２１６をクロ
スバ２１２へ結合するので、５ＣＰ２１．６はネットワ
ーク内のホストコンビュークと同一の通信メカニズムを
使用してクロスバ２１２を介してデータ　パケットを送
り、また受けることができる。

各リンク　ユニット２１４はクロスバ２１２を１つの全
二重リンク２１５へ結合する。各リンク■ ２１５は２データ　チャネルを有し、従ってデータはリ
ンク２１５を通して同時に両方向に送信することができ
る。従って、各リンク　ユニット２１４は２つの成分、
即ち入力リンク　ユニット２２０（Ｒｘ）及び出力リン
ク　ユニット２２２（Ｔ×）を有する。

スイッチ２１０が新データ　パケットを受信すると、そ
のデータ　パケットを受信中の入力リンク　ユニット２
２０はクロスバ２１２ｃこまって出力リンクユニット２
２２ａ　（人力リンクとは異なるリンクのためのユニッ
ト）に結合される。出力リンク　ユニット２２２ａは受
信したデータパケットを別のリンクを通して再送信し、
それによってそのパケットを宛先に向かわせる。クロス
バ２１２は入力リンク　ユニッ）２２０のどれをも同時
に別個の出力リンク　ユニット２２２ａに結合すること
ができる。この理由がらスイッチ２１０を非閉塞スイッ
チと呼ぶのである。

ルータ２１８の目的番よ、どの出力リンク　ユニット２
２２を各入力リンク　ユニット２２０へ結３ 合すべきかを決定することである。人力リンクユニツト
　２２０は新データ　パケット・を受信すると経路指定
要求をルータ２１８へ送る。経路指定要求は、パケット
の宛先及び人力リンク　ユニットの識別を指定する。図
示のように、リンク　ユニット　２２０はバス２３０を
通してパケットの宛先アドレスをルータ２１８へ送る。

パケットの宛先アドレスは各パケットの始めに、最初の
数ハイドから入手すること番こ注目されたい。

宛先アドレスは、パケットが送られつつあるネットワー
ク　メンバーを指定する。

ルータ　バス２３２はリンク　マスクを含み、該マスク
は各リンク　ユニットに対応する１ビツト、プラス４ビ
ツトのリンク索引、１同報通信ビット及び有効フラグを
含む。ハス２３２のリンクマスク部分の各ラインは、ル
ータ２１８とリンクユニット２１４の１つとの間の単一
ピント通信ラインと考えることができる。可用性フラグ
が各出力リンク　ユニット−２２２から周期的にルータ
２１８へ送られる。可用性フラグは、出力リンク４ が話中ではなく、“閉塞されていない゛°状態にあり、
従って新データ　パケットを経路指定するために使用で
きる場合に゛オン゛となる。出力リンク　ユニツトは、
リンク（即ち出力リンク　ユニットが結合されているリ
ンク）の他方の端のスイッチが流れ停止コマンドを送っ
た場合に閉塞される。流れ停止コマンドは、リンクの他
方の側のスイッチがそれ以上のデータを受信不可である
ことを表示する。出力リンク　ユニット２２２が話中で
あるか或は閉塞されると、その可用性マスクは′“オフ
“になる。出力リンク　ユニット２２２の１３の可用性
マスク　ビットはルータ２１８によって周期的にサンプ
ルされ、経路指定選択を行うために使用される。

人力リンク　ユニツト〜　２２０から送られる情報を使
用して、ルータ２１８はどの（単数或は複数の）出力リ
ンク　ユニノド２２２をデータ　パケツトの再送信のた
めに使用すべきかを決定する。

ルータ２１８によって行われる経路指定選択はルータ　
ハス２３２を介してリンク　１−ニノＩ２１４及びクロ
スバ２１２へ送信され、これらは経路指定選択を使用し
て指定された接続を準備する。

大力リンク　ユニット２２０と出力リンク　ユニツトと
の間の接続は、以下のようにしてクロスバ２１２によっ
てなされる。要約すれば、ルータ２１８が新リンク選択
を発行する度にクロスバ内の２つのマルチプレクサがセ
ン＋−されて、選択された入力リンク　ユニットが選択
された出力リンク　ユニットに結合する。一方が人力リ
ンク　ユニットからのデータを出力リンク　ユニツト〜
・＼送信している間に、他方が流れ制御信号を人力リン
ク　ユニットへ送信して戻すために、２つのマルチプレ
クサが必要なのである。同報通信パケツトが送信される
時にリンク選択信号によって準備されるマルチプレクリ
−の数は、使用されつつある出力リンクの数に依存する
。

初期の好ましい実施例は１ダースのスイッチボート（即
ちリンク　ユニツト〜）２１４しか有していないが、将
来ユニン）・はまり多くのボートを有することに４（ろ
・）。

６ ＳＣＰ２１６は標準マイクロプロセッサ（例えば、好ま
しい実施例においては；〔１−ローラ製６８０１０マイ
クロプロセツサが使用されている）であり、スイッチ２
１０が電源投入された時或はリセツトされた時にはルー
タ２１８を再ロードするように、及びネットマークのあ
る成分が障害を起こすか或は新成分がネットワークにイ
１加された時には再構成を遂行するようにプログラムさ
れている。ＳＣＰはＳＣＰハス２２５によって全てのリ
ンク　ユニット２１４にも結合されているので、ＳＣＰ
はリンク　ユニットのステータスを監視することができ
る。

水二え社狙 ネットワーク内の各スイッチには４８ビットのＵＩＤに
加えて独特な７ビントの類ＩＤが割当てられる。類ＩＤ
はイ、ノドワークの構成中に割当てられ、何れの特定ス
イッチの類ＩＤもネットワークが再構成される時に変更
できる。各ホス１〜　コンピュータには１１ビツトの°
′ネットワーク　アドレス°゛が割当てられる。ホスト
　コンピユークフ のネ・ノドワークは、そのスイ・ンチの類ＩＤと、ホス
トをスイッチに結合するリンクボートのＡピント値とを
連結することによって生成する。各スイッチのネットワ
ーク　アドレスは、その短ＩＤプラスＳＣＰリンク　ユ
ニットのリンク番号に対応する予め定められた４ピツ１
〜値（例えば０）である。

ネットワーク　アドレスは、ネツトワークを通して送信
されるパケットの宛先を表示するために使用されるアド
レス値である。

各ネッＩ・ワーク　メンバーにネツトワーク　アドレス
並びにＵＩＤが割当てられている理由は、ネッＩ・ワー
クを通るパケットの経営指定を容易にするためにより短
い値が必要であったからである。

７ビツトの類ＩＤは１２８までのスイッチを準備する。

各スイッチは多くとも１２の外部ボートを有しており、
その中の少なくとも１つはスイッチをネットワーク内の
別のスイッチに接続するために使用しなければならない
から、多くとも１４０８のホストが存在し得る。これは
、予測される本発明８ の全ての応用に対して充分以上であると３１１持される
。勿論、ネッ１〜ワーク　メンバーの許容数は、単に１
２ヒソＩ・のネントワーク　アドレスを使用することに
よって２倍にすることができる。

データ　パケツトを先ず送信する時、データパゲ・ンＩ
・を送ろうとするネンｌ〜ワーク　メンバーのネットｉ
ノーク　アドレスがパケットの最初の数ハイド内に記憶
される。ルータ２１８は、不ツＩ〜ワーク　アドレスの
値とそのパケツトを受げている人力リンクとを使用して
どの（単数或は複数の）出力リンクをデータ　パケット
の再送信のために使用ずべきかを決定する。

要約すれば、本発明の経路指定メカニズ１、のＩ］的は
、システム資源（即ら出力リンクを公平、公正にデータ
　パケツトに割当てることである。詳細を後述するよう
に、本発明は資源に対する要求と使用可能な資源の集合
とを要求を受↓」た順序に比較する先着順配慮経路指定
を提伊する。使用可能な資源に整合する最初の要求が選
択され、その要求か必要とする資ｌＡ力砧１１当てられ
る。次いでプ０セスば繰返される。

先着順配慮経路指定規律を使用すれば、後着要求は、割
当てが先行要求の必要と競合Ｌ　ｆ：ｃい１１１４す、
先行要求の前に資源に割当てることができる。この経路
指定規律は、使用可能な資源を資源要求粁に割コてるこ
とができるレー　１−をｊニ人にする。同報通信データ
　パケットの場合に番よこの経路１に定規律は、要求さ
れた資源が同報通信要求によって保留されそれによって
後着要求が同報通信データパケットの進行を妨害するの
を防くことを意１味する。

第３図は、好ましい実施例に使用されているルータ回路
２１８の基本成分を示す。第２図で説明したように、ル
ータ２１８はハス２３０からパケット宛先アドレスを受
信する。経路指定アドレス及び出力リンク可用性信号は
、ルータ２１８によるリンク選択埴の伝送と共にルータ
　ハス２３２上に時間多重化される。

各゛経路指定子Ｉ−レス゛は１ピントのパゲノ１アドレ
ス及び４ヒノ１〜の人力９フク番ぢを含む。

０ 経路指定アドレスはレジスタ４２０内に記憶される。経
路指定アドレス　２　Ｌ；ｌ：、経路指定アドレス値に
よって索引されるルンクアソブ　テーブルである。

経路指定表４２２は、経路指定アドレスに対応するパケ
ットを経路指定するために潜在的に使用できる出力リン
クを指定する考え得る全ての経路指定アｌζレス値のた
めのエントりを含む。

人力リンク　ユニットは、その先入れ先出しくＦ　Ｉ　
ＦＯ）ハンファの出力に新パケンＩ・の受信を検出する
と、ルータ　ハス２３２のリンク　マスク部分２３２Ａ
上に要求信号を送る。

経路指定要求セレクタ回路４２４はハス２３２Ａ−Ｌに
経路指定要求が発生したか否かを監視している。何れか
の経路指定エンジン　サイクル中に１或はそれ以」二の
経路指定要求が発生ずれば、セレクタ４２４は要求の１
つを選択する。選択された要求は、適切な時点に“オン
“信号をバス２３２Ａを介して選択されたリンク　ユニ
ット・へ送ることによって１牙定応答される。この肖定
応答信号は信号したリンク　ユニットに該ユニットがそ
の経路１ 指定要求をハス２３０を介して伝送する、Ｌうに選択さ
れたことを通知し、次いで選択された入力リンク　ユニ
ットばその経路指定要求に関するパろット宛先アドレス
をパス２３０を介してハンファ４２０へ送る。

要求セレタク回路／１２４は巡同優先順位エン：Ｉ−ダ
であり、要求が選択された最後のリンク　コーニントの
競合要求の中から選択するための優先！唄位を基礎にし
ている。これにより全ての要求は短時間中に受入れられ
、パケットが枯渇するのを１υｊ止する。

各経路指定要求は、ライン２３０から受ける１１ビツト
のバケット宛先アドレスと、要求セレクタ回路４２４に
よって与えられた関連４ビット入力リンク番号とを含む
。経路指定表アドレスは経路指定表４２２によって使用
されるようにレジスタ４２０内に記憶されている。経路
指定表４２２はランダムアクセス記憶装置（ＲＡＭ）内
に記憶され、レジスタ４２０内の１５ビット値は経路指
定表４２２からのある値（経路指定マスクとＩｌｌばれ
２ る）を検索するためのアドレスとして使用される。

経路指定表４２２によって選択された経路指定マスク出
力は、後述するように次の経路指定エンジンサイクルの
始めに経路指定エンジン４３０によってランチされる。

ｖｉ：路指定表４２２は、老え得る全ての経路指定要求
のためのエントリを含む。換言すれば、人力リンク番号
とパケット宛先アドレスとの全ての考え得るお１合せの
ためのエン１へりを有する。これらの２つのイ直ば１５
ピツＩ・を占めるから、表４２２内のエントリ数は２′
５即ち３２，７６８になる。各エントリしよ記憶装置の
２ハイ１−を占め、従って表４２２は６５．５３６ハイ
トの記憶位置を必要とする。典型的には、経路指定゛表
内のエントりの中の小さい数だけが“′正当な”経路指
定要求を表わし、他の全ては不正な、即ち不当な要求値
を表わすことになろう。不当要求の表エンＩ・りは全て
が０である。但し１゛に等しくセットされる°゛同同報
通信ッＩ・“。

を除く。もしデータ　バケットが不当経路指定要求を生
成ずれば、そのデータ　バケットはスイッ３ チから追放される。

８０のネットワーク　メンバーを有するネツトワークに
おいては、合計８１程度だけの正当なバケット・　アド
レスが存在しよう。即ち、各不ッｌ−ワーク　メンバー
に１つ宛のアドレスと、パケ、。

トをネツトワークーにの全ホストへ送るための１或はそ
れ以上の゛′同同報通信子アドレス含む。また入力リン
ク番号とパゲット　アドレスの若干の組合せは、それら
がバケットを宛先から遠去ける経路に対応するか、或ば
デッドロックを発生ずる恐れがあために不当であろう。

従って、８ｏのメンバーのネッ［・ワークにおいては、
特定のスイ・７チのための経路指定表４２２は３２０乃
至７５　（）の正当エントりをイｆ才ることにｔくろう
。

経路指定表４２Σ内の各エン１〜りば経路指定マスクを
含む。経路指定マスクの例は 経路指定表アドレス 入力リンク　バケット・　　アドレス ０１１．０　　１１．００１１００１１０４ 経路指定表内の各アドレスは入力リンクから受信し得る
考えられる経路指定要求の１つを表わし、従ってごこて
は入力リンク番号及びバケット　アドレスを連結して表
わしである。

芥経路指定表エントリ内の経路指定マスクは、ＳＣＰを
含むスイッチの各出力リンクに１つ宛の１３のマスク　
ビットを含む。各マスク　ビットは“オフ゛゛である時
（即ち“１”に等しい時）に、バケットを経路指定する
ために使用できる出力リンクを表わす。経路指定マスク
は、そのパケットアドレスが同報通信であるか或は通常
アドレスであるかを表わす同報通信ビットＢＣをも含む
。

経路指定マスクの例を第４図に示す。第４図には経路指
定マスクの上に有効ビットを、また経路指定マスクの下
にリンク番号も示しであるが、その理由は後述する。

５ 同報通信ビットＢＣが゛オン”（即ち“１”に等しい）
であれば、そのバケット・は同報通信パケットと呼ばれ
る。同報通信パケットは、経路指定マスクによって指定
された全ての出力リンクに同時に経路指定しなげればな
らない。

もし同報通信ビットが゛オフ゛（即ち“０”に等しい）
であれば、そのパヶソ１へば非同報通信パケツト・と呼
ばれる。非同報通信パケットの場合には、経路指定マス
クはバケットをその宛先に経路指定するために使用でき
る各出カリン’／％に゛１パに等しいマスクピッ１〜を
有する（即ら、バケットは経路指定マスクによって指定
される出力リンクの何れか１つに経路指定できる）。多
くの場合、若干の異なる出力リンクを交互にバケツト〜
をその宛先に向けて経路指定するために使用することが
でき、これが網状接続ネットワークの長所の１つである
。経路指定エンジン４３０はバケットを経路指定する経
路指定マスクによって指定された出力リンクの特に１つ
を選択する。

第４図は、経路指定エンジン４３０内へ入力さ６ れる時の経路指定要求４２５の正確な書式を示す。

有効フラグと呼ばれる」二部ピッ１〜は、経路指定要求
が経路指定エンジン４３０内ヘロードされると“１”に
七ットされ、経路指定エンジン４３０内ヘロードする新
しい経路指定要求が存在しない時に０゛°にリセットさ
れる。次の１４ピントは前述のように、経路指定表４２
２による経路指定マスク及び同報通信ビット出力である
。最後の４ビツトは、経路指定中のパケットの人力リン
ク番号である。

経路指定エンジン４３０は、現在使用可能な出力リンク
を表わすリンク可用性マスクと経路指定要求とを化較す
る。詳述すれば、経路指定エンジン４３０の目的は、各
新バケン１〜の出力リンク要望とスイッチの使用可能な
出力リンクとを整合させることである。経路指定エンジ
ン４３０によって生成された経路指定選択値は、クロス
バ２１２（第２図）がそのマルチプレフナを準（ＩＩＮ
　シ、それによって指定された人力リンクをｌ或はそれ
以」−の指定された出力リンクに接続するために使用す
７ 第２図に関して説り１したよ・うに、各出力リンクユニ
ント２２２はその出力リンクが経路指定のために使用可
能であるか、或は既に使用中或は閉塞されているの何れ
かであることを表わす゛リンク使用可能゛信号を伝送す
る。ハス２３２ば企ての出力リンクからのリンク使用可
能信号ラインを含む。ルータ２１８はハス２３２上のリ
ンク使用可能信号を周期的にサンプルし、それらを内部
に記憶する（第５図るこ列４６５で示す）。経路指定エ
ンジン４３０は経路指定選択を行う時に使用可能リンク
マスクを使用する。

経路指定エンジン４３０は経路指定要求と１或はそれ以
上の使用可能リンクとを整合さセるごとかできると、経
路指定選択値を生成してハス２３２上へ出力する。経路
指定選択値は４ヒソ１−の人力リンク番号、同報通信ビ
ット及び満足された経路指定要求からのイー■効ヒツト
、及び人力リンクに粘合される単数の或は複数のリンク
を識別する出力リンクマスクからなる。入力リンク番号
、同報通８ 信ビット及び有効ビットは２３２Ｂと名付けたルータ　
ハスの部分に伝送され、出力リンクマスクば２３２Ａと
名付けたルータ　バスの部分に伝送される。ルータ　ハ
ス２３２に伝送された経路指定選択値は、指定された入
力リンクを１或はそれ以上の指定された出力リンクに接
続するために入力リンク　ユニッｌ、　２２０、出力リ
ンク　ユニット２２２及びクロスバ２１２（第２図）に
よって使用される。

パ有効°“出力ビットは経路指定エンジン４３０が新経
路指定選択を出力サイクル中のみ“オン”となる。即ち
経路指定エンジン４３０から出力される“有効“ヒソｌ
−は、経路指定エンジン４３０が懸案の経路指定要求の
何れかと使用可能出力リンクとを整合させ得ないサイク
ル中は゛′オフ“°である。

制御回路４３５は経路指定エンジン４３０及び要求選択
回路４２４のためのクロック信号を生成する。これらの
クロック信号はパケット　アドレス　ハス２３０及びル
ータ　ハス２３２の使用も９ 制御する。そのタイ旦ング　プロＩ・コルは第６図を参
照して後述する。

経路指定エンジン 第５図は、経路指定エンジン４３０の好ましい実施例を
示す。この実施例↓こおいては、経路指定エンジンは計
算成分のアレイ４５０から形成され、各成分は第５図に
箱で示されている。図示のアレイはシリンクス（Ｘｉｌ
ｉｎｘ）社が製造しているシリンラス３０９０アレイと
呼ばれるプログラマブルゲート　アレイを表わす。シリ
ンラス３０９０は１６の列を含み、各列ば２０の組合せ
論理ブロック（ＣＬＢ）を有する。Ｃ１，Ｂは種々の論
理及び記憶機能を遂行するように電気的にプロゲラＪ、
することができる。各ＣＬ　Ｂば、２つのフロップ。

フロップ及び２つの機能単位を含む。各機能単位は４人
力変数までのどのプール関数も計算することができる。

ＣＬ　Ｂは、機能単位から或はフリップフロップから直
接得ることかできる２つの出力を発生する。また各ＣＬ
　Ｂ　１１１＝を近には２つのトライステート　ドライ
バも存在する。これらのドライ０ ハばチップを横切る水平金属［・レースに接続可能であ
り、ハスを構成することがてきる。プロゲラｌ、可能な
論理を提供する他に、シンリクス３０９０アレイは近隣
ＣＬ　Ｂ間の、及びアレイの外側の回路へのインフッ１
−スを提供する複数の埋込みセル間のプロゲラｌ、可能
な相互接続をも提供する。即ち、アレイの挙動及び機能
は、外部源（例えば各スインチ内の５ＣＰ）からアレイ
内に１１−ドされる制御ビットのパターンによって決定
される。チップ製造の一部としてのカストマイズは行わ
れない。

経路指定エンジン　アレイ４５０ば、それぞれが１９論
理ブロツクを有する１３の列４５１〜４６３を使用して
いる。これらの各列４５１〜４６３は単一の経路指定要
求を記憶し、処理する。更に、チップの右側には１３の
作動可能信号発生器（ＲＧ）の列４６５、及び１７の出
力信号発生器（Ｏ及び０′）の列４６８が存在する。ア
レイ内の各論理ブロックに関して以下に説明する。

しかし、先ず第５図に示ずアレイ４５０の総合動作方法
を説明することが有用であろう。経路指定要求ばアレイ
の左イ１１すから受信される。アレイの左側に示す信号
記号は、第４図に示ず経路指定要求の書式に一致する。

信号ＲＤＹＯ乃至ＲＤ￥１２によって表わされている出
力リンク可用性マスクばアレイ４５０の右側から受信さ
れる。

経路指定エンジンによって行われた経路指定選択である
アレイ４５０からの出力は、アレイの右側から出力バス
４７０上に現われる。第３図に関して説明したように、
経路指定選択は１９ビット、即ち経路指定選択が行われ
たことを表わす１つの有効ビット、１３ビツトの出力マ
スク、１つの同報通信ピント、及び経路指定要求からの
４ピントの入力リンク番号を含む。

アレイの１３の列４５１〜４６３は、本発明の先着順経
路指定規律を実現する待ち行列として作用する。待ち行
列の右側の列は最も古い満たされていない経路指定要求
を保持し、左側の列はより最新の要求を保持している。

２ アレイ全体は周期的なりロック　サイクルで動作する。

経路指定エンジンは６クロンク　サイクルの各期間中に
１経路指定要求を受入れ、この６クロツクサイクル期間
中に１回の経路指定選択を試みる。

第６図に示すように、各経路指定エンジンは、Ｔｏ乃至
Ｔ、と名付けた６つの相を有する。各相の持続時間は８
０ナノ秒であり、従って合計経路指定エンジン　サイク
ルは４８０ナノ秒である。

経路指定エンジン　サイクルは、クロック信号ＴＯ３に
よって表わされている１つの主要副相を有する。第１の
副相中はＴＯ３＝１であり、第２の副相中はＴＯ３＝Ｏ
である。

以下に説明するように、ルータ２１８へ経路指定要求を
送り、その要求を処理し、そしてリンクユニット及びク
ロスバへ経路指定選択を送るためには３経路指定エンジ
ン　サイクルを必要とする。

経路指定要求は以下のようにしてルータ２１８へ送られ
る。Ｔ４中に、ルータへ送る必要がある３ 経路指定要求を有する各入力リンク　ユニツトシよルー
タ　バス２３２の対応ライン上に“′オン′”信号を供
給する。経路指定セレクタ刊路４２４　＆；Ｉ：１゛４
中にルータ　バス２３２を監視し、経路指定要求が供給
されているか否かを見出す。もし１つの要求だけが供給
されていれば、それば）ｊ゛定応答される。何れか１つ
の経路指定エンジン　サイクル中に、１つよりも多い経
路指定要求が供給されていれば、経路指定セレクタ回路
４２４は前述のようにして１つの要求だけを選択する。

選択された要求は、次の経路指定エンジン　サイクルの
Ｔ２中に、選択されたリンク　ユニット・ヘバス２３２
を介して°′オン”′信号を送ることによって肯定応答
される。この肯定応答信号は選択された信号されたリン
ク　ユニットにその経路指定要求をハス２３０を介して
伝送するように命令する。クロック相Ｔ３乃至Ｔ５中に
、選択された入力リンク　ユニットはその経路指定要求
に関連するパケ・ント　アドレスをバッファ４２０を介
して経路指定表４２２へ送る。経路指定表４２２が４ アクセスされ、その経路指定要求に対応するリンク　ヘ
クｌ〜ルが１゛５の終りによってその出力において作動
可能になる。

相Ｔ５中に全てのリンク　：Ｉ−ニラＩ・はそれらの可
用性フラグ値をルータ　ハス２３２上へ供給するので、
これらの信号は次の経路指定エンジンサイクルの始めに
経路指定エンジンのための準備が整うことになる。

ＴＯの始めに経路指定エンジン４３０は、ルータ　バス
２３２からのリンク可用性フラグと、もしあれば現経路
指定要求とをランチする。現経路指定要求は、経路指定
表４２２によるリンク　ヘクｌル出力、要求選択回路４
２４によるリンク番号及び有効ビット出力とからなる。

経路指定エンジン　リサイクルＴ　Ｏ乃至Ｔ５の残余の
間、経路指定エンジン４３０はランチしたリンク可用性
データと、経路指定エンジン４３０のデータ列内に記憶
されている満たされていない経路指定要求とを比較する
。この比較の結果ばＴ５の終りに経路指定エンジンの出
力列内にラッチさ５ れる。しかし、経路指定エンジンによって生成される経
路指定選択は、後続する経路指定エンジンサイクルＴ１
までルータ　ハス２３２上ＧこＵｊ　袷されない。この
ルータ　サイクルの′Ｉ゛１乃至Ｔ　５中、もし経路指
定選択の有効ピノ１〜か゛オン゛であれば、リンク　ユ
ニント及びクロスバは指定された人力リンクを指定され
た（単数或し、ｌ複数の）出力リンク　ユニノ１〜に結
合するように経路指定選択出力を処理する。

要約ずれば、ルータ２１８の各部分は各経路指定サイク
ル中に異質のタスクを遂行する。更に、ルータ　バス２
３２は経路指定要求を経路指定要求セレクタ４２４へ送
るためと、経路指定選択をリンク　ユニントへ送るため
に時間多重化されている。

６Ｘ８０ｎＳのりｌコック　リサイクル０７段をイアす
る３段パイプラインとして使用されているルータ２１８
は毎秒２００万パゲン］・よりやや多いバケソトを経路
指定することができ、各パケントの通路に約１．４４マ
イクＵＪ秒／スイソチの（，１ｔ）ｌＬ’１問を６ 付加する。ルータ　パイプラインの３段とは、（１）経
路指定要求マスクを生成するための入力リンク選択及び
経路指定表探索、（２）経路指定エンジンサイクル、及
び（３）経路指定選択をクロスバ２１２及びリンク　フ
、ニットへ伝送する。

以下に経路指定エンジン　サイクルの各相中の経路指定
エンジンの動作を詳細に説明する。各経路指定エンジン
　サイクルの始めに、即ちＴ”　０の始めに、経路指定
要求及び使用可能な出力リンクマスクが読め込まれる。

経路指定要求はアレイ４５１の最左列内にラッチされ、
リンク可用性マスク（ＲＤＹＯ−４？ＤＹＩ　２）は作
動可能信号列４６５内ヘラツチされる。更に、既にアレ
イ内に記憶されているが満たされていない各経路指定要
求は、もし満たされない要求によって占有されていない
少なくとも１つの列がアレイの右に春在していれば、ア
レイの右へ１列移動させられる。

経路指定エンジン　サイクルの第１副相中、数組の信号
がアレイを横切って伝播する。第１に、リンク可用性マ
スクがアレイを右から左へ横切っ７ て伝播する。各要求ハン］・リング列４５１〜４６３内
の回路は、それらの列内に記憶されている経路指定要求
とリンク可用性°７クスとを比較する。非同報通信要求
を記憶している列（Ｂ　Ｃ＝　０の列）において、もし
少なくとも１つの可能化された゛マノ、り”′ビットが
可能化されたＲＤＹヒツトとが一救すれば、“′整合゛
′信号を生成する。即ら、ＲＤ　Ｙ−１の値によって表
わされる各使用可能なリンクはアレイ４５０内に記憶さ
れている経路指定マン、りの対応ピッ１〜と比較される
。使用可能なリンクのためのＲＩ）　Ｙ信号が、その経
路指定マスクの対応ビットが′°オン゛′である経路指
定要求に遭遇すると、その列のための゛整合゛信号が生
成される。

同報通信要求を記憶、している列（ＢＣ＝１の列）にお
いては、全ての可能化された“マスク゛ヒノトが対応Ｒ
Ｉ）　Ｙピントに−・致する場合に限りＣ１ｉ＋１ち、
要求によって必要とされる全出力リンクが使用可能であ
る場合に限り）゛整合”信冒が生成される。

同報通信要求を記憶している（ＢＣ＝１）列むｊ、８ 同報通信要求の゛マスク”ヒツトと一致するＲＤＹ　ｉ
へ３７’、の（１，幡を１ｕｌｌ　ｔトする。実際には
、同報通信要求は、その要求によって必要となった使用
可能出力リンクを“反転パさせる。もしこれが行われな
む１れば、同報通信パケットによって必要とされる個々
の出力リンクと一致し、これらを使用する爾後の要求に
よって同報通信パケ・ノド＆Ｊ恒久的に阻止されること
になる。

゛整合°゛信号は、一致が見出された列を上方にイ云団
する。即ち、“整合゛信号【ま経路指定エンジン　サイ
クルの第１副相中に伝播する第２＆１１の信Ｂである。

２或はそれ以上の列が゛整合パ信号を生成する可能性は
極めて高い。従って、最古の要求に最優先順位を与える
ためには、一致を見出した最も右の列を選択する必要が
ある。このようにするために、“応答済み“′と呼ふ信
号がアレイの頂部のＣＩセルを右側から左側へ信器する
。゛応答済み”信号は、使用可能整合信Σを右する打効
列（即ち有効−１）に出逢うまでその値が０“であり、
９ 有効列に出逢うと値が“１゛になる。

′“応答済み”′信号しよ第３の型の信℃であり、経路
指定エンジン　サイクルの第１副相中に（云播される。

Ｔ４及びＴ５中乙こ出力可能化信号（Ｎ　Ｄ　’ｉｉＪ
能化）が、右隣りからＯ°゛の応答済み信号を受は且つ
可能化された整合信号を右する最右列に関して生成され
る。勿論、多くの経路指定エンジン　サイクル中はどの
列も使用可能リンク　マスクと一致・すす、出力可［ｉ
Ｅ化行信号生ｊ戊されない。暫時、出力可能化信号が１
つの選択された列のために生成される場合を考える。

何れか１つの経路指定エンジン　リ゛イクル中に多くと
も１つの列が可能化されたＮＤ可ｆｒ＝化信ぢを有する
ことになろう。もしどの列も可能化されたＮＤ可能化信
号を有していなければ、これは経路指定：［ンジンが利
用可能な出力リンクと−・致した経路指定要求を見出す
ことに失敗したことを意味する。

Ｔ４及びＴ５中に、一致した全ての経路指定マ０ スフ　ピント（即ち利用可能な出力リンクが存在して可
能化されたマスク　ピント）、及び選択された列の同報
通信ビンＩ〜、リンク番号及び有効ビ・７トが右へ伝播
して出力処理列４６８へ入る。同報通信ヒｙ　ｌ・がパ
オフパであれば、アレイ内の最も下の可能化されたマス
ク　ビットのみが出力され、他の全てのマスク　ビット
は不能化される。

得られる経路指定選択値は、可能化された有効ピソト、
１つの可能化されたマスクビ・ント（同報通信パケット
である場合を除＜）、及び経路指定要求の同報通信ビッ
ト及び入力リンク番号をイ１することになろう。

この分野に粕通していれば、パケットが必要とする単一
の或は複数の出力リンクが話中であるかも知れないため
に、若Ｔのパケ・ノドは直ちに経路指定されないであろ
うことば明白である。従って、経路指定エンジン　アレ
イ４．５０の列４５１〜４６３は、満たされていない経
路指定要求が記憶され使用可能な出力リンクと周１１Ｊ
Ｉ的に比較される待ち行列として作用する。

１ 経路指定エンジンが使用可能な出力リンクと未決経路指
定要求との一致に失敗すると、アレイによって出力され
るデータは不能化された′イ・ｆ効°゛ビットを有する
。リンク　ユニソＩ・及びスインチ内のクロス八回路は
、°“有効゛′ヒツトが不能化されているサイクル中の
経路指定エンジンの出力を無視する。

以下に第５図のアレイ内の各論理ブロックカ旬ｒ１何に
作動するかを詳述する。

論理ブロック；ＲＱ 第７図は、第５図にＲＱとして示されている紹合せ論理
ブ１コンク（ＣＬＢ、）５２０を示ず。任意の回路ブロ
ックが如何に作動するかを理解するためには、先ず各ブ
ロンク毎の入力信号が何処から到来するか、及び各回路
ブロックの出力が如何に伝送されるかを考えなげればな
らない。

各論理ブロックの入力ラインは、各ブロソクの４つの最
寄り隣接ブロソク、即ち上及び下のＣＬＢ、及び左及び
右のＣＬ　１３内の信Ｂラインに結合することができる
。例えば、第７図においてフリ２ ノプフロンプ５２２へのデータ入力はこのセルの左のセ
ル内のＲＤ　Ｙ信号（ＲＩ）　Ｙ　（２１で示す）から
得ている。

同−ＣＬ　Ｂのアレイにおいて１つのセルの出力が隣接
セルの入力となり、従って各セルにおいて入力信号及び
出力信号の両方に同一・信号名が現われることに注目す
ることは重要である。信号を表わすために、隣接セルか
ら発セられた信号には“（右）°、“′（左）゛或は゛
（下）゛のように括弧内に源の識別名を記しである。図
示ＣＬ　Ｂが生成する信号ば空括弧”（）”によって示
しである。

更に、各列のＣＬ　Ｂを２つの水平データ　バスが通過
している。これらのデータ　ハスは信号を列４６８（第
５図参照）内の出力セルへ伝送するために使用される。

これらのう・インは、ＣＬ　Ｂのためのデータ　ライン
の一方だけが使用される場合には゛データ“と名付けら
れ、両方が使用される場合には“データ１°“及び“′
データ２゛と名付けられる。第７図においてはＲＱセル
５２０は一方３ の“データ”ハス　ライン５２４だけが使用されている
。データ　パス　ラインばトライステートバッファ Ｙ（　）出力に接続されている。後述するように、ＲＤ
Ｙ（　　）信号は経路選択信号“’ＮＤ可能化“が可能
化された時に限ってデータ　ハス上に伝送される。“’
ＮＤ可能化゛は可能化された時に“０”′の値を有する
負論理信号である。

回路ブロック５２０の動作の詳細は以下の通りである。

この回路５２０の左のセルからのＲＤＹ（左）信号は、
もし°’ＣＯＩ−可能化゛が可能化されていれば（即ち
“′１゛に等しりすれば）Ｔ５の終りにフリップフロッ
プ５２２内ヘランチされる。

明白なように、“ＲＤＹ　（左）“は回路５２０が位置
する列の左の列内に記憶されている経路指定マスク　ビ
ットに等しい。もし回路ブロック５２０が第１列４５１
内にあれば、ＲＤＹ（左）は読み込まれている経路指定
要求からの“マスクＸ°“信号の１つに等しい。ごの理
由から、フリップフロップ５２２の出力ライン５３０ば
“マスク（）′。

４ と名付けである。

整合論理回路５３１のプール式は 整合（　）−同報通信木整合（下）＊（〜マスク（）−
１−ＲＤＹ（右）） 十〜同報通信木（整合（下）１− マスク（）＊ＲＤＹ（右）） である。但し、“＊゛′はブ−ルＯＲ関数を表わし、“
十“はブールＯＲ関数を示し、“−゛はブ−ルＯＲ関数
を意味する。上式は、もしく１）この列に記憶されてい
る要求が同報通信パケットのためのものであり、且つ“
整合信号°“が下の隣接セルによって生成されたもので
あり、且つマスク　ビット“マスク（）°がオフである
か可用可能な出力リンク信号“”ＲＤＹ（右）”がオン
の何れかであれば、或は（２）この要求が非同報通信の
ためのものであり、且つ“整合パ信号が下に隣接するセ
ルによって生成されたものであるか或はマスク　ビット
“′マクス（　）“及び使用可能な出力リンク信号゛Ｒ
ＤＹ　（右）“が共にオン（即ちＲＤＹビン１−がマス
ク　ビットに一致）であれば５ 可能化されたパ整合（）°゛信号出力されることを意味
する。

整合信号は制御論理セルＣ１及びＣ２に至るまで各列を
上方へ伝播する。整合条件ば同報通信ど非同報通信とで
は異なる。非同報通信の場合には、何れかのビットが整
合すればその列が可能化された“′整合（）″信号を生
成するのに充分である。

同報通信の場合には、可能化された真“′マスク（）゛
ビットを有する全てのセル５２０が、満たすべき要求の
到来”ＲＤＹ（右）°“ビットと生成ずべき可能化され
た“整合（　）”′信月とに整合しなければならない。

第５図のアレイ４５０内の列の頂部のＲＱ全セル場合に
は、パ整合”出力信号に与えられる信号名は“整合”で
はなく“完全整合である。アレイ内の各列の最も下のＲ
Ｑ全セル場合には下のセルからの入力との整合はないか
ら、“整合°°論理回路のプール式は 整合（最下セル）−同報通信＊（〜マスク（　）−Ｉ−
ＲＤＹ（右）） ６ −１〜同報通信＊マスク（） ＊ＲＤＹ　（右） である。即ち、各列の最下ＲＱセルの場合には、経路指
定マスク　ピント°マスク（）°が使用可能ラインＲＤ
Ｙ（右）に一致すれば非同報通信要求に対して、或は経
路指定マスク　ビット′°マスク（）′がオンではない
か或は対応するＲＤＹヒソトがオン（即ちＲＤＹ　（右
）に対応する出力リンクが使用可能）の何れかであれば
同報通信要求に対して“整合゛信号を生成する。

ＲＤＹ論理回路５２６のプール式は ＲＤＹ（）＝ＴＯ３＊ＲＤＹ＊　（右）〜（同報通信＊
マスク（）） 十〜Ｔ０３＊マスク（） である。この式は、各経路指定エンジン　サイクルの第
１副相中に、同報通信要求が処理中でなく珪つ右側セル
のマスク　ピントがオンでなければ、Ｔ　Ｏ３−１の時
にはＲＤＹ（）が右側セルからのＲＤＹ信号に等しいこ
とを意味する。換言すれば、第１クロソク副相中に、同
報通信要求が要求マス７ り　ビソＩ・がオンである行内のＲＤＹの伝播を楚止し
ている場合を除いて、ＲＤＹ信号ばアレイの右側から左
へ伝播することが可能である。

各経路指定エンジン　サイクルの第２副■１中にＴＯ３
＝Ｏである場合は、ＲＤＹ（）はマスクビット°マスク
（）”に等しい。即ち、第２クロツク副相中に、Ｒ１）
Ｙ（）信号は要求マスク　ヒントを１つのセルから右へ
伝播さ一吐′るために使用される。

ＲＱ論理ブ１コック５２０の動作は、他の論理ブロック
の動作を説明すれば、より明白になるであろう。

ラッチ　ブロック：　ＬＮ、ＢＣ，Ｖ 第８図に示す論理ブロック５４０は、第５図にＬＮ’”
と名付けたブロックに対応する。この回路は、経路指定
要求に伴う人力リンク番号を槽底している４ピントの中
の２つを記憶するために使用される。これらの２ビツト
値は、次に左の列から、或は左端列４５１の場合には要
求選択回路４２４（第３図）から、ライン１　（左）及
びライ８ ン２（左）と名付けたラインを介して安心ノ゛る。その
列のＣＯＬ可能化がオンであれば、ライン１（左）及び
ライン２（左）」二のビソト（直はＴ５の糸冬りに２つ
のフリップフロップ５４２及び５４４内にラッチされる
。

第１クロツク副相の終り（即ち′Ｆ０３の終り）に”Ｎ
Ｄ可１１Ｌ化”が可能化（即ち”　ｏ　”にセラ１〜）
されていれば、フリップフロップ出力ライン５４６及び
５４８」二の信号はトライステート　ハンファ５５０及
び５５２によってデータ　ハス“データ１′”及び゛′
データ２°゛へ結合される。換言すれば、人力リンク番
号が出力列４６８へ伝送される。

第９図は、第５図に”　ｖ　”で示すブロックに対応す
る論理ブロック５６０である。この回路は、経路指定要
求に伴なう“′有効ピンドパを記憶するために使用され
る。未決経路指定要求を含む列のみが可能化された有効
ピントを有する。有効ビットは次に左の列から″有効（
左）′”ラインを通して供給される。経路指定エンジン
の左端列４５１内の回路の場合には、有効（左）入力は
要求選択９ 回路４２４（第３図）から到来する。

もしその列のＣＯＬ可能化がオンであれば、ＮＤ可能化
（左）と論理的にＡ　Ｎ　Ｄされた時の有効（左）の値
がＴｏの始めにフリップフロップ５６２内ヘランチされ
る。ＡＮＤゲート　５６３の目的は以下の通りである。

各列内のＮＤ可能化信号ば通常は“１°゛に等しく、従
って有効（左）信号は変化セ゛ずにＡＮＤゲー１−５６
３を通過する。しかしＮＤ可能化信号は、ある列におい
て経路指定要求が出力されるように選択されると“′０
゛に等しくセットされる。爾後のサイクル中に要求が供
給してしまわないようにするために、同報通信及び有効
信号のためのシフトレジスタの人力はＮＤ可能化（左）
とＡＮＤされる。これは、ある列がある結果を供給し、
同一サイクル中に移動させるのであればその要求は無効
化され、次に右の列へ移動する時に同報通信ピント・が
クリヤされることを意味する。

左端列４５１内の回路５６０の場合には、経路指定要求
セレクタ４２４からの有効ビットはフリ０ ンプフロン１５６２の入力へ直接印力Ｉ＋される。

もし第１り１コノク副相の終り（１１１らＩ”　０３の
終り）にＮＤ可能化信号が可能化（即ち０゛にセット）
されれば、フリップフＩコンブ出カライン５６４上の信
号はトライスデート　バッファ５６８によってデータ　
パス５６６へ伝送される。

第１０図の論理ブロック５７（）は第５図のＢＣ°′で
示すブロックに対応する。この回路は経路指定要求に対
応イ１けられた同報通信ビットを記憶するために使用さ
れる。同報通信ビン１は同報通信要求に対してパ１°゛
に等しく、非同報通信要求に対して°゛０゛に等しい。

同報通信ピント・ば、次に左の列から“同報通信（左）
′°ラインを通して印加される。左端列４５１内の回路
５７０の場合には、゛同報通信（左）°“人力は経路指
定表４２２（第３図）から印加される。

もしその列のＣＯｆ可能化信号がオンであれば、同報通
信（左）のビシト値はＮ　＋）可１１ヒ化（左）ｆ３号
と論理的にＡＮＤされ、ＴＯの始めにフリップフロップ
５７２内にラッチされる。その結果、Ｃ１ ○Ｉ−可能化信号がオンであり、左からの列内のデータ
が右へ移動し、且つその列内のその経路指定要求が出力
として選択されれば、その要求内の同報通信ビットはフ
リップフロップ５７２内へ記憶される時にオフになる。

可能化された同報通信ヒラ１〜は、ＲＤＹ信号が要求内
のマスク　ピント・がオンである行を横切って伝播する
ことを停止させるので、フ！１（効要求内の同報通信ピ
ント・をオソムらしめることば重要である。しかし同報
通信ヒノｌがオフであれば、ＲＤＹ信号はオンであるマ
スクビノトによって停止されること（ｊない。

左端列４５１内の回路５７０の場合にｔよ、経路指定表
４２２からの同報通信ピントはフリップフロップ５７２
の入力に直接印加される。

同報通信ピントは次に右の列及び該ピントが記憶されて
いる列の−ｈ方の両者・＼伝送される。第７図に示すよ
うに、同報通信回路５７０の上の各ＲＱ論論理ブロツク
５２０同報通信ピントをその整合回路５３２及びｌ’＜
　ｆ）　Ｙ回路５２Ｇへの入力の１つとして使用してい
る。

２ もし第１クロツク副相の終り（即ちＴＯ３の終り）にＮ
Ｄ可能化信号が可能化（即ちパ０′”にセラ１〜）され
れば、フリップフｌコソプ出カライン５７４上の信号は
トライステート　バッファ５７８を通して同報通信デー
タ　パスへ伝送される。

論理フ′１．Ｊンク；Ｃ１ 各列の頂部にある論理制御回路Ｃ１及びＣ２は各経路指
定エンジン　サイクルの第１副相の終り（即ちＴ　Ｏ３
の終り）に２つの判断を行う。即ち（１）列に含まれて
いる要求が満たされたか否か、及び（２）左の列からの
（或は第１列４５１の場合には経路指定表４２２からの
）データを列にロートするか否かを判断する。もし要求
が満たされ、可能化されたＮＤ可能性信号によって表わ
されるように出力として選択されれば、列のマスクが水
平データ　パスを通して経路指定エンジンの出力段（第
５図の列４６８）へ送られる。

第１１図の論理ブロック６００は第５図のブロック“Ｃ
１゛′に対応する。この回路は、この回路６００を含む
列が満たされた要求を含むか否か、３ 及びこの列のマスクをデータ　ハスによって出力段へ伝
送すべきか否かを判定する。１つの列は、もしそのマス
クが有効であれば、もしその内容がＲＤＹラインと一致
していれば、及びもし右側のどの列もマスクをデータ　
ハスに（Ｊ（給していな４Ｊれば、そのマスクをデータ
　ハスにイｊ（給する９マクスを出力段へ供給する列は
経路指定要求が満たされたことを表わし、経路指定待ち
行列から除かれる。

“応答済み゛論理回路６０２のプール式は応答済み（）
一応答済・７＋（右）十も効（）＊完全整合 である。

信号“′応答済み（）゛はＣ１セルを通して右から左へ
伝播して、右の列が現経路指定エンジンサイクル中に経
路指定選択を供給することを表わす。もし受信した応答
済み（右）信号がオンであれば、応答済み論理回路６０
２は自動的にその信号を複製する。もし受信した応答済
め（右）信号がオンでなければ、その列が有効要求を含
め且つ４ 完全整合信号がその列のＲＱ全セルよって生成されてい
る場合に限って応答済み（）がオンにセットされる。

ＮＤ可可能化論理回路６０４プール式ばＮＤ可能化；−
〜（有効（）＊完全整合＊〜応答ｌ斉、７＋（右）　） である。但し゛ニー”操作は、この項がＴ３の終りにフ
リ・ンブフロンブ６０６内にう・ソチされることを表わ
す。

上式は、有効要求がＲＤ　Ｙ　ＩＪタンク用可能信号と
一致してはいるが、右の列からの応答済み（右）信号が
オフである場合に限ってＮＤ可能化信号が°低”になる
ことを意味する。ＮＤ可能化信号が“′低“°になると
第７図乃至第１０図に示す全てのトライステート　バッ
ファが使用可能となるので、この列の経路指定要求は水
平データ　ハスを介して列４６８内の出力回路へ伝達さ
れるようになる。

ＮＶＡＬＩＤ１７Ｇ信号ばアレイ内の何れかの列がＮＤ
可能化信号を（Ｊ（給するとトライステート　ドライハ
ロ０Ｂによって“低′”くされる。ＮＶＡＬＩＤＲ［］
信号は、５ アレイ内のどの列もＮＤ可能化信号を発生していない場
合には、プルアップ抵抗によって゛高°゛へ引き上げら
れる。ＮＶＡＩ、ＩＤＲＱ信号は、後述するように経路
指定エンジンの最終出力を生成する論理回路によって使
用される。

論理ブロック：０２ 第１２図の論理ブロック６１０ば第５図の“Ｃ２゛′ブ
ロツクに対応する。この回路は、この回路６１０を含む
列が友の列からデータをロードされているか否かを判断
するために使用される。

ＣＯＬ可能化論理回路６１２のブルー式はロード・済み
（）−〜有効十ロート済み（右）十〜応答済め（右）＊
完全整合 である。

ロード済み（）信号はフリップフロップ６１４内に記憶
され、その出力はＡＮＤゲー１６１６によってクロック
信号Ｔ４とＡＮＤされてフリップフロップ６１８内へ記
憶される。フリップフロップ６１Ｂの出力が列用（ｉヒ
化信号“Ｃ０Ｉ−可能化。

であり、これはＴ５中のみロート済メ（）信号に６ 等しい。ＣＯＬ可能化信号はクロック相Ｔ５の間だけ可
能化されるから、データはＴ５の終りに、即ち現経路指
定エンジン　サイクルの終りで且つ次の経路指定エンジ
ン　サイクルの始めに左の列からロードされる。

新要求をアレイ４５０内に挿入する際、満たされていな
い或は無効要求を含む列はこの経路指定要求を受入れる
ために右へ移動させなければならない。ｌ１ｌ−ド済め
信号はアレイ４５０のＣ２制御区分を通して右から左へ
伝播する。−船釣に言えば全ての列は各サイクル中に右
へ移動するが、アレイの右側にあって満たされていない
要求を保持する列を除く。

詳述すれば、各列は若干の条件が満たされればその左の
列からのデータがロードされる（最左端の列は経路指定
表４２２からロードされる）。即ち、 （１）有効：もしその列が無効要求を含んでいれば、そ
の列は左の列からのデータで重ね書 きされる。或は ７ （２）０−ド済み（右）；右のある列はその左の列から
データをロードされよう。或は （３）〜応答済み（右）＊完全整合：列内の経路指定要
求は満たされ、出力として選択され ている。

もし１つの列が結果を供給し、その右側の列が移動しな
ければ、要求はその左の列の内容によって重ね書きされ
る。一方もしアレイが、結果を供給している列の右の列
−・の無効要求を含んでいれば、即ち満たされた要求は
１列だけ右へ移動し、アレイ内に留まる。

この要求が爾後のサイクル中に結果を供給しないように
するために、第９図及び第１０図に示すように同報通信
及び有効甲シフトレジスクの人力はＮＤ可能化（左）信
号とＡＮＤされるのである。

これは、もしある列が同一サイクル中に結果を供給して
移動すれば、この結果は無効化され、その同報通信ピッ
１−は次に右の列内へ移動する時にクリヤされる。

８ 論理ブロンク：Ｏ，Ｏ’及びＲＧ 第１３図及び第１４図に示されているアレイ右端の論理
ブロック６３０　（０）、６４０　（０’）及び６５０
（ＲＧ）＆よ経路指定エンジンの最初出力を発生し、ス
イッチの出力リンク　ユニットからＲＤＹマスク（即ち
リンク可用性マスク）を受ける。アレイの各行内の機能
ブロック６３０はその行の最終出力を生成する。機能ブ
ロック６３０は、選択された出力リンクを指定する出力
を供給する第１行から出力機能ブロソクの列を方へ伝播
するパ禁止”信号も生成する。禁止信号の目的は、非同
報通信要求に応答して１つのマスク　ビットのみが出力
されるようにすることである。

ＶＡＬＩＤＢＣ信嵜は全ての出力ブロック６３０へ供給
される。この信号は、有効同報通信要求がアレイの出力
に存在することを表わす。ｖＡＬＩＤＢＣは、ＡＮＤゲ
ー１−（図示せず）によって生成され、次のブ′−ル式
によって表わされる。

ｖＡＬＩＤＢＣ−−ＮＶＡＬＩＤＲ［ｌ＊同報通信デー
タ“出力°゛論理ブロンクロ３２のプール式は９ 出力ニー（−禁止（丁）　−１−ＶＩＩＬＩＤＩＩＣ）
　＊　Ｒｌ）　Ｙ　データである。但し“ニー“操作は
出力信号がＴ５の終りにフリップフロンプロ３４内にラ
ッチされることを表わす。

“′禁止“論理ブロック６３６のプール式は禁止−禁止
（下）＋ＲＤ￥＊データ である。

アレイ内のある列が有効同報通信要求の結果としてその
マスクを供給する場合、経路指定要求内の全てのビット
がＲＤＹマスク内のビットと−・致しているので、これ
らのビン１〜は出力ハス４７０へ引渡される。従って有
効同報通信要求に対しては出力論理ブロック６３２によ
って゛禁止“信号は無視される。

非同報通信の場合には、経路指定要求マスク（データ）
はＲＤＹマスクとＡＮＤＬなければならず、得られたビ
ットの１つのみを最終経路指定選択値の一部として供給
しなければならない。これを達成するために、ＲＤＹマ
スクと一致する経路指定マスク　ビットを有するアレイ
の最下部か０ ら始まる第１行によって禁止信号が生成される。

禁止信号を発生する第１行の上の全ての行は出力を発生
することを禁止される。

アレイのどの列も結果を発生していない場合に経路指定
エンジンが不正確に出力を引渡すことがないように、ブ
ロック６００　（Ｃ１）が生成した信号”　ＮＶＡＬ　
ｒＤＲＱ　’“が禁止（下）信号として出力列の第１（
最下）セル６３０へ供給される。ＮＶＡＬＩＤＲＱは、
アレイが結果を発生しない時に限り“′高゛である。こ
の禁止信号は出力セルの列を上方へ伝播し、全ての出力
の生成を禁止する。

最終出力は各経路指定エンジン　サイクルの終り（即ち
クロンクＴ５の終り）にフリップフロップ６３４内にラ
ッチされ、次の経路指定エンジンサイクルの相Ｔ１中に
出力ライン　ドライハロ３８によって経路指定エンジン
の出力ライン４７０上へ供給される。

第１４図を参照する。リンク番号、同報通信データ及び
経路指定エンジンの有効ビット行のための出力セル６４
０　（０’　）は、これらの各信号の６ま ためのラッチ即ちフリップフロップ６４２及び出力ライ
ン　ドライバ６４４を有する。有効ビット・行の場合に
は、ラッチ６４２内にラッチされる信号はブロックｃ１
　（６００）内のトライステー１−ドライバ６０８によ
り生成されたＮ　Ｖ　／ｌ　Ｌ　ｌ　［１１１Ｑ信冒で
ある。これらの各行内の最終出力は各経路指定エンジン
　サイクルの終り（即ちりＩコック１゛５の終り）にフ
リップフロップ６４２内にラッチされ、次の経路指定エ
ンジン　・す°イクルのＴ　ｌ中に出力ライン　ドライ
バ６４４によって経路指定エンジンの出力ライン４７０
」二へ供給される。

第１３図に示ず出力リンク　ユニソＩ・によって供給さ
れるＲＤＹ信号（即ち可用性マスク）は、経路指定エン
ジンが直接使用することはできない。

これは、ルータ２１８がパイプライン化された回路の故
である。もし経路指定エンジンが特定出力リンクを使用
して出力を供給すれば、その出力リンクは次の経路指定
エンジン　サイクル中に使用する準備が整っていない（
即ち使用不能）と見做されるようにしなければならない
。これば、経路２ 指定エンジンの列４５１〜４６３内の経路指定要求の待
ち行列に引渡す前に人Ｒ１）Ｙマスクを出力マスクの補
数とＡＮＤすることによって遠戚する。

ＲＤＹ信号回ｉｉ’１）（Ｒｅ論理ブ１コック）６５０
のためのプール式は ＲＤＹ＝ＲＤ￥　（ラッチ済み）＊〜出力である。但し
ＲＤＹ　（ラッチ済み）は各経路指定エンジン　サイク
ルの始め（即ち、ＴＯの始め）にフリップフロップ６５
２内にランチされるＲＤＹリンク可用性値である。

経路指定エンジン性能 好ましい実施例においては、経路指定エンジンの動作の
第１副相のための最長組合せ通路は約２７０ナノ秒であ
る。これは、ＲＤＹ信号がアレイを横切って伝播するた
めに、整合信号がアレイを上方に伝播するために、応答
済み信号がアレイがアレイを横切って左方へ伝播するた
めに、及びｃ　ｏ　ｒ−可能化信号及びＮＤ可能化信号
を生成するために要する最大時間量が約２７０ナノ秒で
あることを意味する。

３ 第２副相のための最長組合せ通路は約１５０ナノ秒であ
る。

好ましい実施例は、結果がラッチされる前に全ての信号
が整定するための時間を有するようにする伝統的な設計
を使用している。その結果、第１副相は４Ｘ８０ｎＳの
クロック　サイクル（Ｔｏ乃至Ｔ３）の合計３２０ｎＳ
を使用し、第２副相は２Ｘ８０ｎＳのクロック　サイク
ル（Ｔ４乃至Ｔ５）の合計１６０ｎＳを使用する。従っ
て経路指定エンジンの合計クロック　サイクル時間は４
８０ｎＳである。第６図のタイミング図を参照されたい
。

変形実施例 経路指定エンジンを実現するために使用したシリンラス
３０９０アレイは比較的高価な集積回路である。本発明
を大量生産する場合、経路指定エンジン４３０はカスト
マイズされた集積回路を使用して実現されるものと考え
られろ。カストマイズされた集積回路は経路指定エンジ
ンの価格は、特注回路の設計及びツーリング（即ち集積
回路マスク製造用）のための初期技術費用を旭視ず＊１
沫Ｉ゛、４ ９０％以上低下するものと推定される。

特注集積回路を使用する他の長所は、より高い動作速度
、１２より多い外部リンク　ボートを有するスイッチの
取扱い能力、及び回路に付加的な特色を付加する能力を
含む。シリンクス　アレイは比較的低速の論理回路を使
用している。経路指定エンジンが毎秒約２００万の経路
指定選択を行い得るにも拘わらず、ネットワーク伝送速
度が毎秒１００万ビツトを超えるまで増大した時にはよ
り高速な性能を望む可能性さえある。

本実施例に使用したシリンクス　アレイは２０論理ブ１
コツクの１６列を有する。その結果、経路指定エンジン
４３０がＳＣＰのためのボートを含む１４ボートを有す
るスイッチを取扱い得るように、第５図に示すアレイに
１以上の列及び１以」二の行を付加することが可能であ
る。（好ましい実施例においてはスイッチは１３ボート
を有する。

特注回路を使用すれば、より多くのボートを有するスイ
ッチを取扱うように論理要素のアレイを更に拡張するこ
とができよう。

５ 以上に本発明を若干の特定実施例に関して説明したが、
この説明は本発明を例示するためになされたものであり
、本発明を限定するものではない。

当業者ならば本発明の思想及び範囲から逸脱することな
く種々の変更を考案し得よう。

【図面の簡単な説明】

第１図は本発明により小さい網状に接続されたネットワ
ークのブロック線図であり、 第２図は好ましい実施例に使用されているスイッチのブ
ロック線図であり、 第３図は第２図のスイッチに使用されているルータ装置
のブロック線図であり、 第４図は経路指定要求を表わすデータを示し、第５図は
パケット経路指定選択を行う経路指定エンジンの好まし
い実施例のブロック線図であり、第６図は第５図及び第
７図乃至第１３図のためのタイミング図であり、 第７図は経路指定要求の一部とリンク可用性データとの
一致を検出する回路セルのブロツク線図であり、 ６ 第８図乃至第１０図はそれぞれ人力リンク番号、有効ピ
ッＩ・及び同報通信ビットを記憶し移動させるために使
用されているランチ回路のフロック線図であり、 第１１図及び第１２図は特定ハス要求に対して経路指定
選択を行うことが可能であるか否かを判定するための２
つの論理回路のフロック線図であり、 第１３図は出力回路のフロック線図であり、第１４図は
第２の出力回路のブロック線図である。 １００−　イ、ツトワーク、２１０−　スイッチ、２　
］　］２−−−−−非閉塞クロスバスイッチ、２１４リ
ンク市１１１卸コーニント（スイツチ　ボート）、２１
４　ａ−−−−〜リンク　ユニソ１−１２１５−−−全
二重リンク、２１．６−−−−スイツチ制御プロセッサ
（ＳＣＰ）、２１８　−ルーフ（経路指定論理回路）、
２２０−−−−一人カリンク　ユニラミ・（Ｒｘ）、２
２２−−−−−−出力リンク　ユニット（ＴＸ）、４２
０レジスタ、４２２−−−−−経路指定表、４２４７ 経路指定要求セレクタ、４３０−−経路指定エンジン、
４　ａ　５−−−−−−ｉ１ｉ制御量制御４５ｏ　−経
路指定エンジン　アレイ、５２０−−−ＲＱ論理プロ・
ンク、５２２，５４２，５４４，５７２，６０６，６１
．４，６３４．６４２６５２フリンプフロンブ、５２６
−−−　ＲＩ）　Ｙ　論理回路、５２８．５５０，５５
２，５６８，５７８．６０８　　　　トライステ−トハ
ンファ（ドライバ）、５３２−−−整合論理回路、５４
０−−ｍ−４−Ｎ論理ブ１コック、５６ｏ−−−■論理
フロノク、５６３．６１６−一−−Ａ　Ｎ　Ｄゲート、
５７０ＢＣ論理プロｙり、６００−−−ＣＩ論理ブロノ
ク、６０２−−−一応答済み論理回路、６０４　　−Ｎ
Ｄ可能化論理回路、６ＩＯ−Ｃ２論理フ１コツク、６１
２−一−−ＣＯＬ可能化論理回路、６３０−０論理ブロ
ツク、６３２−　出力論理回路、６３６禁止論理回路、
６３８，６４／ｌ　　−−−−ライン　トライバ、６４
０−−−−０′論理ブ１：１ンク、６５０−　ＥＧ論論
理ブロック ８ ２− 憚− 白

Claims (1)

1. 【特許請求の範囲】 １、事前に定められた組のコンピュータ資源を、受信し
   た資源要求に割当てる資源割当て装置であって： それぞれが前記事前に定められた組のコンピュータ資源
   の部分集合を明示する資源要求を受信する要求受信手段
   ； 割当てに使用可能な所定の組のコンピュータ資源からな
   る一組の使用可能な資源を明示する可用性手段； 前記要求受信手段に結合され、該手段によって受信され
   た前記資源要求を該手段によって受信された順番に記憶
   する待ち行列手段； 前記待ち行列手段及び前記可用性手段に結合され、前記
   待ち行列内に記憶されている前記資源要求と前記一組の
   使用可能資源とを順次に比較し、前記一組の使用可能資
   源と整合する前記資源要求の中の最初の要求を選択する
   選択手段を具備し、それによって先着順配慮基準に基い
   て使用可能資源を資源要求に割当てる資源割当て装置。 ２、各資源要求は、資源要求が該要求によって明示され
   る事前に定められた組のコンピュータ資源の全ての部分
   集合の使用を要求する同報通信要求であるか否かを明示
   する型明示手段を含み、該型明示手段は前記要求によっ
   て明示される事前に定められた組のコンピュータ資源の
   部分集合の１つだけの使用を要求する非同報通信要求で
   あるか否かをも明示し； 選択手段は、同報通信要求によって明示された資源を確
   保する資源確保手段を含み、該資源確保手段は同報通信
   要求に後続する資源要求が同報通信要求によって明示さ
   れた何れの資源とも整合することを阻止する手段を含む
   請求項１記載の資源割当て装置。 ３、選択手段は、資源要求が選択手段によって選択され
   た後に待ち行列から該資源要求を削除する手段を含む請
   求項２記載の資源割当て装置。 ４、事前に定められた組のコンピュータ資源を、受信し
   た資源要求に割当てる方法であって：それぞれが前記事
   前に定められた組のコンピュータ資源の部分集合を明示
   する資源要求を受信し； 割当てに使用可能な所定の組のコンピュータ資源からな
   る一組の使用可能な資源を明示し；受信した資源要求を
   受信した順番に記憶し；記憶した資源要求と前記一組の
   使用可能資源とを順次に比較し、前記一組の使用可能資
   源と整合する前記資源要求の中の最初の要求を選択する
   諸段階からなり； それによって先着順配慮基準に基いて使用可能資源を資
   源要求に割当てる資源割当て方法。 ５、各資源要求は、資源要求が該要求によって明示され
   る事前に定められた組のコンピュータ資源の全ての部分
   集合の使用を要求する同報通信であるか否かを明示し、
   また該要求によって明示される事前に定められた組のコ
   ンピュータ資源の部分集合の１つだけの使用を要求する
   非同報通信要求であるか否かをも明示し； 比較段階は、同報通信要求によって明示された資源を反
   転し、同報通信要求に後続する資源要求が同報通信要求
   によって明示された何れの資源とも整合することを阻止
   する段階を含む請求項４記載の資源割当て方法。 ６、選択段階は、資源要求が選択段階によって選択され
   た後に、記憶された資源要求から該資源要求を削除する
   段階を含む請求項５記載の資源割当て方法。 ７、それぞれがデータパケットを受信するための複数の
   入力リンクとデータパケットを送信するための複数の出
   力リンクとを有し、網状に接続されたネットワーク内に
   存在する各スイッチ内において使用するための経路指定
   装置であって： それぞれが対応するデータパケットを送信 するための一組の出力リンクを明示するデータパケット
   経路指定要求を受信する要求受信手段； データパケットを経路指定するために使用 可能な組の出力リンクを明示する可用性手段；前記要求
   受信手段に結合され、該手段によって受信された前記デ
   ータパケット経路指定要求を該手段によって受信された
   順番に記憶する待ち行列手段； 前記待ち行列手段及び前記可用性手段に結合され、前記
   データパケット経路指定要求と前記組の使用可能出力リ
   ンクとを順次に比較し、前記組の使用可能出力リンクと
   整合する前記データパケット経路指定要求の中の最初の
   要求を選択する選択手段 を具備し、それによって先着順配慮基準に基いて使用可
   能出力リンクを経路指定要求に割当てる経路指定装置。 ８、各データパケット経路指定要求は、該要求が該要求
   によって明示される全ての組の出力リンクの使用を要求
   する同報通信要求であるか否かを明示し、また該要求に
   よって明示される１組だけの出力リンクの使用を要求す
   る非同報通信要求であるか否かをも明示し； 選択手段は、同報通信要求によって明示された出力リン
   クを確保する資源確保手段を含み、該資源確保手段は同
   報通信要求に後続するデータパケット経路指定要求が同
   報通信要求によって明示された何れの出力リンクとも整
   合することを阻止する手段を含む請求項７記載の経路指
   定装置。 ９、選択手段は、データパケット経路指定要求が選択手
   段によって選択された後に待ち行列手段から該データパ
   ケット経路指定要求を削除する手段を含む請求項８記載
   の経路指定装置。