Ns2中單播動(dòng)態(tài)路由的實(shí)現(xiàn)與擴(kuò)展

1、ns2中單播動(dòng)態(tài)路由機(jī)制的剖析與擴(kuò)展摘要：ns2是在網(wǎng)絡(luò)研究和設(shè)計(jì)廣泛使用的一個(gè)網(wǎng)絡(luò)仿真器，但ns2對(duì)路由協(xié)議的實(shí)現(xiàn)過(guò)程非常復(fù)雜，所以嚴(yán)重阻礙了網(wǎng)絡(luò)研究者對(duì)原有路由模塊的擴(kuò)展和仿真。本文詳細(xì)剖析了ns2中單播動(dòng)態(tài)路由的功能和實(shí)現(xiàn)過(guò)程，提出了在ns2中擴(kuò)展路由協(xié)議的方法，最后通一個(gè)路由擴(kuò)展實(shí)例說(shuō)明了擴(kuò)展方法的可行性。關(guān)鍵詞網(wǎng)絡(luò)仿真器ns2路由rtproto引言ns2是免費(fèi)并且可以完全開(kāi)放源代碼的網(wǎng)絡(luò)仿真軟件，使用者可以根據(jù)自己的需求編寫(xiě)代碼，擴(kuò)展ns2的功能，因此備受研究人員的關(guān)注。在ns2中一共有四種路由仿真策略，它們分別是：static（靜態(tài)路由），session（會(huì)話路由），dynamic

2、（動(dòng)態(tài)路由）和manual（手動(dòng)路由）。static和session策略使用的是dijkstras all-pairs spf 路由算法。動(dòng)態(tài)路由策略使用distributed bellman-ford 路由算法。手動(dòng)路由不是一個(gè)用來(lái)計(jì)算路由的協(xié)議，只是ns2提供給用戶一個(gè)可以手工配置路由表的接口。該文將重點(diǎn)討論動(dòng)態(tài)路由策略的實(shí)現(xiàn)和擴(kuò)展方法，并通過(guò)實(shí)例說(shuō)明擴(kuò)展方法的應(yīng)用價(jià)值。因?yàn)閚s2的英文文檔都是專(zhuān)業(yè)技術(shù)人員編寫(xiě)的，理解起來(lái)有一定的難度，并且其中存在不少bug，而且目前公開(kāi)發(fā)表的中文文獻(xiàn)中幾乎沒(méi)有關(guān)于擴(kuò)展路由協(xié)議的報(bào)告。因此該文希望對(duì)路由的研究起到推動(dòng)作用，減少研究開(kāi)發(fā)人員的成本開(kāi)銷(xiāo)。2.

3、ns2單播動(dòng)態(tài)路由的結(jié)構(gòu)因?yàn)殪o態(tài)和手動(dòng)路由實(shí)現(xiàn)簡(jiǎn)單，所以該文重點(diǎn)介紹ns2中動(dòng)態(tài)路由協(xié)議的實(shí)現(xiàn)過(guò)程和擴(kuò)展方法。ns2單播動(dòng)態(tài)路由的組成部分如圖1所示。圖1 ns2單播動(dòng)態(tài)路由結(jié)構(gòu)圖從圖1中可以看出，實(shí)現(xiàn)動(dòng)態(tài)路由協(xié)議的類(lèi)一共有六個(gè)：（）routelogic類(lèi)是仿真器實(shí)例所維護(hù)的。其功能是：管理仿真拓樸中所有節(jié)點(diǎn)和鏈路信息；計(jì)算靜態(tài)路由策略下的路由；查詢(xún)?nèi)致酚尚畔ⅰ＃?） rtobject類(lèi)只應(yīng)用于動(dòng)態(tài)路由仿真中。其功能是：在運(yùn)行動(dòng)態(tài)路由策略的仿真拓?fù)渲?，每一個(gè)節(jié)點(diǎn)都有一個(gè)rtobject型的實(shí)例變量，它在節(jié)點(diǎn)中的作用是管理節(jié)點(diǎn)中的不同的動(dòng)態(tài)路由協(xié)議代理模塊。rtobject實(shí)例變量跟蹤正在節(jié)點(diǎn)

