JP3157113B2 - トラヒックシェイパー装置 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】この発明は、非同期転送モー
ド型の通信網におけるトラヒックシェイパー装置に関
し、特にサービス属性の異なるセルが混在する場合に適
用して好適なものである。

【０００２】

【従来の技術】近年、情報通信の分野においては、通信
ニーズの多様化、情報交換／伝送技術の高度化、デバイ
ス技術の発展等に伴い、ユーザ情報を高速、広帯域で交
換、伝送可能な高速広帯域サービス統合ディジタル網
（以下、Ｂ−ＩＳＤＮ）の実用化が急速に進められてい
る。

【０００３】このＢ−ＩＳＤＮにおいては、情報転送方
式として非同期転送モード（以下、ＡＴＭ）が採用され
ている。このＡＴＭ通信においては、情報はセルと呼ば
れる固定長のパケットで転送、交換される。この場合、
セルの転送先は各セル毎に付与される相手先アドレス情
報に基づいて識別される。

【０００４】従って、従来の時分割方式の回線交換とは
異なり、各端末は空いている時間軸上のスロットの任意
位置にセルを送出することができ、網内でも伝送路上の
任意位置へのセル多重が可能となる。

【０００５】このためＡＴＭ通信では、あらかじめ使用
するセル通信帯域（例えば、ピークセルレートや平均セ
ルレート）を各端末に通信開始前に申告させ、網側では
その情報に基づいて帯域管理が行われる。この網内帯域
管理機能の１つにセル出力帯域規制（以下、シェイパ
ー）がある。このシェイパーは、網内でのセル多重、交
換処理の際、同時刻に同一方路へと向かう複数のセルが
到着した場合に、出力待ち合わせによって生じるセル遅
延ゆらぎ（以下、ＣＤＶ）を吸収し、ユーザ申告値に従
ってセルを出力回線へと送出させる機能である。

【０００６】従来、シェイパー方式としていくつかの方
式が提案されている。そのうちの１つとして、文献（例
えば、"The Spacing Policer,An Algorithm for Effici
entPeak Bit Rate Control in ATM Networks",ISS'92,N
o.A5.5,Yokohama,October 1995 ）に記載されたスペー
シングポリサー（Spacing Policer ）がある。この方式
は、到着セルごとに申告値を満足する送出予定時刻を算
出し、この算出された送出予定時刻ごとにキューイング
されたセルを順次１セルずつ読み出し送出していくこと
で、網内発生ＣＶＤの軽減やユーザ申告値を満足するセ
ル送出の実現を図っている。

【０００７】図２はシェイパー装置の基本的な装置構成
を示す図である。図示するようにシェイパー装置２０１
は、到着セル毎に有効セルを識別し送出予定時刻τを算
出するセル識別＆送出予定時刻算出部２０２と、到着セ
ルを一旦格納し送出予定時刻τに従ってセル送出のスケ
ジューリングを行うセルスケジューラ部２０３と、これ
らセル識別＆送出予定時刻算出部２０２とセルスケジュ
ーラ部２０３へ現在時刻ＣＴを与える時計２０４から構
成される。また、セル識別＆送出予定時刻算出部２０２
は、通信中の全コネクションについてユーザ申告値情報
や後述する各種パラメータをも保持する。時計２０４は
周期Ｔmax を有し、１セル時間に「１」ずつ現在時刻Ｃ
Ｔをインクリメントする。

【０００８】図２において、セル２０５が到着すると、
セル識別＆送出予定時刻算出部２０２は、まず、そのセ
ルが有効なものであるかどうか識別し、その識別結果を
セルスケジューラ部２０３へと通知する。さらにこのセ
ル２０５が有効セルであった場合には、このセル２０５
の属するコネクションの情報から、当該セル２０５がセ
ルスケジューラ部２０３内でどの程度、遅延されれば申
告値を満足するか所要遅延時間を求め、この遅延時間に
基づいて送出予定時刻τを算出し、セルスケジューラ部
２０３へ提供する。また、セルスケジューラ部２０３で
は、到着したセルが有効セルであった場合にのみ、受け
とった送出予定時刻τに基づき、セル２０５を送出予定
時刻τごとにキューイングされたセルバッファ部の最後
尾に格納し、時計２０４の経過に従って１セルずつ送出
していく。

【０００９】図３は従来技術によるセルスケジューラ部
の概念的構成を示すブロック図である。図示するように
セルスケジューラ部３０１は、到着セルを格納するセル
メモリ（以下、単にＣＭとも記載）３０２とセルメモリ
３０２のアドレス情報を司るポインタ群３０７〜３０９
で構成される。セルメモリ３０２は１セル単位のエレメ
ント群３０６で構成されている。

【００１０】図４はエレメント群３０６を構成するエレ
メントの１つを拡大して示したものであり、１セル分の
情報を格納するセル格納フィールド（以下、ＣＢＦ）４
０２と他のエレメントを指し示すアドレスポインタ（以
下、ＡＰｔｒ）４０１から成る。このアドレスポインタ
４０１を用いることで、エレメントは他のエレメントと
数珠つなぎに連結できる。

【００１１】セルメモリ３０２はまた、未使用エレメン
トを管理するフリーリスト（以下、単にＦＬとも記載）
３０３と、待ち合わせ中のセルが送出予定時刻ごとに連
結されて格納されているカレンダーキュー（以下、単に
ＣＱとも記載）３０４、及び出力待ち状態にあるセルを
管理するアウトプットリスト（以下、ＯＬとも記載）３
０５に分割されている。

【００１２】フリーリスト３０３は、セルメモリ３０２
内の全ての未使用エレメントを連結しており、その先頭
エレメント及び最終エレメントのアドレスは、フリーリ
スト用ポインタ３０７のフリーリストヘッダ（以下、Ｆ
ＬＨとも記載）ポインタとフリーリストテイル（以下、
ＦＬＴとも記載）ポインタによりそれぞれ格納されてい
る。

【００１３】カレンダーキュー３０４は、時計周期Ｔma
x 分の送出予定時刻毎に到着セルを連結させて格納して
おり、それぞれの連結セル群はフリーリスト３０３と同
様、カレンダーキュー用ポインタ群３０８のカレンダー
キューヘッダ（以下、ＣＱＨ）、カレンダーキューテイ
ル（以下、ＣＱＴ）により、先頭エレメントと最終エレ
メントが示されている。送出予定時刻に１つもセルが連
結されていなければ、そのＣＱＨポインタとＣＱＴポイ
ンタは、なにも示さず無効情報となっている。

【００１４】アウトプットリスト３０５には、現在時刻
ＣＴが送出予定時刻と一致したセル群が移動してきて格
納されており、アウトプットリスト用ポインタ３０９の
アウトプットリストヘッダ（以下、ＯＬＨ）とアウトプ
ットリストテイル（以下、ＯＬＴ）により先頭エレメン
ト及び最終エレメントが指し示されている。アウトプッ
トリスト３０５に蓄積されたセルは、先頭セルから順次
１セル時間に１セルずつ出力回線３１２に送出されてい
く。セルが送出された後の空きエレメントは再びフリー
リスト３０３の最後尾に連結されて、以降の到着セルの
格納に使用される。

【００１５】ここでセルメモリ３０２は、論理的にフリ
ーリスト３０３、カレンダーキュー３０４及びアウトプ
ットリスト３０５に分割されてはいるが、物理的には１
つの共有型のメモリで実現されており、フリーリスト３
０３からカレンダーキュー３０４へ、さらにアウトプッ
トリスト３０５への移動は全てポインタ処理によって行
われ、各エレメント内のセル情報自体が移動することは
ない。

【００１６】

【発明が解決しようとする課題】上述したように、従来
は到着セルごとにユーザ申告値を満足するような送出予
定時刻を前セル到着時刻に基づいて算出し、その送出予
定時刻単位に到着セルをセルスケジューラ内に一旦格納
しておき、時計の現在時刻が送出予定時刻になった時点
で、その時刻列に格納されているセル群を送出待ちキュ
ーに移動し、先頭セルから順次送出することで、シェイ
パー機能を実現していた。

【００１７】しかしながら、このような構成では、ＡＴ
Ｍ通信において要求されるベストエフォート型のサービ
スに対応することができない。このベストエフォート型
サービスとは、主として非即時系のデータ通信をＡＴＭ
網を介して行う際に、網の使用効率をより向上させるべ
く提供されるサービスである。

【００１８】通常のサービスでは、上述したように、使
用する通信帯域が予め端末より申告され、それに基づい
て網では帯域制限を行う（以下、帯域確保型サービ
ス）。これに対してベストエフォート型サービスでは、
使用する通信帯域ではなく、必要とする最小帯域のみ申
告する（以下、ＡＢＲサービス：Ａvairable Ｂit Ｒ
ate ）、あるいは帯域の申告は何も行わない（以下、Ｕ
ＢＲサービス：Ｕnspecified Ｂit Ｒate ）。網内で
は、このベストエフォート型サービスに属するセルは、
送出する帯域確保型サービスのセルが存在しない場合に
のみ、送出可能となり、またＡＢＲサービスの場合には
最小帯域が確保される。

【００１９】従来技術であるシェイパー装置において、
これらベストエフォート型サービスを、帯域確保型サー
ビスと混在して提供しようとしても、ベストエフォート
型サービスのセルの送出予定時刻の算出が不可能であ
り、また両者の分離がされていないため、カレンダーキ
ュー内に混在して格納されることになり、本来のベスト
エフォート型サービスを提供できないという問題点があ
った。

