用于协议处理的硬件体系结构.doc

《用于协议处理的硬件体系结构.doc》由会员分享，可在线阅读，更多相关《用于协议处理的硬件体系结构.doc（20页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第六章 用于协议处理的硬件体系结构前面我们讨论了常规计算机上的协议处理软件的体系结构，本章讨论用于协议处理的硬件体系结构。我们将讨论为什么常规计算机不适用于协议处理，目前有哪几种用于协议处理的硬件体系结构，它们的优缺点是什么。和早期的计算机设计者一样，网络系统的建造者尝试设计各种功能单元并把它们互连起来。大量的尝试以及缺乏可供借鉴的经验导致出现了很多种方法和体系结构，很难对它们进行一个清楚的分类，对于哪一种结构是最佳的目前也没有统一的认识。尽管如此，我们仍然可以确定出几种基本的方法，我们将简要介绍它们的基本思想。6.1 传统的软件路由器第一个网络设备由分组交换机组成。分组交换机的实验开始于上世

2、纪六、七十年代，那时DEC等公司引入了小型机来代替庞大、昂贵和高性能的主机。小型机的硬件被广泛采用，将它们用于分组交换机有几个好处：1）由于早期的网络运行在很低的速率，小型机的CPU足够用来处理分组交换；2）小型机较小的物理尺寸使得分组交换机可以放入已有的机房；3）小型机较简单的I/O接口简化了网络接口的设计；4）小型机低廉的代价使得用多个分组交换机构成一个网络在经济上是可行的。当因特网技术出现时，更廉价的微型机已经商用，网络工程师们也知道如何将它们用于网络系统。那时候，CPU的速度提高很快，微机的CPU已有足够的能力完成IP包的转发。因此，第一个商用的IP路由器使用的就是常规计算机硬件，目前

3、低端的路由器仍是如此。所谓常规计算机硬件主要指的是通用处理器（General Purpose Presessor，GPP），基于常规计算机的IP路由器也称为软件路由器，因为所有的协议都是用运行在通用处理器上的软件实现的。软件路由器的硬件体系结构如图6-1所示，由一个CPU和若干NIC组成。其中，CPU执行所有的协议处理任务，NIC执行组帧和卡上地址识别。图6-1 软件路由器的硬件体系结构软件路由器的主要优点是代价低，主要缺点是处理速度低。由于路由器必须处理来自各个网络接口的数据包，因此路由器的处理速度决定了可以连接到路由器上的网络的最大数据速率以及路由器能够支持的最大网络接口数。我们使用集合速

4、率指代数据进入或离开一个网络系统的总速率。有时候我们只关心一个方向上的集合速率，如考虑路由表查找时我们只需要关心到达的包，这时集合速率是指所有接口上的数据速率之和。类似地，对于使用单工传输的硬件，我们只考虑一个方向的数据速率；对于使用全双工模式的硬件，我们考虑两个方向的数据速率。一个系统的最大集合速率非常重要，因为它决定了系统可能的效用。尽管集合数据速率易于计算并且提供了系统能力的一种度量，但不够全面。我们知道数据包的长度是变化的，而许多协议处理操作对于每个包的处理时间是固定的，比如IP路由查找的时间不依赖于包的长度，因此，对于许多处理任务来说每秒处理的数据包数比集合数据速率更重要。每秒钟有多

5、少个包通过网络到来呢？这取决于网络的吞吐量以及包的长度。图6-2列出了不同类型网络中的包速，用Kpps表示，1Kpps表示每秒钟1000个包。在高端网络中，一条OC-192线路就可以提供高达20Mpps的包速，由于路由器通常连接多个网络，因此路由器的集合包速比表中列出的值还要大得多。图6-2 不同网络中的包速一个软件系统每秒钟能够处理多少个包呢？一个典型的运行Linux内核的PC机每秒钟最多可以处理50000个IP数据报，前提是每个数据报只要求最少的处理；若每个数据报必须由防火墙软件处理，则每秒钟最多只能处理8000个包。确切的包速要取决于CPU速度、总线带宽、内存延迟以及处理量等。为了获得每

6、秒钟N个数据包的集合速率，CPU处理每个包的时间不能多于1/N，图6-3列出了不同类型的网络中处理每个数据包所允许的最大CPU时间。图6-3 不同网络中一个数据包的最大处理时间实际上，处理一个包的时间包括了中断处理、将包拷入内存以及处理包的时间，在这里我们忽略中断处理时间，只关注CPU处理协议的时间。每个包要求的处理时间取决于包的内容（如使用的协议），并且不同的协议要求的处理时间差异很大。在一个典型的CPU上，处理一个分组的指令不会超过10000条，许多分组要求少于5000条的指令。下面我们看一下，软件路由器在什么场合下是可行的。考虑两个10Base-T的以太网，每个网络的最大包速是19500

