動態源路由協議ＤＳＲ在ＮＤＩＳ架構中的設計與實現

摘 要：研究分析了基于Windows NDIS框架構建無線移動Ad hoc網絡路由協議測試平臺的一般方法，提出了以NDIS中間層驅動形式創建動態源路由協議(dynamic source routing，DSR)的設計方案，有效地解決了嵌入NDIS的DSR協議棧與Windows操作系統既有TCP/IP協議棧以及廠商網卡驅動之間的銜接與交互等關鍵問題，并最終完成了該DSR協議棧的實現。實驗結果表明，該DSR協議棧的設計切實可行，通過在真實環境中的運行測試，為進一步分析研究DSR的安全、優化和應用提供了實體測試平臺。

關鍵詞：無線移動自組網;動態源路由協議;網絡驅動接口規范;中間層驅動

中圖分類號：TP393文獻標志碼：A

文章編號：1001-3695(2009)06-2220-04

doi:10.3969/j.issn.1001-3695.2009.06.067

Design and implementation of dynamic sourcerouting protocol as NDIS intermediate driver

ZHANG Xiang，WANG Wen-yong，HUANG Li-sheng，HUANG Wai-liu

(School of Computer Science Engineering， University of Electronic Science Technology of China， Chengdu 610054， China)

Abstract:Real-world testing platform is very important to promote evaluation of MANET(mobile Ad hoc network) routing protocol. After researching and summarizing the general methods to construct MANET routing protocol stack through Windows NDIS(network device interface specification) architecture， this paper proposed a scheme design to realize DSR(dynamic source routing) protocol through NDIS intermediate driver. This design resolved a series of key problems about cooperation between DSR and Windows inherent TCP/IP stack such as how to process ARP request packet， and also about the DSR inside functions’ realization such as how to count time to resend DSR route request.Experiments results presente the feasibility of this design and implementation.

Key words:MANET(mobile Ad hoc network);DSR;NDIS;intermediate driver

無線移動Ad hoc網絡MANET(mobile Ad hoc network)是一種不依賴于任何固定基礎設施的自組織網絡，具有良好的移動性、自組性和抗毀性，在緊急救援、會務通信以及軍事應用等領域具有廣闊的應用前景。安全高效的路由協議是實現無線移動Ad hoc網絡的重要基礎。國內外在該領域針對路由構建、路由優化、路由安全等方面展開了廣泛研究，目前已經被提交成為RFC的標準協議主要包括AODV、OLSR和DSR等。

在國內的相關研究中，理論探索結合仿真實驗的研究方式得到了廣泛應用，而以實體系統為基礎進行的協議設計研究與實現則相對欠缺。事實上，無線移動環境中由于地形復雜、拓撲變化、噪聲干擾等諸多因素的共同作用，使得信道質量無法保障，節點能量也受到制約，各類應用對于能量的消耗亦有差異。這些現實因素往往難以通過軟件仿真有效展現，也就為MANET路由協議的仿真研究帶來了諸多不便。因此，創建真實的MANET測試環境將為改進優化MANET路由協議，推動擴展MANET應用提供有力的支持。

當前MANET路由協議的設計和實現主要以基于Linux操作系統的研究居多，而涉及Windows操作系統的較少。業已開展的工作中，文獻[1，2]探討了基于Windows 2000操作系統實現DSDV(先驗式)的設計方法，文獻[3]研究了AODV(反應式)在WinCE.NET下的具體實現。本文則以成熟高效的DSR^[4]協議(反應式)作為研究對象，探討了以NDIS中間層驅動形式構建DSR協議棧的若干問題。

1 協議需求分析與整體設計 

1.1 DSR協議簡述

動態源路由協議DSR主要包括路由發現和路由維護兩大功能集合。該協議允許節點根據報文發送的需求動態尋找去往目的節點的路由信息。每一個被發送的數據報文在DSR選項頭中攜帶有完整的從源到達目的的路徑信息，從而有效地避免了環路的產生以及周期性更新路由信息所需要的開銷。同時，任意中間節點一旦監聽到該報文，即可獲取報文中攜帶的路徑信息，可用于更新中間節點的本地路由緩存，增強了路由信息的復用率，并為自動路由縮短等優化措施提供了可能。

DSR通過三個基本數據結構實現尋路與選路功能：DSR路由緩存(DSR route cache)、待發報文緩沖(DSR send buffer)以及路由請求記錄表(DSR route request table)。同時還基于免費路由回復表(gratuitous route reply table)、網絡接口隊列(network interface queue)等數據結構實現路由的優化和維護。

相對于其他MANET路由協議，DSR的主要優點體現為簡潔高效；缺陷是：由于每個數據報文都需要攜帶完整的路徑信息，在減少協議交互通信的同時，增加了報文額外開銷與信道傳輸負擔，文獻[4]針對該問題提出了通過DSR流(DSR flow)的擴展方式，盡量消減數據報文攜帶路徑信息的必要性。本文主要關注DSR的基本功能實現以及協議棧與Windows操作系統之間的交互問題。

1.2 Windows NDIS架構

NDIS^[5](network driver interface specification) 是網絡驅動接口規范的簡稱，最初由Microsoft和3Com公司聯合開發，作為基本網絡通信接口框架廣泛應用于各類Windows操作系統。

NDIS通過對網絡硬件設備的抽象與封裝，規范并簡化了網絡驅動程序的編寫，作為基本網絡通信接口框架廣泛應用于各類Windows操作系統。NDIS在網絡驅動的內部進行了層次化抽象(圖1)，將負責操控網絡硬件設備的底層微端口驅動(miniport driver)與上層傳輸驅動分離開來(transport driver，又稱為協議驅動protocol driver)，同時支持在微端口驅動與協議驅動之間插入中間層驅動(intermediate driver)，從而為系統的網絡通信功能提供廣泛的硬件適用性和良好的協議可擴展性。

NDIS傳輸驅動囊括了OSI模型中傳輸層、網絡層以及數據鏈路層中邏輯鏈路控制子層的功能^[6](圖2)，微端口驅動則對應于數據鏈路層中MAC子層，主要功能在于執行對網絡硬件設備的直接操控。

NDIS中間層驅動并不直接對應于OSI模型中的某個特定層次，它通過向上提供微端口驅動接口，表現為一個或多個可以綁定的虛擬適配器，向下則提供傳輸驅動接口。通過中間層驅動的應用，顯著提高了NDIS框架的靈活性和擴展性，也為MANET路由協議的嵌入提供了選擇。

1.3 整體構思與設計

1.3.1 基于Windows構建MANET路由協議一般方法

設計實現適用于Windows系統的MANET路由協議，關鍵在于明確MANET路由協議棧在Windows系統中的層次定位與嵌入方式。

以DSR協議為例，首先考慮它在OSI參考模型中的對應層次。如若將DSR封裝于二層數據鏈路層，以鏈路層MAC地址作為節點標志進行選路，可以無差別地支持IPv4、IPv6等多種三層網絡協議；若以三層網絡協議地址作為節點標志，DSR協議棧則工作在網絡層，可應用于不同廠商的硬件設備之上，或者不同的二層MAC協議之上。

其次考慮DSR協議棧在NDIS框架中的位置。OSI參考模型二、三層分別部分對應于NDIS框架中的微端口驅動和傳輸驅動(圖2)。微端口驅動通常由網絡硬件廠商提供，不可直接操控，而Windows系統的非開源性也使得傳輸驅動無法修改，完全重寫則費時費力且無法集中精力于MANET路由協議本身。在此情況下，中間層驅動提供了如下有效途徑：

a）它以虛擬適配器的形式與上層傳輸驅動進行綁定，具備真實適配器的全部運行狀態；

b)可以高效截取傳遞于上、下層驅動之間的數據報文，并通過自定義代碼擴展報文處理；

c)便于實施對于目的地址為非本節點的數據報文的選路與轉發，特別是在基于網絡層協議地址進行選路的情況下，無須再將此類報文上傳至網絡層去解析判斷。

以上優勢是NDIS框架中諸如TDI driver、filter driver等其他過濾報文式驅動所無法比擬的，因此，無論將DSR定位于OSI模型中的二層還是三層，使用NDIS中間層驅動實現DSR協議棧都是理想的選擇。

1.3.2 以中間層驅動形式構建DSR協議

根據以上分析，本文采用基于NDIS中間層驅動的形式構建DSR協議棧。協議棧與NDIS上、下層關系整體框架示意圖如圖3所示。

主要設計思路包括：

a)采用IPv4/IPv6協議地址作為MANET節點標志，以期為配置多網卡的節點可能存在的不同底層通信模式提供支持；

b）操作系統采用Windows XP、NDIS版本5.1；

c）保留Windows系統既有TCP/IP協議棧，新建適合DSR的路由緩存及其他基本數據結構，確保嵌入的DSR協議棧與原有TCP/IP協議棧工作流程之間的有效協作與交互；

d）系統底層使用支持802.11b/g協議的無線網卡，直接使用廠商提供的既有網卡驅動。

2 部分關鍵問題與解決方案

2.1 幀的大小及IP分組序列號

2.1.1 幀的大小

以中間層驅動形式構建的DSR協議棧在從上層傳輸驅動TCP/IP接收到802.3或Ethernet Ⅱ格式的數據幀后(在兩者都支持的情況下默認使用Ethernet Ⅱ格式，Ethernet Ⅱ報文的最大有效載荷為1 500 Byte^[7])，將即刻提取報文目的IP進行DSR選路，一旦獲得去往該目的IP的源路由信息，則在下發數據幀之前在原有數據幀中插入DSR選項頭，這將使得數據幀的有效載荷可能大于1 500 Byte，從而影響數據幀的正常發送。

但是實驗結果表明，雖然幀格式轉換機制完全封裝于無線網卡微端口驅動內，不可進行跟蹤與觀測，添加DSR選項頭后的滿載荷數據幀(有效載荷大于1 500 Byte)卻依然可以在下傳之后被正確地轉換為802.11格式發送(802.11報文的最大有效載荷為2 312 Byte^[7])。這為DSR協議棧在NDIS中間層驅動層的設計和正常工作提供了有效保障。

2.1.2 IP分組序列號

參照文獻[4]創建DSR報文， DSR選項頭必須緊跟IP報頭之后，因此對于DSR協議棧自行生成的DSR管理控制報文，則涉及到如何填寫報文IP頭序列號字段的問題。

由于上層驅動下發的IP報文的序列號由系統隨機自動生成并自動增長，中間層驅動產生的DSR控制報文很難插入其中。但是考慮到DSR控制報文僅在中間層驅動產生與處理，無須被上傳至上層傳輸驅動TCP/IP，因此可以忽略此類報文IP頭中序列號的作用，在構建此類報文時，采用統一制訂的IP序列號。

2.2 ARP請求報文的截取處理

傳統網絡依賴ARP交互進行局域網內部通信，而DSR網絡環境中的尋路機制并不關心節點所在網絡及掩碼，僅要求各節點標志惟一。由于位處NDIS中間層驅動的DSR協議對于上層驅動TCP/IP完全透明，TCP/IP將依舊按照傳統方式通過ARP獲取下一跳MAC地址，必須對ARP請求(ARP request)進行攔截處理，以便上層協議驅動TCP/IP適應于DSR網絡環境。

對于ARP請求報文的截取處理詳細流程如圖4所示。

處理ARP請求的核心思路如下：

a）訪問DSR路由緩存，如果存在到達ARP所請求的目的IP地址的DSR源路由，則使用指定源MAC地址構建ARP回復(ARP reply)并上傳至TCP/IP，TCP/IP將認為該目的地可達，隨即建立ARP表項并開始傳輸數據。

b)若無對應的DSR源路由，則根據DSR路由請求記錄決定是否啟動對該目的IP的DSR路由發現。

c)在執行DSR路由發現流程中，若收到對應的DSR路由請求回復，則如a)所描述，構建ARP回復，通知上層協議驅動目的地可達。

2.3 DSR路由請求的重發定時

理想情況下，本地節點每觸發一次DSR路由請求，即須對應啟動一個定時器。若在定時器指定時間內未能收到DSR路由請求回復，則根據路由重發策略決定是否再次發送DSR路由請求^[4]。

實際設計中，在默認配置下，NDIS上層協議驅動下發數據報文時使用報文數組(packet array)作為參數，位于中間層驅動層次的DSR協議棧將通過NDIS接口函數MiniportSendPackets()^[8](關于本節后續系統函數均請參閱文獻[8])接收該報文數組并加以處理。因此，執行DSR路由功能的每個線程通常需要連續處理多個報文。若在某一數據報文觸發DSR路由請求之后，通過掛起當前線程的方式設置DSR路由請求重發定時，勢必嚴重影響DSR線程對于報文數組中后續報文的連續處理。于是，另設線程執行定時功能成為必然選擇。然而，由于系統內核線程創建函數PsCreateSystemThread()僅在調用方的中斷請求級別(interrupt request level，IRQL^[9])設置為PASSIVE_LEVEL時方能使用，工作于IRQL級別DISPATCH_LEVEL上的MiniportSendPackets()將無法根據需要即時創建新線程用于執行對于當次DSR路由請求的重發定時。

根據NDIS中間層驅動接口函數IRQL運行級別的規定，只能在驅動加載與卸載過程中創建或撤銷線程，因此本文設計采用通過獨立線程周期性的訪問DSR路由請求記錄表的方式處理DSR路由請求重發。準備工作包括：定義實現獨立線程的啟動函數thread_start()、撤銷函數thread_stop()以及線程執行函數thread_process()。另外，由于獨立線程的生命周期與DSR協議棧一致且只能自我終結，還須定義并初始化KEVENT類型的事件KillEvent以通知獨立線程終結執行。

具體操作實現為：在DSR協議棧的驅動入口函數driverentry() 中調用thread_start()創建獨立線程用于執行DSR路由請求過期檢查與重發判定(DSR基本數據結構必須先于獨立線程創建)；在DSR協議棧卸載函數中調用thread_stop()，以便觸發KillEvent事件，通知獨立線程任務已結束，需要終止線程執行，隨后清理線程引用 (卸載函數通過NdisMRegisterUnloadHandler()注冊) 。

執行DSR路由請求過期檢測與重法判定的算法如下：

thread_process()

{

while (TRUE)

{

調用KeWaitForSingleObject()等待事件KillEvent；

//設置等待時間為1 s；

if (等待超時)

訪問DSR路由請求記錄表；

if(存在DSR路由請求記錄)

檢查每個DSR路由請求等待時間是否超時；

if(超時請求次數<最大請求次數) 

再次創建并發送DSR路由請求報文；

else if (超時) 刪除DSR路由請求記錄；

else break;//收到KillEvent通知，跳出循環處理；

}

調用PsTerminateSystemThread()結束線程；

}

3 初驗環境設置與協議測試

系統初驗環境設置包括：

a)六臺配有型號DWL-G122無線網卡的便攜PC(支持802.11b/g)；

b)運行安裝有DSR協議棧驅動的Windows XP操作系統；

c)設置各節點無線網卡工作于802.11 IBSS Ad hoc模式^[10]，使用統一的BSS ID；

d)構建初始拓撲(圖5)，其中僅ABCD依次鄰接可達且DE一跳可達。

測試結果顯示，各節點間均可正常通信，其中AE路徑如圖5所示。拓撲位移之后，DSR路由隨之變化，A新建到達E的DSR源路由為ABCDE(圖6)。使用有效載荷為1 472 Byte的ICMP Echo報文持續進行AE連通測試，結果顯示，拓撲變化過程中AE平均時延小于400 ms。

4 結束語

本文研究分析了通過Windows NDIS架構實現MANET路由協議的一般方法，提出了以NDIS中間層驅動形式構建動態源路由協議DSR的設計方案，有效處理了DSR協議嵌入Windows系統時有關銜接與協作方面的關鍵問題。實驗結果顯示該設計切實可行。

后續工作將主要集中于以下幾個方面：a)對本文設計的DSR協議棧進行詳盡的性能測試；b)基于NDIS 6.0系列的WinCE嵌入式平臺，構建更加全面的DSR協議Windows系統實測環境；c)通過真實環境下的應用測試對DSR協議進行持續優化，提高系統性能；d)擴展DSR協議安全特性等。

參考文獻：

［1］陳曦， 張霞， 梁興強. 移動自組網測試平臺設計研究[J].計算機工程與應用，2004，40(12):136-138，152.

［2］梁興強，張霞，陳曦，等.基于NDIS的自組織網測試床設計與實現[J].計算機應用研究，2004，21(7):122-124.

［3］周經宇， 周玲玲， 徐國治.移動Ad hoc網絡AODV路由協議在Windows CE.NET上的實現[J].計算機工程與應用，2006，42(5):131-134.

［4］JOHNSON D，HU Y，MALTZ D.The dynamic source routing protocol for mobile Ad hoc networks for IPv4[EB/OL].(2007-02)[2008-05-10].http://www.ietf.org/rfc/rfc4728.txt.

［5］Microsoft.NDIS drivers(NDIS 5.1)[EB/OL].[2008-05-10].http://msdn.microsoft.com/en-us/library/ms797339.aspx.

［6］Microsoft.Windows 2000 and later network architecture and the OSI model(NDIS 5.1)[EB/OL].[2008-06-12].http://msdn.microsoft.com/en-us/library/ms797342.aspx.

［7］KUROSE J F，ROSS K W.Computer networking a top-down approach featuring the Internet[M].3rd ed. Beijing:Higher Education Press，2005.

［8］Microsoft.Windows driver development kit[EB/OL].[2008-06-12].http://www.microsoft.com/whdc/devtools/wdk/default.mspx.

［9］Microsoft.Scheduling，thread context，and IRQL[EB/OL].[2008-06-13].http://msdn.microsoft.com/en-us/library/ms810029.aspx.

［10］IEEE 802.11 Working Group.Wireless LAN medium access control (MAC) and physical layer (PHY) specifications(revision of IEEE std 802.11—1999)[EB/OL].(2007-08-03)[2008-06-15].http://standards.ieee.org/getieee802/download/802.11-2007.pdf.