Emilie Bosc

Fabien Racapé

Vincent Jantet

Paul Riou

Muriel Pressigout

Luce Morin

A study of depth/texture bit-rate allocation in Multi-View Video plus Depth compression

Keywords: Multi-view video coding, bit-rate, HEVC, H.264, PSNR, view synthesis

Video plus Depth (MVD) data offer a reliable representation of three dimensional (3D) scenes for 3D Video applications. This is a huge amount of data whose compression is an important challenge for researchers at the current time. Consisting of texture and depth video sequences, the question of the relationship between these two types of data regarding bitrate allocation often raises. This paper questions the required ratio between texture and depth when encoding MVD data. In particular, the paper investigates the elements impacting on the best bit-rate ratio between depth and color: total bit-rate budget, input data features, encoding strategy, assessed view.

Introduction

3D video applications rely on exhaustive 3D representations of real or synthetic scenes. Among the numerous possible representations [START_REF] Smolic | Coding algorithms for 3DTV-a survey[END_REF] are the Multi-View Video plus Depth (MVD) sequences. They consist of multiple texture video sequences coupled with depth video sequences, acquired at different viewpoints of the represented scene. The question of MVD compression is delicate because artifacts in 3D video sequences raise new and unsolved issues related to human vision mechanisms [START_REF] Meesters | Survey of perceptual quality issues in threedimensional television systems[END_REF].

Both 3D video applications, namely Free Viewpoint Video (FVV) and 3D Television (3DTV), require the synthesis of novel viewpoints in order to stimulate human vision system and to simulate parallax motion. This is achieved thanks to Depth Image Based Rendering (DIBR) [START_REF] Fehn | Depth-image-based rendering (DIBR), compression and transmission for a new approach on 3D-TV[END_REF] algorithms that use both texture and depth data. Since the quality of the synthesized views depends on the contribution of both texture and depth data, the issue of bit rate allocation between these two types of data must be addressed when designing an MVD coding framework.

Many approaches proposed a solution to the depth/texture bit-rate allocation issue but the optimal ratio criterion remains open. At the beginnings, the objective quality of the depth map was thought to be comparable to that of the color image. Then by the same token, the color signal having three components and the depth signal having only one component, it seemed appropriate to allocate 25% of the total bit-rate to depth data. Besides, in [START_REF] Fehn | Depth-image-based rendering (DIBR), compression and transmission for a new approach on 3D-TV[END_REF], Fehn et al. show that being a gray-scale signal, the depth video can be compressed more efficiently than the texture video and recommend using less than 20% of the texture bit-rate for video-plus-depth data format. This recommendation is based on the fact that "the per-pixel depth information doesn't contain a lot of high frequency components" [START_REF] Fehn | Depth-image-based rendering (DIBR), compression and transmission for a new approach on 3D-TV[END_REF]. In this approach proposed by the AT-TEST project [START_REF] Fehn | Depth-image-based rendering (DIBR), compression and transmission for a new approach on 3D-TV[END_REF][START_REF] Smolic | Coding algorithms for 3DTV-a survey[END_REF], a base layer encodes a conventional 2-D colour video using MPEG-2 and an advanced layer encodes the depth information. Yet, depth maps define the very structure of the scene. Artifacts occurring in critical areas of the depth map may lead to fatal synthesis errors when generating virtual views. Critical areas are known to be the sharp depth planes edges (i.e. high frequencies) whose encoding is costly and particularly prone to errors. To address this problem other studies [START_REF] Daribo | Motion vector sharing and bit-rate allocation for 3D video-plus-depth coding[END_REF] proposed to consider the distortion of the depth information. In [START_REF] Daribo | Motion vector sharing and bit-rate allocation for 3D video-plus-depth coding[END_REF], Daribo et al. proposed a coding method for the video-plus-depth data through a joint estimation of the MV field for the texture motion information and the depth map sequence. This coding method also includes a bit-rate allocation strategy between the texture and depth map stream based on a rate-distortion criterion. Both the distortion (Mean Squared Error, MSE) of texture and depth data are taken into account in the proposed model of [START_REF] Daribo | Motion vector sharing and bit-rate allocation for 3D video-plus-depth coding[END_REF]. However, a previous study [START_REF] Bosc | Focus on visual rendering quality through content-based depth map coding[END_REF] also shown that the distortion of depth maps in terms of MSE may not be appropriate to predict the quality of the resulting synthesized views. In addition, since the depth map will not actually be observed by the users of an 3D Video application, it seems more pertinent to consider the quality of the synthesized views, that are more likely to be observed. Thus, most of the up-to-date bit-rate allocation strategies now rely on the quality of the synthesized views. This is motivated by the realization of the impact of depth map compression on visual quality of the synthesized views ([6], [START_REF] Vetro | Towards a 3D video format for auto-stereoscopic displays[END_REF]). Different bit-rate allocation strategies have been proposed in the literature. Some of them opt for the fixed-ratio bit-allocation scheme, like Martinian et al. [START_REF] Martinian | Extensions of h. 264/AVC for multiview video compression[END_REF] who consider using only 5-10% of the total bit-rate for encoding depth data with H.264/AVC, based on the observation that it "produced acceptable view synthesis performance".

