JPH11234285A - セル送出装置、スケジューラ装置及びセル送出レート制御方法 - Google Patents

Abstract

(57)【要約】 【課題】 必要最小限のメモリ量で実現でき、仮想コネ
クションの設定や解放に伴う処理が簡潔で、シェイピン
グを行なわない他のトラヒックをバースト的させること
のないセル送出装置を提供すること。 【解決手段】 ＶＣ毎のセル送出レートが、定められた
第１のレートを越えないように制御するセル送出装置で
あって、制御すべきＶＣのＶＣ識別子を蓄積するための
少なくとも１つのキューを備え、キューに蓄積されてい
るＶＣ識別子を、設定された第２のレートで定められる
時間間隔で順次取り出して、セルを出力すべきＶＣの候
補として決定し、キューから取り出されたＶＣ識別子に
より示されるＶＣに依然として送出待ちセルが存在する
場合に、その取り出されたＶＣ識別子をキューに再び入
れ、第２のレートを、キューに蓄積されているＶＣ識別
子に対して定められた第１のレートに基づいて決定する
ことを特徴とする。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、パケットの仮想コ
ネクション毎の流量制御を行なうセル送出装置、スケジ
ューラ装置及びセル送出レート制御方法に関する。

【０００２】

【従来の技術】近年、世界各国でＡＴＭ通信網が通信基
盤として整備されつつある。ＡＴＭ通信方式は、セルと
呼ばれる固定長の短パケットを扱うため、ハードウェア
での交換が容易に可能で、セル交換スループットの高速
化が容易であるという利点を持つ。さらに、ＡＴＭ通信
方式には、その高速な物理リンク内に複数のＶＣ（Ｖｉ
ｒｔｕａｌ Ｃｏｎｎｅｃｔｉｏｎ：仮想コネクショ
ン）を設定することができるという柔軟性がある。ＡＴ
ＭのＶＣには、ＶＣＣ（Ｖｉｒｔｕａｌ Ｃｈａｎｎｅ
ｌ Ｃｏｎｎｅｃｔｉｏｎ）と、ＶＣＣを論理的に束ね
て扱うＶＰＣ（Ｖｉｒｔｕａｌ Ｐａｔｈ Ｃｏｎｎｅ
ｃｔｉｏｎ）が定義されている。

【０００３】ＡＴＭ通信方式の転送サービスカテゴリと
しては、ＣＢＲ、ｒｔ−ＶＢＲ、ｎｒｔ−ＶＢＲ、ＡＢ
Ｒ、ＵＢＲ、ＡＢＴが標準化されている。このうち、品
質保証可能で最も基本的なサービスがＣＢＲ（Ｃｏｎｓ
ｔａｎｔ Ｂｉｔ Ｒａｔｅ）である。ＣＢＲは、一定
レートですなわち一定の時間間隔でＶＣ上に送出される
セルの転送サービスであり、他のサービスカテゴリと比
べてよいセル廃棄品質やキューイング遅延品質を期待す
ることができる。

【０００４】このＣＢＲサービスの実現では、セル送出
装置が重要な役割を果たす。複数のＣＢＲのＶＣのセル
を送出する場合、各ＶＣに設定されたレートに応じて一
定間隔でセルを送出する特別な制御機能が必要となる。
この制御機能はシェイピング（ｓｈａｐｉｎｇ）と呼ば
れ、またシェイピングを行なう装置はシェイパ（ｓｈａ
ｐｅｒ）と呼ばれる。シェイパは大きく分けると２つに
分類できる。１つは、端末にあって、セルを設定レート
に応じて送出するものであり、もう１つは、ネットワー
ク内にあって、ネットワーク内を転送される途中で変形
したトラヒックを設定レートに適合するように再整形す
るものである。両タイプのシェイパの構成は、原理的に
は同様であり、送信するセルの間隔が近付き過ぎないよ
うにセルの送出間隔を制御するものである。

【０００５】次に、シェイパの基本的な構成例について
説明する。例えばＡＴＭ通信網におけるシェイパは、図
５に例示するように、セルをＶＣ毎に蓄積するバッファ
（キュー）１１と、セルを出力すべきＶＣ（の候補）を
選択するスケジューラ１３と、スケジューラに指示され
たＶＣのバッファ（キュー）からセルを取り出して出力
するセレクタ１２とを含む。ここでは、ＶＣの識別子を
ＶＣＩ（ＶＣ Ｉｄｅｎｔｉｆｉｅｒ）と呼ぶことにす
る。

【０００６】図６に、従来のスケジューラの一構成例を
示す。このスケジューラは、ＶＣＩの値を書き込むため
の大きなメモリ２３１と、そのメモリ上のＶＣＩへのポ
インタ２３２を用いる。メモリのアドレスは論理的にリ
ング状になっている。ポインタが示すＶＣＩを、セルを
出力すべきＶＣＩとし、セルを出力するタイミング毎に
ポインタが指す位置を隣へ移動させる。もしポインタが
示す場所にＶＣＩが書き込まれていない場合や、そのＶ
Ｃに出力待ちセルが存在しない場合にはセルを出力しな
い。

【０００７】この構成例では、セルを出力できる最小の
時間間隔を１とすると、例えばメモリ上に２０間隔で同
じＶＣＩ＝ｘを書き込んでおけば、そのＶＣＩ＝ｘのセ
ルは２０の時間間隔で出力されることになる。残りの空
いているメモリ上に３０間隔で別のＶＣＩ＝ｙを書いて
おけば、先のＶＣＩ＝ｘと並行してそのＶＣＩ＝ｙのセ
ルは３０の間隔で出力される。

