Ｌｉｎｕｘ操作系統基于ＩＰｖ６地址的ＯＬＳＲ協議實現方案

（電子科技大學通信抗干擾技術國家級重點實驗室， 成都 610054)



摘 要：

闡述了基于IPv6地址的Ad hoc OLSR協議在Linux操作系統上的實現方案及關鍵技術。根據Linux操作系統中路由體系結構的特點，設計了實現OLSR協議的整體框架，描述實現OLSR協議的程序架構，介紹了在這種架構中實現協議的關鍵技術，分析支持IPv6地址所需要的實現OLSR協議的主要困難并給出解決方法；最后在實驗室搭建實驗場景，設計網絡拓撲驗證該OLSR實現方案的可行性和正確性，著重分析了跳數對分組傳輸性能的影響。此實現方案具有良好的擴展性和通用性，各種通信路由協議都可以借鑒該方案設計。

關鍵詞：自組織網絡; Linux操作系統; 優化鏈絡狀態路由協議; IPv6地址

中圖分類號：TP393 文獻標志碼：A

文章編號：1001-3695(2009)02-0655-05



Implementation of IPv6 OLSR protocols in Linux OS



YAN Wen，GUO Wei， LIU Jun

(National Key Laboratory of Communication， University of Electronic Science Technology of China， Chengdu 610054， China)



Abstract:This paper presented a concrete scheme and key techniques about OLSR protocol implementation that supported IPv6 address in Ad hoc network. Firstly， introduced the general framework of IPv6 OLSR protocol according to the routing mechanism in Linux OS. Then analyzed the difficulties encountered in the implementation of IPv6 OLSR and then provided proper solutions. Finally， built two test beds and presented the implementation results. This implementation scheme is extensible and universalitythat can be applied to various proactive routing protocols.

Key words：Ad hoc network; Linux OS; OLSR (optimized link state routing) protocol; IPv6 address



0 引言 

移動Ad hoc網絡(mobile Ad hoc network， MANET)是一種由既是主機又是路由器的移動終端通過無線鏈路鏈接而成的自治系統。與單跳的無線網絡不同，Ad hoc網絡節點之間是通過數據多跳轉發機制進行數據交換，需要路由協議進行分組轉發決策。無線信道變化的不規則性、節點的移動、加入、退出等也會引起網絡拓撲結構的動態變化。路由協議是移動節點互相通信的基礎，提供網絡的連通性。OLSR[1]是經典的表驅動先應式路由協議，能快速高效地形成路由。

隨著互聯網的迅速發展，IPv4定義的有限地址空間將被耗盡，地址空間的不足必將妨礙互聯網的進一步發展。為擴大地址空間，通過IPv6協議重新定義地址空間。IPv6協議采用128 bit地址長度，幾乎能不受限制地提供地址。IPv6協議還考慮了在IPv4中解決不好的其他問題，如端到端IP連接、服務質量、安全性、多播、移動性、即插即用等。因此，實現支持IPv6地址的OLSR協議，并運用到實際網絡中顯得非常重要。

目前，國內外多用兩個流行的路由協議實現方案，即Gated[2]和Zebra[3]。Gated并非完全遵循GNU的條款，而且代碼不公開；Zebra遵循GNU條款，國外做OLSR協議的戶外測試多用Zebra，如支持移動IPv6協議的路由實現[4]，但按照Zebra結構編寫的路由序在閱讀和修改方面都非常困難。國內雖然有人提出OLSR的實現方案[5~7]，但多描述OLSR實現的各個模塊功能，只支持IPv4地址，實現只給出方案，沒有給出結果，不能證明運行結果的好壞。本文將直接按照Linux系統路由體系結構來實現OLSR協議功能。

1 OLSR協議

OLSR協議是對鏈路狀態路由協議的優化，是經典的表驅動先應式路由協議(table-driven routing protocol)。OLSR協議的路由發現策略與傳統路由協議類似，節點通過周期性地廣播路由信息分組，交換路由信息，主動發現路由。節點必須維護去往全網所有節點的路由，每個節點維護多張表格，這些表格包含到達網絡中所有節點的路由信息。

