《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 通信與網(wǎng)絡(luò) > 設(shè)計應(yīng)用 > Ad hoc路由協(xié)議實現(xiàn)研究
Ad hoc路由協(xié)議實現(xiàn)研究
摘要: 目前的路由協(xié)議僅是在仿真條件下研究,,很少有真正的測試床實現(xiàn),。但仿真不能完全反映路由協(xié)議在實際工作中的真實狀態(tài),,無法獲得實際系統(tǒng)的精確行為。實現(xiàn)一個移動自組織網(wǎng)路由協(xié)議需要許多系統(tǒng)組件,。許多路由協(xié)議必須事件支持,,因此要增加對相應(yīng)事件的支持。這里探究在實際操作系統(tǒng)中實現(xiàn)Ad hoc路由協(xié)議所遇到的基本問題,,并提出一種新的體系結(jié)構(gòu)解決方案,。
Abstract:
Key words :

1 引言

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

2  Ad hoc路由協(xié)議實現(xiàn)的基本問題

2.1 一般路由體系結(jié)構(gòu)

當(dāng)前的路由體系結(jié)構(gòu)將按功能分為分組轉(zhuǎn)發(fā)和分組路由兩部分,。其中,分組轉(zhuǎn)發(fā)功能是在操作系統(tǒng)內(nèi)核部分實現(xiàn),;而路由功能在用戶空間作為守護程序?qū)崿F(xiàn),。一般路由體系結(jié)構(gòu)為:內(nèi)核收到分組,查詢路由表并通過相應(yīng)的網(wǎng)絡(luò)接口將分組轉(zhuǎn)發(fā)到下一跳鄰居,。內(nèi)核路由表實體由路由守護進程根據(jù)其路由算法生成,。轉(zhuǎn)發(fā)和路由功能分開的思想與基本 Unix系統(tǒng)機制一策略分開的思想一致。該機制高效,,輕量,,因為策略的設(shè)計可在很大的時間跨度上改變而不會影響機制。分組轉(zhuǎn)發(fā)可高效轉(zhuǎn)發(fā)每個分組,,所以該機制應(yīng)位于內(nèi)核,。這樣分組可盡快通過該節(jié)點。該分離原理使得現(xiàn)代操作系統(tǒng)的路由功能更高效靈活,。同時在不改變系統(tǒng)內(nèi)核的情況下,,也可不斷改進路由功能,。

2.2 按需路由實現(xiàn)的基本問題

Ad hoc網(wǎng)絡(luò)的路由協(xié)議可分為主動路由和反應(yīng)式路由兩類,。主動路由協(xié)議(表驅(qū)動)通過周期性的交換控制信息維護一個到所有可能目的地的路由,而反應(yīng)式路由 (按需)僅當(dāng)有需要時才發(fā)起路由請求,。主動路南協(xié)議如(DSDV)在路由體系中能像有線網(wǎng)絡(luò)中的路由協(xié)議(如RIP,,OSPFBGP)那樣很容易地在用戶空間中實現(xiàn),。而反應(yīng)式路由協(xié)議.如AODV和DSR則帶來以下挑戰(zhàn):

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

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

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

(4)新的路由模型有些路由協(xié)議采用非傳統(tǒng)的路由模式(如源路由,、基于流的轉(zhuǎn)發(fā)路由等)。這些路由模式與當(dāng)前的IP路由體系結(jié)構(gòu)相背離,,并且對系統(tǒng)設(shè)計提出挑戰(zhàn),。在源路由方式下,一個分組要經(jīng)過的全部路徑由源節(jié)點決定,,并且將這些路由信息編碼在分組頭部,。而傳統(tǒng)IP路由轉(zhuǎn)發(fā)功能是逐跳的,并且由本地路由表驅(qū)動,。在基于流的轉(zhuǎn)發(fā)方式下每個分組都有一個流ID,,網(wǎng)絡(luò)中的每個節(jié)點都有一個流表,轉(zhuǎn)發(fā)的過程是根據(jù)流ID查找流表,,而路由的過程是在每個節(jié)點建立流表,。

大多數(shù)通用操作系統(tǒng)不能靈活支持新的路由模型,因此這些路由協(xié)議的實現(xiàn)既要修改內(nèi)核,;IP棧又要使用內(nèi)核擴展機制避開IP棧,。

(5)跨層交互無線信道為跨層交互作用提供許多機會。在某些路由算法中,,路由協(xié)議的設(shè)計要使用物理層和鏈路層參數(shù),,如信號強度、鏈路狀態(tài)等,。概念上應(yīng)放棄跨層交互,,因為雖然跨層設(shè)計會提供最優(yōu)化,但不加選擇的訪問所有底層參數(shù)會嚴(yán)重?fù)p害網(wǎng)絡(luò)體系結(jié)構(gòu),。許多路由協(xié)議使用其他層路由協(xié)議信息以提高性能,,例如每個相鄰節(jié)點的鏈路質(zhì)量信息是某些路由算法所需的,。盡管可得到這些信息,但跨越不同的硬件和操作系統(tǒng)時沒有統(tǒng)一的標(biāo)準(zhǔn),,需通過標(biāo)準(zhǔn)方式以便獲得低層信息,,這對開發(fā)路由協(xié)議非常重要。

3 新的體系結(jié)構(gòu)

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

4 Linux下的一種實現(xiàn)

4.1 Linux系統(tǒng)網(wǎng)絡(luò)協(xié)議棧體系結(jié)構(gòu)

Linux網(wǎng)絡(luò)系統(tǒng)有硬件,數(shù)據(jù)鏈路層,、IP層,、INET Socket層、BSD Socket層和應(yīng)用層5部分,。其中在Linux內(nèi)核中分組包括前4部分,。圖1為Linux系統(tǒng)基于TCP/IP的網(wǎng)絡(luò)體系結(jié)構(gòu)。

 

4.2 Linux系統(tǒng)網(wǎng)絡(luò)堆棧的IP層

Linux路由系統(tǒng)中主要保存3種路由相關(guān)的數(shù)據(jù):(1)在物理上與本機相連接的主機地址信息表,,即鄰居節(jié)點表,。鄰居節(jié)點表用neigh_table{} 數(shù)據(jù)結(jié)構(gòu)表示,以neighbour{}數(shù)據(jù)結(jié)構(gòu)為節(jié)點,;(2)在網(wǎng)絡(luò)訪問中判斷一個網(wǎng)絡(luò)地址的數(shù)據(jù)表,,是轉(zhuǎn)發(fā)信息庫FIB,用來保存路由規(guī)則,,用 fib_table{)數(shù)據(jù)結(jié)構(gòu)鏈表來表示,;(3)最近使用過的路由緩存表,,稱為路由緩存表,用rtable{}數(shù)據(jù)結(jié)構(gòu)鏈表表示,。

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

4.3 Netfilter/iptables網(wǎng)絡(luò)分組的處理

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

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

綜上所述,,由于Linux的Netfilter/iptables功能強大,,并且與內(nèi)核結(jié)合完美,因此受到廣泛關(guān)注并應(yīng)用于Ad hoc路由協(xié)議的實現(xiàn),。

4.4 基本問題的解決

Linux體系結(jié)構(gòu)下,,在處理無路由分組和更新路由緩存時具有較好的解決途徑。

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

當(dāng)路由發(fā)現(xiàn)完成成功后,使用新發(fā)現(xiàn)的路由,,內(nèi)核中的這些分組被恰當(dāng)?shù)芈酚沙鋈?,從而較好處理了沒有路由分組。為每個路南表條目在內(nèi)核外面維護一個時間戳來更新路由緩存,。

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

5 結(jié)束語

由于Linux操作系統(tǒng),,通過分析當(dāng)前操作系統(tǒng)的網(wǎng)絡(luò)模塊,列出實現(xiàn)Ad hoc路由協(xié)議所面臨的問題并提出了一種可行的解決方案,。

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載,。