JP5365415B2 - パケット中継装置および輻輳制御方法 - Google Patents

Description

本発明はパケット中継装置および輻輳制御方法に関する。

パケット通信では、パケットを中継する中継装置において輻輳が発生することがある。輻輳制御方法の１つとして、テイルドロップ方式がある。テイルドロップ方式では、中継装置が備えるキューに送信待ちのパケットを可能な限り格納する。そして、キューが満杯になると、キューに再び空きができるまで後から到着するパケットを廃棄する。ここで、パケットを送信する送信装置の中には、宛先の受信装置からパケットを受信した旨の確認応答がないと、送信レートを低下させる制御（例えば、スロースタートアルゴリズム）を行うものがある。よって、中継装置でパケットを廃棄すると、輻輳の解消が期待できる。

しかし、テイルドロップ方式では、キューが満杯になると、送信量の多い送信装置からのパケットも送信量の少ない装置からのパケットも含めて、後から到着するパケットを無条件に廃棄する。そのため、複数の送信装置が一斉に送信レートを低下させ、トラヒックが一時的に極端に低下する現象（グローバルシンクロナイゼーション）が発生しやすい。グローバルシンクロナイゼーションが発生すると、ネットワークの利用率が低下する。

これに対し、他の輻輳制御方法として、ランダム初期検知（ＲＥＤ：Random Early Detection）方式がある。ＲＥＤ方式では、中継装置が備えるキューが満杯になる前に、到着するパケットを確率的に廃棄する。パケットを確率的に廃棄した場合、送信量の多い送信装置からのパケットが、送信量の少ない装置からのパケットよりも廃棄されやすくなる。よって、ＲＥＤ方式では、グローバルシンクロナイゼーションの発生を抑制できる。

なお、ＲＥＤ方式の輻輳制御について、輻輳が発生すると、到着したセルが最終セルか否か判定し、最終セル以外のセルを任意の確率で廃棄する技術が提案されている。また、キュー長の分布情報を取得し、分布情報に応じてパケット廃棄を行うことで、データ蓄積状況が廃棄制御により反映されるようにした技術が提案されている。

特開２００１−１１１５５６号公報 特開２００４−１０４４１７号公報

ところで、パケットを中継する中継装置には、ＱｏＳ（Quality of Service）制御のため、送信待ちのパケットを格納するキューを複数備えるものがある。複数のキューを備えることで、ネットワークを利用するユーザや通信の種類に応じて、パケットの送信順序を優先付けすることができる。

しかし、前述のＲＥＤ方式のような輻輳制御方法では、パケットの廃棄制御はキュー単位で行われていた。従って、複数のキューそれぞれに対してパケット廃棄のための回路を設けた場合、回路規模が大きくなるという問題がある。一方、回路規模の制約から、一部のキューのみにパケット廃棄のための回路を割り当てた場合、すなわち、パケット廃棄の制御の対象外であるキューが存在する場合、グローバルシンクロナイゼーションの抑制が不十分になるおそれがあるという問題がある。

本発明はこのような点に鑑みてなされたものであり、複数のキューに対するパケット廃棄の制御を効率的に実現するパケット中継装置および輻輳制御方法を提供することを目的とする。

上記課題を解決するためにパケット中継装置が提供される。このパケット中継装置は、複数のキューと輻輳検出部と振分部と廃棄部とを有する。複数のキューは、送信待ちのパケットを格納する。輻輳検出部は、複数のキューの輻輳状態を検出し、輻輳状態に基づいて複数のキューから１またはそれ以上のキューを選択する。振分部は、複数のキューに格納される前の一連のパケットから、輻輳検出部で選択された１またはそれ以上のキュー宛てのパケットを分離する。廃棄部は、振分部で分離された１またはそれ以上のキュー宛てのパケットを、所定の確率で廃棄する。

また、上記課題を解決するために輻輳制御方法が提供される。この輻輳制御方法では、送信待ちのパケットを格納する複数のキューの輻輳状態を検出し、輻輳状態に基づいて複数のキューから１またはそれ以上のキューを選択する。複数のキューに格納される前の一連のパケットから、選択した１またはそれ以上のキュー宛てのパケットを分離する。分離した１またはそれ以上のキュー宛てのパケットを所定の確率で廃棄する。

上記パケット中継装置および輻輳制御方法によれば、複数のキューに対するパケット廃棄の制御が効率的に実現される。

第１の実施の形態のパケット中継装置を示す図である。 第２の実施の形態の通信システムを示す図である。 第２の実施の形態の中継装置を示す図である。 キュー管理部の詳細を示す図である。 廃棄制御部の詳細を示す図である。 シェーパテーブルのデータ構造例を示す図である。 ＲＥＤ回路テーブルのデータ構造例を示す図である。 平均キュー長と廃棄率との関係を示すグラフである。 輻輳発生時の処理を示すフローチャートである。 ＲＥＤ回路適用の処理を示すフローチャートである。 輻輳解消時の処理を示すフローチャートである。 パケットの振り分け例を示す第１の図である。 パケットの振り分け例を示す第２の図である。 パケットの振り分け例を示す第３の図である。 ＲＥＤ回路とキューとの対応付け例を示す図である。

以下、本実施の形態を図面を参照して詳細に説明する。
［第１の実施の形態］
図１は、第１の実施の形態のパケット中継装置を示す図である。第１の実施の形態に係るパケット中継装置１は、ネットワークにおいてパケットの転送を行う。パケット中継装置１は、例えば、ルータやスイッチなどの通信装置である。パケット中継装置１が扱うパケットは、ＩＰ（Internet Protocol）パケットに限られず、通信のために区切られた一定のデータ単位であればよい。パケット中継装置１は、複数のキュー１ａ，１ｂ，１ｃ、輻輳検出部１ｄ、振分部１ｅおよび廃棄部１ｆを有する。

キュー１ａ，１ｂ，１ｃは、送信待ちのパケットを格納する。キュー１ａ，１ｂ，１ｃは、例えば、ユーザやＱｏＳクラスに対応して設けられている。送信するパケットは出力優先度が判定され、キュー１ａ，１ｂ，１ｃの何れかの末尾に挿入される。キュー１ａ，１ｂ，１ｃに格納されたパケットは、先頭から順次取り出されて送信される。送信側には、例えば、キュー１ａ，１ｂ，１ｃのパケットの送信順序を制御するスケジューラや、帯域に応じて送信タイミングを制御するシェーパが設けられる。複雑なＱｏＳ制御を実現するため、多段のシェーパを設けてもよい。

輻輳検出部１ｄは、キュー１ａ，１ｂ，１ｃについての輻輳状態を検出する。そして、検出した輻輳状態に基づいて、キュー１ａ，１ｂ，１ｃからパケット廃棄の対象とする１またはそれ以上のキューを選択する。輻輳状態は、シェーパ単位で検出してもよい。例えば、各シェーパのパケットの通過状況（例えば、使用率）を監視する方法や、シェーパ毎にそのシェーパにパケットを出力するキューにおけるパケットの滞留状況（例えば、直近の一定時間の平均キュー長）を監視する方法が考えられる。その場合、輻輳と判断されたシェーパにパケットを出力しているキューを、パケット廃棄の対象として選択する。

