網(wǎng)絡(luò)協(xié)議棧設(shè)計與分析.doc

1、網(wǎng)絡(luò)協(xié)議棧分析與設(shè)計大作業(yè)最佳鏈路狀態(tài)路由協(xié)議(OLSR)分析Optimized Link State Routing Protocol肖明旺 201192191 網(wǎng)絡(luò)1102萬宇騰 201192280 網(wǎng)絡(luò)1102丁英才 201193068 網(wǎng)絡(luò)1101劉偉麟 201192308 軟件11152013-12-22目錄組內(nèi)分工4第一章引言4第二章代碼介紹52.1文件介紹52.2全局變量52.3 配置變量6第三章OLSR部分消息包數(shù)據(jù)結(jié)構(gòu)73.1 OLSR首部73.2 HELLO消息包83.3 TC消息包9第四章鄰居發(fā)現(xiàn)94.1 節(jié)點信息的存儲94.2 關(guān)于節(jié)點的具體操作分析114.3 鄰居表的

2、操作144.3.1 鄰居表的初始化144.3.2 刪除節(jié)點154.3.3 鄰居節(jié)點的查找與插入174.3.4 鄰居表的更新184.3.5 其他操作18第五章MPR選擇195.1 MPR節(jié)點的添加和清除195.2 MPR算法205.2.1 olsr_find_2_hop_neighbors_with_1_link函數(shù)215.2.2 olse_chosen_mpr函數(shù)225.2.3 olsr_find_maximum_covered函數(shù)225.2.4 olsr_check_mpr_changes函數(shù)235.2.5 優(yōu)化MPR集合24第六章拓撲控制消息洪泛246.1 TC消息初始化與刪除246.2

3、TC消息處理26第七章路由表的計算267.1 主要數(shù)據(jù)結(jié)構(gòu)分析277.1.1 rt_metric和rt_nexthop277.1.2 rt_entry277.1.3 路由類型287.2 路由表計算297.2.1 路由表的創(chuàng)建與刪除297.2.2 最優(yōu)路徑31第八章總結(jié)32組內(nèi)分工項目參與者數(shù)據(jù)結(jié)構(gòu)部分代碼分析萬宇騰鄰居發(fā)現(xiàn)部分代碼分析萬宇騰、劉偉麟MPR選擇部分代碼分析劉偉麟TC消息洪泛部分代碼分析肖明旺路由計算部分代碼分析丁英才論文撰寫肖明旺、萬宇騰、丁英才、劉偉麟論文匯總肖明旺第一章 引言最佳鏈路狀態(tài)路由協(xié)議( Optimized Link Status Routing Protocol,

4、 OLSR )，是專門為無線移動Ad Hoc網(wǎng)絡(luò)提出來的一種標準化的先驗式的優(yōu)化鏈路狀態(tài)路由協(xié)議。該協(xié)議的核心是使用了多點中繼站(MPRs)，MPRs是被選擇的節(jié)點，具有轉(zhuǎn)發(fā)網(wǎng)絡(luò)控制消息的能力。根據(jù)協(xié)議，每個節(jié)點之間周期性的交換控制信息，節(jié)點根據(jù)協(xié)議計算自己的網(wǎng)絡(luò)拓撲。OLSR向所有節(jié)點提供一個最短路徑，該技術(shù)可以有效減少網(wǎng)絡(luò)中數(shù)據(jù)傳輸?shù)男畔⒘俊Ｃ恳粋€被鄰居們選擇的節(jié)點在控制信息里周期性的廣播這一信息。因此，可以說是由被選擇的節(jié)點構(gòu)成了主要的網(wǎng)絡(luò)。相比經(jīng)典的鏈路狀態(tài)算法，OLSR更適合移動無線局域網(wǎng)。該協(xié)議比較適合大型密集的網(wǎng)絡(luò)。OLSR有以下優(yōu)點：1利用MPRs來重傳控制消息可以減少網(wǎng)絡(luò)間消

5、息的發(fā)送數(shù)量。2只需要部分鏈路狀態(tài)洪泛就可以獲取最佳路徑。3網(wǎng)絡(luò)越大則OLSR可優(yōu)化的范圍就越大也就能得到更好的性能在OLSR協(xié)議中，狀態(tài)路由協(xié)議的網(wǎng)絡(luò)信息狀態(tài)由被推選的節(jié)點(MPR)掌控。所以，優(yōu)化的一條途徑是減少網(wǎng)絡(luò)中的控制信息。只有被選擇的MPR節(jié)點才能被用做路由節(jié)點，非MPR節(jié)點不參與路由計算。MPR可以減少網(wǎng)絡(luò)中冗余消息的傳送。每個節(jié)點傳送消息給一跳鄰居，但是鄰居并不能再將此消息傳送給其他節(jié)點。OSLR協(xié)議逐跳尋找路徑，每個節(jié)點利用本地信息向鄰居節(jié)點發(fā)送路由包來獲取路徑。由于該協(xié)議在設(shè)計之初就考慮到協(xié)議的分布式工作，所以該協(xié)議不依賴于任何的中心，也不需要穩(wěn)定的的控制信息的傳播。每一個

6、節(jié)點都周期性的發(fā)送信息，這樣也保證了一個在可以接受范圍內(nèi)的丟包率。OLSR協(xié)議在設(shè)計之初就考慮了協(xié)議的獨立性，因此OLSR協(xié)議獨立工作于一些協(xié)議。它對IP的包格式?jīng)]有做任何改變，因此，任何IP協(xié)議棧都能在協(xié)議中正常使用。第二章 代碼介紹2.1文件介紹OLSR路由協(xié)議共有123個源文件。我們將對部分源文件進行功能型介紹。表格 1 OLSR協(xié)議部分源文件介紹文件描述Olsrd-0.6.0/link_set.c確定鄰居表的信息Olsrd-0.6.0/lq_packet.h對olsr,hello,TC數(shù)據(jù)包以及其他一些數(shù)據(jù)結(jié)構(gòu)的定義Olsrd-0.6.0/mpr.c關(guān)于MPR的一些操作Olsrd-0.

7、6.0/mpr_selector_set.h定義了結(jié)構(gòu)體mpr_selector表示MPR選擇源節(jié)點的集合Olsrd-0.6.0/neighbor_table.h對鄰居信息數(shù)據(jù)結(jié)構(gòu)的定義Olsrd-0.6.0/neighbor_table.c對一跳鄰居和二跳鄰居的處理Olsrd-0.6.0/olsr.c實現(xiàn)一些全局函數(shù)，比如網(wǎng)絡(luò)拓撲結(jié)構(gòu)的計算、路由表的計算與更新和錯誤處理函數(shù)等等Olsrd-0.6.0/olsr_cfg.h定義大部分常量，比如DEF_WILLINGNESS等Olsrd-0.6.0/olsr_spf.c實現(xiàn)spf樹的構(gòu)造從而實現(xiàn)迪杰斯特拉算法計算路由表Olsrd-0.6.0/ro

8、uting_table.c路由表的處理Olsrd-0.6.0/TC_set.cTC消息的洪泛2.2全局變量在olsr路由協(xié)議中使用的全局變量有許多，我們在這里只介紹部分重要的全局變量。表格 2 OLSR協(xié)議部分全局變量介紹全局變量數(shù)據(jù)類型描述olsrportnit16_tOLSR消息發(fā)送接收的端口號rt_protonit8_t路由表計算的所遵循的協(xié)議willingnessnit8_tWILL_ALWAYS的鄰居節(jié)點集合use_hysteresis bool判斷消息是否遲滯min_tc_vtimefloatTC消息vtime的最小取值max_tc_vtimefloatTC消息vtime的最大取值

9、max_jitterfloat消息傳播的最大抖動changes_topologybool判斷拓撲信息是否變化changes_neighborhoodbool判斷鄰居信息是否變化2.3 配置表格 3 OLSR路由協(xié)議配置名稱描述默認值DEF_IP_VERSIONDEF_USE_HYSTDEF_LQ_LEVELDEF_OLSRPORTDEF_MIN_TC_VTIMEDEF_GW_TYPEDEF_DOWNLINK_SPEEDMAX_LQ_LEVELMIN_LQ_LEVELDEF_RTPROTO缺省ip協(xié)議域缺省消息遲滯缺省鏈路質(zhì)量等級缺省olsr端口號TC消息vtime最小取值缺省網(wǎng)關(guān)類型缺省的鏈路

10、下載速度缺省鏈路質(zhì)量最高等級缺省鏈路質(zhì)量最高等級缺省的路由協(xié)議AF_INETFalse26980.0GW_UOLINk_IPV461024kb/s200MAX_TTLMAXJITTER定義ttl最大值Olsr消息傳播最大抖動0.165msHELLO_INTERVAL/4COOKIE_ID_MAX系統(tǒng)cookie數(shù)量最大值25MAXMESSAGESIZE廣播數(shù)據(jù)包大小的最大值1500kbOLSR_LINK_JITTEROLSR_LINK_HELLO_JITTEROLSR_LINK_SYM_JITTEROLSR_LINK_LOSS_JITTERolsr消息抖動時間HELLO消息抖動時間系統(tǒng)抖動時間

