1 引言

目前的路由協議僅是在仿真條件下研究，很少有真正的測試床實現。但仿真不能完全反映路由協議在實際工作中的真實狀態，無法獲得實際系統的精確行為。實現一個移動自組織網路由協議需要許多系統組件。許多路由協議必須事件支持，因此要增加對相應事件的支持。這里探究在實際操作系統中實現Ad hoc路由協議所遇到的基本問題，并提出一種新的體系結構解決方案。

2  Ad hoc路由協議實現的基本問題

2．1 一般路由體系結構

當前的路由體系結構將按功能分為分組轉發和分組路由兩部分。其中，分組轉發功能是在操作系統內核部分實現；而路由功能在用戶空間作為守護程序實現。一般路由體系結構為：內核收到分組，查詢路由表并通過相應的網絡接口將分組轉發到下一跳鄰居。內核路由表實體由路由守護進程根據其路由算法生成。轉發和路由功能分開的思想與基本 Unix系統機制一策略分開的思想一致。該機制高效，輕量，因為策略的設計可在很大的時間跨度上改變而不會影響機制。分組轉發可高效轉發每個分組，所以該機制應位于內核。這樣分組可盡快通過該節點。該分離原理使得現代操作系統的路由功能更高效靈活。同時在不改變系統內核的情況下，也可不斷改進路由功能。

2．2 按需路由實現的基本問題

Ad hoc網絡的路由協議可分為主動路由和反應式路由兩類。主動路由協議(表驅動)通過周期性的交換控制信息維護一個到所有可能目的地的路由，而反應式路由 (按需)僅當有需要時才發起路由請求。主動路南協議如(DSDV)在路由體系中能像有線網絡中的路由協議(如RIP，OSPF，BGP)那樣很容易地在用戶空間中實現。而反應式路由協議．如AODV和DSR則帶來以下挑戰：

(1)沒有路由分組的處理通常經轉發模塊的分組都會匹配內核路由表，如果人口沒有匹配的目的地址，內核就會立即丟棄該分組。而在按需路由協議中這是不可取的，因為并不是所有的路由都是事先存在的，有些是在有路由需求的時才進行路由發現得到的，所以正確方法是通知路由守護進程路由請求，將分組緩存直到路由發現過程結束且更新路由表。但操作系統不支持這種新的分組轉發行為的機制，而且內核不對這些任務(如排隊)所有未處理的分組提供足夠的支持。

(2)更新路由緩存按需路由協議通常是在用戶空間中緩存最近使用的路南，以減少路由發現開銷。路由緩存中的每個條目都有一個定時器，當相應的路由被使用時，需重新設置該定時器，而當達到定時時間，要被刪除該條目。如果內核路由表中的條目在事先定義的時間內未被使用(如未被查找過)，該信息必須能夠被用戶空間的路由守護進程獲得。而這在當前的路由協議體系下很難實現，因為內核中沒有可用的路由使用記錄。

(3)轉發與路由混合有些Ad hoc路南協議轉發和路由功能沒有明顯界線，如DSR。該協議要求每個分組(不只是路由控制分組)必需攜帶一個特殊的DSR頭以供用戶空間中的DSR守護進程處理。該路由和轉發功能結合的方式與現代操作系統內部的路由體系結構不相適應，且很難高效應用。將整個路由協議放入內核，或把核心路由表分離出來而將轉發功能放入用戶空間。而有些情況，違反該分離原則，獲得一些優化以減少路由開銷。

(4)新的路由模型有些路由協議采用非傳統的路由模式(如源路由、基于流的轉發路由等)。這些路由模式與當前的IP路由體系結構相背離，并且對系統設計提出挑戰。在源路由方式下，一個分組要經過的全部路徑由源節點決定，并且將這些路由信息編碼在分組頭部。而傳統IP路由轉發功能是逐跳的，并且由本地路由表驅動。在基于流的轉發方式下每個分組都有一個流ID，網絡中的每個節點都有一個流表，轉發的過程是根據流ID查找流表，而路由的過程是在每個節點建立流表。

大多數通用操作系統不能靈活支持新的路由模型，因此這些路由協議的實現既要修改內核；IP棧又要使用內核擴展機制避開IP棧。

(5)跨層交互無線信道為跨層交互作用提供許多機會。在某些路由算法中，路由協議的設計要使用物理層和鏈路層參數，如信號強度、鏈路狀態等。概念上應放棄跨層交互，因為雖然跨層設計會提供最優化，但不加選擇的訪問所有底層參數會嚴重損害網絡體系結構。許多路由協議使用其他層路由協議信息以提高性能，例如每個相鄰節點的鏈路質量信息是某些路由算法所需的。盡管可得到這些信息，但跨越不同的硬件和操作系統時沒有統一的標準，需通過標準方式以便獲得低層信息，這對開發路由協議非常重要。

3 新的體系結構

