(57)【特許請求の範囲】
【請求項１】
光スイッチの出力ファイバの光信号間の隙間を充填するシステムであって、
複数の波長を含む出力ファイバと、光信号に固有の遅延を引き起こす複数の遅延線とを含む光バッファと、
それぞれの出力ファイバの発信光信号間の隙間ごとの波長、時間位置、および持続時間を含むメモリと、
到着時間と持続時間とを有する新しい光信号が到着した時に、
新しい光信号の到着時間から測られる遅延線ごとの利用できる遅延を計算し、
特定の利用できる遅延が特定の隙間の時間位置内に入り、かつ特定の利用できる遅延から測った新しい光信号の持続時間が特定の隙間の持続時間内に当てはまる場合に、特定の隙間内に新しい光信号をスケジューリングする隙間充填／スケジューリング手段とを含む、システム。
【請求項２】
隙間充填／スケジューリング手段が、
出力ファイバの複数の波長の数に等しい複数の仮想波長をつくるためにさらに実行可能である請求項１に記載のシステム。
【請求項３】
前記システムは、新しい光信号を隙間内にスケジューリングすることに失敗した場合に、新しい光信号をスケジューリングするために、実行可能な別のスケジューリング手段をさらに含み、別のスケジューリング手段は、最小の占有率を有する仮想波長を決定し、新しい光信号を、既存の隙間によって占有されていない最小の遅延で、最小占有仮想波長にスケジューリングする請求項２に記載のシステム。
【請求項４】
別のスケジューリング手段が、
最小の占有率を有する仮想波長を決定し、
新しい光信号を、隙間によって占有されていない最小の遅延で、最小占有仮想波長にスケジューリングするために、実行可能である請求項３に記載のシステム。
【請求項５】
別のスケジューリング手段が、新しい光信号のスケジューリングで生成された新しい隙間をメモリに格納するために、さらに実行可能であり、
新しい隙間が、最小の占有率の終了時間に等しい開始時間、到着時間と最小の占有されていない遅延と新しい光信号の長さとの和に等しい終了時間、および最小占有波長に等しい波長を有する、請求項４に記載のシステム。
【請求項６】
書換えステップを行うことは、隙間充填／スケジューリング手段によって、
メモリの所定の数の隙間メモリ位置を維持し、
所定の数の隙間メモリ位置の各々に、新しい隙間を入れ、
所定の数の隙間メモリ位置の全てが満たされたら、新しい隙間が生成する時に、最も古い隙間メモリ位置をその新しい隙間のデータの組で書換えることによって達成される請求項５に記載のシステム。
【請求項７】
隙間充填／スケジューリング手段が、
メモリの各隙間を検査し、
最小の遅延から最大の遅延に順を追って各遅延を調べ、
特定の隙間の時間位置内に入る最小の遅延を使用して新しい光信号を遅延することで、新しい光信号をスケジューリングするために、さらに実行可能である請求項１に記載のシステム。
【請求項８】
隙間充填／スケジューリング手段が、
現在時間から最も近い隙間から最も遠い隙間に順を追って、メモリの各隙間を検査し、
現在時間に最も近い時間位置の隙間に、新しい光信号をスケジューリングしようと試みるために、さらに実行可能である請求項１に記載のシステム。
【請求項９】
隙間充填／スケジューリング手段が、
新しい光信号ごとに到着時間を計算するために、さらに実行可能である請求項１に記載のシステム。
【請求項１０】
隙間充填／スケジューリング手段が、
新しい光信号の到着時間と特定の遅延との和に等しい発信時間を新しい光信号に割り当て、
特定の隙間の波長に等しい発信波長を新しい光信号に割り当てるために、さらに実行可能である請求項１に記載のシステム。
【請求項１１】
隙間充填／スケジューリング手段が、メモリに新しい隙間を格納するために、さらに実行可能であり、
新しい隙間が、特定の隙間の波長に等しい波長、新しい光信号の到着時間と特定の遅延との和に等しい開始時間、および特定の隙間の終了時間に等しい終了時間を有する、請求項１０に記載のシステム。
【請求項１２】
隙間充填／スケジューリング手段が、新しい光信号を既存のどの隙間にもスケジューリングすることができない場合に、
別のスケジューリングルーチンを使用して新しい光信号をスケジューリングするために、さらに実行可能である請求項１に記載のシステム。
【請求項１３】
隙間充填／スケジューリング手段（１００）を含む、光信号（４０、５０）をスケジューリングするシステムであって、
隙間充填／スケジューリング手段（１００）が、
到着時間と持続時間とを有する新しい光信号（５０）が複数の遅延線（２２）を有する光スイッチ（１４）に到着した時に、
現在時間を新しい光信号（５０）に割り当て、
新しい光信号（５０）の宛先出力ファイバ（３５）を決定し、
出力ファイバ（３５）の隙間（Ｖ１）内に入る現在時間（４６）から測った遅延位置（Ｘ１）と、該遅延位置（Ｘ１）から始まるように位置決めされた新しい光信号（５０）を収容する終了位置との両方を有する、前記隙間（Ｖ１）に、新しい光信号（５０）をスケジューリングするために構成されており、隙間充填／スケジューリング手段（１００）は、メモリ内の隙間（Ｖ１、Ｖ２、Ｖ３、Ｖ４）を検査し、特定の隙間内にある遅延を使用して新しい光信号（５０）をスケジューリングするために、さらに実行可能であるシステム。
【請求項１４】
隙間充填／スケジューリング手段が、出力ファイバの波長の数に等しい複数の仮想波長をつくるために、さらに実行可能である請求項１３に記載のシステム。
【請求項１５】
隙間充填／スケジューリング手段が、
新しい光信号を隙間内にスケジューリングしようと試みるために実行可能な隙間充填手段と、
隙間充填手段が新しい光信号を隙間内にスケジューリングすることに失敗した場合に、新しい光信号をスケジューリングするために、実行可能な別のスケジューリングルーチンとをさらに含む請求項１４に記載のシステム。
【請求項１６】
別のスケジューリングルーチンが、最小占有率の仮想波長を決定し、既存の隙間によって占有されていない最小の遅延で、最小占有仮想波長に新しい光信号をスケジューリングするために、実行可能である請求項１５に記載のシステム。
【請求項１７】
別のスケジューリングルーチンが、新しい光信号のスケジューリングで生成された新しい隙間をメモリに格納するために、さらに実行可能である請求項１６に記載のシステム。
【請求項１８】
新しい隙間が、現在の占有に等しい開始時間、到着時間と最小の占有されない遅延と新しい光信号の長さとの和に等しい終了時間、および最小占有波長に等しい波長を有する、請求項１７に記載のシステム。
【請求項１９】
隙間充填／スケジューリング手段が、
メモリの所定の数の隙間メモリ位置を維持し、
所定の数の隙間メモリ位置の各々に、新しい隙間を入れ、
所定の数の隙間メモリ位置の全てが満たされたら、新しい隙間が生成した時に、最も古い隙間メモリ位置をその新しい隙間のデータの組で書換えることによって、メモリに新しい隙間を格納するように動作可能である請求項１８に記載のシステム。
【請求項２０】
隙間充填／スケジューリング手段が、
メモリの各隙間を検査し、
最小の遅延から最大の遅延に順を追って各遅延線を調べ、
特定の隙間内に入る最小の遅延を使用して、新しい光信号をスケジューリングするために、さらに実行可能である請求項１３に記載のシステム。
【請求項２１】
隙間充填／スケジューリング手段が、メモリ内に新しい隙間を格納するために、実行可能であって、
新しい隙間が、特定の隙間の波長に等しい波長、新しい光信号の到着時間と特定の遅延との和に等しい開始時間、および特定の隙間の終了時間に等しい終了時間を有する、請求項２０に記載のシステム。
【請求項２２】
隙間充填／スケジューリング手段が、
現在時間から時間位置を上昇してメモリの各隙間を検査し、
現在時間に最も近い時間位置の隙間に新しい光信号をスケジューリングするために、さらに実行可能である請求項１３に記載のシステム。
【請求項２３】
隙間充填／スケジューリング手段が、新しい光信号の到着時間を計算し、隙間内に入る遅延線を使用して新しい光信号を遅らせることで、新しい光信号をスケジューリングするために、さらに実行可能である請求項１３に記載のシステム。
【請求項２４】
隙間充填／スケジューリング手段が、新しい光信号を隙間にスケジューリングできない場合に、
別のスケジューリングルーチンを使用して、新しい光信号をスケジューリングするために、さらに実行可能である請求項１３に記載のシステム。
【請求項２５】
既存の発信光データパケットの間に生成された隙間を充填するために、多数の遅延線を備える光バッファを有する光スイッチからの光データパケットを出力ファイバにスケジューリングする方法であって、
出力ファイバの各々の波長ごとに仮想波長フィールドを生成するステップと、
現在時間を新しい光データパケットに割り当てるステップと、
新しい光データパケットの宛先出力ファイバを決定するステップと、
（ａ）現在時間から測られる光バッファ内の遅延線の遅延位置を決定するステップ、
（ｂ）宛先ファイバの仮想波長フィールドの各々にわたって、宛先ファイバの既存の隙間の各々の位置を、決定された遅延位置と比較するステップ、
（ｃ）遅延位置が、既存の隙間位置内に入る場合で、かつ遅延位置と新しい光データパケットの長さとの和が、隙間の終了位置内に入る場合に、新しい光パケットを選択された隙間にスケジューリングするステップ、および、
（ｄ）光バッファ内の遅延線ごとにステップ（ａ）〜（ｃ）を繰返すステップ、を含む隙間充填動作を行うステップと、
を含む光データパケットをスケジューリングする方法。
【請求項２６】
隙間充填動作を行うステップが、出力ファイバの複数の波長の数に等しい複数の仮想波長をつくることをさらに含む請求項２５に記載の方法。
【請求項２７】
隙間充填動作を行うステップが、
現在時間に最も近い隙間から現在時間から最も遠い隙間に順を追ってメモリの各隙間を検査するステップと、
最小の遅延から最大の遅延に順を追って各遅延線を調べるステップと、
隙間の時間位置内に入る最小の遅延か、現在時間に最も近い時間位置の隙間内に入る最小の遅延かいずれかを使用して新しい光データパケットをスケジューリングするステップとをさらに含む請求項２５に記載の方法。
【請求項２８】
隙間充填動作を行うステップが、新しいデータパケットが特定の隙間内にスケジューリングされる場合に、
新しい光データパケットの到着時間と特定の遅延との和に等しい発信時間を新しい光データパケットに割り当てるステップと、
特定の隙間の波長に等しい発信波長を新しい光データパケットに割り当てるステップとをさらに含む請求項２５に記載の方法。
【請求項２９】
隙間充填動作を行うステップが、メモリ内に新しい隙間を格納することをさらに含み、
新しい隙間が、特定の隙間の波長に等しい波長、新しい光データパケットの到着時間と特定の遅延との和に等しい開始時間、および特定の隙間の終了時間に等しい終了時間を有する、請求項２５に記載の方法。
【請求項３０】
新しい光データパケットを既存のどの隙間にもスケジューリングすることができない場合に、
別のスケジューリングルーチンを使用して、新しい光データパケットをスケジューリングすることをさらに含み、別のスケジューリングルーチンを使用するスケジューリングのステップが、
最小占有率の仮想波長を決定するステップと、
既存の隙間によって占有されていない最小の遅延で、最小占有仮想波長に新しい光データパケットをスケジューリングするステップとを含む請求項２５に記載の方法。
【請求項３１】
既存の発信光データパケットの間に生成された隙間を充填するために、多数の遅延線を備える光バッファを有する光スイッチからの光データパケットを出力ファイバにスケジューリングする方法であって、
出力ファイバの各々の波長ごとに仮想波長フィールドを生成するステップと、
現在時間を新しい光データパケットに割り当てるステップと、
新しい光データパケットの宛先出力ファイバを決定するステップと、
隙間内に入る遅延位置と、該遅延位置から始まるように位置決めされた新しい光データパケットを収容する終了位置との両方を有する、前記隙間に新しい光データパケットをスケジューリングするステップとを含み、
遅延位置が、現在時間から測られる特定の遅延線に関連付けられた位置である、光データパケットをスケジューリングする方法。
【請求項３２】
スケジューリングが、出力ファイバの複数の波長の数に等しい複数の仮想波長をつくることをさらに含む請求項３１に記載の方法。
【請求項３３】
スケジューリングが、
新しい光データパケットの到着時間を計算するステップと、
メモリの各隙間を検査するステップと、
最小の遅延から最大の遅延に順を追って各遅延線を調べるステップと、
隙間の時間位置内に入る最小の遅延を使用して、新しい光データパケットをスケジューリングしようと試みるステップとをさらに含む請求項３１に記載の方法。
【請求項３４】
スケジューリングが、新しいデータパケットを特定の隙間内にスケジューリングする場合に、
新しい光データパケットの到着時間と特定の遅延との和に等しい発信時間を新しい光データパケットに割り当てるステップと、
特定の隙間の波長に等しい発信波長を新しい光データパケットに割り当てるステップとをさらに含む請求項３１に記載の方法。
【請求項３５】
スケジューリングが、メモリ内に新しい隙間を格納することをさらに含み、
新しい隙間が、特定の隙間の波長に等しい波長、新しい光データパケットの到着時間と特定の遅延との和に等しい開始時間、および特定の隙間の終了時間に等しい終了時間を有する、請求項３１に記載の方法。
【請求項３６】
新しい光データパケットを既存のどの隙間にもスケジューリングすることができない場合に、
別のスケジューリングルーチンを使用して、新しい光データパケットをスケジューリングすることをさらに含み、別のスケジューリングルーチンを使用するスケジューリングのステップが、
最小占有率の仮想波長を決定することと、
既存の隙間によって占有されていない最小の遅延で、最小占有仮想波長に新しい光データパケットをスケジューリングすることとを含む請求項３５に記載の方法。
【請求項３７】
スケジューリングが、新しい光データパケットのスケジューリングで生成された新しい隙間をメモリに格納することをさらに含み、
新しい隙間が、現在の占有に等しい開始時間、到着時間と最小の占有されない遅延と新しい光データパケットの長さとの和に等しい終了時間、および最小占有波長に等しい波長を有する、請求項３６に記載の方法。
【請求項３８】
新しい隙間をメモリ内に格納するために、隙間書換えステップを行うことをさらに含む請求項３７に記載の方法。
【請求項３９】
隙間書換えステップを行うステップが、
メモリの所定の数の隙間メモリ位置を維持するステップと、
所定の数の隙間メモリ位置の各々に、新しい隙間を入れるステップと、
所定の数の隙間メモリ位置の全てが満たされたら、新しい隙間が生成した時に、最も古い隙間メモリ位置をその新しい隙間のデータの組で書換えるステップとをさらに含む請求項３８に記載の方法。
【請求項４０】
既存の発信光データパケットの間に生成された隙間を充填するために、多数の遅延線を備える光バッファを有する光スイッチからの光データパケットを出力ファイバにスケジューリングする方法であって、
前記方法が、隙間充填手段によって行われ、
隙間充填手段が、
出力ファイバの各々の波長ごとに、仮想波長フィールドを生成し、
現在時間を新しい光データパケットに割り当て、
新しい光データパケットの宛先出力ファイバを決定し、
隙間内に入る遅延位置と、該遅延位置から始まるように位置決めされた新しい光データパケットを収容する終了位置との両方を有する、前記隙間に出力すべき新しい光データパケットをスケジューリングするために、実行可能であり、
遅延位置が、現在時間から測られる特定の遅延線を使用して決定された時間位置である光データパケットをスケジューリングする方法。
【請求項４１】
隙間充填手段が、
特定の宛先ファイバに関連付けられたそれぞれの仮想波長フィールドの各隙間を検査し、
新しい光データパケットの到着時間を計算し、
メモリの各隙間を検査し、
最小の遅延から最大の遅延に順を追って各遅延線を調べ、
隙間の時間位置内に入る最小の遅延を使用して、新しい光データパケットをスケジューリングしようと試みるために、さらに実行可能である請求項４０に記載の方法。
【請求項４２】
隙間充填手段が、
新しい光データパケットの到着時間と特定の遅延との和に等しい発信時間を新しい光データパケットに割り当て、
特定の隙間の波長に等しい発信波長を新しい光データパケットに割り当てるために、さらに実行可能である請求項４０に記載の方法。
【請求項４３】
新しい光データパケットを既存のどの隙間にもスケジューリングすることができない場合に、
隙間充填／スケジューリング手段内の別のスケジューリングルーチンを使用して、新しい光データパケットをスケジューリングすることをさらに含む請求項４０に記載の方法。
【請求項４４】
隙間充填／スケジューリング手段が、新しい光データパケットのスケジューリングで生成された新しい隙間をメモリに格納するためにさらに実行可能である請求項４３に記載の方法。
【請求項４５】
隙間充填／スケジューリング手段が、新しい隙間をメモリ内に格納するために隙間書換えステップを行うために、さらに動作可能である請求項４４に記載の方法。
【請求項４６】
光データパケット（４０、５０）をスケジューリングする方法であって、前記光データパケットは、多数の遅延線を備える光バッファ（２０）を有する光スイッチ（１４）からの、出力ファイバ（３５）の既存の発信光データパケット（４０）間に生成される隙間（Ｖ１、Ｖ２、Ｖ３、Ｖ４）を充填するためにスケジューリングされており、前記方法は、
現在時間（４６）を新しい光信号（５０）に割り当てるステップと、
新しい光信号（５０）の宛先出力ファイバ（３５）を決定するステップと、
現在時間（４６）から測った特定の遅延線に関連付けされた位置である、隙間（Ｖ１）内に入る遅延位置（Ｘ１）と、該遅延位置（Ｘ１）から始まるように位置決めされた新しい光データパケット（５０）を収容する終了位置との両方を有する、前記隙間（Ｖ１）に、新しい光データパケット（５０）をスケジューリングするステップとを含み、
スケジューリングするステップは、
新しい光データパケット（５０）の到着時間を計算するステップと、メモリ（３８）の隙間（Ｖ１、Ｖ２、Ｖ３、Ｖ４）を検査するステップと、遅延線を調べるステップと、隙間（Ｖ１、Ｖ２、Ｖ３、Ｖ４）の時間位置内に入る遅延で新しい光データパケット（５０）をスケジューリングしようと試みるステップとをさらに含む、方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、広義には電気通信のシステムおよび方法に関し、より詳細には光通信のシステムおよび方法に関し、さらに詳細には、固定長および可変長、同期および非同期の光データパケット用の、光伝送のギャップを最小にする隙間（ｖｏｉｄ）充填手順を組み込む光ファイバ遅延線バッファに関する。
【０００２】
【従来の技術】
電気通信プロバイダは、次第に光ファイバをベースにしたネットワークに移ってきた。光ファイバ遠隔通信ネットワークでは、入力光信号を方向付け、適当な出力チャネルを選択するために、光ネットワークのノードに光スイッチまたは光ルータを含む光信号処理手段が必要である。２つ以上のパケットが同時に出力に到着するので、これらの光スイッチまたはルータはデータパケットを衝突させないように設計されている。光スイッチには、光スイッチを通過する光データパケットの処理を支援するバッファが含まれている。
【０００３】
【発明が解決しょうとする課題】
処理中の光データパケットの衝突を防止するようになっている従来型の光交換システムはある。しかし、これらの光交換システムは、同期（すなわち、タイムスロット形式の）および非同期の両方、および固定または可変長の光データパケットを含む全ての潜在的な光データパケットの構成をアドレス指定することができなかった。現在のインターネットプロトコル（ＩＰ）トラヒックは、非同期可変長トラヒックであるから、これには大きな制限がある。ある従来技術のシステムは、同期固定長データパケットで衝突のない交換を行う光スイッチアーキテクチャ専用の交換動作を開示している。しかし、このシステムは、可変長非同期光データパケットに対応しない特定のアーキテクチャの光スイッチに限定されている。さらに、この従来技術システムは、光データパケットのトランスポートと関連した隙間またはギャップを充填しない。他の従来技術のシステムも光データパケットの交換方法を開示しているが、その方法は、固定長の光データパケットに限定され、波長分割多重化（ＷＤＭ）に対応しない。ＷＤＭ伝送を使用しないと、システム性能全体が著しく劣化する。さらに、この従来技術のシステムも光トランスポートシステムで発生する隙間を充填する方法を開示していない。
【０００４】
【課題を解決するための手段】
本発明は、光ファイバデータパケット伝送システム用に以前に開発された光バッファリングシステムおよび方法に関連付けられた欠点と問題を実質的になくす、または少なくする、光伝送のバッファリングを行う改善されたシステムおよび方法を提供する。
【０００５】
より詳細には、本発明は、光通信システムにおけるスイッチング中に光信号間の隙間を充填するシステムおよび方法を提供する。本光スイッチは、それぞれの出力ファイバが多数の波長を含む一連の出力ファイバを有する光バッファを含み、さらに、入ってくる光信号に固有の遅延を引き起こす一連の遅延線を含む。また、本光スイッチは、メモリに常駐しプロセッサによって実行可能な隙間充填／スケジューリングソフトウェアプログラムを含む。また、そのメモリは、以前に予定された光データパケット間のそれぞれの隙間の、波長、時間位置、持続時間を含む。新しい光データパケットが、光スイッチに到着した時に、隙間充填／スケジューリングソフトウェアプログラムが、新しい光信号の到着時間から測られるそれぞれの遅延線の利用できる遅延を計算し、（１）利用できる遅延の１つが、１つの隙間の時間位置内に入る場合で、かつ（２）その特定の利用できる遅延から測った新しい光信号の持続時間が、その隙間の持続時間内に当てはまる場合に、特定の隙間内に新しい光信号をスケジューリングする。
【０００６】
新しい光データパケットが、既存の隙間のどれにも当てはまらない場合には（既存の隙間と合致する遅延がないためか、または、合致した隙間のスペースが新しいデータパケットを収容するだけ十分に大きくないためか、いずれかで）、隙間充填／スケジューリングソフトウェアプログラムは従来のスケジューリングルーチンを使用して新しい光データパケットを出力ファイバにスケジューリングする。従来のスケジューリングの間に新しい隙間が生成された場合には、プログラムがこの隙間をメモリに格納し、新しいデータパケットが到着した時に以前に充填されなかった隙間と一緒にこの新しい隙間を充填しようと試みる。
【０００７】
本発明は、同期トラヒックと共に使用される一様でないバッファの光データパケット、およびバッファが一様であるか一様でないかに無関係な非同期トラヒックの光データパケットの光スイッチングの間に本質的に生じる光データパケットの間の時間ギャップを充填することで、重要な技術的利点を提供する。
【０００８】
本発明は、非同期または同期で、可変長または固定長である光データパケットの隙間充填を行うことができる改良された光バッファを提供することで、他の技術的な利点を提供する。
【０００９】
本発明は、等価な一様なバッファよりも実質的に大きく見える一様でないバッファの隙間充填を行うことができる改良された光バッファを提供することで、さらに他の技術的な利点を提供する。これによって、同じハードウェアでシステム性能を向上させ、一方で、生じる光信号間のギャップを同時に充填する。
【００１０】
本発明は、光スイッチのアーキテクチャに無関係で、様々な光スイッチの固定／可変長光データパケット、同期／非同期光データトラヒックモードに対してバッファリングを行うことができる、光バッファを提供することで、他の技術的な利点を提供する。
【００１１】
本発明は、標準および波長分割の両方の多重化光伝送システムに対して等しく満足に動作する隙間充填バッファおよびバッファリングの方法を提供することで、まだその上に他の技術的な利点を提供する。
【００１２】
本発明は、バッファの深さまたはサイズを増やすことなしに、非同期可変長のトラヒックの下でファイバ遅延線光バッファの性能を向上することで、さらに他の技術的な利点を提供する。
【００１３】
本発明およびその利点をより完全に理解するために、同じ参照数字が同じ機能を示す添付の図面と共に行われる下記の説明が参照される。
【００１４】
【発明の実施の形態】
本発明の好ましい実施形態を図で示すが、同じ数字は様々な図面の同じ部分および対応する部分を参照するために使用される。図は、固定長同期トラヒックモードの例を代表的に図示するが（簡単にするために）、本発明は、固定長／可変長同期／非同期光データパケットの任意の組合わせに等しく適用することができることを理解されたい。
【００１５】
光データパケットのスイッチングまたはルーティングは、本発明によれば、光スイッチの出力を通過する、以前の光パケットの処理で生成されたギャップまたは隙間に光パケットを挿入する隙間充填／スケジューリングの手順を使用して達成される。本発明は、隙間充填方法を使用して光ファイバスイッチの性能を向上させる改良された光バッファを提供する。本発明の光バッファは、同期（すなわち、タイムスロット形式の）か非同期かいずれかの可変または固定光データパケットで隙間充填を行うことができる。
【００１６】
光スイッチは、システム固有の問題を発生させる光バッファを合体している。メモリ容量（すなわち、バッファの深さ）と保持時間が独立した別個のパラメータである電子的なメモリとは異なって、これら２つの機能が密接に関係しているという意味で、従来型の光バッファは縮退している。したがって、ｘ個のパケットの保持時間を有する光バッファは、ｘ個の（別個の）パケットの容量も同様に有している。したがって、より大きな保持時間を有するバッファを構築するには、バッファの深さを増す必要がある。従来型光バッファの１つの基本的な機能は、出力でトラヒックが確実に一様になるようにするために、遅延がバッファの深さの範囲全体に一様に１ユニット刻みでタイル張りになることである。この一様なタイル張りによって、先入れ先出し（ＦＩＦＯ）モードの動作が維持される。遅延の組を（１，２，３，．．．，Ｂ−１，Ｂ）で表すことができる。ここで、Ｂは全体的なバッファの深さである。
【００１７】
図１Ａと図１Ｂは、縮退したバッファと縮退しないバッファの違いを図で説明する。図１Ａは、同報通信選択スイッチに含まれた縮退した（すなわち、一様な）光バッファ１４を図示する。図１Ａにおいて、バッファ１４は、１とＢの間に１の刻みで一様に分布した合計でＢの遅延線２２を含む。同様に、それぞれの遅延線２２の長さまたは深さを図１Ａに示す。示されているように、遅延線２２の数は、図１Ａのバッファ１４の深さに等しい。バッファの深さに制限がある場合には、所定の深さＢに対してより優れた性能を有するより効率のよいバッファをつくるように努力するだけである。
【００１８】
図１Ｂは、一様でない分布の遅延線２４を利用して同じトータルのバッファの深さについてバッファの保持時間を増すために使用できる縮退しない（すなわち、一様でない）光バッファ１８を図示する。バッファ２０内のそれぞれの遅延線２４をＸ１からＸＢで示す。ここで、Ｂは再度トータルのバッファの深さ（すなわち、バッファにおける別個な遅延線の数）である。それぞれの遅延Ｘｉは、その値が別個の値であることを条件として任意の値を取ることができる（すなわち、遅延線２４は、１の単位の刻みで分布していない）。図１Ｂもまた、それぞれの遅延線２４の長さを示す。その結果できる光バッファ２０のバッファの深さもＢであるが、遅延線２４は１とＢの間に一様に分布していない。遅延線２４を完全に任意に分布させることができる。最大遅延｛Ｘｉ｝がＢより大きいか、またはＢより小さい場合には、保持時間がバッファ容量と異なるようになり、縮退が破れる。したがって、より大きなバッファをつくるために、ｍａｘ｛Ｘｉ｝＞Ｂの場合には、光バッファは、バッファの深さよりも大きな保持時間を有する。理解しやすくするために、図１Ａと図１Ｂに固定長のデータパケットのバッファを図示する。説明は、可変長パケットにも同じように適用できることを理解されたい。
【００１９】
一様でない遅延線を使用することで、偶然に、光バッファの出力で光データパケットの分布に隙間が生じる結果になる。これによって、余分な利用が生じ、システム性能を著しく劣化させることになる。非同期可変長インターネットプロトコル（ＩＰ）トランスポート（本来のＩＰトランスポート）の場合には、状況はもっと複雑であり、その場合には、たとえバッファが完全に一様な分布を有していても、これらの隙間は自然に存在する。
【００２０】
一様でないバッファまたは非同期トラヒックを使用して生じる問題を、従来の電子的通信システム８０（図２Ａ）と従来の光通信システム９０（図２Ｂ）の比較として、図２Ａと図２Ｂにさらに図示する。
【００２１】
図２Ａは、電気的なスイッチ１２の入力に異なる時間（ｔ１とｔ２）に到着した２つの電気的なデータパケットＥ１とＥ２を示す。両方の電気的なデータパケットＥ１とＥ２は、電気的スイッチ１２から出力１３で送出される。しかし、ｔ１とｔ２の間の時間差は、バッファリング（または、時間遅延）がなければ信号Ｅ１とＥ２は衝突しデータが失われるようなものである。したがって、電気的なスイッチ１３の中の電子的なバッファ（または、メモリ）は、Ｅ１とＥ２の両方が出力１３を通して送られる時に衝突しないように、電気的な信号Ｅ２を遅らせる（すなわち、出力信号が異なる時間位置を占める）。電子的なバッファは、非常に高精度なので、本質的に任意の必要な期間まで電気的なデータパケットＥ２を遅らせることができる。したがって、図２Ａに示されているように、電気的なデータパケットＥ２を十分長く遅らせて、Ｅ２が正確にＥ１の後に出力されるようにすることができる。このようにして、出力１３から、電気信号Ｅ１が時間ｔ１＋δに出力し、電気信号Ｅ２がｔ２＋δに出力する。ここで、δは電気的スイッチ１２による処理遅延である。
【００２２】
しかし、光スイッチには電気的スイッチと同じような高い精度がない。図２Ｂは、電気的なパケットＥ１とＥ２が電気的スイッチ１２に着いたのと同じ相対的位置で、光スイッチ１４に到着した２つの光データパケットＯ１とＯ２について、図２Ａと同じ状況を示す。しかし、光バッファ２０の細分性の精度が劣るために（特に、非同期および一様でない同期のトラヒックに対して）、光バッファ２０は、光スイッチ１４の出力１６で光処理遅延まで高精度に第２の光信号Ｏ２を遅らせることができない。Ｏ１とＯ２の間で衝突がないようにするために、光バッファ２０は、光処理遅延δよりも大きなある期間まで信号Ｏ２を遅らせなければならない。図２Ｂに示されているように、出力１６から、光信号Ｏ１が時間ｔ１＋δに出て行き、光信号Ｏ２が時間ｔ２＋δ＋Δに出力する。ここで、δは光スイッチ１２による処理遅延であり、Δは光バッファの遅延線で引き起こされた隙間３０である。その結果として、図２Ａを図２Ｂと比較して、２つの光信号Ｏ１とＯ２が占める時間スペース１７は、２つの電気信号Ｅ１とＥ２が占める時間スペース１５よりも大きい。Δで表される時間差は、光処理２０に固有なギャップまたは隙間３０である。また、このギャップまたは隙間３０をここでは余分な利用（ｅｘｃｅｓｓ  ｕｔｉｌｉｚａｔｉｏｎ）と呼ぶ。というのは、光パケットＯ１とＯ２の「見掛けの」利用は、時間スペース１７であるが、一方で「実際の」利用は時間スペース１７から隙間３０を引いたものであるからである。一様でないバッファが、同期光トラヒックと共に使用される時にはいつでもこの余分な利用の問題が起き、また、非同期光トラヒックでは常に（一様なバッファでも）この余分な利用の問題が起きる。
【００２３】
本発明は、隙間充填／スケジューリングソフトウェア１００を使用して、光信号Ｏ１と光信号Ｏ２の間の隙間３０に（および、同様に、光スイッチ動作中に他の光信号の間の他の隙間に）１つまたは複数の光パケットを入れる。図２Ｃは、第３の光データパケットＯ３を光データパケットＯ１と光データパケットＯ２の間の隙間３０に差し入れるために、本発明の隙間充填／スケジューリングソフトウェア１００を図２Ｂの状況に適用した結果を示す。図２Ｂでそうであったように、光信号Ｏ１とＯ２がそれぞれ時間ｔ１とｔ２に光スイッチ１４に到着する。さらに、第３の光信号Ｏ３が時間ｔ３に光スイッチ１４に到着する。隙間充填／スケジューリングソフトウェア１００を３つの光信号に適用することによって、第３の光信号Ｏ３が隙間３０に挿入されて隙間３０の一部を「充填する」。光信号Ｏ３の位置は、信号Ｏ１のきっかり後かもしれないし、あるいはそうではないかも知れないが、データを失うことがないようにするために、Ｏ１とＯ２の間のギャップに当てはまらなければならないことに留意する必要がある。図２Ｃに示されているように、出力１６から、光信号Ｏ３は時間ｔ３＋δに出力する。ここで、δは光スイッチ１２による処理遅延である。その結果、図２Ｃを図２Ｂと比較して、隙間充填／スケジューリングのソフトウェアプログラム１００を使用して、時間スペース１７が、ただ２つの光信号Ｏ１とＯ２ではなくて、今や３つの光信号（Ｏ１，Ｏ２およびＯ３）で占められる。このように、余分な利用が減少し、「見掛けの」利用は「実際の」利用により近くなる。
【００２４】
さらに例をあげて説明するために、図３Ａ〜図３Ｃに示されているような同期固定長パケットトラヒックのシナリオで空バッファの例を考えよう。図３Ａ〜図３Ｃのそれぞれで、時間Ｔ０の前でバッファは空であり、時間Ｔ０に６つの光パケットＰ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、およびＰ６が同じ出力に向けて光スイッチに到着し、一方で、時間Ｔ１に２つの追加のパケットＰ７とＰ８が同じ出力向けでその光スイッチに到着する。図３Ａ〜図３Ｃは、３つの異なったバッファ構成の光バッファの出力フィールド１１を示す。図３Ａは、バッファの深さＢ＝４（すなわち、番号１、２、３および４のユニットの４つの一様な遅延線を有する）である従来の縮退した（すなわち、一様な）バッファの出力フィールド１１を示す。最初の６つのパケットがバッファに到着した時に、Ｔ０より前の配置で、またはゼロ遅延で示されているように、第１のパケットＰ１は遅れていない。図３Ａに示されているように、第２のパケットＰ２は１ユニット（Ｔ１の後に置かれた）だけ遅れており、Ｐ３は２ユニットだけ遅れており、Ｐ４は３ユニットだけ遅れており、Ｐ５は４ユニットだけ遅れている。しかし、これで一様なバッファの４つの遅延線は使い尽くされるので、第６番目パケットＰ６は捨てられる。追加の２つのパケットＰ７とＰ８が時間Ｔ１に到着した時に、２つのパケットの最初のパケットＰ７を４ユニット遅らせることでＴ５で示される位置に格納することができるが、再びこれでバッファが一杯になり、Ｐ８のパケットが捨てられなけばならない。我々の例のこの一様な４遅延線バッファでは、バッファのオーバフローのためにパケットＰ６とＰ８が捨てられる結果になる。
【００２５】
図３Ｂは、６つの初期のパケット全てを収容できるように、バッファの深さＢ＝６（すなわち、６つの一様な遅延線１、２、３、４、５、および６のユニット）である他の従来の縮退した（すなわち、一様な）バッファの出力フィールドを示す。図３Ｂにおいて、最初の６つのパケットがバッファに到着した時に、６の保持時間であるために、それぞれのパケットは収容される。追加の２つのパケットＰ７とＰ８が時間Ｔ１に到着した時に、これらのパケットは次の２つの位置に格納され捨てられるパケットはない。我々の例のこの一様な６遅延線バッファでは、捨てられるパッケージはないという結果になる。図３Ｂのバッファは８つのパケットの全てを収容することができデータの喪失はない。しかし、図３Ｂの６つの遅延線バッファは図３Ａの４遅延線バッファより構築するのにより費用がかかる。
【００２６】
図３Ｃはそれぞれ１ユニット、２ユニット、３ユニットおよび６ユニット（すなわち、６の保持時間）の４つの遅延線を有する深さ４の縮退しない（すなわち、一様でない）バッファの出力フィールド１１を図示する。我々のシナリオでは、パケットＰ１、Ｐ２、Ｐ３、Ｐ４およびＰ５は、それぞれ、遅れなしで、１ユニットだけ遅れて、２ユニットだけ遅れて、３ユニットだけ遅れて、および６ユニットだけ遅れて（Ｄ６の後に差し込んで示される）送られる。パケット６は、再びバッファのオーバフローのために捨てられる。図３Ｃから理解できるように、出力フィールド１１に２つの隙間がある。すなわち、１つはＤ４とＤ５の間であり、もう１つはＤ５とＤ６の間である。
【００２７】
本発明の隙間充填を組み込む高機能スケジューリングを使用して、Ｔ４とＴ５の間の第１の隙間をパケットＰ７で充填することができ、次にパケットＰ８を６ユニットだけ遅らせてＴ７の後に配置する（Ｐ５をＰ１の６ユニット後に配置した方法と同様に）。図３Ｃに示される解決法ではパケット間の時間関係が複雑になり、結果としてパケットＰ７はパケットＰ５の前に出力に現れる。したがって、図３Ｃのバッファは、ＦＩＦＯでない保存バッファを表す。本発明の隙間充填／スケジューリングソフトウェア１００を我々のシナリオの深さ４の一様でないバッファで使用すると、隙間充填をしない一様なバッファでは２つのパケット（パケットＰ６とＰ８）であった（図３Ａに示されているように）のに比べて、１つのパケット（パケット６）が捨てられる結果になった。
【００２８】
図３Ｃを図３Ａおよび図３Ｂと比較することにより示されるように、図３Ｃの隙間充填を使用する縮退しないバッファは、同じバッファの深さを有する縮退したバッファ（図３Ａ）よりも優れた性能を示し、同じ保持時間を有する縮退したバッファ（図３Ｂ）よりも劣った性能を示すと考えられる。特定の遅延線でパケットごとに別個の波長であることを規定する波長の動作モードで、好ましくは全速力でバッファを動作させるべきであることに留意すべきである。これは言い換えると、実質的にバッファの容量を増すことになり、出力での波長インタリーブを可能にし、したがってデータ損失を実質的に減少する。
【００２９】
パケット間の隙間を充填する機能（例えば、図３ＣでパケットＰ４とパケットＰ５の間にパケットＰ７を配置すること）は、本発明の隙間充填／スケジューリングソフトウェア１００で行われる。図４は、モジュール形式の例示的な光スイッチ１４を示す。光データパケットは、入力ファイバ２５上で光スイッチ１４に伝わり、入力２８でスイッチ１４に到着する。データパケット４０は、隙間充填／スケジューリングソフトウェア１００で行われる隙間の優先順位付けおよびスケジューリングを補償するために処理遅延２２を受ける。光データパケットは、隙間充填／スケジューリングソフトウェア１００、メモリ３８およびプロセッサ３６を含むトランスポート２４を介して光バッファ２０にトランスポートされる。プロセッサ３６は、隙間充填／スケジューリングソフトウェア１００を実行し、一方でメモリ３８は、様々なデータパケットおよび隙間の情報を格納する。光データパケットは、光バッファ２０からトランスポート２６を介して出力ファイバ３５の出力３２に転送される。本発明では、本発明の隙間充填／スケジューリングソフトウェア１００を使用して光スイッチ１４により性能を向上させる。
【００３０】
本発明の隙間充填は、あらゆる入力／出力ファイバの多くのデータ波長にわたって、および同期または非同期で到着した可変長または一様な長さのデータパケットに対して作動する。本発明の目的のために、光スイッチにパケットの到着する時間およびパケットの宛先は、データパケットのヘッダから抽出される。それぞれのデータパケットを固定遅延線に入れて、ヘッダ情報を抽出し処理するのに必要な時間の量を補償する（すなわち、それぞれのデータパケットに「到着時間」を割り当てる）。下記により詳細に説明されているように、また、それぞれの光データパケットは、隙間充填／スケジューリングが終わるまで遅延線に留まる。データパケットを光バッファに送る前に、隙間充填／スケジューリングを行う。全ての出力ファイバ３５の波長ごとに、隙間充填／スケジューリングソフトウェア１００によって、フィールド（仮想波長フィールドと呼ばれる）が生成され、そのフィールドはその出力ファイバ３５に向けられたデータパケットで逐次充填される。ある入力波長で到着したデータパケットが同じ出力波長に配置される必要はない。このことは、光バッファ２０の全容量をよりよく利用するために波長をインタリーブすることを可能にする波長変換段階があることを意味している。
【００３１】
光データパケットが光バッファ２０により処理されるときに、それぞれの仮想波長フィールドの各隙間３０は、その時間位置と長さの表示とともにメモリ３８に格納される。新しい光データパケットが到着した時に、そのデータパケットが割り当てられている特定の出力に割り当てられた波長フィールドのどれかの既存の隙間３０を充填するような形で、隙間充填／スケジューリングソフトウェア１００のプログラムがパケットをスケジューリングしようと試みる。これは、波長の偏差は許容するがスペースの偏差は許容しない。したがって、特定の宛先ファイバに関連付けられた全ての波長フィールドの全ての隙間を検査し、そのパケットを隙間に入れるような遅延があることを見出した場合で、かつ隙間の持続時間がパケットの持続時間より長い場合には、その隙間に対応する時間にそのパケットをトランスポートするようにスケジューリングする。次に、新しくスケジューリングされたパケットの持続時間だけ隙間の長さを短くすることで隙間の充填を反映して、メモリ３８を更新する。
【００３２】
これらの遅延と長さの条件を満たす隙間がない場合には、光データパケットの通常のスケジューリングを行う。１つの実施形態では、隙間を充填しないデータパケットは、持続時間（データパケット到着の時間から測った）が最小である仮想フィールドの波長で所望の出力ファイバにトランスポートされるようにスケジューリングされる。データパケット到着時間から仮想波長フィールドの終わりまでの隔たりがバッファの最大保持時間よりも小さい場合には、その隔たりよりも大きいかまたは等しい最も近い遅延になるようにそのデータパケットを遅らせるようにデータパケットをスケジューリングする。その隔たりに等しい遅延である場合には、出力波長フィールドに新しい隙間は生成されない。遅延がその隔たりより大きい場合には、新しい隙間が生成される。新しい隙間の長さ、その開始時間およびその終了時間がメモリ３８に格納される。次のデータパケットが到着した時に、メモリの既存の隙間と共にこの新しい隙間を検査して、そのデータパケットがこれらの隙間のどれかを充填することができるかどうか決定する。パケットの到着時間から最小の持続時間を有する仮想波長フィールドの終わりまでの隔たりが、バッファ２０の保持時間より大きい場合には、それは利用できる遅延線がないことを意味し、その結果、バッファがオーバフローすることになり、パケットは捨てられる。
【００３３】
図５は、それぞれの光信号が光スイッチの出力に現れる時間と波長を計算する本発明の隙間充填／スケジューリングソフトウェア１００の動作を説明する図である。図５に示されているように、光データパケット４０は、非同期で可変長であるが、隙間充填／スケジューリングソフトウェア１００は、光データパケット処理の任意の動作モードに対して隙間を充填する。光スイッチ１４の入力ファイバと出力ファイバの各々には、ＷＤＭ動作の多数の波長がある。図５は、ファイバ用光バッファ当たり４波長の例を示す。示された出力ファイバでは、隙間充填／スケジューリングソフトウェアは、仮想待ち行列としても知られている仮想出力波長フィールド４２（λ１、λ２、λ３およびλ４で示される）をつくり、それらをメモリ３８に格納する。これらの仮想待ち行列４２は、それぞれの出力光データパケットが光バッファから出力するためにスケジューリングされる方法に従って、出力光データパケットの互いに対する関係を追跡する。隙間充填／スケジューリングソフトウェア１００が、データパケット４０で仮想出力波長フィールド４２の充填を始め、タイムスタンプを使用してある時間と波長で光バッファ２０を発信するようにそれぞれのデータパケットをスケジューリングする。図５の例では、例示的なファイバの４つの波長の仮想波長フィールドの占有は、データパケット４０で示されているようになっている。
【００３４】
また、図５は、現在時間４６、出力ファイバ（Ｘ１、Ｘ２およびＸ３で示される）の遅延線Ｘｉに対応する保持時間、および最大遅延線（Ｘ３）に対応する保持時間を示す。現在時間４６は、新しい（スケジューリングされていない）光データパケット４０の到着時間を表し、保持時間は、現在時間４６に対して示されている。図５に示されているように、バッファの深さまたはバッファ容量は３である。出力フィールドの隙間（Ｖ１、Ｖ２、Ｖ３、およびＶ４）をＶｉで示す。図５に示されているように、仮想波長λ１には３つのデータパケット４０と２つの隙間３０（Ｖ１とＶ２で示される）がある。
【００３５】
また、図５は、新しいデータパケット５０が着いた時に、どの隙間位置がアドレス指定可能であるかを図で示している。それぞれの遅延Ｘｉは、現在時間４６から測られる。現在時間４６と特定の遅延線の遅延の和が、隙間の時間位置を横切る時に、その隙間は、入って来るデータパケットで充填されるように利用できる。例えば、図５において、遅延Ｘ１は隙間Ｖ１を横切り、遅延Ｘ２は隙間Ｖ４を横切るが、一方で遅延Ｘ３は隙間を横切らないし、現在時間４６から計算されたどの遅延も隙間Ｖ２とＶ３を横切らない。したがって、図５の遅延Ｘ１、Ｘ２およびＸ３に関して、新しいデータパケット５０が現在時間４６に到着した時に、隙間Ｖ１とＶ４だけがアドレス指定可能である。
【００３６】
隙間充填／スケジューリングソフトウェアのプログラム１００の含む隙間充填プログラム１１０は、最初に新しい光データパケット５０が既存の隙間３０の１つを充填するように新しい光データパケット５０をスケジューリングしようと試みる。メモリは、バッファ２０の出力の隙間ごとに、隙間の開始時間、隙間の終了時間および波長を含む。１つの実施形態では、隙間充填プログラム１１０が、新しく到着したデータパケット５０を最初に隙間Ｖ１に、次に隙間Ｖ３に、次に隙間Ｖ４に、そして最後に隙間Ｖ２（すなわち、時間で一番古いものから一番新しいものに下る順番で）に当てはめようと試みるように動作する。言い換えれば、隙間充填プログラム１１０は、現在時間に最も近い時間位置の隙間に入れるように新しい光データパケット５０をスケジューリングしようと試みる。隙間の優先順位付けのこの選択が唯一の可能性ではないことに留意する必要がある。他の実施形態では、隙間充填／スケジューリングプログラム１００は、第１の単一波長内の隙間を調べ、次に第２の波長の全ての隙間を調べ、利用できる波長全部を通して隙間を調べることができる。さらに別の実施形態では、隙間充填／スケジューリングプログラム１００は、遅延線を最も短いものから最も長いものまで調べて特定の遅延が隙間内に入るかどうか決定することができる。新しいデータパケットを隙間内にきちんと当てはめることは、遅延された新しいパケットの始まりがその隙間の占める時間位置内に当てはまるように十分長く新しいパケットを現在時間４６から遅らせる遅延Ｘｉが存在しなければならないことを意味する。そのような遅延が見出せたら、次に、利用できる遅延Ｘｉから測られる隙間の長さの中に、パケットの長さが当てはまらなければならない。
【００３７】
動作において、図５の現在時間に等しい時間に新しいデータパケットが到着した時に、隙間充填プログラム１１０が、仮想待ち行列から隙間３０の時間位置および持続時間を呼出す。これらの隙間位置を遅延線と比較して、新しいデータパケットが到着した時に、どの隙間がアドレス指定可能であるかを決定する。隙間充填プログラム１１０は、最初に新しい光データパケット４０を隙間Ｖ１に当てはめようと試みる（現在時間４６に最も近いので）。示されているように、現在時間４６からの１番目の遅延Ｘ１は隙間Ｖ１内に入る。パケットの始まりが隙間Ｖ１内に入るように十分にパケットを遅らせる利用できる遅延（Ｘ１）があるので、この隙間Ｖ１は、新しいデータパケット５０をスケジューリングできる可能なタイムスロットということになる。新しいデータパケット５０の長さまたは持続時間が「現在時間＋遅延Ｘ」と隙間Ｖ１の終わりの間の時間間隔に当てはまれば、隙間充填プログラム１１０は新しいデータパケット５０を隙間Ｖ１に配置するだけである。言い換えると、新しいデータパケット５０は、遅延Ｘ１から遅延線の後の隙間Ｖ１に残っているスペースに当てはまらなければならない。したがって、たとえ１つの利用できる遅延で新しいパケットを特定の隙間内に当てはめるように十分に長く遅らせることができても、そのデータパケットを特定の隙間に差し入れることができるかどうかは新しいデータパケットのサイズに影響される。
【００３８】
新しいデータパケット５０が、隙間Ｖ１の利用できるスペースに当てはまると想定して、隙間充填／スケジューリングソフトウェア１００が、Ｘ１の遅延線を使用して新しいデータパケット５０を遅らせ、それを波長λ１に差し入れることで、隙間Ｖ１内に新しいデータパケット５０をスケジューリングする。隙間充填プログラム１１０が、新しいデータパケット５０が光バッファを発信する時間および新しいデータパケット５０が発信する波長を決定する。我々の例では、波長はλ１であり、発信する時間は現在時間に遅延Ｘ１を加えた時間である。理解できるように、新しいデータパケット５０による隙間Ｖ１の充填により、少なくとも１つ、多分に２つの新しいギャップ４８と５２が生成される。これらの新しいギャップ４８と５２を取り扱うためにいくつかのオプションがある。すなわち、（１）隙間充填／スケジューリングソフトウェアを使用して充填することができる「新しい隙間」として両方を追跡するオプション、（２）２つの中の１つを「新しい隙間」として取り扱うオプション、または、（３）どれも新しい隙間と考えないで両方を無視するオプションである。１つの実施形態では、隙間充填／スケジューリングソフトウェア１００は、新しいデータパケット５０の前に生じるギャップ４８を新しい隙間Ｖ１と考え、新しいデータパケット５０の後に生じるギャップ５２を無視する。ギャップ５２は、本質的には、どの光データパケットも使用しない損失スペースになる。検査すべき隙間の数が増加するにつれて複雑さが増すので、このようにする。隙間充填プログラム１１０は、仮想波長λ１の隙間位置が、元の隙間Ｖ２と新しい隙間Ｖ１’（ギャップ５２の位置の）を含むように、直ちにメモリ３８を更新することができる。次に新しいパケットが到着した時に、隙間Ｖ１”はＶ２、Ｖ３、およびＶ４と共に考えられる。
【００３９】
そうではなくて、新しいデータパケット５０が、隙間Ｖ１の利用できるスペース内に当てはまらないとすれば、その時に隙間充填プログラム１１０は、パケットを隙間Ｖ３に当てはめようと試みる。しかし、新しいパケットを隙間Ｖ３に差し入れるような遅延が存在しないので、プログラムは隙間Ｖ４に移る。プログラム１１０は、同様の分析を行って、遅延Ｘ２で新しいデータパケット５０を隙間Ｖ４に差し入れるように十分に遅らせることができるかどうかを決定する。次に、プログラム１１０は、その隙間が隙間Ｖ４の利用できるスペース（現在時間＋遅延Ｘ２と隙間Ｖ４の終わりの間）に当てはまるかどうかを決定する。新しいデータパケット５０が当てはまる場合には、次にそれを隙間Ｖ４にスケジューリングする。新しいデータパケット５０が隙間Ｖ４に当てはまらない場合には、隙間充填／スケジューリングソフトウェアの隙間充填部分は完了し、通常のスケジューリングが始まる。
【００４０】
隙間充填／スケジューリングソフトウェアプログラム１００は、新しい光データパケット４０を既存の隙間３０のどれかにスケジューリングすることができなかった時に、通常のスケジューリング規則に基づいて新しい光データパケット４０をスケジューリングするように従来のスケジューリングプログラム１２０も含むことができる。１つの実施形態では、従来のスケジューリングプログラム１２０は、最小の時間占有（持続時間）を有する仮想波長フィールド４２を見出し、この仮想波長フィールド４２に対して次の利用できる遅延で新しいデータパケット５０をスケジューリングしようと試みる。図５の例では、仮想波長フィールドλ４が最小のデータパケットの占有率を有する（すなわち、他の仮想波長フィールド４２は全て出力データパケットでより多く占有されている）。図５に示されているように、波長フィールドλ４内の既存のデータパケット４０は、Ｘ１の遅延を越え、さらにＸ２の遅延を越える長い時間を占有している。したがって、新しいデータパケット５０をＸ１またはＸ２だけ遅らせたとしても、波長λ４の既存のデータパケット４０との衝突が起き、データは失われるだろう。このような結果を避けるために、従来のスケジューリングプログラム１２０は、新しいパケット５０を波長λ４でＸ３まで遅らせるようにスケジューリングする。図５に示されているように、現在時間からＸ３時間遅れて波長λ４に新しいデータパケット５０を配置することで、波長フィールドλ４の現在のデータパケット占有の終わりと現在時間＋Ｘ３の時間の新しいデータパケット５０の始まりの間に「新しい隙間」６０が生成される。従来のスケジューリングプログラム１２０は、開始時間（λ４でのデータパケットの現在の長さ）、終了時間（現在時間＋Ｘ３）および新しい隙間６０の波長（λ４）をメモリ３８に格納する。隙間充填／スケジューリングソフトウェアプログラム１００は、仮想波長λ４の隙間位置が新しい隙間６０を含むように今やメモリ３８を更新することができる。次の新しいパケットが到着した時に、新しい隙間６０を充填に利用することができる。図５に図示した隙間充填プロセス全体は、光スイッチの出力ポートごとに光データパケットを光バッファに入れる前に行われる。
【００４１】
１つの実施形態では、複雑さの問題をなくすために、隙間充填／スケジューリングソフトウェアプログラム１００が、新しい隙間が生成される度に、既存の隙間の分析を行うことができる。新しい隙間が生成され、数が所定の設定数を上回ると、隙間充填／スケジューリングソフトウェア１００が、隙間書換えプロセスを行うことができ、その場合に、例えば、最も古い隙間が捨てられ、新しい隙間が捨てられた隙間のメモリ位置を占める。もしくは、新しい隙間が生成され、古い隙間が消えた場合には（すなわち、時間において、現在時間が過ぎた）、その時には、新しい隙間が消えた隙間のメモリ位置を取得する。動作において、隙間充填／スケジューリングソフトウェア１００は、所定の数まで全ての隙間を維持し、その数に達すると直ちに、新しい隙間が最も古い隙間のメモリ位置を取得し、最も古い隙間は失われる。図５の例では、４つのメモリ位置があり、この４つのメモリ位置を隙間Ｖ１、Ｖ２、Ｖ３およびＶ４が占めているものとする。今、新しいデータパケット５０が到着し、隙間Ｖ１または隙間Ｖ４に当てはまらないので、波長λ４で現在時間にＸ３を加えた時間に位置決めしなければならず、のように新しい隙間６０が生成されると仮定する。隙間メモリ位置の予め設定された数は４つであるから、新しい隙間６０が生成された時に、隙間充填／スケジューリングソフトウェア１００は、最初に、隙間Ｖ１が占有する時間位置を現在時間が過ぎて、隙間Ｖ１が消えてしまったかどうかを決定する。そうである場合には、プログラム１００は、新しい隙間６０を消えた隙間Ｖ１のメモリ位置に書込む。そうでない場合には、プログラム１００は、隙間Ｖ１が占有したメモリ位置を新しい隙間６０の情報で書き換える。したがって、古い隙間Ｖ１はメモリから捨てられる。その結果として、隙間Ｖ１が占有したスペースは、もはや新しいデータパケットを配置することができるスペースではなくなる。隙間位置情報を格納するために利用できる無制限のメモリ位置があれば、その時には、隙間充填ソフトウェア１００は、隙間書換えサブプログラムを含む必要はない。これに反して、メモリが制限されていれば、隙間充填ソフトウェアプログラム１００内に何らかの隙間書換え方法を含まなければならない。ここで説明した隙間書換え方法は、多くの隙間書換え方法の中の１つの例に過ぎない。
【００４２】
本発明の隙間充填／スケジューリングソフトウェアプログラム１００の１つの固有の特徴は、新しい光データパケットが到着した時に、プログラムが、最初に、以前に処理されたパケットの間に生成された隙間を充填しようと試み、成功しない場合に、従来のスケジューリングが採用されることである。本発明は、固定長パケットトラヒック（ＡＴＭ、光パケット）と可変長パケットトラヒック（ＩＰ、バースト）の両方のための縮退したまたは縮退しないバッファと共に使用することができる。
【００４３】
次の疑似コードは、隙間充填／スケジューリングソフトウェア１００の１つの実施形態の手法を記述する。
【００４４】
【数１】
0004484990.tif 000002
示されているように、隙間充填／スケジューリング方法は、オプションとして隙間充填／スケジューリングソフトウェア１００の一部であるいくつかの初期準備ステップを含む。初期準備ステップは、光スイッチのそれぞれの出力ファイバの波長ごとに仮想波長フィールドを生成すること、それぞれの新しい光データパケットが到着した時にそれを現在時間に割り当てること、およびその宛先出力ファイバを決定することを含む。この点で、隙間充填部が始まる。隙間充填プログラム１１０が、新しいデータパケットの宛先ファイバのそれぞれの隙間を、その宛先ファイバの全波長と光バッファの遅延線のそれぞれの遅延にわたって調べる。新しく到着したデータパケットごとに、それぞれの「現在時間」から遅延を測る。示されているように、最小の遅延から最大の遅延に順番に遅延を検査する。隙間充填プログラム１１０が、宛先ファイバの隙間の時間位置内に入る遅延を見出す（すなわち、測った遅延が隙間の開始より大きく隙間の終了より小さい）時に、プログラム１１０は、新しいデータパケットがその隙間に当てはまるかどうかを調べる。これは、新しいデータパケットの長さを遅延と隙間の終了の間のスペースとを比較することで決定される。新しいパケットが当てはまれば、新しいパケットをその隙間にスケジューリングする。当てはまらなければ、その時には、全ての遅延がなくなるまで、次の遅延を調べる。新しいデータパケットが隙間内に当てはまれば、プログラム１１０は、現在時間に遅延を加えた時間に等しい発信時間と隙間の波長である発信波長に新しいデータパケットを割り当てる。隙間充填プログラム１１０は、また、新しい隙間の開始を、現在時間と遅延と新しいデータパケットの長さとの和としてメモリに入れるように隙間書換えサブルーチンを始動することができる。
【００４５】
新しいデータパケットが、既存の隙間のどれにも当てはまらない場合には、新しいデータパケットをスケジューリングするために従来のスケジューリングルーチンを実行する。示されている実施形態では、従来のスケジューリングプログラム１２０は、宛先ファイバの仮想波長フィールドのどれが最小使用スペースを有するかを決定し、新しいデータパケットをその波長フィールドにスケジューリングする。その仮想波長フィールドに対して、現在スケジューリングされたデータの長さと波長が決定される。通常スケジューリングプログラム１２０は、次に、使用された長さを遅延（再び、現在時間から測れる）と比較して、波長フィールドに既にスケジューリングされたデータパケットと衝突しないように十分に新しいデータパケットを遅らせる遅延があるかどうかを決定する。ない場合には、新しいデータパケットは捨てられる。ある場合には、衝突を避ける最小の遅延まで新しいデータパケットを遅らせる。次に、従来のスケジューリングプログラムが、新しいデータパケットをスケジューリングして、現在時間に使用された遅延を加えた時間に等しい発信時間と最小の長さの波長である発信波長とを得る。疑似コードに示された実施形態では、従来のスケジューリングプログラム１２０は、新しく生成された隙間（その波長における最後のパケットの終了と新しいデータパケットの開始の間に）をメモリに格納する隙間書換えサブルーチンを含む。これは、既存のデータパケットの長さに等しい新しい隙間の開始、現在時間と遅延の和に等しい新しい隙間の終了、および新しい隙間の波長をメモリに記録することで行われる。
【００４６】
図６Ａと図６Ｂは、ネットワーク利用率が０．８である一様でタイムスロット形式のＡＴＭトラヒックの下で、シミュレーション１６×１６同報通信選択スイッチについて行われたシミュレーションのグラフである。図６Ａの破線の曲線は、ファイバ当たりの波長の数をパラメータとした縮退した場合についてのバッファ深さに対する光データパケット損失の確率を表す。実線の曲線は、遅延（１、２、３、．．．、Ｂ−１、２（Ｂ−１））を有する縮退しないバッファを示す。図６Ａに示されているように、シミュレーションは、縮退したバッファに比べると、縮退しないバッファのパケット損失の確率はかなり大きく減少することを示している。ファイバ当たり４波長のシナリオでは、６に等しい深さを有する縮退しないバッファは、７に等しい深さの縮退したバッファと同じ性能を有している。もっと大きな保持時間を有するバッファのシミュレーションが行われ、その結果が図６Ａに点線で示されている。また、図６Ａは、縮退しないバッファの性能は、２つの制限の間に収まっていることを示している。すなわち、３に等しい深さを有する縮退しないバッファの性能は、３に等しい深さを有する縮退したバッファと４に等しい深さを有する縮退したバッファの間に収まる等である。
【００４７】
図６Ｂは隙間充填のない場合に生じた余分な利用を示す。図６Ｂの実線は、隙間を充填することの成功の目安となる隙間充填の場合の余分な利用を示す。遅延線の選択は、（１、２、３、．．．、Ｂ−１、２（Ｂ−１）＋１）であり、最後の遅延線を前のシミュレーションに対して１の増分で増やし、その結果、保持時間をより大きくした。隙間充填係数（図４Ｂで点線による余分な利用で表される）は劣っているが、バッファの動作は僅かに優れている。このことは、その点を過ぎると隙間充填係数が劣化を始め性能に悪影響を与えるある点まで、保持時間を長くすることでより優れた性能を達成できることを示している。
【００４８】
【表１】
0004484990.tif 000003
表１は、一様なトラヒック条件およびバーストのトラヒック条件（２、４、および２０のバースト程度）に関して、同じ深さ制限と遅延｛１、２、３、４｝を有する縮退したバッファ、遅延｛１、２、３、６｝を有する縮退しないバッファ、および同じ保持時間制限と遅延｛１、２、３、４、５、６｝を有する縮退したバッファの間のパケット損失の確率を比較して示す。トラヒックロードは０．８であり、ファイバ当たり４波長が想定されている。これらのバーストトラヒック条件の下で、縮退したバッファに優る縮退しないバッファの利点をよりいっそうはっきりと理解することができる。表１に示されているように、トラヒックのバースト程度が一様から２のバースト程度に、４のバースト程度に、そして最後には２０のバースト程度にと増すにつれて、縮退しないバッファの性能は、同じバッファ深さを有する縮退したバッファの性能よりもますますよくなってくる。実際に、縮退しないバッファの性能は、同じ保持時間を有するがバッファの深さがずっと大きな縮退したバッファの性能に漸近的に近づく（例えば、バッファの深さ４の縮退しないバッファは、バッファの深さ６の縮退したバッファと殆ど同じ性能である）。
【００４９】
図７は、本発明の隙間充填／スケジューリングソフトウェア１００の利点を顕著に示している。図７において、本発明の隙間充填／スケジューリングソフトウェア１００を組み込むバースト程度が４でトラヒックロードが０．８の非同期可変長バーストトラヒックのもとで動作する４×４の光スイッチのシミュレーションを示す（本発明による隙間充填を使用しない同期および非同期のトラヒックと比較する）。非同期と示された一番上の線は、隙間充填をしない非同期動作の場合のバッファの深さに対するパケット損失の結果であり、一方で、同期と示された一番下の線は、隙間充填をしない同期動作の場合のパケット損失の結果である。「非同期、隙間充填」と示された中間の線は、本発明の隙間充填／スケジューリングソフトウェアを利用する非同期動作を示す。２つの非同期のグラフを比較する時に、隙間充填により性能が著しく向上し、実際に性能が同期の性能の方に近づいていることが明らかである。さらに、性能の向上はバッファの深さが大きいほどより実質的なものになる。例えば、４のバッファの深さで、非同期パケット損失は約０．７５であるが、非同期隙間充填動作のパケット損失は約０．５であり、隙間充填動作の結果として約０．２５（または、５０％）パケット損失が少なくなるという向上となる。それと比べると、１６のバッファの深さでは、非同期パケット損失は約０．５であり、一方で、非同期隙間充填動作のパケット損失は約０．００５であり、隙間充填動作の結果として約０．４９５（または、９９％）パケット損失が少なくなるという向上となる。
【００５０】
本発明は詳細に説明されたが、添付の特許請求の範囲に記載されている本発明の精神と範囲から逸脱することなしに、この点に関して様々な変化、置換、および変更を行うことができることは理解されるべきである。
【図面の簡単な説明】
【図１Ａ】縮退した光バッファを示す図である。
【図１Ｂ】縮退しない光バッファを示す図である。
【図２Ａ】従来の電気通信システムの一部を示す図である。
【図２Ｂ】図２Ａと比較するために、従来の光通信システムの一部を示す図である。
【図２Ｃ】本発明の実施形態を組み込む従来の光通信システムの一部を示す図である。
【図３Ａ】従来の縮退した光バッファの代表的な出力フィールドを示す図である。
【図３Ｂ】従来の縮退した光バッファの代表的な出力フィールドを示す図である。
【図３Ｃ】本発明の隙間充填／スケジューリングソフトウェアの実施形態の使用によって生じる縮退しない光バッファの代表的な出力フィールドを示す図である。
【図４】本発明の実施形態を組み込む例示的な光スイッチを示す図である。
【図５】本発明の隙間充填／スケジューリングソフトウェアの１つの実施形態の動作を示す図である。
【図６Ａ】縮退しない光バッファに対する縮退した光バッファの性能の利点を図示するために、ネットワークロードが０．８の一様な同期ＡＴＭトラヒックの下での１６×１６光同報通信交換のシミュレーションのグラフを示す図である。
【図６Ｂ】縮退しない光バッファに対する縮退した光バッファの性能の利点を図示するために、ネットワークロードが０．８の一様な同期ＡＴＭトラヒックの下での１６×１６光同報通信交換のシミュレーションのグラフを示す図である。
【図７】本発明の隙間充填動作の利点を図示するために、同期、非同期、および隙間充填のある非同期の条件の下で動作する光バッファに関して、バッファの深さに対するシミュレーションされたパケット損失のグラフを示す図である。
【符号の説明】
１１  光バッファの出力フィールド
１２  電気的スイッチ
１３  電気的スイッチの出力
１４  光バッファ、光スイッチ
１５、１７  時間間隔
１６  光スイッチの出力
１８  光ファイバ
２０  光バッファ
２２、２４  遅延線
２５  入力ファイバ
２６  トランスポート
２８  入力
３０  隙間
３２  出力
３５  出力ファイバ
３６  プロセッサ
３８  メモリ
４０、５０  データパケット
４２  仮想波長フィールド
４８、５２  ギャップ
１００  隙間充填／スケジューリングソフトウェア
Ｅ１、Ｅ２  電気的データパケット
０１、０２、０３  光データパケット
Ｘ１、Ｘ２、Ｘ３  遅延
【図１Ａ】
0004484990.tif 000004
【図１Ｂ】
0004484990.tif 000005
【図２Ａ】
0004484990.tif 000006
【図２Ｂ】
0004484990.tif 000007
【図２Ｃ】
0004484990.tif 000008
【図３Ａ】
0004484990.tif 000009
【図３Ｂ】
0004484990.tif 000010
【図３Ｃ】
0004484990.tif 000011
【図４】
0004484990.tif 000012
【図５】
0004484990.tif 000013
【図６Ａ】
0004484990.tif 000014
【図６Ｂ】
0004484990.tif 000015
【図７】
0004484990.tif 000016