基于環狀檢測/備份鏈的移動代理容錯方法

張玉軍，張紅梅，馬超，許智君，張瀚文

（1.中國科學院 計算技術研究所 網絡技術研究中心，北京 100190；2.中國科學院 高能物理研究所計算中心，北京 100049）

1 引言

移動IP是網絡層移動管理解決方案，引入了多種移動代理支持節點移動，有移動IPv4（MIPv4）[1]和移動 IPv6（MIPv6）[2]兩項標準，其主要區別在于 MIPv6中沒有外地代理的概念，而由家鄉代理（HA, home agent）作為支持移動功能的唯一基礎設施。在MIPv6網絡中，家鄉代理是移動節點（MN,mobile node）能夠被尋址的最關鍵因素，如果家鄉代理失效，發往MN家鄉地址的數據分組將不能被MN接收到，MN將喪失可尋址性。即使在實現路由優化的場景下，移動節點在通信節點上的注冊過程仍然離不開家鄉代理的支持。為保證移動 IPv6網絡中家鄉代理的可靠服務，本文給出了一種基于環狀檢測/備份鏈的移動代理容錯方法。

2 相關工作

研究容錯的目的是提升系統可靠性，現有研究可分為 2類：基于信息備份的方法[3～8]和基于信息獲取的方法[9,10]。實現容錯的關鍵在于信息備份和服務遷移，下面分別針對這2個問題對現有方案進行分析。

表1中的方案大多是針對移動IPv4提出的，應用于移動 IPv6普遍存在信息冗余大、服務接管時間長、對MN不透明等問題，影響上層應用特別是實時應用的服務質量。移動 IPv6協議標準給出了移動節點維護家鄉代理的過程，其中移動節點能夠處理家鄉代理失效的情況，將這種方法稱為基于被動檢測和恢復的容錯方法（PDRM, method based on passive detection and recovery），其基本過程如下（如圖1所示）。

1) 在T0→T1階段，MN通過動態家鄉代理地址發現機制（DHAAD, dynamical home agent address discovery），獲取其家鄉鏈路上的有效家鄉代理。

2) 在T1→T2階段，MN選擇一個家鄉代理進行家鄉注冊。

3) 在T2→T3階段，家鄉代理為該MN提供服務。在T3時刻，家鄉代理失效。

4) 在T4時刻，MN被觸發執行家鄉注冊，觸發條件有2種可能性：當前注冊即將過期或者MN移動到新的位置。

如果家鄉注冊在T4→T5階段不能夠成功，則MN認為其當前的家鄉代理已經失效，此時MN的狀態轉移為S0，將重新啟動家鄉代理獲取和重新注冊過程。

可以看出，當一個 MN的家鄉代理失效后，MN 將經過一段時間（T3→T4）才會啟動注冊嘗試過程；如果多次注冊不成功，才能夠確認其家鄉代理失效并重新獲取家鄉代理進行重新注冊。其中，T0→T1和T4→T5階段的延時基本上為固定值，可以使MN每次注冊時都從其所保存的家鄉代理列表中選擇一個家鄉代理進行注冊，從而降低以至消除這2個階段的延時。

3 基于環狀檢測/備份鏈的方法

為實現快速有效的失效檢測和服務遷移，將同一鏈路上的家鄉代理組織成環狀的檢測和備份鏈（D&B chain, detection & backup chain）結構，其生成方法如下：在家鄉鏈路存在n個有效HA的情況下，利用一種結果唯一的排序方法對n個HA進行排序，排序結果首尾連接形成環狀結構（HA1→HA2→…→HAn→HA1）。其中，HAi把自己的注冊信息在HAi+1上進行唯一備份，相鄰的2個HA之間基于路由宣告消息的剩余生存期相互進行有效性檢測（如圖 2所示）。當 HAi失效時，HAi?1和HAi+1都能夠檢測到失效發生。

1) HAi?1會把自己所服務的MN的注冊信息在HAi+1備份，同時廣播發送鏈同步消息。

表1 現有的移動代理容錯方法

圖1 基于被動檢測和恢復的容錯方法

圖2 環狀檢測和備份鏈的結構

2) HAi+1會通過發布代理鄰居宣告消息，暫時接管 HAi的工作，同時向 HAi服務的 MN發送DHAAD應答消息。

3.1 容錯方法設計

基于環狀檢測和備份鏈結構，設計了一種基于環狀檢測/備份鏈的容錯方法（DBCM, method based on D&B chain），該方法的描述如下。

1) 采用結果唯一的排序方法，使得HA及MN能夠生成關于當前有效HA相同的鏈式結構。

2) 相鄰的 HA之間基于路由宣告消息的剩余生存期相互進行有效性檢測。

3) 每一個HA都將自己所服務的MN的注冊信息在下一個HA上進行唯一備份。

4) 一旦HAi+1檢測到HAi失效，HAi+1發布代理鄰居宣告消息為HAi服務的MN提供數據轉發服務。

5) HAi+1向HAi服務的MN發送DHAAD應答消息，基于該消息，MN能夠獲知其當前HA已經失效。

6) MN從DHAAD消息中選擇HAi+1作為默認家鄉代理，重新進行注冊。

7) HAi+1收到MN的注冊請求后，將其注冊信息在HAi+2上備份，至此容錯處理過程完成。

從MN的角度來看，該方法的基本過程如下（如圖3所示）。

1) 在T0→T1→T2→T3階段，基本過程與圖1相同。

2) 在T3時刻，家鄉代理失效。在T4時刻，MN收到來自家鄉鏈路的DHAAD應答消息，可獲知其當前家鄉代理已經失效。此時MN回到狀態S1，從DHAAD消息中重新選擇HA進行注冊。

忽略信息的本地處理延時和傳輸延時，可知在T4時刻，已有HA暫時接管了失效HA的工作，即僅在T3→T4階段，MN失去可尋址性。

3.2 數據結構定義

為了維護環狀檢測和備份鏈，需要定義2個數據結構：家鄉代理表（HAT, home agent table），用于存儲當前鏈路上的家鄉代理，其結構為＜家鄉代理地址、家鄉代理有效期、家鄉代理優先級＞，HA和MN都需要維護HAT；注冊信息表（RIT, registration information table），用于存儲移動節點的注冊信息，其結構為＜家鄉地址、轉交地址、注冊有效期、備份狀態標記＞。

家鄉代理的排序規則可采取如下方案：首先按照HA的優先級由高到低進行排序；對于優先級相同的 HA，按照地址的數值順序由小到大進行排序（如圖4所示）。MN的HAT基于動態家鄉代理地址發現機制進行維護，HA的HAT基于IPv6的鄰居發現機制進行維護。

圖3 基于環狀檢測和備份鏈的容錯方法

圖4 家鄉代理排序方案

除HAT外，每一個HA還需要維護RIT，用于存儲移動節點的注冊信息。對于HAi來說，通過接收來自2個方面的注冊信息維護RIT：接收到來自MN的注冊信息，創建/更新相應的注冊信息條目，并把該注冊信息發送給 HAi+1進行備份；接收到來自 HAi?1的備份信息，創建/更新相應的注冊信息條目。

RIT中備份標志的取值為0、1、2。0表示該條目是正常的注冊信息，HA正為相關MN正常提供服務；1表示該條目是來源于前一個HA的備份注冊信息；2表示HA正暫時為相關MN提供服務，即MN的當前HA已經失效。HAi收到家鄉注冊消息后，檢查自己的RIT并如下處理：如果該消息來自RIT中已有的一個MN，且備份標志置位（1或2），則備份標志置0，更新該RIT條目，把該條目備份到HAi+1上；否則，按正常注冊消息處理。

3.3 容錯算法描述

基于前面對容錯方法的描述，設計了在 HAi上運行的容錯算法（如圖5所示），該算法主要描述了HAi在檢測到HAi?1或者HAi+1失效后的處理過程。

圖5 家鄉代理中的容錯算法

3.4 處理流程

假設在家鄉鏈路上有4個家鄉代理HA1、HA2、HA3、HA4，家鄉鏈路前綴為3ffe:320e:1:211::/64，其地址分別為3ffe:320e:1:211::100/200/300/400，優先級由高到低，家鄉代理HAi（i=1, 2, 3, 4）服務的MN記為MNi1、MNi2…。經過排序和初始注冊后，HAi維護如圖6所示的HAT和RIT。

圖6 未失效情況下HAi維護的HAT和RIT

假設在某一時刻HA3失效，根據容錯算法，在HA3最后一次發送的路由宣告消息的生存期結束之后，HA2和HA4將能夠檢測到HA3失效。

1) 對于 HA2來說，會把 MN2i的注冊信息在HA4上進行備份，同步更新HAT，并廣播HAT同步信號。

2) 對于 HA4來說，發布代理鄰居宣告消息把HA3的IP地址映射到HA4的MAC地址上，向RIT表中所有MN_backupflag為1的MN發送DHAAD應答消息，同步更新HAT，并廣播HAT同步信號。

