Eurosys 2006 Scribe - Day 3, Session 1 ====================================== Talk 1 ------ Understanding User Behaviour in Large-Scale Video-on-Demand Systems Presenter: Hongliang Yu Video on demand (VOD) is the future of multi-media networks. It is increasing in popularity world-wide, from 90 million in 2003 to 138 million in 2005. Most systems aren't truly VOD, however, and the systems are still expensive. VOD has a number of properties, including multiple data sources, asynchronous data streams, they are highly interactive and have high bandwidth and I/O requirements. There is not yet a scalable way to deal with these requirements. To design a scalable VOD system you need to know how users use a VOD system. The problem is that most studies extrapolate from rentals in a video store, small scale VOD systems or web streaming. These aren't good models for large VOD systems. This paper presents the results of a study from a deployed system in China. It had twenty-one million sessions, seven thousand movies, 38% of movies were over 90 minutes. The data-rate of the videos was 384kbit. One property of user behaviour, user arrival probability, fits well to a modified Poisson distribution. Also, 37% of user sessions terminate in the first five minutes. There is a large variance in video lengths which makes it difficult to measure sessions on absolute video time. Instead, the metric "normalised sessions length" (NSL) (session length / video length) is used. One surprising finding is that more popular videos do not have longer session lengths. The correlation between popularity and NSL is not so strong. Using the patterns found in the data they can create a model of user behaviour to optimise cache behaviour. Data would suggest that caching the beginning of videos is effective. Higher popularity of a video may not represent an improvement from more caching. Caching is best based on the popularity of individual segments from videos. Further patterns in the data were found. 10% of objects cover 60% of accesses with user interest changing slowly over time. Cache replacement costs are low. Providing a "recommended video list" for users has a high correlation to video usage. Caching according to recommendation is a win, with user interest effectively being "induced". There a number of interesting areas to follow up with future work. Firstly, fully "VCR" studies of user-behaviour where they stop, pause and rewind videos. Secondly, is it feasible to provide a peer-to-peer VOD system? They would also like to deployed optimised caching behaviour based on findings of this work. Questions: Q: Sessions are short. If you start and stop and then restart is that two sessions? A: Yes, two different sessions. You have to restart the movie. Q: Can you fast-forward? A: Yes, but that's a VCR operation which we don't trace yet. Q: That might affect caching behaviour? A: Yes. Q: Have you compared your data with other systems? A: We have the data from other systems, we are still processing it. Talk 2 ====== URICA: Usage-awaRe Interactive Content Adaptation for Mobile Devices Presenter: Iqbal Mohomed There are significant differences in resources in mobile devices. Screen capabilities, battery size etc. Typically viewing desktop content on a mobile device is a very poor experience. Also, downloading data to a mobile device can be expensive. Manual adaptative methods exist to help bridge the gap between desktop and mobile, however, it is very costly with only large websites being able to afford to do this. Typically this still only helps a few devices and content is slow to update. This work looks at automatic adaptation by adding an "adaptive proxy" in the download chain. As an example, an adaptive proxy can transcode images (eg. down-sample them) to save bandwidth. This gives poor results for images with text etc. however. There are many good mechanisms to adapt content, but you need to work out policy what policy controls the mechanisms. You need to take into account the specific content. Machines can't figure this out, but users can. The general idea of URICA is to let users pick the adaptations and then automatically share these with other users. Users can modify "guess" adaptations from the system to get to a level which works with their device. The system then refines its prediction based on this feedback. This is widely applicable to many adaptations. As an example, a server may have a 40kb image in a web page. The adaptive proxy automatically down-samples this to 10kb before returning it to the client. The user may then decide this is too low resolution and ask for a refinement of the image. The adaptive proxy then sends the next quality increment to the client, a 20kb image. Subsequent clients requesting the same image will get the 20kb version. The authors built Chameleon, a URICA prototype. The goal is to reduce bandwidth usage and download latency. This is done by transcoding images into progressive JPEG images. A property of this is that image refinement can be done by shipping a small delta, rather than a whole new better quality image. Users can "tap" an image in their browser to get refinements. Chameleon uses history of refinement for prediction. One study the authors did showed that there is significant "locality" in user preferences when presented with the same task. Variations arise due to task and user preferences. One question is how to predict what the user will want. It is trivial to predict that the user will want minimum bandwidth or minimum number of interactions, however this may not be optimal for latency. You must also factor in user reaction time. Chameleon uses a personal adaptation schedule (PAS) to optimise expected fulfilment time. This factors in bandwidth, user interaction time etc. This means that when more bandwidth is available a higher fidelity image is automatically used. A user study was conducted with people browsing image pages on a device. Users were divided into two groups, one with the same task for all users and the other group with different tasks for users. Prediction mechanisms were disabled to get traces of fidelity levels which satisfy users. No adaptation yields a 1 minute download time. PAS gives a 20 second download time, with the optimal being approximately 18 seconds. The "mean" policy, which does not account for user interaction, provided approximately 25 second download times. The lessons learned from this is that adaptation improves fulfilment time, and PAS is close to optimal. With multiple tasks, PAS is still close to optimal, but the mean profile is worse than naive. The policy needs to take into account bandwidth. With increased bandwidth available, PAS still performs well and mean is worse. This is because PAS can tradeoff time and bandwidth with users specifying the cost of interaction. In summary, URICA provides auto adaptation for a wide range of applications. The system learns from users for other users. Chameleon is an image prototype implementation of URICA. URL: http://adaptive.cs.toronto.edu - There is a demo for firefox on a laptop. Questions Q: You talked about adaptive JPEGs. How do you get rid of advertisements on a small screen? A: We have considered page layout adaptation. We picked an easy prototype with Chameleon. We are working on a firefox plugin to manipulate & learn layout. Q: When you save the document size, eg. 10k, and this is too much, how do you rank it down? A: Currently it's an arbitrary design decision. This is better than no decision right now. We could do it more fine-grained. Q: When using slices, going from quality 1 - 10 is the same as downloading quality 10, not more? A: Yes. Q: What if you have a non-progressive format A: You need to download more Q: Is optimising for that a hard problem? A: Yes Talk 3 ------ Peer Sharing Behaviour in the eDonkey Network, and Implications for the Design of Server-less File Sharing Systems Presenter: F. Le Fessant There has been lots of work on clustering in peer-to-peer systems, and many new algorithms. But does clustering actually exist? Users may have shared interest. This paper provides a workload analysis of eDonkey. What is the real impact of clustering? To measure it, cluster users according to interest. Add local search to this cluster, then check the efficiency on eDonkey. Traces were collected from Dec 9, 2003 to Feb 2, 2004. There were 2.5 million connections to peers. There was a total volume of 350 terrabytes. The network was actively probed with a crawler which output a list of shared files. The crawler was a modified MLDonkey client, which is a multi-network GPL client. The work analysed 3 traces covering 56 days. Ambiguous clients were removed to ensure distinct clients. The trace was extrapolated to fill gaps. The results were roughly linear on a log-log scale. This is similar to the SOSP'03 Kazaa workload, and it is consistent over time. 80% of the clients are "free riders" who don't share. 50% of the remainder share more than 10GB. Mostly small files are shared, however popular files are larger. The study looked at replication evolution. The five most popular files spread very fast and had a long linear decrease -- approximately a one-month half-life. It was found that there is "geo clustering" with 60% of unpopular file replicas existing in one country. They also looked at the semantics of clustering. There are two metrics to measure the degree of clustering. Firstly, overlap between shared files based on the number of files in common. Secondly, the probability of finding another shared file after finding N shared files. This metric has more correlation for unpopular audio, that is audio shared between less than 10 people. Genuine locality may be masked by per generosity and file popularity, however. They removed bias by measuring with and without x% of generous peers, also by comparing to randomised traces. It is found that clustering is clear when the popularity is small. To exploit semantic proximity it may be a good idea to first ask "semantic peers" for a file before doing a full search. An extension of this would be to also ask the peers of peers before searching, to. To evaluate this they ran a simulation and found a 30% hit rate with 5 neighbours. The hit rate was negligible when asking random other nodes. They also found there is only a 10% decrease in this when removing generous peers. The hit rate improves when removing popular files. The conclusion from this is that workloads do in fact show clustering behaviour. A simple strategy for exploiting clustering shows good performance. The traces are available. Questions: Q: How do you determine if two files are the same? A: Checksum Q: You have similar results to the Kazaa work. Is there some difference? will your results apply to them? A: Kazaa is designed for smaller files. We compute replication of files, whereas the Kazaa work looked at traces of downloads. We also have different measures of popularity. Q: Have you considered decoys and spam files? Generous nodes also store lots of junk. People download them. Have you got any idea how the results would change if you took out the junk files? A: People download them, so they are important to traffic. Q: Is is a problem that searching isn't so accurate, ie. you have keyword mismatches etc? A: You still download them. It still should be fast.