CAJ | 학술논문

URL 查找是众多网络系统中重要的组成部分，如 URL 过滤系统、Web 缓存等．随着互联网的迅速发展， URL 查找面临的主要挑战是实现大规模 URL 集合下的高速查找，同时保证低存储和低功耗．本文提出了一种基于并行 Bloom Filter 的 URL 查找算法，CaBF．该算法高度并行化，提供大规模 URL 集合下的高速最长前缀匹配，并很好地适应集合中不同数量的 URL 组件．理论分析和真实网络数据集上的实验表明，该算法相比现有算法可以降低假阳性概率达一个数量级（或者在满足相同假阳性概率的前提下降低存储和硬件逻辑资源消耗）．此外，该方法的体系结构很容易映射到 FPGA 等硬件器件上，提供每秒超过150M次的 URL 查找速度．
URL 사조시음다망락계통중중요적조성부분，여 URL 과려계통、Web 완존등．수착호련망적신속발전， URL 사조면림적주요도전시실현대규모 URL 집합하적고속사조，동시보증저존저화저공모．본문제출료일충기우병행 Bloom Filter 적 URL 사조산법，CaBF．해산법고도병행화，제공대규모 URL 집합하적고속최장전철필배，병흔호지괄응집합중불동수량적 URL 조건．이론분석화진실망락수거집상적실험표명，해산법상비현유산법가이강저가양성개솔체일개수량급（혹자재만족상동가양성개솔적전제하강저존저화경건라집자원소모）．차외，해방법적체계결구흔용역영사도 FPGA 등경건기건상，제공매초초과150M차적 URL 사조속도．
URL lookup is fundamental to numerous networking systems,including URL filters,web caches,etc.With the ex-plosive development of the Internet,the main challenge in implementing URL lookup operation is to achieve fast lookup speed and accommodate large URL sets while keeping memory and power consumption low.This paper presents a new URL lookup scheme based on parallel Bloom Filters.It can adapt to set cardinality and perform fast longest prefix matching(LPM)with large URL sets in a highly parallel fashion.The theoretical analysis and experiments on real-life data traces show that the proposed approach leads to reduced false positive probability for up to an order of magnitude(or reduced memory and hardware logic resources with the same false positive probability guaranteed)compared with the existing methods.Moreover,the architecture can be easily mapped to the state-of-the-art FPGAs with moderate resource consumption to provide over 150M lookups per second.