(57)【特許請求の範囲】
【請求項１】
（ａ）パケットキューの第１のセットからパケットキューを選択し、及び（ｂ）選択される当該パケットキューから中間パケットキューの第１のセットに含まれる中間パケットキューへパケットを移動させるように動作可能であって、スケジューリングノードの第１のセットに対応する情報を用いてパケットキューの前記選択を実行するように構成される第１のスケジューリングエンジンと、
（ａ）パケットキューの第２のセットからパケットキューを選択し、及び（ｂ）選択される当該パケットキューから中間パケットキューの第２のセットに含まれる中間パケットキューへパケットを移動させるように動作可能であって、スケジューリングノードの第２のセットに対応する情報を用いてパケットキューの前記選択を実行するように構成される第２のスケジューリングエンジンと、
（ａ）前記中間パケットキューの第１のセット及び前記中間パケットキューの第２のセットを含むパケットキューのセットからパケットキューを選択し、及び（ｂ）選択される当該パケットキューから送信キューへパケットを移動させるように動作可能な第３のスケジューリングエンジンと、
前記送信キューからのパケットを通信リンク上へ送信するように構成されるパケット送信器と、
を備え、
前記第１のスケジューリングエンジン及び前記第２のスケジューリングエンジンは、当該第１のスケジューリングエンジンと当該第２のスケジューリングエンジンとの間で状態情報が共有される必要がないように互いに独立してパケットキューを選択するように構成される、
パケットスケジューリング装置であって、
前記パケットスケジューリング装置により受信されるパケットは、当該パケットが属するパケットフローに関連付けられるパケットキューに格納される、
パケットスケジューリング装置。
【請求項２】
前記第１のスケジューリングエンジン及び前記第２のスケジューリングエンジンは、ソフトウェアベースのスケジューリングエンジンであり、前記第３のスケジューリングエンジンは、特定用途向け集積回路（ＡＳＩＣ）におけるロジックとして実装される純粋なハードウェアベースのスケジューリングエンジンである、請求項１に記載のパケットスケジューリング装置。
【請求項３】
前記パケットキューの第１のセットに含まれるパケットキューのセットは、第１のパケットフローに関連付けられ、
前記パケットキューの第２のセットに含まれるパケットキューのセットは、第２のパケットフローに関連付けられ、
前記パケットスケジューリング装置は、（ａ）パケットを受信し、（ｂ）当該パケットが属するパケットフローを判定し、及び（ｃ）当該パケットフローに関連付けられるパケットキューに当該パケットを格納するように構成されるパケット受信及び処理ユニット（ＰＲＰＵ）をさらに備える、
請求項１に記載のパケットスケジューリング装置。
【請求項４】
前記第３のスケジューリングエンジンは、前記中間パケットキューの第１のセット、前記中間パケットキューの第２のセット、及びパケットキューの第３のセットを含むパケットキューのセットからパケットキューを選択するように動作可能であり、
前記パケットキューの第３のセットに含まれるパケットキューのセットは、第３のパケットフローに関連付けられ、
（ａ）前記ＰＲＰＵがパケットを受信し及び当該パケットは前記第１のパケットフローに属すると判定する場合、前記ＰＲＰＵは、前記第１のパケットフローに関連付けられる前記パケットキューのセットに含まれる前記パケットキューのうちの１つに当該パケットを格納し、（ｂ）前記ＰＲＰＵがパケットを受信し及び当該パケットは前記第２のパケットフローに属すると判定する場合、前記ＰＲＰＵは前記第２のパケットフローに関連付けられる前記パケットキューのセットに含まれる前記パケットキューのうちの１つに当該パケットを格納し、並びに、（ｃ）前記ＰＲＰＵがパケットを受信し及び当該パケットは前記第３のパケットフローに属すると判定する場合、前記ＰＲＰＵは前記第３のパケットフローに関連付けられる前記パケットキューのセットに含まれる前記パケットキューのうちの１つに当該パケットを格納する、ように前記ＰＲＰＵは構成される、
請求項３に記載のパケットスケジューリング装置。
【請求項５】
前記スケジューリングノードの第１のセットは、スケジューリングツリーの第１のサブツリーからのスケジューリングノードを含み、前記スケジューリングノードの第２のセットは、当該スケジューリングツリーの第２の異なるサブツリーからのスケジューリングノードを含む、請求項１に記載のパケットスケジューリング装置。
【請求項６】
前記スケジューリングツリーを定義する情報を検査し、前記第１のスケジューリングエンジンに前記スケジューリングツリーの第１のサブツリーを割り当て、及び前記第２のスケジューリングエンジンに前記スケジューリングツリーの第２の異なるサブツリーを割り当てるように構成される構成モジュール、
をさらに備える、請求項５に記載のパケットスケジューリング装置。
【請求項７】
前記スケジューリングノードの第１のセットは、前記スケジューリングノードの第２のセットにも含まれるスケジューリングノードのセットを含む、請求項１に記載のパケットスケジューリング装置。
【請求項８】
前記スケジューリングノードの第１のセットに対応する前記情報は、（ａ)前記スケジューリングノードの第１のセットに含まれる前記スケジューリングノードのうちの１つに関連付けられる第１の最大データレート情報と、（ｂ）第１のスケジューリングアルゴリズムを識別する情報と、を含み、
前記スケジューリングノードの第２のセットに対応する前記情報は、（ａ)前記スケジューリングノードの第２のセットに含まれる前記スケジューリングノードのうちの１つに関連付けられる第２の最大データレート情報と、（ｂ）第２のスケジューリングアルゴリズムを識別する情報と、を含む、
請求項１に記載のパケットスケジューリング装置。
【請求項９】
前記第１のスケジューリングエンジンは、前記第１の最大データレート情報及び前記第１のスケジューリングアルゴリズムを用いてパケットが除去されるべきパケットキューを選択するように構成され、
前記第２のスケジューリングエンジンは、前記第２の最大データレート情報及び前記第２のスケジューリングアルゴリズムを用いてパケットが除去されるべきパケットキューを選択するように構成される、
請求項８に記載のパケットスケジューリング装置。
【請求項１０】
前記第１のスケジューリングエンジンは、
データ処理システムと、
当該データ処理システムがアクセス可能なコンピュータ読取可能な媒体であって、当該データ処理システムによって実行される場合、当該データ処理システムに（ａ）前記パケットキューの第１のセットからパケットキューを選択させ、及び（ｂ）選択される当該パケットキューから前記中間パケットキューの第１のセットに含まれる中間パケットキューへパケットを移動させる、コンピュータ読取可能なプログラムコードを記憶するコンピュータ読取可能な媒体と、
を備える、請求項１に記載のパケットスケジューリング装置。
【請求項１１】
パケットスケジューリング方法であって、当該方法は、
パケットキューの第１のセットを第１のスケジューリングエンジンに割り当てることと、
パケットキューの第２のセットを第２のスケジューリングエンジンに割り当てることと、
第１のパケットフローを前記パケットキューの第１のセットに含まれるパケットキューのセットに割り当てることと、
第２のパケットフローを前記パケットキューの第２のセットに含まれるパケットキューのセットに割り当てることと、
ネットワークエレメントのネットワークインタフェースにおいてパケットを受信することと、
前記パケットが属するパケットフローを判定することと、
受信される前記パケットが前記第１のパケットフローに属する場合、受信される前記パケットが前記第１のパケットフローに属すると判定することに応じて、前記第１のパケットフローが割り当てられる前記パケットキューのセットに含まれる前記パケットキューのうちの１つに受信される前記パケットを格納することと、
受信される前記パケットが前記第２のパケットフローに属する場合、受信される前記パケットが前記第２のパケットフローに属すると判定することに応じて、前記第２のパケットフローが割り当てられる前記パケットキューのセットに含まれる前記パケットキューのうちの１つに受信される前記パケットを格納することと、
前記第１のスケジューリングエンジンは、（ａ）前記パケットキューの第１のセットからパケットキューを選択し、及び（ｂ）選択される前記パケットキューから中間パケットキューの第１のセットに含まれる中間パケットキューへパケットを移動させることと、
前記第２のスケジューリングエンジンは、（ａ）前記パケットキューの第２のセットからパケットキューを選択し、及び（ｂ）選択される前記パケットキューから中間パケットキューの第２のセットに含まれる中間パケットキューへパケットを移動させることと、
第３のスケジューリングエンジンは、（ａ）前記中間パケットキューの第１のセット及び前記中間パケットキューの第２のセットを含むパケットキューのセットからパケットキューを選択し、及び（ｂ）選択される前記パケットキューから送信キューへパケットを移動させることと、
前記ネットワークインタフェースのパケット送信器は、前記送信キューからのパケットを通信リンク上へ送信することと、
を含む、方法。
【請求項１２】
前記第１のスケジューリングエンジン及び前記第２のスケジューリングエンジンは、当該第１のスケジューリングエンジンと当該第２のスケジューリングエンジンとの間で状態情報が共有される必要がないように互いに独立してパケットキューを選択するように構成される、請求項１１に記載の方法。
【請求項１３】
前記第１のスケジューリングエンジンは、階層的に配列されるスケジューリングノードの第１のセットを含む第１のスケジューリングツリーに対応する情報を用いてパケットキューの前記選択を実行し、
前記第２のスケジューリングエンジンは、階層的に配列されるスケジューリングノードの第２のセットを含む第２のスケジューリングツリーに対応する情報を用いてパケットキューの前記選択を実行する、
請求項１１に記載の方法。
【請求項１４】
前記スケジューリングノードの第１のセットは、スケジューリングツリーの第１のサブツリーからのスケジューリングノードを含み、前記スケジューリングノードの第２のセットは、当該スケジューリングツリーの第２の異なるサブツリーからのスケジューリングノードを含む、請求項１３に記載の方法。
【請求項１５】
前記スケジューリングノードの第１のセットに対応する前記情報は、（ａ）前記スケジューリングノードの第１のセットに含まれる前記スケジューリングノードのうちの１つに関連付けられる第１の最大データレート情報と、（ｂ）第１のスケジューリングアルゴリズムと、を含み、
前記スケジューリングノードの第２のセットに対応する前記情報は、（ａ）前記スケジューリングノードの第２のセットに含まれる前記スケジューリングノードのうちの１つに関連付けられる第２の最大データレート情報と、（ｂ）第２のスケジューリングアルゴリズムと、を含む、
請求項１３に記載の方法。
【請求項１６】
前記第１のスケジューリングエンジンは、前記第１の最大データレート情報及び前記第１のスケジューリングアルゴリズムを用いてパケットが除去されるべきパケットキューを選択するように構成され、
前記第２のスケジューリングエンジンは、前記第２の最大データレート情報及び前記第２のスケジューリングアルゴリズムを用いてパケットが除去されるべきパケットキューを選択するように構成される、
請求項１５に記載の方法。
【請求項１７】
前記第１のスケジューリングエンジン及び前記第２のスケジューリングエンジンは、ソフトウェアベースのスケジューリングエンジンであり、前記第３のスケジューリングエンジンは、純粋なハードウェアベースのスケジューリングエンジンである、請求項１１に記載の方法。
【請求項１８】
前記第１のスケジューリングエンジン及び前記第２のスケジューリングエンジンは、アセンブリコードを用いて実装され、前記第３のスケジューリングエンジンは、特定用途向け集積回路（ＡＳＩＣ）におけるロジックとして実装される、請求項１７に記載の方法。
【請求項１９】
前記第３のスケジューリングエンジンは、前記中間パケットキューの第１のセット、前記中間パケットキューの第２のセット、及びパケットキューの第３のセットを含むパケットキューのセットからパケットキューを選択し、
第３のパケットフローが、前記パケットキューの第３のセットに含まれるパケットキューのセットに割り当てられ、
前記方法は、受信される前記パケットが前記第３のパケットフローに属すると判定することに応じて、前記第３のパケットフローが割り当てられる前記パケットキューのセットに含まれる前記パケットキューのうちの１つに受信される前記パケットを格納すること、をさらに含む、
請求項１１に記載の方法。
【請求項２０】
（ｉ）前記パケットキューの第１のセットに含まれるパケットキューのセットと、（ｉｉ）前記パケットキューの第２のセットに含まれるパケットキューのセットと、に第３のパケットフローを割り当てることと、
受信される前記パケットが前記第３のパケットフローに属する場合、ロードバランサを用いて、前記第３のパケットフローが割り当てられる前記パケットキューのうちの１つに受信される前記パケットを格納することと、
をさらに含む、請求項１１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケットスケジューリングに関する。本明細書において、「パケット（packet）」という用語は、例えば、ＯＳＩモデルの任意の層（例えば、ネットワーク層、トランスポート層、データ物理通信リンク層、アプリケーション層等）における任意の単位のデータを包含するように広く用いられる。
【背景技術】
【０００２】
パケットスケジューリングは、複数のパケットが共通のアウトゴーイング通信リンク（例えば、物理通信リンク又は疑似ワイヤ）について競合する場合に必要である。このシナリオは、一般にルータ（及び他のネットワークエレメント）において発生する。最も単純な場合、ルータは、第１のネットワークを第２のネットワークに接続する。つまり、ルータの第１のネットワークインタフェースを第１のネットワークに接続する第１の物理通信リンク、及び当該ルータの第２のネットワークインタフェースを第２のネットワークに接続する第２の物理通信リンクが存在し、それによって、当該ルータが２つのネットワーク間でパケットをルーティングすることを可能にする。ルータは、第２のネットワーク内のノードを宛先とするパケットを第１のネットワークから第１の物理通信リンクを介して受信し得る。ある時点において、これらのパケットがルータに到来するレートは、当該ルータが第２の物理通信リンクへパケットを送信することができるレートを超過し得る（例えば、第２の物理通信リンクは、第１の物理通信リンクよりも低い帯域幅を有し得る）。従って、ルータは、パケットキューを採用して、受信されるパケットを一時的に格納し得る。従って、任意の所与の時点で、ルータはそのパケットキュー中に第１のネットワークから受信され且つ第２のネットワークを宛先とする複数のパケットを格納している可能性がある。ルータを第２のネットワークに接続するのは単一の物理通信リンクであり得るため、キューに入れられたパケットは全て、この共通のアウトゴーイング物理通信リンクについて「競合する（compete）」。そのため、ルータは、何らかのパケットスケジューリングの方法を必要とする。つまり、ルータは、キューに入れられたパケットのうちのいずれがアウトゴーイング送信について次の番になるかを選択するための何らかの手法を必要とする。
【０００３】
１つのパケットスケジューリング技法は、（ａ）ルートスケジューリングノードと、各リーフスケジューリングノードがパケットキューに関連付けられるリーフスケジューリングノードのセットと、ゼロ以上のアグリゲートスケジューリングノードと、を有するスケジューリングツリーを生成することと、（ｂ）リーフスケジューリングノードに到達するようにスケジューリングツリーを継続的に走査し（traverse）、及び当該リーフスケジューリングノードから送信キューへパケットを移動させるためのスケジューリングエンジンを採用することと、を含む。この技法の問題は、特に、メモリ帯域幅の制限及び各スケジューリングノードの共有状態情報にアクセスし及び更新するためのコンテンションオーバーヘッドに起因して、スケジューリングエンジンの性能が制限され得ることである。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
それ故に、望ましいのは、改良されたパケットスケジューリング処理である。
【課題を解決するための手段】
【０００５】
ルータ（又は他のネットワークエレメント）のネットワークインタフェースにおけるパケットスケジューリングを改良するための方法及び装置が、本明細書において説明される。１つの方法は、ネットワークインタフェースにおいて送信のために（例えば、物理通信リンク又はポート疑似ワイヤ又はリンクアグリゲーショングループ（ＬＡＧ）上での送信のために）バッファリングされるパケットを各々がスケジューリングツリーによって表される複数のスケジューリングドメインに分割し、各スケジューリングツリーを別個のバーチャルポートスケジューリングエンジンに割り当て、及び最上位のスケジューリングエンジンを採用して、バーチャルポートスケジューリングエンジンの出力間でスケジューリングして、バッファリングされたパケットのいずれを送信すべきかの最終的な選択を行う（例えば、ネットワークインタフェースの送信キューへ移動させる）ことである。
【０００６】
バーチャルポートスケジューリングエンジンを並行して且つ互いに独立して動作させることは、個々のスケジューリング決定ごとに考慮されなければならない共有状態の量を大きく低減する。結果として、この技法により、パケットが送信キューに移動されることができるレートは大幅に増加し得る。従って、ネットワークインタフェースが高速通信リンク（例えば、１００ギガビット／秒（Ｇｂｐｓ）の物理通信リンク）に接続される場合、当該通信リンクの全帯域幅を利用するのに充分なくらい高速に動作するためのスケジューリングシステムの能力は強化される。
【０００７】
従って、１つの態様において、パケットスケジューリング装置が提供される。幾つかの実施形態において、パケットスケジューリング装置は、以下を備える：第１のスケジューリングエンジン（例えば、第１のバーチャルポートスケジューリングエンジン）；第２のスケジューリングエンジン（例えば、第２のバーチャルポートスケジューリングエンジン）；及び第３のスケジューリングエンジン（例えば、最上位のスケジューリングエンジン）。第１のスケジューリングエンジンは、（ａ）パケットキューの第１のセットからパケットキューを選択し、及び（ｂ）選択される当該パケットキューから中間パケットキューの第１のセットに含まれる中間パケットキューへパケットを移動させるように動作可能である。第１のスケジューリングエンジンは、スケジューリングノードの第１のセット（例えば、スケジューリングツリーを形成する、階層的に配列されるスケジューリングノードのセット）に対応する情報を用いてパケットキューの上記選択を実行するように構成され得る。
【０００８】
第１のスケジューリングエンジンのように、第２のスケジューリングエンジンは、（ａ）パケットキューの第２のセットからパケットキューを選択し、及び（ｂ）選択される当該パケットキューから中間パケットキューの第２のセットに含まれる中間パケットキューへパケットを移動させるように動作可能である。第２のスケジューリングエンジンは、スケジューリングノードの第２のセットに対応する情報を用いてパケットキューの上記選択を実行するように構成され得る。幾つかの実施形態において、第１のスケジューリングエンジン及び第２のスケジューリングエンジンは、当該第１のスケジューリングエンジンと当該第２のスケジューリングエンジンとの間で状態情報が共有される必要がないように互いに独立してパケットキューを選択するように構成される。第３のスケジューリングエンジンは、（ａ）中間パケットキューの第１のセット及び中間パケットキューの第２のセットを含むパケットキューのセットからパケットキューを選択し、及び（ｂ）選択される当該パケットキューから送信キューへパケットを移動させるように動作可能である。
【０００９】
幾つかの実施形態において、パケットスケジューリング装置は、ネットワークインタフェースにおいて実装されてもよく、送信キューからのパケットを通信リンク上へ送信するように構成されるパケット送信器も備える。
【００１０】
幾つかの実施形態において、第１のスケジューリングエンジン及び第２のスケジューリングエンジンは、プロセッサにロードされ及びプロセッサによって実行されるコンピュータコードを記憶したコンピュータ読取可能な媒体を含むソフトウェアベースのスケジューリングエンジンであり、第３のスケジューリングエンジンは、特定用途向け集積回路（ＡＳＩＣ：application  specific  integrated  circuit）を用いて実装される純粋なハードウェアベースのスケジューリングエンジンである。
【００１１】
幾つかの実施形態において、パケットキューの第１のセットに含まれるパケットキューのセットは、第１のパケットフローに関連付けられ、パケットキューの第２のセットに含まれるパケットキューのセットは、第２のパケットフローに関連付けられ、パケットスケジューリング装置は、（ａ）パケットを受信し、（ｂ）当該パケットが属するパケットフローを判定し、及び（ｃ）当該パケットフローに関連付けられる出口パケットキューに当該パケットを格納するように構成されるパケット受信及び処理ユニット（ＰＲＰＵ：packet  receiving  and  processing  unit）をさらに備える。ＰＲＰＵは、ソフトウェアベース（例えば、ＰＲＰＵは、プロセッサにロードされ及びプロセッサによって実行されるコンピュータコードを記憶したコンピュータ読取可能な媒体を含み得る）、又はハードウェアベース（例えば、ＰＲＰＵは、特定用途向け集積回路（ＡＳＩＣ）を用いて実装され得る）であり得る。
【００１２】
幾つかの実施形態において、第３のスケジューリングエンジンは、中間パケットキューの第１のセット、中間パケットキューの第２のセット、及びパケットキューの第３のセットを含むパケットキューのセットからパケットキューを選択するように動作可能であり、当該パケットキューの第３のセットに含まれるパケットキューのセットは、第３のパケットフローに関連付けられる。そのような実施形態において、ＰＲＰＵは、以下のように構成される：（ａ）ＰＲＰＵがパケットを受信し及び当該パケットは第１のパケットフローに属すると判定する場合、ＰＲＰＵは、第１のパケットフローに関連付けられるパケットキューのセットに含まれるパケットキューのうちの１つに当該パケットを格納し、（ｂ）ＰＲＰＵがパケットを受信し及び当該パケットは第２のパケットフローに属すると判定する場合、ＰＲＰＵは第２のパケットフローに関連付けられるパケットキューのセットに含まれるパケットキューのうちの１つに当該パケットを格納し、並びに、（ｃ）ＰＲＰＵがパケットを受信し及び当該パケットは第３のパケットフローに属すると判定する場合、ＰＲＰＵは第３のパケットフローに関連付けられるパケットキューのセットに含まれるパケットキューのうちの１つに当該パケットを格納する。
【００１３】
幾つかの実施形態において、スケジューリングノードの第１のセットは、スケジューリングツリーの第１のサブツリーからのスケジューリングノードを含み、スケジューリングノードの第２のセットは、当該スケジューリングツリーの第２の異なるサブツリーからのスケジューリングノードを含む。そのような実施形態において、構成モジュールは、スケジューリングツリーを定義する情報を検査し、第１のスケジューリングエンジンにスケジューリングツリーの第１のサブツリーを割り当て、及び第２のスケジューリングエンジンに当該スケジューリングツリーの第２の異なるサブツリーを割り当てるように構成され得る。
【００１４】
幾つかの実施形態において、スケジューリングノードの第１のセットは、スケジューリングノードの第２のセットにも含まれるスケジューリングノードのセットを含む。
【００１５】
幾つかの実施形態において、スケジューリングノードの第１のセットに対応する情報は、（ａ)スケジューリングノードの第１のセットに含まれるスケジューリングノードのうちの１つに関連付けられる第１の最大データレート情報と、（ｂ）第１のスケジューリングアルゴリズムを識別する情報と、を含み、スケジューリングノードの第２のセットに対応する情報は、（ａ)スケジューリングノードの第２のセットに含まれるスケジューリングノードのうちの１つに関連付けられる第２の最大データレート情報と、（ｂ）第２のスケジューリングアルゴリズムを識別する情報と、を含む。
【００１６】
幾つかの実施形態において、第１のスケジューリングエンジンは、第１の最大データレート情報及び第１のスケジューリングアルゴリズムを用いてパケットが除去されるべきパケットキューを選択するように構成され、第２のスケジューリングエンジンは、第２の最大データレート情報及び第２のスケジューリングアルゴリズムを用いてパケットが除去されるべきパケットキューを選択するように構成される。
【００１７】
幾つかの実施形態において、第１のスケジューリングエンジンは、データ処理システムと、当該データ処理システムがアクセス可能なコンピュータ読取可能な媒体と、を備える。コンピュータ読取可能な媒体は、データ処理システムによって実行される場合、当該データ処理システムに（ａ）パケットキューの第１のセットからパケットキューを選択させ、及び（ｂ）選択される当該パケットキューから中間パケットキューの第１のセットに含まれる中間パケットキューへパケットを移動させるコンピュータ読取可能なプログラムコードを記憶し得る。
【００１８】
別の態様において、パケットスケジューリング方法が提供される。幾つかの実施形態において、パケットスケジューリング方法は、以下のステップを含む：パケットキューの第１のセットを第１のスケジューリングエンジンに割り当てることと；パケットキューの第２のセットを第２のスケジューリングエンジンに割り当てることと；第１のパケットフローをパケットキューの第１のセットに含まれるパケットキューのセットに割り当てることと；第２のパケットフローをパケットキューの第２のセットに含まれるパケットキューのセットに割り当てることと；ネットワークエレメントのネットワークインタフェースにおいてパケットを受信することと；当該パケットが属するパケットフローを判定することと；受信されるパケットが第１のパケットフローに属する場合、受信される当該パケットが第１のパケットフローに属すると判定することに応じて、第１のパケットフローが割り当てられるパケットキューのセットに含まれるパケットキューのうちの１つに受信される当該パケットを格納することと；受信される当該パケットが第２のパケットフローに属する場合、受信される当該パケットが第２のパケットフローに属すると判定することに応じて、第２のパケットフローが割り当てられるパケットキューのセットに含まれるパケットキューのうちの１つに受信される当該パケットを格納すること。
【００１９】
幾つかの実施形態において、第１のスケジューリングエンジンは、（ａ）パケットキューの第１のセットからパケットキューを選択し、及び（ｂ）選択されるパケットキューから中間パケットキューの第１のセットに含まれる中間パケットキューへパケットを移動させる、第２のスケジューリングエンジンは、（ａ）パケットキューの第２のセットからパケットキューを選択し、及び（ｂ）選択されるパケットキューから中間パケットキューの第２のセットに含まれる中間パケットキューへパケットを移動させ、第３のスケジューリングエンジンは、（ａ）中間パケットキューの第１のセット及び中間パケットキューの第２のセットを含むパケットキューのセットからパケットキューを選択し、及び（ｂ）選択されるパケットキューから送信キューへパケットを移動させる。ネットワークインタフェースのパケット送信器は、送信キューからのパケットを通信リンク上へ送信するように構成される。
【００２０】
上記及び他の態様及び実施形態は、添付の図面を参照しつつ以下に説明される。
【図面の簡単な説明】
【００２１】
本明細書に包含され且つ本明細書の一部を構成する添付の図面は、本発明の種々の実施形態を例示し、説明と共に、本発明の原理を説明し及び関連する技術分野における当業者が本発明を実施し及び使用することを可能にする役割をさらに果たす。図面において、同様の参照番号は、同一の要素又は帰納的に同様の要素を示す。
【００２２】
【図１】エッジルータを含む通信システムを例示する。
【図２】エッジルータのネットワークインタフェースの機能図である。
【図３】例示的なスケジューリングツリーを例示する。
【図４】スケジューリングツリーが複数のサブツリーに分割されることができる１つの取り得る手法を例示する。
【図５】一実施形態に係るスケジューリングシステムの機能図である。
【図６】スケジューリングツリーが複数のサブツリーに分割されることができる別の取り得る手法を例示する。
【図７】別の実施形態に係るスケジューリングシステムの機能図である。
【図８】特定の実施形態に係る種々の処理を例示するフローチャートである。
【図９】通信システムを例示する
【図１０】階層的に配列されるスケジューリングノードのセットを例示する。
【図１１】変形されたスケジューリングツリーを例示する。
【図１２】２つの変形されたスケジューリングツリーを例示する。
【図１３】幾つかの実施形態に係るスケジューリングエンジンのブロック図である。
【図１４】スケジューリングエンジンの例示的なソフトウェアコンポーネントを例示するブロック図である。
【発明を実施するための形態】
【００２３】
本明細書において、不定冠詞「ａ」及び「ａｎ」は、「１つ以上」を意味する。
【００２４】
図１は、本発明の実施形態が採用され得る通信システム１００の例を例示する。ただし、本発明は、任意の特定のタイプの通信システムに限定されない。例示される例において、通信システム１００は、ネットワーク１１０（例えば、インターネット）にパケットを送信し及び当該ネットワーク１１０からパケットを受信する複数のエンドユーザデバイス１０１を含む。図１に示されるように、ユーザデバイス１０１は、アクセスネットワーク１０３と当該アクセスネットワーク１０３をネットワーク１１０に接続するように機能するネットワークエレメント１０８（例えば、エッジルータ１０８）とを介してネットワーク１１０（例えば、ネットワーク１１０内のサーバ）と通信する。
【００２５】
示される例において、アクセスネットワーク１０３はデジタル加入者線（ＤＳＬ：digital  subscriber  line）アクセスネットワーク１０３であるが、任意のタイプのアクセスネットワーク１０３が用いられ得る。例示的なＤＳＬアクセスネットワーク１０３は、物理通信リンク１２２を介してスイッチ１０６に接続されるＤＳＬアクセスマルチプレクサ（ＤＳＬＡＭ）１０４に接続されるＤＳＬモデム１０２を含む。例えば、ＤＳＬモデム１０２は、物理通信リンク１２１を介してＤＳＬＡＭ１０４と接続され、当該ＤＳＬＡＭ１０４は、物理通信リンク１２２を介してスイッチ１０６と接続される。スイッチ１０６は、（有線又は無線であり得る）物理通信リンク１２３を介してネットワークエレメント１０８のネットワークインタフェース１９１に接続される。同様に、ネットワーク１１０は、物理通信リンク１２４を介してエッジルータ１０８のネットワークインタフェース１９２に接続される。ネットワークインタフェース１９１及び１９２は、ネットワークエレメント１０８のバックプレーンコンポーネント（例示せず）によって接続され得る。スイッチ１０６には、別のネットワーク１１２も接続され得る。
【００２６】
図２は、ネットワークエレメント１０８のネットワークインタフェース１９１のパケット出口部分の機能図である。図２に例示されるように、ネットワークインタフェース１９１は、パケット受信及び処理ユニット（ＰＲＰＵ）２０２を含む。図１に示される実施形態において、ＰＲＰＵ２０２は、ネットワークインタフェース１９２から例えばネットワークエレメント１０８のバックプレーンを介してパケットを受信する。ネットワークインタフェース１９２から受信されるパケットは、ネットワークインタフェース１９２がネットワーク１１０から受信するパケットを含む。ＰＲＰＵ２０２にパケットを提供することに加えて、ネットワークインタフェース１９２は、当該ネットワークインタフェース１９２がＰＲＰＵ２０２に提供するパケットごとに当該パケットについてのメタデータも提供する。
【００２７】
一実施形態において、ＰＲＰＵ２０２によって受信される各パケットは、単一のパケットフローに属する。この実施形態において、ＰＲＰＵ２０２によって受信される各パケットについて、ＰＲＰＵ２０２は、受信パケットが属するパケットフローを判定するように機能する。幾つかの実施形態において、ＰＲＰＵ２０２は、受信パケットが属するパケットフローを、当該パケットに含まれるパケットヘッダに含まれるデータを調べることによって又はもしあれば当該パケットについてのメタデータを調べることによって判定する。例えば、パケットヘッダ（又はメタデータ）は、１つ以上のバーチャルＬＡＮ（ＶＬＡＮ：virtual  local  area  network）タグ（例えば、アウターＶＬＡＮタグ及びインナーＶＬＡＮタグ）を含んでもよく、当該パケットが搬送しているペイロードデータのタイプ（例えば、ボイスオーバーＩＰデータなどのリアルタイムデータ、又はＨＴＴＰメッセージなどの非リアルタイムデータ）を識別する情報も含んでもよい。具体的な例として、あるアウターＶＬＡＮタグ、インナーＶＬＡＮタグ、及びペイロードタイプに関連付けられる全てのパケットは同じフローに属すると判定される一方で、異なるアウターＶＡＬＮタグ、インナーＶＬＡＮタグ、又はペイロードタイプに関連付けられる全てのパケットは異なるパケットフローに属すると判定される。
【００２８】
ＰＲＰＵ２０２は、受信パケットを、当該パケットが属する判定されたパケットフローに基づいてパケットキューに追加するようにも機能する。つまり、幾つかの実施形態において、各パケットフローは、パケットキューに関連付けられる。例えば、ネットワークインタフェース１９１は、パケットフロー対パケットキューデータベース（ＤＢ）を含み得る。当該データベースは、例えば、定義されるパケットフローのセットのうちの各々をパケットキューにマッピングする情報を格納する、データが書き込まれ及び読み出されるコンピュータ読取可能な媒体において実装され得る。図２に示されるように、ネットワークインタフェース１９１は、パケットキューのセット２０６（例えば、例示のようなパケットキューｑ１〜ｑ８）を含む。
【００２９】
例えば、ＰＲＰＵ２０２によって受信され且つネットワーク１１２を宛先とする全てのパケットが同じパケットフローに属すると仮定される場合、このパケットフローは、例えば、ｑ８に関連付けられ得る。従って、この例において、ＰＲＰＵ２０２がネットワークインタフェース１９２からネットワーク１１２を宛先とするパケット（又は当該パケットについてのメタデータ−例えば、パケット識別子、当該パケットが格納されるメモリロケーションを識別するメモリロケーション識別子、宛先アドレス情報）を受信すると、ＰＲＰＵ２０２は、当該パケットをｑ８に「追加する（add）」であろう。パケットキューのセット２０６内のパケットキューは、パケットキュー内の全てのパケットが同じストレージデバイスにおいて順番に格納されるという意味において、物理的なパケットキューである必要はない。むしろ、本明細書において説明されるパケットキューは、論理的なＦＩＦＯ（first-in-first-out）パケットキューなどの論理的なパケットキューであり得る。パケット自体は、どこに格納されてもよい。従って、パケットをパケットキューに「追加すること（adding）」は、当該パケットに関連付けられる識別子（例えば、当該パケットが格納されるメモリロケーションを識別する識別子）を、パケットキューを実装するデータ構造（例えば、連結リストデータ構造）に単に追加することから成り得る。
【００３０】
ＰＲＰＵ２０２がパケットを処理している（例えば、パケットキュー２０６のうちの１つにパケットを追加している）間、スケジューリングシステム２１２は、パケットキュー２０６のうちの１つを選択し、及び選択されるパケットキューから送信キュー２１４へパケットを移動させ続ける。並行して、パケット送信器２１６は、送信キュー２１４からＰケットを除去し、及びそれらのパケットを物理通信リンク１２３へ送信し続ける。幾つかの実施形態において、パケット送信器２１６は、パケットの送信に先立って、当該パケットにヘッダを追加し、それによって、プロトコルデータユニットを生成する。このようにして、パケットは、ネットワークインタフェース１９１の出口部分へ流れ込み及び当該出口部分から流れ出る。
【００３１】
幾つかの実施形態において、スケジューリングシステム２１２がパケットキューを選択するタイミングになると、スケジューリングシステム２１２は、スケジューリングツリーを走査して、当該スケジューリングシステム２１２が選択すべき、パケットキューのセット２０６からのパケットキューを判定する。従って、ネットワークインタフェース１９１は、スケジューリングツリーデータベース２１０を含み得る。スケジューリングツリーデータベース２１０は、スケジューリングツリーを定義する情報を格納するための、データが書き込まれ及び読み出されるコンピュータ読取可能な媒体において実装され得る。
【００３２】
図３は、スケジューリングシステム３００によって用いられ得る例示的なスケジューリングツリー３００を例示する。スケジューリングツリー３００は、デシジョンツリーの形式で論理的に体系化されるスケジューリングノードのセット（例えば、スケジューリングノード３０１〜３０４）を含み、その各々は、コンピュータ読取可能な媒体に格納されるデータ構造（例えば、互いにグループ化されるデータエレメントのセット）として実装され得る。つまり、リーフスケジューリングノードを除く各スケジューリングノードは、１つ以上の子スケジューリングノードを有し、ルートスケジューリングノードを除く各スケジューリングノードは、親を有する。より具体的には、スケジューリングツリー３００は、ルートスケジューリングノード３０１、アグリゲートスケジューリングノード（例えば、スケジューリングノード３０２、３０４、３０５、３０７及び３０８）、及びリーフスケジューリングノード（例えば、スケジューリングノード３０３、３０６及び３０９〜３１４）を含む。
【００３３】
示される例において、各リーフスケジューリングノード及び各アグリゲートスケジューリングノードは、物理通信リンク１２３へ送信され得る、ＰＲＰＵ２０２によって受信されるパケットフローのサブセットを表し、ルートスケジューリングノード３０１は、物理通信リンク１２３へ送信され得る、ＰＲＰＵ２０２によって受信される全てのパケットフローを表す。また、各リーフスケジューリングノードは、一意のパケットキューに関連付けられる。従って、スケジューリングツリー３００は、上述したようにデータベース２０４に格納され及びＰＲＰＵ２０２によって用いられるパケットフロー対パケットキューマッピングを例示する。
【００３４】
具体的な例として、リーフスケジューリングノード３０３は、ネットワーク１１２へのパケットのフローを表し、リーフスケジューリングノード３０９は、ＶＬＡＮ１．１を宛先とする音声パケット（ボイスオーバーＩＰデータなどの音声データを含むパケット）のフローを表し、リーフスケジューリングノード３１０は、ＶＬＡＮ１．１を宛先とする非音声パケットのフローを表し、アグリゲートスケジューリングノード３０５は、ＶＬＡＮ１．１を宛先とする全て（即ち、音声及び非音声）のパケットのフローを表し、及びリーフスケジューリングノード３０６は、ＶＬＡＮ１．２を宛先とする全てのパケットのフローを表す。この例において、ＶＬＡＮ１は、ＶＬＡＮ１を宛先とする全てのトラフィックがスイッチ１０６によって物理通信リンク１２２上で送信されるようにＤＳＬＡＭ１０４に関連付けられ、ＶＬＡＮ１．１は、ＶＬＡＮ１．１を宛先とする全てのトラフィックがＤＳＬＡＭ１０４によって物理通信リンク１２１上へ送信されるようにＤＳＬデバイス１０２に関連付けられると仮定される。
【００３５】
図３に例示されるように、各リーフスケジューリングノードは、ルートスケジューリングノード３０１に直接接続され、又はルートスケジューリングノード３０１に１つ以上のアグリゲートスケジューリングノードを介して間接的に接続される。例えば、リーフスケジューリングノード３０３は、ルートスケジューリングノード３０１に直接接続される一方で、リーフスケジューリングノード３１１は、ルートスケジューリングノード３０１にアグリゲートスケジューリングノード３０４及び３０７を介して接続される。同様に、各アグリゲートスケジューリングノードは、ルートスケジューリングノード３０１に直接接続され、又はルートスケジューリングノード３０１に１つ以上の他のアグリゲートスケジューリングノードを介して間接的に接続される。
【００３６】
議論したように、各スケジューリングノードは、コンピュータ読取可能な媒体に格納されるデータ構造として実装され得る。従って、幾つかの実施形態において、スケジューリングノードを実装する各データ構造は、（ｉ）別のスケジューリングノード（即ち、スケジューリングノードの親）を実装する別のデータ構造をポインティングする親スケジューリングノードポインタを格納する親ポインタデータエレメントと、（ｉｉ）各子ポインタデータエレメントが、別のスケジューリングノード（即ち、スケジューリングノードの子のうちの１つ）を実装する別のデータ構造をポインティングする子スケジューリングノードポインタを格納する、子ポインタデータエレメントのセットと、を含み得る。従って、各スケジューリングノードは、別のスケジューリングノードに対して、当該別のスケジューリングノードの親又は子であり得る。ルートノードを実装するデータ構造の場合において、当該データ構造の親スケジューリングノードポインタは、ＮＵＬＬをポインティングし得る。幾つかの実施形態において、定義によって、ルートノードは親スケジューリングノードを有しないことがあり得るためである。同様に、リーフノードを実装するデータ構造の場合において、当該データ構造の各子スケジューリングノードポインタは、ＮＵＬＬをポインティングし得る。幾つかの実施形態において、定義によって、リーフノードは如何なる子スケジューリングノードも有しないことがあり得るためである。
【００３７】
上記で議論したように、スケジューリングシステム２１２は、送信キュー２１４への配信のためのパケットを取得するパケットキューをスケジューリングツリー３００を走査することによって選択するように構成され得る。幾つかの実施形態において、スケジューリングシステム２１２は、ルートスケジューリングノード３０１から開始し及び子スケジューリングノードを選択する（例えば、ルートノード３０１を実装するデータ構造から子ポインタデータエレメントを選択する）ことによってスケジューリングツリー３００をトップダウン方式で走査する（ただし、他の実施形態において、スケジューリングシステムは、スケジューリングツリー３００をボトムアップ走査（traversal）アルゴリズムを用いて走査し得る）。幾つかの実施形態において、ルートスケジューリングノード３０１は、スケジューリングアルゴリズム（例えば、ラウンドロビン）に関連付けられ得る。また、各スケジューリングノードは、最大データレート（及び、最小ターゲットデータレートなどの他のパラメータ）に関連付けられてもよい。例えば、上記で議論したように、データ構造はスケジューリングノードを実装してもよく、それ故に、スケジューリングノードは、当該スケジューリングノードを実装するデータ構造のデータエレメントに最大データレートを格納することによって最大データレートに関連付けられてもよい。
【００３８】
そのような実施形態において、スケジューリングエンジン２１２は、ルートスケジューリングノード３０１の子スケジューリングノードを、ルートスケジューリングノード３０１に関連付けられるスケジューリングアルゴリズム及び最大データレートを用いて選択する。例えば、（ａ）スケジューリングノード３０２に関連付けられる最大データレートは７Ｇｂｐｓであり、且つ（ｂ）ルートスケジューリングノード３０１に関連付けられるスケジューリングアルゴリズムはスケジューリングシステム２１２がアグリゲートスケジューリングノード３０２を選択すべきであることを示す、と仮定される場合、最後の瞬間（又は他の期間）において、スケジューリングシステム２１２がスケジューリングノード３０２に関連付けられるパケットキュー（即ち、パケットキューｑ１、ｑ２及びｑ３）から１０Ｇｂを超えるデータを既に選択している場合を除いて、スケジューリングシステム２１２は、アグリゲートスケジューリングノード３０２を選択するであろう。さもなければ、スケジューリングシステム２１２は、ルートスケジューリングノード３０１に直接接続されるその他のスケジューリングノード（即ち、この例において、スケジューリングノード３０３及び３０４）のうちの１つを選択するであろう。
【００３９】
選択される子スケジューリングノードがリーフスケジューリングノードである場合、スケジューリングシステム２１２は、選択されるリーフスケジューリングノードに関連付けられるパケットキューを選択し、及び選択されるパケットキューから送信キュー２１４へパケットを移動させる。選択される子スケジューリングノードがリーフスケジューリングノードではない（即ち、アグリゲートスケジューリングノードである）場合、スケジューリングシステム２１２は、選択されるアグリゲートスケジューリングノードの子スケジューリングノードを選択する。この処理は、スケジューリングシステム２１２がリーフスケジューリングノードを選択するまで繰り返される。このようにして、スケジューリングシステム２１２は、最大レート又は他のスケジューリングルールを各レベル及び当該ツリーのノードにおいて考慮し及び実施しつつ、スケジューリングツリー３００を走査する。
【００４０】
ルートスケジューリングノード３０１と同様に、選択されるアグリゲートスケジューリングノードは、スケジューリングアルゴリズムに関連付けられ、当該選択されるアグリゲートスケジューリングノードの各子スケジューリングノードは、最大データレート（及び／又は他のパラメータ）に関連付けられ得る。従って、スケジューリングシステム２１２は、スケジューリングアルゴリズム及び最大データレートを用いて、いずれの子スケジューリングノードが選択されることとなるかを判定する。上記で議論したように、この処理は、スケジューリングシステム２１２がリーフスケジューリングノードであるスケジューリングノード（即ち、如何なる子スケジューリングノードも有しないスケジューリングノード）を選択するまで繰り返される。リーフスケジューリングノードを選択し、及び選択されるリーフスケジューリングノードに関連付けられるパケットキューから送信キュー２１４へパケットを移動させた後、スケジューリングシステム２１２は、ルートスケジューリングノード３００から開始して再度スケジューリングツリー３００を走査するであろう。従って、スケジューリングシステム２１２は、スケジューリングツリー３００を走査し続け、それによって、パケットを送信キュー２１４へ移動させるパケットキューを選択し続ける。このようにして、パケットは、物理通信リンク１２３上での送信のためにキューイングされる。
【００４１】
上記の説明から明らかなように、スケジューリングシステム２１２は、スケジューリングノードのうちの少なくとも幾つかについて状態情報を維持する。例えば、スケジューリングノードが当該スケジューリングノードに関連付けられる最大データレートを有する場合、スケジューリングシステム２１２は、当該スケジューリングノードに（直接的に又は間接的に）関連付けられるパケットキューから送信のためにどのくらいのデータが選択されたかを追跡するであろう。別の例として、スケジューリングノードがスケジューリングアルゴリズムに関連付けられる場合、スケジューリングシステム２１２は、当該スケジューリングアルゴリズムを実装するために必要とされる状態情報を維持し得る（例えば、スケジューリングノードのスケジューリングアルゴリズムがラウンドロビンスケジューリングアルゴリズムである場合、スケジューリングシステム２１２は、スケジューリングノードのいずれの子が最後の「番（turn）」を有したかを追跡し得る）。幾つかの実施形態において、スケジューリングシステム２１２は、スケジューリングノードについての状態情報を、当該スケジューリングノードを実装するデータ構造の１つ以上のデータエレメントに格納し得る。
【００４２】
物理通信リンク１２３の伝送容量が大きい（例えば、１００Ｇｂｐｓ）状況において、スケジューリングシステム２１２によって用いられるスケジューリングツリーがあまりに多くのデシジョンポイントを有することに起因して、スケジューリングシステム２１２が１００Ｇｂｐｓの容量の全てが利用されるほど迅速にパケットを送信キュー２１４へ移動させることが可能ではない状況があり得る。そのような状況において、複数の新たなスケジューリングツリーが、既存のスケジューリングツリーから形成されることができる。例えば、図４は、どのようにスケジューリングツリー３００が３つのスケジューリングツリー（即ち、ツリー４０１、４０２及び４０３）に分割されることができるかを例示する。示される実施形態において、ツリー４０１〜４０３の各々は、スケジューリングツリー３００のサブツリーである。さらに示されるように、ツリー４０１のルートスケジューリングノードは、ツリー３００のルートスケジューリングノードと同じである一方で、スケジューリングノード３０２は、ツリー４０２のルートスケジューリングノードであり、スケジューリングノード３０４は、ツリー４０３のルートスケジューリングノードである。
【００４３】
図５は、図４に示されるスケジューリングツリー４０１〜４０３と共に用いられることができるスケジューリングシステム２１２の一実施形態の機能図を例示する。示される実施形態において、スケジューリングシステム２１２は、３つのスケジューリングエンジン５２１〜５２３、即ち、各スケジューリングツリー４０１〜４０３について１つのスケジューリングエンジンンを含む。スケジューリングエンジン５２１は、パケットを送信キュー２１４へ移動させるように機能するため、最上位のスケジューリングエンジンとして分類され得る。スケジューリングエンジン５２２及び５２３は、これらのスケジューリングエンジンの各々がパケットを送信キュー２１４ではなく中間パケットキュー（例えば、ｉｑ１、又はｉｑ２）へ移動させるため、バーチャルポートスケジューリングエンジンとして分類され得る。
【００４４】
示される例において、ツリー４０１は、ｉｑ１、ｉｑ２及びｑ８から成るパケットキューのセットからパケットキューを選択するためにスケジューリングエンジン５２１によって用いられる；ツリー４０２は、ｑ１〜ｑ３から成るパケットキューのセットからパケットキューを選択するためにバーチャルポートスケジューリングエンジン５２２によって用いられる；ツリー４０３は、ｑ４〜ｑ７から成るパケットキューのセットからパケットキューを選択するためにバーチャルポートスケジューリングエンジン５２３によって用いられる。各スケジューリングエンジン５２１〜５２３は、ツリー３００に関連して上述されたスケジューリングシステム２１２と同じように動作する。つまり、各スケジューリングエンジン５２１〜５２３は、その対応するスケジューリングツリーを絶えず走査する；従って、各スケジューリングエンジン５２１〜５２３は、対応するツリーに基づいて選択されるパケットキューから送信キュー２１４へ又は中間パケットキューへパケットを絶えず移動させる。
【００４５】
より具体的には、スケジューリングエンジン５２１は、選択されるパケットキューから送信キュー２１４へパケットを移動させるように構成される一方で、スケジューリングエンジン５２２及び５２３は、選択されるパケットキューから中間パケットキュー（例えば、それぞれｉｑ１及びｉｑ２）へパケットを移動させるように各々構成される。スケジューリングエンジン５２１、５２２及び５２３は、並行して動作するように構成されてもよい。つまり、スケジューリングエンジン５２２及び５２３が中間パケットキュー（ｉｑ１及びｉｑ２）へパケットを移動させている間、スケジューリングエンジン５２１は、これらのパケットキューから送信キュー２１４へパケットを移動させていてもよい。また、スケジューリングエンジン５２１、５２２、及び５２３は、スケジューリングエンジンのうちのいずれも別のスケジューリングエンジンによって維持される如何なる状態情報も必要としないように、互いに独立して動作するように構成されてもよい。このようにして、パケットが送信キュー２１４へ移動されるレートは、大きく増加されることができる。例えば、中間パケットキューのうちの少なくとも１つが常に少なくとも１つのパケットを含むと仮定すると、パケットが送信キュー２１４へ移動されるレートは、スケジューリングエンジン５２１の「帯域幅（bandwidth）」（即ち、スケジューリングエンジンがパケットを送信キュー２１４へ伝送することができるレート）のみに依存する。さらに、幾つかの実施形態において、スケジューリングエンジン５２１は、そのスケジューリングツリー（例えば、ツリー４０１）が単一のレベルの走査のみを必要とし得る（例えば、ルートスケジューリングノード３０１に接続される全てのスケジューリングノードがリーフスケジューリングノードである）ため、非常に単純なエンジンとすることができる。従って、幾つかの実施形態において、スケジューリングエンジン５２１は、高い帯域幅を有するように実質的に純粋にハードウェアのみにおいて実装される。例えば、幾つかの実施形態において、スケジューリングエンジン５２１は、特定用途向け集積回路（ＡＳＩＣ）から成る（又は実質的に成る）一方で、スケジューリングエンジン５２２及び５２３は、ソフトウェアベースである（例えば、コンピュータプログラムが格納されたコンピュータ読取可能な媒体が関連付けられた汎用プロセッサを用いて実装される）。
【００４６】
図６は、概念的なスケジューリングツリーであり得るスケジューリングツリー３００を構成するスケジューリングノードから、異なるセットの動作スケジューリングツリー６０１〜６０３がどのように形成されることができるかを例示する。ツリー３００などの以前から存在するスケジューリングツリーから複数のスケジューリングツリーが形成され、当該以前から存在するスケジューリングツリーのルートスケジューリングノードに直接接続されていた１つよりも多くのスケジューリングノードを新たなツリーのうちの１つが含む場合、新たなルートスケジューリングノードが当該ツリーについて生成される必要があるであろう。これは、図６に示される。図６に示されるように、バーチャルポートスケジューリングノード６１０が、ツリー６０２のルートスケジューリングノードとなるように生成されている。バーチャルポートスケジューリングノード６１０が必要とされるのは、ツリー６０２が、ルートスケジューリングノード３０１に以前は直接接続されていた１つよりも多くのスケジューリングノード（例えば、スケジューリングノード３０２及び３０４）を含むためである。ルートスケジューリングノードは、ツリー６０３について生成される必要はない。このツリーは、ルートスケジューリングノード３０１に過去に直接接続されていた単一のスケジューリングノードのみを含むためである。また、図６に示される実施形態において、スケジューリングツリー６０２及び６０３の双方は、スケジューリングノード６２１〜６２３を含み、それによって、以下に議論されるようにロードバランシングの機会を提供する。スケジューリングノード６２１は、ネットワーク１１２を宛先とするトラフィックを表し、スケジューリングノード６２２は、ネットワーク１１２を宛先とする音声トラフィックを表し、スケジューリングノード６２３は、ネットワーク１１２を宛先とする非音声（即ち、「データ」）トラフィックを表す。
【００４７】
図７は、図６に示されるスケジューリングツリー６０１〜６０３と共に用いられることができるスケジューリングシステム２１２の一実施形態の機能図を例示する。図７に示される実施形態において、スケジューリングシステム２１２は、３つのスケジューリングエンジン７２１〜７２３、即ち、各スケジューリングツリー６０１〜６０３について１つのスケジューリングエンジンを含む。ツリー６０１は、ｉｑ１及びｉｑ２から成るパケットキューのセットからパケットキューを選択するために最上位のスケジューリングエンジン７２１によって用いられる；ツリー６０２は、ｑ１〜ｑ７、ｑ８ａ及びｑ９ａから成るパケットキューのセットからパケットキューを選択するためにバーチャルポートスケジューリングエンジン７２２によって用いられる；ツリー４０３は、ｑ８ｂ及びｑ９ｂから成るパケットキューのセットからパケットキューを選択するためにバーチャルポートスケジューリングエンジン７２３によって用いられる。各スケジューリングエンジン７２１〜７２３は、対応するツリーに基づいて選択されるパケットキューから送信キュー２１４へ又は中間パケットキュー（例えば、ｉｑ１、又はｉｑ２）へパケットを絶えず移動させる。より具体的には、最上位のスケジューリングエンジン７２１は、選択されるパケットキューから送信キュー２１４へパケットを移動させるように構成される一方で、バーチャルポートスケジューリングエンジン７２２及び７２３は、選択されるパケットキューから中間パケットキュー（例えば、それぞれｉｑ１及びｉｑ２）へパケットを移動させるようにそれぞれ構成される。スケジューリングエンジン５２１〜５２３と同様に、スケジューリングエンジン７２１〜７２３は、並行して且つ互いに独立して動作するように構成され得る。
【００４８】
図７にさらに示されるように、インタフェース１９１は、ロードバランサ７０２を含み得る。図６及び図７の実施形態において、ＰＲＰＵ２０２がネットワーク１１２を宛先とするパケットを受信すると、ＰＲＰＵ２０２は、当該パケットをパケットキューに即座に格納する代わりに、当該パケットをロードバランサ７０２に渡す。当該ロードバランサ７０２は、トラフィックをパケットキューｑ８ａ、ｑ９ａ、及びパケットキューｑ８ｂ、ｑ９ｂの間で均等に配信し得る。より具体的には、図６に示されるように、ネットワーク１１２を宛先とする音声トラフィックは、パケットキューｑ８ａ及びｑ８ｂ間で均等に配信され、ネットワーク１１２を宛先とする非音声トラフィックは、パケットキューｑ９ａ及びｑ９ｂ間で均等に配信される。
【００４９】
図８は、一実施形態に係る処理８００を例示するフローチャートである。処理８００は、ステップ８０２において開始され得る。当該ステップ８０２において、パケットキューの第１のセット（例えば、パケットキューｑ１〜ｑ３）は、第１のスケジューリングエンジン（例えば、スケジューリングエンジン５２２）に割り当てられる。ステップ８０２は、スケジューリングツリー（例えば、スケジューリングツリー４０２）を第１のスケジューリングエンジンに割り当てることによって達成され得る。ここで、スケジューリングツリーは、パケットキューのセット（図４参照）に関連付けられる。ステップ８０４において、パケットキューの第２のセット（例えば、パケットキューｑ４〜ｑ７）は、第２のスケジューリングエンジン（例えば、スケジューリングエンジン５２３）に割り当てられる。ステップ８０４は、異なるスケジューリングツリー（例えば、スケジューリングツリー４０３）を第２のスケジューリングエンジンに割り当てることによって達成され得る。ステップ８０６において、パケットキューの第３のセット（例えば、パケットキューｑ８）は、第３のスケジューリングエンジン（例えば、スケジューリングエンジン５２１）に割り当てられる。ステップ８０８において、第１のパケットフローは、パケットキューの第１のセットに含まれるパケットキューに割り当てられる。例えば、ステップ８０８において、ネットワークインタフェース１９１は、ＰＲＰＵ２０２によって受信される、ネットワーク１１２を宛先とする全てのパケットが例えばｑ８に格納されるように構成される。ステップ８１０において、第２のパケットフローは、パケットキューの第２のセットに含まれるパケットキューに割り当てられる。ステップ８１２において、第３のパケットフローは、パケットキューの第３のセットに含まれるパケットキューに割り当てられる。幾つかの実施形態（例えば、図６を参照）において、ステップ８１２は実行されない。ステップ８１２の後、処理８００は、ステップ８１４、８２０、８２４及び８２８に並行して進み得る。
【００５０】
ステップ８１４において、ＰＲＰＵ２０２は、パケットを受信する。ステップ８１４において、ＰＲＰＵ２０２は、当該パケットに関連付けられるメタデータも受信し得る。ステップ８１６において、ＰＲＰＵ２０２は、当該パケットが属するパケットフローを判定する。上記で議論されたように、ＰＲＰＵ２０２は、パケットに含まれるデータ（例えば、宛先アドレス）及び／又はメタデータを用いてパケットフローを判定し得る。当該メタデータは、パケットが宛先とする１つ以上のＶＬＡＮを識別し得る。ステップ８１８において、ＰＲＰＵ２０２は、判定されたパケットフローに関連付けられるパケットキューに受信パケットを格納する。例えば、ステップ８１８において、ＰＲＰＵは、判定されたパケットフロー（例えば、判定されたＶＬＡＮ識別子）を用いて、当該判定されたパケットフローに割り当てられる当該パケットキューをデータベース２０４においてルックアップし得る。ＰＲＰＵ２０２は、ステップ８１４〜８１８を実行し続け得る。
【００５１】
ステップ８２０において、第１のスケジューリングエンジンは、パケットキューの第１のセットからパケットキューを選択する。例えば、ステップ８２０において、第１のスケジューリングエンジンは、スケジューリングツリーを走査して、当該ツリーのリーフスケジューリングノードに到達し、それによって、当該リーフスケジューリングノードに関連付けられるパケットキューを選択し得る。ステップ８２２において、第１のスケジューリングエンジンは、選択されたパケットキューから第１の中間パケットキュー（例えば、ｉｑ１）へパケットを移動させる。第１のスケジューリングエンジンは、ステップ８２０〜８２２を実行し続け得る。
【００５２】
幾つかの実施形態において、第１のスケジューリングエンジンは、第１の中間パケットキューの状態を周期的にモニタリングし（例えば、パケットキューの長さを周期的に判定し）、及び当該パケットキューの状態に依存して、ステップ８０２から８２２を実行することを短期間中止し得る（即ち、第１のスケジューリングエンジンは休止し得る）。例えば、第１の中間パケットキューの長さは所定の閾値よりも大きいと第１のスケジューリングエンジンが判定する場合、第１のスケジューリングエンジンは、当該判定に応じて、幾らかの時間休止し、又はいっぱいではない他の中間キューへ向けられるパケットのみを一時的に選択的にスケジューリングし、それによって、第１の中間パケットキューが大きくなることを回避し得る。この特徴は、以下の利点を提供する：（ｉ）中間キューによって消費されるシステムリソース（例えば、パケットバッファ）の量を抑制すること、（ｉｉ）パケットが中間キューにおいて待機している間に被り得る付加的な転送レイテンシを抑制すること、及び（ｉｉｉ）最終的にスケジューリングの振る舞いを判定するバーチャルポートスケジューリングエンジンに関連付けられる規則を確実にすること。
【００５３】
ステップ８２４において、第２のスケジューリングエンジンは、パケットキューの第２のセットからパケットキューを選択する。例えば、ステップ８２４において、第２のスケジューリングエンジンは、スケジューリングツリーを走査して、当該ツリーのリーフスケジューリングノードに到達し、それによって、当該リーフスケジューリングノードに関連付けられるパケットキューを選択し得る。ステップ８２６において、第２のスケジューリングエンジンは、選択されたパケットキューから第２の中間パケットキュー（例えば、ｉｑ２）へパケットを移動させる。第２のスケジューリングエンジンは、第１のスケジューリングエンジンとは独立にステップ８２４〜８２６を実行し続け得る。第１のスケジューリングエンジンと同様、第２のスケジューリングエンジンは、第２の中間パケットキューの状態を周期的にモニタリングし、及び当該パケットキューの状態に依存して休止するように構成され得る。
【００５４】
ステップ８２８において、第３のスケジューリングエンジンは、第１及び第２の中間パケットキュー並びにパケットキューの第３のセットを含むパケットキューのセットからパケットキューを選択する。ステップ８３０において、第２のスケジューリングエンジンは、選択されたパケットキューから送信キュー２１４へパケットを移動させる。第３のスケジューリングエンジンは、第１のスケジューリングエンジン及び第２のスケジューリングエンジンとは独立にステップ８２８〜８３０を実行し続け得る。第１及び第２のスケジューリングエンジンと同様、第３のスケジューリングエンジンは、送信キュー２１４の状態を周期的にモニタリングし、及び当該パケットキューの状態に依存して休止するように構成され得る。
【００５５】
上記の手法で、複数の独立したスケジューリングエンジンが採用されて、パケットが送信キューに移動され、それによって、ネットワークインタフェース１９１のスループットが増加される。
【００５６】
図２に戻ると、図２に示すように、ネットワークエレメント１０８は、構成モジュール２０８を含み得る。構成モジュール２０８は、ユーザ（例えば、ネットワーク管理者）がスケジューリングノードを定義し、スケジューリングツリーを生成し、及びスケジューリングノード及び／又はスケジューリングツリーをスケジューリングエンジンに割り当てることを可能にするように構成され得る。例えば、構成モジュールは、ネットワーク管理者がネットワークインタフェース１９１を構成することを可能にするグラフィカルユーザインタフェース（ＧＵＩ）又はコマンドラインインタフェース（ＣＬＩ）を提供し得る。また、構成モジュール２０８は、ネットワークインタフェース１９１を自動的に構成する（例えば、予め定義されるスケジューリングツリー（例えば、ツリー３００）からスケジューリングツリーのセット（例えば、ツリー４０１〜４０３）を生成する）ように構成され得る。幾つかの実施形態において、構成モジュール２０８は、スケジューリングツリー（例えば、ツリー３００）を定義する情報を検査し、第１のスケジューリングエンジンにスケジューリングツリー３００の第１のサブツリー（例えば、ツリー４０１）を割り当て、及び第２のスケジューリングエンジンにスケジューリングツリー３００の第２の異なるサブツリー（例えば、ツリー４０２）を割り当てるように構成される。
【００５７】
具体的な例として、新たなＤＳＬＡＭ９０１（図９を参照）が通信システム１００に追加されたと仮定する。この新たなＤＳＬＡＭ９０１が追加される場合、ネットワーク管理者は、構成モジュール２０８を用いて、ＤＳＬＡＭ９０１へのパケットのフロー（例えば、ＶＬＡＮ３を宛先とする全てのパケット）を表すための新たなスケジューリングノードを定義し得る。例えば、図１０に示すように、ネットワーク管理者は、３つの新たなスケジューリングノードを定義し得る：（１）ＶＬＡＮ３を宛先とする全てのパケットのフローを表すアグリゲートスケジューリングノード１００１、（２）ＶＬＡＮ３への全ての高優先度のパケット（例えば、音声パケット）を表すリーフスケジューリングノード１００２、及び（３）ＶＬＡＮ３への全ての低優先度のパケットのフローを表すリーフスケジューリングノード１００３。アグリゲートスケジューリングノード１００１は１つよりも多い子スケジューリングノードを有するため、スケジューリングノード１００１を定義する処理は、スケジューリングエンジンがスケジューリングノード１００１に到達し及びどの子スケジューリングノードを選択すべきかを選択しなければならない場合に当該スケジューリングエンジンが用いるであろうスケジューリングアルゴリズム（例えば、ラウンドロビン）にスケジューリングノード１００１を関連付けることを含み得る。また、ＤＳＬＡＭ９０１が８Ｇｂｐｓの最大パケット転送容量を有する場合、ネットワーク管理者は、構成モジュールをさらに用いて、スケジューリングノード１００１が８Ｇｂｐｓの最大帯域幅に関連付けられるように当該スケジューリングノード１００１を構成し得る。
【００５８】
スケジューリングノードが定義された後、リーフスケジューリングノードによって表されるパケットフローは、一意のパケットキューに関連付けられる必要がある。構成モジュール２０８は、リーフスケジューリングノードごとに、当該リーフスケジューリングノードによって定義されるパケットフローをパケットキューにマッピングする情報をパケットフロー対パケットキューデータベース２０４に追加することによってデータベース２０４を更新することによって、この機能を実行し得る。
【００５９】
また、スケジューリングノードが定義された後、スケジューリングシステム２１２によって現在用いられているスケジューリングツリーのうちの１つ以上はリーフスケジューリングノード１００２及び１００３に適応するように変更される必要があり、並びに／又は、新たなスケジューリングツリーが生成される必要がある。これは、ネットワーク管理者によって手動で、又は構成モジュール２０８によって自動的に為されることができる。
【００６０】
一例として、図１１は、図示のようにパケットキューｑ９及びｑ１０にそれぞれ関連付けられているリーフスケジューリングノード１００２及び１００３に適応するように、ツリー４０２がどのように変更され得るかを示す。図１１に示すように、バーチャルポートスケジューリングノード１１０１は、ツリー４０２の新たなルートスケジューリングノードとなるように生成されている。ツリー４０２のルートスケジューリングノードであったスケジューリングノード３０２及びスケジューリングノード１００１は別個のパケットフローを表し、それ故に、スケジューリングノード１００１はスケジューリングノード３０２の子とはなり得ず、その逆もまた同様であるため、バーチャルポートスケジューリングノード１１０１を生成し、当該ノードをツリー４０２のルートスケジューリングノードとすることが必要とされた。図示のように、スケジューリングノード３０２は、ここではスケジューリングノード１１０１に直接接続され、リーフスケジューリングノード１００２及び１００３は、ルートスケジューリングノード１１０１に直接接続されるアグリゲートスケジューリングノード１００１を介してルートスケジューリングノード１１０１に間接的に接続される。図１２は、リーフスケジューリングノード１００２及び１００３がスケジューリングツリーに追加されることができる別の手法を示す。図１２に示すように、ツリー４０１及び４０２は、それぞれリーフスケジューリングノード１００２及び１００３に適応するように変更されている。
【００６１】
構成モジュール２０８がスケジューリングツリーを自動的に再構成する実施形態において、構成モジュール２０８は、スケジューリングエンジンの帯域幅とスケジューリングノードに関連付けられる最大帯域幅とを考慮するようにプログラミングされ得る。例えば、（ａ）スケジューリングエンジン５２２の最大帯域幅は１５Ｇｂｐｓであり、（ｂ）スケジューリングノード３０２に関連付けられる最大帯域幅は１０Ｇｐｂであり、且つ（ｃ）スケジューリングノード１００１に関連付けられる最大帯域幅も１０Ｇｂｐｓであると仮定すると、構成モジュール２０８は、図１１に示すようにツリー４０２にリーフスケジューリングノード１００２及び１００３を追加しないであろう。（ｉ）スケジューリングノード３０２に関連付けられる最大帯域幅と（ｉｉ）スケジューリングノード１００１に関連付けられる最大帯域幅との合計がスケジューリングエンジン５２２の最大帯域幅よりも大きいためである。また、スケジューリングツリーの既存のセットに新たなスケジューリングツリーが追加され得る実施形態において、構成モジュール２０８は、新たなバーチャルポートスケジューリングエンジンのインスタンスを自動的に生成して、当該新たなスケジューリングツリーに関連付けられるパケットフローをスケジューリングし得る。
【００６２】
ここで図１３を参照すると、図１３は、本発明の幾つかの実施形態に係るスケジューリングエンジン５２２のブロック図を例示する。図１３に示すように、スケジューリングエンジン５２２は、以下を備え得る：特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）等といった１つ以上のマイクロプロセッサ及び／又は１つ以上の回路を含み得るデータ処理システム１３０２；ネットワークインタフェース１３０４；及び１つ以上の不揮発性ストレージデバイス及び／又は１つ以上の揮発性ストレージデバイス（例えば、ランダムアクセスメモリ（ＲＡＭ））を含み得るデータストレージシステム１３０６。図示のように、データストレージシステム１３０６は、スケジューリングツリーの状態情報を記憶するために用いられ得る。データ処理システム１３０２がマイクロプロセッサを含む実施形態において、コンピュータ読取可能なコード１３４３は、磁気媒体（例えば、ハードディスク）、光媒体（例えば、ＤＶＤ）、メモリデバイス（例えば、ランダムアクセスメモリ）等といった、但しこれらに限定されないコンピュータ読取可能な媒体１３４２に記憶され得る。幾つかの実施形態において、コンピュータ読取可能なコード１３４３は、プロセッサによって実行される場合、当該コード１３４３がスケジューリングエンジン５２２に上述されたステップ（例えば、図８に示されるフローチャートを参照しつつ上述されたステップ）を実行させるように構成される。他の実施形態において、スケジューリングエンジン５２２は、コード１３４３の必要無しに、上述されたステップを実行するように構成される。つまり、例えばデータ処理システム１３０２は１つ以上のＡＳＩＣのみから成ってもよい。それ故に、上述された本発明の特徴は、ハードウェア及び／又はソフトウェアにおいて実装され得る。例えば、特定の実施形態において、上述されたスケジューリングエンジン５２２の機能的なコンポーネントは、コンピュータ命令１３４３を実行するデータ処理システム１３０２によって、任意のコンピュータ命令１３４３とは独立に動作するデータ処理システム１３０２によって、又はハードウェア及び／若しくはソフトウェアの任意の適切な組み合わせによって実装され得る。
【００６３】
ここで図１４を参照すると、図１４は、コンピュータ読取可能なプログラムコード（ＣＲＰＣ：computer  readable  program  code）１３４３の一実施形態を例示する。図示される実施形態において、ＣＲＰＣ１３４３は、以下を含む：（１）スケジューリングツリーを定義する情報をスケジューリングツリーデータベース２１０から取得するための命令のセット１４０２、（２）スケジューリングツリーを走査することによってパケットキューのセットからパケットキューを周期的に選択するための命令のセット１４０４、及び（３）選択されるパケットキューから中間パケットキューへパケットを移動させるための命令のセット１４０６。
【００６４】
本発明の種々の実施形態が上述されたが、それらはほんの一例として提示され、限定ではないことが理解されるべきである。従って、本発明の広さ及び範囲は、上述された例示的な実施形態のうちのいずれによっても限定されるべきではない。さらに、そのあらゆる取り得る変形例における上述された要素の如何なる組み合わせも、本明細書において別段の記載がない限り又はコンテキストによって明らかに矛盾しない限り、本発明によって包含される。
【００６５】
また、上述され及び図面において例示される処理は一連のステップとして示されているが、これは例示のために為されたにすぎない。従って、幾つかのステップが追加され、幾つかのステップは省略され、ステップの順序が並べ替えられ、及び幾つかのステップが並行して実行され得ることが予期される。
【図１】
0005932020.tif 000002
【図２】
0005932020.tif 000003
【図３】
0005932020.tif 000004
【図４】
0005932020.tif 000005
【図５】
0005932020.tif 000006
【図６】
0005932020.tif 000007
【図７】
0005932020.tif 000008
【図８】
0005932020.tif 000009
【図９】
0005932020.tif 000010
【図１０】
0005932020.tif 000011
【図１１】
0005932020.tif 000012
【図１２】
0005932020.tif 000013
【図１３】
0005932020.tif 000014
【図１４】
0005932020.tif 000015