CAJ | 학술논문

针对IP路由查找中的最长前缀匹配问题，提出了一种基于Bloom滤波器的快速路由查找方法。首先，通过建立首字节索引表，减少了需要并行查询的Bloom 滤波器的数量。其次，基于IP地址前缀长度分布的不均匀性对Bloom滤波器组的设置进行了优化，降低了查询过程对Bloom滤波器总数的需求。最后，将基本Bloom滤波器位向量中的每一比特位与一个计数器相关联，实现了对路由更新的支持。理论分析表明，与现有方法相比，利用该方法进行路由查找可以实现更低的选路表平均探测次数，并在最坏情况下具有更低的平均探测次数上界。实验结果验证了该方法的有效性及相关理论分析的正确性。
침대IP로유사조중적최장전철필배문제，제출료일충기우Bloom려파기적쾌속로유사조방법。수선，통과건립수자절색인표，감소료수요병행사순적Bloom 려파기적수량。기차，기우IP지지전철장도분포적불균균성대Bloom려파기조적설치진행료우화，강저료사순과정대Bloom려파기총수적수구。최후，장기본Bloom려파기위향량중적매일비특위여일개계수기상관련，실현료대로유경신적지지。이론분석표명，여현유방법상비，이용해방법진행로유사조가이실현경저적선로표평균탐측차수，병재최배정황하구유경저적평균탐측차수상계。실험결과험증료해방법적유효성급상관이론분석적정학성。
To solve the problem of the longest prefix matching in IP routing lookups, a fast IP routing lookup meth?od based on Bloom filters was proposed. A first?byte indexing table was established to reduce the number of Bloom filters to be queried in parallel. The number of Bloom filters was optimized based on the non?uniform distribution of the prefix lengths of IP addresses, so that the number of Bloom filters required in IP lookups was reduced. The up?date of routing tables was supported by associating a counter with each bit in the bit vectors of the basic Bloom fil?ters. The theoretical analysis showed the proposed method is more efficient than the existing methods with less aver?aged number of times to probe into the route selection tables, and lowers its upper bound under the worst circum?stances. Experimental results validated the efficacy of the proposed method and proved the accuracy of the perform?ance analysis.