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

1、4.3.3 邻居节点的查找与插入174.3.4 邻居表的更新184.3.5 其他操作18第五章MPR 选择195.1 MPR 节点的添加和清除195.2 MPR 算法205.2.1 olsr_find_2_hop_neighbors_with_1_link 函数215.2.2 olse_chosen_mpr 函数225.2.3 olsr_find_maximum_covered 函数225.2.4 olsr_check_mpr_changes 函数235.2.5 优化 MPR 集合24第六章拓扑控制消息洪泛246.1 TC 消息初始化与删除246.2 TC 消息处理262 / 36第七章路由表

2、的计算267.1 主要数据结构分析277.1.1 rt_metric 和 rt_nexthop277.1.2 rt_entry277.1.3 路由类型287.2 路由表计算297.2.1 路由表的创建与删除297.2.2 最优路径31第八章总结323 / 36组内分工项目参与者数据结构部分代码分析邻居发现部分代码分析万宇腾、刘伟麟MPR 选择部分代码分析TC 消息洪泛部分代码分析路由计算部分代码分析论文撰写肖明旺、万宇腾、丁英才、刘伟麟论文汇总第一章引言最佳链路状态路由协议（ Optimized Link Status Routing Protocol, OLSR ），是专门为无线移动 Ad

3、Hoc 网络提出来的一种标准化的先验式的优化链路状态路由协议。该协议的核心是使用了多点中继站（MPRs），MPRs 是被选择的节点，具有转发网络控制消息的能力。根据协议，每个节点之间周期性的交换控制信息，节点根据协议计算自己的网络拓扑。OLSR 向所有节点提供一个最短路径，该技术可以有效减少网络中数据传输的信息量。每一个被邻居们选择的节点在控制信息里周期性的广播这一信息。因此， 可以说是由被选择的节点构成了主要的网络。相比经典的链路状态算法，OLSR 更适合移动无线局域网。该协议比较适合大型密集的网络。OLSR 有以下优点：1 利用 MPRs 来重传控制消息可以减少网络间消息的发送数量。4 /

4、 362 只需要部分链路状态洪泛就可以获取最佳路径。3 网络越大则 OLSR 可优化的范围就越大也就能得到更好的性能在 OLSR 协议中，状态路由协议的网络信息状态由被推选的节点（MPR）掌控。所以，优化的一条途径是减少网络中的控制信息。只有被选择的 MPR 节点才能被用做路由节点，非 MPR 节点不参与路由计算。MPR 可以减少网络中冗余消息的传送。每个节点传送消息给一跳邻居，但是邻居并不能再将此消息传送给其他节点。OSLR 协议逐跳寻找路径，每个节点利用本地信息向邻居节点发送路由包来获取路径。由于该协议在设计之初就考虑到协议的分布式工作，所以该协议不依赖于任何的中心，也不需要稳定的的控制信

5、息的传播。每一个节点都周期性的发送信息，这样也保证了一个在可以接受范围内的丢包率。OLSR 协议在设计之初就考虑了协议的独立性，因此 OLSR 协议独立工作于一些协议。它对 IP 的包格式没有做任何改变，因此，任何 IP 协议栈都能在协议中正常使用。第二章代码介绍2.1 文件介绍OLSR 路由协议共有 123 个源文件。我们将对部分源文件进行功能型介绍。表格 1 OLSR 协议部分源文件介绍文件描述Olsrd-0.6.0/link_set.c确定邻居表的信息Olsrd-0.6.0/lq_packet.h对 olsr,hello,TC 数据包以及其他一些数据结构的定义Olsrd-0.6.0/mp

6、r.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 树的构

7、造从而实现迪杰斯特拉算法计算路由表5 / 36Olsrd-0.6.0/routing_table.c路由表的处理Olsrd-0.6.0/TC_set.cTC 消息的洪泛2.2 全局变量在 olsr 路由协议中使用的全局变量有许多，我们在这里只介绍部分重要的全局变量。表格 2 OLSR 协议部分全局变量介绍全局变量数据类型olsrportnit16_tOLSR 消息发送接收的端口号rt_protonit8_t路由表计算的所遵循的协议willingnessWILL_ALWAYS 的邻居节点集合use_hysteresisbool判断消息是否迟滞min_tc_vtimefloatTC 消息 vtim

8、e 的最小取值max_tc_vtimeTC 消息 vtime 的最大取值max_jitter消息传播的最大抖动changes_topology判断拓扑信息是否变化changes_neighborhood判断邻居信息是否变化2.3 配置表格 3 OLSR 路由协议配置名称默认值DEF_IP_VERSION DEF_USE_HYST DEF_LQ_LEVEL DEF_OLSRPORT DEF_MIN_TC_VTIME DEF_GW_TYPE DEF_DOWNLINK_SPEED MAX_LQ_LEVEL MIN_LQ_LEVELDEF_RTPROTO缺省 ip 协议域缺省消息迟滞缺省链路质量等级缺

9、省 olsr 端口号TC 消息 vtime 最小取值缺省网关类型缺省的链路下载速度 缺省链路质量最高等级缺省链路质量最高等级缺省的路由协议AF_INETFalse 26980.0GW_UOLINk_IPV461024kb/s 2MAX_TTLMAXJITTER定义 ttl 最大值Olsr 消息传播最大抖动0.165msHELLO_INTERVAL/4COOKIE_ID_MAX系统 cookie 数量最大值25MAXMESSAGESIZE广播数据包大小的最大值1500kb6 / 36OLSR_LINK_JITTER OLSR_LINK_HELLO_JITTER OLSR_LINK_SYM_JIT

10、TER OLSR_LINK_LOSS_JITTERolsr 消息抖动时间HELLO 消息抖动时间系统抖动时间数据包丢失抖动时间5s 0s 0s 0s第三章OLSR 部分消息包数据结构OLSR使用统一的数据包格式，使用UDP通信，数据包嵌入到UDP数据报在网络上传输。每个数据包封装一个或多个消息，邮件分享通用报头格式，使节点能够正确接收和重传一个未知类型的消息。如果数据包不包含任何信息（数据包的长度小于或等于该数据包报头的大小），数据包就会默默的丢弃。每一个消息都会分配一个唯一的标识号，用来确保消息不重传。OLSR 数据包一般包含以下几部分:消息类型,VTIME 邮件大小,发端地址,生存时间,跳

11、数,消息序列号和消息。其中 VTIME 是表示接收后很长时间节点如何， 确保数据包中的消息有效；生存时间包含最大跳数，如果被重发，则减 1；消息序列号被用来确保给定的消息被节点转发的次数不超过一次。3.1 OLSR 首部-Olsr-lq_packet.holsr_common是OLSR协议基本数据包。其中包含以下几部分:type，消息类型；vtime, 表示接收后很长时间节点如何，确保数据包中的消息有效；size，消息大小；orig，发端地址；ttl，跳数，消息在传递过程中最大跳数，每转发一次，ttl减1；hops，此消息在传递过程中经历的跳数； seqno，消息的序列号，这是唯一不变的，以确

12、保消息不回被重发。表格 4 OLSR 协议数据包Packet LengthPacket Sequence NumberMessage TypeVtimeMessage Size7 / 36Originator AddressTime To LiveHop CountMessage Sequence NumberMESSAGE3.2 HELLO 消息包HELLO用于建立一个节点的邻居表，其中包括邻居节点的地址以及本节点到邻居节点的延时和开销，OLSR采用周期性的广播HELLO分组来侦听邻居节点的状态和无线链路的对称性。节点之间无线链路的状态包括：非对称链路，对称链路，连接MPR的链路。但OLSR

13、协议只关心对称链路，同时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）；

14、link_type，连接类型（UNSPEC_LINK）；addr，地址；linkquality，链路的质量。3.3 TC 消息包8 / 36TC 分组数据包必须通过 MPR 节点传递消息被广播到全网中，用以维护网络的拓扑信息、确保链路时刻连通状态和更新路由表集。lq_TC_message是封装后的拓扑数据包格式。from：接受包的上一个节点地址；ansn：节点接受到消息时拓扑集合会被更新。-Olsr-packet.h-Olsr-packet.hTC_message 是 TC 消息数据包格式。第四章邻居发现邻居发现是基于节点的邻居信息库，通过 HELLO 消息的传播实现。邻居信息库包含关于邻居、