振分部１ｅは、キュー１ａ，１ｂ，１ｃに格納される前の一連のパケットを取得する。そして、一連のパケットから、輻輳検出部１ｄで選択された１またはそれ以上のキュー、すなわち、パケット廃棄の対象とするキュー宛てのパケットを分離する。宛先キューまたは出力優先度を示す情報がパケットに付加されている場合、その情報に基づいて分離するか否か判断すればよい。分離されたパケットは、廃棄部１ｆに振り分けられる。一方、それ以外のパケットは、キュー１ａ，１ｂ，１ｃの何れかに格納される。

廃棄部１ｆは、振分部１ｅで分離されたパケットを取得し、取得したパケットを一定の廃棄率で廃棄する。廃棄されずに残ったパケットは、キュー１ａ，１ｂ，１ｃの何れかに格納される。廃棄率は、対象のキューにおけるパケットの滞留状況（例えば、直近の一定時間の平均キュー長）に応じて決まる確率を用いてもよい。複数のキューがパケット廃棄の対象である場合、それらキューについてのキュー長の合計値や最大値に基づいて、廃棄率を算出してもよい。なお、パケット中継装置１は、廃棄部１ｆを含む複数の廃棄部を備えていてもよい。その場合、廃棄部毎に異なる廃棄率を適用できる。

このようなパケット中継装置１によれば、輻輳検出部１ｄにより、キュー１ａ，１ｂ，１ｃについての輻輳状態が検出され、輻輳状態に基づいてキュー１ａ，１ｂ，１ｃから１またはそれ以上のキューが選択される。振分部１ｅにより、キュー１ａ，１ｂ，１ｃに格納される前の一連のパケットから、輻輳検出部１ｄで選択された１またはそれ以上のキュー宛てのパケットが分離される。廃棄部１ｆにより、振分部１ｅで分離されたパケットが所定の確率で廃棄される。キュー１ａ，１ｂ，１ｃには、振分部１ｅで分離されなかったパケットおよび廃棄部１ｆで廃棄されなかったパケットが格納される。

例えば、キュー１ａ，１ｂ，１ｃのうちキュー１ｂ，１ｃに多くのパケットが滞留しており、輻輳の原因になっているとする。そして、輻輳検出部１ｄにより、パケット廃棄の対象としてキュー１ｂ，１ｃが選択されたとする。すると、振分部１ｅにより、キュー１ｂ，１ｃ宛てのパケットが廃棄部１ｆに振り分けられ、廃棄部１ｆにより、キュー１ｂ，１ｃ宛てのパケットが所定の確率で廃棄される。

これにより、廃棄部に対し１またはそれ以上のキューを動的に割り当てることができ、複数のキューに対するパケット廃棄の制御を効率的に実現することができる。すなわち、全てのキューについて１対１に対応する廃棄部を固定的に設ける方法と比べ、回路規模を抑制することができる。また、一部のキューにのみ対応する廃棄部を固定的に設ける方法と比べ、より多くのキューに対してパケット廃棄の処理を適用でき、グローバルシンクロナイゼーションによる通信品質の劣化を抑制できる。

また、廃棄部とキューとを１対多に固定的に対応付ける方法と比べ、通信品質の劣化を抑制できる。すなわち、廃棄部に対して複数のキューが固定的に対応付けられていると、一部のキューのみで輻輳が発生した場合に、輻輳に関与していない他のキューもパケット廃棄の対象となってしまい、通信品質が劣化するおそれがある。これに対し、パケット中継装置１によれば、廃棄部と１またはそれ以上のキューとの対応付けが動的であるため、過剰なパケット廃棄による通信品質の劣化を抑制できる。

特に、シェーパ単位で輻輳状態を検出し、輻輳しているシェーパに対応する複数のキューをパケット廃棄の対象として選択する場合は、シェーパの輻輳に関与していると考えられるキューを適切にグループ化できる。すなわち、輻輳に関与している可能性の高い複数のキューを纏めて１つの仮想的なキューとして扱うことができる。これにより、廃棄部と複数のキューとの対応付けを効率的に行うことができる。

［第２の実施の形態］
図２は、第２の実施の形態の通信システムを示す図である。第２の実施の形態に係る通信システムは、パケット通信が可能なシステムである。この通信システムは、中継装置１０，１０ａ，１０ｂ、端末装置２０，２０ａおよびネットワーク３０，３０ａを含む。

中継装置１０，１０ａ，１０ｂは、パケットの転送を行う通信装置である。中継装置１０，１０ａ，１０ｂとしては、例えば、ルータやスイッチを用いることができる。中継装置１０は、中継装置１０ａ，１０ｂと接続されている。中継装置１０ａは、ネットワーク３０に接続され、中継装置１０ｂは、ネットワーク３０ａに接続されている。なお、中継装置１０，１０ａ，１０ｂが扱うパケットは、通信のために区切られた一定のデータ単位であればよく、ＩＰパケットが含まれる。

端末装置２０，２０ａは、パケットを送受信する通信端末装置である。端末装置２０，２０ａとしては、例えば、通信インタフェースを備えたコンピュータを用いることができる。ＴＣＰ（Transmission Control Protocol）の通信を行う場合、端末装置２０，２０ａは、ＴＣＰセッションを終端する。端末装置２０は、ネットワーク３０に接続されており、端末装置２０ａは、ネットワーク３０ａに接続されている。端末装置２０と端末装置２０ａとは、ネットワーク３０−中継装置１０ａ−中継装置１０−中継装置１０ｂ−ネットワーク３０ａという経路でパケット通信を行うことができる。

図３は、第２の実施の形態の中継装置を示す図である。中継装置１０は、複数の受信部１１，１１ａ，・・・、パケットスイッチ１２および複数の送信部１３，１３ａ，・・・を有する。中継装置１０ａ，１０ｂも、中継装置１０と同様の構成によって実現できる。

受信部１１，１１ａ，・・・は、中継装置１０が備える通信ポートに到着した受信パケットを取得し、各種の受信処理を行ってパケットスイッチ１２に出力する。受信部は通信ポート毎に設けることができる。例えば、受信部１１は、中継装置１０ａと接続された通信ポートに到着した受信パケットを処理し、受信部１１ａは、中継装置１０ｂと接続された通信ポートに到着した受信パケットを処理する。

受信処理には、フロー検出、帯域監視、マーキングなどの処理が含まれる。フロー検出では、プロトコル種別、ＩＰアドレス、ＴＣＰポート番号などのヘッダ情報に基づいてフローを検出する。帯域監視では、フロー毎に使用帯域を監視する。マーキングでは、帯域監視の結果に応じて、ヘッダ内のユーザ優先度を示す値を書き換える。例えば、所定の帯域を超えたフローに対してペナルティを与え、ユーザ優先度を下げる。

パケットスイッチ１２は、パケットを出力先の通信ポートに振り分ける内部スイッチである。パケットスイッチ１２は、受信部１１，１１ａ，・・・からパケットを取得し、ヘッダ情報に基づいて出力先の通信ポートを判断する。そして、出力先の通信ポートに対応する送信部にパケットを出力する。

