research-article

Free access

Flow caching for high entropy packet fields

Authors:

Jarno RajahalmeAuthors Info & Claims

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

Pages 151 - 156

https://doi.org/10.1145/2620728.2620755

Published: 22 August 2014 Publication History

PDF eReader

Abstract

Packet classification on general purpose CPUs remains expensive regardless of advances in classification algorithms. Unless the packet forwarding pipeline is both simple and static in function, fine-tuning the system for optimal forwarding is a time-consuming and brittle process. Network virtualization and network function virtualization value general purpose CPUs exactly for their flexibility: in such systems, a single x86 forwarding element does not implement a single, static classification step but a sequence of dynamically reconfigurable and potentially complex forwarding operations. This leaves a software developer looking for maximal packet forwarding throughput with few options besides flow caching. In this paper, we consider the problem of flow caching and more specifically, how to cache forwarding decisions that depend on packet fields with high entropy (and therefore, change often); to this end, we arrive at algorithms that allow us to efficiently compute near optimal flow cache entries spanning several transport connections, even if forwarding decisions depend on transport protocol headers.

References

[1]

M. Casado, T. Koponen, D. Moon, and S. Shenker. Rethinking Packet Forwarding Hardware. In Proc. of HotNets, October 2008.

Google Scholar

[2]

P. Kazemian, G. Varghese, and N. McKeown. Header Space Analysis: Static Checking for Networks. In NSDI, April 2012.

Digital Library

Google Scholar

[3]

C. Kim, M. Caesar, A. Gerber, and J. Rexford. Revisiting Route Caching: The World Should Be Flat. In Proc. of PAM, April 2009.

Digital Library

Google Scholar

[4]

P. Newman, G. Minshall, and T. L. Lyon. IP Switching - ATM under IP. IEEE/ACM Transactions on Networking, 6(2):117--129, 1998.

Digital Library

Google Scholar

[5]

B. Pfaff, J. Pettit, T. Koponen, K. Amidon, M. Casado, and S. Shenker. Extending Networking into the Virtualization Layer. In Proc. of HotNets, October 2009.

Google Scholar

[6]

L. Rizzo. Netmap: a Novel Framework for Fast Packet I/O. In Proc. of USENIX ATC, June 2012.

Digital Library

Google Scholar

[7]

S. Singh, F. Baboescu, G. Varghese, and J. Wang. Packet Classification Using Multidimensional Cutting. In Proc. of SIGCOMM, 2003.

Digital Library

Google Scholar

[8]

V. Srinivasan, S. Suri, and G. Varghese. Packet Classification using Tuple Space Search. In Proc. of SIGCOMM, 1999.

Digital Library

Google Scholar

[9]

B. Vamanan, G. Voskuilen, and T. N. Vijaykumar. EffiCuts: Optimizing Packet Classification for Memory and Throughput. In Proc. of SIGCOMM, August 2010.

Digital Library

Google Scholar

[10]

M. Waldvogel, G. Varghese, J. S. Turner, and B. Plattner. Scalable High Speed IP Routing Lookups. In Proc. of SIGCOMM, 1997.

Digital Library

Google Scholar

[11]

D. Zhou, B. Fan, H. Lim, M. Kaminsky, and D. G. Andersen. Scalable, High Performance Ethernet Forwarding with CuckooSwitch. In Proc. of CoNEXT, December 2013.

Digital Library

Google Scholar

Cited By

View all

McHale LGratz PSprintson A(2024)Flow Correlator: A Flow Table Cache Management Strategy2024 33rd International Conference on Computer Communications and Networks (ICCCN)10.1109/ICCCN61486.2024.10637657(1-9)Online publication date: 29-Jul-2024
https://doi.org/10.1109/ICCCN61486.2024.10637657
Ling ZChen XSong L(2023)A Composite Pipeline for Forwarding Low-Latency Traffic in SDN Programmable Data PlanesElectronics10.3390/electronics1202046112:2(461)Online publication date: 16-Jan-2023
https://doi.org/10.3390/electronics12020461
Tang XZeng XSong L(2023)Accelerating Protocol Oblivious Forwarding Programmable Data Plane With Flow CacheIEEE Transactions on Network and Service Management10.1109/TNSM.2022.320722720:1(578-594)Online publication date: Mar-2023
https://doi.org/10.1109/TNSM.2022.3207227
Show More Cited By

Index Terms

Flow caching for high entropy packet fields
1. Networks
  1. Network protocols
  2. Network types

Recommendations

Flow caching for high entropy packet fields
SIGCOMM'14

Packet classification on general purpose CPUs remains expensive regardless of advances in classification algorithms. Unless the packet forwarding pipeline is both simple and static in function, fine-tuning the system for optimal forwarding is a time-...
A flow caching mechanism for fast packet forwarding

Next generation access routers and edge devices need to provide functionalities, for layer-4 packet forwarding and firewall/security checks. Consequently, a challenging issue concerns how to achieve fast packet filtering and forwarding at low cost. This ...
Object-Oriented Packet Caching for ICN
ACM-ICN '15: Proceedings of the 2nd ACM Conference on Information-Centric Networking