【０００８】この従来のスケジューラの問題点は、大き
なメモリを用意しなければならないことである。例え
ば、間隔を１００とするためには少なくとも１００の大
きさを持つメモリを用意しなければならないし、間隔が
１００００であれば１００００以上の大きさのメモリを
用意しなければならない。通常、このメモリサイズは、
シェイピングの対象とするＶＣの数よりもシェイピング
レートに依存するため、シェイピングレートが小さいほ
ど、つまり時間間隔が大きいほど、大きくなる。このよ
うに従来のスケジューラでは、低コストでシェイパを実
現することが難しい。

【０００９】さらに、例えば、大きさが１００００のメ
モリ上に、間隔１０のＶＣを設定するためには、１０の
間隔で１０００回、ＶＣＩをメモリに書き込まなければ
ならい。このように、従来のスケジューラでは、ＶＣの
設定と解放の手順が繁雑になるという別の欠点もある。

【００１０】図７に、従来のスケジューラの他の構成例
を示す。このスケジューラは、リング状に配列された複
数のＶＣＩキュー（その各々を回転キューと呼ぶ）２３
３と、回転キューを１つずつ順に示していくポインタ２
３４と、出力待ちキュー２３５で構成されている。

【００１１】この構成例では、スケジューラは、セルを
蓄積していないＶＣにセルが到着すると、そのＶＣに設
定されたシェイピングレートに応じて適切な回転キュー
を選び、その回転キューへＶＣＩを入れる。

【００１２】一方、ポインタは、セルを出力するタイミ
ング毎にリング状に配列された回転キューを１つずつ順
に示していく。そして、ポインタにより示された回転キ
ュー内のＶＣＩをすべて出力待ちキューへ転送する。

【００１３】出力待ちキューから取り出されたＶＣＩが
セルを出力すべきＶＣＩとなるが、該当するセルを出力
した後にそのＶＣにまだ出力待ちのセルが残っている場
合には、再び、そのＶＣに設定されたシェイピングレー
トに応じて適切な回転キューが選ばれ、当該ＶＣＩがそ
の回転キューに入れられる。例えば、あるＶＣのシェイ
ピングレートが２０間隔であれば、現在のポインタの位
置から２０間隔に相当する分だけ離れた位置の回転キュ
ーへＶＣＩを入れる。

【００１４】この構成では、偶然複数の回転キューのう
ちのごく少数にＶＣＩがかたよってしまうことがあり得
る。もしそのようになると、シェイパから出力されるセ
ルがバースト的になってしまうという欠点がある。この
バーストは、各ＶＣに設定されるシェイピングレートが
同じである場合、継続して繰り返されることになる。セ
ル送出装置には、シェイパによって出力されるセルと、
シェイパの制約を受けないＡＢＲ、ＵＢＲサービスなど
のセルの両方が出力を待っていることがあるが、通常は
シェイピングされたトラヒックに悪影響を与えないよう
に、シェイパからの出力セルを優先出力することが多
い。したがって、もしシェイパから出力されるセルがバ
ースト的になれば、ＡＢＲやＵＢＲサービスなど他のサ
ービスカテゴリのセルの出力も必然的にバースト的にな
ってしまう。トラヒックがこのようなバースト性を持つ
と、ネットワーク内でセルが廃棄されやすくなるため、
非常に好ましくない。

【００１５】シェイパの使用環境を考えた場合、多数の
ＶＣをシェイピングしたいが、シェイピングレートの種
類は少数で十分という場合がある。上述した従来のスケ
ジューラを適用するシェイパは、全てのＶＣが互いに異
なるシェイピングレートを持つ場合を指向していると考
えられるが、少ない種類のシェイピングレートに分類で
きるたくさんのＶＣを扱う場合には良い実現方法とはい
えなかった。

【００１６】

【発明が解決しようとする課題】以上説明したように、
従来のシェイピング方式では、扱うＶＣ数に比べて大き
なメモリが必要である、ＶＣの設定や解放に伴う処理が
繁雑である、他のサービスカテゴリのトラヒックをバー
スト的に変化させてしまう可能性がある、などの問題点
があった。なお、この問題点はＡＴＭ通信方式に限ら
ず、他のパケット通信方式においてシェイピングを用い
る場合にも同様に発生するものである。

【００１７】本発明は、上記事情を考慮してなされたも
ので、必要最小限のメモリ量で実現でき、仮想コネクシ
ョンの設定や解放に伴う処理が簡潔で、シェイピングを
行なわない他のトラヒックをバースト的にさせることの
ないセル送出装置を提供することを目的とする。

【００１８】

【課題を解決するための手段】本発明（請求項１）は、
仮想コネクション（例えば、ＶＣ（ＶｉｒｔｕａｌＣｏ
ｎｎｅｃｔｉｏｎ））毎のセル送出レートが、定められ
た第１のレート（例えば、シェイピングレートがこれに
該当する）を越えないように制御するセル送出装置であ
って、制御すべき仮想コネクションの仮想コネクション
識別子（例えば、ＶＣＩ）を蓄積するための少なくとも
１つの蓄積手段（例えば、キュー）と、前記蓄積手段に
蓄積されている仮想コネクション識別子を、設定された
第２のレート（例えば、後述するＳＱＳレートがこれに
該当する）で定められる時間間隔で順次取り出して、セ
ルを出力すべき仮想コネクションの候補として決定する
第１の制御手段と、前記蓄積手段から取り出された仮想
コネクション識別子により示される仮想コネクションに
依然として（例えばセルを送出した後に）送出待ちセル
が存在する場合に、その取り出された仮想コネクション
識別子を前記蓄積手段に再び入れる第２の制御手段と、
前記第２のレートを、前記蓄積手段に蓄積されている仮
想コネクション識別子に対して定められた第１のレート
に基づいて（例えば、蓄積手段内の全ての仮想コネクシ
ョン識別子の第１のレートの合計に応じて）決定する第
３の制御手段とを備えたことを特徴とする。

