2018/3/3

Osaka University

Osaka University

研究背景• インターネットを介したサービスの普及によるトラヒックの増加に伴い[2]，ネットワークの消費電⼒は増加[3]パレート最適制御に基づく進化的ネットワーク省電⼒化⼿法• ネットワーク省電⼒化• 環境の変化に合わせつつ，ネットワーク機器をスリープ化• トラヒック量に応じて，⼀部のリンクにトラヒックを集約

トラヒック量スリープ

秋下 耀介
⼤阪⼤学 ⼤学院情報科学研究科
博⼠前期課程 ２年
村⽥研究室

時刻

2018/3/3

1

2018/3/3[2] Cisco,“Ciscoglobalcloudindex:forecastandm ethodology,2014-2019,” Cisco System s Inc., Tech. Rep., Oct. 2015.

Osaka University

Osaka University

従来⼿法

研究⽬的とアプローチ• 単⼀の⽬的関数で省電⼒化• ⽬的• オンになるリンク数の最⼩化[4]•• 環境変動に追随し複数の⽬的を同時達成するネットワーク制御⼿法の確⽴

min∑' 𝑝(𝑙)min∑((,*)∈1 𝑝(,* 𝑥(,* + ∑-∈0 𝑝- 𝑦-• 環境変動：トラヒック変動，故障など

ノードとリンクの総消費電⼒の最⼩化[5]• 複数の⽬的：耐故障性，性能の確保，低消費電⼒化など
𝒇𝟏→ ネットワークに必要な指標を制約条件として考慮• バイナリ変数を含む最適化により計算時間が増加→変動に対応不可• 省電⼒化以外の指標について最適化が⾏われない• アプローチ

劣解𝒇𝟐• パレートフロント（パレート最適解の集合）を導出• パレートフロントから⼀つをネットワークの設定として投⼊• 同じ消費電⼒でもより性能の⾼い解，信頼性の⾼い解を適⽤すべきパレートフロント• ネットワークの環境変動により適切な解は変化•
環境変動に追随したパレートフロントの導出

複数の指標を考慮した多⽬的最適化が必要[4] Wei, Yunkai, et al. "Energy-aware traffic engineering in hybrid SDN/IP backbone networks." Journal of Communications and Networks 18.4 (2016): 559-566.
[5] Amaldi, E. and Capone, A. and Gianoli, L. G., “Energy-aware IP traffic engineering with shortest path routing,” Comput. Netw., vol. 57, pp. 1503–1517, Apr. 2013.

パレート最適解

⼀⽅の指標の改善を他の指標を悪化させず⾏うことが不可能な解• 複数⽬的を考慮した最適解はパレート最適解•
パレート最適制御によるネットワーク省電⼒化• 本来は省電⼒化以外の指標も考慮したより良い解が望ましい2018/3/3

2[3] Van Heddeghem , Ward and Lam bert, Sofie and Lannoo, Bart and Colle, Didier and Pickavet, Mario and Dem eester, Piet, “Trends in worldwide ICT electricity consum ption from2007 to 2012,” Com puter Com m unications, vol. 50, pp. 64–76, Sep. 2014.

3

2018/3/3

4

Osaka University

Osaka University

パレート最適制御によるネットワーク省電⼒化

環境変動に追随したパレートフロントの導出• 以下の⼿順を 10 分程度の制御間隔で⾏う• 環境が変動するとパレートフロント⾃体が変化

1. 全通信ペアのトラヒック量を取得
2. 多⽬的進化的アルゴリズムに基づき，パレートフロントを導出
3. パレートフロントから⼀つをネットワークの設定として選択• 過去のパレートフロントを現在の解として使⽤することは不適• 各時刻パレートフロントの計算は⾼速に⾏うことが必要• その⼀⽅で全探索には時間を要する
𝒇𝟏

性能

トラヒック量𝒇𝟏

パレート最適解

以前のパレート最適解

パレート最適解劣解• １世代ごとの計算量の削減

性能に対する要件

トラヒック取得

1 2 3 4

パレートフロント導出
設定の投⼊2018/3/3

k時
刻性能の要件を満たしつつ消費電⼒が最⼩な設定を投⼊• 収束に要する世代数の削減

変動発⽣𝒇𝟐

適切なパレートフロント𝒇𝟐• 選択淘汰，突然変異の⼯夫• 進化させる初期解の⼯夫

消費電⼒• 前の時刻のパレートフロントを利⽤：変動が⼩さい場合は即座に対応• 進化を促進する解の導出：急激な変動が起きた場合にも対応→ Evolvability Search を導⼊

ネットワーク52018/3/3

61

2018/3/3

Osaka University

Osaka University

ネットワーク制御のための Evolvability Search

ES を⽤いた制御• Evolvability Search• Evolvability Search は並列実⾏[7]• 進化的アルゴリズムにおいて Evolvability の⾼い解を直接選択する⽅法• 定期的にパレートフロントを初期解として ES を計算• ⾼い Evolvability を持つ解は進化を促進• パレートフロントから離れない空間で ES を探索• 多⽬的進化的アルゴリズムでは保持した解で計算• 得られる解を Evolvable Solutions（ES）と呼ぶ• ネットワークにおける Evolvability• パレートフロントと ES を初期解とする• ES は進化により異なる環境に柔軟に対応することが望ましい• Evolvability：⼗分な回数の遺伝⼦操作により⽣成された個体のうち，異なる状況に対応可能な個体数に基づいて定義• どのフローがボトルネックリンクを経由するかを考慮して評価

