(57)【要約】【課題】処理時間の短い経路探索システムを提供する。【解決手段】再構成可能なデバイス１のＰＥマトリクス１０に仮想ネットワーク３５を構成し、経路探索を行うシステム３０を提供する。システム３０は、ネットワークの情報８９に基づきＰＥマトリクス１０に仮想ネットワーク３５を構成するユニット３１と、探索パケットをフラッディングする探索ユニット３２と、仮想ノードの仮想コストを探索パケットの通過にともない増加するコスト制御ユニット３３と、仮想宛先ノードに到着した探索パケットの経過情報により経路を選択する経路選択ユニット３４とを有する。このシステム３０を用いた経路探索方法では、独立に複数の仮想ノードをソースとしてルート探索をしたにもかかわらず、負荷分散が行われる。【選択図】図１
2010041429.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードと、それらを接続する複数のリンクとを含むネットワークにおける少なくとも１つのソースノードから少なくとも１つの宛先ノードへ至る経路を探索するためのシステムであって、
１または複数のルーティングプロトコルにより収集された前記ネットワークの情報に基づき仮想ネットワークを構成するユニットを有し、
前記仮想ネットワークは、前記ネットワークに含まれる前記複数のノードにそれぞれ対応する複数の仮想ノードと、前記複数のリンクにそれぞれ対応する複数の仮想リンクとを含み、
さらに、当該システムは、
前記複数の仮想ノードのうち、前記少なくとも１つのソースノードに対応する少なくとも１つの仮想ソースノードから前記少なくとも１つの仮想ソースノードに繋がった全ての仮想リンクに探索パケットを送信し、それぞれの探索パケットを前記仮想ネットワークにしたがって伝播する探索ユニットと、
いずれかの探索パケットが通過した通過済みの仮想リンクの仮想コストを増加するコスト制御ユニットと、
前記複数の仮想ノードのうち、前記少なくとも１つの宛先ノードに対応する少なくとも１つの仮想宛先ノードに到着した各探索パケットが通過した複数の仮想リンクの仮想コストの総和に相当する累積コストを含む経過情報により、前記少なくとも１つのソースノードから前記少なくとも１つの宛先ノードに至る経路を選択する経路選択ユニットとを有するシステム。
【請求項２】
請求項１において、
前記探索ユニットは、前記累積コストが所定の値を超えた探索パケットを廃棄する機能を含む、システム。
【請求項３】
請求項１または２において、
前記探索ユニットは、各仮想ノードに到達した探索パケットの累積コストが、到達した仮想ノードを通過済みであって仮想ソースノードが共通の探索パケットの累積コストよりも大きければ前記到達した探索パケットを廃棄する機能を含む、システム。
【請求項４】
請求項１ないし３のいずれかにおいて、
前記コスト制御ユニットは、前記通過済みの仮想リンクの仮想コストを、探索パケットが通過する毎に増加する、システム。
【請求項５】
請求項１ないし３のいずれかにおいて、
前記コスト制御ユニットは、前記通過済みの仮想リンクの仮想コストを、通過済みの探索パケットの数に応じて増加する、システム。
【請求項６】
請求項１ないし５のいずれかにおいて、
複数のプロセッシングエレメントと、前記複数のプロセッシングエレメントの接続を動的に変更可能な接続マトリクスとを含み、動的に回路を再構成可能な再構成ユニットをさらに有し、
前記仮想ネットワークを構成するユニットは、前記複数のプロセッシングエレメントにより前記複数の仮想ノードを構成し、前記接続マトリクスにより前記複数の仮想リンクを構成する機能を含む、システム。
【請求項７】
請求項６において、前記複数のプロセッシングエレメントは、遅延量を動的に設定できる複数の遅延エレメントを含み、
前記仮想ネットワークを構成するユニットは、前記接続マトリクスと、前記複数の遅延エレメントとにより前記複数の仮想リンクを構成し、各仮想リンクに含まれる遅延エレメントの遅延量を前記仮想コストにより設定し、
前記コスト制御ユニットは、各仮想リンクに含まれる遅延エレメントの遅延量を制御する、システム。
【請求項８】
複数のノードと、それらを接続する複数のリンクとを含むネットワークにおける少なくとも１つのソースノードから少なくとも１つの宛先ノードへ至る経路を探索する方法であって、
１または複数のルーティングプロトコルにより収集された前記ネットワークの情報に基づき仮想ネットワークを構成することを有し、
前記仮想ネットワークは、前記ネットワークに含まれる前記複数のノードにそれぞれ対応する複数の仮想ノードと、前記複数のリンクにそれぞれ対応する複数の仮想リンクとを含み、
さらに、当該方法は、
前記複数の仮想ノードのうち、前記少なくとも１つのソースノードに対応する少なくとも１つの仮想ソースノードから前記少なくとも１つの仮想ソースノードに繋がった全ての仮想リンクに探索パケットを送信し、それぞれの探索パケットを前記仮想ネットワークにしたがって伝播することと、
いずれかの探索パケットが通過した通過済みの仮想リンクの仮想コストを増加することと、
前記複数の仮想ノードのうち、前記少なくとも１つの宛先ノードに対応する少なくとも１つの仮想宛先ノードに到着した各探索パケットが通過した複数の仮想リンクの仮想コストの総和に相当する累積コストを含む経過情報により、前記少なくとも１つのソースノードから前記少なくとも１つの宛先ノードに至る経路を選択することとを有する、方法。
【請求項９】
請求項８において、
前記伝播することは、前記累積コストが所定の値を超えた探索パケットを廃棄することを含む、方法。
【請求項１０】
請求項８または９において、
前記伝播することは、各仮想ノードに到達した探索パケットの累積コストが、到達した仮想ノードを通過済みであって仮想ソースノードが共通の探索パケットの累積コストよりも大きければ前記到達した探索パケットを廃棄することを含む、方法。
【請求項１１】
請求項８ないし１０のいずれかにおいて、
前記増加することは、前記通過済みの仮想リンクの仮想コストを、探索パケットが通過する毎に増加することを含む、方法。
【請求項１２】
請求項８ないし１０のいずれかにおいて、
前記増加することは、前記通過済みの仮想リンクの仮想コストを、通過済みの探索パケットの数に応じて増加することを含む、方法。
【請求項１３】
複数のノードと、それらを接続する複数のリンクとを含むネットワークにおける少なくとも１つのソースノードから少なくとも１つの宛先ノードへ至る経路の探索を、動的に回路を再構成可能な再構成ユニットを含むシステムが実行するためのプログラムであって、
前記再構成ユニットは、複数のプロセッシングエレメントと、前記複数のプロセッシングエレメントの接続を動的に変更可能な接続マトリクスとを含み、さらに、前記複数のプロセッシングエレメントは、遅延量を動的に設定できる複数の遅延エレメントを含み、
当該プログラムは、
１または複数のルーティングプロトコルにより収集された前記ネットワークの情報に基づき仮想ネットワークを構成することを有し、
前記仮想ネットワークは、前記ネットワークに含まれる前記複数のノードにそれぞれ対応する複数の仮想ノードと、前記複数のリンクにそれぞれ対応する複数の仮想リンクとを含み、
前記構成することは、前記複数のプロセッシングエレメントにより前記複数の仮想ノードを構成し、前記接続マトリクスおよび前記複数の遅延エレメントにより前記複数の仮想リンクを構成し、
さらに、当該プログラムは、
前記複数の仮想ノードのうち、前記少なくとも１つのソースノードに対応する少なくとも１つの仮想ソースノードから前記少なくとも１つの仮想ソースノードに繋がった全ての仮想リンクに探索パケットを送信し、それぞれの探索パケットを前記仮想ネットワークにしたがって伝播することと、
いずれかの探索パケットが通過した通過済みの仮想リンクの仮想コストを、前記通過済みの仮想リンクに含まれる遅延エレメントの遅延量を制御することにより増加することと、
前記複数の仮想ノードのうち、前記少なくとも１つの宛先ノードに対応する少なくとも１つの仮想宛先ノードに到着した各探索パケットが通過した複数の仮想リンクの仮想コストの総和に相当する累積コストを含む経過情報により、前記少なくとも１つのソースノードから前記少なくとも１つの宛先ノードに至る経路を選択することとを有するプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークにおける種々の経路探索に関するものである。
【背景技術】
【０００２】
インターネットの爆発的な発展と普及とに伴い、仕事および日常生活においてコンピュータネットワークが頻繁に利用されるようになっている。コンピュータネットワークではルーティングプロトコルによって交換される情報に基づいてルーティングテーブルが作成され、そのルーティングテーブルに従いパケットが配送される。代表的なルーティングプロトコルとしては、単一の自律システム（ＡＳ（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）で定期的に交換する。したがって、そのネットワークに属する各ノードはネットワーク中のすべてのリンク情報（コスト）を知っている。したがって、ネットワーク行列８９には、ＬＳＡにより得られたネットワーク内のリンクコスト情報を含めることができる。ネットワーク行列８９には、さらに、ＯＳＰＦとともに、あるいはＯＳＰＦに替えて、他のルーティングプロトコルにより取得されたネットワークの情報を含めることができる。この例では、ネットワーク行列８９には、ターゲットのネットワークに含まれる複数のノードと、複数のノードを接続する複数のリンクと、それぞれのリンクのコストとが含まれる。インターネットなどのコンピュータネットワークにおいて、ノード間のコスト（リンクコスト）を決定する典型的な要素は、通信速度の逆数である。その他に、光ネットワークにおいては波長予約の成功率、送信対象のデータ種別、ＱｏＳにより予約された帯域など複数の要因をリンクコストとして反映することができる。ネットワーク行列８９には、コスト以外の他の、経路の優劣を比較できる要素（ルーティングメトリック）を含めても良い。
【００２３】
図２（ａ）にネットワーク行列の一例を示している。このネットワーク行列ＭＮは、図２（ｂ）に示したネットワークＮに対応するものであり、ネットワークＮはノードＡ〜Ｆの６つのノードを含む。ネットワーク行列ＭＮは、ネットワークＮに含まれる各ノードを基端とし、基端のノードに繋がる他のノードを先端とする各リンクのコストをエレメントとして含む。無限大のエレメントは、ネットワーク行列ＭＮに含まれるノードであって、直接のルートでは繋がっていないノードを示す。ノードが未接続であることを示す値は無限大に限らない。
【００２４】
ルーティングユニット８０は、ルーティングプロトコルを用いて収集されたネットワークの情報（ネットワーク行列）８９に基づき、経路探索を行うシステム（経路探索システム）３０を含む。この経路探索システム３０は、内部に、回路を動的に再構成可能な領域（再構成ユニット）を備えたデバイス（再構成可能デバイス）１を含む。そして、経路探索システム３０は、ネットワーク行列８９に基づき、経路を発見しようとしているネットワーク（ターゲットのネットワーク）に対応するネットワーク構成を、経路探索を目的とした範囲で仮想的に再構成可能デバイス１に再構成し、経路探索を行う。
【００２５】
再構成可能なデバイスの一例は、特許文献２に示したものであり、たとえば、アイピーフレックス社のＤＡＰＤＮＡ（登録商標）として市販されている半導体集積回路装置である。このデバイス１は、ＤＡＰと呼ばれるＲＩＳＣコアモジュール２と、ＤＮＡと呼ばれるダイナミックリコンフィグラブルデータフローアクセレレータ３とを含む。デバイス１は、ＤＡＰ２およびＤＮＡ３に加え、種々のインターフェイスなどを備えている。デバイス１は、多数のＰＥ（ＰＥｓ、処理エレメント）が２次元に配置されたＰＥマトリクス１０と、このＰＥマトリクス１０に含まれるＰＥｓの機能および／またはＰＥｓの接続を変えてＰＥマトリクス１０を再構成するためのコンフィグレーションデータ１８が格納されるコンフィグレーションメモリ１９とを含む。
【００２６】
図３に示すように、ＰＥマトリクス１０は、複数のプロセッシングエレメントＰＥ（ＰＥｓ）４５と、複数のＰＥの接続を動的に変更可能な接続マトリクス４４とを含み、動的に回路を再構成可能な再構成ユニットに相当する。ＰＥマトリクス１０の再構成は、例えば、１サイクル（クロックサイクル）でダイナミックに行なわれる。
【００２７】
経路探索において、ターゲットのネットワークに含まれるノード数が膨大な場合は、ネットワークを複数のサブネットワークに分割し、それらのサブネットワークに対応する仮想ネットワークを時分割で動的に再構成することが可能である。したがって、このデバイス１を採用した経路探索システム３０は、大規模ネットワークに対しても適用できる。また、ルータ１００において、デバイス１は、経路探索システム３０として機能させるだけではなく、ルーティングテーブル８１を参照してパケットを送出するネクストホップを選択する機能８２などとしても用いることができる。このような使用により、多くのアプリケーションを共通のハードウエア（デバイス）１を用いて実行できる。
【００２８】
このデバイス１は、さらに、プログラムレベル（命令レベル）ではなく、データフローレベル（データパスレベル、ハードウエアレベル）で多数の機能を切り換えて実装できる。このため、経路探索のための仮想ネットワークをＰＥマトリクス１０に再構成することにより、専用のハードウェアで構成したのに匹敵する処理速度を得ることができる。その一方で、ＰＥマトリクス１０は動的に再構成できるので、経路探索の対象となるネットワークの変動に対してもフレキシブルに、遅滞なく追従できる。
【００２９】
また、ＰＥマトリクス１０に含まれるＰＥｓは、クロックにより同期した処理を行うことが可能であり、パイプライン処理に適したデータフロー（データパス）をＰＥマトリクス１０に再構成できる。さらに、多数のＰＥｓにより並列処理を行う複数のデータフローを並列に再構成することも可能である。したがって、ＰＥマトリクス１０に仮想ネットワークを再構成し、経路探索用のパケット（探索パケット）を流すことにより、仮想ネットワーク内で、ターゲットのネットワークと同様に、複数の探索パケットを並列に送受信することが可能となる。さらに、探索パケットの送受信（流れ）が同期的に処理されるので、探索パケットが目的のノード（たとえば、宛先ノード）に到達したタイミングを、その探索パケットが通過した経路の質に関する情報として捉えて、経路を選択するための情報として利用することが可能となる。このように、ＰＥマトリクス１０に仮想ネットワークを回路として動的に再構成することにより、ハードウエアによる高速な処理速度と、ソフトウエアのような柔軟性とが融合された経路探索環境を提供できる。
【００３０】
ＰＥマトリクス１０は、縦横に２次元に配置された複数のプロセッシングエレメント（ＰＥ）４５と、それらの間に格子状に配置された配線４７と、配線４７の接続ポイントで縦横の配線４７の接続を自由に切り替えることができるスイッチングユニット４６とを備えている。配線４７およびスイッチングユニット４６が、複数のＰＥ４５の接続を自由に変えることができる接続マトリクス４４を構成する。接続マトリクス４４には、遅延用のＰＥなどの、接続環境を調整するためのＰＥが含まれていても良い。
【００３１】
再構成可能なＰＥマトリクス（回路領域）１０を構成するＰＥ４５の一例は、ルックアップテーブルなどにより自在に機能を設定可能なものである。プロセッサ２から、またはコンフィグレーションメモリ１９から、制御バス９ａを介して、各ＰＥ４５に対してコンフィグレーションデータが供給される。このコンフィグレーションデータにより、各々のＰＥ４５の機能と、配線群４７の接続とが制御され、マトリクス１０の内部に、種々のデータフロー（データパス）を自由に構成できる。さらに、ＰＥマトリクス１０は、バス９ｂを介して外部メモリインターフェイス６などの外界と接続される。
【００３２】
典型的なＰＥ４５の一例は算術演算および論理演算に適した構成の演算用のＰＥである。したがって、コンフィグレーションデータ１８により、１つ、または複数のＰＥ４５により、探索パケットを、所定の条件で転送するような機能を備えたノードを再構成できる。典型的なＰＥ４５の他の例は、データが伝送されるタイミングを遅延する処理に適したものである。遅延のＰＥ４５は、コンフィグレーションデータにより、たとえば、入力毎に１〜１０クロック程度の遅延を制御できる。この遅延用のＰＥ４５を、仮想ネットワークの仮想ノード間を接続する仮想リンクに含めるようにＰＥマトリクス１０を再構成することが可能である。遅延用のＰＥ４５の遅延量はコンフィグレーションデータ１８によりバリアブルに設定できるので、その遅延量により、リンクコストなどのリンクの優劣を決める要素を、探索パケットの遅延（転送時間の遅れ）として探索パケットの履歴（経過情報）に含めることができる。
【００３３】
図１に示すように、経路探索システム３０は、再構成ユニットであるＰＥマトリクス１０に仮想ネットワーク３５を構成する構成ユニット３１と、仮想ネットワーク３５を用いて探索された経路から所定の条件に合致する経路を選択する経路選択ユニット３４とを含む。さらに、１つ、または複数のＰＥ４５により再構成される仮想ノードは、探索パケットを所定の条件で転送あるいは伝播する探索ユニット３２としての機能を含む。また、遅延用のＰＥを含む１つ、または複数のＰＥ４５により再構成される仮想ノードまたは仮想リンクは、仮想コストを増加するコスト制御ユニット３３としての機能を含む。
【００３４】
構成ユニット３１は、ルータ１００がサポートする１または複数のルーティングプロトコルにより収集されたネットワークの情報（ネットワーク行列）８９に基づき、ＰＥマトリクス１０に仮想ネットワーク３５を再構成する。
【００３５】
各仮想ノードの探索ユニット３２としての機能は、複数の仮想ノードのうち、少なくとも１つのソースノードに対応する少なくとも１つの仮想ソースノードから少なくとも１つの仮想ソースノードに繋がった全ての仮想リンクに探索パケットを送信し、それぞれの探索パケットを仮想ネットワークにしたがって伝播（フラッディング）する。探索ユニット３２は、さらに、累積コストが所定の値を超えた探索パケットを廃棄する機能を含む。また、探索ユニット３２は、各仮想ノードに到達した探索パケットの累積コストが、到達した仮想ノードを通過済みであって仮想ソースノードが共通の探索パケットの累積コストよりも大きければ到達した探索パケットを廃棄する機能を含む。
【００３６】
各仮想ノードまたは仮想リンクに付与されるコスト制御ユニット３３は、いずれかの探索パケットが通過した通過済みの仮想リンクの仮想コストを増加する。コスト制御ユニット３３の一例は、通過済みの仮想リンクの仮想コストを、探索パケットが通過する毎に増加するものである。コスト制御ユニット３３の他の例は、通過済みの仮想リンクの仮想コストを、通過済みの探索パケットの数に応じて増加するものである。
【００３７】
経路選択ユニット３４は、仮想ネットワーク３５に含める複数の仮想ノードのうち、宛先ノード（ディスティネーションノード）に対応する仮想宛先ノードに到着した複数の探索パケットの経過情報により、ソースノードから宛先ノードに至る複数の経路から所定の条件に合致する経路を選択する。この例では、これらのユニット３１〜３４としての機能は、ＤＡＰ２にロードされるプログラムにより提供されるようになっている。ＤＡＰ２に実装されているユニット３１および３４は、ＰＥマトリクス１０に、仮想ネットワーク３５とともに、あるいは時分割で再構成しても良い。
【００３８】
図４に、経路探索の対象となるターゲットのネットワークの一例を示している。図５に、そのネットワークに対応するように、経路探索のためにＰＥマトリクス１０に再構成された仮想ネットワークの一例を示している。ターゲットのネットワーク２１はＮ１〜Ｎ１１の１１個のノードと、これらのノードを接続するＬ１〜Ｌ１３の１３個のリンクとを含む。仮想ネットワーク３５は、ノードＮ１〜Ｎ１１にそれぞれ対応する仮想ノードＰＮ１〜ＰＮ１１と、リンクＬ１〜Ｌ１３にそれぞれ対応する仮想リンクＰＬ１〜ＰＬ１３を含む。仮想ノードＰＮ１〜ＰＮ１１は、１または複数のＰＥ４５により構成され、仮想リンクＰＬ１〜ＰＬ１３は、ＰＥ４５を接続する接続マトリクス４４により構成される。仮想リンクＰＬ１〜ＰＬ１３には、配線４７およびスイッチングユニット４６だけではなく、遅延用のエレメントが含まれていても良い。なお、以下では、仮想ノードおよび仮想リンクを一般的に示す場合は、仮想ノードＰＮおよび仮想リンクＰＬとして参照する。
【００３９】
構成ユニット３１は、ネットワーク行列８９に基づいて、ＰＥマトリクス１０に仮想ネットワーク３５を再構成するためのコンフィグレーションデータ１８を生成し、そのコンフィグレーションデータ１８をＰＥマトリクス１０またはコンフィグレーションメモリ１９に供給することにより仮想ネットワーク３５として機能する回路（データフロー、データパス）をＰＥマトリクス１０に再構成する。
【００４０】
構成ユニット３１は、仮想ノードＰＮに探索ユニット３２としての機能を付与するために、受信した探索パケットＳＰに、受信した探索パケットＳＰの通過した仮想リンクおよび／または仮想ノードの情報を含む経過情報を追加するように仮想ノードに関するコンフィグレーションデータ１８を生成し、それぞれの仮想ノードＰＮを再構成する。さらに、構成ユニット３１は、受信した探索パケットＳＰを複製した探索パケットＳＰを、受信した探索パケットＳＰの到来した仮想リンクＰＬを除き、それぞれの仮想ノードＰＮに繋がった全ての仮想リンクＰＬに送信するように仮想ノードに関するコンフィグレーションデータ１８を生成し、それぞれの仮想ノードＰＮを再構成する。
【００４１】
それぞれの仮想ノードＰＮ、すなわち仮想ノードＰＮ１〜ＰＮ１１はすべて仮想ソースノードとなることができ、すべて仮想宛先ノードとなることができる。図４および図５は、ノードＮ１を仮想ソースノードＰＮ１として仮に示しているだけにすぎない。仮想ノードＰＮ１が仮想ソースノードであれば、仮想ソースノードＰＮ１に繋がった全ての仮想リンク、この場合は仮想リンクＰＬ１およびＰＬ２に、仮想ノードＰＮ１がオリジンである探索パケットＳＰを送信する。同様に、他の１または複数の仮想ノードＰＮからも、その仮想ノードＰＮをオリジンとする探索パケットＳＰが送出される。
【００４２】
構成ユニット３１は、さらに、それぞれの仮想ノードＰＮを、探索パケットＳＰの経過情報に含まれる累積コスト（探索パケットが通過した複数の仮想リンクの仮想コストの総和）が所定の値を超えた探索パケットは廃棄するようにコンフィグレーションデータ１８を生成し、仮想ソースノードＰＮを再構成する。仮想コストの総和が探索パケットＳＰの遅延となるこのシステム３０においては、それぞれの仮想ノードＰＮを、それぞれの仮想ノードＰＮに到着した順番の早いものから複数の探索パケットＳＰの複製のみを、受信した探索パケットの到来した仮想リンクＰＬを除き、それぞれの仮想ノードＰＮに繋がった全ての仮想リンクＰＬに送信するようにコンフィグレーションデータ１８を生成し、仮想ソースノードＰＮを再構成してもよい。
【００４３】
構成ユニット３１は、さらに、各仮想ノードに到達した探索パケットＳＰの累積コストが、到達した仮想ノードを通過済みであって仮想ソースノードが共通の探索パケットＳＰの累積コストよりも大きければ到達した探索パケットを廃棄するように仮想ノードに関するコンフィグレーションデータ１８を生成し、仮想ノードＰＮを再構成する。典型的には、各仮想ノードＰＮは、通過済みの探索パケットＳＰについて、ソースノードの情報と累積コストとを記憶するためのテーブルを含む。
【００４４】
構成ユニット３１は、さらに、通過した仮想リンクＰＬおよび／または仮想ノードＰＮについての同じ情報を持つ探索パケットＳＰを廃棄するように仮想ノードに関するコンフィグレーションデータ１８を生成し、仮想ノードＰＮを再構成する。
【００４５】
構成ユニット３１は、この例では、仮想ノードＰＮにコスト制御ユニット３３としての機能を付与するようにコンフィグレーションデータ１８を生成する。すなわち、構成ユニット３１は、それぞれの仮想ノードＰＮを、それらに繋がる仮想リンクＰＬを通過した探索パケットＳＰを受信すると、通過済みの仮想リンクＰＬの仮想コストを増加するようにコンフィグレーションデータ１８を生成し、仮想ノードＰＮを再構成する。
【００４６】
図６に、探索パケットＳＰの一例を示している。この探索パケットＳＰは、ヘッダー情報２４と、経過情報２５とを含む。経過情報２５は、探索パケットＳＰが通過した仮想リンクＰＬおよび／または仮想ノードＰＮをビット位置で識別できるビットマップデータ２５ａと、累積リンクコスト２５ｂとを含む。以下の例では、ビットマップデータ２５ａの一例は、探索パケットＳＰが通過した仮想リンクＰＬをビット位置で識別できるビットマップデータである。ビットマップデータ２５ａは、探索パケットＳＰが通過した仮想ノードＰＮをビット位置で識別できるビットマップデータであってもよい。経路選択ユニット３４は、仮想宛先ノードＰＮ８に到達した探索パケットＳＰの経過情報２５にアクセスすることにより仮想ソースノードＰＮ１から仮想宛先ノードＰＮ８に至る経路を知ることができる。その経路は、ターゲットのネットワーク２１における経路に相当するものであり、所定の条件に合った経路を見つけることにより、ルーティングテーブル８１を更新できる。
【００４７】
探索される経路の典型的なものの１つは、ソースノードＮ１から宛先ノードＮ８に至る最短経路である。たとえば、仮想リンクＬ１〜Ｌ１３の遅延を一定にすることにより、最も早く仮想宛先ノードＰＮ８に到達した探索パケットＳＰの経路を最小ホップ数の経路として選択できる。また、仮想リンクＬ１〜Ｌ１３の遅延をリンクコストに基づいて設定することにより、経路選択ユニット３４は、最も早く仮想宛先ノードＰＮ８に到達した探索パケットＳＰの経路を最小コストの経路として選択できる。さらに、仮想リンクＬ１〜Ｌ１３の遅延を探索パケットＳＰの通過により可変にすることにより、複数のソースおよびディスティネーション間のネットワーク２１の通信の負荷分散を図ることができる。
【００４８】
図７に、複数のソースノードから、１または複数の宛先ノードへ至る経路を、上記のシステム３０により並列に探索する方法の一例を示している。ステップ７１において、ルータ１００が提供する１または複数のルーティングプロトコルによりネットワークの情報８９を収集する。ステップ７２において、構成ユニット３１は、ネットワークの情報８９に基づき、ＰＥマトリクス１０に仮想ネットワーク３５を構成する。ステップ７３において、複数の仮想ノードＰＮを仮想ソースノードとして、その仮想ノードＰＮに繋がった全ての仮想リンクＰＬに探索パケットＳＰを送信する。
【００４９】
ステップ７４において、仮想ノードＰＮは、探索パケットＳＰを受信すると、受信した探索パケットＳＰの通過した仮想リンクの情報を経過情報２５に追加する。たとえば、仮想ノードＰＮ２は、経過情報２５のビットマップの１番目のビットを１にセットすることにより、仮想リンクＰＬ１を通過したことを経過情報２５に追加する。そして、その経過情報２５を含む探索パケットＳＰを複製し、受信した探索パケットＳＰの到来した仮想リンクＰＬ１を除き、仮想ノードＰＮに繋がった全ての仮想リンクＰＬに送信する。
【００５０】
ステップ７６において、仮想ノードＰＮは、探索パケットＳＰを受信した仮想リンクＰＬにセットされている仮想コストを増加する。具体的には、仮想リンクＰＬを構成している遅延ＰＥ４５の遅延量を増し、同じ仮想リンクＰＬを通過する探索パケットＳＰの経過情報２５に含まれる累積コスト２５ｂが急激に増加するようにする。
【００５１】
ステップ７６において、十分な数の探索パケットＳＰが仮想宛先ノードＰＮに到達するまで仮想ノードＰＮ間において探索パケットＳＰを転送する。十分な数の探索パケットＳＰが仮想宛先ノードＰＮに到達すると、経路選択ユニット３４は、各探索パケットＳＰの経過情報２５により、あるソースノードＮからある宛先ノードＮに至る複数の経路を得ることができる。ステップ７７において、経路選択ユニット３４は、それらの得られた経路の中から、所定の条件に合致する経路（最適経路）を選択する。
【００５２】
この探索方法では、他の探索パケットＳＰと共通の仮想リンクＰＬを通過した探索パケットＳＰの累積コスト２５ｂは、ホップ数が多くても他の探索パケットＳＰとは独立した仮想リンクＰＬを通過した探索パケットＳＰの累積コスト２５ｂより大きくなる可能性がある。したがって、ステップ７７において、最小コストを条件に最適経路を選択しても、複数のソースノードから複数の宛先ノードに至る複数の最適経路を、重複したリンクを通過しないように、あるいは、特定のリンクを集中して通過しないように選択することができる。
【００５３】
なお、ステップ７７において、ディスジョイントな経路を選択する場合は、複数の経過情報２５のビットマップデータの論理積を演算することが可能である。また、仮想リンクＰＬの仮想コストを１つの探索パケットＳＰが通過すると無限大にセットするなどの方法によりディスジョイントな経路のみを探索パケットＳＰが辿るようにすることも可能である。仮想ソースノードＰＮは１つであってもよく、上記の探索方法により、１つのソースノードから１または複数の宛先ノード（ディスティネーションノード）に至るディスジョイントな複数の経路を得ることも可能である。また、複数のソースノードから１または複数の宛先ノードに至るディスジョイントな最適経路の組み合わせを得ることも可能である。
【００５４】
また、ステップ７４において、それぞれの仮想ノードＰＮは、累積コスト２５ｂが所定の値を超えた探索パケットは廃棄する。また、ステップ７４において、それぞれの仮想ノードＰＮは、各仮想ノードＰＮに到達した探索パケットＳＰの累積コスト２５ｂが、到達した仮想ノードＰＮを通過済みであって仮想ソースノードが共通の探索パケットＳＰの累積コスト２５ｂよりも大きければ探索パケットＳＰを廃棄する。さらに、仮想ノードＰＮは、到着した順番の早いものから複数の探索パケットＳＰの複製のみを転送する。無駄にリンクをたどっている探索パケットＳＰを活かす必要は通常の場合はなく、そのための処理時間は無駄である。さらに、不要な探索パケットＳＰにより仮想リンクＰＬの仮想コストが不当に増加されるのは好ましくない。
【００５５】
図８に、経路探索の対象となる異なるターゲットのネットワーク２１ａを示している。このターゲットのネットワーク２１ａは、Ｎ１〜Ｎ１２の１２個のノードと、これらのノードを接続するＬ１〜Ｌ１３の１３個のリンクとを含む。このネットワーク２１ａに対応する仮想ネットワークを図５と同様にＰＥマトリクス１０に再構成することができ、その仮想ネットワークは、ノードＮ１〜Ｎ１２にそれぞれ対応する仮想ノードＰＮ１〜ＰＮ１２と、リンクＬ１〜Ｌ１３にそれぞれ対応する仮想リンクＰＬ１〜ＰＬ１３を含む。なお、以下では、説明を簡単にするために仮想ノードおよび仮想リンクを図８に示した符号で説明する。
【００５６】
実際のネットワーク２１ａでは、複数のノードＮがソースとなり、複数のノードＮがディスティネーションとなっている。したがって、このシステム３０においては、ネットワーク２１ａについて、複数のノードＮがソースとなり、複数のノードＮがディスティネーション（目的地）となる異なる複数のルートの最短経路を独立に探索する。
【００５７】
たとえば、仮想ノードＮ１をソースノードＳａとし、仮想ノードＮ５をソースノードＳｂとし、それらの宛先Ｓｄはたまたま共通で仮想ノードＮ９である場合を考える。単純にホップ数が最低の最短経路を探索すると、仮想リンクＬ９およびＬ１０が共通のルート８１および８２が選択される。ネットワーク２１ａにおける通信負荷の分散を図るためには、リンクが輻輳しない、あるいは輻輳の少ないルートを選択することが望ましい。
【００５８】
このシステム３０においては、探索パケットＳＰが通過すると、その仮想リンクＰＬの仮想コストが増す。図９に示すように、仮想ノードＮ１をオリジンとする探索パケットＳＰ１が仮想リンクＬ９およびＬ１０を、仮想ノードＮ５をオリジンとする探索パケットＳＰ５よりたまたま先に通過する。探索パケットＳＰ５の通過により仮想リンクＬ９およびＬ１０の仮想コストは増加する。たとえば、各仮想リンクＬの初期コストが「１」であるとすると、仮想リンクＬ９およびＬ１０の仮想コストは「２」になる。したがって、仮想ソースノードＮ５から仮想宛先ノードＮ９に到達した探索パケットＳＰ５の累積コスト２５ｂは、最短ホップ数の仮想リンクＬ５、Ｌ３、Ｌ９、Ｌ１０を辿った場合が「６」となり、仮想リンクＬ５、Ｌ４、Ｌ１１、Ｌ１２、Ｌ１３を辿った場合が「５」となる。したがって、仮想ソースノードＮ５については、ホップ数としては最適であるルート８２ではなく、コスト最少で別ルート８３が選択される。
【００５９】
このように、上述したシステム３０を用いた経路探索方法では、独立に複数の仮想ノードＮ１（ソースＳａ）およびＮ５（ソースＳｂ）をソースとしてルート探索をしたにもかかわらず、負荷分散が行われる。
【００６０】
図１０は、探索パケットＳＰが通過する毎に、通過した仮想リンクＬの仮想コストを１つだけ上げることを示している。仮想リンクの仮想コストを増加する方法はこれに限らない。図１１に示すように、各リンクの最大許容コスト付近で急激に仮想リンクの仮想コストを増すことも可能である。これにより、実際のネットワーク２１ａにおけるオーバーフローを回避することも可能である。
【図面の簡単な説明】
【００６１】
【図１】ルータの概略構成を示す図。
【図２】図２（ａ）はネットワーク行列の一例、図２（ｂ）は対応するネットワークの一例を示す図。
【図３】ＰＥマトリクスの構成を示す図。
【図４】経路探索のターゲットのネットワークの一例を示す図。
【図５】仮想ネットワークの一例を示す図。
【図６】探索パケットの一例を示す図。
【図７】経路探索のプロセスを示すフローチャート。
【図８】経路探索のターゲットのネットワークの一例を示す図。
【図９】経路探索の結果を模式的に示す図。
【図１０】仮想コストを増加する一例。
【図１１】仮想コストを増加する他の例。
【符号の説明】
【００６２】
１    再構成可能デバイス、  １０  ＰＥマトリクス（再構成ユニット）
３０  経路探索システム
３１  仮想ネットワーク構成ユニット
３２  探索ユニット、  ３３  コスト制御ユニット、  ３４  経路選択ユニット
３５  仮想ネットワーク
８０  ルーティングユニット
１００  ルータ
【図１】
2010041429.tif 000003
【図２】
2010041429.tif 000004
【図３】
2010041429.tif 000005
【図４】
2010041429.tif 000006
【図５】
2010041429.tif 000007
【図６】
2010041429.tif 000008
【図７】
2010041429.tif 000009
【図８】
2010041429.tif 000010
【図９】
2010041429.tif 000011
【図１０】
2010041429.tif 000012
【図１１】
2010041429.tif 000013