【００１９】なお、上記の代わりに、前記蓄積手段から
取り出された仮想コネクション識別子により示される仮
想コネクションが解放されるまで、その取り出された仮
想コネクション識別子を前記蓄積手段に再び入れるよう
にしてもよい。この場合、送出待ちセルのない仮想コネ
クションの仮想コネクション識別子が選択されたなら
ば、代わりの出力可能な他の仮想コネクションのセルを
出力するか、もしくはセルの送出を行わないようにす
る。

【００２０】また、蓄積手段に同一の仮想コネクション
識別子を複数入れることを可能としてもよい。蓄積手段
に同一の仮想コネクション識別子をｎ個入れた仮想コネ
クションは、蓄積手段に同一の仮想コネクション識別子
を１個入れた仮想コネクションに対して、送出レートが
ｎ倍となる。これによって、複数種類の第１のレートを
扱うことができる。

【００２１】また、蓄積手段を複数設けることも可能で
ある。この場合には、上記の第１〜第３の制御手段はそ
れらを一組として各蓄積手段ごとに設ける。各蓄積手段
からの出力は各第２のレートに応じて時分割的に処理さ
れる。

【００２２】また、この場合、例えば、同じ第１のレー
トの仮想コネクション識別子は同じ蓄積手段で管理さ
せ、各蓄積手段に異なる第１のレートの値を担当させる
ようにすることもできる。これによって、複数種類の第
１のレートを扱うことができる。さらに、ある蓄積手段
には同一の仮想コネクション識別子を複数入れることを
可能としてもよい。

【００２３】好ましくは、前記第２の制御手段は、前記
仮想コネクションの解放前は、前記蓄積手段から取り出
された仮想コネクション識別子により示される仮想コネ
クションに（例えばセルを送出したために）送出待ちセ
ルが存在しなくなった場合にも、その取り出された仮想
コネクション識別子を前記蓄積手段に再び入れる手段を
含むようにしてもよい。

【００２４】好ましくは、前記蓄積手段内の仮想コネク
ション識別子の数の減少または増加によって減少変更ま
たは増加変更を伴う前記第２のレートが決定された場合
に、前記第２のレートの設定値をその新たに決定された
値に変更させるタイミングを制御することによって、該
蓄積手段によりセル送出を制御している各仮想コネクシ
ョンに対してセル送出レートが第１のレートを越えない
ことを保証するようにしてもよい。

【００２５】好ましくは、前記蓄積手段内の仮想コネク
ション識別子の数の減少または増加によって、減少変更
または増加変更を伴う前記第２のレートが決定された場
合、前記第２のレートの減少変更は、減少変更を伴う第
２のレートを決定させるもとになった仮想コネクション
識別子が前記蓄積手段から取り出されたときから、該蓄
積手段から次の仮想コネクション識別子が取り出される
ときまでの間の所定のタイミングで行い、前記第２のレ
ートの増加変更は、増加変更を伴う第２のレートを決定
させるもとになった仮想コネクション識別子が前記蓄積
手段に入れられたときに該蓄積手段に蓄積されていた個
数の仮想コネクション識別子が該蓄積手段から取り出さ
れたとき以降の所定のタイミングで行なうようにしても
よい。

【００２６】好ましくは、前記蓄積手段内の仮想コネク
ション識別子の数の減少または増加によって、減少変更
または増加変更を伴う前記第２のレートが決定された場
合、前記第２のレートの減少変更は、前記蓄積手段内の
仮想コネクション識別子の数（例えば、図２のｌｅｎｇ
ｔｈがこれに該当する）が所定のアルゴリズムによって
動的に決定されるしきい値（例えば、図２のｒａｔｅが
これに該当する）より少なくなったときから、該蓄積手
段から次の仮想コネクション識別子が取り出されるとき
までの間の所定のタイミングで行い、前記第２のレート
の増加変更は、最後にその第２のレートを変更したとき
から所定のアルゴリズムで定められた時間（例えば、蓄
積手段内の全ての仮想コネクション識別子が取り出され
る時間のことで、図２ではｃｎｔで決定している）経過
以降の所定のタイミングで行なうようにしてもよい。

【００２７】本発明（請求項６）は、入力したセルを一
旦蓄積した後に送出するセル送出制御装置において、制
御対象となる仮想コネクション（ＶＣ（Ｖｉｒｔｕａｌ
Ｃｏｎｎｅｃｔｉｏｎ））毎のセル送出レートが、定
められた第１のレート（シェイピングレート）を越えな
いように制御するスケジューラ装置であって、制御すべ
き仮想コネクションの仮想コネクション識別子（例え
ば、ＶＣＩ）を蓄積するための少なくとも１つの蓄積手
段（例えば、キュー）と、前記蓄積手段に蓄積されてい
る仮想コネクション識別子を、設定された第２のレート
（例えば、ＳＱＳレートがこれに該当する）で定められ
る時間間隔で順次取り出して、セルを出力すべき仮想コ
ネクションの候補として決定する第１の制御手段と、前
記蓄積手段から取り出された仮想コネクション識別子に
より示される仮想コネクションに依然として（例えばセ
ルを送出した後に）送出待ちセルが存在する場合に、そ
の取り出された仮想コネクション識別子を前記蓄積手段
に再び入れる第２の制御手段と、前記第２のレートを、
前記蓄積手段に蓄積されている仮想コネクション識別子
に対して定められた第１のレートに基づいて（例えば、
蓄積手段内の全ての仮想コネクション識別子の第１のレ
ートの合計に応じて）決定する第３の制御手段とを備え
たことを特徴とする。