【００２０】本発明は、上記課題に鑑みてなされたもの
で、サービス属性の異なるセルが混在しているときで
も、それぞれのサービス特性を損なうこと無くＡＴＭ通
信を行い得るトラヒックシェイパー装置を提供すること
を目的とする。

【００２１】

【課題を解決するための手段】かかる課題を解決するた
め、第１の本発明においては、帯域規制要求に基づいて
セルの出力帯域の規制を実行するトラヒックシェイパー
装置において、以下の手段を具備することを特徴とす
る。

【００２２】すなわち、(1) 到着したセルの属するサー
ビス種別を識別する識別手段と、(2) 到着したセルの属
するサービス種別が出力帯域を確保するタイプであると
きには当該セルの到着毎に当該セルの送出予定時刻をセ
ル出力帯域パラメータに基づいて算出する算出手段と、
(3)この算出手段で算出された送出予定時刻単位に、出
力帯域を確保するタイプのサービス種別の全コネクショ
ンのセルをキューイングするキューイング手段と、(4)
到着したセルの属するサービス種別が出力帯域を保証す
る必要のないタイプであるときには当該到着セルを、出
力帯域を保証する必要のないタイプのサービス種別の全
コネクションについて共通なバッファに格納する格納手
段と、(5)セル送出時刻が更新されたときに、更新され
たセル送出時刻又はそれより以前の時刻を送出予定時刻
としたセルが前記キューイング手段にキューイングされ
ているときにはそのセルを送出し、更新されたセル送出
時刻又はそれより以前の時刻を送出予定時刻としたセル
が前記キューイング手段にキューイングされていないと
きには前記格納手段に格納されている最古のセルを 送出
する送出手段とを具備したことを特徴とする。

【００２３】また、上記課題を解決するため、第２の本
発明においては、帯域規制要求に基づいて、セルの出力
帯域の規制を実行するトラヒックシェイパー装置におい
て、以下の手段を具備することを特徴とする。

【００２４】すなわち、(1) 到着したセルの属するサー
ビス種別を識別する識別手段と、(2)到着したセルの属
するサービス種別が出力帯域を確保するタイプであると
きには当該セルの到着毎に当該セルの送出予定時刻をセ
ル出力帯域パラメータに基づいて算出する第１の算出手
段と、(3)この第１の算出手段で算出された送出予定時
刻単位に、出力帯域を確保するタイプのサービス種別の
全コネクションのセルをキューイングするキューイング
手段と、(4)到着したセルの属するサービス種別が最小
出力帯域のみ保証する必要のあるタイプであるときには
当該セル到着毎に当該セルの最大待ち合わせ可能時刻を
セル出力帯域パラメータに基づいて算出する第２の算出
手段と、(5)この第２の算出手段で算出された最大待ち
合わせ可能時刻単位に、最小出力帯域のみ保証する必要
のあるタイプのサービス種別の全コネクションのセルを
キューイングする第２のキューイング手段と、(6)セル
送出時刻が更新されたときに、更新されたセル送出時刻
又はそれより以前の時刻を最大待ち合わせ可能時刻とし
たセルが前記第２のキューイング手段にキューイングさ
れているときにはそのセルを送出し、更新されたセル送
出時刻又はそれより以前の時刻を最大待ち合わせ可能時
刻としたセルが前記第２のキューイング手段にキューイ
ングされておらず、かつ、更新されたセル送出時刻又は
それより以前の時刻を送出予定時刻としたセルが前記第
１のキューイング手段にキューイングされているときに
はそのセルを送出し、更新されたセル送出時刻又はそれ
より以前の時刻を最大待ち合わせ可能時刻としたセルが
前記第２のキューイング手段にキューイングされておら
ず、かつ、更新されたセル送出時刻又はそれより以前の
時刻を送出予定時刻としたセルが前記第１のキューイン
グ手段にキューイングされていないときには前記第２の
キューイング手段に格納されている最古のセルを送出す
る送出手段とを具備したことを特徴とする。

【００２５】

【発明の実施の形態】（Ａ）第１の実施形態 以下、本発明によるトラヒックシェイパー装置の第１の
実施形態を図面を参照しながら詳述する。

【００２６】（Ａ−１）第１の実施形態の構成 本発明におけるシェイパー装置も、基本的には上述した
図２に示すような構成をとっており、到着セル毎に有効
セルを識別し送出予定時刻τを算出するセル識別＆送出
予定時刻算出部２０２と、到着セルをいったん格納し送
出予定時刻τに従ってセル送出のスケジューリングを行
うセルスケジューラ部２０３と、セル識別＆送出予定時
刻算出部２０２とセルスケジューラ部２０３へ現在時刻
ＣＴを与える時計２０４とから構成される。

【００２７】図２において、セル２０５が到着すると、
セル識別＆送出予定時刻算出部２０２はそのセルの属す
るコネクションの情報から、まず当該セルが帯域確保型
サービスに属するか、あるいはベストエフォート型サー
ビスに属するかを識別し、スケジューラ部へ通知する。
このときセル２０５が帯域確保型サービスのセルであれ
ば、そのセルがセルスケジューラ部２０３内でどれ程遅
延されれば申告値を満足するか所要遅延時間を求め、そ
れを基に送出予定時刻τを算出し、セルスケジューラ部
２０３へ提供する。このように、本実施形態ではセル識
別＆送出予定時刻算出部２０２が、到着セルを帯域確保
型であるか、あるいはベストエフォート型であるかにつ
いてのサービス種別の識別まで行う機能を保有する。

【００２８】図１は、本発明であるシェイパー装置にお
けるスケジューラ部の、第１の実施形態の概念的構成を
示すブロック図である。本実施形態では、ベストエフォ
ートサービスのうちＵＢＲサービスが帯域確保型サービ
スと混在する場合について説明する。

【００２９】このセルスケジューラ部１０１は、セル識
別＆送出予定時刻算出部から信号線１１６を介して入力
されるセル識別情報と、同じくセル識別＆送出予定時刻
算出部から信号線１１５を介して入力されるセル送出予
定時刻τと、時計から信号線１１７を介して入力される
現在時刻ＣＴとをそれぞれ入力し、これらを基に、信号
線１１３を介して入力される到着セルを、帯域確保型サ
ービス、ＵＢＲサービスそれぞれに応じて、スケジュー
リングしながら出力回線１１４へと送出していく。

【００３０】セルスケジューラ部１０１は、到着セルを
格納するセルメモリ１０２、セルメモリ１０２のアドレ
ス情報を司るポインタ群１０８〜１１１、及び帯域確保
型サービスのセルとＵＢＲサービスのセルを選択出力す
るセレクタ１１２から構成される。

【００３１】セルメモリ１０２は、１セル単位のエレメ
ント群１０７で構成されている。上述した図４は、この
第１の実施形態におけるエレメントの１つを拡大したも
のでもあり、１セル分の情報を格納するセル格納フィー
ルド４０２と他のエレメントを指し示すアドレスポイン
タ４０１からなる。このアドレスポインタを用いること
で、エレメントは他のエレメントと数珠つなぎに連結さ
れる。

【００３２】セルメモリ１０２はまた、未使用エレメン
トを管理するフリーリスト（以下、ＦＬ）１０３、待ち
合わせ中のセルが送出予定時刻毎に連結されて格納され
ているカレンダーキュー（以下、ＣＱ）１０４、出力待
ち状態にあるセルを管理するアウトプットリスト（以
下、ＯＬ）１０５、及びＵＢＲサービスに属するセルが
格納されるＵＢＲキュー（以下、ＵＢＲＱ）１０６に理
論的に分割されている。ここでフリーリスト１０３は、
帯域確保型サービス、ＵＢＲサービス両者に共通に使用
されるが、カレンダーキュー１０４とアウトプットリス
ト１０５は帯域確保型サービスのセルのみに、ＵＢＲキ
ュー１０６はＵＢＲサービスのセルのみに使用される。

【００３３】フリーリスト１０３は、セルメモリ１０２
内の全ての未使用エレメントを連結しており、その先頭
エレメント及び最終エレメントのアドレスは、フリーリ
スト用ポインタ１０８のフリーリストヘッダ（以下、Ｆ
ＬＨ）ポインタとフリーリストテイル（以下、ＦＬＴ）
ポインタによりそれぞれ格納されている。

【００３４】カレンダーキュー１０４は、時計周期Ｔma
x 分の送出予定時刻毎に、帯域確保型サービスに属する
到着セルを連結させて格納しており、それぞれの連結セ
ル群はフリーリスト１０３と同様、カレンダーキュー用
ポインタ群１０９のカレンダーキューヘッダ（以下、Ｃ
ＱＨ）、カレンダーキューテイル（以下、ＣＱＴ）によ
り、先頭エレメントと最終エレメントが示されている。
送出予定時刻に１つもセルが連結されていなければ、そ
のポインタＣＱＨとＣＱＴは何も示さず無効情報となっ
ている。

