(57)【要約】【課題】  データ輻輳時のキューイング遅延を低減可能なキューイングシステムを提供する。【解決手段】  データ格納領域１１〜１５には、優先移動先領域としてデータ格納領域２０，１９，１８，１７，１６がそれぞれ関連付けられている。データ格納領域１１にはデータＰがあり、このデータＰの優先度を「Ｐ」とする。データ格納領域１９にはデータＱがあり、このデータＱの優先度を「Ｑ」とする。データ格納領域１１にあるデータＰを移動する際に、次にデータ格納領域２０に移動するデータがデータ格納領域１９にあるデータＱと競合する場合、優先度「Ｐ」＞優先度「Ｑ」ならば、データＰをデータ格納領域２０に移動する。この場合、データＱは待ち状態となり、次回、移動される。【選択図】      図２
2008022179.tif 000002
【特許請求の範囲】
【請求項１】
キュー内の複数の格納領域にそれぞれデータを格納し、前記複数の格納領域に格納されたデータを予め設定された前記格納領域の順番にしたがって出力するキューイングシステムであって、
前記複数の格納領域を入力側と出力側との二つに分割し、前記入力側の格納領域に対して前記出力側の格納領域を優先移動先領域として関連付け、
入力データに予め付与されている優先度に基づいて前記入力側の格納領域に格納されたデータを前記優先移動先領域として関連付けた前記出力側の格納領域に移動させる制御手段を有し、
前記制御手段の制御にて優先度の高いデータから順次出力することを特徴とするキューイングシステム。
【請求項２】
前記データを前記優先移動先領域として関連付けた前記出力側の格納領域へ移動する際に、移動先に競合する他のデータがある場合でも、前記データの優先度が前記他のデータの優先度よりも高ければ前記データを前記優先移動先領域として関連付けた前記出力側の格納領域へ移動することを特徴とする請求項１記載のキューイングシステム。
【請求項３】
前記データが前記優先移動先領域として関連付けた前記出力側の格納領域に移動できない場合に当該データを１つ前方に移動することを特徴とする請求項２記載のキューイングシステム。
【請求項４】
前記複数の格納領域各々に、予め設定された優先度を持つデータの格納回数を計算するカウンタを設け、
前記データを前記優先移動先領域として関連付けた前記出力側の格納領域へ移動する際に前記カウンタの差分に基づいて当該データの移動の可否を決定することを特徴とする請求項１から請求項３のいずれか記載のキューイングシステム。
【請求項５】
前記複数の格納領域からなるキューを、各々予め設定された処理を実行するモジュール間に配設したことを特徴とする請求項１から請求項４のいずれか記載のキューイングシステム。
【請求項６】
前記キュー内の前記複数の格納領域な格納されたデータを優先度の高いモジュールから順番に分配することを特徴とする請求項５記載のキューイングシステム。
【請求項７】
請求項１から請求項６のいずれか記載のキューイングシステムを備えることを特徴とする通信端末。
【請求項８】
キュー内の複数の格納領域にそれぞれデータを格納し、前記複数の格納領域に格納されたデータを予め設定された前記格納領域の順番にしたがって出力するキューイングシステムに用いるキューイング制御方法であって、
前記複数の格納領域を入力側と出力側との二つに分割し、前記入力側の格納領域に対して前記出力側の格納領域を優先移動先領域として関連付け、
入力データに予め付与されている優先度に基づいて前記入力側の格納領域に格納されたデータを前記優先移動先領域として関連付けた前記出力側の格納領域に移動させることによって、優先度の高いデータから順次出力することを特徴とするキューイング制御方法。
【請求項９】
前記データを前記優先移動先領域として関連付けた前記出力側の格納領域へ移動する際に、移動先に競合する他のデータがある場合でも、前記データの優先度が前記他のデータの優先度よりも高ければ前記データを前記優先移動先領域として関連付けた前記出力側の格納領域へ移動することを特徴とする請求項８記載のキューイング制御方法。
【請求項１０】
前記データが前記優先移動先領域として関連付けた前記出力側の格納領域に移動できない場合に当該データを１つ前方に移動することを特徴とする請求項９記載のキューイング制御方法。
【請求項１１】
前記複数の格納領域各々に、予め設定された優先度を持つデータの格納回数を計算するカウンタを設け、
前記データを前記優先移動先領域として関連付けた前記出力側の格納領域へ移動する際に前記カウンタの差分に基づいて当該データの移動の可否を決定することを特徴とする請求項８から請求項１０のいずれか記載のキューイング制御方法。
【請求項１２】
前記複数の格納領域からなるキューを、各々予め設定された処理を実行するモジュール間に配設したことを特徴とする請求項８から請求項１１のいずれか記載のキューイング制御方法。
【請求項１３】
前記キュー内の前記複数の格納領域な格納されたデータを優先度の高いモジュールから順番に分配することを特徴とする請求項１２記載のキューイング制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はキューイングシステム、通信端末及びそれらに用いるキューイング制御方法に関し、特に通信端末でのデータのキューイング処理に関する。
【背景技術】
【０００２】
ネットワークを構成する通信端末においては、そのＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）化によって処理するデータ量が増加しており、それにともなってデータを処理する際に、ネットワーク内の要因による遅延及びそれらの端末内部の処理遅延等の影響を受けることになる。
【０００３】
上記の通信端末では、データを処理する際に、データのキューイング処理を行っている。ここで、キューイング処理とは、入力データをメモリに蓄積し、メモリに蓄積されたデータに対して処理順序を与え、その処理が行われるまで他のデータを待たせることで、メモリに蓄積されたデータを順次処理することを示している。
【０００４】
尚、キューイング処理としては、以下のような従来技術がある。
【特許文献１】特表２００２−０５６２３０号公報
【特許文献２】特開平０２−１９０９６０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
上述した従来のキューイング処理では、必然的に処理待ちのための遅延時間が発生する。また、従来のキューイング処理では、処理待ちのデータが増え、メモリ枯渇等によって蓄積できなくなったデータを廃棄している。
【０００６】
これによって、従来のキューイング処理では、データの再送等が発生し、さらに遅延が発生することが考えられる。このため、これらの遅延の累積が、装置内部のアプリケーションの性能に関して、多大な悪影響を及ぼしていくことが考えられる。
【０００７】
そこで、本発明の目的は上記の問題点を解消し、データ輻輳時のキューイング遅延を低減することができるキューイングシステム、通信端末及びそれらに用いるキューイング制御方法を提供することにある。
【課題を解決するための手段】
【０００８】
本発明によるキューイングシステムは、キュー内の複数の格納領域にそれぞれデータを格納し、前記複数の格納領域に格納されたデータを予め設定された前記格納領域の順番にしたがって出力するキューイングシステムであって、
前記複数の格納領域を入力側と出力側との二つに分割し、前記入力側の格納領域に対して前記出力側の格納領域を優先移動先領域として関連付け、
入力データに予め付与されている優先度に基づいて前記入力側の格納領域に格納されたデータを前記優先移動先領域として関連付けた前記出力側の格納領域に移動させる制御手段を備え、
前記制御手段の制御にて優先度の高いデータから順次出力している。
【０００９】
本発明による通信端末は、上記のキューイングシステムの手段を備えている。
【００１０】
本発明によるキューイング制御方法は、キュー内の複数の格納領域にそれぞれデータを格納し、前記複数の格納領域に格納されたデータを予め設定された前記格納領域の順番にしたがって出力するキューイングシステムに用いるキューイング制御方法であって、
前記複数の格納領域を入力側と出力側との二つに分割し、前記入力側の格納領域に対して前記出力側の格納領域を優先移動先領域として関連付け、
入力データに予め付与されている優先度に基づいて前記入力側の格納領域に格納されたデータを前記優先移動先領域として関連付けた前記出力側の格納領域に移動させることによって、優先度の高いデータから順次出力している。
【００１１】
すなわち、本発明のキューイングシステムは、データに予め付与されている優先度に基づいてキュー内のデータを移動させることによって、優先度の高いデータがより先に出力されることを特徴としている。
【００１２】
本発明のキューイングシステムでは、キュー内の格納領域に対して優先移動先領域を関連付けることによって、データＡは、関連付けされた格納領域へ移動するように制御される。この時の移動先に競合するデータＢがある場合でも、データＡの優先度がデータＢの優先度よりも高い場合には、関連付けされた格納領域に移動することが可能となる。
【００１３】
関連付けされた格納領域に移動できない場合には、通常のＦＩＦＯ（Ｆｉｒｓｔ  Ｉｎ  Ｆｉｒｓｔ  Ｏｕｔ）と同様に、１つ前方に移動する。このような動作によって，キューの出口が輻輳していない場合には、入力データを最短遅延時間で出力することが可能となる。
【００１４】
本発明のキューイングシステムでは、入力データに設定されている高優先度のデータが低優先度のデータをキュー内部で追い越すことが可能となるため、単純なＦＩＦＯを用いた場合と比べて、データ輻輳時のキューイング遅延を低減することが可能となる。これは、主としてデータ輻輳時にその効果がもっとも大きく現れるものと考えられる。
【発明の効果】
【００１５】
本発明は、上記のような構成及び動作とすることで、データ輻輳時のキューイング遅延を低減することができるという効果が得られる。
【発明を実施するための最良の形態】
【００１６】
次に、本発明の実施例について図面を参照して説明する。図１は本発明の一実施例によるキューイングシステムのデータ蓄積構造を示すブロック図である。図１において、本発明の一実施例によるキューイングシステムは、キューイング処理制御部１と、データ格納領域（Ｂｕｆ＿０〜Ｂｕｆ＿２Ｘ−１）１１〜２０とから構成されている。この場合、データ格納領域の数は、２Ｘ（Ｘ＞０）で表現可能な偶数長とする。
【００１７】
本発明の一実施例によるキューイングシステムでは、Ｂｕｆ［２Ｘ−１］で示される配列とみなした場合に、配列番号の和が２Ｘ−１になるバッファの組に対して関連付けをする。すなわち、本実施例では、複数のデータ格納領域１１〜２０を入力側（データ格納領域１１〜１５）と出力側（データ格納領域１６〜２０）との二つに分割し、入力側の格納領域（データ格納領域１１〜１５）に対して出力側の格納領域（データ格納領域２０，１９，１８，１７，１６）を優先移動先領域として関連付けている。
【００１８】
つまり、本実施例では、データ格納領域１１に対して優先移動先領域としてデータ格納領域２０を関連付け、データ格納領域１２に対して優先移動先領域としてデータ格納領域１９を関連付け、データ格納領域１３に対して優先移動先領域としてデータ格納領域１８を関連付け、データ格納領域１４に対して優先移動先領域としてデータ格納領域１７を関連付け、データ格納領域１５に対して優先移動先領域としてデータ格納領域１６を関連付けている。
【００１９】
図１において、データ格納領域１１はデータ格納領域２０と関連付けされているため、データ格納領域２０に移動されるデータが競合しなければ、データ格納領域１１にあるデータＰはデータ格納領域２０に移動される。これによって、本実施例では、最短遅延時間にて入力されたデータを出力することができる。
【００２０】
図２は本発明の一実施例による優先度の高いデータの移動方法を示す図である。図２において、データ格納領域１１にはデータＰがあり、このデータＰの優先度を「Ｐ」とする。データ格納領域１９にはデータＱがあり、このデータＱの優先度を「Ｑ」とする。図２には、優先度「Ｐ」＞優先度「Ｑ」とした場合に、データ格納領域２０にデータＰを移動する様子を示している。
【００２１】
図２においては、優先度の高いデータの移動方法を示している。データ格納領域１１にあるデータＰを移動する際に、次にデータ格納領域２０に移動するデータがデータ格納領域１９にあるデータＱと競合する場合、優先度「Ｐ」＞優先度「Ｑ」ならば、データＰをデータ格納領域２０に移動する。この場合、データＱは待ち状態となり、次回、移動される。これによって、本実施例では、優先度の高いデータＰが優先度の低いデータＱよりも先に出力されることになる。
【００２２】
図３は本発明の一実施例による優先度の低いデータの移動方法を示す図である。図３において、データ格納領域１１にはデータＰがあり、このデータＰの優先度を「Ｐ」とする。データ格納領域１９にはデータＱがあり、このデータＱの優先度を「Ｑ」とする。図３には、優先度「Ｐ」≦優先度「Ｑ」とした場合に、データＰをデータ格納領域１２に、データＱをデータ格納領域２０にそれぞれ移動させる様子と、その後、データＱが出力され、データ格納領域１２にあるデータＰをデータ格納領域１９に移動させる様子とを示している。
【００２３】
図３においては、優先度の低いデータの移動方法を示している。データ格納領域１１にあるデータＰを移動する際に、次にデータ格納領域２０に移動するデータがデータ格納領域１９にあるデータＱと競合する場合、優先度「Ｐ」≦優先度「Ｑ」ならば、データＱが優先移動され、データ格納領域２０に移動される。
【００２４】
データＰは一つ前方のデータ格納領域３０２に移動される。次の移動の際には、データ格納領域１２にあるデータＰは、データ格納領域１２に関連付けされている優先移動先領域であるデータ格納領域１９に関して、競合はないため、データ格納領域１９に移動される。データ格納領域２０にあるデータＱは出力される。
【００２５】
図４は図１のキューイング処理制御部１の動作を示すフローチャートである。これら図１〜図４を参照して本発明の一実施例によるキューイング処理制御の動作について説明する。尚、キューイング処理制御部１による処理動作はプログラム制御でも実現可能である。
【００２６】
キューイング処理制御部１は入力側のデータ格納領域（データ格納領域１１〜１５）から移動するデータがあるか否かをチェックし（図４ステップＳ１）、移動するデータがあれば、移動するデータの移動先に移動する他のデータがあるか否かをチェックする（図４ステップＳ２）。
【００２７】
キューイング処理制御部１は他のデータがなければ、入力側のデータ格納領域（データ格納領域１１〜１５）から優先移動先領域として関連付けられた出力側のデータ格納領域（データ格納領域１６〜２０）にデータを移動する（図２参照）（図４ステップＳ３）。
【００２８】
キューイング処理制御部１は他のデータがあれば、移動するデータの優先度が他のデータの優先度よりも高いかをチェックする（図４ステップＳ４）。キューイング処理制御部１は移動するデータの優先度が他のデータの優先度よりも高ければ、入力側のデータ格納領域（データ格納領域１１〜１５）から優先移動先領域として関連付けられた出力側のデータ格納領域（データ格納領域１６〜２０）にデータを移動する（図２参照）（図４ステップＳ５）。
【００２９】
キューイング処理制御部１は移動するデータの優先度が他のデータの優先度よりも低ければ、現在格納され立ているデータ格納領域から１つ前方のデータ格納領域にデータを移動いる（図３参照）（図４ステップＳ６）。キューイング処理制御部１は上記の処理を全てのデータ格納領域のチェックが終了するまで（図４ステップＳ７）、繰り返し実行する。
【００３０】
図５は本発明の一実施例によるデータ順序逆転の様子を示す図である。図５において、データ格納領域１２にはデータＰ4 があり、このデータＰ4 の優先度を「Ｐ4 」とする。データ格納領域１７にはデータＰ3 があり、このデータＰ3 の優先度を「Ｐ3 」とする。データ格納領域２０にはデータＲがあり、このデータＲの優先度を「Ｒ」とする。この時、優先度は優先度「Ｐ3 」＝優先度「Ｐ4 」＝優先度「Ｐ」＜優先度「Ｒ」とする。
【００３１】
図５においては、データ順序が逆転してしまう現象を示している。データ格納領域１２にあるデータＰ4 は、優先格納領域としてデータ格納領域１９が関連付けられている。データ格納領域１７にあるデータＰ3 は、データＰ4 よりも前に入力されたものとする。
【００３２】
データ格納領域１２にあるデータＰ4 は、図１に示すように、優先移動先領域として関連付けられているデータ格納領域１９に移動されるデータの競合がないために、データ格納領域１９に移動される。この時、データＰ3 とデータＰ4 とは、同じ優先度にも関わらず、先に入力されたデータＰ3 が後から入力されたデータＰ4 と出力順序が逆転してしまう。
【００３３】
図６は本発明の一実施例によるデータ順序逆転制御の方法を示す図である。図６において、データ格納領域１２にはデータＰ4 があり、このデータＰ4 の優先度を「Ｐ」とする。データ格納領域１７にはデータＰ3 があり、このデータＰ3 の優先度も「Ｐ」とする。データ格納領域２０にはデータＲがあり、このデータＲの優先度を「Ｒ」とする。この時、優先度「Ｐ」＜優先度「Ｒ」とする。
【００３４】
また、データ格納領域１２に対しては、優先度「Ｐ」のデータＰ4 が格納された回数に関するカウンタ２１が設けられている。データ格納領域１９に対しては、優先度「Ｐ」のデータＰ3 が格納された回数に関するカウンタ２２が設けられている。
【００３５】
図６においては、図５に示すデータ順序の逆転現象を回避する方法を示している。本実施例では、データ格納領域１１〜２０各々に、予め設定された優先度に関して、設定した優先度を持つデータの格納回数を計算するカウンタ２１，２２を設けている。
【００３６】
データ格納領域１２に設置されたカウンタ２１の値は、Ｎ＝４とする。データ格納領域１９に設置されたカウンタ２２の値は、Ｍ＝２とする。また、データ格納領域１２にあるデータが、そのデータ格納領域１２の優先格納領域として関連付けられているデータ格納領域１９に移動しようとする時、それぞれのカウンタ２１，２２の差分を計算し、Ｎ−Ｍ＝１を満たす場合には、優先移動先領域に移動可能とする。
【００３７】
データ格納領域１２にあるデータＰ4 は、そのデータ格納領域１２の優先格納領域として関連付けられているデータ格納領域１９に移動しようとするが、データ格納領域１２，１９に対応するカウンタ２１，２２の差分を計算すると、Ｎ−Ｍ＝４−２＝２となるため、データＰ4 はデータ格納領域１２の優先格納領域として関連付けられているデータ格納領域１９には移動できない。そのため、データＰ4 は一つ前方のデータ格納領域１３に移動する。これによって、本実施例では、同じ優先度を持つデータの入力順序と出力順序とが逆転することを防止することができる。
【００３８】
このように、本実施例では、入力データに設定されている高優先度のデータが低優先度のデータをキュー内部で、追い越せるため、単純なＦＩＦＯ（Ｆｉｒｓｔ  Ｉｎ  Ｆｉｒｓｔ  Ｏｕｔ）を用いた場合と比べて、データ輻輳時のキューイング遅延を低減することができる。本実施例では、主としてデータ輻輳時にその効果がもっとも大きく現れると考えられる。
【００３９】
図７は本発明の他の実施例によるキューイングシステムを使用する装置の構成例を示すブロック図である。図７において、キューイングシステムを使用する装置４は、上述した本発明の一実施例によるキューイングシステム（キューイングシステム４１，４３〜４５）を各モジュール［データ分配モジュール４２及び上位モジュール（Ｐ1 〜Ｐ3 ）４６〜４８］の間に用いることで、上位モジュール（Ｐ1 〜Ｐ3 ）４６〜４８の優先度にあわせたデータ分配が可能になる。
【００４０】
データ３１〜３３の優先度をそれぞれ「Ｐ1 」＞「Ｐ2 」＞「Ｐ3 」とする。データ分配モジュール４２の前段にキューイングシステム４１を配設した場合、データ分配モジュール４２によって読出されたデータは、優先度の高いものから、上位モジュール（Ｐ1 ）４６、上位モジュール（Ｐ2 ）４７、上位モジュール（Ｐ3 ）４８へと分配することが可能になる。
【００４１】
特に、データが輻輳状態にある時に、優先度の高いデータ３１から処理が可能になるため、装置全体としての処理時間が、優先度の高いモジュールから順番に有効に使うことができる。
【図面の簡単な説明】
【００４２】
【図１】本発明の一実施例によるキューイングシステムのデータ蓄積構造を示すブロック図である。
【図２】本発明の一実施例による優先度の高いデータの移動方法を示す図である。
【図３】本発明の一実施例による優先度の低いデータの移動方法を示す図である。
【図４】図１のキューイング処理制御部１の動作を示すフローチャートである。
【図５】本発明の一実施例によるデータ順序逆転の様子を示す図である。
【図６】本発明の一実施例によるデータ順序逆転制御の方法を示す図である。
【図７】本発明の他の実施例によるキューイングシステムを使用する装置の構成例を示すブロック図である。
【符号の説明】
【００４３】
１  キューイング処理制御部
４  キューイングシステムを使用する装置
１１〜２０  データ格納領域
２１，２２  カウンタ
３１〜３３  データ
４１，４３〜４５  キューイングシステム
４２  データ分配モジュール
４６〜４８  上位モジュール（Ｐ1 〜Ｐ3 ）
【図１】
2008022179.tif 000003
【図２】
2008022179.tif 000004
【図３】
2008022179.tif 000005
【図４】
2008022179.tif 000006
【図５】
2008022179.tif 000007
【図６】
2008022179.tif 000008
【図７】
2008022179.tif 000009