short-paper

CherryPick: tracing packet trajectory in software-defined datacenter networks

Authors:

Praveen Tammana,

Rachit Agarwal,

Myungjin LeeAuthors Info & Claims

SOSR '15: Proceedings of the 1st ACM SIGCOMM Symposium on Software Defined Networking Research

Article No.: 23, Pages 1 - 7

https://doi.org/10.1145/2774993.2775066

Published: 17 June 2015 Publication History

Abstract

SDN-enabled datacenter network management and debugging can benefit by the ability to trace packet trajectories. For example, such a functionality allows measuring traffic matrix, detecting traffic anomalies, localizing network faults, etc. Existing techniques for tracing packet trajectories require either large data collection overhead or large amount of data plane resources such as switch flow rules and packet header space. We present CherryPick, a scalable, yet simple technique for tracing packet trajectories. The core idea of our technique is to cherry-pick the links that are key to representing an end-to-end path of a packet, and to embed them into its header on its way to destination. Preliminary evaluation on a fat-tree topology shows that CherryPick requires minimal switch flow rules, while using header space close to state-of-the-art techniques.

References

[1]

K. Agarwal, E. Rozner, C. Dixon, and J. Carter. SDN Traceroute: Tracing SDN Forwarding Without Changing Network Behavior. In ACM HotSDN, 2014.

Digital Library

[2]

T. Ball, N. Bjørner, A. Gember, S. Itzhaky, A. Karbyshev, M. Sagiv, M. Schapira, and A. Valadarsky. VeriCon: Towards Verifying Controller Programs in Software-defined Networks. In ACM PLDI, 2014.

Digital Library

[3]

P. Bosshart, G. Gibb, H.-S. Kim, G. Varghese, N. McKeown, M. Izzard, F. Mujica, and M. Horowitz. Forwarding Metamorphosis: Fast Programmable Match-action Processing in Hardware for SDN. In ACM SIGCOMM, 2013.

Digital Library

[4]

M. Canini, D. Venzano, P. Perešíni, D. Kostić, and J. Rexford. A NICE Way to Test OpenFlow Applications. In USENIX NSDI, 2012.

Digital Library

[5]

M. Chiesa, I. Nikolaevskiy, A. Panda, A. Gurtov, M. Schapira, and S. Shenker. Exploring the Limits of Static Failover Routing. CoRR, abs/1409.0034, 2014.

[6]

R. Cole, K. Ost, and S. Schirra. Edge-Coloring Bipartite Multigraphs in O(E log D) Time. Combinatorica, 21(1), 2001.

[7]

D. Dean, M. Franklin, and A. Stubblefield. An algebraic approach to IP traceback. ACM Transactions on Information and System Security, 5(2): 119--137, 2002.

Digital Library

[8]

A. Dixit, P. Prakash, Y. C. Hu, and R. R. Kompella. On the Impact of Packet Spraying in Data Center Networks. In IEEE INFOCOM, 2013.

[9]

N. G. Duffield and M. Grossglauser. Trajectory Sampling for Direct Traffic Observation. IEEE/ACM ToN, 9(3), 2001.

Digital Library

[10]

P. Gill, N. Jain, and N. Nagappan. Understanding Network Failures in Data Centers: Measurement, Analysis, and Implications. In ACM SIGCOMM, 2011.

Digital Library

[11]

N. Handigol, B. Heller, V. Jeyakumar, D. Mazières, and N. McKeown. I Know What Your Packet Did Last Hop: Using Packet Histories to Troubleshoot Networks. In USENIX NSDI, 2014.

Digital Library

[12]

V. Jeyakumar, M. Alizadeh, Y. Geng, C. Kim, and D. Mazières. Millions of Little Minions: Using Packets for Low Latency Network Programming and Visibility. In ACM SIGCOMM, 2014.

Digital Library

[13]

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

Digital Library

[14]

A. Khurshid, X. Zou, W. Zhou, M. Caesar, and P. B. Godfrey. VeriFlow: Verifying Network-Wide Invariants in Real Time. In USENIX NSDI, 2013.

Digital Library

[15]

M. Kuzniar, P. Peresini, M. Canini, D. Venzano, and D. Kostic. A SOFT Way for Openflow Switch Interoperability Testing. In ACM CoNEXT, 2012.

Digital Library

[16]

H. Mai, A. Khurshid, R. Agarwal, M. Caesar, P. B. Godfrey, and S. T. King. Debugging the data plane with anteater. In ACM SIGCOMM, 2011.

Digital Library

[17]

S. Narayana, J. Rexford, and D. Walker. Compiling Path Queries in Software-defined Networks. In ACM HotSDN, 2014.

Digital Library

[18]

S. Nelakuditi, S. Lee, Y. Yu, Z.-L. Zhang, and C.-N. Chuah. Fast local rerouting for handling transient link failures. In IEEE/ACM ToN, 2007.

Digital Library

[19]

Open Networking Foundation. OpenFlow Switch Specification Version 1.4.0. http://tinyurl.com/kh6ef6s, 2013.

[20]

P. Prakash, A. Dixit, Y. C. Hu, and R. Kompella. The TCP Outcast Problem: Exposing Unfairness in Data Center Networks. In USENIX NSDI, 2012.

Digital Library

[21]

C. Raiciu, S. Barre, C. Pluntke, A. Greenhalgh, D. Wischik, and M. Handley. Improving Datacenter Performance and Robustness with Multipath TCP. In ACM SIGCOMM, 2011.

Digital Library

[22]

S. Savage, D. Wetherall, A. Karlin, and T. Anderson. Practical Network Support for IP Traceback. In ACM SIGCOMM, 2000.

Digital Library

[23]

F. P. Tso, G. Hamilton, R. Weber, C. S. Perkins, and D. P. Pezaros. Longer is better: exploiting path diversity in data center networks. In IEEE ICDCS, 2013.

Digital Library

[24]

B. Yang, J. Liu, S. Shenker, J. Li, and K. Zheng. Keep forwarding: Towards k-link failure resilient routing. In IEEE INFOCOM, 2014.

[25]

K. Zarifis, R. Miao, M. Calder, E. Katz-Bassett, M. Yu, and J. Padhye. DIBS: Just-in-time Congestion Mitigation for Data Centers. In ACM EuroSys, 2014.

Digital Library

[26]

H. Zeng, P. Kazemian, G. Varghese, and N. McKeown. Automatic Test Packet Generation. IEEE/ACM ToN, 22(2): 554--566, 2014.

Digital Library

[27]

H. Zhang, C. Lumezanu, J. Rhee, N. Arora, Q. Xu, and G. Jiang. Enabling Layer 2 Pathlet Tracing Through Context Encoding in Software-defined Networking. In ACM HotSDN, 2014.

Digital Library

[28]

Y. Zhang, M. Roughan, N. Duffield, and A. Greenberg. Fast Accurate Computation of Large-scale IP Traffic Matrices from Link Loads. In ACM SIGMETRICS, 2003.

Digital Library

Cited By

Liu ZZhao YFan ZYang TLi XZhang RYang KJiang ZZhong ZHuang YLiu CHu JXie GCui B(2024)BurstBalancer: Do Less, Better Balance for Large-Scale Data Center TrafficIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.329545435:6(932-949)Online publication date: Jun-2024
https://doi.org/10.1109/TPDS.2023.3295454
Seo MKim JMarin EYou MPark TLee SShin SKim J(2022)Heimdallr: Fingerprinting SD-WAN Control-Plane Architecture via Encrypted Control TrafficProceedings of the 38th Annual Computer Security Applications Conference10.1145/3564625.3564642(949-963)Online publication date: 5-Dec-2022
https://dl.acm.org/doi/10.1145/3564625.3564642
Xi SBu KMao WZhang XRen KRen X(2022)RuleOut Forwarding Anomalies for SDNIEEE/ACM Transactions on Networking10.1109/TNET.2022.3194970(1-13)Online publication date: 2022
https://doi.org/10.1109/TNET.2022.3194970
Show More Cited By

Index Terms

CherryPick: tracing packet trajectory in software-defined datacenter networks
1. Networks
  1. Network services

Recommendations

Flow-level loss detection with Δ-sketches
SOSR '22: Proceedings of the Symposium on SDN Research

Packet drops caused by congestion are a fundamental problem in network operation. Yet, it is difficult to detect where drops are happening, let alone which flows are most affected. Detecting the small-timescale drops caused by short bursts of traffic is ...
Compiling path queries in software-defined networks
HotSDN '14: Proceedings of the third workshop on Hot topics in software defined networking

Monitoring the flow of traffic along network paths is essential for SDN programming and troubleshooting. For example, traffic engineering requires measuring the ingress-egress traffic matrix; debugging a congested link requires determining the set of ...
Accurate and real time method for network packet classification
AIC'06: Proceedings of the 6th WSEAS International Conference on Applied Informatics and Communications

