JP2007288280A - 同期光パケット交換ネットワークにおける波長割当最適化計算法及び波長割当制御による衝突回避方法 - Google Patents

Abstract

【課題】 本発明は，低コストであるが実用性がある，新しい概念に基づいた同期光パケット交換ネットワークにおける波長割当最適化計算法及び波長割当制御による衝突回避方法を提供することを目的とする。
【解決手段】 本発明は，基本的には，波長競合関係を整理する整理工程と，トランジットパケット間の波長競合を最小化する波長割当優先最適化を行う最適化工程と，システムの負荷に基づいた動的な波長割当制御を行う動的制御工程を含む工程により，（同期）光パケット交換ネットワークにおける衝突を回避するというものである。
【選択図】図１

Description

本発明は，同期光パケット交換ネットワークにおける波長割当制御による衝突回避方法，及びその衝突回避システムなどに関する。

光パケットスイッチネットワーク（ＯＰＳ）では，パケットコンテンション（パケット衝突）が重要な問題であり，システムの性能に大きな影響を与える。衝突は，ネットワークのスイッチノードにおいて，同じ波長を有する２つ以上の光パケットが同じ出力ポートから同時に去ろうとするときに，必然的に生ずる。衝突を解決するために，波長変換，光遅延ファイバを用いた光バッファリング，及び迂回ルーティングなどいくつかの手法が提案されている（たとえば，“S. Dixit, IP over WDM: building the next-generation optical Internet (John Wiley & Sons, 2003)”（下記非特許文献１）。しかし，波長変換装置や波長変換のためのレーザは，高価であり，また装置が複雑である。このような事情は，将来にわたって続くものと考えられる。
S. Dixit, IP over WDM: building the next-generation optical Internet (John Wiley & Sons, 2003).

本発明は，低コストであるが実用性がある，新しい概念に基づいた同期光パケット交換ネットワークにおける波長割当最適化計算法及び波長割当制御による衝突回避方法を提供することを目的とする。

本発明は，基本的には，(1)波長競合関係（wavelength competition relationship）を整理する整理工程と，(2)トランジットパケット間の波長競合を最小化する波長割当優先最適化を行う最適化工程と，(3)システムの負荷に基づいた動的な波長割当制御を行う動的制御工程を含む工程により，（同期）光パケット交換ネットワークにおける衝突を回避するというものである。すなわち，整理（refinement），最適化（optimization），及び動的制御（dynamic control）の工程 (ROD)を含むものである。よって，本明細書において，本発明により提案される方法やシステムをRODともよぶ。

より具体的には，本願の第１の側面に係る発明は，波長競合関係を整理するための整理工程と，トランジットパケット間の波長競合を最小化する波長割当優先最適化を行うための最適化工程と，システムの負荷に基づいた動的な波長割当制御を行う動的制御工程と，を含む光パケット交換ネットワークに用いられる衝突回避方法に関する。

本願の第１の側面に係る発明の好ましい態様は，前記整理工程は，送信ノードが異なるパケットが、光パケットネットワーク交換の同じリンクで同じ波長を用いる競合関係にあるかどうか判断する競合関係検討工程を含む方法である。

本願の第１の側面に係る発明の好ましい態様は，前記最適化工程は，トラフィック分散情報を光パケットスイッチに伝えるトラフィック分散情報伝達工程と，前記光パケットスイッチが，前記トラフィック分散情報に基づいて，最適な順に波長を再整列し波長に優先順位をつける最適波長決定工程と，を含む方法である。

本願の第１の側面に係る発明の好ましい態様は，前記動的制御工程は，前記動的制御工程は、前記整理工程で競合関係がないと判断されたパケットに対しては、前記最適化工程で整列された最優先の波長を割当て、前記整理工程で競合関係があると判断されたパケットに対しては、前記最適化工程で整列された波長からネットワークのパケット量に応じて決められた複数の波長を優先順位の順に選択し、その中から順に利用可能な波長を調べて波長を割当てる、方法である。

本願の第２の側面に係る発明は，波長競合関係を整理するための整理手段と，トランジットパケット間の波長競合を最小化する波長割当優先最適化を行うための最適化手段と，システムの負荷に基づいた動的な波長割当制御を行う動的制御手段と，を具備する光パケット交換ネットワークに用いられる衝突回避システムである。

本願の第２の側面に係る発明の好ましい態様は上記のシステムを含むルータである。

