Approximate Discovery of Service Nodes by Duplicate Detection in Flows  

作　　者：Zhou Changling Xiao Jianguo Cui Jian Zhang Bei Li Feng 

机构地区：[1]Peking Univ, Ctr Comp, Beijing 100871, Peoples R China [2]Peking Univ, Sch Elect Engn & Comp Sci, Beijing 100871, Peoples R China [3]Peking Univ, Inst Comp Sci & Technol, Beijing 100871, Peoples R China [4]Shenyang Acad Governance, Shenyang 110000, Peoples R China

出　　处：《China Communications》2012年第5期75-89,共15页中国通信（英文版）

基　　金：supported by the National Basic Research Program of China under Grant No. 2009CB320505

摘　　要：Discovery of service nodes in flows is a challenging task, especially in large ISPs or campus networks where the amount of traffic across net-work is rmssive. We propose an effective data structure called Round-robin Buddy Bloom Filters （RBBF） to detect duplicate elements in flows. A two-stage approximate algorithm based on RBBF which can be used for detecting service nodes from NetFlow data is also given and the perfonmnce of the algorithm is analyzed. In our case, the proposed algorithm uses about 1% memory of hash table with false positive error rate less than 5%. A proto-type system, which is compatible with both IPv4 and IPv6, using the proposed data structure and al-gorithm is introduced. Some real world case studies based on the prototype system are discussed.Discovery of service nodes in flows is a challenging task,especially in large ISPs or campus networks where the amount of traffic across network is massive.We propose an effective data structure called Round-robin Buddy Bloom Filters(RBBF) to detect duplicate elements in flows.A two-stage approximate algorithm based on RBBF which can be used for detecting service nodes from NetFlow data is also given and the performance of the algorithm is analyzed.In our case,the proposed algorithm uses about 1% memory of hash table with false positive error rate less than 5%.A prototype system,which is compatible with both IPv4 and IPv6,using the proposed data structure and algorithm is introduced.Some real world case studies based on the prototype system are discussed.

关 键 词：duplicate detection service nodes dis-covery buddy bloom filter round-robin schema NETFLOW 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] U467.4[自动化与计算机技术—计算机科学与技术]