第5章高性能路由器体系结构与关键技术 5.引言 1 路由器工作在网络层,它是一种数据包转发设备。路由器通过转发数据包实现网络互 联。虽然路由器可以支持多种协议(如TCP/IP 、IPX/SPX 和AppleTalk等), 但目前绝大多 数路由器都主要运行TCP/IP 。路由器通常连接两个或多个IP 子网。路由器根据收到数 据包中的网络层地址以及路由器内部维护的路由表决定输出端口以及下一跳地址,并且重 写链路层数据包头实现数据包的转发。路由器通过动态维护路由表反映当前的网络拓扑, 并通过与网络上其他路由器交换路由和链路信息维护路由表。 路由与转发是路由器的两个基本功能。路由器必须对每个到达本路由器的分组做出正 确的转发决策,决定分组向哪一个下一跳路由器转发(Forwarding), 为了进行正确的转发决 策,路由器需要在转发表中查找能够与转发分组目的地址最佳匹配的表项,这个查找过程被 称为路由查找(RouteLookup), 同时,路由器在得到正确的转发决策之后必须能够将分组 从输入接口向相应的输出接口传送,这个过程被称为内部交换(Sithig)过程。 从1976 年发明第一台路由器到目前为止,路由器已有40多年(w) 的(c) 历史(n) 。在这期间,随着 Internet的飞速发展,路由器作为网络连接的核心设备,其发展历程也经历了几次飞跃。近 年来,国际上对高性能IP 路由器技术的研究也日益活跃,提出了用交换结构(Switch Fabric)提高各接口单元之间的数据通信速度的基本思想。事实上,多处理器交换式体系结 构的第三代路由器的核心模块就是交换结构。从研究趋势看,交换技术已经成为高速路由 器的核心技术。随着性能要求的进一步提高,研发人员又提出可扩展路由器体系结构,目前 主流的路由器厂商都已经可以提供商用的可扩展路由器产品。 本章首先简要回顾路由器的发展历史,然后介绍路由器的分类和体系结构,让读者对路 由器有一个基本的认识,之后对路由器的软硬件系统组成、路由查找和分组分类算法等关键 技术予以介绍,再从可扩展路由器、高性能路由器交换结构和调度算法、新型路由器研究进 展等方面对路由器相关的研究问题进行讲解和讨论,最后对本章进行总结。 5.路由器的发展历史 2 路由器发展过程中经历了不同的体系结构,本节对其进行简单梳理。 2008 年,IEEE 将InternetAward奖项授予MichaelBrescia、RobertHinden和 VirginiaTravers三人,以表彰他们在20 世纪70 年代发明了第一台路由器( 1(a)), 见图5. 当时他们三人都在BBN 工作。真正第一代的商用路由器是美国Cisco公司首先开发的。 1984 年,在斯坦福大学任教的一对年轻教师列昂纳德·波萨克(LeonardBosack)和桑 德拉·勒纳(SandyLerner)结为夫妇。波萨克是个性格开朗的年轻人,而他的妻子勒纳则 是一位精明能干的女科学家。波萨克当时是斯坦福大学计算机系的计算机中心主任,而勒 ·177· 纳则是斯坦福商学院的计算机中心主任。他们两人当时的办公场地相距不到500米,但由 于一个使用的是IBM系统,一个使用的是DEC系统,他们各自负责的两套系统无法互通。 于是,两人一起设计了一套可以自动将一个系统命令转换成另一个系统能理解的命令的系 统,而实现转换的小盒子就是世界上的第一台多协议路由器。他们由此设计出一种新型设 备,用来将斯坦福校园内的各个计算机局域网连接在一起,形成统一的网络,这就是“多协议 路由器”,它的出现标志着互联网时代真正到来。 1984年,他们在美国加州圣荷塞成立了Cisco系统公司,这是一家标准的硅谷模式高科 技公司。注册公司那天,他们开车经过著名的金门大桥,因为喜欢SanFrancisco这个名字 的发音,于是取了SanFrancisco后面的5个字母作为公司的名字(因此,在此后相当长一段 时间,Cisco公司坚持将公司名称写为cisco)。而Cisco公司的Logo就是金门大桥。巍峨 的金门大桥是旧金山市最著名的景观之一,它横跨金门湾,将两岸相望的人们紧紧连接在一 起,与Cisco公司的网络产品所想表达的意义默契相通。创业成功后,美国知名风投基金 KPCB开始向他们注资。因为管理理念不同,夫妻俩在1990年退出了Cisco公司。当时的 他们将手上持有的33%股份卖了1.sco公司的市值最高曾经达到5000 7亿美元。考虑到Ci 亿美元以上,如果他们能将股份保留,则他们有机会成为世界首富。1986年,Cisco公司发 布了第一代商用路由器CiscoAGS(AdvancedGatewayServer), 1(所示。 如图5.b) 图5. 1 世界上第一台路由器和第一台商用路由器 此后,路由器经历了内存交换、总线交换、Crosbar交换和多集群可扩展的交换结构的 四代发展,后面章节将对这几代路由器的体系结构进行详细介绍。 5.路由器软硬件系统组成 3 路由器是一个复杂的系统,本节首先从概念上对路由器的体系结构进行概述,然后针对 路由器的软件结构给出一个通用的模型。 5.1 路由器基本结构单元 3. 虽然路由器经历了长期的发展过程,但是它的基本结构没有发生很大的变化。图5. 给出了路由器的基本逻辑结构。从功能逻辑上看,路由器主要由四大功能模块组成,分别是 2 网络接口、转发引擎、路由处理器以及交换模块。 网络接口(也就是通常说的线卡(Linecard))和物理链路直接相连,网络接口模块中常 ·178· 常包括处理相应物理传输数据分组的功能,完成网络分组的接收和发送工作。网络接口一 般工作在网络协议栈的最下面两层———物理层和数据链路层。一台路由器中有许多个网络 接口,而且随着通信技术的发展,网络接口的性能也越来越高。使用的通信媒介有电信号线 路到光信号线路的多种规格,速度从10Mb/s到几百Gb/s。 图5. 2 路由器的基本逻辑结构 转发引擎工作在网络协议栈的第三层———网络层,它主要负责决定数据分组的转发路 径,转发引擎对接收的数据分组的头部进行解析,然后根据数据分组的分类标识(如目的IP 地址)在路由表中进行查找,得到转发操作的目的端口。在高速路由器中,转发引擎大多采 用专用硬件(如TCAM)实现。在分布式体系结构中,转发引擎又包含本地转发表,用于在 线卡上完成转发的局部查表操作。 路由处理器主要由运行高层协议(特别是路由协议)的内部处理模块组成。除此之外, 路由处理器还要保证整个核心路由器能够可靠稳定地工作,诸如各个网络接口卡的状态一 致性维护,局部转发表和全局路由器的一致性维护,系统状态的监控等工作都需由路由处理 器模块完成。 交换模块用于连接多个网络接口以及路由引擎模块,为它们之间的数据传输提供高速 的数据通路。交换结构的实现方式主要有共享总线和交叉开关等。 路由器中一个非常关键的数据结构是路由表。路由表包含了能够完成网络分组正确转 发的所有路由信息,它在整个路由器系统中起承上启下的作用,它根据路由处理器提供的路 由信息及时更新路由表,从而能够为转发引擎返回正确的路由查找结果,完成分组的转发。 因此,路由表是实现路由器基本功能最重要的数据结构。 路由器根据网络分组的不同提供了两种相应的处理路径,分别是数据路径以及控制路 径。数据路径上处理的是目的地址不是本路由器而需要转发的网络分组,数据路径是整个 路由器的关键路径,它的实现直接影响路由器的整体性能。控制路径上处理的是目的地址 为本路由器的高层协议分组(特别是各种路由协议分组), 它不是路由器的关键路径,但是它 为路由器分组转发提供了正确的信息。 ·179· 随着光技术的发展,光器件越来越多地出现在路由器的硬件结构中。在研究领域,光学 交换矩阵可以提供具有扩展能力的大规模连接方式,同时保证很短的配置时间。一种基于 FEM(Frame-basedExhaustiveMatching)的设计方案[1]可以完成6400×6400 的交换,理论 上能达到1.s(024×1015b/s)的交换能力。 024Pb/1. 5.2 路由器软件结构 3. 和工作在网络的第二层的交换机相比,路由器的结构要复杂得多。这不仅因为路由器 是工作在网络的第三层,还因为路由器有一套非常复杂的软件系统。路由器上运行的路由 协议通常具有比较复杂的交互流程,而且计算量较大,此外,路由器不仅要完成基于IP 地址 的路由转发操作,还要完成其他许多控制功能,例如安全管理、服务质量控制等。 图5.路由器的软件系统大致可以划 3为路由器软件结构的示意图。根据不同的功能, 分为几个子系统:路由协议子系统、转发子系统、支撑子系统、安全子系统和管理子系统等。 图5. 3 路由器软件结构示意图 路由协议子系统主要负责路由协议的运行和路由表的维护。路由协议通常有IPv4下 的RIPv2、OSPFv2、BGP-4以及IPv6下的RIPng、OSPFv3、BGP-4+(这些路由协议的详细 介绍请参考本书第2章)。它们和邻居路由器进行路由交互,构造路由表,用作转发操作的 依据。在分布式路由器系统中,路由协议通常运行在控制板上,但是,每个线卡都要独立完 成一部分转发操作,需要分布式的路由查表操作。因此,分布式路由器系统中,路由协议子 系统通常维护一个集中的路由表和若干个转发表。路由表集中在控制板上存放,每个线卡 上保存一份转发表,用于查表操作,转发表通常是控制板上的集中路由表的子集,随着硬件 ·180· 能力的提升,目前转发表也可以做到和路由表条目数量完全一致。路由协议子系统中的路 由管理模块负责分布式的转发表和集中的路由表之间的数据同步。 转发子系统是路由器中另一个重要的组成部分,它负责数据分组的查表转发操作。转 发操作本身并不复杂,但是,随着网络速度的提高,对路由器处理速度的需求也不断提高,转 发子系统的处理能力要和数据流的速度相匹配,才可以完成高速的转发。这个要求使得转 发子系统常常成为路由器的性能瓶颈。转发子系统很大程度地依赖于硬件系统的结构,例 如总线方式的硬件和交换网络方式的硬件就有很大的不同。总线方式的硬件结构中,转发 子系统的重点是内部数据的缓冲与管理;而在交换网络方式的硬件结构中,仲裁与调度也是 转发子系统要解决的关键问题。不过,从抽象的角度看,转发子系统的主要功能是提供高速 的数据交换通路。 支撑子系统是路由器中不可或缺的组成部分,主要包含传输层的协议实现,如TCP和 UDP等。支撑子系统主要用于为上层的协议子系统提供通信支持。因为路由协议总是运 行在一定的底层协议之上,例如BGP-4协议就是基于TCP的,所以,在路由器中也要实现 这些通信协议,才能保证上层路由协议的正常运行。而且,在一些特殊的需求下,支撑子系 统本身也要一些特殊的支持,例如,对BGP-4协议的高可用性的支持,就可以通过改进TCP 得到加强。相比于路由器转发的数据量,路由器之间协议交互所占的数据量比较小,支撑子 系统的性能压力不大,但是支撑子系统仍然需要有很好的鲁棒性和运行效率。 安全子系统并不是路由器的必备部分,但是现在的商用路由器都提供一定的安全功能。 此外,涉及安全的处理由于有很大的计算量,常常会成为性能的巨大障碍,所以在路由器中 使用专门的模块或者硬件辅助处理。简单地说,安全子系统通常需要包含两个主要功能部 件:一个是密钥的管理模块;另一个是对IP分组进行安全增强的协议,当前主要是IPSec。 管理子系统负责对路由器的操作与维护进行支持。它包括很多功能模块,如配置管理、 启动控制和文件系统等。此外,管理子系统的一个重要组成部分是基于SNMP的管理模 块,它包含3个主要部分,分别是SNMP处理、管理代理和管理信息库(MIB )。对管理信息 库的更新与访问操作是其中的关键。在分布式系统中,因为每个分布的部件都要受管理子 系统的监控,所以,通常在线卡上运行一个管理代理,负责线卡的本地管理,同时,它和主控 制板上的管理模块进行通信,完成分布式的控制操作。 5.路由器体系结构 4 路由器体系结构[2]变迁的主线如下:由使用通用功能器件发展到使用专用器件;由系 统的串行操作发展到并行操作。器件的专用程度提高,意味着系统的一些关键运算可以采 用独立的物理器件完成,同时还可进行专门的算法优化设计,提高系统性能。另一方面,进 行并行化处理,提高系统的并行度,在提高系统性能方面一直都有广泛的应用,在路由器领 域同样也得到了广泛应用。 一般认为,路由器的体系结构的发展可以划分成如下四代: (1)单机集中式总线结构。 (2)单机分布式共享总线结构。 (3)单机分布式Crosbar结构。 ·181· (4)多机互连的集群结构。 下面首先分析为什么需要高性能路由器,然后逐一介绍这四代路由器体系结构的主要 特点。 5.1 为什么需要高性能路由器 4. 路由器是计算机网络的核心设备,其主要功能是完成路由(Routing)和转发 (Forwarding)。此外,由于应用领域的多样性和应用环境的复杂性,在很多情况下,路由器 还要完成额外的控制与管理功能,如安全、策略和计费等。不过,在骨干网络中,路由转发能 力仍然是核心路由器最重要的性能指标。 简单地说,计算机网络是由大量的路由器和它们之间的连接线路构成的。无论路由器 还是它们之间的连接线路,都有可能成为数据传输的瓶颈。 众所周知,计算机产业的发展速度非常快,根据摩尔定律[3],半导体器件的计算能力大 约每18 个月翻一番,路由器是一种“专用”的计算机,因此,路由器的运算能力也按照这个速 度增长。然而,互联网的发展却超过了这个速度。随着网络技术和网络应用的不断进步,人 们需要的数据传输数量越来越大,据统计,互联网上的数据流量翻一番只需要一年的时 间[4]。有一些估算甚至认为每三四个月就翻一番。不过,即使是保守的估算,网络流量需求 的增长速度还是超过了半导体器件计算能力的增长速度,就算升级很快,网络设备仍然会显 得力不从心。 互联网的传输线路可以有多种介质,其中,光纤的传输速率最高。在过去很长一段时间 里,人们一度认为,由于半导体激光器的限制,TDM(TimeDivisionMultiplexing,时分多路 复用)技术已经达到光纤传输的上限,大约有80Gb/s。但是,随着新技术的出现和成熟,光 纤通信取得了巨大的进步。其中,WDM(WavelengthDivisionMultiplexing,波分多路复 用)技术从20 世纪90 年代的后半段开始逐渐走向实用。这意味着,在一根光纤内,通过增 加不同波长的激光束数目,就可以无限地提高带宽,至少在理论上是如此。与摩尔定律类 似,在这个领域也有一个称为Gilder定律的规则,即光纤的带宽以每6个月翻一番,甚至更 高的速度增长。 光纤通信技术的发展使得传输线路已经不是瓶颈,这样,网络速度提高的主要阻碍就落 在了交换节点———路由器的身上。从图5.路由器的转发速率已经成为网络 4中可以看出, 速度的主要瓶颈。经过研究人员和路由器厂商的共同努力,目前看,路由器的转发能力基本 上每18 个月可以提高2.这至少超过了摩尔定律的增长速度。 2倍, 5.2 单机集中式总线结构 4. 在早期的网络互联中,没有专用的路由器设备,通常使用运行路由软件的通用计算机完 成路由功能。所以,这个时候路由器的体系结构和通用计算机没有很大的区别。系统中包 含一个中央处理器和集中式的内存。所有的通信线卡都通过一条共享的总线和中央处理器 以及集中式内存相连,如图5.成立刚两年的Cisc 5所示。1986 年,o公司推出的业界第一台 路由器产品AGS(AdvancedGatewayServer)就采用了这样的体系结构。 通信线卡(在这种体系结构中实际上就是通常意义上的网卡(NIC)) 完成数据的物理层 以及数据链路层的收发操作,收到的数据分组通过总线送到集中式内存进行存储,同时数据 ·182· 图5. 4 网络发展速度对比 图5. 5 单机集中式总线结构 分组的头部送到中央处理器,进行路由操作,选路成功后的数据分组再通过总线送到目的线 卡,之后再发送出去。 从分组收发的流程可以看出,数据流需要至少两次经过总线,总线在这个系统中是被所 有线卡和中央处理器以及内存共享的,所以,当线卡数目增多或者数据流量很大时,各个设 备对总线的争用会导致严重的访问冲突。 另外,中央处理器需要处理来自所有线卡的数据转发操作,因此,当线卡数目增加或 者数据流量增大时,单一的中央处理器没法完成更高的转发速率要求。同时,路由器还 要和邻居路由器交互路由信息,进行路由计算,这些操作也需要在中央处理器上完成。 因此,在这种单机集中式结构中,单一的中央处理器会成为系统最根本的性能瓶颈。这 种结构路由器的典型交换容量通常小于500Mb/s。这里说明一点,通常路由器计算转发 能力或者交换容量都是按照双向流量计算的,例如一台有两个百兆线卡的路由器,最大 转发能力就是400Mb/s,因为每个百兆网卡都同时支持100Mb/s的入流量和100Mb/s 的出流量。 在这种结构中,数据交换操作主要由软件完成。目前,大部分低端的接入路由器都属于 这种结构。在实际应用环境下,也有许多人使用安装有多块网卡的PC 运行路由软件(如 Gated[5]和Zebra[6])搭建路由器,这种路由器当然也属于单机集中式总线结构。 ·183· 5.3 单机分布式总线结构 4. 单机分布式总线结构的主要思想是提高线卡的处理能力,同时,将用于路由计算的处理 器从路由转发中解放出来,如图5. 6所示。 单机分布式总线结构的“分布式”特性体现为多 个相对独立的线卡可以并行完成各自的操作。每一 块线卡不再是简单的网卡,而是拥有自己的处理器、 内存和若干网卡的独立子系统。到达一块线卡的数 据分组在本地线卡进行存储和转发判决,输出端口 在本线卡内部的数据直接由线卡送到目的端口,只 有路由之后目的端口在其他线卡的数据需要通过总 线送到其他线卡上。这样做主要有两个好处:一方 面提高了线卡上的数据处理能力;另一方面降低了 总线的争用程度。 在这个系统中,通常有一块特殊的“板子”,称做 图5. 6 单机分布式总线结构 “主板”(相对地,线卡通常也称作“从板”),它基本上 不参与路由转发操作,主要完成整个系统的管理操 作和路由计算等任务。它负责运行路由协议和邻居节点进行路由交换,生成路由表,并将用 于转发判决的转发表发布到各个线卡上。 一台完整的路由器主要需要完成两个功能:一个是转发操作;另一个是路由计算功能。 前者处理的是通过路由器的数据流,关键操作是转发表的查找、分组转发以及相应的排队等 操作;后者处理的是路由协议的计算,即通过和邻居路由器进行基于路由协议的交互,完成 路由表的计算。在实际环境中,这两部分都有很高的性能需求。单机分布式总线结构把这 两个功能分布在不同的处理板上完成,其中,转发操作也分布在若干个线卡上完成。这种分 布式结构大大提高了系统的整体性能。 5.2节提到,使用共享总线结构的路由器,都会因为线卡对总线的争用而产生系统效 4. 率的下降,单机分布式总线结构仍然受制于这个因素,虽然为系统提供了分布式处理的特 性,但是共享总线还是成为了系统的性能瓶颈。在典型的应用中,这种结构的交换容量一般 小于5Gb/s。 1993年,Cisco公司推出的7000系列路由器就采用了共享总线分布式处理结构,该系 列产品的最高转发能力可以达到2Gb/s[66]。回顾历史,Cisco7000系列路由器可以说是第 一款IP骨干网路由器。 5.4 单机分布式Coar结构 4.rsb 在单机分布式总线结构中,使用Crosbar(交叉开关)代替共享总线,就得到单机分布式 Crosbar结构,如图5.7所示。图中,SwitchFabric是交换结构的统称,具体实现时厂商一 般均采用Crosbar结构。 共享总线的弊端是无法同时并发地处理多个数据流,即使数据流的输入输出之间没有 冲突也不行。而Crosbar结构可以看作一个交换开关的集合,每对输入端口和输出端口之 ·184· 图5.7Crosbar及单机分布式Crosbar交换结构 间都有一个交换开关,交换开关的控制是彼此独立的,这样,只要数据流彼此不相关(没有公 共的输入端口和公共的输出端口),就可以通过交换开关的控制构成并发的数据通路。通过 Crosbar进行连接进一步提高了路由器分布式结构的并发特性,从而使得整体的交换容量 得到大幅提升。对于这种结构,Crosbar构成的交换网络可以有不同的拓扑结构,基本的 目标是构造一个“无阻塞”的交换网络,在这个领域中,交换网络的拓扑结构冲突的仲裁机制 以及调度算法都是主要的研究内容。 同时,在这种结构的路由器中,通常应用了可以基于内容进行查找的路由表查询器件 (TCAM),可以在一个时钟周期内返回下一跳的查找结果,大大加快了查表速度,突破了查 表与线速之间的速度匹配障碍。这种结构的典型容量是几十到上百Gb/s,现在骨干网络中 的核心路由器通常都采用这种结构。例如,Cisco公司于1997年推出的12000系列路由器 就采用了这样的结构。 从上述前三代路由器的结构变迁过程可以看到,处理路径的并行化是路由器发展的重 要方向。到单机分布式Crosbar结构为止,先是多个线卡的并行操作和主板分离,然后是 多条数据流通路的并行操作,表明在单机基础上的并行化工作已经进行得非常彻底了。要 想进一步提高系统的交换容量,需要更高层次的体系结构革新。 5.5 多机互连的集群结构 4. 网络运营商存放交换设备的地点通常称为POP(PointofPresence),它是网络中的交 通枢纽,连接了若干骨干线路,大量的数据流经POP再转发出去。在POP内部是一组核心 路由器。每台路由器连接部分骨干线路,这些路由器再彼此连接在一起。为什么采取这样 的结构呢? 这是因为,随着数据业务的增加,通常需要POP提供巨大的数据交换能力;另一 方面,因为网络环境日趋复杂,接入的线路也越来越多,因此,POP还需要提供大量的接口 (注:不作特别说明,“接口”指路由器上用于数据通信的端口)。这样,当一台路由器没法满 ·185· 足交换容量和接口数量的要求时,就需要通过多台这样的路由器,每台承担部分流量和接口 消耗,几台路由器再通过路由协议连接在一起,构成一个路由器群,完成对外的数据交换操 作,如图5. 8所示。 图5. 8 五台路由器通过接口进行全连接的路由器群 这种连接方法的浪费是显而易见的。因为路由器之间的连接也是通过接口完成的,在 提高整体容量的同时却占用了宝贵的路由器接口资源。而且,这种资源占用是随着连接在 一起的路由器个数的增加而超线性增长的。以路由器之间采用全连接为例,假设路由器的 个数为n,则占用的接口数为 N =n(n-1)。两个路由器占用的接口数为2,3个路由器占 用的接口数为6,而5个路由器占用的接口数就达到了20 。 另一方面,这样的连接方式很不便于管理。多个路由器是彼此相对独立的,需要单独对 每台路由器进行不同的配置,然后各个路由器之间通过路由协议进行交互。这种方式给管 理带来了很大的复杂性。另外,多个路由器之间的协议有交叉,在一些路由协议中,事实上 存在很多的类似计算和重复计算,造成很大的资源浪费。 如果路由器可以根据需求进行交换容量的自由扩展,则可以解决路由器速度和需求之 间的尖锐矛盾。可扩展的路由器结构应运而生。在这种路由器体系结构中,多个机柜可以 通过内部连接整合成一台新的大型路由器,又叫作路由器集群。每个机柜本身可以独立作 为路由器,也可以和其他机柜进行组合。与前面提到的多机柜互连不同,首先,互连不通过 网络接口进行,而是通过“内部”的连接完成,这样就不会占用宝贵的路由器接口资源;其次, 互连之后的路由器集群在管理操作和实际运行的路由协议实例方面,都是单一映像的方式, 也就是说,整个路由器集群的管理控制在外界来看“如同一台路由器一样”;再有,这种集群 结构在理论上可以进行无限制的扩展,这样,只要进行扩展,就可以满足不断增加的网络流 量需求。下面对这种路由器体系结构模型进行详细讨论。 4.可扩展集群路由器产品简介 5.6 为了满足大型互联网运营商的需求,各主要网络设备提供商纷纷推出多机互连集群结 ·186·