(57)【要約】複数のネットワーク・デバイスを備えるネットワークが、エネルギー効率のためのスケジューリングを実施するように構成される。一態様において、ネットワーク内の系列において互いに接続されたネットワーク・デバイスのセットが識別され、さらに共通のフレーム・サイズが確立される。その系列のネットワーク・デバイスのそれぞれに関して、そのネットワーク・デバイスに関する活性期間および不活性期間が、共通のフレーム・サイズを有する対応するフレーム内でスケジュールされ、その系列のそれぞれのネットワーク・デバイスにおけるそれらのフレームは、指定されたオフセットだけ互いに時間的にずらされる。系列のネットワーク・デバイスの各デバイスの活性期間の１つまたは複数のそれぞれに関して、受信されたパケットが、そのネットワーク・デバイスにおいて処理されるようにスケジュールされる。
2013523012.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク内の系列において互いに接続されたネットワーク・デバイスのセットを識別するステップと、
前記系列の各ネットワーク・デバイスにおける活性期間および不活性期間をスケジュールするための共通のフレーム・サイズを確立するステップと、
前記系列の前記ネットワーク・デバイスのそれぞれに関して、そのネットワーク・デバイスに関する活性期間および不活性期間を、前記共通のフレーム・サイズを有する対応するフレーム内でスケジュールし、前記系列の前記それぞれのネットワーク・デバイスにおける前記フレームは、指定されたオフセットだけ互いに時間的にずらされるステップと、
前記系列の前記ネットワーク・デバイスの各デバイスの前記活性期間の１つまたは複数のそれぞれに関して、受信されたパケットを、そのネットワーク・デバイスにおいて処理されるようにスケジュールするステップとを備える方法。
【請求項２】
前記受信されたパケットを、処理されるように前記スケジュールするステップは、前記受信されたパケットを、行き先の遠い順にスケジュールして、前記活性期間内に、前記ネットワークにおいて、より長い距離を伝送されるパケットが、前記ネットワークにおいて、より短い距離を伝送されるパケットより優先されるようにするステップを備える請求項１に記載の方法。
【請求項３】
前記識別するステップは、前記ネットワークを、系列において互いに接続されたネットワーク・デバイスの対応するセットをそれぞれが備える複数の系列に区分するステップを備え、さらに、前記パケットのうちの所与の１つは、前記系列の第１の系列から前記系列の第２の系列に切り換わり、さらにその系列切換えに関連して、前記第２の系列の第１のネットワーク・デバイスにおいて、前記第１のネットワーク・デバイスにおけるフレームの第１の活性期間を待つ請求項１に記載の方法。
【請求項４】
前記系列の前記ネットワーク・デバイスの第１のデバイスが、前記系列の前記ネットワーク・デバイスの第２のデバイスにメッセージを送信するステップをさらに備え、前記メッセージは、前記第１のネットワーク・デバイスのフレームと前記第２のネットワーク・デバイスのフレームの間の前記オフセットのうちの特定の１つを指定する請求項１に記載の方法。
【請求項５】
前記特定のオフセットは、前記第１のネットワーク・デバイスにおけるフレームの第１の活性期間の始まりと前記第２のネットワーク・デバイスにおけるフレームの第１の活性期間の始まりの間の時間的離隔を表す請求項４に記載の方法。
【請求項６】
前記系列の最後のネットワーク・デバイス以外の前記系列の前記ネットワーク・デバイスの各デバイスは、前記系列の下流の直近の隣接するネットワーク・デバイスに、前記送信側のネットワーク・デバイスの最初の活性期間と前記隣接するネットワーク・デバイスの最初の活性期間の間のオフセットを指定するメッセージを送信する請求項４に記載の方法。
【請求項７】
処理デバイスのプロセッサによって実行されると、前記デバイスに、請求項１に記載の方法のステップを実行させる実行可能なプログラム・コードを実体化しているコンピュータ可読記憶媒体を備える製造品。
【請求項８】
メモリに結合されたプロセッサを備える第１のネットワーク・デバイス
を備える装置であって、
前記第１のネットワーク・デバイスは、ネットワーク内の系列において他のネットワーク・デバイスと互いに接続されるように構成され、前記系列の前記ネットワーク・デバイスのそれぞれにおける活性期間および不活性期間をスケジュールするための共通のフレーム・サイズが確立され、
前記第１のネットワーク・デバイスは、前記共通のフレーム・サイズを有するフレームの活性期間および不活性期間をスケジュールするように動作し、さらに前記活性期間の１つまたは複数のそれぞれに関して、パケットを、前記活性期間内に処理されるようにスケジュールするように動作し、
前記第１のネットワーク・デバイスにおける前記フレームは、前記系列の前記ネットワーク・デバイスの別のネットワーク・デバイスにおける対応するフレームに対して時間的にずらされる装置。
【請求項９】
ネットワーク内の系列において互いに接続されるように構成され、さらに各ネットワーク・デバイスにおける活性期間および不活性期間をスケジュールするための共通のフレーム・サイズを有する複数のネットワーク・デバイスのうちの所与のネットワーク・デバイスにおいて使用するための方法であって、
前記所与のネットワーク・デバイスに関して前記共通のフレーム・サイズを有するフレームの活性期間および不活性期間をスケジュールするステップと、
前記所与のネットワーク・デバイスの前記活性期間の１つまたは複数のそれぞれに関して、パケットを、前記活性期間内に前記所与のネットワーク・デバイスにおいて処理されるようにスケジュールするステップとを備え、
前記所与のネットワーク・デバイスにおける前記フレームは、前記系列の前記ネットワーク・デバイスの別のネットワーク・デバイスにおける対応するフレームに対して、指定されたオフセットだけ時間的にずらされる方法。
【請求項１０】
系列において互いに接続されたネットワーク・デバイスのセットを含む複数のネットワーク・デバイス
を備える通信ネットワークであって、
前記系列の前記ネットワーク・デバイスのそれぞれに関して共通のフレーム・サイズが確立され、
前記系列の前記ネットワーク・デバイスのそれぞれは、フレームの活性期間および不活性期間をスケジュールするように動作し、さらに前記活性期間の１つまたは複数のそれぞれに関して、パケットを、前記活性期間内に処理されるようにスケジュールするように動作し、さらに
前記系列の前記それぞれのネットワーク・デバイスにおける前記フレームは、指定されたオフセットだけ互いに時間的にずらされる通信ネットワーク。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、通信ネットワークに関し、より詳細には、パケットを、そのようなネットワークのネットワーク・デバイスにおいて処理されるようにスケジュールするための技術に関する。
【背景技術】
【０００２】
米国の遠隔通信インフラストラクチャは、１年当たり６００億キロワット時の電力を消費するものと推定される。そのような巨大な消費量は、部分的には、ほとんどのネットワークがピーク・トラフィックを扱うように設計されていることからもたらされる。ルータやスイッチなどのネットワーク・デバイスは、最大速度で動作して、最大限の電力を消費する傾向がある一方で、通常のトラフィック・レベルは、最大限のスループットの小さい割合でしかない。
【０００３】
ネットワークにおけるエネルギー消費を低減する１つの知られているアプローチは、特定のネットワーク・デバイスの電源をときどき切ることを含む。例えば、これらのネットワーク・デバイスは、ネットワーク・デバイスの電力消費が、スリープ・モード、オフ状態、またはネットワーク・デバイスの最大限の電力消費と比べて、相当に低減される他のタイプの不活性状態に入れられることが可能である。しかし、そのようなダウンタイム中、処理のためにネットワーク・デバイスに着信するいずれのパケットも、バッファリングされなければならず、さらに、このことが、ネットワークにおけるパケットのトランスポートに相当な遅延をもたらし得る。このため、ネットワーク・デバイスがネットワーク・デバイスのそれぞれの活性状態にある期間を最小限に抑えることと、ネットワークにおけるパケット伝送の遅延を最小限に抑えることは、対立する２つの目標となる。この問題は、所与のネットワーク・デバイスをネットワーク・デバイスの活性状態と不活性状態の間で切り換えることにかかわる相当な遷移時間が存在することによって悪化する。
【０００４】
ネットワーク・デバイスの活性状態と不活性状態の間のネットワーク・デバイスの遷移に関連する費用に対処するために、同一の送信元と、同一の宛先とを有するネットワーク・グループ・パケットのエッジ・ルータが、送信の回数を減らし、ネットワーク・デバイスの不活性の時間を増加させるために、それらのパケットをバーストで送信することが提案されている。Ｓ．Ｎｅｄｅｖｓｃｈｉ他、「Ｒｅｄｕｃｉｎｇ  Ｎｅｔｗｏｒｋ  Ｅｎｅｒｇｙ  Ｃｏｎｓｕｍｐｔｉｏｎ  ｖｉａ  Ｓｌｅｅｐｉｎｇ  ａｎｄ  Ｒａｔｅ−Ａｄａｐｔａｔｉｏｎ」、Ｊ．ＣｒｏｗｃｒｏｆｔおよびＭ．Ｄａｈｌｉｎ編、ＮＳＤＩ、３２３〜３３６頁、ＵＳＥＮＩＸ  Ａｓｓｏｃｉａｔｉｏｎ、２００８年を参照されたい。しかし、そのようなアプローチは、依然として、ネットワークにおけるパケット伝送に関する相当な遅延につながる可能性があり、エネルギー消費最小化と遅延最小化の両方に同時に対処する包括的な最適化をもたらすことができない。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Ｓ．Ｎｅｄｅｖｓｃｈｉ他、「Ｒｅｄｕｃｉｎｇ  Ｎｅｔｗｏｒｋ  Ｅｎｅｒｇｙ  Ｃｏｎｓｕｍｐｔｉｏｎ  ｖｉａ  Ｓｌｅｅｐｉｎｇ  ａｎｄ  Ｒａｔｅ−Ａｄａｐｔａｔｉｏｎ」、Ｊ．ＣｒｏｗｃｒｏｆｔおよびＭ．Ｄａｈｌｉｎ編、ＮＳＤＩ、３２３〜３３６頁、ＵＳＥＮＩＸ  Ａｓｓｏｃｉａｔｉｏｎ、２００８年
【非特許文献２】Ｂ．ＡｗｅｒｂｕｃｈおよびＹ．Ａｚａｒ、「Ｂｕｙ−ａｔ−ｂｕｌｋ  ｎｅｔｗｏｒｋ  ｄｅｓｉｇｎ」、Ｐｒｏｃ．ＩＥＥＥ  ＦＯＣＳ、１９９７年
【非特許文献３】Ｙ．Ｂａｒｔａｌ、「Ｏｎ  ａｐｐｒｏｘｉｍａｔｉｎｇ  ａｒｂｉｔｒａｒｙ  ｍｅｔｒｉｃｓ  ｂｙ  ｔｒｅｅ  ｍｅｔｒｉｃｓ」、Ｐｒｏｃ．ＡＣＭ  ＳＴＯＣ、１９９８年
【非特許文献４】Ｊ．Ｍａｔｏｕｓｅｋ、「Ｏｎ  ｅｍｂｅｄｄｉｎｇ  ｔｒｅｅｓ  ｉｎｔｏ  ｕｎｉｆｏｒｍｌｙ  ｃｏｎｖｅｘ  ｂａｎａｃｈ  ｓｐａｃｅｓ」、Ｉｓｒａｅｌ  Ｊｏｕｒｎａｌ  ｏｆ  Ｍａｔｈｅｍａｔｉｃｓ、１１４：２２１〜２３７頁、１９９９年
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明の例示的な実施形態は、所与の通信ネットワークのエネルギー効率を大幅に向上させる一方で、パケット遅延を最小限に抑えることもするスケジューリング技術を提供する。
【課題を解決するための手段】
【０００７】
本発明の一態様において、複数のネットワーク・デバイスを備える通信ネットワークが、エネルギー効率のためのスケジューリングを実施するように構成される。より詳細には、ネットワーク内の系列において互いに接続されたネットワーク・デバイスのセットが識別され、さらに共通のフレーム・サイズが確立される。その系列のネットワーク・デバイスのそれぞれに関して、そのネットワーク・デバイスに関する活性期間および不活性期間が、共通のフレーム・サイズを有する対応するフレーム内でスケジュールされ、その系列のそれぞれのネットワーク・デバイスにおけるそれらのフレームは、指定されたオフセットだけ互いに時間的にずらされる。系列のネットワーク・デバイスの各デバイスの活性期間の１つまたは複数のそれぞれに関して、受信されたパケットが、そのネットワーク・デバイスにおいて処理されるようにスケジュールされる。
【０００８】
例示的な実施形態の１つにおいて、受信されたパケットを、ネットワーク・デバイスの活性期間内に処理されるようにスケジュールすることは、行き先の遠い順に実行されることが可能であり、それによって活性期間内に、ネットワークにおいて、より長い距離を伝送されるパケットが、ネットワークにおいて、より短い距離を伝送されるパケットより優先される。
【０００９】
本発明の別の態様において、系列のネットワーク・デバイスの第１のネットワーク・デバイスが、系列のネットワーク・デバイスの第２のネットワーク・デバイスにメッセージを送信することが可能であり、このメッセージは、第１のネットワーク・デバイスのフレームと第２のネットワーク・デバイスのフレームの間のオフセットのうちの特定の１つを指定する。この特定のオフセットは、例えば、第１のネットワーク・デバイスにおけるフレームの第１の活性期間の始まりと第２のネットワーク・デバイスにおけるフレームの第１の活性期間の始まりの間の時間的離隔を表すことが可能である。より一般的には、系列の最後のネットワーク・デバイス以外の系列のネットワーク・デバイスの各デバイスが、系列の下流の直近の隣接するネットワーク・デバイスに、その送信側のネットワーク・デバイスの最初の活性期間とその隣接するネットワーク・デバイスの最初の活性期間の間のオフセットを指定するメッセージを送信することが可能である。
【００１０】
開示される技術は、ネットワーク内の複数の系列に適用され得る。例えば、ネットワークが、系列において互いに接続されたネットワーク・デバイスの対応するセットをそれぞれが備える複数の系列に区分されることが可能である。パケットのうちの所与の１つが、それらの系列の第１の系列からそれらの系列の第２の系列に切り換わることが可能であり、その系列切換えに関連して、パケットが、第２の系列の第１のネットワーク・デバイスにおいて、第１のネットワーク・デバイスにおけるフレームの第１の活性期間を待つことが可能である。
【００１１】
例示的な実施形態は、ネットワークの特定のノードに関する活性期間および不活性期間を、パケット遅延に対する活性期間と不活性期間の間の遷移の影響を最小限に抑える調整された仕方でスケジュールすることによって、通信ネットワークのエネルギー効率を向上させる。
【００１２】
本発明のこれら、およびその他の特徴および利点は、添付の図面、および以下の詳細な説明から、より明白となろう。
【図面の簡単な説明】
【００１３】
【図１】本発明の例示的な実施形態における通信ネットワークを示す図である。
【図２】図１のネットワークの特定のネットワーク・デバイスをより詳細に示す図である。
【図３】図１のネットワークにおいて実施されるスケジューリング・プロセスの動作を示す流れ図である。
【図４】ネットワークの一部分の例示的な系列分解を示す図である。
【図５】図４のネットワーク部分におけるネットワーク・デバイスのうちのいくつかの間の可能なルートを示す図である。
【図６】図１のネットワークのネットワーク・デバイスのうちの所与の１つのネットワーク・デバイス内の例示的なスケジューラの動作を示す図である。
【図７】図１のネットワークにおけるそのようなデバイスの系列の上のネットワーク・デバイス間の対話を示す図である。
【発明を実施するための形態】
【００１４】
本発明は、通信ネットワーク、ネットワーク・デバイス、および関連するスケジューリング・プロセスの例示的な実施形態に関連して説明される。しかし、本発明は、説明される特定のネットワーク、デバイス、およびプロセスで使用されることに限定されず、ネットワーク・デバイスの活性期間および不活性期間の調整されたスケジューリングによって、より高いエネルギー効率をもたらすことが望ましい任意のネットワーク・アプリケーションに、より一般的に適用可能であることを理解されたい。
【００１５】
図１は、複数の互いに接続されたネットワーク・デバイス１０２を備える通信ネットワーク１００を示す。ネットワーク・デバイス１０２は、例が、本明細書でネットワーク・ノードまたは端末装置とも呼ばれ得る、ルータ、スイッチ、サーバ、コンピュータ、または他の処理デバイスを任意の組合せで備えることが可能である。所与のネットワーク・デバイスは、一般に、プロセッサ、およびそのプロセッサに結合されたメモリ、ならびにネットワーク・デバイスが、ネットワーク・デバイスが互いに接続されているその他のネットワーク・デバイスと通信することを可能にするトランシーバを備える。ネットワーク・デバイス１０２の少なくともサブセットが、図示されるとおり、コントローラ１０４に結合される。
【００１６】
後段でより詳細に説明されるとおり、ネットワーク１００は、所与の通信ネットワークのエネルギー効率を大幅に向上させる一方で、パケット遅延を最小限に抑えることもする調整されたスケジューリング・プロセスを実施するように構成される。これらの実施形態におけるスケジューリング・プロセスは、図２から図７に示されるとおり、ネットワーク・デバイス内のスケジューラ、および他の要素を使用して、分散された仕方で実施され得る。そのような実施形態におけるコントローラ１０４は、それらのネットワーク要素間でオフセット、または他のスケジューリング情報を通信することを円滑にするのに利用されることが可能であり、またはスケジューリング・プロセスに関連するいくつかの計算、または他の動作を実行することが可能である。代替として、スケジューリング・プロセスは、コントローラが、スケジューリング動作の実質的にすべてを実行し、さらに適切なスケジュールをネットワーク・デバイスのそれぞれに伝えて、集中化された仕方で実施されてもよい。さらに別の例として、コントローラ１０４が完全に除かれて、スケジューリング・プロセスが、集中化された制御なしに、完全に分散された仕方で実施されてもよい。したがって、本発明の実施形態は、完全に分散されても、完全に集中化されても、分散制御と集中制御の混成を利用してもよい。
【００１７】
ネットワーク１００は、データまたは他の信号をトランスポートするのに適した任意のタイプの通信ネットワークを備えることが可能であり、さらに本発明は、この点で限定されない。例えば、ネットワーク１００のいくつかの部分が、インターネットなどのワイド・エリア・ネットワーク、メトロポリタン・エリア・ネットワーク、ローカル・エリア・ネットワーク、ケーブル・ネットワーク、電話ネットワーク、衛星ネットワーク、ならびにこれら、または他のネットワークのいくつかの部分または組合せを備えることが可能である。したがって、本明細書で使用される「ネットワーク」という用語は、広く解釈されることが意図される。
【００１８】
次に図２を参照すると、ネットワーク１００の所与のネットワーク・デバイス１０２の１つの可能な実施形態が示されている。この実施形態において、ネットワーク・デバイスは、メモリ２０２に結合されたプロセッサ２００を備え、ネットワーク・インターフェース回路２０４をさらに備える。やはりネットワーク・デバイス内に含まれるのが、スケジューラ２１０および系列分解モジュール２１２である。メモリ２０２は、ネットワーク・デバイスによって送信されるべき、またはそれ以外で処理されるべき、受信されたパケットを格納するためのバッファ２１５を備える。本明細書で使用される「パケット」という用語は、広く、したがって、例えば、多種多様な異なるタイプのプロトコル・データ単位を包含するように解釈されることを意図していることに留意されたい。
【００１９】
プロセッサ２００は、マイクロプロセッサとして、マイクロコントローラとして、ＡＳＩＣ（特定用途向け集積回路）もしくは他のタイプの処理デバイスとしても、そのようなデバイスのいくつかの部分もしくは組合せとしても実施され得る。メモリ２０２は、ＲＡＭ（ランダム・アクセス・メモリ）、ＲＯＭ（読み取り専用メモリ）、ディスク・ベースのメモリ、または他のタイプのストレージ・デバイス、ならびにそのようなデバイスのいくつかの部分もしくは組合せを備えることが可能である。プロセッサおよびメモリは、ネットワーク・デバイスの活性期間および不活性期間をスケジュールするための１つまたは複数のソフトウェア・プログラム、ならびにネットワークをネットワーク・デバイスの１つまたは複数の系列に分解することに関連するソフトウェア・プログラムを格納する際、および実行する際に使用され得る。したがって、モジュール２１０および２１２は、少なくとも部分的に、そのようなソフトウェア・プログラムを使用して実施されることが可能である。メモリ２０２は、実行可能なプログラム・コードを実体化している、本明細書でより一般的にコンピュータ・プログラム製品、またはさらにより一般的には、コンピュータ可読記憶媒体と呼ばれるものの例と見なされ得る。コンピュータ可読記憶媒体の他の例には、ディスク、または他のタイプの磁気媒体もしくは光媒体が任意の組合せで含まれ得る。
【００２０】
プロセッサ２００、メモリ２０２、およびインターフェース回路２０４は、本明細書で説明される仕方で動作するように適切に変更された、よく知られた従来の回路を備えることが可能である。そのような回路の従来の態様は、当業者にはよく知られており、したがって、本明細書で詳細に説明することはしない。
【００２１】
本明細書で開示されるネットワーク・デバイスは、図２の例示的な構成で具体的に示される以外の構成要素およびモジュールを使用して実施されてもよいことを認識されたい。
【００２２】
次に、例示的な実施形態におけるネットワーク・デバイス１０２の動作を、図３から図７を参照して説明する。
【００２３】
図３は、本発明の一実施形態における図１のネットワーク１００において実施されるスケジューリング・プロセスの流れ図である。この実施形態におけるスケジューリング・プロセスは、一般に、ネットワークをネットワーク・デバイスの複数の系列に区分し、各系列の上のネットワーク・デバイスのそれぞれのネットワーク・デバイスにおけるフレーム内で活性期間および不活性期間をスケジュールし、さらに各活性期間内で処理するようにパケットをスケジュールする。このプロセスは、図示されるとおり、ステップ３００から３０６を含む。
【００２４】
ステップ３００で、ネットワーク１００の少なくとも一部分が、系列において互いに接続されたネットワーク・デバイス１０２のセットに区分される。この区分は、ネットワーク・デバイス１０２の系列分解モジュール２１２を使用して実行される。ステップ３００でネットワークを区分するのに使用され得る１つのタイプの系列分解の例が、図４および図５に示される。このことは、或る種の最大フロー分解と見なされることが可能であり、さらに一般的なトポロジのネットワークに適している。
【００２５】
図４は、ノード１、２、３、４、および５として識別されるネットワーク・デバイス１０２の特定のデバイスを有する、ネットワーク１００の一部分を示す。ネットワークのこの部分は、最大フロー分解を使用して、ノード１、２、３、および４を備える第１の系列４００と、ノード２、５、および３を備える第２の系列４０２とに例示的に区分される。このことは、一般に、これらのノードのそれぞれにおいて、最大のスループット・トラフィック・フローを伝送する特定の入力リンクおよび出力リンクを特定して、それらのリンクを同一の系列上にあるものと宣言することを含む。より具体的には、ネットワークをいくつかの系列に区分するのに、各ノードにおいて、最大のスループット・トラフィック・フローを有する２つのリンクをマッチングし、それらの２つのリンクを同一の系列に割り当て、さらにこのプロセスを、各ノードに伴うすべてのリンクがマッチングされるまで繰り返す。この分解プロセスの結果、円環が生じた場合、その円環は、系列をもたらすように任意のポイントで切断され得る。
【００２６】
例として、ノード２を通過するトラフィックが、図５のそれぞれ参照符号５００、５０２、および５０４によって識別される１−２−３、１−２−５、または３−２−５という方向をたどり得るものと想定されたい。ノード２における系列分解モジュール２１２が、これらの方向のうちいずれが所与の系列内に留まるかを特定する。図４に示される例において、１−２−３が、１−２−５または３−２−５より多くのトラフィックを伝送するものと想定されたい。したがって、ノード１、２、および３がすべて系列４００上にあり、１−２−３に関するトラフィックが同一の系列上に留まるようになる。１−２−５または３−２−５に関するトラフィックは、ノード２において系列４００から系列４０２に切り換わらなければならない。より大きいトラフィックのリンクを同一の系列上に保つことによって、系列を切り換えなければならないパケットの数が最小限に抑えられる。このことは、各パケットが、新たな系列のスケジュールに追いつくために待たなければならない可能性があるので、１つの系列から別の系列への切換えごとにパケット処理の遅延が潜在的にもたらされ得るため、重要である。しかし、パケットが、一般に、所与の系列の各ネットワーク・デバイスにおける活性期間を待たなければならないのではなく、代わりに、系列を切り換える際に待つだけでよいことが、本明細書で開示される活性期間および不活性期間の調整されたスケジューリングの特別の利点である。
【００２７】
ステップ３００は、いずれの特定の分解プロセスの使用も要求しないことに留意されたい。本発明の別の実施形態は、いわゆる「キャタピラ」分解を利用して、ツリー構造を有するネットワークをネットワーク・デバイスの系列に区分し、この実施形態は、後段でより詳細に説明される。このため、図３のスケジューリング・プロセスは、ネットワーク・デバイスの任意の系列または複数の系列に、それらの系列が決定される特定の仕方にかかわらず、適用され得る。しかし、系列の間でパケットを切り換えることを最小限に抑える傾向にある分解を使用することが好ましい。
【００２８】
ネットワーク・デバイスの系列が特定された後、図３のスケジューリング・プロセスは、ステップ３０２に進む。このステップで、ネットワーク・デバイスの系列のそれぞれに関して、その系列の各ネットワーク・デバイスに関する活性期間および不活性期間をスケジュールする際に利用されるべき共通のフレーム・サイズが確立される。例示的な実施形態における共通のフレーム・サイズは、説明されるとおり、指定されたフレーム長Ｔによって与えられ、ただし、他のタイプの共通のフレーム・サイズが使用されてもよい。ステップ３０４で、各系列のネットワーク・デバイスのそれぞれに関して、そのネットワーク・デバイスに関する活性期間および不活性期間が、共通のフレーム・サイズを有する対応するフレーム内でスケジュールされ、系列のそれぞれのネットワーク・デバイスにおけるそれらのフレームは、指定されたオフセットだけ互いに時間的にずらされる。
【００２９】
例として、ネットワーク・デバイスの所与の系列に関する活性期間および不活性期間をスケジュールすることは、以下の仕方で進められることが可能である。ネットワーク・デバイスの系列が、少なくともノード１、２、３、および４を備える、図４の系列４００であるものと想定されたい。Ｔが共通のフレーム・サイズを表し、したがって、系列の各ノードにおける活性期間および不活性期間のスケジュールが、Ｔ単位時間ごとに繰り返すものとする。各ノードの活性期間がｒＴに等しいものとし、ただし、ｒは、ノードにパケットが着信するレートであり、ノードは、その他の場合は、不活性である。このことは、原則として、各ノードにおいて、すべてのパケットを処理するのに十分な活性時間が存在することを意味する。以上の想定の下で、この例に関する１つの可能なスケジュールは、以下のとおりである。すなわち、ノード１が、期間［０，ｒＴ］において活性であり、ノード２が、期間［ｐ１，ｐ１＋ｒＴ］において活性であり、ただし、ｐ１は、パケットがノード１からノード２まで進む伝送時間であり、ノード３が、期間［ｐ１＋ｐ２，ｐ１＋ｐ２＋ｒＴ］において活性であり、ただし、ｐ２は、パケットがノード２からノード３まで進む伝送時間であり、系列のその他のノードに関して以下同様である。このようにして、パケットは、系列における１つのノードによって処理された後、系列の次のノードによって処理されるのに間に合うように着信する。この単純な例は、所与の系列のネットワーク・デバイスにおける活性期間および不活性期間をスケジュールすることの１つの可能な例示に過ぎないことが認識されよう。他の例が、図６および図７に関連して後段で説明される。活性期間および不活性期間をスケジュールすることは、区分するステップ３００において特定されたネットワーク・デバイスのその他の系列のそれぞれに関して繰り返される。
【００３０】
ステップ３０６で、各系列の各ネットワークの各活性期間に関して、バッファリングされたパケットが、その活性期間内に処理されるようにスケジュールされる。この実施形態において、それらのパケットは、各活性期間内でＦＴＧ（行き先の遠い順）にスケジュールされて、最も長い距離を伝送されるパケットが、その活性期間内で優先される。つまり、ネットワークにおいてスケジュールするノードから、より長い距離を伝送されるパケットが、ネットワークにおいてスケジュールするノードから、より短い距離を伝送されるパケットより前に処理されるようにスケジュールされる。したがって、活性期間中、バッファリングされたパケットは、パケットの宛先から最も遠く離れたパケットが優先されるように処理される。
【００３１】
図３の実施形態は、ＦＴＧアプローチを使用して、ネットワーク・デバイスの所与の活性期間内に処理されるようにパケットをスケジュールするものの、他の実施形態は、活性期間に関して他のタイプの「ベストエフォート」スケジューリング、または、場合により、異なるノードにおける、異なるスケジューリング技術の組合せを使用することが可能である。
【００３２】
所与の系列の各ノードに関する活性期間および不活性期間の適切なスケジューリングを用いて、パケットは、そのパケットの最初のノードの活性期間に関して１回だけしか待たないことが示され得る。パケットは、移動を始めると、宛先に到達するまで動き続ける。パケットは、パケットが１つの系列から別の系列に切り換わる際、活性期間を再び待たなければならない可能性があるものの、累積する遅延は、通過するノードの数によってではなく、切り換えられる系列の数によって決る。通過するノードの数は、通常、切り換えられる系列の数よりはるかに多い。
【００３３】
図６は、図１のネットワークのネットワーク・デバイス１０２のうちの所与の１つのネットワーク・デバイス内の例示的なスケジューラ２１０の動作を示す。この実施形態におけるスケジューラ２１０は、系列分解モジュール２１２およびバッファ２１５に結合される。系列分解モジュール２１２は、隣接するネットワーク・デバイスのいずれが所与のネットワーク・デバイスと同一の系列上にあるかを特定する。バッファ２１５は、ネットワーク・デバイスにおいて受信されたパケット６００を格納する。スケジューラ２１０は、繰り返されるフレーム内でネットワーク・デバイスの活性期間および不活性期間を制御し、さらに各活性期間内でパケットに優先順位を付けることも行う。活性期間および不活性期間は、本明細書で「オン」期間および「オフ」期間とも呼ばれ、ただし、ネットワーク・デバイスは、これらの期間中、完全にオン、または完全にオフである必要はない。例えば、図に示されるとおり、フレームのオフ期間は、比較的低い処理レベルＬ１に対応する。このフレーム内のオン期間のそれぞれは、比較的高い、異なる処理レベルを有する。例えば、フレームの第１のオン期間６０２が、処理レベルＬ２に関連する一方で、第２のオン期間６０４、および第３のオン期間６０６が、第１のオン期間の処理レベルＬ２と比べて、それぞれ、わずかに低い処理レベル、およびわずかに高い処理レベルを有する。このため、特定の系列のネットワーク・デバイスのうちの所与の１つのネットワーク・デバイスの活性期間の２つ以上がそれぞれ、対応するフレーム内の異なる処理レベルに対応することが可能である。活性期間６０２、６０４、および６０６の各期間内で、図３のステップ３０６で示されるとおり、スケジューラ２１０が、パケットのそれぞれの宛先まで伝送される距離が最も長いパケットの処理を優先させる。
【００３４】
図７は、系列７００の一部であるセットのネットワーク・デバイス１０２−１、１０２−２、および１０２−３の間の対話を示す。これらのデバイスは、デバイス１、デバイス２、およびデバイス３としても表され、図４の例におけるノード１、２、および３のそれぞれのノードに対応するものと見なされ得る。デバイスのそれぞれは、一般に、図６に示されるように構成され、したがって、スケジューラ２１０−１、２１０−２、または２１０−３、およびバッファ２１５−１、２１５−２、または２１５−３を含む。系列分解モジュールは、例示を簡明にするために図から省略されている。図３のステップ３０４に示されるとおり、系列のネットワーク・デバイスのそれぞれが、そのネットワーク・デバイスの活性期間および不活性期間を、共通のフレーム・サイズを有する対応するフレーム内にスケジュールし、その系列のそれぞれのネットワーク・デバイスにおけるそれらのフレームは、指定されたオフセットだけ互いに時間的にずらされる。この実施形態において、スケジューラ２１０−１、２１０−２、および２１０−３が、それぞれが同一のフレーム長を有するそれぞれのフレーム７０２−１、７０２−２、および７０２−３の中でスケジューラ２１０−１、２１０−２、および２１０−３のそれぞれのネットワーク・デバイスの活性期間および不活性期間をスケジュールする。フレーム７０２−１、７０２−２、および７０２−３は、フレーム７０２−１、７０２−２、および７０２−３のそれぞれの初期オン期間フレーム７０４−１、７０４−２、および７０４−３が時間的に互い違いに配置されているという点で、互いにオフセットされていることを見て取ることができる。より具体的には、デバイス１におけるオン期間７０４−１の始まりとデバイス２におけるオン期間７０４−２の始まりの間に指定されたオフセット７１０が存在する。同様に、デバイス２におけるオン期間７０４−２の始まりとデバイス３におけるオン期間７０４−３の始まりの間に指定されたオフセット７１２が存在する。図に示されない系列７００のさらなるネットワーク・デバイスについて、同様に、それらのデバイスのそれぞれのフレームが互いに時間的にずらされていることが可能である。
【００３５】
図７の実施形態におけるネットワーク・デバイス１０２は、この図のデバイスを通過する曲線によって示されるとおり、オフセット、および、場合により、他の情報を指定するメッセージを送ることによって互いに通信する。例えば、系列７００のネットワーク・デバイス１０２−１が、系列７００のネットワーク・デバイス１０２−２にメッセージを送ることが可能であり、このメッセージは、ネットワーク・デバイス１０２−１のフレーム７０２−１とネットワーク・デバイス１０２−２のフレーム７０２−２の間に適用されるべきオフセット７１０を指定する。同様に、ネットワーク・デバイス１０２−２が、ネットワーク・デバイス１０２−３にメッセージを送ることが可能であり、このメッセージは、ネットワーク・デバイス１０２−２のフレーム７０２−２とネットワーク・デバイス１０２−３のフレーム７０２−３の間に適用されるべきオフセット７１２を指定する。この例において、この特定のオフセットは、ネットワーク・デバイスのうちの１つにおけるフレームの第１の活性期間の始まりと、その系列の直近の隣接するネットワーク・デバイスの第１の活性期間の始まりの間の時間的離隔を表す。このため、系列の最後のネットワーク・デバイス以外の、系列７００のネットワーク・デバイス１０２のそれぞれが、系列の下流の直近の隣接するネットワーク・デバイスに、送信側ネットワーク・デバイスの初期活性期間と隣接するネットワーク・デバイスの初期活性期間の間のオフセットを指定するメッセージを送ることが可能である。同様のメッセージングを使用して通信され得る他の情報には、例えば、デバイスのいずれが同一の系列に関連するかを特定するのにネットワーク・デバイス１０２のそれぞれの系列分解モジュール２１２によって利用される情報が含まれる。
【００３６】
図７の実施形態におけるフレーム７０２−１、７０２−２、および７０２−３を参照すると、各フレーム内のスケジュールされた活性期間および不活性期間が異なり得ることを見て取ることができる。このため、系列７００のネットワーク・デバイスのうちの１つのネットワーク・デバイスに関する所与のスケジュールされたフレームが、その系列のネットワーク・デバイスのうちの別の１つに関する対応するスケジュールされたフレームとは異なる、活性期間および不活性期間の構成を有することが可能である。また、図から明らかなとおり、その系列のネットワーク・デバイスのうちの１つのネットワーク・デバイスの活性期間の少なくとも１つが、その系列のネットワーク・デバイスの別のネットワーク・デバイスの活性期間の少なくとも１つとは異なる処理レベルに対応することも可能である。
【００３７】
次に、本発明の或る実施形態のより詳細な例を説明する。この実施形態において、各ネットワーク・デバイスは、最大レートの活性モード、またはゼロ・レートのスリープ・モードで動作するものと想定される。ネットワークは、ノードのペアの間でパケットを指定されたレートでそれぞれが送信する必要がある接続のセットをサポートする。接続ｉが、パスＰｉに沿ってルーティングされ、ただし、Ｐｉは、入力として与えられることも、出力の一部として計算されることも可能である。ここでは、両方の状況を検討する。ルートが入力の一部ではない場合、問題のルーティング部分は、各接続ｉに関してルートＰｉを指定する。パケット着信は、リーキーバケット制御され、接続ｉは、ρｉという所望されるレートを有する。問題のスケジューリング部分は、各リンクの活性期間、すなわち、リンクがいつ、Ｒ＝１に正規化された最大レートで動作するか、および各活性期間内でパケットにどのように優先順位が付けられるかを指定する。２つのモードの間で遷移することは、δ単位時間を要し、さらに最大レートと同一のレートでエネルギーを消費し、ただし、ネットワーク・デバイスは、この遷移中にパケットを全く処理することができない。
【００３８】
リンクのスケジューリングについて、この特定の例との絡みで述べたことは、それらのリンクを駆動するそれぞれのネットワーク・デバイスのスケジューリングを包含することを意図していることを理解されたい。
【００３９】
各リンクが、長さＴ、（０，Ｔ］、（Ｔ，２Ｔ］、．．．の毎フレーム内で固定の持続時間にわたって活性であるフレーム・ベースのスケジュールに注目する。
【００４０】
【数１】
2013523012.tif 000003
を、リンクｅを通る合計レートであるものとする。
Ａｅ＝Ｔ・Ｒｅ
を、リンクｅに関する活性期間の最小限の長さとする。各リンクｅ上の活性期間の持続時間が正確にＡｅである場合、スケジュールを「最小限」と呼ぶ。明らかに、固定のセットのルートに関して、さらに固定のＴに関して、最小のスケジュールは、エネルギー最適である。
【００４１】
以下の結果を証明する。簡明のため、或るリンクにわたって１つのパケットを送信することは、１単位時間、または１時間ステップを要するものと想定する。以下の結果は、任意のリンク伝送時間を有するリンクに一般化される。
【００４２】
系列・トポロジから始める。ルーティングは固定であるので、スケジューリングだけに注目する。ｋｉ個のリンクの各接続ｉに関する終端間遅延が、２Ｔ＋ｋｉを上限とする。また、すべてのｅに関して活性期間の持続時間がＡｍａｘ＝ｍａｘｅＡｅである準最小のスケジュールも提示する。この事例に関して、すべてのｉについてＴ＋ｋｉという終端間遅延を示す。
【００４３】
それぞれの固定のＴに関して、これら２つのスケジュールの間のエネルギー−遅延トレードオフは、遅延のより小さいスケジュールが、より多くのエネルギーを消費し、遅延のより大きいスケジュールが、より少ないエネルギーを消費するので、明確である。各スケジュール内で、より大きいＴは、より大きい遅延限度を暗示するが、活性−スリープ遷移の回数がより少なく、したがって、エネルギー消費がより少ないので、やはりトレードオフが見られる。
【００４４】
次に、どのように系列・スケジューリング技術を適用して、任意のトポロジを有するネットワークに関する結果を得るかを示す。ルーティングが入力の一部ではない場合、遷移費用とともに
【００４５】
【数２】
2013523012.tif 000004
を最小限に抑えることを目的としてルートをまず選択する。この合計は、
【００４６】
【数３】
2013523012.tif 000005
というファクタの範囲内に近似されることが可能であり、ただし、ｎは、ネットワークのサイズである。さらに、それらのルートがツリーを形成することを保証することも可能である。キャタピラ分解を使用して、そのツリーを系列のコレクションに区分して、各接続パスがせいぜい２ｌｏｇｎの線と交差するようにする。各線に沿って、最小のスケジュールを採用する。パケットが系列から系列に移動する際、Ｔという最大限の追加の遅延で十分である。このことは、すべての接続に関する終端間遅延において
【００４７】
【数４】
2013523012.tif 000006
保証を証明することを許す。
【００４８】
ルーティングが既に指定されている場合、各接続ｉに関してＴ・ｋｉという遅延限度を有する単純明快な最小のスケジュールを提示する。しかし、リンクが、十分に大きいフレーム内でより長い間、活性である場合、向上した遅延限度が与えられる。このことはやはり、エネルギーと遅延の間のトレードオフを証明する。
【００４９】
系列上のスケジューリング
前述したとおり、系列上の接続のセットをスケジュールすることから始める。各接続の末端は、必ずしもその系列のエンドポイントではない。系列・トポロジは制限されるものの、このソリューションは、任意のトポロジを扱うためのビルディング・ブロックとして使用される。或る系列に関して、すべてのｅについてＴ≧Ａｅ＋２δである限り、任意のフレーム・サイズＴを選択することができる。Ａｅ＝Ｔ・Ｒｅであるので、このことは、
【００５０】
【数５】
2013523012.tif 000007
を暗示する。或る系列・トポロジに関して、せいぜいＴの初期遅延の後、各パケットは、せいぜいＡｍａｘのさらなるキューイング遅延でそのパケットの宛先に到達することができることが以下に示される。活性期間は、各リンクｅに関して最小であるＡｅである。
【００５１】
最小のスケジュールを最初に定義する。その系列に沿ったリンクにｅ１、ｅ２などとラベルを付ける。任意の整数ｊ≧１に関して、第ｉのリンクｅｉに関する第ｊの活性期間は、
【００５２】
【数６】
2013523012.tif 000008
である。以降、固定のｊを考慮する。Ｓｉを、ｅｉを最初のリンクとして有し、さらに期間［（ｊ−１）Ｔ＋ｉ，ｊＴ＋ｉ）中に注入されるパケットのセットとする。以下に、
【００５３】
【数７】
2013523012.tif 000009
の中のパケットが、各リンクの第ｊの活性期間中にそれらのパケットの宛先に伝送されることを示す。
【００５４】
これらのパケットに活性期間内のタイムスロットを割り当てて、ｉ）各パケットに関して、そのパケットのルーティング・パス上のタイムスロットが、非減少であるようにし、さらにｉｉ）共通のリンクを共有する２つのパケットに関して、それらのパケットに、この共通のリンク上で別々のスロットが割り当てられるようにする。これらの要件を伴って、タイムスロットは、各パケットがいつ前に進むかを規定する。
【００５５】
【数８】
2013523012.tif 000010
の中のパケットから、パスが系列全体の最小の範囲を形成するパケットを繰り返し抽出し、すなわち、これらのパケット・パスのいずれの適切なサブセットも、系列全体を範囲に含むことはあり得ない。この最小の範囲Ｃから、重なり合いを取り除き、さらに各リンクが厳密に１つのパケット・パスの範囲に含まれる正確な範囲を作成する。Ｃは最小であるので、ｅ１を含む一意のパケット・パス、例えば、ｐから始める。ｐが別のパケット・パス、例えば、ｑと最初に重なり合うまで、ｐをたどる。正確な範囲として
【００５６】
【数９】
2013523012.tif 000011
を保持し、
【００５７】
【数１０】
2013523012.tif 000012
を取り除く。Ｃが最小であることのため、ｑはやはり、一意であることに留意されたい。ｑが別のパケット・パスと重なり合うまで、ｑをたどることにとりかかる。ｑから同様に重なり合いを取り除く。すべての重なり合いが取り除かれると、Ｃは、正確な範囲となる。次に、すべてのパスＣに、活性期間のそれぞれから次の利用可能なタイムスロットが割り当てられる。次の利用可能なタイムスロットは、何らかの共通のｋに関する各活性期間の第ｋのスロットであることに留意されたい。この不変関係は、簡単な帰納法を介して成立する。また、パケット・パスが切断された場合、取り除かれた部分は常に、取り除かれてない部分に沿い、したがって、後に、より大きいタイムスロットを常に割り当てられることにも留意されたい。このことは、タイムスロット割当てがパケット移動に関して実現可能であることを確実にする。残りのパケット・パスの結合が系列全体を範囲に含まない場合、接続されていない各系列に対して前述のプロセスを実行する。また、
【００５８】
【数１１】
2013523012.tif 000013
の中のパケットのせいぜいＡｅ個が、各リンクｅを要求することにも留意されたい。したがって、活性期間は、すべてのパケットに関して十分なスロットを有する。このため、遷移時間（１つのリンクから次のリンクまでの活性期間のずれによって反映される）に加えて、
【００５９】
【数１２】
2013523012.tif 000014
の中のパケットは、合計でせいぜいＡｍａｘのキューイング時間を経験する。
【００６０】
範囲を繰り返し作成する前述の集中アルゴリズムは、前述したＦＴＧによって置き換えられることが可能である。各リンクｅに関して、そのリンクｅの活性期間中、ＦＴＧは、
【００６１】
【数１３】
2013523012.tif 000015
の中の、伝送されるべき残りのリンクの数が最大であるパケットを優先させる。ＦＴＧが、前述した集中アルゴリズムに合うことを理解するのに、各ｋ≧０に関して、各活性間隔内の第ｋのタイムスロットを使用するパケットについて、それらのパケットのパケット・パスが系列の最小の範囲を形成していることに注目する。
【００６２】
各リンクの活性期間をＡｍａｘに緩めた場合、各パケットは、Ｔまでの初期遅延の後、移動を始めると、キューイング遅延を全く経験しない。或る系列・トポロジに関して、せいぜいＴまでの初期遅延の後、各パケットは、さらなるキューイング遅延なしに、そのパケットの宛先に到達することが可能であることが示され得る。活性期間は、各リンクに関してＡｍａｘである。このことは、以下のとおり示されることが可能である。任意の整数ｊ≧１に関して、系列に沿った第ｉのリンクｅｉに関する第ｊの活性期間は、［ｊＴ＋ｉ，ｊＴ＋ｉ＋Ａｍａｘ）である。この場合も、Ｓｉを、ｅｉを最初のリンクとして有し、さらに期間［（ｊ−１）Ｔ＋ｉ，ｊＴ＋ｉ）中に注入されるパケットのセットとする。
【００６３】
【数１４】
2013523012.tif 000016
の中のパケットは、各リンクの第ｊの活性期間中にそれらのパケットの宛先に伝送される。このことを理解するのに、
【００６４】
【数１５】
2013523012.tif 000017
からのパケットのうちせいぜいＡｍａｘ個が、それらのパケットのパスに沿ってｅを有することに留意されたい。したがって、よく知られた間隔グラフ彩色結果は、Ｓの中の各パケットに［１，Ａｍａｘ］の中の或る色が割り当てられて、２つのパケットに、それらのパケットがリンクを共有する場合に別々の色が割り当てられるようになることが可能である。これらの色は、パケットが前に進むことができる活性期間中のタイムスロットを規定する。このようにして、パケットが１つのリンクから次のリンクに移動する際、パケットにはスロットが伝送のために即時に利用可能である。
【００６５】
組み合わされたルーティングとスケジューリング
次に、任意のネットワーク・トポロジの場合に注目する。ルーティングが入力として与えられない場合、各接続ｉに関するパスＰｉをまず選択する。
【００６６】
【数１６】
2013523012.tif 000018
が、ルーティングの結果としてのリンクｅ上の合計レートであることを思い起こされたい。
【００６７】
【数１７】
2013523012.tif 000019
とする。
【００６８】
【数１８】
2013523012.tif 000020
を目的として接続をルーティングすることによって、すべてのリンク上の伝送時間とともに合計の活性期間を最小限に抑え、さらに、したがって、エネルギーを最小限に抑える。前述の公式は、Ｒｅ＜１である場合に限って意味を成すことに留意されたい。エネルギー低減は、最大レートＲ＝１が、必要とされるより相当に大きいシナリオによって動機付けられているので、ルーティングにかかわらず、Ｒｅ＝１であるものと無理なく想定することができる。
【００６９】
ｆ（・）は、凹関数であり、さらにこのルーティング問題は、事実上、よく研究されているバルク買い型ネットワーク設計問題に相当することに留意されたい。１つの可能なソリューションは、ツリー・メトリックによって確率論的に近似するメトリックの概念を利用する。Ｂ．ＡｗｅｒｂｕｃｈおよびＹ．Ａｚａｒ、「Ｂｕｙ−ａｔ−ｂｕｌｋ  ｎｅｔｗｏｒｋ  ｄｅｓｉｇｎ」、Ｐｒｏｃ．ＩＥＥＥ  ＦＯＣＳ、１９９７年、およびＹ．Ｂａｒｔａｌ、「Ｏｎ  ａｐｐｒｏｘｉｍａｔｉｎｇ  ａｒｂｉｔｒａｒｙ  ｍｅｔｒｉｃｓ  ｂｙ  ｔｒｅｅ  ｍｅｔｒｉｃｓ」、Ｐｒｏｃ．ＡＣＭ  ＳＴＯＣ、１９９８年を参照されたい。考え方は、複数のツリーにわたる確率分布によってグラフＧにおける距離を近似することである。詳細には、ｄｉｊ（Ｇ）をグラフＧにおけるリンクの長さ（ｉ，ｊ）とする。ツリーＨが、確率分布によりランダムに選択されるものと想定し、さらにｄｉｊ（Ｈ）を、ツリーＨにおけるｉとｊの間の距離とする。複数のツリーにわたる確率分布α−は、
Ｅ（ｄｉｊ（Ｈ））／α≦ｄｉｊ（Ｇ）≦ｄｉｊ（Ｈ）
である場合、グラフＧを確率論的に近似するものとする。
【００７０】
前段で参照したＡｗｅｒｂｕｃｈおよびＡｚａｒの参考文献において、確率分布によりツリーをランダムに選択し、次に、すべての接続を、そのツリーによって指定される一意のパスに沿ってルーティングする場合、αの広がりが、バルク買いに関するＯ（α）近似を暗示することが示される。
【００７１】
αについて以下の結果を使用する。すなわち、すべてのネットワークＧが、
【００７２】
【数１９】
2013523012.tif 000021
に関して、スパニング・ツリーにわたる多項式として計算可能な確率分布によってα確率論的に近似され得る。
【００７３】
【数２０】
2013523012.tif 000022
の概念は、ｌｏｇｌｏｇｎ以下の項を隠す。実際、αの正確な値は、Ｏ（ｌｏｇｎｌｏｇｌｏｇｎｌｏｇ３ｌｏｇｌｏｇｎ）である。このことは、遷移時間と合わせた合計の活性期間が、
【００７４】
【数２１】
2013523012.tif 000023
に最小最適を掛けた値であるようにルーティングを選択するランダム化されたアルゴリズムが存在することを暗示する。さらに、ルートがツリーを形成し、任意の接続に関して、ツリーを渡る予期されるルーティング距離は、
【００７５】
【数２２】
2013523012.tif 000024
に元のネットワークを渡る最短のパス距離を掛けた値である。
【００７６】
結果としてもたらされるルートがツリーを形成するという事実をさらに利用する。ツリーのキャタピラ分解と系列・トポロジにわたるスケジューリングを組み合わせることによって、スケジューリング問題を解決する。より具体的には、パケットのキューイング遅延が、初期にせいぜいＴであり、パケットが移動を始めると、合計でせいぜいＡｍａｘ＝Ｔ・Ｒｍａｘが加わる、系列上の最小のスケジュールを設計する。ルーティングをサポートするリンクがツリーを形成することから、キャタピラ分解は、このツリーを、各接続のルーティング・パスがせいぜい２ｌｏｇｎの系列を通るように、系列のコレクションに区分することを許すことを以下に示す。パケットが新たな系列に切り換わるたびに、最悪ケースでは、パケットは、初期のキューイング遅延を被る。
【００７７】
系列上でどのようにスケジュールすべきかを知り、ルーティング・ツリーを、キャタピラ分解と同様の仕方で系列のコレクションに区分する。この分解によれば、任意のツリーは、任意の２つのノードの間の一意のパスが、せいぜい２ｌｏｇｎの系列を通り、ただし、ｎは、そのツリーにおけるノードの数であるように、複数の系列に区分され得る。キャタピラ分解に関するさらなる詳細については、Ｊ．Ｍａｔｏｕｓｅｋ、「Ｏｎ  ｅｍｂｅｄｄｉｎｇ  ｔｒｅｅｓ  ｉｎｔｏ  ｕｎｉｆｏｒｍｌｙ  ｃｏｎｖｅｘ  ｂａｎａｃｈ  ｓｐａｃｅｓ」、Ｉｓｒａｅｌ  Ｊｏｕｒｎａｌ  ｏｆ  Ｍａｔｈｅｍａｔｉｃｓ、１１４：２２１〜２３７頁、１９９９年を参照されたい。
【００７８】
ツリーが系列に分解されると、前述した最小のスケジュールが、各系列において使用される。接続ｉの予期される終端間遅延は、
【００７９】
【数２３】
2013523012.tif 000025
であり、ただし、ｋｉは、元のネットワークを渡る最短のパス距離である。さらに、このスケジュールは、最小である。このことは、以下のとおり示され得る。スパニング・ツリーの広がりは、選択されたツリーにおけるルーティング・パスの長さが、
【００８０】
【数２４】
2013523012.tif 000026
に元のグラフにおける最短のパス距離を掛けた値であることを暗示する。したがって、伝送時間は、
【００８１】
【数２５】
2013523012.tif 000027
にｋｉを掛けた値である。キャタピラ分解から、ツリーにおけるルーティング・パスが、２ｌｏｇｎの系列に区分され得る。したがって、キューイング遅延は、せいぜい２ｌｏｇｎに、１つの系列における最大遅延、Ｔ＋Ａｍａｘ≦２Ｔを掛けた値である。
【００８２】
Ｒｅ＝１であるので、各フレーム内の不活性期間の長さは、Ｔ−Ａｅ＝Ω（Ｔ）であることに注目されたい。すると、この期間の始めに着信するパケットは、移動する前にΩ（Ｔ）待たなければならない。このため、接続ｉに関するパケット遅延は、Ω（Ｔ＋ｋｉ）を下限とする。組み合わされたルーティングとスケジューリングのスキームは、遅延最小化に関する
【００８３】
【数２６】
2013523012.tif 000028
近似、およびエネルギー最小化に関する
【００８４】
【数２７】
2013523012.tif 000029
を確実にすることがさらに示され得る。
【００８５】
所与のルートを用いたスケジューリング
組み合わされたルーティングとスケジューリングのスキームに関する前のセクションにおいて、ルートがツリーを形成するという事実を利用した。このセクションでは、ルートが入力として与えられていると想定するスケジューリングに注目し、さらにこれらのルートが任意のトポロジを形成するものと想定する。
【００８６】
Ａ．エネルギー最適アルゴリズム
任意のトポロジのネットワークにおいて最小のスケジュールが常に可能であるが、パケットは、１リンク当たりＴの遅延を経験する可能性があることを証明する簡単なアルゴリズムから始める。ｋｉを、接続ｉに関するルートＰｉのホップ・カウントとする。任意のトポロジを有するネットワークに関して、接続ｉの終端間遅延は、最小のスケジュールの下でＴ・ｋｉを限界とする。このことは、以下のとおり示され得る。最小のスケジュールをまず定義する。各時間フレームに関して、リンクｅが、第１のＴ・Ｒｅ時間ステップに関して活性化される。時間ステップｊＴの始まりで、Ｓｅを、リンクｅでキューに並んでいるパケットのセットとする。時間フレーム［ｊＴ，（ｊ＋１）Ｔ）中、Ｓｅからのパケットだけがリンクｅに沿って前に進む。つまり、［ｊＴ，（ｊ＋１）Ｔ）中に着信するパケットは、活性期間［ｊＴ，ｊＴ＋ＴＲｅ）中に余地が存在する場合でさえ、次のフレーム［（ｊ＋１）Ｔ，（ｊ＋２）Ｔ）まで待たなければならない。以下に、｜Ｓｅ｜≦ＴＲｅであることを示す。これまで、各パケットが１つのリンクを進むのに１つのフレームを要するものと帰納的に想定している。したがって、Ｓｅは、リンクｅで始まり、［（ｊ−１）Ｔ，ｊＴ）中に注入される接続からのパケット、およびｅを第ｉのリンクとして有し、［（ｊ−ｉ）Ｔ，（ｊ−ｉ＋１）Ｔ）中に注入される接続からのパケットから成る。これらの接続の合計レートは、Ｒｅである。したがって、｜Ｓｅ｜≦Ｔ・Ｒｅである。Ｓｅからのすべてのパケットは、時間フレームの始まりにリンクｅにおいてキューに並んでいるので、最初のＴ・Ｒｅ時間ステップであるフレームの活性期間中にリンクｅに沿って伝送され得る。
【００８７】
この最小のスケジュールは、接続ルートを、各リンクが異なる系列である複数の系列にする自明な分解と見なされ得る。その理由で、パケットは、系列切換えを経験し、このため、各エッジにおいてせいぜいＴの遅延を経験する。明らかに、接続パスを複数の系列にする他の任意の分解が、系列切換えを減らすことによって終端間遅延を向上させる。残念ながら、最悪ケースにおいて、どのように分解が行われるかとは無関係に、ほとんどすべての接続ｉがΩ（ｋｉ）回の系列切換えを経験するネットワークおよび接続セットを見出す可能性があるので、向上のための多くの余地は存在しない。しかし、後段で説明される実験結果は、実際的なレベルで、このことが見込みのあるアプローチであり得ることを示す。
【００８８】
Ｂ．遅延向上アルゴリズム
活性期間が非最小であることを許す場合、パケットが被る最大遅延は、十分に大きいＴに関して、２Ｔまで小さくされることが可能である。より具体的には、十分に大きいフレーム・サイズＴに関して、１つのフレーム中に注入されたすべてのパケットは、次のフレームの活性期間中にそれらのパケットの宛先に到達することが可能であり、さらに活性期間の長さは、せいぜいＴ＋Ｏ（ｋｍａｘｌｎ（ｍＴ））であり、ただし、ｍは、ネットワークにおけるリンクの数であり、さらにｋｍａｘ＝ｍａｘｉｋｉである。
【００８９】
実験結果
このセクションにおいて、シミュレーションを介して、２つのフレーム・ベースのスケジュール、すなわち、調整されたスケジュールと調整なしの単純なスケジュールを比較する。両方のスケジュールは、最小であり、このため、エネルギーの点で最適である。したがって、パケットの平均遅延および最大遅延を、この２つのスケジュールを比較する際の品質メトリックとして使用する。本明細書でＳＷＣ（調整を伴うスケジュール）と呼ばれる、調整されたスケジュールは、複数の系列に関して定義される。調整されたスケジュールは、活性期間が系列上でずらされて、各フレーム内で時間Ａｅにわたって各エッジｅを活性化し、さらに、前述したとおり、系列のエッジのそれぞれにおいてＦＴＧスケジューリング・プロトコルを適用する。ＳＷＯＣ（調整なしのスケジュール）は、フレームの始まりで時間Ａｅにわたって各エッジｅを単に活性化し、ＦＩＦＯを使用してパケットをスケジュールする。
【００９０】
２つのセットのシミュレーションが実行される。第１のセットは、系列であるネットワークを使用するのに対して、第２のセットは、一般的なネットワークを使用する。各シナリオにおいて、接続の数は決っており、各接続の末端は、ネットワークにおけるすべてのノードの中からランダムに一様に選択される。接続レートは、ρ＝１／５０に固定され、したがって、各Ｔフレーム内の各接続につきρＴ個のパケットが着信する。各パケットは、フレーム内の一様に選択された時間ステップで着信する。しかし、ＳＷＣは、リンクが活性であり、さらに利用可能なタイムスロットが存在する場合でさえ、次のフレームまで移動するようにパケットをスケジュールしない。所与のセットのパラメータに関して、これらのパラメータに対応する実験が、１０回、実行され、さらに観察された結果が、平均される。
【００９１】
Ａ．系列
４０のリンクの系列であるネットワークに関するシミュレーション結果をまず提示する。このネットワークにおいて、パス長１０を有する５０の接続が、ランダムに選択される。次に、５０から２５０の範囲内の時間フレーム・サイズＴを用いたシミュレーションが実行される。これらのシミュレーションの結果から、ＳＷＣは、ＳＷＯＣと比べて相当に小さい終端間遅延をもたらすことが観察される。平均終端間遅延と最大終端間遅延はともに、ＳＷＣおよびＳＷＯＣの下でＴとともに増加する。しかし、その増加は、ＳＷＯＣの下でより速く、このことは、フレームが大きいほど、ＳＷＯＣではなく、ＳＷＣを使用することが、より好都合であることを意味する。接続パスの長さを変更することは、ＳＷＣがＳＷＯＣより優れたパフォーマンスを示すという事実を変えないことも観察された。例えば、３０というパス長の場合、ＳＷＣは、ＳＷＯＣと比べて、少なくとも２６％、より良好な平均終端間遅延をもたらす。このため、活性期間および不活性期間の調整されたスケジューリングは、所与の活性時間に関する遅延を大幅に小さくすることができる。
【００９２】
Ｂ．ＮＳＦネットワーク
考慮する第２のネットワークは、１４のノードと、２０のリンクとから成るＮＳＦネットワークである。このネットワークおいて、さらに任意のネットワークにおいても、ＳＷＯＣは、単に最短のパス・ルーティングを使用して、系列において機能したのと同様に機能する。しかし、ＮＳＦネットワークにおいて、さらに任意のネットワーク全般において、ＳＷＣをどのように機能させるかを定義する必要がある。ソリューションは、以下のとおり系列分解を行うことである。すなわち、エッジがつながっていない複数の系列にネットワークを分解し、これらの線に沿って接続をルーティングし、さらに各系列においてＳＷＣを使用することである。この事例において、ＮＳＦネットワークを、リンクがつながっていない４つの系列に手作業で分解する。
【００９３】
必要な場合、パケットは、系列を切り換えなければならない。このシミュレーションにおいて、パケットが系列を切り換えなければならなくなった場合、切り換わるパケットｐは、いずれの新たな着信するパケットとも同様に、その新たな系列において扱われ、詳細には、ｐは、次のフレームまで、移動しない。このことは、各系列切換え時にＳＷＣに高いペナルティを課す。関心があるのは、接続パスの長さ対系列切換えの回数の比である、パラメータκによって捕捉される、パス長に関して系列切換えが終端間遅延に与える影響である。元のＮＳＦネットワークは小さいので、各リンクを長さｌのパスで置き換えることによってＮＳＦネットワークを拡大する。このことは、系列切換えの回数を変えることなしに、前段で定義した比κを大きくすることを許す。このため、これらのシミュレーションにおいて、ｌは、前述の比をほぼ表す。
【００９４】
ＮＳＦネットワークにおける各実験において、１００の接続が作成される。各接続において、同一の数のパケットρＴが、各Ｔフレーム内で各端末ノードにおいて、他方の端末ノードに向けて注入される。前述したとおり、これらのパケットは、ＳＷＯＣを使用している場合、最短のパスを介してルーティングされ、ＳＷＣを使用している場合、分解系列を介してルーティングされる。シミュレーションの結果は、小さいｌ（例えば、ｌ＝１）に関して、ＳＷＣとＳＷＯＣが同等のパフォーマンスを有することを示す。しかし、ｌがより大きくなる（例えば、ｌ＝１０）と、ＳＷＣが、平均と最悪ケースの両方で、ＳＷＯＣと比べて、相当により良好な遅延をもたらす。以下の表Ｉが、値ｌ＝１０に関する実験において観察されるいくつかのパラメータを要約する。この表から、ｌは、実際、比κのように振舞うことが直ちに明白である。このため、この表、および前述したその他の結果から、比κが大きくなるにつれ（例えば、２．０／０．６３＜２０．７／１．１）、ＳＷＣが、ＳＷＯＣと比べて、はるかに良好な終端間遅延パフォーマンスをもたらすと結論付けることができる。
【００９５】
【表１】
2013523012.tif 000030
【００９６】
以上の詳細な例は、本発明の特定の実施形態のパフォーマンス上の利点を例示するために提示されており、さらに例の中で行われた想定は、本発明のその他の実施形態において必ずしも適用されないことを認識されたい。
【００９７】
前述したとおり、本発明の実施形態は、少なくとも部分的に、通信ネットワークのネットワーク・デバイスまたは他の処理デバイスのメモリまたは他のコンピュータ可読記憶媒体の中に格納された１つまたは複数のソフトウェア・プログラムの形態で実施され得る。スケジューラ２１０や系列分解モジュール２１２などのデバイス構成要素は、少なくとも部分的に、ソフトウェア・プログラムを使用して実施され得る。また、前述したとおり、それぞれの個別のネットワーク・デバイスにおいて実施されるのではなく、これらの構成要素は、代わりに、コントローラ１０４などの集中型デバイスにおいて実施されることも可能である。
【００９８】
もちろん、任意の組合せにおけるハードウェア、ソフトウェア、またはファームウェアの多数の代替の構成が、本発明によるこれら、およびその他のシステム要素を実施する際に利用され得る。例えば、本発明の実施形態は、任意の組合せにおけるＦＰＧＡ（フィールド・プログラマブル・ゲート・アレイ）、ＡＳＩＣ（特定用途向け集積回路）、または他のタイプの集積回路デバイスとして実施され得る。そのような集積回路デバイス、ならびにそのようなデバイスの部分または組合せが、本明細書で使用される用語における「回路」の例である。
【００９９】
前述した実施形態は、単に例示を目的としており、限定するものと解釈されてはならないことが再び強調されなければならない。他の実施形態が、特定の用途のニーズに依存して、異なるタイプのネットワーク、デバイス構成、および通信媒体を使用することが可能である。したがって、代替の実施形態は、ネットワーク・デバイスにおける活性期間および不活性期間の調整されたスケジューリングによって通信ネットワークにおけるエネルギー効率をもたらすことが望ましい他の脈絡で、本明細書で説明される技術を利用してもよい。また、例示的な実施形態を説明することとの絡みで行われた特定の想定は、本発明の要件と解釈されてはならないことも理解されたい。本発明は、これらの特定の想定が適用されない他の実施形態において実施され得る。添付の特許請求の範囲に含まれる、これら、および他の多数の代替の実施形態は、当業者には直ちに明白であろう。
【図１】
2013523012.tif 000031
【図２】
2013523012.tif 000032
【図３】
2013523012.tif 000033
【図４】
2013523012.tif 000034
【図５】
2013523012.tif 000035
【図６】
2013523012.tif 000036
【図７】
2013523012.tif 000037
【国際調査報告】
2013523012.tif 000038
2013523012.tif 000039
2013523012.tif 000040