JPH10200549A

JPH10200549A - セルスケジューリング装置

Info

Publication number: JPH10200549A
Application number: JP9316826A
Authority: JP
Inventors: Tokunen Kin; 徳年金
Original assignee: Daewoo Electronics Co Ltd
Current assignee: WiniaDaewoo Co Ltd
Priority date: 1996-12-26
Filing date: 1997-11-18
Publication date: 1998-07-31
Anticipated expiration: 2017-11-18
Also published as: GB9723907D0; US6044091A; JP3810907B2; GB2322258A; GB2322258B

Abstract

(57)【要約】【課題】上位ノードから下位ノードへスケジューリ
ング情報を伝達するためのヘッダー空間がなくても、終
端間遅延及び遅延ジッタを補償して実時間単位で、セル
をスケジューリングし得るセルスケジューリング装置を
提供する。【解決手段】コールに対して、Ｍ個のタイムスロッ
トからなるフレーム大きさを決定し、上位ノードと下位
ノードとの間の伝播遅延及び遅延限界を検出するするコ
ール調節部２１０と、各接続の各ノードごとに１つずつ
割当てられ、フレーム大きさをリセットするために、伝
播遅延及び遅延限界に基づいて接続単位でプリ同期化さ
れ、各フレームのタイムスロットをカウンタダウンし
て、タイムスロット単位にカウント値を生成するカウン
タ同期化部２２０と、フレームの大きさの周期に従って
スイッチング信号を生成するスイッチ制御部１７と、接
続ごとに同期化され、セルを調整、スケジューリングす
る遅延限界トラフィックキュー10-iとを含む。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、ＡＴＭ網において
実時間サービスでセルをスケジューリングするセルスケ
ジューリング装置に関し、特に、プリ同期化されたフレ
ームに基づいてスケジューリング情報をノード間に伝送
せずに、保証された終端間遅延及び遅延ジッタを提供し
得るセルスケジューリング装置に関する。

【０００２】

【従来の技術】広帯域総合通信網（Ｂ−ＩＳＤＮ）は、
広帯域伝送及びスイッチング技法に基づいて、集中また
は分散されている使用者たちをサーバーと接続すること
によって、連続的な実時間サービス及び集団データサー
ビスなどのような多様なサービスを提供するディジタル
網である。そのようなＢ−ＩＳＤＮにおいて、非同期伝
送モード（ＡＴＭ）技法は使用者網インタフェースを通
じて情報を伝達するのに用いられる。ＡＴＭ技法はパケ
ットベース非同期時分割多重化技法として、通常の回路
スイッチング技法及びパケットスイッチング技法ともを
用い、多様な類型のサービスを処理することができる。

【０００３】将来のＡＴＭ網は、現在のサービスより
質、量共に非常に異なるトラフィック特性を有する予測
不可能な大規模サービスを要求するであろう。そのよう
なサービスは、例えば、スループット、遅延、ジッタ及
び損率を補償しなければならない。また、オーディオや
ビデオのような実時間サービスが広帯域網において主な
サービスになるにつれ、遅延及びジッタに対する要求は
段々増大されている。実時間情報は制限時間内に伝達さ
れなければ損失されたものとみなされるので、遅延及び
ジッタに対する要求を効果的に満足させることが更に肝
要になっている。

【０００４】高速パケットスイッチング網において実時
間通信サービスを支援し得るように、キューイング方式
に対する研究案が活発に報告されてきた。それら研究案
は作業保存方式と非作業保存方式とに分類される。作業
保存方式を有する網においては、接続が網の入口におい
て使用者定義のレート制限条件を満足させるにもかかわ
らず、以前のノードにおける網負荷変動は接続のトラフ
ィックのパターンを歪曲させ、幾つかのノードにおいて
瞬間的なレートの上昇を引起こす。接続におけるトラフ
ィックの突発は、ソースノードから宛先ノードまでの接
続経路に沿って累積される傾向があり、従って、後方に
位置したノードに対して資源が更に必要となる。

【０００５】このような問題点を解決するため、幾つか
の非作業保存方式のパケットサービス規則が提案されて
いて、中間ノードにおけるパケットジッタを制御してト
ラフィックの突発を防いでいる。典型的な例として、階
層的ラウンドロビン（HRR: hierarchical round robi
n）法及びストップアンドゴー（stop-and-go）法があ
る。これは時間軸を一定の長さのフレームに分けて、各
接続に幾つかの分割フレームを割当てる。このようなフ
レーミング方式において、パケットサービスは割当てら
れた時間フレームに対してのみ可能であるので、遅延ジ
ッタを制限することができる。しかしながら、帯域幅割
当と遅延制限との間の結合問題は帯域幅の利用効率を低
下させる。ジッタＥＤＤ（Earliest-Due-Date）及びレ
ート制御静的優先順位（RCSP：rate-controlled static
priority）技法は、パケットジッタをパケット単位で
制御する。しかし、各ノードにおいて各パケットの前時
間（leading time）を計算することが必要であり、次ノ
ードの伝送のためにヘッダに計算時間を表示する。

【０００６】図１は、従来のジッタＥＤＤ技法を説明す
るための模式図であって、接続ｊにおける隣接する２つ
のノードｉ及びノードｉ+1を通じてセルｋの進行過程が
示されている。ここで、ノード番号ｉ、接続番号ｊ及び
セル番号ｋは、各々正の整数である。接続ｊのノードｉ
におけるセルｋは適格時刻ＥＴ_ij ^kが過ぎた後に伝送に
適切な状態になり、ノードｉにおけるデッドラインＤＬ
_ij ^kより以前にサービスされなければならない。デッド
ラインＤＬ_ij ^kは適格時刻ＥＴ_ij ^kと遅延限界ｄ_ijとの和
であり、接続ｊのノードｉに対する遅延限界ｄ_ijはコー
ルの設定段階において予め定められる。

【０００７】スケジューラにおける予め定められた割当
方式によって、セルｋがノードｉからノードｉ+1にデッ
ドラインＤＬ_ij ^kの以前にサービス時刻ＳＴ_ij ^kにて実際
サービスされる時、セルｋに先行時間（pre-ahead）Ｐ
Ａ_ij ^kが書込まれる。上記先行時間ＰＡ_ij ^kはノードｉに
おけるセルｋのデッドラインＤＬ_ij ^kとサービス時刻Ｓ
Ｔ_ij ^kとの間の時間間隔を考慮して計算される。ノード
ｉからノードｉ+1までの仮想チャンネルまたは仮想経路
を経る伝播遅延τ_iの後、セルｋはノードｉ+1における
到着時刻ＡＴ_i+1 _、 _j ^kに到着し、その後、セルｋは保持時
間ＨＴ_i+1 _、 _j ^kの間ノードｉ+1のジッタ制御部に一時的に
格納される。ノードｉ+1における保持時間ＨＴ_i+1 _、 _j ^kは
ノードｉにおける先行時間ＰＡ_ij ^kと同一である。セル
ｋがノードｉ+1における伝送に対して適格になる適格時
刻ＥＴ_i+1 _、 _j ^kは、ノードｉ+1における到着時刻ＡＴ_i+1 _、
_j ^kと保持時間ＨＴ_i+1 _、 _j ^kとの和である。従って、ジッタ
制御部は、セルｋがデッドラインＤＬ_ij ^kより先にノー
ドｉを離れている時間の量だけセルｋを保持することに
よって、遅延偏差を制御して突発が網の内部で発生する
ことを防ぐ。

