不完全なTraceroute情報を用いたAS Pathの推測方法

摘要

インターネットにおけるエンドシステム間の経路を調べるためには，通常tracerouteを用いることが多いが，このtracerouteの返す情報は不完全な場合がある．これは，ルータに送られたtracerouteのUDPパケットの応答であるICMPパケットが生成されないことに起因する．一方，インターネットの経路情報は，通常経路とは異なる代替経路（disjoint path）を探索するための基本情報として重要である．オーバーレイルーティングでは，代替経路を利用し，リンク障害を回避することで経路の堅牢性を向上するなどの応用がある．そこで本稿では，通常経路をルータレベルで完全な推測することは一般に困難であること，代替経路の検索には，ASレベルの情報で十分な場合が多いことなどの理由から，不完全なtraceroute情報からASレベルでの完全な経路を推測する手法を提案する．本手法は，ASペア間のピアの関係を調べることにより，tracerouteでICMPパケットが返らないルータ（アスタリスクとして表示される）が属するASを推測する．また，サブネットの異なる191のPlaneLabのノードから得られたtracerouteの結果とASのピアリング関係を用いて，不完全なtracerouteのサンプルの71.4％に対して，通常経路をASレベルで推測可能であることを示す．