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

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

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

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