マルチキャスト通信における𝑳𝟏 ノルム最小化によるパケット損失率推定法とパスの選択法
長岡技術科学大学

大学院工学研究科
吉川泰司
中川健治
渡部康平

Laboratory of Network Performance Evaluation

1

研究背景
通信事業において，ネットワーク内部状態の把握は重要
内部状態にはパケット損失率，遅延などがある
本研究ではネットワークの輻輳の最も直接的な指標であるパケット損失率に注目
内部状態を把握する手法は複数存在するが，いずれも計測精度とネットワークの負荷にトレードオフの関係がある

Laboratory of Network Performance Evaluation

2

計測手法
アクティブ計測・計測用のプローブパケットを用いる手法
・プローブパケットを送出し，ネットワーク特性を計測・計測精度とネットワーク負荷にトレードオフの関係

計測端末

計測端末

：ユーザーパケット：プローブパケット
Laboratory of Network Performance Evaluation

3

計測手法
アクティブ計測
パケット損失率𝒏𝑹

𝒍=𝟏−𝒏

プローブパケットを𝒏𝑺 個送信𝑺

プローブパケットを𝒏𝑹 個受信

計測端末

計測端末：ユーザーパケット：プローブパケット
Laboratory of Network Performance Evaluation

4

計測手法
パッシブ計測・プローブパケットを使用せず，端末間で計測する手法
・ユーザーパケットを記録して計測・計測精度と計測装置の負荷にトレードオフの関係

計測端末

計測端末

：ユーザーパケット
Laboratory of Network Performance Evaluation

5

計測手法
パッシブ計測
パケット損失率

𝑵𝑹

𝜶=𝟏−𝑵

𝑺

ユーザーパケットを𝑵𝑹 個記録

ユーザーパケットを𝑵𝑺 個記録

計測端末

計測端末

：ユーザーパケット
Laboratory of Network Performance Evaluation6パケット損失率推定におけるネットワークトモグラフィ
アクティブ計測はネットワークに本来必要のないパケットを送信し，パケット損失率推定では輻輳しているリンクに送信されることでユーザトラフィックに影響を与える
従来のマルチキャストの推定法ではアクティブ計測のみの推定法が多い
アクティブ計測とパッシブ計測との併用した手法はユニキャストになっている

マルチキャストにおいてアクティブ計測を削減することを考える

Laboratory of Network Performance Evaluation7

マルチキャストのパケット損失率推定 従来法[1]アクティブ計測のみ用いる
𝒏𝑹,𝒊パケット損失率 𝒍𝒊 = 𝟏 − 𝒏
𝑺,𝒊

パケット到達率 𝟏 − 𝒍𝒊 = ∏𝒆𝒋∈𝑾𝒊 𝟏 − 𝒒𝒋
e1

e3
W1

e2e4
W2e5𝒏𝑺,𝒊 : パス𝑾𝒊 に送信したパケット数
𝒏𝑹,𝒊 : パス𝑾𝒊 で受信したパケット数
𝒒𝒋 : リンク𝒆𝒋 のパケット損失率

e6
W3!" " = $, &, … (*+ + = $, &, ,, -W4[1] M.H. Firooz and S. Roy, “Network tomography via compressed sensing,” Global Telecommunications Conference (GLOBECOM
2010)IEEE, pp.1‒5 2010.

Laboratory of Network Performance Evaluation

8マルチキャストのパケット損失率推定 従来法[1]パケットの到達率を対数変換する
𝟏 − 𝒍𝒊 = ∏𝒆𝒋∈𝑾𝒊 𝟏 − 𝒒𝒋
対数𝒚 = 𝑨𝒙
𝑨 : ルーティング行列

𝒚𝒊 = − log 𝟏 − 𝒍𝒊 , 𝒙𝒋 = − log(𝟏 − 𝒒𝒋 )対数変換したことにより線形方程式が得られる

Laboratory of Network Performance Evaluation9

マルチキャストのパケット損失率推定 従来法[1]ルーティング行列𝑨e1 e2 e3
# $ ## $ $!=
$ # $
$ # $

ネットワークの構造を示す
行 パス𝑾𝒊列 リンク𝒆𝒋

e1

e3
W1

e2

e4
W2

e5

e6
W3

e4 e5 e6
$ $ $
# $ $
$ # $
$ $ #,#,,.
,/!" " = $, &, … (*+ + = $, &, ,, W4

Laboratory of Network Performance Evaluation10

マルチキャストのパケット損失率推定 従来法[1]ネットワーク内でパケット損失が起こるリンクは少なく，大部分が0(スパース)である
スパース性を持つと仮定する
得られた線形方程式
𝒚 = 𝑨𝒙を制約条件とする𝑳𝟏 ノルム最小化問題として定式化
𝑳𝟏 ノルム最小化問題= = argmin 𝒙𝒙𝒙

𝟏 𝐬. 𝐭. 𝒚 = 𝑨𝒙

Laboratory of Network Performance Evaluation

11

ユニキャストのパケット損失率推定 従来法[2]アクティブ計測とパッシブ計測を併用する
アクティブ計測パスを減らすことができる
アクティブ計測
パッシブ計測𝒚 = 𝑨𝒙𝜶 = 𝜷G 𝒍⃗

𝜶 : ネットワークのパケット損失率
𝜷 : パス𝑾𝒊 の利用率 𝜷 = 𝜷𝟏 , … , 𝜷𝒊𝒍𝒊 : パス𝑾𝒊 のパケット損失率𝒍⃗ = 𝒍𝟏 , … , 𝒍𝒊 𝑻

[2]手崎達也，渡部康平，中川健治，“L1 ノルム最小化によるパケッ ト損失率推定の高速化”，電子情報通信学会 総合大会，2018

Laboratory of Network Performance Evaluation

12

ユニキャストのパケット損失率推定 従来法[2]アクティブ計測を全てのパスで行うとプローブパケットが多くなりネットワークに負荷がかかる

アクティブ計測のパスを減らす
アクティブ計測を行うパスと行わないパスに分割
𝑨𝑻 = 𝑨𝑻𝒐 , 𝑨𝑻𝒎 , 𝜷𝑻 = 𝜷𝒐 , 𝜷𝒎 , 𝒐: observed
𝒎: missing𝒍⃗𝑻 = 𝒍⃗𝒐 , 𝒍⃗𝒎 , 𝒚𝑻 = (𝒚𝒐 , 𝒚𝒎 )アクティブ計測 𝒚𝒐 = 𝑨𝒐 𝒙
パッシブ計測𝜶 = 𝜷𝑻𝒐 𝒍⃗𝒐 + 𝜷𝑻𝒎 𝒍⃗𝒎
テイラー近似𝜶 − 𝜷𝑻𝒐 𝒍⃗𝒐 = 𝜷𝑻𝒎 𝑨𝒎 𝒙
Laboratory of Network Performance Evaluation

13

ユニキャストのパケット損失率推定 従来法[2]アクティブ計測
パッシブ計測𝒚𝒐 = 𝑨𝒐 𝒙
𝜶 − 𝜷𝑻𝒐 𝒍⃗𝒐 = 𝜷𝑻𝒎 𝑨𝒎 𝒙

損失率の高いリンクは少なく，スパース性持つと仮定でき，𝑳𝟏 ノルム最小化問題として推定できる
𝑳𝟏 ノルム最小化問題= = argmin 𝒙𝒙
𝟏𝒙s. t. 𝒚𝒐 = 𝑨𝒐 𝒙 , 𝜶 − 𝜷𝑻𝒐 𝒍⃗𝒐 = 𝜷𝑻𝒎 𝑨𝒎 𝒙

Laboratory of Network Performance Evaluation

14従来法の問題アクティブ計測のみのマルチキャストの従来法はプローブパケットを流すためユーザトラフィックに影響を与える
目的 1
従来のユニキャストの推定法を拡張し，マルチキャストにおいて，アクティブ計測を少なくリンクのパケット損失率を推定する手法

目的 2
アクティブ計測を行うパスの選択
Laboratory of Network Performance Evaluation

15従来手法の改良
従来法ではユニキャストのみでしか使えないため，これをマルチキャストで使えるように拡張する受信機が複数になることによりパッシブ計測から得られる情報が増え，プローブによる負荷を軽減

計測端末

計測端末

計測端末

計測端末
Laboratory of Network Performance Evaluation

16

提案法
パッシブ計測で観測されるパケット損失率
受信機が複数になったことにより，スカラー 𝜶 → ベクトル 𝜶
受信機数分の列ベクトル

計測端末

計測端末

計測端末

計測端末
Laboratory of Network Performance Evaluation

17

提案法
パスの利用率𝜶になったことにより，ベクトル 𝜷 → 行列 𝚩
行：パス列：受信機例)
e1

e3
W1

𝑹𝟏e2

e4
W2e5

𝑹𝟏 𝑹𝟐 𝑹𝟑 𝑹𝟒𝟎𝟎𝟎. 𝟐𝟓 𝟎𝟎𝟎 𝟎. 𝟐𝟓 𝟎
𝚩=𝟎 𝟎. 𝟐𝟓 𝟎𝟎𝟎𝟎𝟎 𝟎. 𝟐𝟓

𝑾𝟏
𝑾𝟐𝑾𝟑
𝑾𝟒

e6
W3

W4
Laboratory of Network Performance Evaluation

18提案法受信機が複数になったことにより，スカラー 𝜶 → ベクトル 𝜶ベクトル 𝜷 → 行列 𝚩 𝜶 受信機数のパケット損失率の列ベクトル
𝚩 パスの利用率の行列パッシブ計測の式は𝑻
𝜶 − 𝚩𝒐𝑻 𝒍⃗𝒐 = 𝚩𝒎𝑨𝒎 𝒙となり= = argmin 𝒙𝒙𝒙

𝟏

𝑻s. t. 𝒚𝒐 = 𝑨𝒐 𝒙, 𝜶 − 𝚩𝒐𝑻 𝒍⃗𝒐 = 𝚩𝒎𝑨𝒎 𝒙
Laboratory of Network Performance Evaluation

19シミュレーション条件
以下のトポロジーでパケット損失リンクは1つとする
損失発生リンクのパケット損失率のみ0より大きい推定値が得られた場合に推定可能とする
アクティブ計測のみの場合と提案法で全てのリンクを推定可能な計測パス数を比較する
パス数 ：12
𝑾𝒊 (𝒊 = 𝟏, 𝟐, … , 𝟏𝟐)
リンク数：19
𝒆𝒋 𝒋 = 𝟏, 𝟐, … , 𝟏𝟗
損失率：0.05
パスの利用率𝜷𝒊 = 𝟏/𝟏𝟐
Laboratory of Network Performance Evaluation20

結果
全てのリンクを推定可能な計測パス数の比較
計測パス数
12 11 10 9
アクティブ計測のみ
提案法: 推定可能最小の計測パス数• アクティブ計測のみ
• 提案法

87…
…
…

: 推定不可10本
8本

パッシブ計測から得られる情報が増えたため• 提案法の方が計測パス数が少なく推定可能
Laboratory of Network Performance Evaluation21

計測パスの選択
計測パスをいくつ削減できるのかは推定を行わない
とわからない計測を実際に行なって確かめるのはネットワークに負荷をかけてしまう
計測せずに推定可能か評価する方法が必要になる全てのリンクを推定可能な計測パスの選択方法

Laboratory of Network Performance Evaluation22

𝑳𝟏 ノルム最小化問題の完全再現十分条件
完全再現：正しい解が再構成されること
非零成分の個数が高々𝑲個の場合，完全再現十分条件
は𝐬𝐩𝐚𝐫𝐤 𝑨𝒐 > 𝟐𝑲となる[3]𝐬𝐩𝐚𝐫𝐤(𝑨𝒐) : 行列𝑨𝒐の一次従属な列ベクトル数の最小値

sparkの計算量は𝑶(𝟐𝑳 )であり，現実的ではない
𝑳 :ネットワークのリンク数

インコヒーレンスによって計算量を抑える方法が提案されている[4],[5][3] D. L. Donoho, “Optimally sparse representation in general (nonorthogonal) dictionaries via ld minimization,” Proc. Natl. Acad. Sci.,
vol. 100, no. 5, 2197 (2003).
[4] S. Gleichman and Y. C. Eldar, “Blind Compressed Sensing,” IEEE Trans. Info. Theory, vol. 57, no. 10, 6958 (2011).
[5] 三村 和史. ”圧縮センシング -疎情報の再構成とそのアルゴリズム-”. 数理解析研究所講究録. 第1803巻. 2012年

Laboratory of Network Performance Evaluation23

𝑳𝟏 ノルム最小化問題の完全再現十分条件
インコヒーレンス
𝑨𝒐の異なる2つの列ベクトル𝜶𝒊 , 𝜶𝒋 の方向余弦の絶対値の最大値

𝝁(𝑨𝒐 ) ≔ max

𝟏h𝒊h𝒋h𝑳

𝜶𝒊 , 𝜶𝒋𝜶𝒊 𝟐 𝜶𝒋𝟐

行列𝑨𝒐 の一次従属な列ベクトル数の最小値[2]𝝁(𝑨𝒐 )の計算量は𝑶(𝑳𝟐 )インコヒーレンスを用いることで𝐬𝐩𝐚𝐫𝐤 𝑨𝒐𝟏
≥ 𝟏+𝝁(𝑨𝒐 )完全再現十分条件は𝐬𝐩𝐚𝐫𝐤 𝑨𝒐 > 𝟐𝑲より，
𝟏𝟏𝑲<𝟏+𝟐𝝁(𝑨𝒐 )Laboratory of Network Performance Evaluation24

𝑳𝟏 ノルム最小化問題の完全再現十分条件
完全再現十分条件
𝟏𝟏𝑲<𝟏+≔ 𝝉 𝑨𝒐𝟐𝝁(𝑨𝒐 )𝝉(𝑨𝒐 )を求めることで評価できる
パケット損失率推定における𝑲は損失の発生するリンク数であり，損失リンク数が1個の場合2個の場合

𝟏 ≤ 𝝉(𝑨𝒐 )𝟐 ≤ 𝝉(𝑨𝒐 )…

を満たす𝑨𝒐 を選択する
Laboratory of Network Performance Evaluation25提案法の計測パスの選択法
完全再現十分条件

𝑲 < 𝝉(𝑨𝒐 )マルチキャストの従来法に適用するためには・完全再現十分条件が真であること
・𝑨𝒐 に全てのリンクを含むこと
提案法ではパッシブ計測も用いているため𝑨𝒐 に全てのリンクを含む必要はない

Laboratory of Network Performance Evaluation26

提案法の計測パスの選択法
パッシブ計測は端末間のパケット損失率が得られる
トポロジーを1対1に分割した場合に，分割したトポロジー毎に1つのパッシブ計測の式が得られる



Laboratory of Network Performance Evaluation27

提案法の計測パスの選択法
分割したトポロジー内に，𝑨𝒐 に含まれない未計測のリンクが1個以下であればパッシブ計測で推定可能となる提案法の計測パスの選択法
・𝑲 < 𝝉(𝑨𝒐 )が真である・分割したトポロジー内で𝑨𝒐 に含まれない未計測のリンクが1個以下

Laboratory of Network Performance Evaluation

28

シミュレーション条件
以下のトポロジーでパケット損失リンクは1つとする
計測パスを減らしていき，全ての組合せを全探索で，提案法の計測パスの選択法を満たしたものが推定可能であることを示す
パス数 ：12
𝑾𝒊 (𝒊 = 𝟏, 𝟐, … , 𝟏𝟐)
リンク数：19
𝒆𝒋 𝒋 = 𝟏, 𝟐, … , 𝟏𝟗Laboratory of Network Performance Evaluation

29結果
計測パス数に対する条件を満たす組合せ数
計測パス数
完全再現十分条件
提案法のパス選択法

12 11 10 918 20 16
18 16 1684
3

700…
…
…

上表のうち全てのリンクを推定可能な組合せの割合
計測パス数
12 11 1098
完全再現十分条件[%] 100 80 100 100 75
提案法のパス選択法 100 100 100 100 100
[%]

700…
…
…

表から完全再現十分条件だけでは推定可能な組合せのみを選択できていないが，提案法のパス選択法では選択できている
Laboratory of Network Performance Evaluation

30

まとめ
結論
・従来法を拡張し，マルチキャスト通信におけるパケット損失率推定法を提案し，アクティブ計測のみの結果と比べ，計測パスを削減することができた
・パスの選択法提案し，アクティブ計測のパスを削減する𝑨𝒐 を選択できることを示した
今後の展望
・パケット損失発生するリンクが複数の場合・計測パスを削減した𝑨𝒐 を探索するアルゴリズム
・パケットを流したシミュレーション
Laboratory of Network Performance Evaluation

31