JP4342395B2

JP4342395B2 - パケット中継方法及び装置

Info

Publication number: JP4342395B2
Application number: JP2004212152A
Authority: JP
Inventors: 純一江原; 大輔浪平; 昌男吉川
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 2004-07-20
Filing date: 2004-07-20
Publication date: 2009-10-14
Anticipated expiration: 2024-07-20
Also published as: US20060018316A1; US7561516B2; JP2006033628A

Description

本発明は、パケット中継方法及び装置に関し、特にパケット方式の通信ネットワーク内の中継装置等に適用されるパケット中継方法及び装置に関するものである。

インターネットの普及・高度化により、さまざまな種類のデータがインターネットまたはインターネットプロトコルを採用した組織内ネットワーク（イントラネット）上で大量に流通されるようになった。すなわち、電子メールやWWWのようにリアルタイム性を必要としないものから、IP電話のような厳しいリアルタイム性を求められるものや、勘定系データのように高速で確実なデータ転送を必要とするものなど、多種多様なデータが同じ伝送路を共有して伝送されている。

インターネットで用いられるデータ通信規約であるインターネットプロトコル（IP）は、すべてのデータを皆平等に扱うことを基本として設計されている。そのため、現在のように重要・非重要なデータが混在して流通するネットワークでは、通常、重要でないデータの伝送に帯域が消費されたときには、重要なデータのための帯域が無くなってしまうという問題が発生する。

この問題を解決するために古くから採られてきた手法は、伝送経路自体の高速化である。この手法は最も安易に通信品質を改善するが、設備投資のためのコストが大きいこと、データがバースト的（電子メールの送受信のように、短時間に集中して間欠的に大量のデータが流れること。）であった場合にデータの流れない時間帯は設備が無駄になることから、経済的に好ましい手法ではない。

そこで、データを重要性・非重要性、及びリアルタイム性で分類し、重要なデータ及びリアルタイム性の高いデータには大きな帯域を、重要でなくリアルタイム性の低いデータには小さい帯域を割り振るよう、帯域を制御する技術が開発された。これがネットワークQoS（Quality of Service）技術である。

このQoSとは一般にサービス品質のことを指すが、ネットワークのQoSという場合、主に伝送レートと伝送遅延に関する品質のことを指す。QoS技術は、ネットワークのパケット中継（交換）装置に実装される。ネットワーク設計者は、ネットワーク全体での帯域制御ポリシーを設計し、ネットワークに存在する中継装置に対し、このポリシーを適用することで、ネットワークのQoSを保証する。

図5には、このようなパケット中継装置を含んだネットワークの一般的な構成例が示されており、ネットワーク１からのパケットを受信したパケット中継装置2は、L2スイッチ3及び負荷分散装置4_1,4_2（以下、符号「4」で総称することがある。）を経由して、端末（サーバ）5_1〜5_n（以下、符号「5」で総称することがある。）にパケットを送る構成になっている。この例では、パケット中継装置2からのパケット（10Gbps）はL2スイッチ3で1Gbpsのパケットに絞られ（シェーピング）、さらに、負荷分散装置4で100Mbpsのパケットに分散されて各端末5に与えられる。各負荷分散装置4には、8台の端末5が接続されているものとする。

図6には、図5に示したパケット中継装置における帯域制御（シェーピング）方式の従来構成例が示されている。この構成例は、メータリング処理部11とWRED処理部12とキュー部13とスケジューラ部14とで構成されている。なお、この例においては、パケット毎にそのフローが特定される（パケットフローを識別できるような情報が入っている）ことを前提としている。

まず、メータリング処理部11は、入力パケットのフロー毎にデータ流量（単位時間当たりのビット数）の計測（メータリング）を行う。該当フローのパケットが以前入って来た時間と今の時間、入力パケット長、並びに制限帯域値（Bp）及び保証帯域値（Bc）から該当フローの制限トークンカウンタ（データビット数）及び保証トークンカウンタ（パケット数）を計算し、計算したビット数を入力パケットのパケット長と比較することにより、入力パケットに対してフロー状態に関する情報が付与される。このフロー状態情報は交通信号に準じて色（典型的なのが赤、黄、青の３色）で表現される（例えば、非特許文献1,2参照。）。この場合、赤は制限帯域値を越えており、廃棄すべきもの、青は通過させるべきものといった意味を有し、パケットにこの情報を付加することを「色付け（カラーリング）」と呼ぶ。

WRED（Weighted Random Early Detection）処理部12は、メータリング処理部11で付けられた色と、そのパケットが入るべきキュー（待ち行列）部13に入っている総パケット長から、確率的な廃棄を実施する。すなわち、キュー部13は、各フロー毎に一つずつキューが割り当てられており、各WRED処理部12は、キューに入っているパケット数が上限値（指定値）以上なら廃棄、下限値（指定値）以下なら通過、上限値と下限値の間なら、赤は廃棄、青は通過、黄色はキューに入っているキュー数に応じて算出される確率によって廃棄とする処理を実行する。

そして、スケジューラ部14は、各キューのメータリング件名及び各キュー毎に指定された優先度に応じてパケットの出力順序及び出力間隔のスケジューリングを行う。

なお、バースト発生時の帯域制御（シェーピング）におけるキューのオーバーフロー回避に関する技術として、シェーピング処理装置及びシェーピング処理方法がある（例えば、特許文献1参照。）。
Heinanen, J. and R. Guerin, "A Single Rate Three Color Marker", RFC2697,1999.（http://www.IETF.org.） Heinanen, J.and R. Guerin, "A Two Rate Three Color Marker", RFC2698,1999. （http://www.IETF.org.）特開平10-173664号公報

従来、メータリング処理部でのデータ流量測定は、上述の如く、単位時間当りのデータビット数（一般にはbps（bit per second、一秒当りビット数）を単位として表現される。）で実施していた。これは、通信品質保証（QoS）がデータ伝送路の輻輳回避を第一目的としているためである。

しかしながら、サーバや負荷分散装置の多くは、回線の能力を最大限に活用できるほどのパケット処理能力を持っていない。これは、サーバが実施する各種サービス内容が複雑であることが原因である。また、データ回線が高速化されてもパケット中継装置の処理能力がそれに追い着かない場合は、パケット中継装置がボトルネックとなり、設定されたQoSを満足できない場合が発生する。これらサーバ、負荷分散装置、パケット中継装置のパケット処理性能は、単位時間当りパケット処理数で表現され、その単位は一般にpps（packet per second: 一秒当りパケット数）が用いられる。