【０００８】一方、ノードｉ+1におけるセルｋは、デッ
ドラインＤＬ_i+1 _、 _j ^kより先にサービス時刻ＳＴ_i+1 _、 _j ^kに
タイムスタンプ、例えば、先行時間ＰＡ_i+1 _、 _j ^kに対する
スケジューリング情報とともにサービスされる。ここ
で、デッドラインＤＬ_i+1 _、 _j ^kは適格時刻ＥＴ_i+1 _、 _j ^kと遅
延限界ｄ_i+1 _、 _j ^kとの和と同一であり、先行時間ＰＡ_i+1 _、
_j ^kはノードｉ+1におけるデッドラインＤＬ_i+1 _、 _j ^kとサー
ビス時刻ＳＴ_i+1 _、 _j ^kとの間の時間の差と同一である。

【０００９】言換えれば、ノードｉ+1におけるセルｋの
適格時刻ＥＴ_i+1 _、 _j ^kはＥＴ_i+1 _、 _j ^k＝ＥＴ_ij ^k＋ｄ_ij＋τ_i によって計算される。ここで、ＥＴ_ij ^kとＥＴ
_i+1 _、 _j ^kは、各々、接続ｊの上位ノードｉ及び下位ノード
ｉ+1におけるセルｋの適格時刻を表し、ｄ_ijは接続ｊの
上位ノードにおける遅延限界であり、τ_iは上位ノード
ｉと下位ｉ+1との間の伝播遅延を表す。隣接する２つの
ノードのうち、上位ノード及び下位ノードは各々ソース
ノード及び宛先ノードの方を向かっている。下位ノード
ｉ+1におけるセルｋの適格時刻は、上位ノードｉにおけ
る適格時刻に依存するので、上位ノードｉに対する情報
が下位ノードｉ+1に伝達されなければならない。そのよ
うな情報は、幾つかのアルゴリズムにおけるセルヘッダ
ーに伝達される。

【００１０】従って、既存の非作業保存方式のパケット
サービスは、遅延ジッタをフレーミング法を用いるか、
ジッタ情報をパケットヘッダーを用いて伝達することに
よって制御するので、現在の形態ではＡＴＭ網に適用す
るのには適切ではない。フレーミング法の利用は結合問
題のため接続の多様な性能要求量を満足させることが不
可能で、パケットヘッダーの利用は時間を表示するため
ヘッダー空間を要求するので、ＡＴＭ網においては適切
ではないという不都合がある。

【００１１】

【発明が解決しようとする課題】従って、本発明の主な
目的は、上位ノードから下位ノードへスケジューリング
情報を伝達するためのヘッダー空間がなくても、終端間
遅延及び遅延ジッタを補償してＡＴＭ網において無混雑
（congestion-free）実時間通信サービスでセルをスケ
ジューリングし得るセルスケジューリング装置を提供す
ることにある。

【００１２】

【課題を解決するための手段】上記の目的を達成するた
めに、本発明によれば、ソースノード及び宛先ノードを
有する複数のノードを結んで形成された接続を通じてコ
ールの複数のセルをスケジューリングするセルスケジュ
ーリング装置であって、前記コールに対して、Ｍが正の
整数である時、各々が予め定められた時間間隔であるＭ
個のタイムスロットからなるフレームの大きさを決定す
るフレーム大きさ決定手段と、前記ソースノードの方に
位置する上位ノード及び前記宛先ノードの方に位置する
下位ノードからなる隣接する各ノード対において、両ノ
ードの間に対する各伝播遅延及び遅延限界を検出する遅
延情報検出手段であって、前記伝播遅延はセルの伝播の
際、複数のタイムスロットを表し、前記遅延限界はＰが
正の整数である時、前記セルが前記上位ノードにおいて
伝送に適切な状態になった後から、前記下位ノードにサ
ービスされる前のＰ個のタイムスロットを表す、前記遅
延情報検出手段と、各接続の各ノードごとに１つずつ割
当てられ、前記フレーム大きさをリセットするために、
伝播遅延及び遅延限界に基づいて接続単位でプリ同期化
され、各フレームのタイムスロットをカウンタダウンし
て、タイムスロット単位にカウント値を生成する複数の
フレームカウンタであって、前記上位ノードにおいて前
記フレームカウンタによってカウントされた各上位カウ
ント値が、前記下位ノードにおいて前記フレームカウン
タによってカウントされた下位カウント値と相関関係に
ある、前記複数のフレームカウンタと、前記フレームカ
ウンタのカウント値がフレーム大きさにリセットされる
時、フレーム大きさの周期に従ってスイッチング信号を
生成するスイッチ制御部と、前記接続ごとに同期化さ
れ、前記フレームカウンタのカウント値及び前記切換え
信号に基づいて、セルを調整、スケジューリングする同
期化スケジューラとを含むことを特徴とするセルスケジ
ューリング装置が提供される。

【００１３】

【発明の実施の形態】図２を参照すると、本発明の通信
モデルが示されている。ここで、網はリンクの組によっ
て接続されたノードの組からなっている。各々の一方向
性のリンクは２つのノードが帯域幅を用いて通信できる
ようにする。接続ｊにおけるパケットまたはセルｋが複
数のノードを通じてソースノードから宛先ノードまで貫
通するリンクの組は、パケット経路と呼ばれる。各リン
クに対する隣接する２つのノードは、ソースノードの方
に位置した上位ノードと宛先ノードの方に位置した下位
ノードとして分けられる。図２の例は、２つの接続、即
ち、経路P₁={AC,CD,DE}に沿った接続j₁と、P₂={BC,CD,D
F}に沿った接続j₂とが示されている。リンクCDを用いる
接続の組は{J₁,J₂}である。

【００１４】本発明によると、実時間サービスに適切な
新しいキューイング方式が提供される。これは、保証さ
れた情報量及びほぼ一定の終端間遅延を有する無混雑通
信を可能にする。本発明のキューイング方式はパーセシ
ョンプリ同期化（Per-Session Pre−Synchronized；PSP
S）フレーミング法を用いる。各接続のフレームは、各
ノードにあるフレームカウンタによって接続別に定義さ
れ、フレームの境界は接続の設定段階でフレームカウン
タのプリ同期化を通じて整列される。このように同期化
されたフレームカウンタは、ジッタ情報を伝達するため
のヘッダ空間を有しなくても遅延ジッタを効果的に制御
することができる。従って、ＰＳＰＳフレーミング法は
ＡＴＭ網に直接適用され得、時間従属情報、例えば、音
声、映像及びＡＴＭ網の回路エミュレーションのような
実時間通信信号に対する回答を可能にする。

【００１５】図３を参照すると、本発明によって、コー
ル接続の設定及びセル伝送を行う装置が示されている。
伝送されたＡＴＭセルはヘッダー検出部１１０及びジッ
タ調節部１４０に供給される。コールの設定段階におい
て、ヘッダー検出部１１０は、ＡＴＭセルの５オクテッ
トヘッダーを検出し、ＡＴＭセルのコール接続が設定さ
れたか否かを判断する。ＡＴＭセルに対するコールが存
在しない場合、ヘッダー情報に基づいてコール調節部２
１０におけるコール接続を設定するための過程が開始さ
れる。ここで、ＡＴＭセルのヘッダー情報は４ビットの
一般流れ制御フィールド（generic flow-control fiel
d; GFC）、８ビットの仮想経路識別子（virtual path i
dentifier;VPI）、16ビットの仮想チャンネル識別子（v
irtual channel identifier;VCI）、３ビットのペイロ
ード形態（payload type; PT）、１ビットのセル損失優
先順位（call loss priority; CLP）及びヘッダーエラ
ー制御（header error control; HEC）を備える。ＧＦ
Ｃは終端間の流れ制御に用いられ、幾つかの他の種類の
データの流れを制御するのに用いられる。ＶＰＩは使用
者間または使用者−網の間の仮想経路を表し、ＶＣＩは
使用者間または使用者−網の間の仮想チャンネルを表
し、ＰＴは情報フィールドの情報形態を表す。コール調
節部２１０は、接続によって要求されるサービスの質
（QOS: quality ofservice）を供給するために、どの網
資源が必要であるかを決定し、それらの網資源が有用で
あるかを検査し、その後、それらの資源を保持、管理す
る。保持を要する資源は、主に各ノードにおけるバッフ
ァ容量及び接続経路にある各リンクに対する帯域幅であ
る。ある接続が、要求されたＱＯＳに適切でないと、他
の接続が選択され、より低いＱＯＳにて交渉が再開され
る。例えば、コール調節部２１０は終端間のデッドライ
ンを増やし、ジッタ要求事項を緩和させ、最大トラフィ
ック率または可能なバースト大きさを減少させることが
できる。選択された接続ｊに対する情報は、カウンタ同
期化部２２０及び制御メモリ１３０に供給される。ここ
で、上記情報にはフレームの大きさＴ_j、接続ｊの上位
ノードｉと下位ノードｉ＋1との間の遅延限界ｄ_ij、及
び上位ノードｉと下位ノードｉ＋1との間の伝播遅延τ_i
を備える。Ｔ_j、ｄ_ij及びτ_iは各々タイムスロット単位
で表現される。

【００１６】本発明の好適な実施例において、接続ｊの
ノード全体にある全てのフレームカウンタはカウンタ同
期化部２２０において予め同期化される。カウンタ同期
化部２２０は、図３に示すカウンタプール１２０にある
接続ｊに対応するフレームカウンタを初期化させる。

【００１７】ＰＳＰＳフレーム方式において、隣接する
各ノード対のフレームの境界が整列されるので、上位ノ
ード、即ち、ノードｉのスケジューリング情報を下位ノ
ード、即ちノードｉ＋1に効果的に伝達することができ
る。整列過程は次のようなコール接続が設定される間に
反対方向に進行される可能性がある。宛先ノードのフレ
ームカウンタが活性化された後、宛先ノードのフレーム
カウンタにて隣接する上位ノードにカウント値が送られ
る。カウント値を受けるとすぐ、隣接する上位ノードは
コール接続に対応するフレームカウンタを、関連する伝
播遅延を反映する値に初期化する。隣接する各ノード対
に対して上記過程が反復し、ソースノードに到達するま
で上位ノードに転移が続けられる。

【００１８】このような初期化過程が終わると、フレー
ムカウンタはタイムスロットの比率でカウントダウンし
てフレームカウンタが「０」になるとすぐ、フレームサ
イズＴ_j（Ｔ_jは正の整数）にリセットされる。一旦、１
つの接続におけるフレームカウンタがコールの設定段階
にて上述したように同期化されると、各フレームカウン
タは接続が存続する限り独立的に動作するようになる。

【００１９】他の観点からみると、フレームカウンタが
各接続の単位で予め同期化されているので、１つのノー
ドから他のノードにスケジューリング情報を伝達せずに
各ノードにおけるセルの適格時刻を決定することができ
る。詳しくは、接続ｊの下位ノードｉ＋1におけるフレ
ームカウンタの到着カウント値ＡＣ_i+1 _、 _j ^kは、ＥＴ_i+1 _、 _j ^k＝ＥＴ_ij ^k＋ｄ_ij＋τ_i＝ＡＴ_i+1 _、 _j ^k＋ＡＣ
_i+1 _、 _j ^k である。ここで、ＥＴ_ij ^kは上位ノードｉにおける接続
ｊのセルに対する適格時刻、即ち、その時刻以後の上位
ノードｉにあるセルｋが下位ノードｉ+1に伝送され得る
仮想到着時刻を表し、ｄ_ijは上位ノードｉと下位ノード
ｉ+1との間における接続ｊの遅延限界であり、τ_iは上
位ノードｉと下位ノードｉ+1との間の伝播遅延であり、
ＡＴ_i+1 _、 _j ^kは接続ｊの下位ノードｉ+1におけるセルｋの
実際到着時刻であり、ＡＣ_i+1 _、 _j ^kは接続ｊの下位ノード
ｉ+1におけるセルｋの実際到着時刻ＡＴ_i+1 _、 _j ^kにおいて
対応するフレームカウンタを読込んで計算される到着カ
ウント値を表す。

【００２０】結果的に、接続ｊの下位ノードｉ+1におけ
るセルｋの適格時刻ＥＴ_i+1 _、 _j ^kは、接続ｊの下位ノード
ｉ+1におけるセルｋの実際到着時刻ＡＴ_i+1 _、 _j ^kとその実
際到着時刻ＡＴ_i+1 _、 _j ^kにおけるフレームカウンタの到着
カウント値ＡＣ_i+1 _、 _j ^kとの和で計算される。これは、セ
ルｋに対する到着カウント値ＡＣ_i+1 _、 _j ^kが接続ｊの下位
ノードｉ+1における適格時刻ＥＴ_i+1 _、 _j ^kの残余時間（Ｒ
Ｔ）を表すからである。

【００２１】接続ｊの各ノードごとに１つのフレームカ
ウンタが割当てられ、接続ｊの全ノードに設置された全
フレームカウンタが上述したようにパーセッションプリ
同期化過程によって予め同期化される。全フレームカウ
ンタに対する各カウント値は各タイムスロット単位また
は各サービス時間ごとに１つずつ減少し、全フレームカ
ウンタの各カウント値が「０」になるとすぐ、接続ｊの
フレームの大きさＴ_jにリセットされる。詳しくは、接
続ｊのノード全体にある全てのフレームカウンタが隣接
する２つのノードの間の伝播遅延を考慮して予め同期化
されて、セルが上位ノードｉからカウント値がＮである
時に出発する場合、そのセルは伝播遅延に相当する時間
の間に伝送された後、下位ノードｉ+1においても同じカ
ウント値Ｎを見るようになる。このような配列は、コー
ルの設定段階において対応する隣接ノードにフレームカ
ウンタに対する情報を伝送して形成され得る。このよう
にパーセッションプリ同期化されたフレームカウンタは
対応する接続が存続する限り同期が保持される。

