(57)【要約】【課題】  単位時間当たりに処理するパケット数を多くすることができる光パケットのバッファリング装置とそのバッファリング方法を提供する。【解決手段】  複数の光路で伝送された非同期到着する可変長パケットを入力し、少数の光路に出力する装置で、出力用の光路において光パケット信号が重ならないようにするために、遅延素子の遅延値と読み取られた光パケット長と光パケット前置期間とを用いて、演算によって一時的に保管する遅延素子を決める制御装置において、図１３のように複数の演算器を多段に配置して、遅延時間の決定に必要な処理を、プリフィクスサムオペレーションを並列パイプライン化した演算結果とバッファリング装置のキュー長と光パケット長と光パケット前置期間とを用いて並列処理で行う構成とする。【選択図】  図１３
2005033661.tif 000002
【特許請求の範囲】
【請求項１】
複数の光路で伝送された非同期到着する可変長光パケットを入力し、１つの光路に出力する装置であって、
それぞれの光路の可変長光パケットの光パケット長を読みとる読取手段と、予め用意したクロック信号とそれに引き続く最近の前記可変長光パケットの到着時間との時間差（光パケット前置期間）とを読みとる読取手段と、上記の光パケットを一時的に保管し、Ｂ通りの異なった遅延時間のいずれかを上記の光パケットに与える複数の遅延素子からなるキューと、上記の光パケットを上記の複数の遅延素子に振り分ける光スイッチと、上記の遅延された光パケットを合波する合波器と、合波器に接続された出力用の光路とを含み、
出力用の光路において、入力された光パケットが重ならないようにするために、遅延素子の遅延値と読み取られた光パケット長と光パケット前置期間とを用いて、演算によって一時的に保管する遅延素子を決める制御装置を含み、
その制御装置においては、上記の複数の光路には１からＮの順序数ｎが与えられているものとし、以下においては、対応するものが無いときにはその値をゼロとするものとするとき、
それぞれの光路の光パケット長と光パケット前置期間について、
第１段の演算器とレジスタの並びとして、第（ｎ−１）光路上にある光パケットの光パケット長と光パケット前置期間と、第ｎ光路上の光パケットの光パケット長と光パケット前置期間との演算を行う演算器Ｐ（１，ｎ）と、その演算結果を保持するレジスタＲ（１，ｎ）と、が配置され、
第ｍ（２≦ｍ≦ｌｏｇ２  Ｎ）段の並びとして、レジスタＲ（ｍ−１，ｎ−２m-1）あるいはその複写とレジスタＲ（ｍ−１，ｎ）あるいはその複写との演算を行う演算器Ｐ（ｍ，ｎ）と、その演算結果を保持するレジスタＲ（ｍ，ｎ）と、が設けられ、
２M＝Ｎとなる第（Ｍ＋１）段には、演算器とキュー長の最後尾の情報を保持するレジスタＱが設けられ、
さらに、第１の可変長光パケットに与える遅延を、第１光路の光パケット長と光パケット前置期間あるいはその複写とレジスタＱの値との演算から決定する演算器Ｐ（Ｍ+１，１）と、
１より大きいｎについて、第ｎの可変長光パケットに与える遅延を、第ｎの光路の光パケット長と光パケット前置期間あるいはその複写とレジスタＲ（Ｍ，ｎ−１）とレジスタＱの値との演算から決定する演算器Ｐ（Ｍ＋１，ｎ）と、が、設けられ、
演算器Ｐ（Ｍ＋１，１）あるいは、演算器Ｐ（Ｍ＋１，ｎ）の出力によりそれぞれの光路の可変長光パケットに与える遅延時間を調整することを特徴とする非同期到着する光パケットのバッファリング装置。
【請求項２】
上記の光路の数をＮ、その番号をｎとし、
上記の読取手段は、周期Ｔで読み取りを行い、この読み取り手段を指定された時刻に通過する第ｎ番の光路の光パケットについて、光パケットの長さをｌn（エルエヌ）とし、光パケット前置期間をｔnとし、また、ｎ＝０については、ｌn＝ｔn＝０とし、
上記の複数の遅延素子による遅延は、遅延値Ｄで増加する遅延として並べることができる構成とするとき、
上記の演算器は、入力側のそれぞれの光路の数Ｎについてそれぞれ備えられており、その１からＮのうちの整数ｎについて、
１）ｌn-1＝０であるとき、ｔnをｔn,1として出力し、あるいは、
ｌn-1＝０でないとき、ｔn-1を出力ｔn,1とし、
２）また、ｇn-1＝ｌn-1＋ｔn-1、とし、
３）ｌn＝０であるとき、ｇn-1 を出力ｆn,1 とし、あるいは、
ｌn＝０でないとき、Δnを（ｇn-1−ｔn）／Ｄを下回らない最小の整数として、（ｔn＋ｌn＋ΔnＤ）を出力ｆn,1とすることを特徴とし、請求項１に記載の光パケットのバッファリング装置に用いる光パケットのバッファリング方法。
【請求項３】
請求項２に記載された複数の演算器を１段目の演算器と呼ぶものとして、
１段目のそれぞれの演算器Ｐ（１，ｎ）には、それぞれの出力（ｆn,1、ｔn,1）を一時的に保存するレジスタＲ（１，ｎ）が設けられており、
３からＮのｎについて、ｎ番目のレジスタ内容と（ｎ−２）番目のレジスタ内容とを演算し、出力（ｆn,2、ｔn,2）を与える２段目のｎ−２番目の演算器Ｐ（２，ｎ）が備えられている装置のバッファリング方法であって、
１）ｆn-2,1＝０であるとき、ｔn,1をｔn,2として出力し、あるいは、
ｆn-2, 1＝０でないとき、ｔn-2,1をｔn,2として出力し、
２）また、ｆn,1＝０であるとき、ｆn-2,1をｆn,2として出力し、あるいは、ｆn,1＝０でないときで、
２−１）Δnを（ｆn-2,1−ｔn,1）／Ｄを下回らない最小の整数として、（ｆn,1＋ΔnＤ）を出力ｆn,2とする、
ことを特徴とする請求項２に記載の光パケットのバッファリング方法。
【請求項４】
請求項２に記載された複数の演算器を１段目の演算器と呼ぶものとして、
１段目のそれぞれの演算器Ｐ（１，ｎ）には、それぞれの出力（ｆn,1、ｔn,1）を一時的に保存するレジスタＲ（１，ｎ）が設けられており、２からｌｏｇ2Ｎまでの整数ｍについて、（ｍ−１）段目の演算器が定義されているとき、
ｍ段目の演算器について、β＝２m-1として、β＋１からＮのｎについて、前段の演算器Ｐ（ｍ−１，ｎ）に接続された上記のｎ番目のレジスタ内容Ｒ（ｍ−１，ｎ）と（ｎ−β）番目のレジスタ内容Ｒ（ｍ−１，ｎ−?）とを演算し、出力（ｆn,m、ｔn,m）を与えるｍ段目の（ｎ−β）番目の演算器Ｐ（ｍ，ｎ）が備えられている装置のバッファリング方法であって、
１）ｆn-β,m-1＝０であるとき、ｔn,m-1をｔn,mとして出力し、あるいは、
ｆn-β,m-1＝０でないとき、ｔn-β,m-1を出力ｔn,mとし、
２）また、ｆn,m-1＝０であるとき、ｆn-β,m-1をｆn,mとして出力し、あるいは、
ｆn,m-1＝０でないとき、
２−１）Δnを（ｆn-β,m-1−ｔn,m-1）／Ｄを下回らない最小の整数として、（ｆn,m-1＋ΔnＤ）を出力ｆn,mとする、
ことを特徴とする請求項２に記載の光パケットのバッファリング方法。
【請求項５】
上記のキューの長さをｑとするとき、Ｍ＝ｌｏｇ2Ｎ、とするとき、１からＮのうちの整数ｎについて、
１）ｌn≠０でない場合には、終了し、
ｌn≠０である場合で、レジスタＲ（Ｍ，ｎ−１）にあるｆn-1，Mについて、
２）ｆn-1,M＝０のときには、臨時の値（ｔｅｍｐ）を設けて、（ｔｅｍｐ）＝ｑとし、
ｆn-1,M＝０でないときには、（ｑ−ｔn-1,M）／Ｄを下回らない最小の整数とｆn-1,Mとの和を（ｔｅｍｐ）とし、
３）（（ｔｅｍｐ）−ｔn）／Ｄを下回らない最小の整数をΔnとして、
ΔnがＢよりも小さいときは、Δnを遅延素子を指定する情報として出力し、
小さくないときは、それに対応する光パケットを棄却する、
ことを特徴とする請求項４に記載の光パケットのバッファリング方法。
【請求項６】
１）レジスタＲ（Ｎ，Ｍ）に保持されたｆN,Mについて、
ｆN,M＝０が成立する場合は、（ｑ−Ｔ）と０との大きいほうを新規のキュー長（ｑnew）としてその値をレジスタＱに保持し、
ｆN,M＝０が成立しない場合は、Δを（ｑ−ｔN,M）／Ｄを下回らない最小の整数とするとき、
２）このΔが上記のＢより小さいときには、ｆN,M＋ΔＤ−Ｔ  と、０との大きいほうの値を新規のキュー長としレジスタＱに保持し、
このΔがＢより小さくないときには、（ｑ−Ｔ）を新規のキュー長とし、レジスタＱに保持する、
ことを特徴とする請求項５に記載の光パケットのバッファリング方法。
【請求項７】
ＭＴＵ（最大転送サイズ）が設定されている場合で、
１）レジスタＲ（Ｍ，Ｎ）に保持されたｆN,MについてｆN,M＝０が成立する場合は、（ｑ−Ｔ）と０との大きいほうを新規のキュー長（ｑnew）としてその値をレジスタＱに保持し、
ｆN,M＝０が成立しない場合は、Δを（ｑ−ｔN,M）／Ｄを下回らない最小の整数とするとき、
２）このΔがＢより小さいときには、（ｆN,M＋ΔＤ）と、（ＢＤ＋ＭＴＵ）との小さいほうからＴを引いた値と、０との大きいほうの値を新規のキュー長としてその値をレジスタＱに保持し、
このΔがＢより小さくないときには、（ｑ−Ｔ）を新規のキュー長とし、レジスタＱに保持する、
ことを特徴とする請求項５に記載の光パケットのバッファリング方法。
【請求項８】
上記の光路の数をＮ、その番号をｎとし、周期Ｔを適当に決めた単位時間（τ）の２の累乗倍、すなわち、Ｔ＝２aτ（ａは非負の整数）に設定し、ただし、Ｔは単位時間（τ）の整数倍の長さで表される最小パケット長を上回らないものとし、上記の読取手段は、周期Ｔで読み取りを行い、この読み取り手段を指定された時刻に通過する第ｎ番の光路の光パケットについて、光パケットの長さを単位時間の整数倍の長さで表されるｌn（エルエヌ）とし、光パケット前置期間を単位時間の整数倍の長さで表されるｔnとし、前記の光パケットの長さは、その長さを下回らない単位時間の整数倍で表すものとし、前記の前置期間は、その前置期間を上回らない単位時間の整数倍で表すものとし、また、ｎ＝０については、ｌn＝ｔn＝０とし、
上記の複数の遅延素子による遅延は、遅延値Ｄで増加する遅延として並べることができる構成とし、Ｄを２k（ｋは非負の整数）で与えるとき、また、表記法として、整数ｘの２進数の下位ｋビットに相当する整数をｘ(2)とし、前記の下位ｋビットを除いた残りの上位ビットで構成される２進数をｘ(1)とするとき、
上記の演算器は、入力側のそれぞれの光路の数Ｎについてそれぞれ備えられており、その１からＮまでの整数ｎについて、
１）ｌn-1＝０であるとき、ｔnをｔn,1として出力し、あるいは、
ｌn-1＝０でないとき、ｔn-1を出力ｔn,1として出力し、
２）また、ｇn-1＝ｌn-1＋ｔn-1、とし、
３）ｌn＝０であるとき、ｇn-1をｆn,1として出力し、
ｌn＝０でないとき、ｇn-1がｔn以下の場合には、ｇn-1(1)をΔnとし、
ｇn-1がｔn以下でない場合には、（ｇn-1(1)＋１）をΔnとし、
４）（ｔn(2)＋ｌn＋２kΔn）を出力ｆn,1とする、
ことを特徴とする請求項１に記載の非同期到着する光パケットのバッファリング方法。
【請求項９】
請求項８に記載された複数の演算器を１段目の演算器と呼ぶものとして、
１段目のそれぞれの演算器Ｐ（１，ｎ）には、それぞれの出力（ｆn,1、ｔn,1）を一時的に保存するレジスタＲ（１，ｎ）が設けられており、２からｌｏｇ2Ｎまでの整数ｍについて、（ｍ−１）段目の演算器が定義されているとき、
ｍ段目の演算器について、β＝２m-1として、β＋１からＮのｎについて、前段の演算器Ｐ（ｍ−１，ｎ）に接続された上記のｎ番目のレジスタ内容Ｒ（ｍ−１，ｎ）と（ｎ−β）番目のレジスタ内容Ｒ（ｍ−１，ｎ−?）とを演算し、出力（ｆn,m、ｔn,m）を与えるｍ段目の（ｎ−β）番目の演算器Ｐ（ｍ，ｎ）が備えられている装置のバッファリング方法であって、
１）ｆn-β,m-1＝０であるとき、ｔn,m-1をｔn,mとして出力し、あるいは、
ｆn-β,m-1＝０でないとき、ｔn-β,m-1を出力ｔn,mとし、
２）また、ｆn,m-1＝０であるとき、ｆn-β,m-1をｆn,mとして出力し、あるいは、
ｆn,m-1＝０でないときで、
２−１）  ｆn-β,m-1(2)がｔn,m-1(2)以下の時には、ｆn-β,m-1(1)をΔnとし、
２−２）    ｆn-β,m-1がｔn,m-1以下でない時には、（ｆn-β,m-1(1)＋１）をΔnとし、
３）  （ｆn,m-1＋２kΔn）をｆn,mとして出力する、
ことを特徴とする請求項８に記載の光パケットのバッファリング方法。
【請求項１０】
上記のキューの長さをｑとするとき、１からＮのうちの整数ｎについて、Ｍ＝log2 Ｎ  とするとき、
１）ｌn≠０でないときには、終了し、
２）ｌn≠０のときには、
２−１）ｆn-1,M＝０のときで、
ｑ(2)がｔn(2)以下のときには、ｑ(1)をΔnとし、
ｑ(2)がｔn(2)以下でないときには、（ｑ(1)＋１）をΔnとし、
２−２）ｆn-1,M＝０でないときで、
ｑ(2)がｔn-1,M(2)以下のときには、ｑ(1)をΔ1とし、
ｑ(2)がｔn-1,M(2)以下でないときには、（ｑ(1)＋１）をΔ1とし、さらに、
２−３−１）ｆn-1,M(2)がｔn(2)以下のときには、（Δ1＋ｆn-1,M(1)）をΔnとし、
２−３−２）ｆn-1,M(2)がｔn(2)以下でないときには、（Δ1＋１＋ｆn-1,M(1)）をΔnとし、
３）ΔnがＢよりも小さいときは、Δnを遅延素子を指定する情報として出力し、
小さくないときは、それに対応する光パケットを棄却する、
ことを特徴とする請求項８に記載の光パケットのバッファリング方法。
【請求項１１】
Ｍ＝log2Ｎとするとき、
１）ｆN,M＝０が成立する場合で
１−１）  ｑがＴより大きいときは、（ｑ−Ｔ）新規のキュー長を（ｑnew）とし、
１−２）  ｑがＴより大きくないときは、ｑnew＝０とし、
２）ｆN,M＝０でない場合で、
２−１）ｑ(2)がｔN,M(2)以下のときには、ｑ(1)をΔとし、
ｑ(2)がｔN,M(2)以下でないときには、（ｑ(1)＋１）をΔとし、
３−１）このΔがＢより小さいときで、
３−１−１）ｆN,M＋２kΔがＴより大きいときには、（ｆN,M＋２kΔ−Ｔ）をｑnewとし、
３−１−２）ｆN,M＋２kΔがＴより大きくないときには、ｑnew＝０とし、
３−２）このΔがＢより小さくないときには、（ｑ−Ｔ）をｑnewとする、
ことを特徴とする請求項９に記載の光パケットのバッファリング方法。
【請求項１２】
ＭＴＵ（最大転送サイズ）が設定されている場合で、
Ｍ＝log2Ｎとするとき、
１）ｆN,M＝０が成立する場合で
１−１）  ｑがＴより大きいときは、（ｑ−Ｔ）を新規のキュー長（ｑnew）とし、
１−２）  ｑがＴより大きくないときは、ｑnew＝０とし、
２）ｆN,M＝０でない場合で、
２−１）ｑ(2)がｔN,M(2)以下のときには、ｑ(1)をΔとし、
ｑ(2)がｔN,M(2)以下でないときには、（ｑ(1)＋１）をΔとし、
３−１）このΔがＢより小さいときで、
３−１−１）（ｆN,M＋２kΔ）が（２kＢ＋ＭＴＵ）よりも大きいときは、（２kＢ＋ＭＴＵ−Ｔ）をｑnewとし、
３−１−２）（ｆN,M＋２kΔ）が（２kＢ＋ＭＴＵ）よりも大きくないときで、
３−１−２−１）ｆN,M＋２kΔがＴより大きいときには、（ｆN,M＋２kΔ−Ｔ）をｑnewとし、
３−１−２−２）ｆN,M＋２kΔがＴより大きくないときには、ｑnew＝０とし、
３−２）このΔがＢより小さくないときには、（ｑ−Ｔ）をｑnewとする、
ことを特徴とする請求項９に記載の光パケットのバッファリング方法。
【請求項１３】
複数の光路から同期固定長光パケットを入力し、それぞれの光パケットにＢ通りの異なった遅延時間のいずれかを与えてひとつの光路に出力する装置であって、
それぞれの光路の光パケットの有無を読みとる読取手段と、
上記の複数の光パケットを一時的に保管してＢ通りの異なった遅延時間のいずれかを与える複数の遅延素子からなるキューと、上記の光パケットを上記の複数の遅延素子に振り分ける光スイッチと、上記の複数の遅延素子に光路で接続された合波器と、合波器に接続された出力用の光路とを含み、
出力用の光路において光パケットが重ならないようにするために、遅延素子の遅延値と、読み取られた光パケットの有無情報とを用いて、演算によって一時的に保管する遅延素子を決める制御装置を備え、
この制御装置は、
上記の複数の光路には１からＮの順序数ｎが与えられているものとし、以下においては、ｎについて対応するものが無いときには無視するものとするとき、
それぞれの光路の光パケット数について、
第１段の演算器とレジスタの並びとして、第（ｎ−1）光路上にある光パケットの光パケットの有無情報と、第ｎ光路上の光パケットの光パケットの有無情報と、の演算を行う演算器Ｐ（１，ｎ）と、その演算結果を保持するレジスタＲ（１，ｎ）と、が配置され、
第ｍ（２≦ｍ≦ｌｏｇ２  Ｎ）段の並びとして、レジスタＲ（ｍ−１，ｎ−２m-1）あるいはその複写とレジスタＲ（ｍ−１，ｎ）あるいはその複写との演算を行う演算器Ｐ（ｍ，ｎ）と、その演算結果を保持するレジスタＲ（ｍ，ｎ）と、が設けられ、
２M＝Ｎとなる整数Ｍについて、第Ｍ+1段には、演算器とキュー長の最後尾の情報を保持するレジスタＱが設けられ、
さらに、第１の同期固定長光パケットに与える遅延を、第１光路の光パケットの有無情報あるいはその複写とレジスタＱの値との演算から決定し、
１より大きいｎについて、第ｎの同期固定長光パケットに与える遅延を演算器Ｐ（Ｍ＋１，ｎ）を用いて、第ｎの光路の光パケットの有無情報あるいはその複写とレジスタＲ（Ｍ，ｎ−１）とレジスタＱの値との演算から決定することにより、それぞれの光路の同期固定長光パケットに与える遅延時間を調整することを特徴とする光パケットのバッファリング装置。
【請求項１４】
それぞれの光路の光パケットの有無を周期Ｔごとに読みとる読取手段を備え、第１段のそれぞれの演算器は、ポート（ｎ−１）とポートｎへ到着する光パケットの有無にしたがってｌn-1、ｌnに、到着時に１、非到着時に０を入力し、
ｌ0:=０とし、
１からＮまでの整数ｎについて、
ｆn,1:=ｌn-1＋ｌn
とする演算を行ない、２つのポートに到着した光パケット数ｆn,1を出力する演算器であることを特徴とする請求項１３に記載の光パケットのバッファリング装置。
【請求項１５】
請求項１４に記載された複数の演算器を１段目の演算器と呼ぶものとして、１段目のそれぞれの演算器Ｐ（１，ｎ）には、それぞれの出力（ｆn,1）を一時的に保存するレジスタＲ（１，ｎ）が設けられており、２からｌｏｇ2Ｎまでの整数ｍについて、（ｍ−１）段目の演算器が定義されているとき、ｍ段目の演算器について、
β＝２m-1として、β＋１からＮまでのｎについて、前段の演算器Ｐ（ｍ−１，ｎ）に接続されたｎ番目のレジスタＲ（ｍ−１，ｎ）の値と前段の演算器Ｐ（ｍ−１，ｎ−β）に接続された（ｎ−β）番目のレジスタＲ（ｍ−１，ｎ−β）の値とについて、
ｆn,m：＝ｆn,m-1＋ｆn-β,m-1
とする演算を演算器Ｐ（ｍ，ｎ）で行ない、ｆn,mを出力として与えることを特徴とする請求項１４に記載の光パケットのバッファリング装置。
【請求項１６】
第（Ｍ＋１）段目における演算器Ｐ（Ｍ＋１，ｎ）（ただし、１≦ｎ≦Ｎ）は、
ポート１からｎ−１までに到着した光パケット数ｆn-1,M、と、
ポートｎに到着する光パケットの有無ｌn、と、
キュー長ｑとを用いて、１からＮまでの整数ｎについて
ｌn＝０の場合は、終了し
そうでない場合は、Δn：＝ｑ＋ｆn-1,Mとするが、
もし、Δn＜Ｂの場合は、光パケットに、Δnの遅延を与え、
Δn＜Ｂでない場合は、その光パケットを棄却する、
という処理を順に行って遅延Δnの値を、遅延素子を指定する情報として出力することを特徴とする請求項１５に記載の光パケットのバッファリング装置。
【請求項１７】
レジスタＲ（Ｍ，Ｎ）に保持されたｆN,Mについて、（ｍｉｎ（ｑ＋ｆN,M ，Ｂ）−１）と０との大きいほうの値を新規のキュー長（ｑnew）としてその値をレジスタＱに保持する、
ことを特徴とする請求項１６に記載の光パケットのバッファリング装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、バッファ容量やその保持時間に限りがある光回路を用いて、複数の光パケットを１つの光路に重ならないように導くための光パケットのバッファリング装置とそのバッファリング方法に関している。
【背景技術】
【０００２】
多量の情報を効率的に伝送できる光通信技術の進展に伴ない、さらに高いスループットを実現するために、伝送路だけでなく光パケット交換にも光技術が導入されつつある。一般に、光パケット交換では、光パケット転送処理が行われ、これには、光パケットスイッチが用いられる。このための光パケットスイッチの機能は、（１）宛先検索、（２）交換、（３）バッファ管理、（４）バッファリング、（５）経路制御、の５つに大きく分類できる。一般には、上記の（２）あるいは（４）の機能を光化した光パケットスイッチが光パケットスイッチと呼ばれる。これは、光スイッチと光バッファで構成されて、データを光信号のまま転送することにより、広帯域特性をもつ。
【０００３】
また、上記の（３）バッファ管理を改善することにより、光パケットスイッチの転送能力をさらに改善することができる。従来、この（３）バッファ管理には、電子回路による論理回路を用いてきた。これは、実用レベルにある光論理回路がないためである。
【０００４】
バッファ管理の目的のひとつは、光パケットの衝突を防止することである。光パケット交換ネットワークでは、同時に光パケットが光パケットスイッチに到着した場合には、バッファに光パケットを格納して衝突を回避する。図１は、一般的に用いられるバッファの状態を表すキューを示す図である。例えば、現在のインターネットでは、図１のように、優先制御を行なわない光パケット転送が行なわれている。光パケットスイッチに到着した光パケットは、優先度に関係なく、バッファに空きがあればそれに格納される。
【０００５】
また、上記のバッファには、半導体メモリが使われることが多い。しかし、半導体メモリを用いない光パケットスイッチでありながら、バッファをもった光バッファ制御実装方式が、非特許文献１、あるいは、非特許文献２に報告されている。
【０００６】
既に知られている光バッファには、長さの異なる複数の光ファイバが用いられている。これは、遅延時間の異なる光遅延素子であり、その遅延時間の間、光パケットが蓄えられる。この光遅延線に割当てる光パケットを制御することで、光パケット同士の衝突を回避できることは知られている。この際、任意時刻での光パケット取り出しができないため、出力時の光パケットの衝突を防ぐ必要があり、このため、光バッファに入力するに当たり、何らかのバッファ管理手法を用いて遅延時間を管理する必要があった。
【０００７】
また、図２に、従来の光パケットスイッチアーキテクチャの例として、Ｎ入力×Ｎ出力光パケットスイッチのＮ個の１入力×Ｎ出力バッファレス光パケットスイッチとＮ個のＮ入力×１出力バッファからなる構成を示す。それぞれの１入力×Ｎ出力スイッチとＮ入力×１出力バッファは実質的に格子状に接続される。上記の１入力×Ｎ出力光パケットスイッチの性能を十分に発揮するＮ入力×Ｎ出力光パケットスイッチを構成するためには、同時に到着する複数の光パケットも充分に短い時間で処理することが必要であり、それゆえ、計算量の少ないバッファ管理方式の適用が重要である。
【０００８】
上記の光パケットスイッチは、光スイッチを用いて構成される。この用途に使用できる光スイッチとしては、図３（ａ）の模式図に示すような機械式の光スイッチや、図３（ｂ）のブロック図に示すような光半導体を用いた光スイッチ、あるいは、図には示していないが、マッハツェンダー型の光スイッチなどを用いることができることが知られている。
【０００９】
上記の、１入力×Ｎ出力バッファレス光パケットスイッチでは、非特許文献４に記載されているように、光宛先検索機能により高速宛先検索が可能である。その結果、Ｎ入力×Ｎ出力光パケットスイッチは高ノードスループットを示す。しかし、光パケットの衝突を避け、棄却率を改善するためにはバッファが必要であり、Ｎ入力×Ｎ出力光パケットスイッチの各出力ポートにＮ入力×１出力バッファが接続されている。
【００１０】
次に、可変長光パケットを処理するバッファ管理法についてより具体的に説明する。この方法については、既によく知られている。たとえば、非特許文献３では、ラウンドロビンスケジューリングを加えた以下の方法によって管理している。
【００１１】
図２に示した出力バッファ型のＮ入力×Ｎ出力の光パケットスイッチでは、Ｎ入力×１出力の光バッファとＮ個の１入力×Ｎ出力のスイッチを用いる。伝送量が増加した場合、Ｎ入力×１出力の光バッファに同時に最大Ｎ光パケットが到着する可能性がある。
【００１２】
これらの光パケットの衝突（重ね合わせ）を防止するために、遅延線バッファを用いる。この場合、すべての光パケットをバッファに格納するには、Ｎ個の光パケットの遅延を求める処理を最小光パケット長に相当する時間ｌmin以内に行わねばならない。すなわち、１光パケットの処理の許容時間は、ｌmin／Ｎである。この時間を、単純なラウンドロビンに従ってバッファリングをする場合の１光パケットの処理時間と同等であるようにすると、ラウンドロビンスケジューリングによって、バッファ管理を行なうことができることを示している。
【００１３】
図４（ａ）に４入力×１出力の光バッファ構成を示す。この場合はＮ＝４である。光遅延素子で構成された光バッファは、ファイバ遅延線を用いたＢ（＝４）個の光遅延素子、Ｎ×（Ｂ+１）個の光スイッチ、バッファ管理装置（バッファマネージャ）より構成される。Ｂ個のファイバ遅延線{ｄ0、ｄ1、ｄ2、ｄ3}は、それぞれ、遅延線の単位長Ｄの倍数{０、Ｄ、２Ｄ、３Ｄ}の長さを持つ。また、バッファ管理装置からの信号により、ラウンドロビンスケジューリングは、Ｔ時間ごとに繰り返すものである。このため、バッファ管理装置は、前段の光スイッチからＴ時間以上前の離れた時点で光パケットの情報を受け取り、この前もって設けた時間Ｔの間に、この情報を使って、Ｎ個の光パケットのそれぞれに必要な遅延時間を求める。時間Ｔの間に、連続して到着する光パケットを処理する必要があることから、Ｔ≦ｌminを満たさねばならない。たとえば、図４（ａ）に示すように、４個の光パケットが到着し、バッファ管理装置により、光パケットＡ、Ｂ、Ｃはそれぞれ、遅延線ｄ0、ｄ2、ｄ3に格納され、光パケットＤは棄却されるものとする。このような制御は、バッファ管理装置が前段の光スイッチを駆動することで実現する。図４（ｂ）に、光パケットＡが遅延線ｄ0に切替えられた直後の出力ポートから見た光パケットの位置を示す。図４（ｃ）に示すように光パケットＡ、Ｂ、Ｃは衝突することなく出力される。この例では、光パケットＢが光パケットＡよりも先にバッファに到着するが、到着する光パケットはラウンドロビンで順次処理されるため、図４（ｃ）に示した順序で出力される。
【００１４】
以下に、バッファ管理装置の振舞いを図５のフローチャートにしたがって具体的に述べる。その主要部のプログラムを表１に示す。
【００１５】
【表１】
2005033661.tif 000003
【００１６】
バッファ管理装置は、内部あるいは出力時の光パケット衝突を避ける処理をする。ここで、ラウンドロビンの繰り返し時間Ｔの間のあらかじめ決められた時点ｔ0から、光バッファ中のすべての光パケットがバッファを出る時点までの時間ｔfをｆとする。以降で、ｆをバッファ占有量と呼ぶ。バッファ管理装置は、周期Ｔごとに、すべてのポートに到着した光パケットの遅延時間を求める。同一周期内に到着した光パケットに与える遅延時間を、ポートｋ＝１、２、・・・、Ｎの順に求める。ポートｋに光パケット長ｌkの光パケットが時点ｔ0を原点として時間ｔkで到着したとする。衝突回避のために光パケットに与えられるべき遅延時間ｔは、ｔ＝ｆ−ｔkである。ここで、遅延線バッファは、離散時間特性を持つことを考えると、光パケットは、次の時間遅延されるべきであることがわかる。（図５のＦ１）
【００１７】
【数１】
2005033661.tif 000004
【００１８】
ここで、関数Ceil（ｘ）は、ｘを下回らない最小の整数をあらわす。Δk＜Ｂであれば、その光パケットをΔk番目の遅延線に格納する（Ｆ２）。また、Δk≧Ｂであれば、その光パケットを棄却する。このように一部は棄却し、他は格納する光パケットであるので、それに応じてバッファ占有量ｆを更新する必要が生じる。そこで、光パケットを格納する時には（Ｆ４）、
【００１９】
【数２】
2005033661.tif 000005
【００２０】
とｆを更新する。棄却されるポートを除いて、全ポートの光パケットの遅延を求めた後、さらにｍａｘ（(ｆ−Ｔ)，０）を新たなバッファ占有量ｆとして更新し（Ｆ１１）、Ｔ時間後の次のラウンドロビン周期の光パケット処理に備える。
【００２１】
この様に光遅延線バッファを用いると、ポートｋに到着した光パケットは、その直前に格納された光パケット、すなわち、ポートｋに到着した光パケットの遅延をもとめる際に用いられるｆで示された時間に出力される光パケットとは、次の間隔をもつ。
【００２２】
【数３】
2005033661.tif 000006
【００２３】
非特許文献６に木状に遅延線バッファユニットを配置し，それぞれにバッファ管理装置を置く方法が記載されている。これは、上記のラウンドロビン処理と比べてＮをポート数として、処理速度がＮ1/2倍速くなるが、遅延線群を各バッファユニットに置かねばならず、光素子が増大するのが問題である。また、非特許文献５には、光バッファではない、半導体メモリバッファにパケットを格納するための処理を並列処理で行なう方法が記載されている。これは、ラウンドロビン処理と比べて管理装置規模をＮ倍にすることで、処理速度はｌｏｇ2Ｎ倍速くなる。
【非特許文献１】葉原 敬士、三条 広明、西沢 秀樹、小川 育夫、須崎 泰正、“波長ルーチング型大容量光パケットスイッチの開発”、 電子情報通信学会技術研究報告(SSE99-148), 2000年2月.
【非特許文献２】David K. Hunter and Meow C. Chia and Ivan Andonovic, “Buffering in OpticalPacket Switches”, IEEE/OSA Journal of Lightwave Technology, Vol. 16, No. 12,pp. 2081-2094, December 1998.
【非特許文献３】F. Callegati, “Optical buffers for variable length packets, ” IEEECommunications Letters, vol. 4, pp. 292-294, September 2000.
【非特許文献４】N. Wada, H. Harai, W. Chujo, and F. Kubota, “Photonic packet routing based onultiwavelength label switching using fiber Bragg gratings, ” ECOC 2000Technical Digest (26th European Conference on Optical Communication), vol. 4(No. 10.4.6), pp. 71-72, September 2000.
【非特許文献５】A. Prakash, S. Sharif, and A. Aziz, “An O_log_ N_ parallel algorithm foroutput queueing, ” Proceedings of IEEE INFOCOM 2002.
【非特許文献６】H. Harai, N. Wada, F. Kubota, and W. Chujo, “Contention resolution usingmulti-stage fiber delay line buffer in a photonic packet switch, ” Proceedingsof IEEE ICC 2002.
【発明の開示】
【発明が解決しようとする課題】
【００２４】
上記に示したラウンドロビン方式は、バッファリングに関するデータ処理をあらかじめ定められたポート順に順次進めるものであり、高速なバッファリングを行うには、データ処理を高速で行う必要があり、バッファリングの速度が制限されていた。また、非特許文献５の記載のように並列に光路数と同じ数の演算器を配置した場合、あるいは、非特許文献６の記載のように木状に遅延線バッファユニットを配置した場合は、それぞれにバッファ管理装置を置き、並行処理を進める方法でも、入力する光路数の増加とともに、演算器当たりの最大処理時間は急速に増大してしまう。
【発明の効果】
【００２５】
この発明は、データ処理を並行に行ってバッファリングの速度を改善し、入力数が増加しても演算器当たりの最大処理時間の急速な増大をさけることのできる光パケットのバッファリング装置とそのバッファリング方法を提供することができる。
【課題を解決するための手段】
【００２６】
上記目的を達成するための第１の発明は、多数の演算器を用いて演算のスループットを改善した非同期到着する可変長の光パケットのバッファリング装置に関しており、その特徴は、複数の光路で伝送された非同期到着する可変長光パケットを入力し、１つの光路に出力する装置であって、
それぞれの光路の可変長光パケットの光パケット長を読みとる読取手段と、予め用意したクロック信号とそれに引き続く最近の前記可変長光パケットの到着時間との時間差（光パケット前置期間）と、を読みとる読取手段と、上記の光パケットを一時的に保管し、Ｂ通りの異なった遅延時間のいずれかを上記の光パケットに与える複数の遅延素子からなるキューと、上記の光パケットを上記の複数の遅延素子に振り分ける光スイッチと、上記の遅延された光パケットを合波する合波器と、合波器に接続された出力用の光路とを含み、
出力用の光路において、入力された光パケットが重ならないようにするために、遅延素子の遅延値と読み取られた光パケット長と光パケット前置期間とを用いて、演算によって一時的に保管する遅延素子を決める制御装置を含み、その制御装置においては、
上記の複数の光路には１からＮの順序数ｎが与えられているものとし、以下においては、対応するものが無いときにはその値をゼロとするものとするとき、
それぞれの光路の光パケット長と光パケット前置期間について、
第１段の演算器とレジスタの並びとして、第（ｎ−１）光路上にある光パケットの光パケット長と光パケット前置期間と、第ｎ光路上の光パケットの光パケット長と光パケット前置期間との演算を行う演算器Ｐ（１，ｎ）と、その演算結果を保持するレジスタＲ（１，ｎ）と、が配置され、
第ｍ（２≦ｍ≦ｌｏｇ２  Ｎ）段の並びとして、レジスタＲ（ｍ−１，ｎ−２m-1）あるいはその複写とレジスタＲ（ｍ−１，ｎ）あるいはその複写との演算を行う演算器Ｐ（ｍ，ｎ）と、その演算結果を保持するレジスタＲ（ｍ，ｎ）と、が設けられ、
２M＝Ｎとなる第（Ｍ＋１）段には、演算器とキュー長の最後尾の情報を保持するレジスタＱが設けられ、
さらに、第１の可変長光パケットに与える遅延を、第１光路の光パケット長と光パケット前置期間あるいはその複写とレジスタＱの値との演算から決定する演算器Ｐ（Ｍ+１，１）と、
１より大きいｎについて、第ｎの可変長光パケットに与える遅延を、第ｎの光路の光パケット長と光パケット前置期間あるいはその複写とレジスタＲ（Ｍ，ｎ−１）とレジスタＱの値との演算から決定する演算器Ｐ（Ｍ＋１，ｎ）と、が、設けられ、
演算器Ｐ（Ｍ＋１，１）あるいは、演算器Ｐ（Ｍ＋１，ｎ）の出力によりそれぞれの光路の可変長光パケットに与える遅延時間を調整することにある。
【００２７】
また、第２の発明は、第１の発明の非同期到着する光パケットのバッファリング装置に適用できるバッファリング方法に関しており、その特徴は、上記の光路の数をＮ、その番号をｎとし、
上記の読取手段は、周期Ｔで読み取りを行い、この読み取り手段を指定された時刻に通過する第ｎ番の光路の光パケットについて、光パケットの長さをｌn（エルエヌ）とし、光パケット前置期間をｔnとし、また、ｎ＝０については、ｌn＝ｔn＝０とし、
上記の複数の遅延素子による遅延は、遅延値Ｄで増加する遅延として並べることができる構成とするとき、
上記の演算器は、入力側のそれぞれの光路の数Ｎについてそれぞれ備えられており、その１からＮのうちの整数ｎについて、
１）ｌn-1＝０であるとき、ｔnをｔn,1として出力し、あるいは、
ｌn-1＝０でないとき、ｔn-1を出力ｔn,1とし、
２）また、ｇn-1＝ｌn-1＋ｔn-1、とし、
３）ｌn＝０であるとき、ｇn-1 を出力ｆn,1 とし、あるいは、
ｌn＝０でないとき、Δnを（ｇn-1−ｔn）／Ｄを下回らない最小の整数として、（ｔn＋ｌn＋ΔnＤ）を出力ｆn,1とすることを特徴とし、請求項１に記載の光パケットのバッファリング装置に用いることである。
【００２８】
また、第３の発明の特徴は、第２の発明の複数の演算器を１段目の演算器と呼ぶものとして、
１段目のそれぞれの演算器Ｐ（１，ｎ）には、それぞれの出力（ｆn,1、ｔn,1）を一時的に保存するレジスタＲ（１，ｎ）が設けられており、
３からＮのｎについて、ｎ番目のレジスタ内容と（ｎ−２）番目のレジスタ内容とを演算し、出力（ｆn,2、ｔn,2）を与える２段目のｎ−２番目の演算器Ｐ（２，ｎ）が備えられている装置のバッファリング方法であって、
１）ｆn-2,1＝０であるとき、ｔn,1をｔn,2として出力し、あるいは、
ｆn-2, 1＝０でないとき、ｔn-2,1をｔn,2として出力し、
２）また、ｆn,1＝０であるとき、ｆn-2,1をｆn,2として出力し、あるいは、ｆn,1＝０でないときで、
２−１）Δnを（ｆn-2,1−ｔn,1）／Ｄを下回らない最小の整数として、（ｆn,1＋ΔnＤ）を出力ｆn,2とする、
ことである。
【００２９】
また、第４の発明の特徴は、第２の発明の複数の演算器を１段目の演算器と呼ぶものとして、１段目のそれぞれの演算器Ｐ（１，ｎ）には、それぞれの出力（ｆn,1、ｔn,1）を一時的に保存するレジスタＲ（１，ｎ）が設けられており、２からｌｏｇ2Ｎまでの整数ｍについて、（ｍ−１）段目の演算器が定義されているとき、
ｍ段目の演算器について、β＝２m-1として、β＋１からＮのｎについて、前段の演算器Ｐ（ｍ−１，ｎ）に接続された上記のｎ番目のレジスタ内容Ｒ（ｍ−１，ｎ）と（ｎ−β）番目のレジスタ内容Ｒ（ｍ−１，ｎ−?）とを演算し、出力（ｆn,m、ｔn,m）を与えるｍ段目の（ｎ−β）番目の演算器Ｐ（ｍ，ｎ）が備えられている装置のバッファリング方法であって、
１）ｆn-β,m-1＝０であるとき、ｔn,m-1をｔn,mとして出力し、あるいは、
ｆn-β,m-1＝０でないとき、ｔn-β,m-1を出力ｔn,mとし、
２）また、ｆn,m-1＝０であるとき、ｆn-β,m-1をｆn,mとして出力し、あるいは、
ｆn,m-1＝０でないとき、
２−１）Δnを（ｆn-β,m-1−ｔn,m-1）／Ｄを下回らない最小の整数として、（ｆn,m-1＋ΔnＤ）を出力ｆn,mとする、
ことである。
【００３０】
また、第５の発明の特徴は、第４の発明の遅延時間を制御するための値Δnを決める方法に関しており、
上記のキューの長さをｑとするとき、Ｍ＝ｌｏｇ2Ｎ、とするとき、１からＮのうちの整数ｎについて、
１）ｌn≠０でない場合には、終了し、
ｌn≠０である場合で、レジスタＲ（Ｍ，ｎ−１）にあるｆn-1，Mについて、
２）ｆn-1,M＝０のときには、臨時の値（ｔｅｍｐ）を設けて、（ｔｅｍｐ）＝ｑとし、
ｆn-1,M＝０でないときには、（ｑ−ｔn-1,M）／Ｄを下回らない最小の整数とｆn-1,Mとの和を（ｔｅｍｐ）とし、
３）（（ｔｅｍｐ）−ｔn）／Ｄを下回らない最小の整数をΔnとして、
ΔnがＢよりも小さいときは、Δnを遅延素子を指定する情報として出力し、
小さくないときは、それに対応する光パケットを棄却する、
ことである。
【００３１】
また、第６の発明の特徴は、第５の発明のキューの長さを更新する事に関しており、
１）レジスタＲ（Ｍ，Ｎ）に保持されたｆN,Mについて、
ｆN,M＝０が成立する場合は、（ｑ−Ｔ）と０との大きいほうを新規のキュー長（ｑnew）としてその値をレジスタＱに保持し、
ｆN,M＝０が成立しない場合は、Δを（ｑ−ｔN,M）／Ｄを下回らない最小の整数とするとき、
２）このΔが上記のＢより小さいときには、ｆN,M＋ΔＤ−Ｔ  と、０との大きいほうの値を新規のキュー長としレジスタＱに保持し、
このΔがＢより小さくないときには、（ｑ−Ｔ）を新規のキュー長とし、レジスタＱに保持する、
ことである。
【００３２】
また、第７の発明の特徴は、第５の発明のキューの長さを更新する事に関しており、
ＭＴＵ（最大転送サイズ）が設定されている場合に、
１）レジスタＲ（Ｍ，Ｎ）に保持されたｆN,MについてｆN,M＝０が成立する場合は、（ｑ−Ｔ）と０との大きいほうを新規のキュー長（ｑnew）としてその値をレジスタＱに保持し、
ｆN,M＝０が成立しない場合は、Δを（ｑ−ｔN,M）／Ｄを下回らない最小の整数とするとき、
２）このΔがＢより小さいときには、（ｆN,M＋ΔＤ）と、（ＢＤ＋ＭＴＵ）との小さいほうからＴを引いた値と、０との大きいほうの値を新規のキュー長としてその値をレジスタＱに保持し、
このΔがＢより小さくないときには、（ｑ−Ｔ）を新規のキュー長とし、レジスタＱに保持する、
ことである。
【００３３】
また、第８の発明は、第２の発明に関連するものであるが、
上記の光路の数をＮ、その番号をｎとし、周期Ｔを適当に決めた単位時間（τ）の２の累乗倍、すなわち、Ｔ＝２aτ（ａは非負の整数）に設定し、ただし、Ｔは単位時間（τ）の整数倍の長さで表される最小パケット長を上回らないものとし、上記の読取手段は、周期Ｔで読み取りを行い、この読み取り手段を指定された時刻に通過する第ｎ番の光路の光パケットについて、光パケットの長さを単位時間の整数倍の長さで表されるｌn（エルエヌ）とし、光パケット前置期間を単位時間の整数倍の長さで表されるｔnとし、前記の光パケットの長さは、その長さを下回らない、単位時間の整数倍で表すものとし、前記の前置期間はその前置期間を上回らない、単位時間の整数倍で表すものとし、また、ｎ＝０については、ｌn＝ｔn＝０とし、
上記の複数の遅延素子による遅延は、遅延値Ｄで増加する遅延として並べることができる構成とし、Ｄを２k（ｋは非負の整数）で与えるとき、また、表記法として、整数ｘの２進数の下位ｋビットに相当する整数をｘ(2)とし、前記の下位ｋビットを除いた残りの上位ビットで構成される２進数をｘ(1)とするとき、
上記の演算器は、入力側のそれぞれの光路の数Ｎについてそれぞれ備えられており、その１からＮまでの整数ｎについて、
１）ｌn-1＝０であるとき、ｔnをｔn,1として出力し、あるいは、
ｌn-1＝０でないとき、ｔn-1を出力ｔn,1として出力し、
２）また、ｇn-1＝ｌn-1＋ｔn-1、とし、
３）ｌn＝０であるとき、ｇn-1をｆn,1として出力し、
ｌn＝０でないとき、ｇn-1がｔn以下の場合には、ｇn-1(1)をΔnとし、
ｇn-1がｔn以下でない場合には、（ｇn-1(1)＋１）をΔnとし、
４）（ｔn(2)＋ｌn＋２kΔn）を出力ｆn,1とする、
ことである。
【００３４】
また、第９の発明は、第４の発明に関連するものであるが、これらの発明も、ＴがＤの２p（ｐは整数）＝２a-k倍であるときには、除算をしないようにすることによりハードウェア化することを容易にし、データ処理をさらに高速にするものである。その特徴は、１段目のそれぞれの演算器Ｐ（１，ｎ）には、それぞれの出力（ｆn,1、ｔn,1）を一時的に保存するレジスタＲ（１，ｎ）が設けられており、２からｌｏｇ2Ｎまでの整数ｍについて、（ｍ−１）段目の演算器が定義されているとき、
ｍ段目の演算器について、β＝２m-1として、β＋１からＮのｎについて、前段の演算器Ｐ（ｍ−１，ｎ）に接続された上記のｎ番目のレジスタ内容Ｒ（ｍ−１，ｎ）と（ｎ−β）番目のレジスタ内容Ｒ（ｍ−１，ｎ−?）とを演算し、出力（ｆn,m、ｔn,m）を与えるｍ段目の（ｎ−β）番目の演算器Ｐ（ｍ，ｎ）が備えられている装置のバッファリング方法であって、
１）ｆn-β,m-1＝０であるとき、ｔn,m-1をｔn,mとして出力し、あるいは、
ｆn-β,m-1＝０でないとき、ｔn-β,m-1を出力ｔn,mとし、
２）また、ｆn,m-1＝０であるとき、ｆn-β,m-1をｆn,mとして出力し、あるいは、
ｆn,m-1＝０でないときで、
２−１）  ｆn-β,m-1(2)がｔn,m-1(2)以下の時には、ｆn-β,m-1(1)をΔnとし、
２−２）    ｆn-β,m-1がｔn,m-1以下でない時には、（ｆn-β,m-1(1)＋１）をΔnとし、
３）  （ｆn,m-1＋２kΔn）をｆn,mとして出力する、ことである。
【００３５】
また、第１０の発明は、第５の発明に関連するものであるが、この発明も、ＴがＤの２p（ｐは整数）倍であるときには、除算をしないようにすることによりハードウェア化することを容易にし、データ処理をさらに高速にするものである。その特徴は、第９の発明において、上記のキューの長さをｑとするとき、１からＮのうちの整数ｎについて、Ｍ＝log2Ｎ  とするとき、
１）ｌn≠０でないときには、終了し、
２）ｌn≠０のときには、
２−１）ｆn-1,M＝０のときで、
ｑ(2)がｔn(2)以下のときには、ｑ(1)をΔnとし、
ｑ(2)がｔn(2)以下でないときには、（ｑ(1)＋１）をΔnとし、
２−２）ｆn-1,M＝０でないときで、
ｑ(2)がｔn-1,M(2)以下のときには、ｑ(1)をΔ1とし、
ｑ(2)がｔn-1,M(2)以下でないときには、（ｑ(1)＋１）をΔ1とし、さらに、
２−３−１）ｆn-1,M(2)がｔn(2)以下のときには、（Δ1＋ｆn-1,M(1)）をΔnとし、
２−３−２）ｆn-1,M(2)がｔn(2)以下でないときには、（Δ1＋１＋ｆn-1,M(1)）をΔnとし、
３）ΔnがＢよりも小さいときは、Δnを遅延素子を指定する情報として出力し、
小さくないときは、それに対応する光パケットを棄却する、ことである。
【００３６】
また、第１１の発明は、第６の発明に関連するものであるが、この発明も、ＴがＤの２p（ｐは整数）倍であるときには、除算をしないようにすることによりハードウェア化することを容易にし、データ処理をさらに高速にするものである。その特徴は、
Ｍ＝log2Ｎとするとき、
１）ｆN,M＝０が成立する場合で
１−１）  ｑがＴより大きいときは、（ｑ−Ｔ）を新規のキュー長（ｑnew）とし、
１−２）  ｑがＴより大きくないときは、ｑnew＝０とし、
２）ｆN,M＝０でない場合で、
２−１）ｑ(2)がｔN,M(2)以下のときには、ｑ(1)をΔとし、
ｑ(2)がｔN,M(2)以下でないときには、（ｑ(1)＋１）をΔとし、
３−１）このΔがＢより小さいときで、
３−１−１）ｆN,M＋２kΔがＴより大きいときには、（ｆN,M＋２kΔ−Ｔ）をｑnewとし、
３−１−２）ｆN,M＋２kΔがＴより大きくないときには、ｑnew＝０とし、
３−２）このΔがＢより小さくないときには、（ｑ−Ｔ）をｑnewとする、ことである。
【００３７】
また、第１２の発明は、第７の発明に関連するものであるが、この発明も、ＴがＤの２p（ｐは整数）倍であるときには、除算をしないようにすることによりハードウェア化することを容易にし、データ処理をさらに高速にするものである。その特徴は、ＭＴＵ（最大転送サイズ）が設定されている場合で、
Ｍ＝log2Ｎとするとき、
１）ｆN,M＝０が成立する場合で
１−１）  ｑがＴより大きいときは、（ｑ−Ｔ）を新規のキュー長（ｑnew）とし、
１−２）  ｑがＴより大きくないときは、ｑnew＝０とし、
２）ｆN,M＝０でない場合で、
２−１）ｑ(2)がｔN,M(2)以下のときには、ｑ(1)をΔとし、
ｑ(2)がｔN,M(2)以下でないときには、（ｑ(1)＋１）をΔとし、
３−１）このΔがＢより小さいときで、
３−１−１）（ｆN,M＋２kΔ）が（２kＢ＋ＭＴＵ）よりも大きいときは、（２kＢ＋ＭＴＵ−Ｔ）をｑnewとし、
３−１−２）（ｆN,M＋２kΔ）が（２kＢ＋ＭＴＵ）よりも大きくないときで、
３−１−２−１）ｆN,M＋２kΔがＴより大きいときには、（ｆN,M＋２kΔ−Ｔ）をｑnewとし、
３−１−２−２）ｆN,M＋２kΔがＴより大きくないときには、ｑnew＝０とし、
３−２）このΔがＢより小さくないときには、（ｑ−Ｔ）をｑnewとする、ことである。
【００３８】
また、第１３の発明は、同期のとれた固定長の光パケットを入力して、それぞれの光パケットに異なった遅延時間を与えてひとつの光路に出力する装置であって、その特徴は、
複数の光路から同期固定長光パケットを入力し、それぞれの光パケットにＢ通りの異なった遅延時間のいずれかを与えてひとつの光路に出力する装置であって、
それぞれの光路の光パケットの有無を読みとる読取手段と、
上記の複数の光パケットを一時的に保管してＢ通りの異なった遅延時間のいずれかを与える複数の遅延素子からなるキューと、上記の光パケットを上記の複数の遅延素子に振り分ける光スイッチと、上記の複数の遅延素子に光路で接続された合波器と、合波器に接続された出力用の光路とを含み、
出力用の光路において光パケットが重ならないようにするために、遅延素子の遅延値と、読み取られた光パケットの有無情報とを用いて、演算によって一時的に保管する遅延素子を決める制御装置をそなえ、
この制御装置は、
上記の複数の光路には１からＮの順序数ｎが与えられているものとし、以下においては、ｎについて対応するものが無いときには無視するものとするとき、
それぞれの光路の光パケットの有無情報について、
第１段の演算器とレジスタの並びとして、第（ｎ−1）光路上にある光パケットの光パケットの有無情報と、第ｎ光路上の光パケットの光パケットの有無情報と、の演算を行う演算器Ｐ（１，ｎ）と、その演算結果を保持するレジスタＲ（１，ｎ）と、が配置され、
第ｍ（２≦ｍ≦ｌｏｇ２  Ｎ）段の並びとして、レジスタＲ（ｍ−１，ｎ−２m-1）あるいはその複写とレジスタＲ（ｍ−１，ｎ）あるいはその複写との演算を行う演算器Ｐ（ｍ，ｎ）と、その演算結果を保持するレジスタＲ（ｍ，ｎ）と、が設けられ、
２M＝Ｎとなる整数Ｍについて、第Ｍ+1段には、演算器とキュー長の最後尾の情報を保持するレジスタＱが設けられ、
さらに、第１の同期固定長光パケットに与える遅延を、第１光路の光パケットの有無情報あるいはその複写とレジスタＱの値との演算から決定し、
１より大きいｎについて、第ｎの同期固定長光パケットに与える遅延を演算器Ｐ（Ｍ＋１，ｎ）を用いて、第ｎの光路の光パケットの有無情報あるいはその複写とレジスタＲ（Ｍ，ｎ−１）とレジスタＱの値との演算から
決定することにより、それぞれの光路の同期固定長光パケットに与える遅延時間を調整することである。
【００３９】
また、第１４の発明は、同期のとれた固定長の光パケットを入力して、それぞれの光パケットに異なった遅延時間を与えてひとつの光路に出力する装置であって、その特徴は、第１３の発明において、
それぞれの光路の光パケットの有無を周期Ｔごとに読みとる読取手段を備え、第１段のそれぞれの演算器は、ポート（ｎ−１）とポートｎへ到着する光パケットの有無にしたがってｌn-1、ｌnに、到着時に１、非到着時に０を入力し、
ｌ0:=０とし、
１からＮまでの整数ｎについて、
ｆn,1:=ｌn-1＋ｌn
とする演算を行ない、２つのポートに到着した光パケット数ｆn,1を出力する演算器であることである。
【００４０】
また、第１５の発明は、同期のとれた固定長の光パケットを入力して、それぞれの光パケットに異なった遅延時間を与えてひとつの光路に出力する装置であって、その特徴は、第１４の発明において、
１段目のそれぞれの演算器Ｐ（１，ｎ）には、それぞれの出力（ｆn,1）を一時的に保存するレジスタＲ（１，ｎ）が設けられており、２からｌｏｇ2Ｎまでの整数ｍについて、（ｍ−１）段目の演算器が定義されているとき、ｍ段目の演算器について、
β＝２m-1として、β＋１からＮまでのｎについて、前段の演算器Ｐ（ｍ−１，ｎ）に接続されたｎ番目のレジスタＲ（ｍ−１，ｎ）の値と前段の演算器Ｐ（ｍ−１，ｎ−β）に接続された（ｎ−β）番目のレジスタＲ（ｍ−１，ｎ−β）の値とについて、
ｆn,m：＝ｆn,m-1＋ｆn-β,m-1
とする演算を演算器Ｐ（ｍ，ｎ）で行ない、ｆn,mを出力として与えること、である。
【００４１】
また、第１６の発明は、同期のとれた固定長の光パケットを入力して、それぞれの光パケットに異なった遅延時間を与えてひとつの光路に出力する装置であって、その特徴は、第１５の発明において、
レジスタＲ（Ｍ，Ｎ）に保持されたｆN,Mについて、ｍｉｎ（ｑ＋ｆN,M ，Ｂ−１）と０との大きいほうの値を新規のキュー長（ｑnew）としてその値をレジスタＱに保持する、ことである。
【００４２】
また、第１７の発明は、同期のとれた固定長の光パケットを入力して、それぞれの光パケットに異なった遅延時間を与えてひとつの光路に出力する装置であって、その特徴は、第１６の発明において、
第（Ｍ＋１）段目における演算器Ｐ（Ｍ＋１，ｎ）（ただし、１≦ｎ≦Ｎ）は、
ポート１からｎ−１までに到着した光パケット数ｆn-1,M、と、
ポートｎに到着する光パケットの有無ｌn、と、
キュー長ｑとを用いて、１からＮまでの整数ｎについて
ｌn＝０の場合は、終了し
そうでない場合は、Δn：＝ｑ＋ｆn-1,Mとするが、
もし、Δn＜Ｂの場合は、光パケットに、Δnの遅延を与え、
Δn＜Ｂでない場合は、その光パケットを棄却する、
という処理を順に行って遅延Δnの値を、遅延素子を指定する情報として出力することである。
【発明を実施するための最良の形態】
【００４３】
以下にこの発明の実施の形態を図面に基づいて詳細に説明する。以下の例においては、同等のあるいは類似の機能を有する装置等については同じ符号を用いるものとする。
【００４４】
図６に本発明の非同期到着する可変長光パケットのバッファリング装置の概要を示す。図６は、複数の光路で伝送された非同期到着する可変長光パケットを入力し、上記の可変長光パケットのアドレス情報に従った光路に出力する装置であって、光路１から光路４で伝送された光パケット信号を、出力１から出力４に振り分ける装置の構成である。それぞれの光路から入力した信号は、光検出器１で電気信号に変換され、そのヘッダ部の情報が読み込まれ、ルート情報としてルート情報処理器５で処理される。このルート情報は、Ｎ＝４の１×Ｎ光スイッチ３に送られ、振り向ける出力が決められる。光検出器１と１×Ｎ光スイッチ3との間にある遅延線２は、光パケット信号と電気信号との同期をとるためのものである。
ここで、Ｎ×１バッファ４は、本発明の特徴となるバッファであり、図７に示す構成を持っており、それぞれの光路の可変長光パケットの光パケット長を読みとる読取手段と、予め用意したクロックとそれに引き続く最近の前記可変長光パケットとの時間差（光パケット前置期間）を読みとる読取手段と、上記の光パケットを一時的に保管し、Ｂ通りの異なった遅延時間のいずれかを上記の光パケットに与える遅延素子からなるキューと、上記の光パケットを上記の複数の遅延素子に振り分ける光スイッチと、上記の複数の遅延素子に光路で接続された合波器と、合波器に光路で接続された出力用の光路と、を、含んでいる。
【００４５】
図７の光検出器６は、光信号を電気信号に変換することによって光パケット信号の長さｌ（エル）と光パケットと装置内部で発生した、あるいは外部から供給したクロック信号との間隔（パケット前置期間）ｔをバッファマネージャ１１で読み出すためのものである。このバッファマネージャ１１では、上記のｌとｔの値を用いて、それぞれの光路から伝送された光パケット信号が重ならないように、例えば１つの光路に振り分けるためのデータ処理を行う。この出力は、光スイッチを制御して遅延線９のどれを選択するか決めるものである。それぞれの遅延を通過した光パケット信号は、合波器で合波して出力される。
【００４６】
図６に示した構成では、光パケット信号はそれぞれ２回、電気信号に変換されるが、これは、図８に示す非同期到着する可変長光パケットのバッファリング装置の構成のように、光検出器１で電気信号に変換し、管理情報処理器１２により、前記の電気信号を用いて、あるいは、データ処理を施して、１×Ｎスイッチ３やＮ×１バッファ１３の制御を行うことができる。この場合のＮ×１バッファ１３の構成は、図９に示す様に、Ｎ×１バッファ４の構成と比べて、光電変換の回数を減らして光検出器の数を省くことができる。
【００４７】
管理情報処理器１２としては、図１０（a）あるいは図１１（a）の構成のものを用いることができる。
【００４８】
図１０（a）のものでは、電気信号に変換された信号の電圧の高低（Ｈ／Ｌ）を判定し、これを高低の切り替わる時刻を時刻記録器で記録し、この時刻データをレジスタに記録し、このデータをバッファマネージャに定期的に供給する。
【００４９】
また、図１１（a）のものでは、電気信号に変換された信号の電圧の高低（Ｈ／Ｌ）を判定したのち、これを定期的にシフトレジスタに書き込む。この高低の切り替え時期をシフトレジスタの番地を読み出し、クロック信号と比較することで、光パケット信号の長さｌ（エル）と光パケット間の間隔ｔを得るものである。
【００５０】
管理情報処理器１２としては、図１０（ｂ）に示す構成のものを用いることができる。これは、光検出器の出力を分岐し、一方をバッファマネージャへ供給する信号を生成する回路へ振り向け、他方をルート情報を抽出する回路に振り向ける。一方をバッファマネージャへ供給する信号を生成するために、電気信号に変換された信号は、電圧の高低（Ｈ／Ｌ）を判定し、高低の切り替わる時刻を時刻記録器で記録し、この時刻データをレジスタに記録する。このレジスタは、指定された時刻にある光パケット信号の情報を出力する。この出力は、切換器を用いてルート情報読取器からの出力にしたがって、それぞれのバッファマネージャへ振り向けられる。
【００５１】
管理情報処理器１２としては、図１１（ｂ）に示す構成のものを用いることができる。これは、光パケット信号を電気信号に変換された信号の電圧の高低（Ｈ／Ｌ）を判定したのち、これを定期的にシフトレジスタに書き込み、この高低の切り替え時期をシフトレジスタの番地を読み出すことで、光パケット信号の長さｌ（エル）と光パケット間の間隔を得るものである。
【００５２】
ここで、指定されたバッファリング時刻における光パケット信号の長さｌ（エル）と光パケットとクロック信号の間隔ｔについて説明する。まず、バッファリングをＴ秒ごとに行うもとし、この時間Ｔは、ｌの最小の値よりも小さいものとする。すなわち、時刻Ｔ0とそれからＴ時間後の時刻Ｔ1との間に、同一のポートに複数のパケットが到着しないよう、Ｔを決める。このとき、時刻Ｔ0と時刻Ｔ1との間に光パケット信号が到着しなければ、ｌは０（ゼロ）であり、ｔも０である。また、時刻Ｔ0と時刻Ｔ1との間に到着する光パケット信号の場合は、この光パケット信号に長さをｌ（エル）とし、時刻Ｔ0に近いほうのその光パケット信号とクロック信号の間隔をｔとする。つまり、複数の周期に光パケット信号がかかるほど長い場合は、その光パケット信号は、その光パケット信号のかかる最初の周期時刻に属するものとする。
【００５３】
以下で説明するのは、図１２に示すように、複数の光路で非同期に伝送された可変長光パケットを、重ならないように調整して１つの光路にまとめて伝送するバッファリング装置である。重ならないようにするためには、到着する光パケット信号の長さとその光パケット信号とクロック信号との間隔から、それぞれの光パケット信号に割り当てる遅延素子をきめて、最適な遅延を与えることによって行う。図１２に示した構成の装置では、優先的に光路１の光パケット信号がより遅延が少なくなる構成であるが、他の光路を優先させることは、容易であり、優先させるべき光路があれば、それを図１２の光路１と置き換えればよい。ここで、遅延素子の構成については、図１２では、０、Ｄ、２Ｄ、３Ｄと等差的に並んだものを用いているが、等差的でない場合でも、以下に説明する方法や構成をわずかに変えるだけで、適用することができる。
【００５４】
図１２（ｂ）は、光路１から４に与える遅延の一例である。光路４の光パケット信号（信号Ｄ）は、棄却したため、図１２（ｂ）には記載されていない。このように遅延時間を与えられ、重ならないように調整された光パケット信号は、出力用の光路では、図１２（ｃ）のように並ぶ。ここで、さらに長い遅延時間を選択することができれば、光路４の光パケット信号（信号Ｄ）を棄却せずに伝送できることは、容易に想像できる。
【実施例１】
【００５５】
本発明の主眼とする点は、単位時間あたりにより多くのパケットに対して上記の遅延時間を決定することである。このために、多数の演算器Ｐijを図１３のように配置して、遅延時間の決定に必要な処理を並列に処理する。ここでＰijは、ｉ段目の、第ｊ光路に設けられた演算器である。特に明示する場合には、ＰijをＰ（ｉ、ｊ）と表示するものとする。
【００５６】
図１３においては、ＩＮ1からＩＮ8までの８光路の光パケット信号の長さｌ（エル）と光パケット信号とクロック信号との間隔（パケット前置期間）ｔから、光パケット信号の棄却率が小さくなる調整を行う。この場合も、その遅延時間が等差的に並んだ遅延素子について示しており、出力となるΔnは、その基礎となる遅延値Dの係数を示している。図１３において、丸は演算器であり、四角はレジスタＲである。ここで、レジスタとしては、直前の演算器における演算結果を保持するレジスタＲ（１，１）と、第１光路の上にある光パケットの光パケット長と光パケット前置期間を保持するレジスタＲ′（１，１）とが配置される。それぞれのレジスタＲijについても、添え字（ｉｊ）によって、Ｒ（ｉ、ｊ）としてその位置を示す。演算器がある場合には、それと同じ添え字になるようにするものとする。このレジスタＲ′（１，１）は、演算処理のタイミングを調整するためのものであるので、必ずしもこの部分に設ける必要はなく、図２６に示す構成で演算を行い、キューにおける位置を更新する演算が行われるまでに、図には記載していないが、よく知られた遅延回路を用いて、そのタイミングの調整が行われればよい。しかし、上記の様に、レジスタＲ（１，１）と並列させることによって、回路設計を容易にすることができる。
【００５７】
図１３に示す構成は、出力用の光路において、入力された光パケットが重ならないようにするために、遅延素子の遅延値と読み取られた光パケット長と光パケット前置期間とを用いて、一時的に保管する遅延素子を決めるためのものである。便宜的に、その複数の光路には、１からＮの順序数ｎを与えて区別するものとする。以下においては、光路の番号について、対応する演算器やレジスタが無いときには、その機能は恒等演算を行うか、あるいは、その保持する値はゼロであるものとする。
【００５８】
このような場合に、それぞれの光路の光パケット長と光パケット前置期間については、以下の構成をもった光パケットのバッファリング装置で演算する。
１）  それぞれの光路の可変長光パケットの光パケット長を読みとる読取手段と、予め用意したクロック信号とそれに引き続く最近の前記可変長光パケットの到着時間との時間差（光パケット前置期間）とを読みとる読取手段と、上記の光パケットを一時的に保管し、Ｂ通りの異なった遅延時間のいずれかを上記の光パケットに与える複数の遅延素子からなるキューと、上記の光パケットを上記の複数の遅延素子に振り分ける光スイッチと、上記の遅延された光パケットを合波する合波器と、合波器に接続された出力用の光路とを含み、
２）出力用の光路において、入力された光パケットが重ならないようにするために、遅延素子の遅延値と読み取られた光パケット長と光パケット前置期間とを用いて、演算によって一時的に保管する遅延素子を決める制御装置を含み、
３）その制御装置においては、上記の複数の光路には１からＮの順序数ｎが与えられているものとし、以下においては、対応するものが無いときにはその値をゼロとするものとするとき、
それぞれの光路の光パケット長と光パケット前置期間について、
第１段の演算器とレジスタの並びとして、第（ｎ−１）光路上にある光パケットの光パケット長と光パケット前置期間と、第ｎ光路上の光パケットの光パケット長と光パケット前置期間との演算を行う演算器Ｐ（１，ｎ）と、その演算結果を保持するレジスタＲ（１，ｎ）と、が配置され、
４）第ｍ（２≦ｍ≦ｌｏｇ２  Ｎ）段の並びとして、レジスタＲ（ｍ−１，ｎ−２m-1）あるいはその複写とレジスタＲ（ｍ−１，ｎ）あるいはその複写との演算を行う演算器Ｐ（ｍ，ｎ）と、その演算結果を保持するレジスタＲ（ｍ，ｎ）と、が設けられ、
５）２M＝Ｎとなる第（Ｍ＋１）段には、演算器とキュー長の最後尾の情報を保持するレジスタＱが設けられ、
６）さらに、第１の可変長光パケットに与える遅延を、第１光路の光パケット長と光パケット前置期間あるいはその複写とレジスタＱの値との演算から決定する演算器Ｐ（Ｍ＋１，１）と、
７）１より大きいｎについて、第ｎの可変長光パケットに与える遅延を、第ｎの光路の光パケット長と光パケット前置期間あるいはその複写とレジスタＲ（Ｍ，ｎ−１）とレジスタＱの値との演算から決定する演算器Ｐ（Ｍ＋１，ｎ）と、が、設けられ、
８）演算器Ｐ（Ｍ＋１，１）あるいは、演算器Ｐ（Ｍ＋１，ｎ）の出力によりそれぞれの光路の可変長光パケットに与える遅延時間を調整することを特徴とする非同期到着する光パケットのバッファリング装置である。
【００５９】
演算器Ｐijの機能については、後に説明する。N個の要素a1, a2, ・, aN があった場合に、それぞれのプリフィックス和 a1,a1+a2, ・, a1+a2+,・,aN を求めることはプリフィックス和演算（prefix-sum operation）として知られており、N個の演算器を用いて並列処理によりその解を求めることは並列プリフィックス演算として知られている。しかし、その方法を用いてパケットの遅延を求める場合には、演算器あたりlog2N +1回の計算が必要になり、その間に次のパケットの遅延を求めることはできない。また順次、次段にそれぞれの演算結果を送ることによりそのスループットを改善する構成はパイプラインとして知られているが、すでに知られている処理方法を適用しても本発明には用いることができない。本発明に適用するには、特有の演算器の構成が必要で、バッファリング装置やバッファリング方法に応じた演算処理が必要である。
【００６０】
図１４に、以下で用いる変数について、そのタイムチャート上での対応を示す。図１４（ａ）は、本発明のバッファリング装置の出力として想定する光パケット信号の並びの一例である。この場合の入力は、８光路で与えられるものとしている。また、図１４（ｂ）は、以下の説明において用いられる変数の意味を示している。また、図１４（ｃ）は、基礎となる遅延時間の係数で、これが出力となる。
【００６１】
１段目のＰ1nは、図１５に示すフローチャートに従った処理を行う。この処理をプログラムで記述すれば、以下のようになる。
【００６２】
【表２】
2005033661.tif 000007
【００６３】
上記の表２においては、光パケットの長さをｌn（エルエヌ）とし、光パケット前置期間をｔnとし、また、ｎ＝０については、ｌn＝ｔn＝０とし、上記の複数の遅延素子の遅延は、遅延値Ｄで増加する遅延として並べることができる構成としている。この１段目の演算器は、入力側のそれぞれの光路の数Ｎについてそれぞれ備えられており、その１からＮまでの整数ｎについて、以下の処理を行う。
１）ｌn-1＝０であるとき、ｔnをｔn,1として出力し、あるいは、
ｌn-1＝０でないとき、ｔn-1を出力ｔn,1とし、
２）また、ｇn-1＝ｌn-1＋ｔn-1、とし、
３）ｌn＝０であるとき、ｇn-1 を出力ｆn,1 とし、あるいは、
ｌn＝０でないとき、Δnを（ｇn-1−ｔn）／Ｄを下回らない最小の整数として、（ｔn＋ｌn＋ΔnＤ）を出力ｆn,1とする。
【００６４】
２段目のＰ2nは、図１６に示すフローチャートに従った処理を行う。この処理をプログラムで記述すれば、以下のようになる。
【００６５】
【表３】
2005033661.tif 000008
【００６６】
上記の表３は、３からＮまでの整数ｎについて、ｎ番目のレジスタ内容と（ｎ−２）番目のレジスタ内容とを演算し、出力（ｆn,2、ｔn,2）を与える２段目のｎ−２番目の演算器が備えられている装置のバッファリング方法を示している。ここでは、以下の処理を行う。
【００６７】
１からＮのうちの整数ｎについて、
１）ｆn-2,1＝０であるとき、ｔn,1をｔn,2として出力し、あるいは、
ｆn-2, 1＝０でないとき、ｔn-2,1をｔn,2として出力し、
２）また、ｆn,1＝０であるとき、ｆn-2,1をｆn,2として出力し、あるいは、ｆn,1＝０でないときで、
２−１）Δnを（ｆn-2,1−ｔn,1）／Ｄを下回らない最小の整数として、（ｆn,1＋ΔnＤ）を出力ｆn,2とする。
【００６８】
３段目のＰ3nは、図１７に示すフローチャートに従った処理を行う。この処理をプログラムで記述すれば、以下のようになる。
【００６９】
【表４】
2005033661.tif 000009
【００７０】
一般に、ｍ段目のＰmnは、図１８に示すフローチャートに従った処理を行う。この処理をプログラムで記述すれば、以下のようになる。
【００７１】
【表５】
2005033661.tif 000010
【００７２】
上記の表５は、（ｍ−１）段目の演算器が定義されているとき、ｍ段目の演算器について、β＝２m-1として、β＋１からＮのｎについて、前段の演算器に接続された上記のｎ番目のレジスタ内容と（ｎ−β）番目のレジスタ内容とを演算し、出力（ｆn,m、ｔn,m）を与えるｍ段目の（ｎ−β）番目の演算器が備えられている装置のバッファリング方法を示しており、以下の処理を行う。
２≦ｍ  ≦  ｌｏｇ2  Ｎ、であるとして、
１）ｆn-β,m-1＝０であるとき、ｔn,m-1をｔn,mとして出力し、あるいは、
ｆn-β,m-1＝０でないとき、ｔn-β,m-1を出力ｔn,mとし、
２）また、ｆn,m-1＝０であるとき、ｆn-β,m-1をｆn,mとして出力し、あるいは、
ｆn,m-1＝０でないとき、
２−１）Δnを（ｆn-β,m-1−ｔn,m-1）／Ｄを下回らない最小の整数として、（ｆn,m-1＋ΔnＤ）を出力ｆn,mとする。
【００７３】
遅延値が、０、Ｄ、２Ｄ、・・・（Ｂ−１）Ｄ、と等差的に並んだ遅延素子を選択するためのデータとして、第ｎ光路の遅延値をΔnＤとするとき、このΔnを出力する。このためには、図１９に示すフローチャートに従った処理を行う。この処理をプログラムで記述すれば、表６のようになる。ただしこれは、１段目のそれぞれの演算器Ｐ（１，ｎ）には、それぞれの出力（ｆn,1、ｔn,1）を一時的に保存するレジスタＲ（１，ｎ）が設けられており、２からｌｏｇ2Ｎまでの整数ｍについて、（ｍ−１）段目の演算器が定義されているとき、ｍ段目の演算器について、β＝２m-1として、β＋１からＮのｎについて、前段の演算器Ｐ（ｍ−１，ｎ）に接続された上記のｎ番目のレジスタ内容Ｒ（ｍ−１，ｎ）と（ｎ−β）番目のレジスタ内容Ｒ（ｍ−１，ｎ−β）とを演算し、出力（ｆn,m、ｔn,m）を与えるｍ段目の（ｎ−β）番目の演算器Ｐ（ｍ，ｎ）が備えられている装置に用いるものである。
【００７４】
【表６】
2005033661.tif 000011
【００７５】
上記の表６は、上記のキューの長さをｑとするとき、１からＮのうちの整数ｎについて、Δnを求める方法を示しており、以下の処理を行う。ただし、以下においてはＭ＝ｌｏｇ2Ｎとする。
１）ｌn≠０でない場合には、終了し、
ｌn≠０である場合で、レジスタＲ（Ｍ，ｎ−１）にあるｆn-1，Mについて、
２）ｆn-1,M＝０のときには、臨時の値（ｔｅｍｐ）を設けて、（ｔｅｍｐ）＝ｑとし、
ｆn-1,M＝０でないときには、（ｑ−ｔn-1,M）／Ｄを下回らない最小の整数とｆn-1,Mとの和を（ｔｅｍｐ）とし、
３）（（ｔｅｍｐ）−ｔn）／Ｄを下回らない最小の整数をΔnとして、
ΔnがＢよりも小さいときは、Δnを出力し、
小さくないときは、それに対応する光パケットを棄却する。
【００７６】
このように、Ｍ＝ｌｏｇ2Ｎ、として、Ｍ段目の処理結果が得られ得られると同時に別の演算器でキュー長（ｑ）を更新する。これは、図２０に示すフローチャートに従った処理を行う。この処理をプログラムで記述すれば、以下のようになる。
【００７７】
【表７】
2005033661.tif 000012
【００７８】
一般に、パケット通信では、ＭＴＵ（最大転送サイズ）が設定されている。上記の表７は、ＭＴＵが設定されている場合の手続きについて示している。
１）レジスタＲ（Ｍ，Ｎ）に保持されたｆN,MについてｆN,M＝０が成立する場合は、（ｑ−Ｔ）と０との大きいほうを新規のキュー長（ｑnew）としてその値をレジスタＱに保持し、
ｆN,M＝０が成立しない場合は、Δを（ｑ−ｔN,M）／Ｄを下回らない最小の整数とするとき、
２）このΔがＢより小さいときには、（ｆN,M＋ΔＤ）と、（ＢＤ＋ＭＴＵ）との小さいほうからＴを引いた値と、０との大きいほうの値を新規のキュー長としてその値をレジスタＱに保持し、
このΔがＢより小さくないときには、（ｑ−Ｔ）を新規のキュー長とし、レジスタＱに保持する。
【００７９】
ＭＴＵ（最大転送サイズ）が設定されていない場合や、MTUがあっても処理を高速にするには、下記に示す方法でキュー長を設定することもできる。
１）レジスタＲ（Ｍ，Ｎ）に保持されたｆN,MについてｆN,M＝０が成立する場合は、（ｑ−Ｔ）と０との大きいほうを新規のキュー長（ｑnew）としてその値をレジスタＱに保持し、
ｆN,M＝０が成立しない場合は、Δを（ｑ−ｔN,M）／Ｄを下回らない最小の整数とするとき、
２）このΔがＢより小さいときには、（ｆN,M＋ΔＤ-T）と、０との大きいほうの値を新規のキュー長としてその値をレジスタＱに保持し、
このΔがＢより小さくないときには、（ｑ−Ｔ）を新規のキュー長とし、レジスタＱに保持する。
【実施例２】
【００８０】
上記のフローチャートの処理を高速に実行するためには、半導体回路（ハードウェア）で実現することが望ましい。しかし、ハードウェアを実現するためには、その処理手順をＨＤＬ(HardwareDescription Language)で記述して回路化する必要があるが、上記の表６では、最大値を求める関数（ｍａｘ）が使われており、現状ではこの演算を利用することができない。また、上記の処理手順では、除算が使われており、そのため回路が複雑になる、あるいは、処理が遅くなるなどの問題もある。そこで、Ｔ＝２pＤ（ｐは整数）となるように設定すると、これらの問題が解決される。
【００８１】
この場合の、１段目のＰ1nは、図２１に示すフローチャートに従った処理を行う。この処理をプログラムで記述すれば、以下のようになる。
【００８２】
【表８】
2005033661.tif 000013
【００８３】
上記の表８においては、上記の光路の数をＮ、その番号をｎとし、周期Ｔを適当に決めた単位時間（τ）の２の累乗倍、すなわち、Ｔ＝２aτ（ａは非負の整数）に設定し、ただし、Ｔは単位時間（τ）の整数倍の長さで表される最小パケット長を上回らないものとし、上記の読取手段は、周期Ｔで読み取りを行い、この読み取り手段を指定された時刻に通過する第ｎ番の光路の光パケットについて、光パケットの長さを単位時間の整数倍の長さで表されるｌn（エルエヌ）とし、光パケット前置期間を単位時間の整数倍の長さで表されるｔnとし、前記の光パケットの長さは、その長さを下回らない単位時間の整数倍で表すものとし、前記の前置期間は、その前置期間を上回らない単位時間の整数倍で表すものとし、また、ｎ＝０については、ｌn＝ｔn＝０とし、
上記の複数の遅延素子による遅延は、遅延値Ｄで増加する遅延として並べることができる構成とし、Ｄを２k（ｋは非負の整数）で与えるとき、また、表記法として、整数ｘの２進数の下位ｋビットに相当する整数をｘ(2)とし、前記の下位ｋビットを除いた残りの上位ビットで構成される２進数をｘ(1)とするとき、
上記の演算器は、入力側のそれぞれの光路の数Ｎについてそれぞれ備えられており、その１からＮまでの整数ｎについて、
１）ｌn-1＝０であるとき、ｔnをｔn,1として出力し、あるいは、
ｌn-1＝０でないとき、ｔn-1を出力ｔn,1として出力し、
２）また、ｇn-1＝ｌn-1＋ｔn-1、とし、
３）ｌn＝０であるとき、ｇn-1をｆn,1として出力し、
ｌn＝０でないとき、ｇn-1がｔn以下の場合には、ｇn-1(1)をΔnとし、
ｇn-1がｔn以下でない場合には、（ｇn-1(1)＋１）をΔnとし、
４）（ｔn(2)＋ｌn＋２kΔn）を出力ｆn,1とする。
【００８４】
２段目、３段目の処理手順については、それぞれ図２２、図２３に示す。また、これらのプログラムによる記述をそれぞれ、表８、表９に示す。
【００８５】
【表９】
2005033661.tif 000014
【００８６】
【表１０】
2005033661.tif 000015
【００８７】
これらの手順は、一般に、次のようになる。一般に、β＝２m-1とする場合に、β＋１からＮのｎについて、前段の演算器Ｐ（ｍ−１，ｎ）に接続された上記のｎ番目のレジスタ内容Ｒ（ｍ−１，ｎ）と（ｎ−β）番目のレジスタ内容Ｒ（ｍ−１，ｎ−β）とを演算し、出力（ｆn,m、ｔn,m）を与えるｍ段目の（ｎ−β）番目の演算器Ｐ（ｍ，ｎ）が備えられている装置のバッファリング方法で、
１）ｆn-β,m-1＝０であるとき、ｔn,m-1をｔn,mとして出力し、あるいは、
ｆn-β,m-1＝０でないとき、ｔn-β,m-1を出力ｔn,mとし、
２）また、ｆn,m-1＝０であるとき、ｆn-β,m-1をｆn,mとして出力し、あるいは、
ｆn,m-1＝０でないときで、
２−１）  ｆn-β,m-1(2)がｔn,m-1(2)以下の時には、ｆn-β,m-1(1)をΔnとし、
２−２）    ｆn-β,m-1がｔn,m-1以下でない時には、（ｆn-β,m-1(1)＋１）をΔnとし、
３）  （ｆn,m-1＋２kΔn）をｆn,mとして出力する。
【００８８】
また、Δnを出力する段では、図２４に示すフローチャートに従って演算処理を行う。これをプログラムで記述すると、次のようになる。
【００８９】
【表１１】
2005033661.tif 000016
【００９０】
表１１では、キューの長さをｑとするとき、１からＮまでの整数ｎについて、以下の処理をおこなうものである。
Ｍ＝log2 Ｎ  とするとき、
１）ｌn≠０でないときには、終了し、
２）ｌn≠０のときには、
２−１）ｆn-1,M＝０のときで、
ｑ(2)がｔn(2)以下のときには、ｑ(1)をΔnとし、
ｑ(2)がｔn(2)以下でないときには、（ｑ(1)＋１）をΔnとし、
２−２）ｆn-1,M＝０でないときで、
ｑ(2)がｔn-1,M(2)以下のときには、ｑ(1)をΔ1とし、
ｑ(2)がｔn-1,M(2)以下でないときには、（ｑ(1)＋１）をΔ1とし、さらに、
２−３−１）ｆn-1,Mがｔn(2)以下のときには、（Δ1＋ｆn-1,M(1)）をΔnとし、
２−３−２）ｆn-1,Mがｔn(2)以下でないときには、（Δ1＋１＋ｆn-1,M(1)）をΔnとし、
３）ΔnがＢよりも小さいときは、Δnを出力し、
小さくないときは、それに対応する光パケットを棄却する。
【００９１】
また、キュー長を更新する段では、図２５に示すフローチャートに従って演算処理を行う。これをプログラムで記述すると、次のようになる。
【００９２】
【表１２】
2005033661.tif 000017
【００９３】
表１２では、以下の手順で演算処理を行う。上記したように、光パケット通信では、一般にＭＴＵ（最大転送サイズ）が設定されている。
Ｍ＝log2Ｎとするとき、
１）ｆN,M＝０が成立する場合で
１−１）  ｑがＴより大きいときは、（ｑ−Ｔ）を新規のキュー長（ｑnew）とし、
１−２）  ｑがＴより大きくないときは、ｑnew＝０とし、
２）ｆN,M＝０でない場合で、
２−１）ｑ(2)がｔN,M(2)以下のときには、ｑ(1)をΔとし、
ｑ(2)がｔN,M(2)以下でないときには、（ｑ(1)＋１）をΔとし、
３−１）このΔがＢより小さいときで、
３−１−１）（ｆN,M＋２kΔ）が（２kＢ＋ＭＴＵ）よりも大きいときは、（２kＢ＋ＭＴＵ−Ｔ）をｑnewとし、
３−１−２）（ｆN,M＋２kΔ）が（２kＢ＋ＭＴＵ）よりも大きくないときで、
３−１−２−１）ｆN,M＋２kΔがＴより大きいときには、（ｆN,M＋２kΔ−Ｔ）をｑnewとし、
３−１−２−２）ｆN,M＋２kΔがＴより大きくないときには、ｑnew＝０とし、
３−２）このΔがＢより小さくないときには、（ｑ−Ｔ）をｑnewとする。
【００９４】
各周期において、キュー長を更新するときにすでにバッファが光パケットで溢れているときには、従来のラウンドロビン方式と同様に新たに到着するパケットを棄却する処理を行う。そうでない場合には、到着するすべての光パケットをキューに追加できると仮定してキュー長の更新を行う。到着したすべての光パケットをキューに適切に格納するための計算を複数の演算器で行う。
【実施例３】
【００９５】
上記の非同期可変長光パケット用の光パケットスイッチにおけるバッファリング装置を、同期固定長の光パケット用の光パケットスイッチにおけるバッファリングに用いる場合は、図２６の並列演算処理を簡略化して、図２７の構成とすることができる。同様に図１３に示す構成と同様に、データを順次先送りする点線部分を用いる構成で、変数を上記の同期固定長の場合とした図２８の構成とすることができる。図２７、２８では、その処理において用いる変数の数が少なくなっている。この変数の数を少なく出来るのは、この並列演算の際に、光パケット長が全て同じであることから、上記の処理における光パケット長の代わりに、光パケット個数を用いることが出来るためである。また、それぞれの光パケットは、同期していることから、光パケットの前置期間についての処理を省くことが出来る。このための処理は以下のように行う。
【００９６】
複数の光路から同期固定長光パケットを入力し、それぞれの光パケットにＢ通りの異なった遅延時間のいずれかを与えてひとつの光路に出力する装置であって、
それぞれの光路の光パケットの有無を読みとる読取手段と、
上記の複数の光パケットを一時的に保管してＢ通りの異なった遅延時間のいずれかを与える複数の遅延素子からなるキューと、上記の光パケットを上記の複数の遅延素子に振り分ける光スイッチと、上記の複数の遅延素子に光路で接続された合波器と、合波器に接続された出力用の光路とを含み、
出力用の光路において光パケットが重ならないようにするために、遅延素子の遅延値と、読み取られた光パケットの有無情報とを用いて、演算によって一時的に保管する遅延素子を決める制御装置をそなえ、
この制御装置は、
上記の複数の光路には１からＮの順序数ｎが与えられているものとし、以下においては、ｎについて対応するものが無いときには無視するものとするとき、
それぞれの光路の光パケット数について、
第１段の演算器とレジスタの並びとして、第（ｎ−1）光路上にある光パケットの光パケット数と、第ｎ光路上の光パケットの光パケット数と、の演算を行う演算器Ｐ（１，ｎ）と、その演算結果を保持するレジスタＲ（１，ｎ）と、が配置され、
第ｍ（２≦ｍ≦ｌｏｇ２  Ｎ）段の並びとして、レジスタＲ（ｍ−１，ｎ−２m-1）あるいはその複写とレジスタＲ（ｍ−１，ｎ）あるいはその複写との演算を行う演算器Ｐ（ｍ，ｎ）と、その演算結果を保持するレジスタＲ（ｍ，ｎ）と、が設けられ、
２M＝Ｎとなる整数Ｍについて、第Ｍ+1段には、演算器とキュー長の最後尾の情報を保持するレジスタＱが設けられ、
さらに、第１の同期固定長光パケットに与える遅延を、第１光路の光パケットの有無情報あるいはその複写とレジスタＱの値との演算から決定し、
１より大きいｎについて、第ｎの同期固定長光パケットに与える遅延を演算器Ｐ（Ｍ＋１，ｎ）を用いて、第ｎの光路の光パケットの有無情報あるいはその複写とレジスタＲ（Ｍ，ｎ−１）とレジスタＱの値との演算から決定することにより、それぞれの光路の同期固定長光パケットに与える遅延時間を調整する。
【００９７】
まず、１段目（Ｐ1n：２≦ｎ≦Ｎ）の演算器Ｐ1nについて説明する。ここでは、Ｎ個の演算器Ｐ1n（ただし、２≦ｎ≦Ｎ）に対して、（log2Ｎ＋１）Ｔ時間後以降、（log2Ｎ＋２）時間後までに、次の処理を行う。ここで、（log2Ｎ＋１）は、以下の処理を並列処理で行うステップ数であり、Ｔは、１ステップ当たりの時間である。この処理は、光パケットをそれぞれの遅延素子に振り分けるための光スイッチに到着する前に終了していなくてはならない。
【００９８】
１段目の場合は、ポート（ｎ−１）とポートｎへ到着する光パケットの有無を示すｌn-1、ｌnに到着時に１を、非到着時に０を入力する。１段目の演算器は、それらの情報を基に下記の処理を行ない、２つのポートに到着した光パケットの有無情報ｆnを出力する。
開始
ｌ0:=０
for each processor n、 in parallel (ｎ:=１ to Ｎ)
ｆn,1:=ｌn-1＋ｌn；
終了
【００９９】
また、２段目（Ｐ2n：３≦ｎ≦Ｎ）の場合は、次のように処理する。
（Ｎ−２）個の演算器Ｐ2n（ただし、３≦ｎ≦Ｎ）に対して、１段目の演算器から得た光パケットの有無情報について、
・ポート（ｎ−１）からポートｎに到着した光パケット数を表す、ｆn,1と、
・ポートｍａｘ（（ｎ−３），１）からポート（ｎ−２）に到着した光パケット数を表す、ｆn-2,1と、
を入力する。
また、下記の処理により、ポートｍａｘ（ｎ−３，１）からポートｎに到着した光パケット数ｆn,2を出力する。
開始
for each processor n、 in parallel (ｎ:=３ to Ｎ)
ｆn,2:=ｆn,1＋ｆn-2,1；
終了
【０１００】
また、３段目（Ｐ3n：５≦ｎ≦Ｎ）の場合は、次のように処理する。
（Ｎ−４）個の演算器Ｐ3n（ただし、５≦ｎ≦Ｎ）に対して、２段目の演算器から得た光パケットの有無情報について、
・ポート（ｎ−３）からポートｎに到着した光パケット数を表す、ｆn,2と、
・ポートmax(（ｎ−７）,1)からポート（ｎ−４）に到着した光パケット数を表す、ｆn-4,2と、
を入力する。
また、ポートｍａｘ（（ｎ−７），１）からポートｎに到着した光パケット数ｆn,3を次のように求め出力する。
開始
for each processor n、 in parallel (ｎ:=５ to Ｎ)
ｆn,3:=ｆn,2＋ｆn-4,2；
終了
【０１０１】
一般に、ｍ段目（Ｐmn：２m-1＋１≦ｎ≦Ｎ）の場合は次のようにする。
β＝２m-1とするとき、（Ｎ−２m-1）個の演算器Ｐmn（ただし、β＋１≦ｎ≦Ｎ)に対して、（ｍ−１）段目の演算器から得た光パケットの有無情報について、
・ポート（ｎ−２m-1＋１）からポートｎに到着した光パケット数表す、ｆn,m-1と、
・ポートｍａｘ（（ｎ−２m＋１），１）からポート（ｎ−２m-1）に到着した光パケット数表す、ｆn-β,m-1と、を入力する。
また、ポートｍａｘ（（ｎ−２m＋１），１）からｎに到着した光パケット数ｆn,mを次のように求め出力する。
開始
for each processor n、 in parallel (ｎ:=２m-1＋１ to Ｎ)
ｆn,m:=ｆn,m-1＋ｆn-β,m-1；
終了
【０１０２】
以上の処理により、ｍ段の演算器の並列構成におけるパイプライン処理によって、ｎ＝１、２、・・・、Ｎについて、ポート１からポートｎまでに到着する光パケット数を求めることができる。
【０１０３】
また、（Ｍ＋１）段目において、遅延を求める。このためのフローチャートを図２９に示す。また、このフローチャートに対応するプログラム例を以下に示す。
演算器ＰM+1,n（ただし、１≦ｎ≦Ｎ）については、入力としては、ポート１からｎ−１までに到着した光パケット数ｆn-1,M、ポートｎに到着する光パケットの有無ｌn、キュー長ｑであり、遅延Δnの値を出力する。
開始
for each processor n、 in parallel (ｎ:=１ to Ｎ)
begin
if (ｌn＝０) exit;
Δn:=q＋ｆn-1,M;
if (Δn＜Ｂ) Packet n is given delay Δn;
else Packet n is discarded;
end
終了
【０１０４】
遅延の導出と同時に別の演算器Ｐqで保持されているバッファ占有量の更新を行う。
・入力は、全ポートに到着した光パケット数ｆN,Mであり、
・内部変数は、Δ、キュー長ｑで、
・出力は、キュー長ｑnewである。
ｑnew:=ｍａｘ（（ｍｉｎ（ｆN,M＋ｑ，Ｂ）−１，０）；
【０１０５】
以上の処理をラウンドロビン形式の従来の方法で行う場合は、次のようにすることができる。
開始
for  ｎ:=１ to Ｎ  do
begin
if (ｌn＝０)
begin
if  f ＜B
begin
Packet n is given delay f×T;
f:= f ＋１;
end
else Packet n is discarded;
end
end
f := max（f−１，０）;
終了
【０１０６】
このように、従来の方法で、ラウンドロビン型の演算処理では、ループをＮ回まわす必要があるため、上記の本発明のように並列に演算処理する場合に比べて、1演算器あたりの開始から終了までの処理時間は、長時間である。言い換えると、本発明による演算器の処理時間を単位時間とすると、ラウンドロビン型の演算処理では、ポートあたり1つのパケットを処理するのに、N単位時間かかる。
【０１０７】
一般に、種々の光路で伝送された光パケットは、同期がずれているが、既に報告された光同期装置を用いることによって同期した光パケットにすることができる。また、伝送された光パケット最大の光パケット長を、それぞれの光パケット長とすることによって、固定長とすることができる。このような方法により、同期固定長光パケットを用いることができるようになる。
【０１０８】
また、前記の同期固定長光パケットを用意する方法は、非同期可変長光パケットの場合でも適用できるものであり、非同期可変長光パケットを、同期固定長光パケットにした後、上記の同期固定長光パケットのバッファリング装置に適用することによっても、非同期可変長光パケットをその出力において重ならないようにバッファリングできることは明らかである。
【産業上の利用可能性】
【０１０９】
木状に遅延線バッファユニットを配置し，それぞれにバッファ管理装置を置いた非特許文献６あるいは並列処理により遅延を求める非特許文献５に記載された方法による結果と、本発明の方法による結果とを、Ｎ＝８，６４，２５６，１０２４における比較を表１３に示す。
【０１１０】
【表１３】
2005033661.tif 000018
【０１１１】
ここでＮ＝２kは、入力数であり、Ｎp，ＴD、ＴPは、それぞれ、演算器数と処理遅延、演算器あたりの処理時間である。この表１３から分かるように、本発明では、用いる演算器数は大きいが、処理遅延（ＴD）や演算器当たりの処理時間（Ｔｐ）を小さくすることができる。また、本発明では、非特許文献５と比べてさらに、演算器あたりの処理時間については、入力数であるＮ（あるいはｋ）が増加しても変わらないという特徴がある。このように、処理遅延（ＴD）や演算器あたりの処理時間を小さくすることができるという特性は、高速なバッファリングを行うために必要である。特に、後者の演算器あたりの処理遅延を小さくできるという特性は、単位時間に数多くの処理を実現するものである。たとえば、Ｎ＝１０２４において、非特許文献５では、１１単位時間の間に入力あたり１つの処理しかできないが、本発明では、１１単位時間の間に入力あたり１１の処理ができる。このように、入力数が増加しても演算器当たりの最大処理時間の急速な増大をさけることができることがわかる。これは、本発明の目的とする効果であり、さらにＮが大きくなるに従い、この効果はさらに顕著にあらわれる。
【図面の簡単な説明】
【０１１２】
【図１】一般的に用いられるバッファの状態を表すキューを示す図である。
【図２】従来の光パケットスイッチアーキテクチャの例を示す図である。
【図３】光パケットスイッチに用いることのできる光スイッチを示す図である。
【図４】４入力×１出力の光バッファ構成を示す図である。
【図５】従来の光バッファ構成を示す図である。
【図６】本発明の光パケットのバッファリング装置を示すブロック図である。
【図７】Ｎ×１バッファの構成を示すブロック図である。
【図８】光パケットのバッファリング装置の構成を示すブロック図である。
【図９】Ｎ×１バッファの構成を示すブロック図である。
【図１０】管理情報処理器の構成を示すブロック図である。
【図１１】管理情報処理器の構成を示すブロック図である。
【図１２】非同期可変長光パケットのバッファリング装置を説明するためのタイムチャートである。
【図１３】非同期可変長の場合に用いる並列演算回路のブロック図である。
【図１４】非同期可変長光パケットのバッファリング装置を説明するためのタイムチャートである。
【図１５】１段目の並列演算器の演算処理のフローチャートである。
【図１６】２段目の並列演算器の演算処理のフローチャートである。
【図１７】３段目の並列演算器の演算処理のフローチャートである。
【図１８】ｋ段目の並列演算器の演算処理のフローチャートである。
【図１９】遅延値を出力する段の並列演算器の演算処理のフローチャートである。
【図２０】キュー長の更新を行う並列演算器の演算処理のフローチャートである。
【図２１】１段目の並列演算器の演算処理のフローチャートである。
【図２２】２段目の並列演算器の演算処理のフローチャートである。
【図２３】３段目の並列演算器の演算処理のフローチャートである。
【図２４】遅延値を出力する段の並列演算器の演算処理のフローチャートである。
【図２５】キュー長の更新を行う並列演算器の演算処理のフローチャートである。
【図２６】非同期可変長の光パケットに用いる他の並列演算回路のブロック図である。
【図２７】同期固定長の光パケットに用いる並列演算回路のブロック図である。
【図２８】同期固定長の光パケットに用いる他の並列演算回路のブロック図である。
【図２９】同期固定長の場合に遅延を求めるためのフローチャートである。
【符号の説明】
【０１１３】
１  光検出器
２  遅延線
３  １×Ｎ光スイッチ
４  Ｎ×１バッファ
５  ルート情報処理器
６  光検出器
７  遅延線
８  光スイッチ
９  遅延線
１０  合波器
１１  バッファマネージャ
１２  管理情報処理器
１３  Ｎ×１バッファ
【図１】
2005033661.tif 000019
【図２】
2005033661.tif 000020
【図３】
2005033661.tif 000021
【図４】
2005033661.tif 000022
【図５】
2005033661.tif 000023
【図６】
2005033661.tif 000024
【図７】
2005033661.tif 000025
【図８】
2005033661.tif 000026
【図９】
2005033661.tif 000027
【図１０】
2005033661.tif 000028
【図１１】
2005033661.tif 000029
【図１２】
2005033661.tif 000030
【図１３】
2005033661.tif 000031
【図１４】
2005033661.tif 000032
【図１５】
2005033661.tif 000033
【図１６】
2005033661.tif 000034
【図１７】
2005033661.tif 000035
【図１８】
2005033661.tif 000036
【図１９】
2005033661.tif 000037
【図２０】
2005033661.tif 000038
【図２１】
2005033661.tif 000039
【図２２】
2005033661.tif 000040
【図２３】
2005033661.tif 000041
【図２４】
2005033661.tif 000042
【図２５】
2005033661.tif 000043
【図２６】
2005033661.tif 000044
【図２７】
2005033661.tif 000045
【図２８】
2005033661.tif 000046
【図２９】
2005033661.tif 000047