7、pps，CPU最多只有25.6微秒时间处理一个包。为了处理从两个10Mbps以太网上到来的网络流量，CPU必须在25.6微秒内执行500010000条指令。也就是说，CPU的执行速度必须在195Mips390Mips之间。许多商用的CPU可以有超过400Mips的执行速度，因此，一个软件路由器可以连接两个10Mbps以太网。考虑一个10Gbps的网络，每微秒产生大约20个数据包，这时CPU每秒钟必须执行21011条指令。即使是像交换机这样工作在第二层、每个数据包只要求几百条指令的网络设备，这样的分组速率也超过了一个CPU的处理能力。由此可见，运行在通用处理器上的软件不足以应付高速网络，因为集合

8、包速超过了当前CPU的处理能力。6.2 克服单CPU瓶颈尽管已经设计出了专门的算法及数据结构来优化网络系统的性能，但要进一步提高性能还需要对网络系统的硬件进行改进。硬件工程师们使用了多种硬件机制、技术和体系结构来优化性能，它们包括：l 细粒度并行l 对称粗粒度并行l 非对称粗粒度并行l 专用协处理器l 具有板上处理功能的智能NICl 数据流水线以上这些方法有些是通用的，即适用于大多数包处理系统，有些只适用于特殊的网络系统。值得注意的是，一种能够改善某个网络系统性能的方法可能会降低其它网络系统的性能，一种能够改善某类数据包性能的方法可能会降低另一类包的性能。在实际的网络中，不存在一种十全十美的解

9、决方案，每一种方案都代表了在效率、通用性和代价之间的一种权衡。（1）细粒度并行从理论上说，并行的思想很简单：为克服单CPU的局限性，使用多个CPU一起来解决一个问题。一个可以并行执行的系统应当比每次只能执行一个操作的系统有更强的处理能力。并行通常应用于计算密集的任务，比如那些涉及对整个包进行计算的协议处理操作。设计图形系统的开发人员发现，他们可以通过细粒度并行（也称指令级并行）来优化性能。本质上说，一个并行CPU有一些特殊的指令可以应用到一批数据上而不只是一个数据上。比如，有些CPU包含并行指令，可以同时操作在内存的连续8个位置上。尽管指令级并行已在一些网络系统中使用，但是实验和仿真研究表明并

10、没有获得很高的性能。原因有以下几点：1）包处理功能很少有能被细粒度优化的，特别是对包所做的处理要取决于包的内容，因此系统不可能用同一个指令序列处理N个包；2）程序必须花时间建立并行指令，对于较小的包，并行指令建立的时间占总开销的大部分；3）细粒度并行仅能改善CPU性能，而在许多情况下瓶颈是I/O；4）细粒度并行代价很高，因为它要求改变CPU。（2）对称粗粒度并行对称多处理器提供一组N个相同的CPU，由于每个CPU独立运行，一个对称多处理器可以同时处理多个包或多个协议。比如，一个CPU执行重组IP包的代码，而另一个CPU执行发送TCP段的代码。对称多处理器是最早应用于基于软件的网络系统的优化措施

11、之一，它有两个主要的优点：1）网络系统设计者不需要发明新的对称多处理器硬件，因为通用系统已经可以从商业渠道获得；2）设备提供商已经将一个传统的Unix操作系统移植到了他们的多处理器硬件上，这个环境对于程序员来说非常熟悉，他们只需要学习用于控制和调度多处理器的新特性就可以了。有人可能认为N个处理器每秒钟处理的数据包数量大约是一个处理器的N倍，事实上，对称多处理器网络系统的性能令人失望。对称多处理器的处理能力并不随着处理器数目的增加而线性增长，这主要有以下几方面的原因。1）大多数多处理器系统使用共享存储模式，所有处理器共享一个内核地址空间。尽管共享内存可以使得一个数据包很快地从一个处理器传到另一个

12、处理器，但是每次内存访问都会引起竞争，因为一次只能有一个处理器访问内存。2）包处理软件必须协调对数据结构（如包队列）的访问，降低整个系统的处理速度。3）尽管对称多处理器提供了一种增加处理能力的方法，但多处理器体系结构并不自动增加I/O的带宽。（3）非对称多处理器非对称多处理技术使用多个可同时运行的异构处理器。非对称的优点在于专门化的能力，每个处理器可针对一种特定的任务优化。比如，一个处理器可能具有针对第三层处理的特殊指令，而另一个处理器可能具有针对第二层处理的特殊指令。非多称多处理器有四个缺点：1）除了针对特定任务的专门指令外，处理器还需要通用指令；2）非对称系统比对称系统难以编程；3）针对某

