JP2000244576A

JP2000244576A - 隙間充填を有する光ファイバ遅延線バッファ

Info

Publication number: JP2000244576A
Application number: JP32354699A
Authority: JP
Inventors: Ljubisa Tancevski; リユビサ・タンチフスキー
Original assignee: Alcatel SA; Nokia Inc
Current assignee: Alcatel Lucent SAS; Nokia Inc
Priority date: 1999-02-17
Filing date: 1999-11-15
Publication date: 2000-09-08
Anticipated expiration: 2019-11-15
Also published as: EP1030534A3; CA2288286A1; JP4484990B2; ATE540532T1; US6493120B1; EP1030534A2; EP1030534B1

Abstract

(57)【要約】【課題】光通信システムにおいて交換の間に、光信号
間の隙間を充填するシステムおよび方法を提供するこ
と。【解決手段】光スイッチは、メモリに常駐しプロセッ
サによって実行可能な隙間充填／スケジューリングソフ
トウェアプログラムを含む。新しい光データパケットが
光スイッチに到着した時に、プログラムは、利用できる
遅延を計算し、該遅延の１つが隙間の１つの時間位置内
に入り、特定の遅延から測った新しい光信号の持続時間
がその隙間の持続時間内に当てはまる場合に、その新し
い光信号をその特定の隙間内にスケジューリングする。
新しい光データパケットが既存のどの隙間にも当てはま
らない場合には、該プログラムは、従来のスケジューリ
ングのルーティングを使用して新しい光データパケット
を出力ファイバにスケジューリングする。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、広義には電気通信
のシステムおよび方法に関し、より詳細には光通信のシ
ステムおよび方法に関し、さらに詳細には、固定長およ
び可変長、同期および非同期の光データパケット用の、
光伝送のギャップを最小にする隙間（ｖｏｉｄ）充填手
順を組み込む光ファイバ遅延線バッファに関する。

【０００２】

【従来の技術】電気通信プロバイダは、次第に光ファイ
バをベースにしたネットワークに移ってきた。光ファイ
バ遠隔通信ネットワークでは、入力光信号を方向付け、
適当な出力チャネルを選択するために、光ネットワーク
のノードに光スイッチまたは光ルータを含む光信号処理
手段が必要である。２つ以上のパケットが同時に出力に
到着するので、これらの光スイッチまたはルータはデー
タパケットを衝突させないように設計されている。光ス
イッチには、光スイッチを通過する光データパケットの
処理を支援するバッファが含まれている。

【０００３】

【発明が解決しょうとする課題】処理中の光データパケ
ットの衝突を防止するようになっている従来型の光交換
システムはある。しかし、これらの光交換システムは、
同期（すなわち、タイムスロット形式の）および非同期
の両方、および固定または可変長の光データパケットを
含む全ての潜在的な光データパケットの構成をアドレス
指定することができなかった。現在のインターネットプ
ロトコル（ＩＰ）トラヒックは、非同期可変長トラヒッ
クであるから、これには大きな制限がある。ある従来技
術のシステムは、同期固定長データパケットで衝突のな
い交換を行う光スイッチアーキテクチャ専用の交換動作
を開示している。しかし、このシステムは、可変長非同
期光データパケットに対応しない特定のアーキテクチャ
の光スイッチに限定されている。さらに、この従来技術
システムは、光データパケットのトランスポートと関連
した隙間またはギャップを充填しない。他の従来技術の
システムも光データパケットの交換方法を開示している
が、その方法は、固定長の光データパケットに限定さ
れ、波長分割多重化（ＷＤＭ）に対応しない。ＷＤＭ伝
送を使用しないと、システム性能全体が著しく劣化す
る。さらに、この従来技術のシステムも光トランスポー
トシステムで発生する隙間を充填する方法を開示してい
ない。

【０００４】

【課題を解決するための手段】本発明は、光ファイバデ
ータパケット伝送システム用に以前に開発された光バッ
ファリングシステムおよび方法に関連付けられた欠点と
問題を実質的になくす、または少なくする、光伝送のバ
ッファリングを行う改善されたシステムおよび方法を提
供する。

【０００５】より詳細には、本発明は、光通信システム
におけるスイッチング中に光信号間の隙間を充填するシ
ステムおよび方法を提供する。本光スイッチは、それぞ
れの出力ファイバが多数の波長を含む一連の出力ファイ
バを有する光バッファを含み、さらに、入ってくる光信
号に固有の遅延を引き起こす一連の遅延線を含む。ま
た、本光スイッチは、メモリに常駐しプロセッサによっ
て実行可能な隙間充填／スケジューリングソフトウェア
プログラムを含む。また、そのメモリは、以前に予定さ
れた光データパケット間のそれぞれの隙間の、波長、時
間位置、持続時間を含む。新しい光データパケットが、
光スイッチに到着した時に、隙間充填／スケジューリン
グソフトウェアプログラムが、新しい光信号の到着時間
から測られるそれぞれの遅延線の利用できる遅延を計算
し、（１）利用できる遅延の１つが、１つの隙間の時間
位置内に入る場合で、かつ（２）その特定の利用できる
遅延から測った新しい光信号の持続時間が、その隙間の
持続時間内に当てはまる場合に、特定の隙間内に新しい
光信号をスケジューリングする。

【０００６】新しい光データパケットが、既存の隙間の
どれにも当てはまらない場合には（既存の隙間と合致す
る遅延がないためか、または、合致した隙間のスペース
が新しいデータパケットを収容するだけ十分に大きくな
いためか、いずれかで）、隙間充填／スケジューリング
ソフトウェアプログラムは従来のスケジューリングルー
チンを使用して新しい光データパケットを出力ファイバ
にスケジューリングする。従来のスケジューリングの間
に新しい隙間が生成された場合には、プログラムがこの
隙間をメモリに格納し、新しいデータパケットが到着し
た時に以前に充填されなかった隙間と一緒にこの新しい
隙間を充填しようと試みる。

【０００７】本発明は、同期トラヒックと共に使用され
る一様でないバッファの光データパケット、およびバッ
ファが一様であるか一様でないかに無関係な非同期トラ
ヒックの光データパケットの光スイッチングの間に本質
的に生じる光データパケットの間の時間ギャップを充填
することで、重要な技術的利点を提供する。

【０００８】本発明は、非同期または同期で、可変長ま
たは固定長である光データパケットの隙間充填を行うこ
とができる改良された光バッファを提供することで、他
の技術的な利点を提供する。

【０００９】本発明は、等価な一様なバッファよりも実
質的に大きく見える一様でないバッファの隙間充填を行
うことができる改良された光バッファを提供すること
で、さらに他の技術的な利点を提供する。これによっ
て、同じハードウェアでシステム性能を向上させ、一方
で、生じる光信号間のギャップを同時に充填する。

【００１０】本発明は、光スイッチのアーキテクチャに
無関係で、様々な光スイッチの固定／可変長光データパ
ケット、同期／非同期光データトラヒックモードに対し
てバッファリングを行うことができる、光バッファを提
供することで、他の技術的な利点を提供する。

【００１１】本発明は、標準および波長分割の両方の多
重化光伝送システムに対して等しく満足に動作する隙間
充填バッファおよびバッファリングの方法を提供するこ
とで、まだその上に他の技術的な利点を提供する。

【００１２】本発明は、バッファの深さまたはサイズを
増やすことなしに、非同期可変長のトラヒックの下でフ
ァイバ遅延線光バッファの性能を向上することで、さら
に他の技術的な利点を提供する。

【００１３】本発明およびその利点をより完全に理解す
るために、同じ参照数字が同じ機能を示す添付の図面と
共に行われる下記の説明が参照される。

【００１４】

【発明の実施の形態】本発明の好ましい実施形態を図で
示すが、同じ数字は様々な図面の同じ部分および対応す
る部分を参照するために使用される。図は、固定長同期
トラヒックモードの例を代表的に図示するが（簡単にす
るために）、本発明は、固定長／可変長同期／非同期光
データパケットの任意の組合わせに等しく適用すること
ができることを理解されたい。

【００１５】光データパケットのスイッチングまたはル
ーティングは、本発明によれば、光スイッチの出力を通
過する、以前の光パケットの処理で生成されたギャップ
または隙間に光パケットを挿入する隙間充填／スケジュ
ーリングの手順を使用して達成される。本発明は、隙間
充填方法を使用して光ファイバスイッチの性能を向上さ
せる改良された光バッファを提供する。本発明の光バッ
ファは、同期（すなわち、タイムスロット形式の）か非
同期かいずれかの可変または固定光データパケットで隙
間充填を行うことができる。

【００１６】光スイッチは、システム固有の問題を発生
させる光バッファを合体している。メモリ容量（すなわ
ち、バッファの深さ）と保持時間が独立した別個のパラ
メータである電子的なメモリとは異なって、これら２つ
の機能が密接に関係しているという意味で、従来型の光
バッファは縮退している。したがって、ｘ個のパケット
の保持時間を有する光バッファは、ｘ個の（別個の）パ
ケットの容量も同様に有している。したがって、より大
きな保持時間を有するバッファを構築するには、バッフ
ァの深さを増す必要がある。従来型光バッファの１つの
基本的な機能は、出力でトラヒックが確実に一様になる
ようにするために、遅延がバッファの深さの範囲全体に
一様に１ユニット刻みでタイル張りになることである。
この一様なタイル張りによって、先入れ先出し（ＦＩＦ
Ｏ）モードの動作が維持される。遅延の組を（１，２，
３，．．．，Ｂ−１，Ｂ）で表すことができる。ここ
で、Ｂは全体的なバッファの深さである。

