Scalable, low-overhead network delay estimation

Volkan Ozdemir, Shan Muthukrishnan, Injong Rhee

Research output: Contribution to journalConference article

3 Citations (Scopus)

Abstract

The round trip network delay times between pairs of nodes in a multicast session is a key parameter; it is used in suppressing the implosion of request and repair packets, in detecting congestion, etc. This paper presents a protocol to estimate the delays between every pair of nodes in a multicast group. While existing protocols use O(n) multicast messages with O(n) size each (total of O(n2) bits), our protocol requires O(n) multicasts with only O(1) size each (total of O(n) bits); here, n is the session size. It does not require clocks to be synchronized, or any knowledge of network topology and the session size. We incorporate our protocol into the SRM protocol and show by our simulations that (i) our delay estimation protocol is reasonably accurate, (ii) it is just as effective as existing delay estimation protocols in suppressing repair and request traffic in SRM, and (iii) it has significantly lower overhead than the existing delay estimation protocols. Furthermore, our protocol can be extended to run within a hierarchically structured multicast protocol such as RMTP. Here the goal is to estimate round trip delays from a sender to each receiver. Our protocol ensures that only the immediate children of the sender send feedback messages directly to the sender, thereby avoiding feedback implosion. Our delay estimation protocols therefore significantly enhance the scalability of unstructured multicast protocols such as SRM, as well as tree-structured multicast protocols such as RMTP.

Original languageEnglish (US)
Pages (from-to)1343-1350
Number of pages8
JournalProceedings - IEEE INFOCOM
Volume3
StatePublished - Jan 1 2000
Externally publishedYes
Event19th Annual Joint Conference of the IEEE Computer and Communications Societies - IEEE INFOCOM2000: 'Reaching the Promised Land of Communications' - Tel Aviv, Isr
Duration: Mar 26 2000Mar 30 2000

Fingerprint

Repair
Feedback
Scalability
Clocks
Time delay
Topology

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Electrical and Electronic Engineering

Cite this

Ozdemir, V., Muthukrishnan, S., & Rhee, I. (2000). Scalable, low-overhead network delay estimation. Proceedings - IEEE INFOCOM, 3, 1343-1350.
Ozdemir, Volkan ; Muthukrishnan, Shan ; Rhee, Injong. / Scalable, low-overhead network delay estimation. In: Proceedings - IEEE INFOCOM. 2000 ; Vol. 3. pp. 1343-1350.
@article{7c397aac341e4d2a8c2499fee4a08076,
title = "Scalable, low-overhead network delay estimation",
abstract = "The round trip network delay times between pairs of nodes in a multicast session is a key parameter; it is used in suppressing the implosion of request and repair packets, in detecting congestion, etc. This paper presents a protocol to estimate the delays between every pair of nodes in a multicast group. While existing protocols use O(n) multicast messages with O(n) size each (total of O(n2) bits), our protocol requires O(n) multicasts with only O(1) size each (total of O(n) bits); here, n is the session size. It does not require clocks to be synchronized, or any knowledge of network topology and the session size. We incorporate our protocol into the SRM protocol and show by our simulations that (i) our delay estimation protocol is reasonably accurate, (ii) it is just as effective as existing delay estimation protocols in suppressing repair and request traffic in SRM, and (iii) it has significantly lower overhead than the existing delay estimation protocols. Furthermore, our protocol can be extended to run within a hierarchically structured multicast protocol such as RMTP. Here the goal is to estimate round trip delays from a sender to each receiver. Our protocol ensures that only the immediate children of the sender send feedback messages directly to the sender, thereby avoiding feedback implosion. Our delay estimation protocols therefore significantly enhance the scalability of unstructured multicast protocols such as SRM, as well as tree-structured multicast protocols such as RMTP.",
author = "Volkan Ozdemir and Shan Muthukrishnan and Injong Rhee",
year = "2000",
month = "1",
day = "1",
language = "English (US)",
volume = "3",
pages = "1343--1350",
journal = "Proceedings - IEEE INFOCOM",
issn = "0743-166X",
publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

Ozdemir, V, Muthukrishnan, S & Rhee, I 2000, 'Scalable, low-overhead network delay estimation', Proceedings - IEEE INFOCOM, vol. 3, pp. 1343-1350.

Scalable, low-overhead network delay estimation. / Ozdemir, Volkan; Muthukrishnan, Shan; Rhee, Injong.

In: Proceedings - IEEE INFOCOM, Vol. 3, 01.01.2000, p. 1343-1350.

Research output: Contribution to journalConference article

TY - JOUR

T1 - Scalable, low-overhead network delay estimation

AU - Ozdemir, Volkan

AU - Muthukrishnan, Shan

AU - Rhee, Injong

PY - 2000/1/1

Y1 - 2000/1/1

N2 - The round trip network delay times between pairs of nodes in a multicast session is a key parameter; it is used in suppressing the implosion of request and repair packets, in detecting congestion, etc. This paper presents a protocol to estimate the delays between every pair of nodes in a multicast group. While existing protocols use O(n) multicast messages with O(n) size each (total of O(n2) bits), our protocol requires O(n) multicasts with only O(1) size each (total of O(n) bits); here, n is the session size. It does not require clocks to be synchronized, or any knowledge of network topology and the session size. We incorporate our protocol into the SRM protocol and show by our simulations that (i) our delay estimation protocol is reasonably accurate, (ii) it is just as effective as existing delay estimation protocols in suppressing repair and request traffic in SRM, and (iii) it has significantly lower overhead than the existing delay estimation protocols. Furthermore, our protocol can be extended to run within a hierarchically structured multicast protocol such as RMTP. Here the goal is to estimate round trip delays from a sender to each receiver. Our protocol ensures that only the immediate children of the sender send feedback messages directly to the sender, thereby avoiding feedback implosion. Our delay estimation protocols therefore significantly enhance the scalability of unstructured multicast protocols such as SRM, as well as tree-structured multicast protocols such as RMTP.

AB - The round trip network delay times between pairs of nodes in a multicast session is a key parameter; it is used in suppressing the implosion of request and repair packets, in detecting congestion, etc. This paper presents a protocol to estimate the delays between every pair of nodes in a multicast group. While existing protocols use O(n) multicast messages with O(n) size each (total of O(n2) bits), our protocol requires O(n) multicasts with only O(1) size each (total of O(n) bits); here, n is the session size. It does not require clocks to be synchronized, or any knowledge of network topology and the session size. We incorporate our protocol into the SRM protocol and show by our simulations that (i) our delay estimation protocol is reasonably accurate, (ii) it is just as effective as existing delay estimation protocols in suppressing repair and request traffic in SRM, and (iii) it has significantly lower overhead than the existing delay estimation protocols. Furthermore, our protocol can be extended to run within a hierarchically structured multicast protocol such as RMTP. Here the goal is to estimate round trip delays from a sender to each receiver. Our protocol ensures that only the immediate children of the sender send feedback messages directly to the sender, thereby avoiding feedback implosion. Our delay estimation protocols therefore significantly enhance the scalability of unstructured multicast protocols such as SRM, as well as tree-structured multicast protocols such as RMTP.

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

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

M3 - Conference article

VL - 3

SP - 1343

EP - 1350

JO - Proceedings - IEEE INFOCOM

JF - Proceedings - IEEE INFOCOM

SN - 0743-166X

ER -

Ozdemir V, Muthukrishnan S, Rhee I. Scalable, low-overhead network delay estimation. Proceedings - IEEE INFOCOM. 2000 Jan 1;3:1343-1350.