送信部１３，１３ａ，・・・は、パケットスイッチ１２からパケットを取得し、各種の送信処理を行って通信ポートに出力する。送信部は通信ポート毎に設けることができる。例えば、送信部１３は、中継装置１０ａと接続された通信ポートから出力するパケットを処理し、送信部１３ａは、中継装置１０ｂと接続された通信ポートから出力するパケットを処理する。

送信処理には、優先度決定、廃棄制御、出力制御などの処理が含まれる。優先度決定では、パケットの出力優先度が判断され、そのパケットを格納するキューが指定される。廃棄制御では、キューの状態に応じてパケットを廃棄する。出力制御では、複数のキューに格納されたパケットの出力順序の制御（スケジューリング）や、割り当てられた帯域に応じた出力タイミングの制御（シェーピング）を行う。

ここで、送信部１３は、廃棄制御部１００とキュー管理部２００を有する。廃棄制御部１００は、ＲＥＤ方式により送信するパケットを確率的に廃棄する。キュー管理部２００は、複数のキューを備え、これらキューに格納されたパケットのスケジューリングおよびシェーピングを行う。なお、送信部１３ａを含む他の送信部も、送信部１３と同様の構成で実現できる。

以下、廃棄制御部１００とキュー管理部２００の詳細を説明する。なお、第２の実施の形態では、ＲＥＤ方式でパケット廃棄を行う場合を説明するが、ユーザ優先度などの情報を用いて、ＷＲＥＤ（Weighted RED）方式でパケット廃棄を行ってもよい。

図４は、キュー管理部の詳細を示す図である。キュー管理部２００は、分離部２１０、キュー２２０，２２０ａ，２２０ｂ，２２０ｃ，２２０ｄ，２２０ｅ、シェーパ２３０，２３０ａ，２３０ｂ，２３０ｃ，２３０ｄ，２３０ｅ，２５０，２５０ａ，２５０ｂ，２５０ｃ、スケジューラ２４０，２４０ａ，２４０ｂ，２４０ｃ、キュー監視部２６０およびシェーパ監視部２７０を有する。

分離部２１０は、廃棄制御部１００から取得するパケットを、キュー２２０，２２０ａ，２２０ｂ，２２０ｃ，２２０ｄ，２２０ｅの何れかに格納する。格納先のキューは、廃棄制御の前に行われる優先度決定において指定されている。ただし、分離部２１０が、パケットのヘッダ情報に基づいて格納先のキューを判断してもよい。

キュー２２０，２２０ａ，２２０ｂ，２２０ｃ，２２０ｄ，２２０ｅは、送信待ちのパケットを一時的に格納するＦＩＦＯ（First In First Out）型のバッファメモリである。第２の実施の形態では、一例として、キュー管理部２００に６個のキューが設けられている。これら複数のキューは、パケット出力の優先度が異なる。キュー２２０，２２０ａ，２２０ｂ，２２０ｃ，２２０ｄ，２２０ｅは、分離部２１０から取得するパケットを末尾に追加すると共に、格納されているパケットを先頭から順に出力する。

なお、キュー２２０，２２０ａ，２２０ｂ，２２０ｃ，２２０ｄ，２２０ｅは、物理的なキューでもよいし、論理的なキューでもよい。すなわち、各キューのために個別にメモリ装置を設けてもよいし、１つのメモリ装置のメモリ領域を複数に分割して、複数のキューを実現してもよい。後者の場合、設定に応じて、論理的なキューの数を増減させることも可能である。

シェーパ２３０，２３０ａ，２３０ｂ，２３０ｃ，２３０ｄ，２３０ｅ，２５０，２５０ａ，２５０ｂ，２５０ｃは、割り当てられた帯域に応じて、パケットの出力タイミングの制御（シェーピング）を行う。シェーピングにより、到着するパケット量の変動に対し、割り当てられた帯域の範囲内で出力するパケット量を平準化できる。各シェーパには予め帯域が割り当てられている。例えば、シェーパ２３０には１５Ｍｂｐｓ、シェーパ２３０ａには１０Ｍｂｐｓなどの帯域が割り当てられる。シェーパ２５０ｃに割り当てられた帯域が、通信ポートの帯域に対応する。

ここで、シェーパ２３０は、キュー２２０からパケットを取得してスケジューラ２４０ｃに出力する。シェーパ２３０ａ，２３０ｂは、それぞれキュー２２０ａ，２２０ｂからパケットを取得してスケジューラ２４０に出力する。シェーパ２３０ｃ，２３０ｄ，２３０ｅは、それぞれキュー２２０ｃ，２２０ｄ，２２０ｅからパケットを取得してスケジューラ２４０ａに出力する。

また、シェーパ２５０，２５０ａは、それぞれスケジューラ２４０，２４０ａからパケットを取得してスケジューラ２４０ｂに出力する。シェーパ２５０ｂは、スケジューラ２４０ｂからパケットを取得してスケジューラ２４０ｃに出力する。シェーパ２５０ｃは、スケジューラ２４０ｃからパケットを取得し、通信ポートから出力するパケットとする。このように、キュー管理部２００は、多段シェーパを備えている。多段シェーパを用いることで、複数のキューを用いた複雑なＱｏＳ制御に柔軟に対応できる。

シェーパ２３０は、トークン供給部２３１、トークンバケット２３２および通過制御部２３３を有する。シェーパ２３０ａ，２３０ｂ，２３０ｃ，２３０ｄ，２３０ｅ，２５０，２５０ａ，２５０ｂ，２５０ｃも、シェーパ２３０と同様の構成によって実現できる。

トークン供給部２３１は、シェーパ２３０に割り当てられた帯域に応じた時間間隔で、トークンと呼ばれるデータを継続的に生成する。そして、生成したトークンを、トークンバケット２３２の末尾に順次追加する。トークンバケット２３２は、トークンを格納するＦＩＦＯ型のバッファメモリである。格納されたトークンは、先頭から順に取り出すことができる。

通過制御部２３３は、トークンバケット２３２に格納されたトークンを用いて、パケットを通過させるか否かを制御する。具体的には、トークンバケットの先頭からトークンを１つ取り出す毎にパケットを１つ通過させる。トークンバケットが空でありトークンを取得できない間は、パケットを通過させることができない。これにより、パケットの通過レートを制限することができる。

スケジューラ２４０，２４０ａ，２４０ｂ，２４０ｃは、前段の複数のシェーパから入力されるパケットの出力順序の制御（スケジューリング）を行う。すなわち、スケジューラ２４０は、シェーパ２３０ａ，２３０ｂからのパケットをスケジューリングする。スケジューラ２４０ａは、シェーパ２３０ｃ，２３０ｄ，２３０ｅからのパケットをスケジューリングする。スケジューラ２４０ｂは、シェーパ２５０，２５０ａからのパケットをスケジューリングする。スケジューラ２４０ｃは、シェーパ２３０，２５０ｂからのパケットをスケジューリングする。

スケジューリングアルゴリズムは、スケジューラ毎に設定できる。例えば、スケジューラ２４０ａは、重み付きラウンドロビン（ＷＲＲ：Weighted Round Robin）を使用する。ＷＲＲでは、複数のシェーパそれぞれが所定の重みに応じた確率で選択される。スケジューラ２４０ｂは、ラウンドロビン（ＲＲ：Round Robin）を使用する。ＲＲでは、複数のシェーパが所定の順番で均等に選択される。スケジューラ２４０ｃは、完全優先（ＳＰ：Strict Priority）を使用する。ＳＰでは、高優先度のシェーパを優先して選択し、高優先度のシェーパからパケットの入力ない場合のみ低優先度のシェーパを選択できる。