【００２２】ノードｉにおけるフレームカウンタのカウ
ント値は２つの意味を有する。即ち、ノードｉにおいて
ジッタ制御部にある各セルに対する各カウント値は、適
格時刻までの残りの残余時間を意味し、適格時刻が過ぎ
た後予め定められたスケジューリング方式によってセル
がサービスされ得る。ノードｉにあるスケジューラにお
ける各セルに対する各カウント値は、デッドラインまで
の残りの他の残余時間を意味して、デッドラインになる
以前にセルがサービスされなければならない。例えば、
セルが上位ノードにおけるフレームカウンタが「３」で
ある時サービスされる場合、そのセルはデッドライン前
の３タイムスロットでサービスされることを意味する。
そのセルが下位ノードに到着する時、接続する下位ノー
ドにおけるフレームカウンタのカウント値は「３」にな
り、それに従ってそのセルはジッタ制御部にて３タイム
スロットの間に格納された後、スケジューラに入る。ス
ケジューラの観点からみると、下位ノードにあるセルは
まるで上位ノードにおける最大の遅延限界であったよう
にみなされる。即ち、あるセルが下位ノードにおけるス
ケジューラに入る時間は、上位ノードにおけるそのセル
のサービス時間と関係無しに一定に保たれる。

【００２３】上述した方式は、セルの適格時刻及びデッ
ドラインを計算する必要がなく、適格時刻及びデッドラ
インを格納する必要もない。遅延ジッタを調節し、スケ
ジューリング優先順位を決定するために同期化されたフ
レームカウンタのみを必要とする。同期化されたフレー
ムカウンタは、セルが現タイムスロットに到着するかま
たは出発するかには無関係であり、但し、出力リンクに
おけるセル伝送の可否のみに基づいて作動される。

【００２４】同期化されたフレームカウンタは、スケジ
ューリング情報を伝達するための別途のヘッダー空間を
要求せずに、効果的に遅延ジッタを調節する重要な役割
を果たすので、ＡＴＭ網における実時間サービスを可能
にする。

【００２５】図３を参照して、セル伝送ステップにおい
て、ヘッダー検出部１１０におけるＡＴＭセルの５オク
テットヘッダーを検出することによって、ＡＴＭセルが
複数のコールのうち、何れかの１つのコールに対応する
ことに決定されると、５オクテットヘッダーのＶＰＩ／
ＶＣＩに対する情報がカウンタプール１２０に伝達され
る。図３において、点線で示されているブロック１００
は、接続ｊのノードｉにあるセル伝送ブロックを表す。
カウンタプール１２０において、ＶＰＩ／ＶＣＩに対す
る情報に基づいて接続ｊのノードｉにおける対応する同
期化されたフレームカウンタが検出され、セルｋに対す
る到着カウント値ＡＣ_ij ^kを読込み、到着カウント値Ａ
Ｃ_ij ^kはジッタ調節部１４０に伝送される。セルｋはジ
ッタ調節部１４０に到着カウント値ＡＣ_ij ^kの間一時的
に格納され、伝送に適切な状態になり、その後スケジュ
ーリング部１５０に伝送される。

【００２６】一方、カウンタプール１２０は同期化され
たフレームカウンタのカウント値Ｃ_ij ^k-1をタイムスロ
ット単位でスケジューリング部１５０に供給する。ここ
で、カウント値Ｃ_ij ^k-1は接続ｊの上位ノードｉにおけ
る伝送適格である前セルk-1に対するカウント値であ
る。制御メモリ１３０は、フレーム大きさＴ_jと遅延限
界ｄ_ijとの間の差ｂ_ijをスケジューリング部１５０に伝
達する。スケジューリング部１５０は本発明によって前
セルk-1を出発カウント値ＤＣ_ij ^k-1とともに下位ノード
ｉ+1に伝送する。ここで、出発カウント値ＤＣ
_ij ^k-1は、前セルk-1が下位ノードｉ+1にサービスされる
時、上位ノードにあるフレームカウンタのカウント値を
表す。

【００２７】図４を参照しながら、遅延限界が接続ｊの
フレームの大きさＴ_jと同一である場合、ＰＳＰＳ技法
によってプリ同期化された各フレームカウンタを用いて
４つのノードを経てセルの伝送を説明する。各々の白い
矢印は対応するノードにおけるセルの実際の到着を表
し、各々の黒い矢印は対応するノードから次のノードへ
のセルの出発を表す。セルｋがノードｉ-1における到着
カウント値ＡＣ_i-1,j ^k＝2に実際に到着する場合、セル
ｋはノードｉ-1のジッタ制御部に到着カウント値ＡＣ
_i-1,j ^k＝2の間一時的に格納され、次のノードｉへの伝
送に適切な状態になる。ＰＳＰＳ技法によって下位ノー
ドｉに対する各到着カウント値ＡＣ_ij ^kは上位ノードｉ-
1に対する出発カウント値ＤＣ_i-1,j ^kより伝播遅延τ_i-1
だけ遅延されるので、セルｋが出発カウント値ＤＣ
_i-1,j ^k＝5における上位ノードｉ-1を離れると、そのセ
ルｋがノードｉに到着する時、到着カウント値ＡＣ_ij ^k
は「５」にならなければならない。セルｋがノードｉに
おける到着カウント値ＡＣ_ij ^k＝5だけ格納され伝送に適
切な状態になり、その後、出発カウント値ＤＣ_ij ^k＝7で
ある時、次のノードｉ+1に伝送される。

【００２８】一方、一般的なフレーム技法において、各
ノードにおける遅延限界がそれに対応する接続のフレー
ムの大きさに与えられ、フレームの大きさは対応する接
続に割当てられた帯域幅の逆数として決定される。従っ
て、帯域幅の割当は遅延限界と結合され、網資源の非効
率的な使用をもたらすようになる。このような非効率性
は帯域幅割当から遅延限界割当を分離することによって
多少緩和され得る。

【００２９】図５を参照すると、遅延限界ｄ_i-1,jがフ
レーム大きさＴ_jより小さい場合セルｋの伝送を説明し
ている。これは遅延限界から帯域幅割当を分離させる一
実施例である。適格時刻がＥＴ_ij ^kである時、接続ｊの
ノードｉにおけるセルｋのデッドラインは、ＥＴ_ij ^k +
Ｔ_jではないＥＴ_ij ^k +ｄ_ijになる。ここで、ｄ_ijは接続
ｊのノードｉにおける遅延限界であり、Ｔ_jは接続ｊの
フレーム大きさである。接続ｊの各ノードにある各フレ
ームカウンタはプリ同期化され、接続ｊの上位ノードｉ
-1におけるセルｋの出発カウント値がＤＣ_i-1,j ^kであれ
ば、そのセルｋは接続ｊの下位ノードｉに到着して到着
カウント値ＡＣ_ij ^k＝ＤＣ_i-1,j ^k−(Ｔ_j−ｄ_i-1,j) を読込む。

