(57)【特許請求の範囲】
【請求項１】
パケットルータ内のキューを選択するための方法であって：
データパケットを入力インターフェースから受信するステップと、
前記データパケットに関連する前記入力インターフェースに関する識別子をフロー内に記憶するステップと、
前記データパケットの宛先アドレスに従って、前記データパケットを前記フローに導くステップと、
記憶された識別子に従って、前記データパケットを前記フローから前記入力インターフェースに関連するキューのセットに転送するステップとを含む、方法。
【請求項２】
前記データパケットの優先順位に従って、前記データパケットを前記キューのセット内のキューに割り当てるステップであって、前記キューが前記優先順位に対応する、割り当てるステップをさらに含む、請求項１に記載の方法。
【請求項３】
前記識別子を記憶する前記ステップが、前記識別子を前記フロー内の前記データパケットに割り振られた内部レジスタ内に記憶するステップを含む、請求項１に記載の方法。
【請求項４】
前記識別子を記憶する前記ステップが、前記識別子をカプセル化ヘッダ内で前記データパケットにプリペンドするステップを含む、請求項１に記載の方法。
【請求項５】
前記優先順位が、前記データパケット内のサービス品質（ＱｏＳ）パラメータによって定義される、請求項１に記載の方法。
【請求項６】
前記内部レジスタが、前記データパケットが前記フロー内に存在する間に前記フローに割り振られる、請求項２に記載の方法。
【請求項７】
前記宛先アドレスがある範囲の宛先アドレスを含む、請求項１に記載の方法。
【請求項８】
前記パケットルータがＩＰルータを含み、前記データパケットがインターネットプロトコル（ＩＰ）パケットを含む、請求項１に記載の方法。
【請求項９】
前記パケットルータがイーサネットルータを含み、前記データパケットがイーサネットパケットを含み、前記宛先アドレスが宛先ＭＡＣアドレスを含む、請求項１に記載の方法。
【請求項１０】
前記パケットルータがラベルスイッチルータ（ＬＳＲ）を含み、前記データパケットがマルチプロトコルラベルスイッチング（ＭＰＬＳ）パケットを含み、前記宛先アドレスがＭＰＬＳラベルを含む、請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケット交換通信ネットワークに関し、より詳細には、アクセスルータ内のキューイング技術に関する。
【背景技術】
【０００２】
ネットワークプロセッサベースのインターネットプロトコル（ＩＰ）ルータ内で、トラフィック管理のキューイング機能性は、通常、宛先インターフェースごとに実行される。ルータが顧客エッジで使用され、ポートがアクセス側に接続されるときなど、ルータ内でソースベースのキューイングが必要とされるとき、知られている解決策は、それらのキューをソースインターフェースと関連付けるために、ソースインターフェースごと、かつ宛先ルートごとにフローを定義する。フローは、宛先ＩＰルート（例えば：共通して初めの２４ビットを有するＩＰアドレスのグループを表す２．２．２．２／２４）、あるいは特定の宛先ＩＰアドレス（例えば：１．１．１．１）もしくはＶＰＬＳ（バーチャルプライベートＬＡＮサービス、ＲＦＣ２５４７）における宛先ＭＡＣアドレスまたはＬＳＲ（ラベルスイッチルータ、ＲＦＣ３０３２）におけるＭＰＬＳラベルなど、同じトラフィック管理特性を有するデータのストリームである。
【０００３】
別の知られている代替案は、ソースベースのキューイングの後に、ルーティングデータ経路ルックアップを実行させることである。これらの手法は両方とも、ソースごと、かつ宛先ごとにフローを必要とする。それぞれの宛先に関して、ソースごとにフローが作成される必要があり、結果として、メモリ内のコンテキストテーブルが大きくなり、したがって、大量のメモリを消費し、これは、メモリのコスト、またはメモリリソースが使用中に使い果たされることによるパフォーマンス低下のいずれかの点でコストがかかる可能性があるため、ソースごとにキューイング機能性を実行することは、一般に、かなりのリソースを必要とする。
【０００４】
図１は、任意の先行技術のソースベースキューイング実装形態を例示する。図１を参照すると、ポート１０１、１０３は、１つまたは複数の入力インターフェース（ｉｎｇｒｅｓｓ  ｉｎｔｅｒｆａｃｅｓ）１０５、１０７、１０９を用いて構成可能である。それぞれの入力インターフェースからのＩＰパケットは別個のフローに導かれる。例えば、それぞれ入力インターフェース１０５、１０７、１０９からのＩＰパケット１１１、１１３、１１５は、フロー１１７、１１９、１２１に導かれる。ソースベースのキューイングの場合、入力インターフェース１０５から発生するＩＰパケット１２３、１２５、１２７，１２９は、キューセット１３１に転送される。キューセット１３１内のキュー１３３、１３５、１３７は、それぞれ、異なる優先順位でトラフィックを処理するように構成される。これらのキューは、スイッチングファブリック１３９を介してダウンストリーム帯域幅に従って処理される。
【０００５】
したがって、ルーティングおよびキューイングパフォーマンスを維持すると同時に、メモリ使用を最小化する手段が非常に望ましい。
【発明の概要】
【課題を解決するための手段】
【０００６】
一実施形態では、本発明は、パケットルータ内のキューを選択するための方法を提供する。この方法は：データパケットを入力インターフェースから受信するステップと、前記データパケットに関連する前記入力インターフェースに関する識別子を前記フロー内に記憶するステップと、前記データパケットの宛先アドレスに従って、前記データパケットをフローに導くステップと、記憶された識別子に従って、前記データパケットを前記フローから前記入力インターフェースに関連するキューのセットに転送するステップとを含む。
【０００７】
他の実施形態は、前記データパケットの優先順位に従って、前記データパケットを前記キューのセット内のキューに割り当てるステップであって、前記キューが前記優先順位に対応する、割り当てるステップをさらに含む。
【０００８】
他の実施形態では、前記識別子を記憶するステップは、前記識別子を前記フロー内の前記データパケットに割り振られた内部レジスタ内に記憶するステップを含む。
【０００９】
他の実施形態では、前記識別子を記憶するステップは、前記識別子を前記フロー内の前記データパケットに割り振られた外部メモリ内に記憶するステップを含む。
【００１０】
他の実施形態では、前記識別子を記憶するステップは、前記識別子をカプセル化ヘッダ内で前記データパケットにプリペンドする（ｐｒｅ−ｐｅｎｄｉｎｇ）ステップを含む。
【００１１】
他の実施形態では、優先順位は、前記データパケット内のサービス品質（ＱｏＳ）パラメータによって定義される。
【００１２】
他の実施形態では、優先順位は、前記データパケット内の転送クラスパラメータによって定義される。
【００１３】
他の実施形態では、内部レジスタは、前記データパケットが前記フロー内に存在する間に前記フローに割り振られる。
【００１４】
他の実施形態では、宛先アドレスは様々な宛先アドレスを含む。
【００１５】
他の実施形態では、パケットルータはＩＰルータを含み、前記データパケットはインターネットプロトコル（ＩＰ）パケットを含む。
【００１６】
他の実施形態では、パケットルータはイーサネット（登録商標）ルータを含み、前記データパケットはイーサネットパケットを含み、前記宛先アドレスは宛先ＭＡＣアドレスを含む。
【００１７】
他の実施形態では、パケットルータはラベルスイッチルータ（ＬＳＲ）を含み、前記データパケットはマルチプロトコルラベルスイッチング（ＭＰＬＳ）パケットを含み、前記宛先アドレスはＭＰＬＳラベルを含む。
【００１８】
本発明の実施形態の別の態様は、パケットルータ内で着信パケットを処理するためのシステムを提供する。このシステムは：入力インターフェース識別子を有する、データパケットを受信するための入力インターフェースと、前記データパケットに関連する前記入力インターフェース識別子を前記フロー内に記憶するための記憶手段と、前記データパケットの宛先アドレスに関連する、前記データパケットを前記インターフェースから受け入れるためのフローと、記憶された識別子に従って、前記データパケットを前記フローから前記入力インターフェースに関連するキューのセットに転送するための転送手段とを備える。
【００１９】
いくつかの実施形態では、転送手段は、前記データパケットの優先順位に従って、前記データパケットを前記キューのセット内のキューに割り当てるように構成され、前記キューは前記優先順位に対応する。
【００２０】
いくつかの実施形態では、記憶手段は、前記フロー内で前記データパケットに割り振られた内部レジスタを備える。
【００２１】
いくつかの実施形態では、記憶手段は、前記フロー内で前記データパケットに割り振られた外部メモリを備える。
【００２２】
いくつかの実施形態では、記憶手段は、前記データパケットにプリペンドされたカプセル化ヘッダを備える。
【００２３】
いくつかの実施形態では、システムはネットワークプロセッサを備える。
【００２４】
いくつかの実施形態では、システムはフィールドプログラマブルゲートアレイを備える。
【００２５】
いくつかの実施形態では、システムは特定用途向け集積回路を備える。
【００２６】
いくつかの実施形態では、パケットルータはＩＰルータを含み、前記データパケットはインターネットプロトコル（ＩＰ）パケットを含む。
【００２７】
いくつかの実施形態では、パケットルータはイーサネットルータを含み、前記データパケットはイーサネットパケットを含み、前記宛先アドレスは宛先ＭＡＣアドレスを含む。
【００２８】
いくつかの実施形態では、パケットルータはラベルスイッチルータ（ＬＳＲ）を含み、前記データパケットはマルチプロトコルラベルスイッチング（ＭＰＬＳ）パケットを含み、前記宛先アドレスはＭＰＬＳラベルを含む。
【００２９】
本発明の実施形態のさらに別の態様は、上で説明された方法ステップを実行するために、機械によって実行可能な命令のプログラムを有形に具体化する、機械によって読み取り可能なプログラム記憶デバイスを提供する
本発明の実施形態による装置および／または方法のいくつかの実施形態が、次に、例としてだけ、添付の図面を参照して説明される。
【図面の簡単な説明】
【００３０】
【図１】ＩＰルータ内のソースベースのキューイングの先行技術の実装形態を示す線図である。
【図２】本発明のある実施形態による、ＩＰルータ内のソースベースのキューイングを示す線図である。
【図３】本発明の内部レジスタ実施形態の態様を示す図である。
【図４】本発明のパケットカプセル化実施形態を示す図である。
【図５】本発明の方法のある実施形態のステップを示す図である。
【発明を実施するための形態】
【００３１】
図面において、類似の特徴は類似の参照符号によって示される。
【００３２】
ネットワークプロセッサベースのサービスルータ内で、それぞれのローカルＩＰインターフェース（ＩＦ）は入力インターフェースカード上のポートにバインドされる。着信ＩＰパケットは、ＩＰ宛先アドレスに基づいて、ネットワークプロセッサフィルタを使用して解析／分類される。次いで、パケットは、ネットワークプロセッサ上でＩＰルーティング処理を受ける。
【００３３】
一実施形態は、ソースインターフェース情報をネットワークプロセッサによって処理されているデータパケットに関連する記憶レジスタ内に記憶するステップを含む。パケットが経路指定されているとき、そのパケットは、次いで、そのレジスタ内に記憶されたソースインターフェース情報によって識別されたインターフェースに関連するキューセットに送られる。この実施形態では、レジスタは、現在処理されているパケットとだけ関連付けられる。パケットが適切なインターフェースに関連するキューセットに到着したとき、そのパケットは、そのパケットの優先順位に関連する、キューセット内のキューに追加される。そのパケットの優先順位は、パケット内のサービス品質（ＱｏＳ）パラメータ、ＩＰパケットのＤＳＣＰに基づく転送クラス（ＦＣ）および入力ＩＰ  Ｉ／Ｆポリシー、または当業者によく知られている他の優先順位機構によって定義可能である。
【００３４】
図２を参照すると、入力インターフェース２０５、２０７、２０９からのＩＰパケットは、パケットがフローを通じて移動するときに、それぞれのＩＰパケットに関連する入力インターフェースに関する識別子を記憶することによって達成されるその発信入力インターフェースと関連付けられる。これは、パケットがルータを通じて移動するときのパケットを表す曲線矢印上の番号が付けられた円（１）、（２）、（３）によって概念的に例示される。番号が付けられた円（１）、（２）、（３）は、パケットがフロー２１１、２１３、２１５、２１７を通じて移動するときに、ＩＰパケットに関連する、記憶された入力インターフェース識別子を表す。それぞれのフローは、宛先ＩＰアドレスに関連するＩＰパケットのすべてを処理する。ＩＰパケットは、それぞれのＩＰパケットに関連する、記憶された入力インターフェース識別子を読み取ることによって、フロー２１１、２１３、２１５、２１７からキューセット２１９、２２１、２２３に転送される。キューセット２１９内のキュー２２５、２２７、２２９は、それぞれ、異なる優先順位を用いてトラフィックを処理するように構成される。これらのキューは、スイッチングファブリック２３１を介してダウンストリーム帯域幅に従って処理される。
【００３５】
図３は、入力インターフェース識別子がレジスタ３０１内に記憶される、本発明のある実施形態を例示する。ネットワークプロセッサ３０３は、それぞれ１つのフロー専用の複数のメモリブロック３０５、３０７、３０９を有し、それによって、複数のフローが同時に処理されることを可能にする。ＩＰパケットは、一度に１個のパケットがそれぞれのフローを介して処理される。レジスタ３０１、３１１、３１３はフロー３０５に割り当てられ、パケットがフロー内で処理されている時間の間、そのフローと関連付けられた状態に留まる。
【００３６】
別の実施形態では、それぞれのパケットに対応する入力インターフェース識別子は、外部メモリ内に記憶されて、そのパケットがそのフローによって処理されている存続時間にわたって明示的にそのパケットと関連付けられる。
【００３７】
図４は、ルーティング可能なＩＰパケットがスイッチングファブリックカプセル化ヘッダでプリペンドされる別の実施形態を例示する。このように、それぞれのＩＰパケット４０１は、その中にパケットに対応する入力インターフェース識別子が記憶されるカプセル化ヘッダ４０３でプリペンドされる。これは、入力インターフェース情報向けの携帯用記憶機構を提供する。追加の処理に関して、カプセル化ヘッダ内の内部フィールドマーキングを使用することが可能である。
【００３８】
図５は、ステップ５０１から始まる、本発明の方法のある実施形態のステップを例示する。ステップ５０３において、ＩＰルータのネットワークプロセッサは、ＩＰパケットを入力インターフェースから受信する。ステップ５０５において、ネットワークプロセッサは、パケットが受信されたインターフェースに関する入力インターフェース識別子を記憶する。プロセッサは、先に議論されたように、いくつかの異なる形で入力インターフェース識別子を記憶することができる。当業者によって十分理解されるであろう、それぞれのパケットに関する入力インターフェース識別子を記憶するための他の方法も企図される。ステップ５０７において、ＩＰパケットは、ＩＰパケットの宛先アドレスに対応するフローに導かれる。次いで、記憶された識別子は、記憶された識別子に従って、ＩＰパケットが入力インターフェースに関連するキューに転送されるステップ５０９に関して利用可能である。この時点で、識別子は必要でなくなる。識別子がカプセル化ヘッダ内に記憶されている事例では、ヘッダは、識別子を取り出した後で取り除かれる。
【００３９】
先の説明は、ＩＰルータを有し、ＩＰパケットを搬送する実施形態を議論している点に留意されたい。本発明の範囲内で企図される他の実施形態は、一般に、データパケットを搬送するパケットルータに適用され、宛先ＭＡＣアドレスを有するイーサネットパケットを搬送するイーサネットルータ、および宛先アドレスとして、ＭＰＬＳラベルを有するマルチプロトコルラベルスイッチング（ＭＰＬＳ）パケットを搬送するラベルスイッチルータ（ＬＳＲ）にも適用される。
【００４０】
それぞれの宛先ルートおよびそれぞれの入力インターフェースに別個のフローを必要とする、ソースベースのルーティングの先行技術の手法と対照的に、本発明の実施形態は、それぞれの宛先ルートに関して単一のフローを使用する。
【００４１】
本発明の重要性を例示するために、ソースベースのキューイングを必要とする１００（１００）個の入力インターフェースと、１０００（１０００）個の異なる宛先ルートまたは宛先アドレスとを有するＩＰルータを考慮する。入力インターフェースごと、かつ宛先ルートごとに１個のフローを有する先行技術の実装形態を使用すると、これは、１００，０００個の別個のフローを必要とすることになるが、本発明の実施形態は、１００個のフローだけを必要とすることになる。入力インターフェース識別子を記憶するために内部レジスタを使用するある実施形態では、フローごとに１個の内部レジスタも必要とすることになる。典型的なネットワークプロセッサ実装形態では、それぞれのフローには、通常、いくつかの未使用のレジスタが割り当てられ、任意の形で利用可能になる。
【００４２】
当業者は、様々な上述の方法のステップはプログラムされたコンピュータによって実行可能であることを容易に認識されよう。本明細書では、いくつかの実施形態は、機械読取り可読であるかまたはコンピュータ読取り可能であり、命令からなる機械実行可能プログラムまたはコンピュータ実行可能プログラムを符号化するプログラム記憶デバイス、例えば、デジタルデータ記憶媒体を網羅することも意図され、前記命令は、前記上述の方法のステップのうちのいくつかまたはすべてを実行する。プログラム記憶デバイスは、例えば、デジタルメモリ、磁気ディスクおよび磁気テープなど磁気記憶媒体、ハードドライブ、または光学的に読取り可能なデジタルデータ記憶媒体であってよい。これらの実施形態は、上述の方法の前記ステップを実行するようにプログラムされたコンピュータを網羅することも意図される。
【００４３】
この説明およびこれらの図面は、本発明の原理を単に例示する。したがって、当業者は、本明細書に明示的に説明または示されていないものの、本発明の原理を実施し、その趣旨内および範囲内に含まれる様々な構成を考案することができる点を理解されよう。さらに、本明細書に列挙されたすべての例は、読者が当技術分野を促進するために本発明の原理、および（１人または複数の）発明者によって寄与された概念を理解する際に支援するための教育目的でのみ表現されることが原則として意図され、そのような詳細に列挙された例および条件に対する限定なしに解釈されるべきである。さらに、本発明の原理、態様、および実施形態、ならびにそれらの特定の例を列挙する本明細書のすべての記述は、それらの均等物を包含することが意図される。
【００４４】
「プロセッサ」としてラベル付けされた任意の機能ブロックを含めて、図面に示される様々な要素の機能は、専用ハードウェア、ならびに適切なソフトウェアとの関連でソフトウェアを実行することが可能なハードウェアを使用することにより提供可能である。プロセッサによって提供されるとき、これらの機能は、単一の専用プロセッサによって、単一の共有プロセッサによって、またはそのうちのいくつかが共有され得る複数の個々のプロセッサによって提供可能である。さらに、用語「プロセッサ」または「コントローラ」の明示的な使用は、ソフトウェアを実行することが可能なハードウェアを排他的に指すと解釈されるべきではなく、デジタル信号プロセッサ（ＤＳＰ）ハードウェア、ネットワークプロセッサ、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、ソフトウェアを記憶するための読出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、および非揮発性記憶装置を、限定せずに、黙示的に含むことが可能である。従来のかつ／またはカスタムのその他のハードウェアを含むことも可能である。同様に、図面に示される任意のスイッチは概念的であるに過ぎない。その機能は、プログラム論理の演算を介して、専用論理を介して、プログラム制御と専用論理の相互作用を介して、または手動でさえ実行可能であり、内容からより詳細に理解されるように、特定の技術が実装者によって選択可能である。
【００４５】
本明細書のいずれのブロック図も本発明の原理を実施する例示的な回路の概念図を表す点を当業者は認識されたい。同様に、任意のフローチャート、流れ図、状態遷移図、疑似コードなどは、実質的に機械可読媒体内に表されることが可能であり、そのようなコンピュータまたはプロセッサが明示的に示されていようと、いまいと、コンピュータまたはプロセッサによってそのように実行可能な様々な処理を表す点を理解されよう。
【００４６】
請求項で定義される、本発明の範囲から逸脱せずに、上で説明された本発明の実施形態に多数の修正、改変、および適合を行うことが可能である。
【図１】
0005468146.tif 000002
【図２】
0005468146.tif 000003
【図３】
0005468146.tif 000004
【図４】
0005468146.tif 000005
【図５】
0005468146.tif 000006