Towards scalable network delay minimization

Sourav Medya; Petko Bogdanov; Ambuj Singh

doi:10.1109/ICDM.2016.80

Towards scalable network delay minimization

Sourav Medya, Petko Bogdanov, Ambuj Singh

Management and Organizations

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

6 Scopus citations

Abstract

Reduction of end-To-end network delays is an optimization task with applications in multiple domains. Low delays enable improved information flow in social networks, quick spread of ideas in collaboration networks, low travel times for vehicles on road networks and increased rate of packets in communication networks. Delay reduction can be achieved by both improving the propagation capabilities of individual nodes and adding additional edges in the network. One of the main challenges in such design problems is that the effects of local changes are not independent, and as a consequence, there is a combinatorial search space of possible improvements. Thus, minimizing the cumulative propagation delay requires novel scalable and data-driven approaches. In this paper, we consider the problem of network delay minimization via node upgrades. Although the problem is NPhard, we show that probabilistic approximation for a restricted version can be obtained. We design scalable and high-quality techniques for the general setting based on sampling that are targeted to different models of delay distribution. Our methods scale almost linearly with the graph size and consistently outperform competitors in quality.

Original language	English (US)
Title of host publication	Proceedings - 16th IEEE International Conference on Data Mining, ICDM 2016
Editors	Francesco Bonchi, Josep Domingo-Ferrer, Ricardo Baeza-Yates, Zhi-Hua Zhou, Xindong Wu
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1083-1088
Number of pages	6
ISBN (Electronic)	9781509054725
DOIs	https://doi.org/10.1109/ICDM.2016.80
State	Published - Jul 2 2016
Event	16th IEEE International Conference on Data Mining, ICDM 2016 - Barcelona, Catalonia, Spain Duration: Dec 12 2016 → Dec 15 2016

Publication series

Name	Proceedings - IEEE International Conference on Data Mining, ICDM
Volume	0
ISSN (Print)	1550-4786

Other

Other	16th IEEE International Conference on Data Mining, ICDM 2016
Country/Territory	Spain
City	Barcelona, Catalonia
Period	12/12/16 → 12/15/16

Funding

Research was sponsored by the Army Research Laboratory and accomplished under Cooperative Agreement Number W911NF-09-2-0053 (the ARL Network Science CTA). The views and conclusions in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation here on. We also would like to thank Arlei Silva for helpful discussions.

ASJC Scopus subject areas

General Engineering

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1109/ICDM.2016.80

Cite this

Medya, S., Bogdanov, P., & Singh, A. (2016). Towards scalable network delay minimization. In F. Bonchi, J. Domingo-Ferrer, R. Baeza-Yates, Z.-H. Zhou, & X. Wu (Eds.), Proceedings - 16th IEEE International Conference on Data Mining, ICDM 2016 (pp. 1083-1088). Article 7837953 (Proceedings - IEEE International Conference on Data Mining, ICDM; Vol. 0). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICDM.2016.80

Medya, Sourav ; Bogdanov, Petko ; Singh, Ambuj. / Towards scalable network delay minimization. Proceedings - 16th IEEE International Conference on Data Mining, ICDM 2016. editor / Francesco Bonchi ; Josep Domingo-Ferrer ; Ricardo Baeza-Yates ; Zhi-Hua Zhou ; Xindong Wu. Institute of Electrical and Electronics Engineers Inc., 2016. pp. 1083-1088 (Proceedings - IEEE International Conference on Data Mining, ICDM).

@inproceedings{5afc068e78d5405ba55e14f421fe4646,

title = "Towards scalable network delay minimization",

abstract = "Reduction of end-To-end network delays is an optimization task with applications in multiple domains. Low delays enable improved information flow in social networks, quick spread of ideas in collaboration networks, low travel times for vehicles on road networks and increased rate of packets in communication networks. Delay reduction can be achieved by both improving the propagation capabilities of individual nodes and adding additional edges in the network. One of the main challenges in such design problems is that the effects of local changes are not independent, and as a consequence, there is a combinatorial search space of possible improvements. Thus, minimizing the cumulative propagation delay requires novel scalable and data-driven approaches. In this paper, we consider the problem of network delay minimization via node upgrades. Although the problem is NPhard, we show that probabilistic approximation for a restricted version can be obtained. We design scalable and high-quality techniques for the general setting based on sampling that are targeted to different models of delay distribution. Our methods scale almost linearly with the graph size and consistently outperform competitors in quality.",

author = "Sourav Medya and Petko Bogdanov and Ambuj Singh",

note = "Funding Information: Research was sponsored by the Army Research Laboratory and accomplished under Cooperative Agreement Number W911NF-09-2-0053 (the ARL Network Science CTA). The views and conclusions in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation here on. We also would like to thank Arlei Silva for helpful discussions. Publisher Copyright: {\textcopyright} 2016 IEEE.; 16th IEEE International Conference on Data Mining, ICDM 2016 ; Conference date: 12-12-2016 Through 15-12-2016",

year = "2016",

month = jul,

day = "2",

doi = "10.1109/ICDM.2016.80",

language = "English (US)",

series = "Proceedings - IEEE International Conference on Data Mining, ICDM",

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

pages = "1083--1088",

editor = "Francesco Bonchi and Josep Domingo-Ferrer and Ricardo Baeza-Yates and Zhi-Hua Zhou and Xindong Wu",

booktitle = "Proceedings - 16th IEEE International Conference on Data Mining, ICDM 2016",

address = "United States",

}

