(57)【特許請求の範囲】
【請求項１】
複数のノードにより構成されるネットワークに含まれる始点ノードから他のノードへ至る最短経路を、ネットワーク行列を用いて探索するための第１のシステムであって、
前記ネットワーク行列は、当該ネットワークに含まれる各ノードを基端とし、基端のノードに繋がる他のノードを先端とする各リンクのコストを含み、
当該第１のシステムは、複数の回路を構成するための演算ユニットを有し、前記複数の回路は、前記ネットワーク行列に含まれる探索対象のリンクのコストから第１の値を減算することと、
減算によりコストがゼロになる前記探索対象のリンクの先端のノードを到達ノードとすることと、
前記ネットワーク行列に含まれるリンクの内、前記到達ノードを先端とするリンクのコストを探索対象外の値に変更することと、
減算によりコストがゼロにならない前記探索対象のリンクのコストの減算後の値を、継続探索対象のリンクのコストとすることとを実行するための回路を含み、さらに、
当該第１のシステムは、前記ネットワーク行列に含まれる、前記始点ノードを基端とするリンクのコストを、前記探索対象のリンクのコストとして、前記演算ユニットに初期入力するための手段と、
前記継続探索対象のリンクのコストと、前記ネットワーク行列に含まれる前記到達ノードを基端とするリンクのコストとを、前記探索対象のリンクのコストとして、前記演算ユニットに再入力するための手段とを有する第１のシステム。
【請求項２】
請求項１において、
前記演算ユニットは、前記探索対象のリンクのコストの最小値を検出して前記第１の値とする回路を含む、第１のシステム。
【請求項３】
請求項１において、
前記第１の値が、前記探索対象のリンクのコストの最小単位である、第１のシステム。
【請求項４】
請求項１において、
前記始点ノードから到達可能な前記他のノードの全てが前記到達ノードになるまで前記演算ユニットへの前記再入力を繰り返し、前記始点ノードから前記他のノードへ至る最短経路を得るための第１の機能をさらに有する第１のシステム。
【請求項５】
請求項４において、
前記演算ユニットは、前記探索対象のリンクのコストの最小値を検出して前記第１の値とする回路を含み、
前記第１の機能は、前記ネットワーク行列に含まれる、前記始点ノードに対する前記他のノードの数だけ、前記演算ユニットへの前記再入力を繰り返す、第１のシステム。
【請求項６】
請求項４において、
前記第１の機能は、さらに、前記ネットワーク行列に含まれる全てのノードを前記始点ノードとして、前記演算ユニットへの前記初期入力を繰り返し、前記ネットワーク行列に含まれる各ノードから他の各ノードへ至る最短経路を得る、第１のシステム。
【請求項７】
複数のノードにより構成されるネットワークに含まれる始点ノードから他のノードへ至る最短コストを求める第２のシステムであって、
請求項４に記載の第１のシステムと、
前記第１の機能により得られた最短経路と、前記ネットワーク行列とにより、前記始点ノードから前記他のノードへ至る最短コストを得るための第２の機能とを有する第２のシステム。
【請求項８】
請求項７において、
前記第２の機能は、さらに、前記ネットワーク行列に含まれる全てのノードを前記始点ノードとした最短経路を取得し、前記ネットワーク行列に含まれる各ノードから他の各ノードへ至る最短コストを得る、第２のシステム。
【請求項９】
請求項７に記載の第２のシステムと、
ｎ個のノードを含む解析対象ネットワークの中の起点ノードから目的地ノードに至る最短経路を得るための第３の機能とを有し、
前記演算ユニットは、最大ｍ個のノードについて演算可能であり、
この第３の機能は、
前記解析対象ネットワークを、１つのネットワークが最大ｍ個のノードを含む最下層の複数のネットワークに分解することと、
下位層の複数のネットワークの少なくとも２つのネットワークを接続するための境界ノードを最大ｍ個含む上位層のネットワークを生成することと、
前記最下層の複数のネットワークの各々について前記ネットワーク行列を生成することと、
前記第２の機能により、各ノードから他の各ノードへ至る最短コストを得ることと、
前記上位層のネットワークについて、他の境界ノードとの最短コストをリンクのコストとして含む上位層のネットワーク行列を生成することと、
前記上位層のネットワークについて、各々の境界ノードを前記始点ノードとして、前記第２の機能により、各境界ノードから他の各境界ノードに至る最短コストを得ることとを含む、第３のシステム。
【請求項１０】
請求項９において、
前記第３の機能は、前記上位層のネットワークに含まれる複数の境界ノードを介して前記起点ノードから前記目的地ノードに至る複数の経路の各々について、前記最下層の複数のネットワークの中の前記起点ノードを含むネットワークにおける前記起点ノードから境界ノードに至る最短コスト、前記上位層のネットワークに含まれる境界ノード間の最短コスト、および前記最下層の複数のネットワークの中の前記目的地ノードを含むネットワークにおける境界ノードから前記目的地ノードまでの最短コストの和を求めることと、
前記最短コストの和が最小の経路を得ることとを、さらに含む、第３のシステム。
【請求項１１】
請求項９において、
コンピュータネットワークに接続され、パケットを送出するネクストホップを選択する機能を備えたルーティングユニットを有し、
前記選択する機能は、
ルーティングテーブルに基づき、前記ネクストホップを選択することと、
ルーティングプロトコルにより、前記ネクストホップを含むコンピュータネットワークの情報を取得し、前記解析対象ネットワークとして認識し、前記第３の機能により、前記ルーティングテーブルを更新することとを含む、第３のシステム。
【請求項１２】
演算ユニットを用い、複数のノードにより構成されるネットワークに含まれる始点ノードから他のノードへ至る最短経路を探索する第１のプロセスを有する方法であって、
前記第１のプロセスは、
当該ネットワークに含まれる各ノードを基端とし、基端のノードに繋がる他のノードを先端とする各リンクのコストを含むネットワーク行列を取得することと、
演算ユニットに複数の回路を構成することとを含み、
前記複数の回路は、前記ネットワーク行列に含まれる探索対象のリンクのコストから第１の値を減算することと、
減算によりコストがゼロになる前記探索対象のリンクの先端のノードを到達ノードとすることと、
前記ネットワーク行列に含まれるリンクの内、前記到達ノードを先端とするリンクのコストを探索対象外の値に変更することと、
減算によりコストがゼロにならない前記探索対象のリンクのコストの減算後の値を、継続探索対象のリンクのコストとすることとを実行するための回路を含み、
前記第１のプロセスは、さらに、
前記ネットワーク行列に含まれる、前記始点ノードを基端とするリンクのコストを、前記探索対象のリンクのコストとして、前記演算ユニットに初期入力することと、
前記継続探索対象のリンクのコストと、前記ネットワーク行列に含まれる前記到達ノードを基端とするリンクのコストとを、前記探索対象のリンクのコストとして、前記演算ユニットに再入力することとを含む、方法。
【請求項１３】
演算ユニットを用い、複数のノードにより構成されるネットワークに含まれる始点ノードから他のノードへ至る最短経路を探索する第１のプロセスを有する方法であって、
当該ネットワークに含まれる各ノードを基端とし、基端のノードに繋がる他のノードを先端とする各リンクのコストを含むネットワーク行列を用いることを含み、
演算ユニットは、前記ネットワーク行列に含まれる探索対象のリンクのコストから第１の値を減算することと、
減算によりコストがゼロになる前記探索対象のリンクの先端のノードを到達ノードとすることと、
前記ネットワーク行列に含まれるリンクの内、前記到達ノードを先端とするリンクのコストを探索対象外の値に変更することと、
減算によりコストがゼロにならない前記探索対象のリンクのコストの減算後の値を、継続探索対象のリンクのコストとすることとを実行するための回路を含み、
前記第１のプロセスは、
前記ネットワーク行列に含まれる、前記始点ノードを基端とするリンクのコストを、前記探索対象のリンクのコストとして、前記演算ユニットに初期入力することと、
前記継続探索対象のリンクのコストと、前記ネットワーク行列に含まれる前記到達ノードを基端とするリンクのコストとを、前記探索対象のリンクのコストとして、前記演算ユニットに再入力することとを含む、方法。
【請求項１４】
請求項１３において、前記第１のプロセスは、
前記始点ノードから到達可能な前記他のノードの全てが前記到達ノードになるまで前記演算ユニットへの前記再入力を繰り返し、前記始点ノードから前記他のノードへ至る最短経路を得ることをさらに含む、方法。
【請求項１５】
請求項１４において、
前記演算ユニットは、前記探索対象のリンクのコストの最小値を検出して前記第１の値とする回路を含み、
前記第１のプロセスの前記最短経路を得るステップでは、前記ネットワーク行列に含まれる、前記始点ノードに対する前記他のノードの数だけ、前記演算ユニットへの前記再入力を繰り返す、方法。
【請求項１６】
請求項１３において、前記第１のプロセスは、
前記ネットワーク行列に含まれる全てのノードを前記始点ノードとして、前記演算ユニットへの前記初期入力を繰り返し、前記ネットワーク行列に含まれる各ノードから他の各ノードへ至る最短経路を得ることをさらに有する、方法。
【請求項１７】
請求項１４において、
複数のノードにより構成されるネットワークに含まれる始点ノードから他のノードへ至る最短コストを求める第２のプロセスを有し、
前記第２のプロセスは、
前記第１のプロセスにより最短経路を得ることと、
得られた最短経路と、前記ネットワーク行列とにより、前記始点ノードから前記他のノードへ至る最短コストを得ることとを含む、方法。
【請求項１８】
請求項１７において、前記第２のプロセスは、
前記ネットワーク行列に含まれる全てのノードを前記始点ノードとした最短経路を取得し、前記ネットワーク行列に含まれる各ノードから他の各ノードへ至る最短コストを得ることをさらに含む、方法。
【請求項１９】
請求項１８において、
ｎ個のノードを含む解析対象ネットワークの中の起点ノードから目的地ノードに至る最短経路を得る第３のプロセスを有し、
前記演算ユニットは、最大ｍ個のノードについて演算可能であり、
前記第３のプロセスは、
前記解析対象ネットワークを、１つのネットワークが最大ｍ個のノードを含む最下層の複数のネットワークに分解することと、
下位層の複数のネットワークの少なくとも２つのネットワークを接続するための境界ノードを最大ｍ個含む上位層のネットワークを生成することと、
前記最下層の複数のネットワークの各々について前記ネットワーク行列を生成することと、
前記第２のプロセスにより、各ノードから他の各ノードへ至る最短コストを得ることと、
前記上位層のネットワークについて、他の境界ノードとの最短コストをリンクのコストとして含む上位層のネットワーク行列を生成することと、
前記上位層のネットワークについて、各々の境界ノードを前記始点ノードとして、前記第２のプロセスにより、各境界ノードから他の各境界ノードに至る最短コストを得ることとを含む、方法。
【請求項２０】
請求項１９において、
前記第３のプロセスは、
前記上位層のネットワークに含まれる複数の境界ノードを介して前記起点ノードから前記目的地ノードに至る複数の経路の各々について、前記最下層の複数のネットワークの中の前記起点ノードを含むネットワークにおける前記起点ノードから境界ノードに至る最短コスト、前記上位層のネットワークに含まれる境界ノード間の最短コスト、および前記最下層の複数のネットワークの中の前記目的地ノードを含むネットワークにおける境界ノードから前記目的地ノードまでの最短コストの和を求めることと、
前記最短コストの和が最小の経路を得ることとを、さらに含む、方法。
【請求項２１】
請求項１９において、
コンピュータネットワークに接続され、パケットを送出するネクストホップを選択するプロセスを有する方法であって、
前記選択するプロセスは、
ルーティングテーブルに基づき、前記ネクストホップを選択することと、
ルーティングプロトコルにより、前記ネクストホップを含むコンピュータネットワークの情報を取得し、前記解析対象ネットワークとして認識し、前記第３のプロセスにより、前記ルーティングテーブルを更新することとを含む、方法。
【請求項２２】
複数のノードにより構成されるコンピュータネットワークに含まれる始点ノードから他のノードへ至る最短経路を、前記コンピュータネットワークにアクセスするネットワークインターフェイスを含むルーティングユニットが探索する方法であって、
前記ルーティングユニットが、当該コンピュータネットワークに含まれる各ノードを基端とし、基端のノードに繋がる他のノードを先端とする各リンクのコストを含むネットワーク行列に含まれる探索対象のリンクのコストから第１の値を減算するステップと、
減算によりコストがゼロになる前記探索対象のリンクの先端のノードを到達ノードとするステップと、
前記ネットワーク行列に含まれるリンクの内、前記到達ノードを先端とするリンクのコストを探索対象外の値に変更するステップと、
減算によりコストがゼロにならない前記探索対象のリンクのコストの減算後の値を、継続探索対象のリンクのコストとし、この継続探索対象のリンクのコストと、前記ネットワーク行列に含まれる前記到達ノードを基端とするリンクのコストとを、前記探索対象のリンクのコストとし、前記減算するステップに戻るステップとを含む、方法。
【請求項２３】
請求項２２において、
前記減算するステップにおいては、前記探索対象のリンクのコストの最小値を前記第１の値とする、方法。
【請求項２４】
請求項２２において、
前記減算するステップにおいては、前記探索対象のリンクのコストの最小単位を前記第１の値とする、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークにおける最短経路探索の高速化に関するものである。
【背景技術】
【０００２】
インターネットの爆発的な発展と普及とに伴い、仕事および日常生活においてコンピュータネットワークが頻繁に利用されるようになっている。コンピュータネットワークではルーティングプロトコルによって交換される情報に基づいてルーティングテーブルが作成され、そのルーティングテーブルに従いパケットが配送される。代表的なルーティングプロトコルであるＯＳＰＦ（Open Shortest Path First）では、ダイクストラ法と呼ばれる最短経路探索アルゴリズムを用いて、ルーティングテーブルが作成される。
【０００３】
図１に基づき、ダイクストラ法の具体例について説明する。ダイクストラ法は、ある始点ノードから他の全てのノードまでの最短経路を求めるアルゴリズムである。各ノードは、自分の１つ手前のノード及び距離という２つの情報を持つ。図１ではａ、ｂ、ｃおよびｄはノード、ノード間の数値はリンクコストを表す。まず初めに、始点ノードａの距離Ｄａを０、それ以外のノードの距離Ｄｂ〜Ｄｄを無限大にする。次に，ノードａに隣接する各ノードを順番に調べ、ノードａの距離Ｄａ（＝０）にノードａからのリンクコストを加えた値を暫定的な距離とする（図１（ａ））。
【０００４】
次に、暫定的な距離が付されたノード全体の中から距離が最小であるノードｃの最短経路が決定する。ここで、ノードｄはノードｃを経由する場合を暫定的な経路とし、ノードｄの暫定的な距離が決まる（図１（ｂ））。
【０００５】
この段階でノードｂの距離Ｄｂは４、ノードｄの距離Ｄｄは６である。このため、次にノードｂの経路が決定する。ここで、ノードｄの、ノードｂを経由した暫定的な距離が決まる（図１（ｃ））。
【０００６】
この段階で、ノードｄの最小の距離Ｄｄはノードｃを経由した場合の６に更新され、ノードｄまでの最短経路が決まる（図１（ｄ））。このように、あるノードの最短経路が決まったことにより新たな経路が見つかると、最小の値に距離が更新される。すなわち、新たな経路が既知の経路よりも短い場合は、ノードまでの距離が更新される。このように、各ノードは必要に応じて距離を更新し、暫定的な距離が最小であるノードの最短経路が決定する。
【０００７】
ｎ個のノードを含むネットワークにおいてダイクストラ法により最短経路を決定する方法は、一般的に次のようになる。まず、ノード１からｎとコストｃｉｊのリンク（ｉ、ｊ）の連結グラフＧ＝（Ｖ、Ｅ）を生成し、ノード１からノード２〜ｎへの最短経路を決定する。ダイクストラ法では、各ノードが一時距離ｔＤｊと確定距離Ｄｉ（ｉ＝１〜ｎ）という情報を持ち、一時距離が最小のノードの最短経路が決定する。アルゴリズムは以下の通りである。
【０００８】
ステップ１
始点ノード１は確定距離Ｄ１＝０にする点ｊ（＝２〜ｎ）に対して一時距離ｔＤｊ＝ｃｉｊ（連結グラフＧで（１、Ｊ）のリンクがない場合には無限大）とし、最短経路が確定したノードの集合をＮとする。この時点ではＮ＝［１］である。
【０００９】
ステップ２
最短経路が確定していないノードの集合ｔＮにおいて、一時距離ｔＤｋが最小となるｋを見つけ、Ｄｋ＝ｔＤｋとする。複数あるときは最小のノードｋをとり、そのノードｋを集合Ｎに加える。集合Ｎ＝Ｖ（ｔＮ＝０）であればＤ２からＤｎを出力して終了する。そうでない場合はステップ３へ進む。
【００１０】
ステップ３
集合ｔＮの全てのノードｊに対してｔＤｊ＝ｍｉｎ（ｔＤｊ、Ｄｋ＋ｃｋｊ）とする。その後、ステップ２へ戻る。
【特許文献１】特開２００４−３２５６９号公報
【特許文献２】特開２００１−３０８９１２号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
ＩＰネットワークにおけるパケットのルーティングは、通過するルータにおいて、そのルータが保持するルーティングテーブルを参照することで行われる。ルーティングテーブルには、宛先ネットワークアドレスと対応するＮＨＲ（Next Hop Router（ネクストホップ））が記録され、各パケットの宛先アドレスと最長一致するネットワークアドレスに対応したＮＨＲへパケットが転送される。それぞれのルータにおいて、以上の動作を繰り返すことで、宛先までパケットが転送される。
【００１２】
最短経路の計算結果を元にルーティングテーブルの作成が行われる。このため、今後、インターネットの更なる普及とともにネットワークの規模が拡大すると、最短経路探索処理の負担が増大し、ボトルネックになると考えられる。モバイルの端末が増加することになると、ルーティングテーブルを頻繁に更新することが要求される。また、今後ユビキタスコンピューティング化が進展し、ＲＦＩＤ（Radio Frequency Identification）タグによってあらゆる商品にＩＰアドレスが与えられることが考えられる。あらゆる物にＩＰアドレスを割り当てる場合、膨大な数のＩＰアドレスが必要になり、アドレス空間が３２ｂｉｔである現状のＩＰｖ４ではアドレスが不足する。そこで、アドレス不足の解決のために、アドレス空間を１２８ｂｉｔに拡張したＩＰｖ６が提案されている。したがって、膨大な数のＩＰアドレスの機器を含むネットワークに対応したルーティング方法が要求されている。
【００１３】
さらに、近年、光ネットワークにおいては、リンクコストとして、リンクの速度だけでなく、波長予約の成功率など複数の要因を考慮することが提案されている。また、リンクコストは、そのリンクを使用しているユーザ数、リンクを経由するデータ種類などの要因により変動するため、それらの要因の変動も考慮してルーティングテーブルは更新されることが望ましい。したがって、経路計算における負荷はさらに増大するものと考えられる。
【００１４】
特許文献１では、ルータとは別個に、最短経路を計算する処理を実行する専用の装置を設けることを提案している。ハードウェアを増加して、ルータにおける経路計算に要する負荷を低減するものである。しかしながら、ネットワークを構成するシステムとして、ルーティングのための経路計算の負荷を低減するというものではない。
【００１５】
ダイクストラ法は単純なアルゴリズムであり、シーケンシャルプロセッサの処理に向いているという点で現在広く用いられている。しかしながら、ダイクストラ法の計算量はノード数ｎに対してＯ（ｎ２）であり、ノード数の増加にともない計算量が大幅に増加するという問題がある。
【００１６】
特許文献２では、階層化されたＱＯＳＰＦ網における経路計算について記載されている。バックボーンなどを含むエリア内のルーティング情報がエリア境界ルータから縮退されたルーティング情報として提供されるものである。しかしながら、縮退されたルーティング情報により、宛先のノードに対して、どのエリアが通過可能であるかが分かったとしても、１つのエリアに複数のルートが含まれている場合など、条件によっては、最短経路を計算するためには、それらのエリア内の全ノードを用いて再計算する必要がある。ネットワークを階層化してルーティングのための経路計算をすることは、分散処理を可能とし、経路計算の負荷を低減できる方法かもしれない。しかしながら、ダイクストラ法により、全点間の最短経路を計算するためには、さらにｎ回の計算が必要となりＯ（ｎ３）の計算量となる。したがって、ルーティングのための経路計算の負荷を低減できない。
【課題を解決するための手段】
【００１７】
本発明の一態様は、複数のノードにより構成されるネットワークに含まれる始点ノードから他のノードへ至る最短経路を、ネットワーク行列を用いて探索するための第１のシステムである。ネットワーク行列は、当該ネットワークに含まれる各ノードを基端とし、基端のノードに繋がる他のノードを先端とする各リンク（接続、連結）のコストを含む。
【００１８】
この第１のシステムは、複数の回路を構成するための演算ユニットを有し、複数の回路は、ネットワーク行列に含まれる探索対象のリンクのコストから第１の値を減算することと、減算によりコストがゼロになる探索対象のリンクの先端のノードを到達ノードとすることと、ネットワーク行列に含まれるリンクの内、到達ノードを先端とするリンクのコストを探索対象外の値に変更することと、減算によりコストがゼロにならない探索対象のリンクのコストの減算後の値を、継続探索対象のリンクのコストとすることとを実行するための回路を含む。
【００１９】
さらに、この第１のシステムは、ネットワーク行列に含まれる、始点ノードを基端とするリンクのコストを、探索対象のリンクのコストとして、演算ユニットに初期入力するための手段と、継続探索対象のリンクのコストと、ネットワーク行列に含まれる到達ノードを基端とするリンクのコストとを、探索対象のリンクのコストとして、演算ユニットに再入力するための手段とを有する。初期入力するための手段および再入力するための手段は、演算ユニットに含まれる回路あるいは含まれない回路により実現しても良く、ソフトウェアにより実現しても良い。
【００２０】
この第１のシステムは、減算という並列演算の容易なプロセスにより距離が最小のノードを検出する。したがって、並列処理要素を数多く含む演算ユニットを使用することにより処理時間を短縮できる。演算ユニットは、探索対象のリンクのコストの最小値を検出して第１の値とする回路を含むことが望ましい。第１の値が、探索対象のリンクのコストの最小単位であっても良い。
【００２１】
この第１のシステムは、始点ノードから到達可能な他のノードの全てが到達ノードになるまで演算ユニットへの再入力を繰り返し、始点ノードから他のノードへ至る最短経路を得るための第１の機能をさらに有することが望ましい。演算ユニットが、探索対象のリンクのコストの最小値を検出して第１の値とする回路を含む場合は、第１の機能は、ネットワーク行列に含まれる、始点ノードに対する他のノードの数だけ、演算ユニットへの再入力を繰り返すことにより、最短経路を得ることができる。
【００２２】
第１の機能は、さらに、ネットワーク行列に含まれる全てのノードを始点ノードとして、演算ユニットへの初期入力を繰り返すことにより、ネットワーク行列に含まれる各ノードから他の各ノードへ至る最短経路を得ることができる。
【００２３】
本発明の他の態様は、複数のノードにより構成されるネットワークに含まれる始点ノードから他のノードへ至る最短コストを求める第２のシステムである。この第２のシステムは、第１の機能を備えた第１のシステムと、第１の機能により得られた最短経路と、ネットワーク行列により、始点ノードから他のノードへ至る最短コストを得るための第２の機能とを有する。第２の機能は、さらに、ネットワーク行列に含まれる全てのノードを始点ノードとした最短経路を取得し、ネットワーク行列に含まれる各ノードから他の各ノードへ至る最短コストを得る。ネットワーク行列に含まれる各ノードから他の各ノードへ至る最短コストを得ることにより、他のネットワークと接続するノードから他のノードに至る最短コストを抽出できる。その抽出されたコストを用いて、そのネットワークを通る経路の情報を縮退できる。したがって、最短コストを得ることにより、境界ノードを集めた上位層のネットワーク行列を生成することが可能となる。
【００２４】
すなわち、本発明の他の態様は、第２の機能を備えた第２のシステムと、ｎ個のノードを含む解析対象ネットワークの中の起点ノードから目的地ノードに至る最短経路を得るための第３の機能とを有する第３のシステムである。この第３のシステムでは、演算ユニットは、最大ｍ個のノードについて演算可能であり、第３の機能は、解析対象ネットワークを階層化する機能として、１つのネットワークが最大ｍ個のノードを含む最下層の複数のネットワークに分解することと、下位層の複数のネットワークの少なくとも２つのネットワークを接続するための境界ノードを最大ｍ個含む上位層のネットワークを生成することとを含む。さらに、第３の機能は、階層化されたネットワークを用いて最短経路を探索する機能として、最下層の複数のネットワークの各々についてネットワーク行列を生成することと、第２の機能により、各ノードから他の各ノードへ至る最短コストを得ることと、上位層のネットワークについて、他の境界ノードとの最短コストをリンクのコストとして含む上位層のネットワーク行列を生成することと、上位層のネットワークについて、各々の境界ノードを始点ノードとして、第２の機能により、各境界ノードから他の各境界ノードに至る最短コストを得ることとを含む。
【００２５】
階層化することにより、減算という単純な演算を行うエレメントを含む限られたハードウェア資源により、大規模なネットワークについても最短経路を得ることができる。
【００２６】
第３の機能は、上位層のネットワークに含まれる複数の境界ノードを介して起点ノードから目的地ノードに至る複数の経路の各々について、最下層の複数のネットワークの中の起点ノードを含むネットワークにおける起点ノードから境界ノードに至る最短コスト、上位層のネットワークに含まれる境界ノード間の最短コスト、および最下層の複数のネットワークの中の目的地ノードを含むネットワークにおける境界ノードから目的地ノードまでの最短コストの和を求めることと、最短コストの和が最小の経路を得ることとを、さらに含むことが好ましい。各層において得られたノード間（境界ノード間を含む）の最短コストを用いて、解析対象ネットワークに含まれるノードを目的地ノードとした最短経路を決定できる。
【００２７】
第３のシステムの一例はルータであり、コンピュータネットワークに接続され、パケットを送出するネクストホップを選択する機能を備えたルーティングユニットを有する。選択する機能は、ルーティングテーブルに基づき、ネクストホップを選択することと、ルーティングプロトコルにより、ネクストホップを含むコンピュータネットワークの情報を取得し、解析対象ネットワークとして認識し、第３の機能により、ルーティングテーブルを更新することとを含む。
【００２８】
本発明の他の態様は、回路を再構成可能な演算ユニットを用い、複数のノードにより構成されるネットワークに含まれる始点ノードから他のノードへ至る最短経路を探索する第１のプロセスを有する方法である。この第１のプロセスは、当該ネットワークに含まれる各ノードを基端とし、基端のノードに繋がる他のノードを先端とする各リンクのコストを含むネットワーク行列を取得することと、演算ユニットに複数の回路を構成することとを含む。複数の回路は、ネットワーク行列に含まれる探索対象のリンクのコストから第１の値を減算することと、減算によりコストがゼロになる探索対象のリンクの先端のノードを到達ノードとすることと、ネットワーク行列に含まれるリンクの内、到達ノードを先端とするリンクのコストを探索対象外の値に変更することと、減算によりコストがゼロにならない探索対象のリンクのコストの減算後の値を、継続探索対象のリンクのコストとすることとを実行するための回路を含む。
【００２９】
さらに、第１のプロセスは、ネットワーク行列に含まれる、始点ノードを基端とするリンクのコストを、探索対象のリンクのコストとして、演算ユニットに初期入力することと、継続探索対象のリンクのコストと、ネットワーク行列に含まれる到達ノードを基端とするリンクのコストとを、探索対象のリンクのコストとして、演算ユニットに再入力することとを含む。
【００３０】
また、本発明の他の一態様は、上記の複数の回路が構成された演算ユニットを用い、複数のノードにより構成されるネットワークに含まれる始点ノードから他のノードへ至る最短経路を探索する第１のプロセスを有する方法である。この方法も、当該ネットワークに含まれる各ノードを基端とし、基端のノードに繋がる他のノードを先端とする各リンクのコストを含むネットワーク行列を用いることを含む。
【００３１】
第１のプロセスは、以下のステップを含む。
１−１．回路が構成された演算ユニットに対して、ネットワーク行列に含まれる、始点ノードを基端とするリンクのコストを、探索対象のリンクのコストとして、演算ユニットに初期入力すること。
１−２．継続探索対象のリンクのコストと、ネットワーク行列に含まれる到達ノードを基端とするリンクのコストとを、探索対象のリンクのコストとして、演算ユニットに再入力すること。
【００３２】
第１のプロセスは、以下のステップをさらに含むことが望ましい。
１−３．始点ノードから到達可能な他のノードの全てが到達ノードになるまで演算ユニットへの再入力を繰り返し、始点ノードから他のノードへ至る最短経路を得ること。
【００３３】
演算ユニットは、探索対象のリンクのコストの最小値を検出して第１の値とする回路を含み、第１のプロセスの最短経路を得るステップ１−３では、ネットワーク行列に含まれる、始点ノードに対する他のノードの数だけ、演算ユニットへの再入力を繰り返すことが望ましい。
【００３４】
第１のプロセスは、以下のステップをさらに含むことが望ましい。
１−４．ネットワーク行列に含まれる全てのノードを始点ノードとして、演算ユニットへの初期入力を繰り返し、ネットワーク行列に含まれる各ノードから他の各ノードへ至る最短経路を得ること。
【００３５】
本発明に含まれる方法の一形態は、複数のノードにより構成されるネットワークに含まれる始点ノードから他のノードへ至る最短コストを求める第２のプロセスを有する。第２のプロセスは、以下のステップを含む。
２−１．第１のプロセスにより最短経路を得ること。
２−２．得られた最短経路と、ネットワーク行列より、始点ノードから他のノードへ至る最短コストを得ること。
【００３６】
第２のプロセスは、以下のステップをさらに含むことが望ましい。
２−３．ネットワーク行列に含まれる全てのノードを始点ノードとした最短経路を取得し、ネットワーク行列に含まれる各ノードから他の各ノードへ至る最短コストを得ること。
【００３７】
本発明に含まれる方法の他の形態は、さらに、ｎ個のノードを含む解析対象ネットワークの中の起点ノードから目的地ノードに至る最短経路を得る第３のプロセスを有する。演算ユニットは、最大ｍ個のノードについて演算可能である場合、第３のプロセスは、以下のステップを含む。
３−１．解析対象ネットワークを、１つのネットワークが最大ｍ個のノードを含む最下層の複数のネットワークに分解すること。
３−２．下位層の複数のネットワークの少なくとも２つのネットワークを接続するための境界ノードを最大ｍ個含む上位層のネットワークを生成すること。
３−３．最下層の複数のネットワークの各々についてネットワーク行列を生成すること。
３−４．第２のプロセスにより、各ノードから他の各ノードへ至る最短コストを得ること。
３−５．上位層のネットワークについて、他の境界ノードとの最短コストをリンクのコストとして含む上位層のネットワーク行列を生成すること。
３−６．上位層のネットワークについて、各々の境界ノードを始点ノードとして、第２のプロセスにより、各境界ノードから他の各境界ノードに至る最短コストを得ること。
【００３８】
第３のプロセスは、さらに、以下のステップを含むことが望ましい。
３−７．上位層のネットワークに含まれる複数の境界ノードを介して起点ノードから目的地ノードに至る複数の経路の各々について、最下層の複数のネットワークの中の起点ノードを含むネットワークにおける起点ノードから境界ノードに至る最短コスト、上位層のネットワークに含まれる境界ノード間の最短コスト、および最下層の複数のネットワークの中の目的地ノードを含むネットワークにおける境界ノードから目的地ノードまでの最短コストの和を求めること。
３−８．最短コストの和が最小の経路を得ること。
【００３９】
さらに、本発明に含まれる方法の他の形態は、さらに、コンピュータネットワークに接続され、パケットを送出するネクストホップを選択するプロセスを有する。この選択するプロセスは、以下のステップを含む。
４−１．ルーティングテーブルに基づき、ネクストホップを選択すること。
４−２．ルーティングプロトコルにより、ネクストホップを含むコンピュータネットワークの情報を取得し、解析対象ネットワークとして認識し、第３のプロセスにより、ルーティングテーブルを更新すること。
【００４０】
本発明の他の態様は、複数のノードにより構成されるコンピュータネットワークに含まれる始点ノードから他のノードへ至る最短経路を、コンピュータネットワークにアクセスするネットワークインターフェイスを含むルーティングユニットが探索する方法であって、ネットワーク行列を用いることを含み、以下のステップを有する。
ａ１．ルーティングユニットが、当該コンピュータネットワークに含まれる各ノードを基端とし、基端のノードに繋がる他のノードを先端とする各リンクのコストを含むネットワーク行列に含まれる探索対象のリンクのコストから第１の値を減算すること。
ａ２．ルーティングユニットが、減算によりコストがゼロになる探索対象のリンクの先端のノードを到達ノードとすること。
ａ３．ルーティングユニットが、ネットワーク行列に含まれるリンクの内、到達ノードを先端とするリンクのコストを探索対象外の値に変更すること。
ａ４．ルーティングユニットが、減算によりコストがゼロにならない探索対象のリンクのコストの減算後の値を、継続探索対象のリンクのコストとし、この継続探索対象のリンクのコストと、ネットワーク行列に含まれる到達ノードを基端とするリンクのコストとを、探索対象のリンクのコストとし、ステップａ１に戻ること。
【００４１】
減算するステップａ１においては、探索対象のリンクのコストの最小値を第１の値とすることが望ましい。減算するステップａ１においては、探索対象のリンクのコストの最小単位を第１の値としても良い。
【発明を実施するための最良の形態】
【００４２】
図２から図８に、本発明に含まれるアルゴリズムにより、最短経路を探索する様子を示している。図２（ａ）は、４つのノードＡ〜Ｄを含むネットワークＮを示している。図２（ｂ）は、ネットワークＮの各リンクのコストを含むネットワーク行列ＭＮを示している。インターネットなどのコンピュータネットワークにおいて、ノード間のコスト（リンクコスト）を決定する典型的な要素は、通信速度の逆数である。その他に、光ネットワークにおいては波長予約の成功率、送信対象のデータ種別、ＱｏＳにより予約された帯域など複数の要因をリンクコストとして反映することができる。
【００４３】
このネットワーク行列ＭＮは、ネットワークＮに含まれる各ノードを基端とし、基端のノードに繋がる他のノードを先端とする各リンクのコストをエレメントとして含む。この例では、ノードＡを基端としノードＢを先端とするリンク（接続、連結）ＡＢのコスト（リンクコスト）は４、ノードＡを基端としノードＣを先端とするリンクＡＣのコストは３、ノードＢを基端としノードＣを先端とするリンクＢＣのコストは５、ノードＢを基端としノードＤを先端とするリンクＢＤのコストは３、ノードＣを基端としノードＤを先端とするリンクＣＤのコストは３である。ネットワーク行列ＭＮの他のエレメントは繋がっていないため、そのエレメントのコストは、探索対象にならないように、ここでは無限大に設定している。探索のシステムにより、探索対象でないことを示す値は無限大に限定されない。
【００４４】
また、以下では、ノードＡを始点ノードとして、他のノードへ至る最短経路を探索する例を説明する。このため、ノードＡを先端とするリンクＢＡ、ＣＡおよびＤＡは、探索の対象にならないので、それらのコストは予め無限大にセットされている。さらに、リンクＡＡ、ＢＢ、ＣＣおよびＤＤは存在しないので、やはり無限大にセットされている。
【００４５】
図２（ｃ）は、探索が終了したリンクを示す経路行列ＭＲを示している。また、この経路行列ＭＲは、経路探索により到達済みのノードを示し、また、探索対象のリンクの基端を示す機能を含む。したがって、始点ノードであるノードＡは、到達していることを示すフラグ「１」が付されている。
【００４６】
このネットワーク行列ＭＮに対して、上記のステップａ１〜ａ４を含むアルゴリズムを適用して、最短経路を探索する例を説明する。まず、図２に示すように、始点ノードであるノードＡを基端とするリンクのコストが探索対象のリンクのコストとして選択される。次に、図３（ｂ）に示すように、探索対象のリンクのコストから最小値である「３」が減算され、リンクＡＣのコストがゼロになる（ステップａ１）。
【００４７】
減算によりコストがゼロになる探索対象のリンクの先端のノードが到達ノードである。したがって、図３（ｃ）に示すように、経路行列ＭＲのエレメントＡＣに到達済みのフラグ「１」を付す（ステップａ２）。
【００４８】
また、ネットワーク行列ＭＮに含まれるリンクの内、到達ノードを先端とするリンクのコストを探索対象外の値に変更する。このため、図４（ｂ）に示すように、到達ノードであるノードＣを先端とするリンクＡＣ、ＢＣおよびＤＣのコストを探索対象外の値である無限大にセットする（ステップａ３）。
【００４９】
減算されたリンクのコストの内、到達ノードを示すゼロ以外の減算後の値は継続探索の対象となる。さらに、到達ノードを基端とするリンクのコストが探索対象として加えられる。したがって、この例では、経路行列ＭＲに到達済みのフラグ「１」が付されたノードＡおよびノードＣを基端とするリンクのコストが、次の探索対象のリンクのコストとなる。
【００５０】
これらのリンクのコストから、最小値の「１」が減算される。その結果、図５（ｂ）に示すように、リンクＡＢのコストがゼロになる。減算によりコストがゼロになる探索対象のリンクの先端のノードが到達ノードである。したがって、図５（ｃ）に示すように、経路行列ＭＲのエレメントＡＢに到達済みのフラグ「１」を付す。
【００５１】
また、ネットワーク行列ＭＮに含まれるリンクの内、到達ノードを先端とするリンクのコストを探索対象外の値に変更する。このため、図６（ｂ）に示すように、到達ノードであるノードＢを先端とするリンクＡＢ、ＣＢおよびＤＢのコストを探索対象外の値である無限大にセットする。
【００５２】
減算されたリンクのコストの内、到達ノードを示すゼロ以外の減算後の値は継続探索の対象となる。さらに、到達ノードを基端とするリンクのコストが探索対象として加えられる。したがって、この例では、経路行列ＭＲにフラグ「１」が付されたノードＡ、ＢおよびＣを基端とするリンクのコストが、次の探索対象のリンクのコストとなる。
【００５３】
これらのリンクのコストから、最小値の「２」が減算される。その結果、図７（ｂ）に示すように、リンクＣＤのコストがゼロになる。減算によりコストがゼロになる探索対象のリンクの先端のノードが到達ノードである。したがって、図７（ｃ）に示すように、経路行列ＭＲのエレメントＣＤに到達済みのフラグ「１」を付す。
【００５４】
また、ネットワーク行列ＭＮに含まれるリンクの内、到達ノードを先端とするリンクのコストを探索対象外の値に変更する。このため、図８（ｂ）に示すように、到達ノードであるノードＤを先端とするリンクＢＤおよびＣＤのコストを探索対象外の値である無限大にセットする。この結果、ネットワーク行列ＭＮに含まれる全てのリンクのコストが検索対象外となり、始点ノードＡから他のノードに至る全ての最短経路が探索されたことになる。
【００５５】
このアルゴリズムでは、探索対象のリンクのコストから、それらのコストの内の最小値を減算する。したがって、少なくとも１つのリンクのコストはゼロになり、一回の減算により、少なくとも１つの到達ノードが探索される。このため、リンクのコストの大小に関わらず、最大で、ネットワークに含まれる始点ノード以外の他のノードの数、すなわち、ネットワークに含まれるノードの数Ｎａに対して（Ｎａ−１）回だけ、上記の処理を繰り返すことにより、始点ノードから他のノードに至る全ての最短経路を探索できる。したがって、ループを繰り返す回数は、最大でノードの総数に、ほぼ比例して増加するだけである。また、ノードの数が決まれば、（Ｎａ−１）回だけ繰り返すことにより、必ず始点ノードから他のノードに至る全ての最短経路が探索できているので、上述したように、ネットワーク行列の全てのエレメントが無限大であるか否かを確認する必要もない。
【００５６】
一方、探索対象のリンクのコストから、それらのコストの最小単位を減算するアルゴリズムであっても良い。この例では、コストの最小単位は「１」であり、一回のループで、ネットワーク行列のうち、探索対象のリンクのコストから「１」を引く。減算のループを繰り返し、いずれかのコストがゼロになったときに、到達ノードが検索される。このアルゴリズムでは、ループ回数が、コストに依存して増大する。
【００５７】
図９に、経路行列ＭＲから、最短コスト行列ＭＣを求める様子を示している。始点ノードＡについて、経路行列ＭＲを取得する（ステップ２−１）。図８（ｃ）で得られた経路行列ＭＲと、図２（ｂ）に示すオリジナルのネットワーク行列ＭＮとより、図９（ａ）に示すように、最短経路に含まれる各リンクのコストが判明する。したがって、図９（ｂ）に示すように、到達ノードを辿って、始点ノードＡから他の各ノードに至る最短コストが求められ、最短コスト行列ＭＣのノードＡを基端とする行のエレメントが決まる（ステップ２−２）。ネットワーク行列ＭＮに含まれる全てのノードを始点ノードとして、上記のステップ２−１および２−２を繰り返す。これにより、図９（ｃ）に示すようなネットワーク行列に含まれる全てのノードから他のノードへ至る最短コスト行列ＭＣを得ることができる（ステップ２−３）。
【００５８】
図９（ｄ）は、最短コスト行列ＭＣの一般的な表現を示す。ノードａ１１〜ａ１４に対して、最短コストｘ１〜ｘ１２が得られる。したがって、最短コスト行列ＭＣにより、ネットワークＮに含まれる、あるノードと他のノードとが決まれば、その間の最短コストを抽出することができる。
【００５９】
図１０に、異なるネットワークについて、上記のアルゴリズムを適用した結果を示している。図１０（ａ）に示すネットワークＮは、ノードＡ〜Ｆの６つのノードを含む。図１０（ｂ）は、このネットワークＮの各リンクのコストを示すネットワーク行列ＭＮであり、始点ノードをノードＡに設定している。図１０（ｃ）は、上記のアルゴリズムのステップａ１〜ａ４にしたがって求められた、始点ノードＡから、他のノードに至る最短経路を示す経路行列ＭＲである。
【００６０】
図１１に、上記の最短経路探索アルゴリズムを利用して、ルーティングテーブルを更新する機能を備えたルータの概要を示している。このルータ１００は、コンピュータネットワークの一つのノードを構成するデバイスであり、ＣＰＵ、メモリ、回路を再構成可能なプロセッサなどを含む適当なハードウェア資源と、それらを制御するための適当なソフトウェア資源とを備えている。ルータ１００は、有線または無線を含む適当な伝送経路により隣接するルータとの間でデータを交換可能なネットワークインターフェイス１０１と、このネットワークインターフェイス１０１を介して送受信するパケットデータ（パケット）を生成および解析する解析ユニット１０２と、パケットのＩＰヘッダーの情報に基づき、パケットを送出するネクストホップルータ（ネクストホップ）を選択する機能を備えたルーティングユニット８０とを含む。
【００６１】
ルーティングユニット８０としての機能は、専用のモジュール、あるいは他の機能と共用のハードウェア資源、例えば、ＣＰＵあるいは再構成可能なプロセッサとソフトウェアにより提供される。ルーティングユニット８０は、ルーティングテーブル８１を参照してパケットを送出するネクストホップを選択する機能８２と、動的なルーティングテーブルの更新を可能とする適当なルーティングプロトコル、例えばＯＳＰＦにより、近隣のルータを含めたネットワークのルーティングに関する構成を示す情報を取得し、ルーティングテーブル８１を更新する機能８３とを含む。この更新する機能８３は、ルーティングプロトコルにより取得したネットワークの情報を解析対象のネットワークとし、そのネットワークを示すネットワーク行列３９を生成して、または、生成できる情報としてルーティング解析を行なうための下層の解析システム３０に提供する。ＯＳＰＦのようなリンクステート型のルーティングアルゴリズムでは、ルータ間でリンク情報をＬＳＡ（Link-State Advertisement）で定期的に交換する。したがって、そのネットワークに属する各ノードはネットワーク中のすべてのリンク情報（コスト）を知っている。したがって、ネットワーク行列３９には、ＬＳＡにより得られたネットワーク内のリンクコスト情報を含めることができる。
【００６２】
解析システム３０は、階層化された構成を備えている。上位の階層の機能３１は、上位のアプリケーションあるいはシステムより提供された解析対象のネットワークを階層化して、小規模のネットワークに分割する。中間の階層の機能２１は、小規模のネットワークのノード間の最短コストを上位の階層に提供し、上位の階層でネットワークの再編成を可能とする。下層の階層の機能１１は、小規模のネットワークのノード間の最短経路を探索して、上位の階層に提供し、ノード間の最短コストを算出可能とする。
【００６３】
下層の第１の機能１１を含む第１のシステム１０は、複数の回路を再構成可能なプロセッサ（演算ユニット）５０と、それを制御するための制御ユニット５１と、メモリ５２とを備えている。メモリ５２には、回路を再構成するための回路構成情報５４が格納されており、制御ユニット５１の構成制御機能５３により、適当なタイミングになると、演算ユニット５０に経路探索のための回路を再構成する。したがって、経路探索を必要としない間は、演算ユニット５０には異なる回路が再構成され、演算ユニット５０は他の機能と共用される。
【００６４】
演算ユニット５０には、経路探索のためのデータを初期入力するための回路６１と、経路探索のためのデータを再入力するための回路６２と、最小値を検出するための回路６３と、減算のための回路６４と、到達ノードを判断するための回路６５と、継続探索のためのデータを生成するための回路６６とが再構成される。また、制御ユニット５１には、適当なプログラムにより、演算ユニット５０に構成された、これらの回路を制御するための第１の機能１１が実装される。第１の機能１１は、初期入力するために始点ノードを選択し、ネットワーク行列ＭＮに含まれる全てのノードを始点ノードとして、演算ユニット５０への初期入力を繰り返す機能１２と、始点ノードから他の全てのノードに到達するまで演算ユニット５０へ再入力を繰り返す機能１３とを含む。
【００６５】
図１２に、第１のシステム１０を実装可能なデータ処理装置の一例を示している。このデータ処理装置１５は、本願の出願人に含まれるアイピーフレックス社が提供するＤＡＰＤＮＡである。このデータ処理装置１５は、回路を再構成可能な領域５０を備えたプロセッシングユニット（ＰＵ）である。また、このデータ処理装置１５は、チップ状に回路が集積化された集積回路装置でもある。このデータ処理装置１５は、再構成可能な領域５０と、この再構成可能な領域５０を再構成する機能を備えたＲＩＳＣなどの汎用プロセッサ（以降ではプロセッサ）５１と、プロセッサ５１のプログラムおよび再構成用のハードウェア情報５４を格納したメモリ５２を備えている。この集積回路装置１５の再構成可能な回路領域５０は、複数のエレメントがアレイまたはマトリクス状に２次元に配置されており、マトリクスとも称される。このマトリクスを本例の演算ユニット５０として使用できる。マトリクス５０は、縦横に２次元に配置された複数のプロセッシングエレメント（ＰＥ）５５と、それらの間に格子状に配置された配線５７と、配線５７の接続ポイントで縦横の配線５７の接続を自由に切り替えることができるスイッチングユニット５６とを備えている。
【００６６】
再構成可能な回路領域５０を構成するためのＰＥ５５の一例は、ルックアップテーブルなどにより自在に機能を設定可能なものである。この集積回路装置１５のマトリクス５０には、算術論理演算用のエレメント、遅延用のエレメント、メモリ用のエレメント、データを入力または出力するためにアドレスを発生させるエレメント、データの入力または出力用のエレメントなど、特定の機能あるいは処理に適した内部構成のエレメントが配置されている。ある程度の機能グループに分けたエレメントを配置することにより冗長性が減少し、ＡＣ特性および処理速度が向上できる。
【００６７】
ＤＡＰＤＮＡのマトリクス５０は、具体的には、３６８個のＰＥ５５を備えており、プロセッサ５１をプログラム制御することにより、プロセッサ５１から、またはメモリ５２から、制御バス１６を介して、各ＰＥ５５に対してコンフィグレーションデータが供給される。このコンフィグレーションデータにより、各々のＰＥ５５の機能と、配線群５７の接続とが制御され、マトリクス５０の内部に、種々のデータフロー（データパス）を自由に構成できる。したがって、マトリクス５０は、ＰＥ５５を含む回路構成をプログラムにより変更できる。
【００６８】
集積回路装置１５は、マトリクス５０と、外部メモリ２５などの外界とを接続し、処理対象のデータを入出力するために、入力バッファ１８と、出力バッファ１９と、アクセス調停ユニットとして機能するバススイッチングユニット（バスインターフェイス、ＢＳＵ）１７とを備えている。バッファ１８および１９は４つのバッファエレメントをそれぞれ備え、マトリクス５０に構成された回路に対して入出力されるデータを管理する機能を備えている。
【００６９】
図１３は、ＰＥ５５の一例である。このＰＥは、算術演算および論理演算に適した構成の演算用のＰＥである。ＰＥ５５は、機能を変更可能な内部データパス領域５５ｂと、その内部データパス領域５５ｂの機能を設定する制御ユニット５５ａとを備えている。内部データパス部５５ｂは、配線５７から所望の入力データを抽出するためのシフト回路ＳＨＩＦＴおよびマスク回路ＭＡＳＫと、入力データｄｉｘおよびｄｉｙをクロック信号によりラッチするための入力レジスタ（ＦＦ）と、論理演算ユニットＡＬＵと、配線５７に出力する出力データｄｏをクロック信号によりラッチするための出力レジスタ（ＦＦ）とを備えている。
【００７０】
各ＰＥの制御ユニット５５ａは、プロセッサ５１から制御バス１６を介してコンフィグレーションデータを受信し、内部データパス部５５ｂの構成を制御する。したがって、ＰＥ５５においては、制御ユニット５５ａにより、シフト回路ＳＨＩＦＴ、マスク回路ＭＡＳＫ、論理演算ユニットＡＬＵの状態が設定され、各種の算術演算および論理演算を行うことができる。また、各々のＰＥ５５は、入力データをクロック信号でラッチ（セット）するための入力レジスタと、出力データをクロック信号でラッチ（セット）するための出力レジスタとを備えている。このため、ＰＥ５５における処理の内容が確定すると、入力されたデータが演算されて出力されるまでのレイテンシが確定する。したがって、複数のＰＥ５５を配線５７により接続することによりパイプライン化された回路を簡単に構成することができ、スループットの大きな回路を提供できる。
【００７１】
図１４に、演算ユニット（マトリクス）５０に再構成された回路の概要を示している。経路探索のためのデータを初期入力するための回路６１は、４×４のネットワーク行列ＭＮの１行を３２ビットで表現し、それを４並列のデータＡ１〜Ａ４として入力する。図１５に示すように、１行３２ビットのデータを８ビット×４に分割し、４つの行成分を表す。また、８ビットのうち、先頭の１ビットは最短経路が確定したか否かの確定フラグとして使用する。この確定フラグは、経路行列ＭＲを示す。したがって、４並列のデータＡ１〜Ａ４は、ネットワーク行列ＭＮの情報と、経路行列ＭＲの情報とを含み、演算ユニット５０における経路探索は、これらのデータＡ１〜Ａ４により制御することができる。また、探索対象外のデータを示す無限大の値は、１６進数「７Ｆ」で表現される。さらに、確定フラグが付されているノードを基端とするリンク、すなわち、そのノードの行が探索対象となる。
【００７２】
図１６に、図２（ｂ）に示した、ノードＡを始点ノードした経路探索を行なうためのネットワーク行列ＭＮを、演算ユニット５０へ入力する形式に変換する様子を示している。以降では、ノードＡを始点ノードとして経路探索を行なうためのデータＡ１〜Ａ４からなるデータセットをデータＡとして示す。したがって、第１の機能１１の初期入力を繰り返す機能１２は、データＡについては、ノードＡを示すデータＡ１の先頭の確定フラグを「１」にセットし、ノードＡを始点ノードとして初期入力するための回路６１にセットする。このため、初期入力の段階では、データＡ１〜Ａ４の全てが演算ユニット５０に供給されるが、最初に経路探索に使用されるのはデータＡ１のみとなる。
【００７３】
図１４に示した、経路探索のためのデータを再入力するための回路６２は、初期入力のための回路６１からのデータ（初期データ）と、継続探索のために演算ユニット５０の出力からフィードバックされたデータ（再入力データ）とを切り換えて次の回路６３に供給する。再入力データは、いずれかのノードを示すデータの先頭の確定フラグが到達ノードとして新たに「１」にセットされており、その到達ノードを基端とするリンクのコストが、新たな探索対象のリンクコストに含まれる。本例であれば、最初にデータＡ１のみが経路探索に使用され、次の回路６３〜６６の経路探索のための処理対象となる。次のループではデータＡ１およびＡ３が処理対象となり、次のループではデータＡ１、Ａ２およびＡ３が処理対象となり、最後にデータＡ１〜Ａ４が処理対象となる。
【００７４】
最小値を検出するための回路６３では、データＡ１〜Ａ４のうちの処理対象のデータについて、ノックアウト方式で最小値を検出する。減算のための回路６４では、データＡ１〜Ａ４のうちの処理対象のデータについて、検出された最小値を減算する。コストが無限大（「７Ｆ」）については演算しない。到達ノードを判断するための回路６５においては、コストがゼロになったノードに対応する確定フラグに「１」をセットする。
【００７５】
継続探索のためのデータを生成するための回路６６においては、確定フラグに「１」がセットされたノードを先端とするリンク、すなわち、到達フラグの列のリンクコストを全て探索対象外の無限大にセットし、それ以外のリンクについては、減算後のコストを含むデータＡ１〜Ａ４（新データＡ１〜Ａ４）を出力する。これらの新データＡ１〜Ａ４は、再入力回路６２に供給され、適当なタイミングで再び、最小値を検出する回路６３に供給される。所定の回数だけ処理を繰り返し、全てのリンクコストが無限大になったデータは、メモリ５２に回収される。このデータの確定フラグが最短経路を示す経路行列ＭＲとして使用される。初期入力する回路６１と、再入力する回路６２との機能はソフトウェアで実現することも可能である。例えば、再入力を生成する回路６６から出力された回路をいったんメモリ５２に格納し、パイプラインを破綻させない適当なタイミングで再入力しても良い。あるいは、再構成可能な演算ユニット５０が他の機能とタイムシェアリングして使用されている状況であれば、他の機能の実行を阻害しないタイミングで、経路探索用の回路を再構成し、再入力データを入力することにより経路探索を続けることができる。
【００７６】
演算ユニット５０においては、多数の演算エレメントＰＥ５５が用意されており、これらにより複数のデータを並列に処理する回路を構成できる。本明細書においては、４×４の行列を利用して説明しているが、現在のＤＡＰＤＮＡは入力データ単位が３２ビットであり、３２ビットを８ビット×４に分割し、この３２ビットデータを１６個入力することにより、８×８のネットワーク行列ＭＮに含まれるリンクコストについて並列処理を行う構成を採用した。また、ＤＡＰＤＮＡに搭載された各エレメントＰＥは、上述したように、クロック同期で動き、各ＰＥは入出力にクロック同期でデータをラッチするためのＦＦが配置されている。したがって、ＤＡＰＤＮＡには基本的にパイプライン動作する回路が構成され、上述した経路探索のための処理をパイプライン処理することが可能となる。
【００７７】
ダイクストラ法は、ある時点での計算において、それ以前の計算結果が影響を及ぼすため、ＤＡＰＤＮＡのような並列リコンフィギュラブルプロセッサに適したアルゴリズムとはいえない。さらに、ダイクストラ法をデータフローマシン上に実装する場合、ループ間の依存性のため、長いフィードバックループが必要になり処理のスループットが低下する．加えて、リストの探索に時間がかかるため、ダイクストラ法は並列データフローマシンに適した最短経路探索アルゴリズムであるといえない。
【００７８】
ダイクストラ法に対し、本発明に含まれる最短経路検索アルゴリズムは、１回の処理で、全枝について、最小ノード分の距離（コスト）だけ現在位置を進め、到達ノードを判断する。したがって、この最短経路探索アルゴリズムをＡＭＰＳＡ（Advanced-Multi-route Parallel Search Algorithm）と称することにする。本発明に含まれるアルゴリズムは、上述したように、１回の処理で始点から出る全枝について１コスト分だけ現在位置を進め、現在位置が最初に他のノードに達した経路が最短経路である方法であっても良い。このアルゴリズムをＭＰＳＡ（Multi-route Parallel Search Algorithm）と称することにする。ＭＰＳＡでは、現在位置がノードに達すると、そのノードから出ている枝についても現在位置を進め、全ノードに対して現在位置が達すると終了となる。
【００７９】
このＡＭＰＳＡおよびＭＰＳＡでは、処理の依存性を抑え、複数の経路について同時に探索が行うアルゴリズムであるため、並列処理が可能である。また、ＭＰＳＡは行列演算として表現することができる。また、後述するように、本行列計算アルゴリズムは広いネットワークサイズにもスケーラブルである。最小値を減算するタイプの、ＡＭＰＳＡをＤＡＰＤＮＡ上で実行した場合、実行クロック数は、始点ノードからもっとも遠いノードまでの経路のコストによらず、格子状メッシュトポロジの場合では、ノード数ｎに対して、全ノード探索した場合でもＯ（ｎ）となる。したがって、ＡＭＰＳＡは、ダイクストラ法と比較して、ノード数の増加に対して計算量の増加が極めて小さい。
【００８０】
ダイクストラ法の計算量は、ノード数ｎに対してＯ（ｎ２）であり、全ノードを検索すると計算量はＯ（ｎ３）となる。このため、ダイクストラ法では、ネットワークの規模が大きくなると、計算量が急速に増大し、多くのＣＰＵパワーとメモリが必要になる。また、最近では、回線容量や波長など複数の情報を考慮して最短経路を求める研究がなされているが、通常の逐次処理型プロセッサでは個別に最短経路を計算する必要があるため、大幅に計算時間が増加する。本発明に含まれるＡＭＰＳＡおよびＭＰＳＡと、並列リコンフィギュラブルプロセッサとの組合せは、上記の問題を解決できるものである。さらに、ルーティングテーブルを数分に一回あるいは、数十分に一回更新するようなスケジュールにおいて、並列リコンフィギュラブルプロセッサは、他のネットワーク処理、例えば、ＩＰアドレスの最長一致検索などにも有効であり、ハードウェア資源の有効活用という点でも適している。
【００８１】
さらに、本発明に含まれるＡＭＰＳＡおよびＭＰＳＡと、同期型の並列プロセッサとの組合せは、パイプライン処理による独立な計算を可能とする。すなわち、ＡＭＰＳＡおよびＭＰＳＡでは、同じネットワーク行列でも、始点ノードが異なると、独立した処理が可能であり、ＤＡＰＤＮＡではエレメント単位、さらには、１クロックサイクル単位で、データをパイプラインで処理できる。したがって、スループットが大きく、１始点の場合とほぼ同一計算時間で、ｎ始点の最短経路探索を行うことが可能となる。簡単に説明するために、図１７は、エレメント単位でパイプライン処理を行った場合を示している。ノードＡを始点とするデータセットＡに続いて、ノードＢを始点とするデータセットＢ、ノードＣを始点とするデータセットＣ、ノードＤを始点とするデータセットＤをパイプライン方式で計算できる。さらに、それに続いて、異なるネットワーク行列のノードＥを始点とするデータセットＥというように、複数のネットワークについて、最短経路探索を行なうことができる。データセットを構成するデータの組合せを変えなければ、データセットＡ、Ｂ、Ｃといった順番に特に意味はない。始点の異なるデータセットをランダムに演算ユニット５０に構成された回路に供給し、経路探索することができる。
【００８２】
さらに具体的には、ＤＡＰＤＮＡに８×８のネットワーク行列の最短経路探索を実行すると、回路構成にも依存するが、４８０クロック程度を消費する。通常、全点間について最短経路を探索すると、「４８０クロック×ノード数」かかる。しかしながら、パイプライン処理により、結果が連続的に出力されるので、８×８のネットワーク行列の全点間最短経路探索を行う、すなわち、全ノードを始点として、他の全てのノードに達する最短経路を探索するのに、計４８７（４８０＋８−１）クロックを費やすだけである。さらに、複数のネットワークについてもパイプラインで処理できるので、例えば、３グループのネットワークの全点間最短経路探索を計５０３（４８０＋８＋８＋８−１）クロックで終えることができる。
【００８３】
ネットワークのグループ数が増加した場合、入力されるネットワーク行列の数も増加する。もし、最短経路探索回路を通過するために必要な４８０クロック以上、連続的にネットワーク行列が入力される場合、すべての入力が終わるまで、最初のデータは２周目の探索に移ることができない。このような場合は、メモリに最初のデータを格納して、パイプラインを延長しても良いし、複数の演算ユニットをシリアルに接続してパイプラインを延長しても良い。また、複数の演算ユニットをパラレルに接続して並列度を上げても良い。
【００８４】
図１８に、第１のシステム１０において、最短経路探索を行なうアルゴリズムをフローチャートにより示している。ステップ７１において、探索対象のネットワーク行列ＭＮの始点ノードの行（ライン）を選択する。ステップ７２において、探索対象のラインに含まれるリンクコストの最小値を検出する。ステップ７３において、探索対象のラインに含まれるリンクコストから最小値を減算する。ステップ７４において、リンクコストがゼロになったリンクの先端のノードを到達ノードとする。ステップ７５において、到達ノードが先端のリンクのコスト、すなわち、到達ノードの列のコストを探索対象外とする（無限大とする）。ステップ７６において、全ノードに到達していれば、始点ノードから、他の全てのノードに対する最短経路の探索が終了する。全ノードに到達していなければ、ステップ７７において、探索対象であったリンクコストは減算後の値とし、さらに、到達ノードを基端とするリンク、すなわち、到達ノードのラインを、探索対象に追加して、ステップ７２に戻り、それらの探索対象のラインに含まれるリンクコストの最小値を検出する。
【００８５】
このように、第１のシステム１０における第１のプロセスは、ステップ７１から７７を含み、これらの内、少なくともステップ７２から７５を並列プロセッサにより並列処理することが望ましい。すなわち、最小値検出（ステップ７２）から、再探索用のリンクコストの出力（ステップ７５）までの処理７０を、並列プロセッサを用いて、各リンクコストに対し並列に行うことが可能である。そして、並列プロセッサを用いて、各リンクコストを並列に処理することにより、パイプライン処理が可能となり、大きなスループットを得ることができる。
【００８６】
図１１に戻って、第１のシステム１０と、中間の階層の機能（第２の機能）２１を含む第２のシステム２０は、ネットワーク行列ＭＮが与えられると、それに対して、最小コスト行列ＭＣを求めて上位の機能に提供する。最小コスト行列ＭＣの利用方法は種々であるが、その１つは、小規模のネットワークのノード間の最短コストを上位の階層に提供し、上位の階層でネットワークの再編成を可能とすることである。
【００８７】
第２のシステム２０は、第１のシステム１０に供給するネットワーク行列ＭＮと、第１のシステム１０から得られた経路行列ＭＲと、最短コスト行列ＭＣとを格納するためのメモリ２５を含む。第２の機能２１は、ネットワーク行列ＭＮと、経路行列ＭＲとから、ある始点ノードから他のノードに至る最短コストを計算するための機能２２と、ネットワーク行列に含まれる全てのノードを始点ノードとして、上記の処理を繰り返し、全てのノードから他のノードへ至る最短コストをエレメントとして含む最短コスト行列ＭＣを生成する機能２３とを含む。最短コスト行列ＭＣの生成方法については、図９を参照して説明した通りである。
【００８８】
図１９に、第２のシステム２０において、最短コスト行列ＭＣを得るプロセス（第２のプロセス）をフローチャートにより示している。ステップ９１において、始点ノードの指定も含めてネットワーク行列ＭＮを第１のシステム１０に供給する。第１のシステム１０は、第１のプロセスにより、始点ノードから各ノードに至る最短経路を探索し、経路行列ＭＲを生成する。ステップ９２において、第２のシステム２０は、第１のシステム１０から経路行列ＭＲを取得する。ステップ９３において、第２のシステム２０は、始点ノードから他のノードに至る最短コストを計算する。ステップ９４において、ネットワーク行列ＭＮに含まれる全てのノードを始点ノードとした経路行列ＭＲを得るまで、上記の処理を繰り返す。ステップ９５において、ネットワーク行列ＭＮに含まれる全てのノードを始点ノードとした経路行列ＭＲを得られると、ネットワーク行列ＭＮに含まれる各ノードから他の各ノードへ至る最短コストを含む最短コスト行列ＭＣを生成する。
【００８９】
なお、図１９では、ループを含むフローチャートにより第２のプロセスを示しているが、異なる始点ノードのネットワーク行列ＭＮは、第１のシステム１０において独立処理できる。したがって、ステップ９１においては、経路行列ＭＲが取得できるのを待たずに、次々と異なるネットワーク行列ＭＮを第１のシステム１０に供給し、第１のシステム１０においてパイプライン処理ができるようにすることが望ましい。
【００９０】
図１１に戻って、第２のシステム２０と、上位階層の機能（第３の機能）３１を含む第３のシステム３０は、ルーティングプロトコル８３により収集されたネットワークの情報から生成された解析対象ネットワーク３９を、第２のシステム２０により最小コスト行列ＭＣが得られる規模のネットワーク（小規模ネットワーク）に分解し、階層化することにより大規模なネットワークの最短経路探索を可能とする。第３の機能３１は、大規模ネットワーク３９を複数のグループに分け、さらに階層化することにより、大規模ネットワークを小規模ネットワークの組み合わせで表す機能３２と、それら小規模ネットワークのネットワーク行列ＭＮを生成する機能３３と、第２のシステム２０により、それらのネットワーク行列ＭＮをパイプライン処理することで、高速に最短コスト行列ＭＣを求める機能３４とを含む。
【００９１】
図２０にグループ化と階層化について模式的に示している。まず、ｎノードから構成されるネットワーク１１０を最大ｍノードずつのグループ１１１Ａ〜１１１Ｄに分割する。本例では、ＤＡＰＤＮＡで処理することを前提にしており、最大８ノードずつのグループに分解する。これらが最下層のネットワークのグループとなる。
【００９２】
グループ間を接続するノードを境界ノードＢｎと呼び、全グループ内の境界ノードＢｎを抽出する。抽出された境界ノードＢｎの数がｍよりも大きい場合は、再度グループ化を行う。これを繰り返すことにより、図２０に示すように、グループ化された小規模のネットワークの階層構造で、大きなネットワークを表すことが可能となる。上の階層のグループ１１２Ａおよび１１２Ｂは、下の階層のグループの境界ノードＢｎのみで構成され、下の層が抽象化して表される。そして、境界ノードＢｎの数がｍ以下になると、それらにより最上層のグループ１１３Ａが形成され、最終的に、このグループ１１３Ａのネットワーク行列の最短経路を求めることにより、大規模ネットワークの最短経路を求めることができる。
【００９３】
ｎノードから構成される大規模ネットワークをｍノードから構成される小規模ネットワークに分割して処理することは、ネットワークの接続の局所性を利用して、計算量を減らす点でも有用である。すなわち、ｎノードから構成される大規模ネットワークのネットワーク行列は、ｎ×ｎのエレメントを含む。しかしながら、１つのノードがｎ個のノードに接続していることはないので、エレメントのほとんどのコストは、接続されていないことを示す無限大になる。これに対し、小規模ネットワークに分割することにより、局所的なノード同士のリンクが効率的に、ネットワーク行列に反映され、データ量も低減される。したがって、最短経路の探索に要するハードウェアの規模が縮小されると共に、処理時間も短縮できる。
【００９４】
図２１に、説明を簡単にするために、８ノードのネットワークＡ０を４ノードずつのグループＡ１およびＢ１に分割し、それらの境界ノードによりグループＡ２を生成した例を示している。この例では、ネットワークが２階層で表現されている。
【００９５】
ここで、グループＡ１に属するノードａ１１を起点ノードとし、グループＢ１に属するノードｂ１４を目的地ノードとする最短経路を求める場合を考える。図２２に示すように、以下のように処理を進めることができる。
【００９６】
Ｓ１．最下層のグループＡ１のネットワーク行列を生成し、第２のシステム２０に供給して、グループＡ１の最短コスト行列Ａ１ｃを得る（図２２（ａ））。
【００９７】
Ｓ２．最下層のグループＢ１のネットワーク行列を生成し、第２のシステム２０に供給して、グループＢ１の最短コスト行列Ｂ１ｃを得る（図２２（ｂ））。
【００９８】
Ｓ３．次に、グループＡ１とグループＢ１とを接続するための境界ノードａ２２、ａ２３およびａ２４を含む上位層のグループＡ２のネットワーク行列を生成する（図２２（ｃ））。グループＡ２に含まれる境界ノードａ２３と境界ノードａ２４間のリンクコストｚ９（ｚ１２）は、先に求めたグループＢ１の最短コスト行列に含まれるノードｂ１１からノードｂ１２に至る経路の最短コストｙ１（ｙ４）となる。境界ノードａ２２と境界ノードａ２３間のリンクコストｚ５および境界ノードａ２２と境界ノードａ２４間のリンクコストｚ６は、解析対象であるオリジナルのネットワークＡ０の情報として与えられている。
【００９９】
Ｓ４．このネットワーク行列を第２のシステム２０に供給することにより、上位層のグループＡ２の最短コスト行列Ａ２ｃを得る（図２２（ｄ））。
【０１００】
Ｓ５．グループＡ２の最短コスト行列Ａ２ｃより、目的地ノードｂ１４を含むグループＢ１に含まれる境界ノードａ２３（ｂ１１）および境界ノードａ２４（ｂ１２）について、グループＡ１に含まれる境界ノードａ２２（ａ１３）までの最短コストｗ５およびｗ６を加算するための行列Ａ２ｃ´を生成する（図２２（ｅ））。起点ノードａ１１を含むグループＡ１の最短コスト行列Ａ１ｃより、グループＡ１に含まれる境界ノードａ１３（ａ２２）から起点ノードａ１１までの最短コストｘ２を加算するための行列Ａ１ｃ´を生成する（図２２（ｆ））。
【０１０１】
Ｓ６．グループＢ１の最短コスト行列Ｂ１ｃに、行列Ａ２ｃ´および行列Ａ１ｃ´を加算する。これにより、境界ノードａ２２、ａ２３およびａ２４を介して、起点ノードａ１３からグループＢ１に含まれる各ノードまで経路の各々についてのコストを含むコスト行列Ａ０ｃが生成される（図２２（ｇ））。
【０１０２】
Ｓ７．目的地ノードｂ１４については、境界ノードａ２３（ｂ１１）を経由した経路のコスト（ｙ３＋ｗ５＋ｘ２）と、境界ノードａ２４（ｂ１２）を経由した経路のコスト（ｙ６＋ｗ６＋ｘ２）とが比較され、最小のコストの経路が起点ノードａ１１から目的地ノードｂ１４に至る最短経路として選択される。同様に、ノードｂ１３を目的地ノードとした最短経路も、コスト行列Ａ０ｃに含まれる境界ノードａ２３（ｂ１１）を経由した経路のコスト（ｙ２＋ｗ５＋ｘ２）と、境界ノードａ２４（ｂ１２）を経由した経路のコスト（ｙ５＋ｗ６＋ｘ２）とを比較することにより決定できる。
【０１０３】
図２３に、第３のシステム３０における処理（第３のプロセス）をフローチャートにより示している。先ず、境界ノードによるネットワークを生成する機能３２により大規模ネットワークを階層化して小規模ネットワークを生成する。ステップ１２１において、解析対象ネットワーク３９を、１つのネットワークが最大ｍ個のノードを含む最下層の複数のネットワーク（ノードのグループ）に分解する。ステップ１２２において、最下位層の複数のネットワークの少なくとも２つのネットワークを接続するための境界ノードによる上位層のネットワークを生成する。ステップ１２３において、その上位層に含まれる境界ノードの全数が最大値ｍ以下であれば、階層化を終了する。ステップ１２３において、境界ノードの数が最大値ｍより多ければ、ステップ１２４において、さらにグループ化し、境界ノードによる上位層のネットワークを生成する。ステップ１２２から１２４を繰り返すことにより、下位層の複数のネットワークの少なくとも２つのネットワークを接続するための境界ノードを最大ｍ個含む上位層のネットワークを生成することができる。大規模ネットワークを小規模ネットワークに階層化したデータは、階層化データ３８として保存される。
【０１０４】
次に、ネットワーク行列を生成する機能３３と、最短コスト行列を取得する機能３４により、最下位の小規模ネットワークから順番に最短経路を求め、大規模ネットワークの最短経路を求める。まず、ステップ１２５において、最下層の複数のネットワークの各々についてネットワーク行列ＭＮを生成する。ステップ１２６において、それぞれのネットワーク行列を第２のシステム２０に供給して、最短コスト行列ＭＣを取得する。ステップ１２７において、最上層の最短コスト行列ＭＣが求められれば、処理対象ネットワーク３９について最短コスト行列ＭＣを求める作業は終了する。
【０１０５】
したがって、ステップ１２９において、処理対象ネットワーク３９に含まれる各ノードを目的地ノードとして最短経路を求め、ルーティングテーブル８１を更新する。各ノードを目的地ノードとして最短経路を求める方法の一つは上述したものである。すなわち、上位層のネットワークに含まれる複数の境界ノードを介して起点ノードから目的地ノードに至る複数の経路の各々について、最下層の複数のネットワークの中の起点ノードを含むネットワークにおける起点ノードから境界ノードに至る最短コスト、上位層のネットワークに含まれる境界ノード間の最短コスト、および最下層の複数のネットワークの中の目的地ノードを含むネットワークにおける境界ノードから目的地ノードまでの最短コストの和を求める。そして、最短コストの和が最小の経路を起点ノードから目的地ノードまでの最短経路として採用する。
【０１０６】
一方、上位層のネットワークが存在する場合は、ステップ１２８において、最短コスト行列ＭＣに含まれる、上位層のネットワークを生成するための境界ノード間のリンクコストを抽出し、上位層のネットワークのネットワーク行列ＭＮを生成する。
【０１０７】
ネットワーク行列ＭＮが生成されると、ステップ１２６において、第２のシステム２０に供給し、最短コスト行列ＭＣを取得する。すなわち、上位層のネットワークについて、各々の境界ノードを始点ノードとして、第２のシステム２０（第２のプロセス）により、各境界ノードから他の各境界ノードに至る最短コストを得る。
【０１０８】
各ノードを目的地ノードとして最短経路を求める他の方法の１つは、ステップ１２８において、上位層のネットワークのネットワーク行列ＭＮを生成する際に、下位層のネットワークの情報を含める（畳み込む）ことである。例えば、上位層の境界ノード間のリンクコストとして、他の境界ノードとの最短コストに加え、起点ノードに関連する境界ノードは起点ノードに至る最短コストを含め、また、目的地ノードに関連する境界ノードには、目的地ノードに至る最短コストを含めて、目的地ノード毎に異なる上位層のネットワーク行列を生成することが可能である。この方法では、最上層のネットワーク行列の最短コストを求めることにより、あるいは、起点ノードに関連する境界ノードと目的地ノードに関連する境界ノードとが含まれる上位層のネットワーク行列の最短コストを求めることにより、起点ノードから目的地ノードまでの最短経路を決定することが可能となる。
【０１０９】
通常のシーケンシャルプロセッサでｎ始点の最短経路探索を行うと、１始点に要する計算時間のｎ倍の計算時間が必要になる。一方、本発明に含まれるアルゴリズムによりＤＡＰＤＮＡを用いて計算すると、パイプライン処理が可能なので、始点が１ノードでもｎノードでも計算時間はほとんど増加しない。基本的には、ｎノードの増加は、ｎクロックの処理時間の増加で処理できる。１グループあたり８ノードとして演算回路を設計した場合、１グループのノード数は計算量にほとんど依存しない。１グループの平均境界ノード数を２とすると、ｎノードのネットワークのグループ数Ｓは、図２４に示す式で与えられる。１始点の場合に必要な計算クロック数をａとすると、ｎ始点の計算クロック数は、通常の逐次処理型プロセッサではｎ×ａであるのに対し、並列処理プロセッサを用いた提案アルゴリズムでは（ａ＋８Ｓ−１）で計算可能である。その差は、図２５に示すように顕著であり、本発明に含まれる最短経路の探索方法は、ノードの数が多いほど効果的であることが分かる。
【図面の簡単な説明】
【０１１０】
【図１】ダイクストラ法の概要を説明するための図。
【図２】本発明に含まれる最短経路探索方法を説明するための図であって、図２（ａ）はノードＡを始点ノードとするネットワーク構成、図２（ｂ）はネットワーク行列、図２（ｃ）は経路行列を示す。
【図３】図２に続き、図３（ａ）はノードＣに到達した状態のネットワーク、図３（ｂ）はネットワーク行列、図３（ｃ）は経路行列を示す。
【図４】図３に続き、図４（ａ）は次のノードを探索する状態のネットワーク、図４（ｂ）はネットワーク行列、図４（ｃ）は経路行列を示す。
【図５】図４に続き、図５（ａ）はノードＢに到達した状態のネットワーク、図５（ｂ）はネットワーク行列、図５（ｃ）は経路行列を示す。
【図６】図５に続き、図６（ａ）は次のノードを探索する状態のネットワーク、図６（ｂ）はネットワーク行列、図６（ｃ）は経路行列を示す。
【図７】図６に続き、図７（ａ）はノードＤに到達した状態のネットワーク、図７（ｂ）はネットワーク行列、図７（ｃ）は経路行列を示す。
【図８】図７に続き、図８（ａ）は探索が終了した状態のネットワーク、図８（ｂ）はネットワーク行列、図８（ｃ）は経路行列を示す。
【図９】最短コスト行列を求める様子を示す。
【図１０】異なるネットワークの例であり、図１０（ａ）はネットワーク構成、図１０（ｂ）はネットワーク行列、図１０（ｃ）は経路行列を示す。
【図１１】ルータの概略構成を示す。
【図１２】再構成可能なプロセッサの概略構成を示す。
【図１３】図１２に示すプロセッサに含まれるＰＥの概略構成を示す。
【図１４】図１２に示すプロセッサに回路が構成された状態を示す。
【図１５】ネットワーク行列を入力するためのデータフォーマットを示す。
【図１６】ネットワーク行列を入力するためのデータへ変換する様子を示す。
【図１７】図１２に示すプロセッサにおいてパイプライン処理が行われる様子を示す。
【図１８】第１のシステムのプロセスを示すフローチャート。
【図１９】第２のシステムのプロセスを示すフローチャート。
【図２０】ネットワークを階層化する様子を示す。
【図２１】説明のために簡易に示した階層構造を示す。
【図２２】図２１に示す階層化したネットワークにおいて、最短経路を求める様子を示す。
【図２３】第３のシステムのプロセスを示すフローチャート。
【図２４】階層化により生成されるグループ数を示す。
【図２５】性能評価を示すグラフ（横軸はノードの数を示し、縦軸は計算時間（サイクル）を示す）。
【符号の説明】
【０１１１】
１０  第１のシステム、  ２０  第２のシステム、  ３０  第３のシステム
５０  演算ユニット
１００  ルータ
【図１】
0004734539.tif 000002
【図２】
0004734539.tif 000003
【図３】
0004734539.tif 000004
【図４】
0004734539.tif 000005
【図５】
0004734539.tif 000006
【図６】
0004734539.tif 000007
【図７】
0004734539.tif 000008
【図８】
0004734539.tif 000009
【図９】
0004734539.tif 000010
【図１０】
0004734539.tif 000011
【図１１】
0004734539.tif 000012
【図１２】
0004734539.tif 000013
【図１３】
0004734539.tif 000014
【図１４】
0004734539.tif 000015
【図１５】
0004734539.tif 000016
【図１６】
0004734539.tif 000017
【図１７】
0004734539.tif 000018
【図１８】
0004734539.tif 000019
【図１９】
0004734539.tif 000020
【図２０】
0004734539.tif 000021
【図２１】
0004734539.tif 000022
【図２２】
0004734539.tif 000023
【図２３】
0004734539.tif 000024
【図２４】
0004734539.tif 000025
【図２５】
0004734539.tif 000026