Roberto Roverso
email: roberto@peerialism.com

Sameh El-Ansary

Seif Haridi
email: haridi@kth.se

SmoothCache: HTTP-Live Streaming Goes Peer-To-Peer

Keywords: HTTP-Live streaming, peer-to-peer, caching, CDN

In this paper, we present SmoothCache, a peer-to-peer live video streaming (P2PLS) system. The novelty of SmoothCache is threefold: i) It is the first P2PLS system that is built to support the relativelynew approach of using HTTP as the transport protocol for live content, ii) The system supports both single and multi-bitrate streaming modes of operation, and iii) In Smoothcache, we make use of recent advances in application-layer dynamic congestion control to manage priorities of transfers according to their urgency. We start by explaining why the HTTP live streaming semantics render many of the existing assumptions used in P2PLS protocols obsolete. Afterwards, we present our design starting with a baseline P2P caching model. We, then, show a number of optimizations related to aspects such as neighborhood management, uploader selection and proactive caching. Finally, we present our evaluation conducted on a real yet instrumented test network. Our results show that we can achieve substantial traffic savings on the source of the stream without major degradation in user experience.

Introduction

Peer-to-peer live streaming (P2PLS) is a problem in the Peer-To-Peer (P2P) networking field that has been tackled for quite some time on both the academic and industrial fronts. The typical goal is to utilize the upload bandwidth of hosts consuming a certain live content to offload the bandwidth of the broadcasting origin. On the industrial front, we find successful large deployments where knowledge about their technical approaches is rather limited. Exceptions include systems described by their authors like Coolstreaming [START_REF] Zhang | CoolStreaming/DONet: a data-driven overlay network for peer-to-peer live media streaming[END_REF] or inferred by reverse engineering like PPlive [START_REF] Hei | Insights into PPLive: A Measurement Study of a Large-Scale P2P IPTV System[END_REF] and TVAnts [START_REF] Silverston | P2P IPTV measurement: a case study of TVants[END_REF]. On the academic front, there have been several attempts to try to estimate theoretical limits in terms of optimality of bandwidth utilization [START_REF] Guo | AQCS: adaptive queue-based chunk scheduling for P2P live streaming[END_REF] [START_REF] Massoulie | Randomized Decentralized Broadcasting Algorithms[END_REF] or delay [START_REF] Zhang | Understanding the Power of Pull-Based Streaming Protocol: Can We Do Better? In: Selected Areas in Communications[END_REF].

Traditionally, HTTP has been utilized for progressive download streaming, championed by popular Video-On-Demand (VoD) solutions such as Netflix [1] and Apple's iTunes movie store. However, lately, adaptive HTTP-based streaming protocols became the main technology for live streaming as well. All companies who have a major say in the market including Microsoft, Adobe and Apple have adopted HTTP-streaming as the main approach for live broadcasting. This shift to HTTP has been driven by a number of advantages such as the following: i) Routers and firewalls are more permissive to HTTP traffic compared to the RTSP/RTP ii) HTTP caching for real-time generated media is straight-forward like any traditional web-content iii) The Content Distribution Networks (CDNs) business is much cheaper when dealing with HTTP downloads [START_REF]Smooth Streaming[END_REF].

The first goal of this paper is to describe the shift from the RTSP/RTP model to the HTTP-live model (Section 2). This, in order to detail the impact of the same on the design of P2P live streaming protocols (Section 3). A point which we find rather neglected in the research community (Section 4). We argue that this shift has rendered many of the classical assumptions made in the current state-ofthe-art literature obsolete. For all practical purposes, any new P2PLS algorithm irrespective of its theoretical soundness, won't be deployable if it does not take into account the realities of the mainstream broadcasting ecosystem around it. The issue becomes even more topical as we observe a trend in standardizing HTTP live [START_REF] Pantos | HTTP Live Streaming[END_REF] streaming and embedding it in all browsers together with HTML5, which is already the case in browsers like Apple's Safari.

The second goal of this paper is to present a P2PLS protocol that is compatible with HTTP live streaming for not only one bitrate but that is fully compatible with the concept of adaptive bitrate, where a stream is broadcast with multiple bitrates simultaneously to make it available for a range of viewers with variable download capacities (Section 5).

The last goal of this paper is to describe a number of optimizations of our P2PLS protocol concerning neighborhood management, uploader selection and peer transfer which can deliver a significant amount of traffic savings on the source of the stream (Section 6 and 7). Experimental results of our approach show that this result comes at almost no cost in terms of quality of user experience (Section 8).

The Shift from RTP/RTSP to HTTP

In the traditional RTSP/RTP model, the player uses RTSP as the signalling protocol to request the playing of the stream from a streaming server. The player enters a receive loop while the server enters a send loop where stream fragments are delivered to the receiver using the RTP protocol over UDP. The interaction between the server and player is stateful. The server makes decisions about which fragment is sent next based on acknowledgements or error information previously sent by the client. This model makes the player rather passive, having the mere role of rendering the stream fragments which the server provides.

In the HTTP live streaming model instead, it is the player which controls the content delivery by periodically pulling from the server parts of the content at the time and pace it deems suitable. The server instead is entitled with the task of encoding the stream in real time with different encoding rates, or qualities, and storing it in data fragments which appear on the server as simple resources.

When a player first contacts the streaming server, it is presented with a metadata file (Manifest) containing the latest stream fragments available at the server at the time of the request. Each fragment is uniquely identified by a time-stamp and a bitrate. If a stream is available in n different bitrates, then After reading the manifest, the player starts to request fragments from the server. The burden of keeping the timeliness of the live stream is totally upon the player. The server in contrast, is stateless and merely serves fragments like any other HTTP server after encoding them in the format advertised in the manifest.

Manifest Contents. To give an example, we use Microsoft's Smooth Streaming manifest. In Figure 1a, we show the relevant details of a manifest for a live stream with 3 video bitrates (331, 688, 1470 Kbps) and 1 audio bitrate (64 Kbps). By inspecting one of the streams, we find the first (the most recent) fragment containing a d value which is the time duration of the fragment in a unit of 100 nanoseconds and a t value which is the timestamp of the fragment. The fragment underneath (the older fragment) has only a d value because the timestamp is inferred by adding the duration to the timestamp of the one above. The streams each have a template for forming a request url for fragments of that stream. The template has place holders for substitution with an actual bitrate and timestamp. For a definition of the manifest's format, see [START_REF]Smooth Streaming[END_REF].

Adaptive Streaming Protocol. In Figure 1b, we show an example interaction sequence between a Smooth Streaming Client and Server [START_REF]Smooth Streaming[END_REF]. The Client first issues a HTTP GET request to retrieve the manifest from the streaming server. After interpreting the manifest, the player requests a video fragment from the lowest available bitrate (331 Kbps). The timestamp of the first request is not predictable but in most cases we have observed that it is an amount equal to 10 seconds backward from the most recent fragment in the manifest. This is probably the only predictable part of the player's behavior.

In fact, without detailed knowledge of the player's internal algorithm and given that different players may implement different algorithms, it is difficult to make assumptions about the period between consecutive fragment requests, the time at which the player will switch rates, or how the audio and video are interleaved. For example, when a fragment is delayed, it could get re-requested at the same bitrate or at a lower rate. The timeout before taking such action is one thing that we found slightly more predictable and it was most of the time around 4 seconds. That is a subset of many details about the pull behavior of the player.

Implications of Unpredictability. The point of mentioning these details is to explain that the behavior of the player, how it buffers and climbs up and down the bitrates is rather unpredictable. In fact, we have seen it change in different version of the same player. Moreover, different adopters of the approach have minor variations on the interactions sequence. For instance, Apple HTTP-live [START_REF] Pantos | HTTP Live Streaming[END_REF] dictates that the player requests a manifest every time before requesting a new fragment and packs audio and video fragments together. As a consequence of what we described above, we believe that a P2PLS protocol for HTTP live streaming should operate as if receiving random requests in terms of timing and size and has to make this the main principle. This filters out the details of the different players and technologies.

Impact of the Shift on P2PLS Algorithms