【００２８】本発明（請求項７）は、入力したセルを一
旦蓄積した後に送出するセル送出制御装置において、制
御対象となる仮想コネクション（ＶＣ（Ｖｉｒｔｕａｌ
Ｃｏｎｎｅｃｔｉｏｎ））毎のセル送出レートが、定
められた第１のレート（シェイピングレート）を越えな
いように制御するセル送出レート制御方法であって、前
記蓄積手段に蓄積されている仮想コネクション識別子
を、設定された第２のレート（例えば、ＳＱＳレートが
これに該当する）で定められる時間間隔で順次取り出し
て、セルを出力すべき仮想コネクションの候補として決
定し、前記蓄積手段から取り出された仮想コネクション
識別子により示される仮想コネクションに依然として送
出待ちセルが存在する場合に、その取り出された仮想コ
ネクション識別子を前記蓄積手段に再び入れ、前記第２
のレートを、前記蓄積手段に蓄積されている仮想コネク
ション識別子に対して定められた第１のレートに基づい
て（例えば、蓄積手段内の全ての仮想コネクション識別
子の第１のレートの合計に応じて）決定することを特徴
とする。

【００２９】本発明によれば、例えばキューからなる蓄
積手段を用いて仮想コネクション識別子を管理するの
で、使用するメモリ量が必要最小限で済み、仮想コネク
ションの設定や解放に伴う処理が簡潔であり、また一定
の間隔で蓄積手段から仮想コネクション識別子を取り出
すため他のサービスカテゴリのトラヒックをバースト的
にさせることがない。

【００３０】なお、装置に係る本発明は方法に係る発明
としても成立し、方法に係る本発明は装置に係る発明と
しても成立する。また、セル送出装置に係る本発明は、
スケジューラ装置に係る発明としても成立し、スケジュ
ーラ装置に係る本発明は、セル送出装置に係る発明とし
ても成立する。

【００３１】また、装置または方法に係る本発明は、コ
ンピュータに当該発明に相当する手順を実行させるため
の（あるいはコンピュータを当該発明に相当する手段と
して機能させるための、あるいはコンピュータに当該発
明に相当する機能を実現させるための）プログラムを記
録したコンピュータ読取り可能な記録媒体としても成立
する。

【００３２】

【発明の実施の形態】以下、図面を参照しながら本発明
の実施の形態を説明する。本発明は、ＡＴＭ通信方式
や、その他の固定長のパケットを扱うパケット通信方式
に適用可能である。また、可変長のパケットを扱う通信
方式については、全てのパケット長を特定の値にみなす
ことにより、本発明を適用可能である。

【００３３】より具体的には、本発明は、例えば、ネッ
トワークへパケットを送出する端末装置、パケットを中
継するルータ装置、ネットワーク内で仮想コネクション
毎に入力したトラヒックを整形するＡＴＭスイッチ装置
など、種々の装置に適用可能である。

【００３４】以下では、本発明をＡＴＭ通信方式に適用
した場合を例にとって本実施形態を説明する関係上、Ａ
ＴＭ通信における用語である「セル」や「ＶＣ」など用
いるが、「セル」や「ＶＣ」などの用語を「パケット」
や「フロー」など他のパケット通信方式における用語に
置き換えることができる。

【００３５】本発明は、セル（パケット）、ＶＣ（フロ
ー）の定義が何であるかに関わらず有効に作用する。例
えば、ＡＴＭのＶＣには、ＶＰＣ（Ｖｉｒｔｕａｌ Ｐ
ａｔｈ Ｃｏｎｎｅｃｔｉｏｎ）とＶＣＣ（Ｖｉｒｔｕ
ａｌ Ｃｈａｎｎｅｌ Ｃｏｎｎｅｃｔｉｏｎ）が存在
するが、本発明は、ＶＣとしていずれを用いた場合にも
適用可能である。

【００３６】以下、本発明の実施の形態として、本発明
をＡＴＭスイッチに搭載するセル送出装置の構成要素と
してのセルスケジューラに適用した場合について説明す
る。一般に、セル送出装置は、セルを蓄積するバッフ
ァ、バッファに蓄積されているセルの中から出力すべき
セルを絞り込むスケジューラといった要素で構成されて
いるという見方をすることができる（この見方をするの
は単に本発明の有効性をわかりやすく説明するためであ
る）。セルを蓄積するバッファは、例えば図５のように
複数のＶＣ毎キューからなるセル蓄積バッファであり、
この場合、スケジューラは、出力すべきセルのＶＣを選
択するものである。

【００３７】図１に、本発明の一実施形態に係るスケジ
ューラの構成例を模式的に示す。本実施形態に係るスケ
ジューラは、例えば、図５に例示したセル送出装置のス
ケジューラとして適用可能である。

【００３８】このスケジューラは、各ＶＣについて、そ
のセル送出レートが、ある定められた値（これをシェイ
ピングレートと呼ぶ）以上にならないように制御を行
う。本実施形態では、管理する全てのＶＣのシェイピン
グレートが同じである場合を前提とする。

【００３９】図１に示されるように、本スケジューラ
は、概略的には、ＶＣ識別子を蓄積するキュー（以下、
Ｓキュー（Ｓｃｈｅｄｕｌｉｎｇ Ｑｕｅｕｅ）と呼
ぶ）３と、Ｓキュー３に蓄積されているＶＣ識別子を、
後述するＳＱＳレートで順に取り出すＶＣＩデキュー部
（図１にスイッチとして模式的に示す）と、取り出した
ＶＣ識別子をＳキュー３に再度入れるデキュー部（図１
にフィードバックループとして模式的に示す）と、ＳＱ
Ｓレートを制御するＳＱＳレート制御部（図示せず）を
有する。

