複雑なインターネットトポロジの観測に関する基礎的研究イ

点击翻译按钮获取中文摘要

今年度はインターネット上のダイナミクスとして実用上重要なルーティングプロトコルの性能指標(収束性、安定性、頑健性、拡張性など)を規定する要因を洗い出し、それらをネットワークの性質によって記述することを試みた。具体的には、ルーティングプロトコル、特にBGPとその基礎となるアルゴリズムについて、(i)比較的単純なトポロジにおいてアルゴリズムの動作を解析し、性能指標の振る舞いを調べること(ii)いくつかの典型的なあるいは極端なトポロジ(前年度の研究で生成されたトポロジを含む)においてプロトコルを動作させ、これまでに提案されているネットワークを特徴付ける指標と性能指標との関連をシミュレーションによって調べること(iii)インターネットにおいてBGPの運用などに利用されているデータをこれらの解析によって解釈することを試みた。具体的に与えられたトポロジに対してルーティングプロトコルの挙動を解析的に評価することは難しいため、シミュレーションによる評価を行った。この際、ns-2等におけるBGPの実装ではオーバヘッドのためスケーラビリティに乏しいこと及び実装上の詳細により本質的な要素を見出すことが困難なことのため、プロトコルの特徴をよくとらえつつBGPに特徴的なポリシーの表現を可能にしたSobrinhoのnetwork algebraに基づくモデルを採用し、これによる経路情報の収束性のシミュレーションを行うソフトウェアを作成した。ソフトウェア作成及び検証に時間を要したこと、及びシミュレーション結果の解釈(特に、シミュレーション上のステップと実時間とのマッピング、及びモデルにおける大城的な情報とBGPにおいて観測される局所的な情報の関係)において未解決の問題があるため、研究期間内に最終的な結論には至らなかったが、トポロジに関連して発生する特徴的な現象(例:route flapping)において生じるメッセージ伝播の状況を検証しうることが示された。