95
特集●ネットワーク技術

AS 規模定量化による AS 間接続関係の推定
浅井 大史 江崎 浩

インターネットにおける自律システム (AS: Autonomous System) 間の接続関係は，相互接続における経済関係および経路交換ポリシーから大きくトランジットおよびピアリングの 2 つに分類される．本論文では AS の全域部分
グラフ (一部の AS 間リンクを含まない部分グラフ) から AS 規模を定量化し，この AS 規模に基づいた AS 間接続関係の推定手法を提案する．本論文の貢献は次の 2 点である．1) 従来の推定手法と比較して，少数のトポロジー計
測点での AS 間接続関係，特にピアリングの推定精度を向上した．2) 本手法では AS の全域部分グラフから定量化
した AS 規模を用いることで，従来の経路解析に基づく手法では推定できなかった推定に用いた経路情報に含まれない AS 間リンクに対しても AS 間接続関係を推定可能にした．

The relationships between interconnected autonomous systems (ASes) on the Internet are categorized into
two major types: transit and peering. We propose a method to estimate AS relationships by comparing
diﬀerences in AS network size called magnitude that is quantiﬁed by recursively analyzing an AS adjacency
matrix converted from a spanning subgraph of AS-level Internet topology. The contributions of this paper
are two-folds: 1) The proposed method outperforms the existing methods in the inference of AS relationships, especially peering links, with a smaller dataset. 2) The proposed method enables us to estimate AS
relationships of invisible links from a set of quantiﬁed AS magnitude when they become visible because themagnitude of every AS is already quantiﬁed from a spanning subgraph.

クの検出 [32] に応用されている．しかし，AS 間接続関1 はじめに係はネットワークプロバイダ間の契約関係であるため，

インターネットは，IP ネットワークにおけるネッ

多くの商用 ISP にとってその情報は機密情報とされ，

トワークドメインの単位である自律システム (AS:

一般には公開されていない [21]．そのため，計測可能

Autonomous System) [13] が相互に接続することによな経路情報や Internet Routing Registry (IRR) [18]り構成されている．相互に接続された AS 間の接続関などの公開データベースから AS 間接続関係を推定

係は，経済関係および経路交換ポリシーから大きく，する手法が研究されてきた [3] [5] [6] [7] [9]．しかし，こ1) トランジット (小規模な AS が大規模な AS からイれらの手法においてピアリングの推定精度が低いこ

ンターネットへの接続性を購入する接続関係)，2) ピとが指摘されている [31]．また，インターネット上のアリング (無償での相互接続関係) の 2 種類に分類さ99.9% の AS 間リンクを計測するには 700 地点ものれる [9] [21] [25]．これらの AS 間接続関係の情報はト

計測点が必要であると推定されている [24] 一方で，経路情報を公開している計測点は多くない†1 ため，従来

ラフィックエンジニアリング [2] [12] や経路ハイジャッの経路解析に基づく手法では AS 間接続関係を推定でEstimating AS Relationships from Quantiﬁed AS
Magnitude.
Hirochika Asai, Hiroshi Esaki, 東京大学大学院情報理工学系研究科, Graduate School of Information Scienceand Technology,The University of Tokyo.
コンピュータソフトウェア, Vol.29, No.2 (2012),pp.95–108.
[研究論文] 2011 年 6 月 27 日受付.

きない AS 間リンクが多く存在し，これらの手法により推定した AS 間接続関係をオーバーレイネットワー†1 Muhlbauer ら [19] が用いたデータのうち，2011 年
6 月時点で公開されているものは RouteViews [27](8地点) および RIPE NCC [23](17 地点) のみである．

96コンピュータソフトウェア

クにおける経路制御などに応用することが困難であらの手法を発展させ，各 AS 間リンクに対して両端る [1] [2]．そのため，少数の計測点で取得した経路情の AS の次数による重み付けを行い，AS 間接続関係

報を元に，計測した経路情報含まれない AS 間リンクを推測する問題を重み付き MAX2SAT 問題としてに対しても AS 間接続関係を高精度に推定する手法が帰着させ，トランジットの向きの推定精度を向上し必要とされている．

た．また，文献 [6] では次数による重み付けに従い，

本論文では，従来の手法で用いられてきた経路情報

Gao の手法と同様のヒューリスティクスを導入するではなく，AS の隣接情報を表す全域部分グラフ (一ことでピアリングを推定する手法を提案した．さら部の AS 間リンクを含まない部分グラフ) から AS 規に，IRR に登録されている組織名を元に同一組織に属する AS 間の接続関係であるシブリング†2 の推定手模を定量化し，この AS 規模に基づいた AS 間接続関係の推定手法を提案する．本論文では，提案手法によ法を提案した．しかし，これらの研究では，AS パス

り従来手法と比較して，少数の計測点で取得した経路

を Valley-free 規則に基づいて解析することで AS 間

情報を推定に用いたときに AS 間接続関係，特にピア接続関係を推定しているため，Valley-free 規則に従リングをより高精度に推定できることを示す．また，わない経路制御による推定結果への影響が大きく，ま従来手法では推定に用いる経路情報に含まれない AS

た高い推定精度を得るためには十分な計測点 (AS パ

間リンクに対しては AS 間接続関係を推定できなかっス数) が必要であるという問題がある．さらに，ASたが，本手法では定量化した AS 規模を用いることパスから AS 間接続関係を推定するため，例えば，別で，AS 規模の定量化に用いた全域部分グラフに含まの計測により発見された AS 間リンクなど，計測したれなかった AS 間リンクに対しても AS 間接続関係が経路情報に含まれない AS 間リンクについては AS 間

推定可能となることを示す．

接続関係を推定できない．

Xia ら [31] は，Valley-free 規則に基づく推定手法に

2 関連研究おけるピアリング推定精度が低いことを指摘し，ピア

AS 間接続関係の推定問題は Gao [9] により提唱さリングを高精度に推定するために，BGP のパス属性

れ，様々な研究が行われてきた．Gao は，次数 (隣接の 1 つである Community 属性や IRR に登録されてAS 数) の大きい AS をトランジットにおけるプロバ

いる AS-SET 属性およびルーティングポリシーを用

イダ AS とする仮定およびトランジットとピアリン

いて推定した一部の AS 間接続関係から全体の AS 間

グにおける経路交換ポリシーを表す Valley-free 規則

接続関係を高精度に推定する手法を提案した．このよ[8] に従い，Border Gateway Protocol (BGP) [22] の

うに AS グラフや AS パス以外のメタデータはシブリ

ルーティングテーブルから取得した AS パスを解析す

