(57)【特許請求の範囲】
【請求項１】
ネットワークを構成するノード間のリンクの容量を示す情報と、
時系列に発生するトラヒック需要ごとに、トラヒック量、始点ノード、及び終点ノードを示す情報と、
を参照して、
前記各トラヒック需要を前記時系列の順番で、当該トラヒック需要のトラヒック量以上の容量を有するリンクを使用して、当該トラヒック需要の始点ノードから終点ノードまでの最短経路を配置すると共に、当該最短経路を構成する各リンクの容量を当該トラヒック量で消費する過程において、或るトラヒック需要に関して最短経路を配置することができない場合には、既に最短経路が配置されたトラヒック需要のうちの一部のトラヒック需要について最短経路の再配置を行った後で、前記或るトラヒック需要に関して最短経路を配置する手順をコンピュータが実行し、
前記コンピュータが、
前記時系列の順番において前記或るトラヒック需要の直前の所定数のトラヒック需要、前記時系列の順番において最初から所定数のトラヒック需要、又は任意の所定数のトラヒック需要を、前記一部のトラヒック需要として選択する、
ことを特徴とする経路配置方法。
【請求項２】
ネットワークを構成するノード間のリンクの容量を示す情報と、
時系列に発生するトラヒック需要ごとに、トラヒック量、始点ノード、及び終点ノードを示す情報と、
を参照して、
前記各トラヒック需要を前記時系列の順番で、当該トラヒック需要のトラヒック量以上の容量を有するリンクを使用して、当該トラヒック需要の始点ノードから終点ノードまでの最短経路を配置すると共に、当該最短経路を構成する各リンクの容量を当該トラヒック量で消費する過程において、或るトラヒック需要に関して最短経路を配置することができない場合には、既に最短経路が配置されたトラヒック需要のうちの一部のトラヒック需要について最短経路の再配置を行った後で、前記或るトラヒック需要に関して最短経路を配置する手順をコンピュータが実行し、
前記コンピュータが、
トラヒック量が大きい順に所定数のトラヒック需要、又はトラヒック量×配置された最短経路を構成するリンク数の大きい順に所定数のトラヒック需要を、前記一部のトラヒック需要として選択する、
ことを特徴とする経路配置方法。
【請求項３】
ネットワークを構成するノード間のリンクの容量を示す情報と、
時系列に発生するトラヒック需要ごとに、トラヒック量、始点ノード、及び終点ノードを示す情報と、
を参照して、
前記各トラヒック需要を前記時系列の順番で、当該トラヒック需要のトラヒック量以上の容量を有するリンクを使用して、当該トラヒック需要の始点ノードから終点ノードまでの最短経路を配置すると共に、当該最短経路を構成する各リンクの容量を当該トラヒック量で消費する過程において、或るトラヒック需要に関して最短経路を配置することができない場合には、既に最短経路が配置されたトラヒック需要のうちの一部のトラヒック需要について最短経路の再配置を行った後で、前記或るトラヒック需要に関して最短経路を配置する手順をコンピュータが実行し、
前記コンピュータが、
既に配置された最短経路ごとに当該最短経路上の各ノードの次数の合計を算出し、前記合計の大きい順に所定数のトラヒック需要を、前記一部のトラヒック需要として選択する、
ことを特徴とする経路配置方法。
【請求項４】
ネットワークを構成するノード間のリンクの容量を示す情報と、
時系列に発生するトラヒック需要ごとに、トラヒック量、始点ノード、及び終点ノードを示す情報と、
を参照して、
前記各トラヒック需要を前記時系列の順番で、当該トラヒック需要のトラヒック量以上の容量を有するリンクを使用して、当該トラヒック需要の始点ノードから終点ノードまでの最短経路を配置すると共に、当該最短経路を構成する各リンクの容量を当該トラヒック量で消費する過程において、或るトラヒック需要に関して最短経路を配置することができない場合には、既に最短経路が配置されたトラヒック需要のうちの一部のトラヒック需要について最短経路の再配置を行った後で、前記或るトラヒック需要に関して最短経路を配置する手順をコンピュータが実行し、
前記コンピュータが、
既に配置された最短経路ごとに当該最短経路上の各ノードに重なる最短経路の数の合計を算出し、前記合計が大きい順に所定数のトラヒック需要を、前記一部のトラヒック需要として選択する、又は既に配置された最短経路ごとに当該最短経路上の各リンクに重なる最短経路の数の合計を算出し、前記合計の大きい順に所定数のトラヒック需要を、前記一部のトラヒック需要として選択する、
ことを特徴とする経路配置方法。
【請求項５】
ネットワークを構成するノード間のリンクの容量を示す情報と、
時系列に発生するトラヒック需要ごとに、トラヒック量、始点ノード、及び終点ノードを示す情報と、
を参照して、
前記各トラヒック需要を前記時系列の順番で、当該トラヒック需要のトラヒック量以上の容量を有するリンクを使用して、当該トラヒック需要の始点ノードから終点ノードまでの最短経路を配置すると共に、当該最短経路を構成する各リンクの容量を当該トラヒック量で消費する過程において、或るトラヒック需要に関して最短経路を配置することができない場合には、既に最短経路が配置されたトラヒック需要のうちの一部のトラヒック需要について最短経路の再配置を行った後で、前記或るトラヒック需要に関して最短経路を配置する手順をコンピュータが実行し、
前記コンピュータが、
前記最短経路が配置されたトラヒック需要ごとに、当該トラヒック需要の始点ノードと、前記或るトラヒック需要の始点ノードとの間のリンクの数と、当該トラヒック需要の終点ノードと、前記或るトラヒック需要の終点ノードとの間のリンクの数との合計を算出し、前記合計の小さい順に所定数のトラヒック需要を、前記一部のトラヒック需要として選択する、
ことを特徴とする経路配置方法。
【請求項６】
ネットワークを構成するノード間のリンクの容量を示す情報と、時系列に発生するトラヒック需要ごとに、トラヒック量、始点ノード、及び終点ノードを示す情報と、を参照して、前記各トラヒック需要を前記時系列の順番で、当該トラヒック需要のトラヒック量以上の容量を有するリンクを使用して、当該トラヒック需要の始点ノードから終点ノードまでの最短経路を配置すると共に、当該最短経路を構成する各リンクの容量を当該トラヒック量で消費する過程において、或るトラヒック需要に関して最短経路を配置することができない場合には、既に最短経路が配置されたトラヒック需要のうちの一部のトラヒック需要について最短経路の再配置を行った後で、前記或るトラヒック需要に関して最短経路を配置する経路配置部を有し、
前記経路配置部は、
前記時系列の順番において前記或るトラヒック需要の直前の所定数のトラヒック需要、前記時系列の順番において最初から所定数のトラヒック需要、若しくは任意の所定数のトラヒック需要を、前記一部のトラヒック需要として選択する、
又は、トラヒック量が大きい順に所定数のトラヒック需要、若しくはトラヒック量×配置された最短経路を構成するリンク数の大きい順に所定数のトラヒック需要を、前記一部のトラヒック需要として選択する、
又は、既に配置された最短経路ごとに当該最短経路上の各ノードの次数の合計を算出し、前記合計の大きい順に所定数のトラヒック需要を、前記一部のトラヒック需要として選択する、
又は、既に配置された最短経路ごとに当該最短経路上の各ノードに重なる最短経路の数の合計を算出し、前記合計が大きい順に所定数のトラヒック需要を、前記一部のトラヒック需要として選択する、又は既に配置された最短経路ごとに当該最短経路上の各リンクに重なる最短経路の数の合計を算出し、前記合計の大きい順に所定数のトラヒック需要を、前記一部のトラヒック需要として選択する、
又は、前記最短経路が配置されたトラヒック需要ごとに、当該トラヒック需要の始点ノードと、前記或るトラヒック需要の始点ノードとの間のリンクの数と、当該トラヒック需要の終点ノードと、前記或るトラヒック需要の終点ノードとの間のリンクの数との合計を算出し、前記合計の小さい順に所定数のトラヒック需要を、前記一部のトラヒック需要として選択する、
ことを特徴とする経路配置装置。
【請求項７】
ネットワークを構成するノード間のリンクの容量を示す情報と、
時系列に発生するトラヒック需要ごとに、トラヒック量、始点ノード、及び終点ノードを示す情報と、
を参照して、
前記各トラヒック需要を前記時系列の順番で、当該トラヒック需要のトラヒック量以上の容量を有するリンクを使用して、当該トラヒック需要の始点ノードから終点ノードまでの最短経路を配置すると共に、当該最短経路を構成する各リンクの容量を当該トラヒック量で消費する過程において、或るトラヒック需要に関して最短経路を配置することができない場合には、既に最短経路が配置されたトラヒック需要のうちの一部のトラヒック需要について最短経路の再配置を行った後で、前記或るトラヒック需要に関して最短経路を配置する手順をコンピュータが実行し、
前記コンピュータが、
前記時系列の順番において前記或るトラヒック需要の直前の所定数のトラヒック需要、前記時系列の順番において最初から所定数のトラヒック需要、若しくは任意の所定数のトラヒック需要を、前記一部のトラヒック需要として選択する、
又は、トラヒック量が大きい順に所定数のトラヒック需要、若しくはトラヒック量×配置された最短経路を構成するリンク数の大きい順に所定数のトラヒック需要を、前記一部のトラヒック需要として選択する、
又は、既に配置された最短経路ごとに当該最短経路上の各ノードの次数の合計を算出し、前記合計の大きい順に所定数のトラヒック需要を、前記一部のトラヒック需要として選択する、
又は、既に配置された最短経路ごとに当該最短経路上の各ノードに重なる最短経路の数の合計を算出し、前記合計が大きい順に所定数のトラヒック需要を、前記一部のトラヒック需要として選択する、又は既に配置された最短経路ごとに当該最短経路上の各リンクに重なる最短経路の数の合計を算出し、前記合計の大きい順に所定数のトラヒック需要を、前記一部のトラヒック需要として選択する、
又は、前記最短経路が配置されたトラヒック需要ごとに、当該トラヒック需要の始点ノードと、前記或るトラヒック需要の始点ノードとの間のリンクの数と、当該トラヒック需要の終点ノードと、前記或るトラヒック需要の終点ノードとの間のリンクの数との合計を算出し、前記合計の小さい順に所定数のトラヒック需要を、前記一部のトラヒック需要として選択する、
ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路配置方法、経路配置装置、及びプログラムに関する。
【背景技術】
【０００２】
ネットワークを構成する各リンクとのリンク容量と、ネットワーク上の特定対地間の時系列のトラヒック需要が与えられている状態において、この時系列のトラヒック需要を疎通するためのパスを、各時点での空き帯域に最短経路で埋め込むことを考える。リンク容量は有限なため、ある時点でネットワークにパスは埋め込めなくなる。このとき、これまでに埋め込んだ全てのパスの再配置によって、新たにパスを埋め込める可能性が出てくる。新たなパスを埋め込めた場合には、そのまま次の時点のトラヒック需要を最短経路で埋め込んでいく。新たなパスを埋め込めなかった場合には、そのトラヒック需要を廃棄して、次のトラヒック需要を最短経路で埋め込んでいく。これが、パス埋め込み問題におけるパス再配置問題である。
【０００３】
このように、リンク容量制約のあるネットワークにパスを１本ずつ埋め込んでいき、埋め込めなくなったときに、これまで埋め込んだパス全体の再配置を行う技術は、０−１整数計画法として定式化でき、分枝限定法によって厳密解を求める手法又はＷＣＳＰ法によってヒューリスティックに解く手法が知られていた。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】K. Nonobe and T. Ibaraki, A tabu search approach for the constraint satisfaction problem as a general problem solver, European Journal of Operational Research 106, 599-623, 1998.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、パス全体の再配置を行うと、動かす必要のないパスまでも再配置の対象としてしまうため、計算に非常に時間がかかるという問題があった。
【０００６】
本発明は、上記の点に鑑みてなされたものであって、トラヒック需要の経路を時系列に配置する場合の経路の再配置のための計算時間を短縮することを目的とする。
【課題を解決するための手段】
【０００７】
そこで上記課題を解決するため、経路配置方法は、ネットワークを構成するノード間のリンクの容量を示す情報と、時系列に発生するトラヒック需要ごとに、トラヒック量、始点ノード、及び終点ノードを示す情報と、を参照して、前記各トラヒック需要を前記時系列の順番で、当該トラヒック需要のトラヒック量以上の容量を有するリンクを使用して、当該トラヒック需要の始点ノードから終点ノードまでの最短経路を配置すると共に、当該最短経路を構成する各リンクの容量を当該トラヒック量で消費する過程において、或るトラヒック需要に関して最短経路を配置することができない場合には、既に最短経路が配置されたトラヒック需要のうちの一部のトラヒック需要について最短経路の再配置を行った後で、前記或るトラヒック需要に関して最短経路を配置する手順をコンピュータが実行し、前記コンピュータが、前記時系列の順番において前記或るトラヒック需要の直前の所定数のトラヒック需要、前記時系列の順番において最初から所定数のトラヒック需要、又は任意の所定数のトラヒック需要を、前記一部のトラヒック需要として選択する。
【発明の効果】
【０００８】
トラヒック需要の経路を時系列に配置する場合の経路の再配置のための計算時間を短縮することができる。
【図面の簡単な説明】
【０００９】
【図１】本発明の実施の形態におけるシステム構成例を示す図である。
【図２】本発明の実施の形態におけるパス埋め込み算出装置のハードウェア構成例を示す図である。
【図３】パス埋め込み算出装置が実行する処理手順の一例を説明するためのフローチャートである。
【図４】試行に利用されたネットワークの構成を示す図である。
【図５】試行に利用されたネットワークの各リンクの容量を示す図である。
【発明を実施するための形態】
【００１０】
以下、図面に基づいて本発明の実施の形態を説明する。図１は、本発明の実施の形態におけるシステム構成例を示す図である。図１において、パス埋め込み算出装置１０は、オペレーションシステム２０及び操作端末３０等に、ＬＡＮ（Local Area Network）又はインターネット等のネットワークを介して通信可能に接続される。
【００１１】
オペレーションシステム２０は、ネットワーク４０（通信網）上のノード及びノード間のリンク等を管理する１以上のコンピュータである。図１において、オペレーションシステム２０は、ネットワーク情報収集部２１を有する。ネットワーク情報収集部２１は、オペレーションシステム２０にインストールされたプログラムが、オペレーションシステム２０のＣＰＵに実行させる処理により実現される。オペレーションシステム２０は、また、ネットワーク情報記憶部２２を利用する。ネットワーク情報記憶部２２は、オペレーションシステム２０が有する補助記憶装置等を用いて実現可能である。
【００１２】
ネットワーク情報収集部２１は、例えば、ネットワーク４０のトポロジー情報や、各リンクの容量情報、及びネットワーク４０で発生した各トラヒック需要に関する情報等をネットワーク４０から収集し、ネットワーク情報記憶部２２に記憶する。
【００１３】
パス埋め込み算出装置１０は、オペレーションシステム２０によってネットワーク４０から収集された情報に基づいて、ネットワーク４０において発生した各トラヒック需要のパスを、時系列順に、ネットワーク４０を表現する無向グラフに最短経路で埋め込む（配置する）処理を実行する。図１において、パス埋め込み算出装置１０は、情報取得部１１及びパス埋め込み算出部１２等を有する。これら各部は、パス埋め込み算出装置１０にインストールされたプログラムが、パス埋め込み算出装置１０のＣＰＵ（図２のＣＰＵ１０４）に実行させる処理により実現される。パス埋め込み算出装置１０は、また、トラヒック情報記憶部１３及びグラフ情報記憶部１４等を有する。これら各記憶部は、パス埋め込み算出装置１０の補助記憶装置（図２の補助記憶装置１０２）、又はパス埋め込み算出装置１０にネットワークを介して接続可能な記憶装置等を用いて実現可能である。
【００１４】
情報取得部１１は、オペレーションシステム２０のネットワーク情報記憶部２２に記憶されている情報を取得し、取得された情報に基づくグラフ情報及びトラヒック情報のそれぞれを、グラフ情報記憶部１４又はトラヒック情報記憶部１３に記憶する。グラフ情報は、ネットワーク４０の構成を表現する無向グラフを示す情報である。当該無向グラフを構成するノード間のリンク（枝）には、当該リンクに対応する、ネットワーク４０におけるリンクの容量が付与される。グラフ情報は、例えば、ネットワーク情報記憶部２２に記憶されているトポロジー情報や各リンクの容量情報等から導出される。トラヒック情報は、ネットワーク４０において発生したトラヒック需要が時系列に配列された情報である。トラヒック情報は、ネットワーク情報記憶部２２に記憶されている、各トラヒック需要に関する情報から導出可能である。トラヒック情報において、各トラヒック需要は、トラヒックのソースノード（始点ノード）点及びデスティノーションノード（終点ノード）を示す情報と、トラヒック量とを含む。
【００１５】
パス埋め込み算出部１２は、トラヒック情報記憶部１３及びグラフ情報記憶部１４に記憶されたトラヒック情報及びグラフ情報を用いて、各トラヒック需要を疎通させるパスの最短経路を算出する。
【００１６】
操作端末３０は、ネットワーク４０の運用者、または、設計者が直接操作する端末である。操作端末３０は、結果表示部３１を有する。結果表示部３１は、ネットワーク４０の運用者、または、設計者による操作に応じ、パス埋め込み算出装置１０に対して、設計、運用、又は管理の対象であるネットワーク４０に関して埋め込まれたパスに関する情報の取得を要求し、パス埋め込み算出装置１０から返信される情報を表示する。
【００１７】
図２は、本発明の実施の形態におけるパス埋め込み算出装置のハードウェア構成例を示す図である。図２のパス埋め込み算出装置１０は、それぞれバスＢで相互に接続されているドライブ装置１００、補助記憶装置１０２、メモリ装置１０３、ＣＰＵ１０４、及びインタフェース装置１０５等を有する。
【００１８】
パス埋め込み算出装置１０での処理を実現するプログラムは、ＣＤ−ＲＯＭ等の記録媒体１０１によって提供される。プログラムを記憶した記録媒体１０１がドライブ装置１００にセットされると、プログラムが記録媒体１０１からドライブ装置１００を介して補助記憶装置１０２にインストールされる。但し、プログラムのインストールは必ずしも記録媒体１０１より行う必要はなく、ネットワークを介して他のコンピュータよりダウンロードするようにしてもよい。補助記憶装置１０２は、インストールされたプログラムを格納すると共に、必要なファイルやデータ等を格納する。
【００１９】
メモリ装置１０３は、プログラムの起動指示があった場合に、補助記憶装置１０２からプログラムを読み出して格納する。ＣＰＵ１０４は、メモリ装置１０３に格納されたプログラムに従ってパス埋め込み算出装置１０に係る機能を実行する。インタフェース装置１０５は、ネットワークに接続するためのインタフェースとして用いられる。
【００２０】
以下、パス埋め込み算出装置１０が実行する処理手順について説明する。図３は、パス埋め込み算出装置が実行する処理手順の一例を説明するためのフローチャートである。
【００２１】
ステップＳ１０１において、パス埋め込み算出部１２は、グラフ情報記憶部１４に記憶されているグラフ情報を取得して、無向グラフＧを特定する。ここで、無向グラフＧ＝｛Ｎ、Ｅ｝とする。但し、Ｎ、Ｅは、それぞれネットワーク４０に属するノード、リンクの集合とする。ノード数＃Ｎ＝ｎとする。ノードには番号が付与される。リンクｅ∈Ｅにはリンク容量ｙ（ｅ）が付与されている。
【００２２】
続いて、パス埋め込み算出部１２は、トラヒック情報記憶部１３に記憶されているトラヒック需要を、時系列順に一つ取得する（Ｓ１０２）。トラヒック情報記憶部１３には、時系列ｍの順に、各トラヒック需要ｕ（ｍ）について、ソースノードｓ（ｍ）、デスティネーションノードｔ（ｍ）、及びトラヒック量が記憶されている（但し、１≦ｓ（ｍ）、ｔ（ｍ）≦ｎ））。以下、取得されたトラヒック需要を、「対象トラヒック需要」という。
【００２３】
続いて、パス埋め込み算出部１２は、無向グラフＧに対して、対象トラヒック需要を最短経路で疎通可能なパスを埋め込む（配置する）（Ｓ１０３）。すなわち、対象トラヒック需要のトラヒック量以上の容量ｙ（ｅ）を有するリンクｅを使用して、対象トラヒック需要のソースノードｓ（ｍ）からデスティネーションノードｔ（ｍ）へ最短経路で到達可能なパスが、無向グラフＧに埋め込まれる。ここで、ｕ（ｍ）を疎通するパスｐ（ｍ）は、次の容量制約（１）を満たすものとする。
Ｓｅ＝｛ｍ｜ｐ（ｍ）はリンクｅを疎通する。｝と置く。
Σｍ∈Ｓ＿ｅｕｍ≦ｙ（ｅ），ｅ∈Ｅ        （１）
各パスｐ（ｍ）は（１）を満たしつつ、経路長（経路に含まれるリンクの数）を最小化するように最短経路が選択される。
【００２４】
なお、対象トラヒック需要のパスが配置されたリンクｅの容量ｙ（ｅ）は、対象トラヒック需要のトラヒック量によって消費される。すなわち、容量ｙ（ｅ）は、ｙ（ｅ）から対象トラヒック需要のトラヒック量を差し引いた値によって更新される。
【００２５】
対象トラヒック需要のパスを埋め込めた場合（Ｓ１０４でＹｅｓ）、パス埋め込み算出部１２は、トラヒック情報記憶部１３に未処理のトラヒック需要（時系列順において対象トラヒック需要の次のトラヒック需要）が記憶されているか否かを判定する（Ｓ１０５）。該当するトラヒック需要が記憶されている場合（Ｓ１０５でＮｏ）、対象トラヒック需要の次のトラヒック需要に関してステップＳ１０２以降が実行される。すなわち、ｍ＝１から順に、パスｐ（ｍ）が無向グラフＧに埋め込まれていく。
【００２６】
パスｐ（ｍ）が埋め込まれていく過程において、例えば、ｍ＝ｍ１において、どのように経路をとってもパスｐ（ｍ１）を、容量制約（１）を満たすように無向グラフＧ１に埋め込むことができなくなると（Ｓ１０４でＮｏ）、パス埋め込み算出部１２は、既にパスが埋め込まれたトラヒック需要のうちの一部のトラヒック需要について、パスの再配置を実行する（Ｓ１０５）。
【００２７】
パスの再配置を行うときの制約条件は次の通りである。ノード（ｉ，ｊ）ペア（ノードｉとノードｊとのペア）がリンクとして存在するときは、ｃ（ｉ，ｊ）＝１とし、リンクとして存在しないときはｃ（ｉ，ｊ）＝０とする。リンクは無向グラフＧでｃ（ｉ，ｊ）＝ｃ（ｊ，ｉ）とする。リンク（ｉ，ｊ）の容量をｙ（ｉ，ｊ）とする。リンク（ｉ，ｊ）が存在しないときは、ｙ（ｉ，ｊ）＝０とする。パスｐ（ｍ）がリンク（ｉ，ｊ）を含み、ノードｉからノードｊの方向にトラヒックが流れるとき、ｘ（ｉ，ｊ，ｍ）＝１、そうでないとき、ｘ（ｉ，ｊ，ｍ）＝０とする。ｘ（ｉ，ｊ，ｍ）は未知変数と考える。
【００２８】
パスが枝分かれしない条件として、次のフロー保存則（２）−（４）が成立する。
Σｊ（ｃ（ｉ，ｊ）×ｘ（ｉ，ｊ，ｍ）−ｃ（ｊ，ｉ）×ｘ（ｊ，ｉ，ｍ））＝０，  ｉ≠ｓ（ｍ），ｉ≠ｔ（ｍ），１≦ｍ≦ｍ１        （２）
Σｊ（ｃ（ｓ（ｍ），ｊ）×ｘ（ｓ（ｍ），ｊ，ｎ）−ｃ（ｊ，ｓ（ｍ））×ｘ（ｊ，ｓ（ｍ），ｍ））＝１，１≦ｍ≦ｍ１        （３）
Σｊ（ｃ（ｔ（ｍ），ｊ）×ｘ（ｔ（ｍ），ｊ，ｍ）−ｃ（ｊ，ｔ（ｍ））×ｘ（ｊ，ｔ（ｍ），ｍ））＝−１，１≦ｍ≦ｍ１        （４）
パスがループを作らない条件は次の通りである。
Σｊｃ（ｉ，ｊ）×ｘ（ｉ，ｊ，ｍ）≦１，ｉ≠ｓ（ｍ），ｉ≠ｔ（ｍ），１≦ｍ≦ｍ１        （５）
リンクの容量制約条件は次の通りである。
Σｎｕ（ｍ）×（ｃ（ｉ，ｊ）×ｘ（ｉ，ｊ，ｍ）＋ｃ（ｊ，ｉ）×ｘ（ｊ，ｉ，ｍ））≦ｙ（ｉ，ｊ）        （６）
制約条件（２）−（６）の下で、目的関数としてパスのトラヒック×リンク長の総和を次のようにとり、最小化する。
Ｍｉｎｉｍｉｚｅ  Σｉ，ｊ，ｎｕ（ｎ）×ｃ（ｉ，ｊ）×ｘ（ｉ，ｊ，ｎ）        （７）
パス再配置法最適化問題（２）−（７）は、０−１整数計画問題として、分枝限定法として厳密解を算出できるが、ｍ１の値が増えると計算が困難になる。解をヒューリスティックに求める手法としてＷＣＳＰ法があるが、この手法は厳密解があっても解が存在しないと結果を出すこともあるし、ｍ１の値が増えるとやはり計算が困難になる。そこで、本実施の形態では、既に埋め込まれたトラヒック需要ｕ（ｍ）（１≦ｍ≦ｍ１−１）のうち、一部のトラヒック需要のパスに限定して、一部のパスについて、分枝限定法又はＷＣＳＰ法が実行されて、再配置が行われる（すなわち、計算（２）−（７）が実行される）。そうすることで、或る程度の精度の解を、高速に得ることができる。
【００２９】
この際、パスの再配置の対象とする一部のトラヒック需要の一例として以下の（ａ）〜（ｊ）が挙げられる。
（ａ）対象トラヒック需要に対して時系列順に直前のｋ個のトラヒック需要
この場合、パス埋め込み算出部１２は、対象トラヒック需要に対して時系列順に直前のｋ個のトラヒック需要を、再配置の対象として選択する。
（ｂ）時系列順に最初からｋ個のトラヒック需要
この場合、パス埋め込み算出部１２は、時系列順に最初からｋ番目までのトラヒック需要を、再配置の対象として選択する。
（ｃ）既にパスが埋め込まれたトラヒック需要の中からランダムに（任意に）選択されるｋ個のトラヒック需要
この場合、パス埋め込み算出部１２は、既にパスが埋め込まれたトラヒック需要の中からランダムにｋ個のトラヒック需要を選択する。
（ｄ）既にパスが埋め込まれたトラヒック需要のうち、トラヒック量の大きい順にｋ個のトラヒック需要
この場合、パス埋め込み算出部１２は、既にパスが埋め込まれたトラヒック需要の中からトラヒック量の大きい順にｋ個のトラヒック需要を選択する。
（ｅ）既にパスが埋め込まれたトラヒック需要のうち、リンク長（リンクの数）が大きい順にｋ個のトラヒック需要
この場合、パス埋め込み算出部１２は、既にパスが埋め込まれたトラヒック需要ごとに、リンク長を算出し、算出されたリンク長ｎお大きい順にｋ個のトラヒック需要を選択する。
（ｆ）既にパスが埋め込まれたトラヒック需要のうち、リンク長×トラヒック量が大きい順にｋ個のトラヒック需要
この場合、パス埋め込み算出部１２は、既にパスが埋め込まれたトラヒック需要ごとに、リンク長×トラヒック量を算出し、算出結果の大きい順にｋ個のトラヒック需要を選択する。
（ｇ）既にパスが埋め込まれたトラヒック需要のうち、埋め込まれたパス上のノードの次数の和（合計）の大きい順にｋ個のトラヒック需要
この場合、パス埋め込み算出部１２は、既にパスが埋め込まれたトラヒック需要ごとに、当該トラヒック需要に係るパス上の各ノードの次数の合計を算出し、算出された合計の大きい順にｋ個のトラヒック需要を選択する。なお、ノードの次数とは、ノードに接続するリンクの数である。
（ｈ）既にパスが埋め込まれたトラヒック需要のうち、埋め込まれたパス上のノードの媒介中心性の和（合計）の大きい順にｋ個のトラヒック需要
この場合、パス埋め込み算出部１２は、既にパスが埋め込まれたトラヒック需要ごとに、当該トラヒック需要のパス上の各ノードに重なるパス（既に埋め込まれたパス）の数の合計を算出し、算出された数の合計の大きい順にｋ個のトラヒック需要を選択する。なお、ノードの媒介中心性とは、ノードに最短経路が重なる数（回数）をいう。
（ｉ）既にパスが埋め込まれたトラヒック需要のうち、埋め込まれたパス上のリンクの媒介中心性の和（合計）の大きい順にｋ個のトラヒック需要
この場合、パス埋め込み算出部１２は、既にパスが埋め込まれたトラヒック需要ごとに、当該トラヒック需要のパス上の各リンクに重なるパス（既に埋め込まれたパス）の数の合計を算出し、算出された数の合計の大きい順にｋ個のトラヒック需要を選択する。なお、リンクの媒介中心性とは、リンクに最短経路が重なる数（回数）をいう。
（ｊ）既にパスが埋め込まれたトラヒック需要のうち、ｄ（ｓ０，ｓ）＋ｄ（ｔ０，ｔ）の値の小さい順にｋ個のトラヒック需要
なお、ｓ０は、対象トラヒック需要のソースノード、ｄ０は、対象トラヒック需要のデスティネーションノード、ｓは、既にパスが埋め込まれた各トラヒック需要のソースノード、ｄは、当該各トラヒック需要のデスティネーションノードである。また、ｄ（ｓ０，ｓ）は、ｓ０、ｓ間のリンク長であり、ｄ（ｔ０，ｔ）は、ｔ０、ｔ間のリンク長である。
【００３０】
この場合、パス埋め込み算出部１２は、既にパスが埋め込まれたトラヒック需要ごとに、当該トラヒック需要のソースノードｓと対象トラヒック需要のソースノードｓ０との間のリンク長ｄ（ｓ０，ｓ）と、当該トラヒック需要のデスティネーションノードｄと対象トラヒック需要のデスティネーションノードｄ０との間のリンク長ｄ（ｄ０，ｄ）との合計（ｄ（ｓ０，ｓ）＋ｄ（ｔ０，ｔ））を算出し、算出された合計の小さい順にｋ個のトラヒック需要を選択する。例えば、既に５個のトラヒック需要についてパスが埋め込まれている場合、ｄ（ｓ０，ｓ）＋ｄ（ｔ０，ｔ）は、５個算出される。その中から値の小さい順にｋ番目までのトラヒック需要が、再配置対象として選択される。
【００３１】
なお、パスの再配置は、再配置対象のトラヒック需要ごとに、当該トラヒック需要のトラヒック量が、当該トラヒック需要のパスが配置されたリンクの容量に戻された後に実行される。但し、再配置対象以外のトラヒック需要のトラヒック量は消費されたままである。
【００３２】
パスの再配置に続き、パス埋め込み算出部１２は、改めて、ステップＳ１０３と同様に、対象トラヒック需要を最短経路で疎通可能なパスを埋め込む（配置する）（Ｓ１０７）。この際、対象トラヒック需要のパスを埋め込めなかった場合には、対象トラヒック需要のパスの埋め込みは断念して、ステップＳ１０５が実行される。
【００３３】
なお、その後にパスを埋め込めないトラヒック需要が有った場合には（Ｓ１０４でＮｏ）、再びパスの再配置が実行される（Ｓ１０６）。全てのトラヒック需要について処理が完了すると（Ｓ１０５でＹｅｓ）、図３の処理は終了する。
【００３４】
上述したように、本実施の形態によれば、既にパスが配置された全てのトラヒック需要ではなく、一部のトラヒック需要に限定されてパスの再配置が行われる。その結果、トラヒック需要の経路を時系列に配置する場合の経路の再配置のための計算時間のための計算時間を短縮することができる。
【００３５】
続いて、３０個のノードを含むネットワークに対して、２００個のトラヒック需要に係るパスの埋め込みを試行した結果を以下に示す。当該試行において、ネットワークの構成（各ノード間の接続関係）は、図４に示す通りである。図４において、各ノードの内部の数字は、各ノードを識別するための番号（以下、「ノード番号」という。）を示す。
【００３６】
また、各ノード間のリンクの容量は、図５に示される通りである。図５には、３０行３０列のマトリクス（行列）によって各ノード間のリンクの容量が示されている。すなわち、図５の行列において、各要素の値は、当該要素に係る行に対応するノードと、当該要素に係る列に対応するノードとの間のリンクの容量を示す。但し、０は、該当するリンクが無いことを示す。
【００３７】
また、２００個のトラヒック需要は、以下の通りである。以下において、「項番」の列は、時系列の順番を示す。「発」の列は、ソースノードのノード番号を示す。「着」の列は、デスティネーションノードのノード番号を示す。トラヒック量は、トラヒック量を示す。
項番    発    着    トラヒック量
1    27    16    25
2    13    8    20
3    1    13    5
4    29    28    15
5    3    25    30
6    3    25    30
7    3    25    30
8    3    25    30
9    3    19    30
10    3    19    30
11    11    8    25
12    8    21    20
13    8    21    20
14    8    21    20
15    8    21    20
16    8    21    30
17    8    21    30
18    23    6    30
19    23    6    30
20    23    6    30
21    23    6    30
22    23    21    30
23    23    21    30
24    29    17    30
25    23    6    10
26    23    6    10
27    23    6    10
28    23    6    10
29    23    21    30
30    23    21    30
31    2    26    10
32    2    26    10
33    2    26    10
34    2    26    10
35    2    20    30
36    2    20    30
37    9    3    15
38    9    3    15
39    9    3    15
40    9    3    15
41    9    14    30
42    9    14    30
43    26    19    25
44    26    19    25
45    26    19    25
46    26    19    25
47    26    25    30
48    26    25    30
49    23    22    30
50    23    22    30
51    23    22    30
52    23    22    30
53    23    10    30
54    23    10    30
55    27    30    25
56    30    26    10
57    30    26    10
58    30    26    10
59    30    26    10
60    30    26    30
61    30    26    30
62    5    15    5
63    4    2    20
64    1    14    15
65    8    1    5
66    28    15    10
67    7    19    5
68    18    7    30
69    3    15    10
70    3    15    10
71    3    15    10
72    3    15    10
73    3    28    30
74    3    28    30
75    25    21    15
76    25    21    15
77    25    21    15
78    25    21    15
79    25    26    30
80    25    26    30
81    29    27    30
82    13    19    5
83    1    9    20
84    10    6    10
85    10    6    10
86    10    6    10
87    10    6    10
88    10    29    30
89    10    29    30
90    18    28    25
91    17    5    30
92    1    26    20
93    1    26    20
94    1    26    20
95    1    26    20
96    1    20    30
97    1    20    30
98    15    28    15
99    7    17    30
100    13    1    15
101    14    6    25
102    3    20    30
103    3    20    30
104    3    20    30
105    3    20    30
106    3    1    30
107    3    1    30
108    10    11    30
109    10    11    30
110    10    11    30
111    10    11    30
112    10    24    30
113    10    24    30
114    24    21    25
115    24    21    25
116    24    21    25
117    24    21    25
118    24    21    30
119    24    21    30
120    27    6    5
121    20    30    25
122    20    30    25
123    20    30    25
124    20    30    25
125    20    6    30
126    20    6    30
127    17    15    25
128    18    30    25
129    7    3    5
130    7    3    5
131    7    3    5
132    7    3    5
133    7    10    30
134    7    10    30
135    2    10    15
136    2    10    15
137    2    10    15
138    2    10    15
139    2    27    30
140    2    27    30
141    28    5    30
142    10    3    20
143    10    3    20
144    10    3    20
145    10    3    20
146    10    24    30
147    10    24    30
148    8    27    20
149    4    8    5
150    14    13    25
151    26    7    10
152    26    7    10
153    26    7    10
154    26    7    10
155    26    25    30
156    26    25    30
157    13    15    20
158    27    5    10
159    14    17    30
160    7    23    15
161    7    23    15
162    7    23    15
163    7    23    15
164    7    10    30
165    7    10    30
166    30    20    30
167    30    20    30
168    30    20    30
169    30    20    30
170    30    6    30
171    30    6    30
172    3    2    15
173    3    2    15
174    3    2    15
175    3    2    15
176    3    30    30
177    3    30    30
178    15    22    15
179    28    11    10
180    1    17    10
181    20    4    30
182    20    4    30
183    20    4    30
184    20    4    30
185    20    1    30
186    20    1    30
187    2    21    20
188    2    21    20
189    2    21    20
190    2    21    20
191    2    30    30
192    2    30    30
193    13    20    15
194    13    20    15
195    13    20    15
196    13    20    15
197    13    26    30
198    13    26    30
199    17    19    30
200    22    7    15
また、試行の実行環境は、ＰＣ（３．４０ＧＨｚ，Ｉｎｔｅｌ  Ｃｏｒｅ）である。以下の試行結果における（ａ）〜（ｊ）は、ステップＳ１０６の説明における、一部のトラヒック需要の選択方法に対応する。但し、以下の（ａ）〜（ｊ）において、ｋの値（再配置のパスの数）は５である。
（従来の再配置法）埋め込めたパス数：７５本、計算時間：２９３７秒
（ａ）埋め込めたパス数：７６本、計算時間：２３８８秒
（ｂ）埋め込めたパス数：７４本、計算時間：２１４６秒
（ｃ）埋め込めたパス数：７３本、計算時間：２１４３秒
（ｄ）埋め込めたパス数：７４本、計算時間：２１４５秒
（ｅ）埋め込めたパス数：６８本、計算時間：２１３８秒
（ｆ）埋め込めたパス数：７０本、計算時間：２１４９秒
（ｇ）埋め込めたパス数：７３本、計算時間：２１４４秒
（ｈ）埋め込めたパス数：７３本、計算時間：２１４３秒
（ｉ）埋め込めたパス数：７１本、計算時間：２１４６秒
（ｊ）埋め込めたパス数：７４本、計算時間：２１４１秒
（ａ）〜（ｊ）の１０例を、従来の再配置法と比較すると、埋め込めるパス数の変化を抑制しつつ、計算時間を大きく短縮できることが分かる。
【００３８】
なお、本実施の形態において、パス埋め込み算出装置１０は、経路配置装置の一例である。パス埋め込み算出部１２は、経路配置部の一例である。
【００３９】
以上、本発明の実施例について詳述したが、本発明は斯かる特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【符号の説明】
【００４０】
１０          パス埋め込み算出装置
１１          情報取得部
１２          パス埋め込み算出部
１３          トラヒック情報記憶部
１４          グラフ情報記憶部
２０          オペレーションシステム
２１          ネットワーク情報収集部
２２          ネットワーク情報記憶部
３０          操作端末
３１          結果表示部
４０          ネットワーク
１００        ドライブ装置
１０１        記録媒体
１０２        補助記憶装置
１０３        メモリ装置
１０４        ＣＰＵ
１０５        インタフェース装置
Ｂ            バス
【図１】
0006374823.tif 000002
【図２】
0006374823.tif 000003
【図３】
0006374823.tif 000004
【図４】
0006374823.tif 000005
【図５】
0006374823.tif 000006