Ad hoc網(wǎng)絡(luò)的路由協(xié)議實現(xiàn)研究

　　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)

　　當前的路由體系結(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)式路由 (按需)僅當有需要時才發(fā)起路由請求。主動路南協(xié)議如(DSDV)在路由體系中能像有線網(wǎng)絡(luò)中的路由協(xié)議(如RIP，OSPF，BGP)那樣很容易地在用戶空間中實現(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)開銷。路由緩存中的每個條目都有一個定時器，當相應(yīng)的路由被使用時，需重新設(shè)置該定時器，而當達到定時時間，要被刪除該條目。如果內(nèi)核路由表中的條目在事先定義的時間內(nèi)未被使用(如未被查找過)，該信息必須能夠被用戶空間的路由守護進程獲得。而這在當前的路由協(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ā)路由等)。這些路由模式與當前的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ù)會嚴重損害網(wǎng)絡(luò)體系結(jié)構(gòu)。許多路由協(xié)議使用其他層路由協(xié)議信息以提高性能，例如每個相鄰節(jié)點的鏈路質(zhì)量信息是某些路由算法所需的。盡管可得到這些信息，但跨越不同的硬件和操作系統(tǒng)時沒有統(tǒng)一的標準，需通過標準方式以便獲得低層信息，這對開發(fā)路由協(xié)議非常重要。

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

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