ングの推定にも用いられている [6] [7] が，これらのメることで AS 間接続関係を推定する手法を提案した．

タデータを公開していないネットワークプロバイダもSubramanian ら [26] は，複数の計測点のルーティング

多いため，一部の AS 間リンクにしか適応できない．

テーブルから取得した AS パスから AS 間接続関係を

我々は予備実験 [1] により提案手法が AS 間接続関

推測する問題を Valley-free 規則に従った AS パス数を最大とする最適化問題として定式化した．Battista係を推定できる可能性を示したが，この予備実験では
CAIDA による AS 間接続関係の推定データ [4]†3 をら [3] [5] は，全てのリンクをトランジットと仮定す

正解データセットとして用いたため，提案手法と従来ることでこの最適化問題を MAX2SAT(maximum-2-

satisﬁability) 問題に帰着させ，トランジットの向き(プロバイダ・カスタマの関係) を解く手法を提案した．
また，これを拡張し Valley-free 規則に従わない AS
パス数を増やさないようにピアリングを推定する手法を提案した．Dimitropoulos ら [6] [7] は，Battista†2 同一組織に属するため，シブリングにおける経路交換
ポリシーは柔軟であり，また，シブリングリンクの数は非常に少ない [4] ので，本論文ではシブリングについては明示しない限り考慮しない．
†3 CAIDA による推定アルゴリズムは 2010 年 7 月に大幅に変更されているが本論文では文献 [6] [7] に基づく
変更前のアルゴリズムを対象とする．

Vol. 29 No. 2 May 2012

97

手法の性能を適切に比較評価できていなかった．まて定義する．ここで，tij を AS i から AS j へ流れる

た，評価に用いたデータセット数が少なかったため，

トラフィック量とする．

提案手法の性能を十分に検証できていなかった．

3 隣接情報を用いた AS 間接続関係の推定(仮定 a) AS i に流入するトラフィックの総量は，
AS i から流出するトラフィックの総量に等しい(式 (1))．

AS 間接続関係は相互接続する AS で交換されるト
ラフィック量の非対称性により決定されることが一般的であるため，AS 間の規模の比と AS 間接続関係には相関関係がある [9] [14] [21]．本論文では，この点に着目して，各 AS の扱うトラフィック量から AS 規模を定量化し，この AS 規模に基づき AS 間接続関係を推定する手法を提案する．
本提案手法では，まず RouteViews [27] や RIPE

NCC [23] の公開している BGP の経路情報 (AS パス) などから AS の隣接情報を表す全域部分グラフ Gsを得る．ここで，BGP の経路情報は各 AS への到達性を表しているため，そこから展開したグラフは到達可能な全 AS を含む全域部分グラフとなる．デフォ
ルト経路設定や通信障害によりごく少数の AS が含
まれない可能性もあるが，デフォルト経路設定により計測されていない場合はマルチホームをしていない
ため経路制御などへの応用において AS 間接続関係を推定する必要性はなく，また通信障害により観測さ

k∈Ni



tki :=

tik

(1)

k∈Ni

(仮定 b) AS i から AS j へ流れるトラフィック量は，AS j の規模 ρj に比例する (式 (2))．
ρjtij := tikk∈Ni ρk(2)k∈Ni(仮定 b) にこのトラフィック流量仮定から定義される
AS 規模を含むことからもわかるとおり，AS 規模は
再帰的に定義される．n 回の再帰計算により定義された AS 規模は，直感的には，n ホップ先の AS の規模まで考慮した AS の規模であることを意味する．なお，このトラフィック流量仮定を採用した論拠は第 5節で議論する．
このトラフィック流量仮定に従い，AS の隣接情報からトラフィック流量のマルコフ連鎖における定常状態を計算することで各 AS の規模を定量化する．まず，入力情報である AS の全域部分グラフ Gs = (V, E) か ら AS の 隣 接 行 列 A = aij ∈ m×m を 構

成 し ，こ の 隣 接 行 列 を 元 に 各 AS の 規 模 nρ =れない AS は到達不可能として扱うことで無視でき[nρ1 , . . . , nρm ] (s.t. nρ = 1) を再帰的に定義するため，本論文では考慮しない．全域部分グラフ Gs

る．ここで，m は V の要素数，n • (n ≥ 0, n ∈)は AS の集合 V および AS 間リンクの集合 E から構は AS 規模の再帰計算の深さを表す．以下に AS 規模成される．また，全域部分グラフ Gs は無向グラフとの計算手続きを示す．

して表される．ここで，AS i の隣接 AS の集合を集
合 Ni (NiV ) と表現する．次に，全域部分グラフ

Gs から AS 間のトラフィック流量仮定に従い AS の
規模 (magnitude) ρi (i ∈ V ) を定量化する．上述し 
1. 重み付き隣接行列 nW = wij をA(n = 0)n
W :=I (n−1)ρA (n ≥ 1)

(3)

た通り，AS 間接続関係は相互接続する 2 つの AS 間と定義する．ここで，I は単位行列を表す．

の規模の比と相関関係があるため，定量化した AS 規

2. 重み付き隣接行列 nW を用いて，確率行列 nT模の比から AS 間接続関係を推定する．

を式 (4) により定義する．
n3. 1 AS 規模の定量化

T :=

n

m

wij
nw
ik

(4)

k=1

AS 間で交換されるトラフィック流量について次の3. 確率行列 nT の最大固有値に対応する左固有ベ

2 つの仮定を置き，AS 間のトラフィック流量をマルコ

クトルを求め，これを AS 規模 nρ と定義する．

フ連鎖として定義することで各 AS の扱うトラフィッ
ク量を計算し，これを正規化したものを AS 規模としn ≥ 1 についても (n−1)ρ から再帰的に定義できる．
なお，ここで，n = 0 のとき，AS 規模 nρi (= 0ρi ) は

98コンピュータソフトウェア

AS i の次数 (隣接 AS 数) の定数倍となる (証明は付ンクに対しても AS 間接続関係を推定できることを示

録 A を参照)．次数は従来手法 [6] [7] [9] で用いられてし，従来の経路解析に基づく手法に対する提案手法のいるため，本論文では n ≥ 1 のときを提案手法とし優位性を示す．最後に，実インターネット上で計測して扱う．

た経路情報から従来の発見的な AS 間接続関係の推定手法 [6] [7] により推定された AS 間接続関係データ

3. 2 AS 間接続関係の推定

セット [4] を正解データセットとして用いた交差検定

前項で定義した AS 規模から AS 間接続関係を推定を行うことで，提案手法における AS 規模の再帰計算する手法について説明する．まず，AS vi から AS vj

