yasu's blog

A distributed algorithm for finding shortest pairs of disjointpaths

Ogier, R. Shacham, N. , "A distributed algorithm for finding shortest pairs of disjointpaths", INFOCOM '89. Apr, 1989, page 173-182 vol.1

理解するには説明が不足していて (i,k)_j とか頻繁に出てくるが j の意味が理解できないので， さっぱり意味がわからない．変数多すぎだが，何を意味してるんだか．．． 読んでて疲れる．

著者の Richard Ogier は TBRPF の人か．

Conclusion の章無えし！

以下は憶測で，とても怪しい．この理解が正しく無さそうな記述もある．

後ろのアルゴリズムの部分をちょっと読むと少しイメージがつかめるかも． p178 左段真ん中で，M'(i) がネクストホップ集合らしいということが かろうじてわかった．

M'(i) will denote the set of nodes k such that (i,k)_j is a link for some j, i.e., such that k \in T(i,j)-i for some j \in M(i).

終点 j へノード i から到達するための経路を考える．T(i,j) は i から j への最短全域木の中の経路なので，T(i,j) に含まれ， (i,k) が終点 j へのリンクであるようなノード k の集合が M'(i)， と読むのかな？ M(i) がなんであるかちょっと忘れた．．．

asynchronous 版のアルゴリズムを提示し，その停止性とかも議論してから， その後（論文の最後に）synchronous 版のアルゴリズムを議論している． なぜか？普通最終目的は asynchronous にしてルータ上で分散させて実行すること ではないか？計算量の議論をするために synchronous 版を議論する必要が あったのか？不明．