【００１７】図１Ａと図１Ｂは、縮退したバッファと縮
退しないバッファの違いを図で説明する。図１Ａは、同
報通信選択スイッチに含まれた縮退した（すなわち、一
様な）光バッファ１４を図示する。図１Ａにおいて、バ
ッファ１４は、１とＢの間に１の刻みで一様に分布した
合計でＢの遅延線２２を含む。同様に、それぞれの遅延
線２２の長さまたは深さを図１Ａに示す。示されている
ように、遅延線２２の数は、図１Ａのバッファ１４の深
さに等しい。バッファの深さに制限がある場合には、所
定の深さＢに対してより優れた性能を有するより効率の
よいバッファをつくるように努力するだけである。

【００１８】図１Ｂは、一様でない分布の遅延線２４を
利用して同じトータルのバッファの深さについてバッフ
ァの保持時間を増すために使用できる縮退しない（すな
わち、一様でない）光バッファ１８を図示する。バッフ
ァ２０内のそれぞれの遅延線２４をＸ１からＸＢで示
す。ここで、Ｂは再度トータルのバッファの深さ（すな
わち、バッファにおける別個な遅延線の数）である。そ
れぞれの遅延Ｘｉは、その値が別個の値であることを条
件として任意の値を取ることができる（すなわち、遅延
線２４は、１の単位の刻みで分布していない）。図１Ｂ
もまた、それぞれの遅延線２４の長さを示す。その結果
できる光バッファ２０のバッファの深さもＢであるが、
遅延線２４は１とＢの間に一様に分布していない。遅延
線２４を完全に任意に分布させることができる。最大遅
延｛Ｘｉ｝がＢより大きいか、またはＢより小さい場合
には、保持時間がバッファ容量と異なるようになり、縮
退が破れる。したがって、より大きなバッファをつくる
ために、ｍａｘ｛Ｘｉ｝＞Ｂの場合には、光バッファ
は、バッファの深さよりも大きな保持時間を有する。理
解しやすくするために、図１Ａと図１Ｂに固定長のデー
タパケットのバッファを図示する。説明は、可変長パケ
ットにも同じように適用できることを理解されたい。

【００１９】一様でない遅延線を使用することで、偶然
に、光バッファの出力で光データパケットの分布に隙間
が生じる結果になる。これによって、余分な利用が生
じ、システム性能を著しく劣化させることになる。非同
期可変長インターネットプロトコル（ＩＰ）トランスポ
ート（本来のＩＰトランスポート）の場合には、状況は
もっと複雑であり、その場合には、たとえバッファが完
全に一様な分布を有していても、これらの隙間は自然に
存在する。

【００２０】一様でないバッファまたは非同期トラヒッ
クを使用して生じる問題を、従来の電子的通信システム
８０（図２Ａ）と従来の光通信システム９０（図２Ｂ）
の比較として、図２Ａと図２Ｂにさらに図示する。

【００２１】図２Ａは、電気的なスイッチ１２の入力に
異なる時間（ｔ_１とｔ_２）に到着した２つの電気的なデ
ータパケットＥ_１とＥ_２を示す。両方の電気的なデータ
パケットＥ_１とＥ_２は、電気的スイッチ１２から出力１
３で送出される。しかし、ｔ _１とｔ_２の間の時間差は、
バッファリング（または、時間遅延）がなければ信号Ｅ
_１とＥ_２は衝突しデータが失われるようなものである。
したがって、電気的なスイッチ１３の中の電子的なバッ
ファ（または、メモリ）は、Ｅ_１とＥ_２の両方が出力１
３を通して送られる時に衝突しないように、電気的な信
号Ｅ_２を遅らせる（すなわち、出力信号が異なる時間位
置を占める）。電子的なバッファは、非常に高精度なの
で、本質的に任意の必要な期間まで電気的なデータパケ
ットＥ_２を遅らせることができる。したがって、図２Ａ
に示されているように、電気的なデータパケットＥ_２を
十分長く遅らせて、Ｅ_２が正確にＥ_１の後に出力される
ようにすることができる。このようにして、出力１３か
ら、電気信号Ｅ１が時間ｔ _１＋δに出力し、電気信号Ｅ
２がｔ_２＋δに出力する。ここで、δは電気的スイッチ
１２による処理遅延である。

【００２２】しかし、光スイッチには電気的スイッチと
同じような高い精度がない。図２Ｂは、電気的なパケッ
トＥ１とＥ２が電気的スイッチ１２に着いたのと同じ相
対的位置で、光スイッチ１４に到着した２つの光データ
パケットＯ１とＯ２について、図２Ａと同じ状況を示
す。しかし、光バッファ２０の細分性の精度が劣るため
に（特に、非同期および一様でない同期のトラヒックに
対して）、光バッファ２０は、光スイッチ１４の出力１
６で光処理遅延まで高精度に第２の光信号Ｏ２を遅らせ
ることができない。Ｏ１とＯ２の間で衝突がないように
するために、光バッファ２０は、光処理遅延δよりも大
きなある期間まで信号Ｏ２を遅らせなければならない。
図２Ｂに示されているように、出力１６から、光信号Ｏ
１が時間ｔ _１＋δに出て行き、光信号Ｏ２が時間ｔ_２＋
δ＋Δに出力する。ここで、δは光スイッチ１２による
処理遅延であり、Δは光バッファの遅延線で引き起こさ
れた隙間３０である。その結果として、図２Ａを図２Ｂ
と比較して、２つの光信号Ｏ１とＯ２が占める時間スペ
ース１７は、２つの電気信号Ｅ１とＥ２が占める時間ス
ペース１５よりも大きい。Δで表される時間差は、光処
理２０に固有なギャップまたは隙間３０である。また、
このギャップまたは隙間３０をここでは余分な利用（ｅ
ｘｃｅｓｓｕｔｉｌｉｚａｔｉｏｎ）と呼ぶ。という
のは、光パケットＯ１とＯ２の「見掛けの」利用は、時
間スペース１７であるが、一方で「実際の」利用は時間
スペース１７から隙間３０を引いたものであるからであ
る。一様でないバッファが、同期光トラヒックと共に使
用される時にはいつでもこの余分な利用の問題が起き、
また、非同期光トラヒックでは常に（一様なバッファで
も）この余分な利用の問題が起きる。

【００２３】本発明は、隙間充填／スケジューリングソ
フトウェア１００を使用して、光信号Ｏ１と光信号Ｏ２
の間の隙間３０に（および、同様に、光スイッチ動作中
に他の光信号の間の他の隙間に）１つまたは複数の光パ
ケットを入れる。図２Ｃは、第３の光データパケットＯ
３を光データパケットＯ１と光データパケットＯ２の間
の隙間３０に差し入れるために、本発明の隙間充填／ス
ケジューリングソフトウェア１００を図２Ｂの状況に適
用した結果を示す。図２Ｂでそうであったように、光信
号Ｏ１とＯ２がそれぞれ時間ｔ_１とｔ_２に光スイッチ１
４に到着する。さらに、第３の光信号Ｏ３が時間ｔ_３に
光スイッチ１４に到着する。隙間充填／スケジューリン
グソフトウェア１００を３つの光信号に適用することに
よって、第３の光信号Ｏ３が隙間３０に挿入されて隙間
３０の一部を「充填する」。光信号Ｏ３の位置は、信号
Ｏ１のきっかり後かもしれないし、あるいはそうではな
いかも知れないが、データを失うことがないようにする
ために、Ｏ１とＯ２の間のギャップに当てはまらなけれ
ばならないことに留意する必要がある。図２Ｃに示され
ているように、出力１６から、光信号Ｏ３は時間ｔ_３＋
δに出力する。ここで、δは光スイッチ１２による処理
遅延である。その結果、図２Ｃを図２Ｂと比較して、隙
間充填／スケジューリングのソフトウェアプログラム１
００を使用して、時間スペース１７が、ただ２つの光信
号Ｏ１とＯ２ではなくて、今や３つの光信号（Ｏ１，Ｏ
２およびＯ３）で占められる。このように、余分な利用
が減少し、「見掛けの」利用は「実際の」利用により近
くなる。