が実インターネットトポロジーに対しても有効であるへの AS 間リンク eij における AS 規模の比を AS 規

ことを示す．

n

模距離 (magnitude distance) δeij と定義する．AS4. 1 トポロジージェネレータを用いた評価

規模距離 nδeij は式 (5) と定義する．

δeij := log 10 ρvi − log10 ρvj

n

n

n

(5)

本論文では AS レベルのトポロジーを生成するトs.t. eij = (vi , vj ), vi , vj ∈ V

ポロジージェネレータとして Inet-3.0 [30] を用いる．

ピアリングは同規模の AS 間の接続関係であり，一Inet-3.0 は，実インターネット上での計測から構築し方，トランジットは小規模な AS が大規模な AS からたべき乗則に基づくモデルに従い，AS を頂点，AS 間

インターネットの接続を購入する接続関係であるた

リンクを辺とした連結無向グラフを生成する．AS レ

め，AS 規模距離の絶対値 | δ| が小さければピアリン

ベルのトポロジージェネレータは，他に BRITE [17]グ (p2p) であり，大きければトランジットであると推や Orbis [16] があるが，これらのトポロジージェネ

定できる．また，トランジットにおいては，規模の大レータの生成するトポロジーは AS 間接続関係を定nn

きい AS がプロバイダ AS であるため， δ が正数で義しておらず，さらに生成されたトポロジーが階層あればプロバイダからカスタマへのトランジットリン

構造を保持していないため，AS 間接続関係を定義でク (p2c) であり，nδ が負数であればカスタマからプ

きず，AS 間接続関係の推定精度の評価に適さない．

ロバイダへのトランジットリンク (c2p) であると推定

Inet-3.0 の生成するトポロジーも AS 間接続関係を定nできる．すなわち，式 (6) のように閾値 τ を与える
n

義していないが，Inet-3.0 は階層的なトポロジーを生ことで，AS 規模距離 δ から AS 間接続関係を推定成するため，その階層構造から AS 間接続関係を定義することができる．
nn
 δ> τ

することができる．

nδ < −nτ−→ c2p−nτ ≤ nδ ≤ nτ−→ p2p

表 1 に示したパラメータを用い，AS 数を 5000 か−→ p2c(6)

s.t. nτ ≥ 0 (nτ : 閾値)ら 35000 まで 100 刻みで変化させ，301 個の評価ト
ポロジーを生成した．なお，AS 数以外のパラメータは Inet-3.0 デフォルトのものを用いている．これらの生成されたトポロジーの AS 間リンクには AS 間接

4 AS 間接続関係の推定手法の性能評価

続関係が定義されていないため，トポロジーの階層

本節では，第 3 節で提案した AS 間接続関係の推構造から各リンクに対して AS 間接続関係を定義す

定手法の性能評価を行う．本論文では，まず，トポロ

る．まず，これらのトポロジーで次数を最大とする

ジージェネレータ Inet-3.0 [30] により生成したトポ
ロジーを正解データセットとして用い，AS 間接続関係の推定精度について従来手法との比較評価を行う．
次に，実インターネット上の 9 地点で計測された経路情報 [23] [27] を用いて，提案手法が AS 規模の定量化に用いた全域部分グラフに含まれなかった AS 間リ

表1

Inet-3.0 のトポロジー生成パラメータ

パラメータ名値

AS 数
次数 1 である AS の割合
AS 配置面の大きさ
ランダムシード{5000, 5100, . . . , 35000}
0.3
10000
0

Vol. 29 No. 2 May 201299

用データセットを構築した．図 2 に生成したトポロ
ジーの AS 数とトランジットおよびピアリングリンク
数の関係を示す．ピアリングはその経路交換ポリシーの特性上，観測されにくい [24] ため，実インターネッ
ト上での計測に基づく AS 間接続関係の推定データ[4] と比較してピアリングリンク数が多くなっている．

本項ではこのデータセットを用いて，以下の 2 点に
図1

Inet-3.0 の生成するトポロジーに対する AS 間
接続関係の定義：次数を最大とする AS を根とした全域木に対して定義した tier から AS 間接続関係を定義する．

ついて提案手法の評価を行う．

1. 提案手法により定量化した AS 規模を従来手法[6] [7] [9] で AS の大きさを表す指標として使われてきた次数と AS 間接続関係の推定精度の点から比較し，提案手法の AS 規模距離により AS 間接
続関係をより良く表せることを示す．

2. 生成したトポロジーに対して AS 間の典型的な
経路交換ポリシーを表す Valley-free 規則 [8] および一般的な経路選択ポリシー [29] に従う経路を計算し，これらの経路情報を元に，AS 間接続関係の推定に用いる経路を計測する AS の数を変化させたときの推定精度の評価を行う．この評価により，従来の発見的な経路解析に基づく手法 [9]および Valley-free 規則に従う AS パスの数を最
図2

Inet-3.0 により生成したトポロジーに含まれる
トランジットおよびピアリングリンク数

大とするように AS 間接続関係を推定する手法[3] [5] と比較して，提案手法により少数の計測点

AS を根とした全域木を計算する．この全域木の根かで取得した経路情報から AS 間接続関係，特にピら AS i までのホップ数を tieri と定義する．次に，隣アリングの推定を高精度に行えることを示す．

接する 2 つの AS，AS i–AS j 間の tier の差 ∆tieri,j

4. 1. 1 次数と AS 規模の比較評価

を式 (7) により定義する．

第 3 節で説明した通り，n = 0 のとき，AS 規模 nρi∆tieri,j = tierj − tieri(7)は AS i の次数 (隣接 AS 数) の定数倍となる．すな

Inet-3.0 は ∆tier を −1，0，1 のいずれかとするよう

わち，n = 0 のとき，AS 規模距離 nδ は次数の比をな階層的なトポロジーを生成するため，このトポロ表す．次数の比は Gao [9] の AS 間接続関係の推定手

ジーの階層構造から各 AS 間リンクの AS 間接続関係法でピアリングの推定に用いられている．ここでは，

を式 (8) により定める (図 1)．

次数の比 (0δ) を従来手法として，提案手法における


1






∆tieri,j =

0





−1


AS 規模の再帰計算 (n ≥ 1) により AS 規模距離 nδ が

→ p2c
(AS i: プロバイダ, AS j: カスタマ)

AS 間接続関係をより良く表すことを示す．このこと→ p2pを示すため，生成したトポロジーの AS グラフから，→ c2p

