学籍番号
論文題目1

情報システム専攻 電子情報工学分野 (川原研究室)
12674034
氏名
柳 大地
複数ルータの最短経路木を利用した省電力経路制御方式の実現に関する研究

はじめに

インターネットの普及拡大に伴うネットワーク構成機器数，および消費電力量の増加に対処するため，ネットワーク全体の省電力化は急務である．この解決策として，転送トラヒックを特定リンク/ノードに集約し，転送に用いないリンク/ルータを低消費電力状態にすることが有効である．特定リンクの選択手法として，複数ルータの最短経路木を利用した省電力経路集約方式 (XEAR：eXtendedEAR)[1] が提案され，シミュレーションによりその有効性が確認されている．しかし，トラヒック変動に伴う高次数ルータ数の調整を含めた省電力経路制御方式としての実現可能性の検討が必要である．そこで本研究では，変動トラヒックに対して転送性能を維持した省電力化を可能にする複数ルータの最短経路木を利用した省電力経路制御方式の提案・実装を行うことを目的とする．

図 2: テストベッドネットワーク
65packet loss rate[%]2

図 1: XEAR の集約リンク

集約リンクの選択方式：XEAR[1]node0(ER:1)
node0(ER:2)
node3(ER:1)
node3(ER:2)

4
3

OSPF(Open Shortest Path First) によるルーティングを仮定
2
し，各ルータは LSA(Link State Advertisement) により，同一の1トポロジ情報を保持しているものとする．
次数 (接続リンク数) の高いものを代表として選択し (図 1：赤00.2
0.3
0.4
0.5
0.60.7ノード)，その最短経路木に利用されないリンクを削減リンクとす
link utilization
る (図 1：点線)．代表ルータ数が少ない場合，冗長性が低く，トラ
図 4: リンク利用率に対するパケッヒック変動により転送性能が劣化してしまうため，代表ルータは複 図 3: node0 のトラヒック量の推移 トロスの発生状況
数選択する．この場合，全ての代表ルータの最短経路木に利用され5530sec
XEAR
10secないリンクが削減対象となる．
proposal
5sec
3

4packet loss rate[%]

4XEAR に基づく省電力経路制御方式

packet loss rate[%]33

提案/実装する省電力経路制御のアルゴリズムを以下に示す．な22
お本方式において，代表ルータはトラヒック変動に伴って次数の高い順に複数選択され，同次数のルータがある場合は，ノード番号の11小さい順に選択される．
00i 経路切替判定
060 120 180 240 300 360 420 480 540 600
060 120 180 240 300 360 420 480 540 600
times[sec]times[sec]経路切替判定を行うために，代表ルータの持つリンクの利用率に閾値を設定する．この閾値には，代表ルータ数に応じた経路集約
図 5: XEAR と提案手法の比較
図 6: 経路切替判定周期の影響
後，パケットロスが発生しないリンク利用率の上限値を設定する．
切替判定時のリンク利用率が閾値未満の場合，その閾値に対応する は利用率 0.49 以上でパケットロスが発生している．次に node0 で代表ルータ数による経路集約を全ルータに指示し，閾値以上であ は，代表ルータ数 1 の集約 (node0(ER:1))，代表ルータ数 2 の集約ればリンク復旧を指示する．なお，切替判定は選ばれた全ての代表 (node0(ER:2)) ともに利用率が 0.65 以上でパケットロスが発生しルータにて行う．ている．これは，最初に選ばれる代表ルータには最もトラヒックがii リンクコスト変更
集中しやすく，代表ルータ数を増やしても他の代表ルータよりも早全ルータは受け取った指示内容 (経路集約/リンク復旧) に応じ く収容トラヒック量の限界に達してしまうことが原因であると考えて，以下の処理を実行する．
られる．したがって，node0 における切替閾値を 0.65，node3 にお経路集約：指示された代表ルータ数における経路集約によって削減 ける代表ルータ数 1 の切替閾値を 0.31，代表ルータ数 2 の切替閾対象となるリンクを算出し，コストを変更する．
値を 0.48 として制御を行う．具体的には，node0 の利用率が 0.65
リンク復旧：削減対象リンクコストを初期値に変更する．
未満において，node3 の利用率が 0.31 未満の場合には代表ルータiii 経路切替
数 1 の経路集約を行い，0.31 以上 0.48 未満なら代表ルータ数 2 のコスト変更後，全ルータは LSA により新トポロジを通知し，経 経路集約を行う．それ以外の場合においては，リンク復旧を行う．
路切替を行う．
5.3 変動トラヒックに対する提案手法の有効性

