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

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

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

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

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