13、个特定任务或协议而优化的处理器用于其它任务或协议时性能可能不好；4）设计和构造非对称多处理器代价很高。（4）专用协处理器结合通用处理器与非对称系统优点的体系结构由一个通用处理器和一个或多个称为协处理器的专用处理器组成。每个协处理器被设计为执行一个特定的功能，所有协处理器在CPU的控制下运行。使用协处理器的主要优点是它给了设计者很大的自由度。可以将一个协处理器设计为一个强大的计算引擎，也可以只是执行某个操作的逻辑电路。也就是说，和非对称多处理器不同，协处理器不要求能够独立运行，也不需要通用指令，也没有取指令-执行周期。比如，一个设计用来验证IP头校验的协处理器，CPU只要将数据包在内存中的存放地

14、址及包头长度传给协处理器，协处理器计算后将返回一个值，指示头校验是否正确。如果协处理器执行一个任务的时间比通用CPU少，则系统的吞吐量会提高。然而，如果允许所有的协处理器同时执行，则系统性能的提高会更多。也就是说，硬件必须允许CPU在一个协处理器执行完之前启动另一个协处理器。这种异步性允许系统同时处理多个包或对同一个包执行多个独立的操作。那么需要为一个常规CPU增加哪些额外的设施来更好地完成包处理呢？很显然，应该选择那些消耗CPU时间最多或者最频繁执行的操作，如验证校验和、加/解密等，将它们交给协处理器完成。所以，在网络系统设计中一个重要的原则是：将那些最消耗CPU时间的操作转移到硬件上去。术

15、语“应用特定集成电路（ASIC）”是指为某种特殊需要而定制的集成电路。ASIC生产技术已经商业化，这对于设计和构造满足特殊需要的协处理器非常重要。由于ASIC硬件的设计和实现非常昂贵，因此，工程师们努力使每一种芯片尽可能通用。也就是说，不是设计一种只能理解一种包格式或一种协议的协处理器，而是设计一种能适应许多协议的协处理器。（5）智能NIC以上讨论的硬件机制都是为了改善计算性能，然而，网络系统设计者发现计算并不是唯一的瓶颈，许多协议处理任务是I/O密集的，因此必须优化数据穿过系统的流动。前面我们讨论了改善传统I/O接口速度的技术：DMA、卡上缓存和操作链，还讨论了卡上地址识别和过滤。随着网络速

16、度的提高，需要能够支持更高包速的技术。一种显而易见的优化是将一部分处理转移到NIC上，比如，NIC可以验证IP头校验或从IP头中抽取某些域，也可以执行加密或压缩这样的功能。卡上处理的主要优点是减轻了CPU的负担；其次，由于NIC只需要处理来自一个网络接口的包，不像基于软件的网络系统中CPU必须处理来自所有网络接口的包，因此NIC硬件处理包的速度不要求很高。图6-4是带有智能NIC的系统的硬件体系结构及功能划分。有两种实现智能NIC的方法：ASIC硬件和嵌入式RISC硬件。ASIC硬件方法使用定制的硬件，硬件制造商设计一组专用芯片，工程师们将这些芯片集成到NIC上，每个ASIC芯片执行一种协议处

17、理任务。RISC方法用一个标准的RISC处理器代替定制硬件，除了RISC处理器外，智能NIC还包括一个卡上RAM用于包缓存和一个卡上ROM用于存放协议处理软件。RISC处理器比ASIC硬件的设计代价低，且系统易于修改。图6-4 带有智能NIC的系统的硬件体系结构RISC处理器使我们有可能将更多的协议处理功能转移到NIC上。我们能将整个协议栈都放到NIC上吗？如果我们这么做了，它能够消除CPU瓶颈并使系统支持任意多的网络接口吗？工程师们确实已经开发出了能处理第三层上大部分功能的智能NIC。然而，在常规计算机上用智能NIC扩展系统还受到其它因素的制约，特别是在以包转发为目的的网络系统中，智能NIC

18、之间的数据路径将成为瓶颈。在传统的计算机系统中，数据路径包括总线和内存，这些都是在多个NIC间共享的。后面我们将介绍一种能在智能I/O板卡之间提供高速互连的非传统体系结构。（6）数据流水线术语“数据流水线”是指由一系列硬件stage组成的硬件体系结构，数据包经过每一级时被执行一种操作。比如，我们可以设想将IP包的处理安排成一系列的stage。一个IP包到达时进入第一级，检查头校验，第二级对TTL域减1，第三级处理选项，第四级查找路由表，第五级进行IP包分片，第六级计算输出包的头校验，第七级封装数据包，等等。使用流水线结构有两个主要的优点。第一，由于每级只执行一个操作，因此每级的硬件可以做得很简

19、单，从而运行速度很快。第二，由于每级用独立的硬件实现，因此所有的级可以同时执行。也就是说，当第k级在处理一个包时，第k-1级可以处理下一个包。当然，仅当数据包快速连续到达时，所有级才会同时执行。由于每级的处理时间可能不同，流水线结构通常用包队列来连接两个级。每个级从输入队列中取出包执行，处理完后将包放入连接下一级的队列中，见图6-5。另外，一个级输出的包数可能与输入的包数不同，比如它可能丢弃包，可能将一个包划分成若干个报片，或者将若干个报片组装成一个包。由于不同级执行的任务不同，这些级可以是异构的，比如有的级可能包含很复杂的硬件，有的可能很简单。图6-5 一个5级数据流水线的例子我们可以看到，

20、已经有很多种硬件体系结构、机制和技术应用于网络系统，集合数据速率、集合包速、要进行的包处理决定了需要使用什么样的硬件。传统的基于软件的网络系统已经不能适应高速网络的需要，高速网络要求的硬件体系结构包括：多处理器系统、ASIC协处理器、智能NIC和/或数据流水线。第七章 分类和转发本章讨论协议处理中一个非常重要的概念：分类，介绍分类的目的、分类的软硬件实现以及分类与高速转发之间的关系。（1）解多路复用的局限性我们前面介绍过分层协议处理中的解多路复用：输入的数据包在沿着协议栈向上传递的过程中，每一层的协议实体利用协议头中特定域的内容决定将包的内容交给哪一个上层协议。解多路复用的特点是：使用全局类型

21、系统，发送方参与，逐层执行。解多路复用的主要优点在于传输效率和灵活性。解多路复用允许我们为每一种协议定义一个包头，包头中只包含这个协议需要的域，而不需要建立一个能够适用于所有协议的包头。其次，解多路复用允许设计者增加一个新的协议或改变一个已有的协议而不影响其它的协议，这是因为每个协议独立地定义它的协议头，不同协议头中的域不共享。尽管解多路复用有以上优点，但是解多路复用的传统实现却很低效，因为它是顺序执行的。当数据包需要穿过一个L层的协议栈时，需要执行L次解多路复用。（2）包分类如何既保持解多路复用的优点又提高系统的整体效率呢？解决的办法就是用包分类来代替解多路复用。包分类的思想很简单：保持分层

22、协议的设计不变，发送端依然将类型域写入包头中，接收端一次性检查多个协议头中的相关域，将包划分到相应的类（也称流）中。比如，我们希望从输入的以太帧流中分离出去往Web服务器的流量。这个流量定义如下：以太帧中包含一个IP包，IP包中包含一个TCP段，TCP段中的目的协议端口号指定一个Web服务器。在这个例子中，需要三条分类规则来定义Web流量：以太帧中的type域为0x0800（表示包含了一个IP包），IP数据报中的protocol域为6（表示包含了一个TCP段），TCP段中的destination port域为80（表示包含了一个HTTP消息）。从概念上说，分类器需要计算以上三个条件的逻辑“与”

23、。（3）包分类的软件实现最简单的实现方法是使用一系列的条件测试，每次检查一个头域，当有一个域不匹配时即停止往下检查，并声明不匹配，仅当所有测试都通过时才声明匹配。如：If(type=0x0800)&(protocol=6)&(destination port=80)Declare the packet matches the classification;ElseDeclare the packet does not match the classification;对于基于软件的分类器来说，顺序检查是很流行的，最坏情况下需要测试分类规则中描述的所有域。以上算法可以被优化。我们注意到，虽然最坏

24、情况下的测试次数是固定的，但是通过适当安排条件测试的顺序可以最小化平均测试次数。比如，假如我们知道95%的帧携带了IP包，92%的IP包携带了TCP段，85%的TCP段的目的端口号为80，则按下面的测试顺序可使平均测试次数最小。If(destination port=80) &(protocol=6) &(type=0x0800)Declare the packet matches the classification;ElseDeclare the packet does not match the classification;（4）包分类的硬件实现以上算法是针对运行在常规计算机上的分类软

25、件设计的，使用并行硬件可进一步优化分类的效率。并行硬件可避免头域的顺序测试：分类器抽取出多层报头中的相关域，将这些域连接成一个多字节的值，然后将该值与分类规则中给出的常数进行比较。比如，为测试上例中的Web流量，分类器将type、protocol和destination port三个域中的值连接成一个5字节的值，然后与08.00.06.00.50进行比较（数字串中的点是为便于阅读而加上的）。在图7-1中，分类器首先通过一条很宽的数据路径将缓冲区中的报头拷贝到一个专门的寄存器中；硬件抽取特定域中的值送到一个比较器电路，与预先定义的一个常数进行比较；如果匹配则设置一条输出线路为高电平，否则设为低电

26、平。图7-1 硬件分类器可变长度的包给并行硬件的设计带来了很大的困难，因为所要检查的域在包中的位置不固定。一种方法是在并行测试中增加对长度域的检查，对针对每一种可能的长度设计一组分类规则。比如，在上例的Web流量测试中，假设IP包头的长度有20个字节和24个字节（有一个选项）两种情况，则设计以下两组规则。Set 1l 以太帧中的type域为0x0800l IP包头中的头两个字节为0x45l IP包头中的protocol域为6l 距IP包头22个字节处的域为80Set2l 以太帧中的type域为0x0800l IP包头中的头两个字节为0x46l IP包头中的protocol域为6l 距IP包头2

27、6个字节处的域为80另一种方法是建立一个能够顺序计算报头偏移量的硬件。为确定下一个协议头的位置，硬件抽取当前协议头的长度，并移动相应的距离到达下一个协议头。尽管这种方法的速度不如并行硬件高，但是代价要低得多。（5）混合硬件/软件实现方法虽然设计并行硬件进行包分类是可能的，但是高昂的代价使得这种方法很不实用。一般来说，仅当包速超过软件的处理能力时才使用并行硬件。更重要的是，硬件方法的灵活性很差，对分类规则的任何改变都要求修改硬件。混合硬件/软件方法将硬件分类的高速度与软件分类的灵活性有机地结合起来。图7-2是一个包含两个阶段的混合分类器，硬件阶段用于处理标准格式的包，软件阶段用于处理异常的包（如

28、有选项的IP包）。从本质上说，混合设计将硬件分类器作为一个过滤器，被硬件分类器识别的包直接被指派到一个合适的流，未被识别的包被送往软件分类器。图7-2 混合分类器系统（6）多规则集分类和查找引擎以上讨论主要集中在包选择而不是包分类，即一个分类器确定一个包是否匹配一个给定的分类规则集。更一般的情形是，系统中定义了很多个流，分类器需要将每个到来的包分配到一个对应的流，为此需要查找所有的规则集。一般的做法是，分类器从到来的包中抽取出相关域的值，然后通过一个查找引擎去查找分类规则表。查找引擎的实现效率对分类效率的影响很大。查找引擎可以用算法实现，也可以用专门的硬件实现。最简单的软件实现方法是用一系列的

29、条件测试语句和分支指令逐个地检查每个规则集，当然这种方法也是最低效的。目前已经提出了很多种优化的包分类算法及数据结构，它们可以并行地检查所有的规则集，从而大大提高了查找的效率。我们将在后面专门讨论这个问题。为获得高速度，目前绝大多数的查找引擎是基于内容可寻址存储器（Content Addressable Memory，CAM）实现的。CAM与普通存储器的实现机制完全不同。读取普通存储器中的数据时，必须先输入地址，然后读取该地址保存的数据。在CAM中查找与输入关键字相同的内容时，只需要输入查找关键字，CAM会将查找关键字与其存储的所有表项进行匹配。若匹配成功，CAM返回匹配表项的地址。BCAM（

30、Binary CAM）和TCAM（Ternary CAM）是两种内容可寻址存储器，BCAM的存储位有两种状态：0和1，而TCAM的存储位有三种状态：0、1和不确定。BCAM一般用于低层应用，如查找第二层的MAC地址表。TCAM常用于协议栈的高层，如查找第三层的路由表或第四层的应用流等。由于TCAM允许在查找关键字中使用通配符，因此TCAM的使用更加广泛。CAM的最大优势是查找速度快，最快在一个时钟周期内就可以完成查找关键字的匹配，没有其它类型的存储器能做到这一点。其次，可以通过级联多个CAM来增加容量，以存放较大的查找表（这时查找一个关键字所需的时间可能超过一个时钟周期）。第三，CAM具有自动

