JP2006511115A - パケット交換方式ネットワークにおけるリターンパス導出 - Google Patents

Abstract

データを転送するネットワークは、一体的に連結されたスイッチ、ルータまたはコンピュータシステムのような２つ以上のノードのグループにより構成される。データは、送信元ノードからネットワークを介して宛先ノードへ転送される。パケット交換方式ネットワークにおいて、パケットと称される小単位のデータは、ネットワークを介して送信元ノードから宛先ノードへ送られる。これらのパケットはネットワークをプログラムするためにも使用される。一部のケースでは、パケットは送信元ノードへのリターンパスを進むことが要求される。本発明において、リターンパスはネットワークのノードに記憶された情報から得られる。

Description

本発明は、複数のノードとノード間の複数のリンクとを有し、第１のノードが第２のノードとの間に少なくとも１本のリンクを有し、第１のノードそれぞれに対して第２のノードと第１のノートとの間にリンクが存在するネットワークにおいて、送信元ノードから宛先ノードへ少なくとも１台の中間ノードを介してパケットを送信するときに使用されるパケットのリターンパスを決定する方法に関する。

本発明はさらに、複数のノードとノード間の複数本のリンクとを有し、第１のノードが第２のノードとの間に少なくとも１本のリンクを有し、第１のノードそれぞれに対して第２のノードと第１のノートとの間にリンクが存在し、送信元ノードから宛先ノードへ少なくとも１台の中間ノードを介してパケットを送信するときにパケットのリターンパスを決定するように構成されたネットワークを具備する集積回路に関する。

一般に、データを転送するネットワークは、一体的に連結された、ノードと呼ばれる２台以上の装置のグループを具備する。ネットワーク内のノードは、スイッチ、ルータ、またはコンピュータシステムを含む。これらのコンピュータシステムは、また、コンピュータシステムを機能させるために必要である周辺装置を有する。ネットワーク内の２個の隣接ノード間の通信路はリンクと呼ばれる。リンクは単一伝送チャネルを用いて実施される。或いは、２個のノード間の２つのリンクが単一伝送チャネルに結合される。異なるネットワークでは、２個の隣接ノードは、通信の帯域幅を増加させるため、これらの２個のノード間の通信のための３つ以上のリンクを有する。これらのリンクすべてが同様に単一伝送チャネルで実施される。データはネットワークを介して送信元ノードから宛先ノードへ転送される。ネットワークは、例えば、集積回路上に集められた数個の素子間の通信のため、または、数台のコンピュータシステム間の通信のため使用される。データはメッセージまたはパケットとしてネットワークを介して転送される。メッセージはユーザ定義データ単位であり、一方、パケットはネットワーク定義データユニットである。いわゆるメッセージ−スイッチネットワークにおいて、メッセージはネットワークを介してそれらの宛先へ送られ、一方、パケット交換方式ネットワークでは、パケットはネットワークを介してそれらの宛先へ送られる。パケット交換方式ネットワークの場合に、所定の宛先へ送信されるべきメッセージは複数個のパケットに分割され、パケットが宛先へ送信される。宛先で、メッセージ内のパケットは集められ、元のメッセージに再組み立てされる。パケット交換方式ネットワークの利点は、送信元と宛先の間の通信をかなり小さいデータ単位に分解することにより、より細かい精度でネットワーク内の多数のユーザ間で同じデータパスの共有を可能にすることである。本明細書の残りの部分で、文言「パケット」および「パケット交換方式」は効率性の理由のため使用されるが、これらの語は「メッセージ」および「メッセージ交換方式」として読むことも可能である。

パケット交換方式ネットワークでは、データの送信に加えて、パケットはまたネットワークをプログラムするために、例えば、リソースを予約もしくは解放するために、または、コネクションを確立もしくは削除するために使用される。リソースの一例は、ルータ内のバッファ容量、または、コネクションの帯域幅である。コネクションを確立する一例は、１個以上のパケットがそのコネクションを介して送信元ノードから宛先ノードへ送信できるように、ネットワーク内の一連のルータを設定することである。多数のユーザの間でネットワークを共有するとき、アービトレーションスキームは、単一伝送チャネル上のパケットの送信を組み合わせる。例えば、各ストリームにセット内の異なるタイムスロットを割り当てることによりデータストリームを組み合わせる時分割多重（ＴＤＭ）方式が使用される。ＴＤＭ方式は単一伝送チャネルによるタイムスロットの固定シーケンスでデータを繰り返し送信する。

一部のケースでは、リソースの予約またはコネクションの確立は、例えば、そのパケットが送られるパス上の１個のノードでこのアクションが実行できないために失敗する。一例は、パスに沿ったノードにおけるバッファ容量のようなリソースの不足による失敗である。その結果として、希望のコネクションを確立できない。次に、パスの、そのポイントまでに行われたコネクションの確立のみならずリソースの予約は、解放されていなければならない。したがって、パケットが既に通過したパスのノードを再通過すること、すなわち、パケットが送信元ノードへのリターンパスを進むことは不可欠である。

