時系列解析を用いた省電力ルーティング

(1)

2011 年度修士論文

時系列解析を用いた省電力ルーティング

提出日： 2012 年 1 月 31 日

指導：後藤滋樹教授

早稲田大学大学院基幹理工学研究科情報理工学専攻学籍番号： 5110B036-6

川口敬

(2)

図一覧

2.1 OSPFにおける経路制御の例. . . 8

2.2 作成されたSPT木 . . . 9

2.3 データベースが同期される例 . . . 11

3.1 トラフィックが輻輳している時. . . 13

3.2 トラフィックが少ない時 . . . 13

5.1 ネットワーク構成図 . . . 18

5.2 リンク利用率と通信のドロップ率の測定結果 . . . 18

5.3 arima(1,0,1)の場合 . . . 21

5.4 arima(5,0,5)の場合 . . . 21

5.5 arima(1,0,1)の場合 . . . 21

6.1 各リンクにおけるリンク利用率の時系列変化 . . . 23

6.2 Case1におけるリンク利用率の時系列変化 . . . 25

6.3 Case1における通信成功率の時系列変化 . . . 25

6.4 Case 2におけるリンク利用率の時系列変化 . . . 26

6.5 Case 2における通信成功率の時系列変化 . . . 27

6.6 Case 3におけるリンク利用率と集約時間 . . . 28

6.7 Case 3における通信成功率の時系列変化 . . . 29

(5)

表一覧

2.1 OSPFタイプ値 . . . 10

4.1 ARIMAモデルのパラメータ一覧 . . . 15

5.1 経路の変更が完了するまでの時間． . . . 19

5.2 パラメータpと予測誤差率の変化 . . . 20

5.3 パラメータqと予測誤差率の変化 (p=2) . . . 20

5.4 パラメータdと予測誤差率の変化 (p=2, q=1) . . . 20

6.1 実験環境の設定 . . . 22

6.2 Case1における集約時間と通信品質の結果 . . . 26

6.3 Case 2における集約時間と通信品質の結果 . . . 27

6.4 Case 3における集約時間と通信品質の結果 . . . 29

(6)

第 1 章序論

1.1 _{研究の背景}

インターネットのトラフィックが増大するとルータやスイッチなどのネットワーク機器の消費電力も増加する. これらはネットワーク全体における消費電力を増大させる. 文献[1] では, 機器の消費電力,回線・設備の状況を考慮し, かつネットワークの階層構造を加味した上でネットワーク全体における消費電力を算出している. これによると, 2011年時点で年間3.20TWh (32.0 億kWh)が消費されており, 2030年には年間17.49 TWh（174.9億kWh）が消費されると推定している. 消費電力を削減することは重要な課題である

一方で, 現在はネットワーク資源を効率的に利用するためトラフィックを分散させる技術が主流となっている. しかし,トラフィックの分散環境では,ネットワーク機器が常に稼働状態となり, 電力の消費が増大する. そこで, 分散されたトラフィックを一方の経路に集約することによりネットワーク機器をsleepもしくは部分的な稼働状態にして, 消費電力を削減する技術が研究されている. この方法では,トラフィックを集約しておく時間が長いほど, 必要となるネットワーク機器数を削減することができるため, 多くの消費電力を削減することができる. このことから, よりトラフィックの集約時間を長くする手法が求められる.

1.2 _{研究の目的}

本研究は, トラフィックを一方の経路に集約する時間を長くするということを目的としている. 具体的には時系列解析を用いてトラフィックの変動を予測し, その予測値を活用して経路集約を行う方法を提案する. 本論文では, OSPF (Open Shortest Path First) を用いてルーティングを行う環境下で, 3つのトラフィックケースに対して提案手法を適用する. その際, 集約時間や通信品質の観点から時系列解析を用いない場合との比較を行い,評価する.

(7)

第 1 章序論

1.3 本論文の構成

本論文は以下の章により構成される.

第1章序論

本研究の概要について述べる.

第3章 OSPFによるルーティング

OSPF環境下でのルーティングについて説明する.

第2章省電力ルーティング

省電力ルーティングの概要を紹介する.

第4章時系列解析

時系列解析と予測モデルについて述べる.

第5章提案手法と環境設定

提案手法の説明と予備実験を通じたパラメータ設定を検討する.

第6章実証実験

実験の内容の解説と結果の考察を行う.

第7章結論

まとめと今後の課題について述べる.

(8)

第 2 章

OSPF _{によるルーティング}

2.1 OSPF _の概要

