research-article

Free access

A compressive method for maintaining forwarding states in SDN controller

Authors:

Sriram Natarajan,

Ravi ManghirmalaniAuthors Info & Claims

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

Pages 139 - 144

https://doi.org/10.1145/2620728.2620759

Published: 22 August 2014 Publication History

Abstract

Many controller applications require querying existing flow entries in the switches for improving resilience and optimizing resource utilization. These applications can benefit if the controller maintains a copy of the forwarding tables in its memory. However, a naive approach of simply keeping all the tables may encounter scalability challenges. In this work, we identify the redundancy across the flow tables of all switches in the network. We then propose a model-based compression method to efficiently store the network-wide forwarding states. Our evaluation results on a variety of topologies show up to 98% reduction in size.

References

[1]

N. Gude, T. Koponen, J. Pettit, B. Pfaff, M. Casado, N. McKeown, and S. Shenker, "Nox: towards an operating system for networks," SIGCOMM Comput. Commun. Rev., vol. 38, July 2008.

Digital Library

[2]

"Pox." http://www.noxrepo.org/pox.

[3]

"Ryu." http://osrg.github.io/ryu/.

[4]

A. Khurshid, W. Zhou, M. Caesar, and P. B. Godfrey, "Veriflow: verifying network-wide invariants in real time," in Proceedings of the first workshop on Hot topics in software defined networks, HotSDN '12, 2012.

Digital Library

[5]

A. Lazaris, D. Tahara, X. Huang, L. E. Li, A. Voellmy, Y. R. Yang, and M. Yu, "Jive: Performance driven abstraction and optimication for sdn," in Presented as part of the Open Networking Summit 2014 (ONS 2014), (Santa Clara, CA), USENIX, 2014.

[6]

"OpenFlow 1.3." http://www.openflow.org/.

[7]

M. Moshref, M. Yu, A. Sharma, and R. Govindan, "Scalable Rule Management for Data Centers," in Proceedings of NSDI'13), April 2013.

Digital Library

[8]

N. Sarrar, S. Uhlig, A. Feldmann, R. Sherwood, and X Huang, "Leveraging zipf's law for traffic offloading," SIGCOMM Comput. Commun. Rev., vol. 42, January 2012.

Digital Library

[9]

"University of Oregon Route Views Archive Project." www.routeviews.org.

[10]

C.-Y. Hong, S. Kandula, R. Mahajan, M. Zhang, V. Gill, M. Nanduri, and R. Wattenhofer, "Achieving High Utilization with Software-Driven WAN," in Proc. ACM SIGCOMM, August 2013.

Digital Library

[11]

M. Al-Fares, A. Loukissas, and A. Vahdat, "A Scalable, Commodity Data Center Network Architecture," in SIGCOMM, 2008.

Digital Library

[12]

G. Rétvári, J. Tapolcai, A. Korösi, A. Majdán, and Z. Heszberger, "Compressing ip forwarding tables: towards entropy bounds and beyond," in Proceedings of the ACM SIGCOMM 2013 conference on SIGCOMM, SIGCOMM '13, pp. 111--122, 2013.

Digital Library

[13]

E. Karpilovsky, M. Caesar, J. Rexford, A. Shaikh, and J. van der Merwe, "Practical Network-Wide Compression of IP Routing Tables," IEEE Transactions on Network and Service Management (TNSM), vol. 9, December 2012.

[14]

Y. Kanizo, D. Hay, and I. Keslassy, "Palette: Distributing tables in software-defined networks.," in Proc. IEEE INFOCOM, 2013.

[15]

N. Kang, Z. Liu, J. Rexford, and D. Walker, "Optimizing the "one big switch" abstraction in software-defined networks," in Proceedings of the Ninth ACM Conference on Emerging Networking Experiments and Technologies, 2013.

Digital Library

[16]

D. A. Applegate, G. Calinescu, D. S. Johnson, H. Karloff, K. Ligett, and J. Wang, "Compressing rectilinear pictures and minimizing access control lists," in Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007.

Digital Library

