JP3028985B2

JP3028985B2 - セル流量制御装置

Info

Publication number: JP3028985B2
Application number: JP29143591A
Authority: JP
Inventors: 和昭岩村; 康郎正畑; 良成熊木
Original assignee: Toshiba Corp
Current assignee: Toshiba Corp
Priority date: 1991-11-07
Filing date: 1991-11-07
Publication date: 2000-04-04
Anticipated expiration: 2015-04-04
Also published as: JPH05130125A

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、ＡＴＭ交換方式におけ
るセル流量制御装置に関する。

【０００２】

【従来の技術】近年、高速かつ広帯域なＢ−ＩＳＤＮ網
等を実現する網アーキテクチャとしてのＡＴＭ（Asynch
ronous Transfer Mode）交換方式が注目されており、こ
のＡＴＭ交換方式は、固定長で区切られた情報毎にルー
ティング情報等を示すヘッダを付与したセルを情報単位
として伝送路上でラベル多重し、交換ノードではこのヘ
ッダの情報のみを参照してセル単位で交換動作を行うも
のである。また、このＡＴＭ交換方式は、旧来の回線交
換方式とは異なり各通信に固定の通信帯域を割り当てる
ことは無く、複数の通信が単一の通信帯域を共有して通
信を行うようにしている。

【０００３】このＡＴＭ交換を利用して、通信を開始す
るときは、発端末とＡＴＭ交換網との間で必要なトラヒ
ック特性と通信品質との取り決めを行い、ＡＴＭ交換網
では申告されたトラヒック特性をもったセル流が流入し
た場合に要求された通信品質を提供できるか否かを判定
し、要求された通信品質を提供できると判定されたとき
には着端末との間に仮想チャネルＶＣ（Virtual Chane
l）を設定し、セルの転送が発端末と着端末との間で行
われる。前述したように、この仮想チャネルＶＣには固
定の通信帯域が割り当てられるわけではないので、事前
に定められた以上のセル流を発生すると、定められた通
信品質を提供できない。そのため、ＡＴＭ交換網におい
ては、各仮想チャネルＶＣのトラヒック特性が申告され
た特性を満たしているかどうかを監視するポリシング機
能が必要となり、端末においても発生するトラヒックを
申告した通りの特性で出力するためのシェイピング機能
が必要となる。

【０００４】この様なセル流の監視、制御を行う方式と
してはリーキパケットを用いた方式が知られている（J.
S.Turner,"New Directions in Communications",pp8-1
5,IEEE Communications Magazine,vol.24,No.10,Octobe
r 1986 ）。従来のリーキバケットの構成例を図１１に
示す。

【０００５】図１６において、到着監視部１０１はセル
の到着を検出すると、ＡＮＤ回路１０３を介して、カウ
ンタ１０５をインクリメントする。このとき、ＡＮＤ回
路１０３の他側には比較器１１５からの出力が入力され
る。また、単位時間周期のクロックを発生するクロック
１０７から出力されるクロック信号でカウンタ１０９を
インクリメントし、このカウンタ１０９の値Ａと一定値
Ｔを記憶するレジスタ１１１の出力、閾値Ｂとを比較器
１１３において比較し、一致した場合（Ａ＝Ｂ）にカウ
ンタ１０５を１だけデクリメントすると共にカウンタ１
０９をリセットする。なお、カウンタ１０５の値が０で
ある場合には、比較器１１３においてＡ＝Ｂとなった場
合にもそれ以上カウンタ１０５の値をデクリメントしな
い。

【０００６】また、同時にカウンタ１０５の値を比較器
１１５に出力し、このカウンタ１０５の値Ａとレジスタ
１１７からの出力Ｂとを比較し、一致しているとき（Ａ
＝Ｂ）に到着したセルを違反と判定し、到着監視部１０
１において廃棄する。

【０００７】上述したように、ＡＴＭ交換網では一つの
回線上には複数の仮想チャネルＶＣが多重化されること
があり、各仮想チャネルＶＣに対してセル流の監視を独
立に行わなければならない。しかし、各仮想チャネルＶ
Ｃのパラメータは必ずしも等しい値を持たないので、時
間周期の測定などは独立に行う必要がある。このような
複数の仮想チャネルＶＣを監視するためには、図１６に
示したリーキバケットをセル流の監視を行う仮想チャネ
ル数だけ用意して、かつ並行して動作させることで実現
できる。しかしながら、ハードウェア量が仮想チャネル
ＶＣ数に比例して増加するため、多数の仮想チャネルＶ
Ｃが多重化される場合の流量制御装置が非常に大規模に
なる。そこで、ハードウェア量を低減させるために、カ
ウンタの値などをメモリ上に記憶し、一つの演算装置を
複数の仮想チャネルＶＣで共用して、メモリに記憶され
ている値を更新してリーキバケットを実現する構成も考
えられるが、メモリのアクセス速度、演算装置の処理能
力などの制約によって、監視を行うことができる仮想チ
ャネルＶＣ数が制限され、多数の仮想チャネルＶＣを監
視することができない。従って、このような構成を用い
ても仮想チャネルＶＣ数が大なるときには、複数の装置
を並列に動作させなければならず、この場合にもハード
ウェア量が増加してしまう。

