(57)【要約】  装置は、複数のエッジ・ノードを接続する時間領域波長インタリーブ化光ネットワークを備える。エッジ・ノードの各々は、関連した波長チャネル上のエッジ・ノードのうちの別のものから光通信を受信するように構成される。エッジ・ノードの数は、波長チャネルの数よりも多い。
2008541615.tif 000002
【特許請求の範囲】
【請求項１】
エッジ・ノードの各々が、関連した波長チャネル上の前記エッジ・ノードのうちの別のものから光通信を受信するように構成されており、エッジ・ノードの数が、前記波長チャネルの数よりも多い、複数のエッジ・ノードを接続する時間領域波長インタリーブ化光ネットワークを備えた装置。
【請求項２】
前記エッジ・ノードのうちの少なくとも２つが、同じ波長チャネルに割り当てられる請求項１に記載の装置。
【請求項３】
前記時間領域波長インタリーブ化光ネットワークが、光通信を前記光通信の前記波長チャネルに基づいて前記エッジ・ノードにルーティングする受動光ネットワークを備える請求項１に記載の装置。
【請求項４】
前記エッジ・ノードのうちの少なくとも１つが、前記光通信のうちのいくつかの受信されたものを、異なる第２波長チャネル上の前記エッジ・ノードのうちの別のものに光学的に再送信するように構成されている請求項１に記載の装置。
【請求項５】
前記エッジ・ノードの各々が、ＴＷＩＮを介して通信を前記別のエッジ・ノードの各々に送信することができる請求項１に記載の装置。
【請求項６】
通信のキャリア波長に基づいて、ＴＷＩＮの光ネットワークを介した発信元ノードから第２ノードへの通信の第１のルーティングを実行することと、
前記光通信の中で運ばれる補足的ルーティングデータに基づいて、前記第２ノードが前記通信の発信先であるかどうかを判定することと、
前記第２ノードが前記通信の前記発信先ではないという判定に応じて、前記ＴＷＩＮの光ネットワークを介した前記第２ノードから第３ノードへの前記通信の第２のルーティングを実行することとを含む方法。
【請求項７】
前記第２ルーティングを実行することが、前記第１ルーティングを実行する間に前記通信を送信するために使用された波長チャネルとは異なる波長チャネル上で前記通信を送信することを含む請求項６に記載の方法。
【請求項８】
各実行工程が、波長に基づいて受動的に光信号をルーティングする光ネットワークに前記通信を送信することを含む請求項６に記載の方法。
【請求項９】
前記光通信の中で運ばれる補足的ルーティングデータに基づいて、前記第３ノードが前記通信の発信先であるかどうかを判定することと、
前記第３ノードが前記通信の前記発信先ではないという判定に応じて、前記光ＴＷＩＮを介した前記第３ノードから第４ノードへの前記通信の第３のルーティングを実行することをさらに含む請求項６に記載の方法。
【請求項１０】
前記補足的データが、前記通信のための次の中間ノードのアイデンティティを示す情報を一覧にする請求項６に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、２００５年５月１０日に出願した出願第１１／１２６，０２４号の一部継続出願である。
本発明は一般に、例えば時間領域波長インタリーブ化ネットワーク（ｔｉｍｅ‐ｄｏｍａｉｎ  ｗａｖｅｌｅｎｇｔｈ  ｉｎｔｅｒｌｅａｖｅｄ  ｎｅｔｗｏｒｋｓ）などの光通信ネットワークに関する。
【背景技術】
【０００２】
図１は、例示的な従来の時間領域波長インタリーブ化ネットワーク（ＴＷＩＮ）１０を概略的に示す。ＴＷＩＮ１０は、複数のエッジ・ノード１４を物理的に相互接続する受動光ネットワーク（ＰＯＮ）１２を含む。ＰＯＮ１２は複数の内部ノード１６を有する。各内部ノード１６は、波長だけに基づいて、複数の光伝送ファイバ１８の間で光通信を受動的にルーティングするように構成された光クロスコネクト（ＯＸＣ）を有する。各エッジ・ノード１４は、波長可変光トランシーバ（不図示）を有する。したがってエッジ・ノード１４は、ＴＷＩＮによってエンド・ユーザ間で運ばれる光通信のための発信元および発信先としての役割を果たす。
【０００３】
ＴＷＩＮ１０では、各波長チャネルは光通信を受信するために、エッジ・ノード１４のうちの１つに個別に割り当てられる。次いで発信元エッジ・ノード１４は、所望のエッジ・ノード１４に割り当てられた波長チャネル上で、単純に光通信をＰＯＮ１２に送信することによって、光通信を所望のエッジ・ノード１４に送信する。ＰＯＮ１２は、光通信の波長だけに基づいて、光通信を所望の発信先エッジ・ノード１４にルーティングする。第２の発信先エッジ・ノード１４に送信するために、発信元エッジ・ノード１４は単純に、その光トランシーバの送信波長を第２発信先エッジ・ノード１４に割り当てられた波長チャネルに再設定する。
【０００４】
したがって、ＰＯＮ１２は光通信のルーティングを自動的に処理する。つまり、ルーティングを可能にするために、光通信はラベルまたはアドレス・ヘッダを必要としない。波長だけが、光通信の１つが所望の発信先エッジ・ノード１４にルーティングされることを確実とする。
【０００５】
この理由のため、ＰＯＮ１２はその内部ノード１６に光通信をバッファリングするためのハードウェア支援を有していない。内部ノード１６は自動的かつ直ちに、受信された光通信をそれらの発信先ノードにルーティングする。さらにＰＯＮ１２のＯＸＣは複数の光通信を同時にルーティングすることができるので、異なる光通信間の衝突によって、ＰＯＮ１２の内部ノード１６で情報損失が生じることがない。特に２つの光通信間の衝突によって、発信先エッジ・ノード１４のうちの１つで衝突が生じる。したがって、発信先エッジ・ノード１４に到着する時間が重ならないようにするために光通信をスケジューリングすることは、通常そうした衝突を回避する。
【０００６】
特にＰＯＮ１２は、各エッジ・ノード１４が対応する１つのツリーの根となっている、有向ツリー（ｄｉｒｅｃｔｅｄ  ｔｒｅｅ）のトポロジを実装する。各有向ツリーは、関連した内部ノード１６を介して受信された光通信をツリーの根、すなわち発信先エッジ・ノード１４にルーティングする。そのようなトポロジでは、発信先エッジ・ノード１４で光通信間の競合が起こる。そうした発信先の競合を減少させるために、発信元エッジ・ノード１４は、異なる発信先エッジ・ノードへのバーストまたはインタリーブ・バーストとして、光通信の送信をスケジュールする。
【特許文献１】出願第１１／１２６，０２４号
【発明の開示】
【課題を解決するための手段】
【０００７】
受信波長チャネルを単一のエッジ・ノードに割り当てることは、エッジ・ノードの数を利用可能な波長チャネルの数に限定する。本明細書では、様々なＴＷＩＮの実施形態は、受信波長チャネルを２つ以上のエッジ・ノードに割り当てる。したがってＴＷＩＮは、利用可能な波長チャネルの数よりも多いエッジ・ノードを有する。そのような構成によって、高い費用をかけて利用可能な波長チャネルの数を増やすことなく、エッジ・ノードの数の調整が可能となる。
【０００８】
１つの実施形態は、装置を特徴とする。この装置は、複数のエッジ・ノードを接続する時間領域波長インタリーブ化光ネットワークを含む。エッジ・ノードの各々は、関連した波長チャネル上で別のエッジ・ノードからの光通信を受信するように構成されている。エッジ・ノードの数は、波長チャネルの数よりも多い。
【０００９】
第２実施形態もまた、光ネットワークと、光ネットワークによって相互接続された複数のエッジ・ノードとを含む装置を特徴とする。各エッジ・ノードは関連した波長チャネルを有する。光ネットワークは、発信先であるエッジ・ノードに関連した波長チャネル上にある通信に応じて、いくつかの発信元であるエッジ・ノードから発信先であるエッジ・ノードに光通信をルーティングするように構成されている。エッジ・ノードの数は、波長チャネルの数よりも多い。
【００１０】
第３実施形態は、ＴＷＩＮの中で通信を送信する方法を特徴とする。この方法は、通信のキャリア波長に基づいて、ＴＷＩＮの光ネットワークを介した発信元ノードから第２ノードへの通信の第１のルーティングを実行することを含む。この方法は、光通信の中で運ばれるルーティングデータから、第２ノードが通信の発信先であるかどうかを判定することを含む。ルーティングデータは、光ネットワークの中の通信の波長チャネルを補足するものである。この方法は、第２ノードが通信の発信先ではないという判定に応じて、ＴＷＩＮの光ネットワークを介した第２ノードから第３ノードへの通信の第２のルーティングを実行することを含む。
【００１１】
様々な例示的な実施形態は、図面および以下の説明によって、より完全に説明される。しかしながら、本発明は様々な形態の中で具体化されてもよく、例示的な実施形態の図面および詳細な説明の中で説明されている実施形態に限定されるわけではない。
図面および本文の中で、同じ参照符号は類似の機能を備えた要素を示す。
【発明を実施するための最良の形態】
【００１２】
本明細書では、わかり易いように、波長について言及するために、しばしば色を使用する。色は可視、赤外線または紫外線光の波長を指す場合がある。
図２を参照すると、例示的なＴＷＩＮ１０’は受動光ネットワーク（ＰＯＮ）１２’と、ＰＯＮ１２’によって相互接続された複数のエッジ・ノード１４’とを含む。ＰＯＮ１２’は光通信の波長だけに基づいて、エッジ・ノード１４’間の光通信を受動的にルーティングする。ＰＯＮ１２’は光ファイバ送信路１８’と内部ノード１６’とを含む。各エッジ・ノード１４’は、光通信を送受信するためのマルチチャネル光トランシーバを有する。
【００１３】
図３は、光路Ｘ、ＹおよびＺが、どのようにして図２に示されているＴＷＩＮ１０’の例示的な内部ノード１６’によって転換されるのかを概略的に示す。例示的な内部ノード１６’は波長に基づいて、光ポートＡ、Ｂ、ＣおよびＤの間で光通信の光を受動的にルーティングする。光ポートＡ、Ｂ、ＣおよびＤの各々はペアになった入力および出力光ファイバ送信路１８’に接続し、次にその他の内部またはエッジ・ノード１４’（不図示）に接続する。エッジ・ノード１４’に接続する光ポートＡ〜Ｄのうちの１つのために、例示的な内部ノード１６’は光アド／ドロップ・マルチプレクサ（ＯＡＤＭ）として機能する。その他のエッジ・ノード１４’に接続する光ポートＡ〜Ｄのうちの１つのために、例示的な内部ノード１６’は光クロスコネクト（ＯＸＣ）として機能する。
【００１４】
内部ノード１６’は、例えば光路ＸおよびＹなどの、同じ波長の光を運ぶ着信光路を結合してもよい。しかしながら、内部ノード１６’は着信光路を分割することはないので、受信される１つの波長の光はＴＷＩＮ１０’の中の２つ以上の出力光ポートに向けられる。例えば、光路Ｒと潜在的光路Ｓとの間で光路Ｚを分割することは禁止されている。
【００１５】
図４は、図２のエッジ・ノード１４’のうちの例示的な１つを概略的に示す。例示的なエッジ・ノード１４’は波長可変光トランスミッタＴｘと、固定波長光レシーバＲｘと、光レシーバＲｘを光トランスミッタＴｘと１人または複数のユーザ（ＥＵ）とに接続する電子スイッチ（ＳＷ）とを含む。光トランスミッタＴｘは、エッジ・ノード１４’の近隣ノードに割り当てられた波長チャネル上の送信光に対して可変である。ここで、選択されたエッジ・ノードの近隣ノードは、ＰＯＮ１２’を介して、選択されたエッジ・ノードの光トランスミッタＴｘから光通信を直接受信することができる別のエッジ・ノードである。光レシーバＲｘは、関連したエッジ・ノード１４’に割り当てられた単一の波長チャネルで光通信を受信するように構成されている。電子スイッチ（ＳＷ）は電子的に、レシーバＲｘから受信された通信の経路を、１つまたは複数の局所のエンド・ユーザ（ＥＵ）か、または局所のトランスミッタＴｘのいずれかに設定する。すなわち、電子スイッチＳＷは、光形態から電子形態への転換の後で通信の局所ルーティングを実行する。電子スイッチＳＷは受信された通信からの補足的なルーティングデータ、すなわち受信された光通信の波長チャネル以外のデータに基づいて、局所ルーティングの判定を行う。補足的なルーティングデータは、局所のエッジ・ノードが最終的な発信先であるのか、または特定の通信のための単なる中間のエッジ・ノードであるのかを判定する。
【００１６】
ここで再び図２を参照すると、ＰＯＮ１２’は、そこの光通信の波長チャネルだけに基づいて、受動的に光通信をエッジ・ノード１４’にルーティングする。しかしながらＴＷＩＮ１０’では、複数のエッジ・ノード１４’は同じ波長に割り当てられる。すなわち、ＴＷＩＮ１０’は利用可能な波長チャネルよりも多くのエッジ・ノード１４’を有する。これらの理由のために、１つまたは複数のエッジ・ノード１４’は、ＰＯＮ１２’によって実行される光ルーティングだけを介して、１つまたは複数のその他のエッジ・ノード１４’と直接通信することができない。
【００１７】
その代わりＴＷＩＮ１０’では、発信元のエッジ・ノード１４’は直接ＰＯＮ１２’を介して、「近隣の」エッジ・ノード１４’の関連したセットへ光通信を送信することだけを行ってもよい。本明細書では、そのようなＰＯＮを介した全方向の光送信は、単一ホップ送信と呼ばれる。発信元のエッジ・ノード１４’は間接的に１つまたは複数の中間エッジ・ノード１４’を介して、すなわちマルチホップ送信を介して、ＴＷＩＮの別のエッジ・ノード１４’に通信を送信する。中間エッジ・ノード１４’は、単一ホップ光通信の発信先として、およびマルチホップ光通信のためのゲートウェイとして機能する。ゲートウェイとして中間エッジ・ノード１４’はゲートウェイとして受信された光通信を再送信するので、そのような通信はＰＯＮ１２’を通じた１つまたは複数のその他のホップを実行することができる。そうした付加されたホップは、元々の発信元エッジ・ノード１４’の近隣ノードではないエッジ・ノード１４’に、そうした通信をルーティングする。第２または高位のホップの間、光通信は元々の光通信と同じ波長チャネル上にあってよく、または異なる波長チャネル上にあってもよい。特に第２ホップの間の通信の波長は、元々の光通信の波長チャネルではなく、むしろ第２の発信先エッジ・ノード１２’の波長割当によって決まる。
【００１８】
ＴＷＩＮの様々な実施形態で、通信は、その最終的な発信先エッジ・ノードに到達する前に、ＴＷＩＮのＰＯＮの中で１つ、２つまたは複数のホップを作ってもよい。ＴＷＩＮのＰＯＮはエッジ・ノードに相互接続しているが、ＰＯＮ自体は接続されていても、接続されていなくてもよい。
【００１９】
図５は、図２に示されているＴＷＩＮ１０’の特定の実施形態のための単一ホップに関連した光路を示す。特定の実施形態で、各エッジ・ノード１４’、すなわち便宜上１、２、３および４と符号を付けられたエッジ・ノードは、それぞれ赤および青と呼ばれる２つの波長チャネル上で光通信を送信する。この特定の実施形態で、エッジ・ノード１および３は発信先の色青に割り当てられ、エッジ・ノード２および４は発信先の色赤に割り当てられる。これらのカラー割当のために、赤色光および青色光のための単一ホップの光路は、それぞれ実線および点線の矢印を用いて図５の中で示されている。この単一ホップ光路のセットのために、エッジ・ノード１、２、３および４の近隣ノードは、｛３、４｝、｛３、４｝、｛１、２｝および｛２、３｝のそれぞれのノードのセットによって与えられる。次いで、中間エッジ・ノードがそれぞれ｛３、４｝、｛３｝、｛１、２｝および｛３｝のそれぞれのセットから選択される場合、エッジ・ノード１からエッジ・ノード２、エッジ・ノード２からエッジ・ノード１、エッジ・ノード３からエッジ・ノード４、およびエッジ・ノード４からエッジ・ノード１への通信の２ホップ送信が可能となる。
【００２０】
中間エッジ・ノード１４’のセットは、ＰＯＮ１２’からの光通信の受信に応じて、ゲートウェイまたは発信先のいずれかとして、選択的に機能する。
この理由のため、これらのエッジ・ノード１４’は、例えば図４の高機能電子スイッチ（ＳＷ）によって実行される機能など、結果が受信された光通信の形態によって決まる選択／切り替え機能を支援する。特に光通信は、ゲートウェイ・ノードとして動作するのか、または発信先ノードとして動作するのかどうかを判定するために、すなわち通信を局所のエンド・ユーザに与えるために中間エッジ・ノード１４’が使用する、補足的なルーティングデータを運ぶ。利用可能な波長チャネルの数が利用可能な発信先の数よりも少ない場合、通信の波長チャネルは通信の発信先を個別に決定することがないので、補足的なルーティングデータが必要とされる。
【００２１】
光通信は、ヘッダまたは時間パルス・シーケンスとして補足的なルーティングデータを運んでもよい。補足的なルーティングデータは、すなわち元々の発信元エッジ・ノード１４’に判定されるものとして、横断される中間エッジ・ノード１４’の全シーケンスを含んでよい。代替として、補足的なルーティングデータは最終発信先エッジ・ノード１４’のアイデンティティか、または最終発信先エッジ・ノード１４’および元々の発信元エッジ・ノード１４’のアイデンティティだけを含んでもよい。中間エッジ・ノード１４’は、補足的なルーティングデータを読み取って、データから次のホップの形態を判定し、次の受信エッジ・ノード１４’のアイデンティティを表すデータを局所の光トランスミッタに送信するための高機能の回路を有する。局所の光トランスミッタは、ＰＯＮ１２’を通じて通信を次のホップに適した波長チャネル上の光形態に再転換するために、次の受信エッジ・ノード１４’のアイデンティティを表すデータを使用する。
【００２２】
ＴＷＩＮは、ネットワークの単一ホップ構造によって定義される仮想トポロジを有する。本明細書では、仮想トポロジとは、ＴＷＩＮのエッジ・ノードで形成される有向アークのグラフである。このグラフは、エッジ・ノード「ａ」が単一ホップを介して光通信をエッジ・ノード「ｂ」に送信することができる場合に限り、エッジ・ノード「ａ」からエッジ・ノード「ｂ」への有向アークを含む。
【００２３】
従来のＴＷＩＮの仮想トポロジは、そうしたＴＷＩＮの任意のエッジ・ノードが、通信を単一ホップによって任意の別のエッジ・ノードに光学的に送信することができるため、相対する有向アークのペアがエッジ・ノードの各ペアに接続している有向グラフに完全に接続されている。対照的に、本明細書のＴＷＩＮの実施形態は、それらが利用可能な波長チャネルの数よりも多くのエッジ・ノードを有するために、完全に接続された仮想トポロジを有していない。本明細書のＴＷＩＮの実施形態が波長チャネルよりも多くのエッジ・ノードを有するために、所与のエッジ・ノードは単一ホップのプロセスを介して、通信を少なくとも１つの別のエッジ・ノードに送信することができない。完全に接続されていない仮想トポロジの例は、図６に示されている図５のＴＷＩＮのための仮想トポロジである。
【００２４】
上の説明はＴＷＩＮの特定の実施形態に限定されていたが、本発明はその他の実施形態を含むことが意図されている。例えば、ＰＯＮは異なる数の内部ノードおよび／または光ファイバ経路、異なる数のポートを備えた内部ノード、異なる物理的トポロジ、および内部ノードでの異なるルーティング構成を有してもよい。また、エッジ・ノードは異なる割当の波長チャネルおよび／または異なる数の利用可能な波長チャネルを備えた光トランシーバを有してもよい。さらに、ＴＷＩＮは異なる仮想トポロジを実装するように構成されてもよい。
【００２５】
図７は、接続されたネットワークの中で通信を送信するための方法３０を示す。ネットワークの例は図２のＴＷＩＮ１０’、ならびにＰＯＮおよびＰＯＮによって相互接続されたエッジ・ノードのセットを含み、１つまたは複数のエッジ・ノードがＰＯＮのためのゲートウェイとして機能するその他のネットワークを含む。
【００２６】
方法３０は、通信のキャリア波長だけに基づいて、例えばＴＷＩＮの光ネットワークを介した通信の発信元ノードから第２ノードへの第１のルーティングを実行すること（工程３２）を含む。方法３２は、通信の発信先ノードが第２ノードであるのかどうかを第２ノードで判定すること（工程３４）を含む。判定を行う工程は、光通信の中で運搬されるルーティングデータを読み取り、分析することを含む。読み取りルーティングデータは、光ネットワークの中で受信された光通信の波長チャネルを補足するものである。方法３０は、第２ノードが通信の発信先ではないという判定に応じて、光ネットワークを介した第２ノードから第３ノードへの通信の第２のルーティングを実行すること（工程３６）を含む。第２ルーティング工程では、光ネットワークは元々第２ノードで受信された光通信のキャリア波長と同じものであっても、または異なるものであってもよい通信のキャリア波長だけに基づいて、通信をルーティングする。第２ルーティングを実行する工程は、第２ノードが通信の発信先であるという判定に応じて、第２ノードに直接接続されたエッジ・ノードに通信を与えることを含んでもよい。
【００２７】
ＴＷＩＮの様々な実施形態で、中間エッジ・ノードによって受信された通信を処理することには、ＰＯＮを介した単一ホップを通じて通信を光学的にルーティングすることよりも、より多くの時間および／またはより多くの費用がかかる場合がある。したがって、単一ホップの処理能力をほぼ最大にするようにＴＷＩＮを構成することによって、総処理能力を増加させること、および／または総費用を減少させることが可能であると思われる。
【００２８】
所与のトラフィック・マトリクスに基づいて、単一ホップの処理能力をほぼ最大化するようにＴＷＩＮの構成を設計するために、複数の方法が利用可能である。トラフィック・マトリクスＴの中で、要素Ｔａ、ｂは発信元エッジ・ノード「ａ」から発信先エッジ・ノード「ｂ」に運ばれるトラフィックを定義する。様々な設計方法は、所与の物理的アーキテクチャ、すなわちＰＯＮの物理的トポロジ、およびＰＯＮとエッジ・ノードとの間の接続を考慮したＴＷＩＮの構成を作り出す。様々な方法には、内部ノードのＯＸＣおよびＯＡＤＭを構成する複数の工程を実行することが伴う。
【００２９】
ＴＷＩＮを設計するための様々な方法には、色の割当工程（Ｉ）、ツリー設計工程（ＩＩ）およびフローのルーティング工程（ＩＩＩ）を実行することが伴う。色の割当工程には、発信先の波長チャネルまたは色を、ＴＷＩＮの各エッジ・ノードに割り当てることが伴う。ツリー設計工程には、所与の物理的アーキテクチャと互換性がある仮想トポロジを判定する工程が伴う。特にこの工程には、ＰＯＮの物理的光路を判定し、仮想トポロジを決定するために、ＰＯＮの内部ノードのＯＸＣおよびＯＡＤＭを構成することが伴う。フロールーティング工程には、どのようにしてトラフィック・フローが、ツリー設計工程によって作り出された仮想トポロジにルーティングされるのかを判定することが伴う。フロールーティング工程は、どのようにしてトラフィックが様々な中間エッジ・ノードの中で分散されるのかを判定する。
【００３０】
Ｉ．色の割当
色の割当工程は、Ｗ個の発信先波長チャネルすなわち色をＮ個のエッジ・ノードに割当て、ここでＷとＮとは物理的アーキテクチャとＮ＞Ｗとによって定義される。色の割当は、所与のトラフィック・マトリクスＴによって定義される単一ホップの処理能力をほぼ最大化するように実行される。すなわち、色の割当工程は
【数１】
2008541615.tif 000003
をほぼ最大化し、その合計は、仮想トポロジの中の有向アークに対応するノードのペア（ａ、ｂ）だけを上回る。単一ホップの処理能力の最大化は、２つの制約を受ける。第１の制約は、各エッジ・ノードがＷ個までの近隣エッジ・ノードにしか通信トラフィックを光学的に送信することができないということである。したがって、トラフィック・マトリクスの各行では、Ｗよりも少ない数の要素が単一ホップのトラフィックからコントリビューションを得る。第２の制約は、選択されたエッジ・ノードのＷ個の近隣エッジ・ノードが、異なる発信先の色に割り当てられなければならないということである。したがって、発信先の色をトラフィック・マトリクスの列に関連付けることによって、各行の色のためトラフィック・マトリクスの列の中の１つのエントリだけが、単一ホップ・トラフィックのコントリビューションを得る。
【００３１】
色の割当工程を実施するための複数のアルゴリズムが存在する。
１つのアルゴリズムで、色の割当は色の結合プロセスによって作り出される。色の結合プロセスは、個別の色をトラフィック・マトリクスの各列に割当てることによって開始し、その後、ペアになるように列の色を結合する。各結合は、単一ホップ処理能力の連続損失が最も小さくなるように選択される。各発信元エッジ・ノードは、所与の色の１つのエッジ・ノードにしか光学的に送信することができないために、列の色の結合によって処理能力の損失が生じる。したがって、トラフィック・マトリクスの各行のために、２つの列の色の結合は、色が結合される列の要素のうちの１つが、単一ホップ・トラフィックのコントリビューションを得ないということを必要とする。結合される列の色は、単一ホップのトラフィックのコントリビューションの中でそのような損失を最小限にするように選択される。結合プロセスは、Ｗ個の列の色が残るまで、列の色の別のペアのために繰り返される。その後、残っている列の色は、関連したエッジ・ノードへの発信先の色の割当を提供する。
【００３２】
図８は、５つのエッジ・ノードと３つの波長チャネルすなわち色を有するＴＷＩＮのための、色の結合プロセスが進行するときの単一ホップのトラフィック・マトリクスに対するコントリビューションの展開を示す。プロセスの中で、トラフィック・マトリクスの列Ｔは最初に発信先の色、赤（Ｒ）、白（Ｗ）、青（Ｂ）、緑（Ｇ）および黄（Ｙ）に割り当てられる。第１の繰り返しで、プロセスは列４と列２との列の色を結合することを選択するので、列２と列４とは色ラベルＷを持つ。この列の色の結合の選択は、処理能力の連続損失が最も小さくなることにつながる。また列２と列４との色を結合することは、単一ホップの処理能力の連続損失を最小限にするように、各行の中の１つのエントリを「０」に設定することを必要とする。第２の繰り返しの中で、プロセスは列３と列２と列４との列の色を結合することを選択するので、列２〜４は色ラベルＷを持つ。この列の色の結合の選択は、処理能力の連続損失が２番目に小さいものとなることにつながる。列２、３および４の色を結合することもまた、単一ホップの処理能力の連続損失を最小限にするように、各行の中の１つのエントリを「０」に設定することを必要とする。この第２の繰り返しの後、３つの色だけが残るので、プロセスは停止する。結果として生じる列の色の割当から、エッジ・ノード１、２、３、４および５のための発信先の色の割当は、それぞれＲ、Ｗ、Ｗ、ＷおよびＹとなることがわかる。
【００３３】
第２の色の割当アルゴリズムで、整数線形プログラミング・アルゴリズムは、エッジ・ノードのための色の割当を作り出す。線形プログラミング・アルゴリズムは
【数２】
2008541615.tif 000004
を最大化するための任意の従来の方法を使用し、制約
【数３】
2008541615.tif 000005
＃１  および
を受ける。
【００３４】
この式では、Ｑはクロス・コネクト・マトリクスであり、ｕｋｂは根がエッジ・ノード「ｂ」である仮想トポロジの有向ツリー上の２値変数であり、γｋ（ａ，ｂ）はエッジ・ノード「ａ」からエッジ・ノード「ｂ」までの仮想トポロジの有向アークのための特性関数であり、Ｗは波長チャネルのセットであり、Ｖは物理的ＴＷＩＮトポロジのエッジ・ノードのセットである。マトリクス要素Qａｂは、物理的光路がエッジ・ノード「ａ」からエッジ・ノード「ｂ」に進む場合には「１」に等しく、それ以外の場合には「０」に等しい。２値変数ｕｋｂは、仮想トポロジのエッジ・ノード「ｂ」が発信先の色「ｋ」に割り当てられる場合には「１」に等しく、それ以外の場合には「０」に等しい。関数γｋ（ａ，ｂ）は、色「ｋ」を持つために構成されたエッジ・ノード「ａ」からエッジ・ノード「ｂ」への仮想トポロジの有向アークが存在する場合には「１」に等しく、それ以外の場合には「０」に等しい。
【００３５】
ＩＩ．ツリーの設計
ツリーの設計工程には、先のエッジ・ノードに発信先の色を割り当てることに基づいて、所与の物理的アーキテクチャの有向光路を選択することが伴う。有向ツリーでは、各発信先エッジ・ノードは、葉が発信先エッジ・ノードへの光学的な送信を行うことができるエッジ・ノードになっているツリーの根である。有向ツリーの枝は、葉から根まで物理的アーキテクチャの中を通っている光路である。個々の枝は、枝が根に近づいてゆくときに結合することができる。各々の色で分類された発信先エッジ・ノードのために、ツリーの設計工程は、根が発信先エッジ・ノードになっているツリーに物理的ノードを付加することによって、色で分類された有向ツリーを順次構築する。ツリーの設計段階は、単一ホップの処理能力を最大化し、物理的制約に従った仮想トポロジを実装する光路を見つけ出そうとする。物理的制約とは、最高の処理能力の仮想トポロジが実装されることを妨げるものであってもよい。
【００３６】
所与の物理的アーキテクチャ上に有向ツリーを形成するために、繰り返しアルゴリズムが利用可能である。これらのアルゴリズムの中で、各繰り返しには、候補となるノードのペアを選択し、その後、既存の波長で分類されたツリーと一致するやり方で、ノードのペアを接続する物理的光路を見つけ出そうとすることが伴う。そのような光路が見つけ出される場合、そのペアのための有向光路が既存のツリーに付加される。光路がエッジ・ノード「ａ」をエッジ・ノード「ｂ」に接続する場合、このプロセスは、仮想トポロジの中で「ａ」から「ｂ」に有向アークを付加することを含む。アルゴリズムは、Ｗが波長チャネルの数、すなわち色の数であるとして、各エッジ・ノードがＷ個の発信側有向アークに接続する仮想トポロジが得られるまで繰り返される。
【００３７】
アルゴリズムは、補助グラフの中で最短の光路を探すことによって、物理的光路を繰り返し形成する。光路は、所与のＰＯＮの内部ノードの中でＯＸＣおよび／またはＯＡＤＭを構成することによって形成される。アルゴリズムの間、補助グラフの有限コスト光路が、既存の波長で分類されたツリーと互換性を持つ光路に対応するように、補助グラフはＯＸＣ／ＯＡＤＭ制約を実施する。アルゴリズムはトラフィック・マトリクス要素Ｔａ，ｂを減少させる順序で、場合によっては既存のツリーに付加するために各ノードを選択する。すなわち、ツリーに接続するために可能性のあるノードを選択することは、単一ホップの処理能力の連続的な増加を最大化しようとする。アルゴリズムは以下の工程を有する。
【００３８】
最初に、各色のために、アルゴリズムはその色のエッジ・ノードの間で物理的光路の循環シーケンスを設定することを含む。循環経路が設定されると、補助グラフは循環経路のための適切なクロス接続を有するように更新される。各色について、ここで、その色のエッジ・ノードのペアはルーティングされ、かつ拒否されないものとみなされる。そのような循環光路を設定する工程は、最終的な仮想トポロジが接続されることを確実にする。各色のための補助グラフを通じて、そのような適切な循環シーケンスを設定するための助けとして、単純なアルゴリズムが利用可能である。そのアルゴリズムを使用するために、頂点がＶに属し、アーク（ｉ，ｊ）がＡにある場合にはアーク（ｊ，ｉ）もＡにあるように、有向アークがＡに属する有向グラフＧを考える。次に、対称正値コストＣｉｊをＡの中の各有向アークに関連付ける。
【００３９】
Ｕ⊂Ｖの場合、サブサイクル問題は、Ｕの中のすべてのノードを包含するＧの中でアークがばらばらになっているサイクルを見つけることであり、最小コストのサブサイクル問題は、コストが最小のサイクルを見つけることである。１つの色のエッジ・ノードのセットとしてＵを取り出すと、前記サイクルは前記エッジ・ノードを接続するための適切なサイクルを提供する。最小コストのサブサイクル問題に取り組むために、ｍがＵの中の要素の数であり、ｄ（ｉ，ｊ）がグラフＧの中のノード「ｉ」とノード「ｊ」との間の最小コスト経路のコストである、ｍ  ｘ  ｍマトリクス｛ｄ（ｉ，ｊ）｝ｉ，ｊ⊂Ｕを形成する。次に、最小コストのサブサイクル問題に対する解答を得るために、マトリクス｛ｄ（ｉ，ｊ）｝についての巡回セールスマン問題（ｔｒａｖｅｌｉｎｇ  ｓａｌｅｓｍａｎ  ｐｒｏｂｌｅｍ）（ＴＳＰ）を解く。次に、ＴＳＰに対する解答によって特定される順序で、Ｕの中のノードに接続するためにＧの中の最短の経路を使用することによって、その色のエッジ・ノードに望ましい適切なサブサイクルが生じる。ＴＳＰを発見的に解くためのいくつかの方法は、２つの最適サイクル、すなわちサイクルの区間を反転することによって長さが減少されることが不可能なサイクルを求める。２つの最適サイクルを求めるための１つの方法には、改良された２つの最適な解答が得られるまで、サイクル区間の適切な反転を繰り返し求めることが伴う。２つの最適な解答を見つけ出すことは、たとえそうした解答が、必ずしもコストが最小のものではなくても、サブサイクル問題の解答を見つけ出すためのそれ程複雑ではない方法を与えてもよい。
【００４０】
次にアルゴリズムは、各エッジ・ノードが１つの有向ツリーの根となっている、有向ツリーのセットを作り出すためのループを繰り返し実行することを含む。ループは、最大のトラフィック・マトリクス要素を有し、ルーティングも拒否もされていない残りのエッジ・ノードのペア（ｉ，ｊ）を選択することを含む。次にループは、ノード「ｉ」のトランスミッタからノード「ｊ」のレシーバまでの、補助グラフの最小コスト光路を見つけ出すことを含み、この光路は発信先ノード「ｊ」に割り当てられた波長を有する。光路のコストが有限である場合、光路は保持され、「ｉ」から「ｊ」までの有向アークが仮想トポロジの中に付加される。ループはまた、エッジ・ノードのペア（ｉ，ｊ）の経路を設定する物理的光路を示すために、補助グラフを更新することも含む。光路のコストが有限である場合、ループは拒否されるエッジ・ノードのペア（ｉ，ｊ）に印を付けることを含む。ループは、すべてのエッジ・ノードのペアがルーティングされるか、または拒否されるまで、仮想トポロジの新たなエッジ・ノードのペアのために繰り返される。
【００４１】
上記のアルゴリズムの中で、補助グラフを使用することは、ＯＸＣおよびＯＡＤＭが複数の出力光ファイバの間の入力波長チャネルを分割することがないように、共通波長チャネルを結合するためにＯＸＣおよびＯＡＤＭを構成することによる物理的光路の構築を可能にする。補助グラフを構築するために、ＴＷＩＮの物理的トポロジは、Ｖがノードのための頂点のセットであり、Ａがノードに接続する物理的光ファイバのための有向エッジのセットである有向グラフＧ（Ｖ，Ａ）によって表されてもよいことを思い出すことが有効である。各エッジ（ｉ，ｊ）∈Ａは、エッジ（ｉ，ｊ）を使用するためのコストを定義する重量Ｃｉｊに割り当てられる。コストは物理的リンク（ｉ，ｊ）の長さの測定値であってよく、または例えばファイバ、リピータおよび／またはアンプのコストを含んでもよい関連した物理的リンクを構築する、および／または操作するためのエッジのリソース値であってもよい。グラフＧ（Ｖ，Ａ）から、各波長チャネルｗ∈Ｗのために補助グラフＧ’Ｗ（Ｖ’，Ａ’）が作成され、ここでのＷはＴＷＩＮの利用可能な波長チャネルのセットである。補助グラフの中で、Ｖ’の各頂点は、波長チャネルｗ上のＴＷＩＮノードの入力（または出力）光ポートか、またはＴＷＩＮノードのアド・ポートまたはドロップ・ポートを表す。アド・ポートとドロップ・ポートとは、それぞれ発信元ノードのトランスミッタと発信先ノードのレシーバとを表してもよい。
【００４２】
物理的トポロジのために、グラフＧから１つの補助グラフＧ’Ｗを作るための転換は、以下で説明される。ｉ，ｊ∈Ｖである各エッジ（ｉ，ｊ）のために、対応する外部エッジ（ｖｉｏｕｔ（ｊ），ｖｊｉｎ（ｉ））∈Ａ’が重量Ｃｉｊを用いて作成され、ここでのｖｉｏｕｔ（ｊ）∈Ｖ’はノードｊに接続されているノード「ｉ」の出力ポートを意味し、ｖｊｉｎ（ｉ）∈Ｖ’はノードｉに接続されているノード「ｊ」の入力ポートを意味する。各ノードｋ∈Ｖのために、対応する内部エッジ（ｖｋｉｎ（ｉ），ｖｋｏｕｔ（ｊ））は重量Ｃｋ（ｉ，ｊ）を用いて作成され、ここで「ｉ」と「ｊ」とは、Ｇの中のノードｋに対する近隣ノードである。重量Ｃｋ（ｉ，ｊ）は、ノード「ｉ」および「ｊ」に接続された光ファイバのために、ポートに接続するノード「ｋ」の内部エッジを使用するためのコストとして機能する。直接エッジ・ノードに接続された各ノードｋのために、エッジ（ｖｋｉｎ（＋），ｖｋｏｕｔ（ｊ））は、ノードｋの各近隣ノードｊのための、（すなわちエッジ・ノードのトランスミッタの）アド・ポートからｖｋｏｕｔ（ｊ）までのリンクを表すために作成される。また、直接エッジ・ノードに接続された各ノードｋのために、エッジ・ノード（ｖｋｉｎ（ｊ），ｖｋｏｕｔ（−））は、ｖｋｉｎ（ｊ）を（すなわちエッジ・ノードのレシーバの）ドロップ・ポートに接続するリンクを表すために作成される。すべての内部重量Ｃｋ（＊，＊）は、最初に０に設定される。
【００４３】
補助グラフの重量のセット、すなわち｛Ｃｉｊ｝と｛Ｃｋ（ｉ，ｊ）｝とは、グラフの色の各々の新たな経路がツリー設計に付加されるときに更新される。更新は、物理的制約を実施する。例えば、波長ｗの光路が付加され、光路がノードｉ、ｋおよびｊをその順序で横断する場合、更新はｊ’≠ｊのための形態Ｃｋ（ｉ，ｊ’）のすべての内部重量を補助グラフＧ’ｗの中で無限大に設定する。そのような更新は、上述の方法が、その後に続くノード「ｋ」での異なる経路を備えた同じ波長ｗの光路を付加することを妨げ、それによって、２つの異なる出力ポート間で１つの波長の入力光路を分割することを回避する。
【００４４】
補助グラフはまた、仮想トポロジの有向ツリーを形成する間に、リソース使用を最小限にするために使用されることも可能である。例えば、リンク（ｉ，ｊ）を横断するために新たな光路が確立される場合、コストＣｉｊは、今後の経路が同一のマルチポイント対ポイントの有向ツリー上で結合するように促すために、ゼロに設定されることが可能である。
【００４５】
図９ａ〜９ｂは、例示的なＴＷＩＮの有向グラフ１０’’からの補助グラフの構築を示す。
図９ａを参照すると、例示的なＴＷＩＮは内部ノード１６’と光ファイバ１８’とエッジ・ノード（不図示）とを有する。例示的なＴＷＩＮの中で、各内部ノードは直接、対応するエッジ・ノードに接続している。内部ノード１６’はノード１、２、３，４、５，６として示され、またそれらの対応するエッジ・ノードに割り当てられた色、すなわちＲまたはＧによって分類される。例示的なＴＷＩＮは２つの波長チャネル、すなわち赤（Ｒ）および緑（Ｇ）での光通信を支援する。そのような通信のために物理的光路（ＬＰ）もまた概略的に示されており、例えばＲまたはＧなどの関連した有向ツリーの色、すなわち光路のための発信先エッジの色で分類される。
【００４６】
図９ｂは、図９ａで示されている例示的ＴＷＩＮ１０’’のノード１および２のための補助グラフの部分４０を示す。補助グラフは、波長チャネルのための両方の色を結合する。部分４０は内部ノード１および２と、便宜上ノード１および２の中で設定される対応するエッジ・ノード１４’とを含む。部分４０は入力および出力ポート（ｐ）、すなわちＶｉｎおよびＶｏｕｔを含み、内部および外部の物理的光ファイバ（点線の矢印）を示す。部分４０は、ポート（Ｐ）を通るエッジ・ノード１４’までの光路のルーティングを示す。
【００４７】
ＩＩＩ．フローのルーティング
ツリー設計工程は仮想トポロジ、すなわち｛Ｑａ，ｂ｝を決定するので、フローのルーティング工程は、この決定された仮想トポロジ上のトラフィック・フローを判定する。特に、発信元と発信先とのペアが与えられると、フローのルーティング工程は、所与の発信元から所与の発信先に通信を運ぶことができる経路に沿って、仮想トポロジの様々な有向アークの間でルーティングされるトラフィックの割合を判定する。フローのルーティング工程を実行するために、代替のプロセスが利用可能である。
【００４８】
第１の代替プロセスには、通信フローを、最短の経路を介して発信元エッジ・ノードから発信先エッジ・ノードへルーティングすることが伴う。この代替プロセスでは、フローのルーティングは、発信元エッジ・ノードから発信先エッジ・ノードに向かうために必要とされるホップの数を最小化するように選択される。
【００４９】
第２の代替プロセスには、輻輳量Ｃをほぼ最小化するようにフローのルーティングを定義することが伴う。輻輳Ｃは、任意の発信先エッジ・ノードの最大利用とみなされる。最小化は、実フロー変数のセット、すなわち｛Ｆｓｄ（ｉ，ｊ）｝に対する制約を前提として実行され、ここでＦｓｄ（ｉ，ｊ）とは、ノード「ｉ」からノード「ｊ」への物理的トポロジの有向アークＶ上の発信元ノード「ｓ」から発信先ノード「ｄ」へのトラフィック・フローである。ここで、トラフィック・マトリクスＴは波長当たりのデータ速度によって正規化されるので、各発信先に対する全フローは「１」よりも少ないか、または「１」に等しい。実フロー変数は、以下の通常のフロー制約を満たす。
【００５０】
ΣｉεｖＦｓｄ（ｉ，ｋ）−ΣｉεｖＦｓｄ（ｋ，ｊ）＝｛−Ｔｓ，ｄｉｆｋ＝ｓ，＋Ｔｓ，ｄｉｆｋ＝ｄ，０ｉｆｋ≠ｄ  ａｎｄ  ｋ≠ｓ｝
ここでのｓ、ｄ、ｉ、ｊおよびｋは、ＴＷＩＮの物理的トポロジの中のノードである。実フロー変数はまた、仮想トポロジの有向アーク上にあるように制限され、このことは仮想トポロジの中のアークによって接続される各ノードのペア（ａ，ｂ）について、Σｓ，ｄεｖＦｓｄ（ａ，ｂ）≦Ｑａ，ｂの制約を課す。最終的に、輻輳Ｃは任意の発信先エッジ・ノードの最大利用として定義されるので、輻輳は各物理的ノードｊεＶについてΣｓ，ｄεｖＦｓｄ（ｉ，ｊ）≦Ｃを満たさなければならない。通常、上記の制約を前提としてＣを最小化する実フロー変数のセットを判定するために、標準的な多種フロー・プログラムが使用されることが可能である。さらに、そうした方法は通常Ｃの値を判定する。Ｃの最小値が「１」よりも大きくない場合、最終的なフロールーティングの設計は、所与の物理的ネットワーク上で実行可能である。その後、１セットの関連した実変数｛Ｆｓｄ（ｉ，ｊ）｝のセットは、受信されたトラフィックがどのようにルーティングされるべきかを賢く判定するために中間エッジ・ノードが使用することができるフロー情報を提供する。
本開示、図面および特許請求の範囲から、本発明のその他の実施形態が当業者に明らかとなろう。
【図面の簡単な説明】
【００５１】
【図１】従来の時間領域インタリーブ化ネットワーク（ＴＷＩＮ）を示す図である。
【図２】ＴＷＩＮの例示的な実施形態を示す図である。
【図３】図２のＴＷＩＮの内部ノードの例示的な構成を示す図である。
【図４】図２のＴＷＩＮの１つのエッジ・ノードを示す図である。
【図５】図２に示されているＴＷＩＮの特定の実施形態の光路を示す図である。
【図６】図５に示されているＴＷＩＮの特定の実施形態に関連した仮想トポロジを示す図である。
【図７】例えば図２のＴＷＩＮなどの、接続されたＴＷＩＮの中で通信を送信する方法のための流れ図である。
【図８】色の結合プロセスがどのようにして例示的なトラフィック・マトリクスを転換するのかを示す図である。
【図９ａ】例示的なＴＷＩＮの中の色のルーティングを示す有向グラフを示す図である。
【図９ｂ】図９ａのＴＷＩＮに関連した補助グラフの部分を示す図である。
【図１】
2008541615.tif 000006
【図２】
2008541615.tif 000007
【図３】
2008541615.tif 000008
【図４】
2008541615.tif 000009
【図５】
2008541615.tif 000010
【図６】
2008541615.tif 000011
【図７】
2008541615.tif 000012
【図８】
2008541615.tif 000013
【図９ａ】
2008541615.tif 000014
【図９ｂ】
2008541615.tif 000015
【国際調査報告】
2008541615.tif 000016
2008541615.tif 000017