JP3565629B2

JP3565629B2 - Cell output band regulation device

Info

Publication number: JP3565629B2
Application number: JP23248095A
Authority: JP
Inventors: 潔霜越; 文聡真崎
Original assignee: Oki Electric Industry Co Ltd
Current assignee: Oki Electric Industry Co Ltd
Priority date: 1995-09-11
Filing date: 1995-09-11
Publication date: 2004-09-15
Anticipated expiration: 2015-09-11
Also published as: JPH0983525A

Description

【０００１】
【発明の属する技術分野】
この発明は、非同期転送モード型の通信網において、各交換／伝送装置からのセル送出速度が申告値通りになるよう制御するセル出力帯域規制装置に関するものである。
【０００２】
【従来の技術】
近年、情報通信の分野においては、通信ニーズの多様化、情報交換／伝送技術の高度化、デバイス技術の発展等に伴い、ユーザ情報を高速、広帯域で交換、伝送可能な高速広帯域サービス統合デジタル網（以下、Ｂ−ＩＳＤＮ）の実用化が急速に進められている。
【０００３】
このＢ−ＩＳＤＮにおいては、情報転送方式として非同期転送モード（以下、ＡＴＭと呼ぶ）が採用されている。このＡＴＭ通信においては、情報はセルと呼ばれる固定長のパケットで転送、交換される。この場合、セルの転送先は各セル毎に付与される相手先アドレス情報に基づいて識別される。従って、従来の時分割方式の回線交換とは異なり、各端末は空いている時間軸上のスロットの任意位置にセルを送出することができ、網内でも伝送路上の任意位置へのセル多重が可能となる。
【０００４】
このため、ＡＴＭ通信では、予め使用するセル通信帯域（例えば、ピークセルレートや平均セルレート）を各端末に通信開始前に申告させ、網側では、その申告情報に基づいて帯域管理が行なわれる。この網内帯域管理機能の１つにセル出力帯域規制機能（以下、シェイパーと呼ぶ）がある。シェイパー機能は、網内での多重、交換処理の際、同時刻に同一方路へと向かう複数のセルが到着した場合に、出力待ち合わせによって発生するセル遅延ゆらぎ（以下、ＣＤＶと略する）を吸収し、ユーザ申告値に従ってセルを出力回線へと送出させる機能である。
【０００５】
従来、シェイパー機能の実現方式としていくつか提案されている。そのうちの１つとして、スペーシングポリサー（ＳｐａｃｉｎｇＰｏｌｉｃｅｒ）方式がある。この方式は、到着セル毎に申告値を満足する送出予定時刻を算出し、その送出予定時刻毎にキューイングされたセルを順次１セルずつ読み出して送出していくことにより、網内で発生するＣＤＶの軽減やユーザ申告値を満足するセル送出の実現を図っている。
【０００６】
図２は、このようなシェイパー機能を実現するシェイパー装置の基本構成を示すブロック図である。
【０００７】
図２において、シェイパー装置２０１は、到着セル毎に送出予定時刻τを算出する送出予定時刻算出部２０２と、到着セルを一旦格納し送出予定時刻τに従ってセル送出のスケジューリングを行なうセルスケジューラ部２０３と、送出予定時刻算出部２０２及びセルスケジューラ部２０３へ現在時刻情報ＣＴを与える時計２０４とから構成されている。ここで、送出予定時刻算出部２０２は、通信中の全コネクションについてユーザ申告値情報や後述する各種パラメータを保持している。また、時計２０４は１セル時間に１ずつ現在時刻ＣＴをインクリメントするものである。
【０００８】
セル２０５がシェイパー装置２０１に到着すると、送出予定時刻算出部２０２は、そのセルが属するコネクションの情報から、当該セルをセルスケジューラ部２０３内でどれほど遅延されれば申告値を満足するかを規定する所要遅延時間を求め、それを元に送出予定時刻τを算出し、セルスケジューラ部２０３へ提供する。セルスケジューラ部２０３では、受け取った送出予定時刻τに基づき、セルを送出予定時刻毎にキューイングされたセルバッファ部の最後尾に格納し、時計２０４からの現在時刻情報ＣＴの経過に従って、その現在時刻ＣＴに対応したセル２０６を送出していく。
【０００９】
図３は、従来の送出予定時刻算出部２０２による処理を示すフローチャートである。なお、図３における「：＝」は、その左側のパラメータの値や状態値を、右側の値や状態値に設定することを意味しており、後述する他のフローチャートでも同様である。
【００１０】
図３に示す処理方法は、到着セルが出力されるまでの時間を、漏れ孔を有するバケツに今回流入した液体（単位）が漏れ孔から流出するまでの時間と対応させている手法であるので、一般にリーキーバケットと呼ばれており、同一コネクション内の連続するセルの最小送出間隔を満足するように送出予定時刻τを決定することで、セル流のピークレートを規制するものである。
【００１１】
このリーキーバケット手法に使用されるパラメータ及び変数としては、リーキーバケット容量Ｃ、リーキーバケット内蓄積量カウンタ値Ｓ、リークレートＬ、１セル分に対応したカウンタ増加幅Ｆ、セル所要遅延時間Ｄ、及び、前セル到着時刻ＬＡＴである。これらのパラメータは通信中の各コネクション毎に送出予定時刻算出部２０２に格納されており、セル到着時に、そのセルに係るコネクションのパラメータが読み出されて使用、更新、再格納される。また、上記パラメータにより、ピークセルレートはＬ／Ｆに制限されることになる。なお、各ステップでの処理の意味合いは、後述する実施形態での説明を参照されたい。
【００１２】
当該シェイパー装置２０１が起動されると、セル到着の有無が監視され（ステップ３０１）、到着が確認されると以降の処理が行なわれる。まず、現在時刻ＣＴと前セル到着時刻ＬＡＴとの時刻差Δｔが算出された後（ステップ３０３）、前セル到着時刻ＬＡＴを現在時刻ＣＴに更新する（ステップ３０４）。続いて、蓄積量カウンタ値Ｓと、Δｔ時間分のカウンタ減算量Δｔ・Ｌとが比較される（ステップ３０５）。
【００１３】
Ｓ≦Δｔ・Ｌの場合には、所要遅延時間Ｄ及び蓄積量カウンタ値Ｓは共に０にセットされる（ステップ３０６及び３０７）。一方、Ｓ＞Δｔ・Ｌの場合は、カウンタ値Ｓは、Δｔ時間分のカウンタ減算量Δｔ・Ｌだけ減少され（ステップ３０８）、続いて、蓄積量カウンタ値Ｓは、バケット容量Ｃとカウンタ増加幅Ｆとの差分Ｃ−Ｆと比較される（ステップ３０９）。
【００１４】
Ｓ＞Ｃ−Ｆの場合（Ｓ＋Ｆ＞Ｃの場合）には、、到着セルは廃棄処理され、送出予定時刻算出部２０２からセルスケジューラ部２０３へ与えられる送出予定時刻τを無効情報にする（ステップ３１０）。これに対して、Ｓ≦Ｃ−Ｆの場合には、所要遅延時間Ｄは商Ｓ／Ｌの整数値として算出され（バケツ内の最も上の流体部分が漏れ孔から出るまでに要するの時間として算出され）、カウンタ値Ｓは増加幅Ｆだけインクリメントされる（ステップ３１１、３１２）。最後に、廃棄処分以外のセルについて、送出予定時刻τを、現在時刻ＣＴ及び所要遅延時間Ｄの和（ＣＴ＋Ｄ）に対する時計周期Ｔｍａｘでのモジュロ値として算出し、セルスケジューラ部２０３へ引き渡す（ステップ３１３）。
【００１５】
図４は、このようにして算出された今回の到着セルについての送出予定時刻τが与えられる、従来のセルスケジューラ部２０３（図４においては４０１を付与している）の構成を示すブロック図である。
【００１６】
セルスケジューラ部４０１は、到着セルを格納するセルメモリ（ＣＭ）４０２と、セルメモリ４０２のアドレス情報を司るポインタ群４０７〜４０９とで構成される。セルメモリ４０２は、１セル単位のエレメント４０６の一群で構成されている。
【００１７】
図５はエレメントの１つを拡大したものであり、１セル分の情報を格納するセル格納フィールド（ＣＢＦ）５０２と、同一送出予定時刻に係る他のエレメントを指し示すアドレスポインタ（ＡＰｔｒ）５０１からなる。このＡＰｔｒポインタを用いることで、エレメントは他のエレメントと数珠つなぎに連結できる。
【００１８】
セルメモリ４０２はまた、未使用エレメントを管理するフリーリスト（ＦＬ）４０３と、待ち合わせ中のセルが送出予定時刻毎に連結されて格納されているカレンダーキュー（ＣＱ）４０４と、出力待ち状態にあるセルを管理するアウトプットリスト（ＯＬ）４０５とに論理的に分割されている。
【００１９】
フリーリスト４０３は、セルメモリ４０２内の全ての未使用エレメントを連結しており、その先頭エレメント及び最終エレメントのアドレスは、フリーリスト用ポインタ４０７のフリーリストヘッダポインタ（以下、ＦＬＨポインタと呼ぶ）とフリーリストテイルポインタ（以下、ＦＬＴポインタと呼ぶ）によりそれぞれ格納されている。
【００２０】
カレンダーキュー４０４は、時計周期Ｔｍａｘ分の送出予定時刻毎に到着セルを連結させて格納しており、それぞれの連結セル群はフリーリスト４０３と同様に、カレンダーキュー用ポインタ群４０８のカレンダーキューヘッダ（以下、ＣＱＨポインタと呼ぶ）とカレンダーキューテイル（以下、ＣＱＴポインタと呼ぶ）により、先頭エレメントと最終エレメントが示されている。送出予定時刻に１つもセルが連結されていなければ、そのＣＱＨポインタ及びＣＱＴポインタは何も示さず無効情報となっている。
【００２１】
アウトプットリスト４０５には、現在時刻ＣＴが送出予定時刻と一致したセル群が移動してきて格納されており、アウトプットリスト用ポインタ４０９のアウトプットリストヘッダ（以下、ＯＬＨポインタと呼ぶ）とアウトプットリストテイル（以下、ＯＬＴポインタと呼ぶ）とにより先頭エレメント及び最終エレメントが指し示されている。アウトプットリスト４０５に蓄積されたセルは、先頭セルから順次１セル時間に１セルずつ出力回線４１２に送出されていく。セルが送出された後の空きエレメントは再びフリーリスト４０３の最後尾に連結されて、以降の到着セルの格納に使用されていく。
【００２２】
ここで、セルメモリ４０２は、論理的にフリーリスト４０３、カレンダーキュー４０４及びアウトプットリスト４０５に分割されてはいるが、物理的には１つの共有型のメモリで実現されており、フリーリスト４０３からカレンダーキュー４０４へ、さらにアウトプットリスト４０５へのセルの移動は全てポインタ処理によって行なわれ、各エレメント内のセル情報自体が移動するものではない。
【００２３】
【発明が解決しようとする課題】
上述したように、従来は、到着セル毎にユーザ申告値を満足するような送出予定時刻を前セル到着時刻に基づいて算出し、その送出予定時刻単位に到着セルをセルスケジューラ部２０３（４０１）内に一旦格納し、時計２０４が送出予定時刻になった時点で、その時刻列に格納されているセル群を送出待ちキュー（アウトプットリスト）に移動し、先頭セルから順次送出することで、セル出力帯域規制を実現していた。
【００２４】
しかしながら、このような従来の構成では、ＡＴＭ通信においてはユーザ申告値、すなわち最小セル間隔の異なる複数のコネクションを規制対象とする必要があるため、送出予定時刻が同一となる可能性がある。このような場合、セルスケジューラ部内の送出予定時刻単位のカレンダーキューに複数のセルが連結され、結果として、ＣＤＶを生じてユーザ申告値を満足しないことも生じる。
【００２５】
図６を用いて、この問題について具体的に説明する。図６は従来のシェイパー装置における、セル到着例６０１、送出予定時刻算出部内リーキーバケット蓄積量カウンタ値Ｓの遷移６０２、カレンダーキュー内のセル待ち合わせ状況６０３、シェイパー装置からのセル送出過程６０４、及び送出セル間隔６０５の一例を示すタイムチャートである。図中、Ａｉ（ｉ＝１〜８）、Ｂｊ（ｊ＝１〜６）、Ｃｋ（ｋ＝１〜７）はセルを表わしており、３種類のコネクションＡ〜Ｃが１つの回線上に多重されてシェイパー装置で各々帯域規制される様子を示している。ここで、コネクションＡのユーザ申告値はＣ＝１５、Ｆ＝７、Ｌ＝２と仮定され、同様にコネクションＢはＣ＝１５、Ｆ＝５、Ｌ＝１、コネクションＣはＣ＝１５、Ｆ＝４、Ｌ＝１とする。また、時計の周期Ｔｍａｘは９を仮定している。
【００２６】
タイムチャート６０１に示すように、各コネクションのセルはシェイパー装置に到着する前にＣＤＶを受けており、最小セル間隔の規定が満足されていない。タイムチャート６０２に示すリーキーバケット蓄積量カウンタ値Ｓに従って、各到着セルは送出予定時刻が算出され、タイムチャート６０３のようにカレンダーキュー内に送出予定時刻毎に蓄積されていく。異なるコネクションに属するセルＢ４、Ａ５及びＣ５は、前セル到着時刻より算出した送出予定時刻が一致しているために、カレンダーキュー内で同時刻列に連結されてキューイングされる。同様に、セルＡ４とＣ４、セルＢ６とＡ８についても送出予定時刻が重なっている。この結果、シェイパー装置からの実際の出力過程はタイムチャート６０４が示すように、セルＣ４、Ａ５、Ｃ５及びＡ８が予定送出時刻より遅れて送出されることになる。
【００２７】
しかし、同一コネクションの次の到着セルに対する送出予定時刻の算出には、このような予定より遅れた実際のセル送出時刻は考慮されない。タイムチャート６０５は、コネクションＡ〜Ｃの実際のセル送出間隔を示している。上述した複数コネクション間でのセル送出予定時刻の重なりのために（予定より遅れたセル送出のために）、各コネクションの最小セル間隔の規定（ユーザ申告値）は達成できていない。例えば、コネクションＡ（最小セル間隔３．５セル）のセルＡ５とＡ６の間、コネクションＣ（最小セル間隔４セル）のセルＣ５とＣ６の間等である。
【００２８】
従って、ユーザ申告値をより一段と満足させることができるセル出力帯域規制装置が求められている。
【００２９】
【課題を解決するための手段】
かかる課題を解決するため、第１の本発明においては、セルの出力帯域を、セル送出間隔の規定を用いて規制するセル出力帯域規制装置において、以下の手段を具備することを特徴とする。
【００３０】
すなわち、(1)セル到着毎に当該セルの送出予定時刻を、セル出力帯域を規定するパラメータに基づいて算出する送出予定時刻手段と、(2)算出された送出予定時刻単位に全コネクションのセルをキューイングし、セル送出予定時刻に達した時点で、当該時刻にキューイングされているセルを１セルずつ送出していくセル送出手段と、(3)送出予定時刻単位のセルのキューイング過程において、キューイングされているセル数の計数を送出予定時刻毎に行ない、送出予定時刻算出手段へ計数した送出予定時刻単位のセル数を与える送出予定時刻セル数計数手段と、(4)送出予定時刻毎のセル数を用いて、到着セルの送出予定時刻の算出に用いるリーキーバケット蓄積量カウンタ値を、送信予定時刻から遅れて送出されるセル数を反映するように補正する変数補正手段とを具備したことを特徴とする。
【００３１】
この第１の本発明においては、異なるコネクションのセルの送出予定時刻が重なって、送出予定時刻通りにセル送出が実行されないコネクションがあっても、実際のセル時刻と送出予定時刻との差をそれ以降の送出予定時刻の算出に反映させるように、送出予定時刻単位のセル数を用いて、到着セルの送出予定時刻算出に用いる変数を補正することとしたので、セル送出間隔の規定を満たすと共に、ＣＤＶを押さえることができるようになる。
【００３２】
また、上記課題を解決するため、第２の本発明においては、セルの出力帯域を、セル送出間隔の規定を用いて規制するセル出力帯域規制装置において、以下の手段を具備することを特徴とする。
【００３３】
すなわち、(1)セル到着毎に当該セルの送出予定時刻を、セル出力帯域を規定するパラメータに基づいて算出する送出予定時刻手段と、(2)算出された送出予定時刻単位に全コネクションのセルをキューイングし、セル送出予定時刻に達した時点で、当該時刻にキューイングされているセルを１セルずつ送出していくセル送出手段と、(3)規制対象の全コネクションについて、キューイング中のセルをコネクション単位に計数すると共に、そのコネクションの最新のセル送出時刻を記録、保持するコネクション情報管理手段と、(4)セル送出時に、送出セルが属するコネクション番号を検出し、そのコネクションについてのキューイング中のセル計数値と最新セル送出時刻の更新処理を行なうコネクション情報更新手段と、(5)コネクション毎のキューイング中の計数値と最新セル送出時刻とに基づく所定ピークレートを満たす直近の送出予定時刻と、到着セルの送出予定時刻とを比較し、到着セルの送出予定時刻が直近の送出予定時刻以上である場合、到着セルの送出予定時刻を直近の送出予定時刻に補正し、次回到着セルの送出予定時刻の算出に用いるリーキーバケット蓄積量カウンタ値を、到着セルの送出予定時刻からの遅延時間を反映させるように補正する補正手段とを具備したことを特徴とする。
【００３４】
この第２の本発明においては、異なるコネクションのセルの送出予定時刻が重なって、送出予定時刻通りにセル送出が実行されないコネクションがあっても、実際のセル時刻と送出予定時刻との差を、それ以降の送出予定時刻の算出等に反映させるように、コネクション毎のキューイング中のセル計数値と最新セル送出時刻情報とを用いて、到着セルの送出予定時刻とその算出に用いる変数の補正の必要性を判定して、補正が必要なときに補正することとしたので、セル送出間隔の規定をほぼ満たすと共に、ＣＤＶを押さえることができるようになる。
【００３５】
【発明の実施の形態】
（Ａ）第１の実施形態
以下、本発明によるセル出力帯域規制装置の第１の実施形態を図面を参照しながら詳述する。
【００３６】
（Ａ−１）第１の実施形態の構成
図１は、第１の実施形態のセル出力帯域規制装置の構成を示すブロック図である。
【００３７】
このセル出力帯域規制装置も、大きくは、送出予定時刻算出部１０１、セルスケジューラ部１０２、及び、時計１０３によって構成されている。
【００３８】
この実施形態の送出予定時刻算出部１０１も、通信中で出力帯域規制の対象である全コネクションについて、各種帯域規制パラメータや変数を保有しており、到着セル毎に送出予定時刻τを算出してセルスケジューラ部１０２へ提供するものである。
【００３９】
しかし、これらのパラメータ及び変数、並びに、時計１０３からの現在時刻情報ＣＴだけでなく、セルスケジューラ部１０２から与えられる送出予定時刻毎の待ち合わせセル数Ｎ（τ）も、到着セル毎の送出予定時刻τの算出に用いる点が従来とは異なっている。
【００４０】
この実施形態のセルスケジューラ部１０２は、到着セルを一旦格納し、送出予定時刻算出部１０１からの送出予定時刻τを元にセル送出のスケジューリングを行なう点は従来と同様であるが、送出予定時刻τ毎に送出の待ち合わせ中のセルを計数し、その計数値Ｎ（τ）を送出予定時刻算出部１０１へフィードバックする点が従来とは異なっている。
【００４１】
すなわち、この実施形態のセルスケジューラ部１０２は、到着セルを格納するセルメモリ（ＣＭ）１０４、及び、このセルメモリ１０４のアドレス情報を司るポインタ群１０９〜１１１を備えるだけでなく、待ち合わせ中のセルを計数するセル計数カウンタ１１２を備えている。
【００４２】
なお、セルメモリ１０４が、１セル単位の既述した図５に示すエレメント１０８の一群で構成されていると共に、未使用エレメントを管理するフリーリスト（ＦＬ）１０５と、待ち合わせ中のセルが送出予定時刻毎に連結されて格納されているカレンダーキュー（ＣＱ）１０６と、出力待ち状態にあるセルを管理するアウトプットリスト（ＯＬ）１０７に論理的に分割されている点は、従来と同様である。また、フリーリスト１０５の先頭エレメント及び最終エレメントのアドレスを規定するＦＬＨポインタ及びＦＬＴポインタ１０９、カレンダーキュー１０６の各送出時刻の先頭エレメント及び最終エレメントのアドレスを規定するＣＱＨポインタ及びＣＱＴポインタ１１０、並びに、アウトプットリスト１０７の先頭エレメント及び最終エレメントのアドレスを規定するＯＬＨポインタ及びＯＬＴポインタ１１１が、セルスケジューラ部１０２に格納されている点も、従来と同様である。
【００４３】
この第１の実施形態で新たに設けられたセル計数カウンタ１１２は、カレンダーキュー１０６内で待ち合わせ中のセル数Ｎ（τ）を送出予定時刻単位に計数するものであり、待ち合わせ中のセル数Ｎ（τ）を、送出予定時刻算出部１０１に与えるものである。
【００４４】
時計１０３は、例えば従来と同様に、１セル時間毎にインクリメントされるアップカウンタであり、そのカウンタ出力が現在時刻情報ＣＴとして、送出予定時刻算出部１０１及びセルスケジューラ部１０２へ提供される。時計１０３の最大値はＴｍａｘ−１であり、最大値Ｔｍａｘ−１までカウントアップされた後は０に戻り、再び１ずつインクリメントされていくものである。従って、時計１０３の周期はＴｍａｘである。
【００４５】
図７は、概念的には図１に示す構成を有するセルスケジューラ部１０２（７０１）について、より具体的なレベルで構成を示したブロック図である。
【００４６】
図７において、セルスケジューラ部７０１は、セルメモリ（ＣＭ）７０２、送出時刻パラメータメモリ（ＭＥＭ）７０３、２個のレジスタ（ＲＥＧ）７０４及び７０５、２個の選択回路（ＳＥＬ）７０６及び７０７、加算回路（ＡＤＤ）７３２、並びに、制御回路７０８から構成されている。また、このセルスケジューラ部７０１は、外部とのインタフェース（信号線等）部として、セル入力部７０９、セル出力部７１０、送出予定時刻算出部１０１からの送出予定時刻（τ）入力部７１１、送出予定時刻算出部１０１への待ち合わせセル数情報（Ｎ（τ））出力部７３３、及び、時計１０３からの現在時刻情報（ＣＴ）入力部７１２を有している。
【００４７】
セルメモリ７０２は、図５にも示したように、連結先アドレスを示すアドレスポインタ（ＡＰｔｒ）及び到着セルを格納するセル格納フィールド（ＣＢＦ）を１エレメントとするメモリであり、図１におけるフリーリスト１０５、カレンダーキュー１０６、及び、アウトプットリスト１０７を実現するものである。このセルメモリ７０２の読み出し、書き込みは、制御線７３０を介して制御回路７０８により制御される。
【００４８】
メモリ７０３は、カレンダーキュー内に送出予定時刻単位に連結して蓄積されているセルエレメントについて、先頭エレメントアドレスを示すＣＱＨポインタ、最終エレメントを示すＣＱＴポインタ、及び、送出予定時刻毎の蓄積セル数Ｎ（τ）を、時計周期分（０〜Ｔｍａｘ−１）格納しているものである。メモリ７０３の読み出し、書き込みも、制御線７３１を介して制御回路７０８により制御される。
【００４９】
レジスタ７０４は、フリーリストに連結されているセルメモリ７０２内の未使用エレメントの先頭エレメントアドレスを示すＦＬＨポインタと、最終エレメントアドレスを示すＦＬＴポインタを保持している。レジスタ７０５は、アウトプットリストに連結されているセルメモリ７０２内の出力待ちセルエレメントの先頭エレメントアドレスを示すＯＬＨポインタと、最終エレメントアドレスを示すＯＬＴポインタを保持しているものである。これらレジスタ７０４及び７０５への書き込みは、制御線７３５を介して制御回路７０８により制御される。また、少なくともレジスタ７０４は、新旧（最新及びその直前）のポインタを保持し得るようになされている。
【００５０】
選択回路７０６及び７０７はそれぞれ、対応するセルメモリ７０２、メモリ７０３の読み出し、書き込みを行なう際のアドレス情報７１７、７１９の選択を行なうものであり、両者の選択動作は制御線７１８、７２０を介して制御回路７０８により制御される。セルメモリ７０２へのアドレス情報としては、レジスタ７０４、７０５やメモリ０３から出力されたＦＬＨポインタあるいはＦＬＴポインタ（７１３）、ＣＱＨポインタあるいはＣＱＴポインタ（７１４）、又は、ＯＬＨポインタあるいはＯＬＴポインタ（７１５）のいずれかが選択される。メモリ７０３へのアドレス情報としては、送出予定時刻算出部１０１からの送出予定時刻τ（７１１）、あるいは時計１０３からの現在時刻情報ＣＴ（７１２）のいずれかが選択される。
【００５１】
加算回路７３２は、メモリ７０３内に保持されている送出予定時刻毎の待ち合わせ中セル数Ｎ（τ）の更新処理を行なうものである。加算回路７３２は、到着セルの送出予定時刻τを送出予定時刻算出部１０１から受信すると、当該時刻のセル数Ｎ（τ）を送出予定時刻算出部１０１へフィードバック（信号線７３３）した後、１インクリメントする。加算回路７３２の動作もまた、制御線７３６を介して制御回路７０８によって制御される。
【００５２】
制御回路７０８は、セルスケジューラ部７０１全体の制御を司っており、セルメモリ７０２及びメモリ７０３の書き込み、読み出し、レジスタ７０４及び７０５のラッチタイミング、選択回路７０６及び７０７の選択処理動作、加算回路７３２の加算処理動作等を制御する。
【００５３】
（Ａ−２）第１の実施形態の動作
以下、この第１実施形態のシェイパー装置の動作を、送出予定時刻算出部１０１及びセルスケジューラ部１０２の動作の順に詳細に説明する。
【００５４】
ここで、時計１０３は、帯域規制対象のセル到着の有無にかかわらず、常に１セル時間に１ずつ時刻をインクリメントし、送出予定時刻算出部１０１及びセルスケジューラ部１０２に現在時刻情報ＣＴを供給しているとする。また、送出予定時刻算出部１０１内には、監視対象の全コネクションについてのパラメータや変数が一括して格納され、監視対象セルの到着毎に、該当するコネクションのパラメータ及び変数を内部の記憶部から取出して送出予定時刻の算出処理を行ない、かつ処理終了後には更新された変数を再び格納場所へ格納するものとする。
【００５５】
（Ａ−２−１）送出予定時刻算出部１０１の動作
図８は、この第１の実施形態の送出予定時刻算出部１０１の処理を示すフローチャートであり、上述した従来装置に係る図３との同一処理ステップには同一符号を付して示している。この実施形態の送出予定時刻算出部１０１の処理も、一般にリーキーバケットと呼ばれる手法を踏襲したものであり、同一コネクション内の連続するセルの最小送出間隔を満足するように送出予定時刻τを決定することで、ピークセルレートを規制するものである。
【００５６】
なお、この第１の実施形態の送出予定時刻算出部１０１は、パラメータ及び変数としては、従来と同様な、リーキーバケット容量Ｃ、リーキーバケット内蓄積量カウンタ値Ｓ、リークレートＬ、カウンタ増加幅Ｆ、セル所要遅延時間Ｄ、前セル到着時刻ＬＡＴ及び時計周期Ｔｍａｘを用いるだけでなく、送出予定時刻τにおける待ち合わせ中セル数Ｎ（τ）をも利用して、監視対象コネクションをピークセルレートＬ／Ｆに制限するような処理を行なう。
【００５７】
この実施形態の送出予定時刻算出部１０１も、当該シェイパー装置が起動されるとセル到着の有無を監視し、セルの到着が確認されると、現在時刻ＣＴと前セル到着時刻ＬＡＴとの時刻差Δｔ、すなわちそのコネクションの今回の到着間隔を算出すると共に、前セル到着時刻ＬＡＴを次回の到着のために現在時刻ＣＴに更新し、その後、リーキーバケットの更新前のカウンタ値Ｓと、Δｔ時間分のカウンタ減算量Δｔ・Ｌの比較を行なう（ステップ３０２〜３０５）。
【００５８】
Ｓ≦Δｔ・Ｌの場合は、前回の到着時にリーキーバケットに残存していた流体（セル）が今回のセル到着前に既になくなっていることに相当し、そこで、今回の到着セルを直ちに送出可能とすべく所要遅延時間Ｄを０にセットすると共に、蓄積量カウンタ値Ｓも０にセットする（ステップ３０６、３０７）。
【００５９】
一方、Ｓ＞Δｔ・Ｌの場合は、前回の到着時にリーキーバケットに残存していた流体（セル）ＳがリークレートＬずつ到着間隔Δｔの間漏れても今回のセル到着時にリーキーバケットに流体（セル）が残存していることに相当し、そこで、今回のセル到着時点でのリーキーバケットの残存量に、すなわち、Ｓ−Δｔ・Ｌに蓄積量カウンタ値Ｓを更新する（ステップ３０８）。
【００６０】
その後、更新されたカウンタ値Ｓと、バケット容量Ｃとカウンタ増加幅Ｆとの差分Ｃ−Ｆとを比較する（ステップ３０９）。この比較は、今回のセル到着時点でのリーキーバケットの残存量（Ｓ）に、今回のセル到着による流体量（Ｆ）を加えた場合に、その量（Ｓ＋Ｆ）がバケット容量Ｃを越えて、リーキーバケットの上縁からオーバーフローするか否かの判定を行なっていることに相当する。
【００６１】
Ｓ＞Ｃ−Ｆの場合（Ｓ＋Ｆ＞Ｃの場合）は、今回のセル到着を有効としたときにリーキーバケットの上縁からオーバーフローするので、到着セルを廃棄させるために、無効な送出予定時刻τをセルスケジューラ部１０２に出力して今回の到着セルに対する処理を終了する（ステップ３１０）。
【００６２】
これに対して、Ｓ≦Ｃ−Ｆの場合（Ｓ＋Ｆ≦Ｃの場合）には、所要遅延時間Ｄを商Ｓ／Ｌの整数値ｉｎｔ［Ｓ／Ｌ］として算出する（ステップ３１１）。このステップ処理は、今回の到着セルが送出されるのは、今回のセル到着時点で残存していた全てのセル対応の蓄積量（Ｓ）が漏れ出た後であり、リークレートがＬであるので、残存していた全てのセル（Ｓ）が送出されるのに要する時間、すなわち今回の到着セルが送出されるまでの時間はＳ／Ｌであり、この例の場合、時刻は１を単位として変化するので、その整数部分が今回の到着セルが送出されるまでの遅延時間になるという考え方に従っている。
【００６３】
今回のセル到着時点でのリーキーバケットの残存量（Ｓ）がない場合であろうと、到着セルの廃棄がなされない程度に存在する場合であろうと、その残存量に対応した蓄積量カウンタ値Ｓ及び所要遅延時間Ｄが求められた場合には、今回の到着セルの送出予定時刻τを算出し、セルスケジューラ部１０２に出力する（ステップ８１２、図３のステップ３１３と同様）。現在時刻ＣＴと所要遅延時間Ｄとから、単純には、これらの和ＣＴ＋Ｄとして送出予定時刻τが求められるが、時計１０３として周期がＴｍａｘのものを適用しているので、和ＣＴ＋Ｄが時計周期Ｔｍａｘより大きくなることを考慮し、上述した和ＣＴ＋Ｄを時計周期Ｔｍａｘで除算した際のモジュロ値として送出予定時刻τを求めている。
【００６４】
最後に、セルスケジューラ部１０２から受信した、ステップ８１２で求めた送出予定時刻τの列に蓄積されている待ち合わせ中のセル数Ｎ（τ）（今回の到着セル分を計数していない値）をも考慮して、リーキーバケットの蓄積量カウンタ値Ｓを更新して、今回の到着セルに対する一連の処理を終了する（ステップ８１３）。
【００６５】
処理終了時点の蓄積量カウンタ値Ｓは、他のコネクションを考慮しなければ、今回のセル到着時の蓄積量カウンタ値Ｓ（ステップ３０７又は３０８による算出値）に、今回のセル到着による増加分Ｆを加算して求めれば良い（従来に係るステップ３１２参照）。しかし、他のコネクションを考慮しない従来は、上述したような課題を生じている。そのため、この第１の実施形態は、他のコネクションの状況をも反映させるべく、送出予定時刻τの列に蓄積されている待ち合わせ中のセル数Ｎ（τ）も処理終了時点の蓄積量カウンタ値Ｓの算出に利用し、処理終了時点の蓄積量カウンタ値Ｓを、今回のセル到着時の蓄積量カウンタ値Ｓに、Ｆ＋Ｌ・Ｎ（τ）を加えた値とすることとした。
【００６６】
この算出式Ｓ：＝Ｓ＋Ｆ＋Ｌ・Ｎ（τ）における右辺のＳ＋Ｆは、従来同様に、到着セルのコネクションだけを考慮し、今回のセル到着時の蓄積量カウンタ値Ｓ（ステップ３０７又は３０８による算出値）に、今回のセル到着による増加分Ｆを加算した成分である。右辺のＬ・Ｎ（τ）は、以下の考え方に従って、加算することとしたものである。
【００６７】
ステップ８１２で求めた送出予定時刻τを予定時刻とする既に到着している他のコネクションのセルが存在する場合には、今回の到着セルは、同一の送出予定時刻τの他の全て（個数はＮ（τ））のセルが出力された後でなければ送出されず、送出は予定時刻τより遅れる。実際上、このように遅れた時刻で送出される今回の到着セルから、ユーザ申告値で定まる最小のセル間隔を守って次回の到着セルの送出予定時刻を決定する場合、今回の到着セルが送出予定時刻から遅れる分を考慮しなければならず、次回の到着セルに対して決定される送出予定時刻に、今回の到着セルが送出予定時刻から遅れる時間を反映させるために、今回のセル到着時の蓄積量カウンタ値Ｓ（ステップ３０７又は３０８による算出値）と、今回のセル到着による増加分Ｆとの和Ｓ＋ＦにさらにＬ・Ｎ（τ）を加算することとした。
【００６８】
これにより次回のステップ３１１の処理では、Ｌ・Ｎ（τ）の成分はＮ（τ）となり、次回のセル到着時の送出予定時刻が、同一コネクションだけを考慮した場合よりＮ（τ）だけ遅くなり、今回の到着セルに対する実際の送出時刻が予定送出時刻τより遅れても、その分、次回の到着セルの送出予定時刻も遅れて、相前後するセルの出力間隔が他のコネクションの影響を受けずに、ＣＤＶを吸収でき、ユーザ申告値を満足するようになる。
【００６９】
（Ａ−２−２）セルスケジューラ部１０２の動作
次に、第１の実施形態のセルスケジューラ部１０２の動作を、到着セル処理とセル送出処理との順に、図７の構成ブロック図を参照しながら説明する。
【００７０】
［セルスケジューラ部１０２の到着セル処理］
帯域規制対象のセルが到着すると、その到着セルはまず、レジスタ７０４のＦＬＨポインタで示されるセルメモリ７０２内の先頭位置の未使用エレメントのセル格納フィールドＣＢＦに一旦格納される。この際、選択回路７０６は、レジスタ７０４のＦＬＨポインタの格納部から読み出されたＦＬＨポインタ（７１３）を選択出力し、セルメモリ７０２のアドレス入力としている。
【００７１】
ここで、送出予定時刻算出部１０１から受信する当該セルの送出予定時刻τが、無効情報でない限り以降の処理が行なわれる。なお、無効情報である場合は当該セルは廃棄扱いとなり、以降の処理は何も行なわれない。また、フリーリスト内に未使用エレメントがない場合にも、到着セルは同様に廃棄扱いとなる。
【００７２】
送出予定時刻τが有効である場合、これまで、レジスタ７０４のＦＬＨポインタで示されていた未使用エレメントが到着セルへと割り当てられて使用エレメントに変化するので、ＦＬＨポインタの更新が必要となる。すなわち、これまでＦＬＨポインタで示されていた当該到着セルを格納したエレメントのＡＰｔｒポインタで示される連結先の未使用エレメントが、次の先頭未使用エレメントとなるので、制御回路７０８は、前記ＡＰｔｒポインタ値を、信号線７２２を介して、レジスタ７０４のＦＬＨポインタの格納エリアに与えて新ＦＬＨポインタとして格納させる。
【００７３】
このとき、残りの未使用エレメントが１つになる場合には、最終エレメントを規定するＦＬＴポインタもまた先頭エレメントを規定するＦＬＨポインタと同じ未使用エレメントを指し示すことになるため、信号線７２２はＦＬＴポインタ７０４へも接続されている。さらに、当該到着セルが最後の未使用エレメントに格納された場合には、残りの未使用エレメントはなくなり、ＦＬＨ及びＦＬＴポインタは、制御回路７０８により無効とされる。
【００７４】
次に、到着セルを格納した当該エレメントは、送出予定時刻算出部１０１からの送出予定時刻τに基づいた以下のようなポインタ処理によりフリーリストからカレンダーキュー内のその時刻τに対応する待ち合わせセル列に移動される。
【００７５】
この到着セルに対する処理においては、選択回路７０７は送出予定時刻τを選択するように制御されており、この選択回路７０７で選択された送出予定時刻τをアドレスとするメモリ７０３内のＣＱＴポインタを読み出して、選択回路７０６を介してセルメモリ７０２にアドレスとして与えて、到着セルが格納されたセルメモリ７０２のエレメントのＡＰｔｒポインタに旧ＦＬＨポインタを書き込むと共に（信号線７２３）、メモリ７０３のその送出予定時刻τのＣＱＴポインタにも旧ＦＬＨポインタを書き込む（信号線７２７）。なお、送出予定時刻τに相当する連結エレメント列（セル）が何も存在していなかった場合には、旧ＦＬＨポインタがそのままＣＱＨ及びＣＱＴポインタとしてメモリ７０３に書き込まれる（信号線７２７）。
【００７６】
また、このような到着セルに係るエレメントのカレンダーキュー内への移動処理のときに、当該送出予定時刻τの待ち合わせセル数Ｎ（τ）がメモリ７０３から読み出されて送出予定時刻算出部１０１へと受け渡される（信号線７３３）と共に、インクリメント処理が加算回路７３２によって行なわれ、メモリ７０３内へ再格納される（信号線７３４）。
【００７７】
以上のようにして、セルが到着すると、そのときのＦＬＨポインタが示すフリーリストの先頭エレメントにその到着セルが格納され、その先頭エレメントの連結ポインタが示すエレメントがフリーリストの先頭エレメントに変更されると共に、有効な到着予定時刻τが与えられると、カレンダーキュー内のその時刻τのエレメント列の最後尾に今回の到着セルに係る未使用エレメントから使用エレメントに変化したエレメントが連結され、また、その送出予定時刻τにかかる今回の到着セルを含めないセル数Ｎ（τ）を送出予定時刻算出部１０１に出力された後、そのセル数Ｎ（τ）が１インクリメントされる。
【００７８】
［セルスケジューラ部１０２のセル送出処理］
次に、セルスケジューラ部１０２におけるセル送出処理、すなわち、送出予定時刻というスケジュールに従って、バッファリングしているセルを送出する処理を説明する。
【００７９】
時計１０３からの現在時刻情報ＣＴを信号線７１２より受信したセルスケジューラ部７０１は、まず、この現在時刻ＣＴに相当するカレンダーキュー内の連結エレメント（セル）群をアウトプットリストに移動させる以下のような処理を行なう。
【００８０】
最初に、選択回路７０７で選択されるアドレス情報７１９が、時計１０３からの現在時刻ＣＴに設定される。
【００８１】
この現在時刻ＣＴをアドレスとして、その時刻ＣＴの連結エレメント列の先頭及び最終エレメントを規定するＣＱＨポインタ及びＣＱＴポインタをそれぞれメモリ７０３から読み出し、アウトプットリストが空の場合には、それぞれをレジスタ７０５にＯＬＨポインタ及びＯＬＴポインタとして格納する（信号線７２８及び７２９）。この際、アウトプットリストに移動するエレメント（セル）が１つだけの場合には、読み出されたＣＱＨポインタ値をＯＬＨポインタ及びＯＬＴポインタとして格納される。
【００８２】
また、アウトプットリスト内に既にエレメント（セル）がある場合には、メモリ７０３から読出したＣＱＨポインタとＣＱＴポインタの示すエレメント群をその最後尾に連結させる。すなわち、レジスタ７０５のアウトプットリスト内の最終エレメントを規定するＯＬＴポインタに、メモリ７０３から読み出されたＣＱＴポインタ値を格納し（信号線７２９）、旧ＯＬＴポインタをアドレスとするセルメモリ７０２内のエレメントのＡＰｔｒポインタ（連結先ポインタ）の格納エリアに、メモリ７０３から読み出されたＣＱＨポインタを格納する。ここで、移動するエレメントが１つだけの場合には、更新されるＡＰｔｒポインタ及びＯＬＴポインタは共に、メモリ７０３から読み出されたＣＱＨポインタ値になる。
【００８３】
次に、制御回路７０８は、アウトプットリストに移動された現在時刻ＣＴを送出予定時刻としているエレメント（セル）列に相当するセル計数値Ｎ（τ）を０クリアする。
【００８４】
以上のようにして、現在時刻ＣＴを送出予定時刻としているカレンダーキュー内のエレメント（セル）列がアウトプットリストの後半に連結される。
【００８５】
アウトプットリストに移動されたセル群は、以下のようにして、１セル時間に１セルずつ順次出力線７１０から送出されていく。
【００８６】
制御回路７０８は、現在時刻ＣＴが更新されて上述したアウトプットリストへの移動処理が終了すると、レジスタ７０５のＯＬＨポインタを選択回路７０６を介してセルメモリ７０２にアドレスとして与え、そのアドレスを有するエレメント、すなわち、アウトプットリスト内の先頭エレメントのセル格納フィールドＣＢＦにあるセル情報を、出力線７１０から送出させる。
【００８７】
これにより、このエレメントのＡＰｔｒポインタの指し示すエレメントが、次の時刻でのアウトプットリスト内の先頭エレメントになるので、このＡＰｔｒポインタ値をセルメモリ７０２から読み出してレジスタ７０５のＯＬＨポインタのエリアに格納させる（信号線７２４）。なお、今回のセル送出により、アウトプットリスト内の残存セル（エレメント）が１セルとなった場合には、セルメモリ７０２から読出したＡＰｔｒポインタ値を、レジスタ７０５のＯＬＨポインタのエリアだけでなく、ＯＬＴポインタのエリアにも格納させる。また、セル送出によりアウトプットリスト内の残存セルがなくなった場合には、レジスタ７０５のＯＬＨポインタ及びＯＬＴポインタのエリアを無効とする。
【００８８】
セルが送出されたアウトプットリスト内の旧先頭エレメントは、未使用状態となるので、以下のようにして再びフリーリストに移動される。
【００８９】
レジスタ７０４からＦＬＴポインタを読み出して、選択回路７０６を介してセルメモリ７０２にアドレスとして与え、そのアドレスのエレメント、すなわち、フリーリスト内の最後尾エレメントのＡＰｔｒポインタに、レジスタ７０５に格納されている旧ＯＬＨポインタ値を格納させると共に、この旧ＯＬＨポインタ値をレジスタ７０４のＦＬＴポインタに書き込む。なお、フリーリスト内に未使用エレメントが１つもなかった場合には、レジスタ７０４のＦＬＨポインタにも合わせて旧ＯＬＨポインタ値が格納される。
【００９０】
以上のようにして、現在時刻が変更される毎に、アウトプットリスト内の先頭エレメントに格納されているセルが出力されると共に、そのエレメントがフレーリストの最後尾に移動される。
【００９１】
次に、上述した構成を有して上述した動作を行なう第１の実施形態のシェイパー装置の具体的な動作例を図９を用いて説明する。
【００９２】
なお、図９は、従来の課題の説明で用いた図６と同様なセルの到着状況及びユーザ申告条件での動作例を示すタイムチャートである。すなわち、ユーザ申告値がＣ＝１５、Ｆ＝７、Ｌ＝２であるコネクションＡ、ユーザ申告値がＣ＝１５、Ｆ＝５、Ｌ＝１であるコネクションＢ、ユーザ申告値がＣ＝１５、Ｆ＝４、Ｌ＝１であるコネクションＣのセルが、タイムチャート９０１のように当該シェイパー装置の到着以前においてＣＤＶを受けて最小セル間隔の規定が必ずしも満足されていない状態で到着した際の、送出予定時刻算出部１０１内のリーキーバケット蓄積量カウンタ値Ｓの遷移９０２、カレンダーキュー内のセル待ち合わせ状況９０３、当該シェイパー装置からのセル送出過程９０４、及び、送出セル間隔９０５を示している。
【００９３】
この第１の実施形態においても、タイムチャート９０２に示すリーキーバケット蓄積量カウンタ値Ｓが算出され、このカウンタ値Ｓに従って、各到着セルは送出予定時刻τが算出され、タイムチャート９０３のようにカレンダーキュー内に送出予定時刻毎に蓄積されていく。この第１の実施形態でも、異なるコネクションに属するセルについては、同一の送出予定時刻が算出されることがある。セルＡ４とＣ４、Ｂ４とＡ５、Ｂ５とＣ６、及び、Ｂ６とＣ６はそれぞれ、前セル到着時刻より算出した送出予定時刻が一致しているために、カレンダーキュー内で同時刻列に連結キューイングされたものである。
【００９４】
しかし、この第１の実施形態においては、到着セル分を含めた蓄積量カウンタ値Ｓは、その送出予定時刻でのセル数Ｎ（τ）も反映されているので、蓄積量カウンタ値Ｓは従来より高い値をとることも生じ、送出予定時刻τが従来より遅くなるセルが多くなる。タイムチャート６０３及び９０３の比較から明らかなように、セルＣ５、Ａ６、Ｃ６、Ａ７、Ｃ７及びＡ８の送出予定時刻は従来より遅く決定されている。すなわち、同一の送出予定時刻に後で決定されたセルＣ４、Ａ５、Ｃ６及びＣ７は、送出予定時刻より遅れて実際には出力され、他のコネクションのセルの存在によってこのようにセル送出が遅れた分については待ち合わせセル数Ｎ（τ）を用いて蓄積量カウンタ値Ｓを補正処理して次回の送出予定時刻の決定に反映させているため、その後の同一コネクションの到着セルに送出予定時刻は前回に決定された同一コネクションについての送出予定時刻よりはむしろだ実際の送出時刻を基準として決定しているということができ、図６と比べても明らかなようにＣＤＶを押さえることができる。
【００９５】
具体的には、セルＡ５とＡ６との間のセル間隔は従来では２セル時間であったものがこの第１の実施形態では３セル時間になり、また、セルＣ５とＣ６との間のセル間隔は従来ではが２セル時間であったものがこの第１の実施形態では４セル時間になっている。すなわち、最小セル間隔の規定を、従来とは異なって、満足させるようにできている。
【００９６】
（Ａ−３）第１の実施形態の効果
上述した第１の実施形態のシェイパー装置によれば、以下のような効果を得ることができる。
【００９７】
（１）異なるコネクション間で同一時刻にセル送出予定が重なって予定時刻より出力が遅れるセルが発生した場合においても、その出力が待ち合わせされるコネクションについては、待ち合わせ分だけセル送出予定時刻算出処理の変数を補正するようにしたので、そのコネクションの後続するセルとの間でＣＤＶ発生を防ぐことができ、所要の最小セル送出間隔を満足させることができる。
【００９８】
この最小セル間隔の保証は、ＡＴＭネットワークの帯域管理においては最も重要なファクターであり、上記効果の意義は大きい。
【００９９】
（２）上記セル送出予定時刻算出処理の変数の補正処理を、送出予定時刻単位の待ち合わせセル数の計数という簡易な機能追加で対処しているので、回路規模の増大を招くことがない。
【０１００】
因に、従来装置であっても、実際上、送出予定時刻毎の待ち合わせセルの計数機能を具備することが一般的であり、この第１の実施形態はその機能とパラメータを拡張利用し、送出予定時刻算出部へとフィードバックしているだけであるので、送出予定時刻算出部での積和演算機能部を１つ付加のみであり、回路規模の増加はほとんどない。
【０１０１】
このように従来装置に比較すると、送出予定時刻算出部での積和演算機能の追加が必要となるが、この演算部は既に送出予定時刻算出部に含まれており、同じ演算部を切り替えて利用することで、回路規模の増加をさらに抑えることができる。
【０１０２】
（３）この第１の実施形態が使用しているスペーシングポリサー（ＳｐａｃｉｎｇＰｏｌｉｃｅｒ）方式の最大の特徴は、膨大な数のコネクションを同時に帯域規制可能な点にあるが、各種処理をセル到着時とセル送出時にのみ実行しているので、この第１の実施形態の実現上でも、その特徴は何ら損なわれず、装置が許容するコネクション数が制限されることはない。
【０１０３】
（Ｂ）第２の実施形態
次に、本発明によるセル出力帯域規制装置の第２の実施形態を図面を参照しながら詳述する。
【０１０４】
（Ｂ−１）第２の実施形態の構成
図１０は、第２の実施形態のセル出力帯域規制装置の構成を示すブロック図であり、第１の実施形態に係る図１との同一、対応部分には同一符号を付して示している。
【０１０５】
このセル出力帯域規制装置も、大きくは、送出予定時刻算出部１０１、セルスケジューラ部１０２、及び、時計１０３によって構成されている。時計１０３は、第１の実施形態のものと同様である。
【０１０６】
この第２の実施形態の送出予定時刻算出部１０１は、セルスケジューラ部１０２から送出されたセルのコネクション番号ｍをも利用して、到着セル毎に送出予定時刻τを算出してセルスケジューラ部１０２へ提供するものであり、コネクション番号ｍをも利用する点が第１の実施形態とは異なっている。
【０１０７】
この第２の実施形態のセルスケジューラ部１０２は、各送出予定時刻毎の待ち合わせセル数Ｎ（τ）の格納部を備えていない点（備えていても良いが第２の実施形態の特徴とは無関係である）、及び、送出予定時刻算出部１０１に当該セルスケジューラ部１０２から送出されたセルのコネクション番号ｍをフィードバックする点が、第１の実施形態とは異なっている。
【０１０８】
図１１は、概念的には図１０に示す構成を有する第２の実施形態のセルスケジューラ部１０２（７０１）について、より具体的なレベルで内部構成を示したブロック図であり、上述した図７との同一、対応部分には同一符号を付して示している。
【０１０９】
このようなレベルでセルスケジューラ部７０１の構成を見た場合、以下の点が、第１の実施形態の構成と異なっており、これ以外の構成は第１の実施形態と同様である。
【０１１０】
（１）送出予定時刻τのセル数Ｎ（τ）を１インクリメントするための加算回路（図７の符号７３２参照）が設けられていない点、（２）送出時刻毎のパラメータメモリ（ＭＥＭ）７０３にセル数Ｎ（τ）のエリアが設けられておらず、セル数Ｎ（τ）の送出予定時刻算出部１０１へのフィードバック線がない点、（３）制御回路７０８が出力セルのコネクション番号ｍを取り込んで送出予定時刻算出部１０１へフィードバックするようになされている点が、第１の実施形態の構成と異なっている。
【０１１１】
（Ｂ−２）第２の実施形態の動作
以下、この第２の実施形態のシェイパー装置の動作を、送出予定時刻算出部１０１及びセルスケジューラ部１０２の動作の順に詳細に説明する。ここで、時計１０３は、帯域規制対象のセル到着の有無にかかわらず、常に１セル時間に１ずつ時刻をインクリメントし、送出予定時刻算出部１０１及びセルスケジューラ部１０２に現在時刻情報ＣＴを供給しているとする。また、送出予定時刻算出部１０１内には、監視対象の全コネクションについてのパラメータや変数が一括して格納され、監視対象セルの到着毎に、また、セルを外部に出力する毎に、該当するコネクションのパラメータ及び変数を内部の記憶部から取出して送出予定時刻の算出処理等を行ない、かつ処理終了後には更新された変数を再び格納場所へ格納するものとする。
【０１１２】
（Ｂ−２−１）送出予定時刻算出部１０１の動作
この第２の実施形態の送出予定時刻算出部１０１の処理も、一般にリーキーバケットと呼ばれる手法を踏襲したものであり、同一コネクション内の連続するセルの最小送出間隔を満足するように送出予定時刻τを決定することで、ピークセルレートを規制するものである。しかし、この第２の実施形態の場合、送出予定時刻算出部１０１の動作は、当該シェイパー装置にセルが到着した際に実行される動作と、当該シェイパー装置からセルを送出した際に実行される動作とに分けられる。
【０１１３】
なお、この第２の実施形態の送出予定時刻算出部１０１は、従来と同様なリーキーバケット容量Ｃ、リーキーバケット内蓄積量カウンタ値Ｓ、リークレートＬ、カウンタ増加幅Ｆ、セル所要遅延時間Ｄ、前セル到着時刻ＬＡＴ及び時計周期Ｔｍａｘだけでなく、到着セルのコネクション（コネクション番号をｋとする）のセルスケジューラ部１０２内の蓄積セル数（未送出の到着セル数）Ｎ（ｋ）、及び、そのコネクションの最新（直前）のセル送出時刻ＲＤＴ（ｋ）をも利用して、監視対象コネクションをピークセルレートＬ／Ｆに制限する。
【０１１４】
まず、図１２のフローチャートを参照しながら、送出予定時刻算出部１０１のセル到着時の動作を説明する。なお、図１２において、従来装置に係る図３及び第１の実施形態に係る図８との同一、対応ステップには同一符号を付して示している。また、図１２においては、従来と同様な変数、パラメータについては、到着セルのコネクション番号ｋを規定する（ｋ）を省略しているが、正しくは、Ｓ（ｋ）、Ｌ（ｋ）、Ｆ（ｋ）、Ｄ（ｋ）及びＬＡＴ（ｋ）と記載すべきものである。
【０１１５】
当該シェイパー装置が起動されて処理を開始し、ステップ３１３の処理を実行するまでは、従来装置と同様な処理を行なうので、その説明は省略する。なお、これらのステップ処理において、利用する蓄積量カウンタ値Ｓは後述するステップ１２１８で算出されたものとなっていることもあり、この点では、従来装置と同様でないということもできる。
【０１１６】
到着セルが有効であって、ステップ３１２において、到着時の蓄積量カウンタ値Ｓを今回の到着セルに相当する量（Ｆ）だけ増加すると共に、ステップ３１３において、現在時刻ＣＴと、到着時の蓄積量カウンタ値Ｓに基づいて得た今回の到着セルを出力するまでの遅延時間Ｄとから送出予定時刻τを算出すると、更新した蓄積量カウンタ値Ｓ及び算出した送出予定時刻τが、妥当なものか否かを以下のようにして見直す。すなわち、セルスケジューラ部１０２におけるそのコネクションｋの待機しているセル数Ｎ（ｋ）や、このコネクションｋの前回の実際の送出時刻ＲＤＴ（ｋ）からみて妥当なものであるか否かを見直す。
【０１１７】
この一連の見直し処理では、まず、到着セルのコネクションｋの未送出セル数Ｎ（ｋ）を今回の到着セルを含むように１インクリメントし（ステップ１２１４）、その後、ピークセルレートＦ／Ｌを満たす当該到着セルの直近の送出予定時刻τ０を算出する（ステップ１２１５）。ピークセルレートＦ／Ｌを満たす直近の送出予定時刻τ０は、単純には、前回の実際の送出時刻ＲＤＴ（ｋ）に、ピークセルレートＦ／Ｌで未送出のＮ（ｋ）個のセルを送出するのに要する時間ｉｎｔ［Ｎ（ｋ）・Ｆ／Ｌ］を加算することで求まるが（整数化ｉｎｔは時刻の更新が１ずつなされるために行なわれている）、時計１０３がＴｍａｘを一巡周期としているため、その加算値を、この時計周期Ｔｍａｘて割ったモジュロ値として算出する。
【０１１８】
このようにして、ピークセルレートＦ／Ｌを満たす当該到着セルの直近の送出予定時刻τ０を得ると、到着時の蓄積量カウンタ値Ｓを基準として求めた今回の到着セルの送出予定時刻τを、ピークセルレートを考慮した直近の送出予定時刻τ０と比較する（ステップ１２１６）。
【０１１９】
τ≧τ０の場合には、送出予定時刻τがピークセルレートＦ／Ｌを満たすとみなして良いので、ステップ３１２で得られた到着セル分を含めた蓄積量カウンタ値Ｓ、及び、ステップ３１３で求めた送出予定時刻τを変更することなく、セル到着時の一連の処理を終了する。
【０１２０】
一方、τ＜τ０の場合には、送出予定時刻τがピークセルレートＦ／Ｌを満たさないので、ステップ３１２及び３１３で得られた蓄積量カウンタ値Ｓ及び送出予定時刻τを、以下の値に変更させてセル到着時の一連の処理を終了する（ステップ１２１７、１２１８）。すなわち、今回の到着セルの送出予定時刻τを、そのコネクションのピークセルレートＦ／Ｌを満たすと考えられる最も早い時刻τ０まで遅延させてセットし直す（ステップ１２１８）。このように到着時の蓄積量カウンタ値Ｓから求めた送出予定時刻τを時間τ０−τ分だけ遅らせるように更新するので、このコネクションの次回の到着セルの送出予定時刻の算出にも、かかる遅延時間を反映させるように、ステップ３１２で求めた蓄積量カウンタ値Ｓも、その遅延時間の相当分Ｌ・（τ０−τ）だけ増加させる（ステップ１２１７）。
【０１２１】
以上のような一旦求めた送出予定時刻に対するピークセルレートを考慮した確認、補正処理によって、当該到着セルだけでなくこの到着セル以降の到着セルについて、より最小セル送出間隔の規定値を満足するシェイパー動作を実現することができるようになる。
【０１２２】
次に、図１３のフローチャートを参照しながら、当該シェイパー装置からのセル送出時における送出予定時刻算出部１０１の動作を説明する。
【０１２３】
送出予定時刻算出部１０１は、セルスケジューラ部１０２からセル送出がなされたか否かを確認しており（ステップ１３０２）、セル送出が成されると、当該セルのコネクション番号ｍをセルスケジューラ部１０２から受信する（ステップ１３０３）。そして、送出予定時刻算出部１０１は、当該コネクションｍについての内部管理している蓄積セル数Ｎ（ｍ）を１デクリメントすると共に、当該コネクションｍの最新セル送出時刻ＲＤＴ（ｍ）を、時計１０３からの現在時刻ＣＴにセットして、一連のセル送出時の処理を終了する（ステップ１３０４、１３０５）する。
【０１２４】
このようなセル送出時の処理によって適宜更新される蓄積セル数Ｎ（ｍ）及び最新セル送出時刻ＲＤＴ（ｍ）を、上述したセル到着時に活用することにより、到着時の蓄積量カウンタ値Ｓに基づいて求めた到着セル分だけ更新された蓄積量カウンタ値Ｓ及び送出予定時刻τに対し、ピークセルレートを反映させた見直すを実行することができるようになる。
【０１２５】
（Ｂ−２−２）セルスケジューラ部１０２の動作
次に、第２の実施形態のセルスケジューラ部１０２の動作を、到着セル処理とセル送出処理との順に、図１１の構成ブロック図を参照しながら説明する。
【０１２６】
［セルスケジューラ部１０２の到着セル処理］
この第２の実施形態におけるセル到着時のセルスケジューラ部１０２の動作は、第１の実施形態とほぼ同様である。
【０１２７】
すなわち、到着セルを最終の未使用エレメントのセル格納フィールドに格納すると共に、最終の未使用エレメントを規定するＦＬＨポインタを更新する動作は、第１の実施形態と同様である。また、到着セルを格納した当該エレメントを、送出予定時刻算出部１０１からの送出予定時刻τに基づいたポインタ処理により、フリーリストからカレンダーキュー内のその時刻τに対応する待ち合わせセル列に移動する動作も、第１の実施形態と同様である。従って、これらの動作の詳述は省略する。
【０１２８】
しかし、この第２の実施形態の場合、到着セルを格納したエレメントをフリーリストからカレンダーキュー内の送出予定時刻τに対応する待ち合わせセル列に移動しても、その時刻τ対応の蓄積セル数Ｎ（τ）を更新する動作を実行しない点が、第１の実施形態と異なっている。
【０１２９】
［セルスケジューラ部１０２のセル送出処理］
次に、セルスケジューラ部１０２におけるセル送出処理、すなわち、送出予定時刻というスケジュールに従って、バッファリングしているセルを送出する処理を説明する。
【０１３０】
時計１０３からの現在時刻情報ＣＴに基づいて、この現在時刻ＣＴに相当するカレンダーキュー内の連結エレメント（セル）群をアウトプットリストに移動させる動作は、第１の実施形態とほぼ同様であるので、その詳細説明は省略する。なお、この第２の実施形態の場合、このような移動時において、アウトプットリストに移動された現在時刻ＣＴを送出予定時刻としているエレメント（セル）列に相当するセル計数値Ｎ（τ）を０クリアする動作は実行されず、この点は、第１の実施形態と異なっている。
【０１３１】
この移動処理後に実行される、アウトプットリストに移動されたセル群を、１セル時間に１セルずつ順次出力線７１０から送出すると共に、その送出によって未使用エレメントに変化したエレメントをフリーリストに移動する動作も、第１の実施形態とほぼ同様であるので、その詳細説明は省略する。
【０１３２】
なお、この第２の実施形態の場合は、アウトプットリストから出力線７１０に出力されたセルのコネクション番号ｍを制御回路７０８が取り込み、送出予定時刻算出部１０１に出力するようにしている点は、第１の実施形態と異なっている。このコネクション番号ｍが、送出予定時刻算出部１０１による上述した図１３に示す動作に用いられる。
【０１３３】
次に、上述した構成を有して上述した動作を行なう第２の実施形態のシェイパー装置の具体的な動作例を図１４を用いて説明する。
【０１３４】
なお、図１４は、従来の課題の説明で用いた図６と同様なセルの到着状況及びユーザ申告条件での動作例を示すタイムチャートである。すなわち、ユーザ申告値がＣ＝１５、Ｆ＝７、Ｌ＝２であるコネクションＡ、ユーザ申告値がＣ＝１５、Ｆ＝５、Ｌ＝１であるコネクションＢ、ユーザ申告値がＣ＝１５、Ｆ＝４、Ｌ＝１であるコネクションＣのセルが、タイムチャート１４０１のように当該シェイパー装置の到着以前においてＣＤＶを受けて最小セル間隔の規定が必ずしも満足されていない状態で到着した際の、送出予定時刻算出部１０１内のリーキーバケット蓄積量カウンタ値Ｓの遷移１４０２、カレンダーキュー内のセル待ち合わせ状況１４０３、当該シェイパー装置からのセル送出過程１４０４、及び、送出セル間隔１４０５を示している。
【０１３５】
この第２の実施形態においても、タイムチャート１４０２に示すリーキーバケット蓄積量カウンタ値Ｓが算出され、このカウンタ値Ｓに従って、各到着セルは送出予定時刻τが算出され、タイムチャート１４０３のようにカレンダーキュー内に送出予定時刻毎に蓄積されていく。この第１の実施形態でも、異なるコネクションに属するセルについては、同一の送出予定時刻が算出されることがある。セルＡ４とＣ４、Ｂ４とＡ５とＣ５、Ｂ５とＣ６、及び、Ｃ７とＡ８はそれぞれ、前セル到着時刻より算出した送出予定時刻が一致しているために、カレンダーキュー内で同時刻列に連結キューイングされたものである。
【０１３６】
しかし、この第２の実施形態においては、到着セル分を含めた蓄積量カウンタ値Ｓは、そのコネクションでのセル数Ｎ（ｋ）や最新送出時刻ＲＤＴ（ｋ）も反映されているので、蓄積量カウンタ値Ｓは従来より高い値をとることも生じ、送出予定時刻τが従来より遅くなるセルが多くなる。また、コネクションでのセル数Ｎ（ｋ）や最新送出時刻ＲＤＴ（ｋ）を考慮して送出予定時刻τを見直しているので、送出予定時刻τが従来より遅くなるセルが多くなる。タイムチャート６０３及び１４０３の比較から明らかなように、セルＣ６、Ａ７、Ｃ７及びＡ８の送出予定時刻は従来より遅く決定されている。
【０１３７】
すなわち、異なるコネクションに属するセルＡ４とＣ４、Ｂ４とＡ５とＣ５、Ｂ５とＣ６、及び、Ｃ７とＡ８は、それぞれ前セル到着時刻より算出した送出予定時刻が一致しているために、カレンダーキュー内で同時刻列に連結キューイングされ、前記セルＣ４、Ａ５、Ｃ５、Ｃ６及びＡ８は、送出予定時刻より遅れて実際には出力され、このセル送出の遅れた分については、上述したように、コネクション単位のカレンダーキュー内待ち合わせセル数ｍを用いて補正処理をしているために、その後の同一コネクションの到着セルに送出予定時刻は前回に決定された同一コネクションについての送出予定時刻よりはむしろだ実際の送出時刻を基準として決定しているということができ、図６と比べても明らかなようにＣＤＶを押さえることができる。
【０１３８】
具体的には、セルＡ５とＡ６との間のセル間隔は従来装置と同じ２セルのままであるが、その後に続くセルＡ６とＡ７との間が４セルから５セルへと広がり、最小セル間隔を満足していないセルＡ５、Ａ６間の影響を、後続セルを遅らせることで緩和している。またセルＣ５とＣ６との間は２セルから４セルへと、従来装置と比べて広がっており、最小セル間隔の規定を満足している。
【０１３９】
（Ｂ−３）第２の実施形態の効果
上述した第２の実施形態のシェイパー装置によれば、以下のような効果を得ることができる。
【０１４０】
（１）異なるコネクション間で同一時刻にセル送出予定が重なって、待ち合わせを受けるセルが発生した場合においても、待ち合わせを受けるコネクションについて、待ち合わせ分だけセル送出予定時刻算出処理の変数を補正することにより、後続するセルとの間でのＣＤＶ発生を抑制し、所要最小セル送出間隔を満足できないことの影響を緩和することができる。
【０１４１】
上述したように、この最小セル間隔の保証は、ＡＴＭネットワークの帯域管理においては最も重要なファクターであり、上記効果の意義は大きい。
【０１４２】
（２）上記セル送出予定時刻算出処理の変数の補正処理を、コネクション単位での待ち合わせセル数の計数という簡易な機能追加で対処しているので、回路規模の増大を招くことがない。
【０１４３】
また、送出予定時刻算出部では第２実施形態の実現のために、積和演算や除算演算、モジュロ演算等機能の追加が必要となるが、これらの演算部は既に送出予定時刻算出部に含まれており、同じ演算部を切り替えて利用することで、回路規模の増加はさらに抑えられる。
【０１４４】
（３）この第２の実施形態が使用しているスペーシングポリサー（ＳｐａｃｉｎｇＰｏｌｉｃｅｒ）方式の最大の特徴は、膨大な数のコネクションを同時に帯域規制可能な点にあるが、各種処理をセル到着時とセル送出時にのみ実行しているので、この第２の実施形態の実現上でも、その特徴は何ら損なわれず、装置が許容するコネクション数が制限されることはない。
【０１４５】
（Ｃ）他の実施形態
以上、本発明を、２つの実施形態につき詳細に説明したが、本発明は上述した実施形態に限定されるものではない。
【０１４６】
（１）両実施形態におけるセル送出予定時刻算出部１０１は、上述したフローチャートに示す処理を実行できるものであれば、ハードウェア的に構成されていても良く、また、ＤＳＰ等を利用してソフトウェア的に構成されているものであっても良い。
【０１４７】
（２）第１実施形態において、送出予定時刻毎の蓄積セル数Ｎ（τ）の計数処理及び保持を、セルスケジューラ部側で行なう例を示したが、送出予定時刻算出部側で保持、管理しても良い。
【０１４８】
（３）第２実施形態におけるコネクション毎の蓄積セル数Ｎ（ｋ）や最新送出時刻ＲＤＴ（ｋ）の更新処理や保持を、セルスケジューラ部側で実行し、送出予定時刻算出部へとその都度受け渡しても良い。
【０１４９】
（４）到着セルをバッファリングするセルメモリは、物理的に１つのメモリでなくても良く、フリーリスト、カレンダーキュー、アウトプットリストのそれぞれを個別のメモリで実現しても良い。
【０１５０】
（５）両実施形態では、到着セル毎の送出予定時刻算出にリーキーバケット型の手法を用いているが、本発明はリーキーバケット型に限らず、その他の手法、例えばある一定の時間幅内を通過するセル数によって規定するウィンドウ型と呼ばれる手法等を適用しても、その実現性には全く問題は生じない。要は、送出予定時刻を決定するための変数やパラメータを、実際のセル送出時刻の情報を反映させる形で補正できる形式の手法であれば良い。
【０１５１】
【発明の効果】
以上のように、第１の本発明によれば、送出予定時刻単位のセルのキューイング過程において、キューイングされているセル数の計数を送出予定時刻毎に行ない、送出予定時刻算出手段へ計数した送出予定時刻単位のセル数を与える送出予定時刻セル数計数手段と、送出予定時刻毎のセル数を用いて、到着セルの送出予定時刻の算出に用いるリーキーバケット蓄積量カウンタ値を、送信予定時刻から遅れて送出されるセル数を反映するように補正する変数補正手段とを具備したので、異なるコネクションのセルの送出予定時刻が同一になった前後においても、セル送出間隔の規定を満たすことができ、かつＣＤＶを押さえることができる。
【０１５２】
また、第２の本発明によれば、規制対象の全コネクションについて、キューイング中のセルをコネクション単位に計数すると共に、そのコネクションの最新のセル送出時刻を記録、保持するコネクション情報管理手段と、セル送出時に、送出セルが属するコネクション番号を検出し、そのコネクションについてのキューイング中のセル計数値と最新セル送出時刻の更新処理を行なうコネクション情報更新手段と、コネクション毎のキューイング中の計数値と最新セル送出時刻とに基づく所定ピークレートを満たす直近の送出予定時刻と、到着セルの送出予定時刻とを比較し、到着セルの送出予定時刻が直近の送出予定時刻以上である場合、到着セルの送出予定時刻を直近の送出予定時刻に補正し、次回到着セルの送出予定時刻の算出に用いるリーキーバケット蓄積量カウンタ値を、到着セルの送出予定時刻からの遅延時間を反映させるように補正する補正手段とを具備したので、異なるコネクションのセルの送出予定時刻が同一になった前後においても、セル送出間隔の規定を満たすことができ、かつＣＤＶを押さえることができる。
【図面の簡単な説明】
【図１】第１の実施形態の概略構成を示すブロック図である。
【図２】シェイパー装置の一般的構成を示すブロック図である。
【図３】従来の送出予定時刻算出部の処理フローチャートである。
【図４】従来のセルスケジューラ部の概念的構成を示す機能ブロック図である。
【図５】エレメントの構成を示す説明図である。
【図６】従来の課題説明用のタイムチャートである。
【図７】第１の実施形態のセルスケジューラ部の構成例を示すブロック図である。
【図８】第１の実施形態の送出予定時刻算出部の処理フローチャートである。
【図９】第１の実施形態の効果説明用のタイムチャートである。
【図１０】第２の実施形態の概略構成を示すブロック図である。
【図１１】第２の実施形態のセルスケジューラ部の構成例を示すブロック図である。
【図１２】第１の実施形態の送出予定時刻算出部のセル到着時の処理フローチャートである。
【図１３】第１の実施形態の送出予定時刻算出部のセル送出時の処理フローチャートである。
【図１４】第２の実施形態の効果説明用のタイムチャートである。
【符号の説明】
１０１…送出予定時刻算出部、１０２…セルスケジューラ部、１０３…時計、Ｎ（τ）…送出予定時刻単位の送出待ち合わせセル数、ｋ…到着セルのコネクション番号、Ｎ（ｋ）…コネクションｋの送出待ち合わせセル数、ＲＤＴ（ｋ）…コネクションｋの最新送出時刻。[0001]
TECHNICAL FIELD OF THE INVENTION
BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a cell output band regulating device for controlling a cell transmission speed from each switching / transmission device to a declared value in an asynchronous transfer mode type communication network.
[0002]
[Prior art]
In recent years, in the field of information communication, with the diversification of communication needs, advancement of information exchange / transmission technology, development of device technology, etc., a high-speed broadband service integrated digital network capable of exchanging and transmitting user information at high speed and wide band. (Hereinafter, B-ISDN) is being rapidly commercialized.
[0003]
In the B-ISDN, an asynchronous transfer mode (hereinafter, referred to as ATM) is employed as an information transfer method. In this ATM communication, information is transferred and exchanged in fixed-length packets called cells. In this case, the transfer destination of the cell is identified based on the destination address information assigned to each cell. Therefore, unlike the conventional time-division circuit switching, each terminal can transmit a cell to an arbitrary position of a slot on a vacant time axis, and cell multiplexing to an arbitrary position on a transmission line in a network is also possible. It becomes possible.
[0004]
For this reason, in the ATM communication, each terminal declares a cell communication band (for example, a peak cell rate or an average cell rate) to be used in advance before starting communication, and the network manages the band based on the declaration information. One of the intra-network band management functions is a cell output band regulation function (hereinafter, referred to as a shaper). The shaper function is designed to reduce cell delay fluctuation (hereinafter abbreviated as CDV) caused by output queuing when a plurality of cells heading for the same route arrive at the same time during multiplexing and switching processing in a network. This is a function of absorbing and transmitting a cell to an output line according to a user declared value.
[0005]
Heretofore, several methods have been proposed for implementing the shaper function. As one of them, there is a spacing policer method. This method occurs in a network by calculating a scheduled transmission time that satisfies a declared value for each arriving cell, and sequentially reading and transmitting cells queued for each scheduled transmission time one cell at a time. The aim is to reduce CDV and realize cell transmission that satisfies the user declared value.
[0006]
FIG. 2 is a block diagram showing a basic configuration of a shaper device that realizes such a shaper function.
[0007]
In FIG. 2, a shaper device 201 includes a scheduled transmission time calculation unit 202 that calculates a scheduled transmission time τ for each arrival cell, a cell scheduler unit 203 that temporarily stores arrival cells and schedules cell transmission according to the scheduled transmission time τ. , A scheduled transmission time calculation unit 202, and a clock 204 that supplies current time information CT to the cell scheduler unit 203. Here, the scheduled transmission time calculation unit 202 holds user reported value information and various parameters to be described later for all connections in communication. The clock 204 increments the current time CT by one every one cell time.
[0008]
When the cell 205 arrives at the shaper device 201, the scheduled transmission time calculating unit 202 specifies from the information on the connection to which the cell belongs how long the cell is delayed in the cell scheduler unit 203 to satisfy the declared value. The required delay time is obtained, and the scheduled transmission time τ is calculated based on the required delay time, and provided to the cell scheduler 203. The cell scheduler unit 203 stores the cell at the end of the cell buffer unit queued for each scheduled transmission time on the basis of the received scheduled transmission time τ. The cell 206 corresponding to the time CT is transmitted.
[0009]
FIG. 3 is a flowchart showing processing by the conventional scheduled transmission time calculation unit 202. Note that “: =” in FIG. 3 means that the value or state value of the parameter on the left side is set to the value or state value on the right side, and the same applies to other flowcharts described later.
[0010]
The processing method shown in FIG. 3 is a method in which the time until the arrival cell is output corresponds to the time until the liquid (unit) that has flowed into the bucket having the leak hole this time flows out of the leak hole. , Which is generally called a leaky bucket, regulates the peak rate of the cell flow by determining the scheduled transmission time τ so as to satisfy the minimum transmission interval of consecutive cells in the same connection.
[0011]
The parameters and variables used in the leaky bucket method include a leaky bucket capacity C, an accumulated amount counter value S in a leaky bucket, a leak rate L, a counter increment F corresponding to one cell, a cell required delay time D, and , The previous cell arrival time LAT. These parameters are stored in the scheduled transmission time calculation unit 202 for each connection during communication, and upon arrival of a cell, the parameters of the connection relating to the cell are read, used, updated, and stored again. Further, the peak cell rate is limited to L / F by the above parameters. For the meaning of the processing in each step, refer to the description of the embodiment described later.
[0012]
When the shaper device 201 is started, the presence or absence of cell arrival is monitored (step 301), and when the arrival is confirmed, the subsequent processing is performed. First, after the time difference Δt between the current time CT and the previous cell arrival time LAT is calculated (step 303), the previous cell arrival time LAT is updated to the current time CT (step 304). Subsequently, the accumulated amount counter value S is compared with the counter subtraction amount Δt · L for the time Δt (step 305).
[0013]
If S ≦ Δt · L, the required delay time D and the accumulated amount counter value S are both set to 0 (steps 306 and 307). On the other hand, if S> Δt · L, the counter value S is decreased by the counter subtraction amount Δt · L for the time Δt (step 308), and subsequently, the accumulated amount counter value S is increased by the bucket capacity C and the counter increment. The difference C-F from the width F is compared (step 309).
[0014]
In the case of S> CF (in the case of S + F> C), the arrival cell is discarded, and the scheduled transmission time τ given from the scheduled transmission time calculation unit 202 to the cell scheduler unit 203 is set as invalid information (step 310). On the other hand, if S ≦ CF, the required delay time D is calculated as an integer value of the quotient S / L (as the time required for the uppermost fluid portion in the bucket to exit the leak hole). Calculated), and the counter value S is incremented by the increment F (steps 311 and 312). Finally, for the cells other than the cells to be discarded, the scheduled transmission time τ is calculated as a modulo value in the clock cycle Tmax with respect to the sum (CT + D) of the current time CT and the required delay time D, and transferred to the cell scheduler unit 203 (step 313). ).
[0015]
FIG. 4 is a block diagram showing the configuration of a conventional cell scheduler 203 (to which 401 is added in FIG. 4) to which the scheduled transmission time τ for the current arrival cell calculated in this way is given. is there.
[0016]
The cell scheduler unit 401 includes a cell memory (CM) 402 for storing an arrival cell, and a group of pointers 407 to 409 for controlling address information of the cell memory 402. The cell memory 402 includes a group of elements 406 in units of one cell.
[0017]
FIG. 5 is an enlarged view of one of the elements, and includes a cell storage field (CBF) 502 for storing information for one cell, and an address pointer (APtr) 501 pointing to another element related to the same scheduled transmission time. . By using the APtr pointer, an element can be linked to another element in a daisy chain.
[0018]
The cell memory 402 also has a free list (FL) 403 for managing unused elements, a calendar queue (CQ) 404 in which waiting cells are linked and stored at each scheduled transmission time, and an output waiting state. It is logically divided into an output list (OL) 405 for managing cells.
[0019]
The free list 403 links all the unused elements in the cell memory 402, and the addresses of the first element and the last element are referred to as a free list header pointer (hereinafter, referred to as an FLH pointer) of the free list pointer 407. Each is stored by a free list tail pointer (hereinafter, referred to as an FLT pointer).
[0020]
The calendar queue 404 stores arriving cells linked at each scheduled transmission time for the clock cycle Tmax, and each linked cell group has a calendar queue header (a calendar queue pointer 408) of the calendar queue pointer group 408 like the free list 403. Hereinafter, the first element and the last element are indicated by a CQH pointer and a calendar queue tail (hereinafter referred to as a CQT pointer). If no cell is connected at the scheduled transmission time, the CQH pointer and the CQT pointer indicate nothing and indicate invalid information.
[0021]
In the output list 405, a cell group whose current time CT coincides with the scheduled transmission time is moved and stored, and the output list header (hereinafter referred to as an OLH pointer) of the output list pointer 409 and the output The first element and the last element are indicated by a list tail (hereinafter, referred to as an OLT pointer). The cells stored in the output list 405 are sequentially transmitted to the output line 412 one cell at a time, one cell at a time, from the head cell. The empty element after the cell is transmitted is linked again to the end of the free list 403, and is used for storing the arriving cell thereafter.
[0022]
Here, the cell memory 402 is logically divided into a free list 403, a calendar queue 404, and an output list 405, but is physically implemented by one shared memory, and The movement of the cell from to the calendar queue 404 and further to the output list 405 is all performed by pointer processing, and the cell information itself in each element does not move.
[0023]
[Problems to be solved by the invention]
As described above, conventionally, the scheduled transmission time that satisfies the user declared value for each arrival cell is calculated based on the previous cell arrival time, and the cell scheduler unit 203 (401) calculates the arrival cell for each scheduled transmission time. When the clock 204 reaches the scheduled transmission time, the cell group stored in the time sequence is moved to a transmission waiting queue (output list), and is sequentially transmitted from the head cell. Cell output band regulation was realized.
[0024]
However, in such a conventional configuration, in the ATM communication, a user report value, that is, a plurality of connections having different minimum cell intervals need to be restricted, so that the scheduled transmission times may be the same. In such a case, a plurality of cells are connected to a calendar queue in the unit of a scheduled transmission time in the cell scheduler unit, and as a result, a CDV is generated and the user report value may not be satisfied.
[0025]
This problem will be specifically described with reference to FIG. FIG. 6 shows an example of cell arrival 601 in the conventional shaper device, transition 602 of the leaky bucket accumulated amount counter value S in the scheduled transmission time calculator, cell waiting state 603 in the calendar queue, cell transmission process 604 from the shaper device, and transmission. 6 is a time chart illustrating an example of a cell interval 605. In the figure, Ai (i = 1 to 8), Bj (j = 1 to 6), and Ck (k = 1 to 7) represent cells, and three types of connections A to C are multiplexed on one line. This shows how the band is regulated by the shaper device. Here, it is assumed that the user report values of connection A are C = 15, F = 7, L = 2, and similarly, connection B is C = 15, F = 5, L = 1, and connection C is C = 15, F = 4 and L = 1. The clock cycle Tmax is assumed to be 9.
[0026]
As shown in the time chart 601, the cell of each connection receives the CDV before arriving at the shaper device, and the definition of the minimum cell interval is not satisfied. According to the leaky bucket accumulation amount counter value S shown in the time chart 602, the scheduled transmission time of each arrival cell is calculated, and as shown in the time chart 603, is accumulated in the calendar queue for each scheduled transmission time. The cells B4, A5 and C5 belonging to different connections are linked and queued in the calendar queue at the same time sequence because the scheduled transmission times calculated from the previous cell arrival times match. Similarly, the scheduled transmission times of cells A4 and C4 and cells B6 and A8 also overlap. As a result, in the actual output process from the shaper device, as shown in the time chart 604, the cells C4, A5, C5 and A8 are transmitted later than the scheduled transmission time.
[0027]
However, the calculation of the scheduled transmission time for the next arriving cell of the same connection does not consider the actual cell transmission time that is behind such a schedule. The time chart 605 shows actual cell transmission intervals of the connections A to C. Due to the overlap of the scheduled cell transmission times among the plurality of connections (for cell transmission delayed from the schedule), the definition of the minimum cell interval of each connection (user declared value) has not been achieved. For example, between cells A5 and A6 of connection A (minimum cell interval of 3.5 cells) and between cells C5 and C6 of connection C (minimum cell interval of 4 cells).
[0028]
Therefore, there is a need for a cell output band regulating device that can further satisfy the user report value.
[0029]
[Means for Solving the Problems]
In order to solve such a problem, a first aspect of the present invention is characterized in that a cell output band regulating device for regulating a cell output band by using a rule of a cell transmission interval includes the following means.
[0030]
That is, (1) scheduled transmission time means for calculating the scheduled transmission time of the cell every time a cell arrives, based on a parameter defining the cell output band; and (2) cells of all connections in the calculated scheduled transmission time unit. Cell transmission means for transmitting the cells queued at that time one cell at a time when the scheduled cell transmission time is reached; and (3) a cell queuing process in units of transmission scheduled time. A scheduled transmission time cell number counting means for counting the number of queued cells at each scheduled transmission time and providing the counted scheduled transmission time unit cell count to the scheduled transmission time calculation means; Number of cells per time Using Used to calculate the scheduled transmission time of the arrival cell Leaky bucket accumulated amount counter value To To reflect the number of cells transmitted after the scheduled transmission time And a variable correcting means for correcting.
[0031]
In the first aspect of the present invention, even if the scheduled transmission times of cells of different connections overlap, and even if there is a connection in which cell transmission is not executed at the scheduled transmission time, the difference between the actual cell time and the scheduled transmission time is calculated. The variable used for calculating the scheduled transmission time of the arriving cell is corrected by using the number of cells in the scheduled transmission time unit so as to be reflected in the calculation of the scheduled transmission time thereafter. , And CDV.
[0032]
According to a second aspect of the present invention, there is provided a cell output band regulating apparatus for regulating a cell output band using a regulation of a cell transmission interval, comprising the following means. I do.
[0033]
That is, (1) scheduled transmission time means for calculating the scheduled transmission time of the cell every time a cell arrives, based on a parameter defining the cell output band; and (2) cells of all connections in the calculated scheduled transmission time unit. Cell transmission means for transmitting cells queued at that time one cell at a time when the scheduled cell transmission time is reached; and (3) queuing for all regulated connections. And the connection information management means for recording and holding the latest cell transmission time of the connection, and (4) detecting the connection number to which the transmission cell belongs when transmitting the cell, and Connection information updating means for updating the cell count value during queuing and the latest cell transmission time; and (5) a queue for each connection. Count in the ring and at the latest cell transmission Time Based on The latest scheduled transmission time satisfying the predetermined peak rate is compared with the scheduled transmission time of the arrival cell, and when the scheduled transmission time of the arrival cell is equal to or longer than the latest scheduled transmission time, Scheduled transmission time of arrival cell Is corrected to the latest scheduled transmission time, and the next arrival cell Used to calculate scheduled transmission time The leaky bucket accumulation amount counter value is now reflected to the delay time from the scheduled transmission time of the arriving cell. And a correction means for performing correction.
[0034]
According to the second aspect of the present invention, even if the scheduled transmission times of cells of different connections overlap and there is a connection in which cell transmission is not executed at the scheduled transmission time, the difference between the actual cell time and the scheduled transmission time is determined. Using the cell count value during queuing for each connection and the latest cell transmission time information, the expected transmission time of the arriving cell and the correction of the variables used for its calculation are reflected in the calculation of the subsequent transmission time. Is determined and the correction is performed when the correction is necessary. Therefore, the regulation of the cell transmission interval is almost satisfied, and the CDV can be suppressed.
[0035]
BEST MODE FOR CARRYING OUT THE INVENTION
(A) First embodiment
Hereinafter, a first embodiment of a cell output band regulation device according to the present invention will be described in detail with reference to the drawings.
[0036]
(A-1) Configuration of First Embodiment
FIG. 1 is a block diagram illustrating a configuration of the cell output band regulation device according to the first embodiment.
[0037]
This cell output band regulating device also includes a scheduled transmission time calculation unit 101, a cell scheduler unit 102, and a clock 103.
[0038]
The scheduled transmission time calculation unit 101 of this embodiment also holds various band regulation parameters and variables for all connections that are subject to output band regulation during communication, and calculates the scheduled transmission time τ for each arrival cell. This is provided to the cell scheduler unit 102.
[0039]
However, not only these parameters and variables, and the current time information CT from the clock 103, but also the number of waiting cells N (τ) for each scheduled transmission time given from the cell scheduler unit 102, the scheduled transmission time for each arrival cell The point used for calculating τ is different from the conventional one.
[0040]
Although the cell scheduler unit 102 of this embodiment temporarily stores the arriving cell and schedules the cell transmission based on the scheduled transmission time τ from the scheduled transmission time calculation unit 101, it is the same as the conventional case. This is different from the related art in that cells waiting for transmission are counted for each τ, and the counted value N (τ) is fed back to the scheduled transmission time calculation unit 101.
[0041]
That is, the cell scheduler unit 102 of this embodiment includes not only a cell memory (CM) 104 for storing an arrival cell and pointer groups 109 to 111 for controlling the address information of the cell memory 104, but also a cell waiting for a call. Is provided.
[0042]
The cell memory 104 is composed of a group of the above-described elements 108 shown in FIG. 5 in units of one cell, and a free list (FL) 105 for managing unused elements and a cell waiting for transmission are scheduled to be transmitted. It is the same as the conventional one in that it is logically divided into a calendar queue (CQ) 106 connected and stored for each time and an output list (OL) 107 for managing cells in an output waiting state. . Also, an FLH pointer and an FLT pointer 109 that specify the addresses of the first element and the last element of the free list 105, a CQH pointer and a CQT pointer 110 that specify the addresses of the first element and the last element of each transmission time of the calendar queue 106, and The OLH pointer and the OLT pointer 111 that specify the addresses of the first element and the last element of the output list 107 are stored in the cell scheduler unit 102 in the same manner as in the related art.
[0043]
The cell counter 112 newly provided in the first embodiment counts the number of waiting cells N (τ) in the calendar queue 106 for each scheduled transmission time, and the number of waiting cells N (Τ) is given to the scheduled transmission time calculation unit 101.
[0044]
The clock 103 is, for example, an up-counter that is incremented every cell time as in the conventional case, and the output of the counter is provided to the scheduled transmission time calculation unit 101 and the cell scheduler unit 102 as current time information CT. The maximum value of the clock 103 is Tmax-1, and after counting up to the maximum value Tmax-1, returns to 0 and is incremented by one again. Therefore, the cycle of the clock 103 is Tmax.
[0045]
FIG. 7 is a block diagram conceptually showing the configuration at a more specific level of cell scheduler section 102 (701) having the configuration shown in FIG.
[0046]
7, a cell scheduler unit 701 includes a cell memory (CM) 702, a transmission time parameter memory (MEM) 703, two registers (REG) 704 and 705, two selection circuits (SEL) 706 and 707, A circuit (ADD) 732 and a control circuit 708 are provided. The cell scheduler unit 701 includes a cell input unit 709, a cell output unit 710, a scheduled transmission time (τ) input unit 711 from the scheduled transmission time calculation unit 101, and a transmission interface (signal line or the like) unit. It has a waiting cell number information (N (τ)) output unit 733 to the scheduled time calculation unit 101 and a current time information (CT) input unit 712 from the clock 103.
[0047]
As shown in FIG. 5, the cell memory 702 is a memory having an address pointer (APtr) indicating a connection destination address and a cell storage field (CBF) for storing an arrival cell as one element. 105, a calendar queue 106, and an output list 107. Reading and writing of the cell memory 702 are controlled by a control circuit 708 via a control line 730.
[0048]
The memory 703 stores a CQH pointer indicating a head element address, a CQT pointer indicating a last element, and a storage cell number N for each scheduled transmission time for cell elements that are linked and stored in the calendar queue in units of scheduled transmission times. (Τ) is stored for the clock cycle (0 to Tmax−1). The reading and writing of the memory 703 are also controlled by the control circuit 708 via the control line 731.
[0049]
The register 704 holds an FLH pointer indicating a head element address of an unused element in the cell memory 702 linked to the free list, and an FLT pointer indicating a last element address. The register 705 holds an OLH pointer indicating the head element address of the output-waiting cell element in the cell memory 702 linked to the output list, and an OLT pointer indicating the last element address. Writing to these registers 704 and 705 is controlled by a control circuit 708 via a control line 735. In addition, at least the register 704 can hold new and old (latest and immediately before) pointers.
[0050]
The selection circuits 706 and 707 select the address information 717 and 719 when reading and writing the corresponding cell memories 702 and 703, respectively. It is controlled by the control circuit 708. The address information to the cell memory 702 includes the FLH pointer or the FLT pointer (713) output from the registers 704 and 705 or the memory 03, the CQH pointer or the CQT pointer (714), or the OLH pointer or the OLT pointer (715). Either is selected. As the address information to the memory 703, either the scheduled transmission time τ (711) from the scheduled transmission time calculation unit 101 or the current time information CT (712) from the clock 103 is selected.
[0051]
The adder circuit 732 updates the number of waiting cells N (τ) for each scheduled transmission time held in the memory 703. Upon receiving the scheduled transmission time τ of the arriving cell from the scheduled transmission time calculation unit 101, the addition circuit 732 feeds back the number of cells N (τ) at that time to the scheduled transmission time calculation unit 101 (signal line 733), and then Increment. The operation of the addition circuit 732 is also controlled by the control circuit 708 via the control line 736.
[0052]
The control circuit 708 controls the entire cell scheduler unit 701, and writes and reads the cell memory 702 and the memory 703, latch timing of the registers 704 and 705, the selection processing operation of the selection circuits 706 and 707, and the addition circuit 732. , Etc. are controlled.
[0053]
(A-2) Operation of the first embodiment
Hereinafter, the operation of the shaper device of the first embodiment will be described in detail in the order of operations of the scheduled transmission time calculation unit 101 and the cell scheduler unit 102.
[0054]
Here, the clock 103 always increments the time by one for one cell time regardless of whether or not a cell subject to the band regulation has arrived, and supplies the current time information CT to the scheduled transmission time calculation unit 101 and the cell scheduler unit 102. Suppose In addition, the scheduled transmission time calculation unit 101 collectively stores parameters and variables for all connections to be monitored, and stores the parameters and variables of the corresponding connection from an internal storage unit every time a monitored cell arrives. It is assumed that the calculated variable is taken out and the scheduled transmission time is calculated, and after the processing is completed, the updated variable is stored again in the storage location.
[0055]
(A-2-1) Operation of scheduled transmission time calculation section 101
Figure 8 5 is a flowchart showing the processing of the scheduled transmission time calculating unit 101 according to the first embodiment, and the same processing steps as those in FIG. The processing of the scheduled transmission time calculation unit 101 in this embodiment also follows a technique generally called a leaky bucket, and determines the scheduled transmission time τ so as to satisfy the minimum transmission interval of continuous cells in the same connection. This regulates the peak cell rate.
[0056]
It should be noted that the scheduled transmission time calculation unit 101 of the first embodiment uses the same leaky bucket capacity C, leaky bucket accumulation counter value S, leak rate L, and counter increase width F , The cell required delay time D, the previous cell arrival time LAT, and the clock cycle Tmax, as well as the number of waiting cells N (τ) at the scheduled transmission time τ, using the peak cell rate L / A process for restricting to F is performed.
[0057]
The scheduled transmission time calculation unit 101 of this embodiment also monitors the presence or absence of cell arrival when the shaper device is activated, and when the arrival of a cell is confirmed, the time difference between the current time CT and the previous cell arrival time LAT. Δt, that is, the current arrival interval of the connection is calculated, and the previous cell arrival time LAT is updated to the current time CT for the next arrival, and thereafter, the counter value S before the leaky bucket is updated and Δt time Are compared with each other (Steps 302 to 305).
[0058]
In the case of S ≦ Δt · L, it means that the fluid (cell) remaining in the leaky bucket at the time of the previous arrival has already disappeared before the arrival of the current cell, so that the current arrival cell can be immediately transmitted. Then, the required delay time D is set to 0, and the accumulated amount counter value S is also set to 0 (steps 306 and 307).
[0059]
On the other hand, in the case of S> Δt · L, even if the fluid (cell) S remaining in the leaky bucket at the previous arrival leaks by the leak rate L for the arrival interval Δt, the fluid (cell) remains in the leaky bucket at the current arrival at the cell. This corresponds to the remaining cell, and the accumulated amount counter value S is updated to the remaining amount of the leaky bucket at the time of arrival of the current cell, that is, S−Δt · L (step 308).
[0060]
Thereafter, the updated counter value S is compared with the difference CF between the bucket capacity C and the counter increment F (step 309). This comparison is based on the assumption that when the amount of fluid (F) due to the current cell arrival is added to the remaining amount (S) of the leaky bucket at the time of the current cell arrival, the amount (S + F) exceeds the bucket capacity C, This corresponds to determining whether overflow occurs from the upper edge of the leaky bucket.
[0061]
In the case of S> C−F (in the case of S + F> C), when the current cell arrival is valid, overflow occurs from the upper edge of the leaky bucket. Is output to the cell scheduler unit 102, and the process for the currently arriving cell ends (step 310).
[0062]
On the other hand, if S ≦ CF (if S + F ≦ C), the required delay time D is calculated as an integer value int [S / L] of the quotient S / L (step 311). In this step processing, the current arrival cell is transmitted after the storage amount (S) corresponding to all cells remaining at the time of arrival of the current cell leaks out, and the leak rate is L. Therefore, the time required for transmitting all the remaining cells (S), that is, the time required for transmitting the currently arriving cell, is S / L. In this example, the time is united by 1. Therefore, the idea is that the integer part becomes a delay time until the current arrival cell is transmitted.
[0063]
Regardless of whether there is no remaining amount (S) of the leaky bucket at the time of arrival of the current cell or whether it is present to such an extent that the arriving cell is not discarded, the accumulated amount counter value S and When the required delay time D is obtained, the scheduled transmission time τ of the current arrival cell is calculated and output to the cell scheduler unit 102 (step 812, similar to step 313 in FIG. 3). From the current time CT and the required delay time D, the transmission scheduled time τ is simply obtained as the sum CT + D, but since the clock 103 has a cycle of Tmax, the sum CT + D is equal to the clock cycle Tmax. In consideration of the increase, the scheduled transmission time τ is obtained as a modulo value when the above-mentioned sum CT + D is divided by the clock cycle Tmax.
[0064]
Finally, the number of waiting cells N (τ) (a value not counting the number of cells arriving this time) stored in the column of the scheduled transmission time τ obtained in step 812, received from the cell scheduler unit 102, is calculated. In consideration of the above, the storage amount counter value S of the leaky bucket is updated, and a series of processes for the current arrival cell ends (step 813).
[0065]
Unless other connections are taken into account, the storage amount counter value S at the end of the processing is calculated by adding the increase amount F due to the current cell arrival to the storage amount counter value S at the current cell arrival (the value calculated in step 307 or 308). (See step 312 according to the related art). However, in the related art that does not consider other connections, the above-described problem occurs. Therefore, in the first embodiment, in order to reflect the status of other connections, the number of waiting cells N (τ) stored in the column of the scheduled transmission time τ is also the storage amount counter value at the end of the processing. The accumulated amount counter value S at the end of the process is used as a value obtained by adding F + LN (τ) to the accumulated amount counter value S at the time of cell arrival this time.
[0066]
In the calculation formula S: = S + F + L · N (τ), S + F on the right side is the storage amount counter value S at the time of cell arrival this time (the value calculated by step 307 or 308), taking into account only the connection of the arrival cell. ) Is the component obtained by adding the increase F due to the current cell arrival. L · N (τ) on the right side is to be added according to the following concept.
[0067]
If there is a cell of another connection that has already arrived and has the scheduled transmission time τ calculated in step 812 as the scheduled time, the current cell arrives at all other cells of the same scheduled transmission time τ (the number of N (τ)) is not transmitted until after the cells are output, and the transmission is delayed from the scheduled time τ. Actually, when determining the scheduled transmission time of the next arrival cell from the current arrival cell transmitted at such a delayed time while keeping the minimum cell interval determined by the user declared value, the current arrival cell is transmitted. The delay from the scheduled time must be taken into account, and the scheduled transmission time determined for the next arriving cell must reflect the delay of the current arrival cell from the scheduled transmission time. L · N (τ) is added to the sum S + F of the accumulated amount counter value S (the value calculated in step 307 or 308) and the increment F due to the current cell arrival.
[0068]
As a result, in the next process of step 311, the component of L · N (τ) becomes N (τ), and the scheduled transmission time at the next cell arrival is N (τ) later than when only the same connection is considered. Therefore, even if the actual transmission time for the current arrival cell is later than the scheduled transmission time τ, the scheduled transmission time of the next arrival cell is also delayed by that amount, and the output interval of the adjacent cells may be affected by other connections. Without receiving, the CDV can be absorbed and the user's declared value can be satisfied.
[0069]
(A-2-2) Operation of cell scheduler section 102
Next, the operation of the cell scheduler unit 102 according to the first embodiment will be described in the order of arrival cell processing and cell transmission processing with reference to the configuration block diagram of FIG.
[0070]
[Arrival cell processing of cell scheduler section 102]
When the cell whose band is to be regulated arrives, the cell that has arrived is temporarily stored in the cell storage field CBF of the unused element at the head position in the cell memory 702 indicated by the FLH pointer of the register 704. At this time, the selection circuit 706 selects and outputs the FLH pointer (713) read from the FLH pointer storage section of the register 704, and uses it as an address input to the cell memory 702.
[0071]
Here, the subsequent processing is performed unless the scheduled transmission time τ of the cell received from the scheduled transmission time calculation unit 101 is invalid information. If the information is invalid information, the cell is discarded, and no further processing is performed. Also, when there is no unused element in the free list, the arriving cell is similarly discarded.
[0072]
If the scheduled transmission time τ is valid, the unused element indicated by the FLH pointer in the register 704 is assigned to the arrival cell and changes to the used element, so the FLH pointer needs to be updated. That is, since the unused element at the link destination indicated by the APtr pointer of the element storing the arrival cell indicated by the FLH pointer is the next head unused element, the control circuit 708 determines the APtr pointer The value is provided to the FLH pointer storage area of the register 704 via the signal line 722 and stored as a new FLH pointer.
[0073]
At this time, if the number of remaining unused elements becomes one, the FLT pointer that defines the last element also points to the same unused element as the FLH pointer that defines the first element, so the signal line 722 is It is also connected to a pointer 704. Further, when the arriving cell is stored in the last unused element, there is no remaining unused element, and the FLH and FLT pointers are invalidated by the control circuit 708.
[0074]
Next, the element storing the arrival cell is stored in the calendar queue corresponding to the time τ in the calendar queue from the free list by the following pointer processing based on the scheduled transmission time τ from the scheduled transmission time calculation unit 101. Moved to
[0075]
In the processing for the arriving cell, the selection circuit 707 is controlled to select the scheduled transmission time τ, and reads out the CQT pointer in the memory 703 having the transmission scheduled time τ selected by the selection circuit 707 as an address. Then, the old FLH pointer is written to the APtr pointer of the element of the cell memory 702 in which the arriving cell is stored (signal line 723) and given to the cell memory 702 via the selection circuit 706 (signal line 723). The old FLH pointer is also written to the CQT pointer at time τ (signal line 727). If there is no connected element column (cell) corresponding to the scheduled transmission time τ, the old FLH pointer is directly written into the memory 703 as the CQH and CQT pointers (signal line 727).
[0076]
In addition, during the process of moving the element relating to the arriving cell into the calendar queue, the number N (τ) of waiting cells at the scheduled transmission time τ is read from the memory 703 and transmitted to the scheduled transmission time calculation unit 101. (Signal line 733), the increment processing is performed by the addition circuit 732, and the result is stored again in the memory 703 (signal line 734).
[0077]
As described above, when a cell arrives, the arriving cell is stored in the head element of the free list indicated by the FLH pointer at that time, and the element indicated by the concatenation pointer of the head element is changed to the head element of the free list. When an effective estimated arrival time τ is given, an element that has changed from an unused element related to the current arrival cell to a used element is connected to the end of the element sequence at that time τ in the calendar queue. After outputting the cell number N (τ) not including the current arrival cell at the scheduled transmission time τ to the scheduled transmission time calculation unit 101, the cell number N (τ) is incremented by one.
[0078]
[Cell transmission process of cell scheduler section 102]
Next, a description will be given of cell transmission processing in the cell scheduler unit 102, that is, processing of transmitting buffered cells according to a schedule of scheduled transmission time.
[0079]
Upon receiving the current time information CT from the clock 103 via the signal line 712, the cell scheduler unit 701 first moves a connected element (cell) group in the calendar queue corresponding to the current time CT to the output list as follows. Perform various processing.
[0080]
First, the address information 719 selected by the selection circuit 707 is set to the current time CT from the clock 103.
[0081]
Using the current time CT as an address, a CQH pointer and a CQT pointer that define the first and last elements of the concatenated element string at that time CT are read from the memory 703, and if the output list is empty, each is stored in the register 705. It is stored as an OLH pointer and an OLT pointer (signal lines 728 and 729). At this time, when only one element (cell) moves to the output list, the read CQH pointer value is stored as the OLH pointer and the OLT pointer.
[0082]
If an element (cell) already exists in the output list, the element group indicated by the CQH pointer and the CQT pointer read from the memory 703 is linked to the end. That is, the CQT pointer value read from the memory 703 is stored in the OLT pointer defining the last element in the output list of the register 705 (signal line 729), and the cell memory 702 in the cell memory 702 having the old OLT pointer as an address is stored. The CQH pointer read from the memory 703 is stored in the storage area of the APtr pointer (connection destination pointer) of the element. Here, when only one element moves, both the updated APtr pointer and the updated OLT pointer become the CQH pointer value read from the memory 703.
[0083]
Next, the control circuit 708 clears, to 0, the cell count value N (τ) corresponding to the element (cell) column in which the current time CT moved to the output list is the scheduled transmission time.
[0084]
As described above, the element (cell) row in the calendar queue whose current time CT is the scheduled transmission time is linked to the latter half of the output list.
[0085]
The cell group moved to the output list is sequentially transmitted from the output line 710 one cell at a time, as described below.
[0086]
When the current time CT is updated and the above-described movement processing to the output list is completed, the control circuit 708 gives the OLH pointer of the register 705 to the cell memory 702 via the selection circuit 706 as an address, and the element having the address That is, the cell information in the cell storage field CBF of the first element in the output list is transmitted from the output line 710.
[0087]
As a result, the element pointed to by the APtr pointer of this element becomes the first element in the output list at the next time, so that the APtr pointer value is read from the cell memory 702 and stored in the OLH pointer area of the register 705. (Signal line 724). If the number of remaining cells (elements) in the output list becomes one by the current cell transmission, the APtr pointer value read from the cell memory 702 is stored in the register 705 in addition to the OLH pointer area. It is also stored in the area of the OLT pointer. If there are no remaining cells in the output list due to cell transmission, the area of the OLH pointer and the OLT pointer of the register 705 is invalidated.
[0088]
The old head element in the output list from which the cell has been transmitted is in an unused state, and is moved to the free list again as follows.
[0089]
The FLT pointer is read from the register 704 and given as an address to the cell memory 702 via the selection circuit 706, and the element at that address, that is, the APtr pointer of the last element in the free list, is stored in the register 705. The OLH pointer value is stored, and the old OLH pointer value is written into the FLT pointer of the register 704. If there is no unused element in the free list, the old OLH pointer value is stored together with the FLH pointer of the register 704.
[0090]
As described above, every time the current time is changed, the cell stored in the head element in the output list is output, and the element is moved to the tail of the frame list.
[0091]
Next, a specific operation example of the shaper device of the first embodiment having the above-described configuration and performing the above-described operation will be described with reference to FIG.
[0092]
FIG. 9 is a time chart showing an example of an operation under a cell arrival state and a user report condition similar to FIG. 6 used in the description of the conventional problem. That is, connection A with a user declared value of C = 15, F = 7, L = 2, connection B with a user declared value of C = 15, F = 5, L = 1, user declared value of C = 15, When the cell of the connection C in which F = 4 and L = 1 arrives in a state in which the minimum cell interval is not always satisfied by receiving the CDV before the arrival of the shaper device as shown in the time chart 901, The transition 902 of the leaky bucket accumulated amount counter value S in the scheduled transmission time calculation unit 101, the cell waiting state 903 in the calendar queue, the cell transmission process 904 from the shaper device, and the transmission cell interval 905 are shown.
[0093]
Also in the first embodiment, the leaky bucket accumulation amount counter value S shown in the time chart 902 is calculated, and according to the counter value S, the scheduled transmission time τ is calculated for each arriving cell. It is accumulated in the queue at each scheduled transmission time. Also in the first embodiment, the same scheduled transmission time may be calculated for cells belonging to different connections. The cells A4 and C4, B4 and A5, B5 and C6, and B6 and C6, respectively, have the same scheduled transmission time calculated from the previous cell arrival time. It was done.
[0094]
However, in the first embodiment, the accumulated amount counter value S including the arrival cell also reflects the number of cells N (τ) at the scheduled transmission time. A higher value may occur, and the number of cells whose scheduled transmission time τ is later than that of the conventional cell increases. As is clear from the comparison of the time charts 603 and 903, the scheduled transmission times of the cells C5, A6, C6, A7, C7 and A8 are determined later than in the past. That is, the cells C4, A5, C6 and C7 determined later at the same scheduled transmission time are actually output later than the scheduled transmission time, and the cell transmission is delayed due to the existence of the cell of another connection. Since the accumulated amount counter value S is corrected using the number of waiting cells N (τ) and reflected in the determination of the next scheduled transmission time, the scheduled transmission time is set to the next arrival cell of the same connection. It can be said that the transmission time is determined based on the actual transmission time rather than the scheduled transmission time for the same connection determined last time, and the CDV can be suppressed as apparent from comparison with FIG.
[0095]
Specifically, the cell interval between the cells A5 and A6 is 2 cell times in the related art, but is 3 cell times in the first embodiment, and the cell interval between the cells C5 and C6 is The interval is 2 cell hours in the related art, but is changed to 4 cell hours in the first embodiment. That is, the definition of the minimum cell interval can be satisfied differently from the related art.
[0096]
(A-3) Effects of the first embodiment
According to the shaper device of the first embodiment described above, the following effects can be obtained.
[0097]
(1) Even when a cell transmission schedule overlaps between different connections at the same time and a cell whose output is delayed from the scheduled time occurs, for a connection whose output is to be waited for, the cell transmission scheduled time calculation processing is performed by the amount of the wait. Since the variable is corrected, it is possible to prevent the occurrence of CDV with the subsequent cell of the connection, and to satisfy the required minimum cell transmission interval.
[0098]
The guarantee of the minimum cell interval is the most important factor in the bandwidth management of the ATM network, and the above effect is significant.
[0099]
(2) The correction of the variable in the cell transmission scheduled time calculation processing is handled by adding a simple function of counting the number of waiting cells in the transmission scheduled time unit, so that the circuit scale does not increase.
[0100]
In general, even the conventional apparatus generally has a function of counting the number of waiting cells for each scheduled transmission time, and the first embodiment expands and uses the function and parameters to transmit the cells. Since only the feedback to the scheduled time calculation unit is provided, only one product-sum operation function unit in the scheduled transmission time calculation unit is added, and there is almost no increase in the circuit scale.
[0101]
As described above, in comparison with the conventional device, it is necessary to add a product-sum operation function in the scheduled transmission time calculation unit. However, this calculation unit is already included in the scheduled transmission time calculation unit, and the same calculation unit is switched. Utilization can further suppress an increase in circuit scale.
[0102]
(3) The most significant feature of the spacing policer system used in the first embodiment is that a huge number of connections can be bandwidth-controlled at the same time. Since the process is executed only at the time of cell transmission, the features of the first embodiment are not impaired at all, and the number of connections allowed by the device is not limited.
[0103]
(B) Second embodiment
Next, a second embodiment of the cell output band regulating device according to the present invention will be described in detail with reference to the drawings.
[0104]
(B-1) Configuration of Second Embodiment
FIG. 10 is a block diagram showing the configuration of the cell output band regulating device according to the second embodiment, in which the same and corresponding parts as those in FIG. 1 according to the first embodiment are denoted by the same reference numerals. .
[0105]
This cell output band regulating device also includes a scheduled transmission time calculation unit 101, a cell scheduler unit 102, and a clock 103. The clock 103 is the same as that of the first embodiment.
[0106]
The scheduled transmission time calculating unit 101 of the second embodiment calculates the scheduled transmission time τ for each arriving cell by using the connection number m of the cell transmitted from the cell scheduler unit 102, and Is different from the first embodiment in that the connection number m is also used.
[0107]
The point that the cell scheduler unit 102 of the second embodiment does not include a storage unit for the number of waiting cells N (τ) at each scheduled transmission time (may be provided, The second embodiment is different from the first embodiment in that the connection number m of the cell transmitted from the cell scheduler unit 102 is fed back to the scheduled transmission time calculation unit 101.
[0108]
FIG. 11 is a block diagram conceptually showing, at a more specific level, the internal configuration of the cell scheduler unit 102 (701) of the second embodiment having the configuration shown in FIG. The same reference numerals are given to the same and corresponding parts.
[0109]
When the configuration of the cell scheduler unit 701 is viewed at such a level, the following points are different from the configuration of the first embodiment, and the other configuration is the same as that of the first embodiment.
[0110]
(1) An addition circuit (see reference numeral 732 in FIG. 7) for incrementing the cell number N (τ) at the scheduled transmission time τ by 1 is not provided. (2) Parameter memory (MEM) 703 for each transmission time Is not provided with an area for the number of cells N (τ), and there is no feedback line to the scheduled transmission time calculation unit 101 for the number of cells N (τ). (3) The control circuit 708 determines that the connection number m of the output cell is This is different from the configuration of the first embodiment in that the configuration is such that the data is fed back to the scheduled transmission time calculation unit 101.
[0111]
(B-2) Operation of the second embodiment
Hereinafter, the operation of the shaper device according to the second embodiment will be described in detail in the order of operations of the scheduled transmission time calculation unit 101 and the cell scheduler unit 102. Here, the clock 103 always increments the time by one per cell time regardless of whether or not a cell subject to the band regulation has arrived, and supplies the current time information CT to the scheduled transmission time calculation unit 101 and the cell scheduler unit 102. Suppose The scheduled transmission time calculation unit 101 collectively stores parameters and variables for all the connections to be monitored, and applies to each time a monitored cell arrives and every time a cell is output to the outside. It is assumed that the connection parameters and variables are taken out from the internal storage unit to calculate the scheduled transmission time, etc., and that the updated variables are stored again in the storage location after the processing is completed.
[0112]
(B-2-1) Operation of scheduled transmission time calculation section 101
The processing of the scheduled transmission time calculation unit 101 according to the second embodiment also follows a technique generally called a leaky bucket, and the scheduled transmission time τ is set so as to satisfy the minimum transmission interval between consecutive cells in the same connection. Is determined to regulate the peak cell rate. However, in the case of the second embodiment, the operation of the scheduled transmission time calculation unit 101 is performed when a cell arrives at the shaper device and when the cell is transmitted from the shaper device. Operation is divided into:
[0113]
Note that the scheduled transmission time calculation unit 101 of the second embodiment includes the same leaky bucket capacity C, accumulated counter value S in leaky bucket, leak rate L, counter increment F, cell required delay time D, Not only the previous cell arrival time LAT and the clock cycle Tmax, but also the number of stored cells (the number of unsent arrival cells) N (k) in the cell scheduler unit 102 for the connection of the arrival cell (connection number is k), and The connection to be monitored is limited to the peak cell rate L / F by using the latest (immediately before) cell transmission time RDT (k) of the connection.
[0114]
First, the operation of the scheduled transmission time calculation unit 101 when a cell arrives will be described with reference to the flowchart in FIG. 12, the same reference numerals are given to the same and corresponding steps as those in FIG. 3 related to the conventional device and FIG. 8 related to the first embodiment. Further, in FIG. 12, for the same variables and parameters as those in the related art, (k) defining the connection number k of the arriving cell is omitted, but S (k), L (k), F (K), D (k) and LAT (k).
[0115]
Until the shaper apparatus is activated and starts processing, and the processing of step 313 is executed, the same processing as that of the conventional apparatus is performed, and the description thereof will be omitted. In these step processes, the accumulated amount counter value S to be used may have been calculated in step 1218 to be described later. In this respect, it can be said that this is not the same as in the conventional apparatus.
[0116]
The arriving cell is valid, and in step 312, the storage amount counter value S at the time of arrival is increased by an amount (F) corresponding to the current arrival cell, and in step 313, the current time CT and the accumulation time at the time of arrival are increased. When the scheduled transmission time τ is calculated from the delay time D to output the current arrival cell obtained based on the quantity counter value S, the updated accumulated amount counter value S and the calculated scheduled transmission time τ are appropriate. Review whether or not it is as follows. That is, the cell scheduler unit 102 reconfirms whether or not the number of standby cells N (k) of the connection k and the previous actual transmission time RDT (k) of the connection k are appropriate.
[0117]
In this series of review processing, first, the number N (k) of untransmitted cells of the connection k of the arriving cell is incremented by one so as to include the current arriving cell (step 1214), and then the peak cell rate F / L is satisfied. The latest scheduled transmission time τ0 of the arrival cell is calculated (step 1215). The latest scheduled transmission time τ0 that satisfies the peak cell rate F / L is simply the N (k) number of untransmitted cells at the peak cell rate F / L at the previous actual transmission time RDT (k). It is obtained by adding the time int [N (k) · F / L] required for transmission (integerization int is performed because the time is updated one by one). Since the cycle is one cycle, the sum is calculated as a modulo value divided by the clock cycle Tmax.
[0118]
In this manner, when the latest scheduled transmission time τ0 of the arrival cell satisfying the peak cell rate F / L is obtained, the current scheduled transmission time τ of the arrival cell obtained based on the accumulated amount counter value S at the time of arrival is calculated. Is compared with the latest scheduled transmission time τ0 in consideration of the peak cell rate (step 1216).
[0119]
If τ ≧ τ0, the scheduled transmission time τ may be considered to satisfy the peak cell rate F / L. Therefore, the accumulated amount counter value S including the arriving cell amount obtained in step 312, and in step 313, A series of processing upon arrival at the cell is completed without changing the calculated scheduled transmission time τ.
[0120]
On the other hand, if τ <τ0, the scheduled transmission time τ does not satisfy the peak cell rate F / L, so the accumulated amount counter value S and the scheduled transmission time τ obtained in steps 312 and 313 are set to the following values. Then, a series of processing upon arrival of the cell is completed (steps 1217 and 1218). That is, the scheduled transmission time τ of the currently arriving cell is reset with a delay to the earliest time τ0 considered to satisfy the peak cell rate F / L of the connection (step 1218). As described above, the scheduled transmission time τ obtained from the accumulated amount counter value S at the time of arrival is updated so as to be delayed by the time τ0−τ, so that the calculation of the scheduled transmission time of the next arriving cell of this connection also requires such a delay. In order to reflect the time, the storage amount counter value S obtained in step 312 is also increased by L · (τ0−τ) corresponding to the delay time (step 1217).
[0121]
The shaper that satisfies the specified value of the minimum cell transmission interval not only for the arriving cell but also for the arriving cells after this arriving cell by checking and correcting the peak cell rate with respect to the once-determined transmission scheduled time as described above. The operation can be realized.
[0122]
Next, the operation of the scheduled transmission time calculation unit 101 when transmitting cells from the shaper device will be described with reference to the flowchart of FIG.
[0123]
The scheduled transmission time calculation unit 101 confirms whether or not a cell has been transmitted from the cell scheduler unit 102 (step 1302). When the cell is transmitted, the cell scheduler 102 determines the connection number m of the cell from the cell scheduler unit 102. Receive (Step 1303). Then, the scheduled transmission time calculation unit 101 decrements the internally managed storage cell number N (m) for the connection m by 1 and updates the latest cell transmission time RDT (m) of the connection m from the clock 103. Is set to the current time CT, and a series of processing at the time of cell transmission is completed (steps 1304 and 1305).
[0124]
By utilizing the number of stored cells N (m) and the latest cell transmission time RDT (m) which are appropriately updated by such a process at the time of cell transmission at the time of cell arrival, the stored amount counter value S at the time of arrival is obtained. A review reflecting the peak cell rate can be executed on the accumulated amount counter value S and the scheduled transmission time τ updated by the arrival cell obtained based on the calculated cell count.
[0125]
(B-2-2) Operation of cell scheduler section 102
Next, the operation of the cell scheduler unit 102 according to the second embodiment will be described in the order of arrival cell processing and cell transmission processing with reference to the block diagram of FIG.
[0126]
[Arrival cell processing of cell scheduler section 102]
The operation of the cell scheduler unit 102 when a cell arrives in the second embodiment is almost the same as in the first embodiment.
[0127]
That is, the operation of storing the arrival cell in the cell storage field of the last unused element and updating the FLH pointer defining the last unused element is the same as in the first embodiment. Also, the operation of moving the element storing the arrival cell from the free list to the waiting cell column corresponding to the time τ in the calendar queue by pointer processing based on the scheduled transmission time τ from the scheduled transmission time calculation unit 101. Are the same as in the first embodiment. Therefore, a detailed description of these operations is omitted.
[0128]
However, in the case of the second embodiment, even if the element storing the arriving cell is moved from the free list to the waiting cell row corresponding to the scheduled transmission time τ in the calendar queue, the accumulated cell number N corresponding to the time τ The difference from the first embodiment is that the operation for updating (τ) is not executed.
[0129]
[Cell transmission process of cell scheduler section 102]
Next, a description will be given of cell transmission processing in the cell scheduler unit 102, that is, processing of transmitting buffered cells according to a schedule of scheduled transmission time.
[0130]
The operation of moving the connected element (cell) group in the calendar queue corresponding to the current time CT to the output list based on the current time information CT from the clock 103 is substantially the same as in the first embodiment. , And a detailed description thereof will be omitted. In the case of the second embodiment, during such a movement, the cell count value N (τ) corresponding to the element (cell) column having the current time CT moved to the output list as the scheduled transmission time is calculated. The operation of clearing to 0 is not executed, and this point is different from the first embodiment.
[0131]
The cell group moved to the output list, which is executed after the movement processing, is sequentially transmitted from the output line 710 one cell at a time, and the elements changed to unused elements by the transmission are moved to the free list. The operation to be performed is almost the same as that of the first embodiment, and a detailed description thereof will be omitted.
[0132]
In the second embodiment, the control circuit 708 takes in the connection number m of the cell output to the output line 710 from the output list, and outputs it to the scheduled transmission time calculation unit 101. , Is different from the first embodiment. This connection number m is used in the above-described operation shown in FIG.
[0133]
Next, a specific operation example of the shaper device according to the second embodiment having the above-described configuration and performing the above-described operation will be described with reference to FIG.
[0134]
FIG. 14 is a time chart showing an example of operation under the same cell arrival status and user declaration condition as in FIG. 6 used in the description of the conventional problem. That is, connection A with a user declared value of C = 15, F = 7, L = 2, connection B with a user declared value of C = 15, F = 5, L = 1, user declared value of C = 15, When a cell of connection C with F = 4 and L = 1 receives CDV and arrives in a state in which the minimum cell interval rule is not always satisfied before the arrival of the shaper device as shown in the time chart 1401, The transition 1402 of the leaky bucket accumulation amount counter value S in the scheduled transmission time calculation unit 101, the cell waiting state 1403 in the calendar queue, the cell transmission process 1404 from the shaper device, and the transmission cell interval 1405 are shown.
[0135]
Also in the second embodiment, the leaky bucket accumulation amount counter value S shown in the time chart 1402 is calculated, and according to the counter value S, the scheduled transmission time τ is calculated for each arriving cell. It is accumulated in the queue at each scheduled transmission time. Also in the first embodiment, the same scheduled transmission time may be calculated for cells belonging to different connections. The cells A4 and C4, B4 and A5 and C5, B5 and C6, and C7 and A8 are connected to the same time column in the calendar queue because the transmission scheduled times calculated from the previous cell arrival times are the same. It has been queued.
[0136]
However, in the second embodiment, the accumulated amount counter value S including the arriving cell reflects the cell number N (k) and the latest transmission time RDT (k) in the connection. The amount counter value S may take a higher value than before, and the number of cells whose scheduled transmission time τ is later than before increases. In addition, since the scheduled transmission time τ is reviewed in consideration of the number of cells N (k) in the connection and the latest transmission time RDT (k), the number of cells whose scheduled transmission time τ is later than in the past increases. As is clear from the comparison between the time charts 603 and 1403, the scheduled transmission times of the cells C6, A7, C7 and A8 are determined later than in the past.
[0137]
That is, cells A4 and C4, B4 and A5 and C5, B5 and C6, and C7 and A8 belonging to different connections have the same scheduled transmission time calculated from the previous cell arrival time. And the cells C4, A5, C5, C6, and A8 are actually output later than the scheduled transmission time. As described above, for the delayed cell transmission, Since the correction process is performed using the number of waiting cells m in the calendar queue in connection units, the scheduled transmission time for subsequent arrival cells of the same connection is rather than the previously determined scheduled transmission time for the same connection. It can be said that it is determined based on the actual transmission time, and it is clear that the CDV can be suppressed as compared with FIG. Kill.
[0138]
Specifically, the cell interval between the cells A5 and A6 remains the same as the conventional device, ie, two cells, but the space between the subsequent cells A6 and A7 expands from four cells to five cells, and the minimum cell The effect between the cells A5 and A6 that do not satisfy the interval is mitigated by delaying the subsequent cells. Further, the space between cells C5 and C6 is expanded from 2 cells to 4 cells as compared with the conventional device, and satisfies the minimum cell interval.
[0139]
(B-3) Effects of the second embodiment
According to the shaper device of the second embodiment described above, the following effects can be obtained.
[0140]
(1) Even when a cell to be waited for overlaps at the same time between different connections and a cell to be waited for occurs, by correcting the variable of the cell transmission scheduled time calculation processing by the amount of waiting for the connection to be waited for. , The occurrence of CDV with the succeeding cell can be suppressed, and the effect that the required minimum cell transmission interval cannot be satisfied can be reduced.
[0141]
As described above, the guarantee of the minimum cell interval is the most important factor in the bandwidth management of the ATM network, and the above effect is significant.
[0142]
(2) Since the correction of the variable in the cell transmission scheduled time calculation processing is performed by adding a simple function of counting the number of waiting cells in connection units, the circuit scale does not increase.
[0143]
In addition, in order to realize the second embodiment, it is necessary to add functions such as a product-sum operation, a division operation, and a modulo operation in the scheduled transmission time calculation unit. These calculation units are already included in the scheduled transmission time calculation unit. Therefore, by switching and using the same operation unit, an increase in the circuit scale can be further suppressed.
[0144]
(3) The biggest feature of the spacing policer system used in the second embodiment is that an enormous number of connections can be bandwidth-controlled at the same time. Since the second embodiment is executed only at the time of cell transmission, the features of the second embodiment are not impaired at all, and the number of connections allowed by the apparatus is not limited.
[0145]
(C) Other embodiments
As described above, the present invention has been described in detail with reference to the two embodiments, but the present invention is not limited to the above-described embodiments.
[0146]
(1) The scheduled cell transmission time calculation unit 101 in both embodiments may be configured as hardware as long as it can execute the processing shown in the above-described flowchart, and may be configured as software using a DSP or the like. It may be configured in a typical manner.
[0147]
(2) In the first embodiment, an example in which the counting process and the holding of the number N (τ) of accumulated cells for each scheduled transmission time are performed by the cell scheduler unit is described. You may.
[0148]
(3) In the second embodiment, the cell scheduler unit executes the update processing and holding of the number N (k) of stored cells for each connection and the latest transmission time RDT (k), and sends the updated data to the scheduled transmission time calculation unit each time. You may hand it over.
[0149]
(4) The cell memory for buffering the arriving cells may not be physically one memory, and each of the free list, the calendar queue, and the output list may be realized by a separate memory.
[0150]
(5) In both embodiments, the leaky bucket type method is used to calculate the scheduled transmission time for each arrival cell. However, the present invention is not limited to the leaky bucket type, but may be other methods, for example, within a certain fixed time width. Even if a method called a window type defined by the number of passing cells is applied, there is no problem in its feasibility. In short, any method may be used as long as it can correct the variables and parameters for determining the scheduled transmission time so as to reflect the information on the actual cell transmission time.
[0151]
【The invention's effect】
As described above, according to the first aspect of the present invention, in the process of queuing cells in units of scheduled transmission time, the number of queued cells is counted for each scheduled transmission time, and the counting is performed by the scheduled transmission time calculation means. Means for counting the number of cells for each scheduled transmission time, and the number of cells for each scheduled transmission time Using Used to calculate the scheduled transmission time of the arrival cell Leaky bucket accumulated amount counter value To To reflect the number of cells transmitted after the scheduled transmission time Since the variable correction means for correcting is provided, the regulation of the cell transmission interval can be satisfied and the CDV can be suppressed before and after the scheduled transmission times of the cells of different connections become the same.
[0152]
According to the second aspect of the present invention, a connection information management unit counts queuing cells for each connection for each connection, and records and holds the latest cell transmission time of the connection. Connection information updating means for detecting a connection number to which a transmission cell belongs at the time of cell transmission and updating a queued cell count value and the latest cell transmission time for the connection; and a queued count value for each connection. And when sending the latest cell Time Based on The latest scheduled transmission time satisfying the predetermined peak rate is compared with the scheduled transmission time of the arrival cell, and when the scheduled transmission time of the arrival cell is equal to or longer than the latest scheduled transmission time, Scheduled transmission time of arrival cell Is corrected to the latest scheduled transmission time, and the next arrival cell Used to calculate scheduled transmission time The leaky bucket accumulation amount counter value is now reflected to the delay time from the scheduled transmission time of the arriving cell. Since the correction means is provided for correcting, the cell transmission interval can be satisfied and the CDV can be suppressed even before and after the scheduled transmission times of cells of different connections become the same.
[Brief description of the drawings]
FIG. 1 is a block diagram illustrating a schematic configuration of a first embodiment.
FIG. 2 is a block diagram showing a general configuration of a shaper device.
FIG. 3 is a processing flowchart of a conventional scheduled transmission time calculation unit.
FIG. 4 is a functional block diagram showing a conceptual configuration of a conventional cell scheduler unit.
FIG. 5 is an explanatory diagram showing a configuration of an element.
FIG. 6 is a time chart for explaining a conventional problem.
FIG. 7 is a block diagram illustrating a configuration example of a cell scheduler unit according to the first embodiment.
FIG. 8 is a processing flowchart of a scheduled transmission time calculation unit according to the first embodiment.
FIG. 9 is a time chart for explaining effects of the first embodiment.
FIG. 10 is a block diagram illustrating a schematic configuration of a second embodiment.
FIG. 11 is a block diagram illustrating a configuration example of a cell scheduler unit according to the second embodiment.
FIG. 12 is a processing flowchart at the time of arrival of a cell by a scheduled transmission time calculation unit according to the first embodiment.
FIG. 13 is a flowchart illustrating a process performed by the scheduled transmission time calculation unit according to the first embodiment when transmitting a cell.
FIG. 14 is a time chart for explaining effects of the second embodiment.
[Explanation of symbols]
101: scheduled transmission time calculation unit, 102: cell scheduler unit, 103: clock, N (τ): number of cells waiting for transmission in units of scheduled transmission time, k: connection number of arrival cell, N (k): transmission of connection k Number of waiting cells, RDT (k): latest transmission time of connection k.

Claims

In the cell output band regulating device that regulates the output band of the cell using the regulation of the cell transmission interval,
A scheduled transmission time means for calculating a scheduled transmission time of the cell each time the cell arrives, based on a parameter defining a cell output band;
Cell sending means for queuing cells of all connections in the calculated scheduled transmission time unit, and transmitting the cells queued at the time at a time when the scheduled cell transmission time is reached;
In the queuing process of the cells in the scheduled transmission time unit, the number of queued cells is counted for each scheduled transmission time, and the scheduled transmission time cell for giving the counted number of cells in the scheduled transmission time unit to the scheduled transmission time calculation means. Number counting means,
Variable correction means for correcting the leaky bucket accumulated amount counter value used for calculating the scheduled transmission time of an arrival cell using the number of cells at each scheduled transmission time so as to reflect the number of cells transmitted later than the scheduled transmission time. A cell output band regulating device, comprising:

In the cell output band regulating device that regulates the output band of the cell using the regulation of the cell transmission interval,
A scheduled transmission time means for calculating a scheduled transmission time of the cell each time the cell arrives, based on a parameter defining a cell output band;
Cell sending means for queuing cells of all connections in the calculated scheduled transmission time unit, and transmitting the cells queued at the time at a time when the scheduled cell transmission time is reached;
Connection information management means for counting the number of queued cells for each connection for each connection subject to regulation, and recording and holding the latest cell transmission time of the connection;
Connection information updating means for detecting a connection number to which a transmission cell belongs at the time of cell transmission, and updating a queued cell count value and a latest cell transmission time for the connection;
Compared with the last delivery scheduled time to meet the count value and the latest cell transmission during the time and a predetermined peak rate rather than based on the in queuing of each connection, and sending the estimated time of arrival cell, is sending the estimated time of arrival cell If it is longer than the latest scheduled transmission time, the scheduled transmission time of the arriving cell is corrected to the latest scheduled transmission time, and the leaky bucket accumulation amount counter value used for calculating the scheduled transmission time of the next arriving cell is changed to the scheduled transmission time of the arriving cell. A cell output band regulating device, comprising: a correction unit that corrects the delay so as to reflect a delay time from time .