11、數(shù)據(jù)包丟失抖動時間5s0s0s0s第三章 OLSR部分消息包數(shù)據(jù)結(jié)構(gòu)OLSR使用統(tǒng)一的數(shù)據(jù)包格式，使用UDP通信，數(shù)據(jù)包嵌入到UDP數(shù)據(jù)報在網(wǎng)絡(luò)上傳輸。每個數(shù)據(jù)包封裝一個或多個消息，郵件分享通用報頭格式，使節(jié)點能夠正確接收和重傳一個未知類型的消息。如果數(shù)據(jù)包不包含任何信息（數(shù)據(jù)包的長度小于或等于該數(shù)據(jù)包報頭的大?。瑪?shù)據(jù)包就會默默的丟棄。每一個消息都會分配一個唯一的標識號，用來確保消息不重傳。OLSR數(shù)據(jù)包一般包含以下幾部分:消息類型,VTIME郵件大小,發(fā)端地址,生存時間,跳數(shù),消息序列號和消息。其中VTIME是表示接收后很長時間節(jié)點如何，確保數(shù)據(jù)包中的消息有效；生存時間包含最大跳數(shù)，如果被

12、重發(fā)，則減1；消息序列號被用來確保給定的消息被節(jié)點轉(zhuǎn)發(fā)的次數(shù)不超過一次。3.1 OLSR首部-Olsr-lq_packet.h-Olsr-lq_packet.holsr_common是OLSR協(xié)議基本數(shù)據(jù)包。其中包含以下幾部分:type，消息類型；vtime, 表示接收后很長時間節(jié)點如何，確保數(shù)據(jù)包中的消息有效；size，消息大?。籵rig，發(fā)端地址；ttl，跳數(shù)，消息在傳遞過程中最大跳數(shù)，每轉(zhuǎn)發(fā)一次，ttl減1；hops，此消息在傳遞過程中經(jīng)歷的跳數(shù)；seqno，消息的序列號，這是唯一不變的，以確保消息不回被重發(fā)。表格 4 OLSR協(xié)議數(shù)據(jù)包Packet LengthPacket Seque

13、nce NumberMessage TypeVtimeMessage SizeOriginator AddressTime To LiveHop CountMessage Sequence NumberMESSAGE3.2 HELLO消息包-Olsr-lq_packet.h-Olsr-lq_packet.hHELLO用于建立一個節(jié)點的鄰居表，其中包括鄰居節(jié)點的地址以及本節(jié)點到鄰居節(jié)點的延時和開銷，OLSR采用周期性的廣播HELLO分組來偵聽鄰居節(jié)點的狀態(tài)和無線鏈路的對稱性。節(jié)點之間無線鏈路的狀態(tài)包括：非對稱鏈路，對稱鏈路，連接MPR的鏈路。但OLSR協(xié)議只關(guān)心對稱鏈路，同時HELLO分組只在一

14、跳的范圍內(nèi)廣播，不能被轉(zhuǎn)發(fā)；與此相反，TC分組必須被廣播到全網(wǎng)，在TC分組中包含了將發(fā)送TC分組的節(jié)點選為MPR的鄰居節(jié)點的信息，節(jié)點根據(jù)收到的TC分組來計算出網(wǎng)絡(luò)拓撲圖。結(jié)構(gòu)體lq_hello_message即Hello消息數(shù)據(jù)包介紹：htime，HELLO消息發(fā)射間隔；will，指定節(jié)點的意愿進行，有意愿的WILL_NEVER的節(jié)點被選為MPR的任意節(jié)點；neigh，消息傳遞的下一個節(jié)點。lq_hello_neighbor是HELLO消息鄰居節(jié)點集：neigh_type，鄰居類型（SYM_NEIGH，NOT_NEIGH）；link_type，連接類型（UNSPEC_LINK）；addr，地

15、址；linkquality，鏈路的質(zhì)量。3.3 TC消息包-Olsr-lq_packet.h-Olsr-lq_packet.hTC分組數(shù)據(jù)包必須通過MPR節(jié)點傳遞消息被廣播到全網(wǎng)中，用以維護網(wǎng)絡(luò)的拓撲信息、確保鏈路時刻連通狀態(tài)和更新路由表集。lq_TC_message 是封裝后的拓撲數(shù)據(jù)包格式。from：接受包的上一個節(jié)點地址；ansn：節(jié)點接受到消息時拓撲集合會被更新。-Olsr-packet.h-Olsr-packet.hTC_message是TC消息數(shù)據(jù)包格式。第四章 鄰居發(fā)現(xiàn)鄰居發(fā)現(xiàn)是基于節(jié)點的鄰居信息庫，通過HELLO消息的傳播實現(xiàn)。鄰居信息庫包含關(guān)于鄰居、2跳鄰居、MPRs和MPR

16、的信息。4.1 節(jié)點信息的存儲每個節(jié)點都存儲自身的信息在結(jié)構(gòu)體link_entry中。-Olsr-link_set.h-Olsr-link_set.h00059-00060：local_iface_addr存儲該節(jié)點接口ip地址，neighbor_iface_addr存儲鄰居節(jié)點ip地址。00067：neighbor以鏈鏈表形存儲鄰居節(jié)點信息。鄰居節(jié)點具體信息如下：-Olsr-neighbor_table.h-Olsr-neighbor_table.hneighbor_entry結(jié)構(gòu)體，同來存儲鄰居節(jié)點的信息。記錄了鄰居節(jié)點的主地址，狀態(tài)，作為MPR的willingnessz值，是否是MPR，

17、是否曾是MPR,覆蓋的兩跳鄰居節(jié)點的數(shù)量，及節(jié)點連接鏈路的數(shù)量以及指向neighbor_2_list連表的指針。其中，成員變量was_mpr用來發(fā)現(xiàn)MPR的變化。-Olsr-neighbor_table.h-Olsr-neighbor_table.h這段代碼定義了neighbor_2_list_entry結(jié)構(gòu)體，這是用來存儲鄰居節(jié)點信息，兩跳鄰居節(jié)點信息以及記錄有效時間的鏈表結(jié)構(gòu)。mid_address存儲本節(jié)點的其他接口ip地址。其中mid_entry節(jié)點鏈路信息。mid_entry包含節(jié)點主地址，上一節(jié)點和下一節(jié)點鏈路，同時還有本節(jié)點鏈路中其他端口信息存儲在aliases鏈表中。4.2 關(guān)

18、于節(jié)點的具體操作分析-Olsr-link_set.c-Olsr-link_set.c函數(shù)功能：重置所有節(jié)點信息。00095-00103：遍歷所有節(jié)點一遍，把所有信息置為初始值，并把鄰居節(jié)點也設(shè)為空值。-Olsr-link_set.c-Olsr-link_set.c函數(shù)功能：通過查找main_addr(184-185行)找到節(jié)點link_entry,通過lookup_link_status找出節(jié)點鏈路狀態(tài)。判斷其是否是對稱狀態(tài)。00197-00206：行是查找主地址并找出節(jié)點上的其他端口ip判斷該節(jié)點其他端口aliases鏈路狀態(tài)。并判斷該ip地址所在的鏈路狀態(tài)是否是對稱狀態(tài)。只返回對稱鏈路的信

19、息。-Olsr-link_set.c-Olsr-link_set.c函數(shù)功能：查找端口ip地址的最少跳數(shù)鄰居，并返回該節(jié)點信息link_entry；首先定義了三個link_entry結(jié)構(gòu)walker，good_link,backup_link；00223-00229：找出該節(jié)點的主地址，通過遍歷walker鏈表，查找出跳數(shù)最少的鄰居，這就是最新的鄰居表信息，最短的鄰居表。-Olsr-link_set.c-Olsr-link_set.c函數(shù)功能：刪除節(jié)點鏈路上所有的信息。定義拓撲邊緣節(jié)點TC_edge：通過鄰居端口地址找出TC_edge邊緣鏈路。00365-00369：刪除邊緣鏈路 spf；00

20、372-00377：刪除鄰居鏈路信息，存儲在hash表中的鏈路表刪除；00379-00394：清空一些正在計時的屬性，同時釋放link的資源空間；同時將change_neighborhood設(shè)置為true，讓其他節(jié)點更新自己的鏈路狀況，發(fā)送hello消息包及時更新鄰居表的信息。-Olsr-link_set.c-Olsr-link_set.c函數(shù)功能：更新鏈路信息狀態(tài)，通過hello_message來更新鄰居節(jié)點的信息。00694-00699：如果該節(jié)點不在鏈路中，把它加入到鏈路中去，并將計時器更新；00708-00732：通過check_link_status同過發(fā)送hello_message

21、發(fā)現(xiàn)該節(jié)點的鄰居節(jié)點鏈路狀態(tài)link_type，對不同的狀態(tài)采取不同的操作：00708-00718：如果是對稱或者非對稱的需將定時器重新設(shè)置，更新定時器；00732：更新鄰居節(jié)點的狀態(tài)信息，是對稱還是非對稱。-Olsr-link_set.c-Olsr-link_set.c函數(shù)功能：發(fā)送Hello消息，維護一個端口的鄰居信息。00780-00797：發(fā)送hello_message來維護端口信息，直到消息到達端口的所有的鄰居節(jié)點，就停止發(fā)送，則該端口的所有鄰居節(jié)點鏈路都檢查完畢。4.3 鄰居表的操作4.3.1 鄰居表的初始化-Olsr-neighbor_table.c-Olsr-neighbor_

22、table.c函數(shù)功能：初始化鄰居表。00061-00064：將每一個鄰居表neighortablei初始化為指向自身的僅有一個節(jié)點的鏈表。4.3.2 刪除節(jié)點-Olsr-neighbor_table.c-Olsr-neighbor_table.c函數(shù)功能：刪除釋放一個兩跳鄰居節(jié)點記錄。00073-00077：獲取兩跳鄰居節(jié)點記錄中nbr2_list中的鄰居節(jié)點結(jié)構(gòu)體nbr和兩跳鄰居節(jié)點結(jié)構(gòu)體nbr2；00079-00082：釋放兩跳鄰居節(jié)點結(jié)構(gòu)體nbr2的空間；00087-00088：將兩跳鄰居節(jié)點記錄中的計時器置為空；00096-00097：通過將全局變量changes_neighborh

23、ood,changes_topology置為真，通知網(wǎng)絡(luò)重新計算MPR集合和路由表。-Olsr-neighbor_table.c-Olsr-neighbor_table.c函數(shù)功能：將從兩跳鄰居節(jié)點信息中，根據(jù)給定的鄰居節(jié)點地址刪除對應(yīng)的兩跳鄰居節(jié)點。00111-00113：獲取鄰居節(jié)點的兩跳鄰居節(jié)點信息表；00115-00121：遍歷鄰居節(jié)點的兩跳鄰居及節(jié)點信息表，直到找到信息表中兩跳鄰居節(jié)點與給定的兩跳鄰居節(jié)點相同，則刪除該兩跳鄰居節(jié)點并返回1，表示成功刪除；否則返回0表示沒有刪除。-Olsr-neighbor_table.c-Olsr-neighbor_table.c函數(shù)功能：刪除鄰居節(jié)

24、點信息表（及連帶的兩跳鄰居節(jié)點信息表）00177-00182：尋找鄰居節(jié)點信息表entry。00189-00197：刪除鄰居節(jié)點信息表即連帶的兩跳鄰居節(jié)點信息表。4.3.3 鄰居節(jié)點的查找與插入-Olsr-neighbor_table.h-Olsr-neighbor_table.h函數(shù)功能：查找給定鄰居節(jié)點，能否通過該節(jié)點連接到一個給定的兩跳鄰居節(jié)點地址。00140：定義返回值entry,用來記錄找到的兩跳鄰居節(jié)點信息表結(jié)構(gòu)體。00142-00147：遍歷鄰居節(jié)點的兩跳鄰居節(jié)點信息表，如果找到信息表中存在兩跳鄰居節(jié)點的兩跳鄰居節(jié)點ip地址匹配給定的兩跳鄰居節(jié)點地址，怎返回該兩跳鄰居節(jié)點信息表結(jié)

25、構(gòu)體。否則，返回空指針。-Olsr-neighbor_table.c-Olsr-neighbor_table.c函數(shù)作用：在鄰居節(jié)點信息表中插入一條鄰居節(jié)點信息。如果已存在返回0，否則返回1。00226-00230：檢查鄰居節(jié)點信息表中是否存在要添加的鄰居節(jié)點信息；00237-00249：添加鄰居節(jié)點信息并設(shè)置內(nèi)部的地址，willingness，狀態(tài)等變量的初始化。4.3.4 鄰居表的更新-Olsr-neighbor_table.c-Olsr-neighbor_table.c函數(shù)功能：更新鄰居信息表中的狀態(tài)為參數(shù)link。00306-00322:如果將連接狀態(tài)置為SYM_LINK時，如果原來是

26、NOT_SYM則通知網(wǎng)絡(luò)重新進行MPR選舉和路由表更新并刪除通過這個鄰居節(jié)點連接到的兩跳鄰居節(jié)點；00323-00333：否則，如果之前狀態(tài)為SYM_LINK則通知網(wǎng)絡(luò)重新進行MPR選舉和路由表更新。4.3.5 其他操作針對鄰居表的操作有許多。比如，olsr_expire_nbr2_list函數(shù)的作用是回調(diào)兩跳鄰居節(jié)點信息表計時器，olsr_print_neighbor_table函數(shù)的作用是打印鄰居節(jié)點信息表，等等。這里就不詳細介紹。第五章 MPR選擇MPRs用于把節(jié)點的信息傳播出去且減少區(qū)域內(nèi)信息重傳，因此MPR是經(jīng)典洪泛算法的一種優(yōu)化。每個節(jié)點在對稱一跳鏈接里獨立的選擇它的MPRs集合。

27、與MPRs的鏈接會把在HELLO message里的鏈接類型的MPR_NEIGH替換為SYN_NEIGH。5.1 MPR節(jié)點的添加和清除-Olsr-mpr.c-Olsr-mpr.c函數(shù)作用：添加willingness為WILLALWAYS的鄰居節(jié)點到MPR集合中。00366-00378：首先將非對稱的鄰居節(jié)點或是不是WILL_ALWAYS的鄰居節(jié)點忽略，然后將剩余的節(jié)點a_neighbor添加到mpr中，并返回添加節(jié)點的數(shù)量count。-Olsr-mpr.c-Olsr-mpr.c函數(shù)作用：將被選為MPR節(jié)點的記錄清除。00245-00248：如果節(jié)點a_neighbor的ismpr值為真的話，

28、那么就將其置為假代表其不是mpr節(jié)點，同時將was_mpr置為真，代表該鄰居節(jié)點曾經(jīng)被選為mpr。00251-00255：遍歷鄰居節(jié)點a_neighbor覆蓋的兩跳鄰居節(jié)點的數(shù)量置為0。5.2 MPR算法符號 定義N(m)節(jié)點M的鄰居集合，對稱鄰居節(jié)點集合。N2(m)1 節(jié)點M的兩跳鄰居集合，除去僅能通過轉(zhuǎn)發(fā)意愿N_willingness等于WILL_NEVER的鄰居節(jié)點到達的兩跳鄰居2 除去節(jié)點自己，除去對稱鄰居節(jié)點剩下的兩跳鄰居構(gòu)成N2(m)D(m)1 m的一跳網(wǎng)路的深度被定為m的對稱鄰居的數(shù)目2 不包括N里的任何成員3 不包括自己OLSR路由協(xié)議于傳統(tǒng)的鏈路狀態(tài)路由算法最顯著的區(qū)別在于M

29、PR的引入。MPR選舉機制在全網(wǎng)有效地擴散拓撲信息的同時，大大降低了路由控制信息的洪泛規(guī)模。MPR的選舉原則是MPR為對稱鄰居節(jié)點，通過選出的MPR可以到達所有的兩跳鄰居節(jié)點，并且選出MPR個數(shù)盡可能少。一個節(jié)點的意愿可以被設(shè)置為從0-7中的整數(shù)，其中N_willingness表示意愿的值，WILL_ALWAYS表面一個節(jié)點總是選擇執(zhí)行代表其他交通節(jié)點。56432103891112112354330為節(jié)點M的兩跳鄰居節(jié)點為節(jié)點一跳鄰居節(jié)點10117121098圖 1 MPR選舉5.2.1 olsr_find_2_hop_neighbors_with_1_link函數(shù)-Olsr-mpr.c -O

30、lsr-mpr.c函數(shù)功能：查找存在一條連接的兩跳鄰居節(jié)點鏈表。定義了兩個兩跳鄰居節(jié)點鏈表（two_hop_temp,two_hop_list）,前者用來作為函數(shù)的返回值。dup_neighbor用來記錄在鄰居節(jié)點集合中已經(jīng)存在的鄰居節(jié)點，而two_hop_neighbor是用來記錄一個兩跳鄰居節(jié)點的局部變量。00096-00136:遍歷兩跳鄰居表two_hop_neighbortable；000105-00106：尋找在鄰居表中已經(jīng)存在的的鄰居地址neighbor_2_addr；00117-00122：如果存在，并且該鄰居節(jié)點與本節(jié)點不是非對稱的節(jié)點忽略；001168-00136：如果不存在

31、并且該兩跳鄰居節(jié)點只有一個鄰居節(jié)點，那么將兩跳鄰居節(jié)點添加到兩跳鄰居節(jié)點鏈表two_hop_list中。5.2.2 olse_chosen_mpr函數(shù)-Olsr-mpr.c -Olsr-mpr.c函數(shù)功能：用來處理已經(jīng)選定的MPR節(jié)點，以及對MPR的計時器的更新，函數(shù)的返回值是一條鄰居中MPR的數(shù)量。00158-00202：對second_hop_entries進行遍歷；00164-00168：將已經(jīng)存在的于鄰居節(jié)點的節(jié)點忽略；00176-00178：將兩跳鄰居節(jié)點被覆蓋的MPR的數(shù)量mpr_covered_count遞增一，同時將兩跳鄰居節(jié)點的鄰居節(jié)點賦給the_one_hop_list；0

32、0185-00187：如果兩跳節(jié)點的mpr的數(shù)量多于全局變量olsr_cnf的mpr_coverage,那么就要將count的數(shù)量增加一。函數(shù)的最后返回count值。5.2.3 olsr_find_maximum_covered函數(shù)-Olsr-mpr.c -Olsr-mpr.c函數(shù)作用：找到能夠覆蓋到最多兩跳節(jié)點的MPR。00224-00229：如果a_neighbor不是mpr ,同時覆蓋兩條節(jié)點數(shù)量值maximum小于a_neighbor鄰居節(jié)點的股該節(jié)點的數(shù)量，那么將maximum值更新，并且將a_neighbor作為候選的MPR節(jié)點。5.2.4 olsr_check_mpr_chang

33、es函數(shù)-Olsr-mpr.c -Olsr-mpr.c函數(shù)作用：通過遍歷所有的mpr節(jié)點，返回值是1時代表節(jié)點是否是mpr的狀態(tài)發(fā)生過變化，如果是0則代表沒有發(fā)生變化。00275-00281：對于鄰居節(jié)點a_neighbor如果它曾經(jīng)是mpr,但是現(xiàn)在又不是mpr,那么說明它的mpr的狀態(tài)發(fā)生變化，將retval置為1，否則返回retval默認值0。5.2.5 優(yōu)化MPR集合-Olsr-mpr.c-Olsr-mpr.c這段代碼來自olsr_optimize_mpr_set函數(shù)。00474-00509：如果覆蓋兩跳鄰居的mpr數(shù)量的值小于全局變量olsr_cnf-mpr_coverage的值，那

34、么就不需要移除，否則該mpr是冗余的，被除去。第六章 拓撲控制消息洪泛拓撲控制消息即TC消息，其數(shù)據(jù)包格式在前面已有介紹，故在此不再贅述。拓撲控制消息的洪泛有著十分重要的意義，每個被選為MPR的節(jié)點向網(wǎng)絡(luò)中所有節(jié)點廣播TC消息，節(jié)點根據(jù)“缺省的路由轉(zhuǎn)發(fā)算法”轉(zhuǎn)發(fā)TC消息。6.1 TC消息初始化與刪除-Olsr-TC_set.c-Olsr-TC_set.c函數(shù)功能：初始化TC消息。00195-00203：對TC消息的初始化，從cookie中獲取相應(yīng)的值為為TC消息集合的屬性賦值；000208：添加已配置好的TC消息到本地節(jié)點的TC消息集合。-Olsr-TC_set.c -Olsr-TC_set.

35、c函數(shù)功能：刪除TC消息。00289-00292：若宏定義LINUX_NETLINK_ROUTING條件，則刪除網(wǎng)關(guān)信息。其中網(wǎng)關(guān)的刪除操作需要對網(wǎng)關(guān)協(xié)議(IPv4或IPv6)、網(wǎng)關(guān)信息是否為空以及網(wǎng)關(guān)信息保存時間是否為空進行判斷；00296：刪除本地的路由表；00307-00311：將timers參數(shù)都設(shè)置為空，保證數(shù)據(jù)和設(shè)置的徹底刪除；00313-00314：從本地TC消息集合中刪除該TC消息，并將TC消息鏈表的阻塞解除。6.2 TC消息處理當節(jié)點接收到TC消息時，只關(guān)心其消息類型。-Olsr-TC_set.c-Olsr-TC_set.c由00820-00824可知，TC消息接收者在接受消

36、息時會判斷發(fā)送者接口信息，若發(fā)送者并非是對稱一跳鄰居，那么該包將會被丟棄。-Olsr-TC_set.c-Olsr-TC_set.c如果該消息中的msg_seq和外部變量msg_seq相等且ignored變量小于32，則代表該消息已經(jīng)處理過，應(yīng)該忽視。第七章 路由表的計算每一個節(jié)點都會維護一個路由表用于發(fā)送信息。這些路由信息來自于在網(wǎng)絡(luò)拓撲之上的本地鏈路信息。因此任一個節(jié)點的變動都會引起整個網(wǎng)絡(luò)拓撲的變化繼而影響每個節(jié)點維護的路由表的變化。每一條路由信息都包含信息目的地址、下一跳地址、總跳數(shù)、下一跳接口地址。但是在沒有路由的節(jié)點或者只知道部份信息的節(jié)點不包含在路由表內(nèi)。具體來說，當發(fā)生以下變化的

