基于單鏈接和期望最大化規(guī)則聚類的包分類技術.pdf

1、計算機網絡的核心設備是路由器和防火墻等，包分類技術(PacketClassification)是這些核心設備的關鍵技術，它制約著計算機網絡帶寬的發(fā)展，因此，包分類研究具有重要的現實意義和應用前景。現有的包分類技術主要分為基于軟件和硬件實現的技術，基于軟件的技術主要通過復雜數據結構來構造包分類算法，該類算法存在性能瓶頸;基于硬件的技術通過設計專用的硬件體系結構加快包分類過程，該類算法代價高、不易于擴展。本文利用聚類分析的理論和包分類聚集特

2、征將包分類問題映射成空間中點定位問題，并設計相應的包分類算法，提高包分類性能。針對現有包分類算法中存在的常見問題，本文主要做了以下工作:
　　(1)提出了一種基于幾何空間的包分類問題形式化方法。該方法首先將數據包和規(guī)則庫中的規(guī)則映射成空間中的矩形區(qū)域，其次取該矩形區(qū)域的中心點代表該數據包或規(guī)則，最終將包分類問題轉化為空間中點與點之間的距離問題。理論分析和實驗結果表明，利用該方法處理的規(guī)則庫易于進行聚類分析，并能實現數據包與規(guī)則庫的

3、高效匹配。
　　(2)提出了一種基于單鏈接聚類的分支樹包分類算法。該算法分為兩個階段。第一，預處理階段，采用包分類問題形式化方法把規(guī)則和數據包進行形式化成空間坐標中的點，再利用單鏈接算法對已形式化的規(guī)則進行聚類形成多個簇;第二，包匹配階段，根據現有的簇構建分支樹并完成包的匹配過程。實驗結果表明，該方法包匹配效率高、包分類準確率高，是一種支持大規(guī)模規(guī)則庫的高效包分類算法。
　　(3)提出了一種基于期望最大化聚類的層次特里樹包分