第二部分-第二代网络系统课件.ppt

1、第二部分 第二代网络系统主要内容p用于协议处理的硬件体系结构p分类和转发p交换结构1.传统的软件路由器p第一个网络设备是分组交换机，使用的是小型机。p第一个商用的IP路由器是软件路由器，使用常规的计算机硬件：n由通用处理器、共享内存、共享总线、若干个网卡组成n通用处理器执行大部分的协议处理任务，网卡完成组帧及地址识别n适用于低速系统，成本低。2.路由器的速度p路由器的处理速度决定了：n可以连接到路由器上的网络的最大速率n路由器能够支持的最大网络接口数p集合速率和端口速率：n集合速率：数据进入或离开一个网络系统的总速率，是系统处理能力的测度。n端口速率：在一个网络接口上数据进入或离开的速度。p数

2、据速率和包速率：n数据速率：单位为比特/秒。n包速率：单位为包/秒（pps），取决于网络的吞吐量和包的长度。不同网络中的包速 注：灰色条块代表大数据包的速率一个包的最大处理时间注：以上仅是一个网络接口的数据，如果有N个端口，则每个包的处理 时间还要除以N。一个软件系统能够支持多大的包速？p处理一个数据包的时间包括：n中断处理n将包拷入内存n包的协议处理：取决于包的内容（如使用的协议）p一个典型的运行Linux内核的PC机，每秒最多可以处理50000个IP包（每个数据报只做最少的处理）。p若数据包要经过防火墙软件处理，则每秒种最多处理8000个包。软件路由器的能力p考虑两个10Base-T的以太

3、网。每个网络的最大包速是19500pps，每个包的处理时间不超过25.6微秒，处理每个包的指令数一般在500010000条之内。因此，CPU的执行速度必须在195Mips390Mips之间。p许多商用的CPU可以有超过400Mips的执行速度，因此软件路由器可以连接大约两个10Mbps以太网。p考虑一个10Gbps的网络，每微秒产生大约20个数据包，CPU每秒钟必须执行21011 条指令。p结论：运行在通用处理器上的软件无法应对高速网络。3.克服单CPU瓶颈p细粒度并行（指令级并行）p对称粗粒度并行（对称多处理器）p非对称粗粒度并行（非对称多处理器）p专用协处理器p智能NICp数据流水线3.1

4、 细粒度并行（指令级并行）p目前几乎所有的处理器均采用了指令流水线来重叠指令的执行，但数据包处理程序中可以利用的指令重叠很少。p利用程序中的循环级并行，如采用向量指令。向量指令可以同时操作在一组数据单元上，比如进行检查和计算时，对内存中连续8个位置的数值同时相加。但数据包处理程序中可以利用的循环级并行很少。p细粒度并行对包处理来说优势不明显n包处理功能很少能被细粒度优化的n程序必须花时间建立并行指令n细粒度并行仅能改善CPU性能，而多数情况下访存或I/O是瓶颈3.2 对称粗粒度并行（SMP）p在一个计算机上汇集一组相同的CPU，系统资源被所有CPU共享，工作负载被均匀分配到所有可用的CPU上。

5、p典型的设计：每个CPU处理一个包，或者每个CPU执行一个协议。p使用N个处理器的网络系统获得的性能增益不是单处理器系统的N倍：n大多数多处理器系统使用一个共享内存n包处理软件必须协调对共享数据结构（如队列）的访问n只能增加处理能力，不能自动增加I/O带宽。3.3 非对称粗粒度并行p使用多个可并行执行的异构处理器，每个处理器针对一种任务而优化，使用特殊的指令集。p非对称多处理器的缺点：n每一个处理器都要有自己的指令n比对称系统难以编程n需要协调对共享数据结构的访问n通用性差，不适用于其它任务或协议n成本很高3.4 专用协处理器p使用一个通用CPU加上一个或多个专用协处理器构成网络系统。p协处理

6、器是在CPU控制下运行的一个硬件：n灵活的设计自由度：协处理器可以设计得很复杂，也可以设计得很简单n不要求独立运行，没有通用指令，也没有取指令-执行周期n可以像软件例程一样被调用n可以被异步调用，从而允许系统同时处理多个包或对同一个包执行多个独立的操作 p一般将消耗CPU时间最多或最频繁执行的操作（如检查和计算，加/解密等）用专用协处理器实现。p协处理器通常采用ASIC技术实现，ASIC（Application Specific Integrated Circuit）是指为某种特殊需要而定制的集成电路。3.5 智能NICp可以将一部分处理转移到网卡上：n地址识别和过滤，包缓存，DMA，操作链n