Traditionally, the typical setup for a P2PLS agent is to sit between the streaming server and the player as a local proxy offering the player the same protocol as the streaming server. In such a setup, the P2PLS agent would do its best, exploiting the peer-to-peer overlay, to deliver pieces in time and in the right order for the player. Thus, the P2PLS agent is the one driving the streaming process and keeping an active state about which video or audio fragment should be delivered next, whereas the player blindly renders what it is supplied with. Given the assumption of a passive player, it is easy to envisage the P2PLS algorithm skipping for instance fragments according to the playback deadline, i.e. discarding data that comes too late for rendering. In this kind of situation, the player is expected to skip the missing data by fast-forwarding or blocking for few instants and then start the playback again. This type of behavior towards the player is an intrinsic property of many of the most mature P2PLS system designs and analyses such as [START_REF] Vlavianos | BiToS: Enhancing BitTorrent for Supporting Streaming Applications[END_REF][START_REF] Zhang | Understanding the Power of Pull-Based Streaming Protocol: Can We Do Better? In: Selected Areas in Communications[END_REF][START_REF] Zhang | CoolStreaming/DONet: a data-driven overlay network for peer-to-peer live media streaming[END_REF].

In contrast to that, a P2PLS agent for HTTP live streaming can not rely on the same operational principles. There is no freedom in skipping pieces and deciding what is to be delivered to the player. The P2PLS agent has to obey the player's request for fragments from the P2P network and the speed at which this is accomplished affects the player's next action. From our experience, delving in the path of trying to reverse engineer the player behavior and integrating that in the P2P protocol is some kind of black art based on trial-and-error and will result into very complicated and extremely version-specific customizations. Essentially, any P2PLS scheduling algorithm that assumes that it has control over which data should be delivered to the player is rather inapplicable to HTTP live streaming.

Related Work

We are not aware of any work that has explicitly articulated the impact of the shift to HTTP on the P2P live streaming algorithms. However, a more relevant topic to look at is the behavior of the HTTP-based live players. Akhshabi et. al [START_REF] Akhshabi | An experimental evaluation of rateadaptation algorithms in adaptive streaming over HTTP[END_REF], provide a recent dissection of the behavior of three such players under different bandwidth variation scenarios. It is however clear from their analysis that the bitrate switching mechanics of the considered players are still in early stages of development. In particular, it is shown that throughput fluctuations still cause either significant buffering or unnecessary bitrate reductions. On top of that, it is shown how all the logic implemented in the HTTP-live players is tailored to TCP's behavior, as the one suggested in [START_REF] Liu | Parallel Adaptive HTTP Media Streaming[END_REF]. That in order to compensate throughput variations caused by TCP's congestion control and potentially large retransmission delays. In the case of a P2PLS agent acting as proxy, it is then of paramount importance to not interfere with such adaptation patterns.

We believe, given the presented approaches, the most related work is the P2P caching network LiveSky [START_REF] Yin | Livesky: Enhancing cdn with p2p[END_REF]. We share in common the fact of trying to establish a P2P CDN. However, LiveSky does not present any solution for supporting HTTP live streaming.

P2PLS as a Caching Problem

We will describe here our baseline design to tackle the new realities of the HTTPbased players. We treat the problem of reducing the load on the source of the stream the same way it would be treated by a Content Distribution Network (CDN): as a caching problem. The design of the streaming protocol was made such that every fragment is fetched as an independent HTTP request that could be easily scheduled on CDN nodes. The difference is that in our case, the caching nodes are consumer machines and not dedicated nodes. The player is directed to order from our local P2PLS agent which acts as an HTTP proxy. All traffic to/from the source of the stream as well as other peers passes by the agent.

Baseline Caching. The policy is as follows: any request for manifest files (metadata), is fetched from the source as is and not cached. That is due to the fact that the manifest changes over time to contain the newly generated fragments. Content fragments requested by the player are looked up in a local index of the peer which keeps track of which fragment is available on which peer. If information about the fragment is not in the index, then we are in the case of a P2P cache miss and we have to retrieve it from the source. In case of a cache hit, the fragment is requested from the P2P network and any error or slowness in the process results, again, in a fallback to the source of the content. Once a fragment is downloaded, a number of other peers are immediately informed in order for them to update their indices accordingly.

Achieving Savings. The main point is thus to increase the cache hit ratio as much as possible while the timeliness of the movie is preserved. The cache hit ratio is our main metric because it represents savings from the load on the source of the live stream. Having explained the baseline idea, we can see that, in theory, if all peers started to download the same uncached manifest simultaneously, they would also all start requesting fragments exactly at the same time in perfect alignment. This scenario would leave no time for the peers to advertise and exchange useful fragments between each others. Consequently a perfect alignment would result in no savings. In reality, we have always seen that there is an amount of intrinsic asynchrony in the streaming process that causes some peers to be ahead of others, hence making savings possible. However, the larger the number of peers, the higher the probability of more peers being aligned. We will show that, given the aforementioned asynchrony, even the previously described baseline design can achieve significant savings.

Our target savings are relative to the number of peers. That is we do not target achieving a constant load on the source of the stream irrespective of the number of users, which would lead to loss of timeliness. Instead, we aim to save a substantial percentage of all source traffic by offloading that percentage to the P2P network. The attractiveness of that model from a business perspective has been verified with content owners who nowadays buy CDN services.

Beyond Baseline Caching

We give here a description of some of the important techniques that are crucial to the operation of the P2PLS agent. For each such technique we provide what we think is the simplest way to realize it as well as improvements if we were able to identify any. The techniques are summarized in Table 1.

Manifest Manipulation. One improvement particularly applicable in Microsoft's Smooth streaming but that could be extended to all other technologies is manifest manipulation. As explained in Section 2, the server sends a manifest containing a list of the most recent fragments available at the streaming server. The point of that is to avail to the player some data in case the user decides to jump back in time. Minor trimming to hide the most recent fragments from some peers places them behind others. We use that technique to push peers with high upload bandwidth slightly ahead of others because they have they can be more useful to the network. We are careful not to abuse this too much, otherwise peers would suffer a high delay from live playing point, so we limit it to a maximum of 4 seconds. It is worth noting here that we do a quick bandwidth measurement for peers upon admission to the network, mainly, for statistical purposes but we do not depend on this measurement except during the optional trimming process.

Neighborhood & Partnership Construction. We use a tracker as well as gossiping for introducing peers to each other. Any two peers who can establish bi-directional communication are considered neighbors. Each peer probes his neighbors periodically to remove dead peers and update information about their last requested fragments. Neighborhood construction is in essence a process to create a random undirected graph with high node arity. A subset of the edges in the neighborhood graph is selected to form a directed subgraph to establish partnership between peers. Unlike the neighborhood graph, which is updated lazily, the edges of the partneship graph are used frequently. After each successful download of a fragment, the set of (out-partners) is informed about the newly downloaded fragment. From the opposite perspective, it is crucial for a peer to wisely pick his in-partners because they are the providers of fragments from the P2P network. For this decision, we experiment with two different strategies: i) Random picking, ii) Request-point-aware picking: where the in-partners include only peers who are relatively ahead in the stream because only such peers can have future fragments.

Partnership Maintenance. Each peer strives to continuously find better in-partners using periodic maintenance. The maintenance process could be limited to replacement of dead peers by randomly-picked peers from the neighborhood. Our improved maintenance strategy is to score the in-partners according to a certain metric and replace low-scoring partners with new peers from the neighborhood. The metric we use for scoring peers is a composite one based on: i) favoring the peers with higher percentage of successfully transferred data, ii) favoring peers who happen to be on the same bitrate. Note that while favoring peers on the same bitrate, having all partners from a single bitrate is very dangerous, because once a bit-rate change occurs the peer is isolated. That is, all the received updates about presence of fragments from other peers would be from the old bitrate. That is why, upon replacement, we make sure that the resulting in-partners set has all bit-rates with a gaussian distribution centered around the current bitrate. That is, most in-partners are from the current bit rate, less partners from the immediately higher and lower bit rates and much less partners from other bitrates and so forth. Once the bit-rate changes, the maintenance re-centers the distribution around the new bitrate.

Uploader Selection. In the case of a cache hit, it happens quite often that a peer finds multiple uploaders who can supply the desired fragment. In that case, we need to pick one. The simplest strategy would be to pick a random uploader. Our improved strategy here is to keep track of the observed historical throughput of the downloads and pick the fastest uploader.