37、時候，節(jié)點的路由表信息才回發(fā)生變化：鏈路集改變、鄰居集改變、兩跳鄰居集改變、網(wǎng)絡(luò)拓撲集改變、信息庫多點接入改變。在計算X節(jié)點的路由的時候使用最小路徑算法：1 移除所有路由信息；2 添加所有對稱鄰居信息，然后把每一個鄰居信息的狀態(tài) N_status = SYM，把鄰居信息添加到路由列表中，其中 R_dest_addr = L_neighbor_iface_addr R_next_addr= L_neighbor_iface_addr R_dist = 1 R_iface_addr= L_local_iface_addr7.1 主要數(shù)據(jù)結(jié)構(gòu)分析7.1.1 rt_metric和rt_nexthop-

38、Olsr-routing_table.h-Olsr-routing_table.h00067-00070:在路由選擇的時候使用的復(fù)合矩陣，其中包括兩個路由點之間的花銷或者跳數(shù)。00073-00076:該結(jié)構(gòu)體包含下一跳的網(wǎng)關(guān)（IPv4或者IPv6）與接口索引。7.1.2 rt_entry-Olsr-routing_table.h-Olsr-routing_table.h每一個RIB節(jié)點都會有一個路由的接口，這個接口很重要，里面包含了最佳路徑的下一個網(wǎng)關(guān)信息，而且是rt_path的根，同樣也包含了一個在所有路由信息里的一個最好的路徑。rt_dst 包含了該信息的路由地址與前綴長度。rt_tree

39、_node 包含了val_tree的一些信息。如下：-Olsr-avl.h(common)-Olsr-avl.h(common)00052-00061:該結(jié)構(gòu)體里面包含了父親節(jié)點子節(jié)點左右節(jié)點等等表示一棵樹的信息，值。rt_best是所有路徑中的最佳路徑，結(jié)構(gòu)如下：-Olsr-routing_table.h-Olsr-routing_table.h7.1.3 路由類型olsr協(xié)議中有三種路由類型，INT類型的是有TC-Message發(fā)出的，而MID類型是從HNA路由器得到的MID-message。-Olsr-routing_table.h-Olsr-routing_table.h7.2 路由表

40、計算7.2.1 路由表的創(chuàng)建與刪除-Olsr-Routing_table.c-Olsr-Routing_table.c函數(shù)功能：創(chuàng)建一個可用的路由表入口，對于提供的參數(shù)IP前綴分配一個路由表入口空間，并做一些相應(yīng)的初始化并把該入口插入到avl樹里。00234-00239 申請內(nèi)存空間并把空間內(nèi)清零；00241-00245 標識該入口為新分配入口并把該入口的目的地址設(shè)置成為參數(shù)提供的入口地址；00247-00253 把入口的樹節(jié)點插入到整個路由表中并初始化樹。-Olsr-Routing_table.c -Olsr-Routing_table.c函數(shù)功能：從avl樹里面找到一個地址的路由表入口，根

41、據(jù)參數(shù)地址并配上設(shè)置里的最長前綴長度在avl樹里調(diào)用avl_find 函數(shù)從 routingtree 里面找到該地址的rt_enty。00197-00201 配置要查找的變量；00203-00205 從在routingtree里找到該地址的位置并返回該節(jié)點，如果節(jié)點不為空則調(diào)用 rt_tree2rt函數(shù)把返回節(jié)點轉(zhuǎn)化為et_entry類型，否則返回空。-Olsr-Routing_table.c-Olsr-Routing_table.c函數(shù)功能：對于每個給予的rt_path創(chuàng)建一個路由入口并且把它加入到全局的RIB樹里面。00295-00310 創(chuàng)建參數(shù)變量并檢查參數(shù)是否符合要求，如果傳入的tc

42、_entry為ROUTE_COST_BROKEN或者傳入的rtp的目的地址長度大于所設(shè)置的最大地址長度則直接返回；00315-00328 檢查傳入的rtp的節(jié)點是否在路由表中，如果節(jié)點不在路由表的avl樹中則重新分配一個節(jié)點，在的話就把節(jié)點類型從avl_node類型轉(zhuǎn)化成rt_entry類型；00331-00344 把新節(jié)點添加進avl樹里然后更新整個路由表。-Olsr-Routing_table.c -Olsr-Routing_table.c函數(shù)功能：從路由表中刪除rtp樹并把它從從TC樹里刪除然后改變路由表版本。00353-00357把rtp所指向的樹節(jié)點從所在的的樹里刪除并把指向的樹的根置空；003