网络协议栈设计与分析Word格式.docx

网络协议栈设计与分析Word格式.docx

《网络协议栈设计与分析Word格式.docx》由会员分享，可在线阅读，更多相关《网络协议栈设计与分析Word格式.docx（36页珍藏版）》请在冰点文库上搜索。

4.3.3邻居节点的查找与插入 17

4.3.4邻居表的更新 18

4.3.5其他操作 18

第五章 MPR选择 19

5.1MPR节点的添加和清除 19

5.2MPR算法 20

5.2.1olsr_find_2_hop_neighbors_with_1_link函数 21

5.2.2olse_chosen_mpr函数 22

5.2.3olsr_find_maximum_covered函数 22

5.2.4olsr_check_mpr_changes函数 23

5.2.5优化MPR集合 24

第六章 拓扑控制消息洪泛 24

6.1TC消息初始化与删除 24

6.2TC消息处理 26

2/36

第七章 路由表的计算 26

7.1主要数据结构分析 27

7.1.1rt_metric和rt_nexthop 27

7.1.2rt_entry 27

7.1.3路由类型 28

7.2路由表计算 29

7.2.1路由表的创建与删除 29

7.2.2最优路径 31

第八章 总结 32

3/36

组内分工

项目

参与者

数据结构部分代码分析

邻居发现部分代码分析

万宇腾、刘伟麟

MPR选择部分代码分析

TC消息洪泛部分代码分析

路由计算部分代码分析

论文撰写

肖明旺、万宇腾、丁英才、刘伟麟

论文汇总

第一章 引言

最佳链路状态路由协议（OptimizedLinkStatusRoutingProtocol,OLSR），是专门为无线移动AdHoc网络提出来的一种标准化的先验式的优化链路状态路由协议。

该协议的核心是使用了多点中继站（MPRs），MPRs是被选择的节点，具有转发网络控制消息的能力。

根据协议，每个节点之间周期性的交换控制信息，节点根据协议计算自己的网络拓扑。

OLSR向所有节点提供一个最短路径，该技术可以有效减少网络中数据传输的信息量。

每一个被邻居们选择的节点在控制信息里周期性的广播这一信息。

因此，可以说是由被选择的节点构成了主要的网络。

相比经典的链路状态算法，OLSR更适合移动无线局域网。

该协议比较适合大型密集的网络。

OLSR有以下优点：

1利用MPRs来重传控制消息可以减少网络间消息的发送数量。

4/36

2只需要部分链路状态洪泛就可以获取最佳路径。

3网络越大则OLSR可优化的范围就越大也就能得到更好的性能

在OLSR协议中，状态路由协议的网络信息状态由被推选的节点（MPR）掌控。

所以，优化的一条途径是减少网络中的控制信息。

只有被选择的MPR节点才

能被用做路由节点，非MPR节点不参与路由计算。

MPR可以减少网络中冗余消息的传送。

每个节点传送消息给一跳邻居，但是邻居并不能再将此消息传送给其他节点。

OSLR协议逐跳寻找路径，每个节点利用本地信息向邻居节点发送路由包来获取路径。

由于该协议在设计之初就考虑到协议的分布式工作，所以该协议不依赖于任何的中心，也不需要稳定的的控制信息的传播。

每一个节点都周期性的发送信息，这样也保证了一个在可以接受范围内的丢包率。

OLSR协议在设计之初就考虑了协议的独立性，因此OLSR协议独立工作于一些协议。

它对IP的包格式没有做任何改变，因此，任何IP协议栈都能在协议中正常使用。

第二章 代码介绍

2.1文件介绍

OLSR路由协议共有123个源文件。

我们将对部分源文件进行功能型介绍。

表格1OLSR协议部分源文件介绍

文件

描述

Olsrd-0.6.0/link_set.c

确定邻居表的信息

Olsrd-0.6.0/lq_packet.h

对olsr,hello,TC数据包以及其他一些数据结构的

定义

Olsrd-0.6.0/mpr.c

关于MPR的一些操作

Olsrd-0.6.0/mpr_selector_set.h

定义了结构体mpr_selector表示MPR选择源节

点的集合

Olsrd-0.6.0/neighbor_table.h

对邻居信息数据结构的定义

Olsrd-0.6.0/neighbor_table.c

对一跳邻居和二跳邻居的处理

Olsrd-0.6.0/olsr.c

实现一些全局函数，比如网络拓扑结构的计算、路由表的计算与更新和错误处理函数等等

Olsrd-0.6.0/olsr_cfg.h

定义大部分常量，比如DEF_WILLINGNESS等

Olsrd-0.6.0/olsr_spf.c

实现spf树的构造从而实现迪杰斯特拉算法计

算路由表

5/36

Olsrd-0.6.0/routing_table.c

路由表的处理

Olsrd-0.6.0/TC_set.c

TC消息的洪泛

2.2全局变量

在olsr路由协议中使用的全局变量有许多，我们在这里只介绍部分重要的全局变量。

表格2OLSR协议部分全局变量介绍

全局变量

数据类型

olsrport

nit16_t

OLSR消息发送接收的端口号

rt_proto

nit8_t

路由表计算的所遵循的协议

willingness

WILL_ALWAYS的邻居节点集合

use_hysteresis

bool

判断消息是否迟滞

min_tc_vtime

float

TC消息vtime的最小取值

max_tc_vtime

TC消息vtime的最大取值

max_jitter

消息传播的最大抖动

changes_topology

判断拓扑信息是否变化

changes_neighborhood

判断邻居信息是否变化

2.3配置

表格3OLSR路由协议配置

名称

默认值

DEF_IP_VERSIONDEF_USE_HYSTDEF_LQ_LEVELDEF_OLSRPORTDEF_MIN_TC_VTIMEDEF_GW_TYPEDEF_DOWNLINK_SPEEDMAX_LQ_LEVELMIN_LQ_LEVEL

DEF_RTPROTO

缺省ip协议域缺省消息迟滞

缺省链路质量等级缺省olsr端口号

TC消息vtime最小取值缺省网关类型

缺省的链路下载速度缺省链路质量最高等级缺省链路质量最高等级

缺省的路由协议

AF_INET

False2

698

0.0

GW_UOLINk_IPV46

1024kb/s2

MAX_TTL

MAXJITTER

定义ttl最大值

Olsr消息传播最大抖动

0.165ms

HELLO_INTERVAL/4

COOKIE_ID_MAX

系统cookie数量最大值

25

MAXMESSAGESIZE

广播数据包大小的最大值

1500kb

6/36

OLSR_LINK_JITTEROLSR_LINK_HELLO_JITTEROLSR_LINK_SYM_JITTEROLSR_LINK_LOSS_JITTER

olsr消息抖动时间

HELLO消息抖动时间系统抖动时间

数据包丢失抖动时间

5s0s0s0s

第三章 OLSR部分消息包数据结构

OLSR使用统一的数据包格式，使用UDP通信，数据包嵌入到UDP数据报在网络上传输。

每个数据包封装一个或多个消息，邮件分享通用报头格式，使节点能够正确接收和重传一个未知类型的消息。

如果数据包不包含任何信息（数据包的长度小于或等于该数据包报头的大小），数据包就会默默的丢弃。

每一个消息都会分配一个唯一的标识号，用来确保消息不重传。

OLSR数据包一般包含以下几部分:

消息类型,VTIME邮件大小,发端地址,生存时间,跳数,消息序列号和消息。

其中VTIME是表示接收后很长时间节点如何，确保数据包中的消息有效；

生存时间包含最大跳数，如果被重发，则减1；

消息序列号被用来确保给定的消息被节点转发的次数不超过一次。

3.1OLSR首部

-------------------------------------------------Olsr-lq_packet.h

olsr_common是OLSR协议基本数据包。

其中包含以下几部分:

type，消息类型；

vtime,表示接收后很长时间节点如何，确保数据包中的消息有效；

size，消息大小；

orig，发端地址；

ttl，跳数，消息在传递过程中最大跳数，每转发一次，ttl减1；

hops，此消息在传递过程中经历的跳数；

seqno，消息的序列号，这是唯一不变的，以确保消息不回被重发。

表格4OLSR协议数据包

PacketLength

PacketSequenceNumber

MessageType

Vtime

MessageSize

7/36

OriginatorAddress

TimeToLive

HopCount

MessageSequenceNumber

MESSAGE

3.2HELLO消息包

HELLO用于建立一个节点的邻居表，其中包括邻居节点的地址以及本节点到邻居节点的延时和开销，OLSR采用周期性的广播HELLO分组来侦听邻居节点的状态和无线链路的对称性。

节点之间无线链路的状态包括：

非对称链路，对称链路，连接MPR的链路。

但OLSR协议只关心对称链路，同时HELLO分组只在一跳的范围内广播，不能被转发；

与此相反，TC分组必须被广播到全网，在TC分组中包含了将发送TC分组的节点选为MPR的邻居节点的信息，节点根据收到的

TC分组来计算出网络拓扑图。

结构体lq_hello_message即Hello消息数据包介绍：

htime，HELLO消息发射间隔；

will，指定节点的意愿进行，有意愿的WILL_NEVER的节点被选为MPR的任意节点；

neigh，消息传递的下一个节点。

lq_hello_neighbor是HELLO消息邻居节点集：

neigh_type，邻居类型

（SYM_NEIGH，NOT_NEIGH）；

link_type，连接类型（UNSPEC_LINK）；

addr，地址；

linkquality，链路的质量。

3.3TC消息包

8/36

TC分组数据包必须通过MPR节点传递消息被广播到全网中，用以维护网络的拓扑信息、确保链路时刻连通状态和更新路由表集。