7、验证IP头校验，从IP头中抽取某些域，执行加密或压缩等 p在网卡上增加处理的优点：n减轻CPU的负担n不要求NIC有很高的处理速度p使用ASIC硬件实现智能NIC：n设计专用芯片，集成到网卡上，如链路层芯片组、第3层ASIC芯片等n速度快p使用嵌入式RISC硬件实现智能NIC：n使用标准的RISC处理器代替定制硬件n代价低，易于修改，允许将更多的处理功能转移到NIC上TCP Offload Engine（TOE）pTOE将处理TCP/IP的许多开销从主机转移到网卡，只将TCP/IP控制保留在主机上。3.6 数据流水线p由一系列硬件stage组成的硬件体系结构，数据包经过每一级时被执行一种操作。

8、p优点：n适合于多种协议处理任务n每一级可以做得很简单，运行得很快n所有级可以同时运行4.总结p传统的基于软件的网络系统已经不能适应高速网络的需要p高速网络系统需要特殊的硬件支持p可能的硬件体系结构包括：n多处理器系统nASIC协处理器n智能NICn数据流水线主要内容p用于协议处理的硬件体系结构p分类和转发p交换结构1.解多路复用的局限性p解多路复用：n与分层协议一起使用，数据包穿过协议栈时每次前进一层。n在输出端，包头中的类型域指明封装的格式。n在输入端，每一层上的软件选择高一层上的一个协议模块。p特点：n使用全局类型系统，发送方参与，逐层执行。p优点：n传输效率高：每一种协议的包头只需要包

9、含本协议需要的域n灵活定义新的协议类型：每个协议独立地定义它的协议头，不同协议头中的域不共享 p缺点：n逐层顺序执行使得实现上很低效2.包分类p基本思想：一次性检查所有层次上的相关域，将包划分到相应的类（也称流）中。p举例：n从输入的以太帧流中分离出去往Web服务器的流量n描述该流量的规则集：p以太帧的type域为0 x0800（IP）pIP头中的protocol域为6（TCP）pTCP段中的destination port域为80（HTTP）n从概念上说，分类器需要计算以上三个条件的逻辑“与”3.用软件实现分类p比较各级包头中的相关域，进行逻辑“与”运算p比如：If(type=0 x0800

10、)&(protocol=6)&(destination port=80)Declare the packet matches the classification;Else Declare the packet does not match;优化软件实现方法p重新排列条件测试的顺序，将能够过滤掉较多流量的测试排在前面；p比如，若已知95%的帧携带了IP包，92%的IP包携带了TCP段，85%的TCP段的目的端口号为80，则：If(destination port=80)&(protocol=6)&(type=0 x0800)Declare the packet matches the clas

11、sification;Else Declare the packet does not match the classification;4.用硬件实现分类p建立专用的并行硬件，避免头域的顺序测试。p步骤n抽取多层报头中的相关域n将这些域连接成一个多字节的值n与分类规则中给出的常数进行比较p在前面的例子中，分类器将type、protocol和destination port三个域中的值连接成一个5字节的值，然后与08 00 06 00 50进行比较。一个硬件分类器的例子包头长度不固定的解决方法p方法一：在并行测试中增加对长度域的检查，针对每一种可能的包头长度设计一组分类规则。如在前面的例子中，

12、假设IP头长度有20字节和24字节两种，则设计两组规则：Set 1Set2 以太帧的type域为0 x0800 以太帧的type域为0 x0800 IP头中的头两个字节为0 x45 IP头中的头两个字节为0 x46 IP头中的protocol域为6 IP头中的protocol域为6 距IP头22个字节处的域为80 距IP头24个字节处的域为80 p方法二：建立一个能够顺序计算报头偏移量的硬件，抽取当前协议头长度，并移动相应的距离到下一个协议头。5.混合硬件/软件实现方法p硬件分类方法：代价高昂，灵活性差p软件分类方法：灵活性好，速度不高p混合硬件/软件方法：n结合硬件分类的高速度与软件分类的灵

13、活性n包含硬件分类与软件分类两个阶段，硬件分类处理标准格式的包，软件分类处理异常的包一个混合分类器系统 注意：软件分类器可以运行在较低的速率6.多规则集分类与查找引擎p系统中通常定义了很多个流，分类器要将每个包分配到一个对应的流，为此需要查找所有的规则集。p一般做法：n分类器从包中抽取出相关域的值n通过一个查找引擎去查找分类规则表p查找引擎的实现：n算法：已经提出了很多种优化的包分类算法，可以并行地检查所有的规则集。n内容可寻址存储器CAM：目前绝大多数的查找引擎是基于CAM实现的。Content Addressable Memoryp一种支持快速查找的特殊存储器，与普通存储器的实现机制完全不

14、同。p查找操作：n在CAM中输入查找关键字nCAM将查找关键字与其存储的所有表项匹配n返回匹配表项的地址p有两种类型的CAM：nBCAM（Binary CAM）：存储位有0、1两种状态，精确匹配查找，一般用于低层应用。nTCAM（Ternary CAM）：存储位有0、1和不确定三种状态，支持通配符查找，常用于协议栈的高层，使用最为广泛。CAM（续）p优点：n查找速度快，最快在一个时钟周期内完成查找关键字的匹配n可以通过级联多个CAM增加容量n具有自动更新能力，能够更新查找表p缺点：n价格昂贵，封装面积大，功耗太大，容量有限p一般来说，以下应用适合采用CAM：n识别大比特模式n处理小规模的查找表

15、n对查找延时有严格要求7.静态分类与动态分类p静态分类n流的集合及每个流的分类规则事先已知n主要用于根据服务类型或应用来隔离不同的流p动态分类n流的集合随时间而变，允许创建和改变流n动态分类通常使用地址和包类型来区分流n灵活性好，允许细粒度的流控制n开销大，需要保存状态信息p动态分类器应能自动建立和维护流描述表，并进行分类查找。通常用软件实现，状态信息保存在内存中。8.分类与转发p转发的任务是根据接收到的数据包确定包的处理方法，比如根据数据包的目的地址将包转发到合适的下一跳节点。p可以将以上任务分成两步来做：n分类：将输入数据包映射到一个流（包-流）n转发：根据流确定包的处理方法（流-包的处理

16、）用分类优化无连接网络中的转发p将无连接转发划分成两个过程：n分类：destination address-flow IDn转发：flow ID-(next_hop,interface)p引入分类的好处：n可以将转发信息放在一个路由cache中，用流标识进行查找。n可用0,N中的整数作为流标识F，并用F作为路由cache的索引。n路由cache比路由表小很多，而且采用索引查找，查找速度快。p高速转发的过程：n分类器将数据包映射为一个流标识Fn转发器使用F作为索引查找路由cache。p分类和索引的全过程比传统的解多路复用和查表快得多。9.第二代网络系统p使用专门的协议处理硬件，为更高速度的网络而

17、设计的网络系统。p第二代网络系统具有以下三个显著的特点：n使用分类代替解多路复用处理大部分的包n将包处理功能分散到各个网络接口，每个NIC都有分类和转发的能力n提供高速内部互连机制，在各个网络接口间提供快速数据通道p以上三个特点都允许系统扩展，即允许提高每个端口的数据速率，允许系统支持更多的网络连接。第二代网络系统的概念组织p使用一个常规CPU，用于管理和控制系统、向系统管理员提供管理接口、运行路由协议和更新路由表、处理异常和错误。p网络接口使用路由表转发包p快速数据通道连接各个网络接口一个典型的NIC的组成p物理芯片组：组帧p嵌入式RISC处理器：实现分类和转发pROM：存放软件、分类规则集

18、等pRAM：卡上包缓存p总线接口主要内容p用于协议处理的硬件体系结构p分类和转发p交换结构1.内部数据通路p常规计算机中的总线不能提供足够的带宽处理高速网络之间的包转发。p数据通路的速度通常用集合数据速率和集合包速来衡量。p系统的集合数据速率及集合包速对内部互连机制（也称背板）的要求：必须有足够的带宽传输进入系统的所有包。2.交换结构的概念p从概念上说，交换结构是一种承担背板任务的硬件机制，它在一组输入端口、输出端口和CPU之间提供数据通路。交换结构的概念（续）p用于网络系统的交换结构需要优化以下特性：n可提供在CPU和智能I/O端口之间的连接n支持单播、多播和广播包的传输n可扩展支持任意的数

19、据速率n可扩展支持任意的包速率n可扩展支持任意数目的输入或输出端口n低开销n低代价p实际的交换结构是对以上各种特性的权衡3.交换结构的分类p同步结构与异步结构n同步结构：交换结构按固定的时间间隔传输固定长度的数据块，最早用于电话交换机中。n异步结构：交换结构可以在任何时刻传输数据，最早用于通用多处理器系统中。p大多数网络交换结构是同步的，每个包被划分成固定大小的块，按固定的时间间隔传输。p空分结构与时分结构n空分结构：交换结构中使用许多通路以减小延迟，集合吞吐量高，代价高。n时分结构：许多端口共享一条或者很少几条内部通路，集合吞吐量低，代价低。空分交换结构专用内部通路p每一对输入、输出端口之间

