Wei Chen

Zafar Shahid

Thomas Stütz

Florent Autrusseau
email: florent.autrusseau@univ-nantes.fr

Patrick Le Callet

Robust drift-free bitrate preserving H.264 watermarking

This paper presents a novel method for open-loop watermarking of H.264/AVC bitstreams. Existing watermarking algorithms designed for previous encoders, such as MPEG-2 cannot be directly applied to H.264/AVC, as H.264/AVC implements numerous new features that were not considered in

previous coders. In contrast to previous watermarking techniques for H.264/AVC bitstreams, which embed the information after the reconstruction loop and perform drift-compensation, we propose a new completely intra-drift-free watermarking algorithm. The major design goals of this novel H.264/AVC watermarking algorithm are: runtime-e ciency, high perceptual quality, (almost) no bit-rate increase and robustness to re-compression. The watermark is extremely runtime-e ciently embedded in the compressed domain after the reconstruction loop, i.e., all prediction results are reused. Nevertheless intra-

drift is avoided, as the watermark is embedded in such a way that the pixels used for the prediction are kept unchanged. Thus there is no drift as the pixels being used in the intra prediction process of H.264/AVC are not modified. For watermark detection, we use a two stages cross-correlation. Our simulation results confirm that the proposed technique is robust against re-encoding and shows a negligible impact on both the bit-rate and the visual quality.

Keywords Video watermarking • H.264 • perceptual weighting • bit-rate preservation 1 Introduction H.264/AVC is a state-of-the-art video compression standard and has become the most widely deployed video codec in almost all applications: video distribution in the Internet as well as on Blu-ray discs, even mobile devices employ H.264/AVC to compress captured video data. The ubiquity of digital content and its ease of duplication and modification calls for technical solutions for copyright protection and authentication; digital watermarking is an integral part of such solutions. As digital video content is mostly coded with H.264/AVC, watermarking solutions that are tailored to the specifics of this standard can greatly improve the performance of digital watermarking systems, e.g., with respect to runtime performance.

In H.264/AVC, the watermark could be embedded at the various stages in the compression pipeline, i.e., pre-compression or spatial domain, transform coding stage, QTCs (quantized transform coe cients) stage and entropy coding stage. So, basically, the work on video watermarking can be divided into two main approaches: 1) closed-loop watermarking, i.e., watermark em-bedding requires to consider the coder reconstruction loop (any modification due to watermark embedding might likely a↵ect further encoding of information). 2) open-loop watermarking, i.e., the watermark embedding modifies only a well defined set of information without a↵ecting the encoding process of any other information. The closed-loop watermarking almost needs complete re-compression while open-loop watermarking embeds a watermark in compressed domain (syntax elements before entropy encoding) or bitstream domain (bit substitutions of the final bitstream). Thus open-loop watermarking either requires only the entropy encoding stage or no stages from the compression. Therefore open-loop watermarking is extremely runtime-e cient compared to closed-loop watermarking. In Section 2.1, we present the recent research on closed-loop watermarking, while open-loop watermarking approaches are discussed in Section 2.2. Embedding within the reconstruction loop avoids drift, shows a small impact on rate distortion (RD) performance and o↵ers a high watermark payload. It also has the significant disadvantage that it requires re-computation of all prediction decisions for the embedding of each single watermarking message [START_REF] Shahid | Considering the Reconstruction Loop for Data Hiding of Intra and Inter Frames of H.264/AVC[END_REF]. Thus it requires the computationally most complex parts of video compression and therefore cannot be used for applications with runtime constraints or in applications which require numerous watermark messages to be embedded. Active fingerprinting is an example which usually requires numerous watermarks, as each buyer's fingerprinting code is embedded in the visual content to detect the traitor in case of illegal distribution of the content.

On the other hand, if the watermark embedding occurs after the reconstruction loop (open-loop), the most complex parts of the compression pipeline are omitted. Watermark embedding modifies only prediction residuals on the syntax level. In open-loop watermarking, prediction is performed from watermarked content on the decoder side and from the original content on the encoder side. Thus there is a mismatch between encoder and decoder side predictors, which accumulates over time. This accumulating mismatch is referred as drift and makes open-loop watermarking very challenging, as visual quality constraints are hard to meet. As video data are usually stored and distributed in a compressed format (very often H.264), it is often impractical to first decode the video sequence, embed the watermark and then re-compress it. A low-complexity video watermarking solution requires that the embedding be conducted in an open-loop fashion. Furthermore common design goals of watermarking algorithms should also be met, such as robustness and imperceptibility. In this paper, we present an algorithm for open-loop watermark embedding in H.264/AVC bitstreams, which is robust against re-compression.

At the same time, the embedding is imperceptible and avoids intra-drift, by keeping the predictor pixels unchanged.

In previous work we presented the basic idea for intra-drift-free H.264/AVC bitstream watermarking in [START_REF] Chen | A Error-Propagation-Free Perceptual Watermarking Algorithm for H.264/AVC Encoded Video[END_REF], but could only report very preliminary results, which employed ad-hoc solutions of the system of linear equations and used a constant embedding strength without any human visual system model. In this paper, we present a significantly improved version of our basic idea; we now select the most suitable patterns from the complete set of solutions, and use the DCTune perceptual model [START_REF] Watson | DCT Quantization Matrices Visually Optimized for Individual Images[END_REF] to modulate the watermark embedding strength. The use of DCTune improves the basic approach in two ways: First, visible artifacts are avoided in the watermarked video. Second, as the watermark embedding strength is increased to the DCTune imperceptibility Fig. 1: Two main categories of watermarking in video codec: 1) During the encoding process or spatial domain, 2) In the bitstream domain. limit, the improved technique o↵ers higher robustness. Furthermore, a comprehensive analysis and a comprehensive evaluation of our proposed technique is performed in this paper.

The remainder of the paper is organized as follows: Recent work on H.264/AVC watermarking is presented in Section 2. The proposed technique including the derivation of the linear system, watermarking embedding and detection are presented in Section 3. Experimental results are presented in Section 4. In Section 5 we discuss the performance and possible improvements of the presented algorithm. Final conclusion are drawn in Section 6.

Recent work

For video content, watermarking is often strongly tied to the compression. As previously explained, two distinct approaches can be used for video watermarking, closed-loop watermarking, where the information is embedded either before or during compression, or open-loop watermarking, where the watermark is embedded during the entropy coding or directly within the bitstream. the literature, these stages are numbered within the circles. In the following subsections we will describe state-of-the-art methods for these two approaches.

Closed-loop watermarking

Embedding before or during compression can be subdivided into three main classes namely, embedding before compression, embedding in transform coefficients, and embedding in QTCs (quantized transform coe cients):

In the pre-compression stage, denoted stage 1 in Figure 2, watermarking can be performed in the pixel domain [START_REF] Cox | Secure Spread Spectrum Watermarking for Multimedia[END_REF][START_REF] Chen | Temporal Statistic Based Video Watermarking Scheme Robust against Geometric Attacks and Frame Dropping[END_REF] or more commonly in a transform domain like DFT [START_REF] Kang | A DWT-DFT Composite Watermarking Scheme Robust to Both A ne Transform and JPEG Compression[END_REF][START_REF] Deguillaume | Robust 3D DFT Video Watermarking[END_REF] or DWT [START_REF] Wu | Object-Based Multiresolution Watermarking of Images and Video[END_REF]. Pre-compression watermarking approaches can also be performed on multiple frames [START_REF] Chen | Temporal Statistic Based Video Watermarking Scheme Robust against Geometric Attacks and Frame Dropping[END_REF][START_REF] Deguillaume | Robust 3D DFT Video Watermarking[END_REF]. In [START_REF] Pröfrock | A New Uncompressed-Domain Video Watermarking Approach Robust to H.264/AVC Compression[END_REF], Pröfrock et al. have presented a watermarking technique in the spatial domain, robust to H.264/AVC compression attacks with more than 40:1 compression ratio. The watermark is only contained in intra frames similar to the approach presented in [START_REF] Wu | Robust Watermark Embedding/Detection Algorithm for H.264 video[END_REF]. The watermark can also be embedded in the transformed coe cients before quantization as proposed by Golikeri et al. [START_REF] Golikeri | Robust Digital Video Watermarking Scheme for H.264 Advanced Video Coding Standard[END_REF] (see stage 2 in Figure 2).

Visual models developed by Watson [START_REF] Watson | DCT Quantization Matrices Visually Optimized for Individual Images[END_REF] were employed. Some algorithms [START_REF] Gong | Towards Fast and Robust Watermarking Scheme for H.264 Video[END_REF][START_REF] Noorkami | Digital Video Watermarking in P-Frames With Controlled Video Bit-Rate Increase[END_REF][START_REF] Wu | Robust Watermark Embedding/Detection Algorithm for H.264 video[END_REF][START_REF] Shahid | Considering the Reconstruction Loop for Data Hiding of Intra and Inter Frames of H.264/AVC[END_REF] embed the watermark in QTCs of H.264/AVC (see stage 3 in Figure 2). Noorkami and Merserau have presented a technique to embed a watermark message in both intra and inter frames in all non-zero QTCs [START_REF] Noorkami | Digital Video Watermarking in P-Frames With Controlled Video Bit-Rate Increase[END_REF]. They claimed that visual quality of inter frames is not compromised even if the message is embedded only in non-zero QTCs. In [START_REF] Gong | Towards Fast and Robust Watermarking Scheme for H.264 Video[END_REF], Gong and Lu embedded watermarks in H.264/AVC video by modifying the quantized DC coe cients in luma residual blocks. To increase the robustness while maintaining the perceptual quality of the video, a texture-masking-based perceptual model was used to adaptively choose the watermark strength for each block. To eliminate the e↵ects of drift, a drift compensation algorithm was proposed which adds a drift compensation signal before embedding the watermark.

