Event matching is a key component in a large-scale content-based publish/subscribe system. The performance of most existing algorithms is easily affected by the subscription matching probability. In this paper, we propose a new data structure, named AWAW B+-Tree, which is based on the width of the predicates, to efficiently index the subscriptions. The most notable feature ofAW B+-Treeis its ability to combine the advantages of different matching methods, thus achieving high and robust performance in dynamic environments. First, we implement both a forward matching method (AFM) and a backward matching method (ABM) based onAW B+-Tree. Then, we introduce a hybrid matching method (AHM) that combines AFM and ABM. Moreover, we extendAW B+-Treein three aspects: approximate matching, string type matching, and fine-grained parallelization. We conducted extensive experiments to evaluate the performance of the proposed matching algorithms on synthetic and real-world datasets. The experiment results reveal that AHM achieves a reduction in matching time by up to 53.8% compared to the state-of-the-art method. Additionally, AHM exhibits improved performance robustness, with up to a 76.9% reduction in terms of the standard deviation of matching time. Particularly in dynamic scenarios, AHM is at least 2.3 times faster and 41.3% more stable than its counterparts. Furthermore, by implementing parallelization, the matching speed of 8 threads can be accelerated by 4.16 times compared to the single-thread matching speed.

Content-based publish/subscribe systems have the capability to achieve fine-grained data distribution, rapidly forwarding data from publishers to subscribers with specific requirements. The event matching algorithm is a fundamental component, quickly searching for subscriptions that match an event based on constraints defined by subscribers. As data scales continue to expand, there is a heightened demands for more efficient, robust, and versatile event matching algorithms. In this paper, we propose a novel data structure called the Dual-ended Interval Tree (DI-Tree). Firstly, given the splitting point, this data structure classifies intervals into three categories based on the joint distribution of their left and right endpoints in the attribute value domain. Furthermore, the DI-Tree utilizes blue and green nodes to store these three categories of intervals, resulting in enhanced indexing efficiency. Moreover, by utilizing the DITree to efficiently search matching and unmatching intervals, we develop innovative forward and backward event matching algorithms. Additionally, to enhance matching efficacy and reduce memory usage, we introduce key optimization techniques, focusing on improving node balance and bitset optimization. We conduct extensive experiments to evaluate the performance of DITree. When compared with five state-of-the-art event matching algorithms, the DI-Tree demonstrates an average reduction of up to 76.8 % in terms of matching time. This significant improvement highlights the effectiveness of our proposed strategies and the potential of DI-Tree in optimizing event matching performance.

For software-defined networking (SDN), multi-field packet classification plays a key role in the processing of flows, mainly involving fast packet classification and dynamic rule updates. Due to the increasing complexity and size of rulesets, it is becoming more difficult to design a packet classification algorithm which achieves fast lookup and update. In this paper, we propose a novel structure, PT-Tree, for packet classification with high overall performance. PT-Tree cascades the prefixes of multiple discriminatory bytes to achieve efficient partitioning of the ruleset, thereby reducing the search space and ensuring the performance of both lookup and update. Meanwhile, a multi-granularity priority-aware pruning mechanism (MPPM) based on PT-Tree filters out most of the candidate subsets, which further improves the lookup speed. In addition, we propose an auxiliary tree-based optimization method (ATOM) to cope with severely overlapping rules in the search space. Therefore, PT-Tree can better handle the case where the rules in certain fields are skewed. We conduct comprehensive experiments to evaluate the performance of PT-Tree. The results show that compared with the state-of-the-art, the lookup time of PT-Tree is reduced by at least 49.95% on average. Moreover, PT-Tree is also at least 7.13x and 33x faster than the baselines in terms of the update and construction speed on average, respectively. Meanwhile, the performance stability of PT-Tree on multiple rulesets improves by up to 13.68 times.

Packet classification, as a crucial function of networks, has been extensively investigated. In recent years, the rapid advancement of software-defined networking (SDN) has introduced new demands for packet classification, particularly in supporting dynamic rule updates and fast lookup. This paper presents a novel structure called DBTable for efficient packet classification to achieve high overall performance. DBTable integrates the strengths of conventional packet classification methods and neural network concepts. Within DBTable, a straightforward indexing scheme is proposed to eliminate rule replication, thereby ensuring high update performance. Additionally, we propose an iterative method for generating a discriminative bitset (DBS) to evenly partition rules. By utilizing the DBS, rules can be efficiently mapped in a hash table, thus achieving exceptional lookup performance. Moreover, DBTable incorporates a hybrid structure to further optimize the worst-case lookup performance, primarily caused by data skewness. The experiment results on 12 256k rulesets show that, compared to seven state-of-the-art schemes, DBTable achieves an overall lookup speed improvement ranging from 1.53x to 7.29x, while maintaining the fastest update speed.

Content-based publish/subscribe systems are widely used in many fields.Event matching is the core component to achieve fine-grained content-based data distribution.Many efficient algorithms have been proposed to improve event matching performance.However, in large-scale content-based publish/subscribe systems, event matching is still the performance bottleneck of the entire system due to the need to perform a lot of operations, such as additions, comparisons and bitmarkings.In this paper, we explore to convert various nonlogical operations into efficient logical ones, and propose a bitsetbased optimization paradigm (BOP) for matching algorithms.On the one hand, BOP can eliminate expensive operations in the matching process, greatly improving matching performance.On the other hand, BOP can stabilize the performance of matching algorithms, ensuring the quality of service of data distribution.We apply BOP to optimize two existing matching algorithms, namely TAMA and REIN.The experimental results show that BOP shortens the matching time of TAMA and REIN by more than 60%.In addition, the performance of optimized versions is more stable than the original matching algorithms.

The matching algorithm is a critical component of the content-based publish/subscribe system, whose performance has direct effects on the QoS of the whole system. Aiming to improve and stabilize the matching performance, we propose a lightweight parallelization method called PhSIH on the basis of three existing algorithms. PhSIH fulfills Parallelization by horizontally Segmenting the Indexing Hierarchy of data structures to support multiple threads performing matching tasks in parallel on a common data structure. PhSIH can adaptively adjust the degree of parallelism according to the changing workloads in order to meet the performance requirement. The main work of PhSIH concerns dynamically adjusting the degree of parallelism and computing a task allocation solution for parallel threads. PhSIH is implemented in Apache Kafka to augment it as a content-based publish/subscribe system, which makes Kafka suitable for real-time fine-grained event dissemination scenarios, such as stock ticks. To evaluate the parallelization effect and adaptability of PhSIH, a series of experiments are conducted based on synthetic and real-world data. The experiment results demonstrate that PhSIH achieves a good parallelization effect on the three existing algorithms and possesses a desirable adaptability that stabilizes the performance of the matching algorithms.