n = {0, 1, . . . , 7} について AS 規模および AS 規模距(AS i: カスタマ, AS j: プロバイダ)(8)

離を計算し，式 (6) の閾値 n τ を変化させ，AS 間接
続関係の推定精度を評価する．

このようにして Inet-3.0 により生成されたトポロ

AS 間接続関係の推定精度を数値的に評価するため

ジーの各 AS 間リンクに AS 間接続関係を定義し評価に，Receiver Operating Characteristic (ROC) 解析

100

コンピュータソフトウェア
数を {5000, 5100, . . . , 35000} の 301 個のトポロジーに対しても同様に評価した．図 4 に，n = {0, 1, 2, 3}
に対する，AS 数とトランジット (p2c/c2p) およびピ
アリング (p2p) 推定時の AUC の関係を示す．図 4 より，AS 数に依らず，n ≥ 1 のときの AS 規模距離が次数の比 (n = 0 のときの AS 規模距離) よりも高精度に AS 間接続関係を推定できることがわかる．また，AS 数 30000 のときと同様に，特にピアリングの推定精度を大きく向上していることがわかる．これら

図 3 AS 規 模 の 再帰 計 算 回 数 n とト ラ ン ジット(p2c/c2p) およびピアリング (p2p) 推定時のAUC(AS 数：30000)の結果より，n ≥ 1 のときの AS 規模は次数よりも良く AS の大きさを表現していることが言える．

4. 1. 2 経路解析に基づく推定手法との比較評価
次に，発見的な経路解析に基づく AS 間接続関係のにおける ROC 曲線下面積 (AUC: Area Under then推定手法 [9](以下，GAO と呼ぶ) および Valley-freeCurve) を用いる．ROC 曲線は，閾値 τ を変化さ規則に従う AS パスの数を最大とするように AS 間せた際の誤検知率 (False positive rate) を x 軸，検接続関係を推定する手法 [3] [5](以下，DPP と呼ぶ)

知率 (True positive rate) を y 軸に描画した曲線でと提案手法の比較評価を行う．なお，GAO では文ある．ROC 曲線上の点と直線 y = x の距離は，各

献 [9] で推奨されているパラメータ L = 1 およびn点に対応する閾値 τ における推定精度を表しておR = 60 を用いる．また，DPP ではトランジット

り，この距離の積分値に定数 (直線 y = x 下の面積:の推定後に Valley-free 規則に従わない経路を増加

1
xdx = 12 ) を加えた値である AUC は閾値 n τ に依0させないようにピアリングの推定を行うアルゴリ

らない推定精度を表す．また，ROC 解析においては，ズムを選択した．GAO，DPP では AS 間接続関係

n

一般に，この距離を最大とする点に対応する閾値 τの推定に AS パスが必要であるので，まず，生成しが最適な閾値として用いられている．

たトポロジーおよび AS 間接続関係から Valley-free

図 3 に AS 数 30000 のトポロジーにおける AS 規模規則に従う経路を計算した．なお，パスベクタ型のの再帰計算回数 n とトランジット (p2c/c2p) および経路計算の最悪計算量は O((V  − 1)!) であると言ピアリング (p2p) 推定時の AUC の関係を示す．これ

われており [15]，非常に大きいため，ここでは ASより，n ≥ 1 のときの AS 規模距離は次数の比 (n = 0

数 {5000, 10000, 15000, 20000, 25000, 30000, 35000}のときの AS 規模距離) よりも高精度に AS 間接続関のトポロジーのみを経路計算の対象とし評価に用係を推定できることがわかる．図 3 において，トラいる．

ンジットおよびピアリング推定時の AUC はそれぞ

GAO，DPP は閾値を持たないため ROC 解析が適れ，n = 0 のとき 0.942, 0.802，n = 3 のとき 0.972,

用できない．そこで，推定性能の評価に広く用いら

0.907 であり，AS 規模の再帰計算により，ピアリン

れている F-measure を用い，従来手法および提案手

グの推定精度が大きく向上していることがわかる．図法の AS 間接続関係の推定精度を数値的に評価する．

3 から，AUC を極大にする再帰計算回数は，トラン

F-measure は適合率 (Precision) と再現率 (Recall)

ジット推定については n = 6，ピアリング推定についからては n = 5 であるが，実用上は n ≤ 3 で問題ないた
め，以降 n ≤ 3 を評価対象とする．なお，再帰計算
回数 n については第 5 節で議論する．
この結果が AS 数に依らないことを示すために，ASF-measure := 2 ×

Precision × Recall
Precision + Recallと定義される．ここで，False positive を FP，False

negative を FN，True positive を TP としたとき，

Vol. 29 No. 2 May 2012(a) トランジット推定
図4101(b) ピアリング推定

生成したトポロジーの AS 数とトランジット (p2c/c2p) およびピアリング (p2p) 推定時の
AUC の関係 (AS 数：{5000, 5100, . . . , 35000})

Precision および Recall はそれぞれ，次数の大きい順に計測点を選択したときを評価対象とTP
TP + FP

した理由は，次数分布がべき乗則に従うトポロジーでPrecision :=Recall :=TP
TP + FNが低くなってしまう次数の大きい AS を計測点とした

ランダムに計測点を選択した場合に選択される確率

場合を評価するためである．図 5 より，GAO およびと定義される．なお，提案手法の F-measure につい

DPP のピアリングの推定精度は計測点の数および計ては，ROC 解析における最適閾値のときの値を採用

測点の選択に大きく依存しており，計測点の数が少なする．ROC 解析における最適閾値とは，前述の通り，

い場合は推定精度が低いことがわかる．一方，提案手

ROC 曲線上の点と直線 y = x の距離が最大となる点

法は計測点の数および計測点の選択方法に大きく依らnに対応する閾値 τ である．

ず一定の推定精度を得ることができていることがわか

まず，AS 数 5000 のトポロジーを用いて，GAO おる．ここで，計測点の数が 100 のときに着目すると，

よび DPP と提案手法の比較評価を行う．ここで，実提案手法 (n = 3) は GAO と比較して，トランジット

インターネットを想定した場合，AS パスを計測・取の推定においてほぼ同程度 (約 1.0 倍)，ピアリング推得できる地点は限られていることを考える．ここで定において 1.5 倍の高い推定精度を得られたことがわ

は，AS パスを経路表から計測・取得する AS の数をかる．また，DPP と比較して，トランジットの推定

10, 100, 1000 地点と変化させ，計測した AS パスかにおいて 1.1 倍以上，ピアリング推定において 1.4 倍

ら GAO，DPP および提案手法により AS 間接続関係