Other strategies [START_REF] Ekmekcioglu | Bit-rate adaptive down-sampling for the coding of multi-view video with depth information[END_REF][START_REF] Morvan | Joint depth/texture bit-allocation for multi-view video compression[END_REF][START_REF] Cheung | On dependent bit allocation for multiview image coding with depth-image-based rendering[END_REF] rely on a global optimization equation solver based on the objective image quality of the rendered intermediate view. In their experiments [START_REF] Ekmekcioglu | Bit-rate adaptive down-sampling for the coding of multi-view video with depth information[END_REF], Ekmekcioglu et al. consider a given total budget where 15% is assigned to depth data. The authors noticed that their proposed bitallocation strategy based on the synthesized view quality, outperforms the conventional constant-ratio allocation strategy. Similarly, in [START_REF] Morvan | Joint depth/texture bit-allocation for multi-view video compression[END_REF], the authors proposed an efficient joint texture/depth rate allocation method based on a view synthesis distortion model, for the compression of MVD data. According to the bandwidth constraints, the method delivers the best quantization parameters combination for depth/texture sets in order to maximize the quality of the rendered synthesized view in terms of MSE (Mean Squared Error) (with respect to the original captured view). The proposed model finds the optimal ratio between depth bit-rate and texture bit-rate. However, the optimization depends on the target virtual viewpoint. In [START_REF] Cheung | On dependent bit allocation for multiview image coding with depth-image-based rendering[END_REF], the authors proposed a bit-rate allocation strategy between texture and depth maps of multi-view images based on a model that minimizes the distortion of the synthesized views. A cubic distortion model based on basic DIBR properties drives the optimal selection of coded views and quantization levels for corresponding texture and depth maps. Cheung et al. ([11]) observe improvements by up to 1.5 dB with this proposed model, compared to constant-ratio allocation strategy. The 3D-HTM coding software under standardization of MPEG includes a depth coding tool called View Synthesis Optimization (VSO) [START_REF] Wegner | Test model under consideration for hevc based 3d video coding v3.0[END_REF] that is meant to improve depth bit-rate allocation based on the quality of a synthesized view. This tool integrates a distortion term calculated based on the quality of texture synthesized using decoded depth. This previous work on bit-rate allocation between texture and depth data highlights the fact the challenges raised by this issue. These challenges are not that trivial since they seem to involve many questions:

the importance of the preservation of depth sharp edges (discontinuities) -the influence of the target intermediate synthesized viewpoint used for the optimization process other questions such as the bit-rate allocation within one frame, or between frames Based on our previous studies [START_REF] Bosc | Bit-rate allocation for multi-view video plus depth[END_REF][START_REF] Bosc | Bit-rate allocation between texture and depth: influence of data sequence characteristics[END_REF], we rely on the assumption that there exists an optimal ratio between texture and depth data. The experiments presented in this paper investigate the factors impacting on the optimal ratio between texture and depth data in MVD compression. In particular, we question the role of 1) the total bit-rate budget, 2) the coding method, 3) the input data features and 4) the location of the assessed view with respect to the decoded reference views. This paper aims at determining the impact of these four aspects in the bit-rate allocation between texture and depth data, in the con-text of MVD data compression in FVV applications by using objective metrics.

The study includes the compression of MVD data sequences at different bit-rates in order to determine the best bit-rate distribution between depth and texture, when based on Peak Signal to Noise Ratio (PSNR) measures of the synthesized view. In most of the studies, the use of this objective metric is justified by its simplicity and mathematical easiness to deal with such purposes. Thus, we also investigate the bit-rate allocation issue when based on such a metric.

The paper is organized as follows: Section 2 presents the experimental protocol basis. The next sections present the results of our investigations depending on the studied element assumed to impact on the bit-rate between texture and depth data: Section 3 addresses the analysis of the coding constraints; Section 4 addresses the influence of the MVD sequences features and of the assessed viewpoint. Finally Section 5 concludes the paper.

Global experimental conditions

The following experiments aim at investigating the factors impacting the best ratio between texture and depth data, when encoding MVD data, in a FVV application context. For this reason, the experiments are both based on the same global experimental conditions, as depicted in Fig. 1. Texture and depth data from MVD sequences are processed by an encoding method. The reconstructed views are used for generating an intermediate viewpoint thanks to the View Synthesis Reference Software (VSRS) version 3.5, provided by MPEG. The synthesized viewpoint is then evaluated relying on the PSNR with respect to the original acquired view. Depending on the studied criterion (coding method, data features, etc...), some parameters slightly differ from the global experimental conditions. The details are described in the concerned sections. In the following, we present the results of our investigations regarding the factors influencing the best ratio between texture and depth data.

Analysis of coding constraints

In this section, the effects of the encoding method constraints are studied. For this purpose, following the basis scheme described in Section 2, H.264/MVC reference software, JMVM 8.0 (Joint Multiview Video Model) [START_REF]Jmvm software[END_REF] is used to encode three views, as a realistic simulation of a 3D-TV use. To vary the bitrate ratio and the total bit-rate, the quantization parameter QP varies from 20 to 44 for both depth and texture coding. The central view is used to predict the two other views in the case of H.264/MVC. Then, from the decompressed views, we computed an intermediate view between the central view and the right one, by using the reference software: VSRS, version 3.5, provided by

MPEG.

In this case study, "MVC codec" in Figure 1 thus refers to H.264/MVC. We used two different types of sequences to answer our question: Ballet from Microsoft Research, and Book Arrival from Fraunhoffer HHI (1024 × 768). This last sequence is a 3DV test material in MPEG.

The considered views are 2, 4 and 6 for Ballet, and 6, 8 and 10 for Book Arrival. Viewpoint 3 is generated from decoded viewpoints 2 and 4 in the case of Ballet. Viewpoint 9 is generated from decoded viewpoints 8 and 10 in the case of Ballet. For each couple (QP texture , QP depth ), the average PSNR score of the synthesized sequence is evaluated, compared to the original acquired view. The obtained results are discussed in the following in an organized manner, according to the investigated factors.

QP

Visual analysis

Here, we address the visual image quality of the rendered views synthesized from the decompressed data. Fig. 2 gives selected snapshots of the resulting synthesized views when using H.264-decompressed data with various texture/depth ratios. Figures 2(b), 2(f) and 2(j) show that allocating less than 10% of the total bit-rate to depth data induces important damages along the edges. The location of the depth map discontinuities is deeply compromised which leads to errors in the synthesized view. PSNR scores fall down because of the numerous errors along the contours of objects.

Figures 2(d), 2(h) and 2(l) suggest that affecting more than 80% of the total bit-rate to depth data preserves the edges of some objects but texture information is lost because of the coarse quantization.

Affecting between 40% and 60% of the total bit-rate to depth data seems to be a good trade-off for the tested sequences, as it can be observed in Figure 2(c), 2(g) and 2(k). PSNR scores and visual quality are both improved compared with the two other presented cases. The depth maps are accurate enough to ensure correct projections and decompressed texture images are good enough to avoid drastic artifacts.

The obtained results showed that the best quality of reconstruction by using VSRS may require to affect between 40% and 60% of the total bit-rate to depth data, depending on the available MVD data.

Dependence on the total bit-rate