4、中運(yùn)行的每一個(gè)動(dòng)態(tài)路由協(xié)議，并利用節(jié)點(diǎn)中動(dòng)態(tài)路由協(xié)議代理產(chǎn)生的路由信息來(lái)計(jì)算并確定到達(dá)每一個(gè)目的節(jié)點(diǎn)的路由。當(dāng)節(jié)點(diǎn)中的路由表發(fā)生改變或是網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時(shí)，rtobject會(huì)通知節(jié)點(diǎn)中的動(dòng)態(tài)路由協(xié)議代理模塊重新計(jì)算路由。（3） rtpeer類(lèi)是一個(gè)被動(dòng)態(tài)路由協(xié)議代理模塊使用的容器類(lèi)，該類(lèi)存放所有相鄰節(jié)點(diǎn)地址，對(duì)等路由代理模塊的端口號(hào)和路由信息。（4）agent/rtpro類(lèi)是所有路由協(xié)議代理類(lèi)的基類(lèi)。每一個(gè)路由協(xié)議代理類(lèi)都要定義 procedureinit-all過(guò)程完成初始化操作。如果用戶要想實(shí)現(xiàn)自己的路由協(xié)議，最主要的工作是首先應(yīng)當(dāng)繼承并修改agent/rtproto類(lèi)。（5）routin

5、g module路由模塊：此模塊是連接節(jié)點(diǎn)接分類(lèi)器和路由功能模塊之間橋梁，在一般的路由仿真中主要利用的是基本路由模塊rtmodule/base。3. 單播動(dòng)態(tài)路由的實(shí)現(xiàn)為便于討論，首先說(shuō)明下面幾個(gè)數(shù)組變量的意義。rtpref_數(shù)組變量中存放著每一個(gè)路由協(xié)議代理的preference_（優(yōu)先級(jí)）值，表明該路由協(xié)議代理計(jì)算出的路由優(yōu)先級(jí)。metric_數(shù)組變量中存放著到所有目的節(jié)點(diǎn)的cost_度量值，在ns2的動(dòng)態(tài)路由策略中這個(gè)度量的默認(rèn)值是1（跳數(shù)）。rtvia_數(shù)組變量存放著到達(dá)目的節(jié)點(diǎn)所用路由協(xié)議代理的名稱(chēng)。nexthop_數(shù)組變量存放著到下一跳信息。上述四個(gè)數(shù)組變量都以目的節(jié)點(diǎn)作為數(shù)組索引

6、。在仿真器命令$ns rtproto dv開(kāi)始執(zhí)行的時(shí)候，ns2會(huì)新建立一個(gè)routelogic型的變量并調(diào)用routelogic類(lèi)中的register過(guò)程，該過(guò)程將會(huì)接收兩個(gè)參數(shù)：proto和args，proto參數(shù)是仿真中要實(shí)現(xiàn)的路由協(xié)議，該文傳來(lái)的參數(shù)是dv，因此仿真將會(huì)執(zhí)行動(dòng)態(tài)路由協(xié)議策略。第二個(gè)參數(shù)args，它是要實(shí)現(xiàn)路由協(xié)議的節(jié)點(diǎn)列表，如果args為空，ns2將會(huì)對(duì)仿真拓?fù)渲兴泄?jié)點(diǎn)使用dv路由協(xié)議。register過(guò)程主要執(zhí)行下面代碼：agent/rtproto/$proto pre-init-all $args即調(diào)用dv路由協(xié)議中的初始化過(guò)程pre-init-all。在實(shí)際的n

7、s2 tcl仿真源碼中，dv代理pre-init-all過(guò)程是空的。至此，仿真器實(shí)例過(guò)程$ns rtproto dv的執(zhí)行結(jié)束。但是動(dòng)態(tài)路由策略的初始化過(guò)程并沒(méi)有結(jié)束，因?yàn)槁酚纱砟K和rtobject對(duì)象還沒(méi)有安裝到節(jié)點(diǎn)當(dāng)中去。在仿真器類(lèi)執(zhí)行run過(guò)程的時(shí)候，會(huì)有下面的代碼：$self get-routelogic configure即調(diào)用routelogic類(lèi)中的configure方法。在該方法中，主要執(zhí)行存放在該類(lèi)中所有路由策略的初始化過(guò)程，在該文執(zhí)行的是agent/rtproto/dv 的init-all過(guò)程，該過(guò)程的操作步驟如下： （1）首先在仿真拓?fù)渲械拿恳粋€(gè)節(jié)點(diǎn)上創(chuàng)建一個(gè)rtob