OLSR采用兩種方法來減少由于鏈路狀態信息洪泛所帶來的路由開銷：a)多點中繼站(multi-point relay，MPR)。每個節點在自己的一跳鄰居節點中選擇一部分節點作為自己的MPR，由MPR而不是所有的一跳鄰居節點轉發鏈路狀態消息，通過MPR實現路由控制消息的選擇性洪泛。b)鏈路狀態信息的壓縮。鏈路狀態信息只是描述與MPR之間的鏈路，而不是與所有的一跳鄰居節點的鏈路。

每個節點在入網后，迅速建立到網絡中其他節點的路由。單接口的OLSR協議有兩種類型的控制報文，即hello消息和拓撲控制(topology control， TC)消息。OLSR的兩個主要功能是鄰居發現和拓撲分發。鄰居發現通過每個節點在一跳范圍內周期性地廣播hello消息來實現。Hello消息包含與本節點直接相連的鄰居及其鏈路信息，用來確定1跳和2跳鄰居的鏈路狀態，同時根據1跳和2跳鄰居信息選取MPR。拓撲分發則通過MPR在全網范圍內周期性地廣播TC消息來實現：MPR節點周期性地洪泛TC消息，向全網洪泛由自己產生的包含與MPR選擇節點（MPR selector）間鏈路信息的TC消息；同時，轉發來自其他MPR節點的TC消息。

2 Linux系統下OLSR協議實現框架

Linux操作系統與Windows系統一樣，路由體系結構按功能可以分成兩個部分：a)負責與其他節點交換信息，計算到其他節點的正確路由，稱之為路由功能模塊；b)根據內核路由表的信息，將需要發送到網絡中的數據分組，通過正確的網絡接口發送到下一跳節點，稱為轉發功能模塊。這樣，操作系統就可以在轉發功能模塊保持不變的情況下，通過修改路由功能模塊，從而實現不同的路由協議。

本文直接按照Linux系統路由體系結構來實現OLSR協議功能。如圖1所示，OLSR協議的實現通過端口號為698的UDP端口收發路由控制分組；然后維護鄰居表，進行邏輯計算；最后生成路由表并反映到內核路由表中。數據分組和協議控制分組按照內核路由表中的最佳匹配表項進行發送和轉發。當網絡中有分組到達本節點時，內核將判斷該分組的目的地是否是自己。如果不是，則轉發功能模塊根據內核路由表轉發該分組；如果是，則根據分組的不同交給相應的模塊進行處理，當收到OLSR協議控制分組時，轉由OLSR路由協議模塊處理。

3 OLSR協議實現的程序框架

根據上面的分析，圖2提出OLSR路由協議程序框架，其中白色框中為主要函數。首先，根據解析輸入命令，并根據數據配置相應的接口，設置系統參數，獲得當前時間，初始化收發數據所需套接字和協議相關的表格；然后程序分接收處理模塊和信號處理模塊兩部分同時進行。

接收處理模塊用于處理OLSR控制消息，分為hello消息處理和TC消息處理。接收消息在處理之前，都會進行重復性檢查，防止處理相同源節點發送的相同控制分組。

a)當收到hello消息時，本地節點獲取有用信息，并根據獲得的信息來更新鄰居表、2跳鄰居表和MPR-selector表一旦發現鄰居表或2跳鄰居表的拓撲信息有變化，則重新選舉MPR和計算路由表；最后根據路由表更新情況進行添加/刪除核心路由表。Hello消息只在1跳范圍內傳送，不需要轉發。