Sub-fragments. Up to this point, we have always used in our explanation the fragment as advertised by the streaming server as the unit of transport for simplifying the presentation. In practice, this is not the case. The sizes of the fragment vary from one bitrate to the other. Larger fragments would result in waiting for a longer time before informing other peers which would directly entail lower savings because of the slowness of disseminating information about fragment presence in the P2P network. To handle that, our unit of transport and advertising is a sub-fragment of a fixed size. That said, the reality of the uploader selection process is that it always picks a set uploaders for each fragment rather than a single uploader. This parallelization applies for both random and throughput-based uploader selection strategies.

Fallbacks. While downloading a fragment from another peer, it is of critical importance to detect problems as soon as possible. The timeout before falling back to the source is thus one of the major parameters while tuning the system.

We put an upper bound (T p2p ) on the time needed for any P2P operation, computed as: T p2p = T player -S * T f where T player is the maximum amount of time after which the player considers a request for a fragment expired, S is the size of fragment and T f is the expected time to retrieve a unit of data from the fallback. Based on our experience, T player is player-specific and constant, for instance Microsoft's Smooth Streaming waits 4 seconds before timing out. A longer T p2p translates in a higher P2P success transfer ratio, hence higher savings. Since T player and S are outside of our control, it is extremely important to estimate T f correctly, in particular in presence of congestion and fluctuating throughput towards the source. As a further optimization, we recalculate the timeout for a fragment while a P2P transfer is happening depending on the amount of data already downloaded, to allow more time for the outstanding part of the transfer. Finally, upon fallback, only the amount of fragment that failed to be downloaded from the overlay network is retrieved from the source, i.e. through a partial HTTP request on the range of missing data.

Proactive Caching

The baseline caching process is in essence reactive, i.e. the attempt to fetch a fragment starts after the player requests it. However, when a peer is informed about the presence of a fragment in the P2P network, he can trivially see that this is a future fragment that would be eventually requested. Starting to prefetch it early before it is requested, increases the utilization of the P2P network and decreases the risk of failing to fetch it in time when requested. That said, we do not guarantee that this fragment would be requested in the same bitrate, when the time comes. Therefore, we endure a bit of risk that we might have to discard it if the bitrate changes. In practice, we measured that the prefetcher successfully requests the right fragment with a 98.5% of probability.

Traffic Prioritization. To implement this proactive strategy we have taken advantage of our dynamic runtime-prioritization transport library DTL [START_REF] Reale | DTL: Dynamic Transport Library for Peer-To-Peer Applications[END_REF] which exposes to the application layer the ability to prioritize individual transfers relative to each other and to change the priority of each individual transfer at run-time. Upon starting to fetch a fragment proactively, it is assigned a very low-priority. The rationale is to avoid contending with the transfer process of fragments that are reactively requested and under a deadline both on the uploading and downloading ends.

Successful Prefetching. One possibility is that a low-priority prefetching process completes before a player's request and there is no way to deliver it to the player before that happens, the only option is to wait for a player request. More importantly, when that time comes, careful delivery from the local machine is very important because extremely fast delivery might make the adaptive streaming player mistakenly think that there is an abundance of download bandwidth and start to request the following fragments a higher bitrate beyond the actual download bandwidth of the peer. Therefore, we schedule the delivery from the local machine to be not faster than the already-observed average download rate. We have to stress here that this is not an attempt to control the player to do something in particular, we just maintain transparency by not delivering prefetched fragments faster than not prefetched ones.

Interrupted Prefetching. Another possiblity is that the prefetching process gets interrupted by the player in 3 possible ways: i) The player requests the fragment being prefetched: in that case the transport layer is dynamically instructed to raise the priority and T player is set accordingly based on the remaining amount of data as described in the previous section. ii) The player requests the same fragment being prefetched but at a higher rate which means we have to discard any prefetched data and treat the request like any other reactively fetched fragment. iii) The player decides to skip some fragments to catch up and is no longer in need of the fragment being prefetched. In this case, we have to discard it as well.

Evaluation

Methodology. Due to the non-representative behaviour of Planetlab and the difficulty to do parameter exploration in publicly-deployed production network, we tried another approach which is to develop a version of our P2P agent that is remotely-controlled and ask for volunteers who are aware that we will conduct experiments on their machines. Needless to say, that this functionality is removed from any publicly-deployable version of the agent.

Test Network. The test network contained around 1350 peers. However, the maximum, minimum and average number of peers simultaneously online were 770, 620 and 680 respectively. The network included peers mostly from Sweden (89%) but also some from Europe (6%) and the US (4%). The upload bandwidth distribution of the network was as follows: 15% : 0.5M bps, 42% : 1M bps, 17% : 2.5M bps, 15% : 10M bps, 11% : 20M bps. In general, one can see that there is enough bandwidth capacity in the network, however the majority of the peers are on the lower end of the bandwidth distribution. For connectivity, 82% of the peers were behind NAT, and 12% were on open Internet. We have used our NAT-Cracker traversal scheme as described in [START_REF] Roverso | NATCracker: NAT Combinations Matter[END_REF] and were able to establish bi-directional communication between 89% of all peer pairs. The unique number of NAT types encountered were 18 types. Apart from the tracker used for introducing clients to each other, our network infrastructure contained, a logging server, a bandwidth measurement server, a STUN-like server for helping peers with NAT traversal and a controller to launch tests remotely.

Stream Properties. We used a production-quality continuous live stream with 3 video bitrates (331, 688, 1470 Kbps) and 1 audio bitrate (64 Kbps) and we let peers watch 20 minutes of this stream in each test. The stream was published using Microsoft Smooth Streaming traditional tool chain. The bandwidth of the source stream was provided by a commercial CDN and we made sure that it had enough capacity to serve the maximum number of peers in our test network. This setup gave us the ability to compare the quality of the streaming process in the presence and absence of P2P caching in order to have a fair assessment of the effect of our agent on the overall quality of user experience. We stress that, in a real deployment, P2P caching is not intended to eliminate the need for a CDN but to reduce the total amount of paid-for traffic that is provided by the CDN. One of the issues that we faced regarding realistic testing was making sure that we are using the actual player that would be used in production, in our case that was the Microsoft Silverlight player. The problem is that the normal mode of operation of all video players is through a graphical user interface. Naturally, we did not want to tell our volunteers to click the "Play" button every time we wanted to start a test. Luckily, we were able to find a rather unconventional way to run the Silverlight player in a headless mode as a background process that does not render any video and does not need any user intervention.

Reproducibility. Each test to collect one data point in the test network happens in real time and exploring all parameter combination of interest is not feasible. Therefore, we did a major parameter combinations study on our simulation platform [START_REF] Roverso | Mesmerizer: A effective tool for a complete peer-to-peer software development life-cycle[END_REF] first to get a set of worth-trying experiments that we launched on the test network. Another problem is the fluctuation of network conditions and number of peers. We repeated each data point a number of times before gaining confidence that this is the average performance of a certain parameter combination.

Evaluation Metrics. The main metric that we use is traffic savings defined as the percentage of the amount of data served from the P2P network from the total amount of data consumed by the peers. Every peer reports the amount of data served from the P2P network and streaming source every 30 seconds to the logging server. In our bookkeeping, we keep track of how much of the traffic was due to fragments of a certain bitrate. The second important metric is buffering delay. The Silverlight player can be instrumented to send debug information every time it goes in/out of buffering mode, i.e. whenever the player finds that the amount of internally-buffered data is not enough for playback, it sends a debug message to the server, which in our case is intercepted by the agent. Using this method, a peer can report the lengths of the periods it entered into buffering mode in the 30 seconds snapshots as well. At the end of the stream, we calculate the sum of all the periods the player of a certain peer spent buffering.

Deployment Results

Step-by-Step Towards Savings. The first investigation we made was to start from the baseline design with all the strategies set to the simplest possible. In fact, during the development cycle we used this baseline version repeatedly until we obtained a stable product with predictable and consistent savings level before we started to enable all the other improvements. Figure 2a shows the evolution of savings in time for all strategies. The naive baseline caching was able to save a total of 44% of the source traffic. After that, we worked on pushing the higherbandwidth peers ahead and making each partner select peers that are useful using the request-point-aware partnership which moved the savings to a level of 56%. So far, the partnership maintenance was random. Turning on bit-rateaware maintenance added only another 5% of savings but we believe that this is a key strategy that deserves more focus because it directly affects the effective partnership size of other peers from each bitrate which directly affects savings.