Medya, S, Bogdanov, P & Singh, A 2016, Towards scalable network delay minimization. in F Bonchi, J Domingo-Ferrer, R Baeza-Yates, Z-H Zhou & X Wu (eds), Proceedings - 16th IEEE International Conference on Data Mining, ICDM 2016., 7837953, Proceedings - IEEE International Conference on Data Mining, ICDM, vol. 0, Institute of Electrical and Electronics Engineers Inc., pp. 1083-1088, 16th IEEE International Conference on Data Mining, ICDM 2016, Barcelona, Catalonia, Spain, 12/12/16. https://doi.org/10.1109/ICDM.2016.80

Towards scalable network delay minimization. / Medya, Sourav; Bogdanov, Petko; Singh, Ambuj.
Proceedings - 16th IEEE International Conference on Data Mining, ICDM 2016. ed. / Francesco Bonchi; Josep Domingo-Ferrer; Ricardo Baeza-Yates; Zhi-Hua Zhou; Xindong Wu. Institute of Electrical and Electronics Engineers Inc., 2016. p. 1083-1088 7837953 (Proceedings - IEEE International Conference on Data Mining, ICDM; Vol. 0).

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

TY - GEN

T1 - Towards scalable network delay minimization

AU - Medya, Sourav

AU - Bogdanov, Petko

AU - Singh, Ambuj

N1 - Funding Information: Research was sponsored by the Army Research Laboratory and accomplished under Cooperative Agreement Number W911NF-09-2-0053 (the ARL Network Science CTA). The views and conclusions in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation here on. We also would like to thank Arlei Silva for helpful discussions. Publisher Copyright: © 2016 IEEE.

PY - 2016/7/2

Y1 - 2016/7/2

N2 - Reduction of end-To-end network delays is an optimization task with applications in multiple domains. Low delays enable improved information flow in social networks, quick spread of ideas in collaboration networks, low travel times for vehicles on road networks and increased rate of packets in communication networks. Delay reduction can be achieved by both improving the propagation capabilities of individual nodes and adding additional edges in the network. One of the main challenges in such design problems is that the effects of local changes are not independent, and as a consequence, there is a combinatorial search space of possible improvements. Thus, minimizing the cumulative propagation delay requires novel scalable and data-driven approaches. In this paper, we consider the problem of network delay minimization via node upgrades. Although the problem is NPhard, we show that probabilistic approximation for a restricted version can be obtained. We design scalable and high-quality techniques for the general setting based on sampling that are targeted to different models of delay distribution. Our methods scale almost linearly with the graph size and consistently outperform competitors in quality.

AB - Reduction of end-To-end network delays is an optimization task with applications in multiple domains. Low delays enable improved information flow in social networks, quick spread of ideas in collaboration networks, low travel times for vehicles on road networks and increased rate of packets in communication networks. Delay reduction can be achieved by both improving the propagation capabilities of individual nodes and adding additional edges in the network. One of the main challenges in such design problems is that the effects of local changes are not independent, and as a consequence, there is a combinatorial search space of possible improvements. Thus, minimizing the cumulative propagation delay requires novel scalable and data-driven approaches. In this paper, we consider the problem of network delay minimization via node upgrades. Although the problem is NPhard, we show that probabilistic approximation for a restricted version can be obtained. We design scalable and high-quality techniques for the general setting based on sampling that are targeted to different models of delay distribution. Our methods scale almost linearly with the graph size and consistently outperform competitors in quality.

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

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

U2 - 10.1109/ICDM.2016.80

DO - 10.1109/ICDM.2016.80

M3 - Conference contribution

AN - SCOPUS:85014561140

T3 - Proceedings - IEEE International Conference on Data Mining, ICDM

SP - 1083

EP - 1088

BT - Proceedings - 16th IEEE International Conference on Data Mining, ICDM 2016

A2 - Bonchi, Francesco

A2 - Domingo-Ferrer, Josep

A2 - Baeza-Yates, Ricardo

A2 - Zhou, Zhi-Hua

A2 - Wu, Xindong

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 16th IEEE International Conference on Data Mining, ICDM 2016

Y2 - 12 December 2016 through 15 December 2016

ER -

Medya S, Bogdanov P, Singh A. Towards scalable network delay minimization. In Bonchi F, Domingo-Ferrer J, Baeza-Yates R, Zhou ZH, Wu X, editors, Proceedings - 16th IEEE International Conference on Data Mining, ICDM 2016. Institute of Electrical and Electronics Engineers Inc. 2016. p. 1083-1088. 7837953. (Proceedings - IEEE International Conference on Data Mining, ICDM). doi: 10.1109/ICDM.2016.80

Towards scalable network delay minimization

Abstract

Publication series

Other

Funding

ASJC Scopus subject areas

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this