Monday, March 19th 2007
We study the interaction among users of unstructured file sharing applications
that compete for available network resources (link bandwidth or capacity) by
opening multiple connections on multiple paths so as to accelerate data
transfer. We model this interaction as an unstructured file sharing game. Users
are players and their strategies are the numbers of sessions on available
paths. We consider a general bandwidth sharing framework proposed by Kelly and
Mo and Walrand, with TCP as a special case. Furthermore, we incorporate the
Tit-for-Tat strategy (adopted by BitTorrent networks) into the unstructured
file sharing game to model the competition in which a connection can be set up
only when both users find this connection beneficial. We refer to this as an
overlay formation game. We prove the existence of Nash equilibrium in several
variants of both games, and quantify the losses of efficiency of Nash
equilibria. We find that the loss of efficiency due to selfish behavior is
still unbounded even when the Tit-for-Tat strategy is believed to prevent
selfish behavior.
(Joint with G. Neglia, G. LoPresti, H. Zhang)
We consider the problem of information dissemination in networks using network coding. In particular we focus on situations where random network coding is a suitable transmission strategy, i.e. non-interacting multicasts. In order to combat catastrophic error propagation due to packet transmission error, either due to noise or an adversary setting, we propose the use of codes in q-Johnson schemes. We present the theory of these codes including fast, practical algorithms.
After a brief presentation of the Compact Routing problem (whose goal is to design schemes with the best trade-off between the routing table size per node and the stretch on the route length achieved by scheme), we present a state-of-the-art of the field. This includes the best current upper and lower bounds for the problem and all its variants (undirected & directed graph model, the metric model, etc.) A list of open questions and further directions for this field are presented.
This talk will present an overview/tutorial on benefits network coding can offer over dynamically changing networks, as well as open research directions. Some specific application we will discuss are broadcasting in wireless networks and data collection in sensor networks.
YouTube is the largest video-on-demand (VoD) system deployed for user generated contents. We have collected a vast amount of data from YouTube over a period of several months with the intent to study the characteristics of its content and service. In this talk, I will discuss our findings and its implications on massive scale VoD system design.
In recent years, a large number of DHTs have been proposed. However,
very few of them have been deployed in real-life large scale
systems. An exception is KAD, a DHT based on Kademlia that is part of
the widely used eMule peer-to-peer system, which has more than 1.5
million simultaneous users. We have been studying KAD for some time
and will report our preliminary findings.
We have developed a very fast crawler that allows us to explore part
of the KAD ID space in a few seconds and the entire KAD in a few
minutes. We will discuss findings on node uptimes and node lifetime as
well their geographic distribution and some of the anomalies we found.
We also saw that KAD is vulnerable to some of the well known attacks
such as Sybil and Eclipse attack. We will discuss how these
vulnerabilities can be exploited to mount attacks on the routing and
the data placement scheme.
Node churn in KAD is quite high. To counter churn, the implementation
of the publish and search operations use redundancy and
parallelism. However, this comes at a price: We see that load due to
publish is at least an order of magnitude higher than the load due to
search.
Note: This is joint work with Mortiz Steiner and Taoufik Ennajjary
from Institut Eurecom.