インターネットに現れるゾウやネズミたち
ト ポロジ ーとトラフィックにお ける「 べ き 乗 則 」

ンクは，それぞれ点と線と読み替えて差し支えない。図1の(e), (f)は，グラフの例である。一見似ているようにも見えるが，実際はまったく異なる原理により作られている。グラフ(e)はランダム，(f)はスケールフリーという。各ノードに隣接するリンク数の分布を示したものが，それぞれ図1の(c)，(d)である。リンク数の分布は，(e)と(f)の違いを鮮明に表している。(c)は正規分布であり，平均値<k>から外れるに従って生起確率は指数関数的に急速に減少する。それに比べて(d)は，リ京都情報大学院大学 教授

内藤 昭三

ンク数の増加に伴い，べき乗関数に従って生起確率が緩やかに減少する。(c)では，ほとんどのノードは平均値の周辺近くのリンク数を持ち，均質である。(d)の分布からは，多くのノードが少ない数のリンクしか持たないが，その一方で，多くのリンクを持つノード（リンクリッチ）
も比較的多く存在することが分かる。
従来，解析の容易さもあり，ネットワークモデルとしては，ランダムグラフが多用された。
しかし，実際に現実のネットワークを調べてみると，インターネットに限らず，ウェブのリンク網，電力線ネットワーク，人と人との知人関係など， その多くがスケールフリーでのモデル化が妥当

1.

はじめに1969年にアメリカ西海岸の4ホストをつなぐ ARPAnet として始であることが分かってきた。つまり，ネットワークは，勝手に均質であろうと仮定していたのだが，実際には，ネズミのように小さいノードが多く，しかもゾウのように大きいノードも少なからず存在するという非均質なものが多かったということだ。

まったインターネットは，今では43億個のIPアドレスの枯渇が心配されるほどにまで広まり，道路，電気，ガス，水道，電話などと同列の社会インフラの地位を占めつつある。社会システムの役割を果たすことは，その一方で，社会状況を反映するさまざまな現象がインターネット上にも出現する。ウィルスやワームが蔓延し，サギ（phishing）師や偽善・・者，スパイ（spyware），破壊者（cracker）も登場する。さらには，ゾウ・・・やネズミたちまでも出没している。以下では，インターネットのトポロジ
ーとトラフィックの2つのシーンにゾウやネズミがどのような形で現れるかを考察する。

では，このようなネットワークはどのように作られているのだろう。ランダムグラフは，簡単だ。図1(a)に示すように，各リンクに一様に存在確率pを仮定する。この仮定のもとでは，ノードの総数をNとすると，リンク数の分布は，平均p(N−1)の正規分布となる。ネットワークのサイズ(N )が大きくなれば，平均値も大きくなる。一方，スケールフリーネッ
トワークは， 動的に作られる（図1(b)）。ノードが追加されるごとに既存のノードに対してリンクを張るか否かは，なんらかの優先条件に従って判断される。優先条件には，距離的な近さ，既存のノードのリンク数の多さなどが用いられる。図1(b)では，最も右側に追加された新2.

インターネットのトポロジーに現れるゾウやネズミ

インターネットだけでなく，道路網，電話網，ウェブ，人と人の知人関係などのネットワークのトポロジー（構造）は，抽象的にはグラフとしてモデル化できる。グラフは，ノードとリンクから構成される。ノードとリ50

しいノードに，これらの優先条件に従って2つのリンクが張られている。
ノードのリンク数の多さが優先条件に使われると，リンク数を多く持つノードは，さらにリンク数を増やす結果となる。このような現象は，「マタイ効果」と呼ばれている。マタイによる福音書中の「持てる者はますます富み，持たざる者はますます奪われる。」という記述に因んでいる。
また「2−8の法則」と呼ばれたりもする。2割の者が8割の富を占める，という寡占状況が，さまざまなシーンで出現することを表現している。の現象をもたらす。スモールワールドグラフには， 遠くのノードをつなげる「びっくりリンク」が適度に存在している。これらのリンクをうまく使

また，このようなネットワーク構造は，「スモールワールド」現象ともうことによって，世界が小さくなる。kcg.eduグループは，アフリカの各関係している。1967年にアメリカの心理学者Milgramが，興味深い国をはじめ，世界の拠点とのリンクを持っている。スモールワールドに実験の報告を行った。国内電話帳から選んだ任意の2人を，知り合も一役買っているといえるかもしれない。

いを通じて手紙でつないでもらうというものだ。いわばチェーンメール。
その結果，届いた手紙は，その多くが6人程度の仲介者を経て，相手に届いていた。この実験から，スモールワールド仮説が始まった。
あるいは，「分離数6」などとも言われる。スモールワールド仮説は，イ3.

インターネットのトラフィックに現れるゾウやネズミ

ンターネットの世界でも見つかる。tracerouteというコマンドは， 起点次に，インターネットに流れるトラフィックを考察する。
トラフィックは，から終点までどのような経路でパケットが届いているかを表示してく

この場合，通信量のことで，道路網の場合には交通量と訳される。イれる。日本からアフリカのどこかのホストまでtracerouteを実行してみ