【００４０】Ｓキュー３はＦＩＦＯであり、これはリン
グバッファやリンクドリストなどの良く知られたＦＩＦ
Ｏ実現手法で実装することができる。Ｓキュー３内のＶ
Ｃ識別子は、設定されたレート（以下、ＳＱＳレート
（ｐｅｒ−Ｓｃｈｅｄｕｌｉｎｇ Ｑｕｅｕｅ Ｓｈａ
ｐｉｎｇ Ｒａｔｅ）と呼ぶ）で順次選択される。選択
されたＶＣ識別子がセルを出力すべきＶＣの候補とな
る。

【００４１】セルを出力すべきＶＣが選択されたなら
ば、そのＶＣ識別子をＳキュー３から取り出すととも
に、そのＶＣからセルが送出されたとしても、なおその
ＶＣに送出待ちのセルが残る場合には、再び、Ｓキュー
３へそのＶＣ識別子を入れる。

【００４２】なお、あるＶＣの最後のセルを出力しその
ＶＣに出力待ちセルがなくなった場合については、Ｓキ
ュー３から取り出したそのＶＣ識別子を、Ｓキュー３へ
再エンキューする方法と再エンキューしない方法がある
が、それらについては後述する。

【００４３】ＳＱＳレートは、各ＶＣに定められたシェ
イピングレートの合計に応じて決定する。Ｓキュー３内
のＶＣ識別子の数を一定とした場合、１つのＳキューで
管理する各ＶＣのシェイピングレートが互いに同じであ
れば、ＳＱＳレートをＶＣ毎のシェイピングレートとＳ
キュー内のＶＣ識別子の数の積に設定すればよい。例え
ば、シェイピングレート１００ｋｂｐｓのＶＣが２０本
あるのであれば、ＳＱＳレートを１００ｋｂｐｓの２０
倍である２Ｍｂｐｓに設定することにより、各ＶＣのシ
ェイピングレートを１００ｋｂｐｓにすることができ
る。

【００４４】以上のような構成にした場合、設定されて
いるＶＣのみがメモリを使用するだけであるので、必要
最小限のメモリ量でスケジューラを実現することができ
る。また、多数のシェイピングすべきＶＣが存在しても
セルが均等に出力されるため、セル出力優先度の低い非
シェイピングセルをバースト的にさせないという利点が
ある。

【００４５】続いて、Ｓキュー３で管理するＶＣ識別子
の数が変化する場合のＳＱＳレートの変更方式の２つの
例についてそれぞれ説明する。第１のＳＱＳレートの変
更方式は、ＳＱＳレートをＶＣの解放／設定の際に変更
する方式である。

【００４６】この方式では、セルを出力すべきＶＣとし
てＳキュー３からＶＣ識別子が取り出された後、そのＶ
Ｃにさらに待ちセルが残っていなくてもそのＶＣ識別子
を必ず元のＳキュー３へ再エンキューする。従って、Ｓ
キュー３内のＶＣ識別子の中には、バッファに出力すべ
きセルが１つも存在しないものも含まれている。セルを
出力すべきＶＣ識別子として選択されたＶＣ識別子に出
力待ちセルが存在しない場合には、代わりの出力可能な
他のＶＣのセルを出力するか、もしくはどのセルも出力
しないようにする。

【００４７】このようにすれば、Ｓキュー３内のＶＣ識
別子の数は、通常、変化しないので、ＳＱＳレートをセ
ル到着やセル送出の度に変更する必要はない。新たにＶ
Ｃの解放または設定があったときのみ、次のように変更
すればよい。

【００４８】設定済みＶＣの解放は、例えばその解放し
たいＶＣ識別子がＳキュー３からデキューされたときを
切っ掛けにして行なう。例えば、ＶＣの設定／解放を管
理する管理装置（図示せず）がＶＣの解放を指示する場
合、その管理装置は解放したいＶＣ識別子と解放後の新
しいＳＱＳレートをセル送出装置側に通知する。新しい
ＳＱＳレートは、通常、解放後のＶＣ識別子の数とＶＣ
毎のシェイピングレートの積である。セル送出装置のス
ケジューラでは、その通知されたＶＣ識別子がＳキュー
３からデキューされたら、そのＶＣ識別子の再エンキュ
ーをとりやめ、同時にＳＱＳレートを通知された新しい
値に切替える。新しいＳＱＳレートは、もとの値よりも
小さくなるはずであるから、そのＳキュー３で管理され
ている残りのＶＣは一時的に送出レートが小さくなるこ
とはあっても、設定されたシェイピングレートを違反し
た大きなレートにはならないことが保証される。なお、
この場合、ＳＱＳレートの通知された新しい値への切替
えは、次のＶＣ識別子を取り出すまでの間の所定のタイ
ミングで行ってもよい。

【００４９】新しいＶＣの設定は、例えばＶＣの設定を
指示する管理装置が、設定したいＶＣ識別子と設定後の
新しいＳＱＳレートをセル送出装置側へ通知するように
する。新しいＳＱＳレートは、通常、設定後のＶＣ識別
子の数とＶＣ毎のシェイピングレートの積である。セル
送出装置のスケジューラでは、その新しいＶＣ識別子を
直ちにＳキューへエンキューしてよい。ただし、ＳＱＳ
レートを新しい値に変更するのは、エンキューした新し
いＶＣ識別子がＳキュー３からデキューしたときを切っ
掛けにして行なう。これは、新しいＳＱＳレートがもと
の値よりも大きいため、エンキュー直後に変更してしま
うとＶＣ毎のシェイピングレートが設定値を違反してし
まうからである。このように、新しくエンキューしたＶ
Ｃ識別子がＳキュー３内を一巡りしてデキューされたと
きを切っ掛けにＳＱＳレートを変更することで、ＶＣの
シェイピングレート違反が発生しないことを保証するこ
とができる。

