(57)【要約】  トポロジ抽出方法、装置、およびルートコントローラが開示される。トポロジ抽出方法は、リアルトポロジＧＲ内のそれぞれの１対の境界ノード間のリンクダイバーシティパス数ｃ（ｉ，ｊ，λｋ）を取得するステップと、リンクダイバーシティパス数を使用して、接続性マトリックスＣを取得して対応する合計接続性トポロジＧＢを構築するステップとを含む。本方法は、遺伝的アルゴリズムを使用することによって合計接続性トポロジを双方向シャッフルネットトポロジに圧縮するステップをさらに含む。
2011517220.tif 000002
【特許請求の範囲】
【請求項１】
リアルトポロジＧＲ内のそれぞれの１対のボーダーノード間のリンクダイバーシティパス数ｃ（ｉ，ｊ，λｋ）を取得するステップと、
前記リンクダイバーシティパス数ｃ（ｉ，ｊ，λｋ）を利用することによって接続性マトリックスＣを取得して、対応するフルメッシュトポロジＧＢを構築するステップとを含む、トポロジ集約のための方法。
【請求項２】
前記リンクダイバーシティパス数がボーダーノード間の最大フローを計算することによって取得される、請求項１に記載の方法。
【請求項３】
ボーダーノード間の最大フローを計算するステップが最高レベルプリフロープッシュアルゴリズムを利用することによって実行される、請求項２に記載の方法。
【請求項４】
前記フルメッシュトポロジへのトポロジ圧縮を実行するステップをさらに含む、請求項１に記載の方法。
【請求項５】
前記トポロジ圧縮を実行するステップが、
双方向シャッフルネットトポロジの構造パラメータを決定するステップと、
前記構造パラメータを利用することによって前記双方向シャッフルネットトポロジを初期化するステップと、
前記接続性マトリックスを利用することによって前記双方向シャッフルネットトポロジを最適化するステップとを含む、請求項４に記載の方法。
【請求項６】
前記双方向シャッフルネットトポロジを最適化するステップが遺伝的アルゴリズムに基づき、
前記双方向シャッフルネットトポロジの第１世代をランダムに取得するステップと、
現在の世代の染色体のトポロジの接続性マトリックスを取得するステップと、
リアルトポロジのボーダーノードの接続性マトリックスを目的関数として使用して現在の世代の染色体ごとに適合値を計算するステップと、
前記適合値に基づいて現在の世代のそれぞれの染色体に遺伝子操作を実行して次世代の染色体を取得するステップと、
染色体のトポロジの接続性マトリックスを取得し、適合値を計算し、かつ遺伝子操作を実行する操作を、遺伝子操作を終了させる条件が満たされるまで反復するステップと、
最適化された双方向シャッフルネットトポロジを取得するために、結果として得られる染色体を利用することによってフルメッシュトポロジのノードを双方向シャッフルネットトポロジにマッピングするステップとを含む、請求項５に記載の方法。
【請求項７】
前記適合値がそれぞれの偏差値の合計の逆であり、前記それぞれの偏差値が染色体のトポロジの接続性マトリックスと前記フルメッシュトポロジの接続性マトリックスとの間の合計との差異の割合の絶対値である、請求項６に記載の方法。
【請求項８】
遺伝子操作を終了させる条件が反復の数があらかじめ定められた値に達することである、請求項６に記載の方法。
【請求項９】
前記染色体が１次元リテラル順列符号化を利用する、請求項６に記載の方法。
【請求項１０】
ネットワーク状態が変化するときにトポロジの再集約を実行するステップをさらに含む、請求項１に記載の方法。
【請求項１１】
トポロジの再集約が怠惰な再集約ポリシーに基づき、あらかじめ定められたトポロジ変更イベントが発生するか、接続拒否率があらかじめ定められたしきい値に達するときに実行される、請求項１０に記載の方法。
【請求項１２】
前記あらかじめ定められたトポロジ変更イベントが利用可能なリソースの量があらかじめ定められた値になるイベントであり、前記あらかじめ定められたトポロジ変更イベントが、利用可能なリソースがより多い場合はより低い頻度で発生し、利用可能なリソースがより少ない場合はより高い頻度で発生する、請求項１１に記載の方法。
【請求項１３】
リアルトポロジＧＲ内のそれぞれの１対のボーダーノード間のリンクダイバーシティパス数ｃ（ｉ，ｊ，λｋ）を取得するように構成されたリンクダイバーシティパス数取得手段と、
前記リンクダイバーシティパス数ｃ（ｉ，ｊ，λｋ）を使用することによって接続性マトリックスＣを取得して、対応するフルメッシュトポロジＧＢを構築するように構成されたトポロジ構築手段とを備える、トポロジ集約のための装置。
【請求項１４】
前記リンクダイバーシティパス数取得手段が、ボーダーノード間の最大フローを計算することによって前記リンクダイバーシティパス数を取得するようにさらに構成された、請求項１３に記載の装置。
【請求項１５】
ボーダーノード間の最大フローを計算するステップが最高レベルプリフロープッシュアルゴリズムを利用することによって実行される、請求項１４に記載の装置。
【請求項１６】
前記フルメッシュトポロジを圧縮するように構成されたトポロジ圧縮手段をさらに備える、請求項１３に記載の装置。
【請求項１７】
前記トポロジ圧縮手段が、
双方向シャッフルネットトポロジの決定された構造パラメータを利用することによって双方向シャッフルネットトポロジを初期化するように構成された双方向シャッフルネットトポロジ構築手段と、
リアルトポロジのボーダーノードの接続性マトリックスを目的として利用することによって前記双方向シャッフルネットトポロジを最適化するように構成された双方向シャッフルネットトポロジ最適化手段とを備える、請求項１６に記載の装置。
【請求項１８】
前記双方向シャッフルネットトポロジ最適化手段が遺伝的アルゴリズムに基づき、
前記双方向シャッフルネットトポロジの第１世代をランダムに取得するように構成された第１世代生成手段と、
現在の世代の染色体のトポロジの接続性マトリックスを取得するように構成された接続性マトリックス取得手段と、
リアルトポロジのボーダーノードの前記接続性マトリックスを目的として使用して現在の世代の染色体ごとに適合値を計算するように構成された適合値計算手段と、
前記適合値に基づいて現在の世代のそれぞれの染色体に遺伝子操作を実行して次世代の染色体を取得するように構成された遺伝子操作手段と、
遺伝子操作を終了させる条件が満たされるときに、結果として得られる染色体を利用することによってフルメッシュトポロジのノードを双方向シャッフルネットトポロジにマッピングするように構成されたマッピング手段とを備える、請求項１７に記載の装置。
【請求項１９】
前記適合値がそれぞれの偏差値の合計の逆であり、前記偏差値が前記現在の世代の染色体のトポロジの接続性マトリックスと前記フルメッシュトポロジの接続性マトリックスとの間の合計との差異の割合の絶対値である、請求項１８に記載の装置。
【請求項２０】
遺伝子操作を終了させる条件が反復の数があらかじめ定められた値に達することである、請求項１８に記載の装置。
【請求項２１】
前記染色体が１次元リテラル順列符号化に基づく、請求項１８に記載の装置。
【請求項２２】
ネットワーク状態が変化するときにトポロジの再集約をトリガするように構成された再集約トリガ手段をさらに備える、請求項１３に記載の装置。
【請求項２３】
前記再集約トリガ手段が怠惰な再集約ポリシーに基づき、あらかじめ定められたトポロジ変更イベントが発生するか、接続拒否率があらかじめ定められたしきい値に達するときにトポロジの再集約をトリガする、請求項２２に記載の装置。
【請求項２４】
前記あらかじめ定められたトポロジ変更イベントが利用可能なリソースの量があらかじめ定められた値に増加または減少するイベントであり、前記あらかじめ定められたトポロジ変更イベントが、利用可能なリソースがより多い場合はより低い頻度で発生し、利用可能なリソースがより少ない場合はより高い頻度で発生する、請求項２３に記載の装置。
【請求項２５】
請求項１３から２４のいずれか一項に記載のトポロジ集約のための装置と、
トポロジ集約のための装置によって取得されたトポロジに基づいてリンクステート（ＬＳＡ）情報を生成して、前記ＬＳＡ情報を送出するように構成されたリンクステート送信手段とを備える、ルーティングコントローラ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はネットワーク技術に関し、より詳細にはトポロジ集約のための方法および装置、ならびにルーティングコントローラに関する。
【背景技術】
【０００２】
複数のルーティングドメインは全てＩＰネットワーク、ＡＴＭ（非同期伝送モード）ネットワーク、または新興のＡＳＯＮ（自動交換光ネットワーク）内に含まれる。
【０００３】
それぞれのルーティングドメインの内部トポロジ情報は、スケーラビリティおよびセキュリティのために、何らかのトポロジ集約方法を用いて集約されてから初めてネットワーク内の他のルーティングドメインに通知されうる。したがって、それぞれのルーティングドメインは自身の詳細なトポロジ情報ならびに他のルーティングドメインの集約されたトポロジ情報だけを維持し、その結果ネットワーク内に通知および格納される必要がある情報の量が減少する。
【０００４】
一般にトポロジ集約処理は、ボーダーノードから構成されるフルメッシュトポロジをリアルトポロジに基づいてまず構築すること、および任意選択でフルメッシュトポロジをスター型トポロジ、ツリー型トポロジなどのよりまばらなトポロジにさらに圧縮することを含む。
【０００５】
図１はトポロジ集約処理の例を示している。図１に示されるように、トポロジ１００は８つのノード１−８、１０のリンク、および作動している２つの波長λ１およびλ２を備えるリアルトポロジである。図１ではノード１−４は外部ピアドメインに接続されたボーダーノードであり、ノード５−８は内部ノードであり、ノード間の実線／点線はリンクの波長λ１／λ２パスが自由であり新しい接続が確立されうることを示している。
【０００６】
トポロジ集約の間、トポロジ１００の内部ノードは隠され、ボーダーノード１−４およびそれらの間のリソース可用性だけが保存される。これらの４つのボーダーノード間の接続性関係は、式（１）に示されるような接続性マトリックスによって表すことができる：
【数１】
2011517220.tif 000003
【０００７】
図１に示されるトポロジ１０１には４つのボーダーノード１−４があり、したがってボーダーノード間の接続性は波長λ１およびλ２ごとに４×４マトリックスによって表すことができる。２つのボーダーノードが接続できるようにする（たとえば、ノード１およびノード４が波長λ１パス１−５−６−３−４を通じて相互に接続できる）論理リンクがある場合は対応するマトリックスの要素は１に設定され、ない場合は０に設定される。
【０００８】
ボーダーノード１−４だけを含むトポロジ１０１は、接続性マトリックスに従って構築されたフルメッシュトポロジである。フルメッシュトポロジ構築後、リンクの数が５に減少したことが分かる（最悪の場合リンクの数は６であり、すなわち全てのノードが接続される）。
【０００９】
トポロジ１０２は、トポロジ１０１のさらなる圧縮の後に結果として得られるトポロジである。前者のトポロジ１０１内の余剰な論理リンクは削除され、たとえばノード３とノード４との間の波長λ１の論理リンクはパス３−１−４に置換され、ノード２とノード３との間の波長λ２の論理リンクはパス２−１−３に置換される。圧縮後、リンクの総数はさらに減少して３になる。
【００１０】
既存のトポロジ集約技術はＡＴＭネットワークのために設計されている。対称ノード手法、フルメッシュ手法、およびスター型手法を含む、３つのよく知られている方法がある。対称ノード手法の主な考え方は、リアルトポロジの全てのボーダーノードが単一の仮想ノード内に結合されて、ボーダーノード間の接続特性がある種の共通値によって表されることである。この手法の利点は、交換される必要があるのはごく少量の情報だけである点である。しかし欠点は、提供された情報は大まか過ぎて過度に不正確であり、そのためイントラドメインのリソースを適切に利用できないようになることがある点である。フルメッシュ手法は集約情報の正確さを目的とする。フルメッシュ手法は、リアルトポロジの全てのボーダーノードが論理リンクによって完全に接続されており、それぞれのボーダーノードは遅延または帯域幅などの１つまたは複数のＱｏＳパラメータで構成されていると仮定する。この手法は、元のリアルトポロジのボーダーノード間の接続性特性を正確に保存する。しかしこれはＮ（Ｎ−１）／２（Ｎはボーダーノードの数）論理リンクの情報を維持しなければならないので、ネットワークの大きさが比較的大きい場合、スケーラビリティに乏しい。スター型手法は、中心に仮想ノードがあり、リアルトポロジ内の全てのボーダーノードは論理リンクによって仮想ノードに接続されていると仮定する。さらに、それぞれの論理リンクは異なる特性を有してよい。したがってスター型手法はより詳細なリンク情報を表すことができ、対称ノード手法よりもはるかに正確な場合がある。同時に、スター型手法が維持する必要があるのはＮ個の論理リンクの情報だけであり、したがってフルメッシュ手法よりも良いスケーラビリティを有し、比較的大きなネットワークに適している。
【発明の概要】
【発明が解決しようとする課題】
【００１１】
ＡＴＭネットワークのために設計された前述のトポロジ集約方法が光ネットワークに適用されると、これらの方法は大まか過ぎて不正確なので、波長連続性規制の条件が満たされる必要があるときに良いパフォーマンスを達成できなくなる。したがって、トポロジ集約のためのより適したソリューションがＡＳＯＮなどの光ネットワークに必要である。
【００１２】
この目的を達成するために、本発明の目的は光ネットワークにより適したトポロジ集約のためのソリューションを提供することである。
【課題を解決するための手段】
【００１３】
本発明の一態様によれば、
リアルトポロジＧＲ内のそれぞれの１対のボーダーノード間のリンクダイバーシティパス数ｃ（ｉ，ｊ，λｋ）を取得するステップと、
前記リンクダイバーシティパス数ｃ（ｉ，ｊ，λｋ）を利用することによって接続性マトリックスＣを取得して、対応するフルメッシュトポロジＧＢを構築するステップとを含む、トポロジ集約のための方法が提供される。
【００１４】
本発明の他の態様によれば、
リアルトポロジＧＲ内のそれぞれの１対のボーダーノード間のリンクダイバーシティパス数ｃ（ｉ，ｊ，λｋ）を取得するように構成されたリンクダイバーシティパス数取得手段と、
前記リンクダイバーシティパス数ｃ（ｉ，ｊ，λｋ）を使用することによって接続性マトリックスＣを取得して、対応するフルメッシュトポロジＧＢを構築するように構成されたトポロジ構築手段とを備える、トポロジ集約のための装置が提供される。
【００１５】
本発明の他の態様によれば、
前述のトポロジ集約のための装置と、
トポロジ集約のための装置によって取得されたトポロジに基づいてリンクステート（ＬＳＡ）情報を生成して、前記ＬＳＡ情報を送出するように構成されたリンクステート送信手段とを備える、ルーティングコントローラが提供される。
【００１６】
本発明によれば、ルーティング決定のためのより多くのリンク情報、およびより正確なトポロジが提供されうる。
【００１７】
図面を参照して以下の詳細な説明を読むことで本発明を完全に理解することにより、本発明の他の目的および効果がより明らかになり、理解しやすくなるであろう。
【図面の簡単な説明】
【００１８】
【図１】従来技術によるトポロジ集約処理の例を示す図である。
【図２】本発明の実施形態によるトポロジ集約のための方法の流れ図である。
【図３】本発明の実施形態によるトポロジ圧縮処理の流れ図である。
【図４】双方向シャッフルネットトポロジの例を示す図である。
【図５】本発明の実施形態による双方向シャッフルネットトポロジに集約する処理の流れ図である。
【図６】本発明の実施形態による双方向シャッフルネットトポロジを最適化する処理の流れ図である。
【図７】フルメッシュトポロジ内のノードを双方向シャッフルネットにマッピングする方法を示す図である。
【図８】本発明の実施形態によるクロスオーバおよび変異操作の例を示す図である。
【図９】本発明の実施形態によるトポロジ集約のための装置の概略図である。
【図１０】本発明の他の実施形態によるトポロジ集約のための装置の概略図である。
【図１１】本発明の他の実施形態によるトポロジ集約のための装置内の双方向シャッフルネットトポロジ最適化手段の概略図である。
【図１２】本発明の他の実施形態によるトポロジ集約のための装置の概略図である。
【図１３】本発明の実施形態によるルーティングコントローラの概略図である。
【図１４】本発明の実施形態によるルーティングコントローラの開始段階の流れ図である。
【図１５】本発明の実施形態によるルーティングコントローラの作動段階の流れ図である。
【発明を実施するための形態】
【００１９】
上記の図面を通じて、同様の参照番号は同一、類似、または対応する特徴あるいは機能を示している。
【００２０】
以下で、図面を参照して特定の実施形態を用いて本発明を詳細に説明する。
【００２１】
図２は、本発明の実施形態によるトポロジ集約のための方法の流れ図を示している。本発明の実施形態の以下の説明では、トポロジ集約はＡＯＳＮ内の１つのドメインを対象とする。
【００２２】
図２に示されるように、ステップ２１０でまずドメインのリアルトポロジが取得される。
【００２３】
ＧＲ＝（Ｖ，Ｅ）  式（２）
【００２４】
上式で、Ｖはトポロジ内のノードのセットを表し、すなわちＶ＝｛ｖ１，ｖ２，．．．，ｖｎ｝であり、Ｅはノード間のリンクのセットを表し、すなわちＥ＝｛ｅ１，ｅ２，．．．，ｅｍ｝であり、それぞれのリンクは１つまたは複数の波長λ１、λ２、．．．、λＷをサポートでき、ｎはノードの総数であり、ｍはリンクの総数であり、Ｗは波長の総数である。ＧＲは、２つのノード間に複数の光ファイバリンクがあるマルチグラフでありうる点に留意されたい。
【００２５】
次にステップ２２０で、波長λ１λ２、．．．、λＷごとに、全てのノードを含む隣接マトリックスが取得される。
【数２】
2011517220.tif 000004
上式で、（ｉ、ｊ＝１、．．．、ｎ、ｋ＝１、．．．、Ｗ）である。波長λｋについては、ｒ（ｉ，ｊ，λｋ）＝ノードｉとノードｊとの間に１つまたは複数のリンクが存在する場合のリンクの数であり、そうでない場合はｒ（ｉ，ｊ，λｋ）＝０である。
【００２６】
次にステップ２３０で、それぞれの１対のボーダーノード間のリンクダイバーシティパス数ｃ（ｉ，ｊ，λｋ）が隣接マトリックス
【数３】
2011517220.tif 000005
から取得される。本明細書で使用される「リンクダイバーシティパス」という用語は、２つのボーダーノード間にどのような共有リンクもないパスを指す。
【００２７】
ある実施形態では、２つのボーダーノード間のリンクダイバーシティパス数を計算することは、２つのボーダーノード間のリンクダイバーシティパス数がキャナルネットワーク内の送信元と宛先との間の最大フローと等しいので、２つのボーダーノード間の最大フローを計算することになる。したがってこの実施形態では、２つのボーダーノード間のリンクダイバーシティ数は、最大フローアルゴリズムを利用することによって２つのボーダーノードの間の最大フローを計算することによって算出される。
【数４】
2011517220.tif 000006
ある実施形態では、２つのボーダーノード間の最大フローは既存の最高レベルプリフロープッシュアルゴリズムを利用することによって計算される。代替実施形態では、２つのボーダーノード間の最大フローは拡大パスアルゴリズムを使用して計算される。
【００２８】
次いでステップ２４０で、リンクダイバーシティパス数ｃ（ｉ，ｊ，λｋ）を使用することによって接続性マトリックスＣが取得されて、対応するフルメッシュトポロジＧＢが構築される。
この場合、
【数５】
2011517220.tif 000007
上式で、Ｍ＝Ｎ（Ｎ−１）／２、ＶＢ＝｛ｖ１，ｖ２，…，ｖＮ｝、ＥＢ＝｛ｅ１，ｅ２，…，ｅＭ｝、ｅ（ｉ，ｊ，λｋ）＝ｃ（ｉ，ｊ，λｋ）。
【００２９】
上記の実施形態から、本発明の接続性マトリックスＣは式（１）に示された従来の接続性マトリックスとは異なることが分かる。本発明の接続性マトリックスは、０および１によって表される代わりに２つのボーダーノード間のリンクダイバーシティパス数によって表される。リンクダイバーシティパス数を使用して接続性マトリックスＣを構築することによって、利用可能な波長についての情報が提供されるだけでなく、その波長についてのリソース情報も提供される。したがって、最適なパスの選択を助けるために使用できる情報が豊富であるほど、ますますパフォーマンスが向上されうる。たとえば接続が設定される場合、より多くのリソースを有し、枯渇する可能性がより少ない波長を使用することが好ましい。
【００３０】
他の好ましい実施形態では、よりまばらなトポロジを取得するために結果として得られるフルメッシュトポロジがさらに圧縮されて、ドメイン間で交換されるべき情報の量がさらに減少される。
【００３１】
図３は、本発明の実施形態によるトポロジ圧縮処理の流れ図を示している。図３に示されるように、ステップ３１０で全てのノードがｎｕｌｌである双方向シャッフルネットトポロジを取得するためにフルメッシュトポロジについて双方向シャッフルネット構築が実行される。
【００３２】
従来のシャッフルネット（Ｐ，Ｋ）トポロジは、Ｋ列およびＰＫ行に配置されたＮ’＝ＫＰＫノード（Ｐ，Ｋ＝１、２、…）を有するネットである。特に、それぞれの列内のそれぞれのノードは次の列内のノードへのＰ直接リンクを有し、最後の列内のノードも最初の列内のノードにリンクしているので、シリンダトポロジが形成される。すなわち、ノード（１，ｎ）（１＝０、１、…、ＰＫ−１、ｎ＝０、１、…、Ｋ−１）は、次の列内の（１’，ｎ’）、（１’，ｎ’＋１）、…、（１’，ｎ’＋Ｐ−１）へのＰ直接リンクを有し、上式で１’＝１  ｍｏｄ  ＰＫ−１、ｎ’＝（ｎ＋１）  ｍｏｄ  Ｋである。双方向シャッフルネットトポロジはシャッフルネットの拡張バージョンである。双方向シャッフルネットトポロジは、そのリンクが全て双方向である点で、すなわちそれぞれの列内のそれぞれのノードが次の列内のノードへのＰリンクを有するだけでなく前のコラム内のノードへのＰリンクも有するという点で、従来のシャッフルネットトポロジとは異なる。
【００３３】
図４は双方向シャッフルネットトポロジの例を示しており、ここではＫ＝２、Ｐ＝２、Ｎ’＝８である。図示されたように、２つの列および４つの行に８つのノードが配置されている。それぞれの列内のそれぞれのノードは、それぞれ次および前の列への２つのリンクを有している。双方向シャッフルネットトポロジがあれば、論理リンク数をＰＮ’に減少させることができ、これはＮ２の次数であるフルメッシュトポロジの論理リンク数よりも著しく減少しており、その結果氾濫されるべきリンク情報の量を減少させてシグナリングネットワークの負荷を軽減する。
【００３４】
以下では、図５を参照して本発明の双方向シャッフルネットトポロジ構成の処理を詳細に説明する。
【００３５】
図５に示されるように、まずステップ５１０でフルメッシュトポロジのために双方向シャッフルネットトポロジのパラメータＫおよびＰが計算され、この場合ＫおよびＰは以下の式によって解くことができる：
Ｍａｘ｛（Ｋ−１）ＰＫ−１，Ｋ（Ｐ−１）Ｋ｝＜Ｎ≦ＫＰＫ（Ｋ，Ｐ≧２）  式（７）
上式でＮはフルメッシュトポロジ内のノードの数、すなわちリアルトポロジ内のボーダーノードの数である。
【００３６】
次にステップ５２０で、初期化された双方向シャッフルネットトポロジを取得するために、式（７）から取得されたパラメータＫおよびＰを利用することによって双方向シャッフルネットトポロジが初期化される。
【００３７】
Ｇ’＝（Ｖ’，Ｅ’）  式（８）
上式でＶ’は双方向シャッフルネットトポロジ内のノードのセットであり、すなわちＶ’＝｛ｖ’１，ｖ’２，…，ｖ’Ｎ’｝であり、Ｅ’は双方向シャッフルネットトポロジ内のリンクのセットであり、すなわち、Ｅ’＝｛ｅ’１，ｅ’２，…，ｅ’Ｍ’｝、ｅ’１＝｛λ’１，λ’２，…，λ’Ｗ｝であり、Ｎ’＝ＫＰＫ、Ｍ’＝ＫＰＫ＋１、Ｖ’⊇ＶＢ、およびＥ’⊆ＥＢである。
【００３８】
図３に戻ると、ステップ３２０で、あるマッピング関係を用いてフルメッシュトポロジ内のノードがシャッフルネット内のノードにマッピングされ、対応する論理リンク属性がシャッフルネット内の双方向リンクに伝えられる。
【００３９】
図６は本発明の実施形態による双方向シャッフルネットトポロジを最適化する処理の流れ図を示している。この実施形態では、双方向シャッフルネットトポロジを最適化するために遺伝的アルゴリズム（ＧＡ）が使用される。
【００４０】
図示されるように、ステップ６１０でフルメッシュトポロジのノードが双方向シャッフルネットトポロジ内に配置される方法を表すことができるいくつかの染色体を含む双方向シャッフルネットトポロジの第１世代Ｐ０がまず取得される。ある実施形態では、染色体を構築するために１次元リテラル順列符号化が使用される。たとえば第１世代Ｐ０の染色体はＮ’ノードをランダムに並べ替えることによって取得されうる：
ｐ＝ランダム順列（１，２，…，Ｎ’）  ｐ∈Ｐ０  式（９）
【００４１】
ノードの数が７であるフルメッシュトポロジを例にとると、前述の初期化操作によってＫ＝２、Ｐ＝２、およびＮ’＝８である双方向シャッフルネットトポロジが取得される。ランダムに生成された染色体「７  ２  ３  １  ５  ６  ４  ８」については、フルメッシュトポロジのそれぞれのノードが双方向シャッフルネット内に配置される順序を表し（ノード８は不足を補うために満たされる仮想ノードである）、すなわち図７に示されるように、フルメッシュトポロジ内のノード７は双方向シャッフルネット内のノード（０，０）に対応し、ノード２はノード（１，０）に対応し、…、ノード４はノード（２，１）に対応し、仮想ノード８はノード（３，１）に対応する。
【００４２】
本発明における染色体は、通常０−１ビット列からなる染色体とは異なることが分かる。本発明はそれぞれの遺伝子がノード番号である１次元リテラル順列符号化を利用する。したがって本発明の染色体への変異操作は、通常は染色体内の遺伝子の位置を変更する位置ベースであり、したがって確実に次世代が大部分の特性を親から受け継ぐことができ、互換性のある遺伝子が保存される。
【００４３】
次にステップ６２０で、それぞれの染色体ｐに従ってフルメッシュトポロジＧＢの全てのノードＶＢが双方向シャッフルネットトポロジＧ’のノードＶ’にマッピングされた後、ノード位置に従って論理リンクのマッピングが実行されうる。前述の双方向シャッフルネットトポロジのように、ノード７はノード４、５、および６に接続されており、したがって双方向論理リンク（４，７）、（５，７）、（６，７）が保存され、ノード７に接続されている他の論理リンクは全て削除される。ノード８は仮想ノードであり、論理リンクのマッピングに参加しない。それぞれの染色体を評価するために、双方向シャッフルネットトポロジＧ’の対応する接続性マトリックスＣ’を取得することができる。
【００４４】
Ｃ’＝［ｃ’（ｉ，ｊ，λｋ）］Ｎ×Ｎ×Ｗ  式（１０）
【００４５】
接続性マトリックスＣ’は接続性マトリックスＣを取得するのと同様の方法で取得されうる。
【００４６】
ステップ６３０で、次いでリアルトポロジのボーダーノードの接続性マトリックスを目的関数としてそれぞれの染色体の適合値が取得される：
【数６】
2011517220.tif 000008
上式で、
【数７】
2011517220.tif 000009
【００４７】
式（１１）で、適合値はフルメッシュトポロジの接続性マトリックスと染色体のトポロジの接続性マトリックスとの間の近似度を表し、その値は偏位度の合計の逆である。マイナスは偏差値が小さいほどそれだけ適合値が大きいことを表す。偏差値は、染色体のトポロジの接続性マトリックスと目標接続性マトリックスとの間の合計との差異の割合の絶対値でありうる。代替実施形態では、偏差値は染色体のトポロジの接続性マトリックスと目標接続性マトリックスとの間の差異の絶対値である。
【００４８】
次にステップ６４０で、次世代遺伝子の染色体を取得するために取得された適合値に基づいて遺伝子操作を実行する。ある実施形態では、次世代を繁殖させるための染色体を取得するために、まず取得された適合値に基づいて現在の世代の染色体に選択操作が実行される。すなわち適合値が低い染色体（たとえば適合値がしきい値より低い）は淘汰され、適合値がより高い染色体だけが次世代へと選択される。次世代の染色体を取得するために、選択された染色体にクロスオーバおよび変異操作が実行される。図８は、本発明の実施形態によるクロスオーバおよび変異操作の例を示している。本発明は図８に示されたクロスオーバおよび変異操作に限定されないことを理解されたい。
【００４９】
次いでステップ６５０で、反復の数があらかじめ定められたしきい値に達したかどうかが決定される。答えがはいの場合、ステップ６６０で最も良い適合度を有する結果として得られる染色体が最適化の結果と見なされ、すなわち最適化された双方向シャッフルネットトポロジが取得される。答えがいいえの場合、処理はステップ６２０に進み反復を続ける。
【００５０】
他の実施形態では、反復の数についてのあらかじめ定められたしきい値に達する前に染色体の適合値があらかじめ定められたしきい値に達すると遺伝子操作は終了され、取得された染色体に従ってノードが配置および接続された双方向シャッフルネットトポロジが結果として得られたトポロジと見なされる。
【００５１】
反復の数はニーズに基づいて決定されうる。反復の数が多いほど、それだけ取得される結果が良いが、計算するためにより多くの時間を要する。
【００５２】
発明者は、それぞれの世代の平均偏差が初期段階で迅速に減少して、約２０世代後に安定値に達することを確認した。その後、平均偏差は一定の範囲内で変動する。３０世代後の平均偏差は実質的に２０％未満であり、最適個別偏差は実質的に約１０％である。本発明のトポロジ集約方法がより正確なトポロジを達成でき、したがってルーティング決定のためのより正確で豊富な情報を提供でき、したがってパフォーマンスを向上できることが分かる。
【００５３】
さらに、双方向シャッフルネットトポロジを最適化するために、発見的アルゴリズムなどの当業者に知られている他の適切なアルゴリズムも使用されうる。
【００５４】
図３から８を参照して、説明から、本発明のトポロジ集約方法は光ネットワークにとって適切な詳細なリンク情報を提供することが分かる。より詳細には、双方向シャッフルネットトポロジを最適化するために遺伝的アルゴリズムを使用することにより、より少ない論理リンクを使用してより正確なトポロジ構成が説明され、したがってパフォーマンスが向上される。
【００５５】
他の代替実施形態では、フルメッシュトポロジ内のより多くのリンクダイバーシティパス数を有するノードが、フルメッシュトポロジの取得された接続性マトリックスを使用してシャッフルネットトポロジに直接接続されたノード内にマッピングされ、その結果発見的手法を使用してフルメッシュトポロジを双方向シャッフルネットトポロジに圧縮する。
【００５６】
他の代替実施形態では、フルメッシュトポロジの取得された接続性マトリックスを利用することによって、フルメッシュトポロジは対称的スター型トポロジに圧縮される。
【００５７】
ネットワーク状態が変化すると、たとえばリンクの帯域幅利用可能性が変化すると、通知された集約トポロジをアップデートするために再集約操作が実行される必要がある。
【００５８】
本発明のある実施形態では、再集約はあらかじめ定められた時間間隔に基づいて実行されうる。この実施形態では、再集約時間間隔はあらかじめ定められており、再集約はイントラドメイン内のリンクの帯域幅変更状態にかかわらず、あらかじめ定められた時間間隔に基づいて定期的に実行されうる。
【００５９】
本発明の他の実施形態では、イベントベースの再集約ポリシーが採用され、すなわち再集約はあらかじめ定められたイベントが発生するときにのみ実行される。怠惰な再集約ポリシーが使用されうること、すなわち大きなトポロジ変更が発生するか、接続拒否率があらかじめ定められたしきい値に達するときにのみ再集約が実行されることが好ましい。
【００６０】
ある実施形態では、あらかじめ定められた接続拒否率に達したときに再集約が実行される。一例として、あらかじめ定められた再集約時間間隔の間、接続拒否率ｒがあらかじめ定められたしきい値αを超えると再集約がすぐに実行され、この場合αは顧客のＱｏＳ要求に基づく定数、たとえば２０％である。
【００６１】
他の例では、トポロジが大きく変化するときに再集約が実行される。この実施形態では、リンク容量はＢチャネルであり、時間ｔに利用可能なチャネルの数はｃｔと仮定される。時間ｔに利用可能なチャネルの数ｃｔがあらかじめ定められた値シーケンスｂｋ内の値と等しい場合、再集約が実行される。
【００６２】
実施形態では、あらかじめ定められた値シーケンスｂｋは以下のように構築される：ｂｋ＝｛０，Ｌａ｝、すなわち利用可能なチャネルの数ｃｔが０かＬａのときに再集約が実行される。
【００６３】
他の実施形態では、あらかじめ定められた値シーケンスｂｋはより多くの要素を有するので、トポロジ再集約は利用可能チャネルがより多い場合はより低い頻度で発生し、利用可能チャネルがより少ない場合はより高い頻度で発生する。たとえば、あらかじめ定められた値シーケンスｂｋは以下の式によって取得されうる：
【数８】
2011517220.tif 000010
上式で、Ｋは最も大きい指数なのでＬａ＞１の場合はｂｋ＜Ｂ、およびＬａ＝１の場合はｂｋ＝ｋである。たとえば、それぞれの論理リンク上に１６のチャネルがある場合、Ｌａ＝２の場合はあらかじめ定められた値シーケンスはｂｋ＝｛０，２，４，６，１０，１６｝であり、Ｌａ＝３の場合はｂｋ＝｛０，３，６，１２，１６｝であり、Ｌａ＝４の場合はｂｋ＝｛０，４，８，１６｝である。前述の式は単なる例であり、あらかじめ定められた値シーケンスｂｋを取得するために他の方法が使用されうる。
【００６４】
本発明の再集約ポリシーによれば、再集約は大きなトポロジ変更が発生するときにのみ実行され、トポロジ変更が小さいときには実行されない。したがって集約トポロジが時間内にアップデートされることを保証する場合、再集約の数が減少され、その結果、再集約の実装のために消費されるリソースを減少させてパフォーマンスを向上させる。
【００６５】
上記の説明から、本発明が利用可能な波長についての利用可能性情報だけでなく、波長についてのリソース豊富情報も提供する「リンクダイバーシティパス数」を利用することによって接続性マトリックスを構築するので、その結果ルーティング決定がソース割当てを最適化できるようにより詳細なリンク情報が提供されて、ネットワークパフォーマンスを向上させることが分かる。好ましい実施形態では、取得されたフルメッシュトポロジはさらに圧縮されて、その結果ドメイン間で交換されるべき情報の量を減少させてパフォーマンスをさらに向上させる。好ましい実施形態では、フルメッシュトポロジは双方向シャッフルネットトポロジに圧縮されてリンクの数を著しく減少させ、その結果ドメイン間で交換される必要があるルーティング情報の量を減少させてパフォーマンスを向上させる。他の好ましい実施形態では、イベントベースの怠惰な再集約ポリシーを利用することによって再集約が実行され、その結果、再集約の実装のために消費されるリソースを減少させてパフォーマンスを向上させる。
【００６６】
次に、本発明のトポロジ集約のための装置を以下でさらに説明する。
【００６７】
図９は、本発明の実施形態によるトポロジ集約のための装置９００を示している。図９に示されるように、トポロジ集約のための装置９００は、リアルトポロジ内のボーダーノードのそれぞれの対の間のリンクダイバーシティパス数ｃ（ｉ，ｊ，λｋ）を取得するように構成されたリンクダイバーシティパス数取得手段９１０、およびリンクダイバーシティパス数ｃ（ｉ，ｊ，λｋ）を使用することによって接続性マトリックスＣを取得して、対応するフルメッシュトポロジＧＢを構築するように構成されたトポロジ構築手段９２０を含む。
【００６８】
リンクダイバーシティパス数取得手段９１０は、ステップ２１０−２３０に関する上記の説明に従って操作できる：まず隣接マトリックスがドメインのリアルトポロジから計算され、次いでボーダーノード間の最大フローを計算することによってボーダーノード間のリンクダイバーシティパス数が取得される。リンクダイバーシティパス数を計算する場合、最高レベルプリフロープッシュアルゴリズム、拡大パスアルゴリズム、および当業者に知られている他のアルゴリズムが使用されうる。
【００６９】
トポロジ構築手段９２０はステップ２４０に関する上記の説明に従って操作できる：リンクダイバーシティパス数取得手段９１０によって取得されたリンクダイバーシティパス数を使用して接続性マトリックスが構築される。
【００７０】
上記の実施形態から、本発明のトポロジ集約のための装置９００がリンクダイバーシティパス数を使用して接続性マトリックスを構築し、利用可能な波長についての情報だけではなく波長の豊富度についてのリソース情報も提供し、その結果ルート選択を容易にしてパフォーマンスを向上させることが分かる。
【００７１】
好ましい実施形態では、トポロジ集約のための装置９００はフルメッシュトポロジを圧縮するように構成されたトポロジ圧縮手段９３０をさらに含み、その結果ドメイン間で交換されるべき情報の量をさらに減少させる。
【００７２】
図１０に示されるように、ある実施形態ではトポロジ圧縮手段９３０は、双方向シャッフルネットトポロジの決定された構造パラメータを使用して双方向シャッフルネットトポロジを初期化するように構成された双方向シャッフルネットトポロジ構築手段９３２、およびフルメッシュトポロジの接続性マトリックスを使用して双方向シャッフルネットトポロジを最適化するように構成された双方向シャッフルネットトポロジ最適化手段９３４を含む。
【００７３】
双方向シャッフルネットトポロジ最適化手段９３４は、遺伝的アルゴリズムに基づいて双方向シャッフルネットトポロジをさらに最適化できる。図１１は、遺伝的アルゴリズムに基づく双方向シャッフルネットトポロジ最適化手段９３４の実施形態を示している。双方向シャッフルネットトポロジ最適化手段９３４は、双方向シャッフルネットトポロジの第１世代をランダムに取得するように構成された第１世代生成手段９３４２と、現在の世代の染色体の接続性マトリックスを取得するように構成された接続性マトリックス取得手段９３４４と、リアルトポロジのボーダーノードの接続性マトリックスを目的関数として使用して現在の世代のそれぞれの染色体の適合値を計算するように構成された適合値計算手段９３４６と、適合値に基づいて現在の世代における染色体に遺伝子操作を実行して、次世代の染色体を取得するように構成された遺伝子操作手段９３４８であって、遺伝子操作が選択操作、変異操作、クロスオーバ操作などを含む遺伝子操作手段９３４８と、遺伝子操作を終了させる条件が満たされるときにフルメッシュトポロジのノードおよび論理リンクを結果として得られる最適化された染色体を利用して双方向シャッフルネットトポロジにマッピングするように構成されたマッピング手段９３５０とを含む。さらに、双方向シャッフルネットトポロジを最適化するために、発見的アルゴリズムなどの当業者に知られている他の適切なアルゴリズムも使用されうる。
【００７４】
ある実施形態では、適合値計算手段９３４６によって計算された適合値は前記現在の世代の染色体の接続性マトリックスとリアルトポロジのボーダーノードの接続性マトリックスとの間の差異の絶対値である。一方他の実施形態では、適合値は前記現在の世代の染色体の接続性マトリックスとリアルトポロジのボーダーノードの接続性マトリックスとの間の合計との差異の割合の絶対値である。
【００７５】
ある実施形態では、遺伝子操作を終了させる条件は、反復の数があらかじめ定められた値を超えること、または適合値があらかじめ定められた値に達することである。
【００７６】
ある実施形態では、染色体は１次元リテラル順列符号化に基づく。
【００７７】
上記の実施形態から、論理リンクの数が著しく減少され、遺伝的アルゴリズムを利用して双方向シャッフルネットトポロジをさらに最適化することによってより正確なトポロジ構造が提供され、その結果パフォーマンスを向上させることが分かる。
【００７８】
好ましい実施形態では、図１２に示されるように、トポロジ集約のための装置９００は、ネットワーク状態が変化するときにトポロジの再集約をトリガするように、またはあらかじめ定められた時間間隔に基づいてトポロジの再集約をトリガするように構成された再集約トリガ手段９４０をさらに含む。ある実施形態では、怠惰な再集約ポリシーに基づいて、あらかじめ定められたトポロジ変更イベントが発生するか、接続拒否率があらかじめ定められたしきい値に達するときに再集約トリガ手段９４０が再集約をトリガする。あらかじめ定められたトポロジ変更イベントは、利用可能なリソースの量があらかじめ定められた値に増加または減少するイベントであってよく、再集約は利用可能なリソースがより多い場合はより低い頻度で発生し、利用可能なリソースがより少ない場合はより高い頻度で発生する。
【００７９】
その他に、本発明はルーティングコントローラも提供する。図１３は、本発明の実施形態によるルーティングコントローラの概略図を示している。図１３に示されるように、ルーティングコントローラ１３００は、１つのドメインのリアルトポロジを取得するためのリアルトポロジ取得手段１３１０、１つのドメインのリアルトポロジを集約するための本発明のトポロジ集約のための装置９００、およびトポロジ集約のために装置９００によって取得されたトポロジに基づいてリンクステート（ＬＳＡ）情報を生成して、そのＬＳＡ情報を送出するためのリンクステート送信手段１３２０を含む。ルーティングコントローラ内のトポロジ集約のための装置９００がリンクダイバーシティパス数を使用して接続性マトリックスを構築し、利用可能な波長についての情報だけではなく波長についてのリソース情報も提供し、その結果ルート選択を容易にしてパフォーマンスを向上させる。
【００８０】
図１４は、本発明の実施形態によるルーティングコントローラの開始段階処理の流れ図を示している。図１４に示されるように、ルーティングコントローラが操作を開始後、ステップ１４１０でリアルトポロジ取得手段がまず１つのドメインのリアルトポロジを取得する。ステップ１４２０で、次いでトポロジ集約のための装置がリアルトポロジを集約する。次にステップ１４３０で、リンクステート送信手段が集約されたトポロジに基づいてＬＳＡ情報を生成して、そのＬＳＡ情報を送出する。
【００８１】
作動段階では、再集約条件が満たされるときにトポロジ集約のための装置が再集約をトリガすることになる。再集約はネットワーク状態が変化するときにトリガされてもよく、あらかじめ定められた時間間隔に基づいてトリガされてもよい。ある実施形態では、怠惰な再集約ポリシーに基づいて、あらかじめ定められたトポロジ変更イベントが発生するか、接続拒否率があらかじめ定められたしきい値に達するときに再集約がトリガされる。その他に、あらかじめ定められたトポロジ変更イベントは、利用可能なリソースの量があらかじめ定められた値に増加または減少するイベントであってよく、またあらかじめ定められたイベントは、利用可能なリソースがより多い場合はより低い頻度で発生し、利用可能なリソースがより少ない場合はより高い頻度で発生する。
【００８２】
図１５は、本発明の実施形態によるルーティングコントローラの作動段階処理の流れ図を示している。
【００８３】
図１５に示されるように、作動段階では、要求メッセージが受信されるとステップ１５０１でその要求が接続設定要求か接続解除要求かがまず決定される。要求メッセージが接続設定要求の場合、処理はステップ１５０２に進む。
【００８４】
ステップ１５０２で指定された入口ノードと出口ノードとの間のリソースが検査され、指定された入口ノードと出口ノードとの間に接続要求をサポートするための十分なリソースがないことを検査が示すと、処理はステップ１５０４に進む。ステップ１５０４でメッセージが要求者に送信されて、要求者に要求の失敗を通知する。次いでステップ１５０５で失敗数が１だけ増加されて、接続の拒否率すなわち失敗数／（失敗数＋成功数）が計算される。
【００８５】
次にステップ１５０６で拒否率があらかじめ定められた拒否率のしきい値に達するかどうかが決定される。あらかじめ定められたしきい値に達する場合、次いでステップ１５１３で再集約がトリガされてトポロジ再集約が実行される。この後ステップ１５１４で接続の成功および失敗のカウントがリセットされて、再びカウントされる。次いでステップ１５１５で再集約されたトポロジに基づいてＬＳＡが生成されて送出される。このようにして要求のための処理が終了する。
【００８６】
一方、ステップ１５０２で指定された入口ノードと出口ノードとの間に接続要求をサポートするための十分なリソースがあることを検査が示すと、処理はステップ１５０７に進む。ステップ１５０７で要求が次のドメインに送信されて、接続設定指示が待たれる。指示を受信後、ステップ１５０８でイントラ選択されたリンクに沿って波長が割り当てられて、接続が設定される。この後、ステップ１５０９で接続の成功数が１だけ増加される。次いでステップ１５１０でＬＳＡ情報を送信するために再フラッディングがトリガされる。ステップ１５１１で入口ノードと出口ノードとの間の残りのリソースが検査され、ステップ１５１２で残りのリソースの量が再集約のあらかじめ定められたしきい値Ｌａに達するかどうかが決定される。しきい値Ｌａに達すると、処理はステップ１５１３に進んで再集約を実行する。この後、ステップ１５１４で接続の成功および失敗のカウントがリセットされる。次いで処理はステップ１５１５に進み、要求のための処理が終了する。しきい値Ｌａにまだ達しない場合、次いで要求のための処理は直接終了する。
【００８７】
ステップ１５０１で、要求が接続解除要求の場合、処理はステップ１５０３に進む。このステップで接続が解除される。その後処理はステップ１５１０に進み、処理が終了するまで上述したステップが実行される。
【００８８】
本発明の実装に必要な場合がある当業者に知られているより具体的な技術詳細は、本発明をよりよく理解するために上記の説明では省略されている点に留意されたい。
【００８９】
例示および説明のために仕様が提供されるが、これは網羅的なものでも本発明を開示された形式に限定するものでもない。当業者には様々な修正および変更は明らかであろう。
【００９０】
したがって、本発明の原理および本発明の実際の適用を最もよく説明するために、ならびに本発明の趣旨から逸脱することなしに行われた全ての修正および変更は添付の特許請求の範囲で定義される本発明の保護範囲内に入ることを当業者が理解できるようにするために、実施形態を選択して説明した。
【図１】
2011517220.tif 000011
【図２】
2011517220.tif 000012
【図３】
2011517220.tif 000013
【図４】
2011517220.tif 000014
【図５】
2011517220.tif 000015
【図６】
2011517220.tif 000016
【図７】
2011517220.tif 000017
【図８】
2011517220.tif 000018
【図９】
2011517220.tif 000019
【図１０】
2011517220.tif 000020
【図１１】
2011517220.tif 000021
【図１２】
2011517220.tif 000022
【図１３】
2011517220.tif 000023
【図１４】
2011517220.tif 000024
【図１５】
2011517220.tif 000025
【手続補正書】
【提出日】平成22年10月13日(2010.10.13)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
リアルトポロジＧＲ内のそれぞれの１対のボーダーノード間のリンクダイバーシティパス数ｃ（ｉ，ｊ，λｋ）を取得するステップと、
前記リンクダイバーシティパス数ｃ（ｉ，ｊ，λｋ）を利用することによって接続性マトリックスＣを取得して、対応するフルメッシュトポロジＧＢを構築するステップとを含む、トポロジ集約のための方法。
【請求項２】
前記リンクダイバーシティパス数がボーダーノード間の最大フローを計算することによって取得される、請求項１に記載の方法。
【請求項３】
ボーダーノード間の最大フローを計算するステップが最高レベルプリフロープッシュアルゴリズムを利用することによって実行される、請求項２に記載の方法。
【請求項４】
前記フルメッシュトポロジへのトポロジ圧縮を実行するステップをさらに含む、請求項１に記載の方法。
【請求項５】
前記トポロジ圧縮を実行するステップが、
双方向シャッフルネットトポロジの構造パラメータを決定するステップと、
前記構造パラメータを利用することによって前記双方向シャッフルネットトポロジを初期化するステップと、
前記接続性マトリックスを利用することによって前記双方向シャッフルネットトポロジを最適化するステップとを含む、請求項４に記載の方法。
【請求項６】
前記双方向シャッフルネットトポロジを最適化するステップが遺伝的アルゴリズムに基づき、
前記双方向シャッフルネットトポロジの第１世代をランダムに取得するステップと、
現在の世代の染色体のトポロジの接続性マトリックスを取得するステップと、
リアルトポロジのボーダーノードの接続性マトリックスを目的関数として使用して現在の世代の染色体ごとに適合値を計算するステップと、
前記適合値に基づいて現在の世代のそれぞれの染色体に遺伝子操作を実行して次世代の染色体を取得するステップと、
染色体のトポロジの接続性マトリックスを取得し、適合値を計算し、かつ遺伝子操作を実行する操作を、遺伝子操作を終了させる条件が満たされるまで反復するステップと、
最適化された双方向シャッフルネットトポロジを取得するために、結果として得られる染色体を利用することによってフルメッシュトポロジのノードを双方向シャッフルネットトポロジにマッピングするステップとを含む、請求項５に記載の方法。
【請求項７】
前記適合値がそれぞれの偏差値の合計の逆であり、前記それぞれの偏差値が染色体のトポロジの接続性マトリックスと前記フルメッシュトポロジの接続性マトリックスとの間の合計との差異の割合の絶対値である、請求項６に記載の方法。
【請求項８】
遺伝子操作を終了させる条件が反復の数があらかじめ定められた値に達することである、請求項６に記載の方法。
【請求項９】
前記染色体が１次元リテラル順列符号化を利用する、請求項６に記載の方法。
【請求項１０】
ネットワーク状態が変化するときにトポロジの再集約を実行するステップをさらに含む、請求項１に記載の方法。
【請求項１１】
トポロジの再集約が怠惰な再集約ポリシーに基づき、あらかじめ定められたトポロジ変更イベントが発生するか、接続拒否率があらかじめ定められたしきい値に達するときに実行される、請求項１０に記載の方法。
【請求項１２】
前記あらかじめ定められたトポロジ変更イベントが利用可能なリソースの量があらかじめ定められた値になるイベントであり、前記あらかじめ定められたトポロジ変更イベントが、利用可能なリソースがより多い場合はより低い頻度で発生し、利用可能なリソースがより少ない場合はより高い頻度で発生する、請求項１１に記載の方法。
【請求項１３】
リアルトポロジＧＲ内のそれぞれの１対のボーダーノード間のリンクダイバーシティパス数ｃ（ｉ，ｊ，λｋ）を取得するように構成されたリンクダイバーシティパス数取得手段と、
前記リンクダイバーシティパス数ｃ（ｉ，ｊ，λｋ）を使用することによって接続性マトリックスＣを取得して、対応するフルメッシュトポロジＧＢを構築するように構成されたトポロジ構築手段とを備える、トポロジ集約のための装置。
【請求項１４】
請求項１３に記載のトポロジ集約のための装置と、
トポロジ集約のための装置によって取得されたトポロジに基づいてリンクステート（ＬＳＡ）情報を生成して、前記ＬＳＡ情報を送出するように構成されたリンクステート送信手段とを備える、ルーティングコントローラ。
【国際調査報告】
2011517220.tif 000026
2011517220.tif 000027
2011517220.tif 000028
2011517220.tif 000029