(57)【要約】【課題】トラヒック需要の経路を時系列に配置する場合の経路の再配置を効率化すること。【解決手段】経路配置装置は、ネットワークを構成するノード間のリンクの容量を示す情報と、時系列に発生するトラヒック需要ごとに、トラヒック量、始点ノード、及び終点ノードを示す情報と、を参照して、各トラヒック需要を時系列の順番で、当該トラヒック需要のトラヒック量以上の容量を有するリンクを使用して、当該トラヒック需要の始点ノードから終点ノードまでの最短経路を配置すると共に、当該最短経路を構成する各リンクの容量を当該トラヒック量で消費する過程において、或るトラヒック需要に関して最短経路を配置することができない場合には、既に最短経路が配置されたトラヒック需要のうちの一部のトラヒック需要について最短経路を解放し、一部のトラヒック需要のうち、リンクの容量を相対的に多く消費するトラヒック需要から先に最短経路を再配置する。【選択図】図１
2018022957.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークを構成するノード間のリンクの容量を示す情報と、
時系列に発生するトラヒック需要ごとに、トラヒック量、始点ノード、及び終点ノードを示す情報と、
を参照して、
前記各トラヒック需要を前記時系列の順番で、当該トラヒック需要のトラヒック量以上の容量を有するリンクを使用して、当該トラヒック需要の始点ノードから終点ノードまでの最短経路を配置すると共に、当該最短経路を構成する各リンクの容量を当該トラヒック量で消費する過程において、或るトラヒック需要に関して最短経路を配置することができない場合には、既に最短経路が配置されたトラヒック需要のうちの一部のトラヒック需要について最短経路を解放し、前記一部のトラヒック需要のうち、リンクの容量を相対的に多く消費するトラヒック需要から先に最短経路を再配置する再配置部、
を有することを特徴とする経路配置装置。
【請求項２】
ネットワークを構成するノード間のリンクの容量を示す情報と、
時系列に発生するトラヒック需要ごとに、トラヒック量、始点ノード、及び終点ノードを示す情報と、
を参照して、
前記各トラヒック需要を前記時系列の順番で、当該トラヒック需要のトラヒック量以上の容量を有するリンクを使用して、当該トラヒック需要の始点ノードから終点ノードまでの最短経路を配置すると共に、当該最短経路を構成する各リンクの容量を当該トラヒック量で消費する過程において、或るトラヒック需要に関して最短経路を配置することができない場合には、既に最短経路が配置されたトラヒック需要のうちの一部のトラヒック需要について最短経路を解放し、前記一部のトラヒック需要の最短経路の全通りの配置順の中で、再配置される最短経路によるリンクの容量の消費の総和が最小となる配置順で、前記一部のトラヒック需要の最短経路を再配置する再配置部、
を有することを特徴とする経路配置装置。
【請求項３】
ネットワークを構成するノード間のリンクの容量を示す情報と、
時系列に発生するトラヒック需要ごとに、トラヒック量、始点ノード、及び終点ノードを示す情報と、
を参照して、
前記各トラヒック需要を前記時系列の順番で、当該トラヒック需要のトラヒック量以上の容量を有するリンクを使用して、当該トラヒック需要の始点ノードから終点ノードまでの最短経路を配置すると共に、当該最短経路を構成する各リンクの容量を当該トラヒック量で消費する過程において、或るトラヒック需要に関して最短経路を配置することができない場合には、既に最短経路が配置されたトラヒック需要のうちの一部のトラヒック需要について最短経路を解放し、前記一部の各トラヒック需要の最短経路の全通りの配置順の中で、前記リンクの残余帯域の分散が最小となる配置順で、前記一部のトラヒック需要群の最短経路を再配置する再配置部、
を有することを特徴とする経路配置装置。
【請求項４】
ネットワークを構成するノード間のリンクの容量を示す情報と、
時系列に発生するトラヒック需要ごとに、トラヒック量、始点ノード、及び終点ノードを示す情報と、
を参照して、
前記各トラヒック需要を前記時系列の順番で、当該トラヒック需要のトラヒック量以上の容量を有するリンクを使用して、当該トラヒック需要の始点ノードから終点ノードまでの最短経路を配置すると共に、当該最短経路を構成する各リンクの容量を当該トラヒック量で消費する過程において、或るトラヒック需要に関して最短経路を配置することができない場合には、既に最短経路が配置されたトラヒック需要のうちの一部のトラヒック需要について最短経路を解放し、前記一部のトラヒック需要のうち、リンクの容量を相対的に多く消費するトラヒック需要から先に最短経路を再配置する再配置手順、
をコンピュータが実行することを特徴とする経路配置方法。
【請求項５】
ネットワークを構成するノード間のリンクの容量を示す情報と、
時系列に発生するトラヒック需要ごとに、トラヒック量、始点ノード、及び終点ノードを示す情報と、
を参照して、
前記各トラヒック需要を前記時系列の順番で、当該トラヒック需要のトラヒック量以上の容量を有するリンクを使用して、当該トラヒック需要の始点ノードから終点ノードまでの最短経路を配置すると共に、当該最短経路を構成する各リンクの容量を当該トラヒック量で消費する過程において、或るトラヒック需要に関して最短経路を配置することができない場合には、既に最短経路が配置されたトラヒック需要のうちの一部のトラヒック需要について最短経路を解放し、前記一部のトラヒック需要の最短経路の全通りの配置順の中で、再配置される最短経路によるリンクの容量の消費の総和が最小となる配置順で、前記一部のトラヒック需要の最短経路を再配置する再配置手順、
をコンピュータが実行することを特徴とする経路配置方法。
【請求項６】
ネットワークを構成するノード間のリンクの容量を示す情報と、
時系列に発生するトラヒック需要ごとに、トラヒック量、始点ノード、及び終点ノードを示す情報と、
を参照して、
前記各トラヒック需要を前記時系列の順番で、当該トラヒック需要のトラヒック量以上の容量を有するリンクを使用して、当該トラヒック需要の始点ノードから終点ノードまでの最短経路を配置すると共に、当該最短経路を構成する各リンクの容量を当該トラヒック量で消費する過程において、或るトラヒック需要に関して最短経路を配置することができない場合には、既に最短経路が配置されたトラヒック需要のうちの一部のトラヒック需要について最短経路を解放し、前記一部の各トラヒック需要の最短経路の全通りの配置順の中で、前記リンクの残余帯域の分散が最小となる配置順で、前記一部のトラヒック需要群の最短経路を再配置する再配置手順、
をコンピュータが実行することを特徴とする経路配置方法。
【請求項７】
請求項１乃至３いずれか一項記載の再配置部としてコンピュータを機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路配置装置、経路配置方法、及びプログラムに関する。
【背景技術】
【０００２】
ネットワークを構成する各リンクとのリンク容量と、ネットワーク上の特定対地間の時系列のトラヒック需要が与えられている状態において、この時系列のトラヒック需要を疎通するためのパスを、各時点での空き帯域に最短経路で埋め込むことを考える。リンク容量は有限なため、ある時点でネットワークにパスは埋め込めなくなる。このとき、これまでに埋め込んだ全てのパスの再配置によって、新たにパスを埋め込める可能性が出てくる。新たなパスを埋め込めた場合には、そのまま次の時点のトラヒック需要を最短経路で埋め込んでいく。新たなパスを埋め込めなかった場合には、そのトラヒック需要を廃棄して、次のトラヒック需要を最短経路で埋め込んでいく。これが、パス埋め込み問題におけるパス再配置問題である。
【０００３】
このように、リンク容量制約のあるネットワークにパスを１本ずつ埋め込んでいき、埋め込めなくなったときに、これまで埋め込んだパス全体の再配置を行う技術は、０−１整数計画法として定式化でき、分枝限定法によって厳密解を求める手法又はＷＣＳＰ法によってヒューリスティックに解く手法が知られていた。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】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）又はインターネット等のネットワークを介して通信可能に接続される。
【００１２】
オペレーションシステム２０は、ネットワーク４０（通信網）上のノード及びノード間のリンク等を管理する１以上のコンピュータである。図１において、オペレーションシステム２０は、ネットワーク情報収集部２１を有する。ネットワーク情報収集部２１は、オペレーションシステム２０にインストールされたプログラムが、オペレーションシステム２０のＣＰＵに実行させる処理により実現される。オペレーションシステム２０は、また、ネットワーク情報記憶部２２を利用する。ネットワーク情報記憶部２２は、オペレーションシステム２０が有する補助記憶装置等を用いて実現可能である。
【００１３】
ネットワーク情報収集部２１は、例えば、ネットワーク４０のトポロジー情報や、各リンクの容量情報、及びネットワーク４０で発生した各トラヒック需要に関する情報等をネットワーク４０から収集し、ネットワーク情報記憶部２２に記憶する。
【００１４】
パス埋め込み算出装置１０は、オペレーションシステム２０によってネットワーク４０から収集された情報に基づいて、ネットワーク４０において発生した各トラヒック需要のパス（経路）を、時系列順に、ネットワーク４０を表現する無向グラフに最短経路で埋め込む（配置する）処理を実行する。
【００１５】
図１において、パス埋め込み算出装置１０は、情報取得部１１及びパス埋め込み算出部１２等を有する。これら各部は、パス埋め込み算出装置１０にインストールされたプログラムが、パス埋め込み算出装置１０のＣＰＵ（図２のＣＰＵ１０４）に実行させる処理により実現される。パス埋め込み算出装置１０は、また、トラヒック情報記憶部１３及びグラフ情報記憶部１４等を有する。これら各記憶部は、パス埋め込み算出装置１０の補助記憶装置（図２の補助記憶装置１０２）、又はパス埋め込み算出装置１０にネットワークを介して接続可能な記憶装置等を用いて実現可能である。
【００１６】
情報取得部１１は、オペレーションシステム２０のネットワーク情報記憶部２２に記憶されている情報を取得し、取得された情報に基づくグラフ情報及びトラヒック情報のそれぞれを、グラフ情報記憶部１４又はトラヒック情報記憶部１３に記憶する。グラフ情報は、ネットワーク４０の構成を表現する無向グラフを示す情報である。当該無向グラフを構成するノード間のリンク（枝）には、当該リンクに対応する、ネットワーク４０におけるリンクの容量が付与される。グラフ情報は、例えば、ネットワーク情報記憶部２２に記憶されているトポロジー情報や各リンクの容量情報等から導出される。トラヒック情報は、ネットワーク４０において発生したトラヒック需要が時系列に配列された情報である。トラヒック情報は、ネットワーク情報記憶部２２に記憶されている、各トラヒック需要に関する情報から導出可能である。トラヒック情報において、各トラヒック需要は、トラヒックのソースノード（始点ノード）点及びデスティネーションノード（終点ノード）を示す情報と、トラヒック量とを含む。
【００１７】
パス埋め込み算出部１２は、トラヒック情報記憶部１３及びグラフ情報記憶部１４に記憶されたトラヒック情報及びグラフ情報を用いて、各トラヒック需要を疎通させるパスの最短経路を算出する。
【００１８】
操作端末３０は、ネットワーク４０の運用者、または、設計者が直接操作する端末である。操作端末３０は、結果表示部３１を有する。結果表示部３１は、ネットワーク４０の運用者、または、設計者による操作に応じ、パス埋め込み算出装置１０に対して、設計、運用、又は管理の対象であるネットワーク４０に関して埋め込まれたパスに関する情報の取得を要求し、パス埋め込み算出装置１０から返信される情報を表示する。
【００１９】
図２は、本発明の実施の形態におけるパス埋め込み算出装置のハードウェア構成例を示す図である。図２のパス埋め込み算出装置１０は、それぞれバスＢで相互に接続されているドライブ装置１００、補助記憶装置１０２、メモリ装置１０３、ＣＰＵ１０４、及びインタフェース装置１０５等を有する。
【００２０】
パス埋め込み算出装置１０での処理を実現するプログラムは、ＣＤ−ＲＯＭ等の記録媒体１０１によって提供される。プログラムを記憶した記録媒体１０１がドライブ装置１００にセットされると、プログラムが記録媒体１０１からドライブ装置１００を介して補助記憶装置１０２にインストールされる。但し、プログラムのインストールは必ずしも記録媒体１０１より行う必要はなく、ネットワークを介して他のコンピュータよりダウンロードするようにしてもよい。補助記憶装置１０２は、インストールされたプログラムを格納すると共に、必要なファイルやデータ等を格納する。
【００２１】
メモリ装置１０３は、プログラムの起動指示があった場合に、補助記憶装置１０２からプログラムを読み出して格納する。ＣＰＵ１０４は、メモリ装置１０３に格納されたプログラムに従ってパス埋め込み算出装置１０に係る機能を実行する。インタフェース装置１０５は、ネットワークに接続するためのインタフェースとして用いられる。
【００２２】
以下、パス埋め込み算出装置１０が実行する処理手順について説明する。図３は、パス埋め込み算出装置が実行する処理手順の一例を説明するためのフローチャートである。
【００２３】
ステップＳ１０１において、パス埋め込み算出部１２は、グラフ情報記憶部１４に記憶されているグラフ情報を取得して、無向グラフＧを特定する。ここで、無向グラフＧ＝｛Ｎ、Ｅ｝とする。但し、Ｎ、Ｅは、それぞれネットワーク４０に属するノード、リンクの集合とする。ノード数＃Ｎ＝ｎとする。ノードには番号が付与される。リンクｅ∈Ｅにはリンク容量ｙ（ｅ）が付与されている。
【００２４】
続いて、パス埋め込み算出部１２は、トラヒック情報記憶部１３に記憶されているトラヒック需要を、時系列順に一つ取得する（Ｓ１０２）。トラヒック情報記憶部１３には、時系列ｍの順に、各トラヒック需要ｕ（ｍ）について、ソースノードｓ（ｍ）、デスティネーションノードｔ（ｍ）、及びトラヒック量が記憶されている（但し、１≦ｓ（ｍ）、ｔ（ｍ）≦ｎ））。以下、取得されたトラヒック需要を、「対象トラヒック需要」という。
【００２５】
続いて、パス埋め込み算出部１２は、無向グラフＧに対して、対象トラヒック需要を最短経路で疎通可能なパスを埋め込む（配置する）（Ｓ１０３）。すなわち、対象トラヒック需要のトラヒック量以上の容量ｙ（ｅ）を有するリンクｅを使用して、対象トラヒック需要のソースノードｓ（ｍ）からデスティネーションノードｔ（ｍ）へ最短経路で到達可能なパスが、無向グラフＧに埋め込まれる。ここで、ｕ（ｍ）を疎通するパスｐ（ｍ）は、次の容量制約（１）を満たすものとする。
Ｓｅ＝｛ｍ｜ｐ（ｍ）はリンクｅを疎通する。｝と置く。
Σｍ∈Ｓ＿ｅｕｍ≦ｙ（ｅ），ｅ∈Ｅ        （１）
各パスｐ（ｍ）は容量制約（１）を満たしつつ、経路長（経路に含まれるリンクの数）を最小化するように最短経路が選択される。
【００２６】
なお、対象トラヒック需要のパスが配置されたリンクｅの容量ｙ（ｅ）は、対象トラヒック需要のトラヒック量によって消費される。すなわち、容量ｙ（ｅ）は、ｙ（ｅ）から対象トラヒック需要のトラヒック量を差し引いた値によって更新される。
【００２７】
対象トラヒック需要のパスを埋め込めた場合（Ｓ１０４でＹｅｓ）、パス埋め込み算出部１２は、トラヒック情報記憶部１３に未処理のトラヒック需要（時系列順において対象トラヒック需要の次のトラヒック需要）が記憶されているか否かを判定する（Ｓ１０５）。該当するトラヒック需要が記憶されている場合（Ｓ１０５でＮｏ）、対象トラヒック需要の次のトラヒック需要に関してステップＳ１０２以降が実行される。すなわち、ｍ＝１から順に、パスｐ（ｍ）が無向グラフＧに埋め込まれていく。
【００２８】
パスｐ（ｍ）が埋め込まれていく過程において、例えば、ｍ＝ｍ１において、どのように経路をとってもパスｐ（ｍ１）を、容量制約（１）を満たすように無向グラフＧ１に埋め込むことができなくなると（Ｓ１０４でＮｏ）、パス埋め込み算出部１２は、既にパスが埋め込まれたトラヒック需要のうちの一部のトラヒック需要について、パスの再配置を実行する（Ｓ１０５）。
【００２９】
この際、パスの再配置の対象とする一部のトラヒック需要の一例として以下の（ａ）〜（ｊ）が挙げられる。
（ａ）対象トラヒック需要に対して時系列順に直前のｋ個のトラヒック需要
この場合、パス埋め込み算出部１２は、対象トラヒック需要に対して時系列順に直前のｋ個のトラヒック需要を、再配置の対象として選択する。
（ｂ）時系列順に最初からｋ個のトラヒック需要
この場合、パス埋め込み算出部１２は、時系列順に最初からｋ番目までのトラヒック需要を、再配置の対象として選択する。
（ｃ）既にパスが埋め込まれたトラヒック需要の中からランダムに（任意に）選択されるｋ個のトラヒック需要
この場合、パス埋め込み算出部１２は、既にパスが埋め込まれたトラヒック需要の中からランダムにｋ個のトラヒック需要を選択する。
（ｄ）既にパスが埋め込まれたトラヒック需要のうち、トラヒック量の大きい順にｋ個のトラヒック需要
この場合、パス埋め込み算出部１２は、既にパスが埋め込まれたトラヒック需要の中からトラヒック量の大きい順にｋ個のトラヒック需要を選択する。
（ｅ）既にパスが埋め込まれたトラヒック需要のうち、リンク長（リンクの数）が大きい順にｋ個のトラヒック需要
この場合、パス埋め込み算出部１２は、既にパスが埋め込まれたトラヒック需要ごとに、リンク長を算出し、算出されたリンク長ｎお大きい順にｋ個のトラヒック需要を選択する。
（ｆ）既にパスが埋め込まれたトラヒック需要のうち、リンク長×トラヒック量が大きい順にｋ個のトラヒック需要
この場合、パス埋め込み算出部１２は、既にパスが埋め込まれたトラヒック需要ごとに、リンク長×トラヒック量を算出し、算出結果の大きい順にｋ個のトラヒック需要を選択する。
（ｇ）既にパスが埋め込まれたトラヒック需要のうち、埋め込まれたパス上のノードの次数の和（合計）の大きい順にｋ個のトラヒック需要
この場合、パス埋め込み算出部１２は、既にパスが埋め込まれたトラヒック需要ごとに、当該トラヒック需要に係るパス上の各ノードの次数の合計を算出し、算出された合計の大きい順にｋ個のトラヒック需要を選択する。なお、ノードの次数とは、ノードに接続するリンクの数である。
（ｈ）既にパスが埋め込まれたトラヒック需要のうち、埋め込まれたパス上のノードの媒介中心性の和（合計）の大きい順にｋ個のトラヒック需要
この場合、パス埋め込み算出部１２は、既にパスが埋め込まれたトラヒック需要ごとに、当該トラヒック需要のパス上の各ノードに重なるパス（既に埋め込まれたパス）の数の合計を算出し、算出された数の合計の大きい順にｋ個のトラヒック需要を選択する。なお、ノードの媒介中心性とは、ノードに最短経路が重なる数（回数）をいう。
（ｉ）既にパスが埋め込まれたトラヒック需要のうち、埋め込まれたパス上のリンクの媒介中心性の和（合計）の大きい順にｋ個のトラヒック需要
この場合、パス埋め込み算出部１２は、既にパスが埋め込まれたトラヒック需要ごとに、当該トラヒック需要のパス上の各リンクに重なるパス（既に埋め込まれたパス）の数の合計を算出し、算出された数の合計の大きい順にｋ個のトラヒック需要を選択する。なお、リンクの媒介中心性とは、リンクに最短経路が重なる数（回数）をいう。
（ｊ）既にパスが埋め込まれたトラヒック需要のうち、ｄ（ｓ０，ｓ）＋ｄ（ｔ０，ｔ）の値の小さい順にｋ個のトラヒック需要
なお、ｓ０は、対象トラヒック需要のソースノード、ｄ０は、対象トラヒック需要のデスティネーションノード、ｓは、既にパスが埋め込まれた各トラヒック需要のソースノード、ｄは、当該各トラヒック需要のデスティネーションノードである。また、ｄ（ｓ０，ｓ）は、ｓ０、ｓ間のリンク長であり、ｄ（ｔ０，ｔ）は、ｔ０、ｔ間のリンク長である。
【００３０】
この場合、パス埋め込み算出部１２は、既にパスが埋め込まれたトラヒック需要ごとに、当該トラヒック需要のソースノードｓと対象トラヒック需要のソースノードｓ０との間のリンク長ｄ（ｓ０，ｓ）と、当該トラヒック需要のデスティネーションノードｄと対象トラヒック需要のデスティネーションノードｄ０との間のリンク長ｄ（ｄ０，ｄ）との合計（ｄ（ｓ０，ｓ）＋ｄ（ｔ０，ｔ））を算出し、算出された合計の小さい順にｋ個のトラヒック需要を選択する。例えば、既に５個のトラヒック需要についてパスが埋め込まれている場合、ｄ（ｓ０，ｓ）＋ｄ（ｔ０，ｔ）は、５個算出される。その中から値の小さい順にｋ番目までのトラヒック需要が、再配置対象として選択される。
【００３１】
なお、再配置対象とされたトラヒック需要に係るパスの埋め込みは、再配置対象のトラヒック需要ごとに、当該トラヒック需要のパスが解放された後に実行される。パスの解放とは、当該パスのトラヒック量が、当該トラヒック需要のパスが配置されたリンクの容量に戻されることをいう。但し、再配置対象以外のトラヒック需要のトラヒック量は消費されたままである。
【００３２】
パス埋め込み算出部１２は、再配置の対象とされたトラヒック需要に係るパスを、時系列順に関わらない順番で無向グラフＧに埋め込む。パスを１つずつ順に再配置していくとすると、空き容量が大きい前半は、パスを埋め込むのに十分なリンク残余帯域があり、空き容量が小さくなる後半は、パスを埋め込むのに必要なリンク残余帯域が不足するという特性がある。したがって、仮に、再配置対象のトラヒック需要を時系列に埋め込んだ場合、斯かる特性を生かしてパスの再配置を実行することができない。そこで、パス埋め込み算出部１２は、以下手法１〜５のいずれかの手法で、再配置の対象とされたパスを埋め込むことで、パスの埋め込み効率を上げる。
【００３３】
以下の手法１、２、３は、空き容量の大きい再配置の前半に、埋め込みにくいパスを埋め込む発見的手法である。
【００３４】
手法１：解放したパスのトラヒック量（帯域）が相対的に大きいトラヒック需要から順に最短経路でパスを埋め込む。トラヒック量の大きいパスはリンク容量を多く消費するので、先に埋め込もうという発見的手法である。
【００３５】
手法２：解放したパスの発着信ノードをつなぐ最短経路のホップ数が相対的に大きいトラヒック需要から順に最短経路でパス埋め込む。ホップ数の大きいパスはリンク容量を多く消費するので、先に埋め込もうという発見的手法である。
【００３６】
手法３：手法１と手法２を掛け合わせたもので、解放したパスの「トラヒック量（帯域）×発着信ノードをつなぐ最短経路のホップ数」が相対的に大きいトラヒック需要から先に最短経路でパスを埋め込む。これは、トラヒック量（帯域）とホップ数の大きいパスはリンク容量を相対的に多く消費するので、先に埋め込もうという発見的手法である。
【００３７】
以下の手法４、５は、パスの再配置順序の入れ替えの総当たりを行い、その中で、最も適切な（リンクの容量の消費が最も小さい）埋め込みを行う再配置順序を選ぶ発見的手法である。
【００３８】
手法４：パスが解放されたトラヒック需要の最短経路の埋め込み順序の入れ替えを総当たりで行い、最も埋め込みパスのホップ数の総和の小さい埋め込み順序を選ぶ。埋め込み順序の入れ替えを行ったとき、最もリンク容量を消費しないでパスを埋め込む埋め込み順序を選ぶ発見的手法である。
【００３９】
手法５：パスが解放されたトラヒック需要の最短経路の埋め込み順序の入れ替えを総当たりで行い、リンクの残余帯域の分散が最小の埋め込み順序を選ぶ。「分散＝残余帯域の２乗の平均−残余帯域の平均の２乗」なので、分散の最小化は、リンクの残余帯域の２乗和が最小の場合を選ぶことで実現できる。この手法は、残余帯域を均等化する効果があり、残余帯域が不均一な網に適用した場合に、パス再配置の成功率を一層上げると考えられる。
【００４０】
なお、手法４及び５は、解放したパス数が少ない場合（例えば、パス数が閾値以下である場合）に限って実行されてもよい。
【００４１】
パスの再配置に続き、パス埋め込み算出部１２は、改めて、ステップＳ１０３と同様に、対象トラヒック需要を最短経路で疎通可能なパスを埋め込む（配置する）（Ｓ１０７）。この際、対象トラヒック需要のパスを埋め込めなかった場合には、対象トラヒック需要のパスの埋め込みは断念して、ステップＳ１０５が実行される。
【００４２】
なお、その後にパスを埋め込めないトラヒック需要が有った場合には（Ｓ１０４でＮｏ）、再びパスの再配置が実行される（Ｓ１０６）。全てのトラヒック需要について処理が完了すると（Ｓ１０５でＹｅｓ）、図３の処理は終了する。
【００４３】
図４は、簡単な動作例を説明するための図である。図４に示されるノード網の各ノード番号は、ノード番号を１、２、３、４であるとする。リンク容量をｄ（１，２）＝ｄ（１，３）＝ｄ（２，３）＝ｄ（２，４）＝ｄ（３，４）＝５０とし、それ以外は０とする。
【００４４】
この網に、トラヒック量（帯域）の大きい順に埋め込まない例としてトラヒック需要時系列ｕ１（２，３）＝２０、ｕ２（２，３）＝４０、ｕ３（２，４）＝４０、ｕ４（１，２）＝２０、ｕ５（１，３）＝２０を考える。ｕ２はｕ１を最初に埋め込んだために迂回しなければならず、そのためにｕ４、ｕ５が埋め込めなくなってしまう。次にトラヒック量（帯域）の大きい順に埋め込むトラヒック需要時系列ｕ１（２，３）＝４０、ｕ２（２，４）＝４０、ｕ３（２，３）＝２０、ｕ４（１，２）＝２０、ｕ５（１、３）＝２０を考える。ｕ２は迂回をせずに最短経路で埋め込めるので全てのトラヒック需要が埋め込める。この例は、そのまま、トラヒック需要の埋め込み順序の入れ替えを総当たりで行い、埋め込みパスのホップ数の総和を小さくするケースを選ぶとパスが埋め込みやすくなる例となっている。
【００４５】
図５は、計算例を説明するための図である。図５における物理網は、ノード数１５の連結グラフで、３つの地域網とそれらをつなぐ基幹網からなるとする。地域網、基幹網のリンク容量は１００Ｍｂｐｓ、その間のリンク容量を５０Ｍｂｐｓである。トラヒックは生成のみを考え、退去は考慮しない。トラヒック需要として、地域網をまたがった対地間は５Ｍｂｐｓ、地域内に閉じた対地間は４０Ｍｂｐｓ、８０Ｍｂｐｓの混在デマンド（全部で８１件のトラヒック需要で総帯域は１８４０Ｍｂｐｓ）を考えた。この例では、トラヒック需要に対して、再配置を行わないパス埋め込みと再配置を行っても物理網から解放した順にパス埋め込みを行う場合には、総埋め込み帯域は１２８０Ｍｂｐｓで、解放したパス番号順に再配置をしても効果がなかった。ここで、手法１、手法２、手法３を適用してトラヒック需要（帯域）に対するパス埋め込みを行うと、総埋め込み帯域は１７２０Ｍｂｐｓとなり網使用効率は向上した。手法４、手法５を適用してトラヒック需要（帯域）に対するパス埋め込みを行うと、総帯域１８４０Ｍｂｐｓすべてをパスとして埋め込むことができた。このようにパス埋め込み順序が障害となって再配置が失敗してしまう場合に、本実施の形態は、その改善策となることが分かる。
【００４６】
上述したように、本実施の形態によれば、既にパスが配置された全てのトラヒック需要ではなく、一部のトラヒック需要に限定されてパスの再配置が行われる。その結果、トラヒック需要の経路を時系列に配置する場合の経路の再配置のための計算時間を短縮することができる。
【００４７】
また、再配置の対象とされたトラヒック需要のパスの埋め込みについては、リンク容量の消費が相対的に多いパスが先に埋め込めこまれ、リンク容量の消費が相対的に少ないパスが後に埋め込まれるか、パス再配置対象のパス数が少ない場合には、それらのパス群の再配置順序の入れ替えの総当たり計算を行い、網のリソースを最も効率的に利用する場合か最もリンク残余帯域が均等になる場合のパスの再配置順序が選ばれるため、再配置を効率的に行うことができる。
【００４８】
なお、本実施の形態において、パス埋め込み算出装置１０は、経路配置装置の一例である。パス埋め込み算出部１２は、再配置部の一例である。
【００４９】
以上、本発明の実施例について詳述したが、本発明は斯かる特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【符号の説明】
【００５０】
１０          パス埋め込み算出装置
１１          情報取得部
１２          パス埋め込み算出部
１３          トラヒック情報記憶部
１４          グラフ情報記憶部
２０          オペレーションシステム
２１          ネットワーク情報収集部
２２          ネットワーク情報記憶部
３０          操作端末
３１          結果表示部
４０          ネットワーク
１００        ドライブ装置
１０１        記録媒体
１０２        補助記憶装置
１０３        メモリ装置
１０４        ＣＰＵ
１０５        インタフェース装置
Ｂ            バス
【図１】
2018022957.tif 000003
【図２】
2018022957.tif 000004
【図３】
2018022957.tif 000005
【図４】
2018022957.tif 000006
【図５】
2018022957.tif 000007