キュー監視部２６０は、キュー２２０，２２０ａ，２２０ｂ，２２０ｃ，２２０ｄ，２２０ｅそれぞれについて、滞留しているパケットの量、すなわち、キュー長を監視する。そして、キュー監視部２６０は、キュー長を示す情報を、廃棄制御部１００に報告する。

シェーパ監視部２７０は、シェーパ２３０，２３０ａ，２３０ｂ，２３０ｃ，２３０ｄ，２３０ｅ，２５０，２５０ａ，２５０ｂ，２５０ｃそれぞれについて、シェーパの使用率を監視する。シェーパの使用率は、トークンバケットに格納されているトークン量に基づいて判断することができる。例えば、トークン量が一定時間以上連続して所定の閾値を下回っている場合に、使用率１００％と判断する方法が考えられる。そして、シェーパ監視部２７０は、シェーパの使用率を示す情報を、廃棄制御部１００に報告する。

図５は、廃棄制御部の詳細を示す図である。廃棄制御部１００は、振分部１１０、ＲＥＤ回路１２０，１２０ａ，１２０ｂ、集約部１３０、輻輳検出部１４０および記憶部１５０を有する。

振分部１１０は、入力されたパケットが、キュー２２０，２２０ａ，２２０ｂ，２２０ｃ，２２０ｄ，２２０ｅの何れに格納されるパケットであるか特定する。そして、格納先のキューに応じて、パケットを、ＲＥＤ回路１２０，１２０ａ，１２０ｂおよび集約部１３０の何れかに振り分ける。ＲＥＤ回路１２０，１２０ａ，１２０ｂとキューとの対応関係は、輻輳検出部１４０から通知される。輻輳検出部１４０から通知されていないキュー宛てのパケットは、集約部１３０に振り分けられる。

格納先のキューは、廃棄制御部１００にパケットが入力される前に行われる優先度決定において指定されている。ただし、振分部１１０が、パケットのヘッダ情報に基づいて格納先のキューを判断してもよい。

ＲＥＤ回路１２０，１２０ａ，１２０ｂは、振分部１１０から取得するパケットを確率的に廃棄し、廃棄しなかったパケットを集約部１３０に出力する。すなわち、取得する一連のパケットから、ランダムにパケットを間引く。

初期状態では、ＲＥＤ回路１２０，１２０ａ，１２０ｂは、振分部１１０からパケットが振り分けられず、待機状態にある。すなわち、空きＲＥＤ回路がストックされている。その後、輻輳検出部１４０の制御によりパケットが振り分けられると、ＲＥＤ回路１２０，１２０ａ，１２０ｂは、パケット廃棄を開始する。また、パケットの振り分けが停止すると、パケット廃棄を停止する。なお、第２の実施の形態では３個のＲＥＤ回路を設けたが、回路規模を考慮した上で、任意の数のＲＥＤ回路を設けてよい。

ＲＥＤ回路１２０は、平均キュー長算出部１２１、廃棄率算出部１２２およびパケット廃棄部１２３を有する。ＲＥＤ回路１２０ａ，１２０ｂも、ＲＥＤ回路１２０と同様の構成によって実現できる。

平均キュー長算出部１２１は、ＲＥＤ回路１２０を適用する１またはそれ以上のキューが輻輳検出部１４０から通知されると、輻輳検出部１４０経由で、通知されたキューについてのキュー長の情報を取得し始める。そして、取得したキュー長の情報を用いて、直近の一定時間の平均キュー長を算出し、算出した平均キュー長を廃棄率算出部１２２に通知する。平均キュー長の算出は、例えば、パケット廃棄の開始時点と、その後の定期的なタイミングで実行される。

ここで、ＲＥＤ回路１２０を適用するキューが複数ある場合、各キューのキュー長に基づいて算出される統計値を、複数のキューを１つのキューと見なした場合の仮想的なキュー長と定義することができる。例えば、各キューのキュー長の合計値を、仮想的なキュー長と定義できる。この方法では、複数のキューに滞留しているパケット量を精度よく把握することができる。また、各キューのキュー長の最大値を、仮想的なキュー長と定義することもできる。この方法では、回路の簡素化や処理負荷の軽減を図ることができる。

廃棄率算出部１２２には、平均キュー長とパケット廃棄率との対応関係が予め設定されている。廃棄率算出部１２２は、平均キュー長算出部１２１から平均キュー長が通知されると、平均キュー長に対応する廃棄率を算出する。そして、算出した廃棄率を、パケット廃棄部１２３に通知する。また、パケット廃棄の開始後、平均キュー長が更新されると、新たな平均キュー長に対応する廃棄率をパケット廃棄部１２３に通知する。

パケット廃棄部１２３は、廃棄率算出部１２２から廃棄率が通知されると、通知された廃棄率で振分部１１０から取得するパケットを廃棄する。すなわち、振分部１１０から取得する一連のパケットから、一定の廃棄率でランダムにパケットを間引く。そして、廃棄しなかったパケットを集約部１３０に出力する。また、パケット廃棄の開始後、廃棄率が更新されると、新たな廃棄率でパケット廃棄を行う。

集約部１３０は、振分部１１０およびＲＥＤ回路１２０，１２０ａ，１２０ｂから取得するパケットを、１つのストリームに集約する。そして、集約した一連のパケットをキュー管理部２００に出力する。

輻輳検出部１４０は、キュー２２０，２２０ａ，２２０ｂ，２２０ｃ，２２０ｄ，２２０ｅに対するＲＥＤ回路１２０，１２０ａ，１２０ｂの適用を制御する。具体的には、輻輳検出部１４０は、キュー管理部２００のシェーパ監視部２７０から、各シェーパの使用率の情報を継続的に取得する。使用率が所定の閾値を超えた場合、そのシェーパが輻輳していると判断する。使用率の閾値は、全シェーパに共通の値を用いてもよいし、シェーパ毎に異なる値を用いてもよい。

あるシェーパで輻輳が発生した場合、輻輳検出部１４０は、そのシェーパに対応するキュー、すなわち、そのシェーパにパケットを流入させている１またはそれ以上のキューを特定すると共に、適用するＲＥＤ回路を選択する。そして、選択したＲＥＤ回路にキューを通知すると共に、振分部１１０にキューとＲＥＤ回路との対応関係を通知する。また、輻輳検出部１４０は、キュー管理部２００のキュー監視部２６０からキュー長の情報を継続的に取得し、選択したＲＥＤ回路に出力する。

ここで、所定のキューを、パケット廃棄の適用対象外として設定しておくことも可能である。例えば、高優先度のキューを適用対象外に設定することが考えられる。その場合、輻輳検出部１４０は、適用対象外のキューを除いて、振分部１１０および選択したＲＥＤ回路にキューを通知する。また、輻輳検出部１４０は、あるシェーパで輻輳が解消した場合、そのシェーパに対応するキューと適用されているＲＥＤ回路とを特定し、振分部１１０にキューとＲＥＤ回路との対応付けの解除を指示する。

