基于多核處理器的可擴放包分類算法研究.pdf

1、當今的網(wǎng)絡需要為用戶提供更多、更快和更安全的服務。提供多樣性服務需要以數(shù)據(jù)包分類為基礎，數(shù)據(jù)包首先根據(jù)包頭中的相關域(一般為源/目的IP地址、源/目的端口號和協(xié)議五個域)被劃分到不同的流中，然后根據(jù)數(shù)據(jù)包所屬的流進行相應的處理。包分類已成為目前網(wǎng)絡處理的重要支撐技術(shù)之一。 隨著鏈路速度及網(wǎng)絡流量的不斷攀升，包分類已成為高速網(wǎng)絡處理的性能瓶頸。目前，無論硬件方法還是軟件方法都不能很好地滿足數(shù)據(jù)包分類處理的需要。硬件方法能夠提供很高

2、的分類速度，但不具備動態(tài)分類要求的靈活性；軟件方法靈活性好，但達不到高線速處理的要求。多核處理器的出現(xiàn)為實現(xiàn)高效、靈活的數(shù)據(jù)包分類提供了新的途徑，利用多核處理器的計算能力既可以獲得接近硬件的分類速度，同時又具有軟件算法的高度靈活性。然而，多核處理器上的并行程序設計目前依然是一個難題，如何設計具有良好可擴放性的并行算法還有許多問題需要解決。 本文工作主要包括兩個部分。第一部分針對目前的并行加速比模型不能很好地解釋在基于共享存儲的多

3、核處理器上出現(xiàn)的超線性加速及并行系統(tǒng)效率衰減的現(xiàn)象，提出了一種區(qū)分工作負載的并行加速比模型。該加速比模型將工作負載進一步區(qū)分為計算負載和訪存負載，通過顯式地引入系統(tǒng)訪存能力對并行系統(tǒng)加速比的影響，從理論上較好地解釋了超線性加速和并行系統(tǒng)效率衰減的現(xiàn)象，并通過實驗驗證了模型的有效性。根據(jù)該加速比模型，論文對基于多核處理器的并行程序設計提出了幾個設計原則，作為對設計可擴放的包分類算法的優(yōu)化指導。 論文的第二部分工作是設計和實現(xiàn)了一個

4、面向多核平臺的高速數(shù)據(jù)包分類算法TIC(Two-stage Interpreting based Classification)。TIC利用分類規(guī)則集特征以及多核平臺的體系結(jié)構(gòu)特點，將五元組數(shù)據(jù)包分類過程分成針對源/目的IP地址的二維前綴查找和針對另外三個域的范圍查找兩個階段。第二階段采用基于解釋器的范圍查找，極大地減小了算法的內(nèi)存消耗，同時利用多核處理器充足的計算能力來完成解釋執(zhí)行的任務。從本質(zhì)上說，TIC通過平衡算法的計算負載和訪存