Performance tradeoffs in structured peer to peer streaming
| Autor: | Samir Khuller, Yuan Yao, Leana Golubchik, Alix L. H. Chow |
|---|---|
| Rok vydání: | 2012 |
| Předmět: |
Sequence
Computer Networks and Communications Computer science Network packet business.industry Node (networking) 0102 computer and information sciences Construct (python library) Peer-to-peer computer.software_genre 01 natural sciences Theoretical Computer Science 010101 applied mathematics 010201 computation theory & mathematics Artificial Intelligence Hardware and Architecture Cluster (physics) Hypercube 0101 mathematics business Protocol (object-oriented programming) computer Software Computer network |
| Zdroj: | Journal of Parallel and Distributed Computing. 72:323-337 |
| ISSN: | 0743-7315 |
| Popis: | We consider the following basic question: a source node wishes to stream an ordered sequence of packets to a collection of receivers, which are in K clusters. A node may send a packet to another node in its own cluster in one time step and to a node in a different cluster in T"c time steps (T"c>1). Each cluster has two special nodes. We assume that the source and the special nodes in each cluster have a higher capacity and thus can send multiple packets at each step, while all other nodes can both send and receive a packet at each step. We construct two (intra-cluster) data communication schemes, one based on multi-trees (using a collection of d-ary interior-disjoint trees) and the other based on hypercubes. The multi-tree scheme sustains streaming within a cluster with O(dlogN) maximum playback delay and O(dlogN) size buffers, while communicating with O(d) neighbors, where N is the maximum size of any cluster. We also show that this protocol is optimal when d=2 or 3. The hypercube scheme sustains streaming within a cluster, with O(log^2(N)) maximum playback delay and O(1) size buffers, while communicating with O(log(N)) neighbors, for arbitrary N. In addition, we extend our multi-tree scheme to work when receivers depart and arrive over time. We also evaluate our dynamic schemes using simulations. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect