(57)【特許請求の範囲】
【請求項１】
入力されたパケットの列のレートをこれらのパケットが個別に属するフロー毎に規定の上限値以下に調整するレート制御手段と、
前記入力されたパケットが属し得る個々のクラスに対応して備えられ、これらのクラスのパケットの先入れ先出し方式に基づく蓄積および送出に供されるキューと、
前記キューの内、蓄積されているパケットの情報量が規定の閾値を超えるキューを識別するキュー監視手段と、
前記キュー監視手段によって識別されたキューに格納されるべき新たなパケットが属するフロー毎に、その新たなパケットを所定の頻度で廃棄するバッファ管理手段とを備え、
前記バッファ管理手段は、
フロー毎にパケットを廃棄した実績を記録し、その実績があるフローに属する新たなパケットを廃棄の対象から除外し、またはこの実績がないフローに属する新たなパケットが廃棄されるべき頻度より小さな頻度で廃棄する
ことを特徴とするフロー制御装置。
【請求項２】
請求項１に記載のフロー制御装置において、
前記バッファ管理手段は、
前記レート制御手段と一体化され、そのレート制御手段に備えられ、かつ入力された個々のパケットが属するフローを識別する手段を共用する
ことを特徴とするフロー制御装置。
【請求項３】
請求項１または請求項２に記載のフロー制御装置において、
入力されたパケットの列のレートをフロー毎に監視するレート監視手段を備え、
前記バッファ管理手段は、
前記レート監視手段によって監視されたレートのクラス毎の比率、またはその比率の単調増加関数として与えられる比率に等しい頻度で、前記キューの内、前記レート制御手段によってレートが調整されたパケットのクラスに対応するキューにそのパケットを蓄積する
ことを特徴とするフロー制御装置。
【請求項４】
請求項１ないし請求項３の何れか１項に記載され、かつ入力されたパケットの列のレート制御に併せて、これらのパケットのクラスに個別に対応したキューのバッファ管理をフロー毎に行うフロー制御装置と、
所定のリンクまたは端末に、前記フロー制御装置によって行われたレート制御およびバッファ管理の下で与えられたパケットを送出する通信インタフェース手段と
を備えたことを特徴とするノード装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、インタネットその他のパケットルーティング網にアクセスするノードにおいて、そのノードに収容された端末によって与えられ、あるいは入り線を介して与えられたパケットのレート制御と、これらのパケットのクラスに個別に対応したバッファのバッファ管理とを行うフロー制御装置と、そのフロー制御装置が搭載されてなるノード装置とに関する。
【０００２】
【従来の技術】
近年、急速に普及したインタネットでは、伝送遅延時間や伝送域が何ら保証されないベストエフォート型のサービスが多くの利用者に提供されている。
さらに、このようなインタネットに関しては、例えば、ＶｏＩＰ（Voice over IP)の適用による音声通信サービスの実現と、私設網(ＶＰＮ: Virtual Private Network) としての活用とが積極的に図られている。
【０００３】
したがって、インタネットには、例えば、図８に示すように、種々のサービスの形態に適合した下記のサービスクラスをエンド・ツー・エンドで保証する技術が適用されつつある。
・  伝送帯域が予め予約され、その伝送帯域を超えるレートで与えられたパケットが廃棄されることによって、伝送帯域と伝送遅延時間との双方が保証される「ＤＳ(Delay Sensitive) 型」のサービスクラス（以下、単に「ＤＳクラス」という。）
・  規定の最低の伝送帯域が保証され、かつ余剰の伝送帯域が適宜割り付けられる「ＴＳ(Throughput Sensitive)型」のサービスクラス（以下、単に「ＴＳクラス」という。）
・  余剰の伝送帯域がある限りにおいてサービスが提供され、伝送帯域、伝送遅延時間および伝送品質の何れもが保証されない「ＢＥ(Best Effort) 型」のサービスクラス（以下、単に「ＢＥクラス」という。）
図９は、ノードの入り線においてフロー制御を行う装置の構成例を示す図である。
【０００４】
図において、帯域監視部５１の入力には、自局に収容された端末によって送出されたパケット（あるいは先行する伝送区間から受信されたパケット）の列が与えられ、その帯域監視部５１の出力は輻輳制御部５２の入力に直結される。輻輳制御部５２は上述したパケットが属し得るサービスクラス（ここでは、簡単のため、既述の「ＤＳ（Delay Sensitive）型」、「ＴＳ（ThroughputSensitive)型」および「ＢＥ(Best Effort）型」の各サービスクラスであると仮定する。）に個別に対応した出力を有する。これらの出力は上述したサービスクラスに個別に対応したキュー５３-1〜５３-3の入力にそれぞれ直結され、これらのキュー５３-1〜５３-3の各出力は図示されないパケットスイッチ（あるいは回線インタフェース部）の対応するポートに接続される。さらに、キュー５３-1〜５３-3の読み出し制御端子には、先入れ先出し方式に基づくこれらのキュー５３-1〜５３-3の読み出しを主導的に達成するスケジューラ５４の制御端子に直結される。
【０００５】
このような構成の従来例では、帯域監視部５１は、例えば、上述した端末のユーザが契約時に申告した伝送帯域（以下、「契約帯域」という。）が既知の情報として予め与えられる。さらに、帯域監視部５１は、個々の端末からパケット（以下、「新たなパケット」という。）が与えられる度に下記の一連の処理を行うことによって、レート制御（ミーンポリシング）を行う。
【０００６】
(1) この新たなパケットの所定のフィールドを参照することによって、この新たなパケットが属するフロー（送信元の識別子を含む。）を識別する。
(2) その送信元である端末の契約帯域を取得する。
(3) リーキバケット・アルゴリズムその他の規定のアルゴリズムに基づいて、該当するフローに属するパケットのレート（平均速度）がその契約帯域を超えるか否かを判別する。
【０００７】
(4) その判別の結果が真である場合には、該当する新たなパケットを廃棄する。
(5) この判別の結果が偽である場合には、該当する新たなパケットを輻輳制御部５２に引き渡す。
なお、このようなレート制御の過程では、実際には、既述の契約帯域に併せて、網や該当する新たなパケットの宛先の状況（輻輳の程度等を含む。）が勘案されつつ上述した判別が行われる。しかし、これらの状況については、本発明の特徴に関係がないので、ここでは、詳細な説明を省略する。
【０００８】
また、輻輳制御部５２は、帯域監視部５１によって新たなパケットが引き渡される度に、例えば、ＲＥＤ(Random Early Discard)アルゴリズムやＷＲＤ（Weighted Random Early Discard)アルゴリズムに基づいて下記の処理を行う。
(1) この新たなパケットの所定のフィールドを参照することによってこのパケットが属するサービスクラスを特定する。
【０００９】
(2) キュー５３-1〜５３-3の内、このようにして特定されたサービスクラスに対応するキュー（以下、「対象キュー」という。）に先行して蓄積されているパケットの情報量（キュー長またはそのキュー長の平均値であってもよい。）が規定の上限値ＴＨmin(図１０(1))を上回るか否かを判別する。
【００１０】
(3) その判別の結果が偽であるときには、ファーストインファーストアウト方式に基づいてその新たなパケットを対象キューに蓄積する（図１０(2))。
(4) この判別の結果が真であるときには、この情報量が大きいほど高い確率でランダムに該当する新たなパケットを廃棄する（図１０(3))。
なお、既述の「ＤＳクラス」の伝送帯域と「ＴＳクラス」の最低の伝送帯域とは、共にキュー５３-1〜５３-3の内、対応するキューのサイズの範囲で保証されるべき帯域である。したがって、上述した処理の過程で輻輳制御部５２によって廃棄され得るパケットのサービスクラスについては、そのパケットに割り付けられ得る余剰の伝送帯域がある「ＴＳクラス」と「ＢＥクラス」との何れかに限定される。
【００１１】
また、キュー５３-1〜５３-3に先行して蓄積されたパケットがスケジューラ５４によって行われるスケジューリングの下で読み出される過程では、これらのスケジューラ５４とキュー５３-1〜５３-3とが連係することによって所定の処理を行う。
しかし、これらの処理の手順については、本発明の特徴に関係がないので、ここでは、その説明を省略する。
【００１２】
すなわち、上述した新たなパケットは、既述の契約帯域を超過しない限りにおいて帯域監視部５１によって有効なパケットとして取り込まれ、キュー５３-1〜５３-3の内、そのパケットが属するサービスクラスに対応したキューに先行して過剰な情報量（数）のパケットが蓄積されていない限り、そのキューに順次蓄積されると共に、所定のバッファ管理の下で順次読み出される。
【００１３】
したがって、このような従来例が適用されたノードでは、既述のレート制御およびバッファ管理の下でデッドロックの発生が回避され、かつフロー制御が安定に行われると共に、網の利用効率が高く維持される。
【００１４】
【発明が解決しようとする課題】
ところで、上述した従来例では、輻輳制御部５２によって廃棄されるべきパケットは、既述のアルゴリズムの下でランダムに選択され、その過程では、個々のパケットが属するフローは何ら識別されていなかった。
したがって、例えば、「ＴＳクラス」と「ＢＥクラス」との何れか一方に属するパケットの列によって多数のフローが並行して形成されている期間には、これらのフローにそれぞれ属するパケットが廃棄される確率は必ずしも同じ値とはならず、かつ同じサービスクラスに属するパケットであるにもかかわらず、特定のフローに属するパケットが他のフローに属するパケットに比べて著しく高い確率で廃棄される可能性があった。
【００１５】
本発明の目的は、個々のフローに属するパケットがバッファ管理の過程で公平に廃棄されるフロー制御装置およびノード装置を提供することを目的とする。
【００１６】
【課題を解決するための手段】
図１は、本発明にかかわるフロー制御装置の原理ブロック図である。
【００１７】
請求項１に記載の発明では、レート制御手段１１は、入力されたパケットの列のレートをこれらのパケットが個別に属するフロー毎に規定の上限値以下に調整する。キュー１２-1〜１２-Nは、入力されたパケットが属し得る個々のクラスに対応して備えられ、これらのクラスのパケットの先入れ先出し方式に基づく蓄積および送出に供される。キュー監視手段１３は、キュー１２-1〜１２-Nの内、蓄積されているパケットの情報量が規定の閾値を超えるキューを識別する。バッファ管理手段１４は、キュー監視手段１３によって識別されたキューに格納されるべき新たなパケットが属するフロー毎に、その新たなパケットを所定の頻度で廃棄する。さらに、バッファ管理手段１４は、フロー毎にパケットを廃棄した実績を記録し、その実績があるフローに属する新たなパケットを廃棄の対象から除外し、またはこの実績がないフローに属する新たなパケットが廃棄されるべき頻度より小さな頻度で廃棄する。
【００１８】
このようなフロー制御装置では、キュー１２-1〜１２-Nの内、上述した閾値を超える情報量のパケットが蓄積されることによって輻輳状態に陥ったキューに引き続いて格納されるべきパケットは、そのパケットが個別に属するフロー毎に既述の頻度で廃棄される。
また、このようなフロー制御装置では、輻輳状態に陥ったキューに引き続いて蓄積されるべきパケットの内、その輻輳状態の解消を目的として廃棄されるべきパケットは、何れのフローに属する場合であっても、先行して廃棄されたパケットの数や情報量が積算されることなく、フロー毎に簡便に識別される。
請求項２に記載の発明では、バッファ管理手段１４は、レート制御手段１１と一体化され、そのレート制御手段１１に備えられ、かつ入力された個々のパケットが属するフローを識別する手段を共用する。
【００１９】
このようなフロー制御装置では、輻輳状態に陥ったキューに蓄積されるべきパケットが属するフローを識別する手段がバッファ管理手段１４にも重複して備えられる場合に比べて、構成の簡略化と縮小化とが図られる。
請求項３に記載の発明では、レート監視手段１５は、入力されたパケットの列のレートをフロー毎に監視する。バッファ管理手段１４は、レート監視手段１５によって監視されたレートのクラス毎の比率、またはその比率の単調増加関数として与えられる比率に等しい頻度で、キュー１２-1〜１２-Nの内、レート制御手段１１によってレートが調整されたパケットのクラスに対応するキューに、そのパケットを蓄積する。
【００２０】
このようなフロー制御装置では、キュー１２-1〜１２-Nの余剰の領域のサイズの範囲で確保され得る余剰の伝送帯域は、入力されたパケットの列によって形成されるフローの内、レートが高いフローほど大きな割合で割り付けられる。
【００２２】
請求項１ないし請求項３に記載の発明の下位概念の発明では、バッファ管理手段１４は、フロー毎にパケットを廃棄した回数を計数し、その回数が規定の値以上であるフローに属するパケットを廃棄の対象から除外し、またはこの回数がその規定の値未満であるフローに属する新たなパケットが廃棄されるべき頻度より小さな頻度で廃棄する。
【００２３】
このようなフロー制御装置では、輻輳状態に陥ったキューに引き続いて蓄積されるべきパケットの内、その輻輳状態の解消を目的として廃棄されるパケットは、この輻輳状態が解消されるために何れかのフローに属するパケットが廃棄される回数が複数となる場合であっても、フロー毎に確度高く識別される。
請求項１に記載の下位概念の発明では、バッファ管理手段１４は、パケットが廃棄された実績をそのパケットが属するフローに対応付けて保持し、かつキュー監視手段１３によって識別されたキューに蓄積されるべきパケットの内、個別に属するフローに対応した実績が保持されているパケットを廃棄の対象から除外し、またはこの実績がないフローに属する新たなパケットが廃棄されるべき頻度より小さな頻度で廃棄する。
【００２４】
このようなフロー制御装置では、バッファ管理手段１４によって保持された実績は、キュー１２-1〜１２-Nの内、その実績で示されるように先行して廃棄されたパケットのクラスに対応したキューが上述した輻輳状態から復旧した後に再び輻輳状態に陥ったときにも、そのバッファ管理手段１４によって有効に識別される。
【００２５】
請求項１〜３に記載の発明に関連した第一の発明では、バッファ管理手段１４は、パケットが廃棄された回数をそのパケットが属するフローに対応付けて保持し、かつキュー監視手段１３によって識別されたキューに蓄積されるべきパケットの内、個別に属するフローに対応した回数が所定の値を上回るパケットを廃棄の対象から除外し、またはこの回数がその所定の値未満であるフローに属するパケットが廃棄されるべき頻度より小さな頻度で廃棄する。
【００２６】
このようなフロー制御装置では、バッファ管理手段１４によって保持された回数は、キュー１２-1〜１２-Nの内、先行して廃棄され、その回数に等しい数のパケットのクラスに対応したキューが上述した輻輳状態から復旧した後に再び輻輳状態に陥ったときにも、そのバッファ管理手段１４によって有効に識別される。
請求項１〜３に記載の発明に関連した第二の発明では、バッファ管理手段１４は、パケットが廃棄された回数を時間の経過に応じて小さく重み付けしつつそのパケットが属するフローに対応付けて保持し、かつキュー監視手段１３によって識別されたキューに蓄積されるべきパケットの内、個別に属するフローに対応した回数が保持されているパケットを廃棄の対象から除外し、またはこの回数が少ないほど小さな頻度でそのパケットを廃棄する。
【００２７】
このようなフロー制御装置では、輻輳状態に陥ったキューの大半に対応するサービスクラスのパケットがフロー毎に所望の数に亘って廃棄されたにもかかわらず、これらのフローに比べてレートが大幅に小さい特定のフローに属するパケットの廃棄が著しく遅れることが回避される。
請求項１〜３に記載の発明に関連した第三の発明では、キュー監視手段１３は、キュー１２-1〜１２-Nに個別に蓄積されているパケットの情報量が規定の閾値を超える程度を識別する。バッファ管理手段１４は、キュー監視手段１３によって識別された程度が大きいキューほど、大きな頻度でそのキューに格納されるべき新たなパケットを廃棄する。
【００２８】
このようなフロー制御装置では、キュー１２-1〜１２-Nの何れについても、輻輳の度合いが大きいほど、継続して書き込まれるべき新たなパケットの内、廃棄されるパケットの比率が大きな値となる。
請求項１〜３に記載の発明に関連した第四の発明では、バッファ管理手段１４は、キュー１２-1〜１２-Nに個別に対応するクラスに適応した最大値が予め与えられ、その最大値以下の頻度でそのクラスの新たなパケットを廃棄する。
【００２９】
このようなフロー制御装置では、上述した最大値が適正な値に設定される限り、個々のクラスで確保されるべき最低の伝送帯域が確保される。
請求項１〜３に記載の発明に関連した第五の発明では、バッファ管理手段１４は、入力されたパケットが属し得る個々のクラスに確保されるべき伝送帯域の幅に適応し、かつ共通のフローに属して廃棄が許容されるべき新たなパケットの最大の数が個々のフローについて与えられ、これらのフロー毎にその最大の数の新たなパケットを廃棄した後に後続する新たなパケットの廃棄を差し控える。
【００３０】
このようなフロー制御装置では、個々のクラスにおいて実際に確保されるべき最大の伝送帯域が小さいにもかかわらず、輻輳状態の解消を目的として廃棄されるべきパケットの数が過大となることが回避される。
請求項１〜３に記載の発明に関連した第六の発明では、伝送帯域監視手段１６は、キュー１２-1〜１２-Nに個別に対応したクラス毎に確保されるべき最大の伝送帯域の幅を把握する。バッファ管理手段１４は、キュー１２-1〜１２-Nに対応したクラス毎に、伝送帯域監視手段１６によって把握された伝送帯域の幅に適応し、かつ共通のフローに属して廃棄が許容されるべき新たなパケットの最大の数が個々のフローについて与えられ、これらのフロー毎にその最大の数以上の新たなパケットを廃棄した後に後続する新たなパケットの廃棄を差し控える。
【００３１】
このようなフロー制御装置では、個々のクラスにおいて実際に確保される最大の伝送帯域が広範に変化し得る場合であっても、その伝送帯域が小さい期間に輻輳状態の解消を目的として廃棄されるべきパケットの数が過大となることが回避される。
請求項１〜３に記載の発明に関連した第七の発明では、バッファ管理手段１４は、キュー監視手段１３によって識別されたキューに格納されるべきパケットが属し得るフロー毎に、そのキューに対応したクラスに確保されるべき伝送帯域の幅に適応する基準値が与えられ、先行して廃棄されたパケットと廃棄されなかったパケットと数もしくは情報量の総和の差または比がその基準値以上となった後に後続する新たなパケットの廃棄を差し控える。
【００３２】
このようなフロー制御装置では、キュー１２-1〜１２-Nの何れについても、輻輳状態の解消を目的として廃棄されるパケットの数は、そのパケットが属するフロー毎に達成されるべき伝送速度が小さいほど小さな値に設定される。
請求項１〜３に記載の発明に関連した第八の発明では、バッファ管理手段１４は、フロー毎に時系列の順に小さな頻度で、新たなパケットを廃棄する。
【００３３】
このようなフロー制御装置では、輻輳状態に陥ったキューがその輻輳状態から脱却するために要する時間が長くなった場合であっても、そのキューに引き続いて蓄積されるパケットの増加が規制される。
請求項１〜３に記載の発明に関連した第九の発明では、バッファ管理手段１４は、キュー１２-1〜１２-Nに個別に対応するクラスの新たなパケットが廃棄された比率の分散が所定の閾値を下回ったときに、これらの比率の内、そのクラスの新たなパケットに個別に対応する比率が大きいほど大きな頻度でその新たなパケットを廃棄する。
【００３４】
このようなフロー制御装置では、輻輳状態に陥ったキューに蓄積されるべきパケットの内、廃棄されるべき数のパケットの大半が廃棄されたときには、フロー毎に引き続いて廃棄されるべきパケットの数が有効に引き渡されつつ、これらのフローの全てに属するパケットが暫定的に廃棄の対象となる。
すなわち、輻輳状態に陥ったキューに蓄積されるべきパケットとしては、実効的なレートが他のフローに比べて小さい特定のフローに属するパケットは長時間に渡って生起しない。
【００３５】
図２は、本発明にかかわるノード装置の原理ブロック図である。
請求項４に記載の発明では、フロー制御装置２１は、入力されたパケットの列のレート制御に併せて、これらのパケットのクラスに個別に対応したキューのバッファ管理を請求の範囲１に記載の発明の適用の下でフロー毎に行う。通信インタフェース手段２２は、所定のリンクまたは端末に、フロー制御装置２１によって行われたレート制御およびバッファ管理の下で与えられたパケットを送出する。
【００３６】
このようなノード装置では、フロー毎の伝送品質が均一に保たれる。
【００３７】
【発明の実施の形態】
以下、図面に基づいて本発明の実施形態について詳細に説明する。
図３は、本発明の第一ないし第八の実施形態を示す図である。
【００３８】
図において、図９に示すものと機能および構成が同じものについては、同じ符号を付与して示し、ここでは、その説明を省略する。
本実施形態と図９に示す従来例との構成の相違点は、下記の点にある。
・  帯域監視部５１に代えて帯域監視部３１が備えられる。
・  その帯域監視部３１の前段にクラス識別部３２が配置される。
【００３９】
・  輻輳制御部５２に代えてキュー管理部３３が備えられる。
図４は、本発明の第一ないし第五の実施形態における帯域監視部の動作フローチャートである。
図５は、本発明の第一ないし第四の実施形態におけるキュー管理部の動作フローチャートである。
【００４０】
以下、図３〜図５を参照して本発明の第一の実施形態の動作を説明する。
クラス識別部３２は、個々の端末から新たなパケットが与えられる度にそのパケットの所定のフィールドを参照することによって、このパケットが属するサービスクラスを識別する。
さらに、クラス識別部３２は、このようにして識別されたサービスクラスの識別子（以下、「クラス識別子」という。）とこのサービスクラスに属する新たなパケットとの対を帯域監視部３１に逐次引き渡す。
【００４１】
また、帯域監視部３１は、図６に示すように、上述した新たなパケットのサービスクラスを示す「クラス識別子」と、その新たなパケットが属するフローを示す「フロー識別子」とに対応し、そのフローに属するパケットが先行して廃棄されたか否かを示す「廃棄フラグ」が保持されるべき廃棄制御レジスタ３１Ｒａを有する。
【００４２】
さらに、帯域監視部３１には、上述した端末のユーザの契約帯域が既知の情報として予め与えられる。
また、帯域監視部３１は、クラス識別部３２によって上述した新たなパケットとクラス識別子との対が引き渡される度に、下記の点で従来例と異なる手順に基づいてレート制御を行う。
【００４３】
・  該当する対に含まれる新たなパケットのレートが契約帯域を下回る場合には、その新たなパケットを含む対を保持し、この対をキュー管理部３３に引き渡す（図４(1))。
・  反対に、この新たなパケットのレートが契約帯域を超える場合には、その新たなパケットを含む対を廃棄する（図４(2))。
【００４４】
また、キュー管理部３３は、帯域監視部３１によって上述した対が引き渡される度に、下記の処理を行う。
(1) キュー５３-1〜５３-3の内、引き渡された対に含まれるクラス識別子に対応したキュー（以下、「対象キュー」という。）を特定し、その対象キューに先行して蓄積されているパケットの情報量（キュー長またはそのキュー長の平均値であってもよい。）が既述の上限値ＴＨmin（図１０(1)) を上回るか否かを判別する（図５(1))。
【００４５】
(2) その判別の結果を帯域監視部３１に通知する（図５(2))。
(3) この判別の結果が偽である場合には、該当する対に含まれる新たなパケットをファーストインファーストアウト方式に基づいて対象キューに蓄積する（図５(3)、図１０(2))。
(4) 反対に、その判別の結果が真である場合には、該当する対を暫定的に保持し（図５(4))、かつ後述するように帯域監視部３１によって与えられる「フロー検定通知」を待ち受ける。
【００４６】
一方、帯域監視部３１は、上述した判別の結果がキュー管理部３３によって通知されると、下記の処理を行う。
(1) 該当する判別の結果が偽である場合には、下記の処理(a)〜(c)を行う。
(a) 先行して保持された対を廃棄する（図４(3))。
(b) この対に含まれる新たなパケットの所定のフィールドを参照することによって、その新たなパケットが属するフローを識別する（図４(4))。
【００４７】
(c) 廃棄制御レジスタ３１Ｒａのレコードの内、上述した対に含まれるクラス識別子に対応する全てのレコード（全てのフロー識別子に対応する）の「  廃棄フラグ」フィールドの値を初期値「０」に設定する（図４(5))。
(2) 反対に、上述した判別の結果が真である場合には、次の一連の処理(a)〜(f)を行う。
【００４８】
(a) 先行して保持された対に含まれる新たなパケットの所定のフィールドを参照することによって、その新たなパケットが属するフローを識別する（図４    (6))。
(b) 廃棄制御レジスタ３１Ｒａのレコードの内、上述した対に含まれるクラス識別子に対応した全てのレコード（全てのフロー識別子に対応する。）の「廃棄フラグ」フィールドの値が初期値「０」であるか否かを判別する（図４    (7))。
【００４９】
(c) その判別の結果が真である場合に限って、これらの全てのレコードの「廃棄フラグ」フィールドの値を「１」に設定する（図４(8))。
(d) 廃棄制御レジスタ３１Ｒａのレコードの内、上述したフローを示すフロー識別子と該当するクラス識別子とに対応するレコード（以下、「目的レコード」という。）の「廃棄フラグ」フィールドの値が「０」であるか否かを判別する（図４(9))。
【００５０】
(e) その判別の結果が偽である場合には、該当する対を廃棄し、かつ目的レコードの「廃棄フラグ」フィールドの値を「０」に設定する（図４(10)) 。
(f) 反対にこの判別の結果が真である場合には、キュー管理部３３宛に、その旨を示す「フロー検定通知」を与える（図４(11)) 。
キュー管理部３３は、この「フロー検定通知」が与えられると、先行して保持した対に含まれる新たなパケットとクラス識別子とを取得し、キュー５３-1〜５３-3の内、そのクラス識別子に対応するキューに、この新たなパケットを蓄積する（図５(5))。
【００５１】
また、キュー管理部３３は、このような「フロー検定通知」が与えられることなく、帯域監視部３１によって他の新たな対が与えられると、先行して保持した対を廃棄した（図５(6))後に既述の処理を起動する。
すなわち、帯域監視部３１が行うレート制御の下でキュー管理部３３に順次引き渡される新たなパケットは、キュー５３-1〜５３-3の内、これらのパケットが個別に蓄積されるべきキューに先行して過剰な情報量（数）のパケットが蓄積されている輻輳状態であっても、そのキューに対応するサービスクラス毎に特定のフロー毎に属するパケットに偏ることなく、ほぼ同じ確率で廃棄される。
【００５２】
このように本実施形態によれば、輻輳状態に陥ったキューに格納されるべき新たなパケットの内、廃棄されるべきパケットがそのパケットが属するフローが何ら識別されることなく決定されていた従来例に比べて、何れのフローによって達成される伝送品質も等しい値に維持される。
したがって、本実施形態が適用されたノードでは、従来例に比べてデッドロックの発生が確度高く回避され、かつフロー制御の安定性と、網の利用効率とが高められる。
【００５３】
以下、本発明の第二の実施形態について説明する。
本実施形態と上述した第一の実施形態との構成の相違点は、図６に示すように、下記の点で既述の廃棄制御レジスタ３１Ｒａと構成が異なる廃棄制御レジスタ３１Ｒｂがその廃棄制御レジスタ３１Ｒａに代えて備えられた点にある。
・  フロー毎に引き続いて廃棄が許容されるべき新たなパケットの残数を示す「廃棄パケット数」フィールドを「廃棄フラグ」フィールドに代えて有する。
【００５４】
・  フロー毎に廃棄されるべきパケットの語長の総和を示す「廃棄パケット総語長」フィールドを有する。
図７は、本発明の第二および第四の実施形態における帯域監視部の動作フローチャートである。
以下、図３〜図７を参照して本発明の第二の実施形態の動作を説明する。
【００５５】
本実施形態の特徴は、帯域監視部３１が行う下記の処理の手順にある。
帯域監視部３１は、クラス識別部３２によって何らかの対が引き渡される度に、下記の処理を行う。
(1) 該当する対に含まれる新たなパケットの所定のフィールドを参照することによって、その新たなパケットが属するフローを識別すると共に、このフローを示すフロー識別子ｆを求める。
【００５６】
(2) この新たなパケットの語長を求め、上述したように識別されたフロー毎に時系列の順に対応した履歴として、その語長を所定の時間に亘って記録する。
また、帯域監視部３１は、規定の単位時間毎に下記の処理を行う。
・  上述した単位時間に亘って先行する期間内に既述の履歴として記録され、かつクラス識別部３２によって引き渡される対に含まれ得る全てのクラス識別子ｃと、その対に含まれる新たなパケットが属し得るフローを示すフロー識別子ｆとの全ての組み合わせに対応した個々の語長の総和Ｌｃｆを求める。
【００５７】
・  上述した全ての組み合わせに個別に対応する廃棄制御レジスタ３１Ｒｂのレコードの「廃棄パケット総語長」フィールドに、上述した語長の総和の内、該当する組み合わせに対応した語長の総和Ｌｃｆを格納する。
さらに、帯域監視部３１には、クラス識別部３２によって新たな対が引き渡される度に、下記の手順に基づいてレート制御を行う。
【００５８】
・  該当する対に含まれる新たなパケットのレートが契約帯域を下回る場合には、その新たなパケットを含む対を保持し、この対をキュー管理部３３に引き渡す（図４(1))。
・  反対に、この新たなパケットのレートが契約帯域を超える場合には、その新たなパケットを含む対を廃棄する（図４(2))。
【００５９】
また、キュー管理部３３は、帯域監視部３１によって上述した対が引き渡される度に、下記の処理を行う。
(1) キュー５３-1〜５３-3の内、引き渡された対に含まれるクラス識別子に対応した対象キューを特定し、その対象キューに先行して蓄積されているパケットの情報量（キュー長またはそのキュー長の平均値であってもよい。）が既述の上限値ＴＨminを上回るか否かを判別する（図５(1))。
【００６０】
(2) その判別の結果を帯域監視部３１に通知する（図５(2))。
(3) この判別の結果が偽である場合には、該当する対に含まれる新たなパケットをファーストインファーストアウト方式に基づいて対象キューに蓄積する（図５(3))。
(4) 反対に、その判別の結果が真である場合には、該当する対を暫定的に保持し（図５(4))、かつ後述するように帯域監視部３１によって与えられる「フロー検定通知」を待ち受ける。
【００６１】
一方、帯域監視部３１は、上述した判別の結果がキュー管理部３３によって通知されると、下記の処理を行う。
(1) 該当する判別の結果が偽である場合には、下記の処理(a)〜(c)を行う。
(a) 先行して保持された対を廃棄する（図４(3))。
(b) この対に含まれる新たなパケットの所定のフィールドを参照することによって、その新たなパケットが属するフローを識別する（図４(4))。
【００６２】
(c) 廃棄制御レジスタ３１Ｒｂのレコードの内、上述した対に含まれるクラス識別子ｃに対応する全てのレコード（全てのフロー識別子に対応する）の「廃棄パケット数」フィールドの値を初期値「０」に設定する（図４(5))。
(2) 反対に、上述した判別の結果が真である場合には、次の一連の処理(a)〜(f)を行う。
【００６３】
(a) 先行して保持された対に含まれる新たなパケットの所定のフィールドを参照することによって、その新たなパケットが属するフローを識別する（図４    (6))。
(b) 廃棄制御レジスタ３１Ｒｂのレコードの内、上述した対に含まれるクラス識別子ｃに対応した全てのレコード（全てのフロー識別子に対応する。）の「廃棄パケット数」フィールドの値が初期値「０」であるか否かを判別する（図７(1))。
【００６４】
(c) その判別の結果が真である場合に限って、これらの全てのレコードの「廃棄パケット数」フィールドの値を下記の初期値Ｎｃｆに設定する（図７(2))。
ここに、初期値Ｎｃｆは、廃棄制御レジスタ３１Ｒｂのレコードの内、クラス識別子ｃに対応した全てのレコードの「廃棄パケット総語長」フィールドの値の総和と、そのクラス識別子ｃに対応した個々のレコードの「廃棄パケット総語長」フィールドの値との比以上である整数、またはその比が大きいほど大きい整数としてＮｃｆとして与えられる。
【００６５】
(d) 廃棄制御レジスタ３１Ｒｂのレコードの内、上述したフローを示すフロー識別子と該当するクラス識別子とに対応するレコード（以下、「目的レコード」という。）の「廃棄パケット数」フィールドの値が「０」であるか否かを判別する（図７(3))。
(e) その判別の結果が偽である場合には、該当する対を廃棄し、かつ目的レコードの「廃棄パケット数」フィールドの値をデクリメントする（図７(4))。
【００６６】
(f) 反対に、この判別の結果が真である場合には、キュー管理部３３宛に、その旨を示す「フロー検定通知」を与える（図７(5))。
キュー管理部３３は、この「フロー検定通知」が与えられると、先行して保持した対に含まれる新たなパケットとクラス識別子とを取得し、キュー５３-1〜５３-3の内、そのクラス識別子に対応するキューに、この新たなパケットを蓄積する（図５(5))。
【００６７】
また、キュー管理部３３は、このような「フロー検定通知」が与えられることなく、帯域監視部３１によって他の新たな対が与えられる（図５(6))と、先行して保持した対を廃棄した後に、既述の処理を起動する。
すなわち、帯域監視部３１が行うレート制御の下でキュー管理部３３に順次引き渡される新たなパケットは、キュー５３-1〜５３-3の内、これらのパケットが個別に蓄積されるべきキューに先行して過剰な情報量（数）のパケットが蓄積されている輻輳状態であっても、その新たなパケットが属するフロー毎のレートの如何にかかわらず一定の頻度で廃棄される。
【００６８】
したがって、本実施形態によれば、上述した輻輳状態に陥ったキューに格納されるべき新たなパケットの内、廃棄されるべきパケットがこれらのパケットが属するフロー毎のレートの如何にかかわらず決定される場合に比べて、何れのフローによって達成される伝送品質もほぼ均一に維持される。
以下、本発明の第三の実施形態について説明する。
【００６９】
本実施形態と上述した第二の実施形態との構成の相違点は、図６に示すように、廃棄制御レジスタ３１Ｒｂに代えて、レコード毎に既述の「廃棄パケット数」フィールドの値の退避先となるべき「先行廃棄パケット数」フィールドを有する点で、その廃棄制御レジスタ３１Ｒｂと異なる廃棄制御レジスタ３１Ｒｃが備えられた点にある。
【００７０】
以下、図３〜図６を参照して本発明の第三の実施形態の動作を説明する。
本実施形態と既述の第二の実施形態との相違点は、帯域監視部３１とキュー管理部３１とが行う下記の処理の手順にある。
キュー管理部３３は、キュー５３-1〜５３-3に蓄積されているパケットの情報量を個別に所定の頻度で監視し（図５(a)）、これらの情報量の何れかが所定の下限値を下回ると、該当するキューの識別子を含む「輻輳状態解消通知」を帯域監視部３１に与える（図５(b)）。
【００７１】
一方、帯域監視部３１は、下記の点で既述の第二の実施形態と異なる手順に基づく処理を行う。
帯域監視部３１は、キュー５３-1〜５３-3の何れかの識別子（ここでは、簡単のため、既述のクラス識別子ｃに等しいと仮定する。）を含む「輻輳状態解消通知」がキュー管理部３３によって与えられると、廃棄制御レジスタ３１Ｒｃのレコードの内、この「輻輳状態解消通知」に含まれるクラス識別子ｃに対応する全てのレコードについて、それぞれ「廃棄パケット数」フィールドの値を「先行廃棄パケット数」フィールドに退避する（図４(a)）。
【００７２】
なお、帯域監視部３１が何らかの新たな対をキュー管理部３３に引き渡すために行う処理（図４(1)、(2)）の手順については、既述の第二の実施形態において行われる処理と同じであるので、ここではその説明を省略する。
また、帯域監視部３１は、キュー管理部３３によって既述の判別の結果が通知されると、下記の処理を行う。
【００７３】
(1)   該当する判別の結果が偽である場合には、下記の処理(a)〜(c)を行う。
(a) 先行して保持された対を廃棄する（図４(3))。
(b) この対に含まれる新たなパケットの所定のフィールドを参照することによって、その新たなパケットが属するフローを識別する（図４(4))。
(c) 廃棄制御レジスタ３１Ｒｃのレコードの内、上述した対に含まれるクラス識別子ｃに対応する全てのレコード（全てのフロー識別子に対応する）についてそれぞれ「廃棄パケット数」フィールドの値を「先行廃棄パケット数」フィールドに退避し（図４(b)）、さらに、これらの「廃棄パケット数」フィールドの値を初期値「０」に設定する（図４(c))。
【００７４】
(2) 反対に、上述した判別の結果が真である場合には、次の一連の処理(a)〜(g)を行う。
(a) 先行して保持された対に含まれる新たなパケットの所定のフィールドを参照することによって、その新たなパケットが属するフローを識別する（図４    (6))。
【００７５】
(b) 廃棄制御レジスタ３１Ｒｂのレコードの内、上述した対に含まれるクラス識別子ｃに対応した全てのレコード（全てのフロー識別子に対応する。）の「先行廃棄パケット数」フィールドの値が初期値「０」であるか否かを判別する（図４(d))。
(c) その判別の結果が真である場合には、これらの全てのレコードについて、それぞれ「廃棄パケット数」フィールドの値を既述の初期値Ｎｃｆに設定する（図４(e))。
【００７６】
(d) 反対に、この判別の結果が偽である場合には、上述した全てのレコードについて、それぞれ「先行廃棄パケット数」フィールドの値を「廃棄パケット数」フィールドに複写する（図４(f))。
(e) 廃棄制御レジスタ３１Ｒｃのレコードの内、上述したフローを示すフロー識別子と該当するクラス識別子とに対応する目的レコードの「廃棄パケット数」フィールドの値が「０」であるか否かを判別する（図４(g))。
【００７７】
(f) その判別の結果が偽である場合には、該当する対を廃棄し、かつ目的レコードの「廃棄パケット数」フィールドの値をデクリメントする（図４(h))。
(g) 反対に、この判別の結果が真である場合には、キュー管理部３３宛に、その旨を示す「フロー検定通知」を与える（図４(11)) 。
なお、キュー管理部３３がこのような「フロー検定通知」に応じて行う処理の手順については、既述の第二の実施形態と同じであるので、ここではその説明を省略する。
【００７８】
すなわち、キュー５３-1〜５３-3の内、輻輳状態に陥ったキューに蓄積されるべき新たなパケットの内、その輻輳状態からの脱却を目的として廃棄されるべきパケットの数のセル毎の残数は、この輻輳状態が解消された後であっても、後続して発生する輻輳状態において廃棄されるべきパケットの数として確実に引き継がれる。
【００７９】
したがって、キュー５３-1〜５３-3の何れかが間欠的に輻輳状態に陥る場合であっても、個々のフローに属するパケットが廃棄されるべき頻度は、精度よく、かつ適正に保たれる。
なお、本実施形態では、廃棄制御レジスタ３１Ｒｃの何れのレコードについても、「廃棄パケット数」フィールドの値は、対応するサービスクラスおよびフローに属する新たなパケットが廃棄されない限りデクリメントされない。
【００８０】
しかし、何れの「廃棄パケット数」フィールドについても、値が更新された時点から経過した時間に応じて小さな値となる重みによる重み付けが施されることによって、該当するサービスクラスにおいて形成される大半のフローに属する所望の数のパケットが廃棄されたにもかかわらず、これらのフローに比べてレートが著しく小さいフローに属するパケットの廃棄が著しく遅れ、そのために輻輳状態が解消された時点の識別が無用に遅れることが回避されてもよい。
【００８１】
以下、本発明の第四の実施形態について説明する。
本実施形態のハードウエアの構成は、既述の第二の実施形態の構成と基本的に同じであるので、ここではその説明を省略する。
以下、図３〜図７を参照して本発明の第四の実施形態の動作を説明する。
本実施形態と既述の第二の実施形態との相違点は、帯域監視部３１およびキュー管理部３３が連係して行う下記の処理の手順にある。
【００８２】
キュー管理部３３は、帯域監視部３１によって何らかの対が引き渡されるたびに、キュー５３-1〜５３-3の内、その対に含まれるクラス識別子に対応した対象キューを特定し、その対象キューに先行して蓄積されているパケットの情報量が規定の上限値ＴＨmin を上回るか否かを判別する（図５(1)）。
さらに、キュー管理部３３は、その判別の結果が偽である場合には、帯域監視部３１に通知すべきこの判別の結果として、対象キューに実際に蓄積されているパケットの情報量と上述した上限値ＴＨmin との比（または差)(以下、「輻輳係数」という。)を付加する（図５(A)）。
【００８３】
一方、帯域監視部３１は、上述した判別の結果がキュー管理部３３によって通知されると、下記の処理を行う。
(1) 該当する判別の結果が偽である場合には、第二の実施形態と同様の手順に基づいて先行して保持された対を廃棄し、かつ廃棄制御レジスタ３１Ｒｂのレコードの内、上述した対に含まれるクラス識別子ｃに対応する全てのレコードの「廃棄パケット数」フィールドの値を初期値「０」に設定する（図４(3)、(4)、  (A))。
【００８４】
(2) 反対に、上述した判別の結果が真である場合には、次の一連の処理(a)〜(e)を行う。
(a) その判別の結果に含まれる「輻輳係数」を取得する（図４(B))。
【００８５】
(b) 先行して保持された対に含まれる新たなパケットの所定のフィールドを参照することによって、その新たなパケットが属するフローを識別する（図４    (6))。
(c) 廃棄制御レジスタ３１Ｒｂのレコードの内、上述した対に含まれるクラス識別子ｃに対応した全てのレコードの「廃棄パケット数」フィールドの値が初期値「０」であるか否かを判別する（図７(1))。
【００８６】
(d) その判別の結果が真である場合に限って、これらの全てのレコードの「廃棄パケット数」フィールドの値を既述の初期値Ｎｃｆと上述した「輻輳係数」との積に設定する（図７(A))。
(e) 以下、第二の実施形態と同様の手順に基づく処理（ここでは、詳細な説明を省略する。）を続行する。
【００８７】
また、このような処理の過程で帯域監視部３１によって与えられた「フロー検定通知」に応じてキュー管理部３３によって行われる処理の手順については、第二の実施形態と同じであるので、ここではその説明を省略する。
すなわち、帯域監視部３１が行うレート制御の下でキュー管理部３３に順次引き渡される新たなパケットは、キュー５３-1〜５３-3の内、そのパケットが個別に蓄積されるべきキューに先行して過剰な情報量（数）のパケットが蓄積されている輻輳状態には、この新たなパケットが属するフロー毎のレートの如何にかかわらず、その情報量の過剰な程度（既述の「輻輳係数」）に比例した頻度で廃棄される。
【００８８】
したがって、本実施形態によれば、キュー５３-1〜５３-3で並行して生じ得る輻輳状態の程度の如何にかかわらず、その輻輳状態の解消を目的としてフロー毎に廃棄されるべきパケットの頻度が決定される第二の実施形態に比べて、このような輻輳状態の解消が効率的に、かつ速やかに図られる。
なお、本実施形態では、「輻輳係数」として適用されるべき好適な値やその値の値域が何ら示されていない。
【００８９】
しかし、このような「輻輳係数」の値については、所望の形態によるフロー制御の実現、もしくはそのフロー制御にかかわる制約の回避が達成される値、または予め決められ離散的な値の何れかに設定されてもよい。
以下、本発明の第五の実施形態について説明する。
本実施形態のハードウエアの構成については、既述の第三の実施形態と基本的に同じであるので、ここでは、その説明を省略する。
【００９０】
以下、図３および図４を参照して本発明の第五の実施形態の動作を説明する。
本実施形態と既述の第三の実施形態との相違点は、帯域監視部３１によって行われる下記の処理の手順にある。
帯域監視部３１は、キュー５３-1〜５３-3の何れかの識別子（ここでは、簡単のため、既述のクラス識別子ｃに等しいと仮定する。）を含む「輻輳状態解消通知」がキュー管理部３３によって与えられると、廃棄制御レジスタ３１Ｒｃのレコードの内、このクラス識別子ｃに対応する全てのレコードについて、それぞれ「廃棄パケット数」フィールドの値を「先行廃棄パケット数」フィールドに退避する（図４(a)）。
【００９１】
なお、帯域監視部３１が何らかの新たな対をキュー管理部３３に引き渡すために行う処理の手順については、既述の第二の実施形態において行われる処理と同じであるので、ここではその説明を省略する。
また、帯域監視部３１は、キュー管理部３３によって既述の判別の結果が通知されると、下記の処理を行う。
【００９２】
(1) 該当する判別の結果が偽である場合には、第三の実施形態と同様の手順に基づいて、先行して保持された対を廃棄し、かつ廃棄制御レジスタ３１Ｒｃのレコードの内、上述した対に含まれるクラス識別子ｃに対応する全てのレートについて「廃棄パケット数」フィールドの値を「先行廃棄パケット数」フィールドに退避し、さらに、これらの「廃棄パケット数」フィールドの値を初期値「０」に設定する（図４(3)、(4)、(A))。
【００９３】
(2) 反対に、上述した判別の結果が真である場合には、次の一連の処理(a)〜(e)を行う。
(a) 先行して保持された対に含まれる新たなパケットの所定のフィールドを参照することによって、その新たなパケットが属するフローを識別する（図４    (6))。
【００９４】
(b) 廃棄制御レジスタ３１Ｒｂのレコードの内、上述した対に含まれるクラス識別子ｃに対応した全てのレコード（全てのフロー識別子に対応する。）の「先行廃棄パケット数」フィールドの値が初期値「０」であるか否かを判別する（図４(d))。
(c) その判別の結果の如何にかかわらず、これらの全てのレコードについて、「廃棄パケット数」フィールドの値を既述の初期値Ｎｃｆに設定する（図４    (e))。
【００９５】
(d) さらに、上述した判別の結果が偽である場合には、上述した全てのレコードについて、それぞれ「廃棄パケット数」フィールドの値に「先行廃棄パケット数」フィールドの値を加算する（図４(i))。
(e) 以下、第三の実施形態と同様の手順に基づいて処理を続行する。
また、このような処理の過程で帯域監視部３１が与える「フロー検定通知」に応じてキュー管理部３３によって行われる処理の手順については、第三の実施形態と同じであるので、ここではその説明を省略する。
【００９６】
すなわち、キュー５３-1〜５３-3の内、輻輳状態に陥ったキューに蓄積されるべき新たなパケットの内、その輻輳状態からの脱却を目的として廃棄されるべきパケットの数のセル毎の残数は、この輻輳状態が解消された後であっても、後続して発生する輻輳状態において本来的に廃棄されるべきパケットの数に加算されて確実に引き継がれる。
【００９７】
したがって、キュー５３-1〜５３-3の何れかが間欠的に輻輳状態に陥る場合であっても、個々のフローに属するパケットが廃棄されるべき頻度は、第三の実施形態に比べてさらに精度よく、かつ適正に保たれる。
なお、既述の第三および第五の実施形態は、それぞれ第二および第三の実施形態２に既述の改良が加えられることによって構成されている。
【００９８】
しかし、これらの第三および第五の実施形態は、既述の第一の実施形態に同様の改良が加えられることによって構成されてもよい。
以下、本発明の第六の実施形態について説明する。
本実施形態の構成は、既述の第二の実施形態と基本的に同じであるので、ここではその説明を省略する。
【００９９】
以下、図３および図６を参照して本発明の第六の実施形態の動作を説明する。
本実施形態の特徴は、帯域監視部３１が行う下記の処理の手順にある。
帯域監視部３１は、下記の全てまたは一部を勘案することによって、キュー５３-1〜５３-3に対応する個々のサービスクラスのパケットによって実現され得る最大の伝送速度（伝送帯域）(以下、「最大有能速度」という。)を求める。
【０１００】
・  キュー５３-1〜５３-3のサイズ
・  これらのキュー５３-1〜５３-3から読み出されたパケットが与えられ、あるいは送出されるべきスイッチ、後続する伝送区間の状況（輻輳の程度、障害の有無等を含む。）
なお、上述した最大有能速度については、「全てのサービスクラスに共通である規定の標準的な伝送速度に対する比率」として与えられると仮定する。
【０１０１】
また、上述した伝送区間の状況を把握するために行われるべき処理の手順については、本発明の特徴ではなく、かつ多様な公知技術の適用の下で実現が可能であるので、ここではその説明を省略する。
【０１０２】
さらに、帯域監視部３１は、既述の第二の実施形態と同じ手順に基づいて、クラス識別部３２によって引き渡された対に含まれるパケットのフロー毎に、その単位時間当たりの語長の総和Ｌｃｆを求め、かつ廃棄制御レジスタ３１Ｒｂのレコードの「廃棄パケット総語長」フィールドに、この語長の総和Ｌｃｆと「上述した最大有能速度として求められた比率」との積をその語長の総和Ｌｃｆに代えて格納する。
【０１０３】
すなわち、キュー５３-1〜５３-3の何れかに生じた輻輳状態において、帯域監視部３１が行うレート制御の下でキュー管理部３３に順次引き渡された新たなパケットが廃棄される頻度は、フロー毎のレートが大きいほど大きく、かつ該当するキューに対応したサービスクラスにおいて実際に確保され得る最大有能速度が小さいほど小さな頻度で廃棄される。
【０１０４】
このように本実施形態によれば、個々のサービスクラスにおいて実際に確保され得る最大有能速度が小さい状態であるにもかかわらず、キュー５３-1〜５３-3に生じた輻輳状態の解消を目的として廃棄されるべきパケットの数が過大となることが回避される。
したがって、キュー５３-1〜５３-3の何れについても、発生した輻輳状態は、伝送品質が過度に劣化することなく解消される。
【０１０５】
以下、本発明の第七の実施形態について説明する。
本実施形態のハードウエアの構成については、上述した第六の実施形態の構成と基本的に同じであるので、ここではその説明を省略する。
以下、図３を参照して本発明の第七の実施形態の動作を説明する。
本実施形態と上述した第二の実施形態との相違点は、帯域監視部３１が行う下記の処理の手順にある。
【０１０６】
帯域監視部３１は、既述の第六の実施形態と同じ手順に基づいて、キュー５３-1〜５３-3に対応する個々のサービスクラスのパケットによって実現され得る最大の伝送速度（伝送帯域）(以下、「最大有能速度」という。)を求める。
なお、本実施形態では、この最大有能速度は、単位時間当たりに伝送されるべきパケットの数として与えられると仮定する。
【０１０７】
さらに、帯域監視部３１は、このようにサービスクラス毎に求められた最大有能速度の単調増加関数の値として与えられ、かつキュー５３-1〜５３-3に生じた輻輳状態の解消を目的として廃棄されるべきパケットの数と、その廃棄の対象とならないパケットの数とのフロー毎の差または比がとるべき標準的な値である標準値を求める。
【０１０８】
なお、このような標準値は、サービスクラス毎の最大有能速度に適応した値がフロー毎の伝送帯域で比例案分されることによって求められ、これらのフロー毎の伝送帯域は実測によって求められ、あるいは予め定数として与えられてもよい。
また、帯域監視部３１は、キュー５３-1〜５３-3の何れかが陥った輻輳状態の解消を目的として廃棄されるべき新たなパケットを確定する処理（この処理の手順については、後述する点を除いて第二の実施形態と同じであるので、ここではその説明を省略する。）の過程において、下記の処理を併せて行う。
【０１０９】
(a) 上述した廃棄されるべき新たなパケットを確定する度に、そのパケットの数Ｄcfを該当するパケットのサービスクラス（クラス識別子ｃ）とフロー（フロー識別子ｆ）との組み合わせ毎に計数する。
(b) 反対に廃棄の対象とならない新たなパケットを確定する確定する度に、そのパケットの数ｄcfを該当するパケットのサービスクラス（クラス識別子ｃ）とフロー（フロー識別子ｆ）との組み合わせ毎に計数する。
【０１１０】
さらに、帯域監視部３１は、キュー管理部３３によって通知された既述の判別の結果が真である場合には、下記の点を除いて第二の実施形態と同じ手順に基づく処理を行う。
(1) 廃棄制御レジスタ３１Ｒｂのレコードの内、先行して識別されたフローを示すフロー識別子とクラス識別子とに対応する目的レコードの「廃棄パケット数」フィールドの値が「０」でない場合には、上述したパケットの数Ｄcf、ｄcfに対して下記の何れかの判別式の値（以下、「判別値」という。）ｊが上述した標準値以上であるか否かを判別する。
【０１１１】
ｊ＝Ｄcf／ｄcf
ｊ＝ｄcf−Ｄcf
(2) その判別の結果が真である場合には、該当する対の廃棄に併せて、目的レコードの「廃棄パケット数」フィールドの値のデクリメントを差し控える。
したがって、本実施形態によれば、キュー５３-1〜５３-3の輻輳状態の解消を目的として行われるべき新たなパケットの廃棄は、その新たなパケットが属するフローについて求められた最大有能速度が小さいほど少ない回数で打ち切られる。
【０１１２】
なお、本実施形態および既述の第六の実施形態では、キュー５３-1〜５３-3の内、輻輳状態に陥ったキューに対応するサービスクラスで実際に確保され得る最大有能速度が所定の通信制御の下で監視されている。
しかし、このような最大有能速度は、例えば、キュー５３-1〜５３-3のサイズと、これらのキュー５３-1〜５３-3に個別に対応するサービスクラスのパケットによってフロー毎に達成されるべき伝送速度との双方もしくは何れか一方が予め精度よく与えられ、かつ既述の伝送区間の障害に起因して生じ得る低下分が適正なマージンとして与えられる場合には、局情報その他の情報として予め与えられてもよい。
【０１１３】
また、本実施形態および上述した第六の実施形態では、キュー５３-1〜５３-3に生じた輻輳状態の解消を目的としてフロー毎に廃棄されるべきパケットの頻度が一定に保たれている。
【０１１４】
しかし、本発明はこのような構成に限定されず、例えば、フロー毎に下記の双方もしくは何れか一方が大きいほど、廃棄されるべきパケットの頻度が段階的に小さな値に設定されることによって、該当するキューに蓄積されるパケットの数の増加が積極的に規制され、そのキューに過剰に蓄積されたパケットの大半が速やかに読み出される環境が確保されてもよい。
【０１１５】
・  対応するキューが輻輳状態に陥った時点から経過した時間
・  先行して廃棄されたパケットの数
以下、本発明の第八の実施形態について説明する。
本実施形態のハードウエアの構成は、既述の第二の実施形態と基本的に同じであるので、ここではその説明を省略する。
【０１１６】
以下、図３を参照して本発明の第八の実施形態の動作を説明する。
帯域監視部３１は、既述の第七の実施形態と同じ手順に基づいて、「最大有能速度」、標準値、廃棄されたパケットの数Ｄcf、廃棄の対象とならなかったパケットの数ｄcfを求める。
また、帯域監視部３１は、キュー５３-1〜５３-3の何れかの輻輳状態が継続している期間には、下記の処理を行う。
【０１１７】
(1) 該当するクラス識別子ｃ、このクラス識別子ｃのパケットが属し得るフローのフロー識別子ｆとの全ての組み合わせについて、上述したパケットの数Ｄcfの総和ΣＤと、廃棄の対象とならなかったパケットの数ｄcfの総和Σｄとを算出し、かつ下式で示される判別値Ｊを算出する。
Ｊ＝ΣＤ／(ΣＤ＋Σｄ)
(2) その判別値Ｊが規定の下限値を下回るか否かを判別する。
【０１１８】
(3) この判別の結果が真である場合に限って、下記の処理(a)、(b) の何れかを行う。
(a) 該当するサービスクラスに関する限り、全てのフローに個別に対応したパケットの数Ｄcf、パケットの数ｄcfを下式に基づいて更新する。
Ｄcf＝−Ｄcf
ｄcf＝０
(b) 上述した処理(a) に併せて、下記の処理を行う。
【０１１９】
上記の判別値Ｊの値が規定の下限値を下回るフローに対応したパケットの数Ｄcfについては、予め与えられ、あるいはフロー制御の方式に適応した値として算出された正数αに対して下式で示される値に更新する。
Ｄcf＝−Ｄcf−α
すなわち、輻輳状態に陥ったキューに蓄積され得るパケットの内、廃棄されるべき数のパケットの大半が廃棄されたときには、フロー毎に引き続いて廃棄されるべきパケットの残数が有効に引き渡されつつ、これらのフローの全てに属するパケットが廃棄の対象となる。
【０１２０】
このように本実施形態によれば、輻輳状態に一端陥ったキューには、そのキューに蓄積され得るパケットの内、実効的なレートが他のフローに比べて小さい特定のフローに属するパケットが長時間に渡って生起しない場合であっても、多くの新たなパケットがさらに蓄積され、そのためにこの輻輳状態が無用に続き、あるいは再発することが回避される。
【０１２１】
なお、本実施形態では、既述の判別値Ｊは、全てのフローに属する新たなパケットの内、廃棄されたパケットの数の総和ΣＤと、廃棄されなかったパケットの数との総和Σｄとに基づいて算出されている。
しかし、本発明はこのような構成に限定されず、「輻輳状態に陥ったキューに蓄積されることなく廃棄されるべきパケットの内、大半のフローに属する全てのパケットが廃棄された」ことが所望の確度で識別されるならば、例えば、個々のフローに対応した比（＝Ｄcf／(Ｄcf＋ｄcf)) の統計的な分散が判別値Ｊに代えて適用されてもよい。
【０１２２】
また、上述した各実施形態では、キュー５３-1〜５３-3の何れかが輻輳状態に陥っているときに、該当するキューに蓄積されることなく廃棄されるべきパケットを選択する処理が帯域監視部３１によって行われている。
しかし、このような処理の全てまたは一部は、廃棄の対象となり得る新たなパケットのサービスクラスとそのパケットが属するフローとの識別が確実に行われるならば、キュー管理部３３によって行われ、あるいはそのキュー管理部３３および帯域管理部３１とは別体に備えられた構成要素によって行われてもよい。
【０１２３】
さらに、本発明は、上述した実施形態に限定されるものではなく、本発明の範囲において、多様な形態による実施形態が可能であり、かつ構成装置の一部もしくは全てに如何なる改良が施されてもよい。
以下、上述した各実施形態に開示された発明の構成を階層的・多面的に整理し、かつ付記項として順次列記する。
【０１２４】
（付記１）  入力されたパケットの列のレートをこれらのパケットが個別に属するフロー毎に規定の上限値以下に調整するレート制御手段１１と、
前記入力されたパケットが属し得る個々のクラスに対応して備えられ、これらのクラスのパケットの先入れ先出し方式に基づく蓄積および送出に供されるキュー１２-1〜１２-Nと、
前記キュー１２-1〜１２-Nの内、蓄積されているパケットの情報量が規定の閾値を超えるキューを識別するキュー監視手段１３と、
前記レート制御手段１１によってレートが調整され、かつ前記キュー監視手段１３によって識別されたキューに格納されるべき新たなパケットが属するフロー毎に、その新たなパケットを所定の頻度で廃棄するバッファ管理手段１４と
を備えたことを特徴とするフロー制御装置。(1)
（付記２）  付記１に記載のフロー制御装置において、
バッファ管理手段１４は、
レート制御手段１１と一体化され、そのレート制御手段１１に備えられ、かつ入力された個々のパケットが属するフローを識別する手段を共用する
ことを特徴とするフロー制御装置。(2)
（付記３）  付記１または付記２に記載のフロー制御装置において、
入力されたパケットの列のレートをフロー毎に監視するレート監視手段１５を備え、
バッファ管理手段１４は、
前記レート監視手段１５によって監視されたレートのクラス毎の比率、またはその比率の単調増加関数として与えられる比率に等しい頻度で、キュー１２-1〜１２-Nの内、レート制御手段１１によってレートが調整されたパケットのクラスに対応するキューにそのパケットを蓄積する
ことを特徴とするフロー制御装置。(3)
（付記４）  付記１〜３に記載のフロー制御装置において、
バッファ管理手段１４は、
フロー毎にパケットを廃棄した実績を記録し、その実績があるフローに属する新たなパケットを廃棄の対象から除外し、またはこの実績がないフローに属する新たなパケットが廃棄されるべき頻度より小さな頻度で廃棄する
ことを特徴とするフロー制御装置。(4)
（付記５）  付記１〜３に記載のフロー制御装置において、
バッファ管理手段１４は、
フロー毎にパケットを廃棄した回数を計数し、その回数が規定の値以上であるフローに属するパケットを廃棄の対象から除外し、またはこの回数がその規定の値未満であるフローに属する新たなパケットが廃棄されるべき頻度より小さな頻度で廃棄する
ことを特徴とするフロー制御装置。
【０１２５】
（付記６）  付記４に記載のフロー制御装置において、
バッファ管理手段１４は、
パケットが廃棄された実績をそのパケットが属するフローに対応付けて保持し、かつキュー監視手段１３によって識別されたキューに蓄積されるべきパケットの内、個別に属するフローに対応した実績が保持されているパケットを廃棄の対象から除外し、またはこの実績がないフローに属する新たなパケットが廃棄されるべき頻度より小さな頻度で廃棄する
ことを特徴とするフロー制御装置。
【０１２６】
（付記７）  付記５に記載のフロー制御装置において、
バッファ管理手段１４は、
パケットが廃棄された回数をそのパケットが属するフローに対応付けて保持し、かつキュー監視手段１３によって識別されたキューに蓄積されるべきパケットの内、個別に属するフローに対応した回数が所定の値を上回るパケットを廃棄の対象から除外し、またはこの回数がその所定の値未満であるフローに属する新たなパケットが廃棄されるべき頻度より小さな頻度で廃棄する
ことを特徴とするフロー制御装置。
【０１２７】
（付記８）  付記５に記載のフロー制御装置において、
バッファ管理手段１４は、
パケットが廃棄された回数を時間の経過に応じて小さく重み付けしつつそのパケットが属するフローに対応付けて保持し、かつキュー監視手段１３によって識別されたキューに蓄積されるべきパケットの内、個別に属するフローに対応した回数が保持されているパケットを廃棄の対象から除外し、またはこの回数が少ないほど小さな頻度でそのパケットを廃棄する
ことを特徴とするフロー制御装置。
【０１２８】
（付記９）  付記１〜８に記載のフロー制御装置において、
キュー監視手段１３は、
キュー１２-1〜１２-Nに個別に蓄積されているパケットの情報量が規定の閾値を超える程度を識別し、
バッファ管理手段１４は、
前記キュー監視手段１３によって識別された程度が大きいキューほど大きな頻度で、そのキューに格納されるべき新たなパケットを廃棄する
ことを特徴とするフロー制御装置。
【０１２９】
（付記１０）付記１〜９にフロー制御装置において、
バッファ管理手段１４は、
キュー１２-1〜１２-Nに個別に対応するクラスに適応した最大値が予め与えられ、その最大値以下の頻度でそのクラスの新たなパケットを廃棄する
ことを特徴とするフロー制御装置。
【０１３０】
（付記１１）付記１〜１０に記載のフロー制御装置において、
バッファ管理手段１４は、
入力されたパケットが属し得る個々のクラスに確保されるべき伝送帯域の幅に適応し、かつ共通のフローに属して廃棄が許容されるべき新たなパケットの最大の数が個々のフローについて与えられ、これらのフロー毎にその最大の数の新たなパケットを廃棄した後に後続する新たなパケットの廃棄を差し控える
ことを特徴とするフロー制御装置。
【０１３１】
（付記１２）付記１〜１０に記載のフロー制御装置において、
キュー１２-1〜１２-Nに個別に対応したクラス毎に確保されるべき最大の伝送帯域の幅を把握する伝送帯域監視手段１６を備え、
バッファ管理手段１４は、
前記キュー１２-1〜１２-Nに対応したクラス毎に、前記伝送帯域監視手段１６によって把握された伝送帯域の幅に適応し、かつ共通のフローに属して廃棄が許容されるべき新たなパケットの最大の数が個々のフローについて与えられ、これらのフロー毎にその最大の数以上の新たなパケットを廃棄した後に後続する新たなパケットの廃棄を差し控える
ことを特徴とするフロー制御装置。
【０１３２】
（付記１３）付記１〜１０に記載のフロー制御装置において、
バッファ管理手段１４は、
キュー監視手段１３によって識別されたキューに格納されるべきパケットが属し得るフロー毎に、そのキューに対応したクラスに確保されるべき伝送帯域の幅に適応する基準値が与えられ、先行して廃棄されたパケットと廃棄されなかったパケットとの数もしくは情報量の総和の差または比がその基準値以上となった後に後続する新たなパケットの廃棄を差し控える
ことを特徴とするフロー制御装置。
【０１３３】
（付記１４）付記１〜１３に記載のフロー制御装置において、
バッファ管理手段１４は、
フロー毎に時系列の順に小さな頻度で新たなパケットを廃棄する
ことを特徴とするフロー制御装置。
（付記１５）付記１〜１４に記載のフロー制御装置において、
バッファ管理手段１４は、
キュー１２-1〜１２-Nに個別に対応するクラスの新たなパケットが廃棄された比率の分散が所定の閾値を下回ったときに、これらの比率の内、そのクラスの新たなパケットに対応する比率が大きいほど大きな頻度でその新たなパケットを廃棄する
ことを特徴とするフロー制御装置。
【０１３４】
（付記１６）付記１ないし付記１５の何れか１項に記載され、かつ入力されたパケットの列のレート制御に併せて、これらのパケットのクラスに個別に対応したキューのバッファ管理をフロー毎に行うフロー制御装置２１と、
所定のリンクまたは端末に、前記フロー制御装置２１によって行われたレート制御およびバッファ管理の下で与えられたパケットを送出する通信インタフェース手段２２と
を備えたことを特徴とするノード装置。(5)
【０１３５】
【発明の効果】
上述したように請求項１に記載のフロー制御装置では、輻輳状態の解消を目的として該当するキューに対する蓄積が見合わされ、かつ廃棄されるべきパケットがそのフローが属するフローの如何にかかわらず選択される従来例に比べて、特定のフローに属するパケットが他のフローに属するパケットより著しく大きな頻度で廃棄されることが回避される。
また、請求項１に記載のフロー制御装置では、ランニングコストの削減に併せて応答性の向上が図られる。
【０１３６】
また、請求項２に記載のフロー制御装置では、コストの削減と信頼性の向上とが図られる。
さらに、請求項３に記載の第三のフロー制御装置では、余剰の伝送帯域がフロー毎のレートの如何にかかわらず各フローに一律に割り付けられる場合に比べて、そのレートが低い特定のフローの伝送品質が他のフローの伝送品質に比べて大幅に劣化することが回避される。
【０１３７】
さらに、請求項１ないし請求項３に記載の発明の下位概念の発明では、個々のフローのレートが多様に異なり、あるいは刻々と変化し得る場合であっても、上述したパケットの廃棄に伴って特定のフローの伝送品質が他のフローの伝送品質に比べて大幅に劣化することが回避される。
【０１３８】
また、請求項１に記載の発明の下位概念の発明では、何れかのキューが間欠的に輻輳状態に陥る場合であっても、ランニングコストの削減に併せて応答性の向上が図られる。
さらに、請求項１ないし請求項３に記載の発明に関連した第一の発明では、各フローのレートの組み合わせの如何にかかわらず、輻輳状態が解消された時点が無用に遅れることなく識別される。
【０１３９】
また、請求項１ないし請求項３に記載の発明に関連した第二の発明では、輻輳の度合いがキュー毎に何ら識別されない場合に比べて、その輻輳の無用な加速が規制され、この輻輳の解消が効率的に達成される。
さらに、請求項１ないし請求項３に記載の発明に関連した第三の発明では、所望の形態によるフロー制御が確度高く実現され、そのフロー制御の過程でフローおよびサービスクラスの単位に所望の伝送容量が確保される。
【０１４０】
また、請求項１ないし請求項３に記載の発明に関連した第四の発明では、伝送品質が無用に劣化することなく輻輳状態が解消される。
さらに、請求項１ないし請求項３に記載の発明に関連した第五の発明では、伝送品質が無用に劣化することなく、その輻輳状態の緩和や加速の度合い、後続する伝送区間その他の稼働状況に対して柔軟に適応した形態で輻輳状態が解消される。
【０１４１】
また、請求項１ないし請求項３に記載の発明に関連した第六の発明では、伝送速度が小さいフローに属するパケットが不適正に多数に亘って廃棄されることが条件となることなく、輻輳状態の解消が達成され、あるいは識別される。
さらに、請求項１ないし請求項３に記載の発明に関連した第七の発明では、輻輳状態に陥ったキューに蓄積されたパケットの大半は、そのキューがこの輻輳状態に陥った直後に速やかに、かつ確度高く読み出される。
【０１４２】
また、請求項１ないし請求項３に記載の発明に関連した第八の発明では、輻輳状態に陥ったキューに多くの新たなパケットがさらに蓄積され、この輻輳状態が無用に加速されることが回避される。
さらに、請求項４に記載の発明では、フロー毎の伝送品質が均一に保たれ、かつサービス品質が高く維持される。
【０１４３】
したがって、これらの発明が適用された伝送系では、トラヒックの分布、キューならびにパケットのサイズその他の構成の如何にかかわらず、伝送品質が適正に、かつ安定に保たれると共に、サービス品質と総合的な信頼性とが高められる。
【図面の簡単な説明】
【図１】本発明にかかわるフロー制御装置の原理ブロック図である。
【図２】本発明にかかわるノード装置の原理ブロック図である。
【図３】本発明の第一ないし第八の実施形態を示す図である。
【図４】本発明の第一ないし第五の実施形態における帯域監視部の動作フローチャートである。
【図５】本発明の第一ないし第四の実施形態におけるキュー管理部の動作背フローチャートである。
【図６】廃棄制御レジスタの構成を示す図である。
【図７】本発明の第二および第四の実施形態における帯域監視部の動作フローチャートである。
【図８】インタネットにおいてエンド・ツー・エンドで保証されるべきサービスクラスの一例を示す図である。
【図９】ノードの入り線においてフロー制御を行う装置の構成例を示す図である。
【図１０】目的キューの長さに応じてパケットが廃棄されるべき確率の一例を示す図である。
【符号の説明】
１１  レート制御手段
１２，５３  キュー
１３  キュー監視手段
１４  バッファ管理手段
１５  レート監視手段
１６  伝送帯域監視手段
２１  フロー制御装置
２２  通信インタフェース手段
３１，５１  帯域監視部
３１Ｒａ，３１Ｒｂ，３１Ｒｃ  廃棄制御レジスタ
３２  クラス識別語
３３  キュー管理部
５２  輻輳制御部
５４  スケジューラ
【図１】
0004512699.tif 000002
【図２】
0004512699.tif 000003
【図３】
0004512699.tif 000004
【図４】
0004512699.tif 000005
【図５】
0004512699.tif 000006
【図６】
0004512699.tif 000007
【図７】
0004512699.tif 000008
【図８】
0004512699.tif 000009
【図９】
0004512699.tif 000010
【図１０】
0004512699.tif 000011