Ad hoc路由協(xié)議實(shí)現(xiàn)研究-基礎(chǔ)電子

精品文檔-下載后可編輯Adhoc路由協(xié)議實(shí)現(xiàn)研究-基礎(chǔ)電子1引言

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

2Adhoc路由協(xié)議實(shí)現(xiàn)的基本問(wèn)題

2．1一般路由體系結(jié)構(gòu)

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

2．2按需路由實(shí)現(xiàn)的基本問(wèn)題

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

(1)沒(méi)有路由分組的處理通常經(jīng)轉(zhuǎn)發(fā)模塊的分組都會(huì)匹配內(nèi)核路由表，如果人口沒(méi)有匹配的目的地址，內(nèi)核就會(huì)立即丟棄該分組。而在按需路由協(xié)議中這是不可取的，因?yàn)椴⒉皇撬械穆酚啥际鞘孪却嬖诘模行┦窃谟新酚尚枨蟮臅r(shí)才進(jìn)行路由發(fā)現(xiàn)得到的，所以正確方法是通知路由守護(hù)進(jìn)程路由請(qǐng)求，將分組緩存直到路由發(fā)現(xiàn)過(guò)程結(jié)束且更新路由表。但操作系統(tǒng)不支持這種新的分組轉(zhuǎn)發(fā)行為的機(jī)制，而且內(nèi)核不對(duì)這些任務(wù)(如排隊(duì))所有未處理的分組提供足夠的支持。

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

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

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

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

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

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

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

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

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

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

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

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

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

4．3Netfilter／iptables網(wǎng)絡(luò)分組的處理

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

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

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

4．4基本問(wèn)題的解決

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

通過(guò)使用一個(gè)本地隧道設(shè)備UniversalTUN／TAP作為這些地址‘接口’過(guò)濾無(wú)路由分組。再將這些分組緩存在一張由目的地IP地址為索引的Hash隊(duì)列。

當(dāng)路由發(fā)現(xiàn)完成成功后，使用新發(fā)現(xiàn)的路由，內(nèi)核中的這