JP3649661B2 - パケットスケジューリング方法及びパケットスケジューリング装置 - Google Patents
パケットスケジューリング方法及びパケットスケジューリング装置 Download PDFInfo
- Publication number
- JP3649661B2 JP3649661B2 JP2000305247A JP2000305247A JP3649661B2 JP 3649661 B2 JP3649661 B2 JP 3649661B2 JP 2000305247 A JP2000305247 A JP 2000305247A JP 2000305247 A JP2000305247 A JP 2000305247A JP 3649661 B2 JP3649661 B2 JP 3649661B2
- Authority
- JP
- Japan
- Prior art keywords
- class
- priority
- bandwidth
- packet
- packets
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Landscapes
- Data Exchanges In Wide-Area Networks (AREA)
Description
【０００１】
【発明の属する技術分野】
本発明は、パケットスケジューリング方法及びパケットスケジューリング装置に関し、例えばＩＰ（Internet Protocol）網に設けられる自律システム（ＡＳ）内の各種ルータにおいて、入力されるパケットの処理順序を決定するために用いられる。
【０００２】
【従来の技術】
例えば、ＩＰ網などに設けられるルータの入力には、様々な種類のパケットが順次に入力される。様々な種類のパケットを処理するルータの内部には複数のキュー（待ち行列：ｑｕｅｕｅ）が設けられ、入力されたパケットはその種類に応じたキューに蓄積されてから処理される。
【０００３】
このような複数のキューに蓄積されたパケットを処理する順番を決定する処理はパケットスケジューリングと呼ばれている。パケットスケジューリングの方式としては、従来より次のような技術が知られている。
（１）ラウンドロビン（Round Robin）：１番目のキューのパケット，２番目のキューのパケット，３番目のキューのパケット，・・・を順番に処理する。１回に処理するパケットの数は予め決めておく（一般的には１つ）。処理すべきパケットが存在しないキューについては処理がスキップされる。
【０００４】
（２）ＷＲＲ（Weighted Round Robin）：パケットのクラス（キュー）毎に「重み」とパケット長が異なる場合に、重みを平均パケット長で割った「正規化された重み」を用いて、その重みに応じたパケット数を前記ラウンドロビンで処理する。
（３）ＤＲＲ（Deficit Round Robin）：前記ＷＲＲ方式において、事前に平均パケット長の情報を必要としないように工夫されたのもである。詳細には次のような手順で処理される。ある「基準量」が各クラス（キュー）毎に与えられており、あるキューの先頭のパケット長がその基準量より等しいか小さければそのパケットは処理される。そして基準量はそのパケット長分だけ減らされる。このようにして、基準量が次に処理されるパケット長より小さくなるまでそのキューは連続して処理される。それが満たされなくなったとき、ラウンドロビン方式で処理対象は次のキューに移る。全てのキューの先頭パケット長が各キューの基準量より大きくなったら全キューに新たに基準量を加える。
【０００５】
（４）ＧＰＳ（Generalized Processor Sharing）：これは、パケットの存在するＮ個のキューに対して無限の処理容量をもつサーバーが同時に１／Ｎずつのサービス率で処理を行うスケジューリング方式である。あるキューに処理されるべきパケットが存在しない場合には、その分の処理能力は他のキューに等しく割り当てられる。実際には実現不可能な理想的な方式である。
【０００６】
（５）ＷＦＱ（Weighted Fair Queueing）：これは、前記ＧＰＳ方式を近似的に実現させるための方式であり、ＧＰＳでは同時に並列に無限小単位の処理を施しているのに対して、このＷＦＱではビット単位でパケットの処理終了予定時刻の計算を行い、その時刻の早いパケットから順番に処理を行う。
（６）ＣＢ−ＷＦＱ（Class-based Weighted Fair Queueing）：キュー毎に重み値を固定的に割り付ける。
【０００７】
また、例えば特開平９−８３５４７号公報においては、各パケットキューに設定された重みとパケットキューのパケット蓄積量とに基づいてスケジューリングを行うことを開示している。
また、パケットスケジューリングの方式を選択する際には、以下の事項を考慮して選択するのが一般的である。
【０００８】
（ａ）スケジューリングによって何をどのように実現するのか（例えば、優先度の違い、公平性、遅延時間の上限値以内に処理を終了させたい等）。
（ｂ）優先度をどのように定義し、それが実際に実現されるか否か。
（ｃ）クラス間の公平性を考える必要があるか、必要があればそれをどのように考えるか。
【０００９】
（ｄ）実際に装置内で実現する際の容易性はどの程度であるか。
上記の事項の組み合わせを考慮して、最も都合の良い方式が選ばれる。
【００１０】
【発明が解決しようとする課題】
例えばＩＰ網においては、様々な種類のアプリケーションの情報を運ぶために様々な種類のパケットが混在して伝送される。アプリケーションの種類としては、音声（ＶｏＩＰ），画像（Video on Demandやテレビ会議），Ｔｅｌｎｅｔ，Ｘ−Ｗｉｎｄｏｗ，ＷＷＷ，電子メール，ＦＴＰなどがある。
【００１１】
音声や画像のアプリケーションの情報を運ぶパケットは「ストリーム型トラヒック」と呼ばれる。また、ＴｅｌｎｅｔやＸ−Ｗｉｎｄｏｗ等のアプリケーションの情報を運ぶパケットは「インタラクティブ型トラヒック」と呼ばれる。更に、ＷＷＷ，電子メール，ＦＴＰなどのアプリケーションの情報を運ぶパケットは「バルク転送型トラヒック」と呼ばれる。
【００１２】
「ストリーム型トラヒック」や「インタラクティブ型トラヒック」については、実時間性が重要であり、伝送途中の遅延時間が増大すると伝送品質が著しく低下する。また、「バルク転送型トラヒック」については実時間性はあまり重要ではない。
前記ＣＢ−ＷＦＱ方式を採用する場合には、「ストリーム型トラヒック」や「インタラクティブ型トラヒック」を処理するキューに予め大きな重みを割り当て、「バルク転送型トラヒック」を処理するキューに予め小さな重みを割り当てておくことにより、実時間性の要求の厳しいアプリケーションに対する品質を確保することができる。
【００１３】
しかしながら、ＣＢ−ＷＦＱ方式のように各キューの重みを固定的に定める場合には、小さい重みが割り当てられたキューを使用する特定のアプリケーションについては品質が大幅に低下する場合がある。すなわち、特定のキューの使用頻度が高くなり、そのキューに割り当てられた帯域に比べて多くのパケットが短い時間内に到着した場合には当該キューにおける遅延時間が著しく増大する。
【００１４】
また、特開平９−８３５４７号公報の技術を利用する場合には、パケットキューのパケット蓄積量に応じて動的にスケジューリングを行うので、各々のクラスのパケットの優先度が逐次変化することになる。従って、実時間性の高い特定のクラスのパケットに対して帯域を保証できない。また、特定のクラスに割り当てられる帯域の大きさが小さくなりすぎる可能性もある。
【００１５】
本発明は、パケットスケジューリング方法及びパケットスケジューリング装置において、利用可能な全ての帯域を有効に利用し、実時間性に厳しいアプリケーションの品質低下を防止するとともに、実時間性の要求が小さいアプリケーションについても伝送遅延時間が増大するのを防止することを目的とする。
【００１６】
【課題を解決するための手段】
請求項１は、入力されるパケットを複数のクラスに区分するとともに、前記複数のクラスを、処理に要する実時間が重要な優先グループと、前記優先グループ以外の非優先グループとに分類し、順次入力されるパケットを前記複数のクラス毎に設けられた待ち行列として保持し、処理のために前記待ち行列から取り出されるパケットの順序を決定するためのパケットスケジューリング方法であって、前記非優先グループに割り当てられた帯域の大きさが過小であり、未処理の非優先クラス（以下、第１非優先クラスと称する）が存在する場合、前記未処理の非優先クラスのパケットを蓄積する待ち行列に対して、最初に全帯域ＢＷｔにＸ（Ｘは係数）を掛けて得られる帯域ＢＷαを割り当てる第１のステップと、
全帯域ＢＷｔから前記第１非優先クラスに割り当てた帯域ＢＷαを差し引いて得られた帯域ＢＷβに、前記優先グループ内の各優先クラスの要求遅延時間を満足するのに十分な帯域ＢＷｒを割り当てる第２のステップと、前記非優先グループに属する非優先クラスから前記第１非優先クラスを除いて得られる第２非優先クラスに対して、帯域ＢＷβから帯域ＢＷｒを差し引いて得られた帯域ＢＷｚを割り当てる第３のステップとから構成されることを特徴とする。
【００１７】
請求項１においては、第１非優先クラスに対して、帯域ＢＷαが割り当てられる。これによって、割り当てられた帯域の大きさが過小であって、処理が滞っていた待ち行列の処理が促進される。
また、優先グループに属する各優先クラスのパケットを保持する待ち行列には、各優先クラスの要求遅延時間を満足するのに十分な帯域ＢＷｒが割り当てられる。
また、第２非優先クラスに対して、帯域ＢＷｚが割り当てられる。
したがって、処理に要する実時間が重要な優先グループと、前記優先グループ以外の非優先グループとが、効率的に処理される。
【００１８】
請求項２は、請求項１に記載のパケットスケジューリング方法において、前記第１非優先クラスが存在するか否かの判断は、特定期間の間に割り当てられた帯域が小さすぎて、パケットを全く処理できなかったクラスが存在するか否かを前記非優先グループに属するクラス毎に識別することにより行い、前記非優先グループに属する各クラスのパケットを保持する各待ち行列から、前記パケットを取り出す優先度の決定は、直近の特定期間で検出された使用頻度の違いに応じた重みに基づいて行うことを特徴とする。
【００２０】
請求項３は、請求項１記載のパケットスケジューリング方法において、前記第１のステップにおいて、前記非優先グループの各クラスの使用頻度を、前記特定期間に到着したパケットの数及び到着したパケットの平均パケット長に基づいてダイナミックに検出することを特徴とする。
【００２１】
請求項３においては、前記特定期間に到着したパケットの数及び到着したパケットの平均パケット長に基づいて各クラスの使用頻度を検出するので、到着するパケットの各パケット長が変動する場合であっても各クラスの使用頻度を検出することができる。
【００２２】
請求項４は、入力されるパケットを複数のクラスに区分するとともに、前記複数のクラスを、処理に要する実時間が重要な優先グループと、前記優先グループ以外の非優先グループとに分類し、順次に入力されるパケットを前記複数のクラス毎に設けられた待ち行列として蓄積し、処理のために前記待ち行列から取り出されるパケットの順序を決定するためのパケットスケジューリング装置であって、前記非優先グループに割り当てられた帯域の大きさが過小であり、未処理の非優先クラス（以下、第１非優先クラスと称する）が存在する場合、前記未処理の非優先クラスのパケットを蓄積する待ち行列に対して、最初に全帯域ＢＷｔにＸ（Ｘは係数）を掛けて得られる帯域ＢＷαを割り当てる第１の帯域割り当て手段と、全帯域ＢＷｔから前記第１非優先クラスに割り当てた帯域ＢＷαを差し引いて得られた帯域ＢＷβに、前記優先グループ内の各優先クラスの要求遅延時間を満足するのに十分な帯域ＢＷｒを割り当てる第２の帯域割り当て手段と、前記非優先グループに属する非優先クラスから前記第１非優先クラスを除いて得られる第２非優先クラスに対して、帯域ＢＷβから帯域ＢＷｒを差し引いて得られた帯域ＢＷｚを割り当てる第３の帯域割り当て手段とから構成されることを特徴とする。
【００２３】
請求項４のパケットスケジューリング装置においては、請求項１と同様にパケットスケジューリングを行うことができる。
【００２４】
【発明の実施の形態】
本発明のパケットスケジューリング方法及びパケットスケジューリング装置の１つの実施の形態について、図１〜図３を参照して説明する。この形態は全ての請求項に対応する。
【００２５】
図１は、この形態のパケットスケジューリング処理を示すフローチャートである。図２は本発明を実施するルータの構成を示すブロック図である。図３はこの形態の処理のタイミングを示すタイムチャートである。
この形態では、請求項４の第１の帯域割り当て手段，第２の帯域割り当て手段、第３の帯域割り当て手段は、トラヒック特性量計算部１６（Ｓ１５、Ｓ１９、Ｓ２２、Ｓ２５）及び処理クラス指示部１８に対応する。
【００２６】
この形態では、ＩＰ網に接続された図２のルータに、本発明のパケットスケジューリング方法及びパケットスケジューリング装置を適用する場合を想定している。
図２を参照すると、このルータにはパケット情報収集部１０，クラス決定部１１，ヘッダ読み取り測定部１２，パケットヘッダ解析／計算部１３，ルーチングテーブル１４，ヘッダ書き込み制御部１５，トラヒック特性量計算部１６，割り当て帯域計算部１７，処理クラス指示部１８，データベース（ＤＢ）１９，スケジューリング部２０，時計３１及びタイマ３２が備わっている。
【００２７】
また、スケジューリング部２０には、Ｎ個のキューバッファ２１(1)〜２１(N)及びパケット処理部２２が備わっている。キューバッファ２１は、例えばＦＩＦＯ（ファーストインファーストアウト）メモリで構成することができる。
外部からこのルータに到来するパケットは、パケット情報収集部１０に入力され、スケジューリング部２０でいずれか１つのキューバッファ２１に蓄積された後、パケット処理部２２で処理されて外部に出力される。
【００２８】
パケット情報収集部１０は、各パケットからその行き先，クラス及びパケット長を含むヘッダ情報を抽出してクラス決定部１１に通知する。クラス決定部１１は、ヘッダ情報のクラスに基づいて、パケットの種類をＮ以下のクラスに分類する。また、優先グループのクラスと非優先グループのクラスとを区別する。
パケット情報収集部１０は、入力されたパケットをクラス決定部１１の分類したクラスに対応する１つのキューバッファ２１に書き込む。
【００２９】
また、各パケットの行き先及びクラスを含むヘッダ情報は、クラス決定部１１からヘッダ読み取り測定部１２を通ってパケットヘッダ解析／計算部１３に入力される。
パケットヘッダ解析／計算部１３は、ヘッダ情報に基づき、ルーチングテーブル１４を参照して行き先情報を取得する。この行き先情報は、ヘッダ書き込み制御部１５を通り、次ルータ情報としてキューバッファ２１上のパケットに書き込まれる。
【００３０】
トラヒック特性量計算部１６は、パケットのクラス毎に特定区間毎のトラヒック特性量を計算する。割り当て帯域計算部１７は、トラヒック特性量計算部１６の求めた特性量に従って、各クラスの帯域を割り当てる。
割り当て帯域計算部１７が割り当てた帯域の値は、各クラスの重みとして処理クラス指示部１８に入力される。また、処理クラス指示部１８には特定区間毎の処理パケット数がトラヒック特性量計算部１６から入力される。
【００３１】
処理クラス指示部１８は、パケット処理部２２が処理すべきパケットのクラスをパケット処理部２２に指示する。パケット処理部２２は、処理クラス指示部１８から指示されたクラスのパケットを対応するキューバッファ２１の先頭から取り出して処理する。
図２のパケット処理部２２がキューバッファ２１(1)〜２１(N)から取り出すパケットの順番を決定するためのパケットスケジューリング処理の詳細について、以下に説明する。
【００３２】
なお、パケットのクラスについては、アプリケーションの種類によって定められる場合もあるし、ユーザの契約時に定められる場合もあるし、通信の開始時に定められる場合もある。
アプリケーションの種類としては、音声（ＶｏＩＰ），画像（Video on Demandやテレビ会議），Ｔｅｌｎｅｔ，Ｘ−Ｗｉｎｄｏｗ，ＷＷＷ，電子メール，ＦＴＰなどがある。
【００３３】
音声や画像のアプリケーションの情報を運ぶパケットは「ストリーム型トラヒック」と呼ばれる。また、ＴｅｌｎｅｔやＸ−Ｗｉｎｄｏｗ等のアプリケーションの情報を運ぶパケットは「インタラクティブ型トラヒック」と呼ばれる。更に、ＷＷＷ，電子メール，ＦＴＰなどのアプリケーションの情報を運ぶパケットは「バルク転送型トラヒック」と呼ばれる。
【００３４】
「ストリーム型トラヒック」や「インタラクティブ型トラヒック」については、実時間性が重要であり、伝送途中の遅延時間が増大すると伝送品質が著しく低下する。また、「バルク転送型トラヒック」については実時間性はあまり重要ではない。
そこで、このパケットスケジューリング処理においては、パケットのクラスを優先グループと非優先グループとに分類する。「ストリーム型トラヒック」及び「インタラクティブ型トラヒック」に相当するパケットのクラスについては、実時間性が重要なので優先グループに分類する。また、「バルク転送型トラヒック」に相当するパケットのクラスについては実時間性が重要でないので非優先グループに分類する。なお、優先グループに属する各クラスを優先クラスと呼び、非優先グループに属する各クラスを非優先クラスと呼ぶ。
【００３５】
図１に示すパケットスケジューリング処理は、各クラスのパケットを処理する待ち行列（各キューバッファ２１の内容）に対する帯域の割り当て手順を表している。各待ち行列に割り当てられた帯域の大きさに従って、各待ち行列に蓄積されたパケットの処理の優先度が決定される。
また、図１に示すパケットスケジューリング処理は、図３に示すようなタイミングで実行される。すなわち、現時点がｔである場合に、それ以前の情報収集区間Ａ１について情報の収集を行い、計算区間Ａ２で計算を行い、制御対象区間Ａ３に対する帯域の割り当てを行う。
【００３６】
さて、図２のルータの入力にパケットが到着した場合には、パケットスケジューリング処理は図１のステップＳ１２からＳ１３に進む。ステップＳ１３では、到着したパケットのクラスを識別する。また、次のステップＳ１４では到着したパケットをそのクラスに対応付けられた１つのキューバッファ２１に転送する。更に、ステップＳ１５ではクラス毎に到着したパケットのパケット数及び平均パケット長の計算を行う。
【００３７】
各クラスに帯域を割り当てるための所定のタイミングになると、ステップＳ１１からＳ１６に進む。ステップＳ１６〜Ｓ１９は、非優先クラスのパケットに対して最小限の帯域を保証するための処理である。
ステップＳ１６では、ある監視区間（ｔ−ＫＴ，ｔの間）に、割り当てられた帯域が小さすぎて全くパケットを処理できなかった非優先クラスが存在するか否かを識別する。存在する場合にはステップＳ１８に進み、存在しない場合にはステップＳ１７に進む。
【００３８】
ステップＳ１７では、帯域ＢＷα（ｂｐｓ）の値を０にする。
ステップＳ１８では、ルータの全帯域ＢＷｔ（ｂｐｓ）に係数Ｘ（例えば０．１）を掛けた結果を帯域ＢＷαの値にする。なお、係数Ｘ及びＫは各クラスの遅延時間がある値以上にならないように計算により求められる。
ステップＳ１９では、パケットを処理できなかった非優先クラスに対して、帯域ＢＷαを割り当てる。
【００３９】
なお、パケットを処理できなかった非優先クラスが複数存在する場合には、各クラスの遅延時間がある値以上にならないように、帯域ＢＷαの一部分をそれぞれの非優先クラスに割り当てる。
ステップＳ２０では、全帯域ＢＷｔから帯域ＢＷαを差し引いた結果を帯域ＢＷβの値に定める。
【００４０】
ステップＳ２１では、優先クラスのパケットについて、情報収集区間Ａ１で観測されたパケットのノード（ルータ）内滞在時間Ｔｉsys(A1)を次式によりクラス毎に（優先クラスのみ）計算する。
Ｔｉsys(A1)＝ｘｉ(A1)＋ρｉ(A1)ｘｉ(A1)／（２（１−ρｉ(A1)）)・・・(1)
但し、
ｘｉ(A1)＝８ｐｉ(A1)／ＢＷ(Ci，A1)：平均処理時間（ｓｅｃ）
ｐｉ(A1)：平均パケット長（ｂｙｔｅ）
ＢＷ(Ci，A1)：ｉ番目のクラスに割り当てた帯域の大きさ
ρｉ(A1)＝λｉ(A1)ｘｉ(A1)：使用率
λｉ(A1)＝ｑｉ(A1)／ｎＴ：到着率
ｑｉ(A1)：情報収集区間Ａ１に到着したｉ番目のクラスのパケット数
ステップＳ２２では、優先クラスについてクラス毎に帯域の割り当てを更新する。具体的には、ステップＳ２１で求めたパケットの滞在時間Ｔｉsys(A1)が各クラスの要求する遅延時間ｄｉよりも小さくなるように、帯域ＢＷ(Ci，A3)の大きさを割り当てる。すなわち、優先クラスについては直近のｎ周期の区間（Ａ１）で収集して得られた情報に基づいて、遅延時間ｄｉの条件を満足するような帯域を制御対象区間Ａ３に与える。
【００４１】
従って、全ての優先クラスについては、それが要求する遅延時間ｄｉをほぼ満足するように帯域が割り当てられる。また、遅延時間ｄｉを満足できないような優先クラスのパケットについては、予めそのような呼の受付を拒否するように呼受付で制御している。
ステップＳ２３では、まずステップＳ２２で優先グループに属する全てのクラスに割り当てた帯域ＢＷ(Ci，A3)の総和ＢＷｒを求める。
ステップＳ２４では、帯域ＢＷβから帯域ＢＷｒを差し引いた結果を残余の帯域ＢＷｚとして求める。
【００４２】
ステップＳ２５では、非優先クラスについて、残余の帯域ＢＷｚをクラス毎に割り当てる。具体的には、情報収集区間Ａ１で収集して得られた到着パケット数Ｎ(Ck,A1)及び平均パケット長ＰＬ(Ck,A1)（非優先クラスのみ）に基づいて、ｋ番目の各クラスＣｋの帯域ＢＷ(Ck,A3)を次式を用いて求める。
ＢＷ(Ck,A3)＝ＢＷｚ・ｕｋ・ｖｋ／(非優先クラスのｕｋ・ｖｋの総和)・・・(2)
但し
ｕｋ＝Ｎ(Ck,A1)（非優先クラスのみ）
ｖｋ＝ＰＬ(Ck,A1)（非優先クラスのみ）
すなわち、非優先クラスのパケットについては、情報収集区間Ａ１で到着したパケット情報量（パケット数×平均パケット長）に比例した割合で、帯域ＢＷｚを各クラスに配分する。このため、非優先クラスについては使用頻度が高くなるとますます多くの帯域が割り当てられる。また、使用頻度が低くなると割り当てられる帯域は小さくなる。
【００４３】
図１の処理によって各クラスに割り当てられる帯域ＢＷ（Ｃｊ）（ｊ＝１〜Ｎ）の大きさは、ルータのスケジューリングの際の「重み」に相当し、制御対象区間Ａ３における優先度に直結する。
すなわち、制御対象区間Ａ３におけるクラスＣｊの優先度の重みＷ(Cj,A3)は次式で与えられる。
【００４４】
Ｗ(Cj,A3)＝ＢＷ（Cj,A3)／ＢＷｔ ・・・（３）
但し、非優先グループの各クラスについては、優先グループの各クラスの待ち行列にパケットが存在しない場合のみ、上記の重みに従って待ち行列が選択されパケットが処理される。
次に、帯域割り当ての具体例について説明する。
【００４５】
（具体例１）
この例では、次のような状態を想定する。
ＢＷｔ：１２Ｍｂｐｓ
ＢＷα：０
Ｔ：５秒
ｎ：１
ｍ：１
クラス数Ｎ：３
クラス１：優先クラス
クラス２，クラス３：非優先クラス
現時点ｔ：０
また、情報収集区間Ａ１（−５，０）における各クラスの使用状態として次の状態を想定する。
【００４６】
クラス１の到着パケット数：２
クラス２の到着パケット数：２
クラス３の到着パケット数：６
クラス１の平均パケット長：１００
クラス２の平均パケット長：２００
クラス３の平均パケット長：３００
ここで、帯域ＢＷｒが８Ｍｂｐｓである場合を想定すると、制御対象区間Ａ３（５，１０）に対する各クラスへの割り当て帯域は次のようになる。
【００４７】
クラス１：８Ｍｂｐｓ
クラス２：(12-8)×2×200／(2×200＋6×300)＝0.727Ｍｂｐｓ
クラス３：(12-8)×6×300／(2×200＋6×300)＝3.273Ｍｂｐｓ
（具体例２）
この例では、観測周期Ｔの整数倍（ＫＴ）のある区間で、優先クラスのパケットの到着数が多すぎて、非優先グループに対する帯域の割り当てが少なくなり、非優先グループに属するあるクラス（未処理クラス）のパケットが全く処理されなかった場合を想定する。
【００４８】
この場合には、（ＫＴ）の区間毎に、次の制御対象区間Ａ３における全帯域のＸ（％）の帯域を前記未処理クラスに割り当てて処理する。係数Ｋ，Ｘは、各クラスの遅延時間がある値以上にならないように計算により求められる。
すなわち、未処理の非優先クラスを検出した場合には、図１のステップＳ１９で帯域ＢＷαを未処理の非優先クラスに割り当てる。
【００４９】
また、ここでは次の状態を想定する。
ＢＷｔ：１２Ｍｂｐｓ
Ｔ：５秒
ｎ：１
ｍ：１
クラス数Ｎ：３
クラス１：優先クラス
クラス２：非優先クラス
クラス３：非優先クラス（未処理クラス）
Ｋ：２
Ｘ：１０（％）
現時点ｔ：０
また、情報収集区間Ａ１（−５，０）における各クラスの使用状態として次の状態を想定する。
【００５０】
クラス１の到着パケット数：９
クラス２の到着パケット数：１
クラス３の到着パケット数：０
クラス１の平均パケット長：１００
クラス２の平均パケット長：２００
クラス３の平均パケット長：３００
ここで、帯域ＢＷｒが１１Ｍｂｐｓであり、区間（−１０，０）でクラス３のパケットが１個も処理されなかった場合を想定する。この場合、制御対象区間Ａ３（５，１０）に対する各クラスへの割り当て帯域は次のようになる。
【００５１】
クラス１：１２−１．２＝１０．８Ｍｂｐｓ
クラス２：０Ｍｂｐｓ
クラス３：１２×１０／１００＝１．２Ｍｂｐｓ
すなわち、未処理クラスであるクラス３に対しては、次の制御区間でそのパケットを処理できるように（１．２Ｍｂｐｓ）の帯域が優先的に割り当てられる。
【００５２】
従って、この形態では実時間性の高いクラスに対しては、前もって要求遅延時間を満たすのに十分な帯域を確保しておくことができる。また、直近のある時間区間において使用量（パケット数で判断）の多いクラスについては、さらに優先させてスループットを上げ、遅延時間を短くするための優先制御をダイナミックに実時間に近い微小時間内で実現することができる。
【００５３】
また、使用頻度の少ない通過パケット数の少ないクラスに対しても、各ノード（ルータ）内の遅延時間がある限度値以上にならないように最低限の帯域を割り当てることができる。
【００５４】
【発明の効果】
本発明によれば、使用頻度の高いクラスのパケットを優先させるように帯域を割り当てることができる。しかも、実時間性の高いアプリケーションの要求品質を満足するようにそのクラスのパケットの帯域を割り当てることができる。また、実時間性の低いクラスについても、比較的長い時間の平均的なスループットをある値以上にすることが可能である。
【００５５】
本発明の装置を採用することにより、ＩＰ網などを利用するユーザあるいは使用アプリケーションに対して利用頻度に応じた帯域の割り当てが可能になるため、網内の通信量を益々増加させ、網の利用を活発化させることが可能になる。
【図面の簡単な説明】
【図１】実施の形態のパケットスケジューリング処理を示すフローチャートである。
【図２】本発明を実施するルータの構成を示すブロック図である。
【図３】実施の形態の処理のタイミングを示すタイムチャートである。
【符号の説明】
１０ パケット情報収集部
１１ クラス決定部
１２ ヘッダ読み取り測定部
１３ パケットヘッダ解析／計算部
１４ ルーチングテーブル
１５ ヘッダ書き込み制御部
１６ トラヒック特性量計算部
１７ 割り当て帯域計算部
１８ 処理クラス指示部
１９ データベース
２０ スケジューリング部
２１ キューバッファ
２２ パケット処理部
３１ 時計
３２ タイマ
【発明の属する技術分野】
本発明は、パケットスケジューリング方法及びパケットスケジューリング装置に関し、例えばＩＰ（Internet Protocol）網に設けられる自律システム（ＡＳ）内の各種ルータにおいて、入力されるパケットの処理順序を決定するために用いられる。
【０００２】
【従来の技術】
例えば、ＩＰ網などに設けられるルータの入力には、様々な種類のパケットが順次に入力される。様々な種類のパケットを処理するルータの内部には複数のキュー（待ち行列：ｑｕｅｕｅ）が設けられ、入力されたパケットはその種類に応じたキューに蓄積されてから処理される。
【０００３】
このような複数のキューに蓄積されたパケットを処理する順番を決定する処理はパケットスケジューリングと呼ばれている。パケットスケジューリングの方式としては、従来より次のような技術が知られている。
（１）ラウンドロビン（Round Robin）：１番目のキューのパケット，２番目のキューのパケット，３番目のキューのパケット，・・・を順番に処理する。１回に処理するパケットの数は予め決めておく（一般的には１つ）。処理すべきパケットが存在しないキューについては処理がスキップされる。
【０００４】
（２）ＷＲＲ（Weighted Round Robin）：パケットのクラス（キュー）毎に「重み」とパケット長が異なる場合に、重みを平均パケット長で割った「正規化された重み」を用いて、その重みに応じたパケット数を前記ラウンドロビンで処理する。
（３）ＤＲＲ（Deficit Round Robin）：前記ＷＲＲ方式において、事前に平均パケット長の情報を必要としないように工夫されたのもである。詳細には次のような手順で処理される。ある「基準量」が各クラス（キュー）毎に与えられており、あるキューの先頭のパケット長がその基準量より等しいか小さければそのパケットは処理される。そして基準量はそのパケット長分だけ減らされる。このようにして、基準量が次に処理されるパケット長より小さくなるまでそのキューは連続して処理される。それが満たされなくなったとき、ラウンドロビン方式で処理対象は次のキューに移る。全てのキューの先頭パケット長が各キューの基準量より大きくなったら全キューに新たに基準量を加える。
【０００５】
（４）ＧＰＳ（Generalized Processor Sharing）：これは、パケットの存在するＮ個のキューに対して無限の処理容量をもつサーバーが同時に１／Ｎずつのサービス率で処理を行うスケジューリング方式である。あるキューに処理されるべきパケットが存在しない場合には、その分の処理能力は他のキューに等しく割り当てられる。実際には実現不可能な理想的な方式である。
【０００６】
（５）ＷＦＱ（Weighted Fair Queueing）：これは、前記ＧＰＳ方式を近似的に実現させるための方式であり、ＧＰＳでは同時に並列に無限小単位の処理を施しているのに対して、このＷＦＱではビット単位でパケットの処理終了予定時刻の計算を行い、その時刻の早いパケットから順番に処理を行う。
（６）ＣＢ−ＷＦＱ（Class-based Weighted Fair Queueing）：キュー毎に重み値を固定的に割り付ける。
【０００７】
また、例えば特開平９−８３５４７号公報においては、各パケットキューに設定された重みとパケットキューのパケット蓄積量とに基づいてスケジューリングを行うことを開示している。
また、パケットスケジューリングの方式を選択する際には、以下の事項を考慮して選択するのが一般的である。
【０００８】
（ａ）スケジューリングによって何をどのように実現するのか（例えば、優先度の違い、公平性、遅延時間の上限値以内に処理を終了させたい等）。
（ｂ）優先度をどのように定義し、それが実際に実現されるか否か。
（ｃ）クラス間の公平性を考える必要があるか、必要があればそれをどのように考えるか。
【０００９】
（ｄ）実際に装置内で実現する際の容易性はどの程度であるか。
上記の事項の組み合わせを考慮して、最も都合の良い方式が選ばれる。
【００１０】
【発明が解決しようとする課題】
例えばＩＰ網においては、様々な種類のアプリケーションの情報を運ぶために様々な種類のパケットが混在して伝送される。アプリケーションの種類としては、音声（ＶｏＩＰ），画像（Video on Demandやテレビ会議），Ｔｅｌｎｅｔ，Ｘ−Ｗｉｎｄｏｗ，ＷＷＷ，電子メール，ＦＴＰなどがある。
【００１１】
音声や画像のアプリケーションの情報を運ぶパケットは「ストリーム型トラヒック」と呼ばれる。また、ＴｅｌｎｅｔやＸ−Ｗｉｎｄｏｗ等のアプリケーションの情報を運ぶパケットは「インタラクティブ型トラヒック」と呼ばれる。更に、ＷＷＷ，電子メール，ＦＴＰなどのアプリケーションの情報を運ぶパケットは「バルク転送型トラヒック」と呼ばれる。
【００１２】
「ストリーム型トラヒック」や「インタラクティブ型トラヒック」については、実時間性が重要であり、伝送途中の遅延時間が増大すると伝送品質が著しく低下する。また、「バルク転送型トラヒック」については実時間性はあまり重要ではない。
前記ＣＢ−ＷＦＱ方式を採用する場合には、「ストリーム型トラヒック」や「インタラクティブ型トラヒック」を処理するキューに予め大きな重みを割り当て、「バルク転送型トラヒック」を処理するキューに予め小さな重みを割り当てておくことにより、実時間性の要求の厳しいアプリケーションに対する品質を確保することができる。
【００１３】
しかしながら、ＣＢ−ＷＦＱ方式のように各キューの重みを固定的に定める場合には、小さい重みが割り当てられたキューを使用する特定のアプリケーションについては品質が大幅に低下する場合がある。すなわち、特定のキューの使用頻度が高くなり、そのキューに割り当てられた帯域に比べて多くのパケットが短い時間内に到着した場合には当該キューにおける遅延時間が著しく増大する。
【００１４】
また、特開平９−８３５４７号公報の技術を利用する場合には、パケットキューのパケット蓄積量に応じて動的にスケジューリングを行うので、各々のクラスのパケットの優先度が逐次変化することになる。従って、実時間性の高い特定のクラスのパケットに対して帯域を保証できない。また、特定のクラスに割り当てられる帯域の大きさが小さくなりすぎる可能性もある。
【００１５】
本発明は、パケットスケジューリング方法及びパケットスケジューリング装置において、利用可能な全ての帯域を有効に利用し、実時間性に厳しいアプリケーションの品質低下を防止するとともに、実時間性の要求が小さいアプリケーションについても伝送遅延時間が増大するのを防止することを目的とする。
【００１６】
【課題を解決するための手段】
請求項１は、入力されるパケットを複数のクラスに区分するとともに、前記複数のクラスを、処理に要する実時間が重要な優先グループと、前記優先グループ以外の非優先グループとに分類し、順次入力されるパケットを前記複数のクラス毎に設けられた待ち行列として保持し、処理のために前記待ち行列から取り出されるパケットの順序を決定するためのパケットスケジューリング方法であって、前記非優先グループに割り当てられた帯域の大きさが過小であり、未処理の非優先クラス（以下、第１非優先クラスと称する）が存在する場合、前記未処理の非優先クラスのパケットを蓄積する待ち行列に対して、最初に全帯域ＢＷｔにＸ（Ｘは係数）を掛けて得られる帯域ＢＷαを割り当てる第１のステップと、
全帯域ＢＷｔから前記第１非優先クラスに割り当てた帯域ＢＷαを差し引いて得られた帯域ＢＷβに、前記優先グループ内の各優先クラスの要求遅延時間を満足するのに十分な帯域ＢＷｒを割り当てる第２のステップと、前記非優先グループに属する非優先クラスから前記第１非優先クラスを除いて得られる第２非優先クラスに対して、帯域ＢＷβから帯域ＢＷｒを差し引いて得られた帯域ＢＷｚを割り当てる第３のステップとから構成されることを特徴とする。
【００１７】
請求項１においては、第１非優先クラスに対して、帯域ＢＷαが割り当てられる。これによって、割り当てられた帯域の大きさが過小であって、処理が滞っていた待ち行列の処理が促進される。
また、優先グループに属する各優先クラスのパケットを保持する待ち行列には、各優先クラスの要求遅延時間を満足するのに十分な帯域ＢＷｒが割り当てられる。
また、第２非優先クラスに対して、帯域ＢＷｚが割り当てられる。
したがって、処理に要する実時間が重要な優先グループと、前記優先グループ以外の非優先グループとが、効率的に処理される。
【００１８】
請求項２は、請求項１に記載のパケットスケジューリング方法において、前記第１非優先クラスが存在するか否かの判断は、特定期間の間に割り当てられた帯域が小さすぎて、パケットを全く処理できなかったクラスが存在するか否かを前記非優先グループに属するクラス毎に識別することにより行い、前記非優先グループに属する各クラスのパケットを保持する各待ち行列から、前記パケットを取り出す優先度の決定は、直近の特定期間で検出された使用頻度の違いに応じた重みに基づいて行うことを特徴とする。
【００２０】
請求項３は、請求項１記載のパケットスケジューリング方法において、前記第１のステップにおいて、前記非優先グループの各クラスの使用頻度を、前記特定期間に到着したパケットの数及び到着したパケットの平均パケット長に基づいてダイナミックに検出することを特徴とする。
【００２１】
請求項３においては、前記特定期間に到着したパケットの数及び到着したパケットの平均パケット長に基づいて各クラスの使用頻度を検出するので、到着するパケットの各パケット長が変動する場合であっても各クラスの使用頻度を検出することができる。
【００２２】
請求項４は、入力されるパケットを複数のクラスに区分するとともに、前記複数のクラスを、処理に要する実時間が重要な優先グループと、前記優先グループ以外の非優先グループとに分類し、順次に入力されるパケットを前記複数のクラス毎に設けられた待ち行列として蓄積し、処理のために前記待ち行列から取り出されるパケットの順序を決定するためのパケットスケジューリング装置であって、前記非優先グループに割り当てられた帯域の大きさが過小であり、未処理の非優先クラス（以下、第１非優先クラスと称する）が存在する場合、前記未処理の非優先クラスのパケットを蓄積する待ち行列に対して、最初に全帯域ＢＷｔにＸ（Ｘは係数）を掛けて得られる帯域ＢＷαを割り当てる第１の帯域割り当て手段と、全帯域ＢＷｔから前記第１非優先クラスに割り当てた帯域ＢＷαを差し引いて得られた帯域ＢＷβに、前記優先グループ内の各優先クラスの要求遅延時間を満足するのに十分な帯域ＢＷｒを割り当てる第２の帯域割り当て手段と、前記非優先グループに属する非優先クラスから前記第１非優先クラスを除いて得られる第２非優先クラスに対して、帯域ＢＷβから帯域ＢＷｒを差し引いて得られた帯域ＢＷｚを割り当てる第３の帯域割り当て手段とから構成されることを特徴とする。
【００２３】
請求項４のパケットスケジューリング装置においては、請求項１と同様にパケットスケジューリングを行うことができる。
【００２４】
【発明の実施の形態】
本発明のパケットスケジューリング方法及びパケットスケジューリング装置の１つの実施の形態について、図１〜図３を参照して説明する。この形態は全ての請求項に対応する。
【００２５】
図１は、この形態のパケットスケジューリング処理を示すフローチャートである。図２は本発明を実施するルータの構成を示すブロック図である。図３はこの形態の処理のタイミングを示すタイムチャートである。
この形態では、請求項４の第１の帯域割り当て手段，第２の帯域割り当て手段、第３の帯域割り当て手段は、トラヒック特性量計算部１６（Ｓ１５、Ｓ１９、Ｓ２２、Ｓ２５）及び処理クラス指示部１８に対応する。
【００２６】
この形態では、ＩＰ網に接続された図２のルータに、本発明のパケットスケジューリング方法及びパケットスケジューリング装置を適用する場合を想定している。
図２を参照すると、このルータにはパケット情報収集部１０，クラス決定部１１，ヘッダ読み取り測定部１２，パケットヘッダ解析／計算部１３，ルーチングテーブル１４，ヘッダ書き込み制御部１５，トラヒック特性量計算部１６，割り当て帯域計算部１７，処理クラス指示部１８，データベース（ＤＢ）１９，スケジューリング部２０，時計３１及びタイマ３２が備わっている。
【００２７】
また、スケジューリング部２０には、Ｎ個のキューバッファ２１(1)〜２１(N)及びパケット処理部２２が備わっている。キューバッファ２１は、例えばＦＩＦＯ（ファーストインファーストアウト）メモリで構成することができる。
外部からこのルータに到来するパケットは、パケット情報収集部１０に入力され、スケジューリング部２０でいずれか１つのキューバッファ２１に蓄積された後、パケット処理部２２で処理されて外部に出力される。
【００２８】
パケット情報収集部１０は、各パケットからその行き先，クラス及びパケット長を含むヘッダ情報を抽出してクラス決定部１１に通知する。クラス決定部１１は、ヘッダ情報のクラスに基づいて、パケットの種類をＮ以下のクラスに分類する。また、優先グループのクラスと非優先グループのクラスとを区別する。
パケット情報収集部１０は、入力されたパケットをクラス決定部１１の分類したクラスに対応する１つのキューバッファ２１に書き込む。
【００２９】
また、各パケットの行き先及びクラスを含むヘッダ情報は、クラス決定部１１からヘッダ読み取り測定部１２を通ってパケットヘッダ解析／計算部１３に入力される。
パケットヘッダ解析／計算部１３は、ヘッダ情報に基づき、ルーチングテーブル１４を参照して行き先情報を取得する。この行き先情報は、ヘッダ書き込み制御部１５を通り、次ルータ情報としてキューバッファ２１上のパケットに書き込まれる。
【００３０】
トラヒック特性量計算部１６は、パケットのクラス毎に特定区間毎のトラヒック特性量を計算する。割り当て帯域計算部１７は、トラヒック特性量計算部１６の求めた特性量に従って、各クラスの帯域を割り当てる。
割り当て帯域計算部１７が割り当てた帯域の値は、各クラスの重みとして処理クラス指示部１８に入力される。また、処理クラス指示部１８には特定区間毎の処理パケット数がトラヒック特性量計算部１６から入力される。
【００３１】
処理クラス指示部１８は、パケット処理部２２が処理すべきパケットのクラスをパケット処理部２２に指示する。パケット処理部２２は、処理クラス指示部１８から指示されたクラスのパケットを対応するキューバッファ２１の先頭から取り出して処理する。
図２のパケット処理部２２がキューバッファ２１(1)〜２１(N)から取り出すパケットの順番を決定するためのパケットスケジューリング処理の詳細について、以下に説明する。
【００３２】
なお、パケットのクラスについては、アプリケーションの種類によって定められる場合もあるし、ユーザの契約時に定められる場合もあるし、通信の開始時に定められる場合もある。
アプリケーションの種類としては、音声（ＶｏＩＰ），画像（Video on Demandやテレビ会議），Ｔｅｌｎｅｔ，Ｘ−Ｗｉｎｄｏｗ，ＷＷＷ，電子メール，ＦＴＰなどがある。
【００３３】
音声や画像のアプリケーションの情報を運ぶパケットは「ストリーム型トラヒック」と呼ばれる。また、ＴｅｌｎｅｔやＸ−Ｗｉｎｄｏｗ等のアプリケーションの情報を運ぶパケットは「インタラクティブ型トラヒック」と呼ばれる。更に、ＷＷＷ，電子メール，ＦＴＰなどのアプリケーションの情報を運ぶパケットは「バルク転送型トラヒック」と呼ばれる。
【００３４】
「ストリーム型トラヒック」や「インタラクティブ型トラヒック」については、実時間性が重要であり、伝送途中の遅延時間が増大すると伝送品質が著しく低下する。また、「バルク転送型トラヒック」については実時間性はあまり重要ではない。
そこで、このパケットスケジューリング処理においては、パケットのクラスを優先グループと非優先グループとに分類する。「ストリーム型トラヒック」及び「インタラクティブ型トラヒック」に相当するパケットのクラスについては、実時間性が重要なので優先グループに分類する。また、「バルク転送型トラヒック」に相当するパケットのクラスについては実時間性が重要でないので非優先グループに分類する。なお、優先グループに属する各クラスを優先クラスと呼び、非優先グループに属する各クラスを非優先クラスと呼ぶ。
【００３５】
図１に示すパケットスケジューリング処理は、各クラスのパケットを処理する待ち行列（各キューバッファ２１の内容）に対する帯域の割り当て手順を表している。各待ち行列に割り当てられた帯域の大きさに従って、各待ち行列に蓄積されたパケットの処理の優先度が決定される。
また、図１に示すパケットスケジューリング処理は、図３に示すようなタイミングで実行される。すなわち、現時点がｔである場合に、それ以前の情報収集区間Ａ１について情報の収集を行い、計算区間Ａ２で計算を行い、制御対象区間Ａ３に対する帯域の割り当てを行う。
【００３６】
さて、図２のルータの入力にパケットが到着した場合には、パケットスケジューリング処理は図１のステップＳ１２からＳ１３に進む。ステップＳ１３では、到着したパケットのクラスを識別する。また、次のステップＳ１４では到着したパケットをそのクラスに対応付けられた１つのキューバッファ２１に転送する。更に、ステップＳ１５ではクラス毎に到着したパケットのパケット数及び平均パケット長の計算を行う。
【００３７】
各クラスに帯域を割り当てるための所定のタイミングになると、ステップＳ１１からＳ１６に進む。ステップＳ１６〜Ｓ１９は、非優先クラスのパケットに対して最小限の帯域を保証するための処理である。
ステップＳ１６では、ある監視区間（ｔ−ＫＴ，ｔの間）に、割り当てられた帯域が小さすぎて全くパケットを処理できなかった非優先クラスが存在するか否かを識別する。存在する場合にはステップＳ１８に進み、存在しない場合にはステップＳ１７に進む。
【００３８】
ステップＳ１７では、帯域ＢＷα（ｂｐｓ）の値を０にする。
ステップＳ１８では、ルータの全帯域ＢＷｔ（ｂｐｓ）に係数Ｘ（例えば０．１）を掛けた結果を帯域ＢＷαの値にする。なお、係数Ｘ及びＫは各クラスの遅延時間がある値以上にならないように計算により求められる。
ステップＳ１９では、パケットを処理できなかった非優先クラスに対して、帯域ＢＷαを割り当てる。
【００３９】
なお、パケットを処理できなかった非優先クラスが複数存在する場合には、各クラスの遅延時間がある値以上にならないように、帯域ＢＷαの一部分をそれぞれの非優先クラスに割り当てる。
ステップＳ２０では、全帯域ＢＷｔから帯域ＢＷαを差し引いた結果を帯域ＢＷβの値に定める。
【００４０】
ステップＳ２１では、優先クラスのパケットについて、情報収集区間Ａ１で観測されたパケットのノード（ルータ）内滞在時間Ｔｉsys(A1)を次式によりクラス毎に（優先クラスのみ）計算する。
Ｔｉsys(A1)＝ｘｉ(A1)＋ρｉ(A1)ｘｉ(A1)／（２（１−ρｉ(A1)）)・・・(1)
但し、
ｘｉ(A1)＝８ｐｉ(A1)／ＢＷ(Ci，A1)：平均処理時間（ｓｅｃ）
ｐｉ(A1)：平均パケット長（ｂｙｔｅ）
ＢＷ(Ci，A1)：ｉ番目のクラスに割り当てた帯域の大きさ
ρｉ(A1)＝λｉ(A1)ｘｉ(A1)：使用率
λｉ(A1)＝ｑｉ(A1)／ｎＴ：到着率
ｑｉ(A1)：情報収集区間Ａ１に到着したｉ番目のクラスのパケット数
ステップＳ２２では、優先クラスについてクラス毎に帯域の割り当てを更新する。具体的には、ステップＳ２１で求めたパケットの滞在時間Ｔｉsys(A1)が各クラスの要求する遅延時間ｄｉよりも小さくなるように、帯域ＢＷ(Ci，A3)の大きさを割り当てる。すなわち、優先クラスについては直近のｎ周期の区間（Ａ１）で収集して得られた情報に基づいて、遅延時間ｄｉの条件を満足するような帯域を制御対象区間Ａ３に与える。
【００４１】
従って、全ての優先クラスについては、それが要求する遅延時間ｄｉをほぼ満足するように帯域が割り当てられる。また、遅延時間ｄｉを満足できないような優先クラスのパケットについては、予めそのような呼の受付を拒否するように呼受付で制御している。
ステップＳ２３では、まずステップＳ２２で優先グループに属する全てのクラスに割り当てた帯域ＢＷ(Ci，A3)の総和ＢＷｒを求める。
ステップＳ２４では、帯域ＢＷβから帯域ＢＷｒを差し引いた結果を残余の帯域ＢＷｚとして求める。
【００４２】
ステップＳ２５では、非優先クラスについて、残余の帯域ＢＷｚをクラス毎に割り当てる。具体的には、情報収集区間Ａ１で収集して得られた到着パケット数Ｎ(Ck,A1)及び平均パケット長ＰＬ(Ck,A1)（非優先クラスのみ）に基づいて、ｋ番目の各クラスＣｋの帯域ＢＷ(Ck,A3)を次式を用いて求める。
ＢＷ(Ck,A3)＝ＢＷｚ・ｕｋ・ｖｋ／(非優先クラスのｕｋ・ｖｋの総和)・・・(2)
但し
ｕｋ＝Ｎ(Ck,A1)（非優先クラスのみ）
ｖｋ＝ＰＬ(Ck,A1)（非優先クラスのみ）
すなわち、非優先クラスのパケットについては、情報収集区間Ａ１で到着したパケット情報量（パケット数×平均パケット長）に比例した割合で、帯域ＢＷｚを各クラスに配分する。このため、非優先クラスについては使用頻度が高くなるとますます多くの帯域が割り当てられる。また、使用頻度が低くなると割り当てられる帯域は小さくなる。
【００４３】
図１の処理によって各クラスに割り当てられる帯域ＢＷ（Ｃｊ）（ｊ＝１〜Ｎ）の大きさは、ルータのスケジューリングの際の「重み」に相当し、制御対象区間Ａ３における優先度に直結する。
すなわち、制御対象区間Ａ３におけるクラスＣｊの優先度の重みＷ(Cj,A3)は次式で与えられる。
【００４４】
Ｗ(Cj,A3)＝ＢＷ（Cj,A3)／ＢＷｔ ・・・（３）
但し、非優先グループの各クラスについては、優先グループの各クラスの待ち行列にパケットが存在しない場合のみ、上記の重みに従って待ち行列が選択されパケットが処理される。
次に、帯域割り当ての具体例について説明する。
【００４５】
（具体例１）
この例では、次のような状態を想定する。
ＢＷｔ：１２Ｍｂｐｓ
ＢＷα：０
Ｔ：５秒
ｎ：１
ｍ：１
クラス数Ｎ：３
クラス１：優先クラス
クラス２，クラス３：非優先クラス
現時点ｔ：０
また、情報収集区間Ａ１（−５，０）における各クラスの使用状態として次の状態を想定する。
【００４６】
クラス１の到着パケット数：２
クラス２の到着パケット数：２
クラス３の到着パケット数：６
クラス１の平均パケット長：１００
クラス２の平均パケット長：２００
クラス３の平均パケット長：３００
ここで、帯域ＢＷｒが８Ｍｂｐｓである場合を想定すると、制御対象区間Ａ３（５，１０）に対する各クラスへの割り当て帯域は次のようになる。
【００４７】
クラス１：８Ｍｂｐｓ
クラス２：(12-8)×2×200／(2×200＋6×300)＝0.727Ｍｂｐｓ
クラス３：(12-8)×6×300／(2×200＋6×300)＝3.273Ｍｂｐｓ
（具体例２）
この例では、観測周期Ｔの整数倍（ＫＴ）のある区間で、優先クラスのパケットの到着数が多すぎて、非優先グループに対する帯域の割り当てが少なくなり、非優先グループに属するあるクラス（未処理クラス）のパケットが全く処理されなかった場合を想定する。
【００４８】
この場合には、（ＫＴ）の区間毎に、次の制御対象区間Ａ３における全帯域のＸ（％）の帯域を前記未処理クラスに割り当てて処理する。係数Ｋ，Ｘは、各クラスの遅延時間がある値以上にならないように計算により求められる。
すなわち、未処理の非優先クラスを検出した場合には、図１のステップＳ１９で帯域ＢＷαを未処理の非優先クラスに割り当てる。
【００４９】
また、ここでは次の状態を想定する。
ＢＷｔ：１２Ｍｂｐｓ
Ｔ：５秒
ｎ：１
ｍ：１
クラス数Ｎ：３
クラス１：優先クラス
クラス２：非優先クラス
クラス３：非優先クラス（未処理クラス）
Ｋ：２
Ｘ：１０（％）
現時点ｔ：０
また、情報収集区間Ａ１（−５，０）における各クラスの使用状態として次の状態を想定する。
【００５０】
クラス１の到着パケット数：９
クラス２の到着パケット数：１
クラス３の到着パケット数：０
クラス１の平均パケット長：１００
クラス２の平均パケット長：２００
クラス３の平均パケット長：３００
ここで、帯域ＢＷｒが１１Ｍｂｐｓであり、区間（−１０，０）でクラス３のパケットが１個も処理されなかった場合を想定する。この場合、制御対象区間Ａ３（５，１０）に対する各クラスへの割り当て帯域は次のようになる。
【００５１】
クラス１：１２−１．２＝１０．８Ｍｂｐｓ
クラス２：０Ｍｂｐｓ
クラス３：１２×１０／１００＝１．２Ｍｂｐｓ
すなわち、未処理クラスであるクラス３に対しては、次の制御区間でそのパケットを処理できるように（１．２Ｍｂｐｓ）の帯域が優先的に割り当てられる。
【００５２】
従って、この形態では実時間性の高いクラスに対しては、前もって要求遅延時間を満たすのに十分な帯域を確保しておくことができる。また、直近のある時間区間において使用量（パケット数で判断）の多いクラスについては、さらに優先させてスループットを上げ、遅延時間を短くするための優先制御をダイナミックに実時間に近い微小時間内で実現することができる。
【００５３】
また、使用頻度の少ない通過パケット数の少ないクラスに対しても、各ノード（ルータ）内の遅延時間がある限度値以上にならないように最低限の帯域を割り当てることができる。
【００５４】
【発明の効果】
本発明によれば、使用頻度の高いクラスのパケットを優先させるように帯域を割り当てることができる。しかも、実時間性の高いアプリケーションの要求品質を満足するようにそのクラスのパケットの帯域を割り当てることができる。また、実時間性の低いクラスについても、比較的長い時間の平均的なスループットをある値以上にすることが可能である。
【００５５】
本発明の装置を採用することにより、ＩＰ網などを利用するユーザあるいは使用アプリケーションに対して利用頻度に応じた帯域の割り当てが可能になるため、網内の通信量を益々増加させ、網の利用を活発化させることが可能になる。
【図面の簡単な説明】
【図１】実施の形態のパケットスケジューリング処理を示すフローチャートである。
【図２】本発明を実施するルータの構成を示すブロック図である。
【図３】実施の形態の処理のタイミングを示すタイムチャートである。
【符号の説明】
１０ パケット情報収集部
１１ クラス決定部
１２ ヘッダ読み取り測定部
１３ パケットヘッダ解析／計算部
１４ ルーチングテーブル
１５ ヘッダ書き込み制御部
１６ トラヒック特性量計算部
１７ 割り当て帯域計算部
１８ 処理クラス指示部
１９ データベース
２０ スケジューリング部
２１ キューバッファ
２２ パケット処理部
３１ 時計
３２ タイマ
Claims (4)
- 入力されるパケットを複数のクラスに区分するとともに、前記複数のクラスを、処理に要する実時間が重要な優先グループと、前記優先グループ以外の非優先グループとに分類し、順次入力されるパケットを前記複数のクラス毎に設けられた待ち行列として保持し、処理のために前記待ち行列から取り出されるパケットの順序を決定するためのパケットスケジューリング方法であって、
前記非優先グループに割り当てられた帯域の大きさが過小であり、未処理の非優先クラス（以下、第１非優先クラスと称する）が存在する場合、前記未処理の非優先クラスのパケットを蓄積する待ち行列に対して、最初に全帯域ＢＷｔにＸ（Ｘは係数）を掛けて得られる帯域ＢＷαを割り当てる第１のステップと、
全帯域ＢＷｔから前記第１非優先クラスに割り当てた帯域ＢＷαを差し引いて得られた帯域ＢＷβに、前記優先グループ内の各優先クラスの要求遅延時間を満足するのに十分な帯域ＢＷｒを割り当てる第２のステップと、
前記非優先グループに属する非優先クラスから前記第１非優先クラスを除いて得られる第２非優先クラスに対して、帯域ＢＷβから帯域ＢＷｒを差し引いて得られた帯域ＢＷｚを割り当てる第３のステップと
から構成されることを特徴とするパケットスケジューリング方法。 - 請求項１に記載のパケットスケジューリング方法において、
前記第１非優先クラスが存在するか否かの判断は、特定期間の間に割り当てられた帯域が小さすぎて、パケットを全く処理できなかったクラスが存在するか否かを前記非優先グループに属するクラス毎に識別することにより行い、
前記非優先グループに属する各クラスのパケットを保持する各待ち行列から、前記パケットを取り出す優先度の決定は、直近の特定期間で検出された使用頻度の違いに応じた重みに基づいて行う
ことを特徴とするパケットスケジューリング方法。 - 請求項１記載のパケットスケジューリング方法において、
前記第１のステップにおいて、
前記非優先グループの各クラスの使用頻度を、前記特定期間に到着したパケットの数及び到着したパケットの平均パケット長に基づいてダイナミックに検出することを特徴とするパケットスケジューリング方法。 - 入力されるパケットを複数のクラスに区分するとともに、前記複数のクラスを、処理に要する実時間が重要な優先グループと、前記優先グループ以外の非優先グループとに分類し、順次に入力されるパケットを前記複数のクラス毎に設けられた待ち行列として蓄積し、処理のために前記待ち行列から取り出されるパケットの順序を決定するためのパケットスケジューリング装置であって、
前記非優先グループに割り当てられた帯域の大きさが過小であり、未処理の非優先クラス（以下、第１非優先クラスと称する）が存在する場合、前記未処理の非優先クラスのパケットを蓄積する待ち行列に対して、最初に全帯域ＢＷｔにＸ（Ｘは係数）を掛けて得られる帯域ＢＷαを割り当てる第１の帯域割り当て手段と、
全帯域ＢＷｔから前記第１非優先クラスに割り当てた帯域ＢＷαを差し引いて得られた帯域ＢＷβに、前記優先グループ内の各優先クラスの要求遅延時間を満足するのに十分な帯域ＢＷｒを割り当てる第２の帯域割り当て手段と、
前記非優先グループに属する非優先クラスから前記第１非優先クラスを除いて得られる第２非優先クラスに対して、帯域ＢＷβから帯域ＢＷｒを差し引いて得られた帯域ＢＷｚを割り当てる第３の帯域割り当て手段と、
から構成されることを特徴とするパケットスケジューリング装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2000305247A JP3649661B2 (ja) | 2000-10-04 | 2000-10-04 | パケットスケジューリング方法及びパケットスケジューリング装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2000305247A JP3649661B2 (ja) | 2000-10-04 | 2000-10-04 | パケットスケジューリング方法及びパケットスケジューリング装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2002118585A JP2002118585A (ja) | 2002-04-19 |
| JP3649661B2 true JP3649661B2 (ja) | 2005-05-18 |
Family
ID=18786145
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2000305247A Expired - Fee Related JP3649661B2 (ja) | 2000-10-04 | 2000-10-04 | パケットスケジューリング方法及びパケットスケジューリング装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3649661B2 (ja) |
Families Citing this family (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR20040052012A (ko) | 2002-12-13 | 2004-06-19 | 한국전자통신연구원 | 고속 패킷 망을 위한 패킷 스케줄링 시스템 및 방법 |
| JP4335619B2 (ja) | 2003-09-04 | 2009-09-30 | 株式会社エヌ・ティ・ティ・ドコモ | パケット優先制御装置及びその方法 |
| US7684408B2 (en) | 2003-09-30 | 2010-03-23 | Mitsubishi Denki Kabushiki Kaisha | Communication mode control method, mobile communication system, base station control apparatus, base station, and mobile communication terminal |
| US8289972B2 (en) | 2004-11-10 | 2012-10-16 | Alcatel Lucent | Gigabit passive optical network strict priority weighted round robin scheduling mechanism |
| JP2006287385A (ja) * | 2005-03-31 | 2006-10-19 | Nec Corp | Ｈｓｄｐａのパケットスケジューリング方法及び装置 |
| JP2006352420A (ja) * | 2005-06-15 | 2006-12-28 | Kddi Corp | 通信品質情報を含む品質パケットを送受信する端末、品質レポートサーバ及びプログラム |
| WO2007034552A1 (ja) | 2005-09-22 | 2007-03-29 | Mitsubishi Denki Kabushiki Kaisha | 移動局、固定局、通信システム及び通信方法 |
| JP5372988B2 (ja) * | 2011-03-22 | 2013-12-18 | 株式会社日立製作所 | データ同期サーバ、システム、及びデータ転送帯域制御方法 |
| JP2016127531A (ja) * | 2015-01-07 | 2016-07-11 | 日本電信電話株式会社 | 通信ネットワークシステムとそのネットワーク装置、通信帯域割当制御方法およびプログラム |
| KR102020978B1 (ko) * | 2019-04-03 | 2019-09-11 | 한화시스템(주) | Tdma 기반 전술 데이터 링크 모뎀장치 |
-
2000
- 2000-10-04 JP JP2000305247A patent/JP3649661B2/ja not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JP2002118585A (ja) | 2002-04-19 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US7969882B2 (en) | Packet transfer rate monitoring control apparatus, method, and program | |
| JP5365415B2 (ja) | パケット中継装置および輻輳制御方法 | |
| US7958260B2 (en) | Method and apparatus for queuing data flows | |
| EP1646192B1 (en) | Packet switch, scheduling device, drop control circuit, multicast control circuit and QOS control device | |
| KR100323258B1 (ko) | 버퍼 관리를 통한 속도 보증 | |
| JP3526269B2 (ja) | ネットワーク間中継装置及び該中継装置における転送スケジューリング方法 | |
| US7411971B2 (en) | Systems and methods for the schedule alignment of packet flow | |
| JP4454338B2 (ja) | パケット整形装置及びパケット整形方法 | |
| JPH0690255A (ja) | データネットワーク輻輳制御方法 | |
| JP3878603B2 (ja) | パケットスケジューリング方法及び装置 | |
| EP2310946A1 (en) | Dynamic setting of optimal buffer sizes in ip networks | |
| CA2462793C (en) | Distributed transmission of traffic streams in communication networks | |
| JP3649661B2 (ja) | パケットスケジューリング方法及びパケットスケジューリング装置 | |
| US20130044755A1 (en) | Scalable Packet Scheduling Policy for Vast Number of Sessions | |
| CN102413051B (zh) | 一种服务质量调度方法和装置 | |
| KR101737516B1 (ko) | 공평한 대역 할당 기반 패킷 스케줄링 방법 및 장치 | |
| US7142514B2 (en) | Bandwidth sharing using emulated weighted fair queuing | |
| EP2996293B1 (en) | A packet scheduling networking device for deadline aware data flows | |
| JP4087279B2 (ja) | 帯域制御方法およびその帯域制御装置 | |
| JP2001186170A (ja) | パケットスケジューリング方式及び方法及びこの方法を実行するプログラムを記録した記録媒体。 | |
| JP3601592B2 (ja) | パケットスケジューリング方法 | |
| JP3581056B2 (ja) | トラヒック観測装置、トラヒック監視装置、データグラム転送装置及びデータグラム転送システム | |
| JP4302014B2 (ja) | Ｅｔｈｅｒｎｅｔフレーム転送装置および方法 | |
| JP2002354025A (ja) | パケット転送制御装置 | |
| JP4391346B2 (ja) | 通信制御方法、通信制御装置、制御プログラム及び記録媒体 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20040426 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20040518 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20040720 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20040914 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20041112 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20050208 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20050215 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080225 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090225 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090225 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100225 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110225 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110225 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120225 Year of fee payment: 7 |
|
| LAPS | Cancellation because of no payment of annual fees |