面向OC-768 的分类和转发技术
传统的数据库搜索解决方案不能满足不断增长的速率要求，必须采用基于大规模并行搜索和管线搜索的方法。尤其对于OC-768的网络分类和转发，采用并行搜索技术的网络搜索引擎和具有灵活管理功能的分类转发处理器显示了独特的性能优势，有效地提高了网络分类和转发处理效率，并具有高度的灵活性和动态扩展能力。
人们对数据传输带宽的需求促进了光传输速率的提高。10Gbps(OC-192)系统是当前发展的重点，同时，设计工程师正在积极开发40Gbps(OC-768)系统。带宽的提升将影响到网络的光收发器、FEC/PLL及成帧器、数据包解析及调整、数据包分类/转发、数据包分割与重组、排队和调度设计。
所有这些设计都很重要，但数据包的分类和转发无论就处理规则(rule)的数量，还是就处理速率而言都是最复杂而又最重要的。此外，随着基于规则的路由服务和服务质量(QoS)管理的应用不断拓宽，也促使设计工程师将复杂的分类处理和网络数据库搜索融入到涵盖从核心网络到边缘网络的路由和交换应用中。在当前的系统设计中，仅数据包分类和转发功能就可能占据线路卡70%的处理任务。在40Gbps速率中意味着每秒1.25亿个数据包处理，要进行高达200万个的记录分类和转发。
从互连网骨干网使用的光路由器和电信级交换机，到边缘汇集点和复杂的城域网(MAN)环境，线路速率的分类和不同数据流的转发需求已成为现实。随着对整体带宽(每秒传输的数据包)需求的提高，更为复杂的数据包搜索以及不断增大的网络数据库要求未来的系统设计能以比当前系统快数百倍的速率进行数据包包头比较并进行决策。
如上所述，当前数据库搜索解决方案运用的算法或哈希方案都无法适用于不断增长的速率，必须改进设计方法，设计出基于大规模并行搜索和管线搜索的方法。
分类和转发
网络处理单元(NPU)接收来自成帧器(framer)的数据包并对L3层分类进行数据包包头处理。NPU处理TCP包头，并解析出数据包中用于TCP会话(L4层)的SYN和FIN(数据流的起始和结束)。对于L4到L7层的分类，NPU校验URL、文件类型及数据包中的其它信息，然后，NPU将分类表的查寻键值(lookup key)及数据包类型信息传送至分类处理器。NPU还将转发表的查寻键值传送至转发处理器，进行最长词头匹配(LPM)搜索。
分类处理器接收分类查寻键值并搜索整个规则(或记录)数据库，以识别出数据流。该数据流中存储了特定分组数据流的流量、QoS和统计参数，而相关存储器则将这些参数返回至NPU。
分类数据库以不同的权值或优先级存储了多个规则。对于每个搜索，具有最高优先级的规则将用来返回规则和流量参数。分类流程的复杂度取决于分类数据库的大小、每个数据流记录的规则数目以及分类速率。
[page]
转发处理器接收转发查寻键值，该键值通常具有比分类查寻键值更少的字段。然后，转发处理器搜索转发规则数据库，以找到下一跳转(hop)地址的位置，相关存储器返回该地址和输出端接口到NPU。
NPU收到QoS参数后，将数据结构同数据包存储链接、数据包长度、数据包类型和流量工程参数进行组合。之后，数据流的信息键值发送至流量管理器或调度器，然后根据数据流的信息数据结构，对接收的数据流进行流量管理和流量调整。经过流量调整，每个数据流将进入调度控制部分，在这里采用加权公平排队(WFQ)规则，这样每个数据包将根据端口的有效性和WFQ规则进行调度，以发送到对应的输出端接口。
在入口路径上，NPU对来自存储区的数据包进行组合并发送至系统交换机。对于出口路径，NPU直接从交换接口接收数据并加以缓存，然后再发送至用于数据传输的成帧器。
40Gbps系统设计
对于40Gbps设计，理想的分类和转发器件能支持两百万个记录，并能以每秒1.25亿次搜索(MSPS)的速度对所有数据包字段的组合进行分类，这种分类是在8个或更多字段基础上进行的。此外，该器件还应支持建立在多个规则表基础上的并行搜索和专有功能，如用于TCP会话的URL会话检测、HTTP请求和回复检测、目标服务器选择和服务器/客户端会话，以保持负载平衡。
从硬件的角度看，数据库搜索、分类和转发功能必须灵活地与NPU、流量管理器和成帧器进行集成，以将设计复杂度和功耗降至最低的同时，使数据吞吐量达到最大。此外，还需要高效的接口来支持多个器件的数据处理和控制功能的集成。
另一个问题是需要对硬件结构进行分割，以使数据库搜索要求与其它处理任务相比，具有自主的灵活性，而单芯片器件将影响硬件的性能和灵活度。
为了满足电信级QoS服务级协议(SLA)，分类器必须能在L3层、L4层及以上各层处理多种规则，并支持OC-768确定的速率。为了在复杂的城域网中支持上百万用户以及用户间数千万的会话层，分类器必须能对具有2百万条规则的大型数据库进行操作。
以前的很多应用均采用大型、快速的转发设备与小型、复杂的分类设备相结合。但是更多的案例表明，使用从事分类和转发操作的增强型搜索子系统效率更高，也更有效，尤其是在新型高密度单芯片分类和转发引擎中更为明显。
为了在动态变化的网络中进行有效配置，分类和转发功能还必须快速简单地更新数据库。新一代搜索、分类和转发引擎必须保证网络管理人员维护详尽的表结构更方便，同时还必须保证数据库具有最高的效率和灵活度。
[page]
随着性能要求及数据库复杂度的增加，数据库搜索、分类和转发功能也由传统的使用基于算法的搜索方法转向使用专用器件。图2显示了不同的分类和转发方法。
ASIC/SDRAM搜索或者SRAM搜索
ASIC和SDRAM或者SRAM方法采用哈希(hash)和树型结构实现多种存储器搜索，这能满足OC-12或1G的线路速率。但是这些基于算法的方法具有非确定性，每个搜索所需的时间取决于地址表的大小、表中的特定地址以及采用的哈希函数。
不同的哈希函数需要不同的计算量来从一个记录中生成一个哈希键值，并且冲突(某种条件下，多个记录生成了相同的哈希键值)是不确定的。尽管算法不断得到改进，但其固有的不确定性使其难以满足网络设备不断增强的性能要求。
基于算法的实现还限制了搜索的灵活度，附加列表记录虽然可以减少搜索次数，但必须添加至每一个附属的千兆位以太网端口的地址列表中。当大型表记录，如那些用在基于规则的路由和IPv6路由应用中的记录的可能组合不断增加时，冲突发生的概率也相应增大。
设计工程师已成功地使用ASIC和SDRAM或SRAM方法满足OC-12或者1Gbps线路速率，并致力于将该方法应用于OC-48。但是，这些方法对于更多的规则以及更为复杂的分类(包括L4层)却显得力不从心。
例如在OC-48中，表的大小必须严格限制以保证性能，并避免产生过多的数据包丢失。此外，开发基于软件的搜索算法还将占用大量的系统资源，并延长设计进度，产生更多的不确定因素。
网络搜索引擎
与软件或哈希方法不一样，网络搜索引擎(NSE)代表了先进的并行搜索技术，该技术专门用于大量数据的高速搜索。在性能上，这些器件可有效地降低网络处理设备的网络搜索负担，使其能以比传统软件算法快数百倍的速率进行数据库搜索。NSE还能在单个周期内执行搜索操作，使搜索时间可以预测，即搜索时间是确定的。
目前最先进NSE的大型数据库可以在单个设备中容纳超过25万个路由记录，还允许用户定义大量的字段，用于QoS增强、IPv4/6分类和基于内容的分类功能。
每秒1.25亿次的搜索速率允许对复杂的L4~7层分类的每个数据包进行多项搜索，并使快速分层搜索具有极短的等待时间。不像那些在L3层分类实现OC-48的基于算法的搜索，NSE可以以稳定的OC-768 速率支持L4至7层分类搜索。
[page]
此外，由于NSE架构对复杂的搜索进行了优化，具有最大的灵活性，因此设计工程师具有很高的配置灵活度，如串联多个器件以支持更大的数据表。每个搜索引擎还必须能将记录配置成多个搜索宽度以适应各种各样的搜索要求，如36、72、144、288或576位宽。
这些设备可以以144位字执行125MSPS的搜索，这些144位字由5或6个典型的元组(tuple)分类规则组成。可支持规则的实际数目是规定搜索宽度的函数，例如当使用32位字宽结构时，当前的NSE最多可支持256K个独立的规则，而新一代NSE则有望支持512K个规则。
从维护数据库角度看，搜索引擎需要对记录进行分类和排序，以建立并维护分类优先级。表中较高优先级的记录放置在较高的位置，而较低优先级的记录则放置在较低的位置。通常，软件设计工程师对分类和转发表进行归类，以在不同的表分区中保持足够的空间。表分区可以基于LPM词头的长度或分类优先级之上，对于LPM，较长的词头出现在表的顶端，这样长词头匹配将比短词头匹配具有更高的优先级。为了支持快速更新以及较大的更新规模，用户需要在表中留出很大的空间。或者如下所述，设计工程师可选择带有能自动管理数据库优先级的内置功能的专用处理器。
分类和转发处理器
最新开发的用于分类和转发的专用处理器解决方案包含表管理功能，该功能允许用户灵活地为每个记录设置优先级，从而无须考虑表的分类和排序。分类和转发处理器(CFP)这一独特的功能可减少设计工程师软件和硬件配置时间，加速了网络设备的上市。
通过在整个数据库中嵌入记录的优先级权值信息，分类和转发处理器无须考虑所有的表管理开销，如分类、移动或预留空间。因此这些处理器几乎能以任意速率或大小动态地支持快速更新，这在不断变化的网络环境中很有用，如为终端用户服务进行动态供应的复杂边缘环境或带有基于规则的通信服务的汇集点。
目前，每个分类和转发处理器通常可支持128K个规则，并且搜索性能可达到100MSPS。与那些只支持普通NPU的早期分类器相比，CFP可处理整个范围内的分类和转发等数据
人们对数据传输带宽的需求促进了光传输速率的提高。10Gbps(OC-192)系统是当前发展的重点，同时，设计工程师正在积极开发40Gbps(OC-768)系统。带宽的提升将影响到网络的光收发器、FEC/PLL及成帧器、数据包解析及调整、数据包分类/转发、数据包分割与重组、排队和调度设计。
所有这些设计都很重要，但数据包的分类和转发无论就处理规则(rule)的数量，还是就处理速率而言都是最复杂而又最重要的。此外，随着基于规则的路由服务和服务质量(QoS)管理的应用不断拓宽，也促使设计工程师将复杂的分类处理和网络数据库搜索融入到涵盖从核心网络到边缘网络的路由和交换应用中。在当前的系统设计中，仅数据包分类和转发功能就可能占据线路卡70%的处理任务。在40Gbps速率中意味着每秒1.25亿个数据包处理，要进行高达200万个的记录分类和转发。
从互连网骨干网使用的光路由器和电信级交换机，到边缘汇集点和复杂的城域网(MAN)环境，线路速率的分类和不同数据流的转发需求已成为现实。随着对整体带宽(每秒传输的数据包)需求的提高，更为复杂的数据包搜索以及不断增大的网络数据库要求未来的系统设计能以比当前系统快数百倍的速率进行数据包包头比较并进行决策。
如上所述，当前数据库搜索解决方案运用的算法或哈希方案都无法适用于不断增长的速率，必须改进设计方法，设计出基于大规模并行搜索和管线搜索的方法。
分类和转发
 |
