並列資源探索方法及び装置及びプログラム
【課題】 マルチコアCPUの機能を活かして、始点から終点までの全経路を計算する。
【解決手段】 本発明は、少なくとも始点及び終点を含む要求条件を取得して要求記憶手段に格納し、始点を基点として、該始点から基点枝までの経路を経路記憶手段に追記し、始点から該基点枝までの経路の中で終点に向かう未選択の経路の点を、ネットワーク構成、該ネットワークの各ノードの情報を格納したネットワーク情報記憶手段から選択し、選択した経路の点の枝の数だけスレッドを生成して、該始点から生成したスレッドまでの点の経路を経路記憶手段に追記し、新しい枝が見つかった場合は、それまでのスレッドを停止し、停止した経路を該経路記憶手段から削除する処理を終点まで繰り返す。
【解決手段】 本発明は、少なくとも始点及び終点を含む要求条件を取得して要求記憶手段に格納し、始点を基点として、該始点から基点枝までの経路を経路記憶手段に追記し、始点から該基点枝までの経路の中で終点に向かう未選択の経路の点を、ネットワーク構成、該ネットワークの各ノードの情報を格納したネットワーク情報記憶手段から選択し、選択した経路の点の枝の数だけスレッドを生成して、該始点から生成したスレッドまでの点の経路を経路記憶手段に追記し、新しい枝が見つかった場合は、それまでのスレッドを停止し、停止した経路を該経路記憶手段から削除する処理を終点まで繰り返す。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、並列資源探索方法及び装置及びプログラムに係り、特に、マルチコアCPUを用いて始点から終点に至る経路探索技術における並列資源探索方法及び装置及びプログラムに関する。
【背景技術】
【０００２】
経路探索方法として、ダイクストラ法に代表される動的な経路探索法と、整数計画法に代表される静的な経路探索法がある。
【０００３】
動的な経路探索の大半は、始点から終点の計算途中において、始点から計算途中の最適な経路を一つに絞り込む特徴を有する。すなわち、最適とはならない経路候補は廃棄される、もしくは、その計算処理をペンディングされる。つまり、動的な経路探索は常に、始点から計算途中の一つだけの経路について計算しており、一つに絞るための選択ポリシーは探索開始時に決まっている。
【０００４】
動的な経路探索は、主にユーザやオペレータからの需要に応じてサービスとそのためのサービス設備を素早く予約したり、提供したりするために利用される。それゆえ、サービス設備の利用量の最適性よりも提供処理の迅速性が重要であり、上記のアプローチで十分に満足されていた。すなわち、動的な経路探索において、始点から終点の全ての経路候補群を探索する必要性がなかった（例えば、非特許文献１、２参照）。
【０００５】
なお、技術的には動的な経路探索を用いることにより、始点から終点の全ての経路候補群を探索することは可能である（例えば、特許文献１参照）。
【０００６】
また、始点から終点の全ての経路候補群を求めた場合、全ての経路候補群の中から、ある選択ポリシーに基づいて最適な経路候補を探索することは可能である。特に、選択ポリシーが以下のような複数の条件から構成される場合、上記のように全ての経路候補を求めることが必要である。
【０００７】
・条件の例１：始点から終点までの利用可能な帯域幅／量；
・条件の例２：始点から終点までの伝搬遅延時間；
・条件の例３：経路の利用可能な時間帯；
上記のような場合の方が、始点から終点間の経路の全体的な最適化に適する。しかし、ネットワークにおける全体的な経路の最適化の手法は、主に静的な経路探索（＝整数計画問題）によって実行されてきた。静的な経路探索はネットワーク規模に応じて数日に及ぶ膨大な計算時間を要するため、数か月先や数年先のネットワーク構成像の事前設計などに利用される。
【０００８】
昨今、CPUについては、シングルコアCPUからマルチコアCPUにCPU構成が変わってきている。静的な経路探索には、マルチコアCPUの機能を活かしたマルチスレッド経路探索方法が提案されており、既にそれらを実装したソフトウェアが販売されている。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００８−３０１２２５号公報
【非特許文献】
【００１０】
【非特許文献１】藤澤克樹、宮元裕一郎、久保幹雄「最短経路問題」社団法人日本オペレーションズ・リサーチ学会、オペレーションズ・リサーチ11月号Vol.54 No.11, pp. 696-699, 2009/11/01.
【非特許文献２】安井雄一郎、藤澤克樹、笹島啓史、後藤和茂、宮元裕一郎、「大規模最短路問題に対するダイクストラ法の高速化」日本オペレーションズ・リサーチ学会、秋季研究発表会アブストラクト集 2008、pp.314-315, 2009-09-10.
【発明の概要】
【発明が解決しようとする課題】
【００１１】
ユーザからの需要に応じてサービスとそのためのサービス設備を予約したり、提供したりするサービスの観点において、上記のように、動的な経路探索を用い、マルチコアCPUの機能を活かしたマルチスレッド経路探索方法は提案されていない。また、静的な経路探索法はそもそもそのようなサービスに適していない。
【００１２】
本発明は、上記の点に鑑みなされたもので、マルチコアCPUの機能を活かして、始点から終点までの全経路から最適な経路を迅速に計算することが可能な並列資源探索方法及び装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記の課題を解決するために、本発明（請求項１）は、マルチコアCPUを用いて始点から終点までの全経路を計算する並列資源探索装置であって、
ネットワーク構成、該ネットワークの各ノードの情報を格納したネットワーク情報記憶手段と、
ユーザ端末から少なくとも始点及び終点を含む要求条件を取得して要求記憶手段に格納する要求受信手段と、
前記始点から前記終点までの経路を計算するためのスレッドを生成するスレッド生成手段と、
前記要求条件の始点を最初の中継点候補（基点）とし、経路記憶手段に格納する手段と、
前記始点から前記終点に向かう前記基点に隣接する中継点候補までの枝（基点枝）の数だけ前記スレッドを生成し、該中継点候補までの経路を該経路記憶手段に追記し、新たな基点枝がある場合は、該中継点候補までのスレッドを停止し、停止した経路を利用停止として該経路記憶手段を更新する処理を前記終点まで繰り返す探索手段と、
を有する。
【００１４】
また、本発明（請求項２）は、経路上の隣接点を格納した隣接点記憶手段を更に有し、
前記探索手段は、
前記隣接点記憶手段を参照して、隣接点毎に逐次新しいスレッドを生成する手段を含む。
【００１５】
また、本発明（請求項３）は、経路上の隣接点を格納した隣接点記憶手段と、
予め空きスレッドを格納するスレッドプールと、を更に有し、
前記探索手段は、
前記スレッドプールの空きスレッドの数に応じて、前記隣接点記憶手段を参照して、隣接点毎に空きスレッドからひとつを割り当てる手段を含む。
【００１６】
また、本発明（請求項４）は、利用可能な資源情報を格納した利用可能資源情報記憶手段を更に有し、
前記探索手段は、
前記ネットワーク情報記憶手段及び前記利用可能資源情報記憶手段を参照して、生成された前記スレッドが所定の制約条件を満たすかを判定し、満たす場合のみ前記始点から生成したスレッドまでの点の経路を前記経路記憶手段に格納する手段を含む。
【００１７】
本発明（請求項５）は、マルチコアCPUを用いて始点から終点までの全経路を計算する並列資源探索方法であって、
要求受信手段が、ユーザ端末から少なくとも始点及び終点を含む要求条件を取得して要求記憶手段に格納する要求受信ステップと、
探索手段が、前記要求条件の始点を最初の中継点候補（基点）とし、経路記憶手段に格納し、
前記始点から前記終点に向かう前記基点に隣接する中継点候補までの枝（基点枝）の数だけ、前記始点から前記終点までの経路を計算するためのスレッドを生成し、該中継点候補までの経路を該経路記憶手段に追記し、新たな基点枝がある場合は、該中継点候補までのスレッドを停止し、停止した経路を利用停止として該経路記憶手段を更新する処理を前記終点まで繰り返す探索ステップと、を行う。
【００１８】
また、本発明（請求項６）は、前記探索ステップにおいて、
経路上の隣接点を格納した隣接点記憶手段を参照して、隣接点毎に逐次新しいスレッドを生成する。
【００１９】
また、本発明（請求項７）は、前記探索ステップにおいて、
予め空きスレッドが格納されているスレッドプールの空きスレッドの数に応じて、経路上の隣接点を格納した隣接点記憶手段を参照して、隣接点毎に空きスレッドからひとつを割り当てる。
【００２０】
また、本発明（請求項８）は、前記探索ステップにおいて、
前記ネットワーク情報記憶手段及び利用可能な資源情報を格納した利用可能資源情報記憶手段を参照して、生成された前記スレッドが所定の制約条件を満たすかを判定し、満たす場合のみ前記始点から生成したスレッドまでの点の経路を前記経路記憶手段に格納する。
【００２１】
本発明（請求項９）は、請求項１乃至４のいずれか１項に記載の並列資源探索装置を構成する各手段としてコンピュータを機能させるためのプログラムである。
【発明の効果】
【００２２】
上述のように、本発明では、マルチコアCPUを用いるネットワークにおいて、始点から終点の全経路探索に対し、マルチスレッド技術を適用することにより経路探索の高速化が可能である。
【図面の簡単な説明】
【００２３】
【図１】本発明の第１の実施の形態における並列資源探索装置の構成図である。
【図２】本発明の第１の実施の形態における経路探索部内部のスレッドの状況である。
【図３】本発明の第１の実施の形態におけるスレッドの生成による経路探索を示す図である。
【図４】本発明の第１の実施の形態における要求データベースの一例である。
【図５】本発明の第１の実施の形態におけるデータ管理ＤＢの構成図である。
【図６】本発明の第１の実施の形態における隣接行列の一例である。
【図７】本発明の第１の実施の形態における経路ＤＢの遷移例である。
【図８】本発明の第１の実施の形態における岐路探索処理のフローチャートである。
【図９】本発明の第１の実施の形態におけるスレッド割当の例である。
【図１０】本発明の第１の実施の形態における経路ＤＢの内容例と同ＤＢ上の処理の一例である。
【図１１】本発明の第１の実施の形態におけるスレッド割当のシーケンスチャート（その１）である。
【図１２】本発明の第１の実施の形態におけるスレッド割当のシーケンスチャート（その２）である。
【図１３】本発明の第２の実施の形態におけるスレッド起動及び生成を説明するための図である。
【図１４】本発明の第２の実施の形態におけるスレッド割当処理のフローチャートである。
【発明を実施するための形態】
【００２４】
以下図面と共に、本発明の実施の形態を説明する。
【００２５】
［第１の実施の形態］
本発明は、資源探索装置において、ネットワーク上のノード間の伝送メディアの最小物理単位に点を配置し、これらの隣接する点を接続する経路について、始点から終点までの経路を計算するスレッドを生成して起動させ、始点から終点に向かい新しい枝を発見したら、それまで立ち上げたスレッドを停止して、その地点から終点までの経路を計算するスレッドを枝の数だけ立ち上げることにより、マルチスコアCPUの機能を使い切るように経路を計算するものである。
【００２６】
図１は、本発明の第１の実施の形態における並列資源探索装置の構成を示す。
【００２７】
同図に示す並列資源探索装置は、ユーザ要求受信部１０、経路探索部２０、スレッド数管理部３０、利用可能管理部４０、リミテーションチェック部５０、要求ＤＢ６０、経路ＤＢ７０，データ管理ＤＢ８０から構成される。
【００２８】
ユーザ要求受信部１０は、始点や終点などの情報を含む要求条件を受信して要求ＤＢ６０に格納する。
【００２９】
経路探索部２０は、要求ＤＢ６０から要求を読み出して、始点と終点が一致する場合には、探索を完了させ、一致しない場合には、始点を基点枝として始点から基点枝までの経路を経路ＤＢ７０に格納する。経路探索部２０は、内部（メモリ）に図２に示すようなスレッドを管理する。図２に示すように、各スレッドは、経路チェック、コストチェックを行うためのチェック手段を有する。経路探索部２０は、図３（ａ）に示すように、始点から終点までの全経路をマルチコアＣＰＵの性能を使い切るように、新しい枝の発見地点から、順に終点までの経路を計算する新しいスレッドを生成する。例えば、始点からノード"２"にスレッド"１"が生成され、始点からノード"５"にスレッド"４"が新たに生成される。ノード"２"からノード"３"に対するスレッド"２"、ノード"４"に対するスレッド"３"、また、ノード"５"からノード"２"に対するスレッド"６"、ノード"５"からノード"６"に対するスレッド"５"がそれぞれ新たに生成される。そして、図３（ｂ）に示すように、始点から終点に向かってあるノードで新しいノードが見つかった場合はそれまでのスレッドは停止し、停止したことを示す情報（フラグ）で経路ＤＢ７０を更新し、その地点のノードから終点までの経路をスレッドの枝の数だけ起動させることで全経路を計算する。
【００３０】
スレッド数管理部３０は、経路探索部２０からスレッド数を取得してデータ管理ＤＢ８０に格納する。
【００３１】
利用可能管理部４０は、経路探索部２０で探索された経路の資源が利用可能であるかをデータ管理ＤＢ８０を参照し、利用可能時間帯、利用可能な容量等を判断する。具体的には、特開２００８−３０１２２５号公報に開示されている方法等を用いることが可能である。
【００３２】
リミテーションチェック部５０は、経路ＤＢ７０から経路リストを読み込み、所定の条件に基づいて、経路を整理する。具体的には、特開２００８−３０１２２５公報に開示されている方法等を用いることが可能である。
【００３３】
要求ＤＢ６０は、ユーザ要求受信部１０で受信した要求について、図４に示すように、受信時刻、通信路始点、通信路終点、開始時刻、終了時刻、通信容量、料金、優先度等のデータを格納する。
【００３４】
データ管理ＤＢ８０は、図５に示すように、ネットワーク構成リスト８１、利用可能資源リスト８２，接続行列８３を格納する。
【００３５】
ネットワーク構成リスト８１は、点の識別情報、点のＩＤ，ＩＰＤ（IPアドレス、Ifindex、TDMスロット番号）、インタフェースのメディアタイプ、インタフェースの利用可能なSwitching Capability、インタフェースの物理容量、利用可能ラベル、ノードＩＤ，ノード種別等からなる。
【００３６】
利用可能資源リスト８２は、点の識別情報、点のID、PID、メディア、利用可能なSwitching Capability、物理容量、利用可能ラベル、ノードID、ノード種別、時間の区切り情報（時刻＋利用可能容量＋時刻）を含む。
【００３７】
接続行列８３は、ネットワーク上のノード間の伝送メディアの最小物理単位を点（１，２，３，…）として、ノード間接続・ノード内接続の可否を"０"（接続不可）、"１"（接続可）で表した表であり、各最小物理単位の１つのマスごとに図６に示す情報が格納される。接続行列の生成方法については、特開2008-301225号公報に開示されている技術を用いるものとする。
【００３８】
経路ＤＢ７０は、図７に示すように、探索の進行と共に利用済みかつ終点に到達していない経路は利用停止とする。図７において、例えば、「始点→枝ｉ→基点枝ｋ」を評価枝と呼び、これらの集合を評価枝リストと呼ぶ。
【００３９】
次に、経路探索の処理について説明する。
【００４０】
図８は、本発明の第１の実施の形態における経路探索処理のフローチャートである。
【００４１】
ステップ１０１） 要求受信部１０が要求を受信すると、当該要求の要求条件を要求ＤＢ６０に格納する。経路探索部２０は、要求ＤＢ６０から要求条件を読み出し、通信路始点と通信路終点が一致する場合には、探索を終了する。一致しない場合はステップ１０２に移行する。
【００４２】
ステップ１０２） 経路探索部２０は、通信路始点≠通信路終点である場合は、始点を基点として通信路の始点から基点枝までの経路を経路ＤＢ７０に追記する。
【００４３】
ステップ１０３） 経路探索部２０は、経路ＤＢ７０から始点から基点枝までの経路の中で未選択の経路を一つ選択する。
【００４４】
ステップ１０４） 経路探索部２０は、始点から基点枝までの経路毎に次の評価対象となるノードからの評価枝を探索するためにスレッドを割り当てる。当該処理は評価枝がなくなるまで繰り返す。スレッド数管理部３０は、内部のスレッド数メモリ（図示せず）のスレッド数を加算する。スレッド割当のイメージを図９に示す。
【００４５】
ステップ１０５） 経路探索部２０は、データ管理ＤＢ８０の隣接行列８３を参照して、基点枝から隣接している評価枝を探索する。隣接する評価枝が無い場合はステップ１１１に移行し、評価枝がある場合は、始点から基点枝までの経路別に評価枝を経路ＤＢ７０の評価枝リストに格納する。
【００４６】
ステップ１０６） ステップ１０５において評価枝がある場合は、経路探索部２０は、経路ＤＢ７０の評価枝リストから未選択の評価枝を一つ選択する。選択する評価枝が無い場合は、ステップ１１１に移行する。このとき、選択された評価枝については、経路ＤＢ７０の評価枝リストに選択済みを表すフラグを設定するものとする。
【００４７】
ステップ１０７） ステップ１０６において、評価枝が選択された場合は、経路探索部２０は、基点枝を基準として評価枝毎に評価枝の制約条件の合否を確認・評価するためのスレッドを割り当てる。スレッド数管理部３０は、内部のスレッド数メモリ（図示せず）のスレッド数を加算する。
【００４８】
ステップ１０８） 経路探索部２０は、データ管理ＤＢ８０のネットワーク構成リスト８１、利用可能資源リスト８２を参照して所定の制約条件を満たすかを判定し、条件を満足しない場合はステップ１１０に移行し、満足する場合はステップ１０９に移行する。
【００４９】
ステップ１０９） 経路探索部２０は、始点からステップ１０６で選択された評価枝までの経路を経路ＤＢ７０に追加する。
【００５０】
ステップ１１０） 経路探索部２０は、ステップ１０７で割り当てられたスレッドを開放し、スレッド数管理部３０は、スレッド数メモリのスレッド数をクリアする。ステップ１０６に移行する。
【００５１】
ステップ１１１） ステップ１０６において、未選択の評価枝が無い場合は、始点から当該基点枝までの経路について、探索が重複しないように、利用停止として経路ＤＢ７０の探索済みのため利用停止フラグに「１」を設定する。
【００５２】
ステップ１１２） 経路探索部２０は、それまで設定されていたスレッドを開放し、スレッド数管理部３０は、スレッド数メモリのスレッド数をクリアする。
【００５３】
ステップ１１３） 経路探索部２０は、経路ＤＢ７０を参照して、始点から基点枝までの経路の中で基点枝が終点と異なっている経路（基点枝≠終点）があるかを判定し、経路がある場合はステップ１０３に移行する。一方、経路が無い場合はステップ１１４に移行する。
【００５４】
ステップ１１４） 経路探索部２０は、経路ＤＢ７０を参照して、基点枝が終点である経路があるかを判定し、ある場合には、「経路あり」を出力して探索を終了し、無い場合は「経路なし」（探索失敗）として探索を終了する。
【００５５】
なお、上記のフローチャートでは、ステップ１０４において、始点から基点枝までの経路毎に次の評価枝を探索するためのスレッドを割り当て、さらに、ステップ１０７において、基点枝を基点として評価枝毎に評価枝の制約条件の合否を確認・評価するためにスレッドを割り当てているが、ステップ１０４または、制約条件の判定を含めたスレッドの割当を行うステップ１０７のいずれか１つの処理を行うようにしてもよい。
【００５６】
図１０は、本発明の一実施の形態における経路ＤＢの内容例と同ＤＢ上での処理の一例である。
【００５７】
第１ステップ） 最初に始点（ソース）を経路ＤＢ７０に設定し、経路探索途中で図９（ａ）に示す経路探索データを経路ＤＢ７０に格納する。
【００５８】
第２ステップ） データ管理ＤＢ８０の接続行列８３を参照し、「通過点１」を中心に隣接している点を全て探索し、図１０（ｂ）の探索データを経路ＤＢ７０に格納する。このとき、探索済みとなった図１０（ａ）の２つの「通過点１」については、図１０（ｂ）に示すように利用停止とし、利用停止フラグを「１」とする。
【００５９】
第３ステップ） 次に、データ管理ＤＢ８０の隣接行列８３を参照し、図１０（ｃ）に示す経路探索データを経路ＤＢ７０に格納する。このとき、図１０（ｂ）において利用停止となった「通過点１」に加え、２つの「通過点２」、１つの「通過点３」についても、図１０（ｃ）に示すように探索済みのため利用停止とし、利用停止フラグを「１」とする。
【００６０】
第４ステップ） 次に、始点から終点だけが残るまで経路探索を繰り返し、図１０（ｄ）に示す経路探索データを経路リストとし、経路ＤＢ７０に格納する。
【００６１】
次に、図８のステップ１０４及びステップ１０７におけるスレッドを割り当てる際の動作を説明する。
【００６２】
図１１、図１２は、本発明の一実施の形態におけるスレッド割当のシーケンスチャートである。
【００６３】
ステップ２０１） 要求受信部１０が探索開始処理の要求を受け取ると、当該要求を要求ＤＢ６０に格納したことを経路探索部２０に通知する。
【００６４】
ステップ２０２） 経路探索部２０は、受信した要求について、始点と終点が同一かを判定し、同一である場合は探索処理を終了する。
【００６５】
ステップ２０３） 経路探索部２０は、始点を中継点として経路ＤＢ７０に設定すると共に、当該中継点が選択済みであることを示すフラグをたてる。
【００６６】
ステップ２０４） 経路探索部２０は、データ管理ＤＢ８０の接続行列８３を参照し、隣接点を探索する。
【００６７】
ステップ２０５） 接続行列８３を参照することにより隣接点がある場合はステップ２０６に移行し、隣接点が無い場合はステップ２０９に移行する。
【００６８】
ステップ２０６） 経路探索部２０は、隣接点を中継点候補として経路ＤＢ７０を更新する。
【００６９】
ステップ２０７） 経路探索部２０は、スレッド数管理部３０に問い合わせ、その時点におけるスレッド数を取得する。
【００７０】
ステップ２０８） 経路探索部２０は、その時点で起動しているスレッド数が所定の数Ｎ未満であれば、スレッドを起動させ、スレッド数管理部３０にスレッド数の更新を指示する。一方、起動しているスレッド数が所定数以上である場合は、経路チェック及びコストチェックを行う。
【００７１】
上記のステップ２０４以降の処理を隣接点がなくなるまで繰り返す。
【００７２】
ステップ２０９） 経路探索部２０は、選択済みの中継点を選択済みとして選択済みのフラグを立てる。
【００７３】
ステップ２１０） 経路探索部２０は、経路ＤＢ７０にスレッドが起動できなかった経路があるかを判定し、ある場合には、ステップ２１１に移行し、無い場合は、次の起動スレッドを待機する。
【００７４】
ステップ２１１） 経路探索部２０は、経路ＤＢ７０から未選択の中継点を探索する。
【００７５】
ステップ２１２） 未選択の中継点候補が見つかった場合は、ステップ２１３に移行し、ない場合には、起動スレッドの待ち合わせを行う。
【００７６】
ステップ２１３） 未選択の中継点が見つかった場合は、要求ＤＢ６０に終点を問い合わせる。
【００７７】
ステップ２１４） 経路探索部２０は、未選択、かつ、利用可能で終点以外の未選択の中継点があるかを判定し、無い場合は起動スレッドを待ち合わせ、ある場合はステップ２１５に移行する。
【００７８】
ステップ２１５） ステップ２１４において、未選択の中継点がある場合は、未選択の中継点を選択し、選択した中継点を選択済みとして経路ＤＢ７０を更新する。
【００７９】
上記のステップ２０４からステップ２１５までの処理を経路状態が確定するまで繰り返す。
【００８０】
ステップ２１６） 次に、利用可能管理部４０は、経路探索部２０内部の各経路探索スレッドについて、経路ＤＢ７０及びデータ管理ＤＢ８０の利用可能資源リスト８２を参照し、チェック用の情報を取得し、設定された経路状態が利用可能であるかを判定する。判定の方法としては、例えば、特開2008-301225号公報に開示されている手法を用いるものとする。
【００８１】
ステップ２１７） さらに、各経路探索スレッドについて、経路ＤＢ７０、データ管理ＤＢ８０のネットワーク構成リスト８１及び利用可能資源リスト８２を参照し、チェック用の情報を取得し、コストチェックを行う。判定の方法としては、例えば、特開2008-301225号公報に開示されている手法を用いるものとする。
【００８２】
ステップ２１８） この時点で生成されている各スレッドのチェック手段において、データ管理ＤＢ８０を参照して、所定の条件に基づいて、経路チェックとコストチェックを行い、双方チェックが充足している場合には、経路ＤＢ７０にチェック結果を反映し、隣接点を中継点情報として更新する。充足していない場合には、チェック結果と、隣接点の利用を停止し、当該中継点候補に利用停止のフラグを付与して経路ＤＢ７０を更新し、経路探索処理を終了する。ここで、経路チェックとは、例えば、時刻Ｘから時刻Ｙの間において、帯域Ｚが空いているか否かを確認する、といったチェックを指す。コストチェックは、コストチェックアルゴリズムを用いて、データ管理ＤＢ８０を参照し、経路チェックとして条件を満足するか否かを確認し、満足する隣接点についてのコストチェックを行う。上記のチェックにおいて、コストチェックより経路チェックを優先させることで、演算処理が必要なコストチェックでは、チェック対象となる数が少なくて済み、演算時間が短縮される。
【００８３】
ステップ２１９） 各経路探索スレッドにおいて、要求ＤＢ６０を参照し、終点情報を取得して、中継点と終点が一致する場合には、当該探索を終了し、一致しない場合は、ステップ２０１に移行する。
【００８４】
なお、上記の処理に加え、リミテーションチェック部５０による処理を行い、最終的に予約を確定回路として出力するようにしてもよい。なお、リミテーションチェック部５０の処理は、特開2008-301225号公報に開示されている技術を用いるものとする。
【００８５】
［第２の実施の形態］
前述の第1の実施の形態では、隣接点毎に新しいスレッドを生成した（図８：ステップ１０５）。この方法は、予め所要スレッド数を予測できない計算には有効であるが、スレッド生成処理に時間がかかる。
【００８６】
本実施の形態では、予めスレッドプールを用意しておき、隣接点ごとに新しいスレッドを割り当てる。なお、本実施の形態における装置構成は、第１の実施の形態と同様である。
【００８７】
図１２は、本発明の第２の実施の形態におけるスレッドの起動及び生成を説明するための図である。
【００８８】
同図（ａ）に示すように、初期状態では、経路探索部２０がスレッドプール内のＮ個のスレッドを管理し、セマフォが各スレッドの動きを停止する。なお、セマフォはＮ個のスレッドがあることを認識しているものとする。
【００８９】
次に、同図（ｂ）に示すように、経路探索部２０がリクエストに応じてスレッドプール内の1個のスレッドを払い出す。このとき、セマフォは開放されているものとし、セマフォは残りＮ−1個のスレッドがあることを認識している。
【００９０】
この時点でＭ個のスレッドをスレッドプールから払い出したものとすると、総計Ｍ＋１個のスレッドを払い出したことになる。
【００９１】
そして、同図（ｃ）に示すように、利用終了した1個のスレッドがスレッドプールに返却されると、セマフォは残りＮ−Ｍ個のスレッドがあることを把握する。
【００９２】
上記の処理のためにセマフォと経路探索部２０は以下のような処理を行う。
【００９３】
図１３は、本発明の第２の実施の形態におけるスレッド割当処理のフローチャートである。
【００９４】
まず、セマフォは、リクエストを取得すると、スレッドプールの空きスレッド数を確認し（ステップ３０１）、リクエストされた個数分の残りが無い場合は、スレッドの割当を保留し（ステップ３０２）、残りがある場合には、経路探索部２０はリクエストで指定された分のスレッドを割り当てる（ステップ３０３）。
【００９５】
なお、図１に示す並列資源探索装置の構成要素の第１の実施の形態及び第２の実施の形態に示した動作をプログラムとして構築し、並列資源探索装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００９６】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００９７】
１０ ユーザ要求受信部
２０ 経路探索部
３０ スレッド数管理部
４０ 利用可能管理部
５０ リミテーションチェック部
６０ 要求ＤＢ（データベース）
７０ 経路ＤＢ
８０ データ管理部
８１ ネットワーク構成リスト
８２ 利用可能資源リスト
８３ 接続行列
【技術分野】
【０００１】
本発明は、並列資源探索方法及び装置及びプログラムに係り、特に、マルチコアCPUを用いて始点から終点に至る経路探索技術における並列資源探索方法及び装置及びプログラムに関する。
【背景技術】
【０００２】
経路探索方法として、ダイクストラ法に代表される動的な経路探索法と、整数計画法に代表される静的な経路探索法がある。
【０００３】
動的な経路探索の大半は、始点から終点の計算途中において、始点から計算途中の最適な経路を一つに絞り込む特徴を有する。すなわち、最適とはならない経路候補は廃棄される、もしくは、その計算処理をペンディングされる。つまり、動的な経路探索は常に、始点から計算途中の一つだけの経路について計算しており、一つに絞るための選択ポリシーは探索開始時に決まっている。
【０００４】
動的な経路探索は、主にユーザやオペレータからの需要に応じてサービスとそのためのサービス設備を素早く予約したり、提供したりするために利用される。それゆえ、サービス設備の利用量の最適性よりも提供処理の迅速性が重要であり、上記のアプローチで十分に満足されていた。すなわち、動的な経路探索において、始点から終点の全ての経路候補群を探索する必要性がなかった（例えば、非特許文献１、２参照）。
【０００５】
なお、技術的には動的な経路探索を用いることにより、始点から終点の全ての経路候補群を探索することは可能である（例えば、特許文献１参照）。
【０００６】
また、始点から終点の全ての経路候補群を求めた場合、全ての経路候補群の中から、ある選択ポリシーに基づいて最適な経路候補を探索することは可能である。特に、選択ポリシーが以下のような複数の条件から構成される場合、上記のように全ての経路候補を求めることが必要である。
【０００７】
・条件の例１：始点から終点までの利用可能な帯域幅／量；
・条件の例２：始点から終点までの伝搬遅延時間；
・条件の例３：経路の利用可能な時間帯；
上記のような場合の方が、始点から終点間の経路の全体的な最適化に適する。しかし、ネットワークにおける全体的な経路の最適化の手法は、主に静的な経路探索（＝整数計画問題）によって実行されてきた。静的な経路探索はネットワーク規模に応じて数日に及ぶ膨大な計算時間を要するため、数か月先や数年先のネットワーク構成像の事前設計などに利用される。
【０００８】
昨今、CPUについては、シングルコアCPUからマルチコアCPUにCPU構成が変わってきている。静的な経路探索には、マルチコアCPUの機能を活かしたマルチスレッド経路探索方法が提案されており、既にそれらを実装したソフトウェアが販売されている。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００８−３０１２２５号公報
【非特許文献】
【００１０】
【非特許文献１】藤澤克樹、宮元裕一郎、久保幹雄「最短経路問題」社団法人日本オペレーションズ・リサーチ学会、オペレーションズ・リサーチ11月号Vol.54 No.11, pp. 696-699, 2009/11/01.
【非特許文献２】安井雄一郎、藤澤克樹、笹島啓史、後藤和茂、宮元裕一郎、「大規模最短路問題に対するダイクストラ法の高速化」日本オペレーションズ・リサーチ学会、秋季研究発表会アブストラクト集 2008、pp.314-315, 2009-09-10.
【発明の概要】
【発明が解決しようとする課題】
【００１１】
ユーザからの需要に応じてサービスとそのためのサービス設備を予約したり、提供したりするサービスの観点において、上記のように、動的な経路探索を用い、マルチコアCPUの機能を活かしたマルチスレッド経路探索方法は提案されていない。また、静的な経路探索法はそもそもそのようなサービスに適していない。
【００１２】
本発明は、上記の点に鑑みなされたもので、マルチコアCPUの機能を活かして、始点から終点までの全経路から最適な経路を迅速に計算することが可能な並列資源探索方法及び装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記の課題を解決するために、本発明（請求項１）は、マルチコアCPUを用いて始点から終点までの全経路を計算する並列資源探索装置であって、
ネットワーク構成、該ネットワークの各ノードの情報を格納したネットワーク情報記憶手段と、
ユーザ端末から少なくとも始点及び終点を含む要求条件を取得して要求記憶手段に格納する要求受信手段と、
前記始点から前記終点までの経路を計算するためのスレッドを生成するスレッド生成手段と、
前記要求条件の始点を最初の中継点候補（基点）とし、経路記憶手段に格納する手段と、
前記始点から前記終点に向かう前記基点に隣接する中継点候補までの枝（基点枝）の数だけ前記スレッドを生成し、該中継点候補までの経路を該経路記憶手段に追記し、新たな基点枝がある場合は、該中継点候補までのスレッドを停止し、停止した経路を利用停止として該経路記憶手段を更新する処理を前記終点まで繰り返す探索手段と、
を有する。
【００１４】
また、本発明（請求項２）は、経路上の隣接点を格納した隣接点記憶手段を更に有し、
前記探索手段は、
前記隣接点記憶手段を参照して、隣接点毎に逐次新しいスレッドを生成する手段を含む。
【００１５】
また、本発明（請求項３）は、経路上の隣接点を格納した隣接点記憶手段と、
予め空きスレッドを格納するスレッドプールと、を更に有し、
前記探索手段は、
前記スレッドプールの空きスレッドの数に応じて、前記隣接点記憶手段を参照して、隣接点毎に空きスレッドからひとつを割り当てる手段を含む。
【００１６】
また、本発明（請求項４）は、利用可能な資源情報を格納した利用可能資源情報記憶手段を更に有し、
前記探索手段は、
前記ネットワーク情報記憶手段及び前記利用可能資源情報記憶手段を参照して、生成された前記スレッドが所定の制約条件を満たすかを判定し、満たす場合のみ前記始点から生成したスレッドまでの点の経路を前記経路記憶手段に格納する手段を含む。
【００１７】
本発明（請求項５）は、マルチコアCPUを用いて始点から終点までの全経路を計算する並列資源探索方法であって、
要求受信手段が、ユーザ端末から少なくとも始点及び終点を含む要求条件を取得して要求記憶手段に格納する要求受信ステップと、
探索手段が、前記要求条件の始点を最初の中継点候補（基点）とし、経路記憶手段に格納し、
前記始点から前記終点に向かう前記基点に隣接する中継点候補までの枝（基点枝）の数だけ、前記始点から前記終点までの経路を計算するためのスレッドを生成し、該中継点候補までの経路を該経路記憶手段に追記し、新たな基点枝がある場合は、該中継点候補までのスレッドを停止し、停止した経路を利用停止として該経路記憶手段を更新する処理を前記終点まで繰り返す探索ステップと、を行う。
【００１８】
また、本発明（請求項６）は、前記探索ステップにおいて、
経路上の隣接点を格納した隣接点記憶手段を参照して、隣接点毎に逐次新しいスレッドを生成する。
【００１９】
また、本発明（請求項７）は、前記探索ステップにおいて、
予め空きスレッドが格納されているスレッドプールの空きスレッドの数に応じて、経路上の隣接点を格納した隣接点記憶手段を参照して、隣接点毎に空きスレッドからひとつを割り当てる。
【００２０】
また、本発明（請求項８）は、前記探索ステップにおいて、
前記ネットワーク情報記憶手段及び利用可能な資源情報を格納した利用可能資源情報記憶手段を参照して、生成された前記スレッドが所定の制約条件を満たすかを判定し、満たす場合のみ前記始点から生成したスレッドまでの点の経路を前記経路記憶手段に格納する。
【００２１】
本発明（請求項９）は、請求項１乃至４のいずれか１項に記載の並列資源探索装置を構成する各手段としてコンピュータを機能させるためのプログラムである。
【発明の効果】
【００２２】
上述のように、本発明では、マルチコアCPUを用いるネットワークにおいて、始点から終点の全経路探索に対し、マルチスレッド技術を適用することにより経路探索の高速化が可能である。
【図面の簡単な説明】
【００２３】
【図１】本発明の第１の実施の形態における並列資源探索装置の構成図である。
【図２】本発明の第１の実施の形態における経路探索部内部のスレッドの状況である。
【図３】本発明の第１の実施の形態におけるスレッドの生成による経路探索を示す図である。
【図４】本発明の第１の実施の形態における要求データベースの一例である。
【図５】本発明の第１の実施の形態におけるデータ管理ＤＢの構成図である。
【図６】本発明の第１の実施の形態における隣接行列の一例である。
【図７】本発明の第１の実施の形態における経路ＤＢの遷移例である。
【図８】本発明の第１の実施の形態における岐路探索処理のフローチャートである。
【図９】本発明の第１の実施の形態におけるスレッド割当の例である。
【図１０】本発明の第１の実施の形態における経路ＤＢの内容例と同ＤＢ上の処理の一例である。
【図１１】本発明の第１の実施の形態におけるスレッド割当のシーケンスチャート（その１）である。
【図１２】本発明の第１の実施の形態におけるスレッド割当のシーケンスチャート（その２）である。
【図１３】本発明の第２の実施の形態におけるスレッド起動及び生成を説明するための図である。
【図１４】本発明の第２の実施の形態におけるスレッド割当処理のフローチャートである。
【発明を実施するための形態】
【００２４】
以下図面と共に、本発明の実施の形態を説明する。
【００２５】
［第１の実施の形態］
本発明は、資源探索装置において、ネットワーク上のノード間の伝送メディアの最小物理単位に点を配置し、これらの隣接する点を接続する経路について、始点から終点までの経路を計算するスレッドを生成して起動させ、始点から終点に向かい新しい枝を発見したら、それまで立ち上げたスレッドを停止して、その地点から終点までの経路を計算するスレッドを枝の数だけ立ち上げることにより、マルチスコアCPUの機能を使い切るように経路を計算するものである。
【００２６】
図１は、本発明の第１の実施の形態における並列資源探索装置の構成を示す。
【００２７】
同図に示す並列資源探索装置は、ユーザ要求受信部１０、経路探索部２０、スレッド数管理部３０、利用可能管理部４０、リミテーションチェック部５０、要求ＤＢ６０、経路ＤＢ７０，データ管理ＤＢ８０から構成される。
【００２８】
ユーザ要求受信部１０は、始点や終点などの情報を含む要求条件を受信して要求ＤＢ６０に格納する。
【００２９】
経路探索部２０は、要求ＤＢ６０から要求を読み出して、始点と終点が一致する場合には、探索を完了させ、一致しない場合には、始点を基点枝として始点から基点枝までの経路を経路ＤＢ７０に格納する。経路探索部２０は、内部（メモリ）に図２に示すようなスレッドを管理する。図２に示すように、各スレッドは、経路チェック、コストチェックを行うためのチェック手段を有する。経路探索部２０は、図３（ａ）に示すように、始点から終点までの全経路をマルチコアＣＰＵの性能を使い切るように、新しい枝の発見地点から、順に終点までの経路を計算する新しいスレッドを生成する。例えば、始点からノード"２"にスレッド"１"が生成され、始点からノード"５"にスレッド"４"が新たに生成される。ノード"２"からノード"３"に対するスレッド"２"、ノード"４"に対するスレッド"３"、また、ノード"５"からノード"２"に対するスレッド"６"、ノード"５"からノード"６"に対するスレッド"５"がそれぞれ新たに生成される。そして、図３（ｂ）に示すように、始点から終点に向かってあるノードで新しいノードが見つかった場合はそれまでのスレッドは停止し、停止したことを示す情報（フラグ）で経路ＤＢ７０を更新し、その地点のノードから終点までの経路をスレッドの枝の数だけ起動させることで全経路を計算する。
【００３０】
スレッド数管理部３０は、経路探索部２０からスレッド数を取得してデータ管理ＤＢ８０に格納する。
【００３１】
利用可能管理部４０は、経路探索部２０で探索された経路の資源が利用可能であるかをデータ管理ＤＢ８０を参照し、利用可能時間帯、利用可能な容量等を判断する。具体的には、特開２００８−３０１２２５号公報に開示されている方法等を用いることが可能である。
【００３２】
リミテーションチェック部５０は、経路ＤＢ７０から経路リストを読み込み、所定の条件に基づいて、経路を整理する。具体的には、特開２００８−３０１２２５公報に開示されている方法等を用いることが可能である。
【００３３】
要求ＤＢ６０は、ユーザ要求受信部１０で受信した要求について、図４に示すように、受信時刻、通信路始点、通信路終点、開始時刻、終了時刻、通信容量、料金、優先度等のデータを格納する。
【００３４】
データ管理ＤＢ８０は、図５に示すように、ネットワーク構成リスト８１、利用可能資源リスト８２，接続行列８３を格納する。
【００３５】
ネットワーク構成リスト８１は、点の識別情報、点のＩＤ，ＩＰＤ（IPアドレス、Ifindex、TDMスロット番号）、インタフェースのメディアタイプ、インタフェースの利用可能なSwitching Capability、インタフェースの物理容量、利用可能ラベル、ノードＩＤ，ノード種別等からなる。
【００３６】
利用可能資源リスト８２は、点の識別情報、点のID、PID、メディア、利用可能なSwitching Capability、物理容量、利用可能ラベル、ノードID、ノード種別、時間の区切り情報（時刻＋利用可能容量＋時刻）を含む。
【００３７】
接続行列８３は、ネットワーク上のノード間の伝送メディアの最小物理単位を点（１，２，３，…）として、ノード間接続・ノード内接続の可否を"０"（接続不可）、"１"（接続可）で表した表であり、各最小物理単位の１つのマスごとに図６に示す情報が格納される。接続行列の生成方法については、特開2008-301225号公報に開示されている技術を用いるものとする。
【００３８】
経路ＤＢ７０は、図７に示すように、探索の進行と共に利用済みかつ終点に到達していない経路は利用停止とする。図７において、例えば、「始点→枝ｉ→基点枝ｋ」を評価枝と呼び、これらの集合を評価枝リストと呼ぶ。
【００３９】
次に、経路探索の処理について説明する。
【００４０】
図８は、本発明の第１の実施の形態における経路探索処理のフローチャートである。
【００４１】
ステップ１０１） 要求受信部１０が要求を受信すると、当該要求の要求条件を要求ＤＢ６０に格納する。経路探索部２０は、要求ＤＢ６０から要求条件を読み出し、通信路始点と通信路終点が一致する場合には、探索を終了する。一致しない場合はステップ１０２に移行する。
【００４２】
ステップ１０２） 経路探索部２０は、通信路始点≠通信路終点である場合は、始点を基点として通信路の始点から基点枝までの経路を経路ＤＢ７０に追記する。
【００４３】
ステップ１０３） 経路探索部２０は、経路ＤＢ７０から始点から基点枝までの経路の中で未選択の経路を一つ選択する。
【００４４】
ステップ１０４） 経路探索部２０は、始点から基点枝までの経路毎に次の評価対象となるノードからの評価枝を探索するためにスレッドを割り当てる。当該処理は評価枝がなくなるまで繰り返す。スレッド数管理部３０は、内部のスレッド数メモリ（図示せず）のスレッド数を加算する。スレッド割当のイメージを図９に示す。
【００４５】
ステップ１０５） 経路探索部２０は、データ管理ＤＢ８０の隣接行列８３を参照して、基点枝から隣接している評価枝を探索する。隣接する評価枝が無い場合はステップ１１１に移行し、評価枝がある場合は、始点から基点枝までの経路別に評価枝を経路ＤＢ７０の評価枝リストに格納する。
【００４６】
ステップ１０６） ステップ１０５において評価枝がある場合は、経路探索部２０は、経路ＤＢ７０の評価枝リストから未選択の評価枝を一つ選択する。選択する評価枝が無い場合は、ステップ１１１に移行する。このとき、選択された評価枝については、経路ＤＢ７０の評価枝リストに選択済みを表すフラグを設定するものとする。
【００４７】
ステップ１０７） ステップ１０６において、評価枝が選択された場合は、経路探索部２０は、基点枝を基準として評価枝毎に評価枝の制約条件の合否を確認・評価するためのスレッドを割り当てる。スレッド数管理部３０は、内部のスレッド数メモリ（図示せず）のスレッド数を加算する。
【００４８】
ステップ１０８） 経路探索部２０は、データ管理ＤＢ８０のネットワーク構成リスト８１、利用可能資源リスト８２を参照して所定の制約条件を満たすかを判定し、条件を満足しない場合はステップ１１０に移行し、満足する場合はステップ１０９に移行する。
【００４９】
ステップ１０９） 経路探索部２０は、始点からステップ１０６で選択された評価枝までの経路を経路ＤＢ７０に追加する。
【００５０】
ステップ１１０） 経路探索部２０は、ステップ１０７で割り当てられたスレッドを開放し、スレッド数管理部３０は、スレッド数メモリのスレッド数をクリアする。ステップ１０６に移行する。
【００５１】
ステップ１１１） ステップ１０６において、未選択の評価枝が無い場合は、始点から当該基点枝までの経路について、探索が重複しないように、利用停止として経路ＤＢ７０の探索済みのため利用停止フラグに「１」を設定する。
【００５２】
ステップ１１２） 経路探索部２０は、それまで設定されていたスレッドを開放し、スレッド数管理部３０は、スレッド数メモリのスレッド数をクリアする。
【００５３】
ステップ１１３） 経路探索部２０は、経路ＤＢ７０を参照して、始点から基点枝までの経路の中で基点枝が終点と異なっている経路（基点枝≠終点）があるかを判定し、経路がある場合はステップ１０３に移行する。一方、経路が無い場合はステップ１１４に移行する。
【００５４】
ステップ１１４） 経路探索部２０は、経路ＤＢ７０を参照して、基点枝が終点である経路があるかを判定し、ある場合には、「経路あり」を出力して探索を終了し、無い場合は「経路なし」（探索失敗）として探索を終了する。
【００５５】
なお、上記のフローチャートでは、ステップ１０４において、始点から基点枝までの経路毎に次の評価枝を探索するためのスレッドを割り当て、さらに、ステップ１０７において、基点枝を基点として評価枝毎に評価枝の制約条件の合否を確認・評価するためにスレッドを割り当てているが、ステップ１０４または、制約条件の判定を含めたスレッドの割当を行うステップ１０７のいずれか１つの処理を行うようにしてもよい。
【００５６】
図１０は、本発明の一実施の形態における経路ＤＢの内容例と同ＤＢ上での処理の一例である。
【００５７】
第１ステップ） 最初に始点（ソース）を経路ＤＢ７０に設定し、経路探索途中で図９（ａ）に示す経路探索データを経路ＤＢ７０に格納する。
【００５８】
第２ステップ） データ管理ＤＢ８０の接続行列８３を参照し、「通過点１」を中心に隣接している点を全て探索し、図１０（ｂ）の探索データを経路ＤＢ７０に格納する。このとき、探索済みとなった図１０（ａ）の２つの「通過点１」については、図１０（ｂ）に示すように利用停止とし、利用停止フラグを「１」とする。
【００５９】
第３ステップ） 次に、データ管理ＤＢ８０の隣接行列８３を参照し、図１０（ｃ）に示す経路探索データを経路ＤＢ７０に格納する。このとき、図１０（ｂ）において利用停止となった「通過点１」に加え、２つの「通過点２」、１つの「通過点３」についても、図１０（ｃ）に示すように探索済みのため利用停止とし、利用停止フラグを「１」とする。
【００６０】
第４ステップ） 次に、始点から終点だけが残るまで経路探索を繰り返し、図１０（ｄ）に示す経路探索データを経路リストとし、経路ＤＢ７０に格納する。
【００６１】
次に、図８のステップ１０４及びステップ１０７におけるスレッドを割り当てる際の動作を説明する。
【００６２】
図１１、図１２は、本発明の一実施の形態におけるスレッド割当のシーケンスチャートである。
【００６３】
ステップ２０１） 要求受信部１０が探索開始処理の要求を受け取ると、当該要求を要求ＤＢ６０に格納したことを経路探索部２０に通知する。
【００６４】
ステップ２０２） 経路探索部２０は、受信した要求について、始点と終点が同一かを判定し、同一である場合は探索処理を終了する。
【００６５】
ステップ２０３） 経路探索部２０は、始点を中継点として経路ＤＢ７０に設定すると共に、当該中継点が選択済みであることを示すフラグをたてる。
【００６６】
ステップ２０４） 経路探索部２０は、データ管理ＤＢ８０の接続行列８３を参照し、隣接点を探索する。
【００６７】
ステップ２０５） 接続行列８３を参照することにより隣接点がある場合はステップ２０６に移行し、隣接点が無い場合はステップ２０９に移行する。
【００６８】
ステップ２０６） 経路探索部２０は、隣接点を中継点候補として経路ＤＢ７０を更新する。
【００６９】
ステップ２０７） 経路探索部２０は、スレッド数管理部３０に問い合わせ、その時点におけるスレッド数を取得する。
【００７０】
ステップ２０８） 経路探索部２０は、その時点で起動しているスレッド数が所定の数Ｎ未満であれば、スレッドを起動させ、スレッド数管理部３０にスレッド数の更新を指示する。一方、起動しているスレッド数が所定数以上である場合は、経路チェック及びコストチェックを行う。
【００７１】
上記のステップ２０４以降の処理を隣接点がなくなるまで繰り返す。
【００７２】
ステップ２０９） 経路探索部２０は、選択済みの中継点を選択済みとして選択済みのフラグを立てる。
【００７３】
ステップ２１０） 経路探索部２０は、経路ＤＢ７０にスレッドが起動できなかった経路があるかを判定し、ある場合には、ステップ２１１に移行し、無い場合は、次の起動スレッドを待機する。
【００７４】
ステップ２１１） 経路探索部２０は、経路ＤＢ７０から未選択の中継点を探索する。
【００７５】
ステップ２１２） 未選択の中継点候補が見つかった場合は、ステップ２１３に移行し、ない場合には、起動スレッドの待ち合わせを行う。
【００７６】
ステップ２１３） 未選択の中継点が見つかった場合は、要求ＤＢ６０に終点を問い合わせる。
【００７７】
ステップ２１４） 経路探索部２０は、未選択、かつ、利用可能で終点以外の未選択の中継点があるかを判定し、無い場合は起動スレッドを待ち合わせ、ある場合はステップ２１５に移行する。
【００７８】
ステップ２１５） ステップ２１４において、未選択の中継点がある場合は、未選択の中継点を選択し、選択した中継点を選択済みとして経路ＤＢ７０を更新する。
【００７９】
上記のステップ２０４からステップ２１５までの処理を経路状態が確定するまで繰り返す。
【００８０】
ステップ２１６） 次に、利用可能管理部４０は、経路探索部２０内部の各経路探索スレッドについて、経路ＤＢ７０及びデータ管理ＤＢ８０の利用可能資源リスト８２を参照し、チェック用の情報を取得し、設定された経路状態が利用可能であるかを判定する。判定の方法としては、例えば、特開2008-301225号公報に開示されている手法を用いるものとする。
【００８１】
ステップ２１７） さらに、各経路探索スレッドについて、経路ＤＢ７０、データ管理ＤＢ８０のネットワーク構成リスト８１及び利用可能資源リスト８２を参照し、チェック用の情報を取得し、コストチェックを行う。判定の方法としては、例えば、特開2008-301225号公報に開示されている手法を用いるものとする。
【００８２】
ステップ２１８） この時点で生成されている各スレッドのチェック手段において、データ管理ＤＢ８０を参照して、所定の条件に基づいて、経路チェックとコストチェックを行い、双方チェックが充足している場合には、経路ＤＢ７０にチェック結果を反映し、隣接点を中継点情報として更新する。充足していない場合には、チェック結果と、隣接点の利用を停止し、当該中継点候補に利用停止のフラグを付与して経路ＤＢ７０を更新し、経路探索処理を終了する。ここで、経路チェックとは、例えば、時刻Ｘから時刻Ｙの間において、帯域Ｚが空いているか否かを確認する、といったチェックを指す。コストチェックは、コストチェックアルゴリズムを用いて、データ管理ＤＢ８０を参照し、経路チェックとして条件を満足するか否かを確認し、満足する隣接点についてのコストチェックを行う。上記のチェックにおいて、コストチェックより経路チェックを優先させることで、演算処理が必要なコストチェックでは、チェック対象となる数が少なくて済み、演算時間が短縮される。
【００８３】
ステップ２１９） 各経路探索スレッドにおいて、要求ＤＢ６０を参照し、終点情報を取得して、中継点と終点が一致する場合には、当該探索を終了し、一致しない場合は、ステップ２０１に移行する。
【００８４】
なお、上記の処理に加え、リミテーションチェック部５０による処理を行い、最終的に予約を確定回路として出力するようにしてもよい。なお、リミテーションチェック部５０の処理は、特開2008-301225号公報に開示されている技術を用いるものとする。
【００８５】
［第２の実施の形態］
前述の第1の実施の形態では、隣接点毎に新しいスレッドを生成した（図８：ステップ１０５）。この方法は、予め所要スレッド数を予測できない計算には有効であるが、スレッド生成処理に時間がかかる。
【００８６】
本実施の形態では、予めスレッドプールを用意しておき、隣接点ごとに新しいスレッドを割り当てる。なお、本実施の形態における装置構成は、第１の実施の形態と同様である。
【００８７】
図１２は、本発明の第２の実施の形態におけるスレッドの起動及び生成を説明するための図である。
【００８８】
同図（ａ）に示すように、初期状態では、経路探索部２０がスレッドプール内のＮ個のスレッドを管理し、セマフォが各スレッドの動きを停止する。なお、セマフォはＮ個のスレッドがあることを認識しているものとする。
【００８９】
次に、同図（ｂ）に示すように、経路探索部２０がリクエストに応じてスレッドプール内の1個のスレッドを払い出す。このとき、セマフォは開放されているものとし、セマフォは残りＮ−1個のスレッドがあることを認識している。
【００９０】
この時点でＭ個のスレッドをスレッドプールから払い出したものとすると、総計Ｍ＋１個のスレッドを払い出したことになる。
【００９１】
そして、同図（ｃ）に示すように、利用終了した1個のスレッドがスレッドプールに返却されると、セマフォは残りＮ−Ｍ個のスレッドがあることを把握する。
【００９２】
上記の処理のためにセマフォと経路探索部２０は以下のような処理を行う。
【００９３】
図１３は、本発明の第２の実施の形態におけるスレッド割当処理のフローチャートである。
【００９４】
まず、セマフォは、リクエストを取得すると、スレッドプールの空きスレッド数を確認し（ステップ３０１）、リクエストされた個数分の残りが無い場合は、スレッドの割当を保留し（ステップ３０２）、残りがある場合には、経路探索部２０はリクエストで指定された分のスレッドを割り当てる（ステップ３０３）。
【００９５】
なお、図１に示す並列資源探索装置の構成要素の第１の実施の形態及び第２の実施の形態に示した動作をプログラムとして構築し、並列資源探索装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００９６】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００９７】
１０ ユーザ要求受信部
２０ 経路探索部
３０ スレッド数管理部
４０ 利用可能管理部
５０ リミテーションチェック部
６０ 要求ＤＢ（データベース）
７０ 経路ＤＢ
８０ データ管理部
８１ ネットワーク構成リスト
８２ 利用可能資源リスト
８３ 接続行列
【特許請求の範囲】
【請求項１】
CPUの利用を時間的に分割した単位であるスレッドを複数用いることによって複数の計算処理を同時に並列実行できるマルチコアCPUを用い、始点から終点までの全経路を計算する並列資源探索装置であって、
ネットワーク構成、該ネットワークの各ノードの情報を格納したネットワーク情報記憶手段と、
ユーザ端末から少なくとも始点及び終点を含む要求条件を取得して要求記憶手段に格納する要求受信手段と、
前記始点から前記終点までの経路を計算するためのスレッドを生成するスレッド生成手段と、
前記要求条件の始点を最初の中継点候補（基点）とし、経路記憶手段に格納する手段と、
前記始点から前記終点に向かう前記基点に隣接する中継点候補までの枝（基点枝）の数だけ前記スレッドを生成し、該中継点候補までの経路を該経路記憶手段に追記し、新たな基点枝がある場合は、該中継点候補までのスレッドを停止し、停止した経路を利用停止として該経路記憶手段を更新する処理を前記終点まで繰り返す探索手段と、
を有することを特徴とする並列資源探索装置。
【請求項２】
経路上の隣接点を格納した隣接点記憶手段を更に有し、
前記探索手段は、
前記隣接点記憶手段を参照して、隣接点毎に逐次新しいスレッドを生成する手段を含む
請求項１記載の並列資源探索装置。
【請求項３】
経路上の隣接点を格納した隣接点記憶手段と、
予め空きスレッドを格納するスレッドプールと、を更に有し、
前記探索手段は、
前記スレッドプールの空きスレッドの数に応じて、前記隣接点記憶手段を参照して、隣接点毎に空きスレッドからひとつを割り当てる手段を含む
請求項１記載の並列資源探索装置。
【請求項４】
利用可能な資源情報を格納した利用可能資源情報記憶手段を更に有し、
前記探索手段は、
前記ネットワーク情報記憶手段及び前記利用可能資源情報記憶手段を参照して、生成された前記スレッドが所定の制約条件を満たすかを判定し、満たす場合のみ前記始点から生成したスレッドまでの点の経路を前記経路記憶手段に格納する手段を含む
請求項１記載の並列資源探索装置。
【請求項５】
マルチコアCPUを用いて始点から終点までの全経路を計算する並列資源探索方法であって、
要求受信手段が、ユーザ端末から少なくとも始点及び終点を含む要求条件を取得して要求記憶手段に格納する要求受信ステップと、
探索手段が、前記要求条件の始点を最初の中継点候補（基点）とし、経路記憶手段に格納し、
前記始点から前記終点に向かう前記基点に隣接する中継点候補までの枝（基点枝）の数だけ、前記始点から前記終点までの経路を計算するためのスレッドを生成し、該中継点候補までの経路を該経路記憶手段に追記し、新たな基点枝がある場合は、該中継点候補までのスレッドを停止し、停止した経路を利用停止として該経路記憶手段を更新する処理を前記終点まで繰り返す探索ステップと、
を行うことを特徴とする並列資源探索方法。
【請求項６】
前記探索ステップにおいて、
経路上の隣接点を格納した隣接点記憶手段を参照して、隣接点毎に逐次新しいスレッドを生成する
請求項５記載の並列資源探索方法。
【請求項７】
前記探索ステップにおいて、
予め空きスレッドが格納されているスレッドプールの空きスレッドの数に応じて、経路上の隣接点を格納した隣接点記憶手段を参照して、隣接点毎に空きスレッドからひとつを割り当てる請求項５記載の並列資源探索方法。
【請求項８】
前記探索ステップにおいて、
前記ネットワーク情報記憶手段及び利用可能な資源情報を格納した利用可能資源情報記憶手段を参照して、生成された前記スレッドが所定の制約条件を満たすかを判定し、満たす場合のみ前記始点から生成したスレッドまでの点の経路を前記経路記憶手段に格納する請求項５記載の並列資源探索方法。
【請求項９】
請求項１乃至４のいずれか１項に記載の並列資源探索装置を構成する各手段としてコンピュータを機能させるためのプログラム。
【請求項１】
CPUの利用を時間的に分割した単位であるスレッドを複数用いることによって複数の計算処理を同時に並列実行できるマルチコアCPUを用い、始点から終点までの全経路を計算する並列資源探索装置であって、
ネットワーク構成、該ネットワークの各ノードの情報を格納したネットワーク情報記憶手段と、
ユーザ端末から少なくとも始点及び終点を含む要求条件を取得して要求記憶手段に格納する要求受信手段と、
前記始点から前記終点までの経路を計算するためのスレッドを生成するスレッド生成手段と、
前記要求条件の始点を最初の中継点候補（基点）とし、経路記憶手段に格納する手段と、
前記始点から前記終点に向かう前記基点に隣接する中継点候補までの枝（基点枝）の数だけ前記スレッドを生成し、該中継点候補までの経路を該経路記憶手段に追記し、新たな基点枝がある場合は、該中継点候補までのスレッドを停止し、停止した経路を利用停止として該経路記憶手段を更新する処理を前記終点まで繰り返す探索手段と、
を有することを特徴とする並列資源探索装置。
【請求項２】
経路上の隣接点を格納した隣接点記憶手段を更に有し、
前記探索手段は、
前記隣接点記憶手段を参照して、隣接点毎に逐次新しいスレッドを生成する手段を含む
請求項１記載の並列資源探索装置。
【請求項３】
経路上の隣接点を格納した隣接点記憶手段と、
予め空きスレッドを格納するスレッドプールと、を更に有し、
前記探索手段は、
前記スレッドプールの空きスレッドの数に応じて、前記隣接点記憶手段を参照して、隣接点毎に空きスレッドからひとつを割り当てる手段を含む
請求項１記載の並列資源探索装置。
【請求項４】
利用可能な資源情報を格納した利用可能資源情報記憶手段を更に有し、
前記探索手段は、
前記ネットワーク情報記憶手段及び前記利用可能資源情報記憶手段を参照して、生成された前記スレッドが所定の制約条件を満たすかを判定し、満たす場合のみ前記始点から生成したスレッドまでの点の経路を前記経路記憶手段に格納する手段を含む
請求項１記載の並列資源探索装置。
【請求項５】
マルチコアCPUを用いて始点から終点までの全経路を計算する並列資源探索方法であって、
要求受信手段が、ユーザ端末から少なくとも始点及び終点を含む要求条件を取得して要求記憶手段に格納する要求受信ステップと、
探索手段が、前記要求条件の始点を最初の中継点候補（基点）とし、経路記憶手段に格納し、
前記始点から前記終点に向かう前記基点に隣接する中継点候補までの枝（基点枝）の数だけ、前記始点から前記終点までの経路を計算するためのスレッドを生成し、該中継点候補までの経路を該経路記憶手段に追記し、新たな基点枝がある場合は、該中継点候補までのスレッドを停止し、停止した経路を利用停止として該経路記憶手段を更新する処理を前記終点まで繰り返す探索ステップと、
を行うことを特徴とする並列資源探索方法。
【請求項６】
前記探索ステップにおいて、
経路上の隣接点を格納した隣接点記憶手段を参照して、隣接点毎に逐次新しいスレッドを生成する
請求項５記載の並列資源探索方法。
【請求項７】
前記探索ステップにおいて、
予め空きスレッドが格納されているスレッドプールの空きスレッドの数に応じて、経路上の隣接点を格納した隣接点記憶手段を参照して、隣接点毎に空きスレッドからひとつを割り当てる請求項５記載の並列資源探索方法。
【請求項８】
前記探索ステップにおいて、
前記ネットワーク情報記憶手段及び利用可能な資源情報を格納した利用可能資源情報記憶手段を参照して、生成された前記スレッドが所定の制約条件を満たすかを判定し、満たす場合のみ前記始点から生成したスレッドまでの点の経路を前記経路記憶手段に格納する請求項５記載の並列資源探索方法。
【請求項９】
請求項１乃至４のいずれか１項に記載の並列資源探索装置を構成する各手段としてコンピュータを機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２０１２−１４２９０５（Ｐ２０１２−１４２９０５Ａ）
【公開日】平成２４年７月２６日（２０１２．７．２６）
【国際特許分類】
【出願番号】特願２０１１−１３３９（Ｐ２０１１−１３３９）
【出願日】平成２３年１月６日（２０１１．１．６）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 平成２２年８月２５日 独立行政法人産業技術総合研究所主催の「科学技術振興調整費 先端融合領域イノベーション創出拠点の形成 第３回「光ネットワーク超低エネルギー化技術拠点」シンポジウム」において文書をもって発表
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 平成２２年１１月４日 社団法人電子情報通信学会発行の「電子情報通信学会技術研究報告 信学技報 Ｖｏｌ．１１０ Ｎｏ．２６９」に発表
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年７月２６日（２０１２．７．２６）
【国際特許分類】
【出願日】平成２３年１月６日（２０１１．１．６）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 平成２２年８月２５日 独立行政法人産業技術総合研究所主催の「科学技術振興調整費 先端融合領域イノベーション創出拠点の形成 第３回「光ネットワーク超低エネルギー化技術拠点」シンポジウム」において文書をもって発表
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 平成２２年１１月４日 社団法人電子情報通信学会発行の「電子情報通信学会技術研究報告 信学技報 Ｖｏｌ．１１０ Ｎｏ．２６９」に発表
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]