yasu's blog

Network Routing with Path Vector Protocols: Theory and Applications (Joao Luis Sobrinho)

Joao Luis Sobrinho, "Network routing with path vector protocols: theory and applications", ACM, SIGCOMM '03, p49-60

path vector algorithm が収束するための条件を代数を使って示す． path vector が収束するのは代数構造がmonotone（単調）でisotone（等張）であるとき だと示した．これでは意味わからないので簡単に言うと，ネットワークがあって， その経路の重み付けは任意でいい（BGPポリシも許容する）のだが， その重み付けの任意の関数が単調で等張であることがパスベクタ収束の条件である．

単調は「経路を一つ延ばす（リンクをつけたす）と，重み付け（経路コスト・経路メトリック） が増える」という性質であり，最短経路計算方法のdijkstra計算での正当性の条件： 「全てのリンクメトリックは非負（正の）整数」と同じ意味．

等張というのは，複数の異なる（同一終点への）経路があるリンクに対して拡張されるとき， その経路の間の優先順位が逆転しない，という性質． つまり，終点dに対するノードiでの経路Aと経路Bがリンクl上を伝ってノードjに来たとき， ノードiでは A < B という優先度になっていたのに，ノードjでは A+l > B+l とならない， ということ．代数構造（重み付け関数）が等張じゃないと，全体で最適な経路はこれだ， という定義ができなくなり，各ノードに対して最適（重み付けが最小）の経路が変わる． 等張じゃなくても収束はする（局所最適な経路に収束する）．

上の性質が背理法など使って証明された後，最大帯域経路計算やBGPルートリフレクタの構造， BGPピアリング関係などを解析している．収束するとかしないとか，その条件とか．

前に読んだことあった（ 輪講資料 ，読み直し１回目の メモ ）のだが，今回はパスベクタの停止性について（２回目の）読み直し． 8. PROOF OF CONVERGENCE の後半，proposition 3 の証明が停止性について． ある終点ごとの各パスにはランクが付けられる．これは，パスの優先順位のこと． ランクが低いパスのほうが優先される．パスからランクへの変換（写像）は任意の関数 だというのがBGPがポリシ実現プロトコルだと言われる所以．普通のBGPだと， パス長が短いほうが優先されるので，パス長が短いほうがランクが低い．

パスベクタアルゴリズムが停止することを示すためには， ネットワーク上からルーティングメッセージが無くなることを見せれば良い のだが，それをするには，プロトコルのネットワーク全体の状態を入力として， ランクの数だけの数値を組にしたものを出力する関数 F を定義し， それがルーティングメッセージの受信ごとに辞書的に減少することを見せれば良い （参照[11][12]）．たとえば，ランク数の最大が３であれば，Fの出力 (f_1, f_2, f_3) が (1, 4, 3) -> (1, 4, 2) -> (1, 3, 4) -> (1, 3, 3) ... のように減っていく，という感じ．

ここではルーティングメッセージの受信ごとに減少する関数が定義してある（それが 定義できるから，アルゴリズムは停止するということになっている）のだが， 優先度jの同じパスを（重複して）受け取ると f_j が１減少する（ルール１）となっているため， この関数で f_j の出力が負にならないのかなどが疑問． [11][12]を読む必要があるか…．

自分のアルゴリズムでは，方向の決まったリンクの数をランクとして， その中で各ノードの通信可能量の総和でいけるかな？ 「一旦方向が決まったリンクに対して，それが無くなる・無効になることがない」 「途中のノードのパスが変わるときには，通信可能量の総和の減少がある」 「途中のノードのパスが変わるときには，必ず新しいリンクの方向決定がある」 ことなどを明らかにしないといけないような気がする．

パスベクタの計算量に関しても言及があった．

他に重要なのは，6.2 Main convergence results の頭， パスベクタが収束すれば，全ノードで選択されたパスを合わせると 終点への局所最適な in-tree となる， この証明は [7] に似た方法でできる，というところ． in-tree ということは acyclic である証明もされているのかな？

[12]は従来の distance vector の収束の証明もしているらしい．

• [7] 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.
• [11] L. Lamport. An assertional correctness proof of a distributed algorithm. Science of Computer Programming, 2(3):175・06, December 1982.
• [12] L. Lamport. The temporal logic of actions. ACM Trans. on Programming Languages and Systems, 16(3):872・23, April 1994.