OSPF (Open Shortest Path First)とはIGP (Interior Gateway Protocol)の一つで, AS内で利用されるルーティングプロトコルである. IGPにはRIPとOSPFの二つのルーティングプロトコルが良く使われており, RIPが距離ベクトルアルゴリズムを用いるのに対して, OSPFはリンクステートアルゴリズムを用いる. OSPFは主に一般企業やISPなどの内部ネットワークを制御するために採用されている.

2.1.1 RIP

RIP (Routing Informaton Protocol) とは, OSPFと同様にIGPの一つのルーティングプロトコルである. RIPでは最適なルートの選択を, 距離ベクトルアルゴリズムを用いて行っている.

これは送信元と宛先間で通過しなければならないネットワークのホップ数(メトリックと呼ばれる)をカウントし, メトリックが最少のものを最適なルートとして選択する. RIPは, 古くからあるプロトコルで多くのネットワークで使用されており, よく理解されているという点や実装が簡易であるという点がメリットとして挙げられる. しかし, その一方でホップ数のみから計算されるメトリックによりルーティングを行うため,遅延や負荷,信頼性などのリアルタイムのパラメータを考慮することはできない. そのため選択したルートが必ずしも最適なルートとは限らないという問題がある. また,サブネットとホストを識別できないため,可変長サブネットを利用できない点, 経路情報変更時にネットワークが安定するまでに非常に長い時間がかかるという点がRIPのデメリットである. なお, 現在では主にRIP2が使用されており, RIP2では可変調サブネットをサポートしている.

2.1.2 OSPFの特長

• IPを直接使用し, IPヘッダのプロトコルフィールドに独自の値を持つ

(9)

第 2 章 OSPFによるルーティング

• サブネットをサポートし,公告された経路のそれぞれにサブネットマスクを連携できる

• 経路情報が変更した際, ネットワークの安定までに要する時間が短い

• 同一コストの経路に対してトラフィックを分散できる

• TOS (Type Of Service) を基にして, 異なるコストをリンクに与えることができる

2.2 リンクステートアルゴリズム

OSPFの経路選択は, エリア内のすべてのOSPFルータやリンク状態に関する情報を持つ LSDB (Link State DataBase) から計算される. LSDBはリンクの状態を広告するLSA (Link

State Advertisement) のやりとりによって共有される. 複数の経路が存在する場合, OSPFは

あて先に到達するまでに通過するルータのコストの合計を計算し,最小のコスト値を最適な経路として選択する. このコストは主にインターフェースの帯域幅によって決定される. また,複数の経路に対して同一のコスト値が設定されている場合, トラフィックは均等に分散される.

2.3 OSPF における経路制御

2.3.1 SPTの作成

Dijkstraアルゴリズムを用いて最短経路を示すSPT (Shortest Path Tree) を作成する. 宛先までのコスト値はルータの出力インターフェースに設定されているコスト値によって決定される.

図 2.1: OSPFにおける経路制御の例

(10)

1. R1はコスト10でN1とN2に到達することができる.

2. N1には先に枝がないため, N2上のR2, R3に至ることができる.

3. 次に探索する候補はR5とR4になるが, R4のほうが,コストが小さいため先に計算する.

4. R5に対して, R2からの経路はコスト30, R4からの経路はコスト20となるので, R4から

の経路を最短とする.

5. 以下のSPTを作成する

図 2.2: 作成されたSPT木

2.3.2 ルーティングテーブルの作成

上で作成したSPTからR1のルーティングテーブルを作成する. 各ルータは自分が根となる SPTからルーティングテーブルを作成する. 各ルータは同一のトポロジーから経路を計算するため, トポロジー情報の同期が必要となる. OSPFではLSAの集合でネットワークトポロジーを記述し,ネットワーク上のすべてのルータに情報を伝搬する. 各ルータはLSAに含まれた情報に基づいて, LSDBを作成する.

2.4 _{データベースの同期}

2.4.1 関連用語の説明

データベース記述(DD)パケットルータ間で交換されるパケットであり, 到達可能なネットワークとルータの要約情報をもつ. ルータが自分のデータベースを更新する際に利用する.

(11)

リンク状態要求 (LSR) DDパケットの交換により決定したデータベース更新に必要な追加情報を要求する際に, ルータが使用するパケット.

リンク状態更新 (LSU) いくつかのLSAによって構成され,リンク状態要求に対する応答として送られる.

リンク状態広告 (LSA) データベース作成の基となる情報. そのルータに接続されたネットワークの情報やインターフェースのコストなどの情報が含まれている.

2.4.2 OSPFのタイプ値

以下, OSPFで用いられる各パケットを識別するためのタイプ値を示す. このタイプ値が OSPFのパケットヘッダに挿入される.

表 2.1: OSPFタイプ値タイプコード説明

1 Hello

2 データベース記述 3 リンク状態要求 4 リンク状態更新 5 リンク状態応答確認

2.4.3 Helloプロトコル

Helloプロトコルは, 隣接関係の形成とルータの障害検知に利用される. OSPFルータは起動

と同時にHelloパケットを送出し, ネットワーク上の他のルータに自身が利用可能であること

を伝える. Helloパケットを受け取ったルータは自分の存在を知らせるHelloパケットを返答する. その後,隣接ルータとデータベースの同期をとることで隣接関係が成立する.

Helloプロトコルは隣接関係が成立した後にも利用される. 各ルータは定期的に (Helloイン

ターバル毎に) Helloパケットを送出しており, その返答を受け取ることで隣接ルータの生存確認を行う. ルータがダウンしたとみなすDeadインターバル時間が経過するまでにHelloパケットを受け取らなければ, その隣接ルータはダウンしているとみなされ, トポロジーが変更される.

(12)

2.4.4 隣接ルータのデータベースが同期されるまでの手順

各OSPFルータが最適な経路計算を行うには, ルータ間でLSDBを同期させることが重要である. 以下にLSDBが同期される手順を示す.

図 2.3: データベースが同期される例

1. R2が起動し, Helloパケットのやりとりが行われることで, R2がR1を確認する

2. データベース記述 (DD) パケットのやりとりを行う

3. データベースを最新情報隊に保つため, ルータがリンク状態要求 (LSR) を作成する

4. LSRを受信し,応答として要求されたリンク状態広告 (LSU)が含まれるリンク状態更新

(LSU)パケットを送信する

5. 両ルータが同一のデータベースを持ち, 隣接関係として成立する

このようにして各OSPFルータ間のLSDBが同期され, トポロジー情報を共有することができる.

(13)

第 3 章

省電力ルーティング

3.1 _{グリーンネットワーク}

インターネットトラフィックの急増に伴って, ネットワークにおける消費電力が増大し, 将来的にも飛躍的に増大することが予測されている. ネットワークにおける消費電力削減には, ネットワーク機器に対する設備投資の抑制, ネットワーク全体での電力消費の効率化というアプローチがある. 前者は,ネットワーク上に流れるトラフィックを抑制することによってネットワーク機器数を減らし,消費電力の削減を達成するものである. 一方後者は, トラフィックの転送にかかる消費電力や, トラフィックの変動を利用した工夫を行うことで, ネットワーク全体の消費電力を削減するというものである.

3.2 _{省電力スイッチング}

ネットワークを構成しているルータでは,パケットを転送するルーティング処理が,消費電力の約4割を占めている. ルータのパケットバッファやルーティングテーブルの排除により,ルーティング処理を軽量化した新たなスイッチング方式を省電力(ECO)スイッチングと呼ぶ.

省電力スイッチングでは, バッファレス方式と擬似タイムスロットを用いる. バッファレス方式とは, ルータにおいてパケットの衝突を防ぐために行われるバッファリング処理を排除することである. バッファレスなルーティング処理において,擬似タイムスロットを用いてパケットの送出を適切にスケジューリングする事でパケットの衝突を防ぐ. また, 擬似タイムスロットを識別し, 時間軸上でスイッチングを行うことで, ルーティング処理におけるルーティングテーブルの参照しないためテーブルの検索エンジンを必要としない. ルータではバッファリング, ルーティングの過程で消費電力の大きな特殊メモリを必要とするが, ルーティング処理を軽量化することで, 必要な消費電力が削減され, 省電力を実現できる.

(14)

第 3 章省電力ルーティング

3.3 省電力ルーティング

トラフィックの経路制御を行う目的は, 主に負荷を分散させることでサーバへの負担を軽減させることやネットワーク資源を有効活用することにある. しかし, 省電力という観点では,トラフィックが分散されることで,ルータやスイッチなどのネットワーク機器が常時稼働していなければならず, 多くの電力を消費する. しかし,一般的に休日や深夜の時間帯などはトラフィックが少なく, 必ずしもトラフィックの分散を必要としない. このようなトラフィックの少ないときに,分散されたトラフィックを一方の経路に集約し, ネットワーク機器をsleep状態もしくは部分稼働状態にすることで消費電力の削減を達成する技術を省電力(ECO)ルーティングと呼ぶ.

