(57)【要約】【課題】最適な光パス配置を簡単な処理で検索する。【解決手段】全てのノードの組合せに対して初期光パスを設定する。初期光パスの中で、トラフィックが最小の光パスを最小光パスとして選択する。最小光パスが解除可能か否かの判定を行う。連結性判定過程での判定の結果、最小光パスが解除不可能な場合には、最小光パスを非解除光パスに変更し、一方、最小光パスが解除可能な場合には、最小光パスを解除光パスに変更し、及び、解除光パスのトラフィックを退避する。各ノードで用いられるインタフェース数が、使用可能インタフェース数条件を満たすか判定する。インタフェース数条件を満たすまで、上述の最小光パス選択過程、連結性判定過程、光パス変更過程及びインタフェース数判定過程を繰り返し行う。【選択図】図６
2006270460.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードと、隣接するノード間を接続して波長多重光信号を伝送する光ファイバとを備える光ネットワークにおける最適光パス配置を検索する最適光パス検索装置であって、
前記複数のノードから得られたトラフィック情報に基づいてトラフィックマトリックスを生成するトラフィック監視手段と、
全てのノードの組合せに対して初期光パスを設定する初期化手段と、
前記初期光パスの中で、トラフィックが最小の光パスを最小光パスとして選択する最小光パス選択手段と、
該最小光パスが解除可能か否かの判定を行う連結性判定手段と、
前記最小光パスが解除不可能な場合には、前記最小光パスを非解除光パスに変更し、一方、前記最小光パスが解除可能な場合には、前記最小光パスを解除光パスに変更し、及び該解除光パスのトラフィックを退避する光パス変更手段と、
各ノードで用いられるインタフェース数が、使用可能インタフェース数条件を満たすか否かの判定を行うインタフェース数判定手段と
を備えることを特徴とする最適光パス検索装置。
【請求項２】
複数のノードと、隣接するノード間を接続して波長多重光信号を伝送する光ファイバとを備える光ネットワークにおいて、前記複数のノードから得られたトラフィック情報に基づいて生成されたトラフィックマトリックスに基づいて最適光パス配置を検索するにあたり、
全てのノードの組合せに対して初期光パスを設定する初期化過程と、
前記初期光パスの中で、トラフィックが最小の光パスを最小光パスとして選択する最小光パス選択過程と、
該最小光パスが解除可能か否かの判定を行う連結性判定過程と、
前記判定の結果、前記最小光パスが解除不可能な場合には、前記最小光パスを非解除光パスに変更し、一方、前記最小光パスが解除可能な場合には、前記最小光パスを解除光パスに変更し、及び、該解除光パスのトラフィックを退避する光パス変更過程と、
各ノードで用いられるインタフェース数が、使用可能インタフェース数条件を満たすか否かの判定を行うインタフェース数判定過程と
を備え、
インタフェース数条件を満たすまで、前記最小光パス選択過程、前記連結性判定過程、前記光パス変更過程及び前記インタフェース数判定過程を繰り返し行うことを特徴とする最適光パス検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、波長多重光ネットワークでの最適な光パス配置を検索するための、最適光パス検索装置及び最適光パス検索方法に関する。
【背景技術】
【０００２】
近年、インターネットの普及等により通信需要が急速に増大している。それに対応して光ファイバ等を用いた高速でかつ大容量の光通信ネットワークが整備されつつある。このような光通信ネットワークでは、波長分割多重（ＷＤＭ：Ｗａｖｅｌｅｎｇｔｈ  Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅｘｉｎｇ）方法が必要不可欠である。波長分割多重（ＷＤＭ）とは、光波長が異なる搬送波を多重化する技術である。ＷＤＭを用いることにより、１本の光伝送路に複数の搬送波を並列的に伝搬させることができるので、大容量の通信ネットワークを低コストで構築することができる。
【０００３】
このＷＤＭ方法を用いた光通信ネットワークは、ルータを備える複数のノードと、光ファイバで構成されるノード間を接続する経路（パス）とを備えて構成される。この光ネットワークにおいて、ノードは、光分岐挿入機能（ＯＡＤＭ：Ｏｐｔｉｃａｌ  Ａｄｄ  Ｄｒｏｐ  Ｍｕｌｔｉｐｌｅｘｅｒ）や光クロスコネクト機能（ＯＸＣ：Ｏｐｔｉｃａｌ  Ｃｒｏｓｓ  Ｃｏｎｎｅｃｔ）等を備えるものが使用される。光分岐挿入機能とは、ＷＤＭを用いて多重化された光搬送波に他の波長の光搬送波を挿入したり、当該多重光搬送波から特定波長の光搬送波を分岐させたりする機能である。また、光クロスコネクト機能とは、ＷＤＭを用いて多重化された光搬送波の伝播経路を、波長単位で切り替える機能である。これらの機能を用いることにより、光伝送路によって構築された光通信ネットワーク（すなわち物理トポロジー）上に、複数の光パスからなる光パス配置（論理トポロジー）を構築することが可能になる。
【０００４】
ＷＤＭを用いた光通信ネットワークとして、光ファイバで障害又は輻輳などの通信を妨げる状況が発生した場合は、動的に光パス配置を変更することにより、通信を妨げる状況から回避し、通信状態を復旧する方法が提案されている。光パス配置の変更は、障害又は輻輳区間（以下、単に障害区間と称する。）を迂回することにより、又は、輻輳が発生したノードをカットスルーさせることにより可能になる。ここで、カットスルーとは、当該ノードが備えるルーティング機能を使用せずに、すなわち、ＯＡＤＭ又はＯＸＣのみを用いて、通信パケットを、そのまま、ノードを経て、通過させることである（例えば、特許文献１参照）。輻輳が発生したノードにカットスルーパスを設定することにより、当該ノードの処理負荷を軽減することができる。
【０００５】
光パスを動的に変更して障害区間を迂回する方法としては、専有プロテクション法や共有プロテクション法が知られている。専有プロテクション法とは、１本の光パスを、他の１本の光パスで代用する方法である。また、共有プロテクション法とは、複数本の光パスを、他の１本の光パスで代用する方法である。
【特許文献１】特開２００３−２１８９１２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述の従来例の方法は、単に障害区間を迂回することにより通信状況を復旧する方法にすぎず、迂回後の光パス配置は、必ずしも最適な光パス配置とはいえない。それは、この従来技術によれば、特定のノードにトラフィックが集中した場合、当該ノードをカットスルーする光パスを新たに設定することによって、当該ノードの処理負荷を軽減することができるが、一方、このような当該ノードをカットスルーするパス設定が他のノードの処理負荷を増大させてしまう場合があるからである。
【０００７】
また、この従来技術によれば、光パスの設定が変更される場合、当該光通信ネットワークでは、ＩＰ（Ｉｎｔｅｒｎｅｔ  ｐｒｏｔｏｃｏｌ）レイヤのルーティング情報が変更される。従って、新たにカットスルーパスを設定した場合に、そのカットスルーパスが最適経路であると判断されて、当該カットスルーパスにトラフィックが集中する場合がある。このような場合、カットスルーされるノードの処理負荷が過大になることはないが、当該カットスルーパスの終端をなすノードでは処理負荷が増大してしまう。
【０００８】
このような理由から、カットスルーパスを新たに設定する際には、ＩＰレイヤでの経路変更も考慮した上で、光通信ネットワーク全体でトラフィックの集中が発生しないようにすることが望まれる。
【０００９】
しかしながら、光通信ネットワーク全体での光パス配置の設定パターン数は、その光通信ネットワークで使用される波長数やノード数の増加に応じて、指数関数的に増加する。このため、すべての設定パターンについて光通信ネットワーク全体でのトラフィック発生状況を予想して最適なカットスルーパスを選択しようとすると、処理負担が膨大となり、現実的でない。
【００１０】
この発明は、上述の問題点に鑑みてなされたものであり、この発明の目的は、最適な光パス配置を効率的に検索することができる最適光パス検索装置及び最適光パス検索方法を提供することにある。
【課題を解決するための手段】
【００１１】
上述した目的を達成するために、この発明の最適光パス検索装置は、複数のノードと、隣接するノード間を接続して波長多重光信号を伝送する光ファイバとを備える光ネットワークにおける光パスを検索するものであり、トラフィック監視手段と、初期化手段と、最小光パス選択手段と、連結性判定手段と、光パス変更手段と、インタフェース数判定手段とを備えている。
【００１２】
トラフィック監視手段は、複数のノードから得られたトラフィック情報に基づいてトラフィックマトリックスを生成する。初期化手段は、全てのノードの組合せに対して初期光パスを設定する。最小光パス選択手段は、初期光パスの中で、トラフィックが最小の光パスを最小光パスとして選択する。連結性判定手段は、最小光パス選択手段で選択された最小光パスが、解除可能か否かの判定を行う。光パス変更手段は、最小光パスが解除不可能な場合には、最小光パスを非解除光パスに変更し、一方、最小光パスが解除可能な場合には、最小光パスを解除光パスに変更して、及び、解除光パスのトラフィックを退避する。インタフェース数判定手段は、各ノードで用いられるインタフェース数が、使用可能インタフェース数条件を満たすか判定する。
【００１３】
また、この発明の最適光パス検索方法は、複数のノードと、隣接するノード間を接続して波長多重光信号を伝送する光ファイバとを備える光ネットワークにおいて、複数のノードから得られたトラフィック情報に基づいて生成されたトラフィックマトリックスに基づいて光パスを検索するものであり以下の過程を備えている。
【００１４】
先ず、初期化過程において、全てのノードの組合せに対して初期光パスを設定する。次に、最小光パス選択過程において、初期光パスの中で、トラフィックが最小の光パスを最小光パスとして選択する。次に、連結性判定過程において、最小光パスが解除可能か否かの判定を行う。次に、光パス変更過程において、連結性判定過程での判定の結果、最小光パスが解除不可能な場合には、最小光パスを非解除光パスに変更し、一方、最小光パスが解除可能な場合には、最小光パスを解除光パスに変更し、及び、解除光パスのトラフィックを退避する。次に、インタフェース数判定過程において、各ノードで用いられるインタフェース数が、使用可能インタフェース数条件を満たすか判定する。インタフェース数条件を満たすまで、上述の最小光パス選択過程、連結性判定過程、光パス変更過程及びインタフェース数判定過程を繰り返し行う。
【発明の効果】
【００１５】
この発明の最適光パス検索装置及び最適光パス検索方法によれば、仮想的に全てのノードの組み合わせに対して初期光パスを設定し、パケットの到達性を保ちながらトラフィックの少ない順に初期光パスを解除していくので、効率的に最適光パス配置を得ることができる。
【発明を実施するための最良の形態】
【００１６】
以下、図を参照して、この発明の実施の形態について説明するが、構成および配置関係についてはこの発明が理解できる程度に概略的に示したものに過ぎない。また、以下、この発明の好適な構成例につき説明するが、各構成要素の数値的条件などは、単なる好適例にすぎず、この発明は以下の実施の形態に限定されない。
【００１７】
図１は、この発明の最適光パス配置の検索を行う内部ネットワークを説明するための概略構成図である。内部ネットワークは、格子状に配置された複数のノード（以下、Ｎで表すこともある。）と、隣接するノード間を接続して波長多重光信号を伝送する光ファイバと、複数のノードの各々に接続されている管理装置とを備える格子型波長多重光ネットワークである。
【００１８】
ここでは、内部ネットワークは、９個のノードが３×３の格子状に配置されているものとして説明する。これらのノードには、それぞれ固有のノードＩＤが割り当てられていて、ここではノードＩＤを１から９までの自然数とする。例えば、Ｎ１はノードＩＤが１であるノードを示す。
【００１９】
各ノード（Ｎ１〜Ｎ９）の構成の詳細については後述するが、各ノードは外部ネットワークと接続されるルータ、及び光信号の伝送経路を定める光路切換部を備えている。
【００２０】
隣接するノード間は、光ファイバにより物理的に接続されている。これらの光ファイバには、それぞれ固有のファイバＩＤが割り当てられていて、ここではファイバＩＤを１から１２までの自然数とする。また、光ファイバをＦで表し、例えばＦ１はファイバＩＤが１である光ファイバを表す。光ファイバＦ１〜Ｆ１２は、隣接するノード間で双方向に通信可能であり、かつ、波長多重により波長の異なる複数の光信号を多重した波長多重光信号を伝送可能であるもとする。なお、ノード間を接続する光ファイバは１本ずつとして、双方向波長多重光通信を行う構成としても良いし、２本の光ファイバを備えて、一方向の波長多重光通信を行う構成としても良い。光ファイバは、使用する波長など設定に応じて、任意好適な構成とすることができる。ここでは、内部ネットワークを９個のノードが格子状に配列された格子型波長多重光ネットワークとして説明したが、ノードの個数、及び、ネットワークの構成はこの例に何ら限定されるものではない。
【００２１】
図２は、図１を参照して説明した内部ネットワークの経路（パス）配置の制御を行うための制御ネットワークの説明に供する概略構成図である。
【００２２】
制御ネットワークは、ノード（Ｎ１〜Ｎ９）と、管理装置２７０、及び管理装置２７０と各ノード（Ｎ１〜Ｎ９）との間で制御信号の送受信を行う制御回線２５０を備えて構成されている。制御回線２５０は、設定回線２５１及び測定回線２５３を備えている。管理装置２７０で生成された設定信号は、設定回線２５１を経てＮ１〜Ｎ９へ送られる。また、Ｎ１〜Ｎ９でのトラフィックの測定結果は、測定回線２５３を経て、管理装置２７０へ送られる。
【００２３】
図３は、ノード（Ｎ）の構成を説明するための概略構成図である。
【００２４】
ノードは、第１〜４の入力光ファイバ３０１ａ〜３０１ｄ、第１〜４の分波器３２１ａ〜３２１ｄ、光路切換部３３０、第１〜４の合波器３２６ａ〜３２６ｄ、第１〜４の出力光ファイバ３０６ａ〜３０６ｄ、ルータ３５０、第１〜４の変換装置３５３ａ〜３５３ｄ、及び制御装置３３５を備えている。光路切換部３３０は、終端部３３１及び光スイッチ部３３３を備えている。
【００２５】
ノードには、入力光ファイバ３０１ａ〜３０１ｄを経て、他のノードから波長多重された光信号が入力される。ここでは、光信号は４種類の波長を多重した波長多重信号として説明するが、何ら４種類に限定されるものではない。これらの４種類の波長には、それぞれ固有の波長ＩＤが割り当てられていて、ここでは波長ＩＤを１から４までの自然数とする。また、以下の説明では、波長をλで表し、例えばλ１は、波長ＩＤが１である波長を示す。
【００２６】
入力光ファイバ３０１ａ〜３０１ｄを経て入力された波長多重信号は、第１〜４の分波器３２１ａ〜３２１ｄで波長がλ１〜λ４である４つの分波信号に分波される。各分波信号は、終端部３３１を経て、光スイッチ部３３３に送信される。終端部３３１は、分波器３２１ａ〜３２１ｄから分波信号を取り出してルータ３５０に送る機能と、ルータ３５０から送られた光信号を光スイッチ部３３３へ送る機能を備えていて、例えば、任意好適な周知のＯＡＤＭ（Ｏｐｔｉｃａｌ  Ａｄｄ  Ｄｒｏｐ  Ｍｕｌｔｉｐｌｅｘｉｎｇ）装置で実現できる。ここで、ノードは４つの入力光ファイバ３０１ａ〜３０１ｄを備えていて、それぞれが４つの分波信号に分波されるので、終端部３３１に入力される分波信号は１６系統になる。終端部３３１は、この１６系統の分波信号が通る光路のそれぞれにＯＡＤＭ装置を備えて構成することができる。各ＯＡＤＭ装置は、制御装置３３５からの終端制御信号に応答して、通過（カットスルー）状態と、終端状態との間で切換を行う。ここで、カットスルー状態は、分波器３２１ａ〜３２１ｄから入力された分波信号を、ルータ３５０を通過せずに、直接光スイッチ部３３３に送っている状態である。また、終端状態は、分波器３２１ａ〜３２１ｄから終端部３３１に入力された分波信号をルータ３５０に送り、かつルータ３５０から受信した光信号を終端部３３１から光スイッチ部３３３へ送っている状態、すなわち、各波長の光信号をルータで中継する状態である。
【００２７】
光スイッチ部３３３に入力された分波信号は、第１〜４の合波器３２６ａ〜３２６ｄのいずれか１つに出力される。この分波信号の光路の切換は、１６系統の分波信号のそれぞれに対して行われるため、光スイッチ部３３３は１６個の１×４光スイッチ装置を備えて構成することができる。ここで１×４光スイッチ装置は、１つの入力に対して４つのチャネルから１つを選択して出力するものであり、任意好適な周知のものを用いることができる。各１×４光スイッチ装置は、制御装置３３５からの切換制御信号に応答して、終端部３３１から送られた光信号を、第１〜４の合波器３２６ａ〜３２６ｄのいずれか１つに出力する。
【００２８】
第１〜４の合波器３２６ａ〜３２６ｄは、入力された光信号を合波、すなわち、波長多重する。第１〜４の合波器３２６ａ〜３２６ｄには、第１〜４の出力光ファイバ３０６ａ〜３０６ｄが１対１に対応していて、波長多重された光信号が出力光ファイバから出力される。
【００２９】
なお、入力光ファイバ３０１ａ〜３０１ｄと対応する分波器３２１ａ〜３２１ｄのそれぞれの間、及び、合波器３２６ａ〜３２６ｄと対応する出力光ファイバ３０６ａ〜３０６ｄのそれぞれの間には、入出力される波長多重光信号を増幅するための増幅器が設けられることもある。
【００３０】
ノードが外部ネットワーク３６０から受信したパケットは、トラフィック計測装置３５７を経てルータ３５０に送られる。トラフィック計測装置３５７は、パケットから、ＩＰアドレスなどの送信元及び宛先情報と、パケットの伝送量を、トラフィックとして取得する機能を備え、トラフィックの計測結果を、測定回線２５３を経て管理装置２７０に送信する。トラフィック計測装置３５７は任意好適な周知のものを用いることができる。
【００３１】
ルータ３５０は、第１〜４の内部インタフェース３５１ａ〜３５１ｄを備え、受信したパケットをルータ３５０が備える経路情報に従って、内部インタフェース３５１ａ〜３５１ｄのいずれかを経て出力させる。ルータ３５０は任意好適な周知のものを用いることができる。
【００３２】
ルータ３５０から出力されたパケットは、変換装置３５３ａ〜３５３ｄで電気信号から光信号に変換されて終端部３３１へ送られる。ここで、変換装置３５３ａ〜３５３ｄは、第１〜４の内部インタフェース３５１ａ〜３５１ｄに１対１に対応して設けられている。第１の内部インタフェース３５１ａから出力されたパケットは、第１の変換装置３５３ａで波長λ１の光信号に変換される。第２の内部インタフェース３５１ｂから出力されたパケットは、第２の変換装置３５３ｂで波長λ２の光信号に変換される。第３の内部インタフェース３５１ｃから出力されたパケットは、第３の変換装置３５３ｃで波長λ３の光信号に変換される。第４の内部インタフェース３５１ｄから出力されたパケットは、第４の変換装置３５３ｄで波長λ４の光信号に変換される。変換された光信号は、終端部３３１のＯＡＤＭ装置を経て光スイッチ部３３３に送られ、所定の出力光ファイバから出力される。
【００３３】
また、終端部３３１からルータ３５０へ送られるパケットは、波長λ１、λ２、λ３及びλ４のいずれかの光信号であるので、これらの光信号をＩＰルータで処理できる信号に変換する。例えば、ルータ３５０で処理できる信号が電気信号の場合は、第１〜４の変換装置３５３ａ〜３５３ｄが、電気―光変換器及び光―電気変換器を備える構成とすればよい。
【００３４】
管理装置２７０から各ノードに送られる設定信号は、ルータ３５０が備える経路情報を書き換える経路書換信号、終端部３３１に対する終端制御信号、及び光スイッチ部３３３に対する切換制御信号を含んでいる。設定信号は、管理装置２７０から設定回線２５１を経て制御装置３３５に送られる。制御装置３３５は、設定信号の受信に応答してルータ３５０、終端部３３１及び光スイッチ部３３３に、それぞれ、経路書換信号、終端制御信号及び切換制御信号を送信する。
【００３５】
（最適光パス検索装置）
図４は、管理装置２７０を説明するための概略構成図である。管理装置２７０は、ＭＰＵ（Ｍｉｃｒｏｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）２８０、記憶部４５０、送信部２７１、受信部２７３、及び入出力部２７７を備えて構成される、周知のコンピュータ等を用いることができる。入出力部２７７は、コンピュータに通常用いられるキーボード及びマウス等の公知の入力装置、及びディスプレイ等の表示装置を備えている。記憶部４５０には、ハードディスク等の任意好適な周知の記憶装置が用いられる。ＭＰＵ２８０は、周知の構成とすることができ、ここでは、中央処理装置（ＣＰＵ：Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）４００と、メモリとしてのＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）２８３及びＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）２８１を備える構成としている。なお、記憶部４５０は、ＲＡＭ２８３内に設けることも可能である。
【００３６】
ＣＰＵ４００が備える制御手段４０３は、ＲＯＭ２８１等に読み出し自在に記録されているプログラムを読み出して、当該プログラムの実行することにより、ＣＰＵ４００の機能手段として、トラフィック監視手段４１１、目的関数値判定手段４１３、終了条件判定手段４１５、最適光パス検索手段４２０及び光パス配置変更手段４４０を実現する。管理装置２７０は、最適光パス検索手段４２０を備えることで、最適光パス検索装置として機能する。
【００３７】
最適光パス検索手段４２０は、さらに、初期化手段４２１、最小光パス選択手段４２３、連結性判定手段４２５、光パス変更手段４２７、インタフェース（ＩＦ）数判定手段４２９、及び乱数生成手段４３１を備えている。なお、各機能手段が行う処理の詳細は後述する。
【００３８】
受信部２７３は、任意好適な周知の入力インタフェースとすることができる。管理装置２７０に送られたノード（Ｎ１〜Ｎ９）でのトラフィックの測定結果は、受信部２７３を経てトラフィック監視手段４１１に送られる。
【００３９】
トラフィック監視手段４１１は、受信したトラフィックの測定結果に基づいて、トラフィック情報として、ノード間の送受信トラフィックのテーブルとして、トラフィックマトリックス４５８を作成する。トラフィックマトリックス４５８は記憶部４５０に読み出し自在に記憶される。トラフィックマトリックス４５８の詳細については後述する。
【００４０】
光パス配置変更手段４４０は、現在設定されている現用光パス配置から、最適光パス検索手段４２０で検索された最適光パス配置への移行処理を行う。移行処理の詳細は、後述するが、光パス配置変更手段４４０は、さらに、不要光パス選択手段４４３、連結性判定手段４４５、不要光パス解除手段４４１、及び、必要光パス設定手段４４７を備えている。
【００４１】
ここでは、管理装置２７０が、トラフィック監視装置、最適光パス検索装置、及び、光パス設定装置を備える構成として説明したが、それぞれ、図４を参照して説明したのと同様の構成のコンピュータ等を用いた、別の装置とすることもできる。この場合、トラフィック監視装置は、機能手段としてトラフィック監視手段を備え、最適光パス配置検索装置は、機能手段として目的関数値判定手段、終了条件判定手段及び最適光パス検索手段を備え、さらに、光パス設定装置は、機能手段として光パス配置変更手段を備える構成とすればよい。記憶部４５０を共有する構成としてもよいし、トラフィック監視装置、最適光パス検索装置及び光パス設定装置のそれぞれが備える送信部及び受信部を介してデータの送受信を行う構成にしても良い。
【００４２】
（最適光パス検索方法）
図５及び図６を参照して、最適光パス検索方法について説明する。図５は管理装置での処理フローを示す図である。図６は、最適光パス検索フローを示す図である。
【００４３】
ステップ（以下、ステップをＳで表す。）１０において、トラフィック監視手段４１１は、内部ネットワークの各ノードでトラフィックを監視している。トラフィック監視手段４１１は、各ノード（Ｎ１〜Ｎ９）で計測されたトラフィックの測定結果を収集し、その測定結果に基づいて、定期的にトラフィックマトリックス４５８を作成する。作成されたトラフィックマトリックス４５８は記憶部４５０に読み出し自在に記憶される。
【００４４】
Ｓ２０において、目的関数値判定手段４１３は、目的関数値が規定値を満たしているか判定する。目的関数値判定手段４１３は、記憶部４５０に記録されているトラフィックマトリックス４５８及び、現用パステーブル４５２を読み出して、これらを、同じく記憶部４５０から読み出した目的関数４５４に適用して目的関数値を算出する。ここでは、各ノードでの中継トラフィックの和を目的関数とする。現用パステーブル４５２には、現用光パス配置の終端ノードなどの設定情報が記録されている。例えば、現用光パス配置にＮ１とＮ２を直接結ぶ光パスが存在しない場合、Ｎ１からＮ２へパケットを伝送するには、現用光パス配置に存在する光パスを組み合わせて用いることで伝送を行う。ここでは、１つの光パスを用いてＮ１からＮ４へ当該パケットを伝送し、その後、別の光パスを用いてＮ４からＮ２へパケット伝送するものとする。この場合、Ｎ１からＮ２に送信されるトラフィックは、ノード４で中継される。同様に送信先ノードと宛先ノードの全ての組合せについて、ノード毎に中継するトラフィックを足し合わせ、さらに外部ネットワークとルータの間のトラフィックを足し合わせることによって、中継トラフィックが得られる。中継トラフィックの計算結果は、例えばＲＡＭ２８３等に読み出し自在に記録される。
【００４５】
目的関数値判定手段４１３は、ＲＡＭ２８３等に記録されている各ノードでの中継トラフィックと、予めＲＯＭ２８１等に記録されている規定値とを読み出して来て、比較を行う。規定値は、例えば、各ノードについて、ノードが備えるルータにおいて中継処理が可能なトラフィックの最大量に基づいて定められる。中継トラフィックが、規定値を超えているノードがある場合、当該ノードにおいて、輻輳が生じるおそれがある。この場合には、引き続き、Ｓ３０の最適光パス検索過程を実施する。一方、全てのノードにおいて中継トラフィックが規定値以下の場合は、再びＳ１０のトラフィックの監視を行う。
【００４６】
図６を参照して、最適光パス検索過程の詳細について説明する。最適光パス検索過程は、Ｓ１１０からＳ１６０までの過程を備えている。
【００４７】
Ｓ１１０の初期化過程において、初期化手段４２１は、仮想的に全てのノードの組合せに対して初期光パスを設定する。図７は、初期化過程において設定された初期光パスを示す図であって、Ｎ１を終端ノードとする初期光パスのみを示している。初期化過程において、Ｎ２〜Ｎ９についてもＮ１と同様に、他のノードとの間に初期光パスが設定される。
【００４８】
初期化手段４２１は、インタフェーステーブル４６２を作成し、及び、トラフィックマトリックス４５８に基づいて、パステーブル４６０を作成する。図８を参照して、初期状態のトラフィックマトリックス、パステーブル及びインタフェーステーブルについて説明する。なお、トラフィックマトリックス、パステーブル及びインタフェーステーブルをデータテーブルと総称することもある。図８（Ａ）、（Ｂ）及び（Ｃ）は、それぞれ、初期状態のトラフィックマトリックス、パステーブル及びインタフェーステーブルを説明するための図である。
【００４９】
初期状態のトラフィックマトリックス４５８ａには、各ノードで計測された送信元の各ノードに対して、宛先の各ノードへのトラフィックが、マトリックス状に示されている。従って、送信元の各ノードと、宛先の各ノードからそれぞれ１つずつノードを選択すると、送信元のノードから、宛先のノードへのトラフィックを得ることができる（図８（Ａ））。
【００５０】
パステーブル４６０ａは、パスＩＤ毎に、終端ノード、トラフィック量及びフラグを備えている。全てのノードの組み合わせに対して、異なるパスＩＤが割り当てられる。また、光パスをＰで表し、例えばＰ１はパスＩＤが１の光パスを表す。Ｐ１は、終端ノードがＮ１及びＮ２である。トラフィックマトリックス４５８ａによれば、送信元ノードが１であり、かつ、宛先ノードが２であるトラフィックは１であり、送信元ノードが２であり、かつ、宛先ノードが１であるトラフィックは４である。従って、Ｐ１のトラフィックは５（＝１＋４）となる。同様に、それぞれの光パスについてトラフィックを計算してパステーブルを作成する。また、初期化過程では、全ての光パスが初期光パスであり、初期光パスのフラグは、０にする（図８（Ｂ））。
【００５１】
インタフェーステーブル４６２ａは、ノード毎に、インタフェース（ＩＦ）数のデータを備えている。ここでは、ノードが９つあるので、１つのノードから他の全てのノードに光パスを設定すると最大で８の光パスが設定される。この場合、８のインタフェースを用いることになるので、インタフェーステーブル４６２ａのＩＦ数は全て８としておく。なお、このインタフェース数は仮想的に定められるものである。
【００５２】
Ｓ１２０の最小光パス選択過程において、最小光パス選択手段４２３は、初期光パスの中で、トラフィックが最小の光パスを最小光パスとして選択する。具体的には、最小光パス選択手段４２３は、パステーブル４６０ａからフラグが０の光パスの中で、トラフィックが最小のものを選択する。初期化状態のパステーブル４６０ａでは、例えば、トラフィックが１のＰ８が最小光パスとして選択される。ここで、初期光パスの中で、トラフィックが最小の光パスが複数存在する場合は、任意好適な方法で１つの初期光パスを選択すればよく、例えば、乱数を用いて無作為に選択することができる。乱数は、乱数生成手段４３１により、ＲＯＭ２８１等に読み出し自在に書き込まれている乱数表を読み出すことで生成される。また、当該初期光パスの解除の際に退避されるトラフィックが、他のノードに与える影響を調べ、負荷の小さいものを選択する方法などもある。
【００５３】
Ｓ１３０の連結性判定過程において、連結性判定手段４２５は、最小光パスが解除可能か否か、すなわち、最小光パスが解除されても光トポロジーの連結性が保たれるか否かの判定を行う。ここでは、最小光パスが、Ｐ８であるので、Ｎ１とＮ９の間の光パスが解除されたときのパケットの到達性を調べる。初期化された状態では、全てのノード間に光パスが設定されているので、Ｎ１からＮ８までの光パスとＮ８からＮ９までの光パスを用いてＮ１とＮ９の間に、ＩＰパスが設定可能であり、すなわち、Ｐ８が解除可能である。
【００５４】
次に、光パス変更過程を行う。光パス変更過程は、Ｓ１４０及びＳ１５０の過程を備えている。
【００５５】
連結性判定過程での判定の結果、最小光パスが解除不可能な場合には、Ｓ１４０において、最小光パスを非解除光パスに変更した後、再び、Ｓ１２０の最小光パス選択過程を行う。最小光パスを非解除光パスに変更するには、パステーブルの該当する光パスのフラグを２にする。ここでは、最小光パスがＰ８なので、光パス変更手段４２７は、Ｐ８のフラグを２にする。
【００５６】
一方、連結性判定過程での判定の結果、最小光パスが解除可能な場合には、Ｓ１５０において、最小光パスを解除光パスに変更して、当該解除光パスのトラフィックを他のパスに退避させる。ここでは、光パス変更手段４２７は、Ｐ８のフラグを１として、解除光パスのトラフィックを初期光パス又は非解除光パスに移すこと、すなわち、トラフィックの退避によりトラフィックマトリックスを更新する。
【００５７】
図９を参照して、最小光パスであるＰ８を解除して、Ｐ８のトラフィックを、Ｎ１−Ｎ８−Ｎ９のパスに退避する場合について説明する。図９は光パスを解除した状態のデータテーブルを説明するための図であって、図９（Ａ）、（Ｂ）及び（Ｃ）は、それぞれ、トラフィックマトリックス、パステーブル及びインタフェーステーブルを示している。
【００５８】
Ｐ８のＮ１からＮ９に向かうトラフィックは０であるので、Ｎ１からＮ８へ向かうトラフィック、及び、Ｎ８からＮ９へ向かうトラフィックは、Ｎ１からＮ９へ向かうトラフィックが退避された後も変化しない。一方、Ｐ８のＮ９からＮ１に向かうトラフィックは１であるので、Ｎ９からＮ８へ向かうトラフィック、及び、Ｎ８からＮ１へ向かうトラフィックはそれぞれ１だけ増える。この退避の結果、Ｎ１からＮ９へ向かうトラフィック及びＮ９からＮ１へ向かうトラフィックはなくなるので、ともに０になる（図９（Ａ））。
【００５９】
トラフィックマトリックス４５８ｂの更新に伴い、パステーブル４６０ｂの更新が行われる。Ｐ８に対応するトラフィックが０になり、Ｎ１とＮ８の間の光パス、及び、Ｎ８とＮ９の間の光パスのトラフィックがそれぞれ１加算される。また、Ｐ８の解除により、Ｐ８のフラグは１になっている（図９（Ｂ））。
【００６０】
さらに、パステーブル４６０ｂの更新に伴い、インタフェーステーブル４６２ｂの更新が行われる。Ｐ８が解除光パスとなることで、Ｎ１とＮ９を終端ノードとするパスが１つ減る。そこで、インタフェーステーブルのＩＦ数もＮ１とＮ９について、１ずつ減算される（図９（Ｃ））。
【００６１】
Ｓ１６０のインタフェース数判定過程において、各ノードで用いられるインタフェース数が、使用可能インタフェース数条件を満たすか判定する。各ノードで用いられるＩＦ数が使用可能インタフェース数条件を満たした場合には、最適光パス検索処理を終了する。一方、満たさない場合は、Ｓ１２０の最小光パス選択過程を行う。例えば、図３を参照して説明したノードの場合、内部インタフェースを４つ備えているので、使用可能のインタフェース数は４とする。最適光パス検索手段４２０は、各ノードで使用されるインタフェース数が使用可能インタフェース数条件を満たすまで、すなわち、インタフェーステーブルのインタフェース数が全て４以下になるまでＳ１２０からＳ１６０までの過程を繰り返し行う。図１０を参照して、最適光パス検索過程が終了した状態のデータテーブルについて説明する。図１０（Ａ）及び（Ｂ）は、それぞれ終了状態のパステーブル及びインタフェーステーブルを示している。
【００６２】
終了状態のパステーブル４６０ｃでは、解除光パスのフラグが１であり、非解除光パスのフラグが２である。最適光パス検索処理が終了した時点で、最小光パスとして選択されなかった光パスは初期光パスとして、フラグが０のまま残っている（図１０（Ａ））。
【００６３】
終了状態のインタフェーステーブル４６２ｃでは、全てのノードに対して、ＩＦ数が使用可能インタフェース数である４以下になっている（図１０（Ｂ））。
【００６４】
上述したように、この発明の最適光パス検索装置及び最適光パス検索方法によれば、仮想的に全てのノードの組み合わせに対して初期光パスを設定し、パケットの到達性を保ちながらトラフィックの少ない順に初期光パスを解除していくので、効率的に最適光パス配置を得ることができる。
【００６５】
Ｓ４０の終了条件判定過程において、終了条件判定手段４１５は、記憶部４５０に予め記録されている終了条件４５６を読み出して、最適光パス検索過程を実施した結果得られた光パス配置が終了条件４５６を満たしているか判定する。終了条件判定手段４１５は、得られた光パス配置に対してＳ２０の過程と同様の処理により、目的関数値を算出して、規定値との比較を行う。目的関数値が規定値以下である場合は、終了条件４５６を満たしていると判定し、Ｓ５０の光パス配置変更過程を行う。また、目的関数値が規定値以下になっていない場合は、光パス配置変更過程を行わずに処理を終了する。ここで、終了条件は、ネットワークの構成などに応じて、任意好適に設定可能であり、目的関数値が規定値以下になっていない場合であっても、現用光パス配置での目的関数値以下になっている場合は、終了条件を満たしていると判定する設定にしても良い。
【００６６】
Ｓ５０の光パス配置変更過程において、光パス配置変更手段４４０は、現用光パス配置と最適光パス配置の比較を行う。この比較は、記憶部４５０から現用パステーブル４５２と終了状態のパステーブル４６０を読み出してきて、行われる。ここで、現用光パス配置では設定されていて、最適光パス配置でも設定される光パスを、使用光パス、現用光パス配置では設定されていないが、最適光パス配置で設定される光パスを、設定光パス、及び、現用光パス配置では設定されていて、最適光パス配置では設定されない光パスを、非設定光パスとそれぞれ称する。
【００６７】
光パス配置変更過程では、内部ネットワークの光パス配置を現用光パス配置から最適光パス配置へと移行する。この移行は、管理装置２７０から、送信部２７１を介して、各ノード設定信号を送ることで行われる。光パス配置変更過程において、使用光パスはそのまま維持される。また、非設定光パスは現用光パス配置から解除されて、解除の結果得られたネットワーク資源を用いて設定光パスが内部ネットワークに設定される。非設定光パスを現用光パス配置から解除して、設定光パスの設定を行う方法は、任意好適な方法を用いることができ、例えば、以下のように行われる。
【００６８】
先ず、不要光パス選択手段４４３は、非設定パスの中でトラフィックが最小のものを不要パスとして選択する。
【００６９】
次に、連結性判定手段４４５は、不要光パスを解除したときに、連結性が保たれるか判定する。連結性が保たれている場合は、不要光パス解除手段４４１は、設定信号を各ノードに送信して終端部３３１及び光スイッチ部３３３の設定を切り換えることで、不要光パスを内部ネットワークから解除する。連結性が保たれない場合には、不要光パス選択手段４４３は、次にトラフィックが少ないものを不要光パスとして選択して、再び、連結性判定手段４４５により、連結性が保たれるか否かの確認が行われる。
【００７０】
次に、必要光パス設定手段４４７は、不要光パスを内部ネットワークから解除することにより、利用可能となったネットワーク資源を用いて、内部ネットワークに対して設定光パスの設定を行う。ここでは、設定光パスの中でトラフィックの最大のものを必要光パスとして選択する。この選択された必要光パスが設定できない場合には、設定光パスの中で次にトラフィックが多いものを必要光パスとして選択して、設定を行う。
【００７１】
このように、連結性を保ちながら、非設定光パスの中でトラフィックの小さいものから順に解除し、解除の結果得られたネットワーク資源を用いて、設定光パスの中でトラフィックの大きいものから順に設定を行うと、パケットの到達性を確保しながら、ネットワーク全体について現用光パス配置から最適光パス配置へと移行することができる。また、トラフィックの多い必要パスを優先して設定し、トラフィックの少ない不要パスの解除を先に行うので、パス配置の移行の際にパケットの損失を引き起こす可能性をさらに低減できる。
【図面の簡単な説明】
【００７２】
【図１】内部ネットワークの概略構成図である。
【図２】制御ネットワークの概略構成図である。
【図３】ノードの概略構成図である。
【図４】管理装置の概略構成図である。
【図５】管理装置での処理フローを示す図である。
【図６】最適光パス検索フローを示す図である。
【図７】初期化過程において設定された初期光パスを示す図である。
【図８】初期状態のデータテーブルを示す図である。
【図９】光パスを解除した状態のデータテーブルを示す図である。
【図１０】終了状態のデータテーブルを示す図である。
【符号の説明】
【００７３】
２５０    制御回線
２５１    設定回線
２５３    測定回線
２７０    管理装置
２７１    送信部
２７３    受信部
２７７    入出力部
２８０    ＭＰＵ
２８１    ＲＯＭ
２８３    ＲＡＭ
３０１ａ、３０１ｂ、３０１ｃ、３０１ｄ    入力光ファイバ
３０６ａ、３０６ｂ、３０６ｃ、３０６ｄ    出力光ファイバ
３２１ａ、３２１ｂ、３２１ｃ、３２１ｄ    分波器
３２６ａ、３２６ｂ、３２６ｃ、３２６ｄ    合波器
３３０    光路切換部
３３１    終端部
３３３    光スイッチ部
３３５    制御装置
３５０    ルータ
３５１ａ、３５１ｂ、３５１ｃ、３５１ｄ    内部インタフェース
３５３ａ、３５３ｂ、３５３ｃ、３５３ｄ    変換装置
３５７    トラフィック計測装置
３６０    外部ネットワーク
４００    ＣＰＵ
４０３    制御手段
４１１    トラフィック監視手段
４１３    目的関数値判定手段
４１５    終了条件判定手段
４２０    最適光パス検索手段
４２１    初期化手段
４２３    最小光パス選択手段
４２５    連結性判定手段
４２７    光パス変更手段
４２９    ＩＦ数判定手段
４３１    乱数生成手段
４４０    光パス配置変更手段
４４１    不要光パス解除手段
４４３    不要光パス選択手段
４４５    連結性判定手段
４４７    必要光パス設定手段
４５０    記憶部
４５２    現用パステーブル
４５４    目的関数
４５６    終了条件
４５８    トラフィックマトリックス
４６０    パステーブル
４６２    インタフェーステーブル
【図１】
2006270460.tif 000003
【図２】
2006270460.tif 000004
【図３】
2006270460.tif 000005
【図４】
2006270460.tif 000006
【図５】
2006270460.tif 000007
【図６】
2006270460.tif 000008
【図７】
2006270460.tif 000009
【図８】
2006270460.tif 000010
【図９】
2006270460.tif 000011
【図１０】
2006270460.tif 000012