【００５０】なお、上記では新しいＳＱＳレートを管理
装置側で求め、これをセル送出装置側に通知するように
したが、セル送出装置側で新しいＳＱＳレートを求める
ようにしてもよい。

【００５１】第２のＳＱＳレートの変更方式は、ＶＣの
解放／設定ではなく、実際に、あるＶＣ毎バッファが空
になったことや、ある空のＶＣ毎バッファにセルがエン
キューされたことに応答してＳＱＳレートを変更する方
式である。

【００５２】この方式の場合、Ｓキュー３で管理するＶ
Ｃ識別子は、実際にバッファに出力待ちのセルが存在す
るＶＣだけになる。すなわち、あるＶＣの最後のセルを
出力しそのＶＣに出力待ちセルがなくなったとき、つま
りＶＣがアイドルになったときは、そのＶＣ識別子のＳ
キュー３への再エンキューをやめる。一方、出力待ちセ
ルがないＶＣにセルが到着したとき、つまりＶＣがアク
ティブになったときは、Ｓキューへ新しくそのＶＣ識別
子をエンキューする。本方式では、これら各ＶＣのアイ
ドルとアクティブとの間の変化に応じてＳＱＳレートを
変更させるものである。

【００５３】また、本方式では、各ＶＣのシェイピング
レートが設定値を越えないようにするために、変更のタ
イミングを後述するように工夫している。図２に、Ｓキ
ューからＶＣ識別子がデキューされる度に実行される、
ＳＱＳレート変更のアルゴリズムを示す。

【００５４】アルゴリズム中、ｌｅｎｇｔｈはデキュー
処理後のＳキュー内のＶＣ識別子の数、ｔｍｐ、ｒａｔ
ｅはｌｅｎｇｔｈを一時的に記憶した値、ｃｎｔはＳＱ
Ｓレートを変更するタイミングを決定するカウンタであ
る。

【００５５】ＳＱＳレートは、ｒａｔｅとＶＣ毎に設定
されたシェイピングレートを乗じた値である。ただし、
ｒａｔｅが０の場合には、ｒａｔｅを０以外の値、例え
ば１に置き換え、ＶＣ毎に設定されたシェイピングレー
トを乗じた値とする。ｔｅｍｐとｒａｔｅの初期値は
０、ｃｎｔの初期値は１である。

【００５６】まず、ｃｎｔをデクリメントし（ステップ
Ｓ１）、ｌｅｎｇｔｈがｒａｔｅよりも小さいかどうか
を検査する（ステップＳ２）。もしいくつかのＶＣがア
イドルになり、ｌｅｎｇｔｈがｒａｔｅよりも小さくな
っていたならば、ｔｍｐの値をｌｅｎｇｔｈの値と同じ
に設定するとともに、ｒａｔｅもｌｅｎｇｔｈと同じ値
に下げ、また、ｃｎｔをｌｅｎｇｔｈに初期化する（ス
テップＳ３）。ｒａｔｅが下がることによりＳＱＳレー
トは小さくなる。

【００５７】もしステップＳ２にてｌｅｎｇｔｈがｒａ
ｔｅ以上であれば、次にｌｅｎｇｔｈがｔｍｐよりも小
さいかどうかを検査する（ステップＳ４）。もしｌｅｎ
ｇｔｈがｔｍｐよりも小さいならば、ｔｍｐ値をｌｅｎ
ｇｔｈの値と同じに下げ、ｃｎｔをｌｅｎｇｔｈに初期
化する（ステップＳ５）。

【００５８】さらにステップＳ４にてｌｅｎｇｔｈがｔ
ｍｐ以上であれば、ステップＳ１にてｃｎｔをデクリメ
ントした結果を検査し（ステップＳ６）、ｃｎｔが０以
下になっていたならば、すなわちカウンタで決定する期
間が満了したならば、ｒａｔｅにｔｍｐを代入し、ｔｍ
ｐにｌｅｎｇｔｈを代入し、さらにｃｎｔをｌｅｎｇｔ
ｈに初期化する（ステップＳ７）。

【００５９】図２のアルゴリズムでは、ｒａｔｅ（ＳＱ
Ｓレートの元のデータ）を大きな値（ｔｍｐ）に変更す
る操作（ステップＳ７）は、ｃｎｔで決定される周期で
変更を行なう。これによって、図２のアルゴリズムは、
過去の１周期間、ｌｅｎｇｔｈがｒａｔｅ以上かつｔｍ
ｐ以上であることを保証している。つまり、その後の１
周期にデキューするいずれのＶＣ識別子についても、そ
れがエンキューされたときは、Ｓキューの長さがｒａｔ
ｅ以上かつｔｍｐ以上あったということである。過去の
１周期間のＳＱＳレートがｒａｔｅで決定され、その後
の１周期間のＳＱＳレートがｔｍｐで決定されることを
考え合わせると、Ｓキューで管理する全てのＶＣで設定
されたシェイピングレートを違反していないことを保証
することができる。

【００６０】なお、図２のアルゴリズムで決定されるＳ
ＱＳレートの変更タイミングよりも以降にＳＱＳレート
の増加変更を行うようにした場合でも、Ｓキューで管理
する全てのＶＣで設定されたシェイピングレートを違反
していないことを保証することができる。

【００６１】逆に、ｒａｔｅを小さな値に変更する操作
（ステップＳ３）は、ｌｅｎｇｔｈが小さくなったこと
を発見した段階（ステップＳ２）で直ちに行なうこと
で、設定されたシェイピングレートを違反しないことを
保証する。