b)當收到TC消息時，會根據TC消息中的ANSN(advertised neighbor sequence number)來確定該分組是否是較新的TC分組，即比較本節點記錄的最新序列號和ANSN值，檢查是否已經接收并處理過該TC消息。如果已經處理過該消息，則直接丟棄；如果沒有處理，則獲取有用信息來維護更新拓撲表信息，同時根據最短路徑優先算法重新計算路由表，反映到核心路由表中。不同于hello消息的1跳有效，拓撲的變化需要向全網絡擴散。本地節點會根據該收到的TC消息的最后發送節點是否存在于MPR_selector表中來判斷是否需要轉發TC分組。如果本節點是最近發送節點的MPR，則轉發TC分組；否則丟棄該分組。

信號處理模塊實現程序運行的定時、結束和中斷等信號的處理，包括中斷字符信號SIGINT和時間信號SIGALRM。

SIGINT信號用于結束程序。在Linux系統終端，該信號可以由“ctr+c”產生，進程如果收到Linux系統發送的SIGINT信號，則釋放OLSR程序運行相關的資源，結束程序。

SIGALRM信號由定時器設置。當Linux向進程發送SIGALRM信號時，進程將轉向執行中斷處理函數。具體包括：

a)周期性調用發送Hello消息模塊或發送TC消息模塊。Hello消息包含源節點所有鄰居節點的信息，而TC消息中僅僅包含MPR selector的地址。這些消息足以讓網絡中的各個節點形成網絡拓撲圖，進而獨立地根據最短路徑優先的原則來計算路由表。每發送一個TC消息，TC消息中的ANSN自動加1，便于其他節點接收TC分組時確定該分組是否是較新的分組。

b)各種信息表項的定時過期器操作。拓撲表、2跳鄰居表、MPR_selector表的每個表項都保存一個生存時間定時器。當表項過期后，則刪除該表項。鄰居表比較特殊，每個表項都保存了三個定時器。具體為：

(a)N_SYM_time。定時器到時后，該表項的N_status設置為LOST_NEIGH，更新本節點的2_hop鄰居表、MPR表、MPR selector表、拓撲表。

(b)N_ASYM_time。該定時器到時之后，則將該表項的N_status設置為LOST_NEIGH。因為只有N_status從SYM_NEIGH或MPR_NEIGH轉變為LOST_NEIGH或ASYM_NEIGH才需要更新其他相關表項，此處不需要更新其他相關表項。 

(c)N_time。該定時器到時后，則刪除該表項。

4 OLSR協議實現的關鍵技術

4. 1 表存儲結構的設置

OLSR協議是表驅動路由協議，在維護路由表的過程中，會利用各種表來記錄相應的信息。對于單接口的OLSR協議，每個節點需要維護的表信息如表1所示。

表1 單接口OLSR協議維護表信息

表說明

鄰居表記錄鄰居節點信息

2跳鄰居表記錄2跳鄰居節點信息

MPR表記錄本節點選取的MPR信息

MPR selector表記錄選取本節點為MPR的鄰居節點信息

拓撲表本網絡的拓撲信息

路由表本節點的路由信息

重復表記錄本網絡各節點包的序列號信息

采用何種形式存儲信息是實現OLSR協議面臨的第一個問題。鏈地址法hash表[8]可以方便快速地定位所需的信息，大大節約了表操作時間，當節點數目多時效果更加明顯。除了MPR表外，上述各類信息表都選擇hash表。

OLSR協議是表驅動路由協議，各個節點自動維護更新上述各個表。圖3為更新本地各個表的狀態轉移圖。圖中灰色圈標志收到hello消息后必定會更新的信息表，包括鄰居表、2跳鄰居表和MPR selector表；虛線為定時器時間到事件，其中3、4和6分別為2跳鄰居表、拓撲表和MPR selector表表項過期事件，而7事件是鄰居表表項SYM定時器時間到。1代表鄰居表發生變化，雙向鄰居出現或者消失；2為2-hop鄰居表發生變化，雙向2跳鄰居出現或消失；5代表增加或者刪除拓撲表表項。

4. 2 事件時間序列[9]

4. 2. 1 定時器的選擇

