On the Multicast Capacity of Full-Duplex 1-2-1 Networks

Yahya H. Ezzeldin; Martina Cardone; Christina Fragouli; Giuseppe Caire

doi:10.1109/ISIT.2019.8849692

On the Multicast Capacity of Full-Duplex 1-2-1 Networks

Yahya H. Ezzeldin, Martina Cardone, Christina Fragouli, Giuseppe Caire

Electrical and Computer Engineering

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

3 Scopus citations

Abstract

This paper studies the multicast capacity of full-duplex 1-2-1 networks. In this model, two nodes can communicate only if they point "beams" at each other; otherwise, no signal can be exchanged. The main result of this paper is that the approximate multicast capacity can be computed by solving a linear program in the activation times of links connecting pairs of nodes. This linear program has two appealing features: (i) it can be solved in polynomial-time in the number of nodes; (ii) it allows to efficiently find a network schedule optimal for the approximate capacity. Additionally, the relation between the approximate multicast capacity and the minimum approximate unicast capacity is studied. It is shown that the ratio between these two values is not universally equal to one, but it depends on the number of destinations in the network, as well as graph-theoretic properties of the network.

Original language	English (US)
Title of host publication	2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	465-469
Number of pages	5
ISBN (Electronic)	9781538692912
DOIs	https://doi.org/10.1109/ISIT.2019.8849692
State	Published - Jul 2019
Event	2019 IEEE International Symposium on Information Theory, ISIT 2019 - Paris, France Duration: Jul 7 2019 → Jul 12 2019

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
Volume	2019-July
ISSN (Print)	2157-8095

Conference

Conference	2019 IEEE International Symposium on Information Theory, ISIT 2019
Country/Territory	France
City	Paris
Period	7/7/19 → 7/12/19

Bibliographical note

Funding Information:
Y. H. Ezzeldin and C. Fragouli were supported in part by NSF awards 1514531, 1824568 and UC-NL grant LFR-18-548554. 1Constant gap refers to a quantity that is independent of the channel coefficients and operating SNR, and solely depends on the number of nodes.

Funding Information:
Y. H. Ezzeldin and C. Fragouli were supported in part by NSF awards 1514531, 1824568 and UC-NL grant LFR-18-548554.

Publisher Copyright:
© 2019 IEEE.

Access

10.1109/ISIT.2019.8849692

OpenUrl availability

Full text

Cite this

Ezzeldin, Y. H., Cardone, M., Fragouli, C., & Caire, G. (2019). On the Multicast Capacity of Full-Duplex 1-2-1 Networks. In 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings (pp. 465-469). Article 8849692 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2019-July). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2019.8849692

On the Multicast Capacity of Full-Duplex 1-2-1 Networks. / Ezzeldin, Yahya H.; Cardone, Martina; Fragouli, Christina et al.
2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2019. p. 465-469 8849692 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2019-July).

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

Ezzeldin, YH, Cardone, M, Fragouli, C & Caire, G 2019, On the Multicast Capacity of Full-Duplex 1-2-1 Networks. in 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings., 8849692, IEEE International Symposium on Information Theory - Proceedings, vol. 2019-July, Institute of Electrical and Electronics Engineers Inc., pp. 465-469, 2019 IEEE International Symposium on Information Theory, ISIT 2019, Paris, France, 7/7/19. https://doi.org/10.1109/ISIT.2019.8849692