【００６２】なお、上記の代わりに、ｌｅｎｇｔｈがｒ
ａｔｅよりも小さくなった時点から、次にそのＳキュー
によりセルが送出される時点（すなわちそのＳキューか
ら次のＶＣ識別子がデキューされる時点）までの間の所
定のタイミングで行うようにしても、設定されたシェイ
ピングレートを違反しないことを保証することができ
る。例えば、図３に示すようにＡ、Ｂ、Ｃ、Ｄの４つの
ＶＣ識別子から識別子Ｄがデキューされ再エンキューさ
れない場合、（ａ）に示すように即座にレートを変更し
てもレート違反は生ずることはなく、また（ｂ）に示す
ように次の識別子Ａの出力タイミングで変更すると、ち
ょうどシェイピングレートで出力されるが、（ｃ）に示
すように次の次の識別子Ｂの出力タイミングで変更する
と、識別子Ａのデキューの間隔がシェイピングレートで
規定される間隔よりも短くなり、レート違反が生ずる。

【００６３】以上のように、ＳキューのＳＱＳレートの
各設定方法では、Ｓキューで管理されているＶＣ識別子
の数の変化にともないＳキューのＳＱＳレートを変更す
るが、いずれの方法を用いても、各ＶＣのセル送出レー
トがＶＣ毎に定められたシェイピングレートを越えてし
まうことがない。

【００６４】また、本実施形態によれば、ＶＣの設定や
解放手順は、Ｓキューのエンキュー、デキュー操作を行
なうことで容易に行うことができる。また、ＳＱＳレー
トの計算も単純なアルゴリズムで実現可能である。

【００６５】以上説明してきたように、本実施形態によ
れば、Ｓキューを用いてＶＣＩを管理するので、必要最
小限のメモリ量で実現でき、仮想コネクションの設定や
解放に伴う処理が簡潔であり、また一定の間隔でキュー
からＶＣＩを取り出すためシェイピングを行なわない他
のトラヒックをバースト的にさせないようにすることが
できる。

【００６６】さて、これまでの説明では、１つのセル送
出装置で管理するＶＣは全て同じシェイピングレートが
設定されているとしたが、本発明によれば、２以上の異
なるシェイピングレートを扱うことも可能である。

【００６７】そのための方法としては、あるＶＣのＶＣ
識別子を１つのＳキューに複数個エンキューする方法が
考えられる。Ｓキューに同じＶＣ識別子をＮ個エンキュ
ーすると、１個しかエンキューしていないＶＣのシェイ
ピングレートのＮ倍の送出レートでセルを送出すること
ができる。

【００６８】この方法では、もしＮ個のＶＣ識別子間の
間隔を制御できなければ、設定したシェイピングレート
を越えてセルが出力されることがある。しかし、それは
最大でＮ−１セルと上限値が明確であり、このセル流を
受信する装置の遅延揺らぎ許容範囲内なら問題は生じな
い。

【００６９】また、他の方法として、シェイピングレー
トの種類に応じた複数のＳキューを並列に動作させる方
法も考えられる。また、この方法は、上記した同一ＶＣ
識別子を１つのＳキューに複数個エンキューする方法と
組み合わせることもできる。

【００７０】図４に、シェイピングレートの種類に応じ
た複数のＳキューを並列に動作させるようにしたセル送
出装置の一例を示す。このセル送出装置は、セルをＶＣ
毎に蓄積するバッファ（キュー）２１と、セルを出力す
べきＶＣを選択するスケジューラ２３と、スケジューラ
の指示に従っていずれかのバッファ（キュー）からセル
を取り出して出力するセレクタ２２とを有する。

【００７１】スケジューラ２３は、複数のＳキュー（３
３−１〜３３−ｎ）、非シェイピングＶＣスケジューラ
３５、選択部３６を持つ。複数種類のシェイピングレー
トを扱う場合には、そのシェイピングレートの種類に応
じて複数のＳキューを用意する。各Ｓキューはそれぞれ
に設定されたＳＱＳレートでＶＣ識別子を出力すべきＶ
Ｃの候補として選択する。複数の候補が存在する場合に
は、選択部３６がその中から適当にＶＣ識別子を選び、
セルを出力すべきＶＣとしてセルバッファへ伝える。

【００７２】もしいずれのＳキューも候補となるＶＣ識
別子を選択していなかった場合には、非シェイピングＶ
Ｃスケジューラ３５が選択したＶＣ識別子を出力すべき
ＶＣとする。

【００７３】なお、図４のＳキューの一部または全部
が、同一ＶＣ識別子をそのＳキューに複数個エンキュー
することを可能とするものであってもよい。なお、以上
の各機能は、ソフトウェアとしても実現可能である。

【００７４】また、本実施形態は、コンピュータに所定
の手順を実行させるための（あるいはコンピュータを所
定の手段として機能させるための、あるいはコンピュー
タに所定の機能を実現させるための）プログラムを記録
したコンピュータ読取り可能な記録媒体として実施する
こともできる。本発明は、上述した実施の形態に限定さ
れるものではなく、その技術的範囲において種々変形し
て実施することができる。

【００７５】

【発明の効果】本発明によれば、キューを用いてＶＣＩ
を管理するので、使用するメモリ量が必要最小限で済
み、ＶＣの設定や解放に伴う処理が簡潔であり、また一
定の間隔でキューからＶＣＩを取り出すため他のサービ
スカテゴリのトラヒックをバースト的にさせないように
することができる。

【図面の簡単な説明】

【図１】本発明の一実施形態に係るスケジューラの構成
例を説明するための図

【図２】同実施形態におけるＳＱＳレート変更手順の一
例を示すフローチャート

【図３】ＳＱＳレートを減少変更するタイミングについ
て説明するための図

【図４】同実施形態に係るセル送出装置の構成例を示す
図

【図５】一般的なセル送出装置の構成例を示すブロック
図

【図６】従来のスケジューラの一構成例を示す図

【図７】従来のスケジューラの他の構成例を示す図

