社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,INFORMATION AND COMMUNICATION ENGINEERS

信学技報
TECHNICAL REPORT OF IEICE.

回線コストに基づくインターネットトポロジー生成モデルの提案と評価
日高 直人†

荒川 伸一†

村田 正幸†† 大阪大学 大学院情報科学研究科 〒 565–0871 大阪府吹田市山田丘 1–5
E-mail: †{n-hidaka,arakawa,murata}@ist.osaka-u.ac.jp
あらまし

近年、インターネットのトポロジーの出線数分布がべき則に従うことが観測されており、ノードの出線数分布がべき則に従うトポロジーを生成する様々なモデルが提案されている。しかし、インターネットトポロジーの特性はノードの出線数分布によってのみ決定されるのではなく、出線数分布以外の構造上の特徴が重要となる。そこで
本稿では、ISP におけるネットワーク設計に着目した新たなインターネットトポロジー生成モデルを提案する。提案
モデルでは、物理距離およびトラヒック収容に必要な回線容量を考慮した回線コストを導入し、回線コストを最小化することによってトポロジーを生成する。提案モデルにより生成されるトポロジーを ISP ネットワークのトポロジーおよび従来の生成モデルと比較評価した結果、提案モデルによるトポロジーは、従来のトポロジー生成モデルによるトポロジーに比べ、クラスタ係数、平均パス長、リンク負荷に関して、現実の ISP ネットワークのトポロジーに近い特性を示すことを明らかにする。
キーワード

べき則、ルータレベルトポロジー、トポロジー生成、回線コスト、gravity モデル

A modeling method for ISP-level Internet topologies
based on network-cost optimization
Naoto HIDAKA† , 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: †{n-hidaka,arakawa,murata}@ist.osaka-u.ac.jp
Abstract Measurement studies on the Internet topology show that connectivities of nodes exhibit power-law attribute. Manymodeling methods that re-produce the degree distribution have been proposed. However, it is apparent that only the degree
distribution does not determine the structure of the Internet topology. In this paper, we propose a new modeling method forgenerating realistic ISP-level Internet topologies that obey the power-law degree distribution. Our method adds nodes one
by one, and each node is connected to the optimal node in terms of minimizing the overall network costs. For the network
cost, we incorporate not only geographical information into our method, but also incorporate the amount of link capacities thataccommodates traffic. We show that our modeling method can generate ISP-level topologies having more similar topologicalcharacteristics, in terms of clustering coefficients, average shortest path length, and betweenness centrality, when comparing
with existing modeling methods.
Key words power-law network, ISP-level topology, topology generator, network-cost optimization, gravity model

1. は じ め にドは少数のノードと接続される。
べき則に従うトポロジーを生成するモデルの一つに、BA

インターネットの AS (Autonomous System) 間・ルータ間の接(Barabási-Albert) モデル [4] がある。BA モデルは、ノードを段続状況を観測した結果、ノードの出線数分布がべき則に従うこ階的に追加し（段階的接続)、追加したノードから既存のトポロとが示されている [1–3]。べき則に従うトポロジーでは、接続

ジーの各ノードの出線数の大きさに応じて確率的に接続するこするノード数が k であるノードの出現確率 P (k) が k −γ （γ ：とでトポロジーを生成するモデルであり、スケール・フリーや定数）に比例する。そのため、べき則に従うトポロジーでは、スモール・ワールドなどの特性が数学的に示されている [4, 5]。

一部のノードが多数のノードと接続される一方で、多くのノー

しかし、文献 [6] では、同じ出線数分布を有する複数のトポロ—1—

ジーを列挙し、トポロジーの構造上の違いにより、スループッ

インターネットトポロジーとして用いた際の問題点を述べる。

ト性能が大きく異なることが示されている。そのため、単に出2. 1 BA モデル

線数分布がべき則に従うだけではインターネットトポロジーべき則に従うトポロジー生成モデルとして、BA モデルがあの特徴を捉えるには不十分であり、トポロジー特性を利用した

る [4]。BA モデルでは、初期トポロジーに対してノードを段階ネットワーク設計、設備量予測、トラヒック制御手法の評価に的に追加し（Incremental Growth）、追加したノードから既存の応用するためにも、インターネットトポロジーの構造上の特徴トポロジーに対して確率的にリンクを接続する。リンクの接続を捉えた適切な生成モデルが必要である。