【０００８】また、違反と判定された場合に、この違反
と判定されたセルを廃棄せずに、出力されても違反とな
らない時刻までバッファに蓄積してから出力する制御も
ある。例えば、本出願人によって先に出願されている特
願平２−２１７２１６に述べられているように、従来は
バッファからセルを出力する度に、蓄積されているセル
のそれぞれが違反となるか否かを調べて、出力可能であ
るセルを捜して出力する構成がとられていた。しかし、
この様な構成では、上述のリーキバケット実現に大きな
ハードウェアが必要であることに加えて、出力可能なセ
ルを捜すために必要な処理量が大きくなる。

【０００９】

【発明が解決しようとする課題】上述したように、従来
は、多重化されている仮想チャネルＶＣのセル流を監視
するセル流量制御装置は、仮想チャネルＶＣ数が大きい
とき、ハードウェア量が増大して実現が困難である。さ
らに、違反ではなくなるまでの間、バッファに蓄積して
出力する場合には、出力されるセルを決定するための処
理量が大きくなり、処理時間の増大を招来するところと
なった。

【００１０】本発明は、以上のような状況に鑑みてなさ
れたものであり、対象となる仮想チャネルＶＣ数が大き
い場合でも、仮想チャネルＶＣ数に比例したハードウェ
ア量を必要とすることのないセル流量制御装置を実現す
るものである。

【００１１】

【課題を解決するための手段】上記目的を達成するため
に、本発明の第一の特徴は、複数の仮想チャネルが多重
化された伝送路上のセル流を制御するセル流量制御装置
において、仮想チャネルのそれぞれに対して任意に設定
される始点からの経過時間を計測する経過時間計測手段
と、仮想チャネルのそれぞれに対して、到着セルの流量
に関する値を保持する記憶手段と、新たなセルが到着し
たときに、セルが属する仮想チャネルに対する記憶手段
の値を、経過時間計測手段によって得られる現在の時刻
までの経過時間に基づいて更新する演算手段と、演算手
段により更新された記憶手段の値に基づいてセルの転送
制御を行う制御手段とを具備し、経過時間計測手段は、
仮想チャネル毎に設けられた、Ｎセル周期毎にＮ増加す
る第一のカウンタと、１セル周期毎に１増加する第二の
カウンタとを有し、仮想チャネルを経由してセルが到着
した場合、仮想チャネルに対応する第一のカウンタ値
と、第二のカウンタ値とを用いて経過時間を計測するセ
ル流量制御装置であることにある。

【００１２】また、本発明の第二の特徴は、複数の仮想
チャネルが多重化された伝送路上のセル流を制御するセ
ル流量制御装置において、仮想チャネルのそれぞれに対
して、ある時点までに到着して時点でバッファに保持さ
れている一つ以上のセルをバッファから出力し終わるま
でにかかるはずの時間である、残りサービス時間を記憶
する手段と、新たなセルが到着したときに、セルが属す
る仮想チャネルの一つ前のセルが到着した時刻から現在
時刻までの経過時間を求める手段と、経過時間を残りサ
ービス時間から減じた値に仮想チャネルのセルのサービ
ス時間を加えた値に基づいて、セルの転送制御を行う手
段とを具備するセル流量制御装置であることにある。

【００１３】

【作用】本願第１の発明によれば、任意の時点におい
て、任意に設定される始点、例えば直前のセルが到着し
てから、あるいはメモリから読み出したときからの経過
時間を知る経過時間計測手段を持つことによって、セル
が到着した時に一括して記憶手段の値を更新することが
可能となるので、同時に複数の仮想チャネルＶＣの情報
をアクセスする必要がなく、仮想チャネルＶＣ数に関わ
りなく仮想チャネルＶＣ毎に必要な値をメモリ上に蓄積
し、単一の演算手段をもちいて監視を行うことが可能と
なる。これによって、仮想チャネルＶＣが大なる場合に
おいてもセル流量制御装置を構成するために必要なハー
ドウェア量を大きく低下することが可能である。

【００１４】また、本願第２の発明によれば、セル入力
時にセルの出力が可能となる時刻を求め、この時刻以降
で最初に予約されていない時刻にセルの出力を予約し、
予約された時刻にセルを出力することで、出力時にはバ
ッファ内のセルの出力可否の判定を行わずに、定められ
た特性でセルの出力を行うことが可能となる。

【００１５】

【実施例】以下、本発明の一実施例を図面を参照して説
明する。図１は本発明の第１の実施例におけるセル流量
制御装置１の構成を示すブロック図である。

【００１６】まず、図１を参照して本実施例のセル流量
制御装置１の構成を説明する。このセル流量制御装置１
は、入回線上に多重化されたＮチャネルの仮想チャネル
のセル流量の流量監視を行うもので、制御手段としての
転送制御部１１、演算手段としての演算部１３、メモリ
１５、クロック１７及び経過時間計測手段としてのカウ
ンタ７によって構成される。尚、このＮチャネルの仮想
チャネルには予め０から（Ｎ−１）までの仮想チャネル
番号が付与されているものとする。

【００１７】転送制御部１１は、入回線から入力される
セルのヘッダ情報から仮想チャネル番号を識別し、この
転送制御部１１に接続される演算部１３に仮想チャネル
番号を通知するものである。

【００１８】演算部１３は、転送制御部１１から通知さ
れた仮想チャネル番号をもとにしてメモリ１５に記憶さ
れている当該仮想チャネルに対応する情報を読みだし、
この情報に基づく判定結果を転送制御部１１に通知す
る。この演算部１３における判定結果が違反セルである
とき、転送制御部１１は当該入力セルを廃棄する。ま
た、違反セルではないと判定されたときには、当該入力
セルは出回線に出力される。

【００１９】クロック１７はセル周期の信号を発生し、
カウンタ１９はクロック１７の発生する信号によって動
作するＮ進のカウンタである。すなわち、カウンタ１９
の値が（Ｎ−１）であるとき、次のクロックが入力され
るとカウンタ１９の値が０となる。ただし、セル周期は
入回線もしくは出回線上で１セルの転送に要する時間を
示すものとする。

【００２０】次に、セル流量制御装置１の作用を説明す
る。本来のリーキバケットでは、従来の技術の欄で説明
したように、セルが到着すると１だけインクリメントさ
れ、一定時間Ｔ毎に１だけデクリメントされるカウンタ
を持ち、このカウンタの値がしきい値Ｂ以上である時に
到着したセルが違反セルと判定されるものである。

【００２１】このカウンタ１９の値は、１セルのサービ
ス時間がＴである待ち行列システムのキュー長を示して
いると見なすことができ、従ってリーキバケットにおけ
る判定は、この待ち行列システムのシステム内セル数が
（Ｂ−１）以下である場合に違反ではないと判定するこ
とに等しい。この待ち行列システムにおいて、サービス
中のセルが出力されるまでの残り時間と、待ち行列に並
んでいるセルが必要とするサービス時間との合計を残り
サービス時間ＣＴＲ１としたとき、システム内セル数が
（Ｂ−１）以下であるという条件は、

【数１】ＣＴＲ１≦ＴＨ（１）ただし、閾値ＴＨ＝Ｔ×（Ｂ−１）と書ける。

【００２２】また、図２に示すように、新たなセルが到
着した時の残りサービス時間ＣＴＲ１_newは、一つ前の
セルが到着した時点での残りサービス時間ＣＴＲ１_old
と到着時間間隔ΔＴによって

【数２】ＣＴＲ１_mew＝ｍａｘ（ＣＴＲ１_old＋Ｔ−ΔＴ，０）（２）となるので、残りサービス時間ＣＴＲ１_oldと到着時間
間隔ΔＴが分かれば、上述の式を用いて求められる残り
サービス時間ＣＴＲ１_newと閾値ＴＨとを比較して、入
力セルの違反判定を行うことができる。

【００２３】以下、到着時間間隔ΔＴの算出に付いて説
明する。ここでは、カウンタ１９を用いて到着時間間隔
ΔＴを求めるために、仮想チャネルＶＣ毎にセル到着時
刻ＰＨＳと経過時間カウンタＣＴＲ２を用いる。

【００２４】入回線を介して、新たなセルが到着すると
セル到着時刻ＰＨＳにはその時点でのカウンタ１９の値
がセットされる。経過時間カウンタＣＴＲ２は、セルが
到着すると０にリセットされ、カウンタ１９が仮想チャ
ネルＶＣに定められた値を示す度に仮想チャネルのチャ
ネル数に等しい値Ｎが加えられる。ここでは、チャネル
Ｊの経過時間カウンタＣＴＲ２はカウンタ１９の値がＪ
となったときに増加されるものとする。経過時間カウン
タＣＴＲ２の値を、このように更新することによって、
各セル周期には１つの仮想チャネルの経過時間カウンタ
ＣＴＲ２だけを増加すれば良くなる。

【００２５】経過時間カウンタＣＴＲ２は、Ｎセル周期
ごとにしか増加されないため、正確なセルの到着間隔を
示していないが、前のセルが到着したときのカウンタ１
９の値を記憶しているセル到着時刻ＰＨＳと現在のカウ
ンタ１９の値ＣＬＫを用いると正確な到着時間間隔ΔＴ
を求めることができる。

【００２６】到着時間間隔ΔＴと経過時間カウンタＣＴ
Ｒ２、セル到着時刻ＰＨＳおよびカウンタ１９の値ＣＬ
Ｋとの関係は、セル到着時刻ＰＨＳと経過時間カウンタ
ＣＴＲ２がＮ増加されるときのカウンタ１９の値Ｊの関
係と、現在のカウンタ１９の値ＣＬＫとＪの関係によっ
て場合分けされ、以下の式（３−１），（３−２），
（３−３）で到着時間間隔ΔＴは与えられる。図３にこ
の様子を示す。

【００２７】すなわち、図３(3) 及び(1) の場合は、ＰＨＳ（Ｊ）≧Ｊ，ＣＬＫ≧ＪまたはＰＨＳ（Ｊ）＜Ｊ，ＣＬＫ＜Ｊの時の到着時間間隔ΔＴ
が、

【数３】 ΔＴ＝ＣＴＲ２（Ｊ）＋ＣＬＫ−ＰＨＳ（Ｊ）（３−１）で与えられ、図３(2) の場合は、ＰＨＳ（Ｊ）＜Ｊ，ＣＬＫ≧Ｊの時の到着時間間隔ΔＴ
が、

【数４】 ΔＴ＝ＣＴＲ２（Ｊ）＋ＣＬＫ−ＰＨＳ（Ｊ）−Ｎ（３−２）で与えられ、図３(4) の場合は、ＰＨＳ（Ｊ）≧Ｊ，ＣＬＫ＜Ｊの時の到着時間間隔ΔＴ
が、

