基于多域并行编码的高速IPv6流分类  

Ultra-High Speed IPv6 Packet Classification Based on Parallel Multi-Field Encoding

作　　者：李维[1] 刘斌[1] 郗颖[1] 林伟[1] 唐毅[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084

出　　处：《电子学报》2007年第5期976-981,共6页Acta Electronica Sinica

基　　金：自然科学基金(No.60373007;No.60573121;No.60625201);中国-爱尔兰政府间国际科技合作项目(No.CI-2003-02);高等学校博士学科点专项科研基金(No.20040003048);教育部科技创新工程重大项目培育资金项目(No.705003)

摘　　要：IPv6的多域流分类是高速路由器设计中的一个难点.本文提出了一种使用TCAM的高速IPv6流分类方案,其核心思想是:(1)区分IPv6包头5个域字段的不同特征,根据IPv6地址的特征及其分配信息对其进行压缩,对TCP端口域实施扩展的层次编码,根据统计数据对协议域进行压缩,最终结果是把原始域的296比特转换成280比特的查找关键字,与TCAM的表项宽度相匹配;(2)使用嵌入SSRAM表查找技术,对5个域并行进行独立编码,消除瓶颈编码环节,达到线速处理要求;(3)分类规则数据库按照本文预设计的编码方式存储在TCAM中,使用流水线技术让域的编码操作和查找操作并行执行,每个TCAM访存周期完成一次查找操作.同时,为解决范围匹配问题,本文设计了一种预定义位宽的动态范围编码算法,既节省了TCAM的存储空间,又提高了硬件规则库的更新速度.分析和仿真表明,当路由查找和流分类共用一个TCAM时,使用较低的工作频率(66MHz),流分类和路由查找速度均可达到22Mpps,满足高速OC-192接口的线速查找与流分类要求.One challenging issue in IPv6 high speed routers＇ design is the multi-field classification at line-rate for interface 1312-192 and beyond. This paper proposes an efficient ultra-high speed IPv6 packet classification engine （classifier） based on TCAM （Ternary Content Addressable Memory）. The key ideas are： （ 1 ） encoding the five fields according to their distinct features： we compress the IPv6 source/destination address fields based on the features of their formats and the distribution styles,apply an extended hierarchical coding method to TCP source/destination port fields and encode the protocol field based on the statistics. In this way,the original five-tuple with 296-bit length is converted into a 280-bit one which can fit well into the configured width of existing commercial TCAMs; （2） an embedded SSRAM table search technique is adopted to independently encode the five fields in parallel,elirninating the encoding bottleneck and guaranteeing the line-rate processing; （ 3 ） The rides of the classifier are stored in TCAMs according to the pre-designed coding formats. Utilization of pipeline makes the field coding operation and the rule＇ s search running parallel, which results the classifier outputting a search result within a single TCAM access. What＇ s more, to effectively solve the range matching problem, we present a dynamic range encoding scheme which greatly reduces the storage requirement for TCAMs and increases the updating speed. Analysis and simulation demonstrate that running TCAMs at a frequency of 66MHZ（ relatively low） ,the engine can reach a speed of over 22M packets per second （Mpps） for both the lookup and the packet classification respectively when integrated,and this perfectly satisfies the OC-192 interface＇ s line-rate processing.

关 键 词：IP包 IPV6 TCAM 多域流分类 编码 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]