提出日

平成 23 年 2 月 15 日

複数ルータのスパニングツリーを利用した省電力経路集約方式の性能評価
川原研究室07232025 川本 和樹
はじめに2

Link cut rate[%]3020100EAR
Proposal

1510501234567
Number of ERs

89100

図 3: リンク削減率0.2

経路集約手法

EAR アルゴリズム (既存手法)

20EAR
Proposal

40

ネットワーク中の各ルータは LSA (Link State Advertisement) により，同一のトポロジ情報を保持しているものとする．
両手法とも ER を選択し，切断リンクを決定し，LSA を用いて切断リンクのコスト変更を行ったトポロジ状態を通知して各ルータの OSPF の経路制御表を更新する．ER は次数の高いルータから順に選択され，複数設定する場合は隣接しないことを条件とする．

2.1

図 2: 提案手法

図 1: EAR アルゴリズム50EAR-Utilization
Proposal-Utilization
EAR-StandardDevitation
Proposal-StandardDevitation

0.15
Link utilization

102030
Link cut rate[%]4050

図 4: パケットロス率

Standard Devitation

インターネットの普及拡大に伴う消費電力の増加により，ネットワーク全体を考慮した省電力化手法が必要とされている．リ
ンク転送速度 x と消費電力 P が P ∝ x3 となるため，転送トラヒックの経路集約によるリンク (ルータ) の削減が考えられる．
経路制御プロトコル OSPF (Open Shortest Path First) をベースとしたリンクコスト変更による省電力経路集約手法として，代表ルータ (ER：Exporter Router) の隣接ルータ (IR：ImporterRouter) が ER のスパニングツリー (SPT：Shortest Path Tree)を用いて経路集約を行う EAR (Energy Aware Routing) アルゴリズムが提案されている．しかしこの手法では，ネットワーク規模が大きくなると ER に隣接しないルータが増加するため，経路集約により削減可能なリンクの割合 (リンク削減率) が低下すると考えられる．そこで本研究では，全てのルータが ERの SPT を利用して経路集約を行う手法を提案する．シミュレーションにより両手法の省電力性能と通信性能への影響を比較し，提案手法の有効性を検討する．

Packet loss rate[%]10.10.05

00102030
Link cut rate[%]4050

図 5: 平均リンク利用率と標準偏差4

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

ER の隣接ルータである IR のみが ER のスパニングツリー
図 3 に ER 数に対するリンク削減率を示す．既存手法 (図中を利用して経路集約を行う．経路集約の例を図 1 に，各 IR の動“EAR”) では，ER 数の増加に伴ってリンク削減率が増加する．
作を以下に示す．ルータ 0 を ER とし，その隣接ルータ 1，2，
これは，既存手法では各 ER に対して切断リンクとしたリンク
3，4 が IR となる．
1. LSA 情報を用いて ER をルートとした SPT を計算する (図 を全て切断するためである．しかし，IR が複数の ER を持たないという条件から，複数の ER に隣接している場合でも 1 つ中赤矢印)．
2. 計算した SPT において，自身と ER の間のリンクの向き の ER に対してのみ IR となるため，ER を増加させていくとを変更する (図中青矢印) ことで自身のルーティングツリー IR となるルータは減少する．そのため，切断リンク数が増加せず，リンク削減率が上昇しにくくなる．一方，提案手法 (図中MPT (Modified Path Tree) を作成する．
3. MPT を用いて転送する際，自身からの出線リンクのうち， “Proposal”) では各 ER の SPT に利用されないリンクのみを切転送に用いないリンクを切断リンクとする．例えばルータ 1 断するため，ER が増加すると転送に用いられるリンクが増加の場合，ルータ 5 へ向かうリンクが切断リンクとなる．
し，リンク削減率は低下する．両手法を比較すると，提案手法
ER を複数設定する場合，IR は複数の ER を持たないことを条の方が ER 数に対するリンク削減率の増減幅が大きいことがわ件とし，各 ER に対して IR が切断リンクとしたリンクを全てかる．
切断する．
両手法においてリンク削減率が同じ場合の通信性能への影響
2.2 提案手法
既存手法では IR のみが経路集約を行うため，ER 数に対す を調査するため，リンク削減率を横軸として図 4 にパケットロるリンク削減率が低い．また ER 同士が隣接せず，IR が複数の ス率，図 5 に平均リンク利用率 (図中 “Utilization”) とリンク
ER を持たないという条件から，ER を増加してもリンク削減率 利用率の標準偏差 (図中 “Standard Devitation”) を示す．図 4よりリンク削減率が等しい場合，提案手法の方がパケットロスが上昇しにくいと考えられる．
そこで提案手法では全てのルータが ER の SPT を利用して 率が低いことがわかる．また図 5 よりリンク利用率，標準偏差経路集約を行うよう変更する．提案手法による経路集約の例を ともに提案手法の方が低いことが確認できる．これは既存手法
図 2 に示す．全ルータが ER への経路を確保し，転送に用いな に比べて提案手法では利用率の高いリンクが少なく，負荷分散いリンクを切断する．例えば既存手法ではリンク削減を行わな されたためであり，その結果パケットロスが少なくなったもの
いルータ 5 も，ルータ 1 およびルータ 8 へ向かうリンクを切断 と考えられる．既存手法では代表ルータ ER の隣接ルータ IR がすることになる．ER を複数設定する場合，各 ER の SPT に利 出線リンクを切断し，ER を経由して転送するため ER 付近のリンクに負荷が集中する．一方提案手法では，ER の増加によ用されないリンクのみが切断される．
り，ER やその隣接ルータ付近のリンクを切断しにくくなるた
3 シミュレーション評価
め，ER 付近のリンクに負荷が集中しにくい．
ns-2 (Network Simulator version 2) を用いたシミュレーショ図 3 においてリンク削減率が同程度となる ER 数 3 の場合，ンにより評価する．
ERの接続リンクのうち平均利用率が 90%以上となるリンク本
トポロジモデルBA (Barabasi Albert) モデルにより生成したスケールフリー 数は既存手法が平均 5.7 本，提案手法が 4.0 本であり，提案手ネットワークを用いる．ノード数 100，最低次数 2，平均次数 法の方が利用率の高いリンクが少なく，負荷分散されているこ
3.94，各リンク帯域 100[Mbps] とし，全リンクコストを 1，切 とが確認できる．
以上より EAR アルゴリズムに比べ，提案手法ではパケット断リンクのコストを 10 として OSPF による経路制御を行う．
ロスを抑制したリンク削減が可能であることがわかる．
トラヒックモデル
全ノードがランダムに選択した複数の宛先ノードへパケット 5まとめ
サイズ 1000[Byte] の UDP トラヒックを送信レート 1[Mbps] の本研究では省電力化手法として，全てのルータが代表ルータ
CBR で送信する．のスパニングツリーを用いる経路集約手法を提案し，省電力性評価指標

省電力性能と通信性能の評価指標を以下に定義する．
× 100• 省電力性能：リンク削減率 = 削減リンク数
全リンク数
破棄パケット数
× 100• 通信性能：パケットロス率 = 送信パケット数

能と通信性能への影響から有効性を調査した．結果より，リンク削減率とパケットロス率の点から提案手法の有効性を示した．

C5-4