本願の第２の側面に係る発明の好ましい態様は，上記のシステムを含む光ネットワークである。

RODは，後述するシミュレーションにより示されるとおり，従来の純粋優先順位波長割当（pure-PWA: X. Wang, H. Morikawa and T. Aoyama, "Priority-based wavelength assignment for burst switched WDM optical networks," IEICE Trans. Commun., E86-B, 5, 1508-1514 (2003).）に比べて，システムのパフォーマンスが極めて上昇することがわかる。このシステムは，特に，パケット損失率が０．０１以下であることが要求される場合に，従来の波長変換方式によるネットワークと同等のパフォーマンスを有するものである。よって，本発明によれば，コストを抑えた高性能なシステムやそのシステムに用いられる方法を提供できることとなる。

図1は，本発明のノードアーキテクチャを示す概略図である。スイッチの光部分，入力ポートのヘッダ抽出部は，ヘッダを解読するために入力された光を分光して少量抽出する。ヘッダ処理回路は，パケットの最初にあるプリアンブルを解読し，ヘッダ情報を読み出す。ヘッダ処理回路は，スイッチや同期を取るために入力したパケットのタイミング情報を制御装置に伝える。出力ポートのヘッダ修飾部は，パケットのヘッダを整理する。

スロット（同期）ネットワークにおいては，全てのパケットは同じサイズを有する。固定サイズの時間スロットは，ペイロードとヘッダを有する。そのタイムスロットは，保護時間（guard time）を設けるためにパケットの全体よりも長期間とされる。入力ポートに到着する全ての入力パケットは，スイッチに入る前にお互いに同じ位相に調整されなければならない。入力パケットシンクロナイザーと出力パケットシンクロナイザーは，入力ポートから入力し，出力ポートから出力される全てのパケットを一列に並べるために用いられる。システム初期化段階では，異なる入力間の遅延の相違を競合するために同期が行われ，システムの動作時間を通してその状況が維持される。

本発明において必ずしも必要とされないが，付加的な要素として，光ファイバ遅延線と波長変換器が用いられてもよい。例えば，光ファイバ遅延線バッファと波長変換器はノード内でシェアする様に配置されてもよい。そうすると，それらはお互いの入力ポートからアクセスできることとなる。

OPSネットワークは，パケットに基づくスイッチングを光学的に行うことが望まれる。しかしながら，エンドツーエンドの接続を形成するために他のタイプのインターフェイスを用いる必要がある。他のネットワーク（特にクライアントネットワーク）は，しばしば電気的なネットワークである。これは，OPSネットワークの“エッジ”において，インターフェイスが必要であることを意味する。パケットがクライアントネットワーク（電気的ネットワーク）から到着するとき，OPSネットワークに送信される前に電気的なパケットを光学的なフォーマットに変換する必要がある。この変換は，クライアントインターフェースで実行さる。スイッチの電気−光学インターフェイス部分で，いくつかの最初の先入れ先出し（FIFO）バッファが含まれる。各々のバッファは，同じ目的地に向かうパケットを溜める。バーストモードの送信機と受信器は，クライアントネットワークインターフェースに設けられる。それらは，電気−光，光−電気変換を高速に行う。それらは，高速に調整可能であることが好ましい。それらを調整するために用いられる時間は，スロットの継続時間に比べて短いことが好ましい。超高速で調整できるバーストモードの送信機と受信器はとても高価なので，各々のノードにおかれる送信機と受信器の数を少なくしてもよい。

コントローラは，電気的に動作する多機能の制御装置である。コントローラは，好ましくは，入力したそれぞれのパケットのヘッダ部を観測し，スイッチの出力ポートにおける全ての波長の状態をモニターする。それらの情報に基づいて，波長割当やパケット転送のスケジュールを計算し，パケットの衝突を解消し，スイッチを制御し，パケットのヘッダを付け換えるなどを行う。

図1のノードアーキテクチャは，たとえば，ＩＰルータなどとして利用されうる。本発明のシステムは，波長競合関係を整理するための整理手段と，トランジットパケット間の波長競合を最小化する波長割当優先最適化を行うための最適化手段と，システムの負荷に基づいた動的な波長割当制御を行う動的制御手段と，を具備する光パケット交換ネットワークに用いられる衝突回避システムである。このシステムは，整理手が波長競合関係を整理し，最適化手段がトランジットパケット間の波長競合を最小化する波長割当優先最適化を行い，動的制御手段がシステムの負荷に基づいた動的な波長割当制御を行う。これにより，上述したとおり光パケット交換ネットワークにおける衝突を回避するというものである。