3) 對于HA1來說，收到HAT同步信號后，同步更新HAT。

這樣處理完之后，HA4上備份了 HA2和 HA3的注冊信息，同時HA4還暫時充當了MN3i的家鄉代理。在收到 MN3i的家鄉注冊消息后，HA4才成為 MN3i真正的家鄉代理并把相應的注冊消息在HA1上備份。容錯處理過程中RIT表的變化情況如圖7所示。

4 服務中斷時間的理論分析

把家鄉代理失效后移動節點失去可尋址性的這段時間稱為服務中斷時間（SBT, service break time），本節對PDRM方案和DBCM方案的服務中斷時間進行理論分析。

4.1 PDRM方案的服務中斷時間

圖7 容錯過程中RIT的變化

根據第2節的分析和說明，優化后的PDRM方案的服務中斷時間主要集中在T3→T4階段（如圖1所示），這段時間主要指從HA失效到MN重新啟動家鄉注冊之間的時間間隔。MN重新啟動家鄉注冊有 2種觸發條件：其當前的注冊信息到期或者MN移動到新的位置。

從MN移動到一個新的位置開始，其每次的家鄉注冊有效期應該是一個隨機值，讓nα表示MN在當前位置的第n次家鄉注冊的有效期，并且讓nα獨立同分布于隨機變量α。用()tθ表示從HA失效到最近一次家鄉注冊的有效期到期的時間間隔（如圖8(a)所示），根據更新過程理論，有

圖8 對PDRM方案服務中斷時間的分析

MN可能在不同的接入域之間移動，其在每個域的駐留時間是一個隨機值，用nβ表示MN在第n次運動后所到達域的駐留時間，并且讓nβ獨立同分布于隨機變量β。用()tη表示從HA失效到MN離開當前接入域的時間間隔（如圖8(b)所示），有

4.2 DBCM方案的服務中斷時間

在DBCM方案中，相鄰的HA一旦收不到路由通告，將會認為該HA失效。同樣采用更新過程理論，用nυ表示失效HA的第n次宣告間隙，并且讓nυ獨立同分布于隨機變量υ，用()tσ表示從該HA失效到其下一個路由通告的時間，則σ即為DBCM方案的服務中斷時間（如圖9所示），可知

圖9 對DBCM方案服務中斷時間的分析

4.3 服務中斷時間的對比分析

不失一般性，考察家鄉注冊有效期α為固定值k、駐留時間β符合固定區間[,]m n均勻分布的情況。由式(1)、式(2)可得

圖10 服務中斷時間的概率密度

圖11 服務中斷時間的概率分布

5 仿真評價

基于NS2平臺實現了PDRM方案和DBCM方案，拓撲結構見圖 12所示。在家鄉鏈路上部署 4個HA（HA1～HA4），這些HA的配置、優先級和組織關系見3.4節中的描述。仿真環境中有12個MN，初始配置時每個HA服務3個MN，HAi(i=1, 2, 3, 4)服務的3個MN標記為MNi1、MNi2、MNi3，所有MN在BS1和BS2之間移動。通過仿真對2種方案的服務中斷時間、上層應用分組丟失率、信令開銷等指標進行比較。

圖12 仿真的拓撲結構

5.1 服務中斷時間

根據式(4)，DBCM方案的服務中斷時間與路由宣告間隙有關。當HA以固定間隙周期性進行路由宣告時（即ab= 時），式(4)退化為

從式(7)可知，在固定間隙周期性發布路由宣告的情況下，DBCM方案的平均服務中斷時間與路由宣告間隙成正比。圖 13給出了在路由宣告間隙從[0～1]s變化時2方案的服務中斷時間，可以看出，DBCM方案的服務中斷時間小于 PDRM 方案，且隨著路由宣告間隙的增大，DBCM方案的服務中斷時間呈現出線性增長的趨勢，這與通過式(7)得到的結論一致。

圖13 服務中斷時間隨路由宣告頻率的變化關系

5.2 分組丟失率

服務中斷時間可以用應用層分組丟失率直觀反映。在仿真中，讓CN向MN11的家鄉地址發送UDP數據分組，數據分組發送率符合參數為25packet/s的泊松分布，分別統計2種方案在有HA失效情況下能夠到達MN11的數據分組的數量。仿真過程如下：在第10s時，HA1失效，HA2成為MN11的默認HA；在第20s時，HA2失效，HA3成為MN11的默認HA；在第30s時，HA3失效，HA4成為MN11的默認HA。

