Accelerating Packet Classification with Counting Bloom Filters for Virtual Open Flow Switching

The growing trend of network virtualization results in a widespread adoption of virtual switches in virtualized environments. However, virtual switching is confronted with great performance challenges regarding packet classification especially in Open Flow-based software defined networks. This paper first takes an insight into packet classification in virtual Open Flow switching, and points out that its performance bottleneck is dominated by flow table traversals of multiple failed mask probing for each arrived packet. Then we are motivated to propose an efficient packet classification algorithm based on counting bloom filters. In particular, counting bloom filters are applied to predict the failures of flow table lookups with great possibilities, and bypass flow table traversals for failed mask probing. Finally, our proposed packet classification algorithm is evaluated with real network traffic traces by experiments. The experimental results indicate that our proposed algorithm outperforms the classical one in Open v Switch in terms of average search length, and contributes to promote virtual Open Flow switching performance.

基于Bloom Filter本地差分隐私的基数估计

计算机技术和通信技术的共同发展,使得数据呈现指数大爆炸式的增长。数据中蕴含的巨大价值是有目共睹的。但是对数据集的肆意收集与分析,使用户的隐私数据处在被泄露的风险中。为保护用户的敏感数据的同时实现对基数查询的有效响应,提出一种基于差分隐私的隐私保护算法BFRRCE(Bloom Filter Random Response for Cardinality Estimation)。首先对用户的数据利用Bloom Filter数据结构进行数据预处理,然后利用本地差分隐私的扰动算法对数据进行扰动,达到保护用户敏感数据的目的。

一种基于bloom-filters的半连接查询优化算法

以传输费用最小为目的,提出一种新的查询优化算法。该算法以连接属性为关键字,利用半连接关系建立bloom-filters,在半连接关系间相互传送bloom-filters,从而缩减大部分不参与连接的元组,最终形成了计算结果表。通过站点间传送计算结果表来缩减连接关系,半连接的准确性比估算连接结果高,半连接查询优化算法能较准确地做出下一步的连接;新的查询优化算法能有效地得到连接操作的执行计划,从而减少了传输费用。

Comparing Set Reconciliation Methods Based on Bloom Filters and Their Variants

Set reconciliation between two nodes is widely used in network applications. The basic idea is that each member of a node pair has an object set and seeks to deliver its unique objects to the other member. The Standard Bloom Filter （SBF） and its variants, such as the Invertible Bloom Filter （IBF）, are effective approaches to solving the set reconciliation problem. The SBF-based method requires each node to represent its objects using an SBF, which is exchanged with the other node. A receiving node queries the received SBF against its local objects to identify the unique objects. Finally, each node exchanges its unique objects with the other node in the node pair. For the IBF- based method, each node represents its objects using an IBF, which is then exchanged. A receiving node subtracts the received IBF from its local IBF so as to decode the different objects between the two sets. Intuitively, it would seem that the IBF-based method, with only one round of communication, entails less communication overhead than the SBF-based method, which incurs two rounds of communication. Our research results, however, indicate that neither of these two methods has an absolute advantages over the others. In this paper, we aim to provide an in-depth understanding of the two methods, by evaluating and comparing their communication overhead. We find that the best method depends on parameter settings. We demonstrate that the SBF-based method outperforms the IBF-based method in most cases. But when the number of different objects in the two sets is below a certain threshold, the IBF-based method outperforms the SBF-based method.

Hot Data Identification with Multiple Bloom Filters： Block-Level Decision vs I/O Request-Level Decision

Hot data identification is crucial for many applications though few investigations have examined the subject. All existing studies focus almost exclusively on frequency. However, effectively identifying hot data requires equally considering recency and frequency. Moreover, previous studies make hot data decisions at the data block level. Such a fine-grained decision fits particularly well for flash-based storage because its random access achieves performance comparable with its sequential access. However, hard disk drives （HDDs） have a significant performance disparity between sequential and random access. Therefore, unlike flash-based storage, exploiting asymmetric HDD access performance requires making a coarse-grained decision. This paper proposes a novel hot data identification scheme adopting multiple bloom filters to efficiently characterize recency as well as frequency. Consequently, it not only consumes 50% less memory and up to 58% less computational overhead, but also lowers false identification rates up to 65% compared with a state-of-the-art scheme. Moreover, we apply the scheme to a next generation HDD technology, i.e., Shingled Magnetic Recording （SMR）, to verify its effectiveness. For this, we design a new hot data identification based SMR drive with a coarse-grained decision. The experiments demonstrate the importance and benefits of accurate hot data identification, thereby improving the proposed SMR drive performance by up to 42%.