【符号の説明】

３，３３−１，３３−２，３３−ｎ…Ｓキュー ４…出力部 １１，２１…ＶＣ毎キュー １２，２２…セレクタ １３，２３…スケジューラ ３５…非シェイピングＶＣスケジューラ ３６…選択部

Claims (7)

【特許請求の範囲】
1. 【請求項１】仮想コネクション毎のセル送出レートが、
   定められた第１のレートを越えないように制御するセル
   送出装置であって、 制御すべき仮想コネクションの仮想コネクション識別子
   を蓄積するための少なくとも１つの蓄積手段と、 前記蓄積手段に蓄積されている仮想コネクション識別子
   を、設定された第２のレートで定められる時間間隔で順
   次取り出して、セルを出力すべき仮想コネクションの候
   補として決定する第１の制御手段と、 前記蓄積手段から取り出された仮想コネクション識別子
   により示される仮想コネクションに依然として送出待ち
   セルが存在する場合に、その取り出された仮想コネクシ
   ョン識別子を前記蓄積手段に再び入れる第２の制御手段
   と、 前記第２のレートを、前記蓄積手段に蓄積されている仮
   想コネクション識別子に対して定められた第１のレート
   に基づいて決定する第３の制御手段とを備えたことを特
   徴とするセル送出装置。
2. 【請求項２】前記第２の制御手段は、前記仮想コネクシ
   ョンの解放前は、前記蓄積手段から取り出された仮想コ
   ネクション識別子により示される仮想コネクションに送
   出待ちセルが存在しなくなった場合にも、その取り出さ
   れた仮想コネクション識別子を前記蓄積手段に再び入れ
   る手段を含むことを特徴とする請求項１に記載のセル送
   出装置。
3. 【請求項３】前記蓄積手段内の仮想コネクション識別子
   の数の減少または増加によって減少変更または増加変更
   を伴う前記第２のレートが決定された場合に、前記第２
   のレートの設定値をその新たに決定された値に変更させ
   るタイミングを制御することによって、該蓄積手段によ
   りセル送出を制御している各仮想コネクションに対して
   セル送出レートが第１のレートを越えないことを保証す
   ることを特徴とする請求項１に記載のセル送出装置。
4. 【請求項４】前記蓄積手段内の仮想コネクション識別子
   の数の減少または増加によって、減少変更または増加変
   更を伴う前記第２のレートが決定された場合、 前記第２のレートの減少変更は、減少変更を伴う第２の
   レートを決定させるもとになった仮想コネクション識別
   子が前記蓄積手段から取り出されたときから、該蓄積手
   段から次の仮想コネクション識別子が取り出されるとき
   までの間の所定のタイミングで行い、 前記第２のレートの増加変更は、増加変更を伴う第２の
   レートを決定させるもとになった仮想コネクション識別
   子が前記蓄積手段に入れられたときに該蓄積手段に蓄積
   されていた個数の仮想コネクション識別子が該蓄積手段
   から取り出されたとき以降の所定のタイミングで行なう
   ことを特徴とする請求項１に記載のセル送出装置。
5. 【請求項５】前記蓄積手段内の仮想コネクション識別子
   の数の減少または増加によって、減少変更または増加変
   更を伴う前記第２のレートが決定された場合、 前記第２のレートの減少変更は、前記蓄積手段内の仮想
   コネクション識別子の数が所定のアルゴリズムによって
   動的に決定されるしきい値より少なくなったときから、
   該蓄積手段から次の仮想コネクション識別子が取り出さ
   れるときまでの間の所定のタイミングで行い、 前記第２のレートの増加変更は、最後にその第２のレー
   トを変更したときから所定のアルゴリズムで定められた
   時間経過以降の所定のタイミングで行なうことを特徴と
   する請求項１に記載のセル送出装置。
6. 【請求項６】入力したセルを一旦蓄積した後に送出する
   セル送出制御装置において、制御対象となる仮想コネク
   ション毎のセル送出レートが、定められた第１のレート
   を越えないように制御するスケジューラ装置であって、 制御すべき仮想コネクションの仮想コネクション識別子
   を蓄積するための少なくとも１つの蓄積手段と、 前記蓄積手段に蓄積されている仮想コネクション識別子
   を、設定された第２のレートで定められる時間間隔で順
   次取り出して、セルを出力すべき仮想コネクションの候
   補として決定する第１の制御手段と、 前記蓄積手段から取り出された仮想コネクション識別子
   により示される仮想コネクションに依然として送出待ち
   セルが存在する場合に、その取り出された仮想コネクシ
   ョン識別子を前記蓄積手段に再び入れる第２の制御手段
   と、 前記第２のレートを、前記蓄積手段に蓄積されている仮
   想コネクション識別子に対して定められた第１のレート
   に基づいて決定する第３の制御手段とを備えたことを特
   徴とするスケジューラ装置。
7. 【請求項７】入力したセルを一旦蓄積した後に送出する
   セル送出制御装置において、制御対象となる仮想コネク
   ション毎のセル送出レートが、定められた第１のレート
   を越えないように制御するセル送出レート制御方法であ
   って、 前記蓄積手段に蓄積されている仮想コネクション識別子
   を、設定された第２のレートで定められる時間間隔で順
   次取り出して、セルを出力すべき仮想コネクションの候
   補として決定し、 前記蓄積手段から取り出された仮想コネクション識別子
   により示される仮想コネクションに依然として送出待ち
   セルが存在する場合に、その取り出された仮想コネクシ
   ョン識別子を前記蓄積手段に再び入れ、 前記第２のレートを、前記蓄積手段に蓄積されている仮
   想コネクション識別子に対して定められた第１のレート
   に基づいて決定することを特徴とする送出レート制御方
   法。