(57)【特許請求の範囲】
【請求項１】
パケットを入力ポートと出力ポートとの間でスイッチングするパケット交換装置において、廃棄アクションを決定する条件として平均キュー長を使用するパケット廃棄方式であって、
前記平均キュー長と現在のキュー長に対して変動する重みを付加して前記廃棄アクションを決定し、
前記重みは、予め決められた規定値の一定割合の初期値から増加し、前記規定値に達するとリセットされて前記初期値へ戻り、
前記初期値は、１より大きく前記規定値より小さい値であることを特徴とする平均キュー長算出方式。
【請求項２】
前記重みは、前記初期値から前記規定値まで単調に増加することを特徴とする請求項１記載の平均キュー長算出方式。
【請求項３】
前記重みは、ステップ関数であることを特徴とする請求項１記載の平均キュー長算出方式。
【請求項４】
パケットを入力ポートと出力ポートとの間でスイッチングするパケット交換装置において、廃棄アクションを決定する条件として平均キュー長を使用するパケット廃棄プログラムであって、
前記平均キュー長と現在のキュー長に対して変動する重みを付加して前記廃棄アクションを決定する廃棄アクション決定処理と、
前記廃棄アクション決定処理であって、付加する重みを変動させる重み算出処理と、
前記重み算出処理であって、重みを１より大きく予め決められた規定値より小さい前記規定値の一定割合の初期値から増加させ、前記規定値に達するとリセットして前記初期値へ戻す初期化処理とをコンピュータに実行させるための平均キュー長算出プログラム。
【請求項５】
前記重みは、初期値から規定値まで単調に増加することを特徴とする請求項４に記載の平均キュー長算出プログラム。
【請求項６】
前記重みは、ステップ関数であることを特徴とする請求項４に記載の平均キュー長算出プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ＡＴＭ（Asynchronous Transfer Mode）及びＩＰ（Internet Protocol ）に代表されるパケット通信技術を用いて特定の入力ポートと出力ポートとの間でパケットをスイッチングするパケット交換装置におけるパケット廃棄方式の平均キュー長計算方式及びプログラムに関する。
【０００２】
【従来の技術】
パケット交換装置内における平均キュー長を利用したパケット廃棄方式としては、非特許文献１に記載されたRandom Early Detection（ＲＥＤ）方式がある。図３にＲＥＤ方式を適用したキューの制御構成図を示す。ＲＥＤ方式では、キューに対して２種類の廃棄閾値（ｍｉｎＴＨ、ｍａｘＴＨ）を予め設定しておく。
【０００３】
図４はＲＥＤ方式の動作を説明するフロー図を示す。ＲＥＤ方式は、時系列的に変化するキュー長からその時点までの平均キュー長を算出して廃棄判定制御に用いることを特徴とする。パケットの廃棄判定を開始すると（ステップＡ１）、まずキューの平均キュー長を更新し（ステップＡ２）、平均キュー長と前記廃棄閾値の関係に従ってそのパケットに適用すべき廃棄アクションを決定する（ステップＡ３〜Ａ４）。
（１）平均キュー長がｍｉｎＴＨ未満である場合、パケットをキューに蓄積する（ステップＡ５）。
（２）平均キュー長がｍｉｎＴＨ以上かつｍａｘＴＨ未満である場合、廃棄確率を計算し（ステップＡ６）、その廃棄確率に従って廃棄すべきかどうかを決定する（ステップＡ７）。
（３）平均キュー長がｍａｘＴＨ以上である場合、パケットを廃棄する（ステップＡ８）。
従って、ＲＥＤ方式では平均キュー長の計算精度によって廃棄制御の適切性が大きく左右される。
【０００４】
標準的な平均キュー長の計算方式は、式（１）を用いて監視開始から現時点までの全ての観測値から計算する方法である（以後、これを標準方式と呼ぶ）。
0004192691.tif 000002
ここで、ｎはキュー長の監視開始からの観測回数（すなわち、平均キュー長更新回数）であり、Ｑn はｎ回目の観測時のキュー長、Ｑave は更新前の平均キュー長、Ｑave ’は更新後の平均キュー長である。以後、式（１）で計算される平均キュー長を累積平均キュー長と呼ぶ。
【０００５】
更に前記文献において、Exponential Weighted Moving Average （以後、ＥＷＭＡと呼ぶ）と呼ばれる平均キュー長計算方式が紹介されている。図５はＥＷＭＡ方式の動作を説明するフロー図を示す。ＥＷＭＡ技術では、平均キュー長の更新を開始すると（ステップＢ１）、現在のキュー長Ｑを確認し（ステップＢ２）、式（２）に基づいて平均キュー長が計算される（ステップＢ３）。
Ｑave ’＝（１−Ｗq ）×Ｑave ＋Ｗq ×Ｑ        ・・・（２）
ここで、Ｗq は固定の重みである。ＥＷＭＡ方式は、従来方式の式（１）の係数１／ｎを固定値のＷq に置き換えたものに相当する。
【０００６】
平均キュー長を利用した特許文献には、平均キュー長に従い、サービスクラスの帯域幅を変動させるもの（特許文献１）やＲＥＤを改良したパケット廃棄機構を提示するもの（特許文献２）などがある。
【０００７】
【特許文献１】
特開２００２−１３５３２９号公報
【特許文献２】
特開２００２−２２３２４０号公報
【非特許文献１】
IEEE/ACM Transactions on Networking, V. 1 N. 4, August 1993, p.397-413.
【０００８】
【発明が解決しようとする課題】
以上説明した従来技術による課題について説明する。
図６はランダム変数を１０００回生成させた時のランダム変数の時系列変化を示す。平均値計算の応答性の観測のため、試行５００回目から６００回目は意図的に生成するランダム変数を０にしている。図７は図６のランダム変数の生成の都度、標準方式とＥＷＭＡ方式で算出した平均値の時系列変化を示す。縦軸が計算された平均値、横軸が試行回数を示す。図７には、標準方式により算出した平均値、ＥＷＭＡ方式（Ｗq ＝０．０１）により算出した平均値、ＥＷＭＡ方式（Ｗq ＝０．１）により算出した平均値を示す。
【０００９】
図７より、標準方式では、監視開始から十分な時間が経過するとｎが大きくなり、キュー長変動に対しての応答性が悪くなる特性を有している。試行５００回目から６００回目のランダム変数＝０の区間では計算される平均キュー長はあまり変化していないことからその特性は明白である。すなわち、キューは空なのに平均キュー長は依然として大きな値を保持する傾向があり、バッファリソースが余っているにも関わらずパケットが不必要に廃棄されるために通信品質をひどく劣化させる恐れがある。
【００１０】
これに対してＥＷＭＡ方式では、重みＷq を固定値にすることで監視開始から十分な時間が経過した場合の応答性を改善している。しかし、監視開始直後も現在キュー長に乗算する重みＷq の値が小さい為に、計算される平均キュー長が妥当な値になるまでに相当な時間がかかる。ＥＷＭＡ方式では、監視開始直後は適切な廃棄制御ができずに大量のパケット受信によるバッファ枯渇、及びキューイング遅延の増大といった通信品質の劣化が深刻になる。また、重みＷq を０．１位に大きくすると、応答性が過敏になり、監視開始直後の応答性を改善するが、全体的に不安定となり、パケット廃棄アクションを決定する指標として正確性に欠けることになる。
【００１１】
上記問題に鑑み、本発明は、パケット交換装置におけるパケット廃棄方式に関して、監視開始直後でも応答性の高く、かつ安定した正確な平均キュー長を計算する方式を提供することを目的とする。
【００１２】
【課題を解決するための手段】
上記問題を解決する為に、本発明における平均キュー長算出方式は、パケットを入力ポートと出力ポートとの間でスイッチングするパケット交換装置において、廃棄アクションを決定する条件として平均キュー長を使用するパケット廃棄方式であって、平均キュー長と現在のキュー長に対して変動する重みを付加して前記廃棄アクションを決定し、重みは、予め決められた規定値の一定割合の初期値から増加し、規定値に達するとリセットされて初期値へ戻り、初期値は、１より大きく規定値より小さい値であることを特徴とする。
【００１３】
また、本発明における平均キュー長算出方式は、重みが、初期値から規定値まで単調に増加することを特徴とする。
【００１４】
また、本発明における平均キュー長算出方式は、重みが、ステップ関数であることを特徴とする。
【００１５】
また、本発明における平均キュー長算出プログラムは、パケットを入力ポートと出力ポートとの間でスイッチングするパケット交換装置において、廃棄アクションを決定する条件として平均キュー長を使用するパケット廃棄プログラムであって、平均キュー長と現在のキュー長に対して変動する重みを付加して廃棄アクションを決定する廃棄アクション決定処理と、廃棄アクション決定処理であって、付加する重みを変動させる重み算出処理と、重み算出処理であって、重みを１より大きく予め決められた規定値より小さい規定値の一定割合の初期値から増加させ、規定値に達するとリセットして初期値へ戻す初期化処理とをコンピュータに実行させることを特徴とする。
【００１６】
また、本発明における平均キュー長算出プログラムは、重みが、初期値から規定値まで単調に増加することを特徴とする。
【００１７】
また、本発明における平均キュー長算出プログラムは、重みが、ステップ関数であることを特徴とする。
【００２１】
本発明に関わるパケット交換装置の平均キュー長計算方式は、平均キュー長の更新計算に変動する重みを使用し、かつこの変動する重みが規定値に達するとリセットすることを特徴とする。これにより、平均キュー長監視から長時間が経過しても重みが極端な値になってキュー長の変動に対して応答性が悪くなるのを防止することが可能である。また、重みが定数の場合に較べ、これが変動する場合は式（３）の第２項の寄与を大きくすることになり、監視直後の急激なキュー長変動に対しても応答性を改善することができる。
【００２２】
また、本発明に関わるパケット交換装置の平均キュー長計算方式は、リセットした重みの初期値として規定値の一定の割合を用いることを特徴とする。これにより、重みをリセットしたときに応答性が過敏になり平均キュー長が不必要に揺らぐのを防止することができる。
【００２３】
【発明の実施の形態】
以下、本発明の一実施形態について図面を参照して説明する。
図１は、本発明の一実施形態における平均キュー長計算方式の処理フロー図である。本発明の一実施形態による平均キュー長計算方式は、重みＷを更新するステップと、重みＷが最大値Ｗmax に達すると初期値Ｗini に更新するステップを備えていることを特徴とする。
【００２４】
平均キュー長の更新タイミングになると（ステップＳ１）、まず現在のキュー長Ｑを確認する（ステップＳ２）。次の重み更新処理（ステップＳ３）では、前回の平均キュー長更新時に使用した重みＷに対して予め決められた増分を加算して、今回の平均キュー長計算処理に使用する重みＷを算出する。本実施形態では増分として１を使用する。重みの更新処理として増加させることや、増分の大きさは本発明を限定するものではない。本発明の主旨及び特許請求の範囲内での種々の変形は本発明の範囲内である。
【００２５】
更新した重みＷと予め決められた最大値Ｗmax を比較し（ステップＳ４）、Ｗ＞Ｗmax であれば、予め決められた初期値Ｗini にリセットする（ステップＳ６）。そして、前回の平均キュー長Ｑave と現在キュー長Ｑを用いて式（３）に従って新平均キュー長Ｑave ’を計算する（ステップＳ５）。
Ｑave ’＝（１−１／Ｗ）×Ｑave ＋１／Ｗ×Ｑ        ・・・（３）
今回の平均キュー長計算処理で使用した重みＷは、次回の計算時の重み更新処理で使用するため、メモリに保存しておく。
【００２６】
本発明を適用した場合の効果を定量的に評価したデータを図２に示す。本データは、図６と同じランダム変数に対して計算した平均値の時系列変化を示す。比較の為、標準方式による平均値をＥＷＭＡ方式（Ｗq ＝０．０１）による平均値も併せて示す。なお、本発明による計算方式の制御パラメータは、以下のように選択した：
重みＷの増分＝１、
重みの最大値Ｗmax ＝１００、
重みの初期値Ｗini ＝１０（＝Ｗmax ×１０％）。
【００２７】
本明細書及び図面で詳細に示した制御パラメータ例は本発明を限定するものではない。本発明の主旨及び特許請求の範囲内での種々の変形は本発明の範囲内である。
【００２８】
グラフから明らかなように、本発明によって計算した平均キュー長は、試行５００回目から６００回目のランダム変数＝０区間でも従来方式より応答性が良く、より低い値になっている。これにより、依然として平均キュー長が高い値を保持したままで、パケットが不必要に廃棄されるのを防止することが可能である。また、監視開始直後でも従来方式より早い応答性を示し、この区間で適切なパケット廃棄制御を動作させることが可能であり、従来方式で問題であった通信品質の劣化を防ぐことが可能である。
【００２９】
なお、重みの初期値としては１より大きく重みの最大値Ｗmax （規定値）より小さいことが望ましい。
【００３０】
以上のように、本実施形態によれば、キュー長の変動応答性が高く、かつ監視開始直後でも応答性の高い平均キュー長の計算方式を提供することが可能となり、本方式とパケット廃棄方式を組み合わせることによって、輻輳状態に即応してバッファ資源を効率的に利用するパケット廃棄制御を実現できる。
【００３１】
以上、本明細書及び図面で詳細に示した実施形態は本発明を限定するものではない。本発明の主旨及び特許請求の範囲内での種々の変形は本発明の範囲内である。
【００３２】
【発明の効果】
以上説明したように、本発明は、平均キュー長を計算する際に、変動する重みを用い、かつその重みが規定値に達するとリセットされるように構成されているので、監視直後の急激なキュー長変動に対しても応答性を改善することが可能となり、また平均キュー長監視から長時間が経過しても重みが極端な値になってキュー長の変動に対して応答性が悪くなるのを防止することが可能となる。
又、リセットした重みの初期値に規定値の一定の割合を用いるように構成したことで、重みをリセットしたときに応答性が過敏になり平均キュー長が不必要に揺らぐのを防止することが可能となる。
【図面の簡単な説明】
【図１】本発明の一実施形態における平均キュー長計算方式の処理フローチャートである。
【図２】本発明の一実施形態の効果を示すデータ面グラフである。
【図３】ＲＥＤ方式のキュー構成を示す図である。
【図４】ＲＥＤ方式の処理手順を示すフローチャートである。
【図５】従来の平均キュー長計算方式の処理手順を示すフローチャートである。
【図６】ランダム変数の生成の様子を示すデータグラフである。
【図７】従来の平均キュー長計算方式の効果を示すデータグラフである。
【符号の説明】
１  キュー
２  パケット
【図１】
0004192691.tif 000003
【図２】
0004192691.tif 000004
【図３】
0004192691.tif 000005
【図４】
0004192691.tif 000006
【図５】
0004192691.tif 000007
【図６】
0004192691.tif 000008
【図７】
0004192691.tif 000009