Fig. 4 presents the interpolated rate-distortion curves of synthesized views for Ballet sequence and Book Arrival sequences using H264/MVC. The goal of these figures is to visualize the allocated depth ratio obtaining the highest image quality in terms of PSNR. For this reason, these figures plot the PSNR values on the ordinate and the ratio allocated to depth, in percentage, with respect to the total bit-rate (texture+depth), on the abscissa. The obtained synthesized views PSNR scores have been grouped into bit-rate intervals. One color corresponds to one total bit-rate interval (texture+depth), in the figures. In the figures, points correspond to the actual measured scores. Dots with same color belong to same bit-rate range interval. The different curves correspond to interpolation of the measured points for each range of bit-rate.

Our results are consistent with [START_REF] Liu | Joint video/depth rate allocation for 3D video coding based on view synthesis distortion model[END_REF]: although the authors do not state clearly the appropriate ratio for those two sequences, their rate/distortion curves show that, for example, the bit-rate pair (962kbps for texture, 647kbps for depth), i.e. a percentage of 40% for depth, gives better synthesis quality (in terms of PSNR) for Book Arrival. The synthesis conditions are similar to our experiments. On the other hand, in [START_REF] Fehn | Depth-image-based rendering (DIBR), compression and transmission for a new approach on 3D-TV[END_REF], the synthesis conditions involve one single video-plus-depth data: in this case, a very little continuum is supported around the available original view. Since synthesis distortion increases with the distance of the virtual viewpoint, this explains the significant difference with our results.

We observe that for a given sequence, no matter the bit-rate, the ratio that provides the best quality seems relatively constant: around 60% for Ballet, and around 40% for Book Arrival. However, a close observation to the curves shows that this bit-rate ratio lies in a narrow interval of values that depends on the total bit-rate. The value of the inflection points slightly decreases when the total bit-rate decreases.

Dependence on the coding method

The previous subsections observations (3.2 and 3.1) are related to H.264/MVC encoding. Using a different encoding framework may lead to a different ratio for depth. For this reason, our experiment includes another compression method (HEVC), in the same test conditions. This subsection presents the results. As in the previous experiment using H.264/MVC, we observe the visual image quality of the rendered views, from the decompressed data, as depicted in Fig. 3. The analysis of Fig. 2 and 3 leads to interesting observations regarding the influence of the encoding method on the bit-rate ratio between texture and depth data.

