Event Driven Topology Broadcast Without Sequence Numbers
IEEE Trans. on Communications, Vol.37 No. 5 MAY 1989
一般的なtopology algorithmはauxiliary infromation(seqnum, age, msg counter, time stamp等)を用いて、最新の情報か、また必ずそれぞれのノードで持つ情報が消されることを保証している。
この論文の手法はこれらのaux infoを全く用いないこと。periodic retransmitもしない。
1. 他のノードからupdate msgを受け取った。 2. リンク状態が変わったことをdetectした、
という二つの反応でupdate packetを投げる。
この方式の利点は、1. seqnumのような複雑な処理をしなくて済む(timer等も含め), 2. correctness proofが簡単になる。
細かいことは追記に。
アルゴリズムはDijkstraと似ている。すべてのリンクの長さ１としたもの。
データ構造
T^i: ノードiのトポロジテーブル
T^i_j: ノードi上の隣接ノードjの保持するトポロジテーブルのキャッシュ(ポートトポロジテーブルと呼ぶ)
Pk: (k >= 1) 最短k hopでノードiへ到達できるノードの集合
Lk: (k >= 1) link(m, n)の集合。ただしノードiからkホップで近いほうのノードに到達できること。また、リンクのstatusはupじゃないといけない。
N(m): ノードmへの最短パスは隣接ノードN(m)を通過する
s(i, m): ノードi上の隣接ノードmへのリンクのstatus
アルゴリズムの特性。
基本的に、single linkのstatus changeがメイン。N: node数、 L: link数、
Time complexity(the amount of time which it takes to terminate): O(N + K)
Kは、status changeしたリンク数。
communication complexity(the numer of messages which the algorithm sends): O(L)
computational requirment(the amount of processing which is required at the network nodes): O(L)
memory requirement(the amount of node memory which the algorithm and its data consume): O(LBi) where Bi is the number of neighbors of node i.
トラックバック(0)
このブログ記事を参照しているブログ一覧: Event Driven Topology Broadcast Without Sequence Numbers
このブログ記事に対するトラックバックURL: http://www.imaq.net/cgi-bin/mt/mt-tb.cgi/184
コメントする