(57)【要約】  送出チャネルを通じて伝送するべく提示されたパケットの受け入れのレート制御を実現するパケットスイッチング構成であって、正確なレート制御を許容する自動訂正係数を算出する段階を含み、バースト送信を制限すると共に、過少利用を制限する。
2005513829.tif 000002
【特許請求の範囲】
【請求項１】
送出チャネルを通じて伝送するべく提示されたパケットの受け入れのレート制御を実現するパケットスイッチング構成であって、
選択されたビット数を表す値を保存する手段と、
提示されたパケットが前記選択されたビット数内において伝送される場合にのみ、前記提示されたパケットの伝送を許容し、前記伝送に続いて、前記選択された利用可能なビット数内において伝送可能であった残りの利用可能なビット数を計測する手段と、
伝送する残りのビットが存在しているが、これが、次の提示されたパケットをすべて伝送するのに十分なビット数ではない場合に、直後に続く選択された長さの時間のために、この残りのビット数（又は、実質的にこのビット数）だけ、前記選択されたビット数を表す保存されている値を増加させる手段と、
を含む構成。
【請求項２】
送出チャネルを通じて伝送するべく提示されたパケットの受け入れのレート制御を実現するパケットスイッチング構成であって、
選択された長さの時間において伝送される選択されたビット数を表す値を保存する手段と、
提示されたパケット内のビット数と前記選択された長さの時間において既に伝送されているビット数を組み合わせたものが、前記選択されたビット数内に収まっている場合にのみ、前記提示されたパケットの伝送を許容する手段と、
前記伝送に続いて、前記選択された利用可能なビット数内において伝送可能であったが、次の提示されたパケットをすべて伝送するのに十分なビット数ではない残りのビット数を計測する手段と、
直後に続く前記選択された長さの時間のために、この残りのビット数（又は、実質的にこのビット数）だけ、前記選択されたビット数を表す前記保存されている値を増加させる手段と、
を含む構成。
【請求項３】
送信するべくパケットが利用可能であった際に、パケットが１つ又は複数の選択された長さの時間において伝送されなかった場合に、不活性な期間が発生したことを検出する手段と、
「前記残りのビット数」＋「前記不活性期間において伝送可能であったビット数」−「前記不活性期間において伝送するべく提示されたすべてのパケットにおけるビット数」に実質的に等しい量だけ、選択された長さの時間において伝送するべく許容された前記選択されたビット数を表す前記保存されている値を増加させる手段と、
を含む請求項２記載の構成。
【請求項４】
前記選択された長さの時間は、許容可能な最大パケットを伝送するのに必要な時間である請求項２又は３記載の構成。
【請求項５】
前記選択された長さの時間は、物理的な実装によって区別可能な最小時間単位である請求項２又は３記載の構成。
【請求項６】
送出チャネルを通じて伝送するべく提示されたパケットの受け入れのレート制御を実現するパケットスイッチングを実現する方法であって、
選択された期間において伝送するべく選択されたビット数を表す値を保存する段階と、
提示されたパケットが前記選択されたビット数以下によって伝送される場合にのみ、前記提示されたパケットの伝送を許容する段階と、
前記伝送に続いて、前記選択された長さの時間内における残りの利用可能なビット数を計測する段階と、
残りのビットが存在しているが、これが、次の提示されたパケットをすべて伝送するのに十分ではない場合に、直後に続く前記選択された長さの時間のために、この残りのビット数（又は、実質的にこのビット数）だけ、許容されている前記選択されたビット数を表す前記保存されている値を増加させる段階と、
を含む方法。
【請求項７】
送出チャネルを通じて伝送するべく提示されたパケットの受け入れのレート制御を実現するパケットスイッチングを実現する方法であって、
選択された長さの時間において伝送するべく許容された選択されたビット数を表す値を保存する段階と、
提示されたパケット内のビット数と前記選択された期間内において既に伝送されているビット数を組み合わせたものが、前記選択されたビット数内に収まる場合にのみ、前記提示されたパケットの伝送を許容する段階と、
前記伝送に続いて、前記選択された長さの時間内において伝送可能であったが、次の提示されたパケットのすべてを伝送するのに十分ではない残りのビット数を計測する段階と、
直後に続く選択された長さの時間のために、この残りのビット数（又は、実質的にこのビット数）だけ、許容されている前記選択されたビット数を表す前記保存されている値を増加させる段階と、
含む方法。
【請求項８】
送信するべくパケットが利用可能であった際に、パケットが１つ又は複数の選択された長さの時間において伝送されなかった場合に、不活性な期間が発生したことを検出する段階と、
「前記残りのビット数」＋「前記不活性な期間において伝送可能であったビット数」−「前記不活性な期間において伝送するべく提示されたすべてのパケットにおけるビット数」に実質的に等しい量だけ、選択された長さの時間において伝送するべく許容された前記選択されたビット数を表す前記保存されている値を増加させる段階と、
を更に含む請求項７記載の方法。
【請求項９】
請求項７又は８記載の方法を実現するべくプログラムされたデジタルコンピュータ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケットスイッチング構成における改善されたビットレート制限に関するものである。
【背景技術】
【０００２】
チャネルのビットレートを制限するＴＢＦ（Ｔｏｋｅｎ  Ｂｕｃｋｅｔ  Ｆｉｌｔｅｒｉｎｇ：トークンバケットフィルタリング）は、周知の技法である。
【０００３】
ＴＢＦは、バケツの上限に到達するまで、設定レートによってトークンで満たされるバケツの概念を有するものである。パケットを送信するには、チャネルは、当該パケットの送信に十分なトークンを取得しなければならない。そして、パケットの送信が完了すると、これらのトークンは破棄される。必要なトークンをすべて取得できていない場合には、チャネルは、更なるトークンによってバケツが満たされるまで待機しなければならず、送信は、その後に行われることになる。
【０００４】
特定のレート制限シナリオにおいて、この技法は、２つの主要な問題点を有している。第１に、ＴＢＦフィルタリングによれば、バケツがいくつかのトークンを保持できるため、トークンの補充レートに安定化する前の段階で、トラフィックが、バケツが満たされるレートを超過して、一定の期間にわたってバーストすることがある。
【０００５】
もう１つの問題点は、トークンにおける丸めの誤差が考慮されていないため、不正確なものになり得るという点である。即ち、ＴＢＦの場合には、トークンがいくつバケツに入ったかを算出するために、現在の時間とトークンが最後に算出された時間との時間差を算出し、これに対してバケツの補充レートを乗算している。この結果、端数のトークンをバケツに付与しなければならないにも拘らず、トークンが整数値であることから、付与できないという状況が発生するのである。毎回、端数のトークンが失われた場合、時間の経過と共にその累積的な影響は、（特に、トークンの補充レートが低い場合に）大きな丸め誤差となって表れる。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
従って、丸めの誤差を伴うことなしに、初期のチャネルバーストを最小化すると共に、チャネルを所与のレートに制限するレート制限メカニズムを提供すること（或いは、少なくとも有用な代替手段を提供すること）が本発明の目的である。
【課題を解決するための手段】
【０００７】
本発明の一態様は、送出チャネルを通じて伝送するべく提示されたパケットの受け入れのレート制御を実現するパケットスイッチング構成であって、この構成は、選択されたビット数を表す値を保存する手段と；提示されたパケットが選択されたビット数内において伝送される場合にのみ、当該パケットの伝送を許容し、この伝送に続いて、選択された利用可能なビット数において伝送可能であった残りの利用可能なビット数を計測する手段と；送信するための残りのビットが存在しているが、これが、次の提示されているパケットをすべて伝送するのに十分なビット数ではない場合に、直後に続く選択された長さの時間のために、その残りのビット数（又は、実質的にこのビット数）だけ、選択されたビット数を表す保存されている値を増加させる手段と、を含んでいる。
【０００８】
本発明の別の態様は、送出チャネルを通じて伝送するべく提示されたパケットの受け入れのレート制御を実現するパケットスイッチング構成であって、この構成は、選択された長さの時間において伝送される選択されたビット数を表す値を保存する手段と；提示されたパケット内のビット数と選択された長さの時間において既に伝送されているビット数を組み合わせたものが、選択されたビット数内に収まっている場合にのみ、提示されたパケットの伝送を許容する手段と；この伝送に続いて、選択された利用可能なビット数において伝送可能であったが、次の提示されたパケットのすべてを伝送するのに十分なビット数ではない残りのビット数を計測する手段と；直後に続く選択された長さの時間のために、この残りのビット数（又は、実質的にこのビット数）だけ、選択されたビット数を表す保存されている値を増加させる手段と、を含んでいる。
【０００９】
送信するべくパケットが利用可能であった際に、パケットが１つ又は複数の選択された長さの時間において伝送されなかった場合に、不活性な期間が発生したことを検出する手段と；「残っているビット数」＋「不活性な期間において伝送可能であったビット数」−「不活性な期間において伝送するべく提示されたすべてのパケットにおけるビット数」に実質的に等しい量だけ、選択された長さの時間において伝送するべく許容された選択されたビット数を表す保存されている値を増加させる手段と；が更に含まれていることが好ましい。
【００１０】
選択された長さの時間は、許容可能な最大のパケットを伝送するのに必要な時間であることが好ましい。
【００１１】
選択された長さの時間は、物理的な実装によって区別可能な最小時間単位であることが好ましい。
【００１２】
本発明の別の態様は、送出チャネルを通じて伝送するべく提示されたパケットの受け入れのレート制御を実現するパケットスイッチングを実現する方法であって、この方法は、選択された期間において伝送される選択されたビット数を表す値を保存する段階と；提示されたパケットが、選択されたビット数以下において伝送される場合にのみ、当該パケットの伝送を許容する段階と；この伝送に続いて、選択された長さの時間内における残りの利用可能なビット数を計測する段階と；残りのビットが存在しているが、これが、次の提示されたパケットのすべてを伝送するのに十分なものではない場合に、直後に続く選択された長さの時間のために、この残りのビット数（又は、実質的にこのビット数）だけ、許容されている選択されたビット数を表す保存されている値を増加させる段階と、を含んでいる。
【００１３】
本発明の更に別の態様は、送出チャネルを通じて伝送するべく提示されたパケットの受け入れのレート制御を実現するパケットスイッチングを実現する方法であり、この方法は、選択された長さの時間において伝送するべく許容された選択されたビット数を表す値を保存する段階と；提示されたパケットにおけるビット数と選択された期間において既に伝送されているビット数を組み合わせたものが、選択されたビット数内に収まる場合にのみ、提示されたパケットの伝送を許容する段階と；この伝送に続いて、選択された長さの時間内において伝送可能であったが、次の提示されたパケットのすべてを伝送するのに十分ではない残りのビット数を計測する段階と；直後に続く選択された長さの時間のために、この残りのビット数（又は、実質的にこのビット数）だけ、許容されている選択されたビット数を表す保存されている値を増加させる段階と、を含んでいる。
【００１４】
送信するベくパケットが利用可能であった際に、パケットが１つ又は複数の選択された長さの時間において伝送されなかった場合に、不活性な期間が発生したことを検出する段階と；「残りのビット数」＋「不活性な期間において伝送可能であったビット数」−「不活性な期間において伝送するべく提示されたすべてのパケットにおけるビット数」に実質的に等しい量だけ、選択された長さの時間において伝送するべく許容された選択されたビット数を表す保存されている値を増加させる段階と、を更に含むことが好ましい。
【００１５】
本発明のその他の態様については、以下の説明を参照することにより、理解されるであろう。これらの態様は、以下の特徴の一部又はすべてを有することができる。
【００１６】
以下、本発明に対する理解を深めるべく、好適な実施例との関連で、本発明について説明する。尚、これらの特定の実施例は、本発明の一形態を示すものに過ぎないことを理解されたい。
【発明を実施するための最良の形態】
【００１７】
添付の図面を詳細に参照すれば、伝送バイト数を表すＹ軸１１３が示されている。Ｘ軸１１４は、時間を表している。このシステムにおいては、時間は、量子化されており、クォンタムのサイズは、システムにおいて許容されている最大のパケットを伝送するのに所要する時間の長さ、又はシステムのカーネル時間分解能のいずれか大きいものとして選択されている。図１には、隣接するタイムクォンタム１０７、１０８、１０９、及び１１０が示されている。又、この図には、１タイムクォンタムよりも大きな時間間隔だけ離隔した隣接するタイムクォンタム１１１及び１１２が更に示されている。
【００１８】
ライン１０６は、送出リンクの選択ビットレートを表している。又、これは、任意のタイムクォンタムにおいてシステムが送信可能なビット数における限度の最小値でもある。第１のタイムクォンタムにおいて伝送が許容されているバイト数１０３は、この最小レベルと同一であり、第２タイムクォンタムにおいても、送信可能なパケット数に対する上限は、依然、変化してはいない。この第２タイムクォンタムにおいては、サイズがＮビットのパケットNが、伝送のためにキューイングされており、この第２タイムクォンタムにおいて既に送信済みのビット数は、Ｐである。このＮとＰの合計１０１は、明らかに、限度レベル１０３を上回っている、従って、このパケットは、伝送されないことになる。そして、送信済みの実際のバイト数Ｐが限度１０３を下回っているため、自動訂正値が算出されることになり、これは、限度レベル１０６と値Ｐとの差である。そして、この値が最小レベル１０６に加算され、直後に続くタイムクォンタムに対して伝送限度１０５が付与されることになる。この第３のタイムクォンタムにおいては、チャネルは、送信対象としていくつかのビット１０２を有している。そして、これは、限度１０５を下回っているため、この伝送の実行は許容されることになる。
【００１９】
カーネルは、システムからのパケットの送信を継続的に要求する。カーネルがパケットを要求するまで、パケットが送信されることはない。状況に応じて、カーネルが、その他の負荷のために、１つの又は一連のタイムクォンタムにおいて、パケットを要求しない場合がある。これは、送出リンクにおける障害であり、次のタイムクォンタムにおいて補償しなければならない。
【００２０】
任意のタイムクォンタム１１２におけるシステムを考えてみる。このタイムクォンタムにおいて、カーネルがパケットを要求し、前回から１タイムクォンタムを上回る期間にわたって、パケットの送信準備が整ってはいたが、カーネルがパケットを転送することができなかったということを検出すると、「最後のカーネル要求における自動訂正係数」−「カーネルのビジー期間において蓄積されたすべてのパケットの合計」＋「ビジー期間において送信可能であったパケットの数」に実質的に等しい新しい自動訂正係数を当該タイムクォンタムに対して算出する必要がある。
【００２１】
図２を参照すれば、それぞれの到来パケットのサイズを判定するカウンタとしても機能する到来データバッファ１０が存在している。伝送済みのビット数を判定するカウンタとしても機能する送出バッファ１２が存在している。そして、現在のタイムクォンタムにおいて伝送される最大ビット数の値を保存するストレージ要素１４が存在している。当初、この値は、送出リンク上において維持するべく選択された全体ビットレートであるレベル１０６に設定されている。
【００２２】
データパケットは、入力バッファ１０によって受信されるが、自動訂正ルーチン１５によって受け入れ信号１１が供給されるまで、出力バッファ１２には伝送されない。
【００２３】
このルーチンは、現在のタイムクォンタムにおいて伝送に利用可能な容量のビット数とパケットサイズとを比較し、パケットサイズが、この残りの容量以下である場合にのみ、受け入れ信号を供給する。この残りの容量値は、送出カウンタ１２によって供給される伝送済みのビット数と、ストレージ要素１４内に保存されているこの期間において送信が許容されているビット数の値を比較することにより、比較ルーチン１３によって算出される。
【００２４】
そして、自動訂正ルーチン１５が、パケットを送信しないと判定した場合には、受け入れ信号は供給されず、この期間において、更なるパケットは送信されない。そして、残りの容量値がゼロでない場合には、この値が自動訂正値となる。この自動訂正値は、１タイムクォンタムにおいて伝送されるビットの最大数である初期値（１０６）に加算され、この結果生成された値がストレージ要素１４内に保存される。
【００２５】
次いで、このプロセスは、次のタイムクォンタムにおいて反復される。
【００２６】
自動訂正ルーチン１５は、送信するべくパケットが利用可能であった際に、パケットが１つ又は複数の選択された長さの時間において伝送されなかった場合に、期間の発生を検出することができる。そして、このルーチンは、「ビットの送信に成功した最後の期間の残りの容量値」＋「不活性期間において伝送可能であったビット数」−「不活性期間において伝送するべく提示されたすべてのパケットにおけるビット数」の合計として、自動訂正値を算出する。次いで、この自動訂正値は、１タイムクォンタムにおいて伝送される最大ビット数の初期値（１０６）に加算され、この結果生成された値がストレージ要素１４内に保存される。
【図面の簡単な説明】
【００２７】
【図１】本方法を図式的に示すものである。
【図２】同一実施例の機能ブロックダイアグラムを示すものである、
【図１】
2005513829.tif 000003
【図２】
2005513829.tif 000004
【国際調査報告】
2005513829.tif 000005
2005513829.tif 000006