はじめに

リンク多重度/重要度
定義

nw 50%
nw 20%
00.02

0.04

0.06

0.08

10.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
00.1

until 100no remove
0importance

図 1: 重要度と利用率

loss rate2
2.1

utilization

ネットワークの大規模・複雑化により，リンク利用率やパケット廃棄率などのネットワーク特性の計測コストは増大する．そのため，トポロジ構造から得られる情報を用いて各ノードが自律的にネットワーク特性を推定できることが望ましい．本研究ではトポロジ情報としてリンク重要度に着目し，リンク利用率，パケットロス率との相関を調査し，特性推定への可能性を検討する．しかし，リンク重要度は全ノード間の最短経路を計算する必要があり，大規模ネットワークでは導出が困難なため，各ノードが局所的に接続リンクの重要度を求めるために，該当リンクの接続ノードの次数情報を用いる手法について提案する．

10.9
0.8
0.70.6
0.5
0.4
0.3
0.2
0.1
0correlation coeficient

1

情報システム専攻 電子情報工学分野 (川原研究室)
12674012
氏名近藤健司
ネットワークにおけるリンク重要度を用いた特性推定に関する研究

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
00.2

0.4

0.6

0.8

1

nw utilization

図 2: 平均利用率と相関係数

correlation coeficient

学籍番号
論文題目

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0log
product
リンク多重度は，全ノードペア間に転送フローが存在すること
linearsum-productnw 50%
sumを仮定した場合の各リンクにおける論理的なフローの重なり数を表
00.02
0.04
0.06
0.08
0.1
200
400
600
800
1000
す値であり，トポロジ構造から一意に決まる．さらに，この多重度
importancenumber of nodesを全ノードペア数で正規化した値を重要度とする．まず，重要度と 図 3: 重要度とパケットロス率
図 4: 評価値と重要度の相関係数
リンク利用率，パケットロス率の関係を調査し，重要度による特性より精度の高い推定のために，飽和リンクとなる最小重要度を推定の可能性を検討する．
調査した．平均リンク利用率を x とすると，最小重要度 y は，y ∝2.2 推定方式−1x の関係がある．図 2 の図中”until 100”より，飽和リンク最小リンク重要度はネットワークが大規模となると計算が困難になるが，該当リンクの周辺ノードの情報を用いて推定する手法の効果 重要度以下の標本を用いた場合，高い相関を示すため，平均リンクが示されている．ここでは局所情報として，該当リンクに接続され 利用率に対して飽和リンクの重要度の最小値を求め，その値まではるノードの次数を用いて推定する方法を提案する．以下に示す評価 線形分布，以降は飽和リンクであるというモデルでリンク利用率を推定可能であることがわかる．
値と実際のリンク重要度の相関を調査する．

5.2 重要度とパケットロス率の関係
・接続 2 ノードの次数を利用：和 (sum)，積 (product)
飽和リンクではパケットロスが発生する可能性があるため，重要・接続 2 ノード各々の隣接ノードの次数を利用：和積 (sum-product)
度の大きいリンクのパケットロス率の推定可能性を調査する．図 3
隣接ノード次数の総和の積 (ただし隣接ノード分は除く)に平均リンク利用率が 50%のときの重要度とパケットロス率の関
3 評価指標係を示す．この図からパケットロス率は分布が線形でないため，対3.1 相関係数
数回帰線 (log) と線形回帰線 (linear) を示す．決定係数はそれぞれ重要度と各特性との相関調査には，以下の相関係数を用いる． 0.80，0.64 となり，対数関数近似が有効であることがわかる．
Pn
重要度を用いてパケットロス率を推定するために，対数回帰曲線(xi − x̄)(yi − ȳ)
pPnr = pPn i=1(1) y = alog(x) + b の係数 a，b と平均リンク利用率 x との関係を調査(xi − x̄)2(y − ȳ)2i=1i=1 i
したところ，a，b ともに x に対して比例関係にあり，飽和リンクのパケットロス率は対数関数を用いて推定可能であることがわかる．
3.2

決定係数

5.3

接続次数を用いた重要度推定手法

まとめ

2 変数 (x，y) のデータ群において，説明変数 x で従属変数 y を局所的な情報を用いてリンク重要度を推定するため，ノードのどの程度説明できるかを示す値で，寄与率とも呼ばれる．標本値か接続次数を用いて重要度を推定する．ノード数は 100，500，1000
ら求めた回帰式 f のあてはまり度合いを表し，以下の式で示す．の 3 種類，各々のノード数で構成されるトポロジを 10 種類用意し，Pn22.2 の評価値とリンク重要度との相関を調査した．図 4 にノード数(y−f)ii(2)R2 = 1 − Pi=1ごとの各方式における評価値と重要度の相関係数を示す．次数積でn(y − ȳ)2i=1 i判定する場合が最大で 0.92 の高い相関係数を示し，ノード規模によらず重要度と高い相関があることがわかる．
4 シミュレーションモデル
和積で判定する場合は該当リンクから 2hop 先のノードまでの部
NS-2(Network Simulator-2) によるシミュレーションで評価する．
分ネットワークの次数情報を用いて推定したもので，ノード数を大ネットワークモデル:BA(Barabasi-Albert) モデルによるスケー きくすることでより推定精度は高くなると考えられるが，より局所ルフリーネットワーク，ノード数 100，最低次数 2，平均次数 3.94， 的な次数情報を用いた次数積が最も高い相関となった．
リンク帯域は 100[Mbps] とする．
次数積を用いて重要度を推定するために，近似直線の傾きを調
トラヒックモデル:1000[byte] の UDP パケットを全ノードが送信 査した．ノード数を N とするとこの傾き y は y ∝ log(N ) の関係し，宛先に選ぶノード数は 1〜100 とする．トラヒック量の指標と となり，この値を利用することで次数積によるリンク重要度が推定して平均リンク利用率を送信データ量/全帯域で定義する．
可能であることを示した．

5

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

6

5.1

重要度とリンク利用率の関係

本研究ではネットワークにおける各リンクの重要度とリンク利用率，パケットロス率との間の相関度合を調査し，推定の方法について明らかにした．さらにリンクに接続されているノードの次数から重要度を推定する方法を提案し，ノードが自律的に利用率，パケットロス率といった特性情報を推定できることを示した．

図 1 に平均リンク利用率が 20%(図中”nw20%”) と 50%(図中”nw50%”) の時の重要度とリンク利用率の関係を示す．この図から強い線形関係が見られることがわかる．ここで重要度が大きい
リンクは利用率が 100%となるが，これを飽和リンクと呼ぶ．図 2に平均リンク利用率に対する，全標本を利用した場合の相関係数 研究業績
(図中”no remove”)，飽和リンク中で重要度の最小値までの標本を近藤健司，川原憲治 ”次数情報を利用したリンク重要度推定およ用いた相関係数 (図中”until 100”) を示す．前者の線形回帰により， びネットワーク特性との相関調査”，IEICE NS/IN 研究会，2014
図 1 の係数は平均利用率が 30%の時 0.93，50%の時 0.75 となり強 年 3 月発表予定
い相関を示した．

B-1