Multicasting in heterogeneous networks

Amotz Bar-Noy; Sudipto Guha; Joseph Naor; Baruch Schieber

doi:10.1145/276698.276857

Multicasting in heterogeneous networks

Amotz Bar-Noy
, Sudipto Guha
, Joseph Naor
, Baruch Schieber

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

In heterogeneous networks sending messages may incur different delays on different edges, and each processor may have a different switching time between messages. The well studied Telephone model is obtained when all edge delays and switching times are equal to one unit. We investigate the problem of finding the minimum time required to multicast a message from one source to a subset of the processors of size k. The problem is NP-hard even in the basic Telephone model. We present a polynomial time algorithm that approximates the minimum multicast time within a factor of O(log k). Our algorithm improves on the best known approximation factor for the Telephone model by a factor of O (log n/log log k). No approximation algorithms were known for the general model considered in this paper.

Original language	English (US)
Title of host publication	Proceedings of the 1998 30th Annual ACM Symposium on Theory of Computing
Publisher	ACM
Pages	448-453
Number of pages	6
ISBN (Print)	9780897919623
DOIs	https://doi.org/10.1145/276698.276857
State	Published - 1998
Externally published	Yes
Event	30th Annual ACM Symposium on the Theory of Computing, STOC 1998 - Dallas, TX, USA Duration: May 23 1998 → May 26 1998

Publication series

Name	Conference Proceedings of the Annual ACM Symposium on Theory of Computing

Conference

Conference	30th Annual ACM Symposium on the Theory of Computing, STOC 1998
City	Dallas, TX, USA
Period	5/23/98 → 5/26/98

ASJC Scopus subject areas

Software

Access to Document

10.1145/276698.276857

Cite this

@inproceedings{bb1729d1357d441d923aab097280c623,

title = "Multicasting in heterogeneous networks",

abstract = "In heterogeneous networks sending messages may incur different delays on different edges, and each processor may have a different switching time between messages. The well studied Telephone model is obtained when all edge delays and switching times are equal to one unit. We investigate the problem of finding the minimum time required to multicast a message from one source to a subset of the processors of size k. The problem is NP-hard even in the basic Telephone model. We present a polynomial time algorithm that approximates the minimum multicast time within a factor of O(log k). Our algorithm improves on the best known approximation factor for the Telephone model by a factor of O (log n/log log k). No approximation algorithms were known for the general model considered in this paper.",

author = "Amotz Bar-Noy and Sudipto Guha and Joseph Naor and Baruch Schieber",

year = "1998",

doi = "10.1145/276698.276857",

language = "English (US)",

isbn = "9780897919623",

series = "Conference Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "ACM",

pages = "448--453",

booktitle = "Proceedings of the 1998 30th Annual ACM Symposium on Theory of Computing",

note = "30th Annual ACM Symposium on the Theory of Computing, STOC 1998 ; Conference date: 23-05-1998 Through 26-05-1998",

}

Bar-Noy, A, Guha, S, Naor, J & Schieber, B 1998, Multicasting in heterogeneous networks. in Proceedings of the 1998 30th Annual ACM Symposium on Theory of Computing. Conference Proceedings of the Annual ACM Symposium on Theory of Computing, ACM, pp. 448-453, 30th Annual ACM Symposium on the Theory of Computing, STOC 1998, Dallas, TX, USA, 5/23/98. https://doi.org/10.1145/276698.276857

TY - GEN

T1 - Multicasting in heterogeneous networks

AU - Bar-Noy, Amotz

AU - Guha, Sudipto

AU - Naor, Joseph

AU - Schieber, Baruch

PY - 1998

Y1 - 1998

N2 - In heterogeneous networks sending messages may incur different delays on different edges, and each processor may have a different switching time between messages. The well studied Telephone model is obtained when all edge delays and switching times are equal to one unit. We investigate the problem of finding the minimum time required to multicast a message from one source to a subset of the processors of size k. The problem is NP-hard even in the basic Telephone model. We present a polynomial time algorithm that approximates the minimum multicast time within a factor of O(log k). Our algorithm improves on the best known approximation factor for the Telephone model by a factor of O (log n/log log k). No approximation algorithms were known for the general model considered in this paper.

AB - In heterogeneous networks sending messages may incur different delays on different edges, and each processor may have a different switching time between messages. The well studied Telephone model is obtained when all edge delays and switching times are equal to one unit. We investigate the problem of finding the minimum time required to multicast a message from one source to a subset of the processors of size k. The problem is NP-hard even in the basic Telephone model. We present a polynomial time algorithm that approximates the minimum multicast time within a factor of O(log k). Our algorithm improves on the best known approximation factor for the Telephone model by a factor of O (log n/log log k). No approximation algorithms were known for the general model considered in this paper.

UR - https://www.scopus.com/pages/publications/0031645386

UR - https://www.scopus.com/pages/publications/0031645386#tab=citedBy

U2 - 10.1145/276698.276857

DO - 10.1145/276698.276857

M3 - Conference contribution

SN - 9780897919623

T3 - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 448

EP - 453

BT - Proceedings of the 1998 30th Annual ACM Symposium on Theory of Computing

PB - ACM

T2 - 30th Annual ACM Symposium on the Theory of Computing, STOC 1998

Y2 - 23 May 1998 through 26 May 1998

ER -

Multicasting in heterogeneous networks

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this