【００２４】さらに例をあげて説明するために、図３Ａ
〜図３Ｃに示されているような同期固定長パケットトラ
ヒックのシナリオで空バッファの例を考えよう。図３Ａ
〜図３Ｃのそれぞれで、時間Ｔ０の前でバッファは空で
あり、時間Ｔ０に６つの光パケットＰ１、Ｐ２、Ｐ３、
Ｐ４、Ｐ５、およびＰ６が同じ出力に向けて光スイッチ
に到着し、一方で、時間Ｔ１に２つの追加のパケットＰ
７とＰ８が同じ出力向けでその光スイッチに到着する。
図３Ａ〜図３Ｃは、３つの異なったバッファ構成の光バ
ッファの出力フィールド１１を示す。図３Ａは、バッフ
ァの深さＢ＝４（すなわち、番号１、２、３および４の
ユニットの４つの一様な遅延線を有する）である従来の
縮退した（すなわち、一様な）バッファの出力フィール
ド１１を示す。最初の６つのパケットがバッファに到着
した時に、Ｔ０より前の配置で、またはゼロ遅延で示さ
れているように、第１のパケットＰ１は遅れていない。
図３Ａに示されているように、第２のパケットＰ２は１
ユニット（Ｔ１の後に置かれた）だけ遅れており、Ｐ３
は２ユニットだけ遅れており、Ｐ４は３ユニットだけ遅
れており、Ｐ５は４ユニットだけ遅れている。しかし、
これで一様なバッファの４つの遅延線は使い尽くされる
ので、第６番目パケットＰ６は捨てられる。追加の２つ
のパケットＰ７とＰ８が時間Ｔ１に到着した時に、２つ
のパケットの最初のパケットＰ７を４ユニット遅らせる
ことでＴ５で示される位置に格納することができるが、
再びこれでバッファが一杯になり、Ｐ８のパケットが捨
てられなけばならない。我々の例のこの一様な４遅延線
バッファでは、バッファのオーバフローのためにパケッ
トＰ６とＰ８が捨てられる結果になる。

【００２５】図３Ｂは、６つの初期のパケット全てを収
容できるように、バッファの深さＢ＝６（すなわち、６
つの一様な遅延線１、２、３、４、５、および６のユニ
ット）である他の従来の縮退した（すなわち、一様な）
バッファの出力フィールドを示す。図３Ｂにおいて、最
初の６つのパケットがバッファに到着した時に、６の保
持時間であるために、それぞれのパケットは収容され
る。追加の２つのパケットＰ７とＰ８が時間Ｔ１に到着
した時に、これらのパケットは次の２つの位置に格納さ
れ捨てられるパケットはない。我々の例のこの一様な６
遅延線バッファでは、捨てられるパッケージはないとい
う結果になる。図３Ｂのバッファは８つのパケットの全
てを収容することができデータの喪失はない。しかし、
図３Ｂの６つの遅延線バッファは図３Ａの４遅延線バッ
ファより構築するのにより費用がかかる。

【００２６】図３Ｃはそれぞれ１ユニット、２ユニッ
ト、３ユニットおよび６ユニット（すなわち、６の保持
時間）の４つの遅延線を有する深さ４の縮退しない（す
なわち、一様でない）バッファの出力フィールド１１を
図示する。我々のシナリオでは、パケットＰ１、Ｐ２、
Ｐ３、Ｐ４およびＰ５は、それぞれ、遅れなしで、１ユ
ニットだけ遅れて、２ユニットだけ遅れて、３ユニット
だけ遅れて、および６ユニットだけ遅れて（Ｄ６の後に
差し込んで示される）送られる。パケット６は、再びバ
ッファのオーバフローのために捨てられる。図３Ｃから
理解できるように、出力フィールド１１に２つの隙間が
ある。すなわち、１つはＤ４とＤ５の間であり、もう１
つはＤ５とＤ６の間である。

【００２７】本発明の隙間充填を組み込む高機能スケジ
ューリングを使用して、Ｔ４とＴ５の間の第１の隙間を
パケットＰ７で充填することができ、次にパケットＰ８
を６ユニットだけ遅らせてＴ７の後に配置する（Ｐ５を
Ｐ１の６ユニット後に配置した方法と同様に）。図３Ｃ
に示される解決法ではパケット間の時間関係が複雑にな
り、結果としてパケットＰ７はパケットＰ５の前に出力
に現れる。したがって、図３Ｃのバッファは、ＦＩＦＯ
でない保存バッファを表す。本発明の隙間充填／スケジ
ューリングソフトウェア１００を我々のシナリオの深さ
４の一様でないバッファで使用すると、隙間充填をしな
い一様なバッファでは２つのパケット（パケットＰ６と
Ｐ８）であった（図３Ａに示されているように）のに比
べて、１つのパケット（パケット６）が捨てられる結果
になった。

【００２８】図３Ｃを図３Ａおよび図３Ｂと比較するこ
とにより示されるように、図３Ｃの隙間充填を使用する
縮退しないバッファは、同じバッファの深さを有する縮
退したバッファ（図３Ａ）よりも優れた性能を示し、同
じ保持時間を有する縮退したバッファ（図３Ｂ）よりも
劣った性能を示すと考えられる。特定の遅延線でパケッ
トごとに別個の波長であることを規定する波長の動作モ
ードで、好ましくは全速力でバッファを動作させるべき
であることに留意すべきである。これは言い換えると、
実質的にバッファの容量を増すことになり、出力での波
長インタリーブを可能にし、したがってデータ損失を実
質的に減少する。

【００２９】パケット間の隙間を充填する機能（例え
ば、図３ＣでパケットＰ４とパケットＰ５の間にパケッ
トＰ７を配置すること）は、本発明の隙間充填／スケジ
ューリングソフトウェア１００で行われる。図４は、モ
ジュール形式の例示的な光スイッチ１４を示す。光デー
タパケットは、入力ファイバ２５上で光スイッチ１４に
伝わり、入力２８でスイッチ１４に到着する。データパ
ケット４０は、隙間充填／スケジューリングソフトウェ
ア１００で行われる隙間の優先順位付けおよびスケジュ
ーリングを補償するために処理遅延２２を受ける。光デ
ータパケットは、隙間充填／スケジューリングソフトウ
ェア１００、メモリ３８およびプロセッサ３６を含むト
ランスポート２４を介して光バッファ２０にトランスポ
ートされる。プロセッサ３６は、隙間充填／スケジュー
リングソフトウェア１００を実行し、一方でメモリ３８
は、様々なデータパケットおよび隙間の情報を格納す
る。光データパケットは、光バッファ２０からトランス
ポート２６を介して出力ファイバ３５の出力３２に転送
される。本発明では、本発明の隙間充填／スケジューリ
ングソフトウェア１００を使用して光スイッチ１４によ
り性能を向上させる。

【００３０】本発明の隙間充填は、あらゆる入力／出力
ファイバの多くのデータ波長にわたって、および同期ま
たは非同期で到着した可変長または一様な長さのデータ
パケットに対して作動する。本発明の目的のために、光
スイッチにパケットの到着する時間およびパケットの宛
先は、データパケットのヘッダから抽出される。それぞ
れのデータパケットを固定遅延線に入れて、ヘッダ情報
を抽出し処理するのに必要な時間の量を補償する（すな
わち、それぞれのデータパケットに「到着時間」を割り
当てる）。下記により詳細に説明されているように、ま
た、それぞれの光データパケットは、隙間充填／スケジ
ューリングが終わるまで遅延線に留まる。データパケッ
トを光バッファに送る前に、隙間充填／スケジューリン
グを行う。全ての出力ファイバ３５の波長ごとに、隙間
充填／スケジューリングソフトウェア１００によって、
フィールド（仮想波長フィールドと呼ばれる）が生成さ
れ、そのフィールドはその出力ファイバ３５に向けられ
たデータパケットで逐次充填される。ある入力波長で到
着したデータパケットが同じ出力波長に配置される必要
はない。このことは、光バッファ２０の全容量をよりよ
く利用するために波長をインタリーブすることを可能に
する波長変換段階があることを意味している。

【００３１】光データパケットが光バッファ２０により
処理されるときに、それぞれの仮想波長フィールドの各
隙間３０は、その時間位置と長さの表示とともにメモリ
３８に格納される。新しい光データパケットが到着した
時に、そのデータパケットが割り当てられている特定の
出力に割り当てられた波長フィールドのどれかの既存の
隙間３０を充填するような形で、隙間充填／スケジュー
リングソフトウェア１００のプログラムがパケットをス
ケジューリングしようと試みる。これは、波長の偏差は
許容するがスペースの偏差は許容しない。したがって、
特定の宛先ファイバに関連付けられた全ての波長フィー
ルドの全ての隙間を検査し、そのパケットを隙間に入れ
るような遅延があることを見出した場合で、かつ隙間の
持続時間がパケットの持続時間より長い場合には、その
隙間に対応する時間にそのパケットをトランスポートす
るようにスケジューリングする。次に、新しくスケジュ
ーリングされたパケットの持続時間だけ隙間の長さを短
くすることで隙間の充填を反映して、メモリ３８を更新
する。

【００３２】これらの遅延と長さの条件を満たす隙間が
ない場合には、光データパケットの通常のスケジューリ
ングを行う。１つの実施形態では、隙間を充填しないデ
ータパケットは、持続時間（データパケット到着の時間
から測った）が最小である仮想フィールドの波長で所望
の出力ファイバにトランスポートされるようにスケジュ
ーリングされる。データパケット到着時間から仮想波長
フィールドの終わりまでの隔たりがバッファの最大保持
時間よりも小さい場合には、その隔たりよりも大きいか
または等しい最も近い遅延になるようにそのデータパケ
ットを遅らせるようにデータパケットをスケジューリン
グする。その隔たりに等しい遅延である場合には、出力
波長フィールドに新しい隙間は生成されない。遅延がそ
の隔たりより大きい場合には、新しい隙間が生成され
る。新しい隙間の長さ、その開始時間およびその終了時
間がメモリ３８に格納される。次のデータパケットが到
着した時に、メモリの既存の隙間と共にこの新しい隙間
を検査して、そのデータパケットがこれらの隙間のどれ
かを充填することができるかどうか決定する。パケット
の到着時間から最小の持続時間を有する仮想波長フィー
ルドの終わりまでの隔たりが、バッファ２０の保持時間
より大きい場合には、それは利用できる遅延線がないこ
とを意味し、その結果、バッファがオーバフローするこ
とになり、パケットは捨てられる。

【００３３】図５は、それぞれの光信号が光スイッチの
出力に現れる時間と波長を計算する本発明の隙間充填／
スケジューリングソフトウェア１００の動作を説明する
図である。図５に示されているように、光データパケッ
ト４０は、非同期で可変長であるが、隙間充填／スケジ
ューリングソフトウェア１００は、光データパケット処
理の任意の動作モードに対して隙間を充填する。光スイ
ッチ１４の入力ファイバと出力ファイバの各々には、Ｗ
ＤＭ動作の多数の波長がある。図５は、ファイバ用光バ
ッファ当たり４波長の例を示す。示された出力ファイバ
では、隙間充填／スケジューリングソフトウェアは、仮
想待ち行列としても知られている仮想出力波長フィール
ド４２（λ_１、λ_２、λ_３およびλ_４で示される）をつ
くり、それらをメモリ３８に格納する。これらの仮想待
ち行列４２は、それぞれの出力光データパケットが光バ
ッファから出力するためにスケジューリングされる方法
に従って、出力光データパケットの互いに対する関係を
追跡する。隙間充填／スケジューリングソフトウェア１
００が、データパケット４０で仮想出力波長フィールド
４２の充填を始め、タイムスタンプを使用してある時間
と波長で光バッファ２０を発信するようにそれぞれのデ
ータパケットをスケジューリングする。図５の例では、
例示的なファイバの４つの波長の仮想波長フィールドの
占有は、データパケット４０で示されているようになっ
ている。

【００３４】また、図５は、現在時間４６、出力ファイ
バ（Ｘ１、Ｘ２およびＸ３で示される）の遅延線Ｘｉに
対応する保持時間、および最大遅延線（Ｘ３）に対応す
る保持時間を示す。現在時間４６は、新しい（スケジュ
ーリングされていない）光データパケット４０の到着時
間を表し、保持時間は、現在時間４６に対して示されて
いる。図５に示されているように、バッファの深さまた
はバッファ容量は３である。出力フィールドの隙間（Ｖ
１、Ｖ２、Ｖ３、およびＶ４）をＶｉで示す。図５に示
されているように、仮想波長λ_１には３つのデータパケ
ット４０と２つの隙間３０（Ｖ１とＶ２で示される）が
ある。

【００３５】また、図５は、新しいデータパケット５０
が着いた時に、どの隙間位置がアドレス指定可能である
かを図で示している。それぞれの遅延Ｘｉは、現在時間
４６から測られる。現在時間４６と特定の遅延線の遅延
の和が、隙間の時間位置を横切る時に、その隙間は、入
って来るデータパケットで充填されるように利用でき
る。例えば、図５において、遅延Ｘ１は隙間Ｖ１を横切
り、遅延Ｘ２は隙間Ｖ４を横切るが、一方で遅延Ｘ３は
隙間を横切らないし、現在時間４６から計算されたどの
遅延も隙間Ｖ２とＶ３を横切らない。したがって、図５
の遅延Ｘ１、Ｘ２およびＸ３に関して、新しいデータパ
ケット５０が現在時間４６に到着した時に、隙間Ｖ１と
Ｖ４だけがアドレス指定可能である。

【００３６】隙間充填／スケジューリングソフトウェア
のプログラム１００の含む隙間充填プログラム１１０
は、最初に新しい光データパケット５０が既存の隙間３
０の１つを充填するように新しい光データパケット５０
をスケジューリングしようと試みる。メモリは、バッフ
ァ２０の出力の隙間ごとに、隙間の開始時間、隙間の終
了時間および波長を含む。１つの実施形態では、隙間充
填プログラム１１０が、新しく到着したデータパケット
５０を最初に隙間Ｖ１に、次に隙間Ｖ３に、次に隙間Ｖ
４に、そして最後に隙間Ｖ２（すなわち、時間で一番古
いものから一番新しいものに下る順番で）に当てはめよ
うと試みるように動作する。言い換えれば、隙間充填プ
ログラム１１０は、現在時間に最も近い時間位置の隙間
に入れるように新しい光データパケット５０をスケジュ
ーリングしようと試みる。隙間の優先順位付けのこの選
択が唯一の可能性ではないことに留意する必要がある。
他の実施形態では、隙間充填／スケジューリングプログ
ラム１００は、第１の単一波長内の隙間を調べ、次に第
２の波長の全ての隙間を調べ、利用できる波長全部を通
して隙間を調べることができる。さらに別の実施形態で
は、隙間充填／スケジューリングプログラム１００は、
遅延線を最も短いものから最も長いものまで調べて特定
の遅延が隙間内に入るかどうか決定することができる。
新しいデータパケットを隙間内にきちんと当てはめるこ
とは、遅延された新しいパケットの始まりがその隙間の
占める時間位置内に当てはまるように十分長く新しいパ
ケットを現在時間４６から遅らせる遅延Ｘｉが存在しな
ければならないことを意味する。そのような遅延が見出
せたら、次に、利用できる遅延Ｘｉから測られる隙間の
長さの中に、パケットの長さが当てはまらなければなら
ない。

【００３７】動作において、図５の現在時間に等しい時
間に新しいデータパケットが到着した時に、隙間充填プ
ログラム１１０が、仮想待ち行列から隙間３０の時間位
置および持続時間を呼出す。これらの隙間位置を遅延線
と比較して、新しいデータパケットが到着した時に、ど
の隙間がアドレス指定可能であるかを決定する。隙間充
填プログラム１１０は、最初に新しい光データパケット
４０を隙間Ｖ１に当てはめようと試みる（現在時間４６
に最も近いので）。示されているように、現在時間４６
からの１番目の遅延Ｘ１は隙間Ｖ１内に入る。パケット
の始まりが隙間Ｖ１内に入るように十分にパケットを遅
らせる利用できる遅延（Ｘ１）があるので、この隙間Ｖ
１は、新しいデータパケット５０をスケジューリングで
きる可能なタイムスロットということになる。新しいデ
ータパケット５０の長さまたは持続時間が「現在時間＋
遅延Ｘ」と隙間Ｖ１の終わりの間の時間間隔に当てはま
れば、隙間充填プログラム１１０は新しいデータパケッ
ト５０を隙間Ｖ１に配置するだけである。言い換える
と、新しいデータパケット５０は、遅延Ｘ１から遅延線
の後の隙間Ｖ１に残っているスペースに当てはまらなけ
ればならない。したがって、たとえ１つの利用できる遅
延で新しいパケットを特定の隙間内に当てはめるように
十分に長く遅らせることができても、そのデータパケッ
トを特定の隙間に差し入れることができるかどうかは新
しいデータパケットのサイズに影響される。

【００３８】新しいデータパケット５０が、隙間Ｖ１の
利用できるスペースに当てはまると想定して、隙間充填
／スケジューリングソフトウェア１００が、Ｘ１の遅延
線を使用して新しいデータパケット５０を遅らせ、それ
を波長λ_１に差し入れることで、隙間Ｖ１内に新しいデ
ータパケット５０をスケジューリングする。隙間充填プ
ログラム１１０が、新しいデータパケット５０が光バッ
ファを発信する時間および新しいデータパケット５０が
発信する波長を決定する。我々の例では、波長はλ_１で
あり、発信する時間は現在時間に遅延Ｘ１を加えた時間
である。理解できるように、新しいデータパケット５０
による隙間Ｖ１の充填により、少なくとも１つ、多分に
２つの新しいギャップ４８と５２が生成される。これら
の新しいギャップ４８と５２を取り扱うためにいくつか
のオプションがある。すなわち、（１）隙間充填／スケ
ジューリングソフトウェアを使用して充填することがで
きる「新しい隙間」として両方を追跡するオプション、
（２）２つの中の１つを「新しい隙間」として取り扱う
オプション、または、（３）どれも新しい隙間と考えな
いで両方を無視するオプションである。１つの実施形態
では、隙間充填／スケジューリングソフトウェア１００
は、新しいデータパケット５０の前に生じるギャップ４
８を新しい隙間Ｖ１と考え、新しいデータパケット５０
の後に生じるギャップ５２を無視する。ギャップ５２
は、本質的には、どの光データパケットも使用しない損
失スペースになる。検査すべき隙間の数が増加するにつ
れて複雑さが増すので、このようにする。隙間充填プロ
グラム１１０は、仮想波長λ_１の隙間位置が、元の隙間
Ｖ２と新しい隙間Ｖ１’（ギャップ５２の位置の）を含
むように、直ちにメモリ３８を更新することができる。
次に新しいパケットが到着した時に、隙間Ｖ１”はＶ
２、Ｖ３、およびＶ４と共に考えられる。