ATM（Asynchronous Transfer Mode：非同期転送モード）のような固定長パケットの伝送方式の場合、bpsとppsはほぼ比例するため、bpsを制御することで装置の処理性能を含めたQoSを或る程度規定することができる。しかしながら、イーサネット（登録商標）のようにパケットが可変長である伝送方式の場合は、ビット数（bps）とパケット数（pps）の相関が低く、ビット数（bps）のみで規定された帯域制御、又はパケット数（pps）のみで規定された帯域制御では装置のパケット処理性能を考慮に入れることができない。そのため、パケット処理能力の低いサーバ負荷分散装置などを含む可変長パケット方式のネットワークでは、望ましいQoSが得られない場合があった。

これを、図7及び図8にそれぞれ示したパケット中継方式[1]及び[2]を参照して説明する。

まず、図7において、同図（1）に示すように、パケット中継装置2の出力側回線速度を1Gbpsに絞る場合、送出するパケットが64バイトの最短パケットであるとすると、出力データは148万ppsとなり、負荷分散装置4の処理能力が80万ppsであれば、68万パケットが失われることになる。すなわち、負荷分散装置4に8台の端末5が繋がっているとし、端末5のリクエスト処理能力が1台当り10万ppsであるとすれば、負荷分散装置4に対して80万pps以上のパケットを流すと端末5の側で廃棄されることになる。

一方、同図（2）に示すように、同じ回線速度で、送出するパケットが1,514バイトの最長パケットの場合には、出力データは、8万ppsとなり、この場合には、負荷分散装置4の処理能力を超えることはないが、1/10しか稼動しないという問題がある。

さらに、図8（1）に示すように、回線速度を80万ppsに絞る場合、送出するパケットが64バイトの最短パケットであれば、出力データは600Mbpsとなり、負荷分散装置4の処理能力が100M×8=800Mbpsであれば通過することになるが、同図（2）に示すように、同じ回線速度で、送出するパケットが1,514バイトの最長パケットの場合には、出力データは、10Gbpsとなり、負荷分散装置4の処理能力は遠く及ばず、殆どが廃棄されてしまうことになる。

従来の帯域設定では、bps設定のみなので回線帯域の1Gbpsを設定するのが回線効率として最も良いが、その場合、フレーム長によっては150万pps近くのパケットが負荷分散装置に流れてしまう。逆に80万pps以内に抑えようとする場合、bps設定では600Mbps程度に帯域を絞らなければならない。

このように、ビット数（bps）又はパケット数（pps）の一方の帯域制御のみでは、好ましいQoSが得られない。

従って本発明は、可変長パケット方式のネットワークにおいても、データビット数（bps）とパケット数（pps）の調和を図ってパケットの中継を行う方法及び装置を提供することを目的とする。

上記の目的を達成するため、本発明に係るパケット中継方法は、フロー毎の単位時間当りのデータビット数の所定制限帯域値及び入力パケットのパケット長に基づいて該入力パケットの色付けを行う第1のステップと、フロー毎の単位時間当りのパケット数の所定制限帯域値及び入力パケットのパケット数に基づいて該入力パケットの色付けを行う第2のステップと、該第1及び第2のステップでの色付けの内、廃棄すべき色を優先的に該入力パケットの色を決定する第3のステップと、を備え、該データビット数が、パケット入力時のデータビット数から該所定制限帯域値だけ増加する値であり、該パケット数が、パケット入力時のパケット数から該所定制限帯域値だけ増加する値であり、該第1のステップで、該データビット数が、入力パケットのパケット長より小さいとき該入力パケットを該廃棄すべき色として赤色に色付けし、それ以外は青色に色付けし、該第2のステップで、該パケット数が該入力パケットのパケット数より小さいとき該入力パケットを赤色に色付けし、それ以外は青色に色付けすることを特徴としている。

すなわち、第1のステップでは予め設定されているフロー毎の単位時間当りのデータビット数（データビット流量）の所定制限帯域値と入力パケットのパケット長に基づいて入力パケットの色付けを行い、第2のステップでは、予め設定したフロー毎の単位時間当りのパケット数（パケット流量）の所定制限帯域値と入力パケットのパケット数とに基づいて入力パケットの色付けを行う。そして、このように第1及び第2のステップで色付けを行って得られた色の内、廃棄すべき色（赤）を優先して入力パケットの色を第3のステップで決定する。
ここで、上記のデータビット数（制限トークンカウンタ）は、パケット入力時のデータビット数からその所定制限帯域値だけ増加する値であり、また該パケット数（制限トークンカウンタ）は、パケット入力時のパケット数からその所定制限帯域値だけ増加する値であり、該第1のステップで、該データビット数が、入力パケットのパケット長より小さいとき該入力パケットを該廃棄すべき色として赤色に色付けし、それ以外は青色に色付けし、該第2のステップで、該パケット数が該入力パケットのパケット数より小さいとき該入力パケットを赤色に色付けし、それ以外は青色に色付けする。

このようにデータビット流量の所定制限帯域値とパケット流量の所定制限帯域値の双方を指定可能とすることにより、パケットフロー帯域を食い潰さないように制御することが可能となる。

また、本発明に係るパケット中継方法では、フロー毎の単位時間当りのデータビット数の所定保証帯域値及び入力パケットのパケット長に基づいて該入力パケットの色付けを行う第1のステップと、フロー毎の単位時間当りのパケット数の所定保証帯域値及び入力パケットのパケット数に基づいて該入力パケットの色付けを行う第2のステップと、該第1及び第2のステップでの色付けの内、確率的に廃棄（一部廃棄又は一部通過）させるべき色（黄）を優先的に該入力パケットの色を決定する第3のステップと、を備え、該データビット数が、パケット入力時のデータビット数から該所定保証帯域値だけ増加する値であり、該パケット数が、パケット入力時のパケット数から該所定保証帯域値だけ増加する値であり、該第1のステップで、該データビット数が、入力パケットのパケット長より大きいとき該入力パケットを該通過させるべき色として青色に色付けし、それ以外は赤色に色付けし、該第2のステップで、該パケット数が該入力パケットのパケット数より大きいとき該入力パケットを青色に色付けし、それ以外は赤色に色付けすることを特徴としている。