20、有一条专用硬件通路p每个输出接口都包含了附加的电路用于处理端口竞争 空分交换结构-Crossbar结构p使用NM 个交叉开关连接输入与输出端口p控制器硬件处理端口竞争p控制器允许多个端口之间并行传输p优点：n允许同时建立多条路径，集合吞吐率高n路径上的硬件只需要容纳一条数据传输，易于支持更高的端口速度。n比全连接结构经济 p缺点：n要求NM个部件，代价要比其它的一些设计高。空分交换结构基本队列p输入队列n设置在输入端口与交换结构之间n队头阻塞问题p将输入队列改为随机访问列表，或者p为每个输出端口设置一个队列p通常在每个输入端口上设置两个队列，分别存放单播包和多播包p输出队列n设置在交换结构与输

21、出端口之间p只使用输入队列n队头阻塞p只使用输出队列n输出队列及交换结构必须运行在集合速率上，或者n针对每个输入端口设置一个队列有输入输出队列的Crossbar结构时分交换结构共享总线结构p交换结构总线包括地址线、数据线和控制线p每个输入和输出端口都有一个接口硬件，每个端口被分配一个唯一的地址。p端口使用总线硬件将数据包传输到另一个端口p总线协议防止多个端口同时传输总线操作的粒度p包粒度：n端口一次发送一个完整的包n操作和硬件均简单，但增加了包的延迟 p数据块粒度：n包被划分成较小的数据块，每个发送端每次发送一个数据块；n避免了长延迟，多个传输可以并行进行；但增加了从一个发送者切换到另一个发送

22、者的开销 p信元粒度：n传输长度等于网络数据单元的长度；n类似于数据块粒度，但特别针对特殊协议而优化了总线协议p一般采用时分多路复用的方法，将使用总线的时间片分配给各个输入端口。p各个输入端口在总线上轮流广播收到的包；每个输出端口的地址过滤器检查包中携带的内部路由标签，将发往本端口的包存放到相应的缓冲区中。共享总线结构的可扩展性p总线及接口硬件必须操作在集合速率上。p受底层硬件技术的制约，该结构一般不能简单地扩展以适应任意数目的端口。时分交换结构共享存储结构p使用内存作为共享媒体连接输入和输出端口。p每个端口需要一个内存接口硬件，将端口连接到存储系统。p使用一个控制器硬件在端口之间传输控制信息

23、。传输控制p一个控制器提供一条单独的高速总线，各个端口使用总线来协调各自的行为。p输入端口将一个包放入内存后，接口硬件通过控制器发送一个消息，通知输出端口数据准备好，消息中给出包在内存中的存放地址。p输出端口从控制器收到消息后，从内存的指定位置读取包，然后发回响应消息。p控制器只是用来传输短的控制消息，不用于传输大量的数据包。共享存储结构的可扩展性p由于内存接口硬件非常昂贵，通常让许多端口共享一个内存接口。共享存储接口在降低代价的同时也降低了吞吐量。p共享存储结构的性能和代价取决于存储接口的数目。p该结构仅适合小容量的系统。多级交换结构p单级结构：数据包从输入端口到输出端口只经过一个交换单元。

24、p多级结构：交换单元按照层次组织（一层称为一级），数据包从输入端口到输出端口要经过多个层次的交换单元。多级交换结构的两种设计选择p交换结构在每一级上都设置队列，数据包一次一级地转发。允许更多的传输同时进行，吞吐量大，但代价高。p交换结构首先建立一条穿过所有层次的路径，然后数据包直接从输入端口发送到输出端口。吞吐量较低，代价较低。p多级结构中的队列数目由对性能和代价的权衡来确定。Banyan结构2-输入Banyan交换单元p每个交换单元有两个输入端口。p两个输出端口分别标记为“0”和“1”。p交换单元根据包中目的端口标号的某一位选择输出端口。Banyan结构（续）4-输入Banyan交换机Ban

25、yan结构（续）8-输入Banyan交换机pBanyan交换机的输入/输出端口数为2的幂次。Banyan结构的特点p扩展性好：可以很容易地扩展到任意的端口数目。p模块化设计：大的Banyan交换机可以通过互连较小的Banyan交换机构成。p自路由：不需要集中控制器，交换单元通过查看输出端口标号就知道如何转发。pBanyan交换机的最坏情况是所有的包都发往同一个输出端口。第二代网络系统p对第一代网络系统所做的扩展：n把更多的协议处理功能（特别是包的分类和转发）转移到了智能NIC上，大大减轻了CPU的负担。n引入了交换结构，允许数据包直接从一个端口转发到另一个端口而不需要CPU的参与。p与第一代网络系统相比，可以支持更多的网络接口和更高的端口速率。p不足：仍然依赖通用CPU处理例外的包（如带有选项的包、需要分片的包、出错的包等），当集合包速很高时，CPU依然是瓶颈。