In [START_REF] Shahid | Considering the Reconstruction Loop for Data Hiding of Intra and Inter Frames of H.264/AVC[END_REF], Shahid et al. embedded watermarks in H.264/AVC video by modifying the quantized AC coe cients in luma and chroma residual blocks. This method embeds a watermark message inside the reconstruction loop to avoid drift, and hence needs re-compression for each watermark message. This algorithm has a negligible compromise on RD performance and is useful for high payload metadata hiding. While only modifying the AC QTCs above a certain threshold, the scheme o↵ers 195 kbps payload with 4.6% increase in bit-rate and 1.38 dB decrease in PSNR at QP value of 18.

Open-loop watermarking

To avoid decoding followed by the extremely computationally demanding recompression combined with watermarking, some methods have suggested embedding watermark messages in an open-loop fashion, e.g., [START_REF] Kapotas | Data Hiding in H.264 Encoded Video Sequences[END_REF][START_REF] Kim | Data Hiding on H.264/AVC Compressed Video[END_REF][START_REF] Mobasseri | Authentication of H.264 Streams by Direct Watermarking of CAVLC Blocks[END_REF][START_REF] Noorkami | Compressed-Domain Video Watermarking for H.264[END_REF][START_REF] Zou | 264/AVC Substitution Watermarking: A CAVLC Example[END_REF] to achieve low-complexity video watermarking (see stage 4 in Figure 2). In [START_REF] Alattar | Digital Watermarking of Low Bit-Rate Advanced Simple Profile MPEG-4 Compressed Video[END_REF], perceptual models are adopted to mitigate the visual artifacts. In [START_REF] Langelaar | Optimal Di↵erential Energy Watermarking of DCT Encoded Images and Video[END_REF], a compressed domain watermarking technique called di↵erential energy watermark (DEW) is proposed. In [START_REF] Ling | New Real-Time Watermarking Algorithm for Compressed Video in VLC Domain[END_REF], the authors proposed a watermarking algorithm named di↵erent number watermarking (DNW) algorithm, embedding the mark in the texture and edges. For all of the above techniques, the main problems are visible artifacts and bit-rate increase.

In previous work the addition of a drift compensation signal to control / eliminate the drift, i.e., visible artifacts, has been proposed [START_REF] Huo | A Controllable Error-Drift Elimination Scheme for Watermarking Algorithm in H.264/AVC Stream[END_REF][START_REF] Hartung | Watermarking of Uncompressed and Compressed Video[END_REF]. In [START_REF] Huo | A Controllable Error-Drift Elimination Scheme for Watermarking Algorithm in H.264/AVC Stream[END_REF], Huo et al. have proposed to process only a subset of the transformed coe cients as opposed to process all the coe cients as suggested in the other compensation methods. Kapotas et al. [START_REF] Kapotas | Data Hiding in H.264 Encoded Video Sequences[END_REF] have presented a data hiding method in H.264/AVC streams for fragile watermarking. It takes advantage of the di↵erent block sizes used by the H.264 encoder during the inter prediction stage in order to hide the desirable data. The message can be extracted directly from the encoded stream without the need of the original host video. This approach can be mainly used for content-based authentication. In [START_REF] Noorkami | A Framework for Robust Watermarking of H.264-Encoded Video With Controllable Detection Performance[END_REF], the authors propose a self-collusion resistant watermarking embedding algorithm using a key dependent embedding strategy. Their algorithm is reported to cause only one percent increment of the bit-rate; however, it is not robust to recompression.

In [START_REF] Noorkami | Compressed-Domain Video Watermarking for H.264[END_REF], the same authors present a new algorithm that is more robust, but the increment of bit-rate is up to 4-5%. In [START_REF] Qiu | A Hybrid Watermarking Scheme for H.264/AVC Video[END_REF], Qiu et al. propose a hybrid watermarking scheme that embeds a robust watermark in the DCT domain and a fragile watermark in the motion vectors in the compressed domain. This approach is not robust against common watermarking attacks.

Watermark embedding may be conducted directly on the bitstream as well, i.e., by substitution of certain bits. In [START_REF] Mobasseri | Authentication of H.264 Streams by Direct Watermarking of CAVLC Blocks[END_REF], authentication of H.264/AVC is performed by direct watermarking of CAVLC codes. In [START_REF] Kim | Data Hiding on H.264/AVC Compressed Video[END_REF], Kim et al. present a new algorithm embedding the watermark in the sign bit of the trailing ones in CAVLC of H.264/AVC with no change in bit-rate with PSNR higher than 43 dB. But, this technique is not robust against attacks such as re-compression with di↵erent encoding parameters and common signal processing attacks. Zou and Bloom [START_REF] Zou | 264/AVC Substitution Watermarking: A CAVLC Example[END_REF] have proposed to perform direct replacement of CAVLC for watermarking purpose. For CABAC [START_REF] Zou | 264 Stream Replacement Watermarking with CABAC Encoding[END_REF], they have proposed a robust watermarking method using Spread Spectrum modulation while still preserving the bit-rate. This technique is robust against slight shift, moderate downscaling and re-compression. To keep the watermark artifacts invisible and to ensure the robustness, fidelity and robustness filters were used. In [START_REF] Ma | A Data Hiding Algorithm for H.264/AVC Video Streams Without Intra-Frame Distortion Drift[END_REF], the authors present an algorithm for watermarking intra frames without any drift. They propose to exploit several paired-coe cients of a 4 ⇥ 4 DCT block to accumulate the embedding induced distortion. The directions of intra-frame prediction are used to avert the distortion drift. The proposed algorithm has high embedding capacity and low visual distortions. Since this technique is based on intra prediction direction, it is not robust against re-encoding attack, which is the most common non-intentional attack.

Open-loop video watermarking algorithms face major challenges / limitations: First, the payload of such algorithms is significantly reduced, i.e., up to a few bytes per second as explained in [START_REF] Hartung | Watermarking of Uncompressed and Compressed Video[END_REF]. Second, if drift compensation is not applied there is a continuous drift, which significantly distorts the visual quality. Third, if drift compensation is applied, the algorithms face considerable bit-rate increases. Fourth, the robustness is often very limited.

In [START_REF] Hartung | Watermarking of Uncompressed and Compressed Video[END_REF] and [START_REF] Qiao | Non-invertible watermarking methods for MPEG encoded audio[END_REF], the authors emphasize the importance of bit-rate preserving watermarking algorithms.

The goal of this paper is to present a robust open-loop watermarking algorithm for H.264/AVC with a minimal increment of the bit-rate and robustness against recompression. To achieve these goals, drift is avoided instead of compensated which allows to almost preserve the original bit-rate as no compensation signals need to be coded.

Drift-free open-loop H.264 watermarking

The main challenge in the design of an H.264/AVC open-loop watermarking algorithm is drift, which is a result of intra and inter prediction [START_REF] Noorkami | A Framework for Robust Watermarking of H.264-Encoded Video With Controllable Detection Performance[END_REF][START_REF] Noorkami | Compressed-Domain Video Watermarking for H.264[END_REF]. If the watermark embedding algorithm modifies the pixels which are used in these processes, the result is a drift error which accumulates, i.e., multiple drift errors add up to induce clearly visible distortions. In the proposed watermarking technique, a watermark message is embedded in the transformed domain, while making sure that only those pixels are modified which are not used for the intra prediction of future blocks. Capital letters refer to matrices, e.g., C, Y , W and lower case letters with indices refer to the elements of a matrix, e.g.,

x ij represents j th element in i th row of matrix X.

The embedding of the watermark modifies the original pixel value x ij by adding the watermark signal w ij , which results in the watermarked signal x w ij .

x

w ij = x ij + w ij (1)
The values y ij are the pixels in the next block, which is predicted from x ij . A pixel value y ij can be decomposed into its predictor p ij and residual r ij :

y ij = p ij + r ij (2)
At the encoder side, p ij is derived from x ij , but after the watermark embedding, x ij changes into x w ij , so p ij changes to p w ij , y ij will thus become y

0 ij ; y 0 ij = p w ij + r ij (3)
Thus the drift error e is:

e = y 0 ij y ij (4)
In this work, we completely avoid this drift error, as the reference pixel values for the intra prediction remain unchanged.

p w ij = p ij , y 0 ij = y ij , ) e = 0. (5)
In Section 3.1, we present the solutions of a system of linear equations, which allow to embed a watermark message in the DCT coe cients without modifying boundary pixels which are used for prediction of future blocks.

The watermark embedding step is explained in Section 3.2, while watermark detection is presented in Section 3.3.

3.1 Intra-drift-free DCT-watermarking: solutions of a system of linear equations

In the spatial prediction of H.264, the pixels of a macroblock (MB) are predicted by using only information of already transmitted blocks in the same It is more suited for coding the smooth areas of the frame and has four prediction modes. In this paper, we are presenting the algorithm for a watermark embedding in the 4 ⇥ 4 luma blocks of intra frames. Figure 4 shows the nine di↵erent predictions modes for a 4 ⇥ 4 block size. is coded in the bitstream and is watermarked in bitstream domain watermarking techniques, if the residual r ij for pixels at positions d, h, l, p, m, n, o in Figure 4(j) are unchanged, then the original pixels will remain unchanged.

Since these pixels are used in the prediction, the error brought by the watermark embedding process will not propagate in the intra frame. Moreover, if the prediction mode is unchanged, the bit-rate increment will only come from the entropy coding of a few modified coe cients and thus remain low. Since we aim to embed the watermark in the residual in the compressed domain, we need to explore the relationship between the spatial domain pixel values and the compressed domain coe cients.

The 4 ⇥ 4 residual matrix X is derived by the 4 ⇥ 4 de-quantized transform coe cient matrix Y as follows:

X = C T Y C (6)
The matrix C is defined in the H.264 standard.

C = 0 B B B B B B B B @ 1 1 1 1 1 0.5 0.5 1 1 1 1 1 0.5 1 1 0.5 1 C C C C C C C C A (7)
Transform matrix Y will be modified to Y 0 , such that the border pixels of

X 0 = C T Y 0
C are the same as those in X, i.e.:

