調査と解説

省電力化のためのトラフィック最適設計・制御

省電力化のためにルーティングやネットワーク構造を設計・制御する方法として，おおきくわけると 2 種類あるとかんがえられる．

第 1 は静的な最適化問題として定式化する方法である． この方法においては条件が変化するたびに最適化問題をときなおす必要がある． 問題をとく方法として線形のアルゴリズムが存在するばあいはよいが，最適化問題であるため，通常は計算量が NP となる． このばあいには，実ネットワークへの適用は不可能にちかいとかんがえられる．

第 2 は動的な最適制御またはオンライン・アルゴリズムとして定式化する方法である． このばあいは基本的にはある時刻にえられた解をもとにして，変化した条件のもとでの (つぎの時刻の) 解を計算することになり，計算量が減少することが期待される．

静的な最適化問題としての省電力化

Chabarek ら [Cha 08] は電力最適化のためにつぎのような方法をとっている． ネットワーク・ノードのライン・カードや筐体の電源が on/off できることを仮定し，問題を多種流制約 (multi-commodity constraints) がある混合整数計画法として定式化している． これを CPLEX というソルバーを使用して branch-and-cut 法によって，といている．

荒川ら [Ara 08] は電力最適化のために，ネットワーク・ノードのインターフェースとノードの電源遮断がおこなえることを仮定して，この問題を集合被覆問題として定式化し，それを並列リコンフィギャラブル・プロセッサ DAPDNA-2 という特殊なハードウェアを使用することによって高速にといている．

動的な最適制御またはオンライン・アルゴリズムとしてのネットワーク設計・制御

Räcke [Rac 02] は一般のネットワークにおいて輻輳を最小化するオンライン・アルゴリズムを記述している． このアルゴリズムは現在のネットワーク負荷に依存しない (oblivious) というきわだった特徴をもっている． このアルゴリズムの計算時間は多項式時間ではないが，Azar ら [Aza 03] はこのアルゴリズムを改良して多項式時間とし，さらに Applegate ら [App 03] が線形プログラミングによる解法を記述している． しかし，これらのアルゴリズムはまだ省電力化には適用されていない．

参考文献

• [App 03] Applegate, D. and Cohen, E., “Making Intra-domain Routing Robust to Changing and Uncertain Traffic Demands: Understanding Fundamental Tradeoffs”, 2003 conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, pp. 313-324, 2003.
• [Ara 08] 荒川豊, 石井大介, 津留崎彩, 山中直明, 石川浩行, 斯波康裕, “ネットワークの低消費電力化に向けた網再構成手法”, 電子情報通信学会技術研究報告. PN, フォトニックネットワーク, 108 (183), pp. 13-18, August 2008.
• [Aza 03] Azar, Y., Cohen, E., Fiat, A., Kaplan, H., Räcke, H., “Optimal Oblivious Routing in Polynomial Time”, 35th Annual ACM Symposium on Theory of Computing, pp. 383-388, 2003.
• [Cha 08] Chabarek, J., Sommers, J., Barford, P., Estan, C., Tsiang, D., and Wright, S., “Power Awareness in Network Design and Routing Export”, 27th IEEE Conference on Computer Communications (INFOCOM 2008), pp. 457-465, 2008.
• [Gup 07] Gupta, M. and Singh, S., “Using Low-Power Modes for Energy Conservation in Ethernet LANs”, 26th IEEE Int'l Conf. on Computer Communications (INFOCOM 2007), pp. 2451-2455, May 2007.
• [Rac 02] Räcke, H., “Minimizing Congestion in General Networks”, 43rd Annual IEEE Symposium on Foundations of Computer Science, pp. 43-52, 2002.