(57)【要約】【課題】可変長パケットの通信トラフィックのポリーシング技法を提供すること。【解決手段】この技法は、２つ１組にまとめられた複数のポリスエンジンを使用する。選択モジュールは、パケットを処理する１対のポリスエンジンを選択する。各ポリスエンジンは、適合ユニット、クレジットユニット、およびデビットユニットを含み、１つのポリスエンジンのクレジットユニットは、その対の他方のポリスエンジンのクレジットの更新に影響を与える。また、この技法は、組合せ機能を使用して、処理されたパケットのカテゴリ、およびそのデビットユニットを更新するポリスエンジンを決定する。【選択図】　　　図３
2004135264.tif 000002
【特許請求の範囲】
【請求項１】
それぞれが、処理されたパケットの適合結果を生成する適合ユニット、クレジットユニット、およびデビットユニットを含む、パケットを処理する少なくとも１対のポリスエンジンモジュールと、
受信したパケットを、並列処理する１対の前記ポリスエンジンモジュールの一方または両方に対して送信する選択モジュールと、
前記ポリスエンジンモジュールの前記適合結果を受信して、前記受信したパケットのカテゴリおよびどのポリスエンジンモジュールが前記デビットユニットを更新するかを決定する組合せモジュールと、
他方の前記ポリスエンジンモジュールの前記クレジットユニットの状態に応答してクレジットの更新を実行する一方の前記ポリスエンジンモジュールの前記クレジットユニットと、を備える、一連のパケットから構成される通信トラフィックを監視するポリーシング装置。
【請求項２】
１対のポリスエンジンモジュールの一方が、他方のポリスエンジンモジュールとは異なるレートで前記受信したパケットを処理するように設定される請求項１に記載のポリーシング装置。
【請求項３】
それぞれが、ポリスエンジンモジュールの状態に基づいて処理されたパケットの適合結果を生成する適合ユニット、更新時に前記ポリスエンジンモジュールの状態を調整するクレジットユニット、および更新時に前記ポリスエンジンモジュールの状態を調整するデビットユニットを含む、パケットを処理する少なくとも１対のポリスエンジンモジュールと、
受信したパケットを、並列処理する１対の前記ポリスエンジンモジュールの一方または両方に対して送信する選択モジュールと、
前記ポリスエンジンモジュールの前記適合結果を受信して、前記受信したパケットのカテゴリおよびどのポリスエンジンモジュールが前記ユニットを更新するかを決定する組合せモジュールと、を備え、
各ポリスエンジンモジュールの前記適合ユニットが、前記ポリスエンジンモジュールの前記状態に基づいて、前記受信したパケットを独立して測定して適合結果を生成し、
前記組合せモジュールが、前記ポリスエンジンモジュールの前記適合結果のあらかじめ設定された組合せ関係に基づいて決定を行い、前記決定されたポリスエンジンモジュールの前記デビットユニットに、前記状態を調整し、前記受信したパケットを分類するよう指示し、
一方のポリスエンジンモジュールの前記クレジットユニットが、前記対の他方のポリスエンジンモジュールの前記クレジットユニットに応答して更新する
一連のパケットから構成される通信トラフィックを監視するポリーシング装置。
【請求項４】
１対のポリスエンジンモジュールの一方が、他方のポリスエンジンモジュールとは異なるレートで前記受信したパケットを処理するように設定される請求項３に記載のポリーシング装置。
【請求項５】
通信トラフィックが複数のトラフィックストリームから構成され、前記受信したパケットが複数のトラフィックストリームに属する、請求項４に記載のポリーシング装置であって、
各対がトラフィックストリームを監視する複数の対のポリスエンジンモジュールと、
受信したパケットを、トラフィックストリームを処理する複数の対のポリスエンジンモジュールに対して送信する前記選択モジュールと、
ポリスエンジンモジュールの前記適合結果を受信し、前記受信したパケットのカテゴリ、およびどのポリスエンジンモジュールが前記状態を調整するかを、前記適合結果の組合せ関係に基づいて決定する前記組合せモジュールと、を更に備える、装置。
【請求項６】
一連のパケットから構成される通信トラフィックを監視するポリーシング方法であって、
それぞれが、適合ユニット、クレジットユニット、およびデビットユニットを有する、処理するための少なくとも１対のポリスエンジンモジュールの一方または両方に対して、受信したパケットを送信するステップと、
前記対の他方のポリスエンジンモジュールの前記クレジットユニットによって指示されたときに、一方のポリスエンジンモジュールの前記クレジットユニットを更新するステップと、
各ポリスエンジンモジュールにおいて前記適合ユニットで受信したパケットを測定して適合結果を生成するステップと、
前記対のポリスエンジンモジュール内の前記適合結果の組合せ関係に基づいて組合せ決定を生成するステップと、
前記組合せ決定に基づいて前記受信したパケットのカテゴリを決定するステップと、
前記組合せ決定によって選択されたポリスエンジンモジュールの前記デビットユニットを更新するステップと、を含む方法。
【請求項７】
１対のポリスエンジンモジュールの一方が、他方のポリスエンジンモジュールとは異なるレートで前記受信したパケットを処理する請求項６に記載のポリーシング方法。
【請求項８】
１対中のポリスエンジンモジュールは他方と独立してそれぞれの前記クレジットユニットを更新する請求項７に記載のポリーシング方法。
【請求項９】
前記通信トラフィックが複数のトラフィックストリームからなり、前記受信したパケットが複数のトラフィックストリームに属する請求項６に記載のポリーシング方法であって、各対が各トラフィックストリームを異なるレートで監視する複数の対のポリスエンジンモジュールに対して、受信したパケットを送信するステップを更に含む、方法。
【請求項１０】
複数対のポリスエンジンモジュールの前記適合結果の組合せ関係に基づいて組合せ決定を生成するステップと、
前記組合せ決定に基づいて前記受信したパケットのカテゴリを決定するステップと、を更に含む請求項９に記載のポリーシング方法。
【請求項１１】
１対中のポリスエンジンモジュールは他方と独立してそれぞれの前記クレジットユニットを更新する請求項９に記載のポリーシング方法。
【請求項１２】
各対中のポリスエンジンモジュールは他方と独立してそれぞれの前記クレジットユニットを更新する請求項１０に記載のポリーシング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信におけるトラフィック制御に関し、より詳細には、様々な長さのパケットの通信トラフィックのポリーシング技法に関する。この技法は、２つ１組にまとめられた複数のポリーシングエンジンを使用し、ポリーシングエンジンの更新アルゴリズムが共依存するポリーシングアルゴリズムに適用可能である。
【背景技術】
【０００２】
通信ネットワークは、様々なトラフィック制御機構を含む。ポリーシング機構とは、トラフィックストリーム、および／またはサブストリームを監視して、設定されたパラメータに適合しているかどうかを調べ、かつ／または適合していない場合は必要な何らかのアクションを起こす機構である。こうしたアクションには、プロファイル外れの（適合していない）パケットのドロップまたは廃棄、およびパケットの優先度または色でのマーキングまたはタグ付けなどを含まれる。
【０００３】
既知のポリーシング機構は、仮想スケジューリングアルゴリズム（略語はＶＳＡ）として知られるスケジューリングアルゴリズムを使用する。ＶＳＡは、２つの部分に分割されると考えることができる。２つの部分とは、ストリーム内のパケットをＶＳＡインスタンスに従って廃棄すべきかどうかを示す適合チェック部分、および例えば予想到着時刻などＶＳＡが使用する基本的パラメータが非廃棄パケットの到着時刻に応じて更新される更新部分である。
【０００４】
通信ネットワーク上のトラフィックストリームは、固定長または可変長の一連のパケット（またはセルの場合もある）で構成される。ネットワークを流れるトラフィックストリームが数多く存在し、２つ以上のトラフィックストリームを階層構造で配列することができる。したがってパケットは、１以上のトラフィックストリームに属することができる。各トラフィックストリームは、１つまたは２つのサブストリーム（例えば優先度の高いパケットのサブストリーム、および優先度の高いパケットおよび優先度の低いパケットの両方を含む集合サブストリーム（ａｇｇｒｅｇａｔｅ　ｓｕｂｓｔｒｅａｍ））を備えることができる。したがってこの例では、優先度の高いパケットは、両方のサブストリームに属する。各サブストリームは、単一のレート制御を有し、レートパラメータ（レート、バースト許容値など）、およびポリーシング状態（例えば予想到着時刻）を含む。パケットが属する各ストリームに１つのポリーシングエンジンが必要である。
【０００５】
例えば、ＡＴＭセルストリームは、ＣＬＰビットによって示される優先度の高いセルおよび優先度の低いセルを含む。こうしたＡＴＭセルストリームに関して、ＩＴＵ−ＴＳ勧告Ｉ．３７１では、優先度の高い第１のセルのサブストリームは別々に監視すべきであり、一方、第１および第２のセルの集合ＡＴＭストリーム（または用語の使用を統一するために「集合サブストリーム」と言うべき）もまた全体として監視すべきであると規定している。これを達成するための１つの方法は、２つのシリーズ接続されたプロセッサのそれぞれが特定のサブストリームに特定のポリスアルゴリズムインスタンスを適用する処理手段を使用することである。したがって第１のプロセッサは、ＶＳＡのインスタンスに従って、優先度の高い第１のセルから構成される１つのサブストリームに作用し、一方、第２のプロセッサは、同様のＶＳＡインスタンスに従って、監視されていない優先度の低い第２のセルおよび監視されている優先度の高い第１のセルの両方を含む他方のサブストリームに作用する。
【０００６】
１９９６年７月３０日付のＷｉｔｔｅｒｓらによる米国特許第５，５４１，９１３号明細書には、上記の既知のタイプであり、しかしより一般的な構造をもち、広範にわたる別個のポリーシング方法に容易に適応できるポリーシング装置が記載されている。よって、この構造は、ポリスエンジンの複数のインスタンス化が並列に配列されており、ＡＴＭストリームのための多くのポリーシング方法だけではなく、ＩＴＵ勧告が後に変更された結果として実現され得るものに対しても容易に適応できると記載されている。
【０００７】
図１は、上記の特許のポリーシング装置を示す略図である。
【０００８】
任意のアルゴリズムに適応可能であるものとして記載されているが、このポリーシング装置は、複数の並列ポリスプロセッサ１０、１２を含んでおり、そのそれぞれがＭｏｄｉｆｉｅｄ　Ｖｉｒｔｕａｌ　Ｓｃｈｅｄｕｌｉｎｇ　Ａｌｇｏｒｉｔｈｍ（略語はＭＶＳＡ）を実装している。これは一般に更新および適合の２段階の処理に分けることができる。更新段階は、アルゴリズムの状態（セルの予想到着時刻など）を維持する。適合段階は、評価中のセルがアルゴリズムに適合するかどうかを計算する。言い換えれば、セルの実際の到着時刻が予想到着時刻より遅い、つまりセルは予想到着時刻より早く到着しなかったかどうかを計算する。また、ポリーシング装置は、ＡＴＭ入力ストリームの受信したセルごとに１つまたは両方のプロセッサを作動させる有効化回路（ｅｎａｂｌｉｎｇ　ｃｉｒｃｕｉｔ）１４を有し、次いでプロセッサが適合信号を生成する。この適合信号から、調停モジュール１６が廃棄信号１８およびフィードバック信号２０、２２を生成する。廃棄信号は、こうしたセルが廃棄回路によってＡＴＭ出力ストリームに挿入できるかどうかを示し、フィードバック信号は、上記のアルゴリズムで使用されている予測到着時刻のすでに準備されている更新を実行するかどうかを対応するプロセッサに示す。調停モジュールおよび有効化回路を使用することによって、この構造で多くのポリーシング方法の実装が可能となる。
【０００９】
上記の特許では、ＭＶＳＡを以下のコードを備えるものとして記載している。
【数式１】
2004135264.tif 000003
式中、
ＰＡＴは予想到着時刻、
ＴＩＭＥは処理されたセルの到着時刻、
ＴＥＭＰ＿ＰＡＴはＰＡＴの準備された更新値、
γはいわゆるセル遅延変動許容値、
ＮＩＡＴは交渉されたセルの到着時刻間隔（ｉｎｔｅｒ−ａｒｒｉｖａｌ　ｔｉｍｅ）、
ＣＳは処理されたセルがＭＶＳＡの適用されたインスタンスに適合しているかどうかを示す適合値である。ＣＳ＝１は適合、ＣＳ＝０は非適合である。
【００１０】
上記のＭＶＳＡは、いくつかの変更を除いて、上述した仮想スケジューリングアルゴリズムに似ている。変更の１つは、予想到着時刻が直接更新されるのではなく、それに備えて更新が中間変数ＴＥＭＰ＿ＰＡＴで準備されるだけであるということである。次いでこの更新が有効に適用されるかどうかは、以下のようにフィードバック値ＦＳによって決まる。
【数式２】
2004135264.tif 000004
【００１１】
別の変更は、ＭＶＳＡのインスタンスが、処理されたセルは十分ではないことを見つけたときでさえ更新値の準備を可能にする新しい行の導入にある。この変更は、特定のポリーシング方法を適用する際にのみ必要となるが、ポリーシング装置ＰＤを一般的な状態に保つ、すなわちそれぞれの、および任意のポリーシング方法をそれによって適用できるようにするために、すべての場合に導入される。また、ポリーシング装置で同じポリスプロセッサを使用できるようにするために、各ポリスプロセッサによっても実装される。
【００１２】
上記のＭＶＳＡは、適合信号を導出する適用チェック部分、および更新値ＴＥＭＰ＿ＰＡＴを準備し、フィードバック信号によって指示されたときに更新を実行する更新部分に分割される。したがって、ＭＶＳＡのインスタンスを実行する際に、プロセッサは、更新値ＴＥＭＰ＿ＰＡＴを準備し、その結果としてもたらされる適合値を適合信号として生成する。一方、調停モジュールは、上記のＭＶＳＡのインスタンスを実行するときにプロセッサがフィードバック信号として使用するフィードバック値を生成する。
【００１３】
有効化回路ＥＣおよび調停モジュールＡＭの動作を定義することによって、別個のポリーシング方法をいくつか実現することができる。例えば、優先度の高い第１のセルには両方のプロセッサＰＰ１およびＰＰ２を、優先度の低い第２のセルには第２のプロセッサＰＰ２のみを作動させるように有効化回路ＥＣを指定することによって、ＩＴＵ−ＴＳ勧告Ｉ．３７１を満たすポリーシング方法を実現することができる。上述したように、この勧告では、優先度の高いセルおよび優先度の低いセルの両方を含むＡＴＭストリーム（集合ストリーム）を全体として監視するべきであり、優先度の高いセルによって形成されているサブストリームもまた個別に監視すべきであると述べている。
【００１４】
その特許では、そこに記載されている構造によって実現できる他のいくつかのポリーシング方法について説明している。記載されているポリーシング方法は、セルの到着時刻を使用する代わりに、リーキーバケット（ｌｅａｋｙ　ｂｕｃｋｅｔ）とその充足状態（ｆｉｌｌ　ｓｔａｔｅ）を使用してパケットが適合するかどうかを計算する。その特許では一般的と記載しているが、この構造は、１つのプロセッサの更新アルゴリズムが第２のプロセッサの更新アルゴリズムと関係があるようなアルゴリズムを実現するようには構成され得ない。上記の特許に記載されているいくつかのケースでは、ＰＰ１およびＰＰ２は互いに独立して更新する。また、この特許では、ＡＴＭセルストリームとの関連のみで構造を説明している。実現できないこうしたアルゴリズムの１つについてこの次に説明する。詳しく説明するように、そのアルゴリズムは２つのリーキーバケットを使用し、それらの更新は互いに依存している。
【００１５】
ＩＥＴＦ　ＲＦＣ２６９７では、単一レート３色マーカ（ｓｉｎｇｌｅ　ｒａｔｅ　ｔｈｒｅｅ　ｃｏｌｏｕｒ　ｍａｒｋｅｒ）と呼ばれる単一レートの３色デュアルリーキーバケットポリーシングアルゴリズムについて記載している。このポリーシングアルゴリズムは、ＭＰＬＳ、フレームリレー、インターネットなどを介した音声／ビデオを含むＩＰトラフィックなどの可変長パケットストリームを調整するためのものである。このアルゴリズムは、２つのリーキーバケットを必要とし、２つのリーキーバケットのクレジット更新アルゴリズム（ｃｒｅｄｉｔ　ｕｐｄａｔｅ　ａｌｇｏｒｉｔｈｍ）は共依存関係にある。ＲＦＣ２６９７では、このマーカを差別化サービストラフィックコンディショナ（ｄｉｆｆｅｒｅｎｔｉａｔｅｄ　ｓｅｒｖｉｃｅｓ　ｔｒａｆｆｉｃ　ｃｏｎｄｉｔｉｏｎｅｒ）の構成要素として使用することができると述べている。このアルゴリズムは、トラフィックストリーム（ＩＰパケットストリームなど）を測定し、そのパケットを緑色、黄色、赤色のいずれかにマークする。マーキングは、認定情報レート（ＣＩＲ）、２つの関連するバーストサイズ、認定バーストサイズ（ＣＢＳ）および超過バーストサイズ（ＥＢＳ）の３つのトラフィックパラメータに基づいている。ＣＩＲは、毎秒のＩＰパケットのバイト単位で測定され、リンク固有のヘッダではなくＩＰヘッダを含む。ＣＢＳおよびＥＢＳはバイト単位で測定される。パケットは、ＣＢＳを超過していない場合は緑色に、ＣＢＳは超過しているがＥＢＳは超過していない場合は黄色に、それ以外の場合は赤色にマークされる。このアルゴリズムは、例えばバーストの最高レートではなく長さのみがサービスの適格性を決定するサービスの入口ポリーシング（ｉｎｇｒｅｓｓ　ｐｏｌｉｃｉｎｇ　ｏｆ　ａ　ｓｅｒｖｉｃｅ）に有用である。カラーブラインド（ｃｏｌｏｕｒ−ｂｌｉｎｄ）モードおよびカラー認識（ｃｏｌｏｕｒ−ａｗａｒｅ）モードの２つの動作モードがある。
【００１６】
図２は、すべてのパケットが緑色に色付けされているものとして扱われるカラーブラインド動作モードのアルゴリズムを示すブロック略図である。図２からわかるように、選択回路４０は、受信したパケットのサイズ、フロー、時刻、および色（カラー認識モードの場合）をメータ４２に渡す。メータ４２は、各パケットを測定し、測定結果を送信回路４４に渡す。送信回路４４は、パス（受け付ける）／マーク（緑色、黄色、赤色）／ドロップのアクションを測定結果によって示されているように実行する。このメータは、それぞれ４６および４８で示す２つのリーキーバケットＣおよびＥからなる。両方のバケットはＣＩＲを共有する。リーキーバケットからの適合（測定）結果５０がパケットの色を決定する。適合結果およびそのバケットの充足状態が、更新機能５４または５６のどちらを実行すべきであるかを決定する決定ブロック５２で処理される。
【００１７】
アルゴリズムは以下のように動作する。
【００１８】
バケットＣの最大サイズはＣＢＳであり、バケットＥの最大サイズはＥＢＳである。ＴｃおよびＴｅはバケットＣおよびＥのバケット充足状態である。時刻０の時点で２つのバケットは充足されており、すなわちＴｃ（０）＝ＣＢＳおよびＴｅ（０）＝ＥＢＳである。ＴｃおよびＴｅの２つのバケットの充足状態は、時刻０から以下のように毎秒ＣＩＲ回更新される。
・ＴｃがＣＢＳ未満の場合、Ｔｃは１ずつ増分される、または
・ＴｅがＥＢＳ未満の場合、Ｔｅは１ずつ増分される、または
・ＴｃもＴｅも増分されない。
【００１９】
サイズＢバイトのパケットが時刻ｔに到着したとき、カラーブラインドモードの動作では以下のことが起こる。
・Ｔｃ（ｔ）−Ｂ＞＝０の場合、パケットは緑色で、Ｔｃは最小値０までＢずつ減分される、または
・Ｔｅ（ｔ）−Ｂ＞＝０の場合、パケットは黄色で、Ｔｅは最小値０までＢずつ減分される、または
・パケットは赤色で、ＴｃもＴｅも減分されない。
【００２０】
サイズＢバイトのパケットが時刻ｔに到着したとき、カラー認識モードの動作では以下のことが起こる。
・パケットがあらかじめ緑色に色付けされており、Ｔｃ（ｔ）−Ｂ＞＝０の場合、パケットは緑色で、Ｔｃは最小値０までＢずつ減分される、または
・パケットがあらかじめ緑色または黄色に色付けされており、Ｔｅ（ｔ）−Ｂ＞＝０の場合、パケットは黄色で、Ｔｅは最小値０までＢずつ減分される、または
・パケットは赤色で、ＴｃもＴｅも減分されない。
【００２１】
【文献１】
ＩＴＵ−ＴＳ勧告Ｉ．３７１
【文献１】
米国特許第５，５４１，９１３号明細書
【文献２】
ＩＥＴＦ　ＲＦＣ２６９７
【考案の開示】
【発明が解決しようとする課題】
【００２２】
上記記載からわかるように、この例では、各パケットストリームが２つのリーキーバケットによって制御され、その更新（増減）は２つのリーキーバケットの状態に依存している。特に、バケットＥを更新するかどうかは、バケットＣおよびバケットＥ自体の状態に依存する。上記の特許に記載されている一般的な構造は、パケットストリームごとに複数のポリーシングエンジンを必要とし、１つのポリスエンジンの更新アルゴリズムが隣のポリスエンジンなどの更新アルゴリズムと関係を有するといったタイプのアルゴリズムを実現するよう構成することはできない。
【課題を解決するための手段】
【００２３】
１つの態様によれば、本発明は、少なくとも１対のポリスエンジンモジュールから構成される、一連の通信パケットを監視するポリーシング装置に関する。各ポリスエンジンモジュールは、適合ユニット、クレジットユニット（ｃｒｅｄｉｔ　ｕｎｉｔ）、デビットユニット（ｄｅｂｉｔ　ｕｎｉｔ）を含む。組合せモジュールは、適合結果に基づいて、受信した各パケットに適用されるアクション、およびその状態を更新するポリスエンジンモジュールを決定し、一方のポリスエンジンモジュールの更新結果がその対の他方の更新結果に依存する。
【００２４】
本発明の別の態様では、各ポリスエンジンの更新機能は、クレジットの更新およびデビットの更新からなる。一方のポリスエンジンのクレジットの更新は、その対の他方のポリスエンジンのクレジットの更新と関係がある。この機能は、互いに独立している場合もある。各ポリスエンジンのデビットの更新は、組合せモジュールの決定に基づく。
【００２５】
別の態様によれば、本発明は、一連のパケットから構成される通信トラフィックを監視するポリーシング装置を対象とする。装置は、パケットを処理する少なくとも１対のポリスエンジンモジュールを含み、各ポリスエンジンモジュールは、処理されたパケットの適合結果を生成する適合ユニット、クレジットユニット、およびデビットユニットを含む。装置はさらに、受信したパケットを並列処理する１対のポリスエンジンモジュールの一方または両方に対して送信する選択モジュール、ポリスエンジンモジュールの適合結果を受信して、受信したパケットのカテゴリおよびどのポリスエンジンモジュールがデビットユニットを更新するかを決定する組合せモジュール、および他方のポリスエンジンモジュールのクレジットユニットの状態に応答してクレジットの更新を行う一方のポリスエンジンモジュールのクレジットユニットを含む。
【００２６】
更に別の態様によれば、本発明は、一連の通信パケットの監視方法を対象とする。この方法は、適合のために少なくとも１対のポリスエンジンモジュールで受信したパケットを処理する。この方法は、モジュールの適合結果の組合せ関係に基づいて受信したパケットに関するアクションを決定する。組合せ関係は、その状態を更新するモジュールを決定する。さらに、一方のモジュールの更新は、その対の他方のモジュールの更新にも依存する。
【００２７】
なお更に別の態様によれば、本発明は、一連のパケットから構成される通信トラフィックを監視するポリーシング方法に関する。この方法は、それぞれが適合ユニット、クレジットユニット、デビットユニットを有する、処理するための少なくとも１対のポリスエンジンモジュールへ受信したパケットを送信するステップと、その対の一方のポリスエンジンモジュールのクレジットユニットによって指示されたときに他方のポリスエンジンモジュールのクレジットユニットを更新するステップと、適合結果を生成するために、各ポリスエンジンモジュールにおいて適合ユニットで受信したパケットを測定するステップを含む。この方法は、１対のポリスエンジンモジュール内の適合結果の組合せ結果に基づいて組合せ決定を生成するステップと、組合せ決定に基づいて受信したパケットのカテゴリを決定するステップと、組合せ決定に基づいて選択したポリスエンジンモジュールのデビットユニットを更新するステップとを更に含む。
【発明を実施するための最良の形態】
【００２８】
図３は、概略ブロック図に本発明の一実施形態による新規な構造を示している。同図からわかるように、ポリスエンジンは２つ１組で所望の数のグループにまとめられている。ポリスエンジンの数は、単一のパケットへの適用が必要とされているレート制御の数によって決定される。上述したように、トラフィックストリームは、１つまたは２つのサブストリームで構成し、そのストリームのパケットは両方のサブストリームに属することができる。したがって、各サブストリームが１つのレート制御を必要とする場合、異なるレートで同じパケットを監視する２つのポリスエンジンが必要であり、これらが２つ１組で構成されている。この実施形態では、１対の各ポリスエンジンは、リーキーバケットアルゴリズムなどのポリスエンジンアルゴリズムを備える。ポリスエンジンアルゴリズムは３つのユニット、すなわちクレジットユニット、適合ユニット、デビットユニットに分けられ、クレジットユニットおよびデビットユニットは、背景技術に関連して上述した更新段階の機能を実行する。選択機能は、トラフィックストリームの可変長パケットに１つまたは複数の所望のポリスエンジンを選択し、そこでポリーシング機能を実行する。一方、組合せ機能は、実行するアクション、およびポリスエンジンアルゴリズムのいずれかに対して更新アルゴリズムを実行するかどうかを決定する。
【００２９】
図３を参照すると、可変長のパケットがポリーシング装置８２のパケット受信回路８０に到着し、トラフィックストリームに分類される。フローＩＤ、サイズ、到着時刻、および色（すなわちドロップ順に赤色、黄色、緑色）が選択機能８４に渡される。トラフィックストリームに関連するメモリによって、選択機能は、ポリスエンジンをサブストリームに割り当てることができるようになり、８６でパケットが割り当てられたポリスエンジンに対して送信される。パケットは、複数のポリスエンジンに割り当てることができるが、同じトラフィックストリームのサブストリームは、同じポリスエンジンの対に割り当てられる。というのは、その更新が互いに依存しているためである。また、選択機能は、フローのカラー認識構成の９０でパケットカラーに応じて組合せ機能８８に色を直接出力する。カラーブラインドモードでは、すべてのパケットが緑色と見なされ、したがって色の出力は不要である。
【００３０】
パケットサイズおよび到着時刻が選択された各ポリスエンジンに渡される。選択された各ポリスエンジンは、クレジットの更新およびデビットの更新を実行する。また、適合チェック９２を実行して、パケットがポリスエンジンで設定されたパラメータに適合するかどうかを判断する。適合チェック結果は、ポリスエンジンごとに計算され、組合せ機能８８に出力される。組合せ機能８８は、パケット送信回路９４に、パケットを受け付ける（パス、緑色）、廃棄する（ドロップ）、またはそれを赤色または黄色でマークする（マーク）よう指示するアクションを出力する。
【００３１】
上述したように、各ポリスエンジンは、クレジット更新機能９６およびデビット更新機能９８から構成される更新を実行する。１対中の２つのポリスエンジンのクレジット更新アルゴリズムは、矢印１００で示すように共依存している。言い換えれば、一方のエンジンのクレジットの更新は、その対の他方のクレジットの更新に関係している。ここで、場合によっては、この関係は互いに他から独立するものであってよい。各ポリスエンジンのデビット更新アルゴリズムは、組合せ機能に関係し、その対の他方のポリスエンジン以外に、ポリーシング装置８２の他のポリスエンジンによって影響を受ける可能性がある。例えば、トラフィックストリームに関連するメモリによって、ポリーシング装置８２は、各ポリスエンジンの適合結果がどのぐらいその装置の他方のポリスエンジンのデビットの更新に影響を与えるかを決定することができる。したがって、適合チェック結果に加えて、組合せ機能は、デビット更新機能（アルゴリズム）が実行されるかどうかを指示する独立信号を選択された各ポリスエンジンへ出力する。各ポリスエンジンは、組合せ機能の信号が正の場合、デビット更新機能を実行する。
【００３２】
本発明の一実施形態によれば、図３に示した構造は、定期的な更新の代わりに、パケットが到着するとクレジットの更新が実行され、一方のポリスエンジンのクレジットの更新がその対の他方の更新に依存するという点で、ＲＦＣ２６９７に記載されているアルゴリズムを実行するように構成されている。トラフィックストリームに関連するメモリによって、ポリスエンジンの対は、その対の一方のポリスエンジンのクレジットの更新がその対の他方のポリスエンジンのクレジットの更新にどのぐらい影響を与えるかを決定できるようになる。図３の符号１００は、こうした依存関係を示している。本明細書で上述したように、アルゴリズムは、２つのリーキーバケットＣおよびＥを使用する。パケットが到達すると、バケットＣおよびＥの充足状態ＴｃおよびＴｅが以下のようにクレジットで更新される。
・ＴｃがＣＢＳ未満の場合、Ｔｃは１ずつ増分される、または
・ＴｅがＥＢＳ未満の場合、Ｔｅは１ずつ増分される、または
・ＴｃもＴｅも増分されない。
【００３３】
上述したように、２つのリーキーバケットのクレジット更新アルゴリズムは共依存する。ＲＦＣ２６９７で定期的と記載されているが、このアルゴリズムのバケットは、実際にはパケットが到着すると更新される。
【００３４】
引き続きこの実施形態を説明すると、各バケットＣおよびＥの適合結果ＦｃおよびＦｅは、組合せ機能に渡される。また、入力パケットの色も組合せ機能に直接渡される。組合せ機能は、適合結果および入力パケットの色をマップして、各バケットＣおよびＥを更新するかどうか、および出力パケットの各色、つまり緑色、黄色、赤色を決定する。
【００３５】
以下の表は、カラーブラインドの構成およびカラー認識構成の場合の決定および出力カラーの可能な各組合せを示している。表では、０は非適合、１は適合を示す。デビット更新機能は、バケットＣおよびＥのそれぞれについてＵｃおよびＵｅで示している。
【００３６】
カラーブラインド動作モードの場合、入力パケットカラーは緑色である。２つのバイナリ入力変数しかないので、組合せは全部で４つである。以下の表は、バケットＣおよびバケットＥの更新の決定を示している。
【表１】
2004135264.tif 000005
【００３７】
カラー認識動作モードでは、元の色ごとに以下に示す４つの組合せがある。
【表２】
2004135264.tif 000006
【００３８】
したがってここまで説明してきた実施形態は、２つのレート制御が実行されるため、２つのリーキーバケットを使用するＲＦＣ２６９７で定義されているアルゴリズムを扱う。また、各制御の更新が他のいずれかに依存している２つを超えるレート制御が実行される場合があることも想像される。こうした環境では、２つを超えるポリスエンジンが１つのグループにまとめられ、こうした関係を考慮に入れるように組合せ機能を設計することができる。
【００３９】
他の実施形態では、複数のトラフィックストリーム、および２つ以上のポリスエンジンの対を必要とし、各対の一方のポリスエンジンのクレジットの更新が他方のクレジットの更新に影響を与える場合がある。また、複数のトラフィックストリームの状態を維持することによって単一のポリスエンジンが複数のトラフィックストリームにサービスを提供することが可能となる。こうした場合、２つ以上のトラフィックストリームが同じレートで制御される。
【００４０】
上記のＲＦＣで記載されているそれらのアルゴリズムに加えて、このポリーシング構造を、他のタイプのポリスアルゴリズムをサポートするよう構成することができる。
【図面の簡単な説明】
【００４１】
【図１】上記米国特許明細書に記載されているポリーシング装置を示す略図である。
【図２】ＩＥＴＦ　ＲＦＣ２６９７によるポリーシング装置を示す略図である。
【図３】本発明の一実施形態によるポリーシング装置を示す略図である。
【符号の説明】
【００４２】
１０、１２　並列ポリスプロセッサ
１４　有効化回路
１６　調停モジュール
１８　廃棄信号
２０、２２　フィードバック信号
４０　選択回路
４２　メータ
４４　送信回路
４６、４８　リーキーバケット
５０　適合結果
５２　決定ボックス
５４、５６　更新機能
８０　パケット受信回路
８２　ポリーシング装置
８４　選択機能
８８　組合せ機能
９２　適合チェック
９４　送信回路
９６　クレジット更新機能
９８　デビット更新機能
【図１】
2004135264.tif 000007
【図２】
2004135264.tif 000008
【図３】
2004135264.tif 000009
【外国語明細書】
2004135264.tif 000010
2004135264.tif 000011
2004135264.tif 000012
2004135264.tif 000013
2004135264.tif 000014
2004135264.tif 000015
2004135264.tif 000016
2004135264.tif 000017
2004135264.tif 000018
2004135264.tif 000019
2004135264.tif 000020
2004135264.tif 000021
2004135264.tif 000022
2004135264.tif 000023
2004135264.tif 000024
2004135264.tif 000025
2004135264.tif 000026
2004135264.tif 000027
2004135264.tif 000028