【００３０】各フレームカウンタがプリ同期化される
時、隣接する２つのノードの間に伝播遅延τ_i-1、接続
ｊの各ノードｉ-1における遅延限界ｄ_i-1,j、及び接続
ｊのフレーム大きさＴ_jが考慮されなければならないの
で、ＰＳＰＳ技法によって下位ノードｉ-1に対する各到
着カウント値ＡＣ_ij ^kは上位ノードｉ-1に対する対応す
る出発カウント値ＤＣ_i-1,j ^kよりτ_i-1−(Ｔ_j−
ｄ_i-1,j)だけ遅延される。

【００３１】接続ｊのフレームの大きさＴ_jが「１０」
であり、接続ｊのノードｉ-1、ｉ及びｉ+1における遅延
限界ｄ_i-1,j、ｄ_ij及びｄ_i+1,jは、各々「９」、「５」
及び「７」とする。セルｋが出発カウント値ＤＣ_i-1,j ^k
＝5である時ノードｉ-1を離れる場合、そのセルｋがノ
ードｉに到着する時の到着カウント値ＡＣ_ij ^kは「４」
(=5-(10-9))でなければならない。その後、セルｋが到
着カウント値ＡＣ_ij ^k＝4の間格納され伝送に適切な状態
になり、出発カウント値ＤＣ_ij ^k＝6におけるノードｉ+1
に伝送され、ノードｉ+1における到着カウント値ＡＣ
_i+1,j ^kが「１」(=6-(10-5))であることが分かる。セル
ｋの適格時刻は、ノードｉへのセルの到着時刻における
対応するフレームカウンタを読込むだけのことで決定さ
せ得る。

【００３２】本発明はパーセッションフレーム技法を採
択するので、フレーム方式に固有の結合問題を解決する
ことができる。更に、フレーム大きさ及びサービス単位
を調整し、各遅延限界に対応するオフセットで各フレー
ムカウンタを同期化することによって、遅延限界を帯域
幅から分離させることができ、それに従って網資源の流
動的な割当を可能にする。

【００３３】図６は、本発明によってノードｉにおける
接続n+1に対するＰＳＰＳ動的優先順位キューイング方
式でセルを調節しスケジューリングする装置に対するブ
ロック図である。ノードｉに、ｎチャンネルの遅延限界
トラフィック及び１チャンネルの遅延無関トラフィック
があると仮定する。その装置は実時間サービスのための
ｎ個の遅延限界トラフィックキュー10-1〜10-n、１個の
遅延無関トラフィックキュー１９、マルチプレクサ（Ｍ
ＵＸ）２０、ｎ個の残余時間（ＲＴ）発生部30-1〜30-
n、及び比較器４０を備える。

【００３４】各々の遅延限界トラフィックキュー10-1〜
10-nは、対応する制御部、即ちジッタ制御部11-1〜11-n
のうちの１つと対応するスケジューリング検出部12-1〜
12-nのうちの１つを有する。各々の制御部11-1〜11-n
は、接続1〜nのうちに特定の接続に属するセルが仮想チ
ャンネル（VC₁〜VC₂）のうち対応する１つの仮想チャン
ネルを経て入力されるようにし、そのセルを対応する適
格時刻まで格納し、その後、そのセルをスケジューリン
グ検出部12-1〜12-nのうち対応する１つのスケジューリ
ング検出部及びＭＵＸ２０に送る。ここで、全ての接続
1〜nは、上位ノードｉ及びその下位ノードｉ+1を通過
し、１つのセルに対する適格時刻はそのセルを有するフ
レームの終了時刻を表す。各スケジューリング検出部12
-1〜12-nは、プリ同期化されたフレームカウンタを調査
して、タイムスロット単位で減少するカウント値Ｃ_ij ^k
を読込み、空フラグ（empty flag）ＥＦ_ij ^kを生成す
る。ここで、空フラグＥＦ_ij ^kは、伝送され得るセルが
存在するかの可否を表す。対応するスケジューリング検
出部12-jから供給されるカウント値Ｃ_ij ^k及び空フラグ
ＥＦ_ijだけではなく、図３に示されている制御メモリ１
３０から供給されるフレームの大きさＴ_jと遅延限界ｄ
_ijとの差Ｂ_ijが、対応する各残余時間（ＲＴ）生成器30
-1〜30-nに供給される。ここで、ｊはｎ以下の正の整数
である。各ＲＴ生成器30-jは、カウント値Ｃ_ij、空フラ
グＥＦ_ij及び差Ｂ_ijに基づいて、残余時間ＲＴ_ij ^kを生
成する。ここで、残余時間ＲＴ_ijは適格時刻から計算さ
れたセルの遅延限界の終了時刻を表す。

【００３５】図７を参照すると、図６に示す各々の実時
間接続ｊに対するｊ番目の遅延限界トラフィックキュー
及びｊ番目の残余時間（ＲＴ）生成器のブロック図を示
されている。遅延限界トラフィックキューは、第１及び
第２先入れ先出し（FIFO: first in first out）キュー
１１、１２と、第１及び第２空検出部１３、１４と、入
力及び出力トグルスイッチ１５、１６と、スイッチ制御
部１７と、同期化されたフレームカウンタ１８とを備え
る。

【００３６】最初、接続ｊのノードｉに対する同期化さ
れたフレームカウンタ１８が、上述したようにＰＳＰＳ
過程による同期信号によってプリ同期化される。ここ
で、図３に示すカウンタ同期化部２２０から供給された
同期化信号は隣接する２つのノード、即ち、ノードｉと
ノードｉ+1との間の伝播遅延τ_i、接続ｊの各ノードｉ
における遅延限界ｄ_ij、及び接続ｊのフレーム大きさＴ
_jを考慮し、ノードｉにおけるフレームカウンタ１８の
各カウント値は、各タイムスロットまたは各サービス時
間に１つずつ減少しつつ、カウント値が「０」になると
同時に接続ｊのフレームの大きさＴ_jにリセットされ
る。各カウント値が減少するごとに、各カウント値はス
イッチ制御部１７及び拡張カウンタ３１に供給される。
各カウント値がフレーム大きさＴ_jにリセットされる
時、スイッチ制御部１７はスイッチング信号を生成し
て、周期がフレーム大きさＴ_jであるスイッチング信号
が入力及び出力スイッチ１５、１６に供給される。