For similar ratios, the visual quality of the synthesized views is different depending on the used encoding method: in the case of H.264/MVC encoding, Figures 2(c), 2(g) and 2(k) show a correct visual quality when allocating around 60% and 40% (for Ballet and Book Arrival respectively to depth data. However, in the case of HEVC, this compromise is not appropriate since Figures 3(c), 3(g) and 3(k) show inaccurately rendered edges. The observation of Figure 3 suggests that the optimal depth ratio is in a range from 3% to 60% for Ballet and around 6% for Book Arrival, with HEVC. These comments suggest that the encoding method impacts on the optimal ratio between texture and depth data considering visual image quality observations. An important difference between H.264 and HEVC lies in the replacement of H.264 macroblocks by flexible coding scheme based on coding units of variable size (from 64×64 to 8×8 blocks) that can be hierarchically subdivided (through a quadtree subdivision). In addition, as previously studied in [START_REF] Schwarz | Comparison of the coding efficiency of video coding standards #x2013; including high efficiency video coding (HEVC)[END_REF] the gain also comes from changes as the improvement of intra prediction modes and directions and the use of asymmetric partitions for inter prediction. The results thus suggest that HEVC representation is more adpated for depth map compression than H.264, considering the visual observations of the synthesized views respectively: despite a lower rate allocated to depth data, essential depth information is preserved to enhance the quality of the synthesized view in terms of PSNR, in these experiments. As expected, we also note that the visual artefacts in the presented synthesized views differ depending on the coding strategy. Fig. 5 depicts the interpolated rate-distortion curves of synthesized views for Ballet sequence and Book Arrival sequences using HEVC. In average, with HEVC, the percentage of bit-rate allocated to depth data leading to the maximum PSNR is 27.5% for Ballet and 12.2% for Book Arrival. In the case of HEVC, the obtained curves show that the optimal ratio depends on the total bit-rate budget, while remaining in a narrow range: the inflection point values of the curves decreases when the total bit-rate budget decreases. The obtained ranges are [21%-34%] for Ballet and [9%-15%] for Book Arrival. This suggests that the lower the bit-rate budget, the less depth data is required, which implies a necessary return to 2D at very low bit rates.

Analysis of data characteristics

In this section, the effects of the influence of the MVD sequences features and of the assessed synthesized view are studied. In particular, we assume that the video content, the complexity of depth and the camera settings are related to the bit allocation between depth and texture. The following experiments are in line with this concern. The basis experimental scheme described in 2 now includes H.264/MVC codec only with 11 sequences. For each sequence, we encoded different frames. Then we generated the virtual viewpoints with various baseline distances between the reference viewpoints. Table 1 gives the summary of the used material. Table 2 summarizes the tested sequences features. This table is partly based on the analysis provided in [START_REF] Smolic | Report on generation of stereo video data base[END_REF]. The encodings follow the basis scheme protocol described in 2: left and right views (textures and depth maps) are encoded through MVC reference software (JMVM 8.0). Based on the same protocol, the optimal ratio between depth and texture are calculated, with PSNR of an intermediate synthesized viewpoint as an indicator of distortion.

Table 3 summarizes these results. The obtained bit-rate ratios vary from 16% to 52% depending on the test sequence. The analysis of this table, compared to Table 2 does not allow a clear conclusion of the influence of the sequences characterisics on the bit-rate ratio. For this reason, we propose a further study including new axes to be investigated. They are the features which differ from one content to another: depth map accuracy, depth structure complexity, baseline distance between the reference cameras, features of discovered areas. These aspects are addressed by three analyses in the following: depth maps entropy, baseline distance between the reference cameras, high contrast between background and foreground around the discovered areas.

Depth maps entropy and texture images entropy

We assume that the ratio which rules the optimal synthesized views in terms of PSNR, is related to the amount of information contained in the original data. In other words, the entropy of depth against the entropy of texture is expected to influence the optimal allocation between depth and texture. Let e d be the average entropy of the encoded depth maps, for a given content. Let e t be the average entropy of the encoded texture frames, for the same content. For each tested content, we computed the following ratio:

R e = e d e d + e t (1)
Fig. 6 plots the computed mean R e of per sequence against the "optimal" percentage of bit-rate allocated to depth data according to our previous experimental protocol. There is relationship between R e and the "optimal" percentage of bit-rate allocated to depth data. The correlation coefficient between R e and the "optimal" percentage of bit-rate allocated to depth data was calculated through a Matlab-made Pearson coefficient implementation and it reached 76.95%. These results are understandable because a high entropy value for the depth implies a highly detailed depth structure. If the level of details Table 3 Ratio between texture and depth information allowing the minimal distortion in terms of PSNR.

of depth is higher than that of the texture, the synthesis quality mostly relies on the accuracy of the depth map.

In conclusion, these results suggest that an preliminary analysis texture and depth entropies can be used as an indicator for automatic bit-rate allocation between these two types of data.

High contrast background/foreground areas

We assume that errors occurring after the synthesis process are not only more noticeable when the contrast between background objects and foreground objects is high, but also more penalized by signal-based objective metrics. To investigate this assumption, we consider the strong depth discontinuities (highlighted by an edge detection algorithm) and evaluate the standard deviation of Fig. 6 Ratio of entropy between texture and depth data against optimal percentage of bit-rate allocated to depth data according to our previous experimental protocol, in terms of PSNR the texture image around these discontinuities. Let ∆D be the gradient image of depth map D. Any pixel located at coordinates (x, y) is noted p and we consider the set of pixels Γ such as:

Γ = {p = (x, y)|∆D(x, y) > 0} (2)
The investigated feature, denoted C, that expresses the contrast between foreground and background areas around the strong depth discontinuities, is computed as:

C = 1 |Γ | |Γ | p=1 σ(T (p)), p ∈ Γ (3)
where |Γ | is the cardinality of Γ and σ(T (p)) is the standard deviation of 5 × 5 window centered on pixel p in texture view T . For each piece of the tested material, we compute for left and right views and we consider the mean of these two coefficients. Unexpectedly, the results show that the higher the contrast, the less bitrate allocated to depth: two main point clouds are distinguishable. The point cloud corresponding to 40-55% of bit-rate allocated to depth belongs to the two toed-in camera configuration sequences. The second cloud corresponds to the parallel camera configuration sequences. So, our assumption is that despite the high contrast around objects contours, the camera configuration (and thus the distance to the virtual view) might reduce the impact of the synthesis distortions. Fig. 7 Influence of high contrast background/foreground areas: Average of computed standard deviation scores around gradient pixels of depth maps against optimal percentage of bit-rate allocated to depth data according to our previous experimental protocol, in terms of PSNR

Baseline distance between cameras

This aspect is closely related to the distance of the assessed synthesized viewpoint to the reference views. We assume that there is a relationship between the structure of the scene depth and the "optimal" percentage of bit-rate allocated to depth data in MVC. According to the depth structure complexity and the baseline distance between the reference cameras, discovered areas in the novel virtual viewpoints are relatively large and difficult to fill-in by the synthesis process. Since the discovered areas are filled in with in-painting methods whose texture estimation quality differs according the used strategy, these areas are prone to perceptible synthesis errors. We aim at evaluating the influence of the discovered areas on the "optimal" percentage of bit-rate allocated to depth data. Let V r and V l be the original right and left view, respectively and D r and D l be the original right and left depth maps respectively. Let V r→v the projection of V r into the target virtual viewpoint, and V l→v the projection of V l into the target virtual viewpoint. V r→v and V l→v contain undetermined areas that correspond to the discovered areas. V r→v and V l→v are used to create logical masks M r→v and M l→v defined as:

M r→v (x, y) = 0 , if V r→v (x, y) is determined 1 , if V r→v (x, y) is not determined (4) M l→v (x, y) = 0 , if V l→v (x, y) is determined 1 , if V l→v (x, y) is not determined (5)
Then we consider the importance I of the discovered areas according to its depth by applying the masks on the respective depth maps as follows:

I = 1 2 × M × N N x=1 M y=1 D r (x, y) × M r→v (x, y) + D l (x, y) × M l→v (x, y) (6)
where N and M are the width and height of the original image. The score I is computed for each piece of the tested material. In each case, the target virtual point is as indicated in Table 1. The results are plotted in Fig. 8. This figure shows a linear relation between the computed importance score I and the "optimal" percentage of bit-rate allocated to depth data. Although the results suggest a relationship between the discovered areas and the "optimal ratio", the virtual viewpoint is not always known at the encoder side. This limits the use of such an indicator for automatic bit-rate control strategies.

Conclusion

This paper aimed at determining the elements impacting on the best ratio between texture and depth data in MVD compression. Different experiments following the same basis explored several assumed factors. The experiments consisted in encoding both texture and depth data with a given compression scheme, varying the ratio between texture and depth information and analyzing the quality of the rendered virtual view. A first study consisted in investigating the influence of the encoding method on the best ratio between texture and depth data. The test codecs were H.264/MVC coder in the first case of use, and HEVC in the second case of use. Depending on the encoding method, the attributed depth ratio allowing the best synthesizeed image quality in terms of PSNR was different. This suggests that bit-rate savings can be achieved if the encoding method is adapted to depth features, allowing better synthesized views quality. The experiment also showed that the ratio allocated to depth should decrease when the total bit-rate budget decreases. Another aspect investigated in this paper concerns the impact of the input data features. A relevant remark regards the observation that the optimal ratio is significantly different depending on the sequence. The factors related to the sequences have been studied. The assumed factors influencing the best trade-off for bit-rate allocation between texture and depth data were the depth map entropy, its complexity coupled with the camera baseline distance, and the contrast of neighboring background/foreground pixel areas. The experiments revealed the existence of their impact on the best trade-off for bit-rate allocation between texture and depth data.

Despite its limitations regarding the used quality assessment tools, this study raises new topics for future work: the influence of the synthesis method on the best ratio; the investigation of the reasons why the best quality of reconstruction by using VSRS requires different depth/texture ratios depending on the content; the consideration of depth maps features for the design of depth-adapted efficient compression methods for bit-rate savings. Such investigations could be useful for the implementation of an automatic bit-rate allocation method in coding methods. In addition, this work could be extend by considering the subjective quality of the synthesized views.

Fig. 1

 1 Fig. 1 Global experimental conditions.

Fig. 2 Fig. 3 Fig. 4

 234 Fig. 2 Synthesized images from H.264 encoded MVD data, with different bit-rate ratios between texture and depth. a), b) ,c) and d) refer to the sequence Ballet. e), f), g), h), i), j) k) anf l) refer to the sequence Bokk Arrival.

