(57)【要約】【課題】単一キューに複数の優先度のパケットを混在した場合でも、優先度に応じた優先転送制御を実現する。【解決手段】優先制御部３１により、転送優先度に基づいて異なる複数のカラーにカラーリングされたパケットを論理キュー格納部１１に格納して単一キューでキューイングする際に、優先度別管理用キュー格納部２１にて、パケット流入時に、『流入パケット長』と『待ちパケット列の長さ』と『流入パケットの優先度』を管理し、論理キュー格納部１１で格納済みパケットを廃棄するとともに、格納済みパケットから廃棄すべきパケット量を確保できない場合には廃棄できなかった量に応じた確率で流入パケットを廃棄する。特に、格納済みパケットの廃棄においては、流入パケットより優先度の低いパケットを対象に、格納済みパケットを優先度別のリストとして管理し、キュー内の全パケットのなかから優先度の低いものより順番に廃棄する。【選択図】      図１
2011147033.tif 000002
【特許請求の範囲】
【請求項１】
転送優先度に基づいて異なる複数のカラーにカラーリングされた流入パケットを単一キューでキューイングするキュー制御装置において、
前記流入パケットを順に格納する論理キュー格納部と、
前記論理キュー格納部に格納されているパケットを優先度別に格納する優先度別管理用キュー格納部と、
前記優先度別管理用キュー格納部に格納されたパケットの優先度を参照して、前記論理キュー格納部に対して一定以上のキュー長を有するパケットが流入されたとき、その流入パケットの優先度より低い格納済みパケットを前記論理キュー格納部から廃棄して前記流入パケットを前記論理キュー格納部に格納する優先制御部と
を具備することを特徴とするキュー制御装置。
【請求項２】
前記優先度別管理用キュー格納部は、前記論理キュー格納部の格納済みパケットそれぞれのパケット長、優先度、パケット数を管理し、
前記優先制御部は、前記パケットの流入時にそのパケット長、優先度を取得して、前記論理キュー格納部の格納済みパケットの管理情報と比較することで前記廃棄のパケットを選別することを特徴とする請求項１記載のキュー制御装置。
【請求項３】
前記優先制御部は、前記キューの待ちパケット列の長さに応じた係数を前記流入パケット長に乗じて決定し、前記格納済みパケットのうち前記流入パケットより優先度の低いバケットに対し、流入パケット長のα倍（０＜α＜１）に相当する量を廃棄するものとし、格納済みパケットから必要なパケット量を廃棄できない場合は、廃棄できなかった量に応じた確率で流入パケットを廃棄することを特徴とする請求項１記載のキュー制御装置。
【請求項４】
前記優先制御部は、前記流入パケットに対する廃棄パケットの割合の算定において、前記格納済みパケットの列長に二つの基準値Ｌ１，Ｌ２（０≦Ｌ１≦Ｌ２≦バッファ長）を設け、前記流入パケット列の長さＬによって流入パケット格納・格納済みパケット廃棄を行う場合に、前記流入パケット列の長さがＬ１以下の場合には、前記流入パケット・格納済みパケットのいずれからも廃棄は行わす、前記流入パケット列の長さがＬ２以上の場合には、前記流入パケットと同じ長さだけ格納済みパケットを廃棄（但し再優先度のパケットは廃棄対象外）し、列長がＬ１以上Ｌ２未満の場合には、列の長さのＬ１超過の程度に比例して、Ｌ１で廃棄率０、Ｌ２で廃棄率γ（０＜γ≦１）となるように線形に廃棄率を決定することを特徴とする請求項１記載のキュー制御装置。
【請求項５】
転送優先度に基づいて異なる複数のカラーにカラーリングされた流入パケットを単一キューでキューイングするために、前記流入パケットを論理キュー格納部に順に格納し、前記論理キュー格納部に格納されているパケットを優先度別に優先度別管理用キュー格納部に格納するキュー制御装置に用いられ、
前記優先度別管理用キュー格納部に格納されたパケットの優先度を参照し、
前記論理キュー格納部に対して一定以上のキュー長を有するパケットが流入されたことを検知し、
前記検知された流入パケットの優先度を判別し、
前記論理キュー格納部からより優先度の低い格納済みパケットを廃棄し、
前記流入パケットを前記論理キュー格納部に格納することを特徴とするキュー制御方法。
【請求項６】
前記論理キュー格納部の格納済みパケットそれぞれのパケット長、優先度、パケット数を管理し、
前記パケットの流入時にそのパケット長、優先度を取得して、前記論理キュー格納部の格納済みパケットの管理情報と比較することで前記廃棄のパケットを選別することを特徴とする請求項５記載のキュー制御方法。
【請求項７】
前記キューの待ちパケット列の長さに応じた係数を前記流入パケット長に乗じて決定し、前記格納済みパケットのうち前記流入パケットより優先度の低いバケットに対し、流入パケット長のα倍（０＜α＜１）に相当する量を廃棄するものとし、格納済みパケットから必要なパケット量を廃棄できない場合は、廃棄できなかった量に応じた確率で流入パケットを廃棄することを特徴とする請求項５記載のキュー制御方法。
【請求項８】
前記流入パケットに対する廃棄パケットの割合の算定において、前記格納済みパケットの列長に二つの基準値Ｌ１，Ｌ２（０≦Ｌ１≦Ｌ２≦バッファ長）を設け、前記流入パケット列の長さＬによって流入パケット格納・格納済みパケット廃棄を行う場合に、前記流入パケット列の長さがＬ１以下の場合には、前記流入パケット・格納済みパケットのいずれからも廃棄は行わず、前記流入パケット列の長さがＬ２以上の場合には、前記流入パケットと同じ長さだけ格納済みパケットを廃棄（但し再優先度のパケットは廃棄対象外）し、列長がＬ１以上Ｌ２未満の場合には、列の長さのＬ１超過の程度に比例して、Ｌ１で廃棄率０、Ｌ２で廃棄率γ（０＜γ≦１）となるように線形に廃棄率を決定することを特徴とする請求項５記載のキュー制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケット通信における単一キュー内で複数の転送品質クラスの優先制御を行うキュー制御装置とその制御方法に関する。
【背景技術】
【０００２】
パケット通信において、転送品質クラス毎の転送優先度に基づいてカラーリングされたパケットを単一キューでキューイングする場合、従来技術では、単一キューで複数の優先度の制御を行う技術としては、ＷＲＥＤ（Weighted Random Early Detection：例えば、非特許文献１参照）のように、キューへのパケット流入時に一回だけ、キュー長に応じて確率的廃棄を行う方式が存在している。
【０００３】
しかしながら、上記の従来技術では、一度キューに格納されたパケットは優先度の低いパケットであっても廃棄されないため、低優先度のパケットが格納された後に高優先度のパケットが多量に流入してくると、低優先度パケットがキュー前方に格納されていることによって高優先度のパケットがキューから溢れてパケットロスになることがあった。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】ＷＲＥＤ（Weighted Random Early Detection）ＲＦＣ２５９７，ＲＦＣ２５９８
【発明の概要】
【発明が解決しようとする課題】
【０００５】
以上述べたように、従来のキュー制御装置では、一度キューに格納されたパケットは優先度の低いパケットであっても廃棄されないため、低優先度のパケットが格納された後に高優先度のパケットが多量に流入してくると、低優先度パケットがキュー前方に格納されていることによって高優先度のパケットがキューから溢れてパケットロスになることがあった。
【０００６】
本発明は、上記の事情を鑑みてなされたもので、単一キューに複数の優先度のパケットを混在した場合でも、優先度に応じた優先転送制御を実現するキュー制御装置とその制御方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明に係るキュー制御装置は以下のような態様の構成とする。
（１）転送優先度に基づいて異なる複数のカラーにカラーリングされた流入パケットを単一キューでキューイングするキュー制御装置において、前記流入パケットを順に格納する論理キュー格納部と、前記論理キュー格納部に格納されているパケットを優先度別に格納する優先度別管理用キュー格納部と、前記優先度別管理用キュー格納部に格納されたパケットの優先度を参照して、前記論理キュー格納部に対して一定以上のキュー長を有するパケットが流入されたとき、その流入パケットの優先度より低い格納済みパケットを前記論理キュー格納部から廃棄して前記流入パケットを前記論理キュー格納部に格納する優先制御部とを具備する態様とする。
【０００８】
（２）（１）の構成において、前記優先度別管理用キュー格納部は、前記論理キュー格納部の格納済みパケットそれぞれのパケット長、優先度、パケット数を管理し、前記優先制御部は、前記パケットの流入時にそのパケット長、優先度を取得して、前記論理キュー格納部の格納済みパケットの管理情報と比較することで前記廃棄のパケットを選別する態様とする。
【０００９】
（３）（１）の構成において、前記優先制御部は、前記キューの待ちパケット列の長さに応じた係数を前記流入パケット長に乗じて決定し、前記格納済みパケットのうち前記流入パケットより優先度の低いバケットに対し、流入パケット長のα倍（０＜α＜１）に相当する量を廃棄するものとし、格納済みパケットから必要なパケット量を廃棄できない場合は、廃棄できなかった量に応じた確率で流入パケットを廃棄する態様とする。
【００１０】
（４）（１）の構成において、前記優先制御部は、前記流入パケットに対する廃棄パケットの割合の算定において、前記格納済みパケットの列長に二つの基準値Ｌ１，Ｌ２（０≦Ｌ１≦Ｌ２≦バッファ長）を設け、前記流入パケット列の長さＬによって流入パケット格納・格納済みパケット廃棄を行う場合に、前記流入パケット列の長さがＬ１以下の場合には、前記流入パケット・格納済みパケットのいずれからも廃棄は行わず、前記流入パケット列の長さがＬ２以上の場合には、前記流入パケットと同じ長さだけ格納済みパケットを廃棄（但し再優先度のパケットは廃棄対象外）し、列長がＬ１以上Ｌ２未満の場合には、列の長さのＬ１超過の程度に比例して、Ｌ１で廃棄率０、Ｌ２で廃棄率γ（０＜γ≦１）となるように線形に廃棄率を決定する態様とする。
【００１１】
また、本発明に係るキュー制御方法は以下のような態様の構成とする。
（５）転送優先度に基づいて異なる複数のカラーにカラーリングされた流入パケットを単一キューでキューイングするために、前記流入パケットを論理キュー格納部に順に格納し、前記論理キュー格納部に格納されているパケットを優先度別に優先度別管理用キュー格納部に格納するキュー制御装置に用いられ、前記優先度別管理用キュー格納部に格納されたパケットの優先度を参照し、前記論理キュー格納部に対して一定以上のキュー長を有するパケットが流入されたことを検知し、前記検知された流入パケットの優先度を判別し、前記論理キュー格納部からより優先度の低い格納済みパケットを廃棄し、前記流入パケットを前記論理キュー格納部に格納する態様とする。
【００１２】
（６）（５）の構成において、前記論理キュー格納部の格納済みパケットそれぞれのパケット長、優先度、パケット数を管理し、前記パケットの流入時にそのパケット長、優先度を取得して、前記論理キュー格納部の格納済みパケットの管理情報と比較することで前記廃棄のパケットを選別する態様とする。
【００１３】
（７）（５）の構成において、前記キューの待ちパケット列の長さに応じた係数を前記流入パケット長に乗じて決定し、前記格納済みパケットのうち前記流入パケットより優先度の低いバケットに対し、流入パケット長のα倍（０＜α＜１）に相当する量を廃棄するものとし、格納済みパケットから必要なパケット量を廃棄できない場合は、廃棄できなかった量に応じた確率で流入パケットを廃棄する態様とする。
【００１４】
（８）（５）の構成において、前記流入パケットに対する廃棄パケットの割合の算定において、前記格納済みパケットの列長に二つの基準値Ｌ１，Ｌ２（０≦Ｌ１≦Ｌ２≦バッファ長）を設け、前記流入パケット列の長さＬによって流入パケット格納・格納済みパケット廃棄を行う場合に、前記流入パケット列の長さがＬ１以下の場合には、前記流入パケット・格納済みパケットのいずれからも廃棄は行わず、前記流入パケット列の長さがＬ２以上の場合には、前記流入パケットと同じ長さだけ格納済みパケットを廃棄（但し再優先度のパケットは廃棄対象外）し、列長がＬ１以上Ｌ２未満の場合には、列の長さのＬ１超過の程度に比例して、Ｌ１で廃棄率０、Ｌ２で廃棄率γ（０＜γ≦１）となるように線形に廃棄率を決定する態様とする。
【発明の効果】
【００１５】
上記構成では、キューに格納済みのパケットも廃棄対象とするため、トラヒック増大時の高優先度パケットのスループットの改善が可能となる。特に、高優先度パケット流入時の低優先度パケット廃棄メカニズムとして、格納済みパケットも廃棄対象としているので、列長の伸長時に流入した高優先度のパケットに対し、前方の低優先度パケットを廃棄して当該高優先度パケットをキュー出側に詰めることが可能となり、これによって、高優先度パケットの遅延を抑制できる。また同時に、混雑時に列長を短縮させることができるので、高優先度パケットのトラヒックのスループットを向上させることができる。
【００１６】
また、廃棄パケットの選択においては、異なる優先度の待ちパケット数を一体で管理し、低優先側のパケットがすべて廃棄されるまでは高優先側のパケットが廃棄されないようにしているので、低優先度側のパケットにおいても異なる優先度間での完全優先を実現することが可能となる。
【００１７】
したがって、本発明によれば、単一キューに複数の優先度のパケットを混在した場合でも、優先度に応じた優先転送制御を実現するキュー制御装置とその制御方法を提供することができる。
【図面の簡単な説明】
【００１８】
【図１】本発明に係るキュー制御装置の一実施形態を示すブロック構成図。
【図２】上記実施形態の装置に用いられる優先制御機能部のパケット格納動作を説明するためのフローチャート。
【図３】上記実施形態の優先制御機能において、論理キュー内の格納済みパケット長Ｌが小さい（Ｌ１未満）の場合のパケット格納例を示す図。
【図４】上記実施形態の優先制御機能において、廃棄割合αの評価関数例を示す図。
【図５】上記実施形態の優先制御機能において、論理キュー内の格納済みパケット長Ｌが一定範囲内に収まる（Ｌ１以上Ｌ２未満）の場合のパケット格納例を示す図。
【図６】上記実施形態の優先制御機能において、論理キュー内の格納済みパケットが一定量存在（Ｌ１以上Ｌ２未満）の場合の動作例を示す図。
【図７】上記実施形態の優先制御機能において、論理キュー内の格納済みパケット長Ｌが大きい（Ｌ２以上）の場合のパケット格納例を示す図。
【発明を実施するための形態】
【００１９】
以下、図面を参照して本発明の実施の形態を詳細に説明する。  
図１は、パケット通信において、単一キュー内で複数の転送品質クラスの優先制御を行うキュー制御装置の構成を示すブロック図である。この装置は、物理キュー（図示せず）に格納されているパケットを格納順に記録した論理キュー格納部１１と、同論理キュー格納部１１内に格納されているパケットを優先度別に記録する優先度別管理用キュー格納部２１と、流入パケット長・優先度、および格納済みパケット数に基づいて格納済みパケットを廃棄する制御を行う優先制御機能部３１より構成される。
【００２０】
ここで、論理キュー格納部１１では、キュー長について２つの閾値Ｌ１，Ｌ２を保持する。また、優先度別管理用キュー格納部２１には、優先度毎に流入パケットをＦＩＦＯ（First In First Out）メモリによって管理する優先度毎パケット管理用キュー格納領域２２が設定される。このキュー格納領域２２は、許容される優先度の種類の数だけ設定される。尚、図では優先度がｍ通り存在する場合のキューの構成を示している。各々の優先度毎パケット管理用キュー格納領域２２は、格納済みパケット量の情報を保持する。
【００２１】
上記構成において、以下に処理の流れについて、例をあげて説明する。
まず、キューに流入するパケットの優先度（単一キューに複数の異なる優先度のパケットを対応付け）について説明する。
本装置にパケットが流入されると、パケットに設定された転送品質クラスに基づき、流入先のキューが割り振られる。本装置の優先制御機能を有するキューには、転送品質クラス以外に複数の異なる廃棄優先度を持つパケットが割り振られる。例えば、転送優先クラスＡＦ１に対しては、ＩＥＴＦ（Internet Engineering Task Force）仕様で規定される複数の廃棄優先度のパケット（ＡＦ１１からＡＦ１４までの４通り）が単一キューに割り振られるケースが有り得る。また、この他にも、ネットワークの設計ポリシによって、さらに多数の優先度を設ける可能性も考えられる。
【００２２】
流入するパケットは、キューに割り当てられる前に、優先度に応じたカラーリングが行われる。本実施形態においては、ここで付与されたカラーに基づいてキュー内での優先度評価が行われる。以下では、対象キューに割り当てられるパケットのうち、優先度が最も高いものをＰ１、次に優先度の高いものをＰ２、以降順にＰ３，Ｐ４，…と表記する。
【００２３】
ここで、キューでの格納済みパケットの管理について説明する。
本発明を適用する装置では、キューに格納されている全パケットに対して、パケットが格納されているメモリ空間上のアドレスを格納順に管理する論理キュー格納部１１を持つ。また、当該装置では、この論理キュー格納部１１と別に、優先度別管理用キュー格納部２１をもつ。この優先度別管理用キュー格納部２１に格納されるキューは、パケットが格納されているメモリ空間上のアドレスを優先度別に保持するリストである。論理キュー格納部１１では、論理キューの先頭から格納パケットの最後尾までの長さ（格納済みパケット列の長さ）をパラメータＬとして管理する。また、廃棄制御時の係数決定のため、二つの閾値Ｌ１，Ｌ２（Ｌ１＜Ｌ２）をもつ。
【００２４】
図２は、図１に示す優先制御機能部３１において、流入パケットをキュー格納部１１，２１に格納する制御動作を示すフローチャートである。
まず、キューへのパケット流入時の判定処理について説明する。
図示しないネットワークインターフェースより本装置へのパケット流入の通知を受けると（ステップＳ１１）、この通知により流入時の論理キューのキュー長（Ｌ）を取得すると共に、流入パケットのパケット長（ｎ）、優先度（ｐ）を取得する（ステップＳ１２）。続いて、以下の判断処理に基づいて、『流入パケット長』と『格納済みパケット列の長さ』と『流入パケットの優先度』に応じて、格納済みパケットの廃棄、流入パケットの格納／廃棄を行う。格納済みパケット列の長さＬは、流入パケットが格納される前の値で評価を行う。具体的には、格納済みパケット列の長さＬを予め設定された閾値Ｌ１，Ｌ２と比較する（ステップＳ１３）。
【００２５】
（i）ステップＳ１３の比較結果において、格納済みパケット列の長さＬが閾値Ｌ１未満の場合（Ｌ＜Ｌ１）は、格納済みパケットの廃棄や流入パケットの廃棄は行わず、流入したパケットをキューの最後尾に追加する。具体的には、ステップＳ１４において、流入パケットを優先度別キューＰｐに格納し、当該キューのキュー長（ｌｐ）に流入パケット長ｎを加算する（図６のＳＴ４）。また、論理キュー１１に格納し、論理キューのキュー長（Ｌ）に流入パケット長ｎを加算して（図６のＳＴ５）、一連の処理を終了する。
【００２６】
このときの流入パケットの優先制御動作例を図３に示す。図３は論理キュー内の格納済みパケット長Ｌが小さい（Ｌ１未満）場合のパケット格納例を示すもので、流入するパケットが、流入パケットの優先度によらず、格納済みパケットを廃棄することなく全て格納される様子を示している。ここで、図３（ａ）は流入パケットの優先度が最大（Ｐ１）の場合、図３（ｂ）は流入パケットの優先度が次に高い（Ｐ２）の場合である。
【００２７】
（ii）ステップＳ１３の比較結果において、格納済みパケット列の長さＬが閾値Ｌ１以上で閾値Ｌ２未満の場合（Ｌ１≦Ｌ＜Ｌ２）は、以下の手順で、格納済みパケットの廃棄と流入パケットの格納を行う。
まず、ステップＳ１５において、格納済みパケット長Ｌの長さに応じて格納済みパケットの廃棄量（Ｄ）を算定する（図６のＳＴ１）。流入パケット長をｎ、廃棄率（割合）をαとする。廃棄率（割合）αは、格納済みパケット列の長さＬの閾値Ｌ１超過の程度に応じて決定される係数とする。図４に廃棄率αの評価関数例として、待ちパケット列の長さ（流入パケット格納前）と廃棄率αとの関係を示す。格納済みパケット列の長さＬがＬ１以上Ｌ２未満の場合の廃棄率αは、格納済みパケット列の長さＬのＬ１超過の程度に比例して、Ｌ１で廃棄率０、Ｌ２で廃棄率γ（０＜γ≦１）となるように線形に決定される係数である。このとき、格納済みパケットから廃棄する量ＤはＤ＝α×ｎと表される。
【００２８】
続いて、ステップＳ１６において、どの格納済みパケットを廃棄するかの評価を優先度別管理キューにおいて行い、優先度別管理キューで評価した結果に基づき、廃棄対象となったパケットに対し、論理キュー上で対応するパケットの廃棄処理を行う。具体的には、流入パケットの優先度よりも低い優先度のパケットに対して、優先度の低いものから順に、流入パケット長より算出される廃棄量Ｄ（＝α×ｎ）に相当する量のパケットを廃棄パケットとする。すなわち、優先度別管理キュー（Ｐ１，Ｐ２，…）のうち、優先度が流入パケットの優先度より低いキュー（Ｐｘ：ｘ≧ｐ＋１）のパケットに対し、廃棄パケット総量が廃棄すべき量Ｄ以上になるまで（図６のＳＴ２）、優先度の低いキューから順に、優先度別管理用キューにおいて、各キューの後ろから順に廃棄する対象となる格納済みパケットを特定し、前項に対応するパケットを論理キューから削除する（図６のＳＴ３）。このとき、（図６のＳＴ４）流入パケットを優先度別管理キュー格納部２１において対応するキューの最後尾に追加し、優先度別管理キューでのパケット追加を論理キューに反映する。
【００２９】
続いて、ステップＳ１７において、廃棄総量がＤ以上となったか判断し、廃棄総量がＤ以上ならばステップＳ１８に移行し、廃棄対象と特定した格納済みパケットを廃棄した後、先に述べたステップＳ１４の処理に移行し、その処理の完了後に一連の処理を終了する。廃棄総量がＤ未満ならば、ステップＳ１９において、流入パケットの優先度ｐが２以上か判断し、ｐ＝１ならばステップＳ１８に移行し、廃棄対象と特定した格納済みパケットを廃棄した後、先に述べたステップＳ１４に移行し、その処理の完了後に、一連の処理を終了する。ｐ＝２ならば、ステップＳ２０において、流入パケットを廃棄達成度に比例した確率（β＝１−（Ｄ−廃棄総量）／Ｄ）で廃棄する。ここでステップＳ２１において、これまでの処理で流入パケットが廃棄されたか否かを判断し、流入パケットが廃棄された場合には直ちに一連の処理を終了し、流入パケットが廃棄されなかった場合には、ステップＳ２２に進む。ステップＳ２２では、廃棄対象として特定した格納済みパケットを廃棄したものとし、かつ、流入パケットを格納した場合の、論理キューのパケット列の長さＬについて、Ｌが閾値Ｌ２以上か否かを判断し、ＬがＬ２以上（ＹＥＳ）の場合には流入パケットを廃棄して（Ｓ２２）一連の処理を終了し、Ｌ２より小さい場合（ＮＯ）にはステップＳ１８に移行して廃棄対象と特定した格納済みパケットを廃棄した後、先に述べたステップＳ１４に移行し、その処理の完了後に、一連の処理を終了する。
【００３０】
この様子を図５に示す。図５は、論理キュー内の格納済みパケット長Ｌが一定範囲内に収まる（Ｌ１以上Ｌ２未満）の場合のパケット格納例を示すもので、図５において、（ａ），（ｂ），（ｃ）はそれぞれ流入パケットの優先度が最大（Ｐ１）の場合、次の値（Ｐ２）の場合、さらに次の値（Ｐ３）の場合に、パケット流入前、格納判定処理、パケット格納後の様子を示している。この場合には、入力パケットより低優先のパケットが廃棄される。但し、廃棄される格納済みパケットの数は入力パケット長より小さく設定されるものとする。
【００３１】
図６に、論理キュー内の格納済みパケットが一定量存在する場合（Ｌ１以上Ｌ２未満）の動作例を示す。まず、（ＳＴ１）パケット入力前のキュー長と入力パケット長から廃棄パケット長を算出する。図では、キュー長の閾値超過度が０．５で、入力パケット長が４の場合、入力パケット格納時に廃棄する格納済みパケット長２（＝０．５×４）である。次に、（ＳＴ２）クラス別キューにおいて、格納済みパケットのうち、低優先のものから順に、廃棄パケット長分のパケットを廃棄する。図では、優先度の低い側から順に、廃棄パケット長２を廃棄する。図では、Ｐ５から１パケット廃棄し、Ｐ４から残りの１パケット（入力側）を廃棄する。続いて、（ＳＴ３）廃棄結果を論理キューに反映し、（ＳＴ４）流入パケットをクラス別キューに格納し、（ＳＴ５）格納結果を論理キューに反映させる。
【００３２】
（iii）ステップＳ１３の比較結果において、格納済みパケット列の長さＬが閾値Ｌ２以上（Ｌ２≦Ｌ）の場合は、ステップＳ２４において、格納済みパケットから廃棄すべき量（Ｄ）に流入パケット長ｎを設定する。そして、前項（ii）と同様に（但し、廃棄パケットの数は流入パケット長と同等（前項でα＝１とする場合と同様）とする）、流入パケット長と同量の格納済みパケット（但し流入パケットの優先度よりも低優先度のパケットに限る）を廃棄し、流入パケットをキューの最後尾に追加する。流入パケットより低優先の格納済みパケットの総量が、流入パケット長よりも小さい場合、格納済みパケットから廃棄できない量に応じた確率で流入パケットを廃棄し、廃棄されなかった場合に流入パケットを新たにキュー最後尾に追加する。
【００３３】
但し、最も高い優先度のパケットの場合は、廃棄可能な格納済みパケットの量が廃棄すべきパケット量に満たない場合であっても流入パケットからの廃棄は行わず（Ｌ２超過による廃棄は行わないが、キュー長超過が起こった場合には廃棄は発生する）、格納済みパケットに対する可能な廃棄を行ったうえで、流入パケットをキューの最後尾に追加する。流入パケットの優先制御動作例を図７に示す。図７は論理キュー内の格納済みパケット長Ｌが大きい（Ｌ２以上）の場合のパケット格納例を示すもので、（ａ），（ｂ），（ｃ）はそれぞれ流入パケットの優先度が最大（Ｐ１）の場合、次の値（Ｐ２）の場合、さらに次の値（Ｐ３）の場合に、パケット流入前、格納判定処理、パケット格納後の様子を示している。この場合は、閾値Ｌ２を超えてキューに格納されるのはＰ１のみであり、全パケットがＰ１の時に限る。
【００３４】
以上のように、上記実施形態の装置では、転送優先度に基づいて異なる複数のカラーにカラーリングされたパケットを単一キューでキューイングする際に、パケット流入時に、『流入パケット長』と『待ちパケット列の長さ』と『流入パケットの優先度』に応じて、格納済みパケットを廃棄するとともに、格納済みパケットから廃棄すべきパケット量を確保できない場合には廃棄できなかった量に応じた確率で流入パケットを廃棄する。特に、格納済みパケットの廃棄においては、流入パケットより優先度の低いパケットを対象に、格納済みパケットを優先度別のリストとして管理し、キュー内の全パケットのなかから優先度の低いものより順番に廃棄する。
【００３５】
また、廃棄量は待ちパケット列の長さに応じた係数を、流入パケット長に乗じて決定し、格納済みパケットのうち、流入パケットより優先度の低いパケットに対し、流入パケット長のα倍（０＜α＜１）に相当する量を廃棄する。格納済みパケットから必要なパケット量を廃棄できない場合は、廃棄できなかった量に応じた確率で流入パケットを廃棄する。
【００３６】
また、流入パケットに対する廃棄パケットの割合の算定において、格納済みパケットの列長に二つの基準値Ｌ１，Ｌ２（０≦Ｌ１≦Ｌ２≦バッファ長）を設け、列の長さＬによって流入パケット格納・格納済みパケット廃棄を行う方式であって、列の長さがＬ１以下の場合には、流入パケット・格納済みパケットのいずれからも廃棄は行わず、列の長さがＬ２以上の場合には、流入パケットと同じ長さだけ格納済みパケットを廃棄（但し再優先度のパケットは廃棄対象外）し、列長がＬ１以上Ｌ２未満の場合には、列の長さのＬ１超過の程度に比例して、Ｌ１で廃棄率０、Ｌ２で廃棄率γ（０＜γ≦１）となるように線形に廃棄率を決定する。
【００３７】
上記のように構成したことにより、キューに格納済みのパケットも廃棄対象とするため、トラヒック増大時の高優先度パケットのスループットの改善が可能となる。特に、高優先度パケット流入時の低優先度パケット廃棄メカニズムとして、格納済みパケットも廃棄対象としているので、列長の伸長時に流入した高優先度のパケットに対し、前方の低優先度パケットを廃棄して当該高優先度パケットをキュー出側に詰めることが可能となり、これによって、高優先度パケットの遅延を抑制できる。また同時に、混雑時に列長を短縮させることができるので、高優先度パケットのトラヒックのスループットを向上させることができる。
【００３８】
また、廃棄パケットの選択においては、異なる優先度の待ちパケット数を一体で管理し、低優先側のパケットがすべて廃棄されるまでは高優先側のパケットが廃棄されないようにしているので、低優先度側のパケットにおいても異なる優先度間での完全優先を実現することが可能となる。
【００３９】
なお、本発明は、上記実施形態例そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。
また、上記実施形態例に開示されている複数の構成要素の適宜な組合せにより種種の発明を形成できる。例えば、実施形態例に示される全構成要素からいくつかの構成要素を削除しても良い。更に、異なる実施形態例に亘る構成要素を適宜組み合わせてもよい。
【符号の説明】
【００４０】
１１…論理キュー格納部、２１…優先度別管理用キュー格納部、２２…優先度毎パケット管理用キュー格納領域、３１…優先制御機能部。
【図１】
2011147033.tif 000003
【図２】
2011147033.tif 000004
【図３】
2011147033.tif 000005
【図４】
2011147033.tif 000006
【図５】
2011147033.tif 000007
【図６】
2011147033.tif 000008
【図７】
2011147033.tif 000009