yasu's blog

A LOOP-FREE EXTENDED BELLMAN-FORD ROUTING PROTOCOL WITHOUT BOUNCING EFFECT

SIGCOMM の古い論文．J.J.Garcia-Luna-Aceves 著．bouncing effect を回避する distance vector algorithm の改良が載っている．

ディスタンスベクタのアルゴリズムが載っていたり，収束の証明は元の ベルマンフォードと同じだろうに省略されていないでちゃんと載っていたり， "send its routing vector to neighbor" と言っていて ああやっぱり vector って配列のことなんだねっていうのがわかったりする．

BGP には，「BGPを発明しました」という論文が無い．IETFの人たちが 工学的に（？，理論的にではなく）作ったのがパスベクタでありBGPだ． そこらへんの事情は，Huitema 著 Routing in the Internet と合わせて この論文を読むとわかる．huitema 本には「ループを解消するために『直前の 中継ノード』を経路情報に追加する手法が提案されていた」と言っていて， その手法を説明してる元の論文がこれ．この論文には，「Shin and Chen[19] では path 全体が経路情報として記録されていて，オーバヘッドが大きい」と書いてある． つまり，当時からそういう方法は提案されていて，それを IETFの人たちがプロトコルにした，という感じじゃないかな．しかし，Shin and Chen[19] が BGPの発明の元となった論文である，とは言われないので，他にも沢山 あったのだろうか，それとも発明というほどのものじゃないからほっとかれているのか．

「演習プログラムの証明」（アンダスン著）や 「計算機科学入門」（ゴールドシュレーガー・リスター著）を読んでからこの論文を 読むと，「アルゴリズムの正当性は部分正当性と停止性によって証明される」という ことが実践されていておもしろい．4.2 Convergence で背理法によって停止性を 証明している．リンクメトリックが正で，経路メトリックは有限で，経路メッセージは 無限になるというのは矛盾だ，という証明方法みたい．

メトリックが最短となる経路を計算するのではなく，メトリックの総和を最大にする 経路の計算は数学的に最短経路計算より難しい，とどっかで読んだ気がする． 自分のアルゴリズムはメトリックが帯域なので，最大経路に近い． そのため，この証明方法を真似るだけでは不十分・不適切に思えるので， この論文の方法は利用できない．

Network Routing with Path Vector Protocols: Theory and Applications(sobrinho) を辿っていけば，最大経路計算の証明方法にたどり着けるかな．．．