基于TCAM的二维前缀报文分类算法  

A TCAM-Based Two-Dimensional Prefix Packet Classification Algorithm

作　　者：王志恒[1] 李晓勇[1] 白英彩[1] 

机构地区：[1]上海交通大学计算机科学与工程系,上海200030

出　　处：《上海交通大学学报》2004年第1期9-13,共5页Journal of Shanghai Jiaotong University

基　　金：IntelIXAProject(No.9078)

摘　　要：报文分类已成为保障网络应用的服务质量及安全性的重要手段,而二维的前缀报文分类则是其中最为常用的.通过对规则冲突的分析,提出了一个基于三态内容可寻址存储器(TCAM)的二维前缀报文分类算法,该算法借助TCAM的并行查找能力,在一个指令周期内找到前缀的最长匹配,采用内存映像及相关数据结构消除了规则之间的冲突,实现了快速的二维前缀分类查找.与其他二维分类算法相比,该算法具有最小的查找时间复杂度和较小的内存空间复杂度.Packet classification (PC) becomes an important method to support the QoS and security of network, in which two-dimensional prefix PC is the most popular one. Based on the analysis of ruler conflict, a TCAM-based two-dimensional prefix PC algorithm was presented. This algorithm adopts the parallelism of TCAM to look up the longest prefix in one instruction cycle. Then it uses a memory image and associated data structures to eliminate the ruler conflicts, and performs a fast two-dimensional prefix PC. Compared with other algorithms, it has the least time complexity and less space complexity.

关 键 词：三态内容可寻址存储器 报文分类算法 二维前缀报文分类 

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