Path-quality monitoring in the presence of adversaries

Sharon Goldberg, David Xiao, Eran Tromer, Boaz Barak, Jennifer L. Rexford

Research output: Chapter in Book/Report/Conference proceedingConference contribution

54 Scopus citations

Abstract

Edge networks connected to the Internet need effective monitoring techniques to drive routing decisions and detect violations of Service Level Agreements (SLAs). However, existing measurement tools, like ping, traceroute, and trajectory sampling, are vulnerable to attacks that can make a path look better than it really is. In this paper, we design and analyze path-quality monitoring protocols that reliably raise an alarm when the packet-loss rate and delay exceed a threshold, even when an adversary tries to bias monitoring results by selectively delaying, dropping, modifying, injecting, or preferentially treating packets. Despite the strong threat model we consider in this paper, our protocols are efficient enough to run at line rate on high-speed routers. We present a secure sketching protocol for identifying when packet loss and delay degrade beyond a threshold. This protocol is extremely lightweight, requiring only 250-600 bytes of storage and periodic transmission of a comparably sized IP packet to monitor billions of packets. We also present secure sampling protocols that provide faster feedback and accurate round-trip delay estimates, at the expense of somewhat higher storage and communication costs. We prove that all our protocols satisfy a precise definition of secure path-quality monitoring and derive analytic expressions for the trade-off between statistical accuracy and system overhead. We also compare how our protocols perform in the client-server setting, when paths are asymmetric, and when packet marking is not permitted.

Original languageEnglish (US)
Title of host publicationSIGMETRICS'08
Subtitle of host publicationProceedings of the 2008 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems
Pages193-204
Number of pages12
Edition1 SPECIAL ISSUE
DOIs
StatePublished - Dec 12 2008
Event2008 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS'08 - Annapolis, MD, United States
Duration: Jun 2 2008Jun 6 2008

Publication series

NameSIGMETRICS'08: Proceedings of the 2008 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems
Number1 SPECIAL ISSUE
Volume36

Other

Other2008 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS'08
CountryUnited States
CityAnnapolis, MD
Period6/2/086/6/08

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Software

Keywords

  • Measurement
  • Security

Fingerprint Dive into the research topics of 'Path-quality monitoring in the presence of adversaries'. Together they form a unique fingerprint.

  • Cite this

    Goldberg, S., Xiao, D., Tromer, E., Barak, B., & Rexford, J. L. (2008). Path-quality monitoring in the presence of adversaries. In SIGMETRICS'08: Proceedings of the 2008 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (1 SPECIAL ISSUE ed., pp. 193-204). (SIGMETRICS'08: Proceedings of the 2008 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems; Vol. 36, No. 1 SPECIAL ISSUE). https://doi.org/10.1145/1375457.1375480