(57)【要約】本発明は、所定数（Ｋ）の配分時間を有するタイムプランナ（９）での配分時間（ＮＳ）の検出方法に関する。ここでは割当てるべき時間に対してハッシュ関数を使用して配分時間の数の所定の配分時間が検出され、ハッシュ関数を使用して実際に進行する時間がこの所定数の配分時間にマッピングされる。とりわけＡＴＭ規格によるパケット指向の伝送システムの出力線路（３）を介したデータセル（１３）に対して送信時間を検出するための方法は、所定の送信時間（ＴＳＴ）のレジストが、データセル（１３）に対して配分すべき時間としてタイムプランナ（９）で行われると有利である。有林にはこのことは、前に述べた方法を使用して行われる。別の使用領域は、機械装置、交換装置、とりわけパケット指向の通信装置またはデータをマルチプレクスするマルチプレクサでの使用である。
2004512738.tif 000002
【特許請求の範囲】
【請求項１】
設定された数（Ｋ）の割当て時間を有するタイムプランナ（９）にて割当て時間（ＮＳ）を検出するための方法であって、
割当てるべき時間に対して関数を使用して配分時間の数の所定の配分時間を検出し、
関数によって実際に連続する時間を前記配分時間の設定された数（Ｋ）にマッピングする、
ことを特徴とする方法。
【請求項２】
関数としてハッシュ関数、とりわけモジュロ関数を使用する、請求項１記載の方法。
【請求項３】
割当てるべき時間を目下の割当て可能な時間の外に、またはこれと結び付いたイベントを無視して、および／または一時的に別個のマッピング領域にレジストする、請求項１または２記載の方法。
【請求項４】
配分時間の数（Ｋ）にレジスト領域（１０，１７）を記憶空間で割当て、
レジスト領域（１０，１７）へ直接、データおよび／または指示情報をデータ、プログラムまたはイベントにレジストする、請求項１から３までのいずれか１項記載の方法。
【請求項５】
レジスト領域では、それぞれデータまたは指示情報が１つまたは複数の割当てるべき時間またはイベントにレジストされる、請求項４記載の方法。
【請求項６】
複数のイベントについてのデータまたは指示情報を１つの同じレジスト領域（１０，１７）でそれぞれ量、とりわけリスト（１５）としてファイルする、請求項４または５記載の方法。
【請求項７】
前記量は二重に連鎖した指示情報（１６）のシーケンスから形成される、請求項６記載の方法。
【請求項８】
レジスト領域（１０，１７）の１つにレジストされたデータおよび／または指示方法は再び取り出し可能であり、および／または他の配分時間に相応するレジスト領域（１０，１７）の１つに再配列可能である、請求項４から７までのいずれか１項記載の方法。
【請求項９】
とりわけＡＴＭ規格によるパケット指向の伝送システムの出力線路（３）を介したデータセルに対する送信時間（ＴＳＴ）を検出する方法において、
少なくとも１つの所定の送信時間（ＴＳＴ）の登録を、タイムプランナ（９）へのデータセル（１３）に対して割当てるべき時間として行い、とりわけ請求項１から８までのいずれか１項記載の方法を使用して行う方法。
【請求項１０】
指示情報（１６）の１つによりそれぞれデータセル（１３）および／またはそのメモリスペースを指示する、請求項４から８までのいずれか１項および請求項９記載の方法。
【請求項１１】
送信時間（ＴＳＴ）を検出する際に、出力線路（３）に送信すべきデータの十分な間隔を維持し、とりわけこれにより所定のトラフィックコントラクトを出力線路（３）上で形成する、請求項９または１０記載の方法。
【請求項１２】
別個のアルゴリズムを、最後の送信時間の検出のためと次に可能な送信時間の検出のために使用する、請求項９から１１までのいずれか１項記載の方法。
【請求項１３】
送信時間の検出の際に、データのさらなる処理、とりわけデータをデータセル（１３）に対してマルチプレキシングするための十分な時間を準備する、請求項９から１２までのいずれか１項記載の方法。
【請求項１４】
請求項１から１３までのいずれか１項記載の方法を実施するためのタイムプランナ。
【請求項１５】
所定数の記憶領域と、指示装置とを有し、
前記記憶領域は配分時間の所定の最大数に割当てられており、
前記指示装置は、割当てるべき時間またはそれに所属するデータへの指示を配分時間に指示する、請求項１４記載のタイムプランナ。
【請求項１６】
請求項１４または１５記載のタイムプランナを有する、通信システム、とりわけパケット指向の遠隔通信システムまたはデータネットワークにおける交換装置。
【請求項１７】
請求項１４または１５記載のタイムプランナおよび／または請求項１６記載の交換装置におけるデータをマルチプレキシングするためのマルチプレクサ。
【発明の詳細な説明】
【０００１】
本発明は、請求項１の上位概念の構成を備えるＡＴＭセルを送信するための時間配分方法、並びにそのための時間配分装置に関する。
【０００２】
有線接続された通信システムまたは無線通信システム、例えば第２世代ＧＳＭ（Ｇｌｏｂａｌ Ｓｙｓｔｅｍ ｆｏｒ Ｍｏｂｉｌｅ ｃｏｍｍｕｎｉｃａｔｉｏｎ）の欧州移動無線システム、または将来の無線通信システムＵＭＴＳ（Ｕｎｉｖｅｒｓａｌ Ｍｏｂｉｌｅ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎ Ｓｙｓｔｅｍ）では、データの伝送がパケット化して行われ、このときデータは現在のところＡＴＭ線路を介して伝送される（ＡＴＭ：非同期伝送モード）。このようなＡＴＭ線路の使用および維持にはコストがかかるから、プロバイダはＡＴＭ線路の使用可能な帯域幅を可能な限り有効に使用しようと努める。この目的のために、いわゆるＡＴＭアダプション層タイプ２（ＡＡＬ２）プロトコルがマルチプレキシングプロトコルとして標準化され、例えば音声接続の場合に対して、４８バイトの固定のＡＴＭペイロードが、短い加入者パケットの使用時に使用される。
現在通常の音声パケットの平均的サイズが約２０バイトであるから、ＡＴＭセル（４８バイト）のペイロードキャパシティは約４０％しか負荷されない。この問題または類似の問題を解決するために、複数の音声パケットを１つのＡＴＭセルにマルチプレキシングすることが公知である。
このために必要な接続装置の現在の実現例が図１に示されている。ここでは第１の物理的入力線路１が接続装置２に接続される。入力線路１を介して接続装置２に供給されるデータは、この接続装置でとりわけ仮想的に再配分されるか、または新たに配分され、物理的出力線路３を介して出力される。入力線路１と出力線路３は現在のところ、通常は１５５Ｍｂｐｓの線路として構成されている。接続装置１内では到来したＡＴＭセルがＡＴＭデマルチプレクサ４によりデマルチプレクスされ、ＡＡＬ２デマルチプレクサ５にさらに導通される。ここでこれらのデータは多数の仮想接続に配分され、続いてＡＡＬ２スイッチング装置６で新たに配列される。スイッチング装置６から新たに配列されたデータがＡＡＬ２マルチプレクサ７とさらにＡＴＭマルチプレクサ８に供給される。これらのマルチプレクサはセルを物理的出力線路３を介してさらに伝送するために統合し、出力する。
従ってスイッチング装置６には多数の仮想接続が到来し、それらのデータを相応に適切な仮想出力線路に配分しなければならない。通常はバッファが設けられており、これにより同時に到来し、処理すべき所定の量のデータをバッファ装置に中間記憶することができる。スイッチング装置６の機能のために、すなわち相応に多数の仮想接続を介して到来したデータを相応に多数の出力仮想接続（これらはただ１つの出力物理的接続にマルチプレクスしなければならない）に相応に割り当てるために、仮想接続の管理ではいわゆるトラフィックコントラクトが考慮される。このシステム固有のトラフィックコントラクトは、仮想接続に対して所要のサービス品質（ＱｏＳ：Ｑｕａｌｉｔｙ ｏｆ Ｓｅｒｖｉｃｅ）を保証する。とりわけこのコントラクトは、スイッチング装置６およびとりわけ物理的出力線路３により管理できるだけの量のデータトラフィックがスイッチング装置６に入力されるようにする。現在の実現例では個々の接続について前もって、どれだけのデータが後から最大で到来することができるかという情報が入力されなければならない。例えばサービスカテゴリー「固定ビット速度（ＣＢＲ：Ｃｏｎｓｔａｎｔ Ｂｉｔ Ｒａｔｅ）」では、１接続当たりの最大データ速度（ＰＣＲ：Ｐｅａｋ Ｃｅｌｌ Ｒａｔｅ）と、セル遅延変動トレランス（ＣＤＶＴ：Ｃｅｌｌ Ｄｅｌａｙ Ｖａｒｉａｔｉｏｎ Ｔｏｌｅｒａｎｃｅ）が指示される。接続装置２に存在するトラフィックコントラクトを監視するための部門（Ｐｏｌｉｃｅｒ）は、セルが包括的セル速度アルゴリズムＧＣＲＡ（１／ＰＣＲ、ＣＤＶＴ）（ＧＣＲＡ：Ｇｅｎｅｒｉｃ Ｃｅｌｌ Ｒａｔｅ Ａｌｇｏｒｉｔｈｍ）に相応しない場合、このセルをマークするか、または消去する。マークされたセルは別の接続装置により、比較的に後の時点で必要な場合には消去される。
この状況を回避するために、セルは遅延され、時間的間隔をおいて処理される。この処理はとりわけ、バッファないし待ち行列にあるセルをさらなる処理のために選択するアルゴリズムを使用して行われる。固定送信時点を時間的にプラニングするためのアルゴリズムは、処理手段および選択手段の点で非常に固定的で高い計算コストと結び付いている。しかしセルを概観できる時間内で、とりわけ数セルサイクルないし数システムクロック内で処理することはこのアルゴリズムによっては不可能である。
本発明の課題は、ＡＴＭセルを送信するための時間配分方法、並びにそのための適切な時間配分装置を提供することである。
この課題は、請求項１の構成を有する、タイムプランナでの割当て時間を検出する方法、ないしは請求項１５による相応の方法を実施するためのタイムプランナによって解決される。
本発明の解決手段は、請求項９によるパケット指向の伝送システムでのデータセルに対する送信時間の検出方法、およびタイムプランナ、交換装置、並びに通信システムでのマルチプレクサに使用される。
有利な構成は従属請求項に記載されている。
有利には、所定数の割当て時間を有するタイムプランナでの割当て時間の検出方法は、割当てるべき時間を関数を用いて、複数の割当て時間のそれぞれ１つの所定の割当て時間にマッピングする。このとき割当て時間の数は、次のようにして最大数に制限される。すなわちこの関数が実際に進行する時間を、この設定された割当て時間の最大数にマッピングすることにより制限される。イベントの記録、または割当て時間に相応するタイムプランナの記憶領域への指示の記録のために、タイムプランナの記憶空間をこの個所まですべて検索する必要はない。
とりわけこの検索はイベントの記録後は簡単になる。なぜなら、検索すべき時点を直接的に簡単な関数によって、とりわけ例えばハッシュ関数やモジュロ関数によって計算することができるからである。この計算結果は直接的に、この時間に割当てられた記憶空間を指示する。言い替えると、時間のかかる長い検索過程の代わりに、非常に短い、明確に定義された時間コストによって、データと所定の時点との割当てないし再発見を行うことができる。複数の記録が１つの記憶空間にある場合だけ、これを記録に関して検索すればよい。
目下の割当て可能な時間の外にある割当てるべき時間、またはこれと結び付いたイベントは、モジュロ関数を使用する場合、「間違った」割当て時間に割当てられることとなる。このことをシステムに起因して、または十分な数の割当て時間に基づいて排除すべきでない場合、このような時間ないしこれに所属するデータは無視されるか、および／または一時的に別個のマッピング領域に記録される。
割当て時間の数にそれぞれ記録領域を記憶空間で割当てることにより、記録領域には直接的に、データおよび／またはデータへの指示情報、プログラムまたはイベントを記録することができる。特に有利にはデータ記憶空間へのポインタを記録する。これによりタイムプランナの記憶空間およびデータに対する記憶空間はシステマティックにおよび／または構造的に別個に管理することができる。
登録領域にはとりわけそれぞれのデータ、または複数の割当てるべき時間またはイベントについての指示情報（１６）を登録することができる。これにより１つの割当て時間当たりで複数のイベントを簡単に管理することができる。データまたは複数のイベントについての指示情報は同じ登録領域に、とりわけ簡単にはそれぞれ量として、とりわけリストとしてファイルすることができる。とりわけポインタを２重に連鎖したエレメントとして使用することにより、簡単な再組み込みまたは取り出し、ないし個々の登録のこのようなリストでの再配列が可能である。
ＡＴＭ規格によるパケット指向の伝送システムの出力線路を介した、データセルに対する送信時間を検出する方法は、所定の送信時間をデータセルに対して割当てるべき時間としてタイムプランナに登録することにより、簡単かつ高速に実行することができる。
指示情報の１つ、とりわけポインタによりそれぞれのデータセルおよび／またはそれらのメモリスペースを指示することによって、イベントをタイムプランナに高速に登録することができる。なぜなら管理すべき指示情報を大きなコストなしで取り扱うことができるからである。
送信時間の検出の際に、出力線路上で送信すべきデータの十分な間隔が維持されるならば、所定のトラフィックパターンを出力線路上で形成することができる。これにより通信システムに監視装置が備えられる。この監視装置は、到来するデータおよび処理すべきデータの量を監視し、過度に多量のデータが到来する場合には、データの選別を阻止することができる。特に有利には、監視装置は到来するデータの出生について注目し、データ密度が過度に高くなった場合には、同じ起源の所定のデータ量だけを許容する。なぜなら本発明の方法では、種々のデータ源のデータを例えばマルチプレクサと関連して混合し、相応に相互にスペーシングし、ないしは時間的に配分することができるからである。
最後の送信時間を設定するためのアルゴリズムと、次に可能な送信時間を検出するためのアルゴリズムとを別個にすることによって、とりわけこのようなスペーシングメカニズムを種々の要求に、例えば通信システムでのトラフィックコントラクトの観点からフレキシブルに適合することができる。
送信時間を検出する際に、データをデータセルに対してマルチプレクスするという、データをさらに処理するための十分な時間を準備することは、前記の方法ステップによって簡単に置換することができる。
この方法により有利には、時間配分機能を有するスケーラブルなタイムプランナが、複数のＡＴＭ接続のマルチプレキシングと関連し、時間的な周辺条件を考慮して得られる。有利にはこのようなアルゴリズムは少数のハードウエアクロックで実現可能である。とりわけこのようなアルゴリズムないしはこのような装置を用いて、所定の所望の時点に対するセルを送信時点として記録することができる。相応に間隔をおくことによって、所望のトラフィックパターンがいずれの出力線路でも形成される。このことは有利である。なぜならそうでないと、後続の監視装置によるデータのポリシング（Ｐｌｏｃｉｎｇ）により（これはトラフィックコントラクトに対して不利である）、スクリーニングされることがあるからである。さらにこれにより該当する接続に対して最適化された公正さがリソース配分の際に保証される。このメカニズムはスケーラブルであり、数セルサイクルで実現可能であり、ダイナミックなメモリ割り当てを必要としない。とりわけ新たな時間配分（リタイミング）の手段も得られる。これによりセルを後から、別の送信時点に移すことができる。
有利には接続個別のフォームないし整形が複数の接続のＡＴＭマルチプレクサと組み合わされる。このことはスペーシング（スペーシング）を時間配分（スケジューリング）の前に実行することにより行われる。スペーシングは次のようにして可能となる。すなわち１接続当たりで１つの登録だけをタイムプランナで実行するのである。新たな時間配分を可能にするため有利には、二重の連鎖リストがアクセスアドレスにより管理される。択一的にメモリ空間占有をシミュレートするための他の量表示も可能である。この量表示では、個々のエレメントないし指示（ポインタ）を取り出すことができる。
タイムプランナのコアをカレンダー状のテーブルが形成する。このテーブルはＡＴＭセルに対するデータ構造体として用いられ、このＡＴＭセルに対しては、将来的に存在する所定の送信希望が登録される。作成されたタイムプランは最終的に送信待ち行列に存在する。連鎖されたリスト構造により、セルに対する新たな時間配分が可能である。個々の仮想接続または仮想接続からの一群の仮想経路に対するスペーシング変数を共にガイドすることにより、送信希望を相応のトラフィックコントラクトに従って許容される時点にずらすことができる。
ＡＡＬ２／ＡＴＭをサポートする、相応に構成されたスイッチング装置は以下のタスクを実行することができる。ＡＴＭ線路のデータは個々の仮想ＡＴＭチャネル接続（ＶＣＣ）にデマルチプレクスされ、さらに個々の仮想ＡＡＬ２接続にデマルチプレクスされる。リアルタイムデータないしデータパケットを新たに配列した後、ＡＡＬ２マルチプレキシングが実行される。このとき所定の最大持続時間（ＴＣＵ）のためのデータ、またはＡＴＭセル完全性に至るデータが遅延される。ＡＴＭ下でのリアルタイムサービスに対して、現在のトラフィックコントラクト要求を満たすために送信装置を設けることができる。この送信装置は、セル流ないしそのデータを仮想ＡＴＭチャネル接続からスペーシングすることができ、これにより後続の接続装置等の監視装置（ポリサー：Ｐｏｌｉｃｅｒ）による選別によってセル損失が生じるのを回避する。最終的にはＡＴＭマルチプレキシングによってＡＴＭ出力が満たされる。
とりわけ回路ノード等にあるリアルタイムデータはＡＡＬ２マルチプレキシングのために待ち行列に置くことができる。有利にはこのようなＡＡＬ２マルチプレキシングの際に、セルスペーシングの時間およびＡＴＭマルチプレキシング遅延の時間を、ＡＡＬ２マルチプレキシングのための単純な時間発生インターバルＴＣＵに加えてただ１つの制御装置で使用することができる。
有利にはこのようにしてモジュール型のタイムプランアルゴリズムも可能となる。スケーラブルな時間配分システムおよび別個のスペーシングアルゴリズムによって次のようなタイムプランナが得られる。すなわち、多数の仮想チャネル接続に関してもスケーラブルであり、データセルに対しては固有の送信時間の複雑でない割当てないし再割り当てを可能にし、確実なデータ伝送のためのセルスペーシングを保証するタイムプランナが得られる。
いくつかの特別な利点が得られる：ただ１つのデータ装置、とりわけデータ端末点で、ハードウエア実現については僅かなコストによりＡＴＭとＡＡＬ２が共働することが可能である。３つの必要な機能、すなわちＡＡＬ２マルチプレキシング、ＡＡＬ２経路（パス）に対するＡＴＭトラフィックコントラクトによる整形ないしスペーシング、および多数のＡＡＬ２経路のＡＴＭマルチプレキシングが１つの共通のハードウエア装置でスケーラブルな形態で実現される。このことにより、セルスペーシングおよびＡＴＭマルチプレキシングによる遅延をＡＡＬ２マルチプレキシングに対して使用できるようになる。
アルゴリズムをモジュール状に構成することによって、ＣＢＲ特性を有するＡＡＬ２経路に対するスペーシング機能を、別の例えばトレラントな経路特性に置換することが簡単になる。タイムプランナのアーキテクチャはとりわけ別のＡＴＭ適用に対する基礎を形成する。拡張は例えば優先計画の方向でまたはスペーシングの方向で、仮想ＡＴＭ経路接続に基づき行われる。このときアルゴリズムの最も有利な伝搬時間特性が維持される。
スケーラブルなタイムプラン機構を他の例えばインターネットプロトコルＩＰの領域に移し替えることが可能であり、これによりそこでのＲＴＰ／ＵＤＰ／ＩＰマルチプレキシングがサポートされる。
時間的周辺条件を備えるマルチプレキシング方法は、リアルタイムデータに対するＡＡＬ２／ＡＴＭ伝送技術の成立時に初めて意味を持つ。従ってそれ以前に問題意識はなかった。
実施例を以下、図面に基づき説明する。
図１は、データパケットないしデータセルをスイッチングするための基礎となる装置を備える物理的線路でのスイッチング装置を示す。
図２は、仮想接続に対する多数の待ち行列、送信待ち行列およびカレンダー状のテーブルを備えるタイムプランナを示す。
図３は、二重に連鎖されたＶＣＣリストを示す。
図４は、セル流を監視するための包括的セル速度アルゴリズムのフローチャートである。
図５は、理論的送信時間を設定するためのアルゴリズムのフローチャートである。
図６は、理論的送信時間を更新するためのアルゴリズムのフローチャートである。
図７は、ＡＡＬ２規格に対して拡張されたタイムプランナの一部を示す図である。
図８は、データパケットをタイムプランナのマルチプレクサに入力するためのアルゴリズムのフローチャートである。
図９は、データパケットをこのタイムプランナから出力するためのアルゴリズムのフローチャートである。
パケット指向の通信システムまたはＡＴＭによるデータ網では、ステーションからデータが別のステーションへ伝送される。送信ステーションのデータは個々のデータパケットないしデータセルに分解され、送信され、受信ステーションで再び統合される。ここでデータは、他の接続のデータと共に共通の伝送媒体、とりわけ有線線路である物理的接続に分配される。種々異なる接続のこれらデータは伝送経路上でそれらの元のセルから取り出し、他の接続のデータと共に新たなセルにまとめることができる。これは物理的伝送経路の負荷を最適化するためである。相応にしてこれらのデータは、このセルから他の場所で再び取り出し、最終的に受信ステーションに伝送されるセルないしはデータパケットにはめ込まれる。
図１では、この目的のために接続装置２がデータ網にある公知のスイッチング装置（スイッチ）に設けられている。ここでは少なくとも１つの物理的第１入力線路１が接続装置２に接続している。入力線路１を介して接続装置２に供給されるデータは、この接続装置で再配列されるか、または新たに配列され、物理的出力線路３を介して出力される。例えばスイッチまたはハブから複数の線路を導き出すこともできる。入力線路１と出力線路３は現在のところ通常は１５５Ｍｂｐｓの線路として構成されている。接続装置２内では到来したＡＴＭセルがＡＴＭデマルチプレクサ４によりデマルチプレクスされ、ＡＡＬ２デマルチプレクサ５にさらに供給される。ここでデータは多数の仮想接続に配分され、最終的にＡＡＬ２スイッチング装置６で新たに配列される。スイッチング装置６から新たに配列されたデータはＡＡＬ２マルチプレクサ７に供給され、最終的にＡＴＭマルチプレクサ８に供給される。ＡＴＭマルチプレクサは相応のセルを物理的出力線路３を介してさらに伝送するためにまとめる。到来するデータの中間記憶を除外すれば、ここですべてのステップ、例えば制御装置でのデマルチプレキシング／マルチプレキシングは純粋に仮想的に行われる。
次に例としてＡＡＬ２に対して、セルがこのような仮想チャネル接続で、例えば時間配分マルチプレキシング装置（ＴＤＭ：Ｔｉｍｅ Ｄｉｖｉｓｉｏｎ Ｍｕｌｔｉｐｌｅｘｉｎｇ）の場合のように固定的な時点または固定的なタイムスロットに割当てられるのではなく、データを到着順にさらに処理することのできる方法を説明する。有利には仮想的に分割されたデータには必要な場合には固有のヘッダ部分が配属される。このことにより、種々異なる仮想チャネル接続ＶＣＣのセルが、ＡＴＭ出力線路の１つのマルチプレクスされたＡＴＭセル流に貢献することができる。とりわけ同時に１つ以上のＡＴＭセルをＡＴＭ出力のために作成することができ、これらのＡＴＭセルから順次それぞれ１つが出力線路３を介してさらに伝送される。
有利な実施形態では、接続装置２はスケジューラないしタイムプランナ９と接続されているか、またはこれが装備されている。
図２から分かるように、タイムプランナは送信待ち行列１０、カレンダー状に構成されたテーブル（以下、カレンダー１１と称する）、およびＡＴＭセルに対する多数の待ち行列（個々の仮想接続ごとに割当てるためのものであり、以下、ＶＣＣ待ち行列１２と称する）を有する。ＶＣＣ待ち行列１２内には、それぞれＶＣＣ接続ないしＶＣＣ線路１，２，．．．Ｎごとに送信するための個々のセルが示されている。例えばＶＣＣ待ち行列１は３つのセル１３を有し、これらのセルは比較的後の時点で仮想接続１を介してマルチプレクサ７，８の方向に送信される。第２の仮想接続に対するＶＣＣ待ち行列１２は図示の時点では出力すべきデータセルを有していない。セルは最終的にメモリに残るから、有利には論理的マルチプレクサ７，８が取り扱われる。第３の仮想接続に対するＶＣＣ待ち行列１２は再び２つの出力すべきセルを有する。言い替えると、入力線路１を介して接続装置２に到来するデータは多数のＶＣＣ待ち行列１２に分解され、後で再び出力される。ここで到来するデータパケットないしセルは変更されずに直接、ＶＣＣ待ち行列１２の１つに供給され、ないしはこのＶＣＣ待ち行列１２の１つで相応のメモリスペースに中間記憶される。また他方では、接続装置２に到来するデータを元のセルから取り出し、新たに分配することも可能である。この場合、これらのデータは、１つまたは複数のＶＣＣ待ち行列１２の相応のセルに割当てられる。接続装置２にあるＶＣＣ待ち行列１２ないしこれに割当てられたメモリスペースへは、例えばＡＡＬ２の場合のように、前もって統合され、引き渡されたセル全体か、または個々のデータが選択的にはめ込まれる。この場合、個々のデータはＶＣＣ待ち行列１２内でセル１３に統合される。有利には前記装置は論理的装置および／または論理的機能である。
データをＶＣＣ待ち行列１２にはめ込むため、ないしはこのＶＣＣ待ち行列１２からセル１３を取り出し空にするため、送信待ち行列１０とカレンダー１１が使用される。到来するデータに対しては例えばシステムから、将来のどの時点でこのデータを再び送信すべきかが設定される。ここで所定の仮想接続を介してさらに送信すべきデータは共通にセル１３として、ＶＣＣ待ち行列１２の１つで準備される。カレンダー１１では、送信時点が少なくとも間接的に取り出される登録が行われる。
送信待ち行列１０では、どのＶＣＣ待ち行列がセル１３の送信のために次の待ち行列として設けられているかが分かる。このために送信待ち行列１０ではリストが作成され、このリストからどのような順序でＶＣＣ待ち行列１２がそれらのセルを相応する仮想接続ないしマルチプレクサ７，８に出力すべきかが分かる。ＡＴＭでは例えば１つのセル１３が送信サイクルごとに送信される。以下、送信指示を備えるこの種のリストをＶＣＣリスト１５と称する。このようなＶＣＣリスト１５は図３に示されている。
セル１３のＶＣＣ待ち行列１２からの出力はそれぞれセルサイクルで行われる。ここでは１セルサイクルごとにＶＣＣ待ち行列１２の１つがその中に存在する第１のセル１３を出力する。後で説明する方法では、有利には１セルサイクルごとに少数のシステムクロックしか必要としない。図２および図３から分かるように、第１のセルサイクルでは第１のＶＣＣ待ち行列１２の最下層にあるセル１３が出力される。なぜなら送信待ち行列１０の最下層にある、最初に読出すべきＶＣＣリストエレメント１６が値１を含んでいるからである。その後、この値１を有するＶＣＣリストエレメント１６がＶＣＣリスト１５から除去され、その結果、次の読出しセルサイクルでは最下層に続くセル１３が第６のＶＣＣ待ち行列から読出される。なぜならＶＣＣリストエレメント１６の相応する値が今度は「６」だからである。第３のセルサイクルでは、第４のＶＣＣ待ち行列１２にあるセル１３が読出され、第４の仮想接続へさらに伝送される。
このことから分かるように、各ＶＣＣ待ち行列１２には少なくとも１つのＶＣＣリストエレメント１６が割当てられており、ＶＣＣリストエレメント１６の値は相応に割当てられたＶＣＣ待ち行列１２の番号を指示する。言い替えると、各ＶＣＣリストエレメント１６の値は、割当てられたＶＣＣ待ち行列１２ないしはこれに配属された記憶空間中のメモリスペースを指示する。このメモリスペースにはデータないしはセルが中間記憶される。従ってＶＣＣリストエレメント１６はプログラム技術的に見て、メモリスペースないしメモリ領域へのポインタの機能を有する。
図２から分かるように、ＶＣＣリストエレメント１６の取り扱いに対しては３つの手段がある。第１の場合では、第１、第６、ないし第４のＶＣＣ待ち行列１２に割当てられた値１，６および４を有するＶＣＣリストエレメント１６が送信待ち行列１０に配列されている。
第２の場合は、セル１３の存在しない第２のＶＣＣ待ち行列１２の状況である。値２を有する相応のＶＣＣエレメント１６が存在しないか、または少なくとも送信待ち行列１０には配列されていない。なぜなら次の時間では、データが第２のＶＣＣ待ち行列１２から第２の仮想接続を介して出力されないからである。
第３の場合では、ＶＣＣ待ち行列１２に所属するＶＣＣリストエレメント１６が配列されており、このＶＣＣ待ち行列１２には後で送信すべきセル１３が含まれている。しかしこのセルでの所望の送信日付は将来である。この相応するＶＣＣリストエレメント１６はカレンダー１１に相応に配列される。
カレンダー１１は有利な実施形態では、カレンダー待ち行列１７の構成からなり、この実施例では例えばＫ＝４０９６のカレンダー待ち行列がある。
別の実施形態では、このカレンダー待ち行列１７の各々が所望の出力時間ないし所望の出力日付に対するものであり、最初に配列された０番目のカレンダー待ち行列１７が最初に考慮され、第１のカレンダー待ち行列１７は後の時間で処理される。
遅くとも送信待ち行列１０がこの実施形態でＶＣＣリストエレメント１６を含まなくなると、ないしは最後のＶＣＣリストエレメント１６が処理されると、相応のＶＣＣリスト１５が０番目のカレンダー待ち行列１７から送信待ち行列１０へ伝送される。そして空になった０番目のカレンダー待ち行列１７には第１のカレンダー待ち行列１７の相応のＶＣＣリスト１５が伝送される。もちろん択一的に、それぞれＶＣＣリスト１５を含む待ち行列から関連の構成体をすでに作成しても良い。ポインタはこの場合、送信待ち行列１０として取り扱われる待ち行列の１つを指示する。その処理後、ポインタはこの包括的待ち行列構成体にある次の待ち行列にセットされる。その結果、これが送信待ち行列として機能する。しかしこのような場合、後で説明するように、新たに到来するデータないしセルの割当て、または時間的に再配列すべきデータないしセルの割当てを相応に再構築しなければならない。
従ってこの別の実施形態では、まずそれぞれ第１，第６および第４のＶＣＣ待ち行列１２が読出され、これに基づいてＶＣＣリストエレメント１６，この例では値１０を有するリストエレメント１６が送信待ち行列１０に伝送される。これに続いて、第１のセルが第１０のＶＣＣ待ち行列１２から読出される。そしてＶＣＣリスト１５を０番目のカレンダー待ち行列１８から送信待ち行列１０へ再記憶する、またはこれに続いて第１のカレンダー待ち行列１７のＶＣＣリスト１５を０番目のカレンダー待ち行列１７に再記憶する。その結果、値１０を有するＶＣＣリストエレメント１６を送信待ち行列１０から処理した後、０番目のカレンダー待ち行列１７に存在する、値７と３を有するＶＣＣリストエレメント１６が送信待ち行列へ伝送される。相応にして、第１のセルサイクル中の第３の時間では、第１のセルが第７のＶＣＣ待ち行列１２から、そしてこの第３の時間領域の第２のセルサイクルで第３のＶＣＣ待ち行列１２の第１のセルが相応の仮想接続を介して出力される。
ここには示されていないが理論的には、複数のＶＣＣリストエレメント１６をＶＣＣ待ち行列１２ごとに設定することも可能である。例えば第１のＶＣＣ待ち行列１２に存在する３つのセル１３に対して相応に、３つの所望の送信時点を送信待ち行列１０ないしカレンダー１１でマークすることができる。
しかし特に有利な実施形態では、ＶＣＣ待ち行列１２の各々に１つのＶＣＣリストエレメント１６だけが割当てられる。
後に説明する特に有利な実施形態では、時間的方法フロー並びにＶＣＣリスト１５ないしそのＶＣＣリストエレメント１６から送信待ち行列１０およびカレンダー１１，ないしそのカレンダー待ち行列１７へのセットおよび／または再セットが時間変数とモジュロ関数によって行われる。
２つの別個の機能を使用すると有利である。これらの機能を以下、「スペーシング更新」（図６）および「次のスペーシング」（図５）と称する。これらの機能は、最後の送信時間を更新し、またトラフィックコントラクトによるＡＴＭに対して仮想接続チャネルＶＣＣの次の送信時間を計算するために使用される。別々のアルゴリズムに分離することにより、種々異なるシステムまたはシステム条件への適合能力が向上する。
モジュロ関数の使用によって、以下に説明するコンセプトをいわゆるハッシュ関数ないしハッシュテーブルとして置き換えることができる。ここでは到来する多数のセルにそれぞれ１つの所定のメモリスペースがハッシュ関数、ここではモジュロ関数によって割当てられる。このことにより一方ではメモリスペースのダイナミックな占有が行われる。他方では所定のセルを後で見出すためにこのセルの記憶空間全体を検索する必要がなくなる。なぜならセルはハッシュ関数を介して少なくともカレンダー待ち行列に関しては高速に見出すことができるからである。
例としてのＡＴＭシステムでは、時間がセルサイクルで測定され、このセルサイクルは５３バイトのデータ量を有する伝送単位として準備される。１つのセルサイクルはここに示した１５５Ｍｂｐｓの伝送速度の場合、２．７μｓの時間を有する。スタート時間は例えば、オペレーティングシステムがスタートした時間として選択することができる。
以下、絶対的時間値を三角括弧により囲まれたデータ変数〈Ｄａｔｕｍ〉により示す。さらに以下、変数〈Ｔｏｄａｙ〉（今日）を現在のセルサイクルの時点に対する変数として、変数〈Ｔｏｍｏｒｒｏｗ〉＝〈Ｔｏｄａｙ〉＋１（明日）を現在のセルサイクル〈Ｔｏｄａｙ〉に続くセルサイクルに対する変数として用いる。変数〈Ｔｏｄａｙ〉と〈Ｔｏｍｏｒｒｏｗ〉はここでは多種多様な離散的時間単位から発し、「カレンダーインターバル」の持続時間に相応するか、または完全なセルサイクルを意味するが、他の変数は任意の値を取ることができる。ここでは丸めまたは変換を実行することもできる。変数〈ｎｏｗ〉は以下、システムの瞬時時間を表す。
これらの絶対的時間変数はシステムによって自動的に、各セルサイクルの開始時に１だけ増加される。以下、スケーラブルな時間計画メカニズムのために例として、タイムプランナ９はＫの列を有するフィールドにより構成されており、ここでは０からＫ−１が通し番号になっている。タイムプランナでの最も古い日付は〈Ｔｏｍｏｒｒｏｗ〉であり、最も若い日付は〈Ｔｏｄａｙ〉＋Ｋである。
すでに冒頭で述べたように、セルは相応のトラフィックコントラクトに応じなければならない。とりわけ前記のスペーシングが前提とされる。間隔（スペーシング）も監視も仮想チャネル接続（ＶＣＣ：Ｖｉｒｔｕａｌ Ｃｈａｎｎｅｌ Ｃｏｎｎｅｃｔｉｏｎ）に対する回路に基づいて行うことができる。
セル流を監視するために、包括的セル速度アルゴリズムが使用される。これが図４に示されている。このアルゴリズムは、１つのセルが接続装置２に到来するたびに呼び出される。セルの到着時間はここでは常にシステム時間に相応する。すなわち日付変数〈ｎｏｗ〉に相応し、この日付変数は最後のシステムスタートからの時間に対するものである。静的変数〈ＴＡＴ〉は次のセルの理論的到着時間〈ＴＡＴ〉（ＴＡＴ：Ｔｈｅｏｒｅｔｉｃａｌ Ａｒｒｉｖａｌ Ｔｉｍｅ）に対するものである。各仮想的ＡＴＭチャネル接続ＶＣＣにはここでは変数〈ＴＡＴ〉が割当てられている。次のセルが〈ＴＡＴ〉より前に到来しなければ（ここでは所定の公差Ｌ（リミット）が考慮される）、このセルは包括的セル速度アルゴリズムＧＣＲＡ（Ｉ，Ｌ）への一致として取り扱われ、それ以外の場合はそう取り扱われない。この結果に応答するようなシステム設定に依存して、適合しないセルはセル損失優先度（ＣＬＰ：Ｃｅｌｌ Ｌｏｓｔ Ｐｒｉｏｒｉｔｙ）に対するビットによりマークされ、接続装置に転送問題が生じた場合または時間的に後で、ネットワークにおいてこれらのセルはバッファにおかれるか、または完全に消去することができる。サービスカテゴリー「固定ビット速度」（ＣＢＲ：Ｃｏｎｓｔａｎｔ Ｂｉｔ Ｒａｔｅ）では例えば１接続当たりの最大データ速度（ＰＣＲ：Ｐｅａｋ Ｃｅｌｌ Ｒａｔｅ）とセル遅延変動トレランス８ＣＤＶＴ：Ｃｅｌｌ Ｄｅｌａｙ Ｖａｒｉａｔｉｏｎ Ｔｏｌｅｒａｎｃｅ）が設定される。セルがこの包括的セル速度アルゴリズムＧＣＲＡ（１／ＰＣＲ、ＣＤＶＴ）（ＧＣＲＡ：Ｇｅｎｅｒｉｃ Ｃｅｌｌ Ｒａｔｅ Ａｌｇｏｒｉｔｈｍ）に相応しない場合、このセルはマークされる。それ自体公知のサービスカテゴリー「リアルタイム可変ビットレート」（ｒｔ−ＶＢＲ：ｒｅａｌ ｔｉｍｅ Ｖａｒｉａｂｌｅ Ｂｉｔ Ｒａｔｅ）に対しては、達成可能なセル速度（ＳＣＲ：Ｓｕｓｔａｉｎａｂｌｅ Ｂｉｔ Ｒａｔｅ）とバーストトレランス（ＢＴ）を考慮しなければならない。従ってＧＣＲＡ（１／ＳＣＲ、ＣＤＶＴ＋ＢＴ）が設定される。
以下に説明するスペーシングアルゴリズムの目的は、セル流をトラフィックコントラクトに適合することである。
従って次に可能な送信時間〈ＮＳ〉を、セルに対する所望の送信時間〈ＴＴ〉（ＴＴ：Ｔａｒｇｅｔ Ｔｉｍｅ）に依存して計算しなければならない。このために例えば図５に示したアルゴリズム「次のスペーシング」ないし「スペーシングネクスト」が使用される。このセルを送信できるかできないかを見出すために、このアルゴリズムでは変数〈ＴＡＴ〉に類似の理論的送信時間〈ＴＳＴ〉がセル速度アルゴリズムＧＣＲＡで使用される。
目標時間〈ＴＴ〉が、理論的送信時間〈ＴＳＴ〉から交差限界Ｌを減じたものより小さい場合、すなわちセルをより早期に送信したい場合、次の送信時間〈ＮＳ〉が、次の理論的送信時間〈ＴＳＴ〉から交差限界Ｌを減じたものにセットされる。それ以外の場合、セルを十分に後で送信したい場合には、次の送信時間〈ＮＳ〉が目標時間〈ＴＴ〉に設定される。最後に次の送信時間〈ＮＳ〉が出力される。
ここで必要な理論的送信時間〈ＴＳＴ〉を更新するためのアルゴリズムが図６に示されており、以下「スペーシング更新」ないし「スペーシングアップデート」と称する。１つのセルが理論的送信時間〈ＴＳＴ〉の前で送信されるたびに、理論的送信時間〈ＴＳＴ〉は値「Ｉ」だけ増分される。トラフィックコントラクトがサービス「固定ビット速度」ＣＢＲのためのものである場合、限界値はセル遅延変動トレランスＣＤＶＴおよび１接続当たりの最大データ速度の逆数（１／ＰＣＲ）に相応する。ここでＩ＝１／ＰＣＲである。セルが理論的送信時間〈ＴＳＴ〉で、またはこれより後で送信される場合、理論的送信時間は最後のセルの送信時点〈ｎｏｗ〉にインクリメントを加算したものから検出される。すなわち
〈ＴＳＴ〉＝〈ｎｏｗ〉＋Ｉ
である。
図５に示されたアルゴリズム「次のスペーシング」は、いつセルを送信できるか、すなわちこのセルに対する時間計画の前で送信できるかを見出すために呼び出される。アルゴリズムスペーシング更新は、セルが送信されるたびに呼び出される。すなわち計画結果が満たされるたびに呼び出される。
アルゴリズムが正しく動作することを保証するために、有利には常に、１つの仮想接続回路ＶＣＣ当たり１つのセルだけが許容され、次の送信時間〈ＮＳ〉を検出するためのアルゴリズムが呼び出される。なぜならアルゴリズム「次のスペーシング」は最後の理論的送信時間〈ＴＳＴ〉の値に基づくからであり、この時間は先行のセルが送信された場合だけ計算することができる。
２つのアルゴリズム「次のスペーシング」と「スペーシング更新」はスペーシングメカニズムを完全に実施することができるから、これらのアルゴリズムを適合して、別の機能を実施させることも容易である。とりわけこれらを他のトラフィックコントラクトの観点で適合することも容易である。
次に例として説明するタイムプランナ９での経過に対してはさらに、仮想接続回路に対して補助データ構造が導入される。とりわけただ１つのＡＴＭ回路だけが仮想接続（ＶＣＣ）に対して考慮されるので、その中にＡＴＭセル１３ないしそれの実際のメモリスペースへの指示を記憶しなければならない。この記憶は、セルを通常の比較的に後の時点で送信できるようになるまで行う。ここで一般的には、セル合成、スペーシングおよびセルマルチプレキシングに基づく遅延を考慮しなければならない。これらの機能は、データ構造がファストインファストアウト待ち行列の場合にような記憶を可能にする限り問題なしに実施することができる。
トラフィックコントラクトとはそれぞれ回路ごとに仮想接続ＶＣＣに対して変換されるから、スペーシングは回路毎に仮想接続ＶＣＣに対して実施される。前に説明したスペーシングメカニズムは、ＣＢＲトラフィックコントラクトの場合にはこの目的のために使用される。ここでアルゴリズムの変数は大部分がトラフィックコントラクトにより固定的に設定される。この実施例でこれらは、１接続当たりの最大データ速度ＰＣＲおよびセル遅延変動トレランスＣＤＶＴである。さらに仮想接続に対する回路毎の変数〈ＴＳＴ〉が記憶される。
ＶＣＣ待ち行列が高い割合で満たされたことは、ＡＴＭセルに対する長い遅延を意味する。このことはリアルタイム動作では許容できない。従って適用目的のために、個々のＶＣＣ待ち行列１２に対して閾値を設けることができる。この閾値はＡＴＭセル１３の最大数を定める。閾値より上では、相応のＶＣＣ待ち行列１２のＡＴＭセル１３はもはや考慮されない。
インテリジェント型プラニングメカニズムを編成するために、仮想チャネル接続、ないしそのＶＣＣ待ち行列１２に対するＶＣＣリストエレメント１６は有利には二重の連鎖リストとして作成される。これは図３に示されている。有利な実施例によれば、各ＶＣＣ待ち行列１２に対して１つのＶＣＣリストエレメント１６が作成される。この各ＶＣＣリストエレメント１６はすでに前に説明した仮想接続識別子（ＶＣＩ：Ｖｉｒｔｕａｌ Ｃｏｎｎｅｃｔｉｏｎ Ｉｄｅｎｔｉｆｉｅｒ）を有している。この識別子は実質的に、ＶＣＣ待ち行列１２、ないしそのメモリスペースへの一定のポインタである。さらに各ＶＣＣリストエレメント１６には次ポインタ１７（ネクスト）と前ポインタ１８（以前）が配属されており、これらは隣接するＶＣＣリストエレメント１６を指示する。特に有利な実施例では、仮想接続識別子が変化せず、この構造をとりわけ効率的にファイルすることができる。
二重に連鎖したＶＣＣリスト１５を作成するために、ヘッドポインタ１９とテールポインタ２０が使用される。ヘッドポインタ１９（ｈｅａｄ）は、ＶＣＣリスト１５内で最初に処理すべきＶＣＣリストエレメント１６を指示する。リストにある最後のＶＣＣリストエレメント１６以外はすべて、その前ポインタ１８により後から処理すべきＶＣＣリストエレメント１６を指示する。リストにある最後のリストエレメントは一定のゼロを指示し、これはＶＣＣリスト１５を閉じる。相応のことがテールポインタ２０（ｔａｉｌ）、およびＶＣＣリストエレメント１６の次ポインタにおいて逆方向で言える。
ＶＣＣリストエレメント１６’をＶＣＣリスト１５から除去することは次のように行われる：次ポインタ１７（Ｎｅｘｔ）、ないし第１のＶＣＣリストエレメント１６’の場合はヘッドポインタ１９（ｈｅａｄ）が除去すべきＶＣＣリストエレメント１６を指示する。このポインタを新たに、除去すべきＶＣＣリストエレメント１６’の次ポインタ１７（Ｎｅｘｔ）が指示するＶＣＣリストエレメント１６”に向けなければならない。相応のことが反対方向のポインタにも当てはまる。このようにして個々のＶＣＣリストエレメント１６’の除去を大きなコストをかけずに、前もって既知の短い時間で行うことができる。この種の二重連鎖リストの利点は、単純な連鎖リストの場合は多数のリストエレメントのポインタまたは内容を比較しなければならないことである。
前に説明した構造の点で、有利なタイムプランナ９は実質的に２つの異なるユニットからなる。カレンダー１１は、仮想チャネル接続からの、ないし仮想チャネル接続に対する将来的送信問い合せを、ＶＣＣ待ち行列１２のアドレスの形態で保持する。このＶＣＣ待ち行列は前記の仮想チャネル接続に割当てられており、送信すべきセル１３を含んでいる。送信待ち行列１０は、正のＡＴＭマルチプレキシング遅延の場合に対する送信問い合せ、ないしその内容を最も近いセルサイクルで送信すべきＶＣＣ待ち行列１２に対する送信問い合わせを保持する。
各仮想チャネル接続ＶＣＣに対して、ないし相応に配属されたＶＣＣ待ち行列１２に対して、所定のセルサイクルを次の送信時間〈ＮＳ〉として選択ないしリザーブすることができる。この所定のセルサイクルでは、次のＡＴＭセル１３がこの仮想チャネル接続を介してＶＣＣ待ち行列１２から送信される。ＶＣＣ待ち行列１２のそれぞれ第１のセルをリザーブされたセルサイクルでこのように読出すための順序は、カレンダー１１に登録される。後で説明する方法ステップでの概念選択の点から、分かり易くするために瞬時のセルサイクルに対しては概念「今日」ないし〈Ｔｏｄａｙ〉、およびこれに続くセルサイクルに対しては概念「明日」ないし〈Ｔｏｍｏｒｒｏｗ〉が使用される。個々の「日にち」は個々のセルサイクルにそうそうし、このセルサイクルはこの実施例では実際に２．７μｓの持続時間を有する。
リザーブのために計算された現在〈Ｔｏｄａｙ〉のＫより後の時点に対するリザーブのための登録が付与されていないと仮定すれば、〈ＮＳ〉ｍｏｄ Ｋのモジュロ計算の結果は列番号ないしカレンダー待ち行列番号に等しく、これがカレンダーにセットされる。モジュロ計算の際には２つの数値が割算される。すなわち第１の数が第２の数により割算され、このとき流動点数は整数に丸められ、結果としてこの割算ステップの余りがリターンされる。その結果、１９ ｍｏｄ ６．７は５となる。この想定の下では、Ｋ列を有するフィールドによりすべてのセルサイクルを表すことができ、すべてのセルサイクルを参照することができる。従ってカレンダー１１は日にち「明日」（〈Ｔｏｍｏｒｒｏｗ〉）から付加的にＫ日までの列を有する（〈Ｔｏｄａｙ〉＋Ｋ−１）。
有利には、１つ以上の仮想チャネル接続に対する所定のセルサイクルを、この仮想チャネル接続に対して次に可能な送信時間〈ＮＳ〉として要求することができる。このことを可能にするため、カレンダー１１はＬ個の領域を備えるフィールドを有する。これらの領域にはそれぞれ１つの個別のＶＣＣリストエレメント１６が記憶されるのではなく、ＶＣＣリスト１５が記憶される。このことは図２に示されている。二重に連鎖されたＶＣＣリスト１５は再び多数のＶＣＣリストエレメント１６を含み、このＶＣＣリストエレメント１６はそれぞれ１つのＶＣＣ待ち行列１２を表す。
有利な実施形態によれば、次に送信すべきセルとしてＶＣＣ待ち行列１２内に配置されたセル１３に対して、所望の送信時間を指示するのに２つの場合が考えられる。第１の場合では、所望の送信時間が過去に存在するか、または現在のセルサイクルないし送信サイクルに存在する。この場合、相応のＶＣＣ待ち行列１２に割当てられたＶＣＣリストエレメント１６は送信待ち行列１０に直接はめ込まれる。第２の場合では、所望の送信時間が将来の時点ないし送信サイクルに対して配置されている。この場合、このＶＣＣ待ち行列１２に割当てられたＶＣＣリストエレメントはカレンダー１１の列に登録される。この列を指示するために、前記のモジュロ計算が使用される。相応の待ち行列、すなわち送信待ち行列１０または相応のカレンダー待ち行列１７にすでにＶＣＣリストエレメント１６が存在する場合、この追加すべきＶＣＣリストエレメント１６はＶＣＣリストエレメントと前記のように二重に連鎖される。
ＶＣＣ待ち行列１２，送信待ち行列１０、およびカレンダー待ち行列１７を有するカレンダーのこのような構成により、スペーシング機能およびＡＴＭマルチプレキシングが非常に短い時間で実行されるようになる。
ＶＣＣ待ち行列１２からないしＶＣＣ待ち行列１２に対して、所定の時点ないし所定の日付〈ＴＴ〉に対する送信要求が出力される場合、またはこのような要求がタイムプランナ９またはシステム制御装置から到来する場合、可能な限り最も早い送信日付が図５に示したアルゴリズムによって計算される。この場合、次の送信時点〈ＮＳ〉に対しては〈ＮＳ〉＝次のスペーシング（〈ＴＴ〉）が当てはまる。時間発生器をこのイベントに対して調整およびコントロールする代わりに、相応の日付ないし相応の時間的送信領域をカレンダー１１に登録する。以下、このステップを実施するための相応の機能をレジスト（〈ＴＴ〉）と称する。相応にしてこのＶＣＣ待ち行列１２に割当てられたＶＣＣリストエレメント１６はカレンダー１１の列に登録される。この列は〈ＮＳ〉ｍｏｄ Ｌにより計算される。所定のセルサイクル〈ＴＴ〉を要求するために、このプログラム機能はレジスタ（〈ＴＴ〉）を使用することができる。これはプログラム技術的に一般的な機能であり、次の目標時間〈ＴＴ〉に対してセルサイクルが調整可能であるか否かを検査する。ここでスペーシングは次の送信時間を与え、これに基づいて相応のリストエレメントがカレンダー１１に登録される。
この実施例では、各ＶＣＣ待ち行列１２にはただ１つのＶＣＣリストエレメント１６しか割当てられない。従って個々のＶＣＣ待ち行列１２、例えば第１のＶＣＣ待ち行列１２は開いている。すなわち別のセル１３に対して割当てられていない送信要求を有している。このことは前に図４と図５に基づいて説明した、２つのアルゴリズム「次のスペーシング」ないし「スペーシング更新」によるものである。
ＶＣＣリストエレメント１６を二重連鎖ＶＣＣリストに追加するための簡単な択一例がある。ＶＣＣリストエレメント１６を始端部に継ぎ合わせることにより、ラストインファストアウト指示（ＬＩＦＯ：Ｌａｓｔ Ｉｎ Ｆｉｒｓｔ Ｏｕｔ）が送信待ち行列１０のこのＶＣＣリスト１５で得られる。一方、このＶＣＣリストエレメント１６を終端部に継ぎ合わせることにより、ファストインファストアウト順序（ＦＩＦＯ：Ｆｉｒｓｔ Ｉｎ Ｆｉｒｓｔ Ｏｕｔ）がこのＶＣＣリスト１５の個々のＶＣＣリストエレメント１６の処理の際に得られる。
接続当たりで高いデータ速度または最大のデータ速度ＰＣＲを有する仮想ＡＴＭチャネル接続ＶＣＣ、すなわち帯域幅の大きな仮想ＡＴＭチャネル接続ＶＣＣに対しては、その次の送信セルサイクルは近い将来、低いまたは最小のデータ速度を有する仮想ＡＴＭチャネル接続に対するものとして存在する。従ってセルサイクルは低いデータ速度を有する仮想ＡＴＭチャネル接続によって、高いデータ速度を有する仮想ＡＴＭチャネル接続よりも早期に要求される。言い替えると、高速接続の場合、セル間隔は非常に小さく、これは送信時点の変化の比較的大きな作用によるものである。これに対して緩慢な接続では送信時点シフトはさほど重要ではない。従って公正なリソース割り当ての観点から、データ速度の高い仮想ＡＴＭチャネル接続をデータ速度の低い仮想ＡＴＭチャネル接続よりも優先させる。なぜならこれらは同じ絶対的ＡＴＭマルチプレキシングジッタによりより大きく影響を受けるからである。相応に、ＶＣＣリストエレメントをカレンダー１１のＶＣＣリスト１５の始端部に付き合わせることを優先する。
セルサイクルの終了時には、次のセルサイクルに対して、すなわち「明日」〈Ｔｏｍｏｒｒｏｗ〉に対して登録されたＶＣＣリストエレメント１６がカレンダー１１の第１のカレンダー待ち行列１７から送信待ち行列１０へ伝送される。このことにより二重に連鎖されたＶＣＣリスト１５が個所〈Ｔｏｍｏｒｒｏｗ＋１ ｍｏｄ Ｌ〉においてカレンダー１１から除去され、送信待ち行列１０の二重に連鎖されたＶＣＣリスト１５の終了部に継ぎ合わせる。
各セルサイクルの開始時に複数のアクションを実行することができる。第１として、現在および次の「日」、すなわち〈Ｔｏｄａｙ〉および〈Ｔｏｍｏｒｒｏｗ〉に対するシステム変数が１だけ増分される。次にＡＴＭセル１３の潜在的送信が準備され、開始される。このために第１のＶＣＣリストエレメント１６が送信待ち行列委１０から除去され、相応のＶＣＣ待ち行列１２がトリガされ、その次のセル１３が送信される。このセルが相応のセルサイクル内で変化するのを保護するためにセルコンテクストで送信マーカー〈ＳＦ〉（ＳＦ：Ｓｅｎｄ Ｆｌａｇ）がセットされる。このＶＣＣ待ち行列１２に対する理論的送信時間〈ＴＳＴ〉に対するスペーシング変数は同様に更新される。これは前に説明したスペーシングプロシージャ「スペーシング更新」の呼び出しによって行われる。ＶＣＣ待ち行列１２がまだ空でなければ（これは最下部のセル１３が読出された後の第１のＶＣＣ待ち行列１２の場合である）、このＶＣＣ待ち行列１２のＶＣＣリストエレメント１６またはカレンダー待ち行列１７の１つが、ＶＣＣ待ち行列１２の次のセル１３に対するセルサイクルの準備によって使用される。
有利にはこのシステムによってＶＣＣリストエレメント１６の新たな配列も可能になる。すでに存在している送信問い合わせは、相応のＶＣＣリストエレメント１６をカレンダー１１または送信待ち行列１０から単純に除去することにより除去される。二重に連鎖されたＶＣＣリスト１５の構成によって、このことは前に説明した方法により高速に行われる。この場合、送信待ち行列１０またはカレンダー１１のカレンダー待ち行列１８のＶＣＣリストエレメントを区別せずにも行われる。ＶＣＣ待ち行列１２に対してすでに存在する送信問い合わせの変化は相応に、そのＶＣＣリストエレメント１６を単純に除去し、このＶＣＣリストエレメント１６を新たな目標時間に対して新たにセットすることにより変換できる。このような方法は例えばアルゴリズム「レジスト」（〈ＴＴ〉）により実行することができる。アルゴリズム「レジスト」（〈ＴＴ〉）に相応して、このようなアルゴリズムはＶＣＣリストエレメント１６をその構造から取り出し、レジストアルゴリズムの場合のように適切な個所に再び配列する。
この過程すべての実行時間は一定である。とりわけ実行時間は仮想チャネル接続ＶＣＣの数に依存する。アルゴリズムの全体経過時間は、ＶＣＣ待ち行列１２の１つに対してどれだけ頻繁にセルサイクルが要求され、どれだけ頻繁にこのような要求が変化するかに依存している。
前に説明したタイムプランナ９により、ＡＴＭマルチプレキシングに対する簡単な構造によってスケーラブルが可能となる。これにより、伝搬時間がＶＣＣ待ち行列の数に依存しなくなり、少数のセルサイクルによる適用が実現され、ダイナミックなメモリ占有を行う必要がなくなる。有利にはＶＣＣリストエレメントを配置換えするのには、単に所定のポインタ再配向を行えばよい。さらに簡単なスペーシング手段が得られ、実行されたＶＣＣはピークセル速度（ＰＣＲ）について同形であり、スペーシングはＶＣＣかでの公正さを形成する。さらなる利点は所望の時点（タイミング）の設定にあり、絶対的時点に対する送信希望を許可することができる。ただしこれは時間発生器機能によって可能な場合である。最後に送信時点の変更（リタイミング）も可能である。さらに多数の拡張が可能である。
他の通信システムに伝送するためには、相応の変形が行われる。インターネットプロトコル領域では別のクロック配分がここに説明したセルサイクルの代わりに使用される。列状のカレンダー待ち行列の代わりに３次元のメモリ空間を使用することもできる。
以下、ＡＡＬ２規格に対する接続装置の有利な実施形態を説明する。この実施形態は前に説明したプランナに基づいており、とりわけ区別のためにＡＣＥプランナ（ＡＣＥ：ＡＡＬ２ Ｃｏｎｎｅｃｔｉｎｇ Ｅｌｅｍｅｎｔ）と称する。そのためにまず非同期伝送モード（ＡＴＭ）を簡単に説明し、なぜＡＡＬ２が必要であるか、これがどのように機能するのかを説明する。さらにＡＡＬ２プランナ９に対するシナリオを説明する。
非同期伝送モードを有するＡＴＭネットワークでは、セルが４８バイトの固定のペイロードと、５バイトの大きさの情報ヘッド部分ないし情報ヘッダを有する。これは接続指向の過程であり、従ってデータを伝送するのに仮想チャネル接続（ＶＣＣ）を使用する。帯域幅は種々のＶＣＣの下で、ＡＴＭセルの非同期マルチプレキシングにより分割される。このＡＴＭセルは種々異なるＶＣＣに所属する。これが意味するのは、ＶＣＣ待ち行列ないしこれに割当てられた仮想チャネル接続ＶＣＣは所定のタイムスロットに割当てられていないということである。これは時分割多重アクセスシステク（ＴＤＭＡ）と接続されていないシステムの場合と同じである。これらのセルは到来すると直ちに送信される。従って１つの以上のＶＣＣがある場合、１つのセルを同時に送信するために１つだけのＶＣＣ待ち行列１２の管理を許容することができる。このことにより他のＶＣＣ待ち行列１２はセル１３の送信を同時に待機しなければならず、１つのセル１３だけを送信することができる。その結果、他のＶＣＣのセルを時間的に遅延しなければならない。このことはＡＴＭマルチプレキシング遅延を引き起こす。このタスクはタイムプランナ９により実行され、タイムプランナは仮想チャネル接続ＶＣＣへの送信割り当てを実行する。
標準的プロトコルＡＡＬ２から、グループないしサンプルにまとめられた複数の音声データを１つのＡＴＭセルにマルチプレキシングすることが公知である。このために音声サンプルには３バイトの大きさのヘッダ部分（ヘッダ）が設けられている。このヘッダ部分はとりわけ接続識別子（ＣＩＤ：Ｃｏｎｎｅｃｔｉｏｎ Ｉｄｅｎｔｉｆｉｅｒ）と長さ指示子（ＬＩ：Ｌｅｎｇｔｈｓ Ｉｎｄｉｃａｔｏｒ）を有する。音声パケットはＡＡＬ２パケットヘッダ部分も含めて一般的にコモンパートサブレイヤ（ＣＰＳ）パケットと称される。
次に図７に基づいて、ＡＣＥタイムプランナ９の実施例を説明する。ＡＣＥタイムプランナは個のＡＡＬ２規格に従ってマルチプレキシングを実行する。
ＡＣＥタイムプランナ２０には、多数の仮想チャネル接続がここではＡＡＬ２接続２１として入力される。ＡＣＥタイムプランナ２０内では、各ＡＡＬ２接続２１にＡＴＭ・ＶＣＣ待ち行列２２が割当てられている。ここでこれらのＡＴＭ・ＶＣＣ待ち行列２２にはそれぞれ１つのＡＡＬ２マルチプレクサ２３が前置接続されている。最後にＡＴＭ・ＶＣＣ待ち行列２２のセルはＡＴＭマルチプレクサ２４でマルチプレキシングされ、有利には１５５Ｍｂｐｓの物理的出力線路に出力される。これも有利には仮想構造である。
できるだけすべての遅延源、例えば所要のマルチプレキシング時間ＴＣＵ、処理およびＡＴＭマルチプレキシング遅延をＡＡＬ２マルチプレキシングの際に考慮すべきであるから、比較的に古いセルが完全に充填されるか、このセルが送信プロセスに存在しておらず、相応の送信マーカ〈ＳＦ〉がセットされる場合に新たなＡＴＭセルの充填が開始される。従ってＶＣＣ待ち行列２２では最も新しいＡＴＭセル以外のすべてセルが充填される。ＡＡＬ２マルチプレキシングのために、マルチプレキシング時間ＴＣＵが各仮想チャネル接続２１に対してリアルタイムで指示される。最も新しいＡＴＭセルが充填されるから、変数〈Ｔｏｕｔ〉だけが１つの仮想チャネル接続２１ごとに使用され、いつマルチプレキシングプロセスが過度に持続して掛かったかが指示される。この要求をすべてで満たすために、マルチプレクサはプラニング機構に有利には組み込まれる。ＶＣＣ待ち行列はさらに、前に説明したＡＡＬ２機能だけ拡張される。
ＡＡＬ２パケットが到来すると、機能パケットセットが呼び出される。このことは図８のフローチャートに示されている。機能パケットセットが開始した後、パケット、とりわけＣＰＳパケットが閾値を越えたか否かという検査が継続される。ｊａ（肯定）の場合、このパケットはさらなる処理から除外され、機能パケットセットは終了する。ｎｅｉｎ（否定）の場合、次のステップで、ＶＣＣ待ち行列が空であるか否かが検査される。ｊａの場合、新たなセルが構築され、変数〈Ｔｏｕｔ〉が、変数〈ｎｏｗ〉とマルチプレキシング時間ＴＣＵに対する変数との和にセットされる。次にレジスト機能が、このセルをカレンダー１にセットないしレジストのために呼び出される。このレジスト機能はここでは機能レジスト（〈Ｔｏｕｔ〉）としてし召されている。これに続いて機能パケットセットは終了される。
ＶＣＣ待ち行列が空でなければ、１つのセルだけがＶＣＣ待ち行列に存在し、送信マークないし送信フラグ〈ＳＦ〉がセットされているか、ないし真であるか否かが検査される。ｊａの場合、再び新たなセルを構築するための機能が呼び出され、続いて機能パケットセットは終了する。最後に述べた条件が真でなければ、この第１のセルが完全であるか否か、およびこの仮想チャネル接続ないしＶＣＣ待ち行列に対する変数〈Ｔｏｕｔ〉が瞬時のセルサイクル〈ｎｏｗ〉より大きいか否かがさらに検査される。ｊａの場合、新たな割り当てが行われる。この割り当ては前に再レジスト（〈Ｔｏｍｏｒｒｏｗ〉）として説明したように、古いレジストの除去を含む。次の日付値に対するこの新たな割当ての後、または前記の問い合せが否定の場合、プログラム経過はさらなる問い合せに進み、空きスペースがＡＴＭセル中で十分であるか否かが検査される。スペースが十分であれば、機能パケットセットは終了する。空きスペースが最後のＡＴＭセル中で十分でなければ、この到来すべきＡＡＬ２パケットのデータを収容するために、新たなセルを作成しなければならない。このために相応に、変数〈Ｔｏｕｔ〉が再び、瞬時のセルサイクルに対する変数〈ｎｏｗ〉とこの所要のセルをマルチプレキシングするための変数ＴＣＵとの和として形成される。続いて機能パケットセットが終了する。
この機能で強調すべきことは、この場合、新たなセルの形成を開始しなければならないことである。これは、使用可能なＶＣＣ待ち行列２２が空の場合、またはその中に送信マーク〈ＳＦ〉のセットされたＡＴＭセルが１つだけ存在する場合、すなわちちょうど送信されるセルが存在する場合、すべてのパケットをこの新たなセルにセットするためである。この場合、変数〈Ｔｏｕｔ〉は瞬時の時間値ないしセルサイクル〈ｎｏｗ〉と、マルチプレキシングに必要な時間ＴＣＵとの和として更新され、これに基づいてＡＴＭセルは時間〈Ｔｏｕｔ〉に対するカレンダー１１にレジストされる。
さらに、第１のセルが新たなパケットの収容によって十分に充填された場合、または終了する場合、およびこの時間がマルチプレキシングにまだ十分でない場合、すなわち変数〈Ｔｏｕｔ〉が瞬時の時間値〈ｎｏｗ〉より大きい場合を強調すべきである。この場合、例えば機能再レジストの呼び出しによって、ＡＴＭセルのリストエレメントがカレンダー１１から除去され、次のセルサイクル〈Ｔｏｍｏｒｒｏｗ〉に対して、スペーシングを考慮する機能レジストによりレジストされる。その結果、そのセルを次のセルサイクルで送信することができる。最後のＡＴＭセルが十分でない場合、ないし十分なスペースを使用できない場合、新たなセルをすでに作成し、所望の送信時間に対する変数〈Ｔｏｕｔ〉を相応に更新しなければならない。
続いて、ＡＴＭセルの送信を図９のフローチャートに基づいて説明する。ここでは相応の機能がＡＴＭセル送信と称される。
この種のタイムプランナ９についての前記基本的実施例に相応して、相応のＶＣＣリストエレメント１６が送信待ち行列１０に存在する場合、ＡＴＭセル１３がセルサイクルの開始時に送信される。送信過程の始めに、ＶＣＣリストエレメント１６が送信待ち行列１０から除去され、相応のＶＣＣ待ち行列１２／２２のセルが送信のためにトリガされ、この仮想チャネル接続ないし割当てられたＶＣＣ待ち行列１２のスペーシング変数が更新される。さらに次のセル１３がカレンダー１２でセットされる。すなわち、機能スペーシング更新（）を使用してセットされる。ＡＡＬ２によるマルチプレキシングによって発生する時間的制限のため、この過程は微調整しなければならない。
図９に示されているように、機能ＡＴＭセル送信ではその開始後にロックがセットされる。これによりそれ以上マルチプレキシングされることはない。読出し・書込み問題の点で不一致を回避するために、すなわち記憶領域への読出しアクセスと書込みアクセスが同時に行われることによるコリージョンを回避するために、送信マーク〈ＳＦ〉がセルコンテクストでセットされる。これに基づいてセルの送信が開始され、機能スペーシング更新（）が呼び出され、仮想チャネル接続に対してその〈ＴＳＴ〉変数が更新される。
次のステップでは、ＶＣＣ待ち行列が空であるか否かが検査される。これが空である場合、機能ＡＴＭセル送信は終了する。なぜなら、送信すべきセルが存在しないからである。ＶＣＣ待ち行列が空でない場合、この第１のセルがＶＣＣ待ち行列で満たされているか否かが検査される。
第１のセルがＶＣＣ待ち行列にすでに満たされていれば、またはその時間が経過していれば、機能ないしサブプログラム、レジスト（〈Ｔｏｍｏｒｒｏｗ〉）が呼び出され、このＶＣＣ待ち行列に対して次の「明日の」セルサイクルが割当てられる。それ以外の場合、セルはカレンダー１１に所望の出力時点、ないし希望に相応して計算された出力時点が送信〈Ｔｏｕｔ〉に対してレジストされる。そのために再び比較が実行され、セットされた出力時間〈Ｔｏｕｔ〉の変数値が明日の時間値〈Ｔｏｍｏｒｒｏｗ〉より大きいか否かが検査される。これに依存して、機能レジスト（〈Ｔｏｕｔ〉）または機能レジスト（〈Ｔｏｍｏｒｒｏｗ〉）が呼び出され、その後に機能ＡＴＭセル送信が終了する。
まとめると、この最後に説明したＡＣＥタイムプランナに対しては次のことが分かる：入力側でタイムプランナにはＡＡＬ２パケットが１つまたは複数のＡＡＬ２パケット入力流を介して到着する。このとき複数のＡＡＬ２経路を使用することができる。出力側では１つまたは複数のＡＴＭセル流が有利には１つの出力線路で出力される。ＡＡＬ２マルチプレキシング、スペーシングおよびＡＴＭマルチプレキシングは統合されている。冒頭に記載した有利なタイムプランナの基本コンセプトに基づいて、ここではＡＴＭマルチプレキシングが前に説明したタイムプランナにより行われるが、ＡＡＬ２マルチプレキシングは仮想チャネル接続の待ち行列で行われる。複数のＡＡＬ２パケットの１つのＡＴＭセルへのマルチプレキシングが行われ、ここで時間発生器は最大マルチプレキシング時間を制限する。さらにスペーシングとＡＡＬ２マルチプレキシングがＡＴＭマルチプレキシングに対してセルサイクルごとにサポートされるという時間計画が行われる。ここでＡＴＭセルは複数のＶＣＣ待ち行列で送信待機することができるが、１つの仮想チャネル接続ないしその待ち行列だけが同時に１つのＡＴＭセルを送信する。さらにスペーシングが実行される。ここでは各仮想チャネル接続に対してトラフィックコントラクトが維持されることに注意すべきである。これはとりわけＰＣＲおよびＣＤＶＴの点でそうである。相応の制御により、送信時間の割当てに対しては公正な配分に注意するというコンセプトが含まれる。全体としてこの手段により全構成素子ないし全接続装置のスループットの最大化が達成される。大きな利点がリアルタイム処理またはほぼリアルタイムの処理で得られる。
スペーシングを実行するのは、他のネットノードを比較的に後の時点で監視を実行し、そこで密に順次連続するデータが消去されることがあるからである。
【図面の簡単な説明】
【図１】
図１は、データパケットないしデータセルをスイッチングするための基礎となる装置を備える物理的線路でのスイッチング装置を示す。
【図２】
図２は、仮想接続に対する多数の待ち行列、送信待ち行列およびカレンダー状のテーブルを備えるタイムプランナを示す。
【図３】
図３は、二重に連鎖されたＶＣＣリストを示す。
【図４】
図４は、セル流を監視するための包括的セル速度アルゴリズムのフローチャートである。
【図５】
図５は、理論的送信時間を設定するためのアルゴリズムのフローチャートである。
【図６】
図６は、理論的送信時間を更新するためのアルゴリズムのフローチャートである。
【図７】
図７は、ＡＡＬ２規格に対して拡張されたタイムプランナの一部を示す図である。
【図８】
図８は、データパケットをタイムプランナのマルチプレクサに入力するためのアルゴリズムのフローチャートである。
【図９】
図９は、データパケットをこのタイムプランナから出力するためのアルゴリズムのフローチャートである。
【図１】
2004512738.tif 000003
【図２】
2004512738.tif 000004
【図４】
2004512738.tif 000005
【図５】
2004512738.tif 000006
【図６】
2004512738.tif 000007
【図８】
2004512738.tif 000008
【図９】
2004512738.tif 000009
【国際公開パンフレット】
2004512738.tif 000010
2004512738.tif 000011
2004512738.tif 000012
2004512738.tif 000013
2004512738.tif 000014
2004512738.tif 000015
2004512738.tif 000016
2004512738.tif 000017
2004512738.tif 000018
2004512738.tif 000019
2004512738.tif 000020
2004512738.tif 000021
2004512738.tif 000022
2004512738.tif 000023
2004512738.tif 000024
2004512738.tif 000025
2004512738.tif 000026
2004512738.tif 000027
2004512738.tif 000028
2004512738.tif 000029
2004512738.tif 000030
2004512738.tif 000031
2004512738.tif 000032
2004512738.tif 000033
2004512738.tif 000034
2004512738.tif 000035
2004512738.tif 000036
2004512738.tif 000037
2004512738.tif 000038
2004512738.tif 000039
2004512738.tif 000040
2004512738.tif 000041
2004512738.tif 000042
2004512738.tif 000043
2004512738.tif 000044
2004512738.tif 000045
2004512738.tif 000046
2004512738.tif 000047
2004512738.tif 000048
2004512738.tif 000049
2004512738.tif 000050
2004512738.tif 000051
2004512738.tif 000052
2004512738.tif 000053
2004512738.tif 000054
【国際調査報告】
2004512738.tif 000055
2004512738.tif 000056
2004512738.tif 000057
2004512738.tif 000058