【数５】 ΔＴ＝ＣＴＲ２（Ｊ）＋ＣＬＫ−ＰＨＳ（Ｊ）＋Ｎ（３−３）で与えられることを、それぞれ示すものである。

【００２８】また、カウンタ１９の周期を、監視するチ
ャネル数Ｎと等しくしているので、各セル周期には１つ
の仮想チャネルＶＣの経過時間カウンタＣＴＲ２を増加
すれば良い。

【００２９】以上述べたアルゴリズムを実現するため
に、メモリ１５は図４に示される構成の情報を有する。
すなわち、チャネル０からチャネル（Ｎ−１）のＮ個の
仮想チャネルのそれぞれに、残りサービス時間ＣＴＲ１
（０），〜，（Ｊ），〜，（Ｎ−１）、しきい値ＴＨ
（０），〜，（Ｊ），〜，（Ｎ−１）、１セルのサービ
ス時間Ｔ（０），〜，（Ｊ），〜，（Ｎ−１）、セル到
着時刻ＰＨＳ（０），〜，（Ｊ），〜，（Ｎ−１）、経
過時間カウンタＣＴＲ２（０），〜，（Ｊ），〜，（Ｎ
−１）をテーブルとして持つ。ここでＪは対応する仮想
チャネル番号を示す。

【００３０】セル到着時刻ＰＨＳ（Ｊ）、経過時間カウ
ンタＣＴＲ２（Ｊ）はこの仮想チャネルにおいて直前に
セルが入力されてらかの経過時間を求めるために用いら
れ、残りの値によってリーキバケットを構成する。

【００３１】次に、図５に示すフローチャートを参照し
て、各セル周期でのセル流量制御装置１の作用を説明す
る。以下、入回線を介して仮想チャネル番号Ｊのセルが
入力され、このセルの仮想チャネル番号が転送制御部１
１において当該セルのヘッダ情報から識別される場合を
例に説明する。

【００３２】まず、セル周期の初めにステップＳ１１に
おいて、後段のステップでのΔＴの算出を可能にするた
めに、予めカウンタ１９の値ＣＬＫに等しい仮想チャネ
ル番号の経過時間カウンタＣＴＲ２の値に仮想チャネル
のチャネル数に等しい値Ｎを加えておく。

【００３３】また、ΔＴは（ＣＴＲ１＋Ｔ）より大きい
場合には、後述する動作はΔＴの値に影響されないの
で、ＣＴＲ２が適当な閾値以上である時にはＮを加えな
いようにすることで、ＣＴＲ２がオーバフローを生じる
ことがないようにすることができる。さらに、ＣＴＲ２
にはカウンタ１９の値が仮想チャネル番号に等しくなっ
た回数だけを記憶するようにして、必要なときにこれを
Ｎ倍して用いる構成も可能である。

【００３４】次に、ステップＳ１３において、セルの入
力がなければ（ＮＯ）、このセル周期での動作を終了す
る。一方、入回線を介してセルが入力された場合（ＹＥ
Ｓ）には、ステップＳ１５に進み、この入力され到着し
たセルの仮想チャネル番号Ｊに対応するセル到着時刻Ｐ
ＨＳ（Ｊ）の値と仮想チャネル番号とを比較する。ここ
で、ＰＨＳ（Ｊ）≧Ｊならば、ステップＳ１７に進む。
このとき、図３に示す(3) 、(4) が選択されたことにな
る。また、ＰＨＳ（Ｊ）＜Ｊならば、ステップＳ１９に
進む。このとき図３に示す(1) 、(2) が選択されたこと
になる。

【００３５】次にステップＳ１７，Ｓ１９において、仮
想チャネル番号Ｊとカウンタ１９の値ＣＬＫとの比較を
行う。ステップＳ１７で、ＣＬＫ≧Ｊならば、ステップ
Ｓ２３に進み、ＣＬＫ＜Ｊならば、ステップＳ２１に進
む。このとき、ステップＳ２３は図３(3) に対応する式
（３−１）が、ステップＳ２１は同(4) に対応する式
（３−３）がそれぞれ選択されたことになる。

【００３６】一方、ステップＳ１９で、ＣＬＫ≧Ｊなら
ば、ステップＳ２５に進み、ＣＬＫ＜Ｊならば、ステッ
プＳ２３に進む。このとき、ステップＳ２５は図３(2)
に対応する式（３−２）が、ステップＳ２３は同(1) に
対応する式（３−１）がそれぞれ選択されたことにな
る。

【００３７】この比較の結果を用いて、経過時間、すな
わち到着時間間隔ΔＴを式（３−１），（３−２），
（３−３）に基づいて求める。

【００３８】なお、このとき仮想チャネルＪの経過時間
カウンタＣＴＲ２（Ｊ）は、必ずしもカウンタ１９の値
ＣＬＫがＪである時に増加される必要はなく、一定時間
周期に更新されればよい。その場合には、ステップＳ１
５，Ｓ１７，Ｓ１９においてＪの変わりに経過時間カウ
ンタＣＴＲ２（Ｊ）が更新される時のカウンタ１９の値
を用いる。

【００３９】次にステップＳ２７で、経過時間ΔＴを用
いて次式（４）に従って次の残りサービス時間ＣＴＲ１
ａを求める。

【００４０】

【数６】ＣＴＲ１ａ＝ｍａｘ｛ＣＴＲ１（Ｊ）＋Ｔ（Ｊ）−ΔＴ，０｝（４）さらに、ステップＳ２９において、式（４）で求めた残
りサービス時間ＣＴＲ１ａを閾値ＴＨ（Ｊ）とを比較
し、流量違反の判定を行う。