以下の図3.1と図3.2はトラフィックが輻輳している時とトラフィックが少ないときのそれぞれのルーティングの様子を表した図である. 図中の矢印はトラフィックの流れを示す.

図 3.1: トラフィックが輻輳している時

図 3.2: トラフィックが少ない時

(15)

第 4 章時系列解析

4.1 _{時系列解析データ}

時系列データとは, 時間とともに変化する値を時間の順序で観測したものである. 一般的には, 医療データや気象データ, 株価および為替レートのような経済データにおいて活用されている. この時系列データを用いて, 変動や特徴を統計的に分析し, 将来の値を予測, 制御する方法論が時系列解析である.

4.2 _{時系列解析モデル}

本論文では時系列解析における主なモデルとして, ARモデル, MAモデル, ARMAモデル,

ARIMAモデルを紹介する.

4.2.1 ARモデル

時点(t−p)からtまでの各時系列データの関係式が, ある時系列時点の値y_tとホワイトノイズe_tを用いて

y_t=

∑p

i=1

a_i∗y_t₋_i+e_t (4.1)

で表せるとき, このモデルをp次の自己回帰モデルもしくはAR (AutoregRession)モデルと呼ぶ. つまりp個過去の値の加重和に誤差を加えたものであり, p個過去の時点からの値の変動を関係式として表現したものである. p次の自己回帰モデルをAR(p)で表す. ARモデルを当てはめる方法としては, ユールウォーカー(Yule-Walker)法,最小二乗法,バーグ(Burg)法などが提案されている. 本論文では, ユールウォーカー法を適用した.

(16)

第 4 章時系列解析

4.2.2 MAモデル

時点(t−q)からtまでの各時系列データの関係式が, ある時系列時点の値y_tを用いて y_t=

∑q

j=1

b_j ∗e_t₋_j (4.2)

と表せるとき,このモデルをq次の移動平均モデルもしくはMA (Moving Average)モデルと呼ぶ. q次の移動平均モデルをMA(q)で表す. 次に説明するARMAモデルにおいて, 移動平均モデルが活用される.

4.2.3 ARMAモデル

上で説明した自己回帰モデル∑_p

i=1a_i∗y_t₋_i +e_tに誤差の移動平均である∑_q

j=1b_j ∗e_t₋_j を加え

y_t =

∑p

i=1

a_i∗y_t₋_i+e_t+

∑q

j=1

b_j∗e_t₋_j (4.3)

として表すことのできるモデルを自己回帰移動平均モデルもしくはARMA (AutoregRessive

Moving Average)モデルと呼ぶ. 自己回帰移動平均モデルは自己回帰モデルの次数pと移動平

均モデルの次数qを用いてARMA(p,q)で表す.

4.2.4 ARIMAモデル

自己回帰移動平均y_tのd階の差分y_t−y_t₋₁がARMA過程となるとき,このモデルを自己回帰和分移動平均モデルもしくはARIMA (AutoregRessive Integrated Moving Average)モデルと呼ぶ. 自己回帰和分移動平均モデルをARIMA(p,d,q)で表す. 非定常な時系列データに対し, 時系列データの階差をとることで, 定常化を行う. ARIMA(p,d,q)について, 特にd = 0のと

きARMA(p,q)となる. ARIMAモデルを用いる際の各パラメータp, d, qについて以下にまと

める.

表 4.1: ARIMAモデルのパラメータ一覧

パラメータ説明

p ARの次数

d 階差の次数

d MAの次数

(17)

第 4 章時系列解析

4.3 パラメータの推定方法

各時系列モデルを決定するにあたって, モデルが持つパラメータの推定を行うことが必要である. 本研究では,後に第5章で述べるパラメータの決定方法について,直感的な予測の精度を重視したため予測誤差率を用いた. 一方で,一般的なパラメータの設定方法としてAICと呼ばれる手法がある. 以下で, 本研究で用いた予測誤差率と, AICについて紹介する.

4.3.1 予測誤差率

本研究では, パラメータを決定する際に, この予測誤差率がもっとも小さくなるパラメータを選定した. 予測誤差率の算出方法を以下に示す.

予測誤差率(%) = |(測定値) - (予測値)|

(測定値) ∗100 (4.4)

4.3.2 AIC

