More Web Proxy on the site http://driver.im/

research-article

Packet Clustering Introduced by Routers: Modeling, Analysis, and Experiments

Authors:

Hakim Weatherspoon,

Ao TangAuthors Info & Claims

ACM Transactions on Modeling and Performance Evaluation of Computing Systems (TOMPECS), Volume 4, Issue 3

Article No.: 15, Pages 1 - 28

https://doi.org/10.1145/3345032

Published: 30 August 2019 Publication History

Abstract

In this article, we investigate a router’s inherent variation on packet processing time and its effect on interpacket delay and packet clustering. We propose a simple pipeline model incorporating the inherent variation, and two metrics—one to measure packet clustering and one to quantify inherent variation. To isolate the effect of the inherent variation, we begin our analysis with no cross traffic and step through setups where the input streams have different data rates, packet size, and go through a different number of hops. We show that a homogeneous input stream with a sufficiently large interpacket gap will emerge at the router’s output with interpacket delays that are negative correlated with adjacent values and have symmetrical distributions. We show that for smaller interpacket gaps, the change in packet clustering is smaller. It is also shown that the degree of packet clustering could in fact decrease for a clustered input. We generalize our results by adding cross traffic. All the results predicted by the model are validated with experiments with real routers. We also investigated several factors that can affect the inherent variation as well as some potential applications of this study.

References

[1]

2008. IEEE Standard 802.3-2008. Retrieved from https://standards.ieee.org/standard/802_3-2008.html.

[2]

2016. Cisco Catalyst 6500 white paper. Retrieved from https://www.cisco.com/c/en/us/products/switches/catalyst-6500-series-switches/white-paper-listing.html.

[3]

Steven Blake, David Black, Mark Carlson, Elwyn Davies, Zheng Wang, and Walter Weiss. 1998. RFC 2475: An architecture for differentiated services. Internet Engineering Task Force (IETF) RFC. https://tools.ietf.org/html/rfc2475.

Digital Library

[4]

Jean-Chrysotome Bolot. 1993. End-to-end packet delay and loss behavior in the Internet. ACM SIGCOMM Comput. Commun. Rev. 23, 4 (Oct. 1993), 289--298.

Digital Library

[5]

Lawrence S. Brakmo and Larry L. Peterson. 1995. TCP Vegas: End to end congestion avoidance on a global Internet. IEEE J. Sel. Areas Commun. (J-SAC) 13, 8 (1995), 1465--1480.

Digital Library

[6]

Andre Broido, Ryan King, Evi Nemeth, and K. C. Claffy. 2003. Radon spectroscopy of inter-packet delay. In High-Speed Networking (HSN) Workshop.

[7]

H. Jonathan Chao and Bin Liu. 2007. High Performance Switches and Routers. John Wiley 8 Sons.

Digital Library

[8]

Roman Chertov and Sonia Fahmy. 2011. Forwarding devices: From measurements to simulations. ACM Trans. Model. Comput. Simul. 21, 2, Article 12 (Feb. 2011), 23 pages.

Digital Library

[9]

Mark E. Crovella and Azer Bestavros. 1997. Self-similarity in World Wide Web traffic: Evidence and possible causes. IEEE/ACM Trans. Networking 5, 6 (1997), 835--846.

Digital Library

[10]

Hamza Dahmouni, André Girard, and Brunilde Sansò. 2012. An analytical model for jitter in IP networks. Ann. Telecommun. 67, 1--2 (2012), 81--90.

[11]

Allen B. Downey. 2001. The structural cause of file size distributions. In International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS). IEEE, 361--370.

Digital Library

[12]

Daniel A. Freedman, Tudor Marian, Jennifer H. Lee, Ken Birman, Hakim Weatherspoon, and Chris Xu. 2010. Exact temporal characterization of 10 Gbps optical wide-area network. In Proceedings of the 10th ACM SIGCOMM Conference on Internet Measurement (IMC’10). ACM, New York, NY, 342--355.

Digital Library

[13]

Nicolas Hohn, Darryl Veitch, Konstantina Papagiannaki, and Christophe Diot. 2004. Bridging router performance and queuing theory. In ACM SIGMETRICS Performance Evaluation Review, Vol. 32. ACM, 355--366.

Digital Library

[14]

Hao Jiang and Constantinos Dovrolis. 2005. Why is the internet traffic bursty in short time scales? In Proceedings of the 2005 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS’05). ACM, New York, NY, 241--252.

