時分割多重化回路切り換えルータ
時分割多重化回路切り換えルータは、複数の入力手段（ｉ１，．．．，ｉＮ）と、少なくとも１つの出力手段（ｏ１，．．．．，ｏＭ）と、前記入力手段（ｉ１，．．．，ｉＮ）と前記出力手段（ｏ１，．．．．，ｏＭ）との間を切り換えるとともに、所定のタイムスロット中に、選択された前記入力手段を前記出力手段に対して接続するための切り換え手段と、所定のタイムスロットにおいてどの入力手段が出力手段に接続されるかについての命令を含み、前記切り換え手段を制御するためのルータテーブル手段とを備えている。前記ルータテーブル手段は複数のテーブルに分割され、各テーブルは、他のテーブルにおける予約に関連して１つのテーブルにおける予約毎に帯域幅の大きさを特定する重みを有している。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の入力手段と、少なくとも１つの出力手段と、入力手段と出力手段との間を切り換えるとともに、所定のタイムスロット中に、選択された入力手段を出力手段に対して接続するための切り換え手段と、所定のタイムスロットにおいてどの入力手段が出力手段に接続されるかについての命令を含み、切り換え手段を制御するためのルータテーブル手段とを備えている時分割多重化回路切り換えルータに関する。
【背景技術】
【０００２】
共有された相互接続にわたる通信において正確な待ち時間およびスループットを実現するために、従来の通信アーキテクチャは、一般に、時分割多重接続方式（ＴＤＭＡ）と呼ばれるアービトレーション方式に依存する。アービトレーション方式は、コンテンション解決を行ない、共有相互接続ラインにわたる通信の場合には不可欠である。ＴＤＭＡは、固有のマスタのために各スロットを静的に予約することができる（スロットの）タイムホイールのように機能する。タイムホイールがＳ個のスロットから成り且つ各スロットが等しい量の時間を要する場合、全てのスロット予約は、バスの利用可能な帯域幅Ｂの１／Ｓ番目に対応する。Ｂ／Ｓよりも大きい帯域幅を必要とする接続のためには、複数のスロットを予約しなければならない。スロット予約は１つのテーブル内に記憶され、これは、一般に、内蔵メモリ等、例えばランダムアクセスメモリ（ＲＡＭ）または先入れ先出し（ＦＩＦＯ）バッファによって実施される。
【０００３】
プログラムされた接続の帯域幅要件の範囲が大きい（例えば１Ｍｂ／ｓ〜２０Ｇｂ／ｓ）場合には、問題が生じる。この時、２００００個未満のスロットを用いて大きな比率を実現するためには、タイムホイール内の多くのスロット（与えられた例においては、＞２００００）あるいは何か他のものが必要とされる。
【０００４】
莫大な数のトランジスタを有するチップを設計する複雑度を管理するには、計算を通信から切り離す必要がある。通信においては、ネットワークオンチップ（ＮｏＣ）等の拡張可能で且つ合成的な相互接続を使用しなければならない。そのため、オンチップ通信の将来は、ルータのオンチップネットワークである。回路切り換えにより、送信元から送信先への概念的物理経路にわたる通信を確立することができる。オンチップルータネットワークは、他の部品間に、相互接続されたルータから成る。
【０００５】
米国特許第４４６６０６０号明細書は、パケットメッセージ切り換えデジタルコンピュータネットワークにおいてデータメッセージのルーティングを制御するための適応分散メッセージルーティングアルゴリズムを開示している。ネットワークトポロジ情報は、排他的ツリーと称される最小長さのツリーの形態を成す隣接するノード間でだけやりとりされる。排他的ツリーは、隣接するノード及びそのリンクをツリーから排除することにより形成される。受けられた排他的ツリーの組から、ルータテーブルおよび送信された排他的ツリーが構成される。
【０００６】
国際公開第０１／８９１５８号パンフレットは、リンクによって相互に接続されたノードを備える通信ネットワーク内でリソースを制御するための方法を開示している。各リンクは、複数のフレームに分割されるビットストリームを伝送する。また、各フレームは、回路切り換えチャンネルを形成するために割り当てることができる複数のタイムスロットに分割される。タイムスロットへの書き込みアクセスの形態を成すリソースは、管理エンティティに関連付けられている。その後、リソースが対象管理エンティティに関連付けられた程度まで対象管理エンティティに属するチャンネルに対するリソースの割り当てが保証されるように、リソースの割り当てが行なわれる。
【０００７】
時分割多重化（ＴＤＭ）を使用するオンチップルータネットワークにおいては、物理的なリンクを共有して、相互接続リソースの高い利用度を得ることができる。これは、ルータ内にスイッチをセットするための制御を必要とし、また、この制御情報は、所謂スロットすなわち所定の時間単位あるいはルータテーブルに記憶される。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明の目的は、低コストでオンチップルータネットワークにおいて使用できる時分割多重化回路切り換えルータを提供することである。
【課題を解決するための手段】
【０００９】
【００１０】
前記目的および更なる目的を達成するために、複数の入力手段と、少なくとも１つの出力手段と、前記入力手段と前記出力手段との間を切り換えるとともに、所定のタイムスロット中に、選択された前記入力手段を前記出力手段に対して接続するための切り換え手段と、所定のタイムスロットにおいてどの入力手段が出力手段に接続されるかについての命令を含み、前記切り換え手段を制御するためのルータテーブル手段とを備えるルータであって、前記ルータテーブル手段が複数のテーブルに分割され、各テーブルが、他のテーブルにおける予約に関連して１つのテーブルにおける予約毎に帯域幅の大きさを特定する重みを有していることを特徴とするルータが提供される。
【００１１】
本発明によれば、ルータテーブル手段のサイズが減少し、それにより、対応するシリコン領域およびオーバーヘッドが減少し、したがって、コストが節約される。これは、オンチップルータネットワークを設ける場合に重要である。また、本発明によれば、同じサイズのルータテーブル手段において帯域幅粒度を更に細かくすることができ、したがって、同じコストで、ネットワーク中の利用可能な帯域幅をより効率的に使用することができる。これは、より高く重み付けられたテーブルによって高帯域幅のデータストリームを網羅でき、それにより、僅かなタイムスロットを割り当てるだけで済むからである。本発明は、全てのデジタルシステムオンチップＩＣにおいて使用できる。
【００１２】
テーブルの重みがプログラム可能であることが好ましい。
【００１３】
各テーブルは所定数の横列を含むことができ、また、所定時間毎にテーブルが各重み（ｗｌ>１）に対応して所定回数（ｗｌ）循環される。そのため、有効スロットサイクル周期（Ｓｅ）は、
Ｌ
Ｓｅ＝Σｗｌ・Ｓｌ
ｌ＝１
であることが好ましい。
【００１４】
テーブルのエントリが列挙される方法は、ルータが一部を成すネットワークを通じた待ち時間要件に依存している。
【００１５】
複数のバッファ手段を備える更なる好ましい実施形態において、各バッファ手段はそれぞれ、前記入力手段と前記切り換え手段との間に接続され、前記各バッファ手段はそれぞれ、複数のテーブルに対応する複数のバッファ部を備え、各バッファ部がそれぞれ１つのテーブルに割り当てられ、前記ルータテーブル手段は、前記テーブルにしたがって前記バッファ部を制御するために設けられている。そのようなバッファリングコンセプトは、共有バッファリングコンセプトよりもエレガントである。これは、そのようなバッファ手段内に入力フロー制御数字がテーブル毎に記憶され、それにより、様々なレベルのＴＤＭＡスケジュールが論理的に独立するようになるからである。前記バッファ手段は先入れ先出し（ＦＩＦＯ）バッファ手段であることが好ましい。
【００１６】
本発明の前述した目的および他の態様は、以下の説明および添付図面によって更に良く理解される。
【発明を実施するための最良の形態】
【００１７】
以下、図面を参照しながら、本発明の好ましい実施形態について説明する。
【００１８】
回路切り換えのための単純なルータのアーキテクチャ（構造）が図１に説明の目的で示されている。ルータは、バッファを含むＮ個の入力ポートと、Ｍ個の出力ポートと、ルータテーブルにしたがって入力から出力へと（同時に）データを転送するためのスイッチとから成る。回路切り換えにより、特定の時間の間に送信元から送信先へと物理的な経路にわたって接続を行なうことができる（Leijten, J. A. J.;van Meerbergen, J. L.; Timmer, A. H.;Jess, J. A. G.;「高性能マルチプロセッサにおけるリアルタイムタスク間でのストリーム通信」，Design, Automation and Test in Europe，１９９８年、議事録、１９９８年２月２３日〜２６日、１２５〜１３１頁）。
【００１９】
ルータにおいて、データは、タイミングを図るため、特定の時間の間、キュー内に記憶される。したがって、ルータネットワークにわたる回路切り換えは、ネットワークにわたるデータ転送が１つのホップだけではなく複数のホップ（経路上の各ルータ毎に１つずつ）を含んでいるという点で、共有バスＴＤＭＡアーキテクチャとは異なる。この場合、各ホップ（ルータ）は、異なるルータテーブルを有している。また、回路切り換えは、マスタ−スレーブにより或いはルータ入力−出力ポートとの関連で後述するように対がスケジュールされる特定の形式のＴＤＭＡである。
【００２０】
個々のルータのルータテーブルは、経時的にコンテンションフリーな態様でクロスバースイッチをプログラムするための情報を含んでいる。このため、時間がスロットと呼ばれる所定の複数の単位時間に分けられる。１スロット中においては、フリット（フロー制御数字）と呼ばれるデータの単位をクロスバースイッチによりルータ入力バッファから出力へと転送することができる。特定のスロットにおける入力／出力マッピングは、Ｓ×Ｍサイズのマトリクス（行列）であるルータテーブルＴによって特定される。ここで、Ｓはスロットエントリの数であり、Ｍはルータの出力端子の数である。Ｔの要素は組｛φ，Ｉ，．．．，Ｎ｝内にある。値ｎ＝Ｔ（ｓ，ｍ）（０＜ｓ＜Ｓおよび０＜ｍ＜Ｍ）は、スロットｓにおいてｎ≠φの場合にフリットが入力ｉｎから出力ｏｍへと転送されることを意味している。そのため、Ｔの行ｓは、スロットｓにおけるマッピングを特定する。スロット割り当てＴは、ｓ＝ｋ ｍｏｄ Ｓにしたがって、時間と共に周期的に繰り返され、ここで、ｋはスロット反復子である。
【００２１】
したがって、ネットワーク内の全てのルータのルータテーブルは、Ｓ個のタイムスロットを有している。同時性の論理的概念が存在する。すなわち、ネットワーク内の全てのルータは、前述したように、同じ所定の持続スロット内にある。スロット反復ｋにおいては、多くとも１つのデータブロックが出力ポート毎に書き込まれる。ネットワーク中のルータの出力は、入力／出力対間のリンクにより、ルータの入力に接続されている。そのようなリンクにより、スロット反復ｋにおいて１つの出力に書き込まれるブロックが、次のスロット反復でリンクにより接続される入力のキュー内に存在するようになる。次のスロットｋ＋１中において或いはその後において、到達したブロックは、その適切な出力ポートに対して再び書き込まれる。したがって、ブロックは、記憶装置内を伝搬してファッションを転送する。ブロックがルータ毎に要する待ち時間は、（経路に沿うその後の２つのルータの予約によって与えられる）ブロックの発着時間の差が乗じられるスロットの持続時間に等しい。帯域幅は、Ｓ個のスロット毎のブロックサイズの倍数単位で保証される。
【００２２】
送信元から送信先への経路において確保（予約）されたスロットは、ルータ毎に少なくとも１（モジュロＳ）だけ増大する。スロットｓが経路上の特定のルータで確保（予約）され且つスロット（ｓ＋ｑ）％Ｓ（ｑ＞０）が経路上の次のルータで確保（予約）される場合には、経路のこの部分において要した待ち時間はｑスロットである。
【００２３】
ルータの入力におけるブロックの到達順序は、これらのブロックがルータの出力のうちの１つを通じて書き込まれる順序と同じでなければならない。これは、ＦＩＦＯによって入力に接続されるキューの実施を可能にする。
【００２４】
ルータテーブルのエントリは、全てのスロット毎に出力を入力に対してマッピングする。すなわち、Ｔ（ｓ，０）＝ｉである。そのスロットにおけるその出力のための確保（予約）が存在しない場合には、エントリは空である。出力毎に多くとも１つの入力しか存在しないため、コンテンションは全く生じない。１つの入力を複数の出力に対して送信する（マルチキャスト）ことができる。
【００２５】
ＧＴ（保証スループット）ルーティング法において、特定のルータにおいてタイムスロットｓで読み取られる全てのＧＴトークンは、トークンが辿る経路中の次のルータにおいてタイムスロット（ｓ＋ｑ）％Ｓで読み取られる。ｑの値は、少なくとも１であり、選択されたスケジュールの結果である。それはできる限り小さいことが好ましい。なぜなら、接続の全体の待ち時間が、経路に沿う全てのｑの合計に等しいからである。保証スループット（ＧＴ）サービスは、最悪の場合のシナリオのためにリソース予約を必要とするが、これは費用が高くなる可能性がある。
【００２６】
ルータテーブルサイズＳ＝４での２つの２×２ルータＲ１，Ｒ２を含む単純なルータネットワークの一例が図２に示されている。この図では、４つのＧＴ接続がデータストリームｓ１，ｓ２，ｓ３，ｓ４によって表されている。そのデータストリームのために割り当てられるタイムスロットの数が図２の括弧内に示されている。
【００２７】
第１のルータＲ１の第１の出力ポート（図２では上側ポートとして示されている）は使用されておらず、したがって、ルーティングテーブルの第１の列は空である。第１のルータＲ１のルーティングマトリクスの第２の列は、その入力からのトークンが第２の出力ポート（図２では下側ポートとして示されている）上に交互に書き込まれることを示している。したがって、第１のルータＲ１におけるコンテンション無くして、両方のデータストリームｓ１，ｓ２が所定の帯域幅をもってルーティング（経路指定）される。第２のルータＲ２において、第１の出力ポート（図２では上側ポートとして示されている）は、データストリームｓ１，ｓ３のトークンを受ける。データストリームｓ１からのトークンは、第１のルータＲ１においてはタイムスロット０，２でルーティングされるため、第２のルータＲ２においてはタイムスロット１，３でルーティングされる。これは、第２のルータＲ２のルータテーブルの第１の列における２つの「１」によって見られる。データストリームｓ３によって必要とされる１つのタイムスロットは、第１の列のタイムスロット２においてスケジュールされる。同様に、第２のルータＲ２のルータテーブルの第２の列で「１」により示されるように、データストリームｓ２のトークンはタイムスロット０，２においてスケジュールされる。最終的に、データストリームｓ４のトークンはタイムスロット１においてスケジュールされる。
【００２８】
ＧＴトークンが全ての予約されたタイムスロットにおいて利用できる必要はない。ＧＴパケットが予約されたタイムスロットにおいて到達しない場合には、要求されているが使用されていないリンクのタイムスロットにわたってＢＥ（ベストエフォート）パケットを送信することができる。ベストエフォート（ＢＥ）サービスは、リソースを全く予約せず、したがって保証を行なわないが、一般に最悪の場合のシナリオではなく平均的な場合のシナリオのために設計されているため、リソースをうまく使用する。
【００２９】
ルータテーブル中のスロットの数Ｓは、リンクの帯域幅の全体の大きさを分割することができる粒度を決定する。Ｂがリンク毎の帯域幅の大きさを表している場合には、１つの接続がＢ／Ｓのかなりの部分で帯域幅を割り当てることができる。そのため、全てのルータのスロットテーブルエントリの数の増大を意味するＳの増大により、粒度が更に細かくなる。しかしながら、ルータテーブルのサイズが更に大きいと、シリコン領域においてルータのコストが高くなる。現在の評価では、ルータテーブルが全ルータシリコン領域の５０％程度を占められることが分かっている。また、大きなルータテーブルは動作上の欠点も有している。すなわち、高い大域幅および中間の帯域幅の接続においては、多数のスロットをプログラムしなければならない。これは、接続のセットアップおよび解除時間において高くつく。
【００３０】
図３は、直列に接続された２つの２×２ルータＲ１，Ｒ２の組み合わせの一例を示している。この場合、２つの２×２ルータがＲ１，Ｒ２で示されており、また、ネットワーク端子がｔｉ（ｉ＝１，２，．．．，６）で示されている。
【００３１】
第１のルータＲ１が端子ｔ１を介してＢＥパケットを受けるとともに、これらのパケットが全て端子ｔ５へ向かうことになっており、また、これらのパケットの帯域幅がリンクの容量の１０％を必要とすると仮定する。同様に、パケットは、端子ｔ２から端子ｔ６へと向かうとともに、リンク容量の１％しか必要としない。第２のルータＲ２は、端末ｔ６へと向かうことになっている端子ｔ４を介してＧＴデータストリームを受ける。ＧＴデータストリームは、帯域幅の９９％を要求して使用し、したがって、時間の９９％の間、ルータＲ２の出力ポートｂから端子ｔ６に向かう出力リンクを占める。そのため、ＢＥストリーム共有ポートｂは、残りの１％のリンク容量においてフリットだけを送ることができ、また、ＧＴデータがポートｂにおいて到達する毎に、ポートｂにわたるＢＥパケットの送信がプリエンプト（pre-empted)される。
【００３２】
これは、１％のＢＥデータストリームのパケットにおいて長い待ち時間を引き起こす可能性がある。この場合、待ち時間は、パケットがネットワークにわたって送信される持続時間として規定される。また、待ち時間により、ルータＲ１，Ｒ２間のリンクは、１％のＢＥストリームによってほぼ連続的に占められる。これは、異なるパケットのフリットがインタリーブされないからである。したがって、１０％のデータストリームのＢＥパケットは、リンクの速度の１０％未満を得る。これにより、図３の例において、ルータＲ１，Ｒ２間のリンクは、その理論的容量の１１％未満の利用度を有する。
【００３３】
この問題を解消するため、基本的に３つの手法がある。すなわち、（１）いわゆるワームホールルーティングではなく仮想カットスルールーティングを使用する、（２）データが無い長い期間およびデータの比較的大きなブロックにおいてＧＴ通信を実行する、（３）１％のＢＥストリームにおいてＧＴサービスを使用する。
【００３４】
最初の手法は、次のルータの入力リンクがブロックしないように、全てのパケットが次のルータで受け入れられることを保証する。しかしながら、これにより、メモリが余計に必要になる。
【００３５】
２番目の手法では、フリット強制排除がめったに生じない。ＧＴデータの９９％が１０時間単位のブロックでグループ化される場合、この帯域幅は、９９個のデータブロックを選択的に送信した後に１０時間単位を無くすることにより得られる。ＢＥデータストリームのパケットサイズがそのような１０時間単位と比べて小さい場合には、１％ＢＥデータストリームの全パケットが１０時間単位で送られ、パケットが送信された直後に１０％ＢＥデータストリームによりルータＲ１，Ｒ２間のリンクを使用することができる。最初の手法ではルータにおいて更なるメモリが必要になるが、この２番目の手法では、ＢＥデータストリームにおいて更なる待ち時間が必要になる。
【００３６】
第３の手法においては、端子ｔ２，ｔ６間の接続を実現するためにＧＴサービスが使用される。したがって、ルーティングテーブル中の１００個の全てのスロットから１つを予約することにより特定の瞬間に比較的低い帯域幅のストリームがスケジュールされる。これにより、スロットテーブルは、少なくとも１００エントリのサイズを有している必要がある。ＧＴサービスにより予約期間中に回路切り換え接続が得られるため、接続は、ルータＲ１，Ｒ２間のリンク容量のせいぜい１％しか使用しない。残りのリンク容量は、１０％ＢＥストリームのために利用できる。
【００３７】
３番目の手法は、低帯域幅および高帯域幅の両方を要する一組の接続を効率的に記憶するための手段を必要とする。これは、階層予約テーブルによって達成される。予約テーブルによってかなりの量のエリアオーバーヘッドが費やされるとすると、テーブルはＬ層に構造化される。すなわち、Ｔ＝（Ｔ１，．．．，ＴＬ）である。層ｌ＝１，．．.，Ｌのテーブルは、Ｓ１行から成るサイズと、ｗ１（>１）の重みとを有している。重みは帯域幅の大きさを定め、対応する予約テーブルのスロットが他の層の重みに比例して表す。これは、Ｌ個のテーブルの組み合わせスケジュールを構成することにより実現される。この組み合わせスケジュールにおいては、周期毎に、テーブルＴｌ，ｌ＝１，．．．，Ｌがｗ１回それぞれ循環される。そのため、有効スロットサイクル周期Ｓｅは以下のようになる。
Ｌ （１）
Ｓｅ＝Σｗｌ・Ｓｌ
ｌ＝１
【００３８】
また、これは、物理的な予約テーブルエトリを殆ど犠牲にしない。
Ｌ （２）
Ｓ＝ΣＳｌ
ｌ＝１
【００３９】
方程式（１）から、層ｌのスロットが全リンク帯域幅Ｂの比ｗｌ／Ｓｅに対応していることが分かる。
【００４０】
多層ルータテーブルを含むそのようなル−タアーキテクチャが図４に概略的に示されている。
【００４１】
図５は、多層手法に係る図３に示されるような状況におけるルータテーブルのファイリングを示している。ここでは、２つの層が必要とされる。１つのストリームがベストエフォートストリームであり、これがｂｅ１で示されている。また、２つの他のストリームが保証スループットである。これらはｇｔ１，ｇｔ２で示されている。両方のストリームをスケジュールする各ルータのルータテーブルは２つの層に分割され、各層は異なる重みを有している。第１の層は、重み１を有するとともに、ｇｔ２をサポートする。第２の層は、重み９９を有するとともに、ｇｔ１をサポートする。マトリクスＴ１ｌ，Ｔ２ｌは、ルータＲ１，Ｒ２のそれぞれにおける第１の層１に関連付けられた２つのサブテーブルを規定する。マトリクスＴ１２，Ｔ２２は、第２の層２のための予約を与える。したがって、第２の層２におけるスロットの予約は、第１の層１におけるスロットの予約よりも９９倍大きい帯域幅割り当てを必要とする。２層手法の結果として、スロットエントリＳの総数は、この場合において、３よりも多くなる必要はない。
【００４２】
様々なテーブルのエントリが列挙される方法は、ネットワークを通じた待ち時間要件に依存しており、また、層毎の独立したバッファリングに関して余計なコストを費やすことが望まれているかどうかに依存している。
【００４３】
以下の説明は、２つのバッファオプションを扱っている。両方のケースでは、ネットワーク内の全てのルータにおいて一方の層から他方の層への切り換えが同期して行なわれるものとする。
【００４４】
様々な層のテーブルが経時的にインタリーブされるため、ルータの層コントローラは、遅かれ早かれ、１つの層のテーブルの列挙を中断して、他の層のうちの１つを続ける。先入れ先出し（ＦＩＦＯ）バッファポリシーが入力毎に使用される場合、ＦＩＦＯは、コントローラが他の層に切り換わるレベルに属するデータを含んでいてはならない。さもなければ、データがだめになってしまう。そのようなポイントを特定の層において全てのルータのテーブル中で見出すことは取るに足りないことではない。なぜなら、一般に、ネットワークを通じた多くの経路が経時的に互いに重なり合うからである。経路を横切ることなく異なる層への巧みな切り換えを行なうことができる自然なポイントは、テーブルの最後のエントリの後ということもあり得る。しかし、循環スケジュールの場合、そのようなポイントは全く終了しない。すなわち、循環スケジュールにより、ルータを経由する経路を２つの部分に分けることができる。この場合、第１の部分はテーブルの最後でスロットを使用し、第２の部分はテーブルの最初にスロットを使用する。すなわち、１つの経路をテーブルの境界上で重ね合わせることができる。実際には、「入力毎に１つのＦＩＦＯ−手法」における有効な割り込みポイントを有するスケジュールにより、リンク利用度が低下する。
【００４５】
更に優れたバッファ手法は、図４と併せて図６に示されるように、レベル毎に入力フリットをＦＩＦＯに記憶する。図４に示されるように、複数のバッファＱが設けられている。この場合、各入力ｉ１〜ｉＮは、そのようなバッファＱに結合されている。図６には、そのようなバッファＱの構成が概略的に示されている。この概念において、様々なレベルのＴＤＭＡスケジュールは、それ自体が論理的に独立する異なるキューを使用する。そのため、予約テーブルを環状にすることができ、層間の切り換えを経時的な任意の瞬間において行なうことができる。
【００４６】
なお、ネットワークを通じた待ち時間は、２つのバッファリング方法において同じではない。
【００４７】
便宜上、高帯域幅接続と低帯域幅接続との間の割合および接続数はそれぞれ、１：９９および３と、小さく維持される。しかしながら、実際には、接続の割合および数がもっと大きくても良い。
【００４８】
多層スロットテーブルの利点は以下のように示される。簡単のため、図４にしたがってネットワークオンチップがたった１つのルータから成ると仮定する。また、１つの特定の出力ポートを通じて流れる保証スループット接続に焦点を合わせることとする。また、この出力を通じて流れる６０個のＧＴストリームが存在するものとする。これらのストリームの帯域幅要件は以下の通りである。すなわち、５０個のＧＴストリームが１Ｍｂ／ｓであり、１０個のＧＴストリームが１Ｇｂ／ｓである。そのため、全体の総帯域幅は少なくとも１０．０５Ｇｂ／ｓである。
【００４９】
以下、層の数およびスロットテーブルエントリの数が異なるスロットテーブルの３つの例Ａ，Ｂ，Ｃについて説明する。
【００５０】
例Ａは、１００５０個のスロットから成る１つのスロットテーブルを利用する。１つのリンクの帯域幅を１０．０５Ｇｂ／ｓとして、スロット毎の帯域幅が１／１００５０×１０．０５Ｇｂ／ｓ＝１Ｍｂ／ｓとなるようにする。ここで、１Ｍｂ／ｓの５０個のＧＴストリームはそれぞれ１スロットを確保する必要があり、また、１Ｇｂ／ｓの１０個のＧＴストリームはそれぞれ１０００個のスロットを確保する必要がある。
【００５１】
例Ｂも、同様に、単層スロットテーブルであるが、ここではちょうど２５０個のスロットエントリから成るスロットテーブルを利用する。この減少した数のスロットエントリは、かなりのコストを節約する。６０個のストリームにわたる２５６個のスロットの最適な分配は以下の通りである。すなわち、１Ｍｂ／ｓの５０個のストリームはそれぞれ１スロットを使用し、１Ｇｂ／ｓの１０個のストリームはそれぞれ残りの２０個のスロットを使用する。ここで、全てのストリームの帯域幅要件を満たすため、リンクの帯域幅は２５０／２０×１Ｇｂ／ｓ＝１２．５Ｍｂ／ｓでなければならない。したがって、スロット毎の帯域幅は５０Ｍｂ／ｓである。この実現には欠点があるのが分かる。すなわち、第１に、例Ａよりも２５％多い帯域幅を有するリンクを必要とするという点であり、また、第２に、この余計な帯域幅を他の接続において利用できないという点である。これは、そうすることを５０Ｍｂ／ｓの帯域幅粒度が許容しないからである。
【００５２】
例Ｃは２層スロットテーブルを使用する。スロットテーブルの第１の層は、スロット毎の帯域幅が１Ｍｂ／ｓである５０個のエントリから成る。スロットテーブルの第２の層は１０個のエントリから成る。この場合、各スロットの帯域幅は１Ｇｂ／ｓである。したがって、その後の層の重みｗｌは、１および１０００である。この実現では、例Ａと同様に、リンクの帯域幅を１０．０５ＧＢ／ｓにする必要があるが、我々は、全体で６０個のスロットテーブルエントリしか必要としない。その数は、例Ａの数の０．６％にすぎない。
【００５３】
以上、添付図面に示される実施例を参照して本発明について説明したが、本発明がそれに限定されず、添付の請求項に開示された範囲内において多くの方法で本発明を変形できることは明らかである。
【図面の簡単な説明】
【００５４】
【図１】時分割多重化回路切り換えルータの概略的な基本ブロック図を示している。
【図２】直列に接続された２つのルータの組み合わせ及び４つの保証スループットデータストリームのフローを概略的に示している。
【図３】２つの２×２ルータを有する単純なルータネットワーク、及び２つのデータストリームがベストエフォートであり１つのデータストリームが保証スループットである３つのデータストリームのフローを概略的に示している。
【図４】本発明の好ましい実施形態に係る多層ルータテーブルを含む時分割多重化回路切り換えルータの概略的なブロック図を示している。
【図５】本発明の好ましい実施形態に係る２つのルータから成るネットワークを通じて伝搬する３つのデータストリームのフローの概略図を示している。
【図６】入力毎に図４のルータに含まれる複数のバッファの概略的なブロック図を示している。
【技術分野】
【０００１】
本発明は、複数の入力手段と、少なくとも１つの出力手段と、入力手段と出力手段との間を切り換えるとともに、所定のタイムスロット中に、選択された入力手段を出力手段に対して接続するための切り換え手段と、所定のタイムスロットにおいてどの入力手段が出力手段に接続されるかについての命令を含み、切り換え手段を制御するためのルータテーブル手段とを備えている時分割多重化回路切り換えルータに関する。
【背景技術】
【０００２】
共有された相互接続にわたる通信において正確な待ち時間およびスループットを実現するために、従来の通信アーキテクチャは、一般に、時分割多重接続方式（ＴＤＭＡ）と呼ばれるアービトレーション方式に依存する。アービトレーション方式は、コンテンション解決を行ない、共有相互接続ラインにわたる通信の場合には不可欠である。ＴＤＭＡは、固有のマスタのために各スロットを静的に予約することができる（スロットの）タイムホイールのように機能する。タイムホイールがＳ個のスロットから成り且つ各スロットが等しい量の時間を要する場合、全てのスロット予約は、バスの利用可能な帯域幅Ｂの１／Ｓ番目に対応する。Ｂ／Ｓよりも大きい帯域幅を必要とする接続のためには、複数のスロットを予約しなければならない。スロット予約は１つのテーブル内に記憶され、これは、一般に、内蔵メモリ等、例えばランダムアクセスメモリ（ＲＡＭ）または先入れ先出し（ＦＩＦＯ）バッファによって実施される。
【０００３】
プログラムされた接続の帯域幅要件の範囲が大きい（例えば１Ｍｂ／ｓ〜２０Ｇｂ／ｓ）場合には、問題が生じる。この時、２００００個未満のスロットを用いて大きな比率を実現するためには、タイムホイール内の多くのスロット（与えられた例においては、＞２００００）あるいは何か他のものが必要とされる。
【０００４】
莫大な数のトランジスタを有するチップを設計する複雑度を管理するには、計算を通信から切り離す必要がある。通信においては、ネットワークオンチップ（ＮｏＣ）等の拡張可能で且つ合成的な相互接続を使用しなければならない。そのため、オンチップ通信の将来は、ルータのオンチップネットワークである。回路切り換えにより、送信元から送信先への概念的物理経路にわたる通信を確立することができる。オンチップルータネットワークは、他の部品間に、相互接続されたルータから成る。
【０００５】
米国特許第４４６６０６０号明細書は、パケットメッセージ切り換えデジタルコンピュータネットワークにおいてデータメッセージのルーティングを制御するための適応分散メッセージルーティングアルゴリズムを開示している。ネットワークトポロジ情報は、排他的ツリーと称される最小長さのツリーの形態を成す隣接するノード間でだけやりとりされる。排他的ツリーは、隣接するノード及びそのリンクをツリーから排除することにより形成される。受けられた排他的ツリーの組から、ルータテーブルおよび送信された排他的ツリーが構成される。
【０００６】
国際公開第０１／８９１５８号パンフレットは、リンクによって相互に接続されたノードを備える通信ネットワーク内でリソースを制御するための方法を開示している。各リンクは、複数のフレームに分割されるビットストリームを伝送する。また、各フレームは、回路切り換えチャンネルを形成するために割り当てることができる複数のタイムスロットに分割される。タイムスロットへの書き込みアクセスの形態を成すリソースは、管理エンティティに関連付けられている。その後、リソースが対象管理エンティティに関連付けられた程度まで対象管理エンティティに属するチャンネルに対するリソースの割り当てが保証されるように、リソースの割り当てが行なわれる。
【０００７】
時分割多重化（ＴＤＭ）を使用するオンチップルータネットワークにおいては、物理的なリンクを共有して、相互接続リソースの高い利用度を得ることができる。これは、ルータ内にスイッチをセットするための制御を必要とし、また、この制御情報は、所謂スロットすなわち所定の時間単位あるいはルータテーブルに記憶される。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明の目的は、低コストでオンチップルータネットワークにおいて使用できる時分割多重化回路切り換えルータを提供することである。
【課題を解決するための手段】
【０００９】
【００１０】
前記目的および更なる目的を達成するために、複数の入力手段と、少なくとも１つの出力手段と、前記入力手段と前記出力手段との間を切り換えるとともに、所定のタイムスロット中に、選択された前記入力手段を前記出力手段に対して接続するための切り換え手段と、所定のタイムスロットにおいてどの入力手段が出力手段に接続されるかについての命令を含み、前記切り換え手段を制御するためのルータテーブル手段とを備えるルータであって、前記ルータテーブル手段が複数のテーブルに分割され、各テーブルが、他のテーブルにおける予約に関連して１つのテーブルにおける予約毎に帯域幅の大きさを特定する重みを有していることを特徴とするルータが提供される。
【００１１】
本発明によれば、ルータテーブル手段のサイズが減少し、それにより、対応するシリコン領域およびオーバーヘッドが減少し、したがって、コストが節約される。これは、オンチップルータネットワークを設ける場合に重要である。また、本発明によれば、同じサイズのルータテーブル手段において帯域幅粒度を更に細かくすることができ、したがって、同じコストで、ネットワーク中の利用可能な帯域幅をより効率的に使用することができる。これは、より高く重み付けられたテーブルによって高帯域幅のデータストリームを網羅でき、それにより、僅かなタイムスロットを割り当てるだけで済むからである。本発明は、全てのデジタルシステムオンチップＩＣにおいて使用できる。
【００１２】
テーブルの重みがプログラム可能であることが好ましい。
【００１３】
各テーブルは所定数の横列を含むことができ、また、所定時間毎にテーブルが各重み（ｗｌ>１）に対応して所定回数（ｗｌ）循環される。そのため、有効スロットサイクル周期（Ｓｅ）は、
Ｌ
Ｓｅ＝Σｗｌ・Ｓｌ
ｌ＝１
であることが好ましい。
【００１４】
テーブルのエントリが列挙される方法は、ルータが一部を成すネットワークを通じた待ち時間要件に依存している。
【００１５】
複数のバッファ手段を備える更なる好ましい実施形態において、各バッファ手段はそれぞれ、前記入力手段と前記切り換え手段との間に接続され、前記各バッファ手段はそれぞれ、複数のテーブルに対応する複数のバッファ部を備え、各バッファ部がそれぞれ１つのテーブルに割り当てられ、前記ルータテーブル手段は、前記テーブルにしたがって前記バッファ部を制御するために設けられている。そのようなバッファリングコンセプトは、共有バッファリングコンセプトよりもエレガントである。これは、そのようなバッファ手段内に入力フロー制御数字がテーブル毎に記憶され、それにより、様々なレベルのＴＤＭＡスケジュールが論理的に独立するようになるからである。前記バッファ手段は先入れ先出し（ＦＩＦＯ）バッファ手段であることが好ましい。
【００１６】
本発明の前述した目的および他の態様は、以下の説明および添付図面によって更に良く理解される。
【発明を実施するための最良の形態】
【００１７】
以下、図面を参照しながら、本発明の好ましい実施形態について説明する。
【００１８】
回路切り換えのための単純なルータのアーキテクチャ（構造）が図１に説明の目的で示されている。ルータは、バッファを含むＮ個の入力ポートと、Ｍ個の出力ポートと、ルータテーブルにしたがって入力から出力へと（同時に）データを転送するためのスイッチとから成る。回路切り換えにより、特定の時間の間に送信元から送信先へと物理的な経路にわたって接続を行なうことができる（Leijten, J. A. J.;van Meerbergen, J. L.; Timmer, A. H.;Jess, J. A. G.;「高性能マルチプロセッサにおけるリアルタイムタスク間でのストリーム通信」，Design, Automation and Test in Europe，１９９８年、議事録、１９９８年２月２３日〜２６日、１２５〜１３１頁）。
【００１９】
ルータにおいて、データは、タイミングを図るため、特定の時間の間、キュー内に記憶される。したがって、ルータネットワークにわたる回路切り換えは、ネットワークにわたるデータ転送が１つのホップだけではなく複数のホップ（経路上の各ルータ毎に１つずつ）を含んでいるという点で、共有バスＴＤＭＡアーキテクチャとは異なる。この場合、各ホップ（ルータ）は、異なるルータテーブルを有している。また、回路切り換えは、マスタ−スレーブにより或いはルータ入力−出力ポートとの関連で後述するように対がスケジュールされる特定の形式のＴＤＭＡである。
【００２０】
個々のルータのルータテーブルは、経時的にコンテンションフリーな態様でクロスバースイッチをプログラムするための情報を含んでいる。このため、時間がスロットと呼ばれる所定の複数の単位時間に分けられる。１スロット中においては、フリット（フロー制御数字）と呼ばれるデータの単位をクロスバースイッチによりルータ入力バッファから出力へと転送することができる。特定のスロットにおける入力／出力マッピングは、Ｓ×Ｍサイズのマトリクス（行列）であるルータテーブルＴによって特定される。ここで、Ｓはスロットエントリの数であり、Ｍはルータの出力端子の数である。Ｔの要素は組｛φ，Ｉ，．．．，Ｎ｝内にある。値ｎ＝Ｔ（ｓ，ｍ）（０＜ｓ＜Ｓおよび０＜ｍ＜Ｍ）は、スロットｓにおいてｎ≠φの場合にフリットが入力ｉｎから出力ｏｍへと転送されることを意味している。そのため、Ｔの行ｓは、スロットｓにおけるマッピングを特定する。スロット割り当てＴは、ｓ＝ｋ ｍｏｄ Ｓにしたがって、時間と共に周期的に繰り返され、ここで、ｋはスロット反復子である。
【００２１】
したがって、ネットワーク内の全てのルータのルータテーブルは、Ｓ個のタイムスロットを有している。同時性の論理的概念が存在する。すなわち、ネットワーク内の全てのルータは、前述したように、同じ所定の持続スロット内にある。スロット反復ｋにおいては、多くとも１つのデータブロックが出力ポート毎に書き込まれる。ネットワーク中のルータの出力は、入力／出力対間のリンクにより、ルータの入力に接続されている。そのようなリンクにより、スロット反復ｋにおいて１つの出力に書き込まれるブロックが、次のスロット反復でリンクにより接続される入力のキュー内に存在するようになる。次のスロットｋ＋１中において或いはその後において、到達したブロックは、その適切な出力ポートに対して再び書き込まれる。したがって、ブロックは、記憶装置内を伝搬してファッションを転送する。ブロックがルータ毎に要する待ち時間は、（経路に沿うその後の２つのルータの予約によって与えられる）ブロックの発着時間の差が乗じられるスロットの持続時間に等しい。帯域幅は、Ｓ個のスロット毎のブロックサイズの倍数単位で保証される。
【００２２】
送信元から送信先への経路において確保（予約）されたスロットは、ルータ毎に少なくとも１（モジュロＳ）だけ増大する。スロットｓが経路上の特定のルータで確保（予約）され且つスロット（ｓ＋ｑ）％Ｓ（ｑ＞０）が経路上の次のルータで確保（予約）される場合には、経路のこの部分において要した待ち時間はｑスロットである。
【００２３】
ルータの入力におけるブロックの到達順序は、これらのブロックがルータの出力のうちの１つを通じて書き込まれる順序と同じでなければならない。これは、ＦＩＦＯによって入力に接続されるキューの実施を可能にする。
【００２４】
ルータテーブルのエントリは、全てのスロット毎に出力を入力に対してマッピングする。すなわち、Ｔ（ｓ，０）＝ｉである。そのスロットにおけるその出力のための確保（予約）が存在しない場合には、エントリは空である。出力毎に多くとも１つの入力しか存在しないため、コンテンションは全く生じない。１つの入力を複数の出力に対して送信する（マルチキャスト）ことができる。
【００２５】
ＧＴ（保証スループット）ルーティング法において、特定のルータにおいてタイムスロットｓで読み取られる全てのＧＴトークンは、トークンが辿る経路中の次のルータにおいてタイムスロット（ｓ＋ｑ）％Ｓで読み取られる。ｑの値は、少なくとも１であり、選択されたスケジュールの結果である。それはできる限り小さいことが好ましい。なぜなら、接続の全体の待ち時間が、経路に沿う全てのｑの合計に等しいからである。保証スループット（ＧＴ）サービスは、最悪の場合のシナリオのためにリソース予約を必要とするが、これは費用が高くなる可能性がある。
【００２６】
ルータテーブルサイズＳ＝４での２つの２×２ルータＲ１，Ｒ２を含む単純なルータネットワークの一例が図２に示されている。この図では、４つのＧＴ接続がデータストリームｓ１，ｓ２，ｓ３，ｓ４によって表されている。そのデータストリームのために割り当てられるタイムスロットの数が図２の括弧内に示されている。
【００２７】
第１のルータＲ１の第１の出力ポート（図２では上側ポートとして示されている）は使用されておらず、したがって、ルーティングテーブルの第１の列は空である。第１のルータＲ１のルーティングマトリクスの第２の列は、その入力からのトークンが第２の出力ポート（図２では下側ポートとして示されている）上に交互に書き込まれることを示している。したがって、第１のルータＲ１におけるコンテンション無くして、両方のデータストリームｓ１，ｓ２が所定の帯域幅をもってルーティング（経路指定）される。第２のルータＲ２において、第１の出力ポート（図２では上側ポートとして示されている）は、データストリームｓ１，ｓ３のトークンを受ける。データストリームｓ１からのトークンは、第１のルータＲ１においてはタイムスロット０，２でルーティングされるため、第２のルータＲ２においてはタイムスロット１，３でルーティングされる。これは、第２のルータＲ２のルータテーブルの第１の列における２つの「１」によって見られる。データストリームｓ３によって必要とされる１つのタイムスロットは、第１の列のタイムスロット２においてスケジュールされる。同様に、第２のルータＲ２のルータテーブルの第２の列で「１」により示されるように、データストリームｓ２のトークンはタイムスロット０，２においてスケジュールされる。最終的に、データストリームｓ４のトークンはタイムスロット１においてスケジュールされる。
【００２８】
ＧＴトークンが全ての予約されたタイムスロットにおいて利用できる必要はない。ＧＴパケットが予約されたタイムスロットにおいて到達しない場合には、要求されているが使用されていないリンクのタイムスロットにわたってＢＥ（ベストエフォート）パケットを送信することができる。ベストエフォート（ＢＥ）サービスは、リソースを全く予約せず、したがって保証を行なわないが、一般に最悪の場合のシナリオではなく平均的な場合のシナリオのために設計されているため、リソースをうまく使用する。
【００２９】
ルータテーブル中のスロットの数Ｓは、リンクの帯域幅の全体の大きさを分割することができる粒度を決定する。Ｂがリンク毎の帯域幅の大きさを表している場合には、１つの接続がＢ／Ｓのかなりの部分で帯域幅を割り当てることができる。そのため、全てのルータのスロットテーブルエントリの数の増大を意味するＳの増大により、粒度が更に細かくなる。しかしながら、ルータテーブルのサイズが更に大きいと、シリコン領域においてルータのコストが高くなる。現在の評価では、ルータテーブルが全ルータシリコン領域の５０％程度を占められることが分かっている。また、大きなルータテーブルは動作上の欠点も有している。すなわち、高い大域幅および中間の帯域幅の接続においては、多数のスロットをプログラムしなければならない。これは、接続のセットアップおよび解除時間において高くつく。
【００３０】
図３は、直列に接続された２つの２×２ルータＲ１，Ｒ２の組み合わせの一例を示している。この場合、２つの２×２ルータがＲ１，Ｒ２で示されており、また、ネットワーク端子がｔｉ（ｉ＝１，２，．．．，６）で示されている。
【００３１】
第１のルータＲ１が端子ｔ１を介してＢＥパケットを受けるとともに、これらのパケットが全て端子ｔ５へ向かうことになっており、また、これらのパケットの帯域幅がリンクの容量の１０％を必要とすると仮定する。同様に、パケットは、端子ｔ２から端子ｔ６へと向かうとともに、リンク容量の１％しか必要としない。第２のルータＲ２は、端末ｔ６へと向かうことになっている端子ｔ４を介してＧＴデータストリームを受ける。ＧＴデータストリームは、帯域幅の９９％を要求して使用し、したがって、時間の９９％の間、ルータＲ２の出力ポートｂから端子ｔ６に向かう出力リンクを占める。そのため、ＢＥストリーム共有ポートｂは、残りの１％のリンク容量においてフリットだけを送ることができ、また、ＧＴデータがポートｂにおいて到達する毎に、ポートｂにわたるＢＥパケットの送信がプリエンプト（pre-empted)される。
【００３２】
これは、１％のＢＥデータストリームのパケットにおいて長い待ち時間を引き起こす可能性がある。この場合、待ち時間は、パケットがネットワークにわたって送信される持続時間として規定される。また、待ち時間により、ルータＲ１，Ｒ２間のリンクは、１％のＢＥストリームによってほぼ連続的に占められる。これは、異なるパケットのフリットがインタリーブされないからである。したがって、１０％のデータストリームのＢＥパケットは、リンクの速度の１０％未満を得る。これにより、図３の例において、ルータＲ１，Ｒ２間のリンクは、その理論的容量の１１％未満の利用度を有する。
【００３３】
この問題を解消するため、基本的に３つの手法がある。すなわち、（１）いわゆるワームホールルーティングではなく仮想カットスルールーティングを使用する、（２）データが無い長い期間およびデータの比較的大きなブロックにおいてＧＴ通信を実行する、（３）１％のＢＥストリームにおいてＧＴサービスを使用する。
【００３４】
最初の手法は、次のルータの入力リンクがブロックしないように、全てのパケットが次のルータで受け入れられることを保証する。しかしながら、これにより、メモリが余計に必要になる。
【００３５】
２番目の手法では、フリット強制排除がめったに生じない。ＧＴデータの９９％が１０時間単位のブロックでグループ化される場合、この帯域幅は、９９個のデータブロックを選択的に送信した後に１０時間単位を無くすることにより得られる。ＢＥデータストリームのパケットサイズがそのような１０時間単位と比べて小さい場合には、１％ＢＥデータストリームの全パケットが１０時間単位で送られ、パケットが送信された直後に１０％ＢＥデータストリームによりルータＲ１，Ｒ２間のリンクを使用することができる。最初の手法ではルータにおいて更なるメモリが必要になるが、この２番目の手法では、ＢＥデータストリームにおいて更なる待ち時間が必要になる。
【００３６】
第３の手法においては、端子ｔ２，ｔ６間の接続を実現するためにＧＴサービスが使用される。したがって、ルーティングテーブル中の１００個の全てのスロットから１つを予約することにより特定の瞬間に比較的低い帯域幅のストリームがスケジュールされる。これにより、スロットテーブルは、少なくとも１００エントリのサイズを有している必要がある。ＧＴサービスにより予約期間中に回路切り換え接続が得られるため、接続は、ルータＲ１，Ｒ２間のリンク容量のせいぜい１％しか使用しない。残りのリンク容量は、１０％ＢＥストリームのために利用できる。
【００３７】
３番目の手法は、低帯域幅および高帯域幅の両方を要する一組の接続を効率的に記憶するための手段を必要とする。これは、階層予約テーブルによって達成される。予約テーブルによってかなりの量のエリアオーバーヘッドが費やされるとすると、テーブルはＬ層に構造化される。すなわち、Ｔ＝（Ｔ１，．．．，ＴＬ）である。層ｌ＝１，．．.，Ｌのテーブルは、Ｓ１行から成るサイズと、ｗ１（>１）の重みとを有している。重みは帯域幅の大きさを定め、対応する予約テーブルのスロットが他の層の重みに比例して表す。これは、Ｌ個のテーブルの組み合わせスケジュールを構成することにより実現される。この組み合わせスケジュールにおいては、周期毎に、テーブルＴｌ，ｌ＝１，．．．，Ｌがｗ１回それぞれ循環される。そのため、有効スロットサイクル周期Ｓｅは以下のようになる。
Ｌ （１）
Ｓｅ＝Σｗｌ・Ｓｌ
ｌ＝１
【００３８】
また、これは、物理的な予約テーブルエトリを殆ど犠牲にしない。
Ｌ （２）
Ｓ＝ΣＳｌ
ｌ＝１
【００３９】
方程式（１）から、層ｌのスロットが全リンク帯域幅Ｂの比ｗｌ／Ｓｅに対応していることが分かる。
【００４０】
多層ルータテーブルを含むそのようなル−タアーキテクチャが図４に概略的に示されている。
【００４１】
図５は、多層手法に係る図３に示されるような状況におけるルータテーブルのファイリングを示している。ここでは、２つの層が必要とされる。１つのストリームがベストエフォートストリームであり、これがｂｅ１で示されている。また、２つの他のストリームが保証スループットである。これらはｇｔ１，ｇｔ２で示されている。両方のストリームをスケジュールする各ルータのルータテーブルは２つの層に分割され、各層は異なる重みを有している。第１の層は、重み１を有するとともに、ｇｔ２をサポートする。第２の層は、重み９９を有するとともに、ｇｔ１をサポートする。マトリクスＴ１ｌ，Ｔ２ｌは、ルータＲ１，Ｒ２のそれぞれにおける第１の層１に関連付けられた２つのサブテーブルを規定する。マトリクスＴ１２，Ｔ２２は、第２の層２のための予約を与える。したがって、第２の層２におけるスロットの予約は、第１の層１におけるスロットの予約よりも９９倍大きい帯域幅割り当てを必要とする。２層手法の結果として、スロットエントリＳの総数は、この場合において、３よりも多くなる必要はない。
【００４２】
様々なテーブルのエントリが列挙される方法は、ネットワークを通じた待ち時間要件に依存しており、また、層毎の独立したバッファリングに関して余計なコストを費やすことが望まれているかどうかに依存している。
【００４３】
以下の説明は、２つのバッファオプションを扱っている。両方のケースでは、ネットワーク内の全てのルータにおいて一方の層から他方の層への切り換えが同期して行なわれるものとする。
【００４４】
様々な層のテーブルが経時的にインタリーブされるため、ルータの層コントローラは、遅かれ早かれ、１つの層のテーブルの列挙を中断して、他の層のうちの１つを続ける。先入れ先出し（ＦＩＦＯ）バッファポリシーが入力毎に使用される場合、ＦＩＦＯは、コントローラが他の層に切り換わるレベルに属するデータを含んでいてはならない。さもなければ、データがだめになってしまう。そのようなポイントを特定の層において全てのルータのテーブル中で見出すことは取るに足りないことではない。なぜなら、一般に、ネットワークを通じた多くの経路が経時的に互いに重なり合うからである。経路を横切ることなく異なる層への巧みな切り換えを行なうことができる自然なポイントは、テーブルの最後のエントリの後ということもあり得る。しかし、循環スケジュールの場合、そのようなポイントは全く終了しない。すなわち、循環スケジュールにより、ルータを経由する経路を２つの部分に分けることができる。この場合、第１の部分はテーブルの最後でスロットを使用し、第２の部分はテーブルの最初にスロットを使用する。すなわち、１つの経路をテーブルの境界上で重ね合わせることができる。実際には、「入力毎に１つのＦＩＦＯ−手法」における有効な割り込みポイントを有するスケジュールにより、リンク利用度が低下する。
【００４５】
更に優れたバッファ手法は、図４と併せて図６に示されるように、レベル毎に入力フリットをＦＩＦＯに記憶する。図４に示されるように、複数のバッファＱが設けられている。この場合、各入力ｉ１〜ｉＮは、そのようなバッファＱに結合されている。図６には、そのようなバッファＱの構成が概略的に示されている。この概念において、様々なレベルのＴＤＭＡスケジュールは、それ自体が論理的に独立する異なるキューを使用する。そのため、予約テーブルを環状にすることができ、層間の切り換えを経時的な任意の瞬間において行なうことができる。
【００４６】
なお、ネットワークを通じた待ち時間は、２つのバッファリング方法において同じではない。
【００４７】
便宜上、高帯域幅接続と低帯域幅接続との間の割合および接続数はそれぞれ、１：９９および３と、小さく維持される。しかしながら、実際には、接続の割合および数がもっと大きくても良い。
【００４８】
多層スロットテーブルの利点は以下のように示される。簡単のため、図４にしたがってネットワークオンチップがたった１つのルータから成ると仮定する。また、１つの特定の出力ポートを通じて流れる保証スループット接続に焦点を合わせることとする。また、この出力を通じて流れる６０個のＧＴストリームが存在するものとする。これらのストリームの帯域幅要件は以下の通りである。すなわち、５０個のＧＴストリームが１Ｍｂ／ｓであり、１０個のＧＴストリームが１Ｇｂ／ｓである。そのため、全体の総帯域幅は少なくとも１０．０５Ｇｂ／ｓである。
【００４９】
以下、層の数およびスロットテーブルエントリの数が異なるスロットテーブルの３つの例Ａ，Ｂ，Ｃについて説明する。
【００５０】
例Ａは、１００５０個のスロットから成る１つのスロットテーブルを利用する。１つのリンクの帯域幅を１０．０５Ｇｂ／ｓとして、スロット毎の帯域幅が１／１００５０×１０．０５Ｇｂ／ｓ＝１Ｍｂ／ｓとなるようにする。ここで、１Ｍｂ／ｓの５０個のＧＴストリームはそれぞれ１スロットを確保する必要があり、また、１Ｇｂ／ｓの１０個のＧＴストリームはそれぞれ１０００個のスロットを確保する必要がある。
【００５１】
例Ｂも、同様に、単層スロットテーブルであるが、ここではちょうど２５０個のスロットエントリから成るスロットテーブルを利用する。この減少した数のスロットエントリは、かなりのコストを節約する。６０個のストリームにわたる２５６個のスロットの最適な分配は以下の通りである。すなわち、１Ｍｂ／ｓの５０個のストリームはそれぞれ１スロットを使用し、１Ｇｂ／ｓの１０個のストリームはそれぞれ残りの２０個のスロットを使用する。ここで、全てのストリームの帯域幅要件を満たすため、リンクの帯域幅は２５０／２０×１Ｇｂ／ｓ＝１２．５Ｍｂ／ｓでなければならない。したがって、スロット毎の帯域幅は５０Ｍｂ／ｓである。この実現には欠点があるのが分かる。すなわち、第１に、例Ａよりも２５％多い帯域幅を有するリンクを必要とするという点であり、また、第２に、この余計な帯域幅を他の接続において利用できないという点である。これは、そうすることを５０Ｍｂ／ｓの帯域幅粒度が許容しないからである。
【００５２】
例Ｃは２層スロットテーブルを使用する。スロットテーブルの第１の層は、スロット毎の帯域幅が１Ｍｂ／ｓである５０個のエントリから成る。スロットテーブルの第２の層は１０個のエントリから成る。この場合、各スロットの帯域幅は１Ｇｂ／ｓである。したがって、その後の層の重みｗｌは、１および１０００である。この実現では、例Ａと同様に、リンクの帯域幅を１０．０５ＧＢ／ｓにする必要があるが、我々は、全体で６０個のスロットテーブルエントリしか必要としない。その数は、例Ａの数の０．６％にすぎない。
【００５３】
以上、添付図面に示される実施例を参照して本発明について説明したが、本発明がそれに限定されず、添付の請求項に開示された範囲内において多くの方法で本発明を変形できることは明らかである。
【図面の簡単な説明】
【００５４】
【図１】時分割多重化回路切り換えルータの概略的な基本ブロック図を示している。
【図２】直列に接続された２つのルータの組み合わせ及び４つの保証スループットデータストリームのフローを概略的に示している。
【図３】２つの２×２ルータを有する単純なルータネットワーク、及び２つのデータストリームがベストエフォートであり１つのデータストリームが保証スループットである３つのデータストリームのフローを概略的に示している。
【図４】本発明の好ましい実施形態に係る多層ルータテーブルを含む時分割多重化回路切り換えルータの概略的なブロック図を示している。
【図５】本発明の好ましい実施形態に係る２つのルータから成るネットワークを通じて伝搬する３つのデータストリームのフローの概略図を示している。
【図６】入力毎に図４のルータに含まれる複数のバッファの概略的なブロック図を示している。
【特許請求の範囲】
【請求項１】
複数の入力手段と、
少なくとも１つの出力手段と、
前記入力手段と前記出力手段との間を切り換えるとともに、所定のタイムスロット中に、選択された前記入力手段を前記出力手段に接続するための切り換え手段と、
所定のタイムスロットにおいてどの入力手段が出力手段に接続されるかについての命令を含み、前記切り換え手段を制御するためのルータテーブル手段と、
を備え、
前記ルータテーブル手段が複数のテーブル（Ｔｌ）（ｌ＝１，．．．，Ｌ）に分割され、各テーブルは、他のテーブルにおける予約に関連して１つのテーブルにおける予約毎に帯域幅の大きさを指定する重み（ｗｌ>１）を有していることを特徴とするルータ。
【請求項２】
前記ルータテーブル手段が複数の階層レベルに分割され、各テーブルが特定の階層レベルに割り当てられる請求項１に記載のルータ。
【請求項３】
前記テーブルの重みがプログラム可能である請求項１または２に記載のルータ。
【請求項４】
前記各テーブル（Ｔｌ）が多数の行（Ｓｌ）を含んでいる請求項１乃至３のいずれかに記載のルータ。
【請求項５】
所定時間毎に前記テーブル（Ｔｌ）が各重み（ｗｌ>１）に対応して多数回（ｗｌ）循環される請求項１乃至４のいずれかに記載のルータ。
【請求項６】
有効スロットサイクル周期（Ｓｅ）は、
Ｌ
Ｓｅ＝Σｗｌ・Ｓｌ
ｌ＝１
である請求項４または５に記載のルータ。
【請求項７】
前記テーブル（Ｔｌ）のエントリが列挙される方法は、ルータが一部を成すネットワークを通じた待ち時間要件に依存している請求項１乃至６のいずれかに記載のルータ。
【請求項８】
複数のバッファ手段を備え、各バッファ手段はそれぞれ、前記入力手段と前記切り換え手段との間に接続され、前記各バッファ手段はそれぞれ、複数のテーブル（Ｔｌ）に対応する複数のバッファ部を備え、各バッファ部がそれぞれ１つのテーブルに割り当てられ、前記ルータテーブル手段は、前記テーブルにしたがって前記バッファ部を制御するために設けられている請求項１乃至７のいずれかに記載のルータ。
【請求項９】
前記バッファ手段が先入れ先出しバッファ手段である請求項８に記載のルータ。
【請求項１】
複数の入力手段と、
少なくとも１つの出力手段と、
前記入力手段と前記出力手段との間を切り換えるとともに、所定のタイムスロット中に、選択された前記入力手段を前記出力手段に接続するための切り換え手段と、
所定のタイムスロットにおいてどの入力手段が出力手段に接続されるかについての命令を含み、前記切り換え手段を制御するためのルータテーブル手段と、
を備え、
前記ルータテーブル手段が複数のテーブル（Ｔｌ）（ｌ＝１，．．．，Ｌ）に分割され、各テーブルは、他のテーブルにおける予約に関連して１つのテーブルにおける予約毎に帯域幅の大きさを指定する重み（ｗｌ>１）を有していることを特徴とするルータ。
【請求項２】
前記ルータテーブル手段が複数の階層レベルに分割され、各テーブルが特定の階層レベルに割り当てられる請求項１に記載のルータ。
【請求項３】
前記テーブルの重みがプログラム可能である請求項１または２に記載のルータ。
【請求項４】
前記各テーブル（Ｔｌ）が多数の行（Ｓｌ）を含んでいる請求項１乃至３のいずれかに記載のルータ。
【請求項５】
所定時間毎に前記テーブル（Ｔｌ）が各重み（ｗｌ>１）に対応して多数回（ｗｌ）循環される請求項１乃至４のいずれかに記載のルータ。
【請求項６】
有効スロットサイクル周期（Ｓｅ）は、
Ｌ
Ｓｅ＝Σｗｌ・Ｓｌ
ｌ＝１
である請求項４または５に記載のルータ。
【請求項７】
前記テーブル（Ｔｌ）のエントリが列挙される方法は、ルータが一部を成すネットワークを通じた待ち時間要件に依存している請求項１乃至６のいずれかに記載のルータ。
【請求項８】
複数のバッファ手段を備え、各バッファ手段はそれぞれ、前記入力手段と前記切り換え手段との間に接続され、前記各バッファ手段はそれぞれ、複数のテーブル（Ｔｌ）に対応する複数のバッファ部を備え、各バッファ部がそれぞれ１つのテーブルに割り当てられ、前記ルータテーブル手段は、前記テーブルにしたがって前記バッファ部を制御するために設けられている請求項１乃至７のいずれかに記載のルータ。
【請求項９】
前記バッファ手段が先入れ先出しバッファ手段である請求項８に記載のルータ。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公表番号】特表２００７−５００９８５（Ｐ２００７−５００９８５Ａ）
【公表日】平成１９年１月１８日（２００７．１．１８）
【国際特許分類】
【出願番号】特願２００６−５３０７９１（Ｐ２００６−５３０７９１）
【出願日】平成１６年５月１０日（２００４．５．１０）
【国際出願番号】ＰＣＴ／ＩＢ２００４／０５０６２２
【国際公開番号】ＷＯ２００４／１０２９８９
【国際公開日】平成１６年１１月２５日（２００４．１１．２５）
【出願人】（５９００００２４８）コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ (12,071)
【氏名又は名称原語表記】Ｋｏｎｉｎｋｌｉｊｋｅ Ｐｈｉｌｉｐｓ Ｅｌｅｃｔｒｏｎｉｃｓ Ｎ．Ｖ．
【住所又は居所原語表記】Ｇｒｏｅｎｅｗｏｕｄｓｅｗｅｇ １，５６２１ ＢＡ Ｅｉｎｄｈｏｖｅｎ， Ｔｈｅ Ｎｅｔｈｅｒｌａｎｄｓ
【Ｆターム（参考）】
【公表日】平成１９年１月１８日（２００７．１．１８）
【国際特許分類】
【出願日】平成１６年５月１０日（２００４．５．１０）
【国際出願番号】ＰＣＴ／ＩＢ２００４／０５０６２２
【国際公開番号】ＷＯ２００４／１０２９８９
【国際公開日】平成１６年１１月２５日（２００４．１１．２５）
【出願人】（５９００００２４８）コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ (12,071)
【氏名又は名称原語表記】Ｋｏｎｉｎｋｌｉｊｋｅ Ｐｈｉｌｉｐｓ Ｅｌｅｃｔｒｏｎｉｃｓ Ｎ．Ｖ．
【住所又は居所原語表記】Ｇｒｏｅｎｅｗｏｕｄｓｅｗｅｇ １，５６２１ ＢＡ Ｅｉｎｄｈｏｖｅｎ， Ｔｈｅ Ｎｅｔｈｅｒｌａｎｄｓ
【Ｆターム（参考）】
[ Back to top ]