[光パケットルーティング装置]
光パケットルーティング装置であって，前記光パケットルーティング装置に入力される光パケットを電気信号に変換するためのＯ／Ｅ変換手段と，前記Ｏ／Ｅ変換手段が変換した電気信号に基づき，前記光パケットルーティング装置に入力される光パケットのヘッダ部を検知し，ヘッダ部に含まれる情報を検出するためのヘッダ部検出手段と，前記ヘッダ部検出手段が検出した光パケットのヘッダ部に関する情報に基づいて，当該光パケットのヘッダ部に対応する光ラベルを生成するための光ラベル生成手段と，前記Ｏ／Ｅ変換手段が変換した電気信号を，パラレル信号に変換するためのシリアル／パラレル変換手段と， 前記シリアル／パラレル変換手段が変換した電気信号の伝送速度を調整するための伝送速度調整手段と，前記伝送速度調整手段が伝送速度を調整した電気信号を光信号に変換するためのＥ／Ｏ変換手段と，前記光ラベル生成手段が生成する光ラベルと，前記Ｅ／Ｏ変換手段が変換する光信号とを合わせ光信号を生成する光信号生成手段とを具備する光パケットルーティング装置によって実現される。

[光パケット交換ネットワーク]
図２は，光パケット交換ネットワークの基本構成を示す図である。図２に示されるように，光パケット交換ネットワーク（21）は，基幹ノード（22）を含む基幹ネットワーク(23)と，基幹ネットワークの外部の光パケット通信用のネットワークであるメトロネットワーク（24）と，基幹ネットワークとメトロネットワークを連結するエッジノード(25)とを含む。

そして，エッジノード（25）は，光パケットがメトロネットワーク（24）から基幹ネットワーク（23）へ進入する際の光パケットルーティング装置である進入エッジノードと，光パケットが，光パケットが基幹ネットワーク（23）からメトロネットワーク（24）へ出る際の光パケットルーティング装置である退出エッジノードとを含む。

メトロネットワーク(24)では，例えば，単一波長からなる光パケットを用いて光情報が伝達されている。そして，その光パケットは，宛先などの情報を含むヘッダ部と，伝送しようとする内容に関するデータを含むペイロード部とからなる。

本発明のネットワークは，たとえば，光パケットルーティング装置として，上述したシステムを採用するので，低コストで好ましいパフォーマンスをもって衝突を回避できる。

[システムモデル]
本発明による方式及びシステムを検証するために，以下のシステムをモデルとした。なお，全てのタイミング等の制御はコントローラなどの制御部によって行われればよい。制御部は，プログラマブルロジックデバイスなどのハードウェアによって実装されてもよい。また，所定の制御プログラムを搭載したソフトウェアと，ＣＰＵ，演算部，メモリ，入出力部，各要素を接続するバスなどによって構成されていてもよい。ＣＰＵは，入力部からの入力信号に応じて，制御プログラムを読み出し，制御プログラムの指令を受けて，入力部から入力された信号や，メモリに格納される各種情報を読み出して，演算部に各種演算を行わせ，演算結果をメモリに格納するとともに，出力部から適宜制御指令などを出力するようにすればよい。なお，制御プログラムとして，本明細書に開示される各ステップを実現するプログラム，ヘッダ情報を抽出又は調整するプログラム，各種信号のタイミングを制御するプログラムなどがあげられる。N個の光パケットスイッチが双方向ファイバリンクと接続され，任意トポロジーの光パケットスイッチネットワーク(OPS)を構築する。それぞれのファイバには，M波長が含まれる。OPSネットワークのエッジには，IPクライアントネットワークが接続される。エッジノードでは，多くのバッファ(subqueue)が入力される。そして，それぞれのバッファ(subqueue)バッファは，同じ目的地向けのパケットとされる。それぞれのバッファのパケット長は，Ｑとして表され，それはパケット単位とされる。それぞれのノードは，Ａ個の波長チューニング可能な転送装置と10Gb/sでのバースト受信器（burst receiver）を備えている。チューニングの時間は，スロットの継続時間（slot duration）に比べて短いものと仮定する。スロットネットワーク（slotted networks）において，パケットは，スイッチングノードに入力する前にアラインされるものとし，12,000bitに固定した。簡単のため，それぞれのパケットがひとつの1.2マイクロ秒スロットにおかれるものとした（詳細なノード構成については，非特許文献１“S. Dixit, IP over WDM: building the next-generation optical Internet (John Wiley & Sons, 2003).”を参照のこと）。

