重みパラメータの選定

0 50 100 150 200 250 300

0123456

Number of Neighbors

Memory(MB)

w=1

図5 500ASにおける隣接AS数ごとのQuaggaの消費メモリ量の推定結果と実際

にQuaggaが使用したメモリ量の誤差(ω = 1)

前節で定義した(116)式の妥当性と適切な重みパラメータを評価するための実 験を行った．実験に用いたトポロジはCAIDA Project [63]が2009年7月20日に 収集した，AS Relationshipデータセットを利用し，文献[67]で定義されたフィル タリングルールを用いて上位500ASのASトポロジーを抽出し，AnyBed [66]を

用いてQuagga bgpdおよびzebraの設定ファイルを生成した．IPv4プライベート アドレスを用いた模擬を行ったため，各ASから広報されるOriginの経路は/24 ひとつとなっている．この検証には表2の物理サーバを100台用いた．

始めに重みパラメータを導入しない場合の割り当てメモリとQuagga bgpdが使 用したメモリ量の関係を見る．図4に重みパラメータを導入しない場合(ω = 1)

とQuagga bgpdが使用したメモリ量の関係を示す．この図は横軸がASiと接続

しているAS数，縦軸が割り当てまたは使用したメモリ量になっている．隣接AS 数が多くなると誤差が増えているが，これは1隣接ASあたりの誤差が増えてい るためで，この誤差が積算され結果合計での誤差が大きくなっている．次に，AS 数ごとの提案近似式による推定結果と実際にQuaggaが使用したメモリ量の誤差 を図5に示す．誤差を以下に定義する．

誤差=推定近似結果−使用メモリ量の実測値 (117) ここで，重みパラメータωを設定する際に考慮すべき点を以下に示す．

• 導出したメモリ割り当て量で割り当て不足がない

• 導出したメモリ割り当て量が過剰な割り当てにならない

とくに，ASエミュレーション環境を構築する際，割り当て量が不足した場合 実験環境が構築できなくなってしまう．よって，上記の条件のうち割り当て不足 が起きないωの中で最も割り当てるメモリ量が少なくなるようなωを求める．

本稿では仮想計算機上にBGP経路制御プログラムを動かし，ASエミュレーショ ン環境を構築することを目指しているが，仮想計算機にメモリを割り当てる際の 単位は1MB以上であり今回設定する重みパラメータは500ASで得られたデータ の中で誤差が-1MB以下であれば，仮想計算機に割り当てる量を決定する場合に 切り上げることで影響がなくなる．よって，今回は500ASにおいて負方向の最大 誤差が-1MB以下になる最大のωを探索する．

500ASの場合，ω= 1.4とすると割り当てたメモリ量と消費したメモリの誤差

で負方向に最大の誤差は-0.74MBとなり，ω = 1.5では誤差は-1.024MBと条件を

満たさなくなる．そこで，500ASのトポロジにおいて導出されたω = 1.4の規模 追従性について次節で確認を行う．

0 50 100 150 200 250 300

01234

Number of Neighbors

Memory(MB)

w=1.4

図6 500ASにおける1隣接ASあたりの割り当てメモリ量と消費メモリ量の差

(ω = 1.4)

0 100 200 300 400 500

02468

Number of Neighbors

Memory(MB)

w=1.4

図7 1000ASにおける1隣接ASあたりの割り当てメモリ量と消費メモリ量の差

(ω = 1.4)

0 200 400 600 800

0246810

Number of Neighbors

Memory(MB)

w=1.4

図8 1500ASにおける1隣接ASあたりの割り当てメモリ量と消費メモリ量の差

(ω = 1.4)