学籍番号
論文題目

1情報システム専攻 電子情報工学分野 (川原研究室)
10674005
氏名
岩村 幸歩
省電力経路制御におけるトポロジ情報を利用した削減対象リンク選択方式に関する研究

はじめに

150
BA
140130 Waxman
12011010090807060504030
20
10000.002

0.4

22.2 Steiner Tree を用いた選択方式
リンク削減において全ノードペア間の通信維持が前提条件となるが，これを満たす最小トポロジは全ノードペア間の SteinerTree(最小経路木) と等しくなる．そこで近似アルゴリズムである SCTF (Selective Closest Terminal First) を利用して Steiner
Tree トポロジを算出し，それ以外のリンクを一意に削減対象とする方式の省電力性能を調査し，提案方式と比較する．
2.3 リンク利用率を用いた選択方式
提案方式ではトポロジ構造から得られる重要度を指標に用いるが，実際のネットワークでは通信状況は動的に変化する．そのため，各ノード毎に接続リンクのトラヒック量増減を反映するリンク利用率を用いて，自律的に削減リンクを判断することが現実的であるため，各リンクの平均リンク利用率を指標に用いた場合の性能評価を行い，提案方式と比較して動的制御の方針を検討する．

断絶されるノードペア即ち孤立ノードが発生する．そこで，孤立ノード発生時点を電力削減の上限とすると，BA モデル (図中赤線 BA) で約 38 ％，Waxman モデル (図中青線 Waxman)で約 9.5 ％が最大電力削減率となり，提案方式は BA モデルにおいて省電力効果が高いことがわかる．
4.2 提案方式と Steiner Tree との性能比較
図 3 に，BA モデルにおける提案手法と Steiner Tree の転送性能を示す．NW トラヒック量 (図中 traf) は 0.1〜0.3 とする．
Steiner Tree では制御リンク数 196 本，電力削減率約 50 ％まで制御可能であるが，NW トラヒック量 0.2 の時のパケットロス率は約 26 ％となる．提案手法では，最大電力削減率は約 38％であるが，パケットロス率は約 5 ％に抑えられる．これは，提案手法では重要度の高い，即ち利用率の高いリンクは制御されにくいが，Steiner Tree では代替経路が存在した場合，リンク利用率に関わらず制御対象となるためである．
4.3 提案方式とリンク利用率を用いた選択方式の比較
図 4 より，BA モデルにおいてはリンク利用率を制御指標に用いると (図中緑線 Utilization)，電力削減率とパケットロス率共に提案方式 (図中赤線 Importance) と比較して性能が劣化する．そこで改善方式として，BA モデルにおいて高次数ノードの接続リンク程重要度が高いことから，リンク利用率にリンク接続ノードの次数和を反映させた以下の式で評価値を算出する．
評価値 = (リンク利用率) ∗ (リンク接続ノードの次数和)nシミュレーション

スケールフリーネットワーク (図 1 右) に BA(BarabasiAlbert) モデル，ランダムネットワーク (図 1 左) に Waxman
モデルを仮定し，ns-2 を用いたシミュレーションにより評価する．それぞれノード数 100，最低次数 2，平均次数 3.94，リンク帯域 100[Mbps] とする．トラヒックモデルは 1000[byte] のUDP パケットを 1[Mbps] の CBR で送信する．また，無制御時の平均リンク利用率をネットワーク (NW) トラヒック量と定義し，NW トラヒック量の影響を調査する．
性能評価指標として設定閾値に対する正規化制御可能リンク数を電力削減率と定義する．また転送性能は平均パケットロス率により評価する．

4

Power reduction ratio

省電力経路制御における削減リンク選択方式

2.1 リンク重要度を用いた選択方式 (提案方式)
全ノードペア間の転送を仮定し，各リンクにおける論理的なフローの重なり数である多重度を全ノードペア数で正規化した値を重要度と定義する．各リンクの重要度に対して閾値 α 以下のリンクを削減対象リンクとする．このとき非対象リンクのコストを 1，対象リンクのコストを 10 に設定してフローを迂回させ，低速度状態に移行することで省電力化を図る．

3

Packet loss ratio

Packet loss ratio

Nunber of links

0.3
近年，インターネットの普及拡大に伴うネットワーク機器の増加のため，省電力化は重要な課題である．その方法として，0.2あるフローの転送経路が複数存在することを仮定し，最短経路0.1
中に低利用率のリンクまたはルータが存在する場合，該当箇所を迂回して他経路を利用することにより低帯域化もしくは遮断00.004 0.006 0.008
0.01
Threshold alpha
することが有効である．しかしトラヒックは変動するため，該図 2: 提案方式の電力削減率
当リンク/ルータの特定は困難であり，トポロジ構造から一意
図 1: トポロジと次数分布
0.4
0.08
Utilization:traf0.2
ST:traf0.3に特定できることが望ましい．
ST:traf0.2
n=0.05:traf0.2
0.35
0.07
ST:traf0.1
Importance:traf0.2
traf0.3
Utilization:traf0.1
0.30.06
そこで本研究では，各リンクに対しトポロジ構造から決定すtraf0.2n=0.05:traf0.1
traf0.1
Importance:traf0.1
0.25
0.05
る重要度という指標を利用した削減対象リンク選択方式を提案
0.20.04
する．提案方式に対して各種トポロジにおけるリンク削減率の0.15
0.03
0.10.02
上限を明らかにし，転送トラヒック量がリンク削減率やパケッ
0.05
0.01
トロス率に及ぼす影響について調査する．さらに，各ルータの
00
0
0.1
0.2
0.3
0.4
0.5
00.1
0.2
0.3
0.4
Power reduction ratio
Power reduction ratio
接続リンクの利用率を基に，動的に対象リンクの設定・解除を行う省電力制御のための基本方針について明らかにする．
図 3: 性能比較 (Steiner Tree)
図 4: 性能比較 (利用率)

シミュレーション結果・考察

上式において n = 0.05 とした場合 (図中青線 n = 0.05)，重要度の性能とほぼ一致することから，接続リンクの利用率と次数情報を用いることで，各ノードが自律的に削減リンクを判断して動的に制御することが可能であることがわかる．

5

まとめ

本研究では，トポロジ情報を利用した経路集約のための削減リンク選択方式を提案し，Steiner Tree との性能比較より重要度を用いた経路集約が通信品質の劣化を抑制できることを示した．またリンク利用率を用いる方式を検討し，リンクの接続ノード次数を反映させることで各ノードが自律的に削減リンクを判断する動的制御が実現可能であることを示した．

研究業績
4.1 提案方式の電力削減効果[1] 岩村 幸歩 他，”省電力経路制御における削減対象リンク選
図 2 に閾値 α に対する電力削減率を示す．α を高くしていく択方式” 電子情報通信学会 ソサイエティ大会 Sept. 2011.と削減リンク本数も多くなるが，一定閾値以上になると通信がC-12