(57)【要約】【課題】ネットワーク上に構築された論理トポロジをトラヒックに応じて変更する際に、最適な光パス構造を、遺伝的アルゴリズムを用いて検索する。【解決手段】まず、論理トポロジ上のノード配置を示す複数の遺伝子コードを生成し、各遺伝子コードが示す論理トポロジのトラヒックをそれぞれ評価し、評価の結果が小さいものほど高くなるような被選択確率をそれぞれの遺伝子コードに割り当てて当該被選択確率に応じた選択を所定回数繰り返すことにより所定個の遺伝子コードを選択し、選択された遺伝子コードから任意の遺伝子コード・ペアを生成してランダムに選択された遺伝子要素を当該遺伝子コード・ペア間で交叉させ、各遺伝子コードに含まれる遺伝子要素の一部または全部を所定の確率で突然変異させる。【選択図】図７
2006270677.tif 000002
【特許請求の範囲】
【請求項１】
論理トポロジ上のノード配置を示す複数の遺伝子コードを用いてトラヒックの小さいパス配置を検索する最適パス配置検索装置であって、
それぞれの前記遺伝子コードが示す前記論理トポロジのトラヒックを評価する評価手段と、
前記評価の結果が小さいものほど高くなるような被選択確率をそれぞれの前記遺伝子コードに割り当てて、当該被選択確率に応じた選択を所定回数繰り返すことにより、所定個の当該遺伝子コードを選択する選択手段と、
前記遺伝子コードから任意の遺伝子コード・ペアを生成し、ランダムに選択された遺伝子要素を当該遺伝子コード・ペア間で交換する交叉手段と、
前記遺伝子コードに含まれる前記遺伝子要素の一部または全部を所定の確率で変更する突然変異手段と、
を備えることを特徴とする最適パス配置検索装置。
【請求項２】
最初の前記遺伝子コードが、乱数生成手段によって生成されることを特徴とする請求項１に記載の最適パス配置検索装置。
【請求項３】
前記評価手段が、前記遺伝子コードが示す前記論理トポロジの中継トラヒックを前記論理トポロジのノード毎に算出し、最も大きい当該中継トラヒックを当該遺伝子コードの評価結果とすることを特徴とする請求項１または２に記載の最適パス配置検索装置。
【請求項４】
前記評価手段が、前記遺伝子コードが示す前記論理トポロジの中継トラヒックおよび１搬送波当たりのトラヒックを前記論理トポロジのノード毎に算出し、最も大きい当該中継トラヒックおよび当該１搬送波当たりのトラヒックをそれぞれ選択し、当該最も大きい中継トラヒックおよび１搬送波当たりのトラヒックが両方とも当該遺伝子コードよりも小さい前記遺伝子コードの個数を計数し、当該個数に‘１’を加えた値を評価結果とすることを特徴とする請求項１または２に記載の最適パス配置検索装置。
【請求項５】
前記選択手段が、前記評価の結果に逆比例する被選択確率をそれぞれの前記遺伝子コードに割り当てた後、既に選択された前記遺伝子コードを選択対象から取り除くことなく、当該被選択確率に応じた選択を所定回数繰り返すことを特徴とする請求項１〜４のいずれかに記載の最適パス配置検索装置。
【請求項６】
前記交叉手段が、前記遺伝子コードの前記遺伝子要素と同値の要素をランダムに配列してなる順序リストを生成し、当該順序リストに対応させてそれぞれの前記遺伝子コードにおける当該遺伝子要素の配列順を並べ換えることによって複数の予備コードを生成し、当該複数の予備コードを２個ずつに分けることによって複数の予備コード・ペアを生成し、交換を行う当該遺伝子要素を当該予備コード・ペア毎にランダムに決定し、当該決定に基づいて当該予備コード・ペア間で当該遺伝子要素の交換を行った後、前記順序リストに対応させて前記遺伝子要素の配列順を復元することを特徴とする請求項１〜５のいずれかに記載の最適パス配置検索装置。
【請求項７】
前記突然変異手段が、前記遺伝子コード毎に発生させた乱数を所定の閾値と比較することにより当該遺伝子コードにおける突然変異の発生／非発生を決定し、突然変異を発生させる当該遺伝子コード毎に２個の乱数ｈ，ｋ（１≦ｈ，ｋ≦ｎ；ｎは当該遺伝子コードに含まれる前記遺伝子要素の個数）を発生させ、当該遺伝子コードに含まれるｈ番目からｋ番目までの前記遺伝子要素の配列順を逆にすることを特徴とする請求項１〜６のいずれかに記載の最適パス配置検索装置。
【請求項８】
前記評価手段が、ｍ個の前記遺伝子コードについて評価を行い、
前記選択手段が、当該評価の結果が最も小さい当該遺伝子コードを除くｍ−１個の当該遺伝子コードからｍ個の遺伝子コードを選択し、
前記突然変異手段が、突然変異を発生させなかった前記遺伝子コードのいずれかを、前記評価の結果が最も小さい遺伝子コードと入れ換える、
ことを特徴とする請求項１〜７のいずれかに記載の最適パス配置検索装置。
【請求項９】
前記論理トポロジがトーラス構造を有することを特徴とする請求項１〜８に記載の最適パス配置検索装置。
【請求項１０】
前記論理トポロジがリング構造を有することを特徴とする請求項１〜８に記載の最適パス配置検索装置。
【請求項１１】
論理トポロジ上のノード配置を示す複数の遺伝子コードを用いてトラヒックの小さいパス配置を検索する最適パス配置検索方法であって、
前記遺伝子コードが示す前記論理トポロジのトラヒックを評価する評価ステップと、
当該評価ステップにおける評価の結果が小さいものほど高くなるような被選択確率をそれぞれの前記遺伝子コードに割り当てて、当該被選択確率に応じた選択を所定回数繰り返すことにより、所定個の当該遺伝子コードを選択する選択ステップと、
当該選択ステップで選択された前記遺伝子コードから任意の遺伝子コード・ペアを生成し、ランダムに選択された遺伝子要素を当該遺伝子コード・ペア間で交換する交叉ステップと、
当該交叉ステップで交叉された前記遺伝子コードに含まれる前記遺伝子要素の一部または全部を所定の確率で変更する突然変異ステップと、
を備えることを特徴とする最適パス配置検索方法。
【請求項１２】
乱数を発生させることによって最初の前記遺伝子コードを生成する遺伝子コード生成ステップをさらに備えることを特徴とする請求項１１に記載の最適パス配置検索方法。
【請求項１３】
前記評価ステップが、前記遺伝子コードが示す前記論理トポロジの中継トラヒックを前記論理トポロジのノード毎に算出し、最も大きい当該中継トラヒックを当該遺伝子コードの評価結果とするステップであることを特徴とする請求項１１または１２に記載の最適パス配置検索方法。
【請求項１４】
前記評価ステップが、前記遺伝子コードが示す前記論理トポロジの中継トラヒックおよび１搬送波当たりのトラヒックを前記論理トポロジのノード毎に算出し、最も大きい当該中継トラヒックおよび当該１搬送波当たりのトラヒックをそれぞれ選択し、当該最も大きい中継トラヒックおよび１搬送波当たりのトラヒックが両方とも当該遺伝子コードよりも小さい前記遺伝子コードの個数を計数し、当該個数に‘１’を加えた値を評価結果とするステップであることを特徴とする請求項１１または１２に記載の最適パス配置検索方法。
【請求項１５】
前記選択ステップが、前記評価の結果に逆比例する被選択確率をそれぞれの前記遺伝子コードに割り当てた後、既に選択された前記遺伝子コードを選択対象から取り除くことなく、当該被選択確率に応じた選択を所定回数繰り返すステップであることを特徴とする請求項１１〜１４のいずれかに記載の最適パス配置検索方法。
【請求項１６】
前記交叉ステップが、前記遺伝子コードの前記遺伝子要素と同値の要素をランダムに配列してなる順序リストを生成し、当該順序リストに対応させてそれぞれの前記遺伝子コードにおける当該遺伝子要素の配列順を並べ換えることによって複数の予備コードを生成し、当該複数の予備コードを２個ずつに分けることによって複数の予備コード・ペアを生成し、交換を行う当該遺伝子要素を当該予備コード・ペア毎にランダムに決定し、当該決定に基づいて当該予備コード・ペア間で当該遺伝子要素の交換を行った後、前記順序リストに対応させて前記遺伝子要素の配列順を復元するステップであることを特徴とする請求項１１〜１５のいずれかに記載の最適パス配置検索方法。
【請求項１７】
前記突然変異ステップが、前記遺伝子コード毎に発生させた乱数を所定の閾値と比較することにより当該遺伝子コードにおける突然変異の発生／非発生を決定し、突然変異を発生させる当該遺伝子コード毎に２個の乱数ｈ，ｋ（１≦ｈ，ｋ≦ｎ；ｎは当該遺伝子コードに含まれる前記遺伝子要素の個数）を発生させ、当該遺伝子コードに含まれるｈ番目からｋ番目までの前記遺伝子要素の配列順を逆にするステップであることを特徴とする請求項１１〜１６のいずれかに記載の最適パス配置検索方法。
【請求項１８】
前記評価ステップが、ｍ個の前記遺伝子コードについて評価を行うステップであり、
前記選択ステップが、当該評価の結果が最も小さい当該遺伝子コードを除くｍ−１個の当該遺伝子コードからｍ個の遺伝子コードを選択するステップであり、
前記突然変異ステップが、突然変異を発生させなかった前記遺伝子コードのいずれかを、前記評価の結果が最も小さい遺伝子コードと入れ換える処理を含むステップである、
ことを特徴とする請求項１１〜１７のいずれかに記載の最適パス配置検索方法。
【請求項１９】
前記論理トポロジがトーラス構造を有することを特徴とする請求項１１〜１８に記載の最適パス配置検索方法。
【請求項２０】
前記論理トポロジがリング構造を有することを特徴とする請求項１１〜１８に記載の最適パス配置検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、通信トラヒックに基づいて、論理トポロジを構成するパスの最適配置を検索する技術に関する。この発明は、例えば、ＷＤＭ(Wavelength Division Multiplex) 技術を用いて構築された論理トポロジを動的に変更する機能を有する光通信ネットワークで使用される。
【背景技術】
【０００２】
近年、インターネット等の通信ネットワークでは、利用者の急増等に伴うトラヒックの増大が問題になっている。この問題に対処する技術として、ＷＤＭが注目されている。ＷＤＭとは、光波長が異なる搬送波を多重化する技術である。ＷＤＭを用いることにより、１本の光伝送路に複数の搬送波を並列的に伝搬させることができるので、大容量の通信ネットワークを低コストで構築することができる。
【０００３】
ＷＤＭを用いた光通信ネットワークでは、各ノードとして、例えば、光分岐挿入機能(Optical Add Drop Multiplexer;OADM) や光クロスコネクト機能(Optical Cross Connect;OXC) 等を備えるものが使用される。光分岐挿入機能とは、ＷＤＭを用いて多重化された光搬送波に他の波長の光搬送波を挿入したり、当該多重光搬送波から特定波長の光搬送波を分岐させたりする機能である。また、光クロスコネクト機能とは、ＷＤＭを用いて多重化された光搬送波の通信パスを、波長単位で切り替える機能である。これらの機能を用いることにより、光伝送路上に構築された光通信ネットワーク（すなわち物理トポロジ）上に、複数の光パスからなる論理トポロジを構築することが可能になる。
【０００４】
さらに、ＷＤＭを用いた光通信ネットワークとして、論理トポロジを動的に変更する機能を備えるものが知られている。ネットワークでは、一部のノードやパスで、輻輳や障害が発生する場合がある。このような場合には、論理トポロジを動的に変更することにより、通信パケットに、輻輳が発生したノードをカットスルーさせることや、障害発生区間を迂回させることが可能になる。
【０００５】
ここで、カットスルーとは、当該ノードのルーティング機能を使用せずに、光分岐挿入機能或いは光クロスコネクト機能のみを用いて、通信パケットをそのまま通過させることである（下記特許文献１の段落０００２〜０００５および図６参照）。輻輳が発生したノードにカットスルーパスを設定することにより、当該ノードの処理負荷を軽減することができる。
【０００６】
光パスを動的に変更して障害区間を迂回する方法としては、専有プロテクション法や共有プロテクション法が知られている。専有プロテクション法とは、１本の光パスを、他の１本の光パスで代用する方法である。また、共有プロテクション法とは、複数本の光パスを、他の１本の光パスで代用する方法である。
【特許文献１】特開２００２−３７４２９１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
上述のように、特定のノードにトラヒックが集中した場合、当該ノードをカットスルーする光パスを新たに設定することによって、当該ノードの処理負荷を軽減することができる。しかし、以下のような理由により、このようなパス設定が他のノードの処理負荷を増大させてしまう場合がある。
【０００８】
光パスが新たに設定が変更される場合、当該光通信ネットワークでは、ＩＰ(Internet protocol) レイヤのルーティング情報が変更される。したがって、新たにカットスルーパスを設定した場合に、そのカットスルーパスが最適経路であると判断される場合が多いと、当該カットスルーパスにトラヒックが集中する場合がある。このような場合、カットスルーされるノードの処理負荷が過大になることは少ないが、当該カットスルーパスの終端をなすノードでは処理負荷が増大する。
【０００９】
このような理由から、カットスルーパスを新たに設定する際には、ＩＰレイヤでの経路変更も考慮した上で、光通信ネットワーク全体でトラヒックの集中が発生しないようにすることが望まれる。しかしながら、特定の２個のノードを終端とするカットスルーパスの設定パターン数は、その光通信ネットワークで使用される波長数やノード数の増加に応じて、指数関数的に増加する。このため、すべての設定パターンについて光通信ネットワーク全体でのトラヒック発生状況を予想して最適なカットスルーパスを選択しようとすると、処理負担が膨大となり、現実的でない。
【００１０】
この発明の課題は、最適な光パス構造を簡単な処理で検索することができる最適パス配置検索装置を提供することにある。
【課題を解決するための手段】
【００１１】
（１）第１の発明は、論理トポロジ上のノード配置を示す複数の遺伝子コードを用いてトラヒックの小さいパス配置を検索する最適パス配置検索装置に関する。
【００１２】
そして、それぞれの遺伝子コードが示す論理トポロジのトラヒックを評価する評価手段と、評価の結果が小さいものほど高くなるような被選択確率をそれぞれの遺伝子コードに割り当てて被選択確率に応じた選択を所定回数繰り返すことにより所定個の遺伝子コードを選択する選択手段と、遺伝子コードから任意の遺伝子コード・ペアを生成してランダムに選択された遺伝子要素を遺伝子コード・ペア間で交換する交叉手段と、遺伝子コードに含まれる遺伝子要素の一部または全部を所定の確率で変更する突然変異手段とを備える。
【００１３】
（２）第２の発明は、論理トポロジ上のノード配置を示す複数の遺伝子コードを用いてトラヒックの小さいパス配置を検索する最適パス配置検索方法に関する。
【００１４】
そして、それぞれの遺伝子コードが示す論理トポロジのトラヒックを評価する評価ステップと、評価ステップにおける評価の結果が小さいものほど高くなるような被選択確率をそれぞれの遺伝子コードに割り当てて被選択確率に応じた選択を所定回数繰り返すことにより所定個の遺伝子コードを選択する選択ステップと、選択ステップで選択された遺伝子コードから任意の遺伝子コード・ペアを生成してランダムに選択された遺伝子要素を遺伝子コード・ペア間で交換する交叉ステップと、交叉ステップで交叉された遺伝子コードに含まれる遺伝子要素の一部または全部を所定の確率で変更する突然変異ステップとを備える。
【発明の効果】
【００１５】
本発明によれば、トラヒックの小さいパス構造の検索に遺伝的アルゴリズムを適用することができるので、最適なパス構造或いはそれに近いパス構造を、簡単な処理で検索することができる。
【発明を実施するための最良の形態】
【００１６】
以下、この発明の実施の形態について、図面を用いて説明する。なお、図中、各構成成分の大きさ、形状および配置関係は、この発明が理解できる程度に概略的に示してあるにすぎず、また、以下に説明する数値的条件は単なる例示にすぎない。
【００１７】
第１の実施の形態
以下、この発明の第１の実施形態について、図１〜１１を用いて説明する。
【００１８】
図１は、この実施形態に係るＩＰ基幹ネットワークのデータプレーン構成を示す概念図である。図１に示したように、ＩＰ基幹ネットワーク１００のデータプレーンは、ノードＮ１〜Ｎ９と、光ファイバＦ１〜Ｆ２４とを備えている。
【００１９】
ノードＮ１〜Ｎ９は、それぞれ、図示しないＩＰルータと光コアノードとを備えている（後述）。
【００２０】
光ファイバＦ１〜Ｆ２４は、それぞれ、物理的に隣接するノードどうしを通信接続する。各光ファイバＦ１〜Ｆ２４には、識別のためのファイバＩＤとして‘１’〜‘２４’が付されている。
【００２１】
このような構成により、ＩＰ基幹ネットワーク１００上に、光コアノードを中継ノードとし且つ光波長を識別子とした光パス(Lambda Switch Capable-Label Switched Path;LSC-LSP) を構築することができる（後述）。
【００２２】
図２は、ＩＰ基幹ネットワーク１００の制御プレーン構成を示す概念図である。図２に示したように、ＩＰ基幹ネットワーク１００の制御プレーンは、トラヒック計測管理装置２１０と、最適光パス配置検索装置２２０と、光パス設定管理装置２３０と、制御ネットワーク２４０，２５０とを備えている。
【００２３】
トラヒック計測管理装置２１０は、各ノードＮ１〜Ｎ９のトラヒック計測装置３６１，３６２（後述の図３参照）で計測されたトラヒック情報（流入パケットのトラヒック、流出パケットのトラヒック等）を、制御ネットワーク２４０を介して受信して、集計・管理する。
【００２４】
最適光パス配置検索装置２２０は、トラヒック計測管理装置２１０から受け取ったトラヒック情報を用い、遺伝的アルゴリズムに基づいて最適な光パス配置を計算する（後述）。
【００２５】
光パス設定管理装置２３０は、最適光パス配置検索装置２２０の計算結果に基づき、制御ネットワーク２５０を介して各ノードＮ１〜Ｎ９のＩＰルータ３５１および光スイッチ制御装置３７１（後述の図３参照）を制御することにより、最適な光パスをデータプレーン（図１参照）に設定する。
【００２６】
図３は、ノードＮ１の内部構成を示すブロック図である。図３は、四種類の搬送波（波長λ１〜λ４）をＷＤＭ多重化して光パス中を伝搬させる場合の例である。図３に示したように、ノードＮ１は、光増幅器３１１〜３１４、光合分波器３２１〜３２４、光スイッチ３３１，３３２、光送受信機３４１〜３４４、ＩＰルータ３５１、トラヒック計測装置３６１，３６２および光スイッチ制御装置３７１を備えている。
【００２７】
光増幅器３１１〜３１４は、ＷＤＭ多重化された光搬送波を増幅する。光増幅器３１１〜３１４としては、例えばＥＤＦＡ(Erbium Doped Fiber Amplifier)が使用される。
【００２８】
光合分波器３２１，３２２は、ＷＤＭ多重化された光搬送波を入力して、波長λ１〜λ４の搬送波に分離する。一方、光合分波器３２３，３２４は、波長λ１〜λ４の光搬送波を入力して、合波（すなわちＷＤＭ多重化）する。光合分波器３２１〜３２４としては、例えばＡＷＧ(Arrayed Waveguide Grating)波長合分波器が使用される。
【００２９】
光スイッチ３３１，３３２は、光合分波器３２１〜３２４および光送受信機３４１〜３４４間で、光波長λ１〜λ４ごとに、光搬送波経路を設定する。例えば、光合分波器３２１のλ１端子から出力された光搬送波は、光スイッチ３３１，３３２により、光合分波器３２３のλ１端子、光合分波器３２４のλ１端子または光送受信機３４１のいずれかに送られる。同様に、光合分波器３２２のλ１端子から出力された光搬送波も、光合分波器３２３，３２４のλ１端子または光送受信機３４１のいずれかに送られる。一方、光送受信機３４１から出力された光搬送波は、光合分波器３２３，３２４のλ１端子のいずれか一方に送られる。他の波長λ２〜λ４の光搬送波も、波長λ１の搬送波と同様であり、光合分波器３２１，３２２から光合分波器３２３，３２４或いは光送受信機３４２〜３４４への経路や、光送受信機３４２〜３４４から光合分波器３２３，３２４への経路が設定される。
【００３０】
光送受信機３４１〜３４４は、光スイッチ３３１，３３２とＩＰルータ３５１との間で送受信される光搬送波の波長変換を行う。すなわち、光送受信機３４１は、光スイッチ３３１，３３２から入力した光搬送波の波長λ１を、ＩＰルータ３５１で使用される波長λ０に変換し、且つ、ＩＰルータ３５１から入力した光搬送波の波長λ０を、λ１に変換する。同様に、光送受信機３４２は波長λ２・λ０間、光送受信機３４３は波長λ３・λ０間、光送受信機３４４は波長λ４・λ０間の、双方向の波長変換を行う。なお、ＩＰルータ３５１が電気信号を用いてルーティング等を行う場合には、光送受信機３４１〜３４４として光電変換装置を使用すればよい。
【００３１】
ＩＰルータ３５１は、光送受信機３４１〜３４４を介して光スイッチ３３１，３３２に通信接続されるとともに、トラヒック計測装置３６１，３６２を介して外部ネットワーク３８１，３８２に通信接続される。上述のように、ＩＰルータ３５１と光送受信機３４１〜３４４との通信は、例えば、波長λ０の光搬送波を用いて行われる。一方、ＩＰルータ３５１と外部ネットワーク３８１，３８２との通信は、波長λ０の光搬送波を使用してもよいし、波長λ１〜λ４或いは他の波長の光搬送波を使用してもよいし、電気信号を使用してもよい。波長λ０以外の光搬送波或いは電気信号が使用される場合には、ＩＰルータ３５１内に波長変換機能或いは光電変換機能が設けられる。ＩＰルータ３５１は、受信した光搬送波等からＩＰパケットを読み出し、当該ＩＰパケットに対して、ＩＰレイヤのルーティングを行う。すなわち、ＩＰルータ３５１は、光送受信機３４１〜３４４や外部ネットワーク３８１，３８２から受信したＩＰパケットの宛先アドレスを読み出し、ルーティング表に基づいて当該宛先アドレスに対応するＩＰパスを検索して、当該ＩＰパスに対応する光送受信機３４１〜３４４或いは外部ネットワーク３８１，３８２に当該ＩＰパケットを送出する。また、ＩＰルータ３５１は、制御ネットワーク２５０を介して光パス設定管理装置２３０（図２参照）から受信した制御信号に基づいて、内部のルーティング表（図示せず）を書き換える。
【００３２】
トラヒック計測装置３６１，３６２は、ＩＰルータ３５１と外部ネットワーク３８１，３８２との間で送受信されるＩＰパケットのトラヒックを計測する。計測結果は、制御ネットワーク２４０を介して、トラヒック計測管理装置２１０に送られる。
【００３３】
光スイッチ制御装置３７１は、制御ネットワーク２５０を介して光パス設定管理装置２３０から受信した制御信号に基づき、光スイッチ３３１，３３２内に設けられる光搬送波経路の設定・変更を行う。
【００３４】
他のノードＮ２〜Ｎ２４の内部構成は、ノードＮ１の内部構成と同様であるので、説明を省略する。
【００３５】
図４は、最適光パス配置検索装置２２０（図２参照）の内部構成を示すブロック図である。図４に示したように、最適光パス配置検索装置２２０は、受信処理部４１０と、遺伝子コートテーブル４２０と、目的関数テーブル４３０と、乱数生成部４４０と、パス検索部４５０と、物理パス割当処理部４６０と、送信処理部４７０と、バス４８０とを備えている。
【００３６】
受信処理部４１０は、トラヒック計測管理装置２１０（図２参照）からトラヒック情報を受信し、目的関数テーブル４３０に送る。
【００３７】
遺伝子コードテーブル４２０は、遺伝的アルゴリズムを用いてパス検索を行うための遺伝子コード等を格納する。
【００３８】
目的関数テーブル４３０は、候補となる光パストポロジを評価するための目的関数を保存する。この実施形態では、目的関数として、上述のトラヒック情報等が、目的関数テーブル４３０に格納される。
【００３９】
乱数生成部４４０は、パス検索部４５０等の制御に基づき、所定の条件下で乱数を生成する。
【００４０】
パス検索部４５０は、上述のトラヒック情報、遺伝子コードテーブル、目的関数および乱数等を用いて、最適な光パストポロジを検索する。
【００４１】
物理パス割当処理部４６０は、パス検索部４５０の検索によって得られた最適な光パストポロジを、ＩＰ基幹ネットワーク１００に実際に反映させるための、物理パスの割り当てを行う。
【００４２】
送信処理部４７０は、物理パス割当処理部４６０が行った割り当て処理処理の結果を、光パス設定管理装置２３０（図２参照）に送る。
【００４３】
バス４８０は、各構成部４１０〜４７０を相互に接続する。
【００４４】
次に、図１〜図４に示したＩＰ基幹ネットワーク１００の動作を説明する。
【００４５】
最初に、ノードＮ１〜Ｎ９の動作について、ノードＮ１を例に採って説明する。ここでは、光ファイバＦ１を介してノードＮ２からノードＮ１への光パスが設定され且つ光ファイバＦ６を介してノードＮ４からノードＮ１への光パスが設定されている場合について説明する。
【００４６】
上述のように、光ファイバＦ１内には、四種類の搬送波（波長λ１〜λ４）がＷＤＭ多重化されて伝搬される。これにより、ノードＮ２からノードＮ１へ、ＩＰパケットが転送される。このＷＤＭ多重化光は、光増幅器３１１で増幅された後、光合分波器３２１で多重分離されて、光スイッチ３３１に送られる。ノードＮ２，Ｎ１間に例えば波長λ１の光パスが設定されている場合、光スイッチ３３１に入力された光搬送波（波長λ１）は、光送受信機３４１に送られる。上述のように、光送受信機３４１は、この光搬送波の波長をλ０に変換して、ＩＰルータ３５１に送る。ＩＰルータ３５１は、この光搬送波からＩＰパケットを読み出し、さらに、当該ＩＰパケットから宛先アドレスを読み出す。そして、ＩＰルータ３５１は、内部のルーティング表（図示せず）を用いて、当該宛先アドレスに対応する最適な光パスを検索する。
【００４７】
検索された光パスが光ファイバＦ６を用いた光パス（波長λ１〜λ４の光搬送波のいずれか）である場合、ＩＰルータ３５１は、光送受信機３４１〜３４４のいずれか対応するものに、当該ＩＰパケットに係る光搬送波を出力する。光送受信機３４１〜３４４は、当該光搬送波の波長λ０を、対応する波長（λ１〜λ４のいずれか）に変換して出力する。返還後の光搬送波は、スイッチ３３１を介して、光合分波器３２３に送られ、ＷＤＭ多重化される。多重化後の光搬送波は、光増幅器３１３で増幅された後、光ファイバＦ６を介して、ノードＮ４に転送される。
【００４８】
また、ＩＰパケットの宛先アドレスがＩＰ基幹ネットワーク１００以外のアドレスであった場合、最適な光パスは外部ネットワーク３８１，３８２のいずれかになる。この場合、ＩＰルータ３５１は、当該ＩＰパケットに係る光搬送波を、対応する外部ネットワークに送信する。
【００４９】
一方、外部ネットワーク３８１，３８２からＩＰ基幹ネットワーク１００にＩＰパケットが転送された場合も、ＩＰルータ３５１は、当該ＩＰパケットの宛先アドレスから、最適な光パスを検索する。そして、ＩＰルータ３５１は、最適な光パスに対応する光送受信機３４１〜３４４に、当該ＩＰパケットに係る光搬送波を出力する。さらに、当該光搬送波が、当該光送受信機で波長変換され、スイッチ３３１，３３２を介して光合分波器３２３，３２４のいずれか対応する方に送られ、ＷＤＭ多重化および光増幅された後、対応する光ファイバに出力される。
【００５０】
ＩＰルータ３５１と外部ネットワーク３８１，３８２との間のトラヒックは、トラヒック計測装置３６１，３６２によって測定される。この計測結果は、制御ネットワーク２４０を介して、トラヒック計測管理装置２１０に送られる。
【００５１】
次に、ノードＮ１を中継点として、ノードＮ２からノードＮ４へのカットスルーパスが設定されている場合について説明する。
【００５２】
上述の場合と同様、光ファイバＦ１を介してノードＮ２から受信された光搬送波は、光増幅器３１１で増幅され、光合分波器３２１で多重分離された後、光スイッチ３３１に入力される。ノードＮ１に当該波長のカットスルーパスの中継点が設定されている場合、光スイッチ３３１は、入力した光搬送波を、光送受信機３４１〜３４４に送ることなく、そのまま光合分波器３２３に送る。したがって、ノードＮ２から送信された光搬送波は、ＩＰルーティング処理を施されることなく、そのままノードＮ１を通過して、ノードＮ４に送られる。すなわち、このようなカットスルーパスが設定されている場合には、物理トポロジではノードＮ２，Ｎ１間およびノードＮ１，Ｎ４間にパスが設定されているが、論理トポロジではノードＮ２，Ｎ４間のパスが設定されているにすぎないことになる。
【００５３】
図５は、この実施形態に係る論理トポロジを示す概念図である。図５に示したように、カットスルーパスを用いることにより、非隣接の論理配置Ｌ１〜Ｌ９間を通信接続する論理パスを設定することができ、したがって図１に示したようなデータプレーン構成のネットワーク上に、図５に示したような論理トポロジを構築することができる。図５に示したような、同一行および同一列の両端論理配置どうしが論理パスで接続された構造を、トーラス構造と称する。一般に、トーラス構造の論理トポロジは、負荷分散効果が高いとされている。
【００５４】
通常の光パスやカットスルーパスを適当に設定することにより、このトーラス構造の各論理配置Ｌ１〜Ｌ９の位置に、任意のノードを配置することができる。図６は、その一例を示す概念図である。そして、光パスやカットスルーパスの設定を適当に変更することにより、各論理配置Ｌ１〜Ｌ９に配されるノードを、任意に変更することができる。すなわち、光パスやカットスルーパスの設定変更による論理トポロジの変更は、トーラス構造内におけるノードの再配置と同一視することができる。
【００５５】
トーラス構造を保ったままカットスルーパスを変更することによって、ＩＰルータの中継トラヒック量を低減させることが可能である。すなわち、トーラス構造のネットワーク内でノードを適当に再配置することにより、効果的な負荷分散が達成できる。この実施形態では、このようなノード再配置を、遺伝的アルゴリズムを用いて実現する。
【００５６】
以下、この実施形態に係るＩＰ基幹ネットワーク１００のノード再配置動作について説明する。
【００５７】
上述のように、各ノードＮ１〜Ｎ９では、トラヒック計測装置３６１，３６２（図３参照）により、トラヒック量が計測される。この計測結果は、制御ネットワーク２４０を介して、トラヒック計測管理装置２１０（図２参照）に送られる。トラヒック計測管理装置２１０は、各ノードＮ１〜Ｎ９のトラヒック分布をマトリクス化して、最適光パス配置検索装置２２０に送る。
【００５８】
最適光パス配置検索装置２２０は、このトラヒックマトリクスを、受信処理部４１０（図４参照）で受信する。そして、最適光パス配置検索装置２２０は、遺伝的アルゴリズムを用いて、最適な光パス配置を検索する。ここで、遺伝的アルゴリズムとは、ある問題に対する最適解を求めるための演算アルゴリズムの一種であり、生物界の遺伝法則を模倣して案出されたものである。遺伝的アルゴリズムでは、遺伝法則を模倣した演算処理である「選択」、「交叉」および「突然変異」を行って固体群を進化させる操作を繰り返すことにより、所望の「評価」を得ようとする。ここで、個体群とは、個体すなわち演算解の集合である。遺伝的アルゴリズムを用いることにより、最適解或いはそれに近い解を、大域的に検索することができる。
【００５９】
以下、最適光パス配置検索装置２２０の演算動作について、図７〜図１１を用いて説明する。
【００６０】
図７は、最適光パス配置検索装置２２０の演算処理を概略的に示すフローチャートである。
【００６１】
（１）初期個体群の生成
最初に、複数の遺伝子コードからなる初期個体群が生成される（図７のステップＳ７０１参照）。遺伝子コードとは、演算解の候補となるデータである。この実施形態では、遺伝的アルゴリズムを用いて、トーラス構造の論理トポロジにおけるノードの最適な再配置を検索する。上述のように、論理トポロジの変更は、実際には光パスやカットスルーパスの設定変更によって実現されるが、最適光パス配置検索装置２２０の検索処理では各ノードの再配置に置き換えて考える（図５参照）。この実施形態のＩＰ基幹ネットワーク１００は、９個のノードＮ１〜Ｎ９を備えている（図１参照）。したがって、遺伝子コードは、９個の要素を備えることになる。
【００６２】
図８は、この実施形態で使用される遺伝子コードのデータ構造を示す表である。図８に示されたように、この実施形態で使用される遺伝子コードは、論理配置の順に列記された９個のノードＩＤを有している。ここで、論理配置とは、基準となる論理トポロジにおける各ノードの配置位置である（図５、図６参照）。また、ノードＩＤとは各ノードＮ１〜Ｎ９に付された番号であり、例えばノードＮ１のＩＤは「１」、ノードＮ２のＩＤは「２」である。なお、図８に示された遺伝子コードは、図６に示した論理トポロジのノード配置と一致する。
【００６３】
この実施形態では、初期個体群が２０個の遺伝子コードを含む場合を例に採って説明する。但し、初期個体群に含まれる遺伝子コードの数は、任意であり、演算結果に要求される信頼度等に応じて決定すればよい。また、初期個体群に含まれる各遺伝子コードの値も、任意である。この実施形態では、これらの遺伝子コードを、乱数生成部４４０（図４参照）に生成させる。生成された遺伝子コードは、バス４８０を介して、遺伝子コードテーブル４２０に送られる。遺伝子コードテーブル４２０は、２０個の遺伝子コード（すなわち２０種類のノード配置パターン）を、初期の個体群として格納する。
【００６４】
（２）遺伝子コードの評価
次に、パス検索部４５０が、遺伝子コードの評価を行う。評価とは、遺伝子コードが所定条件を満たすか否かを判定するためのパラメータを算出する処理である。以下に説明するように、この実施形態の評価処理では、最適各遺伝子コードが示す論理トポロジの中継トラヒックを評価する（図７のステップＳ７０２，Ｓ７０３参照）。
【００６５】
まず、パス検索部４５０が、これら遺伝子コードの適合度を計算する（図７のステップＳ７０２参照）。この演算処理では、まず、最初の遺伝子コードが示すノード配置パターンに対応する論理トポロジが仮想的に構築され、次に、当該論理トポロジにおける各ノード間の最短経路がそれぞれ計算される。かかる最短経路の計算は、例えば公知のダイクストラ(Dijkstra)法等を用いて行うことができる。続いて、パス検索部４５０は、このようにして得られた各最短経路を用いてノード間のＩＰパケット通信を行う場合の中継トラヒック量を、ノードごとに計算する。上述のように、中継トラヒック量は、目的関数として、目的関数テーブル４３０に格納される。パス検索部４５０は、この測定結果に基づいて、仮想的な論理トポロジにおける中継トラヒック量を演算する。そして、パス検索部４５０は、各ノードの中継トラヒック量（演算結果）のうち、最も大きいものを、適合度として選択する。他の遺伝子コードについても、同様にして、適合度が算出される。各遺伝子コードについて算出された適合度の例を、図９（Ａ）に示す。
【００６６】
続いて、パス検索部４５０は、これら２０個の遺伝子コードから、最も優秀な遺伝子コードを選択する（図７のステップＳ７０３参照）。上述のように、この実施形態では、各ノードの中継トラヒック量のうち最大のものが、適合度である。したがって、この適合度が小さいほど、トラヒックの集中が発生し難いと考えられる。このため、この実施形態では、２０個の遺伝子コードの中で最も適合度が小さいものを、最も優秀な遺伝子コードに選択する。以下、図９（Ａ）の遺伝子コードＧ２が最も優秀な遺伝子コードに選択された場合を例に採って説明する。
【００６７】
パス検索部４５０は、最も優秀な遺伝子コードを読み出して、終了条件を満たしているか否かを判定する（図７のステップＳ７０４参照）。例えば、最も優秀な遺伝子コードの適合度が閾値以下になった場合、遺伝的アルゴリズムの処理時間が予め設定された処理時間を超えた場合または遺伝子コードに対する演算処理が予め定められた世代分行われた場合に、終了条件が満たされたと判定される。ここでは、終了条件が満たされていないものとする。
【００６８】
（３）遺伝子コードの選択
次に、パス検索部４５０は、遺伝子コードの選択を行う（図７のステップＳ７０５参照）。「選択」とは、遺伝子コードの中から優秀なものを選び出す処理であり、生物界において優秀な遺伝子ほど後の世代に残り易いことに対応している。選択処理では、優秀な遺伝子コード、すなわち適合度が小さい遺伝子コードほど、選択され易くする。以下に説明するように、この実施形態では、上述の評価の結果が小さいものほど高くなるような被選択確率を各遺伝子コードに割り当て、ランダムな選択を所定回数繰り返すことによって、所定個の遺伝子コードを選択する。
【００６９】
この選択処理では、最も優秀な遺伝子コードＧ２を除く１９個の遺伝子コードＧ１，Ｇ３〜Ｇ２０を用いて、２０個の遺伝子コードを選択する。
【００７０】
まず、パス検索部４５０は、遺伝子コードＧ１，Ｇ３〜Ｇ２０に、被選択確率を割り当てる。ここで、被選択確率とは、遺伝子コードＧ１，Ｇ３〜Ｇ２０のいずれか１つを選択するときに、当該遺伝子コードが選択される確率である。各遺伝子コードの被選択確率は、優秀な遺伝子コードほど選択されやすくなるように、決定される。上述のように、この実施形態では、適合度が小さい遺伝子コードほど、優秀である。したがって、各選択確率は、適合度に逆比例するように定めることとする。例えば、遺伝子コードＧ１，Ｇ３〜Ｇ２０の各適合度についての逆数を求め、全体の和が‘１’になるようにこれらの逆数を重み付けすればよい。ここでは、各遺伝子コードＧ１，Ｇ３〜Ｇ２０の被選択確率を、ｘ１，ｘ３，ｘ４，・・・，ｘ２０（ｘ１＋ｘ３＋ｘ４＋・・・＋ｘ２０＝１）とする。
【００７１】
次に、パス検索部４５０は、遺伝子コードＧ１，Ｇ３〜Ｇ２０から、いずれか１個を選択する。パス検索部４５０は、まず、乱数生成部４４０に、０以上１未満の乱数Ｒを生成させ、さらに、この乱数Ｒの値の基づいて遺伝子コードを選択する。例えば、乱数Ｒが、０≦Ｒ＜ｘ１のときは遺伝子コードＧ１が選択され、ｘ１≦Ｒ＜ｘ３のときは遺伝子コードＧ３が選択され、ｘ３≦Ｒ＜ｘ４のときは遺伝子コードＧ４が選択される。このような方法によれば、上述の被選択確率に応じた確率で、いずれかの遺伝子コードを選択することができる。
【００７２】
パス検索部４５０は、１９個の遺伝子コードＧ１，Ｇ３〜Ｇ２０からいずれか１個を選択する処理を、２０回繰り返す。選択された遺伝子コードは、次回以降の選択処理でも、選択候補の遺伝子コード群に含まれる。したがって、この選択処理では、同じ遺伝子コードが２回以上選択されるケースが、１回以上発生する。また、特定の遺伝子コードが１回も選択されない場合も、あり得る。この選択処理で選択された遺伝子コードの一例を、図９（Ｂ）に示す。図９（Ｂ）では、選択後の各遺伝子コードに、新しく符号Ｇｓ１〜Ｇｓ２０が付されている。選択された遺伝子コードＧｓ１〜Ｇｓ２０は、予め保存された最も優秀な遺伝子コードＧ２とともに、遺伝子コードテーブル４２０に格納される。
【００７３】
（４）遺伝子コードの交叉
次に、パス検索部４５０は、遺伝子コードの交叉を行う（図７のステップＳ７０６〜Ｓ７０８参照）。交叉とは、同じ個体群に属する遺伝子コード間でランダムに一部の要素を交換する処理であり、生物界において個体どうしが交配することによって遺伝子が交叉されることに対応している。以下に説明するように、この実施形態では、遺伝子コードから任意の遺伝子コード・ペアを生成し、ランダムに選択された遺伝子要素を各遺伝子コード・ペア間で交換する。
【００７４】
最初に、パス検索部４５０は、以下のようにして予備コードＰ１〜Ｐ２０を作成する（図７のステップＳ７０６参照）。
【００７５】
まず、パス検索部４５０は、順序リストＣ（０）を作成する。この実施形態では、ＩＰ基幹ネットワーク１００のノード数が９個であるため、順序リストＣ（０）として、１から９までの自然数を小さい順に並べてなる数列｛１，２，３，４，５，６，７，８，９｝を使用する。但し、数値‘１’〜‘９’の並び順は、これに限定されない。
【００７６】
次に、パス検索部４５０は、遺伝子コードテーブル４２０から、選択された遺伝子コードＧｓ１を読み出す。図９（Ｂ）の例では、遺伝子コードＧｓ１のデータ構造は、｛１，６，３，７，４，８，９，２，５｝である。
【００７７】
続いて、パス検索部４５０は、順序リストＣ（０）と遺伝子コードＧｓ１とを用い、以下のようにして、予備コードＰ１を作成する（図１０参照）。
【００７８】
パス検索部４５０は、遺伝子コードＧｓ１＝｛１、６、３、７、４、８、９、２、５｝から１番目の要素を読み出す。ここで、遺伝子コードＧｓ１の１番目の要素は‘１’である。さらに、パス検索部４５０は、この要素‘１’が順序リストＣ（０）の何番目の要素と一致するかを、チェックする。ここで、‘１’は、順序リストＣ（０）の１番目の要素である。したがって、パス検索部４５０は、予備コードＰ１の１番目の要素を‘１’とする（図１０（Ａ）参照）。
【００７９】
次に、パス検索部４５０は、順序リストＣ（０）から１番目の要素‘１’を取り除くことにより、順序リストＣ（１）＝｛２，３，４，５，６，７，８，９｝を作成する。そして、パス検索部４５０は、遺伝子コードＧｓ１の２番目の要素を読み出して、順序リストＣ（１）の何番目の要素と一致するかをチェックする。ここで、遺伝子コードＧｓ１の２番目の要素は‘６’であり、‘６’は順序リストＣ（１）の５番目の要素である。したがって、パス検索部４５０は、予備コードＰ１の２番目の要素を‘５’とする（図１０（Ｂ）参照）。
【００８０】
さらに、パス検索部４５０は、順序リストＣ（１）から５番目の要素‘６’を取り除くことにより、順序リストＣ（２）＝｛２，３，４，５，７，８，９｝を作成する。そして、パス検索部４５０は、遺伝子コードＧｓ１の３番目の要素を読み出して、順序リストＣ（２）の何番目の要素と一致するかをチェックする。ここで、遺伝子コードＧｓ１の３番目の要素は‘３’であり、‘３’は順序リストＣ（２）の２番目の要素である。したがって、パス検索部４５０は、予備コードＰ１の３番目の要素を‘２’とする（図１０（Ｃ）参照）。
【００８１】
以下、パス検索部４５０は、このような操作を繰り返す。このようにして、最終的に、予備コードＰ１＝｛１，５，２，４，２，３，３，１，１｝が得られる（図１０（Ｄ）参照）。
【００８２】
続いて、パス検索部４５０は、遺伝子コードＧｓ２＝｛３，５，１，８，６，７，４，２，９｝（図９（Ｂ）参照）についても同様の処理を行う。これにより、予備コードＰ２＝｛３，４，１，５，３，３，２，１，１｝を得ることができる（図１０（Ｅ）参照）。
【００８３】
同様にして、他の遺伝子コードＧｓ３〜Ｇｓ２０についても、予備コードＰ３〜Ｐ２０が作成される。
【００８４】
次に、パス検索部４５０は、予備コードＰ１〜Ｐ２０を１０個のペアに分け、同一ペア間で交叉を行う（図７のステップＳ７０７参照）。ペアの決定方法は任意であり、パラメータを用いて組み合わせを決定することとしてもよい。ここでは、予備コードＰ１，Ｐ２のペアを交叉させる場合を例に採って説明する（図１０（Ｆ）参照）。
【００８５】
この交叉処理において、パス検索部４５０は、最初に、予備コードＰ１，Ｐ２の交叉位置を決定する。交叉位置の決定は、例えば、乱数生成部４４０に、１〜９の自然数のいずれかを生成させることによって、行うことができる。例えば、生成された乱数が‘３’の場合、パス検索部４５０は、予備コードＰ１，Ｐ２の３番目の要素まではそのままとし、４番目以降の要素を交換する。その結果、交叉後の予備コードとして、Ｐｈ１＝｛１，５，２，５，３，３，２，１，１｝と、Ｐｈ２＝｛３，４，１，４，２，３，３，１，１｝とが得られる（図１０（Ｇ）参照）。
【００８６】
続いて、パス検索部４５０は、以下のようにして、交叉後の予備コードＰｈ１，Ｐｈ２から、交叉後の遺伝子コードＧｈ１，Ｇｈ２を復元する（図７のステップＳ７０８、図１１参照）。
【００８７】
まず、パス検索部４５０は、交叉後の予備コードＰｈ１から１番目の要素を読み出す。ここでは、予備コードＰｈ１の１番目の要素は、‘１’である。さらに、順序リストＣ（０）の１番目の要素は‘１’である。したがって、パス検索部４５０は、遺伝子コードＧｈ１の１番目の要素を、‘１’とする（図１１（Ａ）参照）。
【００８８】
次に、パス検索部４５０は、予備コードＰｈ１の２番目の要素を読み出す。ここで、予備コードＰｈ１の２番目の要素は‘５’であり、順序リストＣ（１）の５番目の要素は‘６’である。したがって、パス検索部４５０は、遺伝子コードＧｈ１の２番目の要素を‘６’とする（図１１（Ｂ）参照）。
【００８９】
さらに、パス検索部４５０は、予備コードＰｈ１の３番目の要素を読み出す。ここで、予備コードＰｈ１の３番目の要素は‘２’であり、順序リストＣ（２）の２番目の要素は‘３’である。したがって、パス検索部４５０は、遺伝子コードＧｈ１の３番目の要素を‘３’とする（図１１（Ｃ）参照）。
【００９０】
以下、パス検索部４５０は、このような操作を繰り返す。このようにして、最終的に、交叉後の遺伝子コードＧｈ１＝｛１，６，３，８，５，７，４，２，９｝が得られる（図１１（Ｄ）参照）。
【００９１】
続いて、パス検索部４５０は、交叉後の予備コードＰｈ２＝｛３，４，１，４，２，３，３，１，１｝（図１０（Ｇ）参照）についても同様の処理を行う。これにより、交叉後の遺伝子コードＧｈ２＝｛３，５，１，７，４，８，９，２，６｝を得ることができる（図１１（Ｅ）参照）。
【００９２】
同様にして、他の予備コードＰｈ３〜Ｐｈ２０からも、遺伝子コードＧｈ３〜Ｇｈ２０が復元される。
【００９３】
以上のようにして遺伝子コードＧｓ１〜Ｇｓ２０の交叉が行われ、その結果、交叉後の遺伝子コードＧｈ１〜Ｇｈ２０が得られる（図９（Ｃ）参照）。
【００９４】
（５）遺伝子コードの突然変異
次に、パス検索部４５０は、遺伝子コードに突然変異を発生させる（図７のステップＳ７０９参照）。突然変異とは、遺伝子コードを構成する要素の一部を所定の低い確率でランダムに書き換える処理であり、生物界において遺伝子が突発的に変異を起こすことに対応している。突然変異を発生させることにより、演算解が局所解に陥り難くなる。以下に説明するように、この実施形態では、一般的に逆位と呼ばれる手法を使用して、遺伝子コードに含まれる遺伝子要素の一部または全部を所定の確率で変更する。
【００９５】
パス検索部４５０には、予め、突然変異が発生する確率が格納されている。突然変異の発生確率やその決定方法は任意であり、例えばパラメータを用いて発生確率を変動させてもよい。ここでは、突然変異の発生確率を、０．０３とする。
【００９６】
パス検索部４５０は、乱数生成部４４０に、交叉後の遺伝子コードＧｈ１〜Ｇｈ２０にそれぞれ対応させて、乱数Ｒ１〜Ｒ２０を発生させる。ここでは、各乱数Ｒ１〜Ｒ２０は、それぞれ０以上１未満の実数とする。そして、乱数Ｒ１〜Ｒ２０の値が突然変異発生確率の設定値（ここでは０．０３）以下であった遺伝子コードに対してのみ、突然変異を発生させる。図９（Ｄ）に、乱数Ｒ１〜Ｒ２０の例を示す。図９（Ｄ）の例では、遺伝子コードＧｈ１が、突然変異処理の対象になる。
【００９７】
突然変異処理では、まず、乱数生成部４４０が、突然変異を発生させる遺伝子コード毎に、新たに２個の乱数ｈ，ｋを発生させる。これらの乱数ｈ，ｋはそれぞれ１以上９以下の自然数であり、且つ、ｈ≠ｋである。そして、パス検索部４５０は、遺伝子コードＧｈ１の、ｈ番目の要素からｋ番目の要素までの並び順を逆転させる。すなわち、突然変異前の遺伝子コードＧｈ１を下式（１）で表した場合（ここではｈ＜ｋとした）、突然変異後の遺伝子コードＧｍ１は下式（２）のようになる。
【００９８】
Gh1＝｛s(1),…,s(h-1),s(h),s(h+1),…,s(k-1),s(k),s(k+1),…,s(9)｝・・・（１）
Gm1＝｛s(1),…,s(h-1),s(k),s(k-1),…,s(h+1),s(h),s(k+1),…,s(9)｝・・・（２）
例えば、遺伝子コードＧｈ１に対応して生成した乱数がｈ＝２，ｋ＝８の場合、Ｇｈ１＝｛１，３，４，２，９，８，７，６，５｝は、Ｇｍ１＝｛１，６，７，８，９，２，４，３，５｝に変異する。
【００９９】
次に、パス検索部４５０は、突然変異処理を行わなかった遺伝子コードのいずれか１個をランダムに選択する。そして、パス検索部４５０は、選択された遺伝子コードの各要素の値を、最も優秀な遺伝子コードの各要素の値に書き換える。これにより、最も優秀な遺伝子コードが次の世代に残されて、最適解または最適解に近い解が得られ易くなる。図９（Ｅ）に、遺伝子コードＧｈ２０が最も優秀な遺伝子コードＧ２に書き換えられた例を示す。
【０１００】
その後、パス検索部４５０は、個体群内の各遺伝子コードを用いて、ステップＳ７０２以降の処理を、再び行う。これら一連の処理Ｓ７０２〜Ｓ７１０は、ステップ７０４で終了条件を満たしていると判断されるまで、繰り返される。
【０１０１】
ステップＳ７０４で終了条件を満たしていると判断された場合、パス検索部４５０は遺伝的アルゴリズムによる演算処理を終了し、このときの最も優秀な遺伝子コードを最適な論理トポロジを示す演算解であると判定する。そして、パス検索部４５０は、この演算解を、物理パス割当処理部４６０（図４参照）に送る。
【０１０２】
物理パス割当処理部４６０は、現状パスの終端ノードのペアと物理経路とに関する情報を、内部に記憶している。物理パス割当処理部４６０は、パス検索部４５０から受信した最適解を当該記憶情報と比較して、終端ノードが一致する光パスのマッピングを作成する。そして、物理パス割当処理部４６０は、終端ノードが一致する光パスについては、現状パスの物理経路を、最適な光パスの物理経路にそのまま割り当てる。一方、終端ノードが一致しない光パスについては、例えば公知のダイクストラ(Dijkstra)法等を用いて、最短物理経路を判定し、当該判定結果を最適な光パスの物理経路に割り当てる。ここで、同一長の物理経路が複数種類存在する場合には、ランダムに割り当てればよい。このようにして、物理パス割当処理部４６０は、パス検索部４５０の検索結果に対応する終端ノード・ペアおよび物理経路を決定する。この物理経路情報は、現状パスの情報として物理パス割当処理部４６０内に記憶されるとともに、送信処理部４７０を介して、光パス設定管理装置２３０（図２参照）に送られる。
【０１０３】
光パス設定管理装置２３０は、受信した物理経路情報を用いて各ノードＮ１〜Ｎ９内の光スイッチ制御装置３７１（図３参照）を制御することにより、ＩＰ基幹ネットワーク１００の物理経路を変更する。また、光パス設定管理装置２３０は、当該物理経路情報に応じて、各ノードＮ１〜Ｎ９内のＩＰルータに格納されたルーティング表（図示せず）を変更する。
【０１０４】
以上説明したように、この実施形態に係る最適光パス配置検索装置によれば、最適なカットスルーパスを、遺伝的アルゴリズムを用いた簡単な処理によって検索することができる。
【０１０５】
第２の実施形態
次に、この発明の第２の実施形態について、図１２〜１４を用いて説明する。この実施形態は、この発明に係る最適パス配置検索装置を、本発明者が既に提案した経路配置移行方法（特願２００４−３５８３６７）を使用するＩＰ基幹ネットワークに適用した例である。
【０１０６】
この実施形態に係るＩＰ基幹ネットワークのデータプレーン構成および制御プレーン構成は、第１の実施形態の場合（図１、図２参照）と同様である。また、各ノードＮ１〜Ｎ９、トラヒック計測管理装置２１０および最適光パス配置検索装置２２０の構成も、第１の実施形態の場合（図３、図４参照）と同様である。一方、この実施形態の光パス設定管理装置２３０は、最適光パス配置検索装置から受信した物理経路情報を用い、上述の経路配置移行方法（特願２００４−３５８３６７）を使用して、ＩＰ基幹ネットワークの光パス設定を変更する。
【０１０７】
図１２は、この実施形態に係るＩＰ基幹ネットワークの論理トポロジを示す概念図である。図１２から解るように、この実施形態では、論理配置Ｌ１〜Ｌ９間に合計９本の論理パスを設定することによって、ＩＰ基幹ネットワーク上にリング構造の論理トポロジを構築する。
【０１０８】
図１３は、図１２の各論理配置Ｌ１〜Ｌ９にノードＮ１〜Ｎ９を配置した例である。上述の第１の実施形態と同様、この実施形態でも、通常の光パスやカットスルーパスを適当に設定することにより、各論理配置Ｌ１〜Ｌ９に任意のノードを配置することができる。最適光パスの検索には、第１の実施形態と同様の遺伝的アルゴリズムが使用される。
【０１０９】
この実施形態に係るＩＰ基幹ネットワークでも、第１の実施形態と同様、例えば四種類の波長の搬送波をＷＤＭ多重化して、ＩＰパケットの送受信を行う（図３参照）。但し、この実施形態では、各ノードは、同じ論理パスに対しては、同一波長の搬送波を使用する。上述の第１の実施形態では、例えば波長λ１の受信搬送波が、光送受信機３４１で波長λ０に変換されてルーティングが行われ、その後、他の光送受信機３４２〜３４４のいずれかで波長λ２，λ３またはλ４の搬送波に再変換されて送信される場合もあった。これに対して、この実施形態では、例えば波長λ１の搬送波を用いて受信されたＩＰパケットは、常に、波長λ１の搬送波に再変換されて送信される。
【０１１０】
図１２、図１３に示したように、すべてのノードＮ１〜Ｎ９は、２つのパスに対する終端ノードとして使用される。したがって、各ノードＮ１〜Ｎ９において、ＩＰルータ３５１が中継する搬送波波長は二種類である（中継に使用する波長が一種類とカットスルーに使用する波長が一種類）。これに対して、各ＩＰルータ３５１は、四種類の搬送波波長を使用することができる（図３参照）。このため、各ノードＮ１〜Ｎ９では、割り当てられた４種類の波長のうち、２種類の波長を現用論理パスの構築に使用し、残りの２種類の波長を予備とする。
【０１１１】
このように、この実施形態によれば、第１の実施形態よりも少ないカットスルーパスを用いて、すべてのノードＮ１〜Ｎ９を連結することができる。すなわち、この実施形態では、第１の実施形態よりも少ない種類の波長を用いて、論理トポロジを構築することが可能である。このため、最適な光パス配置を実現しつつ、上述のような予備の光パスを確保することができる。予備の光パスは、現用パスにおいて突発的な輻輳・障害が発生したときの救済に使用することが可能である。
【０１１２】
この実施形態に係るＩＰ基幹ネットワークにおいても、第１の実施形態のＩＰ基幹ネットワークと同様の遺伝的アルゴリズム（図７〜図１１参照）を用いて、最適な光パスを検索する。図１４に、図１３のノード配置に対応する遺伝子コードの構成を、概念的に示す。すなわち、この実施形態に係る最適光パス配置検索装置によれば、現行論理パスと予備論理パスとを備えたリング構造のＩＰ基幹ネットワークにおいて、遺伝的アルゴリズムを用いた簡単な処理によって、最適なカットスルーパスを検索することができる。
【０１１３】
第３の実施形態
次に、この発明の第３の実施形態について、図１５〜図１７を用いて説明する。この実施形態に係る最適パス配置検索装置は、中継トラヒック量の最大値のみならず、１搬送波当たりのトラヒック量の最大値をも考慮して最適な光パス配置を検索する点で、上述の第１の実施形態の最適パス配置検索装置と異なる。
【０１１４】
この実施形態に係るＩＰ基幹ネットワークのデータプレーン構成および制御プレーン構成は、第１の実施形態の場合（図１、図２参照）と同様である。また、各ノードＮ１〜Ｎ９、トラヒック計測管理装置２１０および光パス設定管理装置２３０の構成も、第１の実施形態の場合（図２、図３参照）と同様である。
【０１１５】
図１５は、最適光パス配置検索装置の内部構成を示すブロック図である。図１５において、図４と同じ符号を付した構成要素は、それぞれ、図４の場合と同じものを示している。
【０１１６】
図１５から解るように、この実施形態に係る最適光パス配置検索装置は、目的関数・適合度変換部１５１０を備えている。目的関数・適合度変換部１５１０は、各遺伝子コードの中継トラヒック量の最大値および１搬送波当たりのＩＰパケット伝送量の最大値とから、当該遺伝子コードの優越順位を演算する（後述）。
【０１１７】
以下、最適光パス配置検索装置２２０の演算動作について、図１６および図１７を用いて説明する。
【０１１８】
図１６は、この実施形態に係る最適光パス配置検索装置の演算処理を概略的に示すフローチャートである。
【０１１９】
（１）初期個体群の生成
まず、第１の実施形態と同様にして、乱数生成部４４０（図１５参照）が複数の遺伝子コードからなる初期個体群を生成する（図１６のステップＳ１６０１参照）。この実施形態でも、第１の実施形態と同様、初期個体群は２０個の遺伝子コードを備え、且つ、各遺伝子コードは９個の要素を備える。生成された遺伝子コードは、遺伝子コードテーブル４２０に格納される。
【０１２０】
（２）遺伝子コードの評価
次に、パス検索部４５０が、以下のようにして、当該個体群に属する各遺伝子コードの評価を行う（図１６のステップＳ１６０２，Ｓ１６０３参照）。
【０１２１】
まず、パス検索部４５０が、これら遺伝子コードの適合度を計算する（図１６のステップＳ１６０２参照）。この実施形態の適合度演算処理では、まず、第１の実施形態と同様にして、遺伝子コード毎に、ノード配置パターンに対応する論理トポロジが仮想的に構築され、さらに、当該論理トポロジにおける各ノード間の最短経路がそれぞれ計算される。続いて、パス検索部４５０は、これらの最短経路について、中継トラヒック量と、１搬送波当たりのトラヒック量とを、ノードごとに算出する。かかる中継トラヒック量および１搬送波当たりのトラヒック量は、目的関数として、目的関数テーブル４３０に格納される。そして、目的関数・適合度変換部１５１０が、当該中継トラヒック量のうち最も大きいものと、当該１搬送波当たりのトラヒック量のうち最も大きいものとを用いて、各遺伝子コードの優越順位を計算する。
【０１２２】
図１７は、優越順位の算出方法を説明するためのグラフであり、横軸ｆは中継トラヒック量の最大値、縦軸ｇは１搬送波当たりのトラヒック量の最大値である。目的関数・適合度変換部１５１０は、各遺伝子コードに対応する中継トラヒック量の最大値および１搬送波当たりのトラヒック量の最大値を、目的関数テーブル４３０から受け取る。そして、各遺伝子コードについて、中継トラヒック量の最大値と１搬送波当たりのトラヒック量の最大値との両方が当該遺伝子コードよりも小さい遺伝子コードの個数を計数する。例えば、図１７の遺伝子コードＣ７の場合、中継トラヒック量の最大値（すなわちｆ座標）および１搬送波当たりのトラヒック量の最大値（すなわちｇ座標）の両方が当該遺伝子コードＣ７よりも小さいのは、３個の遺伝子コードＣ１，Ｃ３，Ｃ４のみである。したがって、遺伝子コードＣ７の優越順位は、‘４’である。また、遺伝子コードＣ２，Ｃ４については、ｆ座標およびｇ座標の両方が当該遺伝子コードよりも小さいのは、遺伝子コードＣ１のみである。したがって、遺伝子コードＣ２，Ｃ４の優越順位は‘２’である。さらに、遺伝子コードＣ１，Ｃ３，Ｃ５，Ｃ６は、ｆ座標およびｇ座標の両方が小さい遺伝子コードが存在しないので、優越順位は‘１’である。
【０１２３】
続いて、パス検索部４５０が、２０個の遺伝子コードから、最も優秀な遺伝子コードを選択する（図１６のステップＳ１６０３参照）。この実施形態では、優越順位が最も小さい遺伝子コードが、最も優秀な遺伝子コードである。
【０１２４】
パス検索部４５０は、最も優秀な遺伝子コードを読み出して、終了条件を満たしているか否かを判定する（図１６のステップＳ１６０４参照）。最も優秀な遺伝子コードが複数個ある場合には、いずれか１個をランダムに選択してもよいし、最も優秀な遺伝子コードすべてについて終了条件をチェックしてもよいし、他の方法を採用してもよい。この実施形態では、最も優秀な遺伝子コードの中継トラヒック量の最大値および１搬送波当たりのトラヒック量の最大値がともに閾値以下になった場合、遺伝的アルゴリズムの処理時間が予め設定された処理時間を超えた場合または遺伝子コードに対する演算処理が予め定められた世代分行われた場合に、終了条件が満たされたと判定する。
【０１２５】
（３）遺伝子コードの選択
終了条件が満たされていなかった場合、パス検索部４５０は、以下のようにして、遺伝子コードの選択を行う（図１６のステップＳ１６０５参照）。
【０１２６】
この実施形態の選択処理では、優越順位が‘１’の遺伝子コードは、無条件に選択される。そして、残りの遺伝子コードから例えば２０個の遺伝子コードが選択される。この実施形態でも、第１の実施形態と同様にして、パス検索部４５０は、対象となる遺伝子コード（優越順位が‘１’でない遺伝子コード）に、被選択確率を割り当てる。この被選択確率は、優越順位が小さい遺伝子コードほど高くなるように割り当てられる。そして、パス検索部４５０は、第１の実施形態と同様にして、遺伝子コードの選択を、例えば２０回行う。これにより、上述の被選択確率に応じた確率で、所定数個の遺伝子コードが選択される。選択された遺伝子コードは、遺伝子コードテーブル４２０に格納される。
【０１２７】
（４）遺伝子コードの交叉
次に、パス検索部４５０は、第１の実施形態と同様にして、予備コードを作成し（図１６のステップＳ１６０６参照）、予備コードの交叉を行い（図１６のステップＳ１６０７参照）、さらに、交叉後の予備コードから遺伝子コードを復元する（図１６のステップＳ１６０８参照）。
【０１２８】
（５）遺伝子コードの突然変異
さらに、パス検索部４５０は、第１の実施形態と同様にして、遺伝子コードに突然変異を発生させる（図１６のステップＳ１６０９参照）。
【０１２９】
その後、パス検索部４５０は、個体群内の各遺伝子コードを用いて、ステップＳ１６０２以降の処理を、再び行う。これら一連の処理Ｓ１６０２〜Ｓ１６０９は、ステップ１６０４で終了条件を満たしていると判断されるまで、繰り返される。
【０１３０】
ステップＳ１６０４で終了条件を満たしていると判断された場合、パス検索部４５０は遺伝的アルゴリズムによる演算処理を終了し、このときの最も優秀な遺伝子コードを最適な論理トポロジを示す演算解であると判定する。そして、パス検索部４５０は、この演算解を、物理パス割当処理部４６０（図１５参照）に送る。
【０１３１】
なお、この実施形態では、上述の選択処理（図１６のステップＳ１６０５参照）において優越順位が‘１’の遺伝子コードをすべて選択した代わりに、突然変異処理では最も優秀な遺伝子コードの導入を行わなかった。但し、上述の第１の実施形態と同様、選択処理では最も優秀な遺伝子コード以外の遺伝子コードを用い、突然変異処理では当該最も優秀な遺伝子コードの導入を行うこととしてもよい。
【０１３２】
他の動作については、第１の実施形態と同様であるので、説明を省略する。
【０１３３】
以上説明したように、この実施形態に係る最適光パス配置検索装置によれば、最適なカットスルーパスを、中継トラヒック量と１搬送波当たりのトラヒック量の両方を考慮した遺伝的アルゴリズムを用いて、検索することができる。
【図面の簡単な説明】
【０１３４】
【図１】第１の実施形態に係るＩＰ基幹ネットワークのデータプレーン構成を示す概念図である。
【図２】第１の実施形態に係るＩＰ基幹ネットワークの制御プレーン構成を示す概念図である。
【図３】第１の実施形態に係るノードの内部構成を示すブロック図である。
【図４】第１の実施形態に係る最適光パス配置検索装置の内部構成を示すブロック図である。
【図５】第１の実施形態に係るＩＰ基幹ネットワークの論理トポロジを示す概念図である。
【図６】図５に示した論理トポロジへのノード配置の一例を示す概念図である。
【図７】第１の実施形態に係る最適光パス配置検索装置の演算処理を概略的に示すフローチャートである。
【図８】第１の実施形態で使用される遺伝子コードのデータ構造を示す表である。
【図９】（Ａ）〜（Ｅ）ともに、第１の実施形態に係る最適光パス配置検索装置の動作を説明するための表である。
【図１０】（Ａ）〜（Ｇ）ともに、第１の実施形態に係る最適光パス配置検索装置の動作を説明するための表である。
【図１１】（Ａ）〜（Ｅ）ともに、第１の実施形態に係る最適光パス配置検索装置の動作を説明するための表である。
【図１２】第２の実施形態に係るＩＰ基幹ネットワークの論理トポロジを示す概念図である。
【図１３】図１２に示した論理トポロジへのノード配置の一例を示す概念図である。
【図１４】第２の実施形態で使用される遺伝子コードのデータ構造を示す表である。
【図１５】第３の実施形態に係る最適光パス配置検索装置の内部構成を示すブロック図である。
【図１６】第３の実施形態に係る最適光パス配置検索装置の演算処理を概略的に示すフローチャートである。
【図１７】第３の実施形態に係る最適光パス配置検索装置の動作を説明するための表である。
【符号の説明】
【０１３５】
１００  ＩＰ基幹ネットワーク
Ｎ１〜Ｎ９  ノード
Ｆ１〜Ｆ２４  光ファイバ
２１０  トラヒック計測管理装置
２２０  最適光パス配置検索装置
２３０  光パス設定管理装置
２４０，２５０  制御ネットワーク
３１１〜３１４  光増幅器
３２１〜３２４  光合分波器
３３１，３３２  光スイッチ
３４１〜３４４  光送受信機
３５１  ＩＰルータ
３６１，３６２  トラヒック計測装置
３７１  光スイッチ制御装置
４１０  受信処理部
４２０  遺伝子コードテーブル
４３０  目的関数テーブル
４４０  乱数生成部
４５０  パス検索部
４６０  物理パス割当処理部
４７０  送信処理部
【図１】
2006270677.tif 000003
【図２】
2006270677.tif 000004
【図３】
2006270677.tif 000005
【図４】
2006270677.tif 000006
【図５】
2006270677.tif 000007
【図６】
2006270677.tif 000008
【図７】
2006270677.tif 000009
【図８】
2006270677.tif 000010
【図９】
2006270677.tif 000011
【図１０】
2006270677.tif 000012
【図１１】
2006270677.tif 000013
【図１２】
2006270677.tif 000014
【図１３】
2006270677.tif 000015
【図１４】
2006270677.tif 000016
【図１５】
2006270677.tif 000017
【図１６】
2006270677.tif 000018
【図１７】
2006270677.tif 000019