ＮＳ２中最快路由協(xié)議的設(shè)計(jì)與實(shí)現(xiàn)

摘要：利用網(wǎng)絡(luò)仿真器NS2對(duì)路由協(xié)議進(jìn)行仿真是一種既有效又經(jīng)濟(jì)的辦法。本文介紹了NS2中單播動(dòng)態(tài)路由協(xié)議的原理，并實(shí)現(xiàn)了任意兩點(diǎn)間最快路由協(xié)議，仿真實(shí)驗(yàn)表明該路由協(xié)議是有效的。

關(guān)鍵詞：NS2；路由模塊；最快路由協(xié)議

中圖分類號(hào)：TP393文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2008)17-21407-02

1 引言

NS2是面向?qū)ο蟮摹㈦x散事件驅(qū)動(dòng)的網(wǎng)絡(luò)環(huán)境模擬器，它可以為低成本的網(wǎng)絡(luò)實(shí)驗(yàn)提供一個(gè)良好的模擬環(huán)境。NS2為已有協(xié)議的驗(yàn)證提供了很多便利，同時(shí)還提供了用于開(kāi)發(fā)新協(xié)議所需的豐富的構(gòu)件平臺(tái)，研究者可以在一個(gè)受控的環(huán)境下研究大規(guī)模協(xié)議的交互，能夠更方便的比較不同方法的結(jié)果[1]。NS2中實(shí)現(xiàn)路由協(xié)議的的模塊比較繁瑣而且非常復(fù)雜，這使得從事網(wǎng)絡(luò)研究的人員對(duì)路由協(xié)議的擴(kuò)展變得非常困難。因此本文在詳細(xì)介紹單播動(dòng)態(tài)路由模塊的工作原理的基礎(chǔ)上，對(duì)靜態(tài)策略進(jìn)行擴(kuò)展 （將原來(lái)的兩點(diǎn)間距離最短修改成兩點(diǎn)間最快），仿真實(shí)驗(yàn)表明修改后的任意兩點(diǎn)間最快路由協(xié)議是有效的。

2 NS2路由模塊的工作原理

通常，NS2中每個(gè)路由的實(shí)現(xiàn)包含3個(gè)功能塊：

1)路由代理（Routing agent），用于和鄰居交換路由信息；

2)路由邏輯（Routing logic），用路由代理收集來(lái)的信息（或者是靜態(tài)路由情況下全局的拓?fù)鋽?shù)據(jù)庫(kù)）執(zhí)行實(shí)際的路由計(jì)算；

3)節(jié)點(diǎn)中的分類器，它們用來(lái)計(jì)算路由表，從而執(zhí)行包的傳遞。

我們要編寫一個(gè)新的路由協(xié)議時(shí)，上述的3個(gè)模塊不必全部實(shí)現(xiàn)。例如，實(shí)現(xiàn)鏈路狀態(tài)路由協(xié)議時(shí)，我們只需要實(shí)現(xiàn)以鏈路狀態(tài)方式交換信息的路由代理，以及一個(gè)計(jì)算拓?fù)鋽?shù)據(jù)庫(kù)的路由邏輯，然后就可使用象單播路由協(xié)議一樣的分類器。

3 NS2中單播動(dòng)態(tài)路由模塊的實(shí)現(xiàn)

目前，NS2中有四種路由策略：靜態(tài)（static）、會(huì)話（session）、動(dòng)態(tài)（DV）和手動(dòng)（manual）。靜態(tài)和會(huì)話路由采用的是Dijkstra的all-pairs SPF（兩節(jié)點(diǎn)間最短距離）算法，動(dòng)態(tài)路由策略目前用的是分布式Bellman-Ford（單源最短路徑）算法。

NS2中單播動(dòng)態(tài)路由體系主要涉及四個(gè)類：Routelogic類、rtObject類、rtPeer類以及所有路由協(xié)議都使用的基類Agent/rtProto類[2]。

1)Routelogic類

Routelogic類的成員函數(shù)register{ }用于注冊(cè)指定路由策略（如上述的static）。它建立一個(gè)變量rtprotos_，并將所注冊(cè)的路由策略名及其作用的節(jié)點(diǎn)序列當(dāng)作主題插入rtprotos_。Routelogic類的另一個(gè)成員函數(shù)configure{ }則讀取變量rtprotos_，對(duì)隊(duì)列中的每個(gè)元素調(diào)用相應(yīng)的路由協(xié)議初始化方法進(jìn)行路由初始化。

2)rtObject類

rtObject類類應(yīng)用于動(dòng)態(tài)路由協(xié)議DV，當(dāng)設(shè)置了DV路由策略后， rtObject類的init-all{ }函數(shù)會(huì)為它的每個(gè)作用節(jié)點(diǎn)創(chuàng)建一個(gè)rtObject對(duì)象，然后分別讓每個(gè)節(jié)點(diǎn)的rtObject對(duì)象調(diào)用自身的成員函數(shù)computer-router{ }進(jìn)行獨(dú)立的路由計(jì)算。

3)rtPeer類

rtPeer類是路由代理應(yīng)用的一個(gè)容器類， 該類維護(hù)著實(shí)例變量addr_（相鄰節(jié)點(diǎn)地址）和實(shí)例變量隊(duì)列metric_（所有目的節(jié)點(diǎn)cost_度量值）和rtpref_（存放路由代理優(yōu)先級(jí)）。

4)Agent/rtProto類

Agent/rtProto類是所有路由協(xié)議的基類。每個(gè)路由協(xié)議都要定義函數(shù)init-all{ }以初始化完整的協(xié)議。

4 最快路由協(xié)議的實(shí)現(xiàn)

NS2中靜態(tài)和會(huì)話路由策略采用的是Dijkstra的all-pairs SPF（兩節(jié)點(diǎn)間最短距離）算法進(jìn)行路由表的計(jì)算，算法利用構(gòu)建整個(gè)網(wǎng)絡(luò)圖的鄰接矩陣，計(jì)算出所有節(jié)點(diǎn)對(duì)之間的最短路徑。在這里是代價(jià)指cost最小的路徑，當(dāng)鏈路代價(jià)1為時(shí)，也是最少跳數(shù)路徑，并在路由表中登記兩節(jié)點(diǎn)間路徑下一跳節(jié)點(diǎn)的信息。現(xiàn)在我們的工作就是將其改寫成最快路由（時(shí)延最短）協(xié)議，也就是說(shuō)如在一對(duì)源和目的節(jié)點(diǎn)中存在多條路由的話，那么將選出具有最短時(shí)延的路由。對(duì)靜態(tài)路由協(xié)議的擴(kuò)展只需對(duì)Routelogic類進(jìn)行擴(kuò)展，無(wú)需修改tcl接口[3]。下面是我們對(duì)Routelogic類進(jìn)行擴(kuò)展的部分代碼。

1)改寫route.h

route.h文件是NS2中C++類Routelogic定義的頭文件。它包含網(wǎng)絡(luò)拓?fù)鋱D鄰接矩陣!路由表的結(jié)構(gòu)定義，以及類中支持路由計(jì)算的各成員變量和成員函數(shù)的說(shuō)明。對(duì)route.h文件的改寫包括以下幾部分：

①鄰接矩陣結(jié)構(gòu)增加對(duì)時(shí)延的支持，具體的結(jié)構(gòu)定義如下

struct adj_ entry {

double cost;

double delay;#存放鏈路的時(shí)延

void* entry;}

②增加私有成員變量adj_dl_和route_dl_

adj_ entry* adj_dl_#包含時(shí)延信息的鄰接矩陣

route_entry * route_dl_#包含時(shí)延信息的路由表

③增加私有函數(shù)insert_dl( )

void insert_dl(int src， int dst， double cost，double delay)，

#給鄰接矩陣插入信息，除原有信息外還包括新增加時(shí)延信息。

④增加公有成員函數(shù)lookup_flat_dl( )

int lookup_flat_dl(char* asrc， char* adst， intresult);

用于查以時(shí)延為度量的路由表中asrc至adst的下一跳。

2)改寫route.cc

route.cc程序是實(shí)現(xiàn)路由計(jì)算的核心代碼。本文最快路由算法就是通過(guò)修改該程序完成的。對(duì)route.cc的修改包括對(duì)新增OTcI命令支持以及新增成員函數(shù)的實(shí)現(xiàn)兩部分：

①新增OTcl命令的支持

這部分是完成int RouteLogic::command(int argc， const char*const*argv)函數(shù)的編寫。主要完成以下三項(xiàng)工作：

a：定義插入命令(inset_dl)：將時(shí)延信息輸入路由計(jì)算所需的鄰接矩陣；

b：定義查表命令( lookup_dl )：為了不破壞原有的單播路由表，本文建立了新的路由表，與之相對(duì)應(yīng)，需要新的查表命令：

c：定義路由計(jì)算命令(compute-dl )：最快路由對(duì)象要調(diào)用新的路由計(jì)算程序進(jìn)行路由計(jì)算。

②新增成員函數(shù)的實(shí)現(xiàn)

a：insert_dl( )

該函數(shù)的作用是將時(shí)延信息存入鄰接矩陣。

b：compute_routes_dl( )

該函數(shù)是本文最快路由計(jì)算的重點(diǎn)，同原有的comput-routes函數(shù)類似，函數(shù)的工作流程是：

步驟1：分配鄰接矩陣空間，登記網(wǎng)絡(luò)拓?fù)鋱D；

步驟2：分配路由表空間，存儲(chǔ)源、目的節(jié)點(diǎn)間的下一跳；

步驟3：填寫包含時(shí)延的鄰接矩陣信息；

步驟4：用Dijkstra all-pair SPF算法（算法以時(shí)延最短作為判優(yōu)標(biāo)準(zhǔn)）計(jì)算任意節(jié)點(diǎn)對(duì)之間最優(yōu)路徑，并在路由表中登記下一跳信息。

c：lookup_flat_dl( )

該函數(shù)的作用是從路由表中查找任意源、目的節(jié)點(diǎn)間的下一跳節(jié)點(diǎn)，并返回該節(jié)點(diǎn)。函數(shù)定義同原有的lookup- flat函數(shù)相似，區(qū)別僅在于所查路由表為Route_dl而不是route_。

5 仿真

為了證明上述的改動(dòng)是有效的，在ns2中編寫tcl腳本進(jìn)行仿真，在仿真開(kāi)始前，將網(wǎng)絡(luò)拓?fù)渲懈麈溌范攘吭O(shè)置為時(shí)延，設(shè)置0-1-2-3的總時(shí)延最小。從圖中我們可以看到雖然從0-4-3的跳數(shù)為3，但由節(jié)點(diǎn)0發(fā)往節(jié)點(diǎn)3的數(shù)據(jù)包仍然選擇0-1-2-3的路由（時(shí)延最短），盡管其跳數(shù)為4。

參考文獻(xiàn)：

[1] 于斌，孫斌，等.NS2與網(wǎng)絡(luò)模擬[M].北京:人民郵電出版社，2007.

[2] http://www.isi.edu/nsnam/ns/ns-contributed.html[EB/OL].

[3] 夏利，張鵬，等.NS2中單播動(dòng)態(tài)路由機(jī)制的剖析與擴(kuò)展[J].微計(jì)算機(jī)應(yīng)用，2006(5):275-277.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文