【００３７】一方、入力スイッチ１５において、接続ｊ
のノードｉに対する仮想チャンネルＶＣ_ijは、スイッチ
制御部１７から供給されたスイッチング信号によって第
１及び第２ＦＩＦＯキューに選択的に接続される。ま
た、第１ＦＩＦＯキュー１１の入力がスイッチング信号
によって図７において実線の矢印で示すように仮想チャ
ンネルＶＣ_ijに接続されると、出力スイッチ１６におい
て、第２ＦＩＦＯキュー１２の出力がＭＵＸ２０に接続
される。反対に、第２ＦＩＦＯキュー１２の入力が、図
７において点線の矢印で示すように接続されれば、第１
ＦＩＦＯキュー１１の出力がＭＵＸ２０に接続される。
言換えれば、第１及び第２ＦＩＦＯキュー１１、１２
は、論理的に分離され、一方のＦＩＦＯキューが伝送の
ためスケジューリングされる準備ができた適格セルを格
納する間、他方のＦＩＦＯキューは適切な状態でない、
即ち、フレーム時間の端までジッタ調節されなければな
らないセルを格納する。

【００３８】また、第１及び第２ＦＩＦＯキュー１１、
１２の出力は、各々、第１及び第２空検出部１３、１４
に接続される。第１及び第２空検出部１３、１４は、各
々第１及び第２ＦＩＦＯキュー１１、１２が空いている
か否か、即ち第１及び第２ＦＩＦＯキュー１１、１２に
伝送されるセルが存在するか否かを検出する。１つのセ
ルが予めスケジューリング方式によって伝送されていた
か、若しくは上位ノードから対応するＦＩＦＯキューに
ジッタ調節されるためのセルが入力されていない場合、
空フラグＥＦ_ij＝「１」が拡張カウンタ３１の前段に供給
され、対応するＦＩＦＯキューに伝送するためのセルが
存在する場合、空フラグＥＦ_ij＝「０」に供給される。ま
た、出力スイッチ１６において、第１ＦＩＦＯキュー１
１がＭＵＸ２０に接続されれば、第１空検出部１３の空
フラグＥＦ_ijがスイッチング信号によって拡張カウンタ
３１の前段に供給され加えられ、第２ＦＩＦＯキュー１
２がＭＵＸ２０に接続されれば、第２空検出部１４の空
フラグＥＦ_ijが拡張カウンタ３１の前段に供給され加え
られる。

【００３９】拡張カウンタ３１は空フラグＥＦ_ijとカウ
ント値Ｃ_ij ^kとを格納する。同期化されたフレームカウ
ンタ１８から供給されたカウント値Ｃ_ij ^kは、各タイム
スロットに１つずつ減少し、「０」になると同時にフレ
ームの大きさＴ_jにリセットされ、カウント値Ｃ_ij ^kがフ
レームの大きさＴ_jの周期で変化するようになる。１ビ
ット「０」または「１」である空フラグＥＦ_ij ^kは、拡張カ
ウンタ３１におけるカウント値Ｃ_ij ^kに加えられて拡張
カウント値ＥＣ_ij ^kを生成することによって、空フラグ
ＥＦ_ij ^k＝1を有する空キューが適格セルを有する他のキ
ューより低い優先順位を備えるようにするのが望まし
い。減算器３２において、拡張カウント値ＥＣ_ij ^kから
フレーム大きさＴ_jと遅延限界ｄ_ijとの間の差Ｂ_ijが減
算され、接続ｊのノードｉにおけるセルｋの残余時間Ｒ
Ｔ_ij ^kが生成される。ここで、残余時間ＲＴ_ij ^kは、キュ
ーにおけるデッドラインまでの残りの時間を表す。残余
時間ＲＴ_ij ^kは比較器４０に供給される。

【００４０】図６を再び参照すると、比較器４０はタイ
ムスロットごとに全ての接続ｊに対する全ての残余時間
ＲＴ_ij ^kを比較し、最小残余時間ＲＴ_ij ^kを対応する接続
ｊとともに選択し、最小残余時間ＲＴ_ij ^kに対応する仮
想チャンネル選択信号ＶＣ_ＳＥＬを生成する。比較器
４０は、１つのノードを通過する全ての接続と関連され
ており、１タイムスロット内に比較機能を行わなければ
ならないので複雑な構造を有しなければならない。比較
器４０が２つの入力比較器の多ステップ構造を有すると
すれば、接続数Ｍである場合、比較作用は［logＭ］の
複雑さを有する。ここで、［］は、被演算数以上の最小
整数を求める演算子である。しかしながら、比較機能は
接続の数のみに関連され、全体のセルの個数には無関係
であるので、そのように難しい計算は伴わない。例え
ば、１Ｇbpsリンク帯域幅及び64kbpsの最小接続率を有
するＡＴＭ網を考慮してみよう。最悪の場合において最
大の接続数Ｍが15,625であるので、１４番の比較作用に
おけるデッドラインのセルを決定することが可能にな
る。１タイムスロット、例えば、424ns内に比較作用を
行うために、30nsの程度に２つの１５ビットの単語を比
較しなければならない。これは現在の技術水準で可能な
範囲である。このような例は、比較作用がＰＳＰＳサー
ビス方式の実行において障害にならないことを表す。

【００４１】図６に示すＶＣ_ＳＥＬ信号は、ＭＵＸ２
０に供給される。このＭＵＸ２０に対応するキューに格
納されたセルデータに対する接続識別子（CID: connect
ionidentifier）を出力することによって、ＶＣ_ＳＥＬ
信号に対応するセルｋを次のノードｉ+1に伝送する。実
時間接続に対する全てのキューが空いている場合、即
ち、全ての空フラグＥＦ_ijが「１」であるので伝送される
セルがないとすれば、実時間連続に対する遅延無関トラ
フィックキュー１９から遅延無関知セルが選択されＭＵ
Ｘ２０に供給される。

【００４２】図８は、本発明によるＡＴＭ系において、
フレームカウンタを用いて生成されたＰＳＰＳフレーム
に基づいて接続ｊのノードｉにおけるセルｋの動的優先
順位キューイング方式に対する流れ図を表す。ステップ
Ｓ１０において、ＡＴＭセルが到着すると、ステップＳ
１１にてセルのヘッダーが検出され、ステップＳ１２に
て、ＡＴＭセルに対するコールが存在するか否かが検出
される。ＡＴＭセルに対するコールがない場合、ステッ
プＳ１３にて、複数のノードを貫通するＡＴＭセルに対
するコール接続ｊが設定され、ステップＳ１４にて、本
発明によるＰＳＰＳ技法を用いて各ノードにある各カウ
ンタが接続単位でプリ同期化される。その後、ステップ
Ｓ１８において、セルがスケジューリングされて伝送さ
れる。

【００４３】一方、ＡＴＭセルに対するコールが存在す
る場合、ステップＳ１５において、セルが遅延無関知ト
ラフィックに該当するか否かが検出される。セルが遅延
に無関知である場合、セルはステップＳ１８にて、直接
スケジューリングされ伝送される。そうでない場合、接
続ｊのノードｉにおけるセルｋに対する到着カウント値
ＡＣ_ij ^kが、ジッタ調節のために同期化されたフレーム
カウンタから検出され、ステップＳ１７にて、セルｋが
到着カウント値ＡＣ_ij ^kの間にジッタ調節され、その
後、ステップＳ１８においてスケジューリングされ伝送
される。

