流水技术用于提升路由器性能的分析与研究论.doc

流水技术用于提升路由器性能的分析与研究学生： （指导老师： ）（淮南师范学院计算机学院）摘要：随着互联网技术的发展和各种类型的网络应用的出现，使得网络的服务质量受到了巨大的挑战和关注，许多研究人员发现单纯的加大带宽并不能解决这个问题。由此观之，路由设备是网络首要连接器件。它的性能将即刻反应网络服务质量。本文是在流水技术方面做了探究的。其最重要的目标是来增加路由器的性能。在路由器的高速转发过程中，着重研究流水技术的应用。关于转发引擎在速度进展方面，它对其进行了透彻的研究。提升转发引擎必须面对困境。通过应用多种方法（多种办法里包括TCAM等方法），为高速转发引擎指出了新的思想流水线机制的高速转发引擎。这种方法能增多路由器的性能。从而能够解决网络服务质量的问题，让路由器不再成为是制约网络发展的关口和约束。关键字：路由器 网络服务质量 高速转发引擎 流水技术 并行流水技术 Water technology is used to improve the performance of router analysis and researchStudent: (Faculty Adviser： )(Huainan normal university computer college)Abstract: With the advent of Internet technology and various types of network applications, so network quality of service has been a huge challenge and concern, many researchers have found a simple increase bandwidth does not solve this problem. From this perspective, the routing device is the primary network connection devices. Its performance will be immediate reaction network quality of service. This article is made inquiry in water technology. Its most important goal is to increase the performance of the router. In the high-speed router forwarding process, focusing on application of water technologies. About forwarding engine speed progress, it was carried out thorough research. Enhance the forwarding engine must face difficulties. By using a variety of methods (a variety of approaches in other methods including TCAM), high-speed forwarding engine pointed out new ideas - pipelining of high-speed forwarding engine. This method can increase the performance of the router. It is possible to solve the problem of network quality of service, so that the router is no longer a barrier restricting network development and constraints.Keywords: The router Network quality of service High-speed forwarding engine Water technology Parallel flow technology前言路由器是整个互联网设备中的枢纽，它是相互之间有差别的网络进行彼此联接的核心，路由器是Internet的全部框架的组成者，它的处理速度在网络快速发展中是一大制约因素。因此，在未来整个因特网研究领域，路由器技术处于并且将长时间的出去要害地位，它的发展过程也将成为整个因特网研究的一个重要写照。现今网络发展速度，不可小观。随着网络快速成长，它在路由器的性能方面，提出了愈来愈高的要求。为了适合于下一代网络的高速度的需求，路由器正在被挑衅。为了对路由器的性能加以提升，许多先行者会有很多在路由器上研究。对于路由器高速转发技术，他们是研究的方向之一。高速转发技术中引入流水线技术。这是现今提升路由器的一个重要探究方向。流水线技术可谓是很好一种方法。它将串行处理转变为并行处理。简单在运行操作期间，多条指令一起执行。流水技术能够提升指令的运行功效。其利用的方法是对各个部件的使用来兑现的。路由器是整个网络重要组成部分，流水技术在路由器中应用也将在提升路由器性能发挥巨大作用。本文对路由器的工作原理、转发过程、体系结构等理论进行了简要的概述，对于流水线进行了基本概念的叙述和有关问题的说明，并且流水技术在路由器中的应用。1 路由器的概述1.1路由器产生网上的最重要的设备是路由器。它用于连接不同的网络的。传输控制协议/互联网络协议(Transmission Control Protocol/Internet Protocol，简称TCP/IP)是在美国国防部ARAPNET基础上发展过来，时间为上世纪70年代。美国军方期望能够在它帮助下，使得不同广域网和局域网能够互相通信。让路由器称为一种不能够被交换机所替换的设备，这样可以确保网络即使在遭受战争打击后也能够相互连接通信。在这种历史背景下，路由器的产生就称为了必然结果。1.11路由器基本结构和发展历程网络接口路由引擎路由表转发引擎内部交换网络接口控制路径路由更新控制路径路由查找数据路径图1路由器基本结构图据图1，路由器的基础构造能够从图1中看出，网络接口、引擎模块（包括转发和路由的引擎）和内部互换模块这四个功能模块构造了路由设备。从图1中可以看到物理链路和网络接口。它们是直接连接的。处理互相对应的物理传输数据报文模块、将网络报文接收和发送任务完成，都是有网络接口实现的。高速路由查找需要一种特种设备。路由器转发引擎是其所需的。转发引擎是具有数据包发送途径决策的任务。路由设备由内部处理模块实现，其对高层协议操作。路由引擎有很多工作。它对高层协议进行操作，特别是路由协议。整个路由设备稳定工作也是由路由器来负责。整个路由器稳工作包括维护各个网络之间状态的一致性，监控系统状态等工作。这些工作任务都是经由路由设备引擎来实现的。路由引擎模块和网络接口连接。它们之间进行的数据传输。其传输过程中提供高速数据路径。这是内部交换模块的任务。另外，从图1中能够看出路由设备提供哪一种路径是依据网络报文来确定。数据路径处理的目标地址是需要转发网络报文，路由器的整体性能都受到它的影响。固然处理的目标地址（在控制路径上的）不处于路由器的要害途径，然而它在路由器报文转发时提供了准确讯息。身为互联网关卡的路由器现在正向着运行速度不断增加、服务在质量的更好以及更便于管理的方向发展。随着网络速度的不段发展，路由器也在几个方面快速发展着，这个几个方面主要是：引擎模块划分为路由引擎和转发引擎，它们之间相互独立、在路由表上，对全局路由表和局部转发表的划分、硬件设备上，我在对于网络之间互连的协议（Internet Protocol，简称IP）的报文，要实现报头的快速处理、对于路径，要进行搜索和发送、转变中央处理器为中央处理控制器。将接口卡模式转变为许多个单元。这个单元是分布式的接口，这样，新的方式将上述的方式替换、提高数据通信速度使用的交换结构。路由器在成长的历程中，走过了两个过渡阶段。一个是历经了单个处理器阶段向并行处理器的过渡阶段。另外一个由总线的同享向结构的交换的过渡阶段。目前路由器又提出在大规模并行工作处理技术的结构体系基础上，路由器性能在路由器结构体系的发展下不断提高。1.12路由器研究现状现有的高性能路由器技术基快速发展。高端路由器的成长方向和探究方向基本上都关注在四个方面：首先是硬件将在并行工作处理技能中广泛采用的；第二方面是协议处理将专注于分布式处理技术；第三方面是在网络骨干节点多粒度路由提供流量控制和管理技术。最后的是路由协议在算法的改进。而且智能路由技术（这种技术有约束条件）将基于距离准则替代。思科，Juniper，华为，上海贝尔艾尔卡特、中兴等企业是目前的高水准路由器的来源。主流的高端设备都有很强的能力。例如，高于360G的交换能力、G比特每秒单端口速率等。许多制造商走的是中低端路由器路线。在上文中提到的制造商之外，比威，神州数码，迈普等制造商也从事制作中低端路由器。具有强大的适用范围中低端设备，在定位和功能形态上都各有不同，差距很大，这里也不再对它们详细阐述了。1.2 路由器体系结构（1） 从上文所述的路由器的发展历程，我们可以看出路由器体系机构的变化。一般路由器的结构体系可以分为三种类型：在同享总线方面，单个处理设备的体系结构和多个处理设备结构以及互换机制的多个处理设备体系结构。下面对于上文中提到体系结构进行详细阐述（2） 单个处理总线体系结构CPUmemorybusLineCardLineCardLineCard图2 单个处理器结构体系图2呈现的是经典的路由器结构系统。它是基于总线的路由器结构体制。整个数据报文转发过程是：数据报文首先抵达接口卡，然后将报文发送给中央处理器（Central Processing Unit，简称CPU），CPU对路由表进行搜索，然后根据搜索结果做出下一步的地址的选择，最后通过其他的接口卡将报文转发出去。从上述报文转发过程中，可以看要通过两次才能将数据转发出去。这成为了制约整个系统因素。在路由器的传统总线结构中央处理器是要完成很多工作的。例如包的转发、路由协议等。整个系统都依赖于路由器的CPU，从而可以得出这种系统的缺点有：1）路由设备的报文都由中央处理设备来进行执行操作，中央处理设备成为制约因素。2）报文转发涉及存储器访问，CPU处理不能成线性处理，访问存储器时间成为主要的制约者；3）总线结构的交换方式对高速转发无法支持。（3） 多个处理共享总线体系结构CPUmemoryLine cardProcessMemoryLine cardProcessMemoryLine cardProcessmemoryProcessmemoryProcessmemoryProcessmemoryCPU MemoryLine cardLine cardLine card图3 多个处理共享总线结构这种体系结构是在传统的路由器结构中的改进，其主要的理论是用多个处理部件来分解处理报文转发。如图3所展示的一样，图中有在多处理共享总线体系结构有存在两种。其分别为分布体系结构和并行式体系结构。其中，分布式体系结构的工作原理是一个线卡上报文要由对应其线卡的处理器来进行操作。另一种的原理是将相互独立的线卡和转发处理器在共享总线的上连接。并行体系结构已经初步有了流水线操作的模式，它在处理过程同时对数据报文进行路由查找和数据缓存的操作，完成报文的更新和发送报文数据部分。从总线带宽上看，这种方法节约了花费。（4） 多个处理互换机构结构体系LineCardLineCardLineCardForwordEngineForwordEngineForwordEngineCPU memoryLineCardLineCardLineCardCPU memoryForwordEngineForwordEngineForwordEngine图4 多处理互换机构结构体系这种体系结构在第二代路由器的基础上，使用了交换机构方式作为背板传输的方式，而且使用集成电路（Application Specific Integrated Circuit,简称ASIC）替换了通用CPU，使得路由器的性能大大提高。通过对路由体系研究与分析，我们可以看出传统路由工作模式依然是串行模式，路由器的转发性能的不到提高，因此，本文中将引入流水线机制，在路由转发的过程中改变传统路由器的工作模式，使得路由器作业流水化、并行化，从而提高路由器性能。本次论文将论文的第二部分和第三部分对流水技术和如何使用流水技术提升路由器性能做详细阐述。1.3 路由器的工作原理在开放式系统互联（Open System Interconnection，简称OSI）七层协议中，它位于网络层，并且在其中工作。每当一个网络层发送的数据报，路由器对其接收和做直线前进，给自己连接到网络或转发到另一个路由器或丢弃该数据报的决定。路由器使用的源地址和目的地址的网络层的信息进行转发的信息。据此确定将信息转发到哪个网络。假如同一个网络中包含了源网络和目的网络号，则传递到该网络所指定主机。一个信息包在抵达路由器以后立即进入队列，然后路由器遵从以下顺序进行处理：获取数据信息包的目标地址，对路由表进行检查，若是抵达目标地有超过一条以上途径，那么路由设备在对选择道路途径的中，他会选择最佳路径，路由器的选择时除了上面说的，在互联网上的路由器的延长时间，分组长度和指定的服务类型等因素来综合分析的数据集，然后根据这些做出决定，在道路途径上选择最优的一个的决定。下面对路由设备对于路由的选择算法说明（以IP路由器为例）：保存目的地网络号码于路由表中，当路由器接收到IP数据信息报文之时，首先找到IP数据信息报文的目标站点的地址（即IP地址），由IP路由设备将其获取，计算出目的站点的网络号（网络号是属于目标站点所在的网），然后依据计算出的网络号查找路由，最后决定该IP数据报要通过哪个接口发送出去。在TCP/IP协议控制下，数据包到达路由器后，对于数据包，路由器将进行拆除报头（报头属于数据链路层）操作，查找到目标地址（其属于网络层）。当目的地址被获取。路由器就会对路由表进行查看。通过路由表搜索到目标地址。最后获取目标地址的路由。整个数据包的转发过程为：第一：数据包的报头先进入路由器的入站口，通过多路访问控制(Multiple Access Control, 简称MAC)过程找到可用的硬件的目的地址，如若MAC过程中找到目的地址，就会使用循环冗余校验（Cyclical Redundancy Check，简称CRC）来对数据信息包的帧来确认这个帧没有被破坏。通过CRC校验，拆包，丢弃该帧。在由路由设备的内存中将数据信息包保存后结束。第二：路由器运行搜索的操作。这个操作在路由表中运行。其后获取匹配地址（该地址为最长的数据信息包报头的目标地址）。如若符合，该路由将由路由器为其搜索到下一跳的地址或者是直连的接口上（其中，若是存在一个直接连接的接口，它被指向路由，我们可以就可以跳过下一步而没有执行递归查找）。反之，匹配不符，路由也未发现默认网关，数据包会被丢弃，并且会发送网络控制信息协议（Internet Control Message Protocol，简称ICMP）不可达到的消息给原设备。第三：当下一跳地址被获取，递归查找操作被路由器执行。这么做的目的便于直连的接口（在路由器上），找到表项（位于流出接口的），然后把数据包转发出去。如若递归操作被运行后未获取到IP地址(在表项的上的），也没有默许的网关，那么路由器会出现两种操作：一是将该数据包扔掉，二是利用ICMP发消息给数据包源。第四：出站口缓冲器有自己的作用。它接收被交换的数据包。其交换过程主要通过ARP技术实现。第五：路由器根据直连接口和下一跳的连接类型。将合适的数据链路帧封包装入数据包。在传输线上有出站接口。其放置携带下一跳地址的帧（该帧属于数据链路层）。在数据信息包到达目标地之前，这个包的转而发送过程都要被路由设备控制运行。1.4路由器的基本功能和特点路由器有一个最重要的功能。它就是“路由”的作用。简单的来说就是“方向导航”功用，基本上是用来对数据信息包的转而发送时为其指清楚方向的功能。若是详细的划分，路由器的“路由”作用可以区别为以下两个方面：（1）路由选择根据地址（由网络层提供的），使用路由表为IP数据包选择到达目标地的最好途径，换句话说就是通过路由器的选择算法选择一条最佳的途径到目的地。为了目标的完成，每个路由设备都会建成并保护路由表，在路由表中，其包涵盖了能够被本地连接的所有的网络。在路由表的基础上路由设备查找数据信息包所要选取的最好的途径。路由表中包括路由的有关信息。路由器利用这些信息转发数据包使达到非直连远程网络。一条路由蕴含了目标网络地址、掩码、网关或者接口地址、路由开销或度量等讯息。（2）存储转发路由设备首先让自己的以连接端口获取一个IP包，然后，在经由路由设备另一个连接端口发送出去。如果我们想区分关于路由的算法是动态算法和静态算法，我们可以通过网的拓扑结构和通信的应变能力来判断。静态路由算法又称为非自适应路由选择算法。其特征是更加简洁，花费少，结构简单，但无法立即适应网络的状态的改变。动态路由算法又称为自适应路由选择算法，其优点是迅速在网络状态的变化并做出相应的反应，缺点是更复杂的完成，成本也比较大。路由器的主要特点是：（1）路由器，不一样的MAC协议，不一样的传输介质，不相同的拓扑结构和不一样的网络不同的传输速率是相互连接的，具有很强的异构网络互联能力。（2）路由器是一种设备。它的功能体现在存储转发上。它在相互连通的远程网上，有着很强大的使用性。在远程网上，它具有强大相互连接能力。它被较大范围的使用在远网和局域网之间互联互接情况里。（3）在逻辑上相互不相同的的子网络可以凭借路由器连接在一起，其中每个子网络全部看一个单一的子网广播域，因此在子网网络与子网路之间，广播信息在路由器中不会流通。因此，路由器有这个能力。它可以去阻隔广播信息。（4）路由器具备很多能力，例如流量控制、拥塞控制的能力，可以对异种速率网络之间进行速度匹配，用来确保数据包可以准确地进行传输。（5）路由器忙碌于OSI的第三层。OSI第三层也就是网络层。它是与网络层的各种协议都有着紧密联系。多种协议路由设备可以支撑许多不同种网络层的协议（例如：IPX，DECnet，TCP / IP协议），数据包转发在异种网络的协议之间。（6）路由设备对于网络层面的地址进行检查，从而发送数据的分组（Packet）。当然，该该数据分组来自网络层。出于这个原因，路由设备能够根据网络协议地址来进行数据包的过滤,路由设备使用访问控制列表(Access Control List,简称ACL)根据各种协议封包装入的数据信息包并且对封包装入过程加以掌控。同样，TCP、UDP端口号也会被实施数据过滤。（7）首先对较大规模的网络划分为微小段化，然后将划分为微小段后的网段运用路由设备互连在一起。这方法不仅达到在网络上提高性能，提升网络的带宽的目标。另外，这种方法有利于管理网络和维护网络。其亦是一个网络同享的方法通常是带宽问题解决方案。（8）路由设备即可以在中、小规模分级集中网中进行运用。同样适合在大规模、情况多变的互联网络环境。（9）路由器有很好的分离效果。它具体体现冲突域和广播域中。2 流水技术的研究2.1流水技术的基本概念2.1.1什么是流水线技术流水线（pipelining）是一种将串行工作的方式转变为并行工作的技术，在程序运行期间，若干条指令在时间上重叠进行并行操作的。关于计算机的系统结构性能上，流水线技术是一种十分好方法。它可以提高计算机系统性能。重复的过程，它将流程进行了重新规划，把原本该是顺序执行的流程，重新划分成相对独立的流程，但在耗时上却相当步骤，提高资源途径等方法来，在时间方面或者资源方面，让这些步骤之间相关性解除，这样他们就可以实现并行到一定程度，从而达到优化性能的目的。在最初的时，CPU的内部结构中最先运用到流水线技术，它被分为两种：一是部件级别的流水，二是处理设备级别的流水。2.1.2流水线的特点在处理器方面，让两种方式进行对比，这二者是：一是传统的串行方式，二是流水线方式。它们特征如下：（1）持续不断地操作是流水线处理的前提。在这种前提下，才能将流水线的效率发挥出来。若断流，则会效率会变差。（2）在流水线过程中，运行一个操作过程可以分解成多个子操作（它们之间有互联关系），并分别让专门的功能组件运行。（3）缓冲寄存器位于在每个功能组件之后，作用是缓冲本步骤的执行之后所得到结果的，这是因为在每一段间延迟不平等，因此必须使用缓冲寄存器解决。（4）同时有多个操作在执行。每一个子操作的功能组件工作在并行状态，但各个功能组件上正在运行的是不一样的操作。（5）各个子任务执行的时间应尽量相等，如果延时过长将造成“断流”问题。2.2流水技术的主要性能指标与许多其他的计算机技术一样，流水技术作为计算机的技术也有着自己的性能指标。流水技术的性能指标不仅仅关系着流水技术的好坏，而且对于使用流水技术的路由器也有着十分重要的影响，所以下面我们来对流水技术的性能指标加以分析。指标一：吞吐率流水线的吞吐量是单位时间内其流水线处理指令数，或者说是从流水线中，我们能够获取输出的结果数量。流水线的最大吞吐率是一个关于吞吐的数量。这个吞吐量仅仅当流水线来到一个稳定状态后，才会发生。若各个功能阶段的时间相等，那么ti=t0 TPmax=1/t0，若各功能段时间不相等，TPmax=1/max（ti）由花费时间最多的功能段所决定。计算吞吐率的公式为：在这个公式中，操作数是n，是完成全部操作的时间。为了对流水线的最大吞吐率进行提升，首先要找出阻碍吞吐率的制约因素，然后想办法解除制约因素。解除这种因素有两种方案：一是将制约因素子过程再次逐一划分，二是多次设立多个制约因素区让它们并联在一起，允许它们交叉进行。第二种方法，首先要把在各并行子过程之间的任务分配合同步控制解决好，其与把制约因素子过程再细分控制过程相比，它更加要复杂、需要的设备量更多。指标二：加速比 有一条流水线采用串行模式。然后将它更改为流水模式，流水速度两者比值被称为加速比。加速比通常用来衡量流水线的工作安排合理程度。则流水线的加速比为：公式中 是在顺序执行期间所要花费的时间， 是采用用流水线方式后执行花费的时间，其就是加速比的公式。指标三：效率在时间上，流水线中的设备实际使用的花费和整体运行的花费比称为流水线效率。简单来说流水线效率就是流水线中设备的使用率。如图5所示，流水线的效率是在时空区进行定义的，具体来说：n个操作任务在现实中使用的时空区和多个（公式中用k表示）功能阶段的总的数量的的比值。一个段线效率用公式表示为：它就是是计算流水线的效率的基本公式。1 2 3 4 5S5S4S3S20mt(n-1)tS1(段号)sttn-1 tn tn+4t1 t2 t3 t4 t5n-1 nn-1 nn-1 nn-1 nn-1 n1 2 3 4 51 2 3 4 51 2 3 4 51 2 3 4 5填入填满（正常）排空 图5 流水线的各区间构成和时空图2.3流水线技术的相关问题流水线中会出现流水相关现象。造成这种现象的原因是指令流（流水线上的工作），受到某种缘故的影响，在指令的一个时钟内，流水部件无法完成应该完成的的操作，这种现象我们就称为流水线相关。流水线相关现象促使了流水线性能滑落，使得加速比大大的小于理想情况。下面就流水线相关的三个方面开始分个讨论。2.2.1资源相关多指令进入流水线，在同一个机器周期，在对相同的组件资源的竞争引起冲突。有一些不能够完全流水化生产功能部件的根本原因就是造成了资源相关。流水冲突产生的另一个关键原因就在于系统中，对流水线中的组合所有指令的情况分析，使硬件资源数量充足。解决的方法有1）完全流水化功能部件；2）根据流水线中指令组合，设置足够多的资源。2.2.2数据相关数据相关就是指在一个程序中，在前面的一条条指令执行完成情况下，后面的一条的指令才能被执行，因此，我们可以知道这两条指令就是数据相关。数据相关可以划分三种，它们是指令相关、主存空间数相关和通用寄存器组相关。解决数据相关的方案有：一就是退后分析法，在碰到数据冲突时候，暂不对本条指令进行分析，等到本条指令所需数据写入，才开始分析本条指令的操作。二是建立一个专门的路径，原理是操作必要数据直接从专用路径中获取，不需要再等待操作需要的数据写入该指令存储单元中。2.2.3控制相关由于程序在运行过程中，也许其运行方向发生变化造成的冲突，这种相关叫做控制相关。它亦被称为局部性相关。解决的方法有：（1）延迟转移法延迟转移法的理论是让前面少数不相关的指令和转系指令互换位置，使得成功转移指令在少数指令执行后才开始执行，这种方法可以减少转移造成的性能损失。这种方法用软件实现。（2）转移预测法在指令过去行为的基础上，我们可以来预先猜想指令未来可能出现的行为。我们要达到预定猜想，在指令预取队列器和目标指令缓存的帮助下，可以在取指阶段提前进行转移预测。其中这种方法用硬件来实现。3路由器的转发引擎分析3.1路由器的转发引擎的概述3.1.1转发引擎概述伴随路由器结构体系的改进，它的内部的转发引擎也在持续的高速发展着。现今路由器中最典型的路由器结构就是如图6呈现的。它是一种分布式的并行多处理结构。从图6中我们可以直观的看见转发引擎在路由器中处于什么位置。外部接口线路接口模块线路接口模块线路接口模块转发引擎模块转发引擎模块转发引擎模块转发引擎模块转发引擎模块转发引擎模块高速交换网络主 控 处 理 模 块 图6 路由器结构图转发引擎的任务是对输入报文的IP层进行处理完成。它的任务内容有许多，例如报文完整性检查、地址路由查找等。另外，转发引擎的实现基本上凭借它的功能模块。这些功能模块是它的重要组成部分，其包括有报头处理、安全检测等。转发引擎工作过程如下：首先，外部IP包进入转发引擎，转发引擎就对其缓存，第二，在缓存中IP包，处理逻辑将其取出，再由处理逻辑对IIP包的报头进行分析，将错误的报文挑出来并且丢掉。依据查转发表的结果得出其输出的接口，在确保QoS的基础上查流的分类。当第二步完成后，依据第二步操作的结果来修改报头，完成报头修改后IP包被输出到交换网络。最后完成转引擎的交换功能。3.1.2转发引擎的的功能上文中对转发引擎的工作过程有一个清晰的分析，下面对转发引擎需要实现的功能做一个分析：（1）输入处理：信号转换和实现和线路接口模块之间的数据格式转换，得到IP包，使得IP数据包报头和报文缓存孤立（2）报头的有效性检测处理：分析报头，对版本域、负载长度等检测其合法性和有效性以及检测IP包是否有扩展项。（3）安全策略检查处理：在五元组信息基础上对IP包进行安全过滤（五元组信息是源地址、目标地址源端口、源接口和协议域）。在安全过滤的基础上记录和转发IP包。（4）单播地址查表处理：发现完整输出接口，控制逻辑的IPV6单播目的地址查找表部。（5）直连检查处理：组播报文被检查，看其是否与对应的路由器相连。（6）RPF检查处理：组播报文的反向地址检测。（7）组播地址查表处理：找到输出接口列表，对组播地址查表完成部分控制逻辑。(8)性能统计处理：完成对每个线口发到本模块IP包的统计。（9）QoS（英文全称Quality of Service，中文全称服务质量，下文中都以QoS简称）查表处理：在DiffServ协议帮助下完成PHB相互对应，提供QoS给高性能路由器。3.2转发引擎系统级流水线上文已经提出了要运用流水技术于路由转发过程，为了更清晰的了解流水技术如何在路由器的转发过程中应用，我们需要对路由器的转发引擎的转发过程转发过程进行全面的分析。如图7所示，转发引擎的处理过程包括了接口的转发、提取报头、路由查表、报文的修改和处理以及输出控制等的五个方面。这是转发引擎系统级的流水。以下文中将对它们进行一一剖析其作用。接口的转换提取报头路由查表报头的修改和处理输出控制 图7（1） 输入缓存：接收和缓存线路接口输出的报文。（2） 提取报头：先对所接收到的报文进行分析，提取报头，在把所提取的报头发送到路由表模块。（3） 路由查表：表关键字根据数据报头生成，再依据生成的表关键来路由查表。（4） 报头处理：检查报头的有效性，报文的TTL、地址范围的有效性也要检查。若是报文为组播报文，除了上述的操作外，还要对直连和RPF检查。（5） 输出控制：操纵报文的输出。这个报文由报头处理。有一些的转发引擎的系统级功能模块的知识，我们来分析在系统级别上流水线的工作过程：外部接口的输入数据包转发引擎，转发引擎接收写存储在输入缓冲器，然后报头提取模块从输入缓存中的数据包提取报头，提取出来的报头被送给查表模块后开始查表操作。然后在查表后的结果和关于报头有效性结果的基础上，报头处理模块对报文如何处理做抉择，如丢弃等。最后输出控制模块把报文(按照报文处理方式重新封装好的)输出去。上述的论文重点分析转发引擎，并对其系统流水线做了详细的分析，从而我们得到在系统流水线中，路由查表的过程时间最长。路由查表也就成了制约整个系统流水线的一大因素，因此，本文将在下一章节中提出一个基于TCAM流水线查找方案，从而提高路由器性能。4流水线在路由查表中的应用分析4.1基于TCAM的路由查找由一次三态内容寻址存储器（ternary content addressable memory，简称TCAM）操作和一次静态随机存储器（英文全称为Static Random Access Memory，简称SRAM）操作构成了典型的TCAM路由查找方案。TCAM的结构又是构建在存储阵列和优先编码器的基础上。那么，TCAM的存储阵列作用就是存储前缀，前缀对应的转发信息却在SRAM上进行存储。TCAM查找结构图如图8所展示的。TCAM的查找过程是：目标地址被拿来与存储阵列的各个掩码做与运算，其与运算的结果用来和同样存储在TCAM中前缀做比对，比对结果相等，匹配向量为1，反之，匹配向量为。另外，匹配符合的项可能有多个，因此让优先编码器作为结果进行输出的是保存于地址匹配项最低的地址。然后在此基础上，在SRAM中取得与之相对的转发信息（转发信息值得是输出端口号和下一跳的地址）。据上所述，我们可以看出TCAM查表过程中由TCAM查表搜索过程和TCAM读出表项两个操作组成，这两个操作是串行执行的并且无法进行流水操作，因此，整个路由器的路由表查表过程需要的时间是TCAM查表搜索过程和TCAM读出表项两个操作的和，这个过程通常需要十几个时钟周期甚至更多存储阵列321010N目的地址P9P8前缀长度匹配向量优先编码器转发信息存储器匹配表项转发信息地址转发消息TCAMSRAM图8 TCAM查找结构为了解决这个现象，本论文设计了一个将流水技术引入路由查表的方案来解决路由查表周期时间长的问题，其方案由TCAM和SRAM一起完成路由查表流水线，使得路由查表区分为两个层次来完成:首先查表的搜索过程是通过TCAM完成，然后查表结果从SRAM里取出。将流水技术引入路由查表可使得减少到2个时钟周期或者是4个时钟周期。4.2路由查表的流水线方案设计路由查表是路由转发过程中的重要组成部分。它的处理过程耗费的时间也是最长的。表项搜索和结果读取两个过程构成了实际上的路由查表过程，如同上文所说的一样，要将两个操作通过TCAM和SRAM分别来实现，我们就需要引入流水技术，尽可能的减少路由查表的时间，凭借这种来提高转发引擎在转发处理过程中的效率，提升路由器的整体性能。流水查表方案具体为：TCAM表用来将关键字（在路由查表时需要的）保存起来，SRAM则是用与之相对某个的地址将查表后得到结果存贮起来，从单播查表看，TCAM地址保存为一个查表的关键字目标IP地址，在SRAM中的相应的一地址空间将保存，然后用作查表结果的目的接口号，从而形成了一条完整的单播表项。当报文来到时，第一是由FPGA将查表关键字从报头中提出，随后发送给TCAM查表来搜索，当TCAM搜索到与关键字相匹配的表项时，RBUS就会发送该表项的地址，SRAM获取该表项的地址即获得这次路由查表操作后得到结果转发该报文的目标接口，通过SRAM发送到FPGA。如图8所示。FPGATCAMDBUS RBUSAddrDQ SRAM第1步：送查表关键字第2步：输出匹配地址第3步：读出查表结果FPGATCAMDBUS RBUSAddrSRAMDQ 第1步：送查表关键字第2步：输出匹配结果第3步：读SRAM操作第4步：读出查表结果（1）（2）图9图9中有两种关于流水线的设计方案，其两者不同就在于TCAM中的RBUS是直连到SRAM的地址总线上还是不直连到SRAM的地址总线上若将TCAM的RBUS让SRAM直接读取地址，如图9（1），好处是电路板的制作较为简单，降低了现场可编程逻辑门阵列(FieldProgrammable Gate Array，简称FPGA)中的User IO的资源紧张问题。不足的是记录表项的用时较长，原因在于记录SRAM表项必须经过相应的TCAM操作才能实现，即需要通过TCAM才能完成记录TCAM表项和SRAM表项。因此，记录一条完整的表项所用的时间是二者之和：方法（1）记录表项的时间等于是写TCAM表项的时间和经由TCAM记录SRAM表项的时间之和。反过来说，若是TCAM的结果总线RBUS和SRAM的地址相连方式是要FPGA做中间人，如图9（2）所示，电路板的制作难度是加大了，但是写一条完整表项的时间却降低了（其时间为写TCAM表项和SRAM表项二者之间最大值）。原因是可以同时进行写TCAM表项和SRAM表项，而且一般来说TCAM的读写时间大于SRAM的读写时间。即：方法（2）记录表项时间就是等于记录TCAM表项的时间。然而，若是SRAM表项是由TCAM写的，那么它的时间常常和独自写TCAM表项时间是差不多，因此图9中的方法（2）写表项的时间与图9方法（1）写表项的时间大大的不同，图9中方法（2）写表项的时间有了大幅度的降低了。所以方法（2）更有利于发挥转发性能，这篇论文选用的就是方法（2）的流水线的路由查表方案。4.3基于TCAM的具体并行处理研究通过上文中我们对转发引擎系统流水线的分析，提出了对路由查表也引入流水线机制，并且给出了路由查表流水线设计方案，那么我们在这里根据TCAM的特点，提出一种路由查找的并行工作方式，下文中将详细阐述。根据已有的资料，我们可以知道TCAM在查表方面具有很快的速度，在存储方面也很灵活。当然，它也有不足之处，其不足之处在价格昂贵，功能消耗大而且表项更新方面速度很慢。据此，本文提出一种将TCAM空间进行多个分区处理，且这些分区是相互独立的，我们称这些分区为block。根据TCAM的特性，这些分区中，每一个都可以在独立的情况下对查表任务完成，而且为分区供电只在其工作时。这种方法的具体实现过程是：第一要将TCAM空间进行分区，划分为m个独立的分区。将特征想同的表项存放在同一个分区中，那么路由查表时，现根据目标地址的特点，判断它是哪个分区的。然后再使用该分区，对路由表进行再次查表操作。SRAM用来存放下一条的地址，读取TCAM分区查表的结果。那么它的并行流水处理过程如图10所呈现的。一次查表逻辑Block1Block2.Blockm-1BlockmSRAM下一跳地址Hash值TCAM1TCAM2图10基于TCAM并行处理流水工程4.4转发查表外部结构和FPGA内部结构4.41转发查表的外部结构为了实现上述的路由查表，我们需要如下器件:FPGA、CAM和SRAM，它们组成的外部结构图如图11所示。SRAMFPGATCAM1TCAM2图11 转发查表的外部结构图4.41转发查表的FPGA内部结构由逻辑仲裁、搜索查表、表项更新、数据选择和TCAM的初初始化等功能构成了转发查表FPGA模块内部结构，其图如图12所示。这些功能每一个都有自己的功用，在这里就不一一详述了。TCAM初始化报头处理单播入FIFO（处理机接口逻辑仲裁FWP2FWP51搜素查表表项更新单元单播入FIFO（处理机接口FWP51查表结果输出FWP2数据选择TCAMSRAM图12 FPGA内部结构图路由查表过程采用流水技术设计后，转发引擎的等效流水线就如图13所示。SRAM查表结果读取CAM查表结果输出CAM查关键字生成输入接口转换报头提取输出控制报头处理和合成路由查表图13 转发引擎等效流程图5路由器转发性能提升小结高端的路由器其转发引擎都要支持G比特的线速转发能力。本文将流水技术引入到路由器转发引擎。路由器的转而发送能力有了很大的增长。路由器报文发送处理过程中速度最慢就是路由查表。那么，解决路由查表问题就是扫除了路由器的性能问题。本次论文首先详细介绍了流水技术、路由器和转发引擎。在路由设备的角度中，主要叙述的是路由设备的概念。工作过程、路由器的特点、基本构成以及研究现在的状态也进行了描述。通过对路由器的分析，让我明白了如何工作原理和如何提升路由器性能以及为什么要提升路由器性能。流水技术主要阐述了基本思想