すなわち、この発明の場合には、上記の所定制限帯域値の代わりに所定保証帯域値を用い、データビット流量の所定保証帯域値及びパケット流量の所定保証帯域値を同時に設定可能とし、以って速度を保証しつつ、帯域を食い潰さない程度に重要なパケットを通過させるようにパケットフロー帯域の制御を行ったものである。

さらに本発明に係るパケット中継方法では、フロー毎の単位時間当りのデータビット数の第1の所定制限帯域値、第1の所定保証帯域値及び入力パケットのパケット長に基づいて該入力パケットの色付けを行う第1のステップと、フロー毎の単位時間当りのパケット数の第2の所定制限帯域値、第2の所定保証帯域値及び入力パケットのパケット数に基づいて該入力パケットの色付けを行う第2のステップと、該第1及び第2のステップでの色付けの内、廃棄すべき色（赤）と通過させるべき色（青）と確率的に廃棄すべき色（黄）のいずれかを決定する第3のステップと、を備え、該データビット数が、パケット入力時のデータビット数から該第1の所定制限帯域値及び該第1の所定保証帯域値だけそれぞれ増加する第1及び第2のビット数を含み、該パケット数が、パケット入力時のパケット数から該第2の所定制限帯域値及び該第2の所定保証帯域値だけそれぞれ増加する第1及び第2のパケット数を含み、該第1のステップで、該第1のビット数が、入力パケットのパケット長より小さいとき該入力パケットを該廃棄させるべき色として赤色に色付けし、該パケット長より大きく該第2のビット数も該パケット長より大きいとき該入力パケットを該通過させるべき色として青色に色付けし、これら以外は黄色に色付けし、該第2のステップで、該第1のパケット数が、入力パケットのパケット数より小さいとき該入力パケットを該廃棄させるべき色として赤色に色付けし、該パケット数より大きく該第2のパケット数も該パケット数より大きいとき該入力パケットを該通過させるべき色として青色に色付けし、これら以外は黄色に色付けするとともに、該第3のステップでは、競合したとき赤色、黄色、及び青色の順に優先して該入力パケットの色を決定することを特徴としている。

すなわち、この発明では、上記の各所定制限帯域値と各所定保証帯域値の両方を用いることにより、廃棄すべき色と通過させるべき色と確率的に廃棄（一部通過）すべき色のいずれかを決定して入力パケットに付与するようにしている。これにより、帯域を食い潰さないようにするとともに大切なパケットをより有効に出力することが可能となる。

上記の本発明に係るパケット中継方法を実現するパケット中継装置は、フロー毎の単位時間当りのデータビット数の所定制限帯域値及び入力パケットのパケット長に基づいて該入力パケットの色付けを行う第1の手段と、フロー毎の単位時間当りのパケット数の所定制限帯域値及び入力パケットのパケット数に基づいて該入力パケットの色付けを行う第2の手段と、該第1及び第2の手段での色付けの内、廃棄すべき色を優先的に該入力パケットの色を決定する第3の手段と、を備え、該データビット数が、パケット入力時のデータビット数から該所定制限帯域値だけ増加する値であり、該パケット数が、パケット入力時のパケット数から該所定制限帯域値だけ増加する値であり、該第1の手段が、該データビット数が、入力パケットのパケット長より小さいとき該入力パケットを該廃棄すべき色として赤色に色付けし、それ以外は青色に色付けし、該第2の手段が、該パケット数が該入力パケットのパケット数より小さいとき該入力パケットを赤色に色付けし、それ以外は青色に色付けすることを特徴とするものである。

あるいは、本発明に係るパケット中継装置は、フロー毎の単位時間当りのデータビット数の所定保証帯域値及び入力パケットのパケット長に基づいて該入力パケットの色付けを行う第1の手段と、フロー毎の単位時間当りのパケット数の所定保証帯域値及び入力パケットのパケット数に基づいて該入力パケットの色付けを行う第2の手段と、該第1及び第2の手段での色付けの内、確率的に廃棄すべき色を優先的に該入力パケットの色を決定する第3の手段と、を備え、該データビット数が、パケット入力時のデータビット数から該所定保証帯域値だけ増加する値であり、該パケット数が、パケット入力時のパケット数から該所定保証帯域値だけ増加する値であり、該第1の手段が、該データビット数が、入力パケットのパケット長より大きいとき該入力パケットを該通過させるべき色として青色に色付けし、それ以外は赤色に色付けし、該第2の手段が、該パケット数が該入力パケットのパケット数より大きいとき該入力パケットを青色に色付けし、それ以外は赤色に色付けすることを特徴とするものでもよい。

さらに、本発明に係るパケット中継装置は、フロー毎の単位時間当りのデータビット数の第1の所定制限帯域値、第1の所定保証帯域値及び入力パケットのパケット長に基づいて該入力パケットの色付けを行う第1の手段と、フロー毎の単位時間当りのパケット数の第2の所定制限帯域値、第2の所定保証帯域値及び入力パケットのパケット数に基づいて該入力パケットの色付けを行う第2の手段と、該第1及び第2の手段での色付けの内、廃棄すべき色と通過させるべき色と一部廃棄すべき色のいずれかを決定する第3の手段と、を備え、該データビット数が、パケット入力時のデータビット数から該第1の所定制限帯域値及び該第1の所定保証帯域値だけそれぞれ増加する第1及び第2のビット数を含み、該パケット数が、パケット入力時のパケット数から該第2の所定制限帯域値及び該第2の所定保証帯域値だけそれぞれ増加する第1及び第2のパケット数を含み、該第1の手段が、該第1のビット数が、入力パケットのパケット長より小さいとき該入力パケットを該廃棄させるべき色として赤色に色付けし、該パケット長より大きく該第2のビット数も該パケット長より大きいとき該入力パケットを該通過させるべき色として青色に色付けし、これら以外は黄色に色付けし、該第2の手段が、該第1のパケット数が、入力パケットのパケット数より小さいとき該入力パケットを該廃棄させるべき色として赤色に色付けし、該パケット数より大きく該第2のパケット数も該パケット数より大きいとき該入力パケットを該通過させるべき色として青色に色付けし、これら以外は黄色に色付けするとともに、該第3の手段が、競合したとき赤色、黄色、及び青色の順に優先して該入力パケットの色を決定することを特徴とするものでもよい。

本発明によれば、データビット数（bps）とパケット数（pps）の双方でシェーピングが行えるため、回線の輻輳と装置の輻輳の双方を制御できることになり、より安定したQoSのネットワークを構築することが可能となる。