For the uploader selection, running the throughput-based picking achieved 68% of savings. Finally, we got our best savings by adding proactive caching which gave us 77% savings. User Experience. Getting savings alone is not a good result unless we have provided a good user experience. To evaluate the user experience, we use two metrics: First, the percentage of peers who experienced a total buffering time of less than 5 seconds, i.e. they enjoyed performance that did not really deviate much from live. Second, showing that our P2P agent did not achieve this level of savings by forcing the adaptive streaming to move everyone to the lowest bitrate. For the first metric, Figure 2b shows that with all the improvements, we can make 87% of the network watch the stream with less than 5 seconds of buffering delay. For the second metric, Figure 3a shows also that 88% of all consumed traffic was on the highest bitrate and P2P alone shouldering 75% (Figure 3b), an indication that, for the most part, peers have seen the video at the highest bitrate with a major contribution from the P2P network.

P2P-less as a Reference. We take one more step beyond showing that the system offers substantial savings with reasonable user experience, namely to understand what would be the user experience in case all the peers streamed directly from the CDN. Therefore, we run the system with P2P caching disabled. Figure 2b shows that without P2P, only 3% more (90%) of all viewers would have a less than 5 seconds buffering. On top of that, Figure 3c shows that only 2% more (90%) of all consumed traffic is on the highest bitrate, that is the small price we paid for saving 77% of source traffic. Figure 4a instead describes the lower performance of our baseline caching scenario, which falls 13% of the P2Pless scenario (77%). This is mainly due to the lack of bit-rate-aware maintenance, which turns out to play a very significant role in terms of user experience. Partnership Size. There are many parameters to tweak in the protocol but, in our experience, the number of in-partners is by far the parameter with the most significant effect. Throughout the evaluation presented here, we use 50 in-partners. Figure 4b shows that more peers result in more savings; albeit with diminishing returns. We have selected 50-peers as a high-enough number, at a point where increasing the peers does not result into much more savings.

Single Bitrate. Another evaluation worth presenting as well is the case of a single bitrate. In this experiment, we get 84%, 81% and 69% for the low, medium and high bitrate respectively (Figure 5a). As for the user experience compared with the same single bitrates in a P2P-less test, we find that the user experience expressed as delays is much closer to the P2P-less network (Figure 5b). We explain the relatively better experience in the single bitrate case by the fact that all the in-partners are from the same bitrate, while in the multibitrate case, each peer has in his partnership the majority of the in-partners from a single bitrate but some of them are from other bitrates which renders the effective partnership size smaller. We can also observe that the user experience improves as the bitrate becomes smaller.

Conclusion

In this paper, we have shown a novel approach in building a peer-to-peer live streaming system that is compatible with the new realities of the HTTP-live. These new realities revolve around the point that unlike RTSP/RTP streaming, the video player is driving the streaming process. The P2P agent will have a limited ability to control what gets rendered on the player and much limited ability to predict its behaviour. Our approach was to start with baseline P2P caching where a P2P agent acts as an HTTP proxy that receives requests from the HTTP live player and attempts to fetch it from the P2P network rather the source if it can do so in a reasonable time.

Beyond baseline caching, we presented several improvements that included: a) Request-point-aware partnership construction where peers focus on establishing relationships with peers who are ahead of them in the stream, b) Bit-rate-aware partnership maintenance through which a continuous updating of the partnership set is accomplished both favoring peers with high successful transfers rate and peers who are on the same bitrate of the maintaining peer, c) Manifest trimming which is a technique for manipulating the metadata presented to the peer at the beginning of the streaming process to push high-bandwidth peers ahead of others, d) Throughput-based uploader selection which is a policy used to pick the best uploader for a certain fragment if many exist, e) Careful timing for falling back to the source where the previous experience is used to tune timing out on P2P transfers early enough thus keeping the timeliness of the live playback.

Our most advanced optimization was the introduction of proactive caching where a peer requests fragments ahead of time. To accomplish this feature without disrupting the already-ongoing transfer, we used our application-layer congestion control [START_REF] Reale | DTL: Dynamic Transport Library for Peer-To-Peer Applications[END_REF] to make pre-fetching activities have less priority and dynamically raise this priority in case the piece being pre-fetched got requested by the player. We evaluated our system using a test network of real volunteering clients of about 700 concurrent nodes where we instrumented the P2P agents to run tests under different configurations. The tests have shown that we could achieve around 77% savings for a multi-bitrate stream with around 87% of the peers experiencing a total buffering delay of less than 5 seconds and almost all of the peers watched the data on the highest bitrate. We compared these results with the same network operating in P2P-less mode and found that only 3% of the viewers had a better experience without P2P which we judge as a very limited degradation in quality compared to the substantial amount of savings.

Fig

  Fig. 1: a) Sample Smooth streaming Manifest, b) Client-Server interactions in Microsoft Smooth Streamingthis means that for each timestamp, there exists n versions of it, one for each bitrate.After reading the manifest, the player starts to request fragments from the server. The burden of keeping the timeliness of the live stream is totally upon the player. The server in contrast, is stateless and merely serves fragments like any other HTTP server after encoding them in the format advertised in the manifest.Manifest Contents. To give an example, we use Microsoft's Smooth Streaming manifest. In Figure1a, we show the relevant details of a manifest for a live stream with 3 video bitrates (331, 688, 1470 Kbps) and 1 audio bitrate (64 Kbps). By inspecting one of the streams, we find the first (the most recent) fragment containing a d value which is the time duration of the fragment in a unit of 100 nanoseconds and a t value which is the timestamp of the fragment. The fragment underneath (the older fragment) has only a d value because the timestamp is inferred by adding the duration to the timestamp of the one above. The streams each have a template for forming a request url for fragments of that stream. The template has place holders for substitution with an actual bitrate and timestamp. For a definition of the manifest's format, see[START_REF]Smooth Streaming[END_REF].Adaptive Streaming Protocol. In Figure1b, we show an example interaction sequence between a Smooth Streaming Client and Server[START_REF]Smooth Streaming[END_REF]. The Client first issues a HTTP GET request to retrieve the manifest from the streaming server. After interpreting the manifest, the player requests a video fragment from the lowest available bitrate (331 Kbps). The timestamp of the first request is not predictable but in most cases we have observed that it is an amount equal to 10 seconds backward from the most recent fragment in the manifest. This is probably the only predictable part of the player's behavior.In fact, without detailed knowledge of the player's internal algorithm and given that different players may implement different algorithms, it is difficult to make assumptions about the period between consecutive fragment requests, the time at which the player will switch rates, or how the audio and video are interleaved. For example, when a fragment is delayed, it could get re-requested at the same bitrate or at a lower rate. The timeout before taking such action is one thing that we found slightly more predictable and it was most of the time

Fig. 2 :

 2 Fig. 2: (a) Comparison of traffic savings with different algorithm improvements, (b) Comparison of cumulative buffering time for source only and improvements.

Fig. 3 :

 3 Fig. 3: Breakdown of traffic quantities per bitrate for: (a) A network with P2P caching, Source & P2P traffic summed together. (b) The same P2P network with source & P2P traffic reported separately, and (c) A network with no P2P.

Fig. 4 :

 4 Fig. 4: (a) Breakdown of traffic quantities per bitrate using baseline, (b) Comparison of savings between different in-partners number.

Fig. 5 :

 5 Fig. 5: (a) Savings for single bitrate runs, (b) Buffering time for single bitrate runs.

Table 1 :

 1 Summary of baseline and improved strategies.

	Strategy	Baseline	Improved
	Manifest Trimming (MT )	Off	On
	Partnership Construction (PC )	Random	Request-Point-aware
	Partnership Maintenance (PM )	Random	Bitrate-aware
	Uploader Selection (US )	Random	Throughput-based
	Proactive Caching (PR)	Off	On


Dimitra Gkorou

Tamás Vinkó

Nitin J Chiluka

Johan A Pouwelse

Dick Epema
email: epema@tudelft.nl

{d Gkorou

T Vinko

Reducing the History in Decentralized Interaction-Based Reputation Systems

Keywords: decentralized reputation systems, P2P networks, computational cost

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

A family of reputation systems useful in many Internet applications consists of interaction-based systems (also called content-driven systems [START_REF] De Alfaro | Reputation systems for open collaboration[END_REF]). These systems are based on algorithms analyzing all interactions among users and computing the reputations without using any explicit feedback from users, such as PageRank [START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF] for ranking web pages and Bartercast [START_REF] Meulpolder | Bartercast: A practical approach to prevent lazy freeriding in p2p networks[END_REF] for computing reputations of users in P2P systems. In interaction-based systems, the amount of historical information on the interactions maintained by each node affects the performance and the characteristics of the reputation mechanism. Networks such as popular online markets and social networks consist of hundreds of thousands or even millions of active users and thus, using the complete history for computing the reputation of nodes is prohibitive due to its resource requirements. Particularly in decentralized systems, such as file-sharing P2P systems, the available resources at nodes are limited and thus, only scalable solutions can be applied. Furthermore, a long-term history allows previously well-behaved nodes to exploit their good reputations by acting maliciously [START_REF] Feldman | Robust incentive techniques for peer-to-peer networks[END_REF][START_REF] Marti | Taxonomy of trust: Categorizing p2p reputation systems[END_REF][START_REF] Xiong | Peertrust: Supporting reputation-based trust for peer-to-peer electronic communities[END_REF]. In this paper, we propose a scheme for reducing the amount of history maintained in decentralized interaction-based reputation systems. We experimentally explore its effect on the computed reputations using synthetic and real-world graphs.

In order to reduce the history of interactions, we use only a subset of the complete history to approximate reputations. We model the interactions of the complete history of a network as a growing graph with the nodes of the network as its vertices and the interactions between pairs of nodes as its edges, and the corresponding reduced history as a subgraph of the complete history. The reduced history is derived from the complete history by deleting the least important edges and nodes. We define the importance of a node according to its age, its activity level, its reputation, and its position in the graph, while the importance of an edge is defined according to its age, its weight, and its position in the graph. Then we evaluate our approach using synthetic random and scale-free graphs, and two real-world graphs, one derived from the Bartercast reputation system of our BitTorrent-based P2P client Tribler [START_REF] Pouwelse | Tribler: a social-based peer-to-peer system[END_REF] and the other from the author-to-author Citation network of Physical Review E journal 1 . The main difference between the Bartercast and the Citation graphs, besides their structural properties, is that the former is derived from a deployed distributed system with personalized reputations while the latter is derived from a centralized system with global reputations.

On these networks, we apply two different computations for reputations, one based on the max-flow algorithm [START_REF] Cormen | Introduction to Algorithms[END_REF] and the other based on eigenvector centrality [START_REF] Bonacich | Eigenvector-like measures of centrality for asymmetric relations[END_REF]. We evaluate our approach according the following two observations: (i) for the vast majority of reputation systems, the rank of reputations is more important than the actual reputation values themselves; and (ii) in most cases the identification of the highest ranked nodes is enough. We demonstrate that the performance of the reduced history depends on the topology of the complete history. Furthermore, we show that the performance of the reduced history depends on the reputation algorithm. Finally, we conclude that reduced history can be applied in a large range of networks. Although our approach focuses on decentralized reputation systems, it can be applied to centralized systems as well.

Motivation and Problem Statement

Our main motivation for reducing the history of interactions in a network is the computational cost and the storage requirements of decentralized reputation algorithms. Reputation systems, such as those of eBay or Google, cover hundreds of thousands of active nodes while reputation algorithms (e.g., Eigentrust [START_REF] Kamvar | The eigentrust algorithm for reputation management in p2p networks[END_REF], PageRank [START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF] and max-flow based ones [START_REF] Cormen | Introduction to Algorithms[END_REF]) have a high computational complexity. In decentralized systems, like BarterCast, where each node stores and analyzes data locally using, e.g., the max-flow algorithm (with complexity O(nm 2 ) where n is the number of nodes and m and the number of edges), even much smaller graphs of 10 6 nodes make the computation of reputations prohibitive. Taking into account that the contributions of nodes in the computation of reputations are not equal in quality and quantity [START_REF] De Alfaro | Reputation systems for open collaboration[END_REF], thus we aim to delete the least important contributions and compute reputations using only a subset of the complete history. In this way, we can reduce the computational cost significantly without decreasing the accuracy very much.

In addition to the computational cost, the dynamic behavior of many reputation systems makes the use of the complete history ineffective. In systems with a high population turnover such as P2P networks, only a few nodes remain for a long period in the system while the majority of nodes enters the system performing some interactions and then leaves it. Also a node behaving properly for a long time can build a good reputation and become a traitor [START_REF] Marti | Taxonomy of trust: Categorizing p2p reputation systems[END_REF] by exploiting other nodes. Preserving only short-term history forces all nodes in the system to behave continuously according to the protocol. For these reasons, several widely used reputation mechanisms, such as those of eBay and eLance, allow the use of historical information of a 1 or 6-month window. Although using a time window is useful for such feedback-based reputation systems, it is not effective in interaction-based reputation systems since important information of highly reputed nodes is deleted.

We model the interactions of a network as a directed weighted graph G = (V, E), where the vertices V represent the nodes and the edges E the interactions among the nodes. The weight of an edge represents its importance; for instance, in Bartercast, the weight of an edge between nodes represents the amount of data transferred in the corresponding direction, and in a citation graph, it represents the number of references to an author by another. The graph is dynamically growing over time and allows not only new nodes to join but also existing nodes to create new edges. The graph G represents the complete history (CH) of interactions in the network.

Given the growing graph G, our target is to create a subgraph of G, denoted by G ′ , which preserves the highest ranked nodes in G and keeps the ranking of the reputations similar to that in G. The subgraph G ′ has to be dynamically maintained as the complete history grows while its size has to be almost fixed. The graph G ′ will be used for the computation of reputations, and represents the reduced history (RH) of interactions in the network.

Creating the Reduced History

The basic idea of creating the reduced history G ′ consists of removing the least important elements, either nodes or edges, from G. We use a node removal process in conjunction with edge removal. The ratio of removed nodes versus removed edges depends on the dynamics of the network. Nevertheless, edge removal implies node removal and vice versa. More precisely, edge removal can lead to disconnecting a node from the graph and node removal results in deleting the adjacent edges of the removed node.

The parameters for removal of a node consist of its age, its activity level, its reputation, and its position in the graph.

The age of node i is expressed as τ i = t -t i where t is the current time and t i is the time instance node i joined the system. In most networks, the age of a node i affects its behavior in a non-linear way (e.g. [START_REF] Amaral | Classes of small-world networks[END_REF]14]). Thus, instead of its age, we consider its aging factor f (τ i ), where f is a decreasing function with f (0) = 1 (e.g., f (τ ) = e -bτ , where τ represents the age of a node and b is a constant). Keeping fresh information allows the reputations system to capture the dynamic behavior of nodes.

The activity level d i of a node i represents its degree. Nodes with a high activity level participated in many interactions, and so, they provide much information.

The reputation of node i is denoted by r i . Our aim is to preserve the information of nodes with high reputations, since these nodes are the most reliable in the network. Moreover, allowing nodes with high reputations to contribute to the computation of reputations longer is a kind of rewarding the most trusted nodes.

For node i the importance of its position in the graph is expressed by its betweenness centrality (BC), denoted by C B (i), which measures the sum of the fractions of the numbers of shortest paths among all pairs of vertices that pass through node i [START_REF] Freeman | A set of measures of centrality based on betweenness[END_REF]. Removing nodes from the graph can result in destroying its structure by creating many disconnected components and thus, we need to maintain the nodes that keep the graph connected.

The first three factors represent the behavior of node i while the fourth factor is added for preserving the structure of the graph during the deletion process. Therefore, in our method, the priority score P n (i) of deleting node i is defined as

P n (i) = αP A (d i , r i , τ i ) + (1 -α)P B (C B (i)), (1)
where P A (d i , r i , τ i ) expresses the priority score of deleting node i based on its activity level, aging factor and reputation, and P B (C B (i)) represents the priority score of deleting node i according to its position in the graph. The parameter α takes values in [0, 1] and can be chosen according to the graph properties. We define the priority score P A as

P A (d i , r i , τ i ) = n -d i r i f (τ i ) n 2 - ∑ j d j r j f (τ j ) , ( 2
)
where n is the number of nodes in the graph, and the denominator acts as a normalization so that the sum of the priority scores sum to 1. Clearly, a node with a higher age, a lower activity level, or a lower reputation will be removed. Although the maximum value of

d i r i f (τ i ) is equal to n -1 (corresponding to d i = n -1, r i = 1 and f (τ i ) = 1)
, for simplicity, we approximate it to n. Similarly, P B is expressed as

P B (C B (i)) = (n 2 -C B (i))/(n 3 - ∑ j C B (j)). Again, even though the maximum value of C B (i) is equal to (n -1)(n -2)
, we approximate it by n 2 . When considering a single parameter for node removal, Eq.2 can be adapted in a straightforward way (similarly as P B for parameter C B (i)).

The removal of an edge is determined by its age, its weight, and its position in the graph.

The age of edge e ij connecting nodes i and j, is defined similarly to the age of a node, and is denoted by τ ij = t -t ij , where t is the current time and t ij is the time of its creation. The aging factor of edge e ij is a decaying function f (τ ij ) and can be, e.g., an exponential function.

The weight of edge e ij , denoted by w ij , is one of the parameters for edge removal, since interactions with a high cost are more important for the computation of reputations, edges with high weights have to be preserved in the graph.

The importance of the position of edge e ij in the graph is expressed by its edge betweenness centrality (BC), denoted by C E (e ij ), which is defined as the sum of the ratios of shortest paths between all pairs of nodes containing this edge [START_REF] Freeman | A set of measures of centrality based on betweenness[END_REF]. The aging factor and the weight of an edge represent its contribution to the computation of reputations, while its C E helps in preserving the structure of the graph.

Similarly to node removal, we express the priority score of removing an edge e ij as

P e (e ij ) = αP S (w ij , τ ij ) + (1 -α)P F (C E (e ij )), (3)
where α is the parameter used in the definition of P n to control the topology of the derived graph. The scores P S and P F are defined similarly to P A and P B , respectively. Therefore, edges with lower age, lower weight, and lower betweenness centrality will be removed.

The basic computational components of reducing the history consist in the computation of BC (we do not distinguish between node and edge BC because the algorithm is the same). Computing the degree, the aging factor of nodes, the weight, and the aging factor of edges has a linear cost on the number of nodes and edges respectively and can be computed incrementally. However, the computational cost of BC is high (for unweighted networks it is O(mn) where n is the number of nodes in the network and m the number of edges). The cost can be significantly reduced by using approximations [START_REF] Geisberger | Better approximation of betweenness centrality[END_REF] and exploiting the structure of the network. In particular in scalefree networks, the BC values do not have to be updated very often with the network growth [START_REF] Gkorou | Betweenness centrality approximations for an internet deployed p2p reputation system[END_REF] and in networks without community structure, the BC of a node shows a strong correlation with its degree. Note that the reputations of nodes are computed by the core reputation mechanism.

Datasets

In order to assess our method for creating the complete history, we consider both synthetic graphs and graphs derived from real networks. In our synthetic complete history graphs we consider two processes occur simultaneously: first, new nodes enter the system, and secondly, the already existing nodes interact, thus creating new links. Thus, we define the probability p c which represents the probability of adding a new node at each time step to the graph, and the probability 1 -p c which represents the probability of adding new links between existing nodes. In highly dynamic systems, the appearance of new nodes is dominant, and so the value of p c is high. In our models for synthetic graphs, we allow the occurrence of multiple edges between a pair of nodes and we consider the number of multiple edges as the weight of that edge.

For our experiments, we create the complete history G and the corresponding reduced history G ′ in parallel. In the complete history, we store all the new information. For the construction of the reduced history we keep its size (almost) constant to a maximum number of nodes n max , which represents the computational or memory limitation of the system. We control the size of the reduced history by removing nodes or edges from the graph as new information is stored as described in the previous section. Below, we describe in detail our models for random graphs and scale-free graphs, the properties of the Bartercast and Citation graph, and the construction of the corresponding reduced histories.

A random graph, denoted by R(n, p r ), is composed of n nodes, and each potential edge connecting two nodes occurs independently with probability p r . Based on this model, we generate a growing directed random graph R(n t , p r ) representing the complete history of interactions.

To create the graph R(n t , p r ) with n t nodes at time t, starting from a single node, we perform the following two operations at each time step:

-With probability p c we add a new node with each of its potential directed edges existing with probability p, for some value of p. -With probability 1 -p c we add pn t new directed edges adjacent to chosen existing nodes uniformly at random. For the proof of p r ∼ p/2p c the reader is referred to Appendix A. In accordance with R, we create the reduced history graph R ′ . The reduced history R ′ is equal to R up to the maximum number of nodes n max . After having reached n max nodes, R ′ is maintained by performing the following operations at each time step:

-When a new node is added to R, we also add this node to R ′ along with its edges, and then we remove one node together with its edges with the highest priority score (Eq. ( 1)).

-When new edges are added to R, we add the same edges to R ′ . Then we remove from R ′ the same number of edges with the highest priority score (Eq. ( 3)). Note that some edges in R may be adjacent to nodes that have been removed from R ′ ; in this case, these edges are not added to R ′ .

Scale-free graphs are characterized by their degree distribution following a power law. We create a growing directed scale-free graph based on the preferential attachment model [START_REF] Barabási | Emergence of scaling in random networks[END_REF]. Similarly to the procedure for random graphs, we generate two directed graphs S and S ′ corresponding to the complete history and the reduced-history.

We create S(n t ) by starting with a small seeding graph with m 0 nodes connected by m 0 -1 edges and then performing the following steps:

-With probability p c we add a new node with m directed edges, with m m 0 . Each edge is adjacent to an already existing node i with probability Π(i) = d i / ∑ j d j , where d i is the degree of node i.

-With probability 1 -p c we add m new directed edges. Each of these edges are adjacent to an existent node i with probability Π(i). One can show that S is scale-free with power-law exponent equal to γ = 1 + 2/(2 -p c ) (see Appendix B for the proof). In line with S, we build the reduced history S ′ using the same procedure as for random graphs.

The Bartercast graph is derived from Bartercast [START_REF] Meulpolder | Bartercast: A practical approach to prevent lazy freeriding in p2p networks[END_REF], the distributed reputation mechanism used in our BitTorrent-based client Tribler [START_REF] Pouwelse | Tribler: a social-based peer-to-peer system[END_REF]. In Bartercast, when a peer exchanges content with another peer, they both store a record with the amount of data transferred and the identity of the corresponding peer. Regularly, peers contact another peer to exchange records using a gossip-like protocol. From the records it receives, every peer i dynamically creates a weighted, directed subjective graph, the nodes of which represent the peers about whose activity i has heard through Bartercast records, and the edges of which represent the total amount of data transferred between two nodes in the corresponding directions.

We have crawled the Tribler system from September 1, 2010 to January 31, 2011, collecting information from 29,716 nodes. In our experimental analysis, we will assume full-gossip in which peers forward the records they receive from other peers, and so all peers eventually receive all the propagated records. Thus, the graph derived from Bartercast, denoted by B, can be considered as the subjective graph of all nodes which corresponds to the complete history. The graph B is not connected and so, we proceed in the analysis using its largest weakly connected component. Bartercast presents high population turnover and thus, the derived graph consists in a dense core with very few long living and active nodes and a periphery with many loosely connected nodes of low activity (small average path length and small clustering coefficient, see Table 1). The addition of new nodes/edges in B is based on the actual timestamps of the crawled database of Bartercast. Similarly to the procedure for random and scale-free graphs, we maintain the reduced history B ′ by removing nodes and edges using Eqs. ( 1) and (3) as new nodes and edges are added according to the timestamps. The author-to-author Citation graph, denoted by C, is derived from the citation network of 21,858 papers published in Physical Review E from January 2001 to November 2011. Its vertices represent the authors of papers and edges represent the citation relationship between two authors (or coauthors). The weight of an edge indicates multiple citations from one author to another. Unlike Bartercast, the graph C is derived from a centralized system with global reputations. In Table 1, we can see that graph C exhibits small-world behavior with small average path length and large clustering coefficient. Its degree distribution has a power-law tail with exponent γ = 2.55. As described for the Bartercast graph, we create the complete history C and the corresponding reduced history C ′ based on the actual timestamps in the database of the Citation graph.

Computation of Reputations and Evaluation Metrics

We consider two methods for computing reputations: the max-flow algorithm and the eigenvector centrality. However, our approach can be generalized to other methods for computing reputations as well.