【００４１】ここで、残りサービス時間ＣＴＲ１ａが閾
値ＴＨ（Ｊ）以下であるときには、ステップＳ３１に進
み、当該入力セルを出回線に出力し、さらにステップＳ
３３で残りサービス時間ＣＴＲ１（Ｊ）に残りサービス
時間ＣＴＲ１ａを代入する。次に、ステップＳ３５で経
過時間カウンタＣＴＲ２（Ｊ）の値を０に、セル到着時
刻ＰＨＳ（Ｊ）に現在のカウンタ１９の値ＣＬＫを代入
する。

【００４２】また、ステップＳ２９において、残りサー
ビス時間ＣＴＲ１（Ｊ）がサービス時間Ｔ（Ｊ）より大
きい場合には、入力セルは違反セルであるため、ステッ
プＳ３７で入力セルを転送制御部１１において廃棄す
る。

【００４３】上述してきたように、本実施例のセル流量
制御装置は、仮想チャネル毎にセル到着時刻ＰＨＳ
（Ｊ）と経過時間カウンタＣＴＲ２（Ｊ）を持つこと
で、単一のカウンタ１９を用いてセル到着時にセルの到
着時間間隔を求めることが可能であり、仮想チャネル毎
に時間間隔を計測するカウンタを持つことが不要とな
る。さらに、セル到着時に一つ前のセルが到着した時刻
からの経過時間を得ることが可能となったことにより、
リーキバケットのカウンタをセル到着時に一括して更新
することができる。従来のように各仮想チャネルのカウ
ンタを一定時間周期でデクリメントすることが必要では
なくなり、１セル周期において更新しなければならない
リーキバケットカウンタは常に僅かに１個であることが
保証される。そこでこれらの値をメモリ上に蓄積し、す
べての仮想チャネルに共通に使用される演算部によって
リーキバケットのカウンタを更新し、違反の判定を行う
ことが可能となった。メモリ素子は論理素子に比べて高
集積に実現可能であるため、監視されなければならない
仮想チャネル数が大きな場合にも従来に比べて小さなハ
ードウェア規模でセル流量制御装置を実現することがで
きる。

【００４４】次に、第２の実施例におけるセル流量制御
装置３について説明する。このセル流量制御装置３は、
入力されたセルが規定されたセル流の特性に反している
場合には、違反ではなくなるまでの間、バッファに蓄積
してから出力するようにしたものである。

【００４５】以下、図６を参照して、第２の実施例にお
けるセル流量制御装置３の構成を説明する。セル流量制
御装置３は、ヘッダ解析部３１、Ｍセルを記憶すること
のできるバッファ３７と、入力セルが出力できるまでの
時間を計算するスロット計算部３３及びバッファ３７へ
の入力と出力を管理するスロット管理部３５とからな
る。

【００４６】スロット計算部３３は各仮想チャネルＶＣ
のトラヒック特性のパラメータを管理しており、セルが
入力されると、現在の時刻から出力が可能となる時刻ま
での時間Ｘ_oを計算し、スロット管理部３５に通知す
る。

【００４７】バッファ３７はＭセル分の記憶領域を持
ち、先頭から順に出力されるが、任意の位置に入力でき
る機能を有する。バッファ３７の各領域の空塞がりはス
ロット管理部３５によって管理されており、セル入力時
にスロット計算部３３から通知されたＸ_o以降の最も先
頭に近い空領域Ｘを捜して、先頭からＸ番目に入力セル
を記憶すると共に、Ｘをスロット計算部３３に通知す
る。スロット計算部３３では通知されたＸの値によって
パラメータを更新する。

【００４８】このスロット計算部３３の構成例を図７に
示す。スロット計算部３３は各仮想チャネルの情報を記
憶するメモリ３３５、演算部３３３及びクロック３３７
によって１だけ増加されるＮ進のカウンタ３３９とから
なる。ここでＮは、監視の対象となる仮想チャネルのチ
ャネル数を表すものとする。このメモリ３３５に記憶さ
れる情報は図４に示したメモリ１５の情報内容と等し
く、演算部３３３はカウンタ３３９の値とメモリ３３５
に蓄積されている情報とから図８に示すフローチャート
に従って、セルを出力できるまでの時間Ｘ_oを求める。

【００４９】図８に示すフローチャートにおいて、ステ
ップＳ１１１からＳ１２７までの動作は図５に示すフロ
ーチャートのステップＳ１１からＳ２７までのステップ
に等しい。

【００５０】以下、ステップＳ１２７以降に付いて説明
すると、ステップＳ１４１において

【数７】Ｘ_o＝ＣＴＲ１ａ−ＴＨ（Ｊ）（５）として、Ｘ_oを求め、スロット管理部３５に送信する。

【００５１】ここで、図９を参照して、スロット管理部
３５の構成例を説明する。Ｍビットのシフトレジスタ３
５５は、バッファ３７の各領域の空塞がりの状態を示す
もので、バッファ３７のｉ番目にセルが記憶されている
場合には、シフトレジスタ３５５のｉ番目のレジスタに
１がセットされる。

