Fabio V Hecht
email: hecht@ifi.uzh.ch

Flávio Thomas Bocek
email: bocek@ifi.uzh.ch

Roberto Santos
email: santos@ifi.uzh.ch

Burkhard Stiller
email: stiller@ifi.uzh.ch

Flávio Roberto Santos

Playback Policies for Live and On-Demand P2P Video Streaming

Keywords: P2P, live streaming, video on demand, playback policies

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

Introduction

The peer-to-peer (P2P) paradigm has been successfully applied to increase scalability and decrease cost for the publisher of video streams on the Internet [START_REF] Hei | A Measurement Study of a Large-Scale P2P IPTV System[END_REF]. Since users of a P2P system already collaborate on distributing video streams, LiveShift [START_REF] Hecht | LiveShift: Mesh-Pull P2P Live and Time-Shifted Video Streaming[END_REF] makes further collaboration possible by allowing peers to store received video streams and distribute them in the future, thus enabling time shifting or -if the combined storage is large -even video-on-demand (VoD). This gives users the freedom to, without having previously prepared any local recording, watch any program from an arbitrary position in the time scale, skipping uninteresting parts until seamlessly catching up with the live stream as desired.

Content availability in any video streaming system is affected by network and server conditions, possibly causing content not to be downloaded on time to be played. The challenge increases in P2P systems due to, e.g., poorly managed networks, asymmetric bandwidth of peers, traffic-shaping at Internet service providers, free-riding, limited view of peers, and the fact that users change their interest frequently -switching channels and, in case of LiveShift, also time shifting. Content may even be available in some peers, but not downloaded before playback, because these peers have allocated all their upload capacity to serve other peers. In this paper, the term content availability is thus defined as content that is downloaded before its playback deadline.

The playback policy is the decision on, when content is unavailable, whether to stall playback, or skip to a block that has already been downloaded. Though any P2P video streaming system needs to implement a playback policy, current systems either omit this information, or adopt an arbitrarily-defined policy. Up to the authors' knowledge, this paper's work is the first aiming specifically at investigating and comparing the effect of different playback policies.

The two main research questions this paper addresses are (1) do different playback policies affect user experience in a P2P video streaming system, and (2) which playback policies are most suitable for live and on-demand scenarios? In order to answer these questions, this paper briefly overviews P2P video streaming and introduces key terminology in Sect. 2. Section 3 displays the related work survey on playback policies used by different live and on-demand P2P video streaming systems. Based on this, a classification and generalization of different playback policies are presented in Sect. 4, enabling a meaningful comparison among them. These policies have been implemented in LiveShift; Sect. 5 presents their evaluation and comparison under a variety of carefully-selected scenarios and parameters. Finally, Sect. 6 concludes this paper.

Background and Terminology

LiveShift, like most widely-deployed P2P video streaming systems, employs the mesh-pull approach [START_REF] Hei | A Measurement Study of a Large-Scale P2P IPTV System[END_REF][START_REF] Magharei | Mesh or Multiple-Tree: A Comparative Study of Live P2P Streaming Approaches[END_REF], which consists on dividing the stream into blocks that are announced and exchanged directly between peers with no fixed structure.

Figure 1 illustrates various terms used in this paper, and Table 1 defines nomenclature. In LiveShift, blocks have a fixed length L in the time scale. A viewing session starts when a user chooses a channel and starting time t 0 (the current time, if live streaming). While the user holds on to (i.e. watches) a channel, the system attempts to locate and download the corresponding blocks. Ideally, the user would experience perfect playback, that is, without interruptions, the block to be played b p (t) would be obtained based on the playback position t: However, due to lack of content availability, the playback experienced by the user at t is the block b e (t), as given by ( 2), where n sk (t) is the number of skipped blocks and t st (t) is the time stalled from t 0 until t.

b p (t) = t/L (1)
b e (t) = n sk (t) + (t -t st (t))/L (2)
Performing initial buffering corresponds to stalling playback until the playback buffer accumulates a number of blocks (typically a fixed configuration parameter), as an attempt to reduce the chance of skipping or stalling during playback. The start-up delay is the experienced stalling time caused by initial buffering. The playback deadline determines the time that a particular block is due to be played, according to the playback policy. The term playback lag is commonly defined for live streaming as the elapsed time from the moment a block is generated at the source until it is played at the peer side [START_REF] Liang | Is Random Scheduling Sufficient in P2P Video Streaming?[END_REF]. In LiveShift, the concept of playback lag is extended also for viewing time-shifted streams; playback lag is thus defined by (3) as the time difference between the block that is playing, according to the playback policy used, and the block that would be playing, if there were no interruptions from the moment the user pressed the play button. This extension in the definition of playback lag preserves its original concept of measuring the overall ability of the system of locating and downloading content, while being applicable to non-live viewing as well. Liveness is a general term that stands for low playback lag.

t lag (t) = (b p (t) -b e (t)) * L (3)
While both stalling and skipping negatively impact user-perceived video quality, their impact is different. On one hand, when stalling occurs, the video stream is interrupted and playback lag is increased. Besides, peers with higher playback lag lose their ability of providing streams with more liveness to other peers, negatively impacting the entire system. On the other hand, when skipping occurs, image quality might be impaired. Besides, since skipped blocks are not downloaded, they cannot be uploaded to any other peer, creating buffer "holes" that may harm the distribution overlay. In both cases, peers need a larger number of providers to compensate for those missing blocks, which may be challenging, since upload capacity is typically a rare resource in such systems [START_REF] Hei | A Measurement Study of a Large-Scale P2P IPTV System[END_REF].

Related Work

Though the implementation of a playback policy is required in any video streaming system, it is often omitted from their specification. Works that do describe the adopted playback policy are introduced in this section.

The most popular P2P live video streaming applications, such as Sop-Cast [START_REF]SopCast -Free P2P Internet TV[END_REF], are proprietary and do not disclose in detail their policies. Measurement works [START_REF] Sentinelli | Will IPTV Ride the Peer-to-Peer Stream?[END_REF], though, suggest that these systems, after performing initial buffering, employ a window that moves at constant speed, skipping all blocks that are not downloaded on time. The assumption is that, since streaming is live, maintaining liveness is more important than attempting to play every single block. It also helps keep peers mutually interested in a narrow content window. Such policy is also used on works that model live P2P systems [START_REF] Kumar | Stochastic Fluid Theory for P2P Streaming Systems[END_REF].

For VoD, the assumption is frequently the opposite. Since liveness is not important, an intuitive policy would be, after performing initial buffering, stall every time a block to be played is missing. In a P2P system, though, such policy could cause playback to stall for a very long time in case there are a few very rare blocks. The VoD P2P client Tribler [START_REF] Mol | Free-riding, Resilient Video Streaming in Peer-to-Peer Networks[END_REF] addresses this issue by stalling playback only if less than 50% of a 10-second playback buffer is filled; otherwise, it skips to the next available piece.

The work presented in [START_REF] Mol | The Design and Deployment of a BitTorrent Live Video Streaming Solution[END_REF] also uses Tribler for VoD, but adopts a different policy. Playback is stalled until a 10-second-long buffer is filled and the remaining download time is less than the duration of the video plus 20%. The policy does not allow skipping.

Gridcast [START_REF] Cheng | GridCast: Improving Peer Sharing for P2P VoD[END_REF] is a P2P VoD system which playback policy consists on stalling if a block is not available at its playback deadline, while attempting to play it up to 10 times. If the block still has not been downloaded, playback skips to the next block. Initial buffering is 10 seconds, and each block is 1 second long.

LiveShift [START_REF] Hecht | LiveShift: Mesh-Pull P2P Live and Time-Shifted Video Streaming[END_REF] adopts a unified policy for live and on-demand streaming which consists on skipping n contiguous missing blocks if and only if the peer holds at least 2n contiguous blocks immediately after those, otherwise stalling. It aims not to let peers stall for long in case only a few blocks are not available from current neighbors, while skipping if there is a good chance of continuing playback without interruptions.

While these works discuss briefly the playback policy adopted, they do not offer a plausible proof or justification to why such algorithms and parameters were chosen in the foreseen scenarios.

Playback Policies

This section describes and generalizes a set of four playback policies based on the related work survey presented in Sect. 3, plus a new Catchup policy, enabling a fair and meaningful comparison among them. Analysis and discussion on respective trade-offs in both live and on-demand scenarios are as well performed.

Always Skip and Skip/Stall Policies

The Always Skip policy, commonly used for live streaming, consists on always skipping missing blocks to maintain liveness. It is defined by P as = (ℓ, α), where ℓ represents the size of the playback buffer (in blocks), and α ∈ (0, 1] corresponds to the share of blocks that the buffer must hold before starting playback. After the first block has been played, buffered blocks are attempted to be played sequentially and at constant speed. Missing blocks are immediately skipped; however, if the buffer is empty, playback stalls to perform again initial buffering. This is done so peers adapt their playback position b e (t) according to the blocks that can be found at -and downloaded from -currently known peers.

The Skip/Stall (sk) policy is an extension to the Skip policy to allow stalling as in Tribler [START_REF] Mol | Free-riding, Resilient Video Streaming in Peer-to-Peer Networks[END_REF]. It is defined as P sk = (ℓ, α, β), which introduces the β ∈ [0, 1] coefficient, such that, when a block at b e (t) is missing and the buffer is not empty, the system stalls playback until a share β of the playback buffer is filled; then, it skips to the next available block. The Always Skip policy is, thus, an instance of the sk policy when β = 0.

Remaining Download Time Policy

