IP报文分类算法概述

Survey of IP Packet Classification Algorithms

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.