15、2 跳邻居、MPRs 和 MPR 的信息。4.1 节点信息的存储每个节点都存储自身的信息在结构体 link_entry 中。-Olsr-link_set.h9 / 3600059-00060：local_iface_addr 存储该节点接口 ip 地址，neighbor_iface_addr 存储邻居节点 ip 地址。00067：neighbor 以链链表形存储邻居节点信息。邻居节点具体信息如下：-Olsr-neighbor_table.hneighbor_entry 结构体，同来存储邻居节点的信息。记录了邻居节点的主地址，状态，作为 MPR 的 willingnessz 值，是否是 MPR，

16、是否曾是 MPR,覆盖的两跳邻居节点的数量，及节点连接链路的数量以及指向 neighbor_2_list 连表的指10 / 36针。其中，成员变量 was_mpr 用来发现 MPR 的变化。这段代码定义了 neighbor_2_list_entry 结构体，这是用来存储邻居节点信息， 两跳邻居节点信息以及记录有效时间的链表结构。mid_address 存储本节点的其他接口 ip 地址。其中 mid_entry 节点链路信息。mid_entry 包含节点主地址，上一节点和下一节点链路，同时还有本节点链路中其他端口信息存储在 aliases 链表中。4.2 关于节点的具体操作分析-Olsr-lin

17、k_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； 首先定义了三个

18、 link_entry 结构 walker，good_link,backup_link；00223-00229：找出该节点的主地址，通过遍历 walker 链表，查找出跳数最少的邻居，这就是最新的邻居表信息，最短的邻居表。删除节点链路上所有的信息。定义拓扑边缘节点 TC_edge：通过邻居端口地址找出 TC_edge 边缘链路。00365-00369：删除边缘链路 spf；00372-00377：删除邻居链路信息，存储在 hash 表中的链路表删除；13 / 3600379-00394：清空一些正在计时的属性，同时释放 link 的资源空间；同时将 change_neighborhood 设置

19、为 true，让其他节点更新自己的链路状况，发送 hello 消息包及时更新邻居表的信息。更新链路信息状态，通过 hello_message 来更新邻居节点的信息。00694-00699：如果该节点不在链路中，把它加入到链路中去，并将计时器更新；00708-00732：通过 check_link_status 同过发送 hello_message 发现该节点的邻居节点链路状态 link_type，对不同的状态采取不同的操作：00708-00718：如果是对称或者非对称的需将定时器重新设置，更新定时器；14 / 3600732：更新邻居节点的状态信息，是对称还是非对称。发送 Hello 消息，维

20、护一个端口的邻居信息。00780-00797：发送 hello_message 来维护端口信息，直到消息到达端口的所有的邻居节点，就停止发送，则该端口的所有邻居节点链路都检查完毕。4.3 邻居表的操作4.3.1 邻居表的初始化-Olsr-neighbor_table.c初始化邻居表。00061-00064：将每一个邻居表 neighortablei初始化为指向自身的仅有一个节点的链表。15 / 364.3.2 删除节点删除释放一个两跳邻居节点记录。00073-00077：获取两跳邻居节点记录中 nbr2_list 中的邻居节点结构体nbr 和两跳邻居节点结构体 nbr2；00079-00082

21、：释放两跳邻居节点结构体 nbr2 的空间；00087-00088：将两跳邻居节点记录中的计时器置为空；00096-00097：通过将全局变量 changes_neighborhood,changes_topology置为真，通知网络重新计算 MPR 集合和路由表。16 / 36将从两跳邻居节点信息中，根据给定的邻居节点地址删除对应的两跳邻居节点。00111-00113：获取邻居节点的两跳邻居节点信息表；00115-00121：遍历邻居节点的两跳邻居及节点信息表，直到找到信息表中两跳邻居节点与给定的两跳邻居节点相同，则删除该两跳邻居节点并返回 1， 表示成功删除；否则返回 0 表示没有删除。-