赤池情報量基準と呼ばれ, モデルを決定する手法の一つとして用いられる. AICは, 最尤推定量とパラメータ数を考慮して算出される. この結果がもっとも小さくなるパラメータを最適なモデルとして選定する. AICの算出方法を以下に示す. Mはモデル, MLLは最大対数尤度, k はパラメータ数をそれぞれ示す.

AIC (M) =−2∗M LL(M) + 2∗k (4.5)

(18)

第 5 章

提案手法と環境設定

この章では, 提案手法の概要と本研究で想定する環境設定を予備実験の結果を用いて行う.

5.1 提案手法の概要

本研究の提案は, トラフィックの傾向を時系列解析によって予測し, 省電力ルーティングに適用することである. 具体的には, トラフィックが少なくなると予測されたときに分散から集約への移行を行い, トラフィックが輻輳すると予測されたときに集約から分散へと移行する. また, 分散時と集約時でパラメータを切り替えて設定することで, 集約に対してより早く判断し, さらに集約時のバーストトラフィックへの反応回避を可能にする.

5.2 想定するネットワーク環境

本研究では, 一定時間ごとにトラフィックを監視し, 閾値にしたがって集約と分散を行う. 実験には, 仮想環境上に図5.1のネットワークを構築した. 各ルータR1〜R4で表し, トラフィックはクライアントCL1〜2からサーバSVに向かう. ルーティングプロトコルにはOSPFを使用し,各ルートに等コストを設定することでトラフィックの分散環境を用意した.

図5.1の観測点においてSNMPを用いてトラフィック情報を取得する. また設定した閾値にしたがいルーティングテーブルの書き換え, および経路変更を行う.

(19)

第 5 章提案手法と環境設定

図 5.1: ネットワーク構成図

5.3 集約と分散に用いる閾値の設定

平均リンク利用率から閾値を決定する. 100Mbpsのリンクにおいて, トラフィックの帯域幅を増加させていった際のリンク利用率と通信のドロップ率の関係を測定したところ図5.2のような結果を得た.

図 5.2: リンク利用率と通信のドロップ率の測定結果

この図より50%というリンク利用率に達すると通信の劣化が見られた.また文献[2]では,年

率およそ30%の割合でトラフィックが増大していると報告されている.これらから,回線を5年

間運用することを想定すると, 平均リンク利用率を50÷1.3⁵ ; 13(%)と算出できる. よって

(20)

と判断するLink-Aのリンク利用率の閾値を13%の1/2である6.5%に, 分散と判断する閾値を 13%とした.

5.4 トラフィックの監視間隔

OSPFにおいて, ルーティングテーブルの変更が反映され, 経路が切り替わるまでの時間からトラフィックの監視間隔を決定する.経路の移行処理の際に,処理が開始し集約の対象となる通信が途切れてから, 再び疎通が確認できるまでの時間を測定した. 10回測定を行った結果を表5.1に示す. 分散から集約への移行に最大18秒, 集約から分散への移行に最大25秒を要したことから, トラフィックの監視間隔を30秒とした.

表 5.1: 経路の変更が完了するまでの時間．

Avg (sec) Max (sec) Min (sec) トラフィックの集約 12.3 18.0 9.0 トラフィックの分散 20.6 25.0 12.0

5.5 予測モデルのパラメータ設定

本研究では,時系列解析モデルとして,第4章で説明したARIMAモデルを用いる. このモデ

ルarima(p,d,q)を用いるにあたって, パラメータp, d, qを設定する必要がある. ここでは以下

の点に着目し,パラメータの設定を行った.

分散時予測の精度が高いパラメータを設定する

集約時時系列データの急な増大に対して反応しないパラメータを設定する

5.5.1 分散時のパラメータ

トラフィックが分散されている,つまりトラフィックの多い時には,予測の精度を予測誤差率から評価し, 予測誤差率がもっとも小さいパラメータを選定する. 予測誤差率については第4 章で示した式4.4を用いる.

輻輳状態から減少するトラフィックに対して予測モデルを適用し, 各パラメータを変化させながら予測誤差率を算出した. 予測誤差率は, 30秒ごとにトラフィックを監視することによって得られる10個の測定値と予測値のデータから予測誤差率を算出し, その平均の値を用いた.

解析に用いる時系列データは10個とし, ARの次数であるパラメータpは, 0< p≤10の範囲

(21)

で設定する. まずq = 0, d = 0とし, パラメータpについてpを変化させたときの予測誤差率の値を表5.2に示す.

表 5.2: パラメータpと予測誤差率の変化パラメータpの値 2 5 8 予測誤差率 (%) 1.115 1.367 6.319

