research-article

Free access

CAB: a reactive wildcard rule caching system for software-defined networks

Authors:

Bo Yan,

Yang Xu,

Hongya Xing,

Kang Xi,

H. Jonathan ChaoAuthors Info & Claims

HotSDN '14: Proceedings of the third workshop on Hot topics in software defined networking

Pages 163 - 168

https://doi.org/10.1145/2620728.2620732

Published: 22 August 2014 Publication History

PDF eReader

Abstract

Software-Defined Networking (SDN) enables flexible flow control by caching policy rules at OpenFlow switches. Compared with exact-match rule caching, wildcard rule caching can better preserve the flow table space at switches. However, one of the challenges for wildcard rule caching is the dependency between rules, which is generated by caching wildcard rules overlapped in field space with different priorities. Failure to handle the rule dependency may lead to wrong matching decisions for newly arrived flows, or may introduce high storage overhead in flow table memory.

In this paper, we propose a wildcard rule caching system for SDN named CAching in Buckets (CAB). The main idea of CAB is to partition the field space into logical structures called buckets, and cache buckets along with all the associated rules. Through CAB, we resolve the rule dependency problem with small storage overhead. Compared to previous schemes, CAB reduces the flow setup requests by an order of magnitude, saves control bandwidth by a half, and significantly reduce average flow setup time.

References

[1]

Openflow switch specification 1.4.0. https://www.opennetworking.org/, Oct. 2013.

Google Scholar

[2]

M. Casado, M. J. Freedman, J. Pettit, J. Luo, N. Gude, N. McKeown, and S. Shenker. Rethinking enterprise network control. IEEE/ACM Transactions on Networking (TON), 17(4):1270--1283, 2009.

Digital Library

Google Scholar

[3]

A. R. Curtis, J. C. Mogul, J. Tourrilhes, P. Yalagandula, P. Sharma, and S. Banerjee. Devoflow: Scaling flow management for high-performance networks. In ACM SIGCOMM Computer Communication Review, volume 41, pages 254--265. ACM, 2011.

Digital Library

Google Scholar

[4]

Q. Dong, S. Banerjee, J. Wang, and D. Agrawal. Wire speed packet classification without tcams: a few more registers (and a bit of logic) are enough. In ACM SIGMETRICS Performance Evaluation Review, volume 35, pages 253--264. ACM, 2007.

Digital Library

Google Scholar

[5]

N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner. Openflow: enabling innovation in campus networks. ACM SIGCOMM Computer Communication Review, 38(2):69--74, 2008.

Digital Library

Google Scholar

[6]

X. Meng, V. Pappas, and L. Zhang. Improving the scalability of data center networks with traffic-aware virtual machine placement. In INFOCOM, 2010 Proceedings IEEE, pages 1--9. IEEE, 2010.

Digital Library

Google Scholar

[7]

M. Moshref, M. Yu, A. Sharma, and R. Govindan. Scalable rule management for data centers. In Proceedings of the 10th USENIX conference on Networked Systems Design and Implementation, pages 157--170. USENIX Association, 2013.

Digital Library

Google Scholar

[8]

S. Singh, F. Baboescu, G. Varghese, and J. Wang. Packet classification using multidimensional cutting. In Proceedings of the ACM SIGCOMM 2003 conference on Applications, technologies, architectures, and protocols for computer communications, pages 213--224. ACM, 2003.

Digital Library

Google Scholar

[9]

D. E. Taylor and J. S. Turner. Classbench: a packet classification benchmark. In INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, volume 3, pages 2068--2079. IEEE, 2005.

Crossref

Google Scholar

[10]

A. Tootoonchian, S. Gorbunov, Y. Ganjali, M. Casado, and R. Sherwood. On controller performance in software-defined networks. In USENIX Workshop on Hot Topics in Management of Internet, Cloud, and Enterprise Networks and Services (Hot-ICE), 2012.

Digital Library

Google Scholar

[11]

M. Yu, J. Rexford, M. J. Freedman, and J. Wang. Scalable flow-based networking with difane. ACM SIGCOMM Computer Communication Review, 41(4):351--362, 2011.

Digital Library

Google Scholar

Cited By

View all

Doron-Arad IKortsarz GNaor JSchieber BShachnai H(2025)Approximations and Hardness of Covering and Packing Partially Ordered ItemsGraph-Theoretic Concepts in Computer Science10.1007/978-3-031-75409-8_12(166-180)Online publication date: 22-Jan-2025
https://doi.org/10.1007/978-3-031-75409-8_12
Li XSun HHuang Y(2024)Efficient Flow Table Caching Architecture and Replacement Policy for SDN SwitchesJournal of Network and Systems Management10.1007/s10922-024-09824-w32:3Online publication date: 18-Jun-2024
https://doi.org/10.1007/s10922-024-09824-w
Wan YSong HPan TLiu BJia YQian L(2023)Multi-Stage Flow Table Caching: From Theory to Algorithm2023 IEEE Symposium on Computers and Communications (ISCC)10.1109/ISCC58397.2023.10217871(252-258)Online publication date: 9-Jul-2023
https://doi.org/10.1109/ISCC58397.2023.10217871
Show More Cited By

Index Terms

CAB: a reactive wildcard rule caching system for software-defined networks
1. Networks
  1. Network architectures

Recommendations

Applying LSTM to Enable Cache Prefetching to Optimize Flow Table Update Efficiency in SDN Switches
ICIT '19: Proceedings of the 2019 7th International Conference on Information Technology: IoT and Smart City

Due to the fast growth of the Internet and social network, a massive amount of data has been generated and move to the cloud. With the ability to separate the control and data plane, SDN (Software Defined Network) provide an emerging solution for data ...
CAB: Cache Aware Bi-tier Task-Stealing in Multi-socket Multi-core Architecture
ICPP '11: Proceedings of the 2011 International Conference on Parallel Processing

Modern multi-core computers often adopt a multi-socket multi-core architecture with shared caches in each socket. However, traditional task-stealing schedulers tend to pollute the shared cache and incur more cache misses due to their random stealing. To ...
Many-Field Packet Classification for Software-Defined Networking Switches
ANCS '16: Proceedings of the 2016 Symposium on Architectures for Networking and Communications Systems

Packet classification is a core problem for OpenFlow-based software-defined networking switches, which required 38 packet header fields per flow to be examined against thousands of rules in a ruleset. With the trend of continue growing number of fields ...

Comments

Information & Contributors

Information

Published In

HotSDN '14: Proceedings of the third workshop on Hot topics in software defined networking

August 2014

252 pages

ISBN:9781450329897

DOI:10.1145/2620728

Program Chairs:
Aditya Akella
University of Wisconsin-Madison, USA
,
Albert Greenberg
Microsoft, USA

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 August 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGCOMM'14

Sponsor:

SIGCOMM

SIGCOMM'14: ACM SIGCOMM 2014 Conference

August 22, 2014

Illinois, Chicago, USA

Acceptance Rates

HotSDN '14 Paper Acceptance Rate 50 of 114 submissions, 44%;

Overall Acceptance Rate 88 of 198 submissions, 44%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

46
Total Citations
View Citations
1,269
Total Downloads

Downloads (Last 12 months)89
Downloads (Last 6 weeks)7

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Doron-Arad IKortsarz GNaor JSchieber BShachnai H(2025)Approximations and Hardness of Covering and Packing Partially Ordered ItemsGraph-Theoretic Concepts in Computer Science10.1007/978-3-031-75409-8_12(166-180)Online publication date: 22-Jan-2025
https://doi.org/10.1007/978-3-031-75409-8_12
Li XSun HHuang Y(2024)Efficient Flow Table Caching Architecture and Replacement Policy for SDN SwitchesJournal of Network and Systems Management10.1007/s10922-024-09824-w32:3Online publication date: 18-Jun-2024
https://doi.org/10.1007/s10922-024-09824-w
Wan YSong HPan TLiu BJia YQian L(2023)Multi-Stage Flow Table Caching: From Theory to Algorithm2023 IEEE Symposium on Computers and Communications (ISCC)10.1109/ISCC58397.2023.10217871(252-258)Online publication date: 9-Jul-2023
https://doi.org/10.1109/ISCC58397.2023.10217871
Luan ZLi QWang YJiang Y(2023)H-Cache: Traffic-Aware Hybrid Rule-Caching in Software-Defined Networks2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS54959.2023.00017(69-78)Online publication date: May-2023
https://doi.org/10.1109/IPDPS54959.2023.00017
Luan ZLi QZhang ZJiang YChen MWang YLi K(2023)AWEsome-Cache: Dependency-Free Rule-Caching for Arbitrary Wildcard Patterns in TCAM2023 IEEE 31st International Conference on Network Protocols (ICNP)10.1109/ICNP59255.2023.10355586(1-12)Online publication date: 10-Oct-2023
https://doi.org/10.1109/ICNP59255.2023.10355586
Hussain MShah NAmin RAlshamrani SAlotaibi ARaza S(2022)Software-Defined Networking: Categories, Analysis, and Future DirectionsSensors10.3390/s2215555122:15(5551)Online publication date: 25-Jul-2022
https://doi.org/10.3390/s22155551
Luo CChen CMei HYao RWan YLi WLiu SLiu BXu Y(2022)BubbleTCAM: Bubble Reservation in SDN Switches for Fast TCAM Update2022 IEEE/ACM 30th International Symposium on Quality of Service (IWQoS)10.1109/IWQoS54832.2022.9812904(1-10)Online publication date: 10-Jun-2022
https://doi.org/10.1109/IWQoS54832.2022.9812904
Ali FAmin RMajeed MIqbal M(2022)Dynamic ACL Policy Implementation in Software Defined Networks2022 International Conference on IT and Industrial Technologies (ICIT)10.1109/ICIT56493.2022.9989241(01-07)Online publication date: 3-Oct-2022
https://doi.org/10.1109/ICIT56493.2022.9989241
Wan YSong HXu YWang YPan TZhang CWang YLiu B(2021)T-Cache: Efficient Policy-Based Forwarding Using Small TCAMIEEE/ACM Transactions on Networking10.1109/TNET.2021.309832029:6(2693-2708)Online publication date: Dec-2021
https://doi.org/10.1109/TNET.2021.3098320
Wan YSong HXu YZhang CWang YLiu B(2021)Adaptive Batch Update in TCAM: How Collective Optimization Beats Individual OnesIEEE INFOCOM 2021 - IEEE Conference on Computer Communications10.1109/INFOCOM42981.2021.9488758(1-10)Online publication date: 10-May-2021
https://doi.org/10.1109/INFOCOM42981.2021.9488758
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Applying LSTM to Enable Cache Prefetching to Optimize Flow Table Update Efficiency in SDN Switches

CAB: Cache Aware Bi-tier Task-Stealing in Multi-socket Multi-core Architecture

Many-Field Packet Classification for Software-Defined Networking Switches