フロー階層に着目したインターネットトポロジーの成長過程の - 村田研究室

社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,
INFORMATION AND COMMUNICATION ENGINEERS
信学技報
TECHNICAL REPORT OF IEICE.
フロー階層に着目したインターネットトポロジーの成長過程の分析
中田
侑†
荒川
伸一†
村田
正幸†
† 大阪大学 大学院情報科学研究科 〒 565–0871 大阪府吹田市山田丘 1–5
E-mail: †{y-nakata,arakawa,[email protected]
あらまし
通信需要の増加に伴い、インターネットのトポロジーは大規模化し続けている。インターネットを構成す
る AS レベルトポロジーの構造がどのように成長しているかを明らかにすることは、ネットワークの拡張を行う際や、
プロトコルやアプリケーションのパフォーマンス分析などを行う上で有用である。そこで本稿では、AS レベルトポロ
ジーの構造的成長を明らかにした。特に、トラヒックが集約されて負荷が集中しやすい AS がトポロジーのどこに位
置するのかを明らかにするため、AS レベルトポロジーを、リンクで密に繋がれた AS の集合への分割を繰り返すこと
で導かれるフロー階層と呼ばれる階層構造を抽出し、その構造の変化を示す。また、AS の次数に基づくグラビティモ
デルによりトポロジーに通信需要を与えた場合に、トラヒックが集中する箇所を示す。これにより、フロー階層の構
造は、トポロジーが大規模化するにつれ、幅の広がるように成長しており、一部の AS にトラヒックが集中する傾向
にあることがわかった。また、近年ではフロー階層の 2 階層におけるリンクに、トラヒックがより集中する傾向にあ
ることがわかった。
キーワード
AS レベルトポロジー、フロー階層、AS(Autonomous System)、Tier-1
Analyzing the evolution of the Internet topology from a hierarchical flow
perspective
Yu NAKATA† , Shin’ichi ARAKAWA† , and Masayuki MURATA†
† Graduate School of Information Science and Technology, Osaka University
1–5 Yamadaoka, Suita, Osaka 565–0871, Japan
E-mail: †{y-nakata,arakawa,[email protected]
Abstract The scale of topology in the Internet is becoming larger corresponding to increase of traffic demand.
Understanding how the AS level topology has been evolving is important for network design and analyzing performance of applications and protocols. In this paper, we investigate the evolution of the Internet topology. In
particular, we focus on the flow hierarchy in the Internet topology, which describes where ASes accommodating
heavy traffic are in the topology. The flow hierarchy is the hierarchical structure derived from recursively splitting
the topology into some subset of ASesa that are densely connected with many links. Our finding is that the width
of the containment hierarchy is becoming larger, but the depth of the containment hierarchy is almost constant.
This fact suggests that a part of ASes aggregates more amount of traffic and suffers from overload. Furthermore,
we show that more traffic tends to be aggregated at the links in second level of flow hierarchy.
Key words AS-level topology, Flow hierarchy, AS(Autonomous System), Tier-1
1. は じ め に
インターネットは社会インフラとしての役割を担っており、
の設計者が他のネットワークとリンクを構築する際、独自のポ
リシーによりリンクを繋ぐ先のネットワークを選択しているた
め、必ずしもネットワーク全体の性能向上は意識されていない。
通信需要や接続する情報端末の数は増加の一途をたどってい
インターネットには、インターネット全体を制御する管理者が
る。それに伴い、ネットワーク機器や回線の追加や増強が行わ
存在しないため、現在のインターネットトポロジーの構造的特
れ、現在もなおインターネットは成長し、インターネットを構
徴は明白ではない。しかしながら、トポロジーが持つ構造的特
成するトポロジーは大規模化し続けている。あるネットワーク
徴の違いにより、ネットワーク機器に流れるトラヒック負荷や
—1—
通信品質の向上、規模拡張の容易さなどのネットワークの性能
て、AS レベルトポロジーの構造的特徴について研究されてき
も大きく異なることが指摘されている [1]。そのため、通信事
た。Faloutsos らにより、AS レベルトポロジーは次数分布がべ
業者が新たに回線やネットワーク機器を構築する際には、イン
き則に従うことが明らかにされている [5]。また、AS に流れる
ターネットトポロジーの構造的特徴を踏まえた設計が必要であ
トラヒックの媒介中心性の分布もべき則に従うことが知られて
る。また、新たなアプリケーションやプロトコルを開発する際
いる [6]。ただしこれらの分析では、成長過程の一点を取り出し
には、インターネットトポロジーの構造的特徴を反映した環境
てそのトポロジーの構造的特徴を分析しているにすぎず、トポ
下でアプリケーションやプロトコルの性能分析を行う必要があ
ロジーの大規模化に伴う構造の変化については明らかにされて
る。そのため、現在のインターネットトポロジーの構造や、イ
いない。これに対し、Dhamdhere らは AS やリンクの数、ま
ンターネットトポロジーの成長を分析し、将来の構造的特徴を
た AS 間の平均ホップ数などの経年変化を示すことで、AS レ
理解する必要がある。そこで本稿では、現在のトポロジーが持
ベルトポロジーの構造的成長を分析しており [4]、また Shavitt
つ構造的特徴を明らかにし、さらにインターネットの成長過程
らは ISP や Hyper Giants の次数の変化に着目し、AS レベル
を分析する。
トポロジーの成長を分析している。しかしながら、AS の次数
インターネットは、AS(Autonomous System) と AS 同士を
などのグラフメトリックによる分析のみではネットワーク性能
繋ぐリンクによって構成されている。このトポロジーは AS レ
を示すことができない。例えば、同じ次数分布を有する二つ
ベルトポロジーと呼ばれ、非常に多数の AS の相互接続による
のネットワークが存在した場合でも、他の構造的特徴の違いに
大規模かつ複雑なグラフを形成している。AS とは、通信事業
よって、ネットワークに流れるトラヒックを収容するために必
者や研究組織、コンテンツプロバイダーが保有・運用する自律
要なネットワーク機器の設備量が異なる。
したネットワークである。AS レベルトポロジーに含まれるリ
ネットワークの性能は AS の次数だけではなくトラヒックの
ンクには、そのリンクの両端の AS で交わされる契約により、
集約にも依存しており、ある AS で生成されたトラヒックが目
ピアリングリンクとトランジットリンクの 2 種類が存在する。
的の AS に到達するまでに集約される回数や、トポロジー上で
ピアリングリンクは、リンクに隣接する AS 間で、任意の AS
集約が行われる箇所などによって特徴づけられる。そこで本稿
宛てのトラヒックを無償で転送するリンクであり、同等のネッ
では、多くのリンクにより密に連結した AS の集合に着目し、
トワーク規模を持つ AS の間に構築される場合が多い。またト
AS レベルトポロジーの構造を分析する。ここでは、この AS
ランジットリンクは、ある AS がインターネット内の任意の AS
の集合をモジュールと呼ぶ。AS レベルトポロジーはモジュー
にトラヒックを中継することを、相手側の AS に有償で委託す
ルの連結により構成され、複数のモジュールの間は、少数の
る際に用いられるリンクである。トラヒックの中継を委託する
リンクによって連結されている。そのためモジュール間のリン
AS が相手側の AS に支払う料金はトランジット料と呼ばれ、一
クでトラヒックが集約される。各々のモジュールは、小さなモ
般にトラヒック量に応じて金額が決定する。各 AS は少ないコ
ジュールの連結によって構成されており、さらにそれらの小さ
ストで良好な通信を確保するために、同程度のトラヒックを処
なモジュールもより小さいモジュールの連結により構成される。
理している AS とはピアリングリンクを繋ぎ、その他の AS と
このようにして得られるモジュールの階層構造を、本稿ではフ
はトランジットリンクを繋ぐことによりネットワークの接続性
ロー階層と呼ぶ。取得可能であった過去 12 年間の AS レベル
を確保している。
トポロジーのデータから、AS レベルトポロジーのフロー階層
AS レベルトポロジーでは、Tier-1 と呼ばれる少数の AS が他
の構造やその経年変化を分析することによって、トポロジーの
の Tier-1 の AS とピアリングリンクを繋いでおり、多くのトラ
大規模化に伴う構造の変化について明らかにする。さらに、AS
ヒックを処理している。また、Tier-2 と呼ばれる AS が Tier-1
レベルトポロジーにおいてトラヒックが集中する箇所の特定を
の AS とトランジットリンクを繋いでおり、さらに Tier-2 の
行うため、各 AS に対して、AS の次数に基づくグラビティモ
AS が他の AS とトランジットリンクをつなぐことで、AS レベ
デルにより通信需要を与え、その際の AS レベルトポロジーの
ルトポロジーは階層構造を有することが知られている。また近
各リンクに流れるトラヒック量を示す。
年、Hyper Giants と呼ばれる多量のトラヒックを送出するコ
本稿の構成は、以下の通りである。2 章では本研究の分析に
ンテンツプロバイダーが台頭しており、Hyper Giants によっ
用いたデータの取得方法について述べ、3 章ではフロー階層の
て流されるトラヒック量がインターネット全体に流れるトラ
抽出方法、及びフロー階層の構造やその経年変化について述べ
ヒック量の約 30%を占めていることが報告されている [2]。さ
る。4 章では各 AS に対し、AS の次数に基づくグラビティモデ
らに、Hyper Giants と他の ISP との間でピアリングリンクが
ルにより AS の通信需要を与え、その際にトラヒックが集中す
メッシュ状に構築されていることが指摘されている [3]。
るリンクについて述べる。最後に 5 章で本稿のまとめと今後の
ISP が他の ISP とリンクを構築する際や、アプリケーション
やプロトコルの性能分析を行う際には、上記のトポロジーの構
造的特徴を明らかにする必要がある。現在に至るまで、トポロ
ジーの構造を明らかにするために、AS レベルトポロジーを視
課題を述べる。
2. データセット
2. 1 AS の隣接関係
覚化する研究が行われているが、AS レベルトポロジーは 2012
AS レベルトポロジーの成長を分析するためには、定期的に
年 12 月現在で AS の数が 42,009、リンク数が 93,470 本存在
記録されたトポロジー情報が必要である。しかしながら、AS
し、大規模かつ複雑であるため、視覚化されたトポロジーマッ
の隣接関係などを記した情報は記録されていないため、AS レ
プを用いてもトポロジーの構造的特徴を直観的に捉えることは
ベルトポロジーを観測して全体像を推定する手法が研究されて
出来ない [4]。そのためこれまで様々なグラフメトリックを用い
きた。AS レベルトポロジーの接続関係を推定する手法には大
—2—
表 1 ノード数、リンク数、AS パス数の経年変化
者から得られたリンクの種類がどの程度一致するかを調べるこ
とで、有効性を示している。[14] による手法では 99.1%の精度
2000/6/15 2004/6/15 2008/6/15 2012/6/15
AS 数
リンク数
AS パス数
8,162
18,015
29,320
42,009
17,533
40,205
64,305
93,470
299,434
1,108,704
1,901,745
2,605,770
でリンクの種類を推定することが可能であり、本稿ではこの手
法の推定結果を利用している。
2. 3 AS の分類
Tier-1 や Hyper Giants といった階層ごとに、トポロジーの
構造的特徴を捉えるため、AS を Tier-1, sub Tier-1, Tier-2,
分して 2 種類存在する。
• 任意の場所から送られる多数の traceroute パケットから
推定する手法 [7, 8]
• BGP テーブルに記載された AS パスから AS 間の隣接
関係を推定する手法 [9, 10]
Tier-3, Hyper Giants, Academic, non Layer の 7 種類に分類
する。sub Tier-1 は、Tier-1 か Tier-2 かの判断が分かれている
AS や過去は Tier-1 と認識されていたが現在は Tier-2 の AS、
またその逆の AS が含まれる。
ピアリングリンクは組織の規模や保有するコンテンツ量、送
一つ目の手法では、世界中の多数の端末から特定の端末へ
信するトラヒック量などが同等な AS の間に繋がれるリンクで
traceroute パケットを送信し、traceroute パケットの通った経
あるため、ピアリングリンクで構成された連結成分は一つの階
路を記録し、それらを収集する。その後、IP アドレスから AS
層と見なすことができる。そこで、ピアリングで構成された連
番号を変換することで AS レベルトポロジーを生成する。こ
結成分を抽出し、各連結成分に含まれる AS の企業名を確認す
の手法を用いることで、AS レベルトポロジーのリンクを多く
ることで、それぞれの連結成分の階層を決定する。ピアリング
計測することが可能であるが、traceroute の送信は、善意に
リンクを持たない AS は、non Layer とする。non Layer に含
よりこの推定に協力した参加者により行われ、分析期間中に
まれる AS の多くは、小規模のネットワークを持つ ISP やアプ
traceroute パケットを送信する端末の位置が異なる可能性があ
リケーションサービスプロバイダーである。
る。同じネットワークであっても、計測時刻によって得られる
トポロジーが異なるため、AS レベルトポロジーの成長に関す
る分析には適していない。
3. フロー階層
3. 1 フロー階層の抽出方法
二つ目の手法では、ある ISP が保有するゲートウェイルー
フロー階層の分析を行い、トラヒック集約の階層性を明らか
ターの BGP テーブルを収集し、BGP の AS パス情報から AS
にするために、AS レベルトポロジーからフロー階層を抽出す
レベルトポロジーを推定する手法である。この方法では、大
る。まず AS レベルトポロジーを複数のモジュールに分割する。
部分の AS を観測することは可能だが、予備のトランジットリ
分割されたモジュールを、さらに複数のモジュールに分割する。
ンクとピアリングリンクのうち、40%以上が観測できないとい
これを繰り返すことで、フロー階層を得る。
う欠点がある [4, 11]。ただし、ゲートウェイルーターの BGP
モジュールへの分割は、文献 [15] の手法に基づき行っている。
テーブルを提供している ISP は、収集を始めた時点から現在に
トポロジーの分割 P が与えられたとき、モジュール内の AS
かけて基本的に変わっていない。そのため、AS レベルトポロ
を繋ぐリンクが密であり、異なるモジュール間を繋ぐリンクが
ジーの成長の分析には適している。また、トラヒック集約は、
疎であるほど、高い値を示す指標であるモジュラリティM (P )
下位層にある複数の AS のトラヒックがトランジットリンクを
を用いて、モジュラリティを最大化するようにトポロジーをモ
経由して上位層の AS が受け取る際に行われる。BGP テーブ
ジュールに分割する。これ以降では、モジュール内の AS を繋
ルの AS パス情報を用いる手法は、ピアリングリンクを全て観
ぐリンクをモジュール内リンク、異なるモジュール間を繋ぐリ
測することは不可能であるが、トランジットリンクの大部分は
ンクをモジュール間リンクと呼ぶ。モジュラリティは式 (1) で
取得することが可能であるのため、トラヒックの集約に着目し
定義され、式中の変数の説明を表 2 に記載している [16]。
た本稿の分析に用いることができる。そこで本稿では、この手
法により得られたトポロジーの情報を利用する。
BGP パス情報は、RouteViews Project の route-views.routeviews.org サーバーと RIPE NCC の rrc00.ripe.net サーバーで
M (P ) =
ki kj
1 ∑
[Aij −
]δSi Sj
2m
2m
(1)
ij
モジュラリティM (P ) の値は、モジュール内リンクが密で、モ
収集されたものを用いている。これらのサーバーは複数の ISP
ジュール間リンクが疎なグラフであるほど 1 に近づき、完全
のゲートウェイルーターが保持している BGP テーブルのデー
グラフやスター型グラフのようにリンクが一様に張られ、モ
タを収集しており、稼働が開始された年は、それぞれ 1997 年
ジュールが存在しないグラフでは 0 である。
と 1999 年である。表 1 に、取得された BGP テーブルに含ま
ここでは、AS レベルトポロジーを 1 回モジュール分割する
れていた AS パス数と、生成した AS レベルトポロジーの AS
ことで得られるモジュールの集合を、Containment Level 1(今
数、リンク数をまとめている。
後、CL1 と略す) のモジュール群と呼び、CL1 のモジュールを
2. 2 トランジットリンクとピアリンクリンクの推定情報
さらにモジュール分割して得られるモジュール群を CL2 のモ
AS 間のリンクの種類がトランジットリンクかピアリングリ
ジュール群と呼ぶ。各 CL がフロー階層の各階層に相当する。
ンクかは公表されていない。そこで AS レベルトポロジーの
分析のために、リンクの種類を推定する手法が提案されてい
る [12–14]。リンクの種類を推定する手法の多くは、考案した
アルゴリズムで推定したリンクの種類と、あらかじめ通信事業
フロー階層の抽出は、以下の方法によって行われる。
( 1 ) AS レベルトポロジーをモジュールに分割し、CL1 の
モジュール群を生成する。
( 2 ) CL1 のモジュール群のうち、モジュラリティが 0 より
—3—
表2
1
モジュラリティ( 2m
∑
ij
[Aij −
ki kj
2m
]δSi Sj ) の定義式内に現れ
表3
各 AS に隣接するモジュール間リンクの数
e1
る変数の説明
989.54
e2
e3
e4
e5
e6
変数
説明
Tier-1
158 624.31 0.54 22.77
0
m
総リンク数
sub Tier-1 191.03 75.23 160.82 2.31 14.31
0
i, j
ノード
Tier-2
52.76 29.39
52.63 0.93
7.74 0.03
Aij
隣接行列の要素。ノード ij 間にリンクがある場合は
Tier-3
16 11.33
33.08 0.58
2.42 0.17
1、ない場合は 0 をとる。
ki
ノード i の次数
Si
ノード i が属するモジュール
Tier-1
δSi Sj Si と Sj が等しい場合 1、異なる場合に 0 をとる変数
120
Tier-2
Tier-1
sub Tier-1
Tier-2
Tier-3
Hyper Giants
Academic
100
80
AS数
sub Tier-1
Tier-3
&/भঔ४গ‫ش‬ঝ
&/भঔ४গ‫ش‬ঝ
図 2 モジュールに分割した AS レベルトポロジーの概略図
60
表4
40
Year CL1
20
0
0
10
20
30
モジュール
40
50
図 1 CL1 の各モジュールに含まれる AS の種類と数
一つのモジュールに含まれる AS の数
CL2
CL3
CL4 CL5 CL6
2000 224.97 24.78 8.41
4.01 3.22 2
2002 424.32 35.73 9.81
4.32 3.35 2.75
2004 414.07 37.84 10.41 4.67 3.59 3.5
2006 528.33 43.54 11.25 5.43 3.59 2
2008 695.98 57.18 12.20 6.20 3.71 2
2010 841.98 69.16 12.26 5.71 3.81 2.166667
大きいモジュールはさらにモジュール分割し、CL2 のモジュー
2012 915.93 73.31 12.93 6.36 3.74 2.892857
ル群を生成する。
( 3 ) CL2 以上の階層で (2) の手順を繰り返す。
の概略図を示しており、異なる階層の AS を繋ぐリンクや同一
3. 2 フロー階層の構造
の階層の AS を繋ぐリンク、各階層に含まれるノードの 1/5 を
フロー階層を用いてトラヒック集約の分析を行うために、ま
抽出し、AS を階層ごとに配置している。図 2 より AS レベル
ず AS レベルトポロジーにおけるフロー階層の構造を明らかに
トポロジーでは、Tier-1 などの上位層の AS は、自身が属する
する必要がある。そこで、AS レベルトポロジーをモジュール
モジュールのトラヒックを集約して、他のモジュールに伝送す
に分割した際、各モジュールがどのような種類の AS で構成さ
る構造になっている。
れているかを確認した。図 1 に、2012 年の AS レベルトポロ
ジーの CL1 モジュールに含まれる AS の種類とその数を示し
ている。
3. 3 フロー階層の経年変化
トポロジーの大規模化に伴う、フロー階層における構造の変
化を調査したところ、図 2 のような階層構造において深さより
図 1 より、それぞれのモジュールには複数の種類の AS が含
も幅が広がるように成長していることが分かった。2000 年か
まれており、AS が種類ごとにまとまってはいないことが分か
ら 2012 年にかけて AS の数は約 5 倍、BGP パスの総数は約 9
る。なお、この傾向は CL2 以降の階層のモジュールにおいて
倍に増えているが、AS レベルトポロジーをモジュール分割で
も存在することを確認している。
きる回数は 2002 年から 2012 年にかけて 6 回であり変化がな
次に、モジュール間リンクを持つ AS の種類を確認した。表
い。よって、フロー階層は幅が広がるように成長していると言
3 に、各 AS が持つ他のモジュールとのリンク数を、階層ごと
える。フロー階層の幅が広がると、一つのモジュール内の AS
にまとめて示している。ex は、一つの AS に隣接する CLx の
数が増え、モジュール間リンクにより多くのパスが経由するこ
モジュール間リンクの数の平均を表している。表 3 において、
とになる。表 4 に、各 CL における一つのモジュールに含まれ
ex の値が上位の階層ほど値が高くなっていることから、Tier-3
る AS の数の平均を示している。2000 年から 2012 年にかけて、
のような下位層の AS に比べ、Tier-1 のような上位層の AS の
一つのモジュールに含まれる AS の数は、CL1 のモジュールで
方がモジュール間リンクを多く持つ傾向にあることが分かる。
は 4.07 倍、CL2 のモジュールでは、2.96 倍に増えている。そ
一つのモジュールに複数の種類の AS が存在し、さらに上位
のため、モジュール間リンクでは、より多くのトラヒックが集
の AS がモジュール間リンクを多く持つことから、AS レベル
約され、モジュール間リンクに隣接する AS では、トラヒック
トポロジーをモジュール分割すると、図 2 のようなモジュール
の負荷が高まると考えられる。
に切り分けられる。図 2 では、2012 年の AS レベルトポロジー
トラヒックの集中が高まっているモジュール間リンクが、ど
—4—
16
CL1
CL2
CL3
CL4
CL5
12
10
Ti
१ঈঔ४গ‫ش‬ঝਯ
14
8
6
4
2
0
2002
2004
2006
2008
2010
2012
2e+006
1.8e+006
1.6e+006
1.4e+006
1.2e+006
1e+006
800000
600000
400000
200000
0
2002 2004 2006 2008 2010 2012
ফ
図3
CL1 (x=1)
CL2 (x=2)
CL3 (x=3)
CL4 (x=4)
CL5 (x=5)
CL6 (x=6)
ফ
一つのモジュールに含まれるサブモジュールの数
図 4 各モジュール間リンクに流れるトラヒック量の平均
の CL に多く存在するかを確認した。図 3 に、一つのモジュール
の中に含まれるサブモジュールの数の推移を示している。2008
年頃までは、CL1 のモジュール内に含まれるサブモジュール
(CL2 のモジュール) の数は増加傾向にあった。しかしながら
2008 年頃以降は減少傾向にある。これに対し、CL2 のモジュー
ルではサブモジュールである CL3 のモジュールの数が 2000 年
から 2012 年にかけて、継続して増加している。そのためトラ
ヒックの集中は、CL1 のモジュール間リンクよりも CL2 のモ
ジュール間リンクで高まる傾向にあることが分かる。
が送出するトラヒック量は、ISP が送出するトラヒック量の約
895 倍であることが分かる。よって、コンテンツプロバイダー
の場合は、次数に対して 895 倍した値を送出するトラヒック量
とする。本稿では Google と Akamai を Hyper Giants とみな
している。
4. 2 リンクに流れるフロー量の分布
通信需要を 4. 1 節のように与え、モジュール間リンクに流れ
るトラヒック量の経年変化を示す。図 4 では、各モジュール間
リンクに流れるトラヒック量の平均を、CL ごとに示している。
4. フロー階層の経年変化
CL x に属する二つのモジュールを繋ぐモジュール間リンクの
集合を Lx とし、リンク集合 Lx に含まれるリンク lx に流れる
4. 1 リンクに流れるトラヒック量の決定
AS レベルトポロジーが大規模化しトポロジーに流れるトラ
ヒック量が増えた際に、トラヒック負荷が上昇する箇所を明ら
かにする。3. 2 節の結果より、AS レベルトポロジーは、トポロ
トラヒック量を T (lx ) とすると、CL x のモジュール間リンク
に流れるトラヒック量の平均 Tx は式 (3) のように表される。図
4 は、Tx を 3ヶ月ごとにプロットしている。
ジーの成長に伴いモジュール間リンクにトラヒックが集中する
構造であることが判明したため、ここではモジュール間リンク
に流れるトラヒック量を示す。しかしながら、AS レベルトポ
ロジーの各リンクに流れるトラヒック量などを記した情報は記
録されていないため、本稿では文献 [17] に示された、グラビ
ティモデルによる推定手法を用いて、AS レベルトポロジーの
各 AS に通信需要を与える。
∑
Tx =
lx ∈Lx
T (lx )
|Lx |
(3)
図 4 から、上位層のモジュール間リンクほど流れるトラヒッ
クの量が多いことが分かる。また、2011 年頃より CL2 のモ
ジュール同士をつなぐリンクで、より多くのトラヒックが流れ
る傾向にあることが分かる。これは、より下の階層でトラヒッ
文献 [17] におけるグラビティモデルは以下の式によって表現
される。
ク集約が行われる傾向にあることを示している。2011 年頃か
ら CL2 のモジュール間のリンクでトラヒック量が増大した要
Tout (Ij )
Xij = Tin (Ii ) ∑
T (I )
k out k
(2)
因として、CL2 に比べ CL3 と CL4 のモジュール数の増加が考
えられる。図 5 に、各 CL のモジュールの数の経年変化を示し
Xij は AS ij 間の対地間トラヒック量、Tin (Ii ) は AS i に流入
ており、CL2 のモジュール数がほぼ一定の値をとっているのに
するトラヒック量、Tout (Ij ) は AS j が送出するトラヒック量
対し、CL3 と CL4 のモジュールの数は増大していることが分
を表しており、
Tout (Ik ) はネットワーク全体に流れるトラ
かる。また特に、CL4 のモジュールの数は 2011 年ごろより大
ヒック量を意味している。ここでは、各々の AS が送出するト
きく増大している。増加した CL3 と CL4 のモジュールのトラ
ラヒック量と流入するトラヒック量は、AS の次数に比例する
ヒックを、CL2 のモジュール間リンクが集約するため、CL2 の
と仮定して計算を行う。その後、AS 間のルーティング行列か
モジュール間リンクに流れるトラヒック量が 2011 年頃より増
ら、各リンクに流れるトラヒック量を求める。
大したと考えられる。
∑
k
AS が Hyper Giants の場合は、送出するトラヒック量を他
5. お わ り に
の AS よりも多く設定する。文献 [17] の手法では、トポロジー
内の AS を分類していないため、同じ次数の ISP とコンテン
ネットワークを拡張する際やプロトコルの性能を測るために、
ツプロバイダーは、同じトラヒックを送出することになる。し
現在のネットワークの構造がどのように変化してきたのかを理
かしながら、Cisco 社が試算 [18, 19] した全世界に流れる総ト
解する必要がある。特に、ネットワークの性能はトラヒックが
ラヒック量や、データセンターとユーザー間でのトラヒック量
トポロジーのどこで集約されるかに依存するため、トラヒック
のデータより、Hyper Giants などのコンテンツプロバイダー
集約の階層性を明らかにしなければならない。そこで本稿では、
—5—
3500
CL1
CL2
CL3
CL4
CL5
CL6
ঔ४গ‫ش‬ঝਯ
3000
2500
2000
1500
1000
500
0
2002
2004
2006
2008
2010
2012
ফ
図5
各 CL に存在するモジュールの数
モジュール分割を繰り返すことで得られるフロー階層に基づき、
トポロジーにおいてトラヒックが集約される箇所を分析した。
分析により、AS レベルトポロジーが大規模化するにつれ、
フロー階層の各モジュールに含まれる AS の数が増大すること
が明らかとなり、フロー階層の構造は幅が広がるように変化し
ていることが分かった。また、一つのモジュールの中に含まれ
るサブモジュールの数が、CL1 のモジュールでは、2004 年ご
ろからほぼ一定であるのに対し、CL2 のモジュールでは継続し
て増加していることが明らかとなった。これにより、トラヒッ
クは CL2 のモジュール間リンクでより集中されるように、構
造が変化していることを表している。さらに、AS の次数に基
づくグラビティモデルにより各 AS に対地間通信需要を与えた
場合、2011 年頃より CL2 のモジュール間リンクに流れるトラ
ヒック量の増加量が増えてことが明らかとなった。これは、ト
ポロジーが大規模化するにつれ CL3 と CL4 のモジュール数が
増大しており、特に CL4 のモジュールが 2011 年ごろより大き
く増大しているためであると考えられる。
今後は、一部のネットワークへのトラヒックの集中を避ける
ために最適な、インターネットトポロジーの成長を前提にした
トポロジーの設計指針を明らかにする。
謝
辞
本研究の一部は、科学研究費補助金基盤研究 (A)24240010 に
よっている。ここに記して謝意を表す。
文
[7] Y. Shavitt and E. Shir, “DIMES: Let the Internet measure
itself,” in Proceedings of ACM SIGCOMM, vol. 35, pp. 71–
74, Oct. 2005.
[8] H. V. Madhyastha, T. Isdal, M. Piatek, C. Dixon, T. Anderson, A. Krishnamurthy, and A. Venkataramani, “iPlane:
An information plane for distributed services,” in Proceedings of USENIX Symposium on Operating Systems Design
and Implementation, vol. 7, pp. 367–380, Nov. 2006.
[9] Q. Chen, H. Chang, R. Govindan, S. Jamin, S. J. Shenker,
and W. Willinger, “The origin of power laws in Internet
topologies revisited,” in Proceedings of IEEE INFOCOM,
vol. 2, pp. 608–617, June 2002.
[10] B. Zhang, R. Liu, D. Massey, and L. Zhang, “Collecting the
Internet as-level topology,” in Proceedings of ACM SIGCOMM, vol. 35, pp. 53–61, ”Jan” 2005.
[11] R. Cohen, “The Internet dark matter: on the missing links
in the as connectivity map,” in Proceedings of IEEE INFOCOM, vol. 25, pp. 1–12, Apr. 2006.
[12] L. Subramanian, S. Agarwal, J. Rexford, and R. H. Katz,
“Characterizing the Internet hierarchy from multiple vantage points,” in Proceedings of IEEE INFOCOM, vol. 2,
pp. 618–627, Nov. 2002.
[13] X. Dimitropoulos, D. Krioukov, B. Huffaker, kc claffy, and
G. Riley, “Inferring as relationships: Dead end or lively
beginning?,” in Proceedings of Workshop on Experimental
and Efficient Algorithms, vol. 4, pp. 113–125, May 2005.
[14] “The Cooperative Association for Internet Data Analysis.”
http://www.caida.org/home/.
[15] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks,”
Journal of Statistical Mechanics, vol. 2008, pp. 10008–
10019, Oct. 2008.
[16] M. E. J. Newman, “Fast algorithm for detecting community
structure in networks,” Phys. Rev. E, vol. 69, p. 066133,
June 2004.
[17] Y. Zhang, M. Roughan, N. Duffield, and A. Greenberg,
“Fast accurate computation of large-scale IP traffic matrices from link loads,” in Proceedings of ACM SIGMETRICS,
vol. 31, pp. 206–217, June 2003.
[18] Cisco, “The zettabyte era.” Available: http://www.cisco.
com/en/US/solutions/collateral/ns341/ns525/ns537/ns705/
ns827/VNI_Hyperconnectivity_WP.html.
[19] Cisco, “Cisco global cloud index: Forecast and methodology, 2011-2016.” Available: http://www.cisco.com/en/US/
solutions/collateral/ns341/ns525/ns537/ns705/ns1175/
Cloud_Index_White_Paper.html.
献
[1] L. Li, D. Alderson, W. Willinger, and J. Doyle, “A firstprinciples approach to understanding the Internet’s routerlevel topology,” in Proceedings of ACM SIGCOMM, vol. 34,
pp. 3–14, Oct. 2004.
[2] C. Labovitz, S. Iekel-Johnson, D. McPherson, J. Oberheide,
and F. Jahanian, “Internet inter-domain traffic,” in Proceedings of ACM SIGCOMM, vol. 41, pp. 75–86, Aug. 2010.
[3] A. Dhamdhere and C. Dovrolis, “The Internet is flat: Modeling the transition from a transit hierarchy to a peering
mesh,” in Proceedings of ACM Co-NEXT, vol. 6, pp. 1–12,
Dec. 2010.
[4] A. Dhamdhere and C. Dovrolis, “Twelve years in the evolution of the Internet ecosystem,” IEEE/ACM Transactions
on Networking, vol. 19, pp. 1420–1433, Sept. 2011.
[5] M. Faloutsos, P. Faloutsos, and C. Faloutsos, “On powerlaw relationships of the Internet topology,” in Proceedings
of ACM SIGCOMM, vol. 29, pp. 251–262, Oct. 1999.
[6] R. Pastor-Satorras, A. V´
azquez, and A. Vespignani, “Topology, hierarchy, and correlations in Internet graphs,” Complex Networks, vol. 650, pp. 425–440, 2004.
—6—