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

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

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

3、前分類速度最快的多維包分類算法，但其縮減樹不支持增量更新。TIC相比RFC極大地減少了存儲消耗和預處理時間，并保持了與RFC相當?shù)姆诸愃俣?，但它仍不支持增量更新?br>　　 因此，本文利用遞歸空間分解來替換TIC第一階段的RFC縮減樹，提出了一個支持快速增量更新的兩階段多維包分類算法TICS。但是，遞歸空間分解生成的AQT樹中存在很多空結點，AQT樹路徑過長導致查找性能不佳。通過兩種路徑壓縮技術來壓縮樹路徑，以提高查找性能。利用樹結

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