OLSR協議的實現，定時器具有舉足輕重的作用。程序架構描述中，無論是發送協議控制消息，還是各種信息表的更新，都離不了定時器。本文實現中使用settimer（或alarm）來設置定時器。因為該方法具有兩大優點：a)允許進程設置一次或每隔一定時間反復設置定時器；b)進程可以選擇定時對象。當設定的時間到時，Linux操作系統會向進程發送SIGALRM信號。SIGALRM產生后，進程會轉入處理SIGALRM信號函數。

4. 2. 2 事件時間序列

按照4.2.1節的方法，一個進程只能設置一個實時定時器，而OLSR協議需要多個定時器來滿足發送協議控制消息以及各種信息表表項更新的需要。

本文設計事件時間隊列（TimerQ隊列）來解決上述問題。TimerQ隊列的成員結構如圖4中的白色方框，該結構將事件與事件發生的時間一一對應。

TimerQ隊列使用雙向循環鏈表，按先后順序將事件掛載到時間軸上，構成事件鏈表。TimerQ隊列的操作包括添加、刪除和處理事件。當時間信號到達時，進入SIGALRM信號函數，節點依次查看事件發生時間，檢查是否有時間到達應該發生卻還未發生的事件。如果有則讓事件發生，并移除發生事件，在退出中斷函數之前為下一個最近事件設置實時事件發生定時器。

5 基于IPv 6地址的關鍵操作

5. 1 IPv6地址的基本操作[10]

因為IPv6地址長為128 bit，不同于IPv4的32 bit地址。相應的有一套支持IPv6通信的套接口地址結構及其函數。

5.1.1 IPv 6套接口地址結構

IPv6套接口地址結構與IPv4的套接口地址結構不一樣。IPv6的套接口地址結構定義如下:

struct in6_addr {

unit8_t s6_addr[16]; 

};

struct sockaddr_in6

{

uint8_t sin6_len;/*length of this struct (28)*/

uint8_tsin6_family;/*AF_INET6*/

unsigned short sin6_port; 

unsigned long sin6_flowinfo;

struct in6_addr sin6_addr;

unsigned long sin6_scope_id;

};

其中：IPv6地址簇為AF_INET6；IPv4為AF_INET。套接口地址結構僅在給定主機上使用。雖然結構中的某些成員用在不同主機間的通信，但結構本身并不參與通信。

5. 1. 2 地址轉換函數

在使用IP地址時，常常需要在ASCII字符串與網絡字節序的二進制值間進行轉換。IPv6和IPv4地址轉換操作如圖5所示。

5. 1. 3 套接口函數

OLSR實現需要用到的套接口函數有bind()、sendto()、recvfrom()。這些函數對IPv6與IPv4地址的操作基本一致，惟一的區別在于IPv6地址長度為sockaddr_in6結構體的長度，而不是sockaddr_in結構體的長度。

5. 2 IPv6多播

與IPv4協議不同，在 IPv6協議沒有廣播地址，而是由多播功能代替。

5. 2. 1 IPv6多播地址

多播地址識別多個接口。使用適當的多播路由拓撲，將向多播地址發送的數據包發送給該地址識別的所有接口。IPv6多播地址的高序字節值為ff，低序兩位是該地址的標志和范圍。多播地址不能用做源地址。特別地，為了識別用于節點本地和鏈路本地作用域的所有節點，定義多播地址FF01::1標志節點本地作用域所有節點地址，FF02::1標志鏈路本地作用域所有節點地址。 

5. 2. 2 加入多播組

節點需要設置多播地址所屬的接口讓其識別多播地址，才能與多播組的其他節點通信。Linux操作系統提供setsockopt函數完成加入和離開多播組的操作。當選項名為IPv6_MULTICAST_IF時，指定外出多播數據包的缺省接口，而IPv6_ADD_MEMBERSHIP為加入一個不限源的多播組。在加入多播組時，會用到如下的數據結構：

struct ipv6_mreq{

struct in6_addr ipv6mr_multiaddr;/*IPv6 multicast addr */

unsigned int ipv6mr_interface;/* interface index， or 0 */

};

在一個指定的本地接口上離開一個不限源的多播組，操作過程與加入多播組一致，不同的是選項名為IPv6_DROP_MEMBERSHIP。如果一個進程加入某個多播組后從不顯示離開該組，那么在關閉相應套接口時，該多播組成員關系將自動抹除。

5. 3 核心路由表的操作[10]

路由功能模塊需要按照路由協議的算法添加、修改和刪除相應的內核路由表項。Linux系統的ioctl可以方便地實現從用戶空間對內核路由表項的維護操作。它提供了內核/用戶空間的雙向通道。Linux系統提供兩個用于操縱路由表的ioctl請求：SIOADDRT和SIOCDELRT。SIOADDRT請求往路由表中增添一個表項，SIOCDELRT請求從路由表中刪除一個表項。

IPv4中，在添加和刪除路由表請求時，ioctl的第三個參數是rtentry結構的指針；而對IPv6核心路由表進行修改時，使用in6_rtmsg的數據結構。特別需要注意的是，在設置接口時，in6_rtmsg中的設備標志不再是網卡名，而是網卡的設備號，需要使用if_nametoindex函數將網卡名轉換為設備號。

IPv6核心路由表表項的添加和刪除主要受目的地、網關（下一跳）和標志設置的影響。標志位的設置非常重要，決定著傳輸數據時添加的路由表項是否發揮作用。跳數大于1跳的路由表項標志設為RTF_UP、RTF_HOST、RTF_GATEWAY開啟；跳數等于1跳的路由表項標志設為RTF_UP、RTF_HOST開啟。

6 實驗場景的搭建及應用

實現中， socket采用的是普通UDP socket，端口為698；多播地址為ff05::15。用帶IEEE 802.11b無線網卡的主機（包括臺式機和筆記本電腦）來表示移動節點。

6. 1 實驗場景的搭建方法

為驗證OLSR協議實現的正確性和可行性，需要在無線多跳網絡環境下測試。然而網卡的實際傳送距離是室外約為300 m，室內為100 m以上。由于實驗室條件的限制，在實驗室節點間都是相互直連的，很難建立多跳的無線網絡。

Linux操作系統的包過濾器可以在實驗室模擬不直連的情況。包過濾器是這樣一種軟件：它檢查通過的每個包的頭部，然后決定如何處置它們。可以這樣對待它們：丟棄（也就是說如果這個包從未被接受，那么丟棄它）、通過（也就是說，讓包通過），或者更復雜的操作。通過包過濾器，在構建局域網時，可以決定哪些通信是允許的，哪些不允許。Linux操作系統專門提供了ip6tables[11]工具，以向內核的包過濾表中插入和刪除支持IPv6協議操作的規則。假設某節點M，它的無線網卡接口IP地址是fec0:106:2700::12(以后簡寫為::12)，MAC地址為00:19:E0:85:01:57，那么，要阻止與節點M的通信，需要添加規則：

ip6tables-A INPUT-m mac--mac-source 00:19:E0:85:01:57-j DROP

要刪除該規則，使其重新與M通信：

ip6tables-D INPUT 1

查看ip6tables制定的規則：

ip6tables-L INPUT

通過上述方法，可以在實驗室中搭建所需的各種拓撲，測試OLSR協議實現的性能。

另外，由于筆者使用的是PC機，而不是路由器，在搭建網絡場景時，如果設置兩節點不直連，即使它們之間有路由，也不能通信。問題的關鍵在于節點沒有轉發功能。Linux操作系統中有/proc/sys/net/ipv6/conf/all/forwarding文件，可以通過設置參數值為1來開啟包轉發功能，從而使系統充當路由器。

6. 2 OLSR協議性能測試工具

6. 2. 1 Watch route-A inet6

按照6.1節描述的方法搭建實驗場景，運行OLSR實現后，watch route-A inet6命令能觀察IPv6核心路由表的更新情況。

6. 2. 2 Ping6

