【手続補正書】
【提出日】平成17年5月13日(2005.5.13)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数の仮想接続にしたがって送信されるＡＴＭセルのスペーサであって、
着信セルが書き込まれ、発信セルが読み出されるセルメモリ（４２）と、
少なくとも前記セルの到着時刻（ｔａ）と仮想接続に割り当てられたスペーシング間隔（Ｔ）とを含むパラメータに基づいて、前記仮想接続に関連する各セルに対する理論的送出時間（ＴＥＴ）の回帰的な計算をする手段（４０）を有し、前記セルメモリに格納された各セルに理論的送出時間（ＴＥＴ）を割り当てる手段（４０、４１）と、
セルメモリがセルを収容している各仮想接続に対して、前記セルがリストの始めとリストの終わりの間で先入れ先出しモードで格納されるロケーションのリストを前記セルメモリが有するように、関連するポインタメモリ（４３）により、前記セルメモリ（４２）を管理するスペーシング制御手段（４１、４６）と、
仮想接続特性と、前記仮想接続に関するリストの始めに含まれているセルの理論的送出時間から成るソートキーを各々が含むデータ要素（Ｋ（ｉ）、Ｒ（ｉ））を順序づけ、最小のソートキーを有する少なくとも１つのデータ要素を選択するソーティング手段（４１、４４）と
を有し、
前記スペーシング制御手段は、前記ソーティング手段によって、選択されたデータ要素において識別された仮想接続に関するリストの始めに含まれたセルの送出を命令するように構成されており、
前記セルメモリ（４２）がセルを含んでいない仮想接続に関連するセルが到着すると、前記ソーティング手段（４１、４４）が前記仮想接続の識別情報を有する新しいデータ要素、およびソートキーとして、前記回帰的計算手段（４０）により与えられた前記セルの理論的送出時間を受け取る、ＡＴＭセルのスペーサにおいて、
少なくとも１つの第２のセルをさらに含むロケーションのリストを前記セルメモリが有する仮想接続に関連する第１のセルを送出すると、前記ソーティング手段が前記仮想接続の識別情報を有する新しいデータ要素、およびソートキーとして、前記第１のセルの理論的送出時間と前記接続に割り当てられたスペーシング間隔との和に等しい、前記第２のセルの理論的送出時間を受け取ることを特徴とするＡＴＭセルのスペーサ。
【請求項２】
送出されるセルによって占有されていない前記セルメモリ（４２）のロケーションが、フリーロケーションのリストの始めとフリーロケーションのリストの終わりの間のフリーロケーションのリストの形で前記スペーシング制御手段（４１、４６）により、前記ポインタメモリ（４３）に含まれるポインタ（Ｐｔｒ＿ｆｒｅｅ、Ｐｔｒ＿ｃｏｎｔ）によって管理される請求項１に記載のスペーサ。
【請求項３】
前記セルメモリの各ロケーション（Ｃｈ＿ｃｅｌｌ（ｉ））が、もし前記ロケーションがリストの終わりでなければ、そのリストの中で、そこから続いているセルメモリの他のロケーションを指定する継続ポインタ（Ｐｔｒ＿ｃｏｎｔ（ｉ））と組み合わされている請求項２に記載のスペーサ。
【請求項４】
前記ポインタメモリ（４３）が、各仮想接続に対して、もし前記接続に関連する少なくとも１つのセルが前記セルメモリ（４２）に含まれていれば、前記接続に対応するロケーションのリストの始めとリストの終わりをそれぞれ指定するリスト開始ポインタ（Ｐｔｒ＿ｓｔａｒｔ）およびリスト終了ポインタ（Ｐｔｒ＿ｅｎｄ）を含む請求項３に記載のスペーサ。
【請求項５】
優先権インデックス（ｕ）が仮想接続に割り当てられ、前記ソーティング手段がそれぞれ同様の優先権インデックスの仮想接続の識別情報を有するデータ要素を処理し、またそれが処理するデータ要素の中から最小のソートキー（Ｋ(u)（１））を有する要素を選択するいくつかのソーティング装置（４４(u)）を有し、前記スペーシング制御手段は、最小のソートキーを示す選択されたデータ要素の１つに、あるいは、いくつかのソーティング装置がそれぞれソートキーが最小であるデータ要素を選択するならば、これらのソーティング装置により選択された、優先権インデックスが最高であるデータ要素の１つにおける識別された接続に関連するリストの始めに含まれているセルの送出を命令するように構成されている請求項１から４までのいずれか１項に記載のスペーサ。
【請求項６】
種々のソーティング装置の各々が、それぞれの記憶手段（２０q（１）、２０q（２））を有し、またその制御手段（２１q、２６q）を共有する請求項５に記載のスペーサ。
【請求項７】
前記ソーティング手段が、それぞれデータ要素を含むことが可能であり、０からｎまで番号を付けられたｎ個の連続したステージに分配され、ステージｑはノード２qから２q+1−１を有する、１から２n−１まで番号を付けられた２n−１個のノードを有するバイナリーツリーにしたがって構成された記憶手段（２０0−２０n-1）と、
１から２n-1−１の間の各整数ｉに対して、ノードｉは分類されるべき要素を含み、ノード２iおよび２i+1のそれぞれは分類されるべき要素を含まないか、あるいはソートキーがノードｉに含まれている要素のソートキーよりも大きいかまたはそれに等しい要素を含むように、順序付けの条件を満足するように、ツリーの中でソートされる要素を分散させるバイナリーツリーの制御手段（２１0−２１n-1）と
を有するソーティング装置（４４）を少なくとも１つ有し、前記バイナリーツリーの制御手段はソートされる新しい要素を挿入するためのコマンドを含むバイナリーツリーの内容を修正するコマンドに応答する、請求項１から６までのいづれか１項に記載のスペーサ。
【請求項８】
前記バイナリーツリーの制御の手段が、それぞれステージ（２０q）あるいはバイナリーツリーの複数の連続したステージと組み合わされた、２からｎの間の整数であるｍ個の連続したコントローラ（２１q）と、連続したステージ間のｎ−１個のインタフェース・レジスタ（２６q）を有し、それらのうち異なるコントローラと組み合わされたステージ対の間のｍ−１個のインタフェース・レジスタの各々はパイプラインレジスタを構成し、バイナリーツリーの内容を修正するための各コマンドがステージ０からステージｎ−１へ前記インタフェース・レジスタによって伝搬され、前記パイプラインレジスタが前記コントローラの並行動作を許容する請求項７に記載のスペーサ。
【請求項９】
１からｎ−１の間の各整数ｑに対して、ステージｑ−１とステージｑの間のインタフェース・レジスタ（２６q）が、ステージｑ−１のノードからステージｑのノードへ伝搬されるコマンド（Ａq）を受信するための第１のロケーションと、関連するコントローラ（２１q-1）が前記コマンドの処理の間にアクセスするステージｑ−１の前記ノードの識別情報（Ｄq）を受信するための第２のロケーションと、ステージｑ−１の前記ノードからあるいはステージｑ−１の前記ノードへ送信されるデータ要素（Ｂq、Ｃq）を受信するための第３のロケーションを有する請求項８に記載のスペーサ。
【請求項１０】
１からｎ−１の間の各整数ｑに対して、ステージｑ−１とステージｑの間のインタフェース・レジスタ（２６q）が、第２のロケーションに含まれる識別情報（Ｄq）により、もしこのコマンドがツリーの中への新しい要素の挿入を示しているならば、前記コマンドが伝搬され、また対応するコントローラ（２１q）が第１のロケーションに含まれるコマンドの処理の間にアクセスするステージｑのノードを指定するビット（Ｅq）を受信するための第４のロケーションを有する請求項９に記載のスペーサ。
【請求項１１】
１からｎ−１の間の各整数ｑに対して、ステージｑ−１とステージｑの間のインタフェース・レジスタ（２６q）の第２および第４のロケーションが、新しい要素を挿入するためのコマンドの伝搬の間に、空きの葉の数のｎ−１個の最下位ビットを含むｎ−１ビットの葉指定フィールド、すなわち、それに向かって前記コマンドが伝搬されるステージｎ−１の空きのノードの一部を形成し、前記コマンドが伝搬されるステージｑのノードは葉指定フィールドの内容のｑ個の最高位のビットにより指定される請求項１０に記載のスペーサ。
【請求項１２】
ツリーのステージｎ−１と組み合わされたコントローラ（２１n-1）が、各葉に向かって、新しい要素を挿入するためのコマンドが現在ツリーの中で伝搬されつつある各々の葉を含む空きの葉の指定された数ｎ'を含む空き葉の第１のリストと、第１のリストに含まれていない空きの葉を含む空きの葉の第２のリストを管理し、
ステージ０と１の間のインタフェース・レジスタの第１のロケーションにソートされる新しい要素を挿入するためのコマンドを登録する間に、各葉に向かってツリーの中で他の挿入コマンドが現在伝搬されつつある前記各葉と異なった、第１のリストの空きの葉の数のｎ−１個の最下位ビットがステージ０と１の間のインタフェース・レジスタの葉指定フィールドの中に登録され、
ツリーの葉からの要素の抽出の間は、前記葉は空きの葉の第２のリストに含まれ、
新しい要素を挿入するためのコマンドがステージｎ−２とｎ−１の間のインタフェース・レジスタ（２６n-1）の中のステージｎ−１に到達する時、組み合わされたコントローラ（２１n-1）は空きの葉の第１のリストから前記インタフェース・レジスタの葉指定フィールドのｎ−１個のビットにより指定された葉（Ｇn-1）を除去し、それを第２のリストからの葉と置換する請求項１１に記載のスペーサ。
【請求項１３】
ｎ'＜ｎである請求項１２に記載のスペーサ。
【請求項１４】
空きの葉の第１のリストが、それぞれ葉の数のｎ−１個の最下位ビットを受信するｎ'個のロケーションを有するそれ自身ループバックされるシフト・レジスタ（３０）に記憶される請求項１２または１３に記載のスペーサ。
【請求項１５】
空きの葉の第２のリストが後入れ先出し形式でポインタの連鎖の形で記憶され、各ポインタは葉の数を表し、前記連鎖の第１のポインタ（Ｐ）は特定のロケーションに記憶され、前記連鎖のｉ番目のポインタ（ｉ≧２）は番号が前記連鎖のｉ−１番目のポインタで表される葉に記憶されている請求項１２、１３または１４に記載のスペーサ。
【請求項１６】
前記第１および第２のリストが少なくともｎ'個のロケーションを有する先入れ先出し型式の論理待ち行列の形式で記憶され、第１のリストは、前記論理待ち行列の最後のｎ'個のロケーションと前記論理待ち行列の先行するロケーションの第２のリストからなる請求項１２または１３に記載のスペーサ。
【請求項１７】
ｐが、ｍ番目のコントローラと組み合わされているバイナリーツリーのステージの数であって１以上ｎ−１未満であり、前記記憶手段がｉが１から２n-p-1−１の範囲であるツリーのノード２iと２i+1の対とそれぞれ組み合わされた差分カウンタ（Δ（ｉ））を含むための少なくとも２n-p-1−１個のロケーション（２５）を有し、データ要素の数の間の差を示す値を有する一対のノードと組み合わされた各差分カウンタは前記対の２つのノードの子孫にそれぞれ含まれ、ステージｑのノードｉの子孫は、数がｉ２j＋ｊ'の形である（ここで、ｊおよびｊ'は０≦ｊ＜ｎ−ｑおよび０≦ｊ'＜２ｊのような整数）バイナリーツリーの２n-q−１個のノードと規定されており、
ステージｑ−１とステージｑ（ｌ≦ｑ＜ｎ−ｐ）の間のインタフェース・レジスタ（２６q）が、新しい要素をその第１のロケーションに、またステージｑ−１のノードｉの識別情報（Ｄq）をその第２のロケーションに挿入するためのコマンド（Ａq）を受信すると、ノード２iと２i+1の対と組み合わされた差分カウンタ（Δ（ｉ））の値に応じて前記挿入コマンドがステージｑのノード２iあるいは２i+1に伝搬される請求項１１または１２に記載のスペーサ。
【請求項１８】
ステージのノードの対と組み合わされた差分カウンタ（Δ（ｉ））を含む記憶手段のロケーション（２５）が、前記ステージのノードと同じコントローラによりアクセス可能である請求項１７に記載のスペーサ。
【請求項１９】
前記記憶手段が、ｉが１から２n-1−１の範囲である、ツリーのノード２iと２i+1の対とそれぞれ組み合わされたステアリングビット（Ｆ（ｉ））を含むための２n-1−１個のロケーション（２３）を有し、前記対のノードの１つを指す一対のノードと組み合わされた各ステアリングビットは、ソートキーが前記対のノードの他の１つに含まれる要素のソートキー以下である要素を含み、
ステージｑ−１とステージｑ（１≦ｑ≦ｎ−１）の間のインタフェース・レジスタ（２６q）が、その第１のロケーションにおいて要素を抽出あるいは交換するためのコマンド（Ａq）を、またその第２のロケーションにおいてステージｑ−１のノードｉの識別情報（Ｄq）を受信すると、前記抽出あるいは交換コマンドが、ノード２iと２i+1の対と組み合わされたステアリングビット（Ｆ（ｉ））の値に応じて、ステージｑのノード２iあるいは２i+1に伝搬される請求項１１から１８までのいづれか１項に記載のスペーサ。
【請求項２０】
１つのステージのノードの対と組み合わされたステアリングビット（Ｆ（ｉ））を含む記憶手段のロケーション（２３）が、前記ステージのノードと同じコントローラによってアクセス可能である請求項１９に記載のスペーサ。
【請求項２１】
前記バイナリーツリーの制御手段が、バイナリーツリーの１つのステージ、あるいはいくつかの連続したステージと組み合わされた２つの連続したコントローラ（２１o、n-p、２１n-p、p）と、連続したステージ間のｎ−１個のインタフェースを有し、それらのステージのうちのそれぞれ２つのコントローラと組み合わされた２つの連続したステージの間のインタフェース・レジスタ（２６n-p）が２つのコントローラの並行動作を許容するパイプラインレジスタを構成し、前記スペーシング制御手段および前記バイナリーツリーの制御手段は、ソートされるべき新しいデータ要素を挿入するためのコマンドが第１のフェーズにおいて第２のコントローラにより、および第２のフェーズにおいて第１のコントローラにより処理され、ツリーの中のデータ要素を抽出あるいは交換するためのコマンドは第１のフェーズにおいて第１のコントローラにより、および第２のフェーズにおいて第２のコントローラにより処理されるように、各セル期間を第１のフェーズ（Ｉ）と第２のフェーズ（ＩＩ）に分割するように構成され、挿入コマンドはインタフェース・レジスタによってステージｎ−１からステージ０まで伝搬され、抽出あるいは交換コマンドはインタフェース・レジスタによってステージ０からステージｎ−１まで伝搬される請求項７に記載のスペーサ。
【請求項２２】
ステージ０と組み合わされている第１のコントローラがスペーシング制御手段の一部を少なくとも構成している請求項８から２１までのいずれか１項に記載のスペーサ。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１８
【補正方法】変更
【補正の内容】
【００１８】
【課題を解決するための手段】
本発明は、複数の仮想接続にしたがって送信されるＡＴＭセルのスペーサであって、
着信セルが書き込まれ、発信セルが読み取られるセルメモリと、
少なくとも前記セルの到着時刻と仮想接続に割り当てられたスペーシング間隔とを含むパラメータに基づいて、仮想接続に関連する各セルに対する理論的送出時間の回帰的な計算をする手段を有するセルメモリに蓄積された各セルに理論的送出時間を割り当てるための手段と、
セルメモリがセルを収容している各仮想接続に対して、前記セルがリストの開始とリストの終わりの間で先入れ先出しモードで蓄積されるロケーションのリストをセルメモリが有するような方法による関連するポインタメモリにより、セルメモリを管理するためのスペーシング制御手段と、
それぞれ仮想接続特性と、前記仮想接続に関するリストの開始に含まれているセルの理論的送出時間から成るソートキーを有する、データ要素を順序づけ、最小のソートキーを有する少なくとも一つのデータ要素を選択するためのソーティング手段とを有し、
スペーシング制御手段は、ソーティング手段により選択されたデータ要素において識別された仮想接続に関するリストの開始に含まれたセルの送出を命令するように工夫されている、複数の仮想接続に応じて送信されるＡＴＭセルのスペーサを提供する。