(57)【特許請求の範囲】
【請求項１】
ノードおよびリンクから成るネットワークを構成または再構成する方法において、前記リンクの少なくともあるものは、１つより多くの独立サブリンクを含み、前記独立サブリンクは、所定の品質により識別可能であり且つ前記リンク内の他のサブリンクとは無関係に信号を搬送することができ、１つより多くの独立サブリンクを含む前記リンクに接続された前記ノードは、それぞれの独立サブリンクが前記ノードにおいて成端され、または別の独立サブリンクへ伝送されるように少なくともセットされることができ、前記方法は、
辺がサブリンクを表し、平行辺が前記サブリンクを含むリンクを表し、頂点および辺がノードを表すグラフを定めるステップと、
第１の所定の基準により、それぞれのノードにおけるそれぞれの辺に伝送および成端のための初期の重みをそれぞれ割当てるステップと、
第２の所定の基準により第１のノード対を選択するステップと、
前記第１のノード対の間に特定の経路を形成する前記独立サブリンクの系列を決定するステップであって、前記特定の経路が前記第１のノード対の間の他の可能な経路に対する第３の所定の基準を満たし、前記第３の所定の基準が経路に沿っての前記辺の前記重みに関連する経路を決定するためのものである前記決定するステップと、
前記特定の経路を形成する前記辺に割当てられた前記重みを前記経路に沿ったそれぞれのノードにおいて前記経路のそれぞれの辺について更新するステップであって、
−  前記経路内の前記ノードを経て特定の辺へ伝送される辺に割当てられ、前記特定の辺への伝送のための前記重みが伝送のための前記初期の重みに対し減少され、
−  前記経路内の前記ノードにおいて成端される辺に割当てられる伝送のための前記重みが伝送のための前記初期の重みに対し増加され、
−  前記経路内の前記ノードを経て伝送される辺に割当てられる成端のための前記重みが成端のための前記初期の重みに対し増加され、
−  前記経路内の前記ノードにおいて成端される辺に割当てられる成端のための前記重みが成端のための前記初期の重みに対し減少される、
前記更新するステップと、
前記第１の基準に従い前記第１のノード対と異なる別のノード対を選択し、かつ、経路を決定し、前記重みを更新し、さらなるノード対を選択する前記プロセスを第４の所定の基準が満たされるまで繰返すステップと、
を含む前記方法。
【請求項２】
前記ネットワークは、光ネットワークである請求項１記載の方法。
【請求項３】
前記ネットワークは、空間分割多重化ネットワークであり、前記所定の品質は、空間的位置である請求項２記載の方法。
【請求項４】
前記ネットワークは、波長分割多重化ネットワークであり、前記所定の品質は、波長である請求項２記載の方法。
【請求項５】
前記第１の基準により、同じ品質のサブリンクに対応する辺への伝送のための前記初期の重みは、成端のための前記初期の重みより小さく、同じ品質のサブリンクに対応する辺への伝送のための前記初期の重みは、異なる品質のサブリンクに対応する辺への伝送のための前記初期の重みより小さい請求項１記載の方法。
【請求項６】
成端のための前記初期の重みと、異なる品質のサブリンクに対応する辺への伝送のための前記初期の重みとは、同じである請求項５記載の方法。
【請求項７】
前記第２の基準により、ノード対の前記選択は、ノードの間の平均トラヒック需要に依存し、最大トラヒック需要を有するノード対がまず選択され、その後、トラヒック需要が減少していく順序で、さらなるノード対は、選択される請求項１記載の方法。
【請求項８】
前記第２の基準により、ノード対の前記選択は、ランダムにおこなわれる請求項１記載の方法。
【請求項９】
前記第２の基準により、ノード対の前記選択は、ノードの間の距離に依存して行われ、最短距離を有するノード対がまず選択され、その後、距離が増加していく順序で、さらなるノード対は、選択され、前記距離は、前記ノードの間の物理的距離とホップの数との一方である請求項１記載の方法。
【請求項１０】
前記第２の基準により、ノード対の前記選択は、ノードの間のトラヒック需要と距離との関数に依存して行われ、前記距離は、前記ノードの間の物理的距離とホップの数との一方である請求項１記載の方法。
【請求項１１】
前記第３の基準により、前記特定の経路は、前記ノードの間の全ての可能な経路から最小の合計重みを有する経路として選択される請求項１記載の方法。
【請求項１２】
前記重みを更新するステップにおいて
−  前記経路内の前記ノードを経て特定の辺へ伝送される辺へ割当てられ、前記特定の辺への伝送のための前記重みは、ゼロまで減少され、
−  前記経路内の前記ノードにおいて成端される辺に割当てられる伝送のための前記重みは、数値的に実現可能な無限大に相当する値まで増加され、
−  前記経路内の前記ノードを経て伝送される辺に割当てられる成端のための前記重みは、数値的に実現可能な無限大に相当する値まで増加され、
−  前記経路内の前記ノードにおいて成端される辺に割当てられる成端のための前記重みは、成端のための前記初期の重みとゼロとの間の値まで減少される、
請求項１記載の方法。
【請求項１３】
前記第４の基準により、前記プロセスは、それぞれの可能なノード対が考慮され終わるまで繰返される請求項１記載の方法。
【請求項１４】
前記第４の基準により、前記プロセスは、ノード対の所定の集合が考慮され終わるまで繰返される請求項１記載の方法。
【請求項１５】
与えられたノードの間に特定の経路を形成する独立サブリンクの系列を決定する前記ステップは、前記系列内のそれぞれのサブリンクが前記与えられたノードの間のトラヒック需要を処理するための十分大きい伝送容量を有する前記系列のみを決定するステップを含む請求項１記載の方法。
【請求項１６】
ノードおよびリンクから成るネットワークを構成または再構成する装置において、前記リンクの少なくともあるものは、１つより多くの独立サブリンクを含み、前記独立サブリンクは、所定の品質により識別可能であり且つ前記リンク内の他のサブリンクとは無関係に信号を搬送することができ、１つより多くの独立サブリンクを含む前記リンクに接続された前記ノードは、それぞれの独立サブリンクが前記ノードにおいて成端され、または別の独立サブリンクへ伝送されるように少なくともセットされることができる前記装置は、
辺がサブリンクを表し、平行辺が前記サブリンクを含むリンクを表し、頂点および辺がノードを表すグラフを定める手段と、
第１の所定の基準により、それぞれのノードにおけるそれぞれの辺に伝送および成端のための初期の重みをそれぞれ割当てる手段と、
第２の所定の基準により、第１のノード対を選択する手段と、
前記第１のノード対の間に特定の経路を形成する前記独立サブリンクの系列を決定する手段であって、前記特定の経路が前記第１のノード対の間の他の可能な経路に対する第３の所定の基準を満たし、前記第３の所定の基準が経路に沿って前記辺の前記重みに関連する経路を決定するためのものである前記決定する手段と、
前記特定の経路を形成する前記辺に割当てられた前記重みを前記経路に沿ったそれぞれのノードにおいて前記経路のそれぞれの辺について更新する手段であって、前記更新手段は、
−  前記経路内の前記ノードを経て特定の辺へ伝送される辺へ割当てられ、前記特定の辺への伝送のための前記重みが伝送のための前記初期の重みに対し減少され、
−  前記経路内の前記ノードにおいて成端される辺に割当てられる伝送のための前記重みが伝送のための前記初期の重みに対し増加され、
−  前記経路内の前記ノードを経て伝送される辺に割当てられる成端のための前記重みが成端のための前記初期の重みに対し増加され、
−  前記経路内の前記ノードにおいて成端される辺に割当てられる成端のための前記重みが成端のための前記初期の重みに対し減少される、
前記更新手段と、
前記第１の基準に従い前記第１のノード対と異なる別のノード対を選択し、かつ、経路を決定し、前記重みを更新し、さらなるノード対を選択する前記プロセスを第４の所定の基準が満たされるまで繰返す手段と、
を含む前記装置。
【発明の詳細な説明】
【０００１】
（発明の背景）
本発明は、ノードおよびリンクを含む通信ネットワークを構成および再構成する方法に関し、前記リンクの少なくともあるものは、２つのノード間の１つより多くの独立サブリンクを含んでいる。
【０００２】
この意味における独立サブリンクとは、２つのノード間のそれぞれのサブリンクが前記２つのノード間の他のサブリンクに沿って搬送される信号とは無関係に信号を搬送しうることを意味する。そのような通信ネットワークの例は、光ＷＤＭネットワーク（ＷＤＭ＝波長分割多重化）であり、ＷＤＭネットワークにおいては、リンクは、ノード間において光信号を搬送し、その場合、複数の波長が複数のサブリンクを定め、すなわち、それぞれの波長が独立して信号を搬送するように用いられる。この場合、サブリンクは、論理リンクである。もう１つの例は、光ＳＤＭネットワーク（ＳＤＭ＝空間分割多重化）であり、ＳＤＭネットワークにおいては、ケーブルに含まれる複数のファイバがリンクを構成し、それぞれのファイバが独立して信号を搬送する。この場合、サブリンクは、物理リンクである。
【０００３】
図１は、そのようなネットワークの簡単化された例を示す。ノード１、３、５および７は、リンク２、４および６により接続されている。１から７までのこの配置は、物理レベルにおけるトポロジを構成する。
【０００４】
上述の例においては、それぞれのリンクは、ａおよびｂにより、それぞれが示される２つのサブリンクを含む。それぞれのノードは、少なくとも２つの機能、すなわち、サブリンクの成端またはサブリンクの伝送を実行するようにセットされる。成端とは、そのノードにおいて対応する信号がネットワークから抽出されるという意味において、サブリンクがそのノードにおいて終了するように、そのノードがセットされることを意味し、一方、伝送とは、サブリンクが成端されないようにセットされることを意味する。換言すれば、伝送とは、入力信号が必然的にそのノードにより出力されることを意味し、一方、成端とは、信号がネットワークから除去されうることを意味する。成端サブリンクからの信号は、そのネットワーク内へ再入力されるが、成端された前記サブリンクの状態を変化させるものではない。その理由は、そのサブリンクが伝送にセットされていたならば、そうなるように、その信号が必ず再びそのノードから出力されるようにはならないからである。むしろ、ネットワークからの信号の永久的除去および、例えば、そのノードの近くにあるその信号の宛先へのその信号のルーティング、または、そのノードにおけるネットワーク内への信号の再導入に存する成端サブリンクからの信号の処理は、瞬間的トラヒック制御の領域内にあり、一方、伝送または成端へのノードのセッティングは、瞬間的トラヒック制御の影響を受けない構成の領域内にあり、これらについては、さらに後述される。
【０００５】
例として、ＷＤＭネットワークにおいては、成端は、光信号がそのノードにおいて取出されて電気信号に変換され、かつ多重分離されてさらに処理されることを意味する。一方、伝送は、特定の波長でノードへ入来する光信号が必然的にノードから同じ波長または別の波長の出力信号として出力されることを意味する（波長偏移の可能性は、本発明の基礎をなす問題には関係がなく、従って、ここでは説明しないが、本発明の特定の実施例に関連して後述する）。もちろん、電気信号に変換され、かつ多重分離された成端波長の信号は、再び多重化され、かつ光信号に変換されて、次に同じノードにおいて光ＷＤＭネットワーク内へ再導入される。しかし、ある波長の伝送は、ノードへ入来する与えられた波長の光信号上のデータがノードから（その信号が入来サブリンクから送出サブリンクへどのようにして転送されるか、すなわち、光アッド・アンド・ドロップ（Ａｄｄ−ａｎｄ−Ｄｒｏｐ）マルチプレクサ、光交差接続または電気交差接続により転送されるかにかかわらず）必然的に光信号として出力されること、すなわち成端されていないことを意味するので、成端と伝送とは明らかに異なっており、一方、成端は、入来信号が変換され、かつ多重分離され、その後、その信号は、再導入されるが、必ずしも、そうとは限らないことを意味する。
【０００６】
これを、図２ａおよび図２ｂに関連して説明する。図２ａは、図１と同じ例を示しているが、図１に示されている一般的トポロジの特定の構成を示している。図２ａからわかるように、サブリンク２ａは、ノード３において成端（Ｔｅ）されており、一方、サブリンク２ｂは、サブリンク４ｂへ伝送されている。図２ａの例においては、サブリンク４ｂは、次にノード５を経てサブリンク６ｂへ伝送されているので、サブリンク２ｂ、４ｂおよび６ｂは、ノード１とノード７との間に経路を確立する。一方、サブリンク４ａおよび６ａは、ノード対３、５および５、７においてそれぞれ成端されている。伝送または成端するようにセットされたそのようなノードの配置は、物理レベル上の論理トポロジを定める。この論理配置は、ネットワークの構成と呼ばれる。
【０００７】
実際のネットワークにおいては、通信のためにネットワークを使用し始める前に構成が行われ、その構成は、ネットワークの動作中そのままにしておかれる。換言すれば、ネットワークを経てのトラヒックの瞬間的ルーティングは、構成を変えることなく、すなわち、固定された構成において行われる。しかし、もしネットワークにおける需要が激しく変化すれば（例えば、２つのノード間の平均トラヒックが著しく変化すれば）、またはネットワークにおける状況が変化すれば（例えば、特定のノードが故障すれば）、一般に構成の変更が必要となり、再構成と呼ばれる。
【０００８】
図２ａに示されている構成によれば、例えば、ノード１とノード７との間の通信は、経路（２ｂ−４ｂ−６ｂ）を経て、または経路（２ａ）、（４ａ）および（６ａ）を経て行われる。経路（２ａ）、（４ａ）および（６ａ）を経る通信は、それぞれの成端された信号がネットワーク内へ再導入されることを意味するのは、明らかである。ノード１とノード５との間の通信は、経路（２ａ）および（４ａ）を経て、または経路（２ｂ−４ｂ−６ｂ）および（６ａ）を経て行われる。この例においては、サブリンク２ａないし６ｂは、双方向性のものであると仮定されていることに注意される。
容易にわかるように、経路という用語は、それぞれの端部において成端されている１つ又はそれ以上の接続されたサブリンクを指す用語である。
【０００９】
図１の物理ネットワークは、図２ａに示されている構成へ制限されるわけではない。むしろ、図２ｂに示されているもののような他の構成も可能である。その場合は、サブリンク２ｂおよび４ｂがノード１とノード５との間の経路（２ｂ−４ｂ）を形成し、サブリンク４ａおよび６ａがノード３とノード７との間の経路（４ａ−６ａ）を形成し、サブリンク２ａがノード１とノード３との間の経路（２ａ）を確立し、サブリンク６ｂがノード５とノード７との間の経路（６ｂ）を確立する。この特定の構成によれば、ノード３とノード５との間の直接通信は、不可能であり、代わりに経路（２ａ）および（２ｂ−４ｂ）または経路（４ａ−６ａ）および（６ｂ）を選択しなければならない。図示されていないもう１つの構成においては、それぞれのサブリンクは、それが接続されているそれぞれのノードにおいて成端され、すなわち、相隣るノード間においてのみ経路を形成する。
【００１０】
可能な構成の数がノード、リンクおよびリンク毎のサブリンクの数に依存することは明らかである。ノード、リンクおよびサブリンクの数の増加に伴い、構成の数は、極めて大きくなる。一方、特定の物理ネットワークが与えられた時は、通信のために設定された要求を満たす構成を決定し、かつ同時に高通信速度、低損失、低設備コストなどのような１つ又はそれ以上の基準を満たす必要がある。これらの基準は、相互に排他的、競合的または相互に受益的なものである。同じ挑戦は、再構成においても生じる。
【００１１】
図２ａと図２ｂとの比較からわかるように、もしノード１とノード７との間に強いトラヒック需要があれば、図２ａの構成が有利であり、そのトラヒックがネットワークレベルに保持されること、すなわち、ノードにおける信号処理が少ないことが所望され、一方、もしノード１とノード５との間およびノード３とノード７との間に強いトラヒック需要があれば、図２ｂの構成が有利である。しかし、図２の例は、簡単化されており、実際のネットワークは、遥かに複雑である。実際のネットワークにおける可能な構成は、法外に多数であるために、要求および補助基準との無矛盾性に関する全ての可能な構成の簡単な検査は、不可能である。
【００１２】
また、上述の例は、基本タイプの伝送を示しているのみである意味において簡単化されている。この基本的伝送においては、タイプ「ａ」のサブリンクは、成端されるか、またはタイプ「ａ」の別のサブリンクへ伝送される。タイプ「ａ」のサブリンクをタイプ「ｂ」のサブリンクへ伝送する可能性は、考えられていない。しかし、１つのタイプのサブリンクから別のタイプのサブリンクへ、すなわち、特定の特性を有する１つのサブリンクから異なる特性を有する別のサブリンクへの伝送が行われるノードは、存在する。
【００１３】
一般に特定の特性を有するサブリンクを同じ特性の別のサブリンクへ伝送するのみであるノードの実際的な例は、ＷＤＭネットワークにおけるＯＡＤＭノード（ＯＡＤＭ＝光アッド・アンド・ドロップ・マルチプレクサ）である。図１および図２の上述の例において、１つのリンクに沿っての異なるサブリンクは、異なる波長のものであり、例えば、２ａ、４ａおよび６ａは、波長ＷＬ１であり、２ｂ、４ｂおよび６ｂは、波長ＷＬ２である。換言すれば、この例においては波長は、前記特性である。その場合、図２ａのノード３の構成は、波長ＷＬ１がノードにおいて成端されていることを意味し、一方、波長ＷＬ２は、通過、すなわち伝送される。換言すれば、ＯＡＤＭノードを用いるＷＤＭネットワークにおいては、与えられた波長で入来する信号は、伝送される。すなわち、光信号から電気信号への変換のような処理を受けるか、または、通過して再び同じ波長で送り出される。伝送は、光スイッチにより行われることに注意すべきである。
【００１４】
しかし、特性の変化および／または１つのサブリンクの複数の他のサブリンクへの伝送をさらに許容するノードもまた存在する。ＷＤＭネットワークにおける例は、ＯＸＣノード（ＯＸＣ＝光交差接続）である。図１の例において、個々のサブリンクが個々の波長を有すると仮定すると、ＯＸＣノードは、入来波長を成端させ、または同じ波長へ伝送するようにセットされるのみでなく、１つの入来波長を異なる送出波長へ変化させ、かつ／または同じ品質の複数のサブリンクの１つへ伝送するようにもセットされる。換言すれば、もし図１のノード３がＯＸＣノードであったとすれば、図１におけるサブリンク２ａ（ＷＬ１）は、成端され、またはサブリンク４ａ（ＷＬ１）へ通過されるのみでなく、サブリンク４ｂ（ＷＬ２）へも伝送される。そのような特性変化ノードは、ノードに２つより多くの線路が接続されている時に重要になる。その理由は、その場合の構成は、１つの入来サブリンクが１つより多くの送出サブリンクへ伝送されえなければならないことを意味するからである。
【００１５】
そのような追加の可能性が前記要求および基準による構成または再構成の問題をより複雑にすることは、容易に理解される。
【００１６】
（従来技術）
ＷＤＭネットワークの設計、構成および最適化への標準的アプローチは、問題を与えられた順序で以下の下位問題に分解することである。
−  仮想トポロジー（光波経路）を決定し、
−  それぞれの光経路に対し波長を割当て（ＷＡ、すなわち波長割当てとも呼ばれる）、かつ
−  トラヒックを前記光経路を経てルーティングする。
【００１７】
このアプローチの利点は、複雑な全体的問題が少数の変数を有し、従って複雑さの少ない下位問題に分割されることである。その理由は、アルゴリズムの（動作時間を決定する）複雑さは、変数の数の（多項式または指数）関数に比例するからである。欠点は、下位問題が連続して解かれ、それが全体的問題の解決の品質を劣化させることである。
【００１８】
そのような方法は、例えば、１９９５年６月のＩＥＥＥネットワーキングに関する会報、第３巻、第３号、第２８１ないし２８８頁に所載の、Ｚ．ツァング（Ｚ．Ｚｈａｎｇ）およびＡ．Ｓ．アカンポラ（Ａ．Ｓ．Ａｃａｍｐｏｒａ）著「波長ルーティングおよび波長再使用によるマルチホップＷＤＭネットワークのための発見的波長割当てアルゴリズム」、１９９５年１０月のネットワーキングに関するＩＥＥＥ会報、第３巻、第５号、第４８９ないし５００頁に所載のＲ．ラマスワミ（Ｒ．Ｒａｍａｓｗａｍｉ）およびＫ．Ｎ．シバラジャン（Ｋ．Ｎ．Ｓｉｖａｒａｊａｎ）著「全光ネットワークにおけるルーティングおよび波長割当て」、またはＩＣＣ’９７、すなわち１９９７年６月のモントリオールでの通信に関するＩＥＥＥ国際会議における、Ｈ．ハライ（Ｈ．Ｈａｒａｉ）、Ｍ．ムラタ（Ｍ．Ｍｕｒａｔａ）およびＨ．ミヤハラ（Ｈ．Ｍｉｙａｈａｒａ）著「制限された範囲の波長収束による全光ネットワークのパフォーマンス」に開示されている。これらの文献は、あるネットワークの特定の特徴を処理する方法に関し、特定の基準に従って上述の分解を用いている。
【００１９】
本技術分野においては、ネットワークを処理する問題を解決するためにグラフ理論を適用することも公知である。その例は、上述のハライ外著の論文と、１９９６年６月の通信における選択された分野のＩＥＥＥジャーナル、第１４巻、第５号、第９０９ないし９１３頁に所載のネットワークを波長グラフと呼ばれる特殊な構造に変換することによる光経路ルーティングのためのアルゴリズムを提示しているＪ．クラムタク（Ｊ．Ｃｈｌａｍｔａｃ）、Ａ．ファラゴ（Ａ．Ｆａｒａｇｏ）およびＴ．ツァング（Ｔ．Ｚｈａｎｇ）著の「大形ＷＤＭネットワークにおける光経路（波長）ルーティング」と題する論文と、光ファイバネットワークにおける多重化装置の最適の割当ておよび負荷の配分のための技術を記載したＷＯ９７／０５７１４とである。
【００２０】
（発明の目的）
本発明の目的は、与えられたネットワークを構成または再構成する一般化された方法を提供することであり、この方法は、過程を上述の３つのステップに分割せず、しかも複雑さが少なく、１つのタイプのネットワークと共用されるように制限されず、最適化のための特定の基準へ制限されることもない。
【００２１】
（発明の開示）
この目的は、ノードおよびリンクから成るネットワークを構成または再構成する方法により達成される。この場合、リンクの少なくともあるものは、１つより多くの独立サブリンクを含み、独立サブリンクは、リンク内の他のサブリンクとは無関係に信号を伝送することができ、１つより多くの独立サブリンクを含むリンクに接続されたノードは、それぞれの独立サブリンクがノードにおいて成端され、または別の独立サブリンクへ伝送されるように少なくともセットされることができる。この方法は、辺がサブリンクを表し、平行辺がサブリンクを含むリンクを表し、頂点および辺がノードを表すグラフを定めるステップと、第１の所定の基準により、それぞれの頂点におけるそれぞれの辺に伝送および成端のための初期の重みをそれぞれ割当てるステップと、第２の所定の基準により、第１のノード対を選択するステップと、第１のノード対の間に特定の経路を形成する独立サブリンクの系列を決定するステップであって、特定の経路が第１のノード対の間の他の可能な経路に対する第３の所定の基準を満たし、第３の所定の基準が経路に沿って辺の重みに関連する経路を決定するためのものである決定ステップと、特定の経路を形成する辺に割当てられた重みを経路に沿ったそれぞれのノードにおいて経路のそれぞれの辺について更新するステップであって、
−  経路内のノードを経て伝送される辺に割当てられる伝送のための重みが伝送のための初期の重みに対し減少され、
−  経路内のノードにおいて成端される辺に割当てられる伝送のための重みが伝送のための初期の重みに対し増加され、
−  経路内のノードを経て伝送される辺に割当てられる成端のための重みが成端のための初期の重みに対し増加され、
−  経路内のノードにおいて成端される辺に割当てられる成端のための重みが成端のための初期の重みに対し減少される、
更新ステップと、第１の基準に従い第１のノード対と異なる別のノード対を選択し、かつ、経路を決定し、重みを更新し、さらなるノード対を選択するプロセスを第４の所定の基準が満たされるまで繰返すステップとを含む。
【００２２】
核心において、ノードの対を決定するステップと、ノードの間に与えられた基準に従い最適である経路を決定するステップと、次に辺に対する重みを更新するステップと、このプロセスを繰返すステップとから成る本発明の方法は、上述のルーティングおよび波長割当ての問題を同時に解決し、一方、それにもかかわらず複雑さが少ない。
【００２３】
また、本発明の方法の特徴は、特定のタイプのネットワーク（光ネットワーク、電気ネットワーク）へ制限されず、上述のノードおよびリンクを含むどのようなネットワークの構成にも用いられることである。さらに、本発明の特徴は、どのようなタイプの最適化基準と共にも用いられることであり、すなわち、特定の基準へ制限されない。換言すれば、本発明の方法は、高度の柔軟性を有する。
本発明は、添付図面と共に以下の実施例についての詳細な説明を参照すれば容易に理解される。
【００２４】
（詳細な説明）
図３は、本発明の基本過程を説明するフローチャートを示す。
第１のステップＳ１においては、構成されるべきネットワークに基づき、辺および頂点から成るグラフが定められる。頂点は、辺の端部であり、それゆえ、それぞれの辺は、２つの頂点を有する。グラフは、辺がサブリンクを表し、平行辺がサブリンクを含むリンクを表し、頂点および辺がノードを表すように定められる。
【００２５】
図６ａ、図６ｂおよび図６ｃには、例が示されており、図６ａは、ノードおよびリンクから成るネットワークトポロジを示す。図６ｂは、図６ａに示されているリンクを表す辺および頂点から成る対応するグラフを示す。容易にわかるように、図６ａにおけるリンクは、それぞれが３つのサブリンクを有するように仮定されているので、３つの平行辺がそれぞれのリンクを表している。図６ｃは、図６ａに示されているノードをさらにモデル化している。容易にわかるように、この例においては、６０１ないし６０５により示されているノードは、それぞれのサブリンクが１つの他のサブリンクのみに伝送されるか（１つの辺の頂点と、もう１つの辺の頂点との間の線により表されている）、または成端される（破線の箱から引き出された線により表されている）ように仮定されている。６０６により示されているノードは、それぞれの頂点がそれぞれの他の頂点に接続されていることにより表されている通りに、それぞれのサブリンクがそれぞれの他のサブリンクへ伝送されるか、または、諸頂点から破線の箱の外部へ引き出された線により表されている通りに、それぞれのサブリンクが成端されるように仮定されている。図６ｃに示されているグラフは、接続されたグラフである。
【００２６】
モデル化ノードのもっと多くの例は、図７に示されている。図７ａから図７ｃまでには、４つの辺７０１ないし７０４が示され、７０１、７０２は、右から来て、７０３、７０４は、左から来ている。これらは、それぞれ２つのサブリンクを表す。図７ａは、ＷＤＭネットワーク内のＯＡＤＭ（光アッド・アンド・ドロップ多重化）ノードのモデルを示し、このノードにおいては、１つのサブリンクから別のサブリンクへの伝送のみ（２つの頂点の間の線により表されている）、または成端が許容される（破線の箱の外部へ引き出された線により表されている）。図７ｂは、図７ａに示された能力を有するＯＡＤＭノードのモデルを示しているが、さらに波長変換をも許容する。波長変換とは、１つの波長（すなわち、サブリンク）が異なる波長へスイッチすることを意味する。従って、サブリンクを表す辺からのそれぞれの頂点は、他の側の２つの頂点に接続され、すなわち、追加の線７０５、７０６が加えられている。最後に、図７ｃは、既に図７ａおよび図７ｂに示されている能力を有するＯＡＤＭノードのモデルを示しているが、さらに、いわゆるループバック機能を有し、これは、１つのリンク内のサブリンクが同じリンク内の別のサブリンクへスイッチされることを意味する。換言すれば、１つのリンク内の波長は、同じリンク内の別の波長に変換される。これは、右側の頂点を相互に、また左側の頂点を相互に、それぞれ接続する線７０７、７０８により表されている。
【００２７】
図８は、ノードのモデルのもう１つの例を示す。このモデルは、ＷＤＭネットワーク内のＯＸＣ（光交差接続）ノードを表す。４つの辺８０１ないし８０４は、頂部から来ており、４つの辺８０５ないし８０９は、底部から来ている。それぞれの辺は、波長を表す。このノードは、（図７ａのＯＡＤＭノードの場合におけるように）波長を別のリンク上の同じ波長へ伝送することができ、（図７ｂに示されているＯＡＤＭノードの場合のように）波長を別のリンク上の別の波長へ変換することができ、また、（図７ｃに示されているＯＡＤＭノードの場合のように）波長を同じリンク上の別の波長へループバックすることができるようなノードである。しかし、この例のノードは、成端は行わず、従って、このモデルは、対応する線をもたない。本発明は，もちろん、この場合にも適用される。
【００２８】
次に、ステップＳ２において、それぞれのノードにおけるそれぞれの辺に重みが割当てられ、その少なくとも１つは、成端のためのものであり、１つは、伝送のためのものである。もし重みを割当てられる辺が１つより多くの他の辺へ伝送される（すなわち、対応するノードがサブリンクを１つより多くの他のサブリンクへ伝送するもの、例えば、ＷＤＭネットワーク内のＯＸＣノードである）ならば、それぞれの可能な伝送に重みが割当てられる。これを図４および図５に関連して説明する。
【００２９】
図４ａは、２つのリンク１０および１１が引き込まれたノード１２を示す。これらのリンクは、３つの線により表されており、それぞれのリンクが３つのサブリンクを含むことを示すよう意図したものである。例としては、図４ａにおけるノードおよびリンクは、ＷＤＭネットワーク内のＯＡＤＭノードであり、その場合は、３つのサブリンクは、３つの異なる波長を有する。ノード１２は、１つのリンクのそれぞれのサブリンクが成端され、または他のリンクの１つのサブリンクへ伝送されるように仮定される。さらに、諸リンクは、双方向性のものであると仮定される。
【００３０】
図４ｃは、図４ａに示されているノードおよびリンクに対応するグラフを示し、１０１、１０２および１０３は、リンク１０内のサブリンクに対応する辺を示し、１１１、１１２および１１３は、リンク１１内のサブリンクに対応する辺を示す。参照番号１０１ａないし１０３ａと、１１１ａないし１１３ａとは、それぞれ辺１０１ないし１０３と、１１１ないし１１３とに関連する頂点を示す。
【００３１】
図４ｂは、図４ｃのグラフを示し、このグラフにおける重みの割当てを説明している。１３０により示されている箱は、グラフの部分ではないが、重みの割当てをより良く説明するために図４ｂに含まれている。さらに、長方形１２０は、ノード１２を示し、その中の辺および頂点により表されている。辺１０１と箱１３０との間および辺１１１と箱１３０との間の破線は、対応するサブリンクの成端を表し、一方、辺１０１と辺１１１との間の鎖線は、対応するサブリンクの間の伝送を表す。従って、辺１０１は、成端のための重みターム（１０１）と、伝送のための重みトランス（１）とを割当てられる。辺１１１は、成端のための重みターム（１１１）と、伝送に対する辺１０１および１１１のセッティングが相互的であることによる伝送のための辺１０１と同じ重み、すなわちトランス（１）とが割当てられる。
【００３２】
辺１０２、１０３および１１２、１１３に対し、重みの同様の割当てが行われるが、図４ｂには図をわかりやすくするために示さない。換言すれば、辺１０２は、成端のための重みターム（１０２）と、伝送のための重みトランス（２）とが割当てられ、トランス（２）は、また辺１１２の伝送のための重みでもある。同様にして、辺１０３は、成端のための重みターム（１０３）と、伝送のための重みトランス（３）とが割当てられ、トランス（３）は、辺１１３の伝送のための重みでもある。最後に、成端のための重みターム（１１２）およびターム（１１３）もまた、辺１１２および１１３のそれぞれに割当てられる。
【００３３】
図５ａは、ノード２０を示し、このノードには４つのリンク２１、２２、２３、および２４が入っている。それぞれのリンクは、３つの線により表され、それぞれのリンクが３つのサブリンクを含むことを示している。例としては、ノード２０は、ＷＤＭネットワーク内のＯＸＣノードである。この場合、３つのサブリンクは、３つの異なる波長を有する。それぞれのサブリンクは、成端され、または１１個の残りのサブリンクの１つに伝送される。図５ａの諸リンクは、双方向性のものであると仮定されている。
【００３４】
図５ｃは、図５ａの配置に対応するグラフを示す。辺２１１、２１２および２１３は、リンク２１を表し、辺２２１、２２２および２２３は、リンク２２を表し、辺２３１、２３２および２３３は、リンク２３を表し、辺２４１、２４２および２４３は、リンク２４を表す。参照番号２１１ａないし２１３ａと、２２１ａないし２２３ａと、２３１ａないし２３３ａと、２４１ａないし２４３ａとは、それぞれ、辺２１１ないし２１３と、２２１ないし２２３と、２３１ないし２３３と、２４１ないし２４３とに関連する頂点を示す。
【００３５】
図５ｂは、図５ｃのグラフを示し、そのグラフにおける重みの割当てを説明している。図４ｂにおける箱１３０と同様に、図５ｂにおける箱２５０は、グラフの部分ではないが、成端をより良く説明する目的のために役立つ。さらに、長方形２００は、ノード２０を示し、これは、その中の辺および頂点により表されている。辺２３１と箱２５０との間の破線は、成端を表し、従って成端のための重みターム（２３１）が割当てられる。やはり図をわかりやすくするために、成端のための全ての重みは図示されていないが、それぞれの辺は、成端のための重みターム（辺）が割当てられることを理解すべきである。例として、図５ｂは、さらに、辺２１１、２２３および２４３を成端する成端のための重みターム（２１１）、ターム（２２３）およびターム（２４３）を示している。
【００３６】
図５ｂは、辺２３１と、辺２１１ないし２１３および辺２２１ないし２２３との間の鎖線を示している。これらの鎖線は、それぞれの辺、すなわち対応するサブリンクの間の伝送を表す。図５ａに関連して上述した仮定により、辺２３１と、辺２３２、２３３、２４１、２４２および２４３との間にも伝送がセットされることを理解すべきであるが、図の理解を容易ならしめるために図５ｂには示されていない。また、図５ｂは、辺２３１と辺２２１との間の伝送のための１つの重みトランス（２３１／２２１）のみを示しているが、２つの辺ＸおよびＹ（ＸおよびＹは辺を表す）の間のそれぞれの伝送が伝送のための重みトランス（Ｘ／Ｙ）が割当てられることを理解すべきである。要約すると、それぞれの辺Ｘは、成端のための重みトランス（Ｘ）と、伝送のための１１個の重みトランス（Ｘ／Ｙ）とが割当てられ、ここでＹは、残りの１１個の辺のそれぞれを表す。図４ｂの場合におけると同様に、伝送は、相互的なものであるので、伝送のための重みトランス（Ｘ／Ｙ）は、双方の辺ＸおよびＹに割当てられる。
【００３７】
それぞれの辺に割当てられる重みの大きさに関しては、本発明は、再びその柔軟性を特徴とする。その理由は、これらの大きさを選択するために、どのような適切な基準でも適用されるからである。換言すれば、この基準は、構成されるべきネットワークの要求、制限および特性により、また、ネットワークがどのように最適化されるべきかにより、本発明の方法を適用する前に決定される。これは、さらに詳細に説明される。
【００３８】
ここで図３を再び参照すると、初期の重み割当てステップ（Ｓ２）に続いてステップＳ３が行われ、そこでは第１のノード対が選択される。この対を選択するための基準は、個々のアプリケーションの要求および制約に従って、再び柔軟に選択される。これもまた、さらに詳細に説明される。例として、第１のノード対は、その対の間の平均トラヒック需要が最高である対として、トラヒック需要に基づいて決定される。
【００３９】
次に、ステップＳ４においては、２つのノードの間の「最適」経路が経路に沿って遭遇される重みに基づいて決定される。経路とは、２つのノードの間のサブリンク（辺）のシーケンスである。経路に沿って遭遇される重みとは、その経路を構成する成端または伝送のための重みと、辺（サブリンク）のための可能な重みとである。サブリンクは、例えば、全てゼロの重みを有するが、ゼロよりも大きい重みを割当てられていてもさしつかえない。これは、図４ｂおよび図５ｂに示されている例を再び参照すれば、より良く理解される。図４ｂにおけるノード１２０を通る１つの可能な経路は、辺１１１と、辺１０１への伝送と、次の辺１０１とにより構成される。その場合、遭遇される重みは、単にトランス（１）である。一方、辺１１１と、（箱１３０への破線により記号化された）成端と、（箱１３０と辺１０１との間の破線により記号化された）辺１０１へのネットワーク内への再入力と、辺１０１とにより構成される経路に沿っては、重みは、ターム（１１１）およびターム（１０１）である。ノード１２０を通るもう１つの可能な経路は、辺１１１から成端および１３０を経ての辺１０２または１０３への再入力である。これらの場合においては、遭遇される重みは、ターム（１１１）と、ターム（１０２）（図４ｂには示されていない）またはターム（１０３）（図４ｂには示されていない）とである。いずれにせよ、ノード１２０内へ入る１つの辺からノード１２０内へ入るもう１つの辺まで導くどのような道も、ノード１２０を通る経路の部分を構成することは明らかである。
【００４０】
例として、もし図１のネットワークが構成されるであったとし、２つの上述のノードがノード１および７であったとすれば、１から７までの経路は、ノード３および５を通過する、すなわち、ノード３および５は、図４ｂに関連して上述したように遭遇される重みに寄与する。
【００４１】
経路に沿って遭遇される重みは、図５ｂに示されている例においても同様に決定されることは容易に理解できる。例えば、辺２３１と、辺２２１への伝送と、辺２２１とを部分として有する経路に沿って遭遇される重みは、トランス（２３１／２２１）であり、一方、辺２３１と、（２３１から箱２５０までの破線により記号化された）成端と、（箱２５０から辺２１１までの破線により記号化された）辺２１１における再入力と、辺２１１とを部分として有する経路に沿って遭遇される重みは、ターム（２３１）およびターム（２１１）である。
【００４２】
最適経路として考えられるべきもののための基準は、やはり以下にさらに詳述されるように、柔軟に選択される。例として、合計重みが経路に沿って遭遇される全ての重みの合計であるとするとき、基準は、最低の合計重みを有する経路が最適の経路であるとされる。
【００４３】
ここで、図３に説明されている基本的過程へ復帰すると、Ｓ４において最適経路が決定された後、ステップＳ５において、決定された経路を形成する辺に割当てられた重みが経路上のそれぞれのノードに対し、以下のように更新される。
−  経路内においてノードを経て伝送される辺に割当てられる伝送のための重みは、伝送のための初期の重みに対し減少され、
−  経路内においてノードにおいて成端される辺に割当てられる伝送のための重みは、伝送のための初期の重みに対し増加され、
−  経路内においてノードを経て伝送される辺に割当てられる成端のための重みは、成端のための初期の重みに対し増加され、
−  経路内においてノードにおいて成端される辺に割当てられる成端のための重みは、成端のための初期の重みに対し減少される。
【００４４】
この例を再び図４ｂを参照しつつ以下に与える。もし決定された経路がノード１２０を通過する部分を有し、その部分が辺１１１と、辺１０１への伝送と、辺１０１とを含むならば、伝送のための新しい重みトランス（１）が割当てられ、これは初期の重みよりも小さく、成端のための新しい重みターム（１１１）およびターム（１０１）は、初期の重みよりも大きい。もう１つの例として、もし決定された経路が辺１１１と、辺１１１の成端と、辺１０１への再入力と、辺１０１とを含む部分を有すれば、伝送のための重みトランス（１）は、高い値へ更新され、成端のための重みターム（１０１）およびターム（１１１）は、低い値へ更新される。最後に、もう１つの例として、もし辺１０１がノード１２０において成端され、ノード１２０が端点（すなわち、一対のノードの間で経路が決定されているとき、そのノードの一方）であるために、辺１１１における対応する再入力がなければ、トランス（１）は高い値へ更新され、ターム（１０１）は、低い値へ更新される。この場合、ターム（１１１）は、不変のままであるが、ターム（１１１）もまた低い値へ更新されるほうが好ましい。
【００４５】
更新後の重みの正確な値に関しては、初期の重みの正確な値についての対応する注意と同様に、本発明の方法は、特定の構成タスクの特定の要求に適するどのような値でも選択されうる点で柔軟性がある。好ましくは、伝送される経路においては、伝送のための重みは、ゼロに更新され、成端のための重みは、成端のための初期の重みよりも遥かに大きい値、例えば、１０００倍大きい値、または数値的に実現可能な無限大に相当する値に更新される。また、１つより多くの辺への伝送が行われうるノードにおいては、経路内において伝送を受けるようセットされた辺への伝送のための重みは、ゼロへ更新され、経路から伝送を受けない他の辺への伝送のための重みは、成端のための重みと同様に初期の重みよりも遥かに大きい値にセットされる。一方、成端された経路においては、トランジションのための重み（または諸重み）は、好ましくは、極めて大きい値、例えば、初期値より１０００倍大きい値、または数値的に実現可能な無限大に相当する値に更新され、成端のための重みは、好ましくは、ゼロと初期値との間の値へ更新される。すでに述べたように、これらの値は、単なる例であり、本発明がそれらへ制限されることを意味するものではない。
【００４６】
ここで図３において、ステップＳ５における更新の次には、もう１つのノード対の選択（再びステップＳ３）および、経路決定と、更新と、新しいノード対の選択とのサイクルの繰返しが停止のための基準が満たされる（ステップＳ６）まで行われる。上述の他の基準に関してと同様に、本発明は、この基準に関しても、どのような適切な基準でも適用されるので、柔軟性がある。例として、前記サイクルは、それぞれの可能なノード対が考慮され終わるまで継続されることができ、すなわち、それぞれの連続するサイクルは、まだ最適経路を決定されていない新しい対を全ての可能な対が考慮され終わるまで選択する。双方向性リンクの場合は、ＡおよびＢが対を形成するノードを表すものとすると、対Ａ−Ｂは、対Ｂ−Ａに等しく、単方向性リンクの場合は、Ａ−ＢおよびＢ−Ａは、別個に考慮すべき２つの異なる対である。もう１つの例として、前記サイクルは、制限された数のノードから得られる対が考慮され、終わった後に停止することも可能であり、例えば、ネットワークの部分のみの再構成の場合には、その部分は、制限された数のノードから成る。
【００４７】
過程が完了した時は、構成は、辺へ割当てられた重みにより与えられる。換言すれば、与えられたノードにおける辺が成端のための初期の重みより低い成端のための重みを有すれば、そのノードは、対応するサブリンクを成端するようにセットされて、もし伝送のための重みが初期の重みより低ければ、対応するサブリンクは、伝送へセットされている。
【００４８】
本発明は、好ましくは、ＷＤＭネットワークまたはＳＤＭネットワークのような光ネットワークへ適用される。ＷＤＭネットワークにおいては、リンクに含まれる独立サブリンクは、異なる波長により構成され、すなわち、サブリンクを識別する品質は、光の波長である。ＳＤＭネットワークにおいては、独立サブリンクは、定められた位置を有する個々のファイバにより構成され、すなわち、サブリンクを識別する品質は、場所または位置である。しかし、本発明は、決してＷＤＭまたはＳＤＭネットワークまたは一般の光ネットワークへ制限されるものではないことは明らかである。その理由は、本発明は、ノードの間のリンクの少なくともあるものの中にいくつかの独立サブリンクを有し、どのようなシステムに対しても適用可能であるからであり、その場合、ネットワークは、ノードが、ノードに取付けられた独立サブリンクに対し成端または伝送の状態にセットされる必要があるという意味において、構成される必要がある。もちろん、ネットワークは、異なるリンクが異なる数のサブリンクを有するようなものである。
【００４９】
成端および伝送という用語は、序論におけると同じ意味で用いられており、序論の内容は、本発明の開示に取り込まれている。換言すれば、成端という用語は、信号がネットワークから取り去られうることを意味し、一方、伝送という用語は、サブリンク上のノードへ入来する信号がノードを去ってもう１つのサブリンク上へ進まなくてはならないこと、すなわち、その信号が成端されないことを意味する。
【００５０】
本発明の方法は、どのようなトポロジのネットワーク、例えば、星形、リング形、星形またはリング形の変形、またはリンクにより接続された任意のノードの集合へも適用可能であることも理解すべきである。
【００５１】
本発明の方法は、ネットワークの最適化において特定の基準へ制限されないので、高度の柔軟性および汎用性を有する。本発明の方法は、与えられたネットワーク、要求および制約に依存し、どのような適切な、または所望される、基準のセットをも用いる点で、むしろ明確な特徴および利点を有する。
【００５２】
重みの割当て（図３のＳ２）に関する第１の基準は、一般に、頂点および辺により表されるノードの特定のタイプに依存し、また、構成または再構成されるべきネットワークを最適化する戦略に依存する。例えば、波長変化の可能性を含まないＯＡＤＭノードを用いるＷＤＭネットワークにおいて、もし光レベルにおけるトラヒックを好ましく保つことが所望されるならば、成端のための初期の重みは、伝送のための初期の重みよりも高くなる。その理由は、その場合は、成端よりも伝送のほうが好ましいからである。一方、もし光ネットワークにおいて電気交差接続ノード（ＥＸＣ）が用いられるならば、そのようなＥＸＣノードを表す辺および頂点のための全ての初期の重みは、同じになる。その理由は、全ての入来信号が電気信号へ変換され、伝送のための信号のみが次に光信号へ再変換されて、光ネットワークへ再導入されるからである。
【００５３】
ＷＤＭネットワークにおけるＥＸＣノードの上述の例に関連して、構成されるネットワークまたはノードの特定の性質に依存しない、成端と伝送との間の相違の一般的特徴に注意すべきである。上述のように、ＥＸＣノードへ入力される光信号は、サブリンク（この場合は波長）が成端されるか、伝送されるかの事実にかかわらず、全て電気信号へ変換される。成端される波長上の信号は、もし瞬間的なトラヒック制御が要求すれば、光信号へ再変換されてネットワークへ再導入される。このプロセスは、伝送へセットされたサブリンク上の信号に起こることと物理的に同じである。その理由は、この信号もまず電気信号へ変換され、後に光信号へ再変換されて、光ネットワークへ再導入されるからである。しかし、基本的な相違は、ノードにおいて伝送または成端へセットされた特定のサブリンクにより、成端されたサブリンク上の信号は、再導入される上、ネットワークから永久に除去されることもでき、一方、伝送された線路上の信号は、再導入されなければならず、すなわち、成端されないことである。
【００５４】
第２の基準、すなわち、考慮されるべきノード対の選択（図３のＳ３）の基準としては、ノードの間のトラヒック需要によるノードの分類を用いることができ、すなわち、第１の選択対は、それらの間に最高のトラヒック需要を有する対であり、第２の対は、第２の最高の需要を有する対などとなる。光ネットワークの場合には、これは、構成されたネットワークにおける電気的処理の減少となり、すなわち、トラヒック負荷は、主として光レイヤにより搬送され、電気的レイヤ（電気的スイッチ）により搬送されるものは少ない。そのわけは、成端されたサブリンクから光ネットワークへの信号の再導入は、その信号が伝送されるならば回避されうる電気的レイヤにおける処理を必要とするからである。一方、これは、より多くのリソースが光レイヤにおいて用いられることを意味する。もし、構成される、または再構成される特定のネットワークにおけるボトルネックが、電気的処理機能の容量であるならば、これは、よい戦略である。しかし、第２の基準は、どのような他の適切な基準であってもよい。例えば、ノード対を選択するステップは、距離によるソーティングによっても行われる。「距離」とは、経路に沿って交差されるリンクの数である。これは、「ホップ」の数とも呼ばれ、信号が経路に沿ってホップするノードの数を示す。この基準は、例えば、等しい数のホップを有する対をソーティングする時、リンクの（従って、リンクに含まれる独立サブリンクの）物理的長さをも考慮することにより洗練される。距離による対の選択は、構成された（または再構成された）光ネットワークの光レイヤにおけるリソースを最小化するが、電気的処理の量は増加させる。距離またはトラヒック需要によるソーティングの上述の基準を、例えば、双方と適正な重みとの線形結合である関数により、組合わせることも可能である。しかし、第２の基準のために特定の戦略を用いないで、単にランダムにノード対を選択することにより対選択ステップを行うことも、同様に十分に可能である。
【００５５】
第１および第２の基準についてと同様に、２つの選択されたノードの間の経路の決定（図３のＳ４）に関する第３の基準は、構成されるべきネットワークの与えられた要求および制約により選択される。最も簡単な基準は、最小の合計重みを有する経路、すなわち、２つのノードの間の全ての可能な経路のうちで、経路に沿って重みの和が最小である経路を選択することである。もう１つの可能な基準は、２つのノードの間の距離に関連するパラメータにより合計重みを修正し、修正量により最適経路を選択することである。一般的な意味において、第３の基準は、経路の「コスト」を与える経路に沿って重みの関数である。「コスト」という用語は一般的性質に関し、金銭的なコスト、エネルギーに関するコスト、必要な技術的プロセス（例えば、スイッチング）におけるコスト、または他の定義によるコストに等しいことがある。もちろん、この「コスト」は、この用語の上述の定義のあるもの、または全ての組合せでもある。上述の一般的意味において、第３の基準は、最低の「コスト」を有する経路を決定することである。
【００５６】
最低の合計重みを有する経路を見出すことによる最も簡単な経路決定のアプローチを用いる時、この経路は「最短経路」とも呼ばれ（すなわち、この特定の文脈においては、経路の合計重みは、上述の距離と混同されてはならない経路の「長さ」として見られる）、所望の経路は、ディジクストラ（Ｄｉｊｋｓｔｒａ）のアルゴリズムのような、最短経路アルゴリズムの助けにより決定される。このアルゴリズムは、本技術分野において公知であり、本発明は、その固有の柔軟性により、経路決定に用いられる特定のアルゴリズムに関するものではないので、このアルゴリズムの説明の必要はない。
【００５７】
更新ステップ（図３のＳ５）においては、重みは、重みと重みが関係する特性、すなわち、成端または伝送とにより変化される。これらの更新された重みの正確な数値に関しては、これらの数値が構成されるべきネットワークに伴う特定の要求および所望ならびに計算に用いられるシステムの特定の数値的要求および制約に応じて選択されるので、本発明の方法は、再び高度の柔軟性を有する。本発明の教示に関しては、初期の重み、または更新された重みの正確な数値は、任意のものであることは明らかである。その理由は、本発明の方法は、これらの重みの相対的変化にのみ関係しているからである。
【００５８】
以下においては、第１の例において、伝送の１つの可能性のみ、すなわち、１つの品質のサブリンクから同じ品質の別のサブリンクへの伝送のみが存在する場合が与えられる。従って、伝送へ割当てられる１つのみの重みが存在する。これは、すでに上述した図４に例示した場合である。１つより多くの他のサブリンクへの伝送が可能な場合は、後に説明される。
【００５９】
例として、経路内において伝送へセットされている辺に割当てられる、伝送のための重みは、好ましくは、初期の重みよりも遥かに小さい数、好ましくはゼロに更新される。一方、経路内において伝送へセットされている辺に割当てられる成端のための重みは、好ましくは、初期の重みよりも遥かに大きい数、好ましくは数値的に実現可能な無限大に相当する値に更新される。本発明の方法の文脈においては、そのような大きい重みは、成端する経路がその辺に対し、もはや不可能であることを意味する。経路に沿って辺が成端される時は、その辺の伝送のための１つの重み（または複数の重み）は、極めて大きい値、好ましくは数値的に実現可能な無限大に相当する値に更新され、また、成端のための重みは、初期値に対して減少されるが、好ましくはゼロまでは減少されず、初期値とゼロとの間の値まで減少される。上述の値は、好ましい例であるが、すでに述べたように、要求および制約により他の値も選択されることは、明らかである。
【００６０】
本発明の方法は、１つのサブリンクへの伝送へセットされるのみでなく、複数のサブリンクへの伝送へもセットされ、例えば、ある品質の１つの独立サブリンクを同じ品質の他の独立サブリンクと、かつ／または、異なる品質の複数の他の独立サブリンクと接続され、ノードを用いるネットワークへも適用できる。そのようなノードの例は、ＷＤＭネットワークにおけるＯＸＣ（光交差接続）ノードであり、このノードは、入来波長を成端することができ、１つの波長の入来サブリンクを同じ波長の送出サブリンクと接続することができ、または、１つの波長の入来サブリンクを異なる波長の送出サブリンクと接続することができる。この最後の可能性は、波長変換と呼ばれる。もしノードが、以上に定めた意味において伝送されるならば、辺への重みの割当てステップは、ノードにおける辺への伝送のためのさらなる重みの割当てにより補足されなければならず、すなわち、別の辺へのそれぞれの伝送の可能性に対し、それぞれの重みが割当てられなければならない。重みの更新ステップは、これらの補足の重みの更新により補足されなければならない。これら補足のステップと、２つのノードの間の可能な経路の数が増加する事実とを除外すれば、ノード対の決定、ノードの間での与えられた基準による最適経路の決定、および次に行われる辺における重みの更新の基本サイクルは、同じであるから、本発明の方法は、不変である。再び、これは、本発明がいかに汎用性を有し、広く適用されるかを証明している。
【００６１】
ノード対の決定、ノードの間での与えられた基準による最適経路の決定、および次に行われる辺における重みの更新のサイクルを終了するステップの第４の基準に関して、本発明の方法は、どのような特定の基準へも制限されないので、本発明の方法は、再び高度の柔軟性および汎用性を有する。もし所望の構成が全ネットワークに関連するならば、すなわち、ことごとくのノードをセットする必要があれば、全てのノードの間に経路が確立されるまで、過程は、繰返される。もし、例えば、ローカルな再構成において、ネットワークの部分のみが構成されるべきであれば、過程は、関係するノードに対し新しい経路が確立され終わるまで繰返される。
【００６２】
本発明のさらなる実施例によれば、あるノードの間でルーティングされるべきトラヒック需要は、あるサブリンクの伝送容量を超えることができ、この方法は、サブリンクの伝送容量を考慮するための補足的手段を含む。この実施例においては、それぞれのサブリンクの伝送容量およびそれぞれのノードの対の間のトラヒック需要は、既知であるものと仮定される。この実施例の方法によれば、（以上においてＳ４と呼ばれた）２つのノードの間の最適経路の決定ステップは、考慮されている２つのノードの間のトラヒックの量を処理するための十分な伝送容量をもたないサブリンクを含む経路を考慮から外すことにより補足される。
【００６３】
これは、例えば、まず最適経路を上述のように（例えば、合計重みに基づいて）決定し、次に、その経路上のそれぞれのサブリンクが考慮されているノード対に割当てられたトラヒック需要を処理しうるかどうかをチェックすることにより行われる。それぞれのサブリンクがトラヒックを処理できれば、与えられた経路は、最適であるとして選択され、プロセスは、重みを更新することにより継続され、一方、トラヒック需要が１つまたはそれ以上のサブリンクの伝送容量を超えていれば、この経路は捨てられて、次の最良の経路（基準として合計重みが用いられる時は、次の最低の合計重みを有する経路）が選択され、再び、経路に沿ってそれぞれのサブリンクがトラヒック需要を処理しうるかどうかのチェックを受ける。このプロセスは、トラヒック需要を処理しうる経路、すなわち、考慮されているノードの間のトラヒック需要を処理するために十分な伝送容量を有するサブリンクを含む経路が決定されるまで繰返される。もう１つの可能性は、考慮されている２つのノードの間にある全ての可能なサブリンクをまずチェックし、次に、与えられたトラヒック需要を処理するサブリンクを含む経路からのみ、最適の経路を決定することである。
【００６４】
（最良の態様）
以下においては、本発明の実施の最良の態様と発明者が現在考える本発明の実施例を説明する。この実施例によれば、以上において説明され、図３において説明された方法は、双方向性波長分割多重化（ＷＤＭ）ネットワークを構成するタスクへ適用される。そのようなＷＤＭネットワークにおいては、独立サブリンクは、異なる波長により形成される。
【００６５】
グラフの画定は、上述のように行われ、すなわち、リンク内のそれぞれの波長は、グラフ内の辺に対応し、平行辺は、リンクを表し、ノードは、辺および頂点により表される。
【００６６】
次に、重みが割当てられる。もしノードがＯＡＤＭ（光アッド・アンド・ドロップ）ノードであれば、この割当ては、図４に関連して説明された内容に対応する。換言すれば、ノードがＯＡＤＭノードであれば、辺１０１ないし１０３と、１１１ないし１１３とは、それぞれのリンク内の個々の波長を表す。例においては、１１１は、リンク１１内の波長であり、１０１は、リンク１０内の同じ波長である。換言すれば、ＯＡＤＭノードは、同じ波長へ伝送するのみであり、すなわち波長変化は、不可能である。従って、成端のための１つの重みと、伝送のための１つの重みとは、それぞれの辺へ割当てられる。本実施例によれば、成端のための初期の重み（例えば５０）は、伝送のためのそれ（例えば２５）よりも大きい。その理由は、もしトラヒックが光レイヤ上に留まることが所望されるならば、成端よりも伝送のほうが好ましいからである。
【００６７】
もしノードが、ＯＸＣ（光交差接続）またはＥＸＣ（電気交差接続）ノードであれば、重みの割当ては、図５に関連して説明された内容に対応する。双方の場合（ＯＸＣおよびＥＸＣ）において、辺２１１ないし２１３と、２２１ないし２２３と、２３１ないし２３３と、２４１ないし２４３とは、リンク２１、２２、２３および２４内の波長を表す。辺２１１、２２１、２３１および２４１に対応する波長は、同じであり、辺２１２、２２２、２３２および２４２に対応する波長は、同じであり、辺２１３、２２３、２３３および２４３に対応する波長は、同じであると仮定する。
【００６８】
図５ｂの例の場合には、それぞれの辺には、成端のための１つの重みと、伝送のための１１個の重みとが割当てられる。もしノードがＯＸＣノードならば、ＯＡＤＭの場合におけるように、成端のための初期の重み（例えば５０）は、同じ波長を有する別の辺への伝送のための初期の重み（例えば２５）よりも大きくセットされるが、異なる波長の別の辺への伝送のための初期の重みは、同じ波長への伝送のための初期の重みよりも大きく（例えば、５０に）割当てられる。その理由は、異なる波長への変化は、より複雑な処理を必要とするからである。従って、辺２３１のための重みは、例えば、ターム（２３１）＝５０であり、
トランス（２３１／２１１）＝トランス（２３１／２２１）＝トランス（２３１／２４１）＝２５また、
トランス（２３１／２１２）＝トランス（２３１／２１３）＝トランス（２３１／２２２）＝トランス（２３１／２２３）＝トランス（２３１／２３２）＝トランス（２３１／２３３）＝トランス（２３１／２４２）＝トランス（２３１／２４３）＝５０である。
【００６９】
他の辺へも、重みは同様にして割当てられる。
もしノードがＥＸＣノードならば、全ての初期の重みは、同じ（例えば２５）になる。
【００７０】
次に、本発明の実施例によれば、第１のノード対が平均トラヒック需要により選択され、すなわち、第１のノード対は、それらの間のトラヒック需要が最高の対である。次に、最適経路は、経路に沿って遭遇される合計重みにより決定される。この実施例によれば、可能な経路の合計重みは、長さのように処理され、最も短い長さ、すなわち、最低の合計重みがこの時ディジクストラのアルゴリズムにより決定される。もし同じ合計重みを有するいくつかの経路が存在すれば、リンクの物理的距離、または１つのノードへ他のノードから到達するために物理的トポロジ上において必要とされるホップの数を考慮するような補足的基準を用いることができ、あるいは経路の１つを単にランダムに選択することもできる。
【００７１】
最適経路が決定された後、前述のように、経路に沿っての重みが更新される。本実施例においては、特定の辺へ伝送する経路内の辺における特定の辺への伝送のための重みは、ゼロへ更新され、一方、伝送している辺における成端のための重みは、極めて大きい数（例えば１０6）へ更新され、特定の辺以外の辺への伝送のための重みもまた極めて大きい数へ更新される。ノードがＯＡＤＭノード、ＯＸＣノードまたはＥＸＣノードであるかどうかにかかわらず、成端のための重みは、成端される経路内の辺においては、ゼロと成端のための初期値との間の値（例えば２５）へ更新され、一方、伝送のための重みは、成端される辺においては、極めて大きい数（例えば１０6）へ更新される。
【００７２】
次に、新しいノード対、すなわち、第２の最高平均トラヒック需要を有するノード対が選択されて、サイクルが繰返され、ことごとくの可能なノード対の間に最適経路が決定され終わるまで、それぞれの新しいノード対が減少していく平均トラヒック需要により決定される順序で選択され、その場合、上述の双方向性リンクの仮定のもとでは、対Ａ−ＢおよびＢ−Ａは、１つの対として取り扱われることに注意すべきである。もし単方向性リンクが選択されれば、Ａ−ＢおよびＢ−Ａは、２つの異なる対として処理される。
【００７３】
結果として得られる構成は、次に辺に割当てられる重みにより与えられ、すなわち、もし辺の成端のための重みが低い値にセットされれば、対応するサブリンクは、成端されるように構成され、また、もし別の特定の辺へ辺の伝送のための重みが低い値にセットされれば、対応するサブリンクは、その別の辺に対応するサブリンクへ伝送されるように構成される。
【００７４】
ノード対の選択基準と、初期の重みと、更新重みとの上述の選択により、結果として得られる構成は、好ましくはトラヒックを光レイヤ上に保持する。
本発明は、以上の実施例へ制限されるものではなく、むしろ添付の特許請求の範囲により定められる。特許請求の範囲における参照番号は、よりよい理解を与える目的のものであり、範囲を制限するものではない。
【図面の簡単な説明】
【図１】  ネットワークの構成の問題を説明するための、簡単化されたネットワークの概略図である。
【図２ａ】  図１に示されているネットワークの概略的構成を示す。
【図２ｂ】  図１に示されているネットワークのもう１つの概略的構成を示す。
【図３】  本発明による方法の基本過程を示すフローチャートである。
【図４ａ】  それぞれのリンクが３つのサブリンクを有する２つのリンクを有するノードの概略的例を示す。
【図４ｂ】  ａのノードおよびリンクを表す辺および頂点を示し、かつ重みの割当てを説明している。
【図４ｃ】  ａの配置を表すグラフのみを示す。
【図５ａ】  それぞれのリンクが３つのサブリンクを有する４つのリンクを有するノードの概略的例を示す。
【図５ｂ】  ｂのノードおよびリンクを表す辺および頂点を示し、かつ重みの割当てを説明している。
【図５ｃ】  ａの配置を表すグラフのみを示す。
【図６ａ】  ネットワークの例を示す。
【図６ｂ】  ａのネットワークのリンクをモデル化したグラフを示す。
【図６ｃ】  ａのネットワークのリンクおよびノードをモデル化したグラフを示す。
【図７ａ】  ＯＡＤＭノードの１つのモデルを示す。
【図７ｂ】  ＯＡＤＭノードのもう１つのモデルを示す。
【図７ｃ】  ＯＡＤＭノードのさらにもう１つのモデルを示す。
【図８】  ＯＸＣノードのモデルを示す。
【図１】
0004017342.tif 000002
【図２ａ】
0004017342.tif 000003
【図２ｂ】
0004017342.tif 000004
【図３】
0004017342.tif 000005
【図４ａ】
0004017342.tif 000006
【図４ｂ】
0004017342.tif 000007
【図４ｃ】
0004017342.tif 000008
【図５ａ】
0004017342.tif 000009
【図５ｂ】
0004017342.tif 000010
【図５ｃ】
0004017342.tif 000011
【図６ａ】
0004017342.tif 000012
【図６ｂ】
0004017342.tif 000013
【図６ｃ】
0004017342.tif 000014
【図７ａ】
0004017342.tif 000015
【図７ｂ】
0004017342.tif 000016
【図７ｃ】
0004017342.tif 000017
【図８】
0004017342.tif 000018