(57)【要約】  パケットバッファ装置１１−１は、到着したパケットを一時的に保持するキュー２１と、到着したパケットがキュー２１内に滞留する時間を予測する滞留時間予測手段２４と、滞留時間予測手段２４により決定された予測時間ＴＦが所定の第１基準値ＴＨＴを超えるとき、到着したパケットを廃棄するパケット廃棄手段２６と、を備える。
2010089886.tif 000002
【特許請求の範囲】
【請求項１】
到着したパケットを一時的に保持するキューと、
到着したパケットが前記キュー内に滞留する時間を予測する滞留時間予測手段と、
前記滞留時間予測手段により決定された予測時間が所定の第１基準値を超えるとき、到着したパケットを廃棄するパケット廃棄手段と、
を備えるパケットバッファ装置。
【請求項２】
到着したパケットを一時的に保持するキューと、
到着したパケットが前記キュー内に滞留する時間を予測する滞留時間予測手段と、
前記滞留時間予測手段により決定された予測時間が所定の第１基準値を超える超過量に応じて変化する割合で、到着したパケットを廃棄するパケット廃棄手段と、
を備えるパケットバッファ装置。
【請求項３】
前記予測時間が前記第１基準値を超えるとき、到着したパケットの送信元装置へ、輻輳の発生を通知する輻輳発生通知手段を備える請求項１に記載のパケットバッファ装置。
【請求項４】
前記キューに保持されている到着パケットのデータ量であるキュー長を測定するキュー長測定手段と、
キューから出力されるパケットの出力レートを測定するレート測定手段と、を備え、
前記滞留時間予測手段は、測定された前記キュー長と測定された前記出力レートとに基づいて、前記予測時間を決定する請求項１〜３のいずれか一項に記載のパケットバッファ装置。
【請求項５】
前記キューに保持されているデータ量であるキュー長を測定するキュー長測定手段と、
パケット到着時において測定された前記キュー長を記憶する記憶手段と、
前記キュー内に滞留するパケットの滞留時間を測定する滞留時間測定手段と、を備え、
前記滞留時間予測手段は、パケット到着時から現時点までの前記キュー長の変化率と、現時点で測定した前記滞留時間とに基づいて、前記予測時間を決定する請求項１〜３のいずれか一項に記載のパケットバッファ装置。
【請求項６】
前記レート測定手段は、一定周期で、前記キューから出力されるパケット量を測定し、各周期間におけるパケット出力量と前記周期に基づいて、前記出力レートを測定する請求項４に記載のパケットバッファ装置。
【請求項７】
前記レート測定手段は、前記キューにおけるパケットの書き込み時において前記キューへ書き込まれるパケット累積量を測定し、前回書き込み時と今回書き込み時との間のパケット累積量の差と、前回書き込み時と今回書き込み時との間の時間間隔に基づいて、前記出力レートを測定する請求項４に記載のパケットバッファ装置。
【請求項８】
前記レート測定手段は、前記キューにおけるパケットの読み出し時において前記キューから読み出されるパケット累積量を測定し、前回読み出し時と今回読み出し時との間のパケット累積量の差と、前回読み出し時と今回読み出し時との間の時間間隔に基づいて、前記出力レートを測定する請求項４に記載のパケットバッファ装置。
【請求項９】
前記レート測定手段は、順次測定した出力レートの測定値の加重平均値を前記出力レートとして出力する請求項４に記載のパケットバッファ装置。
【請求項１０】
前記キュー長測定手段は、順次測定したキュー長の加重平均値を前記キュー長として出力する請求項４又は５に記載のパケットバッファ装置。
【請求項１１】
前記キュー内に滞留するパケットの滞留時間を測定する滞留時間測定手段を備え、
前記パケット廃棄手段は、測定される滞留時間が所定の第２基準値未満のとき、前記予測時間が前記第１基準値を超えていても前記パケットを廃棄しない請求項１又は３のいずれか一項に記載のパケットバッファ装置。
【請求項１２】
到着したパケットがキュー内に滞留する時間を予測する滞留時間予測ステップと、
前記滞留時間予測ステップにより決定された予測時間が所定の基準値を超えるとき、到着したパケットを廃棄するパケット廃棄ステップと、
を含むパケット廃棄方法。
【請求項１３】
到着したパケットがキュー内に滞留する時間を予測する滞留時間予測ステップと、
前記滞留時間予測ステップにより決定された予測時間が所定の基準値を超える超過量に応じて変化する割合で、到着したパケットを廃棄するパケット廃棄ステップと、
を含むパケット廃棄方法。
【請求項１４】
到着したパケットについて予測された前記予測時間が前記基準値を超えるとき、前記到着したパケットの送信元装置へ、輻輳の発生を通知する請求項１２に記載のパケット廃棄方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、到着したパケットを一時的に保持するパケットバッファ装置におけるパケットの廃棄方法に関する。
【背景技術】
【０００２】
近年のインターネットの普及に伴い、種々のＷＥＢサーバ、電子メール、ＩＰ電話や動画転送といった様々なサービスを、インターネット上で実現する動きが活発化している。このため、インターネットを支えるネットワークノード装置における、サービス品質（QoS: Quality of Service）制御の重要性がますます高まっている。【０００３】
次世代ネットワークなどで提供されるサービスは、原則として、十分なデータ伝送帯域幅をネットワークに用意することによってサービスの品質が保証される。一方で、ＷＥＢサーバによるサービス、ＩＰ電話サービスや動画転送サービスでは、通常のインターネット上でサービスが提供されるため、十分なデータ伝送帯域幅が与えられるとは限らない。【０００４】
なお、パケットバッファが輻輳した際のデータ廃棄方法としては、テイルドロップ（Tail Drop）とランダム初期検知（RED: Random Early Detection）が提案されている。また、パケットの滞在時間に応じてパケットの廃棄率を変化させることによりＲＥＤを実施するエッジ・ノード装置が提案されている。さらに、基地局から移動局へ送信するパケットが基地局のバッファに滞留する予定時刻を算出するデータ流入量制御装置が開示されている。さらに、転送データに登録されているデータ受取先での到着必須時刻を読み取り、到着必須時刻までに到着しないと判定したとき、データパケットを廃棄するデータ伝送方法が開示されている。【０００５】
【特許文献１】特開２００５−３４８１６６号公報
【特許文献２】特開２００８−５３８５１号公報
【特許文献３】特開平９−１８５１０号公報
【０００６】
【非特許文献１】B.Braden, D.Clark, J.Crowcroft, "Recommendations on Queue Management and Congestion Avoidance in the Internet", RFC2309, IETF, April 1998
【発明の開示】
【発明が解決しようとする課題】
【０００７】
データ伝送を行うネットワーク上で十分なデータ伝送帯域幅が保証されない環境下では、ネットワーク上で発生する輻輳の影響を受けて、大きな遅延変動が発生する。この遅延変動は遅延ジッタとも呼ばれる。電話サービスや動画提供サービスにおいて大きな遅延変動が発生すると、快適な視聴に支障をきたす。Ｗｅｂサービスにおいても、遅延変動はユーザへのレスポンス時間に影響を与える。また、データ転送においても遅延変動は実効スループットに影響を与え、転送効率を悪化させる要因にもなる。
このように、輻輳発生時における遅延変動を低減することは、ネットワークのサービス品質を確保する上で重要である。上記問題点に鑑み、開示の装置及び方法は、到着したパケットを一時的に保持するパケットバッファ装置において、輻輳発生時における出力パケットの遅延変動を低減することを目的とする。
【課題を解決するための手段】
【０００８】
実施例の一形態によれば、到着したパケットを一時的に保持するキューと、到着したパケットがこのキュー内に滞留する時間を予測する滞留時間予測手段と、この滞留時間予測手段により決定された予測時間が所定の第１基準値を超えるとき到着したパケットを廃棄するパケット廃棄手段と、を備えるパケットバッファ装置が与えられる。
【発明の効果】
【０００９】
所定時間を超えてキュー内に滞留することが予定される到着パケットを廃棄するため、輻輳が発生しても、パケットバッファ装置において生じる遅延変動が低減される。
【図面の簡単な説明】
【００１０】
【図１】出力レートの変動と遅延変動との関係を説明するグラフである。
【図２】滞留時間に基づくパケット廃棄制御の第１例を説明する図である。
【図３】滞留時間に基づくパケット廃棄制御の第２例を説明する図である。
【図４Ａ】滞留時間に基づくパケット廃棄制御において発生する遅延変動を説明する図（その１）である。
【図４Ｂ】滞留時間に基づくパケット廃棄制御において発生する遅延変動を説明する図（その２）である。
【図４Ｃ】滞留時間に基づくパケット廃棄制御において発生する遅延変動を説明する図（その３）である。
【図４Ｄ】滞留時間に基づくパケット廃棄制御において発生する遅延変動を説明する図（その４）である。
【図４Ｅ】滞留時間に基づくパケット廃棄制御において発生する遅延変動を説明する図（その５）である。
【図５】開示のスイッチの全体構成を説明する図である。
【図６】図５に示す入力パケットバッファの第１構成例を説明する構成図である。
【図７】開示のパケット廃棄方法を説明する第１例の方法である。
【図８】開示のパケット廃棄方法を説明する第２例の方法である。
【図９】図６に示すレート測定部の第１構成例を説明する構成図である。
【図１０】開示のレート測定方法の第１例説明する方法である。
【図１１】図６に示すレート測定部の第２構成例を説明する構成図である。
【図１２】開示のレート測定方法の第２例を説明する方法である。
【図１３】図５に示す入力パケットバッファの第２構成例を説明する構成図である。
【図１４】開示のパケット廃棄方法の第３例を説明する方法である。
【図１５】図５に示す入力パケットバッファの第３構成例を説明する構成図である。
【図１６】開示のパケット廃棄方法の第４例を説明する方法である。
【図１７】図５に示す入力パケットバッファの第４構成例を説明する構成図である。
【図１８】開示のパケット廃棄方法の第５例を説明する方法である。
【図１９】図５に示す入力パケットバッファの第５構成例を説明する構成図である。
【図２０】開示のパケット廃棄方法の第６例を説明する方法である。
【図２１】図５に示す入力パケットバッファの第６構成例を説明する構成図である。
【図２２】開示のパケット廃棄方法の第７例を説明する方法である。
【図２３】図５に示す入力パケットバッファの第７構成例を説明する構成図である。
【図２４】開示のパケット廃棄方法の第８例を説明する方法である。
【符号の説明】
【００１１】
１０    スイッチ
１１−１〜１１−Ｌ    入力パケットバッファ
１２    パケット交換部
１３−１〜１３−Ｌ    出力パケットバッファ
２１、２１−１〜２１−Ｎ    キュー
２２    キュー長測定部
２３    レート測定部
２４    滞留時間予測部
２６    パケット廃棄部
Ｐ    パケット
【発明を実施するための最良の形態】
【００１２】
以下、添付する図面を参照して実施例を説明する。上述の通り、パケットバッファ装置が輻輳した際のデータ廃棄方法としては、テイルドロップとＲＥＤが知られている。テイルドロップでは、パケットバッファ装置はその内部のキュー内に格納されたデータ量がある規定値を超えるか否かを判定する。キュー内のデータ量が規定値を超えたとき、パケットバッファ装置は、その後に到着するパケットをキュー内に格納せずに廃棄する。なお、キュー内に格納されるデータ量のことを、以下の説明において「キュー長」と示すことがある。なお、キューと、入力および／または出力パケットバッファとの技術的関係については後述する。【００１３】
ＲＥＤは、送信元装置のＴＣＰ制御において、パケット廃棄が発生するとパケットの送信レートを下げるという機能を利用する輻輳制御方法である。パケットバッファ装置は、輻輳が発生しそうなとき早めに、ある廃棄率でパケットを廃棄する。そうすることにより、輻輳が大きくなる前に送信元装置に輻輳の発生を通知して輻輳を解消する。すなわち、パケットバッファ装置は、ある廃棄率でランダムにフローを破棄することで、このキューに収容されるフロー全てのレートを同時に下げ、パケット転送のスループットが劣化する現象を避ける。【００１４】
上記のテイルドロップ及びＲＥＤは、いずれもキュー長に基づくパケットの廃棄制御である。パケットバッファ装置においては、ＱｏＳ制御の際に、キューに優先度を与えられるのが一般的である。優先度がより低いキューの出力レートは、優先度がより高いキューへ入力されるトラヒック量に依存してリアルタイムに変化する。【００１５】
ここで、キュー内の滞在時間は、「キュー内の滞留時間＝キュー長（データ量）／出力レート」で定まるため、遅延変動は出力レートに依存する。図１は、出力レートの変動と遅延変動との関係を説明するグラフである。図１に示す実線が出力レートの変動を示し、破線が遅延時間を示す。図示するとおり、出力レートが増加するに応じてキュー内の滞留時間すなわち遅延が増加し、出力レートの変動が遅延変動を生じることがわかる。このように、上記のテイルドロップやＲＥＤといったキュー長に基づく廃棄制御では、輻輳時に発生する出力レート変動により遅延変動を招いてしまうという問題がある。【００１６】
図２は、滞留時間に基づくパケット廃棄制御の第１例を説明する図である。参照符号１はパケットバッファ装置を示し、参照符号Ｐ１及びＰ２はパケットバッファ装置１に入力された入力パケットを示す。参照符号３−１〜３−Ｎは、入力パケットを一時的に保持するＮ個のキューを示し、参照符号２はパケット判別部を示し、参照符号４はパケット分配部を示し、参照符号５はスケジューラを示す。なお、このパケットバッファ装置はレイヤ２およびレイヤ３のパケット転送装置に適用可能である。【００１７】
パケット判別部２は、入力パケットＰ１、Ｐ２が、送信元のユーザについて定めた入力帯域幅に関する規定を遵守しているか否かを判別し、規定を遵守しているパケットとそうでないパケットに分類する。図２において、パケット判別部２は白抜きの矩形で示すパケットＰ１は規定を遵守しているパケットをマーキングし、ハッチングされた矩形で示すパケットＰ２は、規定を遵守していないパケットをマーキングした例を示す。【００１８】
パケット分配部４は、入力パケットの宛先、ユーザ、アプリケーションなどに応じて、入力パケットを、キュー３−１〜３−Ｎのいずれかに分配する。スケジューラ５は、所定の優先度や出力帯域幅に応じて、キュー３−１〜３−Ｎからパケットを読み出して出力する。図２に示すパケット廃棄制御では、現在、パケットがキューに滞留している滞留時間を測定する。測定された滞留時間が基準値を超える場合には、入力帯域幅に関する規定を遵守していないパケットＰ２を廃棄する。以下、このような廃棄制御を、「滞留時間に基づくテイルドロップ」（Time Based Tail Drop）と呼ぶことがある。【００１９】
または、測定された滞留時間に応じて変化する廃棄率を決定し、決定された廃棄率で、入力帯域幅に関する規定を遵守していないパケットＰ２を廃棄する。以下、このような廃棄制御を、「滞留時間に基づく重み付けランダム初期検知」（Time Based WRED）と呼ぶことがある。ＷＲＥＤは、Weighted Random Early Detectionの略である。【００２０】
図３は、滞留時間に基づくパケット廃棄制御の第２例を説明する図である。図２に示す構成要素と同じ構成要素に同じ参照符号を付する。図３に示すパケット廃棄制御では、現在、パケットがキューに滞留している滞留時間を測定し、基準値を超えてキュー内に滞留したパケットをキューの先頭から廃棄する。以下、このような廃棄制御を、「滞留時間に基づくヘッドドロップ」（Time Based Head Drop）と呼ぶことがある。【００２１】
滞留時間に基づくテイルドロップや滞留時間に基づくＷＲＥＤでは、パケットバッファ装置１は滞留時間に基づいて廃棄制御を行っている。このとき、パケットバッファ装置１は、滞留時間としてキューの先頭パケットの滞留時間を用いていた。このため先頭パケットの滞留時間が基準値を超えて廃棄処理が開始した時点で既にキュー内にパケットがたまり過ぎている。このため、廃棄処理が開始するとキューが空になるまで滞留時間が増加し、キューが空になったときにまた滞留時間が急減する現象が生じていた。この理由を図４Ａ〜図４Ｅに沿って説明する。【００２２】
図４Ａ〜図４Ｅは、滞留時間に基づくパケット廃棄制御において発生する遅延変動を説明する図である。図４Ａの状態において、パケットの入力レートが出力レートよりも大きいため、キュー３−１のキュー長は増加傾向にあるが、まだ、キューの先頭パケットの滞留時間は、パケット廃棄を始める基準値ＴＨＴＤに達していない。【００２３】
その後、図４Ｂの状態になると、キュー３−１のキュー長が図４Ａの状態と比べて増加する。このため、図４Ｂの状態では、図４Ａの状態よりもキュー３−１内に滞留する時間が長くなるため、パケットの遅延時間が長くなる。この様子を図４Ｅに示す。矢印Ａ〜Ｄは、それぞれ図４Ａ〜４Ｄの状態における遅延時間を示す。【００２４】
図４Ｃの状態になると、キュー３−１の先頭パケットの滞留時間が基準値ＴＨＴＤを超えているため、パケットバッファ装置１は、テイルドロップ又はＷＲＥＤを開始する。この結果、キュー３−１にはパケットが入力されなくなるが、キュー３−１内には、すでに多量のパケットが保持されている。このため、キュー３−１内のパケットが全て出力されるまで、キュー先頭に到達したパケットの滞留時間は増加し続ける。そして図４Ｄの状態になり、キュー３−１内が空になると滞留時間が「０」に戻り、キュー内へのパケットの格納が再開される。このため遅延時間が急減する。このように、滞留時間に基づくテイルドロップ及び滞留時間に基づくＷＲＥＤにおいても、輻輳時に遅延変動が発生するという問題があった。【００２５】
図５は、開示のスイッチの全体構成を説明する図である。スイッチ１０は、複数の入力ポートのいずれかから入力されたパケットを、複数の出力ポートのいずれかへ出力する装置である。スイッチ１０は、例えばレイヤ２スイッチやレイヤ３スイッチであってよい。参照符号１１−１〜１１−Ｌは入力パケットバッファを示し、参照符号１２はパケット交換部１２を示し、参照符号１３−１〜１３−Ｍは出力パケットバッファを示す。Ｌ個の入力パケットバッファ１１−１〜１１−Ｌは、入力ポートから入力したパケットを一時的に保持し、スケジューリングした後に、パケット交換部１２へ入力する。パケット交換部１２は、入力したパケットに示されるアドレス情報に従って、パケットを出力する出力ポートを決定し、決定された出力ポートに接続される出力パケットバッファへパケットを出力する。Ｍ個の出力パケットバッファ１３−１〜１３−Ｍは、パケット交換部１２から出力されたパケットを一時的に保持し、スケジューリングした後に出力ポートから出力する。
なお、パケット交換部１２が、その内部にパケットバッファを備えていてもよい。パケット交換部１２のパケットバッファは、例えば、パケット交換部１２の入力ポートから入出力ポートから出力される経路上のいずれかにおいて、パケットを一時的に保持するために使用される。また他の実施例では、入力パケットバッファ１１−１〜１１−Ｌ及び出力パケットバッファ１３−１〜１３−Ｍのいずれか又は両方を省いてもよく、パケット交換部１２内に、パケットバッファを集約してもよい。【００２６】
図６は、図５に示す入力パケットバッファ１１−１の第１構成例を説明する構成図である。他の入力パケットバッファ１１−２〜１１−Ｌや、出力パケットバッファ１３−１〜１３−Ｍや、パケット交換部内に設けられるパケットバッファも同様の構成であってよい。以下の示す、入力パケットバッファ１１−１の第２構成例〜第７構成例においても同様である。参照符号２１はキューを示し、参照符号２２はキュー長測定部を示し、参照符号２３はレート測定部を示し、参照符号２４は滞留時間予測部を示し、参照符号２５は移動平均演算部を示し、参照符号２６はパケット廃棄部を示し、参照符号Ｐはパケットを示す。入力パケットバッファ１１−１は、キュー２１、キュー長測定部２２、レート測定部２３、滞留時間予測部２４、移動平均演算部２５及びパケット廃棄部２６を備える。【００２７】
キュー２１は、入力パケットバッファ１１−１へ入力されたパケットを一時的に保持するための待ち行列であり、入力パケットを先入れ先出し方式で保持する。キュー長測定部２２は、キュー２１内に保持されているデータ量、すなわちキュー長ＬＱを測定する。キュー長測定部２２は、順次測定されるキュー長の測定値そのものに代えて、その加重移動平均値を測定結果として出力してもよい。加重移動平均値を用いることで突発的なキュー長変化が発生した際に、その影響を排除し、安定した制御を行うことが可能となる。レート測定部２３は、キュー２１から出力されるパケットの出力レートＲＯを測定する。【００２８】
滞留時間予測部２４は、測定されたキュー長ＬＱを出力レートＲＯで除することにより、現時点においてパケットがキュー２１内にどれくらい滞留するかの予測値ＴＦを決定する。すなわち滞留時間予測部２４は、予測値を、（予測値＝キュー長ＬＱ／出力レートＲＯ）により算出する。移動平均演算部２５は、滞留時間予測部２４が決定した滞留時間の予測値の加重移動平均値ＴＦを算出する。以下、滞留時間の予測値の加重移動平均値を「平均予測値ＴＦ」と示す。パケット廃棄部２６は、平均予測値ＴＦに基づいて、到着パケットをキュー２１に格納する前の廃棄処理を行う。なお、平均予測値ＴＦを求める他の方法として単純平均法、簡易指数平均法、最小二乗法などがある。これらの方法を移動平均演算部２５に適用することも可能である。【００２９】
図７は、開示のパケット廃棄方法の第１例を説明する方法である。オペレーションＳＢにおいてレート測定部２３は、キュー２１から出力されるパケットの出力レートＲＯを測定する。レート測定部２３による出力レートＲＯの測定処理の例は後述する。オペレーションＳＣにおいてキュー長測定部２２は、キュー２１のキュー長ＬＱを測定する。オペレーションＳＤにおいて滞留時間予測部２４は、（予測値＝キュー長ＬＱ／出力レートＲＯ）により、予測値を算出する。移動平均演算部２５は、滞留時間予測部２４が決定した滞留時間の平均予測値ＴＦを算出する。【００３０】
オペレーションＳＥにおいてパケット廃棄部２６は、移動平均演算部２５が算出した平均予測値ＴＦが、所定の滞留可能許容時間ＴＨＴを超えるか否かを判定する。平均予測値ＴＦが滞留可能許容時間ＴＨＴを超えないとき（オペレーションＳＥ：Ｎ）、入力パケットバッファ１１−１は処理をオペレーションＳＢに戻す。【００３１】
平均予測値ＴＦが滞留可能許容時間ＴＨＴを超えるとき（オペレーションＳＥ：Ｙ）、パケット廃棄部２６は処理をオペレーションＳＦへ移す。オペレーションＳＦにおいてパケット廃棄部２６は、到着したパケットをキュー２１に保持せずに廃棄する。すなわち、パケット廃棄部２６は、キュー２１におけるパケットの滞留時間の予測値に基づくテイルドロップ処理を行う。【００３２】
またオペレーションＳＧにおいてパケット廃棄部２６は、パケット廃棄についてこのパケットの送信元の装置に対して、スイッチ１０において輻輳が発生したことを明示的に通知する。パケット廃棄部２６は、例えばＴＣＰ／ＩＰの輻輳情報通知機能（Explicit Congestion Notification）に従って、明示的に輻輳の発生を送信元の装置に通知する。その後、入力パケットバッファ１１−１は処理をオペレーションＳＢに戻す。なお、別な実施の態様においては、上記オペレーションＳＢ乃至オペレーションＳＧの各オペレーションはステップであってもよい。【００３３】
本実施例によれば、輻輳が発生したときキュー２１内に滞留するパケットの滞留時間はほぼ滞留可能許容時間ＴＨＴ程度となるため、入力パケットバッファ１１−１において生じる遅延変動が低減される。【００３４】
ＴＣＰ制御では、再送タイムアウト時間を計測してパケットの再送制御が行われる。本実施例によれば、伝送経路に設けた入力パケットバッファにおける遅延変動が低減されるので、安定した再送制御が可能となり、パケットのスループット向上に資する。【００３５】
また、図４Ａ〜４Ｅを参照して説明したような、一度、テイルドロップが発生したときキューが空になるまで廃棄が継続する、バースト的な廃棄が抑制される。このためバースト的な廃棄により生じていた、ＴＣＰフローが一斉にレートを下げてしまう現象を回避することが可能となる。【００３６】
図８は、開示のパケット廃棄方法の第２例を説明する方法である。オペレーションＳＢ〜ＳＤにより、図７に示すオペレーションＳＢ〜ＳＤと同様にして、平均予測値ＴＦが決定される。オペレーションＳＨにおいてパケット廃棄部２６は、平均予測値ＴＦに応じて、入力パケットの廃棄率を以下の通り決定する。ここで廃棄率とは、所定時間当たりの入力パケットの全数に対する、パケット廃棄部２６により廃棄されるパケット数の割合である。【００３７】
パラメータＭｉｎＴｈを、入力パケットを廃棄し始める滞留時間の予測値の閾値（廃棄開始時予測値）とする。パラメータＭａｘＰを、入力パケットの廃棄率の最大値（最大廃棄率）とする。パラメータＭａｘＴｈを、廃棄率が最大廃棄率ＭａｘＰに至る滞留時間（最大廃棄時予測値）とする。【００３８】
平均予測値ＴＦがＭｉｎＴｈ以下であるとき、パケット廃棄部２６は正常に転送可能なパケットの廃棄率を０にする。すなわち、ＴＦ≦ＭｉｎＴｈのとき入力パケットは廃棄されない。平均予測値ＴＦがＭａｘＴｈ以上のとき、パケット廃棄部２６は、廃棄率をＭａｘＰにする。平均予測値ＴＦがＭｉｎＴｈより大きくＭａｘＴｈ未満であるとき、パケット廃棄部２６は、廃棄率を、（廃棄率＝ＭａｘＰ×（平均予測値ＴＦ−ＭｉｎＴｈ）／（ＭａｘＴｈ−ＭｉｎＴｈ））により決定する。【００３９】
オペレーションＳＩにおいてパケット廃棄部２６は、到着したパケットをＳＨにて決定した廃棄率で廃棄する。すなわち、パケット廃棄部２６は、キュー２１におけるパケットの滞留時間の予測値に基づくＷＲＥＤを行う。オペレーションＳＪにおいてパケット廃棄部２６は、平均予測値ＴＦがＭｉｎＴｈより大きいか否かを判定することにより、輻輳が発生したか否かを判定する。パケット廃棄部２６が輻輳が発生していないと判定したとき（オペレーションＳＪ：Ｎ）、入力パケットバッファ１１−１は処理をオペレーションＳＢに戻す。【００４０】
輻輳が発生したと判定したとき（オペレーションＳＪ：Ｙ）、オペレーションＳＧにおいてパケット廃棄部２６は、廃棄パケットの送信元の装置に対して、スイッチ１０において輻輳が発生したことを明示的に通知する。その後、入力パケットバッファ１１−１は処理をオペレーションＳＢに戻す。なお、別な実施の態様においては、上記オペレーションＳＢ乃至オペレーションＳＪの各オペレーションはステップであってもよい。【００４１】
本実施例によれば、輻輳が発生したとき、平均予測値ＴＦが廃棄開始時予測値ＭｉｎＴｈを超えた頃からパケットの廃棄が開始され、パケット廃棄を検知した送信元装置からのパケットのフローのレートが低減される。この結果、平均予測値ＴＦが過度に大きくなると予想されるときには、キュー２１内にパケットが蓄積されないので、パケットの滞留時間は、上記各パラメータに応じて定まる設定値に近づくように制御される。この結果、入力パケットバッファ１１−１において生じる遅延変動が低減される。【００４２】
図９は、図６に示すレート測定部２３の第１構成例を説明する構成図である。本実施例では、入力パケットバッファ１１−１は入力パケットを一時的に保持するためのＮ個のキュー２１−１〜２１−Ｎを有している。キュー２１−１〜２１−Ｎは、入力パケットバッファ１１−１へ入力されたパケットを一時的に保持するための待ち行列であり、宛先、ユーザ、アプリケーションなどによって分類された入力パケットを、各分類ごとに先入れ先出し方式で保持する。参照符号３０はレート測定制御部を示し、参照符号３１は送出累積量測定部を示し、参照符号３２は測定値記憶部を示し、参照符号３３は送出量算出部を示し、参照符号３４はレート算出部を示す。レート測定部２３は、レート測定制御部３０と、送出累積量測定部３１と、測定値記憶部３２と、送出量算出部３３と、レート算出部３４を備える。【００４３】
レート測定制御部３０は、Ｎ個のキュー２１−１〜２１−Ｎのそれぞれを、パケットの出力レートを測定する対象となるキューとして、一定の測定周期Ｔ０で周期的に順次選択する。レート測定制御部３０は、選択したキューを、送出累積量測定部３１及び測定値記憶部３２へ通知する。送出累積量測定部３１は、各キュー２１−１〜２１−Ｎから送出されるデータ量をカウントしてその累積量を求める。レート測定制御部３０から測定対象のキューを通知されたとき、その測定対象のキューから送出されたデータ量の累積量を、測定値記憶部３２及び送出量算出部３３へ出力する。【００４４】
測定値記憶部３２は、送出累積量測定部３１から出力された送出データ量の累積量を、各キュー２１−１〜２１−Ｎ毎に記憶する。また、レート測定制御部３０から測定対象のキューを通知されたとき、前回の測定時に記憶した送出データ量の累積量を送出量算出部３３へ出力する。送出量算出部３３は、今回測定した送出データ量の累積量を送出累積量測定部３１から受信し、前回測定した送出データ量の累積量を測定値記憶部３２から受信する。送出量算出部３３は、前回測定時から今回測定時までの間に対象キューから送出された送出データ量（＝今回測定した送出データ量の累積値−前回測定した送出データ量の累積値）を算出する。送出量算出部３３は、算出した送出データ量をレート算出部３４へ出力する。【００４５】
レート算出部３４は、送出量算出部３３から入力した送出データ量から、測定対象のキューから出力されるパケットの出力レートＲＯ（＝送出データ量／測定周期Ｔ０）を算出し、出力する。レート算出部３４は、逐次算出される出力レートＲＯに代えて、出力レートＲＯの加重移動平均値を出力してもよい。加重移動平均値を用いることで突発的なレート変化が発生した際に、その影響を排除し、安定した制御を行うことが可能となる。なお、加重移動平均値以外の平均値を求める他の方法として単純平均法、簡易指数平均法、最小二乗法などを適用してもよい。【００４６】
図１０は、開示のレート測定方法の第１例を説明する方法である。図７及び図８に示すオペレーションＳＢにおいて測定される出力レートは、図１０を参照して以下に説明するレート測定方法によって測定することができる。【００４７】
レート測定制御部３０は、Ｎ個のキュー２１−１〜２１−Ｎのそれぞれを、パケットの出力レートを測定する対象となるキューとして、一定の測定周期Ｔ０で周期的に順次選択する。選択された各キューについて、送出累積量測定部３１、測定値記憶部３２、送出量算出部３３及びレート算出部３４が、パケットの出力レートを算出することにより、繰り返しループＳＢＡ〜ＳＢＦが実行される。【００４８】
送出累積量測定部３１は、各キュー２１−１〜２１−Ｎから送出されるデータ量をカウントしてその累積量を求める。オペレーションＳＢＢにおいて送出累積量測定部３１は、選択された測定対象のキューから送出されたデータ量の累積量を、測定値記憶部３２及び送出量算出部３３へ出力する。オペレーションＳＢＣにおいて測定値記憶部３２は、送出累積量測定部３１から出力された送出データ量の累積量を、各キュー２１−１〜２１−Ｎ毎に記憶する。【００４９】
オペレーションＳＢＤにおいて測定値記憶部３２は、測定対象のキューについて前回の測定時に記憶した送出データ量の累積量を送出量算出部３３へ出力する。送出量算出部３３は、前回測定時から今回測定時までの間に対象キューから送出された送出データ量を算出する。オペレーションＳＢＥにおいてレート算出部３４は、送出量算出部３３から入力した送出データ量から、測定対象のキューから出力されるパケットの出力レートＲＯを算出する。その後、レート測定制御部３０は、次のキューを選択して処理をオペレーションＳＢＢに戻す。なお、別な実施の態様においては、上記オペレーションＳＢＡ乃至オペレーションＳＢＦの各オペレーションはステップであってもよい。【００５０】
本実施例では、上記の通り、一定間隔で周期的に各キューの出力レートを測定することにより、測定間隔の算出を省略することができる。このため処理内容が簡略化することができ、多数のキューに対するリアルタイムな測定処理を短時間に行うことが可能となる。【００５１】
図１１は、図６に示すレート測定部２３の第２構成例を説明する構成図である。本実施例においても、入力パケットバッファ１１−１は入力パケットを一時的に保持するためのＮ個のキュー２１−１〜２１−ＮをＮ個有している。参照符号４０は読み出しタイミング検出部を示し、参照符号４１は時刻測定部を示し、参照符号４２は時刻記憶部を示し、参照符号４３は測定間隔算出部を示す。レート測定部２３は、レート測定制御部３０と、送出累積量測定部３１と、測定値記憶部３２と、送出量算出部３３と、レート算出部３４と、読み出しタイミング検出部４０と、時刻測定部４１と、時刻記憶部４２と、測定間隔算出部４３を備える。【００５２】
送出累積量測定部３１、測定値記憶部３２及び送出量算出部３３の機能は、図９を参照して説明したそれぞれの機能と同様である。読み出しタイミング検出部４０は、各キュー２１−１〜２１−Ｎのいずれかからデータの読み出しがあったとき、データが読み出されたキューをレート測定制御部３０に通知する。レート測定制御部３０は、通知されたキューを、パケットの出力レートを測定する対象となるキューとして、送出累積量測定部３１、測定値記憶部３２及び時刻記憶部４２へ通知する。【００５３】
時刻測定部４１は現在時刻を測定する。レート測定制御部３０から測定対象のキューを通知されたとき、時刻記憶部４２は、測定対象のキューの測定時刻として現在時刻を記憶するとともに、記憶されている前回の測定時刻を測定間隔算出部４３へ出力する。測定間隔算出部４３は、時刻記憶部４２から出力された前回の測定時刻と現在時刻との差から、測定対象のキューについて測定が行われた測定間隔Ｔ１を算出する。測定間隔算出部４３は、算出した測定間隔Ｔ１をレート算出部３４へ出力する。【００５４】
レート算出部３４は、送出量算出部３３から入力した送出データ量と、測定間隔算出部４３から入力した測定間隔Ｔ１から、測定対象のキューから出力されるパケットの出力レートＲＯ（＝送出データ量／測定間隔Ｔ１）を算出し、出力する。レート算出部３４は、逐次算出される出力レートＲＯに代えて、出力レートＲＯの加重移動平均値を出力してもよい。なお、加重移動平均値以外の平均値を求める他の方法として単純平均法、簡易指数平均法、最小二乗法などを適用してもよい。【００５５】
図１２は、開示のレート測定方法の第２例を説明する方法である。図７及び図８に示すオペレーションＳＢにおいて測定される出力レートは、図１２を参照して以下に説明するレート測定方法によって測定することができる。オペレーションＳＣＡにおいて読み出しタイミング検出部４０は、各キュー２１−１〜２１−Ｎのいずれかからデータの読み出しがあったか否かを検出する。データの読み出しが検出されなかったとき（オペレーションＳＣＡ：Ｎ）、レート測定部２３は処理をオペレーションＳＣＡに戻す。【００５６】
データの読み出しが検出されたとき（オペレーションＳＣＡ：Ｙ）、オペレーションＳＣＢにおいて送出累積量測定部３１は、測定対象となる、読み出しが検出されたキューから読み出されたデータ量をカウントしてその累積量を求める。送出累積量測定部３１は、測定対象のキューから読み出されたデータ量の累積量を、測定値記憶部３２及び送出量算出部３３へ出力する。オペレーションＳＣＣにおいて測定値記憶部３２は、送出累積量測定部３１から出力されたデータ量の累積量を、各キュー２１−１〜２１−Ｎ毎に記憶する。【００５７】
オペレーションＳＣＤにおいて測定値記憶部３２は、測定対象のキューについて前回の測定時に記憶した読み出しデータ量の累積量を送出量算出部３３へ出力する。送出量算出部３３は、前回測定時から今回測定時までの間に対象キューから読み出されたデータ量を、このキューから送出される送出データ量として算出する。【００５８】
オペレーションＳＣＥにおいて時刻測定部４１は、現在時刻を測定する。オペレーションＳＣＦにおいて時刻記憶部４２は、測定対象のキューの測定時刻として現在時刻を記憶するとともに、記憶されている前回の測定時刻を測定間隔算出部４３へ出力する。オペレーションＳＣＧにおいて測定間隔算出部４３は、時刻記憶部４２から出力された前回の測定時刻と現在時刻との差から、測定対象のキューについて測定が行われた測定間隔Ｔ１を算出する。【００５９】
オペレーションＳＣＨにおいて、レート算出部３４は、送出量算出部３３から入力した送出データ量と、測定間隔算出部４３から入力した測定間隔Ｔ１から、測定対象のキューから出力されるパケットの出力レートＲＯを算出する。レート算出部３４は、逐次算出される出力レートＲＯに代えて、出力レートＲＯの加重移動平均値を出力してもよい。加重移動平均値を用いることで突発的なレート変化が発生した際に、その影響を排除し、安定した制御を行うことが可能となる。なお、別な実施の態様においては、上記オペレーションＳＣＡ乃至オペレーションＳＣＨの各オペレーションはステップであってもよい。【００６０】
本実施例では、キューからのデータの読み出し時に、データの読み出し量に基づいてキューの出力レートを測定することとした。これに代えて、キューへデータの書き込みを検出するデータ書き込みタイミング検出手段を設けて、データ書き込み時にデータの書き込み量に基づいて出力レートを測定してもよい。【００６１】
本実施例では、キューからのデータの読み出し時又は、キューへのデータの書き込み時に各キューの出力レートを測定することにより、各キューの出力レートの測定値が変動するタイミングで、これらの測定値をリアルタイムで決定することができる。このため、出力レートの変動に対する追従性を向上することができる。また、データの読み出しや書き込みが発生しない場合に、無駄な測定処理を省略することができる。【００６２】
図１３は、図５に示す入力パケットバッファ１１−１の第２構成例を説明する構成図である。参照符号２７はキュー長記憶部を示し、参照符号２８は滞留時間測定部を示す。他の参照符号は、図６において同じ参照符号を付した構成要素と同様である。入力パケットバッファ１１−１は、キュー２１、キュー長測定部２２、滞留時間予測部２４、移動平均演算部２５、パケット廃棄部２６、キュー長記憶部２７及び滞留時間測定部２８を備える。【００６３】
キュー長測定部２２は、パケット毎に、各パケットがキュー２１に到着したときのキュー長（以下「到着時キュー長」と示す）と、先頭パケットをキュー２１から読み出すときのキュー長（以下「現キュー長」と示す）を測定する。キュー長測定部２２は、到着時キュー長を、パケット毎にキュー長記憶部２７に記憶する。【００６４】
滞留時間測定部２８は、パケット毎に、その到着時刻とキュー２１からの読み出し時刻との差を算出することにより、キュー２１内における各パケットの滞留時間を測定する。滞留時間予測部２４は、各パケット毎に、到着時キュー長に対する現キュー長の変化率（現キュー長／到着時キュー長）を算出し、この変化率とこのパケットの滞留時間との積を滞留時間の予測値（予測値＝滞留時間×現キュー長／到着時キュー長）として決定する。【００６５】
なお、キュー長測定部２２は、到着時キュー長及び現キュー長を測定する際に、順次測定される測定値そのものに代えて、その荷重移動平均値を測定結果として出力してよい。このように加重移動平均値を測定結果として用いることで、突発的なキュー長の変化により滞留時間の予測値が不安定になることが回避される。なお、加重移動平均値以外の平均値を求める他の方法として単純平均法、簡易指数平均法、最小二乗法などを適用してもよい。【００６６】
図１４は、開示のパケット廃棄方法の第３例を説明する方法である。オペレーションＳＤＡにおいてキュー長測定部２２は、パケット到着時におけるキュー２１のキュー長、すなわち到着時キュー長を測定する。オペレーションＳＤＢにおいてキュー長測定部２２は、到着時キュー長をキュー長記憶部２７に記憶する。【００６７】
オペレーションＳＤＣにおいて滞留時間測定部２８は、パケットの到着時刻とキュー２１読み出し時刻の差から、キュー２１内における各パケットの滞留時間を測定する。オペレーションＳＤＤにおいてキュー長測定部２２は、オペレーションＳＤＡにおいて到着時キュー長を測定したパケットについて、このパケットをキュー２１から読み出した時のキュー長、すなわち現キュー長を測定する。【００６８】
オペレーションＳＤＥにおいて滞留時間予測部２４は、各パケット毎に、到着時キュー長に対する現キュー長の変化率（現キュー長／到着時キュー長）を算出する。オペレーションＳＤＦにおいて滞留時間予測部２４は、オペレーションＳＤＥで測定した変化率とパケットの滞留時間との積を滞留時間の予測値として決定する。移動平均演算部２５は、滞留時間予測部２４が決定した滞留時間の平均予測値ＴＦを算出する。【００６９】
オペレーションＳＤＧにおいてパケット廃棄部２６は、移動平均演算部２５が算出した平均予測値ＴＦが、所定の滞留可能許容時間ＴＨＴを超えるか否かを判定する。平均予測値ＴＦが滞留可能許容時間ＴＨＴを超えないとき（オペレーションＳＤＧ：Ｎ）、入力パケットバッファ１１−１は処理をオペレーションＳＤＡに戻す。【００７０】
平均予測値ＴＦが滞留可能許容時間ＴＨＴを超えるとき（オペレーションＳＤＧ：Ｙ）、パケット廃棄部２６は処理をオペレーションＳＤＨへ移す。オペレーションＳＤＨにおいてパケット廃棄部２６は、到着したパケットをキュー２１に保持せずに廃棄する。すなわち、パケット廃棄部２６は滞留時間の予測値に基づくテイルドロップ処理を行う。またオペレーションＳＤＩにおいてパケット廃棄部２６は、パケットを廃棄するとき、このパケットの送信元の装置に対して、スイッチ１０において輻輳が発生したことを明示的に通知する。その後、入力パケットバッファ１１−１は処理をオペレーションＳＢＡに戻す。【００７１】
なお、本実施例においてパケット廃棄部２６は、平均予測値ＴＦを滞留可能許容時間ＴＨＴと比較して輻輳判定を行った。これに代えてパケット廃棄部２６は、図８に示すオペレーションＳＨ、ＳＩ、ＳＪ及びＳＧの処理と同様に、平均予測値ＴＦに応じた入力パケットの廃棄率を決定することによってＷＲＥＤを行ってもよい。なお、別な実施の態様においては、上記オペレーションＳＤＡ乃至オペレーションＳＤＩの各オペレーションはステップであってもよい。【００７２】
本実施例によれば、滞留時間予測部２４がキュー長の変化率に基づいて予測値を計算することで、キュー長の変化傾向を考慮した滞留時間の予測を行うことが可能となる。【００７３】
図１５は、図５に示す入力パケットバッファ１１−１の第３構成例を説明する構成図である。参照符号５０はキュー長閾値決定部を示し、参照符号５１はパケット廃棄制御部を示し、参照符号５２はヘッドドロップ処理部５２を示す。【００７４】
入力パケットバッファ１１−１は、パケット判別部２と、パケット分配部４と、Ｎ個のキュー２１−１〜２１−Ｎと、キュー長測定部２２と、パケット廃棄部２６とを備える。入力パケットバッファ１１−１は、レート測定制御部３０と、送出累積量測定部３１と、測定値記憶部３２と、送出量算出部３３を備える。入力パケットバッファ１１−１は、キュー長閾値決定部５０と、パケット廃棄制御部５１と、ヘッドドロップ処理部５２を備える。【００７５】
レート測定制御部３０と、送出累積量測定部３１と、測定値記憶部３２及び送出量算出部３３の機能は、図９を参照して説明したそれぞれの機能と同様である。すなわち、レート測定制御部３０と、送出累積量測定部３１と、測定値記憶部３２及び送出量算出部３３は、各キュー２１−１〜２１−Ｎについて、所定の測定周期Ｔ０毎に、各キューから出力される送出データ量を測定する。【００７６】
パケット判別部２は、入力パケットが、送信元のユーザについて定めた入力帯域幅に関する規定を遵守しているか否かを判別し、規定を遵守しているパケットとそうでないパケットに分類する。パケット分配部４は、入力パケットの宛先、ユーザ、アプリケーションなどに応じて、入力パケットを、キュー２１−１〜２１−Ｎのいずれかに分配する。ヘッドドロップ処理部５２は、各パケットのキュー２１−１〜２１−Ｎでの滞留時間を測定する。基準値を超えてパケットがキュー内に滞留した場合、ヘッドドロップ処理部５２は、入力帯域幅に関する規定を遵守しているか否かに関わらずパケットをキューの先頭から廃棄する。【００７７】
キュー長閾値決定部５０は、各キュー２１−１〜２１−Ｎについて、送出量算出部３３が算出した送出データ量を受信する。キュー長閾値決定部５０は、各キュー２１−１〜２１−Ｎについて、送出量算出部３３から入力した送出データ量と、所定の定数である滞留可能許容時間ＴＨＴと、所定の測定周期Ｔ０に応じて、キュー長閾値ＴＨＱ（キュー長閾値ＴＨＱ＝滞留可能許容時間ＴＨＴ／測定周期Ｔ０×送出データ量）を算出する。キュー長閾値決定部５０は、キュー長閾値ＴＨＱをパケット廃棄制御部５１へ出力する。【００７８】
パケット廃棄制御部５１は、キュー長測定部２２が各キュー２１−１〜２１−Ｎについて測定したキュー長ＬＱが、キュー長閾値決定部５０が各キュー２１−１〜２１−Ｎについて算出したキュー長閾値ＴＨＱを超えるか否かを判定する。各キュー２１−１〜２１−Ｎからのパケットの出力レートは、（送出データ量／測定周期Ｔ０）と等しいため、キュー長ＬＱがキュー長閾値ＴＨＱよりも長い場合、滞留時間の予測値（キュー長ＬＱ／出力レート）が滞留可能許容時間ＴＨＴよりも長くなる。パケット廃棄制御部５１は、パケット廃棄部２６に対して、キュー長ＬＱがキュー長閾値ＴＨＱを超えるキューについてテイルドロップを行う指示を出力する。【００７９】
パケット廃棄部２６は、テイルドロップが行われるべきキューへ保持されることを予定されている、入力帯域幅に関する規定を遵守していないパケットが入力されたとき、このパケットを、キューに保持せずに廃棄する。パケット廃棄部２６は、テイルドロップが行われるべきキューへ保持することを予定されているパケットであっても、入力帯域幅に関する規定を遵守しているパケットが入力されたとき、このパケットをキューに保持する。【００８０】
図１６は、開示のパケット廃棄方法の第４例を説明する方法である。オペレーションＳＥＡにおいてパケット判別部２は、入力パケットが、送信元のユーザについて定めた入力帯域幅に関する規定を遵守しているか否かを判別し、規定を遵守しているパケットとそうでないパケットに分類する。パケット廃棄部２６は、入力帯域幅に関する規定を遵守しているパケットをキューに保持する。【００８１】
以下、各キュー２１−１〜２１−Ｎのそれぞれについて、繰り返しループＳＥＢ〜ＳＦＢ繰り返す。繰り返しループＳＥＢ〜ＳＦＢにて繰り返される各処理において、レート測定制御部３０は、Ｎ個のキュー２１−１〜２１−Ｎのそれぞれを、パケットの出力レートを測定する対象となるキューとして、一定の測定周期Ｔ０で周期的に順次選択する。【００８２】
送出累積量測定部３１は、各キュー２１−１〜２１−Ｎから送出されるデータ量をカウントしてその累積量を求める。オペレーションＳＥＣにおいて送出累積量測定部３１は、選択された測定対象のキューから送出されたデータ量の累積量を、測定値記憶部３２及び送出量算出部３３へ出力する。オペレーションＳＥＤにおいて測定値記憶部３２は、送出累積量測定部３１から出力された送出データ量の累積量を、各キュー２１−１〜２１−Ｎ毎に記憶する。【００８３】
オペレーションＳＥＥにおいて測定値記憶部３２は、測定対象のキューについて前回の測定時に記憶した送出データ量の累積量を送出量算出部３３へ出力する。送出量算出部３３は、前回測定時から今回測定時までの間に対象キューから送出された送出データ量を算出する。オペレーションＳＥＦにおいてキュー長閾値決定部５０は、測定対象のキューについて、送出量算出部３３から入力した送出データ量と、所定の定数である滞留可能許容時間ＴＨＴと、所定の測定周期Ｔ０に応じて、キュー長閾値ＴＨＱを算出する。【００８４】
オペレーションＳＥＧにおいて、オペレーションＳＣにおいてキュー長測定部２２は、測定対象となるキューのキュー長ＬＱを測定する。オペレーションＳＥＨにおいてパケット廃棄制御部５１は、測定対象となるキューのキュー長ＬＱが、キュー長閾値決定部５０が算出したキュー長閾値ＴＨＱを超えるか否かを判定する。キュー長ＬＱがキュー長閾値ＴＨＱを超えないとき（オペレーションＳＥＨ：Ｎ）、入力パケットバッファ１１−１は処理をオペレーションＳＦＡへ移す。【００８５】
キュー長ＬＱがキュー長閾値ＴＨＱを超えるとき（オペレーションＳＥＨ：Ｙ）、オペレーションＳＥＩにおいてパケット廃棄部２６は、入力帯域幅に関する規定を遵守していない到着パケットを、対象のキューに保持せずに破棄する。オペレーションＳＥＪにおいてパケット廃棄部２６は、廃棄したパケットの送信元の装置に対して、スイッチ１０において輻輳が発生したことを明示的に通知する。入力パケットバッファ１１−１は処理をオペレーションＳＦＡに移す。【００８６】
オペレーションＳＦＡにおいてヘッドドロップ処理部５２は、測定対象となるキュー内に保持されたパケットの滞留時間を測定する。基準値を超えてパケットがキュー内に滞留した場合、ヘッドドロップ処理部５２は、入力帯域幅に関する規定を遵守しているか否かに関わらずパケットをキューの先頭から廃棄する。その後、入力パケットバッファ１１−１は処理をオペレーションＳＥＡに戻す。なお、別な実施の態様においては、上記オペレーションＳＥＡ乃至オペレーションＳＦＢの各オペレーションはステップであってもよい。【００８７】
ヘッドドロップ処理部５２が、パケットを廃棄するか否かを判定するために、パケットの滞留時間と比較する基準値は、滞留可能許容時間ＴＨＴよりも長い値を使用してよい。このような値を使用することにより、入力帯域幅に関する規定を遵守していないパケットを、入力帯域幅に関する規定を遵守しているパケットよりも先に破棄することができる。【００８８】
第３構成例によれば、一定の所定周期Ｔ０で各キューからの送出データ量を測定する。これにより、キュー長閾値ＴＨＱの計算式（キュー長閾値ＴＨＱ＝滞留可能許容時間／測定周期Ｔ０×送出データ量）において、係数（滞留可能許容時間／測定周期Ｔ０）を定数とすることができる。このため、キュー長閾値ＴＨＱの計算回路を簡単化することができる。【００８９】
なお、上記構成例において、ヘッドドロップ処理部５２を省略してもよい。このとき、入力帯域幅に関する規定を遵守しているか否かに関わらず、全てのパケットをパケット廃棄部２６による廃棄の対象としてよい。また、入力帯域幅に関する規定を遵守しているか否かに応じて、滞留可能許容時間の長さを異ならせてもよい。例えば、入力帯域幅に関する規定を遵守しているパケットを廃棄するか否かを判定する場合には、遵守していないパケットの場合と比べて、比較的長い滞留可能許容時間を用いてもよい。以下の第４構成例〜第７構成例においても同様である。【００９０】
図１７は、図５に示す入力パケットバッファ１１−１の第４構成例を説明する構成図である。入力パケットバッファ１１−１は、パケット判別部２と、パケット分配部４と、Ｎ個のキュー２１−１〜２１−Ｎと、キュー長測定部２２と、パケット廃棄部２６とを備える。入力パケットバッファ１１−１は、レート測定制御部３０と、送出累積量測定部３１と、測定値記憶部３２と、送出量算出部３３を備える。入力パケットバッファ１１−１は、読み出しタイミング検出部４０と、時刻測定部４１と、時刻記憶部４２と、測定間隔算出部４３を備える。入力パケットバッファ１１−１は、キュー長閾値決定部５０と、パケット廃棄制御部５１と、ヘッドドロップ処理部５２を備える。【００９１】
レート測定制御部３０と、送出累積量測定部３１と、測定値記憶部３２と、送出量算出部３３と、読み出しタイミング検出部４０と、時刻測定部４１と、時刻記憶部４２と、測定間隔算出部４３の機能は、図１１を参照して説明したそれぞれの機能と同様である。読み出しタイミング検出部４０が、各キュー２１−１〜２１−Ｎのいずれかからデータの読み出しがあったことを検出したとき、レート測定制御部３０は、読み出しがあったキューを、送出データ量の測定対象となるキューとして指定する。送出累積量測定部３１と、測定値記憶部３２と、送出量算出部３３は、測定対象となるキューについて今回の測定時と前回の測定時の間にキューから読み出されたデータ量を、送出データ量として算出する。時刻測定部４１と、時刻記憶部４２と、測定間隔算出部４３は、今回の測定時と前回の測定時の間の測定間隔を算出する。【００９２】
キュー長閾値決定部５０は、各キュー２１−１〜２１−Ｎについて、送出量算出部３３が算出した送出データ量を受信する。キュー長閾値決定部５０は、各キュー２１−１〜２１−Ｎについて、送出量算出部３３から入力した送出データ量と、測定間隔算出部４３から入力した測定間隔Ｔ１に応じて、キュー長閾値ＴＨＱ（キュー長閾値ＴＨＱ＝滞留可能許容時間ＴＨＴ／測定間隔Ｔ１×送出データ量）を算出する。キュー長閾値決定部５０は、キュー長閾値ＴＨＱをパケット廃棄制御部５１へ出力する。【００９３】
パケット廃棄制御部５１、パケット廃棄部２６、パケット判別部２、パケット分配部４及びヘッドドロップ処理部５２の機能は、図１５を参照して説明したそれぞれの機能と同様である。【００９４】
図１８は、開示のパケット廃棄方法の第５例を説明する方法である。オペレーションＳＧＡにおいてパケット判別部２は、入力パケットが、送信元のユーザについて定めた入力帯域幅に関する規定を遵守しているか否かを判別し、規定を遵守しているパケットとそうでないパケットに分類する。パケット廃棄部２６は、入力帯域幅に関する規定を遵守しているパケットをキューに保持する。【００９５】
オペレーションＳＧＢにおいて読み出しタイミング検出部４０は、各キュー２１−１〜２１−Ｎのいずれかからデータの読み出しがあったか否かを検出する。データの読み出しが検出されなかったとき（オペレーションＳＧＢ：Ｎ）、入力パケットバッファ１１−１は処理をオペレーションＳＧＢに戻す。【００９６】
データの読み出しが検出されたとき（オペレーションＳＧＢ：Ｙ）、オペレーションＳＧＣにおいて送出累積量測定部３１は、読み出しが検出された測定対象となるキューから読み出されたデータ量をカウントしてその累積量を求める。送出累積量測定部３１は、測定対象のキューから読み出されたデータ量の累積量を、測定値記憶部３２及び送出量算出部３３へ出力する。オペレーションＳＧＤにおいて測定値記憶部３２は、送出累積量測定部３１から出力されたデータ量の累積量を、各キュー２１−１〜２１−Ｎ毎に記憶する。【００９７】
オペレーションＳＧＥにおいて測定値記憶部３２は、測定対象のキューについて前回の測定時に記憶した読み出しデータ量の累積量を送出量算出部３３へ出力する。送出量算出部３３は、前回測定時から今回測定時までの間に対象キューから読み出されたデータ量を、このキューから送出される送出データ量として算出する。【００９８】
オペレーションＳＧＦにおいて時刻測定部４１は、現在時刻を測定する。オペレーションＳＧＧにおいて時刻記憶部４２は、測定対象のキューの測定時刻として現在時刻を記憶するとともに、記憶されている前回の測定時刻を測定間隔算出部４３へ出力する。オペレーションＳＧＨにおいて測定間隔算出部４３は、時刻記憶部４２から出力された前回の測定時刻と現在時刻との差から、測定対象のキューについて測定が行われた測定間隔Ｔ１を算出する。【００９９】
オペレーションＳＧＩにおいてキュー長閾値決定部５０は、測定対象のキューについて、所定の定数である滞留可能許容時間ＴＨＴと、送出量算出部３３から入力した送出データ量と、測定間隔算出部４３から入力した測定間隔Ｔ１に応じて、キュー長閾値ＴＨＱを算出する。以下に続くオペレーションＳＧＪ〜ＳＨＤの処理は、図１６に示すオペレーションＳＥＧ〜ＳＦＡと同じである。オペレーションＳＨＤの後、入力パケットバッファ１１−１は処理をオペレーションＳＧＡに戻す。なお、別な実施の態様においては、上記オペレーションＳＧＡ乃至オペレーションＳＨＤの各オペレーションはステップであってもよい。【０１００】
なお本実施例では、キューからのデータの読み出し時に、データの読み出し量に基づいてキューからの送出データ量を測定することとした。これに代えて、キューへデータの書き込みを検出するデータ書き込みタイミング検出手段を設けて、データ書き込み時にデータの書き込み量に基づいてキューからの送出データ量を測定してもよい。以下に示す第６実施例においても同様である。【０１０１】
第４構成例によれば、キューからのデータの読み出し時又は、キューへのデータの書き込み時に、キュー長閾値ＴＨＱを決定することにより、各キューへのトラヒックが実際に生じたタイミングで、これらのキュー長閾値ＴＨＱをリアルタイムで決定することができる。このため、トラヒック量の変動に対する追従性を向上することができる。また、データの読み出しや書き込みが発生しない場合に、無駄な測定処理を省略することができる。【０１０２】
図１９は、図５に示す入力パケットバッファ１１−１の第５構成例を説明する構成図である。入力パケットバッファ１１−１は、パケット判別部２と、パケット分配部４と、Ｎ個のキュー２１−１〜２１−Ｎと、キュー長測定部２２と、滞留時間予測部２４と、パケット廃棄部２６とを備える。入力パケットバッファ１１−１は、レート測定制御部３０と、送出累積量測定部３１と、測定値記憶部３２と、送出量算出部３３を備える。入力パケットバッファ１１−１は、読み出しタイミング検出部４０と、時刻測定部４１と、時刻記憶部４２と、測定間隔算出部４３を備える。入力パケットバッファ１１−１は、パケット廃棄制御部５１と、ヘッドドロップ処理部５２を備える。【０１０３】
レート測定制御部３０と、パケット判別部２と、パケット分配部４と、送出累積量測定部３１と、測定値記憶部３２と、送出量算出部３３と、ヘッドドロップ処理部５２は、図１５に示すそれぞれの要素と同様である。キュー長測定部２２は、レート測定制御部３０により選択された、測定対象となるキューについてキュー長を測定する。滞留時間予測部２４は、キュー長測定部２２により測定されたキュー長と、送出量算出部３３により測定された測定対象のキューのデータ送出量と、測定周期Ｔ０に応じて、滞留時間の予測値ＴＦ（予測値ＴＦ＝キュー長×測定周期Ｔ０／データ送出量）を算出する。滞留時間予測部２４は、この予測値ＴＦそのものに代えて、その加重移動平均値を予測値ＴＦとして出力してよい。なお、加重移動平均値以外の平均値を求める他の方法として単純平均法、簡易指数平均法、最小二乗法などを適用してもよい。【０１０４】
パケット廃棄制御部５１は、滞留時間の予測値ＴＦに基づいて、入力パケットの廃棄率を決定する。廃棄率の決定方法は、図８を参照して説明した方法と同様であってよい。パケット廃棄部２６は、廃棄率が決定されたキューへ保持されることが予定されている、入力帯域幅に関する規定を遵守していないパケットが入力されたとき、このパケットを、パケット廃棄制御部５１により決定された廃棄率で廃棄する。【０１０５】
図２０は、開示のパケット廃棄方法の第６例を説明する方法である。オペレーションＳＩＡにおいて、パケット判別部２は、入力パケットが、送信元のユーザについて定めた入力帯域幅に関する規定を遵守しているか否かを判別し、規定を遵守しているパケットとそうでないパケットに分類する。パケット廃棄部２６は、入力帯域幅に関する規定を遵守しているパケットをキューに保持する。【０１０６】
以下、各キュー２１−１〜２１−Ｎのそれぞれについて、繰り返しループＳＩＢ〜ＳＪＣを繰り返す。繰り返しループＳＩＢ〜ＳＪＣにて繰り返される各処理において、レート測定制御部３０は、Ｎ個のキュー２１−１〜２１−Ｎのそれぞれを、パケットの出力レートを測定する対象となるキューとして、一定の測定周期Ｔ０で周期的に順次選択する。【０１０７】
オペレーションＳＩＣ〜オペレーションＳＩＥにおいて、図１６に示すオペレーションＳＥＣ〜オペレーションＳＥＥの処理と同様の処理にて、対象となるキューの送出データ量が算出される。オペレーションＳＩＦにおいてキュー長測定部２２は、対象となるキューについてキュー長を測定する。オペレーションＳＩＧにおいて滞留時間予測部２４は、キュー長測定部２２により測定されたキュー長と、送出量算出部３３により測定された測定対象のキューのデータ送出量と、測定周期Ｔ０に応じて、測定対象のキューについて滞留時間の予測値ＴＦを算出する。【０１０８】
オペレーションＳＩＨにおいてパケット廃棄制御部５１は、滞留時間の予測値ＴＦに基づいて、入力パケットの廃棄率を決定する。オペレーションＳＩＩにおいてパケット廃棄部２６は、対象となるキューへ保持されることが予定されている、入力帯域幅に関する規定を遵守していないパケットが入力されたとき、このパケットを、オペレーションＳＩＨで決定された廃棄率で廃棄する。【０１０９】
オペレーションＳＩＪにおいてパケット廃棄部２６は、図８に示すオペレーションＳＪと同様の判定を行い輻輳が発生したか否かを判定する。輻輳が発生していないと判定されたとき（オペレーションＳＩＪ：Ｎ）、入力パケットバッファ１１−１は処理をオペレーションＳＪＢに移す。輻輳が発生したと判定したとき（オペレーションＳＩＪ：Ｙ）、オペレーションＳＪＡにおいてパケット廃棄部２６は、廃棄パケットの送信元の装置に対して、スイッチ１０において輻輳が発生したことを明示的に通知する。その後、入力パケットバッファ１１−１は処理をオペレーションＳＪＢに移す。【０１１０】
オペレーションＳＪＢにおいてヘッドドロップ処理部５２は、測定対象となるキュー内に保持されたパケットの滞留時間を測定する。ヘッドドロップ処理部５２は、基準値を超えてキュー内に滞留するパケットをキューの先頭から廃棄する。その後、入力パケットバッファ１１−１は処理をオペレーションＳＩＡに戻す。なお、別な実施の態様においては、上記オペレーションＳＩＡ乃至オペレーションＳＪＢの各オペレーションはステップであってもよい。【０１１１】
図２１は、図５に示す入力パケットバッファ１１−１の第６構成例を説明する構成図である。入力パケットバッファ１１−１は、パケット判別部２と、パケット分配部４と、Ｎ個のキュー２１−１〜２１−Ｎと、キュー長測定部２２と、滞留時間予測部２４と、パケット廃棄部２６とを備える。入力パケットバッファ１１−１は、レート測定制御部３０と、送出累積量測定部３１と、測定値記憶部３２と、送出量算出部３３を備える。入力パケットバッファ１１−１は、読み出しタイミング検出部４０と、時刻測定部４１と、時刻記憶部４２と、測定間隔算出部４３を備える。入力パケットバッファ１１−１は、パケット廃棄制御部５１と、ヘッドドロップ処理部５２を備える。【０１１２】
レート測定制御部３０と、パケット判別部２と、パケット分配部４と、送出累積量測定部３１と、測定値記憶部３２と、送出量算出部３３は、図１７に示すそれぞれの要素と同様である。また、読み出しタイミング検出部４０と、時刻測定部４１と、時刻記憶部４２と、測定間隔算出部４３と、ヘッドドロップ処理部５２は、図１７に示すそれぞれの要素と同様である。パケット廃棄制御部５１とパケット廃棄部２６は図１９に示すそれぞれの要素と同様である。【０１１３】
キュー長測定部２２は、レート測定制御部３０により選択された、測定対象となるキューについてキュー長を測定する。滞留時間予測部２４は、キュー長測定部２２により測定されたキュー長と、送出量算出部３３により測定された測定対象のキューのデータ送出量と、測定間隔算出部４３により決定された測定間隔Ｔ１に応じて、滞留時間の予測値ＴＦ（予測値ＴＦ＝キュー長×測定間隔Ｔ１／データ送出量）を算出する。滞留時間予測部２４は、この予測値ＴＦそのものに代えて、その加重移動平均値を予測値ＴＦとして出力してよい。なお、加重移動平均値以外の平均値を求める他の方法として単純平均法、簡易指数平均法、最小二乗法などを適用してもよい。【０１１４】
図２２は、開示のパケット廃棄方法の第７例の方法である。オペレーションＳＢＡＡにおいてパケット判別部２は、入力パケットが、送信元のユーザについて定めた入力帯域幅に関する規定を遵守しているか否かを判別し、規定を遵守しているパケットとそうでないパケットに分類する。パケット廃棄部２６は、入力帯域幅に関する規定を遵守しているパケットをキューに保持する。【０１１５】
オペレーションＳＢＡＢにおいて読み出しタイミング検出部４０は、各キュー２１−１〜２１−Ｎのいずれかからデータの読み出しがあったか否かを検出する。データの読み出しが検出されなかったとき（オペレーションＳＢＡＢ：Ｎ）、入力パケットバッファ１１−１は処理をオペレーションＳＢＡＢに戻す。【０１１６】
データの読み出しが検出されたとき（オペレーションＳＢＡＢ：Ｙ）、読み出しが検出された測定対象のキューについて、オペレーションＳＢＡＣ〜ＳＢＡＨにおいて、図１８に示すオペレーションＳＧＣ〜ＳＧＨと同様にして、送出データ量と測定間隔Ｔ１が測定される。【０１１７】
ＳＢＡＩにおいてキュー長測定部２２は、対象となるキューについてキュー長を測定する。オペレーションＳＢＡＪにおいて滞留時間予測部２４は、キュー長測定部２２により測定されたキュー長と、送出量算出部３３により測定された測定対象のキューのデータ送出量と、測定間隔算出部４３により決定された測定間隔Ｔ１に応じて、測定対象のキューについて滞留時間の予測値ＴＦを算出する。以下に続くオペレーションＳＢＢＡ〜ＳＢＢＥの処理は、図２０に示すオペレーションＳＩＨ〜ＳＪＢと同じである。オペレーションＳＢＢＥの後、入力パケットバッファ１１−１は処理をオペレーションＳＢＡＡに戻す。なお、別な実施の態様においては、上記オペレーションＳＢＡＡ乃至オペレーションＳＢＢＥの各オペレーションはステップであってもよい。【０１１８】
上記第５構成例及び第６構成例においても、ヘッドドロップ処理部５２を省略し、入力帯域幅に関する規定を遵守しているか否かに関わらず、全てのパケットを、パケット廃棄部２６による廃棄の対象としてよい。また、入力帯域幅に関する規定を遵守しているパケットと遵守していないパケットの間で、廃棄率の決定に使用する上述のパラメータＭｉｎＴｈ、ＭａｘＰ及びＭａｘＴｈの値を変えてもよい。例えば、入力帯域幅に関する規定を遵守しているパケットを廃棄するか否かを判定する場合には、遵守していないパケットの場合と比べて、比較的小さい廃棄率となるようにパラメータを定めてもよい。以下の第７構成例においても同様である。【０１１９】
なお、第５構成例及び第６構成例において、パケット廃棄制御部５１及びパケット廃棄部２６は、滞留時間の予測値ＴＦを算出し、この滞留時間の予測値に応じた廃棄率でパケットを廃棄した。これに代えて、パケット廃棄制御部５１は、滞留時間の予測値ＴＦが滞留可能許容時間ＴＨＴより大きいか否かを判定し、パケット廃棄部２６は、予測値ＴＦ＞滞留可能許容時間ＴＨＴとなるキューに到着する到着パケットを廃棄してもよい。【０１２０】
図２３は、図５に示す入力パケットバッファ１１−１の第７構成例を説明する構成図である。参照符号６０は時刻測定部を示し、参照符号６１は時刻記憶部を示し、参照符号６２は滞留時間算出部を示す。入力パケットバッファ１１−１は、パケット判別部２と、パケット分配部４と、Ｎ個のキュー２１−１〜２１−Ｎと、キュー長測定部２２と、パケット廃棄部２６と、キュー長記憶部２７を備える。入力パケットバッファ１１−１は、パケット廃棄制御部５１と、ヘッドドロップ処理部５２と、時刻測定部６０と、時刻記憶部６１と、滞留時間算出部６２を備える。【０１２１】
パケット判別部２と、パケット分配部４と、パケット廃棄部２６は、ヘッドドロップ処理部５２は、図１５に示すそれぞれの要素と同様である。キュー長測定部２２は、パケット毎に、各パケットがキュー２１−１〜２１−Ｎに到着したときのキュー長である、到着時キュー長ＬＱＡを測定する。またキュー長測定部２２は、先頭パケットをキュー２１−１〜２１−Ｎから読み出すときのキュー長である、現キュー長ＬＱＣを測定する。キュー長測定部２２は、到着時キュー長ＬＱＡを、各パケット毎にキュー長記憶部２７に記憶する。【０１２２】
時刻測定部６０は、パケット毎に、各パケットが各キュー２１−１〜２１−Ｎに到着したとき時刻（以下「到着時刻」と示す）と、先頭パケットを各キュー２１−１〜２１−Ｎからから読み出すときの時刻（以下「現時刻」と示す）を測定する。時刻測定部６０は、到着時刻を、各パケット毎に時刻記憶部６１に記憶する。滞留時間算出部６２は、各パケット毎に、その到着時刻と現時刻との差を算出することにより、各キュー２１−１〜２１−Ｎ内における各パケットの滞留時間ＴＳを測定する。【０１２３】
パケット廃棄制御部５１は、キュー長測定部２２が各キュー２１−１〜２１−Ｎに格納されたパケットについて決定された、到着時キュー長ＬＱＡ、現キュー長ＬＱＣ及び滞留時間ＴＳと、予め定めた滞留可能許容時間ＴＨＴとに基づいて、各キュー毎に次の条件式（１）が満たされるか否かを判定する。
滞留可能許容時間ＴＨＴ×到着時キュー長ＬＱＡ  ＜  滞留時間ＴＳ×現キュー長ＬＱＣ    …（１）
ここで、滞留時間の予測値ＴＦを、ＴＦ＝（滞留時間ＴＳ×現キュー長ＬＱＣ／到着時キュー長ＬＱＡ）によって決定するとすれば、条件式（１）は予測値ＴＦ＞滞留可能許容時間ＴＨＴと等価である。【０１２４】
パケット廃棄制御部５１は、滞留時間ＴＳと、所定の基準値ＭＩＮＴＳに基づいて、各キュー毎に、次の条件式（２）が満たされるか否かを判定する。
滞留時間ＴＳ＞所定の基準値ＭＩＮＴＳ    …（２）【０１２５】
パケット廃棄制御部５１は、パケット廃棄部２６に対して、上記条件式（１）及び（２）を満たすキューについてテイルドロップを行う指示を出力する。条件式（１）に加えて条件式（２）を加えることにより、滞留時間の予測値ＴＦが滞留可能許容時間ＴＨＴを超えていても、実際には、滞留時間ＴＳがある程度の大きさになっていない場合にはパケット廃棄を停止することができる。【０１２６】
図２４は、開示のパケット廃棄方法の第８例を説明する方法である。オペレーションＳＢＣＡにおいて、パケット判別部２は、入力パケットが、送信元のユーザについて定めた入力帯域幅に関する規定を遵守しているか否かを判別し、規定を遵守しているパケットとそうでないパケットに分類する。パケット廃棄部２６は、入力帯域幅に関する規定を遵守しているパケットをキューに保持する。【０１２７】
オペレーションＳＢＣＢにおいてキュー長測定部２２は、各キューに到着するパケット毎に到着時キュー長ＬＱＡを測定する。オペレーションＳＢＣＣにおいてキュー長測定部２２は、到着時キュー長ＬＱＡを、各パケット毎にキュー長記憶部２７に記憶する。オペレーションＳＢＣＤにおいて時刻測定部６０は、パケット毎に、各パケットが各キューに到着したときの到着時刻を測定する。オペレーションＳＢＣＥにおいて時刻測定部６０は、到着時刻を、各パケット毎に時刻記憶部６１に記憶する。【０１２８】
オペレーションＳＢＣＦにおいて滞留時間算出部６２は、各パケット毎に、その到着時刻と現時刻との差を算出することにより、各キュー２１−１〜２１−Ｎ内における各パケットの滞留時間ＴＳを測定する。オペレーションＳＢＣＧにおいてキュー長測定部２２は、オペレーションＳＢＣＢにおいて到着時キュー長ＬＱＡを測定したパケットについて、このパケットをキュー２１から読み出した時の現キュー長ＬＱＣを測定する。【０１２９】
オペレーションＳＢＣＨにおいてパケット廃棄制御部５１は、上記条件式（１）及び条件式（２）の両方が満たされるか否かを判定する。条件式（１）及び条件式（２）の一方又は両方が満たされないとき（オペレーションＳＢＣＨ：Ｎ）、入力パケットバッファ１１−１は処理をＳＢＤＡへ移す。【０１３０】
条件式（１）及び条件式（２）の両方が満たされるとき（オペレーションＳＢＣＨ：Ｙ）、オペレーションＳＢＣＩにおいてパケット廃棄制御部５１は、条件式（１）及び条件式（２）の両方が満されるキューについてテイルドロップを行う指示をパケット廃棄部２６へ出力する。パケット廃棄部２６は、テイルドロップが行われるキューへ、入力帯域幅に関する規定を遵守していないパケットが到着したとき、このパケットを破棄する。オペレーションＳＢＣＪにおいてパケット廃棄部２６は、廃棄したパケットの送信元の装置に対して、スイッチ１０において輻輳が発生したことを明示的に通知する。入力パケットバッファ１１−１は処理をオペレーションＳＢＤＡに移す。オペレーションＳＢＤＡにおいてヘッドドロップ処理部５２は、図１６に示すオペレーションＳＦＡと同様の処理を行う。その後、入力パケットバッファ１１−１は処理をオペレーションＳＢＣＡに戻す。なお、別な実施の態様においては、上記オペレーションＳＢＣＡ乃至オペレーションＳＢＤＡの各オペレーションはステップであってもよい。【０１３１】
本実施例によれば、上記条件式を判定する際に除算を用いないので、除算回路を不要とすることができる。【０１３２】
なお、本実施例においてパケット廃棄制御部５１及びパケット廃棄部２６は、滞留時間ＴＳ×到着時キュー長ＬＱＡが、滞留可能許容時間ＴＨＴ×現キュー長ＬＱＣよりも大きいときパケットを廃棄した。これに代えて、パケット廃棄制御部５１は、滞留時間ＴＳと現キュー長ＬＱＣと到着時キュー長ＬＱＡとに基づき、滞留時間の予測値を算出し、この滞留時間の予測値に応じた入力パケットの廃棄率を決定してよい。また、パケット廃棄部２６は、決定された廃棄率に基づくＷＲＥＤ処理を行ってもよい。【０１３３】
また本実施例においてパケット廃棄制御部５１及びパケット廃棄部２６は、上記条件式（２）が満たされる場合に限り、すなわち滞留時間ＴＳが所定の基準値ＭＩＮＴＳを超える場合にのみ、パケットの廃棄処理を行っている。同様に、上記の第１構成例〜第６構成例においても、滞留時間ＴＳが所定の基準値ＭＩＮＴＳを超える場合にのみ、パケットの廃棄処理を行ってもよい。【０１３４】
以上、本発明の好適な実施態様について詳述したが、当業者が種々の修正及び変更をなし得ること、並びに、特許請求の範囲は本発明の真の精神および趣旨の範囲内にあるこの様な全ての修正及び変更を包含することは、本発明の範囲に含まれることは当業者に理解されるべきものである。
上記実施例の記載に基づき以下のように発明を構成してもよい。
（１）
到着したパケットがキュー内に滞留する時間を予測する滞留時間予測ステップと、
前記滞留時間予測ステップにより決定された予測時間が所定の第１基準値を超えるとき、到着したパケットを廃棄するパケット廃棄ステップと、
を含むパケット廃棄方法。（図７）
（２）
前記パケット廃棄ステップは、前記予測時間が前記第１基準値を超える超過量に応じて、到着したパケットを廃棄する割合を変化させる（１）に記載のパケット廃棄方法。（図８）
（３）
到着したパケットについて予測された前記予測時間が前記第１基準値を超えるとき、前記到着したパケットの送信元装置へ、輻輳の発生を通知する（１）に記載のパケット廃棄方法。
【産業上の利用可能性】
【０１３５】
本発明は、到着したパケットを一時的に保持するパケットバッファ装置に利用可能である。
【図１】
2010089886.tif 000003
【図２】
2010089886.tif 000004
【図３】
2010089886.tif 000005
【図４Ａ】
2010089886.tif 000006
【図４Ｂ】
2010089886.tif 000007
【図４Ｃ】
2010089886.tif 000008
【図４Ｄ】
2010089886.tif 000009
【図４Ｅ】
2010089886.tif 000010
【図５】
2010089886.tif 000011
【図６】
2010089886.tif 000012
【図７】
2010089886.tif 000013
【図８】
2010089886.tif 000014
【図９】
2010089886.tif 000015
【図１０】
2010089886.tif 000016
【図１１】
2010089886.tif 000017
【図１２】
2010089886.tif 000018
【図１３】
2010089886.tif 000019
【図１４】
2010089886.tif 000020
【図１５】
2010089886.tif 000021
【図１６】
2010089886.tif 000022
【図１７】
2010089886.tif 000023
【図１８】
2010089886.tif 000024
【図１９】
2010089886.tif 000025
【図２０】
2010089886.tif 000026
【図２１】
2010089886.tif 000027
【図２２】
2010089886.tif 000028
【図２３】
2010089886.tif 000029
【図２４】
2010089886.tif 000030
【手続補正書】
【提出日】平成23年4月19日(2011.4.19)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
到着したパケットを一時的に保持するキューと、
到着したパケットが前記キュー内に滞留する時間を予測する滞留時間予測手段と、
前記滞留時間予測手段により決定された予測時間が所定の第１基準値を超えるとき、到着したパケットを廃棄するパケット廃棄手段と、
を備えるパケットバッファ装置。
【請求項２】
到着したパケットを一時的に保持するキューと、
到着したパケットが前記キュー内に滞留する時間を予測する滞留時間予測手段と、
前記滞留時間予測手段により決定された予測時間が所定の第１基準値を超える超過量に応じて変化する割合で、到着したパケットを廃棄するパケット廃棄手段と、
を備えるパケットバッファ装置。
【請求項３】
前記予測時間が前記第１基準値を超えるとき、到着したパケットの送信元装置へ、輻輳の発生を通知する輻輳発生通知手段を備える請求項１に記載のパケットバッファ装置。
【請求項４】
前記キューに保持されている到着パケットのデータ量であるキュー長を測定するキュー長測定手段と、
キューから出力されるパケットの出力レートを測定するレート測定手段と、を備え、
前記滞留時間予測手段は、測定された前記キュー長と測定された前記出力レートとに基づいて、前記予測時間を決定する請求項１〜３のいずれか一項に記載のパケットバッファ装置。
【請求項５】
前記キューに保持されているデータ量であるキュー長を測定するキュー長測定手段と、
パケット到着時において測定された前記キュー長を記憶する記憶手段と、
前記キュー内に滞留するパケットの滞留時間を測定する滞留時間測定手段と、を備え、
前記滞留時間予測手段は、パケット到着時から現時点までの前記キュー長の変化率と、現時点で測定した前記滞留時間とに基づいて、前記予測時間を決定する請求項１〜３のいずれか一項に記載のパケットバッファ装置。
【請求項６】
到着したパケットがキュー内に滞留する時間を予測する滞留時間予測ステップと、
前記滞留時間予測ステップにより決定された予測時間が所定の基準値を超えるとき、到着したパケットを廃棄するパケット廃棄ステップと、
を含むパケット廃棄方法。
【請求項７】
到着したパケットがキュー内に滞留する時間を予測する滞留時間予測ステップと、
前記滞留時間予測ステップにより決定された予測時間が所定の基準値を超える超過量に応じて変化する割合で、到着したパケットを廃棄するパケット廃棄ステップと、
を含むパケット廃棄方法。
【請求項８】
到着したパケットについて予測された前記予測時間が前記基準値を超えるとき、前記到着したパケットの送信元装置へ、輻輳の発生を通知する請求項６に記載のパケット廃棄方法。
【手続補正書】
【提出日】平成23年10月11日(2011.10.11)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
入力されたパケットを変化する出力レートで出力するパケットバッファ装置であって、
パケットを順に格納し、先入れ先出しで出力するキュー手段と、
前記キュー手段が格納しているデータ量であるキュー長を測定するキュー長測定手段と、
前記キュー手段から出力されるパケットの前記出力レートを測定するレート測定手段と、
測定された前記キュー長と測定された前記出力レートとに基づいて、前記パケットバッファ装置に入力された入力パケットが前記キュー手段に滞留すると予測される予測時間を求める滞留時間予測手段と、
前記予測時間が所定の基準値を超えるとき、前記入力パケットを前記キュー手段に格納する前に廃棄するパケット廃棄手段と、
を備えるパケットバッファ装置。
【請求項２】
前記パケット廃棄手段は、前記予測時間が前記基準値を超える超過量に応じて変化する割合で、前記入力パケットを廃棄する請求項１に記載のパケットバッファ装置。
【請求項３】
パケットの出力優先順位が異なる複数の前記キュー手段を備え、
前記キュー長測定手段は、前記複数のキュー手段のうち出力優先順位が最高でないいずれかのキュー手段のキュー長を測定し、
前記レート測定手段は、前記いずれかのキュー手段から出力されるパケットの出力レートを測定し、
前記パケット廃棄手段は、前記予測時間が前記基準値を超えるとき前記いずれかのキュー手段に入力したパケットを廃棄する、請求項１又は２に記載のパケットバッファ装置。
【請求項４】
前記キュー手段に滞留するパケットの滞留時間を測定する滞留時間測定手段を備え、
前記パケット廃棄手段は、測定される滞留時間が所定の第１基準値未満のとき、前記予測時間が前記基準値である第２基準値を超えていても前記パケットを廃棄しない請求項１〜３のいずれか一項に記載のパケットバッファ装置。
【請求項５】
前記予測時間が前記基準値を超えるとき、前記パケットバッファ装置に入力された入力パケットの送信元装置へ、輻輳の発生を通知する輻輳発生通知手段を備えることを特徴とする請求項１〜４のいずれか一項に記載のパケットバッファ装置。
【請求項６】
入力されたパケットを変化する出力レートで出力するパケットバッファ装置に入力されるパケットの廃棄方法であって、
パケットを順にキュー手段へ格納し、出先入れ先出しで前記キュー手段から出力するパケット格納ステップと、
前記キュー手段が格納しているデータ量であるキュー長を測定するキュー長測定ステップと、
前記キュー手段から出力されるパケットの前記出力レートを測定する出力レート測定ステップと、
測定された前記キュー長と測定された前記出力レートとに基づいて、前記パケットバッファ装置に入力された入力パケットが前記キュー手段に滞留すると予測される予測時間を求める滞留時間予測ステップと、
前記滞留時間予測ステップにより決定された予測時間が所定の基準値を超えるとき、前記入力パケットを前記キュー手段に格納する前に廃棄するパケット廃棄ステップと、
を含むパケット廃棄方法。
【請求項７】
前記パケット廃棄ステップにおいて、前記予測時間が所定の基準値を超える超過量に応じて変化する割合で、前記入力パケットを廃棄する請求項６に記載のパケット廃棄方法。
【請求項８】
前記パケット格納ステップは、パケットの出力優先順位が異なる複数の前記キュー手段にパケットを格納し、
前記キュー長測定ステップにおいて、パケットの出力優先順位が異なるキュー手段のうち出力優先順位が最高でないいずれかのキュー手段のキュー長を測定し、
前記レート測定ステップにおいて、前記いずれかのキュー手段から出力されるパケットの出力レートを測定し、
前記パケット廃棄ステップにおいて、前記予測時間が前記基準値を超えるとき前記いずれかのキュー手段に入力したパケットを廃棄する、請求項６又は７に記載のパケット廃棄方法。
【請求項９】
前記キュー手段に滞留するパケットの滞留時間を測定する滞留時間測定ステップを含み、
測定される滞留時間が所定の第１基準値未満のとき、前記予測時間が前記基準値である第２基準値を超えていても前記パケット廃棄ステップで前記パケットを廃棄しない請求項６〜８のいずれか一項に記載のパケット廃棄方法。
【請求項１０】
前記予測時間が前記基準値を超えるとき、前記パケットバッファ装置に入力された入力パケットの送信元装置へ、輻輳の発生を通知する請求項６〜９のいずれか一項に記載のパケット廃棄方法。
【国際調査報告】
2010089886.tif 000031
2010089886.tif 000032
2010089886.tif 000033
2010089886.tif 000034