C T Y 0 C C T Y C = X 0 X = D = 0 B B B B B B B B @ d 00 d 01 d 02 0 d 10 d 11 d 12 0 d 20 d 21 d 22 0 0 0 0 0 1 C C C C C C C C A (8) Y 0 can be written as Y + N , with N = 0 B B B B B B B B @
1 C C C C C C C C A
, and thus:

X 0 X = C T Y 0 C C T Y C = C T (Y + N )C C T Y C = C T NC = D (9)
Each d i,j = 0 in Equation 8 corresponds to a linear equation, we thus get seven linear equations in ! n = (n 00 , . . . , n 33 ) T .

P ! n = ! 0 ( 10
)
The solutions of this system of linear equations are spanned by a 9 element basis. Any linear combination of these basis vectors can be added to the dequantized coe cient matrix without changing the border pixels.

The nine possible basis that would preserve the last row and column for the blocks are given below in equation 11. As explained above, any summation of these basis matrices could be computed and be used as solution patterns that will preserve the "prediction pixels".

8 > > > > > > > > < > > > > > > > > : 0 B B B B B B B B @ 1 4 0 0 1 2 0 0 0 0 0 0 0 0 1 2 0 0 1 1 C C C C C C C C A , 0 B B B B B B B B @ 1 2 0 1 2 0 0 0 0 0 0 0 0 0 1 0 1 0 1 C C C C C C C C A , 0 B B B B B B B B @ 1 2 1 2 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 C C C C C C C C A , 0 B B B B B B B B @ 1 2 0 0 1 0 0 0 0 1 2 0 0 1 0 0 0 0 1 C C C C C C C C A , 0 B B B B B B B B @ 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 C C C C C C C C A , 0 B B B B B B B B @ 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 C C C C C C C C A , 0 B B B B B B B B @ 1 2 0 0 1 1 2 0 0 1 0 0 0 0 0 0 0 0 1 C C C C C C C C A , 0 B B B B B B B B @ 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 1 C C C C C C C C A , 0 B B B B B B B B @ 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 C C C C C C C C A 9 > > > > > > > > = > > > > > > > > ; (11)
Our watermark embedding requires two solution patterns of the linear system in order to embed a single symbol of the watermarking sequence. The solutions should modify important coe cients (close to the DC coe cient, but not the DC coe cient itself), but modify as few coe cients as possible, which are also most likely to be non-zero. Hence, we have selected patterns with the minimum amount of non-zero entries that contain non-zero entries close to the DC-coe cient. The following two solution patterns have been employed, each containing 4 non-zero coe cients:

We can notice that sol 1 actually corresponds to the matrix summation of the 8 th and 9 th elements of the basis matrices, whereas sol 2 corresponds to the matrix summation of the 6 th and 9 th elements of the basis matrices (see the nine basis matrices in equation 11).

We can thus use either solution sol 1 or sol 2 in order to embed a 1 or a 0 within the block:

8 > < > : y 1(i,j) = y i,j + ↵.sol 1(i,j) ! Embed watermark bit '0' y 2(i,j) = y i,j + ↵.sol 2(i,j) ! Embed watermark bit '1' (14)
↵ is a weighting parameter, for any ↵ value, the coe cient used for the prediction will be unchanged in y 1(i,j) and y 2(i,j) . In the following, we will explain how to use a JND model to optimize the embedding strength.

Watermark embedding

For a better imperceptibility, we have adapted DCTune [START_REF] Watson | DCT Quantization Matrices Visually Optimized for Individual Images[END_REF] to H.264/AVC. DCTune performs in the DCT transform domain. Since DCT transform has been replaced by integer transform (IT) in H.264/AVC, we have computed the DCTune visibility threshold using the IT. The adaptation of DCTune in our method is performed the same way as in [START_REF] Noorkami | A Framework for Robust Watermarking of H.264-Encoded Video With Controllable Detection Performance[END_REF]. Interested readers should refer to section II in [START_REF] Noorkami | A Framework for Robust Watermarking of H.264-Encoded Video With Controllable Detection Performance[END_REF] for in depth details on the DCTune adaptation. In a video frame, every area has di↵erent characteristics in terms of luminance, contrast and texture. Hence the sensitivity to human vision also varies from one area to another inside a video frame. DCTune computes a visibility threshold for every transformed coe cient in the DCT domain. DCTune considers both luminance masking and contrast masking. Luminance masking occurs in the bright portions of an image, where basically, our visual system is less sensitive to luminance variation. E↵ectively, the same luminance variation leads to a lower contrast in brighter areas (than in darker areas). Hence, information loss is less noticeable in bright portions of the image. Concerning contrast masking, the human visual system exhibits a reduced sensitivity when two components having similar frequencies and orientations are mixed together.

Watermark can be embedded in two ways as shown in Fig. 5. If we have raw video input, the watermark embedding and video compression steps can be simultaneously performed as shown in Fig. 5a. A 4x4 block is selected for embedding based on solution of linear equations and DCTune threshold. Since the watermark is embedded in encoded video and not in the original video, DCTune is employed on reconstructed video content as shown in Fig. 5a.

If the input video is in compressed form, we need to perform entropy decoding for watermark embedding as shown in Fig. 5b. In this case, video will be completely decoded for HVS mask creation by DCTune. It is pertinent to mention that complete video decoding is required only once. For example, if we want to embed 1000 di↵erent watermarks in a video bitstream, it would require entropy re-encoding 1000 times but a complete decoding only once.

For both approaches, the solutions of the system of linear equations are employed for watermarking the Quantized Transform Coe cients. One can note that the HVS masking operates on the decoded/reconstructed pixels, which already takes into account the quantization e↵ect. As previously explained, for each 4⇥4 block, a system of 7 linear equations is derived. Evidently, several solutions may exist to this system of equations.

In this work, for every "watermarkable" block, we need at least two solutions to exist. Basically, using either of these two solutions, allows us to embed the watermark information into the host media. In this work, once two solutions to the system are selected, they are used throughout all the blocks of every intra frame. Thus, two solution patterns of the system of linear equations are used to embed a single symbol of a bipolar watermark sequence W 2 { 1, +1} (with zero mean and unit variance). Consequently, using the two solution patterns, we either encode -1, or +1 within the considered block. During the detection, the cross-correlation of the two solutions with the possibly watermarked block is determined. Thus, the goal is to achieve a maximum di↵erence between these two correlations (cross-correlation gap ✓), while keeping the embedding strength within the DCTune visibility threshold. The DCTune JND mask provides a maximum allowable strength for every coe cient within the 4⇥4 block, thus, the transformed coe cients within the selected embedding patterns (see In order to determine the required processing power for the proposed algorithm, we performed a simulation on 50 frames of the tempete sequence in CIF format with a QP value of 24. For this simulation, three scenarios are considered: 1) Encoding only was performed on the sequence, 2) both encoding and watermark embedding was performed, and 3) the sequence was encoded and the watermark was weighted using DCTune before the embedding. For this experiment, a 2.1 GHz Intel Core 2 Duo T8100 machine with 3072 MB RAM was used. We have done this simulation both on intra only sequence and on intra & inter sequences. For intra only sequences, where a watermark is embedded within every frame, the encoding itself took 47.9 seconds for the whole sequence of 50 frames. When encoding the sequence and embedding the watermark, it took 48.9 seconds, and finally, when encoding and watermarking were performed using DCTune to weight the watermark strength, 49.3 seconds were needed.

Since intra only sequence is used very rarely and intra, followed by inter frames (IPP sequence) is used most of the time, the simulation was also conducted on intra & inter sequence with intra period of 10. On IP sequences, the encoding itself took 4078 seconds. When encoding the sequence and embedding the watermark, it took 4083 seconds, and finally, when encoding and watermarking were performed using DCTune to weight the watermark strength, 4084 seconds were needed.

The table 1 shows the processing time for all three scenarios. The processing times are given both in terms of average time per frame, and for the whole processing time needed for the 50 frames. We can observe that when I frames only are considered, the processing time is increased by less than 3% compared to the "encoding-only" scenario. When P frames are included in the sequence (intra period=10), the use of DCTune when embedding the watermark only increases the processing time by 0.15 %.

The proposed embedding process is thus slightly faster than the works in [START_REF] Ma | A Data Hiding Algorithm for H.264/AVC Video Streams Without Intra-Frame Distortion Drift[END_REF] where the authors mentioned: "The data hiding procedure for an I frame of the sequence Coastguard and Bridge-far cost 188 ms and 125 ms on average, respectively.". It should be noted that in [START_REF] Ma | A Data Hiding Algorithm for H.264/AVC Video Streams Without Intra-Frame Distortion Drift[END_REF], QCIF sequences were used, whereas in Table 1 we used CIF format sequences.

Moreover, in order to ensure a proper quality on Intra + Inter coded sequences, the PSNR was computed on an sequence containing both intra and inter coded frames. The figure 6 shows for every frame of the tempete sequence (50 frames) the PSNR when 1) only coding is applied (QP = 24) and 2) both coding and watermarking are applied. In this experiment, the intra period is 10, only the I frames are watermarked (frames 1, 11, 21, 31, 41). On average (across the 50 video frames), when encoding only was performed, the PSNR reaches 39.35 dB, and when both coding and watermarking are applied, the PSNR equals 38.89 dB. We can thus witness only a 0.46 dB decrease when the watermarking method is applied.

The following constraints are employed during the watermark embedding:

-Bit-rate constraint: we do not modify zero transform coe cients, i.e., these blocks are not used for embedding. -Imperceptibility constraint: DCTune visibility threshold is calculated for each transformed coe cient. Embedding is performed with the maximum embedding strength allowed by the DCTune visibility threshold.

-Robustness constraint: To guarantee the robustness of this scheme, the cross-correlation gap between the two added solution patterns should be greater than a pre-determined threshold ✓.

Embedding can be interpreted as a constrained optimization problem, in which we want to maximize the embedding strength under the constraints of bit rate, imperceptibility and robustness.

When modifying the residuals, several constraints need to be respected:

-A block is considered as watermarkable if at least two solution exist for the system of equations.

-For every watermarkable 4 ⇥ 4 block, the border pixels (x 03 , x 13 , x 23 , x 30 ,

x 31 , x 32 , x 33 ) must be kept unchanged (see Equation 8). -Modify the 4 ⇥ 4 blocks having non-zero coe cients at the positions determined in the selected solution patterns (see Eqs. 12 and 13).

-The watermark strength must remain below the visibility threshold as defined by DCTune.

-The cross-correlation gap between the two solution patterns should be above a threshold ✓.

Watermark detection

The detection of the watermark is performed in the compressed domain as well. Its procedure is shown in Figure 7 (within the dotted rectangle). During the watermark detection process, the data required during the retrieval procedure is: 1) the chosen solution patterns of the system of linear equations used for watermarking (sol 1 , sol 2 ) and 2) the watermarked block positions. The proposed detection algorithm is thus semi-blind as some side information needs to be transmitted to the detector. More precisely, 32 bits are needed to encode the solution patterns, and 21 bits are needed for every embedded watermark symbol to specify its particular location within the frame, and within the embedding block.

The detection actually proceeds in two separate steps, in a first step, a watermark is extracted from the potentially watermarked video sequence, and then, during the second step, a global detection is performed where a correlation is computed between the original watermark and its extracted counterpart. These two steps are detailed thereafter.

Watermarked transform coe cients are extracted from the watermarked block. Let Z be the extracted 4⇥4 block, which can be extracted directly from the bitstream by partially decoding it as shown in Figure 7. We will extract one bit of watermark from the block Z using a normalized cross-correlation Fig. 7: Watermark detection procedure with each of (sol 1 , sol 2 ) to find which solution pattern has been embedded as explained in Algorithm 1.

Algorithm 1 Extraction of one bit of watermark message from extracted block Z.

1: if xcorr(Z, sol 1 ) > xcorr(Z, sol 2 ) then 2: sol 1 detected ! Extract watermark bit '0' 3: else 4: if xcorr(Z, sol 2 ) > xcorr(Z, sol 1 ) then 5: sol 2 detected ! Extract watermark bit '1' 6: end if 7: end if 8: end
Once the extraction of all the watermark symbols is performed, the so obtained watermark sequence W M ext is compared to the original watermark sequence using a normalized cross-correlation. A detection threshold has to be determined, in order to ensure a proper detection [START_REF] Miller | Computing the Probability of False Watermark Detection[END_REF][START_REF] Piva | Threshold Selection for Correlation-Based Watermark Detection[END_REF][START_REF] Autrusseau | A Robust Image Watermarking Technique Based on Quantization Noise Visibility Threshold[END_REF]. False alarm and missed detection rates were computed in order to select the optimal detection threshold as explained in detail in Section 4. The second cross-correlation differs from the first one in the sense that it is employed to detect the watermark sequence, while the first correlation is employed to extract a symbol of the watermarking sequence, i.e., is employed to determine which solution pattern has been embedded in the block.

Simulation Results

This section presents evaluations of the proposed watermarking algorithm1 .

We have used a custom implementation based on the H.264/AVC reference software JM 12.22 . Several benchmark video sequences containing di↵erent combinations of motion, texture and objects have been used. In the following, unless otherwise specified, the benchmark sequences were in CIF format (352 ⇥ 288 pixels). In Section 4.1, the choice of a proper detection threshold is presented. The payload and invisibility of our algorithm are assessed as well.

Finally, the robustness of the technique is tested against recompression.

Detection Threshold

The choice of the optimal detection threshold was obtained by computing the false alarm and missed detection rate on 100 samples, each sample is made of three consecutive intra frames. The false positive and false negative rates were computed and led to an optimum detection threshold at 0.3 as depicted in Figure 8. These thresholds allow minimization of false positives, while granting a very weak false negative rate. We deliberately chose here to avoid false positives, in order to ensure that no watermark is detected in an unmarked video. Figure 8 shows the detection performances for five benchmark video sequences. Gray curves indicate the detector result when it is looking for a wrong watermark, while the black curve indicates the results for an original watermark.

In Figure 8(a) the watermarked sequences were re-encoded using a QP value of 34, whereas, in Figure 8(b) the re-encoding used a QP value of 40, and thus the true positives decreases.

Concerning the selection of a detection threshold, two detection scenarios need to be considered. The hypothesis H 0 when no watermark is actually embedded into the host media (or the detector seek for a di↵erent watermark), and the hypothesis H 1 when the correct watermark is indeed embedded into the input sequence. The detector is run on a large number of sequences under the two assumptions, H 0 and H 1 , and the distribution of the detector is plotted for both cases. This way, two distinct distributions (commonly Gaussian) can be observed while varying the detection threshold. Ideally, the two distributions H 0 and H 1 should not overlap, which then allows us to set a detection threshold in between the two distributions. Distributions for the two hypothe- Percantage of detected watermarks marked "bus" marked "mobile" marked "paris" marked "tempete" marked "waterfall"' un-marked "bus" un-marked "mobile" un-marked "paris" un-marked "tempete" un-marked "waterfall" Percentage of detected watermarks marked "bus" marked "mobile" marked "paris" marked "tempete" marked "waterfall" un-marked "bus" un-marked "mobile" un-marked "paris" un-marked "tempete" un-marked "waterfall"

(b) QP = 40 ses H 0 and H 1 for QP value of 34 and 40 are depicted in Figure 9(a) and Figure 9(b) respectively. Moreover, Figure 9(c) shows all the 500 detections (whether detected or undetected) for all the sequences. In this plot, five input sequences were considered ("bus", "mobile", "paris", "tempete" and "waterfall"), each one was either watermarked with the correct embedding sequence that is used by the detector (H 1 , represented by gray circles) or watermarked with a di↵erent watermark sequence (H 0 , represented by white squares). For each of the five input sequences, 100 watermarked versions were generated, and thus, the H 0 and H 1 distributions are each composed of 500 data points.

Analysis of payload, bit-rate and visual quality

The watermark embedding payload is dependent on two parameters: video content and QP value. The more the video content exhibits textures and motion, the higher is the payload. Table 2 shows the payload, bit-rate increment and PSNR decrease for the benchmark sequences at QP value of 24. The negative value of bit-rate modification actually represents a reduction in bit-rate.

Bit-rate change is so small that it is shown in milli( 103 ) of percent. One can observe that the proposed technique has a negligible e↵ect on PSNR as well, with only 0.064 dB increase, while having an acceptable payload, and a similar bit-rate. It is important to notice that there is a negligible change in the bit-rate despite the fact that we have embedded the watermark message with the maximum embedding strength allowed by DCTune, to make our scheme more robust. Re-compression is the most traditional non-intentional attack against watermarked videos. Evidently, the higher is the quantization step, the more devastating is the attack.

Comparison with previous works

For the sake of comparison with the recent works on H.264/AVC watermarking, we compared the performances of our watermarking system with [START_REF] Noorkami | Compressed-Domain Video Watermarking for H.264[END_REF] and [START_REF] Noorkami | A Framework for Robust Watermarking of H.264-Encoded Video With Controllable Detection Performance[END_REF] in terms of both PSNR and watermark payload. The PSNR were computed for three watermarked videos, either for the watermarking technique operating within the encoder or in the bitstream. In the following experiments QCIF sequences were used (144 ⇥ 176 pixels), as this was the format used by the authors in [START_REF] Noorkami | Compressed-Domain Video Watermarking for H.264[END_REF] and [START_REF] Noorkami | A Framework for Robust Watermarking of H.264-Encoded Video With Controllable Detection Performance[END_REF]. Figure 10 shows the PSNR for both the proposed technique and [START_REF] Noorkami | A Framework for Robust Watermarking of H.264-Encoded Video With Controllable Detection Performance[END_REF]. It is important to notice that in [START_REF] Noorkami | A Framework for Robust Watermarking of H.264-Encoded Video With Controllable Detection Performance[END_REF], the spreading of the prediction error when the watermark is embedded in the bitstream quickly leads to a severe quality loss. On the other hand, PSNR closely overlap in the proposed scheme. For example, for the bus video sequence, the PSNR are respectively 40.05 dB and 39.93 dB in the encoder and in the bitstream. The di↵erence in the PSNR in the proposed scheme is due to the quantization step.

Moreover, in [START_REF] Noorkami | A Framework for Robust Watermarking of H.264-Encoded Video With Controllable Detection Performance[END_REF], the authors stated: On average, watermark embedding using our algorithm increases the bit rate of the video by about 5.6% (...)

readers might find it useful to know that the PSNR of the watermarked video decreases 0.58 dB compared to the compressed (but unwatermarked) video (...).

As we will see in the following, in the proposed method, the bit-rate increase is marginal, and the PSNR decrease remains very low.

We summarize in Table 5 the performances of our algorithm in terms of bit-rate increase, PSNR decrease, and payload. We highlight the di↵erences in terms of payload between the proposed watermarking system and the works in [START_REF] Noorkami | Compressed-Domain Video Watermarking for H.264[END_REF]. We can notice on this table that the two methods present similar watermark payload. Moreover, we also present in Table 5 the payload obtained in [START_REF] Noorkami | A Framework for Robust Watermarking of H.264-Encoded Video With Controllable Detection Performance[END_REF]. We can notice that the payload from our proposed embedding technique cannot compete with the payload presented in [START_REF] Noorkami | A Framework for Robust Watermarking of H.264-Encoded Video With Controllable Detection Performance[END_REF], but on the other hand the bit-rate modification is marginal with our method. The authors in [START_REF] Noorkami | A Framework for Robust Watermarking of H.264-Encoded Video With Controllable Detection Performance[END_REF] did not provide the bit-rate increase per input sequence, but, as explained above, the average bit-rate increase for their method was about 5.6%.

(a) Algorithm [START_REF] Noorkami | A Framework for Robust Watermarking of H.264-Encoded Video With Controllable Detection Performance[END_REF] (b) Proposed algorithm Fig. 10: Comparison of PSNR values with the method presented in [START_REF] Noorkami | A Framework for Robust Watermarking of H.264-Encoded Video With Controllable Detection Performance[END_REF]. Seven QP values for both the Encoder and Bitstream scenarios.

