（通信与信息系统专业论文）isis多拓扑路由在路由器上的设计与实现.pdf

中文摘要 摘要： 多拓扑路由是近几年提出的一种智能路由方案，与基于目的地址路由和基于 策略路由方案不同，多拓扑路由根据流量类型动态的选择路由，利用i p 报文中的 d s c p ( 差分服务代码点) 、n b a r ( 网j 络的应用程序识别) 等字段区分不同的业务类 型，为每种业务类型独立创建子拓扑，每个子拓扑独立进行路径选择和路由转发 来实现动态路由。这种新的路由思想为解决负载均衡、流量工程和网络安全提供 了新的视角。 i s i s 路由协议( 中间系统到中间系统路由协议) 是当今硕果仅存的两大链路状 态内部网关路由协议，具有收敛速度快，易于扩展的特性，在欧洲各大电信运营 商中应用十分广泛。本文在深入理解i s i s 路由协议的基础上，依据r f c 5 1 2 0 在 h 3 c 路由器上设计和实现i s i s 多拓扑路由功能，最后提出i s i s 多拓扑路由的一些 优化方案，并在路由器上仿真验证，论文主要工作包括： 1 ：在深入了解i s o 标准组织对i s i s 邻居模块如何实现的前提下，提出多拓扑 邻居状态机模型，简化邻居处理流程和增加了模块可扩展性；并对广播网中指定 路由器选举方案进行优化 2 ：设计和实现多拓扑路由l s p ( 链路状态数据报文) 模块，提出了多拓扑l s p 存储优化方案 3 ：在深入介绍i s p f ( 增量最短路径优先算法) 路由计算的前提下，提出了一种 多拓扑路由计算存储的优化方案 4 ：对h 3 c 路由器软件平台进行改进，设计并实现了一套多拓扑路由计算测试 平台，并在此平台上对两种多拓扑路由计算方案进行验证 关键词：多拓扑路由；i s i s ；i s p f ；路由计算 分类号：t p 3 9 3 t r a bs t r a c t a b s t r a c t ：m u l t i - t o p o l o g yr o u t i n gi sp r o p o s e di nr e c e n ty e a r s ，i ti s a ni n t e l l i g e n t r o u t i n gp a r a d i g m c o m p a r e dt o t h ed e s t i n a t i o n - b a s e dr o u t i n gp a r a d i g ma n dt h e p o l i c y - b a s e dr o u t i n gp a r a d i g m ，m u l t i - t o p o l o g yr o u t i n gd y n a m i c a l l ys e l e c tr o u t i n gp a t h b a s e do nt h et y p eo ft r a f f i c i tm a p sac e r t a i ns u b t o p o l o g yt ot h es a m eu n d e r l y i n g p h y s i c a li n f r a s t r u c t u r eb a s e do na t t r i b u t e ss u c ha sd s c p n b a r e t c e a c hs u b t o p o l o g y o w n sa l o g i c a lp a t hw h i c hm e a n se a c ht o p o l o g yw i l lr o u t eas u b s e to ft r a f f i ca n ds e l e c t m u t i n gp a t hi n d e p e n d e n t l y t l l i sn e wp a r a d i g ms u p p l i e sa n o t h e rw a yt os o l v es o m e n e t w o r kp r o b l e m ss u c ha sl o a db a l a n c i n gr o u t i n g ，t r a f f i ce n g i n e e r i n ga n dn e t w o r k s e c u r i t ye t c n o w a d a y s ，i s i sr o u t i n gp r o t o c o li so n eo ft h et w or e m a i n i n gl i n ks t a t ei n t e r i o rg a t e w a y m u t i n gp r o t o c o l ，i ti sa l le x c e l l e n tr o u t i n gp r o t o c o lw h i c hh a sa r i c h e rs e to fe x t e n s i o n s a n ds p e e do fc o n v e r g e n c eu s e db ym a n yi n t e r a c ts e r v i c ep r o v i d e r s ( i s p s ) r e c e n t l y 1 f 1 1 e m a i nc o n t e n to ft h i st h e s i si st h a ti td e s c r i b e dt h ed e s i g na n di m p l e m e n t a t i o no fi s i s m u l t i t o p o l o g yi nh 3 c r o u t e ra c c o r d i n gt or f c 512 0 ，t h em a i nc o n t e n to ft h i st h e s i si s a sf o l l o w s ： 1 ：p r o p o s e di s i sm u l t i - t o p o l o g yr o u t i n gn e i g h b o rs t a t em a c h i n em o d e l ，w h i c hg r e a t l y s t r e a m l i n et h e n e i g h b o rp r o c e s s e s a n di n c r e a s e n e i g h b o r m o d u l e s c a l a b i l i t y ； o p t i m i z a t i o nt h ep r o c e s so fd e s i g n a t e di n t e r m e d i a t es y s t e me l e c t i o n 2 ：d e s i g na n di m p l e m e n t a t i o no fm u l t i - t o p o l o g yr o u t i n gl s p m o d u l e s 3 ：p r o p o s e da ni s i sm u l t i - t o p o l o g yr o u t ec a l c u l a t i o ns c h e m e ，a n ds i m u l a t e dt h es c h e m e u n d e rh 3 cr o u t e r k e y w o r d s ：m u l t i t o p o l o g yr o u t i n g ；i s i s ；i s p f ；r o u t i n gc a l c u l a t i o n c i 。a s s n o ：t p 3 9 3 致谢 本论文的工作是在我的导师陈常嘉教授的悉心指导下完成的，陈常嘉教授严 谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢三年来 陈常嘉老师对我的关心和指导。 感谢华为三康公司的魏志广老师，作为华为三康公司i s i s 路由协议的资深专 家，魏老师对我论文的研究方案上提出了很多有益的建议；感谢华为三康公司张 蓓老师，作为项目的i s i s 设计负责人，她对我在华为三康公司完成项目以及论文 撰写提供了很多帮助；感谢张立忠老师，作为项目经理，他对我论文的选题和研 究方向提供了很多有益的建议，促使我对i s i s 多拓扑路由存储优化方案的思考。 此外，我还要感谢在实验室工作及撰写论文期间，魏巍、赵瑞敏等同学在我 论文撰写期间，一起研究讨论，在此向他们表达我的感激之情。 另外也感谢我的家人，他们的理解和支持使我能够在学校专心完成我的学业。 1 引言 随着互联网的蓬勃发展，作为网络之间联系枢纽的路由器开始彰显其核心地 位，而一个可靠和可扩的路由协议是路由器正常工作的关键因素。i s i s 路由协议 就是当今硕果仅存的两大内部网关链路状态路由协议。相比于o s p f 路由协议，i s i s 路由协议具有收敛速度快、易于扩展、维护简单等优良特性，使其在各大电信运 营商中应用十分广泛。 众所周知，近十年来互联网以一种难以置信的速度飞速发展，网络中各种业 务不断增多，如何保证不同业务获得很好的服务质量，并使得网络的利用率达到 最大一直是互联网研究的重要研究方向。随着研究的不断深入，现在有很多解决 方案，如策略路由、访问控制列表和m p l s 等。 相比较于上述解决方案，多拓扑路由是一种新的路由思路，有别于基于目的 地址和基于策略的路由思路，它可以根据流量类型动态的选择路由。多拓扑路由 方案根据网络业务类型分另u t g , j 建子拓扑，每个子拓扑独立进行路径选择和数据转 发，子拓扑之间互相独立。多拓扑路由为负载均衡、流量工程和网络安全提供了 新的解决方案。 1 1课题背景 本课题来源于实验室同h 3 c 公司的合作开发项目“c o m w a r e v 5 0 0 ri s i sm t r 的设计与实现，主要研究i s i s 多拓扑路由在h 3 c 路由器上的设计与实现。 众所周知，路由协议创建路由表，描述网络拓扑结构；并协同路由器一起执 行路由选择和数据包转发功能。一个优秀的路由协议应该具备收敛速度快、可靠 性好以及扩展性强等特点，并能随着网络发展而不断发展。i s i s 正是这样的一个 链路状态路由协议，它通过h e l l o 报文建立和维护同相邻路由器的邻居关系；通过 l s p 报文构建全局网络拓扑；根据全局网络拓扑进行最短路径优先路由计算得到 最佳路由。 i s i s 协议报文是基于t l v 格式的，可扩展性很强。多拓扑路由根据r f c 5 1 2 0 的规定在i s i s 路由协议报文中增加多拓扑t l v 来实现。本论文在h 3 c 路由器上 设计和实现i s i s 多拓扑路由，通过实际运行数据说明多拓扑路由的各种特性，提 出并验证i s i s 多拓扑路由优化方案。 q 1 2 研究现状和目的 多拓扑路由方案自提出之后，就受到许多学者和公司的关注。多拓扑路由为 不同类型的服务分别创建子拓扑，每个子拓s b g , j 建独立的逻辑路径，独立进行路 径选择和路由转发。多拓扑路由在现实中有许多应用，如创建不同子拓扑分别处 理对时延敏感的业务和对吞吐量敏感的业务；为机密业务单独创建独立的逻辑路 径保证安全；根据网络中不同业务的流量统计设计子多拓扑保证网络负载均衡等。 当今，主流的路由器制造厂商如c i s c o 、j u n i p e r 、华为都有支持多拓扑路由的路由 器产品。 目前，国内外对多拓扑路由的研究主要集中在以下方面： l ：多拓扑路由在流量工程方面的应用 通过合理的设计子拓扑使得各个拓扑之间形成相互备份，当某个拓扑的链路 发生故障时，可以快速的寻找最优子拓扑作为备份进行数据转发。 2 ：多拓扑路由在负载均衡方面的应用 按照不同业务的流量合理的设计子拓扑使得网络中各链路利用率达到最大。 3 ：多拓扑路由在安全方面的应用 按照数据的可疑程度设计子拓扑的安全策略，对不同业务提供不同级别的保 护，有效的保证了数据安全。 1 3 主要研究内容 本课题依托于实验室同华为三康公司的合作开发项目“c o m w a r e v 5 0 0 ri s i s m t r 的设计与实现 ，通过在华为三康公司路由器上实现i s i s 多拓扑路由功能， 主要研究内容包括以下几个方面： 1 ：在熟悉华为三康公司路由器软件开发平台的基础上提出了i s i s 多拓扑路由 协议的总体框架设计，并对模块之间的接口进行定义。 2 ：提出了i s i s 多拓扑广播网邻居模块的两种设计方案：i s o 协议解决方案和 邻居状态机解决方案，着重介绍了邻居状态机方案的邻居状态机事件提取和邻居 状态机中原子操作的抽象工作，以及对两种方案进行对比认证。 3 ：对i s i s 广播网中指定路由器选举提出了两种设计方案：原d i s 解决方案和 d i s 原子选举方案，着重阐述了如何从原d i s 解决方案中抽象出d i s 选举公共操 作形成d i s 原子方案，以及对两种方案进行对比认证。 4 ：提出了i s i s 多拓扑l s p 模块的两种存储方案：独立存储方案和共同存储 方案，着重阐述了如何设计存储数据结构使得子拓扑之间共享一套数据，以及对 2 两种方案进行对比认证。 5 ：在i s i s 多拓扑路由计算i s p f 算法实现介绍的前提下，提出了两种路由计 算数据结构存储方案：子拓扑路由信息单独存储方案和子拓扑路由信息共同存储 方案，着重阐述了如何设计路由计算存储结构以及两者性能的对比认证。 1 4 本文的主要内容 本文的主要内容和组织形式如下： l ：第一章为引言，主要介绍课题背景，研究现状和目的以及论文的组织形式 2 ：第二章为i s i s 多拓扑路由概述，首先介绍i s i s 路由协议的基本知识，数据报 文以及工作机制；多拓扑路由在i s i s 中的实现原理和数据报文格式；最后介绍i s i s m t r 的主要应用 3 ：第三章为i s i s 多拓扑路由在路由器上的设计与实现，主要介绍协议实现的三 大组成部分：邻居模块，l s p 模块和路由计算模块，并分别对这几个模块在路由 器上的设计与实现进行详细的描述。 4 ：第四章为i s i s 多拓扑路由的优化方案，主要介绍对多拓扑路由计算两种不同 存储方案，详细介绍两种方案的工作原理以及如何在路由器上设计实现，最后在 搭建实验平台上进行仿真验证。 5 ：第五章为本文的工作总结，并探讨了多拓扑路由的下一步工作。 3 2i s i s 多拓扑路由综述 2 1i s i s 路由协议简介 i s i s 路由协议是当今硕果仅存的两大链路状态路由协议，它是由国际化标准 组织制定的i s o i e c1 0 5 8 9 所规范的内部网关协议，起初是为i s o 七层模型中网 络层设计的路由协议，并不适用于p 网络，后来i e t f 标准化组织的制定了具有 i p 路由扩展功能的集成i s i s 协议r f c l l 9 5 ，自那之后i s i s 作为一种m 路由选择 方案的逐渐流行开来，现在欧洲很多电信运营商都使用i s i s 路由协议。本文中提 到的i s i s 协议都是指经过扩展后适用i p 的集成i s i s 协议。 同o s p f 路由协议类似，i s i s 路由协议属于内部网关链路状态路由协议，两者 具有很多相似之处，如都是链路状态路由协议，采用s p f 算法进行最短路径计算； 采用类似的报文扩散方案保证网络中路由器链路状态数据库一致：采用分层结构 保证路由协议的扩展性。区别于o s p f ，i s i s 路由协议是直接运行在数据链路层之 上，对口协议支持不够彻底；i s i s 协议通过报文t l v 格式进行扩展，报文格式简 单易扩展：i s i s 协议仅支持p 2 p 网络和广播网，而o s p f 还支持n b m a 和点对多 点链路。 i s i s 协议主要由邻居模块，l s p 模块和路由计算模块组成，三个模块共同协 作，完成最短路径选择和路由转发表的创建。其中邻居模块通过定期发送h e l l o 报 文维护同周边路由器的邻居关系，邻居关系是本地l s p 生成的信息源，也是数据 报文的发送出口；l s p 模块负责l s p 泛洪发送和l s p 接收，最终整个网络中所有 路由器形成统一的链路状态数据库；路由计算模块根据链路状态数据库进行最短 路径优先路由计算，计算出最短路径树，最终生成到每个目的地址的路由条目。 2 1 1i s i s 区域 为了减少路由器中路由条目的规模，增加路由协议的可靠性，i s i s 路由协议 将自治系统划分为不同区域进行管理。i s i s 路由协议将自治系统分为两类区域： l e v e l - l ( 简称l 1 ) 和l e v e l 2 ( 简称l 2 ) ，并规定路由信息只能在同一l e v e l 进行传递， 即l e v e l 1 的路由信息只能在l l 区域内传递，l 2 的路由信息只能在l e v e l 2 传递。 为了将l l 的路由信息通知给l 2 ，i s i s 协议规定了l 1 2 路由器( 既属于l 1 区域也 属于l 2 区域) 作为l 1 同l 2 路由信息交互的桥梁 6 。 4 在i s i s 路由协议中，每个路由器通过n e t 进行标识。n e t 包含三部分：区域 地址，系统标识符和网络层选择符。区域地址表示该路由器所处的区域，在l 1 中， 只有区域地址相同的路由器之间才能建立邻居( l 2 没有该限制) ；系统标识符是路 由器在区域内的唯一标识，一般为6 个字节，不允许在区域内重复：网络层选择 符表示网络层用户( 在i p 网络中一般初始化为o o ，表示上层协议为i p ) 。例如配置 n e t 为1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 ，即区域地址为l o ：系统标识符为1 1 1 1 1 1 1 1 1 1 1 1 ，网 络选择符为0 0 。 如图2 1 所示，在实际的网络设计中，通常将性能好的路由器作为l 2 路由器， 负责各个区域间路由信息的交互，而且必须保证l 2 区域是连续的，只有这样i s i s 路由协议才能路由到所有的目的地址。在l 1 区域中，路由器之间必须有相同的区 域地址才能建立邻居关系，所有不在本区域内的数据报文都将发送到最近的l 1 2 路由器上，由l 1 2 路由器通过l 2 区域转发出去。i s i s 路由协议通过将自治系统划 分为不同的l 1 和l 2 区域不但缩小了每个区域的路由条目，同时增加了路由协议 的可靠性，即某个l l 区域发生了故障不会影响到其他的l l 区域。 2 1 2i s i s 路由协议报文 图2 1 ：l 1 和l 2 区域划分 f j 9 2 - 1 ：l 1a n dl 2 a r e ap a r t i t i o n i s i s 路由协议规定了三种类型报文【2 】： l ：h e l l o 报文 h e l l o 报文用于维护路由器同相邻路由器之间的邻居关系以及广播网中d i s ( 指 定路由器) 选举。根据链路状态类型不同，h e l l o 报文分为三种不同格式：点对点 h e l l o 报文、l 1 广播网h e l l o 报文和l 2 广播网h e l l o 报文。i s i s 路由协议根据接口 链路类型不同选择发送对应格式的h e l l o 报文。三种报文格式基本一致，以l l 广 播h e l l o 报文为例，详见附录a 中图a 1 ，主要字段解释如下： i dl e n g t h 字段：表示n e t 中系统标识符的长度。 p d ut y p e 字段：表示报文类型。 s o u r c ei d 字段：系统标识符字段，唯一标识该路由器。 h o l d i n g t i m e 字段：邻居保持时间，若在该时间内没有收到h e l l o 报文，双方 邻居关系将被清除。 p r i o r i t y 字段：d i s 选举优先级字段，用于d i s 选举( 广播网h e l l o 报文特有) 。 l a ni d 字段：该字段由d i s 的系统标识符字段和1 字节的d i s 标识符组成( 若 该路由器是d i s ，则将该字节置1 ) 。表明路由器对应l e v e l 的指定路由器。 恻a b l el e n g t hf i e l d s 字段：可变长字段，该字段由t l v 构成，主要 用于h e l l o 报文的功能扩展，主要t l v 介绍如下： 区域地址t l v ：包含路由器配置的区域地址，其中l 1 的路由器之间只有在双 方有共同的区域地址时才能建立邻居关系。 邻居t l v ：路由器邻居m a c 地址的集合，即已经同该路由器已经建立了邻居 的路由器m a c 地址集合。该t l v 是邻居实现三次握手的关键t l v 。 协议支持t l v l 3 】：表明网络层协议，目前支持i s o 、i p v 4 和i p v 6 认证t l v ：用于防止欺诈，只有对端路由器通过了认证t l v ，邻居关系才能 建立，可用于保证路由器安全。 接口i p 地址t l v 【3 】：表明发送h e l l o 报文的接口i p 地址 填充t l v ：默认为0 ，通过将邻居报文填充到链路m t u 大小，用于路由器链 路协商m t u 。 2 ：l s p 报文 l s p 报文又称为链路状态报文，它主要用于在路由器之间传递路由信息，根 据l e v e l 不同分为：l 1l s p 和l 2l s p ，两者格式基本一致。下面以l 1l s p 报文 为例，详见附录a 中图a 一2 ，主要字段解释如下： l s pi d 字段：该字段由三部分组成：系统i d 、d i s 标识和l s p 分片。其中系 统i d 用于唯一标识产生该l s p 的路由器；d i s 标识表示是否为d i s 产生的l s p ； l s p 分片则表明该l s p 报文在路由器产生的所有l s p 报文中的排列。 r e m a i n i n gl i f e t i m e 字段：l s p 剩余时间字段，若在该时间内没有收到l s p 报 文，该l s p 将置为过期状态。 s e q u e n c en u m b e r 字段：l s p 的序列号，序列号数目越大表示该l s p 越新。 a t t 字段：当路由器为l 1 2 时，若该字段置1 则表示路由器有通往外部区域 ( l 2 ) 的出口。 l s d b o l 字段：o v e r l o a d 标识符，若该字段置1 表示路由器处于过载状态，即 路由器处于不可靠状态( 如内存空间不足) ，在进行最短路径计算时注意不要通过该 路由器转发数据。 v a r i a b l el e n g t hf i e l d s 字段：可变长字段，该字段由t l v 构成，主要 6 用于l s p 报文的功能扩展，主要t l v 介绍如下： 邻居n b rt l v ：路由器邻居系统标识符和到该邻居路由器的c o s t 值，该t l v 描述了该路由器同周围邻居路由器的拓扑图，是l s p 模块构建全局链路状态数据 库的信息来源。 i p 地址可达t l v l 3 】：表示路由器可以直接到达的i p v 4 路由条目( 包括i p 地址、 子网掩码和c o s t 值) ，在路由计算的p r c 模块将路由条目下刷到路由转发表中。 i p v 6 地址可达t l v 【3 】：表示路由器可以直接到达的i p v 6 路由条目( 包括i p v 6 地址、子网掩码和c o s t 值) ，在路由计算p r c 时将路由条目下刷到路由转发表中。 协议支持t l v 、区域地址t l v 、接口p 地址t l v 同h e l l o 报文介绍。 3 ：s n p 报文 s n p 报文用于同步链路状态数据库，使得全网的链路状态数据库保持同步。 有四种报文：l lc s n p 、l 2c s n p 、l 1p s n p 和l 2p s n p 。 c s n p ：完全序列号报文，报文包含路由器所有l s p 的摘要信息。路由器接收 到c s n p 报文后，对比本身链路状态数据库中的l s p 摘要和c s n p 报文中的摘要， 若发现不一致，则通过发送p s n p 报文和l s p 报文进行链路状态数据库同步交互， 最终达到全网链路状态数据库同步。以l 1c s n p 为例，详见附录a 中图a - 3 ，主 要字段解释如下： s t a r tl s pi d 字段：该字段表明该c s n p 报文l s p 摘要信息起始l s pi d 。 e n dl s pi d 字段：该字段表明该c s n p 报文l s p 摘要信息终止l s pi d 。 v a r i a b l el e n g t hf i e l d s 字段：可变长字段，该字段由t l v 构成，包括 下列t l v ： l s p 摘要t l v ：该t l v 是一个l s p 分片的概括信息，主要字段有： r e m a i n i n gl i f e t i m e 字段：l s p 剩余时间字段，若在该时间内没有收到l s p 报 文，该l s p 将置为过期状态。 l s pi d 字段：该字段由三部分组成：系统i d 、d i s 标识和l s p 分片。其中系 统i d 用于唯一标识产生该l s p 的路由器；d i s 标识表示是否为d i s 产生的l s p ； l s p 分片则表明该l s p 报文在路由器产生的所有l s p 报文中的排列。 l s ps e q u e n c e n u m b e r ：l s p 序列号，序列号数目越大标明该l s p 越新，路由 器始终保持链路状态数据库中的l s p 是最新的。 c h e c k s u m 字段：该l s pi d 的l s p 的校验和字段。 p s n p 报文：部分序列号报文，该报文用于请求发送l s p 和确认收到l s p ，与 c s n p 报文协作完成l s d b 的同步。以l 1p s n p 为例，详见附录a 中图a - 4 ，其 中可变长字段中包含l s p 摘要t l v 。当路由器链路状态数据库中不包含p s p n 报 文中的l s p 摘要时，路由器将发送p s n p 报文请求该l s p ；当路由器链路状态数 7 据库中的l s p 摘要比p s n p 报文新时，路由器将发送该l s p 报文给请求路由器。 2 1 3i s i s 工作机制 如图2 2 所示，i s i s 主要功能由四部分组成：接收，更新，决策和转发，下面将详 细介绍每个部分的功能【2 】 图2 - 2 ：i s i s 路由协议原理框图 f i 9 2 2 ：t h ed e c o m p o s i t i o no fi s i sp r o t o c a i 接收模块：该模块负责h e l l o 报文、l s p 报文和s n p 报文的接收。该模块首先对 报文进行合法性检查，若报文合法性检查通过则根据报文类型不同送往相应模块 进行处理 更新模块：该模块负责构建、接收和发送l s p 报文【l 5 l 1 ：l s p 报文接收：该模块从接收模块中获取l s p 报文，通过l s p 报文解析后获取 最新路由拓扑信息，用于更新本地链路状态数据库，并将这些信息泛洪出去。 2 - l s p 报文生成：i s i s 路由协议除了周期性的生成l s p 报文用于保证网络链路状 态数据库的同步之外，当路由信息发生变化时将触发l s p 报文的生成，这种机制 保证了网络中路由变化能被快速的响应。 3 ：l s p 报文发送：l s p 报文通过泛洪的方式保证网络中每个路由器能接收到。通 8 常l 1 的l s p 只在l l 区域内传播，l 2 的l s p 只在l 2 中泛洪；任何l s p 都不能传 送到自治系统外部。 决策模块：通过收集更新模块中获得的网络路由拓扑信息形成全网链路状态数据 库l s d b ，决策模块根据l s d b 运行最短路径算法得到最佳路由，最后经过路由优 选得到路由转发表。 转发模块：从接收模块中获得数据报文，查找路由转发表，选择合适的路由条目 将数据转发出去。 2 2多拓扑路由简介 数据包 图 2 3 ：多拓扑路由介绍 f i 9 2 3 ：t h ei n t r o d u c t i o no fm u l t i - t o p o l o g y 多拓扑路由又称着色路由，它根据不同的服务创建子拓扑，每个子拓扑具有独 立的逻辑路径和路由表。多拓扑路由可以在众多路由协议上实现比如i s i s ，o s p f 和b g p ，而且几乎支持所有的路由特性如引入、聚合、默认路由等p j 。 在多拓扑路由中存在标准拓扑的概念，标准拓扑相当于没有实现多拓扑路由的 网络拓扑，标准拓扑包含了网络中所有的路由器和路由链路，是最全的网络拓扑 信息【8 】。在多拓扑路由应用中，标准拓扑作为子拓扑的备份拓扑，即在子拓扑中没 有对应路由条目时，通过标准拓扑进行转发。为了避免环路的出现，默认情况下， 多拓扑路由不支持子拓扑之间的相互备份，如何设计合适的子拓扑分类使得子拓 扑之间进行有效备份是国内外对多拓扑应用研究的热点所在。 如图2 3 所示为路由器创建3 个子拓扑后的路由表示意图，当路由器接口接收 到数据包时，路由器对数据包进行解析获得多拓扑信息( 比如i p 数据包中的d s c p 或n b a r ) 进而选择合适的子拓扑进行转发，通过查找对应子拓扑路由转发表进行 9 转发。路由器实现多拓扑路由后，不同服务的数据将选择不同的逻辑路径转发， 从而实现业务分流，负载均衡和网络传输安全等。 r f c 5 1 2 0 是i s i s 路由协议实现多拓扑路由的标准。由于i s i s 协议的报文格式 是基于t l v 格式( 参考2 1 2 章节) ，i s i s 路由协议对于多拓扑路由的扩展十分简单。 根据r f c 5 1 2 0 的规定，i s i s 路由协议增加了四种t l v 用以支持多拓扑路由特性【l 】， 通过将以下四种t l v 封装到对应报文的可变长度字段实现多拓扑路由： 1 多拓扑i dt l v ：子拓扑的i d 号，即子拓扑的着色。 2 多拓扑邻居t l v ：该t l v 在i s i s 邻居t l v 的基础上增加了多拓扑i d 标 识，表示路由器上该子拓扑的所有子拓扑邻居信息。 3 多拓扑i p v 4 前缀可达t l v ：该t l v 在i p v 4 可达t l v 的基础上增加了多 拓扑i d 标识，表示路由器该子拓扑下的i p v 4 前缀可达t l 、，。 4 多拓扑i p v 6 前缀可达t l v ：该1 r i 在i s i si p v 6 可达n 的基础上增加 了多拓扑i d 标识，表示路由器在该子拓扑下的i p v 6 前缀可达t l v 。 2 3i s i sm t r 主要应用 由于i s i s 路由协议中同时实现i p v 4 路由和i p v 6 路由，其邻居t l v 中不能区 分是v 4 邻居或v 6 邻居，在多拓扑路由方案提出之前，若一个网络中i p v 4 和i p v 6 共存，i s i s 可能出现路由计算错误的现象，如下图所示： r t cr t d 图2 4 ：i p v 4 和i p v 6 共存示意图 f i 9 2 - 4 ：t h ec o e x i s t e n c eo fi p v 4a n di p v 6 如图2 4 所示，r t a 中通过路由计算得到到达r t d 的i p v 4 和i p v 6 路由都是 通过r t b ( c o s t 值最小) 。当r t b 接收到r t a 发送过来的i p v 6 数据包时，r t b 查 询i p v 6 路由表发现并没有通往r t d 的路由，r t b 选择将丢弃该数据包；但从全 1 0 网拓扑中可以得出，r t a 可以通过r t c 将i p v 6 数据包传送到r t d 。 上述问题出现的根源在于i s i s 路由协议的邻居t l v 不能区分i p v 4 邻居和 i p v 6 邻居，多拓扑路由的提出可以很好的解决i s i si p v 4 i p v 6 共存的问题，多拓 扑路由通过在h e l l o 报文中的添加m t i dt l v ，在路由器中分开维护i p v 4 和i p v 6 邻居。i p v 6 作为一个单独的子拓扑进行处理，该子拓扑维护自己的多拓扑邻居， 接收l s p 报文处理本拓扑的路由信息，最后通过路由计算得到i p v 6 路由。如如图 2 4 所示，r t b 与r t d 之间不存在v 6 邻居，故r t a 的i p v 6 子拓扑中路由计算将 得到正确的路径转发i p v 6 数据，即通过r t c 进行转发。 i p v 4 i p v 6 网络共存问题的解决只是多拓扑路由在i s i s 中的一个应用，多拓 扑路由在负载均衡、流量工程和安全路由上都有重大应用。比如将对时延敏感的 语音数据流单独分配在子拓扑中，选择一些负载不重的链路作为子拓扑的逻辑链 路，可以有效的保证通话质量；将对安全性要求较高的业务( 如电子商务付款) 单独 分配子拓扑，选择物理独立的路径进行路由，可以有效的保证安全性；将可疑数 据流导向具有安全防范策略的子拓扑进行分析处理等。 3i s i s 多拓扑路由在路由器上的设计与实现 本章将介绍i s i s 多拓扑路由在华为三康公司路由器的设计与实现。i s i s 路由 协议由三大模块组成：邻居模块、l s p 维护模块和路由维护模块。i s i s 多拓扑路 由协议特性扩展需要对i s i s 协议三大模块都进行改动，每个模块的扩展都有不同 的方案，本章将详细介绍i s i s 多拓扑路由三大模块的扩展实现，并对不同的扩展 方案进行对比验证。 3 1i s i s 多拓扑路由总体设计方案 图3 1 ：i s i s 多拓扑路由总体设计框架图 d 1接收到h e l l o 报文 d 2接收到l s p 报文和s n p 报文 d 3路由计算完成后将最优路由下刷到路由转发表 c l邻居增删改触发l s p 改变 c 2邻居增删改触发路由计算 c 3路由信息增删改触发路由计算 c 4路由计算完成后触发l s p 重新生成 本小节主要介绍i s i s 多拓扑路由在华为三康公司路由器上的总体设计框架。 参考i s 0 1 0 5 8 9 协议对i s i s 协议实现的规定，i s i s 多拓扑路由扩展总体设计主要包 括三个部分：邻居模块( 广播网中包括d i s 选举模块) 、l s p 模块和路由计算模块。 三个模块之间协同工作共同完成多拓扑路由计算的功能，其中三个模块的数据交 互如图3 1 所示。 其中邻居模块通过定期发送和接收h e l l o 报文维护同周边路由器的邻居关系， 路由器的邻居是本地l s p 生成的源，也是路由器报文的转发出口；l s p 模块负责 l s p 报文泛洪发送和l s p 报文接收，该模块保证网络中所有路由器形成统一的链 路状态数据库；路由计算模块根据l s p 模块生成的链路状态数据库和邻居模块生 成的邻居表进行最短路径优先路由计算，得到到达全网拓扑的最短路径树，最后 根据最短路径树生成到每个目的地址的路由转发表。当路由器接收到待转发的数 据包时，通过查询路由转发表进行报文转发。 本章其它章节将在i s i s 多拓扑路由总体框架的设计基础上，分别对邻居模块、 l s p 模块和路由计算模块在路由器上的设计与实现进行详细阐述，通过不同的方 案对比得出最优的实现手段。目前华为三康公司路由器已经实现了i s i s 多拓扑路 由功能。 3 2i s i s 多拓扑路由邻居模块在广播网上的设计与实现 i s i s 协议支持点对点链路和广播网链路两种，两者在实现上大体一致。本小 节首先介绍i s i s 邻居的基本概念，然后提出两种i s i s 多拓扑邻居实现方案，最后 对这两种方案进行比较验证。 在i s i s 多拓扑邻居实现之前，首先简要介绍i s i s 广播网邻居的基本概念和建 立过程。i s i s 邻居有三种状态：i n i t 、d o w n 和叩。i n i t 状态邻居表示邻居三次握手 没有通过，处于该状态下的邻居不能作为路由的下一跳进行转发；d o w n 状态邻居 表示邻居将被删除，该状态属于不稳定状态，它很快会转移到邻居结构销毁状态； u p 状态是邻居正常工作状态，处于该状态的邻居可以作为路由的下一跳进行数据 转发。三个状态之间可以相互转换，图3 2 为广播网邻居建立过程。 如图3 2 所示：r t a 发送h e l l o 报文，报文中包含路由器本身的系统标识符( a ) 和邻居信息( n u l l ) ，通过组播方式从接口发送出去；r t b 接收到r t a 的h e l l o 报 文后，创建一个i n i t 状态的邻居r t a ，并回应h e l l o 报文，报文中包含本身的系统 标识符( b ) 和邻居信息( 包含r t a 的m a c a ) ；r t a 接收到r t b 的h e l l o 报文后首先 创建一个i n i t 状态的邻居b ，查看h e l l o 报文的邻居信息，发现包含r t a 的m a c 地址，即双向链路检查通过，在路由器后续处理中将邻居r t b 状态置为u p ，同时 回送h e l l o 报文，报文包含邻居信息( r t b 的m a c ) ；r t b 接收到r t a 的h e l l o 报 文后，查找发现h e l l o 报文中包含本机的m a c 地址即双向链路检查通过，将r t a 的邻居状态置为u p 。广播网邻居的三次握手建立过程保证了邻居之间链路的双向 1 3 性，可以有效的防止网络欺骗。 r t a 系统i d 为s y s i m a c 地址为m a c a r t b 系统l d 为s y s 2 m a c 地址为m a c b 图3 - 2 ：广播网邻居三次握手 f i 9 3 - 2 ：t h et h r e e - w a yh a n d s h a k eo f b r o a d c a s tn e i g b o r 3 2 - 1i s o 协议上i s i s 广播网邻居设计方案 该设计方案按照i s i s 协议i s 0 1 0 5 8 9 规定在路由器上实现i s i s 广播网邻居模 块，将i s i s 广播网邻居模块分为发送部分和接收部分，发送模块的功能包括：按 照协议规定封装h e l l o 报文，报文格式详见附录a 。为支持多拓扑功能，在报文中 封装多拓扑i dt l v ，表明该路由器所支持的子拓扑；响应h e l l o 报文发送定时器 定时发送h e l l o 报文，其中d i s 发送的时间为其它路由器的1 3 ，保证d i s 变化可 以快速的被检测到；同时在发送h e l l o 报文时，将报文大小填充到链路的m t u ， 用这种方式进行邻居路由器之间m t u 协商。接收模块须响应h e l l o 报文接收以及 外部触发事件( 接i ：iu p d o w n ，i s i s 协议使能去使能) ，其处理流程如图3 。3 所示。 在该设计方案中，i s i s 邻居协议处理和i s i s 多拓扑邻居处理在逻辑上分开进行， 首先保证i s i s 协议邻居处理完成，然后再处理i s i s 多拓扑邻居部分和其他协议扩 展功能( 如n s r 、g r 等) 。 1 4 城s k 燃谴收 1 4 c 1 1 0 旅支 拨幽帅协 议，7 电能 i 昔h o l d 宅h 器趟e j 互拜j h 上 将等 超 j l i 芷台汀j 忾榆矗 i s o 协议广播饲邻居模 涠遗，j 接口盼专l ；屠 多拓扑邻居模块 1 i c l 24 l 土j ：= i t = 三2 f f j 彩孙扑 i 。 。1r d ；i i 嚣f i ! 骨的名拓扑f df 。 王：科i 扑j d 搬文手u 路| l l 器 ii j i ；把孙i d ：报之：f ，仃件瑞：| i 均存在创建f 扣i 扑邻腑1 ： 中，：行 ：；涮际子托补邻居 彰礼扑j d ：蹈l l i 器巾和 ； 撩文巾，f i 打件1 ：仆处砷 图3 3 - i s o 协议邻居处理流程 f i 9 3 - 3 ：t h ep r o c e s so fi s on e i g h b o r 3 2 2i s i s 广播网邻居状态机的设计方案 在i s o 协议规定的i s i s 广播网邻居设计方案实现中，将协议邻居和协议邻居 扩展分开进行处理，这种处理方式从直观上便于理解，在i s i s 协议发展早期，即 1 5 i s i s 邻居比较简单时是一个优秀的解决方案，但随着i s i s 路由协议的发展，各种 扩展特性不断增多( 多拓扑、n s r 、g r 等) ，若每种协议扩展按照图3 3 进行扩展， 代码规模将开始膨胀，而且由于协议扩展同协议邻居之间存在一定的关系( 如多拓 扑邻居必须在标准拓扑邻居存在的前提下才能建立) ，每一种协议扩展都必须对协 议邻居进行改造，久而久之协议邻居部分将变得复杂且难以维护，同时各种协议 扩展都有类似的操作，都涉及到邻居的增删改操作，这些部分如果在每个协议扩 展部分都重复一遍，则代码冗余严重。 鉴于i s o 协议规定的i s i s 广播网邻居设计方案的弊端，本论文提出了一种新 的i s i s 邻居解决方案：i s i s 广播网邻居状态机方案。如图3 - 4 所示为i s i s 邻居状 态机实现方案示意图，将邻居模块抽象为状态机事件转换和邻居状态机处理两部 分，其中状态机事件转换部分负责将接收到的h e l l o 报文信息提取出来，