Fig. 5

 5 Fig. 5 Interpolated rate-distortion curves of synthesized views (from HEVC encoded MVD data). PSNR (dB) of synthesized views as a function of rate allocated to depth in percentage of total rate.

Fig. 8

 8 Fig.8Importance of discovered area against optimal percentage of bit-rate allocated to depth data according to our previous experimental protocol, in terms of PSNR

Table 1

 1 Test material.

	Sequence	Characteristics	Depth	Camera spacing
	Name			structure
				complex-
				ity
	Ballet		natural scene, high detail	high	varying, toed-in con-
					figuration
	Balloons		natural scene, moving cameras, high detail	high	stereo distance, par-
					allel configuration
	Book	Ar-	natural scene, high detail	high	stereo distance, par-
	rival				allel configuration
	Breakdancers	natural scene, high detail	high	varying, toed-in con-
					figuration
	Cafe		natural scene, medium detail	medium	stereo distance, par-
					allel configuration
	Champagne	natural scene, high detail	medium	stereo distance, par-
					allel configuration
	Kendo		natural scene, moving cameras, high detail	high	stereo distance, par-
					allel configuration
	Lovebirds1	natural scene, natural light, high detail	medium	stereo distance, par-
					allel configuration
	Mobile		animation, high detail	simple	stereo distance, par-
					allel configuration
	Newspaper	natural scene, high detail	medium	stereo distance, par-
					allel configuration
	Pantomime	natural scene, medium detail	high	stereo distance, par-
					allel configuration

Table 2

 2 Features of the tested sequences.

	Sequence Name	Ratio Depth/Texture in %
	Ballet	51.6
	Balloons	28.21
	Book Arrival	31.97
	Breakdancers	46.27
	Cafe	38.38
	Champagne	52.11
	Kendo	27.6
	Lovebirds	23.58
	Mobile	16.57
	Newspaper	30.97
	Pantomime	19.48


Maximiliano Geier

Lucas Nussbaum

Martin Quinson

On the Convergence of Experimental Methodologies for Distributed Systems: Where do we stand?

Understanding distributed systems is a complex task. There are many subsystems involved, such as network equipment, disk and CPU, which effect behavior. In order to analyze this kind of applications, different approaches have been proposed: simulation, emulation and experimentation. Each paradigm has evolved independently, providing their own set of tools and methodologies.

This paper explores how these tools and methodologies can be combined in practice. Given a simple question on a particular system, we explore how different experimental frameworks can be combined in practice. We use a representative framework for each methodology: Simgrid for simulation, Distem for emulation and Grid'5000 for experimentation. Our experiments are formally described using the workflow logic provided by the XP Flow tool.

Our long term goal is to foster a coherent methodological framework for the study of distributed systems. The contributions of this article to that end are the following: we identify a set of pitfalls in each paradigm that experimenters may encounter regarding models, platform descriptions and others. We propose a set of general guidelines to avoid these pitfalls. We show these guidelines may lead to accurate simulation results. Finally, we provide some insight to framework developers in order to improve the tools and thus facilitate this convergence.

I. INTRODUCTION

Distributed systems are pervasive in many areas of computing, ranging from scientific applications to content distribution systems. Many of these systems, such as peer-topeer networks, comprise millions of nodes, distributed all over the world. These are generally highly heterogeneous systems, in which many different subsystems and technologies interact simultaneously using common protocols. It has been a running effort since decades to assess the properties of these systems, such as reliability, resilience, performance or security. Most often, researchers rely for that on experimentation: they analyze the behavior by running the system under a particular scenario and capturing output data that could be of interest.

Experimental work in distributed systems could be categorized in three different paradigms [START_REF] Gustedt | Experimental Methodologies for Large-Scale Systems: a Survey[END_REF], [START_REF] Beaumont | Towards Scalable, Accurate, and Usable Simulations of Distributed Applications and Systems[END_REF]:

• Simulation: a prototype of the application is executed on top of a model of the environment. This approach enables the researcher to analyze questions about the system without having access to the actual environment or the actual application. The reliability of the results depend on the validity of the underlying models.

• Emulation: the actual application is executed on a simulated environment. The environment can be controlled through classical virtualization techniques, or a controlled artificial load can be injected onto real resources such as network links and CPUs according to the given experimental scenario.

• Experimentation: the actual application is executed on a real environment. Although it might be desirable, it is not always possible to do this, as it requires access to an instrumented platform that matches the real environment. This might be prohibitively expensive or not available. Moreover, testing on different scenarios under these circumstances can turn into an incredibly complex task. Each paradigm offers its own set of tools and methodologies. Most of these tools have evolved independently from each other. It is then difficult to combine them for an augmented analysis.

This paper constitutes a status report regarding the emergence of a coherent experimental framework combining these different approaches. We opted for a practical evaluation where we conduct an experimental analysis leveraging these methodologies, and report on the difficulties encountered. To that extend, we analyze a file broadcasting application that is widely used in a cluster setting. Our focus remains however on the methodological aspect of this study, not on the results of this study per se.

This paper is organized as follows: Section II first introduces the related work while Section III describes the proposed methodology. Section IV presents several experimental traps arising in the different methodological paradigms and hints on how to avoid these traps to get satisfying results. Section V discusses several considerations that tool designers must address to facilitate the methodologies convergence. Finally, Section VI concludes this paper.

II. RELATED WORK

Several works combine differing experimental methodologies in a coherent framework toward augmented analysis. The Emulab-Planetlab portal [START_REF] Webb | Implementing the emulab-planetlab portal: Experience and lessons learned[END_REF] allows to use the interface of the Emulab [START_REF] White | An integrated experimental environment for distributed systems and networks[END_REF] emulator to access the Planetlab [START_REF] Chun | Planetlab: an overlay testbed for broad-coverage services[END_REF] experimental platform, clearly bridging the gap between these instruments. EMUSIM [START_REF] Calheiros | Emusim: an integrated emulation and simulation environment for modeling, evaluation, and validation of performance of cloud computing applications[END_REF] is another interesting attempt in this regard. It integrates emulation and simulation environments in the domain of cloud computing applications, providing a framework for increased understanding of this type of systems. Similarly, Netbed [START_REF] White | An integrated experimental environment for distributed systems and networks[END_REF] is a platform based on Emulab that mixes emulation with simulation to build homogeneous networks using heterogeneous resources.

