基于環(huán)狀檢測/備份鏈的移動代理容錯方法

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

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

1 引言

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

2 相關工作

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

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

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

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

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

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

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

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

3 基于環(huán)狀檢測/備份鏈的方法

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

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

表1 現(xiàn)有的移動代理容錯方法

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

圖2 環(huán)狀檢測和備份鏈的結構

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

3.1 容錯方法設計

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

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

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

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

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

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

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

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

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

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

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

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

3.2 數(shù)據(jù)結構定義

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

家鄉(xiāng)代理的排序規(guī)則可采取如下方案：首先按照HA的優(yōu)先級由高到低進行排序；對于優(yōu)先級相同的 HA，按照地址的數(shù)值順序由小到大進行排序（如圖4所示）。MN的HAT基于動態(tài)家鄉(xiāng)代理地址發(fā)現(xiàn)機制進行維護，HA的HAT基于IPv6的鄰居發(fā)現(xiàn)機制進行維護。

圖3 基于環(huán)狀檢測和備份鏈的容錯方法

圖4 家鄉(xiāng)代理排序方案

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

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

3.3 容錯算法描述

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

圖5 家鄉(xiāng)代理中的容錯算法

3.4 處理流程

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

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

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

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

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

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

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

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

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

4.1 PDRM方案的服務中斷時間

圖7 容錯過程中RIT的變化

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

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

圖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 服務中斷時間的對比分析

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

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

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

5 仿真評價

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

圖12 仿真的拓撲結構

5.1 服務中斷時間

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

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

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

5.2 分組丟失率

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

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

圖14 容錯處理過程中的數(shù)據(jù)分組接收數(shù)目

5.3 信令開銷

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

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

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

6 結束語

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