米国特許出願公開第２００２／００３１０９５号明細書は、ネットワークを介してパケットを送信するときにリターンパスの内容を設定するための方法を開示する。ネットワークは、任意のネットワークトポロジー内の物理的なポイントツーポイントコネクションにおける少なくとも２台の双方向コネクションインタフェースを用いて柔軟にネットワーク化されたモジュールを具備する。モジュールがパケットを別のモジュールへ転送するとき、そのモジュールの受信用インタフェースの番号がパケットに格納される。このようにして、リターンパスは、パケットに格納され、パケットが既に通過したモジュールに対応する受信用インタフェースのリストから取得される。

従来技術のプロセッサの欠点は、リターンパス上の情報がパケットに格納され、これが、特に、ネットワークを通るパスの完全な記述の代わりに宛先アドレスだけを収容するパケットの場合に、パケットのサイズを増大させることである。

本発明の目的は、パケットのサイズを縮小することを可能にする、改良されたネットワークにおいてパケットのリターンパスを決定する方法を提供することである。

上記目的は、リターンパスを得るため中間ノードに情報を記憶するステップを含むことを特徴とする上記のネットワークにおいてパケットのリターンパスを決定する方法によって達成される。リターンパスに関する情報は、パケットが宛先ノードまでのパス上で通過したノードに記憶される。例えば、特定のノード内のリソースを予約できないという理由のため失敗が起こる場合、パケットはその宛先ノードまでのパス上で通過した１個以上のノードに保存された情報からそのリターンパスを得ることができる。リターンパスに関する情報を記憶するためにパケット内に付加的な空間は不要であり、これはパケットのサイズを縮小させる。

本発明の有利な実施形態は、この方法が、送信元ノードから宛先ノードへパケットを送信するときに、パケットが通過した制限された個数のノードだけに、または、１個のノードだけに集中的に情報を記憶するのではなく、パケットが通過した各ノードにリターンパスを得るための情報を記憶するステップをさらに含むことを特徴とする。リターンパスに関する情報はノードに分散して保存され、リターンパスを進むときに、パケットは、各ノードからリターンパスに関する情報を取得しながら、一方のノードから別のノードへ移動することができる。パケットが通過したすべてのノードにリターンパスに関する情報を記憶することにより、リターンパスを決定するオーバーヘッドは各個別のノードに関して削減することができる。

本発明の一実施形態は、中間ノードに記憶された情報が、パケットの識別子と、パケットを戻すため使用されるべき中間ノードの出力ポートを符号化する情報と、を含むことを特徴とする。利点は、この情報がノードにおいて容易に得られ、各パケットのリターンパスを一意に識別できることである。

本発明によれば、冒頭の段落に記載されたような集積回路は、中間ノードがリターンパスを得るための情報を記憶するため構成されることを特徴とする。その結果として、オンチップ通信ネットワークにおいて使用されるパケットのサイズを縮小し、通信オーバーヘッドを削減することが可能である。

本発明による集積回路の好適な実施形態は従属請求項に規定されている。