Especially for VoD, it is reasonable to define a playback policy that depends on the remaining download time, so stalling is reduced for users with a fast network, while buffering increases with slower networks. The Remaining Download Time (rd) policy stalls playback until the remaining download time t d ≤ t p , the remaining movie length. In order to apply this policy to LiveShift, the concept of remaining playback time must be defined, since the stream ahead of playback position may be very large -it extends until the current (live) time. Hence, t p is a parameter that may be set to, e.g., 30 minutes of video that buffering will attempt to guarantee playback for.

The rd policy can be modeled as P rd = (ℓ, α, β, t p ) by using the same algorithm as defined for the sk policy, but using a variable buffer size ℓ ′ , calculated based on the parameters t p and ℓ, instead of ℓ directly. Infinite geometric series are used to calculate how long the playback buffer would last, since the application continues to download blocks while the buffer is being used. If i represents the incoming block (i.e. download) rate, and L being block length, let r represent the relative incoming block rate, such that r = i * L; thus, if r = 1, the peer is downloading blocks at a rate exactly enough to keep normal playback. The variable buffer size ℓ ′ can therefore be calculated as shown in [START_REF] Cheng | GridCast: Improving Peer Sharing for P2P VoD[END_REF], where ℓ is used both for initial buffering and as a general lower limit of the buffer size (when, for example, r ≥ 1). The coefficient α is present in the equation to preserve the semantic of remaining download time, since only a share α of the buffer is required by the playback policy to be held in the buffer.

ℓ ′ = max t p L × (1 -r) α , ℓ (4)

Retry Policy

The Retry (re) playback policy is similar to the policy implemented in Gridcast [START_REF] Cheng | GridCast: Improving Peer Sharing for P2P VoD[END_REF], and is defined as P re = (ℓ, α, T ). It consists on performing initial buffering, then stalling if the block at playback position t is not available. The system retries playing the missing block up to T times, which brings playback to stall for a maximum of T * L seconds. As soon as the missing block is downloaded, it will be played back; if the stalling threshold is hit, though, playback skips to the next available block.

Ratio Policy

The Ratio (ra) policy aims at skipping blocks only if there is a high chance of then continuing playback without interruptions. It is described as P ra = (ℓ, α, n), where ℓ and α retain their previous meaning. After initial buffering, if the block at playback position is locally held, it is always played. If, however, the block is missing, a ratio 1 : n is given, such that x contiguous missing blocks are skipped, if and only if, at least xn contiguous blocks are held directly after those.

Catchup Policy

The Catchup (ca) playback policy is introduced to keep playback lag very low at the cost of skipping more blocks than other policies. It is defined by P ca = (ℓ, α), where ℓ and α are used to perform initial buffering as in the sk policy. After playback has started, all missing blocks are skipped, as long as the buffer is not empty. When it is indeed empty, playback position is restored to the original one by skipping all blocks responsible for playback lag until b p (t) = b e (t). It is meant to provide a practical limit on the lowest possible playback lag achievable.

Evaluation

All playback policies defined in Sect. 4 have been implemented into LiveShift. Experiments were conducted using the entire LiveShift code in a deployed test-bed of 20 machines [START_REF]Test-bed Infrastructure for Research Activities -Communication Systems Group (CSG)[END_REF]. The main objective was to compare how different playback policies affect user experience of a P2P video streaming system under scenarios with different levels of content availability. Table 2 displays those different scenarios used. Peers are divided in classes according to their maximum upload capacities -while high upload capacity (HU) peers and peercasters (PC) are able to upload at a rate equivalent to 5 times the bit rate of the video stream being transmitted, low upload capacity (LU) peers are able to upload at only 0.5 times the original stream rate. The increasing number of LU peers causes available upload bandwidth to decrease; while Scenario s1 has abundance of total upload capacity compared to the number of peers to be served, in Scenario s4, the chance that peers experience content unavailability is much higher. It is important to note that peers that have unused upload capacity might only hold unpopular content, leading to suboptimal overlay resource usage. Peers are not artificially limited in download bandwidth, and latency between peers was introduced by using a random sample from the King dataset [START_REF] Gummadi | King: Estimating Latency Between Arbitrary Internet End Hosts[END_REF], and enforced using DummyNet [START_REF]Dummynet -Network Emulation Tool for Testing Networking Protocols[END_REF]; the sample contains an average latency of 114.2 ms. This paper only displays results for scenarios s1 and s4, for brevity and because scenarios s2 and s3 produced expected results between s1 and s4. Multiple instances of LiveShift were executed using the same settings as in [START_REF] Hecht | LiveShift: Mesh-Pull P2P Live and Time-Shifted Video Streaming[END_REF]. In short, peers were created with an inter-arrival time of 1 s. Every peer was programmed to repeatedly switch to a channel and starting time t 0 , then hold to the channel, attempting to locate and download blocks. While holding to the channel, every peer reported, once per second, its experienced playback lag t lag (t), as defined in Sect. 2, and share of skipped blocks n sk (t)/(n pl (t) + n sk (t)). Channel popularity and holding time were both characterized by traces, as described in [START_REF] Hecht | LiveShift: Mesh-Pull P2P Live and Time-Shifted Video Streaming[END_REF]. Results were obtained through 10 runs of 20 minutes each.

Due to content unavailability, a peer may sometimes experience very long stalling times. In such cases, it is not realistic to assume that users would wait indefinitely for the content. Thus, when a peer is able to play less than 50% in a moving window of 30 seconds, playback is considered failed, that is, the user is considered to have given up and switched to another (channel, t 0 ). Buffering is not taken into account, since it is part of the playback policy being investigated.

Since the goal of the evaluation is to measure the impact of playback policies in the entire overlay, on each run, all peers were configured to adopt one of the playback policies defined in Sect. 4. Each playback policy, as specified in Table 3, has been investigated using different values for their main parameters, based on values seen in the literature, complemented by additional values that allow a deeper understanding of their effect. To make results better comparable, parameters that apply to all playback policies were kept constant; all experiments were obtained using ℓ = 6 s, α = 0.8, and L = 1 s. The evaluation metrics used are playback lag, share of skipped blocks, and share of failed playback sessions.

Playback Lag

Playback lag is an important metric to evaluate user experience, since a lower value denotes a lower start-up delay, less interruptions, and more closeness to what the user initially intended to watch. It is expected to increase with larger sessions, as well as with lower content availability, due to stalling. Reports from each peer and run were collected and an average was calculated for every 1minute interval. The same proceeding was performed on all runs. The distribution of playback lag among different peers and at different t values was analyzed for each policy. For most peers, playback lag differences for the investigated parameters are consistent, as exemplified in Fig. 2, which shows the CDF of playback lag at 10 min of holding time under the sk policy. Peers, however, with highest playback lag (i.e. above 90 th percentile) suffer from severe content unavailability, as a result of the high channel switching frequency in the defined peer behavior; these peers are not able to download any blocks, so the playback policy cannot play a significant role. Since this occurs as well under all other investigated policies, all playback lag plots on the rest of this section focus on the 80 th percentile, that is, the maximum playback lag experienced by 80% of the peers. Always Skip and Skip/Stall Playback Policies. Experiments with the sk playback policy were made using three different values for the parameter β, as shown in Fig. 3. While the x-axis represents the time t (in minutes) for which a user holds on to a channel, the y-axis represents the playback lag t lag (t) (in seconds). The experiments reveal that the sk playback policy is extremely flexible. It is able to maintain a relatively low playback lag even for longer sessions (higher holding time values) when β = 0 (sk-0, the Always Skip policy).

In Scenario s1, sk-.5 and sk-.75 display very distinct results, yet on Scenario s4 they yield very similar results in terms of playback lag. This is due to the fact that, in a scenario with more available upload bandwidth, peers have more opportunity to perform several parallel downloads, hence the chance that a peer is able to download blocks out of order (thus being able to skip) is higher.

Remaining Download Time Playback Policy. The rd playback policy was instantiated with different values of t p , which is the minimum playback time the policy attempts to guarantee playback for, considering the current download rate. Figure 4 shows that, on the over-provisioned Scenario s1, results differ little with the different parameters evaluated. This is due to the fact that peers can often download at a rate r ≥ 1, therefore ℓ ′ frequently reaches its minimum value ℓ, as ℓ ′ decreases with a higher download rate. In the more bandwidth-restricted Scenario s4, larger values of t p cause higher playback lag with higher holding times, as expected. In comparison with other playback policies, the Remaining Download Time playback policy shows the highest playback lag, which is due to a potentially larger buffer, especially with lower download rates. Retry Playback Policy. The re playback policy was investigated with different values for the parameter T , which expresses the stalling limit per block.

Figure 5 shows that, on both scenarios s1 and s4, while re-1 displays a lower playback lag than re-5 and re-10, it is still higher than levels achieved under the sk policy. The fact that playback lag under re-5 and re-10 policies are very similar is due to the unlikelihood, on both s1 and s4, of situations in which playback needs to stall for longer than 5, but less than 10 seconds, until the block at playback position is downloaded.

Ratio Playback Policy. Results with the ra playback policy were obtained using different values for the parameter n. Figure 6 shows that it has a noticeable impact on the experienced playback lag in the over-provisioned Scenario s1, but not on s4. Like with the sk policy, peers have much fewer opportunity to skip in s4 due to the lower probability of performing parallel downloads. Catchup Playback Policy. The Catchup (ca) playback policy is designed to keep a very low playback lag by resetting it to zero when the playback buffer is empty by skipping the necessary amount of blocks. Results show on Fig. 7 that, as designed, it displays a relatively lower playback lag in comparison to the other policies. Interestingly, while it displays in Scenario s1 a clearly higher playback lag than sk-0, the opposite is observed in s4. This happens due to the much higher probability in Scenario s4 that the buffer becomes empty and the catchup mechanism is therefore triggered. means. The share of skipped blocks is, as expected, inversely proportional to the playback lag shown by each policy, hence sk-0 and ca policies skip more blocks than other policies.