このように、シェーパの使用率の情報に基づいて輻輳検出を行うことで、輻輳の発生および解消を迅速に検出できる。一方、キュー長の情報に基づいて輻輳検出を行うことも可能である。その場合、輻輳検出部１４０は、シェーパ毎にそのシェーパに対応する１またはそれ以上のキューのキュー長の合計値を算出する。そして、キュー長の合計値が所定の閾値を超えた場合、そのシェーパが輻輳していると判断する。この方法では、キュー管理部２００にシェーパ監視部２７０を設けなくてもよい。よって、回路規模を抑制することができる。

記憶部１５０は、輻輳検出部１４０の処理に使用される各種の情報を記憶する。記憶部１５０としては、例えば、不揮発性メモリを使用する。記憶部１５０に記憶される情報には、各シェーパに対応するキューを示す情報や、ＲＥＤ回路１２０，１２０ａ，１２０ｂを適用しているキューを示す情報が含まれる。後者の情報は、輻輳検出部１４０によって適宜書き換えられる。

図６は、シェーパテーブルのデータ構造例を示す図である。図６に示すシェーパテーブル１５１は、廃棄制御部１００の記憶部１５０に記憶されている。シェーパテーブル１５１は、シェーパＩＤ（IDentification）、上流シェーパ、下流シェーパ、キューおよび輻輳フラグを示す項目を含む。各項目の横方向に並べられた情報同士が互いに関連付けられて、各シェーパについてのシェーパ情報を構成する。

シェーパＩＤの項目には、シェーパを識別するための識別情報が設定される。上流シェーパの項目には、そのシェーパの上流側（キュー２２０，２２０ａ，２２０ｂ，２２０ｃ，２２０ｄ，２２０ｅに近い側）に接続された他のシェーパの識別情報が設定される。下流シェーパの項目には、そのシェーパの下流側（出力先の通信ポートに近い側）に接続された他のシェーパの識別情報が設定される。キューの項目には、そのシェーパに直接接続されているキューの識別情報が設定される。輻輳フラグの項目には、輻輳しているか否かを示す値が設定される。輻輳している場合は１、輻輳していない場合は０が設定される。

例えば、シェーパＩＤ＝Ｓ７、上流シェーパ＝Ｓ２，Ｓ３、下流シェーパ＝Ｓ９、輻輳フラグ＝０というシェーパ情報が、シェーパテーブル１５１に格納されている。これは、シェーパ２５０の上流側にシェーパ２３０ａ，２３０ｂが接続されると共に、下流側にシェーパ２５０ｂが接続されており、シェーパ２５０が輻輳していないことを示している。なお、輻輳フラグの項目の情報は、輻輳検出部１４０によって適宜書き換えられる。

図７は、ＲＥＤ回路テーブルのデータ構造例を示す図である。図７に示すＲＥＤ回路テーブル１５２は、廃棄制御部１００の記憶部１５０に記憶されている。ＲＥＤ回路テーブル１５２は、回路ＩＤ、シェーパおよびキューを示す項目を含む。各項目の横方向に並べられた情報同士が互いに関連付けられて、各ＲＥＤ回路についてのＲＥＤ回路情報を構成する。

回路ＩＤの項目には、ＲＥＤ回路１２０，１２０ａ，１２０ｂを識別するための識別情報が設定される。シェーパの項目には、そのＲＥＤ回路が適用されているシェーパ、すなわち、そのＲＥＤ回路が輻輳を解消しようとしているシェーパの識別情報が設定される。キューの項目には、そのＲＥＤ回路が適用されているキューの識別情報が設定される。

例えば、回路ＩＤ＝ＲＥＤ３、シェーパ＝Ｓ８、キュー＝Ｑ４，Ｑ５，Ｑ６というＲＥＤ回路情報が、ＲＥＤ回路テーブル１５２に格納される。これは、シェーパ２５０ａの輻輳を解消するためにＲＥＤ回路１２０ｂが使用されており、ＲＥＤ回路１２０ｂがキュー２２０ｃ，２２０ｄ，２２０ｅ宛てのパケットを処理することを示している。なお、シェーパおよびキューの項目の情報は、輻輳検出部１４０によって適宜書き換えられる。

図８は、平均キュー長と廃棄率との関係を示すグラフである。ＲＥＤ回路１２０の廃棄率算出部１２２は、図８に示すようなグラフ（確率曲線）に従って、平均キュー長算出部１２１で算出された平均キュー長から廃棄率を決定する。ＲＥＤ回路１２０ａ，１２０ｂにおいても同様の制御が行われる。

具体的には、平均キュー長が閾値Ｔmin以下のときは、廃棄率が０に設定される。平均キュー長が閾値Ｔminより大きく閾値Ｔmax（Ｔmin＜Ｔmax）未満のときは、廃棄率が平均キュー長に比例する確率Ｐ（０＜Ｐ＜Ｐmax＜１）に設定される。平均キュー長が閾値Ｔmaxのときは、廃棄率がＰmaxに設定される。平均キュー長が閾値Ｔmaxより大きいときは、廃棄率が１に設定される。

すなわち、平均キュー長が閾値Ｔmin以下のときは、入力されるパケットは廃棄されずに、全てＲＥＤ回路１２０，１２０ａ，１２０ｂを通過する。平均キュー長が閾値Ｔmaxより大きいときは、入力されるパケットは全て廃棄され、ＲＥＤ回路１２０，１２０ａ，１２０ｂを通過しない。平均キュー長が閾値Ｔminより大きく閾値Ｔmax以下のときは、入力されるパケットの一部がランダムに廃棄され、残りのパケットがＲＥＤ回路１２０，１２０ａ，１２０ｂを通過する。

なお、ＲＥＤ回路１２０，１２０ａ，１２０ｂは、キュー２２０，２２０ａ，２２０ｂ，２２０ｃ，２２０ｄ，２２０ｅの任意の組み合わせに対して、共通の確率曲線を使用してもよいし、組み合わせに応じて異なる確率曲線を使用してもよい。

図９は、輻輳発生時の処理を示すフローチャートである。以下、図９に示す処理をステップ番号に沿って説明する。
（ステップＳ１１）輻輳検出部１４０は、輻輳していないシェーパ、すなわち、シェーパテーブル１５１で輻輳フラグがＯＦＦ（０）であるシェーパを監視し、輻輳が発生したシェーパを検出する。輻輳検出部１４０は、例えば、使用率が所定の閾値を超えたシェーパを、輻輳が発生したと判断する。または、対応するキュー（そのシェーパにパケットを流入させているキュー）のキュー長の合計値が所定の閾値を超えたシェーパを、輻輳が発生したと判断する。

（ステップＳ１２）輻輳検出部１４０は、シェーパテーブル１５１において、ステップＳ１１で検出したシェーパの輻輳フラグを、ＯＦＦ（０）からＯＮ（１）に変更する。
（ステップＳ１３）輻輳検出部１４０は、シェーパテーブル１５１を検索し、ステップＳ１１で検出したシェーパの下流、すなわち、そのシェーパと通信ポートとの間に、輻輳しているシェーパが存在するか否か判断する。下流に輻輳しているシェーパがある場合、処理を終了する。輻輳しているシェーパがない場合、処理をステップＳ１４に進める。