【００３５】アウトプットリスト１０５には、現在時刻
ＣＴが送出予定時刻と一致したセル群が移動してきて格
納されており、アウトプットリスト用ポインタ１１０の
アウトプットリストヘッダ（以下、ＯＬＨ）とアウトプ
ットリストテイル（以下、ＯＬＴ）により先頭エレメン
ト及び最終エレメントが指し示されている。アウトプッ
トリスト１０５に蓄積されたセルは、先頭セルから順次
１セル時間に１セルずつ出力回線１１９（最終的には出
力回線１１４）へと送出されていく。セルが送出された
後の空きエレメントは再びフリーリスト１０３の最後尾
に連結されて、以降の到着セルの格納に使用される。

【００３６】ＵＢＲキュー１０６には、ＵＢＲサービス
に属するセルが、到着順に連結されて格納されており、
ＵＢＲＱ用ポインタ１１１のＵＢＲヘッダ（以下、ＵＢ
ＲＨ）とＵＢＲテイル（以下、ＵＢＲＴ）により、先頭
エレメント及び最終エレメントが指し示されている。勿
論、１つもセルが連結されていなければ、ポインタＵＢ
ＲＨとＵＢＲＴは何も示さず無効情報となっている。こ
のＵＢＲキュー１０６に格納されたＵＢＲサービスセル
は、帯域確保型セルで送出待ちのものが無い場合、即ち
アウトプットリスト１０５にセルが格納されていない場
合にのみ、出力回線１２０に出力される。この時、セレ
クタ１１２は、ＵＢＲキュー１０６からのセルを出力回
線１１４へと出力する処理を行う。

【００３７】（Ａ−２）第１の実施形態の動作 以下、この第１の実施形態のシェイパー装置の動作を詳
細に説明する。

【００３８】ここでシェイパー装置の時計は、図２に示
すように帯域規制対象のセル到着の有無にかかわらず、
常に１セル時間に１ずつインクリメントされており、セ
ル識別＆送出予定時刻算出部２０２とセルスケジューラ
部２０３に、現在時刻ＣＴを供給しているとする。

【００３９】まず、セルスケジューラ部の動作を説明す
る。図５は、セルスケジューラ部５０１の基本装置構成
を示すブロック図であり、セルメモリ（ＣＭ）５０２、
メモリ（ＭＥＭ）５０３、レジスタ群５０４、５０５及
び５０６、選択回路（ＳＥＬ）５０７及び５０８、及び
制御回路５０９により構成されている。

【００４０】このセルスケジューラ部５０１は、外部イ
ンタフェースとして、セル入力（信号線５１０）、セル
出力（信号線５１１）、セル識別＆送出予定時刻算出部
からの送出予定時刻τ（信号線５１２）とセル識別情報
（信号線５１４）、及び時計からの現在時刻ＣＴ（信号
線５１３）をそれぞれの信号線を介して入力する。

【００４１】セルメモリ５０２は、図４にも示したよう
に、連結先アドレスを示すアドレスポインタ（ＡＰｔ
ｒ）と、到着セルを格納するセル格納フィールド（ＣＢ
Ｆ）を１エレメントとするメモリであり、図１における
フリーリスト１０３、カレンダーキュー１０４、アウト
プットリスト１０５及びＵＢＲキュー１０６を実現して
いる。このセルメモリ５０２の読み出し、書き込み動作
は、制御線５３３を介して制御回路５０９により制御さ
れる。

【００４２】メモリ５０３は、カレンダーキュー内に送
出予定時刻単位に連結して蓄積されているセルエレメン
トについて、先頭エレメントアドレスを示すポインタＣ
ＱＨと最終エレメントを示すポインタＣＱＴを、時計周
期分（０〜Ｔmax ）格納している。メモリ５０３の読み
出し、書き込み動作は、制御線５３５を介して制御回路
５０９により制御される。

【００４３】レジスタ５０４は、フリーリスト内に連結
されているセルメモリ５０２内の未使用エレメントの、
先頭エレメントアドレスを示すポインタＦＬＨと、最終
エレメントアドレスを示すポインタＦＬＴとを保持して
いる。同様にレジスタ５０５は、アウトプットリスト内
に連結されているセルメモリ５０２内の出力待ちセルエ
レメントの、先頭エレメントアドレスを示すポインタＯ
ＬＨと、最終エレメントアドレスを示すポインタＯＬＴ
とを保持している。さらにレジスタ５０６は、ＵＢＲＱ
内に連結されているセルメモリ５０２内ＵＢＲサービス
セルエレメントの、先頭エレメントアドレスを示すポイ
ンタＵＢＲＨと、最終エレメントアドレスを示すポイン
タＵＢＲＴとを保持している。レジスタ５０４、５０５
および５０６への書き込み動作は、制御線５３４を介し
て制御回路５０９により制御される。

【００４４】選択回路５０７と５０８はそれぞれ、セル
メモリ５０２とメモリ５０３の読み出し、書き込みを行
う際のアドレス情報５１９と５２１の選択を行い、両者
の選択動作は制御線５２０と５３６を介して制御回路５
０９により制御されている。セルメモリ５０２へのアド
レス情報には、信号線５１５を介して入力されるＦＬＨ
あるいはＦＬＴ、信号線５１６を介して入力されるＣＱ
ＨあるいはＣＱＴ、信号線５１７を介して入力されるＯ
ＬＨあるいはＯＬＴ、あるいは信号線５１８を介して入
力されるＵＢＲＨあるいはＵＢＲＴのいずれかが選択さ
れる。メモリ５０３へのアドレス情報は、信号線５１２
を介して入力されるセル識別＆送出予定時刻算出部から
の送出予定時刻τ、あるいは信号線５１３を介して入力
される時計からの現在時刻ＣＴのいずれかが選択され
る。

【００４５】制御回路５０９は、セルスケジューラ部５
０１全体の制御を司っており、セルメモリ５０２、メモ
リ５０３の書き込み、読み出し動作、レジスタ５０４〜
５０６のラッチタイミング（書き込みタイミング）、お
よび選択回路５０７と５０８の選択処理動作等を制御す
る。

【００４６】次に、第１の実施形態のセルスケジューラ
部１０１の動作を、到着セル処理とセル送出処理との順
に、図５の構成ブロック図を参照しながら説明する。

【００４７】［セルスケジューラ部１０１の到着セル処
理］ 帯域確保型サービス、ＵＢＲサービスいずれかの帯域規
制対象のセル到着時、まず到着セルは、ＦＬＨポインタ
５０４で示されるセルメモリ５０２内の先頭未使用エレ
メントのセル格納フィールドＣＢＦに一旦格納される。
この際、選択回路５０７は、信号線５１５を介して入力
されるＦＬＨを選択出力し、セルメモリ５０２のアドレ
ス入力としている。ここでフリーリスト内の未使用エレ
メントが無い場合には、到着セルは廃棄扱いとなり、以
降の処理は実施されない。

【００４８】到着セルが格納された場合、これまでＦＬ
Ｈ５０４で示されていた未使用エレメントが到着セルへ
と割り当てられることになるので、ＦＬＨポインタの更
新が必要となる。即ち、これまでＦＬＨポインタで示さ
れていた当該到着セルを格納したエレメントのＡＰｔｒ
ポインタで示されされる未使用エレメントが、次の先頭
未使用エレメントとなるので、前記ＡＰｔｒポインタ値
を信号線５２３を介してそのまま新ＦＬＨポインタとす
ればよい。

【００４９】このとき、残りの未使用エレメントが１つ
になる場合には、ＦＬＴポインタもまたＦＬＨポインタ
と同じ未使用エレメントを指し示すことになるため、信
号線５２３はＦＬＴポインタ５０４へも接続されてい
る。さらに、当該到着セルが最後の未使用エレメントに
格納された場合には、残りの未使用エレメントは無くな
り、ＦＬＨ及びＦＬＴポインタは無効となる。

【００５０】次に到着セルを格納した当該エレメント
は、そのセルの属するサービスにより異なる処理を受け
る。サービスの属性は、セル識別情報５１４に基づいて
判断される。

【００５１】帯域確保型サービスの場合、到着セルを格
納したエレメントは、セル識別＆送出予定時刻算出部か
らの送出予定時刻τに従い、ポインタ処理によりフリー
リストからカレンダーキュー内の送出予定時刻τに対応
する待ち合わせセル列に移動される。この処理は、送出
予定時刻τをアドレスにして読み出されたメモリ５０３
内のＣＱＴポインタが示すカレンダーキュー内エレメン
ト列の、最後尾エレメント内ＡＰｔｒポインタに信号線
５２４を介して旧ＦＬＨポインタ値を書き込み、前記Ｃ
ＱＴポインタもまた信号線５３２を介して旧ＦＬＨポイ
ンタ値とすることで実現される。送出予定時刻τに相当
する連結エレメント列に何もセルが存在していなかった
場合には、旧ＦＬＨポインタ値が信号線５３２を介して
そのままＣＱＨ及びＣＱＴポインタとなる。

【００５２】ＵＢＲサービスの場合、到着セルを格納し
たエレメントはＵＢＲＱ内エレメント列の最後尾に移動
される。この処理は、ＵＢＲＴポインタ５０６の示す最
後尾エレメント内ＡＰｔｒポインタに信号線５２４を介
して旧ＦＬＨポインタ値を書き込み、前記ＵＢＲＴポイ
ンタもまた信号線５３１を介して旧ＦＬＨポインタ値と
することで実現できる。ＵＢＲＱ内に連結されていたセ
ルが何も無かった場合には、旧ＦＬＨポインタ値が信号
線５３１を介してそのままＵＢＲＨ及びＵＢＲＴポイン
タとなる。

