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

1、 快速路由迭代方法的实现 摘 要： 在计算机网络中 每个路由项均必须有其对应的下一跳地址，对于普通的路由来说，其下一跳地址在路由器直连的网段内； 对于 需要 迭代 的路由，其下一跳不在 路由器 的直连网段内。 在转发时 ，必须将此非直连 下一跳 地址做一次或多次迭代处理，以找出一个直连的下一跳地址，从而 进行 二层寻址。 迭代部分大多使用定时器迭代方式， 此方法 定时时间只能根据经验值来选择 ，而迭代 路由需要等待定时 时间后 才可能生效 ， 效率低 。 本课题 提出 一种 快速 路由迭代 的实现 方案 ，基于 实时迭代， 抽象出 邻居 信息 并加以 复用 ，迭代效率 得以 大幅提 升 。 关

2、键词： 路由迭代 ； 静态路由 协议 ； 边界网关协议 ； 邻居 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 directly connected.

3、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 th

4、e 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; Sta

5、tic Routing Protocol; BGP; Neighbour 路由器在 Internet 中起着举足轻重的作用，它是构成 IP 网络的核心，最基本的作用就是连接不同类型的网络，可以智能选择最佳的信息传送线路。路由迭代是路由系统中一个重要 的功能。对于 BGP 路由和静态路由而言，其所携带的下一跳信息可能并不是直接可达，需要找到到达下一跳的直连出口。路由迭代的过程就是通过路由的下一跳信息来找到直连出口的过程。 传统路由迭代方法是定时器路由迭代。定时器路由迭代总体来说就是按一定的时间间隔，循环遍历需要迭代的路由进行重新迭代。定时器时间间隔根据经验设置，也可根据需要修改定时器时间。定时器

6、路由迭代对所有迭代节点进行重新操作。 过大和过小的时间片对于 CPU 的影响都很大，效率低 。 随着网络的大规模发展，路由器的数量成倍的 增长， 网络中 每增加一台路由器，随之而 来 就会带来 IP 地址、路由协议邻居数量、路由表条目 的 增加等问题 。 而定时器每次处理 的 迭代 路由 个数 是 有限 的 ，以免阻塞太久。 迭代路由表项过大会 导致 每次 完成一次 完整 遍历的周期 较长 ， 迭代延时更为明显 。 为了 解决上述问题， 本文 实现一种快速 路由 迭代 的 方法。 1 系统功能结构 作为路由系统 中一个 功能 ， 路由迭代关联到多个模块，路由管理模块与周边模块之间的关系见图 1

7、所示。 路 由 管 理路 由 协 议转 发 表路 由 表协 议 内 路 由 表图 1 路由管理与周边模块关系 路由协议模块包括各路由协议进程，本课题重点研究的是需要迭代的静态路由协议 和 BGP 协议。每个路由协议 往往 对应 路由系统 中的 一个进程。 路由管理对应 系统中的一个核心模块，负责 处理 各协议以及其他 模块 的交互。 每个协议 本地 以及 路由管理都维护了自己的路由表，而 路由器 中的路由表指的是路由管理中的路由表， 该 路由 表 是路由器的控制核心，存放着来自各种路由协议如 OSPF、 BGP 等的路由1。 而 转发 表 是将 路由表 中选择出来的最佳路由附加上相关的转发信息

8、，如 目的地址、 下一跳地址、接口信息等结合在一起的转发信息表。路由器通过转发表来实现对网络包的转发。 路由器使用本地管理路由表来保存协议路由和决策优选路由，并负 责把优选路由下发到 转发表 中， 转发表 指导报文进行转发。这张路由表依据各种路由协议的优先级和度量值来选取 同一 目的地址的不同 路由。 为充分利用 Linux 上对多核 /多 CPU 的支持，提高多核 /多 CPU 环境的路由计算及下刷性能，平台上路由管理模块划分为 3 个常驻线程：路由主线程、路由表线程、同步线程， 3 个线程也对应了 3 个模块 2-3。 路由管理主线程需要处理所有外部输入，包括各种配置管理信息、 响 应 L

9、3VPN 事件等。考虑到大部分外部输入采用 fd 方式提供，主线程采用较新的 epoll 机制，无外部事件时阻塞，有事件时能够多路IO 处理。同 时 epoll 机制采用 ET（边界触发）方式，减少事件触发次数，以提高处理效率 4。主线程接管了所有外部输入，且其他路由线程大部分输入均为路由进程内部因素触发。为实现时间通知机制，其他路由线程则采用 POSIX 线程信号通知机制，通过 sigwait 方式，无信号时阻塞，有信号时逐一处理。如图 2 所示： S t a t i cO S P FI S I S. . .同 步 模 块路 由 表 模 块公 共 接 口图 2 路由管理模块 2 系统关键技术

10、 2.1 两段式存储 NBR（ Neighbour） ， 即邻居。可以作为流量下一站的虚拟节点，也可以是一个 接口 ，也可以是 一个可表达的 下一跳 节点，或者某个接口出发 可达 的下一跳节点。 NBR 包含了 下一条信息，如果是迭代节点，则还会记录保存路由迭代的结果，包括 依赖路由 的概要信息、迭代路径、迭代深度等。 每个 NBR 都有 唯一的 ID， 占用 4 个 字节， 其 构成如 图 3。 0 1 2 3A d d I D4 5 6 7P r o I D0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7I n d e x 图 3 邻居 ID

11、AddID 表示 地址簇，区分 IPV4 和 IPV6； ProID 表示协议 ； Index 表示 NBR 的 索引 ， 24bits，即最大支持 16M 个 NBR； 数据结构在路由快速迭代的实现中至关重要，对路由表采用查找（ Radix 树）和存储（ DB）分离的方式设计。 Radix 树提高了 的 路由表项的查找速度， DB 提高内存分配的速度以及安全性 。 为了提高效率， 节约内存，实现 IPV4/IPV6 地址簇 复用，路由表采用完全二段式的组织方式（ 下一跳 和前缀分离存储） 。 下一跳 信息 采用复用原则单独维护，路有前缀根据地址簇存储到对应的 radix 树 上。复用 的逻辑

12、关系如图 4 所示，其中 ，每个 邻居 的信息 包含了 引用 了 该 邻居 的前缀的 各数。 .P r e f i x 1目 的 地 址 1P r e f i x 2目 的 地 址 2P r e f i x 1 W目 的 地 址 1 WN B R下 一 跳 地 址C o u n t = 1 W依 赖 路 由图 4 邻居复用 关系 从 真实的组网 应用 来看， 路由邻居 个数是非常有限的 ， 而充分利用 复用邻居 是提高路由表的维护 和路由迭代效率的关键。 静态路由协议配置并且优选后的路由以及动态路由协议学习到的路由都统一发给路由管理进行优选。优选后每个路由器中都至少保存着一张路由表和一张路由转

13、发表，路由器决策路由的关键是路由表，而路由表正是由路由管理维护的。每台路由器中都保存着一张由本地管理的路由表，同时各个路由协议也维护着自己的一张自己协议的路由表。 邻居的组织方式为 Radix 树 ， 如图 5， 其外 节点 存储 路由地址 、 掩码 以及其他信息 。此处 的 其他信息 有整条路由 的详细信息 的 指针以及 所有 此相同前缀的链表 的 指针。 只 存储 路由 详细信息的链表 是为了达到存储 与查找分离 的 目的 ，因为很多应用场合是需要查询或者之需要用到前缀 而不用 下一跳。 存储 相同前缀的 链表 的指针也是 为了 同样的目的， 同时 为了 遍历 查找和删除以该前缀 的 路由

14、。 A d d rM a s kp s t I n N o d eu l H a n d l eE x t N o d e下 一 跳 R a d i x 树图 5 邻居的组织 方式 2.2 触发 式 路由迭代 路由迭代是 作为庞大的路由系统 中的 一个重要 功能 ，不 应 从普通路由的 添加、修改、删除等功能独立出来。 实际 的路由系统涉及到的数据结构非常复杂，本论文 大大简化 该部分 ， 突出 系统结构， 旨在 说明快速路由迭代原理 。 以下迭代 过程可 参考图 6。 路 由 表路 由 查 询 树迭 代 树路 由 管 理路 由 表静 态 / B G PP r e f i x N e x t

15、h o p转 发 表图 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 的总是由路由管理创建）。 路

16、由管理创建了空的 NBR 并通知协议。 协议创建空的 NBR，将下一跳信息填充进去并同步给路由管理。 路由管理也将下一跳 1.1.1.1 填充进去，并添加到迭代树。迭代树与路由查询树都是 Radix 二叉树，他们以地址和掩码作为树节点。 然后遍历路由查询树查找以 1.1.1.1 为目的地址的路由。此处用到查找与存储分离技术，因为每个路由表项包含着大量的属性，将目的地址和掩码作为 搜索节点提升搜索速度然后匹配到对应的路由表项。根据最长匹配原则，如果没有匹配到任何表项则迭代失 败。假设匹配到路由表中某 一路由 3.3.3.3/32 4.4.4.4，便将此路由作为依赖路由填充到 NBR 中，由于路由

17、管理中的 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 时，则直接加复用计数并同步给路由管理后直接返回。 而迭代路由的删除需要删除 Pref

18、ix 与 NBR。对于 NBR，如果减一后其复用计数不为零则将复用计数同步给路由管理后直接返回即可，否则删除协议本地的 NBR 并同步删除路由管理中迭代树中对应的NBR 节点。 3 总结 在 实际 应用 中 ， 同一路由系统 中 定时器迭代与触发式迭代 两者是 并存的 。后者 可以实 时响应迭代，从路由表中找出有效的 下一跳 。 但定时器 迭代更全面，比如，当前的迭代路由的依赖路由并 未 激活， 触发式 迭代 便 不会迭代出结果 ， 而 当 该依赖 路由激活 后的 一段时间 内 ，定时器 可以 遍历 到 迭代 树 上 的 该 节点进行迭代。 参考文献 1 吴鲲 , 吴建平，徐恪 . 基于树结构的分布式 BGP 路由计算迭代算法 . 小型微型计算机系统 , 2007. 2 梁志勇 , 徐恪 , 吴建平 , 徐明伟 . 分布式路由器中的路由管理模型 . 清华大学学报 (自然科学版 ) , 2003. 3 王伟 . IP 网络路由管理系统的设计与实现 . 北京邮电大学 , 2010. 4 张超 , 潘旭东 . Linux下基于 EPOLL 机制的海量网络信息处理模型 . 强激光与粒子束 , 2013.