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