Digital Library

[15]

Srikanth Kandula, Dina Katabi, Shantanu Sinha, and Arthur Berger. 2007. Dynamic load balancing without packet reordering. ACM SIGCOMM Comput. Commun. Rev. 37, 2 (March 2007), 51--62.

Digital Library

[16]

John F. C. Kingman. 1970. Inequalities in the theory of queues. J. R. Stat. Soc. Ser. B Stat. Method. 32, 1 (1970), 102--110.

[17]

Hisashi Kobayashi and Brian L. Mark. 2008. System modeling and analysis: Foundations of system performance evaluation. (2008).

Digital Library

[18]

Ki Suh Lee, Han Wang, and Hakim Weatherspoon. 2013. SoNIC: Precise realtime software access and control of wired networks. In USENIX Symposium on Networked Systems Design and Implementation (NSDI) (NSDI’13). USENIX Association, Berkeley, CA, 213--266.

Digital Library

[19]

Ki Suh Lee, Han Wang, and Hakim Weatherspoon. 2014. PHY covert channels: Can you see the idles? In USENIX Symposium on Networked Systems Design and Implementation (NSDI) (NSDI’14). USENIX Association, Berkeley, CA, 173--185.

Digital Library

[20]

Will E. Leland, Murad S. Taqqu, Walter Willinger, and Daniel V. Wilson. 1993. On the self-similar nature of ethernet traffic. ACM SIGCOMM Comput. Commun. Rev. 23, 4 (Oct. 1993), 183--193.

Digital Library

[21]

David V. Lindley. 1952. The theory of queues with a single server. In Mathematical Proceedings of the Cambridge Philosophical Society, Vol. 48. Cambridge University Press, 277--289.

[22]

Xiliang Liu, Kaliappa Ravindran, and Dmitri Loguinov. 2007. A queueing-theoretic foundation of available bandwidth estimation: Single-hop analysis. IEEE/ACM Trans. Networking 15, 4 (Aug. 2007), 918--931.

Digital Library

[23]

Yuanqiu Luo and Nirwan Ansari. 2005. Bandwidth allocation for multiservice access on EPONs. IEEE Commun. Mag. 43, 2 (2005), S16--S21.

Digital Library

[24]

Tudor Marian, Daniel A. Freedman, Ken Birman, and Hakim Weatherspoon. 2010. Empirical characterization of uncongested optical lambda networks and 10gbe commodity endpoints. In IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). IEEE, 575--584.

[25]

Wassim Matragi, Khosrow Sohraby, and Chatschik Bisdikian. 1997. Jitter calculus in ATM networks: Multiple nodes. IEEE/ACM Trans. Networking 5, 1 (Feb. 1997), 122--133.

Digital Library

[26]

A. Morton and B. Claise. 2009. RFC 5481: Packet delay variation applicability statement. Internet Engineering Task Force (IETF) RFC. https://tools.ietf.org/html/rfc5481.

[27]

Kihong Park, Gitae Kim, and Mark Crovella. 1996. On the relationship between file sizes, transport protocols, and self-similar network traffic. In IEEE International Conference on Network Protocols (ICNP). IEEE, 171--180.

Digital Library

[28]

Li-Shiuan Peh and William J. Dally. 2001. A delay model and speculative architecture for pipelined routers. In 7th International Symposium on High-Performance Computer Architecture. IEEE, 255--266.

Digital Library

[29]

Li-Shiuan Peh and William J. Dally. 2001. A delay model for router microarchitectures. IEEE Micro 21, 1 (2001), 26--34.

Digital Library

[30]

Jonathan Perry, Amy Ousterhout, Hari Balakrishnan, Devavrat Shah, and Hans Fugal. 2014. Fastpass: A centralized “Zero-Queue” datacenter network. In ACM SIGCOMM Computer Communication Review, Vol. 44. ACM, New York, NY, 307--318.

Digital Library

[31]

Aleksandr Privalov and Khosrow Sohraby. 1998. Per-stream jitter analysis in CBR ATM multiplexors. IEEE/ACM Trans. Networking 6, 2 (1998), 141--149.

Digital Library

[32]

Henning Schulzrinne, Steven Casner, R. Frederick, and Van Jacobson. 2003. RFC 3550 RTP: A Transport Protocol for Real-Time Applications. Internet Engineering Task Force (IETF) RFC. https://tools.ietf.org/html/rfc3550.

