ネットワークに含まれるノード間の経路を探索するためのシステムおよび方法

【課題】処理時間の短い経路探索システムを提供する。
【解決手段】再構成可能なデバイス１のＰＥマトリクス１０に仮想ネットワーク３５を構成し、経路探索を行うシステム３０を提供する。システム３０は、ネットワークの情報８９に基づきＰＥマトリクス１０に仮想ネットワーク３５を構成するユニット３１と、仮想宛先ノードブロックに到着した探索パケットの経過情報により、ソースノードから宛先ノードに至る複数の経路を得て、それらの経路から所定の条件に合致する経路を選択する経路選択ユニット３２とを有する。仮想ネットワーク構成ユニット３１は、ＰＥにより、複数の仮想ノードブロックを構成し、接続マトリクスにより、複数の仮想リンクを構成する。ソースノードに対応する仮想ソースノードブロックは、それに繋がった全ての仮想リンクに探索パケットを送信する。仮想ノードブロックは、受信した探索パケットに、経過情報を追加し送信する。

【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークにおける種々の経路探索、特に、ディスジョイントな経路の探索に関するものである。
【背景技術】
【０００２】
インターネットの爆発的な発展と普及とに伴い、仕事および日常生活においてコンピュータネットワークが頻繁に利用されるようになっている。コンピュータネットワークではルーティングプロトコルによって交換される情報に基づいてルーティングテーブルが作成され、そのルーティングテーブルに従いパケットが配送される。代表的なルーティングプロトコルとしては、単一の自律システム（ＡＳ（Autonomous System））内で用いられるＯＳＰＦ（Open Shortest Path First）、ＲＩＰ（Routing Information Protocol）、ＳＩ−ＳＩ（Intermediate System to Intermediate System）がある。また、Ｐ２Ｐおよび無線（ワイヤレス）端末によるネットワーク（マルチホップ無線ネットワーク、アドホックネットワーク（Ad hoc network））用として提唱されているＤＳＲ（Dynamic Source Routing）プロトコルがある。さらに、異なるＡＳ間のルーティングプロトコルであるＢＧＰ（Border Gateway Protocol）がある。
【特許文献１】特開２００７−１５９０９９号公報
【特許文献２】特開２００６−２８５３８６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
これらのルーティングプロトコルは、基本的には、ノード（典型的にはルータ）間の情報の交換により、ソース（ソースノード）から目的ノード（宛先ノード）までのネットワークの情報（ネットワークトポロジ）を取得する機能と、取得されたネットワークの情報に基づき適当なアルゴリズムにより、ソースノードと宛先ノードとの間の適当な経路を決定する機能を備えている。たとえば、ＯＳＰＦでは、ネットワーク・トポロジーのデータベースを構築し、ダイクストラ法と呼ばれる最短経路探索アルゴリズムを用いて、ルーティングテーブルが作成される。最短経路の探索には、ホップ数だけではなく、経路のコスト、帯域幅、遅延などを含めた要素（ルーティングメトリック（routing metric））も考慮することが望ましい。
【０００４】
インターネットに代表されるＩＰネットワークにおけるパケットのルーティングは、通過するルータにおいて、そのルータが保持するルーティングテーブルを参照することで行われる。ルーティングテーブルには、宛先ネットワークアドレスと対応するＮＨＲ（Next Hop Router（ネクストホップ））が記録され、各パケットの宛先アドレスと最長一致するネットワークアドレスに対応したＮＨＲへパケットが転送される。それぞれのルータにおいて、以上の動作を繰り返すことで、宛先までパケットが転送される。
【０００５】
今後、インターネットの更なる普及とともにネットワークの規模が拡大すると、経路探索処理の負担が増大すると考えられる。また、ノードの状態の変化により、新たな経路を探索する機会も増加する。典型的には、モバイルの端末がインターネットに参加することにより、ルーティングテーブルをさらに頻繁に更新することが要求される可能性がある。
【０００６】
さらに、近年、光ネットワークにおいては、リンクコストとして、リンクの速度だけでなく、波長予約の成功率など複数の要因を考慮することが提案されている。また、リンクコストは、そのリンクを使用しているユーザ数、リンクを経由するデータ種類などの要因により変動するため、それらの要因の変動も考慮してルーティングテーブルが更新されることが望ましい。したがって、経路探索を行い、ルーティングテーブルを更新する頻度はさらに増大するものと考えられる。
【０００７】
特許文献１には、複数のノードを含むアドホックネットワークにおいて、あるモバイルノードから、モバイルノードにサービスを提供することのできる複数のサービスノードへのディスジョイントなルートを発見する方法が記載されている。その方法は、モバイルノードからルート要求を送信するステップと、ネットワークのノードによりルート要求を配信するステップと、あるルート要求があるサービスノードへ到達すると、モバイルノードからサービスノードへのルート要求のトレースを含んだルート応答を返却するステップと、モバイルノードが受信したルート応答に基づいてディスジョイントなルートを決定するステップと、モバイルノードが受信したルート応答が、十分な数のディスジョイントなルートに対応していない場合に、インクリメントされたパス拡張パラメータを有する新たなルート要求を発行するステップとを含む。
【０００８】
あるモバイルルートから、インターネットと接続するためのサービスノード（ゲートウェイノード）へのディスジョイントな経路を発見することが記載されている。アドホックネットワークをインターネットへ接続する際に、通信の信頼性を向上するために、現在通信しているゲートウェイへのルートが切断されると、別のゲートウェイへの高速マルチホップを実行することが記載されている。そのような事態に対応するように、常に複数のルートを確保するためには、ルート探索のプロセスを頻繁に行う必要があり、ルート探索に要する処理時間も短縮する必要がある。
【０００９】
特許文献２には、複数種類のプロセッシングエレメント（ＰＥ）の機能およびそれらの接続を変えて種々のデータパスを動的に再構成するタイプの集積回路装置が記載されている。
【課題を解決するための手段】
【００１０】
本発明の一態様は、複数のノードと、それらを接続する複数のリンクとを含むネットワークにおいて、ソースノードから、１または複数の宛先ノードへ至る経路を探索するためのシステムである。このシステムは、再構成ユニットと、再構成ユニットに仮想ネットワークを構成するユニットとを有する。再構成ユニットは、複数のプロセッシングエレメントと、複数のプロセッシングエレメントの接続を動的に変更可能な接続マトリクスとを含み、動的に回路を再構成可能なユニットである。
【００１１】
仮想ネットワークを構成するユニットは、１または複数のルーティングプロトコルにより収集されたネットワークの情報に基づき、再構成ユニットに仮想ネットワークを構成する。さらに、仮想ネットワークを構成するユニットは、複数のプロセッシングエレメントにより、ネットワークに含まれる複数のノードにそれぞれ対応する複数の仮想ノードブロックを構成し、接続マトリクスにより、複数のリンクにそれぞれ対応する複数の仮想リンクを構成する。
【００１２】
仮想ネットワークを構成するユニットは、さらに、複数の仮想ノードブロックのうち、ソースノードに対応する仮想ソースノードブロックを、仮想ソースノードブロックに繋がった全ての仮想リンクに探索パケットを送信するように構成する。仮想ネットワークを構成するユニットは、さらに、複数の仮想ノードブロックのそれぞれを、受信した探索パケットに、受信した探索パケットの通過した仮想リンクおよび／または仮想ノードブロックの情報を含む経過情報を追加し、受信した探索パケットを複製した探索パケットを、受信した探索パケットの到来した仮想リンクを除き、それぞれの仮想ノードブロックに繋がった全ての仮想リンクに送信するように構成する。
【００１３】
当該システムは、さらに、複数の仮想ノードブロックのうち、宛先ノード（ディスティネーションノード）に対応する仮想宛先ノードブロック（仮想ディスティネーションノードブロック）に到着した複数の探索パケットの経過情報により、ソースノードから宛先ノードに至る複数の経路から所定の条件に合致する経路を選択する経路選択ユニットを有する。
【００１４】
仮想ネットワークを構成するユニットおよび／または経路選択ユニットは、再構成ユニットに構成される回路により実現しても良く、あるいは再構成ユニットを制御するためのＲＩＳＣなどのプロセッサにより実現しても良く、再構成ユニットを含むチップとは物理的に異なる外部のプロセッサにより実現しても良い。
【００１５】
このシステムにおいては、回路を動的に再構成できる再構成ユニットに、探索パケットを転送する機能を備えた仮想ネットワークを再構成する。再構成ユニットに構成される仮想ノードブロックは、探索パケットを所定の条件で複写および転送する機能を有すればよいので、それぞれの仮想ノードブロックを１つまたは少ない数のプロセッシングエレメント（ＰＥ）で実装できる。このため、適当な数のＰＥをハードウェア資源として備えた再構成ユニットに、経路探索の対象となるネットワーク（ターゲットネットワーク）に対応する仮想ネットワークを再構成できる。また、チップ化された再構成ユニットのハードウェア資源が不足する場合は、複数のチップを接続したり、ターゲットネットワークに対応する仮想ネットワークをマルチコンテキスト化して時分割で再構成ユニットに再構成することが可能である。
【００１６】
そして、再構成ユニットには回路を動的に再構成できるので、ルーティングプロトコルにより収集されたネットワーク（オリジナルのネットワークまたはターゲットのネットワーク）の情報が更新されると、それに基づき、再構成ユニットに更新された情報に基づく仮想ネットワークを再構成できる。
【００１７】
このシステムにおいては、再構成ユニットに仮想ネットワークを再構成できる。このため、ダイクストラ法などの多くの計算時間を必要とする経路探索方法を用いずに、仮想ネットワークに探索パケットを流すことにより経路探索を実行できる。再構成ユニットに構成される仮想ネットワークにおいては、探索パケットの転送は再構成ユニットの動作速度（クロック速度）で行われる。したがって、特許文献１に示したような方法に比較し、短時間で経路を発見できる。
【００１８】
さらに、このシステムにおいては、仮想ネットワークが構成された再構成ユニット内で探索パケットを処理できる。したがって、仮想宛先ノードに受信した探索パケットにより経路を選択でき、仮想ソースノードに応答を戻す必要はない。このため、オリジナルのネットワークに探索パケットを発信した場合において発生する、他のノードからのルート応答を待つ時間を省略できる。
【００１９】
経過情報は、通過した仮想リンクおよび／または仮想ノードブロックをビット位置で識別できるビットマップデータを含むことが望ましい。経路選択ユニットは、複数の経過情報のビットマップデータのビット単位の論理積を演算することにより、ソースノードから宛先ノードに至る複数の経路から、ディスジョイントな経路を選択することができる。
【００２０】
再構成ユニットの複数のプロセッシングエレメントは、遅延量を動的に設定できる複数の遅延エレメントを含むことが望ましい。仮想ネットワークを構成するユニットは、接続マトリクスと、複数の遅延エレメントとにより、複数の仮想リンクを構成することができる。それぞれの仮想リンクに含まれる遅延エレメントに、対応するリンクのコストに対応する遅延量を設定することにより、経路選択ユニットは、仮想宛先ノードブロックが受信したタイミングにより、探索パケットが通過した経路について、リンクコストも含めた情報を得ることができ、その情報を経路の選択に利用できる。
【００２１】
経路選択ユニットは、仮想宛先ノードブロックに到着した順番の早い複数の探索パケットの経過情報により、ソースノードから宛先ノードに至る複数の経路から所定の条件に合致する経路を選択することが好ましい。このシステムにおいては、仮想ネットワークに探索パケットを送信するので、仮想宛先ノードブロックに到着した順番（先に到着するタイミングは）、ターゲットのネットワークにおけるルートのホップ数、その他のメトリックが反映された情報である。したがって、その情報を利用して経路をフィルタリングできる。さらに、経路の選択に要する処理時間を短縮できる。
【００２２】
仮想ネットワークを構成するユニットは、それぞれの仮想ノードブロックを、それぞれの仮想ノードブロックに到着した順番の早いものから複数の探索パケットの複製のみを、受信した探索パケットの到来した仮想リンクを除き、それぞれの仮想ノードブロックに繋がった全ての仮想リンクに送信するように再構成することが望ましい。仮想宛先ノードブロックに到着する順番が早い探索パケットに絞って送信することができ、再構成ユニットにおける無用な資源の消費を防止できる。再構成ユニットにおいて、所定の数の探索パケットが通過した仮想ノードブロックを解放できるので、その仮想ノードブロックを構成しているＰＥを、次のネットワークにおける経路探索に用いたり、他のアプリケーションを処理するための回路に利用できる。
【００２３】
また、仮想ネットワークを構成するユニットは、さらに、それぞれの仮想ノードブロックを、通過した仮想リンクおよび／または仮想ノードブロックについての同じ情報を持つ探索パケットを廃棄するように構成することが望ましい。ループした経路を辿っている探索パケットを廃棄することにより、無用な探索パケットが仮想ノードブロック間で交換される事態を防止し、処理速度を高めたり、消費電力を削減したりできる可能性がある。
【００２４】
本発明の他の態様は、複数のノードと、それらを接続する複数のリンクとを含むネットワークにおいて、ソースノードから、１または複数の宛先ノードへ至る経路を、再構成ユニットを用いて探索する方法である。再構成ユニットは、複数のプロセッシングエレメントと、前記複数のプロセッシングエレメントの接続を動的に変更可能な接続マトリクスとを含み、動的に回路を再構成可能である。
【００２５】
当該方法は、以下のステップを含む。
１．１または複数のルーティングプロトコルにより収集されたネットワークの情報に基づき、複数のプロセッシングエレメントにより、ネットワークに含まれる複数のノードにそれぞれ対応する複数の仮想ノードブロックを構成し、接続マトリクスにより、複数のリンクにそれぞれ対応する複数の仮想リンクを構成し、再構成ユニットに仮想ネットワークを構成すること。
２．複数の仮想ノードブロックのうち、ソースノードに対応する仮想ソースノードブロックが、仮想ソースノードブロックに繋がった全ての仮想リンクに探索パケットを送信すること。
３．複数の仮想ノードブロックのそれぞれが、受信した探索パケットに、受信した探索パケットの通過した仮想リンクおよび／または仮想ノードブロックの情報を含む経過情報を追加し、受信した探索パケットを複製した探索パケットを、受信した探索パケットの到来した仮想リンクを除き、それぞれの仮想ノードブロックに繋がった全ての仮想リンクに送信すること。
４．複数の仮想ノードブロックのうち、宛先ノードに対応する仮想宛先ノードブロックに到着した複数の探索パケットの経過情報により、ソースノードから宛先ノードに至る複数の経路から所定の条件に合致する経路を選択すること。
【００２６】
経過情報は、通過した仮想リンクおよび／または仮想ノードブロックをビット位置で識別できるビットマップデータを含み、経路を選択すること（ステップ４）は、複数の経過情報のビットマップデータのビット単位の論理積を演算することにより、ソースノードから宛先ノードに至る複数の経路から、ディスジョイントな経路を選択することを含む。
【００２７】
複数のプロセッシングエレメントは、遅延量を動的に設定できる複数の遅延エレメントを含み、仮想ネットワークを構成すること（ステップ１）は、接続マトリクスと、複数の遅延エレメントとにより、複数の仮想リンクを構成し、それぞれの仮想リンクに含まれる遅延エレメントには、対応するリンクのコストに対応する遅延量を設定することを含む。
【００２８】
経路を選択すること（ステップ４）は、仮想宛先ノードブロックに到着した順番の早いものから複数の探索パケットの前記経過情報により、ソースノードから宛先ノードに至る複数の経路から所定の条件に合致する経路を選択することを含む。
【００２９】
それぞれの仮想ノードブロックに繋がった全ての仮想リンクに送信すること（ステップ３）は、それぞれの仮想ノードブロックが、それぞれの仮想ノードブロックに到着した順番の早いものから複数の探索パケットの複製のみを、受信した探索パケットの到来した仮想リンクを除き、それぞれの仮想ノードブロックに繋がった全ての仮想リンクに送信することを含む。
【００３０】
それぞれの仮想ノードブロックに繋がった全ての仮想リンクに送信すること（ステップ３）は、通過した仮想リンクおよび／または仮想ノードブロックについての同じ情報を持つ探索パケットを廃棄することを含む。
【発明を実施するための最良の形態】
【００３１】
図１に、経路探索を行うシステムの一例として、ルーティングテーブルを更新する機能を備えたルータの概要を示している。このルータ１００は、コンピュータネットワークの一つのノードを構成するデバイスであり、ＣＰＵ、メモリ、回路を再構成可能なプロセッサなどを含む適当なハードウェア資源と、それらを制御するための適当なソフトウェア資源とを備えている。ルータ１００は、有線または無線を含む適当な伝送経路により隣接するルータとの間でデータを交換可能なネットワークインターフェイス１０１と、このネットワークインターフェイス１０１を介して送受信するパケットデータ（パケット）を生成および解析する解析ユニット１０２と、パケットのＩＰヘッダーの情報に基づき、パケットを送出するネクストホップルータ（ネクストホップ）を選択する機能を備えたルーティングユニット８０とを含む。
【００３２】
ルーティングユニット８０の機能は、専用のモジュール、あるいは他の機能と共用のハードウェア資源、例えば、ＣＰＵあるいは再構成可能なプロセッサとソフトウェアにより提供される。ルーティングユニット８０は、ルーティングテーブル８１を参照してパケットを送出するネクストホップを選択する機能８２と、動的なルーティングテーブルの更新を可能とする適当なルーティングプロトコル、例えばＯＳＰＦにより、近隣のルータを含めたネットワークの情報、特に、ルーティングに関するネットワークの構成を示す情報を取得し、ルーティングテーブル８１を更新する機能８３とを含む。この更新する機能８３は、ルーティングプロトコルにより取得したネットワークの情報を解析対象のネットワークとし、そのネットワークの構成を示すネットワーク行列８９を生成する。
【００３３】
ＯＳＰＦのようなリンクステート型のルーティングアルゴリズムでは、ルータ間でリンク情報をＬＳＡ（Link-State Advertisement）で定期的に交換する。したがって、そのネットワークに属する各ノードはネットワーク中のすべてのリンク情報（コスト）を知っている。したがって、ネットワーク行列８９には、ＬＳＡにより得られたネットワーク内のリンクコスト情報を含めることができる。ネットワーク行列８９には、さらに、ＯＳＰＦとともに、あるいはＯＳＰＦに替えて、他のルーティングプロトコルにより取得されたネットワークの情報を含めることができる。この例では、ネットワーク行列８９には、ターゲットのネットワークに含まれる複数のノードと、複数のノードを接続する複数のリンクと、それぞれのリンクのコストとが含まれる。インターネットなどのコンピュータネットワークにおいて、ノード間のコスト（リンクコスト）を決定する典型的な要素は、通信速度の逆数である。その他に、光ネットワークにおいては波長予約の成功率、送信対象のデータ種別、ＱｏＳにより予約された帯域など複数の要因をリンクコストとして反映することができる。ネットワーク行列８９には、コスト以外の他の、経路の優劣を比較できる要素（ルーティングメトリック）を含めても良い。
【００３４】
図２（ａ）にネットワーク行列の一例を示している。このネットワーク行列ＭＮは、図２（ｂ）に示したネットワークＮに対応するものであり、ネットワークＮはノードＡ〜Ｆの６つのノードを含む。ネットワーク行列ＭＮは、ネットワークＮに含まれる各ノードを基端とし、基端のノードに繋がる他のノードを先端とする各リンクのコストをエレメントとして含む。無限大のエレメントは、ネットワーク行列ＭＮに含まれるノードであって、直接のルートでは繋がっていないノードを示す。ノードが未接続であることを示す値は無限大に限らない。
【００３５】
ルーティングユニット８０は、ルーティングプロトコルを用いて収集されたネットワークの情報（ネットワーク行列）８９に基づき、経路探索を行うシステム（経路探索システム）３０を含む。この経路探索システム３０は、内部に、回路を動的に再構成可能な領域（再構成ユニット）を備えたデバイス（再構成可能デバイス）１を含む。そして、経路探索システム３０は、ネットワーク行列８９に基づき、経路を発見しようとしているネットワーク（ターゲットのネットワーク）に対応するネットワーク構成を、経路探索を目的とした範囲で仮想的に再構成可能デバイス１に再構成し、経路探索を行う。
【００３６】
図３（ａ）に、再構成可能なデバイスの一例を示している。このデバイス１は、本願の出願人が開発したＤＡＰＤＮＡと称する半導体集積回路装置である。このデバイス１は、ＤＡＰと呼ばれるＲＩＳＣコアモジュール２と、ＤＮＡと呼ばれるダイナミックリコンフィグラブルデータフローアクセレレータ３とを含む。デバイス１は、ＤＡＰ２およびＤＮＡ３に加え、ＤＮＡ３のダイレクト入出力用のインターフェイス４と、ＰＣＩインターフェイス５と、ＳＤＲＡＭインターフェイス６と、ＤＭＡコントローラ７と、その他の周辺デバイス８と、これらを接続するための高速スイッチングバス（内部バス）９とを含む。ＤＡＰ２は、デバッグインターフェイス４２ａと、ＲＩＳＣコア４２ｂと、命令キャッシュ４２ｃと、データキャッシュ４２ｄとを含む。ＤＮＡ３は、３７６個のＰＥ（ＰＥｓ、処理エレメント）が２次元に配置されたＰＥマトリクス１０と、このＰＥマトリクス１０に含まれるＰＥｓの機能および／またはＰＥｓの接続を変えてＰＥマトリクス１０を再構成するためのコンフィグレーションデータ１８が格納されるコンフィグレーションメモリ１９とを含む。ＰＥ１０は、複数のプロセッシングエレメントＰＥ（ＰＥｓ）と、複数のＰＥの接続を動的に変更可能な接続マトリクスとを含み、動的に回路を再構成可能な再構成ユニットに相当する。ＰＥマトリクス１０に配置されるＰＥの数は、上記に限定されるものではない。
【００３７】
コンフィグレーションメモリ１９は、複数バンクの構成になっている。例えば、図３（ｂ）に示すように、ＰＥマトリクス１０には、フォアグラウンドバンクに格納されるコンフィグレーションデータ１８により第１の機能（データフロー、回路デザイン）１７ａが構成される。また、異なるバックグラウンドバンクにそれぞれ格納されるコンフィグレーションデータにより、第２の機能１７ｂおよび第３の機能１７ｃがそれぞれ構成される。メモリ１９のバンクを切り替えることにより、ＰＥマトリクス１０には、第１の機能１７ａに変わって第２の機能１７ｂまたは第３の機能１７ｃが再構成される。ＰＥマトリクス１０の再構成は、例えば、１サイクル（クロックサイクル）でダイナミックに行なわれる。
【００３８】
図３（ｃ）は、ＰＥマトリクス１０に回路を再構成する一例である。あるアプリケーション、例えば、ＭＰＥＧデコーダを複数の機能（サブファンクション）に時分割し、それらの機能を、ＰＥマトリクス１０に時分割で動的に再構成し、ＭＰＥＧデコーダの機能を専用回路（専用ハードウェア）で提供する。同様に、経路探索において、ターゲットのネットワークに含まれるノード数が膨大な場合は、ネットワークを複数のサブネットワークに分割し、それらのサブネットワークに対応する仮想ネットワークを時分割で動的に再構成することが可能である。したがって、このデバイス１を採用した経路探索システム３０は、大規模ネットワークに対しても適用できる。このような使用により、再構成可能なデータ処理装置であるデバイス１を用いて、多くのハードウエア資源を必要とするアプリケーションを、少ないハードウエア資源で実行できる。
【００３９】
図３（ｄ）は、ＰＥマトリクス１０に回路を構成する他の例の一つである。たとえば、再生方式が異なるアプリケーションを実行するために、複数の機能がそれぞれ実現されるようにＰＥマトリクス１０を再構成できる。同様に、ルータ１００において、デバイス１は、経路探索システム３０として機能させるだけではなく、ルーティングテーブル８１を参照してパケットを送出するネクストホップを選択する機能８２などとしても用いることができる。このような使用により、多くのアプリケーションを共通のハードウエア（デバイス）１を用いて実行できる。
【００４０】
このデバイス１は、さらに、プログラムレベル（命令レベル）ではなく、データフローレベル（データパスレベル、ハードウエアレベル）で多数の機能を切り換えて実装できる。このため、専用のハードウエアに匹敵する速度で処理を行うことができる。したがって、経路探索のための仮想ネットワークをＰＥマトリクス１０に再構成することにより、専用のハードウェアで構成したのに匹敵する処理速度を得ることができる。その一方で、ＰＥマトリクス１０は動的に再構成できるので、経路探索の対象となるネットワークの変動に対してもフレキシブルに、遅滞なく追従できる。
【００４１】
また、ＰＥマトリクス１０に含まれるＰＥｓは、クロックにより同期した処理を行うことが可能であり、パイプライン処理に適したデータフロー（データパス）をＰＥマトリクス１０に再構成できる。さらに、多数のＰＥｓにより並列処理を行う複数のデータフローを並列に再構成することも可能である。したがって、ＰＥマトリクス１０に仮想ネットワークを再構成し、経路探索用のパケット（探索パケット）を流すことにより、仮想ネットワーク内で、ターゲットのネットワークと同様に、複数の探索パケットを並列に送受信することが可能となる。さらに、探索パケットの送受信（流れ）が同期的に処理されるので、探索パケットが目的のノード（たとえば、宛先ノード）に到達したタイミングを、その探索パケットが通過した経路の質に関する情報として捉えて、経路を選択するための情報として利用することが可能となる。このように、ＰＥマトリクス１０に仮想ネットワークを回路として動的に再構成することにより、ハードウエアによる高速な処理速度と、ソフトウエアのような柔軟性とが融合された経路探索環境を提供できる。
【００４２】
図４に、ＰＥマトリクス１０を拡大して示している。ＰＥマトリクス１０は、縦横に２次元に配置された複数のプロセッシングエレメント（ＰＥ）４５と、それらの間に格子状に配置された配線４７と、配線４７の接続ポイントで縦横の配線４７の接続を自由に切り替えることができるスイッチングユニット４６とを備えている。配線４７およびスイッチングユニット４６が、複数のＰＥ４５の接続を自由に変えることができる接続マトリクス４４を構成する。接続マトリクス４４には、以下で説明する遅延用のＰＥなどの、接続環境を調整するためのＰＥが含まれていても良い。
【００４３】
再構成可能なＰＥマトリクス（回路領域）１０を構成するＰＥ４５の一例は、ルックアップテーブルなどにより自在に機能を設定可能なものである。この集積回路デバイス１のマトリクス１０には、算術論理演算用のエレメント、遅延用のエレメント、メモリ用のエレメント、データを入力または出力するためにアドレスを発生させるエレメント、データの入力または出力用のエレメントなど、特定の機能あるいは処理に適した内部構成のエレメントが配置されている。ある程度の機能グループに分けたエレメントを配置することにより冗長性が減少し、ＡＣ特性および処理速度が向上できる。
【００４４】
プロセッサ２から、またはコンフィグレーションメモリ１９から、制御バス９ａを介して、各ＰＥ４５に対してコンフィグレーションデータが供給される。このコンフィグレーションデータにより、各々のＰＥ４５の機能と、配線群４７の接続とが制御され、マトリクス１０の内部に、種々のデータフロー（データパス）を自由に構成できる。さらに、ＰＥマトリクス１０は、外部メモリインターフェイス６などの外界との接続のため、処理対象のデータを入出力する入力バッファ４８および出力バッファ４９と、アクセス調停ユニットとして機能するバススイッチングユニット（バスインターフェイス、ＢＳＵ）９ｂとを備えている。
【００４５】
図５は、ＰＥ４５の一例である。このＰＥは、算術演算および論理演算に適した構成の演算用である。ＰＥ４５は、機能を変更可能な内部データパス領域４５ｂと、その内部データパス領域４５ｂの機能を設定する制御ユニット４５ａとを備えている。内部データパス部４５ｂは、配線４７から所望の入力データを抽出するためのシフト回路ＳＨＩＦＴおよびマスク回路ＭＡＳＫと、入力データｄｉｘおよびｄｉｙをクロック信号によりラッチするための入力レジスタ（ＦＦ）と、論理演算ユニットＡＬＵと、配線４７に出力する出力データｄｏをクロック信号によりラッチするための出力レジスタ（ＦＦ）とを備えている。
【００４６】
各ＰＥの制御ユニット４５ａは、プロセッサ２から制御バス９ａを介してコンフィグレーションデータを受信し、内部データパス部４５ｂの構成を制御する。したがって、コンフィグレーションデータにより、１つ、または複数のＰＥ４５により、探索パケットを、所定の条件で転送するような機能を備えたノードを再構成できる。
【００４７】
図６は、ＰＥ４５の他の例の１つである。このＰＥは、データが伝送されるタイミングを遅延する処理に適したものである。この内部データパス部４５ｄは、複数のセレクタとフリップフロップの組み合わせで構成された遅延回路４５ｅと、入力側のフリップフロップ（ＦＦ）と、出力側のフリップフロップ（ＦＦ）と、回路を選択するセレクタ４５ｓとを備えている。遅延回路４５ｅは、コンフィグレーションデータにより、本例では０〜５クロックの遅延をセットできる。したがって、入力毎に１〜７クロックの遅延を制御できる。さらに、コンフィグレーション情報により、２つの入力系統（Ｘ系統およびＹ系統）を直列に接続することが可能であり、２倍の遅延時間を制御できる。また、これらのデータと共にキャリー信号用の行配線群および列配線群で導かれるキャリー信号ｃｉｘおよびｃｉｙも同様のデータパスにより遅延して出力される。
【００４８】
この遅延用のＰＥ４５を、仮想ネットワークの仮想ノード間を接続する仮想リンクに含めるようにＰＥマトリクス１０を再構成することが可能である。遅延用のＰＥ４５の遅延量はコンフィグレーションデータによりバリアブルに設定できるので、その遅延量により、リンクコストなどのリンクの優劣を決める要素を、探索パケットの遅延（転送時間の遅れ）として探索パケットの履歴（経過情報）に含めることができる。
【００４９】
図１に示すように、経路探索システム３０は、再構成ユニットであるＰＥマトリクス１０に仮想ネットワーク３５を構成する構成ユニット３１と、仮想ネットワークを用いて探索された経路から所定の条件に合致する経路を選択する経路選択ユニット３２とを含む。構成ユニット３１は、ルータ１００がサポートする１または複数のルーティングプロトコルにより収集されたネットワークの情報（ネットワーク行列）８９に基づき、ＰＥマトリクス１０に仮想ネットワーク３５を再構成する。経路選択ユニットは、仮想ネットワーク３５に含める複数の仮想ノードブロックのうち、宛先ノード（ディスティネーションノード）に対応する仮想宛先ノードブロックに到着した複数の探索パケットの経過情報により、ソースノードから宛先ノードに至る複数の経路から所定の条件に合致する経路を選択する。この例では、これらのユニット３１および３２としての機能は、ＤＡＰ２にロードされるプログラムにより提供されるようになっている。これらのユニット３１および３２は、ＰＥマトリクス１０に、仮想ネットワーク３５とともに、あるいは時分割で再構成しても良い。
【００５０】
図７に、経路探索の対象となるターゲットのネットワークの一例を示している。図８に、そのネットワークに対応するように、経路探索のためにＰＥマトリクス１０に再構成された仮想ネットワークの一例を示している。ターゲットのネットワーク２１はＮ１〜Ｎ１１の１１個のノードと、これらのノードを接続するＬ１〜Ｌ１３の１３個のリンクとを含む。仮想ネットワーク３５は、ノードＮ１〜Ｎ１１にそれぞれ対応する仮想ノードブロックＰＮ１〜ＰＮ１１と、リンクＬ１〜Ｌ１３にそれぞれ対応する仮想リンクＰＬ１〜ＰＬ１３を含む。仮想ノードブロックＰＮ１〜ＰＮ１１は、１または複数のＰＥ４５により構成され、仮想リンクＰＬ１〜ＰＬ１３は、ＰＥ４５を接続する接続マトリクス４４により構成される。仮想リンクＰＬ１〜ＰＬ１３には、配線４７およびスイッチングマトリクス４６だけではなく、遅延用のエレメントが含まれていても良い。なお、以下では、仮想ノードブロックおよび仮想リンクを一般的に示す場合は、仮想ノードブロックＰＮおよび仮想リンクＰＬとして参照する。
【００５１】
構成ユニット３１は、ネットワーク行列８９に基づいて、ＰＥマトリクス１０に仮想ネットワーク３５を再構成するためのコンフィグレーションデータ１８を生成し、そのコンフィグレーションデータ１８をＰＥマトリクス１０またはコンフィグレーションメモリに供給することにより仮想ネットワーク３５として機能する回路（データフロー、データパス）をＰＥマトリクス１０に再構成する。さらに、構成ユニット３１は、仮想ノードブロックＰＮ１〜ＰＮ１１のうち、ソースノードＮ１に対応する仮想ソースノードブロックＰＮ１が、仮想ソースノードブロックＰＮ１に繋がった全ての仮想リンク、この場合は仮想リンクＰＬ１およびＰＬ２に探索パケットＳＰを送信するようにコンフィグレーションデータ１８を生成し、仮想ソースノードブロックＰＮを再構成する。
【００５２】
また、構成ユニット３１は、複数の仮想ノードブロックＰＮ１〜ＰＮ１１のうち、仮想ソースノードブロックＮ１と、仮想宛先ノードブロックＮ８を除いたそれぞれの仮想ノードブロックＰＮを、受信した探索パケットＳＰに、受信した探索パケットＳＰの通過した仮想リンクおよび／または仮想ノードブロックの情報を含む経過情報を追加するようにコンフィグレーションデータ１８を生成し、それぞれの仮想ソースノードブロックＰＮを再構成する。構成ユニット３１は、さらに、受信した探索パケットＳＰを複製した探索パケットＳＰを、受信した探索パケットＳＰの到来した仮想リンクＰＬを除き、それぞれの仮想ノードブロックＰＮに繋がった全ての仮想リンクＰＬに送信するようにコンフィグレーションデータ１８を生成し、それぞれの仮想ソースノードブロックＰＮを再構成する。
【００５３】
構成ユニット３１は、さらに、それぞれの仮想ノードブロックＰＮを、それぞれの仮想ノードブロックＰＮに到着した順番の早いものから複数の探索パケットＳＰの複製のみを、受信した探索パケットの到来した仮想リンクＰＬを除き、それぞれの仮想ノードブロックＰＮに繋がった全ての仮想リンクＰＬに送信するようにコンフィグレーションデータ１８を生成し、仮想ソースノードブロックＰＮを再構成する。
【００５４】
構成ユニット３１は、さらに、それぞれの仮想ノードブロックＰＮを、通過した仮想リンクＰＬおよび／または仮想ノードブロックＰＮについての同じ情報を持つ探索パケットＳＰを廃棄するように構成するようにコンフィグレーションデータ１８を生成し、仮想ソースノードブロックＰＮを再構成する。
【００５５】
図９に、探索パケットＳＰの一例を示している。この探索パケットＳＰは、ヘッダー情報２４と、経過情報２５とを含む。経過情報２５は、探索パケットＳＰが通過した仮想リンクＰＬおよび／または仮想ノードブロックＰＮをビット位置で識別できるビットマップデータを含む。以下の例では、経過情報２５は、探索パケットＳＰが通過した仮想リンクＰＬをビット位置で識別できるビットマップデータとなっている。経過情報２５に、探索パケットＳＰが通過した仮想ノードブロックＰＮをビット位置で識別できるビットマップデータを含めることは、仮想リンクと同様に可能である。仮想宛先ノードブロックＰＮ８に到達した探索パケットＳＰの経過情報２５には、仮想ソースノードブロックＰＮ１から仮想宛先ノードブロックＰＮ８に到達するまでに探索パケットＳＰが通過した仮想リンクＰＬの情報が収められている。したがって、経路選択ユニット３２は、仮想宛先ノードブロックＰＮ８に到達した探索パケットＳＰの経過情報２５にアクセスすることにより仮想ソースノードＰＮ１から仮想宛先ノードブロックＰＮ８に至る経路を知ることができる。その経路は、ターゲットのネットワーク２１における経路に相当するものであり、所定の条件に合った経路を見つけることにより、ルーティングテーブル８１を更新できる。
【００５６】
探索される経路の典型的なものの１つは、ソースノードＮ１から宛先ノードＮ８に至る最短経路である。たとえば、仮想リンクＬ１〜Ｌ１３の遅延を一定にすることにより、最も早く仮想宛先ノードブロックＰＮ８に到達した探索パケットＳＰの経路を最小ホップ数の経路として選択できる。また、仮想リンクＬ１〜Ｌ１３の遅延をリンクコストに基づいて設定することにより、経路選択ユニット３２は、最も早く仮想宛先ノードブロックＰＮ８に到達した探索パケットＳＰの経路を最小コストの経路として選択できる。
【００５７】
探索される経路の典型的なものの異なる例は、ソースノードＮ１から宛先ノードＮ８に至るディスジョイントな経路である。経路選択ユニット３２は、仮想宛先ノードブロックＰＮ８に到達した複数の探索パケットＳＰの経過情報２５のビットマップデータのビット単位の論理積を演算することにより、ソースノードＮ１から宛先ノードＮ８に至る複数の経路から、ディスジョイントな経路を選択することができる。経過情報２５のビットマップデータのビット単位の論理積が全て０であれば、比較した経過情報２５に含まれる経路はディスジョイントな経路である。ビットマップ（ビット列）の比較は、ＰＥマトリクス１０に含まれる算術演算用のＰＥを用いることにより極めて短時間に処理できる。ＤＡＰ２によりソフトウェアでビットマップの比較を行っても良い。
【００５８】
さらに、仮想リンクＬ１〜Ｌ１３の遅延を一定にすることにより、仮想宛先ノードブロックＰＮ８に到達したタイミングにより、経路選択ユニット３２は、最小ホップ数のディスジョイントな経路を選択できる。仮想リンクＬ１〜Ｌ１３の遅延をリンクコストに基づいて設定することにより、経路選択ユニット３２は、仮想宛先ノードブロックＰＮ８に到達した探索パケットＳＰのタイミングにより、最小コストのディスジョイントな経路を選択できる。
【００５９】
図１０に、ソースノードから、１または複数の宛先ノードへ至る経路を、再構成ユニットであるＰＥマトリクス１０を用いて探索する方法の一例を示している。ステップ７１において、ルータ１００が提供する１または複数のルーティングプロトコルによりネットワークの情報８９を収集する。ステップ７２において、構成ユニット３１は、ネットワークの情報８９に基づき、ＰＥマトリクス１０に仮想ネットワーク３５を構成する。ステップ７３において、ソースノードＮ１に対応する仮想ソースノードブロックＰＮ１から、仮想ソースノードブロックＰＮ１に繋がった全ての仮想リンクＰＬ１およびＰＬ２に探索パケットＳＰを送信する。この段階の経過情報２５は、全てのビットが０である。
【００６０】
ステップ７４において、仮想ノードブロックＰＮは、探索パケットＳＰを受信すると、受信した探索パケットＳＰの通過した仮想リンクの情報を含む経過情報２５に追加する。たとえば、仮想ノードブロックＰＮ２は、経過情報２５のビットマップの１番目のビットを１にセットすることにより、仮想リンクＰＬ１を通過したことを経過情報２５に追加する。そして、その経過情報２５を含む探索パケットＳＰを複製し、受信した探索パケットＳＰの到来した仮想リンクＰＬ１を除き、仮想ノードブロックＰＮに繋がった全ての仮想リンクＰＬに送信する。たとえば、仮想ノードブロックＰＮ２は、経過情報２５のビットマップの１番目のビットが１にセットされた探索パケットＳＰの複製を２つ生成し、それぞれを、仮想リンクＰＬ３およびＰＬ４に送信する。
【００６１】
ステップ７５において、十分な数の探索パケットＳＰが仮想宛先ノードブロックＰＮ８に到達するまで仮想ノードブロックＰＮ間において探索パケットＳＰを転送する。十分な数の探索パケットＳＰが仮想宛先ノードブロックＰＮ８に到達すると、ステップ７６において、経路選択ユニット３２は、得られた複数の探索パケットＳＰの経過情報２５により、ソースノードＮ１から宛先ノードＮ８に至る複数の経路を得ることができる。そして、得られた経路の中から、所定の条件に合致する経路を選択する。
【００６２】
ステップ７５において、ディスジョイントな経路を選択する場合は、上述したように、複数の経過情報２５のビットマップデータの論理積を演算することが望ましい。最小ホップ数の最短経路、最小コストの最短経路の探索もディスジョイントな経路の探索とともに行うことができる。仮想宛先ノードブロックＰＮ８に順番の早いものから（先に到着した）複数の探索パケットＳＰのみの（に限定した）経過情報２５により、ディスジョイントな経路で、最短の経路を選択することが可能である。基本的には、種々の条件を加味して、最短な経路を選択することがルート探索の目的であり、全ての探索パケットＳＰが仮想宛先ノードブロックＰＮ８に到達することを待つ必要はない。
【００６３】
また、ステップ７４において、それぞれの仮想ノードブロックＰＮは、到着した順番の早いものから複数の探索パケットＳＰの複製のみを転送することが望ましい。種々の条件を加味して、最短な経路を選択することがルート探索の目的であり、無駄にリンクをたどっている探索パケットＳＰを活かす必要は通常の場合はない。さらに、ステップ７４において、通過した仮想リンク（または仮想ノードブロック）についての同じ情報を経過情報２５に持つ探索パケットＳＰを廃棄することが望ましい。たとえば、仮想リンクＰＬ３を経過した情報を持つ探索パケットＳＰが仮想リンクＰＬ３を通して仮想ノードブロックＰＮ４に到達したときは、その探索パケットＳＰは、仮想リンクＰＬ３をループしていることを意味する。ループする経路を示す探索パケットＳＰは、経路探索には不要であり、そのような探索パケットＳＰは破棄し、仮想ネットワーク３５を流れる探索パケットＳＰの数を減らすことが望ましい。
【００６４】
図１１から図１７に、図７に示したネットワーク２１について、経路探索システム３０により経路が探索される様子を示している。まず、ネットワーク２１内のすべてのリンクに、リンク番号（Ｌ１〜Ｌ１３）を付与する。リンク番号は、ＳＲＬＧ（Shared Risk Link Group）番号のようなものにしてもよいが、本例ではリンク番号で独立性を促進する。
【００６５】
図１１に示したステップ１において、Ｓ（ソース）ノードＮ１（ＰＮ１）からソースノードＮ１につながっているすべてのノードに対して、探索パケットＳＰを流して探索を開始する。
【００６６】
図１２に示したステップ２において、探索パケットＳＰが到着したノードＮ（ＰＮ）は、当該ノードＮに接続し、逆戻りとならないノードＮすべてに1つずつ探索パケットＳＰを流して探索を行う。この際、それぞれの探索パケットＳＰは通過したリンク番号を含む経過情報２５を保持する。
【００６７】
図１３〜図１６に示すように、ステップ３〜ステップ６において、上記と同様に、１サイクルごとに次のノードＮ（ＰＮ）へ探索を行う。図１５に示したステップ５では、ループを作った探索パケットＳＰを廃棄している。ループの検出方法としては、経過情報２５の通過ノード番号から判断する方法と、探索パケットＳＰに適当な識別情報を付加して各仮想ノードブロックＰＮがすでに通過している探索パケットＳＰを把握し、仮想リンクＰＬを再度探索しようとした場合に廃棄する方法とが考えられる。各仮想リンクＰＬの遅延を同じに設定することが可能であり、その場合、ＰＥマトリクス１０に再構成された仮想ネットワーク３５においては、仮想ノードブロックＰＮにおけるレイテンシを別にすれば、１サイクル毎に次の仮想ノードブロックＰＮの探索を行うことができる。したがって、多数のノードおよびリンクを含むネットワーク２１の経路探索を短時間で行うことができる。
【００６８】
遅延エレメントにより各仮想リンクＰＬにコストをセットした場合であっても、１つの仮想リンクＰＬについて数クロックの遅れが発生するだけであり、実際のネットワーク２１にパケットを流して、各ノードにおいて、各種のネットワークプロトコルが処理するのを待って、ルート探索用のパケットが送受信されるのと比較すると、遙かに短時間でネットワーク２１の経路探索を行うことができる。さらに、仮想ネットワーク３５は、経路探索システム３０の内部に存在しているので、仮想宛先ノードブロックＰＮ８に到達した探索パケットＳＰをソースノードブロックＰＮ１に戻さなくても、経過情報２５に基づき経路を探索できる。この点でも、ターゲットのネットワーク２１にパケットを流すことに比較すると、はるかに短時間で経路探索を行うことができる。
【００６９】
図１７に示したステップ７では、すべてのルートで探索が終了している。仮想宛先ノードブロックＰＮ８に到達した探索パケットＳＰに含まれる経路情報２５の例は、早く到着した順に以下の通りである。かっこ内は、リンク番号を、Ｌを除いて示す。
ルート１（１，４，７）３ｈｏｐ
ルート２（２，５，１２，７）４ｈｏｐ
ルート３（１，３，６，１３）４ｈｏｐ
ルート４（２，５，８，９，１０，１１）６ｈｏｐ
ルート５（１，４，１２，８，９，１０，１１）７ｈｏｐ
ルート６（２，５，１２，４，３，６，１３）７ｈｏｐ
【００７０】
したがって、経路選択ユニット３２においては、ルート１が最小ホップ数の最短経路であることがわかる。さらに、経路選択ユニット３２は、これら６つのルートの中でディスジョイントなルートの組合せを求めることができる。
【００７１】
図１８に、各ルートを辿って仮想宛先ノードブロックＰＮ８に到達した探索パケットＳＰに含まれている経過情報２５を示している。経過情報２５は、少なくとも１３ビット以上のビット幅を持つビットマップデータであり、通過した仮想リンクＰＬに相当する位置のビットが１になっている。経過情報２５は、たとえば、１００リンク程度を含むネットワークであれば１００ビット幅が必要であり、１３バイト程度のデータになる。
【００７２】
ルート１に対してディスジョイントなルートを求める場合は、ルート１の経過情報２５と、他のすべてのルート（ルート２〜６）の経過情報２５とのビット単位の論理積（ＡＮＤ）を演算すれば良い。１つでも論理積が“１”であれば、ディスジョイントではない。
【００７３】
図１９に、ソフトウェアで論理積を求める方法の１つをフローチャートにより示している。まず、ルートｉ（１〜６）の使用しているリンク番号ｊ（１〜１３）をｌ（ｉ,ｊ）行列とする。次に１つのルート（例えばルート１）を選択し、他のすべてのルート（例えばルート２〜６）のリンク番号ごとに論理積（ＡＮＤ）をとり、１つでも論理積が“１”であれば、ディスジョイントではないと判断する。
【００７４】
その結果、経路選択ユニット３２においては、以下のようなディスジョイントなルートの組み合わせを得ることができる。
ルート１とルート４
ルート２とルート３
ルート３と、ルート２およびルート４
ルート４とルート３
ルート５および６にはディスジョイントなルートは存在しない。
【００７５】
さらに、経路選択ユニット３２は、以下の３つのディスジョイントルートの候補が計算できる。
ルート１（３ｈｏｐ）＋ルート４（６ｈｏｐ）= ９ｈｏｐ
ルート２（４ｈｏｐ）＋ルート３（４ｈｏｐ）= ８ｈｏｐ
ルート３（４ｈｏｐ）＋ルート４（６ｈｏｐ）= １０ｈｏｐ
この場合、ルート２とルート３との組み合せが、もっともホップ数が少なくなることが分かる。したがって、このケースでは、経路選択ユニット３２は、理想解としてルート２およびルート３との組み合わせを選択する。これらのルート２およびルート３は、図２０に示すようにリンクディスジョイントであるとともに、ノードディスジョイントなルートである。ノードディスジョイントなルートを選択することにより、さらにリンクのみならず、ノードの欠陥に対して信頼性の高いルーティングテーブル８１を提供できる。積極的にノードディスジョイントなルートを選択する場合は、経過情報２５に通過したノード（仮想ノードブロック）の識別情報を含めることが望ましい。また、ディスジョイントなルートを選択する条件は、総ホップ数が最少に限定されず、コストが反映されている場合は、総コスト数が最少となる組み合わせであっても良い。あるいは、ディスジョイントなルートのコスト差あるいはホップ差が最少になるような組み合わせであっても良い。
【００７６】
また、大規模ネットワークでは、すべてのルートを探索してくるのを待つのは、探索時間が大きくなってしまう問題がある。そこで、経路選択ユニット３２は、仮想宛先ノードブロックＰＮ８に到着した順番の早い探索パケットＳＰのベストｍ個のルートのみに制限して選択する。
【００７７】
また、到着した順番の早いもののベストｍを仮想宛先ノードブロックＰＮ８で得るため、各中継ノードブロックＰＮでも、すべて到着した順番の早いものｍ個のみを処理して、残りは廃棄する。このことによって、ネットワーク内の探索は、最大ｍ、ｎ（ｎはノード数）で上限が決まる。
【００７８】
さらに、ＰＥマトリクス１０のＰＥなどのハードウェア資源が不足する場合は、仮想ネットワーク３５をマルチコンテキスト化し、時分割でＰＥマトリクス１０に再構成することが可能である。また、複数のデバイス１のＰＥマトリクス１０をダイレクト接続し、仮想的にＰＥマトリクス１０のハードウェア資源を拡大しても良い。
【００７９】
また、この経路探索システム３０においては、再構成ユニットであるＰＥマトリクス１０に仮想ネットワークが再構成できれば、ルート検索が可能となる。したがって、異なるルーティングプロトコルが適用される複数のネットワークあるいは複数のＡＳをカバーする範囲のルート検索にも適用できる。
【図面の簡単な説明】
【００８０】
【図１】ルータの概略構成を示す図。
【図２】図２（ａ）はネットワーク行列の一例、図２（ｂ）は対応するネットワークの一例を示す図。
【図３】図３（ａ）は、再構成可能なデバイスの一例の概略構成を示し、図３（ｂ）は、ＰＥマトリクスの概略を示し、図３（ｃ）および図３（ｄ）は、ＰＥマトリクスを動的に再構成する様子を示す図。
【図４】ＰＥマトリクスの構成を示す図。
【図５】ＰＥの一例の概略構成を示す図。
【図６】ＰＥの他の例の概略構成を示す図。
【図７】ルート探索のターゲットのネットワークの一例を示す図。
【図８】仮想ネットワークの一例を示す図。
【図９】探索パケットの一例を示す図。
【図１０】経路探索のプロセスを示すフローチャート。
【図１１】経路探索の一例（ステップ１）を示す図。
【図１２】経路探索のステップ２を示す図。
【図１３】経路探索のステップ３を示す図。
【図１４】経路探索のステップ４を示す図。
【図１５】経路探索のステップ５を示す図。
【図１６】経路探索のステップ６を示す図。
【図１７】経路探索のステップ７を示す図。
【図１８】経過情報のビットマップを示す図。
【図１９】論理積を求めるプロセスの一例を示すフローチャート。
【図２０】ディスジョイントなルートの組み合わせの一例を示す図。
【符号の説明】
【００８１】
１再構成可能デバイス、１０ＰＥマトリクス（再構成ユニット）
３０経路探索システム
３１仮想ネットワーク構成ユニット、３２経路選択ユニット
３５仮想ネットワーク
８０ルーティングユニット
１００ルータ

【特許請求の範囲】
【請求項１】
複数のノードと、それらを接続する複数のリンクとを含むネットワークにおいて、ソースノードから、１または複数の宛先ノードへ至る経路を探索するためのシステムであって、
複数のプロセッシングエレメントと、前記複数のプロセッシングエレメントの接続を動的に変更可能な接続マトリクスとを含み、動的に回路を再構成可能な再構成ユニットと、
１または複数のルーティングプロトコルにより収集された前記ネットワークの情報に基づき、前記再構成ユニットに仮想ネットワークを構成するユニットとを有し、
前記仮想ネットワークを構成するユニットは、前記複数のプロセッシングエレメントにより、前記ネットワークに含まれる前記複数のノードにそれぞれ対応する複数の仮想ノードブロックを構成し、前記接続マトリクスにより、前記複数のリンクにそれぞれ対応する複数の仮想リンクを構成し、
前記複数の仮想ノードブロックのうち、前記ソースノードに対応する仮想ソースノードブロックを、前記仮想ソースノードブロックに繋がった全ての仮想リンクに探索パケットを送信するように構成し、さらに、
前記複数の仮想ノードブロックのそれぞれを、受信した前記探索パケットに、前記受信した探索パケットの通過した仮想リンクおよび／または仮想ノードブロックの情報を含む経過情報を追加し、前記受信した探索パケットを複製した探索パケットを、前記受信した探索パケットの到来した仮想リンクを除き、前記それぞれの仮想ノードブロックに繋がった全ての仮想リンクに送信するように構成し、
さらに、当該システムは、
前記複数の仮想ノードブロックのうち、前記宛先ノードに対応する仮想宛先ノードブロックに到着した複数の前記探索パケットの前記経過情報により、前記ソースノードから前記宛先ノードに至る複数の経路から所定の条件に合致する経路を選択する経路選択ユニットを有する、システム。
【請求項２】
請求項１において、前記経過情報は、前記通過した仮想リンクおよび／または仮想ノードブロックをビット位置で識別できるビットマップデータを含み、
前記経路選択ユニットは、複数の前記経過情報の前記ビットマップデータのビット単位の論理積を演算することにより、前記ソースノードから前記宛先ノードに至る複数の経路から、ディスジョイントな経路を選択する、システム。
【請求項３】
請求項１または２において、前記複数のプロセッシングエレメントは、遅延量を動的に設定できる複数の遅延エレメントを含み、
前記仮想ネットワークを構成するユニットは、前記接続マトリクスと、前記複数の遅延エレメントとにより、前記複数の仮想リンクを構成し、それぞれの仮想リンクに含まれる遅延エレメントには、対応するリンクのコストに対応する遅延量を設定する、システム。
【請求項４】
請求項１ないし３のいずれかにおいて、前記経路選択ユニットは、前記仮想宛先ノードブロックに到着した順番の早いものから複数の前記探索パケットの前記経過情報により、前記ソースノードから前記宛先ノードに至る複数の経路から所定の条件に合致する経路を選択する、システム。
【請求項５】
請求項１ないし４のいずれかにおいて、前記仮想ネットワークを構成するユニットは、前記それぞれの仮想ノードブロックを、前記それぞれの仮想ノードブロックに到着した順番の早いものから複数の探索パケットの複製のみを、前記受信した探索パケットの到来した仮想リンクを除き、前記それぞれの仮想ノードブロックに繋がった全ての仮想リンクに送信するように構成する、システム。
【請求項６】
請求項１ないし５のいずれかにおいて、前記仮想ネットワークを構成するユニットは、前記それぞれの仮想ノードブロックを、前記通過した仮想リンクおよび／または仮想ノードブロックについての同じ情報を持つ探索パケットを廃棄するように構成する、システム。
【請求項７】
複数のノードと、それらを接続する複数のリンクとを含むネットワークにおいて、ソースノードから、１または複数の宛先ノードへ至る経路を、再構成ユニットを用いて探索する方法であって、
前記再構成ユニットは、複数のプロセッシングエレメントと、前記複数のプロセッシングエレメントの接続を動的に変更可能な接続マトリクスとを含み、動的に回路を再構成可能であり、
当該方法は、
１または複数のルーティングプロトコルにより収集された前記ネットワークの情報に基づき、前記複数のプロセッシングエレメントにより、前記ネットワークに含まれる前記複数のノードにそれぞれ対応する複数の仮想ノードブロックを構成し、前記接続マトリクスにより、前記複数のリンクにそれぞれ対応する複数の仮想リンクを構成し、前記再構成ユニットに仮想ネットワークを構成することと、
前記複数の仮想ノードブロックのうち、前記ソースノードに対応する仮想ソースノードブロックが、前記仮想ソースノードブロックに繋がった全ての仮想リンクに探索パケットを送信することと、
前記複数の仮想ノードブロックのそれぞれが、受信した前記探索パケットに、前記受信した探索パケットの通過した仮想リンクおよび／または仮想ノードブロックの情報を含む経過情報を追加し、前記受信した探索パケットを複製した探索パケットを、前記受信した探索パケットの到来した仮想リンクを除き、前記それぞれの仮想ノードブロックに繋がった全ての仮想リンクに送信することと、
前記複数の仮想ノードブロックのうち、前記宛先ノードに対応する仮想宛先ノードブロックに到着した複数の前記探索パケットの前記経過情報により、前記ソースノードから前記宛先ノードに至る複数の経路から所定の条件に合致する経路を選択することとを含む方法。
【請求項８】
請求項７において、前記経過情報は、前記通過した仮想リンクおよび／または仮想ノードブロックをビット位置で識別できるビットマップデータを含み、
前記経路を選択することは、複数の前記経過情報の前記ビットマップデータのビット単位の論理積を演算することにより、前記ソースノードから前記宛先ノードに至る複数の経路から、ディスジョイントな経路を選択することを含む、方法。
【請求項９】
請求項７または８において、前記複数のプロセッシングエレメントは、遅延量を動的に設定できる複数の遅延エレメントを含み、
前記仮想ネットワークを構成することは、前記接続マトリクスと、前記複数の遅延エレメントとにより、前記複数の仮想リンクを構成し、それぞれの仮想リンクに含まれる遅延エレメントには、対応するリンクのコストに対応する遅延量を設定することを含む、方法。
【請求項１０】
請求項７ないし９のいずれかにおいて、前記経路を選択することは、前記仮想宛先ノードブロックに到着した順番の早いものから複数の前記探索パケットの前記経過情報により、前記ソースノードから前記宛先ノードに至る複数の経路から所定の条件に合致する経路を選択することを含む、方法。
【請求項１１】
請求項７ないし１０のいずれかにおいて、前記それぞれの仮想ノードブロックに繋がった全ての仮想リンクに送信することは、前記それぞれの仮想ノードブロックが、前記それぞれの仮想ノードブロックに到着した順番の早いものから複数の探索パケットの複製のみを、前記受信した探索パケットの到来した仮想リンクを除き、前記それぞれの仮想ノードブロックに繋がった全ての仮想リンクに送信することを含む、方法。
【請求項１２】
請求項７ないし１１のいずれかにおいて、前記それぞれの仮想ノードブロックに繋がった全ての仮想リンクに送信することは、前記通過した仮想リンクおよび／または仮想ノードブロックについての同じ情報を持つ探索パケットを廃棄することを含む、方法。

【図１】