セル流量制御装置
【目的】 本発明は伝送路上に多重化された複数の仮想チャネルVCのセル流をリーキバケットに基づいて監視する監視装置を小さなハードウェア規模で実現する。
【構成】 セル到着時に、このセルの属する仮想チャネルVCにおいて直前にセルが到着してからの経過時間を計測し、この経過時間によってリーキバケットのカウンタを更新する。
【効果】 各仮想チャネルVCのカウンタはセル到着時にのみ更新されるので、これらの値をメモリ上に蓄積し、一つの演算装置によって多数の仮想チャネルVCの監視を行うことができる。
【構成】 セル到着時に、このセルの属する仮想チャネルVCにおいて直前にセルが到着してからの経過時間を計測し、この経過時間によってリーキバケットのカウンタを更新する。
【効果】 各仮想チャネルVCのカウンタはセル到着時にのみ更新されるので、これらの値をメモリ上に蓄積し、一つの演算装置によって多数の仮想チャネルVCの監視を行うことができる。
【発明の詳細な説明】
【0001】
【産業上の利用分野】本発明は、ATM交換方式におけるセル流量制御装置に関する。
【0002】
【従来の技術】近年、高速かつ広帯域なB−ISDN網等を実現する網アーキテクチャとしてのATM(Asynchronous Transfer Mode)交換方式が注目されており、このATM交換方式は、固定長で区切られた情報毎にルーティング情報等を示すヘッダを付与したセルを情報単位として伝送路上でラベル多重し、交換ノードではこのヘッダの情報のみを参照してセル単位で交換動作を行うものである。また、このATM交換方式は、旧来の回線交換方式とは異なり各通信に固定の通信帯域を割り当てることは無く、複数の通信が単一の通信帯域を共有して通信を行うようにしている。
【0003】このATM交換を利用して、通信を開始するときは、発端末とATM交換網との間で必要なトラヒック特性と通信品質との取り決めを行い、ATM交換網では申告されたトラヒック特性をもったセル流が流入した場合に要求された通信品質を提供できるか否かを判定し、要求された通信品質を提供できると判定されたときには着端末との間に仮想チャネルVC(Virtual Chanel)を設定し、セルの転送が発端末と着端末との間で行われる。前述したように、この仮想チャネルVCには固定の通信帯域が割り当てられるわけではないので、事前に定められた以上のセル流を発生すると、定められた通信品質を提供できない。そのため、ATM交換網においては、各仮想チャネルVCのトラヒック特性が申告された特性を満たしているかどうかを監視するポリシング機能が必要となり、端末においても発生するトラヒックを申告した通りの特性で出力するためのシェイピング機能が必要となる。
【0004】この様なセル流の監視、制御を行う方式としてはリーキパケットを用いた方式が知られている(J.S.Turner,"New Directions in Communications",pp8-15,IEEE Communications Magazine,vol.24,No.10,October 1986 )。従来のリーキバケットの構成例を図11に示す。
【0005】図11において、到着監視部101はセルの到着を検出すると、AND回路103を介して、カウンタ105をインクリメントする。このとき、AND回路103の他側には比較器115からの出力が入力される。また、単位時間周期のクロックを発生するクロック107から出力されるクロック信号でカウンタ109をインクリメントし、このカウンタ109の値Aと一定値Tを記憶するレジスタ111の出力、閾値Bとを比較器113において比較し、一致した場合(A=B)にカウンタ105を1だけデクリメントすると共にカウンタ109をリセットする。なお、カウンタ105の値が0である場合には、比較器113においてA=Bとなった場合にもそれ以上カウンタ105の値をデクリメントしない。
【0006】また、同時にカウンタ105の値を比較器115に出力し、このカウンタ105の値Aとレジスタ117からの出力Bとを比較し、一致しているとき(A=B)に到着したセルを違反と判定し、到着監視部101において廃棄する。
【0007】上述したように、ATM交換網では一つの回線上には複数の仮想チャネルVCが多重化されることがあり、各仮想チャネルVCに対してセル流の監視を独立に行わなければならない。しかし、各仮想チャネルVCのパラメータは必ずしも等しい値を持たないので、時間周期の測定などは独立に行う必要がある。このような複数の仮想チャネルVCを監視するためには、図11に示したリーキバケットをセル流の監視を行う仮想チャネル数だけ用意して、かつ並行して動作させることで実現できる。しかしながら、ハードウェア量が仮想チャネルVC数に比例して増加するため、多数の仮想チャネルVCが多重化される場合の流量制御装置が非常に大規模になる。そこで、ハードウェア量を低減させるために、カウンタの値などをメモリ上に記憶し、一つの演算装置を複数の仮想チャネルVCで共用して、メモリに記憶されている値を更新してリーキバケットを実現する構成も考えられるが、メモリのアクセス速度、演算装置の処理能力などの制約によって、監視を行うことができる仮想チャネルVC数が制限され、多数の仮想チャネルVCを監視することができない。従って、このような構成を用いても仮想チャネルVC数が大なるときには、複数の装置を並列に動作させなければならず、この場合にもハードウェア量が増加してしまう。
【0008】次に本発明の第3の実施例について説明する。第3の実施例のセル流量制御装置5は、入回線上に多重化された仮想チャネルのセル流をスライディングウィンドウに基づいて監視し、定められたパラメータに違反したセルを廃棄する。すなわち、セルが入力された時に、そのセルの属する仮想チャネルにおいて(X0−1)個前に到着したセルの到着時刻から現在時刻までの経過時間TM(以下モニタリング時間と呼ぶ)が監視周期T0未満であるときには、入力セルを違反セルであると判定し、廃棄する。この様な機能を実現するために、セル流量制御装置5は図11に示されるように転送制御部51、演算部53、メモリ55、クロック57、カウンタ59から構成される。転送制御部51、クロック57、カウンタ59の動作は第1の実施例における転送制御部11、クロック17、カウンタ19の動作とそれぞれ等しい。また、メモリ55は図12に示される構成の情報を有する。すなわちチャネル0からチャネル(N−1)のN個の仮想チャネルのそれぞれに、モニタリング時間TM(0)〜(N−1)、セル到着間隔DT(0、0)〜DT(0、L−1)〜(J、0)〜DT(J、L−1)〜(N−1、0)〜DT(N−1、L−1)、セル到着間隔ポインタn(0)〜、(J)、〜(N−1)、監視周期T0(0)〜、(J)、〜(N−1)、最大セル数X0(0)〜、(J)、〜(N−1)、セル到着時刻PHS(0)〜、(J)、〜(N−1)、経過時間カウンタCTR2(0)〜、(J)、〜(N−1)をテーブルとして持つ。モニタリング時間TM(J)は(X0−1)個前に到着したセルの到着時刻から最後に到着したセルの到着時刻までの経過時間を記憶する。セル到着間隔DT(J、0)〜DT(J、L−1)は過去L個のセルの到着間隔を記憶し、セル到着間隔ポインタn(J)が最も新しい到着間隔を記憶するセル到着間隔を示す。すなわち、DT(J、n(J))が最も新しいセル到着間隔である。これらの値を用いて、演算部53では図13に示されるフローチャートにしたがって演算を行い、違反判定を行う。ステップS211からS225までの動作は図5に示すフローチャートのステップS11からS25までのステップに等しいので、ステップS227以降について説明する。ステップS227においてTM´を次式によって求める。
【0009】
TM´=TM(J)−DT(J、n(J)−X0(J)+1)+ΔT (7)
ただし、上式でn(J)−X0(J)+1が負になる場合には、Lでモジュロをとった値を用いる。TM´はX0(J)−1個前に到着したセルの到着時刻から現在までの経過時間であり、ステップS229においてTM´をT0(J)と比較する。TM´がT0(J)以上である場合には、入力されたセルは違反セルではないので出回線に出力し(ステップS231)、次に到着するセルの判定を行うためにステップS233でn(J)の値を1増加させ、ステップS235においてこのn(J)で定まるセル到着間隔DT(J、n(J))にΔTを記憶し、TM(J)にTM´を記憶する。次にステップS237でセル到着時刻PHS(J)に現在のカウンタ59の値を設定し、経過時間カウンタCTR2(J)を0にリセットする。ステップS229においてTM´がT0(J)より小さい場合には、ステップS239において入力セルを廃棄する。
【0010】また、スライディングウィンドウを用いた場合にも第2の実施例のセル流量制御装置3のように出回線に出力しても違反とならない時刻までセルをバッファに蓄積してから出力するセル流量制御装置を構成することも可能である。スライディングウィンドウを用いる場合には、出力することが可能となる時刻までに必要な時間間隔は、監視周期T0とTM´との差(T0−TM´)であるので、現在の時刻から(T0−TM´)以降でありかつ出力可能である最初の時刻に出力するようにバッファからのセルの出力を制御すれば良い。
【0011】上述の第3の実施例におけるセル流量制御装置においても、第1、第2の実施例におけるセル流量制御装置と同じく、到着したセルの属する仮想チャネルに関した情報だけを用いてセル流量の制御が可能となっている。
【0012】また、リーキーバケット、スライディングウィンドウの他にセル流の監視・制御を行う方式として、ジャンピングウィンドウ、トリガードジャンピングウィンドウなどが知られている。ジャンピングウィンドウは、図14に示されるように、T1時間周期でそれぞれのT1時間内の入力セル数を計測し、定められた最大セル数X1を越えて入力されたセルを違反とする。また、トリガードジャンピングウィンドウでは、T1時間経過後、最初にセルが到着した時刻にT1時間のウィンドウをリセットし、これからT1時間以内にX1セルを越えたセルが入力したときに、このセルを違反とする。このようなジャンピングウィンドウもしくはトリガードジャンピングウィンドウにもとづいたセル流量制御装置を、上述の第1の実施例および第3の実施例におけるセル流量制御装置と同様の構成で実現することができる。ジャンピングウィンドウに基づく場合には、メモリに仮想チャネルごとにセル数カウンタN(0)〜N(J)〜N(N−1)、監視周期T1(0)〜T1(J)〜T1(N−1)、最大セル数X1(0)〜X1(J)〜X1(N−1)、セル到着位相PHS(0)〜PHS(J)〜PHS(N−1)、経過時間カウンタCTR2(0)〜CTR2(J)〜CTR2(N−1)を有する。このセル流量制御装置の動作のフローチャートを図15に示す。ステップS311〜S325までの動作は、図5のステップS11〜からステップS25までの動作に等しい。次にステップS327においてΔTとT1(J)とを比較し、ΔTがT1(J)より小さい場合には、ステップS329においてN(J)とX1(J)との比較を行う。N(J)がX1(J)より小さい場合には、ステップS331でセルを出回線に出力し、ステップS333でN(J)の値を1増加させる。ステップS329においてN(J)がX1(J)以上である場合には入力セルは違反セルであるので、ステップS335で廃棄する。また、ステップS327においてΔTがT1(J)以上である場合には、新しい周期に移行しているので、ステップS337でN(J)をセルを出力し、ステップS339でN(J)に1を代入する。次にステップS341で新しい周期における経過時間を計測するためにCTR2(J)にΔTをT1(J)でモジュロをとった値を代入し、PHS(J)にCLKを代入する。トリガードジャンピングウィンドウにもとづいてセル流を制御するセル流量制御装置においては、動作のフローチャートが異なり、図15のステップS341でCTR2(J)にΔTをT1(J)でモジュロをとった値を代入する変わりに0を代入すればよい。この場合にも、1セル時間に必要な情報は、一つの仮想チャネルVCの情報だけであるので少ないハードウェア量でセル流量制御装置を構成することができる。
【0013】また、違反と判定された場合に、この違反と判定されたセルを廃棄せずに、出力されても違反とならない時刻までバッファに蓄積してから出力する制御もある。例えば、本出願人によって先に出願されている特願平2−217216に述べられているように、従来はバッファからセルを出力する度に、蓄積されているセルのそれぞれが違反となるか否かを調べて、出力可能であるセルを捜して出力する構成がとられていた。しかし、この様な構成では、上述のリーキバケット実現に大きなハードウェアが必要であることに加えて、出力可能なセルを捜すために必要な処理量が大きくなる。
【0014】
【発明が解決しようとする課題】上述したように、従来は、多重化されている仮想チャネルVCのセル流を監視するセル流量制御装置は、仮想チャネルVC数が大きいとき、ハードウェア量が増大して実現が困難である。さらに、違反ではなくなるまでの間、バッファに蓄積して出力する場合には、出力されるセルを決定するための処理量が大きくなり、処理時間の増大を招来するところとなった。
【0015】本発明は、以上のような状況に鑑みてなされたものであり、対象となる仮想チャネルVC数が大きい場合でも、仮想チャネルVC数に比例したハードウェア量を必要とすることのないセル流量制御装置を実現するものである。
【0016】
【課題を解決するための手段】上記目的を達成するために、本願第1の発明は、複数の仮想チャネルが多重化された伝送路上のセル流を制御するセル流量制御装置において、前記仮想チャネルのそれぞれに対して任意に設定される始点からの経過時間を計測する経過時間計測手段と、前記仮想チャネルのそれぞれに対して、到着するセルの流量を計測する流量計測手段と、新たなセルが到着したときに当該セルが属する仮想チャネルに対する前記流量計測手段の値を、前記経過時間計測手段によって得られた現在の時刻までの経過時間に係る値に更新する演算手段と、この演算手段の演算結果に基づいてセルの転送制御を行う制御手段とを有することを要旨とする。
【0017】また、本願第2の発明は、複数の仮想チャネルが多重化された伝送路上のセル流を制御するセル流量制御装置において、入力されるセルが出力可能となる時刻までの、現在の時刻からの時間差を求める計算手段と、前記計算手段で求められた時間差以降の出力が予約されていない時刻に出力を予約する予約手段と、前記予約手段によって予約された時刻にセルの出力を行う制御手段とを有することを要旨とする。
【0018】
【作用】本願第1の発明によれば、任意の時点において、任意に設定される始点、例えば直前のセルが到着してから、あるいはメモリから読み出したときからの経過時間を知る経過時間計測手段を持つことによって、セルが到着した時に一括して流量計測手段の値を更新することが可能となるので、同時に複数の仮想チャネルVCの情報をアクセスする必要がなく、仮想チャネルVC数に関わりなく仮想チャネルVC毎に必要な値をメモリ上に蓄積し、単一の演算手段をもちいて監視を行うことが可能となる。これによって、仮想チャネルVC数が大なる場合においてもセル流量制御装置を構成するために必要なハードウェア量を大きく低下することが可能である。
【0019】また、本願第2の発明によれば、セル入力時にセルの出力が可能となる時刻を求め、この時刻以降で最初に予約されていない時刻にセルの出力を予約し、予約された時刻にセルを出力することで、出力時にはバッファ内のセルの出力可否の判定を行わずに、定められた特性でセルの出力を行うことが可能となる。
【0020】
【実施例】以下、本発明の一実施例を図面を参照して説明する。図1は本発明の第1の実施例におけるセル流量制御装置1の構成を示すブロック図である。
【0021】まず、図1を参照して本実施例のセル流量制御装置1の構成を説明する。このセル流量制御装置1は、入回線上に多重化されたNチャネルの仮想チャネルのセル流量の流量監視を行うもので、制御手段としての転送制御部11、演算手段としての演算部13、メモリ15、クロック17及び経過時間計測手段としてのカウンタ7によって構成される。尚、このNチャネルの仮想チャネルには予め0から(N−1)までの仮想チャネル番号が付与されているものとする。
【0022】転送制御部11は、入回線から入力されるセルのヘッダ情報から仮想チャネル番号を識別し、この転送制御部11に接続される演算部13に仮想チャネル番号を通知するものである。
【0023】演算部13は、転送制御部11から通知された仮想チャネル番号をもとにしてメモリ15に記憶されている当該仮想チャネルに対応する情報を読みだし、この情報に基づく判定結果を転送制御部11に通知する。この演算部13における判定結果が違反セルであるとき、転送制御部11は当該入力セルを廃棄する。また、違反セルではないと判定されたときには、当該入力セルは出回線に出力される。
【0024】クロック17はセル周期の信号を発生し、カウンタ19はクロック17の発生する信号によって動作するN進のカウンタである。すなわち、カウンタ19の値が(N−1)であるとき、次のクロックが入力されるとカウンタ19の値が0となる。ただし、セル周期は入回線もしくは出回線上で1セルの転送に要する時間を示すものとする。
【0025】次に、セル流量制御装置1の作用を説明する。本来のリーキバケットでは、従来の技術の欄で説明したように、セルが到着すると1だけインクリメントされ、一定時間T毎に1だけデクリメントされるカウンタを持ち、このカウンタの値がしきい値B以上である時に到着したセルが違反セルと判定されるものである。
【0026】このカウンタ19の値は、1セルのサービス時間がTである待ち行列システムのキュー長を示していると見なすことができ、従ってリーキバケットにおける判定は、この待ち行列システムのシステム内セル数が(B−1)以下である場合に違反ではないと判定することに等しい。この待ち行列システムにおいて、サービス中のセルが出力されるまでの残り時間と、待ち行列に並んでいるセルが必要とするサービス時間との合計を残りサービス時間CTR1としたとき、システム内セル数が(B−1)以下であるという条件は、 CTR1≦TH (1)
ただし、閾値TH=T×(B−1)
と書ける。
【0027】また、図2に示すように、新たなセルが到着した時の残りサービス時間CTR1new は、一つ前のセルが到着した時点での残りサービス時間CTR1old と到着時間間隔ΔTによって CTR1mew =max(CTR1old +T−ΔT,0) (2)
となるので、残りサービス時間CTR1old と到着時間間隔ΔTが分かれば、上述の式を用いて求められる残りサービス時間CTR1new と閾値THとを比較して、入力セルの違反判定を行うことができる。
【0028】以下、到着時間間隔ΔTの算出に付いて説明する。ここでは、カウンタ19を用いて到着時間間隔ΔTを求めるために、仮想チャネルVC毎にセル到着時刻PHSと経過時間カウンタCTR2を用いる。
【0029】入回線を介して、新たなセルが到着するとセル到着時刻PHSにはその時点でのカウンタ19の値がセットされる。経過時間カウンタCTR2は、セルが到着すると0にリセットされ、カウンタ19が仮想チャネルVCに定められた値を示す度に仮想チャネルのチャネル数に等しい値Nが加えられる。ここでは、チャネルJの経過時間カウンタCTR2はカウンタ19の値がJとなったときに増加されるものとする。経過時間カウンタCTR2の値を、このように更新することによって、各セル周期には1つの仮想チャネルの経過時間カウンタCTR2だけを増加すれば良くなる。
【0030】経過時間カウンタCTR2は、Nセル周期ごとにしか増加されないため、正確なセルの到着間隔を示していないが、前のセルが到着したときのカウンタ19の値を記憶しているセル到着時刻PHSと現在のカウンタ19の値CLKを用いると正確な到着時間間隔ΔTを求めることができる。
【0031】到着時間間隔ΔTと経過時間カウンタCTR2、セル到着時刻PHSおよびカウンタ19の値CLKとの関係は、セル到着時刻PHSと経過時間カウンタCTR2がN増加されるときのカウンタ19の値Jの関係と、現在のカウンタ19の値CLKとJの関係によって場合分けされ、以下の式(3−1),(3−2),(3−3)で到着時間間隔ΔTは与えられる。図3にこの様子を示す。
【0032】すなわち、図3(3) 及び(1) の場合は、PHS(J)≧J,CLK≧JまたはPHS(J)<J,CLK<Jの時の到着時間間隔ΔTが、 ΔT=CTR2(J)+CLK−PHS(J) (3−1)
で与えられ、図3(2) の場合は、PHS(J)<J,CLK≧Jの時の到着時間間隔ΔTが、 ΔT=CTR2(J)+CLK−PHS(J)−N (3−2)
で与えられ、図3(4) の場合は、PHS(J)≧J,CLK<Jの時の到着時間間隔ΔTが、 ΔT=CTR2(J)+CLK−PHS(J)+N (3−3)
で与えられることを、それぞれ示すものである。
【0033】また、カウンタ19の周期を、監視するチャネル数Nと等しくしているので、各セル周期には1つの仮想チャネルVCの経過時間カウンタCTR2を増加すれば良い。
【0034】以上述べたアルゴリズムを実現するために、メモリ15は図4に示される構成の情報を有する。すなわち、チャネル0からチャネル(N−1)のN個の仮想チャネルのそれぞれに、残りサービス時間CTR1(0),〜,(J),〜,(N−1)、しきい値TH(0),〜,(J),〜,(N−1)、1セルのサービス時間T(0),〜,(J),〜,(N−1)、セル到着時刻PHS(0),〜,(J),〜,(N−1)、経過時間カウンタCTR2(0),〜,(J),〜,(N−1)をテーブルとして持つ。ここでJは対応する仮想チャネル番号を示す。
【0035】セル到着時刻PHS(J)、経過時間カウンタCTR2(J)はこの仮想チャネルにおいて直前にセルが入力されてらかの経過時間を求めるために用いられ、残りの値によってリーキバケットを構成する。
【0036】次に、図5に示すフローチャートを参照して、各セル周期でのセル流量制御装置1の作用を説明する。以下、入回線を介して仮想チャネル番号Jのセルが入力され、このセルの仮想チャネル番号が転送制御部11において当該セルのヘッダ情報から識別される場合を例に説明する。
【0037】まず、セル周期の初めにステップS11において、後段のステップでのΔTの算出を可能にするために、予めカウンタ19の値CLKに等しい仮想チャネル番号の経過時間カウンタCTR2の値に仮想チャネルのチャネル数に等しい値Nを加えておく。
【0038】また、ΔTは(CTR1+T)より大きい場合には、後述する動作はΔTの値に影響されないので、CTR2が適当な閾値以上である時にはNを加えないようにすることで、CTR2がオーバフローを生じることがないようにすることができる。さらに、CTR2にはカウンタ19の値が仮想チャネル番号に等しくなった回数だけを記憶するようにして、必要なときにこれをN倍して用いる構成も可能である。
【0039】次に、ステップS13において、セルの入力がなければ(NO)、このセル周期での動作を終了する。一方、入回線を介してセルが入力された場合(YES)には、ステップS15に進み、この入力され到着したセルの仮想チャネル番号Jに対応するセル到着時刻PHS(J)の値とカウンタ19の値CLKとを比較する。ここで、PHS(J)≧Jならば、ステップS17に進む。このとき、図3に示す(3) 、(4) が選択されたことになる。また、PHS(J)<Jならば、ステップS19に進む。このとき図3に示す(1)、(2) が選択されたことになる。
【0040】次にステップS17,S19において、仮想チャネル番号Jとカウンタ19の値CLKとの比較を行う。ステップS17で、CLK≧Jならば、ステップS23に進み、CLK<Jならば、ステップS21に進む。このとき、ステップS23は図3(3) に対応する式(3−1)が、ステップS21は同(4) に対応する式(3−3)がそれぞれ選択されたことになる。
【0041】一方、ステップS19で、CLK≧Jならば、ステップS25に進み、CLK<Jならば、ステップS23に進む。このとき、ステップS25は図3(2) に対応する式(3−2)が、ステップS23は同(1) に対応する式(3−1)がそれぞれ選択されたことになる。
【0042】この比較の結果を用いて、経過時間、すなわち到着時間間隔ΔTを式(3−1),(3−2),(3−3)に基づいて求める。
【0043】なお、このとき仮想チャネルJの経過時間カウンタCTR2(J)は、必ずしもカウンタ19の値CLKがJである時に増加される必要はなく、一定時間周期に更新されればよい。その場合には、ステップS15,S17,S19においてJの変わりに経過時間カウンタCTR2(J)が更新される時のカウンタ19の値を用いる。
【0044】次にステップS27で、経過時間ΔTを用いて次式(4)に従って次の残りサービス時間CTR1aを求める。
【0045】
CTR1a=max{CTR1(J)+T(J)−ΔT,0} (4)
さらに、ステップS29において、式(4)で求めた残りサービス時間CTR1aを閾値TH(J)とを比較し、流量違反の判定を行う。
【0046】ここで、残りサービス時間CTR1aが閾値TH(J)以下であるときには、ステップS31に進み、当該入力セルを出回線に出力し、さらにステップS33で残りサービス時間CTR1(J)に残りサービス時間CTR1aを代入する。次に、ステップS35で経過時間カウンタCTR2(J)の値を0に、セル到着時刻PHS(J)に現在のカウンタ19の値CLKを代入する。
【0047】また、ステップS29において、残りサービス時間CTR1(J)がサービス時間T(J)より大きい場合には、入力セルは違反セルであるため、ステップS37で入力セルを転送制御部11において廃棄する。
【0048】上述してきたように、本実施例のセル流量制御装置は、仮想チャネル毎にセル到着時刻PHS(J)と経過時間カウンタCTR2(J)を持つことで、単一のカウンタ19を用いてセル到着時にセルの到着時間間隔を求めることが可能であり、仮想チャネル毎に時間間隔を計測するカウンタを持つことが不要となる。さらに、セル到着時に一つ前のセルが到着した時刻からの経過時間を得ることが可能となったことにより、リーキバケットのカウンタをセル到着時に一括して更新することができる。従来のように各仮想チャネルのカウンタを一定時間周期でデクリメントすることが必要ではなくなり、1セル周期において更新しなければならないリーキバケットカウンタは常に僅かに1個であることが保証される。そこでこれらの値をメモリ上に蓄積し、すべての仮想チャネルに共通に使用される演算部によってリーキバケットのカウンタを更新し、違反の判定を行うことが可能となった。メモリ素子は論理素子に比べて高集積に実現可能であるため、監視されなければならない仮想チャネル数が大きな場合にも従来に比べて小さなハードウェア規模でセル流量制御装置を実現することができる。
【0049】次に、第2の実施例におけるセル流量制御装置3について説明する。このセル流量制御装置3は、入力されたセルが規定されたセル流の特性に反している場合には、違反ではなくなるまでの間、バッファに蓄積してから出力するようにしたものである。
【0050】以下、図6を参照して、第2の実施例におけるセル流量制御装置3の構成を説明する。セル流量制御装置3は、ヘッダ解析部31、Mセルを記憶することのできるバッファ37と、入力セルが出力できるまでの時間を計算するスロット計算部33及びバッファ37への入力と出力を管理するスロット管理部35とからなる。
【0051】スロット計算部33は各仮想チャネルVCのトラヒック特性のパラメータを管理しており、セルが入力されると、現在の時刻から出力が可能となる時刻までの時間Xo を計算し、スロット管理部35に通知する。
【0052】バッファ37はMセル分の記憶領域を持ち、先頭から順に出力されるが、任意の位置に入力できる機能を有する。バッファ37の各領域の空塞がりはスロット管理部35によって管理されており、セル入力時にスロット計算部33から通知されたXo 以降の最も先頭に近い空領域Xを捜して、先頭からX番目に入力セルを記憶すると共に、Xをスロット計算部33に通知する。スロット計算部33では通知されたXの値によってパラメータを更新する。
【0053】このスロット計算部33の構成例を図7に示す。スロット計算部33は各仮想チャネルの情報を記憶するメモリ335、演算部333及びクロック337によって1だけ増加されるN進のカウンタ339とからなる。ここでNは、監視の対象となる仮想チャネルのチャネル数を表すものとする。このメモリ335に記憶される情報は図4に示したメモリ15の情報内容と等しく、演算部333はカウンタ339の値とメモリ335に蓄積されている情報とから図8に示すフローチャートに従って、セルを出力できるまでの時間Xo を求める。
【0054】図8に示すフローチャートにおいて、ステップS111からS127までの動作は図5に示すフローチャートのステップS11からS27までのステップに等しい。
【0055】以下、ステップS127以降に付いて説明すると、ステップS141において Xo =CTR1a−TH(J) (5)
として、Xo を求め、スロット管理部35に送信する。
【0056】ここで、図9を参照して、スロット管理部35の構成例を説明する。Mビットのシフトレジスタ355は、バッファ37の各領域の空塞がりの状態を示すもので、バッファ37のi番目にセルが記憶されている場合には、シフトレジスタ355のi番目のレジスタに1がセットされる。
【0057】スロット計算部33からXo を入力すると、エンコーダ357は、Xo 番目以降で最も先頭に近い0であるレジスタの位置Xを制御部351に出力する。入回線からは複数の仮想チャネルが多重化されて入力されているため、Xo 番目にはすでに他の仮想チャネルのセルが記憶されている可能性があるが、このようにして求めたXは出力可能な最も早い時刻を示している。
【0058】制御部351はバッファ37のX番目の領域にセルを記憶すると共にXをデコーダ353に出力し、デコーダ353は先頭からX番目のレジスタに信号を出力し、このレジスタの値を1にセットする。Xは同時にスロット計算部33に通知される。
【0059】セルがXセル周期後に出力されることが決まると、スロット管理部35では、この仮想チャネルに次のセルが入力されたときに、そのセルに対して出力可能となる時刻を求めるために、メモリ335の値を図10R>0のフローチャートに従って更新する。すなわち、ステップS211では、残りサービス時間CTR1(J)の値を CTR1(J)=max(CTR1a−X,0) (6)
によって更新する。次にステップS213では経過時間カウンタCTR2(J)に−Xを、セル到着時刻PHS(J)にカウンタ339の現在の値CLKを代入する。
【0060】セルの出力は、バッファの先頭から順に行い、同時に、シフトレジスタ355を1ビットだけシフトする。ただし、シフトの際に、末尾のレジスタには0を設定する。また、バッファの先頭の領域が空であるときにはセルを出力しない。
【0061】以上の構成によって、各仮想チャネルのセルは定められた特性に従ってセル流量制御装置3から出力される。
【0062】また、異なる優先権をもったセルが入力された場合には、前記式(5)によって得られるXo が定められた閾値以上である場合には、そのセルを廃棄することとし、その閾値を優先度ごとに異なる値に設定することで優先制御を行うことが可能である。
【0063】上述した第2の実施例においても、直前のセルが出力された時刻と現在時刻との時間間隔を新たなセル到着時に求めることを可能とすることにより、セル到着時にだけリーキバケットカウンタの値を更新し、定められたトラヒック特性を満たす場合に出力できるまでの時間を求めることが可能となる。さらに、セル入力時に出力が可能となる時刻を特定するため、出力時に出力の判定を行う必要がなく、少ない処理量で、トラヒック特性を満たして可能な最も早い時刻に出力することが可能である。
【0064】
【発明の効果】以上、説明したように本発明によれば、多数の仮想チャネルの多重化された伝送路のセル流の制御を行うセル流量制御装置を、少ないハードウェア規模で実現することが可能となる。
【図面の簡単な説明】
【図1】セル流量制御装置の構成例を示す図である。
【図2】残りサービス時間CTR1の更新の様子を現す図である。
【図3】到着時間間隔ΔTとセル到着間隔の関係を示す図である。
【図4】メモリの構成例を示す図である。
【図5】セル流量制御装置の動作を示すフローチャートである。
【図6】第2の実施例のセル流量制御装置の構成例を示す図である。
【図7】スロット計算部の構成例を示す図である。
【図8】Xo を求める動作のフローチャートである。
【図9】スロット管理部の構成例を示す図である。
【図10】メモリの更新のフローチャートである。
【図11】第3の実施例のセル流量制御装置の構成例を示す図である。
【図12】メモリの構成例を示す図である。
【図13】セル流量制御装置の動作を示すフローチャートである。
【図14】ジャンピングウィンドウにおける判定の様子を現す図である。
【図15】ジャンピングウィンドウに基づくセル流量制御装置の動作を示すフローチャートである。
【図16】従来技術における構成例である。
【符号の説明】
1 セル流量制御装置
11 転送制御部
13 演算部
15 メモリ
17 クロック
19 カウンタ
101 到着監視部
105 カウンタ
107 クロック
109 カウンタ
111 レジスタ
113 比較器
115 比較器
117 レジスタ
3 セル流量制御装置
31 ヘッダ解析部
33 スロット計算部
35 スロット管理部
37 バッファ
333 演算部
335 メモリ
337 クロック
339 カウンタ
351 制御部
353 デコーダー
355 シフトレジスタ
357 エンコーダー
5 セル流量制御装置
51 転送制御部
53 演算部
55 メモリ
57 クロック
59 カウンタ
【0001】
【産業上の利用分野】本発明は、ATM交換方式におけるセル流量制御装置に関する。
【0002】
【従来の技術】近年、高速かつ広帯域なB−ISDN網等を実現する網アーキテクチャとしてのATM(Asynchronous Transfer Mode)交換方式が注目されており、このATM交換方式は、固定長で区切られた情報毎にルーティング情報等を示すヘッダを付与したセルを情報単位として伝送路上でラベル多重し、交換ノードではこのヘッダの情報のみを参照してセル単位で交換動作を行うものである。また、このATM交換方式は、旧来の回線交換方式とは異なり各通信に固定の通信帯域を割り当てることは無く、複数の通信が単一の通信帯域を共有して通信を行うようにしている。
【0003】このATM交換を利用して、通信を開始するときは、発端末とATM交換網との間で必要なトラヒック特性と通信品質との取り決めを行い、ATM交換網では申告されたトラヒック特性をもったセル流が流入した場合に要求された通信品質を提供できるか否かを判定し、要求された通信品質を提供できると判定されたときには着端末との間に仮想チャネルVC(Virtual Chanel)を設定し、セルの転送が発端末と着端末との間で行われる。前述したように、この仮想チャネルVCには固定の通信帯域が割り当てられるわけではないので、事前に定められた以上のセル流を発生すると、定められた通信品質を提供できない。そのため、ATM交換網においては、各仮想チャネルVCのトラヒック特性が申告された特性を満たしているかどうかを監視するポリシング機能が必要となり、端末においても発生するトラヒックを申告した通りの特性で出力するためのシェイピング機能が必要となる。
【0004】この様なセル流の監視、制御を行う方式としてはリーキパケットを用いた方式が知られている(J.S.Turner,"New Directions in Communications",pp8-15,IEEE Communications Magazine,vol.24,No.10,October 1986 )。従来のリーキバケットの構成例を図11に示す。
【0005】図11において、到着監視部101はセルの到着を検出すると、AND回路103を介して、カウンタ105をインクリメントする。このとき、AND回路103の他側には比較器115からの出力が入力される。また、単位時間周期のクロックを発生するクロック107から出力されるクロック信号でカウンタ109をインクリメントし、このカウンタ109の値Aと一定値Tを記憶するレジスタ111の出力、閾値Bとを比較器113において比較し、一致した場合(A=B)にカウンタ105を1だけデクリメントすると共にカウンタ109をリセットする。なお、カウンタ105の値が0である場合には、比較器113においてA=Bとなった場合にもそれ以上カウンタ105の値をデクリメントしない。
【0006】また、同時にカウンタ105の値を比較器115に出力し、このカウンタ105の値Aとレジスタ117からの出力Bとを比較し、一致しているとき(A=B)に到着したセルを違反と判定し、到着監視部101において廃棄する。
【0007】上述したように、ATM交換網では一つの回線上には複数の仮想チャネルVCが多重化されることがあり、各仮想チャネルVCに対してセル流の監視を独立に行わなければならない。しかし、各仮想チャネルVCのパラメータは必ずしも等しい値を持たないので、時間周期の測定などは独立に行う必要がある。このような複数の仮想チャネルVCを監視するためには、図11に示したリーキバケットをセル流の監視を行う仮想チャネル数だけ用意して、かつ並行して動作させることで実現できる。しかしながら、ハードウェア量が仮想チャネルVC数に比例して増加するため、多数の仮想チャネルVCが多重化される場合の流量制御装置が非常に大規模になる。そこで、ハードウェア量を低減させるために、カウンタの値などをメモリ上に記憶し、一つの演算装置を複数の仮想チャネルVCで共用して、メモリに記憶されている値を更新してリーキバケットを実現する構成も考えられるが、メモリのアクセス速度、演算装置の処理能力などの制約によって、監視を行うことができる仮想チャネルVC数が制限され、多数の仮想チャネルVCを監視することができない。従って、このような構成を用いても仮想チャネルVC数が大なるときには、複数の装置を並列に動作させなければならず、この場合にもハードウェア量が増加してしまう。
【0008】次に本発明の第3の実施例について説明する。第3の実施例のセル流量制御装置5は、入回線上に多重化された仮想チャネルのセル流をスライディングウィンドウに基づいて監視し、定められたパラメータに違反したセルを廃棄する。すなわち、セルが入力された時に、そのセルの属する仮想チャネルにおいて(X0−1)個前に到着したセルの到着時刻から現在時刻までの経過時間TM(以下モニタリング時間と呼ぶ)が監視周期T0未満であるときには、入力セルを違反セルであると判定し、廃棄する。この様な機能を実現するために、セル流量制御装置5は図11に示されるように転送制御部51、演算部53、メモリ55、クロック57、カウンタ59から構成される。転送制御部51、クロック57、カウンタ59の動作は第1の実施例における転送制御部11、クロック17、カウンタ19の動作とそれぞれ等しい。また、メモリ55は図12に示される構成の情報を有する。すなわちチャネル0からチャネル(N−1)のN個の仮想チャネルのそれぞれに、モニタリング時間TM(0)〜(N−1)、セル到着間隔DT(0、0)〜DT(0、L−1)〜(J、0)〜DT(J、L−1)〜(N−1、0)〜DT(N−1、L−1)、セル到着間隔ポインタn(0)〜、(J)、〜(N−1)、監視周期T0(0)〜、(J)、〜(N−1)、最大セル数X0(0)〜、(J)、〜(N−1)、セル到着時刻PHS(0)〜、(J)、〜(N−1)、経過時間カウンタCTR2(0)〜、(J)、〜(N−1)をテーブルとして持つ。モニタリング時間TM(J)は(X0−1)個前に到着したセルの到着時刻から最後に到着したセルの到着時刻までの経過時間を記憶する。セル到着間隔DT(J、0)〜DT(J、L−1)は過去L個のセルの到着間隔を記憶し、セル到着間隔ポインタn(J)が最も新しい到着間隔を記憶するセル到着間隔を示す。すなわち、DT(J、n(J))が最も新しいセル到着間隔である。これらの値を用いて、演算部53では図13に示されるフローチャートにしたがって演算を行い、違反判定を行う。ステップS211からS225までの動作は図5に示すフローチャートのステップS11からS25までのステップに等しいので、ステップS227以降について説明する。ステップS227においてTM´を次式によって求める。
【0009】
TM´=TM(J)−DT(J、n(J)−X0(J)+1)+ΔT (7)
ただし、上式でn(J)−X0(J)+1が負になる場合には、Lでモジュロをとった値を用いる。TM´はX0(J)−1個前に到着したセルの到着時刻から現在までの経過時間であり、ステップS229においてTM´をT0(J)と比較する。TM´がT0(J)以上である場合には、入力されたセルは違反セルではないので出回線に出力し(ステップS231)、次に到着するセルの判定を行うためにステップS233でn(J)の値を1増加させ、ステップS235においてこのn(J)で定まるセル到着間隔DT(J、n(J))にΔTを記憶し、TM(J)にTM´を記憶する。次にステップS237でセル到着時刻PHS(J)に現在のカウンタ59の値を設定し、経過時間カウンタCTR2(J)を0にリセットする。ステップS229においてTM´がT0(J)より小さい場合には、ステップS239において入力セルを廃棄する。
【0010】また、スライディングウィンドウを用いた場合にも第2の実施例のセル流量制御装置3のように出回線に出力しても違反とならない時刻までセルをバッファに蓄積してから出力するセル流量制御装置を構成することも可能である。スライディングウィンドウを用いる場合には、出力することが可能となる時刻までに必要な時間間隔は、監視周期T0とTM´との差(T0−TM´)であるので、現在の時刻から(T0−TM´)以降でありかつ出力可能である最初の時刻に出力するようにバッファからのセルの出力を制御すれば良い。
【0011】上述の第3の実施例におけるセル流量制御装置においても、第1、第2の実施例におけるセル流量制御装置と同じく、到着したセルの属する仮想チャネルに関した情報だけを用いてセル流量の制御が可能となっている。
【0012】また、リーキーバケット、スライディングウィンドウの他にセル流の監視・制御を行う方式として、ジャンピングウィンドウ、トリガードジャンピングウィンドウなどが知られている。ジャンピングウィンドウは、図14に示されるように、T1時間周期でそれぞれのT1時間内の入力セル数を計測し、定められた最大セル数X1を越えて入力されたセルを違反とする。また、トリガードジャンピングウィンドウでは、T1時間経過後、最初にセルが到着した時刻にT1時間のウィンドウをリセットし、これからT1時間以内にX1セルを越えたセルが入力したときに、このセルを違反とする。このようなジャンピングウィンドウもしくはトリガードジャンピングウィンドウにもとづいたセル流量制御装置を、上述の第1の実施例および第3の実施例におけるセル流量制御装置と同様の構成で実現することができる。ジャンピングウィンドウに基づく場合には、メモリに仮想チャネルごとにセル数カウンタN(0)〜N(J)〜N(N−1)、監視周期T1(0)〜T1(J)〜T1(N−1)、最大セル数X1(0)〜X1(J)〜X1(N−1)、セル到着位相PHS(0)〜PHS(J)〜PHS(N−1)、経過時間カウンタCTR2(0)〜CTR2(J)〜CTR2(N−1)を有する。このセル流量制御装置の動作のフローチャートを図15に示す。ステップS311〜S325までの動作は、図5のステップS11〜からステップS25までの動作に等しい。次にステップS327においてΔTとT1(J)とを比較し、ΔTがT1(J)より小さい場合には、ステップS329においてN(J)とX1(J)との比較を行う。N(J)がX1(J)より小さい場合には、ステップS331でセルを出回線に出力し、ステップS333でN(J)の値を1増加させる。ステップS329においてN(J)がX1(J)以上である場合には入力セルは違反セルであるので、ステップS335で廃棄する。また、ステップS327においてΔTがT1(J)以上である場合には、新しい周期に移行しているので、ステップS337でN(J)をセルを出力し、ステップS339でN(J)に1を代入する。次にステップS341で新しい周期における経過時間を計測するためにCTR2(J)にΔTをT1(J)でモジュロをとった値を代入し、PHS(J)にCLKを代入する。トリガードジャンピングウィンドウにもとづいてセル流を制御するセル流量制御装置においては、動作のフローチャートが異なり、図15のステップS341でCTR2(J)にΔTをT1(J)でモジュロをとった値を代入する変わりに0を代入すればよい。この場合にも、1セル時間に必要な情報は、一つの仮想チャネルVCの情報だけであるので少ないハードウェア量でセル流量制御装置を構成することができる。
【0013】また、違反と判定された場合に、この違反と判定されたセルを廃棄せずに、出力されても違反とならない時刻までバッファに蓄積してから出力する制御もある。例えば、本出願人によって先に出願されている特願平2−217216に述べられているように、従来はバッファからセルを出力する度に、蓄積されているセルのそれぞれが違反となるか否かを調べて、出力可能であるセルを捜して出力する構成がとられていた。しかし、この様な構成では、上述のリーキバケット実現に大きなハードウェアが必要であることに加えて、出力可能なセルを捜すために必要な処理量が大きくなる。
【0014】
【発明が解決しようとする課題】上述したように、従来は、多重化されている仮想チャネルVCのセル流を監視するセル流量制御装置は、仮想チャネルVC数が大きいとき、ハードウェア量が増大して実現が困難である。さらに、違反ではなくなるまでの間、バッファに蓄積して出力する場合には、出力されるセルを決定するための処理量が大きくなり、処理時間の増大を招来するところとなった。
【0015】本発明は、以上のような状況に鑑みてなされたものであり、対象となる仮想チャネルVC数が大きい場合でも、仮想チャネルVC数に比例したハードウェア量を必要とすることのないセル流量制御装置を実現するものである。
【0016】
【課題を解決するための手段】上記目的を達成するために、本願第1の発明は、複数の仮想チャネルが多重化された伝送路上のセル流を制御するセル流量制御装置において、前記仮想チャネルのそれぞれに対して任意に設定される始点からの経過時間を計測する経過時間計測手段と、前記仮想チャネルのそれぞれに対して、到着するセルの流量を計測する流量計測手段と、新たなセルが到着したときに当該セルが属する仮想チャネルに対する前記流量計測手段の値を、前記経過時間計測手段によって得られた現在の時刻までの経過時間に係る値に更新する演算手段と、この演算手段の演算結果に基づいてセルの転送制御を行う制御手段とを有することを要旨とする。
【0017】また、本願第2の発明は、複数の仮想チャネルが多重化された伝送路上のセル流を制御するセル流量制御装置において、入力されるセルが出力可能となる時刻までの、現在の時刻からの時間差を求める計算手段と、前記計算手段で求められた時間差以降の出力が予約されていない時刻に出力を予約する予約手段と、前記予約手段によって予約された時刻にセルの出力を行う制御手段とを有することを要旨とする。
【0018】
【作用】本願第1の発明によれば、任意の時点において、任意に設定される始点、例えば直前のセルが到着してから、あるいはメモリから読み出したときからの経過時間を知る経過時間計測手段を持つことによって、セルが到着した時に一括して流量計測手段の値を更新することが可能となるので、同時に複数の仮想チャネルVCの情報をアクセスする必要がなく、仮想チャネルVC数に関わりなく仮想チャネルVC毎に必要な値をメモリ上に蓄積し、単一の演算手段をもちいて監視を行うことが可能となる。これによって、仮想チャネルVC数が大なる場合においてもセル流量制御装置を構成するために必要なハードウェア量を大きく低下することが可能である。
【0019】また、本願第2の発明によれば、セル入力時にセルの出力が可能となる時刻を求め、この時刻以降で最初に予約されていない時刻にセルの出力を予約し、予約された時刻にセルを出力することで、出力時にはバッファ内のセルの出力可否の判定を行わずに、定められた特性でセルの出力を行うことが可能となる。
【0020】
【実施例】以下、本発明の一実施例を図面を参照して説明する。図1は本発明の第1の実施例におけるセル流量制御装置1の構成を示すブロック図である。
【0021】まず、図1を参照して本実施例のセル流量制御装置1の構成を説明する。このセル流量制御装置1は、入回線上に多重化されたNチャネルの仮想チャネルのセル流量の流量監視を行うもので、制御手段としての転送制御部11、演算手段としての演算部13、メモリ15、クロック17及び経過時間計測手段としてのカウンタ7によって構成される。尚、このNチャネルの仮想チャネルには予め0から(N−1)までの仮想チャネル番号が付与されているものとする。
【0022】転送制御部11は、入回線から入力されるセルのヘッダ情報から仮想チャネル番号を識別し、この転送制御部11に接続される演算部13に仮想チャネル番号を通知するものである。
【0023】演算部13は、転送制御部11から通知された仮想チャネル番号をもとにしてメモリ15に記憶されている当該仮想チャネルに対応する情報を読みだし、この情報に基づく判定結果を転送制御部11に通知する。この演算部13における判定結果が違反セルであるとき、転送制御部11は当該入力セルを廃棄する。また、違反セルではないと判定されたときには、当該入力セルは出回線に出力される。
【0024】クロック17はセル周期の信号を発生し、カウンタ19はクロック17の発生する信号によって動作するN進のカウンタである。すなわち、カウンタ19の値が(N−1)であるとき、次のクロックが入力されるとカウンタ19の値が0となる。ただし、セル周期は入回線もしくは出回線上で1セルの転送に要する時間を示すものとする。
【0025】次に、セル流量制御装置1の作用を説明する。本来のリーキバケットでは、従来の技術の欄で説明したように、セルが到着すると1だけインクリメントされ、一定時間T毎に1だけデクリメントされるカウンタを持ち、このカウンタの値がしきい値B以上である時に到着したセルが違反セルと判定されるものである。
【0026】このカウンタ19の値は、1セルのサービス時間がTである待ち行列システムのキュー長を示していると見なすことができ、従ってリーキバケットにおける判定は、この待ち行列システムのシステム内セル数が(B−1)以下である場合に違反ではないと判定することに等しい。この待ち行列システムにおいて、サービス中のセルが出力されるまでの残り時間と、待ち行列に並んでいるセルが必要とするサービス時間との合計を残りサービス時間CTR1としたとき、システム内セル数が(B−1)以下であるという条件は、 CTR1≦TH (1)
ただし、閾値TH=T×(B−1)
と書ける。
【0027】また、図2に示すように、新たなセルが到着した時の残りサービス時間CTR1new は、一つ前のセルが到着した時点での残りサービス時間CTR1old と到着時間間隔ΔTによって CTR1mew =max(CTR1old +T−ΔT,0) (2)
となるので、残りサービス時間CTR1old と到着時間間隔ΔTが分かれば、上述の式を用いて求められる残りサービス時間CTR1new と閾値THとを比較して、入力セルの違反判定を行うことができる。
【0028】以下、到着時間間隔ΔTの算出に付いて説明する。ここでは、カウンタ19を用いて到着時間間隔ΔTを求めるために、仮想チャネルVC毎にセル到着時刻PHSと経過時間カウンタCTR2を用いる。
【0029】入回線を介して、新たなセルが到着するとセル到着時刻PHSにはその時点でのカウンタ19の値がセットされる。経過時間カウンタCTR2は、セルが到着すると0にリセットされ、カウンタ19が仮想チャネルVCに定められた値を示す度に仮想チャネルのチャネル数に等しい値Nが加えられる。ここでは、チャネルJの経過時間カウンタCTR2はカウンタ19の値がJとなったときに増加されるものとする。経過時間カウンタCTR2の値を、このように更新することによって、各セル周期には1つの仮想チャネルの経過時間カウンタCTR2だけを増加すれば良くなる。
【0030】経過時間カウンタCTR2は、Nセル周期ごとにしか増加されないため、正確なセルの到着間隔を示していないが、前のセルが到着したときのカウンタ19の値を記憶しているセル到着時刻PHSと現在のカウンタ19の値CLKを用いると正確な到着時間間隔ΔTを求めることができる。
【0031】到着時間間隔ΔTと経過時間カウンタCTR2、セル到着時刻PHSおよびカウンタ19の値CLKとの関係は、セル到着時刻PHSと経過時間カウンタCTR2がN増加されるときのカウンタ19の値Jの関係と、現在のカウンタ19の値CLKとJの関係によって場合分けされ、以下の式(3−1),(3−2),(3−3)で到着時間間隔ΔTは与えられる。図3にこの様子を示す。
【0032】すなわち、図3(3) 及び(1) の場合は、PHS(J)≧J,CLK≧JまたはPHS(J)<J,CLK<Jの時の到着時間間隔ΔTが、 ΔT=CTR2(J)+CLK−PHS(J) (3−1)
で与えられ、図3(2) の場合は、PHS(J)<J,CLK≧Jの時の到着時間間隔ΔTが、 ΔT=CTR2(J)+CLK−PHS(J)−N (3−2)
で与えられ、図3(4) の場合は、PHS(J)≧J,CLK<Jの時の到着時間間隔ΔTが、 ΔT=CTR2(J)+CLK−PHS(J)+N (3−3)
で与えられることを、それぞれ示すものである。
【0033】また、カウンタ19の周期を、監視するチャネル数Nと等しくしているので、各セル周期には1つの仮想チャネルVCの経過時間カウンタCTR2を増加すれば良い。
【0034】以上述べたアルゴリズムを実現するために、メモリ15は図4に示される構成の情報を有する。すなわち、チャネル0からチャネル(N−1)のN個の仮想チャネルのそれぞれに、残りサービス時間CTR1(0),〜,(J),〜,(N−1)、しきい値TH(0),〜,(J),〜,(N−1)、1セルのサービス時間T(0),〜,(J),〜,(N−1)、セル到着時刻PHS(0),〜,(J),〜,(N−1)、経過時間カウンタCTR2(0),〜,(J),〜,(N−1)をテーブルとして持つ。ここでJは対応する仮想チャネル番号を示す。
【0035】セル到着時刻PHS(J)、経過時間カウンタCTR2(J)はこの仮想チャネルにおいて直前にセルが入力されてらかの経過時間を求めるために用いられ、残りの値によってリーキバケットを構成する。
【0036】次に、図5に示すフローチャートを参照して、各セル周期でのセル流量制御装置1の作用を説明する。以下、入回線を介して仮想チャネル番号Jのセルが入力され、このセルの仮想チャネル番号が転送制御部11において当該セルのヘッダ情報から識別される場合を例に説明する。
【0037】まず、セル周期の初めにステップS11において、後段のステップでのΔTの算出を可能にするために、予めカウンタ19の値CLKに等しい仮想チャネル番号の経過時間カウンタCTR2の値に仮想チャネルのチャネル数に等しい値Nを加えておく。
【0038】また、ΔTは(CTR1+T)より大きい場合には、後述する動作はΔTの値に影響されないので、CTR2が適当な閾値以上である時にはNを加えないようにすることで、CTR2がオーバフローを生じることがないようにすることができる。さらに、CTR2にはカウンタ19の値が仮想チャネル番号に等しくなった回数だけを記憶するようにして、必要なときにこれをN倍して用いる構成も可能である。
【0039】次に、ステップS13において、セルの入力がなければ(NO)、このセル周期での動作を終了する。一方、入回線を介してセルが入力された場合(YES)には、ステップS15に進み、この入力され到着したセルの仮想チャネル番号Jに対応するセル到着時刻PHS(J)の値とカウンタ19の値CLKとを比較する。ここで、PHS(J)≧Jならば、ステップS17に進む。このとき、図3に示す(3) 、(4) が選択されたことになる。また、PHS(J)<Jならば、ステップS19に進む。このとき図3に示す(1)、(2) が選択されたことになる。
【0040】次にステップS17,S19において、仮想チャネル番号Jとカウンタ19の値CLKとの比較を行う。ステップS17で、CLK≧Jならば、ステップS23に進み、CLK<Jならば、ステップS21に進む。このとき、ステップS23は図3(3) に対応する式(3−1)が、ステップS21は同(4) に対応する式(3−3)がそれぞれ選択されたことになる。
【0041】一方、ステップS19で、CLK≧Jならば、ステップS25に進み、CLK<Jならば、ステップS23に進む。このとき、ステップS25は図3(2) に対応する式(3−2)が、ステップS23は同(1) に対応する式(3−1)がそれぞれ選択されたことになる。
【0042】この比較の結果を用いて、経過時間、すなわち到着時間間隔ΔTを式(3−1),(3−2),(3−3)に基づいて求める。
【0043】なお、このとき仮想チャネルJの経過時間カウンタCTR2(J)は、必ずしもカウンタ19の値CLKがJである時に増加される必要はなく、一定時間周期に更新されればよい。その場合には、ステップS15,S17,S19においてJの変わりに経過時間カウンタCTR2(J)が更新される時のカウンタ19の値を用いる。
【0044】次にステップS27で、経過時間ΔTを用いて次式(4)に従って次の残りサービス時間CTR1aを求める。
【0045】
CTR1a=max{CTR1(J)+T(J)−ΔT,0} (4)
さらに、ステップS29において、式(4)で求めた残りサービス時間CTR1aを閾値TH(J)とを比較し、流量違反の判定を行う。
【0046】ここで、残りサービス時間CTR1aが閾値TH(J)以下であるときには、ステップS31に進み、当該入力セルを出回線に出力し、さらにステップS33で残りサービス時間CTR1(J)に残りサービス時間CTR1aを代入する。次に、ステップS35で経過時間カウンタCTR2(J)の値を0に、セル到着時刻PHS(J)に現在のカウンタ19の値CLKを代入する。
【0047】また、ステップS29において、残りサービス時間CTR1(J)がサービス時間T(J)より大きい場合には、入力セルは違反セルであるため、ステップS37で入力セルを転送制御部11において廃棄する。
【0048】上述してきたように、本実施例のセル流量制御装置は、仮想チャネル毎にセル到着時刻PHS(J)と経過時間カウンタCTR2(J)を持つことで、単一のカウンタ19を用いてセル到着時にセルの到着時間間隔を求めることが可能であり、仮想チャネル毎に時間間隔を計測するカウンタを持つことが不要となる。さらに、セル到着時に一つ前のセルが到着した時刻からの経過時間を得ることが可能となったことにより、リーキバケットのカウンタをセル到着時に一括して更新することができる。従来のように各仮想チャネルのカウンタを一定時間周期でデクリメントすることが必要ではなくなり、1セル周期において更新しなければならないリーキバケットカウンタは常に僅かに1個であることが保証される。そこでこれらの値をメモリ上に蓄積し、すべての仮想チャネルに共通に使用される演算部によってリーキバケットのカウンタを更新し、違反の判定を行うことが可能となった。メモリ素子は論理素子に比べて高集積に実現可能であるため、監視されなければならない仮想チャネル数が大きな場合にも従来に比べて小さなハードウェア規模でセル流量制御装置を実現することができる。
【0049】次に、第2の実施例におけるセル流量制御装置3について説明する。このセル流量制御装置3は、入力されたセルが規定されたセル流の特性に反している場合には、違反ではなくなるまでの間、バッファに蓄積してから出力するようにしたものである。
【0050】以下、図6を参照して、第2の実施例におけるセル流量制御装置3の構成を説明する。セル流量制御装置3は、ヘッダ解析部31、Mセルを記憶することのできるバッファ37と、入力セルが出力できるまでの時間を計算するスロット計算部33及びバッファ37への入力と出力を管理するスロット管理部35とからなる。
【0051】スロット計算部33は各仮想チャネルVCのトラヒック特性のパラメータを管理しており、セルが入力されると、現在の時刻から出力が可能となる時刻までの時間Xo を計算し、スロット管理部35に通知する。
【0052】バッファ37はMセル分の記憶領域を持ち、先頭から順に出力されるが、任意の位置に入力できる機能を有する。バッファ37の各領域の空塞がりはスロット管理部35によって管理されており、セル入力時にスロット計算部33から通知されたXo 以降の最も先頭に近い空領域Xを捜して、先頭からX番目に入力セルを記憶すると共に、Xをスロット計算部33に通知する。スロット計算部33では通知されたXの値によってパラメータを更新する。
【0053】このスロット計算部33の構成例を図7に示す。スロット計算部33は各仮想チャネルの情報を記憶するメモリ335、演算部333及びクロック337によって1だけ増加されるN進のカウンタ339とからなる。ここでNは、監視の対象となる仮想チャネルのチャネル数を表すものとする。このメモリ335に記憶される情報は図4に示したメモリ15の情報内容と等しく、演算部333はカウンタ339の値とメモリ335に蓄積されている情報とから図8に示すフローチャートに従って、セルを出力できるまでの時間Xo を求める。
【0054】図8に示すフローチャートにおいて、ステップS111からS127までの動作は図5に示すフローチャートのステップS11からS27までのステップに等しい。
【0055】以下、ステップS127以降に付いて説明すると、ステップS141において Xo =CTR1a−TH(J) (5)
として、Xo を求め、スロット管理部35に送信する。
【0056】ここで、図9を参照して、スロット管理部35の構成例を説明する。Mビットのシフトレジスタ355は、バッファ37の各領域の空塞がりの状態を示すもので、バッファ37のi番目にセルが記憶されている場合には、シフトレジスタ355のi番目のレジスタに1がセットされる。
【0057】スロット計算部33からXo を入力すると、エンコーダ357は、Xo 番目以降で最も先頭に近い0であるレジスタの位置Xを制御部351に出力する。入回線からは複数の仮想チャネルが多重化されて入力されているため、Xo 番目にはすでに他の仮想チャネルのセルが記憶されている可能性があるが、このようにして求めたXは出力可能な最も早い時刻を示している。
【0058】制御部351はバッファ37のX番目の領域にセルを記憶すると共にXをデコーダ353に出力し、デコーダ353は先頭からX番目のレジスタに信号を出力し、このレジスタの値を1にセットする。Xは同時にスロット計算部33に通知される。
【0059】セルがXセル周期後に出力されることが決まると、スロット管理部35では、この仮想チャネルに次のセルが入力されたときに、そのセルに対して出力可能となる時刻を求めるために、メモリ335の値を図10R>0のフローチャートに従って更新する。すなわち、ステップS211では、残りサービス時間CTR1(J)の値を CTR1(J)=max(CTR1a−X,0) (6)
によって更新する。次にステップS213では経過時間カウンタCTR2(J)に−Xを、セル到着時刻PHS(J)にカウンタ339の現在の値CLKを代入する。
【0060】セルの出力は、バッファの先頭から順に行い、同時に、シフトレジスタ355を1ビットだけシフトする。ただし、シフトの際に、末尾のレジスタには0を設定する。また、バッファの先頭の領域が空であるときにはセルを出力しない。
【0061】以上の構成によって、各仮想チャネルのセルは定められた特性に従ってセル流量制御装置3から出力される。
【0062】また、異なる優先権をもったセルが入力された場合には、前記式(5)によって得られるXo が定められた閾値以上である場合には、そのセルを廃棄することとし、その閾値を優先度ごとに異なる値に設定することで優先制御を行うことが可能である。
【0063】上述した第2の実施例においても、直前のセルが出力された時刻と現在時刻との時間間隔を新たなセル到着時に求めることを可能とすることにより、セル到着時にだけリーキバケットカウンタの値を更新し、定められたトラヒック特性を満たす場合に出力できるまでの時間を求めることが可能となる。さらに、セル入力時に出力が可能となる時刻を特定するため、出力時に出力の判定を行う必要がなく、少ない処理量で、トラヒック特性を満たして可能な最も早い時刻に出力することが可能である。
【0064】
【発明の効果】以上、説明したように本発明によれば、多数の仮想チャネルの多重化された伝送路のセル流の制御を行うセル流量制御装置を、少ないハードウェア規模で実現することが可能となる。
【図面の簡単な説明】
【図1】セル流量制御装置の構成例を示す図である。
【図2】残りサービス時間CTR1の更新の様子を現す図である。
【図3】到着時間間隔ΔTとセル到着間隔の関係を示す図である。
【図4】メモリの構成例を示す図である。
【図5】セル流量制御装置の動作を示すフローチャートである。
【図6】第2の実施例のセル流量制御装置の構成例を示す図である。
【図7】スロット計算部の構成例を示す図である。
【図8】Xo を求める動作のフローチャートである。
【図9】スロット管理部の構成例を示す図である。
【図10】メモリの更新のフローチャートである。
【図11】第3の実施例のセル流量制御装置の構成例を示す図である。
【図12】メモリの構成例を示す図である。
【図13】セル流量制御装置の動作を示すフローチャートである。
【図14】ジャンピングウィンドウにおける判定の様子を現す図である。
【図15】ジャンピングウィンドウに基づくセル流量制御装置の動作を示すフローチャートである。
【図16】従来技術における構成例である。
【符号の説明】
1 セル流量制御装置
11 転送制御部
13 演算部
15 メモリ
17 クロック
19 カウンタ
101 到着監視部
105 カウンタ
107 クロック
109 カウンタ
111 レジスタ
113 比較器
115 比較器
117 レジスタ
3 セル流量制御装置
31 ヘッダ解析部
33 スロット計算部
35 スロット管理部
37 バッファ
333 演算部
335 メモリ
337 クロック
339 カウンタ
351 制御部
353 デコーダー
355 シフトレジスタ
357 エンコーダー
5 セル流量制御装置
51 転送制御部
53 演算部
55 メモリ
57 クロック
59 カウンタ
【特許請求の範囲】
【請求項1】 複数の仮想チャネルが多重化された伝送路上のセル流を制御するセル流量制御装置において、前記仮想チャネルのそれぞれに対して任意に設定される始点からの経過時間を計測する経過時間計測手段と、前記仮想チャネルのそれぞれに対して、到着するセルの流量を計測する流量計測手段と、新たなセルが到着したときに当該セルが属する仮想チャネルに対する前記流量計測手段の値を、前記経過時間計測手段によって得られた現在の時刻までの経過時間に係る値に更新する演算手段と、この演算手段の演算結果に基づいてセルの転送制御を行う制御手段とを有することを特徴とするセル流量制御装置。
【請求項2】 複数の仮想チャネルが多重化された伝送路上のセル流を制御するセル流量制御装置において、入力されるセルが出力可能となる時刻までの、現在の時刻からの時間差を求める計算手段と、前記計算手段で求められた時間差以降の出力が予約されていない時刻に出力を予約する予約手段と、前記予約手段によって予約された時刻にセルの出力を行う制御手段とを特徴とするセル流量制御装置。
【請求項1】 複数の仮想チャネルが多重化された伝送路上のセル流を制御するセル流量制御装置において、前記仮想チャネルのそれぞれに対して任意に設定される始点からの経過時間を計測する経過時間計測手段と、前記仮想チャネルのそれぞれに対して、到着するセルの流量を計測する流量計測手段と、新たなセルが到着したときに当該セルが属する仮想チャネルに対する前記流量計測手段の値を、前記経過時間計測手段によって得られた現在の時刻までの経過時間に係る値に更新する演算手段と、この演算手段の演算結果に基づいてセルの転送制御を行う制御手段とを有することを特徴とするセル流量制御装置。
【請求項2】 複数の仮想チャネルが多重化された伝送路上のセル流を制御するセル流量制御装置において、入力されるセルが出力可能となる時刻までの、現在の時刻からの時間差を求める計算手段と、前記計算手段で求められた時間差以降の出力が予約されていない時刻に出力を予約する予約手段と、前記予約手段によって予約された時刻にセルの出力を行う制御手段とを特徴とするセル流量制御装置。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図12】
【図8】
【図14】
【図9】
【図16】
【図10】
【図11】
【図13】
【図15】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図12】
【図8】
【図14】
【図9】
【図16】
【図10】
【図11】
【図13】
【図15】
【公開番号】特開平5−130125
【公開日】平成5年(1993)5月25日
【国際特許分類】
【出願番号】特願平3−291435
【出願日】平成3年(1991)11月7日
【出願人】(000003078)株式会社東芝 (54,554)
【公開日】平成5年(1993)5月25日
【国際特許分類】
【出願日】平成3年(1991)11月7日
【出願人】(000003078)株式会社東芝 (54,554)
[ Back to top ]