yasu's blog

The Stable Paths Problem and Interdomain Routing

T. Griffin, F. Shepherd, and G. Wilfong. The stable paths problem and interdomain routing. IEEE/ACM Transactions on Networking, 10(2):232・43, April 2002.

BGP のルーティングを Stable Paths Problem (SPP) として モデル化し，それが唯一の解に収束するのかを調べることに 取り組んだ論文．概要，イントロ，関連研究，モデル， 証明，証明，証明，議論，で終わりというスゴイ論文． 結論(conclusion)無いし．

BGPの経路計算は，各ノード（AS）が自分の好き勝手な経路を選択するので， 全体で「経路Aより経路Bのほうが良い」などという重み付けができない． そのため，最短経路計算ではない．各ASが好き勝手な経路を選択する という前提で，経路計算アルゴリズムがいつかある一つの解に収束するかどうか， つまりBGPがある経路群に収束するかをSPPとしてモデル化した． いくつか，SPP（つまり勿論BGPも）が収束しない例について書かれている．

ASトポロジと，それぞれのASが優先するパスの順位(ルーティングポリシの意味を持つ） を定義したものは，SPPの実例（インスタンス）となる．あるSPP実例が 唯一つの解に収束するかどうかを判定する問題は，3-SAT 問題を reduction して （逆か？でもこう書いてあった気がする），NP-完全問題だとわかる．

SPP実例が解を持つか調べるのはほぼ不可能だが，「ある条件を満たすものは かならず解を持つ」という条件を調べることは可能だ． この論文では dispute wheel というポリシー矛盾の構造を定義し， それが含まれなければかならず解が存在することを証明した． dispute wheel があるからと言ってかならず解が無いわけではなく， dispute wheel があるけどある解に収束するSPP実例も存在する．

dispute wheel のモデルを使って，最短経路制御は収束すること， 収束するSPP実例において，回線が故障した場合（別のSPP実例に変化した場合） にも解が存在することなどを示している．

SPPが収束するかの判定に関する計算量の議論はオープン（まだ分かっていない問題） だとしている．これが知りたかったものの一つだったので残念． また，参照元の論文 「Network routing with path vector protocols: theory and applications」 でこれを参照しながら「In this model, the problem is represented by sets of ordered paths, one set per node, leading to a representation whose size may be exponential in the size of the network.」と言っていたので，そのような議論があるかと思っていたが， 3-SATは解空間が大きいので難解な問題（NP-完全）である，というような 議論のことを指していたようだ．．．

また，昔「BGP Flap dampening considered harmful」というような プレゼン資料を見たが，論旨がさっぱり意味わからなかったのだが， もしかしたらこれのことを言っているのかも，というような記述があった． VII章Discussion and Open problems にあった，次のような議論． 回線の揺らぎによるフラップとポリシー矛盾によるフラップは 同じように観測され，見分けがつかない．ポリシー矛盾は 解決しなければBGPが収束しないという大問題なのに，回線の揺らぎからの 影響を緩和するBGP Flap Dampening によってフラップの原因となる ポリシー矛盾が隠されてしまう．これはBGP Flap Dampening という技術の 欠点だ，というもの．

bellman-ford の証明と計算量については，バートセカスのデータネットワーク を参照．日本語版は p380 「すべての i \neq 1 に対して正しい最短(<=1)経路 であるような D_i^(1)=d_li を与える」の部分， d_li ではなくて d_1i だ． 原書も確認した．第２版になっているし原書を読むべき．

追記：(2007/06/26) BGP Flap Damping Harmful は読み返したら 意味わかった．Link