毕业论文——快速路由迭代方法的实现

快速路由迭代方法的实现摘 要：在计算机网络中每个路由项均必须有其对应的下一跳地址，对于普通的路由来说，其下一跳地址在路由器直连的网段内；对于需要迭代的路由，其下一跳不在路由器的直连网段内。在转发时，必须将此非直连下一跳地址做一次或多次迭代处理，以找出一个直连的下一跳地址，从而进行二层寻址。迭代部分大多使用定时器迭代方式，此方法定时时间只能根据经验值来选择，而迭代路由需要等待定时时间后才可能生效，效率低。本课题提出一种快速路由迭代的实现方案，基于实时迭代，抽象出邻居信息并加以复用，迭代效率得以大幅提升。关键词：路由迭代；静态路由协议；边界网关协议；邻居Abstract: In computer networks, each route entry must have the corresponding nexthop address. For ordinary route, its nexthop address is in the router directly connected network segment. For a route requiring recursion, its nexthop address is not directlyconnected. During route forwarding, this non-directly connected nexthop address must be recursion-processed once or several times to find out a directly connected nexthop address to enable Layer2 path searching. Most of recursive routing using the timer, time can only be selected according to experience and the recursive routing may need to wait until timer time to take effect, which has low efficiency. This paper proposes a fast and real-time based recursive routing implementation. It abstract and reuse neighbor information, recursive efficiency can be greatly improved.Key words: Recursive Routing; Static Routing Protocol; BGP; Neighbour路由器在Internet中起着举足轻重的作用，它是构成IP网络的核心，最基本的作用就是连接不同类型的网络，可以智能选择最佳的信息传送线路。路由迭代是路由系统中一个重要的功能。对于BGP路由和静态路由而言，其所携带的下一跳信息可能并不是直接可达，需要找到到达下一跳的直连出口。路由迭代的过程就是通过路由的下一跳信息来找到直连出口的过程。传统路由迭代方法是定时器路由迭代。定时器路由迭代总体来说就是按一定的时间间隔，循环遍历需要迭代的路由进行重新迭代。定时器时间间隔根据经验设置，也可根据需要修改定时器时间。定时器路由迭代对所有迭代节点进行重新操作。过大和过小的时间片对于CPU的影响都很大，效率低。随着网络的大规模发展，路由器的数量成倍的增长，网络中每增加一台路由器，随之而来就会带来IP地址、路由协议邻居数量、路由表条目的增加等问题。而定时器每次处理的迭代路由个数是有限的，以免阻塞太久。迭代路由表项过大会导致每次完成一次完整遍历的周期较长，迭代延时更为明显。为了解决上述问题，本文实现一种快速路由迭代的方法。1 系统功能结构作为路由系统中一个功能，路由迭代关联到多个模块，路由管理模块与周边模块之间的关系见图1所示。图1路由管理与周边模块关系路由协议模块包括各路由协议进程，本课题重点研究的是需要迭代的静态路由协议和BGP协议。每个路由协议往往对应路由系统中的一个进程。路由管理对应系统中的一个核心模块，负责处理各协议以及其他模块的交互。每个协议本地以及路由管理都维护了自己的路由表，而路由器中的路由表指的是路由管理中的路由表，该路由表是路由器的控制核心，存放着来自各种路由协议如OSPF、BGP等的路由1。而转发表是将路由表中选择出来的最佳路由附加上相关的转发信息，如目的地址、下一跳地址、接口信息等结合在一起的转发信息表。路由器通过转发表来实现对网络包的转发。路由器使用本地管理路由表来保存协议路由和决策优选路由，并负责把优选路由下发到转发表中，转发表指导报文进行转发。这张路由表依据各种路由协议的优先级和度量值来选取同一目的地址的不同路由。为充分利用Linux上对多核/多CPU的支持，提高多核/多CPU环境的路由计算及下刷性能，平台上路由管理模块划分为3个常驻线程：路由主线程、路由表线程、同步线程，3个线程也对应了3个模块2-3。路由管理主线程需要处理所有外部输入，包括各种配置管理信息、响应L3VPN事件等。考虑到大部分外部输入采用fd方式提供，主线程采用较新的epoll机制，无外部事件时阻塞，有事件时能够多路IO处理。同时epoll机制采用ET（边界触发）方式，减少事件触发次数，以提高处理效率4。主线程接管了所有外部输入，且其他路由线程大部分输入均为路由进程内部因素触发。为实现时间通知机制，其他路由线程则采用POSIX线程信号通知机制，通过sigwait方式，无信号时阻塞，有信号时逐一处理。如图2所示：图2路由管理模块2 系统关键技术2.1两段式存储NBR（Neighbour），即邻居。可以作为流量下一站的虚拟节点，也可以是一个接口，也可以是一个可表达的下一跳节点，或者某个接口出发可达的下一跳节点。NBR包含了下一条信息，如果是迭代节点，则还会记录保存路由迭代的结果，包括依赖路由的概要信息、迭代路径、迭代深度等。每个NBR都有唯一的ID，占用4个字节，其构成如图3。图 3邻居IDAddID表示地址簇，区分IPV4和IPV6；ProID表示协议；Index表示NBR的索引，24bits，即最大支持16M个NBR；数据结构在路由快速迭代的实现中至关重要，对路由表采用查找（Radix树）和存储（DB）分离的方式设计。Radix树提高了的路由表项的查找速度，DB提高内存分配的速度以及安全性。为了提高效率，节约内存，实现IPV4/IPV6地址簇复用，路由表采用完全二段式的组织方式（下一跳和前缀分离存储）。下一跳信息采用复用原则单独维护，路有前缀根据地址簇存储到对应的radix树上。复用的逻辑关系如图4所示，其中，每个邻居的信息包含了引用了该邻居的前缀的各数。图 4邻居复用关系从真实的组网应用来看，路由邻居个数是非常有限的，而充分利用复用邻居是提高路由表的维护和路由迭代效率的关键。静态路由协议配置并且优选后的路由以及动态路由协议学习到的路由都统一发给路由管理进行优选。优选后每个路由器中都至少保存着一张路由表和一张路由转发表，路由器决策路由的关键是路由表，而路由表正是由路由管理维护的。每台路由器中都保存着一张由本地管理的路由表，同时各个路由协议也维护着自己的一张自己协议的路由表。邻居的组织方式为Radix树，如图5，其外节点存储路由地址、掩码以及其他信息。此处的其他信息有整条路由的详细信息的指针以及所有此相同前缀的链表的指针。只存储路由详细信息的链表是为了达到存储与查找分离的目的，因为很多应用场合是需要查询或者之需要用到前缀而不用下一跳。存储相同前缀的链表的指针也是为了同样的目的，同时为了遍历查找和删除以该前缀的路由。图 5邻居的组织方式2.2触发式路由迭代路由迭代是作为庞大的路由系统中的一个重要功能，不应从普通路由的添加、修改、删除等功能独立出来。实际的路由系统涉及到的数据结构非常复杂，本论文大大简化该部分，突出系统结构，旨在说明快速路由迭代原理。以下迭代过程可参考图6。图 6快速路由迭代快速路由迭代过程，以添加一条迭代路由为例：当静态路由配置一条路由，目的地址/掩码为2.2.2.2/24，原始下一跳为3.3.3.3。当下一跳3.3.3.3不在此路由的直连网段内，此时就需要通过一次或者多次迭代找到路由直连的下一跳。二段式存储，先将路由分成前缀和下一跳两部分，然后抽象成Prefix和NBR两个结构。查找协议本地有没有注册过以3.3.3.3为下一跳的NBR，假设这是第一次添加以3.3.3.3为下一跳的路由，则协议内没有此NBR的信息，则向路由管理申请创建（为了统一管理，NBR的总是由路由管理创建）。路由管理创建了空的NBR并通知协议。协议创建空的NBR，将下一跳信息填充进去并同步给路由管理。路由管理也将下一跳1.1.1.1填充进去，并添加到迭代树。迭代树与路由查询树都是Radix二叉树，他们以地址和掩码作为树节点。然后遍历路由查询树查找以1.1.1.1为目的地址的路由。此处用到查找与存储分离技术，因为每个路由表项包含着大量的属性，将目的地址和掩码作为搜索节点提升搜索速度然后匹配到对应的路由表项。根据最长匹配原则，如果没有匹配到任何表项则迭代失败。假设匹配到路由表中某一路由3.3.3.3/32 4.4.4.4，便将此路由作为依赖路由填充到NBR中，由于路由管理中的NBR变化，此时需要并同步给协议。协议将依赖路由的信息填充至本地。如果经过该依赖路由的出接口到达的下一跳4.4.4.4是与本路由器直连的下一跳，则将NBR复用计数加一并同步给路由管理，至此迭代过程结束，2.2.2.2/24 3.3.3.3的真实下一跳为4.4.4.4。否则需要以4.4.4.4作为原始下一跳进行第二次迭代，跳转至步骤a，以此类推，直至找出直连的下一跳和出接口。如再配一条路由8.8.8.8/24 3.3.3.3，此时查到本地有3.3.3.3对应的NBR时，则直接加复用计数并同步给路由管理后直接返回。而迭代路由的删除需要删除Prefix与NBR。对于NBR，如果减一后其复用计数不为零则将复用计数同步给路由管理后直接返回即可，否则删除协议本地的NBR并同步删除路由管理中迭代树中对应的NBR节点。3 总结在实际应用中，同一路由系统中定时器迭代与触发式迭代两者是并存的。后者可以实时响应迭代，从路由表中找出有效的下一跳。 但定时器迭代更全面，比如，当前的迭代路由的依赖路由并未激活，触发式迭代便不会迭代出结果，而当该依赖路由激活后的