To the best of our knowledge, there is however not much previous work that compares these methodologies in practice.

The work in [START_REF] Spring | Using planetlab for network research: myths, realities, and best practices[END_REF] analyzes "myths and beliefs" about Planetlab as it stood in 2006. It concentrates on debunking assumptions about the platform that were either never correct or simply no longer true at that point. Moreover, it is clear with regard to stating real limitations of the platform, so as to help users decide if it is reasonable to use it for their objectives. This approach is different to our work in the fact that its conclusions are a set of best practices for users of a single platform. It does not analyze how Planetlab plays with other platforms and does not try to construct an unified methodology for the analysis of distributed systems.

III. METHODOLOGY

A. Selected Tools

Although certainly interesting, including in this study every existing experimental tool or framework would be a daunting task. In this work, we preferred focusing on one representative framework per methodological paradigm and focus on the methodological aspects. Additional conclusions would have been reached with other tools, but we believe that this does not reduce the impact of our conclusions.

Concerning simulation, we used SimGrid [START_REF] Casanova | Simgrid: a generic framework for large-scale distributed experiments[END_REF]. This is an ever growing simulation framework, with more than 10 years of development and over 100 papers based on its results. It features sound and scalable models of distributed systems. Direct experiments were run on Grid'5000 [START_REF] Cappello | Grid'5000: A large scale and highly reconfigurable grid experimental testbed[END_REF]. As of May 2013, this platform consists of 11 sites all over France and Luxembourg, with several clusters on each site, connected by high speed links. This scientific instrument is dedicated to the live study of distributed systems. To this end, it allows full deployment of custom operating system on the reserved nodes and the reservation of isolated network portions. We chose the Distem [START_REF] Sarzyniec | Design and Evaluation of a Virtual Experimental Environment for Distributed Systems[END_REF] emulator. It is easily deployed on Grid'5000 nodes, and enables the experimenter to simulate network topologies. Nodes are deployed as Linux containers, meaning that many virtual nodes could be instantiated in a single physical node, with a small resource overhead. The platform is simulated by slowing down physical links artificially (network or memory bus).

B. Driving Question

The driver of any experimental analysis is usually an interesting question that researchers are trying to answer. As a consequence, the methodology is often an afterthought, and the contribution quality comes from the results found.

This paper is rather different in that regard. As we focus on the methodology itself, we base our analysis on a simple question. It was not chosen to be innovative but instead to be simple enough to not distract the study while being complex enough to mandate non-trivial experiments. This driving question is to evaluate the relative advantages of different chain propagation algorithms for file broadcasting in a cluster setting.

One such algorithm is already implemented in the Kastafior tool of the Kadeploy suite [START_REF] Jeanvoine | Kadeploy3: Efficient and Scalable Operating System Provisioning[END_REF]. It is used in production on Grid'5000 to deploy user OS images to each node.

It works as follows: an efficient communication chain is built to connect all participating nodes to their network neighbor when possible and to reduce the transfer interactions on the chain. This chain can be built semi-automatically since the network topology is well documented on this instrument. The file is then split in fixed size chunks, that are sent sequentially from the broadcaster to the first node of the chain. As soon as the first chunk is received by the first node, it is forwarded to the next one in the chain, concurrently to the reception of the second chunk. This algorithm is intended to minimize the time to send the whole file to all participating nodes by overlapping as much communication as possible while avoiding network interactions. In taking advantage of the network topology, this algorithm can be used to deploy files very efficiently, without using multicast or other advanced tools which introduce a huge administration overhead.

Kastafior was never analyzed thoroughly, but it performs well in practice for the users of the Grid'5000 infrastructure.

IV. OBSERVED TRAPS

In this section, we show some of the problems that an experimenter might run into when analyzing a distributed system. We encountered these issues while analyzing our own implementation of the Kastafior algorithm in the context of broadcasting files in a single Grid'5000 site. This implementation, called chainsend, has been written entirely in C.

The metric of interest in our study is the bandwidth per node, i.e. the average of all bandwidths. It is measured in every node as the amount of time to receive the complete file divided by the file size. This value is then averaged over all nodes to get a single value. This metric has been produced by measuring time in every node. In direct experimentation in Grid'5000 and in Distem we use the local clock of each node. In the case of Simgrid, we use the simulated time provided by the framework. We show this metric as a function of the number of nodes, to indicate the progression. The data points have also been interpolated using splines to ease visualization.

Our experiments leverage up to 100 nodes of the Nancy site of Grid'5000 (clusters griffon and graphene), up to 10 virtual nodes in Distem, and 92 nodes in Simgrid (griffon platform file). The file size used is 1 GiB.

A. Difficulties getting the platform right

The platform in which the experiment runs tells us about network size and characteristics, how nodes are connected to each other and all the information that is required to reproduce a similar setup. However, for non-trivial experiment sizes, it could become increasingly difficult to ensure that it represents exactly what the user wanted.

In the case of Simgrid, it is important to understand the platform syntax correctly. The description is given in the form of an XML file, but it is tedious to write explicitly. In order to simplify it, some syntax shortcuts have been put in place (e.g. the cluster tag) which alleviate platform writing significantly, but could introduce errors if the user does not understand what they and their attributes mean exactly.

Finally, as said before, another important issue is accuracy: it is possible that the description is correct in terms of what the user wanted to say, but wrong with respect to the reference platform. This problem is significant as it could induce false conclusions from the experiments. For example, in a bandwidth-limited experiment, if the platform description is wrong with respect to this metric, it is obviously not possible to reproduce a result in simulation even though the underlying model may be correct otherwise. Latency parameters also effect metrics in unexpected ways (e.g. delaying communication and thus reducing overall bandwidth usage) and it may not be easy to identify this problem in the platform description.