以下、本発明に係るパケット中継方法及び装置の実施例を図面を参照して説明する。

図1は、図6に示したパケット中継装置のメータリング処理部11の本発明による一実施例を示したもので、このメータリング処理部11は、データビット数（bps）及びパケット数（pps）の双方での計量を実現したものである。

この実施例において、情報設定部21はユーザが指定した設定内容をbps計算部22及びbps計算部23に送るように接続されている。情報設定部21からbps計算部22に対する設定値は、初期値Tp1(0),Tc1(0)とビット数制限帯域値Bp1とビット数保証帯域値Bc1である。この場合のビット数制限帯域値Bp1の例としては、図5(a), (b)に示したように1Gbpsであり、ビット数保証帯域値Bc1の例としては、100Mbpsである。

また、情報設定部21からbps計算部23への設定値としては、初期値Tp2(0),TC2(0)とパケット数制限帯域値Bp2とパケット数保証帯域値Bc2である。この場合のパケット数制限帯域値Bp2の例としてはやはり図5(a), (b)に示す如く0.8Mpps（80万pps）であり、パケット数保証帯域値Bc2としては0.2Mpps（20万pps）である。

ここで、初期値Tp1(0)は、制限バーストサイズ(Burst Size)(Peak Burst Size:PBS)と称され、バースト時に出力可能なデータビット流量の最大値を制限するための値である。

また、初期値Tc1(0)は、保証バーストサイズ（Committed Burst Size: CBS）と称され、やはりバースト時に出力可能なデータビット流量の最小値を保証するための設定値であり、保証バーストサイズが設定されたフローでは、バースト発生時においてもこの保証バーストサイズ以上の通信が可能となる。

また、初期値Tc2(0)は、制限バーストパケット(Peak Burst Packet:PBP)と称され、制限バーストサイズと同様にバースト時に出力可能なパケット流量の最大値を制限するための設定値である。

さらに初期値Tc2(0)は、保証バーストパケット(Committed Burst Packet:CBP)と称され、バースト時に出力可能なパケット流量の最小値を保証するための設定値である。

また、「制限帯域値」とは、或るフローが使用できる帯域の最大値（最大流量）を指し、各フロー毎にビット数（bps）とパケット数（pps）の双方で設定が可能となっている。

また、「保証帯域値」とは或るフローに対して最低限保証したい帯域（流量）を指し、この場合も、ビット数（bps）とパケット数（pps）の双方で設定が可能になっている。

情報抽出部24は、入力したパケットPKTからそのパケット長を抽出してbps計算部22に与えると共に、パケット数を抽出してpps計算部23に与える。この場合、情報抽出部24はフロー毎、すなわち同一のフロー識別子毎にパケット長及びパケット数をそれぞれbps計算部22とpps計算部23に与えるようにしている。

bps計算部22は、これらの入力から色判定を行って色出力CL1を色選択部25に出力し、pps計算部23もこれらの入力から色判定を行って色出力CL2を色選択部25に与える。色選択部25は、これらの色出力CL1とCL2に基づいて、入力パケットPKTに対するフロー状態を決定し、色選択信号として色情報付与部26に与える。色情報付与部26は、パケットと色情報の双方を持ち、パケットPKTに対して色情報を付与して次段のWRED処理部12に渡す。以後のパケット処理の流れは、図6に示した従来技術と同様である。

bps計算部22
図2は、図1に示したbps計算部22における処理手順例を示している。まず、このbps計算部22において、情報抽出部24からパケット長Aバイトのパケットが入力したことが知らされると、ステップS1においてTp(t)とこのパケット長Aとの比較が行われる。

ここで、Tp(t)は、時刻tにおける制限トークンカウンタと称されるもので、上述の通り、制限バーストサイズTp(0)以下の値をとり、図6に示したキュー部13から出力することのできるパケット数を表わしている。

従って、ステップS1において、制限トークンカウンタTp(t)がパケット長Aより小さい場合（Tp(t)-A＜0）には、パケットは廃棄すべきであるので「赤」に色付けする（ステップS2）。そうでない場合にはステップS3に進む。

ステップS3では、Tc(t)とパケット長Aとを比較する。この場合のTc(t)は、時刻tにおける保証トークンカウンタを示しており、保証バーストサイズTc(0)以下の値をとるもので、この保証トークンカウンタTc(t)がパケット長Aより小さい場合（Tc(t)-A＜0）は、パケットは確率的に廃棄させるべきであるので、「黄」に色付けされ、これと同時に制限トークンカウンタTp(t)をパケット長Aだけデクリメント（Tp(t)-A）する。そうでない場合にはステップS5に進む（ステップS4）。

ステップS5では、保証トークンカウンタTc(t)がパケット長Aより大きいことが分かったので、パケットは通過すべきであり、以って「青」と色付けし、且つ制限トークンカウンタTp(t)をパケット長Aだけデクリメント（Tp(t)-A）すると共に保証トークンカウンタTc(t)をパケット長Aだけデクリメント（Tc(t)-A）してこのルーチンを終わる。

この後、次のパケットが来るまでの時間τ秒毎に、制限トークンカウンタTp(t)及び保証トークンカウンタTc(t)はそれぞれ、次式のように変化する。

Tp(t+τ)= Tp(t)+Bp×τ ・・・式(1)
Tc(t+τ)= Tc(t)+Bc×τ ・・・式(2)
すなわち、式(1)は、制限トークンカウンタTp(t)が時間τ秒で制限帯域値Bpだけ増加する（但し、制限バーストサイズTp(0)は超えない。）ことを示しており、式(2)は、保証トークンカウンタTc(t)が時間τ秒で保証帯域値Bcだけ増加する（但し、保証バーストサイズTc(0)は超えない。）ことを示している。

この図2に示したbps計算部22における処理手順のシーケンスが図4(1)に示されている。但し、この例では、時間t1〜t9毎にパケットが入力され、これに伴って色判定が行われたことを示している。なお、このbps計算部22においては、それぞれトークンカウンタやバーストサイズに“1”を付して、後述するpps計算部23でトークンカウンタやバーストサイズに付した“2”と区別している。

図示のように、縦軸は制限・保証トークンカウンタ（データビット数）を示しており、時間t=0の時には、初期値である制限バーストサイズTp1(0)(PBS)と保証バーストサイズTc1(0)(CBS)に設定されている。

