Distributed Selfish Replication

A commonly employed abstraction for studying the object placement problem for the purpose of Internet content distribution is that of a distributed replication group. In this work, the initial model of the distributed replication group of Leff et al. [CHECK END OF SENTENCE] is extended to the case that individual nodes act selfishly, i.e., cater to the optimization of their individual local utilities. Our main contribution is the derivation of equilibrium object placement strategies that 1) can guarantee improved local utilities for all nodes concurrently as compared to the corresponding local utilities under greedy local object placement, 2) do not suffer from potential mistreatment problems, inherent to centralized strategies that aim at optimizing the social utility, and 3) do not require the existence of complete information at all nodes. We develop a baseline computationally efficient algorithm for obtaining the aforementioned equilibrium strategies and then extend it to improve its performance with respect to fairness. Both algorithms are realizable, in practice, through a distributed protocol that requires only a limited exchange of information.     

On the impact of playout scheduling on the performance of peer-to-peer live streaming

In this paper we examine the impact of the adopted playout policy on the performance of P2P live streaming systems. We argue and demonstrate experimentally that (popular) playout policies which permit the divergence of the playout points of different nodes can deteriorate drastically the performance of P2P live streaming. Consequently, we argue in favor of keeping different playout points “near-in-time”, even if this requires sacrificing (dropping) some late frames that could otherwise be rendered (assuming no strict bidirectional interactivity requirements are in place). Such nearly synchronized playout policies create “positive correlation” with respect to the available frames at different playout buffers. Therefore, they increase the number of upstream relay nodes from which a node can pull frames and thus boost the playout quality of both single-parent (tree) and multiple-parent (mesh) systems. On the contrary, diverging playout points reduce the number of upstream parents that can offer a gapless relay of the stream. This is clearly undesirable and should be avoided as it contradicts the fundamental philosophy of P2P systems which is to supplement an original service point with as many additional ones presented by the very own users of the service.     

Intrastream synchronization for continuous media streams: a surveyof playout schedulers

The transmission of real-time streams over best effort networks has been an interesting research area for over a decade. An important objective of the research community has been to devise methods that cope with the variations of the network delay-also called delay jitter-that are an inherent characteristic of best effort networks. Jitter destroys the temporal relationships between periodically transmitted media units, that constitute a real-time media stream, thus hindering the comprehension of the stream. Playout adaptation algorithms undertake the labor of the temporal reconstruction of the stream, which is sometimes referred to as the restoration of its' intrastream synchronization quality. This article surveys the work in the area of playout adaptation, aiming to concisely organize ideas that have been presented in isolation and identify the main points of differentiation among different schemes. The survey, discusses issues related to timing information, handling of late media units, quality evaluation metrics, and adaptation to changing delay conditions     

Bounded Budget Connection (BBC) games or how to make friends and influence people,on a budget

Motivated by applications in social and peer-to-peer networks, we introduce the Bounded Budget Connection (BBC) game and study its pure Nash equilibria. We have a collection of n   players, each with a budget for purchasing links. Each link has a cost and a length. Each node has a preference weight for each node, and its objective is to purchase outgoing links within its budget to minimize its sum of preference-weighted distances to the nodes. We show that determining if a BBC game has pure Nash equilibria is NP-hard. We study (n,k)$(n,k)$-uniform BBC games, where all link costs, lengths, and preferences are equal and every budget equals k  . We show that pure Nash equilibria exist for all (n,k)$(n,k)$-uniform BBC games and all equilibria are essentially fair. We construct a family of equilibria spanning the spectrum from minimum to maximum social cost. We also analyze best-response walks and alternative node objectives.