It is important to notice that the watermarking methods in [START_REF] Noorkami | Compressed-Domain Video Watermarking for H.264[END_REF][START_REF] Noorkami | A Framework for Robust Watermarking of H.264-Encoded Video With Controllable Detection Performance[END_REF] are blind, whereas our algorithm is semi-blind, as previously explained.

Finally, we show in Table 6 a performance comparison with [START_REF] Ma | A Data Hiding Algorithm for H.264/AVC Video Streams Without Intra-Frame Distortion Drift[END_REF] in terms of both bit-rate increase and Payload.

Again, we can witness that the method from [START_REF] Ma | A Data Hiding Algorithm for H.264/AVC Video Streams Without Intra-Frame Distortion Drift[END_REF] o↵ers a higher embedding capacity, but also leads to a higher bit-rate increase. Such an increase could become an important issue when dealing with high definition video sequences.

Table 5: Comparison of payload per frame with the algorithm presented in [START_REF] Noorkami | Compressed-Domain Video Watermarking for H.264[END_REF] and [START_REF] Noorkami | A Framework for Robust Watermarking of H.264-Encoded Video With Controllable Detection Performance[END_REF]. BRi: bit-rate increase, PSNRd: PSNR decrease, P: Payload (in bits per frame) 1.23e-3 52 7.17 936

Discussion

In these experiments, we have only embedded in very specific 4 ⇥ 4 blocks: 1) all of the coe cients involved in watermark embedding are non-zero, 2) the cross-correlation gap between the two watermarking patterns must be greater than ✓, and 3) the embedding strength must be within DCTune threshold for that block. If all the three constraints are satisfied, we embed the watermark message bit using the maximum allowable strength by DCTune. In our experiments, we have selected only two solutions to embed a watermark and if any of the above-mentioned constraints are not met for those two solutions, we do not embed any watermark bit in that block.

Our main goal in this work was to provide a robust embedding technique while granting a minimum bit rate modification and high quality marked sequences. We did not intend to provide a high payload embedding. However, it is important to note that the watermark payload, and consequently, the robustness could significantly be improved if more than two solutions were selected. The above-mentioned objectives (robustness, invisibility, bit-rate) were reached using a bipolar watermark. Nevertheless, future will be devoted to study the possible improvements of using a multipolar watermark.

In [START_REF] Noorkami | A Framework for Robust Watermarking of H.264-Encoded Video With Controllable Detection Performance[END_REF], the authors used a human visual system model adapted for 4 ⇥ 4

DCT blocks, while we have used DCTune for this purpose. Since the embedding position inside the 4 ⇥ 4 block depends on the solutions of the linear system and such solution patterns could be randomly selected to increase security.

We have used the experimental threshold for embedding and cross-correlation to detect the watermark. In [START_REF] Noorkami | A Framework for Robust Watermarking of H.264-Encoded Video With Controllable Detection Performance[END_REF], the authors establish a theoretical framework for watermark detection, however, this framework only applies for blind detection. Our experiment prove that our algorithm can resist recompression even associated with a high quality degradation.

Conclusion

In this paper, we proposed an intra-drift-free robust watermarking algorithm for H.264/AVC in the compressed domain. A system of linear equations is solved to determine additive watermarking patterns for the H.264 4 ⇥ 4 transform coe cients that do not cause intra-drift in the pixel domain. The watermarking strength is adjusted with an adapted DCTune JND mask. A crosscorrelation based detection system is employed to guarantee the robustness.

The proposed scheme preserves the bit-rate on average, there is often even a decrease in bit-rate. This is a significant advantage compared to previously proposed approaches, which lead to an increase in bit-rate of the watermarked video. Another advantage of our approach is its runtime-e ciency.

Hence the proposed scheme is very suitable for real-time applications, such as video streaming of actively fingerprinted content. At the same time, we see a negligible e↵ect on visual quality (results are given in terms of PSNR).

The watermark remains detectable in re-compressed videos, even in very low quality and highly distorted video sequences (encoded with a high QP).

Figure 2

 2 Figure 2 summarizes the di↵erent embedding stages that we can encounter in

Fig. 2 :

 2 Fig. 2: Classification of watermarking schemes on the basis of working domain: (1) Pre-compression, (2) Transform domain, (3) Quantized transform domain, (4) Open-loop.

Fig. 3 :

 3 Fig. 3: H.264/AVC intra prediction in spatial domain: (a) Prediction is performed from pixels at left and top of every 4⇥4 block for I 4⇥4 mode. Moreover, 4 ⇥ 4 blocks are transmitted in a dyadic manner inside a MB, (b) Prediction is performed at MB level for I 16⇥16 mode. The order of transmission of 4 ⇥ 4 blocks inside a MB is in a raster scan fashion. In this mode, DC coe cients are further transformed using Hadamard transform and are sent before AC coe cients.

Figure 4 (Fig. 4 :

 44 Figure 4(j), shows the labeling of prediction sample. The prediction is based on pixels labeled A to M for the current block. Thus, the d, h, l, p, m, n, o pixels will be used for future prediction. Since it is only the residual r ij which

Fig. 5 :

 5 Fig. 5: Block diagram of drift-free robust watermarking system for H.264/AVC, (a) raw video input, and (b) H.264 bitstream input.

Equations 12 and 13 )

 13 are successively increased until their value reaches the DCTune threshold. For every considered 4 ⇥ 4 block, DCTune provides a 4 ⇥ 4 JND matrix. During the perceptual optimization, we use the minimum JND coe cient being non-zero in either sol 1 or sol 2 (see Equations 12 and 13). This minimum perceptual weighting coe cient is then used as ↵ in Equation 14. It is important to note that only the coe cients located within the patterns sol 1 or sol 2 are modified, all other coe cients are kept unchanged. It is important to note that the DCTune mask coe cients are not needed during the detection stage.

Fig. 6 :

 6 Fig.6: PSNR computed on every frame of I+P coded sequence for either coding only, or watermarked sequence.

Fig. 8 :

 8 Fig. 8: Experimental analysis for threshold selection (false positives and true negatives).

  Fig. 9: a) H 0 vs. H 1 analysis and detection for all five input sequences.

Table 1 :

 1 Processing time when 1) encoding only is applied, 2) encoding and watermarking are applied, and 3) encoding and DCTune adapted watermarking are performed.

	Average processing	Global processing
	time (sec / frame)	time (sec)

Table 2 :

 2 Analysis of the proposed algorithm in terms of payload (per frame), bit-rate and PSNR at QP Values of 24 for benchmark sequences.

	Seq	Payload	Bit-rate increase PSNR decrease
		(per frame)	(x 10 3 %)	(dB)
	"bus"	210.76	-0.52	0.06
	"mobile"	275.28	-0.47	0.13
	"paris"	117.88	-0.38	0.06
	"tempete"	179.24	-0.13	0.05
	"waterfall"	173.6	-0.12	0.02
	Average	191.35	-0.324	0.064

Table 3 :

 3 Analysis of the proposed algorithm in terms of payload (per frame), bit-rate and PSNR for di↵erent QP Values for the tempete sequence.Video content can be encoded at di↵erent quality levels using di↵erent QP values. Hence, it is important to observe the payload of the proposed scheme on di↵erent QP values. Table3shows the analysis of our proposed scheme at di↵erent QP values for benchmark video sequence tempete. It is evident that the proposed scheme conserves bit-rate and PSNR for the whole range of QP values. Nevertheless, payload reduces with increase in QP value. It is because we embed our watermark symbols only in blocks where solely non-zero coe cients are a↵ected. The number of such blocks is reduced with the increase in the QP value.

	QP	Payload	Bit-rate increase PSNR decrease
		(per frame)	(x 10 3 %)	(dB)
	16	250.38	-0.11	0.28
	20	221.28	-0.16	0.12
	24	179.24	-0.13	0.05
	28	132.8	-0.39	0.02
	32	72.54	0.12	0
	36	23.02	-0.80	0

Table 4 :

 4 Table 4 summarizes the cross-correlation peaks for five benchmark video sequences for re-compression with 10 di↵erent QP values (from 24 to 42 with a step of 2). These results show that the watermark is successfully detected up to a QP value of 40. In Table4the gray shaded cells represent the missed detections (the peak correlation is below the detection threshold). Watermark detection rate for benchmark video sequences under recompression at di↵erent QP values (originally encoded at QP value of 24).

	Video/QP	24	26	28	30	32	34	36	38	40	42
	"bus"	1.00	0.79	0.77	0.74	0.71	0.66	0.54	0.39	0.30	0.23
	"mobile"	0.99	0.82	0.81	0.81	0.80	0.71	0.66	0.52	0.56	0.43
	"paris"	0.98	0.94	0.84	0.80	0.75	0.69	0.55	0.46	0.33	0.32
	"tempete"	1.00	0.83	0.72	0.71	0.67	0.62	0.58	0.52	0.42	0.32
	"waterfall"	0.97	0.82	0.78	0.72	0.60	0.51	0.45	0.39	0.34	0.21

Table 6 :

 6 Comparison with[START_REF] Ma | A Data Hiding Algorithm for H.264/AVC Video Streams Without Intra-Frame Distortion Drift[END_REF] in terms of bit-rate modification and Payload.

		Proposed method		from [19]	from [20]
		PSNRd	BRi		P	BRi	P	P
		(dB)	(%)	(bpf)	(%)	(bpf)	(bpf)
	"Carphone"	0.11	-2.69e-5	37	0.80	44	891
	"Claire"	0.14	1.75e-3		34	0.44	22	450
	"Mobile"	0.38	-3.51e-3	71	0.23	85	2291
	"Mother"	0.14	8.11e-4		36	0.69	42	630
	"Salesman"	0.12	1.23e-3		52	N/A N/A	953
	"Soccer"	0.11	-2.14e-5	52	N/A N/A	N/A
	"Table"	0.08	1.09e-3		44	0.31	38	810
	"Tempete"	0.14	2.79e-4		45	0.44	81	N/A
			Proposed		Ma et al. [16]
			BRi (%)	P (bpf)	BRi (%)	P (bpf)
	"carphone"	-2.69e-5	37		3.24	806
	"mobile"	-3.51e-3	71		0.88	910
	"salesman"