表5.2より,p= 2の時にもっとも予測誤差率が小さくなることから, pの値には2を適用する.

次にMAの次数であるパラメータqの値を設定する. p= 2としてqの値を変化させたときの予測誤差率の値を表5.3に示す. ここでパラメータqは, 0≤q≤2の範囲で設定する.

表 5.3: パラメータqと予測誤差率の変化 (p=2) パラメータqの値 0 1 2 予測誤差率 (%) 1.115 0.475 0.965

表5.2より, q = 1でもっとも予測誤差率が小さくなるため, パラメータqの値には1を採用する.

最後に階差の次数であるパラメータdの設定を行う. dは0≤d≤2の範囲で設定する. p= 2, q= 1を設定し, dを変化させた際の予測誤差率を表5.4に示す.

表 5.4: パラメータdと予測誤差率の変化 (p=2, q=1) パラメータdの値 0 1 2 予測誤差率 (%) 0.475 0.412 0.919 表5.4より,d= 1をパラメータとして採用した.

これらから, arima(2,1,1)が予測誤差率のもっとも小さくなるパラメータであるとした. また,

arima(2,1,1)におけるAICの値の平均は−25.4であり, 十分に小さい値である. したがって,ト

ラフィックが分散されている環境下におけるARIMAモデルのパラメータとしてarima(2,1,1) というモデル設定を行う.

5.5.2 集約時のパラメータ

トラフィックが集約されている,つまりトラフィックの少ない時には, 時系列データの急な増大に対して予測データが追随しないパラメータを設定する. ここで, 時系列データの急な増大として, 平均リンク利用率6.5%以下から分散の閾値13%を超えるデータをバーストであると想

(22)

予測結果を示している. 図中のプロットが予測データ, それより以前のデータが学習用の時系列データのサンプルであり, サンプル中に上で述べたバーストを混ぜた際の予測の様子を表している.

図 5.3: arima(1,0,1)の場合図 5.4: arima(5,0,5)の場合

図 5.3と図 5.4 より, ARとMA の次数が高く, より過去の情報から学習するパラメータ

arima(5,0,5)については, 時系列データの急な増大に対して予測データが反応していること

がわかる. その一方で, 過去のデータの参照を最小限にするarima(1,0,1)では,時系列データの急な増大に対する反応を回避している.

図5.3は, arima(1,0,1)について時系列データの最後にバーストを混ぜた際の予測の様子を示している. この例でも予測データは, 時系列データの急な増大に対する反応していない. これらから,トラフィックが集約されている時の予測モデルのパラメータとして, arima(1,0,1)を設定する.

図 5.5: arima(1,0,1)の場合

(23)

第 6 章実証実験

6.1 _{実験の目的}

本実験の目的は, トラフィックの変動に応じて動的に経路制御を行う処理を実現するとともに, 時系列解析を用いたトラフィック予測を行うことによる集約時間,通信品質を評価することである.

6.2 実験の環境

第5章で述べた環境を適用する. ネットワークの構成は図5.1と同様である. その他の環境設定について,以下にまとめる.

表 6.1: 実験環境の設定

項目設定

リンク利用率の閾値(集約) 6.5%

リンク利用率の閾値(分散) 13%

トラフィックの監視間隔と予測先の秒数 30sec 予測モデルのパラメータ(分散時) arima(2,1,1) 予測モデルのパラメータ(集約時) arima(1,0,1)

6.3 トラフィックの集約と分散

本研究では, トラフィックを集約することで, 図5.1のR2にトラフィックを集中させることを想定する. R1において, Link-A, Link-B, Link-Cそれぞれのトラフィックを, SNMPを用い

(24)

第 6章実証実験

て取得する. トラフィックの変動に応じて動的に経路制御を行う際のLink-A, Link-B, Link-C を流れるトラフィックの様子を以下の図6.1に示す. ここではトラフィックの減少と経路の集約について各リンクのリンク利用率の時系列変化を示した. グラフの左縦軸はLink-Aのリンク利用率を, 右縦軸はLink-BとLink-Cのリンク利用率を表す.

図 6.1: 各リンクにおけるリンク利用率の時系列変化

図6.1より, 6.5%に達した時点からLink-Cのリンク利用率は大きく減少している. R2を通る経路のみが有効となり, Link-Cにトラフィックが流れなくなるためである. 一方で, Link-B は経路が集約されることで一時的にリンク利用率が上昇している. また全体のトラフィック量

