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

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

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

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

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