それぞれのノードは，スロットベースでスロットにおける全ての波長と全ての転送物の状態（フリーかビジーか）を観測できるとする。これは，ラムダ観測（lambda monitoring）とよばれる（A. Carena, et al., "RingO: an experimental WDM optical packet network for metro applications," JSAC, 22, 8, 1561-1571 (2004).）。転送パケットとローカルインプットパケットとの衝突は，ローカルインプットパケットをバッファ(subqueue)バッファに，電気的に入力することにより避けるものとする。バッファ(subqueue)の間のパケット転送は，“ラウンドロビン（round robin）”方式により計画されるものとする。転送パケット衝突（transit packet contention）や受信器での衝突（receiver contention）が起こった場合，単純なラウンドロビンドロップ（round robin drop）方式を用いるものとする。議論を簡単にし，焦点を波長割当に集中させるため，パケットのルートは，最短なパスに固定されるものとした。

[波長競合関係整理]
まずは，限られた波長資源を効果的に用いるため波長競合関係を整理する。波長競合関係整理するために，基本的には，ルートを検証することで衝突する可能性のないパケットを把握し，そのパケットについては異なる波長を割り当る必要がないと判断する。そして，衝突する可能性のあるパケットについては，できるだけ異なる波長を割り当てるようにする。この波長の割当については，衝突の生ずる可能性を算出した上で行う。これらの制御は，コントローラなどの制御部からの制御信号に従って行えばよい。本モデルでは，衝突を表すグラフをＧ_C＝（Ｖ_C，Ｅ_C）とした。ここで，グラフＶ_Cにおける各ノードは，ネットワークにおけるバーチャルパスに相当する。二つの隣接するノードにおける双方向のリンクを示すＥ_Cは，潜在的な波長衝突（wavelength contention）の問題を避けるための，異なる波長であることを要求する波長競合関係をあらわす。この競合関係はマトリックス[ｇ_ij]によってあらわされる。もし，バーチャルパスｉとｊとの間に競合がある場合は，[ｇ_ij]は１であり，そうでない場合は[ｇ_ij]は０である。競合関係の整理過程は，図３と図４とに示される。図３は波長競合整理を示すシュードコードである。図４は，整理後の波長競合関係を説明するための概念図である。図４(a)は，整理前のネットワークを示し，図４(b)は整理後の衝突グラフＧ_C（conflict graph）を示す。

波長競合関係を整理する目的は，全てのパケットの間で，波長競合関係を最も少なくするためである。なお，衝突関係とは，ソースノードと目的ノードの組み合わせが異なるパケット間で生じうる波長競合関係を意味する。パケットは，同じ波長のものが同時に同じファイバに存在する場合に，衝突しうる。一般的に，異なるパケット間の衝突関係はグラフによって表現できる。このグラフを，Ｇ_p＝（Ｖ_p，Ｅ_p）とする。Ｖ_pは頂点の組を示し，｜Ｖ_p｜＝Ｎである。Ｅ_pはリンクのセットを示す。この様子は，ネットワークを表す図４（ａ）に示される。図４（ａ）のグラフにおける頂点Ｖ_p（０〜３）は，ネットワークにおけるノードに相当する。そして，２つの頂点の間の端部は，２つのノード間のファイバに相当する。パケットのルートは，グラフＧ_pにおける仮想パスに相当するので，ネットワークにおけるルートの組合わせは，グラフＧ_pにおける仮想バスの組合わせに相当する。すると，図４（ｂ）に示すような任意の衝突グラフＧ_C＝（Ｖ_C，Ｅ_C）を設計できる。もしも，２つの仮想パスがグラフＧ_pにおけるあるエッジを共有する場合，その２つの仮想パスの間で衝突関係が生ずる。グラフＧ_Cにおける対応するノードは，進行方向とは異なるエッジにより連結される。なお，図４（ａ）のグラフを整理せず，そのまま変換すると，図４（ｃ）に示されるような仮想パス間での衝突関係を示すグラフとなる。

