(57)【特許請求の範囲】
【請求項１】
伝送路へのセルの送出間隔を制御するためのシェーピング方法であって、
入力セルをバッファメモリに一時的に蓄積しておき、上記入力セルが属するグループの識別子と対応して予め申告されているトラヒック条件と、上記入力セルが属するサブグループの識別子と対応して予め申告されているトラヒック条件との両方の条件に応じて、該入力セルの送出時刻を決定する第１ステップと、
上記セルの送出時刻を先着セルに割り当て済の送出時刻と比較し、もし、送出時刻が重なった場合は上記第１ステップで決定した送出時刻を修正した後、上記送出時刻と上記入力セルの識別情報との対応関係を記憶しておく第２ステップと、  上記第２ステップで記憶されたセル識別子と送出時刻の対応関係に基づいて、上記バッファメモリに蓄積されたセルを送出時刻順に読み出し、出力回線に送出する第３ステップと
からなることを特徴とするシェーピング方法。
【請求項２】
前記グループ識別子およびサブグループ識別子と対応するトラヒック条件が、それぞれ出力回線におけるピークセル間隔として記憶されていることを特徴とする請求項１に記載のシェーピング方法。
【請求項３】
前記送出時刻が、出力回線における１セル転送時間を単位として時系列的に定義されたタイムスロットを示すことを特徴とする請求項１または請求項２に記載のシェーピング方法。
【請求項４】
前記グループの識別子が仮想パスの識別子であり、前記サブグループの識別子が上記仮想パス上に多重化された仮想チャネルの識別子であることを特徴とする請求項１記載〜請求項３の何れかに記載のシェーピング方法。
【請求項５】
伝送路へのセルの送出間隔を各セルが属するグループおよびサブグループ対応に制御するためのシェーピング方法であって、
出力インタフェース速度で決まる１セル転送時間を１単位として、各グループ毎に申告ピーク速度に対応した第１のピークセル間隔を設定し、上記第１のピークセル間隔を１単位として、サブグループ毎の申告トラヒック速度に対応したパラメータを記憶しておき、
セル到着時に、各セルの属するサブグループ対応のパラメータに基づいて、当該セルと対応する上記第１ピークセル間隔を１単位として相対セル送出時刻を求め、上記相対セル送出時刻から上記出力インタフェース速度で決まる１セル転送時間を１単位としたセル送出時刻を決定し、
各セルを上記セル送出時刻に従って送出するようにしたことを特徴とするシェーピング方法。
【請求項６】
前記パラメータが、前記サブグループ対応の申告ピーク速度に対応した第２のピークセル間隔を含み、
セル到着時に、各セルの属するグループの前記第１のピークセル間隔を１単位としてセル到着時刻を求め、
上記セル到着時刻と、該セルの属するサブグループにおける直前のセルの送出時刻と前記第２のピークセル間隔とに基づいて、前記相対セル送出時刻を決定することを特徴とする請求項５に記載のシェーピング方法。
【請求項７】
前記相対セル送出時刻が、同一グループ内の他のサブグループに属するセルの相対セル送出時刻と競合した場合、当該セルの上記相対セル送出時刻以降に存在する空き状態の相対セル送出時刻を求めることを特徴とする請求項５または請求項６に記載のシェーピング方法。
【請求項８】
前記相対セル送出時刻が、同一グループ内の他のサブグループに属するセルの相対セル送出時刻と競合した場合、当該セルの上記相対セル送出時刻以降に存在する当該グループ内で他セルと競合しない新たな相対セル送出時刻を求め、
上記新たな相対セル送出時刻に対して求めたセル送出時刻が他のグループに属するセルの送出時刻と競合した場合、上記セル送出時刻以降に存在する他の空きセル送出時刻を求めることを特徴とする請求項５または請求項６に記載のシェーピング方法。
【請求項９】
時刻と対応した複数のビット位置からなる第１ビットマップによって前記グループ毎に相対セル送出時刻の空き状態を記憶しておき、時刻と対応した複数のビット位置からなる第２ビットマップでセル送出時刻の空き状態を記憶しておき、相対セル送出時刻が競合した場合、そのセルが属したグループ対応の第１ビットマップを参照して、上記相対セル送出時刻に対応するビット位置以降に存在する空き状態のビットを検索し、該ビットに対応する時刻を相対セル送出時刻として求め、
セル送出時刻が競合した場合、上記第２ビットマップを参照して上記セル送出時刻に対応するビット位置以降に存在する空き状態のビットを検索し、該ビットに対応する時刻をセル送出時刻として求めることを特徴とする請求項５〜請求項８の何れかに記載のシェーピング方法。
【請求項１０】
前記第１ビットマップまたは第２ビットマップに対応したレジスタを備え、各ビットマップ内の複数ビットを１ブロックとして、各ブロックの状態を上記レジスタで記憶しておき、
上記レジスタを参照して、第１ビットマップまたは第２ビットマップにおける参照範囲を特定するようにしたことを特徴とする請求項９に記載のシェーピング方法。
【請求項１１】
前記第１ビットマップまたは第２ビットマップの所定のブロック内で空き時刻を検索し、該ブロック内に空き時刻が存在しなかった場合に前記レジスタを参照して、第１ビットマップまたは第２ビットマップにおける次の参照範囲を特定するようにしたことを特徴とする請求項１０に記載のシェーピング方法。
【請求項１２】
前記グループが仮想パス、前記サブグループが仮想パス上に多重化された仮想チャネルであることを特徴とする請求項５〜請求項１１の何れかに記載のシェーピング方法。
【請求項１３】
出力線へのＡＴＭセルの送出を各セルが属するグループおよびサブグループ対応に制御するためのシェーピング機能を備えたＡＴＭインターフェイスであって、  入力線から入力された複数のＡＴＭセルを一時的に蓄積するためのバッファメモリと、
上記バッファメモリへのセルの書き込みと、該バッファメモリから上記出力線へのセルの読み出しを行うための制御手段と
を備え、上記制御手段が、
上記出力線におけるセル速度で決まる１セル転送時間を１単位として、各グループ毎に申告ピーク速度に対応して求められた第１のピークセル間隔と、上記第１のピークセル間隔を１単位として、サブグループ毎の申告トラヒック速度に対応して求められた制御パラメータとを記憶するためのテーブル手段と、
上記入力線からセルが到着した時、上記テーブル手段に記憶された当該セルの属するサブグループ対応の制御パラメータに基づいて、当該セルと対応する上記第１ピークセル間隔を１単位として相対セル送出時刻を求め、上記相対セル送出時刻から上記出力線のインタフェース速度で決まる１セル転送時間を１単位としたセル送出時刻を決定し、上記バッファメモリに蓄積された各セルを上記セル送出時刻に従って上記出力線に読み出すためのアクセス手段と
を有することを特徴とするＡＴＭインターフェイス。
【請求項１４】
前記相対セル送出時刻とセル送出時刻が、前記出力線の帯域によって決まるタイムスロットの１つを指定することを特徴とする請求項１３に記載のＡＴＭインターフェイス。
【請求項１５】
前記制御手段が、前記出力線上のタイムスロットと対応させて、前記バッファメモリから読み出すべきセルを指定する情報を記憶するためのメモリ手段を有し、  前記アクセス手段が、上記メモリ手段を参照して、前記バッファメモリから各タイムスロットに対応したセルを読み出すことを特徴とする請求項１４に記載のＡＴＭインターフェイス。
【請求項１６】
前記制御手段が、前記グループ毎に相対セル送出時刻の空き状態を記憶するための前記タイムスロットと対応した複数のビット位置からなる第１ビットマップと、前記セル送出時刻の空き状態を記憶するための前記タイムスロットと対応した複数のビット位置からなる第２ビットマップとを有し、
相対セル送出時刻が競合した場合、そのセルが属したグループ対応の第１ビットマップを参照して、上記相対セル送出時刻に対応するビット位置以降に存在する空き状態のビットを検索し、該ビットに対応する時刻を相対セル送出時刻として求め、セル送出時刻が競合した場合、上記第２ビットマップを参照して上記セル送出時刻に対応するビット位置以降に存在する空き状態のビットを検索し、該ビットに対応する時刻をセル送出時刻として求めることを特徴とする請求項１３〜請求項１５の何れかに記載のＡＴＭインターフェイス。
【請求項１７】
前記制御手段が、前記第１ビットマップまたは第２ビットマップ内の複数ビットを１ブロックとして、各ブロックの状態を記憶するためのレジスタ手段を備え、  上記レジスタ手段を参照して、前記第１ビットマップまたは第２ビットマップにおける参照範囲を特定するようにしたことを特徴とする請求項１６に記載のＡＴＭインターフェイス。
【請求項１８】
出力線へのＡＴＭセルの送出間隔を制御するためのシェーピング機能を備えたＡＴＭインターフェイスであって、
入力線から入力された複数のＡＴＭセルを一時的に蓄積するためのバッファメモリと、
上記バッファメモリへのセルの書き込みと、該バッファメモリから上記出力線へのセルの読み出しを行うための制御手段と
を備え、上記制御手段が、
入力セルの属するグループ別およびサブグループ別に予め申告されたトラヒック条件に対応して求められた制御パラメータを記憶するための第１のテーブル手段と、
上記出力線上でのタイムスロット対応に空き状態を記憶するための第２のテーブル手段と、
上記入力線からセルが到着した時、上記第１のテーブル手段に記憶された当該セルの属するグループおよびサブグループ対応の制御パラメータに基づいて、当該セルの送出タイミングを求め、上記第２のテーブル手段を参照して、上記送出タイミングと対応させるべき空き状態の送出タイムスロットを決定し、上記バッファメモリに蓄積された該当セルを上記送出タイムスロットのタイミングで上記出力線に読み出すためのアクセス手段と
を有することを特徴とするＡＴＭインターフェイス。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、非同期転送モード（ＡＴＭ：Ａｓｙｎｃｈｒｏｎｏｕｓ  Ｔｒａｎｓｆｅｒ  Ｍｏｄｅ）網のためのインタフェース装置およびトラヒック制御方法に関し、特に、申告トラヒックに従ってセルを送出制御するためのシェーピング技術に関するものである。
【０００２】
【従来の技術】
ＡＴＭ交換方式のネットワークでは、セルと呼ばれる固定長パケットを用いることによって、複数のコネクションでネットワークリソースを共有し、高速かつ効率的な伝送を可能としている。セルは、例えば、５バイトのヘッダ部と４８バイトの情報部とからなる５３バイト長で構成され、上記ヘッダ部には、仮想パス（以下、ＶＰという）の識別子ＶＰＩと、上記ＶＰに多重化される仮想チャネル（以下、ＶＣという）の識別子ＶＣＩとを含む。
【０００３】
ＡＴＭ網のトラヒック制御に関しては、例えばＩＴＵ−Ｔ、Ｄｒａｆｔ  Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ  Ｉ．３７３において、発呼時に、呼設定すべきトラヒックについて、ユーザ（発信元装置）から通信速度や通信品質などのトラヒックパラメータを申告させ、この申告パラメータに基づいて各コネクション毎にリソースを割り付ける「コネクション受付制御」と、通信品質を保証するために入力セルの状態を監視しておき、申告トラヒックに違反して送出されたセルについては、マーキングやセル廃棄等の対策をとる「使用量パラメータ制御（以下、ＵＰＣという）」について記載されている。
【０００４】
ユーザ端末やユーザ網インタフェース装置（以下、ＵＮＩという）が備えるＡＴＭインタフェースでは、上述したＵＰＣによるセル廃棄を避けるために、トラヒック制御機能として、申告トラヒックに違反しないようにセルをＡＴＭ網に出力するための「シェーピング機能」が必要となる。
上記文献には、ＵＰＣに適用可能なシェーピング制御アルゴリズムとして、リーキーバケットアルゴリズムと、バーチャルスケジューリングアルゴリズムが挙げられている。
トラヒック制御に関する他の従来技術として、例えば、特開平５−１３０１３６号公報には、図１２に示す装置構成によってＵＰＣとシェーピングを行なうようにした「伝送ビットレートの監視方法」が提案されている。
【０００５】
ここで、シェーピング機能にのみに着目して説明すると、図１２の構成では、ユーザ装置から送出され、例えばＡＴＭ多重化装置を経由したセルが装置５００に到来すると、ヘッダ識別部５０１が、入力セルのＶＣＩを識別してこれを時刻計算部５０２に通知すると共に、上記入力セルをメモリ装置５０３に渡す。時刻計算部５０２は、ＶＣＩ毎に予め申告されたトラヒックを守るように、リーキーバケットアルゴリズムを用いて、上記メモリ装置内におけるセルの待ち時間Ｄを計算する。メモリ装置５０３に蓄積された入力セルは、それぞれの待ち時間Ｄが経過した時点、上記時刻計算部５０２からの指示に応答してメモリ装置から読み出され、出力線ｒに送出される。
【０００６】
【発明が解決しようとする課題】
然るに、ＡＴＭ網を構成している各交換機は、ＶＰ単位で帯域管理を行なっているため、各ユーザが公衆ＡＴＭ網を利用する場合には、ＶＣＩ対応のトラヒックのみならず、ＶＰＩ対応のトラヒックも申告しておく必要がある。
しかしながら、従来のシェーピング制御では、ＶＣＩ毎に申告トラヒックに従ったセル出力制御を行っているため、例えば、出力インタフェース速度に比べてＶＰＩ対応の申告ピークレートが遅い場合、ＶＣＩに関して申告トラヒックが守られていても、ＶＰＩ毎に観測するとセル送出間隔が申告ピークレートより速くなり、結果的に申告トラヒックに違反する場合がある。
【０００７】
図１３は、従来のシェーピング制御によるセルの送出間隔の１例を示す。
図において、「ＴＡ」はＶＰＩ＝「Ａ」をもつ仮想パスにおける申告ピーク間隔、Ｔ（ａ）とＴ（ｂ）は、それぞれ上記仮想パス上に形成されたＶＣＩ＝「ａ」およびＶＣＩ＝「ｂ」をもつ仮想チャネルの申告ピーク間隔を示す。また、６０１と６０２は、ＶＣＩ＝「ａ」の仮想チャネルに属したセル、６１１と６１２はＶＣＩ＝「ｂ」の仮想チャネルに属したセルを示す。
図示した例では、セル６０１と６０２と間の送出間隔、およびセル６１１と６１２の送出間隔は、それぞれの申告値Ｔ（ａ）、Ｔ（ｂ）を満たしている。しかしながら、仮想パスを単位として、ＶＰＩ＝「Ａ」をもつセルの間隔を観測すると、セル６０２と６１２の送出間隔は、申告ピーク間隔ＴＡに違反している。
【０００８】
本発明の目的は、一つの仮想パス上に複数の仮想チャネルが形成されるＡＴＭネットワークにおける改良されたシェーピング方法およびＡＴＭインターフェイスを提供することにある。
本発明の他の目的は、ＶＰＩとＶＣＩの両方で申告トラヒックを満足できるシェーピング方法およびＡＴＭインターフェイスを提供することにある。
本発明の更に他の目的は、１つの物理的な回線上に複数のＶＰが多重化されるネットワークに適用されるＡＴＭインターフェイス装置、あるいはＶＰＩ対応の申告ピークレートが出力回線速度に比べて遅いような入力セルを扱うＡＴＭインターフェイス装置において、ＶＰＩ／ＶＣＩ毎の申告トラヒックとＶＰＩの申告ピークレートとに応じてセル送出間隔を制御できるシェーピング方法および制御装置を提供することにある。
【０００９】
【課題を解決するための手段】
上記目的を達成するために、本発明による伝送路へのセルの送出間隔を制御するためのシェーピング方法は、入力セルをバッファメモリに一時的に蓄積しておき、上記入力セルが属するグループの識別子と対応して予め申告されているトラヒック条件と、上記入力セルが属するサブグループの識別子と対応して予め申告されているトラヒック条件との両方の条件に応じて、該入力セルの送出時刻を決定する第１ステップと、上記セルの送出時刻を先着セルに割り当て済の送出時刻と比較し、もし、送出時刻が重なった場合は上記第１ステップで決定した送出時刻を修正した後、上記送出時刻と上記入力セルの識別情報との対応関係を記憶しておく第２ステップと、上記第２ステップで記憶されたセル識別子と送出時刻の対応関係に基づいて、上記バッファメモリに蓄積されたセルを送出時刻順に読み出し、出力回線に送出する第３ステップとからなることを特徴とする。
【００１０】
また、本発明によるＡＴＭインターフェイスは、入力線から入力された複数のＡＴＭセルを一時的に蓄積するためのバッファメモリと、上記バッファメモリへのセルの書き込みと、該バッファメモリから上記出力線へのセルの読み出しを行うための制御手段とを備え、上記制御手段が、
入力セルの属するグループ別およびサブグループ別に予め申告されたトラヒック条件に対応して求められた制御パラメータを記憶するための第１のテーブル手段と、上記出力線上でのタイムスロット対応に空き状態を記憶するための第２のテーブル手段と、上記入力線からセルが到着した時、上記第１のテーブル手段に記憶された当該セルの属するグループおよびサブグループ対応の制御パラメータに基づいて、当該セルの送出タイミングを求め、上記第２のテーブル手段を参照して、上記送出タイミングと対応させるべき空き状態の送出タイムスロットを決定し、上記バッファメモリに蓄積された該当セルを上記送出タイムスロットのタイミングで上記出力線に読み出すためのアクセス手段とを有することを特徴とする。
更に具体的に言うと、上記グループには、例えば、伝送路上に多重化して形成される仮想パス（ＶＰ）が該当し、上記サブグループには、各仮想パス上に多重化して形成される仮想チャネル（ＶＣ）が該当する。また、上記第１のテーブル手段に記憶する制御パラメータは、例えば、各グループ（仮想パス識別子：ＶＰＩ）毎に申告ピークレートと対応したピークセル間隔、および、各サブグループ（仮想チャネル識別子：ＶＣＩ）毎に申告トラヒックに対応したピークセル間隔である。
【００１１】
本発明の好ましい実施例では、出力インタフェース速度で１セル転送するのにかかる時間を１単位としてセル到着時刻およびセル送出タイムスロットを管理する。この場合、上記第１のテーブル手段には、上記各グループ（仮想パス識別子：ＶＰＩ）毎のピークセル間隔が、上記出力インタフェース速度での１セル転送時間を１単位とする値で記憶され、各サブグループ（仮想チャネル識別子：ＶＣＩ）毎のピークセル間隔が、該当グループ（ＶＰＩ）のピークセル間隔を１単位とする値で記憶される。また、セル到着時には、サブグループ（ＶＣＩ）毎の制御パラメータに従って、上記ＶＰＩのピークセル間隔を１単位として相対的なセル送出時刻が算出され、第２のテーブル手段を参照して、空き状態のタイムスロットの中から、上記相対セル送出時刻と対応させるべきセル送出タイムスロットが選択される。
【００１２】
上記構成によれば、第２のテーブル手段に他のセルによるタイムスロットの使用状態（空き状態）が記憶してあるため、相対セル送出時刻が、仮に同一グループ内の他のサブグループに属するセルあるいは他のグループに属したセルの相対セル送出時刻（タイムスロット）と競合していた場合、時刻を後にずらして他のセルと競合しない新たな相対セル送出時刻に変更することができる。
上記第２のテーブルは、例えば、グループ毎に相対セル送出時刻の空き状態を記憶するために利用する時刻（タイムスロット）対応の複数のビット位置からなる第１ビットマップと、全グループに共通してタイムスロット空き状態を記憶するために利用する複数のビット位置からなる第２ビットマップとに分けて構成してもよい。
【００１３】
【作用】
本発明によれば、ＶＰＩ毎のピークセル間隔を守った形で各ＶＣＩ毎の申告パラメータに従ったセル送出時刻（タイムスロット）を決定でき、制御パラメータから求めた送出時刻が他のセルの送出時刻と競合時した場合でも、空き状態の時刻（タイムスロット）の中からＶＰＩ毎の申告されたピークセル間隔に違反しない範囲で送出タイミングを決定できるため、この送出タイミングでバッファメモリからのセルの読み出しを行うことによって、ＶＰＩ毎、ＶＣＩ毎のシェーピングを実現できる。
【００１４】
【実施例】
図２の（ａ）、（ｂ）は、本発明によるＡＴＭインタフェース１ａ〜１ｃを適用した通信システムの構成の１例を示す。
図２において、（ａ）は、ＡＴＭインタフェース１ａ〜１ｂが、構内ＡＴＭ交換機２と広域ＡＴＭ網との間に適用された例である。
ＡＴＭインターフェイス１ａは、ＡＴＭ交換機２の１つの出力回線４ａと広域ＡＴＭ網の１つの入力線（加入者線）５ａとの間に接続され、出力回線４ａが広域ＡＴＭ網入力線５ａのインタフェース速度ｒ’と同等、もしくはそれ以上のインタフェース速度ｒを有し、ＡＴＭインタフェース１ａは、ＡＴＭ交換機２から出力回線４ａに出力された同一ＶＰに属したセルを入力線５ａに中継する。
【００１５】
ＡＴＭインタフェース１ｂは、ＡＴＭ交換機２の１つの出力回線４ｂと広域ＡＴＭ網の複数の入力線５ｂ−１〜５ｂ−Ｎとの間に接続され、ＡＴＭ交換機２から出力回線４ｂに多重化して出力されたＶＰの異なる複数セルを受取り、これらをＶＰ対応の入力線５ｂ−１〜５ｂ−Ｎに分配動作する。
図２の（ｂ）は、ＡＴＭインタフェース１ｃが、ユーザ構内のＡＴＭ多重化装置３と広域ＡＴＭ網との間に接続された例を示す。ＡＴＭインタフェース１ｃは、多重化装置３から出力回線４ｃに多重化して出力されたＶＰの異なる複数のセルを受信し、広域ＡＴＭ網への入力線５ｃに中継する。この場合、出力回線４ｃと広域ＡＴＭ網の入力線５ｃは同一のインタフェース速度をもつ。
【００１６】
図３は、同一ＶＰのセルをシェーピングするＡＴＭインタフェース１ａの機能ブロックを示す。
図３の（ａ）は、回線４ａからインタフェース速度ｒで受信された入力セルを、ＦＩＦＯ等のバッファメモリを用いた速度変換手段１１ａによって出力側インターフェイス速度ｒ’に変換した後、ＶＰＩ毎の申告トラヒックに従うＶＰシェーピング機能とＶＣＩ毎の申告トラヒックに従うＶＣシェーピング機能とを備えたシェーピング手段１０ａによってシェーピングし、回線５ａに出力するようにした構成を示す。
図３の（ｂ）は、速度変換用のバッファと、ＶＰシェーピングおよびＶＣシェーピングに用いるバッファとを共用し、速度変換機能を備えたシェーピング回路１０ｂによって回線４ａからの受信セルを処理するようにした構成を示す。
【００１７】
図４は、入力セルをＶＰ対応の複数の回線に分離するＡＴＭインタフェース１ｂの機能ブロックを示す。
図４の（ａ）は、回線４ｂから受信したインタフェース速度ｒの入力セルを分離回路（セレクタ）１２ａでＶＰＩ別に振り分け、ＶＰＩ対応に設けた速度変換手段１１ｂ−１〜１１ｂ−Ｎによって速度ｒ’１〜ｒ’Ｎのセル流に変換した後、シェーピング回路１０ｃ−１〜１０ｃ−Ｎによって、ＶＣシェーピングとＶＰシェーピングとを同時に行ない、シェーピングされたセルを回線５ｂ−１〜５ｂ−Ｎに出力するようにした構成を示す。
図４の（ｂ）は、分離回路１２ｂでＶＰＩ別に振り分けられたセルを、ＶＰＩ対応に設けられた速度変換機能を備えるシェーピング回路１０ｄ−１〜１０ｄ−Ｎに入力し、速度変換と同時に、ＶＰシェーピングとＶＣシェーピングを行った後、ＶＰＩ対応の回線５ｂ−１〜５ｂ−Ｎに出力するようにした構成を示す。
図４の（ｃ）は、回線４ｂからの入力セルをシェーピング回路１０ｅによって、ＶＰシェーピングとＶＣシェーピングした後に、分離回路１２ｃでＶＰＩ対応の回線５ｂ−１〜５ｂ−Ｎに振り分けるようにした構成を示す。
【００１８】
図５は、回線４ｃから多重化して入力された複数ＶＰの入力セルを回線５ｃに多重化して出力するＡＴＭインタフェース１ｃの機能ブロックを示す。この場合、回線４ｃから受信したセルは、シェーピング回路１０ｆによって、ＶＰシェーピングとＶＣシェーピングを施された後、入力回線４ｃと同一のインターフェイス速度ｒで回線５ｃに出力される。
【００１９】
次に、シェーピング回路１０の構成について説明する。ここでは、異なる複数ＶＰの入力セルを扱うシェーピング回路１０ｅ、１０ｆの構成について説明するが、同一ＶＰの入力セルを扱うシェーピング回路１０ｂ、１０ｄ、および速度変換用のバッファを別に備えるシェーピング回路１０ａ、１０ｃの構成は、以下に説明する回路構成から容易に得られるため、説明を省略する。
【００２０】
図１は、シェーピング手段１０の構成の１例を示すブロック図である。
シェーピング回路１０は、入力セルを一時的に蓄積するためのセルバッファ２０と、入力セルのヘッダに含まれるＶＰＩ／ＶＣＩを識別するためのヘッダ識別部３０と、入力セルの送出時刻（送出タイムスロット）を算出するための送出時刻計算部４０と、上記送出時刻計算部４０で算出された送出時刻に対応する空き時刻（空きタイムスロット）を検索するための空き時刻検索部５０と、セルバッファ２０へのセルの書き込み、および読み出しを制御するためのバッファ制御部６０と、コネクション別の申告トラヒックやセル送出時刻等の各種パラメータを記憶するためのパラメータテーブル７０と、送出時刻の状態（空き／塞がり状態）を示す状態情報を記憶するための検索テーブル８０と、セルバッファ６０から読み出すべきセルのバッファの番号（バッファアドレス）を記憶するためのセル出力リスト９０とから構成される。
【００２１】
回線４からインタフェース速度ｒで入力されたセルは、セルバッファ２０に順次に書き込まれ、送出時刻が来る迄、一時的に蓄積される。この時、ヘッダ識別部３０によって、受信セルのヘッダに含まれるＶＰＩ／ＶＣＩが識別され、識別されたＶＰＩ／ＶＣＩがバス５を介して送出時刻計算部４０に通知される。
送出時刻計算部４０は、予めパラメータテーブル７０に記憶してあるパラメータを使って、ＶＰＩ別、ＶＣＩ別の申告トラヒックにセル流となるように、上記入力の送出時刻を計算し、計算結果（送出時刻）をバス６を介して空き時刻検索部５０に通知する。
空き時刻検索部５０は、検索テーブル７０を参照して、上記送出時刻計算部４０から通知された送出時刻またはそれ以降の時間帯でのセル送出が可能な空き時刻（タイムスロット）を検索し、検出された空き時刻をバス７を介してバッファ制御部６０に通知する。
【００２２】
バッファ制御部６０は、セル出力リスト９０中の上記空き時刻（タイムスロット）に対応したエントリに、上記空き時刻で送出すべきセルの識別情報（例えば、上記セルの蓄積一を示すバッファアドレスまたはセルバッファ番号）を登録する。上記バッファ制御部６０は、インタフェース速度ｒ’をもつ出力回線５上の各タイムスロットで、セル出力リスト９０からそのタイムスロットと対応するセル識別情報を読み出し、該セル識別情報に基づいて、セルバッファ２０からセルを読み出し、回線５に出力する。
【００２３】
図６は、送出時刻計算部４０が参照するパラメータテーブル７０の内容の１例を示す。
パラメータテーブル７０は、ＶＰＩ対応に、インタフェース速度ｒ’を基準にして表されたピークセル間隔Ｔを記憶するための第１のパラメータテーブル７１と、ＶＰＩ／ＶＣＩ対応に、各ＶＰＩのピークレートを基準にして表されたピークセル間隔Ｔ’と、理想的な送出時刻ｔｎ’を記憶するための第２のパラメータテーブル７２とからなる。
ここでは、セルの到着時刻をインタフェース速度ｒ’における１セルの転送時間を１単位として表し、１例として、ＶＰＩ＝「１」、「Ａ」、「Ｎ」の申告トラヒック（ピークレート）がそれぞれ「ｒ’１」、「ｒ’Ａ」、「ｒ’Ｎ」であり、ＶＰＩ／ＶＣＩ＝（１）、（ａ）、（Ｎ）の申告トラヒック（ピークレート）がそれぞれ「Ｐ（１）」、「Ｐ（ａ）」、「Ｐ（ｍ）」の場合のピークセル間隔を示している。なお、シェーピング回路１０に供給される入力セルが全て同一のＶＰＩをもつ場合は、上記第１パラメータテーブル７１に代えて、１つのピークセル間隔を記憶するレジスタを適用できる。
【００２４】
図７は、上記パラメータテーブル７０を参照して行なわれる送出時刻の計算手順を示すフローチャートである。
ここで、セルの到着時刻をタイマが示す現在時刻ｔａとし、ヘッダ識別部３０から通知されるＶＰＩの値を「Ａ」、ＶＰＩ／ＶＣＩの値を「（ａ）」とすると、送出時刻計算部４０は、バス５を介してヘッダ識別部３０からＶＰＩ、ＶＣＩを受け取ると（ステップ１０１）、上記ＶＰＩの値「Ａ」をアドレスとして第１パラメータテーブル７１をアクセスし、ＶＰＩに対応するピークセル間隔「ＴＡ」を読み取り、到着時刻ｔａをピークレートにおけるセル送出タイミングを単位とした値に変換するために、上記到着時刻ｔａをＴＡで割り、これを制御用の到着時刻「ｔａ’Ａ」とする（ステップ１０２）。
【００２５】
次に、ＶＰＩ／ＶＣＩ（＝（ａ））をアドレスとして第２パラメータテーブル７２をアクセスし、上記ＶＰＩ／ＶＣＩと対応する理想送出時刻「ｔｎ’（ａ）」を読み取って、上記「ｔａ’Ａ」と比較する（ステップ１０３）。理想送出時刻「ｔｎ’（ａ）」が到着時刻「ｔａ’Ａ」より早い場合（ｔｎ’（ａ）＜ｔａ’Ａ）は、理想送出時刻ｔｎ’（ａ）＝ｔａ’Ａとし、ｔａ’Ａの小数部を切り上げた値を送出時刻ｔｏ’Ａに設定する（ステップ１０４）。もし、ｔｎ’（ａ）≧ｔａ’Ａの場合は、理想送出時刻ｔｎ’（ａ）の小数部を切り上げた値を送出時刻ｔｏ’Ａに設定する（ステップ１０５）。送出時刻ｔｏ’Ａの値が決まると、送出時刻ｔｏ’Ａをバス６を介して空き時刻検索部５０に通知し（ステップ１０６）、第２パラメータテーブル７２に記憶してある理想送出時刻の値をｔｎ’（ａ）＝ｔｎ’（ａ）＋Ｔ’（ａ）に更新する（１０７）。
【００２６】
図８は、上述した送出時刻計算に基づく本発明によるシェーピング動作の１例を示す。
ここで、ＶＰＩ（＝Ａ）のピークセル間隔ＴＡを「３」、このＶＰＩに属するＶＰＩ／ＶＣＩ＝（ａ）とＶＰＩ／ＶＣＩ＝（ｂ）のピークセル間隔の値をそれぞれＴ’（ａ）＝４、Ｔ’（ｂ）＝３、理想送出時刻ｔｎ（ａ）の初期値１３１を「０」、ｔｎ（ｂ）の初期値２３１を「０」と仮定する。
【００２７】
ＶＰＩ／ＶＣＩ＝（ａ）のセル１１１、１１２および１１３の到着時刻ｔａを、それぞれ「０」、「１７」、「２４」とすると、最初の入力セル１１１の制御用の到着時刻ｔａ’Ａの値は、１２１に示すように「０」であるから、送出時刻ｔｏ’Ａの値は、３０１に示すように「０」となり、次セルの理想送出時刻ｔｎ’（ａ）の値は、１３２に示すように、更新されて「４」になる。
次の入力セル１１２は、制御用の到着時刻ｔａ’Ａの値が、１２２に示すように「１７／３」となる。これは理想送出時刻ｔｎ’（ａ）＝「４」より大きいため、送出時刻ｔｏ’Ａの値は、３０２に示すように「６」となり、次セルの理想送出時刻ｔｎ’（ａ）の値は、１３３に示すように「２９／３」に更新される。
また、セル１１３は、制御用の到着時刻ｔａ’Ａの値が、１２３に示すように「８」となり、１３３で示した理想送出時刻より早くセルが到着したことになる。このため、送出時刻ｔｏ’Ａの値は、３０３に示すように「１０」となり、次セルの理想送出時刻ｔｎ’（ａ）の値は、１３４に示すように「４１／３」となる。
【００２８】
一方、ＶＰＩ／ＶＣＩ＝（ｂ）のセル２１１、２１２の到着時刻ｔａをそれぞれ「１」、「９」とすると、セル２１１は、制御用の到着時刻ｔａ’Ａの値が、２２１に示すように「１／３」であるから、送出時刻ｔｏ’Ａの値は、３１１に示すように「１」となり、次セルの理想送出時刻ｔｎ’（ｂ）の値は、２３２に示すように「１０／３」に更新される。また、次のセル２１２は、制御用の到着時刻ｔａ’Ａの値が、２２２に示すように「３」であり、２３２に示した理想送出時刻の値「１０／３」より早いため、送出時刻ｔｏ’Ａの値は、３１２に示すように「４」となる。
上述した送出時刻の値ｔｏ’Ａから、本実施例によれば、コネクション毎のピークセル間隔のみならず、ＶＰＩ対応のピークセル間隔も申告されたコネクションの条件を満足することがわかる。
【００２９】
図９は、空き時刻検索部５０と検索テーブル８０の構成の１例を示す。
８１は、ＶＰＩ対応の複数のテーブル領域８１−１〜８１−Ｎから構成されるＶＰＩ別検索テーブルであり、各テーブル領域は、セル送出時刻（送信タイムスロット）と対応した複数のビット領域からなり、そのＶＰＩにとって各送出時刻が空き状態か塞がり状態かを示すフラグビットを記憶するようになっている。
【００３０】
８２は、セル送出時刻と対応する複数のビット領域からなる全コネクション検索テーブルであり、コネクション全体で見た場合の各送出時刻の空き／塞がり状況をフラグビットで記憶するようになっている。これらの検索テーブルでは、例えば、送出時刻＝ｉのタイムスロットで送出すべきセルがあれば、テーブルのｉビット目に「１」がセットされる。
【００３１】
空き時刻検索部５０では、送出時刻計算部４０からバス６ａ、６ｂを介して送出時刻の値ｔｏ’Ａとピークセル間隔の値ＴＡを受け取ると、第１検索部５１によってＶＰＩ別検索テーブル８１内のテーブル領域８１−Ａをアクセスし、送信時刻ｔｏ’Ａ以降に位置するタイムスロットの中から、フラグビットが「０」状態にある空き時刻ｔｇｏ’Ａを検索して、これを計算部５２に渡す。計算部５２は、上記時刻ｔｇｏ’Ａから送出タイムスロットを基準にした送出時刻ｔｏ（＝ｔｇｏ’Ａ×ＴＡ）を計算し、これを第２の検索部５３に渡す。第２の検索部５３は、上記送出時刻ｔｏに基づいて全コネクション検索テーブル８２にアクセスし、時刻ｔｏ以降のタイムスロットの中で空き状態にある送信時刻ｔｇｏを検索し、これをバス７を介してバッファ制御部６０に通知する。
【００３２】
尚、上記テーブル領域８１、８２における空き状態を示すフラグビットの検索において、テーブルの先頭から順番に１ビットずつチェックする方式にすると、塞がりビットが多い場合に検索に時間がかかるため、数ビット分をまとめてフラグ情報を読み出し、プライオリティエンコーダ等を用いて一括検索すると良い。メモリアクセス回数を更に削減するためには、例えば、数ビット分のテーブル領域の空き塞がり状態を１ビットで表すブロック別状態表示レジスタを設ければ良い。例えば、メモリ８２のｊビット分を１ブロックにし、送出時刻ｉからｉ＋ｊまでの全てのタイムスロットが塞がっている場合、レジスタ５４のｉ／ｊ番目に「１」をセットしておく。
【００３３】
図１０は、ブロック別状態表示レジスタ５４を適用した空き時刻検索動作の１例を示す。
送出時刻の値がｔｏ’Ａ＝「６」、ＶＰＩ対応のピークセル間隔の値がＴＡ＝「４」の場合、メモリ８１−Ａの６ビット目以降を検索し、「０」がセットされている最初のビット位置ｉを実送出時刻ｔｇｏ’Ａとする（矢印４０１）。この時、メモリ８１−Ａのｉビット目を「１」に変更する。このようにして見つけたｔｇｏ’Ａの値が、例えばｉ＝「７」であったと仮定すると、計算部５２では、上記値「７」にＴＡ＝「４」を掛け、ｔｏ＝「２８」を算出する。
次に、メモリ８２の２８ビット目以降を検索する（矢印４０２）。レジスタ５４が、メモリ８２の１０ビット分を１ブロックとして、各ブロック毎の状態を記憶している場合、もし、メモリ８２の２９ビットまでの間に「０」状態のビットが見つからなければ、レジスタ５４の３０／１０＝３番目以降を検索する（矢印４０３）。図示した例では、レジスタ５４の５番目のビットが「０」状態となているため、メモリ８２の（５−１）×１０＝４０ビット番目以降を検索し（矢印４０４）、最初の空きビット位置ｉ（この例では「４１」）をｔｇｏの値とし、メモリ８２のｉビット目に塞がり状態を示すフラグ「１」を設定する。
【００３４】
なお、空き時刻検索によって生じるＣＤＶ（Ｃｅｌｌ  Ｄｅｌａｙ  Ｖａｒｉａｔｉｏｎ）に対しても厳密にシェーピングを行ないたい場合には、実送出時刻ｔｇｏをＶＰＩのピークセル間隔ＴＡで割った値を第２パラメータテーブルの理想送出時刻ｔｎ１’（ａ）に設定し、第１検索テーブル８１内にあるテーブル領域８１−Ａにおいて、上記値の小数部を切り上げた値と対応したビット位置でフラグを「１」に更新すればよい。
【００３５】
図１１は、セルバッファ２０とバッファ制御部６０とセル出力リスト９０の構成の１例を示す。
セルバッファ２０は、セル単位の複数のバッファ領域から構成され、書き込み動作はシーケンシャルに行われ、読み出し動作はランダムに行われる。バッファ制御部６０は、上記セルバッファ２０の書き込みアドレスを生成する書き込み制御部６１と、セル出力リスト９０にセルバッファ番号を登録する送出時刻登録部６２と、セルバッファ２０の読み出しアドレスを生成する読み出し制御部６３とから構成される。セル出力リスト用メモリ９０は、送出タイムスロット対応にバッファ番号を蓄積する。
【００３６】
回線４から入力セルを受信すると、書き込み制御部６１が、図示しないカウンタから出力されるバッファ番号に従って、シーケンシャルな書き込みアドレスを生成し、入力セルをセルバッファ２０に書き込む。送出時刻登録部６２は、セル出力リスト９０のうち、空きセル検索５０からバス７を介して通知された時刻ｔｇｏと対応したにエントリ領域に、上記書き込みバッファ番号を登録する。例えば、ｔｇｏ＝「４１」、書き込みバッファ番号＝「１７」の場合、セル出力リスト９０の４１番目のエントリにバッファ番号「１７」が書き込まれる。
読み出し制御部６３は、送出タイムスロットに従って、セル出力リスト９０からバッファ番号を読み取り（例えば、送出タイムスロット＝「２４」の場合、バッファ番号「４」が読み出される）、そのバッファ番号に応じて読み出しアドレスを生成し、セルバッファ２０から１個のセルを読み出して回線５に送出する。
【００３７】
上記実施例では、ＶＰＩ毎にピークセル送出間隔単位での各時刻の空き塞がり状況を１ビットで示す検索テーブルを用意し、送出時刻が競合した場合に空き時刻を検索するようにしているため、時刻競合時におけるＣＤＶ発生において厳密なシェーピングを行なうことができる。
【００３８】
図１４は、図１に示したシェーピング回路の具体的な構成を示す。
タイマ４１は、入力回線４のインタフェース速度ｒでの１セル転送時間を単位として現在時刻ｔａを示す。送出タイムスロット生成６３ａは、出力回線５のインタフェース速度ｒ’での１セル転送時間を単位として、送出タイムスロット番号を生成する。セレクタ６２は、Ｒ／Ｗ信号に応じて、書き込みアドレスと読み出しアドレスの切替を行なう。
【００３９】
まず、セル受信時の動作について説明する。回線４から入力セルを受信すると、カウンタ６１ａがカウントアップされ、ＷＡ生成回路６１ｂが、上記カウンタ６１ａの値をバッファ２０の書き込みバッファ番号として書き込みアドレスを生成し、受信セルをバッファ２０に書き込む。
この時、ＶＰＩ識別回路３１とＶＰＩ／ＶＣＩ識別回路３２が、上記入力セルのヘッダ部からＶＰＩの値とＶＰＩ／ＶＣＩの値をそれぞれ識別する。上記ＶＰＩ識別３１から出力されたＶＰＩ値に基づいて、第１パラメータテーブル７１からピークセル間隔Ｔが読み出され、割算回路４２において、タイマ４１ａが示すセル到着時刻ｔａをピークセル間隔Ｔで割って制御用の到着時刻ｔａ’が算出される。また、上記ＶＰＩ／ＶＣＩ識別３２から出力されたＶＰＩ／ＶＣＩの値に基づいて、第２パラメータテーブル７２から理想送出時刻ｔｎ’が読み出され、比較器４３が上記理想送出時刻ｔｎ’と到着時刻ｔａ’を比較する。セレクタ４４は、上記比較器の出力に応じて、もし、ｔｎ’＜ｔａ’であればｔａ’を選択し、ｔｎ’≧ｔａ’であればｔｎ’を選択して、セル送出時刻ｔｏ’とする。
【００４０】
上記ＶＰＩ識別回路３１から出力されたＶＰＩに基づいて、セレクタ５１ａが、ＶＰＩ別検索テーブル８１−１〜８１−Ｎの中から、ＶＰＩ値に対応したテーブルをで選択する。上記テーブルの内容は、プライオイリティエンコーダ５１ｂに入力され、セル送出時刻ｔｏ’以降に位置したタイムスロットの中から、フラグビットが「０」状態となっている空き時刻ｔｇｏ’が一括検索され、乗算回路５２で識別ＶＰＩ値に対応したピークセル間隔Ｔと掛け合わせることにより、送出タイムスロットを基準にした送出時刻ｔｏが算出される。
【００４１】
上記送出時刻ｔｏは、割算回路５３ａで全コネクション検索テーブルメモリ８２の１ブロック分のビット数（スロット数）ｊで割り算される。割算回路５３ａから出力されるｔｏ／ｊの整数部の値を読み出しアドレスとして、全ＶＰＩ／ＶＣＩメモリ８２から１ブロックのデータが読み出され、プライオリティエンコーダ５３ｄに入力される。また、割算回路５３ａの剰余分を示す値がプライオリティエンコーダ５３ｄに入力され、プライオリティエンコーダ５３ｄは、メモリ８２から読み出された１ブロックのデータの中から、上記剰余値が示すビット以降でフラグビットが「０」となっている空きビット位置を一括検索する。１ブロックのデータ内に空きビットが存在しない場合は、ラッチ５３ｅにイネーブル信号が保持され、セレクタ５３ｂとセレクタ５３ｃがそれぞれの選択入力を切替る。この結果、ブロック状態レジスタ５４の中から、ｔｏ／ｊの整数部が示すビット位置以降でフラグビットが「０」状態にあるビット位置がプライオリティエンコーダ５３ｆで一括検索され、見つかった空きビット位置を読み出しアドレスとして、テーブルメモリ８２から次の１ブロック分のデータが読み出され、プライオリティエンコーダ５３ｄによって、再び空きビット位置が検索される。
【００４２】
このようにして、プライオリティエンコーダ５３ｄによって空きビット位置が見つかると、空きビット位置を示す値は加算器５３ｈに入力され、乗算器５３ｇによって計算されたメモリ８２の読み出しアドレスにｊを掛けた値と加算され、実送出時刻ｔｇｏを示す値として出力される。上記実送出時刻ｔｇｏの値を書き込みアドレスとして、セル出力リスト９０にカウンタ６１ａが示す書き込みバッファ番号が登録される。
【００４３】
また、プライオリティエンコーダ５３ｄによって見つけられた空きビット位置は、デコーダ５５ａによってデコードされ、フラグ更新回路５５ｂによって、全コネクション検索テーブル８２の上記ビット位置にフラグビット「１」がセットされる。また、比較器５５ｃで、上記ビット位置を含む１つのブロックのフラグビットが全て「１」となったか否かをチェックし、全て「１」の場合は、デコーダ５５ｄによってテーブル８２の読み出しアドレスをデコードし、フラグ更新回路５５ｅによって、レジスタ５４内の上記ブロックの属するビット位置のフラグを「１」に変更する。
【００４４】
加算器５３ｈから出力された実送出時刻ｔｇｏは、割算器５６ａにも入力され、をｔｇｏをＶＰＩのピークセル間隔Ｔで割ることによって、理想送出時刻ｔｎ’が算出される。算出された理想送出時刻ｔｎ’はデコーダ５６ｂに入力され、上記理想送出時刻ｔｎ’の値から小数部を切り上げた値と対応したビット位置がフラグ更新回路５６ｃに入力され、ＶＰＩ別検索テーブル８１のうち入力セルのＶＰＩ値に対応したテーブルのフラグが更新される。また、割算器５６ａから出力されたｔｎ’の値は、加算回路４５にも供給され、上記ｔｎ’の値にＶＰＩ／ＶＣＩのピークセル間隔Ｔ’が加算されて、第２パラメータテーブル７２の理想送出時刻の値が更新される。
【００４５】
セルの送出動作は次のようにして行われる。各送出タイムスロットにおいて、送出タイムスロット生成回路６３ａから送出タイムスロット番号が出力される。上記送出タイムスロット番号は、セレクタ６２を介して、セル出力リスト９０に読み出しアドレスとして与えられる。これによって、そのタイムスロットに登録されているバッファ番号がセル出力リスト９０から読み出され、読み出しアドレス（ＲＡ）生成回路６３ｂに供給される。ＲＡ生成回路６３ｂは、上記バッファ番号に基づいて読み出しアドレスを生成して、バッファ２０からりセルを読み出し、回線５に送出する。
【００４６】
【発明の効果】
以上の説明から明らかなように、本発明によれば、ＶＰＩとＶＣＩの両方の申告パラメータを考慮し、例えば、ＶＰＩのピークセル送出間隔単位でＶＣＩ対応の申告パラメータを満たすように送出時刻を計算し、ＶＰＩの申告ピークレートを満たす送出時刻を算出することによって、ＶＣＩ毎の申告トラヒックとＶＰＩ毎の申告トラヒックの両方を満足するシェーピング制御を実現することができる。
【図面の簡単な説明】
【図１】本発明によるＡＴＭインターフェイスの１実施例を示すブロック図。
【図２】本発明によるＡＴＭインタフェースの適用例を示すシステム構成図。
【図３】同一ＶＰに属するセルを処理するためのＡＴＭインタフェースの機能構成を示すブロック図。
【図４】複数ＶＰのセルを処理し、複数の出力回線に中継するためのＡＴＭインタフェースの機能構成を示すブロック図。
【図５】複数ＶＰに属するセル処理し、１つの回線へ中継するＡＴＭインタフェースの機能構成を示すブロック図。
【図６】図１におけるパラメータテーブルの構成を示す図。
【図７】図１における送出時刻計算の１例を示すフローチャート。
【図８】シェーピング動作の１例を示す図。
【図９】図１における空き時刻検索部と検索テーブルの構成の１例を示す図。
【図１０】図９における空き時刻検索の動作例を示す図。
【図１１】図１におけるセルバッファと、バッファ制御部と、セル出力リストの構成の１例を示す図。
【図１２】シェーピング機能の従来例を示す図。
【図１３】従来のシェーピングにおける問題点を説明するための図。
【図１４】図１のシェーピング回路の詳細構成の１例を示す図。
【符号の説明】
１…ＡＴＭインタフェース、１０…シェーピング回路、２０…セルバッファ、４０…送出時刻計算部、５０…空き時刻検索部、６０…バッファ制御部、
７０…パラメータテーブル、８０…検索テーブル、９０…セル出力リスト。
【図１】
0003602893.tif 000002
【図２】
0003602893.tif 000003
【図３】
0003602893.tif 000004
【図４】
0003602893.tif 000005
【図５】
0003602893.tif 000006
【図６】
0003602893.tif 000007
【図７】
0003602893.tif 000008
【図８】
0003602893.tif 000009
【図９】
0003602893.tif 000010
【図１０】
0003602893.tif 000011
【図１１】
0003602893.tif 000012
【図１２】
0003602893.tif 000013
【図１３】
0003602893.tif 000014
【図１４】
0003602893.tif 000015