(57)【特許請求の範囲】
【請求項１】
バッファ内の滞留パケット量から判定される輻輳状態レベルの遷移が検出されるたび、当該遷移後の輻輳状態レベルをバッファの上流側に通知する方式の輻輳状態通知方法にあって、
上方に遷移した輻輳状態レベルは流入量規制用の第１の状態通知キューを介して通知する一方、下方に遷移した輻輳状態レベルは流入量緩和用の第２の状態通知キューを介して通知することとし、いずれの状態通知キューにも通知すべき輻輳状態レベルが存在する場合には、第１の状態通知キューに存在している輻輳状態レベルを第２の状態通知キューに存在している輻輳状態レベルに優先させて通知する
ことを特徴とする輻輳状態通知方法。
【請求項２】
バッファ内の滞留パケット量から判定される輻輳状態レベルの遷移が検出されるたび、当該遷移後の輻輳状態レベルをバッファの上流側に通知する方式の輻輳状態通知方法にあって、
上記輻輳状態レベルの判定の際、その遷移方向に応じて異なる判定閾値を使用すると共に、
上方に遷移した輻輳状態レベルは流入量規制用の第１の状態通知キューを介して通知する一方、下方に遷移した輻輳状態レベルは流入量緩和用の第２の状態通知キューを介して通知することとし、いずれの状態通知キューにも通知すべき輻輳状態レベルが存在する場合には、第１の状態通知キューに存在している輻輳状態レベルを第２の状態通知キューに存在している輻輳状態レベルに優先させて通知する
ことを特徴とする輻輳状態通知方法。
【請求項３】
請求項１又は２に記載の輻輳状態通知方法であって、
輻輳状態レベルが第１の状態通知キューを介して通知される場合、被通知側で保持されているパケット流入量制御用の輻輳状態レベルを通知された値に更新し、
輻輳状態レベルが第２の状態通知キューを介して通知される場合、被通知側で保持されているパケット流入量制御用の輻輳状態レベルよりも通知された値が１段階低い値であり、かつ、遷移方向に応じて値が増減される状態遷移変数と上記パケット流入量制御用の輻輳状態レベルの値が一致するとの条件が満たされるか判定し、条件が満たされるとき上記パケット流入量制御用の輻輳状態レベルを通知された値に更新し、条件が満たされないとき現在の値をそのまま保持する
ことを特徴とする輻輳状態通知方法。
【請求項４】
請求項１、２又は３に記載の輻輳状態通知方法であって、
上記第１の状態通知キューと第２の状態通知キューがいずれも空のとき、定期的に最新の輻輳状態レベルを通知するようにした
ことを特徴とする輻輳状態通知方法。
【請求項５】
請求項１、２又は４に記載の輻輳状態通知方法であって、
輻輳状態レベルが第１の状態通知キューを介して通知される場合、被通知側で保持されているパケット流入量制御用の輻輳状態レベルを通知のあった値に更新し、
輻輳状態レベルが第２の状態通知キューを介して通知される場合、第１の状態通知キューから最後に通知された輻輳状態レベルに付されていたタイムスタンプよりも通知のあった輻輳状態レベルに付されているタイムスタンプの方が時間的に後であるか否か判定し、時間的に後であるとき上記パケット流入量制御用の輻輳状態レベルを通知のあった値に更新し、その他のとき現在の値をそのまま保持する
ことを特徴とする輻輳状態通知方法。
【請求項６】
バッファ内の滞留パケット量から判定される輻輳状態レベルの遷移が検出されるたび、当該遷移後の輻輳状態レベルをバッファの上流側に通知する輻輳状態通知装置であって、
上方遷移した遷移後の輻輳状態レベルを先入れ先出し方式で出力する第１の状態通知キューと、下方遷移した遷移後の輻輳状態レベルを先入れ先出し方式で出力する第２の状態通知キューとを備え、上記第１の状態通知キューと上記第２の状態通知キューがいずれも通知すべき輻輳状態レベルを有する場合、上記第１の状態通知キューに存在する輻輳状態レベルの通知が優先される
ことを特徴とする輻輳状態通知装置。
【請求項７】
バッファ内の滞留パケット量から判定される輻輳状態レベルの遷移が検出されるたび、当該遷移後の輻輳状態レベルをバッファの上流側に通知する輻輳状態通知装置であって、
輻輳状態レベルの上方遷移の判定に使用する判定閾値と下方遷移の判定に使用する判定閾値とで異なる値を使用する輻輳状態監視手段を備えると共に、
上方遷移した遷移後の輻輳状態レベルを先入れ先出し方式で出力する第１の状態通知キューと、下方遷移した遷移後の輻輳状態レベルを先入れ先出し方式で出力する第２の状態通知キューとを備え、上記第１の状態通知キューと上記第２の状態通知キューがいずれも通知すべき輻輳状態レベルを有する場合、上記第１の状態通知キューに存在する輻輳状態レベルの通知が優先される
ことを特徴とする輻輳状態通知装置。
【請求項８】
請求項６又は７に記載の輻輳状態通知装置であって、
輻輳状態レベルが第１の状態通知キューを介して通知される場合、自身が保持するパケット流入量制御用の輻輳状態レベルを通知された値に更新し、輻輳状態レベルが第２の状態通知キューを介して通知される場合、自身が保持するパケット流入量制御用の輻輳状態レベルよりも通知された値が１段階低い値であり、かつ、遷移方向に応じて値が増減される状態遷移変数と上記パケット流入量制御用の輻輳状態レベルの値が一致するとの条件が満たされるか判定し、条件が満たされるとき上記パケット流入量制御用の輻輳状態レベルを通知された値に更新し、条件が満たされないとき現在の値をそのまま保持する輻輳状態保持手段を更に備えることを特徴とする輻輳状態通知装置。
【請求項９】
請求項６、７又は８に記載の輻輳状態通知装置であって、
上記第１の状態通知キューと第２の状態通知キューがいずれも空のとき、定期的に最新の輻輳状態レベルを通知する定期通知手段を更に備えることを特徴とする輻輳状態通知装置。
【請求項１０】
請求項６、７又は９に記載の輻輳状態通知装置であって、
輻輳状態レベルが第１の状態通知キューを介して通知される場合、自身が保持するパケット流入量制御用の輻輳状態レベルを通知のあった値に更新し、輻輳状態レベルが第２の状態通知キューを介して通知される場合、第１の状態通知キューから最後に通知された輻輳状態レベルに付されていたタイムスタンプよりも通知のあった輻輳状態レベルに付されているタイムスタンプの方が時間的に後であるか否か判定し、時間的に後であるとき上記パケット流入量制御用の輻輳状態レベルを通知のあった値に更新し、その他のとき現在の値をそのまま保持する輻輳状態保持手段を更に備えることを特徴とする輻輳状態通知装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、パケット交換装置に用いて好適な輻輳状態通知方法及び装置に関する。例えば、ＡＴＭ（Ａｓｙｎｃｈｒｏｎｏｕｓ  Ｔｒａｎｓｆｅｒ  Ｍｏｄｅ）交換機及びＡＴＭルータ等に適用し得る
【０００２】
【従来の技術】
以下では、ＡＴＭセルをスイッチングするＡＴＭ装置について説明する。この種の装置は、ＡＴＭセルをスイッチングする際一般に、バッファを用いてスイッチング制御を行う。しかし、バッファ容量は有限であるため、出力側のスループットに対して入力側のスループットが大きいと、バッファ溢れを起こす可能性がある。
【０００３】
バッファ溢れが起きると、その溢れる瞬間に入力されたパケットは、パケットの重要度（優先パケット）とは無関係に消失してしまう。そこで、優先パケットは極力消失させないために、バッファが溢れる前にバッファの輻輳状態を検出し、入力側でパケットの優先度に従って優先度の低いパケットを廃棄する機能部が必要となる。
【０００４】
図２に上記機能部に関連する従来構成を示す。この機能部は、バッファ溢れが生じる前に入力パケットを選択的に廃棄する入力パケット廃棄制御部１０（優先度識別部１１、抑制制御部１２、抑制判定部１３）と、バッファに滞留するパケット量を監視し輻輳状態を通知するバッファ制御部２０（バッファ２１）とを構成要素に有する。
【０００５】
バッファ制御部２０は、バッファ２１の滞留パケット量がある「特定の量」に達したことを輻輳状態監視部（図２では不図示）で検出する。ここでの「特定の量」は必ずしも１つでなくとも良い。従って、輻輳状態レベルを数段階に設定したのであれば、バッファの滞留パケット数の増減に伴って輻輳状態は遷移する。例えば、輻輳状態レベルを３段階に設定する場合、バッファ制御部２０は、現在の滞留パケット数に応じた輻輳状態レベルを入力パケット廃棄制御部１０に通知する。
【０００６】
入力パケット廃棄制御部１０は、入力パケット毎の優先度を優先度識別部１１で抽出すると、その情報を抑制判定部１３に与える。抑制判定部１３は、与えられた優先度に対応するバッファの輻輳状態レベルを抑制制御部１２に与える。抑制制御部１２は、与えられた輻輳状態レベルに応じた抑制制御（パケットの廃棄等）を行う。かくして、バッファ輻輳時には、より優先度の低いパケットが廃棄され、優先度の高いパケットの消失が極力抑制される。
【０００７】
一例を説明する。ここでは、バッファの輻輳状態レベルを（０、１、２）の３段階とし（輻輳の度合いは０＜１＜２の順に大きいとする。）、また入力パケットの優先度を（ａ、ｂ、ｃ）の３段階とする（優先度はａ＜ｂ＜ｃの順に高いとする。）。このとき、廃棄処理は入力パケットの優先度に応じて次のように実行される。
【０００８】
ａ）バッファの輻輳状態レベル（０）が通知された場合
入力パケットの廃棄を行わない
ｂ）バッファの輻輳状態レベル（１）が通知された場合
入力パケットの優先度（ａ）のパケットのみが廃棄される
ｃ）バッファの輻輳状態レベル（２）が通知された場合
入力パケットの優先度（ａ、ｂ）のパケットのみが廃棄される
ここで、ａ）、ｂ）、ｃ）の状態遷移において規制方向とは、ａ）→ｂ）やｂ）→ｃ）の遷移を指す。また、緩和方向とは、ｃ）→ｂ）やｂ）→ａ）の遷移を指す。
【０００９】
【発明が解決しようとする課題】
ところで、この装置構成は大規模化すると、図３に示すようにバッファの輻輳状態通知用に個々の入力に対応した通知ルートが必要となり、その変動は全入力パケットのスループットの和に比例して大きくなる。
【００１０】
しかし実際上、バッファ輻輳による入力パケットの廃棄はそれほど発生しないようにネットワークの設計が行われているのに加え、輻輳の度合いが高まる方向への輻輳状態の遷移（すなわち、規制方向への遷移）は比較的リアルタイムで通知されなければならないのに対し、輻輳の度合いが下がる方向への輻輳状態の遷移（すなわち、緩和方向への遷移）の通知はリアルタイム性がさほど要求されないという特性がある。
【００１１】
これは、バッファ溢れの回避により重要度（優先度）の高いパケットを極力消失させないという機能を実現する上で、規制方向はバッファの輻輳に連動して速やかに遷移することが求められるが、緩和方向は比較的ゆっくり遷移しても問題ないものと考えられる。
【００１２】
すなわち、従来の構成及び方法は、輻輳通知の機能部にて実使用上、過剰な性能を有しており、入力パケットのスループットを上げていった場合に（すなわち、装置の大容量化を行う際に）、必要以上に装置コストを上昇させると共に、スループットの向上に伴う技術面（実装面、速度面）でのボトルネックが発生するという課題があった。
【００１７】
【課題を解決するための手段】
（Ａ）かかる課題を解決するため、以下の第１の手段を提案する。すなわち、バッファ内の滞留パケット量から判定される輻輳状態レベルの遷移が検出されるたび、当該遷移後の輻輳状態レベルをバッファの上流側に通知する方式の輻輳状態通知方法にあって、上方に遷移した輻輳状態レベルは流入量規制用の第１の状態通知キューを介して通知する一方、下方に遷移した輻輳状態レベルは流入量緩和用の第２の状態通知キューを介して通知することとし、いずれの状態通知キューにも通知すべき輻輳状態レベルが存在する場合には、第１の状態通知キューに存在している輻輳状態レベルを第２の状態通知キューに存在している輻輳状態レベルに優先させて通知する方法を提案する。
【００１８】
このように、輻輳状態レベルの遷移の通知を状態通知キューを介して実行することにより、バースト的な輻輳状態レベルの遷移を平均的なスループットの通知として実現できる。また、状態通知キューを流入規制用の第１の状態通知キューと流入緩和用の第２の状態通知キューとの２種類とし、第１の状態通知キューに存在する輻輳状態レベルの通知を第２の状態通知キューに存在する輻輳状態レベルの通知に優先させるため、規制方向の通知をリアルタイムで実現できる。
【００２１】
（Ｂ）また、以下の第２の手段を提案する。この第２の手段では、バッファ内の滞留パケット量から判定される輻輳状態レベルの遷移が検出されるたび、当該遷移後の輻輳状態レベルをバッファの上流側に通知する方式の輻輳状態通知方法にあって、上記輻輳状態レベルの判定の際、その遷移方向に応じて異なる判定閾値を使用すると共に、上方に遷移した輻輳状態レベルは流入量規制用の第１の状態通知キューを介して通知する一方、下方に遷移した輻輳状態レベルは流入量緩和用の第２の状態通知キューを介して通知することとし、いずれの状態通知キューにも通知すべき輻輳状態レベルが存在する場合には、第１の状態通知キューに存在している輻輳状態レベルを第２の状態通知キューに存在している輻輳状態レベルに優先させて通知する方法を提案する。
【００２２】
この第２の手段によれば、輻輳状態レベルの遷移頻度を減らせる（すなわち、輻輳状態通知のスループットを低く抑える）ことができるのに加え、バースト的な輻輳状態レベルの遷移を平均的なスループットの通知として実現できる。これにより、技術的なボトルネックの解消をより確実に実現できる。さらに、状態通知キューを流入規制用の第１の状態通知キューと流入緩和用の第２の状態通知キューとの２種類とし、第１の状態通知キューに存在する輻輳状態レベルの通知を第２の状態通知キューに存在する輻輳状態レベルの通知に優先させるため、規制方向の通知をリアルタイムで実現できる。
【００２５】
（Ｃ）また、以下の第３の手段を提案する。この第３の手段では、第１又は第２の手段に、輻輳状態レベルが第１の状態通知キューを介して通知される場合、被通知側で保持されているパケット流入量制御用の輻輳状態レベルを通知された値に更新し、輻輳状態レベルが第２の状態通知キューを介して通知される場合、被通知側で保持されているパケット流入量制御用の輻輳状態レベルよりも通知された値が１段階低い値であり、かつ、遷移方向に応じて値が増減される状態遷移変数と上記パケット流入量制御用の輻輳状態レベルの値が一致するとの条件が満たされるか判定し、条件が満たされるとき上記パケット流入量制御用の輻輳状態レベルを通知された値に更新し、条件が満たされないとき現在の値をそのまま保持する機能を追加する。
【００２６】
この第３の手段によれば、状態遷移変数（例えば、第１の輻輳状態キューから入力があるたび増加され、第２の輻輳状態キューから入力があるたび減少される。）によって輻輳状態レベルの遷移方向が短期的にいずれの方向にあるかを把握し、保持されている輻輳状態レベルを緩和する場合には、所定の条件を満たす場合についてのみこれを許可することにより、大量に発生した輻輳状態レベルの遷移の一部が通知されないような事態が生じたとしても、いずれかの時点でバッファ内の輻輳状態レベルと保持されている輻輳状態レベルとを一致させることができる。
【００２７】
また、バッファ内の輻輳状態レベルよりも保持されている輻輳状態レベルの方が大きい状態での不一致は残り得るが、この場合でもバッファ溢れのような致命的な事態は生じ得ないため状態通知キューを比較的浅く（小さく）することが可能となり、装置全体のコスト低下を実現できる。
【００２８】
（Ｄ）また、以下の第４の手段を提案する。すなわち、第１、第２又は第３の手段に、上記第１の状態通知キューと第２の状態通知キューがいずれも空のとき、定期的に最新の輻輳状態レベルを通知する機能を追加する。
【００２９】
この第４の手段によれば、第１及び第２の状態通知キューがいずれも空のときに定期的に最新の輻輳状態レベルが通知されるため、仮に状態通知キューの深さ（大きさ）が十分でなく、大量に発生した輻輳状態レベルの遷移の一部が通知されないような事態が生じたとしても、その後の定期通信によって輻輳状態レベルを早期に最新の状態に一致させることができる。この結果、状態通知キューを比較的浅く（小さく）することが可能となり、装置全体のコスト低下を実現できる。また、定期通知によって必要以上に入力パケットが廃棄される事態を回避することもできるため、装置の性能向上を実現できる。
【００３０】
（Ｅ）また、以下の第５の手段を提案する。この第５の手段では、第１、第２又は第４の手段に、輻輳状態レベルが第１の状態通知キューを介して通知される場合、被通知側で保持されているパケット流入量制御用の輻輳状態レベルを通知のあった値に更新し、輻輳状態レベルが第２の状態通知キューを介して通知される場合、第１の状態通知キューから最後に通知された輻輳状態レベルに付されていたタイムスタンプよりも通知のあった輻輳状態レベルに付されているタイムスタンプの方が時間的に後であるか否か判定し、時間的に後であるとき上記パケット流入量制御用の輻輳状態レベルを通知のあった値に更新し、その他のとき現在の値をそのまま保持する機能を追加する。
【００３１】
この第５の手段によれば、状態遷移変数（例えば、第１の輻輳状態キューから入力があるたび増加され、第２の輻輳状態キューから入力があるたび減少される。）によって輻輳状態レベルの遷移方向が短期的にいずれの方向にあるかを把握し、保持されている輻輳状態レベルを緩和する場合には、所定の条件を満たす場合についてのみこれを許可することにより、大量に発生した輻輳状態レベルの遷移の一部が通知されないような事態が生じたとしても、いずれかの時点でバッファ内の輻輳状態レベルと保持されている輻輳状態レベルとを一致させることができる。
【００３２】
また、バッファ内の輻輳状態レベルよりも保持されている輻輳状態レベルの方が大きい状態での不一致は残り得るが、この場合でもバッファ溢れのような致命的な事態は生じ得ないため状態通知キューを比較的浅く（小さく）することが可能となり、装置全体のコスト低下を実現できる。
【００３７】
（Ｆ）また、以下の第６の手段を提案する。すなわち、バッファ内の滞留パケット量から判定される輻輳状態レベルの遷移が検出されるたび、当該遷移後の輻輳状態レベルをバッファの上流側に通知する輻輳状態通知装置であって、上方遷移した遷移後の輻輳状態レベルを先入れ先出し方式で出力する第１の状態通知キューと、下方遷移した遷移後の輻輳状態レベルを先入れ先出し方式で出力する第２の状態通知キューとを備え、上記第１の状態通知キューと上記第２の状態通知キューがいずれも通知すべき輻輳状態レベルを有する場合、上記第１の状態通知キューに存在する輻輳状態レベルの通知が優先されるものを提案する。
【００３８】
このように、輻輳状態レベルの遷移の通知を状態通知キューを介して実行することにより、バースト的な輻輳状態レベルの遷移を平均的なスループットの通知として実現できる。また、状態通知キューを流入規制用の第１の状態通知キューと流入緩和用の第２の状態通知キューとの２種類とし、第１の状態通知キューに存在する輻輳状態レベルの通知を第２の状態通知キューに存在する輻輳状態レベルの通知に優先させるため、規制方向の通知をリアルタイムで実現できる。
【００４１】
（Ｇ）また、以下の第７の手段を提案する。すなわち、バッファ内の滞留パケット量から判定される輻輳状態レベルの遷移が検出されるたび、当該遷移後の輻輳状態レベルをバッファの上流側に通知する輻輳状態通知装置であって、輻輳状態レベルの上方遷移の判定に使用する判定閾値と下方遷移の判定に使用する判定閾値とで異なる値を使用する輻輳状態監視手段を備えると共に、上方遷移した遷移後の輻輳状態レベルを先入れ先出し方式で出力する第１の状態通知キューと、下方遷移した遷移後の輻輳状態レベルを先入れ先出し方式で出力する第２の状態通知キューとを備え、上記第１の状態通知キューと上記第２の状態通知キューがいずれも通知すべき輻輳状態レベルを有する場合、上記第１の状態通知キューに存在する輻輳状態レベルの通知が優先されるものを提案する。
【００４２】
この第７の手段によれば、輻輳状態レベルの遷移頻度を減らせる（すなわち、輻輳状態通知のスループットを低く抑える）ことができるのに加え、バースト的な輻輳状態レベルの遷移を平均的なスループットの通知として実現できる。これにより、技術的なボトルネックの解消をより確実に実現できる。さらに、状態通知キューを流入規制用の第１の状態通知キューと流入緩和用の第２の状態通知キューとの２種類とし、第１の状態通知キューに存在する輻輳状態レベルの通知を第２の状態通知キューに存在する輻輳状態レベルの通知に優先させるため、規制方向の通知をリアルタイムで実現できる。
【００４５】
（Ｈ）また、以下の第８の手段を提案する。すなわち、第６又は第７の手段に、輻輳状態レベルが第１の状態通知キューを介して通知される場合、自身が保持するパケット流入量制御用の輻輳状態レベルを通知された値に更新し、輻輳状態レベルが第２の状態通知キューを介して通知される場合、自身が保持するパケット流入量制御用の輻輳状態レベルよりも通知された値が１段階低い値であり、かつ、遷移方向に応じて値が増減される状態遷移変数と上記パケット流入量制御用の輻輳状態レベルの値が一致するとの条件が満たされるか判定し、条件が満たされるとき上記パケット流入量制御用の輻輳状態レベルを通知された値に更新し、条件が満たされないとき現在の値をそのまま保持する輻輳状態保持手段を更に備えるものを提案する。
【００４６】
この第８の手段によれば、状態遷移変数（例えば、第１の輻輳状態キューから入力があるたび増加され、第２の輻輳状態キューから入力があるたび減少される。）によって輻輳状態レベルの遷移方向が短期的にいずれの方向にあるかを把握し、保持されている輻輳状態レベルを緩和する場合には、所定の条件を満たす場合についてのみこれを許可することにより、大量に発生した輻輳状態レベルの遷移の一部が通知されないような事態が生じたとしても、いずれかの時点でバッファ内の輻輳状態レベルと保持されている輻輳状態レベルとを一致させることができる。
【００４７】
また、バッファ内の輻輳状態レベルよりも保持されている輻輳状態レベルの方が大きい状態での不一致は残り得るが、この場合でもバッファ溢れのような致命的な事態は生じ得ないため状態通知キューを比較的浅く（小さく）することが可能となり、装置全体のコスト低下を実現できる。
【００４８】
（Ｉ）また、以下の第９の手段を提案する。すなわち、第６、第７又は第８の手段に、上記第１の状態通知キューと第２の状態通知キューがいずれも空のとき、定期的に最新の輻輳状態レベルを通知する定期通知手段を更に備えるものを提案する。
【００４９】
この第９の手段によれば、第１及び第２の状態通知キューがいずれも空のときに定期的に最新の輻輳状態レベルが通知されるため、仮に状態通知キューの深さ（大きさ）が十分でなく、大量に発生した輻輳状態レベルの遷移の一部が通知されないような事態が生じたとしても、その後の定期通信によって輻輳状態レベルを早期に最新の状態に一致させることができる。この結果、状態通知キューを比較的浅く（小さく）することが可能となり、装置全体のコスト低下を実現できる。また、定期通知によって必要以上に入力パケットが廃棄される事態を回避することもできるため、装置の性能向上を実現できる。
【００５０】
（Ｊ）また、以下の第１０の手段を提案する。すなわち、第６、第７又は第９の手段に、輻輳状態レベルが第１の状態通知キューを介して通知される場合、自身が保持するパケット流入量制御用の輻輳状態レベルを通知のあった値に更新し、輻輳状態レベルが第２の状態通知キューを介して通知される場合、第１の状態通知キューから最後に通知された輻輳状態レベルに付されていたタイムスタンプよりも通知のあった輻輳状態レベルに付されているタイムスタンプの方が時間的に後であるか否か判定し、時間的に後であるとき上記パケット流入量制御用の輻輳状態レベルを通知のあった値に更新し、その他のとき現在の値をそのまま保持する輻輳状態保持手段を更に備えるものを提案する。
【００５１】
この第１０の手段によれば、状態遷移変数（例えば、第１の輻輳状態キューから入力があるたび増加され、第２の輻輳状態キューから入力があるたび減少される。）によって輻輳状態レベルの遷移方向が短期的にいずれの方向にあるかを把握し、保持されている輻輳状態レベルを緩和する場合には、所定の条件を満たす場合についてのみこれを許可することにより、大量に発生した輻輳状態レベルの遷移の一部が通知されないような事態が生じたとしても、いずれかの時点でバッファ内の輻輳状態レベルと保持されている輻輳状態レベルとを一致させることができる。
【００５２】
また、バッファ内の輻輳状態レベルよりも保持されている輻輳状態レベルの方が大きい状態での不一致は残り得るが、この場合でもバッファ溢れのような致命的な事態は生じ得ないため状態通知キューを比較的浅く（小さく）することが可能となり、装置全体のコスト低下を実現できる。
【００５３】
【発明の実施の形態】
以下、本願発明に係る輻輳状態通知方法及び装置の実施形態を説明する。なお、これら方法及び装置は、図４に示すような全体構成を有するパケット交換装置に適用される。ここで、パケット交換装置とは、パケットの交換機能を備える装置を意味するものとし、交換機やルータだけでなく、端末装置も含み得るものである。また、パケット長は固定長であっても、任意長でも良い。なお、５３バイトの固定長パケット（セル）を扱うものが、ＡＴＭ交換機であり、ＡＴＭルータである。
【００５４】
（Ａ）第１の実施形態（第１の手段と第１０の手段の一例に相当する。）
（Ａ−１）装置構成
図１に、第１の実施形態に係る輻輳状態通知装置の機能ブロック構成を示す。この装置には、バッファ溢れが生じる前に入力パケットを選択的に廃棄する入力パケット廃棄制御部１００（優先度識別部１０１、抑制制御部１０２、抑制判定部１０３、輻輳状態保持部１０４）と、バッファに滞留するパケット量を監視し輻輳状態を通知するバッファ制御部２００（バッファ２０１、輻輳状態監視部２０２）とが設けられている。
【００５５】
このうち、特徴的な構成要素は、輻輳状態監視部２０２と輻輳状態保持部１０４の２つである。輻輳状態監視部２０２は、バッファ２０１の滞留パケット量を監視し、当該パケット量と判定閾値とを比較することで、入力パケット廃棄制御部１００に通知すべき輻輳状態レベルを特定する機能部である。
【００５６】
なお、輻輳状態監視部２０２が用いる判定閾値は遷移方向に応じて異なるものを使用する。すなわち、ヒステリシス特性を有する判定閾値を使用する。この実施形態では、この使用目的から輻輳状態レベルが緩和される方向には遷移が起こり難くするため（実際よりも輻輳状態を高く判定してもバッファ溢れが生じることはないが、その反対の場合にはバッファ溢れが生じる危険性を高める。）、同一レベル間の判定閾値では緩和方向で使用する判定閾値の方に、規制方向で使用する判定閾値よりも低い値（滞留バッファ量がより少ない場合に輻輳状態レベルの遷移が生じる）を使用するものとする。
【００５７】
輻輳状態監視部２０２は、バッファ２０１の輻輳状態レベルの遷移が認められた場合のみ、判定の結果確認された遷移後の輻輳状態レベルを入力パケット廃棄制御部１００（具体的には、輻輳状態保持部１０４）に通知するよう構成されている。
【００５８】
輻輳状態保持部１０４は、輻輳状態レベルの遷移が確認された場合にのみ単発的に通知される輻輳状態レベルを保持して継続的な入力パケット量の抑制制御に使用するための機能部である。一般に、この輻輳状態保持部１０４には半導体メモリが使用されるが、他の構成の記憶手段を除外するものではない。輻輳状態保持部１０４は、新たな輻輳状態レベルが通知されるまで現在値を保持し、保持している値を抑制判定部１０３に与える。すなわち、抑制判定部１０３は、バッファ２０１内の滞留パケット量の実変動値に基づいて流流パケット量の抑制を行うのではなく、ある種の代表値として与えられる輻輳状態レベルに基づいて平均的な抑制制御を実行する。
【００５９】
（Ａ−２）輻輳通知動作
図５に、本実施形態に特有なバッファ輻輳の監視方法を示す。図５は、輻輳状態レベルを３段階（状態（０）、状態（１）、状態（２））で判定する場合の例である。勿論、輻輳状態レベルの段数は適応システムに応じて任意の段数を選択することが可能である。ここでは、状態の数が大きいほど輻輳の程度がひどいものとする。
【００６０】
また、入力パケット廃棄制御部１００に通知された輻輳状態レベルは入力パケットの流入量の抑制（廃棄）に使用されるため、輻輳状態レベルが大きくなる方向を「規制方向」とし、輻輳状態レベルが小さくなる方向を「緩和方向」とする。
【００６１】
輻輳状態監視部２０２は、規制方向用と緩和方向用とで異なる判定閾値を使用する。この例の場合、輻輳状態監視部２０２は、各方向用に２つの判定閾値を有する。図５は、各方向に対応した判定閾値の関係を表している。図５に示すように、状態（２）と状態（１）の判定閾値と、状態（１）と状態（０）の判定閾値のそれぞれにおいて、規制方向用の判定閾値が緩和方向用の判定閾値よりも大きな値に設定されている。すなわち、輻輳状態レベルの遷移にヒステリシス特性が現れるようにしている。
【００６２】
なお、緩和方向用の判定閾値を規制方向用の判定閾値よりも相対的に小さくした結果、下位の輻輳状態レベルには遷移が起こり難くなる。従って、バッファ２０１内の滞留パケット量が多少減少しても輻輳状態レベルは現在のレベルを維持され、優先度の低い入力パケットは廃棄され続けることになる。しかし、このような多少余分な廃棄が生じても、優先度の高い入力パケットは保護される点では本来の目的を果たしており、かつ、バッファ溢れといった致命的な現象が生じないという効果が認められる。
【００６３】
かかる判定閾値を用いた判定結果として輻輳状態レベルの遷移が確認された場合にのみ、輻輳状態監視部２０２は、遷移後の輻輳状態レベルを含む通知データをバッファ上流側の入力パケット廃棄制御部１００に出力する。
【００６４】
通知された輻輳状態レベルは、抑制制御に用いるために必要な情報として輻輳状態保持部１０４に保持される。この輻輳状態保持部１０４に保持される輻輳状態レベルは、バッファ制御部２００から新たな輻輳状態レベルが通知されるまで保持され、通知時に更新される。この保持されている輻輳状態レベルが「抑制レベル」として抑制判定部１０３に逐次読み出され、入力パケットの抑制制御に用いられる。
【００６５】
（Ａ−３）第１の実施形態の効果
以上のように第１の実施形態によれば、輻輳状態レベルの遷移にヒステリシスを持たせたことにより、規制方向と緩和方向とで共通の判定閾値を使用する場合に比して輻輳状態レベルの遷移頻度を一段と低減させることができる。従って、輻輳状態レベルの通知に要するスループットを低く押さえることができる。すなわち、入力パケットのスループットを上げていったとしても（大規模化したとしても）、輻輳状態レベルの通知に技術的な（実装面や速度面で）ボトルネックが生じないようにできる。
【００６６】
（Ｂ）第２の実施形態（第５の手段と第１４の手段の一例に相当する。）
前述のように、第１の実施形態で説明した方法（装置）を採用すれば、入力パケットや出力パケットのスループットの増大にかかわらず、輻輳状態レベルの通知に要するスループットの低減を実現することが可能であるが、ここでは更に輻輳状態レベルの通知に要するスループットを低減させることができる方法（装置）を説明する。
【００６７】
（Ｂ−１）装置構成
図６に、第２の実施形態に係る輻輳状態通知装置の機能ブロック構成を示す。図５は、図１との同一部分に同一符号を付して示す図面であり、状態通知キュー２０３がバッファ制御部２００側に設けられたことを除いて同一の構成を有している。すなわち、輻輳状態監視部２０２から輻輳状態保持部１０４に宛てて送出された輻輳状態レベルは、状態通知キュー２０３を介して出力される点を除き、構成要素は第１の実施形態と同じである。
【００６８】
状態通知キュー２０３は、２つの通知キューで構成されている。１つは、規制方向遷移用の通知キュー２０３Ａであり、１つは、緩和方向遷移用の通知キュー２０３Ｂである。
【００６９】
ここで、規制方向遷移用の通知キュー２０３Ａには、規制方向に遷移が確認された場合の遷移後の輻輳状態レベルを含む通知データがキューイングされる。一方、緩和方向遷移用の通知キュー２０３Ｂには、緩和方向に遷移が確認された場合の遷移後の輻輳状態レベルを含む通知データがキューイングされる。なお、いずれの通知データにも、通知すべき輻輳状態レベル（状態（０）、（１）、（２）のいずれか）と、通知種別（規制方向か緩和方向か）とが含まれる。
【００７０】
状態通知キュー２０３は、規制方向遷移用の通知キュー２０３Ａからの通知データの出力を、緩和方向遷移用の通知キュー２０３Ｂからの通知データの出力に優先させるよう設定されている。規制方向遷移用の通知キュー２０３Ａ及び緩和方向遷移用の通知キュー２０３Ｂのいずれも、先入れ先出し方式のバッファで構成されている。
【００７１】
なお、輻輳状態保持部１０４には、次の規則に基づいて抑制レベルを更新する機能を設けることとする。
【００７２】
１）通知種別が「規制方向」であった場合
抑制レベル←通知データの輻輳状態レベル
ただし、”←”は、右辺の値を左辺に代入（更新）することを意味する（以下同じ）。例えば、抑制レベルが「２」である場合に、通知データとして「規制方向」かつ「輻輳状態レベル３」が通知された場合、抑制レベルを「３」に更新する２）通知種別が「緩和方向」であった場合
▲１▼抑制レベルよりも通知データに含まれている輻輳状態レベルが１段階小さいとき
抑制レベル←通知データの輻輳状態レベル
▲２▼上記以外のとき
抑制レベルの現在値を維持する。例えば、抑制レベルが「３」である場合に、通知データとして「緩和方向」かつ「輻輳状態レベル２」が通知されたときは、抑制レベルを「２」に更新するが、抑制レベルが「３」である場合に、通知データとして「緩和方向」かつ「輻輳状態レベル１」が通知されたときは、抑制レベルを「３」のままとする。
【００７３】
（Ｂ−２）輻輳通知動作
この輻輳状態監視部２０２にも、その輻輳状態の判定特性にヒステリシス特性が設けられている。従って、規制方向と緩和方向で共通の判定閾値を使用する場合に比して輻輳状態レベルの遷移頻度は一段と低減されている。
【００７４】
この実施形態の場合も、輻輳状態監視部２０２は、バッファ２０１の滞留パケット量から輻輳状態レベルの遷移が確認された場合のみ、通知種別と輻輳状態レベルを含む通知データの出力を行う。
【００７５】
ただし、本実施形態の場合には状態通知キュー２０３を経由して輻輳状態保持部１０４（バッファ上流側の入力パケット廃棄規制部１００）に通知する形態を採用しているので、輻輳状態監視部２０２から出力された輻輳状態レベルは状態通知キュー２０３内の対応する通知キューに入力される。
【００７６】
すなわち、通知種別が規制方向である通知データは、状態通知キュー２０３内の規制方向遷移用の通知キュー２０３Ａに、通知種別が緩和方向である通知データは、状態通知キュー２０３内の緩和方向遷移用の通知キュー２０３Ｂに振り分けられて入力される。このように、振り分けは通知種別にのみ依存する。
【００７７】
このため、バッファ内の滞留パケット量が頻繁に増減する状態では、規制方向遷移用の通知キュー２０３Ａにも、緩和方向遷移用の通知キュー２０３Ｂにも通知データがある状態が生じ得る。ただし、この場合には、規制方向遷移用の通知キュー２０３Ａ内にある全ての通知データが送出されるまで、緩和方向遷移用の通知キュー２０３Ｂ内にある通知データの出力は待たされる。
【００７８】
一方、このような規則に従った通知データの通知を受ける輻輳状態保持部１０４は、通知データに含まれている輻輳状態レベルを取り出し、その通知種別と輻輳状態レベルの内容に従って、自身の保持する輻輳状態レベルの更新動作を制御する。保持されている輻輳状態レベルは、「抑制レベル」として抑制判定部１０３に通知される。
【００７９】
続いて、より具体例により、輻輳状態レベルの通知動作を説明する。一般に、入力パケット廃棄制御部１００における制御は、滞留パケット量が規制方向に遷移する際にはリアルタイム性が求められるのに対し、緩和方向に遷移する際にはリアルタイム性がそれほど要求されない。この特性に適応することを説明する。
【００８０】
＜具体例１＞
１）輻輳状態監視部２０２における判定の結果、バッファ２０１の輻輳状態レベルが次のように遷移した場合を考える
０→１→２→１→０
２）このとき、状態通知キュー２０３には、それぞれ次のように輻輳状態レベルがキューイングされる
規制方向遷移用の通知キュー２０３Ａ：１、２
緩和方向遷移用の通知キュー２０３Ｂ：１、０
ただし、右辺は、左側から順番にキューイングされた状態を示している
３）状態通知キュー２０３は、規制方向遷移用の通知キュー２０３Ａ内の通知データを優先的に通知するため、通知データの内容は次のようになる
▲１▼「規制方向」かつ「１」
→▲２▼「規制方向」かつ「２」
→▲３▼「緩和方向」かつ「１」
→▲４▼「緩和方向」かつ「０」
４）この結果、輻輳状態保持部１０４が保持する抑制レベルは、上記規則に従って次のように変化する
０→１→２→１→０
この場合、抑制レベルの遷移は、輻輳状態レベルの遷移の順番と一致する。
【００８１】
＜具体例２＞
１）輻輳状態監視部２０２における判定の結果、バッファ２０１の輻輳状態レベルが次のように遷移した場合を考える
０→１→０→１→２
２）状態通知キュー２０３には、それぞれ次のように輻輳状態レベルがキューイングされる
規制方向遷移用の通知キュー２０３Ａ：１、１、２
緩和方向遷移用の通知キュー２０３Ｂ：０
ただし、右辺は、左側から順番にキューイングされた状態を示している
３）状態通知キュー２０３は、規制方向遷移用の通知キュー２０３Ａ内の通知データを優先的に通知するため、通知データの内容は次のようになる
▲１▼「規制方向」かつ「１」
→▲２▼「規制方向」かつ「１」
→▲３▼「規制方向」かつ「２」
→▲４▼「緩和方向」かつ「０」
４）この結果、輻輳状態保持部１０４が保持する抑制レベルは、上記規則に従って次のように変化する。
【００８２】
０→１→１→２→２
抑制レベルがこのように与えられるのは、▲４▼の通知データが「緩和方向」であり、かつ、現在の抑制レベルが「２」であるときに、当該値よりも２段階小さい「０」が通知されたため、更新動作が実行されず通知が無視されたためである。なお、最終的に得られた抑制レベルは、発生した輻輳状態レベルの値と一致している。
【００８３】
（Ｂ−３）第２の実施形態の効果
以上のように第２の実施形態によれば、第１の実施形態の構成に加えて状態通知キュー２０３を設けたことにより、バースト的な輻輳状態レベルの遷移の発生を平均的な通知データヘとすることができる。従って、輻輳状態通知に要するスループットの最大値を低く押さえることが可能となる。
【００８４】
また、この状態通知キュー２０３のようにその通知キューを「規制方向遷移用」と「緩和方向遷移用」との２種類で構成し、規制方向遷移用の通知キュー２０３Ａに存在する通知データの通知を緩和方向遷移用の通知キュー２０３Ｂの通知に優先させるようにしたことにより、規制方向への遷移に対してはリアルタイム性を損なうことなく通知することが可能となる。
【００８５】
この結果、第１の実施形態に比べて性能を低減させることなく、より入力パケットのスループットの増大に対しても、輻輳状態通知に要するスループットを低く押さえることを可能とできる。かくして、入力パケットのスループットを上げていったとしても（大規模化したとしても）、輻輳状態レベルの通知に技術的な（実装面や速度面で）ボトルネックが一層生じないようにできる。
【００８６】
（Ｃ）第３の実施形態（第７の手段と第１６の手段の一例に相当する。）
前述のように、第２の実施形態で説明した方法（装置）を採用すれば、輻輳状態レベルの通知に要するスループットを平均的なものとして低減させることが可能であるが、入力パケットのスループットの変動が激しい場合には、以下に示すようにバッファ２０１内で生じている実際の輻輳状態レベルと制御に使用される抑制レベルとの間に不一致が起きる可能性がある。
【００８７】
ただし、不一致が生じても、バッファの輻輳状態レベルが抑制レベルよりも小さい場合には、入力パケット廃棄制御部１００で廃棄されるパケットが多くなるだけで、バッファ溢れのような致命的な問題は生じない。
【００８８】
しかし、バッファの輻輳状態レベルが抑制レベルよりも大きい場合には、バッファ溢れが発生する可能性があり、仮にバッファ溢れが発生してしまうと、入力パケットが無秩序に廃棄される結果、致命的な問題が生じてしまう。
【００８９】
以下に輻輳状態レベルと抑制レベルとの間に状態の不一致が生じる場合の例を示す。
【００９０】
１）輻輳状態監視部２０２における判定の結果、バッファ２０１の輻輳状態レベルが次のように遷移した場合を考える
０→１→２→１→０→１→２
２）状態通知キュー２０３には、それぞれ次のように輻輳状態レベルがキューイングされる
規制方向遷移用の通知キュー２０３Ａ：１、２、１、２
緩和方向遷移用の通知キュー２０３Ｂ：１、０
ただし、右辺は、左側から順番にキューイングされた状態を示している
３）状態通知キュー２０３は、規制方向遷移用の通知キュー２０３Ａ内の通知データを優先して通知するため、通知データの内容は次のようになる
▲１▼「規制方向」かつ「１」
→▲２▼「規制方向」かつ「２」
→▲３▼「規制方向」かつ「１」
→▲４▼「規制方向」かつ「２」
→▲５▼「緩和方向」かつ「１」
→▲６▼「緩和方向」かつ「０」
４）この結果、輻輳状態保持部１０４が保持する抑制レベルは、第２の実施形態に示す規則に従って次のように変化する。
【００９１】
０→１→２→１→２→１→０
すなわち、最終的に得られる抑制レベルとして「０」が得られる。ところが、バッファ２０１内の実際の輻輳状態レベルは「２」であり、輻輳状態レベルの遷移態様によっては不一致が生じる可能性がある。
【００９２】
（Ｃ−１）装置構成
そこで、第３の実施形態では、以下の装置構成を採用する。図７に、第３の実施形態に係る輻輳状態通知装置の機能ブロック構成を示す。図７は、図６との同一部分に同一符号を付して示す図面であり、輻輳状態保持部１０４に状態遷移変数更新／保持機能部１０４Ａが設けられている点を除いて同一の構成を有している。
【００９３】
この輻輳状態保持部１０４は、「抑制レベル」の更新を、「通知種別」と「輻輳状態レベルと抑制レベルの関係」だけでなく、「状態遷移変数」を加味して実行することで、前述のような抑制レベルとバッファ内の輻輳状態レベルとの不一致が生じないようにする。
【００９４】
状態遷移変数更新／保持機能部１０４Ａは、状態遷移変数の更新と保持を実行する手段である。状態遷移変数は、抑制レベル数（今までの例では３段階）よりも大きい値を保持できるようにしておく。例を挙げると抑制レベルが３段階存在し得る場合、状態遷移変数は４段階以上存在し得るものとする。
【００９５】
状態遷移変数更新／保持機能部１０４Ａは、次に示す規則に従って「状態遷移変数」の更新と保持を実行する。
【００９６】
１）通知種別が「規制方向」であった場合
通知データに含まれる輻輳状態レベルの値に関係なく１段階大きいレベルに更新する
２）通知種別が「緩和方向」であった場合
通知データに含まれる輻輳状態レベルの値に関係なく１段階小さいレベルに更新する。
【００９７】
輻輳状態保持部１０４は、この状態遷移変数更新／保持機能部１０４Ａで管理される状態遷移変数を利用し、以下の規則に従って抑制レベルの更新を実行する。
【００９８】
１）通知種別が「規制方向」であった場合
抑制レベル←通知データの輻輳状態レベル
この更新動作は、第２の実施形態の場合と同じである
２）通知種別が「緩和方向」であった場合
▲１▼抑制レベルよりも通知データに含まれている輻輳状態レベルが１段階小さく、かつ、抑制レベルと状態遷移変数の値が同一のとき
抑制レベル←通知データに含まれる輻輳状態レベル
▲２▼上記以外のとき
抑制レベルの現在値を維持する。この動作の内容が第２の実施形態と異なる。
【００９９】
（Ｃ−２）輻輳通知動作
この実施形態の輻輳通知動作は、輻輳状態保持部１０４の動作を除き、第２の実施形態と同じ動作となる。従って、輻輳状態監視部２０２における輻輳状態レベルの遷移にヒステリシス特性が現れること、状態通知キュー２０３によって規制方向への輻輳状態レベルの通知が優先的に行われる（リアルタイムに行われる。）ことについての説明は省略する。
【０１００】
以下、冒頭で説明した事態が、この実施形態に係る方法（装置）を適用することにより生じ得ないことを説明する。
【０１０１】
＜具体例＞
１）輻輳状態監視部２０２における判定の結果、バッファ２０１の輻輳状態レベルが次のように遷移した場合を考える
０→１→２→１→０→１→２
２）このとき、状態通知キュー２０３には、それぞれ次のように輻輳状態レベルがキューイングされる
規制方向遷移用の通知キュー２０３Ａ：１、２、１、２
緩和方向遷移用の通知キュー２０３Ｂ：１、０
ただし、右辺は、左側から順番にキューイングされた状態を示している
３）状態通知キュー２０３は、規制方向遷移用の通知キュー２０３Ａ内の通知データを優先的に通知するため、通知データの内容は次のようになる
▲１▼「規制方向」かつ「１」
→▲２▼「規制方向」かつ「２」
→▲３▼「規制方向」かつ「１」
→▲４▼「規制方向」かつ「２」
→▲５▼「緩和方向」かつ「１」
→▲６▼「緩和方向」かつ「０」
４）この結果、輻輳状態保持部１０４が保持する抑制レベルは、前述の規則に従って次のように変化する。またこのとき、状態遷移変数は次のように変化する
［状態遷移変数が５段階（０、１、２、３、４）の場合］
状態遷移変数：０→１→２→３→４→３→２
抑制レベル  ：０→１→２→１→２→２→２
ここで、緩和方向の通知は、抑制レベルと状態遷移変数の値が異なるために無視されている
［状態遷移変数が４段階（０、１、２、３）の場合］
状態遷移変数：０→１→２→３→３→２→２
抑制レベル  ：０→１→２→１→２→２→２
ここで、最後の緩和方向の通知は、抑制レベルと通知された輻輳状態レベルの関係が
条件に合わないために無視されている
以上のように、「状態遷移変数」を用いた結果、輻輳状態レベルの通知に要するスループットを増大させることなく、バッファの輻輳状態レベルと抑制レベルを一致させることが可能となった。
【０１０２】
（Ｃ−３）第３の実施形態の効果
以上のように第３の実施形態によれば、第２の実施形態と同様の効果に加え、入力パケットのスループットの変動が激しい場合でも、輻輳状態レベルの通知が一段落した時点で、抑制レベルが輻輳状態レベルよりも大きくなる事態を有効に回避できる。
【０１０３】
かかる結果は、緩和方向遷移用の通知キュー２０３Ｂに求められる容量を比較的小規模なものとしても可能なため、装置コストの低減を実現できる。
【０１０４】
（Ｄ）第４の実施形態（第８の手段と第１７の手段の一例に相当する。）
前述のように、第２の実施形態で説明した方法（装置）を採用すれば、輻輳状態レベルの通知に要するスループットを平均的なものとして低減させることが可能であるが、入力パケットのスループットの変動が大きい場合には、状態通知キュー２０３の深さ（大きさ）も比較的深くする必要がある。
【０１０５】
理由は、入力パケットのスループットの変動が大きいということは、通知データの頻度が増大することと等価なため、増大した通知データを溢れることなくキューイングすることが可能な状態通知キューが必要になることによる。
【０１０６】
従って、状態通知キュー２０３の深さ（大きさ）が通知データの発生量に比して十分でないと、通知データの廃棄が発生して過度の抑制制御が継続される可能性が生じてしまう。かかる事態を、第２の実施形態の動作説明で用いた＜具体例１＞の場合を例に説明する。
【０１０７】
１）輻輳状態監視部２０２における判定の結果、バッファ２０１の輻輳状態レベルが次のように遷移した場合を考える
０→１→２→１→０
２）このとき、状態通知キュー２０３の容量が十分であれば、それぞれ次のように輻輳状態レベルがキューイングされる
規制方向遷移用の通知キュー２０３Ａ：１、２
緩和方向遷移用の通知キュー２０３Ｂ：１、０
ただし、右辺は、左側から順番にキューイングされた状態を示している
しかしながら、規制方向遷移用の通知キュー２０３Ａは優先的に通知が行われるため容量の不足が問題になることはまず生じ得ないが、緩和方向遷移用の通知キュー２０３Ｂでは通知待ちの間に通知キュー２０３Ｂの深さが不足して「２→１」の遷移に対するキューイングがなされないことが生じ得、その場合には次のようなことが生じる
規制方向遷移用の通知キュー２０３Ａ：１、２
緩和方向遷移用の通知キュー２０３Ｂ：０
３）状態通知キュー２０３は、規制方向遷移用の通知キュー２０３Ａ内の通知データを優先的に通知するため、通知データの内容は次のようになる
▲１▼「規制方向」かつ「１」
→▲２▼「規制方向」かつ「２」
→▲３▼「緩和方向」かつ「０」
４）この結果、輻輳状態保持部１０４が保持する抑制レベルは、第２の実施形態に示す規則に従って次のように変化する
０→１→２→２
なお、最後の緩和方向の通知は、抑制レベルと通知された輻輳状態レベルの関係が条件に合わないために無視されている
この時点で、バッファ２０１の輻輳状態レベル「０」に対して、抑制レベルは「２」となる。以降、規制方向の通知がされればレベルの不一致は解消されるがそれまでは必要以上に入力パケットの廃棄が行われることになり、性能を十分に発揮することができない。
【０１０８】
（Ｄ−１）装置構成
そこで、第４の実施形態では、状態通知キューが比較的浅く（小さく）ても、「性能を十分に出すことができない」時間を可能な限り少なくするために以下の装置構成を採用する。図８に、第４の実施形態に係る輻輳状態通知装置の機能ブロック構成を示す。図８は、図６との同一部分に同一符号を付して示す図面であり、定期通知挿入部２０４が設けられている点を除いて同一の構成を有している。
【０１０９】
定期通知挿入部２０４は、バッファ２０４の輻輳状態レベル（輻輳状態監視部２０２で判定されるレベルと同一）を状態通知キュー２０３に常時伝達するため手段である。ここで、輻輳状態レベルは、定期通知挿入部２０４自身が、輻輳状態監視部２０２と全く同じ手法で求めることとしても良いし、輻輳状態監視部２０２の判定結果を利用しても良い。
【０１１０】
この定期通知挿入部２０４を設けたことに伴い、状態通知キュー２０３に以下の機能を追加した。状態通知キュー２０３は、前述のように規制方向遷移用の通知キュー２０３Ａと緩和方向遷移用の通知キュー２０３Ｂの両方に通知データが存在する場合には規制方向遷移用の通知キュー２０３Ａを優先し、いずれか一方しか通知データが存在しない場合には存在する通知データを先入れ先出し方式で通知しているが、どちらも空になったことが確認された場合には、定期通知挿入部２０４から伝達されている最新の輻輳状態レベルを通知データとして輻輳状態保持部１０４に通知する機能を新たに付加することにする。
【０１１１】
なお、このように第４の実施形態では「規制方向」とも「緩和方向」とも異なる通知データが発生するため、その通知種別は、「定期」、「規制方向」、「緩和方向」の３種類となる。
【０１１２】
また、通知種別が「定期」の通知データは、規制方向遷移用の通知キュー２０３Ａと緩和方向遷移用の通知キュー２０３Ｂが共に空であると判定されている間、定期的に送信される。定期的とは、必ずしも常に一定間隔を意味するものでなく、送信と送信との間が不規則である場合も含む。
【０１１３】
一方、通知データの受け手となる輻輳状態保持部１０４であるが、この実施形態の場合、通知種別が「定期」の通知データが通知された場合には、その輻輳状態レベルで抑制レベルを強制的に更新する機能を備えている。
【０１１４】
（Ｄ−２）輻輳通知動作
この実施形態の輻輳通知動作は、状態通知キュー２０３と定期通知挿入部２０４の動作を除き、第２の実施形態と同じ動作となる。従って、輻輳状態監視部２０２における輻輳状態レベルの遷移にヒステリシス特性が現れること、状態通知キュー２０３によって規制方向への輻輳状態レベルの通知が優先的に行われる（リアルタイムに行われる。）ことについての説明は省略する。
【０１１５】
違いは、冒頭の４）で説明したように、輻輳状態保持部１０４に保持される抑制データが一連の通知データの通知完了後に「２」になった後も、輻輳状態レベルの変化が認められない状態が一定時間以上継続した場合には輻輳状態レベルの変化を待つことなく、通知種別が「定期」の通知データが状態通知キュー２０３から送信される点である。
【０１１６】
前述のように、「定期」の通知データにはバッファ２０１の最新の輻輳状態レベルが含まれており、この例の場合には「０」である。従って、この通知データによって、輻輳状態保持部１０４が保持する抑制レベルは「０」に更新され、抑制レベルとバッファ内の輻輳状態レベルとの一致が実現される。
【０１１７】
（Ｄ−３）第４の実施形態の効果
以上のように第４の実施例によれば、第２の実施形態と同様の効果に加え、仮に緩和方向での通知データの通知に廃棄が生じて輻輳状態レベルの通知が一段落した時点で抑制レベルとバッファ内の輻輳状態レベルとの間に不一致が生じるとしても、最悪でも最後の通信データの通知があってから（規制方向遷移用の通知キュー２０３Ａ及び緩和方向遷移用の通知キュー２０３Ｂの両方が空になってから）一定時間内に抑制レベルとバッファ内の輻輳状態レベルとを一致させることができる。
【０１１８】
このため、状態通知キューを比較的浅く（小さく）することが可能となり、装置全体のコスト低減を実現できる。
【０１１９】
また、定期通知（通知種別が「定期」の通知）によって、必要以上に入力パケットが廃棄される状態が有効に回避されるため、装置全体の性能を向上させることが可能となる。
【０１２０】
（Ｅ）第５の実施形態（第８の手段と第１７の手段の一例に相当する。）
前述のように、第３の実施形態で説明した方法（装置）を採用すれば、輻輳状態レベルの通知に要するスループットを平均的なものとして低減させることが可能であるが、入力パケットのスループットの変動が大きい場合には、状態通知キュー２０３の深さ（大きさ）も比較的深くする必要があった。
【０１２１】
理由は、入力パケットのスループットの変動が大きいということは、通知データの頻度が増大することと等価なため、増大した通知データを溢れることなくキューイングすることが可能な状態通知キューが必要になることによる。
【０１２２】
従って、状態通知キュー２０３の深さ（大きさ）が通知データの発生量に比して十分でないと、通知データの廃棄が発生して過度の抑制制御が継続される可能性が生じてしまう。かかる事態を、第３の実施形態の動作説明で用いた＜具体例＞の場合を例に説明する。
【０１２３】
１）輻輳状態監視部２０２における判定の結果、バッファ２０１の輻輳状態レベルが次のように遷移した場合を考える
０→１→２→１→０
２）このとき、状態通知キュー２０３の容量が十分であれば、それぞれ次のように輻輳状態レベルがキューイングされる
規制方向遷移用の通知キュー２０３Ａ：１、２
緩和方向遷移用の通知キュー２０３Ｂ：１、０
ただし、右辺は、左側から順番にキューイングされた状態を示している
しかしながら、規制方向遷移用の通知キュー２０３Ａは優先的に通知が行われるため容量の不足が問題になることはまず生じ得ないが、緩和方向遷移用の通知キュー２０３Ｂでは通知待ちの間に通知キュー２０３Ｂの深さが不足して「２→１」の遷移に対するキューイングがなされないことが生じ得、その場合には次のようなことが生じる
規制方向遷移用の通知キュー２０３Ａ：１、２
緩和方向遷移用の通知キュー２０３Ｂ：０
３）状態通知キュー２０３は、規制方向遷移用の通知キュー２０３Ａ内の通知データを優先的に通知するため、通知データの内容は次のようになる
▲１▼「規制方向」かつ「１」
→▲２▼「規制方向」かつ「２」
→▲３▼「緩和方向」かつ「０」
４）この結果、輻輳状態保持部１０４が保持する抑制レベルは、第２の実施形態に示す規則に従って次のように変化する。ここでは、状態遷移変数の変化も同時に示す
［状態遷移変数が５段階（０、１、２、３、４）の場合］
状態遷移変数：０→１→２→１
抑制レベル  ：０→１→２→２
なお、最後の緩和方向の通知は、抑制レベルと通知された輻輳状態レベルの関係が条件に合わないために無視されている
この時点で、バッファ２０１の輻輳状態レベル「０」に対して、抑制レベルは「２」となる。以降、規制方向の通知がされればレベルの不一致は解消されるがそれまでは必要以上に入力パケットの廃棄が行われることになり、性能を十分に発揮することができない。
【０１２４】
（Ｅ−１）装置構成
そこで、第５の実施形態では、状態通知キューが比較的浅く（小さく）ても、「性能を十分に出すことができない」時間を可能な限り少なくするために以下の装置構成を採用する。図９に、第５の実施形態に係る輻輳状態通知装置の機能ブロック構成を示す。図８は、図７との同一部分に同一符号を付して示す図面であり、定期通知挿入部２０４が設けられている点を除いて同一の構成を有している。この第５の実施形態と第３の実施形態との関係は、前述の第４の実施形態と第２の実施形態の関係と同じである。
【０１２５】
定期通知挿入部２０４は、バッファ２０１の輻輳状態レベル（輻輳状態監視部２０２で判定されるレベルと同一）を状態通知キュー２０３に常時伝達するため手段である。ここで、輻輳状態レベルは、定期通知挿入部２０４自身が、輻輳状態監視部２０２と全く同じ手法で求めることとしても良いし、輻輳状態監視部２０２の判定結果を利用しても良い。
【０１２６】
この定期通知挿入部２０４を設けたことに伴い、状態通知キュー２０３に以下の機能を追加した。状態通知キュー２０３は、前述のように規制方向遷移用の通知キュー２０３Ａと緩和方向遷移用の通知キュー２０３Ｂの両方に通知データが存在する場合には規制方向遷移用の通知キュー２０３Ａを優先し、いずれか一方しか通知データが存在しない場合には存在する通知データを先入れ先出し方式で通知しているが、どちらも空になったことが確認された場合には、定期通知挿入部２０４から伝達されている最新の輻輳状態レベルを通知データとして輻輳状態保持部１０４に通知する機能を新たに付加することにする。
【０１２７】
なお、このように第４の実施形態では「規制方向」とも「緩和方向」とも異なる通知データが発生するため、その通知種別は、「定期」、「規制方向」、「緩和方向」の３種類となる。
【０１２８】
また、通知種別が「定期」の通知データは、規制方向遷移用の通知キュー２０３Ａと緩和方向遷移用の通知キュー２０３Ｂが共に空であると判定されている間、定期的に送信される。定期的とは、必ずしも常に一定間隔を意味するものでなく、送信と送信との間が不規則である場合も含む（以下同じ）。
【０１２９】
一方、通知データの受け手となる輻輳状態保持部１０４であるが、この実施形態の場合、通知種別が「定期」の通知データが通知された場合には、その輻輳状態レベルで抑制レベルを強制的に更新する機能を備えている。
【０１３０】
（Ｅ−２）輻輳通知動作
この実施形態の輻輳通知動作は、状態通知キュー２０３と定期通知挿入部２０４の動作を除き、第３の実施形態と同じ動作となる。従って、輻輳状態監視部２０２における輻輳状態レベルの遷移にヒステリシス特性が現れること、状態通知キュー２０３によって規制方向への輻輳状態レベルの通知が優先的に行われる（リアルタイムに行われる。）こと、状態遷移変数によって抑制レベルが輻輳状態レベルよりも大きくなる事態が有効に回避されることについての説明は省略する。
【０１３１】
違いは、冒頭の４）で説明したように、輻輳状態保持部１０４に保持される抑制データが一連の通知データの通知完了後に「２」になった後も（状態遷移変数の存在によって抑制データがバッファの輻輳データよりも小さくならないことは保証されているが）、輻輳状態レベルの変化が認められない状態が一定時間以上継続した場合には輻輳状態レベルの変化を待つことなく、通知種別が「定期」の通知データが状態通知キュー２０３から送信される点である。
【０１３２】
前述のように、「定期」の通知データにはバッファ２０１の最新の輻輳状態レベルが含まれており、この例の場合には「０」である。従って、この通知データによって、輻輳状態保持部１０４が保持する抑制レベルは「０」に更新され、抑制レベルとバッファ内の輻輳状態レベルとの一致が実現される。
【０１３３】
（Ｅ−３）第５の実施形態の効果
以上のように第５の実施例によれば、第３の実施形態と同様の効果に加え、仮に緩和方向での通知データの通知に廃棄が生じて輻輳状態レベルの通知が一段落した時点で抑制レベルとバッファ内の輻輳状態レベルとの間に不一致が生じるとしても、最悪でも最後の通信データの通知があってから（規制方向遷移用の通知キュー２０３Ａ及び緩和方向遷移用の通知キュー２０３Ｂの両方が空になってから）一定時間内に抑制レベルとバッファ内の輻輳状態レベルとを一致させることができる。
【０１３４】
このため、状態通知キューを比較的浅く（小さく）することが可能となり、装置全体のコスト低減を実現できる。
【０１３５】
また、定期通知（通知種別が「定期」の通知）によって、必要以上に入力パケットが廃棄される状態が有効に回避されるため、装置全体の性能を向上させることが可能となる。
【０１３６】
（Ｆ）第６の実施形態（第６の手段と第１５の手段の一例に相当する。）
前述のように、第１の実施形態で説明した方法（装置）を採用すれば、輻輳状態レベルの通知に要するスループットを平均的なものとして低減させることが可能であるが、ここでは更に輻輳状態レベルの通知に要するスループットを低減させることができる方法（装置）を説明する。
【０１３７】
（Ｆ−１）装置構成
図１０に、第６の実施形態に係る輻輳状態通知装置の機能ブロック構成を示す。図１０は、図１との同一部分に同一符号を付して示す図面であり、状態通知キュー２０３と定期通知挿入部２０４がバッファ制御部２００側に設けられたことを除いて同一の構成を有している。なおこの構成は、外間上、前述の第４の実施形態と同種の構成となるが、状態通知キュー２０３内に規制方向遷移用の通知キュー２０３のみしか設けられていない点で異なる。また、通知データに通知種別を付す必要が無い点でも異なっている。
【０１３８】
このため、状態通知キュー２０３は、輻輳状態監視部２０２から規制方向の輻輳状態レベルが入力された場合にはこれを通知キュー２０３Ａに入力し、先入れ先出し方式にて出力するが、緩和方向の輻輳状態レベルが入力された場合にはそのまま廃棄する。例えば、輻輳状態監視部２０２における判定の結果、バッファ２０１の輻輳状態レベルが、０→１→２→１→０と遷移したとすると、この状態通知キュー２０３は、その通知キュー２０３Ａに「１」、「２」のみを順番にキューイングする。
【０１３９】
また、状態通知キュー２０３は、規制方向遷移用の通知キュー２０３Ａ内に通知すべき通知データが存在しない（すなわち、空である）と判定した場合、定期通知挿入部２０４から常時入力されている最新の輻輳状態レベルを定期的に送信する。なおこの場合も、定期的とは、必ずしも常に一定間隔を意味するものでなく、送信と送信との間が不規則である場合も含む。
【０１４０】
なお、定期通知挿入部２０４は、バッファ２０１の輻輳状態レベル（輻輳状態監視部２０２で判定されるレベルと同一）を状態通知キュー２０３に常時伝達するため手段である。ここで、輻輳状態レベルは、定期通知挿入部２０４自身が、輻輳状態監視部２０２と全く同じ手法で求めることとしても良いし、輻輳状態監視部２０２の判定結果を利用しても良い。
【０１４１】
（Ｆ−２）輻輳通知動作
この輻輳状態監視部２０２にも、その輻輳状態の判定特性にヒステリシス特性が設けられている点については、第１の実施形態と同じである。従って、輻輳状態監視部２０２からは、バッファ２０１の滞留パケット量から輻輳状態レベルの遷移が確認された場合にのみ、通知種別と輻輳状態レベルを含む通知データが出力される。以下、具体例により説明する。
【０１４２】
１）輻輳状態監視部２０２における判定の結果、バッファ２０１の輻輳状態レベルが次のように遷移した場合を考える
０→１→２→１→０
２）このとき、状態通知キュー２０３は、次のように規制方向の輻輳状態レベルのみを選択的にキューイングする
規制方向遷移用の通知キュー２０３Ａ：１、２
ただし、右辺は、左側から順番にキューイングされた状態を示している
３）状態通知キュー２０３は、規制方向遷移用の通知キュー２０３Ａ内の通知データを先入れ先出し方式で出力する
１→２
４）この結果、輻輳状態保持部１０４が保持する抑制レベルは、次のようになる０→１→２
ただし、このままでは前述の他の実施形態でも説明したように、抑制レベルとバッファの輻輳状態レベル（０）との不一致が生じ、次の規制方向への輻輳状態レベルの遷移が確認されて通知されるまでの間、必要以上に入力パケットが廃棄され得る。
【０１４３】
しかしながら、前述のように、状態通知キュー２０３は、自身の通知キュー２０３Ａが空になってからしばらくの間、規制方向の輻輳状態レベルの入力が無かった場合には、定期通知挿入部２０４から与えられている最新の輻輳状態レベルを通知するため、一定時間後における抑制レベルは「０」に変更される。従って、抑制レベルとバッファ内の輻輳状態レベルの一致も可能とできる。
【０１４４】
（Ｆ−３）第６の実施形態の効果
以上のように第６の実施形態によれば、第１の実施形態の構成に加えて状態通知キュー２０３を設けたことにより、バースト的な輻輳状態レベルの遷移の発生を平均的な通知データヘとすることができる。従って、輻輳状態通知に要するスループットの最大値を低く押さえることが可能となる。
【０１４５】
また、この第６の実施形態によれば、比較的入力パケットのスループットの変動がそれほど高くない場合には第２〜第５の実施形態のよう状態通知キューに通知キューを２つ設ける必要が無いため、その分、装置コストの低減を可能とできる。
【０１４６】
また、状態通知キューが空の期間に輻輳状態レベルを定期的に通知する構成を採用しているため、必要以上に入力パケットが廃棄される時間は最小化されている。
【０１４７】
（Ｇ）第７の実施形態（第９の手段と第１８の手段の一例に相当する。）
前述のように、第２の実施形態で説明した方法（装置）を採用すれば、輻輳状態レベルの通知に要するスループットを平均的なものとして低減させることが可能であるが、入力パケットのスループットの変動が激しい場合には、以下に示すようにバッファ２０１内で生じている実際の輻輳状態レベルと制御に使用される抑制レベルとの間に不一致が起きる可能性がある。
【０１４８】
（Ｇ−１）装置構成
そこで、第７の実施形態では、以下の装置構成を採用する。図１１に、第７の実施形態に係る輻輳状態通知装置の機能ブロック構成を示す。図１１は、図６との同一部分に同一符号を付して示す図面であり、輻輳状態保持部１０４にタイムスタンプ監視機能部１０４Ｂが設けられている点を除いて同一の構成を有している。
【０１４９】
この輻輳状態保持部１０４は、「抑制レベル」の更新を、「通知種別」だけでなく、「タイムスタンプ」を加味して実行することで、前述のような抑制レベルとバッファ内の輻輳状態レベルとの不一致が生じないようにする。
【０１５０】
タイムスタンプ監視機能部１０４Ｂは、通知データに含まれた形態で逐次通知されるタイムスタンプと保持されている抑制レベルに付されていたタイムスタンプとの関係を監視する手段である。このタイムスタンプ監視機能部１０４Ｂは、通知データの通知種別が「緩和方向」である場合に機能する。
【０１５１】
タイムスタンプ監視機能部１０４Ｂは、規制方向遷移用の通知キュー２０３Ａから最後に通知された通知データに付されていたタイムスタンプ値よりも緩和方向遷移用の通知キュー２０３Ｂから通知のあった通知データに付されているタイムスタンプ値の方が時間的に後であるか否か判定し、時間的に後である場合に限り、通知データの輻輳状態レベルによる抑制レベルの更新を許可する。
【０１５２】
すなわち、輻輳状態保持部１０４は、通知種別が「緩和方向」であった場合に、通知データに付されていたタイムスタンプ値が、通知種別が「規制方向」である通知データの中で最後に通知された通知データのタイムスタンプ値よりも時間的に前であった場合には、現在保持している抑制レベルをそのまま保持し、抑制レベルの更新を禁止する。
【０１５３】
一方、輻輳状態保持部１０４は、通知種別が「規制方向」であった場合には、通知データに付されているタイムスタンプ値で抑制レベルを更新する。
【０１５４】
なおここでのタイムスタンプは、輻輳状態監視部２０２において輻輳状態レベルの遷移が確認された時点の時刻情報である。また、タイムスタンプには、タイムスタンプの値が１巡して重複することがないように十分な大きさのものが使用される。
【０１５５】
因みに、この実施形態における通知データには、「通知種別」、「輻輳状態レベル」、「タイムスタンプ」の３つの情報が含まれる。
【０１５６】
（Ｇ−２）輻輳通知動作
この輻輳状態監視部２０２も、その輻輳状態の判定特性にヒステリシス特性が設けられている。そして、バッファ２０１の滞留パケット量から輻輳状態レベルの遷移が確認された場合のみ、通知種別と輻輳状態レベルを含む通知データが出力される。ただし、その通知データには、遷移が確認された時刻情報であるタイムスタンプ値と、遷移方向を示す通知種別が付される。ここでは、次の場合を考える。
【０１５７】
＜具体例＞
１）輻輳状態監視部２０２における判定の結果、バッファ２０１の輻輳状態レベルが次のように遷移した場合を考える
0003563016.tif 000002
ただし、タイムスタンプ値の桁数は一例である
２）状態通知キュー２０３には、それぞれ次のように輻輳状態レベルがキューイングされる
規制方向遷移用の通知キュー２０３Ａ：１、１、２
緩和方向遷移用の通知キュー２０３Ｂ：０
ただし、右辺は、左側から順番にキューイングされた状態を示している
３）状態通知キュー２０３は、規制方向遷移用の通知キュー２０３Ａ内の通知データを優先的に通知するため、通知データの内容は次のようになる
0003563016.tif 000003
４）この結果、輻輳状態保持部１０４が保持する抑制レベルは、上記規則に従って次のように変化する。
【０１５８】
０→１→１→２→２
抑制レベルがこのように与えられるのは、「緩和方向」の通知データである▲４▼の通知データに付されているタイムスタンプ値「０００３２」が、「規制方向」の最後に通知された通知データに付されていたタイムスタンプ値「０００５７」よりも小さい（時間的に前である）ため、更新動作が実行されず通知が無視されたためである。なお、最終的に得られた抑制レベルは、発生した輻輳状態レベルの値と一致している。
【０１５９】
以上の例は、「緩和方向」の通知データに付されているタイムスタンプ値が「規制方向」の最後に通知された通知データに付されていたタイムスタンプ値よりも小さい場合であったが、勿論、「緩和方向」の通知データに付されているタイムスタンプ値の方が「規制方向」の最後に通知された通知データに付されていたタイムスタンプ値よりも大きい場合には「緩和方向」で生じた輻輳状態レベルに抑制レベルが更新されるため、抑制レベルとバッファの輻輳状態レベルの一致を実現できる。
【０１６０】
（Ｇ−３）第７の実施形態の効果
以上のように第７の実施形態によれば、第２の実施例と同等の効果が得られるのに加え、緩和方向遷移用の通知キュー２０３Ｂは入力パケットのスループットの変動が激しいような場合でも比較的小規模で済むため、装置コストの一層の低減化を実現できる。
【０１６１】
（Ｈ）第８の実施形態（第９の手段と第１８の手段の一例に相当する。）
前述の第７の実施形態では、タイムスタンプ値を抑制レベルの更新基準に含めることで、バッファの輻輳状態レベルと抑制レベルの不一致を解消させる方法を示した。しかし、入力パケットのスループットの変動が大きい場合には、やはり状態通知キュー２０３の深さ（大きさ）も比較的深くする必要がある。
【０１６２】
理由は、入力パケットのスループットの変動が大きいということは、通知データの頻度が増大することと等価なため、増大した通知データを溢れることなくキューイングすることが可能な状態通知キューが必要になることによる。
【０１６３】
従って、状態通知キュー２０３の深さ（大きさ）が通知データの発生量に比して十分でないと、通知データの廃棄が発生して過度の抑制制御が継続される可能性が生じてしまう。
【０１６４】
（Ｈ−１）装置構成
そこで、第８の実施形態では、状態通知キューが比較的浅く（小さく）ても、「性能を十分に出すことができない」時間を可能な限り少なくするために以下の装置構成を採用する。図１２に、第８の実施形態に係る輻輳状態通知装置の機能ブロック構成を示す。この第８の実施形態は、第５の実施形態の構成と第７の実施形態のタイムスタンプ機能を組み合わせたことを特徴とする。
【０１６５】
すなわち、図１２は、図９との同一部分に同一符号を付して示す図面であり、輻輳状態保持部１０４にタイムスタンプ監視機能部１０４Ｂが設けられている点を除いて同一の構成を有している。若しくは、図１２は、図１１との同一部分に同一符号を付して示す図であり、定期通知挿入部２０４と、状態遷移変数更新／保存機能部１０４Ａが設けられている点を除いて同一の構成を有するものである。
【０１６６】
なお図１２中の輻輳状態監視部２０２、定期通知挿入部２０４、状態変数更新／保存機能部１０４Ａ及びタイムスタンプ監視機能部１０４Ｂは、それぞれ図１１の輻輳状態監視部、図９の定期通知挿入部、図９の状態変数更新／保存機能部、図１１のタイムスタンプ監視機能部と同じものである。
【０１６７】
すなわち、輻輳状態監視部２０２は、タイムスタンプ付与機能付きのものである。また、定期通知挿入部２０４は、バッファ２０１の最新の輻輳状態レベルを常に通知するものである。また、状態変数更新／保存機能部１０４Ａは、通知データが「規制方向」か「緩和方向」かで状態遷移変数を更新するものである。タイムスタンプ監視機能部１０４Ｂは、「規制方向」の通知データのうち最後に通知されたものよりも時間的に古い「緩和方向」の通知データによる抑制レベルの更新を禁止するものである。
【０１６８】
（Ｈ−２）輻輳通知動作
この実施形態では、輻輳状態監視部２０２が、ヒステリシス特性を有する判定閾値を使用してバッファ２０１の輻輳状態レベルを判定し、その遷移が確認されたとき、当該遷移が確認されたタイムスタンプ値と、通知種別と、輻輳状態レベルを通知データとして出力する。
【０１６９】
この通知データは、その通知種別が「規制方向」か「緩和方向」かに応じて対応する通知キュー２０３Ａ又は２０３Ｂに与えられる。
【０１７０】
状態通知キュー２０３は、規制方向遷移用の通知キュー２０３Ａ内にある通知データの出力を優先し、通知キュー２０３Ａ及び２０３Ｂのいずれにも通知データが存在しない場合、定期通知挿入部２０４から与えられている最新の輻輳状態レベルを定期的に出力する。ここで、定期的に挿入される通知データには通知種別として「定期」が付される。なお、定期の通知データには、タイムスタンプ値は付されない。
【０１７１】
輻輳状態保持部１０４は、通知種別が「規制方向」である場合、通知データの輻輳状態レベルで抑制レベルを更新する。
【０１７２】
一方、輻輳状態保持部１０４は、通知種別が「緩和方向」である場合、タイムスタンプ監視機能部１０４Ｂによって更新が可能と許可されたものについてのみ、状態変数更新／保存機能部１０４Ａによる抑制レベルの更新処理を実行する。
【０１７３】
ここでは、タイムスタンプ値に基づく判定によって、時間的に古いデータによる抑制レベルの更新が排除される。また、状態遷移変数に基づく判定によって、抑制レベルとバッファの輻輳状態レベルとの不一致、特に抑制レベルの方がバッファの輻輳状態レベルよりも小さくなる事態が有効に回避される。
【０１７４】
なお、輻輳状態保持部１０４は、通知種別が「定期」である場合、通知のあった輻輳状態レベルで抑制レベルを更新することにより、通知キューの容量が十分でないこと等に起因して生じた抑制レベルとバッファの輻輳状態レベルとの不一致を確実に一致させる。
【０１７５】
このように、本実施形態では、抑制判定部１０３に通知される抑制レベルの信頼性が非常に高くなる。
【０１７６】
（Ｈ−３）第８の実施形態の効果
以上のように第８の実施形態によれば、第７の実施例と同等の効果が得られるのに加え、状態通知キューが比較的浅い（小さい）場合でも、抑制データの信頼性を高めることが可能となり、装置全体のコスト低減が可能となる。
【０１７７】
また、定期通知により必要以上に入力パケットを廃棄している状態を回避することが可能となり、装置の性能を向上させることが可能となる。
【０１７８】
（Ｉ）他の実施形態
（１）第１の実施形態においては、判定結果へのヒステリシス特性を可能とする判定閾値を使用する（すなわち、規制方向側と緩和方向側とで異なる種類の判定閾値を使用する）場合について説明したが、判定基準に従来手法を使用する（規制方向側と緩和方向側とで同じ閾値を使用する）輻輳状態監視部と状態通知キューとを組み合わせて輻輳状態通知装置を構成しても良い。
【０１７９】
ここで、単一の通知キューを使用する場合が、前述の第２の手段と第１１の手段に対応する。また、規制方向用の通知キューと緩和方向用の通知キューの２つを使用する場合が、前述の第３の手段と第１２の手段に対応する。
【０１８０】
いずれの構成の場合も、状態遷移の頻度は第１の実施形態よりも増加するものの、その通知は状態通知キューを介して行われるため、輻輳状態レベルのバースト的な遷移を平均的なスループットとすることができる。
【０１８１】
なお、単一の通知キューを使用する場合、この通知キューには規制方向の通知データも緩和方向の通知データも書き込み可能としても良いし、そのいずれか一方だけの書き込みを可能としても良い。
【０１８２】
また、規制方向用の通知キューと緩和方向用の通知キューを使用する場合は、リアルタイム性の要請の高い規制方向側の状態遷移を優先的に通知できるという効果が更に期待できる。
【０１８３】
（２）第２の実施形態においては、規制方向側と緩和方向側とで異なる種類の判定閾値を使用する輻輳状態監視部と、規制方向用の通知キューと緩和方向用の通知キューの両方を備えた状態通知キューとを組み合わせた構成の輻輳状態通知装置について説明したが、状態通知キューが単一の通知キューからなるものに置き換えても良い。この構成は、前述の第４の手段と第１３の手段に対応する。
【０１８４】
かかる構成の場合も、通知データの通知を平均的なスループットにできるという効果が期待できる。この場合も、この通知キューには規制方向の通知データも緩和方向の通知データも書き込み可能としても良いし、そのいずれか一方だけの書き込みを可能としても良い。
【０１８５】
（３）第３の実施形態においては、規制方向側と緩和方向側とで異なる種類の判定閾値を使用する輻輳状態監視部と、規制方向用の通知キューと緩和方向用の通知キューの両方を備えた状態通知キューと、状態遷移変数を用いることで抑制レベルがバッファの輻輳状態レベルよりも小さくなるのを回避する機能とを組み合わせた構成の輻輳状態通知装置について説明したが、その輻輳状態監視部に従来手法の判定基準を使用する（規制方向側と緩和方向側とで同じ閾値を使用する）ものを適用しても良い。この構成は、前述の第７の手段と第１６の手段に対応する。
【０１８６】
かかる構成とする場合、状態遷移の頻度は第３の実施形態よりも増加するものの、その通知は状態通知キューを介して行われるため、輻輳状態レベルのバースト的な遷移を平均的なスループットとすることができる。
【０１８７】
また、リアルタイム性の要請の高い規制方向側の状態遷移を優先的に通知できるという効果も期待できるし、抑制レベルがバッファの輻輳状態レベルよりも小さくなる事態を有効に回避できるという効果も得られる。
【０１８８】
（４）第４の実施形態においては、規制方向側と緩和方向側とで異なる種類の判定閾値を使用する輻輳状態監視部と、規制方向用の通知キューと緩和方向用の通知キューの両方を備えた状態通知キューと、状態通知キューが空の場合に最新の輻輳状態レベルを定期的に通知する機能とを組み合わせた構成の輻輳状態通知装置について説明したが、その輻輳状態監視部に従来手法の判定基準を使用する（規制方向側と緩和方向側とで同じ閾値を使用する）ものを適用しても良い。この構成は、前述の第８の手段と第１７の手段に対応する。
【０１８９】
この構成の場合も、状態遷移の頻度は第４の実施形態よりは増加するものの、その他は第４の実施形態と同様の効果を得ることが期待できる。
【０１９０】
（５）第５の実施形態においては、規制方向側と緩和方向側とで異なる種類の判定閾値を使用する輻輳状態監視部と、規制方向用の通知キューと緩和方向用の通知キューの両方を備えた状態通知キューと、状態遷移変数を用いることで抑制レベルがバッファの輻輳状態レベルよりも小さくなるのを回避する機能と、状態通知キューが空の場合に最新の輻輳状態レベルを定期的に通知する機能とを組み合わせた構成の輻輳状態通知装置について説明したが、その輻輳状態監視部に従来手法の判定基準を使用する（規制方向側と緩和方向側とで同じ閾値を使用する）ものを適用しても良い。この構成は、前述の第８の手段と第１７の手段に対応する。
【０１９１】
この構成の場合も、状態遷移の頻度は第５の実施形態よりも増加するものの、その他は第５の実施形態と同様の効果を得ることができる。
【０１９２】
（６）第６の実施形態においては、規制方向側と緩和方向側とで異なる種類の判定閾値を使用する輻輳状態監視部と、単一の状態通知キューと、当該状態通知キューが空の場合に最新の輻輳状態レベルを定期的に通知する機能とを組み合わせた構成の輻輳状態通知装置について説明したが、その輻輳状態監視部に従来手法の判定基準を使用する（規制方向側と緩和方向側とで同じ閾値を使用する）ものを適用しても良い。この構成は、前述の第６の手段と第１５の手段に対応する。
【０１９３】
かかる構成とする場合、状態遷移の頻度は第６の実施形態よりも増加するものの、その通知は状態通知キューを介して行われるため、輻輳状態レベルのバースト的な遷移を平均的なスループットとすることができる。
【０１９４】
なお、この場合も第６の実施形態の場合も、単一の状態通知キューには規制方向の通知データも緩和方向の通知データも書き込み可能としても良いし、そのいずれか一方だけの書き込みを可能としても良い。
【０１９５】
（７）第７の実施形態においては、規制方向側と緩和方向側とで異なる種類の判定閾値を使用する輻輳状態監視部と、規制方向用の通知キューと緩和方向用の通知キューの両方を備えた状態通知キューと、タイムスタンプ値による発生時刻の古い状態遷移レベルによる抑制レベルの書き込み禁止機能とを組み合わせた構成の輻輳状態通知装置について説明したが、その輻輳状態監視部に従来手法の判定基準を使用する（規制方向側と緩和方向側とで同じ閾値を使用する）ものを適用しても良い。この構成（ここでは７−１構成と呼ぶ。）は、前述の第９の手段と第１８の手段に対応する。この７−１構成の場合も、状態遷移の頻度は第７の実施形態よりも増加するものの、その他は第７の実施形態と同様の効果を得ることができる。
【０１９６】
また、第７の実施形態に係る輻輳状態通知装置に、状態通知キューが空の場合に最新の輻輳状態レベルを定期的に通知する機能とを組み合わせた構成（ここでは、７−２構成と呼ぶ。）を採用しても良い。この７−２構成も、前述の第９の手段と第１８の手段に対応する。この７−２構成の場合、必要以上に入力パケットが廃棄される時間を最小限にできるという更なる効果が期待できる。
【０１９７】
また、７−２構成の輻輳状態監視部に、従来手法の判定基準を使用する（規制方向側と緩和方向側とで同じ閾値を使用する）ものを適用しても良い。この構成（７−３構成と呼ぶ。）も、前述の第９の手段と第１８の手段に対応する。この７−３構成の場合、７−２構成よりも状態遷移の頻度は増加するものの、その他は７−２構成と同様の効果を得ることができる。
【０１９８】
（８）第８の実施形態においては、規制方向側と緩和方向側とで異なる種類の判定閾値を使用する輻輳状態監視部と、規制方向用の通知キューと緩和方向用の通知キューの両方を備えた状態通知キューと、状態遷移変数を用いることで抑制レベルがバッファの輻輳状態レベルよりも小さくなるのを回避する機能と、状態通知キューが空の場合に最新の輻輳状態レベルを定期的に通知する機能と、タイムスタンプ値による発生時刻の古い状態遷移レベルによる抑制レベルの書き込み禁止機能とを組み合わせた構成の輻輳状態通知装置について説明したが、その輻輳状態監視部に従来手法の判定基準を使用する（規制方向側と緩和方向側とで同じ閾値を使用する）ものを適用しても良い。この構成は、前述の第９の手段と第１８の手段に対応する。
【０１９９】
この構成の場合も、状態遷移の頻度は第８の実施形態よりも増加するものの、その他は第８の実施形態と同様の効果を得ることができる。
【０２０２】
【発明の効果】
（Ａ）上述のように請求項１又は請求項６に係る発明によれば、上方に遷移した輻輳状態レベルは流入量規制用の第１の状態通知キューを介して通知する一方、下方に遷移した輻輳状態レベルは流入量緩和用の第２の状態通知キューを介して通知するようにし、しかも、いずれの状態通知キューにも通知すべき輻輳状態レベルが存在する場合には、第１の状態通知キューに存在している輻輳状態レベルを第２の状態通知キューに存在している輻輳状態レベルに優先させて通知するようにしたことにより、バースト的な輻輳状態レベルの遷移を平均的なスループットの通知として実現できる。
【０２０３】
また、状態通知キューを流入規制用の第１の状態通知キューと流入緩和用の第２の状態通知キューとの２種類とし、第１の状態通知キューに存在する輻輳状態レベルの通知を第２の状態通知キューに存在する輻輳状態レベルの通知に優先させるため、規制方向の通知をリアルタイムで実現できる。
【０２０５】
（Ｂ）上述のように請求項２又は請求項７に係る発明によれば、バッファ内の滞留パケット量から判定される輻輳状態レベルの遷移が検出されるたび、当該遷移後の輻輳状態レベルをバッファの上流側に通知する輻輳状態通知装置であって、輻輳状態レベルの上方遷移の判定に使用する判定閾値と下方遷移の判定に使用する判定閾値とで異なる値を使用する輻輳状態監視手段を備えると共に、判定された輻輳状態レベルのうち上方に遷移した輻輳状態レベルは流入量規制用の第１の状態通知キューを介して通知する一方、下方に遷移した輻輳状態レベルは流入量緩和用の第２の状態通知キューを介して通知するようにし、しかも、いずれの状態通知キューにも通知すべき輻輳状態レベルが存在する場合には、第１の状態通知キューに存在している輻輳状態レベルを第２の状態通知キューに存在している輻輳状態レベルに優先させて通知する機能を設けたことにより、バースト的な輻輳状態レベルの遷移を平均的なスループットの通知として実現できる。
【０２０６】
また、状態通知キューを流入規制用の第１の状態通知キューと流入緩和用の第２の状態通知キューとの２種類とし、第１の状態通知キューに存在する輻輳状態レベルの通知を第２の状態通知キューに存在する輻輳状態レベルの通知に優先させるため、規制方向の通知をリアルタイムで実現できる。
【０２０８】
（Ｃ）上述のように請求項３又は請求項８に係る発明によれば、請求項１若しくは請求項２又は請求項６若しくは請求項７に係る発明に、判定された輻輳状態レベルが第１の状態通知キューを介して通知される場合、被通知側で保持されているパケット流入量制御用の輻輳状態レベルを通知された値に更新し、輻輳状態レベルが第２の状態通知キューを介して通知される場合、被通知側で保持されているパケット流入量制御用の輻輳状態レベルよりも通知された値が１段階低い値であり、かつ、遷移方向に応じて値が増減される状態遷移変数と上記パケット流入量制御用の輻輳状態レベルの値が一致するとの条件が満たされるか判定し、条件が満たされるとき上記パケット流入量制御用の輻輳状態レベルを通知された値に更新し、条件が満たされないとき現在の値をそのまま保持する機能を更に追加したことにより、大量に発生した輻輳状態レベルの遷移の一部が通知されないような事態が生じたとしても、バッファ内の輻輳状態レベルよりも保持されている輻輳状態レベルの方が小さくなる事態を確実に回避できる。
【０２０９】
（Ｄ）上述のように請求項４又は請求項９に係る発明によれば、請求項１、請求項２若しくは請求項３又は請求項６、請求項７若しくは請求項８に係る発明に、上記第１の状態通知キューと第２の状態通知キューがいずれも空のとき、定期的に最新の輻輳状態レベルを通知する機能を更に追加することにより、仮に状態通知キューの深さ（大きさ）が十分でなく、大量に発生した輻輳状態レベルの遷移の一部が通知されないような事態が生じたとしても、その後の定期通信によって輻輳状態レベルを早期に最新の状態に一致させることができる。
【０２１０】
（Ｅ）上述のように請求項５又は請求項１０に係る発明によれば、請求項１、請求項２若しくは請求項４又は請求項６、請求項７若しくは請求項９に係る発明に、判定された輻輳状態レベルが第１の状態通知キューを介して通知される場合、被通知側で保持されているパケット流入量制御用の輻輳状態レベルを通知のあった値に更新し、輻輳状態レベルが第２の状態通知キューを介して通知される場合、第１の状態通知キューから最後に通知された輻輳状態レベルに付されていたタイムスタンプよりも通知のあった輻輳状態レベルに付されているタイムスタンプの方が時間的に後であるか否か判定し、時間的に後であるとき上記パケット流入量制御用の輻輳状態レベルを通知のあった値に更新し、その他のとき現在の値をそのまま保持する機能を更に追加したことにより、大量に発生した輻輳状態レベルの遷移の一部が通知されないような事態が生じたとしても、バッファ内の輻輳状態レベルよりも保持されている輻輳状態レベルの方が小さくなる事態を確実に回避できる。
【図面の簡単な説明】
【図１】輻輳状態通知装置の第１の実施形態例を示す機能ブロック図である。
【図２】輻輳状態通知装置の従来構成例を示す機能ブロック図である。
【図３】輻輳状態通知装置の大規模従来例を示す機能ブロック図である。
【図４】パケット交換装置の概念構成例を示す図である。
【図５】輻輳状態レベルの判定にヒステリシス特性を与える判定閾値の設定例を示す図である。
【図６】輻輳状態通知装置の第２の実施形態例を示す機能ブロック図である。
【図７】輻輳状態通知装置の第３の実施形態例を示す機能ブロック図である。
【図８】輻輳状態通知装置の第４の実施形態例を示す機能ブロック図である。
【図９】輻輳状態通知装置の第５の実施形態例を示す機能ブロック図である。
【図１０】輻輳状態通知装置の第６の実施形態例を示す機能ブロック図である。
【図１１】輻輳状態通知装置の第７の実施形態例を示す機能ブロック図である。
【図１２】輻輳状態通知装置の第８の実施形態例を示す機能ブロック図である。
【符号の説明】
１０、１００…入力パケット廃棄制御部、１１、１０１…優先度識別部、１２、１０２…抑制制御部、１３、１０３…抑制判定部、１０４…輻輳状態保持部、１０４Ａ…状態遷移変数更新／保持機能部、１０４Ｂ…タイムスタンプ監視機能部、２０、２００…バッファ制御部、２１、２０１…バッファ、２０２…輻輳状態監視部、２０３…状態通知キュー、２０３Ａ…規制方向遷移用キュー、２０３Ｂ…緩和方向遷移用キュー、２０４…定期通知挿入部。
【図１】
0003563016.tif 000004
【図２】
0003563016.tif 000005
【図３】
0003563016.tif 000006
【図４】
0003563016.tif 000007
【図５】
0003563016.tif 000008
【図６】
0003563016.tif 000009
【図７】
0003563016.tif 000010
【図８】
0003563016.tif 000011
【図９】
0003563016.tif 000012
【図１０】
0003563016.tif 000013
【図１１】
0003563016.tif 000014
【図１２】
0003563016.tif 000015