図１は、宛先ルーティングを使用して、すなわち、最終的な宛先に関する情報だけをパケットに記憶させて、送信元ノードから宛先ノードへパケットを送信するときに、本発明によるネットワークにおいてパケットのリターンパスを決定する方法を使用するネットワークの一実施形態を示す。１０１を参照すると、ノードＳ、Ｒ１、Ｒ２、Ｒ３およびＤを含むネットワークが表され、これらのノードは、それらの入力ポートおよび出力ポートＳ＿１、Ｓ＿２、Ｒ１＿１、Ｒ１＿２、Ｒ１＿３、Ｒ１＿４、Ｒ２＿１、Ｒ２＿２、Ｒ２＿３、Ｒ２＿４、Ｒ３＿１、Ｒ３＿２、Ｒ３＿３、Ｒ３＿４、Ｄ＿１およびＤ＿２を介して、リンク１０７、１０９、１１１、１１３、１１５、１１７、１１９および１２１を用いて結合される。ネットワーク１０１は、集積回路のネットワークまたはネットワークの一部分でもよい。ノードＳ、Ｒ１、Ｒ２、Ｒ３およびＤは、データユニットを次の宛先へ送信するルータまたはスイッチを含む。ノードＳ、Ｒ１、Ｒ２、Ｒ３およびＤはまた、図１に示されていない他のノードへの結合のための、より多くの入力ポートおよび出力ポートを具備してもよい。すべてのノードＳ、Ｒ１、Ｒ２、Ｒ３およびＤに関して、第１のノードが第２のノードとの間に少なくとも１本のリンクを有するならば、第２のノードと第１のノードとの間にもリンクが存在する。ノードＳ、Ｒ１、Ｒ２、Ｒ３およびＤは、それぞれ、特定のノードから来る入力ポートでパケットを受信し、そのパケットを出力ポート経由で送信するとき、パケットがその特定のノードへ送信されるように、そのノードの各入力ポートをそのノードの出力ポートに関係付けるリターン関係を記憶する。ノードＲ１、Ｒ２およびＲ３はそれぞれメモリＭ１、Ｍ２およびＭ３を具備する。ノードＤおよびＳは同様にメモリを具備するが、図１には示されていない。パケット１２３は送信元ノードＳから宛先ノードＤへ送信される。パケット１２３は、ネットワークをプログラムするように、例えば、いくつかの例を挙げると、コネクションを確立もしくは削除するために、または、リソースを予約もしくは解放するために構成される。コネクションを確立する一例は、パケットを希望の方向へ送信するため、あるノードの入力ポートをそのノードの出力ポートに連結することである。リソースの例は、ルータ内のバッファ容量、または、コネクションの帯域幅である。ネットワークのプログラミングが各ノードで成功したとき、パケットは宛先ノードＤへ送られる。しかし、ネットワークのプログラミングはある特定のノードで、例えば、バッファ容量のようなネットワークリソースの不足を原因として、失敗する場合がある。そのケースでは、パケットは、送信元ノードＳへのリターンパスを進み、例えば、予約されたリソースを解放することによって、その特定のノードから前方へ送信元ノードＳまでネットワークを再プログラムすることが不可欠である。この実施形態では、ネットワークのプログラミングが宛先ノードＤまで成功したことを仮定している。パケット１２３は、ネットワークをプログラミングするため使用される識別子ＩＤと、宛先アドレスＤＥＳＴと、データＤＡＴとを含む。各ノードＳ、Ｒ１、Ｒ２、Ｒ３およびＤは、パケットを希望の宛先へ送信するため使用する出力ポートを見分けるためにすべての宛先をそのノードの出力ポートに関係付ける宛先関係を記憶している。この情報を使用することにより、ノードは、そのノードによって受信されたパケットの宛先アドレスＤＥＳＴが与えられるならば、パケットを隣接ノードうちの一つへ送信するために使用すべき出力ポートを決定することが可能である。宛先関係とリターン関係の両方は、図１には示されていないが、例えば、ノードＳ、Ｒ１、Ｒ２、Ｒ３およびＤに存在するプログラマブルメモリにプログラムされる。宛先アドレスＤＥＳＴは宛先ノードＤのアドレスに一致する。１０３を参照すると、パケットを送信元ノードＳから宛先ノードＤへ送信するときに、そのパケット１２３が辿るパスが示されている。１０５を参照すると、パケット１２３を送信元ノードＳから宛先ノードＤへ送信するときのメモリＭ１、Ｍ２およびＭ３の内容が示されている。最初のステップ１において、パケット１２３は送信元ノードＳによって、出力ポートＳ＿１、リンク１０７および入力ポートＲ１＿１を介して、ノードＲ１へ送信される。ノードＲ１はパケット１２３から識別子ＩＤを読み、それを入力ポートＲ１＿１からの識別子Ｒ１＿１と組み合わせて、（ＩＤ，Ｒ１＿１）のペアとしてメモリＭ１に格納する。パケット１２３に格納された宛先アドレスＤＥＳＴおよびその宛先関係を使用して、ノードＲ１は、そのパケット１２３を転送するために使用すべき出力ポート、ここでは、出力ポートＲ１＿３を決定する。次のステップ２において、パケット１２３は、出力ポートＲ１＿３、リンク１１１および入力ポートＲ２＿１を介して、ノードＲ２へ送信される。ノードＲ２はパケット１２３から識別子ＩＤを読み、それを入力ポートＲ２＿１からの識別子Ｒ２＿１と組み合わせて、（ＩＤ，Ｒ２＿１）のペアとしてメモリＭ２に格納する。パケット１２３に格納された宛先アドレスＤＥＳＴおよびその宛先関係を使用して、ノードＲ２は、そのパケット１２３を転送するために使用すべき出力ポート、ここでは、出力ポートＲ２＿３を決定する。次のステップ３において、パケット１２３は、出力ポートＲ２＿３、リンク１１５および入力ポートＲ３＿１を介して、ノードＲ３へ送信される。ノードＲ３はパケット１２３から識別子ＩＤを読み、それを入力ポートＲ３＿１からの識別子Ｒ３＿１と組み合わせて、（ＩＤ，Ｒ３＿１）のペアとしてメモリＭ３に格納する。パケット１２３に格納された宛先アドレスＤＥＳＴおよびその宛先関係を使用して、ノードＲ３は、そのパケット１２３を転送するために使用すべき出力ポート、ここでは、出力ポートＲ３＿３を決定する。次のステップ４において、パケット１２３は、出力ポートＲ３＿３、リンク１１９および入力ポートＤ＿１を介して、ノードＤへ送信される。宛先ノードＤはパケット１２３に格納された宛先アドレスＤＥＳＴを読み、自分のアドレスと比較したときに、自ノードが宛先ノードであることを決定する。ネットワークのプログラミングがノードＤにおいて失敗したケースでは、パケット１２３は、ネットワークの再プログラミングのため、分散して保存されたリターンパスを使用して、宛先ノードＤから送信元ノードＳへ戻される。宛先ノードＤは、パケットを受信するときに用いられた入力ポートＤ＿１の識別子Ｄ１と、宛先ノードＤに記憶されたリターン関係との組み合わせから、パケット１２３を送信するため出力ポートＤ＿２を使用することを決定する。次のステップ５において、パケット１２３は、出力ポートＤ＿２、リンク１２１および入力ポートＲ３＿４を介して、ノードＲ３へ送信される。ノードＲ３はパケット１２３から識別子ＩＤを読み、この識別子が（ＩＤ，Ｒ３＿１）のペアとしてメモリＭ３に記憶されていることを検証する。ノードＲ３は、入力ポートＲ３＿１の識別子Ｒ３＿１と、ノードＲ３に記憶されたリターン関係との組み合わせから、パケットを送信するため出力ポートＲ３＿２を使用することを決定する。次に、識別子ＩＤと識別子Ｒ３＿１のペアの形でメモリＭ３に記憶されていたリターンパスに関する情報が削除される。次のステップ６において、パケット１２３は、出力ポートＲ３＿２、リンク１１７および入力ポートＲ２＿４を介して、ノードＲ２へ送信される。ノードＲ２はパケット１２３から識別子ＩＤを読み、この識別子が（ＩＤ，Ｒ２＿１）のペアとしてメモリＭ２に記憶されていることを検出する。ノードＲ２は、入力ポートＲ２＿１の識別子Ｒ２＿１と、ノードＲ２に記憶されたリターン関係との組み合わせから、パケットを送信するため出力ポートＲ２＿２を使用することを決定する。次に、識別子ＩＤと識別子Ｒ２＿１のペアの形でメモリＭ２に記憶されていたリターンパスに関する情報が削除される。次のステップ７において、パケット１２３は、出力ポートＲ２＿２、リンク１１３および入力ポートＲ１＿４を介して、ノードＲ１へ送信される。ノードＲ１はパケット１２３から識別子ＩＤを読み、この識別子が（ＩＤ，Ｒ１＿１）のペアとしてメモリＭ１に記憶されていることを検出する。ノードＲ１は、入力ポートＲ１＿１の識別子Ｒ１＿１と、ノードＲ１に記憶されたリターン関係との組み合わせから、パケットを送信するため出力ポートＲ１＿２を使用することを決定する。次に、識別子ＩＤと識別子Ｒ１＿１のペアの形でメモリＭ１に記憶されていたリターンパスに関する情報が削除される。次のステップ８において、パケット１２３は、出力ポートＲ１＿２、リンク１１３および入力ポートＳ＿２を介して、送信元ノードＳへ送信される。送信元ノードＳはパケット１２３から識別子ＩＤを読み、識別子ＩＤが、図１に示されていない内部メモリに記憶されていないことを検出した後、自ノードがパケット１２３の最終的な送信元であることを判定する。本実施形態において、メモリＭ１、Ｍ２およびＭ３は、「パケットの識別子と入力ポートの識別子」のペアの記憶を効率的に実施するため、ハッシュテーブル、または、内容のアドレス指定が可能であるメモリを含む。メモリＭ１、Ｍ２およびＭ３はまた、図１に示されていないが、パケット１２３以外の他のパケットリターンパスに関する情報を含む。

リターンパスに関する情報は、パケット１２３が送信元ノードＤから宛先ノードＳへ送られているときに、通過したノードから得られる。情報はノードに分散的に保存され、リターンパスを進むときに、パケットはあるノードから別のノードへ移動し、各ノードからリターンパスに関する情報を得ることができる。その結果として、リターンパスに関する情報を記憶するためにパケット内に余分な空間が要求されず、パケットのサイズの縮小を可能にさせる。

他の実施形態では、「パケットの識別子と出力ポートの識別子」のペアが、パケット１２３のリターンパスを決定するためメモリＭ１、Ｍ２およびＭ３に記憶される。出力ポートの識別子は、あるノードがパケットを受信したときに用いられた入力ポートの識別子と、そのノードに記憶されたリターン関係とから決定される。例えば、ステップ１の後、ノードＲ１は、パケット１２３から識別子ＩＤを読み、識別子Ｒ１＿２と共に、（ＩＤ，Ｒ１＿２）のペアとしてメモリＭ１に記憶する。識別子Ｒ１＿２は、入力ポートＲ１＿１の識別子Ｒ１＿１とノードＲ１に記憶されたリターン関係との組み合わせから決定される。ステップ７において、パケット１２３をノードＲ１へ送信した後、ノードＲ１はパケット１２３から識別子ＩＤを読み、この識別子が（ＩＤ，Ｒ１＿２）のペアとしてメモリＭ１に記憶されていることを検証する。出力ポートＲ１＿２の識別子Ｒ１＿２を使用して、ノードＲ１は、出力ポートＲ１＿２、リンク１０９および入力ポートＳ＿２を介意して、パケット１２３を送信元ノードＳへ送信する。ノードＲ１、Ｒ２およびＲ３の入力ポートの個数が出力ポートの個数よりも多い場合、リターンパスの決定のため入力ポートの識別子の代わりに出力ポートの識別子をメモリＭ１、Ｍ２およびＭ３に記憶することにより必要な記憶空間が小さくなる。

他の実施形態では、ネットワークのプログラミングは、宛先ノードに到達する前に、あるノードで失敗することがある。図１を参照すると、ネットワークのプログラミングがノードＲ３において失敗したとき、このノードはパケット１２３を送信元ノードＳへ送られる。上記のように、ネットワークを再プログラムするためにパケットがリターンパスを移動することは不可欠である。本実施形態において、ネットワークの再プログラミングは、パスのそのポイントまでになされた予約を取り消すことを伴う。別の実施形態では、ネットワークの再プログラミングは、リターンパスを移動する間に、宛先ノードへの代替パスを見つけることを含む。ノードＲ３は、パケットを受信するため使用された入力ポートＲ３＿１の識別子Ｒ３＿１と、ノードＲ３に記憶されているリターン関係との組み合わせから、パケットを送信するため出力ポートＲ３＿２を使用することを決定する。次のステップ６において、パケットは、出力ポートＲ３＿２、リンク１１７および入力ポートＲ２＿４を介してノードＲ２へ送信される。次に、パケット１２３は前述の実施形態において説明したように、送信元ノードＳへ送られる。

