基于多級查找的高效包分類算法研究及應用.pdf

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

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

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