计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2005年
8期
1-3,77
,共4页
IP分类%查找算法%冲突率%异或哈希
IP分類%查找算法%遲突率%異或哈希
IP분류%사조산법%충돌솔%이혹합희
文章在哈希算法的基础上,提出了一种基于异或哈希的IP分类算法,该算法的核心有三点:一是将目的/源IP、目的/源端口和协议五域连成比特串,然后分为五块后进行异或,获得分类关键值;二是为了降低冲突率,将异或后的关键值再与一个随机数进行异或,获得最终分类索引值;三是为了保证查找到的规则的正确性,对每一个索引值的源/目的IP地址均匹配一次.通过以上三点改进一般会降低算法的时间复杂度和空间复杂度,通过仿真,当对1万条分类规则进行包分类时,该算法的包分类速度可以达到2Mpps,所消耗的最大内存为6MB.
文章在哈希算法的基礎上,提齣瞭一種基于異或哈希的IP分類算法,該算法的覈心有三點:一是將目的/源IP、目的/源耑口和協議五域連成比特串,然後分為五塊後進行異或,穫得分類關鍵值;二是為瞭降低遲突率,將異或後的關鍵值再與一箇隨機數進行異或,穫得最終分類索引值;三是為瞭保證查找到的規則的正確性,對每一箇索引值的源/目的IP地阯均匹配一次.通過以上三點改進一般會降低算法的時間複雜度和空間複雜度,通過倣真,噹對1萬條分類規則進行包分類時,該算法的包分類速度可以達到2Mpps,所消耗的最大內存為6MB.
문장재합희산법적기출상,제출료일충기우이혹합희적IP분류산법,해산법적핵심유삼점:일시장목적/원IP、목적/원단구화협의오역련성비특천,연후분위오괴후진행이혹,획득분류관건치;이시위료강저충돌솔,장이혹후적관건치재여일개수궤수진행이혹,획득최종분류색인치;삼시위료보증사조도적규칙적정학성,대매일개색인치적원/목적IP지지균필배일차.통과이상삼점개진일반회강저산법적시간복잡도화공간복잡도,통과방진,당대1만조분류규칙진행포분류시,해산법적포분류속도가이체도2Mpps,소소모적최대내존위6MB.