8、ject實(shí)例對(duì)象，并對(duì)其進(jìn)行初始化。初始化的結(jié)果是：節(jié)點(diǎn)node和rtobject對(duì)象實(shí)例可相互訪問(wèn)；對(duì)其成員變量rtpref_、metric_、rtvia_賦初值；調(diào)用其add-proto方法在rtobject實(shí)例中添加direct路由協(xié)議代理；調(diào)用direct協(xié)議代理的compute-routes方法來(lái)建立節(jié)點(diǎn)與其相鄰節(jié)點(diǎn)的路由。rtobject初始化之后，ns會(huì)為所有節(jié)點(diǎn)添加dv路由協(xié)議代理模塊。（2），調(diào)用dv路由協(xié)議add-peer方法。其功能是在每一個(gè)節(jié)點(diǎn)的dv代理中添加其相鄰節(jié)點(diǎn)對(duì)等dv代理的rtpeer引用，并把這個(gè)引用存放在peers_數(shù)組中。（3）路由協(xié)議中的每個(gè)節(jié)點(diǎn)定期地

9、向其相鄰節(jié)點(diǎn)發(fā)送該節(jié)點(diǎn)路由信息的操作在dv路由代理初始化的時(shí)候被設(shè)置。dv路由代理的初始化過(guò)程會(huì)調(diào)用send-updates告知ns事件調(diào)度器定期地向相鄰節(jié)點(diǎn)rtpeer對(duì)等實(shí)例發(fā)送該節(jié)點(diǎn)所保存的路由信息。（4）當(dāng)相鄰節(jié)點(diǎn)的對(duì)等dv代理接收到路由更新信息時(shí)，首先取出dv和ip頭部；接下來(lái)調(diào)用otcl解釋器對(duì)象的evalf方法，該方法的作用是在tcl層面上執(zhí)行dv代理解釋對(duì)象的recv-update方法：在peers_數(shù)組中找到發(fā)送路由更新消息代理的rtpeer引用，接著用傳來(lái)的跳數(shù)信息更新原有的跳數(shù)信息。接著執(zhí)行下面兩句重要代碼：$self compute-routes$rtobject_ c

10、ompute-routes第一條代碼是dv路由代理調(diào)用自己的compute-routes方法計(jì)算到達(dá)各個(gè)節(jié)點(diǎn)的路由，即確定下一跳nexthop_數(shù)組中的值，該方法僅是確定dv代理模塊的路由。第二條代碼是調(diào)用rtobject_類(lèi)中compute-routes方法在其路由代理數(shù)組rtprotos_($proto)所確定的路由中挑選出最優(yōu)的路由，并最終通過(guò)rtmodule模塊把節(jié)點(diǎn)計(jì)算出的路由安裝到節(jié)點(diǎn)的地址分類(lèi)器中。至此，agent/rtproto/dv 的inin-all過(guò)程才全部執(zhí)行完成。初始化完成后，通過(guò)ns的事件調(diào)度機(jī)制周期性地調(diào)用路由消息發(fā)送和路由接收方法，在仿真拓?fù)渲械拿恳粋€(gè)節(jié)點(diǎn)中建立

11、到達(dá)所有節(jié)點(diǎn)的路由表，整個(gè)路由的建立過(guò)程結(jié)束。4. 功能擴(kuò)展及實(shí)現(xiàn)綜上所述，擴(kuò)展動(dòng)態(tài)路由模塊的步驟如下：（1）僅擴(kuò)展靜態(tài)路由協(xié)議算法只需要對(duì)routelogic模塊中的計(jì)算路由過(guò)程進(jìn)行修改，不需要修改tcl接口。（2）對(duì)動(dòng)態(tài)路協(xié)議算法的擴(kuò)展,可分為下述兩種情況：l 路由選擇部分的擴(kuò)展：該擴(kuò)展的實(shí)現(xiàn)需要繼承rtobject類(lèi)并進(jìn)行修改。因?yàn)閞tobject對(duì)象是ns系統(tǒng)在每一個(gè)實(shí)現(xiàn)動(dòng)態(tài)路由協(xié)議節(jié)點(diǎn)中創(chuàng)建并管理的，所以用戶不必再編寫(xiě)tcl接口。l 添加具體的協(xié)議實(shí)現(xiàn)：首先從agent/rtproto類(lèi)派生出要實(shí)現(xiàn)協(xié)議的子類(lèi)；根據(jù)具體實(shí)現(xiàn)，重載初始化和路由計(jì)算這兩個(gè)重要的方法；最后在仿真器類(lèi)中的rt