【００５２】スロット計算部３３からＸ_oを入力する
と、エンコーダ３５７は、Ｘ_o番目以降で最も先頭に近
い０であるレジスタの位置Ｘを制御部３５１に出力す
る。入回線からは複数の仮想チャネルが多重化されて入
力されているため、Ｘ_o番目にはすでに他の仮想チャネ
ルのセルが記憶されている可能性があるが、このように
して求めたＸは出力可能な最も早い時刻を示している。

【００５３】制御部３５１はバッファ３７のＸ番目の領
域にセルを記憶すると共にＸをデコーダ３５３に出力
し、デコーダ３５３は先頭からＸ番目のレジスタに信号
を出力し、このレジスタの値を１にセットする。Ｘは同
時にスロット計算部３３に通知される。

【００５４】セルがＸセル周期後に出力されることが決
まると、スロット管理部３５では、この仮想チャネルに
次のセルが入力されたときに、そのセルに対して出力可
能となる時刻を求めるために、メモリ３３５の値を図１
０のフローチャートに従って更新する。すなわち、ステ
ップＳ２１１では、残りサービス時間ＣＴＲ１（Ｊ）の
値を

【数８】ＣＴＲ１（Ｊ）＝ｍａｘ（ＣＴＲ１ａ−Ｘ，０）（６）によって更新する。次にステップＳ２１３では経過時間
カウンタＣＴＲ２（Ｊ）に−Ｘを、セル到着時刻ＰＨＳ
（Ｊ）にカウンタ３３９の現在の値ＣＬＫを代入する。

【００５５】セルの出力は、バッファの先頭から順に行
い、同時に、シフトレジスタ３５５を１ビットだけシフ
トする。ただし、シフトの際に、末尾のレジスタには０
を設定する。また、バッファの先頭の領域が空であると
きにはセルを出力しない。

【００５６】以上の構成によって、各仮想チャネルのセ
ルは定められた特性に従ってセル流量制御装置３から出
力される。

【００５７】また、異なる優先権をもったセルが入力さ
れた場合には、前記式（５）によって得られるＸ_oが定
められた閾値以上である場合には、そのセルを廃棄する
こととし、その閾値を優先度ごとに異なる値に設定する
ことで優先制御を行うことが可能である。

【００５８】上述した第２の実施例においても、直前の
セルが出力された時刻と現在時刻との時間間隔を新たな
セル到着時に求めることを可能とすることにより、セル
到着時にだけリーキバケットカウンタの値を更新し、定
められたトラヒック特性を満たす場合に出力できるまで
の時間を求めることが可能となる。さらに、セル入力時
に出力が可能となる時刻を特定するため、出力時に出力
の判定を行う必要がなく、少ない処理量で、トラヒック
特性を満たして可能な最も早い時刻に出力することが可
能である。

【００５９】次に本発明の第３の実施例について説明す
る。第３の実施例のセル流量制御装置５は、入回線上に
多重化された仮想チャネルのセル流をスライディングウ
ィンドウに基づいて監視し、定められたパラメータに違
反したセルを廃棄する。すなわち、セルが入力された時
に、そのセルの属する仮想チャネルにおいて（Ｘ０−
１）個前に到着したセルの到着時刻から現在時刻までの
経過時間ＴＭ（以下モニタリング時間と呼ぶ）が監視周
期Ｔ０未満であるときには、入力セルを違反セルである
と判定し、廃棄する。

【００６０】この様な機能を実現するために、セル流量
制御装置５は図１１に示されるように転送制御部５１、
演算部５３、メモリ５５、クロック５７、カウンタ５９
から構成される。

【００６１】転送制御部５１、クロック５７、カウンタ
５９の動作は第１の実施例における転送制御部１１、ク
ロック１７、カウンタ１９の動作とそれぞれ等しい。ま
た、メモリ５５は図１２に示される構成の情報を有す
る。

【００６２】すなわちチャネル０からチャネル（Ｎ−
１）のＮ個の仮想チャネルのそれぞれに、モニタリング
時間ＴＭ（０）〜（Ｎ−１）、セル到着間隔ＤＴ（０、
０）〜ＤＴ（０、Ｌ−１）〜（Ｊ、０）〜ＤＴ（Ｊ、Ｌ
−１）〜（Ｎ−１、０）〜ＤＴ（Ｎ−１、Ｌ−１）、セ
ル到着間隔ポインタｎ（０）〜、（Ｊ）、〜（Ｎ−
１）、監視周期Ｔ０（０）〜、（Ｊ）、〜（Ｎ−１）、
最大セル数Ｘ０（０）〜、（Ｊ）、〜（Ｎ−１）、セル
到着時刻ＰＨＳ（０）〜、（Ｊ）、〜（Ｎ−１）、経過
時間カウンタＣＴＲ２（０）〜、（Ｊ）、〜（Ｎ−１）
をテーブルとして持つ。

【００６３】モニタリング時間ＴＭ（Ｊ）は（Ｘ０−
１）個前に到着したセルの到着時刻から最後に到着した
セルの到着時刻までの経過時間を記憶する。セル到着間
隔ＤＴ（Ｊ、０）〜ＤＴ（Ｊ、Ｌ−１）は過去Ｌ個のセ
ルの到着間隔を記憶し、セル到着間隔ポインタｎ（Ｊ）
が最も新しい到着間隔を記憶するセル到着間隔を示す。
すなわち、ＤＴ（Ｊ、ｎ（Ｊ））が最も新しいセル到着
間隔である。

