高性能包分類技術及其應用研究.pdf

1、隨著計算機硬件體系結構和虛擬網(wǎng)絡的迅猛發(fā)展,包分類(PacketClassification)的運行模式發(fā)生了顯著的變化:首先,包分類的物理路由平臺從單核處理器向多核處理器過渡;其次,一個物理路由器需要被復用為大量的虛擬路由器。本文針對包分類運行模式的變化,研究支持大規(guī)模規(guī)則庫的高效多維包分類算法,以及在多核處理器路由平臺上支持多虛擬路由器的高效包分類技術,最后將提出的算法應用到網(wǎng)絡新型業(yè)務的流量識別中。
　　(1)支持大規(guī)模規(guī)則

2、庫的高效多維包分類算法包括:基于規(guī)則集壓縮的多維包分類決策樹研究和基于并行分布式聯(lián)合布魯姆過濾器的包分類算法。
　　基于規(guī)則集壓縮的多維包分類決策樹研究包括兩個部分,首先提出基于規(guī)則集壓縮的二維地址前綴匹配算法EGT-SC(Extended Grid of Triewith Sets Compression)。然后,針對新型業(yè)務的包分類規(guī)則庫特點,提出在多維多模式匹配情況下的四種包分類決策樹,通過實驗比較這些決策樹的時間和空間性能

3、差異,進而得出適合新型業(yè)務包分類的最佳算法。
　　基于并行分布式聯(lián)合布魯姆過濾器的包分類算法PDCBF(ParallelDistributed Combination Bloom Filter)分為兩個階段:規(guī)則存儲階段和包匹配階段,兩個階段的核心部件都是聚合結點。在規(guī)則存儲階段,算法將所有規(guī)則依據(jù)協(xié)議存放到三個匹配邏輯單元中,相對原始數(shù)據(jù)包匹配規(guī)則數(shù)目來說,每個邏輯單元的待匹配規(guī)則數(shù)目大大減少。包匹配階段分為三個步驟,協(xié)議匹配、

4、地址的單域匹配和聚合匹配。理論分析和實驗結果表明,PDCBF算法包匹配效率高、硬件資源消耗合理、包分類準確率高,是一種支持大規(guī)模規(guī)則庫的高效多維包分類算法。
　　(2)在多核處理器路由平臺上支持多虛擬路由器的包分類技術包括基于演化博弈(非合作博弈)和基于聯(lián)盟博弈(合作博弈)的多虛擬路由器的多核動態(tài)選擇算法。
　　非合作博弈方面,通過多個獨立群體的演化博弈分析和建模多虛擬路由器的多核動態(tài)選擇行為,演化均衡的策略分布作為最后的解

5、。本文基于演化博弈模型提出了三種演化算法:群體演化算法、強化學習算法和基于均衡迭代方程的分布式演化算法。實驗結果表明,三種算法都能夠實現(xiàn)多核的負載均衡,保障各個虛擬路由器公平地使用計算資源,并且維持系統(tǒng)穩(wěn)定的高吞吐量。基于均衡迭代方程的分布式演化算法比群體演化算法和強化學習算法具有更快的收斂速度。
　　合作博弈方面,本文針對多虛擬路由器的多核動態(tài)選擇問題建立聯(lián)盟博弈模型,通過聯(lián)盟形成的過程設計了一個多核選擇算法,即核聯(lián)盟算法。算法

6、中,核與核之間組成聯(lián)盟,每個核可以屬于不同的聯(lián)盟,由一個聯(lián)盟組成的集合為虛擬路由器提供計算服務。實驗結果表明,算法可以有效地實現(xiàn)多核的負載均衡和維持系統(tǒng)穩(wěn)定的高吞吐量。
　　(3)新型業(yè)務的流量識別技術包括兩個部分:基于H.323協(xié)議的VoIP語音流量識別技術和一種高效的P2P流量識別技術。
　　本文通過分析基于H.323協(xié)議的VoIP語音通信過程中出現(xiàn)的會話特征,提取出通信方的元組信息,進而識別整個語音會話流量。同時,設計

7、相應流結點的存儲、搜索和更新方案,提出一種H.323語音流量的識別算法。仿真實驗結果表明,與傳統(tǒng)流量識別方法相比,本文算法能夠更加準確地識別基于H.323協(xié)議的VoIP語音流量。
　　針對目前網(wǎng)絡中典型的P2P應用,本文通過分析通信終端會話過程中的特征,提取數(shù)據(jù)傳輸通道的五元組信息,建立P2P流量的識別規(guī)則庫,并且設計相應的流存儲結構和提出一種識別P2P流量的高效包分類算法。仿真實驗和實際的鏈路測試結果表明,與基于端口的識別方法和