Skipped Blocks

User-experienced image degradation levels vary according to specific video encoding and decoding algorithms (codecs) used -to which LiveShift is agnostic. Understanding both expected levels of skipped blocks and codec characteristics are thus crucial when choosing the appropriate playback policy for a specific situation.

Failed Playback Sessions

The share of sessions in which the peer stalls for such a long time that playback is considered failed represent less than 0.5% of all sessions in Scenario s1, as shown in Fig. 9. In contrast, in Scenario s4, the mean oscillates between 9.5% and 13.5% in all scenarios. The overlapping 95% confidence interval error bars indicate that the share of failed playback depends rather on each scenario's available upload capacity than on the playback policy used. Having observed the behavior of LiveShift under different playback policies, with different parameters, in scenarios ranging from under-to over-provisioned P2P networks, it is evident that different playback policies do affect user experience in a P2P video streaming system, in terms of playback lag and share of skipped blocks. Understanding their behavior is, hence, imperative to select the most appropriate policy for the desired result, whether it is keeping playback lag as low as possible, avoiding skipping many video blocks, or achieving a compromise. The ultimate decision may depend on the type of content being transmitted, or be left completely up to the user.

This raises the second research question, which playback policies are more suitable for live and on-demand scenarios? Under circumstances in which minimizing playback lag is the main goal, which might be desirable by viewers of live (e.g., sports) events, the ca and sk-0 are the most suitable policies studied, considering that they have consistently shown much lower playback lag for a majority of peers compared to all other approaches. This comes, however, at the cost of a higher number of skipped blocks. If lowest number of skipped blocks is the objective, the policies that have shown to skip less than 0.5% of the total blocks on both scenarios s1 and s4 are sk-.75, re-5, re-10, ra-3, ra-5, and all rd policies. These policies may be applied in cases in which occasional interruptions are of less importance than skipping content, for instance for VoD. Alternatively, compromising playback lag and skipped block rate may be the goal. Policies that show a skipped block rate inferior to 0.5% and playback lag inferior or equal to 45 seconds for 15-minute-long sessions (for 80% of peers) are, on the under-provisioned Scenario s4, the following: ra-3, ra-5, re-5, re-10, and sk-.75. In Scenario s1, the ra-3, re-1, sk-.5, and sk-.75 are policies that yield a skipped block rate inferior to 0.5% and playback lag less than or equal to 9 seconds for 10-minute-long sessions, also for 80% of peers.

In all evaluated scenarios, peers adopt a uniform playback policy, which allows for an evaluation of their effect on the entire distribution overlay, if assumed that all users are interested in either live or on-demand characteristics. Future work will investigate scenarios in which peers adopt mixed policies, which are likely in LiveShift. There is also the opportunity of combining characteristics of different policies. A further promising possibility is creating a predictive playback policy that considers past peer experiences to avoid stalling when the probability that a missing block is downloaded in a timely fashion is low.

Fig. 1 .

 1 Fig. 1. Terminology

Fig. 2 .

 2 Fig. 2. CDF of playback lag under Skip/Stall playback policy in scenarios s1 and s4

Fig. 3 .

 3 Fig. 3. Playback lag under Skip/Stall playback policy in scenarios s1 and s4

Fig. 4 .

 4 Fig. 4. Playback lag under Remaining Download Time playback policy in s1 and s4

Fig. 5 .

 5 Fig. 5. Playback lag under Retry playback policy in scenarios s1 and s4

Fig. 6 .

 6 Fig. 6. Playback lag under Ratio playback policy in scenarios s1 and s4

Figure 8 Fig. 7 .

 87 Figure 8 compares the mean share of skipped blocks under the playback policies and parameters investigated. Error bars indicate 95% confidence intervals of the

Fig. 8 .

 8 Fig. 8. Skipped blocks in scenarios s1 and s4

Fig. 9 .

 9 Fig. 9. Failed playback in scenarios s1 and s4

Table 1 .

 1 Nomenclature

	L	Block length (time unit)	ℓ Buffer size (in blocks)
	t0	Session start time	α Initial buffering coefficient
	t	Current playback position	β Stalling coefficient
	bp(t) Block played at t if perfect playback	t d Remaining download time
	be(t) Block played at t	tp Remaining movie length
	t lag (t) Playback lag at t	r Relative incoming block rate
	n sk (t) Skipped blocks from t0 to t	T Maximum retries
	n pl (t) Played blocks from t0 to t	n Minimum block ratio

Table 2 .

 2 Evaluation scenarios

	Scenario	# PC	# HU # LU	Total Peers	Total Upload Capacity
	s1	6	15	60	81	135
	s2	6	15	90	111	150
	s3	6	15	120	141	165
	s4	6	15	150	171	180

Table 3 .

 3 Playback policies and parameters

Acknowledgments

This work has been performed partially in the framework of the of the European FP7 STREP SmoothIT (FP7-2008-ICT-216259) and was backed partially by the FP7 CSA SESERV (FP7-2009-ICT-258138) coordination inputs on incentives.


Julius Rückert
email: rueckert@ps.tu-darmstadt.de

Osama Abboud
email: abboud@kom.tu-darmstadt.de

Thomas Zinner

Ralf Steinmetz
email: steinmetz@kom.tu-darmstadt.de

David Hausheer
email: hausheer@ps.tu-darmstadt.de

Quality Adaptation in P2P Video Streaming Based on Objective QoE Metrics

Keywords: Peer-to-Peer Video Streaming, Quality Adaptation, Quality of Experience, Scalable Video Coding

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

Quality Adaptation in P2P Video Streaming Based on Objective QoE Metrics 1 Introduction

Recent studies show that the streaming of video content has become a dominating part of today's Internet traffic, with a forecast of further increase for the next years [START_REF]Cisco VNI: Forecast and Methodology[END_REF][START_REF]Fall 2011 Internet Phenomena Report[END_REF]. The support of a large number of users as well as a wide range of heterogeneous devices and constantly changing conditions, such as sudden user fluctuations or network congestion, make the provision of appropriate video streaming mechanisms a challenging task. Based on these dynamics, an impact on the provided service quality can sometimes be inevitable. This may become visible to the user in form of degraded video quality or stalling during video playback. The goal of content providers is to reduce both effects to a minimum in order to maximize the service quality. This requires quality adaptations that allow for a flexible reaction to provide the individual users with a continuous playback and a maximum possible video quality. In this context, the video codec Scalable Video Coding (SVC) [START_REF] Schwarz | Overview of the Scalable Video Coding Extension of the H.264/AVC Standard[END_REF] is especially interesting as it allows for flexible adaptation of the video quality in different dimensions. Furthermore, by limiting adaptation decisions to only compatible quality layers, e.g., in terms of bandwidth or screen resolution, heterogeneous clients with different capabilities can be supported in an efficient way.

For quality adaptation during an SVC-based streaming process, the decisions for appropriate layers are essential. Therefore, Quality of Service (QoS) aspects, such as the throughput, are typically taken into consideration to select appropriate quality layers during streaming. However, this approach follows a simplified assumption about video quality and might not directly result in a maximization of the video quality as perceived by a human user. Therefore, the idea proposed in this paper is to extend SVC-based video streaming with the properties of the human visual system in order to judge the influence on the perceived quality, also referred to as Quality of Experience (QoE).

Since the human perception is a complex process and influenced by many factors, only few viable automated metrics, so called objective QoE metrics, exist that can be applied in a general context. At the same time, user studies, which are considered the only reliable alternative to assess perceived quality [START_REF] Mu | An Interview with Video Quality Experts[END_REF], are not applicable in most technical solutions. Therefore, although automated QoE metrics can only approximate the perception of a user [START_REF] Winkler | Digital Video Quality: Vision Models and Metrics[END_REF], they are a promising approach to enable a more user-centric quality adaptation in SVC based video streaming. In the context of the presented approach, the Video Quality Metric (VQM) [START_REF] Pinson | A New Standardized Method for Objectively Measuring Video Quality[END_REF], a state-of-the-art objective QoE metric, is applied.

To investigate the impact of using objective QoE metrics for quality adaptation, the focus of this paper is on a Peer-to-Peer (P2P) based Video-on-Demand (VoD) scenario. Besides evaluating the adaptation mechanisms on its own, the scenario also allows to study how such adaptations influence the dynamics of a P2P system and the resulting overall performance. For large-scale streaming systems, P2P technologies have proven to be a valid alternative to traditional client-server (C/S) solutions. They allow to efficiently leverage resources of enduser devices in order to remove bottlenecks and unburden the content provider from high costs. In principle, the adaptation mechanisms presented in this paper could also be applied in a C/S scenario, however, they were designed to meet the specific requirements of a highly distributed scenario, with clients autonomously deciding on adaptations according to their needs.

The remainder of this paper is structured as follows. In Sect. 2, an overview about existing work in the field is provided. The QoE-aware adaptation mechanism, which is the main contribution of this paper, is introduced in Sect. 3. Subsequently, in Sect. 4, the evaluation of the mechanism is presented. Finally, the paper is concluded in Sect. 5.

Related Work