そして、時間t1において、パケット長A1のパケットがメータリング処理部11に入力されると、これを受けてbps計算部22では、図2のフローチャートにおいて、図4(1)に示すとおり、Tp1(0)-A1＞0であるのでステップS1からステップS3に進む。ステップS3でも図示の如くTc1(0)-A1＞0であるのでステップS3からステップS5に進み、パケットの色付を「青」に設定すると共に、Tp1(t1)は“Tp1(0)-A1”に更新され、Tc1(t1)は“Tc1(t1)-A1”に更新される。

この結果、図4(1)の時間t1においては、トークンカウンタTp1(t1)及びTc1(t1)は、それぞれバーストサイズTp1(0)及びTc1(0)からパケット長A1だけ減少した値になる。

そして、上記の式(1)及び(2)に示したように、時間τ秒毎にトークンカウンタTp1(t)の場合には制限帯域値Bp1（傾き）だけ増加することになる。なお、この場合の制限帯域値としては、上述の通り“1Gbps”である。

また、保証トークンカウンタTc1(t)についても同様に保証帯域値Bc1（傾き）だけ時間τ秒毎に増加することになるので、トークンカウンタTp1(t)及びTc1(t)は、時間t1から時間t2に向かってそれぞれ傾きBp1及びBc1で増加することになる。

時間t2において、制限トークンカウンタTp1(2)は時間t1より帯域制限値Bp1だけ増加した値となっており、この時間t2において入力パケットのパケット長がA2であった場合には、図2のステップS1においてTp1(t2)-A2＞0であるので、ステップS1からステップS3に進む。ステップS3では、図4(1)に示すとおりTc1(t2)-A2＜0であるので、ステップS4に進み、パケットの色付けを「黄」とすると共に、制限トークンカウンタTp1(t)をパケット長A2だけデクリメントする。すなわち、時間t2での色付けが「黄」となり、色出力CL1が色選択部25に与えられることになる。

時間t3では、時間t2から同様にして時間τ秒の間に制限トークンカウンタTp1(t3)は制限帯域値Bp1だけ増加し、保証トークンカウンタTc1(t3)も保証帯域値Bc1だけ増加する。そして、この時、パケット長A3のパケットが入力したとすると、図示の例では、Tp1(t3)-A3＜0であるので、この場合には、保証トークンカウンタTc1(t3)とパケット長A3との関係を見るまでも無く、パケットの色付けを「赤」にする(ステップS2)。従って、ステップS4やS5に示すようなトークンカウンタの更新は行われず、制限トークンカウンタTp1(t)は時間t2からさらに時間t3を経由してさらに時間t4まで帯域制限値Bp1による増加を続ける。同様にトークンカウンタTc1(t)についても、時間t1から時間t2及びt3を経由して時間t4まで増加し続けることになる。

そして、この時間t4において、パケット長A4のパケットが入力して来たとき、このパケット長A4が図示ような長さであるとすると、Tp1(t4)-A4＞0であり、従ってステップS1からS3に進む。ステップS3では、図示の如くTc1(t4)-A4＞0であるのでさらにステップS5に進み、パケットの色付けを「青」とした色出力CL1を色選択部25に送ると共に、制限トークンカウンタTp1(t4)からパケット長A4をデクリメントし、同様に保証トークンカウンタTc1(t4)もパケット長A4だけデクリメントする。

以降、時間t5〜t9についても同様に色判定が行われ、これに対応した色出力CL1が色選択部25に与えられることになる。

pps計算部23
図3は、図1に示したpps計算部23の処理手順例を示したものである。この図3の処理手順と図2に示したbps計算部22の処理手順との違いは、入力パケットのパケット長Aの代わりにパケット数Pを用いる点である。従って、図3に示すように、図2の各ステップS1〜S5に対して図3ではダッシュを付けてそれぞれステップS1'〜S5'で対応して示している。この図3の処理手順を図4(2)に示したpps計算部23での色判定シーケンスを参照して説明する。

図示のように、縦軸は制限・保証トークンカウンタ（パケット数）を示しており、時間t=0の時には、初期値である制限バーストパケットTp2(0)(PBP)と保証バーストパケットTc2(0)(CBP)に設定されている。

そして、時間t1において、パケット数P1のパケットPKTがメータリング処理部11に入力されると、これを受けてpps計算部23では、図3のフローチャートにおいて、図4(2)に示すとおり、Tp2(0)-P1＞0であるのでステップS1’からステップS3’に進む。ステップS3’でも図示の如くTc2(0)-P1＞0であるのでステップS3’からステップS5’に進み、パケットの色付を「青」に設定すると共に、Tp2(t1)は“Tp2(0)-P1”に更新され、Tc2(t1)は“Tc2(0)-P1”に更新される。

この結果、図4(1)の時間t1においては、トークンカウンタTp1(t)及びTc1(t)はそれぞれバーストパケットTp2(0)及びTc2(0)からパケット数P1だけ減少した値になる。

そして、上記の式(1)及び(2)に示したように、時間τ秒毎にトークンカウンタTp2(t)の場合には制限帯域値Bp2（傾き）だけ増加することになる。なお、この場合の制限帯域値としては、上述の通り“80万pps”である。

また、保証トークンカウンタTc2(t)についても同様に保証帯域値Bc2（傾き）だけ時間τ秒毎に増加することになるので、トークンカウンタTp2(t)及びTc2(t)は、時間t1から時間t2に向かってそれぞれ傾きBp2及び傾きBc2で増加することになる。

時間t2において、制限トークンカウンタTp2(t2)は時間t1より帯域制限値Bp2だけ増加した値となっており、この時間t2において入力パケットのパケット数がP2であった場合には、図3のステップS1’においてTp2(t2)-P2＞0であるので、ステップS1’からステップS3’に進む。ステップS3’では図4(2)に示すとおり、Tc2(t2)-P2＞0であるので、ステップS5’に進み、時間t1のときと同様にパケットの色付けを「青」とすると共に、トークンカウンタTp2(t2)及びTc2(t2)を共にパケット数P2だけデクリメントする。すなわち、時間t2では、色付けが「黄」の色出力CL2が色選択部25に与えられることになる。

時間t3においても、パケット数P3に基づき、時間t1, t2と同様に色付けが「青」の色出力CL2が色選択部25に与えられることになる。