様々な実施形態では、ネットワークの再プログラミングは、例えば、ある特定のリソースへのアクセスがそのリソースが既に使用されているので拒絶されるため、ある種のノードで失敗することがある。図１を参照すると、パケットは宛先ノードＤへ送られるが、ノードＲ３のプログラミングは失敗し、次に、パケットは、前述の実施形態において説明したように、ノードＲ１およびＲ２に記憶されたリターンパスに関する情報を使用して送信元ノードＳへ送られる。ネットワークの再プログラミングがノードＲ２で失敗するのは、このノードのリソースへのアクセスが拒絶されるからである。ノードＲ２は、パケット１２３に格納された宛先アドレスＤＥＳＴを読み、この宛先アドレスおよび宛先関係を使用して、ノードＲ２はパケットを宛先ノードＤへ送るために出力ポートＲ２＿４を使用することに決定する。（ＩＤ，Ｒ２＿１）のペアの形でメモリＭ２に記憶されたリターンパスに関する情報は、そのままメモリＭ２に存在している。次のステップ３において、パケットは、出力ポートＲ２＿３、リンク１１５および入力ポートＲ３＿１を介して、ノードＲ３へ送信される。ノードＲ３において、ネットワークを再プログラミングすることが新たに試みられる。この試みが成功した場合、パケット１２３は、前述の実施形態において説明したように、宛先ノードＤへ送信される。この試みが失敗した場合、パケットは、前述の実施形態において説明したように、送信元ノードＳへ送られる。

他の実施形態では、パケットの固有識別子を得る別の方法が使用される。例えば、時分割多重方式アービトレーションスキームを使用するとき、スロットテーブルがルータのため使用され、所与のタイムスロットにおいて、そのルータのどの出力ポートがそのルータのどの固有入力ポートに接続されるかが決められる。その結果として、タイムスロットは、パケットを一意に識別し、以下の通りにリターンパスを決定するため使用される。送信元ノードから宛先ノードへ進むときに、パケットがノードによって送信する期間のタイムスロットがパケットに格納され、２台の隣接ノード間を移動するために１スロットが必要であるため、タイムスロットの値がノードごとに１ずつ増加させられる。パケットがリターンパスを進まなければならない場合、パケットは、あるノード、例えば、入力ポートＲ２＿４を介して、ノードＲ２へ送信される。入力ポートＲ２＿４のリターン関係が一意であると仮定するならば、出力ポートＲ２＿３はリターン関係を入力ポートＲ２＿４に適用することによって一意に識別される。次に、出力ポートＲ２＿３と組み合わせてパケットに格納されたタイムスロットを使用して、送信元ノードから宛先ノードへ進むときにパケットを受信するため使用された入力ポートの識別子、すなわち、Ｒ２＿１がルータテーブルから得られる。次に、リターン関係と入力ポートＲ２＿１の識別子とを使用して、出力ポートＲ２＿２の識別子が決定され、この出力ポートが送信元ノードの方向にパケットを送信するため、すなわち、リターンパスを進むため使用される。パケットを送信する前に、パケットに格納されたタイムスロットの値が１ずつ減少させられる。