すなわち，以下のようにして波長競合関係を整理すればよい。光パケットのソースノートど目的ノードの組合せから最も短いパスを計算する（ステップ１）。この計算は公知の方法により達成することができる。もともとのネットワークを示すグラフＧ_pから衝突グラフＧ_Cを作成する（ステップ２）。グラフＧ_pから衝突グラフＧ_Cを作成するためには，グラフＧ_pに含まれる各ノードに相当する頂点と，各頂点を結ぶルートを把握すればよく，容易に衝突グラフＧ_Cを作成できる。衝突グラフＧ_Cを全てのノードの組合せ（ｉ，ｊ）についてのこの競合関係をマトリックス[ｇ_ij]で表現する。なお，いずれの [ｇ_ij]も初期値は０となるように初期化する。仮想パスの組合せに相当する衝突グラフＧ_Cのそれぞれのノードの組合せ（ｉ，ｊ）についてインデックスｉに相当する仮想パスについてのリンクの組であるＸと，インデックスｊに相当する仮想パスについてのリンクの組であるＹとを準備する(ステップ３)。ＸとＹとに含まれる要素は，それぞれ仮想パスに沿ったリンクである。その後，図３に示すようなシュードコードを用いて波長関係を最適化する。

すなわち，ＸとＹとに同じ要素が含まれていなければ，[ｇ_ij]を０，すなわち衝突が生じないとし；また，Ｘの最初のリンクがＹに含まれるか，又はＹの最初のリンクがＸに含まれる場合も[ｇ_ij]を０，すなわち衝突が生じないとし；それら以外の場合は[ｇ_ij]を１，すなわち衝突が生じうるとする。

より具体的に説明すると，波長競合関係を整理するためには，あるネットワークに含まれる各ノードを把握する。好ましくは各ノードに符号をつける。そして，各ノードの間のルートを把握する。次に，複数の光パケットのソース（出発）ノードと，目的ノードとを把握する。その上で，光パケットの最短となるパスを把握する。その際に，どのノードを経由するかについても把握する。その上で，他の光パケットと衝突が起こりうるかどうか判断する。すなわち，衝突は，同じ経路（ファイバ）に同じ波長の光パケットが同時に入った場合に生じうるので，まずは，最短となるパス同士に共通のパスが含まれるかどうか判断する。そして，共通のパスがないのであれば，衝突は生じない。また，例えば，２つの光パケットについて検討すると，それら２つの光パケットのソースノードは異なることが前提であるから，いずれかの光パケットの最初のパスが相手のパスに含まれる場合は，衝突は生じないとする。すなわち，本発明の波長競合関係を整理する工程では，上記のような検討を各光パケットについて行い，望ましくは全ての光パケットについて最短の経路で波長衝突が生じ得ないようにする。

[波長割当優先順位最適化（Wavelength Assignment Priority Optimization）]
次に，整理された波長競合関係に基づいて，潜在的な波長衝突を最小限にするために，限られた波長資源を割当てる。この最適化工程を通して，それぞれのバーチャルパスに対応して優先波長リスト（wavelength priority list）が作成される。それぞれのバーチャルパスにおいて，次の優先順位のためにＭ波長が準備される。衝突を起こす可能性が最も低いので，優先順位が最も高い波長が最も好ましい。この波長割当最適化工程では，好ましくは，トラフィック分散情報を用いる。GMPLSのOSPF-TE/IS-IS-TE のような拡張内部ゲートウェイプロトコル（Extended Interior Gateway Protocols）を用いれば，トラフィック分散情報をそれぞれの光パケットスイッチへと通知できる。簡単のために，ここでは，トラフィック情報が知られているものとした。

最適化とサブルーティンプロセスとを，それぞれ図５と図６とに示す。図５は，最適化プロセスを示すシュードコードであり，図６はサブルーティンプロセスを示すシュードコードである。符号ｐ，ｐ’は，バーチャルパスを示す。ωは，波長を示す。ｔ_pは，バーチャルパスｐのトラフィック量を示す。Ｐの集合は，競合関係を有する全てのバーチャルパスを含む。Ｐ_lは，Ｐのサブセットであり，リンクｌを通るバーチャルバスを含む。Ｌｐは，バーチャルパスｐに沿ったリンクのリストを示す。Ψは，全ての波長の集合を示す。Ψは１からMのインデックスを有するM個の波長を含む波長の集合を示す。Ψｐはバーチャルパスｐの割当てられた波長を含む集合である。ΨｐはΨに含まれる。Δ^w _lは，それぞれのサブルーティン最適化後に更新され，次の最適化まで定常状態として利用される，リンクｌにおける波長ｗについてのそれぞれの最適化による現在の蓄積負荷を記憶する可変トラフィック量（traffic load variable）を示す。λ^w（_p,l）は，リンクｌを通過するバーチャルパスｐにおける波長割当を示す２値数を示し，ｐはＰ_lに含まれる。そして，バーチャルパスｐがリンクｌに波長ｗを通過させる場合，λ^w（_p,l）は１となり，その他の場合は０となる。θ^w _pは，バーチャルパスｐに波長ｗが割当てられる場合に１となり，それ以外の場合は０となる２値数を示す。図６中の式(５)は，バーチャルパスｐにおける波長ｗの衝突可能性を示す。衝突を避けるために，C^w _pの小さい波長ｗを選択する。

