日本ソフトウェア科学会第 37 回大会 (2020 年度) 講演論文集

BGP 経路情報の地図上への投影における AS 位置推定について
黒澤 直史

藤本 衡

海底ケーブルやトラフィック量の情報を地図上に投影することで，ネットワークの状態を把握する取り組みは広く行われている．同様の考え方で，BGP 経路情報に基づくネットワーク間の接続情報を地図上に投影することができれば，障害の発生位置などを特定することが容易になると期待される．しかし，BGP 経路情報に基づくネットワーク単位である AS は時として複数の国や大陸にまたがるため，地図上の特定座標に対応付ける何らかの基準が必要となる．本研究では，AS 番号所有者の名称や住所に基づく座標推定手法と，AS に含まれる IP アドレスから得られる座標情報を用いた手法との精度比較を行う．

も行われている [8]．

1 はじめにこれら既存の研究におけるグラフ表現では，AS をインターネットの世界的な普及に伴い，特定箇所の頂点，AS 間の接続を辺と見なしている．頂点の配置障害が広範囲の通信に影響を及ぼす事例も増加しては特に考慮されないか，またはばねモデルなどの力いる．ネットワーク管理者が障害を早期に把握し，障学的モデルを用いて配置を決定している．そのため，害箇所の把握や原因の切り分けなどの対応を支援す

可視化において AS の地理的位置あるいは位置関係はるためには，テキストベースでのモニタリングだけで考慮されていない．

なくネットワークの可視化が必要と考えられる．

しかしながら，障害の影響が及ぶ範囲は地球全体

インターネットは，通信事業者などの組織ごとににまで広がっており，地理的な位置関係の把握がよよって管理される，AS [1] と呼ばれるネットワークのり重要になっていると考えられる．2008 年に地中海集合体と見なされる．2 点間で通信を行う場合，経由で発生した海底ケーブル切断の際には，広範囲でのする AS を決定するプロトコルとして BGP [2] が標準

BGP 経路情報の取消や更新が観測された [4]．最近で的に用いられている．BGP に基づく AS レベルでのは 2017 年 8 月に米 Google 社が誤った経路情報を設ネットワーク構造を可視化することにより，ルーティ定・配信したことにより，日本国内のプロバイダに通ング，輻輳制御，負荷分散などのさまざまな分野に活信障害が発生し，モバイル Suica など決済サービス用できる．そのため，ネットワーク構造の可視化が広にまで影響が及んだ [3]．こうした遠隔地で発生したく研究されている [5] [6] [7]．また，障害発生時に作成障害を可視化する際に，実際の地理的位置を反映するされる迂回経路を検出し，その経路を可視化する研究ことができれば，障害の発生位置などを特定し原因を推定することが容易になると期待される．

Position Estimation of AS for Geographical Mappingof BGP Routing Information
Naofumi Kurosawa, 東京電機大学大学院理工学研究科情報学専攻, Informatics, Tokyo Denki University.
Kou Fujimoto, 東京電機大学理工学部情報システムデザ
イン学系, Div. of Information Systems and Design,
Tokyo Denki University.

AS はネットワークの集合体であるため，一般には一意な座標で表現することができないと考えられる．
場合によっては，複数の国や大陸にまたがる場合もある．そのため，地図上の特定座標に対応付けるためには，何らかの基準が必要となる．

図1

AS の相互接続イメージ
図2bgpdump による BGP UPDATE メッセージのそこで本研究では，AS の位置推定方法として，AS出力例に含まれる IP アドレスから得られる情報を用いた位置推定手法と，AS 情報の管理組織に登録されている期的に送信することによって，経路情報を最新のもの

AS 所有者の情報を用いた位置推定手法の 2 つをとりに更新する．

あげ，比較を行う．

交換される経路情報は図 2 のような内容であり，特定のネットワークに到達するための経路候補が AS-

2 AS レベルのネットワーク構造

PATH に記載されている．特定のネットワークへの地球規模でのインターネットを可視化する場合，個経路候補が複数得られた場合，BGP では一定のアル別のネットワークの集合体である AS を単位として扱ゴリズムに従ってその中から 1 つの候補を実際の経うことが多い．本節では，AS の概要および AS 間で路として選択する．AS レベルのネットワーク構造をの経路決定方法を概説する．

グラフ表現する場合，物理的経路が外部から認識できAS(Autonomous System，自律システム) とは，統一された運用ポリシーによって管理された，IP ネットないことも多いため，BGP の経路情報に基づいて辺を生成することが多い．

ワークやルータの集合 [1] であり，16bit または 32bitの数字を用いた AS 番号によって一意のものとして3 関連研究識別される．AS 間は図 1 のように相互に接続されてAS レベルのネットワーク構造を可視化する試みは，いる．

2000 年代以降広く行われている． [5] では，AS レベ

AS レベルのネットワーク構造は，AS をノード，ルでのインターネットルーティングの動作と不安定性

AS 間の接続をエッジで表すことにより，グラフとしを可視化することを目的とし，BGPlay という可視化て表すことができる．

システムを作成している．

図 1 において，たとえば AS2 と AS5 の間には複[5] の研究で作成されたシステムは，RIPE [9] でも数の物理的経路 (AS2 → AS3 → AS5, A2 → AS4 →公開されており，ブラウザ上で動作する．任意の IPAS5 など) が存在しているが，実際の通信においてはアドレスを指定することにより，その IP アドレスがこの中のどれかを選択する必要がある．そこで，利含まれる AS を中心とする，ネットワークグラフが描用可能な経路情報の交換と経路決定を行うために用画される．例えば，日本の SINET(AS2907) を中心いられるのが BGP(Border Gateway Protocol) [2] でに表示させると，図 3 のように AS2907 を中心としある．て，接続されている AS がグラフとして表現される．

BGP では，最初に自組織の AS と接続先の AS でBGPlay では，大量のルーティング履歴データをわピアを確立して経路の交換を行う．その後は，経路情かりやすい方法で可視化することに焦点を当ててい報を伝達するために BGP UPDATE メッセージを定るため，時間を遡り，任意の時点でのネットワークの図3BGPlay [9] の実行例

接続グラフを表現できる．その際に，ノードの位置はどの時点のものでも同じであり，時間変化によって図4想定するシステム

移動したエッジがアニメーションを用いて強調表示される．
このシステムでは，ノードとしての AS を画面上に配置するために，ばねモデル [10] を用いている．ばね

障害発生場所などを効果的に可視化するためには，AS の地理的位置を反映した可視化が効果的と考られる．

モデルとは，Eades によって提案されたバネ埋め込み

筆者らは，図 4 のような，地理的位置情報を含むと呼ばれる力学モデルに基づいたアルゴリズムであ

3D の可視化システムを作成することを目標としていり，グラフのエッジをバネに置き換えて，シミュレーる．実際に AS が存在する国または地域の緯度経度情ションによってレイアウトを変形させる手法である．

報をもとに，地球型の球体上に配置する．このような[7] では，インターネットトポロジの AS レベルで地理的情報を強く意識した可視化を行うことで，障害の構造の理解を深めるために，Gao [11] の提案するの影響範囲や原因を推定することが容易になること

Valley-free 規則に着目し，provider-customer，peer-が期待される．

peer の関係を直感的に理解することができる，ネッ

現在，Unity を用いた実装が進められているが，ASトワーク上のトラフィックの方向を考慮した新しいの座標としては GeoLite2 [12] を用いて推定した暫定ネットワーク描画ツールの提案を行っている．

的なものを用いている．

[8] の研究では，30 分毎の BGP UPDATE メッセー

ジから迂回路を検出し，障害が発生した際に迂回路5 AS の位置推定として利用される AS を特定している．また，障害前筆者らの調査した限りにおいては，AS の位置座標後のネットワークの状態を可視化し，負担が集中するはデータベース化されていない．また，2 節で述べたAS を明確にしている．

とおり AS は複数ネットワークの集合体であるため，単純に 1 つの座標に対応付けることは必ずしも現実4 構築するシステムを反映していないと言える．しかしながら，グラフ表

AS レベルでのネットワーク構造を可視化する際，現をするためには AS を 1 つの頂点と考え，AS を代[5] や [7] などの関連研究では，ノードの配置をばねモ表すると考えられるような座標に対応付ける必要がデルを用いて決定している．ばねモデルを用いることある．