lq_TC_message 是封装后的拓扑数据包格式。

from：

接受包的上一个节点地址；

ansn：

节点接受到消息时拓扑集合会被更新。

---------------------------------------------------Olsr-packet.h

----------------------------------------------------Olsr-packet.h

TC_message是TC消息数据包格式。

第四章 邻居发现

邻居发现是基于节点的邻居信息库，通过HELLO消息的传播实现。

邻居信息库包含关于邻居、2跳邻居、MPRs和MPR的信息。

4.1节点信息的存储

每个节点都存储自身的信息在结构体link_entry中。

------------------------------------------------Olsr-link_set.h

9/36

00059-00060：

local_iface_addr存储该节点接口ip地址，

neighbor_iface_addr存储邻居节点ip地址。

00067：

neighbor以链链表形存储邻居节点信息。

邻居节点具体信息如下：

-----------------------------------------Olsr-neighbor_table.h

neighbor_entry结构体，同来存储邻居节点的信息。

记录了邻居节点的主地址，状态，作为MPR的willingnessz值，是否是MPR，是否曾是MPR,覆盖的两跳邻居节点的数量，及节点连接链路的数量以及指向neighbor_2_list连表的指

10/36

针。

其中，成员变量was_mpr用来发现MPR的变化。

这段代码定义了neighbor_2_list_entry结构体，这是用来存储邻居节点信息，两跳邻居节点信息以及记录有效时间的链表结构。

mid_address存储本节点的其他接口ip地址。

其中mid_entry节点链路信息。

mid_entry包含节点主地址，上一节点和下一节点链路，同时还有本节点链路中其他端口信息存储在aliases链表中。

4.2关于节点的具体操作分析

------------------------------------------------Olsr-link_set.c

函数功能：

重置所有节点信息。

00095-00103：

遍历所有节点一遍，把所有信息置为初始值，并把邻居节点也设为空值。

11/36

通过查找main_addr（184-185行）找到节点link_entry,通过lookup_link_status

找出节点链路状态。

判断其是否是对称状态。

00197-00206：

行是查找主地址并找出节点上的其他端口ip判断该节点其他端口aliases链路状态。

并判断该ip地址所在的链路状态是否是对称状态。

只返回对称链路的信息。

12/36

查找端口ip地址的最少跳数邻居，并返回该节点信息link_entry；

首先定义了三个link_entry结构walker，good_link,backup_link；

00223-00229：

找出该节点的主地址，通过遍历walker链表，查找出跳数最少的邻居，这就是最新的邻居表信息，最短的邻居表。

删除节点链路上所有的信息。

定义拓扑边缘节点TC_edge：

通过邻居端口地址找出TC_edge边缘链路。

00365-00369：

删除边缘链路spf；

00372-00377：

删除邻居链路信息，存储在hash表中的链路表删除；

13/36

00379-00394：

清空一些正在计时的属性，同时释放link的资源空间；

同时将change_neighborhood设置为true，让其他节点更新自己的链路状况，发送hello消息包及时更新邻居表的信息。

更新链路信息状态，通过hello_message来更新邻居节点的信息。

00694-00699：

如果该节点不在链路中，把它加入到链路中去，并将计时器更新；

00708-00732：

通过check_link_status同过发送hello_message发现该节点的邻居节点链路状态link_type，对不同的状态采取不同的操作：

00708-00718：

如果是对称或者非对称的需将定时器重新设置，更新定时器；

14/36

00732：

更新邻居节点的状态信息，是对称还是非对称。

发送Hello消息，维护一个端口的邻居信息。

00780-00797：

发送hello_message来维护端口信息，直到消息到达端口的所有的邻居节点，就停止发送，则该端口的所有邻居节点链路都检查完毕。

4.3邻居表的操作

4.3.1邻居表的初始化

-----------------------------------------Olsr-neighbor_table.c

初始化邻居表。

00061-00064：

将每一个邻居表neighortable[i]初始化为指向自身的仅有一个节点的链表。

15/36

4.3.2删除节点

删除释放一个两跳邻居节点记录。

00073-00077：

获取两跳邻居节点记录中nbr2_list中的邻居节点结构体

nbr和两跳邻居节点结构体nbr2；

00079-00082：

释放两跳邻居节点结构体nbr2的空间；

00087-00088：

将两跳邻居节点记录中的计时器置为空；

00096-00097：

通过将全局变量changes_neighborhood,changes_topology

置为真，通知网络重新计算MPR集合和路由表。

16/36

将从两跳邻居节点信息中，根据给定的邻居节点地址删除对应的两跳邻居节点。

00111-00113：

获取邻居节点的两跳邻居节点信息表；

00115-00121：

遍历邻居节点的两跳邻居及节点信息表，直到找到信息表中两跳邻居节点与给定的两跳邻居节点相同，则删除该两跳邻居节点并返回1，表示成功删除；

否则返回0表示没有删除。

---------