31、更新功能，即可以更新查找表。由于CAM查找的高效率，它垄断了2.5Gbit/s以上的应用，没有对手可以与其匹敌。但是CAM也有明显的不足，一是价格昂贵，即使大批量采购每片价格也要几百美元；二是封装面积大，在电路板上要占较多的空间；三是功耗太大。一般来说，在以下应用中采用CAM，将有助于提高系统性能：l 识别大比特模式。由于每识别一个大比特模式需要执行多次I/O操作，若用传统的基于存储方法进行大比特模式分类，查找延时会很大，而且查找性能也会很低。而CAM的入口数据宽度为36位的倍数，可以配置为支持72位、144位、288位、甚至576位的查找关键字长度。l 处理小规模的查找表。考虑到CAM的成本

32、和功耗，一般不会用CAM存储大型的查找表。l 对查找延时有严格要求的应用。（7）动态分类到目前为止，我们的讨论一直局限在静态分类，即系统中流的集合以及每个流的分类规则是事先确定的。静态分类主要用于根据服务类型（如IP区分服务）或应用（如Web流量）来隔离不同的流。比如，DiffServe定义了几种服务类型，每种服务类型对应一个流，用IP头中的TOS域携带服务类型信息。动态分类允许系统中流的集合随时间而改变，比如允许创建新的流或改变已有的流，因此短期的流量工程需要动态分类。动态分类典型地使用源地址和包类型来区分流。比如，一个ISP提供优质服务和标准服务，支付了优质服务的客户的前20个并发TCP连

33、接可以获得优先服务。当一个用户支付了优质服务的费用后，ISP使用动态分类器将该用户的前20个TCP连接分配到一个高优先级的流，超出该数目的TCP连接以及未支付该项费用的用户的流量被分配到标准流。ISP也可以允许客户为自己的每个流选择服务类型，比如，有些客户可能为其音频流选择优质服务，另一些客户可能为其音频流、FTP和Web流量选择优质服务。在这些例子中，网络系统都需要一个接口来描述和管理分类规则集。动态分类器最简单的实现是使用一个基于软件的系统，因为它代价最低。动态分类器的一个重要方面是它能够自动建立流。比如，当要将一个TCP连接映射到一个虚拟网络连接时，分类器在其流描述表中添加一个表项，记录

34、该连接的源/目的IP地址和源/目的端口号，以及分配给该流的标识。当一个数据帧到达时，分类器检查帧中的相关域以确定该帧携带了一个IP包和一个TCP段；然后，分类器抽取以上四个域的值并查表，如果表中有一个表项匹配，则分类器将该表项中的流标识赋给该包。为了管理流描述表，分类器需要监视TCP SYN段和TCP FIN段。当它接收到一个TCP SYN段时，选择一个新的流标识，并在表中创建一个表项。类似地，当它收到一对TCP FIN段时，从表中删除相应的表项。动态分类的优点是灵活性好，缺点是开销大，对硬件所做的优化不如在静态分类中那么多。（8）转发从概念上说，分类是一个两步处理中的第一步，它将一个输入包分

35、配给一个流；第二步是转发，即利用流来确定如何处理包。这两步可以表示为两个绑定：分类将一个包绑定到一个特殊的流，转发将一个流绑定到一个特殊的处理。第二个绑定可以是一对一的，也可以是多对一的。即转发可以为每个流选择一个特殊的处理，也可以为多个流选择相同的处理。在面向连接的网络（如ATM网络）中，转发器和分类器一起工作。每当分类器创建了一个新的流，转发器就创建一条新的网络连接（如一条SVC）。如果令分类器选择的流标识等于网络连接的连接标识（如SVC的VPI/VCI值），则转发将变得非常简单。一旦分类器生成了一个流标识，转发器只要将该标识传给底层网络即可，不需要额外的计算或查表，也不需要第二个绑定。分

36、类也可以用来优化无连接网络中的转发。我们可以将传统的无连接转发看成是将一个目的地址映射到一个（下一跳地址，端口）对上，该绑定可以描述为：forwarding: destination address - (next_hop, interface)。由于分类将每个包映射到一个流，因此分类引入了一个中间绑定：forwarding: flow - (next_hop, interface)。这样，转发使用流而不是目的地址作为关键字。尽管这看起来变化不大，但是这个差别很重要，因为它允许我们将相关的路由信息放到一个单独的转发cache（或称路由cache）中，这些信息可以很快地从转发cache中读出。特

37、别是，由于动态分类系统允许使用任意值作为流标识，分类器可以使用0, N-1中的整数作为流标识，其中N为当前分配的流的数目。当一个包被分类时，分类器将它映射到一个流标识F。转发器不需要搜索路由表，它只要用F作为索引去查找转发cache就可以了。F指向的cache位置即存放了转发信息：(next_hop, interface) = forward_cacheF。索引比路由表查找快得多，而分类又比解多路复用快得多，因此，分类和索引的全过程要比传统的解多路复用和查表快得多。现在的路由器一般都实现了这种优化，这样的路由器也称交换式路由器，或第三层交换机。但这里有一个需要权衡的问题，即转发效率是通过较早的