でレイアウトとして綺麗に配置でき，AS 同士の接続確認できる AS は 2020 年 8 月時点で 90,000 個近関係も効果的に可視化できているが，実際に AS が存くあるため，個別に調べるのは現実的ではない．その在する地理的位置は反映されていない．

ため，比較的容易に入手できる公開情報に基づいて推定することが必要になる．

5. 2 GeoIP と RIR の精度について
AS の緯度・経度を推定する準備として，GeoIP

5. 1 入手可能な情報サービスに基づいて推定される国がどの程度 RIR 統

AS の座標を推定するために使用できる情報として計に合致しているかについて評価を行った．2020 年

は，GeoIP サービスと RIR 統計，WHOIS が挙げら7 月時点での RIR 統計，および GeoLite2 のデータれる．

を用いて，それぞれから推定される国が一致している

GeoIP サービスは IP アドレスから使用地域を特かどうかを比較した．なお，GeoLite2 データに基づ定するサービスであり，MaxMind 社の GeoLite2 [12]く国推定方法としては，AS に含まれる全ての IP アが知られている．このサービスでは，AS の持つ IPドレスについて使用国を取得し，総数が最も多い国をアドレス群のデータベースと，IP アドレス群の緯度・推定値として採用することとした．

経度のデータベースが公開されており，それらを組みGeoLite2 に登録されている IP アドレスには，それ合わせることで，その IP アドレス群を含む AS の緯らがどの AS に含まれているかを網羅したデータベー度・経度が推定できる．ただし，AS には複数の IP アスも別途用意されており，そのデータベースに含まれドレス群が含まれており，それらが異なる地域・国・る AS は全部で 68,037 個である．このうち，61,673

大陸にある場合も実在する．したがって，複数の緯個は RIR に登録されている国情報と，GeoLite2 の情度・経度から何らかの方法によって代表値を求めなけ報から推定した国が等しかった．これに対して，6,364ればならない．

個は GeoLite2 から推測した国と RIR から得られる

RIR 統計は地域インターネットレジストリが公開

国が違うことがわかった．

している情報で，IP アドレスと AS 番号の割り当てら得られる国が食い違っている例を，表 1 に示す．

れた国の国コードが取得できる．地域インターネット

AS13232 の登録者はドイツの銀行 Portigon AG であレジストリとは，インターネットリソース (AS 番号，り，RIR，WHOIS 共に国情報はドイツとなっている．

IP アドレス) の配分と登録を管理する組織であり，

しかし，GeoIP から推測した場合，アメリカ，ドイ

ARIN [14]，RIPE NCC [15]，APNIC [16]，LACNIC

ツ，イギリスで使用されている IP アドレスがそれぞ[17]，AfriNIC [18] の 5 つが存在する．小さな国であれ 3 分の 1 ずつ含まれているため，国の推定が困難

ればこの情報に基づいて AS の座標を指定しても誤差である．また，AS16880 はトレンドマイクロ社の ASは小さいが，国土の広い国では誤差が大きくなる懸念であるが，WHOIS と RIR の登録情報はアメリカでがある．さらに，米国のように多くの AS が登録されあり，GeoIP から推測した国は日本となっている．トている国では，国土の中心など少数の座標に多くのレンドマイクロ社は米国創業であるものの，現在の本AS が集中してしまい，可視化という観点からは望ま社は日本に所在しているため，GeoIP から推測したしくない．

国の方が実際のネットワークに近い可能性があるが，WHOIS も RIR の登録情報を取得するサービスだ

精度は不明である．

が，AS 番号をキーとして登録者の名称が検索できる．

このように，WHOIS 情報と GeoIP からの推定結レジストリによっては AS の登録者に関する詳細な住果の国が違う傾向があるため，IP の数の割合を使用所も含まれているが，こうした情報を公開していなした国推定の信用度は低いと考えられる．そのため，いレジストリも存在する．また，登録者住所と実際のAS に含まれる IP アドレスから得られる情報を用いネットワークの所在地が常に一致しているとは限らた位置推定手法においても，国は WHOIS から得らない．

れる情報を用いるものとした．

表1[14] で管理されている AS に限定する．これは，ARIN各情報から推定される国の比較の WHOIS データベースには AS 登録者の住所情報

AS 番号

RIR

GeoIP

WHOIS

13232

