OSPF SPF計算的退避演算法

OSPF在計算SPF時，為了防止震蕩以及連續收到LSA時多次計算SPF，某些代碼里實現了避讓演算法。代碼如下：

Tv_spf：SPF計算完畢後更新此變數

Tv_spf_cur：SPF本次需要延遲的時間，初始值為spf_min_delay

spf_max_delay：SPF最大延遲時間，設定為50s

spf_min_delay：SPF最小延遲時間，設定為500ms

spf_start_delay：SPF開始的延遲時間，設定為spf_min_delay，即500ms

1)獲取當前的系統時間，並計算當前時間和上一次SPF計算完的差值delta

2)判斷delta和spf_cur的差值，如果delta大於spf_cur，進入到a流程，否則進入到b流程

a)設置delay時間為0，並計算hold值，hold=2*spf_cur，hold最大不能超過spf_max_delay，同時比較hold和delta，如果hold比delta小（即當前需要spf計算的時間超過了2倍的記錄的延遲時間）就把spf_cur重新設置為spf_min_delay【即認為不再震蕩，重新恢復spf_cur為初始值】

b)設置delay時間為spf_cur和delta的差值，即認為還沒有到設置的延遲時間，需要繼續延遲delay的時間再觸發。並且，認為發生了震蕩，將spf_cur的時間設置為當前的2倍。

3)判斷spf_start_delay和delay的差值，如果大於零，進入a流程，否則b

a)設置delay為spf_start_delay，即至少要延遲spf_start_delay的時間。

b)不做任何設置

4)判斷spf_cur是否超過spf_max_delay，如果超過，進入（a），如果不超過進入(b)

a)Spf_cur = spf_max_delay

b)不做任何處理

5)開啟定時器，超時時間為delay。

根據以上流程，可以看出，如果不是頻繁震蕩，那麼流程總是1->2(a)->3(a)->4(b)->5。這個時候，SPF計算總是在spf_min_delay時間後觸發，即500ms。

如果頻繁震蕩，那麼流程會進入1->2(b)->3(b)->4(b)->5，此時設置的定時器將會是一個spf_cur-delta的差值，並且由於spf_cur會被更新為當前的2倍，這個延遲將會越來越大，直至50s。

如果震蕩中恢復到穩態，就進入1->2(a)，此時又會把spf_cur更新為最小值。

通過以上分析，可以看出無論是否震蕩，系統總是延遲spf_min_delay才進行SPF計算，那麼當某次介面down，需要快速收斂時，將會有很大的延遲。因此可以把spf_min_delay設置為更小的值來提高收斂速度。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！