(57)【要約】ネットワーク用のルータが、第１の数Ｎi個の入力(Ｉ)の１つから第２の数Ｎo個の出力(Ｏ)の１つ以上にデータトラフィックを導くように構成されている。各入力は、データをバッファ記憶するための第３の数ｍ個の入力待ち行列を有する。第３の数ｍは１より大きいが、第２の数Ｎoより小さい。このルータは、１つの入力で受信したデータを、この入力の選択した入力待ち行列に書き込むための第１選択装置、及び入力待ち行列から選択した出力にデータを供給するための第２選択装置を具えている。総数Ｎj,k個の入力において、互いに異なる宛先Ｏj及びＯkを有するパケットの対が同じ待ち行列内に配列され、各ｊ，ｋについてＮj,k＜Ｎiであることを特徴とする。
2008532408.tif 000002
【特許請求の範囲】
【請求項１】
第１の数Ｎi個の入力の１つから第２の数Ｎo個の出力の１つ以上にデータトラフィックを導くように構成されたネットワーク用のルータであって、前記入力の各々が、データをバッファ記憶するための第３の数ｍ個の入力待ち行列を有し、前記第３の数ｍは１より大きく、かつ前記第２の数Ｎoより小さく、前記ルータが、
１つの前記入力で受信したデータを、当該入力の選択した前記入力待ち行列に書き込むための第１選択装置と；
前記入力待ち行列からのデータを、選択した前記出力に供給するための第２選択装置とを具え、
総数Ｎjkの前記入力において、互いに異なる宛先Ｏj及びＯkを有するパケットの対が同じ待ち行列内に配列されるネットワーク用ルータにおいて、
各ｊ，ｋについて、Ｎj,k＜Ｎiであることを特徴とするネットワーク用ルータ。
【請求項２】
各ｊ，ｋについて、Ｎj,k≦Ｎi−ｍであることを特徴とする請求項１に記載のルータ。
【請求項３】
【数１】
2008532408.tif 000024
を満足することを特徴とする請求項２に記載のルータ。
【請求項４】
【数２】
2008532408.tif 000025
をｉ毎に最小化し、ここに、λi,kは入力Ｉiから出力Ｏkへのデータトラフィックの強度であり、εi,j,kは、共に入力Ｉiに到着し、それぞれが出力Ｏj及びＯkを宛先として有する２つのパケットが同じ前記入力待ち行列内に配列される場合に１であり、前記２つのパケットが同じ前記入力待ち行列に割り当てられない場合に０であることを特徴とする請求項１に記載のルータ。
【請求項５】
複数の機能ユニットを相互接続する請求項１〜４のいずれかに記載のルータを少なくとも１つ具えたネットワークを有するシステム・オンチップ。
【請求項６】
請求項１〜４のいずれかに記載のルータを少なくとも１つ具え、複数のコンピュータシステムを遠隔的に結合するコンピュータネットワーク。
【請求項７】
第１の数Ｎi個の入力の１つから第２の数Ｎo個の出力の１つ以上にデータトラフィックをルーティングする方法であって、
１つの前記入力に到着するパケットに対して、当該パケットをバッファ記憶するためのｍ個の入力待ち行列の１つを選択するステップと；
前記入力待ち行列の出力端にあるパケットを転送すべき前記出力を選択するステップとを具え、
総数Ｎjkの前記入力において、互いに異なる宛先Ｏj及びＯkを有する前記パケットの対が同じ前記入力待ち行列内に配列されるデータトラフィックのルーティング方法において、
各ｊ，ｋについて、Ｎj,k＜Ｎiであることを特徴とするデータトラフィックのルーティング方法。
【請求項８】
第１の数Ｎi個の入力、第２の数Ｎo個の出力、及び前記入力毎に第３の数ｍ個の入力待ち行列を有するルータにおける、データパケットの前記入力待ち行列への分配を計算する方法において、
ａ．前記入力待ち行列の各々に割り当てられる行の数が最大でも１だけ異なるものとして、１番目の入力に到着するデータパケットについて、当該データパケットの宛先に応じて、前記入力待ち行列への前記データパケットの割り当てを選択するステップと；
ｂ．次の入力であるｒ番目の入力に対して、次の関数：
【数３】
2008532408.tif 000026
を最小化する割り当てを選択するステップと；
ｃ．ｒ＜Ｎiである場合に、ｒを増加させてステップｂ．を繰り返すステップと
を具えていることを特徴とするデータパケットの分配の計算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
ネットワークは、複数のシステムをフレキシブル（柔軟）な方法で結合する実際的なアーキテクチャである。こうしたネットワークは例えばローカルエリアネットワークがあり、さらに、ＮｏＣｓ（ネットワークス・オン・チップ：チップ上のネットワーク）は、将来のＩＰブロック（Intellectual Property Block：知的財産ブロック）間のオンチップ（チップ上）相互接続用の可能な解決法として新興しつつある。ＩＰブロックは、いくつかの特定機能（例えばＣＰＵ、メモリ、ＤＳＰ）を有するモジュールである。ネットワークは、少なくとも１つのルータ、及び互いに通信する複数の機能ユニットまたはブロックを具えている。ネットワークは、他の解決法（例えばバス）に比べて、ブロック数が増加する際に容易に拡張可能であるという点がある。
【背景技術】
【０００２】
機能ユニットは、ネットワーク・インタフェース経由でルータに結合することが好ましい。ネットワーク・インタフェースは、少なくとも次の２つの主要機能を提供する：(i)ブロック固有のプロトコルの、ネットワークに適したプロトコル（ネットワーク・プロトコル）への移行、及び(ii)特別な通信の特性及び／またはサービス（例えばＱｏＳフロー制御）を通信に提供すること。ルータに直接接続されたブロックはこれらの機能そのものをすべて実現しなければならない。他方では、ネットワークは、メモリーコントローラのようなこれらの機能そのものを提供するモジュールを具えることができる。ネットワーク・プロトコルを伴う通信の共通した管理及びメモリの管理は、メモリのアクセスレート（アクセス速度）にとって有利であり得る。
【０００３】
ネットワーク内では、ルータは、互いにブロック（阻害）し合い得る複数のデータトラフィック・ストリームを管理しなければならない。例えば、バッファの出力におけるトラフィックはブロックされ得る、というのは、このトラフィックは次のルータによる受け取りを待機しているか、あるいは２つの入力が同じ出力（接続）に行こうとするからである。
【０００４】
ブロックされたトラフィックをバッファ記憶（一時記憶）するための、いくつかの待ち行列（キューイング）方策が知られている。
【０００５】
出力待ち行列：ルータの各出力が、各入力から来るデータ用に別個の待ち行列（キュー）を有する。
【０００６】
仮想待ち行列：各入力が、各出力宛てのデータ用に別個のキューを有する。
【０００７】
入力待ち行列は、いわゆるヘッド・オブ・ライン（ＨＯＬ：Head of Line）ブロッキングにより処理能力が比較的低いという欠点を有する。ＨＯＬブロッキングは、待ち行列の前端にあるデータが出力への伝送を待機している際に発生する。このことは、待ち行列内の他のデータの伝送を、このデータの宛先としての出力が空いていてもブロックする。
【０００８】
この問題は、出力待ち行列及び仮想出力待ち行列によって克服される。しかし、これらの解決法は共に、待ち行列を実現するために大量のメモリを必要とする。
【０００９】
【非特許文献１】Kolias, C. and Kleinock, L., “Throughput analysis of multiple input queuing in ATM switches”
【００１０】
多入力待ち行列は、限定量のメモリで妥当な処理能力を得ようとする解決法である。このことは、オンチップ・ネットワークにとっては、メモリはチップ上の少ないリソース（資源）であるので、特に重要である。多入力待ち行列の場合には、各入力が複数のキューを有する。入力に到着するトラフィックはその宛先に応じて複数の待ち行列に分配される。入りのトラフィックを分配する既知の方法は、Kolias, C. and Kleinock, L.著：“Throughput analysis of multiple input queuing in ATM switches”, In MASON, L., and Casaca, A. (編集)： Broadband communications (Chapman & Hall, London, UK, 1996)の382〜393ページに記載されている。この文献では、いわゆる奇数−偶数ルールに従ってトラフィックを第１及び第２待ち行列に分配することが提案されている。このルールは、奇数番号の待ち行列宛てのパケットを第１待ち行列に割り当て、偶数番号の宛先を有するパケットを第２待ち行列に割り当てる。このようにして、奇数番号の宛先を有するストリームは偶数番号の宛先を有するストリームをブロックしない。多入力待ち行列は、（単）入力待ち行列に比べて処理能力を大幅に改善しつつ、必要とするメモリは出力待ち行列または仮想出力待ち行列よりもずっと小量である。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
本発明の目的は、要求されるメモリを増加させることなしに、処理能力をさらに改善するネットワーク用のルータを提供することにある。
【課題を解決するための手段】
【００１２】
本発明によれば、この目的は請求項１によって達成される。
本発明による方策は次の見識に基づくものである。
ルータの処理能力は、データを伝送することのできる入力の数に依存する。毎回、データのパケットを各入力から１つの出力に伝送することのできる場合には、処理能力（スループット）は１である。平均的に、データのパケットをＮi個のうちｎ個の入力から１つの出力に伝送することのできる場合には、処理能力はｎ／Ｎiである。処理能力は、伝送することのできるパケットの割合の加重平均によって計算することができる。
【００１３】
この目的のために、ルータの状態をＯ＝{ｏij}なる行列Ｏとして定義し、ここにｏijは、入力Ｉiにおける待ち行列ｊのＨＯＬパケットの宛先である出力を示す。
処理能力Ｔは、
【数４】
2008532408.tif 000003
で表され、ここにｐnは、（全体のうち）ｎ／Ｎiの割合のパケットが出力に伝送される状態が発生する確立である。
【００１４】
例えば、４つの入力、４つの出力、及び１入力当たり２つの待ち行列を有するルータは次の行列：
【数５】
2008532408.tif 000004
を有する。
【００１５】
こうしたルータが奇数−偶数ルールを用いて入力トラフィックを複数の待ち行列に分配する場合には、このルータは、一度に２つの入力パケットしかその宛先に伝送することのできない状態を４通り有する。これらの状態は、２のマッチング（整合）を有すると称され、次式で表される：
【数６】
2008532408.tif 000005
【００１６】
３のマッチングを有する７２通りの状態、及び４のマッチングを有する１８０通りの状態も存在する。これらを合計すれば２５６通りの状態となる。
結果的に、処理能力は次式のようになる：
【数７】
2008532408.tif 000006
【００１７】
待ち行列が同じ宛先のＨＯＬパケットを有すれば上記確率は比較的高くなり、この確率は、異なる宛先を有するパケットの割り当てどうしの間の相関を低減することによって減少することを、発明者は認識している。
【００１８】
このことは、パケットの宛先だけでなく、パケットの発生源にも応じてパケットを待ち行列に割り当てることによって実現される。本発明によるこうした割り当ての一例では、割り当てられる待ち行列番号は((ｋ÷ｍ)＋ｉ)mod ｍであり、ここにｋは宛先である出力の数であり、ｉは入力番号である。
【００１９】
この割り当ては、異なる宛先を有するパケット対の同時発生を複数の入力の待ち行列により良好に分配することがわかる。パケットの対ｊ、ｋが同じ待ち行列内にある入力の数はＮi−ｍであることを示すことができる。このことは、少数のパケットしか処理することのできない悪い状態の数を低減する。均一なトラフィック分配の場合、即ち、ルータの各入力が平均的に時間単位当たり同数のパケットを受信し、そしてこれらのパケットの宛先が各出力に均等に分布している場合には、ほぼ同数の入力に対して、即ち次式：
【数８】
2008532408.tif 000007
の下に、宛先の対の各々を同じ待ち行列に割り当てれば、最適な処理能力を得ることができる。
【００２０】
Ｎavの値は、入力の数Ｎi、出力の数Ｎo、及び入力当りの待ち行列の数ｍから次のように計算することができる。
【００２１】
ｍ個の待ち行列が存在するので、待ち行列当たりＮo／ｍ個の出力が存在する。従って、各待ち行列内には
2008532408.tif 000008
対の出力が存在する。そして各入力は
2008532408.tif 000009
対の出力を有し、そしてＮi個の入力が
2008532408.tif 000010
対用の空間を有する。合計ではもちろん
2008532408.tif 000011
個の出力対が存在し、従って、各出力対は平均的に、次式：
【数９】
2008532408.tif 000012
個の入力における同じ待ち行列内にある。
【００２２】
トラフィックの分配が不均一である状況があり得る。この場合には、待ち行列のトラフィックへの割り当ては、次のようにトラフィック分配に適応させることができる：
λi,kを入力Ｉiから出力Ｏkへのデータトラフィックの相対強度とし、そしてεi,j,kは、共に入力Ｉiに到着し、それぞれ出力Ｏj及びＯkを宛先として有する２つのパケットが同じ待ち行列に割り当てられる場合には１とし、これらのパケットが同じ待ち行列に割り当てられない場合には０とする。従って、最適な処理能力は、次式の差：
【数２】
2008532408.tif 000013
をｉ毎に最小化すれば達成される。
【００２３】
以下、本発明のこれら及び他の特徴について図面を参照しながら詳細に説明する。
【発明を実施するための最良の形態】
【００２４】
図１にネットワークの例を示す。図に示す例では、このネットワークはオンチップ（チップ上の）ネットワーク（ＮoＣ）である。このネットワークは、相互接続された複数のルータ、ここではトーラストポロジの形に相互接続された４つのルータを具えている。各ルータはネットワークインタフェースＮＩに接続されている。各ネットワークインタフェースＮＩは、ＩＰブロックで表す１つ以上の機能ユニットに接続されている。このネットワークインタフェースは、ＩＰブロックからの情報をネットワークが処理することのできる情報に変換し、同様に、ネットワークからの情報をＩＰブロックが受け入れ可能な情報に変換する。例えば、ＩＰブロックは、ＯＣＰ、ＡＸＩ、またはＤＴＬのようなより高レベルのプロトコルを使用することができるのに対し、ネットワークは、データをパケットに入れて搬送するためのより低レベルのプロトコルを使用する。しかし、ＩＰブロック及びネットワークが同じプロトコルを使用する場合には、ネットワークインタフェースは不要である。図２に示すように、種々のネットワークトポロジが可能である。明瞭にするために、図２ａ以外はルータのみを示す。物理的には、トーラスは図２ｄに示す形または図２ｅに示す形のいずれでも実現することができる。図２ｄの物理的実現では、互いに連続するルータＲが互いに近接して配列されているが、最初のルータと最後のルータとの間の接続は比較的長い。図２ｅの実現では、ルータ間の接続がほぼ同じ長さを有する。
【００２５】
トーラストポロジとは別に、他の種々のトポロジが可能である。図２ａに示す完全に接続されたネットワークでは、すべての機能ユニットＮＩが同じルータＲに接続されている。あるいはまた、図２ｂに示すように、複数のルータを二次元（２Ｄ）メッシュの形に配列することができ、ここで各ルータは最近隣のルータに結合されている。
【００２６】
図２ｃに示すリニア（線状）アレイでは、ルータは連鎖（チェーン）の形に配列されている。先頭及び最終以外の各ルータは、先行及び後続するルータに結合されている。トーラストポロジは、その終端どうしを結合したリニアアレイと考えることができる。図２ｆに示すさらに別な配列はツリー（木）、例えばバイナリ（２分岐の）ツリーである。このツリー内では、ルータが階層的に組織されている。最低レベル以外の各ルータは、２つ以上のより低レベルのルータと通信することができる。また、最高レベル以外の各ルータは、より高レベルのルータと通信することができる。最高レベルのルータは最大のデータストリームも管理しなければならないので、ツリーは通常、いわゆるファット（太った）ツリーとして実現され、ここでは、より高レベルのルータ間の伝送能力がより低レベルのルータ間の伝送能力に比べて相対的に高い。このことは、ルータは、当該ルータに結合されたサブツリー（副木）のデータトラフィックを処理しなければならない、ということによる。ルータのレベルが高くなるほど、サブツリーのサイズも大きくなる。特に最高レベルのルータにおいてボトルネック（障害）が生じることを防ぐために、例えばツリーの上部にあるルータは、底部にあるルータよりも多くの配線で接続することによって、ルータ間の接続の帯域幅をこのトラフィックパターンに適応させ、ファットツリートポロジを生成する。
【００２７】
別なトポロジはいわゆるハイパーキューブ（超立方体）である。ハイパーキューブ・ネットワークトポロジは図７に示すように、トポロジ空間を論理的にｎ次元のハイパーキューブに体系化する。この種のトポロジを特徴付ける２つの良く知られた性質は、(a)ネットワーク上のすべてのノード（ルータ）がlogＮ個の隣接ノードによって包囲される、(b)ハイバーキューブ内の最長ルートはlogＮである。ここにＮはハイパーキューブ内のノードの数である。主な欠点は、この種のトポロジを物理的なハードウェアのレイアウトに移行することが困難なことである。
【００２８】
図３に、ルータをより詳細に示す。これらのルータは、第１の数の入力、この場合には４つの入力Ｉ0，Ｉ1，Ｉ2，Ｉ3、及び第２の数の出力Ｏ1，Ｏ2，Ｏ3，Ｏ4を具えている。この場合には、第２の数は第１の数に等しい。このことは実際的な選定である、というのは、データを送信するソース（送信源）は通常、データを受信する必要もあるからである。しかし、その代わりに、ルータが互いに異なる数の出力と入力を有することもできる。各入力は選択素子に接続され、選択素子は入力で受信したデータを、第３の数の入力待ち行列（キュー）、例えば入力Ｉ0用の待ち行列Ｑ0,1及びＱ0,2に転送する。選択素子Ｓ10，Ｓ11，Ｓ12，Ｓ13が一緒になって第１選択装置を形成する。図に示す実施例では、各入力が２つの入力待ち行列を有する。任意数Ｎoの出力を任意数ｍの入力待ち行列と組み合わせることができ、例えば、Ｎo＝４，ｍ＝２；Ｎo＝６，ｍ＝２；Ｎo＝６，ｍ＝３；Ｎo＝１２，ｍ＝２；等であり、入力待ち行列の数は出力の数の増加関数であることが好ましく、例えば入力待ち行列の数は出力の数の平方根におよそ等しい。
【００２９】
【非特許文献２】McKeon, ”The iSLP scheduling algorithm for input queued switches”, IEEE/ACM transactions on networking, Vol.7, No.2
【００３０】
このルータは、２つ以上の入力待ち行列のうち選択した１つからのデータを導くための第２選択装置を具えている。図に示す実施例では、第２選択装置は、各出力に結合された第２選択素子Ｓ20，Ｓ21，Ｓ22，Ｓ23を具えている。第２選択装置は、既知の原理に従って、例えばMcKeon著：”The iSLP scheduling algorithm for input queued switches”, IEEE/ACM transactions on networking, Vol.7, No.2, 1999年4月の188〜201ページに記載のアルゴリズムを用いて動作することができる。
【００３１】
図４に、第１選択素子の１つをより詳細に示す。第１選択素子は検出器ＤＥＴを具え、検出器ＤＥＴは入力パケット毎の宛先を検出し、そして多重素子ＭＵＸを制御する。多重素子ＭＵＸは、検出素子の制御信号に応答して、これらのパケットを複数の出力のうちの１つに転送する。Koliasによる文献１に記載のアルゴリズムでは、選択素子の動作は、次の表によって概略的に表すことができる：
【００３２】
【表１】
2008532408.tif 000014
【００３３】
各入力に到着するトラフィックは同じ方法で処理される。既知のアルゴリズム、即ち、上述した奇数−偶数ルールによれば、偶数番号の出力を宛先として有するパケットに割り当てられる待ち行列番号は０であり、奇数番号の出力を宛先として有するパケットに割り当てられる待ち行列番号は１である。このルールは各入力に適用される。
【００３４】
次の表は、異なる方法における既知のアルゴリズムの動作を示す。この表には、異なる出力を宛先として有する入力パケットを同じ待ち行列内にバッファ記憶するか否かを示す。この表より、出力０及び２を宛先として有するパケット、並びに宛先１及び３を有するパケットが常に同じ待ち行列内にバッファ記憶されることがわかる。他のパケットの対は決して同じ待ち行列内にバッファ記憶されない。換言すれば、互いに異なる宛先Ｏj及びＯkを有するパケットの対、ここでは宛先対として表すものは、４つの入力全部について同じ待ち行列内に配列されるか、あるいは全く同じ待ち行列内に配列されないかのいずれかである。
【００３５】
【表２】
2008532408.tif 000015
【００３６】
本発明によれば、総数Ｎi個の入力のうち、互いに異なる宛先Ｏj及びＯkを有する一対のパケットが同じ待ち行列内に配列される入力の総数ＮjkはＮi未満にすべきである。
【実施例１】
【００３７】
本発明の第１実施例Inv1では、パケットは次のルールに従って複数の入力待ち行列に分配される：
【００３８】
割り当てられる待ち行列番号は((ｋ÷ｍ)＋ｉ)mod ｍであり、ここにｋは宛先（出力）番号であり、ｉは入力番号である。この割り当てを、４つの入力及び４つの出力、及び入力毎に２つの待ち行列を有するルータについて次の表に示す：
【００３９】
【表３】
2008532408.tif 000016
【００４０】
次の表は、行毎に、それぞれ宛先Ｏj及びＯkを有する一対のパケットが同じ待ち行列内に配列される（１）か否か（０）を示す：
【００４１】
【表４】
2008532408.tif 000017
【００４２】
本発明によれば、総数Ｎiのパケット対に対して、互いに異なる宛先Ｏj及びＯkを有するパケット対が同じ待ち行列内に配列される総数はＮi未満にすべきである。特に、この総数は最大でもＮi−ｍである。
【００４３】
本発明のこの実施例では、２の最大マッチングを有する状態は２通りしか存在せず、即ち(0, 2, 2, 0, 2, 0, 0, 2)及び(1, 3, 3, 1, 3, 1, 1, 3)である。６８通りの状態が３の最大マッチングを有し、そして１８６通りの状態が４の最大マッチングを有する。各状態において期待される処理能力は等しい確率で生じ、そして最大マッチングを見つけるスケジューリング・アルゴリズムを使用する際には、平均処理能力は次式のように推定される：
【数１０】
2008532408.tif 000018
この処理能力は、奇数−偶数ルールを用いる既知のルータの処理能力に比べて増加している。
【実施例２】
【００４４】
本発明の第２実施例Inv2によれば、さらなる改善が提供される。この実施例によれば、総数Ｎiの入力に対して、互いに異なる宛先Ｏj及びＯkを有するパケット対が同じ待ち行列内に配列される入力の総数Ｎj,kの差を最大１にすべきである。
このことの例を次の表に示す：
【００４５】
【表５】
2008532408.tif 000019
【００４６】
次の表は、出力Ｏj及びＯkをそれぞれの宛先として有するパケットが同じ待ち行列に割り当てられる行数Ｎj,kを示す：
【００４７】
【表６】
2008532408.tif 000020
【００４８】
本発明のこの実施例では、各サイクルに少なくとも３つのパケットを伝送することができる。特に、２５６通りの状態のうち、３のマッチングを有する６４通りの状態、及び４のマッチングを有する１９２通りの状態が存在する。従って、平均処理能力は次式のように推定される：
【数１１】
2008532408.tif 000021
【００４９】
上述した処理能力の期待値では、入力Ｉiに到着し、宛先ｊ，ｋを有する、即ち出力Ｏj及びＯkを宛先として有するパケット対が同じ待ち行列内に配列される確率は、各対ｊ，ｋについておよそ同じである。以下では、Ｎi個の入力、Ｎo個の出力、及び１行当たりｍ個の待ち行列を有するルータ用の割り当て方策を、適度な演算数で計算するアルゴリズムについて図５を参照しながら説明する。
【００５０】
まず、ステップＳ1では、一般性を失うことなしに、単一入力用のすべての割り当てから任意の選定を行うことができる。例えば、出力Ｏkを宛先として有する第１入力Ｉ0のトラフィックは待ち行列(ｋ mod ｍ)に割り当てることができる。そして、(ｊ−ｋ mod ｍ)＝０ならばｃ0,j,k＝１であり、(ｊ−ｋ mod ｍ)≠０ならばｃ0,j,k＝０である。
【００５１】
ここで、最初の(ｒ−１)個の入力についての割り当てが見つかっているものとし、例えばｒ＝２である。従って、ｃi,j,kは、ｉ≦ｒ−１なるすべてのｉ、及び０≦ｊ＜ｋ＜Ｎoなるすべての出力対について固定である。そして、ステップＳ２では、ｒ番目の入力に対して、次式：
【数１２】
2008532408.tif 000022
を最小化する可能な割り当ての集合から割り当てを選択する。
このステップの後には、ｃi,j,kはｉ≦ｒなるすべての対ｊ，ｋについて固定である。
【００５２】
ステップＳ３では、ｒ＜Ｎ−１であるか否かを検証する。ｒ＜Ｎ−１である場合には、ステップＳ２を繰り返し、さもなければステップＳ４でアルゴリズムを終了する。
【００５３】
図６の表は、Ｎ＝６，８及び１０個の入力及び同数の出力、及び入力毎に２つの入力待ち行列を有するルータについての、本発明による入力待ち行列の最適な割り当てのいくつかの例を示す。これらの表には、入力Ｉi及び出力Ｏkを有するパケットがどちらの待ち行列（０または１）に割り当てられるかを示す。
【００５４】
上記計算は、ルータにおいて発生する各状態が独立であることを仮定している。実際には、いわゆる悪い状態は繰り返されるように見え、このため、実際に測定される処理能力では、飽和処理能力は平均処理能力より低い。次の表は、３通りの待ち行列の割り当て、即ち、既知の奇数−偶数ルールによる割り当て、本発明の第１実施例による割り当て、及び本発明の第２実施例による割り当てについての飽和処理能力を示す。この表は、本発明による待ち行列割り当てによって、待ち行列割り当て用の既知のルール、即ち奇数−偶数ルールに比べて飽和処理能力が改善されることも示している。
【００５５】
【表７】
2008532408.tif 000023
【００５６】
本発明はオンチップ・ネットワークについて例示したが、本発明は、ローカルエリアネットワーク及びワイドエリアネットワークのようなオフチップ（チップ外の）ネットワークにも同等に適用可能である。オンチップ・ネットワークでは、ルータは４〜６個の入力及びバッファ当たり２個の待ち行列を有することが多い。オフチップ・ネットワークは、より大きいルータ、例えば１２〜１６個の入力を有するルータを使用することが多い。これで最大の利点が得られる。しかし、オンチップ・ネットワークでは、オフチップ・ネットワークにおけるように、待ち行列用に必要なメモリは高価なリソースであり、本発明はこのリソースを可能な限り効率的に利用する。
【００５７】
なお、上述した実施例は本発明を限定するものではなく例示するものであり、当業者は多くの代案実施例を、請求項に記載の範囲を逸脱することなしに設計することができる。「具えている」及びその活用形は、請求項に挙げた以外の要素またはステップの存在を排除するものではない。いくつかの手段を挙げた装置の請求項では、これらの手段のいくつかを同一のハードウェアのアイテムによって具体化することができる。単に、互いに異なる従属請求項中に特定の方策が挙げられているということは、これらの方策の組合せを有利に用いることができないことを示すものではない。
【図面の簡単な説明】
【００５８】
【図１】本発明を適用可能なネットワークの例を示す図である。
【図２】ネットワーク用の種々のトポロジを示す図である。
【図３】ルータをより詳細に示す図である。
【図４】ルータの一部分をより詳細に示す図である。
【図５】入力毎に待ち行列を割り当てる方法を計算するアルゴリズムを示す図である。
【図６】本発明による待ち行列の最適な割り当ての例を示す図である。
【図７】ネットワーク用の別なトポロジを示す図である。
【図１】
2008532408.tif 000027
【図２ａ】
2008532408.tif 000028
【図２ｂ】
2008532408.tif 000029
【図２ｃ】
2008532408.tif 000030
【図２ｄ】
2008532408.tif 000031
【図２ｅ】
2008532408.tif 000032
【図２ｆ】
2008532408.tif 000033
【図３】
2008532408.tif 000034
【図４】
2008532408.tif 000035
【図５】
2008532408.tif 000036
【図６】
2008532408.tif 000037
【図７】
2008532408.tif 000038
【国際調査報告】
2008532408.tif 000039
2008532408.tif 000040
2008532408.tif 000041