HSR(路由協定)

HSR（Hierarchical State Routing,分層狀態路由）協定是一種層次化的鏈路狀態路由協定，它基於組移動模型將網路中的節點劃分為不同的組，每個組形成一個邏輯子網。

基本介紹

• 中文名：分層狀態路由
• 外文名：Hierarchical StateRouting
• 外語縮寫：HSR
• 類型：路由協定

基本思想

HSR協定 不僅根據節點的物理位置使用分散式分群思想劃分物理分群，動態生成節點的物理層次地址，以決定數據分組的轉發路徑，而且還根據節點的邏輯地址對其位置進行管理。在每個邏輯子網內至少存在一個歸屬代理，負責管理本子網內節點邏輯地址與當前物理地址之間的對應關係，並為所管理的節點轉發數據分組。節點需要向歸屬代理進行註冊，通告最新的物理地址。

關鍵技術問題

1、物理上的多層分群結構

HSR協定可以根據節點的地理位置關係，維護一個物理的多層分群結構，底層選出的群首成為高一層1群的成員，高一層群的成員又選出新的群首，形成新的群，如此反覆，形成一個多層的分群結構，可以採用多種不同的方法動態生成群及選出群首。圖1-1為一個物理多層分群的例子，在最底層有4個物理的群，其4個群首形成第二層的群，第二層的群首又構成最高層的群。

圖 1-1 物理分層結構示意圖

（1）物理多層分群結構下的節點分類

一個群中通常有3類節點：群首、網關及內部節點，圖1-1中第一層群首節點為1、2、3和4，網關節點6、7、8和11，內部節點為5、9、10、12。群首是群內部傳輸的協調者。

（2）物理層次地址HID

網路中的每個節點都有一個唯一的物理地址（如MAC地址）作為自己的標識NodeID。由於路由的需要，HSR中的每個節點還有一個動態的物理層次地址HID。HID反映節點的物理層次拓撲信息，它是指從最高層群到節點本身的層次化路徑上的節點的NodeID（MAC地址）序列。如在圖1-1中節點12的HID為<3,2,12>，它由從最高層到達節點12的路徑上所經過節點的MAC地址序列組成，節點3為節點12的最高層代表，節點2為節點12的次高層代表。

（3）物理多層分群結構下數據分組的轉發方法

配合使用HSR路由表，節點可以根據HID地址將一個分組從源傳送到目的。如圖1-1所示，節點5將一個數據分組傳送到節點10，節點5的HID為<1,1,5>，節點10的HID為<3,3,10>，節點5首先將分組沿層次向上傳送到節點1，節點1通過一條虛擬鏈路（1,6,2,8,3），將分組轉發至節點3，節點3再沿著向下的層次路徑將分組轉發至節點10.

使用層次地址的好處在於節點一旦收到從高層發來的路由更新分組，可以局部動態地該變自己的HID，無需中央控制。

（4）物理多層分群結構的優缺點

採用物理多層分群結構，可以大大降低路由表維護和存儲的相關開銷。假設網路中有N個節點，如果採用非層次化網路結構，則節點路由表的空間複雜度為O（N）；而HSR路由表的空間複雜度僅為O(M*N)。HSR物理多層分群結構的主要缺點是需要動態地維護分群結構及節點的HID地址，既造成很大的開銷，又使得對節點的跟蹤和定位變得非常困難。另外，節點地址用多個層次的物理地址來標識，與其他路由方式相比，節點地址加長了。

2、 邏輯子網和節點位置管理

採用物理上的多層分群結構進行路由，節點的位置管理是一個難題。由於節點的可移動性，當節點從一個群移動到另一個群的範圍，或任一層的群首發生變換時，都將造成節點HID的變化與更新。隨著節點移動性的增強，這一過程勢必造成大量控制開銷。考慮到在自組網的許多套用場景下，節點具有組移動特性，因此HSR協定還使用了邏輯子網的結構來解決節點移動過程中的位置管理問題。依據某種邏輯或功能上的關係（如戰場上的坦克、某公司的銷售成員等），自組網將節點分成不同的組，每個組稱為一個邏輯子網。在每個組中有一個中心節點，其移動（位置、速度及方向）代表整個組的移動。組的移動軌跡可以預先定義域，既可以是隨機的移動，也可以是有目的地的移動，每個節點除了組的移動，還有獨立的隨機移動，節點的運動由組的運動矢量GM和隨機矢量RM共同決定，如圖1-2所示。在每個邏輯子網內部，至少存在一個歸屬代理，負責管理所屬節點的當前HID地址（位置管理），並為所屬節點轉發數據分組。為了追蹤節點的位置，節點需要向自己的歸屬代理註冊當前的HID地址。註冊過程包括周期性觸發和事件觸發兩種機制。由於一個邏輯子網內的節點通常成組移動，它們一般只出現在相鄰的物理群，因而用於註冊的開銷不會太高。

