| Speaker : | Mathieu Leconte |
| INRIA | |
| Date: | 06/06/2012 |
| Time: | 2:00 pm - 3:00 pm |
| Location: | LINCS Meeting Room 40 |
Abstract
ACM SIGMETRICS’12 Preview Talk
This paper considers large scale distributed content serviceplatforms, such as peer-to-peer video-on-demand systems.Such systems feature two basic resources, namely storageand bandwidth. Their efficiency critically depends on twofactors: (i) content replication within servers, and (ii) howincoming service requests are matched to servers holding requestedcontent. To inform the corresponding design choices,we make the following contributions.We first show that, for underloaded systems, so-called pro-portional content placement with a simple greedy strategyfor matching requests to servers ensures full system efficiencyprovided storage size grows logarithmically with the systemsize. However, for constant storage size, this strategy undergoesa phase transition with severe loss of efficiency assystem load approaches criticality.To better understand the role of the matching strategy inthis performance degradation, we characterize the asymptoticsystem efficiency under an optimal matching policy.Our analysis shows that -in contrast to greedy matching-optimal matching incurs an inefficiency that is exponentiallysmall in the server storage size, even at critical systemloads. It further allows a characterization of content replicationpolicies that minimize the inefficiency. These optimalpolicies, which differ markedly from proportional placement,have a simple structure which makes them implementablein practice.On the methodological side, our analysis of matching performanceuses the theory of local weak limits of randomgraphs, and highlights a novel characterization of matchingnumbers in bipartite graphs, which may both be of independentinterest.
Joint work by Mathieu Leconte (Technicolor РINRIA), Marc Lelarge (INRIA РEcole Normale Sup̩rieure) and Laurent Massouli̩ (Technicolor)