【００５３】［セルスケジューラ部１０１のセル送出処
理］ 時計からの現在時刻ＣＴを信号線５１３より受信したセ
ルスケジューラ部５０１では、この現在時刻ＣＴに相当
するカレンダーキュー内の連結セル群をアウトプットリ
ストに移動させる処理が行われる。

【００５４】まず、選択回路５０８の選択出力５２１
が、現在時刻ＣＴに設定される。この現在時刻ＣＴをア
ドレスとして、メモリ５０３から読み出されるＣＱＨ及
びＣＱＴポインタの指し示すセルメモリ５０２内のセル
群をアウトプットリストに移動させる。

【００５５】アウトプットリストに何も残存セルのない
場合は、ＣＱＨとＣＱＴポインタが、それぞれ信号線５
２９及び５３０を介して入力され、そのままＯＬＨ及び
ＯＬＴポインタ５０５となる。移動するセルが１つだけ
の場合は、前記ＣＱＨポインタ値が前記ＯＬＨ及びＯＬ
Ｔポインタとなる。

【００５６】アウトプットリスト内に既にセルがある場
合、ＣＱＨとＣＱＴポインタの示すセル群をその最後尾
に連結させることになり、信号線５３０を介して前記Ｏ
ＬＴポインタにＣＱＴポインタ値がセットされ、旧ＯＬ
Ｔポインタの指し示すセルメモリ５０２内エレメントの
ＡＰｔｒポインタ値が、新たに前記ＣＱＨポインタにな
る（信号線５２２）。ここで、移動するセルが１つだけ
の時は、前記ＡＰｔｒポインタとＯＬＴポインタが共に
当該ＣＱＨポインタ値に設定される（信号線５２２、５
２９）。

【００５７】アウトプットリストに移動されたセル群
は、次に１セル時間に１セルずつ順次出力線５１１から
送出されていく。ＯＬＨポインタで示されるアウトプッ
トリスト内先頭エレメントのセル格納フィールドＣＢＦ
にあるセルが、出力線５１１から送出されると、当該エ
レメントのＡＰｔｒポインタの指し示す次のアウトプッ
トリスト内エレメントが先頭となるので、前記ＡＰｔｒ
ポインタ値が信号線５２７を介してＯＬＨレジスタに入
力されＯＬＨの新ＯＬＨポインタとなる。

【００５８】セル送出によりアウトプットリスト内の残
存セルが１セルとなった場合には、ＯＬＨと共にＯＬＴ
ポインタもまた前記ＡＰｔｒポインタ値にセットされ
る。セル送出によりアウトプットリスト内の残存セルが
無くなった場合には、ＯＬＨ及びＯＬＴポインタは共に
無効となる。

【００５９】セルが送出されたアウトプットリスト内の
旧先頭エレメントは、未使用状態となり再びフリーリス
トに移動される。これは、旧ＯＬＨポインタ値が、ＦＬ
Ｔポインタ５０４の指し示すフリーリスト内の最後尾エ
レメントのＡＰｔｒポインタ（信号線５２６）と、ＦＬ
Ｔポインタ（信号線５２５）に書き込まれることで実現
される。フリーリスト内に未使用エレメントが１つも無
かった場合には、信号線５２５を介してＦＬＨポインタ
５０４も合わせて旧ＯＬＨポインタ値に設定される。

【００６０】セル送出時にアウトプットリスト内に１つ
も送出待ちのセルの無い場合、ＵＢＲサービスのセルが
送出される。即ち、ＵＢＲＱ内に連結されたエレメント
のうち先頭エレメントのセルが、出力線５１１に送出さ
れる。ＵＢＲＨポインタ５０６で示されるＵＢＲＱ内先
頭エレメントのセル格納フィールドＣＢＦにあるセルが
出力されると、当該エレメントのＡＰｔｒポインタの指
し示す次のＵＢＲＱ内エレメントが先頭となるので、前
記ＡＰｔｒポインタ値が新ＵＢＲＨポインタとなる（信
号線５３８）。

【００６１】セル送出によりＵＢＲＱ内の残存セルが１
セルとなった場合には、ＵＢＲＨと共にＵＢＲＴポイン
タもまた全ＡＰｔｒポインタにセットされる。セル送出
によりＵＢＲＱ内にセルが存在しなくなった時には、Ｕ
ＢＲＨ及びＵＢＲＴポインタは共に無効となる。

【００６２】セルが送出されたＵＢＲＱ内の旧先頭エレ
メントは、未使用状態となり再びＦＬに移動される。こ
れは、旧ＵＢＲＨポインタ値が、ＦＬＴポインタ５０４
の指し示すフリーリスト内の最後尾エレメントのＡＰｔ
ｒポインタ（信号線５２８）と、ＦＬＴポインタ（信号
線５３７）に書き込まれることで実現される。フリーリ
スト内に未使用エレメントが１つも無かった場合には、
ＦＬＨポインタ５０４も合わせて旧ＯＬＨポインタ値に
設定される（信号線５３７）。

【００６３】（Ａ−３）第１の実施形態の効果 上述した第１の実施形態のトラヒックシェイパー装置に
よれば、次のような効果を得ることができる。

【００６４】(1) ＡＴＭセルの出力帯域を規制するシェ
イパー装置において、帯域確保型サービスに属するセル
とＵＢＲ型のベストエフォートサービスに属するセルが
混在するようなＡＴＭ回線においても、両サービスの帯
域管理を同一ハードウエアで実現することが可能であ
る。

【００６５】(2) 上記シェイパー装置では、帯域確保型
サービスのセルとＵＢＲサービスのセルが論理的に分離
されて格納されるので、お互いに干渉しあうことはな
く、帯域確保型サービスのセルを常に優先的に送出する
ことが可能であると共に、帯域確保型サービスのセルの
無い場合にはＵＢＲサービスのセルを即時に送出できる
ので、網の使用効率の向上が可能である。

【００６６】(3) 本実施形態におけるハードウエア量の
増加は、従来構成と比べてＵＢＲサービス用キューのポ
インタ２個のみである。従って、ほとんどハードウェア
の増加なしに、ポインタ用レジスタの追加のみで、容易
にＵＢＲサービスを帯域確保型サービスに混在させるこ
とが可能である。

【００６７】(4) 上述したように、帯域確保型サービス
のセルとＵＢＲサービスのセルが論理的に分離されて格
納されるが格納用のメモリは物理的には共有して使用し
ており、メモリの使用効率の向上、ひいては必要なメモ
リ容量の削減効果が期待される。

【００６８】(5) 本実施形態に使用しているシェイパー
装置の最大の特徴は、膨大な数のコネクションを同時に
帯域規制可能な点にあるが、各種処理をセル到着時とセ
ル送出時にのみ実行しているので、本実施形態の実現上
でもその特徴を何ら損なうことはなく、コネクション数
を制限することはない。

【００６９】（Ｂ）第２の実施形態 次に、本発明によるトラヒックシェイパー装置の第２の
実施形態を図面を参照しながら詳述する。

【００７０】（Ｂ−１）第２の実施形態の構成 本実施形態におけるシェイパー装置も、第１の実施形態
と同様、図２に示すような基本構成をとっており、到着
セル毎に有効セルを識別し送出予定時刻τを算出するセ
ル識別＆送出予定時刻算出部２０２と、到着セルをいっ
たん格納し送出予定時刻τに従ってセル送出のスケジュ
ーリングを行うセルスケジューラ部２０３と、セル識別
＆送出予定時刻算出部２０２とセルスケジューラ部２０
３へ現在時刻ＣＴを与える時計２０４とから構成され
る。

【００７１】図２においてセル２０５が到着すると、セ
ル識別＆送出予定時刻算出部２０２はそのセルの属する
コネクションの情報から、当該セルが帯域確保型サービ
スに属するか、あるいはベストエフォート型サービスに
属するかをまず識別し、スケジューラ部へ通知する。ま
た帯域確保型サービスのセルであれば、そのセルがセル
スケジューラ部２０３内でどれ程遅延されれば申告値を
満足するか所要遅延時間を求め、それを基に送出予定時
刻τを算出し、セルスケジューラ部２０３へ提供する。
また、ベストエフォート型サービス（ＡＢＲサービス）
であった場合には、そのセルの最長可能待ち合わせ時間
を算出し、それに基づいて最も遅い場合のセル送出可能
時刻を求め、送出予定時刻τとしてセルスケジューラ部
２０３へ提供する。即ち、セルスケジューラ部２０３
が、この送出予定時刻τ以内に当該セルを送出すれば、
そのセルの属するコネクションについて、最小帯域を保
証することが可能となる。

【００７２】図６は、本発明であるシェイパー装置にお
けるセルスケジューラ部６０１の、第２の実施形態の概
念的構成を示すブロック図である。本実施形態では、ベ
ストエフォートサービスのうちＡＢＲサービスが帯域確
保型サービスと混在する場合について説明する。

【００７３】このセルスケジューラ部６０１は、セル識
別＆送出予定時刻算出部から信号線６１８を介して入力
されるセル識別情報、セル識別＆送出予定時刻算出部か
ら信号線６１７を介して入力されるセル送出予定時刻
τ、時計から信号線６１９を介して入力される現在時刻
ＣＴに基づいて、信号線６１５を介して入力される到着
セルを、帯域確保型サービス、ＡＢＲサービスのそれぞ
れに応じて、スケジューリングしながら出力回線６１６
へと送出していく。

【００７４】セルスケジューラ部６０１は、到着セルを
格納するセルメモリ６０２、セルメモリ６０２のアドレ
ス情報を司るポインタ群６０９〜６１３、帯域確保型サ
ービスのセルとＡＢＲサービスのセルを選択出力するセ
レクタ６１４、及びＡＢＲサービスの格納セル数を保持
するレジスタ（ＲＥＧ）６２４から構成される。

【００７５】セルメモリ６０２は、１セル単位のエレメ
ント群６０８で構成されている。この第２の実施形態で
も、エレメントは、図４に示すように、１セル分の情報
を格納するセル格納フィールド４０２と他のエレメント
を指し示すアドレスポインタ４０１からなる。このアド
レスポインタを用いることで、エレメントは他のエレメ
ントと数珠つなぎに連結される。

【００７６】セルメモリ６０２はまた、未使用エレメン
トを管理するフリーリスト（ＦＬ）６０３、帯域確保型
サービスの待ち合わせ中のセルが送出予定時刻毎に連結
されて格納されているカレンダーキュー（ＣＱ）６０
４、出力待ち状態にあるセルを管理するアウトプットリ
スト（ＯＬ）５０５、及びＡＢＲサービスに属する待ち
合わせ中のセルが送出予定時刻毎に連結されて格納され
ているＡＢＲキュー（ＡＢＲＱ）６０６と、出力待ち状
態にあるセルを管理するＡＢＲアウトプットリスト（Ａ
ＢＲＯＬ）６０７に理論的に分割されている。ここでフ
リーリスト６０３は、帯域確保型サービス、ＡＢＲサー
ビス両者に共通に使用されるが、カレンダーキュー６０
４とアウトプットリスト６０５は帯域確保型サービスの
セルのみに、ＡＢＲキュー６０６及びＡＢＲアウトプッ
トリスト６０７はＡＢＲサービスのセルのみに使用され
る。

【００７７】フリーリスト６０３は、セルメモリ６０２
内の全ての未使用エレメントを連結しており、その先頭
エレメント及び最終エレメントのアドレスは、ＦＬ用ポ
インタ６０９のフリーリストヘッダ（ＦＬＨ）ポインタ
とフリーリストテイル（ＦＬＴ）ポインタによりそれぞ
れ格納されている。

【００７８】カレンダーキュー６０４は、時計周期Ｔma
x 分の送出予定時刻毎に、帯域確保型サービスに属する
到着セルを連結させて格納しており、それぞれの連結セ
ル群はフリーリスト６０３と同様、カレンダーキュー用
ポインタ群６１０のカレンダーキューヘッダ（ＣＱ
Ｈ）、カレンダーキューテイル（ＣＱＴ）により、先頭
エレメントと最終エレメントが示されている。送出予定
時刻に１つもセルが連結されていなければ、そのポイン
タＣＱＨとＣＱＴは何も示さず無効情報となっている。

【００７９】アウトプットリスト６０５には、現在時刻
ＣＴが送出予定時刻と一致したセル群が移動してきて格
納されており、アウトプットリスト用ポインタ６１１の
アウトプットリストヘッダ（ＯＬＨ）とアウトプットリ
ストテイル（ＯＬＴ）により先頭エレメント及び最終エ
レメントが指し示されている。

【００８０】ＡＢＲキュー６０６もまた、時計周期Ｔma
x 分の最大待ち合わせ可能時刻毎に、ＡＢＲサービスに
属する到着セルを連結させて格納しており、それぞれの
連結セル群はフリーリスト６０３と同様、ＡＢＲキュー
用ポインタ群６１２のＡＢＲキューヘッダ（ＡＢＲＱ
Ｈ）とＡＢＲキューテイル（ＡＢＲＱＴ）により、先頭
エレメント及び最終エレメントが示されている。送出予
定時刻に１つもセルが連結されていなければ、そのポイ
ンタＡＢＲＱＨとＡＢＲＱＴは何も示さず無効情報とな
っている。

【００８１】ＲＥＧ６２４は最大待ち合わせ可能時刻毎
に、ＡＢＲキュー６０６に格納されているセル数を保持
している。すなわち、ＡＢＲキュー６０６にセルが格納
される毎に該当する時刻位置のレジスタが１だけインク
リメントされる。反対に、ＡＢＲキュー６０６からＡＢ
Ｒアウトプットリスト６０７へセルが移動した場合には
移動したセル数が、またＡＢＲキュー６０６から直接セ
ルが出力された場合には１が、該当する時刻位置のレジ
スタから減算される。このレジスタ情報に基づいてＡＢ
Ｒキュー６０６内のセル格納位置を知ることができ、後
述するＡＢＲキュー６０６から直接セルを出力すること
が可能となる。

【００８２】ＡＢＲアウトプットリスト６０７には、現
在時刻ＣＴが最大待ち合わせ可能時刻と一致したセル群
が移動してきて格納されており、ＡＢＲＯＬ用ポインタ
６１３のアウトプットリストヘッダ（ＡＢＲＯＬＨ）と
アウトプットリストテイル（ＡＢＲＯＬＴ）によりと先
頭エレメント及び最終エレメントが指し示されている。

【００８３】アウトプットリスト６０５とＡＢＲアウト
プットリスト６０７、及びＡＢＲキュー６０６内のエレ
メントに格納されたセルは、以下の優先順位に従って送
出されていく。

【００８４】(1) ＡＢＲアウトプットリスト６０７に送
出待ちセルがあれば、最優先に送出する。

【００８５】(2) ＡＢＲアウトプットリスト６０７に送
出待ちセルが無く、アウトプットリスト６０５に送出待
ちセルがあれば、アウトプットリスト６０５内のセルを
送出する。

【００８６】(3) ＡＢＲアウトプットリスト６０７にも
アウトプットリスト６０５にも送出待ちセルが無けれ
ば、ＡＢＲキュー内に連結されているセルの内、現在時
刻ＣＴに最も近い時刻系列に格納されているセルから順
次送出する。出力すべきセルは、ＲＥＧ６２４の情報に
基づいて検索する。

【００８７】上記のような優先制御を行うことで、帯域
確保型サービスに最小帯域を保証する必要のあるＡＢＲ
サービスを混在させて、シェイパーすることが可能とな
る。 （Ｂ−２）第２の実施形態の動作 以下、この第２の実施形態のシェイパー装置におけるセ
ルスケジューラ部の動作を詳細に説明する。

【００８８】ここでシェイパー装置の時計は、図２に示
すように帯域規制対象のセル到着の有無にかかわらず、
常に１セル時間に１ずつインクリメントされており、セ
ル識別＆送出予定時刻算出部２０２とセルスケジューラ
部２０３に、現在時刻ＣＴを供給しているとする。

【００８９】まず、図７を用いてセルスケジューラ部の
動作を説明する。図７は、セルスケジューラ部７０１の
基本装置構成を示すブロック図であり、セルメモリ７０
２、メモリ（ＭＥＭ）７０３、レジスタ群７０４〜７０
６及び７４０、選択回路（ＳＥＬ）７０７及び７０８、
及び制御回路７０９から構成されている。

【００９０】このセルスケジューラ部７０１はまた、外
部インタフェースとして、セル入力（信号線７１０）、
セル出力（信号線７１１）、セル識別＆送出予定時刻算
出部からの送出予定時刻τ（信号線７１２）、セル識別
情報（信号線７１４）、及び時計からの現在時刻ＣＴ
（信号線７１３）を有している。

【００９１】セルメモリ７０２は、図４にも示したよう
に、連結先アドレスを示すアドレスポインタ（ＡＰｔ
ｒ）と、到着セルを格納するセル格納フィールド（ＣＢ
Ｆ）を１エレメントとするメモリであり、図６における
フリーリスト６０３、カレンダーキュー６０４、アウト
プットリスト６０５及びＡＢＲキュー６０６、ＡＢＲア
ウトプットリスト６０７を実現している。このセルメモ
リ７０２の読み出し、書き込み動作は、制御線７３３を
介して制御回路７０９により制御される。

【００９２】メモリ７０３は、カレンダーキュー内に送
出予定時刻単位に連結して蓄積されているセルエレメン
トについて、先頭エレメントアドレスを示すポインタＣ
ＱＨと最終エレメントを示すポインタＣＱＴを、またさ
らにＡＢＲキュー内に最大待ち合わせ可能時刻単位に連
結して蓄積されているセルエレメントについて、先頭エ
レメントアドレスを示すポインタＡＢＲＯＱと最終エレ
メントを示すポインタＡＢＲＱＴを、それぞれについて
時計周期分（０〜Ｔmax ）格納している。メモリ７０３
の読み出し、書き込み動作は、制御線７３５を介して制
御回路７０９により制御される。

【００９３】レジスタ７０４は、フリーリスト内に連結
されているセルメモリ７０２内の未使用エレメントの、
先頭エレメントアドレスを示すポインタＦＬＨと、最終
エレメントアドレスを示すポインタＦＬＴを保持してい
る。同様にレジスタ７０５は、アウトプットリスト内に
連結されているセルメモリ７０２内の出力待ちセルエレ
メントの、先頭エレメントアドレスを示すポインタＯＬ
Ｈと、最終エレメントアドレスを示すポインタＯＬＴを
保持している。またレジスタ７０６は、ＡＢＲＯＬ内に
連結されているセルメモリ７０２内のＡＢＲサービスの
出力待ちエレメントの、先頭エレメントアドレスを示す
ポインタＡＢＲＯＬＨと、最終エレメントアドレスを示
すポインタＡＢＲＯＬＴを保持している。レジスタ７０
４、７０５、７０６への書き込み動作は、制御線７３４
を介して制御回路７０９により制御される。

【００９４】レジスタ群７４０（ＲＥＧ0 ，ＲＥＧ1 ，
…，ＲＥＧTmax）は、ＡＢＲキュー内に連結されて格納
されているエレメント数を、最大待ち合わせ可能時刻０
〜Ｔｍａｘ毎に計数し保持している。すなわち、ＡＢＲ
キューにＡＢＲサービスに属するセルが格納される毎に
該当する時刻位置のレジスタ７４０が１増加される。反
対に、ＡＢＲキューからＡＢＲＯＬへセルが移動した場
合には移動したセル数が、またＡＢＲキューより直接セ
ルが出力された場合には１が、該当する時刻位置のレジ
スタ７４０から減算される。このレジスタ情報に基づい
て制御回路７０９は、ＡＢＲキュー内のセル格納位置を
知ることができ、ＡＢＲキューから直接セルを出力する
場合のメモリ７０３の読み出しアドレス７３６を選択回
路７０８へと出力する。

【００９５】選択回路７０７と７０８はそれぞれ、セル
メモリ７０２とメモリ７０３の読み出し、書き込み動作
を行う際のアドレス情報７１９と７２１の選択を行い、
両者の選択動作は制御線７２０と７３６を介して制御回
路７０９により制御されている。

【００９６】セルメモリ７０２へのアドレス情報には、
信号線７１５を介して入力されるＦＬＨあるいはＦＬ
Ｔ、信号線７１６を介して入力されるＣＱＨあるいはＣ
ＱＴ、信号線７１７を介して入力されるＯＬＨあるいは
ＯＬＴ、信号線７１８を介して入力されるＡＢＲＱＨあ
るいはＡＢＲＱＴ、あるいは信号線７４２を介して入力
されるＡＢＲＯＬＨあるいはＡＢＲＯＬＴのいずれかが
選択される。

【００９７】メモリ７０３へのアドレス情報は、信号線
７１２を介して入力されるセル識別＆送出予定時刻算出
部からの送出予定時刻τ、信号線７１３を介して入力さ
れる時計からの現在時刻ＣＴ、あるいは制御回路７０９
からの直接出力アドレス７４３のいずれかが選択され
る。この直接出力アドレス７４３は、ＡＢＲＯＬ内、ア
ウトプットリスト内共に出力待ちセルの無い場合に、Ａ
ＢＲキューより直接ＡＢＲサービスのセルを送出させる
ために設定されるメモリ７０３のアドレスであり、レジ
スタ群７４０に保持されている情報から制御回路７０９
が判断して生成する。

【００９８】制御回路７０９は、セルスケジューラ部７
０１全体の制御を司っており、セルメモリ７０２、メモ
リ７０３の書き込み、読み出し動作、レジスタ群７０４
〜７０６及び７４０のラッチタイミング、選択回路７０
７と７０８の選択処理動作、ＡＢＲＱからの直接セル送
出処理の際のセル格納アドレス検索動作等を実行する。

【００９９】次に、第２の実施形態のセルスケジューラ
部７０１の動作を、到着セル処理とセル送出処理との順
に、図７の構成ブロック図を参照しながら説明する。

【０１００】［セルスケジューラ部７０１の到着セル処
理］ 帯域確保型サービス、ＡＢＲサービスのいずれかの帯域
規制対象のセル到着時、まず到着セルは、ＦＬＨポイン
タ７０４で示されるセルメモリ７０２内の先頭未使用エ
レメントのセル格納フィールドＣＢＦに一旦格納され
る。この際選択回路７０７は、ＦＬＨ７１５を選択出力
し、セルメモリ７０２のアドレス入力としている。ここ
でフリーリスト内未使用エレメントが無い場合には、到
着セルは廃棄扱いとなり、以降の処理は実施されない。

【０１０１】到着セルが格納された場合、これまでＦＬ
Ｈ７０４で示されていた未使用エレメントが到着セルへ
と割り当てられることになるので、ＦＬＨポインタの更
新が必要となる。即ち、これまでＦＬＨポインタで示さ
れていた当該到着セルを格納したエレメントのＡＰｔｒ
ポインタで示されされる未使用エレメントが、次の先頭
未使用エレメントとなるので、前記ＡＰｔｒポインタ値
を信号線７２３を介してそのまま新ＦＬＨポインタとす
ればよい。このとき、残りの未使用エレメントが１つに
なる場合には、ＦＬＴポインタもまたＦＬＨポインタと
同じ未使用エレメントを指し示すことになるため、信号
線７２３はＦＬＴポインタ７０４へも接続されている。
さらに、当該到着セルが最後の未使用エレメントに格納
された場合には、残りの未使用エレメントは無くなり、
ＦＬＨ及びＦＬＴポインタは無効となる。

【０１０２】次に到着セルを格納した当該エレメント
は、そのセルの属するサービスにより異なる処理を受け
る。サービスの属性は、セル識別情報７１４に基づいて
判断される。

【０１０３】帯域確保型サービスの場合、到着セルを格
納したエレメントは、セル識別＆送出予定時刻算出部か
らの送出予定時刻τに従い、ポインタ処理によりＦＬか
らカレンダーキュー内の送出予定時刻τに対応する待ち
合わせセル列に移動される。本処理は、送出予定時刻τ
をアドレスにして読み出されたメモリ７０３内のＣＱＴ
ポインタが示すカレンダーキュー内エレメント列の、最
後尾エレメント内ＡＰｔｒポインタに信号線７２４を介
して旧ＦＬＨポインタ値を書き込み、前記ＣＱＴポイン
タもまた信号線７３２を介して旧ＦＬＨポインタ値とす
ることで実現される。送出予定時刻τに相当する連結エ
レメント列に何もセルが存在していなかった場合には、
旧ＦＬＨポインタ値が信号線７３２を介してそのままＣ
ＱＨ及びＣＱＴポインタとなる。

【０１０４】ＡＢＲサービスの場合、到着セルを格納し
たエレメントはセル識別＆送出予定時刻算出部からの最
大待ち合わせ可能時刻τに従い、ポインタ処理によりＦ
ＬからＡＢＲキュー内のτに対応する待ち合わせセル列
に移動される。

【０１０５】この処理は、最大待ち合わせ可能時刻τを
アドレスにして読み出されたメモリ７０３内のＡＢＲＯ
Ｑポインタが示すＡＢＲキュー内エレメント列の最後尾
エレメント内ＡＰｔｒポインタに旧ＦＬＨポインタ値を
書き込み（信号線７２４）、前記ＡＢＲＱＴポインタも
また旧ＦＬＨポインタ値とする（信号線７３２）ことで
実現される。最大待ち合わせ可能時刻τに相当する連結
エレメント列に何もセルが存在していなかった場合に
は、旧ＦＬＨポインタ値がそのままＡＢＲＱＨ及びＡＢ
ＲＱＴポインタとなる（信号線７３２）。最後に該当す
る時刻のレジスタ７４０の値を１インクリメントさせ
る。

【０１０６】［セルスケジューラ部７０１のセル送出処
理］ 時計からの現在時刻ＣＴを信号線７１３より受信したセ
ルスケジューラ部７０１では、この現在時刻ＣＴに相当
するカレンダーキュー内の連結セル群をアウトプットリ
ストに、ＡＢＲキュー内の連結セル群をＡＢＲＯＬに移
動させる処理が行われる。

【０１０７】帯域確保型サービスについては、まず選択
回路７０８の選択出力７２１が、現在時刻ＣＴに設定さ
れる。この現在時刻ＣＴをアドレスとして、メモリ７０
３から読み出されるＣＱＨ及びＣＱＴポインタの指し示
すセルメモリ７０２内のセル群をアウトプットリストに
移動させる。アウトプットリストになにも残存セルのな
い場合は、ＣＱＨとＣＱＴポインタが、それぞれそのま
まＯＬＨ及びＯＬＴポインタ７０５となる（信号線７２
９及び７３０）。移動するセルが１つだけの場合は、前
記ＣＱＨポインタ値が前記ＯＬＨ及びＯＬＴポインタと
なる。アウトプットリスト内に既にセルがある場合、Ｃ
ＱＨとＣＱＴポインタの示すセル群をその最後尾に連結
させることになり、前記ＯＬＴポインタに信号線７３０
を介してＣＱＴポインタ値がセットされ、旧ＯＬＴポイ
ンタの指し示すセルメモリ７０２内エレメントのＡＰｔ
ｒポインタ値が、新たに前記ＣＱＨポインタになる（信
号線７２２）。ここで、移動するセルが１つだけの時
は、前記ＡＰｔｒポインタとＯＬＴポインタが共に当該
ＣＱＨポインタ値に設定される（信号線７２２、７２
９）。

【０１０８】ＡＢＲサービスについても上記と同様であ
り、まず選択回路７０８の選択出力７２１が現在時刻Ｃ
Ｔに設定される。この現在時刻ＣＴをアドレスとして、
メモリ７０３から読み出されるＡＢＲキューＨ及びＡＢ
ＲＱＴポインタが、それぞれそのままＡＢＲＯＬＨ及び
ＡＢＲＯＬＴポインタ７０６となる（信号線７３８及び
信号線７３９）。移動するセルが１つだけの場合は、前
記ＡＢＲＱＨポインタ値が前記ＡＢＲＯＬＨ及びＡＢＲ
ＯＬＴポインタとなる。ＡＢＲＯＬ内に既にセルがある
場合、ＡＢＲＱＨとＡＢＲＱＴポインタの示すセル群を
その最後尾に連結させることになり、前記ＡＢＲＯＬＴ
ポインタにＡＢＲＱＴポインタ値がセットされ（信号線
７３９）、旧ＡＢＲＯＬＴポインタの指し示すＣＭ７０
２内のエレメントのＡＰｔｒポインタ値が、新たに前記
ＡＢＲＱＨポインタになる。ここで移動するセルが１つ
だけのときは、前記ＡＰｔｒポインタとＡＢＲＯＬＴポ
インタが共に当該ＡＢＲＱＨポインタ値に設定される。
またこのとき、ＡＢＲキューからＡＢＲＯＬに移動され
たセル数が、当該時刻のレジスタ７４０から減算される
（すなわち、０クリアされる）。

【０１０９】ここで上述したように、アウトプットリス
トとＡＢＲＯＬ、及びＡＢＲキュー内のエレメントに格
納されたセルは、以下の優先順位に従って出力線７１１
へと送出されていく。

【０１１０】(1) ＡＢＲＯＬに送出待ちセルがあれば、
最優先に送出する。

【０１１１】(2) ＡＢＲＯＬに送出待ちセルがなく、ア
ウトプットリストに送出待ちセルがあれば、アウトプッ
トリスト内のセルを送出する。

【０１１２】(3) ＡＢＲＯＬにもアウトプットリストに
送出待ちセルがなければ、ＡＢＲキュー内に連結されて
いるセルのうち現在時刻ＣＴに最も近い時刻系列に格納
されているセルから順次送出する。

【０１１３】上記の優先順位に従って、セル送出手順を
以下説明していく。

【０１１４】まず、ＡＢＲＯＬに送出待ちのセルが存在
する場合である。この場合、ＡＢＲＯＬに移動されたセ
ル群は、次に１セル時間に１セルずつ順次出力線７１１
から送出されていく。ＡＢＲＯＬＨポインタで示される
ＡＢＲＯＬ内先頭エレメントのセル格納フィールドＣＢ
Ｆにあるセルが、出力線７１１から送出されると、当該
エレメントのＡＰｔｒポインタの指し示す次のＡＢＲＯ
Ｌ内エレメントが先頭となるので、前記ＡＰｔｒポイン
タ値が信号線７３１を介して新ＡＢＲＯＬＨポインタと
なる。セル送出によりＡＢＲＯＬ内残存セルが１セルと
なった場合には、ＡＢＲＯＬＨと共にＡＢＲＯＬＴポイ
ンタもまた前記ＡＰｔｒポインタ値にセットされる。セ
ル送出によりＡＢＲＯＬ内の残存セルが無くなった場合
には、ＡＢＲＯＬＨ及びＡＢＲＯＬＴポインタは共に無
効となる。

【０１１５】セルが送出されたＡＢＲＯＬ内の旧先頭エ
レメントは、未使用状態となり再びＦＬに移動される。
これは、旧ＡＢＲＯＬＨポインタ値が、ＦＬＴポインタ
７０４の指し示すフリーリスト内の最後尾エレメントの
ＡＰｔｒポインタ（信号線７２８）と、ＦＬＴポインタ
（信号線７３７）に書き込まれることで実現される。フ
リーリスト内に未使用エレメントが１つも無かった場合
には、ＦＬＨポインタ７０４も合わせて信号線７３７を
介して旧ＡＢＲＯＬＨポインタ値に設定される。

【０１１６】次にＡＢＲＯＬに送出待ちのセルが無く、
アウトプットリスト内にのみ送出待ちのセルが存在する
場合を説明する。この場合、アウトプットリストに連結
されたセル群は、１セル時間に１セルずつ順次出力線７
１１から送出されていく。ＯＬＨポインタで示されるア
ウトプットリスト内の先頭エレメントのセル格納フィー
ルドＣＢＦにあるセルが、出力線７１１から送出される
と、当該エレメントのＡＰｔｒポインタの指し示す次の
アウトプットリスト内のエレメントが先頭となるので、
前記ＡＰｔｒポインタ値が信号線７２７を介して新ＯＬ
Ｈポインタとなる。セル送出によりアウトプットリスト
内の残存セルが１セルとなった場合には、ＯＬＨと共に
ＯＬＴポインタもまた全ＡＰｔｒポインタにセットされ
る。セル送出によりアウトプットリスト内にセルが存在
しなくなった時には、ＯＬＨ及びＯＬＴポインタは共に
無効となる。

【０１１７】セルが送出されたアウトプットリスト内の
旧先頭エレメントは、未使用状態となり再びＦＬに移動
される。これは、旧ＯＬＨポインタ値が、ＦＬＴポイン
タ７０４の指し示すフリーリスト内の最後尾エレメント
のＡＰｔｒポインタ（信号線７２６）と、ＦＬＴポイン
タ（信号線７２５）に書き込まれることで実現される。
フリーリスト内に未使用エレメントが１つも無かった場
合には、ＦＬＨポインタ７０４も合わせて信号線７２５
を介して旧ＯＬＨポインタ値に設定される。

【０１１８】最後に、ＡＢＲＯＬにもアウトプットリス
トにも送出待ちセルが無い場合を説明する。この場合
は、ＡＢＲキュー内に連結されているセルのうち現在時
刻ＣＴに最も近い時刻系列に格納されているセルから順
次出力線７１１へと送出される。まず選択回路７０８の
選択出力、すなわちメモリ７０３の読み出しアドレス
が、制御回路７０９からのアドレス情報７４３に設定さ
れる。そして該当する最大待ち合わせ可能時刻のＡＢＲ
ＱＨポインタで示されるＡＢＲキュー内の先頭エレメン
トのセル格納フィールドＣＢＦにあるセルが、出力線７
１１から送出されると、そのエレメントのＡＰｔｒポイ
ンタの指し示す次のＡＢＲキュー内エレメントが当該時
刻での先頭となるので、信号線７４４を介して前記ＡＰ
ｔｒポインタ値が新ＡＢＲＱＨポインタとなる。セル送
出により当該時刻のＡＢＲキュー内の残存セルが１セル
となった場合には、ＡＢＲＱＨと共にＡＢＲＱＴポイン
タもまた前記ＡＰｔｒポインタ値にセットされる。セル
送出により当該時刻のＡＢＲキュー内の残存セルが無く
なった場合には、ＡＢＲＱＨ及びＡＢＲＱＴポインタは
共に無効となる。

【０１１９】セルの送出された当該時刻におけるＡＢＲ
キュー内の旧先頭エレメントは、未使用状態となり再び
ＦＬに移動される。これは、旧ＡＢＲＱＨポインタ値
が、ＦＬＴポインタ７０４の指し示すフリーリスト内の
最後尾エレメントのＡＰｔｒポインタ（信号線７２２）
と、ＦＬＴポインタ（信号線７４５）に書き込まれるこ
とで実現される。フリーリスト内に未使用エレメントが
１つも無かった場合には、信号線７４５を介してＦＬＨ
ポインタ７０４も合わせて旧ＡＢＲＱＨポインタ値に設
定される。

【０１２０】またＡＢＲキューから直接セルが送出され
た場合、当該時刻のレジスタ７４０の値が「１」減算さ
れて、再び保持される。

【０１２１】（Ｂ−３）第２の実施形態の効果 上述した第２の実施形態のトラヒックシェイパー装置に
よれば、以下のような効果を得ることができる。

【０１２２】(1) ＡＴＭセルの出力帯域を規制するシェ
イパー装置において、帯域確保型サービスに属するセル
とＡＢＲ型のベストエフォートサービスに属するセルが
混在するようなＡＴＭ回線においても、両サービスの帯
域管理を同一ハードウエアで実現可能である。

【０１２３】(2) 上記シェイパー装置では、帯域確保型
サービスのセルとＡＢＲサービスのセルが論理的に分離
されて格納されるので、お互いに干渉しあうことはな
く、帯域確保型サービスのセルを常に優先的に送出する
ことが可能であると同時に、帯域確保型サービスのセル
の無い場合にはＡＢＲサービスのセルを即時に送出で
き、またＡＢＲサービスに要求される最小帯域の保証も
行われるので、網の使用効率の向上が実現可能である。

【０１２４】(3) 本実施形態におけるハードウエア量の
増加は、従来構成と比べてＡＢＲサービス用キューのポ
インタ２個とメモリ（ＭＥＭ）のワード長（ＡＢＲＱＨ
とＡＢＲＱＴ）のみである。従って、ハードウェアの劇
的な増加なしに、容易にＡＢＲサービスを帯域確保型サ
ービスに混在させることが可能である。

【０１２５】(4) 上述したように、帯域確保型サービス
のセルとＡＢＲサービスのセルが論理的に分離されて格
納されるが、格納用のメモリは物理的には共有して使用
しており、メモリの使用効率の向上、ひいては必要なメ
モリ容量の削減効果が期待される。

【０１２６】(5) 本実施形態に使用しているシェイパー
装置の最大の特徴は、膨大な数のコネクションを同時に
帯域規制可能な点にあるが、各種処理をセル到着時とセ
ル送出時にのみ実行しているので、本実施形態の実現上
でも、その特徴は何ら損なわれず、装置が許容するコネ
クション数が制限されることはない。

【０１２７】（Ｃ）他の実施形態 以上、本発明を、２つの実施形態につき詳細に説明した
が、本発明は上述した実施形態に限定されるものでは無
く、例えば以下に示す適宜の方式を本発明のトラヒック
シェイパー装置に適用することができる。

【０１２８】(1) 到着セルを格納するセルメモリは物理
的に１つのメモリでなくても良く、フリーリスト、カレ
ンダーキュー、アウトプットリスト等それぞれ別個のメ
モリでも実現しても良い。

【０１２９】(2) 第２の実施形態において、ＡＢＲキュ
ーから直接セルを送出する際の、読み出しセルの格納位
置の検索のために、最大待ち合わせ可能時刻毎の格納セ
ル数を計数する手段を用いたが、セル格納位置の検索手
段として別の方法を用いても良く、例えばメモリ（ＭＥ
Ｍ）のアドレスを現在時刻ＣＴから１つずつ増加させて
いき、読み出すべきセルを検索する手法であっても良
い。

【０１３０】(3) 第２の実施形態において、ＡＢＲキュ
ーから直接セルを送出する際の、読み出すべきセルの選
択基準として、現在時刻ＣＴに最も近い時刻系列に格納
されているセルから順次送出する、としたが、これに捕
われること無く、例えばセル到着順序に送出する手法で
あっても良い。

【０１３１】(4) 第１の実施形態では、ベストエフォー
トサービスのうちＵＢＲサービスを、第２の実施形態に
おいてはＡＢＲサービスを、それぞれ帯域確保型サービ
スと混在させてシェーピングする構成について述べた
が、帯域確保型サービス、ＡＢＲサービス、ＵＢＲサー
ビスの全てを混在させてサポートすることも可能であ
る。この場合には第１の実施形態と第２の実施形態とを
組み合わせ、ＵＢＲサービスに属するセルの送出優先順
位を最も低くすることで実現可能である。

【０１３２】(5) 第２の実施形態において、帯域確保型
サービスとＡＢＲサービスとの間のセル送出優先順位を
ＡＢＲサービスのほうを高く設定する例を説明したが、
逆に帯域確保型サービスの方を高く設定することも可能
であり、この場合のハードウェア構成は全く変更を要し
ない。

【０１３３】

【発明の効果】以上のように、本発明によれば、到着す
るセルの属するサービス種別を識別し、この識別された
セルのサービス属性に応じて処理内容を切り替え、各サ
ービス属性に属するセルの送出時刻が重なったときには
各サービスに要求される特性に応じてセル送出の優先処
理を行うので、サービス属性が異なるセルが混在してい
る場合であっても、それぞれのサービスの特性を損なう
こと無く通信を行うことができる。

【０１３４】

【図面の簡単な説明】

【０１３５】

【図１】第１の実施形態の概念的構成を示すブロック図
である。

【０１３６】

【図２】シェイパー装置の基本的な装置構成を示すブロ
ック図である。

【０１３７】

【図３】従来技術によるセルスケジューラ部の概念的構
成を示すブロック図である。

【０１３８】

【図４】図３に示したエレメント群を構成するエレメン
トの１つの構成を示す説明図である。

【０１３９】

【図５】第１の実施形態におけるセルスケジューラ部の
基本的な装置構成を示すブロック図である。

【０１４０】

【図６】第２の実施形態のセルスケジューラ部の基本的
な装置構成を示すブロック図である。

【０１４１】

【図７】第２の実施形態のセルスケジューラ部の動作を
説明するための図である。

【０１４２】

【符号の説明】

１０１…セルスケジューラ部、１０２…セルメモリ（Ｃ
Ｍ）、１０３…フリーリスト（ＦＬ）、１０４…カレン
ダーキュー（ＣＱ）、１０５…アウトプットリスト（Ｏ
Ｌ）、１０６…ＵＢＲキュー（ＵＢＲＱ）、１０７…エ
レメント群、１０８…ＦＬ用ポインタ、１０９…ＣＱ用
ポインタ群、１１０…アウトプットリスト用ポインタ、
１１２…セレクタ、１１３…到着セル用信号線、１１４
…セル出力用信号線、１１５…セル送出予定時刻用信号
線、１１６…セル識別情報用信号線、１１７…現在時刻
用信号線、１１９…出力回線、２０２…セル識別＆送出
予定時刻算出部、２０３…セルスケジューラ部、２０４
…時計、２０５…セル。

フロントページの続き (56)参考文献 特開 平８−213992（ＪＰ，Ａ) 特開 平６−276209（ＪＰ，Ａ) 特開 平７−273773（ＪＰ，Ａ) 特開 平９−36912（ＪＰ，Ａ) 特開 平８−125669（ＪＰ，Ａ) 特開 平９−83525（ＪＰ，Ａ) 特開 平８−97832（ＪＰ，Ａ) 特開 平９−233101（ＪＰ，Ａ) 特開 平９−200218（ＪＰ，Ａ) 特開 平９−307566（ＪＰ，Ａ) 特開 平10−56492（ＪＰ，Ａ) 特開 平10−107803（ＪＰ，Ａ) 信学論 Ｖｏｌ．Ｊ72−Ｂ−▲Ｉ▼ Ｎｏ．11 ｐ1062−1069 (58)調査した分野(Int.Cl.⁷，ＤＢ名) H04L 12/56 H04L 12/28

Claims (2)

(57)【特許請求の範囲】
1. 【請求項１】 帯域規制要求に基づいてセルの出力帯域
   の規制を実行するトラヒックシェイパー装置において、 到着したセルの属するサービス種別を識別する識別手段
   と、到着したセルの属するサービス種別が出力帯域を確保す
   るタイプであるときには当該セルの到着毎に当該セルの
   送出予定時刻をセル出力帯域パラメータに基づいて算出
   する算出手段と、 この算出手段で算出された送出予定時刻単位に、出力帯
   域を確保するタイプのサービス種別の全コネクションの
   セルをキューイングするキューイング手段と、 到着したセルの属するサービス種別が出力帯域を保証す
   る必要のないタイプであるときには当該到着セルを、出
   力帯域を保証する必要のないタイプのサービス種別の全
   コネクションについて共通なバッファに格納する格納手
   段と、 セル送出時刻が更新されたときに、更新されたセル送出
   時刻又はそれより以前の時刻を送出予定時刻としたセル
   が前記キューイング手段にキューイングされているとき
   にはそのセルを送出し、更新されたセル送出時刻又はそ
   れより以前の時刻を送出予定時刻としたセルが前記キュ
   ーイング手段にキューイングされていないときには前記
   格納手段に格納されている最古のセルを送出する送出手
   段と を具備したことを特徴とするトラヒックシェイパー
   装置。
2. 【請求項２】 帯域規制要求に基づいてセルの出力帯域
   の規制を実行するトラヒックシェイパー装置において、 到着したセルの属するサービス種別を識別する識別手段
   と、 到着したセルの属するサービス種別が出力帯域を確保す
   るタイプであるときには当該セルの到着毎に当該セルの
   送出予定時刻をセル出力帯域パラメータに基づいて算出
   する第１の算出手段と、 この第１の算出手段で算出された送出予定時刻単位に、
   出力帯域を確保するタイプのサービス種別の全コネクシ
   ョンのセルをキューイングするキューイング手段と、 到着したセルの属するサービス種別が最小出力帯域のみ
   保証する必要のあるタイプであるときには当該セル到着
   毎に当該セルの最大待ち合わせ可能時刻をセル出力帯域
   パラメータに基づいて算出する第２の算出手段と、 この第２の算出手段で算出された最大待ち合わせ可能時
   刻単位に、最小出力帯域のみ保証する必要のあるタイプ
   のサービス種別の全コネクションのセルをキューイング
   する第２のキューイング手段と、 セル送出時刻が更新されたときに、更新されたセル送出
   時刻又はそれより以前の時刻を最大待ち合わせ可能時刻
   としたセルが前記第２のキューイング手段にキューイン
   グされているときにはそのセルを送出し、更新されたセ
   ル送出時刻又はそれより以前の時刻を最大待ち合わせ可
   能時刻としたセルが前記第２のキューイング手段にキュ
   ーイングされておらず、かつ、更新されたセル送出時刻
   又はそれより以前の時刻を送出予定時刻としたセルが前
   記第１のキューイング手段にキューイングされていると
   きにはそのセルを送出し、更新されたセル送出時刻又は
   それより以前の時刻を最大待ち合わせ可能時刻としたセ
   ルが前記第２のキューイング手段にキューイングされて
   おらず、かつ、更新されたセル送出時刻又はそれより以
   前の時刻を送出予定時刻としたセルが前記第１のキュー
   イング手段にキューイングされていないときには前記第
   ２のキューイング手段に格納されている最古のセルを送
   出する送出手段と を具備したことを特徴とするトラヒッ
   クシェイパー装置。