ソート装置及び方法
ユニットを所定の順序に従ってユニット記憶構造にソートするためのソート装置及び方法であり、ソート装置が、ユニット記憶構造内のユニットのレコードを含むユニットサーチ構造と、ユニット記憶構造内のユニットの位置ポインタを含むユニット位置ポインタ構造とを備え、ソート装置が、ソートされるユニットを受信し、ユニットサーチ構造が、ソートされるユニットを読み出し、ユニット記憶構造内のユニットのそのレコードを使用して、ソートされるユニットに最も近く一致するユニットをサーチし、ユニット位置ポインタ構造にアクセスし、最も近く一致するユニットの位置ポインタを取り出し、ソート装置が、最も近く一致するユニットの位置ポインタを使用して、ユニット記憶構造にアクセスし、ユニット記憶構造にソートされるユニットを、所定の順序による適切な位置に置く。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ソート装置及び方法に関し、詳細には、限定的ではないが、通信ネットワーク内でパケットのタグをソートするためのソート装置及び方法に関する。
【背景技術】
【０００２】
個々のユニットをある順序、たとえば昇順又は降順にソートすることが望ましい多くの適用例がある。こうした適用例は、パケット交換通信網である。パケット交換通信網は、ネットワークを介して伝播されるデータをパケットに分割することによって動作する。それらのパケットは、ネットワークを介して別々に伝播される。ルータなどのネットワークのノード上では、ノードの多くの異なる入力からのパケットをノードの単一の出力に伝播する必要があることは、よくあることである。これは、パケットキューイング、及びパケット伝播競合をもたらし、それによって、パケットの処理（ｓｅｒｖｉｃｅ）のスケジューリング、たとえばパケットを処理する順序の決定が必要になる。従来、これは、各パケットにタグを割り当て、タグ、したがってパケットの処理がスケジューリングされるべき順序を決定することによって達成される。たとえば、多くの場合、タグを昇順に処理すると決定される。次いで、より高いスケジューリング優先度を有するパケットにはより低いタグ値が割り当てられ、より低いスケジューリング優先度を有するパケットにはより高いタグ値が割り当てられるように、スケジューリングポリシーを使用してタグの値が計算される。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
タグを昇順に処理するには、最低の値を有するタグのサーチの繰返し、又はタグを昇順にソートし、順序の先頭のタグの読出しを繰り返すことを必要とする。それぞれの技術の様々な方法が使用されてきた。しかし、特に、通信ネットワークの使用及び所望の速度は増加し続けており、パケットスケジューリングがこれまで以上に重要になるので、ソート技術の向上が望ましい。
【課題を解決するための手段】
【０００４】
本発明の第１の態様によれば、ユニットを所定の順序に従ってユニット記憶構造にソートするためのソート装置が提供され、ユニット記憶構造内のユニットのレコードを含むユニットサーチ構造と、ユニット記憶構造内のユニットの位置ポインタを含むユニット位置ポインタ構造とを備え、ソート装置が、ソートされるユニットを受信し、ユニットサーチ構造が、ソートされるユニットを読み出し、ユニット記憶構造内のユニットのそのレコードを使用して、ソートされるユニットに最も近く一致するユニットをサーチし、ユニット位置ポインタ構造にアクセスし、最も近く一致するユニットの位置ポインタを取り出し、ソート装置が、最も近く一致するユニットの位置ポインタを使用して、ユニット記憶構造にアクセスし、ユニット記憶構造にソートされるユニットを所定の順序による適切な位置に置く。
【０００５】
ユニット位置ポインタ構造の使用は、ユニットサーチ構造が、ユニット記憶構造に直接アクセスする必要がないことを意味する。サーチ構造と記憶構造は、互いに分離される。これによって、ソート装置のためにより柔軟な設計を採用することが可能になる。さらに、ソート装置にこの構成を使用すると、この装置のソート機能を、ユニット記憶構造からのユニットの取出しとは別々に実施することが可能となる。これによって、ユニットの取出しを依然として可能にしながら、記憶構造の容量が柔軟なままであることが可能となる。
【０００６】
ユニットサーチ構造は、ツリーサーチ構造を備えてもよい。ツリーサーチ構造は、マルチビットツリーサーチ構造を備えてもよい。マルチビットツリーサーチ構造を使用すると、ツリー構造の圧縮が可能となり、サーチ構造の速度が増す。ツリーサーチ構造は、複数のサーチレベルを備えてもよい。ツリーサーチ構造は、少なくとも１つのノードを備える第１のサーチレベルを具備してもよい。ツリーサーチ構造は、前のサーチレベルのノードにリンクされた１つ又は複数のノードをそれぞれが含む、１つ又は複数のさらなるサーチレベルを備えてもよい。ノードの少なくとも一部は、ユニット記憶構造内のユニットのレコードを含んでもよい。ノードはそれぞれ、１つ又は複数のビットを備えてもよい。ノードのビットの少なくとも一部は、ユニット記憶構造内のユニットのレコードを含んでもよい。
【０００７】
ツリーサーチ構造は、ソートされるユニットの少なくとも１つのセグメントを、１つ又は複数のサーチレベルの少なくとも１つのノードと比較して、そのセグメント又は各セグメントに最も近い一致を見つけ、したがって、ソートされるユニットに最も近く一致するユニットを見つけることによって、最も近く一致するユニットをサーチしてもよい。たとえば、ツリーサーチ構造は、ソートされるユニットの第１のセグメントを、ツリーサーチ構造の第１のサーチレベルのノードと比較して、第１のセグメントに最も近い一致、及び第１のサーチレベルのノードがリンクされているツリーサーチ構造の第２のサーチレベル内のノードを見つけ、ソートされるユニットの第２のセグメントを、第２のサーチレベルのノードと比較して、第２のセグメントに最も近い一致、及び第２のサーチレベルのノードがリンクされているツリーサーチ構造の第３のサーチレベル内のノードを見つけ、ソートされるユニットの第３のセグメントを、第３のサーチレベルのノードと比較して、第３のセグメントに最も近い一致、したがって、ソートされるユニットに最も近いユニットを見つけることによって、最も近く一致するユニットをサーチしてもよい。
【０００８】
ツリーサーチ構造は、ユニット記憶構造内のユニットのそのレコードを更新してもよい。これは、ユニットがソートされた後に実施されてもよい。これは、ユニットがソートされる間に実施されてもよい。
【０００９】
ユニット位置ポインタ構造は、ソート装置によってユニット記憶構造にソートされ得る各ユニットの位置ポインタの位置を備えてもよい。位置は、ユニットがソート装置によってユニット記憶構造にソートされている場合、そのユニットの位置ポインタを含んでもよい。ソート装置は、ユニットがソートされた後、ユニットの位置ポインタを、ユニット位置ポインタ構造内に置いてもよい。ユニット位置ポインタ構造は、ルックアップテーブルを備えてもよい。ユニット位置ポインタ構造は、ユニットサーチ構造にリンクされてもよい。ユニット位置ポインタ構造は、それがユニットサーチ構造のツリーサーチ構造の最下位レベルを有効に備えるように、ユニットサーチ構造にリンクされてもよい。
【００１０】
ソート装置は、ユニットを所定の順序にソートするために、ユニットソートポリシーを操作してもよい。順序は、ユニット値の昇順であってもよい。順序は、ユニット値の降順であってもよい。
【００１１】
ソート装置は、ユニットサーチ構造及びユニット位置ポインタ構造のための分散メモリアーキテクチュアを含んでもよい。具体的には、ユニットサーチ構造及びユニット位置ポインタ構造のツリーサーチ構造の各サーチレベルは、それぞれ独立にアクセス可能なメモリアーキテクチュアを備えてもよい。メモリアーキテクチュアは、互いに独立に書き込まれ、又は読み出され得る。これによって、ソート装置のための並列パイプライン構造が提供される。これは、ユニットサーチ構造のサーチ、及びソート装置のソートの速度を増加させる。ソート装置は、クロックのサイクルに従って動作してもよい。メモリアーキテクチュアは、各クロックサイクル内に一度だけアクセス可能であってもよい。ユニットサーチ構造及びユニット位置ポインタ構造のツリーサーチ構造のサーチレベルについてそれぞれ独立にアクセス可能なメモリアーキテクチュアを使用すると、ソート装置が各クロックサイクル内で、最も近く一致するユニットの位置ポインタを取り出すことが可能となる。ユニットサーチ構造及びユニット位置ポインタ構造のツリーサーチ構造のサーチレベルについてそれぞれ独立にアクセス可能なメモリアーキテクチュアを使用すると、ソート装置が各クロックサイクル内でユニットをソートすることが可能となる。これは、ユニット記憶構造内にユニットを置くことが１クロックサイクル内で実施される場合に当てはまる。
【００１２】
特に、ユニットサーチ構造及びユニット位置ポインタ構造のツリーサーチ構造の各サーチレベルについてそれぞれ独立にアクセス可能な４つのメモリアーキテクチュアを備えた、ユニットサーチ構造及びユニット位置ポインタ構造用の分散型のメモリアーキテクチュアを使用すると、ソート装置のスループット速度は増加するが、装置の複雑さ及びコストも増加する。ユニットサーチ構造及びユニット位置ポインタ構造用に他の数のメモリアーキテクチュアが使用され得ることが理解されよう。たとえば、１つのメモリアーキテクチュアだけが、ユニットサーチ構造及びユニット位置ポインタ構造用に使用されてもよく、或いは２つ又は３つのメモリアーキテクチュアが、ユニットサーチ構造及びユニット位置ポインタ構造用に使用されてもよい。使用するメモリアーキテクチュアの数を選択する際には、ソート装置の速度とソート装置のコストの間のトレードオフが行われなければならない。
【００１３】
ソート装置は、ハードウェアベースであってもよい。ソート装置は、システムオンチップ（ＳｏＣ：ｓｙｓｔｅｍ ｏｎ ｃｈｉｐ）技術を使用した実装によるハードウェアベースのものであってもよい。ソート装置は、ユニットサーチ構造及びユニット位置ポインタ構造用のＳｏＣメモリアーキテクチュアを備えてもよい。ユニットサーチ構造のＳｏＣメモリアーキテクチュアは、ＲＡＭメモリのブロックを備えてもよい。ユニットサーチ構造がツリーサーチ構造を含む場合、ツリーサーチ構造の第１のサーチレベル及び第２のサーチレベルは、複数のレジスタを備えてもよく、ツリーサーチ構造のさらなるサーチレベルはそれぞれ、ＲＡＭメモリのブロックを備えてもよい。
【００１４】
ユニット記憶構造は、ソート装置とは別々に提供されてもよい。或いは、ソート装置は、ユニット記憶構造を備えてもよい。ユニット記憶構造は、リンクリストを備えてもよい。リンクリスト内に格納されたユニットは、所定の順序になるように互いにリンクされてもよい。各ユニットについては、ユニット記憶構造は、ユニットに関連する１つ又は複数の要素をさらに格納してもよい。ユニット記憶構造にリンクリストを使用すると、ソートされ得るすべての可能なユニットのためのメモリを取っておくのではなく、ユニットがソートされるときにユニットへの必要に応じてメモリを使用することが可能となる。これは、それによってメモリ管理及びメモリ割当ての制御が非常に単純化されるので特に有用であり、またユニット記憶構造が、他の装置によって共有されているメモリで実装される場合にも有益であり得る。
【００１５】
ユニットをソートするために単一のソート装置が使用されてもよい。或いは、複数のソート装置が、ユニットをソートするために併せて使用されてもよい。それぞれのソート装置が、クロックのサイクルに従って動作してもよい。複数のソート装置を併せて使用すると、ユニットを各クロックサイクル内でソートすることが可能となる。たとえば、４つのソート装置が、ユニットをソートするために併せて使用されてもよい。ユニットは、４つの別個のユニット記憶構造、各ソート装置について１つのユニット記憶構造にソートされてもよい。ユニットをユニット記憶構造に置くことが４クロックサイクル内で実施される場合、４つのソート装置を併せて使用すると、ユニットを各クロックサイクル内でソートすることが可能となる。
【００１６】
ソート装置は、通信ネットワークのパケットのタグをソートしてもよい。ソート装置は、パケットのタグをソートするために、タグソートポリシーを操作してもよい。タグは、タグ計算回路によって計算されてもよい。タグ計算回路は、タグを計算するために、パケットスケジューリングポリシーを操作してもよい。パケットスケジューリングポリシーは、たとえば、公平キューイングポリシーのファミリーのいずれか、たとえば重み付き公平キューイングポリシーを備えてもよい。
【００１７】
ソート装置は、パケットスケジューラの一部を備えてもよい。スケジューラのソート装置は、通信ネットワークのルータの一部を備えてもよい。
【００１８】
本発明の第２の態様によれば、ユニット記憶構造内のユニットのレコードを含むユニットサーチ構造と、ユニット記憶構造内のユニットの位置ポインタを含むユニット位置ポインタ構造とを備えるソート装置を使用して、ユニットを所定の順序に従ってユニット記憶構造にソートする方法が提供され、ソート装置が、ソートされるユニットを受信するステップと、ユニットサーチ構造が、ソートされるユニットを読み出し、ユニット記憶構造内のユニットのそのレコードを使用して、ソートされるユニットに最も近く一致するユニットをサーチし、ユニット位置ポインタ構造にアクセスし、最も近く一致するユニットの位置ポインタを取り出すステップと、ソート装置が、最も近く一致するユニットの位置ポインタを使用して、ユニット記憶構造にアクセスし、ユニット記憶構造にソートされるユニットを所定の順序による適切な位置に置くステップとを含む。
【００１９】
本発明の第３の態様によれば、本発明の第１の態様によるソート装置を備える、通信ネットワークのためのスケジューラが提供される。
【００２０】
次に、本発明の一実施形態について、例示するためだけに、添付の図面を参照して述べる。
【発明を実施するための最良の形態】
【００２１】
図１に示されたソート装置１は、ユニットサーチ構造２、ユニット位置ポインタ構造３、及びユニット記憶構造４をも備える。しかし、ユニット記憶構造は、ソート装置の外部に設けられてもよいことが理解されよう。
【００２２】
ユニットサーチ構造は、マルチビットツリーサーチ構造を備え、このマルチビットツリーサーチ構造は、示されるように、３つのサーチレベル５を備え、各レベルが１つ又は複数のノード６を備える。ツリーサーチ構造は、より多い又は少ないサーチレベル、また各レベル内により多い又は少ないノードを備え得ることが理解されよう。このツリーサーチ構造は、２ビットの長さを有するユニットセグメントを使用して、６ビットの長さを有するユニットをソートする。本発明はこのツリーサーチ構造に限定されないが、それぞれ異なる長さのユニットをソートするためのツリーサーチ構造を包含することが再び理解されよう。ツリーサーチ構造２の３つのサーチレベル５の各ノード６は、４ビットを、各ユニットセグメントオプション００、０１、１０又は１１について１ビットを備える。レベルのノードのビットは、装置によってユニット記憶構造にソートされたユニットのレコードを含むために使用される。ビットのユニットセグメントオプションに対応するユニットセグメントが装置によって以前にソートされていない場合は、ビットは、０を含む。ビットのユニットセグメントオプションに対応するユニットセグメントが装置によって以前にソートされている場合は、ビットは、１を含む。第１及び第２のサーチレベルに１を含むノードのビットは、ツリーサーチ構造内のそれより下のレベルで、ノード、子ノードにリンクされる。
【００２３】
ツリーサーチ構造は、メモリ内で実装される。構造の２つの第１のサーチレベルはレジスタからなり、第３のサーチレベルは、ＲＡＭのブロックからなる。２つの第１のサーチレベルは、これらのサーチレベルに必要なメモリの量が比較的小さく、レジスタを使用して実現され得るので、レジスタを使用して実装されてもよい。
【００２４】
ユニット位置ポインタ構造３は、ルックアップテーブルを備える。ソート装置によってユニット記憶構造にソートされ得る各ユニットについて、位置がテーブル内に提供されてもよい。ユニット位置ポインタ構造の位置は、そのユニットがソート装置によってユニット記憶構造にソートされている場合は、ユニットの位置ポインタを含む。各ユニットについて、位置ポインタは、ユニット記憶構造内のユニットの位置を示す。ユニット位置ポインタ構造は、メモリ内で実装され、ＲＡＭのブロックを含む。ユニットサーチ構造及びユニット位置ポインタ構造は、ユニット位置ポインタ構造がユニットサーチ構造のツリーサーチ構造の第４のサーチレベルを有効に形成するようにリンクされる。
【００２５】
ユニット記憶構造４は、リンクリストを含む。リンクリストは、メモリ内で実装される。リンクリスト内のユニットは、メモリ全体にわたってランダムに分散されてもよい。リンクリスト内に格納されたユニットは、所定の順序になるように互いにリンクされる。リンクリストの各エントリは、ユニットと、リスト内の後続のユニットへの位置ポインタとを含む。ソート装置のこの実施形態では、リンクリストは、ユニットサーチ構造２及びユニット位置ポインタ構造３を備えたチップ内に含まれる。しかし、リンクリストは、たとえば外部デュアルポートＲＡＭ上で、オフチップで実装されてもよい。
【００２６】
ソート装置は、以下のように動作する。ユニットがユニット記憶構造にソートされる所定の順序を決定する、ユニットソートポリシーが選択される。この実施形態では、所定の順序は、ユニットの昇順である。しかし、ユニットの他の順序、たとえば降順が選択され得ることが理解されよう。
【００２７】
ソートされるユニットは、ソート装置１によって受信され、ユニットサーチ構造２によって読み出される。ユニットサーチ構造によって読み出される各ユニットについて、ユニットの値に基づいて、復号手順が、ツリーサーチ構造の３つのサーチレベル５のそれぞれで実施される。この手順は、ユニットサーチ構造内に含まれるこれらのユニットのレコードを使用して、ユニット記憶構造内の最も近く一致するユニットをサーチする。たとえば、１１０１１０の値を有するユニットに最も近く一致するユニットを見つけるために、２つの第１のビット、１１を備えるユニットセグメントが、ツリーサーチ構造の第１のサーチレベルのノードと比較される。このノード内の第４のビットは、ユニットセグメントオプション１１に関連する。第４のビット内に１が存在する場合は、これは、１１で始まるユニットが装置によって既にソートされており、ノードの第４のビットがそれより下のサーチレベル、すなわちツリーサーチ構造の第２のサーチレベルのノードにリンクされることを示す。ユニットの、次の２つのビット、０１を備えるユニットセグメントが、第２のサーチレベルのノードと比較される。このノードの第２のビットが１を含む場合は、これは、１１０１で始まるユニットが以前に装置によってソートされており、このノードの第２のビットがそれより下のサーチレベル、すなわちツリーサーチ構造の第３のサーチレベルのノードにリンクされることを示す。（第２のビットが０を含む場合は、ユニットセグメント０１にできるだけ近い一致、及び第３サーチレベルの対応するノードを見つけるために第２のサーチレベルのノード内の４ビットがスキャンされる。）ユニットの、最後の２ビットを備えるユニットセグメントは、第３のサーチレベル内のノードと比較される。このノードの第３のビットは、現在ソートされているユニットとまさに同じユニットを装置が既にソートしている可能性が低いので、通常０を含む。ユニットセグメント１０にできるだけ近い一致を見つけるために、第３のサーチレベルのノード内の４つのビットがスキャンされる。これは、たとえば、０１であり得る。次いで、ソートされるユニットに最も近く一致するユニットは、１１０１０１である。
【００２８】
ツリーサーチ構造の第３のサーチレベルの各ノードは、ユニット位置ポインタ構造内の４つのエントリ、ユニットセグメントオプション、００、０１、１０及び１１のそれぞれについて１つのエントリにリンクされる。ユニット位置ポインタ構造は、ユニット記憶構造内のユニットの位置へのポインタを含む。この実施例では、ユニット１１０１１０は、以前にソートされておらず、ユニット位置ポインタ構造内のこのユニットの場所は空である。最も近く一致するユニットが１１０１０１であると決定される。ソート装置は、このユニットについてユニット位置ポインタ構造内の位置にアクセスし、ユニット記憶構造内のこのユニットの位置を読み出す。
【００２９】
この時点で、ソートされるユニットは、リンクリストユニットの記憶構造内に、所定の順序、すなわちこの実施例では昇順による正確な位置に容易に挿入することができる。ソート装置は、ソートされるユニットについてリンクリスト内の記憶位置を要求し、この位置にユニットを格納する。ソート装置は、最も近く一致するユニット１１０１０１の位置ポインタを使用して、リンクリスト内のこのユニットの位置にアクセスし、この位置から、リンクリスト内の後続のユニットの位置ポインタを読み出す。ソート装置は、ユニット１１０１０１の位置の位置ポインタを、ソートされるユニットのリンクリスト内に位置を指すように変更する。またソート装置は、最も近く一致するユニットの位置からそれが読み出した、リンクリスト内の後続のユニットの位置ポインタを、ソートされるユニットのリンクリストの位置に挿入する。したがって、ソートされるユニットは、リンクリストユニット記憶構造内に、ユニットの昇順による位置に置かれる。
【００３０】
ユニットサーチ構造に含まれた、ユニット記憶構造内のユニットのレコードが更新される。これは、ユニットがソートされた後に、或いはユニットに最も近く一致するユニットをサーチする間に行うことができる。ユニットの各セグメントについて、ツリーサーチ構造の第１、第２及び第３のサーチレベルの適切なノードの適切なビット内に、１が置かれる。上記に示された実施例では、第１のサーチレベルのノード内の第４のビットに１が置かれ、第２のサーチレベルでアクセスされたノード内の第２のビットに１が置かれ、第３のサーチレベルでアクセスされたノード内の第３のビットに１が置かれる。ソートされた各ユニットについて、ソート装置は、ユニット位置ポインタ構造内に、ユニットのユニット記憶構造内の位置へのポインタを置く。
【００３１】
ユニットサーチ構造のマルチビットツリーサーチ構造及びユニット位置ポインタ構造は、分散メモリアーキテクチュアを使用して実装される。ツリーサーチ構造及びユニット位置ポインタ構造の３つのサーチレベルは、それぞれ独立にアクセス可能なメモリアーキテクチュア内に保持される。ツリーサーチ構造及びユニット位置ポインタ構造のレベルは、互いに独立に書き込み、又は読み出すことができる。これによって、ソート装置の並列パイプライン構造が提供され、装置の動作速度が向上する。
【００３２】
上記説明は、ソート装置によってソートされる第２及び後続のユニットに当てはまる。ソートされるべきユニットが、装置によってソートされる第１のユニットである場合、異なる、第１のユニットソート手順を使用しなければならない。ソートされるべき第１のユニットが、ソート装置によって受信され、ユニットサーチ構造がアクセスされ、ツリーサーチ構造の第１のサーチレベルのノードのビットはそれぞれ、０を含む。これは、ソート装置に、第１のユニットソート手順を適用させる。第１のユニットは、それに割り当てられたリンクリストユニット記憶構造内に位置を有する。次いで、ユニットサーチ構造は、第１のユニットの第１のセグメントを読み出し、ツリーサーチ構造の第１のサーチレベルのノードの適切なビットに１を書き込み、第１のサーチレベルのノード内のビットにリンクされた第２のサーチレベルのノードに移動する。次いで、ユニットサーチ構造は、第１のユニットの次のセグメントを読み出し、第２のサーチレベルのノードの適切なビットに１を書き込み、第２のサーチレベルのノード内のビットにリンクされた第３のサーチレベルのノードに移動する。次いで、ユニットサーチ構造は、第１のユニットの最後のセグメントを読み出し、第３のサーチレベルのノードの適切なビットに１を書き込み、第１のユニットに割り当てられたユニット位置ポインタ構造内の位置に移動し、第１のノードに割り当てられたユニット記憶構造位置をユニット位置ポインタ構造内の位置に書き込む。次いで、ソート装置は、ユニット記憶構造内の事前に割り当てられた位置に第１のユニットを置くために、第１のユニットの位置ポインタを使用する。
【００３３】
ソート装置は、たとえば通信ネットワークの一部を備える場合、クロックサイクルに従って動作してもよい。これが当てはまる場合、特定のどんなメモリも、クロックサイクル当たり一度だけアクセスされ得るのが通常である。ツリーサーチ構造及びユニット位置ポインタ構造の３つのサーチレベルは、それぞれ独立にアクセス可能なメモリ位置内に保持され、したがって、３つのすべてのサーチレベル及びポインタ位置構造が、同じクロックサイクル内にアクセスされ得る。したがって、第１の３クロックサイクルの後、ソート装置は、各クロックサイクル内で、ソートされるユニットに最も近く一致するユニットの位置ポインタを取り出すことができる。したがって、ソート装置は、ユニット記憶構造内にユニットを置くのに１クロックサイクルしか必要でないならば、各クロックサイクル内でユニットをソートするであろう。しかし、リンクリストユニット記憶構造を備えるメモリは、ユニットをリンクリストに置くために、４回アクセスしなければならない。したがって、ユニットをリンクリスト内に置くには、４クロックサイクルを要する。したがって、４つのクロックサイクルごとにユニットがソート装置に入力され、そうでない場合は、最も近く一致するユニット位置ポインタが取り出され、リンクリスト内に置かれるべきユニットのキューが発生する。したがって、ソート装置は、４クロックサイクルごとにユニットをソートするにすぎない。３つの各サーチレベル、及び位置ポインタ構造は、４クロックサイクルごとにアクセスされるにすぎない。中間にある「冗長な」クロックサイクルは、メモリ位置がそれぞれ独立にアクセス可能であるために、同じクロックサイクル内に２つ以上のサーチレベル及び位置ポインタ構造にアクセスすることができるので、ツリーサーチ構造のビット、及び位置ポインタ構造内の位置ポインタを更新するために使用することができる。
【００３４】
ソート装置のアーキテクチュアは、ＶＨＤＬで実装され、Ｓｙｎｐｉｌｃｉｔｙ ａｎｄ Ｘｉｌｉｎｘ Ｆｏｕｎｄａｔｉｏｎツールを使用して、Ｘｉｌｉｎｘ Ｖｉｒｔｅｘ ＦＰＧＡ用に合成されている。８４ＭＨｚのクロック速度で、ソート操作当たり４クロックサイクルの場合、この実装形態は、４０Ｇｂｐｓで２５０Ｂの平均ユニットサイズをサポートすることができる。この回路実装にＳｏＣ技術を使用すると、１００Ｇｂｐｓを超過する速度の達成が可能となり得る。
【００３５】
ユニットをソートするために、単一のソート装置が使用されてもよい。或いは、複数のソート装置が、ユニットをソートするために併せて使用されてもよい。たとえば、４つのソート装置が、ユニットをソートするために併せて使用されてもよい。ユニットは、４つの別個のユニット記憶構造、各ソート装置について１つのユニット記憶構造にソートされる。（この場合、ユニットの取出しが必要な場合、各記憶構造の第１のユニットが読み出され、最低の値を有するユニットが取り出される。）それぞれのソート装置は、クロックのサイクルに従って動作してもよい。上記のようにユニット記憶構造がリンクリストである場合、ユニットを記憶構造に置くのに４クロックサイクルを要する。したがって、それぞれのソート装置は、４つのクロックサイクルごとに１ユニットをソートし得るにすぎない。４つのソート装置を併せて使用すると、ユニットを各クロックサイクル内でソートすることが可能となる。
【００３６】
図２は、パケットベースの通信ネットワーク用のスケジューラの概略図を示している。スケジューラは、通信ネットワークのルータの一部を備える。ルータは、ネットワークを介して伝播されるデータパケットをルーティングするように働く。ルータは、ルータの複数の入力を介してパケットを受信し、この複数のパケットを、ルータの出力に伝播する必要がある。これによって、パケットの伝播のスケジューリングが必要となる。
【００３７】
こうしたスケジューリングは、スケジューラによって実施される。スケジューリングプロセスは、２つの段階、パケットスケジューリングポリシー機能及びパケット修理機能からなる。スケジューラ１０は、パケットスケジューリングポリシー機能を担うパケットスケジューリングポリシー回路１２と、パケット処理機能を担うパケット処理回路１４とを備える。
【００３８】
パケットスケジューリングポリシー回路１２は、スケジューラを介したパケットの伝播のスケジューリング、特に順序を決定するために使用されるパケットスケジューリングポリシーを操作する。スケジューリングポリシー回路は、スケジューリングポリシーに従って各パケットのタグを計算し、タグの値は、互い対してパケットのスケジューリングを決定するために使用される。通常、タグを昇順に処理するようにスケジューリングすることが決定される。次いで、タグの値は、スケジューリングポリシーを使用して、より低いタグ値が、より高いスケジューリング優先度を有するパケットに割り当てられ、より高いタグ値が、より低いスケジューリング優先度を有するパケットに割り当てられるように計算される。
【００３９】
パケットスケジューリングポリシー回路は、タグを計算するために使用されるタグ計算回路１６を備える。タグは、計算されると、パケット処理回路１４に渡される。
【００４０】
パケット処理回路１４によって受信されるタグは本質的に、ランダムな順序である。この理由は、ネットワーク内の単一のトラフィックフロー内のパケットは、フローに以前に割り当てられたタグよりも高くなっていくタグを受信するが、別個のトラフィックフローからのパケットは、タグを昇順には受信しないが、フローの特性、及びタグ計算回路によって操作されたスケジューリングポリシーに従って受信するからである。スケジューラは、複数のフローからパケットを受信し、したがって、計算されたタグ値は、特定の順序を有さない。タグが、タグ計算回路から受信される順序、すなわちランダムな順序で格納される場合、これは、関連するパケットの処理のための後続のタグ取出しに対して意味をもつ。通常、タグは、まず最低のタグから始めて、昇順に取り出され、これを容易にするために、タグは、パケット処理回路に到着するとすぐに昇順にソートされ、したがって順番に格納される。
【００４１】
パケット処理回路１４は、タグソート装置１８を備える。タグソート装置は、上述の図１のユニットソート装置と同じ構造を有する。タグソート装置１８は、タグサーチ構造と、タグ位置ポインタ構造と、タグ記憶構造とを備える。上述したように、ソートされるべきタグがタグサーチ構造によって受信される場合、最も近く一致する値のサーチが実施される。これによって、タグ位置ポインタ構造から、ソートされるタグに最も近く一致するタグ記憶構造内のタグに、位置ポインタが返される。次いで、ソートされるタグは、タグの昇順に従って、タグ記憶構造内の正確な位置に挿入される。したがって、タグソート装置は、タグを昇順にソートする問題への解決策を提供する。タグツリーサーチ構造及びタグ位置ポインタ構造のサーチレベルが、互いに独立に実装されるので、これによって、高速タグソート方法、及びマルチギガビット回線高速ネットワーク内のパケットスケジューリングが可能なスケジューラが提供される。
【００４２】
またスケジューラは、到着するタグのソートが行われている間、ルータからネットワークへと前方伝播を行うために、ソートされたタグを取り出し、それに関連するパケットをスケジューラの出力に転送している。ソートされたタグは、まず最も低いタグから始めて、昇順に取り出される。これは、タグがリンクリストの記憶構造内で昇順にソートされているので、リンクリストのタグ記憶構造の第１のエントリ内のタグを繰り返し読み出す単純なプロセスである。タグ記憶構造の各エントリは、タグ、及びタグに関連するパケットが格納された位置を示す位置ポインタをも含み、スケジューラ及びルータからの前方伝播のためにパケットを取り出すことを可能にする。
【図面の簡単な説明】
【００４３】
【図１】本発明の第１の態様によるソート装置の概略図である。
【図２】図１のソート装置を組み込む、本発明の第２の態様によるスケジューラの概略図である。
【技術分野】
【０００１】
本発明は、ソート装置及び方法に関し、詳細には、限定的ではないが、通信ネットワーク内でパケットのタグをソートするためのソート装置及び方法に関する。
【背景技術】
【０００２】
個々のユニットをある順序、たとえば昇順又は降順にソートすることが望ましい多くの適用例がある。こうした適用例は、パケット交換通信網である。パケット交換通信網は、ネットワークを介して伝播されるデータをパケットに分割することによって動作する。それらのパケットは、ネットワークを介して別々に伝播される。ルータなどのネットワークのノード上では、ノードの多くの異なる入力からのパケットをノードの単一の出力に伝播する必要があることは、よくあることである。これは、パケットキューイング、及びパケット伝播競合をもたらし、それによって、パケットの処理（ｓｅｒｖｉｃｅ）のスケジューリング、たとえばパケットを処理する順序の決定が必要になる。従来、これは、各パケットにタグを割り当て、タグ、したがってパケットの処理がスケジューリングされるべき順序を決定することによって達成される。たとえば、多くの場合、タグを昇順に処理すると決定される。次いで、より高いスケジューリング優先度を有するパケットにはより低いタグ値が割り当てられ、より低いスケジューリング優先度を有するパケットにはより高いタグ値が割り当てられるように、スケジューリングポリシーを使用してタグの値が計算される。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
タグを昇順に処理するには、最低の値を有するタグのサーチの繰返し、又はタグを昇順にソートし、順序の先頭のタグの読出しを繰り返すことを必要とする。それぞれの技術の様々な方法が使用されてきた。しかし、特に、通信ネットワークの使用及び所望の速度は増加し続けており、パケットスケジューリングがこれまで以上に重要になるので、ソート技術の向上が望ましい。
【課題を解決するための手段】
【０００４】
本発明の第１の態様によれば、ユニットを所定の順序に従ってユニット記憶構造にソートするためのソート装置が提供され、ユニット記憶構造内のユニットのレコードを含むユニットサーチ構造と、ユニット記憶構造内のユニットの位置ポインタを含むユニット位置ポインタ構造とを備え、ソート装置が、ソートされるユニットを受信し、ユニットサーチ構造が、ソートされるユニットを読み出し、ユニット記憶構造内のユニットのそのレコードを使用して、ソートされるユニットに最も近く一致するユニットをサーチし、ユニット位置ポインタ構造にアクセスし、最も近く一致するユニットの位置ポインタを取り出し、ソート装置が、最も近く一致するユニットの位置ポインタを使用して、ユニット記憶構造にアクセスし、ユニット記憶構造にソートされるユニットを所定の順序による適切な位置に置く。
【０００５】
ユニット位置ポインタ構造の使用は、ユニットサーチ構造が、ユニット記憶構造に直接アクセスする必要がないことを意味する。サーチ構造と記憶構造は、互いに分離される。これによって、ソート装置のためにより柔軟な設計を採用することが可能になる。さらに、ソート装置にこの構成を使用すると、この装置のソート機能を、ユニット記憶構造からのユニットの取出しとは別々に実施することが可能となる。これによって、ユニットの取出しを依然として可能にしながら、記憶構造の容量が柔軟なままであることが可能となる。
【０００６】
ユニットサーチ構造は、ツリーサーチ構造を備えてもよい。ツリーサーチ構造は、マルチビットツリーサーチ構造を備えてもよい。マルチビットツリーサーチ構造を使用すると、ツリー構造の圧縮が可能となり、サーチ構造の速度が増す。ツリーサーチ構造は、複数のサーチレベルを備えてもよい。ツリーサーチ構造は、少なくとも１つのノードを備える第１のサーチレベルを具備してもよい。ツリーサーチ構造は、前のサーチレベルのノードにリンクされた１つ又は複数のノードをそれぞれが含む、１つ又は複数のさらなるサーチレベルを備えてもよい。ノードの少なくとも一部は、ユニット記憶構造内のユニットのレコードを含んでもよい。ノードはそれぞれ、１つ又は複数のビットを備えてもよい。ノードのビットの少なくとも一部は、ユニット記憶構造内のユニットのレコードを含んでもよい。
【０００７】
ツリーサーチ構造は、ソートされるユニットの少なくとも１つのセグメントを、１つ又は複数のサーチレベルの少なくとも１つのノードと比較して、そのセグメント又は各セグメントに最も近い一致を見つけ、したがって、ソートされるユニットに最も近く一致するユニットを見つけることによって、最も近く一致するユニットをサーチしてもよい。たとえば、ツリーサーチ構造は、ソートされるユニットの第１のセグメントを、ツリーサーチ構造の第１のサーチレベルのノードと比較して、第１のセグメントに最も近い一致、及び第１のサーチレベルのノードがリンクされているツリーサーチ構造の第２のサーチレベル内のノードを見つけ、ソートされるユニットの第２のセグメントを、第２のサーチレベルのノードと比較して、第２のセグメントに最も近い一致、及び第２のサーチレベルのノードがリンクされているツリーサーチ構造の第３のサーチレベル内のノードを見つけ、ソートされるユニットの第３のセグメントを、第３のサーチレベルのノードと比較して、第３のセグメントに最も近い一致、したがって、ソートされるユニットに最も近いユニットを見つけることによって、最も近く一致するユニットをサーチしてもよい。
【０００８】
ツリーサーチ構造は、ユニット記憶構造内のユニットのそのレコードを更新してもよい。これは、ユニットがソートされた後に実施されてもよい。これは、ユニットがソートされる間に実施されてもよい。
【０００９】
ユニット位置ポインタ構造は、ソート装置によってユニット記憶構造にソートされ得る各ユニットの位置ポインタの位置を備えてもよい。位置は、ユニットがソート装置によってユニット記憶構造にソートされている場合、そのユニットの位置ポインタを含んでもよい。ソート装置は、ユニットがソートされた後、ユニットの位置ポインタを、ユニット位置ポインタ構造内に置いてもよい。ユニット位置ポインタ構造は、ルックアップテーブルを備えてもよい。ユニット位置ポインタ構造は、ユニットサーチ構造にリンクされてもよい。ユニット位置ポインタ構造は、それがユニットサーチ構造のツリーサーチ構造の最下位レベルを有効に備えるように、ユニットサーチ構造にリンクされてもよい。
【００１０】
ソート装置は、ユニットを所定の順序にソートするために、ユニットソートポリシーを操作してもよい。順序は、ユニット値の昇順であってもよい。順序は、ユニット値の降順であってもよい。
【００１１】
ソート装置は、ユニットサーチ構造及びユニット位置ポインタ構造のための分散メモリアーキテクチュアを含んでもよい。具体的には、ユニットサーチ構造及びユニット位置ポインタ構造のツリーサーチ構造の各サーチレベルは、それぞれ独立にアクセス可能なメモリアーキテクチュアを備えてもよい。メモリアーキテクチュアは、互いに独立に書き込まれ、又は読み出され得る。これによって、ソート装置のための並列パイプライン構造が提供される。これは、ユニットサーチ構造のサーチ、及びソート装置のソートの速度を増加させる。ソート装置は、クロックのサイクルに従って動作してもよい。メモリアーキテクチュアは、各クロックサイクル内に一度だけアクセス可能であってもよい。ユニットサーチ構造及びユニット位置ポインタ構造のツリーサーチ構造のサーチレベルについてそれぞれ独立にアクセス可能なメモリアーキテクチュアを使用すると、ソート装置が各クロックサイクル内で、最も近く一致するユニットの位置ポインタを取り出すことが可能となる。ユニットサーチ構造及びユニット位置ポインタ構造のツリーサーチ構造のサーチレベルについてそれぞれ独立にアクセス可能なメモリアーキテクチュアを使用すると、ソート装置が各クロックサイクル内でユニットをソートすることが可能となる。これは、ユニット記憶構造内にユニットを置くことが１クロックサイクル内で実施される場合に当てはまる。
【００１２】
特に、ユニットサーチ構造及びユニット位置ポインタ構造のツリーサーチ構造の各サーチレベルについてそれぞれ独立にアクセス可能な４つのメモリアーキテクチュアを備えた、ユニットサーチ構造及びユニット位置ポインタ構造用の分散型のメモリアーキテクチュアを使用すると、ソート装置のスループット速度は増加するが、装置の複雑さ及びコストも増加する。ユニットサーチ構造及びユニット位置ポインタ構造用に他の数のメモリアーキテクチュアが使用され得ることが理解されよう。たとえば、１つのメモリアーキテクチュアだけが、ユニットサーチ構造及びユニット位置ポインタ構造用に使用されてもよく、或いは２つ又は３つのメモリアーキテクチュアが、ユニットサーチ構造及びユニット位置ポインタ構造用に使用されてもよい。使用するメモリアーキテクチュアの数を選択する際には、ソート装置の速度とソート装置のコストの間のトレードオフが行われなければならない。
【００１３】
ソート装置は、ハードウェアベースであってもよい。ソート装置は、システムオンチップ（ＳｏＣ：ｓｙｓｔｅｍ ｏｎ ｃｈｉｐ）技術を使用した実装によるハードウェアベースのものであってもよい。ソート装置は、ユニットサーチ構造及びユニット位置ポインタ構造用のＳｏＣメモリアーキテクチュアを備えてもよい。ユニットサーチ構造のＳｏＣメモリアーキテクチュアは、ＲＡＭメモリのブロックを備えてもよい。ユニットサーチ構造がツリーサーチ構造を含む場合、ツリーサーチ構造の第１のサーチレベル及び第２のサーチレベルは、複数のレジスタを備えてもよく、ツリーサーチ構造のさらなるサーチレベルはそれぞれ、ＲＡＭメモリのブロックを備えてもよい。
【００１４】
ユニット記憶構造は、ソート装置とは別々に提供されてもよい。或いは、ソート装置は、ユニット記憶構造を備えてもよい。ユニット記憶構造は、リンクリストを備えてもよい。リンクリスト内に格納されたユニットは、所定の順序になるように互いにリンクされてもよい。各ユニットについては、ユニット記憶構造は、ユニットに関連する１つ又は複数の要素をさらに格納してもよい。ユニット記憶構造にリンクリストを使用すると、ソートされ得るすべての可能なユニットのためのメモリを取っておくのではなく、ユニットがソートされるときにユニットへの必要に応じてメモリを使用することが可能となる。これは、それによってメモリ管理及びメモリ割当ての制御が非常に単純化されるので特に有用であり、またユニット記憶構造が、他の装置によって共有されているメモリで実装される場合にも有益であり得る。
【００１５】
ユニットをソートするために単一のソート装置が使用されてもよい。或いは、複数のソート装置が、ユニットをソートするために併せて使用されてもよい。それぞれのソート装置が、クロックのサイクルに従って動作してもよい。複数のソート装置を併せて使用すると、ユニットを各クロックサイクル内でソートすることが可能となる。たとえば、４つのソート装置が、ユニットをソートするために併せて使用されてもよい。ユニットは、４つの別個のユニット記憶構造、各ソート装置について１つのユニット記憶構造にソートされてもよい。ユニットをユニット記憶構造に置くことが４クロックサイクル内で実施される場合、４つのソート装置を併せて使用すると、ユニットを各クロックサイクル内でソートすることが可能となる。
【００１６】
ソート装置は、通信ネットワークのパケットのタグをソートしてもよい。ソート装置は、パケットのタグをソートするために、タグソートポリシーを操作してもよい。タグは、タグ計算回路によって計算されてもよい。タグ計算回路は、タグを計算するために、パケットスケジューリングポリシーを操作してもよい。パケットスケジューリングポリシーは、たとえば、公平キューイングポリシーのファミリーのいずれか、たとえば重み付き公平キューイングポリシーを備えてもよい。
【００１７】
ソート装置は、パケットスケジューラの一部を備えてもよい。スケジューラのソート装置は、通信ネットワークのルータの一部を備えてもよい。
【００１８】
本発明の第２の態様によれば、ユニット記憶構造内のユニットのレコードを含むユニットサーチ構造と、ユニット記憶構造内のユニットの位置ポインタを含むユニット位置ポインタ構造とを備えるソート装置を使用して、ユニットを所定の順序に従ってユニット記憶構造にソートする方法が提供され、ソート装置が、ソートされるユニットを受信するステップと、ユニットサーチ構造が、ソートされるユニットを読み出し、ユニット記憶構造内のユニットのそのレコードを使用して、ソートされるユニットに最も近く一致するユニットをサーチし、ユニット位置ポインタ構造にアクセスし、最も近く一致するユニットの位置ポインタを取り出すステップと、ソート装置が、最も近く一致するユニットの位置ポインタを使用して、ユニット記憶構造にアクセスし、ユニット記憶構造にソートされるユニットを所定の順序による適切な位置に置くステップとを含む。
【００１９】
本発明の第３の態様によれば、本発明の第１の態様によるソート装置を備える、通信ネットワークのためのスケジューラが提供される。
【００２０】
次に、本発明の一実施形態について、例示するためだけに、添付の図面を参照して述べる。
【発明を実施するための最良の形態】
【００２１】
図１に示されたソート装置１は、ユニットサーチ構造２、ユニット位置ポインタ構造３、及びユニット記憶構造４をも備える。しかし、ユニット記憶構造は、ソート装置の外部に設けられてもよいことが理解されよう。
【００２２】
ユニットサーチ構造は、マルチビットツリーサーチ構造を備え、このマルチビットツリーサーチ構造は、示されるように、３つのサーチレベル５を備え、各レベルが１つ又は複数のノード６を備える。ツリーサーチ構造は、より多い又は少ないサーチレベル、また各レベル内により多い又は少ないノードを備え得ることが理解されよう。このツリーサーチ構造は、２ビットの長さを有するユニットセグメントを使用して、６ビットの長さを有するユニットをソートする。本発明はこのツリーサーチ構造に限定されないが、それぞれ異なる長さのユニットをソートするためのツリーサーチ構造を包含することが再び理解されよう。ツリーサーチ構造２の３つのサーチレベル５の各ノード６は、４ビットを、各ユニットセグメントオプション００、０１、１０又は１１について１ビットを備える。レベルのノードのビットは、装置によってユニット記憶構造にソートされたユニットのレコードを含むために使用される。ビットのユニットセグメントオプションに対応するユニットセグメントが装置によって以前にソートされていない場合は、ビットは、０を含む。ビットのユニットセグメントオプションに対応するユニットセグメントが装置によって以前にソートされている場合は、ビットは、１を含む。第１及び第２のサーチレベルに１を含むノードのビットは、ツリーサーチ構造内のそれより下のレベルで、ノード、子ノードにリンクされる。
【００２３】
ツリーサーチ構造は、メモリ内で実装される。構造の２つの第１のサーチレベルはレジスタからなり、第３のサーチレベルは、ＲＡＭのブロックからなる。２つの第１のサーチレベルは、これらのサーチレベルに必要なメモリの量が比較的小さく、レジスタを使用して実現され得るので、レジスタを使用して実装されてもよい。
【００２４】
ユニット位置ポインタ構造３は、ルックアップテーブルを備える。ソート装置によってユニット記憶構造にソートされ得る各ユニットについて、位置がテーブル内に提供されてもよい。ユニット位置ポインタ構造の位置は、そのユニットがソート装置によってユニット記憶構造にソートされている場合は、ユニットの位置ポインタを含む。各ユニットについて、位置ポインタは、ユニット記憶構造内のユニットの位置を示す。ユニット位置ポインタ構造は、メモリ内で実装され、ＲＡＭのブロックを含む。ユニットサーチ構造及びユニット位置ポインタ構造は、ユニット位置ポインタ構造がユニットサーチ構造のツリーサーチ構造の第４のサーチレベルを有効に形成するようにリンクされる。
【００２５】
ユニット記憶構造４は、リンクリストを含む。リンクリストは、メモリ内で実装される。リンクリスト内のユニットは、メモリ全体にわたってランダムに分散されてもよい。リンクリスト内に格納されたユニットは、所定の順序になるように互いにリンクされる。リンクリストの各エントリは、ユニットと、リスト内の後続のユニットへの位置ポインタとを含む。ソート装置のこの実施形態では、リンクリストは、ユニットサーチ構造２及びユニット位置ポインタ構造３を備えたチップ内に含まれる。しかし、リンクリストは、たとえば外部デュアルポートＲＡＭ上で、オフチップで実装されてもよい。
【００２６】
ソート装置は、以下のように動作する。ユニットがユニット記憶構造にソートされる所定の順序を決定する、ユニットソートポリシーが選択される。この実施形態では、所定の順序は、ユニットの昇順である。しかし、ユニットの他の順序、たとえば降順が選択され得ることが理解されよう。
【００２７】
ソートされるユニットは、ソート装置１によって受信され、ユニットサーチ構造２によって読み出される。ユニットサーチ構造によって読み出される各ユニットについて、ユニットの値に基づいて、復号手順が、ツリーサーチ構造の３つのサーチレベル５のそれぞれで実施される。この手順は、ユニットサーチ構造内に含まれるこれらのユニットのレコードを使用して、ユニット記憶構造内の最も近く一致するユニットをサーチする。たとえば、１１０１１０の値を有するユニットに最も近く一致するユニットを見つけるために、２つの第１のビット、１１を備えるユニットセグメントが、ツリーサーチ構造の第１のサーチレベルのノードと比較される。このノード内の第４のビットは、ユニットセグメントオプション１１に関連する。第４のビット内に１が存在する場合は、これは、１１で始まるユニットが装置によって既にソートされており、ノードの第４のビットがそれより下のサーチレベル、すなわちツリーサーチ構造の第２のサーチレベルのノードにリンクされることを示す。ユニットの、次の２つのビット、０１を備えるユニットセグメントが、第２のサーチレベルのノードと比較される。このノードの第２のビットが１を含む場合は、これは、１１０１で始まるユニットが以前に装置によってソートされており、このノードの第２のビットがそれより下のサーチレベル、すなわちツリーサーチ構造の第３のサーチレベルのノードにリンクされることを示す。（第２のビットが０を含む場合は、ユニットセグメント０１にできるだけ近い一致、及び第３サーチレベルの対応するノードを見つけるために第２のサーチレベルのノード内の４ビットがスキャンされる。）ユニットの、最後の２ビットを備えるユニットセグメントは、第３のサーチレベル内のノードと比較される。このノードの第３のビットは、現在ソートされているユニットとまさに同じユニットを装置が既にソートしている可能性が低いので、通常０を含む。ユニットセグメント１０にできるだけ近い一致を見つけるために、第３のサーチレベルのノード内の４つのビットがスキャンされる。これは、たとえば、０１であり得る。次いで、ソートされるユニットに最も近く一致するユニットは、１１０１０１である。
【００２８】
ツリーサーチ構造の第３のサーチレベルの各ノードは、ユニット位置ポインタ構造内の４つのエントリ、ユニットセグメントオプション、００、０１、１０及び１１のそれぞれについて１つのエントリにリンクされる。ユニット位置ポインタ構造は、ユニット記憶構造内のユニットの位置へのポインタを含む。この実施例では、ユニット１１０１１０は、以前にソートされておらず、ユニット位置ポインタ構造内のこのユニットの場所は空である。最も近く一致するユニットが１１０１０１であると決定される。ソート装置は、このユニットについてユニット位置ポインタ構造内の位置にアクセスし、ユニット記憶構造内のこのユニットの位置を読み出す。
【００２９】
この時点で、ソートされるユニットは、リンクリストユニットの記憶構造内に、所定の順序、すなわちこの実施例では昇順による正確な位置に容易に挿入することができる。ソート装置は、ソートされるユニットについてリンクリスト内の記憶位置を要求し、この位置にユニットを格納する。ソート装置は、最も近く一致するユニット１１０１０１の位置ポインタを使用して、リンクリスト内のこのユニットの位置にアクセスし、この位置から、リンクリスト内の後続のユニットの位置ポインタを読み出す。ソート装置は、ユニット１１０１０１の位置の位置ポインタを、ソートされるユニットのリンクリスト内に位置を指すように変更する。またソート装置は、最も近く一致するユニットの位置からそれが読み出した、リンクリスト内の後続のユニットの位置ポインタを、ソートされるユニットのリンクリストの位置に挿入する。したがって、ソートされるユニットは、リンクリストユニット記憶構造内に、ユニットの昇順による位置に置かれる。
【００３０】
ユニットサーチ構造に含まれた、ユニット記憶構造内のユニットのレコードが更新される。これは、ユニットがソートされた後に、或いはユニットに最も近く一致するユニットをサーチする間に行うことができる。ユニットの各セグメントについて、ツリーサーチ構造の第１、第２及び第３のサーチレベルの適切なノードの適切なビット内に、１が置かれる。上記に示された実施例では、第１のサーチレベルのノード内の第４のビットに１が置かれ、第２のサーチレベルでアクセスされたノード内の第２のビットに１が置かれ、第３のサーチレベルでアクセスされたノード内の第３のビットに１が置かれる。ソートされた各ユニットについて、ソート装置は、ユニット位置ポインタ構造内に、ユニットのユニット記憶構造内の位置へのポインタを置く。
【００３１】
ユニットサーチ構造のマルチビットツリーサーチ構造及びユニット位置ポインタ構造は、分散メモリアーキテクチュアを使用して実装される。ツリーサーチ構造及びユニット位置ポインタ構造の３つのサーチレベルは、それぞれ独立にアクセス可能なメモリアーキテクチュア内に保持される。ツリーサーチ構造及びユニット位置ポインタ構造のレベルは、互いに独立に書き込み、又は読み出すことができる。これによって、ソート装置の並列パイプライン構造が提供され、装置の動作速度が向上する。
【００３２】
上記説明は、ソート装置によってソートされる第２及び後続のユニットに当てはまる。ソートされるべきユニットが、装置によってソートされる第１のユニットである場合、異なる、第１のユニットソート手順を使用しなければならない。ソートされるべき第１のユニットが、ソート装置によって受信され、ユニットサーチ構造がアクセスされ、ツリーサーチ構造の第１のサーチレベルのノードのビットはそれぞれ、０を含む。これは、ソート装置に、第１のユニットソート手順を適用させる。第１のユニットは、それに割り当てられたリンクリストユニット記憶構造内に位置を有する。次いで、ユニットサーチ構造は、第１のユニットの第１のセグメントを読み出し、ツリーサーチ構造の第１のサーチレベルのノードの適切なビットに１を書き込み、第１のサーチレベルのノード内のビットにリンクされた第２のサーチレベルのノードに移動する。次いで、ユニットサーチ構造は、第１のユニットの次のセグメントを読み出し、第２のサーチレベルのノードの適切なビットに１を書き込み、第２のサーチレベルのノード内のビットにリンクされた第３のサーチレベルのノードに移動する。次いで、ユニットサーチ構造は、第１のユニットの最後のセグメントを読み出し、第３のサーチレベルのノードの適切なビットに１を書き込み、第１のユニットに割り当てられたユニット位置ポインタ構造内の位置に移動し、第１のノードに割り当てられたユニット記憶構造位置をユニット位置ポインタ構造内の位置に書き込む。次いで、ソート装置は、ユニット記憶構造内の事前に割り当てられた位置に第１のユニットを置くために、第１のユニットの位置ポインタを使用する。
【００３３】
ソート装置は、たとえば通信ネットワークの一部を備える場合、クロックサイクルに従って動作してもよい。これが当てはまる場合、特定のどんなメモリも、クロックサイクル当たり一度だけアクセスされ得るのが通常である。ツリーサーチ構造及びユニット位置ポインタ構造の３つのサーチレベルは、それぞれ独立にアクセス可能なメモリ位置内に保持され、したがって、３つのすべてのサーチレベル及びポインタ位置構造が、同じクロックサイクル内にアクセスされ得る。したがって、第１の３クロックサイクルの後、ソート装置は、各クロックサイクル内で、ソートされるユニットに最も近く一致するユニットの位置ポインタを取り出すことができる。したがって、ソート装置は、ユニット記憶構造内にユニットを置くのに１クロックサイクルしか必要でないならば、各クロックサイクル内でユニットをソートするであろう。しかし、リンクリストユニット記憶構造を備えるメモリは、ユニットをリンクリストに置くために、４回アクセスしなければならない。したがって、ユニットをリンクリスト内に置くには、４クロックサイクルを要する。したがって、４つのクロックサイクルごとにユニットがソート装置に入力され、そうでない場合は、最も近く一致するユニット位置ポインタが取り出され、リンクリスト内に置かれるべきユニットのキューが発生する。したがって、ソート装置は、４クロックサイクルごとにユニットをソートするにすぎない。３つの各サーチレベル、及び位置ポインタ構造は、４クロックサイクルごとにアクセスされるにすぎない。中間にある「冗長な」クロックサイクルは、メモリ位置がそれぞれ独立にアクセス可能であるために、同じクロックサイクル内に２つ以上のサーチレベル及び位置ポインタ構造にアクセスすることができるので、ツリーサーチ構造のビット、及び位置ポインタ構造内の位置ポインタを更新するために使用することができる。
【００３４】
ソート装置のアーキテクチュアは、ＶＨＤＬで実装され、Ｓｙｎｐｉｌｃｉｔｙ ａｎｄ Ｘｉｌｉｎｘ Ｆｏｕｎｄａｔｉｏｎツールを使用して、Ｘｉｌｉｎｘ Ｖｉｒｔｅｘ ＦＰＧＡ用に合成されている。８４ＭＨｚのクロック速度で、ソート操作当たり４クロックサイクルの場合、この実装形態は、４０Ｇｂｐｓで２５０Ｂの平均ユニットサイズをサポートすることができる。この回路実装にＳｏＣ技術を使用すると、１００Ｇｂｐｓを超過する速度の達成が可能となり得る。
【００３５】
ユニットをソートするために、単一のソート装置が使用されてもよい。或いは、複数のソート装置が、ユニットをソートするために併せて使用されてもよい。たとえば、４つのソート装置が、ユニットをソートするために併せて使用されてもよい。ユニットは、４つの別個のユニット記憶構造、各ソート装置について１つのユニット記憶構造にソートされる。（この場合、ユニットの取出しが必要な場合、各記憶構造の第１のユニットが読み出され、最低の値を有するユニットが取り出される。）それぞれのソート装置は、クロックのサイクルに従って動作してもよい。上記のようにユニット記憶構造がリンクリストである場合、ユニットを記憶構造に置くのに４クロックサイクルを要する。したがって、それぞれのソート装置は、４つのクロックサイクルごとに１ユニットをソートし得るにすぎない。４つのソート装置を併せて使用すると、ユニットを各クロックサイクル内でソートすることが可能となる。
【００３６】
図２は、パケットベースの通信ネットワーク用のスケジューラの概略図を示している。スケジューラは、通信ネットワークのルータの一部を備える。ルータは、ネットワークを介して伝播されるデータパケットをルーティングするように働く。ルータは、ルータの複数の入力を介してパケットを受信し、この複数のパケットを、ルータの出力に伝播する必要がある。これによって、パケットの伝播のスケジューリングが必要となる。
【００３７】
こうしたスケジューリングは、スケジューラによって実施される。スケジューリングプロセスは、２つの段階、パケットスケジューリングポリシー機能及びパケット修理機能からなる。スケジューラ１０は、パケットスケジューリングポリシー機能を担うパケットスケジューリングポリシー回路１２と、パケット処理機能を担うパケット処理回路１４とを備える。
【００３８】
パケットスケジューリングポリシー回路１２は、スケジューラを介したパケットの伝播のスケジューリング、特に順序を決定するために使用されるパケットスケジューリングポリシーを操作する。スケジューリングポリシー回路は、スケジューリングポリシーに従って各パケットのタグを計算し、タグの値は、互い対してパケットのスケジューリングを決定するために使用される。通常、タグを昇順に処理するようにスケジューリングすることが決定される。次いで、タグの値は、スケジューリングポリシーを使用して、より低いタグ値が、より高いスケジューリング優先度を有するパケットに割り当てられ、より高いタグ値が、より低いスケジューリング優先度を有するパケットに割り当てられるように計算される。
【００３９】
パケットスケジューリングポリシー回路は、タグを計算するために使用されるタグ計算回路１６を備える。タグは、計算されると、パケット処理回路１４に渡される。
【００４０】
パケット処理回路１４によって受信されるタグは本質的に、ランダムな順序である。この理由は、ネットワーク内の単一のトラフィックフロー内のパケットは、フローに以前に割り当てられたタグよりも高くなっていくタグを受信するが、別個のトラフィックフローからのパケットは、タグを昇順には受信しないが、フローの特性、及びタグ計算回路によって操作されたスケジューリングポリシーに従って受信するからである。スケジューラは、複数のフローからパケットを受信し、したがって、計算されたタグ値は、特定の順序を有さない。タグが、タグ計算回路から受信される順序、すなわちランダムな順序で格納される場合、これは、関連するパケットの処理のための後続のタグ取出しに対して意味をもつ。通常、タグは、まず最低のタグから始めて、昇順に取り出され、これを容易にするために、タグは、パケット処理回路に到着するとすぐに昇順にソートされ、したがって順番に格納される。
【００４１】
パケット処理回路１４は、タグソート装置１８を備える。タグソート装置は、上述の図１のユニットソート装置と同じ構造を有する。タグソート装置１８は、タグサーチ構造と、タグ位置ポインタ構造と、タグ記憶構造とを備える。上述したように、ソートされるべきタグがタグサーチ構造によって受信される場合、最も近く一致する値のサーチが実施される。これによって、タグ位置ポインタ構造から、ソートされるタグに最も近く一致するタグ記憶構造内のタグに、位置ポインタが返される。次いで、ソートされるタグは、タグの昇順に従って、タグ記憶構造内の正確な位置に挿入される。したがって、タグソート装置は、タグを昇順にソートする問題への解決策を提供する。タグツリーサーチ構造及びタグ位置ポインタ構造のサーチレベルが、互いに独立に実装されるので、これによって、高速タグソート方法、及びマルチギガビット回線高速ネットワーク内のパケットスケジューリングが可能なスケジューラが提供される。
【００４２】
またスケジューラは、到着するタグのソートが行われている間、ルータからネットワークへと前方伝播を行うために、ソートされたタグを取り出し、それに関連するパケットをスケジューラの出力に転送している。ソートされたタグは、まず最も低いタグから始めて、昇順に取り出される。これは、タグがリンクリストの記憶構造内で昇順にソートされているので、リンクリストのタグ記憶構造の第１のエントリ内のタグを繰り返し読み出す単純なプロセスである。タグ記憶構造の各エントリは、タグ、及びタグに関連するパケットが格納された位置を示す位置ポインタをも含み、スケジューラ及びルータからの前方伝播のためにパケットを取り出すことを可能にする。
【図面の簡単な説明】
【００４３】
【図１】本発明の第１の態様によるソート装置の概略図である。
【図２】図１のソート装置を組み込む、本発明の第２の態様によるスケジューラの概略図である。
【特許請求の範囲】
【請求項１】
ユニットを所定の順序に従ってユニット記憶構造にソートするためのソート装置であって、
前記ユニット記憶構造内のユニットのレコードを含むユニットサーチ構造と、
前記ユニット記憶構造内のユニットの位置ポインタを含むユニット位置ポインタ構造と
を備え、
当該ソート装置が、ソートされるユニットを受信し、
前記ユニットサーチ構造が前記ソートされるユニットを読み出し、前記ユニット記憶構造内のユニットのそのレコードを使用して、前記ソートされるユニットに最も近く一致するユニットをサーチし、前記ユニット位置ポインタ構造にアクセスし、前記最も近く一致するユニットの位置ポインタを取り出し、
前記ソート装置が、前記最も近く一致するユニットの前記位置ポインタを使用して、前記ユニット記憶構造にアクセスし、前記ユニット記憶構造にソートされる前記ユニットを、前記所定の順序による適切な位置に置く、ソート装置。
【請求項２】
前記ユニットサーチ構造がツリーサーチ構造を含む、請求項１に記載のソート装置。
【請求項３】
前記ツリーサーチ構造がマルチビットツリーサーチ構造を含む、請求項２に記載のソート装置。
【請求項４】
前記ツリーサーチ構造が複数のサーチレベルを含む、請求項３に記載のソート装置。
【請求項５】
前記ツリーサーチ構造が、少なくとも１つのノードを備える第１のサーチレベルを具備する、請求項４に記載のソート装置。
【請求項６】
前記ツリーサーチ構造が、直前のサーチレベルのノードにリンクされた１つ又は複数のノードをそれぞれが備える１つ又は複数のさらなるサーチレベルを具備する、請求項５に記載のソート装置。
【請求項７】
前記ノードの少なくとも一部が、前記ユニット記憶構造内のユニットの前記レコードを含む、請求項５又は６に記載のソート装置。
【請求項８】
前記ノードのそれぞれが１つ又は複数のビットを備える、請求項５〜７のいずれか一項に記載のソート装置。
【請求項９】
前記ノードの前記ビットの少なくとも一部が、前記ユニット記憶構造内のユニットの前記レコードを含む、請求項８に記載のソート装置。
【請求項１０】
前記ツリーサーチ構造が、ソートされる前記ユニットの少なくとも１つのセグメントを１つ又は複数のサーチレベルの少なくとも１つのノードと比較することによって、前記最も近く一致するユニットをサーチして、前記セグメント又は各セグメントに最も近い一致を見つけ、もって、前記ソートされるユニットに前記最も近く一致するユニットを見つける、請求項５〜９のいずれか一項に記載のソート装置。
【請求項１１】
前記ツリーサーチ構造が、前記ソートされるユニットの第１のセグメントを前記ツリーサーチ構造の第１のサーチレベルのノードと比較して、前記第１のセグメントに最も近い一致、及び前記第１のサーチレベルの前記ノードがリンクされた前記ツリーサーチ構造の第２のサーチレベル内のノードを見つけ、前記ソートされるユニットの第２のセグメントを前記第２のサーチレベルの前記ノードと比較して、前記第２のセグメントに最も近い一致、及び前記第２のサーチレベルの前記ノードがリンクされた前記ツリーサーチ構造の第３のサーチレベル内のノードを見つけ、前記ソートされるユニットの第３のセグメントを第３のサーチレベルの前記ノードと比較して、前記第３のセグメントに最も近い一致、したがって、前記ソートされるユニットに最も近く一致するユニットを見つけることによって、前記最も近く一致するユニットをサーチする、請求項１０に記載のソート装置。
【請求項１２】
前記ツリーサーチ構造が、前記ユニット記憶構造内の前記ユニットのそのレコードを更新する、請求項２〜１１のいずれか一項に記載のソート装置。
【請求項１３】
前記ユニット位置ポインタ構造が、前記ソート装置によって前記ユニット記憶構造にソートされ得る各ユニットの位置ポインタの位置を備える、請求項１〜１２のいずれか一項に記載のソート装置。
【請求項１４】
ユニットが前記ソート装置によって前記ユニット記憶構造にソートされている場合は、位置が前記ユニットの位置ポインタを含む、請求項１３に記載のソート装置。
【請求項１５】
前記ユニットがソートされた後、前記ソート装置がユニットの位置ポインタを前記ユニット位置ポインタ構造内に置く、請求項１３又は１４に記載のソート装置。
【請求項１６】
前記ユニット位置ポインタ構造がルックアップテーブルを備える、請求項１〜１５のいずれか一項に記載のソート装置。
【請求項１７】
ユニット位置ポインタ構造が前記ユニットサーチ構造にリンクされる、請求項１〜１６のいずれか一項に記載のソート装置。
【請求項１８】
前記ユニット位置ポインタ構造が、前記ユニットサーチ構造の前記ツリーサーチ構造の最下位レベルを有効に備えるように前記ユニットサーチ構造にリンクされる、請求項１７に記載のソート装置。
【請求項１９】
前記ソート装置が、前記ユニットを前記所定の順序にソートするためにユニットソートポリシーを操作する、請求項１〜１８のいずれか一項に記載のソート装置。
【請求項２０】
前記ソート装置が、前記ユニットサーチ構造及び前記ユニット位置ポインタ構造のための分散メモリアーキテクチュアを備える、請求項１〜１９のいずれか一項に記載のソート装置。
【請求項２１】
前記ユニットサーチ構造及び前記ユニット位置ポインタ構造の前記ツリーサーチ構造の各サーチレベルが、それぞれ独立にアクセス可能なメモリアーキテクチュアを備える、請求項４〜２０のいずれか一項に従属する請求項２０に記載のソート装置。
【請求項２２】
前記ユニット記憶構造がリンクリストを含む、請求項１〜２１のいずれか一項に記載のソート装置。
【請求項２３】
前記リンクリスト内に格納された前記ユニットが、所定の順序になるように互いにリンクされる、請求項２２に記載のソート装置。
【請求項２４】
通信ネットワークのパケットのタグをソートする、請求項１〜２３のいずれか一項に記載のソート装置。
【請求項２５】
請求項１〜２４のいずれか一項に記載のソート装置を備えるパケットスケジューラ。
【請求項２６】
ユニット記憶構造内のユニットのレコードを含むユニットサーチ構造と、前記ユニット記憶構造内のユニットの位置ポインタを含むユニット位置ポインタ構造とを備えるソート装置を使用して、ユニットを所定の順序に従って前記ユニット記憶構造にソートする方法であって、
前記ソート装置が、ソートされるユニットを受信するステップと、
前記ユニットサーチ構造が、前記ソートされるユニットを読み出し、前記ユニット記憶構造内のユニットのそのレコードを使用して、前記ソートされるユニットに最も近く一致するユニットをサーチし、前記ユニット位置ポインタ構造にアクセスし、前記最も近く一致するユニットの位置ポインタを取り出すステップと、
前記ソート装置が、前記最も近く一致するユニットの前記位置ポインタを使用して、前記ユニット記憶構造にアクセスし、前記ユニット記憶構造にソートされる前記ユニットを、前記所定の順序による適切な位置に置くステップと
を備える方法。
【請求項１】
ユニットを所定の順序に従ってユニット記憶構造にソートするためのソート装置であって、
前記ユニット記憶構造内のユニットのレコードを含むユニットサーチ構造と、
前記ユニット記憶構造内のユニットの位置ポインタを含むユニット位置ポインタ構造と
を備え、
当該ソート装置が、ソートされるユニットを受信し、
前記ユニットサーチ構造が前記ソートされるユニットを読み出し、前記ユニット記憶構造内のユニットのそのレコードを使用して、前記ソートされるユニットに最も近く一致するユニットをサーチし、前記ユニット位置ポインタ構造にアクセスし、前記最も近く一致するユニットの位置ポインタを取り出し、
前記ソート装置が、前記最も近く一致するユニットの前記位置ポインタを使用して、前記ユニット記憶構造にアクセスし、前記ユニット記憶構造にソートされる前記ユニットを、前記所定の順序による適切な位置に置く、ソート装置。
【請求項２】
前記ユニットサーチ構造がツリーサーチ構造を含む、請求項１に記載のソート装置。
【請求項３】
前記ツリーサーチ構造がマルチビットツリーサーチ構造を含む、請求項２に記載のソート装置。
【請求項４】
前記ツリーサーチ構造が複数のサーチレベルを含む、請求項３に記載のソート装置。
【請求項５】
前記ツリーサーチ構造が、少なくとも１つのノードを備える第１のサーチレベルを具備する、請求項４に記載のソート装置。
【請求項６】
前記ツリーサーチ構造が、直前のサーチレベルのノードにリンクされた１つ又は複数のノードをそれぞれが備える１つ又は複数のさらなるサーチレベルを具備する、請求項５に記載のソート装置。
【請求項７】
前記ノードの少なくとも一部が、前記ユニット記憶構造内のユニットの前記レコードを含む、請求項５又は６に記載のソート装置。
【請求項８】
前記ノードのそれぞれが１つ又は複数のビットを備える、請求項５〜７のいずれか一項に記載のソート装置。
【請求項９】
前記ノードの前記ビットの少なくとも一部が、前記ユニット記憶構造内のユニットの前記レコードを含む、請求項８に記載のソート装置。
【請求項１０】
前記ツリーサーチ構造が、ソートされる前記ユニットの少なくとも１つのセグメントを１つ又は複数のサーチレベルの少なくとも１つのノードと比較することによって、前記最も近く一致するユニットをサーチして、前記セグメント又は各セグメントに最も近い一致を見つけ、もって、前記ソートされるユニットに前記最も近く一致するユニットを見つける、請求項５〜９のいずれか一項に記載のソート装置。
【請求項１１】
前記ツリーサーチ構造が、前記ソートされるユニットの第１のセグメントを前記ツリーサーチ構造の第１のサーチレベルのノードと比較して、前記第１のセグメントに最も近い一致、及び前記第１のサーチレベルの前記ノードがリンクされた前記ツリーサーチ構造の第２のサーチレベル内のノードを見つけ、前記ソートされるユニットの第２のセグメントを前記第２のサーチレベルの前記ノードと比較して、前記第２のセグメントに最も近い一致、及び前記第２のサーチレベルの前記ノードがリンクされた前記ツリーサーチ構造の第３のサーチレベル内のノードを見つけ、前記ソートされるユニットの第３のセグメントを第３のサーチレベルの前記ノードと比較して、前記第３のセグメントに最も近い一致、したがって、前記ソートされるユニットに最も近く一致するユニットを見つけることによって、前記最も近く一致するユニットをサーチする、請求項１０に記載のソート装置。
【請求項１２】
前記ツリーサーチ構造が、前記ユニット記憶構造内の前記ユニットのそのレコードを更新する、請求項２〜１１のいずれか一項に記載のソート装置。
【請求項１３】
前記ユニット位置ポインタ構造が、前記ソート装置によって前記ユニット記憶構造にソートされ得る各ユニットの位置ポインタの位置を備える、請求項１〜１２のいずれか一項に記載のソート装置。
【請求項１４】
ユニットが前記ソート装置によって前記ユニット記憶構造にソートされている場合は、位置が前記ユニットの位置ポインタを含む、請求項１３に記載のソート装置。
【請求項１５】
前記ユニットがソートされた後、前記ソート装置がユニットの位置ポインタを前記ユニット位置ポインタ構造内に置く、請求項１３又は１４に記載のソート装置。
【請求項１６】
前記ユニット位置ポインタ構造がルックアップテーブルを備える、請求項１〜１５のいずれか一項に記載のソート装置。
【請求項１７】
ユニット位置ポインタ構造が前記ユニットサーチ構造にリンクされる、請求項１〜１６のいずれか一項に記載のソート装置。
【請求項１８】
前記ユニット位置ポインタ構造が、前記ユニットサーチ構造の前記ツリーサーチ構造の最下位レベルを有効に備えるように前記ユニットサーチ構造にリンクされる、請求項１７に記載のソート装置。
【請求項１９】
前記ソート装置が、前記ユニットを前記所定の順序にソートするためにユニットソートポリシーを操作する、請求項１〜１８のいずれか一項に記載のソート装置。
【請求項２０】
前記ソート装置が、前記ユニットサーチ構造及び前記ユニット位置ポインタ構造のための分散メモリアーキテクチュアを備える、請求項１〜１９のいずれか一項に記載のソート装置。
【請求項２１】
前記ユニットサーチ構造及び前記ユニット位置ポインタ構造の前記ツリーサーチ構造の各サーチレベルが、それぞれ独立にアクセス可能なメモリアーキテクチュアを備える、請求項４〜２０のいずれか一項に従属する請求項２０に記載のソート装置。
【請求項２２】
前記ユニット記憶構造がリンクリストを含む、請求項１〜２１のいずれか一項に記載のソート装置。
【請求項２３】
前記リンクリスト内に格納された前記ユニットが、所定の順序になるように互いにリンクされる、請求項２２に記載のソート装置。
【請求項２４】
通信ネットワークのパケットのタグをソートする、請求項１〜２３のいずれか一項に記載のソート装置。
【請求項２５】
請求項１〜２４のいずれか一項に記載のソート装置を備えるパケットスケジューラ。
【請求項２６】
ユニット記憶構造内のユニットのレコードを含むユニットサーチ構造と、前記ユニット記憶構造内のユニットの位置ポインタを含むユニット位置ポインタ構造とを備えるソート装置を使用して、ユニットを所定の順序に従って前記ユニット記憶構造にソートする方法であって、
前記ソート装置が、ソートされるユニットを受信するステップと、
前記ユニットサーチ構造が、前記ソートされるユニットを読み出し、前記ユニット記憶構造内のユニットのそのレコードを使用して、前記ソートされるユニットに最も近く一致するユニットをサーチし、前記ユニット位置ポインタ構造にアクセスし、前記最も近く一致するユニットの位置ポインタを取り出すステップと、
前記ソート装置が、前記最も近く一致するユニットの前記位置ポインタを使用して、前記ユニット記憶構造にアクセスし、前記ユニット記憶構造にソートされる前記ユニットを、前記所定の順序による適切な位置に置くステップと
を備える方法。
【図１】
【図２】
【図２】
【公表番号】特表２００９−５１８９１６（Ｐ２００９−５１８９１６Ａ）
【公表日】平成２１年５月７日（２００９．５．７）
【国際特許分類】
【出願番号】特願２００８−５４３８８８（Ｐ２００８−５４３８８８）
【出願日】平成１８年１２月５日（２００６．１２．５）
【国際出願番号】ＰＣＴ／ＧＢ２００６／００４５２６
【国際公開番号】ＷＯ２００７／０６６０８５
【国際公開日】平成１９年６月１４日（２００７．６．１４）
【出願人】（５０４３８９６３６）ザ クイーンズ ユニヴァーシティ オブ ベルファスト (14)
【Ｆターム（参考）】
【公表日】平成２１年５月７日（２００９．５．７）
【国際特許分類】
【出願日】平成１８年１２月５日（２００６．１２．５）
【国際出願番号】ＰＣＴ／ＧＢ２００６／００４５２６
【国際公開番号】ＷＯ２００７／０６６０８５
【国際公開日】平成１９年６月１４日（２００７．６．１４）
【出願人】（５０４３８９６３６）ザ クイーンズ ユニヴァーシティ オブ ベルファスト (14)
【Ｆターム（参考）】
[ Back to top ]