The topic of quality adaptation in the context of multi-layer and SVC-based video streaming has been broadly studied before. A number of researchers have investigated the general applicability of multi-layer video coding and especially SVC to P2P video streaming [START_REF] Cui | Layered Peer-to-Peer Streaming[END_REF][START_REF] Mokhtarian | Analysis of peer-assisted Video-on-Demand Systems with Scalable Video Streams[END_REF]. Others proposed concrete SVC-based systems to address specialized issues, such as low start-up or streaming delays, or smooth video playback, while trying to assure a minimum video quality [START_REF] Baccichet | Low-delay Peer-to-Peer Streaming using Scalable Video Coding[END_REF][START_REF] Lee | Live Video Streaming Using P2P and SVC[END_REF][START_REF] Mushtaq | Smooth Video Delivery for SVC based Media Streaming over P2P Networks[END_REF]. In contrast to the approach presented in this paper, none of these works considers QoE characteristics of the content.

In a previous work, the authors evaluated the impact of quality adaptation mechanisms in SVC-based P2P streaming systems [START_REF] Abboud | On the Impact of Quality Adaptation in SVC-based P2P Video-on-Demand Systems[END_REF]. These purely QoS-driven mechanisms were considered and further extended in the context of the presented work to allow for more sophisticated adaptations, also considering QoE aspects.

The QoE during streaming clearly depends on the visual quality of the delivered content. Furthermore, it is also influenced by characteristics of the video streaming process and the quality adaptation mechanism itself. Zinner et al. [START_REF] Zinner | Impact of Frame Rate and Resolution on Objective QoE Metrics[END_REF] derived dependencies between SVC quality layers of different videos and their objectively assessed QoE in terms of the Video Quality Metric (VQM) [START_REF] Pinson | A New Standardized Method for Objectively Measuring Video Quality[END_REF]. This paper is directly based on this work and uses the results as an input for the presented adaptation mechanism. Lee et al. [START_REF] Lee | Subjective Quality Evaluation via Paired Comparison: Application to Scalable Video Coding[END_REF] conducted subjective studies to model the dependencies between SVC quality layers and perceived quality. Others, such as Gustafsson et al. [START_REF] Gustafsson | Measuring Multimedia Quality in Mobile Networks with an Objective Parametric Model[END_REF], considered more streaming process related issues and evaluated the impact of buffering events on the perceived quality. Zink et al. [START_REF] Zink | Subjective Impression of Variations in Layer Encoded Videos[END_REF] focused on the role of different layer adaptation characteristics.

Zhai et al. [START_REF] Zhai | Three Dimensional Scalable Video Adaptation via User-End Perceptual Quality Assessment[END_REF] proposed a centralized live SVC video streaming system for wireless, heterogeneous clients that aims at maximizing the QoE. While this work shares the objective of the presented approach to use objectively assessed quality, it greatly differs in its C/S scenario and the quality estimation by clients, using own simple objective QoE metrics and local knowledge of the peers. In the context of the presented VoD scenario, it is assumed that content providers could do a pre-processing and this way profit from more sophisticated quality assessments. Furthermore, Kim et al. [START_REF] Kim | An Objective Perceptual Quality-Based ADTE for Adapting Mobile SVC Video Content[END_REF] also proposed a SVC streaming system to maximize the QoE of the users. This approach builds on a centralized dissemination and decision taking approach, where a central entity estimates the perceived quality of a client by using own specialized objective QoE metrics and decides on switching to higher quality layers.

Menkovski et al. [START_REF] Menkovski | Machine Learning Approach for Quality of Experience Aware Networks[END_REF] described an adaptation mechanism for a distributed streaming system to maintain acceptable video quality. Therefore, direct user feedback and distributed machine learning mechanisms are used to detect unacceptable quality and react by improving the streaming quality. In contrast to the presented work, they do not consider the use of layered video coding but utilize parameters of single layer codecs, including only limited means of adaptability in quality. Furthermore, the approach is limited to two levels of perceived quality which does not allow accounting for heterogeneous clients and fine granular adaption of the video quality.

3 QoE-aware Quality Adaptation This section presents how Quality of Experience (QoE) estimation of SVC encoded videos can be used by quality adaptation algorithms to achieve better system performance. Therefore, QoE-aware quality adaptation mechanisms are proposed, designed, and evaluated, that expand the use of classical QoS-driven mechanisms to include other metrics that are closer to how users perceive video quality. What is especially interesting for the performed analysis, is checking whether using estimated QoE in quality layer decisions has any impact on the dynamics of the P2P network and how this influences the performance. For the best of our knowledge, this question has not yet been addressed.

In order to bring QoE to the quality adaptation algorithms in SVC-based VoD systems, an approach is devised that constitutes two major steps: the Quality Management running on a server and the Layer Adaptation running on the peers. The first step is executed by the content provider to derive the QoE ratings for a streamed video. The second step, the actual quality adaptation, takes place in a distributed manner and is autonomously performed by the peers. The quality ratings are disseminated at the beginning of the streaming process and are used by the peers to decide on appropriate video layers during quality adaptations.

Quality Management

The Quality Management step calculates QoE ratings for all SVC layer possibilities of the streamed videos, using an objective QoE metric. This step, depending on the used metric, might be computationally intensive and it is assumed in the considered VoD scenario, that the processing happens offline, executed by the content provider. Currently, a fixed quality rating for a layer over the whole streaming process is assumed, while for longer videos with changing types of content, also multiple rating sets could be used to account for changing characteristics in the quality rating of different scenes.

In the context of this work, the Video Quality Metric (VQM) [START_REF] Pinson | A New Standardized Method for Objectively Measuring Video Quality[END_REF] has been applied to estimate the QoE for the different SVC layers of a video. This objective QoE metric is considered to be state-of-the-art as it was independently evaluated and has proven to correlate with the human perception of video quality for both TV-like video resolutions [START_REF]Video Quality Experts Group: Final Report on the Validation of Objective Models of Video Quality Assessment, FR-TV Phase II[END_REF] as well as for high definition videos [START_REF] Wolf | Application of the NTIA General Video Quality Metric (VQM) to HDTV Quality Monitoring[END_REF]. Using VQM, deriving the QoE ratings can happen offline without human intervention.

Layer Adaptation

The second step, called Layer Adaptation, extends the QoS-based adaptation mechanisms presented in an earlier work [START_REF] Abboud | On the Impact of Quality Adaptation in SVC-based P2P Video-on-Demand Systems[END_REF]. These mechanisms decide on which SVC layers and blocks to request, considering a client's resources and maximizing the throughput. Their decisions are limited by the static resources of the peers and may change over time according to the available real-time resources to allow for a continuous playback. In the presented work, quality decisions take also into consideration the QoE ratings of the Quality Management step, to always select the quality layer that does not exceed the peers' bandwidth and has the maximum quality. These ratings depend on a specific video and are distributed to the peers together with other meta data. This could be done by the tracker as the overhead is very small and only transmitted once per video and peer. The rating consists of a single numeric value for each SVC layer.

Quality adaptation in the VoD streaming system is done in two phases. First using the Initial Quality Adaptation (IQA) strategy, an initial quality is selected based on the peer's static resources, for example its bandwidth and screen resolution. After the streaming starts, another set of algorithms called the Progressive Quality Adaptation (PQA) makes sure that streaming and video playback are continuous. If needed, the PQA increases or decreases the video quality when the throughput increases or decreases respectively. Both adaptation phases are extended to maximize the quality according to the QoE ratings.

Since the PQA is executed periodically, there is time between two executions for the adaptation process. Motivated by the fact that too frequent layer variation can have an adverse effect on the quality of experience [START_REF] Zink | Subjective Impression of Variations in Layer Encoded Videos[END_REF], mechanisms were developed to switch the layer smoothly. Therefore, two steps have been defined for the actual layer adaptation. The first step is the Layer Decision while the second is the Layer Switching. Both take the QoE ratings as input so that to select layers with the highest quality. The layer decision is executed as part of the PQA in order to select a new layer, the so called target layer. The layer switching step follows by defining an adaptation path that starts from the current layer and smoothly changes the quality to the target layer.

Layer Decision. The Layer Decision mechanism decides on a layer that fulfills a certain criterion. In the context of this work, two different strategies for this are considered and compared. Additional strategies are presented in [START_REF] Abboud | QoE-aware Quality Adaptation in Peerto-Peer Video-on-Demand[END_REF].

The first strategy, called D Bw , has the goal to maximize the bandwidth utilization at the peers and chooses the layer, out of the compatible ones, that has the highest bit rate. This strategy is not QoE-aware as it does not consider any implication on the QoE, rather it focuses on simply fetching the layers with the highest bit rate. This is the state-of-the-art approach for SVC quality adaptation so far and, therefore, used for the sake of comparison and analysis.

The second strategy, called D QoE , constitutes the major contribution of this paper since it uses full knowledge about the QoE ratings of the different SVC layers during quality adaptation. Using the derived QoE rating, as provided by the Quality Management phase, the D QoE strategy works by selecting the layer that maximizes quality and using it as adaptation target layer.

In Fig. 1 a simple example for D QoE based on VQM is presented. For the sake of simplicity, the example is 2-dimensional, comprising only spatial and temporal scalability. According to VQM, a QoE rating ranges between 0 (best quality) and 1 (worst quality). The ratings start off with the lowest value for the highest quality at the upper right most block. The values decrease in any dimensions towards the base layer, which has the lowest quality. The selection algorithm iterates over all layers within the illustrated dashed polygon, which defines the layers that do not exceed the peer's resources, in terms of, e.g., bandwidth or maximum screen resolution. From these layers, the one with the highest QoE rating and, therefore, the best video quality is chosen. Since the time between two adaptation processes can be configured to span several seconds or even minutes, switching between two layers can be done more smoothly by stretching the process over a longer time.