多⽬的進化的アルゴリズム

パレートフロント

パレートフロント• ボトルネックリンクを流れるフローを他のリンクを経由できるよう変更→ 制約を満たした状態に遷移• フローを他のリンクに集約→ 省電⼒化を促進

更新

評価

更新
Evolvability[7] H. Mengistu, J. Lehman, and J. Clune, “Evolvability search: directly selecting for evolvability in order to study andproduce it,” in Proceedings of the 2016 on Genetic and Evolutionary Computation Conference, pp. 141–148, ACM, 2016.

7解の⽣成計算

Search2018/3/3

8Osaka UniversityEvolvability の遷移収束に要する世代数の評価• 評価環境• パレートフロントを初期解として ES を導出• トポロジ：Waxman モデルで⽣成• トラヒック：各通信ペアにおいてあらかじめ定義したトラヒック量内でランダムに⽣成• 設定した要件：最⼤リンク利⽤率が 0.5 以下で，２本の独⽴な経路を確保

Gene1
Gene2
Gene3

800

淘汰

時刻

Osaka University

900

ES

進化アルゴリズムの初期値ES

Evolvability が⾼ければフローを柔軟に集約・分散→ あらゆる環境で進化を促進する可能性
2018/3/3

計算

Evolvability

700600• ⽐較⼿法

500
400
300

少ない世代数でEvolvability は上昇

200
100
0020

4060

Number of generations

80100

⼿法名

計算に⽤いる解M ethod with Evolvable Solution（ w/ ES）

ES ， 前 の 時 刻 の パ レ ー ト フ ロ ン トM ethod with Random Solution（ w/ RS）

ランダム解，前の時刻のパレートフロント

M ethod without Evolvable Solution norRandom Solution（ w/o ESRS）

前の時刻のパレートフロント• 評価⽅法• w/o ESRS で⼗分進化させたパレートフロントを⽤意：変動前を統⼀• 同じ解に対してトラヒック変動を与え，（１）要件を満たした解への収束，（２）省電⼒解への収束に要する世代数を評価

１世代の計算には時間を要する⼀⽅で，ES は少ない世代数で導出可能→ 現実的な時間間隔で制御が可能
2018/3/3

92018/3/3

10

Osaka University

Osaka University

評価：要件を満たした解への収束

評価：省電⼒解への収束• 総トラヒック量が変化しなかった場合
w/o ESRS

11M ax111M in111• ES の導⼊によって収束に要する平均世代数は減少• ES の計算にかけた世代数の増加に伴い収束までの世代数は減少傾向• 50 世代以降の ES を⽤いた場合は平均世代数が上昇• ES の計算に要した世代数が⼤きすぎると，独⽴な経路などを考慮しない変異が積み重なった解が存在→ パレートフロントを⽣成する際に淘汰されてしまうことが多くなる• 総トラヒック量が２倍に変化した場合
w/ ESw/ RS

w/o ESRS

Avg.

3.93

2.93

3.96

M ax

14829

M in

1

11

収束に要した
平均
世
代
数

変動が⼤きかった場合にも 4 世代程度で収束可能→ 環境変動に追随した制御が可能
2018/3/3

11

2018/3/3w/ ES
w/ RS
w/o ESRS

200

1w/ ES(gen=10)
w/ RS
w/o ESRS

相0.8
補累 0.6
積分 0.4150CCDFw/ RS

1Avg. number of generations

w/ ES
Avg.

100

ES を含めても世代数をかけなければ収束できない場合が存在

布関 0.250数00020406080

Number
ESの 計 算ofにgenerations
か け た 世 代of数ES

1000100200300400500600700

収Number束 に 要ofしgenerations
た世代数

800

900

1000

122

2018/3/3

Osaka University

Osaka University

評価：省電⼒解への収束（総トラヒック量が２倍）

まとめと今後の課題• 収束に要する世代数は増加• まとめ• 適切なパレートフロントに対して前の時刻のパレートフロントはかけ離れている• 提案⼿法により，変動が⼤きい場合にも要件を満たした状態に収束可能であることを⽰した• 変動の⼤きさによって効果的な ES に差異• Evolvability Search の導⼊により，より少ない世代数で消費電⼒を削減できることを⽰した• 前の時刻のパレートフロントは収束には効果的に作⽤しない• ES においては前の時刻のパレートフロントへの近さよりもEvolvability の⾼さが進化の促進に作⽤

た
平均
世代
数

2018/3/3

w/ ESw/ RS
w/o ESRS

1200

Avg. number of generations

収束に要し• 今後の課題• 局所最適に陥り省電⼒状態に収束できない場合の改善⽅法の検討• ES の計算に要する世代数の決定⽅針の検討

保持したパレートフロントやES が同じでも効果的に作⽤する ES に差異

1000
800
600
400
200
0020406080

Numberof にgenerations
ESの計算
か け た 世of代ES
数

10013

2018/3/3

143