先は、既存トポロジーの各ノードの出線数 ki に比例した接続確

インターネットトポロジーを対象とした生成モデルとして、FKP (Fabrikant Koutsoupias Papadimitriou) モデル [7] およ率 Π(ki ) に基づいて決定する (Preferential Attachment)。BA モ
デルのトポロジー生成アルゴリズムを以下に示す。

び HOT (Heuristically Optimal Topology) モデル [6] が提案されている。FKP モデルは、ノード間の物理距離およびホップ間距離の重み付き和を最小化することでトポロジーを生成する

Step 0m0 個の初期ノードを配置する。

Step 1

トポロジーのノードが N 個未満である場合、Step 2トポロジー生成モデルである。一方、HOT モデルは、ルータへ。N 個である場合、Step 4 へ。のパケット処理能力の制約に着目し、回線容量が少ないリンクは出線数の大きいノードと連結し、回線容量が大きいリンクは出線数が比較的小さいノードを連結する生成モデルである。しStep 2

ノードを新たに 1 個追加する（Incremental Growth）。

Step 3式 (1) の確率に従い、相異なる m (<= m0 ) 個のノーかし、FKP モデルにより生成したトポロジーには出線数 1 のドを選択する。そして、追加したノードと選択したノードが数多く存在するとの指摘もなされており [8]、さらに、ノードを接続する（Preferential Attachment）。接続しHOT モデルにより生成したトポロジーは、ISP (Internet Serviceた後、Step 1 へ。

Provider) ネットワークのトポロジーと比較して代替経路が極めて少なく、トポロジーの構造が大きく異なることが示されてΠ (ki ) = ki/∑

いる [9]。そこで、文献 [9] では FKP モデルを拡張し、ネットワーク設備の増強を考慮した ISP ネットワークのトポロジー生

kj

(1)

j

Step 4トポロジーの生成を終了する。

成モデルを検討している。しかし、ノード間のトラヒック量は均一であり、かつ、ISP ネットワークの設計で重要となるネットワークコストについては考えられてない。
そこで本稿では、ネットワーク設計に基づく新たなインター以上のようにして、Incremental Growth と Preferential Attach-ment の 2 つの成長メカニズムにより、出線数分布がべき則に従うトポロジーが生成される。

ネットトポロジー生成モデルを提案する。提案モデルでは、ネッ2. 2 FKP モデル

トワークを保守、管理するための費用に相当する回線コスト

FKP モデルは、リンクの接続先を確率的に選択する BA モデを定義し、回線コストの最小化に基づいたネットワーク設計にルと異なり、ノードの物理的な配置を考慮してリンクの接続先よってトポロジーを生成する。提案モデルにより生成されるトを決定するトポロジー生成モデルである [7]。FKP モデルにおポロジーを評価した結果、従来のトポロジー生成モデルによるいても初期トポロジーに対してノードを段階的に追加していくトポロジーに比べ、クラスタ係数、平均パス長、リンク負荷にものの、新たに追加したノード (ノード i) の接続先ノード j を関して ISP ネットワークのトポロジーに近い特性を示すことをノード i からの物理距離 dij 、および、ノード j から他ノードへ明らかにする。さらに、提案モデルにおける回線コスト、トラの論理距離 hj の重み付け和を最小にするノードを選択し、リヒックの偏り、ノード配置の設定が、現実のインターネットトンクを接続する。すなわち、以下の式を満たすノード j にリンポロジーのモデル化に対する有効性を明らかにする。

クを接続する。

本稿の構成は以下の通りである。まず 2 章において、従来のトポロジー生成モデルおよびそれらの問題点を述べる。次に 3min α · dij + hj
j(2)章において、ISP ネットワークの設計方針としてのコスト最適

文献 [7] では、論理距離 hj として、(a) ノード j とその他の化に基づいた新たなインターネットトポロジー生成モデルを提ノード間の平均ホップ数、(b) ノード j とその他のノード間の案する。そして 4 章において、提案モデルにより生成したトポ最大ホップ数、(c) ノード j と初期ノード間のホップ数、のいロジーを、ISP ネットワークのトポロジーおよび従来のトポロずれの場合においても、出線数分布がべき則に従うトポロジージー生成モデルにより生成したトポロジーと比較する。最後にが生成できることが示されている。また、物理距離の重み α が5 章において、本稿のまとめと今後の課題を述べる。