以上の高い推定精度を得られたことがわかる．これよを推定し，F-measure を比較することで推定精度を評り，提案手法は AS パスの計測点の数が少なくても高価する．図 5 に計測点の数を 10, 100, 1000 と変化さ精度に AS 間接続関係を推定できることが示された．

せたときの GAO，DPP および提案手法 (n = 3) の特に，ピアリングの推定精度を大きく向上できた．

トランジット (p2c/c2p) およびピアリング (p2p) 推

次に，AS 数が 5000 以外のトポロジーを用いて定における F-measure を示す．この図において，折GAO および DPP と提 案手法の 比較評 価を行う．

れ線は計測点を次数の大きい順に選択したときの値でDPP のピアリング推定は NP 完全問題であり [3]，入あり，エラーバーは計測点をランダムで 10 通り選択

力経路数が増加すると計算量が爆発的に増大するた

したときの最小・平均・最大値を表している．なお，

め，ここでは計測点の数を 10 として評価を行う．図102コンピュータソフトウェア(a) トランジット推定
図5(b) ピアリング推定

経路計測点の数を変化させたときのトランジット (p2c/c2p) およびピアリング (p2p) 推定時のF-measure (AS 数：5000)．折れ線は計測点を次数の上位から選択したときの値，エラーバーは計測点をランダムで 10 通り選択したときの最小・平均・最大値を表している．

(a) トランジット推定
図6(b) ピアリング推定

計測点の数が 10 のときのトランジット (p2c/c2p) およびピアリング (p2p) 推定時の F-measure．
折れ線は計測点を次数の上位から選択したときの値，エラーバーは計測点をランダムで 5 通り選択したときの最小・平均・最大値を表している．

6 に計測点の数が 10 のときの DPP および提案手法

比較して，提案手法はピアリングを高精度に推定でき(n = 3) のトランジット (p2c/c2p) およびピアリング

ることがわかる．

(p2p) 推定における F-measure を示す．この図にお以上の評価より，提案手法は AS 間接続関係の推定

いて，折れ線は計測点を次数の大きい順に選択したとに用いる経路情報を計測・取得する AS の数が少なくきの値であり，エラーバーは計測点をランダムで 5 通ても高精度に AS 間接続関係を推定できることが示さり選択したときの最小・平均・最大値を表している．

れた．また，提案手法は GAO および DPP と比較し

図 6 は，AS 数が 5000 のときと同様に，どの AS 数てピアリングの推定精度を大きく向上できることがのトポロジーに対しても，提案手法により GAO およ

示された．

び DPP と比較して高精度に AS 間接続関係を推定できたことを示している．特に，GAO および DPP とVol. 29 No. 2 May 2012
表2

a)
b)
c)
d)
e)
f)
g)
h)
i)

103

各計測地点のデータセットに含まれる AS 経路数およびユニーク AS 数，
ユニークリンク数 (RIB データセット)

計測地点

略記法

データ元

Oregon IX
Equinix Ashburn
ISC (PAIX)
LINX
DIXIE (WIDE)RIPE NCC, Amsterdam
Otemachi, Japan (JPIX)
Stockholm, Sweden (NETNOD)
Milan, Italy (MIX)

oregon
eqix
isc
linx
wide
rrc00
rrc06
rrc07
rrc10

RouteViews
RouteViews
RouteViews
RouteViews
RouteViews
RIPE NCC
RIPE NCC
RIPE NCC
RIPE NCC

経路数

AS 数

リンク数

1641141
25713043310878255420814764112796924
242386242168

32262
32065
32145
32159
32099
32275
32032
32104
32090

69246
57726
60641
65774
51328
64151
45040
56563
56241

4. 2 実インターネットトポロジーによる評価

則に従う経路の割合を比較することで，推定用データ

第 4. 1 項ではトポロジージェネレータにより生成セットに含まれなかった AS 間リンクに対する AS 間したトポロジーとその階層構造から定義した AS 間

接続関係の推定精度を評価する．すなわち，本評価で接続関係を正解データセットとして，提案手法の性は，推定された AS 間接続関係を AS パスに適用し，能評価を行った．本項では，提案手法により推定した

1) Valley-free 規則に従う経路，2) Valley-free 規則に

AS 間接続関係が実インターネット上でのトラフィッ

従わない経路，3) AS 間接続関係が推定できない AS

ク最適化 [2] などに応用できることを示すため，実イ間リンクを含む経路の 3 つに分類し，Valley-free 規

ンターネット上で計測された経路情報を用い，AS 規則に従う経路の割合を比較する．トラフィック最適化

模の定量化に用いた経路情報に含まれなかった AS 間

[2] への応用を考えると，Valley-free 規則に従うこと

リンクに対しても AS 間接続関係が推定可能であるこは経路のコストを推定できていることを表しているとを示す．

一方，Valley-free 規則に従わないことや AS 間接続

本項では，RouteViews [27] RIPE NCC [23] で公関係が推定できない AS 間リンクを含むことは経路の開されているインターネット上の BGP ルータで取得コストを適切に推定できていないことを表している．

した経路情報のうち表 2 に示す 9 地点の 2009 年 8 月

本評価では Valley-free 規則に従う経路数が多いほど

1 日から 2009 年 8 月 5 日の 5 日間の経路情報を各地

AS 間接続関係を高精度に推定できたと考えることが点ごとで結合したデータセットを用いる．表 2 に計できる．

測地点およびデータ元，各データセットに含まれる

本評価を行うため，まず 9 個の各データセットを

AS 経路数およびユニーク AS 数，ユニーク AS 間リ
ンク数†4 を示す．

用いて，DPP により AS 間接続関係を推定し，次数(n = 0 のときの AS 規模) および n = 3 のときの AS

実インターネット上のトポロジーでは AS 間接続関規模を計算した．なお，次数の比を用いた推定 (以下係の正解データセットを定義できないため，これらのDEG と呼ぶ) および n = 3 のときの AS 規模距離を

9 個のデータセットを用い，ある地点のデータセット

用いた推定 (以下 MAG3 と呼ぶ) は，計算した次数(推定用データセット) から各手法で AS 間接続関係

や AS 規模から推定用データセットに含まれない ASを推定し (提案手法では AS 規模を計算し)，他の地

間リンクに対しても適用可能であるため，これらの点のデータセット (評価用データセット) の AS パス

推定手法は評価用データセットの AS 間リンクに対しに推定した AS 間接続関係を適用して Valley-free 規て適用する．なお，本評価においては，トランジット†4 AS 間リンク数は IP アドレスレベルのリンク数ではなく，AS 番号レベルでのリンク数，すなわち AS グ
ラフ上での辺の数を意味する．

の向き (プロバイダ・カスタマの関係) が重要となる

Valley-free 規則に従うかを評価するため，全ての AS
間リンクをトランジットとして扱う．つまり，DPP

104

コンピュータソフトウェア

1

1

0.8

rrc06
rrc00

0.6

wide
0.4

linx
isc

0.2

eqix

rrc07
Dataset for verification

Dataset for verification

rrc07

0.8

rrc06
rrc00

0.6

wide
0.4

linx
isc

0.2

eqix

oregon-ix

Proportion of valley-free paths

rrc10
Proportion of valley-free paths

rrc10

oregon-ix
ore eq isc
go ix
n-i
x

lin wid rrc rrc rrc rrc
xe 00 06 07 10

0ore eq isc
go ix
n-i
x

Dataset for annotation

lin wid rrc rrc rrc rrc
xe 00 06 07 10

0

Dataset for annotation(a) DPP(b) DEG1

Dataset for verification

rrc07

0.8

rrc06
rrc00

0.6

wide
0.4

linx
isc

0.2

eqix

Proportion of valley-free paths

rrc10

oregon-ix
ore eq isc
go ix
n-i
x

lin wid rrc rrc rrc rrc
xe 00 06 07 10

0

Dataset for annotation(c) MAG3
図79 地点の経路情報データセットに対する Valley-free 適用評価結果

においてはトランジットの向きの推定後に行うピアリに推定用データセットと異なる地点のデータセットを

ングの数を最大とする推定手続きを省略し，DEG お

用いた場合は，Valley-free 規則に従う経路の割合がよび MAG3 においては閾値 τ = 0 を用いる．

少なくなっていることがわかる．一方，MAG3 では，

図 7 に 9 地点の経路データセットに対する Valley-

全体的に Valley-free 規則に従う経路の割合が大きく

free 適用評価の結果を示す．横軸に推定用データセッ

なっており，1 地点の計測データから推定した AS 規

ト，縦軸に評価用データセットをとり，Valley-free 規

模から推定用データセットに含まれなかった AS 間リ

則に従う経路の割合を明度で表し，9 × 9 の格子状にンクに対しても高精度に AS 間接続関係を推定できる

描画した．この図から，経路解析に基づく推定手法

ことが示された．また，DEG を用いて AS 間接続関である DPP は，推定用データセットと評価用データ

係を推定した場合も，推定用データセットに含まれなセットが同一である場合は Valley-free 規則に従う経路の割合が多くなっている†5 が，評価用データセット

かった AS 間リンクに対して AS 間接続関係を推定で†5 DPP は推定用データセット中の Valley-free 規則に従う経路数を最大とするように推定しているためこのきていることがわかる (図 7(b)) が，MAG3 と比較

値が最大値である．

Vol. 29 No. 2 May 2012

105

5 考察
AS 間のトラフィック流量仮定と AS 規模：次数(隣接 AS 数) は従来から AS の規模を表す指標として用いられてきた [9] [11] [20]．一方，本論文で用いたAS 間のトラフィック流量仮定に基づき計算した AS
規模 nρ は，n = 0 のとき次数の定数倍となる．すな
わち，n = 0 のときのトラフィック流量仮定は従来研
図 8 CAIDA データセットを正解データセットとしたときの AS 規模の再帰計算回数とピアリング
推定時の AUC

究の AS の規模と一致している．一方，n = 0 のときのトラフィック流量仮定はランダムウォークモデルに等しく，本論文で採用したトラフィックの流量仮定ですると，明度から Valley-free 規則に従う経路の割合はこのランダムウォークモデルにおける遷移確率を隣が少ないことがわかる．これより，MAG3 により推接 AS の規模で重み付けをしたものである．この重み定用データセットに含まれなかった AS 間リンク対し

付けは，規模の大きな AS により多くのトラフィックて，より高精度に AS 間接続関係を推定できることがが流れることを意味しており，このことは AS 規模が示された．

扱うトラフィック量から定義されることからも妥当な仮定であると考える．本論文では，重み付け関数とし

4. 3 実インターネットトポロジーに対する
AS 規模の再帰計算の評価
本項では実インターネット上で計測した経路情報か
ら従来の発見的な AS 間接続関係の推定手法 [6] [7] にて単純に流出トラフィック量が隣接 AS の規模に比例すると仮定して，AS 間接続関係の推定に応用し高い推定精度を達成したが，重み付け関数については改善の余地があると考える．

より推定された AS 間接続関係データセット (CAIDA

再帰計算回数 n：CAIDA [4] の AS 間接続関係のデータセット) [4] を正解データセットとして用いた交推定結果を正解データセットとして n = {0, 1, 2, 3}

差検定を行うことで，提案手法における AS 規模の再について ROC 解析を行った我々の予備実験 [1] では，帰計算が実インターネットトポロジーに対しても有効

トランジットの推定においては n = 1，ピアリングのであることを示す．

推定においては n = 3 が最適値 (AUC を極大とする

図 8 に CAIDA データセットを正解データセットn) であった．一方，本論文のトポロジージェネレーとしたときの AS 規模の再帰計算回数とピアリング

タにより生成したトポロジーでは，どのトポロジーに推定時の AUC を示す．これより，2004 年 1 月 5 日

ついても n ≥ 2 に最適な再帰計算回数 n を持っておから 2010 年 1 月 20 日までの全てのデータに対して，り，図 4 に示したようにトポロジーごとに AUC を提案手法における AS 規模の再帰計算 (1 ≤ n ≤ 3) が極大とする再帰計算回数 n が異なる．しかし，本論

ピアリングの推定精度を向上していることがわかる．

文の評価結果を通じて，再帰計算回数として n = 3

CAIDA データセットで定義される AS 間接続関係もを用いて高い性能を得ることができており，実用上はAS パスの解析により推定したものであり，推定誤り

n = 3 を用いても問題がないことが示された．

が含まれる可能性があるため，この結果からの推定精AS 間接続関係推定における閾値 nτ ：本論文では，度の定量的な評価は困難であるが，トポロジージェネ

AS 規模距離 nδ から AS 間接続関係を推定する際のレータにより生成したトポロジーによる評価結果 (図閾値 nτ については，ROC 解析の結果から最適値を4(b)) の傾向と一致しているため，提案手法が実イン求めた．しかし，実際には正しい AS 間接続関係は公ターネットトポロジーに応用可能であることが定性的開されておらず，ROC 解析から閾値の最適値を求めに分かる．