を示すLink-Aのリンク利用率は,パケットのドロップが発生するために経路の切り替えを行う

際に一時的にリンク利用率が落ちる.

これらのリンク利用率の変化の様子からトラフィックがR2を通る経路, つまりLink-Bに集約されているということが分かる.

(25)

6.4 本実験

時系列解析を用いたトラフィック予測を行うことによる集約時間, 通信品質を評価する. また予測を用いない場合との比較を行う.

以下に示す3つのテストケースを想定したトラフィックを生成し, 実験を行った. 本研究では, 通信成功率をパケットのドロップ率から算出することにより通信品質を評価する. そのため, 本実験ではiperfを用いたUDPトラフィックを用いてトラフィックケースを生成した.

Case 1 分散から集約に向かう減少トラフィック Case 2 集約時にバーストが発生するトラフィック Case 3 集約から分散に向かう上昇トラフィック

6.5 実験結果

予測を用いる手法を提案手法, 用いない手法を従来手法として, 各Caseにおけるトラフィックの集約時間を示す. また,経路変更の発生による通信への影響を評価するため, 経路変更時の通信成功率を通信のドロップ率から算出し, 結果を示す.

6.5.1 Case 1における結果リンク利用率の変化と集約時間

Case 1におけるリンク利用率の時系列変化と集約時間について, 測定結果のグラフを図6.2

に示す.

リンク利用率の変化と通信品質

Case 1におけるリンク利用率の時系列変化と通信成功率について,測定結果のグラフを図6.3

に示す.

(26)

図 6.2: Case1におけるリンク利用率の時系列変化

図 6.3: Case1における通信成功率の時系列変化

(27)

結果に対する考察

図6.2と図6.3から得られる集約時間とトラフィックの集約による経路変更時の通信成功率を以下の表6.2に示す.

表 6.2: Case1における集約時間と通信品質の結果

提案従来集約時間 172sec 148sec 通信品質 43% 50%

図6.2および表6.2より,集約が早く行われることで,集約時間を長くすることに成功した.また図6.3と表6.2の通信成功率の評価から, 通信品質は従来とほぼ同様の値であり,集約を早めたことによる通信品質への影響はあまり見られないという結果を得た.

に示す.

図 6.4: Case 2におけるリンク利用率の時系列変化

(28)

に示す.

図 6.5: Case 2における通信成功率の時系列変化

図6.4と図6.5から得られる集約時間と経路変更時の通信成功率を以下の表6.3に示す. 表 6.3内の通信成功率については, トラフィックの分散に影響した通信成功率の値を記載した.

表 6.3: Case 2における集約時間と通信品質の結果

提案従来

集約時間 300sec 237sec

通信成功率 – 1%

図6.4より,予測データがバーストトラフィックに対しては反応しないため,急激なトラフィックの増大によって発生し得る分散, 集約の処理を回避できる.通信品質については, 図6.5より従来手法ではトラフィックのバーストによって大きく通信品質を損なうことが分かる.

(29)

に示す.

図 6.6: Case 3におけるリンク利用率と集約時間

に示す.

(30)

図 6.7: Case 3における通信成功率の時系列変化

図6.6と図6.7から得られる集約時間とトラフィックの分散による経路変更時の通信成功率を以下の表6.4に示す.

表 6.4: Case 3における集約時間と通信品質の結果

提案従来

集約時間 417sec 385sec

通信成功率 64% 71%

図6.6より,予測の精度が落ちるため, 予測を用いない場合と比較して, 提案はやや遅く分散に移行する. そのため集約時間という観点では,従来手法よりも長くなるという結果を得た. その一方で通信品質については, 従来手法よりもトラフィックがより輻輳した状態で分散に移行するため, より多くのパケットのドロップが発生してしまうことが考えられる. しかし表6.4内の通信成功率より,通信成功率の大きな変化はなく,通信品質への影響はごくわずかである. つまり,通信品質に悪影響を及ぼすことなく提案手法が適用できることが分かる.

(31)

第 7 章結論

7.1 _まとめ

本研究では, 時系列解析によるトラフィックの予測値を用いて経路の切り替えを行うことで, トラフィックを一方の経路に集約する時間を長くする手法を提案した. 3つのトラフィックケースについて実験を行った結果, 時系列解析を用いて予測を行うことにより, 通信品質の劣化を防ぎながら, 集約時間を長くできることを示した.

7.2 _{今後の課題}

以下では本研究における今後の課題を述べる.