[17]

S. Babu, M. N. Garofalakis, and R. Rastogi, "Spartan: A model-based semantic compression system for massive data tables.," in SIGMOD Conference, 2001.

Digital Library

[18]

B. Lantz, B. Heller, and N. McKeown, "A network in a laptop: rapid prototyping for software-defined networks," in Proceedings of the 9th ACM SIGCOMM Workshop on Hot Topics in Networks, 2010.

Digital Library

[19]

I. H. Witten and E. Frank, Data Mining: Practical Machine Learning Tools and Techniques, Second Edition (Morgan Kaufmann Series in Data Management Systems). San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2005.

Digital Library

[20]

R. N. Mysore, A. Pamporis, N. Farrington, N. Huang, P. Miri, S. Radhakrishnan, Subramanya, and A. Vahdat, "PortLand: A Scalable, Fault-Tolerant Layer 2 Data Center Network Fabric," in SIGCOMM 2009.

Digital Library

[21]

"The Internet Topology Zoo." http://www.topology-zoo.org/.

[22]

N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner, "Openflow: enabling innovation in campus networks," SIGCOMM Comput. Commun. Rev., vol. 38, pp. 69--74, March 2008.

Digital Library

[23]

A. Greenberg, G. Hjalmtysson, D. A.Maltz, A. Myers, J. Rexford, G. Xie, H. Yan, J. Zhan, and H. Zhang, "A clean slate 4d approach to network control and management," SIGCOMM Comput. Commun. Rev., vol. 35, October 2005.

Digital Library

[24]

R. Sherwood, G. Gibb, K.-K. Yap, G. Appenzeller, M. Casado, N. McKeown, and G. Parulkar, "Can the production network be the testbed?," in Proceedings of the 9th USENIX conference on Operating systems design and implementation, OSDI'10, 2010.

Digital Library

[25]

T. Koponen, M. Casado, N. Gude, J. Stribling, L. Poutievski, M. Zhu, R. Ramanathan, Y. Iwata, H. Inoue, T. Hama, and S. Shenker, "Onix: a distributed control platform for large-scale production networks," in Proceedings of the 9th USENIX conference on Operating systems design and implementation, OSDI'10, 2010.

Digital Library

[26]

M. Moshref, M. Yu, A. Sharma, and R. Govindan, "vCRIB: Virtual Cloud Rule Information Base," in Proceedings of HotCloud'12, June 2012.

Cited By

Li FChen SJia XGao CWang PWang XCao J(2024)Distributed Program Deployment for Resource-Aware Programmable SwitchesIEEE Transactions on Computers10.1109/TC.2024.335578673:5(1357-1370)Online publication date: May-2024
https://doi.org/10.1109/TC.2024.3355786
Tiwari NBajpai AMaurya SChaurasiya D(2024)Efficient Forwarding Rule Management in Software Defined Network via Subnet-Based Pattern MatchingSN Computer Science10.1007/s42979-024-03172-x5:6Online publication date: 14-Aug-2024
https://doi.org/10.1007/s42979-024-03172-x
Jia XLi FChen SGao CWang PWang X(2023)RED: Distributed Program Deployment for Resource-aware Programmable SwitchesIEEE INFOCOM 2023 - IEEE Conference on Computer Communications10.1109/INFOCOM53939.2023.10228974(1-10)Online publication date: 17-May-2023
https://doi.org/10.1109/INFOCOM53939.2023.10228974
Show More Cited By

Index Terms

A compressive method for maintaining forwarding states in SDN controller
1. Networks
  1. Network services
    1. Network management

Recommendations

DC-CAMP: Dynamic Controller Creation, Allocation and Management Protocol in SDN
Abstract
Software-defined networking (SDN) is a new paradigm that influences all networking aspects. SDN decouples the control and data planes. Decoupling the control and data planes makes possible the management of network equipment in a more comfortable ...
Memory Forensics of the OpenDaylight Software-Defined Networking (SDN) Controller
ARES '23: Proceedings of the 18th International Conference on Availability, Reliability and Security