【００３９】そうではなくて、新しいデータパケット５
０が、隙間Ｖ１の利用できるスペース内に当てはまらな
いとすれば、その時に隙間充填プログラム１１０は、パ
ケットを隙間Ｖ３に当てはめようと試みる。しかし、新
しいパケットを隙間Ｖ３に差し入れるような遅延が存在
しないので、プログラムは隙間Ｖ４に移る。プログラム
１１０は、同様の分析を行って、遅延Ｘ２で新しいデー
タパケット５０を隙間Ｖ４に差し入れるように十分に遅
らせることができるかどうかを決定する。次に、プログ
ラム１１０は、その隙間が隙間Ｖ４の利用できるスペー
ス（現在時間＋遅延Ｘ２と隙間Ｖ４の終わりの間）に当
てはまるかどうかを決定する。新しいデータパケット５
０が当てはまる場合には、次にそれを隙間Ｖ４にスケジ
ューリングする。新しいデータパケット５０が隙間Ｖ４
に当てはまらない場合には、隙間充填／スケジューリン
グソフトウェアの隙間充填部分は完了し、通常のスケジ
ューリングが始まる。

【００４０】隙間充填／スケジューリングソフトウェア
プログラム１００は、新しい光データパケット４０を既
存の隙間３０のどれかにスケジューリングすることがで
きなかった時に、通常のスケジューリング規則に基づい
て新しい光データパケット４０をスケジューリングする
ように従来のスケジューリングプログラム１２０も含む
ことができる。１つの実施形態では、従来のスケジュー
リングプログラム１２０は、最小の時間占有（持続時
間）を有する仮想波長フィールド４２を見出し、この仮
想波長フィールド４２に対して次の利用できる遅延で新
しいデータパケット５０をスケジューリングしようと試
みる。図５の例では、仮想波長フィールドλ_４が最小の
データパケットの占有率を有する（すなわち、他の仮想
波長フィールド４２は全て出力データパケットでより多
く占有されている）。図５に示されているように、波長
フィールドλ_４内の既存のデータパケット４０は、Ｘ１
の遅延を越え、さらにＸ２の遅延を越える長い時間を占
有している。したがって、新しいデータパケット５０を
Ｘ１またはＸ２だけ遅らせたとしても、波長λ_４の既存
のデータパケット４０との衝突が起き、データは失われ
るだろう。このような結果を避けるために、従来のスケ
ジューリングプログラム１２０は、新しいパケット５０
を波長λ_４でＸ３まで遅らせるようにスケジューリング
する。図５に示されているように、現在時間からＸ３時
間遅れて波長λ_４に新しいデータパケット５０を配置す
ることで、波長フィールドλ_４の現在のデータパケット
占有の終わりと現在時間＋Ｘ３の時間の新しいデータパ
ケット５０の始まりの間に「新しい隙間」６０が生成さ
れる。従来のスケジューリングプログラム１２０は、開
始時間（λ_４でのデータパケットの現在の長さ）、終了
時間（現在時間＋Ｘ３）および新しい隙間６０の波長
（λ_４）をメモリ３８に格納する。隙間充填／スケジュ
ーリングソフトウェアプログラム１００は、仮想波長λ
_４の隙間位置が新しい隙間６０を含むように今やメモリ
３８を更新することができる。次の新しいパケットが到
着した時に、新しい隙間６０を充填に利用することがで
きる。図５に図示した隙間充填プロセス全体は、光スイ
ッチの出力ポートごとに光データパケットを光バッファ
に入れる前に行われる。

【００４１】１つの実施形態では、複雑さの問題をなく
すために、隙間充填／スケジューリングソフトウェアプ
ログラム１００が、新しい隙間が生成される度に、既存
の隙間の分析を行うことができる。新しい隙間が生成さ
れ、数が所定の設定数を上回ると、隙間充填／スケジュ
ーリングソフトウェア１００が、隙間書換えプロセスを
行うことができ、その場合に、例えば、最も古い隙間が
捨てられ、新しい隙間が捨てられた隙間のメモリ位置を
占める。もしくは、新しい隙間が生成され、古い隙間が
消えた場合には（すなわち、時間において、現在時間が
過ぎた）、その時には、新しい隙間が消えた隙間のメモ
リ位置を取得する。動作において、隙間充填／スケジュ
ーリングソフトウェア１００は、所定の数まで全ての隙
間を維持し、その数に達すると直ちに、新しい隙間が最
も古い隙間のメモリ位置を取得し、最も古い隙間は失わ
れる。図５の例では、４つのメモリ位置があり、この４
つのメモリ位置を隙間Ｖ１、Ｖ２、Ｖ３およびＶ４が占
めているものとする。今、新しいデータパケット５０が
到着し、隙間Ｖ１または隙間Ｖ４に当てはまらないの
で、波長λ_４で現在時間にＸ３を加えた時間に位置決め
しなければならず、のように新しい隙間６０が生成され
ると仮定する。隙間メモリ位置の予め設定された数は４
つであるから、新しい隙間６０が生成された時に、隙間
充填／スケジューリングソフトウェア１００は、最初
に、隙間Ｖ１が占有する時間位置を現在時間が過ぎて、
隙間Ｖ１が消えてしまったかどうかを決定する。そうで
ある場合には、プログラム１００は、新しい隙間６０を
消えた隙間Ｖ１のメモリ位置に書込む。そうでない場合
には、プログラム１００は、隙間Ｖ１が占有したメモリ
位置を新しい隙間６０の情報で書き換える。したがっ
て、古い隙間Ｖ１はメモリから捨てられる。その結果と
して、隙間Ｖ１が占有したスペースは、もはや新しいデ
ータパケットを配置することができるスペースではなく
なる。隙間位置情報を格納するために利用できる無制限
のメモリ位置があれば、その時には、隙間充填ソフトウ
ェア１００は、隙間書換えサブプログラムを含む必要は
ない。これに反して、メモリが制限されていれば、隙間
充填ソフトウェアプログラム１００内に何らかの隙間書
換え方法を含まなければならない。ここで説明した隙間
書換え方法は、多くの隙間書換え方法の中の１つの例に
過ぎない。

【００４２】本発明の隙間充填／スケジューリングソフ
トウェアプログラム１００の１つの固有の特徴は、新し
い光データパケットが到着した時に、プログラムが、最
初に、以前に処理されたパケットの間に生成された隙間
を充填しようと試み、成功しない場合に、従来のスケジ
ューリングが採用されることである。本発明は、固定長
パケットトラヒック（ＡＴＭ、光パケット）と可変長パ
ケットトラヒック（ＩＰ、バースト）の両方のための縮
退したまたは縮退しないバッファと共に使用することが
できる。

【００４３】次の疑似コードは、隙間充填／スケジュー
リングソフトウェア１００の１つの実施形態の手法を記
述する。

【００４４】

【数１】示されているように、隙間充填／スケジューリング方法
は、オプションとして隙間充填／スケジューリングソフ
トウェア１００の一部であるいくつかの初期準備ステッ
プを含む。初期準備ステップは、光スイッチのそれぞれ
の出力ファイバの波長ごとに仮想波長フィールドを生成
すること、それぞれの新しい光データパケットが到着し
た時にそれを現在時間に割り当てること、およびその宛
先出力ファイバを決定することを含む。この点で、隙間
充填部が始まる。隙間充填プログラム１１０が、新しい
データパケットの宛先ファイバのそれぞれの隙間を、そ
の宛先ファイバの全波長と光バッファの遅延線のそれぞ
れの遅延にわたって調べる。新しく到着したデータパケ
ットごとに、それぞれの「現在時間」から遅延を測る。
示されているように、最小の遅延から最大の遅延に順番
に遅延を検査する。隙間充填プログラム１１０が、宛先
ファイバの隙間の時間位置内に入る遅延を見出す（すな
わち、測った遅延が隙間の開始より大きく隙間の終了よ
り小さい）時に、プログラム１１０は、新しいデータパ
ケットがその隙間に当てはまるかどうかを調べる。これ
は、新しいデータパケットの長さを遅延と隙間の終了の
間のスペースとを比較することで決定される。新しいパ
ケットが当てはまれば、新しいパケットをその隙間にス
ケジューリングする。当てはまらなければ、その時に
は、全ての遅延がなくなるまで、次の遅延を調べる。新
しいデータパケットが隙間内に当てはまれば、プログラ
ム１１０は、現在時間に遅延を加えた時間に等しい発信
時間と隙間の波長である発信波長に新しいデータパケッ
トを割り当てる。隙間充填プログラム１１０は、また、
新しい隙間の開始を、現在時間と遅延と新しいデータパ
ケットの長さとの和としてメモリに入れるように隙間書
換えサブルーチンを始動することができる。

【００４５】新しいデータパケットが、既存の隙間のど
れにも当てはまらない場合には、新しいデータパケット
をスケジューリングするために従来のスケジューリング
ルーチンを実行する。示されている実施形態では、従来
のスケジューリングプログラム１２０は、宛先ファイバ
の仮想波長フィールドのどれが最小使用スペースを有す
るかを決定し、新しいデータパケットをその波長フィー
ルドにスケジューリングする。その仮想波長フィールド
に対して、現在スケジューリングされたデータの長さと
波長が決定される。通常スケジューリングプログラム１
２０は、次に、使用された長さを遅延（再び、現在時間
から測れる）と比較して、波長フィールドに既にスケジ
ューリングされたデータパケットと衝突しないように十
分に新しいデータパケットを遅らせる遅延があるかどう
かを決定する。ない場合には、新しいデータパケットは
捨てられる。ある場合には、衝突を避ける最小の遅延ま
で新しいデータパケットを遅らせる。次に、従来のスケ
ジューリングプログラムが、新しいデータパケットをス
ケジューリングして、現在時間に使用された遅延を加え
た時間に等しい発信時間と最小の長さの波長である発信
波長とを得る。疑似コードに示された実施形態では、従
来のスケジューリングプログラム１２０は、新しく生成
された隙間（その波長における最後のパケットの終了と
新しいデータパケットの開始の間に）をメモリに格納す
る隙間書換えサブルーチンを含む。これは、既存のデー
タパケットの長さに等しい新しい隙間の開始、現在時間
と遅延の和に等しい新しい隙間の終了、および新しい隙
間の波長をメモリに記録することで行われる。

【００４６】図６Ａと図６Ｂは、ネットワーク利用率が
０．８である一様でタイムスロット形式のＡＴＭトラヒ
ックの下で、シミュレーション１６×１６同報通信選択
スイッチについて行われたシミュレーションのグラフで
ある。図６Ａの破線の曲線は、ファイバ当たりの波長の
数をパラメータとした縮退した場合についてのバッファ
深さに対する光データパケット損失の確率を表す。実線
の曲線は、遅延（１、２、３、．．．、Ｂ−１、２（Ｂ
−１））を有する縮退しないバッファを示す。図６Ａに
示されているように、シミュレーションは、縮退したバ
ッファに比べると、縮退しないバッファのパケット損失
の確率はかなり大きく減少することを示している。ファ
イバ当たり４波長のシナリオでは、６に等しい深さを有
する縮退しないバッファは、７に等しい深さの縮退した
バッファと同じ性能を有している。もっと大きな保持時
間を有するバッファのシミュレーションが行われ、その
結果が図６Ａに点線で示されている。また、図６Ａは、
縮退しないバッファの性能は、２つの制限の間に収まっ
ていることを示している。すなわち、３に等しい深さを
有する縮退しないバッファの性能は、３に等しい深さを
有する縮退したバッファと４に等しい深さを有する縮退
したバッファの間に収まる等である。

【００４７】図６Ｂは隙間充填のない場合に生じた余分
な利用を示す。図６Ｂの実線は、隙間を充填することの
成功の目安となる隙間充填の場合の余分な利用を示す。
遅延線の選択は、（１、２、３、．．．、Ｂ−１、２
（Ｂ−１）＋１）であり、最後の遅延線を前のシミュレ
ーションに対して１の増分で増やし、その結果、保持時
間をより大きくした。隙間充填係数（図４Ｂで点線によ
る余分な利用で表される）は劣っているが、バッファの
動作は僅かに優れている。このことは、その点を過ぎる
と隙間充填係数が劣化を始め性能に悪影響を与えるある
点まで、保持時間を長くすることでより優れた性能を達
成できることを示している。

【００４８】

【表１】表１は、一様なトラヒック条件およびバーストのトラヒ
ック条件（２、４、および２０のバースト程度）に関し
て、同じ深さ制限と遅延｛１、２、３、４｝を有する縮
退したバッファ、遅延｛１、２、３、６｝を有する縮退
しないバッファ、および同じ保持時間制限と遅延｛１、
２、３、４、５、６｝を有する縮退したバッファの間の
パケット損失の確率を比較して示す。トラヒックロード
は０．８であり、ファイバ当たり４波長が想定されてい
る。これらのバーストトラヒック条件の下で、縮退した
バッファに優る縮退しないバッファの利点をよりいっそ
うはっきりと理解することができる。表１に示されてい
るように、トラヒックのバースト程度が一様から２のバ
ースト程度に、４のバースト程度に、そして最後には２
０のバースト程度にと増すにつれて、縮退しないバッフ
ァの性能は、同じバッファ深さを有する縮退したバッフ
ァの性能よりもますますよくなってくる。実際に、縮退
しないバッファの性能は、同じ保持時間を有するがバッ
ファの深さがずっと大きな縮退したバッファの性能に漸
近的に近づく（例えば、バッファの深さ４の縮退しない
バッファは、バッファの深さ６の縮退したバッファと殆
ど同じ性能である）。

【００４９】図７は、本発明の隙間充填／スケジューリ
ングソフトウェア１００の利点を顕著に示している。図
７において、本発明の隙間充填／スケジューリングソフ
トウェア１００を組み込むバースト程度が４でトラヒッ
クロードが０．８の非同期可変長バーストトラヒックの
もとで動作する４×４の光スイッチのシミュレーション
を示す（本発明による隙間充填を使用しない同期および
非同期のトラヒックと比較する）。非同期と示された一
番上の線は、隙間充填をしない非同期動作の場合のバッ
ファの深さに対するパケット損失の結果であり、一方
で、同期と示された一番下の線は、隙間充填をしない同
期動作の場合のパケット損失の結果である。「非同期、
隙間充填」と示された中間の線は、本発明の隙間充填／
スケジューリングソフトウェアを利用する非同期動作を
示す。２つの非同期のグラフを比較する時に、隙間充填
により性能が著しく向上し、実際に性能が同期の性能の
方に近づいていることが明らかである。さらに、性能の
向上はバッファの深さが大きいほどより実質的なものに
なる。例えば、４のバッファの深さで、非同期パケット
損失は約０．７５であるが、非同期隙間充填動作のパケ
ット損失は約０．５であり、隙間充填動作の結果として
約０．２５（または、５０％）パケット損失が少なくな
るという向上となる。それと比べると、１６のバッファ
の深さでは、非同期パケット損失は約０．５であり、一
方で、非同期隙間充填動作のパケット損失は約０．００
５であり、隙間充填動作の結果として約０．４９５（ま
たは、９９％）パケット損失が少なくなるという向上と
なる。

【００５０】本発明は詳細に説明されたが、添付の特許
請求の範囲に記載されている本発明の精神と範囲から逸
脱することなしに、この点に関して様々な変化、置換、
および変更を行うことができることは理解されるべきで
ある。

【図面の簡単な説明】

【図１Ａ】縮退した光バッファを示す図である。

【図１Ｂ】縮退しない光バッファを示す図である。

【図２Ａ】従来の電気通信システムの一部を示す図であ
る。

【図２Ｂ】図２Ａと比較するために、従来の光通信シス
テムの一部を示す図である。

【図２Ｃ】本発明の実施形態を組み込む従来の光通信シ
ステムの一部を示す図である。

【図３Ａ】従来の縮退した光バッファの代表的な出力フ
ィールドを示す図である。

【図３Ｂ】従来の縮退した光バッファの代表的な出力フ
ィールドを示す図である。

【図３Ｃ】本発明の隙間充填／スケジューリングソフト
ウェアの実施形態の使用によって生じる縮退しない光バ
ッファの代表的な出力フィールドを示す図である。

【図４】本発明の実施形態を組み込む例示的な光スイッ
チを示す図である。

【図５】本発明の隙間充填／スケジューリングソフトウ
ェアの１つの実施形態の動作を示す図である。

【図６Ａ】縮退しない光バッファに対する縮退した光バ
ッファの性能の利点を図示するために、ネットワークロ
ードが０．８の一様な同期ＡＴＭトラヒックの下での１
６×１６光同報通信交換のシミュレーションのグラフを
示す図である。

【図６Ｂ】縮退しない光バッファに対する縮退した光バ
ッファの性能の利点を図示するために、ネットワークロ
ードが０．８の一様な同期ＡＴＭトラヒックの下での１
６×１６光同報通信交換のシミュレーションのグラフを
示す図である。

【図７】本発明の隙間充填動作の利点を図示するため
に、同期、非同期、および隙間充填のある非同期の条件
の下で動作する光バッファに関して、バッファの深さに
対するシミュレーションされたパケット損失のグラフを
示す図である。

【符号の説明】

１１光バッファの出力フィールド１２電気的スイッチ１３電気的スイッチの出力１４光バッファ、光スイッチ１５、１７時間間隔１６光スイッチの出力１８光ファイバ２０光バッファ２２、２４遅延線２５入力ファイバ２６トランスポート２８入力３０隙間３２出力３５出力ファイバ３６プロセッサ３８メモリ４０、５０データパケット４２仮想波長フィールド４８、５２ギャップ１００隙間充填／スケジューリングソフトウェアＥ１、Ｅ２電気的データパケット０１、０２、０３光データパケットＸ１、Ｘ２、Ｘ３遅延