波長割当優先順位を最適化するためには，具体的には以下のようにすればよい。
まず，初期化を行う（ステップ１）。すなわち，全ての仮想パスについてΨｐに何も含まれないとし，全ての波長ｗ及び全てのリンクｌについて，可変トラフィック量Δ^w _lを０とする。λ^w _(p,l)を０とする。θ^w _p を０とする。このステップを式で表すと以下のようになる。

全てのリンクｌ上の全ての波長ｗについて，現在累積トラフィック量の小さい波長ｗをを選択する。全てのリンクｌの全ての波長ｗについてのトラフィック量を合計する。すなわち、下記サブルーティンに従って波長割当の優先度を計算する。一回の計算でそれぞれの仮想パスについて，選択された波長を記録する。一度選択された波長が，次回の計算で再び選択されないように制約を設定する。次回の波長割当のために，それぞれの波長におけるトラフィック量を更新する（ステップ２）。このステップを式で表すと以下のようになる。

次に，上記の解放と制約とを記憶する（ステップ３）。このステップを式で表すと以下のようになる。

ステップ２に戻り，それをM回繰り返す（ステップ４）。上記のようにして，最適化を終える（ステップ５）。

上記各ステップの意味を簡単に説明すると，ステップ１は初期化工程である。そして，ステップ２は，好ましくは，下記サブルーティンで計算を行い，衝突可能性の低い波長を選択するための工程である。目標とする評価値は上記式（５）である。ステップ３は，ステップ２での一回の計算結果を記録し，各バーチャルパスに一本の波長ｗを割当するための工程である。その後，Δ^w _lを更新し，また，次回の計算のために，λ^w（_p,l）をリセットする。更新されたΔ^w _lの上にもう一度ステップ２を行い，衝突可能性を計算することで，別の波長を選択してもよい。このとき選択された波長は，それほど最適な波長とはいえない。しかし，この選択された波長を記憶しておくことが好ましい。このようにM回ステップ２，及びステップ３を繰り返して，各バーチャルパスに波長割当のリストを得ることができる。なお，最後に計算して得られた波長は，一番混雑な波長といえる。

上記のステップ２は，最適化するために以下のサブルーティンとされてもよい。すなわち，以下の帰納的サブルーティンである。

Ｐに含まれるバーチャルパスをホップ（hops）の数により降順にソートする（ステップ１）。ただし，全てのω,p及びlについて，λω_(p,l)について初期値を０とする。

最初からバーチャルパスpを選択し，式（１）の衝突係数Ｃω_pが最も小さいバーチャルパスについて波長ωを選択する（ステップ２）。ただし，全てのωは，Ψ−Ψｐに含まれるものとする。この波長は，式（５）Ｃω_pの最小値を満たす。

ωを前記バーチャルパスｐの選択された波長としたときに，Ｌ_pに含まれる全てのｌに関しλω_(p,l)を１とし，Θω_(p)を１とする（ステップ３）。

上記ステップ２に戻り，Ｐに含まれるすべてのバーチャルパスに対して波長が割り当てられるまで最適化を繰り返す（ステップ４）。これが終わった後に，このサブルーティンを終える（ステップ５）。

[トラフィック量に基づいた動的波長割当制御]
純粋ＰＷＡでは，望ましい波長が得られない場合，得られるのであれば次に優先順位の高い候補がすぐさま割当てられる。実際，最も優先順位の高い波長いつも得られるとは限らないし，最も好ましい波長がパケットに割当てられるとは限らない。したがって，従来の波長割当最適化方法は，必ずしも効率的ではない。本発明では，パケットを保持して，好ましい波長が得られるまで待つことにより，それぞれのパケットに対する好ましい波長利用性を改良する。パケットは他のパケットと競合関係を有するので，波長は，波長選択空間の中から，最も優先順位の高い波長から選択される。もしバッファに含まれるパケットの数が増加した場合，例えばより高い負荷の下では，波長選択空間は拡大されるか，さもなければ，縮小される。この波長選択空間の大きさは，関数T(x)により決定されうる。ここで，x（0＜ｘ＜Ｑ）は，バッファにおける現在のパケット数を示す。そして，T(x)は，式(2)に示されるように，波長選択空間の大きさとなる。式(2)において，オペレーション└X┘はXより大きくない最大の整数とする関数である。他のパケットと競合関係を持たないパケットに対しては，波長はＭ個の波長の中からランダムに選択される。