Digital Library

[33]

Rishi Sinha, Christos Papadopoulos, and John Heidemann. 2007. Internet packet size distributions: Some observations. Retrieved from http://netweb.usc.edu/&sim;rsinha/pkt-sizes.

[34]

Ao Tang, Lachlan L. H. Andrew, Krister Jacobsson, Karl H. Johansson, Håkan Hjalmarsson, and Steven H. Low. 2010. Queue dynamics with window flow control. IEEE/ACM Trans. Networking 18, 5 (2010), 1422--1435.

Digital Library

[35]

Xinyuan Wang, Douglas S. Reeves, and S. Felix Wu. 2002. Inter-packet delay based correlation for tracing encrypted connections through stepping stones. In European Symposium on Research in Computer Security (ESORICS). Springer, 244--263.

Digital Library

[36]

Walter Willinger, Murad S. Taqqu, Robert Sherman, and Daniel V. Wilson. 1997. Self-similarity through high-variability: Statistical analysis of Ethernet LAN traffic at the source level. IEEE/ACM Trans. Networking 5, 1 (1997), 71--86.

Digital Library

[37]

Sebastian Zander, Grenville Armitage, and Philip Branch. 2007. A survey of covert channels and countermeasures in computer network protocols. IEEE Commun. Surv. Tutorials 9, 3 (2007), 44--57.

Digital Library

Cited By

Bäckman ROliver ILimonta G(2020)Integrity Checking of Railway Interlocking FirmwareComputer Safety, Reliability, and Security. SAFECOMP 2020 Workshops10.1007/978-3-030-55583-2_12(161-175)Online publication date: 15-Sep-2020
https://dl.acm.org/doi/10.1007/978-3-030-55583-2_12
Zoppi TMungiello ICeccarelli ACirillo ASarti LEsposito LScaglione GRepetto SBondavalli A(undefined)Safe Maintenance of Railways using COTS Mobile Devices: The Remote Worker DashboardACM Transactions on Cyber-Physical Systems10.1145/3607193
https://dl.acm.org/doi/10.1145/3607193

Index Terms

Packet Clustering Introduced by Routers: Modeling, Analysis, and Experiments
1. Networks
  1. Network performance evaluation
    1. Network performance modeling

Recommendations

Buffer size and packet loss in a tandem queueing network
Application of Multi Level ATM in Reducing Latency in Clouds for Performance Improvement of Integrated Voice, Video and Data Services
ITNG '14: Proceedings of the 2014 11th International Conference on Information Technology: New Generations

A study to apply binary ATM in reducing latency and packet error probability in cloud for integrated voice, video and data is made in the paper. Studies reveal the superiority of binary ATM to conventional ATM.
A Packet Switch with a Priority Scheduling Discipline: Performance Analysis

In this paper, we analyze a discrete-time GI-G₁, Geo₂-1 preemptive resume priority queue. We consider two classes of packets which have to be served, where one class has preemptive resume priority over the other. The high-priority class contains packets ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Modeling and Performance Evaluation of Computing Systems

ACM Transactions on Modeling and Performance Evaluation of Computing Systems Volume 4, Issue 3

September 2019

151 pages

ISSN:2376-3639

EISSN:2376-3647

DOI:10.1145/3343140

Editors:
Sem Borst
Nokia Bell Labs / Eindhoven University of Technology, the Netherlands
,
Carey Williamson
University of Calgary, Canada

Issue’s Table of Contents

Copyright © 2019 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 August 2019

Accepted: 01 April 2019

Revised: 01 March 2019

Received: 01 December 2017

Published in TOMPECS Volume 4, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
104
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)1

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bäckman ROliver ILimonta G(2020)Integrity Checking of Railway Interlocking FirmwareComputer Safety, Reliability, and Security. SAFECOMP 2020 Workshops10.1007/978-3-030-55583-2_12(161-175)Online publication date: 15-Sep-2020
https://dl.acm.org/doi/10.1007/978-3-030-55583-2_12
Zoppi TMungiello ICeccarelli ACirillo ASarti LEsposito LScaglione GRepetto SBondavalli A(undefined)Safe Maintenance of Railways using COTS Mobile Devices: The Remote Worker DashboardACM Transactions on Cyber-Physical Systems10.1145/3607193
https://dl.acm.org/doi/10.1145/3607193

View Options

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents