(57)【特許請求の範囲】
【請求項１】
ソースノード及び宛先ノードを有する複数のノードを結んで形成された接続を通じてコールの複数のセルをスケジューリングするセルスケジューリング装置であって、
前記コールに対して、Ｍが正の整数である時、各々が予め定められた時間間隔であるＭ個のタイムスロットからなるフレームの大きさを決定するフレーム大きさ決定手段と、
前記ソースノードの方に位置する上位ノード及び前記宛先ノードの方に位置する下位ノードからなる隣接する各ノード対において、両ノードの間に対する各伝播遅延及び遅延限界を検出する遅延情報検出手段であって、前記伝播遅延はセルの伝播の際、複数のタイムスロットを表し、前記遅延限界はＰが正の整数である時、前記セルが前記上位ノードにおいて伝送に適切な状態になった後から、前記下位ノードにサービスされる前のＰ個のタイムスロットを表す、前記遅延情報検出手段と、
各接続の各ノードごとに１つずつ割当てられ、前記フレーム大きさをリセットするために、伝播遅延及び遅延限界に基づいて接続単位でプリ同期化され、各フレームのタイムスロットをカウンタダウンして、タイムスロット単位にカウント値を生成する複数のフレームカウンタであって、前記上位ノードにおいて前記フレームカウンタによってカウントされた各上位カウント値が、前記下位ノードにおいて前記フレームカウンタによってカウントされた下位カウント値と相関関係にある、前記複数のフレームカウンタと、
前記フレームカウンタのカウント値がフレーム大きさにリセットされる時、フレーム大きさの周期に従ってスイッチング信号を生成するスイッチ制御部と、
前記接続ごとに同期化され、前記フレームカウンタのカウント値及び前記切換え信号に基づいて、セルを調整、スケジューリングする同期化スケジューラとを含むことを特徴とするセルスケジューリング装置。
【請求項２】
前記同期化スケジューラが、一方のＦＩＦＯキューが伝送のためにスケジューリングされる準備ができた適格セルを格納し、他方のＦＩＦＯキューが前記フレーム大きさの端までジッタ調節されるべき非適格セルを格納する、論理的に分離された二つの先入れ先出し（ＦＩＦＯ）キューを備えることを特徴とする請求項１に記載のセルスケジューリング装置。
【請求項３】
一方のＦＩＦＯキューが、前記上位ノードに各非適格セルが到着した後、前記上位ノードにおける前記フレームカウンタの前記上位カウント値が前記非適格セルが到着したフレームの前記フレーム大きさにリセットされるまで前記非適格セルを保持し、他方のＦＩＦＯキューが、前記上位ノードにおける前記フレームカウンタの前記上位カウント値がフレームの前記フレーム大きさにリセットされる以前に、前記適格セルの各々を前記上位ノードからそれに対応する下位ノードに伝送することを特徴とする請求項２に記載のセルスケジューリング装置。
【請求項４】
１つのノードにおけるセルに対する到着カウント値が、前記ノードにおいてセル到着と同時に前記フレームカウンタから読み出され、伝送のための適格時刻までの残余時間を表し、前記残余時間の経過後、前記セルが予め決められたスケジューリング方式によってサービス可能であり、
前記ノードにおけるセルに対する出発カウント値が、記出発カウント値は前記上位ノードから前記下位ノードへの前記セルの出発と同時に前記上位ノードにおける前記フレームカウンタから読み出され、前記セルの遅延限界までの他の残余時間を表し、前記残余時間の以前に前記セルがサービス可能であることを特徴とする請求項２に記載のセルスケジューリング装置。
【請求項５】
ＥＴi+1、jkが上位ノードｉにおけるセルｋが下位ノードｉ+1に伝送可能な状態で、前記上位ノードｉにおける接続ｊの前記セルｋに対する適格時刻（仮想到着時刻層）を表し、ｄijが前記上位ノードｉと前記下位ノードｉ+1との間における前記接続ｊの遅延限界であり、τiが前記上位ノードｉと前記下位ノードｉ+1との間の伝播遅延であり、ＡＴi+1、jkが前記接続ｊの前記下位ノードｉ+1におけるセルｋの実際の到着時刻であり、ＡＣi+1、jkが前記接続ｊの下位ノードｉ+1におけるセルｋの実際の到着時刻ＡＴi+1、jkにおいて、対応するフレームカウンタから読み出される到着カウント値を表す時、接続ｊの前記下位ノードｉ+1における前記フレームカウンタの到着カウント値ＡＣi+1、jkが、
ＥＴi+1、jk＝ＥＴijk＋ｄij＋τi＝ＡＴi+1、jk＋ＡＣi+1、jk
のように定義されることを特徴とする請求項４に記載のセルスケジューリング装置。
【請求項６】
ＤＣijkが接続ｊの前記上位ノードｉにおけるセルｋの出発時間をカウントした出発カウント値を表し、Ｔjが前記接続ｊのフレーム大きさであり、ｄijが前記接続ｊの前記上位ノードｉと前記下位ノードｉ+1との間の遅延限界である時、接続ｊの現ノードｉにおけるセルｋの到着カウント値ＡＣi+1、jkが、
ＡＣi+1、jk＝ＤＣijk−(Ｔj−ｄij)
のように定義されることを特徴とする請求項４に記載のセルスケジューリング装置。
【請求項７】
前記同期化スケジューラが、
前記上位ノードにおける各接続の適格セルに対して、前記適格セルがサービス可能になるべき前記遅延限界までのタイムスロットの数を表す残余時間をタイムスロット単位で計算する残余時間計算手段と、
前記上位ノードにおける前記対応する接続の全ての適格セルの残余時間を互いに比較する残余時間比較手段と、
全ての残余時間のうち最小の残余時間を選択して、タイムスロット単位で前記最小の残余時間に対応する前記適格セルを伝送する最小残余時間選択手段とを、更に備えることを特徴とする請求項４に記載のセルスケジューリング装置。
【請求項８】
前記残余時間計算手段が、
前記上位ノードにおける各接続に対して、伝送に適格な前記適格セルが存在するか否かを表す空信号をタイムスロット単位で生成する空信号生成部と、
各接続の拡張カウント値をタイムスロット単位で格納する格納手段であって、前記拡張カウント値は各フレームカウンタのカウント値であり、これらのフレームカウンタは前記各空信号によって予め決まる、前記格納部と、
各接続のフレーム大きさと前記上位ノードにおける前記接続に対する各遅延限界との間の差を計算する差値計算部と、
前記拡張カウント値から前記各差を減算して前記対応する残余時間を発生する減算部とを有することを特徴とする請求項７に記載のセルスケジューリング装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ＡＴＭ網において実時間サービスでセルをスケジューリングするセルスケジューリング装置に関し、特に、プリ同期化されたフレームに基づいてスケジューリング情報をノード間に伝送せずに、保証された終端間遅延及び遅延ジッタを提供し得るセルスケジューリング装置に関する。
【０００２】
【従来の技術】
広帯域総合通信網（Ｂ−ＩＳＤＮ）は、広帯域伝送及びスイッチング技法に基づいて、集中または分散されている使用者たちをサーバーと接続することによって、連続的な実時間サービス及び集団データサービスなどのような多様なサービスを提供するディジタル網である。そのようなＢ−ＩＳＤＮにおいて、非同期伝送モード（ＡＴＭ）技法は使用者網インタフェースを通じて情報を伝達するのに用いられる。ＡＴＭ技法はパケットベース非同期時分割多重化技法として、通常の回路スイッチング技法及びパケットスイッチング技法ともを用い、多様な類型のサービスを処理することができる。
【０００３】
将来のＡＴＭ網は、現在のサービスより質、量共に非常に異なるトラフィック特性を有する予測不可能な大規模サービスを要求するであろう。そのようなサービスは、例えば、スループット、遅延、ジッタ及び損率を補償しなければならない。また、オーディオやビデオのような実時間サービスが広帯域網において主なサービスになるにつれ、遅延及びジッタに対する要求は段々増大されている。実時間情報は制限時間内に伝達されなければ損失されたものとみなされるので、遅延及びジッタに対する要求を効果的に満足させることが更に肝要になっている。
【０００４】
高速パケットスイッチング網において実時間通信サービスを支援し得るように、キューイング方式に対する研究案が活発に報告されてきた。それら研究案は作業保存方式と非作業保存方式とに分類される。作業保存方式を有する網においては、接続が網の入口において使用者定義のレート制限条件を満足させるにもかかわらず、以前のノードにおける網負荷変動は接続のトラフィックのパターンを歪曲させ、幾つかのノードにおいて瞬間的なレートの上昇を引起こす。接続におけるトラフィックの突発は、ソースノードから宛先ノードまでの接続経路に沿って累積される傾向があり、従って、後方に位置したノードに対して資源が更に必要となる。
【０００５】
このような問題点を解決するため、幾つかの非作業保存方式のパケットサービス規則が提案されていて、中間ノードにおけるパケットジッタを制御してトラフィックの突発を防いでいる。典型的な例として、階層的ラウンドロビン（HRR: hierarchical round robin）法及びストップアンドゴー（stop-and-go）法がある。これは時間軸を一定の長さのフレームに分けて、各接続に幾つかの分割フレームを割当てる。このようなフレーミング方式において、パケットサービスは割当てられた時間フレームに対してのみ可能であるので、遅延ジッタを制限することができる。しかしながら、帯域幅割当と遅延制限との間の結合問題は帯域幅の利用効率を低下させる。ジッタＥＤＤ（Earliest-Due-Date）及びレート制御静的優先順位（RCSP：rate-controlled static priority）技法は、パケットジッタをパケット単位で制御する。しかし、各ノードにおいて各パケットの前時間（leading time）を計算することが必要であり、次ノードの伝送のためにヘッダに計算時間を表示する。
【０００６】
図１は、従来のジッタＥＤＤ技法を説明するための模式図であって、接続ｊにおける隣接する２つのノードｉ及びノードｉ+1を通じてセルｋの進行過程が示されている。ここで、ノード番号ｉ、接続番号ｊ及びセル番号ｋは、各々正の整数である。接続ｊのノードｉにおけるセルｋは適格時刻ＥＴijkが過ぎた後に伝送に適切な状態になり、ノードｉにおけるデッドラインＤＬijkより以前にサービスされなければならない。デッドラインＤＬijkは適格時刻ＥＴijkと遅延限界ｄijとの和であり、接続ｊのノードｉに対する遅延限界ｄijはコールの設定段階において予め定められる。
【０００７】
スケジューラにおける予め定められた割当方式によって、セルｋがノードｉからノードｉ+1にデッドラインＤＬijkの以前にサービス時刻ＳＴijkにて実際サービスされる時、セルｋに先行時間（pre-ahead）ＰＡijkが書込まれる。上記先行時間ＰＡijkはノードｉにおけるセルｋのデッドラインＤＬijkとサービス時刻ＳＴijkとの間の時間間隔を考慮して計算される。ノードｉからノードｉ+1までの仮想チャンネルまたは仮想経路を経る伝播遅延τiの後、セルｋはノードｉ+1における到着時刻ＡＴi+1、jkに到着し、その後、セルｋは保持時間ＨＴi+1、jkの間ノードｉ+1のジッタ制御部に一時的に格納される。ノードｉ+1における保持時間ＨＴi+1、jkはノードｉにおける先行時間ＰＡijkと同一である。セルｋがノードｉ+1における伝送に対して適格になる適格時刻ＥＴi+1、jkは、ノードｉ+1における到着時刻ＡＴi+1、jkと保持時間ＨＴi+1、jkとの和である。従って、ジッタ制御部は、セルｋがデッドラインＤＬijkより先にノードｉを離れている時間の量だけセルｋを保持することによって、遅延偏差を制御して突発が網の内部で発生することを防ぐ。
【０００８】
一方、ノードｉ+1におけるセルｋは、デッドラインＤＬi+1、jkより先にサービス時刻ＳＴi+1、jkにタイムスタンプ、例えば、先行時間ＰＡi+1、jkに対するスケジューリング情報とともにサービスされる。ここで、デッドラインＤＬi+1、jkは適格時刻ＥＴi+1、jkと遅延限界ｄi+1、jkとの和と同一であり、先行時間ＰＡi+1、jkはノードｉ+1におけるデッドラインＤＬi+1、jkとサービス時刻ＳＴi+1、jkとの間の時間の差と同一である。
【０００９】
言換えれば、ノードｉ+1におけるセルｋの適格時刻ＥＴi+1、jkは
ＥＴi+1、jk＝ＥＴijk＋ｄij＋τi
によって計算される。ここで、ＥＴijkとＥＴi+1、jkは、各々、接続ｊの上位ノードｉ及び下位ノードｉ+1におけるセルｋの適格時刻を表し、ｄijは接続ｊの上位ノードにおける遅延限界であり、τiは上位ノードｉと下位ｉ+1との間の伝播遅延を表す。隣接する２つのノードのうち、上位ノード及び下位ノードは各々ソースノード及び宛先ノードの方を向かっている。下位ノードｉ+1におけるセルｋの適格時刻は、上位ノードｉにおける適格時刻に依存するので、上位ノードｉに対する情報が下位ノードｉ+1に伝達されなければならない。そのような情報は、幾つかのアルゴリズムにおけるセルヘッダーに伝達される。
【００１０】
従って、既存の非作業保存方式のパケットサービスは、遅延ジッタをフレーミング法を用いるか、ジッタ情報をパケットヘッダーを用いて伝達することによって制御するので、現在の形態ではＡＴＭ網に適用するのには適切ではない。フレーミング法の利用は結合問題のため接続の多様な性能要求量を満足させることが不可能で、パケットヘッダーの利用は時間を表示するためヘッダー空間を要求するので、ＡＴＭ網においては適切ではないという不都合がある。
【００１１】
【発明が解決しようとする課題】
従って、本発明の主な目的は、上位ノードから下位ノードへスケジューリング情報を伝達するためのヘッダー空間がなくても、終端間遅延及び遅延ジッタを補償してＡＴＭ網において無混雑（congestion-free）実時間通信サービスでセルをスケジューリングし得るセルスケジューリング装置を提供することにある。
【００１２】
【課題を解決するための手段】
上記の目的を達成するために、本発明によれば、ソースノード及び宛先ノードを有する複数のノードを結んで形成された接続を通じてコールの複数のセルをスケジューリングするセルスケジューリング装置であって、
前記コールに対して、Ｍが正の整数である時、各々が予め定められた時間間隔であるＭ個のタイムスロットからなるフレームの大きさを決定するフレーム大きさ決定手段と、
前記ソースノードの方に位置する上位ノード及び前記宛先ノードの方に位置する下位ノードからなる隣接する各ノード対において、両ノードの間に対する各伝播遅延及び遅延限界を検出する遅延情報検出手段であって、前記伝播遅延はセルの伝播の際、複数のタイムスロットを表し、前記遅延限界はＰが正の整数である時、前記セルが前記上位ノードにおいて伝送に適切な状態になった後から、前記下位ノードにサービスされる前のＰ個のタイムスロットを表す、前記遅延情報検出手段と、
各接続の各ノードごとに１つずつ割当てられ、前記フレーム大きさをリセットするために、伝播遅延及び遅延限界に基づいて接続単位でプリ同期化され、各フレームのタイムスロットをカウンタダウンして、タイムスロット単位にカウント値を生成する複数のフレームカウンタであって、前記上位ノードにおいて前記フレームカウンタによってカウントされた各上位カウント値が、前記下位ノードにおいて前記フレームカウンタによってカウントされた下位カウント値と相関関係にある、前記複数のフレームカウンタと、
前記フレームカウンタのカウント値がフレーム大きさにリセットされる時、フレーム大きさの周期に従ってスイッチング信号を生成するスイッチ制御部と、
前記接続ごとに同期化され、前記フレームカウンタのカウント値及び前記切換え信号に基づいて、セルを調整、スケジューリングする同期化スケジューラとを含むことを特徴とするセルスケジューリング装置が提供される。
【００１３】
【発明の実施の形態】
図２を参照すると、本発明の通信モデルが示されている。ここで、網はリンクの組によって接続されたノードの組からなっている。各々の一方向性のリンクは２つのノードが帯域幅を用いて通信できるようにする。接続ｊにおけるパケットまたはセルｋが複数のノードを通じてソースノードから宛先ノードまで貫通するリンクの組は、パケット経路と呼ばれる。各リンクに対する隣接する２つのノードは、ソースノードの方に位置した上位ノードと宛先ノードの方に位置した下位ノードとして分けられる。図２の例は、２つの接続、即ち、経路P1={AC,CD,DE}に沿った接続j1と、P2={BC,CD,DF}に沿った接続j2とが示されている。リンクCDを用いる接続の組は{J1,J2}である。
【００１４】
本発明によると、実時間サービスに適切な新しいキューイング方式が提供される。これは、保証された情報量及びほぼ一定の終端間遅延を有する無混雑通信を可能にする。本発明のキューイング方式はパーセションプリ同期化（Per-Session Pre−Synchronized；PSPS）フレーミング法を用いる。各接続のフレームは、各ノードにあるフレームカウンタによって接続別に定義され、フレームの境界は接続の設定段階でフレームカウンタのプリ同期化を通じて整列される。このように同期化されたフレームカウンタは、ジッタ情報を伝達するためのヘッダ空間を有しなくても遅延ジッタを効果的に制御することができる。従って、ＰＳＰＳフレーミング法はＡＴＭ網に直接適用され得、時間従属情報、例えば、音声、映像及びＡＴＭ網の回路エミュレーションのような実時間通信信号に対する回答を可能にする。
【００１５】
図３を参照すると、本発明によって、コール接続の設定及びセル伝送を行う装置が示されている。伝送されたＡＴＭセルはヘッダー検出部１１０及びジッタ調節部１４０に供給される。コールの設定段階において、ヘッダー検出部１１０は、ＡＴＭセルの５オクテットヘッダーを検出し、ＡＴＭセルのコール接続が設定されたか否かを判断する。ＡＴＭセルに対するコールが存在しない場合、ヘッダー情報に基づいてコール調節部２１０におけるコール接続を設定するための過程が開始される。ここで、ＡＴＭセルのヘッダー情報は４ビットの一般流れ制御フィールド（generic flow-control field; GFC）、８ビットの仮想経路識別子（virtual path identifier;VPI）、16ビットの仮想チャンネル識別子（virtual channel identifier;VCI）、３ビットのペイロード形態（payload type; PT）、１ビットのセル損失優先順位（call loss priority; CLP）及びヘッダーエラー制御（header error control; HEC）を備える。ＧＦＣは終端間の流れ制御に用いられ、幾つかの他の種類のデータの流れを制御するのに用いられる。ＶＰＩは使用者間または使用者−網の間の仮想経路を表し、ＶＣＩは使用者間または使用者−網の間の仮想チャンネルを表し、ＰＴは情報フィールドの情報形態を表す。コール調節部２１０は、接続によって要求されるサービスの質（QOS: quality of service）を供給するために、どの網資源が必要であるかを決定し、それらの網資源が有用であるかを検査し、その後、それらの資源を保持、管理する。保持を要する資源は、主に各ノードにおけるバッファ容量及び接続経路にある各リンクに対する帯域幅である。ある接続が、要求されたＱＯＳに適切でないと、他の接続が選択され、より低いＱＯＳにて交渉が再開される。例えば、コール調節部２１０は終端間のデッドラインを増やし、ジッタ要求事項を緩和させ、最大トラフィック率または可能なバースト大きさを減少させることができる。選択された接続ｊに対する情報は、カウンタ同期化部２２０及び制御メモリ１３０に供給される。ここで、上記情報にはフレームの大きさＴj、接続ｊの上位ノードｉと下位ノードｉ＋1との間の遅延限界ｄij、及び上位ノードｉと下位ノードｉ＋1との間の伝播遅延τiを備える。Ｔj、ｄij及びτiは各々タイムスロット単位で表現される。
【００１６】
本発明の好適な実施例において、接続ｊのノード全体にある全てのフレームカウンタはカウンタ同期化部２２０において予め同期化される。カウンタ同期化部２２０は、図３に示すカウンタプール１２０にある接続ｊに対応するフレームカウンタを初期化させる。
【００１７】
ＰＳＰＳフレーム方式において、隣接する各ノード対のフレームの境界が整列されるので、上位ノード、即ち、ノードｉのスケジューリング情報を下位ノード、即ちノードｉ＋1に効果的に伝達することができる。整列過程は次のようなコール接続が設定される間に反対方向に進行される可能性がある。宛先ノードのフレームカウンタが活性化された後、宛先ノードのフレームカウンタにて隣接する上位ノードにカウント値が送られる。カウント値を受けるとすぐ、隣接する上位ノードはコール接続に対応するフレームカウンタを、関連する伝播遅延を反映する値に初期化する。隣接する各ノード対に対して上記過程が反復し、ソースノードに到達するまで上位ノードに転移が続けられる。
【００１８】
このような初期化過程が終わると、フレームカウンタはタイムスロットの比率でカウントダウンしてフレームカウンタが「０」になるとすぐ、フレームサイズＴj（Ｔjは正の整数）にリセットされる。一旦、１つの接続におけるフレームカウンタがコールの設定段階にて上述したように同期化されると、各フレームカウンタは接続が存続する限り独立的に動作するようになる。
【００１９】
他の観点からみると、フレームカウンタが各接続の単位で予め同期化されているので、１つのノードから他のノードにスケジューリング情報を伝達せずに各ノードにおけるセルの適格時刻を決定することができる。詳しくは、接続ｊの下位ノードｉ＋1におけるフレームカウンタの到着カウント値ＡＣi+1、jkは、
ＥＴi+1、jk＝ＥＴijk＋ｄij＋τi＝ＡＴi+1、jk＋ＡＣi+1、jk
である。ここで、ＥＴijkは上位ノードｉにおける接続ｊのセルに対する適格時刻、即ち、その時刻以後の上位ノードｉにあるセルｋが下位ノードｉ+1に伝送され得る仮想到着時刻を表し、ｄijは上位ノードｉと下位ノードｉ+1との間における接続ｊの遅延限界であり、τiは上位ノードｉと下位ノードｉ+1との間の伝播遅延であり、ＡＴi+1、jkは接続ｊの下位ノードｉ+1におけるセルｋの実際到着時刻であり、ＡＣi+1、jkは接続ｊの下位ノードｉ+1におけるセルｋの実際到着時刻ＡＴi+1、jkにおいて対応するフレームカウンタを読込んで計算される到着カウント値を表す。
【００２０】
結果的に、接続ｊの下位ノードｉ+1におけるセルｋの適格時刻ＥＴi+1、jkは、接続ｊの下位ノードｉ+1におけるセルｋの実際到着時刻ＡＴi+1、jkとその実際到着時刻ＡＴi+1、jkにおけるフレームカウンタの到着カウント値ＡＣi+1、jkとの和で計算される。これは、セルｋに対する到着カウント値ＡＣi+1、jkが接続ｊの下位ノードｉ+1における適格時刻ＥＴi+1、jkの残余時間（ＲＴ）を表すからである。
【００２１】
接続ｊの各ノードごとに１つのフレームカウンタが割当てられ、接続ｊの全ノードに設置された全フレームカウンタが上述したようにパーセッションプリ同期化過程によって予め同期化される。全フレームカウンタに対する各カウント値は各タイムスロット単位または各サービス時間ごとに１つずつ減少し、全フレームカウンタの各カウント値が「０」になるとすぐ、接続ｊのフレームの大きさＴjにリセットされる。詳しくは、接続ｊのノード全体にある全てのフレームカウンタが隣接する２つのノードの間の伝播遅延を考慮して予め同期化されて、セルが上位ノードｉからカウント値がＮである時に出発する場合、そのセルは伝播遅延に相当する時間の間に伝送された後、下位ノードｉ+1においても同じカウント値Ｎを見るようになる。このような配列は、コールの設定段階において対応する隣接ノードにフレームカウンタに対する情報を伝送して形成され得る。このようにパーセッションプリ同期化されたフレームカウンタは対応する接続が存続する限り同期が保持される。
【００２２】
ノードｉにおけるフレームカウンタのカウント値は２つの意味を有する。即ち、ノードｉにおいてジッタ制御部にある各セルに対する各カウント値は、適格時刻までの残りの残余時間を意味し、適格時刻が過ぎた後予め定められたスケジューリング方式によってセルがサービスされ得る。ノードｉにあるスケジューラにおける各セルに対する各カウント値は、デッドラインまでの残りの他の残余時間を意味して、デッドラインになる以前にセルがサービスされなければならない。例えば、セルが上位ノードにおけるフレームカウンタが「３」である時サービスされる場合、そのセルはデッドライン前の３タイムスロットでサービスされることを意味する。そのセルが下位ノードに到着する時、接続する下位ノードにおけるフレームカウンタのカウント値は「３」になり、それに従ってそのセルはジッタ制御部にて３タイムスロットの間に格納された後、スケジューラに入る。スケジューラの観点からみると、下位ノードにあるセルはまるで上位ノードにおける最大の遅延限界であったようにみなされる。即ち、あるセルが下位ノードにおけるスケジューラに入る時間は、上位ノードにおけるそのセルのサービス時間と関係無しに一定に保たれる。
【００２３】
上述した方式は、セルの適格時刻及びデッドラインを計算する必要がなく、適格時刻及びデッドラインを格納する必要もない。遅延ジッタを調節し、スケジューリング優先順位を決定するために同期化されたフレームカウンタのみを必要とする。同期化されたフレームカウンタは、セルが現タイムスロットに到着するかまたは出発するかには無関係であり、但し、出力リンクにおけるセル伝送の可否のみに基づいて作動される。
【００２４】
同期化されたフレームカウンタは、スケジューリング情報を伝達するための別途のヘッダー空間を要求せずに、効果的に遅延ジッタを調節する重要な役割を果たすので、ＡＴＭ網における実時間サービスを可能にする。
【００２５】
図３を参照して、セル伝送ステップにおいて、ヘッダー検出部１１０におけるＡＴＭセルの５オクテットヘッダーを検出することによって、ＡＴＭセルが複数のコールのうち、何れかの１つのコールに対応することに決定されると、５オクテットヘッダーのＶＰＩ／ＶＣＩに対する情報がカウンタプール１２０に伝達される。図３において、点線で示されているブロック１００は、接続ｊのノードｉにあるセル伝送ブロックを表す。カウンタプール１２０において、ＶＰＩ／ＶＣＩに対する情報に基づいて接続ｊのノードｉにおける対応する同期化されたフレームカウンタが検出され、セルｋに対する到着カウント値ＡＣijkを読込み、到着カウント値ＡＣijkはジッタ調節部１４０に伝送される。セルｋはジッタ調節部１４０に到着カウント値ＡＣijkの間一時的に格納され、伝送に適切な状態になり、その後スケジューリング部１５０に伝送される。
【００２６】
一方、カウンタプール１２０は同期化されたフレームカウンタのカウント値Ｃijk-1をタイムスロット単位でスケジューリング部１５０に供給する。ここで、カウント値Ｃijk-1は接続ｊの上位ノードｉにおける伝送適格である前セルk-1に対するカウント値である。制御メモリ１３０は、フレーム大きさＴjと遅延限界ｄijとの間の差ｂijをスケジューリング部１５０に伝達する。スケジューリング部１５０は本発明によって前セルk-1を出発カウント値ＤＣijk-1とともに下位ノードｉ+1に伝送する。ここで、出発カウント値ＤＣijk-1は、前セルk-1が下位ノードｉ+1にサービスされる時、上位ノードにあるフレームカウンタのカウント値を表す。
【００２７】
図４を参照しながら、遅延限界が接続ｊのフレームの大きさＴjと同一である場合、ＰＳＰＳ技法によってプリ同期化された各フレームカウンタを用いて４つのノードを経てセルの伝送を説明する。各々の白い矢印は対応するノードにおけるセルの実際の到着を表し、各々の黒い矢印は対応するノードから次のノードへのセルの出発を表す。セルｋがノードｉ-1における到着カウント値ＡＣi-1,jk＝2に実際に到着する場合、セルｋはノードｉ-1のジッタ制御部に到着カウント値ＡＣi-1,jk＝2の間一時的に格納され、次のノードｉへの伝送に適切な状態になる。ＰＳＰＳ技法によって下位ノードｉに対する各到着カウント値ＡＣijkは上位ノードｉ-1に対する出発カウント値ＤＣi-1,jkより伝播遅延τi-1だけ遅延されるので、セルｋが出発カウント値ＤＣi-1,jk＝5における上位ノードｉ-1を離れると、そのセルｋがノードｉに到着する時、到着カウント値ＡＣijkは「５」にならなければならない。セルｋがノードｉにおける到着カウント値ＡＣijk＝5だけ格納され伝送に適切な状態になり、その後、出発カウント値ＤＣijk＝7である時、次のノードｉ+1に伝送される。
【００２８】
一方、一般的なフレーム技法において、各ノードにおける遅延限界がそれに対応する接続のフレームの大きさに与えられ、フレームの大きさは対応する接続に割当てられた帯域幅の逆数として決定される。従って、帯域幅の割当は遅延限界と結合され、網資源の非効率的な使用をもたらすようになる。このような非効率性は帯域幅割当から遅延限界割当を分離することによって多少緩和され得る。
【００２９】
図５を参照すると、遅延限界ｄi-1,jがフレーム大きさＴjより小さい場合セルｋの伝送を説明している。これは遅延限界から帯域幅割当を分離させる一実施例である。適格時刻がＥＴijkである時、接続ｊのノードｉにおけるセルｋのデッドラインは、ＥＴijk +ＴjではないＥＴijk +ｄijになる。ここで、ｄijは接続ｊのノードｉにおける遅延限界であり、Ｔjは接続ｊのフレーム大きさである。接続ｊの各ノードにある各フレームカウンタはプリ同期化され、接続ｊの上位ノードｉ-1におけるセルｋの出発カウント値がＤＣi-1,jkであれば、そのセルｋは接続ｊの下位ノードｉに到着して到着カウント値
ＡＣijk＝ＤＣi-1,jk−(Ｔj−ｄi-1,j)
を読込む。
【００３０】
各フレームカウンタがプリ同期化される時、隣接する２つのノードの間に伝播遅延τi-1、接続ｊの各ノードｉ-1における遅延限界ｄi-1,j、及び接続ｊのフレーム大きさＴjが考慮されなければならないので、ＰＳＰＳ技法によって下位ノードｉ-1に対する各到着カウント値ＡＣijkは上位ノードｉ-1に対する対応する出発カウント値ＤＣi-1,jkよりτi-1−(Ｔj−ｄi-1,j)だけ遅延される。
【００３１】
接続ｊのフレームの大きさＴjが「１０」であり、接続ｊのノードｉ-1、ｉ及びｉ+1における遅延限界ｄi-1,j、ｄij及びｄi+1,jは、各々「９」、「５」及び「７」とする。セルｋが出発カウント値ＤＣi-1,jk＝5である時ノードｉ-1を離れる場合、そのセルｋがノードｉに到着する時の到着カウント値ＡＣijkは「４」(=5-(10-9))でなければならない。その後、セルｋが到着カウント値ＡＣijk＝4の間格納され伝送に適切な状態になり、出発カウント値ＤＣijk＝6におけるノードｉ+1に伝送され、ノードｉ+1における到着カウント値ＡＣi+1,jkが「１」(=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のうちに特定の接続に属するセルが仮想チャンネル（VC1〜VC2）のうち対応する１つの仮想チャンネルを経て入力されるようにし、そのセルを対応する適格時刻まで格納し、その後、そのセルをスケジューリング検出部12-1〜12-nのうち対応する１つのスケジューリング検出部及びＭＵＸ２０に送る。ここで、全ての接続1〜nは、上位ノードｉ及びその下位ノードｉ+1を通過し、１つのセルに対する適格時刻はそのセルを有するフレームの終了時刻を表す。各スケジューリング検出部12-1〜12-nは、プリ同期化されたフレームカウンタを調査して、タイムスロット単位で減少するカウント値Ｃijkを読込み、空フラグ（empty flag）ＥＦijkを生成する。ここで、空フラグＥＦijkは、伝送され得るセルが存在するかの可否を表す。対応するスケジューリング検出部12-jから供給されるカウント値Ｃijk及び空フラグＥＦijだけではなく、図３に示されている制御メモリ１３０から供給されるフレームの大きさＴjと遅延限界ｄijとの差Ｂijが、対応する各残余時間（ＲＴ）生成器30-1〜30-nに供給される。ここで、ｊはｎ以下の正の整数である。各ＲＴ生成器30-jは、カウント値Ｃij、空フラグＥＦij及び差Ｂijに基づいて、残余時間ＲＴijkを生成する。ここで、残余時間ＲＴijは適格時刻から計算されたセルの遅延限界の終了時刻を表す。
【００３５】
図７を参照すると、図６に示す各々の実時間接続ｊに対するｊ番目の遅延限界トラフィックキュー及びｊ番目の残余時間（ＲＴ）生成器のブロック図を示されている。遅延限界トラフィックキューは、第１及び第２先入れ先出し（FIFO: first in first out）キュー１１、１２と、第１及び第２空検出部１３、１４と、入力及び出力トグルスイッチ１５、１６と、スイッチ制御部１７と、同期化されたフレームカウンタ１８とを備える。
【００３６】
最初、接続ｊのノードｉに対する同期化されたフレームカウンタ１８が、上述したようにＰＳＰＳ過程による同期信号によってプリ同期化される。ここで、図３に示すカウンタ同期化部２２０から供給された同期化信号は隣接する２つのノード、即ち、ノードｉとノードｉ+1との間の伝播遅延τi、接続ｊの各ノードｉにおける遅延限界ｄij、及び接続ｊのフレーム大きさＴjを考慮し、ノードｉにおけるフレームカウンタ１８の各カウント値は、各タイムスロットまたは各サービス時間に１つずつ減少しつつ、カウント値が「０」になると同時に接続ｊのフレームの大きさＴjにリセットされる。各カウント値が減少するごとに、各カウント値はスイッチ制御部１７及び拡張カウンタ３１に供給される。各カウント値がフレーム大きさＴjにリセットされる時、スイッチ制御部１７はスイッチング信号を生成して、周期がフレーム大きさＴjであるスイッチング信号が入力及び出力スイッチ１５、１６に供給される。
【００３７】
一方、入力スイッチ１５において、接続ｊのノードｉに対する仮想チャンネルＶＣijは、スイッチ制御部１７から供給されたスイッチング信号によって第１及び第２ＦＩＦＯキューに選択的に接続される。また、第１ＦＩＦＯキュー１１の入力がスイッチング信号によって図７において実線の矢印で示すように仮想チャンネルＶＣijに接続されると、出力スイッチ１６において、第２ＦＩＦＯキュー１２の出力がＭＵＸ２０に接続される。反対に、第２ＦＩＦＯキュー１２の入力が、図７において点線の矢印で示すように接続されれば、第１ＦＩＦＯキュー１１の出力がＭＵＸ２０に接続される。言換えれば、第１及び第２ＦＩＦＯキュー１１、１２は、論理的に分離され、一方のＦＩＦＯキューが伝送のためスケジューリングされる準備ができた適格セルを格納する間、他方のＦＩＦＯキューは適切な状態でない、即ち、フレーム時間の端までジッタ調節されなければならないセルを格納する。
【００３８】
また、第１及び第２ＦＩＦＯキュー１１、１２の出力は、各々、第１及び第２空検出部１３、１４に接続される。第１及び第２空検出部１３、１４は、各々第１及び第２ＦＩＦＯキュー１１、１２が空いているか否か、即ち第１及び第２ＦＩＦＯキュー１１、１２に伝送されるセルが存在するか否かを検出する。１つのセルが予めスケジューリング方式によって伝送されていたか、若しくは上位ノードから対応するＦＩＦＯキューにジッタ調節されるためのセルが入力されていない場合、空フラグＥＦij＝「１」が拡張カウンタ３１の前段に供給され、対応するＦＩＦＯキューに伝送するためのセルが存在する場合、空フラグＥＦij＝「０」に供給される。また、出力スイッチ１６において、第１ＦＩＦＯキュー１１がＭＵＸ２０に接続されれば、第１空検出部１３の空フラグＥＦijがスイッチング信号によって拡張カウンタ３１の前段に供給され加えられ、第２ＦＩＦＯキュー１２がＭＵＸ２０に接続されれば、第２空検出部１４の空フラグＥＦijが拡張カウンタ３１の前段に供給され加えられる。
【００３９】
拡張カウンタ３１は空フラグＥＦijとカウント値Ｃijkとを格納する。同期化されたフレームカウンタ１８から供給されたカウント値Ｃijkは、各タイムスロットに１つずつ減少し、「０」になると同時にフレームの大きさＴjにリセットされ、カウント値Ｃijkがフレームの大きさＴjの周期で変化するようになる。１ビット「０」または「１」である空フラグＥＦijkは、拡張カウンタ３１におけるカウント値Ｃijkに加えられて拡張カウント値ＥＣijkを生成することによって、空フラグＥＦijk＝1を有する空キューが適格セルを有する他のキューより低い優先順位を備えるようにするのが望ましい。減算器３２において、拡張カウント値ＥＣijkからフレーム大きさＴjと遅延限界ｄijとの間の差Ｂijが減算され、接続ｊのノードｉにおけるセルｋの残余時間ＲＴijkが生成される。ここで、残余時間ＲＴijkは、キューにおけるデッドラインまでの残りの時間を表す。残余時間ＲＴijkは比較器４０に供給される。
【００４０】
図６を再び参照すると、比較器４０はタイムスロットごとに全ての接続ｊに対する全ての残余時間ＲＴijkを比較し、最小残余時間ＲＴijkを対応する接続ｊとともに選択し、最小残余時間ＲＴijkに対応する仮想チャンネル選択信号ＶＣ_ＳＥＬを生成する。比較器４０は、１つのノードを通過する全ての接続と関連されており、１タイムスロット内に比較機能を行わなければならないので複雑な構造を有しなければならない。比較器４０が２つの入力比較器の多ステップ構造を有するとすれば、接続数Ｍである場合、比較作用は［logＭ］ の複雑さを有する。ここで、［］は、被演算数以上の最小整数を求める演算子である。しかしながら、比較機能は接続の数のみに関連され、全体のセルの個数には無関係であるので、そのように難しい計算は伴わない。例えば、１Ｇbpsリンク帯域幅及び64kbpsの最小接続率を有するＡＴＭ網を考慮してみよう。最悪の場合において最大の接続数Ｍが15,625であるので、１４番の比較作用におけるデッドラインのセルを決定することが可能になる。１タイムスロット、例えば、424ns内に比較作用を行うために、30nsの程度に２つの１５ビットの単語を比較しなければならない。これは現在の技術水準で可能な範囲である。このような例は、比較作用がＰＳＰＳサービス方式の実行において障害にならないことを表す。
【００４１】
図６に示すＶＣ_ＳＥＬ信号は、ＭＵＸ２０に供給される。このＭＵＸ２０に対応するキューに格納されたセルデータに対する接続識別子（CID: connection identifier）を出力することによって、ＶＣ_ＳＥＬ信号に対応するセルｋを次のノードｉ+1に伝送する。実時間接続に対する全てのキューが空いている場合、即ち、全ての空フラグＥＦijが「１」であるので伝送されるセルがないとすれば、実時間連続に対する遅延無関トラフィックキュー１９から遅延無関知セルが選択されＭＵＸ２０に供給される。
【００４２】
図８は、本発明によるＡＴＭ系において、フレームカウンタを用いて生成されたＰＳＰＳフレームに基づいて接続ｊのノードｉにおけるセルｋの動的優先順位キューイング方式に対する流れ図を表す。ステップＳ１０において、ＡＴＭセルが到着すると、ステップＳ１１にてセルのヘッダーが検出され、ステップＳ１２にて、ＡＴＭセルに対するコールが存在するか否かが検出される。ＡＴＭセルに対するコールがない場合、ステップＳ１３にて、複数のノードを貫通するＡＴＭセルに対するコール接続ｊが設定され、ステップＳ１４にて、本発明によるＰＳＰＳ技法を用いて各ノードにある各カウンタが接続単位でプリ同期化される。その後、ステップＳ１８において、セルがスケジューリングされて伝送される。
【００４３】
一方、ＡＴＭセルに対するコールが存在する場合、ステップＳ１５において、セルが遅延無関知トラフィックに該当するか否かが検出される。セルが遅延に無関知である場合、セルはステップＳ１８にて、直接スケジューリングされ伝送される。そうでない場合、接続ｊのノードｉにおけるセルｋに対する到着カウント値ＡＣijkが、ジッタ調節のために同期化されたフレームカウンタから検出され、ステップＳ１７にて、セルｋが到着カウント値ＡＣijkの間にジッタ調節され、その後、ステップＳ１８においてスケジューリングされ伝送される。
【００４４】
図９には、１つのノードにおける全ての接続の全てのセルに対するスケジューリング過程に対する流れ図が示されており、各実時間接続ごとに各同期化されたフレームカウンタが割当てられている。まず、ステップＳ２０において、全ての接続が調査され１つ以上の実時間セルが存在するか否かが判断される。
【００４５】
実時間セル、即ち遅延限界セルがない場合、ステップＳ２６にて遅延無関知セルが存在するか否かが調査される。ここで、遅延無関知セルは、その伝送時間が重要ではないので、いつでも伝送さえされればいい。遅延無関知セルが存在することが調査されると、ステップＳ２７において、遅延無関知セルが次のノードｉ+1に供給される。そうでない場合には、そのタイムスロットにはどんなセルも伝送されない。
【００４６】
ステップＳ２０において１つ以上の実時間セルが検出される場合、ノードｉにおける各実時間接続ごとに接続単位別に同期化されたフレームカウンタを有するので、ステップＳ２１にて１つ以上の伝送のための実時間セルに有する全ての接続ｊに対するカウント値Ｃijkが検出される。ステップＳ２２において、全ての接続ｊに対する残余時間ＲＴijkが、カウント値Ｃijk、フレーム大きさＴj及び遅延限界ｄijに基づいて計算され、ステップＳ２３において最小残余時間ＲＴijkが選択され、ステップＳ２４において最小残余時間ＲＴijkに該当するセルが次のノードｉ+1にサービスされる。
【００４７】
図１０には、１つのノードｉにおける２つの遅延限界接続と１つの遅延無関知接続に対する例示的なスケジューリング表が示されている。ここで、第１及び第２接続ｊ=1及びｊ=2に対する遅延限界は、各々ｄi1=4及びｄi2=3であり、第３接続ｊ=3は遅延に無関係である。時間はタイムスロット単位に変化すると仮定する。接続１のセルｋ1がタイムスロット「０」に到着カウント値ＡＣijk =1である時到着すれば、そのセルｋ1は１タイムスロットの間にジッタ調節され、タイムスロット「１」である時が伝送に適切な状態になり、タイムスロット「０」である時到着カウント値ＡＣi2k =1の状態に到着する接続２のセルｋ2も１タイムスロットの間にジッタが調節され伝送に適切な状態になる。
【００４８】
タイムスロット「１」である時、接続１のカウント値Ｃi1k =4と接続２のカウント値Ｃi2k =3とが互いに比較された後、最小カウント値「３」が選択され接続２のセルｋ2が出発カウント値ＤＣi2k =3とともに次のノードｉ+1にサービスされる。また、接続３のセルｋ3もタイムスロット「１」である時到着する。タイムスロット「２」である時、接続２には伝送されるべきセルが存在しないので、空フラグＥＦi2k=「１」が生成される反面、接続１のセルｋ1はスケジューリングされ出発カウント値ＤＣi1k =3である時ノードｉ+1にサービスされる。到着カウント値ＡＣi2k+1 =2である時到着された接続２の他のセル(ｋ+1)2は２タイムスロットの間に調節されタイムスロット「４」である時が伝送に適切な状態になる。タイムスロット「３」において、接続１及び接続２には伝送されるセルが存在しない。これは接続１にあるセルｋ1は予め伝送される反面、接続２にあるセル(ｋ+1)2はジッタ調節中にあるからである。従って、遅延無関知トラフィックにあるセルｋ3がタイムスロット「３」である時スケジューリングされ伝送される。タイムスロット「４」において、接続２にあるセル(ｋ+1)2がスケジューリングされ出発カウント値ＤＣi2k+1 =3である時次のノードｉ+1に伝送される。
【００４９】
上記において、本発明の好適な実施の形態について説明したが、本発明の請求範囲を逸脱することなく、当業者は種々の改変をなし得るであろう。
【００５０】
【発明の効果】
従って、本発明によれば、上位ノードから下位ノードへスケジューリング情報を伝達するためのヘッダー空間がなくても、終端間遅延及び遅延ジッタを補償してＡＴＭ網において無混雑実時間通信サービスでセルをスケジューリングすることができる。
【図面の簡単な説明】
【図１】通常のジッタＥＤＤ（jitter earliest-due-date）規則を説明するための模式図。
【図２】複数のノードから構成される網に対する１つの例示図。
【図３】本発明によるコール設定及びセル伝送を行う装置に対するブロック図。
【図４】本発明による遅延限界がフレーム大きさと同一である場合、コールの設定段階においてカウンタの間にパーセッションプリ同期化（per-session pre-synchronization）の第１実施例を示す図面。
【図５】本発明によって、遅延限界がフレーム大きさより小さい場合、コールの設定段階においてカウンタの間にパーセッションプリ同期化の第２実施例を示す模式図。
【図６】本発明によって、ノードｉにおけるn+1個の接続に対するＰＳＰＳ動的優先順位のキューイング方式を用いてセル調節及びスケジューリング装置に対するブロック図。
【図７】図６において接続ｊに対するｊ番目の遅延境界及びｊ番目の残余時間（ＲＴ）生成器に対するブロック図。
【図８】本発明によるＡＴＭ系において、フレームカウンタを用いて形成されたパーセッションプリ同期化（ＰＳＰＳ）フレーム法に基づいて動的優先順位キューイング方式に対する流れ図。
【図９】全ての実時間接続の同期化されたフレームカウンタを用いる図８のスケジューリングステップに対する流れ図。
【図１０】ノードｉにおいて、２つの遅延限界接続及び１つの遅延無関接続に対するスケジューリング表の一実施例を示す模式図。
【符号の説明】
１０−１〜１０−ｎ  遅延限界トラフィックキュー
１１  第１先入れ先出し（ＦＩＦＯ）キュー
１１−１〜１１−ｎ  ジッタ制御部
１２  第２先入れ先出し（ＦＩＦＯ）キュー
１２−１〜１２−ｎ  スケジューリング検出部
１３  第１空検出部
１４  第２空検出部
１５  入力トグルスイッチ
１６  出力トグルスイッチ
１７  スイッチ制御部
１８  フレームカウンタ
１９  遅延無関トラフィックキュー
２０  マルチプレクサ（ＭＵＸ）
３０−１〜３０−ｎ  残余時間発生部
３１  拡張カウンタ
３２  減算器
４０  比較器
１００  セル伝送ブロック
１１０  ヘッダー検出部
１２０  カウンタプール
１３０  制御メモリ
１４０  ジッタ調節部
１５０  スケジューリング部
２１０  コール調節部
２２０  カウンタ同期化部
【図１】
0003810907.tif 000002
【図２】
0003810907.tif 000003
【図３】
0003810907.tif 000004
【図４】
0003810907.tif 000005
【図５】
0003810907.tif 000006
【図６】
0003810907.tif 000007
【図７】
0003810907.tif 000008
【図８】
0003810907.tif 000009
【図９】
0003810907.tif 000010
【図１０】
0003810907.tif 000011