圖1-2組移動模型

（1）節點的邏輯地址

每個節點具有一個類似於IP位址的邏輯地址，地址形式為<subnet，host>，其中，subnet欄位表示節點的歸屬邏輯子網號，host表示主機號。邏輯地址在全網範圍內是唯一的。由於一個邏輯子網可以跨越多個物理分群，邏輯地址與物理層次地址HID並無確定的對應關係，二者之間的動態映射由歸屬代理負責維護。傳輸層使用節點的邏輯地址傳送數據分組，網路層必須能夠正確地將邏輯地址解析為物理層次地址HID。

（2）歸屬代理HID的獲得方法

歸屬代理也是邏輯子網的節點，出於位置註冊和轉發數據分組的需要，每個節點需要知道自己和通信目的節點歸屬代理的HID。歸屬代理HID的獲得方式如下：歸屬代理將自己的HID通告給網路的頂層節點，然後頂層節點通過分層信息逐級向下傳播，這樣一來，每個節點就可以獲得每個歸屬代理HID與它代表的邏輯子網的子網號之間的一一映射。

路由協定描述

1、信息種類

（1）存儲的訊息

每個節點均存儲物理層次拓撲信息和邏輯子網歸屬代理的相關信息。

（2）交換的訊息

鏈路狀態信息

最底層為群內的物理鏈路信息，高層均為群內的虛擬鏈路信息。

邏輯組的維護信息

包括邏輯子網中的歸屬代理髮布其HID訊息、節點向主代理註冊當前HID訊息等。

2、工作過程

（1）各層鏈路狀態信息的傳遞過程

在一個物理群（層次1）內部，每個節點監視與鄰節點之間鏈路的狀態（如是否連線、頻寬等）並在群內廣播，群首收集歸納群內節點的鏈路狀態信息，並把它通過網關節點傳遞給相鄰群首。這樣一來，每個群首都可以了解與鄰居群首的虛擬連線情況，這種連線關係構成了高一層次的分群（層次2）。層次2節點路由表存儲的鏈路狀態信息，為相鄰兩個群首之間的虛擬鏈路狀態信息。如圖1-1所示，第2層中節點1和節點2之間的虛擬鏈路計算方法：網關6將鏈路6-2的更新訊息傳播至群首1，群首1根據本地鏈路1-6的信息和接收到的鏈路6-2的信息，計算出路徑1-6-2的信息，作為群首1和2之間虛擬鏈路的鏈路狀態信息。虛擬鏈路可以看作一條由低層鏈路組成的隧道。如此反覆，每層都選出群首作為更高層次群的成員，構成更高層次的群。

在高層群內部，節點之間交換虛擬鏈路信息和群成員信息，然後再向低層群節點廣播這些群成員，最終使得每個最底層群中的節點，都存有一個層次的拓撲信息，與普通的鏈路狀態協定的非層次全局拓撲不同。

（2）數據分組的轉發方法

如果一個節點需要向目的節點傳送數據分組，路由過程將分兩個階段進行：從源節點到目的節點的歸屬代理：從目的節點的歸屬代理到目的節點。在第一階段，源節點首先根據目的節點的邏輯地址中的邏輯子網號，通過查詢自己的列表或向最高層節點請求獲得目的節點的歸屬代理HID，然後依據該HID將數據分組向目的節點的歸屬代理髮送。在第二階段，歸屬代理根據目的節點的邏輯地址查詢目的節點當前的註冊HID，並依據該HID將數據分組向目的節點轉發。兩個階段的轉發都依據物理多層分群結構下的數據分組轉發方法進行。如果源節點和目的節點都獲得了對方的HID，則它們之間可以直接傳遞數據分組，而不在需要經過歸屬代理。

總結

HSR協定是一種層次化的鏈路狀態路由協定，它將動態、分散式分群思想與有效的位置/成員管理結合起來，維護節點物理的層次拓撲和邏輯上的子網。HSR協定使用物理層次拓撲解決分組的轉發路徑問題，而使用邏輯子網結構解決節點移動過程中的位置管理問題。HSR協定雖然具有一定的可擴展性，但協定比較複雜，得到的路徑可能為非最優路徑，當網路中節點移動速度較高時，路由開銷也較大。