李 賓 劉淑媛 劉衍珩
摘要:通過分析Internet網(wǎng)絡(luò)主干路由器分組分類的關(guān)鍵問題和解決方案,提出了基于散列表的快速分組分類算法,該算法時(shí)間復(fù)雜度為O(1);通過分析規(guī)則表的相關(guān)性將規(guī)則表分成相關(guān)子集和不相關(guān)子集,對不相關(guān)子集采用哈希法構(gòu)造散列表.實(shí)驗(yàn)測試表明,所給算法比順序匹配算法的吞吐率提高近10%.進(jìn)一步分析了規(guī)則沖突,并給出了沖突的理論證明和查找算法。
關(guān)鍵詞:分組分類;散列表;規(guī)則表;相關(guān)規(guī)則;沖突檢測
中圖分類號:TP393
文獻(xiàn)標(biāo)識碼:A
文章編號:1671-5489(2005)06-0787-07