| 图1显示了从分类搜索包头的组合到调度包头的生成的分类和转发流程 |
分类处理器接收分类查寻键值并搜索整个规则(或记录)数据库，以识别出数据流。该数据流中存储了特定分组数据流的流量、QoS和统计参数，而相关存储器则将这些参数返回至NPU。
分类数据库以不同的权值或优先级存储了多个规则。对于每个搜索，具有最高优先级的规则将用来返回规则和流量参数。分类流程的复杂度取决于分类数据库的大小、每个数据流记录的规则数目以及分类速率。
[page]
转发处理器接收转发查寻键值，该键值通常具有比分类查寻键值更少的字段。然后，转发处理器搜索转发规则数据库，以找到下一跳转(hop)地址的位置，相关存储器返回该地址和输出端接口到NPU。
NPU收到QoS参数后，将数据结构同数据包存储链接、数据包长度、数据包类型和流量工程参数进行组合。之后，数据流的信息键值发送至流量管理器或调度器，然后根据数据流的信息数据结构，对接收的数据流进行流量管理和流量调整。经过流量调整，每个数据流将进入调度控制部分，在这里采用加权公平排队(WFQ)规则，这样每个数据包将根据端口的有效性和WFQ规则进行调度，以发送到对应的输出端接口。
在入口路径上，NPU对来自存储区的数据包进行组合并发送至系统交换机。对于出口路径，NPU直接从交换接口接收数据并加以缓存，然后再发送至用于数据传输的成帧器。
40Gbps系统设计
对于40Gbps设计，理想的分类和转发器件能支持两百万个记录，并能以每秒1.25亿次搜索(MSPS)的速度对所有数据包字段的组合进行分类，这种分类是在8个或更多字段基础上进行的。此外，该器件还应支持建立在多个规则表基础上的并行搜索和专有功能，如用于TCP会话的URL会话检测、HTTP请求和回复检测、目标服务器选择和服务器/客户端会话，以保持负载平衡。
从硬件的角度看，数据库搜索、分类和转发功能必须灵活地与NPU、流量管理器和成帧器进行集成，以将设计复杂度和功耗降至最低的同时，使数据吞吐量达到最大。此外，还需要高效的接口来支持多个器件的数据处理和控制功能的集成。
另一个问题是需要对硬件结构进行分割，以使数据库搜索要求与其它处理任务相比，具有自主的灵活性，而单芯片器件将影响硬件的性能和灵活度。
为了满足电信级QoS服务级协议(SLA)，分类器必须能在L3层、L4层及以上各层处理多种规则，并支持OC-768确定的速率。为了在复杂的城域网中支持上百万用户以及用户间数千万的会话层，分类器必须能对具有2百万条规则的大型数据库进行操作。
以前的很多应用均采用大型、快速的转发设备与小型、复杂的分类设备相结合。但是更多的案例表明，使用从事分类和转发操作的增强型搜索子系统效率更高，也更有效，尤其是在新型高密度单芯片分类和转发引擎中更为明显。
为了在动态变化的网络中进行有效配置，分类和转发功能还必须快速简单地更新数据库。新一代搜索、分类和转发引擎必须保证网络管理人员维护详尽的表结构更方便，同时还必须保证数据库具有最高的效率和灵活度。
[page]
随着性能要求及数据库复杂度的增加，数据库搜索、分类和转发功能也由传统的使用基于算法的搜索方法转向使用专用器件。图2显示了不同的分类和转发方法。
ASIC/SDRAM搜索或者SRAM搜索
ASIC和SDRAM或者SRAM方法采用哈希(hash)和树型结构实现多种存储器搜索，这能满足OC-12或1G的线路速率。但是这些基于算法的方法具有非确定性，每个搜索所需的时间取决于地址表的大小、表中的特定地址以及采用的哈希函数。
 |
