今回は、今までの記事とはちょっと違った傾向で行こうと思います。
先日、私の書いた記事に対して、以下のような質問を頂きました。このような深い視点での鋭い質問からは学ぶことが多く、質問をいただけたことをこの場で感謝したいと思います。ありがとうございました。
以下、質問内容です。
こんにちは。
私は○○大学 ××学部 △回生 □□と申します。
大変恐縮ですが、あきみちさんがお書きになったブログ「AS番号からGoogleのネットワーク構成を推測する」を拝読させていただきまして、お伺いしたいことがございましたのでメールを差し上げたました。
ご質問の内容は、cyclopsについてでございます。私も、実際にcyclopsを利用してみました。ネットワーク同士の繋がりが見えることは、大変興味深いです。先ほど、利用中にふと疑問が2つほど浮かんできました。
cyclopsはRelationのカテゴリーで、Eye番号のネットワークとASNの関係をピア、カスタマー、プロバイダの中から適切な関係を表示しています。一体、どのようにcyclopsはその両者の関係を把握しているのでしょうか？
2つ目の疑問は、Weightに関することです。cyclops内にある計算式の説明は目を通しましたし、書籍、海外サイト含めいろいろとネット検索しました。でもどうしてもこのWeightがどのような計算をもとに算出されているのかがわかりません。ご存知でしたら、もちろん推測の範囲でも構いませんので、教えていただけないでしょうか？
以上二点が、あきみちさんのお書きになった「AS番号からGoogleのネットワーク構成を推測する」を読ませていただいて疑問に思ったことです。
大変お手数ですが、ご教示いただければ幸いでございます。何卒宜しくお願い致します。
今回いただいた質問が非常に鋭いものであり、私もよくわからなかったので、調べてみました。また、せっかく調べるのならということで、記事として書かせていただきたいとも思いました。
Cyclopsサイトを見てみる
まず、Cyclopsのサイトを調べてみましたが、確かに質問を頂いた2点に関しての記述は発見できませんでした。というより、あまり詳しい説明はサイト全体を通してなさそうです。
仕方がないので次の手段に出ました。Cyclopsは、UCLAによる研究プロジェクトとして運営されています。ということは、恐らく論文が執筆されているはずです。
そこで、論文著者に関しての情報得るために、「About Cyclops」のページを見ました。
- About Cyclops
- URL：http://cyclops.cs.ucla.edu/?v=about
すると、2名のPh.D生徒とともにLixia Zhang氏の名前がありました。これを見たら、ACMなどの著名論文誌に論文が通ってないわけがないと勝手に思いました。
そこで、次にGoogle Scholarを使って「Lixia Zhang Cyclops BGP」という単語で検索をしてみました。すると、最初に出て来たのが2008年のACM SIGCOMM Computer Communication Reviewの論文です。はやり、流石としか言いようがないぐらい由緒正しい論文誌に掲載されています。
- Ying-Ju Chi, Ricardo Oliveira, Lixia Zhang, "Cyclops: the AS-level connectivity observatory", ACM SIGCOMM Computer Communication Review, Volume 38 Issue 5 (October 2008), Pages: 5-16
- URL：http://portal.acm.org/citation.cfm?id=1452335.1452337
-
論文の中身を読む
ここではいただいた質問に答えることを主眼としているため、詳細は割愛しますが、発見したCyclops論文は非常に面白いものでした。Cyclopsがどのような情報を使って、どのようにデータを造り出しているかを解説しています。
Relationに関して
まず、1つめの質問のRelationに関してです。CyclopsはなぜProvider、Customer、Peerという接続関係を推測可能なのでしょうか？
論文中に、解析の仕組みが書いてありましたが、その仕組みを理解する前に、そもそものBGP運用に関して知る必要があります。BGPのプロトコルそのものは純粋にASパスを計算するものですが、その背景には経済的な事情が非常に大きく働いています。
BGPによる接続には3種類あります。双方が接続料金を均等に負担するPeer-Peerと、料金を受け取って接続を許可するProvider、料金を支払って接続してもらうCustomerです。
Customerは、Providerに対して流れるトラフィックに応じた金額を支払います。そのため、3種類の接続が存在していた場合、ASは可能な限りCustomerへとトラフィックを向けます。そして、優先度的に次になるのがPeer側で、最終的に選ばれるのがProvider側です。
このような条件があるため、基本的にPeer-Peerの接続で受け取ったものが、上流のProvider側へと流れることはありません。そんなことをすると丸ごと損ですから。Cyclopsでは、このような生態系で成り立っているAS間接続の世界を計算によってProvider、Customer、Peerの3種類に分けています。
まず、Tier-1から下流へと向かう接続はCustomerへの提供となります。Provider側からCustomerへの接続は、複数のASパス上で観測されるという特徴もあるので、その特徴も接続形態を断定するために利用されるそうです。一方、Peer-Peerの接続は、Tier-1を介さない接続となっているようです。
Tier-1、Large ISP、Small ISP、Stubの分類方法
さて、そうなると気になるのがTier1、Large AS、Small AS、Stubという階層分けをCyclopsがどのように行っているかです。それに関しても論文中で記述がありました。
we sort ASes into four classes based on the number of downstream customer ASes: stubs if they have 4 or less downstream ASes, small ISPs if they have between 5 an 50 downstreams, large ISPs if they have more than 50 downstreams and finally Tier-1 ASes.
下流へと向かう接続の本数によって分けているようです。
4つ以下の下流接続のASはスタブASと定義されています。下流接続が5-50の場合はSmall ISP、50以上がLarge ISPで、さらに上がTier-1とされているようです。論文では、明確にTier-1の定義は行われていませんでした。
明らかに接続数が多いからTier-1としているのか、それともTier-1という存在は既知としてCyclopsが設計されているのかは、残念ながら今回読んでみたところではわかりませんでした。
Weightに関して
次に2つめの質問に関してです。Weightに関しても論文中に解説がありました。
To measure how much an AS link is used, we keep track of the number of BGP routes carried on each AS link.
We call this number the link weight, a concept borrowed from our previous work [16].
[16] M. Lad, R.Oliveira, D.Massey, and L.Zhang, "Inferring the Origin of Routing Changes using Link Weights", In Proc. IEEE ICNP, 2007
詳しくは2007年の論文を読む必要がありそうですが、AS接続の利用率を推測するために、BGPによる経路数を指標として重み付けを行っているようです。
最後に
非常に面白いご質問、ありがとうございました。おかげさまで、いつも気にせずに使っていた機能に関して調べて知ることができました。このような鋭いご質問をいただけると非常にありがたいです。
Cyclopsの論文は面白いので、興味がある方はぜひACMの論文をご覧ください（ただし、ACMの論文は有料です。ACM会員になる、お金を払って単体として購入、大学や研究機関アカウントで見る、などが必要なのでご注意ください）。