図２は、送信元ルーティングを使用して、すなわち、パケットがそのパケットのルーティングに関する情報を含む場合に、送信元ノードから宛先ノードへパケットを送信するときに、本発明によるネットワークにおいてパケットのリターンパスを決定する方法を使用するネットワークの一実施形態を示す。ルーティングに関する情報は、後続のノードの出力ポートの系列の形でパケットに格納されるので、各ノードは、パケットを次のノードへ送信するため使用すべき出力ポートをそのパケットから検出する。パケットが宛先ノードへ送られている間に、リターンパスに関する情報はノードに記憶される。２０１を参照すると、ノードＳ１、Ｒ４、Ｒ５およびＤ１を含むネットワークが示され、これらのノードは、それらの入力ポートおよび出力ポートＳ１＿１、Ｓ１＿２、Ｒ４＿１、Ｒ４＿２、Ｒ４＿３、Ｒ４＿４、Ｒ５＿１、Ｒ５＿２、Ｒ５＿３、Ｒ５＿４、Ｄ１＿１およびＤ＿１２を介して、リンク２０７、２０９、２１１、２１３、２１５および２１７を用いて接続される。ネットワーク２０１は、集積回路のネットワークまたはネットワークの一部分でもよい。ノードＳ１、Ｒ４、Ｒ５およびＤ１は、データユニットを次の宛先へ送信するルータまたはスイッチを含む。ノードＳ１、Ｒ４、Ｒ５およびＤ１はまた、図２に示されていない他のノードへの結合のためのより多くの入力ポートおよび出力ポートを具備してもよい。パケット２１９は送信元ノードＳ１から宛先ノードＤ１へ送信される。ノードＲ４およびＲ５はそれぞれメモリＭ４、およびＭ５を具備する。ノードＳ１およびＤ１は同様にメモリを具備するが、図２には示されていない。すべてのノードＳ１、Ｒ４、Ｒ５およびＤ１に関して、第１のノードが第２のノードとの間に少なくとも１本のリンクを有するならば、第２のノードと第１のノードとの間にもリンクが存在する。ノードＳ１、Ｒ４、Ｒ５およびＤ１は、それぞれ、特定のノードから来る入力ポートでパケットを受信し、そのパケットを出力ポート経由で送信するとき、パケットがその特定のノードへ送信されるように、そのノードの各入力ポートをそのノードの出力ポートに関係付けるリターン関係を記憶する。パケット２１９は、ネットワークをプログラムするように構成される。ネットワークのプログラミングが各ノードで成功したとき、パケットは宛先ノードＤへ送られる。しかし、ネットワークのプログラミングはある特定のノードで、例えば、リソースの不足を原因として、失敗する場合がある。そのケースでは、パケットは、それまでに通過したネットワークの部分を再プログラムするため、送信元ノードへのリターンパスを進むことが不可欠である。この実施形態では、ネットワークのプログラミングが宛先ノードＤ１まで成功したことを仮定している。２０３を参照すると、パケット２１９を送信元ノードＳ１から宛先ノードＤ１へ送信するときにパケット２１９が辿るパスが示されている。２０５を参照すると、パケットを送信元ノードＳ１から宛先ノードＤ１へ送信するときのメモリＭ４およびＭ５の内容が示されている。パケット２１９は、識別子ＩＤと、ポインタＰと、出力ポート識別子Ａ１およびＡ２と、カウンタＣと、データＤＡＴとを含む。ポインタＰは、パケットを送信するため使用されるべき出力ポートの出力ポート識別子が格納されているパケット２１９内の場所を指定する。出力ポート識別子Ａ１およびＡ２は、パケットを送信するため経由させられるべき出力ポートを一意に識別する。カウンタＣは宛先ノードＤへ到達する前に通過されるべきノードの総数を決める。他の実施形態では、当業者によって知られているように、送信元ルーティングのための別の符号化方式が考えられる。送信元ノードＳ１から宛先ノードＤ１へパケット２１９を送信する前に、パケット２１９内の出力ポート識別子Ａ１の場所を指定するようにポインタＰが定義される。出力ポート識別子Ａ１は出力ポートＲ４＿３の出力ポート識別子Ｒ４＿３と一致するように設定され、出力ポート識別子Ａ２には出力ポートＲ５＿３の出力ポート識別子Ｒ５＿３が設定される。カウンタＣには２が設定される。最初のステップ１において、パケット２１９は送信元ノードＳ１によって、出力ポートＳ１＿１、リンク２０７および入力ポートＲ４＿１を介して、ノードＲ４へ送信される。パケット２１９を送信するために適切な出力ポートを選択するため、送信元ノードＳ１は、それが接続されているネットワークに関する情報を、例えば、ノードＳ１に記憶された宛先関係の形で、保有することが必要である。ノードＲ４はカウンタＣの値を読み、カウンタＣの値がゼロに一致しないので、宛先ノードではないことを検出する。カウンタＣの値は１ずつ減少させられる。ノードＲ４はパケット２１９から識別子ＩＤを読み、それを入力ポートＲ４＿１からの識別子Ｒ４＿１と組み合わせて、（ＩＤ，Ｒ４＿１）のペアとしてメモリＭ４に格納する。ノードＲ４は、ポインタＰの値を読み、出力ポート識別子Ａ１を読むためその値を使用することにより、パケット２１９を送信するため出力ポートＲ４＿３を使用することに決定する。ノードＲ４は、出力ポート識別子Ａ２が格納されているパケット２１９内の場所を指定するようにポインタＰを更新する。次のステップ２において、パケット２１９は、出力ポートＲ４＿３、リンク２１１および入力ポートＲ５＿１を介して、ノードＲ５へ送信される。ノードＲ５はカウンタＣの値を読み、カウンタＣの値がゼロに一致しないので、宛先ノードではないことを検出する。カウンタＣの値は１ずつ減少させられる。ノードＲ５はパケット２１９から識別子ＩＤを読み、それを入力ポートＲ５＿１からの識別子Ｒ５＿１と組み合わせて、（ＩＤ，Ｒ５＿１）のペアとしてメモリＭ５に格納する。ノードＲ５は、ポインタＰの値を読み、出力ポート識別子Ａ２を読むためその値を使用することにより、パケット２１９を送信するため出力ポートＲ５＿３を使用することに決定する。ノードＲ５は、カウンタＣの値がゼロに一致するので、ポインタＰの更新が不要であることを決定する。次のステップ３において、パケット２１９は、出力ポートＲ５＿３、リンク２１３および入力ポートＤ１＿１を介して、ノードＤ１へ送信される。ノードＤ１はカウンタＣの値を読み、カウンタＣの値がゼロに一致するので、自ノードが宛先ノードであることを判定する。したがって、Ｃの値は更新する必要が無く、ポインタＰの値は読まれない。ネットワークのプログラミングがノードＤ１において失敗したケースでは、パケット２１９は、ネットワークの再プログラミングのため分散して保存されたリターンパスを使用して、宛先ノードＤ１から送信元ノードＳ１へ送られる。ノードＤ１は、パケット２１９を受信する際に使用された入力ポートＤ１＿１の識別子Ｄ１＿１と、ノードＤ１に記憶されているリターン関係とを使用して、送信元ノードＳ１へパケット２１９を返信するため出力ポートＤ１＿２を使用することを決定する。次のステップ４において、パケットは、出力ポートＤ１＿２、リンク２１７および入力ポートＲ５＿４を介して、ノードＲ５へ送信される。ノードＲ５はパケット２１９から識別子ＩＤを読み、この識別子が（ＩＤ，Ｒ５＿１）のペアとしてメモリＭ５に記憶されていることを検出する。ノードＲ５は、入力ポートＲ５＿１の識別子Ｒ５＿１と、ノードＲ５に記憶されたリターン関係との組み合わせから、パケット２１９を送信するため出力ポートＲ５＿２を使用することを決定する。ノードＲ５は、カウンタＣの値がゼロに一致するので、ポインタＰの更新が不要であることを決定する。次に、ノードＲ５はカウンタＣを１ずつ増加させる。識別子ＩＤと識別子Ｒ５＿１のペアの形でメモリＭ５に記憶されていたリターンパスに関する情報が削除される。次のステップ５において、パケットは、出力ポートＲ５＿２、リンク２１１および入力ポートＲ４＿４を介して、ノードＲ４へ送信される。ノードＲ４はパケット２１９から識別子ＩＤを読み、この識別子が（ＩＤ，Ｒ４＿１）のペアとしてメモリＭ４に記憶されていることを検出する。ノードＲ４は、入力ポートＲ４＿１の識別子Ｒ４＿１と、ノードＲ４に記憶されたリターン関係との組み合わせから、パケット２１９を送信するため出力ポートＲ４＿２を使用することを決定する。ノードＲ４は、出力ポート識別子Ａ１が記憶されている場所を指定するようにポインタＰを更新し、カウンタ１を１ずつ増大させる。識別子ＩＤと識別子Ｒ４＿１のペアの形でメモリＭ４に記憶されていたリターンパスに関する情報が削除される。次のステップ６において、パケット１２３は、出力ポートＲ４＿２、リンク２０９および入力ポートＳ１＿２を介して、ノードＳ１へ送信される。送信元ノードＳ１は、パケット２１９から識別子ＩＤを読み、この識別子が、図２に示されていないその内部メモリに記憶されていないことを検出し、自ノードが宛先ノードであることを判定する。