Distem also shows similar problems: it is not possible to map Simgrid platform files to Distem platform descriptions yet. This is a known issue, and even though it is able to load simple v2 Simgrid platform files correctly, most advanced features are not working yet. Moreover, there is also the nontrivial problem of mapping a virtual platform on a set of physical nodes. For example, using up several physical nodes imposes limitations on inter-node bandwidth and communication time that have to be taken into account when designing experiments. Lastly, Distem has some limitations on what kind of routing it can emulate, thus rendering impossible, for instance, to experiment with redundantly connected nodes.

B. Missing hardware models in simulation

Both simulation and emulation abstract away some details which can be found in the real platform. These abstractions could lead to wrong or inaccurate results if they are not correctly accounted for. It is important to understand them to design good experiments.

Simgrid's MSG API, for instance, forces some restrictions on what kind of software can be accurately simulated. It should be noted that, as a result of this, applications written using this API cannot be implemented as if they were actual network applications.

Simgrid simulates only a network and a CPU, the latter only given that appropriate CPU parameters were input to the model. This implies that, for example, it doesn't simulate disk activity, therefore a disk-bound application would not produce the expected results in simulation.

In Figure 1, we show a comparison of the bandwidth per node in Grid'5000 by measuring the transfer time at two different points: as soon as the file has been transferred (before the fsync system call is issued), and after the data has been successfully written to disk (after fsync). As we can see, chainsend is a disk-bound application, and as such we cannot make a fair comparison against the Simgrid implementation unless we take the disk out of the picture. Even if we

• •••• • • • • • • • • • • • • • • •• •• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• • • •• • • • • • • • • •• • ••••••• • •••••• •• • • •• • •••• • •• 0
• • • • • • • •• •• •••••••• • ••• • • ••• • •• ••• •• ••••••• • ••• •••• • • ••• ••••••••••• •••••••••••••••••• •• • •••••• •••••

Before fsync After fsync

Figure 1. Bandwidth per node in Grid'5000 before fsync and after fsync. measure time after fsync, there is still disk activity going on that could affect the results. In order to mitigate this, all the following runs in Grid'5000 write the file to the special device /dev/null. This device discards data without writing anything to disk. We show the results of doing so in Figure 2.

• ••••••••••••••••••••••••••••••••••••••••• • •••••••••••••••• • ••••• • ••••••• • ••• • • • • • •• • •• • • •••• • • ••••
As we can see, the results are much more stable now. The reason behind this is that there is no interference of the I/O cache, as writes are properly discarded. This scenario is more realistic compared to what is actually simulated by Simgrid.

C. Bad assumptions behind network models

Simgrid provides a network model for the simulation. This model makes some assumptions that have to be taken into account to make good use of the platform. They could be categorized as follows:

• Transport protocol: MSG assumes that all its communications are handled using TCP, ruling out every other transport protocol.

• Connection flow: the mailbox abstraction in MSG assumes that every task takes up its own connection, meaning that for each send, it simulates the time it takes to open a socket, do the three-way handshake, send data, receive its respective ACKs, and finally close it. This also implies that it can't simulate a continuous stream of data, unless it is sent as a single task.

• Connection flow arguments: there are two parameters in the default network model (LV08 [START_REF] Velho | Accuracy study and improvement of network simulation in the simgrid framework[END_REF]) that can be adjusted to change the behavior explained above, bandwidth_factor and latency_factor. The first one effects what percentage of the total bandwidth can actually be consumed by the connection, while the latter is a latency penalty factor, that effects how much time it takes to go from "slow start" to a "steady state". If this factor is closer to 1.0, the "slow start" effect is less noticeable. This factor could be used to simulate a stream of continuous data more accurately, but it is necessary to adjust it beforehand (i.e. it is not dynamically adjustable). To highlight the effects of the connection flow parameters in Simgrid, we show bandwidth per node in Grid'5000 compared against Simgrid in Figure 3, using the default network model and connection flow arguments. As we can see, performance in Simgrid is roughly half of that in the real platform. This can be explained by what we have said before: in MSG, Simgrid simulates a complete connection for each send/receive. This means that for each file fragment being sent, there is a threeway handshake, data being sent on the network, and finally the connection is closed. At the same time, the congestion control algorithm in TCP takes place. This results in slow start taking place for every chunk of the file being sent. This is unrealistic compared to the real application, as the whole transfer happens during a single TCP connection.

If we change the default network model to CM02, which is a much simpler model that doesn't simulate accurately all the TCP congestion control algorithms, we obtain the results that are shown in Figure 4.

As we can see, the results for Simgrid are very similar to those of Grid'5000 now. This simpler model lets us fake the fact that Simgrid doesn't correctly account for single streams of data over multiple messages. In this case, it works as if there was no slow start at all, meaning that the stream is continuously in "steady state". This is very similar, although slightly overfitting, to the actual situation.

Moreover, there is an adjustable parameter, SG_TCP_CTE_GAMMA, which modifies how Simgrid takes into account the TCP congestion window when it updates the simulated time. This parameter can also be found in real TCP implementations (in Linux, it is possible to modify it on runtime by writing to the files /proc/sys/net/ipv4/tcp_rmem and /proc/sys/net/ipv4/tcp_wmem).

These, among many other parameters, change behavior in actual TCP

• •• ••••••••••••••••••••••••••••••••••••••••••••••••• • ••••••••••••••• • • • •••• • •••• • •• • •••••••••••••• • 0 20
• •• •••••••••••••••••••••••••••• ••••• •••••••• ••••••••••• ••••••••••••••••• •••••••••••••••••••
Grid'5000 (Nancy) Simgrid (Griffon)

Figure 3. Bandwidth per node in Grid'5000 vs. Simgrid (default network model and arguments). implementations and it is clear that not all of them behave the same way in practice. As a consequence of this, it is very difficult to decide on which implementation to follow as the "right one", as there are so many of them on the Internet.

• ••••••••••••••••••••••••••••••••••••••••• • •••••••••••••••• • ••••• • ••••••• • ••• • • • • • •• • •• • • •••• • • ••••
••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••• Grid'5000 (Nancy) Simgrid (griffon)

D. Physical node mapping interference

Distem, on the other hand, has a different set of issues arising from its abstractions. In a Distem network, the network is presented as an overlay, the underlying network and the physical nodes are hidden from the application. This derives in several constraints that have to be carefully analyzed.

