基于聚類的高效包分類算法研究及其應(yīng)用.pdf

1、近年來，網(wǎng)絡(luò)技術(shù)的發(fā)展催生了很多新興的網(wǎng)絡(luò)應(yīng)用，但是現(xiàn)有的網(wǎng)絡(luò)性能不能很好地支持這些應(yīng)用。性能良好的包分類算法對于網(wǎng)絡(luò)性能的提升具有至關(guān)重要的作用。網(wǎng)絡(luò)已經(jīng)逐漸出現(xiàn)僵化的狀態(tài)，很大程度上影響了其性能的提升空間。OpenFlow成為互聯(lián)網(wǎng)創(chuàng)新理念的強(qiáng)大促成者。而OpenFlow網(wǎng)絡(luò)中由于其靈活性和可擴(kuò)展性，對包分類的要求更高更復(fù)雜，現(xiàn)有研究中很少有專門針對OpenFlow包分類的解決方案，并且在性能上存在一定的局限性。因此，設(shè)計一款針對O

2、penFlow的包分類方案成為當(dāng)務(wù)之急。
　　針對上述問題，本文主要做了以下工作:
　　(1)根據(jù)數(shù)據(jù)挖掘中的聚類思想提出了一種基于無前綴關(guān)系聚類的高效層次Trie樹結(jié)構(gòu)，該方案依據(jù)的是不同前綴關(guān)系聚類的方式來消除回溯。算法首先會根據(jù)前綴關(guān)系來將規(guī)則劃分為不同的聚類，然后再根據(jù)這些聚類來構(gòu)建多棵層次特里樹，在單棵層次特里樹中就不存在前綴關(guān)系的節(jié)點(diǎn)，從而消除了回溯。并且由于算法結(jié)構(gòu)采用了節(jié)點(diǎn)的路徑壓縮策略，該結(jié)構(gòu)在很大程度上提

3、高算法的存儲性能。
　　(2)針對OpenFlow的超五元組包分類，本文提出了另一種聚類方式，也就是基于前綴長度聚類的設(shè)計方案。該方案根據(jù)前綴長度對不同的前綴進(jìn)行聚類，每個聚類中的前綴都具有相同的前綴長度。然后再選擇性地對這些聚類進(jìn)行合并,進(jìn)行選擇的原則除了滿足聚類元素數(shù)目的要求，也需要滿足合并之后的聚類內(nèi)部元素之間不具有前綴關(guān)系的要求。最后將生成的聚類構(gòu)建為層次特里樹。
　　(3)針對OpenFlow12元組匹配問題，本文