The max-flow algorithm [START_REF] Cormen | Introduction to Algorithms[END_REF] computes the maximum flow passing between two nodes and is the core of many reputation systems (such as Bazaar [START_REF] Post | Bazaar: Strengthening user reputations in online marketplaces[END_REF], Bartercast [START_REF] Meulpolder | Bartercast: A practical approach to prevent lazy freeriding in p2p networks[END_REF], and the system proposed by Feldman et al. [START_REF] Feldman | Robust incentive techniques for peer-to-peer networks[END_REF]) because it provides resilience to misreporting by nodes who may exaggerate their contributions to increase their reputations. In our study, we use the definition of reputation of Bartercast mechanism [START_REF] Gkorou | Betweenness centrality approximations for an internet deployed p2p reputation system[END_REF] since we use a graph derived from it for the evaluation of our approach. The reputation of a node j is computed as arctan(f ji -f ij )/(π/2), where node i represents the node with the maximum betweenness centrality, f ji represents the maximum flow from node j to node i in the network and f ij is the maximum flow in the reverse direction. The function arctan in the computation of reputations emphasizes the differences of flows close to 0 (neutral reputation), so that newcomers with only a small contribution can achieve a good reputation value and participate in the system. Every reputation value is normalized with the factor π/2 so that it is in (-1, 1).

Eigenvector centrality is a well-studied metric for the importance of a node in a network and its variants constitute the core of many reputation and recommendation mechanisms (such as EigenTrust [START_REF] Kamvar | The eigentrust algorithm for reputation management in p2p networks[END_REF], PageRank [START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF], TrustRank [START_REF] Gyongyi | Combating web spam with trustrank[END_REF] and many others). The basic idea of eigenvector centrality is that interactions with highly reputed nodes contribute more to the reputation of a node. In our analysis, we use PageRank computed using the power iteration: r t+1 = dAr t + [(1 -d)/N ]1, where A represents the normalized adjacency matrix of the network, r t the ranking vector at time step t, d the damping factor (we set it equal to its typical value 0.85 [START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF]), N the number of nodes, and 1 the vector of length N containing only ones. In some networks like Bartercast, an incoming edge of a node has a negative meaning for the reputation of that node (because a weighted edge represents the amount of transferred data and so, adds to the reputation of the donator of the data). Therefore, in these networks, first we reverse the direction of links before we apply PageRank (reverse PageRank [START_REF] Bar-Yossef | Local approximation of pagerank and reverse pagerank[END_REF]).

The evaluation of our method is based on the observations that for the vast majority of reputation systems, the ranking of nodes according to their reputations is more important than the actual reputation values themselves, and that in many systems the identification of the highest ranked nodes is more important than of the rest of the nodes. Therefore, we define the ranking error as the difference between the rankings of the nodes according to their reputations in the reduced history and the complete history. More precisely, we consider the sequences of the Unique Identifiers (UIDs) of the nodes in the reduced and the corresponding complete history of our graphs, and we compute the minimum number of inversions of consecutive elements needed in the sequence of the reduced history to get all the common nodes in their correct order in the complete history. This minimum number of inversions is then normalized over the worst case, which would occur if the ranking would be completely reversed. Furthermore, to explore the ability of the reduced history to identify the highest ranked nodes, we define a second metric called the ranking overlap which is defined as the fraction of nodes the sequences of the top-5%, 10% and 20% ranked nodes in the reduced history and the corresponding sequences in the complete history have in common. More precisely, we compute the ranking overlap as |U ∩ V|/|U|, where U is the set of the top-5%, 10% and 20% ranked nodes in the reduced history and V is the set of the top ranked nodes in the complete history of size |V| = |U|.

Evaluation

In this section, we present our experimental evaluation. First, we explore the effect of each of the parameters for node and edge removal separately and in combination. Next, we study the effect of the size of the reduced history relative to the size of the complete history. Finally, we evaluate the effect of the growth of the complete history while the size of the reduced history is constant. In our experiments, we use the synthetic and real-world graphs introduced in Section 4. Our synthetic graphs consist of 5, 000 nodes with α and p c neutral (both equal to 0.5), unless other initializations are mentioned. We choose the other parameters for the random graph (p r = 0.02) and the scale-free graph (m = 3 and γ = 2.2) so that they roughly correspond to the Bartercast graph. For the synthetic graphs, our results presented in each plot are the average of 25 independent experiments, while for the Bartercast and Citation graphs, we conduct only one experiment since we have only one instance of these real-world graphs.

Experiments and Results

We first explore the effect of the parameters for node and edge removal defined in Section 3 on the ranking error. To explore the effect of the parameter α, we remove 50% of the nodes and edges of the complete history according to Eqs. ( 1) and ( 3) for different values of α. Due to space limitations we omit the corresponding figure. We find that α does not affect the performance of the reduced history much. In particular, for random graphs using max-flow (or Pagerank), the ranking error Fig. 1: The effect of the parameters for node and edge removal when removing a fraction of the nodes and edges of CH for random and scale-free graphs when the reputation algorithm is max-flow (left) and Pagerank (right). The indication ER in the legend denotes parameters for edge removal and NR parameters for node removal.

starts at 0.33 (or 0.21) for α equal to 0, and it slightly decreases by 0.02 (or 0.01) until α is equal to 0.8. As α increases further, the ranking error increases by 0.07 (or 0.06).

A similar stable behavior for the ranking error is observed for the scale-free and realworld graphs. Since α doesn't affect the performance of the reduced history much we take it as neutral, equal to 0.5, for all the following experiments. Next, we explore the effect of the parameters for node and edge removal separately, and their combination as defined by Eqs. ( 1) and (3). For the parameters for node or edge removal, we remove fractions nodes or edges of the complete history using only one parameter at a time. The effect of these parameters on the ranking error is plotted in Fig. 1 for the random and scale-free networks. We observe that creating the reduced history using only node removal results in similar performance as edge removal for the corresponding parameters. This is to be expected as there is a correlation between these parameters: in general, an edge with high BC is adjacent to nodes with high BC, an old edge is attached to old nodes, and an edge with a large weight is adjacent to a node with high reputation. Furthermore, the combination of all parameters in Eqs. ( 1) and (3) results in the smallest ranking error. The largest ranking error occurs when we remove nodes based on their age. The reputation of a node depends on the period it participates in the system and thus, when only new nodes with low reputations participate in the reduced history, the ranking error is high. All the other parameters cause quite similar ranking errors because they exhibit correlations in graphs without strong community structure, such as the random and scale-free graphs. In the real-world graphs, the parameters for node and edge removal and their combination exhibit similar relative performance as in the scale-free graphs. We omit the plot for the real-world graphs due to space limitations. Since the combination of the parameters for node and edge removal achieves the lowest ranking error, we use it to create the reduced history for all the following experiments.

We next evaluate the effect of the size of the reduced history relative to the size of the complete history on the ranking error and the ranking overlap. For this purpose, we construct reduced histories of different sizes for a complete history of fixed size as described in Section 4. Fig. 2 of the reduced history. We observe that when using max-flow, the scale-free, Bartercast and Citation graphs exhibit much smaller ranking error than the random graphs. For all the graphs using Pagerank, the reduced history exhibits smaller ranking error than using max-flow. Fig. 3 plots the ranking overlap for different relative sizes of the reduced history. The scale-free and Bartercast graphs exhibit much higher ranking overlap than the random and Citation graphs when using the max-flow based algorithm. Particularly, in these networks the ranking overlap decreases quite slowly with the decrease of the size of the reduced history, until the size of the reduced history is about 0.4 of the complete history. The reason is that these networks have a large amount of redundant information for approximating the highest ranked nodes when using the max-flow algorithm. When the size of the reduced history is smaller than 0.3 of the complete history, the ranking overlap degrades quickly. With Pagerank, the reduced history exhibits very low ranking overlap for all the graphs. Finally, we evaluate the effect of the growth of the complete history while the reduced history is of constant size on the ranking error and the ranking overlap. For the synthetic graphs, we let the complete history grow from 500 to 5, 000 nodes while we Scale-Free Graph keep the size of the reduced history constant at 500 nodes. For the real-world graphs, using the available temporal information, we have the Bartercast graph grow from 1, 063 to 10, 634 nodes with the reduced history constant at 1, 063, and the Citation graph from 1, 536 to 15, 360 nodes with the reduced history at 1, 536. Fig. 2 (right) plots the ranking error and Fig. 4 plots the ranking overlap for different relative growths of the complete history. We observe again that Pagerank achieves a smaller ranking error while the max-flow based algorithm achieves a better ranking overlap, specially for the scale-free and real-world graphs.

Discussion

The observations arising from our experiments indicate that the reduced history can give a good approximation of the ranking of nodes according to their reputations when the complete history exhibits a particular structure. In this subsection, we explain and discuss our main observations. First, we observe that constructing the reduced history using the combination of all the parameters for node and edge removal results in the lowest ranking error. Considering only parameters such as degree and reputation gives priority for removal to the newest nodes and so, new nodes will not participate in the reduced history. On the other hand, considering only the age as parameter for removal results in high ranking error because then, only new nodes participate in the reduced history and information of old important nodes has been removed. Therefore, for good performance of the reduced history, it is required to use a combination of these parameters as defined by Eqs. ( 1) and (3).

Secondly, the performance of the reduced history depends on the topology of the graph, and is better in the scale-free, Bartercast and Citation graphs than in the random graphs. The scale-free and our real-world graphs have only a few well connected nodes accumulating the majority of links, while the vast majority of nodes has a very low connectivity. In the reduced history, the highly connected nodes are preserved keeping their good ranking position, while most of the loosely connected nodes have been removed. In contrast, in random graphs all nodes have stochastically similar connectivity properties. Since most real networks exhibit heterogeneity in the connectivity properties of their nodes [START_REF] Amaral | Classes of small-world networks[END_REF], we can conclude that the reduced history can be applied in a large range of networks.

Finally, the performance of the reduced history depends on the reputation algorithm used. In particular, it causes a lower ranking error when using Pagerank, while it achieves a higher ranking overlap when using max-flow. Pagerank computes the reputation of a node by aggregating the interactions of all nodes participating in a graph. The aggregative computation of centrality by Pagerank achieves lower ranking error even if the reduced history has a relatively small size. Unlike Pagerank, the max-flow based algorithm computes the reputation of a node taking into account only the interactions between that node and the most central node. Since both the most central and the highest ranked nodes are considered as important, they are preserved in the reduced history. Therefore, we achieve a high ranking overlap when using the max-flow based algorithm.

In conclusion, our observations demonstrate the effectiveness of the reduced history in approximating the ranking of nodes with Pagerank and in identifying the highest ranked nodes with the max-flow based algorithm. This implies that the reduced history can approximate with reasonably accuracy the complete history in real world graphs, while it has much smaller resource requirements. As we stated in Section 2, this result is valuable especially for decentralized systems, such as Tribler, because of the limited resources available at each node.

Related work

The observations of our experiments are consistent with the findings of prior published research for the robustness of centrality measures under sampling or missing data. In particular, our finding that node and edge removal cause similar ranking errors has been discussed in the context of the robustness of centrality measures under missing data [START_REF] Borgatti | On the robustness of centrality measures under conditions of imperfect data[END_REF]. In the context of network sampling, it has been observed that ranking nodes with eigenvector centrality is highly robust [START_REF] Costenbader | The stability of centrality measures when networks are sampled[END_REF]. Moreover, the result that the use of BC for node and edge removal does not affect the ranking error much, has been also observed under the context of edge removal for security reasons [START_REF] Zeng | Removing spurious interactions in complex networks[END_REF]. However, our approach is different from sampling techniques, since sampling techniques focus on creating a static subgraph with similar properties as the original graph. In our case, we need to maintain the reduced history dynamically with the growth of the original graph, and we are interested in producing a reduced history that preserves the reputations of nodes and not necessarily the general properties of the original graph.

Conclusion and Future Work

Using the complete history of interactions in a reputation system is not efficient due to its high computational cost and high memory requirements, and to the high population turnover. We have proposed the use of the reduced history instead of the complete history defining the main parameters for choosing the nodes participating in it. Next, we have evaluated our approach experimentally exploring both theoretical graph models and real-world graphs using two reputation algorithms, a max-flow based algorithm and Pagerank. We conclude that for scale-free and real-world graphs, the reduced history is reasonably accurate while for random graphs, due to their structural properties, the reduced history causes high error. Furthermore, we have demonstrated that using the max-flow based algorithm results in better identification of the highest ranked nodes while using Pagerank results in better ranking error. An interesting direction for future work is the evaluation of the reduced history using only the local information available at each node in a decentralized environment.

Fig. 3 :

 3 Fig. 3: The effect of the size of RH relative to the size of CH for max-flow (top) and Pagerank (bottom).

Fig. 4 :

 4 Fig. 4: The effect of the growth of CH relative to the size of RH for max-flow (top) and Pagerank (bottom).

Table 1 :

 1 The average path length (L) and the clustering coefficient (cc) of the largest connected component of the Bartercast and Citation graph, and of the corresponding random graphs with similar average path length.

	Graph	# Nodes # Edges L	cc	L rand cc rand
	Bartercast 10, 634	31, 624 2.64 0.00074	2.63	0.0032
	Citation 15, 360 365, 319 3.29 0.1098	3.31	0.0012

  (left) plots the ranking error for different relative sizes The effect of the size of RH relative to the size of CH (left) and the effect of the growth of CH relative to the size of RH (right).

			Max-flow			Pagerank				Max-flow				Pagerank
								Bartercast	0.45
	0.4							Citation Random	0.40
	ranking error 0.2 0.3							Scale-Free	0.20 0.25 0.30 ranking error 0.35
	0.1									0.15 0.10			Bartercast Citation Random Scale-Free
	0.2	0.4	0.6	0.8	0.2	0.4	0.6	0.8		2	4	6	8	10	2	4	6	8	10
			size of RH relative to the size of CH						growth of CH relative to the size of RH
	0.0 0.1 0.6 0.7 Fig. 2: size of RH relative to the size of CH Random Graph 0.2 0.4 0.6 0.8 Scale-Free Graph 0.2 0.4 0.6 0.8 Bartercast Graph 0.2 0.4 0.6 0.8 0.2 0.3 0.4 ranking overlap 0.5	0.2	Citation Graph 0.4 0.6 top-5% top-10% top-20%	0.8
				Random Graph		Scale-Free Graph	Bartercast Graph		Citation Graph
		0.7
																top-5%
		0.6														top-10%
	ranking overlap	0.2 0.3 0.4 0.5														top-20%
		0.1
		0.0
			0.2	0.4	0.6	0.8	0.2	0.4	0.6	0.8	0.2	0.4	0.6	0.8	0.2	0.4	0.6		0.8
								size of RH relative to the size of CH

Data available to us after request to American Physical Society

A Proof for Probability of Connectivity for Random Graphs

We start with one initial node with no edges. Then, we start building our graph as described in Section 4, and at time t > 0, the expected number of nodes is n t = 1+p c t. Since the probability of connection is p, the expected number of edges at time t is:

). Thus, the probability of connection in the random graph is equal to E(t)/(n t (n t -1)) ≈ (pp c t 2 /2)/(p 2 c t 2 ) = p/2p c for large t, which proves that our procedure described in Section 4 creates a random graph R(n t , p/2p c ).

B Proof for the Exponent of our Scale-free Graphs

The proof of S being a scale-free graph is based on the mean-field theory proposed by Barabási and Albert [START_REF] Barabási | Emergence of scaling in random networks[END_REF]. With p c = 1 we have the classic Barabási-Albert model, where only a new node is added and the exponent of power-law is γ = 3. We start with one initial node and then, to construct our scale-free graph, we follow the constructive process described in Section 4. With probability p c we add a new node with m edges, and so the degree of node i, denoted by d i , changes with rate:

With probability 1 -p c we add m new directed edges and the degree of node i changes with rate: ∂di ∂t = 2md i / ∑ j d j . Therefore, in total:

Moreover,

, where E(t) is the number of edges in the graph at time t, so we can solve Eq. ( 4) for d i and find:

where t i represents the time that node i joined the network. Using Eq. ( 5), the probability P [d i (t) < d], that a node i has a connectivity d i smaller than d, can be written as

) . We assume that each operation of either adding a new node or a set of edges takes one unit of time, and so the probability density of t i is P i (t i ) = 1/(m 0 + t i ). Thus,

The degree distribution is the probability density for P (d), thus we obtain:

and as a consequence, for large t, P (d) ∼ d -γ with γ = (2/(2 -p c ) + 1).