38、路由绑定来取得的，而cache中的内容可能会过时。因此，为确保转发信息的准确，需要一种更新机制在路由表发生变化时更新转发cache中的相应表项。（9）第二代网络系统上个世纪90年代初期，随着FDDI、ATM等高速网络的出现，传统的基于软件的路由器（第一代网络系统）已不能适应这么高的包速，网络工程师们开始用专用的协议处理硬件来设计第二代网络系统。第二代网络系统具有以下三个显著的特点：l 用分类代替解多路复用处理大部分的数据包；l 将包转发的功能分散到各个网络接口上，每个NIC都有分类和转发的能力；l 提供一种高速内部互连机制，在各个网络接口间提供快速数据通道。以上这三个特点都允许系统扩展。分类允

39、许提高每个端口的数据速率，因为分类能够处理较高的包速；分散式结构以及端口间高速互连机制允许系统支持更多的网络连接，因为所有接口可并行地分类和转发包。第二代网络系统包括一个常规CPU，用于管理和控制系统、向系统管理员提供管理接口以及运行路由协议。因此，CPU更新路由表，而网络接口使用路由表转发包。除了更新路由表外，常规CPU还处理异常和错误，包括ICMP消息和不匹配任何分类规则的包。实际上，不需要专门去测试异常或错误，每个NIC上的分类和转发机制都配置了一个转发到本地CPU的缺省流，不匹配任何分类规则的包被自动分配到这个流。图7-3是第二代网络系统的一个概念组织图，输入接口通过快速数据通道将大部

40、分的包转发到适当的输出接口，常规CPU处理异常和错误。我们前面介绍过，为分类设计专门的硬件是可能的。但是，由于定制的ASIC硬件相当昂贵又不能用于其它系统，硬件制造商一般都避免这么做。大多数的第二代网络系统使用软件实现方案，即在每个NIC中包含一个用于分类和转发的嵌入式处理器。设备制造商们通常选用一个RISC处理器作为NIC上的嵌入式处理器，RISC芯片具有体积小、计算速度快、价格便宜、易于同其它硬件集成、易于编程等优点。因此，一个典型的NIC包括一个物理层芯片组、一个RISC处理器、存放软件的ROM、用于板上包缓存的RAM和一个总线接口。后面我们将介绍这个基本的体系结构在网络处理器中是怎么被

41、扩展的。图7-3 第二代网络系统的概念组织目前也有制造商提供商用的分类硬件，称为分类器芯片。大多数分类器芯片提供一种有限形式的动态分类。和专为分类优化的并行硬件不同，分类器芯片的分类规则并没有被固化在硬件中；但它也不使用传统的软件方法，即芯片不从内存中执行指令。分类器芯片允许配置分类规则，比如，将分类规则放入PROM或可编程门阵列FPGA等。有些制造商提供一个分类器芯片组，这些芯片组可以一起工作完成分类和转发。芯片组中通常还包括连接分类器/转发器到系统其它部分的芯片，如在分类器和以太网端口之间、在转发器和快速数据通道提供接口的芯片等。第八章 交换结构我们在前面看到，分散式的硬件体系结构可使网络

42、系统具有良好的可扩展性。由于每个网络接口独立地进行分类和转发而不需要CPU的参与，因此CPU的速度不影响系统的性能，系统可以支持更多的网络接口。但是，除非内部数据通路提供足够的带宽，否则各个接口之间的数据包传递将成为系统的瓶颈。尤其是，常规计算机中的总线不能提供足够的带宽来处理高速网络之间的包转发。数据通路的速度通常用集合数据速率和集合包速来衡量。系统的集合数据速率提出了对互连机制（也称背板）的主要要求：背板必须有足够的带宽传输进入系统的所有包。因此，连接了16个100Mbps以太网的网络系统，其背板容量至少应为1.6Gbps（还应有少量容量用于控制和传输间延迟）。连接了16条OC-192线路

43、的网络系统，其背板至少应有160Gbps的容量。由于网络系统使用内部连接来移动数据包，因此集合包速也可能是比较重要的。比如，若一次包传输对应一个操作，则传输的包数决定了要执行的操作数。连接的带宽和连接支持的最大包速可能是相关的，比如，有些硬件只能在传输较大的数据包（即较小的包速）时才能获得较高的集合数据速率。8.1 交换结构的概念从概念上说，交换结构是一种承担背板任务的硬件机制，它在一组输入端口、一组输出端口和CPU之间提供数据通路。交换结构也可以用于将较小的网络系统连接成一个较大的系统。图8-1给出了交换结构的基本体系结构。图8-1 交换结构概念尽管许多机制满足交换结构的一般概念，但用于网络