首先提出一種通用方法以在通用操作系統中支持按需路由協議，并提出下面機制以增強當前分組轉發功能。在內核路由表的每個條目增加一個標志表明該條目是否為按需路由條目，從而當路由不可達時，內核將分組排隊緩存而不是直接丟棄。一個路由若具有空的下一條或接口則將緩存以等待路由發現。同時路由表無需包括所可能目的地，使用基于子網標志的路由和默認路由可到達同樣的目的。將一種稱為按需路由組件 (ODRC)的新組件加入內核分組轉發功能以實現按需路由功能。當內核收到一個分組并發現沒有向應的路由時，它首先通知用戶空間的路由守護進程對該分組的目的地發出路由請求，然后將該分組緩存等待守護進程返回路由發現狀態。如果該過程成功完成，則填充相應路由表條目，緩存的分組重新插入轉發隊列。為解決路由緩存問題，必須在每個路由條目上加入時間戳，記錄該條目最后被使用時間。時間戳用于刪除一個未使用的過期路由。

4 Linux下的一種實現

4．1 Linux系統網絡協議棧體系結構

Linux網絡系統有硬件，數據鏈路層、IP層、INET Socket層、BSD Socket層和應用層5部分。其中在Linux內核中分組包括前4部分。圖1為Linux系統基于TCP／IP的網絡體系結構。

4．2 Linux系統網絡堆棧的IP層

Linux路由系統中主要保存3種路由相關的數據：(1)在物理上與本機相連接的主機地址信息表，即鄰居節點表。鄰居節點表用neigh_table{} 數據結構表示，以neighbour{}數據結構為節點；(2)在網絡訪問中判斷一個網絡地址的數據表，是轉發信息庫FIB，用來保存路由規則，用 fib_table{)數據結構鏈表來表示；(3)最近使用過的路由緩存表，稱為路由緩存表，用rtable{}數據結構鏈表表示。

在類Unix操作系統中，路由功能一般包括2部分。一部分駐留在操作系統內核中，用以基于表驅動的進程，根據路由表信息，設定正確的地址，將數據分組發往對應的網絡接口，這部分稱為“分組轉發功能模塊”；另一部分實現路由協議的邏輯計算，通過與其他主機交換信息計算出到其他節點的正確路由，實現真正的尋找路由和維護路由功能，這部分稱為“分組尋址功能模塊”。分組轉發路由模塊在內核中基于一個內核路由表來工作，每次發送數據分組都要查詢內核路由表，取得對應的下一跳鄰居節點的地址和對應的網絡接口。內核路由表一般由分組尋路功能模塊操作維護。在查找內核路由表時根據路由表項轉發。如果找不到匹配的路由表項，則按缺省路由發送，一般將網關作為缺省路由的下一跳節點。如果缺省路由不存在則操作系統將直接丟棄數據分組。分組尋路模塊功能負責尋路，它和其他節點交換信息，采用一定的路由算法計算和維護內核路南表。分組尋路功能模塊既可在內核實現，也可在用戶空間實現，Linux系統自帶的分組尋路模塊在內核中。分組轉發功能和分組尋路功能分開后，可在分組轉發功能模塊不變的情況下，通過修改分組尋路功能模塊用其他路由協議代替現有的路由協議。

4．3 Netfilter／iptables網絡分組的處理

Netfilter是嵌入在內核IP協議棧的一系列調用入口，設置在數據報處理的路徑上。Netfilter為每種網絡協議定義一套鉤子函數(IPv4定義5個子函數)，這些鉤子函數在數據分組流過協議棧的幾個關鍵點時被調用。在這幾個關鍵點上，協議把網絡數據分組、鉤子函數及鉤子函數標號作為參數調用 Netfilter框架。內核的任何模塊可對每種協議的一個或多個鉤子進行注冊。當某個數據報被傳送至Netfilter框架時，內核能夠檢測是否有模塊對該協議和鉤子進行注冊。若已注冊則調用該模塊注冊時使用的回調函數，這些模塊就有機會檢查、修改或丟棄該分組及指示Netfilter將該數據分組傳入用戶空間的隊列。排隊的數據分組被傳遞至用戶空間，在用戶空間異步進行處理。

一個用戶空間進程能夠檢查數據分組、修改數據分組，甚至還可重新將該數據分組通過離開內核的同一個鉤子函數重新注入內核中。

綜上所述，由于Linux的Netfilter／iptables功能強大，并且與內核結合完美，因此受到廣泛關注并應用于Ad hoc路由協議的實現。

4．4 基本問題的解決

Linux體系結構下，在處理無路由分組和更新路由緩存時具有較好的解決途徑。

通過使用一個本地隧道設備Universal TUN／TAP作為這些地址‘接口’過濾無路由分組。再將這些分組緩存在一張由目的地IP地址為索引的Hash隊列。

當路由發現完成成功后，使用新發現的路由，內核中的這些分組被恰當地路由出去，從而較好處理了沒有路由分組。為每個路南表條目在內核外面維護一個時間戳來更新路由緩存。

設計一個route_check的簡單核心模塊維護該表，每個路由出去的分組都將經該模塊，還可查看分組頭并更新對應的時間戳。

5 結束語

由于Linux操作系統，通過分析當前操作系統的網絡模塊，列出實現Ad hoc路由協議所面臨的問題并提出了一種可行的解決方案。