（ステップＳ１４）輻輳検出部１４０は、シェーパテーブル１５１を検索し、ステップＳ１１で検出したシェーパの上流、すなわち、対応するキューとそのシェーパとの間に、輻輳しているシェーパが存在するか否か判断する。上流に輻輳しているシェーパがある場合、処理をステップＳ１５に進める。輻輳しているシェーパがない場合、処理をステップＳ１６に進める。

（ステップＳ１５）輻輳検出部１４０は、ＲＥＤ回路テーブル１５２を検索し、上流の輻輳しているシェーパに適用されているＲＥＤ回路を特定する。そして、特定したＲＥＤ回路を解放する。具体的には、輻輳検出部１４０は、ＲＥＤ回路テーブル１５２から、特定したＲＥＤ回路に対応付けられているシェーパの識別情報およびキューの識別情報を削除する。また、上流の輻輳しているシェーパに対応するキューと特定したＲＥＤ回路との対応付けを解除するよう、振分部１１０に指示する。なお、上流の輻輳しているシェーパが複数ある場合、シェーパ毎に処理を行う。

（ステップＳ１６）輻輳検出部１４０は、ＲＥＤ回路テーブル１５２を検索し、ＲＥＤ回路１２０，１２０ａ，１２０ｂのうち空きのＲＥＤ回路があるか否か判断する。シェーパの項目およびキューの項目が空欄であるＲＥＤ回路を、空きのＲＥＤ回路と判断することができる。空きのＲＥＤ回路がある場合、処理をステップＳ１７に進める。空きのＲＥＤ回路がない場合、処理を終了する。

（ステップＳ１７）輻輳検出部１４０は、ステップＳ１１で検出したシェーパを対象としてＲＥＤ回路を適用する。処理の詳細は後述する。
このようにして、廃棄制御部１００は、シェーパの使用状況またはキューの滞留状況に基づいて、シェーパ単位で輻輳状態を検出する。輻輳の発生したシェーパがあると、そのシェーパを対象としてＲＥＤ回路を適用する。

ただし、下流に輻輳しているシェーパがある場合は、新たにＲＥＤ回路を適用しない。検出されたシェーパに対応するキューは、下流のシェーパに適用されているＲＥＤ回路によって既にカバーされているためである。また、上流に輻輳しているシェーパがある場合は、上流のシェーパに適用されているＲＥＤ回路を解放する。検出されたシェーパに適用するＲＥＤ回路によって、上流のシェーパに対応するキューがカバーされるからである。このように、上流・下流の関係にある複数のシェーパが輻輳している場合、下流側のシェーパを対象としてＲＥＤ回路が適用される。

なお、図９のフローチャートでは、上流のシェーパに適用されているＲＥＤ回路を解放した後、検出されたシェーパに適用するＲＥＤ回路を選択しているが、空きのＲＥＤ回路があれば両者の順序が逆でもよい。また、上流のシェーパに適用されているＲＥＤ回路の１つを、検出されたシェーパに適用するＲＥＤ回路として流用してもよい。

図１０は、ＲＥＤ回路適用の処理を示すフローチャートである。この処理は、上記ステップＳ１７で実行される。以下、図１０に示す処理をステップ番号に沿って説明する。
（ステップＳ１０１）輻輳検出部１４０は、ＲＥＤ回路テーブル１５２を検索し、空きのＲＥＤ回路の中から、上記ステップＳ１１で検出されたシェーパに適用するＲＥＤ回路を選択する。適用するＲＥＤ回路は、ランダムに選択してもよいし、所定の規則に従って選択してもよい。後者の方法として、例えば、ＲＥＤ回路１２０，１２０ａ，１２０ｂの優先順位を予め決めておく、シェーパ毎に優先順位を決めておく、各ＲＥＤ回路の使用率が偏らないように選択する、などの方法が考えられる。

（ステップＳ１０２）輻輳検出部１４０は、シェーパテーブル１５１を検索して、検出されたシェーパに対応する１またはそれ以上のキューを特定する。そして、輻輳検出部１４０は、ＲＥＤ回路テーブル１５２に、ステップＳ１０１で選択したＲＥＤ回路に対応付けて、検出されたシェーパの識別情報と特定したキューの識別情報とを登録する。また、選択したＲＥＤ回路に、特定したキューを通知する。以下では、ＲＥＤ回路１２０が選択された場合を考える。

（ステップＳ１０３）平均キュー長算出部１２１は、輻輳検出部１４０から通知されたキューのキュー長の情報を取得し始める。そして、直近の一定時間の平均キュー長を算出する。ここで、通知されたキューが複数ある場合、各キューのキュー長の合計値を、複数のキュー全体に対する仮想的なキュー長と見なす。または、各キューのキュー長の最大値を仮想的なキュー長と見なす。そして、仮想的なキュー長を時間平均したものを平均キュー長として算出する。ただし、他の方法で平均キュー長を算出してもよい。

（ステップＳ１０４）廃棄率算出部１２２は、ステップＳ１０３で平均キュー長算出部１２１によって算出された平均キュー長から、パケットの廃棄率を算出する。例えば、図８に示したような確率曲線に基づいて算出することができる。確率曲線は、パケット廃棄の対象のキューまたはシェーパに応じて異なるものを使用してもよい。

（ステップＳ１０５）輻輳検出部１４０は、ステップＳ１０２で特定されたキュー宛てのパケットをＲＥＤ回路１２０に振り分けるよう、振分部１１０に指示する。パケット廃棄部１２３は、ステップＳ１０４で廃棄率算出部１２２によって算出された廃棄率に従って、振分部１１０から取得するパケットを確率的に廃棄すると共に、廃棄しなかったパケットを集約部１３０に出力する。

このようにして、廃棄制御部１００は、輻輳が発生したシェーパに適用するＲＥＤ回路を、ストックされているＲＥＤ回路１２０，１２０ａ，１２０ｂの中から選択する。選択されたＲＥＤ回路は、輻輳が発生したシェーパに対応するキューの滞留状態に応じて廃棄率を算出し、それらキュー宛てのパケットを算出した廃棄率で確率的に廃棄する。なお、パケット廃棄の開始後、平均キュー長の算出および廃棄率の算出は継続的（例えば、定期的）に行い、キュー状態の変化に応じて廃棄率を変更することが好ましい。

図１１は、輻輳解消時の処理を示すフローチャートである。以下、図１１に示す処理をステップ番号に沿って説明する。
（ステップＳ２１）輻輳検出部１４０は、輻輳しているシェーパ、すなわち、シェーパテーブル１５１で輻輳フラグがＯＮ（１）であるシェーパを監視し、輻輳が解消したシェーパを検出する。輻輳検出部１４０は、例えば、使用率が所定の閾値以下になったシェーパを、輻輳が解消したと判断する。または、対応するキューのキュー長の合計値が所定の閾値以下になったシェーパを、輻輳が解消したと判断する。なお、輻輳の発生を検出するための閾値と輻輳の解消を検出するための閾値とは、異なる閾値にすることができる。その場合、例えば、後者の閾値を前者の閾値よりも低く設定することが考えられる。