【００６４】これらの値を用いて、演算部５３では図１
３に示されるフローチャートにしたがって演算を行い、
違反判定を行う。ステップＳ２１１からＳ２２５までの
動作は図５に示すフローチャートのステップＳ１１から
Ｓ２５までのステップに等しいので、ステップＳ２２７
以降について説明する。ステップＳ２２７においてＴＭ
´を次式によって求める。

【００６５】

【数９】ＴＭ´＝ＴＭ（Ｊ）−ＤＴ（Ｊ、ｎ（Ｊ）−Ｘ０（Ｊ）＋１）＋ΔＴ（７）ただし、上式で（ｎ（Ｊ）−Ｘ０（Ｊ）＋１）が負にな
る場合には、Ｌでモジュロをとった値を用いる。ＴＭ´
は（Ｘ０（Ｊ）−１）個前に到着したセルの到着時刻か
ら現在までの経過時間であり、ステップＳ２２９におい
てＴＭ´をＴ０（Ｊ）と比較する。ＴＭ´がＴ０（Ｊ）
以上である場合には、入力されたセルは違反セルではな
いので出回線に出力し（ステップＳ２３１）、次に到着
するセルの判定を行うためにステップＳ２３３でｎ
（Ｊ）の値を１増加させ、ステップＳ２３５においてこ
のｎ（Ｊ）で定まるセル到着間隔ＤＴ（Ｊ、ｎ（Ｊ））
にΔＴを記憶し、ＴＭ（Ｊ）にＴＭ´を記憶する。

【００６６】次にステップＳ２３７でセル到着時刻ＰＨ
Ｓ（Ｊ）に現在のカウンタ５９の値を設定し、経過時間
カウンタＣＴＲ２（Ｊ）を０にリセットする。ステップ
Ｓ２２９においてＴＭ´がＴ０（Ｊ）より小さい場合に
は、ステップＳ２３９において入力セルを廃棄する。

【００６７】また、スライディングウィンドウを用いた
場合にも第２の実施例のセル流量制御装置３のように出
回線に出力しても違反とならない時刻までセルをバッフ
ァに蓄積してから出力するセル流量制御装置を構成する
ことも可能である。スライディングウィンドウを用いる
場合には、出力することが可能となる時刻までに必要な
時間間隔は、監視周期Ｔ０とＴＭ´との差（Ｔ０−ＴＭ
´）であるので、現在の時刻から（Ｔ０−ＴＭ´）以降
でありかつ出力可能である最初の時刻に出力するように
バッファからのセルの出力を制御すれば良い。

【００６８】上述の第３の実施例におけるセル流量制御
装置においても、第１、第２の実施例におけるセル流量
制御装置と同じく、到着したセルの属する仮想チャネル
に関した情報だけを用いてセル流量の制御が可能となっ
ている。

【００６９】また、リーキーバケット、スライディング
ウィンドウの他にセル流の監視・制御を行う方式とし
て、ジャンピングウィンドウ、トリガードジャンピング
ウィンドウなどが知られている。ジャンピングウィンド
ウは、図１４に示されるように、Ｔ１時間周期でそれぞ
れのＴ１時間内の入力セル数を計測し、定められた最大
セル数Ｘ１を越えて入力されたセルを違反とする。

【００７０】また、トリガードジャンピングウィンドウ
では、Ｔ１時間経過後、最初にセルが到着した時刻にＴ
１時間のウィンドウをリセットし、これからＴ１時間以
内にＸ１セルを越えたセルが入力したときに、このセル
を違反とする。

【００７１】このようなジャンピングウィンドウもしく
はトリガードジャンピングウィンドウにもとづいたセル
流量制御装置を、上述の第１の実施例および第３の実施
例におけるセル流量制御装置と同様の構成で実現するこ
とができる。

【００７２】ジャンピングウィンドウに基づく場合に
は、メモリに仮想チャネルごとにセル数カウンタＮ
（０）〜Ｎ（Ｊ）〜Ｎ（Ｎ−１）、監視周期Ｔ１（０）
〜Ｔ１（Ｊ）〜Ｔ１（Ｎ−１）、最大セル数Ｘ１（０）
〜Ｘ１（Ｊ）〜Ｘ１（Ｎ−１）、セル到着位相ＰＨＳ
（０）〜ＰＨＳ（Ｊ）〜ＰＨＳ（Ｎ−１）、経過時間カ
ウンタＣＴＲ２（０）〜ＣＴＲ２（Ｊ）〜ＣＴＲ２（Ｎ
−１）を有する。

【００７３】このセル流量制御装置の動作のフローチャ
ートを図１５に示す。ステップＳ３１１〜Ｓ３２５まで
の動作は、図５のステップＳ１１〜からステップＳ２５
までの動作に等しい。次にステップＳ３２７においてΔ
ＴとＴ１（Ｊ）とを比較し、ΔＴがＴ１（Ｊ）より小さ
い場合には、ステップＳ３２９においてＮ（Ｊ）とＸ１
（Ｊ）との比較を行う。Ｎ（Ｊ）がＸ１（Ｊ）より小さ
い場合には、ステップＳ３３１でセルを出回線に出力
し、ステップＳ３３３でＮ（Ｊ）の値を１増加させる。
ステップＳ３２９においてＮ（Ｊ）がＸ１（Ｊ）以上で
ある場合には入力セルは違反セルであるので、ステップ
Ｓ３３５で廃棄する。また、ステップＳ３２７において
ΔＴがＴ１（Ｊ）以上である場合には、新しい周期に移
行しているので、ステップＳ３３７でＮ（Ｊ）をセルを
出力し、ステップＳ３３９でＮ（Ｊ）に１を代入する。