基于算法的实现还限制了搜索的灵活度，附加列表记录虽然可以减少搜索次数，但必须添加至每一个附属的千兆位以太网端口的地址列表中。当大型表记录，如那些用在基于规则的路由和IPv6路由应用中的记录的可能组合不断增加时，冲突发生的概率也相应增大。
设计工程师已成功地使用ASIC和SDRAM或SRAM方法满足OC-12或者1Gbps线路速率，并致力于将该方法应用于OC-48。但是，这些方法对于更多的规则以及更为复杂的分类(包括L4层)却显得力不从心。
例如在OC-48中，表的大小必须严格限制以保证性能，并避免产生过多的数据包丢失。此外，开发基于软件的搜索算法还将占用大量的系统资源，并延长设计进度，产生更多的不确定因素。
网络搜索引擎
与软件或哈希方法不一样，网络搜索引擎(NSE)代表了先进的并行搜索技术，该技术专门用于大量数据的高速搜索。在性能上，这些器件可有效地降低网络处理设备的网络搜索负担，使其能以比传统软件算法快数百倍的速率进行数据库搜索。NSE还能在单个周期内执行搜索操作，使搜索时间可以预测，即搜索时间是确定的。
目前最先进NSE的大型数据库可以在单个设备中容纳超过25万个路由记录，还允许用户定义大量的字段，用于QoS增强、IPv4/6分类和基于内容的分类功能。
每秒1.25亿次的搜索速率允许对复杂的L4~7层分类的每个数据包进行多项搜索，并使快速分层搜索具有极短的等待时间。不像那些在L3层分类实现OC-48的基于算法的搜索，NSE可以以稳定的OC-768 速率支持L4至7层分类搜索。
[page]
此外，由于NSE架构对复杂的搜索进行了优化，具有最大的灵活性，因此设计工程师具有很高的配置灵活度，如串联多个器件以支持更大的数据表。每个搜索引擎还必须能将记录配置成多个搜索宽度以适应各种各样的搜索要求，如36、72、144、288或576位宽。
这些设备可以以144位字执行125MSPS的搜索，这些144位字由5或6个典型的元组(tuple)分类规则组成。可支持规则的实际数目是规定搜索宽度的函数，例如当使用32位字宽结构时，当前的NSE最多可支持256K个独立的规则，而新一代NSE则有望支持512K个规则。
从维护数据库角度看，搜索引擎需要对记录进行分类和排序，以建立并维护分类优先级。表中较高优先级的记录放置在较高的位置，而较低优先级的记录则放置在较低的位置。通常，软件设计工程师对分类和转发表进行归类，以在不同的表分区中保持足够的空间。表分区可以基于LPM词头的长度或分类优先级之上，对于LPM，较长的词头出现在表的顶端，这样长词头匹配将比短词头匹配具有更高的优先级。为了支持快速更新以及较大的更新规模，用户需要在表中留出很大的空间。或者如下所述，设计工程师可选择带有能自动管理数据库优先级的内置功能的专用处理器。
分类和转发处理器
最新开发的用于分类和转发的专用处理器解决方案包含表管理功能，该功能允许用户灵活地为每个记录设置优先级，从而无须考虑表的分类和排序。分类和转发处理器(CFP)这一独特的功能可减少设计工程师软件和硬件配置时间，加速了网络设备的上市。
通过在整个数据库中嵌入记录的优先级权值信息，分类和转发处理器无须考虑所有的表管理开销，如分类、移动或预留空间。因此这些处理器几乎能以任意速率或大小动态地支持快速更新，这在不断变化的网络环境中很有用，如为终端用户服务进行动态供应的复杂边缘环境或带有基于规则的通信服务的汇集点。
目前，每个分类和转发处理器通常可支持128K个规则，并且搜索性能可达到100MSPS。与那些只支持普通NPU的早期分类器相比，CFP可处理整个范围内的分类和转发等数据