メンバー: Justin Loye, Romain Fontugne
カテゴリー: Exploring
- 背景:BGPは、その複雑な挙動と変動の傾向にも関わらず、インターネットにおいて重要な役割を果たしています。AS障害を引き起こすBGPは定期的に観測され、社会的および経済的な影響を与えています。リンクストリーム分析の最近の進展により、構造と頻度の観点から時系列BGPトポロジーグラフを完全に特徴付けることが可能となり、障害による急激な変化を監視することが可能になります。
- 目的:BGPデータのより良い理解は、異常検出、リンク予測、ASランキングや分類などの有用な応用につながる可能性があります。
- アプローチ:Ⅰ) データ収集および前処理:BGP更新メッセージから高頻度およびグローバルスケールのインターネットトポロジーを作成し、AS特徴を収集。Ⅱ) データ分析:多スケール頻度構造分解を適用してBGPトポロジーを特徴付ける。
QuickRIB:BGP更新メッセージからの高頻度およびグローバルスケールインターネットトポロジー
私たちはトポロジーデータを収集するツールを開発しました:QuickRIB、効率的な(再)構築とBGP「ルーティングテーブル」の分析のためのオープンソースPythonツールです。 このプロジェクトは以下の機能を提供します:
- RIPE RISとRouteViews MRTアーカイブのダウンロードとキャッシュ。
- 異なるコレクターから集約されたRIBテーブルの構築。
- より高い頻度で完全なRIBを持つための更新の処理。
- オブザーバー(例:トポロジーグラフ、ASパスカウントなど)と呼ばれる事前定義された分析カーネル。
- オブザーバーの実装は簡単です。
オンラインリポジトリ:https://github.com/JustinLoye/quickrib
AS特徴収集
私たちはインターネットイエローページから25のAS特徴を収集し、前処理を行いました。これらの特徴は機械学習モデルの基盤として機能し、リンクストリーム分析のための意思決定に役立つ可能性があります。たとえば、分析の複雑さを減らすために、ASビジネスタイプに基づいて完全なASトポロジーをサブグラフに縮小しました。 特徴の前処理は、異なるデータソースからの部分的なカバレッジのため、単純ではありません。 AS特徴収集を実行するために、私たちはIIJ研究所の「インターネットイエローページ」プロジェクトに貢献しました。
- スタンフォード.asdbクローラーの改良を行い、ASのビジネスタイプ分類を取得。
- 新たなクローラーworldbank.countrypopを実装し、国の人口を取得。この情報はapnic.aspopデータセットとリンクして、ISPの最終ユーザー顧客数の見積もりができます。
BGPトポロジーを特徴付けるための多スケール頻度構造分解の適用
おもちゃモデルのリンクストリーム分析
リンクストリーム分析は新しいツールであり、まだ様々な問題に適用されていません。完全なインターネットトポロジーにおけるBGP異常検出を行う前に、このツールはおもちゃモデルでテストされなければなりません。私たちは、確率的ブロックモデル(SBM)の実現において構造分解をテストしました:
- 理論とコードライブラリの理解。
- 大規模でノイズの多いSBMであっても、構造分解を用いて高次構造(ブロック)と低次構造(リンクノイズ)を区別することができます。
BGP異常検出の予備結果
実際のBGP障害に適用されたエンドツーエンドのBGP異常検出パイプラインが設定されました。 それはグラフの時間的な連続に構造分解を適用します。 歴史的に重要な構造が重要性を失った場合、異常が検出されます。 Telecom Italiaの障害時間中に関連する異常が観察されました。 しかし、結果はまだ初期段階であり、コミュニティに興味を持ってもらう前に洗練が必要です。現在の欠点は:
- 我々は構造分解のみを活用しており、頻度分解を行うことの価値を信じていますが、それを行っていません。
- 私たちの異常検出器は未熟でノイズに敏感です。