パケットは，優先順位の順に並べられている。そして，バッファ中のパケット数がＱ／Mより小さい場合は，波長検索空間は１となる。すなわち，バッファ中の最初のパケットだけが，最も高い優先順位として割り当てられる。一方，バッファ中のパケット数が増加した場合は，たとえば，Ｑ／M＜ｘ＜２Ｑ／Mの場合は，波長検索空間は２となり，もしも利用可能であるならばバッファ中の最初のパケットがもっとも高い優先順位として割り当てられ，そうでないならば2番目に優先順位の高い波長が利用可能であるならば割り当てられる。バッファ中のパケットの数が増えるにつれて，すなわち，パケット負荷が増えるにつれて，波長検索空間は大きくなる。もしも，（M−１）Ｑ／M＜ｘの場合は，M個すべての波長が割り当てのために検索されることとなる。波長は，優先順位順に割当て調査がなされる。一方，パケット負荷が減少した場合は，バッファ中のパケットも減少する。そして，他の波長との衝突関係が最も好ましい波長を割り当てることに集中するため,波長検索空間も次第に小さくなる。このようなメカニズムは，パケット転送を保持することやよりよい波長を割り当てるために効果的に用いることができる。そして，このようなメカニズムは，ネットワークの光学的部分や退出エッジノードにおいて衝突が起こる事態を減少させる。さらには，波長検索空間，がシステムの負荷に応じて動的に調整される。すなわち，システムの負荷が変われば，それに応じて波長割り当てのポリシー（方式），すなわち波長検索空間が変換する。一方，他のパケットと衝突とは関連しない送信源と宛先の間のパケットは，利用可能な波長の中からランダムに割り当てられることとなる。

[シミュレーション結果]
シミュレーションは，非特許文献1に開示されるものと同様のNSFNETトポロジーに基づいて行った。それぞれのリンクのファイバ長を36km（およそ100個のタイムスロット）と仮定した。トラフィックは一様であり，パケット到着はポアソンプロセス(Poisson process)とした。本シミュレーションでは，ＲＯＤを3つのスキームと比較した。すなわち，(1)ランダムな波長割当て（Ｒａｎｄ）;(2)上述した純粋ＰＷＡ（pureＰＷＡ）及び(3)完全な波長変換方式（Conv）である。これらの3つのスキームは，動的な波長割当制御を行わない。平均パケット送出率（すなわち，それぞれの送信器（transmitter）における，単位時間あたりに送出されるパケットのビット数をリンク速度で除した値）に対する パケット損失率と，平均遅延という観点から，パフォーマンスを比較した。その際，それぞれパラメータＭ，Ｑ及びＡを変えた。パラメータを変えたそれぞれのケースは「スキーム-ＭａＱｂＡｃ」とラベルをつけた。ここで，ａは波長の数を示し，ｂはバッファの長さを示し，ｃは送信器又は受信器の数を示す。得られた結果の一部を以下に示す。

図７は，M=16, Q=100, A=8の場合のパケット損失率を示す。一方，図８は，M=16, Q=100, A=8の場合の平均遅延を示す。表１は，許容されるパケット損失率が０．０１の場合の，平均パケット送出率の上限を示す。負荷が軽い場合，ＲＯＤは，動的波長割当制御パケットがネットワークにおいて衝突を軽減できる好ましい波長をバッファで待つことができるので，波長変換を行うケース（Conv）よりもよいパフォーマンスを有する。したがって，ＲＯＤは，低いパケット損失率を達成できる。図８に示されるように，遅延に対する性能は犠牲になるが，キューイングによりもたらされる遅延は，遅延を考慮する場合に最大の要素である長距離リンクの伝播遅延に比べると無視できる程度である。さらに，ＲＯＤにとって好ましいバッファ長が，それほど長くないことを確認した。すなわち，バッファ長を相当長くした場合，システムのコストが高くなるが，ＲＯＤの性能をそれほど向上させない。

