网络协议栈设计与分析Word格式.docx
- 文档编号:3716675
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:36
- 大小:879.87KB
网络协议栈设计与分析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表示没有删除。
---------
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 网络 协议 设计 分析