FSR[路由協定]

FSR[路由協定]
更多義項 ▼ 收起列表 ▲

FSR協定(Fisheye State Routing Protocol)是一種先應式的鏈路狀態協定,但是綜合採用了距離矢量和鏈路狀態兩種協定的思想。

基本思想

FSR協定基於一種“魚眼”(fusheye)技術,模仿魚眼的功能,通過對不同距離的節點採用不同的路由更新頻率,使得距離越近的節點,掌握的路由信息越準確。另外它的路由更新分組僅在鄰節點之間交換,減少了用於路由的控制開銷。

關鍵技術問題

1、魚眼技術

模仿魚眼的生理特徵,FSR協定採用了以下作法:一是劃分節點不同層次的魚眼範圍(scope of fisheye),二是在不同魚眼範圍內採用不同的路由更新頻率,由此維護遠近不同精度的路由信息。

圖1-1 FSR協定的魚眼範圍 圖1-1 FSR協定的魚眼範圍

節點i的魚眼範圍定義為從i出發,在N跳內可達的節點集合。如圖1-1所示,節點11有3個魚眼範圍:範圍1為節點11一跳可達的節點集合,範圍2為節點11兩跳可達的節點集合,範圍3為節點11多於兩跳可達的節點集合。魚眼範圍的層次數和半徑由網路的大小來確定。

FSR協定採用周期性傳送鏈路狀態信息分組的方法來更新路由表。魚眼範圍不同,路由的更新頻率也不同,魚眼範圍越小,其路由更新頻率越高,這樣可以大大地降低路由的開銷。目的節點距離自己的距離不同路由信息的精度也不相同,目的節點距離越遠,路由信息就越不準確。

2、路由分組的傳遞方法

FSR協定是一種鏈路狀態協定,網路中的節點間需要交換鏈路狀態信息分組,但是不同於普通的鏈路狀態協定。FSR協定的鏈路狀態信息分組僅在鄰節點之間交換,而普通的鏈路狀態協定採用洪泛的方法。

路由協定描述

設自組網的模型為無向圖G=(V,E),V為節點的集合,E為連線V中節點的無向邊。每個節點代表自組網中的一個無線移動設備,有唯一的標識符,傳輸範圍為R且有無窮的存儲空間。節點何以自主移動,改變速度及方向等。當兩個節點i,j之間的距離小於或等於傳輸範圍R時,i,j之間就形成一條無向邊(i,j);當節點i,j運動導致兩者之間的距離大於傳輸範圍R時,就需從圖G中刪除無向邊(i,j)。

1、信息種類

(1) 存儲的訊息

每個節點i都維護一個列表和三張表,如下所述。

1)鄰居列表A

為節點i的鄰節點列表

2)拓撲表TT

每個節點j,均在該表中有一個路由條目。該表的結構如圖1-2所示。

節點標識符j 鏈路狀態LS(j) 時間戳SEQ(j)

圖1-2 FSR協定節點的拓撲表

LS(j)欄位中存儲節點j報告的鏈路狀態,SEQ(j)欄位中存儲節點j產生該鏈路信息的時間戳。

3)下一跳表NEXT

NEXT(j)給出到達目的節點j最短路徑上的下一跳地址。

4)距離表D

D(j)給出從節點i到節點j最短路徑的長度。可以使用不同的加權函式來計算,本算法使用跳數來計算最短路徑,即如果兩個節點之間存在一跳邊,則兩者之間的權值為1;否則兩者之間的權值為無窮。

(2) 交換的訊息

圖1-3 使用FSR協定後控制訊息的變化 圖1-3 使用FSR協定後控制訊息的變化

鄰節點之間周期性地交換拓撲表中的鏈路狀態信息,如圖1-3所示,離節點的距離越近,更新的頻率越高,圖中字型加黑且傾斜的條目比不加黑不傾斜的條目更新頻率高。

2、工作過程

(1) 節點的初始化

協定開始運行時,每個節點的鄰居列表A和拓撲表TT均為空。

(2) 路由分組的處理

假設一個節點只能收到鄰節點傳送的鏈路狀態分組,這樣當節點i收到鏈路狀態分組時,就會將該分組的傳送者添加至自己的鄰居列表A,並更新本地存儲的拓撲表TT。對每個TT中的節點j,檢查pkt.SEQ(j)與本地的TT.SEQ(j),如果前者的序列號新,則使用pkt.LS(j)替換本地的TT.LS(j),同時pkt.SEQ(j)替換本地的TTi.SEQ(j)。

(3) 修改鄰居列表和拓撲表

處理完接收到的路由分組後,節點i將檢驗本地鄰居列表A中節點的有效性,用新的A修改拓撲表TT中的TT.LS(i)。

(4) 計算最短路徑

根據最新的拓撲表TT,使用選定的最短路徑計算節點i至所有其他節點的最短路徑,更新NEXTi表及D表。

(5) 向鄰節點傳送最新的鏈路狀態信息

掃描本地的拓撲信息表TTi,對每一個條目TTi.LS(j),根據D(j)是否在FSR協定規定的範圍層次n內,決定是否將TTi.LS(j)加入到欲傳送的路由分組中。FSR協定有不同的範圍層次,不同的範圍層次有不同的更新頻率,離節點的距離越近,更新的頻率越高。

生成路由分組後,向鄰節點廣播並進入下一輪的路由分組處理過程。

(6) 數據分組轉發

每個節點根據自己計算的“最短”路徑轉發數據分組。在轉發節點與目的節點之間距離較遠的情況下,受鏈路狀態傳播時延和節點移動性的影響,該“最短”路徑未必最短。隨著數據分組距離目的節點越來越近,轉發節點存儲的路由信息也越來越精確,直至數據分組最終到達目的節點。

總結

FSR協定是一種先應式的自組網路由協定,它運用魚眼技術對不同距離的節點採用不同的路由更新頻率,並且路由分組僅在鄰節點之間交換,降低了路由的控制開銷。通過恰當選擇魚眼範圍層次和半徑大小,可以提供比較準確的路由信息。該協定存在的問題是路由表的大小仍然隨網路的增大而線性增加,到達遠處目的節點的路徑可能是過時的。

相關詞條

相關搜尋

熱門詞條

聯絡我們