Evolution of Internet has been accompanied by the development of a range of network applications which introduce many interesting, challenging and tricky problem to the network traffic monitoring. The increasing numbers of applications cause network ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SOSR '15: Proceedings of the 1st ACM SIGCOMM Symposium on Software Defined Networking Research

June 2015

226 pages

ISBN:9781450334518

DOI:10.1145/2774993

Program Chairs:
Jennifer Rexford
Princeton
,
Amin Vahdat
Google

Copyright © 2015 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
ONS: Open Networking Summit

In-Cooperation

USENIX Assoc: USENIX Assoc

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 June 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Short-paper

Funding Sources

Engineering and Physical Sciences Research Council

Conference

SOSR 2015

Sponsor:

SIGCOMM
ONS

SOSR 2015: ACM SIGCOMM Symposium on SDN Research

June 17 - 18, 2015

California, Santa Clara

Acceptance Rates

SOSR '15 Paper Acceptance Rate 7 of 43 submissions, 16%;

Overall Acceptance Rate 7 of 43 submissions, 16%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

63
Total Citations
View Citations
638
Total Downloads

Downloads (Last 12 months)29
Downloads (Last 6 weeks)10

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu ZZhao YFan ZYang TLi XZhang RYang KJiang ZZhong ZHuang YLiu CHu JXie GCui B(2024)BurstBalancer: Do Less, Better Balance for Large-Scale Data Center TrafficIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.329545435:6(932-949)Online publication date: Jun-2024
https://doi.org/10.1109/TPDS.2023.3295454
Seo MKim JMarin EYou MPark TLee SShin SKim J(2022)Heimdallr: Fingerprinting SD-WAN Control-Plane Architecture via Encrypted Control TrafficProceedings of the 38th Annual Computer Security Applications Conference10.1145/3564625.3564642(949-963)Online publication date: 5-Dec-2022
https://dl.acm.org/doi/10.1145/3564625.3564642
Xi SBu KMao WZhang XRen KRen X(2022)RuleOut Forwarding Anomalies for SDNIEEE/ACM Transactions on Networking10.1109/TNET.2022.3194970(1-13)Online publication date: 2022
https://doi.org/10.1109/TNET.2022.3194970
Fang CLiu HMiao MYe JWang LZhang WKang DLyu BZhu SCheng PChen J(2022)Towards Automatic Root Cause Diagnosis of Persistent Packet Loss in Cloud Overlay NetworkIEEE/ACM Transactions on Networking10.1109/TNET.2021.313755730:3(1178-1192)Online publication date: Jun-2022
https://doi.org/10.1109/TNET.2021.3137557
Liu ZZhao YFan ZYang TLi XZhang RYang KZhong ZHuang YLiu CHu JXie GCui B(2022)BurstBalancer: Do Less, Better Balance for Large-scale Data Center Traffic2022 IEEE 30th International Conference on Network Protocols (ICNP)10.1109/ICNP55882.2022.9940372(1-13)Online publication date: 30-Oct-2022
https://doi.org/10.1109/ICNP55882.2022.9940372
Yuming LYong WHao FZeyu W(2022)GwPFV: A novel packet forwarding verification mechanism based on gateways in SDN-based storage environmentJournal of Information Security and Applications10.1016/j.jisa.2022.10335471(103354)Online publication date: Dec-2022
https://doi.org/10.1016/j.jisa.2022.103354
Xu HHui KFu CZhang H(2021)Computational LEGO technic designACM Transactions on Graphics10.1145/3355089.335650438:6(1)Online publication date: 27-Aug-2021
https://dl.acm.org/doi/10.1145/3355089.3356504
Popescu DMoore A(2021)Measuring Network Conditions in Data Centers Using the Precision Time ProtocolIEEE Transactions on Network and Service Management10.1109/TNSM.2021.308153618:3(3753-3770)Online publication date: Sep-2021
https://doi.org/10.1109/TNSM.2021.3081536
Thimmaraju KSchiff LSchmid S(2021)Preacher: Network Policy Checker for Adversarial EnvironmentsIEEE/ACM Transactions on Networking10.1109/TNET.2021.307814329:5(2087-2100)Online publication date: Oct-2021
https://doi.org/10.1109/TNET.2021.3078143
Kim JNam JLee SYegneswaran VPorras PShin S(2021)BottleNet: Hiding Network Bottlenecks Using SDN-Based Topology DeceptionIEEE Transactions on Information Forensics and Security10.1109/TIFS.2021.307584516(3138-3153)Online publication date: 2021
https://doi.org/10.1109/TIFS.2021.3075845
Show More Cited By

View Options

Get Access

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents