1、第三章第三章 路由器的硬件结构与路路由器的硬件结构与路由查询算法由查询算法本章提纲本章提纲v3.1 路由器的软硬件组成路由器的软硬件组成v3.2 路由器硬件体系结构的类型路由器硬件体系结构的类型v3.3 路由查询算法路由查询算法目标目标v了解路由器的硬件组成及各部分功能了解路由器的硬件组成及各部分功能v了解路由器硬件体系结构的类型了解路由器硬件体系结构的类型v掌握基本的路由查询算法掌握基本的路由查询算法本章提纲本章提纲v3.1 路由器的软硬件组成路由器的软硬件组成v3.2 路由器硬件体系结构的类型路由器硬件体系结构的类型v3.3 路由查询算法路由查询算法路由器的基本组成 输入输出部分路由器上的
2、网卡，工作在子网层（物理层和数据链路层），完成数据包的收发速度从10Mbps到几十Gbps甚至更高单个网络接口的网卡发展到集成多个网络接口的网卡 数据转发引擎完成路由查询，确定转发目的端口是路由器数据转发速率的决定性因素 交换结构连接输入输出部分和数据转发引擎，提供高速数据通道。总线结构（适于单个网络接口）、Cross-bar（交叉开关）结构（适于多个网络接口）影响路由器吞吐量的关键因素 路由计算部分根据网络拓扑选择路由协议，计算出路由表 中央处理单元（Central Processor Unit，CPU）只读存储器（Read Only Memory，ROM）随机存储器（Random Acce
3、ss Memory，RAM）闪存（FLASH Memory）非易失性随机存储器（Nonvolatile RAM，NVRAM）控制台端口（CONsole Port）辅助端口（AUXiliary Port）接口（INTerface）线缆（CABle）路由器的硬件组成路由器的硬件组成 中央处理单元（Central Processor Unit，CPU）作为路由器的中枢，CPU主要负责执行路由器操作系统（IOS）的指令，以及解释、执行用户输入的命令。CPU还完成与计算有关的工作。例如，网络拓扑发生改变时，重新计算网络拓扑数据库。路由器的硬件组成 只读存储器（Read Only Memory，ROM）R
4、OM中包括开机自检程序（Power On Self Test，POST）、系统引导程序以及路由器操作系统（IOS）的精简版本。随机存储器（Random Access Memory，RAM）RAM用来存储用户的数据包队列以及路由器在运行过程中产生的中间数据，如路由表、ARP缓冲区等。RAM还用来存储路由器的运行配置文件。闪存（FLASH Memory）Flash是可擦写、可编程的ROM。它主要负责保存操作系统的映像文件。非易失性随机存储器（Nonvolatile RAM，NVRAM）用来存储路由器的启动配置文件。在路由器断电时，其内容仍能保持。路由器的硬件组成 控制台端口（CONsole Por
5、t）供用户对路由器进行配置使用。不同的路由器可能有着不同形式的控制台端口，如RS-232异步串行接口，DB25母线连接器，更常见的是RJ-45控制台连接器。辅助端口（AUXiliary Port）用来连接调制解调器以实现对路由器的远程管理。接口（INTerface）数据包进出路由器的通道。不同路由器可能有着不同种类、不同数量的接口。常见的两种基本接口类型为局域网和广域网接口。每个接口都有自己的名称和编号。线缆（CABle）路由器软件组成1路由器操作系统2配置文件3实用管理程序路由器操作系统 路由器操作系统 路由器之所以可以连接不同类型的网络并对报文进行路由，除了必备的硬件条件外，更主要的还是因
6、为每个路由器都有一个核心操作系统来统一调度路由器各部分的运行。大 部 分 Cisco 路 由 器 使 用 的 是 Cisco 网 络 互 连 操 作 系 统（Internetworking Operating System，IOS）。IOS配置通常是通过基于文本的命令行接口（Command Line Interface，CLI）进行的。配置文件 配置文件 它是路由器的第二个主要的软件组成部分。该文件是由路由器管理员所创建的文本文件。在每次路由器启动过程的最后阶段，配置文件中每条语句被IOS执行以完成对应的功能。如配置接口IP地址信息、路由协议参数等。这样，当路由器每次断电或重新启动时，网络管理
7、人员不必对路由器的各种参数重新进行配置。配置文件并不能执行自身所定义的路由器操作的各个功能。实际执行这些操作的是路由器操作系统IOS。IOS负责翻译并执行配置文件中的语句。配置文件中的语句以无格式文本形式存储，其内容可以在路由器的控制台终端或远程虚拟终端上显示、修改或删除，也可以通过TFTP服务器上传或下载。配置文件有两种类型的配置文件：启动配置文件：也称为备份配置文件，被保存在NVRAM中，并在路由器每次初始化时加载到RAM中变成运行配置文件。运行配置文件：也称为活动配置文件，驻留在RAM中。当路由器的命令行接口对路由器进行配置时，配置命令被实时添加到路由器的运行配置文件中并被立即执行。但是
8、，这些新添加的配置命令不会被自动保存到NVRAM中。因此，通常对路由器进行重新配置或修改后，应该将当前的运行配置保存到NVRAM中变成启动配置文件。实用管理程序 Fast Step安装软件。使非技术用户可以非常轻松地迅速安装一个Cisco路由器。Cisco ConfigMaker路由器配置工具。用ConfigMaker可以创建所有Cisco路由器的配置，做好配置后通过网络传到路由器中。如果网络尚未开通运行，可以从运行ConfigMaker的计算机通过控制端口和路由器相连，并将配置导入到路由器。Cisco Works 网络管理软件。拥有思科全套产品的数据库，能调出各种产品的直观视图，并深入到每个
9、物理端口去查询状态信息。其功能具体包括：自动发现网络拓扑结构和设备；生成和修改网络设备配置参数；网络状态监控；设备视图管理本章提纲本章提纲v3.1 路由器的软硬件组成路由器的软硬件组成v3.2 路由器硬件体系结构的类型路由器硬件体系结构的类型v3.3 路由查询算法路由查询算法v集中式单（多）集中式单（多）CPU+总线结构总线结构CPU内存内存网络网络接口接口卡卡网络网络接口接口卡卡网络网络接口接口卡卡.缺陷缺陷CPU要负责整体系统的控制管理、路由计算和数据转发等要负责整体系统的控制管理、路由计算和数据转发等各项功能，存在计算瓶颈。各项功能，存在计算瓶颈。所有接口卡的数据都要争用总线，存在数据交
10、换瓶颈所有接口卡的数据都要争用总线，存在数据交换瓶颈。v分布式多分布式多CPU+总线结构总线结构主控主控CPU内存内存.CPU内存内存接口卡接口卡接口卡接口卡.CPU内存内存接口卡接口卡接口卡接口卡.CPU内存内存接口卡接口卡接口卡接口卡.线线卡卡线线卡卡线线卡卡特点特点路由计算和转发分离：主控路由计算和转发分离：主控CPU负责整个系统的控制管理负责整个系统的控制管理和路由计算（即运行路由协议，维护和更新路由表）；线和路由计算（即运行路由协议，维护和更新路由表）；线卡上的卡上的CPU负责查询路由表，对数据进行转发。负责查询路由表，对数据进行转发。部分地克服了总线瓶颈，即如果数据的接收和发送都在
11、一部分地克服了总线瓶颈，即如果数据的接收和发送都在一个线卡上，就不用争用总线；若数据的接收和发送涉及不个线卡上，就不用争用总线；若数据的接收和发送涉及不同的线卡，还是会出现总线争用问题。同的线卡，还是会出现总线争用问题。v分布式多分布式多CPU+Crossbar结构结构特点特点路由计算和转发分离。路由计算和转发分离。采用采用Crossbar的交换结构（的交换结构（Switch Fabric），），每个输入端每个输入端口和输出端口之间都有一个交叉开关，只要数据流彼此不口和输出端口之间都有一个交叉开关，只要数据流彼此不相关，就可以实现无阻塞的交换，解决了总线争用问题。相关，就可以实现无阻塞的交换，
12、解决了总线争用问题。基本上解决了路由器吞吐量的问题。基本上解决了路由器吞吐量的问题。交叉开关的设计和调度算法是研究的重点和难点。交叉开关的设计和调度算法是研究的重点和难点。v路由器硬件体系结构发展总结路由器硬件体系结构发展总结共享总线共享总线 交叉开关交叉开关路由计算与转发分离路由计算与转发分离本章提纲本章提纲v3.1 路由器的软硬件组成路由器的软硬件组成v3.2 路由器硬件体系结构的类型路由器硬件体系结构的类型v3.3 路由查询算法路由查询算法影响影响IP网络性能的关键因素网络性能的关键因素v链路速度链路速度v路由器的吞吐量路由器的吞吐量v包转发速率包转发速率v对路由变化的快速适应性对路由变
13、化的快速适应性v采用光纤等技术提高链路速度采用光纤等技术提高链路速度v在路由器中采用大容量的交换结构以提高吞吐量在路由器中采用大容量的交换结构以提高吞吐量v采用高效的路由查询算法和硬件路由查询方案提高包转采用高效的路由查询算法和硬件路由查询方案提高包转发速率（发速率（路由查询路由查询）v优化各种动态路由协议优化各种动态路由协议解决方案解决方案v为什么是最长前缀匹配而不是精确匹配为什么是最长前缀匹配而不是精确匹配CIDR等机制的引入：等机制的引入：IP地址是无类别的，从地址是无类别的，从IP地址不能地址不能判断出其网络前缀长度；判断出其网络前缀长度；IPv6单播地址也是无类别的。单播地址也是无类
14、别的。最长前缀匹配给路由查询带来很大的困难，因为不仅要考最长前缀匹配给路由查询带来很大的困难，因为不仅要考虑前缀的值，还要考虑前缀的长度。虑前缀的值，还要考虑前缀的长度。传统的关键字查找算法不能直接用于路由查询。传统的关键字查找算法不能直接用于路由查询。W.Doeringer,G.Karjoth,and M.Nassehi,“Routing on longest matching prefixes,”IEEE/ACM Trans.Networking,vol.4,pp.8697,Feb.1996.路由查询算法分类路由查询算法分类v按照采用的数据结构和实现方式，大致可以分为：按照采用的数据结构和
15、实现方式，大致可以分为：基于检索树（基于检索树（Trie）查找查找基于硬件基于硬件TCAM查找查找分段查找分段查找哈希表查找哈希表查找Cache命中查找等。命中查找等。v按照路由查询的依据，可以分为：按照路由查询的依据，可以分为：基于路由前缀值的查找基于路由前缀值的查找基于路由前缀长度的查找基于路由前缀长度的查找路由查询算法评价标准路由查询算法评价标准v时间复杂度（查找速度）时间复杂度（查找速度）v空间复杂度（占用的存储空间）空间复杂度（占用的存储空间）v更新复杂度（增加、删除、变更路由表条目时，路更新复杂度（增加、删除、变更路由表条目时，路由表的更新速度）由表的更新速度）v可扩展性可扩展性
16、v注意，上述复杂度一般是指最坏情况下的复杂度。注意，上述复杂度一般是指最坏情况下的复杂度。基本的二叉检索树（基本的二叉检索树（TrieTrie）根据唯一前缀原则把路由表组织成根据唯一前缀原则把路由表组织成一棵二叉一棵二叉树树问题：问题：使用二叉树仅为每个路由存储唯一前缀，而没使用二叉树仅为每个路由存储唯一前缀，而没有覆盖路由的整个网络部分。有覆盖路由的整个网络部分。为了确保选路正确，应保证整个网络前缀与路由匹为了确保选路正确，应保证整个网络前缀与路由匹配才转发数据报。配才转发数据报。为保证正确选路，外部节点必须完全匹配为保证正确选路，外部节点必须完全匹配(需需在外部节点在外部节点增加网络地址和
17、地址掩码增加网络地址和地址掩码)问题：若包含了子网路由和特定主机路由，则内节点问题：若包含了子网路由和特定主机路由，则内节点也有可能标识了路由。此时的策略如何？也有可能标识了路由。此时的策略如何？最长匹配选路策略最长匹配选路策略:相关内节点也包含地址相关内节点也包含地址/掩掩码对码对，并且按最长匹配选路，并且按最长匹配选路 。唯一前缀唯一前缀000100010101110101011032比特地址（目标项）比特地址（目标项）00110101 00000000 00000000 0000000001000110 00000000 00000000 0000000001010110 0000000
18、0 00000000 0000000001100001 00000000 00000000 0000000010101010 11110000 00000000 0000000010110000 00000010 00000000 0000000010111011 00001010 00000000 0000000010111000011100101181.12.0.0，255.255.0.0例：假如目标地址是：例：假如目标地址是：10111011 10111011 10100000 00000000 0000000110100000 00000000 00000001若仅查二叉树，则出现错误
19、！若仅查二叉树，则出现错误！31下一跳10.0.0.210.0.0.410.1.0.510.0.0.610.0.0.310.0.0.6前缀128.10.0.0/16128.10.2.0/24128.10.3.0/24128.10.4.0/24128.10.4.3/32128.10.5.0/24128.10.5.7/3210.0.0.3问题：路由表中含有同一网络的一般路由和具体路由。000111012815个00173128.10.0.0/16128.10.4.0/24128.10.4.3/32路径压缩路径压缩Triev该算法是对基本二叉检索树的改进，最早起源于该算法是对基本二叉检索树的改进，最
20、早起源于Patricia算法，算法，后来后来Sklower对对Patricia算法做了改进，使之可以用于路由查询。算法做了改进，使之可以用于路由查询。v其其基本思想基本思想是去掉没有分支的节点，所谓没有分支的节点是指是去掉没有分支的节点，所谓没有分支的节点是指一个几点不同时有左子节点和右子节点，同时该节点也不是有一个几点不同时有左子节点和右子节点，同时该节点也不是有效节点。效节点。v由于去掉了一些节点，某些比特将被忽略，所以节点要维护一由于去掉了一些节点，某些比特将被忽略，所以节点要维护一个变量，用于维持下一个要检查的比特位。个变量，用于维持下一个要检查的比特位。BDEA 0*B 1*C 00
21、1*D 10*E 110*A/CABDE000011C1A 0*B 1*C 001*D 10*E 110*多比特检索树（多比特检索树（Trie）v在基本的二叉检索树中每次检查一个比特，即一级对应在基本的二叉检索树中每次检查一个比特，即一级对应1个个比特；如果比特；如果让每一级对应多个比特让每一级对应多个比特，就可以大大降低树的深，就可以大大降低树的深度。也就能够降低路由查询的时间复杂度。度。也就能够降低路由查询的时间复杂度。v每一级对应的比特数被称为每一级对应的比特数被称为查找步宽查找步宽。同一级的步宽可以一。同一级的步宽可以一样，也可以不一样。前者实现起来比较简单，但浪费存储空样，也可以不一
22、样。前者实现起来比较简单，但浪费存储空间，后者实现复杂一些，但是会节省一定的存储空间。间，后者实现复杂一些，但是会节省一定的存储空间。v因为一次查找多个比特，因此不能处理任意长度的路由前缀，因为一次查找多个比特，因此不能处理任意长度的路由前缀，一般要使用前缀扩展。一般要使用前缀扩展。每一级的步宽都是每一级的步宽都是2 第一级的步宽是第一级的步宽是2 第二级三个节点步宽第二级三个节点步宽是是2，一个节点步宽是，一个节点步宽是1对于上图中绿色部分，如何应用多比特检索？对于上图中绿色部分，如何应用多比特检索？v前缀扩展：将一条较短的路由前缀展开成多条较长的路前缀扩展：将一条较短的路由前缀展开成多条较
23、长的路由前缀集，这些前缀集的转发信息就是原来地址前缀所由前缀集，这些前缀集的转发信息就是原来地址前缀所对应的转发信息。也就是扩展后的路由前缀要继承原来对应的转发信息。也就是扩展后的路由前缀要继承原来前缀的转发信息。例如，前缀的转发信息。例如，1*可以扩展为可以扩展为10*和和11*。v对于对于Trie中不能直接应用多比特树的地方，可以先进行中不能直接应用多比特树的地方，可以先进行前缀扩展，使应用多比特树的局部成为一个满的子树。前缀扩展，使应用多比特树的局部成为一个满的子树。101*111*1010*1011*1110*1111*v由于步宽大于等于由于步宽大于等于1，使检索树的深度明显降低，所以
24、多比特检索，使检索树的深度明显降低，所以多比特检索树的时间复杂度比基本二进制树的时间复杂度比基本二进制Trie或路径压缩或路径压缩Trie要低，具体的数要低，具体的数值与每一级步宽有关。当每一级步宽都是值与每一级步宽有关。当每一级步宽都是K时（这是多比特检索树时（这是多比特检索树中最简单的情况），时间复杂度为中最简单的情况），时间复杂度为O(W/K)。v时间复杂度降低的代价就是空间复杂度的上升，每一个中间节点时间复杂度降低的代价就是空间复杂度的上升，每一个中间节点都需要包含都需要包含2k个指针（每一级步宽都是个指针（每一级步宽都是K），），最差情况下每加入一最差情况下每加入一个新前缀，需要插入
25、个新前缀，需要插入W/K个中间节点，从而需要占用空间个中间节点，从而需要占用空间O(2k*W/K)，所以空间复杂度为所以空间复杂度为O(N*2k*W/K)。v更新时需要进行一次路由查找，然后更新节点的指针，最差情况更新时需要进行一次路由查找，然后更新节点的指针，最差情况下需要更新下需要更新2k-1指针，所以更新复杂度为指针，所以更新复杂度为O(2k W/K)。v对于多比特检索树来说，当步宽为对于多比特检索树来说，当步宽为1时，就成为基本二叉检索树或时，就成为基本二叉检索树或路径压缩树路径压缩树，当步宽达到当步宽达到W时，时间复杂度为时，时间复杂度为O(1)，但空间复杂但空间复杂度变为度变为O(
26、2W)。v很显然，多比特检索树的主要问题就是引入了很多冗余路由前缀，很显然，多比特检索树的主要问题就是引入了很多冗余路由前缀，占用了大量存储空间，所以对它的优化是研究的一个重点，例如占用了大量存储空间，所以对它的优化是研究的一个重点，例如有些人就提出了步宽选择策略，也有人提出了一些压缩算法。有些人就提出了步宽选择策略，也有人提出了一些压缩算法。v实际进行压缩时可以考虑互联网地址分布的特点，例如长度实际进行压缩时可以考虑互联网地址分布的特点，例如长度1624之间的前缀数最多。之间的前缀数最多。v叶子扩展的概念叶子扩展的概念0*110*10*111*0*11*1*111*路由前缀长度空间的二分查找
27、路由前缀长度空间的二分查找vTrie树算法的实质是地址前缀长度空间的线性查找：先检查第树算法的实质是地址前缀长度空间的线性查找：先检查第1个（个（1k）个比特，再检查第个比特，再检查第2个（个（k+12k）个比特，一直个比特，一直到路由前缀的最大长度为止。到路由前缀的最大长度为止。v文献文献“Scalable high-speed prefix matching，Marcel Waldvogel,George Varghese,Jon Turner,Bernhard Plattner，ACM Transactions on Computer Systems,2001”提出了地址前提出了地址前缀
28、长度空间的二分查找法。缀长度空间的二分查找法。v基本思想是把所有路由前缀按照其长度分为不同的前缀集合，基本思想是把所有路由前缀按照其长度分为不同的前缀集合，每个前缀集合内采用哈希算法查找；查询时，从长度位每个前缀集合内采用哈希算法查找；查询时，从长度位W/2的的集合开始，采用二分查找法。集合开始，采用二分查找法。W/23W/45W/87W/8W/43W/8W/84657231图中节点对应的是前缀集合，而不是某个或某几个比特位图中节点对应的是前缀集合，而不是某个或某几个比特位v为了保证该算法的正确性，需要引入一个被成为为了保证该算法的正确性，需要引入一个被成为Marker的表的表项。考虑下面的例
29、子。有项。考虑下面的例子。有4个地址前缀：个地址前缀：0*、1*、00*、110*。现查找现查找110*。0*1*00*110*2130*1*00*11*(Marker)110*213v路由前缀长度空间的二分查找在路由查询方面的时间复路由前缀长度空间的二分查找在路由查询方面的时间复杂度为杂度为O(logW)，对对IPv4来说，最多需要来说，最多需要5次查询，对次查询，对IPv6来说，最多需要来说，最多需要7次查询。次查询。v对于每个前缀，最多可能需要对于每个前缀，最多可能需要logW个个Marker，因此，因此，算法的空间复杂度为算法的空间复杂度为O(N*logW)。v路由更新比较麻烦，其复杂
30、度为路由更新比较麻烦，其复杂度为O(N*logW)，因为最坏因为最坏情况下更新一个前缀可能影响情况下更新一个前缀可能影响N-1个前缀，而一个前缀个前缀，而一个前缀又有可能对应又有可能对应logW 个个Maker。v哈希算法也是该算法中的关键问题。哈希算法也是该算法中的关键问题。TCAMvTCAM（Ternary Content Address Memory）是一种新型的是一种新型的存储器，存放一系列路由表项，为到来的每一个分组并行查存储器，存放一系列路由表项，为到来的每一个分组并行查找所有的路由前缀。因此，它的路由查询只需要一次内存访找所有的路由前缀。因此，它的路由查询只需要一次内存访问，若有
31、多个匹配表项，经过优先级比较后，确定路由信息。问，若有多个匹配表项，经过优先级比较后，确定路由信息。v路由管理比较复杂，路由表的动态删除和更新会导致路由管理比较复杂，路由表的动态删除和更新会导致TCAM中存放大量的碎片。中存放大量的碎片。v成本昂贵，功耗比较大，存储容量小。成本昂贵，功耗比较大，存储容量小。v这实际上是一种硬件查找方法。这实际上是一种硬件查找方法。基于分段的查找基于分段的查找v这种方案实际上是多比特检索树的具体硬件实现方案。典型的是这种方案实际上是多比特检索树的具体硬件实现方案。典型的是Gupta等人提出的等人提出的DIR-24-8-BASIC查找算法。查找算法。vDIR-24
32、-8-BASIC算法是把算法是把IPv4地址空间分为长度分别为地址空间分为长度分别为24和和8的两部分的两部分（TBL24和和TBLlong），），最大内存访问次数为最大内存访问次数为2，采用硬件流水线技术可，采用硬件流水线技术可以用以用1次内存访问。第一部分是次内存访问。第一部分是22416M个表项；第二部分个表项；第二部分256个表项。个表项。v因为是基于多比特检索树，因此需要进行前缀扩展。因为是基于多比特检索树，因此需要进行前缀扩展。v第一级中的节点携带的指针信息指示可能存在于第第一级中的节点携带的指针信息指示可能存在于第2级中的一棵子树。级中的一棵子树。指针指针下一跳信息下一跳信息10
33、下一跳下一跳基基地地址址下一跳下一跳信息信息TBL24TBLlong偏偏移移量量缓存（缓存（Cache）策略策略v缓存策略是指把最近查找过的目的地址和路由下一跳缓存策略是指把最近查找过的目的地址和路由下一跳信息放在缓存之中，当信息放在缓存之中，当IP分组达到时，先从缓存中查分组达到时，先从缓存中查找，找不到时再执行最长前缀匹配策略。找，找不到时再执行最长前缀匹配策略。v显然，数据包的相关度越大，这种方法的有效性就越显然，数据包的相关度越大，这种方法的有效性就越高。高。v缓存的命中率是这种策略的一个关键。由于缓存容量缓存的命中率是这种策略的一个关键。由于缓存容量有限，且数据日益多样化，缓存的命中
34、率大大降低。有限，且数据日益多样化，缓存的命中率大大降低。哈希查找哈希查找v哈希哈希(Hash)算法在路由查询中应用的时候，通过查找建立的算法在路由查询中应用的时候，通过查找建立的哈希索引，来找到对应的路由前缀。哈希索引，来找到对应的路由前缀。v理论上讲，哈希算法的时间复杂度和空间复杂度都很低，但理论上讲，哈希算法的时间复杂度和空间复杂度都很低，但实际上很难找到一个完美的或者近似完美的哈希函数。另外，实际上很难找到一个完美的或者近似完美的哈希函数。另外，路由更新也往往会导致哈希表的重建。路由更新也往往会导致哈希表的重建。v一般来说，把整个路由表做为一个哈希表是不切实际的，可一般来说，把整个路由表做为一个哈希表是不切实际的，可以在局部范围内应用哈希算法。如在前缀长度空间的二分查以在局部范围内应用哈希算法。如在前缀长度空间的二分查找中，就可以在同一前缀长度的前缀集合内应用哈希算法。找中，就可以在同一前缀长度的前缀集合内应用哈希算法。其他路由查询算法其他路由查询算法v层压缩树层压缩树v地址区间的二分查找法地址区间的二分查找法v多路和多列查询算法等多路和多列查询算法等
