(57)【特許請求の範囲】
【請求項１】
デジタルネットワークにおいて、情報転送ユニットの転送に関連して使用される待ち行列制御システムであって、ネットワークは、複数のサービスレートを有しており、待ち行列制御サブシステムは、
Ａ．情報転送ユニットを受信する情報転送ユニット受信装置と、
Ｂ．情報転送ユニット受信装置が受信した情報転送ユニットを一時記憶する一時記憶装置と、
Ｃ．一時記憶装置における情報転送ユニットの一時記憶を制御するグループ制御装置であって、複数のグループ別に一時記憶装置に情報転送ユニットを集め、各グループは、複数のサービスレートの１つに関係するグループ制御装置とを具えており、
全ての情報転送ユニットは、複数のサービスレートの１つに関係しており、複数のクループの中の同じグループに集められ、
各情報転送ユニットは、ネットワークを通る経路を識別する経路識別子に関係し、 各経路は、複数のサービスレートの中の関連する１つを有し、
グループ制御装置は、情報転送ユニットの経路識別子と、情報転送ユニットの個々のサービスレートとに基づいて、一時記憶装置内の情報転送ユニットを複数のグループに集め、
各グループは、経路待ち行列のリストを具えており、
各リストは、個々のリスト内に、経路待ち行列の中の１つである先頭経路待ち行列を有しており、
グループ制御装置は、経路識別子を伴った情報転送ユニットを、その経路識別子に関連した一時記憶装置内の経路待ち行列に集め、
グループ制御装置は、伝送する情報転送ユニットを選択する伝送選択装置を含んでおり、
伝送選択装置は、
Ａ．各グループの先頭経路待ち行列のタイムスタンプに対応して、１つのグループを選択されたグループとして識別するグループ選択装置と、
Ｂ．選択されたグループの先頭経路待ち行列から、伝送する情報転送ユニットを選択する情報転送ユニット選択装置とを具える待ち行列制御システム。
【請求項２】
各情報転送ユニットはセルを含んでいる、請求項１に規定された待ち行列制御システム。
【請求項３】
セルは所定の長さを有する、請求項２に規定された待ち行列制御システム。
【請求項４】
経路待ち行列は、経路待ち行列末尾メンバを有しており、
グループ制御装置は、情報転送ユニットの受信に応答して、経路識別子に関連する情報転送ユニットに関連する経路待ち行列に対して、情報転送ユニットを経路待ち行列に経路待ち行列末尾メンバとして追加する、請求項１に規定された待ち行列制御システム。
【請求項５】
新たな経路識別子に関連する情報転送ユニットの情報一時記憶装置制御サブシステムによる受信に応答して、その情報転送ユニットに関する経路待ち行列をグループ制御装置に配備するリソースアロケータを含んでいる、請求項１に規定された待ち行列制御システム。
【請求項６】
グループ制御装置は、個々にサービスレートに関連しているグループの中の少なくとも１つのグループに、経路待ち行列を集める、請求項１に規定された待ち行列制御システム。
【請求項７】
少なくとも１つのグループは、グループリストを具える、請求項６に規定された待ち行列制御システム。
【請求項８】
各情報転送ユニットは、ネットワークを通る経路を識別する経路識別子に関係しており、
各経路は、サービスレートに関連しており、
グループ制御装置は、情報一時記憶装置制御サブシステムが情報転送ユニットを受信している経路の各サービスレートについて、関連するグループを保持しており、
各グループは、各々の経路待ち行列が経路に関連している経路待ち行列のリストを具え、その経路に関連した情報転送ユニット受信装置が受信する情報転送ユニットを含んでいる、請求項１に規定された待ち行列制御システム。
【請求項９】
各経路待ち行列は、関連するサービスタイムスタンプを有しており、
グループ制御装置は、タイムスタンプによって決定される順番に経路待ち行列のリストを保持し、
少なくとも１つのグループは、第２リストを含んでおり、
グループ制御装置は、グループのサービスレートに新たに関連した経路に関する経路待ち行列を前記第２リストに接続する、請求項８に規定された待ち行列制御システム。
【請求項１０】
伝送のために情報転送ユニットを選択する伝送選択装置を含んでおり、
伝送選択装置は、グループ内の経路待ち行列を、各経路待ち行列のタイムスタンプに基づいて選択し、
伝送選択装置は、
Ａ．各グループリストの各グループの先頭経路待ち行列のタイムスタンプに対応して、１つのグループを選択されたグループとして識別するグループ選択装置と、
Ｂ．選択されたグループの先頭経路待ち行列から、伝送する情報転送ユニットを選択する情報転送ユニット選択装置とを具える、請求項９に規定された待ち行列制御システム。
【請求項１１】
伝送選択装置は、各グループの先頭経路待ち行列のタイムスタンプが最低値であるグループの１つを、選択されたグループとして選択する、請求項１０に規定された待ち行列制御システム。
【請求項１２】
各グループの第１リストは、末尾経路待ち行列を含んでおり、
伝送選択装置は、第２リストの先頭経路待ち行列を含む経路待ち行列が、第１リストの末尾経路待ち行列としてリストにリンクされるように、選択したグループに関連したリストを再整理するグループリスト再整理要素を含む、請求項１０に規定された待ち行列制御システム。
【請求項１３】
少なくとも１つのグループは、第３リストを含んでおり、
グループ制御装置は、グループのサービスレートに新たに関連した経路に関する経路待ち行列を、経路待ち行列のタイムスタンプに基づいて、第２リストまたは第３リストの何れかに接続する、請求項９に規定された待ち行列制御システム。
【請求項１４】
デジタルネットワークにおいて、情報転送ユニットの形式にて情報を転送する際に使用される伝送スケジューラであって、
ネットワークは、複数のサービスレートを有しており、
各情報転送ユニットは、ネットワークを通る経路を識別する経路識別子に関係しており、
各経路は、サービスレート及びタイムスタンプを有する経路待ち行列に関連しており、
伝送スケジューラは、
Ａ．伝送する情報転送ユニットを選択する伝送選択装置であって、各経路待ち行列のタイムスタンプ及びサービスレートに基づいて、経路を選択する伝送選択装置と、
Ｂ．伝送選択装置が提供する情報転送ユニットを伝送する情報転送ユニット伝送装置とを具えており、
対応するサービスレートに関連した経路に関する情報転送ユニットは、それらユニットのサービスレートに関連したグループにて保持され、
各グループは、経路待ち行列のリストを具えており、
各リストは、個々のリスト内に、経路待ち行列の中の１つである先頭経路待ち行列を有し、
伝送選択装置は、
Ａ．各グループの先頭経路待ち行列のタイムスタンプに対応して、１つのグループを選択されたグループとして識別するグループ選択装置と、
Ｂ．選択されたグループの先頭経路待ち行列から、伝送する情報転送ユニットを選択する情報転送ユニット選択装置とを具えていることを特徴とする伝送スケジューラ。
【請求項１５】
各情報転送ユニットはセルを含んでいる、請求項１４に規定された伝送スケジューラ。
【請求項１６】
セルは所定の長さを有する、請求項１５に規定された伝送スケジューラ。
【請求項１７】
無制限のサービスレートを含むネットワークにて使用するために、グループ制御装置は、無制限のサービスレートに関連する経路に関する無制限グループを形成し、
どのグループも適格なグループでないと適格性決定要素が判別した場合、伝送選択装置は、情報転送ユニットが伝送されるべき経路を無制限グループから選択する、請求項１４に規定された伝送スケジューラ。
【請求項１８】
少なくとも１つの経路は、別の伝送スケジューラによって提供される、請求項１４に規定された伝送スケジューラ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般的にはディジタル通信システムに関係するものであり、ディジタル式に画像、音声、ビデオ映像を配送するシステム中や、ディジタル・コンピュータシステム同士の間などにおける、ディジタル・データ通信の効率化の促進を目的として、とりわけ、ディジタル・ネットワークに関係するものである。本発明は、特に、メッセージの転送経路に、様々な程度の転送サービス（transfer service）を持たせられるようなディジタル・ネットワークを目指したものであり、また、本発明の特長は、転送サービスレートが類似した転送経路同士をまとめることによってそこの転送スケジューリング効率を高めるために、ひとつのメカニズムを加えたことである。
【０００２】
【従来の技術及び発明が解決しようとする課題】
ディジタル・ネットワークが開発されてきた結果、ディジタル・コンピュータおよびその他ディジタル式装置同士の間で、データやプログラムなどの情報が、効率よく転送されるようになった。様々な情報転送方式を用いて、色々なタイプのネットワークが開発され、また実施化されてきた。よく知られているイーサネットのように、そこに接続された全ての装置を繋ぐのに、ただ１本しか回線を使用しないネットワークもある。このようにすれば、ネットワークへの装置の接続や技術の面において、ネットワーク配線が単純化されるものの、一度に一つの装置からでしか、メッセージ形式で、回線が情報を配送できないため、結果として概して情報転送の速度が落ちる。この問題を多少緩和するために、或る種のイーサネットの設置では、ネットワーク全体を多数のサブ・ネットワークに分割し、各々に別々の回線を持たせ、その回線間をインターフェースで繋ぐ場合がある。そのような設備では、回線がそこに接続された装置への複数のメッセージを一度に配送することが可能になり、その結果、一度に転送されるメッセージの数が増えるのである。２つ以上のサブ・ネットワークで回線が使用されるであろうと考えられるのは、ある回線に接続された装置から別の回線に接続された装置にメッセージを送信するために、その回線に接続された他の装置がそれを使えなくなっている場合のみである。
【０００３】
また、この問題を緩和するために、切換ノード（swichting nodes）の網の目を経て通信の操作がなされるようなネットワークが開発されてきた。コンピュータ・システムおよびその他の装置は、色々な位置の切換ノードで接続され、情報の送信点としてネットワーク上へ転送すべき情報を発信することもあれば、また、ネットワークを構成する切換ノード上で選択された経路で転送されてくる情報を受け取るための受信点となったりして、情報に対応する。よく知られている“ＡＴＭ”（Asynchronous Transfer Mode「非同期転送モード」）転送方式を用いて情報を転送しているネットワークも含めて、色々なタイプのネットワークにおいて、各送受信点間を繋ぐ色々な情報転送経路には、ネットワークの各経路上へ情報転送が行われる保証レート（guaranteed rate）という、転送サービスの保証によって、何段階かのクラスに分けることが可能である。しかし、ネットワークの切換ノードによって、サービスレートの保証値を利用して経路上に転送された情報を、それぞれその値に対応して確実に効率よく転送できなければならないことに加えて、サービスレートの保証値というものがない経路上への情報転送も今後起こり得るであろうというところに、ひとつの問題が生じるのである。
【０００４】
【課題を解決するための手段】
本発明の特長は、メッセージ転送経路のサービスレートの値が何種類もあってもよいような、新しい改良型のディジタル・ネットワーク、即ち、そこへの転送スケジューリングの効率を高めるために、転送サービスレートが近い転送経路同士をまとめるメカニズムを有するネットワークを供給したことである。
【０００５】
概要を述べると、ある面では本発明は、ディジタル・ネットワークに於いて、セル形式で情報の転送に待ち行列制御システムを用いる。ネットワークでは、色々な経路に対する伝送レートなどを考慮して、多段階のサービスレートを設けている。情報バッファ制御サブシステムは、セル受信部（cell reciever）、セル・バッファ部（cell buffer）、およびグループ制御部（group controller）を有する。セル受信部がセルを受信し、バッファ部が、伝送に先だって、受信したセルをバッファリングする。グループ制御部は、受信部が受信したセルに対してバッファリング部が行なうバッファリングを制御する。そのオペレーション過程で、グループ制御部は、それぞれのサービスレートの程度に応じて、バッファ部における経路ごとにセルを集めるが、特に、ひとつの待ち行列の中で同じ経路に対応するセル同士を集め、さらには、待ち行列の中でのサービスレートが同じ度合になるような経路のセル同士も集める。
【０００６】
本発明の特長は、他の面では、情報の転送に於いて、ディジタル・ネットワーク上でそれぞれ経路に関連したセルの形を用いた、伝送のスケジューラを用いることである。ネットワークは、色々な経路に対する伝送レートなどをもとに考えて、多段階のサービスレートを設けている。経路の待ち行列の中で、同経路に対応するセル同士、および、サービスレートの度合が同じであるような経路に対応する待ち行列同士は、一つのサービスレートの待ち行列の中に集合される。また、伝送のスケジューラは、同一サービスレートの待ち行列の中から、さらに１種類の経路の待ち行列だけを選んでセルを伝送するためのセル・セレクタ部、および、その選択した経路の待ち行列から発信されるセルを伝送するためのセル伝送部（cell transmitter）を有する。
【０００７】
【発明の実施の形態】
図１は、いくつもの装置間でデータを表わす信号を転送しあうための、複数の切換ノード１１（１）〜１１（Ｎ）（１１（ｎ）という文字で一般化して表わすものとする）を有するコンピュータ・ネットワーク１０を、概略的に示したものであり、それらの装置は、図１ではコンピュータ・システム１２（１）〜１２（Ｍ）（１２（ｍ）という文字で一般化して表わすものとする）として表現されている。コンピュータ・システム１２（ｍ）は従来どおり、プログラムの命令に従ってデータを処理し、処理を経たデータを生成する。この処理過程では、コンピュータ・システム１２（ｍS）（下付き添字“Ｓ”は、“source”つまり『送信点』を表わす）が、送信点のコンピュータ・システムとして、未処理データや処理済みデータやプログラムの命令（本文では以後、これらを一括して「情報」と表現する）を、受信先となる別のコンピュータ・システム（１２（ｍD）（下付き添字“Ｄ”は、“destination”つまり『受信先』を表わす）に転送し、そのコンピュータ・システム１２（ｍD）は転送されてきた情報を使って稼働しなくてはならない。各コンピュータ・システム１２（ｍ）は、１３（ｌ）という文字で一般化して表わした通信リンクを使って、切換ノード１１（ｎ）に接続され、効率よくそこへデータを伝送したり、また、そこからデータを受信したりできるようになっている。
【０００８】
切換ノード１１（ｎ）同士は、これもまた、１３（ｌ）という文字で一般化して表わす通信リンクで接続し、ノード同士の間でのデータ転送の効率化を促進する。通信リンク１３（ｌ）は、適当なデータ伝送媒体のうち大抵何に対しても適用できるであろうから、一実施例では、１本以上の光ファイバーのリンクが構成されるように、各通信リンク１３（ｌ）の伝送媒体を決めた。通信リンク１３（ｌ）は、切換ノード１１（ｎ）が、リンクでそれに繋がるコンピュータ・システム１２（ｍ）とや、ノード同士の間で、信号の送受ができるよう、双方向のリンクであることが望ましいので、通信リンク１３（ｌ）を光ファイバーにした実施例では、各通信リンク１３（ｌ）あたり、２本の光ファイバーを使用して、その１本ずつが、切換ノード１１（ｎ）同士の間や、切換ノード１１（ｎ）とコンピュータ・システム１２（ｍ）の間の、単方向の光信号の転送の効率を高めるようにしてもよい。
【０００９】
一実施例では、ネットワーク１０は、よく知られている「ＡＴＭ」（非同期転送モード」）転送方式を使って、データを転送する。この方式の概論が記述されている文献としては、Ｃ．パートリッジ著『ギガビット・ネットワーキング』（リーディングＭＡ：アディソン・ウェズリー出版、１９９４年）の主に第３章か第４章や、Ｄ．マクダイサンほか著『ＡＴＭ理論と応用』（マグロウヒル、１９９５年）があるので、ここでは詳細な記述は行なわない。図２に表わすように、一般にＡＴＭ方式では、コンピュータ・システム１２（ｍ）と切換ノード１１（ｎ）は、データを“セル”という一定の長さを持つ形にして、伝送する。ＡＴＭデータ転送方式では、送信コンピュータ・システム１２（ｍS）から受信コンピュータ・システム１２（ｍD）に伝送されるパケット２０に対して、送信コンピュータシステム１２（ｍS）は、通信リンク上を逐次伝送して、そこからネットワーク１０に転送し始められるよう、データ・パケット２０を、いくつもの“セル”ＣＥＬＬ（１）〜ＣＥＬＬ（Ｉ）（ＣＥＬＬ（ｉ）という文字で一般化して表わすものとする）に分割する。各セルは、図３により詳しく示す通り、ヘッダ部ＨＤＲ（ｉ）、データ部ＤＡＴＡ（ｉ）を有する。ヘッダ部ＨＤＲ（ｉ）は接続経路情報を有するが、２１と２２の番号で表わした部分それぞれに、仮想経路および仮想回路の識別子を有し、それぞれ、送信コンピュータ・システム１２（ｍS）から受信コンピュータ・システム１２（ｍD）への経路ないし接続の上における、ネットワーク１０の切換ノード１１（ｎ）のノード同士の間のセル転送を、制御する。前述のＡＴＭ方式では、送信コンピュータ・システム１２（ｍS）から受信コンピュータ・システム１２（ｍD）に至るまでに使われる経路上にある、全ての切換ノード１２（ｎ）に対しても同じものである必要もなければ、コンピュータ・ネットワーク１０全体を通じて全て異なっている必要もない。個々の仮想経路および仮想回路識別子は、送信コンピュータ・システム１２とそれに繋がる切換ノード１１（ｎ）、および送信コンピュータ・システム１２（ｍS）から受信コンピュータ・システム１２（ｍD）に至る経路上の切換ノードの各ペア、および、送信コンピュータ・システム１２（ｍS）と受信コンピュータ・システム１２（ｍD）に繋がる切換ノード１１（ｎ）に割り当てられるのが典型的である。
【００１０】
ヘッダ部ＨＤＲ（ｉ）も、「雑多なものからなる（miscellaneous）」部分２３を有し、そこには以下に概説するように、他のルーチン制御情報が含まれる。どのセルも、ヘッダ部ＨＤＲ（ｉ）とデータ部ＤＡＴＡ（ｉ）は共に、予め決めた一定の長さとなる。そこで、一実施例では、ヘッダ部ＨＤＲ（ｉ）を５バイト、データ部ＤＡＴＡ（ｉ）を４８バイトにした。メッセージ中の、伝送されるべきデータの量が、各セルのデータ部ＤＡＴＡ（ｉ）のサイズの整数倍でなくても、送信コンピュータ・システム１２（ｍS）が、最後のセルＣＥＬＬ（Ｉ）に対応するデータ部ＤＡＴＡ（ｉ）をパディングして、確実に、データ部ＤＡＴＡ（ｉ）の長さを理想的なものにすると考えられる。
【００１１】
前述の通り、送信コンピュータ・システム１２（ｍS）は、データ・パケット２０から生じた一連のセルＣＥＬＬ（１）〜ＣＥＬＬ（Ｉ）を順次伝送し、そして、ネットワーク１０は、そのセルを受信コンピュータ・システム１２（ｍD）に、伝送された順に配送する。受信コンピュータ・システム１２（ｍD）は、送信コンピュータ・システム１２（ｍS）から、順次伝送されてくるセルを全て受信して、パケット２０を再構築しなくてはならない。前述のＡＴＭ転送方式では、セルは順序の情報を持たない。そのため、受信コンピュータ・システム１２（ｍD）は、受信した時のセルの順番から適正な順序を判断して、パケット２０を再構築する。最後尾のセルＣＥＬＬ（Ｉ）は、図２でＥＯＰと表わしたように、パケットの終点を示すインジケータを雑多フィールド２３に含むことで、それがパケットの最後のセルであることを示す。
【００１２】
さらに話を進める前に、図１に示したネットワーク１０において有効な切換ノード１１（ｎ）の構造を概説するのが有益であろう。図４は、このような切換ノード１１（ｎ）の機能説明図である。図１でも述べたように、切換ノード１１（ｎ）は、多数の入力ポート・モジュール３０（０）〜３０（Ｐ）（３０（ｐ）という文字で一般化して表わすとする）と、多数の出力ポート・モジュール３１（０）〜３１（Ｐ）（３１（ｐ）という文字で一般化して表わすとする）を有し、１本以上のバス３２によって結ばれている。各入力ポート・モジュール３０（ｐ）は、１本以上の通信リンク１３（ｌ）に繋がれているが、それは特に、そこでセルＣＥＬＬ（ｉ）を表わす信号を受信する理由からである。特定の入力ポート・モジュール３０（ｐ）に繋がれた通信リンク１３（ｌ）は、それぞれ順に、ネットワーク１０内の特定の送信コンピュータ・システム１２（ｍS）や切換ノード１１（ｎ）からのセルＣＥＬＬ（ｉ）を受信できるよう、接続される。入力ポート・モジュール３０（ｐ）が、それに継いだ通信リンク１３（ｌ）から、各セルＣＥＬＬ（ｉ）を受信したら、それ（即ち、入力ポート・モジュール３０（ｐ）のこと）は、受信したセルＣＥＬＬ（ｉ）を出力ポート・モジュール３１（ｐ）に伝送する。
【００１３】
各出力ポート・モジュール３１（ｐ）は、１本以上の通信リンク１３（ｌ）に繋がれ、そこに、入力ポート・モジュール３０（ｐ）が受信したＣＥＬＬ（ｉ）を表わす信号を伝送する。先ほどと同様に、特定の出力ポート・モジュール３１（ｐ）に繋がれた通信リンク１３（ｌ）は、それぞれ順に、ネットワーク１０内の特定の他の切換ノード１１（ｎ）や、受信コンピュータ・システム１２（ｍD）にセルＣＥＬＬ（ｉ）を転送できるよう、接続される。入力ポート・モジュール３０（ｐ）の数は、都合よく出力ポート・モジュール３１（ｐ）の数に合わせられる。そうすれば、各出力ポート・モジュール３１（ｐ）も都合よく、入力ポート・モジュール３０（ｐ）がセルＣＥＬＬ（ｉ）を受信した切換ノード１１（ｎ）かコンピュータ・システム１２（ｍ）に、セルＣＥＬＬ（ｉ）を伝送できるのである。
【００１４】
前述の通り、各入力ポート・モジュール３０（ｐ）は、それに繋がる通信リンク１３（ｌ）から、セルを受信し、出力ポート・モジュール３１（ｐ）に向けて、バス３２上に伝送する。出力ポート・モジュール３１（ｐ）は、必要なら、それに繋がるそれぞれの通信リンク１３（ｌ）上へのセルＣＥＬＬ（ｉ）の伝送やスケジューリングをする前に、２１、２２の仮想経路および仮想回路識別子（図３）を変更するといったことまで含めた、多くのオペレーションをこなすのである。全ての出力ポート・モジュール３１（ｐ）は、全般的に類似しており、図５は、図４に示した切換ノードにおいて有効な出力ポート・モジュール３１（ｐ）の機能説明図を示したものである。
【００１５】
図５参照の通り、出力ポート・モジュール３１（ｐ）は、入力セクション３３、記憶セクション３４、および、出力セクション３５を有し、これらは全て、制御セクション３６により制御される。一般的には、入力セクション３３がセルＣＥＬＬ（ｉ）をバス３２から受信して、制御セクション３６の制御の下それを記憶セクション３４にローディングする。同時に、出力セクション３５が、前に記憶させたセルＣＥＬＬ（ｉ）を、記憶セクション３４から取り出して、各通信リンク１３（ｌ）へ伝送する。詳細は、図６〜１０に関連して後述するが、制御セクション３６は入力セクション３３を制御して、セルＣＥＬＬ（ｉ）を、出力セクション３５による伝送のスケジューリング効率が高くなるようにグループ分けした上で、記憶セクション３４に記憶させる。そうして、出力セクション３５が様々なグループから行う伝送のスケジューリングも制御する。
【００１６】
引き続き図５を参照に、さらに特長を述べると、入力セクション３３は、入力用先入れ先出しバッファ３７（ＦＩＦＯバッファ）と、書き込み状態マシン３８を含む。入力ＦＩＦＯバッファ３７は、セルＣＥＬＬ（ｉ）をバス３２から受信し、バッファリングする。書き込み状態マシン３８は、セルＣＥＬＬ（ｉ）をＦＩＦＯバッファ３７から取り出し、取り出したセルＣＥＬＬ（ｉ）のひとつひとつが、出力ポート・モジュール３１（ｐ）によって操作される接続に対応するかどうかを判断し、もし、それが対応するものであって、なおかつ、他の諸条件もそろえば、制御セクション３６の制御の下、その取り出したセルＣＥＬＬ（ｉ）を記憶セクション３４の対応する接続の待ち行列に記憶させる。さらに、後述するように、書き込み状態マシン３８は、制御セクション３６の制御を受けて、セルＣＥＬＬ（ｉ）に対応する接続に関係するの他の情報があれば、それを更新して書き換えていく。
【００１７】
出力セクション３５は、制御セクション３６の制御を受けて、セルＣＥＬＬ（ｉ）を記憶セクションから取り出す。制御セクション３６は、そのセルＣＥＬＬ（ｉ）が伝送されるのに適当な接続の選択を制御する。出力セクション３５は、読み込み状態マシン４０と、出力ＦＩＦＯ４１を含む。読み込み状態マシン４０は、制御セクション３６によって選択された接続状態に合う待ち行列からのセルＣＥＬＬ（ｉ）の取り出し作業を制御し、そして、取り出されたセルＣＥＬＬ（ｉ）を、バッファリングのために一旦出力ＦＩＦＯ４１に転送してから、そこに繋がる通信リンク１３（ｌ）上に伝送する。読み込み状態マシン４０を用いれば、セルＣＥＬＬ（ｉ）を記憶セクション３４から取り出してから後、必要であれば、セルが伝送される際に新しい仮想経路および仮想回路識別子を、セルのヘッダに書き込んで更新することもできる。
【００１８】
詳細は後述するが、さまざまな接続に対応する待ち行列は伝送のスケジューリングの目的にかなうようにグループに分類されまとめられる。そして、後述のとおり、そのグループの編成と維持のために、制御セクション３６が多くの動作を行う。背景に触れると、ＡＴＭ転送方式では、何種類ものサービスのクラスが規定され、それらのサービスのクラス中には、サービスレートの保証最低値があるものもある。ある決まった値のサービスレートの保証最低値を持つ接続形態においては、それらの接続につながるセルは、ネットワーク１０上を一定の速度で転送することが保証される。このサービスレートは、接続状態の種類によって異なるものの、同一の切換ノード１１（ｎ）からサーブされる接続状態同士に関してなら、そのサービス・レートの保証最低値は同じか近い値である。それぞれの接続に、最低速度のサービス・レートばかりが割り当てられた場合には、接続全体の速度も最低になるであろう。しかし大抵の場合、転送可能な帯域幅が、サービスレートが保証最低値ばかりの接続の場合に予想される値よりも上であれば、接続は保証された最低速よりは速く転送されるであろう。他の接続状態でも、サービスレートが保証最低値の接続状態ばかりの場合に予想される速度の値より、ネットワーク１０やとくに切替えノード１１が転送可能な帯域幅が上回れば、サービスレートは一定せず、かわりに利用可能なサービスレートでそれらの接続に対してセルＣＥＬＬ（ｉ）は転送されることになるであろう。
【００１９】
様々な接続状態に対して、有効にセルの転送のスケジューリングを調整するために、記憶セクション３４の中にある待ち行列も、様々な接続状態に応じて、さらにグループに分類し、そのグループはそれぞれ、出力ポート・モジュール３１（ｐ）が操る接続状態に対応するサービス・レートのどれかひとつに直結している。制御セクション３６もまた、それぞれの接続状態をつくりだす際に、グループ分類をしたり再編成をするだけでなく、スケジュール・ユニット４３を用い、セルＣＥＬＬ（ｉ）を様々なグループから伝送するためのスケジューリングを行うことで、各グループに直結する接続状態に対応するサービス・レートの保証最低値を確実に維持しながら、これらのグループを保持する役目も果たしている。制御セクション３６は、図５に機能説明図として示したとおり、接続グルーピング・ユニット４２とスケジュール・ユニット４３を含む。また、接続グルーピング・ユニット４２は、グループ制御モジュール４５、グループ・アロケーション・モジュール４６、および、グループ・ポリシー・モジュール４７を含むが、これらの働きは後述する。
【００２０】
話を進める前に、ここで、制御セクション３６や記憶部が様々な接続のグループ分け作業を制御する際や、各セルＣＥＬＬ（ｉ）のスケジューリング・取り出しの作業の際に、図５に示す諸エレメントが用いている、様々なデータ構造のことを述べるのが有益であろう。図６は、そのようなデータ構造を多数、詳細に示したものである。図６参照のとおり、制御セクション３６は、仮想経路識別子探索テーブル５０、仮想回路識別子探索テーブル５１、接続テーブル５２、セル・ポインタ・テーブル５３、後続グループテーブル５４、タイム・スタンプ・テーブル５５、グループ・テーブル５６、タイム・インターバル・テーブル５７を含む、多くの表を要する。接続テーブル５２は、各接続の状態、即ち、特定の出力ポート・モジュール３１（ｐ）を通じて切換ノードによって維持されている各接続の状態の情報を含む。接続テーブル５２は、５２（ｃ）という文字で一般化して表わされている多数のエントリを含み、それは、仮想経路識別子探索テーブル５０、および、仮想回路識別子探索テーブル５１によって、それぞれの接続の状態に対応して識別される。特に、仮想経路識別子探索テーブル５０は、５０（ｐ）という文字で一般化して表わされている多数のエントリを含み、そのそれぞれがセルＣＥＬＬ（ｉ）の仮想経路識別子フィールド２１のエンコードに関係している（図３）。すなわち、出力ポート・モジュール３１（ｐ）の受信するセルの仮想経路識別子フィールド２１の中身は、オフセットの値になり、それで仮想経路識別子探索テーブル５０の１つのエントリ５０（ｐ）を識別する。
【００２１】
仮想経路識別子テーブル５０の各エントリ５０（ｐ）は、終端フラッグ６０と仮想回路識別子探索テーブルのオフセット・フィールド６１を含む。また、仮想回路識別子探索テーブルのオフセット・フィールド６１には、仮想回路識別子探索テーブル５１のエントリ５１（ｃ）を指示する数値がある。仮想回路識別子探索テーブル５１は、多数のエントリ５１（ｃ）を含み、そのそれぞれが、有効性フラッグ６３と接続テーブル・ポインタ・フィールド６３を含む。有効性フラッグ６３は、接続テーブル・ポインタ・フィールド６３が、有効な接続テーブル・ポインタを含むかどうかを示す。有効性フラッグ６３が、接続テーブル・ポインタ・フィールド６３が有効な接続テーブル・ポインタを含むことを示す場合には、今度は、接続テーブル・ポインタが、その接続状態に対応する接続テーブルのエントリ５２（ｃ）を指し示す。
【００２２】
既に示したとおり、仮想経路識別子探索テーブル５０のエントリ５０（ｐ）も同じく終端フラッグ６０を含む。終端フラッグ６０は、その接続状態に対応する特定の接続識別子（すなわち、セルＣＥＬＬ（ｉ）のフィールド２１と２２の仮想経路識別子や仮想回路識別子）が、出力ポート・モジュール３１（ｐ）を含む特定の切換ノード１１（ｎ）で接続を、終了するかどうかを示す。もし、そうであれば、その接続に対応して受信されたセルＣＥＬＬ（ｉ）の接続識別子は、セルＣＥＬＬ（ｉ）が伝送される前に、テーブル中にある、仮想経路および仮想回路識別子の最新情報を用いて、それぞれ新しい値に更新されることになる（図示はしていない）。
【００２３】
接続テーブル５２の各エントリ５２（ｃ）は、入力セクション３３が、セルＣＥＬＬ（ｉ）を、記憶セクション３４の中に記憶させたり、記憶セクション３４の中から取り出したりする作業を、制御するための情報を含む。特に、各エントリ５２（ｃ）は、セル・カウンタ・フィールド７０、セル読み込みポインタ７２、セル書き込みポインタ７３、ポート識別フィールド７４、サービス・クラス・フィールド７５、および雑多フィールド７７というように、多くのフィールドを含む。セル・カウンタ・フィールド７０は、エントリ５２（ｃ）に結びつけられた接続に対応して、記憶セクション３４の中に蓄えられたセルＣＥＬＬ（ｉ）の数を示す値を含む。書き込み状態マシン３８が、ある接続状態に結びつくセルＣＥＬＬ（ｉ）を、記憶セクション３４の中に記憶させると、セル・カウンタ・フィールド７０の値は増加し、また、読み込み状態マシンが、記憶セクション３４の中から、その接続に結びつくセルＣＥＬＬ（ｉ）をひとつ伝送用に取り出せば、セル・カウンタ・フィールドの値は減少する。一実施例で、もし、ある接続に対応して受信されたセルＣＥＬＬ（ｉ）が、全て伝送されてしまったことをセル・カウンタ・フィールド７０が示せば、スケジューラ43にその接続状態をスケジューリングさせるために結びつけていたグループから、その接続状態は削除されることになるが、これについては後述する。もし、ひとつのセルＣＥＬＬ（ｉ）が、その接続状態に対応して、後から受信されてきたところ、書き込み状態マシン３８が、前述のように記憶セクション３４の中にそのセルを記憶させ、セル・カウンタ・フィールド７０の数値を増加したあとだったとしても、その接続状態は後から再び、入るべきグループに結びつけられることになる。
【００２４】
セル読み込みポインタ７２は、記憶セクション３４の中から、接続状態に対応して次に伝送される予定のセルを識別する。一方、セル書き込みポインタ７３は、接続状態に対応して記憶セクション３４に記憶された最後のセルを識別する。書き込み状態マシン３８がある接続状態に関係したセルＣＥＬＬ（ｉ）を、記憶セクション３４の中に記憶させようとする時には、セル書き込みポインタ７３を参照する事で、記憶セクション３４に入った最後のセルを識別し、セル・ポインタ・テーブル５３のポインタを用いて、その新着のセルＣＥＬＬ（ｉ）を、その接続に関する他のセルに、後述のような、待ち行列を形づくるようにリンクさせることができる。読み込み状態マシン４０が、ある接続状態に対するセルＣＥＬＬ（ｉ）を記憶セクション３４の中から取り出そうとする時には、セル読み込みポインタ７２を利用して、取り出すべきセルＣＥＬＬ（ｉ）を識別することが出来る。書き込み状態マシン３８は、記憶されるべきセルＣＥＬＬ（ｉ）のフィールド２１にある仮想経路識別子を用いることができるほか、仮想経路識別子探索テーブル５０と仮想回路識別子探索テーブル５１を用いて、接続状態に対応する、接続情報エントリ５２（ｃ）を識別して、そこからセル書き込みポインタ７３を得ることが出来る。同様に、読み込み状態マシン４０も、制御セクション３６によって供給される接続識別子、とりわけ、後述のとおり、接続グルーピング・ユニット４２とスケジュール・ユニット４３を用いることができると同時に、仮想経路識別子探索テーブル５０と仮想回路識別子探索テーブル５１を用いて、接続状態に対応する、接続情報エントリ５２（ｃ）を識別して、そこからセル読み込みポインタ７２を得ることが出来る。
【００２５】
ポート識別子フィールド７４は通信リンク１３（ｌ）の中から、接続に対応するセルが送出されていく出力ポート・モジュール３１（ｐ）に繋がれている、特定の通信リンクを識別する。しかるに、出力ポート・モジュール３１（ｐ）によってセルＣＥＬＬ（ｉ）が伝送されていく先の通信リンク１３（ｌ）が、ただ１本のみであるような、ユニキャストによる接続であった場合、ポート識別子フィールド７４は、そのただ１本の通信リンク１３（ｌ）を識別するであろうが、もし、出力ポート・モジュール３１（ｐ）によってセルが複数の通信リンク１３（ｌ）によって伝送されるような、マルチキャストによる接続であった場合、ポート識別子フィールド７４は、出力ポート・モジュールに繋がれた通信リンク１３（ｌ）のうち、そこにセルが伝送されるはずであるところのものをそれぞれ識別する。サービス・クラス・フィールド７５は、その接続状態による速度が、保証サービス・レートか、最低サービス・レートか、転送可能レートかを示すなど、接続状態に応じてＡＴＭのサービスの種類を識別する。雑多フィールド７７は、接続状態に有益であろうと思われる、その他の情報を含む。
【００２６】
セル・ポインタ・テーブル５３は、記憶セクション３４の中に記憶されている様々なセルを関連づけ、１つの接続のためのセルを結び付けて、リンクされたリストを作るために使われる。一般に、記憶セクション３４は、記憶のためのひと続きのロケーションを含み、それは、切れ目のないアドレスによって識別されるものであるが、そのそれぞれのロケーションにはひとつのセルを記憶することができる。セル・ポインタ・テーブル５３は、後述されるように、マルチキャストを行う上で役にたつ、状況情報をも有している。セル・ポインタ・テーブル５３は、５３（ｔ）という文字で一般化して識別される、一続きのエントリを有していて、そのそれぞれが、記憶セクション３４の中のセルのストレージの所在と関連性がある。たとえば、５３（０）という文字で参照される、セル・ポインタ・テーブル５３の第一番目のエントリ（図６には示されていない）は、（０）というアドレスのストレージ・ロケーションに対応し、第二番目のエントリは、５３（１）という文字で示されるが、これも（１）というアドレスのストレージ・ロケーションに対応しているといった具合で続くのである。
【００２７】
セル・ポインタ・テーブル５３の各エントリ５３（ｔ）は、いくつものフィールドを持ち、後続セル・ポインタ・フィールド８０やセル・ポート・マスク・フィールド８１から成る。セル・ポインタ・フィールド８０にあるセル・ポインタは、接続テーブル５２の接続情報エントリ５２（ｃ）のセル読み込みポインタ７２とセル書き込みポインタ７３と共に、接続情報エントリ５２（ｃ）に関する接続状態に対してバッファリングされたセルＣＥＬＬ（ｉ）の待ち行列を規定する役目を果たす。すなわち、接続情報エントリ５２（ｃ）のセル読み込みポインタ７２が指し示すのは、接続を通して伝送される最初のセルＣＥＬＬ（ｉ）であり、そのセルＣＥＬＬ（ｉ）に関するセル・ポインタ・テーブル５３のエントリ５３（ｔ）のフィールド８０にある、後続セル・ポインタが、次に、接続を通して伝送されるべき２番目のセルを指し示す。同様に接続を通して伝送される２番目のセルＣＥＬＬ（ｉ）に対応する、セル・ポインタ・テーブルのエントリ５３（ｔ）のフィールド８０にある後続セルポインターは、その接続を通して伝送されるべき３番目のセルを指し示すといった具合に続くのである。だから、セル読み込みポインタ７２と、セル・ポインタ・テーブル５３フィールドの中に繋がれている、フィールド８０の後続セル・ポインタ列が、記憶セクション３４の中でバッファリングされたセルの列を、まとめて規定するのである。また、接続情報エントリ５２（ｃ）のセル書き込みポインタ７３は、それに対し、接続に応じてバッファリングされている最後のセルを示す。伝送待ちのセルＣＥＬＬ（ｉ）がない状態の、ストレージの所在は、空セルの待ち行列（free queue）に接続される。書き込み状態マシン３８は、セルＣＥＬＬ（ｉ）を記憶セクション３４の中に、記憶させるときに、空セルの待ち行列の中から、ストレージの所在を得る。読み込み状態マシン４０は、セルＣＥＬＬ（ｉ）を、伝送するためにストレージから取り出すとき、ストレージの所在をその空セルの待ち行列に繋ぐが、そのような場合、そのストレージ・ロケーションは、後から書き込み状態マシン３８が別のセルのために使うことができる。
【００２８】
前述のとおり、セル・ポインタ・テーブル５３のエントリ５３（ｔ）も、セル・ポート・マスク８１を含む。そのセル・ポート・マスクは、多くのポート・ビットを含み、それらは各々、出力ボート・モジュール３１（ｐ）に接続された通信リンク１３（ｌ）のどれかと結び付いているのだが、セル・ポート・マスクが、エントリ５３（ｔ）に対応するセルＣＥＬＬ（ｉ）が伝送されていく予定の１つまたは複数の通信リンク１３（ｌ）を識別する。もし、そのセルＣＥＬＬ（ｉ）がユニキャストによる接続状態に関連するものである場合、セル・ポート・マスク８１の１ビットだけがセットされ、そのセルＣＥＬＬ（ｉ）が伝送される予定の通信リンク１３（ｌ）を識別できるようになっている。他方、セルＣＥＬＬ（ｉ）が通信リンクがマルチキャストによる接続状態に関連するものである場合には、セル・ポート・マスク８１の複数ビットがセットされ、そのそれぞれが、そのセルＣＥＬＬ（ｉ）が接続状態に対応して伝送される予定の１本の通信リンク１３（ｌ）に対応している。ＣＥＬＬ（ｉ）がそれぞれに通信リンク１３（ｌ）に伝送されると、そのセル・ポート・マスク８１の対応するビットはリセットされる。
【００２９】
グループ・テーブル５６、タイム・インターバル・テーブル５７、および後続グループテーブル５４は、接続テーブル５２の接続情報エントリ５２（ｃ）によって規定される接続状態を結び付けたり、つないだりして、伝送スケジューリングの目的にかなうグループに分類するのに用いられる。グルーピングのメカニズムは、詳細には、図７と８に関連して後述する。しかし、予備的に述べると、グループ・テーブル５６は、５６（ｇ）という文字で一般化して識別される、多数のエントリを含み、そのそれぞれがグループのどれかに結びつく。同様に、タイム・インターバル・テーブル５７も、同程度に多数のエントリ５７（ｇ）を含み、そのそれぞれがグループのどれかに結びつく。他方、後続グループテーブル５４は、５４（ｎ）という文字で一般化して識別される、多数のエントリを含み、そのそれぞれが接続テーブル５２の接続情報エントリ５２（ｃ）と結び付く。
【００３０】
各グループ・テーブル・エントリ５６（ｇ）は、多数のフィールドを含み、有効性フラッグ８２、グループ・ヘッド・ポインタ８３、および、グループ  ・テイル・ポインタ８４をから成る。有効性フラッグ８３は、エントリ５６（ｇ）の内容が有効か有効でないかを示す。もしも、グループ・テーブル・エントリ５６（ｇ）の有効性フラッグ８３がエントリ５６（ｇ）の内容が有効でないと示したと場合は、エントリ５６（ｇ）に結び付くグループはひとつもない。他方、もしも、グループ・テーブル・エントリ５６（ｇ）の有効性フラッグ８３がエントリ５６（ｇ）の内容は有効であると示せば、グループ・テーブル・エントリ５６（ｇ）に結び付くグループの一部を形成する接続テーブル５２の中から、グループ・ヘッド・ポインタ・フィールド８３が、エントリ５２（ｃ）のひとつを、一番目の、あるいは、「先頭の(ヘッド)」接続状態のために指定する。また、接続情報エントリ５２（ｃ）と結び付く、後続グループテーブル５４の中にある、エントリ５４（ｎ）（接続テーブル５２の接続情報エントリ５２（ｃ）を指定するのは、グループ・ヘッド・ポインタ８３であるが）は、後続グループポインタ８６から成るが、これは同じグループの２番目の接続状態に結び付く接続情報エントリ５２（ｃ）を識別するものである。同様に、２番目の接続情報エントリ５２（ｃ）と結び付く後続グループテーブル５４中のエントリ５４（ｎ）も、同グループの３番目の接続状態に結び付く接続情報エントリ５２（ｃ）を識別する、後続グループポインタ８６から成り、このようにして、グループ内で次々と接続状態が識別されていくのである。そして、グループ・ヘッド・ポインタ８３と、エントリ５４（ｎ）の中に集められた後続グループポインタ８６の列が、グループ・テーブルのエントリ５６（ｇ）に結び付くグループに入る接続状態のリストを規定する。また、エントリ５６（ｇ）の中のグループ・テイル・ポインタ８４は、そのグループに関する最後の接続状態、ないし、「末尾（テイル）の」接続状態に対応して、接続テーブル５２の接続情報エントリ５２（ｃ）を指定する。後続グループポインタ８３が、そのグループの中の最後の接続状態、ないし、「末尾の」接続状態に結びつくと、例えば、無意味なポインタになってしまうか、グループ・テーブル５６のエントリ５６（ｇ）を指すポインタだけが残るかであるような場合は、各グループに対応する接続情報エントリ５２（ｃ）は、全てひとつのリストの中に収まってしまうであろうが、或いはそうではなく、末尾の接続状態に結びつく後続グループポインタ８３が、先頭の接続状態に結びつく接続情報エントリ５２（ｃ）を指定するような場合なら、接続情報エントリ５２（ｃ）の列が対応するグループは、循環的につながり続くであろう。
【００３１】
グループ・テーブル５６の規定する接続状態のグループは、伝送のスケジューリングの目的にかなうように、グループ分けされている。タイム・インターバル・テーブル５７は、グループ内の色々な接続状態に対応して伝送のスケジューリング情報を更新するのに使われる情報を含むし、また、タイム・スタンプ・テーブル５５は、接続テーブル５２の接続情報エントリ５２（ｃ）に関する様々な接続状態に対応した、スケジューリングの情報を含む。タイム・スタンプ・テーブル５５は、たくさんのエントリ５５（ｃ）を含み、その各エントリ５５（ｃ）が、接続テーブル５２の接続情報エントリ５２（ｃ）に順序良く対応していて連関している。タイム・スタンプ・テーブル５５の各エントリ５５（ｃ）は、タイム・スタンプ８７から成るが、これは、接続情報エントリ５２（ｃ）に対応してセルＣＥＬＬ（ｉ）の伝送のスケジューリングを行うときに用いる。また、タイム・インターバル・テーブル５７は、グループ・タイム・インターバル値８５を含み、これは、グループ・テーブル５６の規定するグループのどれかに関する様々な接続状態に応じてセルＣＥＬＬ（ｉ）の伝送をする際の時間の間隔を識別する。一実施例では、マルチキャストを用いてメッセージを伝送する場合、各通信リンク１３（ｌ）が関わる伝送時間間隔は一定ではなく、タイム・インターバル・テーブル５７の中の、色々なグループ・タイム・インターバル値８５に関係する。タイム・インターバル・テーブル５７は、５７（ｇ）という文字で一般化して識別できる複数のエントリを含み、その各々が、グループテーブル５６のエントリ５６（ｇ）に順序良く対応していて関連している。グループ・テーブル５６の中の、エントリ５６（ｇ）で識別されるグループに関連する接続が利用されたとき、すなわち、セルＣＥＬＬ（ｉ）がその接続から伝送されるとき、その接続と関連するタイム・スタンプ・テーブルのエントリ５５（ｎ）の中の、タイム・スタンプ８７は、グループ・テーブル５６中の、そのグループのエントリ５６（ｇ）の順番に対応する“ｇ”番目のタイム・インターバル・テーブルのエントリ５７（ｇ）で示されるような、グループ・タイム・インターバルに対応した値で増大すると考えられる。
【００３２】
このような背景とともに、接続グループ・ユニット４２によって与えられるグルーピング・メカニズムを図７〜９に関連して、詳細に述べる。図７と８は、関連して転送速度が保証されているか、最低速度が保証されているような場合の接続状態に関して使われるグルーピング・メカニズムの詳細を示したものであり、図９は、保証最低速度のサービス・レートと考えられる速度を上回るような、転送可能な速度での接続状態に対する詳細を示したものである。図７と８に主に示されるように、出力ポート・モジュール３１（p）によって、一般にひとつ以上のグループ９１（ｌ）〜９１（Ｇ）（９１（ｇ）という文字で一般化して表わすものとする）が与えられ、それらを規定するのは、グループ・テーブルの各エントリ５６（ｇ）の中の情報であるとする。上述のように、もし、グループ・テーブル５６のエントリ５６（ｇ）の有効性フラッグ８２がセットされていれば、グループ・テーブル５６のエントリ５６（ｇ）はグループ・ヘッダ９０（ｎ）を含み、エントリ５６（ｇ）のグループ・ヘッド・ポインタ８３が指すのが、そのグループの一番先頭の接続状態に対応する接続テーブル５２のエントリ５２（ｃ）で、グループ・テイル・ポインター８４が指すのが、そのグループでの一番最後の接続状態に対応する接続テーブルのエントリ５２（ｃ）であるような状況になる。もし、グループ・テーブル５６のエントリ５６（ｇ）の有効性フラッグが、クリアされていなければ、エントリ５６（ｇ）は、関連するグループ９１（ｎ）を持つことはなく、そのような場合、以下に述べる５６（ｇ）は、新しいグループを編成するのに用いることができるようになる。
【００３３】
グループ９１（ｇ）の一般の構造的な仕組みは、大体どれも似たようなものである。図８は、そのようなグループの一例を挙げ、構造的な仕組み概略的に示したものであり、そのグループを９１（ｇ）という文字で表わして示すものとする。図８参照の通り、グループ９１（g）は、おおむね類似したサービス・レートをもつ数多くの待ち行列９４（q）が集まってできたリスト９４で成っている。ひとつの待ち行列、つまり待ち行列９４（０）は、グループ（ｇ）の１番目の待ち行列、いわば「先頭の」待ち行列となり、グループ・ヘッド・ポインタ８３から指定を受ける。もうひとつの待ち行列、つまり待ち行列９４（Ｑ）は、グループ（ｇ）の最後の行列、いわば「末尾の」待ち行列となり、グループ・テイル・ポインタ８４から指定を受ける。リスト６１中で、待ち行列９４（q）に対応する接続状態は色々であるが、グループ９１（ｇ）に関与する全ての接続状態に対して、セルＣＥＬＬ（ｉ）はサービス・レートの保証速度を維持しながら伝送されなければならないという条件を満たすような状況を設定する。すなわち、スケジュール・ユニット43が、セルＣＥＬＬ（ｉ）を伝送するグループ９１（ｇ）を選択したとすると、そのセルはグループ９１（ｇ）の中の先頭の待ち行列９４（０）によって、送り出される。そのあと、グループ制御モジュール４５によって、グループ９１（ｇ）のリスト９４が再編成されて、次の待ち行列９４（１）が、セルを伝送したばかりの待ち行列９４（０）のあとに続いて、グループ９１（ｇ）の新しい先頭待ち行列になり、そして、セルを伝送したばかりの待ち行列が、グループ９１（ｇ）の新しい末尾行列になるのである。次にグループ９１（ｇ）から、セルＣＥＬＬ（ｉ）が伝送されるときには、そのセルＣＥＬＬ（ｉ）は、グループ９１（ｇ）の新しい先頭待ち行列から選択されることになる。であるから、リスト９４内の待ち行列９４（ｑ）は、セルの伝送順で保持されているのであり、セルＣＥＬＬ（ｉ）は、グループ９１（ｇ）それぞれの先頭の待ち行列９４（０）から伝送されるべく選ばれるのを待つ状態に常にあるのである。また、スケジュール・ユニット４３は、後述するようなやり方で、多種多様のグループ９１（ｇ）の中から選んで、多種多様にわたるグループ９１（ｇ）の中から待ち行列９４（ｑ）に関連した接続状態の全てについて、保証した速度のサービス・レートを守る。
【００３４】
ひとつのグループ９１（ｇ）内に含まれる各待ち行列９４（ｑ）を規定するのは、添付された待ち行列ヘッダ９５であり、これは、図６に関連して前述したような、様々なデータ構造に由来するフィールドから成っており、それは、（ｉ）リスト９４内に含まれる待ち行列９４（ｑ）同士をリンクさせること、（ii）待ち行列９４（ｑ）に関連した接続状態に応じて、セルＣＥＬＬ（ｉ）列を待ち行列ヘッダ９５とリンクさせること、及び、（iii）待ち行列９４（ｑ）に関連した接続状態に応じて、セル伝送の状況の情報を知っておくこと、である。待ち行列９４（ｑ）に関する待ち行列ヘッダ９５は、待ち行列９４（ｑ）に関連した接続状態に応じた後続グループテーブル５４の接続情報エントリ５２（ｃ）から出てきた、後続グループポインタのフィールド５６（図６）を含み、それはグループ５１（０）内の次の待ち行列９４（ｑ+１）を指定する後続グループポインタから成る。既に示したとおり、リスト９４の末尾の待ち行列９４（Ｑ）のフィールド８６の後続グループポインタは、それがリスト９４の最後尾の待ち行列であるとすれば、無意味な内容を持つことになるかもしれないし、もしくは、そのグループのグループ・テイル・ポインター８４を指すかもしれない。あるいは、逆に、リスト９４の先頭の待ち行列９４（０）をそれが指して、リスト９４が循環リストのようになるかもしれない。リスト９４内のばらばらな待ち行列９４（ｑ）が、互いに離れないでいるのは、リスト９４の待ち行列９４（ｑ）の各フィールド８６の、後続グループポインタによるものであるということは、理解できるであろう。
【００３５】
待ち行列９４（ｑ）に対応する待ち行列ヘッダ９５は、また、待ち行列９４（ｑ）に関連する接続状態に応じて接続テーブル５２の接続情報エントリ５２（ｃ）から出てきた、セル読み込みポインタ７２をも含む。上述のように、それぞれの接続状態に関連するセルＣＥＬＬ（ｉ）は、切換ノード１１（ｎ）が、それらセルが受信される順序で伝送されるように、待ち行列に集められる。待ち行列９４（ｑ）は、接続に関連するそれらのセルＣＥＬＬ（ｉ）を一続きのセル列エントリ９４（ｑ）（ｏ）〜９４（ｑ）（Ｅ）に、保有する（９４（ｑ）（ｅ）という文字で表わして、一般化して識別するものとする）。各列エントリは、セル・ポインタ・テーブル５３（図６）から出た後続セルポインタ８０とセル・フィールド９６を含む。各セル列エントリ９４（ｑ）（ｅ）に対応して、セル・フィールド９６は、実際にセルＣＥＬｌ（ｉ）を含む記憶セクション３４（図５）の中のストレージ・ロケーションにあたり、そして、後続セル・ポインタ８０は、後続のセル列エントリ９４（ｑ）（ｅ＋１）を待ち行列９４（ｑ）の中から指定する。
【００３６】
最後のセル列エントリ９４（ｑ）（ｅ）には、後続セル・ポインタ８０の持つ値は、無意味であるか、待ち行列９４（ｑ）の最後の列エントリ６０（ｑ）（Ｅ）であることを示すという意味であるかもしれない。理解できるであろうことは、待ち行列９４（ｑ）に関連する接続状態に対応して、出力ポート・モジュール３１（ｐ）によってセルＣＥＬＬ（ｉ）が、送受されるレートによって、待ち行列９４（ｑ）の中のセル列エントリ９４（ｑ）（ｅ）の数にばらつきが出るであろうことである。それに、様々な待ち行列９４（ｑ）が、様々の数のセル列エントリを持つことになるだろう。また、待ち行列ヘッダ９５の中のセル読み込みポインタ７２は、待ち行列の中の最初のセル列エントリ９４（ｑ）（０）を指定する。理解できるであろうことは、ある一定の接続状態とだけ関連する待ち行列９４（ｑ）内の列エントリ９４（ｑ）（ｅ）は、各セルＣＥＬＬ（ｉ）が、順序正しく、伝送されるので、待ち行列ヘッダ９５のセル読み込みポインタ７２は、常に、セル列エントリ９４（ｑ）（０）を指定できる上に、後続のセルもその同じ接続状態で伝送されることである。待ち行列ヘッダ９５もまた、セル書き込みポインタのフィールド７３を含み、それは、最後のセル列エントリ９４（ｑ）（Ｅ）を待ち行列９４（ｑ）の中から識別でき、１個のセルＣＥＬＬ（ｉ）が待ち行列９４（ｑ）との接続状態によって受信されてしまったとき、セル列エントリ（ｑ）（ｅ）を加えるのに用いる。
【００３７】
前述のとおり、待ち行列ヘッダ９５は、待ち行列９４（ｑ）に関連する接続状態による、セル伝送状況の情報から成る。特に、待ち行列ヘッダ９５はタイム・スタンプ・フィールド８７を含むが、前述の通り、それは、スケジュール・ユニットによって、待ち行列９４（ｑ）からのセルの伝送作業を制御するのに用いる。タイム・スタンプ・フィールド８７は、タイム・スタンプから成るが、これは、グループ９１（ｇ）に関するグループ・タイム・インターバル・フィールド８５の内容とともに、最初のセル列エントリ９４（ｑ）（０）のどのセルＣＥＬＬ（ｉ）が伝送されれば、待ち行列９０（ｑ）との接続状態に対応しつつ保証最低限度のサービス・レートを守って伝送できるかという、タイム・ウインドウの範囲を規定するものである。即ち、保証速度のサービス・レートを守るために、スケジュール・ユニット４３は、フィールド８７のタイム・スタンプの数値から、割りだした時間間隔によって、待ち行列９４（ｑ）が伝送すべくセルＣＥＬＬ（ｉ）を供給する作業をスケジューリングする。しかし、エントリ９４（ｑ）（ｅ）のセルＣＥＬＬ（ｉ）をきわだって高速で伝送するために、スケジュール・ユニット４３は、タイム・インターバル・テーブル５７のエントリ５７（ｇ）内のグループ・タイム・インターバル８５を差し引いたタイム・スタンプ・フィールドの数値に対応した伝送好適時間に先行して、伝送するセルＣＥＬＬ（ｉ）を供給するように、待ち行列９４（ｑ）をスケジューリングすることはしないであろう。それに、次のセルＣＥＬＬ（ｉ）の伝送をするために、グループ９１（ｇ）がスケジューリングされるための新たな時間を規定するには、セルＣＥＬＬ（ｉ）がリスト９４の先頭の待ち行列９４（０）から伝送されたあと、そのグループに関連するタイム・インターバル・テーブル５７のエントリ５７（ｇ）のタイム・インターバル８７の値に対応して、タイム・エントリ５７（ｇ）のスタンプ８７を、増やさなくてはならない。グループ５１（ｇ）に対応するリスト９４内の待ち行列９４（ｑ）は、接続状態がスケジュール・ユニット４３によってスケジューリングされるような条件で編成される。だから、グループ９１（ｇ）で待ち行列が９４（０）から９４（Ｑ）まで続いていくのに応じて、各ヘッダ９５のタイム・スタンプ８７も増加していくのが望ましいと考えられる。そうすれば、先頭と末尾、９４（０）から９４（Ｑ）のタイム・スタンプ８７の開きが、グループ・タイム・インターバル８５と同等かそれ以下になるだろう。
【００３８】
各種接続の待ち行列９４（ｑ）を、上記した如く、グループ９１（ｇ）にグループ化することによって、伝送のサービスレートを制限しなければならない各種接続の回路と関連しているセル（ｉ）の伝送を制限するのに効果的な配置が与えられる。サービスレートとは関係の無い接続や、伝送の最大レートが制限されていない接続を含む、その他の接続については、無制限グループ（unregulated group）９２が設けられている。該無制限グループ（９２）は、通信リンク１３（ｌ）に渡る過剰な情報伝送帯域幅の使用が出来るメカニズムを提供する。該情報伝送帯域幅は、それ以外の場合には、グループ９１（ｇ）の何れもが好適状況な待ち行列９４（ｑ）を有しないから使用されない。１実施例では、無制限グループ９２は複数レベルビットマップ９７の形式であって、それは第９図に記載している。図面を参照すると、ビットマップ９７は次の構成を含んでいる。
（i）、高レベルビット９７（０）（１）から９７（０）（Ｋ）のシリーズ（通常は参照符号９７（０）（Ｋ）で表す）
（ii）、中レベルビット９７（１）（ｌ）から９７（２）（ＩＫ）のシリーズ（通常は参照符号９７（１）（ｉＫ）と表示する）
（iii）、低レベルビット９７（２）（ｌ）から９７（２）（ＩＫＬ）のシリーズ（但しＫ、Ｉ、Ｌは素数である）（通常は参照符号９７（２）（ＩＫＬ）と表示する。（但しＩ、Ｋ、Ｌは素数である。）
【００３９】
各低レベルビット９７（２）（ｉｋｌ）は、出力ポートモジュール３１（Ｐ）によって取り扱われる可能性のある、接続の一つに関係している。もし接続が過剰な情報伝送帯域幅を分担している場合、該接続に関係するデジタルワード９７（２）（ｉｋｌ）のビットは、選ばれた値に設定され、さもない時はビットはクリアされる。接続が保証されたサービスレートに関係したものでない場合、又は接続が保証されたサービスレートと関係し且つ、接続が過剰帯域幅を分担する場合には、接続のビット９７（２）（ｉｋｌ）が通常は設定される。接続がグループ９１（ｇ）に関係している時は、無制限グループ９２にだけ関係する各接続は、接続表中の接続情報エントリー５２（ｃ）を有しており、待ち行列はエントリー５２（ｃ）とセルポインターテーブル５３中の後続セルポインター８０によって示される。しかしながら、無制限グループ中にのみ存在する待ち行列のエントリー５２（ｃ）は、後続グループテーブル５４中の後続グループポインター８６によって、他のエントリー５２（ｃ）にリンクする必要は無い。
【００４０】
中及び高レベルビット９７（１）（ｉｋ）と９７（０）（Ｋ）は、設定されている低レベルビット９７（２）（ｉｋｌ）の中の何れであるかを特定する時間を節減するために使用される。特に中レベルビット９７（１）（ｉｋ）のおのおのは、例えば低レベルビット９７（２）（ｉｋｌ）のシリーズと関係しており、中レベルビット９７（ｌ）（１）は低レベルビット９７（２）（ｌ）から９７（２）（Ｌ）域に関係し、中レベルビット９７（ｌ）（２）は低レベルビット９７（２）（Ｌ＋１）から９７（２）（２Ｌ）と関係し、以下同様である。もし、低レベルビット９７（２）（ｉｋｌ）の何れかが設定されている時、関係する中レベルビット９７（１）（ｉｋ）も又設定される。同様に中レベルビット９７（ｌ）（ｉｋ）のおのおのは、高レベルビット９７（０）（ｋ）と例えばＩ個の中レベルビット９７（１）（ｉｋ）のシリーズと、中レベルビット９７（１）（ｌ）から９７（２）（Ｉ）と関係する低レベルビット９７（０）（１）と関係し、高レベルビット９７（０）（２）は中レベルビット９７（２）（Ｉ＋１）から９７（２）（２Ｉ）と関係し、以下同様である。もし、中レベルビット９７（１）（ｉｋ）の何れかが設定されると、関係する上レベルビット９７（０）（ｋ）も又設定される。
【００４１】
無制限の待ち行列９２もまた、高レベルポインター９８（Ｕ）、中レベルポインター９８（Ｉ）、低レベルポインター９８（Ｌ）の一組のポインター（引用符号（９８）で一般化される）を利用する。ポインター９８（Ｕ）、９８（Ｉ）、９８（Ｌ）の一組はインデックスを作り、それは無制限の待ち行列９２を用いた最後の選択である接続と関連して高レベルビット９７（０）（ｋ）、中レベルビット（１）（ｉｋ）、低レベルビット９７（ｉｋｌ）を示す。グループ９１（ｇ）の何れも選択するには適切でない場合、ビットマップ９７とポインター９８が使われて、セルＣＥＬＬ（ｉ）が転送されるべき、接続が示される。セルＣＥＬＬ（ｉ）を転送すべき次の接続を選択するには、低レベルポインター９８（Ｌ）をまず増加させ、設定されている次のビット９７（２）（ｉｋｌ）を見つける。もし低レベルポインター９８（Ｌ）が、低レベルビット９７（２）（ｉｋｌ）の組を示することなく、値（Ｌ）を通過して増加した時は、それをリセットし、中レベルポインター９８（Ｉ）が増加し、該中レベルポインター９８（Ｉ）によって指定された中レベルビット９７（１）（ｉｋ）が検査される。もし中レベルビット９７（１）（（ｉ＋１）ｋ）が設定されている時、少なくとも低レベルビット９７（２）（（ｉ＋１）ｋ＋Ｉ）から９７（２）（（ｉ＋１）ｋ＋Ｌ）が設定され、この場合、低レベルポインター９８（Ｌ）が繰り返し増加し、最初の低レベルビットが見つかるまでこれを行い、その後選択すべき次の接続を示す。
【００４２】
他方、低レベルポインター９８（Ｌ）がリセットされる場合、中レベルポインター９７（Ｉ）が示す中レベルビット９７（１）（（ｉ＋１）ｋ）は設定されず、低レベルビット９７（２）（（ｉ＋１）ｋ＋Ｉ）から９７（２）（（ｉ＋１）ｋ＋Ｌ）の何れも設定されないことは明らかである。この場合には、中レベルポインター９８（Ｉ）が再び増やされ、設定されている中レベルビットを示すまで行われる。中レベルポインター９８（Ｉ）が設定されている中レベルビット９７（１）（ｉｋ）をポイントする場合、低レベルビット９７（２）（ｉｋ）から９７（２）（ｉｋ＋Ｌ）の一つがセットされ、低レベルポインター９８（Ｌ）は、設定されている低レベルビット９７（２）（ｉｋ）から９７（２）（ｉｋ＋Ｌ）の最初のものをポイントするまで増加する。それは順番に、伝送すべきセルＣＥＬＬ（ｉ）を提供するために選択される接続と関係する。
【００４３】
しかし、もし中レベルポインター９８（Ｉ）が一組の中レベルビット９７（１）（ｉｋ）をポイントせずに値（Ｌ）を通過するときは、それはリセットされ、高レベルポインター９８（Ｕ）が増加し、高レベルビット９７（０）（ｋ＋１）であって、中レベルポインター９８（Ｉ）によってポイントされたものが検査される。もし前記高レベルビット９７（０）（ｋ＋１）がセットされていると、少なくとも中レベルビット９７（１）（ｋ＋１）から９７（１）（ｋ＋Ｉ）の少なくとも一つがセットされ、この場合中レベルポインター９８（Ｉ）は、セットされた低レベルビットの最初のものが見つかるまで増加して、そして順番に、選択されるべき次の接続が認識される。
【００４４】
他方、中レベルポインター９８（Ｉ）がリセットされるとき、高レベルポインター９７（Ｕ）がポイントする高レベルビット（０）（ｋ＋１）はセットされず、中レベルビット９７（１）（ｋ＋Ｉ）から９７（１）（ｋ＋Ｉ）の何れもがセットされない。この場合、高レベルポインター９８（Ｕ）は再び増加し、セットされている高レベルビットをポイントするまで続けられる。高レベルポインター９８（Ｕ）が、セットされている高レベルビット９７（０）（ｋ）をポイントする時、中レベルビット９７（１）（ｋ）から９７（１）（ｋ＋Ｉ）の一つがまたセットされ、中レベルポインター９８（Ｉ）はセットされている中レベルビット９７（１）（ｋ）から９７（１）（ｋ＋Ｉ）の最初のものをポイントするまで増加する。そして、転送するセルＣＥＬＬ（ｉ）を提供するために選択される接続に順次関係する。もし高レベルポインター９７（Ｕ）が、セットされている高レベルビットをポイントすることなく、最後の高レベルビット９７（０）（Ｋ）をポイントする値Ｋを通過して増加すると、それはリセットされ操作は続く。
【００４５】
中間及び高レベルビット９７（１）（ｉｋ）及び９７（０）（ｋ）を与えることによって、無制限待ち行列９２中の接続を表示するために必要な時間が、短縮されることが認められるであろう。なぜならば、一連の低及び中間レベルビットは、それぞれ中間及び高レベルビットとそれぞれ関係しており、各高レベルビットがセットされていない時は検査する必要がないからである。
【００４６】
無制限グループ９２を用いて伝送したセルＣＥＬＬ（ｉ）が、保証サービスレートの接続を用いたグループ９１（ｇ）中の待ち行列９４（ｑ）からであった場合、第８図に関連して記載したように、待ち行列９４（ｑ）を含むリスト９４を再度求めることは通常はしない。待ち行列９４（ｑ）がそれぞれのグループ９１（ｇ）に関するリストのヘッドへ到達した時に、リスト９４（ｇ）が再度要求されなければ、スケジュールユニット４３は後続セル待ち行列エントリー９４（ｑ）（１）（すなわち、無制限グループ９２を経て、伝送の為に選択されたものの行にあるセル待ち行列エントリー）中のセルＣＥＬＬ（ｉ）を第５図及び第６図に関連して記載された伝送の為にある時点で選択するであろう。従って待ち行列９４（ｑ）が二つのメカニズムを通じて、伝送するためのセルＣＥＬＬ（ｉ）を提供する為に選択される。即ち上記二つのメカニズムとは、最低限のサービスレートを確保する様にグループ９１（ｇ）によって与えられた制御メカニズムと、待ち行列９４（ｑ）が過剰帯域幅の一部受け持ちを確実にするため、無制御グループ９２によって与えられた制御メカニズムである。
【００４７】
図５乃至図７を再び参照し、接続グループユニット４２、特にグループコントローラーモジュール４５は次を含む多くの機能を実行する。
（Ａ）新しい接続が作成された時、新しい待ち行列９４（ｑ）と必要に応じて新しいグループ９１（ｇ）を作成し、新しい資源（リソーシズ）（特に図６に関連して上述した各種データ構造）をそれらの為に配分する。
（Ｂ）スケジュールユニット（４３）から得られたグループ選択情報に基づき、伝送のためのセルＣＥＬＬｉを提供するため、セル出力部３５をイネーブルにする。グループ選択情報は、先頭待ち行列９４（０）が伝送の為のセルＣＥＬＬ（ｉ）を与えるグループを示す。さらに、先頭待ち行列のタイムスタンプを増加し、選択されたグループ９１（ｇ）中の待ち行列９４（ｑ）を認識する。
（Ｃ）待ち行列９４（ｑ）のサービスレートが変化し、あるいはグループ９１（ｇ）の資源が新しいグループの為に必要とされたとき等に、待ち行列９４（ｑ）の一つあるいはそれ以上が、あるグループ９１（ｇ）から他のグループ９１（ｇ’）へ移動する。
（Ｄ）待ち行列が空になった時に、待ち行列９４（ｑ）を消滅させ、グループが空になったとき、グループ９１（ｇ）を削除する。
【００４８】
接続グルーピング・ユニット４２は、グループ制御モジュール４５に加えて、グループ・アロケーション・モジュール４６、及び、グループポリシング・モジュール４７を含み、グループ９１（ｇ）の設定、維持を行いながら、数多くの作業をこなす。出力ポート・モジュール３１（ｐ）が新たな接続状況を作り出したり、ある接続状況に対応するサービス・レートが変化したりすると、これらの要素４６、４７は、グループ制御モジュールとともに、新たな状況に対応する待ち行列９４（ｑ）をつくり、サービス・レートが変わる接続状況に対応する待ち行列９４（ｑ）、古いサービス・レートのグループ９１（ｇ）から、新しいサービス・レートのグループ９１（ｇ）へ移動するべきか、するならどうやって移動するのか、あるいは、新たなサービス・レートに対応する新しいグループ９１（ｇ）を新設するべきかを、確定する。特に、グループ・ポリシング・モジュール４７は、グループ制御モジュール４５とともに、別々のサービス・レートの数が（グループ情報テーブル５２のエントリ５２（ｎ）の数に対応する）、予め決めた上限を越さないことを保証するものであり、また、近い値であるけれども、必ずしも同一ではないサービス・レートは、ひとつの範疇にまとめる。加えて、グループ・アロケーション・モジュール４３は、多様なエントリ５６（ｇ）をグループ・テーブル５６内に保有することで、新しいグループ９１（ｇ）や各グループ内での待ち行列９４（ｑ）を配列する際に、グループ制御モジュール４５を助ける。
【００４９】
新しい待ち行列９４（ｑ）、及び、必要であれば、新しいグループ９１（ｇ）（上記アイテムＡ）の設定という点に関していえば、グループ制御モジュール４５は、それに呼応し、ネットワーク１０上に伝送されるセルを制御するように作動して、送信元コンピュータ・システム１２（ｍS）と、受信先コンピュータ・システム１２（ｍD）の間のパケット２０（図２）の伝送経路の設定を制御する。その作動過程で、グループ制御モジュール４５は、新しい接続状況に対応する接続テーブル５２にある接続情報エントリ５２（ｃ）を設定および初期化し、接続情報エントリ５２（ｃ）に対応するタイムスタンプ・テーブル５５のエントリ５５（ｎ）の中に、最初のタイム・スタンプ８７を与える。第１セルＣＥＬＬ（ｉ）がクロック（９３）に表示された時刻として、接続のために受信されたとき、グループ制御モジュール（４５）は、最初のタイムスタンプを与えることができる。そのとき、セルは受信せられ、その値は下記の如く変形されるであろう。もし、新しい接続が、グループ・テーブル（５６）中のエントリ５６（ｇ）によって決められたグループ９１（ｇ）の１つに関連するサービスレートに対応した関連のある保証されたサービスレートを有しているときは、グループ制御モジュール（４５）は、新たに作られた待ち行列（９４（ｑn））をグループ９１（ｇ）のためのリスト（９４）に関連させることができる。それは、必要とされる保証されたサービスレートを提供し、実際にもセルＣＥＬＬ（ｉ）が接続のために受信されたときは、それをグループにリンクする。他方、新しい接続が、実在するグループ９１（ｇ）の何れから与えられるサービスレートにも対応しない保証されたサービスレートを必要とするときは、グループ制御モジュール（４５）は、新しい待ち行列９４（ｑn）を含めて、新しいグループを形成できる。そして、その過程で、新しいグループのためのグループ・テーブル（５６）中で、グループ・アロケーション・モジュール（４６）とグループ・ポリシー・モジュール（４７）によって与えられた資源を用いて、新しいエントリ５６（ｇ）を形成する。
【００５０】
上記したとおり、各接続に対応する待ち行列９４（ｑ）の関連は、特にグループ９１（ｇ）については、通常は該接続部に関連した保証サービスレートに基づいている。出力サポートモジュール３１（ｐ）は、接続がそれによって扱われるべき異なった各保証サービスレートに対応して、新しいグループ９１（ｇ）を形成する。しかし乍らそれは、グループ表（５６）中での別個のエントリー５６（ｇ）と、タイム・インターバル・テーブル（５７）中での対応するエントリー５７（ｇ）を、各異なった保証サービスレート毎に必要とすることを認識せねばならない。或る特別な例では、グループ表（５６）及びタイム・インターバル・テーブル（５７）中のエントリー５６（ｇ）と（５７）の数は制限されている。上記の例では、グループ・テーブル（５６）とタイム・インターバル・テーブル（５７）が詰まっているとき、そして出力ポートモジュール３１（ｐ）が別の保証サービスレートであって、表（５２）中のどのエントリー５２（ｎ）にも関連しないレートの新しい接続に用いられるときには、グループ制御モジュール（４５）は、グループ・ポリシー・ユニット（４４）と協働して、新しい接続を提供する。該接続の提供は、新接続に対応して必要なサービスレートに最も近く、且つそれ以下ではないサービスレートを有するグループ９１（ｇ）に関連させることが望ましい。
【００５１】
グループ制御モジュール（４５）が、新しい接続を、新接続のために必要とされるサービスレートに最も近いが、望ましくはそれ以下ではないサービスレートのグループ９１（ｇ）に関連させるとき（上記（ｉ）項）、新接続に対応する待ち行列９４（ｑ）を、待ち行列９４（ｑ）のシーケンス中の位置で、グループ９１（ｇ）に対応するリスト（９４）にリンクさせ、次の待ち行列９４（ｇ）がより高いタイムスタンプに確実に関連させることが望ましい。タイムスタンプ（８７）の無い新たに形式された接続については、グループ・コントローラ・モジュール（４５）は、初期タイムスタンプを有する接続に関連する待ち行列９４（ｑ）を提供する。初期タイムスタンプを有する該接続は、ヘッドとテイルの待ち行列９４（０）と９４（０）と、グループの２分されたタイム・インターバル（８５）のタイムスタンプ（８７）の合計に対応する。グループ中の連続した待ち行列９４（ｑ）のタイムスタンプの順序を維持するため、それが新接続のための待ち行列９４（ｑ）の挿入時であれ、又はそれのセルカウンター（７０）が零にまで減少したためにグループ９１（ｇ）から以前取り除いた接続のための待ち行列９４（ｑ）を再挿入する時であれ、グループ制御モジュール（４５）は、グループ９１（ｑ）のリスト（９４）中の待ち行列９４（ｑ）へ進み込む（ｓｔｅｐ  ｔｈｒｏｕｇｈ）ことが望ましい。該グループ９４（ｇ）中へ、新待ち行列９４（ｑ）を接続して、リスト（９４）中の特定点を指定する様にする。該リスト（９４）には新リスト９４（ｑ）をリンクさせて、シーケンス順序中での各タイムスタンプを維持する。
【００５２】
または、グループ制御モジュール（４５）は、この順序維持を、次の手段で略実現する。
（i）待ち行列９４（ｑ）のタイムスタンプ（８７）が、ヘッドの待ち行列９４（０）のタイムスタンプより以下の場合は、待ち行列９４（ｑ）をリスト（９４）のヘッドへ挿入し、待ち行列９４（ｑ）に関連してタイムスタンプを調整して、（ａ）．それのタイムスタンプ（８７）又は（ｂ）．テイルの待ち行列９４（Ｑ）のタイムスタンプから、フィールド（５６）中のグループのサービスレートを減じたもの，の最大に対応させる。
（ii）リスト（９４）のタイムスタンプ（８７）が、テイルの待ち行列９４（Ｑ）のタイムスタンプより以上のときは、待ち行列９４（ｑ）をリスト（９４）のテイルへ挿入し、待ち行列９４（ｑ）に関連するタイムスタンプを（ａ）．それのタイムスタンプ（８７）又は（ｂ）．テイルの待ち行列９４（Ｑ）のタイムスタンプからフィールド（５６）のグループのサービスレートを減じたもの，の最大に対応させる。
（iii）待ち行列９４（ｑ）のタイムスタンプ（８７）が、テイルの待ち行列９４（Ｑ）のタイムスタンプの方へよりも、ヘッドの待ち行列９４（０）のタイムスタンプの方へ一層近いが、ヘッドの待ち行列９４（０）のタイムスタンプより以上であったときは、待ち行列９４（ｑ）をリスト（９４）のヘッドへ挿入し、それのタイムスタンプ（８７）をヘッドの待ち行列９４（０）のタイムスタンプと等しくなる様に調整する。
（iv）待ち行列９４（ｑ）のタイムスタンプ（８７）が、ヘッド待ち行列９４（０）のタイムスタンプの方へよりも、テイル待ち行列９４（Ｑ）のタイムスタンプの方に一層近いが、テイル待ち行列９４（Ｑ）のタイムスタンプよりも大きくない場合は、待ち行列９４（ｑ）をリスト（９４）のテイルに挿入し、それのタイムスタンプ（８７）を、テイル待ち行列のタイムスタンプと等しくなる様に調整する。
これらはリスト（９４）中のタイムスタンプの順序を維持する。グループ・コントローラ・モジュール（４５）は、以前除去した接続を、セルＣＥＬＬ（ｉ）をその接続のために受信したとき、グループ９１（ｇ）へ接続する際、同様な機能（i）から（iv）を実行する。
【００５３】
セル出力部（３５）が、伝送のためにセルＣＥＬＬ（ｉ）を提供することに関して（上記（Ｂ）項）、セルＣＥＬＬ（ｉ）を伝送すべき場合には、スケジュールユニット（４３）が、伝送のためのセルＣＥＬＬ（ｉ）を与えるグループ９１（ｇ）からのヘッド待ち行列９４（０）の標識を、グループ制御モジュール（４５）に提供するとき、グループ制御モジュール（４５）は、セル出力部（３５）に対して、ヘッド待ち行列９４（０）からのセルＣＥＬＬ（ｉ）を伝送する。更にグループ制御モジュール（４５）は、次の処理を実行する。
（i）セルＣＥＬＬ（ｉ）が伝送されて来るグループ９１（ｇ）に関連して、タイム・インターバル・テーブル（５２）のエントリー５７（ｇ）中のタイム・インターバル・テーブル（８５）を用いて、選択したグループのヘッド待ち行列９４（０）のヘッダー（９５）のタイムスタンプ（８５）を増加させ、且つ、（ii）グループ（９１）のリスト（９４）を上記した如く再整理し、セルが伝送されて来た待ち行列９４（０）をリスト（９４）のテイルにリンクさせる。
【００５４】
他方、スケジュールユニット（４３）が、無制限グループ（９２）からの待ち行列の標識を有するグループ制御モジュール（４５）を提供すると、グループ制御モジュール（４５）は、セル出力部（３５）に対し、待ち行列からセルＣＥＬＬ（ｉ）を伝送することを可能ならしめる。セルＣＥＬＬ（ｉ）が伝送されて来る待ち行列９４（０）のヘッダー（９５）のタイムスタンプ（８５）を新規にする場合（上記（ｉ）項）、グループ制御モジュール（４５）は、セルＣＥＬＬ（ｉ）が伝送されて来たグループ９１（ｇ）に関連するタイム・インターバル・テーブル（５７）のエントリー５７（ｇ）中のグループインターバル（８５）を利用する。各グループ９１（ｇ）に与えられたグループタイムインターバル（８５）の値は、各グループ９１（ｇ）の様々な接続に関連した待ち行列９４（ｑ）からのセルＣＥＬＬ（ｉ）の伝送の間の時間は、必要とされる保証された、又は最小のサービスレートを満たす。
【００５５】
上記したとおり、例えば待ち行列９４（ｑ）のサービスレートが変り、又はグループ９１（ｇ）の資源（ｒｅｓｏｕｒｃｅｓ）が新グループに必要とされる場合、グループ制御モジュール（４５）は待ち行列９４（ｑ）を或るグループ９１（ｇ）から他のグループ９１（ｇ’）へ移動する（上記（Ｃ）項）。上記作用に於て、グループ制御モジュール（４５）は、１つ又は複数の待ち行列を、グループ９１（ｇ）から他のグループ９１（ｇ’）へ、前述の（Ａ）項に関連して記載した同じ要領でリンクさせることができる。
【００５６】
これに加えて、グループ制御モジュール（４５）は、待ち行列が空になったとき、待ち行列９４（ｑ）の削除、及びグループが空になったときグループ９１（ｇ）の削除をも行なう（上記（Ｄ）項）。グループ制御モジュール（４５）は、待ち行列９４（ｑ）が空になったときを決定が出来る。また待ち行列に関連する接続のための接続情報エントリー５２（ｃ）のセルカウンター（７０）がゼロ値を有するときは、待ち行列９４（ｑ）は、削除されねばならない。待ち行列９４（ｑ）が削除されねばならないときは、後続グループポインター（８６）は調整されて、待ち行列（９４）の削除に対応する。このことは、待ち行列９４（ｑ）がヘッドの待ち行列であって、セルＣＥＬＬ（ｉ）を伝送した直後のときに、起こり易いから、グループ制御モジュール（４５）はそれがリスト（９４）を再整理する場合、新ヘッド待ち行列を単に識別するだけでよく、グループ９１（ｇ）のテイル待ち行列９４（Ｑ）として削除する様には、待ち行列をリンクしない。グループ９１（ｇ）の削除に際して、グループ制御モジュール（４５）は、グループ９１（ｇ）に関連するエントリー５６（ｇ）の有効フラッグ（８２）をリセットするであろう。
【００５７】
上記したとおり、スケジュールユニット（４３）は伝送のため、様々なグループ９１（ｇ）と（９２）をスケジュールする。図１０は、スケジュールユニット（４３）の機能ブロック図である。通常は、スケジュールユニット（４３）がセルＣＥＬＬ（ｉ）の伝送のために、グループ９１（ｇ）を選択するときは、先ずそのグループが好適か否かを判断せねばならない。上記したとおり、グループが好適か否かを判断するためには、スケジュールユニット（４３）は、様々なグループのヘッド待ち行列９４（０）のタイムスタンプを利用し、更に様々なグループ９１（ｇ）のグループタイムインターバル（８５）も利用する。スケジュールユニット（４３）は、様々なグループ９１（ｇ）の中から、伝送のために選択する。この選択は、グループ９１（ｇ）の各ヘッド待ち行列９４（ｑ）のタイムスタンプ（８７）の特定の値と、各グループ９１（ｇ）に関連したグループタイムインターバル（８５）とに基づいて行なう。各グループ９１（ｇ）に対して、ヘッド待ち行列のタイムスタンプ（８７）とグループタイムインターバル（８５）は、それ以前にはグループ９１（ｇ）のヘッド待ち行列９４（０）は選択されることはないであろう好適なスタートタイムから始まるタイムウインドウを決定する。また必要な伝送レートを提供するために、グループのヘッド待ち行列が選択されるべき終了時刻が決められる。タイムスタンプ（８７）が終了時刻として扱われるのであれば、好適開始時刻は、グループタイムインターバル（８５）によって減少させられたタイムスタンプ（８７）によって決定されるであろう。他方、タイムスタンプ（８７）が好適な開始時刻として扱われるのであれば、終了時刻は、グループタイムインターバル（８５）によって増加させられたタイムスタンプ（８７）によって決定されるであろう。もし伝送に好適なグループがあれば、それらのグループに関してスケジュールユニット（４３）はヘッド待ち行列９４（０）にタイムスタンプ（８５）を有するグループ９１（ｎ）を選択し、該待ち行列９４（０）の中にある第１待ち行列エントリー９４（０）（０）中のセルＣＥＬＬ（ｉ）を適当な通信リンク１３（ｌ）を越えて伝送する最低の終了時刻を決める。もしスケジュールユニット（４３）がグループ９１（ｇ）のどれも、好適でないと判断したときは、伝送のためにスケジュールされるべき接続は、無制限のグループ（９２）から選択されるべきであろう。
【００５８】
図９を参照すると、スケジュール・ユニット４３は、グループ・セレクタ・モジュール１００、有効フラッグ・チェック・モジュール１０１、好適タイム・ジェネレータ１０２、タイム・スタンプ検索モジュール１０３、最小値エレメント・セレクタ１０４、及び最小値エレメント・ストア１０５を含んでおり、これら全てはコントロール・モジュール１０６の制御下にある。一般に、スケジュール・ユニット４３は、夫々がグループ９１（ｇ）の１つに関係づけて待ち行列内の先頭待ち行列９４（０）からタイム・スタンプを検索し、待ち行列９４（０）が好適であることを該タイム・スタンプが示しているか否かを判別し、もし示しているならば、該タイム・スタンプが以前に検索したタイム・スタンプの最小値であるか否かを判別する動作が連続的に繰り返される。もし、前記最小値であるならば、スケジュール・ユニット４３は、前記タイム・スタンプを新たな最小値として、先頭待ち行列９４（０）に関する識別子と共に記憶し、次の繰返しに対して順番付ける。グループ９１（ｇ）の全てに接続して、これらの動作を実行した後に、スケジュール・ユニット４３が記憶する先頭グループ識別子によって、好適であるグループ全ての中で最小のタイム・スタンプを有する先頭待ち行列９４（０）が識別され、次に、該先頭待ち行列９４（０）が、伝送用セルＣＥＬＬ（ｉ）を供給する。
【００５９】
特に、スケジュール・ユニット４３が先頭待ち行列９４（０）が伝送用のセルＣＥＬＬ（ｉ）を供給すべきグループ９１（ｇ）を特定するために、グループ９１（ｇ）を選択する必要があるときには、グループ・セレクタ・モジュール１００は、グループ・テーブル５６内の最初のエントリ５６（０）を特定するＧＲＯＵＰ  ＥＮＴＲＹ  ＳＥＬ（グループ・エントリ選択）指示を生成する。有効フラッグ・チェック・モジュール１０１は、前記エントリ５６（０）が好適であるとエントリ５６（０）の有効フラッグ８２が示しているか否かを判別する。もし、エントリ５６（０）の有効フラッグ８２がクリアであって、エントリ５６（０）が有効なグループ９１（ｇ）を特定するものではないことを示していると、有効フラッグ・チェック・モジュール１０１が判別するならば、グループ・セレクタ・モジュール１００は、次のエントリ５６（１）に進み、該エントリ５６（１）を特定するＧＲＯＵＰ  ＥＮＴＲＹ  ＳＥＬ（グループ・エントリ選択）指示を生成し得る。
【００６０】
他方、もし、エントリ５６（０）の有効フラッグ８２がセットであると、有効フラッグ・チェック・モジュール１０１が判別するならば、グループ９１（ｇ）に関連したグループ・タイム・インターバル８５をタイム・インターバル・テーブル５７から検索し、該グループ・タイム・インターバル８５を好適タイム・ジェネレータ・モジュール１０２に連結する。さらに、タイム・スタンプ検索モジュール１０３は、グループ９１（ｇ）においてエントリ５６（０）に関連する先頭待ち行列９４（０）に関する接続に関係するタイム・スタンプ８７を検索し、該タイム・スタンプ８７を好適タイム・ジェネレータ・モジュール１０２に結合する。次に、好適タイム・ジェネレータ・モジュール１０２は、タイム・スタンプ検索モジュール１０３が提供するタイム・スタンプ８７と、タイム・インターバル・テーブルが提供するグループ・タイム・インターバルとから好適タイム値を生成し、好適タイム値をクロック９３が提供する現在タイムと比較する。好適タイム・ジェネレータ・モジュール１０２は、もし、好適タイムが現在のタイムより小さいと判別するならば、グループ・テーブル５６内のエントリ５６（０）に関連したグループ９１（ｇ）が好適であることを示すＥＬＩＧ（好適）指示を生成する。
【００６１】
また、タイムスタンプ検索モジュール１０３が検索するタイム・スタンプ８７は、最小エレメント選択モジュール１０４に結合される。また、最小エレメント選択モジュール１０４は、以前の最小タイム・スタンプに対応する最小エレメント・ストア１０５のエントリ１０７から、以前の最小タイムスタンプ値を受信する。一般に、最小エレメント選択モジュール１０４は、エントリ１０７における以前の最小タイム・スタンプ値を、検索したタイム・スタンプと比較して、何れが小さい値であるかを判別する。しかしながら、このとき、スケジュール・ユニット４３は、グループ・テーブル５６における最初のエントリ５６（０）に関係するグループ９１（ｇ）を処理しているから、比較に用いられるべき以前の最小タイム・スタンプは、存在しない。従って、最小エレメント選択モジュール１０４は、この繰り返しに関してエントリ１０７の内容を無視でき、或いは、最小エレメント選択モジュール１０４が、最小タイム・スタンプ値を有する最初のエントリ５６（０）を確実に選択するために、エントリ１０７は、最初の繰り返しの前に相当高い値で初期化され得る。最小エレメント選択モジュール１０４は、記憶のために、最小タイム・スタンプ値をエントリ１０７に結合する。さらに、最小値レメント選択モジュール１０４は、記憶のために、選択された最小タイム・スタンプ値に関係するグループに関する識別子を、最小エレメントストア１０５の最小エレメント識別子エントリ１０８に提供する。従って、もし、グループ選択モジュール１００からのＧＲＯＵＰ  ＥＮＴＲＹ  ＳＥＬ（グループ・エントリ選択）表示によって特定されたグループが、最小エレメントストア１０５のエントリ１０７における現在のタイム・スタンプ値よりも小さいタイム・スタンプ値を有すると、最小エレメント選択モジュール１０４が判別するならば、最小エレメント選択モジュール１０４は、タイム・スタンプ検索モジュール１０３が提供するタイム・スタンプ８７と、グループ選択モジュール１００からのＧＲＯＵＰ  ＥＮＴＲＹ  ＳＥＬ（グループ・エントリ選択）表示とをイネーブルにして、最小エレメント・ストア１０５内のエントリ１０７、１０８にそれぞれ記憶される。他方、もし、エントリ１０７に以前に記憶された最小タイム・スタンプ値の方が低いタイム・スタンプ値を有すると、最小エレメント選択モジュール１０４が判別するならば、最小エレメント・ストア１０５の内容を変化しない。
【００６２】
スケジュール・ユニット４３は、これらの動作を連続的に繰り返して実行する。グループ・テーブル５６内の連続するエントリ５６（ｇ）に関係のあるグループに渡って、これらの動作は進行する。各繰り返しの最後には、最小エレメントストア１０５は、繰返しの間にエントリ５６（ｇ）に関連した好適なグループに関する先頭待ち行列９４（０）に関するタイム・スタンプ８７の最小値を、先頭待ち行列が最小タイム・スタンプを有するエントリ５６（ｇ）に関する識別子と共に含むだろう。従って、全てのエントリ５６（ｇ）を処理した後に、最小エレメント・ストア１０５は、もしあれば、好適である全てのグループに関するタイム・スタンプ８７の最小値と、該グループを特定する識別子とを含むだろう。スケジュール・ユニット４３は、伝送のためのセルＣＥＬＬ（ｉ）を形成すべきグループ９１（ｇ）を選択する際に使用するグループ制御モジュール４５に、識別子とタイム・スタンプ８７の両方を提供し得る。
【００６３】
このような背景をふまえた上で、スケジュール・ユニット４３によってなされる一連の作業を、図１１乃至図１３のフローチャートと併せて、詳細述べることにする。図１１乃至図１３を参照すると、スケジュール・ユニットは、一般的に動作が連続して繰り返される。１回の反復作業ごとに、グループ・テーブル５６内のグループ・テーブル・エントリ５６（ｇ）の１つが処理される。図１１乃至図１３を参照すると、スケジュール・ユニット４は、１回の反復作業ごとに最小エレメント・ストア１０５を初期化し（ステップ１７０）、それから「次の」グループ・テーブル・エントリ５６（ｇ）をグループ・テーブル５６から選択し、そのエントリ５６（ｇ）が有効かどうかを有効性フラッグ８２により確定する（ステップ１７１）。初回の操作では、「次の」グループ・エントリ５６（ｇ）にあたるのは、グループ・テーブル５６の中の最初のエントリ５６（０）であると考えられる。もし、エントリ５６（ｇ）が有効であれば、スケジュール・ユニット４３は、その選択されたグループ・エントリ５６（ｇ）のグループ・ヘッド・ポインタによって示される接続情報エントリ５２（ｃ）に関連するタイムスタンプ８７を取得して、好適な開始時間を算出し（ステップ１７３）、その算出された好適な開始時間が現行時間よりも短いかどうかをクロック９３により確定する（ステップ１７４）。もし、ステップ１７４において好適な終了時間は現行より短いと、スケジュール・ユニット４３が確定したら、そのグループは、セルＣＥＬＬ（ｉ）をそこから伝送するのに好適なグループとして選択される。上述のように、タイムスタンプ８７が好適な開始時刻に対応していれば、スケジュールユニット４３は、ステップ１７３においてタイムスタンプ８７を現行時間に合わせて用い、算出したグループの値の方が好適であるかどうかを確定する。他方、タイムスタンプ８７が終了時間に対応していれば、スケジュールユニット４３は、そのグループのグループ・タイム・インターバル８５だけ、タイムスタンプ８７を減少し、ステップ１７３における好適な開始時間を算定する。
【００６４】
スケジュール・ユニット４３が、ステップ１７４において、ステップ１７１で選択したグループが好適であると確定する場合、それ（すなわち、スケジュール・ユニット４３）は、タイム・スタンプ８７と、多分そのグループのグループ・タイム・インターバル８５とを用いて、終了時間を算出する（ステップ１７５）。上述のように、タイム・スタンプ８７が好適な開始時間に対応している場合、スケジュール・ユニット４３は、ステップ１７５に於いて、そのグループのタイム・インターバルだけ、タイム・スタンプ８７を増分し、終了時間を決める。逆に、タイム・スタンプ８７が終了時間に対応している場合、スケジュール・ユニット４３は、ただその数値を終了時間として使うのみである。ステップ１７５にて終了時間が決定した後、スケジュール・ユニット４３は、その終了時間を、最小エレメントストア１０５のエントリ１０７に記憶されている終了時間の最小値と比較する（ステップ１７６）。もし、スケジュール・ユニット４３がステップ１７６においてステップ１７５で求めた終了時間が最小エレメントストア１０５のエントリ１０７の最小終了時間より値が小さければ、そのステップ１７５で求めた終了時間の方を、エントリ１０７の中に記憶させると共に、選択したグループ９１（ｇ）の識別子もエントリ１０８に記憶させる（ステップ１７７）。
【００６５】
（i）ステップ１７６に戻って、スケジュール・ユニット４３は、このステップにおいて、ステップ１７５で求めた終了時間が、最小エレメントストアのエントリ１０７の中に記憶されている最小終了時間より値が大きいと確定した場合、（ii）ステップ１７４に戻って、スケジュール・ユニット４３は、このステップにおいて、選択したグループが好適でないと確定した場合、又は、（iii）ステップ１７１に戻って、スケジュール・ユニットは、このステップにおいて、選択されたグループのグループ・テーブル・エントリ５６（ｇ）の有効フラッグ８２が、エントリ５６（ｇ）の非有効性を示していると確定した場合、それ（即ち、スケジュール・ユニット４３）は、続いてステップ１７８に進み、グループ・テーブルにさらなるエントリ５６（ｇ）があるかどうかを確定する。もし、さらにエントリ５６（ｇ）があれば、スケジュール・ユニット４３は、ステップ１７０に戻って、そのさらなるエントリ５６（ｇ）に接続して、最初から新たな繰り返しが実行される。他方、さらにエントリ５６（ｇ）がなければ、スケジュール・ユニット４３は、ひきつづきステップ１７９に進み、最小グループ識別エントリ１０８にグループ識別子があるかどうかを確定し、もしあれば、そのグループ識別子をグループ制御モジュール４５に提供し（ステップ１８０）、グループ制御モジュール４５は、上述のように、セル出力セクション３５をイネーブルにして、伝送のためのセルＣＥＬＬ（ｉ）を探索する際に使用される。しかしながら、もし、スケジュール・ユニット４３は、ステップ１７９において、最小グループ識別エントリ１０８にグループ識別子がないと確定するならば（このことは、全てのグループ９１（ｇ）が好適でない場合に起こり得る）、それ（すなわちスケジュール・ユニット４３）は、その旨をグループ制御モジュール４５に伝送し（ステップ１８１）し、グループ制御モジュール４５は、無制限グループを用いて接続を選択し、該接続に関してセルＣＥＬＬ（ｉ）が伝送される。
【００６６】
本発明は、多数の利点を提供する。特に、メッセージの転送経路にいくつもの異なる転送サービス速度が存在するようなディジタル・ネットワークの使用環境に関して、メッセージを転送する経路を、転送サービス速度が近いもの同士でグループ分けして、転送のスケジューリングの効率を高める装置を、本発明は提供する。
【００６７】
上述のように、図１〜図１３に関連して、変更を加えて工夫しうるところが数多くあることは、認識できるであろう。例えば、グルーピングやスケジューリングのメカニズムは、ネットワーク切換ノードと結びつけて上述したが、このメカニズムは、セルを一列に並べ、伝送をスケジューリングするもの以外にも利用できるのであり、例えば、様々なセル供給装置  （図１では、コンピュータ・システム１２（ｍ）として表されている）とネットワーク１０とのインターフェースをとるために使用されるネットワークアダプタ、マルチステージスイッチのキューイングポイント等でもよい。さらに、グルーピングやスケジューリングのメカニズムは、それぞれの装置に分離して使用されることもできる。
【００６８】
さらに、切換ノードは、それが繋がるどのような接続に関しても、最高のセルＣＥＬＬ（ｉ）転送速度を強いる必要がないならば、無制限待ち行列９２を省略できる。その場合、送信可能なサービスレートでの接続状態が割り当てられ、その待ち行列９４（０）は、切換ノードによって割り当てられるサービスレートに基いて、各グループ９１（ｇ）にリンクされる。さらに、超過の帯域幅が確実に使えることで、伝送に適したグループが一つも無ければ、スケジュール・ユニット４３は、（i）少なくとも１つのグループが、伝送に好適であることを保証する量だけ、クロック９３を増加することによって、若しくは（ii）好適性の条件を除去して、タイム・スタンプ８７の値が最も低いグループ９１（ｇ）を選択することによって、グループのスケジューリングを行う。
【００６９】
さらに、この装置が、サービスレートが比較的低い接続状態に対応した転送を効果的に操作する一方、もし、サービスレートが比較的活発である場合、ばらばらなグループ９１（ｇ）のリスト９４を確実に適正な秩序下においておくことは困難であろう。例えば、グループ９１（ｇ）のある接続状態でのサービスレートが変わったとすると、待ち行列９４（ｇ）はそのグループから新しいサービスレートの別グループ９１（ｇ）に移動されることになり、それは新しいグループのことも既存のグループのこともある。図１４は、これらの工程が効率的に操作されるようなアレンジメントを示す。
【００７０】
図１４参照のとおり、図１４において２００（ｇ）という文字で表わされるグループには、各々にノーマルリスト２０１、早期リスト２０２、晩期リスト２０３という３種類のリストが与えられる。ノーマルリスト２０１は、多くの待ち行列２０１（０）〜２０１（Ｘ）（２０１（ｘ）という文字で一般化して示すものとする）から成り、図８に関連して上述したものと同じような方法でリスト内に配置されている。同様に、早期リスト２０２も数多くの待ち行列２０２（０）〜２０２（Ｙ）（２０２（ｙ）という文字で一般化して示すものとする）から成り、晩期リスト２０３も数多くの待ち行列２０３（０）〜２０３（Ｚ）（２０３（ｚ）という文字で一般化して示すものとする）から成る。各待ち行列２０１（ｘ）、２０２（ｙ）、２０３（ｚ）は、図８に関連して前に９４（ｇ）と表わした待ち行列と同じようなものである。これらのリストを規定しているのは、ポインタ２０３〜２０８のそれぞれの先頭と末尾であり、それは、テーブル５２（図６）と同じようなグループ・インフォメーション・テーブルの中に、有効性フラッグ８２とともに加えられたものである。２０１〜２０３のリストは、全て同じグループ・タイム・インターバル８５を共有しており、それによって、グループ２００（ｇ）の待ち行列に関わる全ての接続状態に対するサービスレートを識別する。早期および晩期待ち行列２０２（ｙ）、２０３（ｚ）は、グループ２００（ｇ）と結びつく際には、各ヘッダ９５の各タイム・スタンプ８７に基き、それぞれ、早期リスト２０２、晩期リスト２０３に繋がれる。特に、もし、クロック９３が示す現行時間の値が、待ち行列のタイム・スタンプ８７より大きい場合、接続状態は「早期」に設定され、待ち行列は早期リスト２０２に分類されるが、その逆の場合、接続状態は「晩期」に設定され、待ち行列は晩期リスト２０３に分類される。新たに作られた接続状態は、普通は全て早期リスト２０２に入れられ、グループ制御モジュール４５がそれらの待ち行列をリンクさせている。同様に、晩期リスト２０３にリンクされる待ち行列も上述と同様である（アイテム（Ａ）参照）。早期リスト２０２から来た待ち行列２０２（ｙ）および晩期リスト２０３から来た待ち行列２０３（ｚ）は、伝送用に選択される際、ノーマル・リスト２０１のところで一緒になることになる。
【００７１】
スケジュール・ユニット４３は、グループ２００（ｇ）が伝送に適しているかどうかを決めるとき、および、グループ２００（ｇ）が図６〜１０に触れて上述したのと同じような方法での伝送のために選択されるべきかを決めるとき、２０１〜２０３のリストを全て用いる。すなわち、スケジュール・ユニットだけで、リスト２０１、２０２、２０３がそれぞれ異なるグループであるのにも関わらず、各リストの先頭の待ち行列である２０１（０）、２０２（０）、２０３（０）を処理して、それぞれのリストへの好適性を決定するばかりでなく、伝送予定のセルＣＥＬＬ（ｉ）の接続状態を選択する。しかし、早期リスト２０２もしくは晩期リスト２０３の、それぞれの先頭待ち行列２０２（０）ないし２０３（０）が、伝送用に選択される際、グループ制御モジュール４５は、グループ２００を再整理するときに、ノーマルリスト２０１の先頭待ち行列と末尾の待ち行列を繋げるので、グループ・タイム・インターバルによって、待ち行列のタイム・スタンプ８７は値が大きくなる。以上の理由で、ノーマルリスト２０１は常に分類されやすい状態にあるのである。
【００７２】
図１４に触れて、上述した混合リストの配列方法は、待ち行列がグループから移動してセル・カウンターが０になったあとに、新しいセルＣＥＬＬ（ｉ）が受信されたとき、待ち行列９４（ｇ）をあるグループに入れる。再挿入の接続状況に関しても、用いることができる。その作業では、その接続状況の待ち行列９４（ｇ）は、その待ち行列のタイム・スタンプ８７に基いて、早期リスト２０２を晩期リスト２０３に適正に挿入することができる。
【００７３】
他の変更点についても明らかである。例えば、ＡＴＭメッセージ転送方式を用いたネットワークに関してこの配列は述べられてきたが、ばらばらのサービスレートが存在すると、他方式を使ったネットワークについても、この配列方法が使えることは、評価できることである。加えて、この配列方法は、接続状況の分類法やＡＴＭメッセージ転送方式に従って規定される、一定の長さのセルＣＥＬＬ（ｉ）のキューイングの分類法に関連して記述られてきたが、数あるネットワークのタイプのどれで用いられている情報転送方式についても、この配列方法は使用可能であることも評価できることであろう。
【００７４】
加えて、スケジュール・ユニット４３は、好適性のある接続状況の中から最もタイム・スタンプ８７の値が小さい接続状況を選択するものとして記述されてきたが、スケジュール・ユニットもまた、他の新しい評価基準を用いて選択作業を行えるのである。例えば、スケジュール・ユニットが二者択一式に選択作業を行えるのは、タイム・スタンプ８７が、奇数―偶数値であるような接続状況の中から選択する場合か、グループ・タイム・インターバルが偶数―奇数値は高―低値であるようなグループの中から選択する場合などである。更に、スケジュール・ユニット４３は、他のスケジュール・ユニットが選択したグループや接続状況から更に選択するということもでき、その際、他のスケジュール・ユニットはスケジュール・ユニット４３と同じものであってもよいし、そうでなくてもよいし、似たような別のスケジュール・ユニットでもよいし、あるいは、似たような評価基準を用いて選択作業を行ってもよい。
【００７５】
また、特殊な用途向けに作られたハードウェアからでも、一般向けのマイクロプロセッサからでも、それらを適当なプログラムでどのように組み合わたものであっても、本発明に従った装置は、全体的にあるいは部分的に構成され得ることが認識される。上記の説明は、本発明の特定の実施形態に限定されている。しかしながら、本発明に様々な変形及び修正を行なって、本発明の特徴の幾つかまたは全てを達成し得ることは、明らかであろう。特許請求の範囲の目的は、前記範囲及び本発明の真の精神及び範囲内に入るような他の変形及び修正をカバーする。
【００７６】
論文、ジョン・Ｃ．Ｒ．ベネット（Jon C.R. Bennet）とヒューイ・チャン（Hui Zhang）共著“ＷＦ2Ｑ：最悪の場合も考慮した、適正評価行列（Worst-caseFair Weighed Fair Queuing）”を参考文献として本願に添付する。また、未発表論文、ジョン・Ｃ．Ｒ．ベネット、ヒュー・チャン共著、“なぜ、ＷＦＱは統合サービス・ネットワークに不十分か（Why WFQ Is Not Good Enough For Integrated Services Networks）”を参考文献として本願に添付する。
【図面の簡単な説明】
【図１】本発明に基づく切換ノードを有するコンピュータ・ネットワークを示す概略図である。
【図２】図１のネットワーク上で転送される、メッセージ・パケットおよび構成セルの構造を示す概略図である。
【図３】図１のネットワーク上で転送される、メッセージ・パケットおよび構成セルの構造を示す概略図である。
【図４】図１に示す切換ノードにおいて有効な切換ノードの構造を示す概略図である。
【図５】図４に示す切換モードにおいて有効な出力ポートモジュールを機能的に示すブロック図である。
【図６】図１に示すネットワークでの情報転送において、出力ポート・モジュールが使うデータ構造のいくつかを示す図である。
【図７】図６に示す出力ポート・モジュールにおいて有効なグループ分けの構造を示す図である。
【図８】図６に示す出力ポート・モジュールにおいて有効なグループ分けの構造を示す図である。
【図９】図６に示す出力ポート・モジュールにおいて有効なグループ分けの構造を示す図である。
【図１０】図６に示す出力ポート・モジュールにおいて有効なスケジュール・ユニットを機能的に示すブロック図である。
【図１１】図１０に示すスケジュール・ユニットにて行われる動作を示す流れ図である。
【図１２】図１０に示すスケジュール・ユニットにて行われる動作を示す流れ図である。
【図１３】図１０に示すスケジュール・ユニットにて行われる動作を示す流れ図である。
【図１４】  セル転送サービス・グループ、および、それに有効なデータ構造の第２実施例を示す図である。
【符号の説明】
(10) コンピュータネットワーク
(11) 切換ノード
(12) コンピュータシステム
(13) 通信リンク
(31) 出力ポートモジュール
(43) スケジュールユニット
(94) 待ち行列
【図１】
0003984680.tif 000002
【図２】
0003984680.tif 000003
【図３】
0003984680.tif 000004
【図４】
0003984680.tif 000005
【図５】
0003984680.tif 000006
【図６】
0003984680.tif 000007
【図７】
0003984680.tif 000008
【図８】
0003984680.tif 000009
【図９】
0003984680.tif 000010
【図１０】
0003984680.tif 000011
【図１１】
0003984680.tif 000012
【図１２】
0003984680.tif 000013
【図１３】
0003984680.tif 000014
【図１４】
0003984680.tif 000015