7.2.1 実環境における評価

本論文では, 3つのトラフィックケースに基づいて実験と評価を行ったが, 実環境で流れるトラフィックに対しては評価を行っていない. 実環境で本研究を適用するには実トラフィックに対する評価を行う必要がある.

7.2.2 他の予測モデルの検討

本研究では時系列解析の予測モデルとしてARIMAモデル (パラメータによってはARMA モデル)を適用して, 実験を行った. 一方で, 学習データを用いて予測を行うモデルはその他にも多く研究されている. 他のモデルとの比較を行うことで, より最適なモデルの選定を行っていくことが必要である. また,モデルの決定という点では, パラメータの設定方法の検討も重要である. ネットワーク環境によって最適なパラメータを検討し設定する必要がある.

(32)

第 7 章結論

7.2.3 実際の消費電力の評価

本研究では, 集約時間という点に着目したが, 実際の消費電力を評価するという点に到っていない. 集約時間を延ばすことによって, ネットワーク上の消費電力をどの程度削減できるかという点については今後評価を行っていく必要がある.

(33)

謝辞

本卒業論文の作成にあたり日頃より御指導を頂いた早稲田大学理工学部の後藤滋樹教授に深く感謝致します. また, 研究を進めるにあたって貴重なアドバイスをくださった下田晃弘氏, 持永大氏に感謝致します. 最後に, 多くの御協力を頂きました後藤研究室の諸氏に感謝いたします.

(34)

参考文献

[1] 持永大, 小林克志, 工藤知宏, 村瀬一郎, 後藤滋樹, インターネット上のコンテンツ分布を考慮した光回線交換方式およびCDN方式の採用による省電力化の評価, 電子情報通信学会論文誌B, Vol.J94-B, No.10, pp.1293–1302, 2011.

[2] Kenjiro Cho, Kensuke Fukuda, Hiroshi Esaki, Akira Kato, Observing Slow Crustal Move- ment in Residential User Traﬃc, ACM CoNEXT2008, pp.1–12, Madrid, Spain, 2008.

[3] Pulak Chowdhury, Energy Eﬃciency in Telecom Optical Networks, Workshop on Energy Eﬃcient Networking and System Photonics in Switching, July 25, 2010.

[4] 掛水光明,中後明, グリーンネットワークへ向けた取り組み, FUJITSU. 60, 4, pp.311–335, 07, 2009.

[5] Mingui Zhang, Cheng Yi, Bin Liu, Beichuan Zhang, GreenTE: Power-Aware Traﬁc En- ginering, IEEE International Conferece on Network Protocols, pp.21–30, 2010.

[6] 警察庁技術対策課, 我が国におけるインターネット治安情勢について, 2004.

[7] 秋岡明香, 村岡洋一,グリッド環境でのCPU負荷予測に基づくネットワーク負荷中期予測, 電子情報通信学会論文誌D–I, vol. j87–D–I No.9 pp.845–854, 09, 2004.

[8] Rich Wolski, Dynamically forecasting network performance using the Network Wether Service, Computer Science and Ewngineering Department, University of California, San Diego, La Jolla CA 92093–0114, USA, pp.119–132, 1998.

[9] Peter J.B rockwell, Richard A.Davis 著, 時系列解析と予測, シーエーピー出版, 2004.

[10] 田中孝文著, Rによる時系列分析入門, シーエーピー出版, 2008.

[11] 金明哲著, Rによるデータサイエンス, 森北出版, 2010.

[12] 福地純一郎, 時系列解析入門, 学習院大学, 2002.

(35)

参考文献

[13] 寺本翼, 原元司, ベイズ推定を用いた負荷分散ルーティングに関する研究, FIT2010, 第9 回情報科学技術フォーラム, pp.187–188, 2010.

[14] Philip Miller, 苅田幸雄訳, マスタリングTCP/IP 応用編, オーム社, 2005.

[15] W.Richard Stevens, 井上尚司監訳, 橘康雄訳,詳解TCP/IPプロトコル,ピアソン・エデュケーション, 2004.

[16] アラクサラ, ダイナミック省電力技術, http://www.alaxala.com/jp/solution/

environment/dynamic.html

[17] Rodney S.Tucker, Jayant Baliga, Robert Ayre, Kerry Hinton, Wayne V.Sorin, Energy Consumption in IP Networks, ARC Special Research Centre for Ultra-Broadband Infor- mation Networks University of Melbourne, 2008.

時系列解析を用いた省電力ルーティング

2011 年度 修士論文