The Layer Switching mechanism defines how to switch to a new layer. In other words, given an old layer A and a new layer B as calculated by the layer decision mechanism, the layer switching algorithms defines the set of layers that have to be passed when switching from A to B. The main reason that motivates a smoother switch is the fact that the perceived video quality can be negatively influenced by too frequent quality switches [START_REF] Zink | Subjective Impression of Variations in Layer Encoded Videos[END_REF]. Therefore, a stepwise adaptation allows to have quality adaptation with smaller steps in between. To avoid having too much layer variation, the mechanism additionally samples the adaptation path in order to put a limit on the amount of steps until the target layer is reached. This process is described at the end of this section.

In the following, the concrete realization of layer switching is presented. The mechanism is referred to as Minimized Absolute Variation in QoE Ratings (S QoE ). For the sake of clarity, configurations without switching are referred to as Simple Layer Switching (S Sim ). In this case, switching is done in a simple step by directly jumping to the adaptation's target layer.

The switching mechanism S QoE uses the variation in QoE ratings of the traversed layers as its minimization metric. Therefore, the goal is to find a path from the old to the new layer which would go through the layers that have the closest QoE ratings. By doing this, the effective quality of the video is changing smoothly between the two layers. In order to implement the switching strategy, graph theory is applied by generalizing the SVC layer model into a graph. Using classical and extensively researched algorithms from graph theory, determines an efficient approach to the problem of minimizing the absolute QoE variation.

The above described problem is related to the so called Single-Source Shortest Paths problems. Prominent solutions to such problems are the well-known Bellman-Ford and Dijkstra algorithms [START_REF]Introduction to Algorithms[END_REF]. The Dijkstra algorithm has been chosen as it exhibits lower complexity and can be easily applied to the presented scenario where the edges between the SVC layers (the variation of QoE ratings) are positive numbers. For the application of the algorithm, in the following the old layer is used as source node while the target layer is used as destination. Before the Dijkstra algorithm can be applied, required for the S QoE algorithm, first a graph needs to be derived from the SVC layer model. The steps of deriving the graph, applying the Dijkstra algorithm, and interpreting the result as adaptation path are illustrated in Fig. 2. To start off, each SVC layer in the layer model is represented as individual node in a graph. Since adaptation is only expected to happen within the set of a peer's compatible layers, in Fig. 2 referred to as QS S,B,C , only the nodes within this set are connected. This way, only supported layers can be reached. Edges are generated by connecting nodes. Since it is considered to switch one layer at a time, each node is only connected to its neighbor nodes that can be reached by adding or removing a single layer in any dimension. Furthermore, the weights of the edges are derived by using the absolute value of the difference between the QoE ratings of the SVC layers presented by the adjacent nodes.

The actual calculation of the switching path is performed by applying the Dijkstra algorithm on the calculated graph. The Dijkstra algorithm ensures that the retrieved path minimizes the switching variation of the QoE ratings.

Sampling the Retrieved Paths. Since the main objective of performing Layer Switching is to have smooth transitions, it is essential not to overwhelm the user with too many layer variations [START_REF] Zink | Subjective Impression of Variations in Layer Encoded Videos[END_REF]. Therefore, it might not be beneficial to switch through all layers along a derived switching path. Thus, a sampling of the derived adaptation path has been introduced to limit the number of jumps in a given time interval. Motivated by Ni et al. [START_REF] Ni | Flicker Effects in Adaptive Video Streaming to Handheld Devices[END_REF], a minimal time of 3 seconds has been chosen per switch. Given a default adaptation interval of 10 seconds, this allows for three steps per adaptation.

Configuration of Strategies.

For the sake of clarity, an adaptation strategy is referred to by the name D x S y , where x denotes the used Layer Decision and y the Layer Switching algorithm. This way, D Bw S Sim , for example, refers to the mechanisms that combine Layer Decision maximizing bandwidth utilization and the simple Layer Switching algorithm.

Evaluation Results

A VoD scenario was considered that comprises nine streaming servers and 100 peers with three different resource classes to reflect peer heterogeneity. The used number of peers has been shown to be typical in content distribution scenarios [START_REF] Kaune | The Seeder Promotion Problem: Measurements, Analysis and Solution Space[END_REF]. The peers differ in their static device properties such as the maximum screen resolution and connection bandwidth. The VoD system uses a mesh-/pullbased dissemination scheme. For an accurate simulation of the transferred video streams, all properties of the videos were derived from real SVC encoded videos. The length of the test video is 300 seconds, which is a typical duration of, e.g., a video shared at YouTube. Peers enter the system with an exponentially distributed arrival time with a mean of 90 seconds. They stay in the system after finishing the streaming process with a probability of 40% for a random time between 0 and 300 seconds. During streaming, progressive quality adaptation takes place every 10 seconds, which has been shown in a previous work to be a reasonable value [START_REF] Abboud | On the Impact of Quality Adaptation in SVC-based P2P Video-on-Demand Systems[END_REF]. All simulations were conducted using the simulation framework PeerfactSim.KOM [START_REF] Stingl | PeerfactSim.KOM: A Simulation Framework for Peer-to-Peer Systems[END_REF]. They were repeated 10 times with different seeds for each configuration, 95-percent confidence intervals are reported for all results. Further details on the simulation parameters and the setup as well as additional scenarios are described in [START_REF] Abboud | QoE-aware Quality Adaptation in Peerto-Peer Video-on-Demand[END_REF].

Evaluation Metrics. For the evaluation, two classes of metrics were used: session metrics, describing characteristics of the streaming process, and SVC video quality metrics focusing on the quality of the delivered video content.

The class of session metrics includes the start-up delay, the total stalling time, the number of stalling events, the number of SVC layer changes, and the SVC layer change amplitude. The start-up delay is the time between starting the streaming process and the time until enough initial data were received to start the playback. The total stalling time is defined by the sum of all stalling event durations over the playback process, including the start-up delay. The number of stalling events describes how often the playback was paused due to missing data. The number of SVC layer changes and the change amplitude describe how often quality layer changes happened and how far jumps between two layers were. The SVC layer change amplitude is defined as follows:

Amplitude (l 1 , l 2 ) = |d 1 -d 2 | + |t 1 -t 2 | + |q 1 -q 2 |, (1)
where l 1 = (d 1 , t 1 , q 1 ) and l 2 = (d 2 , t 2 , q 2 ) describe the two involved SVC layers as triple of their spatial (s), temporal (t), and quality (q) layer dimensions.

For the class of SVC video quality metrics, the relative received layer and the VQM rating were used. The relative received layer describes the ratio of a peer's received SVC layer to its requested maximum layer. A value of 1 denotes that a peer received the video with the maximum requested quality. The VQM rating describes the estimated QoE for the received SVC layers, derived using the objective QoE metric VQM [START_REF] Pinson | A New Standardized Method for Objectively Measuring Video Quality[END_REF]. For this metric a lower value denotes a better quality rating. For clarity, the mapping to the Mean Opinion Score (MOS) is included in the evaluation figures as described by Zinner et al. [START_REF] Zinner | Impact of Frame Rate and Resolution on Objective QoE Metrics[END_REF].

System Capacity. In a first step, the impact of changing server resources on the system performance and the streaming process were assessed. Good provisioning of server capacity is essential for content providers who want to provide good performance but still keep costs low. For the experiments, the upload bandwidth of the streaming servers was used as target parameter. In Fig. 3, a subset of the results are presented, including the start-up delay, total stalling time, relative received quality, and played-out VQM rating.

The following observations can be made for the session quality: Increasing the server capacity yields almost an exponential decrease in the start-up delay for both mechanisms. The QoE-aware mechanism D QoE S QoE shows clear advantage (of one second) over the QoS-based D Bw S Sim mechanism. Starting from 25 Mbps server capacity, a saturation effect can be observed, where adding more capacity does not further decrease the start-up delay. This can be attributed to the time the buffer has to be filled, which is limited by the download speed of the peers and the server capacity. A similar observation can be made for the total stalling time, where both mechanisms show a saturation effect for capacities above 25 Mbps, with the QoE-aware mechanism constantly having a slightly better performance.

For the SVC video quality the following observation can be made: First of all, increasing server capacity enables the peers to better maintain the initially selected layer and this way achieve high relative received quality values. When a content provider is offering a high server upload capacity of 55 Mbps, the relative received quality reaches 80% and 90% for the D Bw S Sim and the D QoE S QoE mechanisms respectively. For the QoE-aware adaptation mechanism this is already achieved starting from 25 Mbps. For content providers it is possible to save precious server resources using the proposed QoE-aware mechanism. Assuming, for example, a target average received layer of 80%, for D Bw S Sim this would require server resources of 35 Mbps, whereas for D QoE S Sim 15 Mbps would be sufficient, resulting in up to 60% reduced server resources. This can be explained by the fact that since the peers are favoring layers with higher VQM ratings, those layers are better replicated, making it easier to retrieve video data from other peers rather than from the server. For the VQM rating, it can be observed that, starting from a 15 Mbps server capacity, the D QoE S QoE mechanisms yields an average played VQM quality of 0.2. This maps to an excellent perceived quality on the MOS scale. D Bw S Sim only achieves a good level of quality.

To sum these results up, it can be concluded that using the QoE-aware mechanism a great reduction of server capacities by up to 60% is possible in comparison to the used non-QoE-aware mechanism, while providing a high level of relative received quality of 80% and improving the VQM to the highest quality level on the MOS scale. Using these results, enables content providers to define a threshold for the relative received quality, or even better the estimated perceived quality in terms of the VQM rating, and provide additional server capacities on demand, if a certain critical limit is about to be violated.