A verifiable essential secret image sharing scheme based on HLRs(VESIS-(t,s,k,n))

In traditional secret image sharing schemes,a secret image is shared among shareholders who have the same position.But if the shareholders have two different positions,essential and non‐essential,it is necessary to use essential secret image sharing schemes.In this article,a verifiable essential secret image sharing scheme based on HLRs is proposed.Shareholder's share consists of two parts.The first part is produced by the shareholders,which prevents the fraud of dealers.The second part is a shadow image that is produced by using HLRs and the first part of share.The verification of the first part of the shares is done for the first time by using multilinear and bilinear maps.Also,for verifying shadow images,Bloom Filters are used for the first time.The proposed scheme is more efficient than similar schemes,and for the first part of the shares,has formal security.

BloomRouter:A Framework for Dissemination of Compressed XML Stream

As our best knowledge, in the Publish/Subscribe application environment, few research work has been done on the dissemination and routing of compressed XML （extended markup language） data. A high-speed compressed XML data routing and dissemination framework BloomRouter is proposed. In BloomRouter, a Bloom Filter based prefilte ring mechanism is used to filter out compressed XML elements that users do not care; after that an interval tree dis seminator forwards target elements to the corresponding end users by matching the incomming compressed XML elements with indexed users＇ query regions. Based on this framework, we can efficiently filter/query the compressed incoming XML data, and then route the query result to the corresponding subseriber.

L-priorities Bloom Filter: A New Member of the Bloom Filter Family

A Bloom filter is a space-efficient data structure used for concisely representing a set as well as membership queries at the expense of introducing false positive. In this paper, we propose the L-priorities Bloom filter （LPBF） as a new member of the Bloom filter （BF） family, it uses a limited multidimensional bit space matrix to replace the bit vector of standard bloom filters in order to support different priorities for the elements of a set. We demonstrate the time and space complexity, especially the false positive rate of LPBF. Furthermore, we also present a detailed practical evaluation of the false positive rate achieved by LPBF. The results show that LPBF performs better than standard BFs with respect to false positive rate.

PERFORMANCE EVALUATION AND COMPARISON OF THREE COUNTING BLOOM FILTER SCHEMES

The Counting Bloom Filter （CBF） is a kind of space-efficient data structure that extends a Bloom filter so as to allow approximate multiplicity queries on a dynamic multi-set. This paper evaluates the performance of multiplicity queries of three simple CBF schemes-the Naive Counting Bloom Filter （NCBF）, the Space-Code Bloom Filter （SCBF） and the d-left Counting Bloom Filter （dlCBF）-using metrics of space complexity and counting error under both uniform and zipfian multiplicity distributions. We compare their counting error under same space complexity, and their space complexity when similar counting errors are achieved respectively. Our results show that dICBF is the best while SCBF is the worst in terms of both space-efficiency and accuracy. Furthermore, the performance gap between dlCBF and the others has a trend of being enlarged with the increment of space occupation or counting accuracy.

基于BLOOM FILTER过滤算法的重复数据删除技术的研究与改进

随着企业数据信息量的不断地增加,海量数据信息的存储和不断备份给企业的存储空间带来了巨大的存储压力。该文深入研究重复数据删除技术,并针对目前重复数据删除技术中存在的数据丢失及性能低等问题以及BLOOM FILTER算法流程和重复数据删除策略的分析和研究,提出了一种重复数据删除技术优化模型。测试分析表明,该优化模型实现了高效和安全的重复数据删除功能,节省了企业内部存储空问的存储成本开销。

The Impact of Check Bits on the Performance of Bloom Filter