44、系统的交换结构需要优化以下特性：l 设计为在一个网络系统内使用l 可提供在CPU和智能I/O端口之间的连接l 支持单播、多播和广播包的传输l 可以扩展支持任意的数据速率l 可以扩展支持任意的包速率l 可以扩展支持任意数目的输入或输出端口l 低开销l 低代价实际上，没有哪一种机制能够满足以上所有特性。比如，代价往往和带宽成正比，提供高带宽的机制总是具有高代价。因此，设计者们并不试图去寻找能满足所有特性的机制，而是针对特定的问题寻找能适当平衡以上特性的机制。比如，为获得低代价，有些交换结构限制集合数据速率，有些交换结构限制端口数等。多种不同的权衡方案导致出现了大量的交换结构，包括：共享总线、共享存

45、储、crossbar交换机和Banyan交换机等，每一种交换结构都适用于一些场合。在应用于网络系统之前，早期的交换结构起源于两个截然不同的背景并产生了两种基本结构。一种用于电话系统中，用来构造电话交换机；另一种用在通用多处理器系统中，用于多个处理器之间的通信。用在电话交换机中的交换结构倾向于采用同步设计，即交换结构按固定的时间间隔传输固定长度的数据块。用在通用多处理器中的交换结构倾向于采用异步设计，即交换结构可以在任何时刻传输数据。当交换结构应用于网络系统时，设计者们主要关注传输包的机制，不同的结构变形主要是为了处理一些特殊的情形。大多数网络交换结构是同步的，每个包被划分成固定大小的块，按固定

46、的时间间隔传输。数据块的大小取决于具体的应用，如有些交换结构专用于转发ATM信元，有些专用于转发以太帧。类似地，有些交换结构用来处理许多低速端口，而有些交换结构用来处理少量高速端口。为便于理解各种方法之间的折衷，我们将交换结构的设计分为以下两大类：l 时分方法：在许多端口间共享一条或者很少几条内部通路l 空分方法：交换结构中使用许多通路以减小延迟。下面我们将描述几种体系结构方法。8.2 空分交换结构（1）专用内部通路多通路交换结构的一种极端情形是全连接结构，即从每一个输入端口到每一个输出端口都有一条独立的硬件通路，一条硬件通路可能由一条线路或者一组并行的线路组成，见图8-2。当有一个包要传输时

47、，输入端口必须首先选择通往正确输出端口的路径，然后使用这条路径传送数据包，位于端口和交换结构之间的接口硬件处理路径选择的细节。图8-2 全连接结构的交换结构是否这样的一种全连接结构就能使所有的分组没有任何限制地穿过交换结构了呢？实际上不是这样，当两个输入端口试图向同一个输出端口发送时会出现竞争。所以，每个输出接口都包含了附加的电路用于处理端口竞争，竞争电路确保任何时候只有一个输入端口向一个输出端口发送。也就是说，发往一个输出端口的数据包可能被阻塞，以等待该端口上的一个数据传输结束。（2）Crossbar结构每个连接使用一条单独的物理通路的主要缺点是代价高。例如在上图中，或者每个输入接口必须包含

48、一个竞争电路，或者每个输出接口必须包含一个竞争电路。Crossbar交换结构采用另一种方法来处理竞争：每个端口连接一段物理路径，交换结构由一个NM的开关阵列组成，每个开关可连接一对输入和输出端口的物理路径，如图8-3所示。当一个开关被激活时，和这个开关连接的两段物理路径被连接起来，数据可以在这两个端口间流动；若开关未被激活，则这两段路径未连接。除了开关阵列以外，crossbar结构还包括处理端口竞争的控制器硬件。假设端口i准备发送一个包到端口j，和端口i相联的接口电路与控制器通信，请求建立到端口j的一条路径；假如端口j空闲，则控制器激活连接这两个端口的开关，数据包从输入端口发往输出端口；否则，控制器令端口i等待，直到端口j空闲。为提供最大的吞吐量，控制器允许并行传输。也就是说，当端口i向端口j发送时，控制器允许端口k向端口l发送。控制器可以建立最多P条并行路径，其中P=min (N, M)。图8-3 Crossbar交换结构Crossbar结构既有优点也有缺点。Crossbar允许同时建立多条路径，这使得crossbar能够处理多对端口之间的数据传输，可以