Achieving the maximum P2P streaming rate using a small number of trees

Joohwan Kim, R. Srikant

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

Abstract

We consider structured peer-to-peer (P2P) networks for distributing streaming data such as real-time video. In such P2P networks, each chunk of data is transferred from the server to all the peers using a data distribution tree. The number of trees and the number of children in each tree contribute to the overhead in the data distribution process. In this paper, we show that the maximum streaming rate can be achieved using O(log N) trees in a network of N peers with homogeneous upload capacities, where each peer has O(1) children in each tree. It is further shown that O(1) trees suffice to achieve a near-maximum streaming rate with heterogeneous upload capacities. The solution involves mapping the tree construction problem to a novel Block Packing problem where two-dimensional blocks are packed into a two-dimensional bin subject to some packing constraints. The block packing problem allows us to visualize network bandwidth usage, thus facilitating a particular way to construct trees which establish the above bounds.

Original languageEnglish (US)
Title of host publication2011 20th International Conference on Computer Communications and Networks, ICCCN 2011 - Proceedings
DOIs
StatePublished - Sep 26 2011
Event2011 20th International Conference on Computer Communications and Networks, ICCCN 2011 - Maui, HI, United States
Duration: Jul 31 2011Aug 4 2011

Publication series

NameProceedings - International Conference on Computer Communications and Networks, ICCCN
ISSN (Print)1095-2055

Other

Other2011 20th International Conference on Computer Communications and Networks, ICCCN 2011
CountryUnited States
CityMaui, HI
Period7/31/118/4/11

Fingerprint

Peer to peer networks
Bins
Servers
Bandwidth

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture
  • Software

Cite this

Kim, J., & Srikant, R. (2011). Achieving the maximum P2P streaming rate using a small number of trees. In 2011 20th International Conference on Computer Communications and Networks, ICCCN 2011 - Proceedings [6005902] (Proceedings - International Conference on Computer Communications and Networks, ICCCN). https://doi.org/10.1109/ICCCN.2011.6005902

Achieving the maximum P2P streaming rate using a small number of trees. / Kim, Joohwan; Srikant, R.

2011 20th International Conference on Computer Communications and Networks, ICCCN 2011 - Proceedings. 2011. 6005902 (Proceedings - International Conference on Computer Communications and Networks, ICCCN).

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

Kim, J & Srikant, R 2011, Achieving the maximum P2P streaming rate using a small number of trees. in 2011 20th International Conference on Computer Communications and Networks, ICCCN 2011 - Proceedings., 6005902, Proceedings - International Conference on Computer Communications and Networks, ICCCN, 2011 20th International Conference on Computer Communications and Networks, ICCCN 2011, Maui, HI, United States, 7/31/11. https://doi.org/10.1109/ICCCN.2011.6005902
Kim J, Srikant R. Achieving the maximum P2P streaming rate using a small number of trees. In 2011 20th International Conference on Computer Communications and Networks, ICCCN 2011 - Proceedings. 2011. 6005902. (Proceedings - International Conference on Computer Communications and Networks, ICCCN). https://doi.org/10.1109/ICCCN.2011.6005902
Kim, Joohwan ; Srikant, R. / Achieving the maximum P2P streaming rate using a small number of trees. 2011 20th International Conference on Computer Communications and Networks, ICCCN 2011 - Proceedings. 2011. (Proceedings - International Conference on Computer Communications and Networks, ICCCN).
@inproceedings{b956035d4e4a4ecfa4c2abb3c530574e,
title = "Achieving the maximum P2P streaming rate using a small number of trees",
abstract = "We consider structured peer-to-peer (P2P) networks for distributing streaming data such as real-time video. In such P2P networks, each chunk of data is transferred from the server to all the peers using a data distribution tree. The number of trees and the number of children in each tree contribute to the overhead in the data distribution process. In this paper, we show that the maximum streaming rate can be achieved using O(log N) trees in a network of N peers with homogeneous upload capacities, where each peer has O(1) children in each tree. It is further shown that O(1) trees suffice to achieve a near-maximum streaming rate with heterogeneous upload capacities. The solution involves mapping the tree construction problem to a novel Block Packing problem where two-dimensional blocks are packed into a two-dimensional bin subject to some packing constraints. The block packing problem allows us to visualize network bandwidth usage, thus facilitating a particular way to construct trees which establish the above bounds.",
author = "Joohwan Kim and R. Srikant",
year = "2011",
month = "9",
day = "26",
doi = "10.1109/ICCCN.2011.6005902",
language = "English (US)",
isbn = "9781457706387",
series = "Proceedings - International Conference on Computer Communications and Networks, ICCCN",
booktitle = "2011 20th International Conference on Computer Communications and Networks, ICCCN 2011 - Proceedings",

}

TY - GEN

T1 - Achieving the maximum P2P streaming rate using a small number of trees

AU - Kim, Joohwan

AU - Srikant, R.

PY - 2011/9/26

Y1 - 2011/9/26

N2 - We consider structured peer-to-peer (P2P) networks for distributing streaming data such as real-time video. In such P2P networks, each chunk of data is transferred from the server to all the peers using a data distribution tree. The number of trees and the number of children in each tree contribute to the overhead in the data distribution process. In this paper, we show that the maximum streaming rate can be achieved using O(log N) trees in a network of N peers with homogeneous upload capacities, where each peer has O(1) children in each tree. It is further shown that O(1) trees suffice to achieve a near-maximum streaming rate with heterogeneous upload capacities. The solution involves mapping the tree construction problem to a novel Block Packing problem where two-dimensional blocks are packed into a two-dimensional bin subject to some packing constraints. The block packing problem allows us to visualize network bandwidth usage, thus facilitating a particular way to construct trees which establish the above bounds.

AB - We consider structured peer-to-peer (P2P) networks for distributing streaming data such as real-time video. In such P2P networks, each chunk of data is transferred from the server to all the peers using a data distribution tree. The number of trees and the number of children in each tree contribute to the overhead in the data distribution process. In this paper, we show that the maximum streaming rate can be achieved using O(log N) trees in a network of N peers with homogeneous upload capacities, where each peer has O(1) children in each tree. It is further shown that O(1) trees suffice to achieve a near-maximum streaming rate with heterogeneous upload capacities. The solution involves mapping the tree construction problem to a novel Block Packing problem where two-dimensional blocks are packed into a two-dimensional bin subject to some packing constraints. The block packing problem allows us to visualize network bandwidth usage, thus facilitating a particular way to construct trees which establish the above bounds.

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

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

U2 - 10.1109/ICCCN.2011.6005902

DO - 10.1109/ICCCN.2011.6005902

M3 - Conference contribution

AN - SCOPUS:80053049821

SN - 9781457706387

T3 - Proceedings - International Conference on Computer Communications and Networks, ICCCN

BT - 2011 20th International Conference on Computer Communications and Networks, ICCCN 2011 - Proceedings

ER -