@inproceedings{5a498da6b9994cc8870f7cbb6698abc5,

title = "On the Multicast Capacity of Full-Duplex 1-2-1 Networks",

abstract = "This paper studies the multicast capacity of full-duplex 1-2-1 networks. In this model, two nodes can communicate only if they point {"}beams{"} at each other; otherwise, no signal can be exchanged. The main result of this paper is that the approximate multicast capacity can be computed by solving a linear program in the activation times of links connecting pairs of nodes. This linear program has two appealing features: (i) it can be solved in polynomial-time in the number of nodes; (ii) it allows to efficiently find a network schedule optimal for the approximate capacity. Additionally, the relation between the approximate multicast capacity and the minimum approximate unicast capacity is studied. It is shown that the ratio between these two values is not universally equal to one, but it depends on the number of destinations in the network, as well as graph-theoretic properties of the network.",

author = "Ezzeldin, {Yahya H.} and Martina Cardone and Christina Fragouli and Giuseppe Caire",

note = "Funding Information: Y. H. Ezzeldin and C. Fragouli were supported in part by NSF awards 1514531, 1824568 and UC-NL grant LFR-18-548554. 1Constant gap refers to a quantity that is independent of the channel coefficients and operating SNR, and solely depends on the number of nodes. Funding Information: Y. H. Ezzeldin and C. Fragouli were supported in part by NSF awards 1514531, 1824568 and UC-NL grant LFR-18-548554. Publisher Copyright: {\textcopyright} 2019 IEEE.; 2019 IEEE International Symposium on Information Theory, ISIT 2019 ; Conference date: 07-07-2019 Through 12-07-2019",

year = "2019",

month = jul,

doi = "10.1109/ISIT.2019.8849692",

language = "English (US)",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "465--469",

booktitle = "2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings",

}

TY - GEN

T1 - On the Multicast Capacity of Full-Duplex 1-2-1 Networks

AU - Ezzeldin, Yahya H.

AU - Cardone, Martina

AU - Fragouli, Christina

AU - Caire, Giuseppe

N1 - Funding Information: Y. H. Ezzeldin and C. Fragouli were supported in part by NSF awards 1514531, 1824568 and UC-NL grant LFR-18-548554. 1Constant gap refers to a quantity that is independent of the channel coefficients and operating SNR, and solely depends on the number of nodes. Funding Information: Y. H. Ezzeldin and C. Fragouli were supported in part by NSF awards 1514531, 1824568 and UC-NL grant LFR-18-548554. Publisher Copyright: © 2019 IEEE.

PY - 2019/7

Y1 - 2019/7

N2 - This paper studies the multicast capacity of full-duplex 1-2-1 networks. In this model, two nodes can communicate only if they point "beams" at each other; otherwise, no signal can be exchanged. The main result of this paper is that the approximate multicast capacity can be computed by solving a linear program in the activation times of links connecting pairs of nodes. This linear program has two appealing features: (i) it can be solved in polynomial-time in the number of nodes; (ii) it allows to efficiently find a network schedule optimal for the approximate capacity. Additionally, the relation between the approximate multicast capacity and the minimum approximate unicast capacity is studied. It is shown that the ratio between these two values is not universally equal to one, but it depends on the number of destinations in the network, as well as graph-theoretic properties of the network.

AB - This paper studies the multicast capacity of full-duplex 1-2-1 networks. In this model, two nodes can communicate only if they point "beams" at each other; otherwise, no signal can be exchanged. The main result of this paper is that the approximate multicast capacity can be computed by solving a linear program in the activation times of links connecting pairs of nodes. This linear program has two appealing features: (i) it can be solved in polynomial-time in the number of nodes; (ii) it allows to efficiently find a network schedule optimal for the approximate capacity. Additionally, the relation between the approximate multicast capacity and the minimum approximate unicast capacity is studied. It is shown that the ratio between these two values is not universally equal to one, but it depends on the number of destinations in the network, as well as graph-theoretic properties of the network.

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

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

U2 - 10.1109/ISIT.2019.8849692

DO - 10.1109/ISIT.2019.8849692

M3 - Conference contribution

AN - SCOPUS:85073153223

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 465

EP - 469

BT - 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2019 IEEE International Symposium on Information Theory, ISIT 2019

Y2 - 7 July 2019 through 12 July 2019

ER -

On the Multicast Capacity of Full-Duplex 1-2-1 Networks

Abstract

Publication series

Conference

Bibliographical note

Access

OpenUrl availability

Other files and links

Fingerprint

Cite this