ンターネットのトラフィックは，起点から終点まで，中継ノードを経由しると，せいぜい10ホップ程度で到達していることが分かる。案外近いて送られるパケットの集まりだ。ウェブやメールなどのアプリケーションなと感じる。図2は，このような現象を説明するモデルとして提案されによって発生する起点／終点ペア間の一連のトラフィックをフローとた。左の規則正しいグラフから右の完全にランダムなグラフの中間に，呼ぶ。従来は，フローの発生は，ランダムに生じるとしてモデル化さ適度に不規則なグラフがあり，このようなグラフが，スモールワールドれた。また，フローのサイズも一様性が仮定された。このようなモデル化は，電話のトラフィックを対象とするときには比較的うまく機能する。
電話のコールはランダムに起こり，電話のトラフィックサイズは，ほぼ一（a）（c）（e）様に小さく，いわばネズミサイズだ。
しかし，インターネットのトラフィックP（k ）pEP.=0.2

では，この仮定はうまくいかない。

図3の左側が，ランダム生成モデルによるトラフィックを示す。下に

〈k 〉

k（d）

行くほどトラフィックの集約が進んでいる。このモデルでは，トラフィック
（f）

log P
（k ）

（b）

PoissonMeasuredFractallog k

図1. ランダムグラフ（上）とスケールフリーグラフ1）

REGULAR NETWORK

P=0

SMALL WORLD NETWORKINCREASING RANDOMNESS

図2. ＷＳ（Watts-Strogatz)モデル 2）

RANDOM NETWORK

P=1

図3. ランダムトラフィックモデル（左）, フラクタル
トラフィックモデル（右）と実測データ（中央）3）51

の集約を進めると正規分布（図1(c)）に従う。平均値の近辺に集中し，健全に発展し，安心して使える社会インフラとして認められるために分散が小さくなる。このような現象を統計多重と呼ぶ。電話網の幹は，セキュリティの問題などとともに，まだ解決しておかなければなら線設計では，統計多重効果を見越して，帯域を決めていた。一方，ない問題が残されているのである。

図3の中央が，インターネットトラフィックの実測データを示している。こ
ちらでは，集約を進めても，相変わらず大きな分散が残っている。図3の右側は，フラクタルモデルによるトラフィックを示す。こちらは，実測

Occurrence/occupation ratio of elephant flows

データと似た分布を示している。フラクタルは，集約を進めると，元と相似の形が出現する。海岸線地図などが代表的なフラクタル図形の例だ。

では，何が原因で，このようなフラクタル的なトラフィックが生じるの

Occurrence
ratio

NTTlab

WasedaOCN-SINET

APAN

WIDE

3.01％

1.15％

2.35％

3.22％

4.65％

Occupation
35.72％ 39.07％ 25.59％
ratio

41.22％ 41.30％

図4. ゾウサイズのフローの生起確率と帯域占有率 4）だろうか。我々は，その原因のひとつとして，ゾウサイズのフローが関係していると分析している4）。インターネットのトラフィックは，telnetやVoIPなどのようなネズミサイズのものから，FTP，video streaming，さらにはP2Pファイル交換のようなゾウサイズのものまで，さまざまな規模のものが混在している。そしてこのフローサイズの分布は，やはり正規分布よりも，むしろべき乗分布に従っているようだ。図4には，さまざまな回線上で，ゾウサイズのフローがどのくらいの頻度で発生し，それらが回線帯域のどれだけの部分を占有するかを示している。ここでは，平均プラス分散の2倍以上のサイズを持つフローをゾウサイズのフローと定義している。ゾウサイズのフローが，発生頻度に比して，大きな帯域を占めることを示している。ここでも定性的に「2−8の法則」が成り立っている。

参考文献
1） M. E. J Newman, A. L. Barabasi, and D. J. Watts(Eds.),"The Structure and Dynamics of Complex Networks", Princeton University Press, Princeton, 2003.
2）D. J. Watts, "Small Worlds, The Dynamics of Networks be-4.

おわりにインターネットのネットワーク構造やトラフィックの特性が，従来の電話網などで採用されたモデルとは，かなり異なる可能性があることを見てきた。インターネットのネットワーク構造の持つスケールフリー性は，ランダムな障害に対しては耐性が強いのだが，一種ハブとなってtween Order and Randomness", Princeton University Press,
1999.
3）W. Willinger, and V. Paxson, "Where mathematics meet theinternet", Notices of the AMS 45, pp.961−970, 1998.
4）T. Mori, R. Kawahara, S. Naito, and S. Goto, "On the Characteristics of Internet Traffic Variability: Spikes and Elephants", IEICE Transactions on Information and Systems,Vol.E87-D, No.12, pp.2644−2653, Dec. 2004.

いるゾウサイズのノードを集中的に攻撃されると，弱みを露呈する。
また，トラフィックに関しては，ベストエフォートを制御原理とするインターネットでは，ゾウサイズのフローが「幅を利かせる」とネズミサイズのフローが不利益を被るということが起こりうる。最近では，フロー間の公平性を実現する制御方式なども研究されている。インターネットが52

内藤 昭三

Shozo Naito

京都大学工学部卒，同大学院修士課程修了（数理工学専攻），工学修士。元日本電信電話株式会社情報流通プラットフォーム研究所主任研究員，電子情報通信学会インターネット研究会幹事。京都情報大学院大学教授。