Bloom filter(BF)is a space-and-time efficient probabilistic technique that helps answermembership queries.However,BF faces several issues.The problems with traditional BF are generally two.Firstly,a large number of false positives can return wrong content when the data is queried.Secondly,the large size of BF is a bottleneck in the speed of querying and thus uses large memory.In order to solve the above two issues,in this article,we propose the check bits concept.From the implementation perspective,in the check bits approach,before saving the content value in the BF,we obtain the binary representation of the content value.Then,we take some bits of the content value,we call these the check bits.These bits are stored in a separate array such that they point to the same location as the BF.Finally,the content value(data)is stored in the BF based on the hash function values.Before retrieval of data from BF,the reverse process of the steps ensures that even if the same hash functions output has been generated for the content,the check bits make sure that the retrieval does not depend on the hash output alone.This thus helps in the reduction of false positives.In the experimental evaluation,we are able to reduce more than 50%of false positives.In our proposed approach,the false positives can still occur,however,false positives can only occur if the hash functions and check bits generate the same value for a particular content.The chances of such scenarios are less,therefore,we get a reduction of approximately more than 50%false positives in all cases.We believe that the proposed approach adds to the state of the art and opens new directions as such.

Cross-Domain Data Traceability Mechanism Based on Blockchain

With the application and development of blockchain technology,many problems faced by blockchain traceability are gradually exposed.Such as cross-chain information collaboration,data separation and storage,multisystem,multi-security domain collaboration,etc.To solve these problems,it is proposed to construct trust domains based on federated chains.The public chain is used as the authorization chain to build a cross-domain data traceability mechanism applicable to multi-domain collaboration.First,the architecture of the blockchain cross-domain model is designed.Combined with the data access strategy and the decision mechanism,the open and transparent judgment of cross-domain permission and cross-domain identity authentication is realized.And the public chain consensus node election mechanism is realized based on PageRank.Then,according to the characteristics of a nonsingle chain structure in the process of data flow,a data retrievalmechanism based on a Bloom filter is designed,and the cross-domain traceability algorithm is given.Finally,the safety and effectiveness of the traceability mechanism are verified by security evaluation and performance analysis.

BloomDT-An improved privacy-preserving decision tree inference scheme

Outsourcing decision tree models to cloud servers can allow model providers to distribute their models at scale without purchasing dedicated hardware for model hosting.However,model providers may be forced to disclose private model details when hosting their models in the cloud.Due to the time and monetary investments associated with model training,model providers may be reluctant to host their models in the cloud due to these privacy concerns.Furthermore,clients may be reluctant to use these outsourced models because their private queries or their results may be disclosed to the cloud servers.In this paper,we propose BloomDT,a privacy-preserving scheme for decision tree inference,which uses Bloom filters to hide the original decision tree's structure,the threshold values of each node,and the order in which features are tested while maintaining reliable classification results that are secure even if the cloud servers collude.Our scheme's security and performance are verified through rigorous testing and analysis.

基于并行BP神经网络的路由查找算法

结合Bloom-filter算法和并行反向传播神经网络,提出了一种新的基于并行神经网络的路由查找算法(BFBP)。该算法满足路由查找的需求,只需学习路由条目的网络ID,且易于扩展到IPv6地址查询。研究结果表明,相比于己有的神经网络路由查找方法,该算法需要学习的条目数平均减少了520倍,提高了学习效率,为神经网络应用于路由查找创造了有利条件。

Implementation and Validation of the Optimized Deduplication Strategy in Federated Cloud Environment

Cloud computing technology is the culmination of technical advancements in computer networks,hardware and software capabilities that collectively gave rise to computing as a utility.It offers a plethora of utilities to its clients worldwide in a very cost-effective way and this feature is enticing users/companies to migrate their infrastructure to cloud platform.Swayed by its gigantic capacity and easy access clients are uploading replicated data on cloud resulting in an unnecessary crunch of storage in datacenters.Many data compression techniques came to rescue but none could serve the purpose for the capacity as large as a cloud,hence,researches were made to de-duplicate the data and harvest the space from exiting storage capacity which was going in vain due to duplicacy of data.For providing better cloud services through scalable provisioning of resources,interoperability has brought many Cloud Service Providers(CSPs)under one umbrella and termed it as Cloud Federation.Many policies have been devised for private and public cloud deployment models for searching/eradicating replicated copies using hashing techniques.Whereas the exploration for duplicate copies is not restricted to any one type of CSP but to a set of public or private CSPs contributing to the federation.It was found that even in advanced deduplication techniques for federated clouds,due to the different nature of CSPs,a single file is stored at private as well as public group in the same cloud federation which can be handled if an optimized deduplication strategy be rendered for addressing this issue.Therefore,this study has been aimed to further optimize a deduplication strategy for federated cloud environment and suggested a central management agent for the federation.It was perceived that work relevant to this is not existing,hence,in this paper,the concept of federation agent has been implemented and deduplication technique following file level has been used for the accomplishment of this approach.