図２を参照すると、別の実施形態では、ネットワークのプログラミングは、宛先ノードＤ１に到達する前にあるノードで失敗することがある。図２を参照すると、ネットワークのプログラミングがノードＲ５において失敗する場合に、このノードはパケット２１９を送信元ノードＳ１へ送る。上記のように、ネットワークを再プログラムするためにパケット２１９が送信元ノードＳ１へのリターンパスを移動することは不可欠である。ノードＲ５は、入力ポートＲ５＿１の入力ポート識別子Ｒ５＿１と、ノードＲ５に記憶されたリターン関係との組み合わせを使用して、パケット２１９を送信元ノードＳ１へ送るため出力ポートＲ５＿２を使用することを決定する。ノードＲ５は、カウンタＣの値がゼロに一致するので、ポインタＰ５の値は更新する必要がないことを決定する。ノードＲ５はカウンタＣを１ずつ増加させる。次のステップ５において、パケットは、出力ポートＲ５＿１、リンク２１１および入力ポートＲ４＿３を介してノードＲ４へ送信される。次に、パケット２１９は前述の実施形態において説明したように、送信元ノードＳ１へさらに送られる。

図２を参照すると、他の実施形態では、ネットワークの再プログラミングは、例えば、ある特定のリソースへのアクセスが特定のノードにおいて拒絶されるため、失敗することがある。パケット２１９は宛先ノードＤ１へ送られるが、ネットワークのプログラミングがノードＲ５において失敗し、次に、パケット２１９は、前述の実施形態において説明したように、ノードに記憶されたリターン情報を使用して送信元ノードＳへ送られる。パケット２１９はノードＲ４へ送信される。ノードＲ４は、出力ポート識別子Ａ１が記憶されているパケット２１９内の場所を指定するようにポインタＰを更新し、カウンタＣの値が１ずつ増加させられる。次に、ネットワークの再プログラミングがノードＲ４において失敗し、このノードはパケットを宛先ノードＤ１へ送る。ノードＲ４は、ポインタＰの値を読み、出力ポート識別子Ａ１を読むためにこの値を使用することによって、パケット２１９を送信するため出力ポートＲ４＿３を使用することに決定する。ノードＲ４は、出力ポート識別子Ａ２が記憶されている場所を指定するようにポインタＰを更新し、カウンタＣの値が１ずつ減少させられる。次のステップ２において、パケット２１９は、前述の実施形態において説明したように、出力ポートＲ４＿３、リンク２１１および入力ポートＲ５＿１を介して、ノードＲ５へ送信される。送信元ノードＳ１から宛先ノードＤ１へのパケットのルーティングのためパケット２１９に格納された情報はパケット２１９内にそのまま残り、リターンパスに関する情報はノードＲ４およびＲ５に記憶される。その結果として、パケット２１９は、本実施形態において説明したように、同じパスを介して、宛先ノードＤ１へ２回以上送られ、ネットワークをプログラムすることが毎回試される。

