A coalition formation game in partition form for peer-to-peer file sharing networks

Walid Saad, Zhu Han, M Tamer Basar, Merouane Debbah, Are Hjørungnes

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In current peer-to-peer file sharing networks, a large number of peers with heterogeneous connections simultaneously seek to download resources, e.g., files or file fragments, from a common seed at the time these resources become available, which incurs high download delays on the different peers. Unlike existing literature which mainly focused on cooperative strategies for data exchange between different peers after all the peers have already acquired their resources, in this paper, we study the cooperation possibilities among a number of peers seeking to download, concurrently, a number of resources at the time the availability of the resources is initially announced at a common seed. We model the problem as a coalitional game in partition form and we propose an algorithm for coalition formation among the peers. The proposed algorithm enables the peers to take autonomous decisions to join or leave a coalition while minimizing their average download delay. We show that, by using the proposed algorithm, a Nash-stable partition composed of coalitions of peers is formed. Within every coalition, the peers distribute their download requests between the seed and the cooperating partners in a way to minimize the total average delay incurred on the coalition. Analytically, we study the 2-peer scenario and derive the optimal download request distribution policies. Simulation results show that, using the proposed coalition formation game, the peers can improve their average download delay per peer of up to 99.6% compared to the non-cooperative approach for the case with N = 15 peers.

Original languageEnglish (US)
Title of host publication2010 IEEE Global Telecommunications Conference, GLOBECOM 2010
DOIs
StatePublished - Dec 1 2010
Event53rd IEEE Global Communications Conference, GLOBECOM 2010 - Miami, FL, United States
Duration: Dec 6 2010Dec 10 2010

Publication series

NameGLOBECOM - IEEE Global Telecommunications Conference

Other

Other53rd IEEE Global Communications Conference, GLOBECOM 2010
CountryUnited States
CityMiami, FL
Period12/6/1012/10/10

Fingerprint

Seed
Electronic data interchange
Availability

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Cite this

Saad, W., Han, Z., Basar, M. T., Debbah, M., & Hjørungnes, A. (2010). A coalition formation game in partition form for peer-to-peer file sharing networks. In 2010 IEEE Global Telecommunications Conference, GLOBECOM 2010 [5683136] (GLOBECOM - IEEE Global Telecommunications Conference). https://doi.org/10.1109/GLOCOM.2010.5683136

A coalition formation game in partition form for peer-to-peer file sharing networks. / Saad, Walid; Han, Zhu; Basar, M Tamer; Debbah, Merouane; Hjørungnes, Are.

2010 IEEE Global Telecommunications Conference, GLOBECOM 2010. 2010. 5683136 (GLOBECOM - IEEE Global Telecommunications Conference).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Saad, W, Han, Z, Basar, MT, Debbah, M & Hjørungnes, A 2010, A coalition formation game in partition form for peer-to-peer file sharing networks. in 2010 IEEE Global Telecommunications Conference, GLOBECOM 2010., 5683136, GLOBECOM - IEEE Global Telecommunications Conference, 53rd IEEE Global Communications Conference, GLOBECOM 2010, Miami, FL, United States, 12/6/10. https://doi.org/10.1109/GLOCOM.2010.5683136
Saad W, Han Z, Basar MT, Debbah M, Hjørungnes A. A coalition formation game in partition form for peer-to-peer file sharing networks. In 2010 IEEE Global Telecommunications Conference, GLOBECOM 2010. 2010. 5683136. (GLOBECOM - IEEE Global Telecommunications Conference). https://doi.org/10.1109/GLOCOM.2010.5683136
Saad, Walid ; Han, Zhu ; Basar, M Tamer ; Debbah, Merouane ; Hjørungnes, Are. / A coalition formation game in partition form for peer-to-peer file sharing networks. 2010 IEEE Global Telecommunications Conference, GLOBECOM 2010. 2010. (GLOBECOM - IEEE Global Telecommunications Conference).
@inproceedings{a4236b5b5e3e4a99a25bcdc85c50ad89,
title = "A coalition formation game in partition form for peer-to-peer file sharing networks",
abstract = "In current peer-to-peer file sharing networks, a large number of peers with heterogeneous connections simultaneously seek to download resources, e.g., files or file fragments, from a common seed at the time these resources become available, which incurs high download delays on the different peers. Unlike existing literature which mainly focused on cooperative strategies for data exchange between different peers after all the peers have already acquired their resources, in this paper, we study the cooperation possibilities among a number of peers seeking to download, concurrently, a number of resources at the time the availability of the resources is initially announced at a common seed. We model the problem as a coalitional game in partition form and we propose an algorithm for coalition formation among the peers. The proposed algorithm enables the peers to take autonomous decisions to join or leave a coalition while minimizing their average download delay. We show that, by using the proposed algorithm, a Nash-stable partition composed of coalitions of peers is formed. Within every coalition, the peers distribute their download requests between the seed and the cooperating partners in a way to minimize the total average delay incurred on the coalition. Analytically, we study the 2-peer scenario and derive the optimal download request distribution policies. Simulation results show that, using the proposed coalition formation game, the peers can improve their average download delay per peer of up to 99.6{\%} compared to the non-cooperative approach for the case with N = 15 peers.",
author = "Walid Saad and Zhu Han and Basar, {M Tamer} and Merouane Debbah and Are Hj{\o}rungnes",
year = "2010",
month = "12",
day = "1",
doi = "10.1109/GLOCOM.2010.5683136",
language = "English (US)",
isbn = "9781424456383",
series = "GLOBECOM - IEEE Global Telecommunications Conference",
booktitle = "2010 IEEE Global Telecommunications Conference, GLOBECOM 2010",

}