Adaptation Strategies. In a second step, the impact of using the proposed QoE-aware mechanism with and without Layer Switching was evaluated. As described before, the concept of Layer Switching was introduced to allow for a smooth change in layers by using an adaptation path and a stepwise execution.

For the evaluation, again the default configuration was used, this time with a fixed maximum upload bandwidth for each server of 25 Mbps. In Fig. 4, the observed impact of the different adaptation mechanisms on the session quality is shown. As already observed before, using the QoE-aware mechanisms, the total stalling time of the peers can be reduced. While for the non-QoE-ware mechanism D Bw S Sim an average value of about 12 seconds is observable, D QoE S Sim and D QoE S QoE allow for a reduction of more than 2 seconds. The high degree of improvement becomes further apparent in the second used session metric, the number of stalling events. Here reductions of observed stalling events over the whole simulation from values of about 110 for D Bw S Sim , to about 40 for D QoE S Sim , and about 50 for D QoE S QoE could be shown. For D QoE S Sim and D QoE S QoE , this relates to a decrease of more than 50%. In Fig. 5, the impact on two further session metrics is shown. For the number of layer changes due to adaptations, a reduction of more than 50% from the non-QoE to the simple QoE-aware mechanisms is observable. The introduction of Layer Switching, in contrast, led again to a slight rise. This and the results presented before imply that using Layer Switching leads to a reduction of the session quality. In order to, nevertheless, show the impact of this mechanism, the layer change amplitude has been introduced as session metric. The motivation for this was the observation that not only the number of changes but also the step width of changes has an important impact on the perceived quality and should be kept as small as possible [START_REF] Zink | Subjective Impression of Variations in Layer Encoded Videos[END_REF]. The metric was defined at the beginning of the section. In Fig. 5b, the result for the layer change amplitude is presented. Compared to the D Bw S Sim mechanism, an increase for this metric can be observed using the simple QoE-aware mechanism. Additionally, using Layer Switching allows to reduce the amplitude to a value even below the value of the non-QoE-aware mechanism. Layer Switching, therefore, may further help to improve the perceived quality.

To understand the relevance of the different adaptation mechanisms for the QoE, the average received VQM rating for the delivered content is presented in Fig. 6. The two most important observations are that, using the QoE-aware mechanisms, the objective QoE rating can be improved from a good to an excellent level and that, in contrast to the non-QoE-aware mechanism, peers with more resources are able to retrieve content with a better quality rating. For the non-QoE-aware mechanisms the opposite was the case. This paper investigated how objective assessment of perceived video quality can be used to realize quality adaptation mechanisms for SVC-based video streaming. Therefore, the design of a QoE-aware quality adaptation mechanism using the state-of-the-art objective QoE metric VQM has been presented. Furthermore, the approach was evaluated in the context of a P2P VoD streaming scenario.

The evaluation results show that by applying the proposed mechanisms, a content provider could benefit from lower costs due to a decrease in required streaming server resources by up to 60%, compared to traditional QoS-driven mechanisms. The QoE-aware adaptation mechanism showed superior advantages over the non-QoE-aware mechanisms in terms of lower total stalling event counts by up to 50%, as well as the relative received quality of the single peers by up to 20%. Besides, it could be shown that the proposed mechanism succeeds in maximizing the objectively estimated perceived quality, which is the target metric of the mechanism. By additionally using Layer Switching mechanisms for smooth transitions during layer changes, the average layer change amplitude can be reduced, at the cost of an increased total number of layer changes. For the latter result it is assumed that subjective studies have to be conducted to further evaluate the two parameters' impact on the perceived quality by human users. The results then can be applied to decide on how these parameters have to be weighted to maximize the QoE during the streaming process.

As future work, the consideration of longer videos is planned. Therefore, it has to be investigated how one can account for changes in the video content, as, e.g., implied by different scenes in a movie. As the perception of video quality is highly dependent on the content, it is assumed that different quality ratings are necessary for different parts of a longer video. Additionally, a more detailed analysis of the adaptation strategies' impact on the perceived quality is planned, including the consideration of the QoE for single users. In this context, it is of particular interest how the strategies affect the users with the worst QoE in the system. Finally, it is planned to perform a prototypical evaluation of the presented adaptation mechanisms in a testbed to investigate their applicability in real-world environments.

Fig. 1 :

 1 Fig. 1: Examples for D QoE . Numbers represent the QoE ratings based on VQMLayer Switching. Since the time between two adaptation processes can be configured to span several seconds or even minutes, switching between two layers can be done more smoothly by stretching the process over a longer time.The Layer Switching mechanism defines how to switch to a new layer. In other words, given an old layer A and a new layer B as calculated by the layer decision mechanism, the layer switching algorithms defines the set of layers that have to be passed when switching from A to B. The main reason that motivates a smoother switch is the fact that the perceived video quality can be negatively influenced by too frequent quality switches[START_REF] Zink | Subjective Impression of Variations in Layer Encoded Videos[END_REF]. Therefore, a stepwise adaptation allows to have quality adaptation with smaller steps in between. To avoid having too much layer variation, the mechanism additionally samples the adaptation path in order to put a limit on the amount of steps until the target layer is reached. This process is described at the end of this section.In the following, the concrete realization of layer switching is presented. The mechanism is referred to as Minimized Absolute Variation in QoE Ratings (S QoE ). For the sake of clarity, configurations without switching are referred to as Simple Layer Switching (S Sim ). In this case, switching is done in a simple step by directly jumping to the adaptation's target layer.The switching mechanism S QoE uses the variation in QoE ratings of the traversed layers as its minimization metric. Therefore, the goal is to find a path from the old to the new layer which would go through the layers that have the closest QoE ratings. By doing this, the effective quality of the video is changing smoothly between the two layers. In order to implement the switching strategy, graph theory is applied by generalizing the SVC layer model into a graph. Using classical and extensively researched algorithms from graph theory, determines an efficient approach to the problem of minimizing the absolute QoE variation.

Fig. 2 :

 2 Fig. 2: The steps of interpreting the SVC layer model as graph, retrieving the path with minimal variation from it, and interpretation as adaptation path

Fig. 3 :

 3 Fig. 3: Comparison of session and video quality for changing system capacities

Fig. 4 :

 4 Fig. 4: Comparison of the session quality for different adaptation mechanisms

Fig. 5 :

 5 Fig. 5: Layer change characteristics for different adaptation mechanisms

Fig. 6 :

 6 Fig. 6: Comparison of the VQM quality for different adaptation mechanisms

Acknowledgements. This work has been supported in parts by the IT R&D program of MKE/KEIT of South Korea (10035587, Development of Social TV Service Enabler based on Next Generation IPTV Infrastructure), by the Federal Ministry of Education and Research of the Federal Republic of Germany (support code 01BK0806, G-Lab), and by the German Research Foundation (Research Group 733, QuaP2P: Quality Improvement of Peer-to-Peer Systems).


Yujing Liu
email: liuyujing@nudt.edu.cn

Xiapu Luo

Rocky K C Chang
email: csrchang@comp.polyu.edu.hk

Jinshu Su

Characterizing Inter-domain Rerouting after Japan Earthquake

Keywords: inter-domain routing, betweenness centrality, Japan earthquake, BGP

The Internet is designed to survive when some of its components become faulty. Rerouting is an important approach to bypassing faulty links. In this paper, we propose a method to characterize interdomain rerouting as a result of the massive earthquake in Japan on March 2011. Moreover, the characterization helps correlate inter-domain rerouting events and end-to-end path-quality degradation measured in Hong Kong. We analyse the variation of AS betweenness centrality extracted from BGP data to identify the time span when most routes changed, the ASes that were most seriously affected, and the correlative and backup paths. The results show that three major providers of inbound traffic to Hong Kong were affected by unstable routing state caused by a cable fault after the earthquake. Our work provides a new method of utilizing control plane's information to diagnose data plane's problem.

Introduction

At 5:46 GMT on Mar. 11th, 2011, a massive 8.9-magnitude earthquake hit northeast Japan, causing dozens of deaths, more than 80 fires, and a 10-meter tsunami along parts of the country's coastline. Nuclear power plant and Japan's largest electric utility were taken down. Fiber optic network of undersea cables that connect Japan to the rest of the world was damaged when the earthquake struck beneath the Pacific seafloor [START_REF]Why the Japan Earthquake Didn't Take Down the Country's Internet[END_REF]. As a result, the Internet relying on this underlying infrastructure to deliver data traffic was affected by this disaster. Many telecom operators reported service disruptions and performance degradations in the communications with either Japan or other places around the world.

Our end-to-end Internet path measurement system OneProbe1 [START_REF] Luo | Design and Implementation of TCP Data Probes for Reliable and Metric-Rich Network Path Monitoring[END_REF] witnessed that 10 out of 19 monitored paths from Europe, US, Australia and Japan to HARNET (The Hong Kong Academic and Research NETwork) in Hong Kong suffered from high packet losses and increased RTTs during Mar. 11th and 12th. To diagnose the cause of this performance degradation, we seek for answers to these questions: Did any of the damaged cables affect those paths? Did the Internet reroute to bypass the fault segment? And how did the rerouting perform?

