システム設計

8.3.2 登録手順

BGP 経路は，以下の手順に従い，BGPデータベースに登録される．データベースへの 登録は，プレフィクス単位となる．BGP経路の変動は，経路更新メッセージにより通知さ れるが，本メッセージに含まれるプレフィクス情報を元に，プレフィクス毎に登録処理を 行う．本データベースは，プレフィクス毎，異なる期間毎のBGP経路を，BGPテーブル として管理する．図 8-4に示すように，BGPテーブルは，プレフィクス，観測点，期間，

属性のパラメータから構成される．期間は，その BGP 経路が有効である期間を示し，開 始，終了時刻で構成される．属性は，ASパス，MED，LOCAL PREF等のBGP経路の 属性を示す．BGP経路の変動の種別はannounce，withdrawの2種類が存在し，経路更 新メッセージの NLRI フィールドに存在するプレフィクスは announce，withdrawn routesフィールドに存在するプレフィクスはwithdrawとして扱う．

各BGP経路の変動に際し，プレフィクス，観測点が一致し，期間の終了時刻がnullで あるBGPテーブルを検索する．BGPテーブルの検索結果と，受信したBGP経路の種別 により，以下のようにBGPテーブルを更新する．

(1) BGPテーブルが存在せず，BGP経路がannounceの場合，annnouceの属性に従い，

新しいBGPテーブルを作成する．

(2) BGPテーブルが存在し，BGP経路がannounceの場合，announceの属性がBGPテ ーブル上の属性と異なれば，既存 BGP テーブルには終了時刻を設定する．さらに，新し いBGPテーブルを作成し，新たに受信したBGP経路の属性を設定する．

(3) (2)において，announceの属性がBGPテーブル上の属性と同じであれば，BGPテーブ ルの更新は行わない．

(4) BGPテーブルが存在し，BGP経路がwithdrawの場合，既存のBGPテーブルの終了 時刻を設定する．

図 8-4 BGPテーブルの更新

8.3.3 BGP テーブルの構成

図 8-5に，BGPテーブルの構成を示す．個々のBGPテーブルは，プレフィクス，観測 点，有効期間の情報を持つ．テーブル内のパラメータのデータ型として，32ビットの数値

である INTEGER，文字列である TEXT の 2種類のみを扱う．プレフィクスは，2 つの

INTEGER のパラメータで表現し，プレフィクス”A.B.C.D/X”の場合，これらはプレフィ

クスID: prefixid=A*(256^3)+B*(256^2)+C*256+D，プレフィクス長: prefixlen=Xとなる．

ユニークな prefixid 毎に，BGP テーブルを検索するためのキーを設定する．観測点は，

ルータを識別する観測点ID(obsid)と，観測点が存在するASを示す観測点AS(obsas)の2

つのINTEGERのパラメータで構成する．図 8-5において，aspath以下のパラメータは

属性を示し，各BGP経路のBGP属性を管理するために用いる．

図 8-5 BGPテーブルの構成

8.3.4 検索手順

本経路検索システムでは，以下のように，運用者からの検索要求が発生することを仮定 している．

z 多くの運用者が，絶え間なくあるいは同時にデータベースへのアクセスを行う．従っ て，データベースは，常時アクセス可能である必要がある．

z 運用者は，現在，過去のいずれのBGP経路も参照する．

z 特定のアドレスにおける障害の有無の調査を目的とするため，運用者は，少なくとも，

プレフィクスやIPアドレスなど，特定のアドレスを指定してBGP経路を検索する．

z 運用者は，検索対象のBGP経路を絞り込むため，自身が把握している情報に基づき，

アドレスに加え，時間，観測点，属性等のパラメータを指定することもありうる．

典型的な検索におけるSQL構文の例を図 8-6に示す．指定したアドレスがプレフィク スの場合，(1)に示すように，そのプレフィクスを数値化した findprefixid，findprefixlen を，BGPテーブル内のプレフィクスと比較する．IPアドレスを指定した場合，(2)に示す

ように，IPアドレスを数値化したfindipidを各プレフィクス長でマスクした値をprefixid と比較する．この検索方法により，プレフィクス長が不明の場合において，不等式を使わ ずに IP アドレスを含むプレフィクスを検索することができる．なお，検索キーの効率向 上のため，トップ部の条件に従った検索を先に行う．

次に，時間を条件とした場合の例を(3)～(5)に示す．現在の BGP 経路を検索する場合，

(3)のように，endtime=nullを条件とする．過去のある１時刻のBGP経路，過去のある２ 時刻間に発生した全BGP経路の変動を検索する場合には，それぞれ(4)(5)の構文となる．

図 8-6 SQL構文による検索例

8.3.5 初期実装

初期の実装として，汎用データベースソフトを用いて，PC 上に本経路検索システムを 実装した．OS は FreeBSD 5.l-RELEASE とし，データベースソフトとして，SQLite 3.3.13[67]およびMySQL server 5.0.37[68]を使用した．

今回は，システムの性能評価が目的であるため，下記のように実装を簡略化した．登録 部はオフライン(非リアルタイム)で動作することとし，RIB/UPDATEファイルをデータベ ース化する機能を実装した．図 8-5に記載されたパラメータのうち，属性についてはAS pathのみを実装した．

双方のデータベースソフトにおいて，BGPデータベースの操作には，同じ意味を持つコ マンドを使用した.BGPテーブルの構成定義には，”create table”を用いた．検索キーの設 定には，”create index prefixidx on BGPtable (prefixed)”を実行した．BGPテーブルの要 素の新規追加，更新には，それぞれ”insert into BGPtable”，”update BGPtable”を使用し た．終了時刻が一定時間(reservationpreriod)以上前の BGP テーブルは，”delete from BGPtable where endtime<currenttime-reservationpreriod”を定期的に実行することに より削除した．

8.3.6 応用

本経路検索システムは，図 8-7 経路検索システムの応用例に示すようにさまざまなネ ットワーク運用システムとして活用できる．例１は，サービスプロバイダが自身の BGP 経路を高速に検索するために使用する例である．この場合，観測点や経路検索システムは 全てプロバイダ自身が用意する．例２は，インターネット全体で経路検索を行う形態であ り，プロバイダ，データベース提供者，観測点がそれぞれ別の組織として存在する．経路 検索システムは，データベース提供者によって運用される．データベース提供者は，異な る組織に存在する複数の観測点から BGP 経路を収集する．観測点等の情報をトレース提 供者間で共有することにより，プロバイダからの要求に対し，要求を満足する BGP 経路 を持つデータベース提供者を自動的に探索する仕組みも可能となる．

図 8-7 経路検索システムの応用例