時間t4では、時間t3から同様にして時間τ秒の間にトークンカウンタTp2(t)は制限帯域値Bp2だけ増加し、トークンカウンタTc2(t)は保証帯域値Bc2だけ増加する。そして、
この時、パケット数P4のパケットが入力したとすると、Tp2(t4)-P4＞0であるので、ステップS3’に進む。ステップS3’では、Tc2(t4)-P4＜0であるので、ステップS4’に進み、パケットの色付けを「黄」とすると共に、トークンカウンタTp2(t4)をパケット数P4だけデクリメントする。すなわち、時間t4では、色付けが「黄」の色出力CL2が色選択部25に与えられることになる。

時間t5, t6においても、パケット数P5, P6に基づき、同様に色付けが「黄」の色出力CL2が色選択部25に与えられることになる。

そして、時間t7においては、パケット数P7のパケットが入力して来たとき、図示の例では、トークンカウンタTp2(t7)-P7＜0であるから、ステップS1’からS2’に進み、トークンカウンタTc2(t7)とパケット数P7との関係を見るまでもなく、パケットの色付けを「赤」とした色出力CL2を色選択部25に送る。

以降、時間t8, t9についても同様に行われ、色出力CL2が色選択部25に与えられることになる。

このように、bps計算部22からの色出力CL1と、pps計算部23からの色出力CL2を入力した色選択部25の出力が図4(3)に示されている。

すなわち、この色選択部25の選択アルゴリズムは、より廃棄すべき色のパケットを優先するということを示しており、色出力CL1とCL2から最終的にフレームの色を決定する。これら二つの色出力CL1とCL2のどちらかに「赤」があれば「赤」を選択し、双方に「赤」が無く、且つどちらかに「黄」があれば「黄」を選択し、それ以外の場合（いずれも「青」の場合）は「青」を選択して色情報付与部26に与えることになる。従って、色選択部25から出力される色選択信号は、図4(1)及び(2)における各時間t1〜t9において同図(3)に示すようになる。

このように、本発明のパケット中継方式の場合、「1Gbpsかつ80万pps未満」という設定が可能であるため、リクエストのフレーム長が長い場合は1Gbpsの回線帯域まで性能を発揮でき、かつリクエストのフレーム長が短い場合は端末の合計性能80万ppsまで性能を出すことが可能となる。

（付記１）
フロー毎の単位時間当りのデータビット数の所定制限帯域値及び入力パケットのパケット長に基づいて該入力パケットの色付けを行う第1のステップと、
フロー毎の単位時間当りのパケット数の所定制限帯域値及び入力パケットのパケット数に基づいて該入力パケットの色付けを行う第2のステップと、
該第1及び第2のステップでの色付けの内、廃棄すべき色を優先的に該入力パケットの色を決定する第3のステップと、
を備えたことを特徴とするパケット中継方法。
（付記２）
フロー毎の単位時間当りのデータビット数の所定保証帯域値及び入力パケットのパケット長に基づいて該入力パケットの色付けを行う第1のステップと、
フロー毎の単位時間当りのパケット数の所定保証帯域値及び入力パケットのパケット数に基づいて該入力パケットの色付けを行う第2のステップと、
該第1及び第2のステップでの色付けの内、確率的に廃棄させるべき色を優先的に該入力パケットの色を決定する第3のステップと、
を備えたことを特徴とするパケット中継方法。
（付記３）
フロー毎の単位時間当りのデータビット数の第1の所定制限帯域値、第1の所定保証帯域値及び入力パケットのパケット長に基づいて該入力パケットの色付けを行う第1のステップと、
フロー毎の単位時間当りのパケット数の第2の所定制限帯域値、第2の所定保証帯域値及び入力パケットのパケット数に基づいて該入力パケットの色付けを行う第2のステップと、
該第1及び第2のステップでの色付けの内、廃棄すべき色と通過させるべき色と確率的に廃棄すべき色のいずれかを決定する第3のステップと、
を備えたことを特徴とするパケット中継方法。
（付記４）付記１において、
該データビット数が、パケット入力時のデータビット数から該制限帯域値だけ増加する値であり、該パケット数が、パケット入力時のパケット数から制限帯域値だけ増加する値であり、該第1のステップで、該データビット数が、入力パケットのパケット長より小さいとき該入力パケットを該廃棄すべき色として赤色に色付けし、それ以外は青色に色付けし、該第2のステップで、該パケット数が該入力パケットのパケット数より小さいとき該入力パケットを赤色に色付けし、それ以外は青色に色付けすることを特徴としたパケット中継方法。
（付記５）付記２において、
該データビット数が、パケット入力時のデータビット数から該保証帯域値だけ増加する値であり、該パケット数が、パケット入力時のパケット数から該保証帯域値だけ増加する値であり、該第1のステップで、該データビット数が、入力パケットのパケット長より大きいとき該入力パケットを該通過させるべき色として青色に色付けし、それ以外は赤色に色付けし、該第2のステップで、該パケット数が該入力パケットのパケット数より大きいとき該入力パケットを青色に色付けし、それ以外は赤色に色付けすることを特徴としたパケット中継方法。
（付記６）付記３において、
該データビット数が、パケット入力時のデータビット数から該第1の所定制限帯域値及び該第1の所定保証帯域値だけそれぞれ増加する第1及び第2のビット数を含み、該パケット数が、パケット入力時のパケット数から該第2の所定制限帯域値及び該第2の所定保証帯域値だけそれぞれ増加する第1及び第2のパケット数を含み、該第1のステップで、該第1のビット数が、入力パケットのパケット長より小さいとき該入力パケットを該廃棄させるべき色として赤色に色付けし、該パケット長より大きく該第2のビット数も該パケット長より大きいとき該入力パケットを該通過させるべき色として青色に色付けし、これら以外は黄色に色付けし、該第2のステップで、該第1のパケット数が、入力パケットのパケット数より小さいとき該入力パケットを該廃棄させるべき色として赤色に色付けし、該パケット数より大きく該第2のパケット数も該パケット数より大きいとき該入力パケットを該通過させるべき色として青色に色付けし、これら以外は黄色に色付けするとともに、該第3のステップでは、競合したとき赤色、黄色、及び青色の順に優先して該入力パケットの色を決定することを特徴としたパケット中継方法。
（付記７）
フロー毎の単位時間当りのデータビット数の所定制限帯域値及び入力パケットのパケット長に基づいて該入力パケットの色付けを行う第1の手段と、
フロー毎の単位時間当りのパケット数の所定制限帯域値及び入力パケットのパケット数に基づいて該入力パケットの色付けを行う第2の手段と、
該第1及び第2の手段での色付けの内、廃棄すべき色を優先的に該入力パケットの色を決定する第3の手段と、
を備えたことを特徴とするパケット中継装置。
（付記８）
フロー毎の単位時間当りのデータビット数の所定保証帯域値及び入力パケットのパケット長に基づいて該入力パケットの色付けを行う第1の手段と、
フロー毎の単位時間当りのパケット数の所定保証帯域値及び入力パケットのパケット数に基づいて該入力パケットの色付けを行う第2の手段と、
該第1及び第2の手段での色付けの内、確率的に廃棄させるべき色を優先的に該入力パケットの色を決定する第3の手段と、
を備えたことを特徴とするパケット中継装置。
（付記９）
フロー毎の単位時間当りのデータビット数の第1の所定制限帯域値、第1の所定保証帯域値及び入力パケットのパケット長に基づいて該入力パケットの色付けを行う第1の手段と、
フロー毎の単位時間当りのパケット数の第2の所定制限帯域値、第2の所定保証帯域値及び入力パケットのパケット数に基づいて該入力パケットの色付けを行う第2の手段と、
該第1及び第2の手段での色付けの内、廃棄すべき色と通過させるべき色と一部廃棄すべき色のいずれかを決定する第3の手段と、
を備えたことを特徴とするパケット中継装置。
（付記１０）付記７において、
該データビット数が、パケット入力時のデータビット数から該所定制限帯域値だけ増加する値であり、該パケット数が、パケット入力時のパケット数から該所定制限帯域値だけ増加する値であり、該第1の手段が、該データビット数が、入力パケットのパケット長より小さいとき該入力パケットを該廃棄すべき色として赤色に色付けし、それ以外は青色に色付けし、該第2の手段が、該パケット数が該入力パケットのパケット数より小さいとき該入力パケットを赤色に色付けし、それ以外は青色に色付けすることを特徴としたパケット中継装置。
（付記１１）付記８において、
該データビット数が、パケット入力時のデータビット数から該所定保証帯域値だけ増加する値であり、該パケット数が、パケット入力時のパケット数から該所定保証帯域値だけ増加する値であり、該第1の手段が、該データビット数が、入力パケットのパケット長より大きいとき該入力パケットを該通過させるべき色として青色に色付けし、それ以外は赤色に色付けし、該第2の手段が、該パケット数が該入力パケットのパケット数より大きいとき該入力パケットを青色に色付けし、それ以外は赤色に色付けすることを特徴としたパケット中継装置。
（付記１２）付記９において、
該データビット数が、パケット入力時のデータビット数から該第1の所定制限帯域値及び該第1の所定保証帯域値だけそれぞれ増加する第1及び第2のビット数を含み、該パケット数が、パケット入力時のパケット数から該第2の所定制限帯域値及び該第2の所定保証帯域値だけそれぞれ増加する第1及び第2のパケット数を含み、該第1の手段が、該第1のビット数が、入力パケットのパケット長より小さいとき該入力パケットを該廃棄させるべき色として赤色に色付けし、該パケット長より大きく該第2のビット数も該パケット長より大きいとき該入力パケットを該通過させるべき色として青色に色付けし、これら以外は黄色に色付けし、該第2の手段が、該第1のパケット数が、入力パケットのパケット数より小さいとき該入力パケットを該廃棄させるべき色として赤色に色付けし、該パケット数より大きく該第2のパケット数も該パケット数より大きいとき該入力パケットを該通過させるべき色として青色に色付けし、これら以外は黄色に色付けするとともに、該第3の手段が、競合したとき赤色、黄色、及び青色の順に優先して該入力パケットの色を決定することを特徴としたパケット中継装置。
（付記１３）
フローごとの単位時間当りのデータビット数の所定制限帯域値、所定保証帯域値及び入力パケットのパケット長に基づいて該入力パケットの色付けを行う第1の手段と、
フローごとの単位時間当りのパケット数の所定制限帯域値、所定保証帯域値及び入力パケットのパケット数に基づいて該入力パケットの色付けを行う第2の手段と、
該第１及び第２の手段での色付けの内、廃棄すべき色を最優先とし、確率的に廃棄すべき色、通過させるべき色の優先順で該入力パケットの色を決定する第3の手段と、
を備えたことを特徴とするパケット中継装置。

