(57)【要約】【解決手段】本発明は、各ルータの入出力ポートが特定の方向に循環して配置されており、各ルータが、入力ポートと所望の出力ポートとの間で循環オフセットを示すルーティング命令を入力パケット内で識別する手段と、ルーティング命令内で前記オフセットを削除し、そこにルータのアリティ（arity）と前記オフセットとの間の差を挿入することによりパケットを戻す手段とを備えるルーティングネットワークに関する。
2009514293.tif 000002
【特許請求の範囲】
【請求項１】
入出力ポートが夫々識別子に関連付けられてあり、該識別子により他の入出力ポートは各々に固有のコードに応じて夫々他の入出力ポートを特定することができるルータであって、
入力パケットで所望の出力ポートのフォワード識別子を示すルーティング命令を識別する手段と、
前記フォワード識別子がルーティング命令から削除されて、リターン識別子がそこに挿入されているパケットを返送する手段とを備えることを特徴とするルータ。
【請求項２】
入出力ポートは定められた順序に循環して配置され、フォワード識別子は入力ポートと出力ポートの間の循環シフトに相当し、リターン識別子はルータのアリティ（arity）と前記シフトの差に相当することを特徴とする請求項１に記載のルータ。
【請求項３】
請求項１又は２に記載のルータを備えたルーティングネットワークであり、送信元から宛先へ送られたパケットは、パケットが通過する必要があるルータ毎に入力ポートに対する出力ポートの連続した識別子を含むルーティング命令を有することを特徴とするルーティングネットワーク。
【請求項４】
識別子はパケットが通過する必要があるルータの順序で連続して配列されてあり、それによってルータから出るパケットのヘッド命令は次のルータの識別子になることを特徴とする請求項３に記載のルーティングネットワーク。
【請求項５】
各ルータではリターン識別子がルーティング命令の末尾に挿入されることを特徴とする請求項４に記載のルーティングネットワーク。
【請求項６】
各宛先は、宛先から送信元へのルーティング命令を形成するために、一連のリターン識別子に対応する受信したルーティング命令を再度順序付ける手段を備えることを特徴とする請求項３乃至５のいずれかに記載のルーティングネットワーク。
【請求項７】
前記差はそのビットの順序を反転した後挿入され、リターンパスを得るために、ルーティング命令は逆順で読まれることを特徴とする請求項２又は６に記載のルーティングネットワーク。
【請求項８】
請求項３乃至７のいずれかに記載のルーティングネットワークを含む集積回路。
【請求項９】
各ルータが、入力パケットのルーティング命令で、所望の出力ポートの相対的位置を示すフォワード識別子を識別する手段と、ルーティング命令から前記フォワード識別子を削除し、その中にリターン識別子を挿入することによりパケットを送り返す手段とを備えたルーティングネットワークでのルーティング方法であって、該方法は、送信元から宛先へメッセージを送るために、データパケットを送信元から宛先に送るべく予め提供されたルータにより選択される出力ポートの一連の識別子を送信元から送るステップを備えることを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、様々なディジタル装置間のデータパケットのルーティングに関する。
【背景技術】
【０００２】
ある場合には、バスの使用ではなく所与のタイムスロットの間にその入力のうちの一つとその出力のうちの一つとの間で夫々メッセージを送信することができるルータのネットワークを用いることが好ましい。
【０００３】
より具体的にはルータ及びルーティングネットワークは、様々な装置間のデータパケットの非常に速いルーティングを可能にするために、プロセッサ及びメモリ等の装置をいくつか含む集積回路チップに一体化されるように成してある。
【０００４】
ルータは入力ポート及び出力ポートを複数含む装置である。入力ポート及び出力ポートは別個かもしれないが、各入力ポートが出力ポートに相当し、またその逆でもあるとすると、各ポートが入出力ポートであると考えられる。従来、ルータは入力ポート毎に少なくとも一つの命令デコーダ、調整論理回路、各入力と各出力との間のスイッチングシステム及びメモリすなわち、現在では、例えばクロックパルスの間、入力及び出力間でデータパケットを一時的に記憶するための先入れ先出しメモリを備える。ルータの入出力ポートは、夫々別のルータ又は装置の入出力ポートに関連している。構造に応じて、ルーティングネットワークの各ルータのポートの数は一定か又は可変である。
【０００５】
現在、集積回路上に形成されたルータネットワークではルータの数は減少している。現在では、数十のルータのみが集積ルーティング回路に用いられている。
【０００６】
尚、ルータネットワークに接続された装置の一部は、入出力ポートを複数有するとき、それら自身ルータとして用いられてもよく、例えば多くのプロセッサの場合がそうである。
【０００７】
更に、各データパケットは特にルーティング命令及びデータを含むヘッダを有する。現在オンチップ集積システムでは、ヘッダのサイズは、特に送られるパスに相当し、送られたデータの量に対して無視できない。
【０００８】
従って、ルーティングネットワーク及び関連したルーティング方法の第１の制約は、ある装置から別の装置へデータパケットを送ることができるルーティング命令のサイズを最小にすることである。
【０００９】
チップ上で一体化されたルーティングネットワークの別の必要性は、特に消費と複雑さの点から、各ルータの寸法を最小にし、様々な性能を最適化することである。
【００１０】
更に、その宛先に届いたデータパケットが、その出どころである送信元への戻りに必要な要素を含むルーティング方法を提供することが望まれている。
【特許文献１】米国特許出願公開第２００７／２０８８７６号明細書
【発明の開示】
【発明が解決しようとする課題】
【００１１】
本発明の目的は、上述した制約の少なくとも一部を満足させることができるルータ及びルーティングネットワークを提供することである。
【課題を解決するための手段】
【００１２】
本発明は、絶対的な方法でこれらのポートを識別するのではなく、ルータの入出力ポートの特定の識別モードに基づき、それらは互いに相対的に特定される。
【００１３】
より具体的には、本発明は、入出力ポートが夫々識別子に関連付けられてあり、該識別子により他の入出力ポートは各々に固有のコードに応じて夫々他の入出力ポートを特定することができ、入力パケットで所望の出力端子のフォワード識別子を示すルーティング命令を識別する手段と、前記フォワード識別子がルーティング命令から削除されて、リターン識別子がそこに挿入されているパケットを返送する手段とを備えるルータを提供する。
【００１４】
本発明の実施例によれば、入出力ポートは定められた順序に循環して配置され、フォワード識別子は入力ポートと出力ポートの間の循環シフトに相当し、リターン識別子はルータのアリティ（arity）と前記シフトの差に相当する。
【００１５】
本発明は、更に上記のタイプのルータを含むルーティングネットワークを提供し、送信元から宛先へ送られたパケットは、パケットが通過する必要があるルータ毎に入力ポートに対する出力ポートの連続した識別子を含むルーティング命令を有する。
【００１６】
本発明の実施例によれば、識別子はパケットが通過する必要があるルータの順序で連続して配列されてあり、それによってルータから出るパケットのヘッド命令は次のルータの識別子になる。
【００１７】
本発明の実施例によれば、各ルータではリターン識別子がルーティング命令の末尾に挿入される。
【００１８】
本発明の実施例によれば、各宛先は、宛先から送信元へのルーティング命令を形成するために、一連のリターン識別子に対応する受信したルーティング命令を再度順序付ける手段を備える。
【００１９】
本発明の実施例によれば、前記差はそのビットの順序を反転した後挿入され、リターンパスを得るために、ルーティング命令は逆順で読まれる。
【００２０】
本発明は、更に上記のタイプのルーティングネットワークを含む集積回路を提供する。
【００２１】
本発明は、更に各ルータが、入力パケットのルーティング命令で、所望の出力ポートの相対的位置を示すフォワード識別子を識別する手段と、ルーティング命令から前記フォワード識別子を削除し、その中にリターン識別子を挿入することによりパケットを送り返す手段とを備えたルーティングネットワークでのルーティング方法を提供し、この方法は、送信元から宛先へメッセージを送るために、データパケットを送信元から宛先に送るべく予め提供されたルータにより選択される出力ポートの一連の識別子を送信元から送るステップを備える。
【００２２】
本発明の前述の目的、特徴及び利点その他を、添付図面を参照して本発明を限定するものではない具体的な実施の形態について以下に詳細に説明する。
【発明を実施するための最良の形態】
【００２３】
図１は、例えばプロセッサ、メモリ又はルータであってもよい装置D1乃至D5間でデータパケットが確実に送信されることを意図された９個のルータR11-R13 、R21-R23 、R31-R33 を含むルーティングネットワークの一例を単純化して概略的に示す。異なるルータ及び装置間のリンクは図面で見ることができる。尚、以下の点だけ言及する。
- ルータR12 、R13 、R23 及びR32 は夫々３個のポートのみ含む。（ルータR13 に関しては装置D4、ルータR12 、及びルータR23 に接続されている）
- ルータR11 及びR21 は４個のポートを含む。
- ルータR31 及びR33 は５個のポートを含む。
- ルータR22 は７個のポートを含み、ルータR13 を除いた他のネットワークルータの各々に関連している。
【００２４】
図１の例は非常に単純化され、単に本発明についての説明及び理解を容易にすることを意図されている。
【００２５】
図２はルータRiを示す。ルータ毎に、アリティ（arity）すなわちこのルータに関連した入出口ポートの数が定義される。図２の例では、ルータは６個の入出力ポートP1-P6 を含む。言い換えれば、このルータは６のアリティ（arity）を有する。本発明によれば、入出力ポートの有効なハードウェア配置が何であれ、これらのポートは、事前に、定められた方向に循環して順番に配置されている。図面では、ポートは、ポートP1からポートP6への三角法の回転順序で（反時計回りに）順番に配置されている。従って、任意の２個のポート間のステップ又はシフトの数が定義されることができる。例えば、ポートP5はポートP3から２ステップ又は２循環シフト離れており、ポートP3はポートP5から４ステップ離れている。ポートP6とP1との間のシフトは１に等しく、ポートP1とP6との間のシフトは５に等しい。上記の２例ではシフトの合計が６に等しいことを意味する。実際、第１ポートと第２ポートとの間のシフト、及びこの第２ポートと第１ポートとの間のシフトの合計が、アリティ（arity）と等しいことは明らかである。
【００２６】
図３に示されるように、任意のデータパケットDPはヘッダとデータとを含む。ヘッダは特にルーティング命令を含む。本発明によれば、送信元と宛先との間のルーティング命令は、送られるパスの各ルータの入力ポート及び出力ポート間の連続したシフト値を含む。
【００２７】
図４に示された例では、データパケットを装置D1から装置D5にルータR11 、R22 及びR33 を介して送信することが求められていると仮定する（図１も参照）。図４の上部に、検討されるデータパケットの転送に含まれる一連のルータ及び装置が示されている。各ルータR11 、R22 及びR33 については、有用なポート以外のポートが示されている。従って、図１及び４に示されるように、装置D1から装置D5へデータパケットが送られるために、ルータR11 は２のシフトを提供し、ルータR22 は４のシフトを提供し、またルータR33 は３のシフトを提供する必要がある。この目的のために、要素D1によって送られるヘッダに属し、図４にこの装置D1の下に示されるルーティング命令は、ルータR11 、R22 及びR33 によって連続して運ばれるシフトを含む。これらのシフトは、夫々FR11、FR22、及びFR33として示される（Ｆはフォワード伝搬方向すなわちD1からD5への方向を示すために用いられる）。従って、ルータR11 によって受信されたルーティング命令FR11-FR22-FR33 は、2-4-3 に等しい。
【００２８】
ルータR11 では、最初のシフト命令(FR11=2)が、入力パケットを反時計回りで出会う第２のポート、すなわちルータR22 のポートへ接続されたリンクに連結されたポートから出力させる。ルータR11 はヘッダを以下のように修正することにより、入力パケットを送り返す。
- 最初のシフト命令(FR11)を削除する
- （ルータR11 からルータR22 への）出力ポートと（装置D1に接続された）入力ポートとの間のシフトの数を示すリターン命令RR11を加える
リターン命令RR11はルータR11 のアリティ（arity）(４)に対して命令FR11(２)の補数(２)である。好ましくは示されているように、シフト命令はルータR22 に達する前にFR22、FR33、RR11の順序に配列される。
【００２９】
ルータR22 は、ルータR22 のために意図された命令(FR22=4)を検出し、その命令から入力パケットが入力ポートの後反時計回りに４番目のポートから出る必要があることを導き出す、すなわちデータパケットは、ルータR33 に向けられたポートから出るようにルータR21 、R31 及びR32 に向けられたポートを無視しなければならない。ルータR22 の出力では、最初にFR22-FR33-RR11 であったルーティング命令がルーティング命令FR33-RR11-RR22 と置換される、すなわちフォワードシフト命令FR22はルーティング命令の先頭で削除され、リターンシフト命令RR22がルーティング命令の末尾に加えられる。この方法は、特に復号される命令でのポインタ、及び／又はメッセージがフォワードメッセージかリターンメッセージかどうかによって読む方向を指定するビットの使用を回避することを可能にする。
【００３０】
ルータR33 はシフト命令FR33=3を受け取る。このようにしてデータパケットは装置D5に向けて出て、命令FR33は削除され、命令RR33、すなわち入力命令(３)のアリティ（arity）(５)に対して補数である値２がルーティング命令の末尾に配列される。
【００３１】
従って、装置D5の入力では、データパケットを送り出した装置へのデータパケットの戻りを可能にするシフト命令RR11-RR22-RR33 が連続して見つけられる。例えば、このようなデータは、以下に示すように様々な目的に用いることができる。
- 宛先装置(D5)の段階で、受信データパケットの送信元(D1)を識別すること
- 宛先装置(D5)から送信元装置(D1)へ、送信元の身元を知らずにデータパケットを送り返すこと
送り返されたデータパケットは、例えば受信通知、応答、又はルーティング命令コーディング又は送られたデータのレベルでのエラー検出の場合に実際に届いたデータパケットである。
【００３２】
戻りを行なうために、ルーティング命令RR11-RR22-RR33 は装置D5の段階でRR33-RR22-RR11 の順序に設定され、パケットは、前に説明した方法と同様の方法で装置D5から装置D1に送り返され、各ルータが受けたデータRRを削除して、対応する命令FR、すなわち受けたシフト命令のアリティ（arity）に対する補数に置換する。このようにして、装置D1の段階で、そのヘッダにルーティング命令FR33-FR22-FR11 を含むパケットを見つけることができ、それは戻されてもよく、前に示したように様々な目的（認証、リターン、セキュリティ…）に用いられてもよい。
【００３３】
本発明は、当業者により想起される様々な変更がなされる。特に、データパケットDPのヘッダは、前に示されたシフト値に対応するルーティングデータに加えて他のデータを含んでもよい（図３参照）。これらの他のデータは様々なサービスデータに相当してもよい。更に、必要ではないが、従来通りセキュリティ又は認証能力を更に向上するために、送信元装置、又は通過されたルータの身元に関するデータIDを追加で挿入すべく提供されてもよい。
【００３４】
使用される必要がある様々なルータのシフト命令をルーティング命令に提供することのみ必要とされ、リターンパスのルーティング命令がフォワードパスのルーティング命令に追加されないので、本発明は特に短いヘッダワードを提供することを可能にする。代わりに、リターンシフト命令がルーティング命令内で各フォワードシフト命令と置換される。従ってヘッダワードは、パケットの進行の間及びこのパケットの戻りの際一定の長さを維持する。
【００３５】
図５は、ルーティング命令のサイズを更に減少することを意図した本発明の具体的な実施例を示す。この図面には、装置D1から装置D5へのパケットの転送におけるルーティング命令の改良が、前の例でのようにルータR11 、R22 及びR33 を介して示されている。図１に示された例でのように、異なるルータが異なるアリティ（arities）を有すると仮定する。尚、アリティ（arity）３のルータについては、３のシフトが入力ポートと出力ポートの重ね合せ、すなわちアクションがないことを意味するので、２シフトのみが一般に用いられる。これら「有用な」２シフトはシングルビットを備えた２進数によって表わされてもよい。同様に、アリティ（arity）５のルータは２ビットの２進数によって表わされてもよい有用な４シフトを示し、アリティ（arity）９のルータは３ビットの２進数によって表わされてもよい有用な８ビットを示す。従って、各ルータに関連したシフト命令のビット数はルータのアリティ（arity）によって決まり、用いられたビット数はこの事実を考慮すると最小限にすることができる。前に示された例では、ルータR11 は４のアリティ（arity）を有し、ルータR22 は７のアリティ（arity）を有し、ルータR33 は４のアリティ（arity）を有する。従って、これらのルータのシフトは夫々２ビット、３ビット及び２ビットの２進数によって表わされてもよい。以降、２進数では最小有効ビットはB0と呼ばれ、第１により大きい有効ビットがB1と呼ばれ、次により大きい有効ビットがB2と呼ばれ、以下同様である。従って、２ビット数はB1-B0 と呼ばれ、３ビット数はB2-B1-B0 と呼ばれる。
【００３６】
図４と関連して示されたD1からD5へ送られる命令を再開すると、装置D1によってルータR11 に送られたルーティング命令はシフト命令FR11、FR22、FR33を含み、夫々２ビット、３ビット及び２ビットの２進数である。この実施例では、ルーティング命令の末尾にルータR11 の出力でシフト命令RR11（ルータR11 のアリティ（arity）に対するFR11の補数）を配置する代わりに、最小有効ビットB0が最初に入る反転された命令RR11* がそこに配置される。同様に、ルータR22 の出力では引き続いてシフトFR33、RR11* 及びRR12* になり、次にルータR33 の出力ではシフト命令RR11* 、RR12* 及びRR13* になる。反転した順に入力値のアリティ（arity）に対する補数のビットを配置するという事実は、決してこの補数を計算するための論理回路を複雑にしない。しかしながら、宛先装置D5では、リターンシフトシーケンスRR33-RR22-RR11 を得るために、それを右から左に読む代わりに、左から右に命令ワードRR11*-RR12*-RR13* を読むだけである。言い換えれば、ルーティング命令は、全体として装置D5の出力でD5によって受けられた命令の反転に相当する。これはワイヤ交差により特に単純な方法で行なわれてもよい。
【００３７】
前述した中では、各ルータがそのために意図されるシフト命令を識別する方法は示されていない。しかしながら、各ルータがそれ自身のアリティ（arity）を知っており、そのために意図される命令が所与のビット数の命令であることを知っているので、これは問題ではない。従って、各ルータは、単にルーティング命令の最初の関連するビット、ルータR11 では最初の２ビット、ルータR22 では最初の３ビット及びルータR33 では最初の２ビットを見るだけである。
【００３８】
本発明のこの具体的な実施例は、任意の送られたデータパケット中のルーティング命令のサイズを減少させることにより、目指された目的を更に改善して達成することを可能にする。
【００３９】
本発明は、現在好まれている具体的な実施例との関連で述べてきた。一般に本発明は、ルータ毎に入出力ポートが互いに相対的に定義されているルーティングネットワークでの特に簡易なルーティング方法を目的とし、必ずしも詳細に上述された循環シフト方法によるものではない。例えば、各ポートはシーケンス番号によって他のポートに対して特定されてもよい。このようにして各ポートは別のポートに対してフォワード識別子及びリターン識別子を有する。
【００４０】
フォワード識別子及びリターン識別子の可能な選択には、暗号化された組合せが選択されてもよく、不正行為の試みに更に抵抗することを可能にすることが理解される。本発明は実際、リターンルーティング命令がその身元を明かすので送信器を識別することを可能にする。このタイプの識別は、証明書の送信によって認証する現在の技術に取って代わってもよいし完成してもよい。
【００４１】
本発明は、命令が、通過されたすべてのルータをアドレス指定せず、単にこれらの一部のみアドレス指定するデフォルトルーティングによるフォワードに用いられてもよい。
【図面の簡単な説明】
【００４２】
【図１】システムの様々な装置間のルーティングネットワークを概略的に示す図である。
【図２】本発明に係るルータのポートを位置付けるための仕様を示す図である。
【図３】従来のデータパケットの概要を示す図である。
【図４】ルーティングネットワークによるデータパケットのルーティングと、送信元装置から宛先装置への転送及び送信元装置に向けた戻りで各ルータ及び装置を介して通過する前後でのデータパケットのヘッダの変動との例を示す図である。
【図５】本発明の具体的な実施例に係るデータパケットのヘッダにルーティング命令を記憶するためのモードを示す図である。
【図１】
2009514293.tif 000003
【図２】
2009514293.tif 000004
【図３】
2009514293.tif 000005
【図４】
2009514293.tif 000006
【図５】
2009514293.tif 000007
【国際調査報告】
2009514293.tif 000008
2009514293.tif 000009
2009514293.tif 000010
2009514293.tif 000011