Every microsecond counts: Tracking fine-grain latencies with a lossy difference aggregator

Ramana Rao Kompella, Kirill Levchenko, Alex C. Snoeren, George Varghese

Research output: Contribution to journalConference article

Abstract

Many network applications have stringent end-to-end latency requirements, including VoIP and interactive video conferencing, automated trading, and high-performance computing - where even microsecond variations may be intolerable. The resulting fine-grain measurement demands cannot be met effectively by existing technologies, such as SNMP, NetFlow, or active probing. We propose instrumenting routers with a hash-based primitive that we call a Lossy Difference Aggregator (LDA) to measure latencies down to tens of microseconds and losses as infrequent as one in a million. Such measurement can be viewed abstractly as what we refer to as a coordinated streaming problem, which is fundamentally harder than standard streaming problems due to the need to coordinate values between nodes. We describe a compact data structure that efficiently computes the average and standard deviation of latency and loss rate in a coordinated streaming environment. Our theoretical results translate to an efficient hardware implementation at 40 Gbps using less than 1% of a typical 65-nm 400-MHz networking ASIC. When compared to Poisson-spaced active probing with similar overheads, our LDA mechanism delivers orders of magnitude smaller relative error; active probing requires 50-60 times as much bandwidth to deliver similar levels of accuracy.

Original languageEnglish (US)
Pages (from-to)255-266
Number of pages12
JournalComputer Communication Review
Volume39
Issue number4
DOIs
StatePublished - Nov 30 2009
Externally publishedYes
EventACM SIGCOMM 2009 Conference on Data Communication, SIGCOMM 2009 - Barcelona, Spain
Duration: Aug 17 2009Aug 21 2009

Fingerprint

Video conferencing
Application specific integrated circuits
Routers
Data structures
Hardware
Bandwidth

Keywords

  • Packet sampling
  • Passive measurement

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications

Cite this

Every microsecond counts : Tracking fine-grain latencies with a lossy difference aggregator. / Kompella, Ramana Rao; Levchenko, Kirill; Snoeren, Alex C.; Varghese, George.

In: Computer Communication Review, Vol. 39, No. 4, 30.11.2009, p. 255-266.

Research output: Contribution to journalConference article

Kompella, Ramana Rao ; Levchenko, Kirill ; Snoeren, Alex C. ; Varghese, George. / Every microsecond counts : Tracking fine-grain latencies with a lossy difference aggregator. In: Computer Communication Review. 2009 ; Vol. 39, No. 4. pp. 255-266.
@article{5d1ed3f792a84e5eaf31764669ff74d8,
title = "Every microsecond counts: Tracking fine-grain latencies with a lossy difference aggregator",
abstract = "Many network applications have stringent end-to-end latency requirements, including VoIP and interactive video conferencing, automated trading, and high-performance computing - where even microsecond variations may be intolerable. The resulting fine-grain measurement demands cannot be met effectively by existing technologies, such as SNMP, NetFlow, or active probing. We propose instrumenting routers with a hash-based primitive that we call a Lossy Difference Aggregator (LDA) to measure latencies down to tens of microseconds and losses as infrequent as one in a million. Such measurement can be viewed abstractly as what we refer to as a coordinated streaming problem, which is fundamentally harder than standard streaming problems due to the need to coordinate values between nodes. We describe a compact data structure that efficiently computes the average and standard deviation of latency and loss rate in a coordinated streaming environment. Our theoretical results translate to an efficient hardware implementation at 40 Gbps using less than 1{\%} of a typical 65-nm 400-MHz networking ASIC. When compared to Poisson-spaced active probing with similar overheads, our LDA mechanism delivers orders of magnitude smaller relative error; active probing requires 50-60 times as much bandwidth to deliver similar levels of accuracy.",
keywords = "Packet sampling, Passive measurement",
author = "Kompella, {Ramana Rao} and Kirill Levchenko and Snoeren, {Alex C.} and George Varghese",
year = "2009",
month = "11",
day = "30",
doi = "10.1145/1594977.1592599",
language = "English (US)",
volume = "39",
pages = "255--266",
journal = "Computer Communication Review",
issn = "0146-4833",
publisher = "Association for Computing Machinery (ACM)",
number = "4",

}

TY - JOUR

T1 - Every microsecond counts

T2 - Tracking fine-grain latencies with a lossy difference aggregator

AU - Kompella, Ramana Rao

AU - Levchenko, Kirill

AU - Snoeren, Alex C.

AU - Varghese, George

PY - 2009/11/30

Y1 - 2009/11/30

N2 - Many network applications have stringent end-to-end latency requirements, including VoIP and interactive video conferencing, automated trading, and high-performance computing - where even microsecond variations may be intolerable. The resulting fine-grain measurement demands cannot be met effectively by existing technologies, such as SNMP, NetFlow, or active probing. We propose instrumenting routers with a hash-based primitive that we call a Lossy Difference Aggregator (LDA) to measure latencies down to tens of microseconds and losses as infrequent as one in a million. Such measurement can be viewed abstractly as what we refer to as a coordinated streaming problem, which is fundamentally harder than standard streaming problems due to the need to coordinate values between nodes. We describe a compact data structure that efficiently computes the average and standard deviation of latency and loss rate in a coordinated streaming environment. Our theoretical results translate to an efficient hardware implementation at 40 Gbps using less than 1% of a typical 65-nm 400-MHz networking ASIC. When compared to Poisson-spaced active probing with similar overheads, our LDA mechanism delivers orders of magnitude smaller relative error; active probing requires 50-60 times as much bandwidth to deliver similar levels of accuracy.

AB - Many network applications have stringent end-to-end latency requirements, including VoIP and interactive video conferencing, automated trading, and high-performance computing - where even microsecond variations may be intolerable. The resulting fine-grain measurement demands cannot be met effectively by existing technologies, such as SNMP, NetFlow, or active probing. We propose instrumenting routers with a hash-based primitive that we call a Lossy Difference Aggregator (LDA) to measure latencies down to tens of microseconds and losses as infrequent as one in a million. Such measurement can be viewed abstractly as what we refer to as a coordinated streaming problem, which is fundamentally harder than standard streaming problems due to the need to coordinate values between nodes. We describe a compact data structure that efficiently computes the average and standard deviation of latency and loss rate in a coordinated streaming environment. Our theoretical results translate to an efficient hardware implementation at 40 Gbps using less than 1% of a typical 65-nm 400-MHz networking ASIC. When compared to Poisson-spaced active probing with similar overheads, our LDA mechanism delivers orders of magnitude smaller relative error; active probing requires 50-60 times as much bandwidth to deliver similar levels of accuracy.

KW - Packet sampling

KW - Passive measurement

UR - http://www.scopus.com/inward/record.url?scp=70450273287&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70450273287&partnerID=8YFLogxK

U2 - 10.1145/1594977.1592599

DO - 10.1145/1594977.1592599

M3 - Conference article

AN - SCOPUS:70450273287

VL - 39

SP - 255

EP - 266

JO - Computer Communication Review

JF - Computer Communication Review

SN - 0146-4833

IS - 4

ER -