大きい場合、追加ノードから物理的に近いノードに接続しやす

2. 従来のトポロジー生成モデル

くなり、出線数分布がポアソン分布に従うトポロジーが生成され、物理距離の重み α が小さい場合には、 スター型のトポロ

本章では、出線数分布がべき則となることに着目したトポロジーが生成されることが示されている。出線数分布がべき則にジー生成モデルである BA モデルおよび FKP モデルを説明す

従うトポロジー は、α を中程度の値に設定することで生成される。これらのモデルにより生成されるトポロジーの特徴を述べ、ることが示されている。

—2—

2. 3 従来の生成モデルにおける問題点

3. 1. 1 回線容量制約

上記の BA モデルおよび FKP モデルを用いることで、べき則回線容量は離散的で、技術的な制約により上限値がある。本に従うトポロジーを生成することができる。しかし、これらの稿では、回線容量の上限値を 10 Gbps とし、回線容量の取りモデルで生成されたトポロジーとインターネットトポロジーに得る値を 1, 10, 100 bps, 1, 10, 100 Kbps, 1, 10, 100 Mbps, 1, 2.4,おいて、以下の相違が指摘されている。

4.8, 10 Gbps とする。回線の収容するトラヒックが回線容量の• BA モデルにより生成したトポロジーは、AS レベルのトポロジーに比べ、クラスタ係数と平均パス長が大きく異なる [10]。

上限値を超える場合、そのトラヒックの一部を他の経路へ迂回させる必要がある。

3. 1. 2 トラヒックの偏りのモデル化
トラヒックの地理的な偏りは、gravity モデル [12] で与える。

• FKP モデルにより生成したトポロジーでは、ほぼすべてgravity モデルは、ノード i-j 間のトラヒック量 xij が、ノードのノードが出線数 1 であり、現実のインターネットトポi、j が扱うトラヒック量 xi 、xj の積に比例するというモデル

ロジーと大きく異なる [8]。
さらに、文献 [6] では、同一の出線数分布を有するが、構造がである [13]。ノードが扱うトラヒック量は、人口分布 p⃗ に比例するものとし、xij を以下の式で与える。

異なるトポロジーをいくつか列挙し、トポロジーの構造上のxij = χ × pi × pj

違いによってスループット性能が大きく異なることも示されている。このように、単に出線数分布がべき則に従うトポロジー

ここで、χ はトラヒックのスケーリングパラメータである。

では、現実のインターネットトポロジーが有する構造上の特性

3. 1. 3 ネットワークコストのモデル化を捉えることができず、その結果、これらの生成モデルにより

本稿では、ネットワーク G (V, E) のネットワークコスト

生成したトポロジーを経路制御手法などのネットワーク制御手

C (V, E) は、回線コストの総和で与える。

法の評価に適用した場合、ネットワーク制御手法の性能を正し

回線 l に対する回線コストは、回線の長さ dl の単調増加関く評価することができない。特に、ISP ネットワークのトポロ

数 fD (dl ) と回線容量 bl の単調増加関数 fB (bl ) の積で与える。

ジーではクラスタ係数に大きな特徴があるものの、既存の生成回線容量は、ネットワーク G (V, E) において、与えられたトラモデルで生成したトポロジーは ISP ネットワークのクラスタ係ヒックを収容するために必要最低限の容量を与える。

数と大きく異なることが示されている [11]。
以上のように、従来のトポロジー生成モデルでは、出線数、C(V, E) =fD (dl ) × fB (bl )l∈E

物理距離、論理距離などが考慮されているものの、これらの指s.t. bl =標だけでは、現実のインターネットトポロジーとクラスタ係数

min b,tl <=b∈B−→→−T = RXが近いトポロジーを生成するには不十分である。そのため、適切なトポロジー生成モデルが必要である。

∑(3)

ここで、R は |E| × |V |2 の経路行列であり、ノード i とノー

3. インターネットトポロジー生成モデルの提案

ド j 間のトラヒックが回線 l を経由する場合、R の (l, (i, j)) を

一般に ISP ネットワークのトポロジーは、その管理者によっ1 とし、経由しない場合は 0 を与える。なお、本稿では、ノード→−i とノード j 間の経路は最小ホップ経路を用いる。また、 X はて設計される。そのため、管理者が定める ISP ネットワークの設計方針が ISP ネットワークの構造に大きな影響を与えるものと考えられる。2.2、2.3 節で述べたように、FKP モデルにおいては、物理距離と論理距離の重み付き和の最小化をネットワークの設計方針と捉えることもできるが、FKP モデルで生成されるトポロジーは ISP ネットワークと構造が大きく異なる。そこで、本章では、ISP ネットワークの設計方針としてコスト最小化に着目し、ネットワークコスト最小化に基づいた ISP ネットワークの生成モデルを提案する。

3. 1 ネットワーク設計のモデル化
提案モデルでは、トラヒック収容のために必要となる回線容量およびその回線の物理距離で定めるネットワークコストを考え、その最小化を目指したネットワーク設計によりトポロジーを生成する。ただし、ネットワークを設計する際には、•回線容量制約•

トラヒックの偏り•

ノードの配置を決める必要があり、以下にその詳細を説明する。

ノード i とノード j 間のトラヒック量 xij を要素とする |V |2 × 1のトラヒック行列であり、式 (3) により回線 l が収容するトラヒック量 tl が求まる。B は 3.1.1 節で示した回線容量が取り得る値の集合である。

3. 2 トポロジー生成アルゴリズム
以上のネットワーク設計方針に基づいたトポロジー生成アルゴリズムを示す。本稿で提案するトポロジー生成モデルでは、従来のモデルと同様に初期トポロジーを与え、そのトポロジーに対してノードを新たに追加する。新しくノードを追加することによってトラヒック量が増加し回線容量の上限値に達すると、トラヒックを迂回させるため新たに回線を追加する。

N ノードのトポロジーを生成するアルゴリズムを以下に示す。
Step 0

初 期 ト ポ ロ ジ ー G0 (V, E)（V= {v0 , v1 } , E =(v0 , v1 )）を配置する。
Step 1

トポロジーのノードが N 個未満である場合、Step 2へ。N 個である場合、Step 6 へ。

—3—

Step 2ノード i を新たに追加し、Step 3 へ。

Step 3

追加ノード i と接続した場合に、接続後のトポロジー

査 [14, 15] により得られた都市人口のデータを用いる。

が回線容量の制約を満たし、ネットワークコストを最• 提案モデルで用いるトラヒック量は、Sprint トポロジー

小にする既存ノード j を求め、追加ノード i と接続すにおいてトラヒックの偏りを gravity モデルと人口分布でる。Step 4 へ。

考えた場合に収容可能な最大トラヒック量と等しくなる

min C (V, E ∪ {(i, h)})h∈V

Step 4• 提案モデルで用いる人口データは、2000 年代の国勢調ように与える。
なお、以降の評価では、提案モデルおよび従来の生成モデル

ただし、どの既存ノードを追加ノード i と接続してで生成するトポロジーは、ノード数およびリンク数が、Sprintも、接続後のトポロジーが回線容量の制約に反するトポロジーと同一となるように生成する。そして、1) クラスタ

場合は、接続後のトポロジーのネットワークコストを係数の分布、2) 平均パス長の分布、およびネットワーク制御手最小にする既存ノード j を求め、追加ノード i と接続法の評価で重要になる負荷に関する指標である、3) Betweennessする。

Centrality [16] の分布に関して、Sprint トポロジーと比較評価

Step 3 と同様に、ノード k(=| j) を求め、追加ノードする。

i と接続する。Step 5 へ。

4. 1 提案モデルと従来の生成モデルの比較提案モデルによる生成トポロジーと Sprint トポロジーおよび

Step 5

Step 6

トポロジーが回線容量の制約を満たす場合、Step 1

BA モデル、FKP モデルによる生成トポロジーの特性を図 1 にへ。トポロジーが回線容量の制約に反する場合、Step示す。提案モデルによるトポロジーは、回線コストの関数を次6 へ。

節で示す 1)〜7) のうち、生成トポロジーのクラスタ係数の分

回線容量が最も大きい回線 (s, t) に対して、その回線の一方のノード u ∈ {s, t} と他方のノードの隣接ノード v を接続した場合に、接続後のトポロジーのネットワークコストを最小にするノード間を接続する。ただし、接続候補のノード間がすべて接続されている場合は、対象にしている回線の次に回線容量が大きい回線を対象にする。接続した後、Step 5 へ。

布が最も Sprint トポロジーに近い d4l log bl を用いて生成している。BA モデルによるトポロジーは、m = 2 でトポロジーを生成し、その後リンク数が Sprint トポロジーと同一になるまで式(1) の接続確率に従い 2 つのノードを選択し、そのノード間にリンクを追加している。10000 個のトポロジーを BA モデルに基づいて生成し、その平均値を図 1 に示している。FKP モデルによるトポロジーは、文献 [7] に基づいて α を 20 とし、BA モデルによるトポロジーと同様に、追加ノードと既存の 2 つのノー

min(u,v)∈{s,t}×(Vs ∪Vt )s.t.

C (V, E ∪ {(u, v)})ドと接続してトポロジーを生成する。その後リンク数が Sprintトポロジーと同一になるまで、式 (2) が最小となる 2 ノード間

bst = maxl∈E blにリンクを追加している。
図 1 より、提案モデルは従来のトポロジー生成モデルに比べ、ここで Vi は、ノード i の隣接ノード集合とする。

Step 7

トポロジーの生成を終了する。冗長な回線が必要な場合は、Step 6 により回線を追加する。

クラスタ係数の分布と平均パス長の分布が Sprint トポロジーに近いトポロジーが生成されることが分かる。また、負荷の分布も、従来のトポロジー生成モデルに比べ、Sprint トポロジーに類似していることが見て取れる。特に、FKP モデルや BA モ

4. 提案モデルで生成したトポロジーの構造特性
本章では、3 章で提案したトポロジー生成モデルによりトポロジーを生成し、その構造特性を比較評価する。
まず、提案モデルと ISP ネットワークのトポロジーおよび従デルでは Betweenness centrality の最大値が Sprint トポロジーから大きく離れている一方で、提案モデルでは極めて近い数値になっていることもわかる。以上より、提案モデルにより生成したトポロジーは現実のインターネットトポロジーをモデル化できていると言える。

来のトポロジー生成モデルの比較を行う。比較対象とする ISP

以降では、提案モデルにおいて用いている回線コストの関数、ネットワークのトポロジーは、Rocketfuel [3] ツールにより計測

トラヒックの偏り、ノード配置を変更し、これらの条件がインされた米国の通信大手 Sprint 社のトポロジーデータ（467 ノー

ターネットトポロジーのモデル化に与える影響を明らかにする。

ド、1280 リンク、以下、Sprint トポロジー）を用いる。また、

4. 2 回線コストによる生成トポロジーへの影響

提案モデルおよび従来の生成モデルにおいて、以下のデータお回線コスト fD (dl ) × fB (bl ) を 1) dl

よびパラメータを用いてトポロジーを生成している。

• 提案モデルおよび FKP モデルで用いるノード配置は、緯度、経度をもとに、Sprint トポロジーを [0, 1]2 空間に正規化したデータを用いる。

1/4

1/2log bl 、2) dllog bl 、

3) dl log bl 、4) d2l log bl 、5) d4l log bl 、6) d8l log bl 、7) dl bl とした際に得られる生成トポロジーと Sprint トポロジーを比較評価した。これらの回線コスト関数のうち、3)、5)、6)、7) で生成したトポロジーの結果を図 2 に示す。1)、2)、4) については、図の見易さのため割愛するが、3)、5)、6)、7) と同じ傾向が得—4—

1
Sprintproposal-Sprint
BA-Sprint
FKP-Sprint-20

0.8

Clustering Coefficients

Clustering Coefficients

10.60.4

0.2

00.40.2

100 150 200 250 300 350 400 450
Rank (Clustering Coefficients asc.)

50

1Complimentary cumulative distribution

Complimentary cumulative distribution

0.6050Sprintproposal-Sprint
BA-Sprint
FKP-Sprint-20

0.8

0.6

0.4

0.2

023456
7
Average Shortest-Path Length

89

100 150 200 250 300 350 400 450
Rank (Clustering Coefficients asc.)

1
SprintD1xlogB
D4xlogB
D8xlogB
D1xB

0.8

0.6

0.4

0.2

02

3

4
56
7
Average Shortest-Path Length

89100000
Link Betweenness Centrality

100000
Link Betweenness Centrality

SprintD1xlogB
D4xlogB
8D xlogB
D1xB

0.810000
1000
100Sprint
proposal-Sprint
BA-Sprint
FKP-Sprint-20

1010000
1000
100Sprint
D1xlogB
D48xlogB
D xlogB
D1xB

1011110100
1000
Rank (Link Betweenness Centrality desc.)1

図 1 従来のトポロジー生成モデルとの構造比較られている。
図 2 より、回線コストの関数の違いによりクラスタ係数の分布が大きく変化することがわかる。特に、回線の長さ dl を複数

10100
1000
Rank (Link Betweenness Centrality desc.)

図 2 回線コストが生成トポロジーに与える影響トラヒックの偏りを変化させた場合と比べて少なくなる。

5. まとめと今後の課題回乗じて回線長の重みを大きくするとともに、クラスタ係数は本稿では、ネットワーク設計論に基づく新たなインターネッ小さくなる。また、回線容量の関数 fB (bl ) を対数関数から線形トトポロジー生成モデルとして、回線に対するコストを最適に関数にした場合も同様の傾向が見て取れる。従って、回線コスするトポロジー生成モデルを提案した。そして、提案モデルにトはクラスタ係数の分布に大きく影響を与えることがわかった。

より生成したトポロジーの構造特性を ISP ネットワークのトポ

4. 3 トラヒックの偏りによる生成トポロジーへの影響

ロジーおよび従来のトポロジー生成モデルにより生成したトポすべてのノード間に一様なトラヒック量を与え、トポロジーロジーと比較評価した。評価の結果、提案モデルによるトポロを生成した結果を図 3 に示す。比較のため、トラヒックに偏り

ジーは、従来のトポロジー生成モデルによるトポロジーに比べ、がある場合の結果 (gravity モデル) も図中に示している。

クラスタ係数、平均パス長、リンク負荷に関して、現実の ISP

図 3 より、トラヒックの偏りが生成トポロジーのクラスタ係ネットワークのトポロジーに類似することを明らかにした。

数の分布と負荷の分布に影響を与えていることがわかる。トラ

本稿では、米国の通信大手 Sprint 社のトポロジーを対象としヒックの偏りを考慮しない場合、クラスタ係数およびリンク負て評価を行った。しかし、ISP によって、その ISP ネットワー荷のばらつきが小さくなることが見て取れる。

クの設計方針は異なる。そのため今後、他の ISP ネットワーク

4. 4 ノード配置による生成トポロジーへの影響
最後に、ノードの配置をランダムにした際のトポロジーの特性を示す。図 4 に、ノードを [0, 1]2 空間にランダムに配置し、500 回の試行を行った平均を示す。この図を見ると、ノード配置がランダムな場合には、平均パス長は Sprint トポロジーよりも長くなり、クラスタ係数も大きく異なることがわかる。しかし、ノードの配置が負荷の分布に与える影響は、回線コストやのトポロジーを対象とし評価する必要がある。

謝

辞本研究の一部は、文部科学省科学研究費基盤研究 (A)18200004
によっている。ここに記して謝意を表す。
文

献[1] M. Faloutsos, P. Faloutsos, and C. Faloutsos, “On power-law rela-—5—1Sprint
gravity TM
uniform TM

0.8

Clustering Coefficients

Clustering Coefficients

10.6

0.4

0.2

0

Complimentary cumulative distribution

Complimentary cumulative distribution

Sprintgravity TM
uniform TM

0.8

0.6

0.4

0.2

034567
Average Shortest-Path Length

89Link Betweenness Centrality

Link Betweenness Centrality

10000
1000
10010Sprint
gravity TM
uniform TM

[8]

[9]

1Sprint
Sprint position
Random position

0.8

0.6

0.4

0.2034567
Average Shortest-Path Length8910000
1000
10010Sprint
Sprint position
Random position

1101001000
Rank (Link Betweenness Centrality desc.)1