A demo is available for download at the following URL: http://www.irccyn.ecnantes.fr/autrusse/DEMO/

2 http://iphome.hhi.de/suehring/tml/


Ihsan Ullah
email: ihsan.ullah@utt.fr

Guillaume Doyen
email: doyen@utt.fr

Grégory Bonnet
email: bonnet@utt.fr

Dominique Gaïti
email: gaiti@utt.fr

User Behavior Anticipation in P2P Live Video Streaming Systems through a Bayesian Network

For a few years, Peer-to-Peer (P2P) architectures have emerged as a scalable, low cost and easily deployable solution for live video streaming applications. In these systems, the load of video transmission is distributed over end-hosts by enabling them to relay the content to each other. Since end-hosts are controlled by users, their behavior directly impact the performance of the system. To understand it, massive measurement campaigns covering large-scale systems and long time periods have been performed. In this paper, we gathered and synthesized results obtained through these measurements and propose a Bayesian network that captures and integrates all of them into a synthetic model. We apply this model to the anticipation of peer departures which is an important challenge toward the performance improvement of these systems and especially churn resilience. The validation of our proposal is performed through intensive simulations that consider a streaming system composed of thousand users over two hundred days. We especially study two deployment scenarios: a system-scale one and a local one. We also compare our proposal with two standard estimators and we show under which conditions an estimator outperforms the others.

I. INTRODUCTION

During the past few years P2P video streaming has attracted great attention in both academia and industry. On one hand it does not require any major change in the current Internet infrastructure unlike IP multicast. On the other hand, it pushes the load of content delivery to the end-hosts through sharing their upload bandwidth. It makes these systems scalable as compared to centralized Client/Server (C/S) architecture which requires an increase in the servers' capacities with an increase in the number of users. Moreover, a P2P system is easy to deploy with a low cost.

P2P approach enables end-hosts to self-organize into a virtual network where a peer not only receives the content but also transmits it to other peers. Since these peers are controlled by users, their behavior directly impacts the virtual network and consequently the performance of the system. Therefore, management of P2P streaming networks with an awareness of user behavior becomes critical.

To do so, first an understanding of user behavior and then its modeling are required. For an understanding of user behavior we have gathered, analyzed and synthesized the measurement studies found in the literature over user behavior in video streaming systems. We extracted from them the components of a user behavior, environmental factors that impact these com-ponents and the network parameters that are impacted by these components. On this basis, we model the relationships among all these elements through a Bayesian network that allows the estimation of a user activity. This Bayesian network enables thus the management of the P2P network with an awareness of user activities and eventually improves the performance. Applications of such a network cover a large spectrum, from the anticipation of system size and churn or the estimation of streaming quality. In this paper, we focus on the estimation of the departure time of peers. The latter is crucial to avoid service disruption in the content delivery and the use of large buffer that induces a significant delay in real-time programs.

In order to validate our model, we simulate two scenarios. In the first scenario, the whole population of users is considered together requiring thus only one Bayesian network for their behavior estimation. In the second scenario, we estimate the activities of individual users which require one Bayesian network for each user present in the P2P system. We intensively analyze the performance of our Bayesian network over these two scenarios. We also compare the performance of the Bayesian network for departure time estimation with two others estimators. The first relies on an exponential moving average and the second on a Bayesian estimation restricted to historical session times. These two alternative estimators do not integrate any contextual information and we show under which conditions the use of a Bayesian network is relevant.

The rest of the paper is organized as follows. In section II, we discuss works related to user behavior modeling. Section III first gives a synthesis of user behavior measurements for identification of user behavior metrics and their relationships. It is followed by the presentation of the user behavior model. Section IV provides the simulation details and results for the validation of our network. Finally, section V gives conclusions and future directions.

II. RELATED WORK

Most of the works on user behavior in live streaming systems are dedicated to its measurements. There are a few others that also model some aspects of user behavior. Here, we only discuss the latter.

Tang et al. [START_REF] Tang | Characterizing user behavior to improve quality of streaming service over P2P networks[END_REF] measure the stability of users in a C/S and a P2P video streaming system and find a positive correlation between the elapsed time of a user and remaining time of a Oct. 2006 (1 day) [START_REF] Li | An empirical study of the Coolstreaming+ system[END_REF] Sep. 2006 (1 day) [START_REF]A case study of large scale P2P video multicast[END_REF] unknown 2006 (11 hours) [START_REF] Tang | Longer, better: On extending user online duration to improve quality of streaming service in P2P networks[END_REF] GridMedia Jan. 2006 (4.5 hours) [START_REF] Liu | Distilling superior peers in largescale P2P streaming systems[END_REF] UUSee May to Jun. 2008 (5 days) [START_REF] Tang | Characterizing user behavior to improve quality of streaming service over P2P networks[END_REF] CCTV Feb. 2005/Jan. 2006 (2 pop. events) [START_REF] Tang | Characterizing user behavior to improve quality of streaming service over P2P networks[END_REF] C/S Oct. to Jan. 2004 -05 [START_REF] Sripanidkulchai | An analysis of live streaming workloads on the Internet[END_REF] Akamai Oct. to Jan. 2003 -04 [START_REF] Veloso | A hierarchical characterization of a live streaming media workload[END_REF] unknown 2002 (90 days) [START_REF] Qiu | Modeling user activities in a large IPTV system[END_REF] IPTV Telco-Managed

Apr. 2008 (6 days) [START_REF] Qiu | Modeling channel popularity dynamics in a large IPTV system[END_REF] Jun. 2008 (1 month) [START_REF] Cha | Watching television over an IP network[END_REF] May to Oct. [3] use a similar method for the identification of stable peers. To minimize the impact of churn, they put those peers in the backbone. The method of stable peers identification in both of these approaches tends to assume all the peers that have recently joined the system as unstable which is not always the case.

The above approaches do not consider any external impacting factors on the stability of users. By contrast, Liu et al. [START_REF] Liu | Distilling superior peers in largescale P2P streaming systems[END_REF] measure a P2P live streaming system and analyze some potential impacting factors on users' stability and bandwidth contribution ratios. They observe that some of them such as streaming quality impact the stability and bandwidth contribution ratios of peers. Based on this finding they present models for predicting the longevity and bandwidth contribution ratios of peers. However, their models are global for all user behaviors while the behavior of an individual can be different from the global one.

Horovitz et al. [START_REF] Horovitz | Collabrium: Active traffic pattern prediction for boosting P2P collaboration[END_REF] propose a machine learning approach based on Support Vector Machines (SVM) for detecting actively the load in the uplink of provider peers. This approach only considers upload bandwidth contribution as a metric of the user behavior, while others such as stability of the provider peers are also important for the performance.

In our earlier work [START_REF] Ullah | Improving performance of ALM systems with Bayesian estimation of peers dynamics[END_REF], we proposed peers' stability estimators based on history of a user's past sessions to estimate his current session duration. Estimators are based on Exponential Moving Average (EMA) and Bayes' rule. Moreover, a proactive mechanism of switching to a new upstream peer before the anticipated departure of the current upstream peer was proposed. The limitation of this work was that it did not take into account other external impacting factors. Therefore, in [START_REF]Modeling user behavior in P2P live video streaming systems through a Bayesian network[END_REF], we presented a preliminary model of user behavior through a Bayesian network that takes into account all the known impacting factors. The limit of this model was the binomial variables which could not estimate states of metrics with a satisfying granularity.

III. UNDERSTANDING AND MODELING OF USER BEHAVIOR

In this section, we first give a brief synthesis of user behavior measurements that highlights the components of user behavior and their relationships with the external environment and network. Then we present our Bayesian network and explain its structure.

A. Understanding user behavior

To get an understanding of user behavior in video streaming systems, we collect all measurements from the literature and perform their synthesis. An overview of these measurements is shown in Table I. This table summarizes the reference of the measurement, the type and name of the system that was studied, the measurement time period, the methodology used for data collection and the observed metrics. It is obvious from this table that taking only one study into account is not sufficient to model user behavior accurately, because each measurement analyzes a few metrics under different conditions. Moreover, other information such as the dependency relationships of metrics with the environment and among themselves are not shown in the table which are split among different measurements and cannot be found in only one work. A global picture of these relationships is shown in Figure 1. An edge from one node to another shows the impact of one element on the other one. To explain these relationships, we discuss each impacted element with its impacting factors in the following. Studies [START_REF] Jia | Characterizing PPStream across Internet[END_REF], [START_REF] Hei | A measurement study of a large-scale P2P IPTV system[END_REF], [START_REF] Cha | Watching television over an IP network[END_REF], [START_REF] Sripanidkulchai | An analysis of live streaming workloads on the Internet[END_REF] agree on a higher arrival rate at the beginning of a program and higher departure rate at the end of the program as compared to the middle of a program. Channel switches during commercial breaks have been observed too. Arrival rates are smoother than departure rates because the number of users normally increases gradually at the start of a program, while the departures usually occur in batches towards the end of a program [START_REF] Cha | Watching television over an IP network[END_REF]. Since most of the TV programs and commercial breaks are scheduled on fixed times, time has an impact on arrival and departure rates of users onto a channel. Apart from time, content type also impacts the departure rate. Hei et al. [START_REF] Hei | A measurement study of a large-scale P2P IPTV system[END_REF] observe batch departures in a movie channel but they do not find this behavior in another (unspecified) popular type of channel.