TY - GEN

T1 - A coalition formation game in partition form for peer-to-peer file sharing networks

AU - Saad, Walid

AU - Han, Zhu

AU - Basar, M Tamer

AU - Debbah, Merouane

AU - Hjørungnes, Are

PY - 2010/12/1

Y1 - 2010/12/1

N2 - In current peer-to-peer file sharing networks, a large number of peers with heterogeneous connections simultaneously seek to download resources, e.g., files or file fragments, from a common seed at the time these resources become available, which incurs high download delays on the different peers. Unlike existing literature which mainly focused on cooperative strategies for data exchange between different peers after all the peers have already acquired their resources, in this paper, we study the cooperation possibilities among a number of peers seeking to download, concurrently, a number of resources at the time the availability of the resources is initially announced at a common seed. We model the problem as a coalitional game in partition form and we propose an algorithm for coalition formation among the peers. The proposed algorithm enables the peers to take autonomous decisions to join or leave a coalition while minimizing their average download delay. We show that, by using the proposed algorithm, a Nash-stable partition composed of coalitions of peers is formed. Within every coalition, the peers distribute their download requests between the seed and the cooperating partners in a way to minimize the total average delay incurred on the coalition. Analytically, we study the 2-peer scenario and derive the optimal download request distribution policies. Simulation results show that, using the proposed coalition formation game, the peers can improve their average download delay per peer of up to 99.6% compared to the non-cooperative approach for the case with N = 15 peers.

AB - In current peer-to-peer file sharing networks, a large number of peers with heterogeneous connections simultaneously seek to download resources, e.g., files or file fragments, from a common seed at the time these resources become available, which incurs high download delays on the different peers. Unlike existing literature which mainly focused on cooperative strategies for data exchange between different peers after all the peers have already acquired their resources, in this paper, we study the cooperation possibilities among a number of peers seeking to download, concurrently, a number of resources at the time the availability of the resources is initially announced at a common seed. We model the problem as a coalitional game in partition form and we propose an algorithm for coalition formation among the peers. The proposed algorithm enables the peers to take autonomous decisions to join or leave a coalition while minimizing their average download delay. We show that, by using the proposed algorithm, a Nash-stable partition composed of coalitions of peers is formed. Within every coalition, the peers distribute their download requests between the seed and the cooperating partners in a way to minimize the total average delay incurred on the coalition. Analytically, we study the 2-peer scenario and derive the optimal download request distribution policies. Simulation results show that, using the proposed coalition formation game, the peers can improve their average download delay per peer of up to 99.6% compared to the non-cooperative approach for the case with N = 15 peers.

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

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

U2 - 10.1109/GLOCOM.2010.5683136

DO - 10.1109/GLOCOM.2010.5683136

M3 - Conference contribution

AN - SCOPUS:79551649626

SN - 9781424456383

T3 - GLOBECOM - IEEE Global Telecommunications Conference

BT - 2010 IEEE Global Telecommunications Conference, GLOBECOM 2010

ER -