Towards Capacity-Adjustable and Scalable Quotient Filter Design for Packet Classification in Software-Defined Networks
Software defined networking (SDN), which can provide a dynamic and configurable network architecture for resource allocation, have been widely employed for efficient massive data traffic management. To accelerate the packet classification process in SDN, the hash-based filters which can support fast...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2022-01-01
|
| Series: | IEEE Open Journal of the Computer Society |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9939040/ |
| _version_ | 1811320637588766720 |
|---|---|
| author | Minghao Xie Quan Chen Tao Wang Feng Wang Yongchao Tao Lianglun Cheng |
| author_facet | Minghao Xie Quan Chen Tao Wang Feng Wang Yongchao Tao Lianglun Cheng |
| author_sort | Minghao Xie |
| collection | DOAJ |
| description | Software defined networking (SDN), which can provide a dynamic and configurable network architecture for resource allocation, have been widely employed for efficient massive data traffic management. To accelerate the packet classification process in SDN, the hash-based filters which can support fast approximate membership query have been widely employed. However, the existing Quotient Filters are limited to fixed size and the number of elements has to be provided in advance. Thus, in this paper, we investigate the first capacity adjustable and scalable quotient filter for dynamic packet classification in SDN. Firstly, a novel Index Independent Quotient Filter (IIQF) is designed, which can adjust its capacity in a more precise level to support dynamic set representation. The algorithms for the operations of insertion, querying, deletion and capacity adjustment of IIQF are also given. Secondly, on the basis of IIQF, a Scalable Index Independent Quotient Filter (SIIQF) is designed to ensure the consistency of the designed quotient filter when adjusting its size. The theoretical performance of the proposed SIIQF, including the error rate, probability of collisions, and the time and space complexity are all analyzed. An instance of employing SIIQF for packet classification with tuple space searching algorithm is also introduced. Finally, the extensive simulations demonstrate the performance gains achieved by the proposed SIIQF compared with the baseline methods. |
| first_indexed | 2024-04-13T13:02:58Z |
| format | Article |
| id | doaj.art-84123e65e6094f38a31c304bd31f4dfe |
| institution | Directory Open Access Journal |
| issn | 2644-1268 |
| language | English |
| last_indexed | 2024-04-13T13:02:58Z |
| publishDate | 2022-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Open Journal of the Computer Society |
| spelling | doaj.art-84123e65e6094f38a31c304bd31f4dfe2022-12-22T02:45:52ZengIEEEIEEE Open Journal of the Computer Society2644-12682022-01-01324625910.1109/OJCS.2022.32196319939040Towards Capacity-Adjustable and Scalable Quotient Filter Design for Packet Classification in Software-Defined NetworksMinghao Xie0https://orcid.org/0000-0003-2856-8741Quan Chen1https://orcid.org/0000-0003-2034-0371Tao Wang2https://orcid.org/0000-0002-6907-4142Feng Wang3https://orcid.org/0000-0002-3492-3714Yongchao Tao4Lianglun Cheng5School of Computer Science and Technology, Guangdong University of Technology, Guangzhou, ChinaSchool of Computer Science and Technology, Guangdong University of Technology, Guangzhou, ChinaSchool of Computer Science and Technology, Guangdong University of Technology, Guangzhou, ChinaSchool of Information Engineering, Guangdong University of Technology, Guangzhou, ChinaShenzhen Academy of Aerospace Technology, Shenzhen, ChinaSchool of Computer Science and Technology, Guangdong University of Technology, Guangzhou, ChinaSoftware defined networking (SDN), which can provide a dynamic and configurable network architecture for resource allocation, have been widely employed for efficient massive data traffic management. To accelerate the packet classification process in SDN, the hash-based filters which can support fast approximate membership query have been widely employed. However, the existing Quotient Filters are limited to fixed size and the number of elements has to be provided in advance. Thus, in this paper, we investigate the first capacity adjustable and scalable quotient filter for dynamic packet classification in SDN. Firstly, a novel Index Independent Quotient Filter (IIQF) is designed, which can adjust its capacity in a more precise level to support dynamic set representation. The algorithms for the operations of insertion, querying, deletion and capacity adjustment of IIQF are also given. Secondly, on the basis of IIQF, a Scalable Index Independent Quotient Filter (SIIQF) is designed to ensure the consistency of the designed quotient filter when adjusting its size. The theoretical performance of the proposed SIIQF, including the error rate, probability of collisions, and the time and space complexity are all analyzed. An instance of employing SIIQF for packet classification with tuple space searching algorithm is also introduced. Finally, the extensive simulations demonstrate the performance gains achieved by the proposed SIIQF compared with the baseline methods.https://ieeexplore.ieee.org/document/9939040/Capacity adjustable and scalable hashingdynamic set representationquotient filtersoftware defined network |
| spellingShingle | Minghao Xie Quan Chen Tao Wang Feng Wang Yongchao Tao Lianglun Cheng Towards Capacity-Adjustable and Scalable Quotient Filter Design for Packet Classification in Software-Defined Networks IEEE Open Journal of the Computer Society Capacity adjustable and scalable hashing dynamic set representation quotient filter software defined network |
| title | Towards Capacity-Adjustable and Scalable Quotient Filter Design for Packet Classification in Software-Defined Networks |
| title_full | Towards Capacity-Adjustable and Scalable Quotient Filter Design for Packet Classification in Software-Defined Networks |
| title_fullStr | Towards Capacity-Adjustable and Scalable Quotient Filter Design for Packet Classification in Software-Defined Networks |
| title_full_unstemmed | Towards Capacity-Adjustable and Scalable Quotient Filter Design for Packet Classification in Software-Defined Networks |
| title_short | Towards Capacity-Adjustable and Scalable Quotient Filter Design for Packet Classification in Software-Defined Networks |
| title_sort | towards capacity adjustable and scalable quotient filter design for packet classification in software defined networks |
| topic | Capacity adjustable and scalable hashing dynamic set representation quotient filter software defined network |
| url | https://ieeexplore.ieee.org/document/9939040/ |
| work_keys_str_mv | AT minghaoxie towardscapacityadjustableandscalablequotientfilterdesignforpacketclassificationinsoftwaredefinednetworks AT quanchen towardscapacityadjustableandscalablequotientfilterdesignforpacketclassificationinsoftwaredefinednetworks AT taowang towardscapacityadjustableandscalablequotientfilterdesignforpacketclassificationinsoftwaredefinednetworks AT fengwang towardscapacityadjustableandscalablequotientfilterdesignforpacketclassificationinsoftwaredefinednetworks AT yongchaotao towardscapacityadjustableandscalablequotientfilterdesignforpacketclassificationinsoftwaredefinednetworks AT liangluncheng towardscapacityadjustableandscalablequotientfilterdesignforpacketclassificationinsoftwaredefinednetworks |