圖14給出了在這一仿真過程中MN11累積收到的UDP數據分組的數目。可以看到，對PDRM方案來說，每次MN11的默認家鄉代理失效，都會存在一個明顯的服務中斷時間，大約為2～3s。與之相比，DBCM方案的服務中斷時間要小很多，可以更好地降低HA失效對上層應用的影響。

圖14 容錯處理過程中的數據分組接收數目

5.3 信令開銷

信令開銷也是評價容錯方案的重要指標，信令開銷分為2類：局部信令和全局信令。將家鄉鏈路和移動節點當前位置之間的信令稱為全局信令，將局限于家鄉鏈路上的信令稱為局部信令。相比于局部信令來說，對全局信令進行優化更有價值。采用5.2節中的仿真過程，獲得了2種方案的局部信令和全局信令（如圖15所示）。可以看出，DBCM方案引入的局部信令多于 PDRM 方案，這是因為DBCM 方案引入了家鄉代理之間的信息備份開銷和同步信令開銷；但 DBCM 的全局信令開銷小于PDRM方案，這是因為其省略了失效檢測時的重新注冊嘗試和家鄉代理的發現過程。在圖 15所示的全局信令中，有些是與容錯處理過程無關的，例如定期綁定更新消息等，如果去掉這部分信令，DBCM比PDRM大約降低了40%的全局信令開銷（如圖16所示）。

圖15 容錯處理過程中的信令開銷

圖16 容錯處理過程帶來的全局信令開銷

6 結束語

針對現有移動IPv6網絡家鄉代理容錯方案的不足，本文提出了一種基于環狀檢測和備份鏈的容錯方法，通過在家鄉代理之間形成有效性檢測關系和注冊信息備份關系，可以大大提升家鄉代理失效后的處理效率。本文提出的方法僅基于家鄉代理之間的信息備份、相互檢測和服務遷移實現容錯處理，向移動節點屏蔽了家鄉代理失效后的處理過程，便于在現有的網絡上部署應用。如果有多個相鄰的HA同時失效，假設HAm、HAm+1、…、HAn同時失效，在現有方案中HAm至HAn?1將同時失去備份信息，無法實現自動的服務遷移，其處理過程將退化為與PDRM方案相同，而HAn失效后的處理過程不受影響，可見在任意情況下，本文方案均優于PDRM方案。在DBCM方案中，可以采取動態散列表的方法，讓每一個HA在其下一個HA上備份注冊信息的同時，通過基于地址的散列運算另外維護一個注冊信息的備份節點，從而提升多個相鄰 HA同時失效后的處理效率，這將是下一步的研究重點。

[1]PERKINS C.IP Mobility Support[S].IETF RFC 3220.2002.

[2]JOHNSON D, PERKINS C, ARKKO J.Mobility Support in IPv6[S].IETF RFC 3775.2004.

[3]WAKIKAWA R.Home Agent Reliability Protocol[S].IETF Draft,2010.

[4]WAKIKAWA R, VALADON G, Murai J.Migrating home agents towards Internet-scale mobility deployments[A].Proceedings of International Conference on Future Networking Technologies (CoNEXT 2006)[C].Lisbon, Portugal, 2006.1-10.

[5]LEE J, CHUNG T M.Performance evaluation of distributed multiple home agents with HAHA protocol[J].International Journal of Network Management, 2007, 17:107-115.

[6]AHN J H, HWANG C S.Efficient fault-tolerant protocol for mobility agents in mobile IP[A].Proceedings of International Parallel and Distributed Processing Symposium (IPDPS 2001)[C].San Francisco,USA, 2001.1273-1280.

[7]CHUANG M H.Fault Tolerance for Home Agents in Mobile IP Master Thesis[D].National Yunlin University of Science and Technology,Taiwan.2003.

[8]CHEN Y S, CHEN C H, FANG H Y.An efficient quorum-based fault-tolerant approach for mobility agents in wireless mobile networks[A].Proceedings of IEEE International Conference on Sensor Networks, Ubiquitous and Trustworthy Computing (SUTC 2008)[C].China, 2008.373-378.

[9]LIN J W, ARUL J.An efficient fault-tolerant approach for mobile IP in wireless systems[J].IEEE Transactions on Mobile Computing, 2003,2(3):207-220.

[10]SHI H, GOTO S.An implementation of multiple home agents mechanism in mobile IPv6[A].Proceedings of International Conference on Testbeds and Research Infrastructures for the Development of Networks and Communities (TridentCom 2007)[C].Orlando, USA, 2007.1-9.