本発明に係るパケット中継方法及び装置に用いられるメータリング処理部の一実施例を示したブロック図である。図1に示したメータリング処理部に用いられるbps計算部の処理手順例を示したフローチャート図である。図1に示したメータリング処理部に用いられるpps計算部の処理手順例を示したフローチャート図である。図2及び図3に示した各計算部による色判定シーケンスと色選択部出力を示した図である。本発明及び従来技術に適用されるパケット方式のネットワーク構成例を示した図である。図5に示したパケット中継装置の一般的な構成例を示したブロック図である。図5に示したネットワーク構成例におけるパケット中継方式[1]を示した図である。図5に示したネットワーク構成例におけるパケット中継方式[2]を示した図である。

符号の説明

1 ネットワーク
2 パケット中継装置
3 L2スイッチ
4, 4_1, 4_2 負荷分散装置
5, 5_1〜5_n 端末(サーバ)
11 メータリング処理部
12 WRED処理部
13 キュー部
14 スケージューラ部
21 情報設定部
22 bps計算部
23 pps計算部
24 情報抽出部
25 色選択部
26 色情報付与部
図中、同一符号は同一又は相当部分を示す。

Claims

フロー毎の単位時間当りのデータビット数の所定制限帯域値及び入力パケットのパケット長に基づいて該入力パケットの色付けを行う第1のステップと、
フロー毎の単位時間当りのパケット数の所定制限帯域値及び入力パケットのパケット数に基づいて該入力パケットの色付けを行う第2のステップと、
該第1及び第2のステップでの色付けの内、廃棄すべき色を優先的に該入力パケットの色を決定する第3のステップと、
を備え、該データビット数が、パケット入力時のデータビット数から該所定制限帯域値だけ増加する値であり、該パケット数が、パケット入力時のパケット数から該所定制限帯域値だけ増加する値であり、該第1のステップで、該データビット数が、入力パケットのパケット長より小さいとき該入力パケットを該廃棄すべき色として赤色に色付けし、それ以外は青色に色付けし、該第2のステップで、該パケット数が該入力パケットのパケット数より小さいとき該入力パケットを赤色に色付けし、それ以外は青色に色付けすることを特徴とするパケット中継方法。
フロー毎の単位時間当りのデータビット数の所定保証帯域値及び入力パケットのパケット長に基づいて該入力パケットの色付けを行う第1のステップと、
フロー毎の単位時間当りのパケット数の所定保証帯域値及び入力パケットのパケット数に基づいて該入力パケットの色付けを行う第2のステップと、
該第1及び第2のステップでの色付けの内、確率的に廃棄させるべき色を優先的に該入力パケットの色を決定する第3のステップと、
を備え、該データビット数が、パケット入力時のデータビット数から該所定保証帯域値だけ増加する値であり、該パケット数が、パケット入力時のパケット数から該所定保証帯域値だけ増加する値であり、該第1のステップで、該データビット数が、入力パケットのパケット長より大きいとき該入力パケットを該通過させるべき色として青色に色付けし、それ以外は赤色に色付けし、該第2のステップで、該パケット数が該入力パケットのパケット数より大きいとき該入力パケットを青色に色付けし、それ以外は赤色に色付けすることを特徴とするパケット中継方法。
フロー毎の単位時間当りのデータビット数の第1の所定制限帯域値、第1の所定保証帯域値及び入力パケットのパケット長に基づいて該入力パケットの色付けを行う第1のステップと、
フロー毎の単位時間当りのパケット数の第2の所定制限帯域値、第2の所定保証帯域値及び入力パケットのパケット数に基づいて該入力パケットの色付けを行う第2のステップと、
該第1及び第2のステップでの色付けの内、廃棄すべき色と通過させるべき色と確率的に廃棄すべき色のいずれかを決定する第3のステップと、
を備え、該データビット数が、パケット入力時のデータビット数から該第1の所定制限帯域値及び該第1の所定保証帯域値だけそれぞれ増加する第1及び第2のビット数を含み、該パケット数が、パケット入力時のパケット数から該第2の所定制限帯域値及び該第2の所定保証帯域値だけそれぞれ増加する第1及び第2のパケット数を含み、該第1のステップで、該第1のビット数が、入力パケットのパケット長より小さいとき該入力パケットを該廃棄させるべき色として赤色に色付けし、該パケット長より大きく該第2のビット数も該パケット長より大きいとき該入力パケットを該通過させるべき色として青色に色付けし、これら以外は黄色に色付けし、該第2のステップで、該第1のパケット数が、入力パケットのパケット数より小さいとき該入力パケットを該廃棄させるべき色として赤色に色付けし、該パケット数より大きく該第2のパケット数も該パケット数より大きいとき該入力パケットを該通過させるべき色として青色に色付けし、これら以外は黄色に色付けするとともに、該第3のステップでは、競合したとき赤色、黄色、及び青色の順に優先して該入力パケットの色を決定することを特徴とするパケット中継方法。
フロー毎の単位時間当りのデータビット数の所定制限帯域値及び入力パケットのパケット長に基づいて該入力パケットの色付けを行う第1の手段と、
フロー毎の単位時間当りのパケット数の所定制限帯域値及び入力パケットのパケット数に基づいて該入力パケットの色付けを行う第2の手段と、
該第1及び第2の手段での色付けの内、廃棄すべき色を優先的に該入力パケットの色を決定する第3の手段と、
を備え、該データビット数が、パケット入力時のデータビット数から該所定制限帯域値だけ増加する値であり、該パケット数が、パケット入力時のパケット数から該所定制限帯域値だけ増加する値であり、該第1の手段が、該データビット数が、入力パケットのパケット長より小さいとき該入力パケットを該廃棄すべき色として赤色に色付けし、それ以外は青色に色付けし、該第2の手段が、該パケット数が該入力パケットのパケット数より小さいとき該入力パケットを赤色に色付けし、それ以外は青色に色付けすることを特徴とするパケット中継装置。
フロー毎の単位時間当りのデータビット数の所定保証帯域値及び入力パケットのパケット長に基づいて該入力パケットの色付けを行う第1の手段と、
フロー毎の単位時間当りのパケット数の所定保証帯域値及び入力パケットのパケット数に基づいて該入力パケットの色付けを行う第2の手段と、
該第1及び第2の手段での色付けの内、確率的に廃棄させるべき色を優先的に該入力パケットの色を決定する第3の手段と、
を備え、該データビット数が、パケット入力時のデータビット数から該所定保証帯域値だけ増加する値であり、該パケット数が、パケット入力時のパケット数から該所定保証帯域値だけ増加する値であり、該第1の手段が、該データビット数が、入力パケットのパケット長より大きいとき該入力パケットを該通過させるべき色として青色に色付けし、それ以外は赤色に色付けし、該第2の手段が、該パケット数が該入力パケットのパケット数より大きいとき該入力パケットを青色に色付けし、それ以外は赤色に色付けすることを特徴とするパケット中継装置。
フロー毎の単位時間当りのデータビット数の第1の所定制限帯域値、第1の所定保証帯域値及び入力パケットのパケット長に基づいて該入力パケットの色付けを行う第1の手段と、
フロー毎の単位時間当りのパケット数の第2の所定制限帯域値、第2の所定保証帯域値及び入力パケットのパケット数に基づいて該入力パケットの色付けを行う第2の手段と、
該第1及び第2の手段での色付けの内、廃棄すべき色と通過させるべき色と一部廃棄すべき色のいずれかを決定する第3の手段と、
を備え、該データビット数が、パケット入力時のデータビット数から該第1の所定制限帯域値及び該第1の所定保証帯域値だけそれぞれ増加する第1及び第2のビット数を含み、該パケット数が、パケット入力時のパケット数から該第2の所定制限帯域値及び該第2の所定保証帯域値だけそれぞれ増加する第1及び第2のパケット数を含み、該第1の手段が、該第1のビット数が、入力パケットのパケット長より小さいとき該入力パケットを該廃棄させるべき色として赤色に色付けし、該パケット長より大きく該第2のビット数も該パケット長より大きいとき該入力パケットを該通過させるべき色として青色に色付けし、これら以外は黄色に色付けし、該第2の手段が、該第1のパケット数が、入力パケットのパケット数より小さいとき該入力パケットを該廃棄させるべき色として赤色に色付けし、該パケット数より大きく該第2のパケット数も該パケット数より大きいとき該入力パケットを該通過させるべき色として青色に色付けし、これら以外は黄色に色付けするとともに、該第3の手段が、競合したとき赤色、黄色、及び青色の順に優先して該入力パケットの色を決定することを特徴とするパケット中継装置。