(57)【要約】  サーバは、キューに保持されたセル送信のための異なるクオリティ・オブ・サービス要件を備えた保証帯域幅（ＧＢ）アレイ２１およびエクストラ帯域幅（ＥＢ）アレイ３１を有する。このサーバは、セルの遅延の変動を最小限に抑えるために、多くても、１アレイ位置ごとに１つのキューしかなくなるまで、キューを循環アレイに分配するように動作する。
2007504735.tif 000002
【特許請求の範囲】
【請求項１】
保証帯域幅アレイおよびエクストラ帯域幅アレイである、送信用セル用の２つのアレイを含むサーバを動作させる方法であって、送信準備ができているセル用の前記保証帯域幅アレイをモニタすること、送信準備ができているセルに対応するイベントをスケジュールすること、およびそのように作成された前記スケジュールの任意に選んだ位置に単一のキュー記述子を付加することを含む方法。
【請求項２】
各位置がキューのリンク・リストを指す、請求項１に記載の方法。
【請求項３】
キューが適当な時間に処理されるように、キュー記述子の配置を調整することを含む、請求項１または２に記載の方法。
【請求項４】
前記スケジューリング動作を実施するためにタイミング・ホイールを使用することを含む、前記請求項のいずれかに記載の方法。
【請求項５】
三次元タイミング・ホイール・データ構造を含む、請求項４に記載の方法。
【請求項６】
動的スケジューリングを実施するために、特定のイベントが発生した後に、タイミング・ホイールの適当な将来の位置に１つまたは複数のイベントを付加することを含む、前記請求項のいずれかに記載の方法。
【請求項７】
イベントの前記スケジュールの再計算を再反復することを含む、前記請求項のいずれかに記載の方法。
【請求項８】
１リスト・エントリごとに参照されるキューが１つになるまで、前記保証帯域幅アレイのリスト中でのキュー参照の分散を最適化することを含む、前記請求項のいずれかに記載の方法。
【請求項９】
前記保証帯域幅アレイを実施するために、あるタイムスロットで、あるキューのセルが前記アレイ中のインデックスされた位置に向けられる循環バッファを動作させることを含む、前記請求項のいずれかに記載の方法。
【請求項１０】
１リスト・エントリによって複数のキューが参照される構成で保証帯域幅アレイを動作させること、インデックスされた位置で第１のキューを処理すること、およびポインタを処理間隔に応じた量だけ前記リストに沿って移動させることを含む、前記請求項のいずれかに記載の方法。
【請求項１１】
送信されるべきセルが前記保証帯域幅アレイ中で１つも見つからないときのみ、前記エクストラ帯域幅アレイを動作させることを含む、前記請求項のいずれかに記載の方法。
【請求項１２】
送信準備ができているセル用の保証帯域幅アレイをモニタし、送信準備ができているセルに対応するイベントをスケジュールし、そのように作成された前記スケジュールの任意に選んだ位置に単一のキュー記述子を付加する方法を実施するためのソフトウェア・コード部分を含む、デジタル・コンピュータの内部記憶装置に直接ロード可能なコンピュータ・プログラム。
【請求項１３】
前記プログラムがコンピュータ上で実行されるときに請求項１から１１のいずれか一項または複数の項の方法を実施するためのソフトウェア・コード部分を含む、デジタル・コンピュータの内部記憶装置に直接ロード可能なコンピュータ・プログラム。
【請求項１４】
前記プログラムがコンピュータ上で実行されるとき、請求項１から１１のいずれか一項または複数の項の方法を実施するためのソフトウェア・コード部分を含む、デジタル・コンピュータの内部記憶装置に直接ロード可能なコンピュータ・プログラム。
【請求項１５】
請求項１４に記載のコンピュータ・プログラムのための、電子信号を含んでもよい、搬送波。
【請求項１６】
請求項１２または１３に記載のコンピュータ・プログラムまたは請求項１４に記載のコンピュータ・プログラムまたは請求項１５に記載の搬送波の電子配布。
【請求項１７】
保証帯域幅アレイおよびエクストラ帯域幅アレイである、送信用セルの２つのアレイを含むサーバであって、送信準備ができているセル用の前記保証帯域幅アレイをモニタする手段と、送信準備ができているセルに対応するイベントをスケジュールする手段と、そのように作成された前記スケジュールの任意に選んだ位置に単一のキュー記述子を付加する手段とを含むサーバ。
【請求項１８】
各位置をキューのリンク・リストに向ける手段を含む、請求項１７に記載のサーバ。
【請求項１９】
キューが適当な時間に処理されるようにキュー記述子の配置を調整する手段を含む、請求項１７または１８に記載のサーバ。
【請求項２０】
前記スケジューリング動作を実施するためのタイミング・ホイールを含む、請求項１７から１９のいずれかに記載のサーバ。
【請求項２１】
前記タイミング・ホイールが三次元タイミング・ホイール・データ構造を含む、請求項２０に記載のサーバ。
【請求項２２】
動的スケジューリングを実施するために、特定のイベントが発生した後、１つまたは複数のイベントをタイミング・ホイールの適当な将来の位置に付加する手段を含む、請求項１７から２１のいずれかに記載のサーバ。
【請求項２３】
イベントの前記スケジュールの再計算を再反復する手段を含む、請求項１７から２２のいずれかに記載のサーバ。
【請求項２４】
実質上、添付の図面の図２から６のいずれか１つまたは複数を参照して上に記載された通りの、かつ／またはそこに示された通りの、サーバを動作させる方法。
【請求項２５】
実質上、添付の図面の図２から６のいずれか１つまたは複数を参照して上に記載された通りの、かつ／またはそこに示された通りのサーバ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、サーバ内のセルの送信をスケジュールする方法、そのようなセルをスケジュールするためのソフトウェア、およびサーバに関する。
【背景技術】
【０００２】
インターネット・ルータ中のトラフィック・マネージャは、所定のレベルのサービスを保証するために、送信を待っているセルが必要な時間内に確実に送出されるように、サーバを利用してセルの送信をスケジュールする。
【０００３】
テーブル・ベースのタイミング・ホイールは、イベントをテーブル中の様々な位置に（すなわち、タイミング・ホイール中のスロットに）配置し、それによってイベント・テーブルを定義することによってイベントをスケジュールし、それによって探索の低減または排除を可能にするために使用されてよい。
【０００４】
このスケジュールは、オフラインで予め計算することができ、これは静的スケジュールと呼ばれる。動的スケジュールは、米国、フロリダ州 33620、Tampa、University of South Florida、Department of Computer Science and EngineeringのYun-Sik Lee、 Peter M Maurer著「MDCSIM: A Compiled Event-Drive Multidelay Simulator」に記載されているように、特定のイベントが発生した後、１つまたは複数のイベントをタイミング・ホイールの適当な将来の位置に付加することによって実現されてもよい。
【０００５】
保証帯域幅サーバは、一定のビット・レートでキューを処理し、そのキューのパケットをさらに先へ送信するためにリンクに転送する。キューの最後尾にパケットが到着するパターンがランダムなので、保証帯域幅サーバがそれらのキューを処理する集約帯域幅がリンク帯域幅より狭くなり得る瞬間がある。これによって、エクストラ帯域幅サーバが機会に応じてそれらのキューを処理することができるようになる。
【０００６】
キューを処理する保証帯域幅サーバとエクストラ帯域幅サーバを様々に組み合せると、異なるパケット・フローに異なるクラスのサービスを提供することができるようになる。たとえば、
保証帯域幅サーバのみによって処理されるキューは、到着パターンが規則的である一定のビット・フローまたはそれらの集合体、たとえばビデオ会議トラフィックに使用される。
【０００７】
エクストラ帯域幅サーバのみによって処理されるキューは、指定されていないビット・フローおよび帯域幅フロー、すなわち到着パターンがランダムであるものに使用される。今日のインターネット・トラフィックがいい例である。
【０００８】
保証帯域幅サーバとエクストラ帯域幅サーバの組合せによって処理されるキューは、到着パターンが規則的なトラフィックとランダムなトラフィックとの組合せである可変ビット・レート・フローに使用される。その一例は、エクストラ帯域幅が利用可能な場合にその利益を得ることができるあるタイプの圧縮ビデオ・トラフィックである。
【０００９】
保証帯域幅サーバおよびエクストラ帯域幅サーバのいくつかの例は、Fabio M. ChiussiおよびAndrea Francini著「Providing QoS Guarantees in Packet Switches」、Proc.IEEE GLOBECOM'99、Seamless Interconnection for Universal Services、 Symposium on High Speed Networks、ブラジル、リオ・デ・ジャネイロ、１９９９年１２月、volume V02、1582〜1590ページに記載されている。
【００１０】
米国特許第５，６９６，７６４号は、静的スケジュールを有する、保証帯域幅アレイおよびエクストラ帯域幅アレイを備えたシステムを記載している。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
本発明の一目的は、より効率のよいセルの送信を実現するサーバを提供することであってよい。
【００１２】
本発明の他の目的は、セルの送信を改善するためのより効率のよいデータ構造を提供することであってよい。
【００１３】
本発明の他の目的は、可変ビット・レート・トラフィックを処理することのできるサーバを提供することである。
【００１４】
本発明の他の目的は、１つまたは複数のイベントをタイミング・ホイールの適当な将来の位置に付加することを可能にするサーバを提供することである。
【課題を解決するための手段】
【００１５】
本発明は、保証帯域幅アレイおよびエクストラ帯域幅アレイである、セル送信用の２つのアレイを備えたサーバを動作させる方法であって、送信準備ができているセル用の保証帯域幅アレイをモニタすること、送信準備ができているセルに対応するイベントをスケジュールすること、およびそのように作成されたスケジュールの任意に選んだ位置に単一のキュー記述子を付加することを含む方法を提供する。
【００１６】
好ましくは、この方法では、各位置はキューのリンク・リストを指し、この方法は、キューが適当な時間に処理されるようにキュー記述子の配置を調整することを含む。
【００１７】
この方法では、有利には三次元タイミング・ホイール・データ構造を有する、タイミング・ホイールを利用して、スケジューリング動作を実施してよい。動的スケジューリングを実施するために、特定のイベントが発生した後、タイミング・ホイールの適当な将来の位置に１つまたは複数のイベントを付加してもよい。
【００１８】
この方法は、１リスト・エントリごとの参照キューが１つになるまで、保証帯域幅アレイのリスト中のキュー参照の分散を最適化することを含んでもよい。
【００１９】
有利には、この方法は、保証帯域幅アレイを実施するために、あるタイムスロットでは、あるキューのセルがそれによってアレイ中のインデックスされた位置に向けられる循環バッファを動作させること、および／または１つのリスト・エントリによって複数のキューが参照される構成で保証帯域幅アレイを動作させること、インデックスされた位置にある最初のキューを処理すること、ならびに、ポインタをリストに沿って処理間隔に対応する量だけ移動させることを含む。
【００２０】
本発明は、ハードウェア、たとえばネットワーク・プロセッサを含めたデジタル・コンピュータ、および／またはソフトウェアで実装されてもよい。
【００２１】
また、本発明は、送信準備ができているセル用の保証帯域幅アレイをモニタし、送信準備ができているセルに対応するイベントをスケジュールし、そのように作成されたスケジュールの任意に選択された位置に単一のキュー記述子を付加する方法を実行するためのソフトウェア・コード部分を含む、デジタル・コンピュータの内部記憶装置に直接ロード可能なコンピュータ・プログラムも提供する。
【００２２】
また、本発明は、本発明を実施したコンピュータ・プログラムおよび搬送波、ならびに、製品、プログラムおよび／または搬送波の電子配布も提供する。
【００２３】
また、本発明は、保証帯域幅アレイおよびエクストラ帯域幅アレイである、セル送信用の２つのアレイを含むサーバであって、送信準備ができているセル用の保証帯域幅アレイをモニタする手段と、送信準備ができているセルに対応するイベントをスケジュールする手段と、そのように作成されたスケジュールの任意に選んだ位置に単一のキュー記述子を付加する手段とを含むサーバも提供する。
【００２４】
本発明は、あらゆる形態のサーバ、特にルータおよびトラフィック・マネージャに適用可能である。
【００２５】
本発明がより容易に理解されるように、次に、添付の図面を参照して例としてのみ説明が行われる。
【発明を実施するための最良の形態】
【００２６】
図１は、たとえば、ここに図示された厳密優先サーバ１１に基づくものでよい、従来技術で知られているスケジューラ１０のノードを表す。厳密優先サーバ１１は、保証帯域幅サーバ１２およびエクストラ帯域幅サーバ１３によって処理される。
【００２７】
現在のパケット交換ネットワークのネットワーク要素は、前述のセルの送信がノード内で均一に管理され得るように、一般に、ノードに到着する可変長のパケットを固定長のセルに分割する。セルの固定長によって、セルが記憶されているデータ・バッファの記憶管理が実施可能になる。特定のクオリティ・オブ・サービスを提供するためには、あるセルを他のセルより速く送信する機能が必要であり、これは、あるセルを遅らせることによってのみ可能である。スケジューラにより処理待ちのセルの異なるフローに異なる遅延を与えるために、セルは複数のキューに入れられてもよい。
【００２８】
従来のシステムでは、セル送信スケジューリングには、一般に、キューを指すポインタをヒープに挿入するか、それとも送信準備ができているセルを見つけるためにキューのリストを探索する必要がある。どちらのやり方も非常に効率の悪い方法である。
【００２９】
本発明は、新しいデータ構造と新しい探索アルゴリズムの両方を提供する点で、従来技術より優れている。
【００３０】
データ構造および探索アルゴリズムは協働で機能して、アルゴリズムが繰り返し適用された後、多くても１つのアレイ位置ごとに１つのキューしかなくなるまで、循環アレイへのキューの分配を促進する。
【００３１】
この結果、セルの遅延の変動は最小限に抑えられ、特定のタイムスロットの間に送信するのに適切なセルを探索する問題は、ポインタを増分することに還元される。この方法は、高レベルのスケジューリング精度を保証し、同時に、広範囲にわたる探索を必要としない、非常に速いスケジューリング機構を提供する。
【００３２】
本発明によるシステムは、一見したところでは、セルの送信順が最初任意選択で割り当てられること、ならびに、スケジューリングが、複数のセルが同時に送信されるようなスケジュールリングになるように見えることから、信頼できないように見えることがあるかもしれない。
【００３３】
しかし、キューをアレイに分配するために利用されるこの方法は、一定の帯域幅がそれを必要としているどんなキューにも割り当てられ得ることを保証し、かつ、アルゴリズムを繰り返し適用することによって、最適の送信順が達成される。
【００３４】
したがって、リスト、ヒープまたはスタックを探索する従来技術によって提示される問題は、たとえば、解決はされないが、回避される。
【００３５】
本発明によって提供されるデータ構造は、保証帯域幅リストとエクストラ帯域幅リストの組合せを含む。
【００３６】
図２は、本発明による保証帯域幅リスト２０の構造を示す。保証帯域幅リスト２０は、リンク・リスト２３を指すポインタ２２の時間順アレイ、つまり図２の最下部に示された保証帯域幅アレイ２１を含む。リンク・リストのノード２５それぞれのデータ・ポインタ２４は、処理されるのを待っているセルのキュー２６、たとえばＧＢ（保証帯域幅）またはＡＦ（保証フォワーディング）と呼ばれるキューを指す。ポインタ２２はルータへの到着時間順に並べられる。
【００３７】
キュー２６は、様々なクオリティ・オブ・サービス要件を有し、保証帯域幅アレイ中ではＧＢ（保証帯域幅）キューでもＡＦ（保証フォワーディング）キューでもよい。
【００３８】
各キュー２６に関連するデータ構造は、パラメータ、つまり、そのキュー２６が処理されるべき時間間隔を示す処理間隔、すなわちそのキュー２６の次のセルが送信をスケジュールされる前に経過すべきタイムスロットの数を含む。１個のセルは、１タイムスロットごとに送信されることに留意されたい。
【００３９】
各キュー２６は、各アレイ位置のリンク・リスト２３中で、各キュー２６のセルが、送信されるセルがある場合は、同じキュー２６の前のセルの送信保証時間内に送信されるように、順に訪問される。もちろん、このキューは、たとえば、空でもよい。
【００４０】
ノード要素中の制御ソフトウェアは、ＧＢセルによって占められる帯域幅がリンクの帯域幅を超えないことを保証しなければならない。トラフィック・マネージャは、その構成により、ＧＢセルの数が利用可能なタイムスロットの数より少ないことを保証する。
【００４１】
図３は、本発明によるエクストラ帯域幅リスト３０の構成を示す。機能が図２と変わらない場合は、同じ番号が使用されている。
【００４２】
エクストラ帯域幅リスト３０は、リンク・リスト３３を指すポインタ２２のアレイ、つまりエクストラ帯域幅アレイ３１を含む。リンク・リスト３３の各ノード２５のデータ・ポインタ２４は、処理されるのを待っているセルのキュー３６を指す。このアレイ３１は時間順ではない。
【００４３】
ＧＢアレイ２１のキュー２６はＧＢまたはＡＦキューであるが、エクストラ帯域幅アレイ３１のキュー３６は、ＡＦまたはＢＥ（ベスト・エフォート）キューである点において、エクストラ帯域幅アレイ３１のキュー３６は、保証帯域幅アレイのキュー２６とはクオリティ・オブ・サービス要件が異なる。
【００４４】
さらに、エクストラ帯域幅アレイのリンク・リスト３３は、ノード２５を１つしか含まず、したがって、処理されるキューも１つしか含まない。
【００４５】
図４は、保証帯域幅リスト２１とエクストラ帯域幅リスト３１の組合せ４０をキュー４１と共に示す。
【００４６】
この組合せでは、ＧＢアレイ２１中のポインタは、ＧＢおよびＡＦキューを指し、一方、ＥＢアレイ３１中のポインタは、ＡＦおよびＢＥキューを指す。ＧＢキューは、一定の間隔でタイムスロットを保証され、ＡＦキューは、ＧＢアレイ２１を介して一定の帯域幅と、さらに、帯域幅がＥＢアレイ３１を介して利用可能な場合は、何らかのエクストラ処理を割り当てられる。
【００４７】
上に述べたように、本発明は、データ構造に加えて、新しい探索アルゴリズムを提供する点で、従来技術より優れている。
【００４８】
この探索アルゴリズムでは、以下の３つのカウンタ／ポインタが定義される。
・RealTimeCounter、
・TimeSlotIndex、
・RoundRobinIndex。
【００４９】
RealTimeCounterは、１セル到着期間ごとに１回（保証帯域幅ArrayLengthを法として）増分される。RealTimeCounterは、経過したタイムスロットの数をカウントすることによってリアル・タイムを実際に絶えず記憶している。
【００５０】
モジュロ演算なので、ＧＢアレイの末尾に到達したとき、リアル・タイム・カウンタは起点に戻る。ArrayLengthは、セルのすべてのフローが処理される集約帯域幅とセルのいずれか１つのフローが処理される最低帯域幅の比から算出される。
【００５１】
セルは毎秒固定数のビットを搬送する接続を介して到着し、セルは固定長を有するので、セルの到着速度は一定である。このセルの到着速度の逆数はセルの到着周期である。
【００５２】
TimeSlotIndexは、ＧＢサーバによって探索されるべきキューのリンク・リスト２３を示す。ＥＢアレイとは違って、そのようなリスト中に複数のキューがあってよい。TimeSlotIndexは、以下に述べられるように（保証帯域幅ArrayLengthを法として）増分される。
【００５３】
RoundRobinIndexは、エクストラ帯域幅サーバ１３によって処理されるべき次のキューを指し、エクストラ帯域幅サーバ１３がセルをキューから除去する度に増分される。
【００５４】
優先スケジューラ１１は、いくつかのキューを処理する保証帯域幅サーバ１２に接続され、保証帯域幅サーバ１２に送る準備ができているセルがない場合に呼び出され得る、エクストラ帯域幅サーバ１３にも接続される。
【００５５】
探索は１タイムスロット（セル到着周期）ごとに１回起動される。各タイムスロットで、保証帯域幅サーバ１２が最初に呼び出される。
【００５６】
１タイムスロットごとの実行フローは以下の通りである。
【００５７】
１）（保証帯域幅ArrayLengthを法として）RealTimeCounterを増分する
２）現在のTimeSlotIndexをパラメータとして、保証帯域幅サーバが呼び出される。保証帯域幅サーバは、現在のＧＢアレイ２１の位置でポインタによって指されたキューのリストの探索を行い、
セルが見つけられるまで、または、
２つの連続するアレイ位置にあるリストが探索されるまで、または、
TimeSlotIndexがRealTimeCounter値に等しくなる（すなわち、ＧＢセルによって占められなかったスペア・スロットがどれもＥＢセルによって占められる）まで、
（リストの末尾または空リストが見つけられる度に）TimeSlotIndexを増分し続ける。
【００５８】
２つの連続するリストの（ヌル・ポインタによって示された）末尾に達した場合、ＥＢセルが存在すれば、それが送信される。次いで、次のタイムスロットの起点で第２の空リストが再び探索されるのを防止するために、TimeSlotIndexが増分される。
【００５９】
３）セルが見つけられた場合、
保証帯域幅ポインタの位置が記憶され、そのセルが取り出され送信される。これでこのタイムスロットでの優先スケジューラは完了する。
【００６０】
保証帯域幅アレイ２１の要素は、ノード２５のリンク・リスト２３を指し、ノード２５のデータ・ポインタ２４は、それぞれの場合に、出力キュー４１を指す。最も新しく処理されたキュー４１を指すリンク・リストのノード２５は、リンク・リスト２３から除去され、保証帯域幅アレイ２１に沿ったもっと先のリストに挿入される。この新しいリスト２３の位置は、RealTimeCounter値と、そのキュー４１に関連するデータ構造に記憶され、そのキュー４１が処理されるべき時間間隔（すなわち、将来へのタイムスロットの数）を示す処理間隔との合計として計算される。
【００６１】
固定速度で動作するリンクを介して送信されるのを待っているセルのキューの集まりでは、この固定速度は、個々のキューがそれぞれ処理される速度の合計より大きいかまたはそれと等しくなければならない。そのような個々のキューのそれぞれで、そのキューが処理されるべき間隔、すなわち処理間隔は、セル送信速度の逆数である。
【００６２】
そのキューに属する２つのアレイ要素のインデックス間の差は、処理され再スケジュールされる、当該キューが処理されるべき速度の逆数に相当する。
【００６３】
このようにして、ＧＢリスト中の各キューは、保証された帯域幅で供給されることが可能である。
【００６４】
キューの処理間隔の変動は、リンク・リストがどのように動的に構築されるかを決定する。たとえば、ポインタが空リストに挿入された場合、そのポインタに添付されたノードは、TimeSlotIndexがこのリストに到達したとき、最初に探索される。あるいは、そのリストがノードを指すポインタをすでに含む場合、付加されたノードは既存のノードにリンクされる。
【００６５】
TimeSlotIndexの値が記憶されたとき、ＧＢサーバは送信準備ができている別のセルを探索する次の反復で同じアレイ位置に戻る。２つのキューのための処理間隔は同じままで、RealTimeCounterが１だけ増分されるので、次いで同じリストからの別のキューが処理されるとすると、この次のキューは、次のアレイ位置で処理されるように再スケジュールされ、それによって、キューが１つの位置に集中されることからアレイのあちこちに分散されるように、キューが分配される。
【００６６】
４）セルが見つけられなかった場合、
エクストラ帯域幅アレイ３１は、エクストラ帯域幅３１中の現在の位置から始めて、探索される。
【００６７】
１）セルが見つけられた場合、エクストラ帯域幅アレイ３１中の位置が記憶され、セルは取り出され送信される。これでこのタイムスロットでの優先スケジューラは完了する。
【００６８】
２）セルが見つけられなかった場合、優先スケジューラはアイドル・セルを送り完了する。
【００６９】
保証帯域幅アレイ２１は、２つのポインタ、RealTimeCounterおよびTimeSlotlndexを有する、処理されるキューのリストの循環アレイと見なされてもよい。RealTimeCounterは、１セル送信時間ごとに１回増分される。
【００７０】
ＧＢアレイ（循環リスト）の末尾に達したとき、この動作はアレイの先頭に戻る。
【００７１】
上記の説明の例として、RealTimeCounterおよびTimeSlotIndexが両方とも値「Ｎ」を有すると仮定されてもよい。保証帯域幅アレイ２１のＮ番目の要素、ＧＢアレイ［Ｎ］は、タイムスロット「Ｎ」で処理されるのを待っている全てのキューのリストを指すことができる。たとえば、タイムスロット「Ｎ」で処理されるのを待っているキューが３つある場合、保証帯域幅アレイ２１のＮ番目の要素は、３つの連続するタイムスロットの間中に１回に１つ処理されなければならない３つのキューのリストを指す。
【００７２】
アレイ位置ＧＢアレイ［Ｎ］によって指されるリンク・リスト中の３つのキューのそれぞれは、その逆数が処理間隔Ｉである特定の速度で処理されるべきである。第１のキューはTimeSlot［Ｎ］で、第２のキューはTimeSlot［Ｎ＋１］で、第３のキューはTimeSlot［Ｎ＋２］で処理される。次に、３つのキューは、それぞれ３つの異なるタイムスロット、TimeSlot［Ｎ＋ｌ］、TimeSlot［Ｎ＋１＋１］、およびTimeSlot［Ｎ＋２＋１］で処理されるようにスケジュールされ、そうすることによって、これらのキューは１つのアレイ位置に集中されるのではなく、アレイのあちこちに分散されるようになる。
【００７３】
これらのキューが次に処理されるようになったとき、送信準備ができているセルを探し出すのに必要な探索が、したがって計算が、軽減される。
【００７４】
探索は必要がない。すなわち、探索が不要になり、したがって探索に関連する計算に伴うオーバーヘッドもなくなる。文献中の他の方法は、多くの計算を必要とする、送信するのに最適のセル用の構造を探索するという考えに基づく。
【００７５】
３つのキューが処理された後、TimeSlotIndexは３つのセル間隔だけRealTimeCounterより遅れる。TimeSlotIndexは、トラフィックが広告された速度で処理されることを保証するために、空リストを指す保証帯域幅アレイ２１のいくつかの連続する要素に出会うことによって、RealTimeCounterに追いつかなければならない。
【００７６】
TimeSlotIndexは、空リストに出会う間、１セル間隔ごとに２回の増分に制限され、保証帯域幅アレイ２１中に送信すべきセルが１つもなかった場合は、エクストラ帯域幅アレイ３１の探索が呼び出される、すなわち、２つの連続する空のアレイ位置の探索が生じた場合は、探索の終了が発生する。
【００７７】
このようにして、空リストの過剰な探索なしに、１セル間隔ごとに１つのセルが送信されてもよく、キューはリアル・タイムで処理される。
【００７８】
図５および６はそれぞれ、送信のために配列される２６個のセルのシーケンス上で動作する、本発明のアルゴリズム中の５つの連続するステップを示す。
【００７９】
図５のダイアグラム５１では、７つのキューが送信を待っていて、それぞれ同一のクオリティ・オブ・サービス要件を有し、同一の処理間隔を有する。
【００８０】
ダイアグラム５２に示されているように、最初、第１タイムスロット中に、ＱＡのセルが送信される。次いで、ＱＡを指すポインタがＧＢアレイ２１中の位置ＧＢ１０に移される。この位置は、ここではゼロの（モジュロ演算なので、タイムスロットの起点で、ＧＢアレイの末尾からゼロに増分されている）RealTimeCounter値と、ここでは１０スロット間隔であるＱＡ用処理間隔との合計として計算される。
【００８１】
次のタイムスロットでは、次いでＱＢが処理され、ＱＢを指すポインタは、RealTimeCounterが１だけ増分したとき、このアレイ中の位置ＧＢ１１、つまりＱＡの１つ後の位置に移される。
【００８２】
この後、ダイアグラム５３に示されているように、７つのキューが全て処理されスケジュールされてしまうまで、残りのキューが処理される。
【００８３】
次に、ＧＢアレイ中の空の位置、ＧＢ７〜ＧＢ９に出会い、その結果、ＥＢアレイ３１のキューがラウンドロビン方式で処理される。TimeSlotIndexは、１スロット間隔ごとに２つの連続するリストの探索に限定されているので、ＧＢ６（セルが見つけられたため、TimeSlotIndexの値が前に記憶されていたので、探索はＧＢ６から始まる）およびＧＢ７は、ＥＢキューが処理される前に探索される。次いで、ＧＢ８およびＧＢ９が探索され、別のＥＢキューが処理される。次のスロット間隔では、ＧＢ１０が探索され、そこで、ＧＢ１０のＱＡ中のセルが見つけられ送信される。
【００８４】
次いで、ダイアグラム５４および５５で、上記と同じようにキューが処理されスケジュールされる。
【００８５】
２つのＥＢキューが処理されたので、（RealTimeCounterが９の場合）ＱＡが第１０タイムスロットで再度処理され、ＧＢ２０で再度送信されるようにスケジュールされる。ここでのキューの処理間隔は、１０スロット間隔の１０＋１０＝２０である。ＱＡをＢＧ２０に置くのは、この処理間隔のためである。
【００８６】
図６では、ＱＡ〜ＱＣは、ＱＤ〜ＱＧとは異なるクオリティ・オブ・サービス要件を有する。すなわち、ＱＡ〜ＱＣは、１１スロット間隔の処理間隔を有し、ＱＤ〜ＱＧは、１０スロット間隔の処理間隔を有する。
【００８７】
ダイアグラム６１および６２では、キューはダイアグラム５１および５２のキューと同様に処理される。しかし、ダイアグラム６３では、ＱＣおよびＱＤの処理間隔が異なる結果、２つのキューが同じタイムスロットで処理されるようにスケジュールされることになる。
【００８８】
ＱＣは最初、第３タイムスロットで処理され、その後、ＱＣを指すポインタがRealTimeCounter値２と処理間隔１１との合計によって計算された位置に移されたので、その結果、ＱＣはＧＢ１３に置かれている。ＱＤは第４タイムスロットで処理され、RealTimeCounter値３と処理間隔１０との合計によって計算された位置に移されたので、その結果、ＱＤもＧＢ１３に置かれている。
【００８９】
キューＱＤおよびＱＡのセルの送信の間に、２つのＥＢキューが処理される。ＧＢ７およびＧＢ８がキューを指していないときは、第１ＥＢキューは次のタイムスロットの間に処理され、第２ＥＢキューはその後のタイムスロットの間に処理される。
【００９０】
ＱＣが第１２タイムスロットで再度処理されるようになったとき、RealTimeCounterが１１の場合は、ＱＣがアレイ位置ＧＢ２２にスケジュールされるが、第１３タイムスロットでは、ＱＤがＧＢ２２にスケジュールされ、それによって、この２つのキューがアレイに沿って配置される。
【００９１】
本明細書に記載されたもの以外のデータ構造またはアルゴリズムが、特許請求の範囲に記載の本発明の範囲から逸脱することなく利用され得ることは、当業者には明らかであろう。
【００９２】
たとえば、本発明は、本明細書中ではリンク・リストの探索を２つの空の位置に限定するものとして説明されてきたが、１つのタイムスロット中に探索されるべきリンク・リストの数とTimeSlotIndexがRealTimeCounterに追いつく速度との間で設計の選択が存在する。
【００９３】
図５および６のそれぞれは、送信のために配列される２６個のセルのタイムスロットのシーケンス上で動作する、本発明のアルゴリズムでの５つの連続するステップを示す。
【００９４】
図５は、タイムスロットＴＳ０中の、キューと保証帯域幅アレイ中の要素との最初の関連を示す。どのキューの時間間隔も１０である。［５２］は１タイムスロット後の状況を示し、（ＴＳ１）でのＱＡは１つのセルを送信のためにデキューされ、保証帯域幅アレイ位置１０に移されている。［５３］は、タイムスロットＴＳ７での状況を示す。ＱＢおよびＱＧは今送信のために１つのセルをデキューされたばかりであり、ＱＡおよびＱＧは保証帯域幅アレイ位置１０〜１６を占める。［５３］は、タイムスロット１０での状況を示す。ＱＡ〜ＱＧは依然として保証帯域幅アレイ位置１０〜１６を占める。［５５］は、タイムスロットＴＳ１２での状況を示す。図５の意図は、全てのキューが同じ速度で処理される（したがって、等しい時間間隔を有する）シナリオを１ステップずつ進めることである。
【００９５】
図６の意図は、キューが異なる速度で処理される（したがって、等しい時間間隔を有しない）シナリオを１ステップずつ進めることである。［６３］はＴＳ１１での状況を示す。保証帯域幅アレイ位置１３は、今度は２つの要素ＱＤおよびＱＣを有するリンク・リストを指していることに留意されたい。ＴＳ１８では、保証帯域幅アレイはやはりそれぞれ１つの要素を含むリンク・リストを指す。タイムスロットへのキューの分配はやはりフラットになる。
【図面の簡単な説明】
【００９６】
【図１】従来技術で知られている、保証帯域幅サーバおよびエクストラ帯域幅サーバ用の厳密優先サーバの図である。
【図２】本発明の特徴を実施した保証帯域幅リストを示す図である。
【図３】本発明の特徴を実施したエクストラ帯域幅リストを示す図である。
【図４】本発明の特徴を実施した保証帯域幅リストとエクストラ帯域幅リストの組合せを示す図である。
【図５】本発明による、処理をするためのセル構造を示す図である。
【図６】本発明による、処理をするためのセル構造を示す図である。
【図１】
2007504735.tif 000003
【図２】
2007504735.tif 000004
【図３】
2007504735.tif 000005
【図４】
2007504735.tif 000006
【図５】
2007504735.tif 000007
【図６】
2007504735.tif 000008
【国際調査報告】
2007504735.tif 000009
2007504735.tif 000010
2007504735.tif 000011