【００７４】次にステップＳ３４１で新しい周期におけ
る経過時間を計測するためにＣＴＲ２（Ｊ）にΔＴをＴ
１（Ｊ）でモジュロをとった値を代入し、ＰＨＳ（Ｊ）
にＣＬＫを代入する。トリガードジャンピングウィンド
ウにもとづいてセル流を制御するセル流量制御装置にお
いては、動作のフローチャートが異なり、図１６のステ
ップＳ３４１でＣＴＲ２（Ｊ）にΔＴをＴ１（Ｊ）でモ
ジュロをとった値を代入する変わりに０を代入すればよ
い。この場合にも、１セル時間に必要な情報は、一つの
仮想チャネルＶＣの情報だけであるので少ないハードウ
ェア量でセル流量制御装置を構成することができる。

【００７５】

【発明の効果】以上、説明したように本発明によれば、
多数の仮想チャネルの多重化された伝送路のセル流の制
御を行うセル流量制御装置を、少ないハードウェア規模
で実現することが可能となる。

【図面の簡単な説明】

【図１】セル流量制御装置の構成例を示す図である。

【図２】残りサービス時間ＣＴＲ１の更新の様子を現す
図である。

【図３】到着時間間隔ΔＴとセル到着間隔の関係を示す
図である。

【図４】メモリの構成例を示す図である。

【図５】セル流量制御装置の動作を示すフローチャート
である。

【図６】第２の実施例のセル流量制御装置の構成例を示
す図である。

【図７】スロット計算部の構成例を示す図である。

【図８】Ｘ_oを求める動作のフローチャートである。

【図９】スロット管理部の構成例を示す図である。

【図１０】メモリの更新のフローチャートである。

【図１１】第３の実施例のセル流量制御装置の構成例を
示す図である。

【図１２】メモリの構成例を示す図である。

【図１３】セル流量制御装置の動作を示すフローチャー
トである。

【図１４】ジャンピングウィンドウにおける判定の様子
を現す図である。

【図１５】ジャンピングウィンドウに基づくセル流量制
御装置の動作を示すフローチャートである。

【図１６】従来技術における構成例である。

【符号の説明】

１セル流量制御装置１１転送制御部１３演算部１５メモリ１７クロック１９カウンタ１０１到着監視部１０５カウンタ１０７クロック１０９カウンタ１１１レジスタ１１３比較器１１５比較器１１７レジスタ３セル流量制御装置３１ヘッダ解析部３３スロット計算部３５スロット管理部３７バッファ３３３演算部３３５メモリ３３７クロック３３９カウンタ３５１制御部３５３デコーダー３５５シフトレジスタ３５７エンコーダー５セル流量制御装置５１転送制御部５３演算部５５メモリ５７クロック５９カウンタ

フロントページの続き (56)参考文献特開平３−150944（ＪＰ，Ａ) 特開平５−110585（ＪＰ，Ａ) 特開平４−329733（ＪＰ，Ａ) 欧州特許出願公開435046（ＥＰ，Ａ１)

Claims

(57)【特許請求の範囲】

【請求項１】複数の仮想チャネルが多重化された伝送
路上のセル流を制御するセル流量制御装置において、前記仮想チャネルのそれぞれに対して任意に設定される
始点からの経過時間を計測する経過時間計測手段と、前記仮想チャネルのそれぞれに対して、到着セルの流量
に関する値を保持する記憶手段と、新たなセルが到着したときに、当該セルが属する仮想チ
ャネルに対する前記記憶手段の値を、前記経過時間計測
手段によって得られる現在の時刻までの経過時間に基づ
いて更新する演算手段と、前記演算手段により更新された前記記憶手段の値に基づ
いてセルの転送制御を行う制御手段とを具備し、前記経過時間計測手段は、前記仮想チャネル毎に設けられた、Ｎセル周期毎にＮ増
加する第一のカウンタと、１セル周期毎に１増加する第二のカウンタとを有し、前記仮想チャネルを経由してセルが到着した場合、当該
仮想チャネルに対応する前記第一のカウンタ値と、前記
第二のカウンタ値とを用いて経過時間を計測することを
特徴とするセル流量制御装置。
【請求項２】複数の仮想チャネルが多重化された伝送
路上のセル流を制御するセル流量制御装置において、前記仮想チャネルのそれぞれに対して、ある時点までに
到着して当該時点でバッファに保持されている一つ以上
のセルを当該バッファから出力し終わるまでにかかるは
ずの時間である、残りサービス時間を記憶する手段と、新たなセルが到着したときに、当該セルが属する仮想チ
ャネルの一つ前のセルが到着した時刻から現在時刻まで
の経過時間を求める手段と、前記経過時間を前記残りサービス時間から減じた値に当
該仮想チャネルのセルのサービス時間を加えた値に基づ
いて、セルの転送制御を行う手段とを具備することを特
徴とするセル流量制御装置。
【請求項３】入力されるセルが出力可能となる時間ま
での現在の時刻からの時間差を求める計算手段と、前記計算手段で求められた時間差以降の出力が予約され
ていない時刻に出力を予約する予約手段と、前記予約手段によって予約された時刻にセルの出力を行
なう制御手段とを具備することを特徴とする請求項１に
記載のセル流量制御装置。