网络协议栈设计与分析

最佳链路状态路由协议(OLSR)分析OptimizedLinkStateRoutingProtocol肖明旺201192191网络1102万宇腾201192280网络1102丁英才201193068网络1101刘伟麟201192308软件11152013-12-22目录组内分工4第一章引言4第二章代码介绍5文件介绍5全局变量52.3配置变量6第三章OLSR部分消息包数据结构73.1OLSR首部73.2HELLO消息包83.3TC消息包9第四章邻居发现94.1节点信息的存储94.2关于节点的具体操作分析114.3邻居表的操作144.3.1邻居表的初始化144.3.2删除节点154.3.3邻居节点的查找与插入174.3.4邻居表的更新184.3.5其他操作18第五章MPR选择195.1MPR节点的添加和清除195.2MPR算法205.2.1olsr_find_2_hop_neighbors_with_1_link函数215.2.2olse_chosen_mpr函数225.2.3olsr_find_maximum_covered函数225.2.4olsr_check_mpr_changes函数235.2.5优化MPR集合24第六章拓扑控制消息洪泛246.1TC消息初始化与删除246.2TC消息处理26第七章路由表的计算267.1主要数据结构分析277.1.1rt_metric和rt_nexthop277.1.2rt_entry277.1.3路由类型287.2路由表计算297.2.1路由表的创建与删除297.2.2最优路径31第八章总结32组内分工项目参与者数据结构部分代码分析万宇腾邻居发现部分代码分析万宇腾、刘伟麟MPR选择部分代码分析刘伟麟TC消息洪泛部分代码分析肖明旺路由计算部分代码分析丁英才论文撰写肖明旺、万宇腾、丁英才、刘伟麟论文汇总肖明旺引言最佳链路状态路由协议(OptimizedLinkStatusRoutingProtocol,OLSR)，是专门为无线移动AdHoc网络提出来的一种标准化的先验式的优化链路状态路由协议。该协议的核心是使用了多点中继站(MPRs)，MPRs是被选择的节点，具有转发网络控制消息的能力。根据协议，每个节点之间周期性的交换控制信息，节点根据协议计算自己的网络拓扑。OLSR向所有节点提供一个最短路径，该技术可以有效减少网络中数据传输的信息量。每一个被邻居们选择的节点在控制信息里周期性的广播这一信息。因此，可以说是由被选择的节点构成了主要的网络。相比经典的链路状态算法，OLSR更适合移动无线局域网。该协议比较适合大型密集的网络。OLSR有以下优点：1利用MPRs来重传控制消息可以减少网络间消息的发送数量。2只需要部分链路状态洪泛就可以获取最佳路径。3网络越大则OLSR可优化的范围就越大也就能得到更好的性能在OLSR协议中，状态路由协议的网络信息状态由被推选的节点(MPR)掌控。所以，优化的一条途径是减少网络中的控制信息。只有被选择的MPR节点才能被用做路由节点，非MPR节点不参与路由计算。MPR可以减少网络中冗余消息的传送。每个节点传送消息给一跳邻居，但是邻居并不能再将此消息传送给其他节点。OSLR协议逐跳寻找路径，每个节点利用本地信息向邻居节点发送路由包来获取路径。由于该协议在设计之初就考虑到协议的分布式工作，所以该协议不依赖于任何的中心，也不需要稳定的的控制信息的传播。每一个节点都周期性的发送信息，这样也保证了一个在可以接受范围内的丢包率。OLSR协议在设计之初就考虑了协议的独立性，因此OLSR协议独立工作于一些协议。它对IP的包格式没有做任何改变，因此，任何IP协议栈都能在协议中正常使用。代码介绍OLSR路由协议共有123个源文件。我们将对部分源文件进行功能型介绍。表格SEQ表格\*ARABIC1OLSR协议部分源文件介绍文件描述确定邻居表的信息lq对olsr,hello,TC数据包以及其他一些数据结构的定义关于MPR的一些操作mpr定义了结构体mpr_selector表示MPR选择源节点的集合neighbor对邻居信息数据结构的定义neighbor对一跳邻居和二跳邻居的处理olsr.c实现一些全局函数，比如网络拓扑结构的计算、路由表的计算与更新和错误处理函数等等olsr定义大部分常量，比如DEF_WILLINGNESS等实现spf树的构造从而实现迪杰斯特拉算法计算路由表routing_table.c路由表的处理TCTC消息的洪泛在olsr路由协议中使用的全局变量有许多，我们在这里只介绍部分重要的全局变量。表格SEQ表格\*ARABIC2OLSR协议部分全局变量介绍全局变量数据类型描述olsrportnit16_tOLSR消息发送接收的端口号rt_protonit8_t路由表计算的所遵循的协议willingnessnit8_tWILL_ALWAYS的邻居节点集合use_hysteresisbool判断消息是否迟滞min_tc_vtimefloatTC消息vtime的最小取值max_tc_vtimefloatTC消息vtime的最大取值max_jitterfloat消息传播的最大抖动changes_topologybool判断拓扑信息是否变化changes_neighborhoodbool判断邻居信息是否变化表格SEQ表格\*ARABIC3OLSR路由协议配置名称描述默认值DEF_IP_VERSIONDEF_USE_HYSTDEF_LQ_LEVELDEF_OLSRPORTDEF_MIN_TC_VTIMEDEF_GW_TYPEDEF_DOWNLINK_SPEEDMAX_LQ_LEVELMIN_LQ_LEVELDEF_RTPROTO缺省ip协议域缺省消息迟滞缺省链路质量等级缺省olsr端口号TC消息vtime最小取值缺省网关类型缺省的链路下载速度缺省链路质量最高等级缺省链路质量最高等级缺省的路由协议AF_INETFalse2698GW_UOLINk_IPV461024kb/s200MAX_TTLMAXJITTER定义ttl最大值Olsr消息传播最大抖动HELLO_INTERVAL/4COOKIE_ID_MAX系统cookie数量最大值25MAXMESSAGESIZE广播数据包大小的最大值1500kbOLSR_LINK_JITTEROLSR_LINK_HELLO_JITTEROLSR_LINK_SYM_JITTEROLSR_LINK_LOSS_JITTERolsr消息抖动时间HELLO消息抖动时间系统抖动时间数据包丢失抖动时间5s0s0s0sOLSR部分消息包数据结构OLSR使用统一的数据包格式，使用UDP通信，数据包嵌入到UDP数据报在网络上传输。每个数据包封装一个或多个消息，邮件分享通用报头格式，使节点能够正确接收和重传一个未知类型的消息。如果数据包不包含任何信息（数据包的长度小于或等于该数据包报头的大小），数据包就会默默的丢弃。每一个消息都会分配一个唯一的标识号，用来确保消息不重传。OLSR数据包一般包含以下几部分:消息类型,VTIME邮件大小,发端地址,生存时间,跳数,消息序列号和消息。其中VTIME是表示接收后很长时间节点如何，确保数据包中的消息有效；生存时间包含最大跳数，如果被重发，则减1；消息序列号被用来确保给定的消息被节点转发的次数不超过一次。OlsrOlsrolsr_common是OLSR协议基本数据包。其中包含以下几部分:type，消息类型；vtime,表示接收后很长时间节点如何，确保数据包中的消息有效；size，消息大小；orig，发端地址；ttl，跳数，消息在传递过程中最大跳数，每转发一次，ttl减1；hops，此消息在传递过程中经历的跳数；seqno，消息的序列号，这是唯一不变的，以确保消息不回被重发。表格SEQ表格\*ARABIC4OLSR协议数据包PacketLengthPacketSequenceNumberMessageTypeVtimeMessageSizeOriginatorAddressTimeToLiveHopCountMessageSequenceNumberMESSAGEOlsrOlsrHELLO用于建立一个节点的邻居表，其中包括邻居节点的地址以及本节点到邻居节点的延时和开销，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，链路的质量。OlsrOlsrTC分组数据包必须通过MPR节点传递消息被广播到全网中，用以维护网络的拓扑信息、确保链路时刻连通状态和更新路由表集。lq_TC_message是封装后的拓扑数据包格式。from：接受包的上一个节点地址；ansn：节点接受到消息时拓扑集合会被更新。OlsrOlsr-TC_message是TC消息数据包格式。邻居发现邻居发现是基于节点的邻居信息库，通过HELLO消息的传播实现。邻居信息库包含关于邻居、2跳邻居、MPRs和MPR的信息。4.1节点信息的存储每个节点都存储自身的信息在结构体link_entry中。Olsr-link_set.hOlsr-link_set.h00059-00060：local_iface_addr存储该节点接口ip地址，neighbor_iface_addr存储邻居节点ip地址。00067：neighbor以链链表形存储邻居节点信息。邻居节点具体信息如下：Olsr-neighbor_table.hOlsr-neighbor_table.hneighbor_entry结构体，同来存储邻居节点的信息。记录了邻居节点的主地址，状态，作为MPR的willingnessz值，是否是MPR，是否曾是MPR,覆盖的两跳邻居节点的数量，及节点连接链路的数量以及指向neighbor_2_list连表的指针。其中，成员变量was_mpr用来发现MPR的变化。Olsr-neighbor_table.hOlsr-neighbor_table.h这段代码定义了neighbor_2_list_entry结构体，这是用来存储邻居节点信息，两跳邻居节点信息以及记录有效时间的链表结构。mid_address存储本节点的其他接口ip地址。其中mid_entry节点链路信息。mid_entry包含节点主地址，上一节点和下一节点链路，同时还有本节点链路中其他端口信息存储在aliases链表中。4.2关于节点的具体操作分析OlsrOlsr-函数功能：重置所有节点信息。00095-00103：遍历所有节点一遍，把所有信息置为初始值，并把邻居节点也设为空值。OlsrOlsr-函数功能：通过查找main_addr(184-185行)找到节点link_entry,通过lookup_link_status找出节点链路状态。判断其是否是对称状态。00197-00206：行是查找主地址并找出节点上的其他端口ip判断该节点其他端口aliases链路状态。并判断该ip地址所在的链路状态是否是对称状态。只返回对称链路的信息。OlsrOlsr-函数功能：查找端口ip地址的最少跳数邻居，并返回该节点信息link_entry；首先定义了三个link_entry结构walker，good_link,backup_link；00223-00229：找出该节点的主地址，通过遍历walker链表，查找出跳数最少的邻居，这就是最新的邻居表信息，最短的邻居表。OlsrOlsr-函数功能：删除节点链路上所有的信息。定义拓扑边缘节点TC_edge：通过邻居端口地址找出TC_edge边缘链路。00365-00369：删除边缘链路spf；00372-00377：删除邻居链路信息，存储在hash表中的链路表删除；00379-00394：清空一些正在计时的属性，同时释放link的资源空间；同时将change_neighborhood设置为true，让其他节点更新自己的链路状况，发送hello消息包及时更新邻居表的信息。OlsrOlsr-函数功能：更新链路信息状态，通过hello_message来更新邻居节点的信息。00694-00699：如果该节点不在链路中，把它加入到链路中去，并将计时器更新；00708-00732：通过check_link_status同过发送hello_message发现该节点的邻居节点链路状态link_type，对不同的状态采取不同的操作：00708-00718：如果是对称或者非对称的需将定时器重新设置，更新定时器；00732：更新邻居节点的状态信息，是对称还是非对称。OlsrOlsr-函数功能：发送Hello消息，维护一个端口的邻居信息。00780-00797：发送hello_message来维护端口信息，直到消息到达端口的所有的邻居节点，就停止发送，则该端口的所有邻居节点链路都检查完毕。4.3邻居表的操作Olsr-neighbor_table.cOlsr-neighbor_table.c函数功能：初始化邻居表。00061-00064：将每一个邻居表neighortable[i]初始化为指向自身的仅有一个节点的链表。Olsr-neighbor_table.cOlsr-neighbor_table.c函数功能：删除释放一个两跳邻居节点记录。00073-00077：获取两跳邻居节点记录中nbr2_list中的邻居节点结构体nbr和两跳邻居节点结构体nbr2；00079-00082：释放两跳邻居节点结构体nbr2的空间；00087-00088：将两跳邻居节点记录中的计时器置为空；00096-00097：通过将全局变量changes_neighborhood,changes_topology置为真，通知网络重新计算MPR集合和路由表。Olsr-neighbor_table.cOlsr-neighbor_table.c函数功能：将从两跳邻居节点信息中，根据给定的邻居节点地址删除对应的两跳邻居节点。00111-00113：获取邻居节点的两跳邻居节点信息表；00115-00121：遍历邻居节点的两跳邻居及节点信息表，直到找到信息表中两跳邻居节点与给定的两跳邻居节点相同，则删除该两跳邻居节点并返回1，表示成功删除；否则返回0表示没有删除。Olsr-neighbor_table.cOlsr-neighbor_table.c函数功能：删除邻居节点信息表（及连带的两跳邻居节点信息表）00177-00182：寻找邻居节点信息表entry。00189-00197：删除邻居节点信息表即连带的两跳邻居节点信息表。Olsr-neighbor_table.hOlsr-neighbor_table.h函数功能：查找给定邻居节点，能否通过该节点连接到一个给定的两跳邻居节点地址。00140：定义返回值entry,用来记录找到的两跳邻居节点信息表结构体。00142-00147：遍历邻居节点的两跳邻居节点信息表，如果找到信息表中存在两跳邻居节点的两跳邻居节点ip地址匹配给定的两跳邻居节点地址，怎返回该两跳邻居节点信息表结构体。否则，返回空指针。Olsr-neighbor_table.cOlsr-neighbor_table.c函数作用：在邻居节点信息表中插入一条邻居节点信息。如果已存在返回0，否则返回1。00226-00230：检查邻居节点信息表中是否存在要添加的邻居节点信息；00237-00249：添加邻居节点信息并设置内部的地址，willingness，状态等变量的初始化。Olsr-neighbor_table.cOlsr-neighbor_table.c函数功能：更新邻居信息表中的状态为参数link。00306-00322:如果将连接状态置为SYM_LINK时，如果原来是NOT_SYM则通知网络重新进行MPR选举和路由表更新并删除通过这个邻居节点连接到的两跳邻居节点；00323-00333：否则，如果之前状态为SYM_LINK则通知网络重新进行MPR选举和路由表更新。针对邻居表的操作有许多。比如，olsr_expire_nbr2_list函数的作用是回调两跳邻居节点信息表计时器，olsr_print_neighbor_table函数的作用是打印邻居节点信息表，等等。这里就不详细介绍。MPR选择MPRs用于把节点的信息传播出去且减少区域内信息重传，因此MPR是经典洪泛算法的一种优化。每个节点在对称一跳链接里独立的选择它的MPRs集合。与MPRs的链接会把在HELLOmessage里的链接类型的MPR_NEIGH替换为SYN_NEIGH。OlsrOlsr-函数作用：添加willingness为WILLALWAYS的邻居节点到MPR集合中。00366-00378：首先将非对称的邻居节点或是不是WILL_ALWAYS的邻居节点忽略，然后将剩余的节点a_neighbor添加到mpr中，并返回添加节点的数量count。OlsrOlsr-函数作用：将被选为MPR节点的记录清除。00245-00248：如果节点a_neighbor的ismpr值为真的话，那么就将其置为假代表其不是mpr节点，同时将was_mpr置为真，代表该邻居节点曾经被选为mpr。00251-00255：遍历邻居节点a_neighbor覆盖的两跳邻居节点的数量置为0。5.2MPR算法符号定义N(m)节点M的邻居集合，对称邻居节点集合。N2(m)1节点M的两跳邻居集合，除去仅能通过转发意愿N_willingness等于WILL_NEVER的邻居节点到达的两跳邻居2除去节点自己，除去对称邻居节点剩下的两跳邻居构成N2(m)D(m)1m的一跳网路的深度被定为m的对称邻居的数目2不包括N里的任何成员3不包括自己OLSR路由协议于传统的链路状态路由算法最显著的区别在于MPR的引入。MPR选举机制在全网有效地扩散拓扑信息的同时，大大降低了路由控制信息的洪泛规模。MPR的选举原则是MPR为对称邻居节点，通过选出的MPR可以到达所有的两跳邻居节点，并且选出MPR个数尽可能少。一个节点的意愿可以被设置为从0-7中的整数，其中N_willingness表示意愿的值，WILL_ALWAYS表面一个节点总是选择执行代表其他交通节点。5656432103891112112354330为节点M的两跳邻居节点

为节点一跳邻居节点10117121098图图SEQ图\*ARABIC1MPR选举_find_2_hop_neighbors_with_1_link函数OlsrOlsr-函数功能：查找存在一条连接的两跳邻居节点链表。定义了两个两跳邻居节点链表（two_hop_temp,two_hop_list）,前者用来作为函数的返回值。dup_neighbor用来记录在邻居节点集合中已经存在的邻居节点，而two_hop_neighbor是用来记录一个两跳邻居节点的局部变量。00096-00136:遍历两跳邻居表two_hop_neighbortable；000105-00106：寻找在邻居表中已经存在的的邻居地址neighbor_2_addr；00117-00122：如果存在，并且该邻居节点与本节点不是非对称的节点忽略；001168-00136：如果不存在并且该两跳邻居节点只有一个邻居节点，那么将两跳邻居节点添加到两跳邻居节点链表two_hop_list中。_chosen_mpr函数OlsrOlsr-函数功能：用来处理已经选定的MPR节点，以及对MPR的计时器的更新，函数的返回值是一条邻居中MPR的数量。00158-00202：对second_hop_entries进行遍历；00164-00168：将已经存在的于邻居节点的节点忽略；00176-00178：将两跳邻居节点被覆盖的MPR的数量mpr_covered_count递增一，同时将两跳邻居节点的邻居节点赋给the_one_hop_list；00185-00187：如果两跳节点的mpr的数量多于全局变量olsr_cnf的mpr_coverage,那么就要将count的数量增加一。函数的最后返回count值。olsr_find_maximum_covered函数OlsrOlsr-函数作用：找到能够覆盖到最多两跳节点的MPR。00224-00229：如果a_neighbor不是mpr,同时覆盖两条节点数量值maximum小于a_neighbor邻居节点的股该节点的数量，那么将maximum值更新，并且将a_neighbor作为候选的MPR节点。_check_mpr_changes函数OlsrOlsr-函数作用：通过遍历所有的mpr节点，返回值是1时代表节点是否是mpr的状态发生过变化，如果是0则代表没有发生变化。00275-00281：对于邻居节点a_neighbor如果它曾经是mpr,但是现在又不是mpr,那么说明它的mpr的状态发生变化，将retval置为1，否则返回retval默认值0。Olsr-mpr.cOlsr-这段代码来自olsr_optimize_mpr_set函数。00474-00509：如果覆盖两跳邻居的mpr数量的值小于全局变量olsr_cnf->mpr_coverage的值，那么就不需要移除，否则该mpr是冗余的，被除去。拓扑控制消息洪泛拓扑控制消息即TC消息，其数据包格式在前面已有介绍，故在此不再赘述。拓扑控制消息的洪泛有着十分重要的意义，每个被选为MPR的节点向网络中所有节点广播TC消息，节点根据“缺省的路由转发算法”转发TC消息。Olsr-TCOlsr-TC函数功能：初始化TC消息。00195-00203：对TC消息的初始化，从cookie中获取相应的值为为TC消息集合的属性赋值；000208：添加已配置好的TC消息到本地节点的TC消息集合。Olsr-TCOlsr-TC函数功能：删除TC消息。00289-00292：若宏定义LINUX_NETLINK_ROUTING条件，则删除网关信息。其中网关的删除操作需要对网关协议(IPv4或IPv6)、网关信息是否为空以及网关信息保存时间是否为空进行判断；00296：删除本地的路由表；00307-00311：将timers参数都设置为空，保证数据和设置的彻底删除；00313-00314：从本地TC消息集合中删除该TC消息，并将TC消息链表的阻塞解除。当节点接收到TC消息时，只关心其消息类型。Olsr-TCOlsr-TC由00820-00824可知，TC消息接收者在接受消息时会判断发送者接口信息，若发送者并非是对称一跳邻居，那么该包将会被丢弃。Olsr-TCOlsr-TC如果该消息中的msg_seq和外部变量msg_seq相等且ignored变量小于32，则代表该消息已经处理过，应该忽视。路由表的计算每一个节点都会维护一个路由表用于发送信息。这些路由信息来自于在网络拓扑之上的本地链路信息。因此任一个节点的变动都会引起整个网络拓扑的变化继而影响每个节点维护的路由表的变化。每一条路由信息都包含信息目的地址、下一跳地址、总跳数、下一跳接口地址。但是在没有路由的节点或者只知道部份信息的节点不包含在路由表内。具体来说，当发生以下变化的时候，节点的路由表信息才回发生变化：链路集改变、邻居集改变、两跳邻居集改变、网络拓扑集改变、信息库多点接入改变。在计算X节点的路由的时候使用最小路径算法：1移除所有路由信息；2添加所有对称邻居信息，然后把每一个邻居信息的状态N_status=SYM，把邻居信息添加到路由列表中，其中R_dest_addr =L_neighbor_iface_addrR_next_addr =L_neighbor_iface_addrR_dist=1R_iface_addr =L_local_iface_addr7.1主要数据结构分析_metric和rt_nexthopOlsr00067-00070:在路由选择的时候使用的复合矩阵，其中包括两个路由点之间的花销或者跳数。00073-00076:该结构体包含下一跳的网关（IPv4或者IPv6）与接口索引。7.1.2rt_entry每一个RIB节点都会有一个路由的接口，这个接口很重要，里面包含了最佳路径的下一个网关信息，而且是rt_path的根，同样也包含了一个在所有路由信息里的一个最好的路径。rt_dst包含了该信息的路由地址与前缀长度。rt_tree_node包含了val_tree的一些信息。如下：Olsr-avl.h(common)Olsr-avl.h(common)00052-00061:该结构体里面包含了父亲节点子节点左右节点等等表示一棵树的信息，值。rt_best是所有路径中的最佳路径，结构如下：7.1.3路由类型olsr协议中有三种路由类型，INT类型的是有TC-Message发出的，而MID类型是从HNA路由器得到的MID-message。Olsr-Routing_table.cOlsr-Routing_table.c函数功能：创建一个可用的路由表入口，对于提供的参数IP前缀分配一个路由表入口空间，并做一些相应的初始化并把该入口插入到avl树里。00234-00239申请内存空间并把空间内清零；00241-00245标识该入口为新分配入口并把该入口的目的地址设置成为参数提供的入口地址；00247-00253把入口的树节点插入到整个路由表中并初始化树。Olsr-Routing_table.cOlsr-Routing_table.c函数功能：从avl树里面找到一个地址的路由表入口，根据参数地址并配上设置里的最长前缀长度在avl树里调用avl_find函数从routingtree里面找到该地址的rt_enty。00197-00201配置要查找的变量；00203-00205从在routingtree里找到该地址的位置并返回该节点，如果节点不为空则调用rt_tree2rt函数把返回节点转化为et_entry类型，否则返回空。Olsr-Routing_table.cOlsr-Routing_table.c函数功能：对于每个给予的rt_path创建一个路由入口并且把它加入到全局的RIB树里面。00295-00310创建参数变量并检查参数是否符合要求，如果传入的tc_entry为ROUTE_COST_BROKEN或者传入的rtp的目的地址长度大于所设置的最大地址长度则直接返回；00315-00328检查传入的rtp的节点是否在路由表中，如果节点不在路由表的avl树中则重新分配一个节点，在的话就把节点类型从avl_node