ることができない．推定した AS 間接続関係をトラ106コンピュータソフトウェア

フィック最適化における経路のコスト計算 [2] などにn用いる場合は，AS 規模距離 δ を直接用いることができるが，経路ハイジャックの検出 [32] などへの応用の際には閾値を設定し，AS 間接続関係を推定する必要がある．トポロジーによって AS 規模距離 nδ の確率密度分布が異なっており，nτ の最適値を定めることは困難であるが，我々の予備実験 [1] で用いた階級
化 AS 規模距離 (Ranked magnitude distance) のよ
うに AS 規模距離を正規化することで閾値を経験的に定めることができると考える．最適閾値の発見については今後の課題とする．

6 むすび
本論文では，従来の AS 間接続関係の推定手法で用いられてきた経路情報を解析するのではなく，AS の隣接情報を表す全域部分グラフから定量化した AS 規
模の比に基づく AS 間接続関係の推定手法を提案し，その性能を評価した．トポロジージェネレータにより生成したトポロジーを評価に用い，提案手法により少数の計測点で取得した経路情報から AS 間接続関係，
特にピアリングを高精度に推定できることを示した．
また，従来手法では推定に用いる経路情報に含まれない AS 間リンクに対しては AS 間接続関係を推定できなかったが，本提案手法では AS 間接続関係の推定に経路情報ではなく AS 規模を用いることで，AS 規模の定量化に用いた全域部分グラフに含まれなかった

AS 間リンクに対しても AS 間接続関係が推定可能となることを 9 地点で計測された実インターネットの経路情報を用い，Valley-free 規則に従う経路の割合を比較することで示した．また，実インターネット上で計測した経路情報から推定した CAIDA による AS間接続関係データセット (CAIDA データセット) との交差検定により，提案手法が実インターネットトポ
ロジーに応用可能であることを示した．

謝辞 本論文の執筆にあたってコメントを頂きました国立情報学研究所福田健介氏に感謝します．

参 考 文 献[ 1 ] Asai, H. and Esaki, H.: Estimating AS Relationships for Application-Layer Traﬃc Optimization, in
3rd Workshop on Economic Traﬃc Management,
2010, pp. 51–63.
[ 2 ] Asai, H. and Esaki, H.: Towards Interdomain
Transit Traﬃc Reduction in Peer-assisted Content
Delivery Networks, in 14th International Telecommunications Network Strategy and Planning Symposium, 2010, pp. 95–100.
[ 3 ] Battista, G. D., Erlebach, T., Hall, A., Patrignani, M., Pizzonia, M. and Schank, T.: Computing the types of the relationships between
autonomous systems, IEEE/ACM Trans. Netw.,
Vol. 15, No. 2(2007), pp. 267–280.
[ 4 ] Cooperative Association for Internet Data Analysis: The CAIDA AS Relationships Dataset, http://www.caida.org/data/active/as-relationships/.
[ 5 ] Di Battista, G., Patrignani, M. and Pizzonia,
M.: Computing the types of the relationships between autonomous systems, in INFOCOM 2003.
Twenty-Second Annual Joint Conference of theIEEE Computer and Communications. IEEE Societies, Vol. 1, 2003, pp. 156–165.
[ 6 ] Dimitropoulos, X., Krioukov, D., Fomenkov,
M., Huﬀaker, B., Hyun, Y., kc claﬀy, and Riley, G.: AS relationships: inference and validation, SIGCOMM Comput. Commun. Rev., Vol. 37,
No. 1(2007), pp. 29–40.
[ 7 ] Dimitropoulos, X., Krioukov, D., Huﬀaker, B.,
kc claﬀy, and Riley, G.: Inferring AS Relationships:
Dead End or Lively Beginning?, Experimental andEﬃcient Algorithms, Lecture Notes in Computer
Science, Vol. 3503/2005, Springer Berlin / Heidelberg, 2005, pp. 113–125.
[ 8 ] Erlebach, T., Hall, A., Panconesi, A., andVukadinovi, D.: Cuts and Disjoint Paths in theValley-Free Path Model of Internet BGP Routing, Combinatorial and Algorithmic Aspects of
Networking, Lecture Notes in Computer Science,Vol. 3405/2005, Springer Berlin / Heidelberg, 2005,
pp. 49–62.
[ 9 ] Gao, L.: On inferring autonomous system relationships in the Internet, Networking, IEEE/ACM
Transactions on, Vol. 9, No. 6(2001), pp. 733–745.
[10] Gentle, J. E.: Matrix Algebra, Springer Texts in
Statistics, Springer New York, 2007.
[11] Govindan, R. and Reddy, A.: An analysis of Internet inter-domain topology and route stability, in
INFOCOM ’97. Sixteenth Annual Joint Conferenceof the IEEE Computer and Communications Societies. Proceedings IEEE, Vol. 2, 1997, pp. 850–857.
[12] Griﬃn, T. and Huston, G.: BGP Wedgies, RFC
4264 (Informational), 2005.
[13] Hawkinson, J. and Bates, T.: Guidelines for creation, selection, and registration of an Autonomous
System (AS), RFC 1930 (Best Current Practice),
1996.

Vol. 29 No. 2 May 2012[14] Huang, C., Li, J. and Ross, K. W.: Can internet
video-on-demand be proﬁtable?, in SIGCOMM ’07:
Proceedings of the 2007 conference on Applications,
technologies, architectures, and protocols for computer communications, New York, NY, USA, ACM,
2007, pp. 133–144.
[15] Labovitz, C., Ahuja, A., Bose, A. and Jahanian,F.: Delayed Internet routing convergence, in Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer
Communication, SIGCOMM ’00, New York, NY,
USA, ACM, 2000, pp. 175–187.
[16] Mahadevan, P., Hubble, C., Krioukov, D., Huffaker, B. and Vahdat, A.: Orbis: rescaling degreecorrelations to generate annotated internet topologies, SIGCOMM Comput. Commun. Rev., Vol. 37,
No. 4(2007), pp. 325–336.
[17] Medina, A., Lakhina, A., Matta, I. and Byers, J.:
BRITE: an approach to universal topology generation, in Modeling, Analysis and Simulation of Computer and Telecommunication Systems, 2001. Proceedings. Ninth International Symposium on, 2001,
pp. 346–353.
[18] Merit Network, Inc.: Internet Routing Registry,
http://www.irr.net/.
[19] Mühlbauer, W., Feldmann, A., Maennel, O.,
Roughan, M. and Uhlig, S.: Building an AStopology model that captures route diversity, inProceedings of the 2006 conference on Applications,
technologies, architectures, and protocols for computer communications, SIGCOMM ’06, New York,NY, USA, ACM, 2006, pp. 195–206.
[20] Nakao, A., Peterson, L. and Bavier, A.: A routing underlay for overlay networks, in SIGCOMM’03: Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols forcomputer communications, New York, NY, USA,ACM, 2003, pp. 11–18.
[21] Norton, W.: Internet service providers and peering, in Proceedings of NANOG, Vol. 19, 2001, pp. 1–
17.
[22] Rekhter, Y., Li, T. and Hares, S.: A Border
Gateway Protocol 4 (BGP-4), RFC 4271 (Draft
Standard), 2006.
[23] Réseaux IP Européens Network Coordination Centre: Routing Information Service (RIS),
http://www.ripe.net/projects/ris/.
[24] Roughan, M., Tuke, S. J. and Maennel, O.: Bigfoot, sasquatch, the yeti and other missing links:
what we don’t know about the AS graph, in IMC’08: Proceedings of the 8th ACM SIGCOMM conference on Internet measurement, New York, NY,
USA, ACM, 2008, pp. 325–330.
[25] Shakkottai, S. and Srikant, R.: Economics of
network pricing with multiple ISPs, IEEE/ACM
Trans. Netw., Vol. 14, No. 6(2006), pp. 1233–1245.
[26] Subramanian, L., Agarwal, S., Rexford, J. andKatz, R.: Characterizing the Internet hierarchy