Software-Defined Networking (SDN) abstracts the underlying networking hardware by keeping the control plane and the data separated. SDNs use the control plane to direct network traffic, while OpenFlow switches and routers play a passive role in the ...
SDN traceroute: tracing SDN forwarding without changing network behavior
HotSDN '14: Proceedings of the third workshop on Hot topics in software defined networking

Software-defined networking provides flexibility in designing networks by allowing distributed network state to be managed by logically centralized control programs. However, this flexibility brings added complexity, which requires new debugging tools ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

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

Copyright © 2014 ACM.

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]

Sponsors

SIGCOMM: ACM Special Interest Group on Data Communication

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%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
1,048
Total Downloads

Downloads (Last 12 months)58
Downloads (Last 6 weeks)5

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li FChen SJia XGao CWang PWang XCao J(2024)Distributed Program Deployment for Resource-Aware Programmable SwitchesIEEE Transactions on Computers10.1109/TC.2024.335578673:5(1357-1370)Online publication date: May-2024
https://doi.org/10.1109/TC.2024.3355786
Tiwari NBajpai AMaurya SChaurasiya D(2024)Efficient Forwarding Rule Management in Software Defined Network via Subnet-Based Pattern MatchingSN Computer Science10.1007/s42979-024-03172-x5:6Online publication date: 14-Aug-2024
https://doi.org/10.1007/s42979-024-03172-x
Jia XLi FChen SGao CWang PWang X(2023)RED: Distributed Program Deployment for Resource-aware Programmable SwitchesIEEE INFOCOM 2023 - IEEE Conference on Computer Communications10.1109/INFOCOM53939.2023.10228974(1-10)Online publication date: 17-May-2023
https://doi.org/10.1109/INFOCOM53939.2023.10228974
Albuquerque Raymundo Da Silva ICalinescu GDe Graaf N(2020)Faster compression of patterns to Rectangle Rule ListsTheoretical Computer Science10.1016/j.tcs.2020.03.014Online publication date: Apr-2020
https://doi.org/10.1016/j.tcs.2020.03.014
Chuang CYu YPang A(2018)Flow-Aware Routing and Forwarding for SDN Scalability in Wireless Data CentersIEEE Transactions on Network and Service Management10.1109/TNSM.2018.286516615:4(1676-1691)Online publication date: Dec-2018
https://doi.org/10.1109/TNSM.2018.2865166
Sheu JLin WChang G(2018)Efficient TCAM Rules Distribution Algorithms in Software-Defined NetworkingIEEE Transactions on Network and Service Management10.1109/TNSM.2018.282502615:2(854-865)Online publication date: Jun-2018
https://doi.org/10.1109/TNSM.2018.2825026
Da Silva ICalinescu GDe Graaf N(2018)Faster Compression of Patterns to Rectangle Rule ListsAlgorithmic Aspects in Information and Management10.1007/978-3-030-04618-7_16(190-208)Online publication date: 3-Dec-2018
https://dl.acm.org/doi/10.1007/978-3-030-04618-7_16
Song SPark HChoi BChoi TZhu H(2017)Control Path Management Framework for Enhancing Software-Defined Network (SDN) ReliabilityIEEE Transactions on Network and Service Management10.1109/TNSM.2017.266908214:2(302-316)Online publication date: Jun-2017
https://doi.org/10.1109/TNSM.2017.2669082
Kreutz DRamos FEsteves Verissimo PEsteve Rothenberg CAzodolmolky SUhlig S(2015)Software-Defined Networking: A Comprehensive SurveyProceedings of the IEEE10.1109/JPROC.2014.2371999103:1(14-76)Online publication date: Jan-2015
https://doi.org/10.1109/JPROC.2014.2371999
da Silva ASmith PMauthe ASchaeffer-Filho A(2015)Resilience support in software-defined networkingComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2015.09.01292:P1(189-207)Online publication date: 9-Dec-2015
https://dl.acm.org/doi/10.1016/j.comnet.2015.09.012

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten