(57)【要約】【課題】従来のＧＣＲＡ方式によるシェーパにおいて、時計に回り込みが発生した場合に、シェーパの動作に誤りが発生する問題を解決したセルスケジューリング方法を提供する。【解決手段】時計部が計数する現在時刻が最大値を越えて０となる回り込みが発生した際に、記憶部に記憶されたパラメータ値で、時計部が計数できる現在時刻の最大値を越える値を有するものから、（時計部が計数できる現在時刻の最大値＋１）の値を減算し、時計部が計数できる現在時刻の最大値以下の値を有するものを０とし、セル送信部に記憶された各送信可能時刻および各優先度で、時計部が計数できる現在時刻の最大値を越える値を有するものから、（時計部が計数できる現在時刻の最大値＋１）の値を減算し、時計部が計数できる現在時刻の最大値以下の値を有するものを０とする。【選択図】　　　　図９
2004023609.tif 000002
【特許請求の範囲】
【請求項１】
コネクション毎にセルを到着順に先頭から格納するキューと、
到着したセルを当該セルが所属するコネクションに対応したキューに格納する入力部と、
回線上において１セルの伝送に要する平均時間を１セル時間とし、当該１セル時間単位の整数値で現在時刻を計数する時計部と、
コネクション毎のセル間隔の値、許容されるセル遅延時間のゆらぎの値、およびパラメータ値を前記１セル時間単位の整数値で記憶する記憶部と、
前記キューに格納されたセルが当該キューの先頭に達した際に、当該セルが所属するコネクションに対応した、前記許容されるセル遅延時間のゆらぎの値、および前記パラメータ値を記憶部から読み込み、これらの値と前記時計部が計数する現在時刻に基づいて、当該セルの送信可能時刻を前記１セル時間単位の整数値で決定するステップと、前記キューに格納されたセルが回線に送信される際に、当該セルが所属するコネクションに対応した、前記セル間隔の値、および前記パラメータ値を前記記憶部から読み込み、これらの値と前記時計部が計数する現在時刻に基づいて、前記パラメータ値の更新値を決定し、前記パラメータ値の更新値を前記記憶部に書き込むステップとを含むセルスケジューリング部と、
前記セルスケジューリング部が決定した送信可能時刻、および当該送信可能時刻が決定されたセルを特定する情報を対で記憶するステップと、記憶された送信可能時刻から最も早い送信可能時刻を特定するステップと、特定された当該送信可能時刻が前記時計部が計数する現在時刻より以前の場合、当該送信可能時刻と対で記憶された情報に基づいて送信するセルを特定するステップと、当該セルを回線に送信するステップとを含むセル送信部とから構成されるセルシェーピング装置のセルスケジューリング方法であって、
前記時計部が計数する現在時刻が、最大値を越えて０となる回り込みが発生した際に、前記記憶部に記憶された各パラメータ値に対して、前記時計部が計数できる現在時刻の最大値を越える値を有するパラメータ値から、（前記時計部が計数できる現在時刻の最大値＋１）の値を減算し、前記時計部が計数できる現在時刻の最大値以下の値を有するパラメータ値を０とするステップと、
前記セル送信部に記憶された各送信可能時刻に対して、前記時計部が計数できる現在時刻の最大値を越える値を有する送信可能時刻から、（前記時計部が計数できる現在時刻の最大値＋１）の値を減算し、前記時計部が計数できる現在時刻の最大値以下の値を有する送信可能時刻を０とするステップとを含むことを特徴とするセルスケジューリング方法。
【請求項２】
コネクション毎にセルを到着順に先頭から格納するキューと、
到着したセルを当該セルが所属するコネクションに対応したキューに格納する入力部と、
回線上において１セルの伝送に要する平均時間を１セル時間とし、当該１セル時間単位の整数値で現在時刻を計数する時計部と、
コネクション毎のセル間隔の値、許容されるセル遅延時間のゆらぎの値、およびパラメータ値を前記１セル時間単位の整数値で記憶する記憶部と、
前記キューに格納されたセルが当該キューの先頭に達した際に、当該セルが所属するコネクションに対応した、前記許容されるセル遅延時間のゆらぎの値、および前記パラメータ値を前記記憶部から読み込み、これらの値と前記時計部が計数する現在時刻に基づいて、当該セルの送信可能時刻を前記１セル時間単位の整数値で決定し、前記パラメータ値を当該セルの優先度とするステップと、前記キューに格納されたセルが回線に送信される際に、当該セルが所属するコネクションに対応した、前記セル間隔の値、および前記パラメータ値を前記記憶部から読み込み、これらの値と前記時計部が計数する現在時刻に基づいて、前記パラメータ値の更新値を決定し、前記パラメータ値の更新値を前記記憶部に書き込むステップとを含むセルスケジューリング部と、
前記セルスケジューリング部が決定した送信可能時刻、優先度、および当該送信可能時刻が決定されたセルを特定する情報を対で記憶するステップと、記憶された送信可能時刻、および優先度から、最も早く、かつ最も優先度の高い送信可能時刻を特定するステップと、特定された当該送信可能時刻が前記時計部が計数する現在時刻より以前の場合、当該送信可能時刻、および優先度と対で記憶された情報に基づいて送信するセルを特定するステップと、当該セルを回線に送信するステップとを含むセル送信部とから構成されるセルシェーピング装置のセルスケジューリング方法であって、
前記時計部が計数する現在時刻が最大値を越えて０となる回り込みが発生した際に、前記記憶部に記憶された各パラメータ値に対して、前記時計部が計数できる現在時刻の最大値を越える値を有するパラメータ値から、（前記時計部が計数できる現在時刻の最大値＋１）の値を減算し、前記時計部が計数できる現在時刻の最大値以下の値を有するパラメータ値を０とするステップと、
前記セル送信部に記憶された各送信可能時刻、および各優先度に対して、前記時計部が計数できる現在時刻の最大値を越える値を有する送信可能時刻、および優先度から、（前記時計部が計数できる現在時刻の最大値＋１）の値を減算し、前記時計部が計数できる現在時刻の最大値以下の値を有する送信可能時刻、および優先度を０とするステップとを含むことを特徴とするセルスケジューリング方法。
【請求項３】
コネクション毎にセルを到着順に先頭から格納するキューと、
到着したセルを当該セルが所属するコネクションに対応したキューに格納する入力部と、
回線上において１セルの伝送に要する平均時間を１セル時間とし、当該１セル時間単位の整数値で現在時刻を計数する時計部と、
コネクション毎のセル間隔の値、許容されるセル遅延時間のゆらぎの値、およびパラメータ値を前記１セル時間単位の整数値で記憶する記憶部と、
前記キューに格納されたセルが当該キューの先頭に達した際に、当該セルが所属するコネクションに対応した、前記許容されるセル遅延時間のゆらぎの値、および前記パラメータ値を前記記憶部から読み込み、これらの値と前記時計部が計数する現在時刻に基づいて、当該セルの送信可能時刻を前記１セル時間単位の整数値で決定するステップと、前記キューに格納されたセルが回線に送信される際に、当該セルが所属するコネクションに対応した、前記セル間隔の値、および前記パラメータ値を前記記憶部から読み込み、これらの値と前記時計部が計数する現在時刻に基づいて、前記パラメータ値の更新値を決定し、前記パラメータ値の更新値を前記記憶部に書き込むステップとを含むセルスケジューリング部と、
当該セルスケジューリング部が決定した送信可能時刻、および当該送信可能時刻が決定されたセルを特定する情報を対で記憶するステップと、記憶された送信可能時刻から最も早い送信可能時刻を特定するステップと、特定された当該送信可能時刻が前記時計部が計数する現在時刻より以前の場合、当該送信可能時刻と対で記憶された情報に基づいて送信するセルを特定するステップと、当該セルを回線に送信するステップとを含むセル送信部とから構成されるセルシェーピング装置のセルスケジューリング方法であって、
前記時計部が計数できる現在時刻の最大値は、前記キューの数以上の値であり、前記時計部が計数する現在時刻と前記キューの対応関係が予め一意に定められ、
前記時計部が、前記時計部が計数する現在時刻が最大値を越えて０となった時計の回り込み回数を記録するステップを含み、
前記時計部が計数する現在時刻が更新された際に、前記記憶部に記憶された当該時刻に対応する前記キューに対応するコネクションのパラメータ値が、前記時計部が計数できる現在時刻の最大値を越える場合は、前記パラメータ値から、（前記時計部が計数できる現在時刻の最大値＋１）の値を減算した値に前記パラメータ値を更新し、前記時計部で計数できる現在時刻の最大値以下の値の場合は０に更新する更新ステップを含み、
セルスケジュール部が、前記記憶部からセルが所属するコネクションに対応したパラメータ値を読み込む際に、時計の回り込みが発生した後に前記パラメータ値に対して前記更新ステップが実行されていない状態であって、かつ読み込んだ前記パラメータ値が前記時計部が計数できる現在時刻の最大値を越える場合は、前記パラメータ値から、（前記時計部が計数できる現在時刻の最大値＋１）の値を減算し、前記時計部が計数できる現在時刻の最大値以下の場合は、前記パラメータ値を０とするステップを含み、
セルスケジュール部が、パラメータ値の更新値を前記記憶部に書き込む際に、時計の回り込みが発生した後に、更新の対象となる前記記憶部のパラメータ値に対して前記更新ステップが実行されていない状態の場合、前記パラメータの更新値に、（前記時計部が計数できる現在時刻の最大値＋１）の値を加算した値を、当該更新の対象となる前記記憶部のパラメータ値に書き込むステップを含み、
セル送信部が、セルの送信可能時刻、および当該送信可能時刻が決定されたセルを特定する情報を対で記憶するステップにおいて、セルの送信可能時刻を決定した際の時計の回り込み回数を、当該セルの送信可能時刻、および当該送信可能時刻が決定されたセルを特定する情報と併せて記憶するステップを含み、
セル送信部が、記憶された送信可能時刻から最も早い送信可能時刻を特定するステップにおいて、送信可能時刻を比較するために、記憶された送信可能時刻の値を評価する際に、当該送信可能時刻と併せて記録された時計の回り込み回数と、前記時計部に記憶された時計の回り込み回数を比較して、当該送信可能時刻の決定以降に発生した時計の回り込み回数を特定するステップと、
特定された当該回り込み回数が１回であって、かつ当該送信可能時刻が前記時計部が計数できる現在時刻の最大値を越える値の場合、当該送信可能時刻から、（前記時計部が計数できる現在時刻の最大値＋１）の値を減算した値に、当該送信可能時刻を変換するステップと、
特定された当該回り込み回数が１回であって、かつ当該送信可能時刻が前記時計部が計数できる現在時刻の最大値以下の場合、当該送信可能時刻を０に変換するステップとを含むことを特徴とするセルスケジューリング方法。
【請求項４】
コネクション毎にセルを到着順に先頭から格納するキューと、
到着したセルを当該セルが所属するコネクションに対応した前記キューに格納する入力部と、
回線上において１セルの伝送に要する平均時間を１セル時間とし、当該１セル時間単位の整数値で現在時刻を計数する時計部と、
コネクション毎のセル間隔の値、許容されるセル遅延時間のゆらぎの値、およびパラメータ値を前記１セル時間単位の整数値で記憶する記憶部と、
前記キューに格納されたセルが当該キューの先頭に達した際に、当該セルが所属するコネクションに対応した、前記許容されるセル遅延時間のゆらぎの値、および前記パラメータ値を前記記憶部から読み込み、これらの値と前記時計部が計数する現在時刻に基づいて、当該セルの送信可能時刻を前記１セル時間単位の整数値で決定し、前記パラメータ値を当該セルの優先度とするステップと、前記キューに格納されたセルが回線に送信される際に、当該セルが所属するコネクションに対応した、前記セル間隔の値、および前記パラメータ値を前記記憶部から読み込み、これらの値と前記時計部が計数する現在時刻に基づいて前記パラメータ値の更新値を決定し、前記パラメータ値の更新値を前記記憶部に書き込むステップとを含むセルスケジューリング部と、
前記セルスケジューリング部が決定した送信可能時刻、優先度、および当該送信可能時刻が決定されたセルを特定する情報を対で記憶するステップと、記憶された送信可能時刻、および優先度から、最も早く、かつ最も優先度の高い送信可能時刻を特定するステップと、特定された当該送信可能時刻が前記時計部が計数する現在時刻より以前の場合、当該送信可能時刻、および優先度と対で記憶された情報に基づいて送信するセルを特定するステップと、当該セルを回線に送信するステップとを含むセル送信部とから構成されるセルシェーピング装置のセルスケジューリング方法であって、
前記時計部が計数できる現在時刻の最大値は、前記キューの数以上の値であり、前記時計部が計数する現在時刻と前記キューの対応関係が予め一意に定められ、
前記時計部が、前記時計部が計数する現在時刻が最大値を越えて０となった時計の回り込み回数を記録するステップを含み、
前記時計部が計数する現在時刻が更新された際に、前記記憶部に記憶された当該時刻に対応する前記キューに対応するコネクションのパラメータ値が、前記時計部が計数できる現在時刻の最大値を越える場合は、前記パラメータ値から、（前記時計部が計数できる現在時刻の最大値＋１）の値を減算した値に前記パラメータ値を更新し、前記時計部で計数できる現在時刻の最大値以下の値の場合は０に更新する更新ステップを含み、
セルスケジュール部が、前記記憶部からセルが所属するコネクションに対応したパラメータ値を読み込む際に、時計の回り込みが発生した後に前記パラメータ値に対して前記更新ステップが実行されていない状態であって、かつ読み込んだ前記パラメータ値が前記時計部が計数できる現在時刻の最大値を越える場合は、前記パラメータ値から、（前記時計部が計数できる現在時刻の最大値＋１）の値を減算し、前記時計部が計数できる現在時刻の最大値以下の場合は、前記パラメータ値を０とするステップを含み、
前記セルスケジュール部が、パラメータ値の更新値を前記記憶部に書き込む際に、時計の回り込みが発生した後に、更新の対象となる前記記憶部のパラメータ値に対して、前記更新ステップが実行されていない状態の場合、前記パラメータの更新値に、（前記時計部が計数できる現在時刻の最大値＋１）の値を加算した値を当該更新の対象となる前記記憶部のパラメータ値に書き込むステップを含み、
前記セル送信部が、セルの送信可能時刻、優先度、および当該送信可能時刻が決定されたセルを特定する情報を対で記憶するステップにおいて、セルの送信可能時刻、および優先度を決定した際の時計の回り込み回数を、当該セルの送信可能時刻、優先度、および当該送信可能時刻が決定されたセルを特定する情報と併せて記憶するステップを含み、
前記セル送信部が、記憶された送信可能時刻、および優先度から、最も早く、かつ最も優先度の高い送信可能時刻を特定するステップにおいて、送信可能時刻、および優先度を比較するために、記憶された送信可能時刻、および優先度の値を評価する際に、当該送信可能時刻、および当該優先度と併せて記録された時計の回り込み回数と、前記時計部に記憶された時計の回り込み回数を比較して、当該送信可能時刻、および当該優先度の決定以降に発生した時計の回り込み回数を特定するステップと、
特定された当該回り込み回数が１回であって、かつ当該送信可能時刻、および当該優先度が各々、前記時計部が計数できる現在時刻の最大値を越える値の場合、当該送信可能時刻、および当該優先度から、（前記時計部が計数できる現在時刻の最大値＋１）の値を減算した値に、当該送信可能時刻、および当該優先度を各々変換するステップと、
特定された当該回り込み回数が１回であって、かつ当該送信可能時刻、および当該優先度が、各々前記時計部が計数できる現在時刻の最大値以下の場合、当該送信可能時刻、当該優先度を各々０に変換するステップとを含むことを特徴とするセルスケジューリング方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ＡＴＭセル等の固定長パケット（以降、「セル」と記載する）に対するセルシェーピング装置のセルスケジューリング方法に係わり、特に、ＧＣＲＡ方式で実現されたセルスケジューリング方法に関する。
【０００２】
【従来の技術】
セルシェーピング装置（以下、シェーパと呼ぶ）とは、コネクション毎に定められたトラヒック特性値に適合する様に、必要に応じてセルに遅延時間を付与する装置のことである。
従来の、シェーパの実現方式には、原理的に異なる２つの方式が存在する。一つはトークン方式、もう一つはＧＣＲＡ方式である。
従来のトークン方式によるシェーパの実現例を図１に示す。同図において、１０１は入力部、１０２，１０３はキュー、１０４，１０５は送信タイミング生成部、１０６は調停部である。
この実現例において、従来のトークン方式によるシェーパの動作を説明する。シェーパに到着したセルは、入力部１０１によってセルが所属するコネクションに対応したキューに格納される。
ここで、コネクションとはセルヘッダに含まれるＶＰＩ（Ｖｉｒｔｕａｌ　Ｐａｔｈ　Ｉｄｅｎｔｉｆｉｒｅ；仮想パス識別子）、およびＶＣＩ（Ｖｉｒｔｕａｌ　Ｃｈａｎｎｅｌ　Ｉｄｅｎｔｉｆｉｒｅ；仮想チャネル識別子）フィールドの一部、あるいは全部によって識別される仮想的なパスやチャネルを意味する。
【０００３】
キュー（１０２，１０３）は、先頭から到着順にセルを格納するもので、コネクション対応に存在する。
送信タイミング生成部（１０４，１０５）は、キュー（１０２，１０３）の先頭のセルが送信可能となった事を示すタイミング信号を生成するもので、コネクションに対応したキュー毎に存在する。
特許第３２３２０３６号や特許第３１０９４９１号に示される通り、送信タイミング生成部（１０４，１０５）は、コネクション毎のトラヒック特性値に応じて、クロック信号を分周する事によってタイミング信号を生成する方式で実現できる。
調停部１０６は、セルが送信可能となった事を示すタイミング信号が生成されたキュー（１０２，１０３）の先頭から、セルを取り出して回線に送信する。
この際に、セルが送信可能となったキュー（１０２，１０３）が複数存在する場合、調停部１０６は、キュー間に予め設定された固定優先度、ラウンドロビン、ランダムやこれらの組み合わせ等の調停規則に基づいてセルを取り出すキューを選択する。
【０００４】
従来のＧＣＲＡ方式によるシェーパの実現例を図２に示す。この図２に示す実現例は、特開２００１−２７４７９５号公報に記載されたシェーピング装置である。同図において、２０１はトラヒック特性値、パラメータ値を記憶する記憶部、２０２は時計部、２０３はセルスケジューリング部、２０４はセル送信部、２０５、２０６はキュー、２０７は入力部である。
この実現例において、従来のＧＣＲＡ方式によるシェーパの動作例を説明する。
記憶部２０１はコネクションの識別子の値でアドレッシングされる配列で構成される。ここで、コネクションとはセルヘッダに含まれるＶＰＩ、およびＶＣＩフィールドの一部、あるいは全部によって識別される仮想的なパスやチャネルを意味する。
図２に示す様に、シェーパに到着したセルは、入力部２０７によってセルが所属するコネクションに対応したキュー（２０５，２０６）に格納される。
キュー（２０５，２０６）は、先頭から到着順にセルを格納するもので、コネクション対応に存在する。
【０００５】
セルがキュー（２０５，２０６）の先頭に達した際に、キュー（２０５，２０６）の先頭に達したセルのコネクションに対応したトラヒック特性値、パラメータ値が記憶部２０１から、セルスケジューリング部２０３に入力される。
セルスケジューリング部２０３は、入力されたトラヒック特性値、パラメータ値、および時計部２０２が計数する現在時刻に基づいて、キュー（２０５，２０６）の先頭に達したセルの送信可能時刻を決定してセル送信部２０４に出力する。
セル送信部２０４は、キュー（２０５，２０６）の先頭のセルヘのポインタ情報とセルスケジューリング部２０３によって決定したセルの送信可能時刻を対で記憶する。
セルを回線に送信する際に、送信するセルのコネクションに対応したコネクション毎のトラヒック特性値、パラメータ値が記憶部２０１からセルスケジューリング部２０３に入力される。
セルスケジューリング部２０３は、入力されたトラヒック特性値、パラメータ値、および時計部２０２が計数する現在時刻に基づいて、パラメータ値の更新値を決定して、記憶部２０１に出力し、記憶されているパラメータ値を更新する。
【０００６】
従来のＧＣＲＡ方式によるシェーパの実現例のセルスケジューリング部２０３におけるセルスケジューリング方法の実現例を特開２００１−２７４７９５号公報に基づいて示す。
図３、および図４は、図２のセルスケジューリング部２０３のセルスケジューリング方法を示すフローチャートである。
このフローチャートでは、トラヒック特性値としてセル間隔の値と許容されるセル遅延時間のゆらぎを用い、セルの送信可能時刻を計算する際の現在時刻をｔａ、パラメータ値を更新する際の現在時刻をｔｅ、セルが所属するコネクションに対応したトラヒック特性値のセル間隔の値をｔ、許容されるセル遅延時間のゆらぎの値をτ、セルが所属するコネクションに対応したパラメータ値をＴＡＴ、セルの送信可能時刻をｔｓとしている。
セルがキュー（図２の２０５，２０６）の先頭に達した際に、キューの先頭に達したセルのコネクションに対応したトラヒック特性値である許容されるセル遅延時間のゆらぎτ、パラメータ値ＴＡＴが、記憶部（図２の２０１）からセルスケジューリング部（図２の２０３）に入力される。
【０００７】
セルスケジューリング部は、入力された許容されるセル遅延時間のゆらぎτ、パラメータ値ＴＡＴ、および時計部（図２の２０２）が計数する現在時刻ｔａに基づいて、図３のフローチャートに示された動作を開始する。
ｔａ＜ＴＡＴ−τの関係が成立する場合は、セルの送信可能時刻ｔｓをＴＡＴ−τとする（ステップ３０１、３０３）。
ＴＡＴ−τ≦ｔａの関係が成立する場合は、セルの送信可能時刻ｔｓをｔａとする（ステップ３０１、３０２）。
決定したセルの送信可能時刻ｔｓは、セル送信部（図２の２０４）に出力される。特願２００２−０２８２８４号に示された通り、この際にパラメータ値ＴＡＴをセルの優先度として、決定したセルの送信可能時刻ｔｓと共にセル送信部に出力する場合もある。
【０００８】
セルが回線に送信される際に、キューの先頭に達したセルのコネクションに対応したトラヒック特性値であるセル間隔の値ｔと、パラメータ値ＴＡＴが、記憶部からセルスケジューリング部に入力される。
セルスケジューリング部は、入力されたセル間隔の値ｔ、パラメータ値ＴＡＴ、および時計部が計数する現在時刻ｔｅに基づいて、図４のフローチャートに示された動作を開始する。
ｔｅ＜ＴＡＴの関係が成立する場合は、パラメータの値ＴＡＴをＴＡＴ＋ｔに更新する（ステップ４０１、４０３）。
ＴＡＴ≦ｔｅの関係が成立する場合は、パラメータの値ＴＡＴをｔｅ＋ｔに更新する（ステップ４０１、４０２）。
決定したパラメータ値の更新値ＴＡＴは記憶部に出力され、記憶されているパラメータ値が更新される。
【０００９】
従来のＧＣＲＡ方式によるシェーパのセル送信部の第１の動作例を、Ｐｉｅｒｒｅ　Ｂｏｙｅｒ，　Ｆａｂｒｉｃｅ　Ｇｕｉｌｌｅｍｉｎ，　Ｍｉｃｈｅｌ　Ｓｅｒｖｅｌ，　Ｊｅａｎ−Ｐｉｅｒｒｅ　Ｃｏｕｄｒｅｕｓｅ，　”ＳｐｅｃｅｉｎｇＣｅｌｌｓ　Ｐｒｏｔｅｃｔｓ　ａｎｄ　Ｅｎｈａｎｃｅｓ　Ｕｔｉｌｉｚａｔｉｏｎ　ｏｆ　ＡＴＭ　Ｎｅｔｗｏｒｋ　Ｌｉｎｋｓ，”ＩＥＥＥ　Ｎｅｔｗｏｒｋ，　Ｖｏｌ．６，　Ｎｏ．５，　Ｓｅｐ．１９９２．に基づいて示す。
図５は、上記の文献に記載された、図２のセル送信部２０４の実現例であり、一般にリングバッファ方式と呼ばれる。同図において、６０１は現在時刻に対応するバッファを示すポインタ、６０２，６０３，６０４はキューの先頭のセルヘのポインタを格納するバッファ１，バッファ２〜バッファＮである。
従来のＧＣＲＡ方式によるシェーパのセル送信部の動作をリングバッファ方式によって説明する。
リングバッファ方式とは、回線上で１セルの転送に要する時間（ＳＴＭ−１／ＳＴＳ−３ｃ回線で約２．８μ秒）を１タイムスロットとし、図５に示す様に、タイムスロットに対応するバッファを環状に並べ、現在時刻に対応するタイムスロットのセルを順次送信する方式である。
具体的には、図５において、現在時刻に対応するバッファを示すポインタ６０１が示すバッファは、現在時刻のタイムスロットに対応するセルヘのポインタを格納する。
【００１０】
ここで、１タイムスロットに要する時間で正規化された時刻、即ち（時刻／１タイムスロットに要する時間）を正規化時刻と呼ぶものとし、図５における正規化された現在時刻をｔ、バッファの数をＮとすると、このバッファの右隣のバッファは送信可能時刻が正規化時刻（ｔ＋１）、左隣のバッファは正規化時刻（ｔ＋Ｎ−１）となるセルへのポインタを格納する。
また、現在時刻に対応するバッファを示すポインタ６０１は、時計部（図２の２０２）が計数する時刻に基づいて更新される。
リングバッファは、セルがキュー（図２の２０５，２０６）の先頭に達した際に、スケジューリング部（図２の２０３）によって決定したセルの送信可能時刻に対応するタイムスロットのバッファに、キューの先頭のセルヘのポインタを格納する事によって、セルヘのポインタと送信可能時刻を対で記憶する。
但し、送信可能時刻に対応するタイムスロットのバッファに既に他のセルヘのポインタが格納されている場合は、時刻順に空きのバッファを検索して、最も近い空きのバッファにセルヘのポインタを格納する。
リングバッファは、現在時刻に対応するバッファを示すポインタ６０１によって示されるバッファのポインタで識別されるセルを回線に送信する事によって、リングバッファに格納されているセルの中から送信可能時刻が現在時刻以前となるセルを検出して回線に送信する。
【００１１】
従来のＧＣＲＡ方式によるシェーパのセル送信部の第２の動作例を、Ｅｕｇｅｎ　Ｗａｌｌｍｅｉｅｒ，　Ｔｏｍ　Ｗｏｒｓｔｅｒ，　”Ｔｈｅ　Ｓｐａｃｉｎｇ　Ｐｏｌｉｃｓｅｒ，　Ａｎ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　Ｅｆｆｉｃｉｅｎｔ　Ｐｅａｋ　Ｒａｔｅ　Ｂｉｔ　Ｃｏｎｔｒｏｌ　ｉｎ　ＡＴＭ　Ｎｅｔｗｏｒｋｓ，”　ＩＳＳ　１９９２，　Ｏｃｔ．１９９２．に基づいて示す。
図６は、上記の文献に記載された、図２に示すセル送信部２０４の実現例であり、一般にカレンダ方式と呼ばれる。同図において、７０１は現在時刻に対応するリストを示すポインタ、７０２，７０３，７０４は各々キューの先頭のセルヘのポインタを格納するリストである。
リストとは、順序関係のある要素を記憶する際に用いられるデータ構造の事で、リストの先頭の要素を示すポインタ、後尾の要素を示すポインタ、リストに記憶される要素から成り、更に、各要素は格納される情報、および次の要素を示すポインタから成る。
例えば、７０５はリスト１の後尾の要素、７０６はリスト１の先頭の要素である。また、図６では、リストに格納される要素の情報はキュー（図２の２０５，２０６）の先頭のセルへのポインタのリストとなる。
７０７は送信可能時刻に達したキューの先頭のセルヘのポインタを格納する送信リストである。
【００１２】
従来のＧＣＲＡ方式によるシェーパのセル送信部の動作をカレンダ方式によって説明する。
カレンダ方式とは、回線上で数セルの転送に要する時間を１タイムスロットとし、タイムスロットに対応するセルヘのポインタを格納するリストを環状に並べ、送信可能時刻に達したタイムスロットに対応するリストに格納された全てのセルヘのポインタを送信リストの後尾に移動する方式である。
具体的には、図６において、現在時刻に対応するリストを示すポインタ７０１が示すリストは、現在時刻のタイムスロットに対応するセルへのポインタを格納する。
ここで、１タイムスロットに要する時間で正規化された時刻、即ち（時刻／１タイムスロットに要する時間）を正規化時刻と呼ぶものとし、図６における正規化された現在時刻をｔ、リストの数をＮとすると、このリストの右隣のリストは送信可能時刻が正規化時刻（ｔ＋１）、左隣のリストは正規化時刻（ｔ＋Ｎ−１）となるセルヘのポインタのリストを格納する。
また、現在時刻に対応するリストを示すポインタ７０１は、時計部（図２の２０２）が計数する時刻に基づいて更新される。
【００１３】
図６に示すセル送信部は、セルがキューの先頭に達した際に、スケジューリング部（図２の２０３）によって決定したセルの送信可能時刻に対応するタイムスロットのリストの最後尾に、キューの先頭のセルヘのポインタをリストの要素として順次付け加えて格納する事によって、キューの先頭のセルヘのポインタと送信可能時刻を対で記憶する。
図６に示すセル送信部は、現在時刻に対応するリストを示すポインタ７０１によって示される、送信可能時刻に達したタイムスロットに対応するリストに格納されたセルヘのポインタを全て送信リスト７０７の後尾に移動し、送信リスト７０７に格納されたセルヘのポインタで示されるセルを、キューの先頭から取り出して順に回線に送信する事によって、格納されているセルヘのポインタの中から送信可能時刻が現在時刻以前となるセルヘのポインタを検出して、ポインタが示すセルを送信可能時刻が最も早いセルから送信可能時刻順に回線に送信する。
【００１４】
従来のＧＣＲＡ方式によるシェーパのセル送信部の第３の実現例を、特開２００１−２７４７９５号公報を基に示す。
図７は、図２に示すセル送信部２０４の実現例であり、一般にシーケンサ方式と呼ばれる。図７において、８０１，８０２はキュー、８０３はキューの先頭のセルへのポインタ、８０４はキューの先頭のセルのタイムスロット値、８０５はポインタとタイムスロット値を要素とする配列構造、８０６はキュー、８０７はキューの先頭に達したセルヘのポインタ、８０８はキューの先頭に達したセルのタイムスロット値、８０９はブロードキャストバスである。
図７に示すセル送信部は、回線上で１セルの転送に要する時間を１タイムスロットとし、図７に示す様に、送信可能時刻が決定したキューの先頭のセルへのポインタと、そのセルのタイムスロット値から成る要素をタイムスロット値の順にソートする方式である。
ここで、セルが所属するコネクション、キュー、ＣＢＲ、ｎｒｔ−ＶＢＲ等のトラヒッククラス間などに予め優先度が設定されているものとし、優先度は値が小さいほど優先度が高いものとする。
シーケンサは主にポインタとタイムスロット値を要素とする配列構造で構成され、図７の実現例では右側からタイムスロット値の順に要素がソートされている。
具体的には、図７において、ポインタとタイムスロット値を要素とする配列構造８０５の各要素は隣の要素にシフトする事が可能な構造となっている。
【００１５】
図７に示すセル送信部は、セルがキュー８０６の先頭に達した際に、このキューの先頭を示す様にキューの先頭に達したセルヘのポインタ８０７を設定し、｛セルスケジューリング部（図２の２０３）によって決定したセルの送信可能時刻＊（優先度の最大値＋１）＋セルの優先度｝の値を、キューの先頭に達したセルのタイムスロット値８０８に設定する事によって、キューの先頭のセルヘのポインタとタイムスロット値を対で記憶する。
次に、図７に示すセル送信部は、キューの先頭に達したセルのタイムスロット値８０８を、ブロードキャストバス８０９を用いてポインタとタイムスロット値を要素とする配列構造８０５内の各要素のタイムスロット値と並列に比較し、配列構造８０５内の各要素のタイムスロット値が、キューの先頭に達したセルのタイムスロット値８０８以上となる最初の要素の位置を挿入位置として、それ以上の全ての要素を左側にシフトし、キューの先頭に達したセルヘのポインタ８０７とキューの先頭に達したセルのタイムスロット値８０８を挿入位置に格納する事によって、要素をタイムスロット値の順にソートする。
図７に示すセル送信部は、配列構造８０５の最も右の要素のタイムスロット値に含まれるセルの送信可能時刻と、時計部２０２が計数する時刻を比較し、前者の値が後者の値以前となる場合は、最も右の要素のポインタが示すキューの先頭に格納されたセルを回線に送信し、最も右の要素を配列構造８０５から削除し、残りの要素を右側にシフトする事によって、格納されているセルへのポインタの中から送信可能時刻が最も早くかつ優先度が最も高いセルのポインタ情報を特定して、特定された送信可能時刻が現在時刻より以前の場合、そのセルを回線に送信する。
【００１６】
従来のＧＣＲＡ方式によるシェーパのセル送信部の第４の動作例を、特願２００２−０２８２８４号に基づいて示す。
特願２００２−０２８２８４号に示された通り、ＧＣＲＡ方式によるシェーパのセル送信部は、ヒープによる優先キューの要素を、到着したセルのタイムスロット値、およびキューの先頭のセルへのポインタとし、要素の優先度をタイムスロット値で判断する事によって実現する事が出来る。
ヒープとは配列による半順序のついた木のデータ構造の事であり、優先キューの実装やソータの実装に用いられる。
優先キューとは、優先度が割り当てられられた要素から、優先度の最も高い要素を特定するデータ構造の事である。優先キューは、要素を記憶するデータ構造と、データ構造から最も優先度の高い要素を削除するアルゴリズムと、データ構造に要素を挿入するアルゴリズムから構成される。
具体的な、削除、挿入のアルゴリズムは特願２００２−０２８２８４号に示されている。
【００１７】
ヒープによる優先キューのデータ構造を図８に示す。図８における要素の値は優先度を表し、値が少ないほど優先度が高いものとする。
図８における要素の配置は、「要素が子を有する場合、その要素の優先度は子の優先度以上となる」規則に基づいている。このため、ヒープの一番上の要素は最も高い優先度を持つことになる。
ヒープによる優先キューは、セルがキュー（図２の２０５，２０６）の先頭に達した際に、このキューの先頭を示す様にキューの先頭に達したセルヘのポインタを設定し、そして、｛セルスケジューリング部（図２の２０３）によって決定したセルの送信可能時刻＊（優先度の最大値＋１）＋セルスケジューリング部によって決定したセルの優先度｝の値をセルのタイムスロット値に設定し、これらの値から成る要素をヒープによる優先キューに挿入する。
次に、ヒープによる優先キューは、最も上の要素のタイムスロット値に含まれるセルの送信可能時刻と、時計部が計数する時刻を比較し、前者の値が後者の値以前となる場合は、最も上の要素のポインタが示すバッファ、もしくはキューの先頭に格納されたセルを回線に送信し、最も上の要素を削除する事によって、ヒープによる優先キューに格納されているセルの中から送信可能時刻が最も早くかつ優先度が最も高いセルを特定し、特定された送信可能時刻が現在時刻より以前の場合、そのセルを回線に送信する。
【００１８】
以上の説明から明らかな通り、従来のＧＣＲＡ方式によるシェーパの実現例におけるセルスケジューリング方法は、時計部（図２の２０２）が計数する現在時刻に基づいて、セルの送信可能時刻を決定し、パラメータ値を更新している。更に、パラメータ値に基づいてセルの優先度を決定する場合もある。
しかし、現実のシェーパの実現において、時計部が計数出来る時刻には上限がある。例えば、時刻がＮｂｉｔの整数値で計数される場合、計数可能な時刻の最大値は（２のＮ乗−１）となり、時間の経過と共に時計部が計数する時刻がこの最大値を越えた場合、時計が計数する時刻が０となる時計の回り込みが発生し、再び最大値の時刻までの計数が行なわれる。
この様に、シェーパの時計に回り込みが発生すると、シェーパに記憶されている回り込み以前の時刻に基づいて計算された値、即ち、セルの送信可能時刻、およびパラメータ値は、回り込み以後の時計が計数する時刻を基準にすると不正な値となる。
セルの送信可能時刻は、コネクション間で比較されたり、時計が計数する現在時刻と比較される。またパラメータ値は、時計が計数する現在時刻と比較される。
このため、時計に回り込みが発生すると、シェーパの動作に誤りが発生する。更に、パラメータ値に基づいてセルの優先度を決定する場合は、時計に回り込みが発生すると、この優先度も不正な値となる。
このため、従来のＧＣＲＡ方式によるシェーパの実現例におけるセルスケジューリング方法には、時計に回り込みが発生すると、シェーパに記憶された時刻に依存した値が不正な値となり、シェーパの動作に誤りが発生する問題点がある。
【００１９】
【発明が解決しようとする課題】
従来のＧＣＲＡ方式によるシェーパの実現例のセルスケジューリング方法における時計の回り込みの問題の解決方法が、特開平１０−１１７１９５号公報に示されている。
この特開平１０−１１７１９５号公報に記載された実施例では、時計部が計数出来る現在時刻の最大値は、セル間隔の値の最大値と、許容されるセル遅延時間のゆらぎの値の最大値と、バッファ長の和の４倍を越える値とし、コネクション毎のパラメータ値の最大値は時計の最大値と同じとしている。
コネクション毎の各パラメータ値は、２ｂｉｔのフラグを持ち、これらのフラグは時計の周期の１／４以上の時間で交互にセットされ、スケジューリング部がセルの送信可能時刻を決定し、パラメータ値を更新した際にリセットされる。
セルスケジューリング部は、現在時刻とパラメータ値に基づいてセルの送信可能時刻を決定する際に、パラメータ値のフラグの値が［１，１］の場合は、パラメータ値が計算されてから時計の周期の１／４以上の時間が経過されたものと判断する。これ以外の場合は、パラメータ値が有効な値を保持しているものと判断し、セルの送信可能時刻を計算する。
以上の説明から明らかな通り、この特開平１０−１１７１９５号公報に記載された実施例は、時計の回り込みによって、シェーパに記憶されたパラメータ値が不正な値となった事を判定する事が出来る。
従って、この実施例は、従来のＧＣＲＡ方式によるシェーパの実現例において、セル送信部として第１の動作例のリングバッファ方式、および第２の動作例のカレンダ方式を適用した場合は、時計の回り込みの問題を解決する事が出来る。
【００２０】
但し、この特開平１０−１１７１９５号公報に記載された実施例は、これらの方式が、各セルの送信可能時刻に関する情報をバッファやリストの位置情報として保持しているため、時計部が計数出来る現在時刻の最大値とバッファやリストの個数を同一値とすれば、時計に回り込みが発生しても位置情報にも同様に回り込みが発生するため、結果としてセルの送信時刻は不正にはならない性質を利用している。
一方、セル送信部として第３の動作例のシーケンサ方式や、第４の動作例のヒープによる優先キューが使用される場合、これらの方式は、各セルの送信可能時刻や優先度等の時刻に依存した値を情報として記憶するが、この特開平１０−１１７１９５号公報に記載された実施例では、セル送信部に記憶された送信可能時刻、優先度等の時刻に依存した値に対する時計の回り込み処理を行なう事は出来ない。
従って、この特開平１０−１１７１９５号公報に記載された実施例は、従来のＧＣＲＡ方式によるシェーパの実現例において、セル送信部として第３の動作例のシーケンサ方式、および第４の動作例ヒープによる優先キュー方式の様に、送信可能時刻、優先度、および送信可能時刻が決定されたセルを特定する情報等を対で記憶する方式に基づくセル送信部を有するシェーパにおいては、時計の回り込みの問題を解決する事が出来ない問題点がある。
【００２１】
従来のＧＣＲＡ方式によるシェーパの実現例のセルスケジューリング方法における時計の回り込みの問題の解決方法が、特開平１０−２９４７４１号公報に示されている。
この特開平１０−２９４７４１号公報に記載された実施例は、特開平１０−２９４７４１号公報の段落番号［００１３］の記述から明らかな通り、セル送信部としてリングバッファ方式を前提としている。
コネクション毎の各パラメータ値は、１ｂｉｔの有効フラグを持つが、この有効フラグの具体的な設定方法や、そのタイミングに関する記述は、特開平１０−２９４７４１号公報の段落番号［００４３］に、「（前回送信時刻＋セル間隔）が時計の時刻以前となったらフラグを無効とし、この制御が読み出し制御メモリ１周毎に１回以上行なわれる」との記述があるのみで、これだけでは時計の回り込みが解決出来るかどうかは、特開平１０−２９４７４１号公報の記載からは判断できない。
しかし、この方法は、明らかにコネクション毎のパラメータ値の有効性しか判断していないため、特開平１０−１１７１９５号公報と同様に、この特開平１０−２９４７４１号公報に記載された実施例は、少なくとも、従来のＧＣＲＡ方式によるシェーパの実現例において、送信可能時刻、優先度、および送信可能時刻が決定されたセルを特定する情報等を対で記憶する方式に基づくセル送信部を有するシェーパにおいては、時計の回り込みの問題を解決する事が出来ない問題点がある。
【００２２】
従来のＧＣＲＡ方式によるシェーパの実現例のセルスケジューリング方法における時計の回り込みの問題の解決方法が、特開２００１−３６５４０号公報に示されている。
この特開２００１−３６５４０号公報に記載された実施例は、特開２００１−３６５４０号公報の段落番号［００２４］の記述から明らかな通り、セル送信部としてリングバッファ方式を前提としている。
コネクション毎の各パラメータ値は、上位に２ｂｉｔが付与されており、時計にも上位２ｂｉｔが付与されており、時計の回り込み回数を計数する。
パラメータ値の上位２ｂｉｔは周期判定処理によって設定される。周期判定処理は、時計に回り込みが発生した際に全てのパラメータ値に対して実行される、もしくは、時計の値が更新された際に更新時刻に対応するキューのパラメータに対して実行される。
周期判定処理は、パラメータ値の上位２ｂｉｔの値から時計の上位２ｂｉｔの値を減算して、パラメータ値が現在時刻以前となったか否かを判断する。
しかし、この方法は、明らかにコネクション毎のパラメータ値の有効性しか判断していないため、特開平１０−１１７１９５号公報と同様に、この特開２００１−３６５４０号公報に記載された実施例は、従来のＧＣＲＡ方式によるシェーパの実現例において、送信可能時刻、優先度、および送信可能時刻が決定されたセルを特定する情報等を対で記憶する方式に基づくセル送信部を有するシェーパにおいては、時計の回り込みの問題を解決する事が出来ない問題点がある。
【００２３】
本発明は、前記従来技術の問題点を解決するためになされたものであり、本発明の目的は、従来のＧＣＲＡ方式によるシェーパにおいて、時計に回り込みが発生すると、シェーパに記憶された時刻に依存した値が不正な値となり、シェーパの動作に誤りが発生する問題点を解決し、かつ、この問題の既存の解決方法における、送信可能時刻、優先度、および送信可能時刻が決定されたセルを特定する情報等を対で記憶する方式に基づくセル送信部を有するシェーパには適用できない問題点を解決したセルスケジューリング方法を提供することにある。
本発明の前記ならびにその他の目的と新規な特徴は、本明細書の記述、および添付図面によって明らかにする。
【００２４】
【課題を解決するための手段】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、下記の通りである。
本発明の請求項１、２に係わる発明は、前述の目的を達成するために、ＧＣＲＡ方式で実現されたシェーピング装置のセルスケジューリング方法において、時計部が計数する現在時刻が最大値を越えて０となる回り込みが発生した際に、記憶部に記憶された各パラメータ値に対して、時計部が計数できる現在時刻の最大値を越える値を有するパラメータ値から、（時計部が計数できる現在時刻の最大値＋１）の値を減算し、時計部が計数できる現在時刻の最大値以下の値を有するパラメータ値を０とするステップ、および、セル送信部に記憶された各送信可能時刻、および、各優先度に対して、時計部が計数できる現在時刻の最大値を越える値を有する送信可能時刻、および、優先度から、（時計部が計数できる現在時刻の最大値＋１）の値を減算し、時計部が計数できる現在時刻の最大値以下の値を有する送信可能時刻、および優先度を０とするステップを含む事を最も主要な特徴とする。
【００２５】
本発明の請求項３、４に係わる発明は、前述の目的を達成するために、ＧＣＲＡ方式で実現されたシェーピング装置のセルスケジューリング方法において、時計部が計数できる現在時刻の最大値は、キューの数以上の値であり、時計部が計数する現在時刻とキューの対応関係が予め一意に定められ、時計部が、当該時計部が計数する現在時刻が最大値を越えて０となった時計の回り込み回数を記録するステップを含み、時計部が計数する現在時刻が更新された際に、当該時刻に対応するキューに対応するコネクションのパラメータ値が、時計部が計数できる現在時刻の最大値を越える場合は、当該パラメータ値から、（時計部が計数できる現在時刻の最大値＋１）の値を減算した値にパラメータ値を更新し、時計部で計数できる現在時刻の最大値以下の値の場合は０に更新する更新ステップを含み、セルスケジュール部が、記憶部からセルが所属するコネクションに対応したパラメータ値を読み込む際に、時計の回り込みが発生した後にパラメータ値に対して前記更新ステップが実行されていない状態であって、かつ読み込んだパラメータ値が時計部が計数できる現在時刻の最大値を越える場合は、パラメータ値から、（時計部が計数できる現在時刻の最大値＋１）の値を減算し、時計部が計数できる現在時刻の最大値以下の場合は、パラメータ値を０とするステップを含み、セルスケジュール部が、パラメータ値の更新値を記憶部に書き込む際に、時計の回り込みが発生した後に、更新の対象となる記憶部のパラメータ値に対して、前記更新ステップが実行されていない状態の場合、パラメータの更新値に、（時計部が計数できる現在時刻の最大値＋１）の値を加算した値を更新の対象となる記憶部のパラメータ値に書き込むステップを含み、セル送信部が、セルの送信可能時刻、優先度、および送信可能時刻が決定されたセルを特定する情報を対で記憶するステップにおいて、セルの送信可能時刻、および優先度を決定した際の時計の回り込み回数を、セルの送信可能時刻、優先度、および送信可能時刻が決定されたセルを特定する情報と併せて記憶するステップを含み、セル送信部が、記憶された送信可能時刻、および優先度から、最も早く、かつ最も優先度の高い送信可能時刻を特定するステップにおいて、送信可能時刻、および優先度を比較するために、記憶された送信可能時刻、および優先度の値を評価する際に、送信可能時刻、および優先度と併せて記録された時計の回り込み回数と、時計部に記憶された時計の回り込み回数を比較して、送信可能時刻、および優先度の決定以降に発生した時計の回り込み回数を特定するステップと、特定された回り込み回数が１回であって、かつ送信可能時刻、および優先度が、各々時計部が計数できる現在時刻の最大値を越える値の場合、送信可能時刻、および優先度から各々、（時計部が計数できる現在時刻の最大値＋１）の値を減算した値に、送信可能時刻、および優先度を各々変換するステップと、特定された該回り込み回数が１回であって、かつ送信可能時刻、および優先度が、各々時計部が計数できる現在時刻の最大値以下の場合、送信可能時刻、優先度を各々０に変換するステップとを含む事を最も主要な特徴とする。
【００２６】
［作用］
従来のＧＣＲＡ方式によるシェーパの実現例から明らかな通り、シェーパに記憶されるコネクション毎のパラメータ値、セルの送信可能時刻の値は何れも１セル時間を単位とする時間となる。
時計部が計数出来る現在時刻が最大値を越えて０となる回り込みが発生した場合、時計が示す時刻は本来の時刻から（時計が計数できる現在時刻の最大値＋１）の値を減算した値となる。
従って、従来のＧＣＲＡ方式によるシェーパの実現例のセルスケジューリング部におけるセルスケジューリング方法の実現例から明らかな通り、時計部に回り込みが発生した場合、シェーパに記憶されたコネクション毎のパラメータ値、セルの送信可能時刻、優先度等の時刻に依存した値から、（時計が計数できる現在時刻の最大値＋１）の値を減算すれば、これらの値を正しい値に修正する事が出来る。
但し、従来のセルスケジューリング方法の実現例から明らかな通り、パラメータ値を修正した結果負の値となる場合は、これを０としても算出される送信可能時刻は同一値となるため、この場合はパラメータ値は０とする。
また、送信可能時刻が負の値となる場合は、現在時刻が送信可能時刻を過ぎたという事であり、セルは可能な限り早急に送信する必要があるため、これを０としてもシェーパの動作に支障は無い。
更に、送信可能時刻を決定した際のパラメータ値を優先度とした場合、優先度が負の値となる場合は、セルは可能な限り早急に送信する必要があるため、これを０としてもシェーパの動作に支障は無い。
【００２７】
本発明の請求項１、２に係わる発明は、前述の原理に基づいて、従来のＧＣＲＡ方式によるシェーパにおいて、時計に回り込みが発生すると、シェーパに記憶された時刻に依存した値が不正な値となり、シェーパの動作に誤りが発生する問題点を、送信可能時刻、優先度、および送信可能時刻が決定されたセルを特定する情報等を対で記憶する方式に基づくセル送信部を有する場合において解決する。
但し、請求項１、２に係わる発明の解決方法は、時計に回り込みが発生した場合、シェーパに記憶されたコネクション毎のパラメータ値、セルの送信可能時刻、優先度等の値を一斉に修正するため、シェーパがサポートするコネクション数が少ない場合は実用的であるが、コネクション数が増大すると短時間の間にこれらの値を一斉に修正することは現実的に困難となる。
【００２８】
従って、シェーパがサポートするコネクション数が多い場合は、時計部が計数出来る現在時刻が最大値を越えて０となる回り込みが発生した後に、これらの値を分散して修正する必要がある。
このため、時計部が計数する現在時刻とキューの対応関係、即ち、コネクションとの対応関係を予め定めておき、現在時刻が更新された際に、その時刻に対応するコネクションのパラメータ値を前述の原理に基づいて修正する。
但し、この場合、時計に回り込みが発生してから修正が完了するまでの間はパラメータ値は不正な値となる。
このため、セルスケジュール部は、パラメータ値を読み込む際に、時計に回り込みが発生したがこのパラメータ値に対する修正が完了していない事を検出した場合、読み込んだ値を前述の原理に基づいて修正する。
また、セルスケジュール部は、パラメータ値を書出す際に、時計に回り込みが発生したがこのパラメータ値に対する修正が完了していない事を検出した場合、書き込む値に対して、（時計が計数できる現在時刻の最大値＋１）の値を加算してから書き込み動作を行ない、その後、このパラメータ値に対する修正が行なわれた際に値が正しくなる様に修正する。
【００２９】
また、セルの送信可能時刻、優先度に関しては、セルスケジューリング部がセルの送信可能時刻を決定した際の時計の回り込み回数を、これらの値と対でセル送信部に記憶する。
セル送信部は、送信可能時刻が決定してからセルが送信されるまで、時計の回り込みは２回以上発生しない性質を利用して、セルの送信可能時刻や優先度と対で記憶された時計の回り込み回数と、これらの値を評価する際の時計の回り込み回数を比較する事によって、これらの値に対して修正を行なう。
具体的には、セル送信部は記憶されたこれらの値を評価する際に、回り込み回数が１の場合は、（時計が計数できる現在時刻の最大値＋１）の値をこれらの値から減算する。但し、減算した結果が負の値となる場合は０に変換する。
本発明の請求項３、４に係わる発明は、前述の原理に基づいて、従来のＧＣＲＡ方式によるシェーパにおいて、時計に回り込みが発生すると、シェーパに記憶された時刻に依存した値が不正な値となり、シェーパの動作に誤りが発生する問題点を、送信可能時刻、優先度、および送信可能時刻が決定されたセルを特定する情報等を対で記憶する方式に基づくセル送信部を有する場合において解決する。
【００３０】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
なお、実施の形態を説明するための全図において、同一機能を有するものは同一符号を付け、その繰り返しの説明は省略する。
［実施の形態１］
本発明の請求項１、２に係わるセルシェーピング装置の実施の形態を、図２に示された従来のＧＣＲＡ方式によるシェーパの実現例と同じ構成のシェーパにおいて示す。
ここで、セルスケジューリング部（図２の２０３）におけるセルスケジューリング方法として、図３、および図４に示されたセルスケジューリング部におけるセルスケジューリング方法が用いられる。
また、セル送信部（図２の２０４）として、図７に示されたシーケンサ方式、もしくは図８に示されたヒープによる優先キューが用いられるものとする。
請求項１に係わる発明の実施の形態は、請求項２に係わる発明の実施の形態に包含されるため、以下、請求項２に係わる発明の実施の形態を用いて動作例を示す。
【００３１】
時計部（図２の２０２）が計数する現在時刻は、回線上において１セルの伝送に要する平均時間を１セル時間とし、この１セル時間を単位とするＮｂｉｔの符合なし整数値で実現されるものとする。
この場合、時計部が計数出来る現在時刻の最大値は（２のＮ乗−１）となり、最大時刻を越えた場合に、計数する時刻が０となる回り込みが発生する。
時計部が計数出来る現在時刻のｂｉｔ長Ｎは、幾らの値であっても論理的には問題は無い。ｂｉｔ長が短ければ回り込み処理が頻発し、長ければ回り込み処理の発生頻度が減少する。
本実施の形態では、回り込み処理の実現方法を簡略化するために、時計部が計数できる現在時刻のｂｉｔ長Ｎを、（セルシェーピング装置が対応出来るセル間隔の最大値＋セルシェーピング装置が対応出来る許容されるセル遅延時間のゆらぎの値）の値を表現できる最小のｂｉｔ長とする。
【００３２】
セルスケジューリング方法の実現例から明らかな通り、パラメータ値が更新された際の更新値の最大値は、（現在時刻の最大値＋セルシェーピング装置が対応出来るセル間隔の最大値＋セルシェーピング装置が対応出来る許容されるセル遅延時間のゆらぎの値）となる。
また、セルの送信可能時刻の最大値は、（現在時刻の最大値＋セルシェーピング装置が対応出来るセル間隔の最大値）、セルの優先度の最大値はパラメータ値の最大値と同じとなる。
従って、時計部が計数できる現在時刻のｂｉｔ長Ｎを、（セルシェーピング装置が対応出来るセル間隔の最大値＋セルシェーピング装置が対応出来る許容されるセル遅延時間のゆらぎの値）の値を表現できる最小のｂｉｔ長とした場合、パラメータ値、セルの送信可能時刻、優先度は、（Ｎ＋１）ｂｉｔの符合なし整数値で実現する事が出来る。
この場合、これらの値が時計部が計数できる現在時刻の最大値を越える場合、これらの値から（時計部が計数できる現在時刻の最大値の値＋１）を減算する演算は、これらの値の最上位ｂｉｔが［１］の場合は、この最上位ｂｉｔを［０］とする演算と等価となる。
【００３３】
以上の前提に基づいて、時計部に回り込みが発生した際の動作例を、図９のフローチャートに示す。
時計部に回り込みが発生した際に、記憶部（図２の２０１）に記憶された各パラメータ値に対して、パラメータ値の上位１ｂｉｔが［０］の場合、パラメータ値を０とし、パラメータ値の上位１ｂｉｔが［１］の場合、上位１ｂｉｔを［０］とする（ステップ１００１）。
この動作によって、時計部が計数できる現在時刻の最大値を越える値を有するパラメータ値から、（時計部が計数できる現在時刻の最大値＋１）の値を減算し、時計部が計数できる現在時刻の最大値以下の値を有するパラメータ値を０とする。
前述の［作用］の欄に記載した通り、時計部が計数できる現在時刻の最大値以下の値を有するパラメータ値を０としてもシェーパの動作には支障は無い。
引き続き、セル送信部（図２の２０４）に記憶された各送信可能時刻、および優先度に対して、送信可能時刻、優先度の上位１ｂｉｔが［０］の場合、これらの値を０とし、送信可能時刻、優先度の上位１ｂｉｔが［１］の場合、上位１ｂｉｔを［０］とする（ステップ１００２）。
この動作によって、時計部が計数できる現在時刻の最大値を越える値を有する送信可能時刻、および優先度から、（時計部が計数できる現在時刻の最大値＋１）の値を減算し、時計部が計数できる現在時刻の最大値以下の値を有する送信可能時刻、および優先度を０とする。
前述の［作用］の欄に記載した通り、時計部が計数できる現在時刻の最大値以下の値を有する送信可能時刻、および優先度を０としてもシェーパの動作に支障は無い。
【００３４】
［実施の形態２］
本発明の請求項３、４に係わるセルシェーピング装置の実施の形態を、図２に示された従来のＧＣＲＡ方式によるシェーパの実現例と同じ構成のシェーパにおいて示す。
ここで、セルスケジューリング部（図２の２０３）におけるセルスケジューリング方法として、図３、および図４に示されたセルスケジューリング部におけるセルスケジューリング方法が用いられる。
また、セル送信部（図２の２０４）として、図７に示されたシーケンサ方式、もしくは図８に示されたヒープによる優先キューが用いられるものとする。
請求項３に係わる発明の実施の形態は、請求項４に係わる発明の実施の形態に包含されるため、以下、請求項４に係わる発明の実施の形態を用いて動作例を示す。
時計部が計数する現在時刻は、回線上において１セルの伝送に要する平均時間を１セル時間とし、この１セル時間を単位とするＮｂｉｔの符合なし整数値で実現されるものとする。
【００３５】
この場合、時計部（図２の２０１）が計数出来る現在時刻の最大値は（２のＮ乗−１）となり、最大時刻を越えた場合、計数する時刻が０となる回り込みが発生する。
また、時計部は、Ｍｂｉｔの符合なし整数値で上記の時計の回り込み回数の発生回数を記録する。
時計部が計数出来る現在時刻のｂｉｔ長Ｎは、セルシェーピング装置が備えるキュー（図２の２０５，２０６）の数を表現できるｂｉｔ長以上であれば、幾らの値であっても論理的には問題は無い。
本実施の形態では、（セルシェーピング装置が対応出来るセル間隔の最大値＋セルシェーピング装置が対応出来る許容されるセル遅延時間のゆらぎの値）の値がセルシェーピング装置が備えるキューの数より大幅に大きいものとし、また、回り込み処理の実現方法を簡略化するために、時計部が計数できる現在時刻のｂｉｔ長Ｎを（セルシェーピング装置が対応出来るセル間隔の最大値＋セルシェーピング装置が対応出来る許容されるセル遅延時間のゆらぎの値）の値を表現できる最小のｂｉｔ長とする。
【００３６】
本実施の形態における、時計部が計数する現在時刻とキューの間の対応関係は、セルシェーピング装置が備えるキューの数をＬ本とした場合、各キューは０から（Ｌ−１）の値で識別され、この値が時計部が計数する時刻と対応するものとする。
時計部が計数する現在時刻が更新された際に、更新時刻に対応するキューに対応するコネクションのパラメータ値に対して更新処理が行なわれる。例えば、更新された時刻がＫの場合、Ｋで識別されるキューに対応するコネクションのパラメータ値に対して更新処理が行なわれる。
この場合、時計に回り込みが発生してから修正が完了するまでの間はパラメータ値は、（時計部が計数できる現在時刻の最大値の値＋１）が加算された値となるため、セルスケジュール部（図２の２０３）は記憶部（図２の２０２）からパラメータ値を読み込む際に、時計に回り込みが発生したが、このパラメータ値に対する修正が完了していない事を検出した場合は、読み込んだ値から上記の値を減算する。
また、記憶部に書き込む際には、時計に回り込みが発生したが、このパラメータ値に対する修正が完了していない事を検出した場合は、パラメータ値に、（時計部が計数できる現在時刻の最大値の値＋１）を加えて修正した値を書き込む。
【００３７】
セルスケジューリング方法の実現例から明らかな通り、パラメータ値が更新された際の更新値の最大値は、（現在時刻の最大値＋セルシェーピング装置が対応出来るセル間隔の最大値＋セルシェーピング装置が対応出来る許容されるセル遅延時間のゆらぎの値）となる。
従って、実際に書き込まれるパラメータ値の更新値の最大値は、（現在時刻の最大値＊２＋１＋セルシェーピング装置が対応出来るセル間隔の最大値＋セルシェーピング装置が対応出来る許容されるセル遅延時間のゆらぎの値）となる。
よって、時計部が計数出来る現在時刻のｂｉｔ長Ｎを、（セルシェーピング装置が対応出来るセル間隔の最大値＋セルシェーピング装置が対応出来る許容されるセル遅延時間のゆらぎの値）の値を表現できる最小のｂｉｔ長とした場合、パラメータ値は、（Ｎ＋２）ｂｉｔの符合なし整数値で実現する事が出来る。
この場合、パラメータ値が、時計部が計数できる現在時刻の最大値を越える場合、パラメータ値から、（時計部が計数できる現在時刻の最大値の値＋１）を減算する演算は、パラメータ値の上位２ｂｉｔが［１，１］の場合は、この上位２ｂｉｔを［１，０］とし、パラメータ値の上位２ｂｉｔが［１，０］の場合は、この上位２ｂｉｔを［０，１］とし、パラメータ値の上位２ｂｉｔが［０，１］の場合は、この上位２ｂｉｔを［０，０］とする演算と等価となる。
同様に、パラメータ値に、（時計部が計数できる現在時刻の最大値の値＋１）を加算する演算は、パラメータ値の上位２ｂｉｔが［１，０］の場合は、この上位２ｂｉｔを［１，１］とし、パラメータ値の上位２ｂｉｔが［０，１］の場合は、この上位２ｂｉｔを［１，０］とし、パラメータ値の上位２ｂｉｔが［０，０］の場合は、この上位２ｂｉｔを［０，１］とする演算と等価となる。
【００３８】
以上の前提に基づいて、時計部に回り込みが発生した際の動作例を、図１０のフローチャートに示す。
時計部に回り込みが発生した際に、更新された時刻に対応するコネクションのパラメータ値に対して、パラメータ値の上位２ｂｉｔが［０，０］の場合、パラメータ値を０とし、パラメータ値の上位２ｂｉｔが［０，１］の場合、この上位２ｂｉｔを［０，０］とし、パラメータ値の上位２ｂｉｔが［１，０］の場合、この上位２ｂｉｔを［０，１］とし、パラメータ値の上位２ｂｉｔが［１，１］の場合、この上位２ｂｉｔを［１，０］とする（ステップ１１０１）。
この動作によって、更新された時刻に対応するキューに対応するコネクションのパラメータ値が、時計部が計数できる現在時刻の最大値を越える場合は、パラメータ値から、（時計部が計数できる現在時刻の最大値＋１）の値を減算した値に該パラメータ値を更新し、時計部で計数できる現在時刻の最大値以下の値の場合は０に更新する。
前述の［作用］の欄に記載した通り、時計部が計数できる現在時刻の最大値以下の値を有するパラメータ値を０としてもシェーパの動作には支障は無い。
【００３９】
また、セルスケジュール部が記憶部からセルが所属するコネクションに対応したパラメータ値を読み込む際の動作例を、図１１のフローチャートに示す。
図１１のフローチャートは、図３、および図４に示したセルスケジューリング方法においてセルスケジュール部が記憶部から所属するコネクションに対応したパラメータ値を読み込む際に実行される。
このフローチャートでは、セルが所属するコネクションに対応したキューの識別子をＱＩＤとしている。
記憶部からセルが所属するコネクションに対応したパラメータ値を読み込む際に、このコネクションに対応したキューの識別子の値が現在時刻以下の場合は、時計の回り込みが発生した後に、このパラメータ値に対して更新ステップが実行されているため、パラメータ値をそのまま読み込む（ステップ１２０１のＮ）。コネクションに対応したキューの識別子の値が現在時刻より大きい場合は、時計の回り込みが発生した後に、このパラメータ値に対して更新ステップが実行されていないため、読み込んだパラメータ値の上位２ｂｉｔが［０，０］の場合、パラメータ値を０とし、上位２ｂｉｔが［０，１］の場合、この上位２ｂｉｔを［０，０］とし、上位２ｂｉｔが［１，０］の場合、この上位２ｂｉｔを［０，１］とし、上位２ｂｉｔが［１，１］の場合、この上位２ｂｉｔを［１，０］とする（ステップ１２０１のＹ、ステップ１２０２）。
この動作によって、パラメータ値を読み込む際に、時計の回り込みが発生した後に、パラメータ値に対して更新ステップが実行されていない状態であって、かつ、読み込んだパラメータ値が時計部が計数できる現在時刻の最大値を越える場合は、パラメータ値から、（時計部が計数できる現在時刻の最大値＋１）の値を減算し、時計部が計数できる現在時刻の最大値以下の場合は、パラメータ値を０とする。
【００４０】
セルスケジュール部が記憶部ヘセルが所属するコネクションに対応したパラメータ値の更新値を書き込む際の動作例を、図１２のフローチャートに示す。
図１２のフローチャートは、図４に示したセルスケジューリング方法においてセルスケジュール部が記憶部から所属するコネクションに対応したパラメータ値の更新値を書き込む際に実行される。
このフローチャートではセルが所属するコネクションに対応したキューの識別子をＱＩＤとしている。
記憶部からセルが所属するコネクションに対応したパラメータ値の更新値を書き込む際に、このコネクションに対応したキューの識別子の値が現在時刻以下の場合は、時計の回り込みが発生した後に、更新の対象となる記憶部のパラメータ値に対して更新ステップが実行されているため、パラメータ値をそのまま書き込む（ステップ１３０１のＮ）。
コネクションに対応したキューの識別子の値が現在時刻より大きい場合は、時計の回り込みが発生した後に、更新の対象となる記憶部のパラメータ値に対して更新ステップが実行されていないため、更新されたパラメータ値の上位２ｂｉｔが［０，０］の場合、この上位２ｂｉｔを［０，１］とし、上位２ｂｉｔが［０，１］の場合、この上位２ｂｉｔを［１，０］とし、上位２ｂｉｔが［１，０］の場合、この上位２ｂｉｔを［１，１］とした値を記憶部へ書き込む（ステップ１３０１のＹ、ステップ１３０２）。
この動作によって、パラメータ値の更新値を記憶部に書き込む際に、時計の回り込みが発生した後に、更新の対象となる記憶部のパラメータ値に対して、更新ステップが実行されていない状態の場合、パラメータの更新値に（時計部が計数できる現在時刻の最大値＋１）の値を加算した値を更新の対象となる記憶部のパラメータ値に書き込む。
【００４１】
次に、セル送信部に記憶されたセルの送信可能時刻、および優先度に対する修正方法を示す。
セルスケジューリング方法の実現例から明らかな通り、セルの送信可能時刻の最大値は、（現在時刻の最大値＋セルシェーピング装置が対応出来るセル間隔の最大値）、セルの優先度の最大値は、パラメータ値が更新された際の更新値の最大値と同じとなる。
従って、セルの送信可能時刻、優先度は、（Ｎ＋１）ｂｉｔの符合なし整数値で実現する事が出来る。
この場合、これらの値が時計部が計数できる現在時刻の最大値を越える場合、これらの値から、（時計部が計数できる現在時刻の最大値の値＋１）を減算する演算は、これらの値の最上位ｂｉｔが［１］の場合は、この最上位ｂｉｔを［０］とする演算と等価となる。
本発明のセルシェーピング装置のセルスケジューリング部は、セルがキューの先頭に達した際に、セルの送信可能時刻、および優先度を決定する。
【００４２】
そして、セル送信部は、これらの値が決定したセルから送信可能時刻順に、送信可能時刻が同一の場合は優先度順にセルを送信する。
従って、セルの送信可能時刻、優先度が決定してから、そのセルが実際に送信されるまでの時間は、最大でも、（セルシェーピング装置が備えるキューの数−１）セル時間となる。
一方、本発明では時計部が計数できる現在時刻の最大値は、セルシェーピング装置が備えるキューの数以上である。
従って、本発明では、セルの送信可能時刻、優先度が決定してから、そのセルが実際に送信されるまでの間は、時計の回り込みは最大でも１回しか発生しない。　従って、時計の回り込み回数をＭ＝１ｂｉｔの符合なし整数値で計数し、スケジュール部がセルの送信可能時刻、優先度を決定した際に、セル送信部がこれらの値に加えて時計の回り込み回数を記憶し、セル送信部がこれらの値を評価する際に、記憶した時計の回り込み回数と時計部が計数する現在時刻における時計の回り込み回数を比較して、値が同じであれば回り込み無し、値が異なれば回り込みが１回発生した事が特定できる。
【００４３】
セル送信部が記憶された送信可能時刻、優先度の値を評価する際の動作例を、図１３のフローチャートに示す。
図１３のフローチャートは、図７に示したシーケンサ方式によるセル送信部や、図８に示したヒープによる優先キューによるセル送信部における、配列構造や木構造に記憶された送信可能時刻や優先度を比較する際に実行される。
配列構造や木構造に記憶された送信可能時刻や優先度を比較する際に、これらの値と併せて記憶された時計の回り込み回数と、その時点での時計の回り込み回数を比較して、これらの値が同一であれば時計の回り込みは発生していないため、シーケンサやヒープによる優先キューは、記憶された送信可能時刻や優先度の値をそのまま使用する（ステップ１４０１のＹ）。
送信可能時刻や優先度と併せて記録された時計の回り込み回数と、その時点での時計の回り込み回数が異なる値の場合、時計の回り込みが発生しているため、シーケンサやヒープによる優先キューは、記憶された送信可能時刻や優先度の値の上位１ｂｉｔが［０］の場合は、これらの値を０とし、上位１ｂｉｔが［１］の場合は、上位１ｂｉｔを［０］とした値を送信可能時刻や優先度の値として使用する（ステップ１４０１のＮ、ステップ１４０２）。
【００４４】
この動作によって、送信可能時刻、および該優先度と併せて記録された時計の回り込み回数と、時計部に記憶された時計の回り込み回数を比較して、送信可能時刻、および優先度の決定以降に発生した時計の回り込み回数を特定し、特定された回り込み回数が１回であって、かつ、送信可能時刻、および優先度が、各々時計部が計数できる現在時刻の最大値を越える値の場合、送信可能時刻、および優先度から各々、（時計部が計数できる現在時刻の最大値＋１）の値を減算した値に、送信可能時刻、および優先度を各々変換し、特定された回り込み回数が１回であって、かつ、送信可能時刻、および優先度が、各々時計部が計数できる現在時刻の最大値以下の場合、送信可能時刻、優先度を各々０に変換する。
尚、本発明は、セル遅延時間のゆらぎの値を、０もしくは定数等の固定的な値に置き換えた場合を包含している事は自明である。また、本発明は、特願２００１−２２７２６８号の請求項２に示されたセルスケジューリング方法と組み合わせる事が出来る事は自明である。
以上、本発明者によってなされた発明を、前記実施の形態に基づき具体的に説明したが、本発明は、前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは勿論である。
【００４５】
【発明の効果】
本願において開示される発明のうち代表的なものによって得られる効果を簡単に説明すれば、下記の通りである。
本発明によれば、送信可能時刻、優先度、および送信可能時刻が決定されたセルを特定する情報等を対で記憶する方式に基づくセル送信部を有するＧＣＲＡ方式によるシェーパにおいて、時計に回り込みが発生しても、シェーパに記憶された時刻に依存した値を正しい値に更新したり、変換するセルスケジューリング方法を提供する事が出来るため、シェーパの動作に誤りが発生しない利点がある。更に、本願の請求項３、４に係わる発明は、シェーパに記憶された時刻に依存した値を分散して更新し、必要に応じて値を正しい値に変換するため、シェーパがサポートするコネクション数が多い場合であっても、本願の請求項１、２に係わる発明と等価なシェーパを実用的に提供出来る利点がある。
【図面の簡単な説明】
【図１】従来のトークン方式によるセルシェーピング装置の実現例の概略構成を示すブロック図である。
【図２】従来のＧＣＲＡ方式によるセルシェーピング装置の実現例の概略構成を示すブロック図である。
【図３】従来のＧＣＲＡ方式によるセルシェーピング装置の実現例のセルスケジューリング部におけるセルスケジューリング方法の実現例を示すフローチャートである。
【図４】従来のＧＣＲＡ方式によるセルシェーピング装置の実現例のセルスケジューリング部におけるセルスケジューリング方法の実現例を示すフローチャートである。
【図５】従来のＧＣＲＡ方式によるセルシェーピング装置の実現例における、リングバッファ方式によるセル送信部の実現例の概略構成を示すブロック図である。
【図６】従来のＧＣＲＡ方式によるセルシェーピング装置の実現例における、カレンダ方式によるセル送信部の実現例の概略構成を示すブロック図である。
【図７】従来のＧＣＲＡ方式によるセルシェーピング装置の実現例における、シーケンサ方式によるセル送信部の実現例の概略構成を示すブロック図である。
【図８】ヒープによる優先キューによるデータ構造を説明するための図である。
【図９】時計部に回り込みが発生した場合における、本発明の実施の形態１のセルスケジューリング方法を説明するためのフローチャートである。
【図１０】時計部に回り込みが発生した場合における、本発明の実施の形態２のセルスケジューリング方法を説明するためのフローチャートである。
【図１１】時計部に回り込みが発生した場合でパラメータ値を読み込む際における、本発明の実施の形態２のセルスケジューリング方法を説明するためのフローチャートである。
【図１２】時計部に回り込みが発生した場合でパラメータ値の更新値を書き込む際における、本発明の実施の形態２のセルスケジューリング方法を説明するためのフローチャートである。
【図１３】時計部に回り込みが発生した場合で送信可能時刻、優先度の値を評価する際における、本発明の実施の形態２のセルスケジューリング方法を説明するためのフローチャートである。
【符号の説明】
１０１，２０７…入力部、１０２，１０３、２０５，２０６、８０１，８０２，８０６…キュー、１０４，１０５…送信タイミング生成部、１０６…調停部、２０１…記憶部、２０２…時計部、２０３…セルスケジューリング部、２０４…セル送信部、６０１…現在時刻に対応するバッファを示すポインタ、６０２，６０３，６０４…キューの先頭のセルヘのポインタを格納するバッファ、７０１…現在時刻に対応するリストを示すポインタ、７０２，７０３，７０４…各々キューの先頭のセルヘのポインタを格納するリスト、７０５…リスト１の後尾の要素、７０６…リスト１の先頭の要素、７０７…送信リスト、８０３…キューの先頭のセルへのポインタ、８０４…キューの先頭のセルのタイムスロット値、８０５…ポインタとタイムスロット値を要素とする配列構造、８０７…キューの先頭に達したセルヘのポインタ、８０８…キューの先頭に達したセルのタイムスロット値、８０９…ブロードキャストバス。
【図１】
2004023609.tif 000003
【図２】
2004023609.tif 000004
【図３】
2004023609.tif 000005
【図４】
2004023609.tif 000006
【図５】
2004023609.tif 000007
【図６】
2004023609.tif 000008
【図７】
2004023609.tif 000009
【図８】
2004023609.tif 000010
【図９】
2004023609.tif 000011
【図１０】
2004023609.tif 000012
【図１１】
2004023609.tif 000013
【図１２】
2004023609.tif 000014
【図１３】
2004023609.tif 000015