(57)【特許請求の範囲】
【請求項１】
データユニットを先入れ先出しするバッファメモリと、
カウンタ値を保持し、所定の規則に基づいて該カウンタ値に値を加えるとともに、前記バッファメモリからデータユニットを出力する場合に該カウンタ値から該先頭のデータユニットのサイズ分を減ずるカウンタ管理部と、
前記バッファメモリに保持されているデータユニットの合計サイズが所定のバッファ閾値よりも小さいという第１条件を満たす場合には、前記カウンタ値が前記バッファメモリの先頭のデータユニットのサイズよりも大きいという第２条件を満たすとともに前記カウンタ値が所定のカウンタ閾値よりも大きい場合に、前記バッファメモリの先頭のデータユニットを出力するとともに、前記第１条件を満たさない場合には、所定の第３条件を満たすまで、前記バッファメモリに保持されているデータユニットを先頭から順次出力する制御部と、
を備える帯域制御装置。
【請求項２】
前記第３条件は、前記第１条件を満たすか、あるいは、前記第２条件を満たさないことである
請求項１記載の帯域制御装置。
【請求項３】
前記バッファメモリは、ｎ個（ｎは２以上の整数）のバッファ閾値Ｑｔｈ（１），Ｑｔｈ（２），・・・，Ｑｔｈ（ｎ）を有し、前記ｎ個のバッファ閾値Ｑｔｈ（ｉ）（０＜ｉ≦ｎ）は、０から前記バッファメモリのサイズ未満の間で、ｉの昇順の値をとり、
前記カウンタ管理部は、ｎ個のカウンタ閾値Ｔｔｈ（１），Ｔｔｈ（２），・・・，Ｔｔｈ（ｎ）を有し、前記ｎ個のカウンタ閾値Ｔｔｈ（ｉ）は、０から前記カウンタ値の最大値以下の間で、ｉの降順の値をとり、
前記制御部は、前記バッファメモリに保持されているデータユニットの合計サイズがＱｔｈ（ｉ−１）以上Ｑｔｈ（ｉ）未満の場合に、前記カウンタ値がＴｔｈ（ｉ）未満になるまで、又は、前記バッファメモリに保持されているデータユニットの合計サイズがＱｔｈ（ｉ−１）未満になるまで、又は、前記カウンタ値が前記バッファメモリの先頭のデータユニットのサイズ未満になるまで、前記バッファメモリに保持されているデータユニットを先頭から順次出力し、前記バッファメモリに保持されているデータユニットの合計サイズがＱｔｈ（ｎ）以上の場合に、前記バッファメモリに保持されているデータユニットの合計サイズがＱｔｈ（ｎ）未満になるまで、又は、前記カウンタ値が前記バッファメモリの先頭のデータユニットのサイズ未満になるまで、前記バッファメモリからデータユニットを出力する
請求項１に記載の帯域制御装置。
【請求項４】
前記バッファメモリは、第１のレート制御閾値と、前記第１のレート制御閾値よりも大きい第２のレート制御閾値とを有し、
前記制御部は、前記バッファメモリに保持されているデータユニットの合計サイズが前記第１のレート制御閾値以上に変化した場合には、前記カウンタ値に値を加えるレートを所定のシェーピングレートを下回るレートに変更し、前記バッファメモリに保持されているデータユニットの合計サイズが前記第２のレート制御閾値以上に変化した場合、及び、前記第１のレート制御閾値未満に変化した場合には、前記カウンタ値に値を加えるレートを前記所定のシェーピングレートに変更する
請求項１から３のいずれか１項に記載の帯域制御装置。
【請求項５】
前記制御部は、前記バッファメモリからデータユニットが出力されたことによって、前記バッファメモリに保持されているデータユニットの合計サイズが前記第１のレート制御閾値より小さくなった場合には、前記カウンタ値の値を加えるレートを前記所定のシェー
ピングレートに変更する
請求項４に記載の帯域制御装置。
【請求項６】
所定の規則に基づいて保持するカウンタ値に値を加え、
データユニットを先入れ先出しするバッファメモリからデータユニットが出力される場合に該カウンタ値から該先頭のデータユニットのサイズ分を減じ、
前記バッファメモリに保持されているデータユニットの合計サイズが所定のバッファ閾値よりも小さいという第１条件を満たす場合には、前記カウンタ値が前記バッファメモリの先頭のデータユニットのサイズよりも大きいという第２条件を満たすとともに前記カウンタ値が所定のカウンタ閾値よりも大きい場合に、前記バッファメモリの先頭のデータユニットを出力するとともに、前記第１条件を満たさない場合には、所定の第３条件を満たすまで、前記バッファメモリに保持されているデータユニットを先頭から順次出力する
帯域制御方法。
【請求項７】
コンピュータに、
所定の規則に基づいて保持するカウンタ値に値を加えさせ、
データユニットを先入れ先出しするバッファメモリからデータユニットが出力される場合に該カウンタ値から該先頭のデータユニットのサイズ分を減じさせ、
前記バッファメモリに保持されているデータユニットの合計サイズが所定のバッファ閾値よりも小さいという第１条件を満たす場合には、前記カウンタ値が前記バッファメモリの先頭のデータユニットのサイズよりも大きいという第２条件を満たすとともに前記カウンタ値が所定のカウンタ閾値よりも大きい場合に、前記バッファメモリの先頭のデータユニットを出力するとともに、前記第１条件を満たさない場合には、所定の第３条件を満たすまで、前記バッファメモリに保持されているデータユニットを先頭から順次出力させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークの帯域を制御する帯域制御装置に関する。
【背景技術】
【０００２】
ＴＣＰ（Transmission Control Protocol）のようにコネクション型プロトコルでは、
送信したデータに対して確認応答（以下、Ａｃｋ）を返すものがある。データを送信してから該データに対するＡｃｋが返ってくるまでの時間は、例えば、ＴＣＰでは、ＲＴＴ（Round Trip Time）と呼ばれる。ＲＴＴが大きくなると、スループットは低下し、遅延が
発生する。遅延の要因として、送受信装置間の物理的な距離，送受信装置間の経由ノード数，及び、輻輳などに伴うバッファリングなどが考えられる。
【０００３】
図１３Ａ及び図１３Ｂは、バッファリングによる遅延について説明するための図である。図１３Ａ及び図１３Ｂでは、送受信装置間で１本のＴＣＰセッションにより通信が行われている例が示される。
【０００４】
図１３Ａでは、送信側装置のウィンドウサイズは１２８ｋｂｉｔであるとする。また、ＲＴＴは平均０．１秒であるとする。図１３Ａにおいて、送信側装置の平均的なスループット（すなわち、送信側装置の平均出力レート）は、以下の式により導き出される。
平均スループット＝１２８ｋｂｉｔ／０．１ｓ＝１．２８Ｍｂｐｓ
【０００５】
図１３Ｂでは、図１３Ａに示される送受信装置間に１Ｍｂｐｓのシェーピングレートのシェーパを有する中継装置が存在する例が示される。図１３Ｂに示される例では、中継装置において、入力レートが１．２８Ｍｂｐｓであるのに対して、出力レートがシェーピングレートの１Ｍｂｐｓに絞られるため、中継装置のバッファにおいてキューが形成される。これによって、シェーパが存在しない図１３Ａに示される例では発生しなかったバッファリング遅延が、例えば、以下のようにして、発生することになる。
【０００６】
（１）例えば、パケット長が１５１８ｂｙｔｅであるとする。中継装置のバッファに平均的に２個のパケットが蓄積された状態になると、バッファリングによる遅延が約０．０２４秒（１５１８×８×２ｂｉｔ／１Ｍｂｉｔ）増加する。
【０００７】
（２）中継装置において、約０．０２４秒の遅延が増加するので、ＲＴＴも０．０２４秒増加し、０．１２４秒（０．１秒＋０．０２４秒）となる。
【０００８】
（３）送信側装置において、ＲＴＴが増加することは、Ａｃｋが返ってくるまでの時間が長くなることであるので、送信側装置が、あるパケットを送信してから該パケットに対するＡｃｋを受信し、次のパケットを送信するまでの間隔が長くなる。すなわち、ＲＴＴが増加したことによって、送信側装置の平均スループットが低下する。図１３Ｂにおける例においては、以下の式によって導き出されるように、送信側装置の平均スループットは約１Ｍｂｐｓに低下する。
平均スループット＝１２８ｋｂｉｔ／０．１２４ｓ≒１Ｍｂｐｓ
【０００９】
送信側装置のスループットが約１Ｍｂｐｓに低下することによって、図１３Ｂに示される例では、中継装置の入力レートも約１Ｍｂｐｓに低下する。中継装置において、入力レートが出力レートまで低下し、入力レートと出力レートが等しくなる。
【００１０】
図１３Ｂに示される例のように、ＴＣＰのようなウィンドウフロー制御が行われるネッ
トワークにおいては、中継装置において出力レートより入力レートが大きい場合でも、キューの形成による遅延の増加によって、入力レートが低下する場合がある。図１３Ｂに示される例のように、中継装置において、入力レートと出力レートが等しくなる状態は、以降、平衡状態と呼ばれる。
【００１１】
なお、平衡状態は、図１３Ａ及び図１３Ｂのような、ＴＣＰのウィンドウフロー制御に限られた現象ではなく、確認応答を行うコネクション型のプロトコルであれば発生しうる現象である。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開平９−２４７２１３号公報
【特許文献２】特開２００８−７８９３２号公報
【発明の概要】
【発明が解決しようとする課題】
【００１３】
図１３Ｂに示されるような平衡状態において、送受信装置間に大量のデータを送信する別のフローが発生したと仮定すると、中継装置においてバッファがあふれてしまい、そののち中継装置に到着するパケットが廃棄される場合がある。ネットワークにおいて突発的に大量のデータが送信又は受信されることは、バーストと呼ばれる。
【００１４】
ＴＣＰの通信において、パケット損失が発生すると、ＴＣＰの再送制御により、パケットの再送が行われる。このパケットの再送により、ネットワークに輻輳が発生している場合には、輻輳状態を悪化させてしまう可能性がある。すなわち、中継装置におけるパケット廃棄は、輻輳状態の悪化の要因となる。
【００１５】
本発明の一態様は、平衡状態においてパケットの廃棄を低減する帯域制御装置を提供することを目的とする。
【課題を解決するための手段】
【００１６】
本発明の態様の一つは、帯域制御装置である。この帯域制御装置は、
データユニットを先入れ先出しするバッファメモリと、
カウンタ値を保持し、所定の規則に基づいて該カウンタ値に値を加えるとともに、前記バッファメモリからデータユニットを出力する場合に該カウンタ値から該先頭のデータユニットのサイズ分を減ずるカウンタ管理部と、
前記バッファメモリに保持されているデータユニットの合計サイズが所定のバッファ閾値よりも小さいという第１条件を満たす場合には、前記カウンタ値が前記バッファメモリの先頭のデータユニットのサイズよりも大きいという第２条件を満たすとともに前記カウンタ値が所定のカウンタ閾値よりも大きい場合に、前記バッファメモリの先頭のデータユニットを出力するとともに、前記第１条件を満たさない場合には、所定の第３条件を満たすまで、前記バッファメモリに保持されているデータユニットを先頭から順次出力する制御部と、
を備える。
【００１７】
本発明の他の態様の一つは、上述した帯域制御方法である。また、本発明の他の態様は、コンピュータを情報処理装置として機能させるプログラム、及び当該プログラムを記録したコンピュータ読み取り可能な記録媒体を含むことができる。
【発明の効果】
【００１８】
開示の中継装置によれば、平衡状態においてパケットの廃棄を低減することができる。
【図面の簡単な説明】
【００１９】
【図１】中継装置のハードウェア構成例を示す図である。
【図２】インターフェースカードの構成例を示す図である。
【図３】シェーパの構成例を示す図である。
【図４】トークンバケットにトークンが供給された際のパケット読出し処理のフローの例が示される。
【図５】シェーパにパケットが到着した場合のパケット読出し処理のフローの例を示す図である。
【図６Ａ】シェーパの平衡状態において、別のバーストトラヒックが到着した例を説明するための図である。
【図６Ｂ】シェーパの平衡状態において、別のバーストトラヒックが到着した例を説明するための図である。
【図６Ｃ】シェーパの平衡状態において、別のバーストトラヒックが到着した例を説明するための図である。
【図６Ｄ】シェーパの平衡状態において、別のバーストトラヒックが到着した例を説明するための図である。
【図６Ｅ】シェーパの平衡状態において、別のバーストトラヒックが到着した例を説明するための図である。
【図７】シェーパの構成例を示す図である。
【図８】トークン供給時のパケット読出し処理のフローの例を示す図である。
【図９】パケット到着時のパケット読出し処理のフローの例を示す図である。
【図１０】シェーパの構成例を示す図である。
【図１１】シェーパにパケットが到着した場合の、パケット読出し処理とトークン供給レート決定処理とのフローの例を示す図である。
【図１２】シェーパからのパケット読出し終了後のトークン供給レート決定処理のフローの例を示す図である。
【図１３Ａ】バッファリングによる遅延について説明するための図である。
【図１３Ｂ】バッファリングによる遅延について説明するための図である。
【図１４】トークンバケット型シェーパの構成例を示す図である。
【図１５】トークンがトークンバケットに供給された場合の読出し処理のフローの例を示す図である。
【図１６】バッファメモリにパケットが到着した際の、パケット読出し処理のフローの例を示す図である。
【図１７】トークンバケット型シェーパを用いた場合のトークン残量とパケットの到着及び送出との関係が時系列で示された例を示す図である。
【図１８Ａ】トークンバケット型シェーパの平衡状態において、別のバーストトラヒックが到着した例を説明するための図である。
【図１８Ｂ】トークンバケット型シェーパの平衡状態において、別のバーストトラヒックが到着した例を説明するための図である。
【図１８Ｃ】トークンバケット型シェーパの平衡状態において、別のバーストトラヒックが到着した例を説明するための図である。
【図１８Ｄ】トークンバケット型シェーパの平衡状態において、別のバーストトラヒックが到着した例を説明するための図である。
【図１８Ｅ】トークンバケット型シェーパの平衡状態において、別のバーストトラヒックが到着した例を説明するための図である。
【発明を実施するための形態】
【００２０】
以下、図面に基づいて、本発明の実施の形態を説明する。以下の実施形態の構成は例示であり、本発明は実施形態の構成に限定されない。
【００２１】
＜トークンバケット型シェーパ＞
図１４は、トークンバケット型シェーパの構成例を示す図である。シェーパＰ１は、出力レートを平均的にシェーピングレートにすることによって、ネットワークの帯域制御を行う帯域制御装置である。トークンバケット型シェーパＰ１は、トークン供給部Ｐ１３，トークンバケットＰ１４，バッファメモリＰ１６，及び読出し制御部Ｐ１５を含む。
【００２２】
トークン供給部Ｐ１３は、周期的にトークンバケットＰ１４に送信権であるトークンを供給する。トークン供給部Ｐ１３は、周期的にトークンバケットＰ１４にトークンを供給することに加え、パケット到着時にもトークンバケットＰ１４にトークンを供給してもよい。トークンは、送信が許可されるパケットのデータサイズを決定する送信権である。例えば、送信が許可されるパケットのデータサイズがトークン１つ当たりにバイト単位で予め決められており、１回に供給されるトークンの数も予め決められている。１つ又はそれ以上のトークンによって送信が許可されるパケットのデータサイズは、以降、トークン量と呼ばれる。トークン供給部Ｐ１３が１回に供給するトークン量と供給する周期は予め決められている。所定時間内に供給されるトークン量（トークン供給レート）は、シェーパＰ１のシェーピングレートと同じである。
【００２３】
トークンバケットＰ１４は、トークン供給部Ｐ１３から供給されるトークンを保持する。シェーパＰ１は、トークンバケットＰ１４に保持されるトークン量だけバッファメモリＰ１６からパケットを読み出すことができる。バッファメモリＰ１６からパケットが読み出されると、読み出されたパケットのサイズに相当するトークン量だけトークンバケットからトークンが減じられる。また、トークンバケットＰ１４にトークンがない場合には、シェーパＰ１はバッファメモリＰ１６からパケット読み出すことができない。トークンバケットＰ１４には、バケットサイズとしてトークンを保持できる最大値が設定されている。以降、トークンバケットに保持されるトークン量は、トークン残量とも呼ばれる。トークン残量は、Ｔｌｅｎで表わされる。トークンバケットのバケットサイズはＴｍａｘで表わされる。
【００２４】
バッファメモリＰ１６には、シェーパＰ１に到着した順番でパケットが一時的に格納される。バッファメモリＰ１６に保持されるパケットは、読み出される順番の待ち行列であるキューを形成する。バッファメモリＰ１６に保持されるパケットの合計サイズはキュー長とも呼ばれる。また、バッファメモリＰ１６には、バッファサイズとしてパケットを保持できる最大値、すなわち、キュー長の最大値が設定されている。キュー長はＱｌｅｎで表わされる。バッファメモリのバッファサイズ（キュー長の最大値）はＱｍａｘで表わされる。
【００２５】
読出し制御部Ｐ１５は、トークンバケットＰ１４のトークン残量に応じて、バッファメモリＰ１６に保持されるパケットを読み出す。読出し制御部Ｐ１５は、トークン残量Ｔｌｅｎの分だけバッファメモリＰ１６からパケットを読み出すことができる。読出し制御部Ｐ１５は、バッファメモリＰ１６からパケットを読み出すと、読み出されたパケットのサイズに相当するトークンをトークンバケットＰ１４から減らす。すなわち、読出し制御部Ｐ１５は、トークンバケットＰ１４に保持されるトークンを使って（消費して）、バッファメモリＰ１６からパケットを読み出す。
【００２６】
図１５は、トークンがトークンバケットＰ１４に供給された場合のパケット読出し処理のフローの例を示す図である。
【００２７】
例えば、トークンの供給周期によって、トークン供給部Ｐ１３からトークンバケットＰ１４にトークンが供給されると処理が開始する。トークン供給部Ｐ１３からトークンバケ
ットＰ１４に供給される一回当たりのトークン量をｃとする。
【００２８】
トークン残量Ｔｌｅｎと供給されたトークン量ｃとの和がトークンバケットＰ１４のバケットサイズＴｍａｘ以下である場合には（ＯＰ１０１：Ｙｅｓ）、トークン残量Ｔｌｅｎは、トークン残量Ｔｌｅｎと供給されたトークン量ｃとの和に更新される（ＯＰ１０２）。
【００２９】
トークン残量Ｔｌｅｎと加算されたトークン量ｃとの和がトークンバケットＰ１４のサイズＴｍａｘより大きい場合には（ＯＰ１０１：Ｎｏ）、トークン残量ＴｌｅｎはトークンバケットＰ１４のバケットサイズＴｍａｘになる（ＯＰ１０３）。
【００３０】
読出し制御部Ｐ１５は、バッファメモリＰ１６にパケットが保持されているか否か、すなわち、バッファメモリＰ１６にキューが形成されているか否かを判定する。さらに、読出し制御部Ｐ１５は、トークン残量Ｔｌｅｎがキューの先頭パケットのサイズｂ以上か否かを判定する（ＯＰ１０４）。
【００３１】
バッファメモリＰ１６にキューが形成されており、且つ、トークン残量Ｔｌｅｎがキューの先頭パケットのサイズｂ以上の場合には（ＯＰ１０４：Ｙｅｓ）、読出し制御部Ｐ１５は、キューの先頭パケットを読み出す（ＯＰ１０５）。読出し制御部Ｐ１５は、トークンバケットＰ１４から読み出された先頭パケットのサイズｂに相当するトークンを減らす。トークン残量Ｔｌｅｎは、バッファメモリＰ１６から読み出された先頭パケットのサイズｂが減算された値になる。キュー長Ｑｌｅｎは、読み出された先頭パケットのサイズｂが減算された値になる。その後、処理がＯＰ１０４に戻り、ＯＰ１０４の条件が満たされる間、バッファメモリＰ１６からパケットが読み出される。
【００３２】
バッファメモリＰ１６にキューが形成されていない場合、又は、トークン残量Ｔｌｅｎがキューの先頭パケットのサイズｂより小さい場合のいずれかの場合には（ＯＰ１０４：Ｎｏ）、バッファメモリＰ１６からパケットは読み出されず、処理が終了する。
【００３３】
図１６は、シェーパＰ１にパケットが到着した際の、パケット読出し処理のフローの例を示す図である。バッファメモリＰ１６にパケットが到着すると処理が開始される。バッファメモリＰ１６に到着したパケットのサイズはａで表わされる。
【００３４】
キュー長Ｑｌｅｎと到着したパケットのサイズａとの和がバッファサイズＱｍａｘより大きい場合には（ＯＰ１１１：Ｎｏ）、バッファあふれの状態であることが示されるので、到着したパケットは廃棄される（ＯＰ１１５）。
【００３５】
キュー長Ｑｌｅｎと到着パケットのサイズａとの和がバッファサイズＱｍａｘ以下である場合には（ＯＰ１１１：Ｙｅｓ）、到着したパケットはバッファメモリＰ１６にバッファされる。キュー長Ｑｌｅｎは、到着したパケットのサイズａが加算された値になる（ＯＰ１１２）。
【００３６】
読出し制御部Ｐ１５は、バッファメモリＰ１６にパケットが保持されているか否か、すなわち、バッファメモリＰ１６にキューが形成されているか否かを判定する。さらに、読出し制御部Ｐ１５は、トークン残量Ｔｌｅｎがキューの先頭パケットのサイズｂ以上か否かを判定する（ＯＰ１１３）。
【００３７】
バッファメモリＰ１６にキューが形成されており、且つ、トークン残量Ｔｌｅｎがキューの先頭パケットのサイズｂ以上の場合には（ＯＰ１１３：Ｙｅｓ）、読出し制御部Ｐ１５は、キューの先頭パケットを読み出す（ＯＰ１１４）。読出し制御部Ｐ１５は、トーク
ンバケットＰ１４から読み出された先頭パケットのサイズｂに相当するトークンを減らす。トークン残量Ｔｌｅｎは、バッファメモリＰ１６から読み出された先頭パケットのサイズｂが減算された値になる。また、キュー長Ｑｌｅｎは、読み出された先頭パケットのサイズｂが減算された値になる。その後、処理がＯＰ１１３に戻り、ＯＰ１１３の条件が満たされる間、ＯＰ１１４の処理が繰り返され、バッファメモリＰ１６からパケットが読み出される。バッファメモリ１６に到着パケットしか保持されていない場合には、先頭パケット＝到着パケットとなり、到着パケットが読み出され、トークン残量Ｔｌｅｎから到着パケットのサイズａが減じられる。
【００３８】
バッファメモリＰ１６にキューが形成されていない場合、又は、トークン残量Ｔｌｅｎがキューの先頭パケットのサイズｂより小さい場合のいずれかの場合には（ＯＰ１１３：Ｎｏ）、バッファメモリＰ１６からパケットは読み出されず、処理が終了する。
【００３９】
図１５及び図１６に示されるように、トークンバケット型シェーパＰ１では、バッファメモリに保持されるパケットがなくなるまで、又は、トークンが枯渇するまでパケットが読み出される。
【００４０】
図１７は、トークンバケット型シェーパを用いた場合のトークン残量とパケットの到着及び送出との関係が時系列で示された例を示す図である。図１７に示されるグラフでは、横軸が時間、縦軸がトークンバケットのトークン残量を示す。図１７において、初期状態では、トークンバケットは空の状態であるとする。また、バッファメモリには、パケットが保持されていないとする。また、説明の簡略化のために、シェーパに到着するパケットのサイズはすべてａと想定する。
【００４１】
初期状態からトークンバケットにパケットサイズａだけのトークンが蓄積されるまでの間にパケットが到着した場合には、トークンバケットにパケットサイズａ以上のトークンが蓄積されるまで、到着パケットはバッファメモリに保持される。トークンが蓄積され、トークン残量がパケットサイズａ以上になると、バッファメモリの先頭パケットが読み出される。トークン残量から読み出されたパケットのサイズａが減じられ、トークン残量は、再び初期状態に戻る。次にパケットが到着した場合にも同様にして、トークン残量が到着パケットのサイズａ以上になるまではパケットは読み出されず、トークン残量が到着パケットのサイズａ以上になってからパケットが読み出される。このようにして、トークンバケットが空の状態でパケットが到着すると、トークンバケットでは、初期状態、初期状態からトークンが到着パケットのサイズａだけ蓄積されるまでの過渡状態、及びトークンが到着パケットのサイズａだけ蓄積された状態が繰り返される。初期状態，トークンが到着パケットのサイズａだけ蓄積されるまでの過渡状態，及びトークンが到着パケットのサイズａだけ蓄積された状態が繰り返される間は、シェーパからはトークン供給レート、すなわちシェーピングレートでパケットが読み出されることとなる。
【００４２】
しばらくの間パケットが到着せず、バッファメモリにもパケットが保持されていない状態が続くと、トークンバケットに定期的にトークンが供給されて蓄積される（図１５参照）。トークンがトークンバケットのバケットサイズまで蓄積されると、その後供給されるトークンは廃棄される。
【００４３】
例えば、トークンバケットのトークン残量が上限値であり、且つ、大量のパケット、すなわち、バーストが到着した場合には、シェーパは、トークン残量がパケットサイズａを下回るまでバーストを送出することができる（図１６参照）。シェーパはトークンバケットに保持されるトークンを使って一気にバーストのパケットを出力し、一時的にシェーピングレートを超えた出力レートでパケットを送出することができる。
【００４４】
以上のようにして、トークンバケット型シェーパは、バーストが発生した場合に、トークンバケットに保持されているトークン量の分だけパケットをバッファメモリから一気に読み出すことができる。トークンバケット型シェーパは、最大でバケットサイズ分のパケットをバッファメモリから一気に読み出すことができる。バッファメモリから複数のパケットを一気に読み出すことは、以降、バースト読出しと呼ばれる。したがって、トークンバケット型シェーパには、或る程度のバースト耐性があるといえる。ただし、トークンバケット型シェーパでは、平衡状態について考慮されていないため、以下に示すように、平衡状態において別のバーストトラフィックが発生した場合に十分な耐性を持っていない可能性がある。
【００４５】
図１８Ａ，図１８Ｂ，図１８Ｃ，図１８Ｄ，及び図１８Ｅは、トークンバケット型シェーパの平衡状態において、別のバーストトラヒックが到着した際の動作の例を説明するための図である。図１８Ａ，図１８Ｂ，図１８Ｃ，図１８Ｄ，及び図１８Ｅにおいて、吹き出しには、トークンバケットのトークン残量のグラフが模式的に示されている。トークン残量のグラフでは、横軸が時間、縦軸がトークン残量を示している。また、図１８Ａ，図１８Ｂ，図１８Ｃ，図１８Ｄ，及び図１８Ｅにおいては、説明の簡略化のために、シェーパに到着するパケットのサイズはすべて同じサイズであることが仮定されている。
【００４６】
（１）トークンバケットのトークン残量が最大の状態で、シェーパにシェーピングレートより大きい入力レートでＴＣＰのトラヒックが到着したと仮定する（図１８Ａ）。
【００４７】
（２）トークンバケットにはトークンが十分に蓄積されているため、トークンが枯渇するまでの間は、到着したパケットは入力レートのままバッファメモリから読み出される（図１８Ｂ）。すなわち、シェーパはバースト読出しをすることができる。
【００４８】
（３）一旦トークンが枯渇すると、トークンの蓄積を待ってパケットの読出しが行われるため、バッファメモリからはシェーピングレートでしかパケットが読み出されなくなり、バッファメモリにキューが形成され始める。図１３Ａ及び図１３Ｂにおいて説明されたように、キューが形成されるとＲＴＴが大きくなるため、しばらく後に、入力レートが小さくなって、平衡状態になる（図１８Ｃ）。トークン残量は、０から到着パケットのサイズに相当する量までの間の値を繰り返す状態になる。
【００４９】
（４）平衡状態にあるＴＣＰのフローとは異なるＴＣＰの通信に属するバーストトラヒックが到着したと仮定する（図１８Ｄ）。
【００５０】
（５）しかしながら、平衡状態のフローが存在する状態ではバッファメモリからはシェーピングレートでしかパケットが読み出されず、トークンの供給が追い付かないので、到着するパケットは次々にバッファメモリに蓄積されていく。次第にバッファメモリが不足し、バッファあふれが発生すると、その後到着したパケットが廃棄されてしまう（図１８Ｅ）。
【００５１】
以上のようにして、トークンバケット型シェーパでは、平衡状態において新たにバーストトラフィックが到着すると、バッファあふれが発生し、パケット廃棄が発生する可能性がある。
【００５２】
＜第１実施形態＞
中継装置は、ネットワーク上で送信側装置と受信側装置との間に存在し、パケットの中継を行う。中継装置は帯域制御装置としてトークンバケット型シェーパを有している。
【００５３】
図１は、中継装置のハードウェア構成例を示す図である。中継装置１００は、例えば、
シャーシ型のスイッチやルータである。中継装置１００は、管理モジュール１１０，スイッチファブリック１２０，複数のインターフェースカード１３０を備える。
【００５４】
管理モジュール１１０は、制御情報のやりとりや装置自身の状態を管理する。スイッチファブリック１２０は、インターフェースカード１０３間のデータのやり取りを中継する。インターフェースカード１３０は、データの入出力のインターフェースを有し、物理リンクを接続する。物理リンクは、例えば、光ファイバケーブルやＬＡＮケーブルなどである。シェーパはインターフェースカードの出力側に備えられる。
【００５５】
図２は、インターフェースカードの構成例を示す図である。インターフェースカード１３０には、ＣＰＵ（Central Processing Unit）１３１，ＴＭ  ＬＳＩ（Traffic Management Large Scale Integration）１３２，ＭＡＣ／ＰＨＹ  ＬＳＩ（Media Access Control/PHYsical LSI）１３３，複数のＳＦＰ（Small Form Factor Pluggable）１３４，及び
外部メモリ１３５が備えられる。ＳＰＦ  １３４は、光ファイバを接続させる光モジュールであり、光信号と電気信号との変換を行う。なお、ＳＰＦ  １３４のような光モジュールの代わりに、例えば、ＲＪ−４５などの電気信号を伝送するケーブルを接続させるインターフェースであってもよい。
【００５６】
ＭＡＣ／ＰＨＹ  ＬＳＩ  １３３は、ＯＳＩ（Open Systems Interconnection）参照モデルのレイヤ１である物理層と、レイヤ２の１つであるＭＡＣ層との処理を行う。具体的には、ＭＡＣ／ＰＨＹ  ＬＳＩ  １３３は、電気信号である入力信号からフレームを復元し、フレームからヘッダを外して逆カプセル化しパケットにしてＴＭ  ＬＳＩ  １３２に出力する。出力信号に対しては、ＭＡＣ／ＰＨＹ  ＬＳＩ  １３３は、パケットに対してヘッダを付加してフレームを生成し、フレームを電気信号に変換してＳＦＰ  １３４に出力する。外部メモリ１３５は、例えば、ＤＲＡＭ（Dynamic Access Memory）などであり
、バッファとしての領域を提供する。
【００５７】
ＴＭ  ＬＳＩ  １３２は、ＯＳＩ参照モデルのレイヤ３以上の上位レイヤにおけるトラヒック制御やＱｏＳ（Quality of Service）に関する制御を行う。ＱｏＳには、例えば、ポリシング，シェーピング，優先制御などがある。帯域制御装置であるシェーパは、ＴＭ
ＬＳＩ  １３２によって実現されるＱｏＳのうちの１つである。
【００５８】
図３は、シェーパの構成例を示す図である。シェーパ１は、例えば、図２に示されるＴＭ  ＬＳＩ  １３２の機能の１つである。
【００５９】
シェーパ１は、キュー長監視部１１と、バースト読出し管理部１２と、トークン供給部１３と、トークンバケット１４と、読出し制御部１５と、バッファメモリ１６とを備える。
【００６０】
トークン供給部１３は、周期的に送信権であるトークンをトークンバケット１４に供給する。トークンは、送信を許可されるパケットのデータサイズを決定する送信権である。例えば、送信を許可されるパケットのデータサイズがトークン１つ当たりにバイト単位で予め決められており、１回に供給されるトークンの数も予め決められている。すなわち、トークン供給部Ｐ１３が１回に供給するトークン量は予め決められている。なお、トークン供給部１３は、周期的にトークンを供給するとともに、パケット到着時にもトークンを供給してもよい。
【００６１】
トークンバケット１４は、トークン供給部１３から供給されるトークンを保持する。トークンバケット１４は、バッファメモリ１６からパケットが読み出されるときにパケットのサイズに相当するトークンを減じられる。
【００６２】
トークンバケット１４には、バケットサイズとしてトークンを保持できる最大値とトークン閾値とが設定されている。トークン閾値は、バッファメモリ１６からのパケットの読み出しを許可するか否かを決定する閾値である。ただし、バーストが発生していると判定された場合には、トークン閾値に関係なく、トークンバケット１４にトークンが保持されていれば、バッファメモリ１６からパケットが読み出される。トークン閾値には、バケットサイズ以下の値が設定される。
【００６３】
図３では、トークン残量はＴｌｅｎ、トークン閾値はＴｔｈ、バケットサイズ（トークン残量の上限値）はＴｍａｘとして表わされている。トークン閾値Ｔｔｈはなるべく大きい値の方が好ましい。例えば、トークン閾値Ｔｔｈはトークンバケット１４のバケットサイズＴｍａｘと等しい値とされる。
【００６４】
バッファメモリ１６は、例えば、図２の外部メモリ１３５の作業領域に生成される。バッファメモリ１６は、例えば、図１のスイッチファブリック１２０から入力されるパケットを到着順に一時的に保持し、到着順にパケットが読み出されるＦＩＦＯ（First In First Out）キューである。すなわち、バッファメモリ１６は、パケットを先入れ先出しする。バッファメモリ１６には、バッファサイズであるキュー長の最大値とバッファ閾値とが設定されている。バッファ閾値は、バーストが発生しているか否かを判定するための閾値である。キュー長がバッファ閾値を超えると、バーストが発生していると判定される。図３では、キュー長はＱｌｅｎ、バッファ閾値はＱｔｈ、バッファサイズ（キュー長の上限値）はＱｍａｘとして表わされる。バッファ閾値Ｑｔｈはなるべく大きい値の方が好ましい。例えば、バッファ閾値Ｑｔｈは、バッファサイズＱｍａｘから１パケットサイズを引いた値とすることができる。
【００６５】
キュー長監視部１１は、バッファメモリ１６に形成されるキューのサイズ（長さ）を監視し、キュー長Ｑｌｅｎとバッファ閾値Ｑｔｈとの関係を定期的にバースト読出し管理部１２に報告する。
【００６６】
バースト読出し管理部１２は、キュー長監視部１１から報告されるキュー長Ｑｌｅｎとバッファ閾値Ｑｔｈとの関係とからバーストの発生を検知する。バースト読出し管理部１２は、バーストが発生しているか否かに応じて、異なるパケット読出しの制御を行う。
【００６７】
バースト読出し管理部１２は、キュー長Ｑｌｅｎがバッファ閾値Ｑｔｈ以上の場合には、バーストの発生を検知する。バーストの発生が検知された場合には、パケット廃棄を防ぐため、バースト読出し管理部１２は、キュー長Ｑｌｅｎがバッファ閾値Ｑｔｈより小さくなるまで、又は、トークン残量Ｔｌｅｎの許容限度まで、バッファメモリ１６からのパケットの読み出しを決定する。
【００６８】
キュー長Ｑｌｅｎがバッファ閾値Ｑｔｈ未満の場合には、バースト読出し管理部１２は、バーストの発生を検知しない。バーストの発生が検知されない場合には、バースト読出し管理部１２は、トークンがトークン閾値Ｔｔｈだけ確保されていれば、すなわち、トークン残量Ｔｌｅｎがトークン閾値Ｔｔｈ以上であれば、バッファメモリ１６からのパケットの読出しを決定する。バーストの発生が検知されない場合には、バースト読出し管理部１２は、トークン残量Ｔｌｅｎがトークン閾値Ｔｔｈ以上でなければバッファメモリ１６からのパケットの読出しを許可しない。バースト読出し管理部１２は、パケットの読出しを決定すると、読出し制御部１５にパケット読出しを指示する。
【００６９】
読出し制御部１５は、バースト読出し管理部１２からパケットの読出しを指示されると、バッファメモリ１６に保持される先頭パケットから順にパケットを読み出す。読出し制
御部１５は、バッファメモリ１６からパケットを読み出すとともに、読み出されるパケットのサイズに相当するトークンをトークンバケット１４から減らす。読出し制御部１５によって読み出されたパケットは、例えば、図２のＭＡＣ／ＰＨＹ  ＬＳＩ  １３３に出力される。
【００７０】
シェーパ１は、帯域制御装置に相当する。パケットはデータユニットに相当する。トークンバケット１４はカウンタ管理部に相当する。トークンバケット１４に保持されるトークンの合計値は、カウンタ値に相当する。トークン閾値はカウンタ閾値に相当する。バースト読出し管理部１２は制御部に相当する。データユニットは、パケットに限られず、例えば、フレームであってもよい。
【００７１】
図４は、トークンバケット１４にトークンが供給された際のパケット読出し処理のフローの例が示される。
【００７２】
トークン供給部１３によって供給されたトークン供給量ｃとトークン残量Ｔｌｅｎとの和がバケットサイズＴｍａｘ以下の場合には（ＯＰ１：Ｙｅｓ）、トークンがｃだけ供給されてもトークン残量ＴｌｅｎがバケットサイズＴｍａｘに満たない。したがって、供給されたトークンはトークンバケット１４に蓄積され、トークン残量Ｔｌｅｎは、トークン供給量ｃが加算された値に更新される（ＯＰ２）。
【００７３】
トークン供給量ｃとトークン残量Ｔｌｅｎとの和がバケットサイズより大きい場合には（ＯＰ１：Ｎｏ）、トークンが供給されるとトークンバケット１４が満杯になり、バケットサイズ以上のトークンはトークンバケット１４には蓄積されない。トークン残量Ｔｌｅｎは、バケットサイズＴｍａｘと同じ値になる（ＯＰ３）。
【００７４】
バースト読出し管理部１２は、バーストが発生しているか否かを判定する。すなわち、バースト読出し管理部１２は、キュー長Ｑｌｅｎがバッファ閾値Ｑｔｈ未満か否かを判定する（ＯＰ４）。このとき、バースト読出し管理部１２は、キュー長監視部１１から報告されるキュー長ＱｌｅｎとバッファＱｔｈ閾値との関係を用いる。
【００７５】
キュー長Ｑｌｅｎがバッファ閾値Ｑｔｈ未満の場合には（ＯＰ４：Ｙｅｓ）、バースト読出し管理部１２は、バーストの発生を検知しない。この場合には、トークン残量Ｔｌｅｎがトークン閾値Ｔｔｈ以上であれば、バッファメモリ１６からパケットが読み出される。バースト読出し管理部１２は、トークンバケット１４のトークン残量Ｔｌｅｎがトークン閾値以上であるか否か、トークン残量Ｔｌｅｎがバッファメモリ１６の先頭パケットのサイズｂ以上か否か、及びバッファメモリ１６にパケットが保持されているか否かを判定する（ＯＰ５）。
【００７６】
トークン残量Ｔｌｅｎがバッファメモリ１６の先頭パケットのサイズｂ以上であり且つトークン閾値Ｔｔｈ以上であり、さらに、バッファメモリ１６にパケットが保持されている場合には（ＯＰ５：Ｙｅｓ）、バースト読出し管理部１２は、バッファメモリ１６から先頭パケットの読み出しを決定する。バースト読出し管理部１２は、読出し制御部１５にバッファメモリ１６の先頭パケットの読出しを指示する。
【００７７】
バッファメモリ１６の先頭パケットの読出しを指示されると、読出し制御部１５は、トークンバケット１４から先頭パケットのサイズｂに相当するトークンを減じて、先頭パケットをバッファメモリ１６から読み出す（ＯＰ７ａ）。トークン残量Ｔｌｅｎは、読み出された先頭パケットのサイズｂが減じられた値になる。キュー長Ｑｌｅｎは、読み出された先頭パケットのサイズｂが減じられた値になる。その後、処理がＯＰ４に戻る。ＯＰ４及びＯＰ５の条件が満たされる間は、ＯＰ７ａの処理が繰り返されてバッファメモリ１６
からパケットが読み出される。
【００７８】
トークン残量Ｔｌｅｎがトークン閾値未満である場合、トークン残量Ｔｌｅｎがバッファメモリ１６の先頭パケットのサイズｂ未満である場合、又は、バッファメモリ１６にパケットが保持されていない場合のいずれかの場合には（ＯＰ５：Ｎｏ）、バッファメモリ１６からパケットは読み出されず、処理が終了する。
【００７９】
ＯＰ４において、キュー長Ｑｌｅｎがバッファ閾値Ｑｔｈ以上の場合には（ＯＰ４：Ｎｏ）、バースト読出し管理部１２は、バーストの発生を検知する。バーストの発生が検知された場合には、バッファあふれによるパケットの廃棄を回避するため、トークン残量Ｔｌｅｎとトークン閾値Ｔｔｈとの関係にかかわらず、バッファメモリ１６からパケットが読み出される。バースト読出し管理部１２は、トークンバケット１４にバッファメモリ１６の先頭パケットのサイズｂに相当するだけのトークンが保持されているか否かを判定する（ＯＰ６）。すなわち、バースト読出し管理部１２は、トークン残量Ｔｌｅｎがバッファメモリ１６の先頭パケットのサイズｂ以上か否かを判定する。
【００８０】
トークン残量Ｔｌｅｎがバッファメモリ１６の先頭パケットのサイズｂ以上の場合には（ＯＰ６：Ｙｅｓ）、バースト読出し管理部１２は、バッファメモリ１６の先頭パケットを読み出すことを決定する。バースト読出し管理部１２は、バッファメモリ１６の先頭パケットの読出しを読み出し制御部１５に指示する。
【００８１】
バッファメモリ１６の先頭パケットの読出しを指示されると、読出し制御部１５は、トークンバケット１４から先頭パケットのサイズｂに相当するトークンを減じて、先頭パケットをバッファメモリ１６から読み出す（ＯＰ７ｂ）。トークン残量Ｔｌｅｎは、読み出された先頭パケットのサイズｂが減じられた値になる。キュー長Ｑｌｅｎは、読み出された先頭パケットのサイズｂが減じられた値になる。その後、処理がＯＰ４に戻る。
【００８２】
トークン残量Ｔｌｅｎがバッファメモリ１６の先頭パケットのサイズｂ未満の場合には（ＯＰ６：Ｎｏ）、トークンが枯渇したことが示され、バッファメモリ１６からパケットは読み出されず、処理が終了する。
【００８３】
ＯＰ４の条件が満たされない、すなわち、バーストが発生が検知されると、トークン残量Ｔｌｅｎがトークン閾値Ｔｔｈ以上か否かにかかわらず、バッファメモリ１６からパケットが読み出される。パケットが読み出されてキュー長Ｑｌｅｎがバッファ閾値Ｑｔｈを下回ると（ＯＰ４：Ｙｅｓ）、バーストが収まったとみなされ、ＯＰ５、ＯＰ７ａの処理が行われる。その後、パケット読出しによってトークン残量Ｔｌｅｎがトークン閾値Ｔｔｈを下回ると（ＯＰ５：Ｎｏ）、処理が終了する。
【００８４】
一方、ＯＰ７ｂの処理の繰り返しによるパケットの読出し後に、バーストが収まらなくても（ＯＰ４：Ｎｏ）、トークン残量Ｔｌｅｎが枯渇すると（ＯＰ６：Ｎｏ）、バッファメモリ１６からパケットが読み出せなくなるため、処理が終了する。
【００８５】
図５は、シェーパ１にパケットが到着した際のパケット読出し処理のフローの例を示す図である。シェーパ１に到着するパケットのサイズはａと仮定される。
【００８６】
到着パケットのサイズａと現在のキュー長Ｑｌｅｎとの和がバッファサイズより大きい場合には（ＯＰ１１：Ｎｏ）、バッファあふれが発生するので、到着パケットは廃棄される（ＯＰ１７）。
【００８７】
到着パケットのサイズａと現在のキュー長Ｑｌｅｎとの和がバッファサイズ以下の場合
には（ＯＰ１１：Ｙｅｓ）、到着パケットはバッファメモリ１６に格納される（バッファリング）（ＯＰ１２）。キュー長Ｑｌｅｎは、到着パケットのサイズａが加算された値になる。この後、キュー長監視部１１によってキュー長Ｑｌｅｎとバッファ閾値Ｑｔｈとの関係がバースト読み出し管理部１２に報告される。
【００８８】
バースト読出し管理部１２は、キュー長Ｑｌｅｎがバッファ閾値Ｑｔｈ未満か否かを判定する（ＯＰ１３）。すなわち、バースト読出し管理部１２は、バーストが発生しているか否かを判定する。
【００８９】
キュー長Ｑｌｅｎがバッファ閾値Ｑｔｈ未満である場合には（ＯＰ１３：Ｙｅｓ）、バーストは検知されない。トークンバケット１４のトークン残量Ｔｌｅｎがトークン閾値Ｔｔｈ以上であれば、バッファメモリ１６からのパケットの読出しが許可される。バースト読出し管理部１２は、トークン残量Ｔｌｅｎがトークン閾値Ｔｔｈ以上か否か、トークン残量Ｔｌｅｎがバッファメモリ１６の先頭パケットのサイズｂ以上か否か、及びバッファメモリ１６にパケットが保持されているか否かを判定する（ＯＰ１４）。
【００９０】
トークン残量Ｔｌｅｎがバッファメモリ１６の先頭パケットのサイズｂ以上であり且つトークン閾値Ｔｔｈ以上であり、さらに、バッファメモリ１６にパケットが保持されている場合には（ＯＰ１４：Ｙｅｓ）、バースト読出し管理部１２は、バッファメモリ１６の先頭パケットを読み出すことを決定する。バースト読出し管理部１２は、読出し制御部１５にバッファメモリ１６の先頭パケットの読出しを指示する。
【００９１】
バッファメモリ１６の先頭パケットの読出しを指示されると、読出し制御部１５は、トークンバケット１４から先頭パケットのサイズｂに相当するトークンを減じて、先頭パケットをバッファメモリ１６から読み出す（ＯＰ１６ａ）。トークン残量Ｔｌｅｎは、読み出された先頭パケットのサイズｂが減じられた値になる。キュー長Ｑｌｅｎは、読み出された先頭パケットのサイズｂが減じられた値になる。その後、処理がＯＰ１３に戻る。ＯＰ１３及びＯＰ１４の条件が満たされる間は、ＯＰ１６ａの処理が繰り返されてバッファメモリ１６からパケットが読み出される。バッファメモリ１６に到着パケットしか保持されていない場合には、先頭パケット＝到着パケットとなり、到着パケットが読み出され、トークン残量Ｔｌｅｎから到着パケットのサイズａが減じられる。
【００９２】
トークン残量Ｔｌｅｎがトークン閾値Ｔｔｈ未満である場合、トークン残量Ｔｌｅｎがバッファメモリ１６の先頭パケットのサイズｂ未満である場合、又は、バッファメモリ１６にパケットが保持されていない場合のいずれかの場合には（ＯＰ１４：Ｎｏ）、バッファメモリ１６からパケットは読み出されず、処理が終了する。
【００９３】
ＯＰ１３において、キュー長Ｑｌｅｎがバッファ閾値Ｑｔｈ以上である場合には（ＯＰ１３：Ｎｏ）、バースト読出し管理部１２はバーストの発生を検知する。バーストの発生が検知された場合には、バッファあふれによるパケットの廃棄を回避するため、トークン残量Ｔｌｅｎとトークン閾値Ｔｔｈとの関係にかかわらず、バッファメモリ１６からパケットが読み出される。バースト読出し管理部１２は、トークンバケット１４にバッファメモリ１６の先頭パケットのサイズｂに相当するトークンが保持されているか否かを判定する（ＯＰ１５）。すなわち、バースト読出し管理部１２は、トークン残量Ｔｌｅｎがバッファメモリ１６の先頭パケットのサイズｂ以上か否かを判定する。
【００９４】
トークン残量Ｔｌｅｎがバッファメモリ１６の先頭パケットのサイズｂ以上の場合には（ＯＰ１５：Ｙｅｓ）、バースト読出し管理部１２は、バッファメモリ１６の先頭パケットを読み出すことを決定する。バースト読出し管理部１２は、バッファメモリ１６の先頭パケットの読出しを読み出し制御部１５に指示する。
【００９５】
バッファメモリ１６の先頭パケットの読出しを指示されると、読出し制御部１５は、トークンバケット１４から先頭パケットのサイズｂに相当するトークンを減じて、先頭パケットをバッファメモリ１６から読み出す（ＯＰ１６ｂ）。トークン残量Ｔｌｅｎは、読み出された先頭パケットのサイズｂが減じられた値になる。キュー長Ｑｌｅｎは、読み出された先頭パケットのサイズｂが減じられた値になる。その後、処理がＯＰ１３に戻る。ＯＰ１３の条件が満たされない場合、すなわち、バーストが発生している場合は、トークン残量Ｔｔｈが先頭パケットのサイズｂ以上あれば（ＯＰ１５：Ｙｅｓ）、ＯＰ１６ｂの処理が繰り返されてバッファメモリ１６からパケットが読み出される。
【００９６】
トークン残量Ｔｌｅｎがバッファメモリ１６の先頭パケットのサイズｂ未満の場合には（ＯＰ１５：Ｎｏ）、トークンが枯渇していることが示され、バッファメモリ１６からパケットは読み出されず、処理が終了する。
【００９７】
ＯＰ１３の条件が満たされない、すなわち、バーストが発生していて、トークンが枯渇するまでの間（ＯＰ１５：Ｙｅｓ）は、ＯＰ１６ｂの処理が繰り返されてバッファメモリ１６からパケットが読み出される。パケットが読み出されてキュー長Ｑｌｅｎがバッファ閾値Ｑｔｈを下回った場合には（ＯＰ１３：Ｙｅｓ）、ＯＰ１４、ＯＰ１６ａの処理が行われる。その後、パケット読出しによって、例えば、トークン残量Ｔｌｅｎがトークン閾値Ｔｔｈを下回ると（ＯＰ１４：Ｎｏ）、処理が終了する。
【００９８】
図４及び図５より、シェーパ１において、バーストが検知された場合には、少なくともキュー長Ｑｌｅｎがバッファ閾値Ｑｔｈを下回るまで、又は、トークンが枯渇するまで、パケットが読み出される。また、バーストが検知されない場合には、トークン残量Ｔｌｅｎがトークン閾値Ｔｔｈを下回るまで、トークン残量Ｔｌｅｎがバッファメモリ１６の先頭パケットのサイズｂを下回るまで、又は、バッファメモリ１６に保持されるパケットがなくなるまで、パケットが読み出される。
【００９９】
図６Ａ，図６Ｂ，図６Ｃ，図６Ｄ，及び図６Ｅは、第１実施形態のシェーパ１の平衡状態において、別のバーストトラヒックが到着した例を説明するための図である。図６Ａ，図６Ｂ，図６Ｃ，図６Ｄ，及び図６Ｅは、図１８Ａ，図１８Ｂ，図１８Ｃ，図１８Ｄ，及び図１８Ｅとそれぞれ対応している。図６Ａ，図６Ｂ，図６Ｃ，図６Ｄ，及び図６Ｅにおいて、吹き出しには、トークンバケットのトークン残量のグラフが模式的に示されており、横軸が時間、縦軸がトークン残量を示している。実線が第１実施形態のシェーパ１のトークン残量を示し、破線がシェーパＰ１（図１４）のトークン残量を示している。すなわち、破線は、図１８Ａ，図１８Ｂ，図１８Ｃ，図１８Ｄ，及び図１８Ｅのそれぞれに示されるトークンバケットのトークン残量に対応している。また、図６Ａ，図６Ｂ，図６Ｃ，図６Ｄ，及び図６Ｅでは、トークン閾値Ｔｈがトークンバケット１４のバケットサイズＴｍａｘの値に設定されていると想定する。また、図６Ａ，図６Ｂ，図６Ｃ，図６Ｄ，及び図６Ｅでは、説明の簡略化のため、到着パケットはすべて同じサイズであると想定する。
【０１００】
（１）トークンバケット１４には、バケットサイズＴｍａｘ分のトークンが蓄積されている。シェーパにシェーピングレートより大きい入力レートでＴＣＰのトラヒックが到着したと仮定する（図６Ａ）。
【０１０１】
（２）シェーパ１では、トークンバケット１４にはトークン閾値Ｔｔｈ分のトークンが蓄積されているため、パケットが読み出される。パケットが読み出されると、読み出されたパケットのサイズの分だけトークンバケット１４からトークンが減る。トークン残量Ｔｌｅｎがトークン閾値Ｔｔｈより小さい間は、バッファメモリ１６からパケットは読み出されず（図５参照）、到着するパケットによってキューが形成される（図６Ｂ）。トーク
ン残量Ｔｌｅｎが再びトークン閾値Ｔｔｈに達すると、先頭パケットがバッファメモリ１６から読み出される。このとき、トークンが供給されるレート、すなわち、シェーピングレートに応じたレートでパケットが読み出されるようになる。一方、図１８Ｂに示されるように、シェーパＰ１では、トークンが枯渇するまでパケットが読み出される。
【０１０２】
（３）キューが形成されるとＲＴＴが大きくなるため、しばらく後に、入力レートが小さくなって、平衡状態になる（図６Ｃ）。シェーパ１では平衡状態において、トークン残量Ｔｌｅｎはトークン閾値Ｔｔｈ付近で推移する。シェーパ１のトークンバケット１４にはトークンが十分残っていることになる。一方、図１８Ｃに示されるシェーパＰ１のトークンバケットＰ１４では、トークン残量Ｔｌｅｎは、トークンが枯渇するか否かの状態で推移する。
【０１０３】
（４）平衡状態にあるＴＣＰのフローとは異なるＴＣＰの通信に属するバーストトラヒックが到着したと仮定する（図６Ｄ）。
【０１０４】
（５）平衡状態のフローを有するシェーパからはシェーピングレートでしかパケットは読み出されないので、到着するパケットは次々にバッファメモリに蓄積されていく。シェーパ１では、キュー長Ｑｌｅｎがバッファ閾値Ｑｔｈに達したときに、トークン閾値Ｔｔｈとトークン残量Ｔｌｅｎとの関係にかかわらず、バッファメモリ１６からパケットが読み出され（バースト送出）、バッファメモリ１６に空きスペースが作り出される。シェーパ１では、バッファメモリの空きが増加するため、次に到着するバーストのパケットを許容することができるようなり、パケットの廃棄を回避することができる（図６Ｅ）。一方、シェーパＰ１では、図１８Ｅに示されるように、平衡状態になった時点で十分にトークンがないため、到着したバーストによってバッファあふれが引き起こされてパケットが廃棄される。
【０１０５】
シェーパ１において、バースト送出によりトークンが枯渇すると、図１８Ｅに示される状態と同じ状態になってしまうものの、バッファあふれの状態になるのを遅らせることができるため、シェーパＰ１に比べてパケット廃棄を低減することができる。
【０１０６】
図１８Ｅに示されるシェーパＰ１のトークン残量と比較すると、シェーパＰ１では、或るＴＣＰのフローが平衡状態のときに別のＴＣＰのバーストが発生すると、トークン残量が十分でないため、すぐにバッファあふれになってしまい、パケットが廃棄されてしまう。第１実施形態のシェーパ１では、トークン閾値Ｔｔｈによって、シェーパＰ１に比べると早く平衡状態になり、トークン残量Ｔｌｅｎがトークン閾値Ｔｔｈ付近を推移する。したがって、シェーパ１には、キュー長Ｑｌｅｎがバッファ閾値Ｑｔｈを超えた時点でバッファメモリ１６からパケットを読み出せるだけの十分なトークンが残っている可能性が高まる。シェーパ１は、キュー長Ｑｌｅｎがバッファ閾値Ｑｔｈを超えた時点で、すなわち、バーストを検知するとパケットを読み出すため、バッファメモリ１６に空きを作ることができ、バッファあふれを遅らせることができる。シェーパ１は、バッファあふれを遅らせることによって、パケット廃棄を低減することができる。
【０１０７】
また、バッファ閾値Ｑｔｈを、例えば、バッファサイズＱｍａｘから1パケットサイズ
を引いた値とし、トークン閾値Ｔｔｈを、例えば、バケットサイズＴｍａｘとした場合には、平衡状態になるまでの過渡状態において、バースト読出しの実行を低減することができる。また、平衡状態において、シェーパ１のバースト耐性を最大にすることができる。
【０１０８】
＜第２実施形態＞
第２実施形態では、トークン閾値及びバッファ閾値がそれぞれ複数設定され、トークン残量と各トークン閾値との関係、及び、キュー長と各バッファ閾値との関係に基づいてパ
ケット読出し処理が実行される。第２実施形態では、第１実施形態と異なる部分についてのみ説明され、共通する部分の説明は省略される。
【０１０９】
図７は、第２実施形態のシェーパの構成例を示す図である。シェーパ１ｂは、キュー長監視部１１，バースト読出し管理部１２ｂ，トークン供給部１３，トークンバケット１４ｂ，読出し制御部１５，及びバッファメモリ１６ｂを備える。
【０１１０】
トークンバケット１４ｂには、第１トークン閾値Ｔｔｈ１，第２トークン閾値Ｔｔｈ２，及び第３トークン閾値Ｔｔｈ３が設定される。０＜第３トークン閾値Ｔｔｈ３＜第２トークン閾値Ｔｔｈ２＜第１トークン閾値Ｔｔｈ１≦トークンバケットサイズＴｍａｘである。
【０１１１】
バッファメモリ１６ｂには、第１バッファ閾値Ｑｔｈ１，第２バッファ閾値Ｑｔｈ２，及び第３バッファ閾値Ｑｔｈ３が設定される。０＜第１バッファ閾値Ｑｔｈ１＜第２バッファ閾値Ｑｔｈ２＜及び第３バッファ閾値Ｑｔｈ３＜バッファサイズＱｍａｘである。
【０１１２】
バースト読出し管理部１２ｂは、キュー長Ｑｌｅｎと、バッファ閾値Ｑｔｈ１〜Ｑｔｈ３との関係と、トークン残量Ｔｌｅｎと、トークン閾値Ｔｔｈ１〜Ｔｔｈ３との関係とに基づいて、バッファメモリ１６からのパケットの読出しを決定する。具体的には、以下の場合に、バースト読出し管理部１２ｂは、バッファメモリ１６ｂから先頭パケットの読出しを決定する。
（１）０＜Ｑｌｅｎ＜Ｑｔｈ１、且つ、Ｔｈ１≦Ｔｌｅｎの場合
（２）Ｑｔｈ１≦Ｑｌｅｎ＜Ｑｔｈ２、且つ、Ｔｈ２≦Ｔｌｅｎの場合
（３）Ｑｔｈ２≦Ｑｌｅｎ＜Ｑｔｈ３、且つ、Ｔｈ３≦Ｔｌｅｎの場合
（４）Ｑｔｈ３≦Ｑｌｅｎ、且つ、先頭パケットサイズｂ≦Ｔｌｅｎの場合
【０１１３】
図８は、第２実施形態における、トークン供給時のパケット読出し処理のフローの例を示す図である。ＯＰ２１からＯＰ２３の処理は、図４に示されるＯＰ１からＯＰ３のそれぞれの処理と同じであるので、説明は省略される。
【０１１４】
バースト読出し管理部１２ｂは、キュー長Ｑｌｅｎが第１バッファ閾値Ｑｔｈ１未満であるか否かを判定する（ＯＰ２４）。
【０１１５】
キュー長Ｑｌｅｎが第１バッファ閾値Ｑｔｈ１未満の場合には（ＯＰ２４：Ｙｅｓ）、バースト読出し管理部１２ｂは、トークン残量Ｔｌｅｎが第１トークン閾値Ｔｔｈ１以上か否か、トークン残量Ｔｌｅｎがバッファメモリ１６の先頭パケットのサイズｂ以上か否か、及びバッファメモリ１６ｂにパケットが保持されているか否かを判定する（ＯＰ２５）。
【０１１６】
トークン残量Ｔｌｅｎがバッファメモリ１６の先頭パケットのサイズｂ以上であり且つ第１トークン閾値Ｔｔｈ１以上であり、さらに、バッファメモリ１６ｂにパケットが保持されている場合には（ＯＰ２５：Ｙｅｓ）、バースト読出し管理部１２ｂは、バッファメモリ１６ｂの先頭パケットを読み出すことを決定する。バースト読出し管理部１２ｂは、読出し制御部１５にバッファメモリ１６ｂの先頭パケットの読出しを指示する。
【０１１７】
バッファメモリ１６ｂの先頭パケットの読出しを指示されると、読出し制御部１５は、トークンバケット１４ｂから先頭パケットのサイズｂに相当するトークンを減じて、先頭パケットをバッファメモリ１６ｂから読み出す（ＯＰ３２ａ）。トークン残量Ｔｌｅｎは、読み出された先頭パケットのサイズｂが減じられた値になる。キュー長Ｑｌｅｎは、読み出された先頭パケットのサイズｂが減じられた値になる。その後、処理がＯＰ２４に戻
り、ＯＰ２４及びＯＰ２５の条件が満たされる間、ＯＰ３２ａの処理が繰り返されてパケットの読出しが行われる。
【０１１８】
トークン残量Ｔｌｅｎが第１トークン閾値Ｔｔｈ１未満である場合、トークン残量Ｔｌｅｎがバッファメモリ１６の先頭パケットのサイズｂ未満である場合、又は、バッファメモリ１６ｂにパケットが保持されていない場合には（ＯＰ２５：Ｎｏ）、バッファメモリ１６ｂからパケットは読み出されず、処理が終了する。
【０１１９】
キュー長Ｑｌｅｎが第１バッファ閾値Ｑｔｈ１以上である場合には（ＯＰ２４：Ｎｏ）、バースト読出し管理部１２ｂは、キュー長Ｑｌｅｎが第１バッファ閾値Ｑｔｈ１以上且つ第２バッファ閾値Ｑｔｈ２未満であるか否かを判定する（ＯＰ２６）。
【０１２０】
キュー長Ｑｌｅｎが第１バッファ閾値Ｑｔｈ１以上且つ第２バッファ閾値Ｑｔｈ２未満の場合には（ＯＰ２６：Ｙｅｓ）、トークン残量Ｔｌｅｎが第２トークン閾値Ｔｔｈ２以上であれば、パケットの読出しが決定される。バースト読出し管理部１２ｂは、トークン残量Ｔｌｅｎが第２トークン閾値Ｔｔｈ２以上か否か、トークン残量Ｔｌｅｎがバッファメモリ１６の先頭パケットのサイズｂ以上か否か、及びバッファメモリ１６ｂにパケットが保持されているか否かを判定する（ＯＰ２７）。
【０１２１】
トークン残量Ｔｌｅｎがバッファメモリ１６の先頭パケットのサイズｂ以上であり且つ第２トークン閾値Ｔｔｈ２以上であり、さらに、バッファメモリ１６ｂにパケットが保持されている場合には（ＯＰ２７：Ｙｅｓ）、バースト読出し管理部１２ｂは、バッファメモリ１６ｂの先頭パケットを読み出すことを決定する。バースト読出し管理部１２ｂは、読出し制御部１５にバッファメモリ１６ｂの先頭パケットの読出しを指示し、その後、ＯＰ３２ａと同様の処理が行われる（ＯＰ３２ｂ）。その後、処理がＯＰ２６に戻り、ＯＰ２６及びＯＰ２７の条件が満たされる間、ＯＰ３２ｂの処理が繰り返されパケットの読出しが行われる。
【０１２２】
トークン残量Ｔｌｅｎが第２トークン閾値Ｔｔｈ２未満である場合、トークン残量Ｔｌｅｎがバッファメモリ１６の先頭パケットのサイズｂ未満である場合、又は、バッファメモリ１６ｂにパケットが保持されていない場合には（ＯＰ２７：Ｎｏ）、バッファメモリ１６ｂからパケットは読み出されず、処理が終了する。
【０１２３】
ＯＰ２６の条件が満たされない場合には（ＯＰ２６：Ｎｏ）、バースト読出し管理部１２ｂは、キュー長Ｑｌｅｎが第２バッファ閾値Ｑｔｈ２以上且つ第３バッファ閾値Ｑｔｈ３未満であるか否かを判定する（ＯＰ２８）。
【０１２４】
キュー長Ｑｌｅｎが第２バッファ閾値Ｑｔｈ２以上且つ第３バッファ閾値Ｑｔｈ３未満の場合には（ＯＰ２８：Ｙｅｓ）、トークン残量Ｔｌｅｎが第３トークン閾値以上であれば、パケットの読出しが決定される。バースト読出し管理部１２ｂは、トークン残量Ｔｌｅｎが第３トークン閾値Ｔｔｈ３以上か否か、トークン残量Ｔｌｅｎがバッファメモリ１６の先頭パケットのサイズｂ以上か否か、及びバッファメモリ１６ｂにパケットが保持されているか否かとを判定する（ＯＰ２９）。
【０１２５】
トークン残量Ｔｌｅｎがバッファメモリ１６の先頭パケットのサイズｂ以上であり且つ第３トークン閾値Ｔｔｈ３以上であり、さらに、バッファメモリ１６ｂにパケットが保持されている場合には（ＯＰ２９：Ｙｅｓ）、バースト読出し管理部１２ｂは、バッファメモリ１６ｂの先頭パケットを読み出すことを決定する。バースト読出し管理部１２ｂは、読出し制御部１５にバッファメモリ１６ｂの先頭パケットの読出しを指示し、ＯＰ３２ａと同様の処理が行われる（ＯＰ３２ｃ）。その後処理がＯＰ２８に戻り、ＯＰ２８及びＯ
Ｐ２９の条件が満たされる間、ＯＰ３２ｃの処理が繰り返されてパケットの読出しが行われる。
【０１２６】
トークン残量Ｔｌｅｎが第３トークン閾値Ｔｔｈ３未満である場合、トークン残量Ｔｌｅｎがバッファメモリ１６の先頭パケットのサイズｂ未満である場合、又は、バッファメモリ１６ｂにパケットが保持されていない場合には（ＯＰ２９：Ｎｏ）、バッファメモリ１６ｂからパケットは読み出されず、処理が終了する。
【０１２７】
キュー長Ｑｌｅｎが第３バッファ閾値Ｑｔｈ３以上である場合には（ＯＰ２８：Ｎｏ）、バースト読出し管理部１２ｂは、バーストを検知する。バーストが検知された場合には、トークン残量Ｔｌｅｎと各トークン閾値との関係にかかわらず、バッファメモリ１６ｂからパケットが読み出される。バースト読出し管理部１２ｂは、トークン残量Ｔｌｅｎが先頭パケットのサイズｂ以上か否かを判定する（ＯＰ３１）。
【０１２８】
トークン残量Ｔｌｅｎが先頭パケットのサイズｂ以上の場合には（ＯＰ３１：Ｙｅｓ）、バースト読出し管理部１２ｂは、バッファメモリ１６ｂの先頭パケットを読み出すことを決定する。バースト読出し管理部１２ｂは、読出し制御部１５にバッファメモリ１６ｂの先頭パケットの読出しを指示し、ＯＰ３２ａと同様の処理が行われる（ＯＰ３２ｄ）。その後処理がＯＰ２８に戻り、ＯＰ２８の条件が満たされず、且つ、ＯＰ３1の条件が満
たされる間は、パケットが読み出される。
【０１２９】
トークン残量Ｔｌｅｎが先頭パケットのサイズｂ未満の場合には（ＯＰ３１：Ｎｏ）、トークンバケット１４ｂに先頭パケットを読み出せるだけのトークンが蓄積されていないので、バッファメモリ１６ｂからパケットは読み出されず、処理が終了する。
【０１３０】
図９は、第２実施形態のパケット到着時のパケット読出し処理のフローの例を示す図である。図９のＯＰ４１，ＯＰ４２，及びＯＰ５２の到着パケットによってバッファあふれがあるか否かを判定する処理は、図５のＯＰ１１，ＯＰ１２，及びＯＰ１７の処理とそれぞれ同様であるので、説明は省略される。また、到着パケットをバッファリングした後の先頭パケットの読出しを決定する処理である図９のＯＰ４３〜ＯＰ５１ｄの処理は、それぞれ、図８のＯＰ２４〜ＯＰ３２ｄの処理と同様であり、説明は省略される。
【０１３１】
図８及び図９より、シェーパ１ｂは、キュー長Ｑｌｅｎが第ｎ−１バッファ閾値以上第ｎバッファ閾値未満（０＜ｎ≦３）の場合には、トークン残量Ｔｌｅｎが第ｎトークン閾値を下回るまで、トークン残量Ｔｌｅｎがバッファメモリ１６の先頭パケットのサイズｂを下回るまで、又は、キュー長Ｑｌｅｎが第ｎ−１バッファ閾値を下回るまでパケットを読み出す。第３バッファ閾値Ｑｔｈ３は、バースト検知のための閾値であり、キュー長Ｑｌｅｎが第３バッファ閾値Ｑｔｈ３を超えた場合には、トークンが枯渇するまで、又は、キュー長Ｑｌｅｎが少なくとも第３バッファ閾値Ｑｔｈ３を下回るまでパケットが読み出される。
【０１３２】
第２実施形態のシェーパ１ｂによれば、バッファ閾値及びトークン閾値がそれぞれ複数設定されることによって、よりきめの細かいパケットの読出しが可能となる。特に、第１実施形態のシェーパ１では、キュー長Ｑｌｅｎがバッファ閾値Ｑｔｈを超えた時点で、トークンバケットに保持される全てのトークンが使用可能となるので、後段の装置に対して大きなバーストが送出される可能性がある。一方、第２実施形態のシェーパ１ｂでは、複数のバッファ閾値と複数のトークン閾値とによって、段階的にトークンの使用が許可されるので、後段の装置へのバースト送出を抑えることができる。
【０１３３】
第２実施形態では、バッファ閾値とトークン閾値とがそれぞれ３つずつ設定される例に
ついて説明されたが、これに限られるものではなく、バッファ閾値とトークン閾値とはそれぞれ２つずつ、あるいは、４つ以上ずつ設定されてもよい。
【０１３４】
＜第３実施形態＞
第１実施形態及び第２実施形態においては、バッファメモリからのパケットの読出しレート、すなわち、シェーパの出力レートについては考慮されていない。シェーパの出力レートはトークン残量と連動している。トークンはトークン供給レートで供給され、初期設定において、トークン供給レート（所定時間内に供給されるトークン量）はシェーピングレートである。したがって、第３実施形態では、シェーパは、バッファメモリにレート制御閾値を複数設定し、キュー長とレート制御閾値との関係に基づいて、トークン供給レートを決定する。第３実施形態において、シェーパは、トークン供給レートを制御することによって、シェーパの出力レートを制御する。第３実施形態では、第１実施形態と異なる部分についてのみ説明され、共通する部分の説明は省略される。
【０１３５】
図１０は、第３実施形態におけるシェーパの構成例を示す図である。シェーパ１ｃは、キュー長監視部１１ｃ，バースト読出し管理部１２ｃ，トークン供給部１３ｃ，トークンバケット１４，読出し制御部１５，及びバッファメモリ１６ｃを備える。
【０１３６】
バッファメモリ１６ｃには、バッファ閾値Ｑｔｈに加えて、トークン供給レートを決定する際の閾値である、第１レート制御閾値ＲＣｔｈ１と第２レート制御閾値ＲＣｔｈ２とが設定される。０＜第１レート制御閾値ＲＣｔｈ１＜第２レート制御閾値ＲＣｔｈ２＜バッファ閾値Ｑｔｈである。
【０１３７】
キュー長監視部１１ｃは、バッファメモリ１６ｃのキュー長Ｑｌｅｎと、バッファ閾値Ｑｔｈ，第１レート制御閾値ＲＣｔｈ１，及び第２レート制御閾値ＲＣｔｈ２との関係を定期的にバースト読出し管理部１２ｃに報告する。
【０１３８】
バースト読出し管理部１２ｃは、キュー長監視部１１ｃから報告されたキュー長Ｑｌｅｎとバッファ閾値Ｑｔｈとの関係と、トークン残量Ｔｌｅｎとトークン閾値Ｔｔｈとの関係に基づいて、バッファメモリ１６ｃからのパケットの読出しを決定する。バースト読出し管理部１２ｃは、パケットの読出しを読出し制御部１５に指示する。
【０１３９】
また、バースト読出し管理部１２ｃは、キュー長監視部１１ｃから報告されるキュー長Ｑｌｅｎ，第１レート制御閾値ＲＣｔｈ１，及び第２レート制御閾値ＲＣｔｈ２の関係に基づいてトークン供給レートを決定する。バースト読出し管理部１２ｃは、決定されたトークン供給レートをトークン供給部１３ｃに指示する。
【０１４０】
バースト読出し管理部１２ｃは、キュー長が増加傾向にある場合、例えば、キュー長が第１レート制御閾値ＲＣｔｈ１未満の値から第１レート制御閾値ＲＣｔｈ１以上の値へと変化した場合には、トークン供給レートをシェーピングレートよりも小さな値にする。トークン供給レートをシェーピングレートよりも小さな値にすることによって、トークン残量の増加速度が遅くなる。トークン残量の増加速度が遅くなると、バッファメモリ１６ｃからパケットが読み出される速度が遅くなり、出力レートが下がる。出力レートが下がると、入力レートがシェーピングレートよりも大きい場合には、キュー長の増加速度が速くなる。シェーパ１ｃのキュー長の増大によって、ＲＴＴが大きくなり、送信側装置の平均的な出力レートが下がる。送信側装置で平均的な出力レートが下がると、シェーパ１ｃの平均的な入力レートも下がり、平衡状態になる。したがって、トークン供給レートがシェーピングレートよりも小さくされることによって、キュー長の増加が加速され、より迅速に平衡状態が導かれる。
【０１４１】
ただし、トークン供給レートがシェーピングレートよりも小さくなると、キュー長の増加が加速されるので、バッファあふれが発生する可能性が高くなる。したがって、バースト読出し管理部１２ｃは、或る程度のキュー長、例えば、キュー長が第２レート制御閾値ＲＣｔｈ２以上になる時点で、トークン供給レートをシェーピングレートに戻す。
【０１４２】
トークン供給部１３ｃは、バースト読出し部１２ｃからトークン供給レートをシェーピングレートよりも小さくするように指示を受けると、トークン供給レートをシェーピングレートよりも小さい予め設定されたレートにする。例えば、トークン供給部１３ｃは、１回当たりにトークンバケット１４に供給するトークン量を小さくすることによって、トークン供給レートを下げる。例えば、トークン供給部１３ｃは、トークンを供給する周期を小さくすることによって、トークン供給レートを下げる。
【０１４３】
図１１は、シェーパ１ｃにパケットが到着した場合の、パケット読出し処理とトークン供給レート決定処理とのフローの例を示す図である。シェーパ１ｃに到着するパケットのサイズはａと仮定される。また、図１１において、トークン供給レートは、単に、供給レートと表示される。
【０１４４】
到着パケットのサイズａとキュー長Ｑｌｅｎとの和がバッファサイズＱｍａｘより大きい場合には（ＯＰ６１：Ｎｏ）、バッファあふれが発生するので、到着パケットは廃棄される（ＯＰ７２）。
【０１４５】
到着パケットのサイズａとキュー長Ｑｌｅｎとの和がバッファサイズＱｍａｘ以下の場合には（ＯＰ６１：Ｙｅｓ）、バースト読出し管理部１２ｃは、到着パケットのバッファリングによって、キュー長が第１レート制御閾値以上の値に変化するか否かを判定する。バースト読出し管理部１２ｃは、バッファリング前のキュー長Ｑｌｅｎが第１レート制御閾値ＲＣｔｈ１未満、且つ、バッファリング後のキュー長Ｑｌｅｎ＋ａが第１レート制御閾値ＲＣｔｈ１以上第２レート制御閾値ＲＣｔｈ２未満か否かを判定する（ＯＰ６２）。なお、バースト読出し管理部１２ｃは、到着パケットのバッファリング前のキュー長を保持することができるものとする。
【０１４６】
ＯＰ６２の条件が満たされる場合には（ＯＰ６２：Ｙｅｓ）、到着パケットのバッファリングによってキュー長が第１レート制御閾値ＲＣｔｈ１未満の値から第１レート制御閾値ＲＣｔｈ１以上の値に変化することが示される。この場合には、バースト読出し管理部１２ｃは、トークン供給レートを予め定められたシェーピングレートよりも小さいレートＲ＿ｌｏｗに決定する（ＯＰ６３）。バースト読出し管理部１２ｃは、トークン供給レートを決定されたレート（この場合は、Ｒ＿ｌｏｗ）に設定するようにトークン供給部１３ｃに指示する。トークン供給部１３ｃは、指示された値（この場合は、Ｒ＿ｌｏｗ）にトークン供給レートを設定する。
【０１４７】
ＯＰ６２の条件が満たされない場合には（ＯＰ６２：Ｎｏ）、バースト読出し管理部１２ｃは、到着パケットのバッファリングによって、キュー長が第２レート制御閾値ＲＣｔｈ２以上の値に変化するか否かを判定する（ＯＰ６４）。すなわち、バースト読出し管理部１２ｃは、到着パケットのバッファリング前のキュー長Ｑｌｅｎが第２レート制御閾値ＲＣｔｈ２未満の値であり、且つ、バッファリング後のキュー長Ｑｌｅｎ＋ａが第２レート制御閾値ＲＣｔｈ２以上の値であるか否かを判定する。
【０１４８】
ＯＰ６４の条件が満たされる場合には（ＯＰ６４：Ｙｅｓ）、到着パケットのバッファリングによってキュー長が第２レート制御閾値ＲＣｔｈ２未満の値から第２レート制御閾値ＲＣｔｈ２以上の値に変化することが示される。この場合、バースト読出し管理部１２ｃは、トークン供給レートをシェーピングレートに決定する（ＯＰ６５）。バースト読出
し管理部１２ｃは、トークン供給レートを決定されたレート（この場合は、シェーピングレート）に設定するようにトークン供給部１３ｃに指示する。トークン供給部１３ｃは、指示された値（この場合が、シェーピングレート）にトークン供給レートを設定する。
【０１４９】
以上より、バッファメモリ１６ｃは、第１レート制御閾値ＲＣｔｈ１及び第２レート制御閾値ＲＣｔｈ２によって、以下に示される３つの領域に区分けされる。
（領域１）０≦Ｑｌｅｎ＜ＲＣｔｈ１
（領域２）ＲＣｔｈ１≦Ｑｌｅｎ＜ＲＣｔｈ２
（領域３）ＲＣｔｈ２＜Ｑｌｅｎ≦Ｑｍａｘ
【０１５０】
到着パケットのバッファリングによってキュー長Ｑｌｅｎの属する領域が領域１から領域２に変更した場合には（ＯＰ６２：Ｙｅｓ）、トークン供給レートはＲ＿ｌｏｗに設定される（ＯＰ６３）。到着パケットのバッファリングによってキュー長Ｑｌｅｎの属する領域が領域２から領域３に変更した場合には（ＯＰ６４：Ｙｅｓ）、トークン供給レートはシェーピングレートに設定される（ＯＰ６５）。
【０１５１】
ＯＰ６２、ＯＰ６４の条件が満たされない場合には、到着パケットがバッファリングされてもキュー長Ｑｌｅｎの属する領域に変更がないことが示される。この場合、バースト読出し管理部１２ｃは、トークン供給レートを変更せずに維持する（ＯＰ６６）。
【０１５２】
到着パケットがバッファリングされるとキュー長Ｑｌｅｎは、到着パケットのサイズａが加算された値になり（ＯＰ６７）、パケット読出し処理が行われる。図１１に示されるＯＰ６７〜ＯＰ７１ｂのパケット読出し処理は、図５のＯＰ１２〜ＯＰ１６ｂの処理とそれぞれ同様であるため、説明は省略される。
【０１５３】
ＯＰ６２において、キュー長が第１レート制御閾値ＲＣｔｈ１未満から第１レート制御閾値ＲＣｔｈ１以上第２レート制御閾値ＲＣｔｈ２未満へと変化した際に、トークン供給レートがシェーピングレートより小さいレートに変更される。これによって、キュー長の増加が加速され、より迅速に平衡状態を導くことができる。ただし、キュー長の増加が加速されることによって、バッファあふれの可能性が高くなる。そこで、ＯＰ６４において、キュー長が第２レート制御閾値ＲＣｔｈ２未満から第２レート制御閾値ＲＣｔｈ２以上へと変化した際に、シェーパ１ｃは、出力レートをシェーピングレートに戻し、キュー長の増加を回避する。なお、トークン供給時のパケット読出し処理については、トークンの供給によってキュー長が変化することはないので、第１実施形態と同様である。
【０１５４】
パケットの到着の他にも、パケットの読出しによってもキュー長は変化する。例えば、パケットの読出しによって、キュー長が第１レート制御閾値ＲＣｔｈ１以上から第１レート制御閾値ＲＣｔｈ１未満へと変化した場合、トークン供給レートがシェーピングレートよりも低いレートＲ＿ｌｏｗのままでは無用なスループット低下を引き起こす可能性がある。したがって、バースト読出し管理部１２ｃは、パケットが読み出された後に、キュー長が第１レート制御閾値ＲＣｔｈ１未満に変化した場合には、トークン供給レートをシェーピングレートに戻す。
【０１５５】
図１２は、シェーパ１ｃからのパケット読出し終了後のトークン供給レート決定処理のフローの例を示す図である。図１２においても、トークン供給レートは、単に、供給レートと表示される。
【０１５６】
バースト読出し管理部１２ｃは、パケット読出しによってキュー長Ｑｌｅｎが第１レート制御閾値ＲＣｔｈ１未満になったか否かを判定する。すなわち、バースト読出し管理部１２ｃは、パケット読出し後のキュー長Ｑｌｅｎが第１レート制御閾値ＲＣｔｈ１未満で
あるか否かを判定する（ＯＰ８１）。
【０１５７】
パケット読出し後のキュー長Ｑｌｅｎが第１レート制御閾値ＲＣｔｈ１未満である場合には（ＯＰ８１：Ｙｅｓ）、バースト読出し管理部１２ｃは、トークン供給レートをシェーピングレートの値に決定する（ＯＰ８２）。バースト読出し管理部１２ｃは、トークン供給レートを決定されたレート（この場合は、シェーピングレート）に設定するようにトークン供給部１３ｃに指示する。トークン供給部１３ｃは、指示された値（この場合は、シェーピングレート）にトークン供給レートを設定する。
【０１５８】
パケット読出し後のキュー長Ｑｌｅｎが第１レート制御閾値ＲＣｔｈ１以上である場合には（ＯＰ８１：Ｎｏ）、トークン供給レートは変更されず、処理が終了する。
【０１５９】
第３実施形態のシェーパ１ｃは、キューが増加傾向にあるときに、トークン供給レートをシェーピングレートよりも下げ、キュー長の増加を加速させる。これによって、平衡状態をより早く引き起こすことができ、将来のバーストの発生に備えることができる。
【０１６０】
第３実施形態において、バッファメモリ１６ｃには、２つのレート制御閾値が設定されたが、これに限られるものではなく、２つ以上のレート制御閾値を設定し、より細かな出力レートの制御を行うことも可能である。
【０１６１】
＜その他＞
第１〜第３実施形態のシェーパは、ＬＳＩの機能として電子回路によって実現されるのみならず、上述のトークンバケットを用いたシェーピングプログラムのＣＰＵによる実行によっても実現可能である。
【符号の説明】
【０１６２】
１，１ｂ，１ｃ          シェーパ
１１，１１ｃ            キュー長監視部
１２，１２ｂ，１２ｃ    バースト読出し管理部
１３，１３ｃ            トークン供給部
１４，１４ｂ            トークンバケット
１５                    読出し制御部
１６，１６ｂ，１６ｃ    バッファメモリ
１００                  パケット装置
１１０                  管理モジュール
１２０                  スイッチファブリック
１３０                  インターフェースカード
１３１                  ＣＰＵ
１３２                  ＴＭ  ＬＳＩ
１３３                  ＭＡＣ／ＰＨＹ  ＬＳＩ
１３４                  ＳＰＦ
１３５                  外部メモリ
【図１】
0005445271.tif 000002
【図２】
0005445271.tif 000003
【図３】
0005445271.tif 000004
【図４】
0005445271.tif 000005
【図５】
0005445271.tif 000006
【図６Ａ】
0005445271.tif 000007
【図６Ｂ】
0005445271.tif 000008
【図６Ｃ】
0005445271.tif 000009
【図６Ｄ】
0005445271.tif 000010
【図６Ｅ】
0005445271.tif 000011
【図７】
0005445271.tif 000012
【図８】
0005445271.tif 000013
【図９】
0005445271.tif 000014
【図１０】
0005445271.tif 000015
【図１１】
0005445271.tif 000016
【図１２】
0005445271.tif 000017
【図１３Ａ】
0005445271.tif 000018
【図１３Ｂ】
0005445271.tif 000019
【図１４】
0005445271.tif 000020
【図１５】
0005445271.tif 000021
【図１６】
0005445271.tif 000022
【図１７】
0005445271.tif 000023
【図１８Ａ】
0005445271.tif 000024
【図１８Ｂ】
0005445271.tif 000025
【図１８Ｃ】
0005445271.tif 000026
【図１８Ｄ】
0005445271.tif 000027
【図１８Ｅ】
0005445271.tif 000028