12、proto過(guò)程中添加新協(xié)議的用戶接口。如果要擴(kuò)展的協(xié)議需要增加新的對(duì)等協(xié)議代理，用戶應(yīng)當(dāng)在tcl層面編寫(xiě)新的對(duì)等協(xié)議模塊。(3)復(fù)雜的路由協(xié)議需要對(duì)路由選擇部分進(jìn)行擴(kuò)展并添加具體的協(xié)議實(shí)現(xiàn)方法。在這種情況下，按照先更改rtobject類(lèi),然后添加協(xié)議代理的原則進(jìn)行擴(kuò)展。如必要，還可在仿真器類(lèi)中為用戶提供合適的tcl接口。根據(jù)上文所提供的方法，現(xiàn)對(duì)ns原有的動(dòng)態(tài)路由協(xié)議做一個(gè)簡(jiǎn)單的擴(kuò)展。在ns原有的動(dòng)態(tài)路由策略下，按照節(jié)點(diǎn)中保存的跳數(shù)信息進(jìn)行路由計(jì)算。一般情況下,一條路由的時(shí)延和跳數(shù)并沒(méi)有直接關(guān)系，這也就意味著擁最有短跳數(shù)的路由并不一定有最短時(shí)延。這里擴(kuò)展目的就是要實(shí)現(xiàn)擁有最短時(shí)延的路由。在理論

13、上時(shí)延和跳數(shù)同屬于加性度量，所以整個(gè)路由的時(shí)延是由組成該路由的各個(gè)鏈路上的時(shí)延之和。如果在一對(duì)源和目的節(jié)點(diǎn)中有多條路由存在的話，那么系統(tǒng)所選出的路由將具有最短時(shí)延。因?yàn)橹簧婕暗綄?duì)路由度量的更改，根據(jù)上文提出的擴(kuò)展方法知：只需修改路由代理就可以完成擴(kuò)展功能。動(dòng)態(tài)路由策略在計(jì)算之前由每個(gè)節(jié)點(diǎn)的direct代理來(lái)計(jì)算并保存其到達(dá)相鄰節(jié)點(diǎn)的路徑和度量信息，并將默認(rèn)跳數(shù)信息修改成鏈路時(shí)延信息。實(shí)現(xiàn)的主要方法如下：agent/rtproto/direct instproc settimedelay(dest,time)set metric_($dest) $time其主要功能是在仿真開(kāi)始前配置每個(gè)節(jié)點(diǎn)di

14、rect代理中的度量值。dest就是目的節(jié)點(diǎn)，因?yàn)闀r(shí)延time是鏈路的時(shí)延值，所以該方法應(yīng)在用戶配置鏈路之后進(jìn)行使用，這樣每個(gè)節(jié)點(diǎn)在交換度量信息前，節(jié)點(diǎn)中的direct代理存放已是時(shí)延度量信息。這樣經(jīng)過(guò)dv路由代理和rtobject模塊所計(jì)算出來(lái)的路由就是具有最短時(shí)延的路由。仿真結(jié)果如下圖所示，在仿真開(kāi)始之前利用上述的用戶接口把各條鏈路上的開(kāi)銷(xiāo)值設(shè)置成為時(shí)延，本文設(shè)置路由0-1-3-4-6的總時(shí)延為最小，雖然其跳數(shù)為4跳，但由節(jié)點(diǎn)發(fā)往節(jié)點(diǎn)6的數(shù)據(jù)包選擇這條時(shí)延最小的路由， 5、結(jié)論本文對(duì)ns2網(wǎng)絡(luò)仿真器中的路由模塊的組成部分進(jìn)行了簡(jiǎn)要介紹,并以動(dòng)態(tài)路由算法為例，就ns2如何實(shí)現(xiàn)distributed bellman-ford算法功能進(jìn)了深入的剖析并做了仿真。在剖析路由模塊工作原理的基礎(chǔ)之上，本文提出了在ns中擴(kuò)展路由模塊的具體的方法。由于ns對(duì)路由的實(shí)現(xiàn)的原理很復(fù)雜，所以本文的分析和提出的方法對(duì)于想