本発明のシステムは，波長のアクセスと衝突を避けるため，上記した整理及び波長割当優先順位最適化工程に基づいて，ネットワークの電気部分のローカルバッファを使用する。すると，ネットワークの光部分における衝突が軽減され，動的な波長割当制御スキームを当てはめることでネットワークの電気部分と光部分との接続問題を解決するバランスをとることができる。シミュレーションは，ＲＯＤが，システムの性能を相当向上させることを示した。０．０１以下のパケット損失率が要求される場合においても，ＲＯＤは，波長変換において，コストを軽減できる基本システムであるといえる。

本発明は、非同期の光パケット交換システムに適用することはもちろん、GMPLSなどの制御技術を用いた光パスネットワークの波長割当技術にも利用できる。すなわち、本発明は、光情報通信などの分野で利用されうる。

図1は，本発明のノードアーキテクチャを示す概略図である。 図２は，光パケット交換ネットワークの基本構成を示す図である。 図３は波長競合整理を示すシュードコードである。 図４は，整理後の概念図である。図４(a)は，整理後のネットワークを示し，図４(b)は整理後の衝突グラフを示す。図4(c)は、整理しない衝突グラフを示す。 図５は，最適化プロセスを示すシュードコードである。 図６はサブルーティンプロセスを示すシュードコードである。 図７は，M=16, Q=100, A=8の場合のパケット損失率を示す。 図８は，M=16, Q=100, A=8の場合の平均遅延を示す。

符号の説明

21 光パケット交換ネットワーク
22 基幹ノード
23 基幹ネットワーク
24 メトロネットワーク
25 エッジノード

Claims (8)

1. 波長競合関係を整理するための整理工程と，
   トランジットパケット間の波長競合を最小化する波長割当優先最適化を行うための最適化工程と，
   システムの負荷に基づいた動的な波長割当制御を行う動的制御工程と，
   を含む光パケット交換ネットワークに用いられる衝突回避方法。
2. 前記整理工程は，
   送信ノードが異なるパケットが、光パケットネットワーク交換の同じリンクで同じ波長を用いる競合関係にあるかどうか判断する競合関係検討工程を含む請求項１に記載の方法。
3. 前記最適化工程は，
   トラフィック分散情報を光パケットスイッチに伝えるトラフィック分散情報伝達工程と，
   前記光パケットスイッチが，前記トラフィック分散情報に基づいて，最適な順に波長を再整列し波長に優先順位をつける最適波長決定工程と，
   を含む請求項１に記載の方法。
4. 前記動的制御工程は、
   前記整理工程で競合関係がないと判断されたパケットに対しては、前記最適化工程で整列された最優先の波長を割当て、
   前記整理工程で競合関係があると判断されたパケットに対しては、前記最適化工程で整列された波長からネットワークのパケット量に応じて決められた複数の波長を優先順位の順に選択し、その中から順に利用可能な波長を調べて波長を割当てる、
   請求項1に記載の方法。
5. 前記整理工程は，
   送信ノードが異なるパケットが、光パケットネットワーク交換の同じリンクで同じ波長を用いる競合関係にあるかどうか判断する競合関係検討工程を含み；
   前記最適化工程は，
   トラフィック分散情報を光パケットスイッチに伝えるトラフィック分散情報伝達工程と，
   前記光パケットスイッチが，前記トラフィック分散情報に基づいて，最適な順に波長を再整列し波長に優先順位をつける最適波長決定工程と，
   を含み；
   前記動的制御工程は，
   前記整理工程で競合関係がないと判断されたパケットに対しては、
   前記最適化工程で整列された最優先の波長を割当て、前記整理工程で競合関係があると判断されたパケットに対しては、前記最適化工程で整列された波長からネットワークのパケット量に応じて決められた複数の波長を優先順位の順に選択し、その中から順に利用可能な波長を調べて波長を割当てる、
   請求項１に記載の方法。
6. 波長競合関係を整理するための整理手段と，
   トランジットパケット間の波長競合を最小化する波長割当優先最適化を行うための最適化手段と，
   システムの負荷に基づいた動的な波長割当制御を行う動的制御手段と，
   を具備する光パケット交換ネットワークに用いられる衝突回避システム。
7. 請求項6に記載のシステムを含むルータ。
8. 請求項6に記載のシステムを含む光ネットワーク。
   
   

Images