"CPUの利用を時間的に分割した単位であるスレッドを複数用いることによって複数の計算処理を同時に並列実行できるマルチコアCPUを用い、始点から終点までの全経路を計算する並列資源探索装置であって、ネットワーク構成、該ネットワークの各ノードの情報を格納したネットワーク情報記憶手段と、ユーザ端末から少なくとも始点及び終点を含む要求条件を取得して要求記憶手段に格納する要求受信手段と、前記始点から前記終点までの経路を計算するためのスレッドを生成するスレッド生成手段と、前記要求条件の始点を最初の中継点候補基点とし、経路記憶手段に格納する手段と、前記始点から前記終点に向かう前記基点に隣接する中継点候補までの枝基点枝の数だけ前記スレッドを生成し、該中継点候補までの経路を該経路記憶手段に追記し、新たな基点枝がある場合は、該中継点候補までのスレッドを停止し、停止した経路を利用停止として該経路記憶手段を更新する処理を前記終点まで繰り返す探索手段と、を有することを特徴とする並列資源探索装置。経路上の隣接点を格納した隣接点記憶手段を更に有し、前記探索手段は、前記隣接点記憶手段を参照して、隣接点毎に逐次新しいスレッドを生成する手段を含む請求項1記載の並列資源探索装置。経路上の隣接点を格納した隣接点記憶手段と、予め空きスレッドを格納するスレッドプールと、を更に有し、前記探索手段は、前記スレッドプールの空きスレッドの数に応じて、前記隣接点記憶手段を参照して、隣接点毎に空きスレッドからひとつを割り当てる手段を含む請求項1記載の並列資源探索装置。利用可能な資源情報を格納した利用可能資源情報記憶手段を更に有し、前記探索手段は、前記ネットワーク情報記憶手段及び前記利用可能資源情報記憶手段を参照して、生成された前記スレッドが所定の制約条件を満たすかを判定し、満たす場合のみ前記始点から生成したスレッドまでの点の経路を前記経路記憶手段に格納する手段を含む請求項1記載の並列資源探索装置。マルチコアCPUを用いて始点から終点までの全経路を計算する並列資源探索方法であって、要求受信手段が、ユーザ端末から少なくとも始点及び終点を含む要求条件を取得して要求記憶手段に格納する要求受信ステップと、探索手段が、前記要求条件の始点を最初の中継点候補基点とし、経路記憶手段に格納し、前記始点から前記終点に向かう前記基点に隣接する中継点候補までの枝基点枝の数だけ、前記始点から前記終点までの経路を計算するためのスレッドを生成し、該中継点候補までの経路を該経路記憶手段に追記し、新たな基点枝がある場合は、該中継点候補までのスレッドを停止し、停止した経路を利用停止として該経路記憶手段を更新する処理を前記終点まで繰り返す探索ステップと、を行うことを特徴とする並列資源探索方法。前記探索ステップにおいて、経路上の隣接点を格納した隣接点記憶手段を参照して、隣接点毎に逐次新しいスレッドを生成する請求項5記載の並列資源探索方法。前記探索ステップにおいて、予め空きスレッドが格納されているスレッドプールの空きスレッドの数に応じて、経路上の隣接点を格納した隣接点記憶手段を参照して、隣接点毎に空きスレッドからひとつを割り当てる請求項5記載の並列資源探索方法。前記探索ステップにおいて、前記ネットワーク情報記憶手段及び利用可能な資源情報を格納した利用可能資源情報記憶手段を参照して、生成された前記スレッドが所定の制約条件を満たすかを判定し、満たす場合のみ前記始点から生成したスレッドまでの点の経路を前記経路記憶手段に格納する請求項5記載の並列資源探索方法。請求項1乃至4のいずれか1項に記載の並列資源探索装置を構成する各手段としてコンピュータを機能させるためのプログラム。ユーザからの需要に応じてサービスとそのためのサービス設備を予約したり、提供したりするサービスの観点において、上記のように、動的な経路探索を用い、マルチコアCPUの機能を活かしたマルチスレッド経路探索方法は提案されていない。また、静的な経路探索法はそもそもそのようなサービスに適していない。本発明は、上記の点に鑑みなされたもので、マルチコアCPUの機能を活かして、始点から終点までの全経路から最適な経路を迅速に計算することが可能な並列資源探索方法及び装置及びプログラムを提供することを目的とする。上記の課題を解決するために、本発明請求項1は、マルチコアCPUを用いて始点から終点までの全経路を計算する並列資源探索装置であって、ネットワーク構成、該ネットワークの各ノードの情報を格納したネットワーク情報記憶手段と、ユーザ端末から少なくとも始点及び終点を含む要求条件を取得して要求記憶手段に格納する要求受信手段と、前記始点から前記終点までの経路を計算するためのスレッドを生成するスレッド生成手段と、前記要求条件の始点を最初の中継点候補基点とし、経路記憶手段に格納する手段と、前記始点から前記終点に向かう前記基点に隣接する中継点候補までの枝基点枝の数だけ前記スレッドを生成し、該中継点候補までの経路を該経路記憶手段に追記し、新たな基点枝がある場合は、該中継点候補までのスレッドを停止し、停止した経路を利用停止として該経路記憶手段を更新する処理を前記終点まで繰り返す探索手段と、を有する。また、本発明請求項2は、経路上の隣接点を格納した隣接点記憶手段を更に有し、前記探索手段は、前記隣接点記憶手段を参照して、隣接点毎に逐次新しいスレッドを生成する手段を含む。また、本発明請求項3は、経路上の隣接点を格納した隣接点記憶手段と、予め空きスレッドを格納するスレッドプールと、を更に有し、前記探索手段は、前記スレッドプールの空きスレッドの数に応じて、前記隣接点記憶手段を参照して、隣接点毎に空きスレッドからひとつを割り当てる手段を含む。また、本発明請求項4は、利用可能な資源情報を格納した利用可能資源情報記憶手段を更に有し、前記探索手段は、前記ネットワーク情報記憶手段及び前記利用可能資源情報記憶手段を参照して、生成された前記スレッドが所定の制約条件を満たすかを判定し、満たす場合のみ前記始点から生成したスレッドまでの点の経路を前記経路記憶手段に格納する手段を含む。本発明請求項5は、マルチコアCPUを用いて始点から終点までの全経路を計算する並列資源探索方法であって、要求受信手段が、ユーザ端末から少なくとも始点及び終点を含む要求条件を取得して要求記憶手段に格納する要求受信ステップと、探索手段が、前記要求条件の始点を最初の中継点候補基点とし、経路記憶手段に格納し、前記始点から前記終点に向かう前記基点に隣接する中継点候補までの枝基点枝の数だけ、前記始点から前記終点までの経路を計算するためのスレッドを生成し、該中継点候補までの経路を該経路記憶手段に追記し、新たな基点枝がある場合は、該中継点候補までのスレッドを停止し、停止した経路を利用停止として該経路記憶手段を更新する処理を前記終点まで繰り返す探索ステップと、を行う。また、本発明請求項6は、前記探索ステップにおいて、経路上の隣接点を格納した隣接点記憶手段を参照して、隣接点毎に逐次新しいスレッドを生成する。また、本発明請求項7は、前記探索ステップにおいて、予め空きスレッドが格納されているスレッドプールの空きスレッドの数に応じて、経路上の隣接点を格納した隣接点記憶手段を参照して、隣接点毎に空きスレッドからひとつを割り当てる。また、本発明請求項8は、前記探索ステップにおいて、前記ネットワーク情報記憶手段及び利用可能な資源情報を格納した利用可能資源情報記憶手段を参照して、生成された前記スレッドが所定の制約条件を満たすかを判定し、満たす場合のみ前記始点から生成したスレッドまでの点の経路を前記経路記憶手段に格納する。本発明請求項9は、請求項1乃至4のいずれか1項に記載の並列資源探索装置を構成する各手段としてコンピュータを機能させるためのプログラムである。上述のように、本発明では、マルチコアCPUを用いるネットワークにおいて、始点から終点の全経路探索に対し、マルチスレッド技術を適用することにより経路探索の高速化が可能である。以下図面と共に、本発明の実施の形態を説明する。[第1の実施の形態]本発明は、資源探索装置において、ネットワーク上のノード間の伝送メディアの最小物理単位に点を配置し、これらの隣接する点を接続する経路について、始点から終点までの経路を計算するスレッドを生成して起動させ、始点から終点に向かい新しい枝を発見したら、それまで立ち上げたスレッドを停止して、その地点から終点までの経路を計算するスレッドを枝の数だけ立ち上げることにより、マルチスコアCPUの機能を使い切るように経路を計算するものである。図1は、本発明の第1の実施の形態における並列資源探索装置の構成を示す。同図に示す並列資源探索装置は、ユーザ要求受信部10、経路探索部20、スレッド数管理部30、利用可能管理部40、リミテーションチェック部50、要求DB60、経路DB70,データ管理DB80から構成される。ユーザ要求受信部10は、始点や終点などの情報を含む要求条件を受信して要求DB60に格納する。経路探索部20は、要求DB60から要求を読み出して、始点と終点が一致する場合には、探索を完了させ、一致しない場合には、始点を基点枝として始点から基点枝までの経路を経路DB70に格納する。経路探索部20は、内部メモリに図2に示すようなスレッドを管理する。図2に示すように、各スレッドは、経路チェック、コストチェックを行うためのチェック手段を有する。経路探索部20は、図3aに示すように、始点から終点までの全経路をマルチコアCPUの性能を使い切るように、新しい枝の発見地点から、順に終点までの経路を計算する新しいスレッドを生成する。例えば、始点からノード2にスレッド1が生成され、始点からノード5にスレッド4が新たに生成される。ノード2からノード3に対するスレッド2、ノード4に対するスレッド3、また、ノード5からノード2に対するスレッド6、ノード5からノード6に対するスレッド5がそれぞれ新たに生成される。そして、図3bに示すように、始点から終点に向かってあるノードで新しいノードが見つかった場合はそれまでのスレッドは停止し、停止したことを示す情報フラグで経路DB70を更新し、その地点のノードから終点までの経路をスレッドの枝の数だけ起動させることで全経路を計算する。スレッド数管理部30は、経路探索部20からスレッド数を取得してデータ管理DB80に格納する。利用可能管理部40は、経路探索部20で探索された経路の資源が利用可能であるかをデータ管理DB80を参照し、利用可能時間帯、利用可能な容量等を判断する。具体的には、特開2008-301225号公報に開示されている方法等を用いることが可能である。リミテーションチェック部50は、経路DB70から経路リストを読み込み、所定の条件に基づいて、経路を整理する。具体的には、特開2008-301225公報に開示されている方法等を用いることが可能である。要求DB60は、ユーザ要求受信部10で受信した要求について、図4に示すように、受信時刻、通信路始点、通信路終点、開始時刻、終了時刻、通信容量、料金、優先度等のデータを格納する。データ管理DB80は、図5に示すように、ネットワーク構成リスト81、利用可能資源リスト82,接続行列83を格納する。ネットワーク構成リスト81は、点の識別情報、点のID,IPDIPアドレス、Ifindex、TDMスロット番号、インタフェースのメディアタイプ、インタフェースの利用可能なSwitchingCapability、インタフェースの物理容量、利用可能ラベル、ノードID,ノード種別等からなる。利用可能資源リスト82は、点の識別情報、点のID、PID、メディア、利用可能なSwitchingCapability、物理容量、利用可能ラベル、ノードID、ノード種別、時間の区切り情報時刻利用可能容量時刻を含む。接続行列83は、ネットワーク上のノード間の伝送メディアの最小物理単位を点1,2,3,...として、ノード間接続ノード内接続の可否を0接続不可、1接続可で表した表であり、各最小物理単位の1つのマスごとに図6に示す情報が格納される。接続行列の生成方法については、特開2008301225号公報に開示されている技術を用いるものとする。経路DB70は、図7に示すように、探索の進行と共に利用済みかつ終点に到達していない経路は利用停止とする。図7において、例えば、始点→枝i→基点枝kを評価枝と呼び、これらの集合を評価枝リストと呼ぶ。次に、経路探索の処理について説明する。図8は、本発明の第1の実施の形態における経路探索処理のフローチャートである。ステップ101要求受信部10が要求を受信すると、当該要求の要求条件を要求DB60に格納する。経路探索部20は、要求DB60から要求条件を読み出し、通信路始点と通信路終点が一致する場合には、探索を終了する。一致しない場合はステップ102に移行する。ステップ102経路探索部20は、通信路始点≠通信路終点である場合は、始点を基点として通信路の始点から基点枝までの経路を経路DB70に追記する。ステップ103経路探索部20は、経路DB70から始点から基点枝までの経路の中で未選択の経路を一つ選択する。ステップ104経路探索部20は、始点から基点枝までの経路毎に次の評価対象となるノードからの評価枝を探索するためにスレッドを割り当てる。当該処理は評価枝がなくなるまで繰り返す。スレッド数管理部30は、内部のスレッド数メモリ図示せずのスレッド数を加算する。スレッド割当のイメージを図9に示す。ステップ105経路探索部20は、データ管理DB80の隣接行列83を参照して、基点枝から隣接している評価枝を探索する。隣接する評価枝が無い場合はステップ111に移行し、評価枝がある場合は、始点から基点枝までの経路別に評価枝を経路DB70の評価枝リストに格納する。ステップ106ステップ105において評価枝がある場合は、経路探索部20は、経路DB70の評価枝リストから未選択の評価枝を一つ選択する。選択する評価枝が無い場合は、ステップ111に移行する。このとき、選択された評価枝については、経路DB70の評価枝リストに選択済みを表すフラグを設定するものとする。ステップ107ステップ106において、評価枝が選択された場合は、経路探索部20は、基点枝を基準として評価枝毎に評価枝の制約条件の合否を確認評価するためのスレッドを割り当てる。スレッド数管理部30は、内部のスレッド数メモリ図示せずのスレッド数を加算する。ステップ108経路探索部20は、データ管理DB80のネットワーク構成リスト81、利用可能資源リスト82を参照して所定の制約条件を満たすかを判定し、条件を満足しない場合はステップ110に移行し、満足する場合はステップ109に移行する。ステップ109経路探索部20は、始点からステップ106で選択された評価枝までの経路を経路DB70に追加する。ステップ110経路探索部20は、ステップ107で割り当てられたスレッドを開放し、スレッド数管理部30は、スレッド数メモリのスレッド数をクリアする。ステップ106に移行する。ステップ111ステップ106において、未選択の評価枝が無い場合は、始点から当該基点枝までの経路について、探索が重複しないように、利用停止として経路DB70の探索済みのため利用停止フラグに1を設定する。ステップ112経路探索部20は、それまで設定されていたスレッドを開放し、スレッド数管理部30は、スレッド数メモリのスレッド数をクリアする。ステップ113経路探索部20は、経路DB70を参照して、始点から基点枝までの経路の中で基点枝が終点と異なっている経路基点枝≠終点があるかを判定し、経路がある場合はステップ103に移行する。一方、経路が無い場合はステップ114に移行する。ステップ114経路探索部20は、経路DB70を参照して、基点枝が終点である経路があるかを判定し、ある場合には、経路ありを出力して探索を終了し、無い場合は経路なし探索失敗として探索を終了する。なお、上記のフローチャートでは、ステップ104において、始点から基点枝までの経路毎に次の評価枝を探索するためのスレッドを割り当て、さらに、ステップ107において、基点枝を基点として評価枝毎に評価枝の制約条件の合否を確認評価するためにスレッドを割り当てているが、ステップ104または、制約条件の判定を含めたスレッドの割当を行うステップ107のいずれか1つの処理を行うようにしてもよい。図10は、本発明の一実施の形態における経路DBの内容例と同DB上での処理の一例である。第1ステップ最初に始点ソースを経路DB70に設定し、経路探索途中で図9aに示す経路探索データを経路DB70に格納する。第2ステップデータ管理DB80の接続行列83を参照し、通過点1を中心に隣接している点を全て探索し、図10bの探索データを経路DB70に格納する。このとき、探索済みとなった図10aの2つの通過点1については、図10bに示すように利用停止とし、利用停止フラグを1とする。第3ステップ次に、データ管理DB80の隣接行列83を参照し、図10cに示す経路探索データを経路DB70に格納する。このとき、図10bにおいて利用停止となった通過点1に加え、2つの通過点2、1つの通過点3についても、図10cに示すように探索済みのため利用停止とし、利用停止フラグを1とする。第4ステップ次に、始点から終点だけが残るまで経路探索を繰り返し、図10dに示す経路探索データを経路リストとし、経路DB70に格納する。次に、図8のステップ104及びステップ107におけるスレッドを割り当てる際の動作を説明する。図11、図12は、本発明の一実施の形態におけるスレッド割当のシーケンスチャートである。ステップ201要求受信部10が探索開始処理の要求を受け取ると、当該要求を要求DB60に格納したことを経路探索部20に通知する。ステップ202経路探索部20は、受信した要求について、始点と終点が同一かを判定し、同一である場合は探索処理を終了する。ステップ203経路探索部20は、始点を中継点として経路DB70に設定すると共に、当該中継点が選択済みであることを示すフラグをたてる。ステップ204経路探索部20は、データ管理DB80の接続行列83を参照し、隣接点を探索する。ステップ205接続行列83を参照することにより隣接点がある場合はステップ206に移行し、隣接点が無い場合はステップ209に移行する。ステップ206経路探索部20は、隣接点を中継点候補として経路DB70を更新する。ステップ207経路探索部20は、スレッド数管理部30に問い合わせ、その時点におけるスレッド数を取得する。ステップ208経路探索部20は、その時点で起動しているスレッド数が所定の数N未満であれば、スレッドを起動させ、スレッド数管理部30にスレッド数の更新を指示する。一方、起動しているスレッド数が所定数以上である場合は、経路チェック及びコストチェックを行う。上記のステップ204以降の処理を隣接点がなくなるまで繰り返す。ステップ209経路探索部20は、選択済みの中継点を選択済みとして選択済みのフラグを立てる。ステップ210経路探索部20は、経路DB70にスレッドが起動できなかった経路があるかを判定し、ある場合には、ステップ211に移行し、無い場合は、次の起動スレッドを待機する。ステップ211経路探索部20は、経路DB70から未選択の中継点を探索する。ステップ212未選択の中継点候補が見つかった場合は、ステップ213に移行し、ない場合には、起動スレッドの待ち合わせを行う。ステップ213未選択の中継点が見つかった場合は、要求DB60に終点を問い合わせる。ステップ214経路探索部20は、未選択、かつ、利用可能で終点以外の未選択の中継点があるかを判定し、無い場合は起動スレッドを待ち合わせ、ある場合はステップ215に移行する。ステップ215ステップ214において、未選択の中継点がある場合は、未選択の中継点を選択し、選択した中継点を選択済みとして経路DB70を更新する。上記のステップ204からステップ215までの処理を経路状態が確定するまで繰り返す。ステップ216次に、利用可能管理部40は、経路探索部20内部の各経路探索スレッドについて、経路DB70及びデータ管理DB80の利用可能資源リスト82を参照し、チェック用の情報を取得し、設定された経路状態が利用可能であるかを判定する。判定の方法としては、例えば、特開2008301225号公報に開示されている手法を用いるものとする。ステップ217さらに、各経路探索スレッドについて、経路DB70、データ管理DB80のネットワーク構成リスト81及び利用可能資源リスト82を参照し、チェック用の情報を取得し、コストチェックを行う。判定の方法としては、例えば、特開2008301225号公報に開示されている手法を用いるものとする。ステップ218この時点で生成されている各スレッドのチェック手段において、データ管理DB80を参照して、所定の条件に基づいて、経路チェックとコストチェックを行い、双方チェックが充足している場合には、経路DB70にチェック結果を反映し、隣接点を中継点情報として更新する。充足していない場合には、チェック結果と、隣接点の利用を停止し、当該中継点候補に利用停止のフラグを付与して経路DB70を更新し、経路探索処理を終了する。ここで、経路チェックとは、例えば、時刻Xから時刻Yの間において、帯域Zが空いているか否かを確認する、といったチェックを指す。コストチェックは、コストチェックアルゴリズムを用いて、データ管理DB80を参照し、経路チェックとして条件を満足するか否かを確認し、満足する隣接点についてのコストチェックを行う。上記のチェックにおいて、コストチェックより経路チェックを優先させることで、演算処理が必要なコストチェックでは、チェック対象となる数が少なくて済み、演算時間が短縮される。ステップ219各経路探索スレッドにおいて、要求DB60を参照し、終点情報を取得して、中継点と終点が一致する場合には、当該探索を終了し、一致しない場合は、ステップ201に移行する。なお、上記の処理に加え、リミテーションチェック部50による処理を行い、最終的に予約を確定回路として出力するようにしてもよい。なお、リミテーションチェック部50の処理は、特開2008301225号公報に開示されている技術を用いるものとする。[第2の実施の形態]前述の第1の実施の形態では、隣接点毎に新しいスレッドを生成した図8:ステップ105。この方法は、予め所要スレッド数を予測できない計算には有効であるが、スレッド生成処理に時間がかかる。本実施の形態では、予めスレッドプールを用意しておき、隣接点ごとに新しいスレッドを割り当てる。なお、本実施の形態における装置構成は、第1の実施の形態と同様である。図12は、本発明の第2の実施の形態におけるスレッドの起動及び生成を説明するための図である。同図aに示すように、初期状態では、経路探索部20がスレッドプール内のN個のスレッドを管理し、セマフォが各スレッドの動きを停止する。なお、セマフォはN個のスレッドがあることを認識しているものとする。次に、同図bに示すように、経路探索部20がリクエストに応じてスレッドプール内の1個のスレッドを払い出す。このとき、セマフォは開放されているものとし、セマフォは残りN-1個のスレッドがあることを認識している。この時点でM個のスレッドをスレッドプールから払い出したものとすると、総計M1個のスレッドを払い出したことになる。そして、同図cに示すように、利用終了した1個のスレッドがスレッドプールに返却されると、セマフォは残りN-M個のスレッドがあることを把握する。上記の処理のためにセマフォと経路探索部20は以下のような処理を行う。図13は、本発明の第2の実施の形態におけるスレッド割当処理のフローチャートである。まず、セマフォは、リクエストを取得すると、スレッドプールの空きスレッド数を確認しステップ301、リクエストされた個数分の残りが無い場合は、スレッドの割当を保留しステップ302、残りがある場合には、経路探索部20はリクエストで指定された分のスレッドを割り当てるステップ303。なお、図1に示す並列資源探索装置の構成要素の第1の実施の形態及び第2の実施の形態に示した動作をプログラムとして構築し、並列資源探索装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更応用が可能である。"