Claims

【特許請求の範囲】

【請求項１】光スイッチの出力ファイバの光信号間の
隙間を充填するシステムであって、複数の波長を含む出力ファイバと、光信号に固有の遅延
を引き起こす複数の遅延線とを含む光バッファと、それぞれの出力ファイバの発信光信号間の隙間ごとの波
長、時間位置、および持続時間を含むメモリと、到着時間と持続時間を有する新しい光信号が到着した時
に、新しい光信号の到着時間から測られる遅延線ごとの利用
できる遅延を計算し、特定の利用できる遅延が特定の隙間の時間位置内に入
り、かつ特定の利用できる遅延から測った新しい光信号
の持続時間が特定の隙間の持続時間内に当てはまる場合
に、特定の隙間内に新しい光信号をスケジューリングす
る、プロセッサによって実行可能な隙間充填／スケジュ
ーリングソフトウェアプログラムとを含むシステム。
【請求項２】隙間充填／スケジューリングソフトウェ
アプログラムが、出力ファイバの複数の波長の数に等しい複数の仮想波長
をつくるためにさらに実行可能である請求項１に記載の
システム。
【請求項３】隙間充填／スケジューリングソフトウェ
アプログラムが、メモリの各隙間を検査し、最小の遅延から最大の遅延に順を追って各遅延を調べ、特定の隙間の時間位置内に入る最小の遅延を使用して新
しい光信号を遅延することで、新しい光信号をスケジュ
ーリングするために、さらに実行可能である請求項１に
記載のシステム。
【請求項４】隙間充填／スケジューリングソフトウェ
アプログラムが、現在時間から最も近い隙間から最も遠い隙間に順を追っ
て、メモリの各隙間を検査し、現在時間に最も近い時間位置の隙間に、新しい光信号を
スケジューリングしようと試みるために、さらに実行可
能である請求項１に記載のシステム。
【請求項５】隙間充填／スケジューリングソフトウェ
アプログラムが、新しい光信号ごとに到着時間を計算するために、さらに
実行可能である請求項１に記載のシステム。
【請求項６】隙間充填／スケジューリングソフトウェ
アプログラムが、新しい光信号の到着時間と特定の遅延との和に等しい発
信時間を新しい光信号に割り当て、特定の隙間の波長に等しい発信波長を新しい光信号に割
り当てるために、さらに実行可能である請求項１に記載
のシステム。
【請求項７】隙間充填／スケジューリングソフトウェ
アプログラムが、メモリに新しい隙間を格納するため
に、さらに実行可能であり、新しい隙間が、特定の隙間の波長に等しい波長、新しい
光信号の到着時間と特定の遅延との和に等しい開始時
間、および特定の隙間の終了時間に等しい終了時間を有
する、請求項６に記載のシステム。
【請求項８】隙間充填／スケジューリングソフトウェ
アプログラムが、新しい光信号を既存のどの隙間にもス
ケジューリングすることができない場合に、従来のスケジューリングルーチンを使用して新しい光信
号をスケジューリングするために、さらに実行可能であ
る請求項１に記載のシステム。
【請求項９】隙間充填／スケジューリングソフトウェ
アプログラムが、新しい光信号を隙間内にスケジューリングしようと試み
るために、実行可能な隙間充填プログラムと、隙間充填プログラムが、新しい光信号を隙間内にスケジ
ューリングすることに失敗した場合に、新しい光信号を
スケジューリングするために、実行可能な従来のスケジ
ューリングプログラムとをさらに含む請求項２に記載の
システム。
【請求項１０】従来のスケジューリングプログラム
が、最小の占有率を有する仮想波長を決定し、新しい光信号を、隙間で占有されていない最小の遅延
で、最小占有仮想波長にスケジューリングするために、
実行可能である請求項９に記載のシステム。
【請求項１１】従来のスケジューリングプログラム
が、新しい光信号のスケジューリングで生成された新し
い隙間をメモリに格納するために、さらに実行可能であ
り、新しい隙間が、最小の占有率の終了時間に等しい開始時
間、到着時間と最小の占有されていない遅延と新しい光
信号の長さとの和に等しい終了時間、および最小占有波
長に等しい波長を有する、請求項１０に記載のシステ
ム。
【請求項１２】書換えステップを行うステップが、隙
間充填／スケジューリングソフトウェアプログラムによ
って、メモリの所定の数の隙間メモリ位置を維持するステップ
と、所定の数の隙間メモリ位置の各々に、新しい隙間を入れ
るステップと、所定の数の隙間メモリ位置の全てが満たされたら、新し
い隙間が生成する時に、最も古い隙間メモリ位置をその
新しい隙間のデータの組で書換えるステップとで達成さ
れる請求項１１に記載のシステム。
【請求項１３】コンピュータ読取り可能媒体に格納さ
れた隙間充填／スケジューリングソフトウェアプログラ
ムを含むシステムであって、隙間充填／スケジューリングソフトウェアプログラム
が、到着時間と持続時間を有する新しい光データパケットが
複数の遅延線を有する光スイッチに到着した時に、現在時間を新しい光データパケットに割り当て、新しい光データパケットの宛先出力ファイバを決定し、出力ファイバの隙間内に入る現在時間から測った遅延位
置と、該遅延位置から始まるように位置決めされた新し
い光データパケットを収容する終了位置との両方を有す
る、前記隙間に、新しい光データパケットをスケジュー
リングするために、プロセッサによって実行可能である
システム。
【請求項１４】隙間充填／スケジューリングソフトウ
ェアプログラムが、出力ファイバの波長の数に等しい複
数の仮想波長をつくるために、さらに実行可能である請
求項１３に記載のシステム。
【請求項１５】隙間充填／スケジューリングソフトウ
ェアプログラムが、メモリの各隙間を検査し、最小の遅延から最大の遅延に順を追って各遅延線を調
べ、特定の隙間内に入る最小の遅延を使用して、新しい光デ
ータパケットをスケジューリングするために、さらに実
行可能である請求項１３に記載のシステム。
【請求項１６】隙間充填／スケジューリングソフトウ
ェアプログラムが、現在時間から時間位置を上昇してメ
モリの各隙間を検査し、現在時間に最も近い時間位置の隙間に新しい光データパ
ケットをスケジューリングするために、さらに実行可能
である請求項１３に記載のシステム。
【請求項１７】隙間充填／スケジューリングソフトウ
ェアプログラムが、新しい光データパケットの到着時間
を計算し、隙間内に入る遅延線を使用して新しい光デー
タパケットを遅らせることで、新しい光データパケット
をスケジューリングするために、さらに実行可能である
請求項１３に記載のシステム。
【請求項１８】隙間充填／スケジューリングソフトウ
ェアプログラムが、メモリ内に新しい隙間を格納するた
めに、実行可能であって、新しい隙間が、特定の隙間の波長に等しい波長、新しい
光データパケットの到着時間と特定の遅延との和に等し
い開始時間、および特定の隙間の終了時間に等しい終了
時間を有する、請求項１５に記載のシステム。
【請求項１９】隙間充填／スケジューリングソフトウ
ェアプログラムが、新しい光データパケットを隙間にス
ケジューリングできない場合に、従来のスケジューリングルーチンを使用して、新しい光
データパケットをスケジューリングするために、さらに
実行可能である請求項１３に記載のシステム。
【請求項２０】隙間充填／スケジューリングソフトウ
ェアプログラムが、新しい光データパケットを隙間内にスケジューリングし
ようと試みるために実行可能な隙間充填プログラムと、隙間充填プログラムが新しい光信号を隙間内にスケジュ
ーリングすることに失敗した場合に、新しい光信号をス
ケジューリングするために、実行可能な従来のスケジュ
ーリングプログラムとをさらに含む請求項１４に記載の
システム。
【請求項２１】従来のスケジューリングプログラム
が、最小占有率の仮想波長を決定し、既存の隙間で占有されていない最小の遅延で、最小占有
仮想波長に新しい光データパケットをスケジューリング
するために、実行可能である請求項２０に記載のシステ
ム。
【請求項２２】従来のスケジューリングプログラム
が、新しい光データパケットのスケジューリングで生成
された新しい隙間をメモリに格納するために、さらに実
行可能である請求項２１に記載のシステム。
【請求項２３】新しい隙間が、現在の占有に等しい開
始時間、到着時間と最小の占有されない遅延と新しい光
データパケットの長さとの和に等しい終了時間、および
最小占有波長に等しい波長を有する、請求項２２に記載
のシステム。
【請求項２４】隙間充填／スケジューリングソフトウ
ェアプログラムが、メモリに新しい隙間を格納するため
にメモリの所定の数の隙間メモリ位置を維持するステッ
プと、所定の数の隙間メモリ位置の各々に、新しい隙間を入れ
るステップと、所定の数の隙間メモリ位置の全てが満たされたら、新し
い隙間が生成した時に、最も古い隙間メモリ位置をその
新しい隙間のデータの組で書換えるステップとで、動作
可能である請求項２３に記載のシステム。
【請求項２５】既存の発信光データパケットの間に生
成された隙間を充填するために、多数の遅延線を備える
光バッファを有する光スイッチからの光データパケット
を出力ファイバにスケジューリングする方法であって、出力ファイバの各々の波長ごとに仮想波長フィールドを
生成するステップと、現在時間を新しい光データパケットに割り当てるステッ
プと、新しい光データパケットの宛先出力ファイバを決定する
ステップと、（ａ）現在時間から測られる光バッファ内の遅延線の遅
延位置を決定するステップ、（ｂ）宛先ファイバの仮想波長フィールドの各々にわた
って、宛先ファイバの既存の隙間の各々の位置を、決定
された遅延位置と比較するステップ、（ｃ）遅延位置が、既存の隙間位置内に入る場合で、か
つ遅延位置と新しい光データパケットの長さとの和が、
隙間の終了位置内に入る場合に、新しい光パケットを選
択された隙間にスケジューリングするステップ、およ
び、（ｄ）光バッファ内の遅延線ごとにステップ（ａ）〜
（ｃ）を繰返すステップ、を含む隙間充填動作を行うス
テップと、を含む光データパケットをスケジューリング
する方法。
【請求項２６】隙間充填動作を行うステップが、出力
ファイバの複数の波長の数に等しい複数の仮想波長をつ
くることをさらに含む請求項２５に記載の方法。
【請求項２７】隙間充填動作を行うステップが、現在時間に最も近い隙間から現在時間から最も遠い隙間
に順を追ってメモリの各隙間を検査するステップと、最小の遅延から最大の遅延に順を追って各遅延線を調べ
るステップと、隙間の時間位置内に入る最小の遅延か、現在時間に最も
近い時間位置の隙間内に入る最小の遅延かいずれかを使
用して新しい光データパケットをスケジューリングする
ステップとをさらに含む請求項２５に記載の方法。
【請求項２８】隙間充填動作を行うステップが、新し
いデータパケットが特定の隙間内にスケジューリングさ
れる場合に、新しい光データパケットの到着時間と特定の遅延との和
に等しい発信時間を新しい光データパケットに割り当て
るステップと、特定の隙間の波長に等しい発信波長を新しい光データパ
ケットに割り当てるステップとをさらに含む請求項２５
に記載の方法。
【請求項２９】隙間充填動作を行うステップが、メモ
リ内に新しい隙間を格納することをさらに含み、新しい隙間が、特定の隙間の波長に等しい波長、新しい
光データパケットの到着時間と特定の遅延との和に等し
い開始時間、および特定の隙間の終了時間に等しい終了
時間を有する、請求項２５に記載の方法。
【請求項３０】新しい光データパケットを既存のどの
隙間にもスケジューリングすることができない場合に、従来のスケジューリングルーチンを使用して、新しい光
データパケットをスケジューリングすることをさらに含
む請求項２５に記載の方法。
【請求項３１】従来のスケジューリングルーチンを使
用するスケジューリングのステップが、最小占有率の仮想波長を決定することと、既存の隙間で占有されていない最小の遅延で、最小占有
仮想波長に新しい光データパケットをスケジューリング
することとを含む請求項３０に記載の方法。
【請求項３２】既存の発信光データパケットの間に生
成された隙間を充填するために、多数の遅延線を備える
光バッファを有する光スイッチからの光データパケット
を出力ファイバにスケジューリングする方法であって、出力ファイバの各々の波長ごとに仮想波長フィールドを
生成するステップと、現在時間を新しい光データパケットに割り当てるステッ
プと、新しい光データパケットの宛先出力ファイバを決定する
ステップと、隙間内に入る遅延位置と、該遅延位置から始まるように
位置決めされた新しい光データパケットを収容する終了
位置との両方を有する、前記隙間に新しい光データパケ
ットをスケジューリングするステップとを含み、遅延位置が、現在時間から測られる特定の遅延線に関連
付けられた位置である、光データパケットをスケジュー
リングする方法。
【請求項３３】スケジューリングが、出力ファイバの
複数の波長の数に等しい複数の仮想波長をつくることを
さらに含む請求項３２に記載の方法。
【請求項３４】スケジューリングが、新しい光データパケットの到着時間を計算するステップ
と、メモリの各隙間を検査するステップと、最小の遅延から最大の遅延に順を追って各遅延線を調べ
るステップと、隙間の時間位置内に入る最小の遅延を使用して、新しい
光データパケットをスケジューリングしようと試みるス
テップとをさらに含む請求項３２に記載の方法。
【請求項３５】スケジューリングが、新しいデータパ
ケットを特定の隙間内にスケジューリングする場合に、新しい光データパケットの到着時間と特定の遅延との和
に等しい発信時間を新しい光データパケットに割り当て
るステップと、特定の隙間の波長に等しい残すべき波長を新しい光デー
タパケットに割り当てるステップとをさらに含む請求項
３２に記載の方法。
【請求項３６】スケジューリングが、メモリ内に新し
い隙間を格納することをさらに含み、新しい隙間が、特定の隙間の波長に等しい波長、新しい
光データパケットの到着時間と特定の遅延との和に等し
い開始時間、および特定の隙間の終了時間に等しい終了
時間を有する、請求項３２に記載の方法。
【請求項３７】新しい光データパケットを既存のどの
隙間にもスケジューリングすることができない場合に、従来のスケジューリングルーチンを使用して、新しい光
データパケットをスケジューリングすることをさらに含
む請求項３６に記載の方法。
【請求項３８】スケジューリングが、最小占有率の仮想波長を決定することと、既存の隙間で占有されていない最小の遅延で、最小占有
仮想波長に新しい光データパケットをスケジューリング
することとをさらに含む請求項３７に記載の方法。
【請求項３９】スケジューリングが、新しい光データ
パケットのスケジューリングで生成された新しい隙間を
メモリに格納することをさらに含み、新しい隙間が、現在の占有に等しい開始時間、到着時間
と最小の占有されない遅延と新しい光データパケットの
長さとの和に等しい終了時間、および最小占有波長に等
しい波長を有する、請求項３８に記載の方法。
【請求項４０】新しい隙間をメモリ内に格納するため
に、隙間書換えステップを行うことをさらに含む請求項
３９に記載の方法。
【請求項４１】書換えステップを行うステップが、メモリの所定の数の隙間メモリ位置を維持するステップ
と、所定の数の隙間メモリ位置の各々に、新しい隙間を入れ
るステップと、所定の数の隙間メモリ位置の全てが満たされたら、新し
い隙間が生成した時に、最も古い隙間メモリ位置をその
新しい隙間のデータの組で書換えるステップとをさらに
含む請求項４０に記載の方法。
【請求項４２】既存の発信光データパケットの間に生
成された隙間を充填するために、多数の遅延線を備える
光バッファを有する光スイッチからの光データパケット
を出力ファイバにスケジューリングする方法であって、前記方法が、コンピュータ読取り可能媒体に格納された
隙間充填コンピュータプログラムで行われ、隙間充填コンピュータプログラムが、出力ファイバの各々の波長ごとに、仮想波長フィールド
を生成し、現在時間を新しい光データパケットに割り当て、新しい光データパケットの宛先出力ファイバを決定し、隙間内に入る遅延位置と、該遅延位置から始まるように
位置決めされた新しい光データパケットを収容する終了
位置との両方を有する、前記隙間に出力すべき新しい光
データパケットをスケジューリングするために、実行可
能であり、遅延位置が、現在時間から測られる特定の遅延線を使用
して決定された時間位置である光データパケットをスケ
ジューリングする方法。
【請求項４３】隙間充填コンピュータプログラムが、特定の宛先ファイバに関連付けられたそれぞれの仮想波
長フィールドの各隙間を検査し、新しい光データパケットの到着時間を計算し、メモリの各隙間を検査し、最小の遅延から最大の遅延に順を追って各遅延線を調
べ、隙間の時間位置内に入る最小の遅延を使用して、新しい
光データパケットをスケジューリングしようと試みるた
めに、さらに実行可能である請求項４２に記載の方法。
【請求項４４】隙間充填コンピュータプログラムが、新しい光データパケットの到着時間と特定の遅延との和
に等しい発信時間を新しい光データパケットに割り当
て、特定の隙間の波長に等しい発信波長を新しい光データパ
ケットに割り当てるために、さらに実行可能である請求
項４２に記載の方法。
【請求項４５】新しい光データパケットを既存のどの
隙間にもスケジューリングすることができない場合に、隙間充填／スケジューリングプログラム内の従来のスケ
ジューリングルーチンを使用して、新しい光データパケ
ットをスケジューリングすることをさらに含む請求項４
２に記載の方法。
【請求項４６】隙間充填／スケジューリングプログラ
ムが、新しい光データパケットのスケジューリングで生
成された新しい隙間をメモリに格納するためにさらに実
行可能である請求項４５に記載の方法。
【請求項４７】隙間充填／スケジューリングプログラ
ムが、新しい隙間をメモリ内に格納するために隙間書換
えステップを行うために、さらに動作可能である請求項
４６に記載の方法。