DE-DEのが第 1 の理由である．またもう 1 つの理由として，

16880

USJP

US

ARIN が管轄する米国やカナダは国土が広く，AS 座が含まれており，比較対象として適切であるという標の推定値と住所地の誤差が大きくなる可能性があ

5. 3 本研究における推定手法

るため，評価に適していると考えられる．

以上の情報を用いて，本研究では以下の方法で ASに緯度・経度を対応付ける．対応付けを行う AS を A

ARIN 管理の AS のうち，以下の 2 つの条件を満たすものを評価対象とした．

• AS が内包する IP アドレス群の情報が GeoLite2とおく。

1. WHOIS で取得できる A の登録者情報のうち，国に関する情報を用いて，A の属する国 CW (A)のデータベースに存在する• GeoLite2 データのみを用いた場合に，RIR の国情報と異なる国に属していると推定されるを推定する．

2. GeoIP サービスを用いて，A に含まれる IP ア
ドレス i についてその使用国 CG (i) を推定する．

3. A の属する国に限定した IP アドレスの集合

該当する AS は 1,224 件であった．この AS 集合をAG1 とおく．
GeoLite2 データから推定された緯度・経度には，(37.751, −97.822) となるものが 750 個 (全対象のうI(CW ) を生成する．すなわち，I(CW (A)) = {i|i ∈ A, CG (i) = CW (A)}ち 61%) 存在した．北緯 37.751 度, 西経 97.822 度は4. すべての i ∈ I(CW (A)) について，GeoIP サー

米国カンザス州に位置し，「米国の地理的中心」を指ビスを用いて緯度 ϕ(i) および経度 λ(i) を取得している．すなわち，当該 IP アドレスが米国内で使する．

用されている以上の情報がなく，便宜的に米国の地理5. 以下の 2 つの方法で緯度・経度の代表値を求的中心座標を設定したものと推測される．以下では，この座標を米国地理中心座標と呼ぶ．

める．

米国地理中心座標を設定された IP アドレスを除外(a) 最頻値を用いる．
(b) 以下の算術平均 ϕ̄(A), λ̄(A) を用いる．
∑ϕ̄(A) = |I(CW (A))|−1ϕ(i)i∈I(CW (A))∑λ̄(A) = |I(CW (A))|−1

したデータも用意し，あわせて比較を行った．このとき，内包する IP アドレスがすべて除外される AS が26%ある．それらを省いた AS 集合 (904 個, AG1 のλ(i)i∈I(CW (A))74%) を AG2 とおく．

上記 5.(a)(b) の手法は，いずれも IP アドレスベー

まず緯度・経度ともに誤差が 0.1 度 (おおよそ 10km)

スの位置推定のため，A が実際に運用されている座以内であれば一致とみなした場合の比較結果を表 2 に標に近い推定ができる可能性がある．

示す．AG1, AG2 のどちらを評価対象とした場合になお，本研究における推定手法を評価するため，ついても，算術平均を用いる推定手法より，最頻値をWHOIS から登録者の住所情報が取得可能な AS につ用いる手法が一致数が多くなることがわかる．また，いて，住所情報に基づく緯度・経度との比較を行う．

AG1 に比べて AG2 では一致数・一致率ともに増加し住所から緯度経度にする方法としては，ジオコーディていることから，米国地理中心座標を除外することはングサービスである [13] を使用した．

精度向上に寄与すると考えられる．
次に，誤差を 1 度 (おおよそ 100km) 以内であれば6 評価一致と見なした場合の比較結果を表 3 に示す．

5. 3 節で示した手法を評価するための対象となる

表 2 と同様に，算術平均より最頻値を用いる手法

AS は，以下のような基準で選定した．まず，ARINがより一致数が多くなることがわかる．また，米国地

表2

許容誤差 0.1 度での一致数・一致率データが位置推定の精度に影響していることが示された．また，WHOIS から得られる住所情報を使用した

最頻値

算術平均

AG1

142 (12%)82 (7%)

も，最大で 34%程度は実際のネットワークの位置に

AG2

224 (18%)156 (13%)近い座標が推定できる可能性があることがわかった．

AS 番号所有者の名称や住所に基づく座標推定手法で今後の課題としては，ARIN 以外の RIR が管理す表3