One of them is the node mapping: if the overlay is emulated completely on top of a single node, memory bandwidth and system software act as a bandwidth barrier which can't be overcome. If the mapping is 1 physical node ↔ 1 virtual node, the barrier exists in the network equipment that connects the nodes to each other. A simple example in this case would be that it is not possible to connect virtual nodes on a Gigabit virtual network, if the underlying physical nodes are connected at 100 Mbps. In the same sense, it is also not possible to connect 100 virtual nodes on a single physical node at 1 Gbps, if memory bandwidth at that node is only 10 Gbps, and expect consistent results. In order to visualize this problem, we can see in Figure 5 the bandwidth per node going down as the number of virtual nodes increases, when the mapping is done over one single physical node. The expected bandwidth should be much higher, but it is limited by the way kernel buffers are managed. Test runs using improved netns and veth kernel subsystems yield a higher maximum bandwidth. Finally, bandwidth is not the only limiting factor, also emulated latencies should be higher than those of the underlying network. As an example of this, it is not possible to emulate a link with a latency of 1 µs over one with a real latency of 1 ms. Also, if both latencies are the same order of magnitude, it is very likely that there is interference from the outside network.

V. DISCUSSION

This section discusses the traps identified in the previous section and propose some recommendations and improvements both for the experimenters and for the tool designers.

A. Platform convergence

Our first conclusion on the platform issues is that the tools should enable users to converge to the platforms used by the different approaches. In our scenario, we have three sets of platforms: Simgrid platform files, Distem platform descriptions and real network testbeds. In order to compare results among all the tools, it is necessary that the platforms represent the same scenarios, otherwise the comparison would be unfair.

The tools could help the user achieve this by checking whether they match or not. For example, in the Emulab [START_REF] White | An integrated experimental environment for distributed systems and networks[END_REF] testbed, which offers a subset of the features found in Distem as used on top of Grid'5000 (namely network topology emulation by means of slowing down fast links), there is a tool called linktest [START_REF] Anderson | Automatic online validation of network configuration in the emulab network testbed[END_REF], that measures link latency and bandwidth after the platform has been instantiated, in order to identify differences with respect to the platform description. This tool is useful not only to corroborate that the experimental framework is able to reproduce the input scenario, but also to ensure that the user didn't make a mistake when they designed the platform model. For example, one such link measurement tool could be run in the real platform, in the platform as emulated by Distem, and finally a simulation of the same tool on top of Simgrid, and then all the results could be compared for statistically significant differences.

Similarly, being able to use the same platform descriptions in both Simgrid and Distem would be very useful to avoid error-prone work duplication. There is still the problem of handling virtual node mappings in Distem, which is a feature that doesn't make sense in the context of Simgrid, but being able to convert from Simgrid platforms to Distem, while keeping the ability to load Simgrid platforms would be a good start. As said before, there is already work in this direction, but it still needs some refinement.

B. Identify application traits

To get the most out of the tools, it is also necessary to understand what kind of application is being analyzed. Although it might seem like a chicken-and-egg problem to have to analyze a system in order to build a better analysis for it, the user has to understand very clearly what kind of application they are working on, as to properly identify traits that would not be conveyed by the experimental framework. Most of these questions require a good understanding of the application that is being analyzed and in some cases it is enough to analyze the source code to answer them. In case it is not that easy to infer, building experiments with the framework limitations in mind is a good start.

C. Converge experimental evaluation

Tools for experiment management are great improvements in terms of being able to automate experiment setup, execution and data gathering and analysis. We have used XP Flow to build all of our experiments. This tool provides an interface to work with Grid'5000 and handle all the steps of the experiment directly. The experiments themselves are structured using workflow logic, such as that used in business to describe processes.

Building experiments by hand has many problems: it is error-prone, it doesn't scale, it becomes increasingly difficult to manage all the data as the experiment size and number grow. Working with several experimental tools expands this problem manyfold, as there is a new dimension that has to be taken into account to match similar experiments using different tools. One big problem in dealing with different tools is that they all have their own way to do things. This is worsened by the fact that there are also many tools for experiment automation. Using several tools might require writing boilerplate code and wrappers to match the way each tool works.

In order to converge to a single framework to build experiments, this code should be clearly modularized to abstract away the differences in a way that they can be written generically.

VI. CONCLUSIONS

We have evaluated three different platforms for distributed system analysis, one for each of the paradigms in experimental evaluation, concentrating on the methodological aspects. Our driving question has been the performance of chain propagation algorithms in a cluster setting. We have discussed traps that users of these platforms might run into and provided some insight on how to avoid them. In particular, we have identified problems in the accuracy of platform descriptions, missing hardware models, incorrect assumptions in network models provided by these frameworks and communication interference due to assumptions with regard to node mapping in overlays. By pointing out these problems, we have been able to create experiments to correctly assess the performance of our chainsend application in simulation. There is ongoing work to show the full picture, including also results in emulation. Our assessment in this case is that, due to the nature of this particular workload, emulation is not able to provide an accurate view while getting the full benefits of the platform.

Finally, an interesting topic to carry our work forward is platform validation. We plan to provide a platform validation tool similar to linktest for each paradigm, and also work towards the convergence of platform descriptions, in order to make it easier for the experimenter to use different tools.

It is our belief that each of the methodologies provide an unique point of view that has to be complemented in order to acquire a better understanding of the system. It is important to understand the tools and their limitations in order to use them appropriately. Our suggestions move towards making it more straightforward to manage experiments and compare results, trying to reduce repetitive, error-prone steps as much as possible.

Figure 2 .

 2 Figure 2. Bandwidth per node in Grid'5000 after discarding writes to disk.

Figure 4 .

 4 Figure 4. Bandwidth per node in Grid'5000 vs. Simgrid (CM02 network model).

Figure 5 .

 5 Figure 5. Bandwidth per node in Grid'5000 vs. Distem (ten virtual nodes in one physical node).

  This means, among other things, understanding what kind of traffic the application generates, what transport protocol is used in the real implementation, what is the application protocol like, what kind of network is targeted by the application, what kind of resources could act as bottlenecks.

ACKNOWLEDGMENTS

M. Geier has a CONICET PhD fellowship. This work was supported by Inria.