再度図１を参照すると、様々な実施形態において、リターンパスに関する情報は、送信元ノードＳから宛先ノードＤまでのパス上でパケット１２３が通過したすべてのノードに格納される。リターンパスの一部分が一意であり、パケットが送信元ノードＳから宛先ノードＤまで通過するパスに一致する場合、リターン情報はリターンパスのその部分に関連付けられたノードに格納する必要がない。例えば、ノードＲ２が２個の入力ポートＲ２＿１およびＲ２＿４と２個の出力ポートＲ２＿３およびＲ２＿２だけを有する実施形態では、リターンパスに関する情報は、送信元ノードＳから宛先ノードＤへパケット１２３を送信するときにノードＲ２のメモリＭ２に記憶されない。ネットワークのプログラミングがノードＲ３において失敗した場合、パケット１２３は、前述の実施形態において説明したように、送信元ノードＳへ送られる。ノードＲ３は、出力ポートＲ３＿２、リンク１１７および入力ポートＲ２＿４を介して、ノードＲ２へパケット１２３を送信する。ノードＲ２は、その宛先関係から決定できるように、パケット１２３を送信元ノードＳへ送るため出力ポートＲ２＿２だけを使用し、パケット１２３を、出力ポートＲ２＿２、リンク１１３および入力ポートＲ１＿４を介して、ノードＲ１へ送信する。次に、ノードＲ１は、前述の実施形態において説明したように、パケット１２３を送信元ノードＳへ送信する。本実施形態では、ノードＲ２は、ノードＲ２がノードＲ３からパケットを受信し、ノードＲ２におけるネットワークの再プログラミングが成功したときに、ノードＲ３へのパケットの返信を許可されないことが仮定される。

上記の実施形態は、本発明を限定するのではなく、明らかにするものであり、当業者は請求項に記載された事項の範囲から逸脱することなく多数の代替的な実施形態を設計し得ることに注意すべきである。請求項中、括弧内に収められた参照符号は請求項を限定するものと考えるべきではない。語「含む、具備する（ｃｏｍｐｒｉｓｉｎｇ）」は請求項に列挙されていない要素またはステップの存在を除外しない。要素の前に置かれる冠詞（「ａ」または「ａｎ」）はこのような要素が複数個存在することを除外しない。複数の手段を列挙する装置クレームにおいて、これらの複数の手段は全く同一のハードウェアによって具現化することが可能である。ある種の手段が相互に異なる請求項で引用されるという単なる事実は、これらの手段を有利に組み合わせることができないということを示唆しない。

宛先ルーティングを使用して送信元ノードから宛先ノードへパケットを送信するときに、本発明によるネットワークにおいてパケットのリターンパスを決定する方法を使用するネットワークの一実施形態を示す図である。 送信元ルーティングを使用して送信元ノードから宛先ノードへパケットを送信するときに、本発明によるネットワークにおいてパケットのリターンパスを決定する方法を使用するネットワークの一実施形態を示す図である。

Claims (6)

1. 複数のノードと前記ノード間の複数のリンクとを備え、第１のノードが第２のノードとの間に少なくとも１つのリンクを有し、第１のノードそれぞれに対して、前記第２のノードと前記第１のノードとの間にリンクが存在するネットワークにおいて、送信元ノードから宛先ノードへ少なくとも１つの中間ノードを介して前記パケットを送信するときに使用され、パケットのリターンパスを決定する方法であって、
   前記リターンパスを得るために情報を前記中間ノードに記憶するステップを含むことを特徴とするネットワークにおいてパケットのリターンパスを決定する方法。
2. 送信元ノードから宛先ノードへパケットを送信するときに、前記リターンパスを得るために前記パケットが通過した各ノードに情報を記憶するステップをさらに含むことを特徴とする請求項１記載のネットワークにおいてパケットのリターンパスを決定する方法。
3. 前記中間ノードに記憶された情報が、前記パケットの識別子と、前記パケットを戻すために使用される前記中間ノードの出力ポートを符号化する情報と、を含むことを特徴とする請求項１記載のネットワークにおいてパケットのリターンパスを決定する方法。
4. 複数のノードと前記ノード間の複数のリンクとを有し、第１のノードが第２のノードとの間に少なくとも１本のリンクを有し、前記第１のノードそれぞれに対して前記第２のノードと前記第１のノートとの間にリンクが存在し、送信元ノードから宛先ノードへ少なくとも１つの中間ノードを介してパケットを送信するときに前記パケットのリターンパスを決定するように構成されたネットワークを備えている集積回路であって、
   前記中間ノードはリターンパスを得るための情報を記憶するように構成されることを特徴とする集積回路。
5. 前記複数のノードのうちの各ノードは、前記リターンパスを得るための情報を記憶するように構成されることを特徴とする請求項４記載の集積回路。
6. 前記中間ノードは、前記パケットの識別子と、前記パケットを戻すために使用される前記中間ノードの出力ポートを符号化する情報と、を記憶するように構成されることを特徴とする請求項４記載の集積回路。

Images