In this paper, we propose a new approach to characterize inter-domain rerouting in the AS level after network events. The Internet is highly distributed and autonomous in nature. Its routing state is profiled by the behaviour of every component in it. According to the evidence that rerouting entails changes of traffic load distribution, we measure the load variance of every AS in terms of AS betweenness centrality to depict properties of rerouting in the Internet. Since Border Gateway Protocol (BGP) is the de-facto standard inter-domain routing protocol, and its AS path attribute records AS-level routes of the Internet, we calculate AS betweenness centrality from publicly available BGP RIBs and updates collected by RIPE [START_REF]RIPE RIS[END_REF] and Route Views [4] in a particular period of time. By exploiting different perspectives of this metric, we can identify several important characteristics of inter-domain rerouting such as the time span when most routes changed, the ASes which were affected worst, and the correlative and backup paths. We apply our methodology to infer the cause of performance degradation on the monitored paths to Hong Kong after Japan earthquake. The results show that the worst impacted ASes along the paths are affected by a cable fault several hours after earthquake, and rerouting occurs frequently among origin and backup paths. Hence, we attribute the path-quality degradation to this unstable routing state. Moreover, we investigate how the Internet performed in a global view after the quake. The study of this event serves as a practical case of leveraging control plane's information to diagnose data plane's problem.

The paper is organized as follows. We introduce our methodology in Sec. 2. Then we apply it to characterize inter-domain rerouting after Japan earthquake in Sec. 3. After discussing the related works in Sec. 4, we conclude the paper and present future works in Sec. 5.

Methodology

Many researches study inter-domain routing behaviour by analysing BGP dynamics for different purposes, such as improving the Internet functioning, troubleshooting BGP, detecting anomalies and monitoring impact of disruptive events on the Internet [START_REF] Li | BGP routing dynamics revisited[END_REF][START_REF] Xu | Inferring Major Events from BGP Update Streams[END_REF][START_REF] Zhang | Learning-Based Anomaly Detection in BGP Updates[END_REF][START_REF] Li | I-seismograph: Observing and measuring Internet earthquakes[END_REF]. Numerous yet computationally intensive metrics have been developed to achieve the goals. Most of them are prefix oriented (origins of routing information) whereas some explore the point of observation (receivers of routing information). In this paper, with the novel attempt to diagnose data plane's problem, we focus on the changes in load carried by every AS in-between to investigate how different routing systems react after network events. To assess the load of an AS, we propose utilizing betweenness centrality as a metric that was introduced in social networks first [START_REF] Freeman | A Set of Measures of Centrality Based on Betweenness[END_REF][START_REF] Holme | Vertex overload breakdown in evolving networks[END_REF]. In this section, we will explain how to identify temporal, topological and relational characteristics of inter-domain rerouting from different perspectives of this single metric.

Variance of AS betweenness centrality

In networks, the more shortest paths a vertex or edge participates in, the more important this vertex or edge is. Betweenness centrality is a metric to quantify the importance of a vertex or edge in a network [START_REF] Da | Characterization of Complex Networks: A Survey of measurements[END_REF]. In this paper, we employ it to measure how many AS paths pass through a certain AS. Since the more AS paths an AS participates in, the more traffic the AS will transmit. Therefore, we consider it as a proper metric to evaluate the load on such AS. We model the Internet as a graph G = (V, E) where V is the set of all ASes, and E is the set of AS links. Let v be an AS in V , then the betweenness centrality BC(v) is defined as

BC(v) = u,w∈V σ uw (v) σ uw (1)
, where the summation is over all pairs of ASes such that u = w = v. σ uw (v) denotes the total number of AS paths between u and w that pass through v and σ uw denotes the total number of AS paths between u and w. It's worth noting that in inter-domain routing system, AS paths are not necessarily the shortest paths among ASes. As a policy-based routing protocol, BGP allows each AS to choose its own routing polices in selecting the best route, announcing and accepting routes. The AS path from source to destination must be policycompliant, thereby follows certain patterns such as valley-free and customerprefer [START_REF] Gao | On inferring autonomous system relationships in the internet[END_REF].

Inter-domain rerouting will result in changes of some ASes' betweenness centrality. As shown in Eqn. (2), we define variance of AS betweenness centrality BC t (v) to quantify the difference of it measured at time t -1 and t. Positive value indicates extra AS paths are rerouted through this AS, while negative value indicates some paths are routed away from the AS. And the magnitude represents amount of paths.

BC t (v) = BC t (v) -BC t-1 (v) ( 2 )
If we measure the variance of betweenness centrality of every AS in V for a period of time T , we can obtain a variance matrix BC where every row represents a sequence of betweenness centrality changes associated with each AS, i.e., the element (i, j) in BC is equal to BC j (i) where i ∈ V and j ∈ T .

In this paper, we calculate BC by analysing BGP data collected by RIPE and Route Views. These two projects employ multiple Remote Route Collectors (RRCs) to establish BGP peering sessions with many ASes around the world, collect their routing information to all the other destination ASes, and periodically dump their BGP routing tables (every 8 hours in RIPE and every 2 hours in Route Views) and updates (every 5 minutes in RIPE and every 15 minutes in Route Views). Therefore, we can get routes from those peering ASes to any other ASes in the Internet, and compute variance of AS betweenness centrality by calculating changes in AS path of these routes. The available data from multiple vantage points reveals a broad and global though necessarily incomplete view of inter-domain routing over time [START_REF] Dainotti | Analysis of Country-wide Internet Outages Caused by Censorship[END_REF]. We use this data to sample the Internet's behaviour.

Identify characteristics of rerouting

Aggregated time of route changes

The variance matrix has two dimensions which are temporal and topological. In temporal dimension, every column of BC is a vector that contains every AS's betweenness centrality change at a certain time slot t, denoted as BC t =< BC t (v 1 ), BC t (v 2 ), ..., BC t (v n ) >, where v i ∈ V . Higher magnitude of variation indicates more route changes. To characterize aggregated time of rerouting, we calculate the mean value of all ASes' absolute variation at time t, denoted as μ t . Comparing all μ t during an observed time window will show the time span having most route changes, which reveals the temporal characteristic of inter-domain rerouting.

Worst affected components

The topological dimension of variance matrix includes all ASes in the Internet. Every row of BC is a vector that consists of betweenness centrality changes over time associated with a certain AS, denoted as BC(v) =< BC t1 (v), BC t2 (v), ..., BC tm (v) >, where t i ∈ T . Higher diversity of this sequence of data indicates the AS experiences more unstable routing changes. Therefore, we use standard deviation of the vector, denoted as δ v , to measure the stability of AS v. Ranking all ASes with their δ v can offer a list of members affected by the events in terms of descend instability.

A summation over a continuous time of elements in BC(v) calculates changes of v's betweenness centrality during that period of time. Formally speaking, BC (tp,tp+q) (v) represents changes of v's betweenness centrality between time t p and t p+q . It can be computed as

BC tp+q (v)-BC tp (v) = BC tp+q (v)-BC tp+q-1 (v)+ BC tp+q-1 (v)-BC tp+q-2 (v)+...+BC tp+1 (v)-BC tp (v) = p+q i=p+1 BC ti (v)
. Large changes of betweenness centrality before and after a continuous time of instability indicate a quite different load distribution over the ASes, in other words, the routing system converges to a different state. Otherwise, the routing system just experiences unstable changing phase then back to the origin state. These two aspects are considered to be the topological features of rerouting.

Correlative and backup paths Elements in networks are not independent. The effect of an event originated from one point will spread out over the network. Investigating the relationship between routing behaviours from both temporal and topological aspects enables us to examine the synchronization of ASes' betweenness centrality changes, further more, to identify correlative parts and backup paths of original routes. Synchronization of routing changes indicates common causes beneath them. It is of great significance for the following diagnose to identify and separate these ASes.

We develop a divisive hierarchical clustering algorithm [START_REF] Han | Data Mining: Concepts and Techniques[END_REF] to analyse this synchronization. The basic idea is to evaluate the similarity between patterns of any two ASes' changes. As shown in Fig. 1, the original data consists of all the vectors BC(v). First, we split it into two clusters using K-Means algorithm with absolute city block distance, which is the sum of differences for all elements' absolute value in vectors (i.e.,

m i=1 || BC ti (v)| -| BC ti (v )||).
In each cluster, the betweenness centrality of every AS changes in similar magnitude at similar time. We assume that in an inter-domain routing event, only a few ASes act synchronously. So the smaller cluster contains the tightly related ASes. To validate this assumption, we examine the topology of these ASes, looking for clues to their relations. In order to further differentiate between correlation and backup, we partition these related ASes into two clusters again with just city block distance (i.e., m i=1 | BC ti (v) -BC ti (v )|). The intra-relation is correlative because the betweenness centrality of ASes within a cluster increases/decreases in similar quantity at same time, whereas inter-relation is backup because betweenness centrality increases in one cluster while decreases in the other at same time. However, before differentiating them, we need to check whether or not there exist backup paths by calculating the intra-distance of correlative clusters and compare it with the intra-distance of their parent synchronous cluster [START_REF] Li | I-seismograph: Observing and measuring Internet earthquakes[END_REF]. If the difference is marginal and less than a threshold θ, it indicates that there is no apparent backup relation in the synchronous ASes, therefore, we consider them all as correlative. The first isolated ASes and their routing behaviours are the dominant changes of the Internet's routing structure. We can keep clustering the remaining data to find different levels of changes as needed.

Rerouting after Japan Earthquake

After Japan's earthquake on Mar. 11th, news reported that some of trans-Pacific cable systems were damaged. Our network measurement system OneProbe observed regional path-quality degradation of the Internet during Mar. 11th and 12th. In this section, we apply our method to this event for better understanding the relationships among cable fault, inter-domain rerouting and end-to-end performance degradation.

We collected the data set from BGP routing tables and updates of RIPE and Route Views during Mar. 9th to 12th, then converted them into a sequence of 10minute time slots so that the routing changes can be distinguished in fineness of 10 minutes. By extracting AS paths from RIBs in conjunction with updates, we can calculate every AS's betweenness centrality in each time slot and construct a variance matrix.