実験環境
XEAR による制御を行った場合 (XEAR) と提案手法を用いた場
テストベッドネットワーク：本実験のトポロジ構成を図 2 に示す．トラ 合 (proposal) におけるパケットロス率を比較した結果を図 5 に示
ヒック送信コマンド iperf を用いて，Senderi-Receiverj(1 ≤ i ≤ 3 す．XEAR では，一度経路集約を行うとその後も常に集約状態を，1 ≤ j ≤ 3) 間でトラヒック転送する．リンク速度は全て 100[Mbps] 維持したままとなるため，通信性能の劣化を抑制できず，図 5 にである．本実験において，代表ルータ数は 2 つまでとし，node0， おいてもトラヒックの増加に伴って通信性能が劣化してしまってい3 の順に選ばれる．
る．提案手法では，ロス発生後の経路切替判定においてリンク復旧
送信トラヒック：UDP トラヒックを 30 秒周期で 20，25，30，25， を行うことにより，通信性能の劣化を抑制できていることが確認で20，...[Mbps] と変動させながら 10 分間送信する．
きる．このことから，提案手法は先行研究に比べ，通信性能の劣化
評価指標：省電力性能/通信性能の評価指標を以下に示す．
を抑制した省電力経路制御が可能である．
• 省電力性能：リンク削減率 = 削減リンク数
× 100
5.4 経路切替判定周期の検討
全リンク数
経路切替判定周期を 5(5sec)，10(10sec)，30(30sec) 秒とした場
×100• 通信性能：パケットロス率 = 破棄パケット数
送信パケット数
合のパケットロス率を比較した結果を図 6 に示す．この図から，短5 実験結果/考察
い周期にした方が細かい制御を行うことができるが，5 秒間隔での5.1 経路切替時間の調査制御よりも 10 秒間隔での制御の方がパケットロスを抑えることがXEAR では，経路集約後のトポロジにおける特性等を検証して できている．これは，経路切替時間と同じ周期での切替判定を行うおり，経路切替に要する時間は考慮されていない．そこで，実装に ことにより，経路切替が完了する前に次の切替判定を行い，本来行おける経路切替時間を調査する．切替判定間隔 30 秒，切替閾値 0.5 うべきでない切替を行なってしまう可能性がでてくるためであるととして，代表ルータ数 1 の経路集約を行った場合の node0-8 間に 考えられる．よって，経路切替周期は経路切替時間より長い時間を流れるトラヒック量の推移を図 3 に示す．図 3 中の青丸で囲んだ とる必要がある．
部分に着目すると，30 秒周期のトラヒック変動後，さらに約 3〜4まとめ秒後にトラヒック量が変化している．これは，経路切替によるもの 6
本研究では，経路集約後の転送性能劣化の抑制のためのリンク復であり，このことから経路切替時間には約 3〜4 秒要することがわ
かる．この時間，コスト変更後の OSPF の経路再構築に要する時 旧も考慮した省電力経路制御方式の提案を行い，テストベッドネッ間であると考えられる．本実装では，実装上の誤差等も考慮して経 トワークにおける実装実験を通して，転送性能を維持した動的省電力経路制御が可能であることを示した．
路切替時間を 5 秒として制御を行なっていく．

45.2

経路切替閾値の調査

参考文献

代表ルータが切替判定に用いる切替閾値について調査する．代 [1] 川本 和樹，田村 瞳，川原 憲治，尾家 祐二， 最短経路木を利用
表ルータ数 1，2 の経路集約状態における，node0，3 でのトラヒッ
した省電力経路制御における集約ルータ/転送経路選択方式 ，ク量の変動に対するパケットロスの発生状況を図 4 に示す．まず，
信学技報 IN2012-149，Jan.2013
node3 では，代表ルータ数 1 の集約 (node3(ER:1)) においては利用率が 0.31 以上，代表ルータ数 2 の集約 (node3(ER:2)) においてB-3