基于C++实现 OLSR 路由协议代码(网络协议栈分析与设计课程大作业)【100012152】

# 网络协议栈分析与设计课程大作业 # OLSR 路由协议代码分析 ## 一、OLSR 简介 ### 1.1 OLSR 基本概念 OLSR 是 Optimized Link State Routing 的简称，主要用于 MANET 网络(Mobile Ad hoc network)的路由协议。它是一种标准化的表驱动式路由协议，它是为了适应无线自组网的需求，对经典链路状态算法进行优化而形成的。协议用到的核心概念是多点中继机制，通过此机制，协议显著的减少了分组消息的开支。具体来讲，协议对传统链路状态算法所做的优化主要有：通过采用多点中继机制，有效减小了控制分组的洪泛范围；节点在其所有的邻节点中，选择部分节点作为其多点中继节点 MPR。对比经典的洪泛机制中每个节点当其第一次收到一个控制消息时转发每一个消息，OLSR 协议中只有节点的 MPR 节点才转发该节点所发送的控制分组，而其他非 MPR 节点只进行处理不进行转发。这样就显著的减少了网络中广播的控制分组的数量，避免了广播风暴。其次是缩减了控制分组的大小。节点并不发布与所有邻节点相连的链路信息，而只发布与其多点中继选择节点间的链路。OLSR 协议中，每个控制分组都携带有序列号，可以用来区分新旧信息，所以协议不要求按序传输控制分组。协议通过节点周期性的发送 TC 分组来发布 MPR Selector 信息，以帮助其他节点建立到它的路由，并通过周期性的交换信息来维护网络拓扑。网络中的每个节点都保存有到网络中所有可达目节点的路由，因此 OLSR 协议特别适用于网络规模大、节点分布密集的网络。 ### 1.2 OLSR 核心机制 多点中继是 OLSR 协议的核心思想，目的是通过减少同一区域内相同控制分组的重复转发次数来减少网络中广播分组的数量。网络中某一节点 N 的邻居节点被分为两类：MPR 节点和非 MPR 节点。每个节点从其一跳邻居中选择自己的 MPR 集，使得该节点通过这个集合转发的 TC 分组能够覆盖该节点的所有两跳节点。节点 N 的 MPR 集是该节点邻居节点集的子集且满足以下条件：N 的每个两跳邻节点都必须有到达 MPR(N)的双向链路，且节点 N 与 MPR(N)间的链路也是双向的。MPR 集越小，协议性能越好。节点 N 发送的广播分组通过其 MPR 节点转发到达其他节点。而非 MPR 节点只接收控制分组并不转发。协议根据 MPR 集来计算到所有目的地的路由。网络中每个节点周期性的广播它的 MPR Selector 信息。每个节点收到后更新自己到每个已知节点的路由。因此，路由就是通过源到目的节点的 MPR 的逐跳节点序列。 采用 MPR 机制有效的减少了网络内控制分组重发的数量，避免了广播风暴。MRP 下的洪泛机制如下图所示：  图无选择性洪范与选择性洪范 ### 1.3 OLSR 协议运行总图  图 OLSR 协议运行总图 为了对复杂的协议有一个整体上的理解，我绘制了一个协议总图。该图从函数调用层面的大致描绘了整个协议的运行。从图中我们可以看出，OLSR 采用了轮询机制。程序进入主函数后，首先调用一系列初始化函数对协议用到的数据结构进行初始化。初始化完成后，主程序调用 olsr_scheduler 函数进入 scheduler 循环。 在 scheduler 循环中，主程序依次调用 poll_sockets 函数和 walk_timers 函数分别进行消息接收操作和产生操作。当进行消息接收操作时，程序轮询读取多种 socket。当发现可识别 socket，就调用相应的处理函数处理。其中，olsr_input_hello, olsr_input_hello 和 olsr_input_mid 分别处理对应的消息。随后程序会根据之前消息处理的结果更新自己存储的数据结构；当进行消息产生操作的时候，程序调用 walk_timers 函数，并根据到期情况，用指定的函数产生各种消息。其中， generate_hello、generate_tc 和 generate_mid 函数分别产生对应的消息。 除了上图中所列函数。OLSRD 中还存在许多其他的函数实现，比如一组处理终端字符信号 SIGINT 的函数，用于在终端结束程序时，释放 OLSR 程序运行时所产生的资源。限于篇幅，未能一一罗列。 ## 1.4 文件与变量 ### 1.4.1 文件列表 OLSR 代码规模巨大，现将后续代码分析会用到的以及一些重要文件罗列为下表： | 文件 | 内容 | | -------------------------- | ------------------------------------------------- | | lq_packet.h/c | 定义了 OLSR、HELLO、TC 等数据首部以及其他数据结构 | | neighbor_table.h/c | 定义了邻居表和一些相关处理函数 | | two_hop_neighbor_table.h/c | 定义了二跳邻居表和一些相关处理函数 | | mpr_selector_set.h/c | 定义了 MPR Selector 表和一些相关处理函数 | | duplicate_set.h/c | 定义了分组重复信息表和一些相关处理函数 | | tc_set.h/c | 定义了拓扑表和一些相关处理函数 | | routing_table.h/c | 定义了路由表和一些相关处理函数 | | link_set.h/c | 定义了链路信息表和一些相关处理函数 | | lq_mpr.c/h | nMPR 的一些操作 | | mpr.c/h | 1MPR 的一些操作 | | generate_msg.c | HELLO、TC 等消息的生成函数 | | packet.h | 消息数据包结构定义 | | olsr.c | 定义一些全局函数，路由计算更新、错误处理等 | | olsr_cfg.h | 定义一些全局常量 | | olsr_spf.c | spf 树的相关函数 | | process_routes.c | 处理核心路由表 | | process_package.c | 处理 HELLO 消息包 | | schedule.c | 定时器处理 | 变量列表一些重要的全局变量如下表： | 全局变量 | 类型 | 描述 | | -------------------- | -------- | ----------------------- | | olsrport | uint16_t | OLSR 消息发送端口 | | rt_proto | uint8_t | 路由的协议 | | min_tc_vtime | float | TC 消息 vtime 最小值 | | max_tc_vtime | float | TC 消息 vtime 最大值 | | changes_topology | bool | 拓扑消息是否改动 flag | | changes_neighborhood | bool | 邻居表信息是否改动 flag | ### 1.4.2 配置变量 OLSR 路由协议的一些配置变量罗列如下： | 配置变量名 | 描述 | 缺省值 | | ---------------- | ---------------------- | --------------- | | DEF_IP_VERSION | 缺省 IP 协议域 | AF_INET | | DEF_USE_HYST | 缺省消息迟滞 | false | | DEF_LQ_LEVEL | 缺省链路质量等级 | 2 | | DEF_OLSRPORT | 缺省 olsr 端口号 | 698 | | DEF_MIN_TC_VTIME | TC 消息 vtime 最小取值 | 0.0 | | DEF_GW_TYPE | 缺省网关类型 | GW_UPLINK_IPV46 | # 二、OLSR 数据结构 ## 2.1 OLSR 消息结构 ### 2.1.1 消息基本格式 ![](https://www.writebug.com/myres/static/upload