(57)【特許請求の範囲】
【請求項１】
複数のドメインを有するパケットネットワーク内で速度整合ドメインを確立する方法であって、
入力インターフェースにおいて、前記速度整合ドメインに対してすぐ上流のドメインからパケットを受信するステップと、
前記受信されたパケットに関連するサービス品質（ＱｏＳ）要件を確立するステップと、
前記受信されたパケットを処理ユニット内で処理するステップと、
出力インターフェースにおいて、前記速度整合ドメインからすぐ下流のドメインに、処理されたパケットを発信するステップと、
状態変数のセットを確立するステップと、
受信されたパケットが前記出力インターフェースを介して発信される速度を制御するために、前記確立された状態変数のセットを用いて前記処理ユニットの動作状態を制御するステップと、
最短の実現可能な出発曲線を満たし、前記速度整合ドメイン内のエネルギー消費を削減するために、最小状態ホールド時間に基づいて、確立された状態変数のセットを選択するステップとを含む、方法。
【請求項２】
前記ＱｏＳ要件が、最大追加遅延を含む、請求項１に記載の方法。
【請求項３】
前記処理ユニットをスリープ状態に置くために状態変数を選択することをさらに含む、請求項１に記載の方法。
【請求項４】
前記処理ユニットのクロック速度を調整するために状態変数を選択することをさらに含む、請求項１に記載の方法。
【請求項５】
前記状態変数を選択するために状態設定ポリシーを使用することをさらに含む、請求項１に記載の方法。
【請求項６】
前記状態設定ポリシーが、前記速度整合ドメインのシステムパラメータに基づいている、請求項５に記載の方法。
【請求項７】
前記パケット処理ステップが、解析すること、修正すること、およびバッファ待ち行列に記憶することからなるグループからの少なくとも１つを含む、請求項１に記載の方法。
【請求項８】
前記状態変数が、前記バッファ待ち行列内の待ち行列長およびトラフィック到着測度からなるグループからの少なくとも１つを含む、請求項７に記載の方法。
【請求項９】
前記実現可能な出発曲線が、最適出発曲線を含む、請求項１に記載の方法。
【請求項１０】
接続されたネットワークノードの複数のサブドメインを有するパケットネットワークにおける速度整合サブドメインにおいて、
前記測度整合サブドメインは、
前記速度整合サブドメインに対してすぐ上流のドメインからパケットを受信するように構成されている入力インターフェースであって、サービス品質（ＱｏＳ）要件のセットが、前記受信されたパケットに関連する、入力インターフェースと、
前記受信されたパケットを処理するように構成されている処理ユニットと、
前記速度整合サブドメインからすぐ下流のドメインに、処理されたパケットを発信するように構成されている出力インターフェースとを具備し、
状態変数が、前記処理ユニットの動作状態を制御し、パケットが前記出力インターフェースを介して発信される速度を制御し、最短の実現可能な出発曲線を満たして前記速度整合ドメイン内のエネルギー消費を削減するために、最小状態ホールド時間に基づいて選択される、速度整合サブドメイン。
【請求項１１】
前記ＱｏＳ要件のセットが、最大追加遅延を含む、請求項１０に記載の速度整合サブドメイン。
【請求項１２】
前記状態変数が、前記処理ユニットをスリープ状態に置く、請求項１０に記載の速度整合サブドメイン。
【請求項１３】
前記状態変数が、前記処理ユニットのクロック速度を調整する、請求項１０に記載の速度整合サブドメイン。
【請求項１４】
状態設定ポリシーが、前記状態変数を選択する、請求項１０に記載の速度整合サブドメイン。
【請求項１５】
前記状態設定ポリシーは、前記速度整合ドメインのシステムパラメータに基づいている、請求項１４に記載の速度整合サブドメイン。
【請求項１６】
バッファ待ち行列をさらに具備し、
前記処理ユニットは、前記処理ユニットにより解析される処理、および、前記処理ユニットにより修正される処理のセットのうちの少なくとも１つがなされているパケットを前記バッファ待ち行列に記憶させる、請求項１０に記載の速度整合サブドメイン。
【請求項１７】
前記状態変数が、前記バッファ待ち行列内の待ち行列長およびトラフィック到着測度からなるグループからの少なくとも１つを含む、請求項１６に記載の速度整合サブドメイン。
【請求項１８】
前記実現可能な出発曲線が、最適出発曲線を含む、請求項１０に記載の速度整合サブドメイン。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、速度整合を用いたエネルギー効率に関し、詳細には、スリープ状態活用技術および速度スケーリング技術の最良の特性を結合させる速度整合方式に関する。
【背景技術】
【０００２】
データネットワーキングサービスおよびデータネットワーキングアプリケーションは、例えば、人および物品の輸送をデータパケットの電子転送と置換することによって、経済活動の広い部門でかなりのエネルギー節約を可能にする。ネットワークサービスおよびネットワークアプリケーションによって提供される置換機能のエネルギー節約収率を最大化するために、パケットネットワーク自体が、すべての構成要素およびすべての機能においてエネルギー効率を包括的に目標としなければならない。したがってエネルギー効率は、ネットワーク設備の設計および能力において最も重要な特性になった。
【０００３】
ネットワークノードは、あるネットワークインターフェースから別のネットワークインターフェースにデータパケット、多くの場合、そのコンテンツの修正部分を転送する。エネルギー消費を最小限に抑えるために、ネットワーク装置内のエネルギー使用は、トラフィック処理活動に比例すべきである。より詳細には、システム内のエネルギー使用は、ネットワークトラフィック負荷に対応すべきであり、システムがパケットを処理しないとき、わずかになるべきである。
【０００４】
速度スケーリングおよびスリープ状態活用は、トラフィック負荷がリンク容量を遥かに下回るとき、ネットワークノード内のエネルギー消費を削減するための人気ある方法である。（参考までに、この開示では、速度スケーリングおよびスリープ状態活用という用語は、速度整合の例として言及される。）
速度スケーリングにより、データパスデバイスのクロック周波数は、一般に、低いトラフィック負荷の下で電力消費レベルを削減するために、周波数と電力との間に存在する線形関係を使用して、トラフィック負荷を追跡するために経時的に変化する。しかし、トラフィック処理速度は動作周波数にも対応するため、周波数削減によって遅延蓄積が引き起こされる可能性がある。遅延蓄積を制御するために、速度スケーリングシステムの動作は、通常、より低い処理速度がトラフィックに課す可能性がある追加遅延に関する限界によって制約される。電力消費レベルの急な削減は、速度スケーリングシステム内に動的な電圧および周波数スケーリング（ＤＶＦＳ）技術を統合することによって取得され得る。ＤＶＦＳデバイスでは、電力供給装置の電圧レベルは、クロック周波数が低減するにつれて、予想可能な動作においてデバイスの電気回路を維持するのに必要とされる最低電圧レベルまで少なくとも低下する場合がある。
【０００５】
スリープ状態活用により、ネットワークデバイスは、処理のためにトラフィックが利用可能な限り最大クロック周波数で動作する全容量状態と電力消費がずっと低いスリープ状態とを交互に行う。
【０００６】
速度スケーリングの方式およびアーキテクチャ、ならびにスリープ状態活用の方式およびアーキテクチャを定義し研究する文献においてかなり多くの取り組みを見出すことができるが、いくつかの課題が依然として未解決のままである。
【０００７】
第１に、隣接する速度整合デバイスの調整に関する明らかな枠組みがまだ利用可能でない。今まで提案されているアーキテクチャを備えたスリープ状態活用技術の場合、調整の不足がエネルギー節約パフォーマンスのかなりの減少をもたらす可能性があると同時に、調整の導入は、標準団体の幅広い合意（例えば、ＩＥＥＥ８０２．３ａｚ  Ｅｎｅｒｇｙ  Ｅｆｆｉｃｉｅｎｔ  Ｅｔｈｅｒｎｅｔ（登録商標）  Ｔａｓｋ  Ｆｏｒｃｅ内の進行中の作業を参照されたい）、またはネットワーク全体の大部分の完全な連携を必要とする。単一の回路パック内ですら、複数の速度スケーリングデバイスのクロック周波数を調整するために、新しい構成要素、および、したがって、エネルギー消費の新しいソースが追加されなければならない。
【０００８】
第２に、速度整合技術に関して提示されるエネルギー節約パフォーマンス結果は、一般に、有望であるが、これらの結果は、所与のデバイス内で利用可能な動作状態の特定のセットと、結果として生じる電力速度（ＰＲ）関数とにひどく依存する。異なる方式が比較されるとき、最良の解決策に関する最終的な選択は、実用的なデバイスの実際のパラメータを入力した後でだけ決定され得る。簡単な設計実践に関する一般的な指針は、依然として利用不可能である。
【０００９】
したがって、当技術分野で利用可能な速度整合技術の制約を克服すると同時に、スリープ状態活用および速度スケーリングの最良の特性を結合させる速度整合に関する方式を有することが望ましいことになる。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】２００４年３月  Ｗｈｉｔｅｐａｐｅｒ、「Ｅｎｈａｎｃｅｄ  Ｉｎｔｅｌ（Ｒ）  ＳｐｅｅｄＳｔｅｐ（Ｒ）Ｔｅｃｈｎｏｌｏｇｙ  ｆｏｒ  ｔｈｅ  Ｉｎｔｅｌ（Ｒ）  Ｐｅｎｔｉｕｍ（Ｒ）Ｍ  Ｐｒｏｃｅｓｓｏｒ」
【発明の概要】
【発明が解決しようとする課題】
【００１１】
本発明の目標は、速度整合を介してネットワークデバイス内のエネルギー効率を達成するための改善されたシステムおよび方法を提供することである。
【課題を解決するための手段】
【００１２】
本発明のある態様によれば、複数のドメインを有するパケットネットワーク内で速度整合ドメインを確立する方法であって、入力インターフェースにおいて、速度整合ドメインに対してすぐ上流のドメインからパケットを受信するステップと、受信されたパケットに関連するサービス品質要件を確立するステップと、受信されたパケットを処理ユニット内で処理するステップと、出力インターフェースにおいて、速度整合ドメインからすぐ下流のドメインにパケットを発信するステップと、状態変数のセットを確立するステップと、パケットが出力インターフェースを介して発信される速度を制御するために、状態変数を用いて処理ユニットの動作状態を制御するステップと、実現可能な出発曲線を満たすためにそのような状態変数を選択するステップと、速度整合ドメイン内のエネルギー消費を削減するためにそのような状態変数をさらに選択するステップとを有する方法が提供される。
【００１３】
本発明のいくつかの実施形態では、サービス品質要件は、最大追加遅延を含む。
【００１４】
本発明のその他の実施形態では、さらに選択するステップは、処理ユニットをスリープ状態に置くために状態変数を選択するか、または処理ユニットのクロック速度を調整するために状態変数を選択する。
【００１５】
有利には、いくつかの実施形態では、選択するステップは、状態変数を選択するために、状態設定ポリシーを使用する。同様に、いくつかの実施形態では、状態設定ポリシーは、速度整合ドメインのシステムパラメータに基づく。速度整合ドメインのシステムパラメータは、電力速度関数、状態遷移時間、または最小状態ホールド時間のうちの少なくとも１つの含むことが可能である。
【００１６】
本発明のいくつかの実施形態では、パケットを処理するステップは、解析すること、修正すること、およびバッファ待ち行列に記憶することからなるグループからの少なくとも１つを含む。また、いくつかの実施形態では、状態変数は、バッファ待ち行列内の待ち行列長およびトラフィック到着測度からなるグループからの少なくとも１つを含む。
【００１７】
有利には、いくつかの実施形態では、実現可能な出発曲線は、最適出発曲線を含む。
【００１８】
本発明の別の態様によれば、動的電圧および周波数スケーリング動作モードと、スリープ活用動作モードとを有するパケット処理デバイスを動作させる方法であって、スリープ状態活用動作モードに起因する、パケット処理デバイスに関する第１の電力速度曲線を確立するステップと、動的電圧および周波数スケーリング動作モードに起因する、パケット処理デバイスに関する第２の電力速度曲線を確立するステップと、パケット処理の特定の速度に関するエネルギー消費を最小限に抑えるために、スリープ状態活用モードまたは動的電圧および周波数スケーリングモードのうちの１つを選択することによって、パケット処理デバイスを動作させるステップとを含む方法が提供される。
【００１９】
本発明のいくつかの実施形態では、第１の電力速度曲線と第２の電力速度曲線の交点を確立して、交点を下回る速度で、エネルギー消費を最小限に抑える動作モードを選択して、交点を上回る速度で、代替の動作モードを選択する追加のステップが存在する。
【００２０】
本発明のその他の実施形態では、第１の電力速度曲線と第２の電力速度曲線の交点を確立して、交点を下回る速度で、スリープ状態活用動作モードを選択して、交点を上回る速度で、動的電圧および周波数スケーリング動作モードを選択する追加のステップが存在する。
【００２１】
本発明の別の態様によれば、パケットネットワーク内に速度整合サブドメインが提供され、パケットネットワークは、接続されたネットワークノードの複数のサブドメインを有し、速度整合サブドメインは、速度整合サブドメインに対してすぐ上流のドメインからパケットを受信するための入力インターフェースと、受信されたパケットに関連するサービス品質要件のセットと、受信されたパケットを処理するための処理ユニットと、速度整合サブドメインからすぐ下流のドメインにパケットを発信するための出力インターフェースと、処理ユニットの動作状態を制御するための状態変数のセットであって、状態変数が、パケットが出力インターフェースを介して発信される速度を制御する、状態変数のセットと、実現可能な出発曲線を満たすために選択されたそのような状態変数の初期サブセットと、速度整合ドメイン内のエネルギー消費を削減するために選択された状態変数のサブセットのさらなるサブセットとを有する。
【００２２】
本発明のいくつかの実施形態では、サービス品質要件のセットは、最大追加遅延を含む。
【００２３】
本発明のいくつかの実施形態では、状態変数のさらなるサブセットは、処理ユニットをスリープ状態に置き、一方、その他の実施形態では、状態変数のさらなるサブセットは、処理ユニットのクロック速度を調整する。
【００２４】
有利には、本発明のいくつかの実施形態は、状態変数の初期のサブセットを選択するために使用される状態設定ポリシーを有する。これらの実施形態のうちのいくつかでは、状態設定ポリシーは、速度整合ドメインのシステムパラメータに基づく。速度整合ドメインのシステムパラメータは、電力速度関数、状態遷移時間、および最小状態ホールド時間からなるグループからの少なくとも１つを含むことが可能である。
【００２５】
本発明のいくつかの実施形態では、バッファ待ち行列も存在し、処理ユニットは、処理ユニットによって解析または修正されているパケットを記憶することが可能である。
【００２６】
本発明のいくつかの実施形態では、状態変数は、バッファ待ち行列内の待ち行列長またはトラフィック到着測度のうちの少なくとも１つを含む。
【００２７】
有利には、いくつかの実施形態では、実現可能な出発曲線は、最適出発曲線である。
【００２８】
注記。以下の説明では、記述および図面は、本発明の原理を単に例示する。したがって、当業者は、本明細書で明示的に記述または示されていないが、本発明の原理を具体化し、本発明の趣旨および範囲内に含まれる様々な構成を考案することができる点を理解されよう。さらに、本明細書で列挙されるすべての実施例は、読者が当技術分野を推進する目的で、本発明の原理および（１人または複数の）発明者によって寄与された構想を理解するのを助けるための教育的な目的のみが特に主として意図されており、そのような詳細に列挙された実施例および条件に対する限定なしに解釈されるべきものである。さらに、本発明の原理、態様、および実施形態、ならびにそれらの特定の例を列挙する本明細書のすべての記述は、それらの均等物を包含することが意図される。
【００２９】
本発明は、図面を参照して、本発明の実施形態の以下の詳細な説明からさらに理解されよう。
【図面の簡単な説明】
【００３０】
【図１】知られている技術による、データパスによって接続されたネットワークノードの一例を示す図である。
【図２ａ】知られている技術による、双方向リンクによって接続されたネットワークノードのセットを例示する図である。
【図２ｂ】双方向リンクがその一方向構成要素に分割される、図２ａの代替バージョンを例示する図である。
【図２ｃ】頂点が速度整合ドメインを表し、辺がドメイン同士の間のインターフェースを表す、図２ｂの有向グラフバージョンを例示する図である。
【図３ａ】到着曲線と出発曲線のセットを例示する図である。
【図３ｂ】到着曲線と出発曲線のセットを例示する図である。
【図４ａ】図３ａの到着曲線に関する最適サービス曲線のセットを例示する図である。
【図４ｂ】図３ｂの到着曲線に関する最適サービス曲線のセットを例示する図である。
【図５】本発明のある実施形態による、速度整合ドメインに関する動作間隔のシーケンスを例示するプロットである。
【図６】速度スケーリングデバイスに関する異なる動作領域を例示するプロットである。
【図７】スリープ状態活用デバイスに関する電力消費を例示するプロットである。
【図８】速度スケーリングおよびスリープ状態活用デバイスのハイブリッド結合に関する電力消費を例示するプロットである。
【図９】本発明のある実施形態による、スリープ状態活用から速度スケーリングへの最適電力関数遷移ポイント（ｏｐｔｉｍａｌ  ｐｏｗｅｒ  ｆｕｎｃｔｉｏｎ  ｔｒａｎｓｉｔｉｏｎ  ｐｏｉｎｔ）を例示するプロットである。
【図１０】本発明の実施形態による、いくつかのバックログ処理ポリシーのエネルギー利得に関する比較プロットである。
【図１１】本発明の実施形態による、２つの特定の強バックログ処理ポリシーの追加遅延に関するさらなる比較プロットである。
【図１２】本発明のある実施形態による、速度スケーリングをスリープ状態活用と結合させる速度整合方式の効果を示すパフォーマンスプロットである。
【図１３】本発明のある実施形態による、速度整合方式の遅延パフォーマンスをその基本的な速度スケーリング方式と対比させる比較プロットである。
【発明を実施するための形態】
【００３１】
以下は、この明細書を通じて使用される用語および概念の定義である。やはり記述されるのは、速度整合方式のエネルギー節約パフォーマンスを評価するために使用される基準モデルである。
【００３２】
速度整合ネットワーキングデバイスは、１つまたは複数のインターフェースを介してデータパケットを受信および転送し、そのデバイスに提供されているトラフィック負荷に対して動作状態を調整することができるデバイスである。この速度整合デバイスは、動作状態の有限セットＳ＝｛ｓｋ、ｋ＝１．．．Ｋ｝を用いて構成され、式中、それぞれの状態は、クロック周波数（ｆｋ）および電源電圧（Ｖｋ）：ｓｋ≡（ｆｋ、Ｖｋ）の固定値によって識別される。独自のトラフィック処理容量ｒをすべての周波数値ｆと関連付けることが可能であるため、それぞれの処理容量を参照することによって動作状態を表すことができる。Ｓｋ＝（ｒｋ、Ｖｋ）。それぞれの状態ｓｋに関して、デバイスが、トラフィックを処理している、
【００３３】
【数１】
0005607177.tif 000002
またはトラフィックを処理していない、
【００３４】
【数２】
0005607177.tif 000003
または異なる状態
【００３５】
【数３】
0005607177.tif 000004
から状態ｓｋに遷移しているかどうかに応じて、アクティブサブ状態
【００３６】
【数４】
0005607177.tif 000005
と、アイドルサブ状態
【００３７】
【数５】
0005607177.tif 000006
と、遷移サブ状態
【００３８】
【数６】
0005607177.tif 000007
とがさらに定義される。速度整合デバイスに関するエネルギーモデルの一次近似では、固定レベルの電力消費
【００３９】
【数７】
0005607177.tif 000008
は、それぞれのサブ状態と関連付けられる。３つの電力消費レベルは、それぞれ、アクティブ電力、アイドル電力、および遷移電力と呼ばれる。
【００４０】
所与のデバイスに関して、状態遷移を完了するために必要とされる時間である遷移時間δは、固定されて、遷移に伴う２つの状態から独立することが仮定される：δ（ｓｊ、ｓｋ）＝δ∀（ｊ、ｋ）。控えめな仮定として、状態遷移の間にトラフィック処理は発生し得ないことが仮定される。
【００４１】
方程式（１）は、それぞれのサブ状態内で費やされた時間に基づいて存続時間間隔Ｔ
を通して消費されたエネルギーを表す：
【００４２】
【数８】
0005607177.tif 000009
アイドル電力は、アクティブ電力よりも常に低いことになることが楽に仮定できる。
【００４３】
【数９】
0005607177.tif 000010
デバイスが状態遷移の間にアイドル状態に留まることを考慮すると、遷移電力
【００４４】
【数１０】
0005607177.tif 000011
は、状態遷移の前後の状態に関するアイドル電力の平均、したがって、両方の状態の関数と定義されるべきである点を主張することは妥当である：
【００４５】
【数１１】
0005607177.tif 000012
変動負荷レベルの下で、ある状態へのいずれの遷移に関しても、同じ状態からの遷移が常に存在することに注目すると、その状態ｓｋに関するインバウンドアイドル電力寄与およびアウトバウンドアイドル電力寄与は、インバウンド状態遷移に関して固定遷移電力
【００４６】
【数１２】
0005607177.tif 000013
に集約されることが可能であり、それに応じて、アウトバウンド遷移に関して遷移電力からアイドル電力寄与
【００４７】
【数１３】
0005607177.tif 000014
を除去する。方程式（１）は、このとき、以下のように書き直されてよい：
【００４８】
【数１４】
0005607177.tif 000015
方程式（２）は、異なる速度整合方式のエネルギー節約パフォーマンスを比較するための参照の測定基準（ｍｅｔｒｉｃ  ｏｆ  ｒｅｆｅｒｅｎｃｅ）である。
【００４９】
スリープ状態活用デバイスでは、２つの動作状態、すなわち、全容量状態ｓｃ≡（Ｃ，Ｖｃ）およびスリープ状態Ｓｓ≡（０，Ｖｓ）だけが利用可能である。エネルギー方程式は、以下のようになる：
【００５０】
【数１５】
0005607177.tif 000016
スリープ状態の削減された電力消費を利用するために、デバイスは、処理されることになるパケットが存在しないときはいつでも、
【００５１】
【数１６】
0005607177.tif 000017
であるように、全容量状態から遷移しなければならない：
【００５２】
【数１７】
0005607177.tif 000018
スリープ状態活用は、全容量状態で費やされた時間を制限することによって、平均提供トラフィック負荷（ａｖｅｒａｇｅ  ｏｆｆｅｒｅｄ  ｔｒａｆｆｉｃ  ｌｏａｄ）λと整合する：
【００５３】
【数１８】
0005607177.tif 000019
速度スケーリングデバイスでは、方程式（２）は、利用可能な動作状態のセット内にスリープ状態は含まれないという制限だけを伴いながら、依然として基準エネルギー方程式である。このデバイスは、それぞれの動作状態で費やされた時間の適切な分布によって、提供された負荷と整合する：
【００５４】
【数１９】
0005607177.tif 000020
デバイスの電力速度関数の凹状のタイプは、速度整合方式の選択を促進すべきであり、関数が利用可能な処理能力の全セットを介して凹状、すなわち、（（Ｐ（ｒ１）＋Ｐ（ｒ２））／２≦Ｐ（（ｒ１＋ｒ２）／２）∀ｒ１＜ｒ２である場合、削減されたエネルギー消費のすべてにおいて効果的な場合、スリープ状態活用の採用は当然の選択である。代わりに、曲線が凸状、すなわち、（Ｐ（ｒ１）＋Ｐ（ｒ２））／２≧Ｐ（（ｒ１＋ｒ２）／２）∀ｒ１＜ｒ２である場合、適切に設計された速度スケーリング方式はより高いエネルギー節約をもたらし得る。
パケットネットワークの速度整合表現
いくつかの速度整合技術が任意のエネルギー節約利得を生み出すために、隣接するネットワークノード同士の間の厳密な調整が必要であることは歴史的に主張されてきた。新しい技術が任意のマルチプレイヤ環境において一夜にして包括的に展開されることを合理的に期待することはできないため、調整の必要はそれらの技術の展開を妨げている。以下の展開は、単純なデータパス抽象化を介して、両方とも、個々のネットワークノード内で、かつネットワーク全体の中で、調整の必要性は完全に除去されることが可能であり、速度整合デバイスがインクリメンタルに展開され得ることを示す。
【００５５】
図１を参照すると、速度整合デバイス１０２がインターフェース１０６を介してパケットを速度整合デバイス１０４に転送する、最も単純なデータパス構成１００の一例を理解されよう。
【００５６】
デバイスＡおよびＢは、場合によっては同一である、速度整合動作状態のそれぞれのセットを用いて構成される。インターフェースＣの性質は、デバイスＡおよびＢの状態が一緒に制御されなければならないか、または別個に制御され得るかを決定する：
インターフェースＣが、Ｃを介して転送された任意のデータの完全性が保存されるように、両方のデバイスが一貫した速度整合状態になることを必要とする場合、デバイスＡおよびＢの状態は一緒に制御されなければならない。これは、デバイスＡおよびＢが同じ速度整合ドメインに属する事例の一例であろう。装置の一例として、光ファイバの２つの終端における送信機および受信機は、同じ速度整合ドメインの一部と理解されてよい。
【００５７】
インターフェースＣを介したデータ転送の完全性がデバイスＡおよびＢの動作状態から独立して保存される場合、これら２つのデバイス間に調整の必要性は存在せず、したがって、これら２つのデバイスは、別個の速度整合ドメインに属する。一例として、ルータのラインカードのパケット処理パイプライン内のバッファメモリによって分離された２つのデバイスは、別個の速度整合ドメインに属し、書込み動作および読取り動作のためにバッファメモリが異なる速度でアクセスされ得る限り、その動作状態は調整を厳密に必要としない。
【００５８】
より形式的な定義として、速度整合ドメインは、すぐ上流のドメインからパケットが受信される１個の入力インターフェースと、パケットが解析されること、修正されること、またはバッファ待ち行列に割り当てられることが可能な処理ユニットと、それを介してすぐに下流のドメインにパケットが発信される１個の出力インターフェースとからなり得る。速度整合ドメインは、処理ユニットの動作状態、したがって、パケットが出力インターフェースを介して転送される速度を促進する状態変数を維持する。安定性のために、出力インターフェースの最大送信能力および処理ユニットの最大処理能力は同一であり、入力インターフェースの最大容量を下回ることは決してないことが仮定される。
【００５９】
図２ａを参照すると、双方向リンクＬ１  ２０６およびＬ２  ２０８に接続された３個のネットワークノードｎ１２０１、ｎ２２０２、およびｎ３２０３を理解されよう。ノードｎ２２０２は、例えば、出力待ち行列２×２スイッチファブリックを備えたルータであってよい。図２ｂを参照すると、それぞれの双方向リンクはその２つの一方向構成要素に分割される（Ｌ１  ２０６はｌ１，２２１２とｌ２，１２２１とに分割され、Ｌ２  ２０８は、ｌ２，３２２３とｌ３，２２３２とに分割されることを理解されよう。この表現は、頂点ｖ１２７１からｖ６２７６が速度整合ドメインを表し、辺ｅ１２６１からｅ５２６５がそれらの頂点同士の間のインターフェースを表す図２ｃの有向グラフに示されるようにさらに構成され得る。
【００６０】
より詳細には：
頂点ｖ１２７１は、リンクｌ１，２２１２の２つの終端においてｎ１２０１送信機とｎ２２０２受信機とを含む。
【００６１】
辺ｅ１２６１は、リンクｌ１，２２１２から到着するパケット専用の、ｎ２２０２内のパケットメモリの部分である。
【００６２】
頂点ｖ２２７２は、リンクｌ３，２２３２の２つの終端においてｎ３２０３送信機とｎ２２０２受信機とを含む。
【００６３】
辺ｅ２２６２は、リンクｌ３，２２３２から到着するパケット専用の、ｎ２２０２内のパケットメモリの部分である。
【００６４】
頂点ｖ３２７３は、リンクｌ２，１２１２およびｌ３，２２３２からのパケットストリームを多重化する、ｎ２２０２内のインターフェース集約モジュールである。
【００６５】
辺ｅ３２６３は、異なる入力リンクからのパケットが単一の待ち行列内に並ぶバッファである。
【００６６】
頂点ｖ４は、パケットをそのそれぞれの出口待ち行列に割り当てて、送信に先立って、それらのパケットを修正に向けて準備する、ｎ２２０２内のヘッダ解析モジュールである。
【００６７】
辺ｅ４２６４は、ノードｎ１２０１への送信を待っているパケットが待ち行列に入れられるバッファである。
【００６８】
辺ｅ５２６５は、ノードｎ３２０３への送信を待っているパケットが待ち行列に入れられるバッファである。
【００６９】
頂点ｖ５は、リンクｌ２，１２２１の２つの終点においてｎ２２０２送信機とｎ１２０１受信機とを含む。
【００７０】
頂点ｖ６は、リンクｌ２，３２２３の２つの終点においてｎ２２０２送信機とｎ３２０３受信機とを含む。
【００７１】
速度整合機能を備えたネットワークシステムの設計では、システムの有向グラフ表現は、速度整合デバイスの挿入の機会を識別するのに役立つ。同様に、有向グラフ表現は、少数の速度整合ドメイン（より低い遅延ペナルティ）を有する設計の利点と、より多くのドメイン（より低い複雑性）を有する設計の利点との間のトレードオフを認識することを可能にする。有向グラフ表現は、実際に、ネットワークノード同士の間の厳密な調整がパケットネットワーク内の速度整合機能を導入するための必要条件でないことを明らかにする。速度整合ドメインを独力で形成する速度整合デバイスは、装置のベンダーおよびサービスプロバイダからの調整された取り組みを必要とせずに、ネットワークにインクリメンタルに追加され得る。例えば、システム設計者が速度整合トランシーバを有さないラインカード内に速度整合ネットワークプロセッサを含めることができることが明らかになる。
【００７２】
以下の開示は、ドメイン同士の間のいかなる調整も完全に回避する、速度整合ドメインの動作状態を制御するための方法に重点を置く。
速度整合方式に関する実装指針
以下の議論は、速度整合方式の効果的な実装に関する一般的な指針を特定する。
【００７３】
隔離状態の速度整合ドメインを考慮する。その状態設定ポリシーを通じて、速度整合方式は、着信トラフィックのサービス品質（ＱｏＳ）要件に違反せずに、ドメイン内のエネルギー消費を最小限に抑える目的を有するパケット到着のシーケンスに応答して、動作状態のシーケンスを設定する。異なるタイプのトラフィックは、それぞれのＱｏＳ制約を通じて表現される、異なるタイプのＱｏＳ要件を提示することが可能である。
【００７４】
ここで列挙されるのは、いくつかの有用な定義および意味である：
到着曲線Ａ（ｔ）、ｔ≧０は、時間間隔［０，ｔ］内で速度整合ドメインに到着したビットの数を計数する右連続関数である。実際の非流体ドメインでは、ビットがパケット内にグループ化されて、パケットのすべてのビットが最後のビットが到着した後でだけ処理のために利用可能であると見なされる場合、Ａ（ｔ）は段階関数である。
【００７５】
出発曲線Ｄ（ｔ）、ｔ≧０は、時間間隔［０，ｔ］内で速度整合ドメインから出発したビットの数を計数する右連続関数である。
【００７６】
所与の到着曲線Ａ（ｔ）の場合、最小出発曲線Ｄｍｉｎ（ｔ）は、Ｄｍｉｎ（ｔ）≦Ａ（ｔ）、ｔ≧０であり、速度整合ドメインのＱｏＳ要件を満たすために、時間ｔまでに出発しなければならない最小数のビットとして定義されるような出発関数である。
【００７７】
着信トラフィックのＱｏＳ要件を満たすために、速度整合方式によって設定された動作状態のシーケンスは、最小出発曲線（ＱｏＳ制約）と到着曲線（因果性制約）との間に常に存在する出発曲線を生み出さなければならない。
【００７８】
Ａ（ｔ）≧Ｄ（ｔ）≧Ｄｍｉｎ（ｔ）、ｔ≧０
そのような出発曲線は、実現可能と呼ばれる。図３ａを参照すると、２つのタイプの遅延ベースのＱｏＳ制約に基づく、所与の到着曲線Ａ（ｔ）に関する最小出発曲線Ｄｍｉｎ（ｔ）および実現可能な出発曲線Ｄ（ｔ）を理解されよう。
【００７９】
図３ａの例では、ＱｏＳ制約は、時間０と時間Ｔの間に到着するすべてのパケットが時間Ｔまでに配信されることを要求する。図に示される実現可能な出発曲線は、増大している処理容量を有する３つの動作状態ｓ１、ｓ２、およびｓ３のシーケンスから派生する。図３ｂの場合、最大遅延ｄがすべてのパケットの送信に関して許容される。示される実現可能な出発曲線は、２つの動作状態ｓ１およびｓ２のシーケンスから取得され、この場合、第１の状態はヌル処理容量を有する。
【００８０】
凸状電力速度関数を備えたシステムの場合、最適出発曲線Ｄｏｐｔ（ｔ）と呼ばれる、エネルギー消費を最小限に抑える出発曲線は、ポイント（０，Ａ（０））と（Ｔ，Ｄｍｉｎ（ｔ））との間の最短の実現可能な曲線であることが知られている。結果の迅速な可視化のために、以下が示唆されている：
「Ａ（ｔ）とＤｍｉｎ（ｔ）との間に存在するように制限されたストリングを考慮する。起点のその一方の終端を結び、もう一方の終端をＤｍｉｎ（ｔ）に通過させる。このとき、ストリングが張る場合、その軌跡は最適曲線と同じである。」
図４ａおよび４ｂは、それぞれ、図３ａおよび３ｂの２つの例に関する最適サービス曲線を示す（図３および図４の曲線を図示するために、瞬時状態遷移が仮定される点に留意されたい）。
【００８１】
凸状電力速度関数に関する「最短ストリング結果」は、速度整合ドメインの処理容量が、そのタスクを完了するために利用可能なまさにその時間までにＱｏＳ制約を満たすために必要とされる平均速度に等しく設定されるとき、エネルギー最小化が実現されることを示す。
【００８２】
図４に示される結果に関して、実用的な速度整合ドメインとより抽象的な基準システムとの間で以下の差異が識別され得る。
【００８３】
１．抽象的な基準システムでは、利用可能な処理容量の連続的な範囲を有する動作状態が無限セットから選択されることが可能であり、実用的な速度整合ドメイン内で、利用可能な処理容量の離散値を有する動作状態のセットは有限である。結果として、実用的なドメインに関する最適出発曲線は、通常、理想的なシステムに関する最適曲線よりもより低いエネルギー節約をもたらす。
【００８４】
２．抽象的なシステムでは、すべての状態遷移は瞬時であり、実用的なドメインでは、状態遷移は、その間にトラフィック処理が発生し得ない固定時間量内で完了する。
【００８５】
３．連続的なビットのストリームを処理する抽象的なシステムでは、状態遷移は、任意の時点で発生し得る。アトミックパケット（ａｔｏｍｉｃ  ｐａｃｋｅｔｓ）内でビットを処理する実用的なドメインでは、状態遷移はパケット処理境界でだけ発生し得る。
【００８６】
４．抽象的なシステムでは、到着曲線Ａ（ｔ）は知られており、その結果、最小出発曲線Ｄｍｉｎ（ｔ）は、トラフィックが到着し始める前に、到着曲線Ａ（ｔ）を中心にして調整されることが可能であり、実用的なドメインでは、到着曲線は知られていない。
【００８７】
単一の速度整合ドメインを横断するすべてのパケットに関して、所与の遅延制約ｄに決して違反しない実用的な速度整合方式を実施することが所望される。この実装形態に取り組む際に、以下の３つの側面に沿って議論が展開される：すなわち、
１．時間軸の動作間隔への再分割、
２．基準電力速度関数の最適化、および
３．状態設定ポリシーの仕様、である。
動作間隔
実用的な速度整合ドメイン内の状態遷移の延長期間は、時間軸を可変存続時間間隔に再分割する原動力となるが、最小ホールド時間と呼ばれる固定量ｈより短くなることは決してない。実際に、状態遷移の時間コストδは、状態遷移が速度調整ドメインの動作時間の大部分を占有するのを回避するために、頻繁な状態遷移は阻止されなければならないことを意味する。ドメインがその動作時間切替え状態のかなりの部分を費やすことが可能にされる場合、ドメインは、より高い電力レベルで、より短い時間間隔内ですべてのトラフィック処理作業を実行しなければならない。作業を伴わない遷移の間に消費されたエネルギーを計数しない場合ですら、凸状電力速度関数により、最適平均速度ポイントからの動作状態の単なる偏差は、かなりのエネルギー損失を引き起こす。ドメインの動作状態を最小ホールド時間ｈ＞＞δの間に変更しない状態に留まらせることは、総遷移時間を総動作時間の許容可能な割合未満に維持する。
【００８８】
本出願人の目標速度整合方式は、速度整合ドメインの動作を可変存続時間期間ｈｎ、ｈｎ＞ｈの動作間隔（ｔｎ、ｔｎ＋１］のシーケンスに分割する。任意の動作間隔内の動作状態（および、処理容量）は、直後に続く間隔内の状態（および、容量）とは常に異なる。これらの関係は、図５を参照することによって理解されよう。
【００８９】
一般的な動作間隔（ｔｎ、ｔｎ＋１］を参照すると、速度整合方式は、時間ｔｎにおいて異なる動作状態を設定することを決定する。時間ｔｎ＋δにおいて、状態遷移は完了し、速度整合ドメインは、トラフィック処理を再度開始することができる。時間ｔｎ＋ｈから始まり、状態設定ポリシーが、動作状態が変更されることを必要とする場合、速度整合ドメインはすべてのパケット処理完了を検査する。速度整合ドメインがパケットの処理を完了して、状態設定ポリシーが状態変更の必要性を示すとき、時間ｔｎ＋１＝ｔｎ＋ｈｎ≧ｔｎ＋ｈにおいて、動作間隔の終点に達する。
電力速度関数の最適化
速度整合ドメインの電力速度関数は、アクティブサブ状態における処理容量と電力消費との間の関係を定義する。実用的なデバイスでは、電力速度関数は、通常、離散的容量値の有限セットに関して定義される。しかし、提示の便宜上、かつ実用的なドメインの離散的容量値のセットの構成それ自体が設計選択を構成することを考慮した後で、この節は、容量値の連続的な範囲に関して定義される電力速度関数を参照する。
【００９０】
トラフィック負荷条件に対してその動作状態を迅速に調整することができる商用速度整合ネットワークデバイスの現在の欠如は、状態遷移時間および電力速度関数など、主なパラメータに関する実数の欠如を生じさせる。しかし、より大きな時間スケールを介してだけ制御される、動作状態の拡張されたセットを提供するためのＤＶＦＳ機能を組み込んだスリープ状態活用デバイスおよび速度スケーリングデバイスは、実に存在し（詳細には、汎用プロセッサ［ＩＮＴＥＬＰＸＡ，ＩＮＴＥＬＰＥＮＴＩＵＭ］）、将来のデバイスが何を達成できるかの合理的な表示を取得するために使用され得る。
【００９１】
次に、ＤＶＦＳ可能な速度スケーリングデバイスに重点を置くと、その電力速度関数に関して一般に受け入れられている結論は、その２つの異なる動作領域へのその区分化である。これらの２つの異なる動作領域は、動作状態の有限セットが明示的にマーキングされている図６で理解されよう。容量範囲の上部において、関数は明らかに、速度スケーリング機能の展開を促す凸状である。しかし、速度スケーリングの利点は、特に、非常に低い動作周波数に関して、容量範囲の下部においてより不明瞭になる。行動上の不連続性をマーキングする容量しきい値は、デバイス全体にわたって明らかに変化し、すべての事例において、エネルギー節約利点の損失は、デバイスの動作状態を低容量領域内に設定することを無意味にするほどである。結果として、より重いトラフィック負荷が高利得領域内で動作状態に維持するとき、速度スケーリングデバイスのエネルギー効率は優れているが、より軽いトラフィック負荷の下では不十分である。
【００９２】
ここで、その動作が全容量状態ｓｃ≡（Ｃ，Ｐｃ）とスリープ状態ｓｓ≡（０，Ｐｓ）とを交互に行うスリープ状態活用デバイスの等価電力速度関数を考慮することは妥当である。瞬時状態遷移（δ＝０）を伴うデバイスの理想的な事例では、等価電力速度関数は連続関数であり、この場合、存続時間間隔Ｔにわたるデバイスの動作状態は、以下のように、全容量状態で費やされる時間Ｔｃから導出される。Ｐｅｑ（Ｔ）＝［Ｐｃ・Ｔｃ＋Ｐｓ・（Ｔ−Ｔｃ）／Ｔ。図７を参照されたい。
【００９３】
同一の全容量状態ｓｃ≡（Ｃ，Ｐｃ）を有する速度スケーリングデバイスとスリープ状態活用デバイスとが比較され、前者における最小容量電力Ｐ０が後者におけるスリープ状態電力Ｐｓよりも高いという条件が当てはまる場合、図８を参照すると、スリープ状態活用デバイスは容量範囲の下部（ｒ＜ｒＴ、式中、ｒＴは、２つの曲線が交差する容量の値である）でより良好なエネルギー節約をもたらし、一方、速度スケーリングデバイスは上部（ｒ＞ｒＴ）で優勢であることが容易に観察され得る。
【００９４】
図８は、軽い負荷の下で（すなわち、ｒＴ未満のトラフィック到着速度の場合）スリープ状態活用を用い、より重い負荷の下で（すなわち、ｒＴを上回るトラフィック到着速度の場合）速度スケーリングを用いる実用的な速度整合デバイスにおいて最適電力速度関数が見出され得ることを示唆する。そのようなハイブリッド電力速度関数を有するデバイスが基本的な速度スケーリングデバイスおよびスリープ状態活用デバイスを超えて改善することになることは確かであるが、最適電力速度関数が、利用可能な速度スケーリング技術の電力速度関数から始めて、そのグラフに基づく領域を最小限に抑える関数であるという観察に基づいて、さらに良好なハイブリッド電力速度関数が定義され得る。実際に、最小領域条件は、可能な最小電力レベルを利用可能なそれぞれの動作状態と関連付ける関数を定義する。そのような関数に関する曲線は、単一の地点で２つの構成要素を結合することによって取得される（ｒＴ，ｏｐｔ，ＰＴ，ｏｐｔ）、この場合、速度スケーリング曲線の接線は（０，Ｐｓ）内のＰ軸と交差する。実際に、凸状曲線の定義によって、その曲線よリ下の固定点（０，Ｐｓ）を含む曲線の接線は、凸状曲線と常に交差する同じポイントによってすべての直線からの最小勾配を伴う直線でもある。
【００９５】
図９は、（ｒＴ，ｏｐｔ，ＰＴ，ｏｐｔ）のそのような定義が、エネルギー消費を最小限に抑える定義である理由をグラフで例示する：結合点の処理容量のより下への移動（ｒＴ，ｉ＜ｒＴ，ｏｐｔ）またはより上への移動（ｒＴ，ｈ＞ｒＴ，ｏｐｔ）が存在しようとしまいと、結果は、ハイブリッド曲線の下のより大きな区域で終わる。数学形式では、ｒＴ，ｏｐｔは、
【００９６】
【数２０】
0005607177.tif 000021
であるように、処理容量の値として定義される。
【００９７】
式中、Ｐｒｓ（ｒ）は、元の速度スケーリングドメインの電力速度関数である。
状態設定ポリシーの仕様
状態設定ポリシーは、速度整合方式のコアである。状態設定ポリシーは、システムパラメータ（電力速度関数、遷移時間δ、および最小ホールド時間ｈ）、ＱｏＳ制約（最大追加遅延ｄ）、ならびに状態変数（待ち行列長Ｑ、およびトラフィック到着測度）に基づいて、それぞれの状態遷移の時間および目的地を設定する。
【００９８】
第１に対処されるのは、状態遷移が発生する時間の決定である。先の節において、状態遷移のコストを負担するために、ドメインは、その遷移を開始した後で、少なくとも時間ｈの間、結果として生じた状態に留まるべきであることが確立された。動作間隔の間、ドメインの処理容量は変更しない状態に留まる。
【００９９】
ｈの値を設定する際に、トレードオフは、状態遷移の悪影響を最小限に抑えるためにｈを延長すること（遷移時間δによって引き起こされる処理容量の損失を補償するために、最高でｈ／（ｈ−δ）までの平均処理速度の増大が必要とされること）と、到着曲線Ａ（ｔ）を追跡する際に出発曲線Ｄ（ｔ）の精度を改善するためにｈを短縮すること（ｈが大きければ大きいほど、２つの曲線が分岐しなければならない時間がより長くなること）との間にある。遅延制約ｄは、到着曲線と出発曲線との間の最大許容距離を表すため、遅延制約ｄは、ｈの仕様を促進するために使用され得る。
【０１００】
以下の定義は、状態設定ポリシーの分類を促進する重要な特性である。
【０１０１】
弱バックログ処理特性。動作間隔の開始時ｔ０に、状態設定ポリシーは、動作間隔の最も近い可能な終点（ｔ１＝ｔ０＋ｈ）までに現在の待ち行列バックログＱ（ｔ０）＞０を処理するために十分な利用可能な容量のセットから処理容量を選択する：ｒ（ｔ０）∈｛ｒｋ：Ｓｋ∈Ｓ∧ｒｋ≧Ｑ（ｔ０）／（ｈ−δ）｝。そのような容量が利用可能でない場合、状態設定ポリシーは、速度整合ドメインの完全容量を選択する：ｒ（ｔ０）＝Ｃ。
【０１０２】
弱バックログ処理特性を保持する状態設定ポリシーは、弱バックログ処理ポリシーと呼ばれる。弱バックログ処理特性は、ヌルバックログの事例（すなわち、Ｑ（ｔ０）＝０のとき）には意味を有さない点に留意されたい。
【０１０３】
以下の定理は、流体速度適合ドメインにおけるｄとｈとの間の関係を提示し、この場合、ビットは、パケット境界を伴わずに連続的なストリームで到着する。
【０１０４】
定理１。弱バックログ処理ポリシーを有する流体速度整合ドメインにおいて、遅延制約ｄは、以下のように制限される：
ｄ＜ｄｍａｘ＝２ｈ＋δ  （８）
証明。一般性を失わずに、ｔ０を動作間隔の開始時間とし、この場合、状態設定ポリシーは、ｒ（ｔ０）＞Ｑ（ｔ０）／（ｈ−δ）であるように処理容量ｒ（ｔ０）を選択する。時間ｔ１＝ｔ０＋ｈにおいて、速度整合ドメインが処理容量を設定する次の機会を有するとき、待ち行列バックログは、Ｑ（ｔ１）＝Ｑ（ｔ０）＋Ａ（ｔ０，ｔ１）−ｒ（ｔ０）・（ｈ−δ）≦Ｃ・ｈであり、式中、Ａ（ｔ０，ｔ１）≦Ｃ・ｈは、ｔ０とｔ１との間で受信されたビットの数である。時間ｔ１において、ドメインは、Ｑ（ｔ１）≦Ｃ・（ｈ−δ）である場合、ｒ（ｔ１）≧Ｑ（ｔ１）／（ｈ−δ）であるか、またはＱ（ｔ１）＞Ｃ・（ｈ−δ）である場合、ｒ（ｔ１）＝Ｃであるように処理容量ｒ（ｔ１）を設定する。
【０１０５】
前者の事例は、場合によっては異なる速度だけを用いて時間ｔ０においてこれらの条件を再生するため、この事例は自明である。
【０１０６】
後者の事例では、処理容量を設定するための次の有用な時点（ｔ２）での待ち行列バックログは、Ｑ（ｔ２）＝Ｑ（ｔ１）＋Ａ（ｔ１，ｔ２）−Ｃ・（ｈ−δ）≦２Ｃ・ｈ−Ｃ・（ｈ−δ）＝Ｃ・（ｈ＋δ）である。時間ｔ２において、Ｑ（ｔ２）≦Ｃ・（ｈ−δ）である場合、ドメインは、時間ｔ０の条件に戻る。そうでない場合、処理容量はＣに留まり、その結果、状態遷移はトリガされない。
【０１０７】
この時点で、待ち行列長がＱｍａｘ＝Ｃ・（ｈ＋δ）よりさらに長くなることはない。Ｑ（ｔ２）＝Ｃ・ｈ＋ΔＢ、ΔＢ≧０であり、ｔ２の後にそれ以上のトラフィックが到着しない場合、バックログＱ（ｔ２）を処理するために最高で２つの完全動作間隔を利用する：第１の動作間隔は、バックログをＱ（ｔ３）＝ΔＢに削減し、第２の間隔は、バックログがｔ４＝ｔ３＋ｈまでに処理されることを保証する。ΔＢ＞０であるようにｔ４までに処理された最後のビットが到達する最早の時間は、ｔε＝ｔ２−δ＋ε、ε→０であり、その結果、ｄ＝ｔ４−ｔε＜２ｈ＋δである。
【０１０８】
定理１の証明における時間ｔ２のシナリオは、ｈおよびδの所与の値に関してより厳密な遅延限界を提供するバックログ処理特性の以下の公式をもたらす：
強バックログ処理特性。動作間隔の始まりｔ０において設定された処理容量が、動作間隔の最も近い可能な終点（ｔ１＝ｔ０＋ｈ）までに現在の待ち行列バックログＱ（ｔ０）＞０を処理するために十分であり、かつ現在の容量
【０１０９】
【数２１】
0005607177.tif 000022
よりも高い利用可能な容量のセットから選択される。
【０１１０】
そのような容量が利用可能でない場合、このポリシーは、速度整合ドメインの完全容量（ｒ（ｔ０）＝Ｃ）を選択する。
【０１１１】
強バックログ処理特性を保持する状態設定ポリシーは、強バックログ処理ポリシーと呼ばれる。
【０１１２】
以下の定理は、強バックログ処理ポリシーを備えた流体速度整合ドメインに関する遅延限界を画定する。
【０１１３】
定理２。強バックログ処理ポリシーを備えた流体速度整合ドメインでは、遅延制約ｄは、以下のように制限される：
ｄ≦ｄｍａｘ＝ｈ＋δ  （９）
証明。バックログＱ（ｔ２）＝Ｃ・ｈ＋ΔＢ、ΔＢ＞０が待ち行列内に蓄積されるときまでの定理１の証明と同じ事象のシーケンスを考慮する。弱バックログ処理ポリシーの事象とは対照的に、速度整合ドメインの処理容量は、待ち行列バックログが完全に処理されるまで、再度削減され得ない。結果として、ｒ（ｔ２）＝Ｃであり、追加バックログが待ち行列内で蓄積することは許可されない。最大待ち行列バックログは、Ｑｍａｘ＝Ｃ・（ｈ＋δ）に留まり、ｄｍａｘ＝ｈ＋δは、それが到着した後で、待ち行列内で最後のビットを転送するのにかかる最大時間である。
【０１１４】
以下の定理は、強バックログ処理ポリシーを備えたパケット化された速度整合ドメイン内の最大待ち行列長を画定する。
【０１１５】
定理３。強バックログ処理ポリシーを備えたパケット化された速度整合ドメインでは、待ち行列サイズＱ（ｔ１）は以下のように制限される：
【０１１６】
【数２２】
0005607177.tif 000023
式中、Ｌｍａｘは、速度整合ドメイン内のパケットの最大サイズであり、ｒｍｉｎは、利用可能な速度のセット内の最小非ヌル速度
【０１１７】
【数２３】
0005607177.tif 000024
である。
【０１１８】
証明。一般性を失わずに、ｔ０を、状態設定ポリシーがｒ（ｔ０）≧Ｑ（ｔ０）／（ｈ−δ）であるように処理容量ｒ（ｔ０）を選択する動作間隔の開始時間とする。時間ｔ１において、パケット化された速度整合ドメインが、パケット送信の終端（ｔ０＋ｈ≦ｔ１＜ｔ０＋ｈ＋Ｌｍａｘ／ｒ（ｔ０））において処理容量を設定する次の機会を有するとき、待ち行列バックログは、Ｑ（ｔ１）＝Ｑ（ｔ０）＋Ａ（ｔ０，ｔ１）−ｒ（ｔ０）・（ｔ１−ｔ０−δ）であり、Ａ（ｔ０，ｔ１）≦Ｃ・（ｔ１−ｔ０）である。したがって：
Ｑ（ｔ１）≦（Ｃ−ｒ（ｔ０））・（ｔ１−ｔ０）＋Ｑ（ｔ０）＋ｒ（ｔ０）・（ｈ−ｈ＋δ）
∴  Ｑ（ｔ１）≦（Ｃ−ｒ（ｔ０））・（ｈ＋Ｌｍａｘ／ｒ（ｔ０））＋ｒ（ｔ０）・ｈ
∴  Ｑ（ｔ１）≦Ｃ・ｈ＋Ｌｍａｘ・（Ｃ／ｒｍｉｎ−１）
Ｑ（ｔ１）＞Ｃ・（ｈ−δ）であるため、時間ｔ１において、状態設定ポリシーは、ｒ（ｔ１）＝Ｃを選択し、後続の状態遷移の間、速度整合ドメインは、最高でＣ・δまでより多くのビットを累積する。時間ｔ１＋δにおいて、Ｑ（ｔ１）≦Ｃ・ｈ＋Ｌｍａｘ・（Ｃ／ｒｍｉｎ−１）のとき、完全容量での動作は、待ち行列長がそれよりさらに延びるのを阻止することを開始する。
【０１１９】
定理２の証明で示されたように、強バックログ処理ポリシーを備えた速度整合ドメインでは、最大遅延は、完全容量において最大バックログを処理するために必要とされる時間である。定理３から、以下の結果が直ちに派生する。
【０１２０】
補助定理１。強バックログ処理ポリシーを備えたパケット化された速度整合ドメインでは、遅延制約ｄは、以下のように制限される。
【０１２１】
【数２４】
0005607177.tif 000025
速度整合ドメインの動作状態に関する選択基準の識別は、状態設定ポリシーの仕様を完成する。最大追加遅延
【０１２２】
【数２５】
0005607177.tif 000026
と最小ホールド時間ｈとの間の関係に関する補助定理１の結果を保持するために、選択基準は、強バックログ処理特性を満たさなければならない。
【０１２３】
やはりエネルギー消費を最小限に抑える最も単純な強バックログ処理ポリシーは、Ｑ（ｔ０）＞０のとき、容量
【０１２４】
【数２６】
0005607177.tif 000027
を選択し、任意の時点ｔｅにおいて、Ｑ（ｔｅ）＞０であるように、容量
【０１２５】
【数２７】
0005607177.tif 000028
を選択する（すなわち、現在の動作間隔の存続時間がｈマークを超えようと、超えなかろうと、待ち行列が空になるとすぐに、現在の処理容量のすぐ下の処理容量を選択する）バックログ処理ポリシーである。両方の状態設定事象において、このポリシーは、対応する条件を満たす容量を見出さない場合がある点に留意されたい。その場合、このポリシーは、状態遷移をトリガせずに、現在の容量を保持する。速度スケーリングをスリープ状態活用と結合させる速度整合方式において、利用可能な動作状態のセットＳは、関連する処理容量が最適しきい値容量ｒＴ，ｏｐｔよりも低くないように、基本的な速度スケーリング方式においてスリープ状態を状態のサブセットと合併することによって形成される点にも留意されたい。
【０１２６】
Ｓ＝｛ｓｓ｝∪｛ｓｋ∈Ｓ’：ｒｋ≧ｒＴ，ｏｐｔ｝であり、式中、Ｓ’は、基本的な速度スケーリング方式における動作状態のセットであり、ｒｓ＝０は、スリープ状態に関連する容量である。このポリシーは、待ち行列が空になったとき、凸状電力速度曲線に沿った広域振動を回避するために、単一ステップの容量減分だけを可能にするが、同じポリシーは、容量増分を引き起こす状態遷移に制限を課さない：時間ｔ０において、Ｑ（ｔ０）＞０であり、現在の動作間隔の開始以来、少なくともｈ時間が経過したために、新しい動作間隔が開始できるとき、このポリシーは、利用可能な容量の完全なサブセットから現在の処理容量よりもより低くない新しい処理容量を選択する。この状態設定ポリシーに関する名称は、単純な強バックログ処理（ＳＳＢＣ）ポリシーである。
【０１２７】
速度整合ドメインの遅延パフォーマンスを統計的に改善するために、トラフィック到着速度に関するプレディクタ（ｐｒｅｄｉｃｔｏｒ）
【０１２８】
【数２８】
0005607177.tif 000029
が状態設定ポリシー内に含まれてよい。最も単純なプレディクタは、次の間隔に関する到着速度推定として動作間隔の到着速度を使用する：
【０１２９】
【数２９】
0005607177.tif 000030
式中、ｔｎおよびｔｎ＋１は、第ｎ番目の動作間隔の開始時間および終了時間である。現在の待ち行列長と次の動作間隔に関する到着の推定との組合せは、速度整合ドメインの平均遅延パフォーマンスを改善するが、この組合せは、方程式（１１）の最悪の追加遅延を削減できない。これは、プレディクタが、いかに正確であっても、将来の到着に関して実際の制御を有さないことによる。以下では、時間ｔ０においてＱ（ｔ０）＞０であるような状態設定決定
【０１３０】
【数３０】
0005607177.tif 000031
に、および時間ｔｅにおいてＱ（ｔｅ）＝０であるような状態設定決定
【０１３１】
【数３１】
0005607177.tif 000032
に、最も単純なプレディクタを含めることの効果を記述する。この状態設定ポリシーに関する名称は、予測的強バックログ処理（ＰＳＢＣ）ポリシーである。
【０１３２】
現在の状態（待ち行列長Ｑ（ｔ））と将来の到着（
【０１３３】
【数３２】
0005607177.tif 000033
）の組合せに対して若干異なる手法が、先行技術［Ｎｅｄｅｖｓｃｈｉ］の速度スケーリング方法から導出される。続く動作間隔全体に関して予測される代わりに、将来の到着に関するプレディクタは、次の遷移を完了するために必要とされる時間だけに適用され、その結果、新しい処理容量は、ドメインがパケットの処理を再度開始できる時点において予測されるバックログに基づいて設定される。時間ｔ０において、Ｑ（ｔ０）＞０であるように、この部分的な予測強バックログ処理（ＰＰＳＢＣ）ポリシーは、以下のように、次の動作間隔に関して処理容量ｒ（ｔ０）を設定する。
【０１３４】
【数３３】
0005607177.tif 000034
時間ｔｅにおいて、Ｑ（ｔｅ）＝０であるように、ＰＰＳＢＣポリシーは、以下のように、次の動作間隔に関して処理容量ｒ（ｔｅ）を設定する。
【０１３５】
【数３４】
0005607177.tif 000035
この点に関する議論は、強バックログ処理特性を保持する状態設定ポリシーを網羅している。しかし、以下の節で提示される実験結果も、弱バックログ処理ポリシーおよび非バックログ処理ポリシーのパフォーマンスを明らかにする。
実験結果
先に（ＳＳＢＣ、ＰＳＢＣ、およびＰＰＳＢＣ）と定義された状態設定ポリシーを組み込む速度整合方式のエネルギー節約および遅延パフォーマンスは、それぞれが、最高で１Ｇｂｐｓまでのトラフィックを供給できる１０個の独立したパレートソースによって供給された１０Ｇｂｐｓ単一待ち行列速度整合ドメインのシミュレーションによって研究された。これらのソースは、１０００バイトのパケットを生成し、５０ミリ秒の平均バースト時間および平均アイドル時間を有する。パケットレベルのシミュレーション実験は、ｎｓ２シミュレーションプラットフォーム用に新しく設計された待ち行列サブクラスを使用して実行された。すべての実験において、５秒の準備時間の満了の後で１００秒のシステム時間の間、データが収集された。
【０１３６】
ドメインの電力速度曲線は、（ｆｔｐ：／／ｄｏｗｎｌｏａｄ．ｉｎｔｅｌ．ｃｏｍ／ｄｅｓｉｇｎ／ｎｅｔｗｏｒｋ／ｐａｐｅｒｓ／３０１１７４０１．ｐｄｆに見出され得る）２００４年３月  Ｗｈｉｔｅｐａｐｅｒ、「Ｅｎｈａｎｃｅｄ  Ｉｎｔｅｌ（Ｒ）  ＳｐｅｅｄＳｔｅｐ（Ｒ）Ｔｅｃｈｎｏｌｏｇｙ  ｆｏｒ  ｔｈｅ  Ｉｎｔｅｌ（Ｒ）  Ｐｅｎｔｉｕｍ（Ｒ）Ｍ  Ｐｒｏｃｅｓｓｏｒ」において文書化されたようなＩｎｔｅｌ（Ｒ）Ｐｅｎｔｉｍｕｎ（Ｒ）Ｍ  Ｐｒｏｃｅｓｓｏｒの６つの動作状態の補間および正規化によって導出された。
【０１３７】
【数３５】
0005607177.tif 000036
式中、ｒ０＝１．６２５Ｇｂｐｓ、Ｐ０＝０．２３２Ｗ、およびＡ＝０．００１３０８Ｗ・Ｇｂｐｓ−３である。表１の動作状態は、状態設定ポリシーに利用可能であることが仮定された。
【０１３８】
スリープ電力Ｐｓは、基礎アクティブ電力Ｐ０の一部（Ｐｓ＝γ・Ｐ０，０＜γ＜１）であり、アイドル電力は、アクティブ電力の一部
【０１３９】
【数３６】
0005607177.tif 000037
であることが仮定される。方程式（７）によれば、最適しきい値容量は、スリープ電力Ｐｓの関数であり、したがって、スリープ電力と基礎アクティブ電力との間の比率γの関数である。方程式（１２）の電力速度曲線の場合、比較的低い値の比率（γ＝０．１２５）は、ｒ（ｔＴ，ｏｐｔ）＝５．２１Ｇｂｐｓをもたらし、一方、比較的高い値（γ＝０．５）は、ｒ（ｔＴ，ｏｐｔ）＝４．５１Ｇｂｐｓをもたらす。これら２つの値同士の間の妥協点として、速度整合ドメイン内で利用可能な最小非ヌル容量は、５Ｇｂｐｓに設定された。
【０１４０】
Ｓ＝｛ｓｓ｝∪｛ｓｋ∈Ｓ’：ｒｋ≧５Ｇｂｐｓ｝＝｛ｓｓ，ｓ５，ｓ６，ｓ７，ｓ８，ｓ９，ｓ１０｝
遷移時間δは十分に既存の技術の能力内であるが、依然として、終端間アプリケーションのユーザ認識に影響を与える可能性がある遅延の原因であることを理解して、遷移時間δは１ミリ秒に設定される。スリープ状態活用を含まない速度スケーリング方式の評価の際、利用可能な最小非ヌル容量は、２Ｇｂｐｓに設定される（表１は、利用可能な動作状態のセット内にｓ１を含めることに、エネルギー利益が存在しないことを示す。）
【０１４１】
【表１】
0005607177.tif 000038
表１
【０１４２】
図１０を参照すると、完全処理容量におけるアクティブとアイドルのサブ状態だけを交互に行うドメインに関して、先に説明された３つの強バックログ処理ポリシー（ＳＳＢＣ、ＰＳＢＣ、およびＰＰＳＢＣ）によって、その弱バックログ処理対応物（ＳＷＢＣ、ＰＷＢＣ、およびＰＰＷＢＣ）によって、およびスリープ状態活用（ＳＳＥ）ドメイン（γ＝０．１２５）によって速度スケーリングの状況で達成されるエネルギー利得を理解されよう。完全性のために、比較の中にやはり含まれるのは、ポリシーは利用可能な速度セット内の単一ステップ増分だけを許容するため、いずれのバックログ処理特性も有効でない、先行技術［Ｎｅｄｅｖｓｃｈｉ］からの非バックログ処理（ＮＢＣ）ポリシーである。すべての事例において、アイドル電力とアクティブ電力との間の比率は、β＝０．８である。
【０１４３】
図１０は、以下の重要な表示を提供する。
【０１４４】
速度整合は、特に、負荷範囲の下部において、大きなエネルギー節約を達成するためのその機能を考慮すると、追求する価値が十分にある。
【０１４５】
負荷範囲の下部における速度スケーリングのスリープ状態活用の利点は、２つの手法を結合させる速度整合方式の仕様を正当化する。
【０１４６】
すべての強バックログ処理ポリシーは、その弱バックログ処理対応物よりもパフォーマンスが優れている。
【０１４７】
ＰＳＢＣポリシーは、ＳＳＢＣポリシーおよびＰＰＳＢＣポリシーよりも明らかにパフォーマンスが低く、トラフィック到着プレディクタの適用は、動作間隔の存続時間全体に拡張されるべきでないことを暗示する。
【０１４８】
ＳＳＢＣポリシーおよびＰＰＳＢＣポリシーのエネルギー節約パフォーマンスは、前から存在するＮＢＣポリシーのパフォーマンスと少なくとも同じくらい良好である。
【０１４９】
ＳＳＢＣポリシーとＰＰＳＢＣポリシーのどちらかを選択するために、その相対的な遅延パフォーマンスが、ＮＢＣポリシーの平均遅延および最大遅延もプロットする図１１に図示される。
【０１５０】
図１１は、ＳＳＢＣポリシーおよびＰＰＳＢＣポリシーは最大遅延を方程式（１１）の１１ミリ秒限界内に維持し、一方、ＮＢＣポリシーは（この実験では、多大ではないが）それに違反することを示す。ＰＰＳＢＣポリシーは、ＰＰＳＢＣ予測が推定される遷移時間δと最小ホールド時間ｈとの間の比率に関係する差だけ、平均遅延および最大遅延の両方に関してＳＳＢＣポリシーよりも常にパフォーマンスが優れている。説明を簡単にするために、この節の残りの部分では、現在利用可能な技術と整合する状態遷移推定に基づいて、すべての他のポリシーよりもパフォーマンスが優れているＰＰＳＢＣポリシーに関する結果だけが提示される。しかし、状態遷移技術が経時的に改善して、ますます短い遷移時間を提供するにつれて、遅延パフォーマンスの区別は、時として、無関係になり、最も単純なポリシー（ＳＳＢＣ）を実施するのにずば抜けて最も魅力的なものにする点を理解されたい。
【０１５１】
次に、速度スケーリングをスリープ状態活用と結合させる速度整合方式において利用可能にされる最良の最小容量を示す。図１２を参照すると、２Ｇｂｐｓ、５Ｇｂｐｓ、および７Ｇｂｐｓの最小容量を用いたＰＰＳＢＣ速度整合方式のエネルギー節約パフォーマンスを理解されよう。このプロットは、最適速度スケーリング方式（２Ｇｂｐｓ最小容量を用いたＰＰＳＢＣ状態設定ポリシー）およびスリープ状態活用（ＳＳＥ）方式も含む。
【０１５２】
図１２は、以下の点で、予測を裏付ける。
【０１５３】
最小非ヌル容量を設定するための方程式（７）の基準は最適であることが証明される。負荷範囲の下部において、ｒｍｉｎ＝５Ｇｂｐｓを用いたＰＰＳＢＣポリシーは、ｒｍｉｎ＝２Ｇｂｐｓおよびｒｍｉｎ＝７Ｇｂｐｓを用いた同じポリシーよりもより高いエネルギー節約をもたらす。
【０１５４】
速度整合方式は、負荷範囲の下部において基本的な速度スケーリング方式よりもパフォーマンスがかなり優れている。
【０１５５】
速度整合方式は、負荷範囲全体を通してスリープ状態活用方式よりもパフォーマンスが優れている。
【０１５６】
最後に、図１３を参照すると、ＰＰＳＢＣ速度整合方式（ＲＡ−ＰＰＳＢＣ）の遅延パフォーマンスと基本的な速度スケーリング方式（ＲＳ−ＰＰＳＢＣ）の遅延パフォーマンスとの間の比較を理解されよう。
【０１５７】
図１３の曲線は、ＰＰＳＢＣの２つのバージョンが５Ｇｂｐｓを上回る負荷に関して完全に重複することと、速度整合バージョンが負荷範囲全体を通して方程式（１１）の遅延限界に適合することとを示す。
【０１５８】
要約すると、パケットネットワークのエネルギー効率を改善するための速度整合方式は、結果として生じる２つの寄与に対処してきた。第１に、ネットワークデータパスの適切な抽象化により、実用的なネットワーク内で速度整合デバイスのインクリメンタルな導入に関する条件を作成することが可能であることが示されている。第２に、それらの方式が、当該方式が展開されているすべてのノードにおいてネットワークトラフィックに対して引き起こす可能性がある追加遅延に関して厳密な決定論的限界を実施する速度整合方式に関する状態設定ポリシーのクラスが定義されている。そのクラス内で、実用的なネットワーク装置内で速度整合を実施することが先行技術に存在する速度整合方法に勝って改善され得ることを示す、スリープ状態活用方式および速度スケーリング方式の最良の特性を効果的に結合させる状態設定ポリシーが開示されている。
【０１５９】
本発明は、それらの方法を実施するための方法および装置の形で実施され得る。本発明はまた、磁気記録媒体、光記録媒体、ソリッドステートメモリ、フロッピディスケット、ＣＤ−ＲＯＭ、ハードドライブ、または任意のその他の機械可読記憶媒体など、有形媒体の形で実施されるプログラムコードの形で実施されることも可能であり、プログラムコードがコンピュータなどの機械内にロードされて、その機械によって実行されるとき、その機械は、本発明を実施するための装置になる。本発明は、例えば、記憶媒体内に記憶されようと、または機械内にロードされようと、かつ／もしくは機械によって実行されようと、プログラムコードの形で実施されることも可能であり、プログラムコードがコンピュータなどの機械内にロードされて、その機械によって実行されるとき、その機械は本発明を実施するための装置になる。汎用プロセッサ上で実施されるとき、このプログラムコード区分は、特定の論理回路に類似して動作する独自のデバイスを提供するためにプロセッサと結合する。
【０１６０】
特許請求の範囲で表現される、本発明の性質を説明するために記述および例示されている部分の詳細、材料、および構成の様々な変更が本発明の範囲から逸脱せずに当業者によって行われ得る点をさらに理解されよう。
【０１６１】
本明細書で記載された例示的な方法のステップは、記述された順序で実行されることが必要とされるとは限らず、またそのような方法のステップの順序は、単なる例示であると理解されるべきである点を理解されたい。同様に、追加のステップがそのような方法内に含まれてよく、本発明の様々な実施形態と整合する方法において、いくつかのステップは、省略されてよく、または組み合わされてもよい。
【０１６２】
以下の方法クレームにおける要素は、もしあれば、対応するラベル付けにより特定の順序で列挙されるが、請求項の列挙がそれらの要素のうちのいくつかまたはすべてを実施するための別段の特定の順序を意味しない限り、それらの要素は、その特定の順序で実施されていることに限定されることが意図されるとは限らない。
【０１６３】
本明細書における、「一実施形態」または「ある実施形態」の言及は、実施形態に関して記述された特定の特徴、構造、または特性が本発明の少なくとも一実施形態の中に含まれ得ることを意味する。本明細書の様々な場所での「一実施形態では」という成句の出現は、すべてが同じ実施形態を指すとは限らず、また別個の実施形態もしくは代替の実施形態が他の実施形態と必ずしも相互に排他的であるとは限らない。「実施」という用語に関しても同様である。請求項で画定される、本発明の範囲から逸脱せずに、数多くの修正、改変、および適合が上で記述された本発明の実施形態に行われることが可能である。
【図１】
0005607177.tif 000039
【図２ａ】
0005607177.tif 000040
【図２ｂ】
0005607177.tif 000041
【図２ｃ】
0005607177.tif 000042
【図３ａ】
0005607177.tif 000043
【図３ｂ】
0005607177.tif 000044
【図４ａ】
0005607177.tif 000045
【図４ｂ】
0005607177.tif 000046
【図５】
0005607177.tif 000047
【図６】
0005607177.tif 000048
【図７】
0005607177.tif 000049
【図８】
0005607177.tif 000050
【図９】
0005607177.tif 000051
【図１０】
0005607177.tif 000052
【図１１】
0005607177.tif 000053
【図１２】
0005607177.tif 000054
【図１３】
0005607177.tif 000055