許容誤差 1 度での一致数・一致率

る AS でも同様の比較を行う必要がある．また，推定精度を向上させるために外れ値の基準を決定するこ

最頻値

算術平均

AG1246 (20%)

162 (14%)

置座標を決定し，可視化システムの作成と評価を行う

AG2

411 (34%)314 (26%)

ことも今後の課題となる．とが求められる．さらに，この推定をもとに AS の位理中心座標を除外することで一致数・一致率ともに向参 考 文 献上するのも表 2 と同じ傾向である．

[ 1 ] Hawkinson, J. and Bates, T.:“Guidelinesfor creation, selection, and registration of an Autonomous System (AS)”, RFC 1930, March 1996.
[ 2 ] Rekhter, Y., Li, T. and Hares, S. (Ed.): “ABorder Gateway Protocol 4 (BGP-4)”, RFC 4271,January 2006.
[ 3 ] 榊原康, 山崎洋一, 高橋健太郎: “OCN や KDDI で大規模ネット障害”, 日経 NETWORK, 2017 年 10 月号, pp.16–17[ 4 ] RIPE NCC: “Appendix – Mediterranean Fibre
Cable Cut”, Archived Projects,
https://www.ripe.net/analyse/archived-projects/
mediterranean-fibre-cable-cut/appendix[ 5 ] Di Battista, G. and Mariani, F. and Patrignani,
M. and Pizzonia, M.: “BGPlay: A system for visualizing the interdomain routing evolution”, LNCS,
2912, pp.295–306, 2004.
[ 6 ] Nomoto, S., Fukuda, K., Uehara, M. and MoriH.: “Graphic Drawing Tools for Network TraﬃcSimulation”, LNCS 5186, pp.293–302, 2008.
[ 7 ] Nomoto, S., Fukuda, K., Uehara, M. and MoriH.: “A Visualization of Internet AS Topology withValley-free Rules”, CISIS 2009, pp.279–286, 2009.
[ 8 ] 小林香, 山谷周平: “BGP メッセージを用いた迂回経路検出手法の検討”, 待ち行列シンポジウム「確率モデルとその応用」報文集, pp.81–83, 2017.
[ 9 ] RIPRStat BGPlay:https://stat.ripe.net/special/bgplay[10] Di Battista, G., Eades, P., Tamassia, R. and Tollis. I. G.: “Graph Drawing: Algorithms for the Visualization of Graphs”, Prentice Hall, 1999.
[11] Gao, L.: “On Inferring Autonomous System Relationships in the Internet”, IEEE/ACM Transactions on Networking, Vol.9, No.6, pp.733–745, 2001.
[12] GeoLite2:
https://dev.maxmind.com/geoip/geoip2/geolite2/[13] Geocoding.jp:
https://www.geocoding.jp/[14] ARIN:

AS の位置推定に用いる情報としては，IP アドレスの使用地域を用いる方が実際のネットワークにより近いと考えられるため，GeoIP サービスの情報が適切であればより精度が高い推定が期待される．しかし，少なくとも本研究で対象とした ARIN 管理の AS においては，米国地理中心座標のような緯度・経度情報が便宜的に設定されたと思われるものも多く存在する．また，算術平均を用いた推定手法の精度が低いことから，IP アドレスの緯度・経度情報に外れ値が多いことが推測される．以上の点から，GeoIP サービスから得られる情報に含まれる外れ値を適切に除外することが AS 位置推定の精度向上に必要であると考えられる．
一方で，WHOIS の住所情報から得られる座標と比較した場合に最大で (誤差を 100km 以内とした場合)34%程度の AS は GeoIP から推測した座標に近いという結果が得られた．これらの AS は，実際のネットワークの位置をある程度の精度で近似できていると考えられる．

7 まとめと課題
本研究では，地理的位置情報を反映したネットワー
ク構造の可視化を行うために，AS の位置を推定する手法を比較した．ARIN の管轄の AS に関して比較を行った結果，GeoIP サービスから得られる情報には外れ値や便宜的なデータも含まれており，これらのhttps://www.arin.net/[15] RIPE NCC:
https://www.ripe.net/[16] APNIC:
https://www.apnic.net/[17] LACNIC:
https://www.lacnic.net/[18] AfriNIC:
https://afrinic.net/