One of the most discussed features offered by Information-centric Networking (ICN) architectures is the ability to support packet-level caching at every node in the network. By individually naming each packet, ICN allows routers to turn their queueing ...

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

ACM SIGCOMM Computer Communication Review Volume 44, Issue 4
SIGCOMM'14
October 2014
672 pages
ISSN:0146-4833
DOI:10.1145/2740070
Editors:
Konstantina Papagiannaki
Telefonica Research, Barcelona, Spain
,
Katerina Argyraki
EPFL, Switzerland
,
Hitesh Ballani
Microsoft Research Cambridge, UK
,
Fabián Bustamante
Northwestern University, USA
,
Joseph Camp
SMU, USA
,
Augustin Chaintreau
Columbia University, USA
,
Phillipa Gill
Stony Brook University, USA
,
Marco Mellia
Politecnico di Torino, Italy
,
Bhaskaran Raman
IIT Bombay, India
,
Joel Sommers
Colgate University, USA
,
Aline Carneiro Viana
INRIA, France
Issue’s Table of Contents

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

28
Total Citations
View Citations
1,373
Total Downloads

Downloads (Last 12 months)99
Downloads (Last 6 weeks)11

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

McHale LGratz PSprintson A(2024)Flow Correlator: A Flow Table Cache Management Strategy2024 33rd International Conference on Computer Communications and Networks (ICCCN)10.1109/ICCCN61486.2024.10637657(1-9)Online publication date: 29-Jul-2024
https://doi.org/10.1109/ICCCN61486.2024.10637657
Ling ZChen XSong L(2023)A Composite Pipeline for Forwarding Low-Latency Traffic in SDN Programmable Data PlanesElectronics10.3390/electronics1202046112:2(461)Online publication date: 16-Jan-2023
https://doi.org/10.3390/electronics12020461
Tang XZeng XSong L(2023)Accelerating Protocol Oblivious Forwarding Programmable Data Plane With Flow CacheIEEE Transactions on Network and Service Management10.1109/TNSM.2022.320722720:1(578-594)Online publication date: Mar-2023
https://doi.org/10.1109/TNSM.2022.3207227
Wang WWang JYang XYang L(2022)Cache Dependent Rules With Size-Limited Flow Table in Software-Defined Networking2022 IEEE Smartworld, Ubiquitous Intelligence & Computing, Scalable Computing & Communications, Digital Twin, Privacy Computing, Metaverse, Autonomous & Trusted Vehicles (SmartWorld/UIC/ScalCom/DigitalTwin/PriComp/Meta)10.1109/SmartWorld-UIC-ATC-ScalCom-DigitalTwin-PriComp-Metaverse56740.2022.00356(1736-1741)Online publication date: Dec-2022
https://doi.org/10.1109/SmartWorld-UIC-ATC-ScalCom-DigitalTwin-PriComp-Metaverse56740.2022.00356
Zhou DYu HKaminsky MAndersen DGavrilovska AZadok E(2020)Fast software cache design for network appliancesProceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference10.5555/3489146.3489191(657-671)Online publication date: 15-Jul-2020
https://dl.acm.org/doi/10.5555/3489146.3489191
Yang JLi TYan JLi JLi CWang B(2020)PipeCache: High Hit Rate Rule-Caching Scheme Based on Multi-Stage Cache TablesElectronics10.3390/electronics90609999:6(999)Online publication date: 15-Jun-2020
https://doi.org/10.3390/electronics9060999
Yang JYang YLiu JLiu RQiao PWang B(2020)MixedCache: Enabling Flow Directed Rule-Caching Scheme based on Heterogeneous Cache for OpenFlowJournal of Physics: Conference Series10.1088/1742-6596/1693/1/0120441693(012044)Online publication date: 17-Dec-2020
https://doi.org/10.1088/1742-6596/1693/1/012044
Csikor LDivakaran DKang MKőrösi ASonkoly BHaja DPezaros DSchmid SRétvári GMohaisen AZhang Z(2019)Tuple space explosionProceedings of the 15th International Conference on Emerging Networking Experiments And Technologies10.1145/3359989.3365431(292-304)Online publication date: 3-Dec-2019
https://dl.acm.org/doi/10.1145/3359989.3365431
Wang JQi HHe YLi WLi KZhou X(2019)FlowTracer: An Effective Flow Trajectory Detection Solution Based on Probabilistic Packet Tagging in SDN-Enabled NetworksIEEE Transactions on Network and Service Management10.1109/TNSM.2019.293659816:4(1884-1898)Online publication date: Dec-2019
https://doi.org/10.1109/TNSM.2019.2936598
Xiong BHu ZLuo YWang J(2019)CuckooFlow: Achieving Fast Packet Classification for Virtual OpenFlow Switching by Exploiting Network Traffic Locality2019 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BDCloud/SocialCom/SustainCom)10.1109/ISPA-BDCloud-SustainCom-SocialCom48970.2019.00160(1123-1130)Online publication date: Dec-2019
https://doi.org/10.1109/ISPA-BDCloud-SustainCom-SocialCom48970.2019.00160
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

Flow caching for high entropy packet fields

A flow caching mechanism for fast packet forwarding

Object-Oriented Packet Caching for ICN