支持快速增量更新的包分類算法研究.pdf

1、隨著Internet的迅速發(fā)展，網(wǎng)絡(luò)服務(wù)日趨多樣化，新的網(wǎng)絡(luò)應(yīng)用層出不窮。包分類技術(shù)是網(wǎng)絡(luò)服務(wù)多樣化的基礎(chǔ)，它使得路由器能夠區(qū)分地處理網(wǎng)絡(luò)流量。隨著一些實(shí)時(shí)性要求很高的新興應(yīng)用出現(xiàn)，服務(wù)質(zhì)量(Quality ofService)保證技術(shù)越來越重要，該技術(shù)通常需要頻繁地更新分類規(guī)則集。然而，現(xiàn)有大多數(shù)包分類算法主要關(guān)心分類速度和空間需求的改進(jìn)，而不太重視更新性能。更新操作過于復(fù)雜，有的甚至需要重建整個(gè)數(shù)據(jù)結(jié)構(gòu)，更新代價(jià)昂貴。這使得這些算法

2、不適合那些要求動(dòng)態(tài)分類的新興應(yīng)用，動(dòng)態(tài)分類必須在滿足線速(Line-rate)的同時(shí)快速地更新規(guī)則集。因此，研究如何實(shí)現(xiàn)一個(gè)支持快速增量更新并且滿足線速分類要求的包分類算法具有重要的實(shí)際意義。
　　 本文先分析了現(xiàn)有典型的包分類算法。發(fā)現(xiàn)遞歸空間分解是目前更新性能最好的二維包分類算法，因?yàn)樗哂蟹浅：玫母戮植啃?。并發(fā)現(xiàn)兩階段多維包分類算TIC很好地利用了規(guī)則集特征，其第一階段采用RFC縮減樹，第二階段引入解釋器方法。RFC是目

3、前分類速度最快的多維包分類算法，但其縮減樹不支持增量更新。TIC相比RFC極大地減少了存儲(chǔ)消耗和預(yù)處理時(shí)間，并保持了與RFC相當(dāng)?shù)姆诸愃俣龋圆恢С衷隽扛隆?br>　　 因此，本文利用遞歸空間分解來替換TIC第一階段的RFC縮減樹，提出了一個(gè)支持快速增量更新的兩階段多維包分類算法TICS。但是，遞歸空間分解生成的AQT樹中存在很多空結(jié)點(diǎn)，AQT樹路徑過長(zhǎng)導(dǎo)致查找性能不佳。通過兩種路徑壓縮技術(shù)來壓縮樹路徑，以提高查找性能。利用樹結(jié)

4、構(gòu)特點(diǎn)，采用局部數(shù)據(jù)結(jié)構(gòu)重建替換的方法，并結(jié)合對(duì)數(shù)據(jù)結(jié)構(gòu)的內(nèi)存管理，在多核平臺(tái)上實(shí)現(xiàn)了共享數(shù)據(jù)結(jié)構(gòu)的單寫者多讀者并行無鎖實(shí)時(shí)規(guī)則集增量更新，消除了更新和查找共享數(shù)據(jù)結(jié)構(gòu)之間的同步開銷，避免了更新導(dǎo)致的查找中斷。
　　 實(shí)驗(yàn)結(jié)果表明，TICS算法的更新速度比現(xiàn)有更新最快算法至少提升了一個(gè)數(shù)量級(jí)。路徑壓縮技術(shù)既減少了存儲(chǔ)消耗，又提高了查找性能。雖然TICS算法相比TIC算法絕對(duì)分類速度差距較大，但TICS算法具有優(yōu)異的并行可擴(kuò)放性，