(57)【要約】【課題】可変長パケットで優先制御を行なってパケットの棄却率を低減することのできる、非同期到着する可変長パケットのバッファリング装置とその方法を提供する。【解決手段】伝送されたデジタル信号のパケットを一時的に保管する複数の遅延素子からなるキューと、上記のパケットを上記の複数の遅延素子に振り分ける第１の光スイッチと、上記の複数の遅延素子を通過したパケットを選択して出力に振り向ける第２の光スイッチと、パケットの優先度と長さとを読み出す読み出し手段と、その読み出された優先度と長さとにより、第１の光スイッチと第２の光スイッチとを制御するバッファ管理装置と、を、備え、上記の読み出し手段と第１の光スイッチとの間に有るパケットを棄却する場合は第１の光スイッチを用いて棄却し、第１の光スイッチと第２の光スイッチとの間に有るパケットを棄却する場合は第２の光スイッチを用いて棄却する。【選択図】図６
2004236236.tif 000002
【特許請求の範囲】
【請求項１】
伝送されたデジタル信号のパケットを一時的に保管する複数の遅延素子からなるキューと、
上記のパケットを上記の複数の遅延素子に振り分ける第１の光スイッチと、
上記の複数の遅延素子を通過したパケットを選択して出力に振り向ける第２の光スイッチと、
パケットの優先度と長さとを読取る読取り手段と、
その読み出された優先度と長さとにより、第１の光スイッチと第２の光スイッチとを制御するバッファ管理装置と、
を、備え、
上記の読取り手段と第１の光スイッチとの間に有るパケットを棄却する場合は第１の光スイッチを用いて棄却し、第１の光スイッチと第２の光スイッチとの間に有るパケットを棄却する場合は第２の光スイッチを用いて棄却することを特徴とする非同期到着する可変長パケットのバッファリング装置。
【請求項２】
伝送されたデジタル信号のパケットを一時的に保管する複数の遅延素子からなるキューと、
上記のパケットを上記の複数の遅延素子に振り分ける第１の光スイッチと、
パケットの優先度と長さとを読取る読取り手段と、
その読み出された優先度と長さとにより、第１の光スイッチを制御するバッファ管理装置とを備える非同期到着する可変長パケットのバッファリング装置のバッファリング方法であって、上記のキューには予め決められた閾値が設けられており、上記のキューに新たなパケットを追加する際に、上記のキューに格納されたパケットの並びについて、
１）上記のキューに格納されたパケットのバッファ占有量が上記の閾値を越えなければ、優先度に関わらず、上記のキューに格納されたパケットの並びの最後方にその追加するパケットを格納し、
２）上記のキューに格納されたパケットのバッファ占有量が上記の閾値をこえる場合であって、
２Ａ）その追加するパケットが、上記のキューに格納されたパケットのどれよりも優先度の低いパケットの場合は、上記のキューに格納されたパケットの並びの最後方にその追加するパケットを格納し、
２Ｂ）その追加するパケットに比べて優先度が同等か高いパケットが、上記のキューに格納されたパケットの中にある場合には、その優先度が同等か高いパケットの次の後方にその追加するパケットを格納して、その格納する位置に、より優先度の低いパケットがあれば、そのパケットを棄却して格納し、
２Ｃ）その追加するパケットが、上記のキューに格納されたパケットのどれよりも優先度の高いパケットの場合は、上記の閾値を越えて格納されているパケットの並びの最後方にその追加するパケットを格納するが、その格納する位置に、より優先度の低いパケットがあれば、そのパケットを棄却して格納することを特徴とする非同期到着する可変長パケットのバッファリング方法。
【請求項３】
伝送されたデジタル信号のパケットを一時的に保管する複数の遅延素子からなるキューと、
上記のパケットを上記の複数の遅延素子に振り分ける第１の光スイッチと、
パケットの優先度と長さとを読取る読取り手段と、
その読み出された優先度と長さとにより、第１の光スイッチを制御するバッファ管理装置とを備える非同期到着する可変長パケットのバッファリング装置のバッファリング方法であって、上記のキューには予め決められた複数の閾値が設けられており、それらの閾値について、昇順に並べられたそれぞれの閾値は、昇順あるいは降順にならべられた単数あるいは連続する複数の優先度に対応付けられているものとし、それぞれの閾値に属する優先度は、そのそれぞれの単数あるいは連続する複数の優先度の最も優先する優先度とするとき、
上記のキューに新たなパケット（Ｐａ）を追加する際に、
０）上記のキューに格納された最後方のパケットが上記の複数の閾値のいずれにも届かない場合には、優先度に関わらずパケットの並びの最後方にその追加するパケット（Ｐａ）を格納し、
１）上記のキューに格納された最後方のパケット（Ｐｒ）が上記の複数の閾値のいずれか（Ｔｈａ）により分断される様に配置しているか、その最後方のパケット（Ｐｒ）の最後尾が上記の閾値（Ｔｈａ）に一致している場合に、優先度に関わらず、上記のキューに格納されたパケットの並びの最後方にその追加するパケットを格納し、
２）上記のキューに格納されたパケットのバッファ占有量が前記閾値（Ｔｈａ）をこえていて、最後方のパケットが前記閾値（Ｔｈａ）を分断される様に配置されていない場合であって、
２Ａ）その追加するパケット（Ｐａ）が、上記のキューに格納されたパケットのどれよりも優先度の低いパケットの場合は、上記のキューに格納されたパケットの並びの最後方にその追加するパケット（Ｐａ）を格納し、
２Ｂ）その追加するパケット（Ｐａ）が上記閾値（Ｔｈａ）に対応づけられた優先度以上に優先されるパケットであって、上記のキューの上記閾値より後方に、上記閾値（Ｔｈａ）に対応づけられた優先度以上に優先されるパケット（Ｐｂ）が格納されたパケットの中にある場合には、そのパケット（Ｐｂ）の次の後方にその追加するパケット（Ｐａ）を格納するが、その格納する位置に、上記閾値（Ｔｈａ）に対応付けられた優先度以下で優先されないパケット（Ｐｃ）があれば、そのパケット（Ｐｃ）を棄却して追加するパケット（Ｐａ）を格納し、
２Ｃ）その追加するパケット（Ｐａ）が、上記閾値（Ｔｈａ）に対応づけられた優先度以上に優先されるパケットであって、上記のキューの上記閾値より後方に上記閾値（Ｔｈａ）に対応づけられた優先度以上に優先されるパケットが、格納されたパケットの中にない場合には、上記閾値（Ｔｈａ）で分断されるパケットの後方にその追加するパケットを格納するが、その格納する位置に、上記閾値（Ｔｈａ）に対応付けられた優先度以下で優先されないパケット（Ｐｃ）があれば、そのパケットを棄却して格納し、
２Ｄ）その追加するパケット（Ｐａ）が、上記閾値（Ｔｈａ）に対応づけられた優先度以下で優先されないパケットであれば、上記のキューに格納されたパケットの並びの最後方にその追加するパケット（Ｐａ）を格納することを特徴とする非同期到着する可変長パケットのバッファリング方法。
【請求項４】
請求項２の非同期到着する可変長パケットのバッファリング方法で動作する請求項１に記載の非同期到着する可変長パケットのバッファリング装置。
【請求項５】
請求項３の非同期到着する可変長パケットのバッファリング方法で動作する請求項１に記載の非同期到着する可変長パケットのバッファリング装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、バッファ容量やその保持時間に限りがある光回路を用いて、多様な長さのパケットを用いた光通信を実現する、非同期到着する可変長パケットをバッファリング方法に関している。
【０００２】
【従来の技術】
多量の情報を効率的に伝送できる光通信技術の進展に伴ない、さらに高いスループットを実現するために、伝送路だけでなくパケット交換にも光技術が導入されつつある。一般に、パケット交換では、パケット転送処理が行われ、これには、パケットスイッチが用いられる。このためのパケットスイッチの機能は、（１）宛先検索、（２）交換、（３）バッファ管理、（４）バッファリング、（５）経路制御、の５つに大きく分類できる。一般には、上記の（２）あるいは（４）の機能を光化したパケットスイッチが光パケットスイッチと呼ばれる。これは、光スイッチと光バッファで構成されて、データを光信号のまま転送することにより、広帯域特性をもつ。さらに、最近では、多波長ラベル処理や光符号ラベル処理などの光アナログ処理によって、上記の（１）宛先検索を高速で処理できるようになった。これらのラベル処理を光スイッチと組合せると、超高性能の１入力×Ｎ（自然数）出力の光パケットスイッチが構成できる。以下では、上記の（１）、（２）および（４）の機能を光のまま処理するパケットスイッチを光パケットスイッチと呼ぶ。
【０００３】
また、上記の（３）バッファ管理を改善することにより、光パケットスイッチの転送能力をさらに改善することができる。従来、この（３）バッファ管理には、電子回路による論理回路を用いてきた。これは、実用レベルにある光論理回路がないためである。
【０００４】
バッファ管理の目的のひとつは、パケットの衝突を防止することである。パケット交換ネットワークでは、同時にパケットがパケットスイッチに到着した場合には、バッファにパケットを格納して衝突を回避する。図１は、一般的に用いられるバッファの状態を表すキューを示す図である。例えば、現在のインターネットでは、図１のように、優先制御を行なわないパケット転送が行なわれている。パケットスイッチに到着したパケットは、優先度に関係なく、バッファに空きがあればそれに格納される。
【０００５】
また、上記のバッファには、半導体メモリが使われることが多い。しかし、半導体メモリを用いない光パケットスイッチでありながら、バッファをもった光バッファ制御実装方式が、非特許文献１、あるいは、非特許文献２に報告されている。
【０００６】
既に知られている光バッファには、長さの異なる複数の光ファイバが用いられている。これは、遅延時間の異なる光遅延素子であり、その遅延時間の間、蓄えられる。この光遅延線に割当てるパケットを制御することで、パケット同士の衝突を回避できることは知られている。この際、任意時刻でのパケット取り出しができないため、出力時のパケットの衝突を防ぐ必要があり、このため、光バッファに入れるに当たり、何らかのバッファ管理手法を用いて遅延時間を管理する必要があった。
【０００７】
また、図２に、従来の光パケットスイッチアーキテクチャの例として、Ｎ入力×Ｎ出力光パケットスイッチのＮ個の１入力×Ｎ出力バッファレスパケットスイッチとＮ個のＮ入力×１出力バッファからなる構成を示す。それぞれの１入力×Ｎ出力スイッチとＮ入力×１出力バッファは実質的に格子状に接続される。上記の１入力×Ｎ出力パケットスイッチの性能を十分に発揮するＮ入力×Ｎ出力パケットスイッチを構成するためには、同時に到着する複数のパケットも充分に短い時間で処理することが必要であり、それゆえ、計算量の少ないバッファ管理方式の適用が重要である。
【０００８】
上記の、１入力×Ｎ出力バッファレスパケットスイッチでは、非特許文献８に記載されているように、光宛先検索機能により高速宛先検索が可能である。その結果、Ｎ入力×Ｎ出力光パケットスイッチは高ノードスループットを示す。しかし、パケットの衝突を避け、棄却率を改善するためにはバッファが必要であり、Ｎ入力×Ｎ出力パケットスイッチの各出力ポートにＮ入力×１出力バッファが接続されている。
【０００９】
また、最近、多様なアプリケーションの出現によってネットワークによる優先制御の提供が望まれている。これは、パケットに優先度を設けて伝送するものであり、優先度の低い場合は、棄却される場合もある。このような優先パケット転送を実現するバッファ管理方式には、部分バッファ共有方式（ＰＢＳ；Ｐａｒｔｉａｌ  Ｂｕｆｆｅｒ  Ｓｈａｒｉｎｇ）、プッシュアウト方式（ＰＯ；  Ｐｕｓｈ  Ｏｕｔ）等があり、これらについては非特許文献３に記載されている。
【００１０】
部分バッファ共有方式（ＰＢＳ）では、図３に示す様に、バッファ内パケット数が閾値を超える場合には新たに到着する非優先パケットのバッファへの格納を許さない。バッファ内パケット数の管理は一つの変数（キュー長）で行なっており、パケットの到着と時間の経過に応じてその値を変化させる。ＰＢＳでは、キュー長、すなわち、キューに入るパケット長の和（あるいはパケット数）について閾値が予め定められる。キュー長が閾値よりも小さければ、すべてのパケットはキューに入る。一方、キュー長が閾値以上であれば、優先パケット（以降、廃棄レベル１のパケット）のみがキューに格納され、非優先パケット（廃棄レベル２）は棄却される。その変数の変更に要する計算量は少なく、比較的短い時間でパケット処理が可能である。この方式では、優先転送制御を行なわない方法による転送と比べると、全体のパケット棄却率がかなり大きくなる。しかし、優先度の高いパケットの棄却率を優先度の低いパケットの棄却率よりも低くすることが可能である。
【００１１】
また、プッシュアウト方式（ＰＯ）方式では、バッファが一杯の時に、優先度の高いパケットが到着すると、すでにバッファにある優先度の低いパケットを追いだして格納する。それによって、ＰＢＳと同様に優先度の高いパケットの棄却率を優先度の低いパケットの棄却率よりも低くすることが可能である。また、ＰＢＳよりも全体のパケット棄却率が小さく、優先制御をしない場合と同じ性能を達成できる。しかし、ＰＯ方式では、パケット数を管理するだけでなく、どこに非優先のパケットがあるかを管理する必要があり、バッファ内パケットの管理が複雑である。この管理では、非優先のパケットの所在情報は、どのパケットを棄却するの判断に使われるだけでなく、棄却されたパケットがあった位置をつめ、それより後方に位置する優先パケットを前方につめ、最後方に到着した優先パケットを格納する処理にも使われる。
【００１２】
従来の電子バッファを持つルータやＡＴＭスイッチでは、バッファを複数に分割し、それぞれを一つのキューとして管理するバッファ管理方法が知られている。このバッファ管理方法を用いた複数キュー方式は、キューを個々に管理し、バッファ管理装置が同時に取り出すパケットは、一つのキューからのものに制限するため、優先制御に有効な方式である。
【００１３】
一方、この複数キュー方式を、光ファイバ遅延線バッファによる複数キューによって実現するのは難しい。これは、それぞれの光ファイバ遅延線バッファでは固有の遅延時間のみが許されるためである。
【００１４】
また、単一キューによる方法としては、上記に説明した部分バッファ共有方式（ＰＢＳ）が既に知られている。また、単一キューによる他の優先制御方式としては、ＨＯＬ（Ｈｅａｄ−ｏｆ−ｔｈｅ−Ｌｉｎｅ）優先キュー制御が非特許文献４に、また、プッシュアウト方式（ＰＯ：Ｐｕｓｈ  Ｏｕｔ）が非特許文献３に記載されている。前記のＨＯＬ優先キュー制御方式あるいはプッシュアウト方式（ＰＯ）では、パケットの優先度に関わらずバッファのすべてを共有するので、それらの方式では光バッファの使用効率は高くなる。ただし、ＨＯＬ方式では、廃棄レベル１のパケットが到着すると、キュー内にある非優先パケットは一つずつ後にずらされる。また、ＰＯ方式では、バッファが一杯の時に優先パケットが到着すると、キュー内で一番後にある非優先パケットが棄却され、それより後方の優先パケットが一つずつ前に移動する。このため、最大キュー長をＢとすると、上記のＨＯＬ優先キュー制御方式あるいはプッシュアウト方式（ＰＯ）では、いずれの場合も、アルゴリズムに従った計算量は、Ｂに依存した値になる。このように計算量が比較的多いことはバッファ管理の速度低下を招き、光パケットスイッチを伝送速度の高い領域で使用する場合は、簡単なＰＢＳ方式の方がＨＯＬあるいはＰＯ方式と比べてより有効である場合が多い。
【００１５】
次に、可変長パケットであるが優先制御を行なわないバッファ管理法についてより具体的に説明する。この方法については、既によく知られている。たとえば、非特許文献６にラウンドロビンスケジューリングを加えた以下の方法によって管理できる。
【００１６】
図２に示した出力バッファ型のＮ入力×Ｎ出力のパケットスイッチでは、Ｎ入力×１出力の光バッファとＮ個の１入力×Ｎ出力のスイッチを用いる。伝送量が増加した場合、Ｎ入力×１出力の光バッファに同時に最大Ｎパケットが到着する可能性がある。
【００１７】
これらのパケットの衝突（重ね合わせ）を防止するために、遅延線バッファを用いる。この場合、すべてのパケットをバッファに格納するには、Ｎ個のパケットの遅延を求める処理を最小パケット長に相当する時間ｌｍｉｎ以内に行わねばならない。すなわち、１パケットの処理の許容時間は、ｌｍｉｎ／Ｎである。この時間は、単純なラウンドロビンに従ってバッファリングをする場合の１パケットの処理時間と同等である。これは、ラウンドロビンスケジューリングによって、バッファ管理を行なうことができることを示している。
【００１８】
図４（ａ）に４入力×１出力の光バッファ構成を示す。この場合はＮ＝４である。光遅延素子で構成された光バッファは、ファイバ遅延線を用いたＢ個の光遅延素子、Ｎ×（Ｂ＋１）個の光スイッチ、バッファ管理装置より構成される。Ｂ個のファイバ遅延線｛ｄ０、ｄ１、・・・、ｄＢ−１｝は、それぞれ、遅延線の単位長Ｄの倍数｛０、Ｄ、・・・、（Ｂ−１）×Ｄ｝の長さを持つ。また、バッファ管理装置からの信号により、ラウンドロビンスケジューリングは、Ｔ時間ごとに繰り返すものである。このため、バッファ管理装置は、前段の光スイッチからＴ時間以上前の離れた時点でパケットの情報を受け取り、この前もって設けた時間Ｔの間に、この情報を使って、Ｎ個のパケットのそれぞれに必要な遅延時間を求めるものである。時間Ｔの間に、連続して到着するパケットを処理する必要があることから、Ｔ≦ｌｍｉｎを満たさねばならない。たとえば、図４（ａ）に示すように、４個のパケットが到着し、バッファ管理装置により、パケットＡ、Ｂ、Ｃはそれぞれ、遅延線ｄ０、ｄ２、ｄ３に格納され、パケットＤは棄却されるものとする。このような制御は、バッファ管理装置が前段の光スイッチを駆動することで実現する。図４（ｂ）に、パケットＡが遅延線ｄ０に切替えられた直後の出力ポートから見たパケットの位置を示す。図４（ｃ）に示すようにパケットＡ、Ｂ、Ｃは衝突することなく出力される。この例では、パケットＢがパケットＡよりも先にバッファに到着するが、到着するパケットはラウンドロビンで順次処理されるため、図４（ｃ）に示した順序で出力される。
【００１９】
以下に、バッファ管理装置の振舞いを図５のフローチャートにしたがって具体的に述べる。バッファ管理装置は、内部あるいは出力時のパケット衝突を避ける処理をする。ここで、ラウンドロビンの繰り返し時間Ｔの間のあらかじめ決められた時点ｔ０から、光バッファ中のすべてのパケットがバッファを出る時点までの時間ｔｆをｆとする。以降で、ｆをバッファ占有量と呼ぶ。バッファ管理装置は、周期Ｔごとに、すべてのポートに到着したパケットの遅延時間を求める。同一周期内に到着したパケットに与える遅延時間を、ポートｋ＝１、２、・・・、Ｎの順に求める。ポートｋにパケット長ｌｋのパケットが時点ｔ０を原点として時間ｔｋで到着したとする。衝突回避のためにパケットに与えられるべき遅延時間ｔは、ｔ＝ｆ−ｔｋである。ここで、遅延線バッファは、離散時間特性を持つことを考えると、パケットは、次の時間遅延されるべきであることがわかる。（図５のＦ１）
【００２０】
【数１】
2004236236.tif 000003
【００２１】
ここで、関数Ｃｅｉｌ（ｘ）は、ｘの少数点以下を切り上げた整数をあらわす。Δｋ＜Ｂであれば、そのパケットをΔｋ番目の遅延線に格納する（Ｆ２）。また、Δｋ≧Ｂであれば、そのパケットを棄却する。このように一部は棄却し、他は格納するパケットであるので、それに応じてバッファ占有量ｆを更新する必要が生じる。そこで、パケットを格納する時には（Ｆ４）、
【００２２】
【数２】
2004236236.tif 000004
【００２３】
とｆを更新する。棄却されるポートを除いて、全ポートのパケットの遅延を求めた後、さらにｍａｘ（ｆ−Ｔ、０）を新たなバッファ占有量ｆとして更新し（Ｆ１１）、Ｔ時間後の次のラウンドロビン周期のパケット処理に備える。
【００２４】
この様に光遅延線バッファを用いると、ポートｋに到着したパケットは、その直前に格納されたパケット、すなわち、ポートｋに到着したパケットの遅延をもとめる際に用いられるｆで示された時間に出力されるパケットとは、次の間隔をもつ。
【数３】
2004236236.tif 000005
【００２５】
この間隔が大きい場合は、バッファに無駄な空きが生じるので、棄却率が増加することが予想される。一方、Ｄを小さくして間隔を詰める場合には、バッファを有効利用できるが、バッファの長さＢ×Ｄが小さくなり格納できるパケットの数が少なくなるので、棄却率が増加することが予想される。したがって、遅延線の単位長Ｄの大きさが、通信の品質を定める重要なパラメータとなる事がわかる。
【００２６】
また、可変長パケットで優先制御を行なうバッファ管理法については、ＰＢＳを拡張した方法が非特許文献７にＷＡ／ＴＤとして提案されている。このＷＡ／ＴＤは、ＰＢＳを可変長非同期に適用したものであるが、ポート間の処理順や、周期を区切ることは明記されていない。以下では、このバッファ管理法を用いた方式をｖＰＢＳ方式と称する。
【００２７】
ｖＰＢＳ方式ではＰＢＳ方式と同じく、閾値より後方には優先度の低いパケットを格納することは許さない。このため、優先度の高いパケット棄却率を優先度の低いパケット棄却率より小さくすることができるという利点はあるが、優先制御を行なわないバッファ制御であるため、本発明に比べてパケット棄却率が大きくなる。
【００２８】
【非特許文献１】
葉原  敬士、三条  広明、西沢  秀樹、小川  育夫、須崎  泰正、“波長ルーチング型大容量光パケットスイッチの開発”、  電子情報通信学会技術研究報告（ＳＳＥ９９−１４８），  ２０００年２月．
【非特許文献２】
Ｄａｖｉｄ  Ｋ．  Ｈｕｎｔｅｒ  ａｎｄ  Ｍｅｏｗ  Ｃ．  Ｃｈｉａ  ａｎｄ  Ｉｖａｎ  Ａｎｄｏｎｏｖｉｃ，  “Ｂｕｆｆｅｒｉｎｇ  ｉｎ  ＯｐｔｉｃａｌＰａｃｋｅｔ  Ｓｗｉｔｃｈｅｓ”，  ＩＥＥＥ／ＯＳＡ  Ｊｏｕｒｎａｌ  ｏｆ  Ｌｉｇｈｔｗａｖｅ  Ｔｅｃｈｎｏｌｏｇｙ，  Ｖｏｌ．  １６，  Ｎｏ．  １２，ｐｐ．  ２０８１−２０９４，  Ｄｅｃｅｍｂｅｒ  １９９８．
【非特許文献３】
Ｙ．  Ｌｉｎ  ａｎｄ  Ｊ．  Ａ．  Ｓｉｌｖｅｒｓｔｅｒ，  “Ｐｒｉｏｒｉｔｙ  Ｑｕｅｕｉｎｇ  Ｓｔｒａｔｅｇｉｅｓ  ａｎｄＢｕｆｆｅｒＡｌｌｏｃａｔｉｏｎ  Ｐｒｏｔｏｃｏｌｓ  ｆｏｒ  Ｔｒａｆｆｉｃ  Ｃｏｎｔｒｏｌ  ａｔ  ａｎ  ＡＴＭ  Ｉｎｔｅｇｒａｔｅｄ  ＢｒｏａｄｂａｎｄＳｗｉｔｃｈｉｎｇ  Ｓｙｓｔｅｍ”，  ＩＥＥＥ  Ｊｏｕｒｎａｌ  ｏｎ  Ｓｅｌｅｃｔｅｄ  Ａｒｅａｓ  ｉｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，  Ｖｏｌ．  ９，Ｎｏ．  ９，  ｐｐ．  １５２４−１５３６，  Ｄｅｃｅｍｂｅｒ  １９９１
【非特許文献４】
Ｌ．  Ｋｌｅｉｎｒｏｃｋ，  Ｑｕｅｕｅｉｎｇ  ｓｙｓｔｅｍｓ  Ｖｏｌｕｍｅ  ＩＩ：  Ｃｏｍｐｕｔｅｒ  ａｐｐｌｉｃａｔｉｏｎｓ．  ＡＷｉｌｅｙ−Ｉｎｔｅｒｓｃｉｅｎｃｅ  Ｐｕｂｌｉｃａｔｉｏｎ，  １９７６．
【非特許文献５】
Ｓ．  Ｌ．  Ｄａｎｉｅｌｓｅｎ  ａｎｄ  Ｂ．  Ｍｉｋｋｅｌｓｅｎ  ａｎｄ  Ｃ．  Ｊｏｅｒｇｅｎｓｅｎ  ａｎｄ  Ｔ．  Ｄｕｒｈｕｕｓ  ａｎｄ  Ｋ．Ｅ．  Ｓｔｕｂｋｊａｅｒ，  “ＷＤＭ  Ｐａｃｋｅｔ  Ｓｗｉｔｃｈ  Ａｒｃｈｉｔｅｃｔｕｒｅｓ  ａｎｄ  Ａｎａｌｙｓｉｓ  ｏｆ  ｔｈｅ  Ｉｎｆｌｕｅｎｃｅ  ｏｆＴｕｎａｂｌｅ  Ｗａｖｅｌｅｎｇｔｈ  Ｃｏｎｖｅｒｔｅｒｓ  ｏｎ  ｔｈｅ  Ｐｅｒｆｏｒｍａｎｃｅ”，  ＩＥＥＥ／ＯＳＡ  Ｊｏｕｒｎａｌ  ｏｆＬｉｇｈｔｗａｖｅ  Ｔｅｃｈｎｏｌｏｇｙ，  Ｖｏｌ．  １５，  Ｎｏ．  ２，  ｐｐ．２１９−２２７，  Ｆｅｂｒｕａｒｙ  １９９７．
【非特許文献６】
Ｆ．  Ｃａｌｌｅｇａｔｉ，  “Ｏｐｔｉｃａｌ  ｂｕｆｆｅｒｓ  ｆｏｒ  ｖａｒｉａｂｌｅ  ｌｅｎｇｔｈ  ｐａｃｋｅｔｓ，”ＩＥＥＥＣｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｌｅｔｔｅｒｓ，  ｖｏｌ．  ４，  ｐｐ．  ２９２−２９４，  Ｓｅｐｔｅｍｂｅｒ  ２０００．
【非特許文献７】
Ｆ．  Ｃａｌｌｅｇａｔｉ，  Ｇ．  Ｃｏｒａｚｚａ，  ａｎｄ  Ｃ．  Ｒａｆｆａｅｌｌｉ，  “Ｅｘｐｌｏｉｔａｔｉｏｎ  ｏｆ  ＤＷＤＭ  ｆｏｒｏｐｔｉｃａｌ  ｐａｃｋｅｔ  ｓｗｉｔｃｈｉｎｇ  ｗｉｔｈ  ｑｕａｌｉｔｙ  ｏｆ  ｓｅｒｖｉｃｅ  ｇｕａｒａｎｔｅｅｓ，”  ＩＥＥＥ  Ｊｏｕｒｎａｌ  ｏｎＳｅｌｅｃｔｅｄ  Ａｒｅａｓ  ｉｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，  ｖｏｌ．  ２０，  ｐｐ．  １９０−２０１，  Ｊａｎｕａｒｙ  ２００２．
【非特許文献８】
Ｎ．  Ｗａｄａ，  Ｈ．  Ｈａｒａｉ，  Ｗ．  Ｃｈｕｊｏ，  ａｎｄ  Ｆ．  Ｋｕｂｏｔａ，  “Ｐｈｏｔｏｎｉｃ  ｐａｃｋｅｔ  ｒｏｕｔｉｎｇ  ｂａｓｅｄｏｎ  ｕｌｔｉｗａｖｅｌｅｎｇｔｈ  ｌａｂｅｌ  ｓｗｉｔｃｈｉｎｇ  ｕｓｉｎｇ  ｆｉｂｅｒ  Ｂｒａｇｇ  ｇｒａｔｉｎｇｓ，”  ＥＣＯＣ  ２０００Ｔｅｃｈｎｉｃａｌ  Ｄｉｇｅｓｔ  （２６ｔｈ  Ｅｕｒｏｐｅａｎ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｏｐｔｉｃａｌ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ），  ｖｏｌ．  ４（Ｎｏ．  １０．４．６），  ｐｐ．  ７１−７２，  Ｓｅｐｔｅｍｂｅｒ  ２０００．
【００２９】
【発明が解決しようとする課題】
上記のように、可変長パケットで優先制御を行なうバッファ管理法については、既に報告された例があるが、棄却率を低減する余地がまだ残っている。
【００３０】
この発明は上記に鑑み提案されたもので、可変長パケットで優先制御を行なってパケットの棄却率を低減することのできる、非同期到着する可変長パケットのバッファリング装置とその方法を提供することを目的とする。
【００３１】
【課題を解決するための手段】
上記目的を達成するために、第１の発明は、非同期到着する可変長パケットのバッファリング装置に関しており、伝送されたデジタル信号のパケットを一時的に保管する複数の遅延素子からなるキューと、上記のパケットを上記の複数の遅延素子に振り分ける第１の光スイッチと、上記の複数の遅延素子を通過したパケットを選択して出力に振り向ける第２の光スイッチと、パケットの優先度と長さとを読取る読取り手段と、その読み出された優先度と長さとにより、第１の光スイッチと第２の光スイッチとを制御するバッファ管理装置と、を、備え、上記の読取り手段と第１の光スイッチとの間に有るパケットを棄却する場合は第１の光スイッチを用いて棄却し、第１の光スイッチと第２の光スイッチとの間に有るパケットを棄却する場合は第２の光スイッチを用いて棄却することを特徴としている。
【００３２】
また、第２の発明は、伝送されたデジタル信号のパケットを一時的に保管する複数の遅延素子からなるキューと、上記のパケットを上記の複数の遅延素子に振り分ける第１の光スイッチと、パケットの優先度と長さとを読取る読取り手段と、その読み出された優先度と長さとにより、第１の光スイッチを制御するバッファ管理装置とを備える非同期到着する可変長パケットのバッファリング装置に摘要するバッファリング方法であって、
上記のキューには予め決められた閾値が設けられており、上記のキューに新たなパケットを追加する際に、上記のキューに格納されたパケットの並びについて、
１）上記のキューに格納されたパケットのバッファ占有量が上記の閾値を越えなければ、優先度に関わらず、上記のキューに格納されたパケットの並びの最後方にその追加するパケットを格納し、
２）上記のキューに格納されたパケットのバッファ占有量が上記の閾値をこえる場合であって、
２Ａ）その追加するパケットが、上記のキューに格納されたパケットのどれよりも優先度の低いパケットの場合は、上記のキューに格納されたパケットの並びの最後方にその追加するパケットを格納し、
２Ｂ）その追加するパケットに比べて優先度が同等か高いパケットが、上記のキューに格納されたパケットの中にある場合には、その優先度が同等か高いパケットの次の後方にその追加するパケットを格納して、その格納する位置に、より優先度の低いパケットがあれば、そのパケットを棄却して格納し、
２Ｃ）その追加するパケットが、上記のキューに格納されたパケットのどれよりも優先度の高いパケットの場合は、上記の閾値を越えて格納されているパケットの並びの最後方にその追加するパケットを格納するが、その格納する位置に、より優先度の低いパケットがあれば、そのパケットを棄却して格納することを特徴としている。
【００３３】
【発明の実施の形態】
以下にこの発明の実施の形態を図面に基づいて詳細に説明する。以下においては、同等の機能を有する装置等については同じ符号を用いるものとする。まず、可変長パケットで優先制御を行なうバッファ管理法について説明する。
【００３４】
説明を分かり易くするために、ひとつの例として、優先度が高い優先度１のクラスと優先度が低い優先度２のクラスとバッファへ格納するパケット数についての閾値があるものとする。さらに多くの優先度を想定した場合については、下記と同様の様式で容易に拡張することができる。このバッファ管理法では、次のようにする。
【００３５】
１）まず、すでにバッファに格納されているパケットによるバッファ占有量が閾値を越えていなければ、優先度に関わらず到着したパケットをキューの最後方に格納する。
【００３６】
２）一方、占有量が閾値をこえる場合には、クラス２のパケットはキューの最後方に格納される。クラス１のパケットは、閾値を越えて格納されているクラス１のパケットの最後方に格納される。その位置にクラス２のパケットがあれば、そのパケットは棄却される。棄却されたパケットは上書きされたと見なされる。
【００３７】
これをより一般化すると次の様になる。まず、すでに上記のキューに格納されたパケットの並びがあり、
キューには予め決められた複数の閾値が設けられており、上記のキューには予め決められた複数の閾値が設けられており、それらの閾値について、昇順に並べられたそれぞれの閾値は、昇順あるいは降順にならべられた単数あるいは連続する複数の優先度に対応付けられているものとし、それぞれの閾値に属する優先度は、そのそれぞれの単数あるいは連続する複数の優先度の最も優先する優先度とするとき、上記のキューに新たなパケット（Ｐａ）を追加する際に、
０）上記のキューに格納された最後方のパケットが上記の複数の閾値のいずれにも届かない場合には、優先度に関わらずパケットの並びの最後方にその追加するパケット（Ｐａ）を格納し、
１）上記のキューに格納された最後方のパケット（Ｐｒ）が上記の複数の閾値のいずれか（Ｔｈａ）により分断される様に配置しているか、その最後方のパケット（Ｐｒ）の最後尾が上記の閾値（Ｔｈａ）に一致している場合に、優先度に関わらず、上記のキューに格納されたパケットの並びの最後方にその追加するパケットを格納し、
２）上記のキューに格納されたパケットのバッファ占有量が前記閾値（Ｔｈａ）をこえていて、最後方のパケットが前記閾値（Ｔｈａ）を分断される様に配置されていない場合であって、
２Ａ）その追加するパケット（Ｐａ）が、上記のキューに格納されたパケットのどれよりも優先度の低いパケットの場合は、上記のキューに格納されたパケットの並びの最後方にその追加するパケット（Ｐａ）を格納し、
２Ｂ）その追加するパケット（Ｐａ）が上記閾値（Ｔｈａ）に対応づけられた優先度以上に優先されるパケットであって、上記のキューの上記閾値より後方に、上記閾値（Ｔｈａ）に対応づけられた優先度以上に優先されるパケット（Ｐｂ）が格納されたパケットの中にある場合には、そのパケット（Ｐｂ）の次の後方にその追加するパケット（Ｐａ）を格納するが、その格納する位置に、上記閾値（Ｔｈａ）に対応付けられた優先度以下で優先されないパケット（Ｐｃ）があれば、そのパケット（Ｐｃ）を棄却して追加するパケット（Ｐａ）を格納し、
２Ｃ）その追加するパケット（Ｐａ）が、上記閾値（Ｔｈａ）に対応づけられた優先度以上に優先されるパケットであって、上記のキューの上記閾値より後方に上記閾値（Ｔｈａ）に対応づけられた優先度以上に優先されるパケットが、格納されたパケットの中にない場合には、上記閾値（Ｔｈａ）で分断されるパケットの後方にその追加するパケットを格納するが、その格納する位置に、上記閾値（Ｔｈａ）に対応付けられた優先度以下で優先されないパケット（Ｐｃ）があれば、そのパケットを棄却して格納し、
２Ｄ）その追加するパケット（Ｐａ）が、上記閾値（Ｔｈａ）に対応づけられた優先度以下で優先されないパケットであれば、上記のキューに格納されたパケットの並びの最後方にその追加するパケット（Ｐａ）を格納する。
【００３８】
このバッファ管理法を用いたバッファ管理装置を図６に示し、そのパケットに対する振舞いを、図７、８、９のフローチャートに従って次に説明する。図７、８、９は、横に連続する図であり、優先度が２クラスの場合を示している。さらに優先度クラスを増加させる場合は、図７に相当する処理を付け加えれば良い。また、図７のＭ２で示した部分を下記のアルゴリズムにしたがって変更する。
【００３９】
図６（ａ）は、それに用いるＮ入力×１出力の光バッファ（Ｎ＝４）を示している。バッファリング装置は、Ｂ個のファイバ遅延線４、Ｎ×（Ｂ＋１）個の光スイッチ１、Ｂ×２個の光スイッチ２、バッファ管理装置３、より構成される。到着するパケットＡ、Ｂ、Ｃ、Ｄの優先度を、それぞれ、２、２、１、２とし、バッファ管理装置の閾値をＴｈ＝Ｄとしたときのバッファ管理装置の振舞いを例として示す。図６（ｂ）は、パケットＡ（優先度＝２）が遅延線ｄ０に切替えられた直後の出力ポートから見たパケットの位置を示している。この場合は、パケットＡ（優先度＝２）を光バッファに格納した後で、バッファ占有度は閾値Ｔｈを超えていることがわかる。したがって、パケットＢ（優先度＝２）については、上記の２）の方針に従って、一旦バッファに格納されるが、この直後に処理されるクラス１のパケットＣによって上書される。ここでいう上書き機能は、まだ入っていないパケットは前段の光スイッチで棄却し、すでに遅延線を流れているパケットは後段の光スイッチで棄却することで実現する。クラス２のパケットＤは、パケットＣの後方に格納される。
【００４０】
次に、このバッファ管理法を用いたバッファ管理装置で持つ情報を以下に述べる。
【００４１】
優先度の種類と等しいｐ個の閾値（Ｔｈ１、Ｔｈ２、・・・、Ｔｈｐ）を設ける。それぞれは、遅延線の単位長Ｄの倍数である。
また、遅延線の数をＢとして、
【００４２】
【数４】
2004236236.tif 000006
とする。
【００４３】
優先度１、２、・・・、ｐのパケットについて、優先度ごとに、該当優先度のパケットがバッファへの格納を許される最小の時刻  ｆ１、ｆ２、・・・、ｆｐのそれぞれを、上記の可変長パケットであるが優先制御を行なわないバッファ管理法の場合に習って定義する。ここで、バッファ占有量ｂ＝ｆｐとする。
【００４４】
このとき以下のアルゴリズムに従って処理をするものとする。
（１）  ｎ＝１、２、・・・、Ｎに対して、ポートｎにパケットが到着していれば、以下の処理を順に行なう。
（１−１）  そのパケットは優先度ｉ、パケット長ｌｎｉ  で、周期開始からｔｎ遅れて到着したとする。光遅延線バッファの離散特性により、パケットは、
【００４５】
【数５】
2004236236.tif 000007
【００４６】
の遅延を持つ必要がある。Δｎ＜Ｂなら、そのパケットをΔｎ番目の遅延線に格納する（図７のＦ３）。また、Δｎ≧Ｂであれば、そのパケットを棄却（図７のＦ９９）する。
【００４７】
（１−２）  パケットをバッファに格納する時は、次のポートに到着するパケットを適切に処理するために、優先度ｉをもつパケットに関する変数ｆｉについて、
【００４８】
【数６】
2004236236.tif 000008
【００４９】
とする（図７のＦ４）。さらに、他の変数（または、該当優先度のパケットがバッファへの格納を許される最小の時刻）ｆ１、ｆ２、・・・、ｆｐも以下のように変更する。
【００５０】
Ａ）到着したパケットを格納する前のバッファ占有量ｂが、Ｔｈｐより小さければ、到着するパケットの優先クラスに関わらず、ｆｉの値をｆｋに設定する（ｋ＝１、２、・・・、ｐ）
【００５１】
Ｂ）  到着したパケットを格納する前のバッファ占有量ｂが、
Ｔｈｊ≦ｂ＜Ｔｈｊ−１  （１＜ｊ≦ｐ）であり、
優先度ｊ以下のパケット（ｉ≧ｊ）が到着する場合、
ｋ＝ｊ、ｊ＋１、・・・、ｐ  に対してｆｉの値をｆｋに設定する。
【００５２】
Ｃ）  到着したパケットを格納する前のバッファ占有量ｂが、
Ｔｈｊ≦ｂ＜Ｔｈｊ−１  （１＜ｊ≦ｐ）  であり、
クラスｊより優先されるパケット（ｉ＜ｊ）  が到着する場合、
ｋ＝１、２、・・・、ｊ−１  に対して、
ｆｉの値をｆｋに設定する。優先度ｍがｊまたはそれより低いパケット（ｍ≧ｊ）を格納する位置を、クラスがｊより高いパケットより前方に格納しないように、ｍ＝ｊ、ｊ＋１、・・・、ｐに対して、
ｆｍにｍａｘ（ｆｊ−１、ｆｍ）の値を設定する。
【００５３】
（２）また、全てのポートのパケットが処理された後、次の周期の処理を適切に行なうために、ｆ１、ｆ２、・・・、ｆｐ  を変更する。
【００５４】
Ｄ）  バッファ占有量ｂ  が閾値Ｔｈｐ以下であれば、
ｋ＝１、２、・・・、ｐに対して、ｆｋにｍａｘ（ｆｋ−Ｔ、０）を設定する。
【００５５】
Ｅ）  バッファ占有量ｂ  が閾値Ｔｈｉ≦ｂ＜Ｔｈｉ−１  （１＜ｉ≦ｐ）であれば、ｍ＝ｉ、ｉ＋１、・・・、ｐに対して、ｆｍにｆｍ−Ｔを設定する。
また、ｋ＝１、２、・・・、ｉ−１に対して、
ｆｋにｍｉｎ（ｆｐ、ｍａｘ（ｆｋ−Ｔ、Ｔｈｉ））の値を設定する。
【００５６】
上記の処理を高速で行う装置は、図１０、１１、１２に示したフローチャートをもとにゲートアレイを構成することにより容易に実現することができる。図１０、１１、１２、１３は一連の図面であり、符号は、図７、８、９において対応するブロックを示している。
【００５７】
このバッファリング方法を用いると、パケットの処理順序は、バッファへの到着順序とは異なる。しかし、優先度に注目すると、それぞれのポートにおけるパケットの到着順序は、棄却されたパケットを除外すると、その出発順序と同じである。このように、出発と到着の順序が保たれていることは、他のアプリケーションにも好都合であることはあきらかである。
【００５８】
このバッファリング方法についてのシミュレーション結果を図１３に示す。これは、１０９個のパケットを用いてシミュレーションした結果である。ここで、パケットは、率ａのポアソン過程に従って到着するものとし、優先度１と優先度２とのパケット数の比率は、ρ１：ρ２とした。パケットの長さは、平均１で、指数関数的に分布するものとした。遅延線の数を５０とし、その遅延単位時間をＤ＝１．０とした。Ｄは平均パケット長で正規化している。ここで、閾値の値を従来の方法（ｖＰＢＳ）に比べ本発明の方法（ｖＰＢＳＯ）を僅かに小さくすることによってパケットの棄却率の改善が図れることが明らかになっている。これは、これらの方法の本質的な違いに依るものである。図１３から分かるように、本発明の方法（ｖＰＢＳＯ）では、従来の方法（ｖＰＢＳ）に比べて、パケットの棄却率が小さくなっている。
【００５９】
【発明の効果】
非同期到着する可変長パケットについて優先制御を行なうようにしたので、優先するパケットの棄却率を優先されないパケットの棄却率よりも低減することができた。また、優先度の低いパケットを上書きする本発明（ｖＰＢＳＯ）により、従来のＰＢＳ方式を可変長パケットに拡張するｖＰＢＳ方式よりも、パケット棄却率を低減することができた。
【図面の簡単な説明】
【図１】一般的に用いられるバッファの状態を表すキューを示す図である。
【図２】従来の光パケットスイッチアーキテクチャの例を示す図である。
【図３】部分バッファ共有方式（ＰＢＳ）に用いられるキューを示す図である。
【図４】４入力×１出力の光バッファ構成を示す図である。
【図５】従来の光バッファ構成を示す図である。
【図６】本発明の光バッファ構成を示す図である。
【図７】本発明のバッファリング方法を実行するためのフローチャートを示す図である。
【図８】本発明のバッファリング方法を実行するためのフローチャートを示す図である。
【図９】本発明のバッファリング方法を実行するためのフローチャートを示す図である。
【図１０】本発明のバッファリング装置に用いるゲートアレイを構成する際に用いるフローチャートを示す図である。
【図１１】本発明のバッファリング装置に用いるゲートアレイを構成する際に用いるフローチャートを示す図である。
【図１２】本発明のバッファリング装置に用いるゲートアレイを構成する際に用いるフローチャートを示す図である。
【図１３】本発明のバッファリング方法についてのシミュレーション結果を示す図である。
【符号の説明】
１、２  光スイッチ
３  バッファ管理装置
４  光遅延素子
５  優先度と長さの読取り手段
【図１】
2004236236.tif 000009
【図２】
2004236236.tif 000010
【図３】
2004236236.tif 000011
【図４】
2004236236.tif 000012
【図５】
2004236236.tif 000013
【図６】
2004236236.tif 000014
【図７】
2004236236.tif 000015
【図８】
2004236236.tif 000016
【図９】
2004236236.tif 000017
【図１０】
2004236236.tif 000018
【図１１】
2004236236.tif 000019
【図１２】
2004236236.tif 000020
【図１３】
2004236236.tif 000021