(57)【要約】パケットの推定到着時間［ＴＡＴ］と実際のパケットが到着した時間［ｔ（ｋ）］との時間差を判定する前に、中間変数［Ｋ］を設け［Ｋ＝ＴＡＴ−ｔ（ｋ）］なる演算を施した後、パケット到来許容時間［Ｌ］と、標準パケット間隔［Ｄ］との和［Ｌ＋Ｄ］で求められるカウンタオーバーフロー判定時間［Ｍ］とを比較する手段を追加したアルゴリズムを用いてポリシング判定を行う。
2003053012.tif 000002
【特許請求の範囲】
【請求項１】
異なるトラフィック量でネットワーク上を伝送するパケットの通過を制限するポリシング制御方法において、
前記パケットが到着すると、当該パケットの到着時刻を検出する到着時刻検出工程と、
パケット推定到着時刻およびパケット到来許容時間を予め設定する設定工程と、
前記検出されたパケット到着時刻と前記設定されたパケット推定到着時刻との時間差を演算する演算工程と、
前記演算された時間差と、前記設定されたパケット到来許容時間に標準パケット間隔時間を加えた加算値とを比較して、該時間差と加算値との大きさを判定する第１の判定工程と、
前記第１の判定工程で前記時間差が前記加算値以下と判定されたときは、時前記時間差とパケット到来許容間とを比較して、該時間差とパケット到来許容時間との大きさを判定する第２の判定工程と、
前記第２の判定工程で前記パケット到来許容時間より前記時間差が大きいと判定されたときは、前記パケットを廃棄する廃棄工程と、
前記第１の判定工程で前記加算値より前記時間差が大きいと判定されたとき、または前記第２の判定工程で前記時間差が前記パケット到来許容時間以下と判断されたときは、前記パケットの通過を許可する許可工程とを含むことを特徴とするポリシング制御方法。
【請求項２】
前記ポリシング制御方法では、前記許可工程でパケットの通過が許可されたときは、前記パケット推定到着時刻と前記標準パケット間隔時間との和を新たなパケット推定到着時刻として再設定する再設定工程を、さらに含むことを特徴とする請求の範囲第１項に記載のポリシング制御方法。
【請求項３】
前記ポリシング制御方法では、前記許可工程でパケットの通過が許可されたときは、前記パケット推定到着時刻と、標準ビット間隔と前記到着したパケットのパケット長の積からなる時間を加えた値を新たなパケット推定到着時刻と再設定する再設定工程を、さらに含むことを特徴とする請求の範囲第１項に記載のポリシング制御方法。
【請求項４】
異なるトラフィック量でネットワーク上を伝送するパケットの通過を制限するポリシング制御装置において、
前記パケットの到着時刻を検出する検出手段と、
前記パケット到着時刻と予め設定されたパケット推定到着時刻との時間差を演算する演算手段と、
前記演算された時間差と、予め設定されたパケット到来許容時間に標準パケット間隔時間を加えた加算値とを比較する第１の比較手段と、
前記第１の比較手段での比較結果に基づいて、前記時間差とパケット到来許容時間とを比較する第２の比較手段と、
前記第１の比較手段での比較結果、または前記第１および第２の比較手段での比較結果に基づいて、該パケットの通過または廃棄を許可する許可手段とを備えたことを特徴とするポリシング制御装置。
【請求項５】
前記ポリシング制御装置は、前記許可手段が前記パケットの通過を許可したときに、前記パケット推定到着時刻と標準パケット間隔時間との和を新たなパケット推定到着時刻として設定する設定手段を、さらに備えたことを特徴とする請求の範囲第４項に記載のポリシング制御装置。
【請求項６】
前記ポリシング制御装置は、前記許可手段が前記パケットの通過を許可したときに、前記パケット推定到着時刻と、標準ビット間隔と前記到着したパケットのパケット長の積からなる時間を加えた値を新たなパケット推定到着時刻として設定する設定手段を、さらに備えたことを特徴とする請求の範囲第４項に記載のポリシング制御装置。
【請求項７】
前記許可手段は、前記第１の比較手段での比較結果で前記加算値より前記時間差が大きいとき、または前記第１の比較手段での比較結果で前記時間差が前記加算値以下、かつ前記第２の比較手段での比較結果で前記時間差が前記パケット到来許容時間以下のときには、前記パケットの通過を許可することを特徴とする請求の範囲第４項〜第６項のいずれか一つに記載のポリシング制御装置。
【請求項８】
前記許可手段は、前記第１の比較手段での比較結果で前記時間差が前記加算値以下、かつ前記第２の比較手段での比較結果で前記パケット到来許容時間より前記時間差が大きいときには、前記パケットを廃棄することを特徴とする請求の範囲第４項〜第６項のいずれか一つに記載のポリシング制御装置。
【請求項９】
前記許可手段は、前記第１の比較手段での比較結果で前記加算値より前記時間差が大きいとき、または前記第１の比較手段での比較結果で前記時間差が前記加算値以下、かつ前記第２の比較手段での比較結果で前記時間差が前記パケット到来許容時間以下のときには、前記パケットの通過を許可し、また前記第１の比較手段での比較結果で前記時間差が前記加算値以下、かつ前記第２の比較手段での比較結果で前記パケット到来許容時間より前記時間差が大きいときには、前記パケットを廃棄することを特徴とする請求の範囲第４項〜第６項のいずれか一つに記載のポリシング制御装置。
【請求項１０】
前記演算手段は、前記伝送されるパケットのパケット間隔を管理するためにカウンタを有し、該カウンタの最大計測時間は、リーキーバケットアルゴリズムのバケットカウンタの最大値と最小パケット間隔との和より十分大きい時間に設定されることを特徴とする請求の範囲第４項〜第６項のいずれか一つに記載のポリシング制御装置。
【請求項１１】
少なくとも複数の加入者ホストと、バックボーンネットワークとから構築され、該加入者ホストとバックボーンネットワーク間で、パケットの送受信を行うネットワークシステムにおいて、
前記加入者ホストとバックボーンネットワーク間に接続され、異なるトラフィック量の前記パケットの通過を制限する請求の範囲第４項〜第１０項のいずれか一つに記載のポリシング制御装置を備えたことを特徴とするネットワークシステム。
【発明の詳細な説明】
技術分野
この発明は、ネットワークシステムにおいて、ネットワーク上を流れるパケットのトラフィック量を監視してフロー制御を行うポリシング制御方法、その制御装置およびその制御装置を用いたネットワークシステムに関する。
背景技術
従来、この種のネットワークシステムでは、例えばパケットが加入者系のＡＴＭ（Ａｓｙｎｃｈｒｏｎｏｕｓ  Ｔｒａｎｓｆｅｒ  Ｍｏｄｅ：非同期転送モード）網などのネットワーク上をバースト的に流れるもの、すなわち短い時間に大きな伝送帯域を必要として流れるものがある。このようなネットワークシステムにおいては、ユーザ（例えば加入者パーソナルコンピュータなどが該当し、これを以下、「加入者ＰＣ」という）に自由なトラフィック量でセルの送出を許容させると、情報発生の頻度のばらつき等によって、特定の加入者ＰＣが大容量のトラフィック量でセルの送出を行ってしまう。このため、このネットワークシステムでは、他の加入者ＰＣが送出できるセルのトラフィック量が小容量になってしまったり、あるいは他の加入者ＰＣによるセルの送出ができなくなる状況が発生して、パケット伝送でのユーザ間の公平性が確保できなくなるという問題がある。
また、このネットワークシステムでは、パケット伝送の規約に違反したパケット（ＡＴＭセル）がネットワークに流入すると、通信回線におけるトラフィックに悪影響を及ぼし、他のユーザの伝送品質を劣化させる虞がある。
このため、従来では、ネットワークシステムを構築するネットワークの通信事業者とユーザとの間で、予め契約によって単位時間あたりに送出できるパケット量の上限を取り決めておく。そして、このネットワークに設けられているエッジルータなどの中継装置によって、加入者ＰＣがこの契約の範囲内のトラフィック量でパケットを送出しているかどうかをチェックするポリシング制御が行われている。
例えば、ＡＴＭ網におけるポリシング制御の基本概念は、ＵＰＣ（Ｕｓａｇｅ  Ｐａｒａｍｅｔｅｒ  Ｃｏｎｔｒｏｌ：使用量パラメータ制御）であり、この使用量パラメータを満足していないパケットを廃棄することにより、このポリシング制御を実現している。このポリシング制御によるパケットの通過、廃棄の判定条件は、ＰＣＲ（Ｐｅａｋ  Ｃｅｌｌ  Ｒａｔｅ：ピークセルレート）監視アルゴリズムとＣＤＴＶ（Ｃｅｌｌ  Ｄｅｌａｙ  Ｖａｒｉａｔｉｏｎ  Ｔｏｌｅｒａｎｃｅ：セル遅延変動許容値）によって定められている。
このようなポリシング制御の機能を備えたルータは、第１図にその概略構成を示すように、パケットの受信時刻を記録する受信時刻記録部１１と、次のパケット到着時刻を推定する推定手段１２と、ポリシング装置内での演算処理を行う演算部１３と、受信時刻記録部１１に記録されたパケット受信時刻と推定手段１２で推定された次のパケットの推定到着時刻との情報に基づいて、パケットの通過または廃棄を判定する判定部１４とから構成される制御部１０ａ〜１０ｎ（ｎは任意の整数）を備えている。このルータは、回線毎に設けられた物理ポートである複数の入力ポート３ａ〜３ｎ（ｎは任意の整数）を有し、制御部１０は、この入力ポート３ａ〜３ｎ毎にそれぞれ別々に設けられている。
さらにルータは、物理ポートである複数の出力ボート４ａ〜４ｎ（ｎは任意の整数）と、この出力ポート４ａ〜４ｎの中からポリシング判定されたパケットを出力するに相応しい適切な出力ポート２を選択するスイッチファブリック５とを備えている。なお、図１において、この入力ポート３ａ〜３ｎと出力ポート４ａ〜４ｎ上に示される矢印は、ルータに入力又はルータから出力されるパケットを示している。
このようなルータ（ポリシング制御装置）の各制御部１０ａ〜１０ｎにおけるポリシング判定は、第２図に示すようなバーチャルスケジューリングアルゴリズムに従って実行される。この処理手順について説明すると、例えば時刻［ｔ（ｋ）］（ｋは、任意の整数）にパケットを受信したとき（ステップ１０１）、先ずこのパケットの受信時刻［ｔ（ｋ）］を記録する（ステップ１０２）。そして、後述するように予め求められているパケット推定到着時刻［ＴＡＴ（Ｔｈｅｏｒｅｔｉｃａｌ  Ａｒｒｉｖａｌ  Ｔｉｍｅ）］の値と前記パケット受信時刻［ｔ（ｋ）］とを比較する（ステップ１０３）。
ここで、このパケット推定到着時刻［ＴＡＴ］よりもパケット受信時刻［ｔ（ｋ）］の方が遅い場合には、第３図（ａ）に示すように、このパケットの到着間隔が長いので、ポリシングレートに適合していると判断して、パケットを通過させると共に、次のパケットの推定到着時刻を計算する（ステップ１０４，１０６）。
また、パケット推定到着時刻［ＴＡＴ］とパケット受信時刻［ｔ（ｋ）］が等しいか、またはパケット推定到着時刻［ＴＡＴ］よりもパケット受信時刻［ｔ（ｋ）］の方が早い場合には（ステップ１０３）、さらにパケット受信時刻［ｔ（ｋ）］に後述するパケット到来許容時間［Ｌ］を加えた加算値［ｔ（ｋ）＋Ｌ］とパケット推定到着時刻［ＴＡＴ］とを比較する（ステップ１０５）。
ここで、この加算値［ｔ（ｋ）＋Ｌ］が、パケット推定到着時刻［ＴＡＴ］と同じか、またはパケット推定到着時刻［ＴＡＴ］を超える場合には、第３図（ｂ）に示すようにパケットの受信タイミングがパケット到来許容時間［Ｌ］内なので、該パケットを通過させると共に、上記パケットの推定到着時刻［ＴＡＴ］を基準として次のパケットの推定到着時刻［ＴＡＴ］を計算する（ステップ１０６）。なお、この計算では、パケット推定到着時刻［ＴＡＴ］を今回のパケットの受信時刻［ｔ（ｋ）］とし、さらに許容パケットレートの逆数で表される標準パケット到着間隔［Ｄ］を［ｔ（ｋ）］に加えることで、次のパケット推定到着時刻［ＴＡＴ］を求める。
一方、ステップ１０５において、パケット受信時刻［ｔ（ｋ）］にパケット到来許容時間［Ｌ］を加えた加算値［ｔ（ｋ）＋Ｌ］がパケット推定到着時刻［ＴＡＴ］より早い場合には、第３図（ｃ）に示すようにパケットの送信間隔が規定間隔よりも短いので、このパケットを非適合とし廃棄する（ステップ１０７）。なお、このバーチャルスケジューリングアルゴリズムの動作は、パケットが受信される度に繰り返し行われている。
このように、バーチャルスケジューリングアルゴリズムはパケットを受信した時刻［ｔ（ｋ）］と、本来そのパケットが受信される推定時刻［ＴＡＴ］とを比較することによってパケットを通過させるか廃棄すべきかを決定している。
さて、この従来例では、パケット到来許容時間［Ｌ］の値を大きくすれば、廃棄されるパケット数を減らすことができる。しかしその反面、この従来例では、契約した以上のレートでのパケット通過を短期的に許容してしまうことになる。このため、この従来例では、ポリシング制御装置が適用されるネットワークシステムに相応しいパケット到来許容時間［Ｌ］の値を予め推定手段１２に登録しておく。
上述のようなポリシング判定では、カウンタにより管理される推定時刻［ＴＡＴ］とパケット受信時間［ｔ（ｋ）］は、０以上の実数として扱われている。しかしながら実機のルータにおいては、カウンタは有限ビット長のカウンタとして実現され、一定以上の時間を超えると再びカウンタのカウント値が０に戻ることになる。このため、パケット受信時刻とパケット推定到着時刻との間で、擬似的に時刻の逆転が起き、ポリシング判定を誤る可能性がある。
例えば、前回のパケット推定到着時刻［ＴＡＴ］に許容パケットレートの逆数で表される標準パケット到着間隔［Ｄ］を加えて、次のパケットの推定到着時刻を演算した結果、パケット推定到着時刻［ＴＡＴ］の値が第４図に示すように本来［Ｔ２］となるべきところ、カウンタがオーバーフローして［Ｔ１］となり（［Ｔ１］＜［Ｔ２］）、その値が０付近に戻る場合がある。この状態になると、本来のカウント動作では、パケット到着時刻［ｔ（ｋ）］よりも大きい（時刻が遅い）パケット推定到着時刻［ＴＡＴ］になるはずが、カウンタのオーバーフローによってパケット推定到着時刻［ＴＡＴ］が小さく（時刻が早く）なってしまう。これは、本来、廃棄すべきパケットの通過を許可することを意味している。
また、パケットフローがしばらく滞ってからパケット受信が起きると、上述のパケット推定到着時刻［ＴＡＴ］のカウンタがオーバーフローする場合と同様に、パケット到着時刻［ｔ（ｋ）］のカウンタがオーバーフローして０付近の値となる場合がある。この場合は、パケット推定到着時刻［ＴＡＴ］の値が大きい（時刻が遅い）と、本来通過させるべきパケットが廃棄されることになる。そして、パケット到着時刻［ｔ（ｋ）］がパケット推定到着時刻［ＴＡＴ］の値を超えるように（時刻が遅く）なるまで、ポリシング制御装置でパケットが廃棄され続けることになる。
発明の開示
この発明は、上述したカウンタのカウント値がオーバーフローして、このカウント値が最大値から０の境界を超えて擬似的に時刻の逆転現象が起きた場合であっても、ポリシング判定を正確に行うことのできるポリシング制御方法、その制御装置およびその制御装置を用いたネットワークシステムを提供することを目的としている。
上述した課題を解決し、目的を達成するため、この発明にかかるポリシング方法は、異なるトラフィック量でネットワーク上を伝送するパケットの通過を制限するポリシング制御方法において、前記パケットが到着すると、当該パケットの到着時刻を検出する到着時刻検出工程と、パケット推定到着時刻およびパケット到来許容時間を予め設定する設定工程と、前記検出されたパケット到着時刻と前記設定されたパケット推定到着時刻との時間差を演算する演算工程と、前記演算された時間差と、前記設定されたパケット到来許容時間に標準パケット間隔時間を加えた加算値とを比較して、該時間差と加算値との大きさを判定する第１の判定工程と、前記第１の判定工程で前記時間差が前記加算値以下と判定されたときは、前記時間差とパケット到来許容間とを比較して、該時間差とパケット到来許容時間との大きさを判定する第２の判定工程と、前記第２の判定工程で前記パケット到来許容時間より前記時間差が大きいと判定されたときは、前記パケットを廃棄する廃棄工程と、前記第１の判定工程で前記加算値より前記時間差が大きいと判定されたとき、または前記第２の判定工程で前記時間差が前記パケット到来許容時間以下と判断されたときは、前記パケットの通過を許可する許可工程とを含むことを特徴とする。
また、この発明にかかるポリシング方法では、上記の発明において、前記許可工程でパケットの通過が許可されたときは、前記パケット推定到着時刻と前記標準パケット間隔時間との和を新たなパケット推定到着時刻として再設定する再設定工程を、さらに含むことを特徴とする。
また、この発明にかかるポリシング方法では、上記の発明において、前記許可工程でパケットの通過が許可されたときは、前記パケット推定到着時刻と、標準ビット間隔と前記到着したパケットのパケット長の積からなる時間を加えた値を新たなパケット推定到着時刻と再設定する再設定工程を、さらに含むことを特徴とする。
また、この発明にかかるポリシング制御装置は、異なるトラフィック量でネットワーク上を伝送するパケットの通過を制限するポリシング制御装置において、前記パケットの到着時刻を検出する検出手段と、前記パケット到着時刻と予め設定されたパケット推定到着時刻との時間差を演算する演算手段と、前記演算された時間差と、予め設定されたパケット到来許容時間に標準パケット間隔時間を加えた加算値とを比較する第１の比較手段と、前記第１の比較手段での比較結果に基づいて、前記時間差とパケット到来許容時間とを比較する第２の比較手段と、前記第１の比較手段での比較結果、または前記第１および第２の比較手段での比較結果に基づいて、該パケットの通過または廃棄を許可する許可手段とを備えたことを特徴とする。
また、この発明にかかるポリシング制御装置は、上記発明において、前記許可手段が前記パケットの通過を許可したときに、前記パケット推定到着時刻と標準パケット間隔時間との和を新たなパケット推定到着時刻として設定する設定手段を、さらに備えたことを特徴とする。
また、この発明にかかるポリシング制御装置は、上記発明において、前記許可手段が前記パケットの通過を許可したときに、前記パケット推定到着時刻と、標準ビット間隔と前記到着したパケットのパケット長の積からなる時間を加えた値を新たなパケット推定到着時刻として設定する設定手段を、さらに備えたことを特徴とする。
また、この発明にかかるポリシング制御装置の前記許可手段は、上記の発明において、前記第１の比較手段での比較結果で前記加算値より前記時間差が大きいとき、または前記第１の比較手段での比較結果で前記時間差が前記加算値以下、かつ前記第２の比較手段での比較結果で前記時間差が前記パケット到来許容時間以下のときには、前記パケットの通過を許可することを特徴とする。
また、この発明にかかるポリシング制御装置は、上記の発明において、前記許可手段は、前記第１の比較手段での比較結果で前記時間差が前記加算値以下、かつ前記第２の比較手段での比較結果で前記パケット到来許容時間より前記時間差が大きいときには、前記パケットを廃棄することを特徴とする。
また、この発明にかかるポリシング制御装置の前記演算手段は、上記の発明において、前記伝送されるパケットのパケット間隔を管理するためにカウンタを有し、該カウンタの最大計測時間は、リーキーバケットアルゴリズムのバケットカウンタの最大値と最小パケット間隔との和より十分大きい時間に設定されることを特徴とする。
また、この発明にかかるネットワークシステムは、少なくとも複数の加入者ホストと、バックボーンネットワークとから構築され、該加入者ホストとバックボーンネットワーク間で、パケットの送受信を行うネットワークシステムにおいて、前記加入者ホストとバックボーンネットワーク間に接続され、異なるトラフィック量の前記パケットの通過を制限する請求の範囲第４項〜第９項のいずれか一つに記載のポリシング制御装置を備えたことを特徴とする。
この発明では、パケット到着時刻とパケット推定時刻との時間差を中間変数とし、この中間変数と、パケット到来許容時間に標準パケット間隔時間を加えたカウンタオーバーフロー判定時間との比較結果およびこの中間変数とパケット到来許容時間との比較結果に基づいてパケットの通過を許可しており、例えカウンタのカウント値が最大値から０の境界を超えて擬似的に時刻の逆転現象が起きた場合であっても、ポリシング判定を正確に行う。
さらには、この発明によればパケット長が可変なネットワークにおいて、前述のカウンタの逆転現象が生じた場合でも、パケットフローの使用する帯域（ｂｐｓ）を正しく制御する。
発明を実施するための最良の形態
次にこの発明にかかるポリシング制御方法、その制御装置およびその制御装置を用いたネットワークシステムの好適な実施の形態について図面を参照して詳細に説明する。
まず、この発明の実施の形態１について説明する。第５図は、この発明にかかるネットワークシステムの構成を示すシステム構成図である。図において、このネットワークシステムは、ＡＴＭなどのアクセスネットワーク１と、このアクセスネットワーク１に接続され、例えば固定長のパケットであるセルのデータ中継を行うエッジルータと呼ばれるポリシング制御装置２と、このポリシング制御装置２に接続される加入者ＰＣ２１〜２５とから構築されている。このポリシング制御装置２は、ポリシング制御を行う機能が備わっており、ＡＴＭ網に存在するネットワーク接続サービスの提供者（例えば通信サービス事業者）とその加入者であるユーザ（加入者ＰＣ）との間で、契約に則したデータの伝送が可能になるように、セルのトラフィックが契約通りかどうか監視して、違反したセルをＡＴＭ網に送出せずに廃棄している。
この発明にかかるポリシング制御装置２は、基本的には前述した第１図に示す従来のポリシング制御装置と同じ入力ポート３ａ〜３ｎと、出力ポート４ａ〜４ｎと、スイッチファブリック４と、受信時刻記録部１１、推定手段１２、演算部１３および判定部１４を有する複数の制御部１０ａ〜１０ｎとから構成されている。
このポリシング制御装置２が従来のポリシング制御装置と異なる点は、パケット推定到着時刻とパケット受信時刻との時間差［Ｋ］を求めるとともに、この時間差［Ｋ］と、パケット到来許容時間［Ｌ］と標準パケット間隔［Ｄ］との和で求められるカウンタオーバーフロー判定時間［Ｍ］とを比較するアルゴリズムを実行する点である。
また、演算部１３は、パケット間隔を管理するために、図示しないカウンタを有している。このカウンタの最大計測時間は、例えばこのカウンタオーバーフロー判定時間［Ｍ］より十分に大きな値［Ｎ］に設定されている。そして、パケット到来許容時間［Ｌ］は、例えばリーキーバケットアルゴリズム（Ｌｅａｋｙ  Ｂｕｃｋｅｔ  Ａｌｇｏｒｉｔｈｍ）におけるバケツ（リーキー・バケット＝バッファ）の深さ（バッファのメモリ容量）を示すものとして定義される。ここで例えば、このバケツの深さがパケット５個分だとすると、パケット到来許容時間［Ｌ］は、［Ｌ＝５Ｄ］となる。
第６図はこの発明にかかるポリシング制御装置２のポリシング判定動作のアルゴリズを示す図である。なお、ポリシング制御装置２の制御部１０ａ〜１０ｎは、同様のポリシング判定動作を行うので、ここでは代表して制御部１０ａのポリシング判定動作を説明する。
先ず、ポリシング制御装置２の制御部１０ａでは、入力ポート３ａからパケットが受信されると（ステップ２０１）、このパケットの受信時刻［ｔ（ｋ）］が受信時刻記録部１１に記録される（ステップ２０２）。そして、予め推定手段１２に求められているパケット推定到着時刻［ＴＡＴ］とパケット受信時刻［ｔ（ｋ）］との時間差［Ｋ＝ＴＡＴ−ｔ（ｋ）］を演算部１３が演算する（ステップ２０３）。
次いで判定部１４は、この求めた時間差［Ｋ］と、パケット到来許容時間［Ｌ］と標準パケット間隔［Ｄ］との和であるカウンタオーバーフロー判定時間［Ｍ］とを比較する（ステップ２０４）。
このステップ２０４において、判定部１４による比較結果が、例えばこの時間差［Ｋ］の方がカウンタオーバーフロー判定時間［Ｍ］より大きい場合には、この受信パケットの通過を許可すると共に、パケット推定到着時刻［ＴＡＴ］を［ｔ（ｋ）］で置き換えた後、標準パケット間隔［Ｄ］を加えて次のパケット推定到着時刻［ＴＡＴ］を求める（ステップ２０５、ステップ２０７）。
一方、ステップ２０４において、この時間差［Ｋ］が、上述のカウンタオーバーフロー判定時間［Ｍ］以下の場合には、次にこの時間差［Ｋ］とパケット到来許容時間［Ｌ］とを比較する（ステップ２０６）。
ここで、この時間差［Ｋ］が、パケット到来許容時間［Ｌ］以下の場合には、このパケットの通過を許可すると共に、このパケットの推定到着時刻［ＴＡＴ］に標準パケット間隔［Ｄ］を加えて、次のパケット推定到着時刻［ＴＡＴ］を求める（ステップ２０７）。
また、ステップ２０６において、この時間差［Ｋ］の方が、パケット到来許容時間［Ｌ］よりも大きい場合には、このパケットの到来間隔が短か過ぎるとして、このパケットを廃棄する（ステップ２０８）。
次に、上述したポリシング判定を第７図〜第１０図に示すパケット受信のタイミングを例に、さらに詳細に説明する。まず、第７図では、例えばパケット推定到着時刻［ＴＡＴ］より後にパケットが到着した場合を説明する。
前回のパケット推定到着時刻［ＴＡＴ］に最小パケット到着間隔［Ｄ］を加えることで、次のパケットが到着するパケット推定到着時刻が［ＴＡＴ＝ＴＡＴ＋Ｄ］として求まる（第６図中のステップ２０７）。そして、第７図に示すようにパケット推定到着時刻［ＴＡＴ］よりも遅い時刻にパケットが受信された場合、このパケット到着時刻［ｔ（ｋ）］とパケット推定到着時刻［ＴＡＴ］との関係は［ＴＡＴ＜ｔ（ｋ）］となる。したがって、ステップ２０３で求められる時間差［Ｋ＝ＴＡＴ−ｔ（ｋ）］の値は負になる。この場合、演算はアンダーフローを起こすが、演算部１３が取り扱えるカウンタのビット幅が時間の計測に用いているカウンタのビット幅と同じだとすると、［Ｋ］の演算結果は、［Ｋ＝ＴＡＴ−ｔ（ｋ）＋Ｎ＋１］という正の値となる。
次にステップ２０４で、この値［Ｋ］をカウンタオーバーフロー判定時間［Ｍ］と比較すると、［ｔ（ｋ）−ＴＡＴ＜Ｎ＋１−Ｍ］の場合には、パケットの通過は許可され、正しく判定されるが、［ｔ（ｋ）−ＴＡＴ≧Ｎ＋１−Ｍ］の場合にはステップ２０６に進み、さらに［ｔ（ｋ）−ＴＡＴ＜Ｎ＋１−Ｌ］が成り立つと、パケットは廃棄されて誤判定が生じる。ここで、カウンタの最大計測時間［Ｎ］は、カウンタオーバーフロー判定時間［Ｍ］に比べて十分大きな値に設定されており、［ｔ（ｋ）−ＴＡＴ］は、高々［Ｎ］にしかならない。このため、ステップ２０４の判定での誤判定は、非常に短時間内の誤判定に抑えることが可能であり、実用上は問題にならない。
次に、第８図に示すように例えばパケット推定到着時刻［ＴＡＴ］より早く、かつ、パケット到来許容時間［Ｌ］を超えない時刻にパケットが到着した場合を説明する。ステップ２０３で計算された［Ｋ］の値が、ステップ２０４でカウンタオーバーフロー判定時間［Ｍ］と比較される。ここに、カウンタオーバーフロー判定時間［Ｍ］は前述したとおり［Ｍ＝Ｌ＋Ｄ］であり、パケット到着時刻［ｔ（ｋ）］がパケット推定到着時刻［ＴＡＴ］より早く、かつ、パケット到来許容時間［Ｌ］を超えない時刻である場合には、この時間差［Ｋ］はカウンタオーバーフロー判定時間［Ｍ］の値を超えることがない。つまりステップ２０４で［Ｋ＞Ｍ］の関係が不成立となり、さらにステップ２０６でパケット到来許容時間［Ｌ］と比較される。そして、パケット到来許容時間［Ｌ］よりも演算値［Ｋ］の値の方が小［Ｋ＜Ｌ］なので、パケットの到来間隔に余裕があることが確認されるのでパケットの通過が許可される（ステップ２０７）。
一方、例えば第９図に示すようにパケット推定到着時刻［ＴＡＴ］よりも先に次のパケットが到着し、かつ、このパケットがパケット到来許容時間［Ｌ］を満たさない場合についての動作を説明する。この場合、第６図に示すステップ２０３で求められる時間差［Ｋ］の値は正の整数となる。そしてステップ２０４で時間差［Ｋ］とカウンタオーバーフロー判定時間［Ｍ］（［Ｌ＋Ｄ］）との値を比較する。ここで、パケットが契約レートよりも早く到着した場合の［ＴＡＴ］の値の変化に着目すると、パケットが到着毎に［ＴＡＴ］は徐々に［ｔ（ｋ）］より大きくなっていくが、ステップ２０６の判定があるため、［ＴＡＴ−ｔ（ｋ）］は、［Ｌ＋Ｄ］を越えることはできない。従って、［Ｍ＞Ｋ＞Ｌ］の関係が成り立つ。つまり［Ｋ≦Ｍ］となる。よって、ステップ２０４の［Ｋ＞Ｍ］の判定は不成立となり、さらにステップ２０６でパケット到来許容時間［Ｌ］と比較する。そして、パケット到来許容時間［Ｌ］よりも演算値［Ｋ］の値の方が大［Ｋ＞Ｌ］なので、このパケットは廃棄される（ステップ２０８）。
このように、この実施の形態にかかるポリシング制御装置は、従来のポリシング装置と同様にカウント値がオーバーフローしない場合のパケットの通過、廃棄を適切に判定することができる。
ところで、この発明の特徴とするところは、カウント値がカウンタの最大値を超えて０に戻ってしまったときでも、パケットの通過、廃棄のポリシング判定が正しくできるところにある。例えば、第６図中のステップ２０７において、次のパケットの推定到着時刻［ＴＡＴ］を演算したところ、第１０図に示すように、カウンタのカウント範囲を超えてしまったとする。このときのカウンタ値は、第４図に示すオーバーフロー状態になり、実際の計算値［Ｔ２］であるが、カウント値は０付近の［Ｔ１＝Ｔ２−Ｎ−１］に戻ってしまう。そして、この［Ｔ１］が次のパケット推定到着時刻［ＴＡＴ］となる。次いでステップ２０３においてパケット受信時間［ｔ（ｋ）］を用いて［Ｋ＝ＴＡＴ−ｔ（ｋ）］の値を計算する。この計算は、アンダーフローを起こすので、上述のように計算結果は、［ＴＡＴ−ｔ（ｋ）＋Ｎ＋１］となるが、［ＴＡＴ＝Ｔ２−Ｎ−１］なので、演算結果は、［Ｔ２−ｔ（ｋ）］となり、オーバーフローが起きなかった場合と同じ結果が得られる。従って、ステップ２０４、ステップ２０６の判定は、上述と同じく正しく行われる。
このように、この実施の形態にかかるポリシング制御装置によれば、カウンタのパケットの到着時刻［ＴＡＴ］のカウンタがオーバーフローしても、従来のポリシング制御装置にあった、本来廃棄されなければならないパケットが誤って通過することがなくなる。そして、カウンタのオーバーフロー現象は、有限長のカウンタを使っているために必ず発生することとなるので、この実施の形態にかかるポリシング制御装置のアルゴリズムを用いれば、カウンタのカウント値がオーバーフローして、最大値から０の境界を超えて擬似的に時刻の逆転現象が起きた場合であっても、ポリシング判定を正確に行うことができ、このポリシング装置は極めて有用である。
次に、この発明の実施の形態２について説明する。この実施の形態では、上記と同様に、有限長のカウンタを用いているパケット受信時刻のカウント値が最大値から０の境界を超えてオーバーフローしたときでも、この実施の形態にかかるポリシング制御装置が正しくポリシング判定可能となることを説明する。例えば第１１図に示すようにパケットの受信時刻［ｔ（ｋ）］のカウンタがオーバーフローした場合、オーバーフローしたカウンタのカウント値は、カウンタの最大値を超えて［ｔ１（ｋ）］となる。そして、この受信時刻［ｔ１（ｋ）］を用いて、ステップ２０３で［Ｋ＝ＴＡＴ−ｔ１（ｋ）］の値を計算する。このときパケットの受信時間はオーバーフローして０に近い値［ｔ（ｋ）＝ｔ１（ｋ）−Ｎ−１］となっているので、［ＴＡＴ＞ｔ（ｋ）］となり、時間差［Ｋ］の値は正の値になる。次いで、第６図中のステップ２０４では、この計算された時間差［Ｋ］とカウンタオーバーフロー判定時間［Ｍ］とを比較する。そして、［Ｋ＞Ｍ］が成立するので、パケットの通過を許可すると共に、パケット推定到着時刻［ＴＡＴ］を［ｔ（ｋ）］で置換えた後、標準パケット間隔［Ｄ］を加えて次のパケット推定時刻［ＴＡＴ］を求める（ステップ２０５、ステップ２０７）。
このようにパケット受信時刻のカウンタ［ｔ（ｋ）］がオーバーフローしたとしても正しくポリシング判定できることになる。
ただし、パケットの推定到着時刻［ＴＡＴ］よりも遅れてパケットが受信され、そのときのパケット受信時刻［ｔ（ｋ）］のカウンタがオーバーフローして［ｔ（ｋ）←ｔ１（ｋ）］となった場合、［ｔ（ｋ）］が［ＴＡＴ］より小さく、かつ［ＴＡＴ−Ｍ］以上の場合、第６図中のステップ２０４の判定で［Ｋ＞Ｍ］が成立しないので、本来はパケットの通過後、［ＴＡＴ＝ｔ（ｋ）＋Ｄ］となるべきところが、［ＴＡＴ］に誤った値が設定され、パケット廃棄が生じる場合がある。
しかし、上述のように、カウンタオーバーフロー判定時間［Ｍ］は、カウンタの最大計測時間［Ｎ］に比べて十分小さいので、非常に短時間内の誤判定に抑えることができる。
なお、パケット長が可変できるネットワークにおいては、ステップ２０７の標準パケット間隔［Ｄ］の代わりに、パケットの伝送ビットを許容する許容ビットレートを用いることも可能である。この場合には、許容ビットレートの逆数である標準ビット間隔［Ｂ］と到着パケット長［ＬＥＮ］との積をパケットの推定到着時刻［ＴＡＴ］に加えた、［ＴＡＴ＝ＴＡＴ＋Ｂ×ＬＥＮ］を新たなパケット推定到着時刻としてもよい。
さらにはカウンタの最大計測時間［Ｔｃｍａｘ］をパケット到来許容時間［Ｌ］と、標準ビット間隔［Ｂ］と到着パケット長［ＬＥＮ］との積［Ｂ×ＬＥＮ］との和より十分大きな時間［Ｌ＋Ｂ×ＬＥＮ≪Ｔｃｍａｘ］とすることで、上述のカウンタの逆転現象が生じた場合でもパケットフローが使用する帯域を正しく制御することができる。
一方、従来のアルゴリズムではカウンタがオーバーフローし、その値が０付近に戻る場合、廃棄すべきパケットが通過されてしまうことがあった。或いは、パケットフローの受信がしばらく滞ってからパケット受信が起きた場合、パケット到着時刻のカウンタがオーバーフローし、０付近の値となる場合はポリシング制御装置でパケット到着時刻［ｔ（ｋ）］がパケット推定到着時刻［ＴＡＴ］の値を超えるように（時刻が遅く）なるまで、パケットが廃棄され続けることが起きていた。
しかしながら、この発明のルータ（ポリシング制御装置）のアルゴリズムによれば上述のように、パケット推定到着時刻［ＴＡＴ］のカウンタまたはパケット到着時刻［ｔ（ｋ）］のカウンタがオーバーフローしたとしてもポリシングの誤判定を著しく改善することが可能となる。
以上述べたように、この発明にかかるポリシング制御装置によれば、カウンタの値が０を超えて擬似的に時間の逆転現象が起きたとしても、時間差として中間変数［Ｋ］を設け、［Ｋ＝ＴＡＴ−ｔ（ｋ）］なる演算を施した後、［Ｍ＝Ｌ＋Ｄ］と比較するアルゴリズムを追加することによって、従来のハードウェア資源を活かしつつ、ポリシングの誤判定問題を著しく改善することが可能となる。
また、この発明のポリシング制御装置によればカウンタのオーバーフローを少なくするためにカウントの語長を無闇に大きくする必要もなく、信頼性の高いポリシング制御が容易に実現可能になる等の実用上多大なる効果が奏せられる。
産業上の利用可能性
以上のように、この発明にかかるポリシング方法、その制御装置およびその制御装置を用いたネットワークシステムは、パケット間隔を管理するためのカウンタのカウント値がオーバーフローして、擬似的に時刻の逆転現象が起きた場合でも、ポリシング判定を正確に行うパケット通信網、例えばＡＴＭ網やＩＰ網などのネットワークシステムに適している。
【図面の簡単な説明】
第１図は、ポリシング制御装置の概略構成を示す図であり、第２図は、従来のポリシング制御装置の制御アルゴリズムを示すフローチャートであり、第３図は、パケットのポリシング制御の概念を示すタイミング図であり、第４図は、カウンタのカウント状況を示す図であり、第５図は、この発明にかかるネットワークシステムの構成を示すシステム構成図であり、第６図は、この発明の一実施形態にかかるポリシング制御装置の制御アルゴリズムを示すフローチャートであり、第７図は、パケット到着時刻が推定到着時刻よりも遅い場合を示すタイミング図であり、第８図は、パケット到着時刻が推定到着時刻よりも早い場合を示すタイミング図であり、第９図は、パケット到着時刻が推定到着時刻よりも早い場合を示すタイミング図であり、第１０図は、推定到着時刻のカウンタがオーバーフローした場合を示すタイミング図であり、第１１図は、パケット到着時刻のカウンタがオーバーフローした場合を示すタイミング図である。
【図１】
2003053012.tif 000003
【図２】
2003053012.tif 000004
【図３】
2003053012.tif 000005
【図４】
2003053012.tif 000006
【図５】
2003053012.tif 000007
【図６】
2003053012.tif 000008
【図７】
2003053012.tif 000009
【図８】
2003053012.tif 000010
【図９】
2003053012.tif 000011
【図１０】
2003053012.tif 000012
【図１１】
2003053012.tif 000013
【国際調査報告】
2003053012.tif 000014
2003053012.tif 000015