小型微型计算机系统
小型微型計算機繫統
소형미형계산궤계통
MINI-MICRO SYSTEMS
2006年
6期
1023-1028
,共6页
戴雪龙%王永纲%石江涛%颜天信
戴雪龍%王永綱%石江濤%顏天信
대설룡%왕영강%석강도%안천신
包分类%层压缩树包分类算法%时间性能曲线%空间性能曲线%仿真测试
包分類%層壓縮樹包分類算法%時間性能麯線%空間性能麯線%倣真測試
포분류%층압축수포분류산법%시간성능곡선%공간성능곡선%방진측시
包分类技术是下一代网络设备的关键技术之一.研究有效的包分类算法是目前网络技术领域的热门课题.层压缩树包分类算法的基本思想是:对路径压缩之后的二叉树进行层压缩,使压缩树中的节点能够按序存储在数组中.通过对数组元素跳跃式的查找快速的对包头进行分类.仿真试验结果表明该算法在较大规则数下能够实现对包头的快速分类,分类速度可以达到每秒处理接近2M个包头,具有O(d)的时间复杂度(d为域的个数);在中等规模规则数下具有O(dN)的空间复杂度,并且其存储量优于其他算法(如Bitmap和区域分割包分类算法).由于层压缩树算法对包头的每个域独立查找,在硬件实现上采用并行查找各个域的处理方式将使该算法的查找性能得到更大的提高.
包分類技術是下一代網絡設備的關鍵技術之一.研究有效的包分類算法是目前網絡技術領域的熱門課題.層壓縮樹包分類算法的基本思想是:對路徑壓縮之後的二扠樹進行層壓縮,使壓縮樹中的節點能夠按序存儲在數組中.通過對數組元素跳躍式的查找快速的對包頭進行分類.倣真試驗結果錶明該算法在較大規則數下能夠實現對包頭的快速分類,分類速度可以達到每秒處理接近2M箇包頭,具有O(d)的時間複雜度(d為域的箇數);在中等規模規則數下具有O(dN)的空間複雜度,併且其存儲量優于其他算法(如Bitmap和區域分割包分類算法).由于層壓縮樹算法對包頭的每箇域獨立查找,在硬件實現上採用併行查找各箇域的處理方式將使該算法的查找性能得到更大的提高.
포분류기술시하일대망락설비적관건기술지일.연구유효적포분류산법시목전망락기술영역적열문과제.층압축수포분류산법적기본사상시:대로경압축지후적이차수진행층압축,사압축수중적절점능구안서존저재수조중.통과대수조원소도약식적사조쾌속적대포두진행분류.방진시험결과표명해산법재교대규칙수하능구실현대포두적쾌속분류,분류속도가이체도매초처리접근2M개포두,구유O(d)적시간복잡도(d위역적개수);재중등규모규칙수하구유O(dN)적공간복잡도,병차기존저량우우기타산법(여Bitmap화구역분할포분류산법).유우층압축수산법대포두적매개역독립사조,재경건실현상채용병행사조각개역적처리방식장사해산법적사조성능득도경대적제고.