| 基于TCAM的二维前缀报文分类算法 |
| |
| 引用本文： | 王志恒,李晓勇,白英彩.基于TCAM的二维前缀报文分类算法[J].上海交通大学学报,2004,38(1):9-13. |
| |
| 作者姓名： | 王志恒 李晓勇 白英彩 |
| |
| 作者单位： | 上海交通大学,计算机科学与工程系,上海,200030 |
| |
| 基金项目： | IntelIXAProject(No.9078) |
| |
| 摘 要： | 报文分类已成为保障网络应用的服务质量及安全性的重要手段，而二维的前缀报文分类则是其中最为常用的．通过对规则冲突的分析，提出了一个基于三态内容可寻址存储器(TCAM)的二维前缀报文分类算法，该算法借助TCAM的并行查找能力，在一个指令周期内找到前缀的最长匹配，采用内存映像及相关数据结构消除了规则之间的冲突，实现了快速的二维前缀分类查找．与其他二维分类算法相比，该算法具有最小的查找时间复杂度和较小的内存空间复杂度．
|
| 关 键 词： | 三态内容可寻址存储器 报文分类算法 二维前缀报文分类 |
| 文章编号： | 1006-2467(2004)01-0009-05 |
A TCAM-Based Two-Dimensional Prefix Packet Classification Algorithm |
| |
| WANG Zhi-heng,LI Xiao-yong,BAI Ying-cai.A TCAM-Based Two-Dimensional Prefix Packet Classification Algorithm[J].Journal of Shanghai Jiaotong University,2004,38(1):9-13. |
| |
| Authors: | WANG Zhi-heng LI Xiao-yong BAI Ying-cai |
| |
| Abstract: | 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. |
| |
| Keywords: | ternary content addressable memory(TCAM) packet classification(PC) algorithm two-(dimensional) prefix PC |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