Ping命令是網絡常用的連通性測試命令;ping6是擴展后測試IPv6網絡連通性的命令，還可以統計丟包率和時延情況。6.3節中的數據就是通過ping6命令獲得。

6. 3 應用

按照上述方法，在實驗室搭建了有六個節點的無線多跳網絡。人為設置了不同的網絡拓撲。無論在單種拓撲還是多種拓撲切換情況下，實時查看核心路由的維護情況，能顯現當前路由，并在拓撲發生變化時快速收斂。

最后，設置如圖6和7所示的兩種靜態網絡拓撲來作性能測試。在每種拓撲下，每個節點向其他五個節點發送1 000個ICMP分組。統計在無負載情況下IPv6分組成功傳輸率和分組平均傳輸延遲兩個信息。其中：成功傳輸率=接收分組個數/發送分組個數；平均傳輸延遲=所有分組發送到收到應答的傳輸時間總和/分組發送個數。

在拓撲1情況下，各節點的統計信息如表2所示。行號代表源節點，IPv6地址為fec0:106:2700::22的節點簡寫為:22；列號標志為目的節點，每個目的節點包含統計的分組傳送成功率(簡寫為成功率)和分組平均傳輸延遲(簡寫為延遲)兩種信息。同樣地，拓撲2的統計信息如表3所示。本文著重分析跳數與分組成功傳輸率和分組平均傳輸延遲的關系。如圖8所示，橫坐標表示跳數，縱坐標表示平均分組成功傳輸率。圖中每一個點是對上面統計信息中擁有相應跳數的所有平均分組成功傳輸率求平均得到的。類似地，圖9分析了跳數和平均延遲的關系。

表2 網絡拓撲1的數據成功率和分組傳輸平均延遲

觀察圖8和9，總的來說，跳數影響網絡分組傳輸的性能。隨著跳數的增加，平均分組成功傳輸率下降，平均分組傳輸延遲隨之增大。

7 結束語

本文提出了Linux操作系統下OLSR協議支持IPv6協議的實現方案，并進行了可行性和正確性測試，得出跳數影響網絡分組傳輸的性能結論。該OLSR協議實現的設計方案充分考慮了主動路由協議的特點，具有良好的通用性和擴展性。其他先應式路由協議也可按照相同的設計方法實現，一般的通信協議也可以借鑒上述設計思路。同時，在資源有限的情況下搭建實驗平臺，驗證了該方案的正確性和可行性。今后將結合QoS作約束路由，改進路由協議在實際網絡中的性能。

參考文獻：

[1]CLAUSEN T， JACQUET P. RFC 3626， Optimized link state routing protocol[S]. 2003.

[2]Gated project homepage［EB/OL］.(2007-09-05).http://www.gated.org.

[3]Zebra project homepage［EB/OL］.(2007-11-05). http://www.zebra.org/.

[4]TSUKADA M， ERNST T. Vehicle communication experiment environment with MANET and NEMO［C］//Proc of Applications and the Internet Workshops. 2007.

[5]梁海蓮，張懿煌，須文波.基于OOP的OLSR路由協議的一種實現方案[J].微計算機信息，2007，23(27):125-126.

[6]陳繼彤，郭偉，任智.OLSR路由協議拓撲發現的一種實現方案[J].中國測試技術，2006，32(3):78-81.

[7]郝立剛.Ad hoc網絡上的動態路由協議研究及實現[J].無線電通信技術，2006，32(3):5-10.

[8]唐發根.數據結構[M].北京：科學出版社， 2001:212-216.

[9]STEVENS W R.Advanced programming in the UNIX environment[M].3rd ed.[S.l.]: Addison Wesley， 2002:263-324.

[10]STEVENS W R， FENNER B， RUDOFF A M. UNIX network programming， volume 1:the sockets networking API[M]. 3rd ed. [S.l.]: Addison Wesley， 2003.

[11]Netfilter/Iptables homepage［EB/OL］.(2007-12-07).http://www.netfilter.org.