【００４４】図９には、１つのノードにおける全ての接
続の全てのセルに対するスケジューリング過程に対する
流れ図が示されており、各実時間接続ごとに各同期化さ
れたフレームカウンタが割当てられている。まず、ステ
ップＳ２０において、全ての接続が調査され１つ以上の
実時間セルが存在するか否かが判断される。

【００４５】実時間セル、即ち遅延限界セルがない場
合、ステップＳ２６にて遅延無関知セルが存在するか否
かが調査される。ここで、遅延無関知セルは、その伝送
時間が重要ではないので、いつでも伝送さえされればい
い。遅延無関知セルが存在することが調査されると、ス
テップＳ２７において、遅延無関知セルが次のノードｉ
+1に供給される。そうでない場合には、そのタイムスロ
ットにはどんなセルも伝送されない。

【００４６】ステップＳ２０において１つ以上の実時間
セルが検出される場合、ノードｉにおける各実時間接続
ごとに接続単位別に同期化されたフレームカウンタを有
するので、ステップＳ２１にて１つ以上の伝送のための
実時間セルに有する全ての接続ｊに対するカウント値Ｃ
_ij ^kが検出される。ステップＳ２２において、全ての接
続ｊに対する残余時間ＲＴ_ij ^kが、カウント値Ｃ_ij ^k、フ
レーム大きさＴ_j及び遅延限界ｄ_ijに基づいて計算さ
れ、ステップＳ２３において最小残余時間ＲＴ_ij ^kが選
択され、ステップＳ２４において最小残余時間ＲＴ_ij ^k
に該当するセルが次のノードｉ+1にサービスされる。

【００４７】図１０には、１つのノードｉにおける２つ
の遅延限界接続と１つの遅延無関知接続に対する例示的
なスケジューリング表が示されている。ここで、第１及
び第２接続ｊ=1及びｊ=2に対する遅延限界は、各々ｄ_i1
=4及びｄ_i2=3であり、第３接続ｊ=3は遅延に無関係であ
る。時間はタイムスロット単位に変化すると仮定する。
接続１のセルｋ₁がタイムスロット「０」に到着カウント
値ＡＣ_ij ^k =1である時到着すれば、そのセルｋ₁は１タ
イムスロットの間にジッタ調節され、タイムスロット
「１」である時が伝送に適切な状態になり、タイムスロッ
ト「０」である時到着カウント値ＡＣ_i2 ^k =1の状態に到着
する接続２のセルｋ₂も１タイムスロットの間にジッタ
が調節され伝送に適切な状態になる。

【００４８】タイムスロット「１」である時、接続１の
カウント値Ｃ_i1 ^k =4と接続２のカウント値Ｃ_i2 ^k =3とが
互いに比較された後、最小カウント値「３」が選択され接
続２のセルｋ₂が出発カウント値ＤＣ_i2 ^k =3とともに次
のノードｉ+1にサービスされる。また、接続３のセルｋ
₃もタイムスロット「１」である時到着する。タイムスロ
ット「２」である時、接続２には伝送されるべきセルが存
在しないので、空フラグＥＦ_i2 ^k=「１」が生成される反
面、接続１のセルｋ₁はスケジューリングされ出発カウ
ント値ＤＣ_i1 ^k =3である時ノードｉ+1にサービスされ
る。到着カウント値ＡＣ_i2 ^k+1 =2である時到着された接
続２の他のセル(ｋ+1)₂は２タイムスロットの間に調節
されタイムスロット「４」である時が伝送に適切な状態に
なる。タイムスロット「３」において、接続１及び接続２
には伝送されるセルが存在しない。これは接続１にある
セルｋ₁は予め伝送される反面、接続２にあるセル(ｋ+
1)₂はジッタ調節中にあるからである。従って、遅延無
関知トラフィックにあるセルｋ₃がタイムスロット「３」
である時スケジューリングされ伝送される。タイムスロ
ット「４」において、接続２にあるセル(ｋ+1)₂がスケジ
ューリングされ出発カウント値ＤＣ_i2 ^k+1 =3である時次
のノードｉ+1に伝送される。

【００４９】上記において、本発明の好適な実施の形態
について説明したが、本発明の請求範囲を逸脱すること
なく、当業者は種々の改変をなし得るであろう。

【００５０】

【発明の効果】従って、本発明によれば、上位ノードか
ら下位ノードへスケジューリング情報を伝達するための
ヘッダー空間がなくても、終端間遅延及び遅延ジッタを
補償してＡＴＭ網において無混雑実時間通信サービスで
セルをスケジューリングすることができる。

【図面の簡単な説明】

【図１】通常のジッタＥＤＤ（jitter earliest-due-da
te）規則を説明するための模式図。

【図２】複数のノードから構成される網に対する１つの
例示図。

【図３】本発明によるコール設定及びセル伝送を行う装
置に対するブロック図。

【図４】本発明による遅延限界がフレーム大きさと同一
である場合、コールの設定段階においてカウンタの間に
パーセッションプリ同期化（per-session pre-synchron
ization）の第１実施例を示す図面。

【図５】本発明によって、遅延限界がフレーム大きさよ
り小さい場合、コールの設定段階においてカウンタの間
にパーセッションプリ同期化の第２実施例を示す模式
図。

【図６】本発明によって、ノードｉにおけるn+1個の接
続に対するＰＳＰＳ動的優先順位のキューイング方式を
用いてセル調節及びスケジューリング装置に対するブロ
ック図。

【図７】図６において接続ｊに対するｊ番目の遅延境界
及びｊ番目の残余時間（ＲＴ）生成器に対するブロック
図。

【図８】本発明によるＡＴＭ系において、フレームカウ
ンタを用いて形成されたパーセッションプリ同期化（Ｐ
ＳＰＳ）フレーム法に基づいて動的優先順位キューイン
グ方式に対する流れ図。

【図９】全ての実時間接続の同期化されたフレームカウ
ンタを用いる図８のスケジューリングステップに対する
流れ図。

【図１０】ノードｉにおいて、２つの遅延限界接続及び
１つの遅延無関接続に対するスケジューリング表の一実
施例を示す模式図。

【符号の説明】

１０−１〜１０−ｎ遅延限界トラフィックキュー１１第１先入れ先出し（ＦＩＦＯ）キュー１１−１〜１１−ｎジッタ制御部１２第２先入れ先出し（ＦＩＦＯ）キュー１２−１〜１２−ｎスケジューリング検出部１３第１空検出部１４第２空検出部１５入力トグルスイッチ１６出力トグルスイッチ１７スイッチ制御部１８フレームカウンタ１９遅延無関トラフィックキュー２０マルチプレクサ（ＭＵＸ）３０−１〜３０−ｎ残余時間発生部３１拡張カウンタ３２減算器４０比較器１００セル伝送ブロック１１０ヘッダー検出部１２０カウンタプール１３０制御メモリ１４０ジッタ調節部１５０スケジューリング部２１０コール調節部２２０カウンタ同期化部

Claims

【特許請求の範囲】

