Browsing by Author "Thanavel, Mahadevan"

Now showing 1 - 2 of 2

Dynamic Reordering Bloom Filter
(2017-01-01)
Chang, Da-Chung
;
Chen, Chien
;
Thanavel, Mahadevan
;
資訊工程學系
;
資訊技術服務中心
In order to check a membership in multiple sets of bloom filter in a dynamic bloom filter, a sequential search is usually used. Since the distribution of queried data is unpredictable because the distribution has a feature of temporal locality. Therefore more search cost is incurred if queried data is stored in the peer which is corresponded to the Bloom Filter has lower query priority. In this paper, we introduce Dynamic Reordering Bloom Filter that can save the cost of searching Bloom Filter by dynamically reorder the searching sequence of multiple bloom filters in a dynamic bloom filter with One Memory Access Bloom Filter (OMABF) and checked in the order saved in Query Index (QI). The performance of the system is evaluated by Markov Chain. Simulation results show that our scheme on average has 43% better in searching performance comparing with the sequential methods, which is verified via three different trace log files.
Fast Packet Classification on OpenFlow Switches Using Multiple R*-Tree Based Bitmap Intersection
(2018-01-01)
Huang, Ding-Fong
;
Chen, Chien
;
Thanavel, Mahadevan
;
資訊工程學系
;
電機工程學系
In order to accomplish a stringent speed requirement for processing internet services such as Access Control List (ACL), Quality of Service (QoS), firewalls, etc., software based OpenFlow switches must have a fast packet classification capability. Even for hardware based OpenFlow switches, a limited size of Ternary Content Addressable Memory (TCAM) in the switch could be only enough for a forwarding table. Therefore, ACL, firewall tables, etc. need to be implemented by using the memory of the switch CPU. However, it has become a great challenge to build extremely effectively for next-generation software based packet classification that supports higher throughput and larger flow entries in OpenFlow switch. This paper first exploits a fast packet classification algorithm that forms a R*-Tree based Bitmap Intersection and secondly discusses an enhanced R*-Tree based Bitmap Intersection by using Bloom Filter and Multiple R*-Tree. The evaluation results show that the performance of the algorithm in OpenFlow switches is 4.42 times of Bitmap Intersection and 5.16 times of R*-Tree algorithm and consumes only 300 KB of memory space, which is much less than that of other methods. Finally, the use of multiple R*-Trees has further improved memory usage by about 30%.