図 3 トラヒックの偏りが生成トポロジーに与える影響[7]

100 150 200 250 300 350 400 450
Rank (Clustering Coefficients asc.)

100000

1[6]

0.2

2

1[5]

0.450

100000[4]

0.6

100 150 200 250 300 350 400 450
Rank (Clustering Coefficients asc.)

12[3]

0.8

050

[2]

SprintSprint position
Random position

tionships of the Internet topology,” in Proceedings of the conference
on applications, technologies, architectures, and protocols for computer communication (SIGCOMM ’99), vol. 29, pp. 251–262, Oct.
1999.
G. Siganos, M. Faloutsos, P. Faloutsos, and C. Faloutsos, “Powerlaws and the AS-level Internet topology,” IEEE/ACM Transactions
on Networking, vol. 11, pp. 514–524, Aug. 2003.
N. Spring, R. Mahajan, D. Wetherall, and T. Anderson, “Measuring ISP topologies with rocketfuel,” IEEE/ACM Transactions on Networking, vol. 12, pp. 2–16, Feb. 2004.
A. Barabási and R. Albert, “Emergence of scaling in random networks,” Science, vol. 286, pp. 509–512, Oct. 1999.
R. Albert and A.-L. B. si, “Statistical mechanics of complex networks,” Reviews of Modern Physics, vol. 74, pp. 47–97, Jan. 2002.
L. Li, D. Alderson, W. Willinger, J. Doyle, R. Tanaka, and S. Low, “Afirst-principles approach to understanding the Internet’s router-level
topology,” in Proceedings of the 2004 conference on applications,technologies, architectures, and protocols for computer communications (SIGCOMM ’04), vol. 34, pp. 3–14, NY, USA, Oct. 2004.
A. Fabrikant, E. Koutsoupias, and C. H. Papadimitriou, “Heuristically optimized trade-offs: A new paradigm for power laws in theInternet,” in Proceedings of the 29th International Colloquium on Automata, Languages and Programming (ICALP’2002), pp. 110–122,July 2002.
N. Berger, B. Bollobas, C. Borgs, J. Chayes, and O. Riordan, “Degree distribution of the FKP network model,” in Proceedings of International Colloquium on Automata, Languages and Programming(ICALP), pp. 725–738, July 2003.
荒川 伸一, 福元 良太, 村田 正幸, 滝根 哲哉, “ルータレベルトポロ

101001000
Rank (Link Betweenness Centrality desc.)

図 4 ノード配置が生成トポロジーに与える影響

[10]

[11]

[12]

[13]

[14]
[15]

[16]

ジの構造特性とそのモデル化手法の提案,” 電子情報通信学会技術研究報告 (IN2005-95), pp. 43–48, Oct. 2005.
T. Bu and D. Towsley, “On distinguishing between Internet powerlaw topology generators,” in Proceedings of Twenty-First Annual
Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2002), vol. 2, pp. 1587–1596, June 2002.
Ryota Fukumoto, Shin’ichi Arakawa, Tetsuya Takine, and Masayuki
Murata, “Analyzing and modeling router–level Internet topology,” inProceedings of the 21st edition of the International Conference onInformation Networking (ICOIN 2007), Jan. 2007.
M. Roughan, A. Greenberg, C. Kalmanek, M. Rumsewicz, J. Yates,and Y. Zhang, “Experience in measuring backbone traffic variability:Models, metrics, measurements and meaning,” in Proceedings of the
2nd ACM SIGCOMM Workshop on Internet Measurment (IMW ’02),
pp. 91–92, Nov. 2002.
A. Feldmann, A. Greenberg, C. Lund, N. Reingold, J. Rexford,
and F. True, “Deriving traffic demands for operational IP networks:Methodology and experience,” IEEE/ACM Transactions on Networking, vol. 9, pp. 265–280, June 2001.
U.S. Census Bureau, “Census 2000 Gateway.” Available at http://www.census.gov/main/www/cen2000.html.
United Nations Statistics Division, “Demographic and Social
Statistics.” Available at http://unstats.un.org/unsd/demographic/.
L. C. Freeman, “Centrality in social networks: Conceptual clarification,” Social Networks, vol. 1, no. 3, pp. 215–239, 1979.

—6—