（ステップＳ２２）輻輳検出部１４０は、シェーパテーブル１５１において、ステップＳ２１で検出したシェーパの輻輳フラグを、ＯＮ（１）からＯＦＦ（０）に変更する。
（ステップＳ２３）輻輳検出部１４０は、ＲＥＤ回路テーブル１５２を検索し、検出されたシェーパに対してＲＥＤ回路が適用されているか否か判断する。ＲＥＤ回路が適用されている場合、処理をステップＳ２４に進める。ＲＥＤ回路が適用されていない場合、処理を終了する。

（ステップＳ２４）輻輳検出部１４０は、検出されたシェーパに適用されているＲＥＤ回路を特定する。そして、特定したＲＥＤ回路を解放する。具体的には、輻輳検出部１４０は、ＲＥＤ回路テーブル１５２から、検出されたシェーパの識別情報および対応するキューの識別情報を削除する。また、検出されたシェーパに対応するキューと特定したＲＥＤ回路との対応付けを解除するよう、振分部１１０に指示する。

（ステップＳ２５）輻輳検出部１４０は、シェーパテーブル１５１を検索し、検出されたシェーパの上流、すなわち、対応するキューとそのシェーパとの間に、輻輳しているシェーパが存在するか否か判断する。上流に輻輳しているシェーパがある場合、処理をステップＳ２６に進める。輻輳しているシェーパがない場合、処理を終了する。

（ステップＳ２６）輻輳検出部１４０は、上流の輻輳しているシェーパのうち、最も下流側に位置する１またはそれ以上のシェーパを選択する。そして、選択したシェーパそれぞれを対象としてＲＥＤ回路を適用する。図１０に示したフローと同様のフローにより、ＲＥＤ回路を適用することができる。

このようにして、廃棄制御部１００は、シェーパの使用状況またはキューの滞留状況に基づいて、シェーパ単位で輻輳状態を検出する。輻輳が解消したシェーパがあると、そのシェーパに適用されているＲＥＤ回路を解放する。

ここで、上流に輻輳しているシェーパがある場合は、上流のシェーパにＲＥＤ回路を適用する。輻輳が解消したシェーパにＲＥＤ回路が適用されなくなると、上流のシェーパに対応するキューがＲＥＤ回路によってカバーされなくなるためである。このように、上流・下流の関係にある複数のシェーパがあり下流側のシェーパのみ輻輳が解消すると、ＲＥＤ回路の適用対象が上流側にシフトする。

なお、図１１のフローチャートでは、輻輳が解消したシェーパに適用されているＲＥＤ回路を解放した後、上流のシェーパに適用するＲＥＤ回路を選択しているが、空きのＲＥＤ回路があれば両者の順序が逆でもよい。また、輻輳が解消したシェーパに適用されているＲＥＤ回路を、上流のシェーパに適用するＲＥＤ回路として流用してもよい。

図１２は、パケットの振り分け例を示す第１の図である。シェーパ２３０ｃで輻輳が発生し、シェーパ２３０ｄ，２３０ｅとシェーパ２５０ａを含む下流のシェーパでは輻輳が発生していないとする。すると、シェーパ２３０ｃに対してＲＥＤ回路１２０，１２０ａ，１２０ｂの何れかが適用される。ここでは、ＲＥＤ回路１２０ｂが適用されたとする。

この場合、振分部１１０により、キュー２２０ｃ宛てのパケットが、ＲＥＤ回路１２０ｂに振り分けられる。ＲＥＤ回路１２０ｂでは、キュー２２０ｃの平均キュー長に基づいて廃棄率が算出される。そして、キュー２２０ｃ宛てのパケットが確率的に廃棄される。廃棄されなかったパケットは、キュー２２０ｃに格納される。一方、キュー２２０ｄ，２２０ｅ宛てのパケットは、ＲＥＤ回路１２０ｂを迂回して通過し、キュー２２０ｄ，２２０ｅに格納される。

図１３は、パケットの振り分け例を示す第２の図である。シェーパ２３０ｃに加えて、シェーパ２５０ａで輻輳が発生し、シェーパ２５０ａより下流のシェーパでは輻輳が発生していないとする。すると、シェーパ２５０ａに対してＲＥＤ回路１２０，１２０ａ，１２０ｂの何れかが適用される。シェーパ２３０ｃに対しては、ＲＥＤ回路を適用しなくてよい。ここでは、シェーパ２５０ａに対してＲＥＤ回路１２０ｂが適用されたとする。

この場合、振分部１１０により、キュー２２０ｃ，２２０ｄ，２２０ｅ宛てのパケットが、ＲＥＤ回路１２０ｂに振り分けられる。ＲＥＤ回路１２０ｂでは、キュー２２０ｃ，２２０ｄ，２２０ｅの平均キュー長に基づいて廃棄率が算出される。そして、キュー２２０ｃ，２２０ｄ，２２０ｅ宛てのパケットが確率的に廃棄される。廃棄されなかったパケットは、キュー２２０ｃ，２２０ｄ，２２０ｅに格納される。

図１４は、パケットの振り分け例を示す第３の図である。図１３の場合と同様、シェーパ２３０ｃ，２５０ａで輻輳が発生し、シェーパ２５０ａより下流のシェーパでは輻輳が発生していないとする。すると、シェーパ２５０ａに対してＲＥＤ回路１２０，１２０ａ，１２０ｂの何れかが適用される。ここでは、ＲＥＤ回路１２０ｂが適用されたとする。ただし、キュー２２０ｅが、予めパケット廃棄の対象外として設定されているとする。

この場合、振分部１１０により、キュー２２０ｃ，２２０ｄ宛てのパケットが、ＲＥＤ回路１２０ｂに振り分けられる。ＲＥＤ回路１２０ｂでは、キュー２２０ｃ，２２０ｄの平均キュー長に基づいて廃棄率が算出される。そして、キュー２２０ｃ，２２０ｄ宛てのパケットが確率的に廃棄される。廃棄されなかったパケットは、キュー２２０ｃ，２２０ｄに格納される。一方、キュー２２０ｅ宛てのパケットは、ＲＥＤ回路適用の対象外であるため、ＲＥＤ回路１２０ｂを迂回して通過し、キュー２２０ｅに格納される。

図１５は、ＲＥＤ回路とキューとの対応付け例を示す図である。ここでは、シェーパ２３０ａで輻輳が発生し、シェーパ２３０ａより下流のシェーパ２５０，２５０ｂ，２５０ｃでは輻輳が発生していない。また、シェーパ２３０ｃ，２５０ａで輻輳が発生し、シェーパ２５０ａより下流のシェーパ２５０ｂ、２５０ｃでは輻輳が発生していない。

そこで、例えば、シェーパ２３０ａとシェーパ２５０ａに対して、それぞれ、ＲＥＤ回路１２０とＲＥＤ回路１２０ｂが適用される。この場合、ＲＥＤ回路１２０は、キュー２２０ａ宛てのパケットを取得し、取得したパケットを確率的に廃棄する。ＲＥＤ回路１２０ｂは、キュー２２０ｃ，２２０ｄ，２２０ｅ宛てのパケットを取得し、取得したパケットを確率的に廃棄する。

このような第２の実施の形態に係る中継装置１０，１０ａ，１０ｂによれば、輻輳が発生したシェーパに対応する１またはそれ以上のキューを、ストックしてある複数のＲＥＤ回路の何れかに動的に対応付けることができる。これにより、複数のキューに対するパケット廃棄の制御を効率的に実現することができる。

