Converging an overlay network to a Gradient topology

Håkan Terelius; Guodong Shi; Jim Dowling; Amir Payberah; Ather Gattami; Karl Henrik Johansson

doi:10.1109/CDC.2011.6161194

Converging an overlay network to a Gradient topology

Håkan Terelius^*, Guodong Shi, Jim Dowling, Amir Payberah, Ather Gattami, Karl Henrik Johansson

^*Corresponding author for this work

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

2 Citations (Scopus)

Abstract

In this paper, we investigate the topology convergence problem for the gossip-based Gradient overlay network. In an overlay network where each node has a local utility value, a Gradient overlay network is characterized by the properties that each node has a set of neighbors containing higher utility values, such that paths of increasing utilities emerge in the network topology. The Gradient overlay network is built using gossiping and a preference function that samples from nodes using a uniform random peer sampling service. We analyze it using tools from matrix analysis, and we prove both the necessary and sufficient conditions for convergence to a complete gradient structure, as well as estimating the convergence time. Finally, we show in simulations the potential of the Gradient overlay, by building a more efficient live-streaming peer-to-peer (P2P) system than one built using uniform random peer sampling.

Original language	English
Title of host publication	2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	7230-7235
Number of pages	6
ISBN (Print)	9781612848006
DOIs	https://doi.org/10.1109/CDC.2011.6161194
Publication status	Published - 2011
Externally published	Yes
Event	2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011 - Orlando, FL, United States Duration: 12 Dec 2011 → 15 Dec 2011

Publication series

Name	Proceedings of the IEEE Conference on Decision and Control
ISSN (Print)	0743-1546
ISSN (Electronic)	2576-2370

Conference

Conference	2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011
Country/Territory	United States
City	Orlando, FL
Period	12/12/11 → 15/12/11

Access to Document

10.1109/CDC.2011.6161194

Cite this

Terelius, H., Shi, G., Dowling, J., Payberah, A., Gattami, A., & Johansson, K. H. (2011). Converging an overlay network to a Gradient topology. In 2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011 (pp. 7230-7235). Article 6161194 (Proceedings of the IEEE Conference on Decision and Control). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC.2011.6161194

@inproceedings{55cf81f032e74e00b6fd384f1d2b7768,

title = "Converging an overlay network to a Gradient topology",

abstract = "In this paper, we investigate the topology convergence problem for the gossip-based Gradient overlay network. In an overlay network where each node has a local utility value, a Gradient overlay network is characterized by the properties that each node has a set of neighbors containing higher utility values, such that paths of increasing utilities emerge in the network topology. The Gradient overlay network is built using gossiping and a preference function that samples from nodes using a uniform random peer sampling service. We analyze it using tools from matrix analysis, and we prove both the necessary and sufficient conditions for convergence to a complete gradient structure, as well as estimating the convergence time. Finally, we show in simulations the potential of the Gradient overlay, by building a more efficient live-streaming peer-to-peer (P2P) system than one built using uniform random peer sampling.",

keywords = "Overlay networks, gossiping, gradient topology, topology convergence",

author = "H{\aa}kan Terelius and Guodong Shi and Jim Dowling and Amir Payberah and Ather Gattami and Johansson, {Karl Henrik}",

year = "2011",

doi = "10.1109/CDC.2011.6161194",

language = "English",

isbn = "9781612848006",

series = "Proceedings of the IEEE Conference on Decision and Control",

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

pages = "7230--7235",

booktitle = "2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011",

address = "United States",

note = "2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011 ; Conference date: 12-12-2011 Through 15-12-2011",

}

Terelius, H, Shi, G, Dowling, J, Payberah, A, Gattami, A & Johansson, KH 2011, Converging an overlay network to a Gradient topology. in 2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011., 6161194, Proceedings of the IEEE Conference on Decision and Control, Institute of Electrical and Electronics Engineers Inc., pp. 7230-7235, 2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011, Orlando, FL, United States, 12/12/11. https://doi.org/10.1109/CDC.2011.6161194

Converging an overlay network to a Gradient topology. / Terelius, Håkan; Shi, Guodong; Dowling, Jim et al.
2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011. Institute of Electrical and Electronics Engineers Inc., 2011. p. 7230-7235 6161194 (Proceedings of the IEEE Conference on Decision and Control).

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

TY - GEN

T1 - Converging an overlay network to a Gradient topology

AU - Terelius, Håkan

AU - Shi, Guodong

AU - Dowling, Jim

AU - Payberah, Amir

AU - Gattami, Ather

AU - Johansson, Karl Henrik

PY - 2011

Y1 - 2011

N2 - In this paper, we investigate the topology convergence problem for the gossip-based Gradient overlay network. In an overlay network where each node has a local utility value, a Gradient overlay network is characterized by the properties that each node has a set of neighbors containing higher utility values, such that paths of increasing utilities emerge in the network topology. The Gradient overlay network is built using gossiping and a preference function that samples from nodes using a uniform random peer sampling service. We analyze it using tools from matrix analysis, and we prove both the necessary and sufficient conditions for convergence to a complete gradient structure, as well as estimating the convergence time. Finally, we show in simulations the potential of the Gradient overlay, by building a more efficient live-streaming peer-to-peer (P2P) system than one built using uniform random peer sampling.

AB - In this paper, we investigate the topology convergence problem for the gossip-based Gradient overlay network. In an overlay network where each node has a local utility value, a Gradient overlay network is characterized by the properties that each node has a set of neighbors containing higher utility values, such that paths of increasing utilities emerge in the network topology. The Gradient overlay network is built using gossiping and a preference function that samples from nodes using a uniform random peer sampling service. We analyze it using tools from matrix analysis, and we prove both the necessary and sufficient conditions for convergence to a complete gradient structure, as well as estimating the convergence time. Finally, we show in simulations the potential of the Gradient overlay, by building a more efficient live-streaming peer-to-peer (P2P) system than one built using uniform random peer sampling.

KW - Overlay networks

KW - gossiping

KW - gradient topology

KW - topology convergence

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

U2 - 10.1109/CDC.2011.6161194

DO - 10.1109/CDC.2011.6161194

M3 - Conference contribution

SN - 9781612848006

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 7230

EP - 7235

BT - 2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011

Y2 - 12 December 2011 through 15 December 2011

ER -

Terelius H, Shi G, Dowling J, Payberah A, Gattami A, Johansson KH. Converging an overlay network to a Gradient topology. In 2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011. Institute of Electrical and Electronics Engineers Inc. 2011. p. 7230-7235. 6161194. (Proceedings of the IEEE Conference on Decision and Control). doi: 10.1109/CDC.2011.6161194

Converging an overlay network to a Gradient topology

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this