2) Channel popularity: Since we are only interested in the user behavior at a particular time instance, we only consider the popularity of a channel at that time also called instantaneous popularity. Channel popularity is impacted by time-of-day, arrival rate and departure rate. Qiu et al. [START_REF] Qiu | Modeling user activities in a large IPTV system[END_REF] find diurnal patterns in popularity dynamics. It means that popularity is time dependent and varies during a day. Similarly, it is evident that higher arrival rate than the departure rate increases the instantaneous popularity and vice versa. For BitTorrent system, Guo et al. [START_REF] Guo | Measurements, analysis, and modeling of BitTorrent-like systems[END_REF] define the popularity of a torrent at a time as the peer arrival rate at that time.

3) Session duration: Holding time of a channel, called session duration, is impacted by the elapsed time in a session, streaming quality, popularity, type of content, time-of-day and day-of-week. Studies [START_REF] Tang | Characterizing user behavior to improve quality of streaming service over P2P networks[END_REF], [START_REF] Cha | Watching television over an IP network[END_REF] report a positive correlation between the elapsed time and remaining time of a session. Liu et al. [START_REF] Liu | Distilling superior peers in largescale P2P streaming systems[END_REF], [START_REF] Liu | Why are peers less stable in unpopular P2P streaming channels?[END_REF] find a strong correlation between the initial streaming quality and session duration of a peer. It states that a user receiving a good buffer level joining a channel is willing to stay longer. Popularity of a channel also impacts the session duration. Users stay longer while watching popular programs as compared to unpopular ones [START_REF] Liu | Distilling superior peers in largescale P2P streaming systems[END_REF], [START_REF] Hei | A measurement study of a large-scale P2P IPTV system[END_REF], [START_REF] Liu | Why are peers less stable in unpopular P2P streaming channels?[END_REF]. Similarly, the time spent on each channel changes with the type of the channel. Cha et al. [START_REF] Cha | Watching television over an IP network[END_REF] observe shorter session durations for news and music channels than documentaries and kids channels. Finally, Liu et al. [START_REF] Liu | Distilling superior peers in largescale P2P streaming systems[END_REF] reveal that session duration has a strong correlation with time-of-day but no correlation with day-of-week, but Veloso et al. [START_REF] Veloso | A hierarchical characterization of a live streaming media workload[END_REF] present a contrasting finding that time-of-day does not impact the session duration, while day-of-week has an impact on it.

4) Other impacted parameters: Here we discuss those parameters that are less studied than the above-mentioned ones.

• Surfing probability: Surfing (channel browsing) probability is impacted by time-of-day and type of content, which increases for less popular channels and specific genres like news and music [START_REF] Cha | Watching television over an IP network[END_REF], [START_REF] Qiu | Modeling user activities in a large IPTV system[END_REF].

• Failure rate: The departure of a user from a channel before the video player becomes ready, called failure, is strongly correlated with the overall arrival/departure rates of users [START_REF] Xie | A measurement of a large-scale Peerto-Peer live video streaming system[END_REF].

• Delay: Playback delay is increased with an increase in popularity and arrival/departuer rates [START_REF] Jia | Characterizing PPStream across Internet[END_REF].

• Streaming quality: The quality of streaming is impacted by arrival and departure rates. It degrades under flash crowds and high departure rates [START_REF] Liu | Distilling superior peers in largescale P2P streaming systems[END_REF].

• Bandwidth contribution ratio: User bandwidth contribution ratio is found to be strongly correlated with initial streaming quality a user receives and popularity of the channel [START_REF] Liu | Distilling superior peers in largescale P2P streaming systems[END_REF].

• Partners discovery: A peer can find partner peers easily while watching a popular channel [START_REF] Zhang | On large scale Peer-to-Peer live video distribution: Coolstreaming and its prelimianry experimental results[END_REF], [START_REF] Vu | Measurement and modeling of a large-scale overlay for multimedia streaming[END_REF].

B. User behavior modeling

We require a model that can predict the next state of a user behavior metric. For example, whether the user will stay or leave during certain time period or/and what will be the bandwidth contribution ratio of a user during a next time period. This is an online analysis where prediction of future observations is needed given observations up to the present time. Moreover, the problem domain contains different variables with dependencies among them. Bayesian networks are well-suited in modeling such type of domains for a number of reasons. Firstly, they are expressive for modeling real-world problems. Secondly, prior knowledge can be incorporated into the network in the absence of any observation. Finally, they model well the relationships of causes and effects.

1) Bayesian networks: Bayesian networks (BN) are graphical models for problems of uncertain reasoning. They are made of two main components namely structure and parameters. The structure is an acyclic graph that encodes variables through nodes. The probabilistic conditional independence relationships among variables are encoded through arcs. A directed arc from one node to another makes them parent and child nodes respectively. A child node is dependent on its parent node. A node is conditionally independent from all other nodes given its parents. The joint probability distribution of variables in a Bayesian network can be written in the form shown in Eq. ( 1)

P (U ) = P (X 1 , ..., X n ) = n i=1 p(X i |parents(X i )) (1)
The network structure can be constructed by an expert or learned from data. Similarly, parameters can be assigned manually or learned from data. In our work, we construct the network manually and let it learn its parameters from the data.

2) Proposed model: Based on the synthesis of measurement studies, the Bayesian network we propose is depicted in Figure 2. It involves 10 nodes each of them representing a component of user behavior, an impacting factor of these components or a network performance metric derived from the graph given in Figure 1. Day-of-week is omitted since it was observed only within two measurements with contradicting results. Surfing probability and failure rate are both merged into session duration because both of them represent short session durations and they can be represented by the session duration variable. Partners discovery has been excluded since it is required only in mesh-based systems and can be easily added if needed.

3) Node types: Our Bayesian network is a mixed model having both discrete and continuous variables. Discrete variables have been shown through rectangles and continuous ones through ellipses. In case of discrete variables, the number of states of a variable should also be chosen. Since our workload contains three content types, we choose three states for the content type variable. Similarly, we choose binary states for elapsed time of a user. Elapsed time can determine wether a user is in surfing mode or viewing mode. Cha et al. [START_REF] Cha | Watching television over an IP network[END_REF] observe that the channel holding time in surfing mode can last up to 2 minutes. Therefore, elapsed time less than 2 minutes makes the first state while the second state is assigned to greater values. Concerning time-of-day, it can be discretized with several intervals and we discuss it in section IV-B1.

Since user behavior is highly dynamic and an accurate quantification of the dependencies among the variables is not possible, we let our network learn its parameters from data. In a real P2P network, it will be the case where the dependencies among different variables for each user are different and should be learned online.

IV. VALIDATION

In order to validate our proposal, we performed intensive simulations considering different scenarios. Results presented in this section have been obtained through Matlab and the Bayes Net Toolbox1 extension. The duration of each simulation was about some hours up to thirty for some of them, leading to more than one hundred simulation hours for the whole presented results.

A. Simulation framework 1) Simulation scenarios: In order to evaluate the performance of our proposal, we considered two simulations scenarios standing for realistic concrete deployments. In the first one, we consider that the target P2P video streaming system presents a central entity owned by the service provider. This central entity could for example be used to authenticate peers as in the case of Skype. It would thus have a knowledge of all information depicted in our Bayesian network, from joining and leaving operations to the type of watched content and time-of-day. The estimation of session time of each peer is done considering information provided by the whole community.

In the second scenario, we consider a deployment of our Bayesian network directly into peers. In this case, only local information is directly known. These are the joining and leaving operations, the type of content the user watches and time-of-day. Nonetheless, external information, resulting from a community-scale aggregation, must be taken into account in order to complete the inference on the Bayesian network. The latter are the arrival and departure rates, and the population. We consider that such indicators can be easily obtained through the use of a decentralized aggregation protocol based on a tree structure or a gossiping approach and thus can be known by every peer with an acceptable accuracy.

For the two presented scenarios, simulation parameters are given in Table II.

2) Workload generation model: As a global model is inadequate to model a population of users with different behaviors, we inspired from [START_REF] Rudstrom | Capturing TV user behaviour in fictional character descriptions[END_REF] that defined different representative and fictional television watchers with different preferences and habits, called personas 2 . Each single user is associated with a persona. It is controlled by a non-homogeneous semimarkovian process whose parameters are set according to the given persona. It means that the state of a user at a given time not only follows the markovian assumption (dependance on the state at the previous time) but also on the time it spends in this state and on the global time of the process. Such kind of process fits well with the video streaming context because, as explained in Section III-A, the behavior of a user vary with respect to the time of the day (e.g. watching longer or more often in the evening than in the morning) and the time spent online impacts the time it will stay. Our Markov process owns the following features: 1) We only consider mono-channel video streaming applications. Consequently, we define two states {X 1 , X 2 } where their semantic is respectively the user's online presence and its offline presence; 2) We consider that the user behavior is a cyclic behavior on each day as highlighted by [START_REF] Liu | Distilling superior peers in largescale P2P streaming systems[END_REF], [START_REF] Cha | Watching television over an IP network[END_REF], [START_REF] Vu | Measurement and modeling of a large-scale overlay for multimedia streaming[END_REF]. Consequently, we consider the process global time t ∈ N + as a day discretized in one-minute intervals, {t 1 . . . t 1440 }; 3) In order to be consistent with the literature [START_REF] Yu | Understanding user behavior in large-scale video-on-demand systems[END_REF], [START_REF] Brampton | Characterising user interactivity for sports video-on-demand[END_REF] and as log-normal laws are commonly used to model slow fading phenomenon, we consider that the transition from state X 1 to state X 2 is controlled by a log-normal law.

As an individual user watches longer in certain time-ofthe day, the µ i t (d) and σ i t (d) depend on the persona i, on the kind of content d, on the global time of the process t and on t X1 the time spent in the state X 1 ; 4) As Poisson laws are widely used to model arrival processes, we consider that the transition from state X 2 to state X 1 is controlled by a Poisson law which is consistent with [START_REF] Yu | Understanding user behavior in large-scale video-on-demand systems[END_REF]. As an individual user has habits about his watching time, the parameter λ i t depends on the persona i and on the global time of the process t.

In order to validate the global behavior of a population of users, we simulate three days of different content types with 10000 users dispatched among the six personna. Figure 3.a compares the cumulative distribution function (CDF) of the session duration of our model with the global models proposed by [START_REF] Yu | Understanding user behavior in large-scale video-on-demand systems[END_REF], [START_REF] Brampton | Characterising user interactivity for sports video-on-demand[END_REF], [START_REF] Veloso | A hierarchical characterization of a live streaming media workload[END_REF]. We can notice that our model fits well with the global model of [START_REF] Yu | Understanding user behavior in large-scale video-on-demand systems[END_REF] and has the same shape as the others. Figure 3.b represents the population evolution through the day. We can notice that our model is consistent with the traces presented in [START_REF] Vu | Measurement and modeling of a large-scale overlay for multimedia streaming[END_REF], [START_REF] Liu | Distilling superior peers in largescale P2P streaming systems[END_REF], [START_REF] Veloso | A hierarchical characterization of a live streaming media workload[END_REF]. The sudden changes in the population with our model represents flash crowds which is a common phenomenon in P2P streaming systems. Thus, these results show that our model is consistent with results obtained through measurements on real systems.

B. Results analysis 1) Network setup:

In Section III-B3, we presented and justified the nature of each network variable that can be binomial, multi-nomial or continuous. For each of them, its nature has been determined at the network design stage. Nonetheless, for the Time-of -day one, this determination is not possible. Although it is obvious that it has to be a discrete one, the discretization period cannot be chosen directly. Indeed, the choice of a discretization period has a strong impact on the network performance since it induces a tradeoff between the accuracy of session time estimations and the convergence time of the learning process: a shorter discretization period will induce a better accuracy while increasing the learning time and vice versa.

In order to choose the most appropriate value of the discretization interval, we perform tests with different intervals. We use the same dataset for all networks. All the observations are provided to the network one by one and for each one an inference test is carried out following by a learning step. In the inference test, variable session duration is kept hidden and all the other observations are given to the network as evidences. The network estimates the session duration under the given conditions. Then the complete observation is provided to the network for updating it beliefs. At the end, we compare actual session durations with estimated ones measure: (1) the Root Mean Square Error (RMSE) of the session time estimations once the learning process is completed and (2) the learning time. The latter is determined by measuring the end of the learning process, given by the time at which the variation of RMSE does not go over a given threshold, set at one minute in our case.

The results we obtained are different for the two deployment scenarios. In case of a global deployment, it appears that the large number of sessions due to the considered population induces an extremely short learning time, hardly measurable, while the RMSE only varies between 17.33 and 17.69 minutes making the discretization period invariant regarding the global network performance. By contrast, in the case of a local deployment, the discretization period presents an important impact. Figure 4 the discretization period. Whatever the considered persona, results are consistent since they exhibit similar shapes. The best tradeoff value appears as being 1 hour, giving thus an average learning time of about 35 days and an RMSE of about 7.6 minutes. We use this 1 minute interval in all simulations presented hereafter.

2) Global case: In order to understand the accuracy of the Bayesian network, we depict in Figure 5.a estimated session durations versus the actual ones over a ten days period. For actual sessions comprised between 0 and 40 minutes, one can see that the Bayesian network over-and under-estimates the same amount of sessions. Moreover, estimated sessions uniformly occupy the [0 -40] × [0 -40] square indicating a poor accuracy. Then, for actual sessions comprised between 40 and 100 minutes, the Bayesian network clearly under-estimates sessions. Although under-estimating a session time does not prevent from anticipating the user behavior, it makes it totally inaccurate, thus inducing a strong overhead for any networking mechanism that rely on it. Such results can be explained by the fact that the shuffle of all individual behaviors leads to an average behavior in which it is hardly feasible to accurately distinguish the elements that induce larger or shorter session durations.

3) Local case: We evaluate our network over six types of individual behaviors represented through six personas. To compare the network performance over these personas, we show the averaged RMSE over ten days period for each of them in Figure 5.b. It is obvious from the plots that our network performs consistently over different types of behavior. In the beginning, the error is larger and it is reduced with time through learning. Due to space constraints, in the following we only present simulation results for persona 6 since the RMSE for this persona remains at an average of all the six personas. Obtained results for the five other personas are consistent with those presented here.

Similarly to the global case, we depict in Figure 5.c the estimated time of sessions versus their actual time over the 200 days period for 10 users of persona 6. Here, the estimation is more accurate than in the global case with a slight tendency to average the user behavior through over-estimated short

C. Comparative analysis

In order to evaluate the benefits of the use of a Bayesian network (BN), we compare it with two standard estimators that only rely on the past behavior of the system. They do not integrate any contextual information.

1) Concurrent estimators: The first estimator (EMA) is a statistical technique which estimates an average from a set of values by giving exponentially decreasing weights to older values. As given in (2), ES t is the current session duration, S t-1 is the actual duration of last session, ES t-1 is the length of the last estimated session and α is a weighting factor in [0, 1]. The chosen optimal value of α is 0.7 suggesting to give more weights to the recent session durations.

ES t = α × S t-1 + (1 -α) × ES t-1 (2)
The second estimator (BR) is a probabilistic approach based on a Bayesian inference, which enables the estimation of peers' session duration in the presence or absence of past sessions' history. We assume that the prior probability distribution is a uniform one, avoiding thus any strong assumption on the user behavior. Due to space constraints we cannot add details of estimators any more. For further information, the reader can refer to [START_REF] Ullah | Improving performance of ALM systems with Bayesian estimation of peers dynamics[END_REF].

2) Comparison metrics: We compare the three estimators (EMA, BN and BR) according to the following metrics. Firstly, we measure success which stands for the number of times our estimated session duration is less than or equal to the actual session duration which is important to anticipate the departure of a node. Secondly, we measure the early reaction time (ERT) which is the difference between the actual session duration and estimated duration when the latter is less than the former one. This measurement shows how optimal the anticipation is. Thirdly, we measure the error that is the difference between the actual session duration and estimated session duration whatever the success. In the global case, we give the error for the 20 th simulation day. In the local case, we give RMSE since the error is averaged over all peers. Figure 6 depicts obtained results in both global and local case and table III gives synthetic results.

3) Global case: Success rates given in Table III clearly show that BR outperforms the two other estimators while presenting a slightly larger RMSE. Moreover, Figure 6.a reinforces the analysis we gave in section IV-B2 by showing that errors of both BN and BR are mainly positive, showing an under-estimating tendency. As for EMA, it presents a fairly distributed error. For successful estimations, ERT is far better for BR since most of estimated sessions present a ratio under 0.05, exhibiting a very good accuracy. EMA and BN present similar distribution with a slight advantage for BN whose ERT does not exceed 0.8.

4) Local case:

Success rate provided in Table III provides mitigated results in the local case. Although BR seems to be better than other estimators in terms of success rate, its accuracy given by RMSE is far worse than that of BN. Concerning EMA, it cumulates the weaknesses of both BR and BN producing a weak success and high RMSE. Figure 6 confirms these results by showing that once the learning period is over, BN presents the best RMSE with an excellent accuracy illustrated by its ERT ratio distribution. As a conclusion, in a local case, BN is the most precise estimator. Its average success rate is explained by the fact that the network is not biased towards under-or over-estimation of sessions. In a peer's departure anticipation application it should integrate safety interval by lowering estimated sessions by a given factor. We already tested a 20% factor which makes in this case BN the best estimator according to both success-rate and accuracy.

V. CONCLUSION

In this paper, we presented a Bayesian network modeling a user behavior in a P2P live streaming system. This model gathers in a single formalism the phenomena and causal relationships that have been established through measurement campaigns. More specifically, the information we get consists of components of users behavior, its external impacting factors from the environment and network, and the relationships among these elements. Such a Bayesian model can be used in different applications. The one we focus on is the estimation of peers' session time which aims at anticipating their departure. Simulation results we have shown let us conclude in the following way.

In a system composed of a variety of users having different behaviors, the use of our Bayesian network in a central entity based on-and-providing system-scale estimation is not the best solution since the global behavior of the system is averaged and its specific aspects cannot be handled. A simplest Bayesian estimator based on the sole previous session times outperforms the Bayesian network in terms of success rate while providing a comparable accuracy. By contrast, using a Bayesian network directly into peers which present a consistent and constant behavior is relevant since it is the sole estimator able to estimate the peer behavior very accurately. This result has been confirmed whatever the type of user we considered. Improvements in the success rate for the peer's departure application should be easily obtained through the use of a small safety interval in session time estimations.

Perspectives opened by this work are numerous. Our current work consists in consolidating simulations through extended scenarios (e.g. mix of personas in peers to address the case of multi-viewers). Short term future work will consist in designing, implementing and evaluating a protocol that can be integrated into peers in order to ensure the communication part of our Bayesian network. We are especially looking at existing implementations to get experimental results. As long term future work, we plan to use our model in other application contexts, such as the estimation of the streaming quality or the anticipation of population changes and especially flash crowds that can be useful to provide a constant quality of service to users whatever the environmental context is.

2007 OD:

 2007 Online Duration; SD: Session Duration; CP: Channel Popularity; A/D: Arrival/Departure rates; D/U: Download/Upload traffic

Fig. 1 .

 1 Fig. 1. Components of user behavior and related metrics

Fig. 3 .

 3 Fig. 3. User simulations: (a) CDF of session durations; (b) population evolution

Fig. 4 .

 4 Fig. 4. Learning time (a) and error (b) generated by networks with different discretization intervals. The number after BN-T indicates the discretization interval in minutes and 'P' represents persona.

Fig. 5 .Fig. 6 .

 56 Fig. 5. (a) Actual sessions vs. estimated ones in global case; (b) RMSE averaged over 10 days period for the six personas; (c) Actual sessions vs estimated ones in local case

TABLE I OVERVIEW

 I OF MEASUREMENT STUDIES OVER LIVE STREAMING SYSTEMS user watching a particular channel. They propose a model for the selection of an upstream peer in such a way that a peer with longer elapsed time is preferred over others.Wang et al.

http://code.google.com/p/bnt/