(57)【特許請求の範囲】
【請求項１】
コネクション毎のトラヒック特性値、及びパラメータ値を記憶する記憶部と、
現在時刻を計数する時計部と、
到着したセルが所属するコネクションに対応した前記トラヒック特性値、前記パラメータ値、及び前記時計部が計数する現在時刻に基づいて、当該セルの送信可能時刻を決定し、前記パラメータの更新を行うセルスケジューリング部と、
前記セルスケジューリング部によって送信可能時刻が決定されたセルから、前記送信可能時刻が最も早く、かつ優先度が最も高いセルを特定し、前記送信可能時刻が前記時計部が計数する現在時刻より以前の場合、当該セルを回線に送信するセル送信部とを備えるセルシェーピング装置において、
前記セルスケジューリング部は、前記セルの送信可能時刻を決定する際に使用したパラメータ値を当該セルの優先度として前記セル送信部に出力する手段を有することを特徴とするセルシェーピング装置。
【請求項２】
コネクション毎のトラヒック特性値、及びパラメータ値を記憶する記憶部と、
現在時刻を計数する時計部と、
到着したセルが所属するコネクションに対応した前記トラヒック特性値、前記パラメータ値、及び前記時計部が計数する現在時刻に基づいて、当該セルの送信可能時刻を決定し、前記パラメータの更新を行うセルスケジューリング部と、
前記セルスケジューリング部によって送信可能時刻が決定されたセルから、前記送信可能時刻が最も早く、かつ優先度が最も高いセルを特定し、前記送信可能時刻が前記時計部が計数する現在時刻より以前の場合、当該セルを回線に送信するセル送信部とを備えるセルシェーピング装置において、
前記コネクション毎のトラヒック特性値として、少なくともセル遅延時間のゆらぎの値が用いられ、
前記セルスケジューリング部は、セルの送信可能時刻を決定する際に使用したパラメータ値及びセル遅延時間のゆらぎの値に起因する値を、当該セルの優先度として前記セル送信部に出力する手段を有することを特徴とするセルシェーピング装置。
【請求項３】
前記セル送信部は、前記送信可能時刻が最も早く、かつ優先度が最も高いセルを特定する際に、ヒープによる優先キューによって、当該セルを特定する手段を有することを特徴とする請求項１または請求項２に記載のセルシェーピング装置。
【請求項４】
コネクション毎のトラヒック特性値、及びパラメータ値を記憶する記憶部と、
現在時刻を計数する時計部と、
到着したセルが所属するコネクションに対応した前記トラヒック特性値、前記パラメータ値、及び前記時計部が計数する現在時刻に基づいて、当該セルの送信可能時刻を決定し、前記パラメータの更新を行うセルスケジューリング部と、
前記セルスケジューリング部によって送信可能時刻が決定されたセルであって、前記送信可能時刻が前記時計部が計数する現在時刻より以前となるセルから、優先度が最も高いセルを特定し、当該セルを回線に送信するセル送信部とを備えるセルシェーピング装置において、
前記セルスケジューリング部は、セルの送信可能時刻を決定する際に使用したパラメータ値を、当該セルの優先度として前記セル送信部に出力する手段を有することを特徴とするセルシェーピング装置。
【請求項５】
コネクション毎のトラヒック特性値、及びパラメータ値を記憶する記憶部と、
現在時刻を計数する時計部と、
到着したセルが所属するコネクションに対応した前記トラヒック特性値、前記パラメータ値、及び前記時計部が計数する現在時刻に基づいて、当該セルの送信可能時刻を決定し、前記パラメータの更新を行うセルスケジューリング部と、
前記セルスケジューリング部によって送信可能時刻が決定されたセルであって、前記送信可能時刻が時計部が計数する現在時刻より以前となるセルから、優先度が最も高いセルを特定し、当該セルを回線に送信するセル送信部とを備えるセルシェーピング装置において、
前記コネクション毎のトラヒック特性値として、少なくともセル遅延時間のゆらぎの値が用いられ、
前記セルスケジューリング部は、セルの送信可能時刻を決定する際に使用したパラメータ値及びセル遅延時間のゆらぎの値に起因する値を、当該セルの優先度として前記セル送信部に出力する手段を有することを特徴とするセルシェーピング装置。
【請求項６】
前記セル送信部は、前記送信可能時刻が前記時計部が計数する現在時刻より以前となるセルから、優先度が最も高いセルを特定する際に、ヒープによる優先キューによって該セルを特定する手段を有することを特徴とする請求項４または請求項５に記載のセルシェーピング装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ＡＴＭ（Asynchronous Transfer Mode）セル等の固定長パケット（以下、「セル」と記載する）に対するセルシェーピング装置に係わるものであり、特に、ＧＣＲＡ（Generic Cell Rate Algorithm）方式で実現されるセルシェーピング装置に適用して有効な技術に関する。
【０００２】
【従来の技術】
セルシェーピング装置（以下、シェーパと呼ぶ）とは、コネクション毎に定められたトラヒック特性値に適合する様に、必要に応じてセルに遅延時間を付与する装置のことである。
従来の、このシェーパの実現方式には、原理的に異なる２つの方式が存在し、一つはトークン方式、もう一つはＧＣＲＡ方式である。
従来のトークン方式のシェーパの実現例を図１に示す。
図１は、従来のトークン方式のシェーパの実現例の概略構成を示すブロック図であり、図１において、１０１は入力部、１０２，１０３はキュー、１０４，１０５は送信タイミング生成部、１０６は調停部である。
図１に示すシェーパの動作を説明する。
シェーパに到着したセルは、入力部１０１によってセルが所属するコネクションに対応したキュー（１０２，１０３）に格納される。
ここで、コネクションとは、セルヘッダ含まれる仮想パス識別子（ＶＰＩ；Virtual Path Identifire、以下、単に、ＶＰＩという）、および仮想チャネル識別子（ＶＣＩ；Virtual Channel Identifire、以下、単に、ＶＣＩという）フィールドの一部、あるいは全部によって識別される仮想的なパスやチヤネルを意味する。
【０００３】
キュー（１０２，１０３）は、先頭から到着順にセルを格納するもので、コネクション対応に存在する。
送信タイミング生成部（１０４，１０５）は、キュー（１０２，１０３）の先頭のセルが送信可能となった事を示すタイミング信号を生成するもので、コネクションに対応したキュー毎に存在する。
特許第３２３２０３６号明細書や、特許第３１０９４９１号明細書に示される通り、送信タイミング生成部（１０４，１０５）は、コネクション毎のトラヒック特性値に応じて、クロック信号を分周する事によってタイミング信号を生成する方式で実現できる。
調停部１０６は、セルが送信可能となった事を示すタイミング信号が生成されたキューの先頭から、セルを取り出して回線に送信する。
この際に、セルが送信可能となったキューが複数存在する場合、調停部１０６は、キュー間に予め設定された固定優先度、ラウンドロビン、ランダムやこれらの組み合わせ等の調停規則に基づいてセルを取り出すキューを選択する。
この様な、従来のトークン方式によるシェーパの調停部１０６の実現例は、特開２００１−２３０７７８号公報にも示されている。
【０００４】
従来のＧＣＲＡ方式によるシェーパの第１の実現例を図２に示す。
図２は、従来のＧＣＲＡ方式によるシェーパの第１の実現例の概略構成を示すブロック図であり、図２において、２０１はコネクション毎のトラヒック特性値、パラメータ値を記憶する記憶部、２０２は時計部、２０３はセルスケジューリング部、２０４はセル送信部である。
以下、図２に示すシェーパの動作を説明する。
記憶部２０１は、コネクションの識別子の値でアドレッシングされる配列で構成される。ここで、コネクションとはセルヘッダに含まれるＶＰＩ及びＶＣＩフィールドの一部、あるいは全部によって識別される仮想的なパスやチャネルを意味する。
図２に示すように、セルがシェーパに到着した際に、到着したセルのコネクションに対応したトラヒック特性値、パラメータ値が、記憶部２０１からセルスケジューリング部２０３に入力される。
セルスケジューリング部２０３は、入力されたトラヒック特性値、パラメータ値、及び時計部２０２が計数する現在時刻に基づいて、到着したセルの送信可能時刻を決定してセル送信部２０４に出力する。
同時に、セルスケジューリング部２０３は、パラメータ値の更新値を決定して、これを記憶部２０１に出力し、記憶されているパラメータ値を更新する。
セル送信部２０４はシェーパにセルが到着した際に、到着したセルとセルスケジューリング部２０３によって決定したセルの送信可能時刻を対で記憶する。
セル送信部２０４のセル送信に関する詳細な動作は以下で説明する。
【０００５】
図２に示すＧＣＲＡ方式によるシェーパのセルスケジューリング部２０３におけるセルスケジューリング方法の第１の実現例を、「Kan Toyoshima, "CDV Reduction Shaping Algorithm in ATM Networks," IEICE Trans.Commun.,Vol. E79-B, No.4,Apr.1996.」に基づいて説明する。
図３は、前述の文献に記載された、図２に示すセルスケジューリング部２０３のセルスケジューリング方法の第１の実現例を示すフローチャートである。
このフローチャートでは、トラヒック特性値としてセル間隔の値と許容されるセル遅延時間のゆらぎを用い、セルの送信可能時刻を計算する際の現在時刻をｔａ、セルが所属するコネクションに対応したトラヒック特性値のセル間隔の値をｔ、許容されるセル遅延時間のゆらぎの値をτ、セルが所属するコネクションに対応したパラメータ値をＴＥＴ、セルの送信可能時刻をｔｓとしている。
セルがシェーパに到着した際に、このセルが所属するコネクションに対応したトラヒック特性値であるセル間隔の値ｔと許容されるセル遅延時間のゆらぎτ、パラメータ値ＴＥＴが、記憶部２０１からセルスケジューリング部２０３に入力される。
【０００６】
セルスケジューリング部２０３は、入力されたセル間隔の値ｔ、許容されるセル遅延時間のゆらぎτ、パラメータ値ＴＥＴ、及び時計部が２０２が計数する現在時刻ｔａに基づいて、図３のフローチャートに示された動作を開始する。
ｔａ≦ＴＥＴの関係が成立する場合は、セルの送信可能時刻ｔｓをＴＥＴとし、パラメータの値ＴＥＴを（ＴＥＴ＋ｔ）に更新する（ステップ３０１、３０３、３０６）。
ｔａ＞ＴＥＴの関係が成立する場合は、セルの送信可能時刻ｔｓをｔａとする（ステップ３０１、３０２）。
この場合、ｔａ≦（ＴＥＴ＋τ）の関係が成立する場合は、パラメータの値ＴＥＴを（ＴＥＴ＋ｔ）に更新する（ステップ３０４、３０６）。
ｔａ＞（ＴＥＴ＋τ）の関係が成立する場合は、パラメータの値ＴＥＴを（ｔａ−τ＋ｔ）に更新する（ステップ３０４、３０５、３０６）。
決定したセルの送信可能時刻ｔｓは、セル送信部２０４に出力される。また、更新されたパラメータの値ＴＥＴは、記憶部２０１に出力され、記憶されているパラメータ値が更新される。
【０００７】
図２に示すＧＣＲＡ方式によるシェーパのセルスケジューリング部２０３におけるセルスケジューリング方法の第２の実現例を図４に示す。
図４は、図２に示すＧＣＲＡ方式によるシェーパにおける、セルスケジューリング部２０３のセルスケジューリング方法の第２の実現例を示すフローチャートである。
図４に示すフローチャートでは、トラヒック特性値としてセル間隔の値と許容されるセル遅延時間のゆらぎを用い、セルの送信可能時刻を計算する際の現在時刻をｔａ、セルが所属するコネクションに対応したトラヒック特性値のセル間隔の値をｔ、許容されるセル遅延時間のゆらぎの値をτ、セルが所属するコネクションに対応したパラメータ値をＴＡＴ、セルの送信可能時刻をｔｓとしている。
セルがシェーパに到着した際に、このセルが所属するコネクションに対応したトラヒック特性値であるセル間隔の値ｔと、許容されるセル遅延時間のゆらぎτ、パラメータ値ＴＡＴが、記憶部２０１からセルスケジューリング部２０３に入力される。
セルスケジューリング部２０３は、入力されたセル間隔の値ｔ、許容されるセル遅延時間のゆらぎτ、パラメータ値ＴＡＴ、及び時計部が２０２が計数する現在時刻ｔａに基づいて、図４のフローチャートに示された動作を開始する。
【０００８】
ｔａ＜（ＴＡＴ−τ）の関係が成立する場合は、セルの送信可能時刻ｔｓを（ＴＡＴ−τ）とする（ステップ４０１、４０３）。
（ＴＡＴ−τ）≦ｔａの関係が成立する場合は、セルの送信可能時刻ｔｓをｔａとする（ステップ４０１、４０２）。
そして、ｔａ＜ＴＡＴの関係が成立する場合は、パラメータの値ＴＡＴを（ＴＡＴ＋ｔ）に更新する（ステップ４０４、４０６）。
ＴＡＴ≦ｔａの関係が成立する場合は、パラメータの値ＴＡＴを（ｔａ＋ｔ）に更新する（ステップ４０４、４０５）。
決定したセルの送信可能時刻ｔｓは、セル送信部２０４に出力される。また、更新されたパラメータの値ＴＡＴは、記憶部２０１に出力され、記憶されているパラメータ値が更新される。
以上から明らかな通り、図３と図４に示されたセルスケジューリング方法は、理論的には等価なスケジューリング方法である。
【０００９】
図２に示す従来のＧＣＲＡ方式によるシェーパのセル送信部２０４の第１の実現例を、「Jonathan Chao,“A General Architecture for Link-Layer Congestion Control in ATM Networks,”ISS 1992,Oct. 1992.」に基づいて説明する。
図５は、図２に示すシェーパのセル送信部２０４の第１の実現例の概略構成を示すブロック図である。この図５に示すセル送信部２０４は、一般にシーケンサ方式と呼ばれる。
５０１，５０２はセルを格納するバッファ、５０３はセルを格納するバッファヘのポインタ、５０４はセルのタイムスロット値、５０５はポインタとタイムスロット値を要素とする配列構造、５０６は到着したセルを格納するバッファ、５０７は到着したセルを格納するバッファヘのポインタ、５０８は到着したセルのタイムスロット値、５０９はブロードキャストバスである。
図５に示すセル送信部２０４は、回線上で数セルの転送に要する時間を（ＳＴＭ−１／ＳＴＳ−３ｃ回線で約２．８μ秒）１タイムスロットとし、図５に示すように、送信可能時刻の決定したセルをバッファに格納し、セルを格納するバッファヘのポインタ５０３と、そのセルのタイムスロット値５０４から成る要素をタイムスロット値の順にソートする方式である。
ここで、セルが所属するコネクション、キュー、ＣＢＲ（Constant Bit Rate；固定伝送速度）、nrt-ＶＢＲ（Non-Real-Time Variable Bit Rate；非実時間可変速度）等のトラヒッククラス間などに予め優先度が設定されているものとし、優先度は値が小さいほど優先度が高いものとする。
【００１０】
シーケンサは、主にポインタとタイムスロット値を要素とする配列構造で構成され、図５に示すセル送信部では、右側からタイムスロット値の順に要素がソートされている。
具体的には、図５において、ポインタとタイムスロット値を要素とする配列構造５０５の各要素は隣の要素にシフトする事が可能な構造となっている。
シーケンサは、シェーパにセルが到着した際に、到着したセルを格納するバッファ５０６にセルを格納し、このバッファを示す様に到着したセルを格納するバッファへのポインタ５０７を設定し、｛セルスケジューリング部２０３によって決定したセルの送信可能時刻＊（優先度の最大値＋１）＋セルの優先度｝の値を５０８の到着したセルのタイムスロット値に設定する事によって、到着したセルとタイムスロット値を対で記憶する。
次に、シーケンサは、到着したセルのタイムスロット値５０８を、ブロードキャストバス５０９を用いてポインタとタイムスロット値を要素とする配列構造５０５内の各要素のタイムスロット値と並列に比較し、配列構造５０５内の各要素のタイムスロット値が、到着したセルのタイムスロット値以上となる最初の要素の位置を挿入位置として、それ以上の全ての要素を左側にシフトし、到着したセルを格納するバッファへのポインタ５０７と到着したセルのタイムスロット値５０８を挿入位置に格納する事によって、要素をタイムスロット値の順にソートする。
シーケンサは、配列構造５０５の最も右の要素のタイムスロット値に含まれるセルの送信可能時刻と、時計部２０２が計数する時刻を比較し、前者の値が後者の値以前となる場合は、最も右の要素のポインタが示すバッファに格納されたセルを回線に送信し、最も右の要素を配列構造５０５から削除し、残りの要素を右側にシフトする事によって、シーケンサに格納されているセルの中から送信可能時刻が最も早く、かつ優先度が最も高いセルを特定し、特定された送信可能時刻が現在時刻より以前の場合、そのセルを回線に送信する。
【００１１】
図２に示す従来のＧＣＲＡ方式によるシェーパのセル送信部２０４の第２の実現例を、「Jonathan Chao,“A General Architecture for Link-Layer Congestion Control in ATM Networks,”ISS 1992,Oct. 1992.」に基づいて説明する。
この実現例では、前記図５に示すセル送信部２０４のシーケンサを直列に２段接続する事によって、セルが所属するコネクション、キュー、トラヒッククラス間などに予め設定された固定優先度に基づいて、送信可能時刻が現在時刻以前となるセルから、最も優先度が高いセルを送信するセルとして特定する。
１段目のシーケンサは、前記図５に示すセル送信部のシーケンサのタイムスロット値を、セルスケジューリング部２０３によって決定したセルの送信可能時刻に設定する。
また、２段目のシーケンサは、前記図５に示すセル送信部２０４のシーケンサのタイムスロット値を、セルの優先度に設定する。
１段目のシーケンサは、配列構造の最も右の要素のタイムスロット値のセルの送信可能時刻と、時計部２０２が計数する時刻を比較し、前者の値が後者の値以前となる場合は、最も右の要素のポインタ及び、ポインタが示すバッファに格納されたセルの優先度を、２段目のシーケンサの、到着したセルを格納するバッファへのポインタ、及び到着したセルのタイムスロット値に各々設定し、最も右の要素を配列構造から削除し、残りの要素を右側にシフトする。
２段目のシーケンサは、配列構造の最も右の要素のポインタが示すバッファに格納されたセルを回線に送信し、最も右の要素を配列構造から削除し、残りの要素を右側にシフトする事によって、送信可能時刻が現在時刻以前となるセルから、最も優先度が高いセルを送信するセルとして特定して、そのセルを回線に送信する。
【００１２】
従来のＧＣＲＡ方式によるシェーパの第２の実現例を特開２００１−２７４７９５号公報に基づいて説明する。
図６は、従来のＧＣＲＡ方式によるシェーパの第２の実現例の概略構成を示すブロック図であり、図６に示すシェーパは、前記の文献（特開２００１−２７４７９５号公報）に記載されたセルシェーピング装置である。
図６において、６０１はトラヒック特性値、パラメータ値を記憶する記憶部、６０２は時計部、６０３はセルスケジューリング部、６０４はセル送信部、６０５，６０６はキュー、６０７は入力部である。
図６に示すシェーパの動作を説明する。
記憶部６０１はコネクションの識別子の値でアドレッシングされる配列で構成される。ここで、コネクションとはセルヘッダに含まれるＶＰＩ及びＶＣＩフィールドの一部、あるいは全部によって識別される仮想的なパスやチャネルを意味する。
図６に示す様に、シェーパに到着したセルは、入力部６０７によってセルが所属するコネクションに対応したキュー（６０５，６０６）に格納される。キュー（６０５，６０６）は、先頭から到着順にセルを格納するもので、コネクション対応に存在する。
【００１３】
セルがキュー（６０５，６０６）の先頭に達した際に、キュー（６０５，６０６）の先頭に達したセルのコネクションに対応したトラヒック特性値、パラメータ値が記憶部６０１から、セルスケジューリング部６０３に入力される。
セルスケジューリング部６０３は、入力されたトラヒック特性値、パラメータ値、及び時計部６０２が計数する現在時刻に基づいて、キュー（６０５，６０６）の先頭に達したセルの送信可能時刻を決定してセル送信部６０４に出力する。
セル送信部６０４は、キュー（６０５，６０６）の先頭のセルへのポインタ情報とセルスケジューリング部６０３によって決定したセルの送信可能時刻を対で記憶する。
セル送信部６０４のセル送信に関する詳細な動作は後述する。
セルを回線に送信する際に、送信するセルのコネクションに対応したコネクション毎のトラヒック特性値、パラメータ値が記憶部６０１からセルスケジューリング部６０３に入力される。
セルスケジューリング部６０３は、入力されたトラヒック特性値、パラメータ値、及び時計部６０２が計数する現在時刻に基づいて、パラメータ値の更新値を決定して、記憶部６０１に出力し、記憶されているパラメータ値を更新する。
【００１４】
図６に示す従来のＧＣＲＡ方式によるシェーパにおける、セルスケジューリング部６０３のセルスケジューリング方法の第１の実現例を、図７、図８に示す。
図７、図８は、図６に示すＧＣＲＡ方式によるシェーパにおける、セルスケジューリング部６０３のセルスケジューリング方法の第１の実現例を示すフローチャートである。
このフローチャートでは、トラヒック特性値として、セル間隔の値と許容されるセル遅延時間のゆらぎを用い、セルの送信可能時刻を計算する際の現在時刻をｔａ、パラメータ値を更新する際の現在時刻をｔｅ、セルが所属するコネクションに対応したトラヒック特性値のセル間隔の値をｔ、許容されるセル遅延時間のゆらぎの値をτ、セルが所属するコネクションに対応したパラメータ値をＴＥＴ、セルの送信可能時刻をｔｓとしている。
セルがキュー（６０５，６０６）の先頭に達した際に、キュー（６０５，６０６）の先頭に達したセルのコネクションに対応したパラメータ値ＴＥＴが、記憶部６０１からセルスケジューリング部６０３に入力される。
セルスケジューリング部６０３は、入力されたパラメータ値ＴＥＴ、及び時計部６０２が計数する現在時刻ｔａに基づいて、図７のフローチャートに示された動作を開始する。
【００１５】
ｔａ≦ＴＥＴの関係が成立する場合は、セルの送信可能時刻ｔｓをＴＥＴとする（ステップ７０１、７０３）。
ＴＥＴ＜ｔａの関係が成立する場合は、セルの送信可能時刻ｔｓをｔａとする（ステップ７０１，７０２）。
決定したセルの送信可能時刻ｔｓは、セル送信部６０４に出力される。
セルが回線に送信される際に、キュー（６０５，６０６）の先頭に達したセルのコネクションに対応したトラヒック特性値であるセル間隔の値ｔと許容されるセル遅延時間のゆらぎτ、パラメータ値ＴＥＴが、記憶部６０１からセルスケジューリング部６０３に入力される。
セルスケジューリング部６０３は、入力されたセル間隔の値ｔ、許容されるセル遅延時間のゆらぎτ、パラメータ値ＴＥＴ、及び時計部６０２が計数する現在時刻ｔｅに基づいて、図８のフローチャートに示された動作を開始する。
ｔｅ≦（ＴＥＴ＋τ）の関係が成立する場合は、パラメータの値ＴＥＴを（ＴＥＴ＋ｔ）に更新する（ステップ８０１、８０３）。
（ＴＥＴ＋τ）＜ｔｅの関係が成立する場合は、パラメータの値ＴＥＴを（ｔｅ−τ＋ｔ）に更新する（ステップ８０１、８０２）。
決定したパラメータ値の更新値ＴＥＴは、記憶部６０１に出力され、記憶されているパラメータ値が更新される。
【００１６】
図６に示す従来のＧＣＲＡ方式によるシェーパにおける、セルスケジューリング部６０３のセルスケジューリング方法の第２の実現例を、図９、図１０に示す。
図９、図１０は、図６に示すＧＣＲＡ方式によるシェーパにおける、セルスケジューリング部６０３のセルスケジューリング方法の第２の実現例を示すフローチャートである。
このフローチャートでは、トラヒック特性値としてセル間隔の値と許容されるセル遅延時間のゆらぎを用い、セルの送信可能時刻を計算する際の現在時刻をｔａ、パラメータ値を更新する際の現在時刻をｔｅ、セルが所属するコネクションに対応したトラヒック特性値のセル間隔の値をｔ、許容されるセル遅延時間のゆらぎの値をτ、セルが所属するコネクションに対応したパラメータ値をＴＡＴ、セルの送信可能時刻をｔｓとしている。
セルがキュー（６０５，６０６）の先頭に達した際に、キュー（６０５，６０６）の先頭に達したセルのコネクションに対応したトラヒック特性値である許容されるセル遅延時間のゆらぎτ、パラメータ値ＴＡＴが、記憶部６０１からセルスケジューリング部６０３に入力される。
セルスケジューリング部６０３は、入力された許容されるセル遅延時間のゆらぎτ、パラメータ値ＴＡＴ、及び時計部６０２が計数する現在時刻ｔａに基づいて、図９のフローチャートに示された動作を開始する。
【００１７】
ｔａ＜（ＴＡＴ−τ）の関係が成立する場合は、セルの送信可能時刻ｔｓを（ＴＡＴ−τ）とする（ステップ９０１、９０３）。
（ＴＡＴ−τ）≦ｔａの関係が成立する場合は、セルの送信可能時刻ｔｓをｔａとする（ステップ９０１、９０２）。
決定したセルの送信可能時刻ｔｓは、セル送信部６０４に出力される。
セルが回線に送信される際に、キュー（６０５，６０６）の先頭に達したセルのコネクションに対応したトラヒック特性値であるセル間隔の値ｔとパラメータ値ＴＡＴが、記憶部６０１からセルスケジューリング部６０３に入力される。
セルスケジューリング部６０３は、入力されたセル間隔の値ｔ、パラメータ値ＴＡＴ、及び時計部６０２が計数する現在時刻ｔｅに基づいて、図１０のフローチャートに示された動作を開始する。
ｔｅ＜ＴＡＴの関係が成立する場合は、パラメータの値ＴＡＴを（ＴＡＴ＋ｔ）に更新する（ステップ１００１、１００３）。
ＴＡＴ≦ｔｅの関係が成立する場合は、パラメータの値ＴＡＴを（ｔｅ＋ｔ）に更新する（ステップ１００１、１００２）。
決定したパラメータ値の更新値ＴＡＴは記憶部６０１に出力され、記憶されているパラメータ値が更新される。
以上の説明から明らかな通り、図７、図８と、図９、図１０に示されたセルスケジューリング方法は、理論的には等価なスケジューリング方法である。
【００１８】
図６に示す従来のＧＣＲＡ方式によるシェーパにおける、セル送信部６０４の第１の実現例を、特開２００１−２７４７９５号公報に基づいて説明する。
図１１は、図６に示すシェーパのセル送信部６０４の第１の実現例を示すブロック図である。
図１１に示すセル送信部６０４は、前述の図５に示すシーケンサ方式によるセル送信部において、セルを格納するバッファへのポインタをキューの先頭のセルへのポインタとしたものである。
図１１において、１１０１，１１０２はキュー、１１０３はキューの先頭のセルヘのポインタ、１１０４はキューの先頭のセルのタイムスロット値、１１０５はポインタとタイムスロット値を要素とする配列構造、１１０６はキュー、１１０７はキューの先頭に達したセルヘのポインタ、１１０８はキューの先頭に達したセルのタイムスロット値、１１０９はブロードキャストバスである。
図１１示すセル送信部は、回線上で１セルの転送に要する時間を１タイムスロットとし、図１１に示す様に、送信可能時刻が決定したキューの先頭のセルへのポインタと、そのセルのタイムスロット値から成る要素をタイムスロット値の順にソートする方式である。
ここで、セルが所属するコネクション、キュー、ＣＢＲ、nrt-ＶＢＲ等のトラヒッククラス間などに予め優先度が設定されているものとし、優先度は値が小さいほど優先度が高いものとする。
シーケンサは主にポインタとタイムスロット値を要素とする配列構造で構成され、図１１の実現例では右側からタイムスロット値の順に要素がソートされている。
具体的には、図１１において、ポインタとタイムスロット値を要素とする配列構造１１０５の各要素は隣の要素にシフトする事が可能な構造となっている。
【００１９】
図１１に示すセル送信部は、セルがキュー１１０６の先頭に達した際に、このキューの先頭を示す様にキューの先頭に達したセルヘのポインタ１１０７を設定し、｛セルスケジューリング部６０３によって決定したセルの送信可能時刻＊（優先度の最大値＋１）＋セルの優先度｝の値を１１０８のキューの先頭に達したセルのタイムスロット値に設定する事によって、キューの先頭のセルヘのポインタとタイムスロット値を対で記憶する。
次に、キューの先頭に達したセルのタイムスロット値１１０８を、ブロードキャストバス１１０９を用いてポインタとタイムスロット値を要素とする配列構造１１０５内の各要素のタイムスロット値と並列に比較し、配列構造１１０５内の各要素のタイムスロット値が、キューの先頭に達したセルのタイムスロット値１１０８以上となる最初の要素の位置を挿入位置として、それ以上の全ての要素を左側にシフトし、キューの先頭に達したセルヘのポインタ１１０７とキューの先頭に達したセルのタイムスロット値１１０８を挿入位置に格納する事によって、要素をタイムスロット値の順にソートする。
図１１に示すセル送信部は、配列構造１１０５の最も右の要素のタイムスロット値に含まれるセルの送信可能時刻と、時計部６０２が計数する時刻を比較し、前者の値が後者の値以前となる場合は、最も右の要素のポインタが示すキューの先頭に格納されたセルを回線に送信し、最も右の要素を配列構造１１０５から削除し、残りの要素を右側にシフトする事によって、格納されているセルヘのポインタの中から送信可能時刻が最も早く、かつ、優先度が最も高いセルのポインタ情報を特定して、特定された送信可能時刻が現在時刻より以前の場合、そのセルを回線に送信する。
【００２０】
図６に示す従来のＧＣＲＡ方式によるシェーパにおける、セル送信部６０４の第２の実現例について説明する。
この実現例では、前記図１１に示すセル送信部のシーケンサを直列に２段接続する事によって、セルが所属するコネクション、キュー、トラヒッククラス間などに予め設定された固定優先度に基づいて、送信可能時刻が現在時刻以前となるセルから、最も優先度が高いセルを送信するセルとして特定する。
１段目のシーケンサは、前記図１１に示すセル送信部のシーケンサのタイムスロット値を、セルスケジューリング部６０３によって決定したセルの送信可能時刻に設定する。
また、２段目のシーケンサは、前記図１１に示すセル送信部のシーケンサのタイムスロット値を、セルの優先度に設定する。
１段目のシーケンサは、配列構造の最も右の要素のタイムスロット値のセルの送信可能時刻と、時計部６０２が計数する時刻を比較し、前者の値が後者の値以前となる場合は、最も右の要素のポインタ及び、ポインタが示すキューの先頭に格納されたセルの優先度を、２段目のシーケンサの、キューの先頭に達したセルヘのポインタ、及びキューの先頭に達したセルのタイムスロット値に各々設定し、最も右の要素を配列構造から削除し、残りの要素を右側にシフトする。
２段目のシーケンサは、配列構造の最も右の要素のポインタが示すキューの先頭に格納されたセルを回線に送信し、最も右の要素を配列構造から削除し、残りの要素を右側にシフトする事によって、送信可能時刻が現在時刻以前となるセルから、最も優先度が高いセルを送信するセルとして特定して、そのセルを回線に送信する。
【００２１】
また、特開平９−３０７５６６号公報には、コネクション毎に固定的な優先度を設定し、送信可能時刻が最も早く、かつ、優先度が最も高いコネクションのセルを送信するセルとして特定する、セル送信部の実現例が示されている。
特開２００１−６９１４８号公報には、キュー毎に固定的な優先度を設定し、送信可能時刻が現在時刻以前となるセルから、最も優先度が高いセルを送信するセルとして特定する、セル送信部の実現例が示されている。
特許第２９４３７０７号明細書には、送信可能時刻が最も早いコネクションが複数ある場合、これらのコネクションからラウンドロビン規則に基づいて送信するセルを特定する、セル送信部の実現例が示されている。
特許第３１２３５３７号明細書には、コネクションやトラヒッククラス毎に固定的な優先度を設定し、優先度が最も高いコネクションのセルを送信するセルとして特定し、優先度が最も高いコネクションが複数ある場合、これらのコネクションからラウンドロビン規則に基づいて送信するセルを特定する、セル送信部の実現例が示されている。
これらのセル送信部は、図２に示す従来のＧＣＲＡ方式によるシェーパ、及び図６に示す従来のＧＣＲＡ方式によるシェーパのセル送信部の双方に適用する事が出来る。
【００２２】
図２に示す従来のＧＣＲＡ方式によるシェーパの問題点を説明するために、図２に示すシェーパのセルスケジューリング部２０３における、図４に示すセルスケジューリング方法（第２の実現例のセルスケジューリング方法）に基づいた、送信可能時刻ｔｓの決定方法とパラメータ値ＴＡＴの更新方法を図１２に示す。
なお、図３に示すセルスケジューリング方法（第１の実現例のセルスケジューリング方法）の場合は、ＴＥＴ＝（ＴＡＴ−τ）とすれば、図４に示すセルスケジューリング方法と論理的に等価であるため、説明は省略する。
図４に示すセルスケジューリング部２０３におけるセルスケジューリング方法は、セルの送信可能時刻ｔｓと、実際にセルが送信される時刻の差が微少であるという前提に基づいている。
従って、図１２から明らかな通り、ｔｓが、ｔｓ＜ＴＡＴとなるセルのＴＡＴの更新値を（ＴＡＴ＋ｔ）としているが、厳密にはセルの実際の送信時刻がＴＡＴを越えた場合、ＴＡＴの更新値は、（セルの送信時刻＋ｔ）としなければならない。このため、ｔｓが、ｔｓ＜ＴＡＴとなるセルの実際の送信時刻がＴＡＴを越えた場合、ＴＡＴの更新値が本来の値より減少するため、次のセルの送信可能時刻が本来の時刻より早い時刻となる可能性が発生し、結果としてセル間隔が規定の値より短い不正な値となる可能性が生じる。
また、このセルスケジューリング方法では、ｔｓが、ｔｓ≧ＴＡＴとなるセルのＴＡＴの更新値を（ｔａ＋ｔ）としているが、厳密にはＴＡＴの更新値は、（セルの送信時刻＋ｔ）としなければならない。このため、ｔｓがｔｓ≧ＴＡＴとなるセルの実際の送信時刻に遅延が発生した場合、ＴＡＴの更新値が本来の値より減少するため、次のセルの送信可能時刻が本来の時刻より早い時刻となる可能性が発生し、結果としてセル間隔が規定の値より短い不正な値となる可能性が生じる。
【００２３】
図６に示す従来のＧＣＲＡ方式によるシェーパの問題点を説明するために、図６に示すシェーパのセルスケジューリング部２０３における、図９、図１０に示すセルスケジューリング方法（第２の実現例のセルスケジューリング方法）に基づいた、送信可能時刻ｔｓの決定方法とパラメータ値ＴＡＴの更新方法を図１３に示す。
なお、図７、図８に示すセルスケジューリング方法（第１の実現例のセルスケジューリング方法）の場合は、ＴＥＴ＝（ＴＡＴ−τ）とすれば、図９、図１０に示すセルスケジューリング方法と論理的に等価であるため、説明は省略する。
図９、図１０に示すセルスケジューリング方法では、セルの送信可能時刻ｔｓと実際にセルが送信される時刻ｔｅの間の時間差が許容される。
従って、図１３から明らかな通り、ｔｓが、ｔｓ＜ＴＡＴとなるセルが時刻ＴＡＴまでに送信された場合、ＴＡＴの更新値を（ＴＡＴ＋ｔ）とし、ＴＡＴ以降に送信された場合、ＴＡＴの更新値を（ｔｅ＋ｔ）としている。このため、ｔｓが、ｔｓ＜ＴＡＴとなるセルの実際の送信時刻がＴＡＴを越えた場合、ＴＡＴを越えない場合と比較してＴＡＴの更新値が増加し、次のセルの送信可能時刻がＴＡＴを越えない場合と比較して遅い時刻となる可能性が発生し、結果として以降のセルの送信時刻に遅延が発生する可能性が生じる。
また、このセルスケジューリング方法では、ｔｓが、ｔｓ≧ＴＡＴとなるセルのＴＡＴの更新値を（ｔｅ＋ｔ）としている。このため、ｔｓが、ｔｓ≧ＴＡＴとなるセルの実際の送信時刻に遅延が発生した場合、ＴＡＴの更新値はセルが即時に送信された場合と比較して増加するため、次のセルの送信可能時刻が即時に送信された場合と比較して遅い時刻となる可能性が発生し、結果として即時に送信された場合と比較して以降のセルの送信時刻に遅延が発生する可能性が生じる。
【００２４】
以上から明らかな通り、従来のＧＣＲＡ方式によるシェーパにおける、セルスケジューリング部のセルスケジューリング方法には、セルの送信可能時刻ｔｓが、ｔｓ＜ＴＡＴとなるセルは時刻ＴＡＴまでに、ｔｓ≧ＴＡＴとなるセルは即時にセルの送信を行わなければ、図２に示すシェーパではセル間隔が不正な値となる可能性が、図６に示すシェーパでは、以降のセルの送信時刻に遅延が発生する可能性がそれぞれ生じる。
しかし、図２および図６に示す従来のＧＣＲＡ方式によるシェーパのセル送信部（２０４，６０４）には、セルが所属するコネクション、キュー、トラヒッククラス間などに予め設定された固定優先度、ラウンドロビンやこれらの組み合わせに基づいて、送信可能時刻が最も早く、かつ、優先度が最も高いコネクションのセルを、送信するセルとして特定する方法や、送信可能時刻が現在時刻以前となるセルから、最も優先度が高いセルを送信するセルとして特定する方法や、送信可能時刻が最も早いコネクションが複数ある場合、これらのコネクションからラウンドロビン規則に基づいて送信するセルを特定する方法や、優先度が最も高いコネクションのセルを送信するセルとして特定し、優先度が最も高いコネクションが複数ある場合、これらのコネクションからラウンドロビン規則に基づいて送信するセルを特定する方法が用いられている。
従って、図２および図６に示す従来のＧＣＲＡ方式によるシェーパには、セルの送信可能時刻をｔｓを決定した際のＴＡＴもしくは（ＴＥＴ＋τ）までの時刻に送信すべきセルと、即時に送信を行わなければならないセルがあった場合は後者を送信するセルとして優先的に特定したり、セルの送信可能時刻ｔｓを決定した際のＴＡＴもしくは（ＴＥＴ＋τ）までの時間に余裕のあるセルと、余裕の少ないセルがあった場合は、後者を送信するセルとして優先的に特定する事が出来ないという第１の問題点がある。
【００２５】
一方、従来のＧＣＲＡ方式によるシェーパにおける、シーケンサ方式によるセル送信部は、到着したセルのタイムスロット値を、ブロードキャストバスを用いてポインタとタイムスロット値を要素とする配列構造内の各要素のタイムスロット値と並列に比較し、配列構造内の各要素のタイムスロット値が、到着したセルのタイムスロット値以上となる最初の要素の位置を挿入位置として、それ以上の全ての要素を左側にシフトし、到着したセルを格納するバッファヘのポインタと到着したセルのタイムスロット値を挿入位置に格納する事によって、要素をタイムスロット値の順にソートしている。
従って、シェーパがサポートするコネクション数やキュー数をＮとした場合、要素の比較や移動の回数はＮに比例する。
また、特開平１１−２３４３０９号公報には、セル送信部にヒープソータを用いたＧＣＲＡ方式によるシェーパの実現例が示されている。
この実現例は、シーケンサと同様に、図２および図６に示す従来のＧＣＲＡ方式によるシェーパのセル送信部の双方に通用する事が出来る。
特開平１１−２３４３０９号公報の段落番号〔００２６〕の記載から明らかな通り、このヒープソータは全ての現時点でアクティブなセルをソートし、セルが送信クレジットを受け取れる順序を設定している。
【００２６】
「Niklaus Wirth著、片山訳、“アルゴリズム＋データ構造＝プログラム、”日本コンピュータ協会、１９７９の８５、９５ページ」によると、この様にヒープを用いて要素間の順序関係を整列するヒープソータでは、シェーパがサポートするコネクション数やキュー数をＮとした場合、要素の比較や移動の回数はＮlog2Ｎに比例する。
以上から明らかな通り、図２および図６に示す従来のＧＣＲＡ方式によるシェーパのセル送信部（２０４，６０４）は、シェーパがサポートするコネクション数やキュー数をＮとすると、要素の比較や移動の回数がＮやＮlog2Ｎに比例するため、シェーパが大量のコネクション数やキュー数をサポートする場合、簡易な実装では要素の比較や移動に要する時間がＮやＮlog2Ｎのオーダとなり、動作時間が増大し高速な動作が困難となったり、並列処理で実装した場合は、比較器等の回路規模がＮやＮlog2Ｎのオーダとなり、装置コストが高価となる第２の問題点がある。
【００２７】
【発明が解決しようとする課題】
従来のＧＣＲＡ方式によるシェーパの実現例において、セルが所属するコネクション、キュー、トラヒッククラス間などに予め設定された固定優先度、ラウンドロビン以外の指標に着目して送信するセルを特定する方法の実現例が特許第２８８２３８４号に示されている。
この実現例では、キューやトラヒッククラス毎に優先度が動的に設定され、送信時刻に達したセルが複数存在する場合、最も優先度の高いセルを送信し、送信したセルが所属するキューやトラヒッククラスの優先度を低下させ、もしくはリセットし、送信時刻に達しているが、送信されなかったセルが所属するキューやトラヒッククラスの優先度上昇させる。
特許第２８８２３８４号明細書の段落番号〔００２７〕、〔００２８〕の記載から明らかな通り、この実現例は、従来のキュー、トラヒッククラス間などに予め設定された固定優先度に基づいて送信するセルを特定する方法において、優先度の高いキューが低いキューをブロックする問題を解決し、公平性を確保する事を目的としており、図２および図６に示す従来のＧＣＲＡ方式によるシェーパの第１及び第２の実現例における第１の問題点の解決方法にはならない。
【００２８】
また、特開２０００−２８６８６７号公報には、キュー毎に優先度が固定的に設定され、送信時刻に達したセルが複数存在する場合、セルが所属するコネクションの帯域順、セルが所属するコネクションの帯域順で同一帯域は優先度順、セルが所属するコネクションのトラヒッククラス順で同一クラスは帯域順で同一帯域は優先度順、のいずれかで送信するセルを特定する方法が示されている。
特開２０００−２８６８６７号公報の段落番号〔００２９〕から〔０００８〕の記載から明らかな通り、この方法は、シェーピングを行わないコネクションのための最優先キューを設けない事を目的としており、図２および図６に示す従来のＧＣＲＡ方式によるシェーパの第１及び第２の実現例における第１の問題点の解決方法にはならない。
更に、特開２００１−３６５３５号公報には、コネクション毎に帯域に基づいた優先度が固定的に設定され、送信時刻に達したセルが複数存在する場合、この優先度に基づいて送信するセルを特定する方法が示されている。
特開２００１−３６５３５号公報の段落番号〔０００７〕から〔００１０〕の記載から明らかな通り、この方法は、従来の固定優先度に基づいて送信するセルを選択する方法では優先度の高いコネクションが低いコネクションをブロックしたり、ラウンドロビンでは帯域保証が出来なくなる場合があり、送信要求が同時に発生しても、セル遅延のゆらぎを大きくせず、帯域保証が出来なくなる事態を回避する事を目的としている。
しかし、この方法では、図２および図６に示す従来のＧＣＲＡ方式によるシェーパの第１及び第２の実現例における第１の問題点の解決方法にはならない。
【００２９】
また、特許第３０６３７２６号明細書には、コネクション毎にセル遅延時間のゆらぎの値、セル遅延時間のゆらぎの値に起因する値、帯域、帯域に起因する値のいずれか一つに基づいた優先度が固定的に設定され、送信時刻に達したセルが複数存在する場合、この優先度に基づいて送信するセルを特定する方法が示されている。
特許第３０６３７２６号明細書の段落番号〔００１１〕、〔００１２〕の記載から明らかな通り、この方法は、セル遅延時間のゆらぎの値の許容値の低いコネクションのセル遅延時間のゆらぎの値を、この許容値が高いコネクションと比較して減少させる事や、帯域が高いコネクションのセル遅延時間のゆらぎの値を、帯域の値が低いコネクションと比較して減少させる事を目的としており、図２および図６に示す従来のＧＣＲＡ方式によるシェーパの第１及び第２の実現例における第１の問題点の解決方法にはならない。
【００３０】
一方、従来のＧＣＲＡ方式によるシェーパにおける、シーケンサ方式によるセル送信部の第２の問題点の解決方法として、要素を２進木構造で管理する方法が、特開平９−３０７５６６号公報に示されている。
特開平９−３０７５６６号公報の段落番号〔００３３〕の記載から明らかな通り、シェーパがサポートするコネクション数やキュー数をＮとすると、この方法では要素の比較の回数がlog2Ｎに比例するため、シェーパが大量のコネクション数やキュー数をサポートする場合、簡易な実装では要素の比較や移動に要する時間がlog2Ｎのオーダとなり、コネクション数やキュー数の増加と比較して動作時間の増加は緩やかとなり、また、並列処理で実装した場合は、比較器等の回路規模がlog2Ｎのオーダとなり、コネクション数やキュー数の増加と比較して回路規模の増加は緩やかとなる。
しかし、特開平９−３０７５６６号公報の段落番号〔００３３〕の記載から明らかな通り、この方法は要素の格納用のメモリ容量が２Ｎのオーダとなる問題点がある。
【００３１】
本発明は、前記従来技術の問題点を解決するためになされたものであり、本発明の目的は、ＧＣＲＡ方式によるセルシェーピング装置において、セル間隔が不正な値となる可能性や、以降のセルの送信時刻に遅延が発生する可能性を低減させることが可能となる技術を提供することにある。
また、本発明の他の目的は、ＧＣＲＡ方式によるセルシェーピング装置において、コネクション数やキュー数の増加と比較して、セル送信部の回路規模の増加を少なくし、装置コストを低減させ、更にセル送信部の要素の格納用のメモリ容量を従来の解決方法と比較して半減させることが可能となる技術を提供することにある。
本発明の前記ならびにその他の目的と新規な特徴は、本明細書の記述及び添付図面によって明らかにする。
【００３２】
【課題を解決するための手段】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、下記の通りである。
即ち、本願の請求項１、請求項２、請求項４、請求項５に記載された発明は、ＧＣＲＡ方式のセルシェーピング装置において、セルスケジューリング部が、セルの送信可能時刻を決定する際に使用したパラメータ値、もしくは、セルスケジューリング部がセルの送信可能時刻を決定する際に使用したパラメータ値及びセル遅延時間のゆらぎの値に起因する値を、そのセルの優先度としてセル送信部に出力する手段を含む事を最も主要な特徴とする。
本願の請求項１、請求項２、請求項４、請求項５に記載された発明によれば、従来のＧＣＲＡ方式によるシェーパにおける、セルが所属するコネクション、キュー、トラヒッククラス間などに予め設定された固定優先度、ラウンドロビンやこれらの組み合わせに基づいて、送信可能時刻が最も早くかつ優先度が最も高いコネクション、もしくは送信可能時刻が現在時刻以前となるセルから、最も優先度が高いセルを送信するセルとして特定する方法や、この優先度を動的に設定する方法や、帯域、セル遅延時間のゆらぎの値やこれらの値に起因する値を設定する方法において、セルの送信可能時刻を決定した際のパラメータ値、もしくはパラメータ値及びセル遅延時間のゆらぎの値に起因する値までの時刻に送信すべきセルと、即時に送信を行わなければならないセルがあった場合は後者を送信するセルとして優先的に特定したり、セルの送信可能時刻を決定した際のパラメータ値、もしくはパラメータ値及びセル遅延時間のゆらぎの値に起因する値までの時間に余裕のあるセルと、余裕の少ないセルがあった場合は、後者を送信するセルとして優先的に特定する事が出来ない第１の問題点を解決する事が出来る。
【００３３】
本願の請求項３、請求項６に記載された発明は、ＧＣＲＡ方式で実現されたセルシェーピング装置において、セル送信部が優先度が最も高いセルを特定する際に、ヒープによる優先キューによって該セルを特定する手段を含む事を最も主要な特徴とする。
本願の請求項３、請求項６に記載された発明によれば、ＧＣＲＡ方式によるシェーパのセル送信部の従来の実現例では、シェーパがサポートするコネクション数やキュー数をＮとすると、要素の比較や移動の回数がＮやＮlog2Ｎに比例するため、シェーパが大量のコネクション数やキュー数をサポートする場合、簡易な実装では要素の比較や移動に要する時間がＮやＮlog2Ｎのオーダとなり、動作時間が増大し高速な動作が困難となったり、並列処理で実装した場合は、比較器等の回路規模がＮやＮlog2Ｎのオーダとなり、装置コストが高価となる問題点を解決し、更にこの間題の既存の解決方法において要素の格納用のメモリ容量が２Ｎのオーダとなる問題点を解決する事が出来る。
【００３４】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
なお、実施の形態を説明するための全図において、同一機能を有するものは同一符号を付け、その繰り返しの説明は省略する。
［実施の形態１］
本発明の実施の形態１のシェーパは、本発明の請求項１に記載されたセルシェーピング装置である。
本実施の形態のシェーパの構成は、図２に示す従来のＧＣＲＡ方式によるシェーパの第１の実現例と同じであるので、構成の図示は省略する。
ここで、セルスケジューリング部２０３におけるセルスケジューリング方法としては、図４に示すセルスケジューリング部におけるセルスケジューリング方法の第２の実現例が用いられる。
但し、セルスケジューリング部２０３が、入力されたセル間隔の値ｔ、許容されるセル遅延時間のゆらぎτ、パラメータ値ＴＡＴ、及び時計部が２０２が計数する現在時刻ｔａに基づいて、図４のフローチャートに示された動作を開始する際に、このセルの優先度をＴＡＴとし、決定したセルの送信可能時刻ｔｓがセル送信部２０４に出力される際に、優先度（ＴＡＴ）もセル送信部２０４に出力されるものとする。
さらに、セル送信部２０４として、図５に示すセル送信部の第１の実現例が用いられる。
但し、セルの優先度は、セルスケジューリング部２０３からセルの送信可能時刻と共に入力されるものとし、セルが所属するコネクション、キュー、ＣＢＲ、nrt-ＶＢＲ等のトラヒッククラス間などに予め設定されているものでは無いものとする。
以上の、セルスケジューリング部２０３におけるセルスケジューリング方法とセル送信部２０４を備えれば、セルスケジューリング部２０３がセルの送信可能時刻を決定する際に使用したパラメータ値を、そのセルの優先度とすることが出来るため、従来のＧＣＲＡ方式によるシェーパの第１の実現例の構成のシェーパで、本願の請求項１に記載されたセルシェーピング装置を実現する事が出来る。
【００３５】
本実施の形態のシェーパの変形例について説明する。
本実施の形態のシェーパの変形例の構成は、図６に示す従来のＧＣＲＡ方式によるシェーパの第２の実現例と同じであるので、構成の図示は省略する。
ここで、セルスケジューリング部６０３におけるセルスケジューリング方法として、図９及び図１０に示すセルスケジューリング部におけるセルスケジューリング方法の第２の実現例が用いられる。
但し、セルスケジューリング部６０３は、入力された許容されるセル遅延時間のゆらぎτ、パラメータ値ＴＡＴ、及び時計部６０２が計数する現在時刻ｔａに基づいて、図９のフローチャートに示された動作を開始する際に、このセルの優先度をＴＡＴとし、決定したセルの送信可能時刻ｔｓがセル送信部６０４に出力される際に、この優先度（ＴＡＴ）もセル送信部６０４に出力されるものとする。
また、セル送信部６０４として、図１１に示すセル送信部の第１の実現例が用いられる。
但し、セルの優先度は、セルスケジューリング部６０３からセルの送信可能時刻と共に入力されるものとし、セルが所属するコネクション、キュー、ＣＢＲ、nrt-ＶＢＲ等のトラヒッククラス間などに予め設定されているものでは無いものとする。
以上の、セルスケジューリング部６０３におけるセルスケジューリング方法とセル送信部６０４を備えれば、セルスケジューリング部６０３がセルの送信可能時刻を決定する際に使用したパラメータ値を、そのセルの優先度とすることが出来るため、従来のＧＣＲＡ方式によるシェーパの第２の実現例の構成のシェーパで、本願の請求項１に記載されたセルシェーピング装置を実現する事が出来る。
【００３６】
［実施の形態２］
本発明の実施の形態２のシェーパは、本発明の請求項２に記載されたセルシェーピング装置である。
本実施の形態のシェーパの構成は、図２に示す従来のＧＣＲＡ方式によるシェーパの第１の実現例と同じであるので、構成の図示は省略する。
ここで、セルスケジューリング部２０３におけるセルスケジューリング方法として、図３に示すセルスケジューリング部におけるセルスケジューリング方法の第１の実現例が用いられる。
但し、セルスケジューリング部２０３が、入力されたセル間隔の値ｔ、許容されるセル遅延時間のゆらぎτ、パラメータ値ＴＥＴ、及び時計部２０２が計数する現在時刻ｔａに基づいて、図３のフローチャートに示された動作を開始する際に、このセルの優先度をパラメータ値及びセル遅延時間のゆらぎの値に起因する値、例えば、（ＴＥＴ＋τ）とし、決定したセルの送信可能時刻ｔｓがセル送信部２０４に出力される際に、優先度（ＴＥＴ＋τ）もセル送信部２０４に出力されるものとする。
また、セル送信部２０４として、図５に示すセル送信部の第１の実現例が用いられる。
但し、セルの優先度は、セルスケジューリング部２０３からセルの送信可能時刻と共に入力されるものとし、セルが所属するコネクション、キュー、ＣＢＲ、nrt-ＶＢＲ等のトラヒッククラス間などに予め設定されているものでは無いものとする。
以上の、セルスケジューリング部２０３におけるセルスケジューリング方法とセル送信部２０４を備えれば、セルスケジューリング部２０３がセルの送信可能時刻を決定する際に使用したパラメータ値、及びセル遅延時間のゆらぎの値に起因する値を、そのセルの優先度とすることが出来るため、従来のＧＣＲＡ方式によるシェーパの第１の実現例の構成のシェーパで、本願の請求項２に記載されたセルシェーピング装置を実現する事が出来る。
【００３７】
本実施の形態のシェーパの変形例について説明する。
本実施の形態のシェーパの変形例の構成は、図６に示す従来のＧＣＲＡ方式によるシェーパの第２の実現例と同じであるので、構成の図示は省略する。
ここで、セルスケジューリング部６０３におけるセルスケジューリング方法として、図７及び図８に示されたセルスケジューリング部におけるセルスケジューリング方法の第１の実現例が用いられる。
但し、セルスケジューリング部６０３は、入力された許容されるセル遅延時間のゆらぎτ、パラメータ値ＴＥＴ、及び時計部６０２が計数する現在時刻ｔａに基づいて、図７のフローチャートに示された動作を開始する際に、このセルの優先度をパラメータ値及びセル遅延時間のゆらぎの値に起因する値、例えば、（ＴＥＴ＋τ）とし、決定したセルの送信可能時刻ｔｓがセル送信部６０４に出力される際に、優先度（ＴＥＴ＋τ）もセル送信部６０４に出力されるものとする。
また、セル送信部６０４として、図１１に示されたセル送信部の第１の実現例が用いられる。
但し、セルの優先度は、セルスケジューリング部６０３からセルの送信可能時刻と共に入力されるものとし、セルが所属するコネクション、キュー、ＣＢＲ、nrt-ＶＢＲ等のトラヒッククラス間などに予め設定されているものでは無いものとする。
以上の、セルスケジューリング部６０３におけるセルスケジューリング方法とセル送信部６０４を備えれば、セルスケジューリング部がセルの送信可能時刻を決定する際に使用したパラメータ値、及びセル遅延時間のゆらぎの値に起因する値を、そのセルの優先度とすることが出来るため、従来のＧＣＲＡ方式によるシェーパの第２の実現例の構成のシェーパで、本願の請求項２に記載されたセルシェーピング装置を実現する事が出来る。
【００３８】
［実施の形態３］
本発明の実施の形態３のシェーパは、本発明の請求項４に記載されたセルシェーピング装置である。
本実施の形態のシェーパの構成は、図２に示す従来のＧＣＲＡ方式によるシェーパの第１の実現例と同じであるので、構成の図示は省略する。
ここで、セルスケジューリング部２０３におけるセルスケジューリング方法として、図４に示すセルスケジューリング部におけるセルスケジューリング方法の第２の実現例が用いられる。
但し、セルスケジューリング部２０３が、入力されたセル間隔の値ｔ、許容されるセル遅延時間のゆらぎτ、パラメータ値ＴＡＴ、及び時計部２０２が計数する現在時刻ｔａに基づいて、図４のフローチャートに示された動作を開始する際に、このセルの優先度をＴＡＴとし、決定したセルの送信可能時刻ｔｓがセル送信部２０４に出力される際に、優先度（ＴＡＴ）もセル送信部２０４に出力されるものとする。
また、セル送信部２０４として、従来のＧＣＲＡ方式によるシェーパの第１の実現例におけるセル送信部の第２の実現例が用いられる。
但し、セルの優先度は、セルスケジューリング部２０３からセルの送信可能時刻と共に入力されるものとし、セルが所属するコネクション、キュー、トラヒッククラス間などに予め設定されているものでは無いものとする。
以上の、セルスケジューリング部２０３におけるセルスケジューリング方法とセル送信部２０４を備えれば、セルスケジューリング部２０３がセルの送信可能時刻を決定する際に使用したパラメータ値を、そのセルの優先度とすることが出来るため、従来のＧＣＲＡ方式によるシェーパの第１の実現例の構成のシェーパで、本願の請求項４に記載されたセルシェーピング装置を実現する事が出来る。
【００３９】
本実施の形態のシェーパの変形例について説明する。
本実施の形態のシェーパの変形例の構成は、図６に示す従来のＧＣＲＡ方式によるシェーパの第２の実現例と同じであるので、構成の図示は省略する。
ここで、セルスケジューリング部６０３におけるセルスケジューリング方法として、図９及び図１０に示されたセルスケジューリング部におけるセルスケジューリング方法の第２の実現例が用いられる。
但し、セルスケジューリング部６０３は、入力された許容されるセル遅延時間のゆらぎτ、パラメータ値ＴＡＴ、及び時計部６０２が計数する現在時刻ｔａに基づいて、図９のフローチャートに示された動作を開始する際に、このセルの優先度をＴＡＴとし、決定したセルの送信可能時刻ｔｓがセル送信部６０４に出力される際に、優先度（ＴＡＴ）もセル送信部６０４に出力されるものとする。
また、セル送信部６０４として、従来のＧＣＲＡ方式によるシェーパの第２の実現例におけるセル送信部の第２の実現例が用いられる。
但し、セルの優先度は、セルスケジューリング部６０３からセルの送信可能時刻と共に入力されるものとし、セルが所属するコネクション、キュー、トラヒッククラス間などに予め設定されているものでは無いものとする。
以上の、セルスケジューリング部６０３におけるセルスケジューリング方法とセル送信部６０４を備えれば、セルスケジューリング部６０３がセルの送信可能時刻を決定する際に使用したパラメータ値を、そのセルの優先度とすることが出来るため、従来のＧＣＲＡ方式によるシェーパの第２の実現例の構成のシェーパで、本願の請求項４に記載されたセルシェーピング装置を実現する事が出来る。
【００４０】
［実施の形態４］
本発明の実施の形態４のシェーパは、本発明の請求項５に記載されたセルシェーピング装置である。
本実施の形態のシェーパの構成は、図２に示す従来のＧＣＲＡ方式によるシェーパの第１の実現例と同じであるので、構成の図示は省略する。
ここで、セルスケジューリング部２０３におけるセルスケジューリング方法として、図３に示すセルスケジューリング部におけるセルスケジューリング方法の第１の実現例が用いられる。
但し、セルスケジューリング部２０３が、入力されたセル間隔の値ｔ、許容されるセル遅延時間のゆらぎτ、パラメータ値ＴＥＴ、及び時計部２０２が計数する現在時刻ｔａに基づいて、図３のフローチャートに示された動作を開始する際に、このセルの優先度をパラメータ値及びセル遅延時間のゆらぎの値に起因する値、例えば、（ＴＥＴ＋τ）とし、決定したセルの送信可能時刻ｔｓがセル送信部２０４に出力される際に、優先度（ＴＥＴ＋τ）もセル送信部２０４に出力されるものとする。
また、セル送信部２０４として、従来のＧＣＲＡ方式によるシェーパの第２の実現例におけるセル送信部の第２の実現例が用いられる。
但し、セルの優先度は、セルスケジューリング部２０３からセルの送信可能時刻と共に入力されるものとし、セルが所属するコネクション、キュー、トラヒッククラス間などに予め設定されているものでは無いものとする。
以上の、セルスケジューリング部２０３におけるセルスケジューリング方法とセル送信部２０４を備えれば、セルスケジューリング部２０３がセルの送信可能時刻を決定する際に使用したパラメータ値、及びセル遅延時間のゆらぎの値に起因する値を、そのセルの優先度とすることが出来るため、従来のＧＣＲＡ方式によるシェーパの第１の実現例の構成のシェーパで、本願の請求項５に記載されたセルシェーピング装置を実現する事が出来る。
【００４１】
本実施の形態のシェーパの変形例について説明する。
本実施の形態のシェーパの変形例の構成は、図６に示す従来のＧＣＲＡ方式によるシェーパの第２の実現例と同じであるので、構成の図示は省略する。
ここで、セルスケジューリング部６０３におけるセルスケジューリング方法として、図７及び図８に示されたセルスケジューリング部におけるセルスケジューリング方法の第１の実現例が用いられる。
但し、セルスケジューリング部６０３は、入力された許容されるセル遅延時間のゆらぎτ、バラメータ値ＴＥＴ、及び時計部６０２が計数する現在時刻ｔａに基づいて、図７のフローチャートに示された動作を開始する際に、このセルの優先度をパラメータ値及びセル遅延時間のゆらぎの値に起因する値、例えば、（ＴＥＴ＋τ）とし、決定したセルの送信可能時刻ｔｓがセル送信部６０４に出力される際に、優先度（ＴＥＴ＋τ）もセル送信部６０４に出力されるものとする。
また、セル送信部６０４として、従来のＧＣＲＡ方式によるシェーパの第２の実現例におけるセル送信部の第２の実現例が用いられる。
但し、セルの優先度は、セルスケジューリング部６０３からセルの送信可能時刻と共に入力されるものとし、セルが所属するコネクション、キュー、トラヒッククラス間などに予め設定されているものでは無いものとする。
以上の、セルスケジューリング部６０３におけるセルスケジューリング方法とセル送信部６０４を備えれば、セルスケジューリング部６０３がセルの送信可能時刻を決定する際に使用したパラメータ値、及びセル遅延時間のゆらぎの値に起因する値を、そのセルの優先度とすることが出来るため、従来のＧＣＲＡ方式によるシェーパの第２の実現例の構成のシェーパで、本願の請求項５に記載されたセルシェーピング装置を実現する事が出来る。
なお、本願の請求項２、請求項５に記載された発明は、セル遅延時間のゆらぎの値を、０もしくは定数等の固定的な値に置き換えた場合を包含している事は自明である。
また、本願の請求項１、請求項４に記載された発明は、特願２００１−２２７２６８号の請求項１に示されたセルスケジューリング方法と、本願の請求項２、請求項５に記載された発明は、特願２００１−２２７２６８号の請求項２に示されたセルスケジューリング方法と組み合わせる事が出来る事は自明である。
【００４２】
［実施の形態５］
本願の請求項３、請求項６に記載された発明で用いられる、ヒープによる優先キューの動作を、「Alfred Aho、他著、大野訳、“データ構造とアルゴリズム、”倍風館、1987の125-126ページ」を基に説明する。
ヒープとは配列による半順序のついた木のデータ構造の事であり、優先キューの実装やソータの実装に用いられる。
ヒープの例を図１４に示す。図１４において、丸は要素を示し、リンクは要素間の上下関係を示す。
ある要素の上の要素を「親」、下の要素を「子」と呼び、図１５に示す様に、一つの要素は最大２つの要素を「子」とする事ができる。
ヒープの要素はアドレスで識別される。ヒープの一番上の要素のアドレスを１とし、以下のアドレスは図１６に示す様に順次割り当てられる。
図１６において、ある要素のアドレスをＩとすると、その要素に子が存在する場合、そのアドレスは、２Ｉ，（２Ｉ＋１）となる。また、親が存在する場合、そのアドレスはＩ／２の整数部となる。
図１６において、アドレス１の要素を一番左の要素、アドレス１２の要素を一番右の要素と呼ぶ事がある。図１６に示す様に、ヒープの要素は左詰めで配置される。
【００４３】
優先キューとは、優先度が割り当てられられた要素から、優先度の最も高い要素を特定するデータ構造の事である。
優先キューは、要素を記憶するデータ構造と、データ構造から最も優先度の高い要素を削除するアルゴリズムと、データ構造に要素を挿入するアルゴリズムから構成される。
優先キューは、優先度が最も高い要素を特定出来るが、ソータと異なり、その他の要素を優先度順に整列するものではない。
ヒープによる優先キューのデータ構造を図１７に示す。
図１７における要素の値は優先度を表し、値が少ないほど優先度が高いものとする。
図１７における要素の配置は、「要素が子を有する場合、その要素の優先度は子の優先度以上となる」規則に基づいている。このため、ヒープの一番上の要素は最も高い優先度を持つことになる。
図１７において、ある要素が２つの子を持つ場合、子の間には、特に優先度の大小関係が規定されない。また、同じ優先度の要素が必ずしも同じ高さに位置する訳では無い。
【００４４】
ヒープヘの要素の挿入アルゴリズムは、ヒープにおける要素の適切な挿入アドレス（位置）を探索する事によって実現される。基本的なアルゴリズムを以下に示す。
（ａ）最初の挿入位置を、ヒープの最も右の要素の右隣とする。
（ｂ）挿入する要素の優先度が、挿入位置の親の要素の優先度以下の場合、もしくは、挿入位置の親の要素が存在しない場合（＝挿入位置が一番上の要素となる場合）、挿入する要素の適切な挿入位置が探索されたため、挿入する要素を挿入位置に移動して、停止する。
（ｃ）挿入する要素の優先度が、挿入位置の親の要素の優先度より高い場合、この位置は適切な挿入位置ではないため、挿入位置の親の要素を挿入位置へ移動し、次の挿入位置を移動前の親の位置とする。
（ｄ）上記（ｂ）と（ｃ）の動作を、アルゴリズムが停止するまで繰り返す。
このアルゴリズムの例として、図１７のヒープに優先度７の要素を挿入する例を図１８に示す。このアルゴリズムによって、図１９に示した様にヒープの一番上の要素によって最も高い優先度の要素が特定される。
【００４５】
ヒープから最も優先度の高い要素を削除するアルゴリズムは、最も上の要素を削除し、最も右の要素の適切な挿入アドレス（位置）を探索する事によって実現される。基本的なアルゴリズムを以下に示す。
（ａ）ヒープの最も上の要素が最も優先度が高いため、これを削除する。
（ｂ）ヒープの要素数が０となった場合、停止する。
（ｃ）最も右の要素を削除し、挿入する要素とする。
（ｄ）最初の挿入位置を、ヒープの最も上の要素とする。
（ｅ）挿入位置の要素が子を持たない場合、もしくは、挿入する要素の優先度が、挿入位置の全ての子の優先度以上となる場合、挿入する要素の適切な挿入位置が探索されため、挿入する要素を挿入位置に移動して、停止する。
（ｆ）挿入する要素の優先度が、何れか一方の子あるいは両方の子の優先度より低い場合、（子が一つしかない場合は子の優先度より低い場合）、この位置は適切な挿入位置ではないため、先度の高い方の子を挿入位置へ移動し、次の挿入位置を移動前の子の位置とする。
（ｇ）上記（ｅ）と（ｆ）の動作を、アルゴリズムが停止するまで繰り返す。
このアルゴリズムの例として、図１７のヒープから最も優先度の高い要素を削除する例を図２０に示す。このアルゴリズムによって、図２１に示した様にヒープの一番上の要素によって最も高い優先度の要素が特定される。
以上から明らかな通り、ヒープによる優先キューにおける要素数をＮとすると、要素の挿入や削除の際の要素の比較や移動の回数はlog2Ｎに比例し、かつ要素の格納用のメモリ容量はＮのオーダとなる。
【００４６】
本願の請求項３に記載された発明の実施例は、前記のヒープによる優先キューの要素を、到着したセルのタイムスロット値、及びセルを格納するバッファヘのポインタ、もしくはキューの先頭のセルへのポインタとし、要素の優先度をタイムスロット値で判断する事によって実現できる。
ヒープによる優先キューは、シェーパにセルが到着した際に、到着したセルを格納するバッファにセルを格納し、このバッファを示す様に到着したセルを格納するバッファヘのポインタを設定する、もしくは、セルがキューの先頭に達した際に、このキューの先頭を示す様にキューの先頭に達したセルヘのポインタを設定し、そして｛セルスケジューリング部によって決定したセルの送信可能時刻＊（優先度の最大値＋１）＋セルスケジューリング部によって決定したセルの優先度｝の値をセルのタイムスロット値に設定し、これらの値から成る要素をヒープによる優先キューに挿入する。
次に、ヒープによる優先キューは、最も上の要素のタイムスロット値に含まれるセルの送信可能時刻と、時計部が計数する時刻を比較し、前者の値が後者の値以前となる場合は、最も上の要素のポインタが示すバッファ、もしくはキューの先頭に格納されたセルを回線に送信し、最も上の要素を削除する事によって、ヒープによる優先キューに格納されているセルの中から送信可能時刻が最も早くかつ優先度が最も高いセルを特定し、特定された送信可能時刻が現在時刻より以前の場合、そのセルを回線に送信する。
【００４７】
本願の請求項６に記載された発明の実施例は、前記のヒープによる優先キューを直列に２段接続し、要素に含まれる値を、到着したセルのタイムスロット値、及びセルを格納するバッファへのポインタ、もしくはキューの先頭のセルへのポインタとし、要素の優先度をタイムスロット値で判断する事によって実現できる。
１段目のヒープによる優先キューは、タイムスロット値をセルスケジューリング部によって決定したセルの送信可能時刻に設定する。
また、２段目のヒープによる優先キューは、タイムスロット値をセルスケジューリング部によって決定したセルの優先度に設定する。
１段目のヒープによる優先キューは、シェーパにセルが到着した際に、到着したセルを格納するバッファにセルを格納し、このバッファを示す様に到着したセルを格納するバッファヘのポインタを設定する、もしくはセルがキューの先頭に達した際に、このキューの先頭を示す様にキューの先頭に達したセルヘのポインタを設定し、そしてセルの送信可能時刻の値をセルのタイムスロット値に設定し、こられの値から成る要素をヒープによる優先キューに挿入する。
次に、１段目のヒープによる優先キューは、最も上の要素のタイムスロット値に含まれるセルの送信可能時刻と、時計部が計数する時刻を比較し、前者の値が後者の値以前となる場合は、最も上の要素のポインタ及び、このポインタが示すバッファ、もしくはキューの先頭に格納されたセルの優先度から成る要素を２段目のヒープによる優先キューに挿入し、１段目のヒープの最も上の要素を削除する。
２段目のシーケンサは、最も上の要素のポインタが示すバッファ、もしくはキューの先頭に格納されたセルを回線に送信し、最も上の要素を削除する事によって、送信可能時刻が現在時刻以前となるセルから、最も優先度が高いセルを送信するセルとして特定して、そのセルを回線に送信する。
【００４８】
以上説明した様に、本願の請求項１、請求項２、請求項４、請求項５に記載された発明は、ＧＣＲＡ方式で実現されたセルシェーピング装置において、セルの送信可能時刻を決定した際のパラメータ値、もしくはパラメータ値及びセル遅延時間のゆらぎの値に起因する値までの時刻に送信すべきセルと、即時に送信を行わなければならないセルがあった場合は後者を送信するセルとして優先的に特定したり、セルの送信可能時刻を決定した際のパラメータ値、もしくはパラメータ値及びセル遅延時間のゆらぎの値に起因する値までの時間に余裕のあるセルと、余裕の少ないセルがあった場合は、後者を送信するセルとして優先的に特定する事が出来るため、セル間隔が不正な値となる可能性や、以降のセルの送信時刻に遅延が発生する可能性を低減させる利点がある。
また、本願の請求項３、請求項６に記載された発明は、請求項１、請求項２、請求項４、請求項５に記載されたＧＣＲＡ方式で実現されたセルシェーピング装置において、セル送信部が、優先度が最も高いセルを特定する際に、ヒープによる優先キューによって該セルを特定する手段を含むため、シェーパがサポートするコネクション数やキュー数をＮとすると、要素の比較や移動の回数がlog2Ｎに比例し、かつ要素の格納用のメモリ容量がＮのオーダとなるため、シェーパが大量のコネクション数やキュー数をサポートする場合、簡易な実装では要素の比較や移動に要する時間がlog2Ｎのオーダとなり、コネクション数やキュー数の増加と比較して動作時間の増加は緩やかとなるため高速な動作が可能となり、また、並列処理で実装した場合は、比較器等の回路規模がlog2Ｎのオーダとなり、コネクション数やキュー数の増加と比較して回路規模の増加は緩やかとなるため、装置コストが廉価となり、更に要素の格納用のメモリ容量が従来の解決方法と比較して半減する利点がある。
以上、本発明者によってなされた発明を、前記実施の形態に基づき具体的に説明したが、本発明は、前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは勿論である。
【００４９】
【発明の効果】
本願において開示される発明のうち代表的なものによって得られる効果を簡単に説明すれば、下記の通りである。
（１）本発明のセルシェーピング装置によれば、セル間隔が不正な値となる可能性や、以降のセルの送信時刻に遅延が発生する可能性を低減させることが可能となる。
（２）本発明のセルシェーピング装置によれば、コネクション数やキュー数の増加と比較して、セル送信部の回路規模の増加を少なくできるため、装置のコストを低減させ、更に要素の格納用のメモリ容量を従来の解決方法と比較して半減させることが可能となる。
【図面の簡単な説明】
【図１】従来のトークン方式によるセルシェーピング装置の実現例の概略構成を示すブロック図である。
【図２】従来のＧＣＲＡ方式によるセルシェーピング装置の第１の実現例の概略構成を示すブロック図である。
【図３】従来のＧＣＲＡ方式によるセルシェーピング装置の第１の実現例のセルスケジューリング部におけるセルスケジューリング方法の第１の実現例を示すフローチャートである。
【図４】従来のＧＣＲＡ方式によるセルシェーピング装置の第１の実現例のセルスケジューリング部におけるセルスケジューリング方法の第２の実現例を示すフローチャートである。
【図５】従来のＧＣＲＡ方式によるセルシェーピング装置の第１の実現例のセル送信部の実現例の概略構成を示すブロック図である。
【図６】従来のＧＣＲＡ方式によるセルシェーピング装置の第２の実現例の概略構成を示すブロック図である。
【図７】従来のＧＣＲＡ方式によるセルシェーピング装置の第２の実現例のセルスケジューリング部におけるセルスケジューリング方法の第１の実現例を示すフローチャートである。
【図８】従来のＧＣＲＡ方式によるセルシェーピング装置の第２の実現例のセルスケジューリング部におけるセルスケジューリング方法の第１の実現例を示すフローチャートである。
【図９】従来のＧＣＲＡ方式によるセルシェーピング装置の第２の実現例のセルスケジューリング部におけるセルスケジューリング方法の第２の実現例を示すフローチャートである。
【図１０】従来のＧＣＲＡ方式によるセルシェーピング装置の第２の実現例のセルスケジューリング部におけるセルスケジューリング方法の第２の実現例を示すフローチャートである。
【図１１】従来のＧＣＲＡ方式によるセルシェーピング装置の第２の実現例のセル送信部の実現例の概略構成を示すブロック図である。
【図１２】従来のＧＣＲＡ方式によるセルシェーピング装置の第１の実現例のセルスケジューリング部におけるセルスケジューリング方法の第２の実現例に基づいた、送信可能時刻ｔｓの決定方法とパラメータ値ＴＡＴの更新方法を説明するための図である。
【図１３】従来のＧＣＲＡ方式によるセルシェーピング装置の第２の実現例のセルスケジューリング部におけるセルスケジューリング方法の第２の実現例に基づいた、送信可能時刻ｔｓの決定方法とパラメータ値ＴＡＴの更新方法を説明するための図である。
【図１４】ヒープの例を示す図である。
【図１５】ヒープの親と子の関係を説明するための図である。
【図１６】ヒープのアドレスを説明するための図である。
【図１７】ヒープによる優先キューのデータ構造を説明するための図である。
【図１８】図１７に示すヒープに優先度７の要素を挿入する例を説明するための図である。
【図１９】図１８の挿入結果を示す図である。
【図２０】図１７に示すヒープから最も優先度の高い要素を削除する例を説明するための図である。
【図２１】図２０の削除結果を示す図である。
【符号の説明】
１０１，６０７…入力部、１０２，１０３、６０５，６０６，１１０１，１１０２，１１０６…キュー、１０４，１０５…送信タイミング生成部、１０６…調停部、２０１，６０１…記憶部、２０２，６０２…時計部、２０３，６０３…セルスケジューリング部、２０４，６０４…セル送信部、５０１，５０２，５０６…バッファ、５０３，５０７，１１０３，１１０７…ポインタ、５０４，５０８，１１０４，１１０８…タイムスロット値、５０５，１１０５…配列構造、５０９，１１０９…ブロードキャストバス。
【図１】
0003742348.tif 000002
【図２】
0003742348.tif 000003
【図３】
0003742348.tif 000004
【図４】
0003742348.tif 000005
【図５】
0003742348.tif 000006
【図６】
0003742348.tif 000007
【図７】
0003742348.tif 000008
【図８】
0003742348.tif 000009
【図９】
0003742348.tif 000010
【図１０】
0003742348.tif 000011
【図１１】
0003742348.tif 000012
【図１２】
0003742348.tif 000013
【図１３】
0003742348.tif 000014
【図１４】
0003742348.tif 000015
【図１５】
0003742348.tif 000016
【図１６】
0003742348.tif 000017
【図１７】
0003742348.tif 000018
【図１８】
0003742348.tif 000019
【図１９】
0003742348.tif 000020
【図２０】
0003742348.tif 000021
【図２１】
0003742348.tif 000022