We first limit the scope of our analysis to the routes from RRCs to HAR-NET's IP prefixes monitored by OneProbe. Results associated with these specific destinations can help us infer the causes of reported performance degradation. After that, we further analyse the routes for the entire routed IP prefix space in order to understand the global routing state.

Rerouting associated with HARNET

The variance matrix for routes associated with HARNET consists of 83 rows and 576 columns, which represent variances of betweenness centrality of 83 ASes in a period of 4 days. These ASes appear at least once in the AS paths of given routes. Further findings listed below show details of reroutings from different perspectives.

Fig. 2 shows the mean values of vector | BC t | wrt. time t, i.e., μ t . We use the first 2 days as a reference period, and calculate its average μ t as a threshold to define normal range of routing changes. Therefore we can find the dominant period that contains the most 'abnormal' time slots after earthquake, which represents a continuous instability of routing state. The dominant period is from 9:00 to 16:00 on Mar. 11th, 3 hours later than the first wave of earthquake. This result is validated by Renesys [START_REF]Japan Quake[END_REF]. They used the number of prefix outages as a metric, and inferred that network in Hong Kong was affected by follow-on events several hours later. Fig. 3 shows ranked ASes with their standard deviations of vector BC(v), i.e., δ v . Higher values indicate more unstable routing states of ASes. To identify the worst affected components, we employ K-Means clustering algorithm to distinguish them from less affected ASes based on their δ v . The first separated cluster contains 3 ASes which are AS10026 (PacNet), AS15412 (FLAG) and AS6939 (HURRICANE). All of them are major service providers of HARNET, transmitting data traffic for it. This result implies that traffic passing through these 3 ASes shifts most frequently. According to TeleGeography's report [START_REF]Why the Japan Earthquake Didn't Take Down the Country's Internet[END_REF], the Hong Kong-based cable-network operator PacNet reported damage to two segments of its East Asia Crossing submarine cable, which connects Japan to other parts of Asia. We believe this is the reason why AS10026's betweenness centrality varies noticeably after earthquake. Further analysis about relationships between ASes reveals causes of changes on AS15412 and AS6939.

To investigate whether the cable fault-caused instability results in noticeable changes of load distribution, we examine BC (t b ,te) (v) of the 3 most unstable ASes, where t b and t e are the beginning and end time of the dominant period of rerouting. Then we compare them with the ASes' average betweenness centralities in the first 2 days. Their changing ratios are 0.32%, 0.68% and 0.75% separately, which indicates that although routes towards Hong Kong experience unstable states, few of them have changed after the instability. We use the divisive hierarchical clustering algorithm described in Sec. 2 to exploit synchronous routing behaviours of ASes. Results show that level 1 cluster consists of the 3 worst affected ASes. AS10026 and AS6939 are correlative while AS15412 is a backup path of them. Given the inference that AS10026 is affected by the cable fault, we estimate that AS6939 is affected by the secondary effect of this cable damage via AS10026. In addition, AS15412 is a backup route for shifting traffic from AS10026 and AS6939. Level 2 consists of 4 ASes, in which AS22388 and AS7660 are backups of AS11537 and AS24167. Level 3 contains AS2914, AS4788 and AS6762, all of which are correlative. The hourly distributions of their variations in betweenness centrality are shown in Fig. 4. The variances decrease with increased levels. We stop at level 3 since changes are negligible after that. Fig. 5 shows the topology of AS paths from all RRCs to HARNET. Every end point is an AS in which a RRC is deployed. The size of each AS is proportional to the log-value of its average betweenness centrality over the reference period (the first 2 days), which is considered as a metric of its importance in transmitting traffic for HARNET. It also serves as evidence to infer HARNET's major providers. This figure validates our results in a topological view. For example, in level 1 cluster, AS10026 and AS6939 are neighbours while AS15412 and AS10026 are multi-hosts of HARNET's major provider AS9381.

When one of the upstream network is damaged, switching to another provider is a quick solution. and 7071 happen in 11th. Some routes don't just flap only once. The maximum time is 73, and 103 of them are more than 20 times. However, 96.9% of these routes are stick to the original one after flapping.

According to our results, we infer that the performance degradation on the paths from other places to HARNET in Hong Kong is mainly due to PacNet's cable fault 3 hours later after Japan earthquake. Paths passing through Pac-Net and HURRICANE change to FLAG as backup. The earthquake entails an unstable state of inter-domain routing system. A large number of inter-domain routes oscillate during that period of time.

Rerouting in the global Internet

In order to better understand inter-domain routing state of the entire Internet, we extend the destinations from HARNET's prefixes to all routed IP prefixes in BGP. The variance matrix for routes from RRCs to all prefixes consists of 5068 rows and 576 columns. These 5068 ASes are transit ASes which transmit traffic for other ones. The other more than 30,000 ASes are stub ASes which are not our targets for this study.

Fig. 6 shows values of μ t in 4 days. We can see that there are lots of spikes over time, probably due to BGP dynamics caused by numerous events in the Internet. But since earthquake and cable faults could result in persistent instability of routing system, we focus on the longest unusual changing time. We use the same method in previous section to identify the dominant period which lasts from 8:50 to 15:20 on 11th. Fig. 7 shows ranked ASes with their δ v in a log-log scale, which indicates an inhomogeneous distribution of them. By separating them into 2 clusters, we get 17 worst affected ASes. They are AS10026, AS6939, AS174, AS3257, AS2914, AS6453, AS3549, AS3491, AS3356, AS7473, AS6762, AS3216, AS15412, AS6461, AS209, AS721 and AS27064, ordered by descend δ v . Remarkably, Pac-Net (AS10026) is still top 1 in the entire Internet. It is evident that PacNet's regional cable faults have a vast impact on inter-domain rerouting of the Internet. Moreover, the changing ratio of AS10026's betweenness centrality during the dominant period of rerouting is -21.91%. Unlike routes to Hong Kong, a large amount of routes which passing through PacNet and destined for other places shift away after unstable rerouting period. The synchronization of routing behaviours in the Internet is not as clear as that with HARNET. Fig. 8 is a demonstration of level 1 synchronization. Further analysis shows that the synchronization of routing behaviours is associated with destinations. It is more effective to study routings with topological-neighbour destinations. [START_REF] Li | I-seismograph: Observing and measuring Internet earthquakes[END_REF]. They employed BGP dynamics in different ways to achieve their different goals. However, it is a challenging work because BGP dynamics are inherent complex and full of outliers. In this paper, our intent is to diagnose network's problem by examining changes of inter-domain routes. Hence we focus on changes of AS paths recorded in BGP routing tables and updates, which directly reflect inter-domain routing behaviours in AS level.

Fukuda et al., Cho et al. and Renesys reported their studies about limited impacts of Japan earthquake on the structure and routing dynamics of the regional Internet [START_REF] Fukuda | Impact of Tohoku Earthquake on R&E Network in Japan[END_REF][START_REF] Cho | The Japan Earthquake: the impact on traffic and routing observed by a local ISP[END_REF][START_REF]Japan Quake[END_REF]. Especially, by examining BGP messages collected from local ISPs in Japan, Cho et al. claimed that almost nothing to see in BGP. Bischof et al. leveraged data collected by BitTorrent to identify specific regions and network links where Internet usage and connectivity were most affected after the earthquake [START_REF] Bischof | Distributed Systems and Natural Disasters[END_REF]. Unlike the local routing information or specific application data that they use, we rely on publicly available control-plane data and focus on inter-domain routing of the Internet in a global scope. This method enables us to study the side effect of this earthquake on communications in Hong Kong and other places in the world.

Conclusion and future work

In this paper, we employ a social network-inspired metric, the variance of AS betweenness centrality, to analyse inter-domain routing behaviours after Japan earthquake. We infer that paths to Hong Kong are affected by unstable routing state caused by a cable fault after the earthquake. Besides, according to our extended analysis, the operator of this cable is also the worst impacted AS in the entire Internet, affecting paths to other destinations. We propose a method of using control-plane information to diagnose data-plane problems with publicly available BGP data. It is a useful and practical approach for understanding then improving the Internet functioning.

As an ongoing work, we will examine the routing states associated with other particular regions so as to achieve full spectrum vision of this event. By further exploring router-level routes presented in this work, we are able to correlate the paths with their geographical locations, then map them to submarine cables to better understand the relationship between logical routes and physical links. We will also apply our method to analysing other network events such as DDoS attacks, prefix hijackings, large-scale power outages and so forth.

Fig. 1 .

 1 Fig. 1. Clustering algorithm for analysing synchronization of route changes

Fig. 2 .

 2 Fig. 2. Aggregated time of route changes with HARNET

Fig. 3 .

 3 Fig. 3. Worst affected ASes with HARNET

Fig. 4 .Fig. 5 .

 45 Fig. 4. Top 3 levels of synchronization with HARNET

Fig. 6 .

 6 Fig. 6. Aggregated time of route changes in the Internet

Fig. 7 .

 7 Fig. 7. Worst affected ASes in the Internet

Fig. 8 .

 8 Fig. 8. Level 1 synchronization in the Internet

Science

  Foundation of China, under Grant No. 61003303, 61070199, 60903185; Program for Changjiang Scholars and Innovative Research Team in University (No. IRT1012); Program for Science and Technology Innovative Research Team in Higher Educational Institutions of Hunan Province (Network Technology, NUDT); and Hunan Province Natural Science Foundation of China (11JJ7003).

www.oneprobe.org

Acknowledgement

This work is partially supported by a grant (ref. no. ITS/355/09) from the Innovation Technology Fund in Hong Kong; a grant (ref. no. H-ZL17) from the Joint Universities Computer Centre of Hong Kong; the National Natural