(57)【要約】  リンク上に流れるパケットベースのトラフィックのカレントレートを移動平均として計算し、算出したカレントレートと所望レートの間の総エラー数を計算し、また、算出した総エラー数に応じて、パケットを流すことができるか否かを決定することで、パケットベースのトラフィックの流れを制御し、所望レートを取得する。カレントレートと所望レートの間の総エラー数が、カレントレートが所望レート未満であることを示す場合には、パケットの流れが許可され、また、総エラー数が、カレントレートが所望レートよりも大きいことを示す場合には、パケットの流れは許可されない。カレントレート及び総エラー数の最小値を人工的に制御することで、バーストの大きさを制御することが可能である。フロー制御アルゴリズムを使用して、レートシェーピング又はレート制限を行うことができる。
2005512365.tif 000002
【特許請求の範囲】
【請求項１】
所望レートを満たすべく、パケットベースのトラフィックの流れを制御する方法であって、
リンク上にあるパケットベースのトラフィックのカレントレートを、移動平均として計算し；
前記算出したカレントレートと前記所望レートの間の総エラー数を計算し；
前記算出した総エラー数に応じて、パケットを流すことが可能であるか否かを決定する方法。
【請求項２】
前記パケットを流すことができるか否かの決定において、前記総エラー数がエラー閾値未満である場合にはパケットの流れを許可し、前記総エラー数が前記エラー閾値よりも高い場合にはパケットの流れを許可しない、請求項１に記載の方法。
【請求項３】
前記パケットを流すことができるか否かの決定において、前記総エラー数がゼロ未満又はゼロと等しい場合にはパケットの流れを許可し、前記総エラー数がゼロよりも大きい場合にはパケットの流れを許可しない、請求項１に記載の方法。
【請求項４】
前記パケットを流すことができるか否かの決定において、前記総エラー数が、取得したトラフィックのレートが所望レート未満であることを示す場合にはパケットの流れを許可し、前記総エラー数が、取得したトラフィックのレートが所望レートよりも高いことを示す場合にはパケットの流れを許可しない、請求項１に記載の方法。
【請求項５】
さらに、前記カレントレートの最小値を確立し、前記カレントレートが最小値未満である場合に前記カレントレートの値を調整する、請求項１に記載の方法。
【請求項６】
さらに、前記総エラー数の最小値を確立し、前記総エラー数が前記最小値未満である場合に前記総エラー数の値を調整する、請求項１に記載の方法。
【請求項７】
さらに、
前記カレントレート及び前記総エラー数の最小値を確立し；
前記カレントレートが前記カレントレートの前記最小値未満である場合に、前記カレントレートの値を調整し；
前記総エラー数が前記総エラー数の前記最小値未満である場合に、前記総エラー数の値を調整する、請求項１に記載の方法。
【請求項８】
前記カレントレートが、前記リンクに関連した実トラフィック情報を用いて計算される、請求項１に記載の方法。
【請求項９】
前記カレントレート及び前記総エラー数が計算され、パケットを流すことができるか否かの決定が各サイクルについて繰り返され、各Δｔについて１つのサイクルが発生する、請求項１に記載の方法。
【請求項１０】
前記カレントレートが重み付き移動平均として計算される、請求項１に記載の方法。
【請求項１１】
前記カレントレートが次のとおり計算され：
Current_Rate＝Previous_Rate＋(Ｗａ・Ｃ−Ｗｂ・Previous_Rate)；
この場合、Ｃはビット数、Ｗａ及びＷｂは重量を表す、請求項１０に記載の方法。
【請求項１２】
次の計算サイクルの前記Previous_Rateが、先行の計算サイクルで算出したCurrent_Rateに設定される、請求項１１に記載の方法。
【請求項１３】
ＷａがＮｃ及びΔｔの関数であり、Δｔがサンプリング・インターバルであり、Ｎｃが前記サンプリング・インターバルの数である、請求項１１に記載の方法。
【請求項１４】
ＷａがＷａ＝１／（Ｎｃ・Δｔ）として定義され、Δｔはサンプリング・インターバルであり、Ｎｃは前記サンプリング・インターバルの数である、請求項１１に記載の方法。
【請求項１５】
前記ＷｂがＮｃの関数であり、Ｎｃはサンプリング・インターバルの数である、請求項１１に記載の方法。
【請求項１６】
ＷｂがＷｂ＝１／Ｎｃとして定義され、Ｎｃはサンプリング・インターバルの数である、請求項１１に記載の方法。
【請求項１７】
さらに、Initial_Rateを確立し、前記Current_Rateが前記Initial_Rateを下回る場合に、前記Current_Rateを前記Initial_Rateに調整する、請求項１１に記載の方法。
【請求項１８】
前記総エラー数が、
Current_Error＝Previous_Error＋(Current_Rate−Desired_Rate)
として計算される、請求項１１に記載の方法。
【請求項１９】
さらに、前記Current_Errorの最小閾値を確立し、前記Current_Errorが前記閾値を下回る場合に、前記Current_Errorを前記閾値に調整する、請求項１８に記載の方法。
【請求項２０】
次の計算サイクルのための前記Previous_Errorが、先行する計算サイクルにおいて算出したCurrent_Errorに設定される、請求項１８に記載の方法。
【請求項２１】
前記Current_Errorがゼロ未満又はゼロと等しい場合にはパケットの流れを許可し、前記Current_Errorがゼロよりも大きい場合にはパケットの流れを許可しない、請求項１８に記載の方法。
【請求項２２】
さらに、前記パケットを流すことができるか否かの決定に応じて、スイッチのオン・オフを切り替える、請求項１に記載の方法。
【請求項２３】
所望レートを満たすべく、入力リンクと出力リンクの間のパケットベースのトラフィックの流れを制御するシステムであって、
前記入力リンクと前記出力リンクの間を接続するスイッチを備え、前記スイッチが、前記スイッチをオンにすると、前記入力リンクから前記出力リンクへのトラフィックの流れを可能にし、前記スイッチをオフにすると、パケットの流れを許可せず；
前記スイッチを制御するべく接続したレートシェーピング論理をさらに備え、前記レートシェーピング論理が；
前記入力リンクと出力リンクのうちの一方上に流れるパケットベースのトラフィックのカレントレートを移動平均として計算する手段と；
前記算出したカレントレートと前記所望レートの間の総エラー数を計算する手段と；
前記算出した総エラー数に応じて、パケットを前記出力リンクに流すことができるか否かを決定する手段とを含む、システム。
【請求項２４】
前記パケットを流すことができるか否かの決定において、前記総エラー数がエラー閾値未満である場合にはパケットの流れを許可し、前記総エラー数が前記エラー閾値よりも高い場合にはパケットの流れを許可しない、請求項２３に記載のシステム。
【請求項２５】
前記パケットを流すことができるか否かの決定において、前記総エラー数がゼロ未満又はゼロと等しい場合にはパケットの流れを許可し、前記総エラー数がゼロよりも大きい場合にはパケットの流れを許可しない、請求項２３に記載のシステム。
【請求項２６】
前記パケットを流すことができるか否かの決定において、前記総エラー数が、取得したトラフィックのレートが所望レート未満であることを示す場合にはパケットの流れを許可し、前記総エラー数が、取得したトラフィックのレートが所望レートよりも高いことを示す場合にはパケットの流れを許可しない、請求項２３に記載のシステム。
【請求項２７】
前記レートシェーピング論理が、前記カレントレートの最小値を確立するための、また、前記カレントレートが該最小値未満である場合に、前記カレントレートの値を調整するための論理を含む、請求項２３に記載のシステム。
【請求項２８】
前記レートシェーピング論理が、前記総エラー数の最小値を確立するための、また、前記総エラー数が該最小値未満である場合に、前記総エラー数の値を調整するための論理を含む、請求項２３に記載のシステム。
【請求項２９】
前記レートシェーピング論理が、
前記カレントレート及び前記総エラー数の最小値を確立するため；
前記カレントレートが該最小値未満である場合に、前記カレントレートの値を調整するため；
前記総エラー数が該最小値未満である場合に、前記総エラー数の値を調整するための論理を含む、請求項２３に記載のシステム。
【請求項３０】
前記カレントレートが、前記入力リンクと出力リンクの一方に関連した実トラフィック情報を用いて計算される、請求項２３に記載のシステム。
【請求項３１】
前記カレントレート及び前記総エラー数が計算され、前記リンクからパケットを流すことができるか否かの決定が各サイクルについて繰り返され、各Δｔについて１つのサイクルが発生する、請求項２３に記載のシステム。
【請求項３２】
前記カレントレートが重み付き移動平均として計算される、請求項２３に記載のシステム。
【請求項３３】
前記カレントレートが次のとおり計算され：
Current_Rate＝Previous_Rate＋(Ｗａ・Ｃ−Ｗｂ・Previous_Rate)；
この場合、Ｃはビット数し、Ｗａ及びＷｂは重量を表す、請求項２３に記載のシステム。
【請求項３４】
次の計算サイクルの前記Previous_Rateが、先行の計算サイクルで算出したCurrent_Rateに設定される、請求項３３に記載のシステム。
【請求項３５】
ＷａがＮｃ及びΔｔの関数であり、Δｔがサンプリング・インターバルであり、Ｎｃが前記サンプリング・インターバルの数である、請求項３３に記載のシステム。
【請求項３６】
ＷａがＷａ＝１／（Ｎｃ・Δｔ）として定義され、Δｔがサンプリング・インターバルであり、Ｎｃが前記サンプリング・インターバルの数である、請求項３３に記載のシステム。
【請求項３７】
ＷｂがＮｃの関数であり、Ｎｃがサンプリング・インターバルの数である、請求項３３に記載のシステム。
【請求項３８】
ＷｂがＷｂ＝１/Ｎｃとして定義され、Ｎｃがサンプリング・インターバルの数である、請求項３３に記載のシステム。
【請求項３９】
前記レートシェーピング論理がさらに、Initial_Rateを確立するため、また、前記Current_Rateが前記Initial_Rateを下回る場合に、前記Current_Rateを前記Initial_Rateに調整するための論理を含む、請求項３３に記載のシステム。
【請求項４０】
前記総エラー数が、
Current_Error＝Previous_Error＋(Current_Rate−Desired_Rate)
として計算される、請求項３３に記載のシステム。
【請求項４１】
前記レートシェーピング論理がさらに、前記Current_Errorの最小閾値を確立するため、また、前記Current_Errorが前記閾値を下回る場合に、前記Current_Errorを前記閾値に調整するための論理を含む、請求項４０に記載のシステム。
【請求項４２】
前記次の計算サイクルが、先行の計算サイクルで算出したCurrent_Errorに設定される、請求項４０に記載のシステム。
【請求項４３】
前記Current_Errorがゼロ未満又はゼロと等しい場合にはパケットの流れを許可し、前記Current_Errorがゼロよりも大きい場合にはパケットの流れを許可しない、請求項４０に記載のシステム。
【請求項４４】
さらに、前記リンクからパケットを流すことができるか否かの決定に応じて、スイッチのオン・オフを切り替える、請求項２３に記載のシステム。
【請求項４５】
所望レートを満たすべく、バッファから出力リンク上へと流れるパケットベースのトラフィックの流れを制御する方法であって、
前記出力リンク上にあるパケットベースのトラフィックのカレントレートを、移動平均として計算し；
前記算出したカレントレートと前記所望レートの間の総エラー数を計算し；
前記算出した総エラー数に応じて、前記バッファから該出力リンク上へのパケットをディスパッチできるか否かを決定する方法。
【請求項４６】
前記バッファからのパケットをディスパッチできるか否かの決定において、前記総エラー数がエラー閾値未満である場合にはパケットのディスパッチを許可し、前記総エラー数が前記エラー閾値よりも高い場合には前記バッファからのパケットのディスパッチを許可しない、請求項４５に記載の方法。
【請求項４７】
前記バッファからパケットをディスパッチできるか否かの決定において、前記総エラー数がゼロ未満又はゼロと等しい場合には前記バッファからのパケットのディスパッチを許可し、前記総エラー数がゼロよりも大きい場合には前記バッファからのパケットのディスパッチを許可しない、請求項４５に記載の方法。
【請求項４８】
前記バッファからパケットをディスパッチできるか否かの決定において、前記総エラー数が、取得したトラフィックのレートが前記所望レート未満であることを示す場合には前記バッファからのパケットのディスパッチを許可し、前記総エラー数が、前記取得したトラフィックのレートが所望レートよりも高いことを示す場合には前記バッファからのパケットのディスパッチを許可しない、請求項４５に記載の方法。
【請求項４９】
さらに、前記カレントレートの最小値を確立することで、パケット・バーストの大きさを制御し、前記カレントレートが前記カレントレートに確立した最小値未満である場合に、前記カレントレートの値を調整する、請求項４５に記載の方法。
【請求項５０】
さらに、前記総エラー数の最小値を確立することで、パケット・バーストの大きさを制御し、前記総エラー数が前記総エラー数に確立した値未満である場合に、前記総エラー数の値を調整する、請求項４５に記載の方法。
【請求項５１】
さらに、
前記カレントレート及び前記総エラー数の最小値を確立し；
前記カレントレートが前記カレントレートに確立した最小値未満である場合に、前記カレントレートの値を調整することで、パケット・バーストの大きさを制御し；
前記総エラー数が前記総エラー数に確立した最小値未満である場合に、前記総エラー数の値を調整することで、前記パケット・バーストの大きさを制御する、請求項４５に記載の方法。
【請求項５２】
前記カレントレートが次のとおり計算され、
Current_Rate＝Previous_Rate＋(Ｗａ・Ｃ−Ｗｂ・Previous_Rate)；
この場合、Ｃはビット数、Ｗａ及びＷｂは重量を表す、請求項４５に記載の方法。
【請求項５３】
さらに、Initial_Rateを確立し、前記Current_Rateが前記Initial_Rateを下回る場合に、前記Current_Rateを前記Initial_Rateに調整する、請求項５２に記載の方法。
【請求項５４】
前記総エラー数が、
Current_Error＝Previous_Error＋(Current_Rate−Desired_Rate)
として計算される、請求項５２に記載の方法。
【請求項５５】
さらに、前記Current_Errorの最小閾値を確立し、前記Current_Errorが前記閾値を下回る場合に、前記Current_Errorを前記閾値に調整する、請求項５４に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケットベースのコンピュータネットワークに関し、より詳細には、パケットベースのネットワークにおけるトラフィックレートの制御に関する。
【背景技術】
【０００２】
パケットベースのネットワークは、データをバースト伝送するものとして知られている。バースト型のトラフィックは、ネットワーク内に混乱を生じさせ、入力バッファが一杯になった際にパケットがドロップする可能性がある。ネットワークのパフォーマンスを改善し、サービス品質（ＱｏＳ）を保証するためには、ネットワーク内の多くの場所においてトラフィックの流れの、特定の所望レートへの制御を可能にすることが必要である。トラフィックの流れを制御するための２つの技術は、一般にレートシェーピングとレート制限に関連している。レートシェーピングは、所与のアルゴリズムに従って、ある場所に到達したパケットをバッファし、該バッファを離れるパケットの流れを制御することで所望のレートを満たす。パケットはバッファされるので、パケットのバーストを吸収した後に、制御された方法でディスパッチできるために、入力パケットのドロップが生じることがない。レート制御では、ある場所に入力されたパケットのレートを測定し、次に、所望レートを超過して到達したパケットのドロップを実施する。
【０００３】
レートシェーピング又はレート制限を達成するために使用できるいくつかの共通のアルゴリズムには、既知のリーキー・バケット・アルゴリズムとトークン・バケット・アルゴリズムが含まれる。レートシェーピングを達成するためのリーキー・バケット・アルゴリズムの使用では、入力パケットをバッファした後に、該バッファから、一定のレート、すなわちリークレート（例えば、バイト／秒において測定）にて、パケットをディスパッチする。たとえば、サイズＣのパケット（つまり、バイトで表される）が受信されると、Ｃ／リークレートの期間中はバッファ内に保持され、その後、バッファからディスパッチされる。バッファが空状態にある間は、リークレートで表される伝送容量は使用されず、後続のパケットのバーストのために累積されることもない。したがって、ノートラフィック期間後に、新規のパケットのバーストがバッファ内に到達すると、この新規のパケットはやはりバッファされ、リークレートにてディスパッチされる。この技術は、パケットベースのネットワーク・トラフィックにバースト型性質の要因となる柔軟性を与えるものではない。
【０００４】
トークン・バケット・アルゴリズムの使用には、一定レートでのバケットへのビット値（つまり、１，０００バイト、５０セル等）の割り当てと、必須の数のビット、バイト、セルがバケット内に累積されている場合のみにおける、バッファからのパケットのディスパッチの許可が含まれる。ノートラフィック期間中には、ビットが、一定レートにてバケット内に累積し続け、後続のトラフィックのバーストが、この累積したビットを使用することができる。この技術は、ネットワークのバースト型性質の要因である柔軟性を提供するが、ノートラフィック期間中にバケットが過剰に累積した場合には、後続のパケット・バーストがシェーピングされない可能性がある。許可可能なバーストのサイズは、バケット内に累積できるビット数に最大値を設定することで制限することができるが、バケットの最大値は、大型のパケットがバッファ内にトラップされることを防止するために、少なくとも予想される最大のパケットでなくてはならない。予想される最大サイズのパケットの最大バケットサイズを設定する上での欠点は、比較的小型のパケットのバーストの多くが、シェーピングされないまま残ってしまうことである。
【０００５】
レートシェーピング又はレート制限に使用できる別のアルゴリズムには、ある場所においてカレントトラフィックレートを計算し、カレントレートを所望レートと比較して、後述のパケットをディスパッチすべきか否かの決定を行うことが含まれる。アルゴリズムによれば、カレントレートが所望レート未満である場合には、パケットの流れが許可され、また、カレントレートが所望レートよりも大きい場合には、パケットの流れが許可されない。レートシェーピングに使用されるこのような既知のアルゴリズムは、指数加重移動平均（ＥＷＭＡ）アルゴリズムと呼ばれる。ＥＷＭＡアルゴリズムの一例は次式で表すことができる。
Current_RateN＝(1−Gain)・Current_RateN−1＋Gain・BytesN
ここで、ｔＮ＋１＝ｔＮ＋Δｔ
この場合、Current_RateNは、Ｎ番目のサンプリング・インターバルにおけるＥＷＭＡであり、Current_RateN−1は、Ｎ−１番目のサンプリング・インターバルにおけるＥＷＭＡであり、BytesNは、Ｎ番目のサンプリング・インターバル中にディスパッチされたバイト数であり、各サンプリング・インターバルはΔｔの期間を有する。Gainが、本質的に低パスフィルタ動作であるものの時間定数（つまり周波数応答）を制御する。バッファからのパケットのディスパッチに使用する際に、Current_RateNが事前定義した所望レート（Desired_Rateと呼ばれる）よりも高い場合には、パケットはディスパッチされない。Current_RateNがDesired_Rate未満である場合には、パケットはディスパッチされる。バッファからのパケットのディスパッチを制御するアルゴリズムは、従来技術において次式で表される。
If(Current_RateN>Desired_Rate)
No packets dispatched
else
Packets dispatched
【０００６】
図１は、バッファがパケットで完全にロードされた状態にあるレートシェーピング・システムにおける上述のＥＷＭＡアルゴリズムを適用した結果生じた時間（Δｔ単位）に対する、トラフィック１０４のカレントレートの例証的なグラフを示す。最初の時間ｔ０にて、トラフィックのバーストがディスパッチされ、ＥＷＭＡとして計算されたカレントレートが所望レートを超えて上昇するが、この場合、所望レートを水平な破線１０６で示している。カレントレートが所望レートよりも高い限り、トラフィックレートはディスパッチされず、また、カレントレートの安定性が低下する。カレントレートが所望レート（つまり、時間ｔ２）未満にまで低下すると、新規のトラフィックのバーストがディスパッチされ、カレントレートが再び所望レートよりも上昇する。図１に示すように、完全にロードされた状態のシステムでは、トラフィックのカレントレートのほぼ全体が所望レートを上回るが、これは、カレントレートが所望レート未満に低下する瞬間により多くのパケットがディスパッチされるためである。カレントレートのほぼ全体が所望レートを上回っているため、完全なローディングの期間にかけて取得される伝送レートが所望レートよりも高くなり、この場合、取得されるレートは、ビットをディスパッチした時間で割った、ディスパッチされた総ビット数として計算される。例えば、図１では、完全にローディングした状態のシステムにおいて、時間ｔ０〜ｔ９にかけて取得されたレート１０８は所望レートよりも高い。理想的には、取得されたレートは所望レートと等しくなければならない。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
特定のネットワーク・トラフィックの所望レートへの制御を可能にする必要性に鑑み、また、従来技術のレートシェーピング・アルゴリズム及びレート制限・アルゴリズムの欠点に鑑み、パケットベースのトラフィックレートを効率的に制御することが可能な、柔軟で、特にハードウェア内での実現が容易なアルゴリズムが必要である。
【課題を解決するための手段】
【０００８】
パケットベースのトラフィックの流れを、所望レートを満たすべく制御する方法及びシステムでは、リンク上にあるパケットベースのトラフィックのカレントレートを、移動平均として計算し、算出したカレントレートと所望レートの間の総エラー数を計算し、算出した総エラー数に応じて、パケットを流すことが可能であるか否かを決定する。ある実施形態では、カレントレートと所望レートの間の総エラー数がゼロ未満、又はゼロと等しい場合には、バッファからリンク上にパケットがディスパッチされ、総エラー数がゼロよりも大きい場合には、パケットがバッファ内に保持される。カレントレートと所望レートの間の総エラー数に応じてパケットの流れが制御されるため、たとえバースト型のトラフィック環境においてでも、取得するトラフィックのレートが所望レートに接近して維持される。
【０００９】
本発明の一実施形態では、総エラー数を閾値と比較して、パケットの流れを許可するか否かを決定する。総エラー数が閾値未満である場合には、パケットの流れが許可され、総エラー数が閾値よりも大きい場合には、パケットの流れは許可されない。ある実施形態では、閾値はゼロであり、総エラー数がゼロ未満、又はゼロと等しい場合には、パケットの流れが許可される。別の実施形態では、総エラー数が、取得されるトラフィックのレートが所望レート未満であることを示す場合には、パケットの流れが許可され、総エラー数が、取得したトラフィックのレートが所望レートよりも高いことを示す場合には、パケットの流れは許可されない。
【００１０】
カレントレートに最小値を確立して、ノートラフィック期間後に流れを許可されたバーストの大きさを制御することができる。カレントレートが最小値未満の場合には、算出したカレントレートを最小値に調整する。同様に、総エラー数に最小値を確立することができ、総エラー数がこの最小値未満である場合には、算出した総エラー数が該最小値に調整される。この両方の技術は、静寂期間から「借りる」ことのできる帯域幅の量を制御するものである。詳細には、後出の（２番目の）技術は、負の留数が大量に累積してしまうことを防止する。
【００１１】
ある実施形態では、カレントレート及び総エラー数を計算し、パケットを流すことができるか否かを決定する工程が各サイクル毎に繰り返され、この場合、Δｔ毎に１サイクルが発生する。
【００１２】
ある実施形態では、カレントレートが次式のとおり計算される。
Current_Rate＝Previous_Rate＋(Ｗａ・Ｃ−Ｗｂ・Previous_Rate)
この場合、Ｃはカレントサイクル中にディスパッチされたビット数を表し、ＷａとＷｂは重量である。上記の公式を使用する場合には、次の計算サイクルのPrevious_Rateを、一つ前の計算サイクルで算出したCurrent_Rateに設定することができる。ある実施形態では、ＷａはＮｃ及びΔｔの関数であり、この場合、Δｔはサンプリング・インターバルであり、Ｎｃはサンプリング・インターバルの定数である。より詳細には、ＷａはＷａ＝１／（Ｎｃ・Δｔ）と定義できる。ある実施形態では、ＷｂはＮｃの関数である。より詳細には、ＷｂはＷｂ＝１／Ｎｃと定義できる。
【００１３】
上記のレート公式を使用する場合、Initial_Rateを確立し、また、Current_RateがInitial_Rate未満に低下した場合に、Current_RateをInitial_Rateに調整することで、トラフィック・バーストの大きさを制御することが可能である。
【００１４】
総エラー数は次式で計算することができる。
Current_Error＝Previous_Error＋(Current_Rate−Desired_Rate)
この場合、Current_Rateは上記の公式に従って計算される。パケット・バーストの大きさは、Current_Errorに最小閾値を確立し、また、Current_Errorが該閾値未満に低下した場合に、Current_Errorを該閾値に調整することで制御できる。上記のエラー表式を用いる場合、次の計算サイクルのPrevious_Errorを、１つ前の計算サイクルで算出したCurrent_Errorに設定する。ある実施形態では、Current_Errorがゼロ未満、又はゼロと等しい場合に、パケットの流れは許可され、Current_Errorがゼロよりも大きい場合に、パケットの流れは許可されない。本発明は、パケットベースのトラフィックの流れを制御する方法及びシステムにおいて実現することができる。この方法及びシステムは、レートシェーピング又はレート制限に使用することができ、また、ユーザが提供したInitial_Rate、Desired_Rate、Ｎｃ、Δｔの入力パラメータを調整することで、アルゴリズムのパフォーマンス特徴を容易に調整することが可能である。
【００１５】
さらに本発明は、レートシェーピングに特化した方法において実現可能であり、この場合、算出したカレントレートと所望レート間の算出した総エラー数に応じて、バッファからパケットがディスパッチされる。
【発明を実施するための最良の形態】
【００１６】
本発明のこれ以外の態様及び利点は、添付の図面と連携した、本発明の原理を例証の方法で示している、これ以降の詳細な記述によって明白となる。
【００１７】
図１は、従来技術に従って、バッファをパケットで完全にロードした状態のレートシェーピング・システムにおいて、ＥＷＭＡアルゴリズムを適用した結果得られたΔｔ単位の時間に対する、トラフィックレートの例証的なグラフを示す。
【００１８】
図２は、本発明のある実施形態に従ってレートシェーピング・アルゴリズムを実現するレートシェーピング・システムを示す。
【００１９】
図３（ａ）は、本発明のある実施形態に従ってレートシェーピング・アルゴリズムの実現から生成されたトラフィックプロファイルのグラフを示す。
【００２０】
図３（ｂ）は、算出したカレントレートと、図３（ａ）から得た所望レートの間の総エラー数のグラフを示す。
【００２１】
図３（ｃ）は、算出したカレントレートと、図３（ｂ）から得た所望レートの間の総エラー数に応じて生成されたスイッチ制御信号のグラフを示す。
【００２２】
図４は、本発明のある実施形態に従って、パケットベースのトラフィックのフローレートを制御して、所望レートを満たすためのプロセスフロー線図を示す。
【００２３】
図５（ａ）は、図４に示したレートシェーピング・アルゴリズムを用いて生成した未調整のレートプロファイルのグラフを示しており、本発明の別の実施形態に従って調整したレートプロファイルの一部分を含んでいる。
【００２４】
図５（ｂ）は、算出したレートと、図５（ａ）のレートプロファイルから得た所望レートの間の未調整の総エラー数を示すグラフであり、本発明の別の実施形態に従って調整された総エラー数の一部分を含んでいる。
【００２５】
図６は、本発明の別の実施形態に従ってノートラフィックの期間に関連して変更した所望レートを満たすために、パケットベースのトラフィックのフローレートを制御するプロセスフロー線図を示す。
【００２６】
図７は、同一の出力リンクに接続し、バッファ固有のスイッチにより制御された２個のバッファの例証的な実施形態を示し、この場合、本発明の実施形態に従って、他のバッファが未使用の帯域幅を使用できるようにするために、図４又は図６からのレートシェーピング・アルゴリズムの複数の例が実現される。
【００２７】
図８は、本発明のある実施形態に従って、使用可能な帯域幅を共用できるようにするために、図７のセレクタのうち１個によって実現される論理の例証的なマトリックスを示す
【００２８】
図９は、ＱｏＳシステムのある実施形態を示し、この場合、図４又は図６のレートシェーピング・アルゴリズムを利用して、本発明のある実施形態に従って複数のバッファからパケットをディスパッチする。
【００２９】
所望のレートを満たすべく、パケットベースのトラフィックの流れを制御する方法及びシステムは、リンク上にあるパケットベースのトラフィックのカレントレートを移動平均として計算し、算出したカレントレートと所望レートの間の総エラー数を計算し、算出した総エラー数に応じて、パケットが流れることが可能であるか否かを決定する。ある実施形態では、カレントレートと所望レートの間の総エラー数がゼロ未満又はゼロと等しい場合に、バッファからリンク上にパケットがディスパッチされ、また、総エラー数がゼロよりも大きい場合には、パケットがバッファ内に保持される。総エラー数に応じて、カレントレートと所望レートの間でパケットの流れが制御されるため、たとえバースト型のトラフィック環境においても、取得したトラフィックのレートは所望レート付近に維持される。
【００３０】
図２は、本発明の焦点であるレートシェーピング・アルゴリズムの実現に使用することができるレートシェーピング・システムの例を示す。レートシェーピング・システムは、バッファ１１２、スイッチ１１４、レートシェーピング論理１１６を含む。バッファは、入力リンク１１８上の入力パケットを受信し、これらのパケットが出力リンク１２０にディスパッチされるまで、これらのパケットをバッファする。スイッチは、バッファと出力リンクの間のゲートウェイである。また、スイッチは、レートシェーピング論理によって制御され、このレートシェーピング論理は、以下に示すようにレートシェーピング・アルゴリズムを実現する。レートシェーピング・アルゴリズムの実施形態では、４個のフィールド（Initial_Rate、Desired_Rate、Δｔ、Ｎｃ）内の初期情報を、ユーザ定義の入力パラメータとして、レートシェーピング論理に提供する必要がある。フィールドのInitial_Rate，Desired_Rate，Δｔ、Ｎｃについては以降で定義する。動作中に、レートシェーピング論理が、出力リンクに関連した実伝送情報Ｃを受信し、制御信号（Switch_Control）をスイッチに出力する。レートシェーピング論理により生成された制御信号によって、スイッチがオン状態になることで（既にオン状態でない場合）、バッファからパケットがディスパッチされるか、又は、スイッチがオフ状態になることで（既にオフ状態でない場合）、パケットがバッファ内に保持される。図２中では、スイッチは、バッファからパケットをディスパッチするための機構として示されているが、これ以外の機構を使用してバッファからパケットをディスパッチすることも可能である。ここで定義しているように、入力リンクと出力リンクは、集積回路上のバス、集積基板上のバス、また、ワイヤ、光ファイバのような媒体、２個のネットワーク装置を接続するＲＦ信号、あるいは、パケット化した情報の通信に使用するこれ以外のリンクを実装することができる。さらに、入力リンクと出力リンクは、上述したリンクの任意の組み合わせを実装することが可能である。
【００３１】
本発明のアルゴリズムを実行する主要なステップのうちの１つでは、パケットベースのトラフィックのカレントレートを、移動平均として計算する。パケットベースのトラフィックのカレントレートを、移動平均として計算する技術については以降で示しており、その後、算出したカレントレートと所望レート間の総エラー数を計算する技術についても記述している。その後、図３〜図９を参照しながら、レートシェーピング・アルゴリズムの実施形態についてより詳細に記述する。
【００３２】
所与の期間Ｔにおける、パケットベースのトラフィックのレート（つまり、ビット/秒で表示するレート）を次式で表すことができる。
【数１】
2005512365.tif 000003
この場合、ΣＣは、時間Ｔ中に伝送された総ビット数である。サンプリングした、Ｎサンプリング・インターバルのドメインでは、レートを次式で表すことができる。
【数２】
2005512365.tif 000004
この場合、Δｔはサンプリング・インターバルであり、Ｎは、レートを計算するサンプリング・インターバルの数である。これにより、Ｎ番目のインターバルに先行するサンプリング・インターバルに関した次式が誘導される。
【数３】
2005512365.tif 000005
この後に、サンプリング・インターバル０〜Ｎの最中に伝送された総ビット数を次式で表すことができ、
【数４】
2005512365.tif 000006
上述のＲａｔｅＮとＲａｔｅＮ−１を使用して置換し、
ＲａｔｅＮ・Ｎ・Δｔ＝ＲａｔｅＮ−１・（Ｎ−１）・Δｔ＋ＣＮ
したがって、ＲａｔｅＮを次式のとおり帰納的に表すことができ、
【数５】
2005512365.tif 000007
又は、
ＲａｔｅＮ＝ＲａｔｅＮ−１＋Ｗａ・ＣＮ−Ｗｂ・ＲａｔｅＮ−１
この場合、重量Ｗａ及びＷｂが以下のとおり定義され、
【数６】
2005512365.tif 000008
及び
【数７】
2005512365.tif 000009
【００３３】
上式においてＮは変数であるが、Ｎを定数値に設定して、レート計算を単純化することができる。ある実施形態では、Ｎは、重量Ｗａ、Ｗｂを計算するために、定数値Ｎｃに設定されるため：
【数８】
2005512365.tif 000010
及び
【数９】
2005512365.tif 000011
この場合、Ｎｃは、サンプリング・インターバルの一定数を表す。レート計算を次式のとおり表すことができる：
Current_Rate＝Previous_Rate＋[Ｗａ・Ｃ−Ｗｂ・Previous_Rate]
この場合、Current_RateがＲａｔｅＮに関連し、Previous_RateがＲａｔｅＮ−１に関連し、Ｗａ及びＷｂがＮｃを用いて計算され、Ｃが、最新のサンプリング・インターバルの最中に伝送されたビット数に関連した実伝送情報である。
【００３４】
図２の実施形態では、Ｃは、１つ前のサンプリング・インターバルにおいてシステムの出力リンク１２０にディスパッチされたビットの実数を表す。図２では、論理ライン１２２は、レートシェーピング論理に供給される出力リンクに関連した実伝送情報を表す。図２中では、論理ライン１２２は出力リンクと接続しているが、実伝送情報は、様々な技術によってレートシェーピング論理に供給することができ、どの技術を使用するかは本発明にとって重要ではない。たとえば、実伝送情報をバッファから供給することができる。
【００３５】
アルゴリズムを実行する上でのこれ以外の主要段階には、算出したカレントレートと所望レートにおける間の総エラー数の計算が含まれる。この説明全体をとおして、算出したカレントレートと所望レートの間のエラーは「留数」と呼ばれるが、「エラー」と「留数」という用語は相互交換可能であることが理解されるべきである。Ｎサンプリング・インターバルのサンプリングしたドメインにおいて、Ｎ番目のサンプリング・インターバルにおける瞬間留数は、
ＲｅｓｉｄｕｅＮ＝ＲａｔｅＮ−Desired_Rate
と表される。
Ｎ番目のサンプリング・インターバルにおける総留数は、ここでは次式のとおり表される。
【数１０】
2005512365.tif 000012
ここから、Ｎ番目のサンプリング・インターバルの前に生じるサンプリング・インターバルについて次式が導かれ、
【数１１】
2005512365.tif 000013
したがって、Ｎ番目のサンプリング・インターバルにおける総留数も、前のＮ−１サンプリング・インターバルにおける総留数と、Ｎ番目のサンプリング・インターバルにおける瞬間留数の合計に関連して表すことができ、
【数１２】
2005512365.tif 000014
ＲｅｓｉｄｕｅＮ＝ＲａｔｅＮ−Desired_Rateで置換することにより、次式が得られ、
【数１３】
2005512365.tif 000015
したがって、Ｎ番目のサンプリング・インターバルにおける総留数を、カレント留数と以前の留数に関連して、次式で表すことができ、
Current_Residue＝Previous_Residue＋(Current_Rate−Desired_Rate)
この場合、Current_Rateは上述のように計算され、Previous_Residueは最後のサンプリング・インターバルにおける総留数に関連し、Desired_Rateはユーザ入力として得られる。
【００３６】
レートシェーピングへのアルゴリズムの使用には、各サンプリング・インターバル、つまり、各Δｔ毎のCurrent_RateとCurrent_Residueを計算し、次に、Current_Residueの値に基づいてスイッチ制御信号を生成することが含まれる。ある実施形態では、Current_Residueがゼロ未満又はゼロと等しい場合には、スイッチにパケット（すなわち「１」）のディスパッチを生じさせる制御信号が生成され、また、Current_Residueがゼロよりも大きい場合には、スイッチにパケット（すなわち「０」）の保持を生じさせる制御信号が生成される。総留数が、取得したレートが現在、所望レートと等しい、又は所望レートよりも低いことを示すために、Current_Residueがゼロ未満又はゼロと等しい場合にパケットがディスパッチされ、また反対に、総留数が、取得したレートが、現在、所望レートよりも低いことを示すために、Current_Residueがゼロよりも大きい場合にはパケットが保持される。このアルゴリズムを使用することで、長時間にわたり、パケットトラフィックの取得したレートが所望レートに接近する。この実施形態では、ゼロの留数値は、パケットのディスパッチとパケットの保持の間の臨界値であるが、別の実施形態では、この値を、ゼロ以外のある値に数学的に操作することができる。
【００３７】
ある実施形態では、レートシェーピング・アルゴリズムがサイクル実行され、この場合、各サイクルは、サンプリング・インターバルと同一である時間Δｔにまたがる。新規のサイクルを開始すると、Previous_Rate及びPrevious_Residueの値が更新されて、カレント値が反映される。詳細には、先行のサイクルで算出したCurrent_RateがPrevious_Rateに使用され、また、この先行のサイクルで算出したCurrent_ResidueがPrevious_Residueに使用される。全体のレートシェーピング・アルゴリズムは、例えば以下に示す擬似コードで表すことができる：すなわち、
//Rate Shaping Algorithm:Executes every Δt.
//PartI:Update Rate and Residue:
Current_Rate＝Previous_Rate＋Ｗａ・Ｃ−Ｗｂ・Previous_Rate;
Current_Residue＝Previous_Residue＋(Current_Rate−Desired_Rate);
//PartII:Update the Switch:
If(Current_Residue<＝0)Switch_Control＝1;
else Switch_Control＝0;
Previous_Rate＝Current_Rate;
Previous_Residue＝Current_Residue;
【００３８】
図３（ａ）、図３（ｂ）、図３（ｃ）は、上述したレートシェーピングのアルゴリズムの実現から得た例証的な結果を表す同期したグラフの一連の時間を示す。図３（ａ）は、上述のアルゴリズムを実現して生成されたレートプロファイルのグラフである。このグラフは、パケットトラフィックの所望レート３０６に関連する時間（Δｔの増分における）に対する移動平均として計算した、パケットトラフィックのCurrent_Rate３０４の例を示す。図３（ｂ）は、図３（ａ）のレートプロファイルから得た留数３２８の合計のグラフであり、図３（ｃ）は、総留数に応じて、レートシェーピング・アルゴリズムから生成されたスイッチ制御信号３３０のグラフである。この例では、「１」のスイッチ制御信号がパケットのディスパッチを生じさせ、また、「０」のスイッチ制御信号がパケットの保持を生じさせる。
【００３９】
図３（ａ）〜図３（ｃ）の例証的な結果の記述において、アルゴリズムが時間ｔ０から開始し、同一の時間にパケットのバーストがバッファからディスパッチされると仮定する。時間ｔ０にてディスパッチされたパケットにより、Current_Rateが図３（ａ）に示すように急増する。時間ｔ１において、Current_Rateが増加することで、Current_Residueがゼロから、ゼロよりも大きな何らかの値へと増加し、次にこれによって、スイッチ制御信号が「１」から「０」へ変わり、次に、残っている任意のバッファされたパケットが保持されるスイッチが新規のパケットをディスパッチしていないため、時間ｔ０と時間ｔ８の間のCurrent_Rateの下方傾斜によって、パケットトラフィックのCurrent_Rateが図３（ａ）に示すとおりに低下する。図３（ｂ）に示したCurrent_Rateに応じて、Current_RateがDisired_Rateよりも高い限り、Current_Residueが増加し、また、一旦Current_RateがDesired_Rate未満になると、Current_Residueが低下する。上述したCurrent_Residue、Current_Rate、Disired_Rate間の関係から、Current_Residueの反応が得られる。Current_Residueがゼロ未満、又はゼロと等しくなる地点において、スイッチ制御信号が「０」から「１」へ変化し、これにより、パケットの別のバーストがバッファからディスパッチされる。例えば、時間ｔ８において、Current_Residueはゼロと等しく、これにより、図３（ｃ）に示すとおり、スイッチ制御信号が「０」から「１」に変更する。スイッチ制御信号が「１」になると、時間ｔ８におけるCurrent_Rateで示すものと同様に、別のパケットのバーストが開放され、Current_Rateが急増する。図３（ｂ）、図３（ｃ）を参照すると、Current_Residueがゼロになるたびに、スイッチ制御信号が「０」から「１」に切り替わり、その後、Current_Residueがゼロよりも高くなると、再び「１」から「０」に切り替わる。この機構により、完全にロードされたシステムにおける全体平均トラフィックレートが所望レートに、又は所望レート付近に留まる。
【００４０】
図４は、上述のレートシェーピング・アルゴリズムを実行するためのプロセスフロー・ダイアグラムの実施形態を示す。第１サイクルが開始する前に、ステップ４３４として、レートシェーピング・アルゴリズムについてDesired_Rateの値ＮＣ及びΔｔが設定される。Desired_Rateの値Ｎｃ、Δｔの設定は、手作業でのユーザ入力、又は、より幅広いＱｏＳシステムに応答して生成される自動入力が関連する。ステップ４３６の第１サイクルの開始時に、ステップ４３８にて、Previous_Rate及びPrevious_Residueがゼロに設定される。ステップ４４０にて、伝送情報Ｃが取得される。ステップ４４２にて、Current_Rateが、上述のように、提供された式を用いて計算される。Current_Rateの計算に使用する値には、Previous_Rate、Ｃ、Ｗａ、Ｗｂが含まれる。ステップ４４４にて、Current_Rateを計算した後に、Current_Residueが、上述のとおり、提供された式を使用して計算される。Current_Residueの計算に使用する値には、Previous_Residue、Current_Rate、Desired_Rateが含まれる。次に、算出したCurrent_Residueを決定ポイント４４６にて使用して、パケットをディスパッチするべきか、保持するべきかを決定する。Current_Residueがゼロ未満、又はゼロと等しい場合には、ステップ４４８にて、パケットがディスパッチされ、また、Current_Residueがゼロよりも大きい場合には、ステップ４５０にて、パケットが保持される。ある実施形態では、パケットのディスパッチには、スイッチをオンにする制御信号の生成が含まれ、また、パケットの保持には、スイッチをオフにする制御信号の生成が含まれる。パケットをディスパッチするか、保持するかを決定した後に、決定ポイント４５２にて、サンプリング・インターバルΔｔが満了している場合には、ステップ４５４にて次のサイクルが開始される。ステップ４５６では、次のサイクルを開始するために、前回のサイクルで算出したCurrent_Rateの値を、次のレート計算のためにPrevious_Rateとして使用し、前回のサイクルで算出したCurrent_Residueの値を、次のResidue計算のためにPrevious_Residueとして使用する。Previous_Rate及びPrevious_Residueの値の設定後に、伝送情報Ｃを取得し（ステップ４４０）、Current_Rateを計算し（ステップ４４２）、Current_Residueを計算し（ステップ４４４）、パケットをディスパッチするか、保持するかを決定する（決定ポイント４４６）処理が上述のとおり繰り返される。この処理は、各Δｔ時間インターバル毎に連続的に繰り返される。
【００４１】
上述のアルゴリズムは、レートシェーピング・システムの入力バッファが完全にロードされた際に上手く働くが、レートシェーピング・アルゴリズムによって、ノートラフィックの期間がバーストに先行する場合に、レートシェーピングを実施しなくても、入力バーストをディスパッチすることが可能になる。ノートラフィックの期間が先行している場合には、バーストをレートシェーピング実行なしでディスパッチすることができるが、これは、ノートラフィックの期間により、比較的大きな負の留数が収集されるためである。Current_Residueがゼロ未満に維持される限り、上述したアルゴリズムの下で、大きな負の留数により、パケットのバーストをディスパッチすることが可能になる。ノートラフィック期間の後に、トラフィックの大きなバーストを防止するために、特定の状態において、Current_Rateの値とCurrent_Residueの値が、事前に確立された閾値に人工的に制御される。詳細には、ある実施形態において、Current_Rateは制御されるため、ここでInitial_Rateと呼ばれる事前に確立したレートよりも低くなることはできず、また、Current_Residueが制御されるため、ゼロよりも低くなることができない。Current_Rate及びCurrent_Residueが特定の閾値レベルよりも低くならないようにすることで、先行のノートラフィックの期間から「借りる」ことができる帯域の量が制御される。図５（ａ）、図５（ｂ）は、ノートラフィックの期間によって生じた問題を示し、さらに、たとえノートラフィックの期間後でも、全てのパケットを確実にレートシェーピングするために、Current_Rate及びCurrent_Residueに実施される調整を示している。図５（ａ）は、レートシェーピング・アルゴリズムを使用して生成したレートプロファイルのグラフを示し、さらに、図５（ｂ）は、図５（ａ）のレートプロファイルの結果得られた総留数の時間同期したグラフを示す。
【００４２】
図５（ａ）を参照すると、例証的な目的で、時間ｔ０における初回のトラフィックのバーストの後に、ノートラフィックの期間が続くと仮定する。人工的に調整しない限り、時間の経過と共に、算出したCurrent_Rate５０４がゼロに向かって低下する。最小値におけるCurrent_Rateを維持するために、算出したCurrent_RateがInitial_Rateを下回る場合には常に、Current_Rateが所定のInitial_Rate５５６に調整される。図５（ａ）は、算出したCurrent_RateがInitial_Rateを下回る際に常に、Current_Rateを所定のInitial_Rateに調整する方法を示す。
【００４３】
ある実施形態では、シミュレーションを使用して、Initial_Rateの値を求めている。このシミュレーションは、完全にパケットをロードしたシステム内で生じるCurrent_Rateの最小値を求めるために使用される。次に、この最小値がInitial_Rateとして確立される。ある実施形態では、シミュレーションが開始すると、Current_RateがDesired_Rateに初期化される。
【００４４】
図５（ｂ）を参照すると、図５（ａ）中のCurrent_Rate５０４がDisired_Rate５０６を下回る際には常に、Current_Residue５２８が低下する。人工的に調整しない限り、Current_RateがDesired_Rateを下回っている間は、Current_Residueが不定に低下する。Current_Residueを最小値に維持するために、算出したCurrent_Residueがゼロ未満である際には常に、Current_Residueがゼロに調整される。図５（ｂ）は、算出したCurrent_Residueがゼロ未満であったためにゼロに調整された、Current_Residueのある区間を示す。この実施形態では、Current_Residueがゼロの最小Current_Residueに調整されるが、Current_Residueをこれ以外の最小閾値に調整することも可能である。
【００４５】
更新したレートシェーピング・アルゴリズムの擬似コードは以下のとおりである：
//Modified Rate Shaping Algorithm:Executes every Δt.
//PartI:Update Rate and Residue:
Current_Rate＝Previous_Rate＋Ｗａ・Ｃ−Ｗｂ・Previous_Rate;
If(Current_Rate<Initial_Rate)Current_Rate＝Initial_Rate;
Current_Residue＝Previous_Residue＋(Current_Rate−Desired_Rate);
If(Current_Residue<0)Current_Residue＝0;
//PartII:Update the Switch:
If(Current_Residue＝0)Switch_Control＝1;
else Switch_Control＝0;
Previous_Rate＝Current_Rate;
Previous_Residue＝Current_Residue;
【００４６】
図６は、上述の変更を加えた、図４のレートシェーピング・アルゴリズムを実行するためのプロセスフロー・ダイアグラムを示す。このプロセスフロー・ダイアグラムは、以下を除いて、図４のプロセスフロー・ダイアグラムと類似しており；すなわち、ステップ６３４にて、他のパラメータに加えてInitial_Rateが確立され、追加のステップ６６０にて、Current_RateがInitial_Rate未満の場合、Current_RateがInitial_Rateに設定され、追加のステップ６６２にて、Current_Residueがゼロ未満である場合、Current_Residueがゼロに設定され、また、決定ポイント６４６にて、Current_Residueがゼロと等しい場合に、パケットがディスパッチされ、Current_Residueがゼロよりも大きい場合に、パケットが保持される。
【００４７】
別の実施形態では、マルチバッファ・システムにおいて、上述のレートシェーピング・アルゴリズムを実現することができ、これにより、この使用可能な帯域幅を、同一リンクに接続している他のバッファが使用することができるようになる。詳細には、マルチバッファ・システムにより、第２バッファがパケットを全く保持していない場合（つまり、第２バッファが、その使用可能な帯域幅を十分に活用していない場合）に、第２バッファに割り当てられた帯域幅を第１バッファが借りられるようになる。図７は、共通の出力リンク７６４に接続し、バッファ固有のスイッチ７１４によって制御された２個のバッファ７１２（バッファ１、バッファ２）の例証的な実施形態を示す。各々のバッファ固有のスイッチは、バッファ固有のセレクタ７６６によって、２個のバッファ固有のレートシェーピング装置７１６、７１７に接続している。バッファ固有のレートシェーピング装置は、上述したレートシェーピング・アルゴリズムの２つのバージョンを実現する。破線７６８で示すように、各セレクタが、他のバッファからバッファ状態情報を受信し、また、ライン７２２で示すように、各レートシェーピング装置が、各々のバッファに関連した実伝送情報を受信する。
【００４８】
図７の実施形態では、バッファ１からのディスパッチのレートを所望レートに制御する必要があり、また、共通の出力リンク７６４上に未使用で使用可能な帯域幅が存在する場合、ディスパッチのレートを最大レートに制御できると仮定している。これはバッファ２についても同様である。各バッファにて所望のレートシェーピングを達成するには、２個のレートシェーピング装置を各バッファに関連付ける。バッファ１を参照すると、一方のレートシェーピング装置RS1_Desired７１６が、バッファ１を所望のレートにレートシェーピングするように設定され（つまり、アルゴリズム内のDesired_Rateフィールドが所望レートに設定され）、他方のレートシェーピング装置、RS1_Maximum７１７が、バッファ１を最大レートにレートシェーピングするように設定される（つまり、アルゴリズム内のDesired_Rateフィールドが最大レートに設定される。同様に、バッファ２を参照すると、RS2_Desired７１６が、バッファ２を所望のレートにレートシェーピングするように設定され（つまり、アルゴリズム内のDesired_Rateフィールドが所望のレートに設定され）、他方のレートシェーピング装置RS2_Maximum７１７が、バッファ２を最大レートにレートシェーピングするように設定される（つまり、アルゴリズム内のDesired_Rateフィールドが最大レートに設定される）。図７の実施形態では、各バッファ内にトラフィックがある場合に、各バッファが、レートシェーピング装置RS1_Desired及びRS2_Desiredの各々によって、その所望レートに制御される。しかしながら、バッファのうち１個がバッファ・トラフィックを含んでいない場合には、これ以外のバッファがその最大レートにまで上昇することが可能となる。
【００４９】
図７、図８を参照して、２個のレートシェーピング装置を実装したバッファ１のレートシェーピングについて例証的目的で説明する。図８は、バッファ１用のセレクタ７６６によって実現される、論理の例証的なマトリックス７７０を示す。RS1_Desired７１６からの制御信号出力が、バッファ１からのパケットのディスパッチが可能であることを表す「１」である場合には、セレクタが「１」の制御信号をスイッチに出力し、パケットがディスパッチされる。セレクタが、RS1_Maximum７１７の値に無関係に、及び、バッファ２内にパケットが含まれているか否かに関わらず、「１」の制御信号を出力する。RS1_Desiredから出力された制御信号が「０」で、RS1_Maximumから出力された制御信号が「０」である場合には、バッファ２内にパケットが含まれているか否かに関係なく、セレクタが「０」の制御信号をスイッチに出力する。RS1_Desiredから出力された制御信号が「０」であり、RS1_Maximumから出力された制御信号が「１」である場合には、セレクタが、パケットをディスパッチできるか否かを決定するために、バッファ２の状態に注目する。バッファ２内にパケットが含まれている場合には、セレクタが"０"の制御信号を出力し、バッファ１からパケットはディスパッチされない。バッファ１からパケットはディスパッチされないが、これは、バッファ２内のパケットのために確保された帯域幅が、他のバッファによって消費されてはならないためである。しかし、バッファ２内にパケットが含まれておらず、RS1_Maximumが「１」である場合には、スイッチ１用のセレクタが、「１」の制御信号をスイッチ１に出力し、バッファ１からパケットがディスパッチされる。バッファ２内にパケットが存在せず、RS1_Desiredが「０」に維持される限り、このバッファ１からのパケットのディスパッチがRS1_Maximumによって制御される。
【００５０】
図７を参照して説明したシステムを、２個よりも多いバッファの制御を含むようにスケーリングすることが可能である。このスケーリングしたシステムでは、各バッファ用のセレクタが、他のバッファ全てのバッファ状態、又は他のバッファの組み合わせのバッファ状態を監視し、このバッファ情報を使用して、指定した最高レートでのパケットのディスパッチが可能であるか否かが決定される。
【００５１】
上述したレートシェーピング・アルゴリズムは、複数のバッファの同時制御にも使用することができる。図９は、同じレートシェーピング論理制御が複数のバッファを制御するＱｏＳシステムの実施形態を示す。ＱｏＳシステムは、パケット・クラシファイア９７２、バッファアクセス制御装置９７４、メモリ９７６、レートシェーピング論理９１６、スケジューラ９７８を含む。メモリは、バッファ固有のスイッチ９１４によって制御される複数のバッファ（つまりバッファ１〜Ｍ）を含んでいる。バッファ固有のスイッチの各々が、上述のようにレートシェーピング論理によって制御される。レートシェーピング論理は、対応する出力リンク９２０に関連した実伝送情報を受信し、また、この実伝送情報を使用して、レートシェーピング・アルゴリズムを実行し、スイッチ制御信号を生成する。
【００５２】
動作中に、クラシファイア９７２が、入力パケットをどのバッファに入れるべきかを決定する。パケットの分類が終わると、バッファアクセス制御装置９７４が、パケットをその適切なバッファに転送できるか否かを決定する。ある実施形態では、バッファアクセス制御装置が重み付けランダム早期検出（ＷＲＥＤ）アルゴリズムを使用して、分類されたパケットを各々対応するバッファに転送するべきか否かを決定する。レートシェーピング論理９１６は、バッファしたパケットがスケジューラ９７８によって受信されたか否かを決定する。ある実施形態では、レートシェーピング論理が、各サイクル中に、各バッファについて、図６を参照して記述したステップを実行し、また、スイッチ制御信号（Switch_1_Control及びSwitch_M_Control）を各々対応するスイッチに出力する。スケジューラは、スイッチの状態に従ってパケットをディスパッチする。たとえば、パケットを、スイッチファブリックにかけて切り替えを実行するようにスケジュールすることができる。
【００５３】
ある実施形態では、図２〜図９を参照して記述したレートシェーピング・アルゴリズムをハードウェア内で実現する。上述したように、Current_Rateの計算には、２つの乗算演算が必要である。ハードウェア実現では、乗算演算は比較的多量のリソースを要し、また、ハードウェア実現のリソースの必要性を制限することが望ましい。乗算演算のリソースの必要性を減少させる１つの方法は、乗算演算をシフティングに減少させるというものである。２つの乗算演算をシフティングに減少したレートシェーピング・アルゴリズムのハードウェア実施形態を以下に記述する。
【００５４】
上記において、重量定数Ｗａは１/（Ｎｃ・Δｔ）と定義されており、この場合、Ｎｃは時間インターバルの数である。ある実施形態において、Ｎｃを２の累乗となるように選択することが可能であり、Ｎｃは、２９から２１３の間の（及びこれらを含む）２の累乗である。上述したように、アルゴリズムが各Δｔ時間インターバルを実行する。乗算演算をシフティングに減少させるために、時間インターバルΔｔが、さらに、２の累乗、より詳細には２の負の累乗となるように選択される。ある実施形態では、時間インターバルΔｔは、ハードウェア・クロック時間（又は期間）の関数であり、レートシェーピング・アルゴリズムによって制御されるバッファの個数である。ある好ましい実施形態では、Δｔは、レートシェーピング論理（つまり、Δｔ>clock_time・number_of_buffers）によって制御されるバッファの個数を乗算したクロック時間よりも大きくなくてはならないため、各々のΔｔの最中に、Current_Rate、Current_Residue、及びスイッチを、各バッファについて更新することができる。これにより、１個のシングルバッファについて、Current_Rate、Current_Residue、及びスイッチを更新するために、１つのクロック周期が必要であると仮定されることに留意すること。表１は、レートシェーピング論理によって制御されるバッファ数の関数として、また、クロック周期の関数として使用できる例証的なΔｔ値を提供する。この表はさらに、使用が可能な最小Δｔと、また、２の負の累乗として選択したΔｔとを含む。
【表１】
2005512365.tif 000016
【００５５】
重量定数Ｗａは１／（Ｎｃ・Δｔ）として定義される。定数Ｗｒａは：Ｗｒａ＝ｌｏｇ２（Ｗａ）として定義することができ、また、１／（Ｎｃ・Δｔ）が２の累乗であり、１よりも大きい場合には、Ｗａ・Ｃが次式のとおり減少する。
Ｗａ・Ｃ≒（Ｃ<<Ｗｒａ）
したがって、この乗算演算が左シフト演算に減少する。
【００５６】
重量定数Ｗｂは１／Ｎと定義される。定数Ｗｒｂは：Ｗｒｂ＝ｌｏｇ２（Ｗｂ）と定義することができ、また、１／Ｎが２の累乗であり、１未満の場合には、Previous_Rate・Ｗｂが次式のとおり減少する。
Previous_Rate・Ｗｂ≒（Previous_Rate>>Ｗｒｂ）
したがって、乗算演算が右シフト演算に減少する。
【００５７】
このシフティングによってビットが損失されるため、計算の正確性が低下する可能性がある。正確性の低下を防止するために、固定点の計算が実現され、小数点以下のビット数がＡＣＣＵＲＡＣＹとして参照される。レートシェーピング・アルゴリズムのハードウェア実現は例証的な目的で、擬似コードで以下のとおり表すことができる。
//Hardware Implementation of Rate Shaping Algorithm:Executes every Δt.
//PartI:Update Rate and Residue:
Current_Rate＝Previous_Rate＋((C<<ACCURACY)<<Wra)−(Previous_Rate>>Wrb);
If(Current_Rate<Initial_Rate)Current_Rate＝Initial_Rate;
Current_Residue＝Previous_Residue＋(Current_Rate−Desired_Rate);
If(Current_Residue<0)Current_Residue＝0;
//PartII:Update the Switch:
If(Current_Residue＝0)Switch_Control＝1;
else Switch_Control＝0;
Previous_Rate＝Current_Rate;
Previous_Residue＝Current_Residue;
【００５８】
ある実施形態では、レートシェーピング・アルゴリズムは、変数長パケットを利用した環境、例えばイーサネット（登録商標名）環境において実現されるが、しかし、レートシェーピング・アルゴリズムは、固定長セル（又はパケット）を利用した環境、例えば非同期伝送モード（ＡＴＭ）環境において実現することも可能である。
【００５９】
ここで実現されるアルゴリズムは、レートシェーピングを達成するために使用されるが、レート制限又は他のレート制御技術を達成するために、このアルゴリズムを使用することも可能である。レート制限のためにアルゴリズムを使用する場合には、Current_Residueが閾値（つまりゼロ）未満である際にパケットがドロップされ、また、Current_Residueが閾値よりも高い場合にはパケットが伝送される。
【００６０】
上述したアルゴリズムの実施形態では、カレントレートと所望レートの間の総エラー数が、提供された公式を用いて、特定の方法で計算される。しかし、カレントレートと所望レートの間の総エラー数は、この説明及び特許請求項に記述した本発明の範囲及び精神から逸脱せずに、多数の方法で計算できることが理解されるべきである。
【００６１】
レートシェーピング・アルゴリズムをハードウェアで実現する場合でも、ソフトウェアで実現する場合でも、単純に、ユーザ入力フィールド、Initial_Rate、Desired_Rate、Δｔ、及びＮｃのいずれかを調整することにより、アルゴリズムのパフォーマンスを容易に調整することが可能である。Initial_Rateに関すれば、より低いInitial_Rateが、先行するノートラフィックの期間から「借りる」帯域幅を効率的に許容され、これにより、より大きなパケットのバーストが静寂の後に流れることが可能となる。Δｔに関すれば、スイッチ更新とスイッチ更新の間が長いため、より大きなΔｔが、トラフィック・プロファイルをよりバースト的に作成する傾向にある。Ｎｃに関すれば、Ｎｃの値が小さい程、算出したCurrent_Rateによる瞬間レートの追跡が接近し、これにより、応答時間がより高速化する。同様に、Ｎｃの値が大きくなる程、算出したCurrent_Rateによる瞬間レートの追跡が遠ざかり、これにより、応答時間が低速化する。
【００６２】
レートシェーピング・アルゴリズムは、スイッチがネットワーク内のノードを表すマクロレベルで、又は、スイッチが特定のバッファからのディスパッチ機能を制御するより低いレベルで、実現することができる。さらに、スイッチは、リンク上のパケットの流れを制御するあらゆる機構であってよい。
【００６３】
本発明の特定の実施形態を記述及び例証してきたが、本発明は、記述及び例証した部分の特定の形状及び配置に限定されるものではない。本発明は特許請求の範囲のみによって限定される。
【図面の簡単な説明】
【００６４】
【図１】従来技術に従って、バッファをパケットで完全にロードした状態のレートシェーピング・システムにおいて、ＥＷＭＡアルゴリズムを適用した結果得られたΔｔ単位の時間に対する、トラフィックレートの例証的なグラフを示す図である。
【図２】本発明のある実施形態に従ってレートシェーピング・アルゴリズムを実現するレートシェーピング・システムを示す図である。
【図３】図３（ａ）は本発明のある実施形態に従ってレートシェーピング・アルゴリズムの実現から生成されたトラフィックプロファイルのグラフを示し、図３（ｂ）は算出したカレントレートと図３（ａ）から得た所望レートの間の総エラー数のグラフを示し、図３（ｃ）は算出したカレントレートと図３（ｂ）から得た所望レートの間の総エラー数に応じて生成されたスイッチ制御信号のグラフを示す図である。
【図４】本発明のある実施形態に従って、パケットベースのトラフィックのフローレートを制御して、所望レートを満たすためのプロセスフロー線図を示す図である。
【図５】図５（ａ）は図４に示したレートシェーピング・アルゴリズムを用いて生成した未調整のレートプロファイルのグラフを示し、図５（ｂ）は算出したレートと図５（ａ）のレートプロファイルから得た所望レートの間の未調整の総エラー数を示すグラフである。
【図６】本発明の別の実施形態に従ってノートラフィックの期間に関連して変更した所望レートを満たすために、パケットベースのトラフィックのフローレートを制御するプロセスフロー線図である。
【図７】同一の出力リンクに接続し、バッファ固有のスイッチにより制御された２個のバッファの例証的な実施形態を示す図である。
【図８】本発明のある実施形態に従って、使用可能な帯域幅を共用できるようにするために、図７のセレクタのうち１個によって実現される論理の例証的なマトリックスを示す図である。
【図９】ＱｏＳシステムのある実施形態を示す図である。
【図１】
2005512365.tif 000017
【図２】
2005512365.tif 000018
【図３】
2005512365.tif 000019
【図４】
2005512365.tif 000020
【図５】
2005512365.tif 000021
【図６】
2005512365.tif 000022
【図７】
2005512365.tif 000023
【図８】
2005512365.tif 000024
【図９】
2005512365.tif 000025
【手続補正書】
【提出日】平成16年9月10日(2004.9.10)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
所望レートを満たすべく、パケットベースのトラフィックの流れを制御する方法であって、
リンク上にあるパケットベースのトラフィックのカレントレートを、移動平均として計算し；
前記算出したカレントレートと前記所望レートの間の総エラー数を計算し；
前記算出した総エラー数に応じて、パケットを流すことができるか否かを決定する方法。
【請求項２】
前記パケットを流すことができるか否かの決定において、前記総エラー数がエラー閾値未満である場合にはパケットの流れを許可し、前記総エラー数が前記エラー閾値よりも高い場合にはパケットの流れを許可しない、請求項１に記載の方法。
【請求項３】
前記パケットを流すことができるか否かの決定において、前記総エラー数が、取得したトラフィックのレートが所望レート未満であることを示す場合にはパケットの流れを許可し、前記総エラー数が、取得したトラフィックのレートが所望レートよりも高いことを示す場合にはパケットの流れを許可しない、請求項１に記載の方法。
【請求項４】
さらに、前記カレントレートの最小値を確立し、前記カレントレートが最小値未満である場合に前記カレントレートの値を調整する、請求項１に記載の方法。
【請求項５】
さらに、前記総エラー数の最小値を確立し、前記総エラー数が前記最小値未満である場合に前記総エラー数の値を調整する、請求項１に記載の方法。
【請求項６】
さらに、
前記カレントレート及び前記総エラー数の最小値を確立し；
前記カレントレートが前記カレントレートの前記最小値未満である場合に、前記カレントレートの値を調整し；
前記総エラー数が前記総エラー数の前記最小値未満である場合に、前記総エラー数を調整する、請求項１に記載の方法。
【請求項７】
前記カレントレートが重み付き移動平均として計算される、請求項１に記載の方法。
【請求項８】
前記カレントレートが次のとおり計算され：
Current_Rate＝Previous_Rate＋（Ｗａ・Ｃ−Ｗｂ・Previous_Rate）；
この場合、Ｃはビット数、Ｗａ及びＷｂは重量を表す、請求項７に記載の方法。
【請求項９】
前記総エラー数が、
Current_Error＝Previous_Error＋（Current_Rate−Desired_Rate）
として計算される、請求項８に記載の方法。
【請求項１０】
所望レートを満たすべく、入力リンクと出力リンクの間のパケットベースのトラフィックの流れを制御するシステムであって、
前記入力リンクと前記出力リンクの間を接続するスイッチを備え、前記スイッチが、前記スイッチをオンにすると、前記入力リンクから前記出力リンクへのトラフィックの流れを許可し、前記スイッチをオフにすると、パケットの流れを許可せず；
前記スイッチを制御するべく接続したレートシェーピング論理をさらに備え、前記レートシェーピング論理が：
前記入力リンクと出力リンクのうちの一方上に流れるパケットベースのトラフィックのカレントレートを移動平均として計算する手段と；
前記算出したカレントレートと前記所望レートの間の総エラー数を計算する手段と；
前記算出した総エラー数に応じて、パケットを前記出力リンクに流すことができるか否かを決定する手段とを含む、システム。
【国際調査報告】
2005512365.tif 000026