IP报文分类算法概述  

Survey of IP Packet Classification Algorithms

作　　者：谭明锋[1] 高蕾[1] 龚正虎[1] 徐田荣 

机构地区：[1]国防科学技术大学计算机学院,博士生长沙410073 [2]中国电子设备系统工程公司计算站,北京100089

出　　处：《计算机科学》2005年第11期5-10,19,共7页Computer Science

基　　金：国家重点基础研究发展计划(973计划);新一代互联网路由与交换理论(No.2003CB314802)资助课题

摘　　要：Internet的高速发展要求提供高性能的IP流分类算法以更好地为防火墙、QoS、流量工程、资源预留、网络地址转换等提供服务。由于IP报文分类算法的多域特征,因此其具有相当的难度。研究者提出了很多报文分类算法,本文将这些算法概括为5类:基于Trie树的算法、基于空间分割的算法、启发式算法、基于硬件实现的算法和其他算法,并对IP报文分类算法的思想、原理和过程进行了介绍和分析,说明了这些算法之间的联系,并对这些算法在搜索和更新的时间性能、空间性能、适用性范围和优缺点等进行了分析和比较。作为总结,本文还对IP报文分类算法研究的方法和趋势进行了分析和总结。The fast incensement of lnternet requires high performance IP packet classification algorithms to serve different services, such as fire wall, QoS, traffic engineering, resource reservation, net address translation, etc. IP packet classification is a hard problem due to its multiple dimension character, hence researchers have proposed a variety of algorithms which can be categorized as algorithms based on Tries, algorithms based on space splitting, heuristic algorithms, hardware-speclflc algorithms and other algorithms. This tutorial describes the main idea and process of these algorithms, and the relationship among them, Also this paper discusses the suitable application for each algorithm, and compares their performance, their strong points and weak points. As the conclusion, this paper summarizes the main research methods and the trends of the IP packet classification algorithms.

关 键 词：IP报文分类 路由器 流量工程 QOS 区分服务 分类算法 IP报文 INTERNET 网络地址转换 时间性能 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论] TP393.08[自动化与计算机技术—计算机科学与技术]