(57)【要約】【課題】パケット交換ネットワークのトラフィックシェーピングを行う方法及びネットワークノードを提供し、ネットワークノードは、少なくとも一つの処理ユニットのセットの同期した利用を提供する順次パケット処理アルゴリズムＡｓｅｒ及び少なくとも一つの処理ユニットのセットの少なくとも部分的に同期しない利用を提供する並列パケット処理アルゴリズムＡｐａｒに少なくとも従ってネットワークに送信されるパケットを処理するように配置され、パケットの処理は、少なくとも一つの処理ユニットのセットによって協力的に負担される総パケットコストに対応する。【解決手段】方法は、並列パケット処理アルゴリズムＡｐａｒに従う処理がパケットを処理するために用いられるとき、少なくとも一つの処理ユニットの一つ以上に対する総パケットコストの負担が少なくとも一つの処理ユニットのパケットを処理する容量を超えているか否かを判定することであって、容量は、一つ以上のパケットに対応することと、少なくとも一つの処理ユニットの一つ以上に対する総パケットコストの負担が容量を超えていると判定された場合、並列パケット処理アルゴリズムＡｐａｒに従う処理から順次パケット処理アルゴリズムＡｓｅｒに従う処理に切り替えることと、を更に含む。【選択図】図２ａ
2019510448.tif 000002
【特許請求の範囲】
【請求項１】
パケット交換ネットワーク（５００）のトラフィックシェーピングを行う方法（２００）であって、
少なくとも一つの処理ユニット（ＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎ）のセット（ＳＰＵ；１５０）の同期した利用を提供する順次パケット処理アルゴリズム（Ａｓｅｒ）及び少なくとも一つの処理ユニット（ＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎ）のセット（ＳＰＵ；１５０）の少なくとも部分的に同期しない利用を提供する並列パケット処理アルゴリズム（Ａｐａｒ）に少なくとも従って前記ネットワーク（５００）に送信されるパケットの処理を含み、
前記パケットの前記処理は、前記少なくとも一つの処理ユニット（ＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎ）のセット（ＳＰＵ；１５０）によって協力的に負担される総パケットコスト（Ｃｔｏｔ）に対応する方法（２００）において、
前記並列パケット処理アルゴリズム（Ａｐａｒ）に従う前記処理が前記パケットを処理するために用いられるとき、前記少なくとも一つの処理ユニット（ＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎ）の一つ以上に対する前記総パケットコスト（Ｃｔｏｔ）の負担（Ｃ１，Ｃ２，．．．，Ｃｎ）が前記少なくとも一つの処理ユニット（ＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎ）のパケットを処理する容量を超えているか否かを判定すること（２１０）であって、前記負担（Ｃ１，Ｃ２，．．．，Ｃｎ）の各々は、一つ以上のパケットに対応することと、
前記少なくとも一つの処理ユニット（ＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎ）の一つ以上に対する前記総パケットコスト（Ｃｔｏｔ）の前記負担（Ｃ１，Ｃ２，．．．，Ｃｎ）が前記容量を超えていると判定された（２１０）場合、前記並列パケット処理アルゴリズム（Ａｐａｒ）に従う前記処理から前記順次パケット処理アルゴリズム（Ａｓｅｒ）に従う前記処理に切り替える（２２０）ことと、
を備えることを特徴とする方法（２００）。
【請求項２】
前記少なくとも部分的に同期しない並列パケット処理アルゴリズム（Ａｐａｒ）は、
前記セット（ＳＰＵ；１５０）の前記少なくとも一つの処理ユニット（ＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎ）に関連した優先レベル（Ｐｈｉｇｈ：Ｐｌｏｗ）に基づいて処理の優先順位付けを行うことを更に含み、これによって、
高い優先順位（Ｐｈｉｇｈ）に関連した処理ユニット（ＰＵｈｉｇｈ）は、パケットを処理するとともに前記パケットの処理に対応する部分デット（Ｄ１＿ｆｒａｃ，Ｄ２＿ｆｒａｃ，．．．，Ｄｎ＿ｆｒａｃ）を低い優先順位（Ｐｌｏｗ）に関連する前記セット（ＳＰＵ；１５０）の一つ以上の処理ユニット（ＰＵｌｏｗ）にチャージすることを許容され、
前記少なくとも一つの処理ユニット（ＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎ）に対する前記総パケットコスト（Ｃｔｏｔ）の前記負担（Ｃ１，Ｃ２，．．．，Ｃｎ）はそれぞれ、部分パケットコスト（Ｃ１＿ｆｒａｃ，Ｃ２＿ｆｒａｃ，．．．，Ｃｎ＿ｆｒａｃ）及び部分デット（Ｄ１＿ｆｒａｃ，Ｄ２＿ｆｒａｃ，．．．，Ｄｎ＿ｆｒａｃ；Ｃ１＝Ｃ１＿ｆｒａｃ＋Ｄ１＿ｆｒａｃ，Ｃ２＝Ｃ２＿ｆｒａｃ＋Ｄ２＿ｆｒａｃ，．．．，Ｃｎ＝Ｃｎ＿ｆｒａｃ＋Ｄｎ＿ｆｒａｃ）を含む請求項１に記載の方法（２００）。
【請求項３】
前記並列パケット処理アルゴリズム（Ａｐａｒ）に従う処理が用いられるときに前記部分デット（Ｄ１＿ｆｒａｃ，Ｄ２＿ｆｒａｃ，．．．，Ｄｎ＿ｆｒａｃ）を経時的に減少させる請求項２に記載の方法（２００）。
【請求項４】
前記並列パケット処理アルゴリズム（Ａｐａｒ）に従ってパケットを処理するとともに前記総パケットコスト（Ｃｔｏｔ）の前記負担（Ｃ１，Ｃ２，．．．，Ｃｎ）がパケットを処理する容量を超える少なくとも部分的に同期しない処理ユニット（ＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎ）は、少なくとも一つの処理ユニット（ＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎ）の前記セット（ＳＰＵ；１５０）が全体として前記パケットを処理することができるか否かを判定することができず、
前記少なくとも部分的に同期しない処理ユニット（ＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎ）は、少なくとも一つの処理ユニット（ＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎ）の前記セット（ＳＰＵ；１５０）が全体として前記パケットを処理することができるか否かを判定することができない結果として前記順次パケット処理アルゴリズム（Ａｓｅｒ）に従う前記処理に切り替えることを要求する請求項１〜３のいずれか一項に記載の方法（２００）。
【請求項５】
前記少なくとも一つの処理ユニット（ＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎ）の一つ以上は、
中央処理装置（ＣＰＵ）及び
中央処理装置コアの群の一つである請求項１〜４のいずれか一項に記載の方法（２００）。
【請求項６】
前記並列パケット処理アルゴリズム（Ａｐａｒ）は、少なくとも部分的に同期しないトークンバケットアルゴリズムであり、
前記総パケットコスト（Ｃｔｏｔ）は、トークンの総数（Ｎｔｏｔ）に関連し、
前記トークンの総数（Ｎｔｏｔ）は、前記少なくとも部分的に同期しない少なくとも一つの処理ユニット（ＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎ）に対するトークンの一部の数（Ｎ１，Ｎ２，．．．，Ｎｎ）として前記セット（ＳＰＵ；１５０）に対してそれぞれ分けられ、
前記総パケットコスト（Ｃｔｏｔ）の前記負担（Ｃ１，Ｃ２，．．．，Ｃｎ）は、前記トークンの一部の数（Ｎ１，Ｎ２，．．．，Ｎｎ）にそれぞれ関連する請求項１〜５のいずれか一項に記載の方法（２００）。
【請求項７】
処理ユニット（ＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎ）に対する前記総パケットコスト（Ｃｔｏｔ）の前記負担（Ｃ１，Ｃ２，．．．，Ｃｎ）は、
前記処理ユニット（ＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎ）の前記負担（Ｃ１，Ｃ２，．．．，Ｃｎ；Ｃ１＞Ｎ１，Ｃ２＞Ｎ２，．．．，Ｃｎ＞Ｎｎ）が前記トークンの一部の数（Ｎ１，Ｎ２，．．．，Ｎｎ）を超えること及び
前記処理ユニット（ＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎ）がゼロ（０）のトークンの一部の数（Ｎ１＝０，Ｎ２＝０，．．．，Ｎｎ＝０）を有することの群の一つ以上が真である場合にパケットを処理する容量を超えたと判定される請求項６に記載の方法（２００）。
【請求項８】
前記並列パケット処理アルゴリズム（Ａｐａｒ）に従う処理を用いるときに前記トークンの一部の数（Ｎ１，Ｎ２，．．．，Ｎｎ）を経時的に増加させる請求項６〜７のいずれか一項に記載の方法（２００）。
【請求項９】
前記トークンの一部の数（Ｎ１，Ｎ２，．．．，Ｎｎ）の全てをトークンの累算した総数（Ｎｔｏｔ；Ｎｔｏｔ＝Ｎ１＋Ｎ２＋．．．＋Ｎｎ）に足し合わせること（２２１）と、
全ての負担（Ｃ１，Ｃ２，．．．，Ｃｎ）を累算した総コスト（Ｃｔｏｔ）に足し合わせること（２２２）と、
前記順次パケット処理アルゴリズム（Ａｓｅｒ）に従う処理に切り替えるとき及び／又はドロップモードアルゴリズム（Ａｄｒｏｐ）に従う処理に切り替えるときにトークンの総数（Ｎｔｏｔ）及び／又は総コスト（Ｃｔｏｔ）を利用すること（２２３）と、
を更に有する請求項６〜８のいずれか一項に記載の方法（２００）。
【請求項１０】
前記順次パケット処理アルゴリズム（Ａｓｅｒ）は、
前記順次パケット処理アルゴリズム（Ａｓｅｒ）によって費やされるトークンより迅速にトークンの総数（Ｎｔｏｔ）を増加させること（２５０）と、
前記トークンの総数（Ｎｔｏｔ）が並列処理しきい値（Ｎｔｏｔ＿ｐａｒ）より大きい（Ｎｔｏｔ＞Ｎｔｏｔ＿ｐａｒ）ときに前記順次パケット処理アルゴリズム（Ａｓｅｒ）に従う前記処理から前記並列パケット処理アルゴリズム（Ａｐａｒ）に従う前記処理に切り替えること（２６０）と、
を含む請求項９に記載の方法（２００）。
【請求項１１】
前記総コスト（Ｃｔｏｔ）が総デット（Ｄｔｏｔ）を含むときに並列処理しきい値（Ｎｔｏｔ＿ｐａｒ）を前記総デット（Ｄｔｏｔ）に対応する値（Ｎｄｅｂｔ＿ｓｕｍ）だけ増加させる請求項１０に記載の方法（２００）。
【請求項１２】
前記順次パケット処理アルゴリズム（Ａｓｅｒ）に従う処理からドロップモードアルゴリズム（Ａｄｒｏｐ）に従う処理に切り替えること（２７１）と、
前記トークンの総数（Ｎｔｏｔ）がゼロ（０）の値を有すること（Ｎｔｏｔ＝０）及び
前記総コスト（Ｃｔｏｔ）が前記トークンの総数（Ｎｔｏｔ）を超えること（Ｃｔｏｔ＞Ｎｔｏｔ）の群において少なくとも一つが真である場合に前記少なくとも部分的に同期しない少なくとも一つの理ユニット（ＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎ）の前記セット（ＳＰＵ；１５０）を用いることによって前記ドロップモードアルゴリズム（Ａｄｒｏｐ）に従って前記パケットを処理すること（２７２）と、
を更に含む請求項６〜１１のいずれか一項に記載の方法（２００）。
【請求項１３】
前記ドロップモードアルゴリズム（Ａｄｒｏｐ）に従う処理は、
少なくとも一つのパケットをドロップすること（２７３）、
少なくとも一つのパケットをキューイングすること（２７４）及び
不適合のラベルを付した少なくとも一つのパケットを送信すること（２７５）の群の少なくとも一つの動作を含む請求項１２に記載の方法（２００）。
【請求項１４】
前記トークンの総数（Ｎｔｏｔ）が前記総コスト（Ｃｔｏｔ）を超える（Ｎｔｏｔ＞Ｃｔｏｔ）場合、
前記ドロップモードアルゴリズム（Ａｄｒｏｐ）に従う処理から前記順次パケット処理アルゴリズム（Ａｓｅｒ）に従う処理に切り替えること（２７１）と、
前記順次パケット処理アルゴリズム（Ａｓｅｒ）に従って前記パケットを処理すること（２３０）と、
を更に含む請求項６〜１３のいずれか一項に記載の方法（２００）。
【請求項１５】
各々がネットワークノード（１００）を介してパケットを受信する一つ以上の装置に関連した少なくとも一つのアクティブ群（Ｇ１，Ｇ２，．．．，Ｇｋ）を規定すること（２９１）と、
前記セットの前記少なくとも一つのアクティブ群（Ｇ１，Ｇ２，．．．，Ｇｋ）に対して前記ネットワーク（５００）の利用できる帯域幅の少なくとも一つの帯域幅部分を割り当てること（２９２）と、を更に含み、前記割り当てること（２９２）は、並列に実行されるとともに前記少なくとも一つのアクティブ群（Ｇ１，Ｇ２，．．．，Ｇｋ）に対して少なくとも部分的に同期しない請求項１〜１６のいずれか一項に記載の方法（２００）。
【請求項１６】
前記少なくとも一つのクライアント群（Ｇ１，Ｇ２，．．．，Ｇｋ）は、
少なくとも一つの発信元インターネットプロトコル（ＩＰ）アドレス、
少なくとも一つの宛先インターネットプロトコル（ＩＰ）アドレス、
少なくとも一つの発信元ネットワーク、
少なくとも一つの宛先ネットワーク、
少なくとも一つの発信元ポート、
少なくとも一つの宛先ポート、
少なくとも一つの受信インタフェース、
少なくとも一つの転送インタフェース、
アプリケーション層データに関連した少なくとも一つのパラメータ及び
ネットワークトラフィックの少なくとも一つのパーティションの群の一つ以上に関連した請求項１５に記載の方法（２００）。
【請求項１７】
前記利用できる帯域幅が少なくとも一つの群（Ｇ１，Ｇ２，．．．，Ｇｋ）の間で略均等に分割されるように前記少なくとも一つの帯域幅部分の割当て（２９２）を行う請求項１５〜１６のいずれか一項に記載の方法（２００）。
【請求項１８】
前記少なくとも一つの帯域幅部分の割当て（２９２）は、少なくとも一つの群（Ｇ１，Ｇ２，．．．，Ｇｋ）の一つ以上の帯域幅部分が使用されていないか否かを判定すること（２９３）と、
一つ以上の使用されていない帯域幅部分を、更なる帯域幅を必要としている前記少なくとも一つの群（Ｇ１，Ｇ２，．．．，Ｇｋ）の他の一つ以上に再割り当てすること（２９４）と、
を更に含む請求項１５〜１７のいずれか一項に記載の方法（２００）。
【請求項１９】
更なる帯域幅を必要としている前記少なくとも一つの群（Ｇ１，Ｇ２，．．．，Ｇｋ）は、再割り当てされた一つ以上の帯域幅部分に対して互いに競合する請求項１８に記載の方法（２００）。
【請求項２０】
コンピュータで実行するときに請求項１〜１９のいずれか一項に記載の方法を実行するプログラムコードを有するコンピュータプログラム。
【請求項２１】
少なくとも一つの処理ユニット（ＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎ）のセット（ＳＰＵ；１５０）の同期した利用を提供する順次パケット処理アルゴリズム（Ａｓｅｒ）及び少なくとも一つの処理ユニット（ＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎ）のセット（ＳＰＵ；１５０）の少なくとも部分的に同期しない利用を提供する並列パケット処理アルゴリズム（Ａｐａｒ）に少なくとも従って前記ネットワーク（５００）に送信されるパケットの処理を行うために配置された処理装置（１２０）を含むパケット交換ネットワークのネットワークノード（１００）であって、
前記パケットの前記処理は、前記少なくとも一つの処理ユニット（ＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎ）のセット（ＳＰＵ；１５０）によって協力的に負担される総パケットコスト（Ｃｔｏｔ）に対応するネットワークノード（１００）において、
前記処理装置（１２０）は、
前記並列パケット処理アルゴリズム（Ａｐａｒ）に従う前記処理が前記パケットを処理するために用いられるとき、前記少なくとも一つの処理ユニット（ＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎ）の一つ以上に対する前記総パケットコスト（Ｃｔｏｔ）の負担（Ｃ１，Ｃ２，．．．，Ｃｎ）が前記少なくとも一つの処理ユニット（ＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎ）のパケットを処理する容量を超えているか否かを判定（２１０）し、前記容量は、一つ以上のパケットに対応し、
前記少なくとも一つの処理ユニット（ＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎ）の一つ以上に対する前記総パケットコスト（Ｃｔｏｔ）の前記負担（Ｃ１，Ｃ２，．．．，Ｃｎ）が前記容量を超えていると判定された（２１０）場合、前記並列パケット処理アルゴリズム（Ａｐａｒ）に従う前記処理から前記順次パケット処理アルゴリズム（Ａｓｅｒ）に従う前記処理に切り替える（２２０）ために配置されたネットワークノード（１００）。
【請求項２２】
前記少なくとも一つの処理ユニット（ＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎ）の一つ以上は、
中央処理装置（ＣＰＵ）及び
中央処理装置コアの群の一つである請求項２１に記載のネットワークノード（１００）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケット交換ネットワークのネットワークノードを用いることによってトラフィックシェーピングを行う方法に関する。また、本発明は、トラフィックシェーピングのために配置されたパケット交換ネットワークのネットワークノードに関する。さらに、本発明は、方法を実現するコンピュータプログラム及びコンピュータプログラム製品に関する。
【背景技術】
【０００２】
トラフィックシェーピングを、パケット交換コンピュータネットワークのようなパケット交換ネットワークのネットワークリソースの制限、優先順位付け及び／又は公正な分担（ｆａｉｒ  ｓｈａｒｉｎｇ）を行うために用いることができる。大抵のトラフィックシェーピング方法は、トークンバケットアルゴリズム、（例えば、Ｌｉｎｕｘ（登録商標）によって用いられる）階層型トークンバケットアルゴリズム又は同様なアルゴリズムに基づく。また、一部のトラフィックシェーピング方法は、ジェネリックセルアルゴリズム（ＧＣＲＡ）に基づく。パケット交換ネットワークトラフィックの優先順位付けを行う既存の方法は、異なる優先レベルに対して異なるパケットキューを用いた後に優先順位の順番にパケットをキューから送出する。デキューイング（ｄｅｑｕｅｕｉｎｇ）デバイスから送出されるパケットの数は、トークンバケットアルゴリズム又は同様なアルゴリズムによってしばしば制御される。
【０００３】
トラフィックシェーピングアルゴリズムを、ネットワークノード、例えば、ファイアウォール装置、ルータ装置、メディアゲートウェイ装置又はネットワークのパケットが通過する他の適切な装置において実行することができる。一般的には、トラフィックシェーピングを、ネットワークノードの基本的にあらゆる種類のトラフィック、例えば、クライアントからサーバへのトラフィック、ピアツーピアトラフィック、サーバからサーバへのトラフィック又は基本的に他の任意の種類のネットワークトラフィックのパケットにおいて行うことができる。
【０００４】
計算能力についての現代の要求の増大及びネットワーク負荷の増大に従って、ネットワークノードのパケットを処理するために利用されるＣＰＵ及び／又はＣＰＵコアの数が増大する。基本的な考えは、パケットを処理する際にＣＰＵ及び／又はＣＰＵコアの数を増やすことによって高くなった計算能力を活用することである。しかしながら、そのような複数のＣＰＵ及び／又は複数のＣＰＵコアの解決を有効利用するのは困難である。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述した既知のトラフィックシェーピングアルゴリズムは全てパケット処理効率問題を有する。既知のアルゴリズムのこれらの問題は、単一のＣＰＵ及び／又は単一のＣＰＵコアを有するネットワークノードに対するシングルスレッドの使用のためにアルゴリズムが開発されるとともに最適化されるという事実に少なくとも部分的に関連する。したがって、現在の既知のトラフィックシェーピングアルゴリズムは、ネットワークのパケットトラフィックが増大するに従って益々顕著になる効率問題を有する。
【０００６】
本発明の実施の形態の目的は、上述した欠点及び問題を軽減又は解決する解決策を提供することである。
【課題を解決するための手段】
【０００７】
上述した目的及び他の目的は、独立項の主題によって達成される。本発明の別の有利な実現形態は、従属項によって規定される。
【０００８】
本発明の第１の態様によれば、例えば、パケット交換ネットワークのトラフィックシェーピングを行う方法を提供する。パケットを、少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎのセットＳＰＵの同期した利用を提供する順次パケット処理アルゴリズムＡｓｅｒ及び少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎのセットＳＰＵの少なくとも部分的に同期しない利用を提供する並列パケット処理アルゴリズムＡｐａｒに少なくとも従ってネットワークに送信されるように処理してもよく、パケットの処理は、少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎのセットＳＰＵ；１５０によって協力的に負担される総パケットコストＣｔｏｔに対応する。方法は、
並列パケット処理アルゴリズムＡｐａｒに従う処理がパケットを処理するために用いられるとき、少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎの一つ以上に対する総パケットコストＣｔｏｔの負担Ｃ１，Ｃ２，．．．，Ｃｎが少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ，；１５１，１５２，．．．，１５ｎのパケットを処理する容量を超えているか否かを判定することであって、容量は、一つ以上のパケットに対応することと、
少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎの一つ以上に対する総パケットコストＣｔｏｔの負担Ｃ１，Ｃ２，．．．，Ｃｎが容量を超えていると判定された場合、並列パケット処理アルゴリズムＡｐａｒに従う処理から順次パケット処理アルゴリズムＡｓｅｒに従う処理に切り替えることと、
を更に含む。
【０００９】
したがって、パケットを、並列モード／アルゴリズムＡｐａｒに少なくとも部分的に従って処理／実行／算出／計算してもよい。本発明は、非常に有利である複数のＣＰＵコアのような複数の（少なくとも二つの）処理ユニットで並列に実行する作業に非常に適している。原理的には、制限されない数の処理ユニット、例えば、ＣＰＵコアを、本発明を利用するときにデータ／情報／パケット／トラフィックを処理するのに用いてもよい。
【００１０】
段階（ｐｈａｓｅ）の自由度／可変性が十分である場合、すなわち、並列モード／アルゴリズムＡｐａｒに従ってパケットを少なくとも部分的に処理できる場合、本発明を用いるときに、同期した順次処理ユニットによって従来実行された方法／アルゴリズムを、少なくとも部分的に同期しない並列モード／アルゴリズムＡｐａｒを用いるセットＳＰＵの処理ユニットに分割／分割／分配してもよい。
【００１１】
一般的に記述すると、並列／非同期処理ユニットが、それに割り当てられた方法／アルゴリズムの適切／正確な実行を保証できない場合、並列／非同期処理ユニットによって実行されるべきであった残りのパケットに対応する残りの方法／アルゴリズムを、一実施の形態によって再び収穫／収集／招集することができる。残りの方法／アルゴリズム、すなわち、収穫／収集／招集された残りのパケットを、順次パケット処理アルゴリズムＡｓｅｒに従って処理／実行／算出／計算することができる。
【００１２】
これは、例えば、パケットが順次モード／アルゴリズム処理によって取り扱われる間に段階の自由度／可変性を累算することができる場合に良好に機能する。順次パケット処理アルゴリズムＡｓｅｒが処理ユニットのセットＳＰＵにおいて良好にバランスがとられる場合、並列モードＡｐａｒにおいて継続することができる処理の可能性が増大する。例えば、並列アルゴリズムＡｐａｒに従うパケット処理が完全にバランスがとられた場合、順次モード／アルゴリズムＡｓｅｒに戻る（ｒｅｔｕｒｎ／ｇｏ  ｂａｃｋ）必要がなく、これによって順次モード処理に対する要求が低くなる。しかしながら、実用的な実現において、並列モード／アルゴリズムに対する処理ユニットのトラフィック／作業負荷／処理のバランスに基づいて順次Ａｓｅｒと並列Ａｐａｒの間の切り替えを行う必要が生じることがある。
【００１３】
第１の態様の実施の形態によれば、少なくとも部分的に同期しない並列パケット処理アルゴリズムＡｐａｒは、
セットＳＰＵの少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎに関連した優先レベルＰｈｉｇｈ：Ｐｌｏｗに基づいて処理の優先順位付けを行うことを更に含み、これによって、
高い優先順位Ｐｈｉｇｈに関連した処理ユニットＰＵｈｉｇｈは、パケットを処理するとともにパケットの処理に対応する部分デット（ｆｒａｃｔｉｏｎａｌ  ｄｅｂｔ）Ｄ１＿ｆｒａｃ，Ｄ２＿ｆｒａｃ，．．．，Ｄｎ＿ｆｒａｃを低い優先順位Ｐｌｏｗに関連するセットＳＰＵの一つ以上の処理ユニットＰＵｌｏｗにチャージすることを許容され、
少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎに対する総パケットコストＣｔｏｔの負担Ｃ１，Ｃ２，．．．，Ｃｎはそれぞれ、部分パケットコストＣ１＿ｆｒａｃ，Ｃ２＿ｆｒａｃ，．．．，Ｃｎ＿ｆｒａｃ及び部分デットＤ１＿ｆｒａｃ，Ｄ２＿ｆｒａｃ，．．．，Ｄｎ＿ｆｒａｃ；Ｃ１＝Ｃ１＿ｆｒａｃ＋Ｄ１＿ｆｒａｃ，Ｃ２＝Ｃ２＿ｆｒａｃ＋Ｄ２＿ｆｒａｃ，．．．，Ｃｎ＝Ｃｎ＿ｆｒａｃ＋Ｄｎ＿ｆｒａｃを含む。
【００１４】
換言すれば、優先順位付けされたパケット処理が、トークン及び／又はトークンバケットのような少なくとも部分的に独立した制限／制限されたユニットを用いることによって優先順位付けされたステップ／タスク／課題（ｉｓｓｕｅ）を取り扱う実施の形態によって提供される。これらの制限／制限されたユニットの各々を、特定／所定の優先順位が割り当てられたパケットのみが特定／所定の優先順位、例えば、低い優先順位Ｐｌｏｗが割り当てられた特定の制限／制限されたユニットをパスするように特定の優先順位、例えば、低い優先順位Ｐｌｏｗに割り当てる／関連付けることができる。
【００１５】
高い優先順位Ｐｈｉｇｈが割り当てられたパケットが特定／所定の優先順位位Ｐｈｉｇｈが割り当てられた特定／所定の制限／制限されたユニットをパスするようにしてもよいが、この高い優先順位のパケット／処理のコストは、低い優先順位Ｐｌｏｗが割り当てられた／関連付けられたユニットに保持／デビットされる（ｃａｒｒｉｅｄ／ｄｅｂｉｔｅｄ）。これによって、制限／制限されたユニットは、同様であり、例えば、多かれ少なかれ同一であり、及び／又は、独立しており、これによって、低い優先順位Ｐｌｏｗが割り当てられた／関連付けられたユニットの正確なデビット（ｄｅｂｉｔｉｎｇ）を並列に実行することができる。例えば、このような並列デットを、デットを実行するように構成された仮想パケットを送信することによって実現することができる。これを、結果を完全に並列処理するように実現してもよい。
【００１６】
第１の態様の一実施の形態によれば、並列パケット処理アルゴリズムＡｐａｒに従う処理が用いられるときに部分デットＤ１＿ｆｒａｃ，Ｄ２＿ｆｒａｃ，．．．，Ｄｎ＿ｆｒａｃを経時的に減少させる。
【００１７】
第１の態様の一実施の形態によれば、並列パケット処理アルゴリズムＡｐａｒに従ってパケットを処理するとともに総パケットコストＣｔｏｔの負担Ｃ１，Ｃ２，．．．，Ｃｎがパケットを処理する容量を超える少なくとも部分的に同期しない処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎは、少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎのセットＳＰＵが全体としてパケットを処理することができるか否かを判定することができず、
少なくとも部分的に同期しない処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎは、少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎのセットＳＰＵが全体としてパケットを処理することができるか否かを判定することができない結果として順次パケット処理アルゴリズムＡｓｅｒに従う処理に切り替えることを要求する。
【００１８】
第１の態様の一実施の形態によれば、少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎの一つ以上は、
中央処理装置（ＣＰＵ）及び
中央処理装置コアの群の一つである。
【００１９】
第１の態様の一実施の形態によれば、並列パケット処理アルゴリズムＡｐａｒは、少なくとも部分的に同期しないトークンバケットアルゴリズムであり、
総パケットコストＣｔｏｔは、トークンの総数Ｎｔｏｔに関連し、
トークンの総数Ｎｔｏｔは、少なくとも部分的に同期しない少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎに対するトークンの一部の数Ｎ１，Ｎ２，．．．，ＮｎとしてセットＳＰＵに対してそれぞれ分けられ、
総パケットコストＣｔｏｔの負担Ｃ１，Ｃ２，．．．，Ｃｎは、トークンの一部の数Ｎ１，Ｎ２，．．．，Ｎｎにそれぞれ関連する。
【００２０】
第１の態様の一実施の形態によれば、処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎに対する総パケットコストＣｔｏｔの負担Ｃ１，Ｃ２，．．．，Ｃｎは、
処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎの負担Ｃ１，Ｃ２，．．．，Ｃｎ（Ｃ１＞Ｎ１，Ｃ２＞Ｎ２，．．．，Ｃｎ＞Ｎｎ）がトークンの一部の数Ｎ１，Ｎ２，．．．，Ｎｎを超えること及び
処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎがゼロ（０）のトークンの一部の数Ｎ１＝０，Ｎ２＝０，．．．，Ｎｎ＝０を有することの群の一つ以上が真である場合にパケットを処理する容量を超えたと判定される。
【００２１】
一実施の形態によれば、段階の自由度／可変性は、トークンバケットのトークンの数に関連する。トークンバケットが、並列パケット算出／アルゴリズム処理ユニットごとに少なくとも一つのトークンを分配するために並列パケット算出／アルゴリズム処理ユニットごとに十分なトークンを含む、すなわち、満たしている場合、段階の十分な自由度／可変性がある。したがって、一実施の形態によれば、並列パケット処理を提供する処理ユニットのセットＳＰＵがトークンを有する限り、すなわち、トークンの一部の数Ｎ１，Ｎ２，．．．，Ｎｎを使い切らない限り、並列パケット処理を提供する処理ユニットのセットＳＰＵは、適切なパケット処理を保証／提供する。
【００２２】
一実施の形態によれば、段階の自由度／可変性は、一般的アルゴリズムに関連してもよい。受信したトラフィックが、許容されるトラフィック制限を表すしきい値／制限を超える場合、及び／又は、受信したトラフィックがしきい値／制限を超える限りにおいて並列アルゴリズムＡｐａｒに従ってパケットを処理する処理ユニットのセットＳＰＵが適切なパケット処理を保証／提供することができる場合、段階の十分な自由度／可変性がある。トラフィックシェーピングに対して、しきい値／制限は、ネットワークアドミニストレータによってしばしば設定され、しきい値／制限を適切な値に選択することができる。例えば、ある種類／タイプのネットワークトラフィックを、例えば、ビット／秒で測定／決定することができ、しきい値／制限は、最大の決定／測定されたトラフィック値、例えば、ある種類／タイプのトラフィックの使用を許容する最大のビット／秒に設定される。一般的には、ある種類／タイプのトラフィックを制限することによって、他のタイプのトラフィックに利用できるリソースが更に多くなる。ここではトークンバケットアルゴリズムについて説明するとしても本明細書で説明する実施の形態が一般的アルゴリズムを用いて実現されてもよいことに留意されたい。
【００２３】
本明細書で主に説明する一実施の形態によれば、ここで説明するパケットの処理／実行／算出／計算を行うトラフィックシェーピング方法は、少なくとも一時的に及び少なくとも部分的に並列モードＡｐａｒで実行されるとともにトークンバケット方法／アルゴリズムと組み合わされる。トークンバケットアルゴリズムは、ここで説明するようにネットワークの制限を実現する方法／アルゴリズムである。トークンバケット方法／アルゴリズムを、計算の複雑性をほとんど加えることなく実現することができる。したがって、トークンバケット方法／アルゴリズムを、ここで説明するパケット処理方法に適用してもよい。この結果、トークンバケット方法／アルゴリズムの原理に従ってパケットを処理／実行／算出／計算するパケット処理／実行／算出／計算方法／アルゴリズムが効率的であるとともに少なくとも部分的に並列となる。
【００２４】
第１の態様の一実施の形態によれば、並列パケット処理アルゴリズムＡｐａｒに従う処理を用いるときにトークンの一部の数Ｎ１，Ｎ２，．．．，Ｎｎを経時的に増加させる。
【００２５】
第１の態様の一実施の形態によれば、トークンの一部の数Ｎ１，Ｎ２，．．．，Ｎｎの全てをトークンの累算した総数Ｎｔｏｔ；Ｎｔｏｔ＝Ｎ１＋Ｎ２＋．．．＋Ｎｎに足し合わせることと、
全ての負担Ｃ１，Ｃ２，．．．，Ｃｎを累算した総コストＣｔｏｔに足し合わせることと、
順次パケット処理アルゴリズムＡｓｅｒに従う処理に切り替えるとき及び／又はドロップモードアルゴリズムＡｄｒｏｐに従う処理に切り替えるときにトークンの総数Ｎｔｏｔ及び／又は総コストＣｔｏｔを利用することと、
を更に有する。
【００２６】
第１の態様の一実施の形態によれば、順次パケット処理アルゴリズムＡｓｅｒは、
順次パケット処理アルゴリズムＡｓｅｒによって費やされるトークンより迅速にトークンの総数Ｎｔｏｔを増加させることと、
トークンの総数Ｎｔｏｔが並列処理しきい値Ｎｔｏｔ＿ｐａｒより大きい（Ｎｔｏｔ＞Ｎｔｏｔ＿ｐａｒ）ときに順次パケット処理アルゴリズムＡｓｅｒに従う処理から並列パケット処理アルゴリズムＡｐａｒに従う処理に切り替えることと、
を含む。
【００２７】
第１の態様の一実施の形態によれば、総コストＣｔｏｔが総デットＤｔｏｔを含むときに並列処理しきい値Ｎｔｏｔ＿ｐａｒを総デットＤｔｏｔに対応する値Ｎｄｅｂｔ＿ｓｕｍだけ増加させる。
【００２８】
第１の態様の一実施の形態によれば、順次パケット処理アルゴリズムＡｓｅｒに従う処理からドロップモードアルゴリズムＡｄｒｏｐに従う処理に切り替えることと、
トークンの総数Ｎｔｏｔがゼロ（０）の値を有すること（Ｎｔｏｔ＝０）及び
総コストＣｔｏｔがトークンの総数Ｎｔｏｔを超えること（Ｃｔｏｔ＞Ｎｔｏｔ）の群において少なくとも一つが真である場合に少なくとも部分的に同期しない少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎのセットＳＰＵを用いることによってドロップモードアルゴリズムＡｄｒｏｐに従ってパケットを処理することと、
を更に含む。
【００２９】
第１の態様の一実施の形態によれば、ドロップモードアルゴリズムＡｄｒｏｐに従う処理は、
少なくとも一つのパケットをドロップすること、
少なくとも一つのパケットをキューイングすること及び
不適合のラベルを付した少なくとも一つのパケットを送信することの群の少なくとも一つの動作を含む。
【００３０】
順次モード／アルゴリズムＡｓｅｒパケット処理を、パケットをキューイングするのに用いてもよい。並列モード／アルゴリズムＡｐａｒパケット処理を用いるとき、パケットをキューイングする必要がない。その理由は、ビット／秒及び／又はパケット／秒のような少なくとも一つのトラフィック特性が設定されたしきい値／制限より低いからである。設定されたしきい値／制限を超えるとき、パケットを、パケットを送出することができる速度より速く受信する。これが起こるとともにパケットキューが充填されている場合、アルゴリズムは、少なくとも一つのネットワークパケットを送出することができるまでに要する時間を計算する。この時間中、到達する全てのパケットを廃棄／処分する必要がある又はキューイングする、すなわち、ドロップモードＡｄｒｏｐにする必要がある。パケットキューが充填されている、すなわち、設定されたしきい値／制限を超えるとき、ドロップモードＡｄｒｏｐにおいてパケットをキューイングする必要がない。その理由は、いずれにしてもパケットが廃棄されるからである。したがって、パケットキューの利点が実現されるが、方法／アルゴリズム／キューイングは、順次モード／アルゴリズムＡｓｅｒが有効である／用いられるとき、すなわち、いずれにしてもアクセスが同期されるときに同期をとるだけでよい。
【００３１】
第１の態様の一実施の形態によれば、トークンの総数Ｎｔｏｔが総コストＣｔｏｔを超える（Ｎｔｏｔ＞Ｃｔｏｔ）場合、
ドロップモードアルゴリズムＡｄｒｏｐに従う処理から順次パケット処理アルゴリズムＡｓｅｒに従う処理に切り替えることと、
順次パケット処理アルゴリズムＡｓｅｒに従ってパケットを処理することと、
を更に含む。
【００３２】
したがって、パケット処理を、ドロップモードアルゴリズムＡｄｒｏｐから順次パケット処理アルゴリズムＡｓｅｒに切り替えることができる。
【００３３】
トラフィック量が設定されたしきい値／制限より上であるとき、パケット処理は、一部の状況において、単一のパケットを処理するだけのために一時的に順次パケット処理Ａｓｅｒに切り替わる。単一のパケットが処理された後、パケット処理は、ドロップモード処理Ａｄｒｏｐにすぐに戻る。最適化として、セットＳＰＵの処理ユニットの一つを正確に順次モード処理Ａｓｅｒに切り替えることができるようにするためにアルゴリズムを一実施の形態に従って実行することができる。例えば、順次モード／アルゴリズムＡｓｅｒへの一時的な切替を、場合によっては順次モード／アルゴリズムＡｓｅｒを実現する方法に応じてトライロックミューテックス（ｔｒｙ−ｌｏｃｋ  ｍｕｔｅｘ）及び／又はアトミックコンペアアンドセット（ａｔｏｍｉｃ  ｃｏｍｐａｒｅ  ａｎｄ  ｓｅｔ）（ＣＡＳ）によって行うことができる。ＣＡＳ動作によれば、既知の値がコンピュータ／プロセッサメモリの位置／空間と比較され、既知の値がメモリに格納される場合、既知の値から他の値へのアトミックな置換／書換が行われる。既知の値が記憶位置に存在しない／格納されていない場合、メモリに何も書き込まれず、動作信号が生じない。例えば、既知の値を、現在の時間表示を上書きするタイムスタンプとしてもよい。したがって、一つの処理ユニットのみが順次モード処理Ａｓｅｒへの一時的な切替をうまく行うことができる。これによって、設定されたしきい値／制限より上のトラフィック量を並列に取り扱うことができ、同時に、パケットキュー及び／又はトークンの順次の更新を行うことができる。一つの処理ユニットのみが順次モード処理Ａｓｅｒへの一時的な切替をうまく行うことができるが、ここでは、これを、一つのパケットを送出するときにのみ行う。これによって、セットＳＰＵの全ての処理ユニットは、とにかく進展し、待機のない／ブロックのないアルゴリズムの拡張を実現する。
【００３４】
第１の態様の一実施の形態によれば、各々がネットワークノードを介してパケットを受信する一つ以上の装置に関連した少なくとも一つのアクティブ群Ｇ１，Ｇ２，．．．，Ｇｋを規定することと、
セットの少なくとも一つのアクティブ群Ｇ１，Ｇ２，．．．，Ｇｋに対してネットワークの利用できる帯域幅の少なくとも一つの帯域幅部分を割り当てることと、を更に含み、割り当てることは、並列に実行されるとともに少なくとも一つのアクティブ群Ｇ１，Ｇ２，．．．，Ｇｋに対して少なくとも部分的に同期しない。
【００３５】
第１の態様の一実施の形態によれば、少なくとも一つのクライアント群Ｇ１，Ｇ２，．．．，Ｇｋは、
少なくとも一つの発信元インターネットプロトコル（ＩＰ）アドレス、
少なくとも一つの宛先インターネットプロトコル（ＩＰ）アドレス、
少なくとも一つの発信元ネットワーク、
少なくとも一つの宛先ネットワーク、
少なくとも一つの発信元ポート、
少なくとも一つの宛先ポート、
少なくとも一つの受信インタフェース、
少なくとも一つの転送インタフェース、
アプリケーション層データに関連した少なくとも一つのパラメータ及び
ネットワークトラフィックの少なくとも一つのパーティションの群の一つ以上に関連する。
【００３６】
第１の態様の一実施の形態によれば、利用できる帯域幅が少なくとも一つの群Ｇ１，Ｇ２，．．．，Ｇｋの間で略均等に分割されるように少なくとも一つの帯域幅部分の割当てを行う。
【００３７】
第１の態様の一実施の形態によれば、少なくとも一つの帯域幅部分の割当ては、少なくとも一つの群Ｇ１，Ｇ２，．．．，Ｇｋの一つ以上の帯域幅部分が使用されていないか否かを判定することと、
一つ以上の使用されていない帯域幅部分を、更なる帯域幅を必要としている少なくとも一つの群Ｇ１，Ｇ２，．．．，Ｇｋの他の一つ以上に再割り当てすることと、
を更に含む。
【００３８】
第１の態様の一実施の形態によれば、更なる帯域幅を必要としている少なくとも一つの群Ｇ１，Ｇ２，．．．，Ｇｋは、再割り当てされた一つ以上の帯域幅部分に対して互いに競合する。
【００３９】
本発明の第２の態様によれば、ネットワークノードを提供し、ネットワークノードは、少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎのセットＳＰＵの同期した利用を提供する順次パケット処理アルゴリズムＡｓｅｒ及び少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎのセットＳＰＵの少なくとも部分的に同期しない利用を提供する並列パケット処理アルゴリズムＡｐａｒに少なくとも従ってネットワークに送信されるパケットの処理を行うために配置された処理装置を含み、
パケットの処理は、少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎのセットＳＰＵによって協力的に負担される総パケットコストＣｔｏｔに対応する。処理装置は、並列パケット処理アルゴリズムＡｐａｒに従う処理がパケットを処理するために用いられるとき、少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎの一つ以上に対する総パケットコストＣｔｏｔの負担Ｃ１，Ｃ２，．．．，Ｃｎが少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎのパケットを処理する容量を超えているか否かを判定し、容量は、一つ以上のパケットに対応し、
少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎの一つ以上に対する総パケットコストＣｔｏｔの負担Ｃ１，Ｃ２，．．．，Ｃｎが容量を超えていると判定された場合、並列パケット処理アルゴリズムＡｐａｒに従う処理から順次パケット処理アルゴリズムＡｓｅｒに従う処理に切り替えるために配置される。
【００４０】
第２の態様の一実施の形態によれば、処理装置は、少なくとも部分的に同期しない並列パケット処理アルゴリズムＡｐａｒに対して配置され、少なくとも部分的に同期しない並列パケット処理アルゴリズムＡｐａｒは、
セットＳＰＵの少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎに関連した優先レベルＰｈｉｇｈ：Ｐｌｏｗに基づいて処理の優先順位付けを行うことを更に含み、これによって、
高い優先順位Ｐｈｉｇｈに関連した処理ユニットＰＵｈｉｇｈは、パケットを処理するとともにパケットの処理に対応する部分デットＤ１＿ｆｒａｃ，Ｄ２＿ｆｒａｃ，．．．，Ｄｎ＿ｆｒａｃを低い優先順位Ｐｌｏｗに関連するセットＳＰＵの一つ以上の処理ユニットＰＵｌｏｗにチャージすることを許容され、
少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎに対する総パケットコストＣｔｏｔの負担Ｃ１，Ｃ２，．．．，Ｃｎはそれぞれ、部分パケットコストＣ１＿ｆｒａｃ，Ｃ２＿ｆｒａｃ，．．．，Ｃｎ＿ｆｒａｃ及び部分デットＤ１＿ｆｒａｃ，Ｄ２＿ｆｒａｃ，．．．，Ｄｎ＿ｆｒａｃ；Ｃ１＝Ｃ１＿ｆｒａｃ＋Ｄ１＿ｆｒａｃ，Ｃ２＝Ｃ２＿ｆｒａｃ＋Ｄ２＿ｆｒａｃ，．．．，Ｃｎ＝Ｃｎ＿ｆｒａｃ＋Ｄｎ＿ｆｒａｃを含む。
【００４１】
第２の態様の一実施の形態によれば、処理装置は、並列パケット処理アルゴリズムＡｐａｒに従う処理が用いられるときに部分デットＤ１＿ｆｒａｃ，Ｄ２＿ｆｒａｃ，．．．，Ｄｎ＿ｆｒａｃを経時的に減少させるために配置される。
【００４２】
第２の態様の一実施の形態によれば、処理装置は、
少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎのセットＳＰＵが全体としてパケットを処理することができるか否かを判定することができないために、並列パケット処理アルゴリズムＡｐａｒに従ってパケットを処理するとともに総パケットコストＣｔｏｔの負担Ｃ１，Ｃ２，．．．，Ｃｎがパケットを処理する容量を超える少なくとも部分的に同期しない処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎを判定し、
少なくとも部分的に同期しない処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎを用いることによって、少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎのセットＳＰＵが全体としてパケットを処理することができるか否かを判定することができない結果として順次パケット処理アルゴリズムＡｓｅｒに従う処理に切り替えることを要求するために配置される。
【００４３】
第２の態様の一実施の形態によれば、少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎの一つ以上は、
中央処理装置（ＣＰＵ）及び
中央処理装置コアの群の一つである。
【００４４】
第２の態様の一実施の形態によれば、並列パケット処理アルゴリズムＡｐａｒは、少なくとも部分的に同期しないトークンバケットアルゴリズムであり、
総パケットコストＣｔｏｔは、トークンの総数Ｎｔｏｔに関連し、
トークンの総数Ｎｔｏｔは、少なくとも部分的に同期しない少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎに対するトークンの一部の数Ｎ１，Ｎ２，．．．，ＮｎとしてセットＳＰＵに対してそれぞれ分けられ、
総パケットコストＣｔｏｔの負担Ｃ１，Ｃ２，．．．，Ｃｎは、トークンの一部の数Ｎ１，Ｎ２，．．．，Ｎｎにそれぞれ関連する。
【００４５】
第２の態様の一実施の形態によれば、処理装置は、
処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎの負担Ｃ１，Ｃ２，．．．，Ｃｎ；Ｃ１＞Ｎ１，Ｃ２＞Ｎ２，．．．，Ｃｎ＞Ｎｎがトークンの一部の数Ｎ１，Ｎ２，．．．，Ｎｎを超えること及び
処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎがゼロ（０）のトークンの一部の数Ｎ１＝０，Ｎ２＝０，．．．，Ｎｎ＝０を有することの群の一つ以上が真である場合に、処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎに対する総パケットコストＣｔｏｔの負担Ｃ１，Ｃ２，．．．，Ｃｎがパケットを処理する容量を超えたと判定するために配置される。
【００４６】
第２の態様の一実施の形態によれば、処理装置は、並列パケット処理アルゴリズムＡｐａｒに従う処理を用いるときにトークンの一部の数Ｎ１，Ｎ２，．．．，Ｎｎを経時的に増加させるために配置される。
【００４７】
第２の態様の一実施の形態によれば、処理装置は、トークンの一部の数Ｎ１，Ｎ２，．．．，Ｎｎの全てをトークンの累算した総数Ｎｔｏｔ；Ｎｔｏｔ＝Ｎ１＋Ｎ２＋．．．＋Ｎｎに足し合わせることと、
累算した総コストＣｔｏｔに全ての負担Ｃ１，Ｃ２，．．．，Ｃｎを足し合わせることと、
順次パケット処理アルゴリズムＡｓｅｒに従う処理に切り替えるとき及び／又はドロップモードアルゴリズムＡｄｒｏｐに従う処理に切り替えるときにトークンの総数Ｎｔｏｔ及び／又は総コストＣｔｏｔを利用することと、
を行うために更に配置される。
【００４８】
第２の態様の一実施の形態によれば、処理装置は、順次パケット処理アルゴリズムＡｓｅｒにおいて配置され、順次パケット処理アルゴリズムＡｓｅｒは、
順次パケット処理アルゴリズムＡｓｅｒによって費やされるトークンより迅速にトークンの総数Ｎｔｏｔを増加させることと、
トークンの総数Ｎｔｏｔ）が並列処理しきい値Ｎｔｏｔ＿ｐａｒより大きい（Ｎｔｏｔ＞Ｎｔｏｔ＿ｐａｒ）ときに順次パケット処理アルゴリズムＡｓｅｒに従う処理から並列パケット処理アルゴリズムＡｐａｒに従う処理に切り替えることと、
を含む。
【００４９】
第２の態様の一実施の形態によれば、処理装置は、総コストＣｔｏｔが総デットＤｔｏｔを含むときに並列処理しきい値Ｎｔｏｔ＿ｐａｒを総デットＤｔｏｔに対応する値Ｎｄｅｂｔ＿ｓｕｍだけ増加させるために配置される。
【００５０】
第２の態様の一実施の形態によれば、処理装置は、順次パケット処理アルゴリズムＡｓｅｒに従う処理からドロップモードアルゴリズムＡｄｒｏｐに従う処理に切り替えることと、
トークンの総数Ｎｔｏｔがゼロ（０）の値を有すること（Ｎｔｏｔ＝０）及び
総コストＣｔｏｔがトークンの総数Ｎｔｏｔを超えること（Ｃｔｏｔ＞Ｎｔｏｔ）の群において少なくとも一つが真である場合に少なくとも部分的に同期しない少なくとも一つの理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎのセットＳＰＵを用いることによってドロップモードアルゴリズムＡｄｒｏｐに従ってパケットを処理することと、
を行うために更に配置される。
【００５１】
第２の態様の一実施の形態によれば、処理装置は、ドロップモードアルゴリズムＡｄｒｏｐに従う処理において配置され、ドロップモードアルゴリズムＡｄｒｏｐに従う処理は、
少なくとも一つのパケットをドロップすること、
少なくとも一つのパケットをキューイングすること及び
不適合のラベルを付した少なくとも一つのパケットを送信することの群の少なくとも一つの動作を含む。
【００５２】
第２の態様の一実施の形態によれば、処理装置は、トークンの総数Ｎｔｏｔが総コストＣｔｏｔを超える（Ｎｔｏｔ＞Ｃｔｏｔ）場合、
ドロップモードアルゴリズムＡｄｒｏｐに従う処理から順次パケット処理アルゴリズムＡｓｅｒに従う処理に切り替えることと、
順次パケット処理アルゴリズムＡｓｅｒに従ってパケットを処理することと、
を行うために更に配置される。
【００５３】
第２の態様の一実施の形態によれば、処理装置は、各々がネットワークノードを介してパケットを受信する一つ以上の装置に関連した少なくとも一つのアクティブ群Ｇ１，Ｇ２，．．．，Ｇｋを規定することと、
セットの少なくとも一つのアクティブ群Ｇ１，Ｇ２，．．．，Ｇｋに対してネットワークの利用できる帯域幅の少なくとも一つの帯域幅部分を割り当てることと、を行うために更に配置され、割り当てることは、並列に実行されるとともに少なくとも一つのアクティブ群Ｇ１，Ｇ２，．．．，Ｇｋに対して少なくとも部分的に同期しない。
【００５４】
第２の態様の一実施の形態によれば、処理装置は、少なくとも一つのクライアント群Ｇ１，Ｇ２，．．．，Ｇｋを、
少なくとも一つの発信元インターネットプロトコル（ＩＰ）アドレス、
少なくとも一つの宛先インターネットプロトコル（ＩＰ）アドレス、
少なくとも一つの発信元ネットワーク、
少なくとも一つの宛先ネットワーク、
少なくとも一つの発信元ポート、
少なくとも一つの宛先ポート、
少なくとも一つの受信インタフェース、
少なくとも一つの転送インタフェース、
アプリケーション層データに関連した少なくとも一つのパラメータ及び
ネットワークトラフィックの少なくとも一つのパーティションの群の一つ以上に関連させるために配置される。
【００５５】
第２の態様の一実施の形態によれば、処理装置は、利用できる帯域幅が少なくとも一つの群Ｇ１，Ｇ２，．．．，Ｇｋの間で略均等に分割されるように少なくとも一つの帯域幅部分の割当てを行うために配置される。
【００５６】
第２の態様の一実施の形態によれば、処理装置は、少なくとも一つの帯域幅部分の割当てに対して、少なくとも一つの群Ｇ１，Ｇ２，．．．，Ｇｋの一つ以上の帯域幅部分が使用されていないか否かを判定することと、
一つ以上の使用されていない帯域幅部分を、更なる帯域幅を必要としている少なくとも一つの群Ｇ１，Ｇ２，．．．，Ｇｋの他の一つ以上に再割り当てすることと、
を行うために配置される。
【００５７】
第２の態様の一実施の形態によれば、処理装置は、再割り当てされた一つ以上の帯域幅部分に対して互いに競合する更なる帯域幅を必要としている少なくとも一つの群Ｇ１，Ｇ２，．．．，Ｇｋを有するために配置される。
【００５８】
本発明の第２の態様によるネットワークノードの利点は、第１の態様による対応する方法の利点と同一である。
【００５９】
また、本発明の実施の形態は、処理手段によって実行するときに処理手段に本発明による方法を実行させるコード手段において特徴付けられるコンピュータプログラムに関する。さらに、本発明は、コンピュータ可読媒体及び上述したコンピュータプログラムを備え、上記コンピュータプログラムがコンピュータ可読媒体に含まれ、ＲＯＭ（リードオンリーメモリ）、ＰＲＯＭ（プログラマブルＲＯＭ）、ＥＰＲＯＭ（消去可能ＰＲＯＭ）、フラッシュメモリ、ＥＥＰＲＯＭ（電気的ＥＰＲＯＭ）及びハードディスクドライブの群からの一つ以上を備えるコンピュータプログラム製品に関する。
【００６０】
本発明の他の用途及び利点は、以下の詳細な説明から明らかになる。
【００６１】
添付図面は、本発明の種々の実施の形態を明瞭にするとともに説明することを意図するものである。
【図面の簡単な説明】
【００６２】
【図１】ネットワーク及びネットワークノードを線形的に示す。
【図２ａ】本発明の方法の種々の実施の形態のフローチャートを示す。
【図２ｂ】本発明の方法の種々の実施の形態のフローチャートを示す。
【図２ｃ】本発明の方法の種々の実施の形態のフローチャートを示す。
【図２ｄ】本発明の方法の種々の実施の形態のフローチャートを示す。
【図２ｅ】本発明の方法の種々の実施の形態のフローチャートを示す。
【図２ｆ】本発明の方法の種々の実施の形態のフローチャートを示す。
【図３】処理構造及び一部のパラメータを線形的に示す。
【図４】優先順位付けした処理及びデットを線形的に示す。
【図５】種々のパケット処理アルゴリズム及びこれらの間の切替を線形的に示す。
【発明を実施するための形態】
【００６３】
図１は、パケット交換ネットワーク５００を線形的に示し、示されたエンドポイントエンティティ／ユーザ／クライアントとすることもできる複数の通信エンティティ１１１，１１２，．．．，１１ｊは、ネットワークノード１００を介して接続され、一部の実施の形態によれば、場合によっては他のネットワークに接続される一つ以上のルータ１６１，１６２を介して接続される。通信エンティティ１１１，１１２，．．．，１１ｊを、少なくとも一つのワイドエリアネットワーク（ＷＡＮ）及び／又は少なくとも一つのローカルエリアネットワーク（ＬＡＮ）を介してネットワークノード１００及び／又はルータ１６１，１６２に接続してもよい。
【００６４】
ネットワークノード１００は、ファイアウォール装置、ルータ装置、ゲートウェイ装置、メディアゲートウェイ装置又はパケットが送出される他の適切な装置の一つ以上を含んでもよい。本発明によるネットワークノード１００を、ネットワークノードを流れる実質的にありとあらゆる種類のトラフィックのパケットにおいてトラフィックシェーピングを行うために配置される。
【００６５】
本発明によるネットワークノード１００は、例えば、方法のステップを実行するために配置した手段／制御装置１２１，１２２によって本発明の種々の実施の形態の方法を実行するために配置された処理装置１２０を含む。簡単にするために、二つの手段／制御装置１２１，１２２のみを図１に示すが、当然、処理装置１２０の三つ以上のそうような手段／制御装置が存在してもよい。個別に示す手段／制御装置１２１，１２２を含むものとして処理装置１２０を図１に示す。しかしながら、これらの装置１２１，１２２を、同一の物理的な装置において少なくともある程度論理的に分離して実現することができる。これらの手段／制御装置１２１，１２２を、少なくとも二つの異なる物理的なユニット／装置で実現される単一の論理ユニット／装置の一部としてもよい。これらの手段／制御装置１２１，１２２を、少なくとも二つの異なる物理的なユニット／装置において少なくともある程度論理的に分離して実現してもよい。さらに、これらの手段／制御装置１２１，１２２を、互いに論理的及び物理的に配置してもよい、すなわち、単一の物理ユニット／装置において実現される単一の論理ユニットの一部としてもよい。これらの手段／制御装置１２１，１２２は、例えば、プログラムコードの形態とすることができる命令の群に対応してもよく、命令の群は、手段／制御ユニットが有効である及び／又は方法ステップを実行するために利用されるときに少なくとも一つのプロセッサに入力されるとともに少なくとも一つのプロセッサによって利用される。
【００６６】
処理装置１２０は、少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎのセットＳＰＵ；１５０の同期した利用を提供する順次パケット処理アルゴリズムＡｓｅｒを実行するために配置される。本明細書において、少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎの各々を、中央処理装置（ＣＰＵ）及び／又は中央処理装置コアとしてもよい。また、ネットワークノード１００は、少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎのセットＳＰＵ；１５０の少なくとも部分的に同期しない利用を提供する並列パケット処理アルゴリズムＡｐａｒを実行するために配置される。
【００６７】
ネットワークノード１００を通過するパケットの処理は、総パケットコストＣｔｏｔに対応する。この総パケットコストＣｔｏｔは、少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎのセットＳＰＵ；１５０によって協力的に負担される。
【００６８】
図２ａは、本発明の一実施の形態による方法を示す。
【００６９】
第１のステップ２０５において、並列パケット処理アルゴリズムＡｐａｒが上記パケットを処理するために用いられる。
【００７０】
第２のステップ２１０において、少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎの一つ以上に対する総パケットコストＣｔｏｔの負担（ｓｈａｒｅ）Ｃ１，Ｃ２，．．．，Ｃｎが少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎのパケットを処理する容量を超えているか否かを判定する。ここでは、負担Ｃ１，Ｃ２，．．．，Ｃｎの各々は、一つ以上のパケットに対応する。各パケットは、処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎの一つによって完全に（ｉｎ  ｉｔｓ  ｅｎｔｉｒｅｔｙ）処理される。したがって、処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎの一つ以上がパケットを処理できないか否かを決定する。しかしながら、当然、異なる処理ユニットが全パケットを同時に処理してもよい、すなわち、全体の／完全なパケットを並列に処理してもよい。
【００７１】
第３のステップ２２０において、少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎの一つ以上に対する総パケットコストＣｔｏｔの負担Ｃ１，Ｃ２，．．．，Ｃｎが容量を超えていると第２のステップ２１０で判定された場合、パケット処理を、並列パケット処理アルゴリズムＡｐａｒに従う処理から順次パケット処理アルゴリズムＡｓｅｒに従う処理に切り替える。したがって、処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎの一つ以上がパケットを処理できない場合、パケット処理を、並列パケット処理アルゴリズムＡｐａｒに従う処理から順次パケット処理アルゴリズムＡｓｅｒに従う処理に切り替える。
【００７２】
第４のステップ２３０において、順次パケット処理アルゴリズムＡｓｅｒを利用するパケット処理を用いる。
【００７３】
並列パケット処理アルゴリズムＡｐａｒに従う処理を行うとき、少なくとも部分的に同期しない一つ以上の処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎは、並列パケット処理アルゴリズムＡｐａｒに従ってパケットを処理し、したがって、総パケットコストＣｔｏｔの対応する負担Ｃ１，Ｃ２，．．．，Ｃｎに関連させる。同期しない処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎの一つがパケットを処理する容量を超える場合、当該処理ユニットは、処理すべきパケットの総数の一部（ｐａｒｔ／ｆｒａｃｔｉｏｎ）を処理できないことを知る。しかしながら、処理ユニットが少なくとも部分的に同期していないので、当該処理ユニットは、少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎのセットＳＰＵ；１５０が全体としてパケットを処理することができるか否かを判定することができない。したがって、本実施の形態によれば、パケットを処理する容量を超える処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎは、順次パケット処理アルゴリズムＡｓｅｒに従う処理に切り替えることを要求する。したがって、容量を超える処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎは、セットＳＰＵ；１５０が全体としてパケットを処理することができるか否かを判定することができないので、当該処理ユニットは、処理アルゴリズムの切替を要求する。
【００７４】
本発明の一実施の形態によれば、並列パケット処理アルゴリズムＡｐａｒは、少なくとも部分的に同期しないトークンバケットアルゴリズムである。総パケットコストＣｔｏｔは、トークンの総数Ｎｔｏｔに関連する。トークンの総数Ｎｔｏｔは、少なくとも部分的に同期しない少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎに対するトークンの一部の数Ｎ１，Ｎ２，．．．，ＮｎとしてセットＳＰＵ；１５０に対してそれぞれ分けられてもよい。同様に、総パケットコストＣｔｏｔの負担Ｃ１，Ｃ２，．．．，Ｃｎは、トークンの一部の数Ｎ１，Ｎ２，．．．，Ｎｎにそれぞれ関連する。
【００７５】
本発明の一実施の形態によれば、処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎに対する総パケットコストＣｔｏｔの負担Ｃ１，Ｃ２，．．．，Ｃｎは、処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎの負担Ｃ１，Ｃ２，．．．，Ｃｎがトークンの一部の数Ｎ１，Ｎ２，．．．，Ｎｎを超える（Ｃ１＞Ｎ１，Ｃ２＞Ｎ２，．．．，Ｃｎ＞Ｎｎ）こと及び処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎがゼロ（０）のトークンの一部の数を有する（Ｎ１＝０，Ｎ２＝０，．．．，Ｎｎ＝０）ことの群の一つ以上が真である場合にパケットを処理する容量を超えたと判定される。
【００７６】
並列パケット処理アルゴリズムＡｐａｒに従う処理を用いるときにトークンの一部の数Ｎ１，Ｎ２，．．．，Ｎｎを経時的に増加させる。当然、トークンのこれらの一部の数Ｎ１，Ｎ２，．．．，Ｎｎは、パケットを処理するときに費やされる、すなわち、処理される一つ以上のパケットのコストは、一部の数Ｎ１，Ｎ２，．．．，Ｎｎから差し引かれる。
【００７７】
図３は、総パケットコストＣｔｏｔの負担Ｃ１，Ｃ２，．．．，Ｃｎ、一部の数Ｎ１，Ｎ２，．．．，Ｎｎ及び対応するタイムスタンプＴ１，Ｔ２，．．．，Ｔｎ、関連の処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ並びにトークン構造を線形的に示す。また、概念を表したパイプを線形的に示し、この場合、例えば、第１のパイプ（パイプ１）は、トークン構造／モード／アルゴリズムの少なくとも一部、トークンの一部の数Ｎ１、総パケットコストＣｔｏｔの負担Ｃ１及びタイムスタンプＴ１を含む。
【００７８】
漏洩バケットアルゴリズム（ｌｅａｋｙ  ｂｕｃｋｅｔ  ａｌｇｏｒｉｔｈｍ）としても知られているトークンバケットアルゴリズムは、時間単位ごとに所定の数のトークンを充填する概念バケット（ｃｏｎｃｅｐｔｕａｌ  ｂｕｃｋｅｔ）を用いる。バケットがトークンを累算するレートは、しばしばクオータ（ｑｕｏｔａ）と称され、しばしばトークン／秒で測定される。さらに、バケットは、限定された数のトークンだけを保持し、その後、一つ以上のトークンが廃棄される。どんなときにもバケットが保持することができるトークンの最大数は、バケット深度（ｂｕｃｋｅｔ  ｄｅｐｔｈ）として知られている。従来のトークンバケットアルゴリズムの問題は、従来のトークンバケットアルゴリズムが単一状態／モードの使用に基づくことである。本発明の実施の形態による並列処理アルゴリズムに対して、部分バケット（ｆｒａｃｔｉｏｎａｌ  ｂｕｃｋｅｔ）、トークンの一部の数Ｎ１，Ｎ２，．．．，Ｎｎ、総パケットコストＣｔｏｔの負担Ｃ１，Ｃ２，．．．，Ｃｎ及び／又は部分トークンクオータ（ｆｒａｃｔｉｏｎａｌ  ｔｏｋｅｎ  ｑｕｏｔａｓ）が並列パケットフローに関連して規定される。
【００７９】
換言すれば、順次アルゴリズムＡｓｅｒパケット処理の間に処理ユニットＰＵごとに十分な数のトークンが累算されるとき、例えば、トークンの総数Ｎｔｏｔが並列処理しきい値Ｎｔｏｔ＿ｐａｒより大きいとき（Ｎｔｏｔ＞Ｎｔｏｔ＿ｐａｒ）、後に詳しく説明するように、トラフィックシェーピングは、順次モード／アルゴリズムＡｓｅｒ処理から並列モード／アルゴリズムＡｐａｒ処理に遷移する／切り替わる。並列モード／アルゴリズムＡｐａｒ処理によれば、上述したように、単一のバケットが、複数の、少なくとも二つの同一サイズのｐｅｒ−ＰＵバケットに分割される。各ｐｅｒ−ＰＵバケットは、トークンの総数Ｎｔｏｔの均等な負担から始まる、すなわち、一部の数Ｎ１，Ｎ２，．．．，Ｎｎは、クオータの均一の負担及び所定のバケット深度が許容される。各処理ユニットＰＵが専用の（ｐｒｉｖａｔｅ）ｐｅｒ−ＰＵバケットを有するので、並列モードは、同期をとることなく専用バケットを自由に更新することができる。したがって、各ｐｅｒ−ＰＵバケットは、クオータの一部のみが与えられ、各ｐｅｒ−ＰＵバケットの深度は等しい。また、各ｐｅｒ−ＰＵバケットの全てのトークンの総和は、単一のバケットのトークンに等しい、すなわち、順次モード／アルゴリズムＡｓｅｒ処理によって用いられるトークンの総数Ｎｔｏｔに等しい。上述したように、例えば、ｐｅｒ−ＰＵバケットの一つ以上がトークンの負担すなわちトークンの一部の数Ｎ１，Ｎ２，．．．，Ｎｎを使い尽くす場合、順次モード／アルゴリズムＡｓｅｒ処理に戻る。
【００８０】
図２ｂは、並列アルゴリズムＡｐａｒから順次アルゴリズムＡｓｅｒ又はドロップモードアルゴリズムＡｄｒｏｐへのパケット処理の切替２２０に関連した本発明の方法２００の一実施の形態を示す。
【００８１】
切替２２０の第１のステップ２２１において、トークンの一部の数Ｎ１，Ｎ２，．．．，Ｎｎの全てを、トークンの累算された総数Ｎｔｏｔに合算／加算／累算する（Ｎｔｏｔ＝Ｎ１＋Ｎ２＋．．．＋Ｎｎ）。
【００８２】
切替２２０の第２のステップ２２２において、コストの全ての負担Ｃ１，Ｃ２，．．．，Ｃｎを累算した総コストＣｔｏｔに合算／加算／累算する。
【００８３】
切替２２０の第３のステップ２２３において、並列パケット処理アルゴリズムＡｐａｒによる処理への切替２２０を行う（ｄｏｎｅ／ｅｆｆｅｃｔｅｄ）ときに及び／又はドロップモードアルゴリズムＡｄｒｏｐによる処理への切替を行うときに、トークンの総数Ｎｔｏｔ及び／又は総コストＣｔｏｔを用いる。
【００８４】
したがって、本発明の一実施の形態によれば、並列モード／アルゴリズムＡｐａｒ処理から順次モード／アルゴリズムＡｓｅｒ処理への遷移／切替の間にパケットコストが外れる（ｓｌｉｐ  ｔｈｒｏｕｇｈ）ことができないことが保証される。トークンの総和Ｎｔｏｔが保存されるので、処理ユニットは、全体として設定されたレートに対応するコストより高いパケットコストを送り出すことができない。
【００８５】
これを、最初のパケットが同期した順次モード／アルゴリズムＡｓｅｒによって処理されるときに漂遊パケットが処理されないことを保証することが並列モード／アルゴリズムＡｐａｒ処理から順次モード／アルゴリズムＡｓｅｒ処理への切替を実行（ｅｘｅｃｕｔｉｎｇ／ｐｅｒｆｏｒｍｉｎｇ）する機能、例えば、プログラムコードの責任であるものとして見ることができる。
【００８６】
一実施の形態によれば、この問題の一つの解決は、並列モード／アルゴリズムＡｐａｒを用いてパケットを処理する間に並列モードＡｐａｒで単一のパケットを処理するのに要する最長時間より長い所定の時間が並列モード処理の終了から順次モード／アルゴリズムＡｓｅｒに従うパケット処理の開始まで経過すると仮定する“ｒｕｎ  ｔｏ  ｃｏｍｐｌｅｔｉｏｎ”概念を用いることである。最適化された機能／プログラミングコードに対して、所定の時間は、典型的には、非常に短い。しかしながら、実施の形態の実現は、この解決に限定されない。
【００８７】
トークンの部分ｐｅｒ−ＰＵ数Ｎ１，Ｎ２，．．．，Ｎｎが、一つ以上の処理ユニットが並列モード／アルゴリズムＡｐａｒに従ってパケットを処理した後の潜在的に長時間に亘って順次モード／アルゴリズムＡｓｅｒ処理において合計されるとき、コード／アルゴリズムは、個別の時間Ｔ１，Ｔ２，．．．，Ｔｎを考慮する。個別の時間Ｔ１，Ｔ２，．．．，Ｔｎは、部分ｐｅｒ−ＰＵバケットが更新されてから考慮される。これによって、同期をとりながら又は同期をとることなく最終パケットが処理されたときが決定される。これによって、コード／アルゴリズムは、全ての累算されたトークンＮｔｏｔを合計することができるとともに対応する処理ユニットによってパケットが処理される頻度を補償することができる。
【００８８】
図２ｃは、本発明の一実施の形態を示す。
【００８９】
第１のステップ２３０において、同期した順次パケット処理アルゴリズムＡｓｅｒを利用する。順次パケット処理アルゴリズムＡｓｅｒは、例えば、トークンバケットアルゴリズムに対応してもよい。
【００９０】
第２のステップ２５０において、順次パケット処理アルゴリズムＡｓｅｒによって費やされるトークンより迅速にトークンの総数Ｎｔｏｔを増加させる。これは、トークンの総数Ｎｔｏｔを経時的に増加させる効果を有する。その理由は、トークンの数が、パケット処理のためにバケットからトークンが差し引かれるのより迅速に増加するからである。
【００９１】
第３のステップ２６０において、トークンの総数Ｎｔｏｔが並列処理しきい値Ｎｔｏｔ＿ｐａｒより大きい（Ｎｔｏｔ＞Ｎｔｏｔ＿ｐａｒ）ときに順次パケット処理アルゴリズムＡｓｅｒに従う処理から並列パケット処理アルゴリズムＡｐａｒに従う処理に切り替える。
【００９２】
第４のステップ２０５において、少なくとも部分的に同期しない並列パケット処理アルゴリズムＡｐａｒを、パケットを処理するために用いる。
【００９３】
一般的には、トークンバケットアルゴリズムに対して、バケットにトークンが充填される。バケットに充填されるトークンの数を、最後のパケットが処理ユニットによって処理されてからの時間に基づいて、入力パケットの各々に対して計算することができる。これは、パフォーマンスを犠牲にしながら高い精度を与える。その理由は、大抵の実現がタイマによって与えられる規則的な間隔でトークンが加えるからである。順次モードＡｓｅｒは、処理ユニットの少なくとも部分的に同期しない利用を提供し、複数の処理ユニットの恩恵を受けない。その理由は、一つの処理ユニットが順次モード／アルゴリズムＡｓｅｒのパケットを処理することができるからである。したがって、パケットは、処理ユニットによって同期をとりながら一つずつ処理される。パケットを処理ユニットによって処理するために、当該処理ユニットに対してバケットに少なくとも一つのトークンが残っている必要がある。処理されるとともに送信されるパケットのそれぞれに対して、パケットのトークンコストがバケットから差し引かれる。
【００９４】
図２ｄは、本発明による方法２００の一実施の形態を示す。
【００９５】
第１のステップ２３０において、少なくとも部分的に同期しない順次パケット処理アルゴリズムＡｓｅｒを用いてパケットを処理する。
【００９６】
第２のステップ２７１において、トークンの総数Ｎｔｏｔがゼロ（０）の値を有する（Ｎｔｏｔ＝０）場合又は総コストＣｔｏｔがトークンの総数Ｎｔｏｔを超える（Ｃｔｏｔ＞Ｎｔｏｔ）場合、順次パケット処理アルゴリズムＡｓｅｒからドロップモードアルゴリズムＡｄｒｏｐに切り替える。
【００９７】
第３のステップ２７２において、例えば、少なくとも一つのパケットをドロップすること（２７３）、少なくとも一つのパケットをキューイングすること（２７４）及び／又は不適合のラベルを付した少なくとも一つのパケットを送信すること（２７５）を含むことができるドロップモードアルゴリズムＡｄｒｏｐに従ってパケットを処理する。
【００９８】
例えば、バケットの残りのトークンが非常に少ない場合、例えば、バケットのトークンがゼロである場合、例えば、パケットをＦＩＦＯ（先入先出）キューに入れるとともに累算のためにトークンを待機してもよい。
【００９９】
図２ｅは、本発明による方法２００の一実施の形態を示す。
【０１００】
第２のステップ２７２において、ドロップモードアルゴリズムＡｄｒｏｐに従ってパケットを処理する。
【０１０１】
第２のステップ２８１において、総コストＣｔｏｔがトークンの総数Ｎｔｏｔを超える（Ｃｔｏｔ＞Ｎｔｏｔ）場合、ドロップモードアルゴリズムＡｄｒｏｐに従う処理から順次パケット処理アルゴリズムＡｓｅｒに従う処理に切り替える。
【０１０２】
第３のステップ２３０において、順次パケット処理アルゴリズムＡｓｅｒに従ってパケットを処理する。
【０１０３】
並列パケット処理アルゴリズムＡｐａｒに従うパケット処理２０５、順次パケット処理アルゴリズムＡｓｅｒに従うパケット処理２３０、ドロップモードアルゴリズムＡｄｒｏｐに従うパケット処理２７２及びこれらの処理アルゴリズムの間の切替２２０，２６０，２７１，２８１を含む上述した実施の形態を、線形的かつ一般的に図５に示す。
【０１０４】
ドロップモード／状態／アルゴリズムＡｄｒｏｐによれば、処理されるパケットは、ドロップされる、キューイングされる及び／又はラベルを付して送信される。処理されるパケットのそれぞれに対して、バケットの累算されたトークンの数が計算されるが、ドロップモードを終了するために十分なトークンが累算されたとき、すなわち、トークンの総数Ｎｔｏｔが総コストＣｔｏｔを超える（Ｃｔｏｔ＞Ｎｔｏｔ）場合にのみ計算が行われる。実質的には、これを、例えば、Ｃｔｏｔ＞Ｎｔｏｔとするのに要する時間、例えば、バケットの一つ以上のトークンが測定／推定される時間として見ることができ、パケットキュー／アルゴリズムは、ドロップモード／アルゴリズムＡｄｒｏｐによる処理の間、すなわち、トークンの総数Ｎｔｏｔが総コストＣｔｏｔを超える（Ｃｔｏｔ＞Ｎｔｏｔ）まで更新されない。
【０１０５】
ドロップモード／アルゴリズムＡｄｒｏｐが更新を行わないので、処理ユニットのセットＳＰＵは、完全に並列に同期をとることなく実行することができる。トークンの総数Ｎｔｏｔが総コストＣｔｏｔを超える（Ｃｔｏｔ＞Ｎｔｏｔ）と、トラフィックシェーピングは、ドロップモードアルゴリズムＡｄｒｏｐに従う処理を終了する（２８１）とともに順次パケット処理アルゴリズムＡｓｅｒに従う処理を再び開始する。
【０１０６】
ドロップＡｄｒｏｐに従うパケット処理から順次Ａｓｅｒに従うパケット処理への遷移２８１は、場合によってはパケットの漏洩を許容する競争／競合に潜在的に満ちている。しかしながら、ドロップモード／アルゴリズムＡｄｒｏｐに従う処理は、典型的には、例えば、順次Ａｓｅｒ又は並列Ａｐａｒアルゴリズムに従うパケット処理より著しく低い頻度で起こるイベントであることに留意されたい。その理由は、遷移２８１の複雑性及びコストがトラフィックシェーピングの全パフォーマンスにとって重大でないからである。また、ドロップモード／アルゴリズムＡｄｒｏｐに従う処理から順次モード／アルゴリズムＡｓｅｒに従う処理への遷移／切替２８１は、作業負荷／総パケット処理が増大するに従って頻度が低くなる。
【０１０７】
ドロップモード／アルゴリズムＡｄｒｏｐに従うパケット処理に対する処理ユニットの同期が全くない。また、ドロップモード／アルゴリズムＡｄｒｏｐに従うパケット処理は並列に実行される。したがって、ドロップモード／アルゴリズムＡｄｒｏｐ処理及び並列モード／アルゴリズムＡｐａｒ処理の共通の特徴が存在する。しかしながら、並列モード／アルゴリズムＡｐａｒは、上限によって制限され、ドロップモード／アルゴリズムＡｄｒｏｐは、下限によって制限され、これらの制限の両方は、実際には同一の制限であり、かつ、トラフィックが制限される設定されたパケットトラフィックレートに関連する。
【０１０８】
ドロップモード／アルゴリズムＡｄｒｏｐから順次モード／アルゴリズムＡｓｅｒへの切替２８１があるとき、処理ユニットＳＰＵ；１５０の二つ以上が幾分同時に切替２８１の開始を試みることがある。したがって、このようなあり得る問題を取り扱う必要がある。
【０１０９】
したがって、ドロップモード／アルゴリズムＡｄｒｏｐ処理が全く同期しないので、所定の負荷において、ドロップモード／アルゴリズムＡｄｒｏｐの同時の開始及び終了の複数の重複する試みが存在する可能性が高い。本発明の一実施の形態によれば、単一（唯一）の処理ユニットＰＵがドロップモード／アルゴリズムＡｄｒｏｐ処理を首尾よく終了するとともにドロップモード／アルゴリズムＡｄｒｏｐ処理を終了する全ての試みがドロップモード／アルゴリズムの終了後に再び行うことを保証するのを確実にするのが終了コード／方法ステップの責任である。これを、例えば、複数の比較交換動作を用いることによって実現することができ、この場合、タイムスタンプとモード／アルゴリズムの両方がアトミックに検証されるとともに更新される。これによって、一つの処理ユニットだけが切替を行うことが保証される。また、ドロップモードの開始及び／又は終了の複数のあり得る重複する試みの中から最後の試みのみが成功する。
【０１１０】
例えば、バケットのトークンを所定のレートで累算することを実現することによって上述した問題を取り扱う他の解決が存在する。したがって、単一のトークンを累算するために所定の時間を要する。トークンバケットアルゴリズムの大抵の実現が微積分を用いるので、これより短い時間の選択は、ゼロトークンとなり、複数の同時の更新は同一結果となる。一例として、ドロップモード／アルゴリズム終了を危険域（ｃｒｉｔｉｃａｌ  ｓｅｃｔｉｏｎ）で行い、セットＳＰＵ；１５０の一つ以上のＰＵは、集中して仕事を行う（ｒｕｎ−ｔｏ−ｃｏｍｐｌｅｔｉｏｎ）。アルゴリズムは、終了タイミングを必要とする。その理由は、ＰＵがＣＰＵ移行（ＣＰＵ  ｍｉｇｒａｔｉｏｎ）、コンテキストスイッチ等の中断によって妨害されないからである。ここで説明する個別の時間Ｔ１，Ｔ２，．．．，Ｔｎの一つ以上に含めることができる又は他の時間パラメータに含めることができる規定したタイムスタンプＴｄが存在し、これは、ドロップモードＡｄｒｏｐに従う処理を行うときから経過した時間、例えば、順次モード／アルゴリズムＡｓｅｒからドロップモード／アルゴリズムＡｄｒｏｐへのパケット処理の切替２７１から経過した時間を表す。
【０１１１】
ＰＵは、一つ以上のタイムスタンプＴｄ、バケットのトークンの数、デット及び／又はモード／アルゴリズムがしばらくの間変更されなかったかを検証する。検証を、トークンの元の数及び／又は元々のデット及び関連の一つ以上のタイムスタンプＴｄと現在の値とを比較することによって行う。したがって、例えば、ここでは、一つ以上のタイムスタンプＴｄが変更されなかったことチェックすることができる。少なくとも一つのタイムスタンプＴｄが変更された場合、これは、タイムスタンプＴｄをチェックする処理ユニットが最初に切替を開始した処理ユニットでないことを表し、ｒｕｎ−ｔｏ−ｃｏｍｐｌｅｔｉｏｎ作業／処理を終了するとともにドロップモード／アルゴリズムＡｄｒｏｐに従う処理を処理ユニットに対して継続する。しかしながら、一つ以上のタイムスタンプＴｄが変更された場合、例えば、トークンの数が関係するとともにチェックされる必要がある。その理由は、ｒｕｎ−ｔｏ−ｃｏｍｐｌｅｔｉｏｎ作業／処理が順次モード／アルゴリズムＡｓｅｒに対するモード／アルゴリズムのコンペアアンドセット（ＣＡＳ）更新を継続するからである。ＣＡＳ更新がモード／アルゴリズム切替に用いられるので、一つの処理ユニットのみが更新／切替に成功する。このように成功した処理ユニットは、タイムスタンプＴｄを更新する。その後、同期した順次モード／アルゴリズムＡｓｅｒに従うパケット処理が用いられる。そして、ＣＡＳ更新が処理ユニットに対して成功したか否かに関係なくｒｕｎ−ｔｏ−ｃｏｍｐｌｅｔｉｏｎ作業／処理を終了する。
【０１１２】
本発明の一実施の形態によれば、少なくとも部分的に同期しない並列パケット処理アルゴリズムＡｐａｒは、優先順位付けを行うことを含む。優先順位付けを行うことは、セットＳＰＵ；１５０の少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎに関連した優先レベルＰｈｉｇｈ：Ｐｌｏｗに基づく。優先レベルを、例えば、処理すべきパケットに割り当ててもよい。例えば、一つのパケットに高い優先レベルＰｈｉｇｈを割り当ててもよい。したがって、高い優先順位のパケットが処理ユニットＰＵによって処理されるときに高い優先順位のパケットを処理する処理ユニットＰＵｈｉｇｈに当該高い優先レベルＰｈｉｇｈが割り当てられる／関連付けられる。同様に、他の時点で同一の処理ユニットＰＵが低い優先レベルＰｌｏｗが割り当てられたパケットを処理するときに、パケットに割り当てられる低い優先レベルＰｌｏｗが処理ユニットＰＵｌｏｗに割り当てられる／関連付けられる。
【０１１３】
優先順位付けを行うとき、高い優先順位Ｐｈｉｇｈが割り当てられた／高い優先順位Ｐｈｉｇｈに関連した処理ユニットＰＵｈｉｇｈは、パケットを処理するとともにパケットの処理に対応する部分デットＤ１＿ｆｒａｃ，Ｄ２＿ｆｒａｃ，．．．，Ｄｎ＿ｆｒａｃを低い優先順位Ｐｌｏｗが割り当てられた／低い優先順位Ｐｌｏｗに関連するセットＳＰＵ；１５０の一つ以上の処理ユニットＰＵｌｏｗにチャージ／デビットすることを許容される。
【０１１４】
したがって、高い優先レベルのパケットを、高い優先順位が一時的に割り当てられた少なくとも一つの処理ユニットＰＵｈｉｇｈによって処理することができ、当該処理のための部分コストは、低い優先順位Ｐｌｏｗが割り当てられた一つ以上の処理ユニットＰＵｌｏｗにデットされる。
【０１１５】
優先順位付けが用いられるとき、少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎに対する総パケットコストＣｔｏｔの負担Ｃ１，Ｃ２，．．．，Ｃｎはそれぞれ、部分パケットコストＣ１＿ｆｒａｃ，Ｃ２＿ｆｒａｃ，．．．，Ｃｎ＿ｆｒａｃ及び部分デットＤ１＿ｆｒａｃ，Ｄ２＿ｆｒａｃ，．．．，Ｄｎ＿ｆｒａｃを含み、デットは、他の高い優先順位の処理ユニットＰＵｈｉｇｈによって作成される（Ｃ１＝Ｃ１＿ｆｒａｃ＋Ｄ１＿ｆｒａｃ，Ｃ２＝Ｃ２＿ｆｒａｃ＋Ｄ２＿ｆｒａｃ，．．．，Ｃｎ＝Ｃｎ＿ｆｒａｃ＋Ｄｎ＿ｆｒａｃ）。本発明の実施の形態によれば、パケットが処理の際に分割されず、各パケットが全体として一つの処理ユニットＰＵによって処理されることに留意されたい。これは、単一のパケットのそれぞれの処理コストが一つの処理ユニットによって支持されることも意味する。しかしながら、処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎの各々が一つ以上の全パケットを処理するために、処理すべきパケットの総数が処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎのセットＳＰＵ；１５０の間で分割／分散される。同様に、部分デットＤ１＿ｆｒａｃ，Ｄ２＿ｆｒａｃ，．．．，Ｄｎ＿ｆｒａｃは、全パケットの処理に関連付けられる。
【０１１６】
並列パケット処理アルゴリズムＡｐａｒに従う処理が用いられるときに部分デットＤ１＿ｆｒａｃ，Ｄ２＿ｆｒａｃ，．．．，Ｄｎ＿ｆｒａｃを経時的に、例えば、ゼロの最小値まで減少させる。一般的には、処理すべきパケットが存在しない場合でも、部分デットＤ１＿ｆｒａｃ，Ｄ２＿ｆｒａｃ，．．．，Ｄｎ＿ｆｒａｃを、トークンの（一部の）数が経時的に増加するクオータに対応するレートで減少させる。
【０１１７】
異なる処理モード／アルゴリズムの間の切替を行うときの上述した規則はしばしば、モード／アルゴリズムの切替を決定するために総コストＣｔｏｔ及び／又はコストの負担Ｃ１，Ｃ２，．．．，Ｃｎとしきい値又は他の値とを比較する。優先順位付けを行うために、負担Ｃ１，Ｃ２，．．．，Ｃｎは、処理すべきパケットのための部分パケットコストＣ１＿ｆｒａｃ，Ｃ２＿ｆｒａｃ，．．．，Ｃｎ＿ｆｒａｃと部分デットＤ１＿ｆｒａｃ，Ｄ２＿ｆｒａｃ，．．．，Ｄｎ＿ｆｒａｃの両方を含む。これによって、切替決定を行うときにデットも考察されるすなわち考慮される。同様に、総コストＣｔｏｔは、全ての優先順位付けされたパケットに対するデットＤｔｏｔを含む。したがって、トークンの総数Ｎｔｏｔが並列処理しきい値Ｎｔｏｔ＿ｐａｒより大きい（Ｎｔｏｔ＞Ｎｔｏｔ＿ｐａｒ）ときに順次パケット処理アルゴリズムＡｓｅｒに従う処理から並列パケット処理アルゴリズムＡｐａｒに従う処理への切替を決定し、並列処理しきい値Ｎｔｏｔ＿ｐａｒを総デットＤｔｏｔに対応する値Ｎｄｅｂｔ＿ｓｕｍだけ増加させる。これを、並列処理しきい値Ｎｔｏｔ＿ｐａｒを総デットＤｔｏｔに対応する値Ｎｄｅｂｔ＿ｓｕｍだけ減少させるときにも見ることができる。
【０１１８】
図４は、高い優先レベルＰｈｉｇｈのパケットを高い優先レベルＰｈｉｇｈが一時的に割り当てられた少なくとも一つの処理ユニットＰＵｈｉｇｈによって処理することができ、当該処理に対する部分パケットコストＣ２＿ｆｒａｃにＤ２＿ｆｒａｃがデットされ、一つ以上のコスト負担Ｃ２が低い優先レベルＰｌｏｗが割り当てられた処理ユニットＰＵｌｏｗに関連することを示す。
【０１１９】
一般的には、ネットワークノード１００が、最短のあり得るレイテンシーで単一のパケットを取り扱う／処理するのに十分なリソースを有する限り、トラフィック優先順位に意味がない。トラフィックに優先順位付けを行うことは、トラフィックすなわち処理すべきパケットの数がネットワークノード１００の処理容量を超えるときにのみ有利である。これは、パケットを処理する総処理コストＣｔｏｔが総コスト制限Ｃｔｏｔ＿ｌｉｍを超える（Ｃｔｏｔ＞Ｃｔｏｔ＿ｌｉｍ）ことに対応する。その状況において、すなわち、処理容量を超えるとき、実質的にはトラフィック送出／処理を減少させることしかできない。したがって、本実施の形態による優先順位付けを行う処理は、ネットワークノード１００が高い優先順位のトラフィック／処理を取り扱うことができるように低い優先順位のトラフィックを制御しながら十分に減少させる方法である。
【０１２０】
概念的には、一般的にトラフィックコストに対する総コスト制限Ｃｔｏｔ＿ｌｉｍ及び高い優先順位のトラフィックコストに対する優先コスト制限Ｃｐｒｉｏ＿ｈｉｇｈ＿ｌｉｍを規定することができる。高い優先順位のトラフィックコストＣｐｒｉｏ＿ｈｉｇｈが優先コストＣｐｒｉｏに含まれるので、高い優先順位のパケット／トラフィックは、総コストＣｔｏｔの第１の負担及を取得し、ベストエフォートトラフィックすなわち低い優先順位のパケットに残りの負担が割り当てられる。高い優先順位のトラフィック／パケットとベストエフォートトラフィック／パケットのいずれも総コスト制限Ｃｔｏｔ＿ｌｉｍを超えない。したがって、総コスト制限Ｃｔｏｔ＿ｌｉｍより高い優先順位の制限Ｃｐｒｉｏ＿ｈｉｇｈ＿ｌｉｍは無意味である。総コスト制限Ｃｔｏｔ＿ｌｉｍより低い優先コスト制限Ｃｐｒｉｏ＿ｈｉｇｈ＿ｌｉｍを設定することは、優先コスト制限Ｃｐｒｉｏ＿ｈｉｇｈ＿ｌｉｍを超えるようにするコストを有する高い優先順位のパケットを別に取り扱う／処理する必要があることを意味する。典型的には、これは、高い優先順位のパケットが降格／廃棄される、すなわち、その状態／優先順位をベストエフォート状況／レベルＰｌｏｗまで減少させることを意味する。
【０１２１】
高い優先順位ＰｈｉｇｈとベストエフォートＰｌｏｗのいずれでパケットを取り扱うかを選択するための優先順位付けされたトラフィックの追跡を、総コスト制限Ｃｔｏｔ＿ｌｉｍを超えるときにパケットをドロップしないように変更した制限パケット処理によって行うことができる。代わりに、パケット処理は、パケットを送出／パスするか否かの決定しか行わない。送出／パスされるパケットは、総コスト制限Ｃｔｏｔ＿ｌｉｍ内であり、送出／パスされないパケットは、ベストエフォートレベルＰｌｏｗまで降格させる。この機能を、追跡パイプ又はパケット分類器に付し、シグナリング／セキュリティゲートウェイ（ＳＧＷ）コード／アルゴリズムにおいて、ベースパイプと対照をなすように優先パイプに付す。
【０１２２】
一般的には、パイプは、モード／アルゴリズムを処理する少なくとも一つのトークンバケット処理構造、少なくとも一つのタイムスタンプ、（トークンの一部の数とすることができる）バケットのトークンの少なくとも一つの数及び／又は（部分デットとすることができる）少なくとも一つのデットを含む概念的なオブジェクトとして規定することができる。
【０１２３】
トークンデット及び部分デットの概念を含む上述した実施の形態による処理によって、制限パケット処理を、高い優先順位のトラフィック／パケット処理により要求される量を有しながら低い優先順位のトラフィック／パケット処理を減少させることができるものにすることができる。デットの概念は、バケット又は部分バケットをゼロ未満のトークンを有することが許容されるバケットとして概念的に見ることができる。バケットが有するそのような概念的な負のトークンが多くなるに従って、制限処理がドロップモードＡｄｒｏｐのままでいる時間が長くなる。原理的には、高い優先順位のパケットが送信されるとき、高い優先順位のパケットの仮想的なコピーが低い優先順位のパケットが流れる、すなわち、低い優先順位のパケットに対応する部分デットが低い優先順位のトラフィック／パケット処理ユニットによって引き受けられた処理ユニットＰＵにアカウント／関連付けすると振る舞う／仮定することもできる。一実施の形態によれば、パケットの仮想的なコピーを用いることができる。その理由は、高いパフォーマンス／優先順位のパケットのコストが実際には低い優先順位の処理ユニットにのみチャージ／デビットされるとともに高い優先順位のパケットが低い優先順位のトラフィック／パケット処理のために帯域幅を使い尽くすからである。
【０１２４】
優先順位付けの一つのあり得る問題は、高い優先順位のトラフィック／パケットが低い優先順位のパケットの処理のために同期を待機する必要がないことである。したがって、一実施の形態によれば、デットを、ｐｒｅ−ＰＵ変数として、すなわち、上述した部分デットＤ１＿ｆｒａｃ，Ｄ２＿ｆｒａｃ，．．．，Ｄｎ＿ｆｒａｃとして表す。技術的には、部分デットＤ１＿ｆｒａｃ，Ｄ２＿ｆｒａｃ，．．．，Ｄｎ＿ｆｒａｃは、並列モード／アルゴリズムＡｐａｒパケット処理によって用いられるような同一のｐｅｒ−ＰＵバケットすなわち同一の部分バケットを用いることができる。その理由は、いずれにしても並列モード／アルゴリズムＡｐａｒを並列に更新することができるからである。しかしながら、実用的な実現において、これがパケット処理をモード／アルゴリズム間で迅速に切り替えるときに競合状態及び例外（ａｎｏｍａｌｉｅｓ）を導入することが確認された。したがって、本発明の実施の形態によれば、個別のｐｅｒ−ＰＵパラメータは、デットすなわち部分デットＤ１＿ｆｒａｃ，Ｄ２＿ｆｒａｃ，．．．，Ｄｎ＿ｆｒａｃを制御するために用いられ、これによって、全く同期しない部分デットＤ１＿ｆｒａｃ，Ｄ２＿ｆｒａｃ，．．．，Ｄｎ＿ｆｒａｃの追加を許容する。
【０１２５】
さらに、未処理の（ｏｕｔｓｔａｎｄｉｎｇ）デット、すなわち、パケット処理アルゴリズムがまだ認められていない総デットＤｔｏｔを、全てのｐｅｒ−ＰＵデットの総和、すなわち、部分デットＤ１＿ｆｒａｃ，Ｄ２＿ｆｒａｃ，．．．，Ｄｎ＿ｆｒａｃの総和から最後の既知のテッドを差し引いたものとして規定してもよい。これによって、パケット処理アルゴリズムを、ｐｅｒ−ＰＵデットすなわち部分デットＤ１＿ｆｒａｃ，Ｄ２＿ｆｒａｃ，．．．，Ｄｎ＿ｆｒａｃの進行中の同時の更新があるとしても取扱後に未処理の総デットＤｔｏｔをリセットすることができる。
【０１２６】
したがって、総未処理デットＤｔｏｔの合計は、比較的不経済な動作（ｒｅｌａｔｉｖｅｌｙ  ｅｘｐｅｎｓｉｖｅ  ｏｐｅｒａｔｉｏｎ）である。その理由は、それが必要なときのみ行われるからである。そのような必要なイベントが消失した場合、総未処理デットＤｔｏｔは、後にイベントが生じるまで残存する。これによって未処理デットの合算を行うことを決定するときにパケット処理コード／アルゴリズムを少し柔軟にすることができる。その理由は、これを頻繁に行うのではなくめったに行わないのが有利であるからである。最終結果は同一である。
【０１２７】
例えば、複数の優先レベルＰｈｉｇｈ：Ｐｌｏｗを利用するパケット処理を取り扱うために、優先パイプは、デット概念の利用のサポートの下で複数の制限／優先順位付パイプのシーケンスをセットアップすることができる。これらのパイプを、例えば、表されたベースパイプとしてもよい。全てのそのようなベースパイプを、例えば、全体の優先順位付けパイプの総コスト制限Ｃｔｏｔに関連した同一のクオータ及びバケット深度で構成することができる。限定されない例として、ベストエフォートすなわち低い優先順位のＰｌｏｗパケットとして分類されたトラフィック／パケットを、例えば、ベストエフォートベースパイプを介して送信することができる。最高の優先順位として分類されたトラフィック／パケットを、最上位の優先順位のベースパイプを介して送信することができる。パケットがドロップした場合、何も起こらない。しかしながら、パケットがパイプコスト制限にあっていることを最上位の優先順位のベースパイプが宣言すると仮定すると、既に送信されたパケットのコストを、低い優先順位の全てのベースパイプからベストエフォートの／低い優先順位のＰｌｏｗパイプまで適用することもできる。その影響は、高い優先順位のＰｈｉｇｈパケットが全ての低い優先順位レベルのＰｌｏｗパケットに対する帯域幅を使い尽くすことである。二つ以上の規定された優先レベルが存在してもよいこと、すなわち、ベストエフォート優先レベルと最上位の優先レベルの間に一つ以上の規定された優先レベルが存在してもよいことに留意されたい。
【０１２８】
図２ｆは、本発明の一実施の形態による方法２００を示す。
【０１２９】
第１のステップ２３０／２７２において、パケットを、上述した順次パケット処理アルゴリズムＡｓｅｒ及び／又は上述したロップモードアルゴリズムＡｄｒｏｐを用いて処理する。
【０１３０】
第２のステップ２９１において、少なくとも一つのアクティブ群Ｇ１，Ｇ２，．．．，Ｇｋを規定し、各群は、ネットワークノードを介してパケットを受信する一つ以上のデバイスに関連する。
【０１３１】
第３のステップ２９２において、例えば、ネットワーク５００及び／又はネットワークノード１００の利用できる帯域幅の少なくとも一つの帯域幅部分を、セットの少なくとも一つのアクティブ群Ｇ１，Ｇ２，．．．，Ｇｋに割り当てる。この割当て２９２は、並列に行われ、少なくとも一つのアクティブ群Ｇ１，Ｇ２，．．．，Ｇｋに対して少なくとも部分的に同期しない。
【０１３２】
一実施の形態によれば、利用できる帯域幅が少なくとも一つの群Ｇ１，Ｇ２，．．．，Ｇｋの間で略均等に分割されるように少なくとも一つの帯域幅部分を割り当てる（２９２）。
【０１３３】
本発明の一実施の形態によれば、方法の第３のステップ２９２は、少なくとも一つの群Ｇ１，Ｇ２，．．．，Ｇｋの一つ以上の帯域幅部分が使用されていないか否かを判定するステップ２９３を含んでもよい。第３のステップ２９２は、一つ以上の使用されていない帯域幅部分を、更なる帯域幅を必要としている少なくとも一つの群Ｇ１，Ｇ２，．．．，Ｇｋの他の一つ以上に再割り当てする第５のステップ２９４を含んでもよい。一実施の形態によれば、更なる帯域幅を必要としている少なくとも一つの群Ｇ１，Ｇ２，．．．，Ｇｋは、再割り当て（２９４）された一つ以上の帯域幅部分に対して互いに競合する。
【０１３４】
本発明の一実施の形態によれば、少なくとも一つの群Ｇ１，Ｇ２，．．．，Ｇｋは、ネットワークトラフィックの重なり合わない／分離した一つ以上のサブセットＳ１，Ｓ２，．．．，Ｓｋに関連する。ここでは、トラフィックを、決定した適切な規則／規定によって、例えば、ネットワークアドミニストレータによって一つ以上のサブセットＳ１，Ｓ２，．．．，Ｓｋに分割してもよい。一つ以上のサブセットＳ１，Ｓ２，．．．，Ｓｋを、例えば、次のように規定してもよい。
各クライアント群Ｇ１，Ｇ２，．．．，Ｇｋは、所定のＩＰアドレス又はネットワーク範囲からのネットワークトラフィックに対応する／当該ネットワークトラフィックを含む。
各クライアント群Ｇ１，Ｇ２，．．．，Ｇｋは、所定のＩＰアドレス又はネットワーク範囲へのネットワークトラフィックに対応する／当該ネットワークトラフィックを含む。
各クライアント群Ｇ１，Ｇ２，．．．，Ｇｋは、検証されたユーザ及び／又は送信されるデータのタイプのような上位層データに関連したネットワークトラフィックに対応する／当該ネットワークトラフィックを含む。
【０１３５】
これを、
少なくとも一つの発信元インターネットプロトコル（ＩＰ）アドレス、
少なくとも一つの宛先インターネットプロトコル（ＩＰ）アドレス、
少なくとも一つの発信元ネットワーク、
少なくとも一つの宛先ネットワーク、
少なくとも一つの発信元ポート、
少なくとも一つの宛先ポート、
少なくとも一つの受信インタフェース、
少なくとも一つの転送インタフェース、
アプリケーション層データに関連した少なくとも一つのパラメータ及び
ネットワークトラフィックの少なくとも一つのパーティションの群の一つ以上に関連した少なくとも一つのクライアント群Ｇ１，Ｇ２，．．．，Ｇｋとして説明することもできる。
【０１３６】
グループ分けを、ダイナミックパイプ／パケット処理フローのセットの形態の実質的な処理として見ることができる。各群Ｇ１，Ｇ２，．．．，Ｇｋは、グループごとの制限及び負担を追跡する群カウンタ／パラメータのセットを割り当てることができる。群Ｇ１，Ｇ２，．．．，Ｇｋが必要とされる場合に群Ｇ１，Ｇ２，．．．，Ｇｋが割り当てられ、無活動（ｉｎａｃｔｉｖｉｔｙ）の期間ｔｉｎａｃｔｉｖｅが閾値ｔｉｎａｃｔｉｖｅ＿ｔｈを超えるとき（ｔｉｎａｃｔｉｖｅ＞ｔｉｎａｃｔｉｖｅ＿ｔｈ）に群Ｇ１，Ｇ２，．．．，Ｇｋが解放される（もはや割り当てられない）。アクティブ群Ｇ１，Ｇ２，．．．，Ｇｋの各々が制限／割当ての均等な負担を保証されるように公平な負担が群Ｇ１，Ｇ２，．．．，Ｇｋの間に適用される。しかしながら、全ての群Ｇ１，Ｇ２，．．．，Ｇｋが全体的に保証された負担を終始用いるとは限らず、他の群が使用されていないトークン／部分トークンを得るために競争することがある場合、群Ｇ１，Ｇ２，．．．，Ｇｋは、この保証に制限されない。全体的なパイプ／処理制限Ｃｔｏｔの重み付けされた負担が群に与えられた場合に公平性の高い負担を得ることができるとしても、通常、使用されていないトークン／部分トークンの公平な負担が存在しない。
【０１３７】
したがって、本発明の本実施の形態の一つの基本的な原理は、所定の全体的なパイプ／処理制限Ｃｔｏｔの公平な負担をカウントすることである。これを群Ｇ１，Ｇ２，．．．，Ｇｋごとに行うことができるとともに対応する全体的なパイプ／処理制限Ｃｔｏｔのクリアランスとみなすことができる。群の負担に十分なトークンが存在する限り、パケットがパスされるとともに送出され、部分コストが全体的なパイプ／処理制限Ｃｔｏｔにデットされる。群の負担の総和が対応する全体的なパイプ／処理制限Ｃｔｏｔを超えることがないことに留意されたい。その理由は、これによって全体的なパイプ／処理制限Ｃｔｏｔにアンダーフローが生じることがないからである。全体的なパイプ／処理カウンタとは異なり、群の負担カウンタがグループごとの制限を超えたときにパケットをドロップ又は降格させない。代わりに、パケットを全体的なパイプ／処理カウンタにパスし、用いられるグループ分けが存在しない場合のように過度のグループごとの制限がそれ相応に取り扱われる。
【０１３８】
本発明の第２の態様によれば、図１に示すようなネットワークノード１００を提供する。ネットワークノードは、本発明の方法の実施の形態を実行するように配置された処理装置１２０を含む。
【０１３９】
一実施の形態によれば、処理装置１２０は、少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎのセットＳＰＵ；１５０の同期した利用を提供する順次パケット処理アルゴリズムＡｓｅｒ及び少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎのセットＳＰＵ；１５０の少なくとも部分的に同期しない利用を提供する並列パケット処理アルゴリズムＡｐａｒに少なくとも従ってネットワーク５００に送信されるパケットの処理を行うために配置される。
【０１４０】
処理装置１２０は、少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎのセットＳＰＵ；１５０によって協力的に負担されるようにパケットの処理に対応する総パケットコストＣｔｏｔを負担するように更に配置される。
【０１４１】
また、処理装置１２０は、並列パケット処理アルゴリズムＡｐａｒに従う処理がパケットを処理するために用いられるとき、少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎの一つ以上に対する総パケットコストＣｔｏｔの負担Ｃ１，Ｃ２，．．．，Ｃｎが少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎのパケットを処理する容量を超えているか否かを判定（２１０）し、容量は、一つ以上のパケットに対応し、
少なくとも一つの処理ユニットＰＵ１，ＰＵ２，．．．，ＰＵｎ；１５１，１５２，．．．，１５ｎの一つ以上に対する総パケットコストＣｔｏｔの負担Ｃ１，Ｃ２，．．．，Ｃｎが容量を超えていると判定された（２１０）場合、並列パケット処理アルゴリズムＡｐａｒに従う処理から順次パケット処理アルゴリズムＡｓｅｒに従う処理に切り替える（２２０）ために配置される。
【０１４２】
これを、上述した決定２１０を行うために配置された決定部１２１及び上述した切替１２２を行うために配置された切替部１２２を含むネットワークノード１００及び／又は処理装置１２０として説明することもできる。
【０１４３】
ネットワークノード１００及び処理装置１２０を、本発明のここで説明する実施の形態のいずれかを実現するために配置することができ、ネットワークノード１００及び処理装置１２０に、これらの実施の形態を実現する対応するユニットを設けてもよい。
【０１４４】
さらに、本発明の実施の形態によるあらゆる方法を、処理手段によって実行するときに処理手段に方法のステップを実行させるコード手段を有するコンピュータプログラムで実現してもよい。コンピュータプログラムは、コンピュータプログラム製品のコンピュータ可読媒体に含まれる。コンピュータ可読媒体は、ＲＯＭ（リードオンリーメモリ）、ＰＲＯＭ（プログラマブルＲＯＭ）、ＥＰＲＯＭ（消去可能ＰＲＯＭ）、フラッシュメモリ、ＥＥＰＲＯＭ（電気的ＥＰＲＯＭ）及びハードディスクドライブのような実質的にあらゆるメモリを備えてもよい。
【０１４５】
ここで説明する処理装置１２０は、一実施の形態において、例えば、中央処理装置（ＣＰＵ）、処理装置、処理回路、プロセッサ、特定用途向け集積回路（ＡＳＩＣ）、マイクロプロセッサ又は命令を解釈するとともに実行することができる他のプロセス論理の一つ以上の例を備えてもよい。語句「プロセッサ」は、上述したものの一部又は全てのような複数の処理回路を備える処理回路構成（ｃｉｒｃｕｉｔｒｙ）を表す。処理回路構成は、入力、出力及びデータバッファリングを備えるデータの処理のためのデータ処理機能並びに呼処理制御、ユーザインタフェース制御等のような装置制御機能を実行してもよい。
【０１４６】
最後に、本発明は、上述した実施の形態に限定されず、添付した独立項の範囲内の全ての実施の形態に関連するとともに当該実施の形態を包含する。
【図１】
2019510448.tif 000003
【図２ａ】
2019510448.tif 000004
【図２ｂ】
2019510448.tif 000005
【図２ｃ】
2019510448.tif 000006
【図２ｄ】
2019510448.tif 000007
【図２ｅ】
2019510448.tif 000008
【図２ｆ】
2019510448.tif 000009
【図３】
2019510448.tif 000010
【図４】
2019510448.tif 000011
【図５】
2019510448.tif 000012
【国際調査報告】
2019510448.tif 000013
2019510448.tif 000014
2019510448.tif 000015
2019510448.tif 000016
2019510448.tif 000017