基于多級(jí)查找的高效包分類算法研究及應(yīng)用.pdf

1、隨著網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，越來越多的網(wǎng)絡(luò)業(yè)務(wù)需要對(duì)數(shù)據(jù)包進(jìn)行快速、準(zhǔn)確的分類，包分類已經(jīng)成為高速路由器的一個(gè)性能瓶頸，如何在良好的時(shí)間和空間性能下進(jìn)行快速、高效的包分類是目前需要解決的一個(gè)難題。本文在研究了眾多不同類型的包分類算法基礎(chǔ)上，將網(wǎng)絡(luò)中流的局部特性和布魯姆過濾器相結(jié)合，設(shè)計(jì)了一種高效的包分類算法，并對(duì)該算法進(jìn)行拓展應(yīng)用，表現(xiàn)出了良好的性能。本文主要研究成果如下:
　　 一、是針對(duì)高速網(wǎng)絡(luò)中包分類算法問題提出一種基于流的局

2、部特性和多級(jí)查找的高效包分類算法(packet classification algorithm based on the flow localityprinciples and multi-level lookup，簡稱PCFM)。PCFM算法將網(wǎng)絡(luò)中數(shù)據(jù)流的局部特性和計(jì)數(shù)布魯姆過濾器的優(yōu)點(diǎn)進(jìn)行了有效的結(jié)合，該算法分為三級(jí):第一級(jí)緩存用于存放最近10秒內(nèi)到達(dá)的流，第二級(jí)計(jì)數(shù)布魯姆過濾器存放最近10秒至60秒內(nèi)到達(dá)的流，第三級(jí)計(jì)數(shù)布魯姆

3、過濾器存放剩余的流。實(shí)驗(yàn)表明:該算法不僅可以支持規(guī)則庫動(dòng)態(tài)更新，相比傳統(tǒng)的包分類算法，在消耗內(nèi)存接近的情況下時(shí)間性能還提高了30％左右。
　　 二、是將改進(jìn)的基于流的局部特性和多級(jí)查找的高效包分類算法應(yīng)用到網(wǎng)絡(luò)流量識(shí)別中。選取網(wǎng)絡(luò)中較為典型的兩種流(HTTP流和PPlive流)，并對(duì)它們的包長和時(shí)間屬性特征進(jìn)行分析。分析發(fā)現(xiàn)HTTP流具有包大、更新慢、穩(wěn)定等特征，而PPlive流則具有包小、更新快、容量大等特征，然后根據(jù)兩種流的