A Fast and Memory-Efficient Approach to NDN Name Lookup

For name-based routing/switching in NDN, the key challenges are to manage large-scale forwarding Tables, to lookup long names of variable lengths, and to deal with frequent updates. Hashing associated with proper length-detecting is a straightforward yet efficient solution. Binary search strategy can reduce the number of required hash detecting in the worst case. However, to assure the searching path correct in such a schema, either backtrack searching or redundantly storing some prefixes is required, leading to performance or memory issues as a result. In this paper, we make a deep study on the binary search, and propose a novel mechanism to ensure correct searching path without neither additional backtrack costs nor redundant memory consumptions. Along any binary search path, a bloom filter is employed at each branching point to verify whether a said prefix is present, instead of storing that prefix here. By this means, we can gain significantly optimization on memory efficiency, at the cost of bloom checking before each detecting. Our evaluation experiments on both real-world and randomly synthesized data sets demonstrate our superiorities clearly

A Trusted and Privacy-Preserving Carpooling Matching Scheme in Vehicular Networks

With the rapid development of intelligent transportation, carpooling with the help of Vehicular Networks plays an important role in improving transportation efficiency and solving environmental problems. However, attackers usually launch attacks and cause privacy leakage of carpooling users. In addition, the trust issue between unfamiliar vehicles and passengers reduces the efficiency of carpooling. To address these issues, this paper introduced a trusted and privacy-preserving carpooling matching scheme in Vehicular Networks (TPCM). TPCM scheme introduced travel preferences during carpooling matching, according to the passengers’ individual travel preferences needs, which adopted the privacy set intersection technology based on the Bloom filter to match the passengers with the vehicles to achieve the purpose of protecting privacy and meeting the individual needs of passengers simultaneously. TPCM scheme adopted a multi-faceted trust management model, which calculated the trust value of different travel preferences of vehicle based on passengers’ carpooling feedback to evaluate the vehicle’s trustworthiness from multi-faceted when carpooling matching. Moreover, a series of experiments were conducted to verify the effectiveness and robustness of the proposed scheme. The results show that the proposed scheme has high accuracy, lower computational and communication costs when compared with the existing carpooling schemes.

High Speed and Low Power Architecture for Network Intrusion Detection System

The tremendous growth in the field of modern communication and network systems places demands on the security. As the network complexity grows, the need for the automated detection and timely alert is required to detect the abnormal activities in the network. To diagnose the system against the malicious signatures, a high speed Network Intrusion Detection System is required against the attacks. In the network security applications, Bloom Filters are the key building block. The packets from the high speed link can be easily processed by Bloom Filter using state- of-art hardware based systems. As Bloom Filter and its variant Counting Bloom Filter suffer from False Positive Rate, Multi Hash Counting Bloom Filter architecture is proposed. The proposed work, constitute parallel signature detection improves the False Positive Rate, but the throughput and hardware complexity suffer. To resolve this, a Multi-Level Ranking Scheme is introduced which deduces the 13% - 16% of the power and increases the throughput to 23% - 30%. This work is best suited for signature detection in high speed network.

Approximate Discovery of Service Nodes by Duplicate Detection in Flows

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.

Data Location Mechanism in Agent-Based Autonomic Storage Systems

This paper introduces agent-based methodology to build a distributed autonomic storage system infrastructure, and an effectively negotiation mechanism based on agent is applied for data location. We present Availability-based Data Allocation （ADA） algorithm as a data placement strategy to achieve high efficient utilization of storage resources by employing multiple distributed storage resources. We use Bloom filter in each storage device to track the location of data. We present the data lookup strategy that small size of read request is handled directly, and large size of read request is handled by cooperation with storage devices.The performance evaluation shows that the data location mechanism is high available and can work well for heterogeneous autonomic storage systems.