【請求項１】ソースノード及び宛先ノードを有する
複数のノードを結んで形成された接続を通じてコールの
複数のセルをスケジューリングするセルスケジューリン
グ装置であって、前記コールに対して、Ｍが正の整数である時、各々が予
め定められた時間間隔であるＭ個のタイムスロットから
なるフレームの大きさを決定するフレーム大きさ決定手
段と、前記ソースノードの方に位置する上位ノード及び前記宛
先ノードの方に位置する下位ノードからなる隣接する各
ノード対において、両ノードの間に対する各伝播遅延及
び遅延限界を検出する遅延情報検出手段であって、前記
伝播遅延はセルの伝播の際、複数のタイムスロットを表
し、前記遅延限界はＰが正の整数である時、前記セルが
前記上位ノードにおいて伝送に適切な状態になった後か
ら、前記下位ノードにサービスされる前のＰ個のタイム
スロットを表す、前記遅延情報検出手段と、各接続の各ノードごとに１つずつ割当てられ、前記フレ
ーム大きさをリセットするために、伝播遅延及び遅延限
界に基づいて接続単位でプリ同期化され、各フレームの
タイムスロットをカウンタダウンして、タイムスロット
単位にカウント値を生成する複数のフレームカウンタで
あって、前記上位ノードにおいて前記フレームカウンタ
によってカウントされた各上位カウント値が、前記下位
ノードにおいて前記フレームカウンタによってカウント
された下位カウント値と相関関係にある、前記複数のフ
レームカウンタと、前記フレームカウンタのカウント値がフレーム大きさに
リセットされる時、フレーム大きさの周期に従ってスイ
ッチング信号を生成するスイッチ制御部と、前記接続ごとに同期化され、前記フレームカウンタのカ
ウント値及び前記切換え信号に基づいて、セルを調整、
スケジューリングする同期化スケジューラとを含むこと
を特徴とするセルスケジューリング装置。
【請求項２】前記同期化スケジューラが、一方のＦ
ＩＦＯキューが伝送のためにスケジューリングされる準
備ができた適格セルを格納し、他方のＦＩＦＯキューが
前記フレーム大きさの端までジッタ調節されるべき非適
格セルを格納する、論理的に分離された二つの先入れ先
出し（ＦＩＦＯ）キューを備えることを特徴とする請求
項１に記載のセルスケジューリング装置。
【請求項３】一方のＦＩＦＯキューが、前記上位ノ
ードに各非適格セルが到着した後、前記上位ノードにお
ける前記フレームカウンタの前記上位カウント値が前記
非適格セルが到着したフレームの前記フレーム大きさに
リセットされるまで前記非適格セルを保持し、他方のＦ
ＩＦＯキューが、前記上位ノードにおける前記フレーム
カウンタの前記上位カウント値がフレームの前記フレー
ム大きさにリセットされる以前に、前記適格セルの各々
を前記上位ノードからそれに対応する下位ノードに伝送
することを特徴とする請求項２に記載のセルスケジュー
リング装置。
【請求項４】１つのノードにおけるセルに対する到
着カウント値が、前記ノードにおいてセル到着と同時に
前記フレームカウンタから読み出され、伝送のための適
格時刻までの残余時間を表し、前記残余時間の経過後、
前記セルが予め決められたスケジューリング方式によっ
てサービス可能であり、前記ノードにおけるセルに対する出発カウント値が、記
出発カウント値は前記上位ノードから前記下位ノードへ
の前記セルの出発と同時に前記上位ノードにおける前記
フレームカウンタから読み出され、前記セルの遅延限界
までの他の残余時間を表し、前記残余時間の以前に前記
セルがサービス可能であることを特徴とする請求項２に
記載のセルスケジューリング装置。
【請求項５】ＥＴ_i+1 _、 _j ^kが上位ノードｉにおけるセ
ルｋが下位ノードｉ+1に伝送可能な状態で、前記上位ノ
ードｉにおける接続ｊの前記セルｋに対する適格時刻
（仮想到着時刻層）を表し、ｄ_ijが前記上位ノードｉと
前記下位ノードｉ+1との間における前記接続ｊの遅延限
界であり、τ_iが前記上位ノードｉと前記下位ノードｉ+
1との間の伝播遅延であり、ＡＴ_i+1 _、 _j ^kが前記接続ｊの
前記下位ノードｉ+1におけるセルｋの実際の到着時刻で
あり、ＡＣ_i+1 _、 _j ^kが前記接続ｊの下位ノードｉ+1におけ
るセルｋの実際の到着時刻ＡＴ_i+1 _、 _j ^kにおいて、対応す
るフレームカウンタから読み出される到着カウント値を
表す時、接続ｊの前記下位ノードｉ+1における前記フレ
ームカウンタの到着カウント値ＡＣ_i+1 _、 _j ^kが、ＥＴ_i+1 _、 _j ^k＝ＥＴ_ij ^k＋ｄ_ij＋τ_i＝ＡＴ_i+1 _、 _j ^k＋ＡＣ
_i+1 _、 _j ^k のように定義されることを特徴とする請求項４に記載の
セルスケジューリング装置。
【請求項６】ＤＣ_ij ^kが接続ｊの前記上位ノードｉ
におけるセルｋの出発時間をカウントした出発カウント
値を表し、Ｔ_jが前記接続ｊのフレーム大きさであり、
ｄ_ijが前記接続ｊの前記上位ノードｉと前記下位ノード
ｉ+1との間の遅延限界である時、接続ｊの現ノードｉに
おけるセルｋの到着カウント値ＡＣ_i+1 _、 _j ^kが、ＡＣ_i+1 _、 _j ^k＝ＤＣ_ij ^k−(Ｔ_j−ｄ_ij) のように定義されることを特徴とする請求項４に記載の
セルスケジューリング装置。
【請求項７】前記同期化スケジューラが、前記上位ノードにおける各接続の適格セルに対して、前
記適格セルがサービス可能になるべき前記遅延限界まで
のタイムスロットの数を表す残余時間をタイムスロット
単位で計算する残余時間計算手段と、前記上位ノードにおける前記対応する接続の全ての適格
セルの残余時間を互いに比較する残余時間比較手段と、全ての残余時間のうち最小の残余時間を選択して、タイ
ムスロット単位で前記最小の残余時間に対応する前記適
格セルを伝送する最小残余時間選択手段とを、更に備え
ることを特徴とする請求項４に記載のセルスケジューリ
ング装置。
【請求項８】前記残余時間計算手段が、前記上位ノードにおける各接続に対して、伝送に適格な
前記適格セルが存在するか否かを表す空信号をタイムス
ロット単位で生成する空信号生成部と、各接続の拡張カウント値をタイムスロット単位で格納す
る格納手段であって、前記拡張カウント値は各フレーム
カウンタのカウント値であり、これらのフレームカウン
タは前記各空信号によって予め決まる、前記格納部と、各接続のフレーム大きさと前記上位ノードにおける前記
接続に対する各遅延限界との間の差を計算する差値計算
部と、前記拡張カウント値から前記各差を減算して前記対応す
る残余時間を発生する減算部とを有することを特徴とす
る請求項７に記載のセルスケジューリング装置。