107

from multiple vantage points, in INFOCOM 2002.
Twenty-First Annual Joint Conference of the IEEE
Computer and Communications Societies. Proceedings. IEEE, Vol. 2, 2002, pp. 618–627.
[27] University of Oregon: Route Views Project,
http://www.routeviews.org/.
[28] Varga, R. S.: Matrix Properties and Concepts,
Matrix Iterative Analysis, Springer Series in Computational Mathematics, Vol. 27, Springer Berlin
Heidelberg, 2009, pp. 1–30.
[29] Wang, F. and Gao, L.: On inferring and characterizing Internet routing policies, in IMC ’03: Proceedings of the 3rd ACM SIGCOMM conference on
Internet measurement, New York, NY, USA, ACM,
2003, pp. 15–26.
[30] Winick, J. and Jamin, S.: Inet-3.0: Internet
Topology Generator, Technical Report UM-CSETR-456-02, EECS, University of Michigan, 2002.
[31] Xia, J. and Gao, L.: On the evaluation of AS
relationship inferences [Internet reachability/traﬃc
ﬂow applications], in Global Telecommunications
Conference, 2004. GLOBECOM ’04. IEEE, Vol. 3,
2004, pp. 1373–1377.
[32] Zhang, Z., Zhang, Y., Hu, Y. C., Mao, Z. M. andBush, R.: iSpy: detecting IP preﬁx hijacking on myown, SIGCOMM Comput. Commun. Rev., Vol. 38,
No. 4(2008), pp. 327–338.

付録 A 確率遷移行列の固有ベクトルと次数第 3. 1 項で説明した AS 規模 nρ は n = 0 のとき隣接 AS 数 (次数) に比例する．つまり，AS 規模ベクト
ル nρ は次数ベクトルの定数倍となる．本付録では，

AS 規模ベクトル nρ が次数ベクトルの定数倍となることを証明する．

n = 0 のとき，式 (3) により定義される重み付き隣接行列 0W は，重み付けを行わない隣接行列となる．
 
本付録では，A := 0W = aij として説明する．また，隣接行列から式 (4) により定義される確率行列
0

T を確率遷移行列 P として扱う．つまり，確率遷移
a
行列 P を P := 0T  ijaと定義する．インターkik

ネットにおける AS グラフまたはその全域部分グラフは強連結であるため，隣接行列 A および確率遷移行
列 P は既約な m 次正方行列である [28]．
以下で，確率遷移行列 P の最大固有値に対応する
固有ベクトルが，次数ベクトルであることを証明する．

Proof. 次数ベクトル d を d := [d1 , . . . , dm ] と定義する．ここで，強連結なグラフを用いているため，d は

108

コンピュータソフトウェア

正ベクトル (d > 0) である．まず，次数ベクトル dは確率遷移行列 P の最大固有値に対応する左固有ベが確率遷移行列 P の最大固有値に対応する固有ベク

クトルであることが示された．
次に，逆を示す．確率遷移行列 P は既約であるのトルであることを示す．
行列 P の固有方程式は，x を左固有ベクトル，λ を固有値として次のように与えられる．

xP = λx(9)

ここで，AS i の次数 di は，


di =
aik =
aki

(10)

k

で，Perron-Frobenius 定理より，既約な非負行列の最大固有値は単純となるため，λ = 1 に対応する固有ベクトルは唯一である．よって，次数の定数倍ベクト
ル cd が確率遷移行列 P の最大固有値に対応する唯一の固有ベクトルとなる．

kとなる．次数ベクトル d が確率遷移行列 P の左固有
浅井大史

ベクトルになると仮定して，

x = cd(c: const., c = 0)

2008 年東京大学工学部電子情報卒．

(11)

2010 年同大学大学院情報理工修士課
程了．現在，同大学院情報理工博士を式 (9) へ代入する．式 (9) の左辺 xP は，課程在学中．主としてインターネッ

xP = cdPa= c [d1 , . . . , dm ]  ija
k ik


aki
=
k cdk dk 
= c k aki
= c [d1 , . . . , dm ](

トトポロジおよびネットワークドメイン間における経aik = di )

k

(



フィックの最適化に関する研究に従事．

aki = di )

k

= cd

済関係の解析，分散システムにおけるドメイン間トラ

(12)

江崎

浩

1987 年九州大学大学院工学部電子工学科修士課程了．同年 (株) 東芝入となる．一方，式 (9) の右辺 λx は，(13)社．1990 年米国ニュージャージ州ベ

Perron-Frobenius 定理 [10] より，確率遷移行列 P に員研究員．1998 年東京大学大型計算機センター助教

は最大固有値を 1 とする固有ベクトルが存在する．

授．2001 年同大学大学院情報理工学系研究科助教授．

つまり，確率遷移行列 P の最大固有値は 1 である．

2005 年同教授，現在に至る．工学博士 (東京大学)．

λ = 1 のとき，式 (12)，式 (13) より，固有方程式 (式MPLS-JAPAN 代表，IPv6 普及・高度化推進協議会(9)) を満足する．よって，次数の定数倍ベクトル cd専務理事，JPNIC 理事．

λx = λcdとなる．

ルコア社．1994 年コロンビア大学客