すなわち、全てのキューについて固定的にＲＥＤ回路を対応付けておく方法と比べて、回路規模を抑制することができる。また、一部のキューにのみ固定的にＲＥＤ回路を対応付けておく方法と比べて、多くのキューをＲＥＤ処理の対象とすることができ、通信品質の劣化を抑制できる。

また、輻輳が発生したシェーパに対応する１またはそれ以上のキュー、すなわち、その輻輳に関与していると考えられるキューを、仮想的な１つのキューと見なしてＲＥＤ回路を適用する。このため、輻輳に関与していないキュー宛てのパケットを過剰に廃棄してしまう可能性を低減できると共に、ＲＥＤ回路とパケット廃棄の対象とすることが好ましいキューとの対応付けの制御が容易になる。

また、各シェーパのパケットの通過状況に基づいて輻輳を検出することで、迅速な輻輳検出が可能となる。一方、各シェーパに対応するキューにおけるパケットの滞留状況に基づいて輻輳を検出することで、回路の簡素化を図ることができる。また、複数のキューに対する平均キュー長を算出する際に、各キューのキュー長の合計値を仮想的なキュー長と見なすことで、平均キュー長の算出精度を向上できる。一方、最大のキュー長を仮想的なキュー長と見なすことで、負荷の軽減および回路の簡素化を図ることができる。また、特定のキューをパケット廃棄の対象外に設定することで、より柔軟なＱｏＳ制御ができる。

なお、第２の実施の形態では、ＲＥＤ回路とシェーパとが動的に１対１に対応付けられる。これにより、特定のシェーパの輻輳を解消するための制御が容易となる。ただし、ＲＥＤ回路が不足した場合、ＲＥＤ回路とシェーパとが動的に１対多に対応付けられるようにしてもよい。すなわち、１つのＲＥＤ回路が複数のシェーパを担当してもよい。

１ パケット中継装置
１ａ，１ｂ，１ｃ キュー
１ｄ 輻輳検出部
１ｅ 振分部
１ｆ 廃棄部

Claims (10)

1. 送信待ちのパケットを格納する複数のキューと、
   前記複数のキューの輻輳状態を検出し、前記輻輳状態に基づいて前記複数のキューから１またはそれ以上のキューを選択する輻輳検出部と、
   前記複数のキューに格納される前の一連のパケットから、前記輻輳検出部で選択された前記１またはそれ以上のキュー宛てのパケットを分離する振分部と、
   前記振分部で分離された前記１またはそれ以上のキュー宛てのパケットを、それぞれ所定の確率で廃棄する複数の廃棄部と、
   を有し、
   前記振分部は、前記複数の廃棄部のいずれかに前記パケットを割り振り、
   前記廃棄部毎の確率で前記パケットが廃棄される
   ことを特徴とするパケット中継装置。
2. 前記複数のキューの一部にそれぞれ対応しており、対応するキューに格納されたパケットの送信タイミングを制御する複数のシェーパを更に有し、
   前記輻輳検出部は、シェーパ単位で前記輻輳状態を検出し、輻輳していると判断されたシェーパに対応するキューを前記１またはそれ以上のキューとして選択する
   ことを特徴とする請求項１記載のパケット中継装置。
3. 送信待ちのパケットを格納する複数のキューと、
   前記複数のキューの輻輳状態を検出し、前記輻輳状態に基づいて前記複数のキューから１またはそれ以上のキューを選択する輻輳検出部と、
   前記複数のキューに格納される前の一連のパケットから、前記輻輳検出部で選択された前記１またはそれ以上のキュー宛てのパケットを分離する振分部と、
   前記振分部で分離された前記１またはそれ以上のキュー宛てのパケットを、それぞれ所定の確率で廃棄する廃棄部と、
   前記複数のキューの一部にそれぞれ対応しており、対応するキューに格納されたパケットの送信タイミングを制御する複数のシェーパと、
   を有し、
   前記輻輳検出部は、各シェーパにおけるパケットの通過状況に基づいて前記輻輳状態を検出し、輻輳していると判断されたシェーパに対応するキューを前記１またはそれ以上のキューとして選択する
   ことを特徴とするパケット中継装置。
4. 前記輻輳検出部は、各シェーパに対応するキューにおけるパケットの滞留状況に基づいて前記輻輳状態を検出する
   ことを特徴とする請求項２に記載のパケット中継装置。
5. 前記複数のシェーパは、第１のシェーパと、前記第１のシェーパを通過したパケットが入力される第２のシェーパとを含み、
   前記輻輳検出部は、前記第１のシェーパと前記第２のシェーパとが輻輳していると判断された場合、前記第２のシェーパに対応するキューを前記１またはそれ以上のキューとして選択する
   ことを特徴とする請求項２乃至４の何れか一項に記載のパケット中継装置。
6. 前記輻輳検出部で選択された前記１またはそれ以上のキューにおけるパケットの滞留状況を算出する算出部を更に有し、
   前記廃棄部は、前記算出部で算出された前記滞留状況に応じた廃棄率を前記所定の確率として使用する
   ことを特徴とする請求項１乃至５の何れか一項に記載のパケット中継装置。
7. 前記算出部は、前記１またはそれ以上のキューそれぞれのキュー長の合計に基づいて、前記滞留状況を算出する
   ことを特徴とする請求項６記載のパケット中継装置。
8. 送信待ちのパケットを格納する複数のキューと、
   前記複数のキューの輻輳状態を検出し、前記輻輳状態に基づいて前記複数のキューから１またはそれ以上のキューを選択する輻輳検出部と、
   前記複数のキューに格納される前の一連のパケットから、前記輻輳検出部で選択された前記１またはそれ以上のキュー宛てのパケットを分離する振分部と、
   前記振分部で分離された前記１またはそれ以上のキュー宛てのパケットを、それぞれ所定の確率で廃棄する廃棄部と、
   前記輻輳検出部で選択された前記１またはそれ以上のキューにおけるパケットの滞留状況を算出する算出部と、
   を有し、
   前記算出部は、前記１またはそれ以上のキューそれぞれのキュー長のうち最大のキュー長に基づいて、前記滞留状況を算出し、
   前記廃棄部は、前記算出部で算出された前記滞留状況に応じた廃棄率を前記所定の確率として使用する
   ことを特徴とするパケット中継装置。
9. 前記輻輳検出部は、前記輻輳状態に拘わらず、前記複数のキューのうち所定のキューを選択対象から除外する
   ことを特徴とする請求項１乃至８の何れか一項に記載のパケット中継装置。
10. 送信待ちのパケットを格納する複数のキューの輻輳状態を検出し、前記輻輳状態に基づいて前記複数のキューから１またはそれ以上のキューを選択し、
    前記複数のキューに格納される前の一連のパケットから、選択した前記１またはそれ以上のキュー宛てのパケットを分離し、
    分離した前記１またはそれ以上のキュー宛てのパケットを、それぞれ所定の確率で廃棄する複数の廃棄部のいずれかに割り振り、
    前記廃棄部毎の確率で前記パケットが廃棄される
    ことを特徴とする輻輳制御方法。
    

Images