Thomas Mensink

Jakob Verbeek

Florent Perronnin

Gabriela Csurka

Metric Learning for Large Scale Image Classification: Generalizing to New Classes at Near-Zero Cost

We are interested in large-scale image classification and especially in the setting where images corresponding to new or existing classes are continuously added to the training set. Our goal is to devise classifiers which can incorporate such images and classes on-the-fly at (near) zero cost. We cast this problem into one of learning a metric which is shared across all classes and explore k-nearest neighbor (k-NN) and nearest class mean (NCM) classifiers. We learn metrics on the ImageNet 2010 challenge data set, which contains more than 1.2M training images of 1K classes. Surprisingly, the NCM classifier compares favorably to the more flexible k-NN classifier, and has comparable performance to linear SVMs. We also study the generalization performance, among others by using the learned metric on the ImageNet-10K dataset, and we obtain competitive performance. Finally, we explore zero-shot classification, and show how the zero-shot model can be combined very effectively with small training datasets.

Introduction

In the last decade we have witnessed an explosion in the amount of images and videos that are digitally available, e.g. in broadcasting archives or social media sharing websites. Only a small fraction of this data is consistently annotated and thus scalable methods are needed for annotation and retrieval to efficiently access this huge volume of data. This need has been recognized in the computer vision research community and largescale methods have become an active topic of research in recent years, see among others [START_REF] Deng | ImageNet: A large-scale hierarchical image database[END_REF][START_REF] Checkik | Large scale online learning of image similarity through ranking[END_REF][START_REF] Deng | What does classifying more than 10,000 image categories tell us?[END_REF][START_REF] Vedaldi | Efficient additive kernels via explicit feature maps[END_REF][START_REF] Rohrbach | Evaluating knowledge transfer and zero-shot learning in a large-scale setting[END_REF][START_REF] Jégou | Product quantization for nearest neighbor search[END_REF][START_REF] Weston | WSABIE: Scaling up to large vocabulary image annotation[END_REF][START_REF] Sánchez | High-dimensional signature compression for large-scale image classification[END_REF][START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF][START_REF] Lin | Large-scale image classification: Fast feature extraction and SVM training[END_REF]. The introduction of the ImageNet dataset [START_REF] Deng | ImageNet: A large-scale hierarchical image database[END_REF], which contains more than 14M manually labeled images of 22K classes, has provided an important benchmark for large-scale image classification and annotation algorithms.

In this paper we focus on the problem of large-scale image annotation, where the goal is to assign automatically a set of relevant labels to an image, e.g. names of objects appearing in the image. The predominant approach to this problem is to treat it as a classification problem. To ensure scalability, often linear classifiers such as SVMs are used [START_REF] Sánchez | High-dimensional signature compression for large-scale image classification[END_REF][START_REF] Lin | Large-scale image classification: Fast feature extraction and SVM training[END_REF], sometimes in combination with dimension reduction techniques to speedup the classification [START_REF] Weston | WSABIE: Scaling up to large vocabulary image annotation[END_REF]. Recently, impressive results have been reported on 10,000 or more classes [START_REF] Deng | What does classifying more than 10,000 image categories tell us?[END_REF][START_REF] Weston | WSABIE: Scaling up to large vocabulary image annotation[END_REF][START_REF] Sánchez | High-dimensional signature compression for large-scale image classification[END_REF][START_REF] Perronnin | Towards good practice in large-scale learning for image classification[END_REF]. A drawback of these methods, however, is that when images of new categories become available, new classifiers have to be trained at a relatively high computational cost.

Many real-life large-scale datasets are open-ended and dynamic: new classes appear over time and new photos/videos are continuously added to existing classes. Therefore, the main objective of our work is to propose and study approaches which enable the addition of new classes and new images to existing classes at (near) zero cost. We explore two techniques to do so. The first is k-NN classification, where images of new classes are added in the database, and can be used for classification without further processing. This is a highly non-linear and non-parametric classifier that has shown competitive performance for image annotation [START_REF] Deng | What does classifying more than 10,000 image categories tell us?[END_REF][START_REF] Weston | WSABIE: Scaling up to large vocabulary image annotation[END_REF][START_REF] Guillaumin | Tagprop: Discriminative metric learning in nearest neighbor models for image auto-annotation[END_REF]. Its main drawback is that the nearest neighbor search for classification is computationally demanding for large and high-dimensional datasets. The second is the nearest class mean classifier (NCM), where classes are represented by their mean feature vector [START_REF] Webb | Statistical pattern recognition[END_REF][START_REF] Veenman | LESS: a model-based classifier for sparse subspaces[END_REF][START_REF] Zhou | SIFT-Bag kernel for video event analysis[END_REF]. The cost of computing the mean can be neglected with respect to the cost of feature extraction and this operation does not require accessing images of other classes. Contrary to the k-NN classifier, this is a linear classifier which leads to efficient classification. The complete distribution of the training data of a class is, however, only characterized by its mean and it is therefore unclear whether this is sufficient for competitive performance.

The success of both methods critically depends on the metric which is used to compute the distance between an image and other images (for k-NN) or class means (for NCM), see Figure 1 for an illustration. Metric learning has received much attention in the machine learning and computer vision communities recently, and has been shown to significantly increase the performance of distance-based classifiers. Therefore, we cast our classifier learning problem as one of learning a metric which is shared across all classes. For k-NN classification, we use the Large Margin Nearest Neighbor (LMNN) framework [START_REF] Weinberger | Distance metric learning for large margin nearest neighbor classification[END_REF] and propose a variation that significantly improves its performance. For the NCM classifier, we propose a novel metric learning algorithm based on multi-class logistic discrimination. A sample from a given class is enforced to be closer to its class mean than to any other class mean in the projected space. To apply these metric learning techniques on large-scale datasets, we employ stochastic gradient descend (SGD) algorithms, which access only a small fraction of the training data at each iteration [START_REF] Bottou | Large-scale machine learning with stochastic gradient descent[END_REF]. To allow metric learning on high-dimensional image features of large scale datasets that are too large to fit in memory, we in addition use product quantization [START_REF] Gray | Quantization[END_REF], a data compression technique that was recently used with success for large-scale image retrieval [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF] and classifier training [START_REF] Sánchez | High-dimensional signature compression for large-scale image classification[END_REF].

We report experiments on the ImageNet Large Scale Visual Recognition Challenge 2010 (ILSVRC'10) dataset, which consists of 1.2M train images of 1,000 classes. As a baseline approach, we use the setup of the winning entry in the 2011 edition of the challenge [START_REF] Sánchez | High-dimensional signature compression for large-scale image classification[END_REF]: Fisher vector image representations [START_REF] Perronnin | Improving the Fisher kernel for large-scale image classification[END_REF] are used to describe images and one-vs-rest linear SVM classifiers are learned independently for each class. Surprisingly, we find that the NCM classifier outperforms the more flexible k-NN classifier. Moreover, the NCM classifier performs on par with the SVM baseline. We also consider the generalization performance to new classes. In a first experiment, we train the metric on a subset of classes of ILSVRC'10 and include the held-out classes at test time. We only observe a small drop in performance compared to the experiment where the metric is learned with all classes. In a second experiment, we train the metric on ILSVRC'10 and apply it to a larger set of 10K ImageNet classes. Once the metric is The rest of the paper is organized as follows. In Section 2 we discuss a selection of related work which is most relevant to this paper. In Section 3 we present the metric learning techniques we explored for the k-NN and NCM classifiers. We then present extensive experimental results in Section 4, followed by our conclusions in Section 5.

Related Work

In this section we discuss some of the most relevant work on large-scale image annotation, metric learning, and transfer learning.

Large-scale image annotation. The ImageNet dataset [START_REF] Deng | ImageNet: A large-scale hierarchical image database[END_REF] has been a catalyst for research on large-scale image annotation. The current state-of-the-art [START_REF] Sánchez | High-dimensional signature compression for large-scale image classification[END_REF][START_REF] Lin | Large-scale image classification: Fast feature extraction and SVM training[END_REF] uses efficient linear SVM classifiers trained in a one-vs-rest manner in combination with highdimensional bag-of-word [START_REF] Zhang | Local features and kernels for classification of texture and object categories: a comprehensive study[END_REF] or Fisher vector representations [START_REF] Perronnin | Improving the Fisher kernel for large-scale image classification[END_REF]. Besides one-vs-rest training, large-scale ranking-based formulations have also been explored in [START_REF] Weston | WSABIE: Scaling up to large vocabulary image annotation[END_REF]. Interestingly, this approach performs joint classifier learning and dimensionality reduction of the image features. Operating in a lower-dimensional space acts as a regularization during learning and reduces the cost of classifier evaluation at test time. The proposed NCM approach also learns low-dimensional projection matrices but the weight vectors are constrained to be the class means. This allows the efficient addition of novel classes.

In [START_REF] Deng | What does classifying more than 10,000 image categories tell us?[END_REF][START_REF] Weston | WSABIE: Scaling up to large vocabulary image annotation[END_REF] k-NN classifiers were found to be competitive with linear SVM classifiers in a very large-scale setting involving 10,000 or more classes. The drawback of k-NN classifiers, however, is that they are expensive in storage and computation, since in principle all training data needs to be kept in memory and accessed to classify new images. The storage issue is also encountered when SVM classifiers are trained since all training data needs to be processed in multiple passes. Product quantization (PQ) was introduced in [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF] as a lossy compression mechanism for local SIFT descriptors in a bag-of-features image retrieval system. It has been subsequently used to compress bagof-word and Fisher vector image representations in the context of image retrieval [START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF] and classifier training [START_REF] Sánchez | High-dimensional signature compression for large-scale image classification[END_REF]. We also exploit PQ in our work to compress high-dimensional image signatures when learning our metrics.

Metric learning. Here, we only discuss methods that learn metrics for image classification problems. Other methods aim at learning metrics for verification problems and essentially learn binary classifiers that threshold the learned distance to decide whether two images belong to the same class or not, see e.g. [START_REF] Nowak | Learning visual similarity measures for comparing never seen objects[END_REF].

Among those methods that learn metrics for classification, the Large Margin Nearest Neighbor (LMNN) approach of [START_REF] Weinberger | Distance metric learning for large margin nearest neighbor classification[END_REF] is specifically designed to support k-NN classification. It tries to ensure that for each image its predefined set of target neighbors from the same class are closer than samples from other classes. Since the cost function is defined over triplets of points -that can be sampled in an SGD training procedurethis method can scale to large datasets. In [START_REF] Weinberger | Distance metric learning for large margin nearest neighbor classification[END_REF] the set of target neighbors is chosen and fixed using the ℓ 2 metric in the original space, that can be problematic as this distance is far from being ideal, see e.g. Figure 1. Therefore, we propose two variants of LMNN that avoid using such a pre-defined set of target neighbors, both leading to significant improvements.

The large margin nearest local mean classifier [START_REF] Chai | Large margin nearest local mean classifier[END_REF] assigns a test image to a class based on its distance to the mean of its nearest neighbors in each class. This method was reported to outperform LMNN but requires computing all pairwise distances between training instances and therefore does not scale well to large datasets. Similarly, TagProp [START_REF] Guillaumin | Tagprop: Discriminative metric learning in nearest neighbor models for image auto-annotation[END_REF] suffers from the same problem. It consists in assigning weights to training samples based on their distance to the test instance and in computing the class prediction by the total weight of samples of each class in a neighborhood. Because of their poor scaling properties, we do not consider these methods in our experiments.

Closely related to our metric learning approach for the NCM classifier is the LESS model of [START_REF] Veenman | LESS: a model-based classifier for sparse subspaces[END_REF]. They learn a diagonal scaling matrix to modify the ℓ 2 distance by rescaling the data dimensions, and include an ℓ 1 penalty on the weights to perform feature selection. However, in their case, NCM is used to address small sample size problems in binary classification, i.e. cases where there are fewer training points (tens to hundreds) than features (thousands). Our approach differs significantly in that (i) we work in a multi-class setting and (ii) we learn a low-dimensional projection which allows efficiency in large-scale. The method of [START_REF] Zhou | SIFT-Bag kernel for video event analysis[END_REF] is also related to our method since they use a NCM classifier and an ℓ 2 distance in a subspace that is orthogonal to the subspace with maximum within-class variance. However, their technique involves computing the first eigenvectors of the within-class covariance matrix, which has a computational cost between O(D 2 ) and O(D 3 ), which again is undesirable for high-dimensional feature vectors. Moreover, this metric is heuristically obtained, rather than directly optimized for maximum classification performance.

Transfer learning. The term transfer learning is used to refer to methods that share information across classes during learning. Examples include the use of part-based or attribute class representations. Part-based object recognition models [START_REF] Fei-Fei | One-shot learning of object categories[END_REF] define an object as a spatial constellation of parts, and share the part detectors across different classes. Attribute-based models [START_REF] Lampert | Learning to detect unseen object classes by between-class attribute transfer[END_REF] characterize a category (e.g. animal) by a combination of attributes (e.g. yellow, stripes, carnivore), and share the attribute classifiers across classes. Other approaches include biasing the weight vector learned for a new class towards the weight vectors of classes that have already been trained [START_REF] Tommasi | The more you know, the less you learn: from knowledge transfer to one-shot learning of object categories[END_REF]. Zero-shot learning [START_REF] Larochelle | Zero-data learning of new tasks[END_REF] is an extreme case of transfer learning where for a new class no training instances are available but a description is provided in terms of parts, attributes, or other relations to already seen classes. In [START_REF] Rohrbach | Evaluating knowledge transfer and zero-shot learning in a large-scale setting[END_REF] various transfer learning methods were evaluated in a large-scale setting using the ILSVRC'10 dataset. They found transfer learning methods to have little added value when training images are available for all classes. In contrast, transfer learning was found to be effective in a zero-shot learning setting, where classifiers were trained for 800 classes, and performance was tested in a 200-way classification across the held-out classes.

In this paper we also aim at transfer learning, in the sense that we allow only a trivial amount of processing on the data of new classes (storing in a database, or averaging), and rely on a metric that was trained on other classes to recognize the new ones. In contrast to most work on transfer learning, we do not use any intermediate representation in terms of parts or attributes, nor do we train classifiers for the new classes. While also considering zero-shot learning, we further evaluate performance when combining a zero-shot model inspired by [START_REF] Rohrbach | Evaluating knowledge transfer and zero-shot learning in a large-scale setting[END_REF] with progressively more training images per class, from one up to thousands. We find that the zero-shot model provides an effective prior when a small amount of training data is available.

Learning Metrics to Generalize to New Categories

In this section we discuss metric learning for the k-NN and NCM classifiers. We learn Mahalanobis distances of the form (x -x ′ ) ⊤ M (x -x ′ ) to improve classification accuracy, where x ∈ IR D . We focus on low-rank metrics with M = W ⊤ W and W ∈ IR d×D , where d ≤ D acts as regularizer and improves efficiency for computation and storage. The Mahalanobis distance induced by W is equivalent to the ℓ 2 distance after projection:

x -x ′ 2 W = (x -x ′ ) ⊤ W ⊤ W (x -x ′ ) = W x -W x ′ 2 .
(1)

Metric Learning for k-NN Classification

K-NN classification is essentially a ranking problem, which is reflected in the metric learning approach of LMNN [START_REF] Weinberger | Distance metric learning for large margin nearest neighbor classification[END_REF]. Their learning objective is based on triplets of images, where the distance between a query image q and a target image p of the same class should be smaller than the distance to a negative image n of a different class. The 0/1-loss for such a triplet is upper-bounded by the hinge-loss on the distance difference:

L qpn = 1+ x q -x p 2 W -x q -x n 2 W + , (2)
which is zero if the negative image n is at least one distance unit farther from the query q than the positive image p, and positive otherwise. The sum of the per-triplet loss is the final learning criterion:

L = N q=1 p∈Pq n∈Nq L qpn , (3)
where P q and N q denote the set of positive and negative images for a query image x q .

The sub-gradient of the loss is obtained as:

∇ W L = N q=1 p∈Pq n∈Nq ∇ W L qpn , (4)
∇ W L qpn = [[L qpn > 0]]2W (x q -x p )(x q -x p ) ⊤ -(x q -x n )(x q -x n ) ⊤ , (5)
where we use Iversons bracket notation [[•]] that equals one if its argument is true, and zero otherwise.

In LMNN the set of targets P q for a query q is set to the query's k nearest neighbors from the same class, using the ℓ 2 distance. The rationale is the following one: if we can ensure that these targets are closer than the instances of the other classes, then the k-NN classification will succeed. In practice, however, it is not always possible to achieve this situation with a given set of target neighbors, since it implicitly assumes that the ℓ 2 distance in the original space is a good similarity measure. Therefore, we consider two alternatives to using a fixed set of target neighbors:

-First, we can set P q to contain all images with the same class label as q. This is similar to [START_REF] Checkik | Large scale online learning of image similarity through ranking[END_REF] where the same type of loss was used to learn image similarity defined as the scalar product between images after a learned linear projection. -Second, we can define P q dynamically to contain the k images of the same class that are closest to q using the current metric. This option corresponds to minimizing the loss function also with respect to the choice of P q . Hence, different target neighbors can be selected, that are closer than the original ones according to the current metric. A similar approach has been proposed in [START_REF] Weinberger | Distance metric learning for large margin nearest neighbor classification[END_REF], where every T iterations P q is redefined using target neighbors according to the current metric.

Since the number of possible triplets tends to be large for any of these strategies3 , at each SGD iteration we generate triplets from a limited set of m ≪ N images.

Metric Learning for the Nearest Class Mean Classifier

We formulate the NCM classifier using multi-class logistic regression and define the probability for a class c given an image feature vector x as:

p(c|x) = exp -µ c -x 2 W C c ′ =1 exp -µ c ′ -x 2 W , (6)
where µ c is the mean for class c ∈ {1, . . . , C}. Our objective is to minimize the negative log-likelihood of the ground-truth class labels y i ∈ {1, . . . , C} of the training images:

L = - 1 N N i=1 ln p(y i |x i ). (7)
The gradient of this objective function is easily verified to be:

∇ W L = 2 N N i=1 C c=1 [[y i = c]] -p(c|x) W (µ c -x i )(µ c -x i ) ⊤ . (8)
To learn the projection matrix W , we use SGD training and sample at each iteration a fixed number of m training images to estimate the gradient. Note that the NCM classifier is linear in x since we assign an image x to the class c * with minimum distance:

c * = arg min c x -µ c 2 W = arg min c W µ c 2 -2µ ⊤ c (W ⊤ W )x . (9)
This observation shows that our classifier can be related to the WSABIE method of [START_REF] Weston | WSABIE: Scaling up to large vocabulary image annotation[END_REF].

In the latter paper, a class c is scored using f c (x) = v ⊤ c W x, where W projects the image into a lower-dimensional space, and v c is a class specific weight vector learned from data. However, we enforce that v c = W µ c , which allows us to add new classes without the need to learn v c from labeled data and therefore at almost zero cost.

Note that our classifier can also be related to the solution of ridge-regression, or regularized linear least-squares regression. Let f c (x i ) = b c + w ⊤ c x i and let y ic = 1, if x i belongs to class c, and y ic = 0 otherwise. The ridge-regression loss function,

1 N i (f c (x i ) -y ic ) 2 + λ w c 2
, can be minimized in closed form and leads to

f c (x) = nc N 1 + µ ⊤ c (Σ + λI) -1
x , where Σ is the (class-independent) data covariance matrix, and n c denotes the number of images in class c. If n c is equal for all classes, then the score function is equivalent to µ ⊤ c (Σ+λI) -1 x up to additive and multiplicative constants. This is similar to our NCM classifier if we set W such that W ⊤ W = (Σ + λI) -1 , see Eq. ( 9). Moreover, just like the NCM classifier, the ridge-regression function for a new class can also be found from the class mean µ c and count n c , once the data covariance matrix has been estimated. would yield already N (N -N C ) pairs. For ILSVRC'10, we have N ≈ 10 6 and C = 10 3 which leads to roughly 10 12 pairs, and to even more triplets.

Experimental Evaluation

In this section we first describe the dataset and evaluation measures used in our experiments. Then, we present our results for metric learning using k-NN classification in Section 4.2, and those using NCM classification in Section 4.3. Finally, in Section 4.4, we present results for transfer learning, where we apply metrics trained on some classes to novel ones, and assess performance as a function of the number of training images.

Experimental Setup and Baseline Approach

Dataset. In most of our experiments we use the dataset of the ImageNet Large Scale Visual Recognition 2010 challenge (ILSVRC '10). This dataset contains 1.2M training images of 1,000 object classes (with between 660 to 3047 images per class), an evaluation set of 50K images, and a test set of 150K images.

Features. We represent each image, with a Fisher vector (FV) [START_REF] Perronnin | Improving the Fisher kernel for large-scale image classification[END_REF] computed over densely extracted SIFT descriptors and local color features, both projected with PCA to 64 dimensions. FVs are extracted and normalized separately for both channels and then combined by concatenating the two feature vectors. We do not make use of spatial pyramids. In our experiments we use FVs extracted using a vocabulary of either 16 or 256 Gaussians. For 16 Gaussians, this leads to a 4K dimensional feature vector, which requires about 20GB for the 1.2M training set (using 4-byte floating point arithmetic). This fits into the RAM of our 32GB servers.

For 256 Gaussians, the FVs are 16 times larger, i.e. 64K dimensional, which would require 320GB of memory. Hence, we compress the feature vectors using product quantization [START_REF] Gray | Quantization[END_REF]. In a nutshell, it consists in splitting the high-dimensional vector into small sub-vectors, and vector quantizing each sub-vector independently. We compress the dataset to approximately 10GB using 8-dimensional sub-vectors and 256 centroids per sub-quantizer, which allows storing each sub-quantizer index in a single byte. In each iteration of SGD learning, we decompress the features of a limited number of images, and use these (lossy) reconstructions for the gradient computation.

Evaluation measures. We report the average top-1 and top-5 flat error used in the ILSVRC'10 challenge. The flat error is one if the ground-truth label does not correspond to the top-1 label with highest score (or any of the top-5 labels), and zero otherwise. Unless specified otherwise, we report the top-5 flat error on the test set using the 4K dimensional features; we use the validation set for parameter tuning only. In tables, we highlight the best result per row in bold, and do so for each feature set if several are used. Additionally, the baseline performance is also highlighted if it is best.

Baseline approach. For our baseline, we follow the state-of-the-art approach of [START_REF] Sánchez | High-dimensional signature compression for large-scale image classification[END_REF] and learn 1,000 one-vs-rest SVMs with SGD. The results of the baseline can be found in Table 2. We see that the 64K dimensional features lead to significantly better results than the 4K ones, despite the lossy PQ compression. The performance using the 64K features is slightly better than the ILSVRC'10 challenge winners [START_REF] Lin | Large-scale image classification: Fast feature extraction and SVM training[END_REF] (28.0 vs. 28.2 flat top-5 error), and very close to the results of [START_REF] Sánchez | High-dimensional signature compression for large-scale image classification[END_REF] (25.7 flat top-5 error). Note that there a much higher dimensional representation was used of more than 1M features. SGD training and early stopping. To learn the projection matrix W , we use SGD training, sampling at each iteration a fixed number of training images to estimate the gradient. Following [START_REF] Bai | Learning to rank with (a lot of) word features[END_REF], we use a fixed learning rate and use the projection dimension d ≤ D as well as the number of iterations as an implicit form of regularization. We run SGD for 750K-4M iterations, and the performance is validated every 10K (NCM) or 50K (k-NN) iterations. The metric which yields the lowest top-5 error is selected. Similarly, all hyper-parameters, like the value of k for the k-NN classifiers, are validated in this way. Unless stated otherwise, training is performed using the ILSVRC'10 training set, and validation on the provided 50K validation set.

k-NN Metric Learning Results

We start with an assessment of k-NN classifiers using metrics learned with the methods described in Section 3.1. Given the cost of k-NN classifiers, we focus our experiments on the 4K features. We consider the impact of the different choices for the set of target images P q as described in Section 3.1, and the influence of the projection dimensionality. We initialize W as a PCA projection, the optimal k is typically 100 or 250.

Target selection for k-NN metric learning. In the first experiment we compare the three different options of Section 3.1 to define the set of target images P q , while learning projections to 128 dimensions. For LMNN and dynamic targets, we experimented with various numbers of targets on the validation set and found that using 10 to 20 targets yields the best results. The results in Table 1 show that all methods lead to metrics that are better than the ℓ 2 metric in the original space, or after a PCA projection to 128 dimensions. Furthermore, we can improve over LMNN by using all within-class images as targets, or even further by using dynamic targets. The success of the dynamic target selection can be explained by the fact that among the three alternatives, it is the most closely related to the k-NN classifier objective. The best performance on the flat top-5 error of 39.8 using 10 dynamic targets is, however, slightly worse than the 38.2 error rate of the SVM baseline.

Impact of projection dimension on k-NN classification. Next, we evaluate the influence of the projection dimensionality, by varying it between 32 and 1024. We only show results using 10 dynamic targets, since this performed best among the evaluated k-NN methods. From the results in Table 2 we see that a projection to 256 dimensions yields the lowest error of 39.0, still somewhat inferior of those of the SVM baseline.

Nearest Class Mean Classification Results

We now consider the performance of NCM classifiers and the related methods described in Section 3.2. In Table 2 we show the results for various projection dimensionalities. We first consider the results for the 4K dimensional features. Our first, unexpected, observation is that our NCM classifier (37.0) outperforms the more flexible k-NN classifier (39.0), and even slightly outperforms the SVM baseline (38.2) when projecting to 256 dimensions or more. Interestingly, using the ℓ 2 instead of a learned metric, the situation is reversed and the k-NN classifier is better (55.9, see Table 1) than the NCM classifier (68.0). WSABIE scores slightly worse (38.5) than the baseline and our NCM classifier, and does not generalize to new classes without retraining. Like the NCM classifier, ridge-regression does allow generalization to new classes, but leads to significantly worse results (54.6) and pre-processing the data with PCA further degrades its performance.

We also consider two variants of the NCM classifier where we use PCA to reduce the dimensionality. In one case we use the ℓ 2 metric after PCA. In the other, inspired by ridge-regression, we use the metric generated by the inverse of the regularized covariance matrix, see Section 3.2. We tuned the regularization parameter λ on the validation set, as was also done for ridge-regression. From these results we can conclude that, just like for k-NN, the ℓ 2 metric with or without PCA leads to poor results as compared to a learned metric. Second, the feature whitening implemented by the inverse covariance metric, leads to results that are better than using the ℓ 2 metric, and also substantially better than ridge-regression. The results are however significantly worse than using our learned metric, in particular when using low-dimensional projections.

When we use the 64K dimensional features, the results of the NCM classifier (30.7) are somewhat worse than the SVM baseline (28.0); again the learned metric is better than using ℓ 2 (63.2). WSABIE obtains an error of 29.2, in between the SVM and NCM.

In Figure 1 we illustrate the difference between the ℓ 2 and the Mahalanobis metric induced by a learned projection from 64K to 512 dimensions. For three reference classes we show the five nearest classes, based on the distance between class means. We also show the probabilities on the reference class and its five neighbor classes according to Eq. ( 6). The feature vector x is set as the mean of the reference class, i.e. a simulated perfectly typical image of this class. For the ℓ 2 metric, we used our metric learning algorithm to learn a scaling of the ℓ 2 metric to minimize Eq. ( 7). This does not change the ordering of classes, but ensures that we can compare probabilities computed using both metrics. We find that, as expected, the learned metric has more semantically related class neighbors. Moreover, we see that using the learned metric most of the probability mass is assigned to the reference class, whereas the ℓ 2 metric leads to rather uncertain classifications.

Generalization to New Classes and Using Few Samples

Given the encouraging classification accuracy of the NCM classifier observed above -and its superior efficiency as compared to the k-NN classifier-we now explore its ability to generalize to novel classes. We also consider its performance as a function of the number of training images available to estimate the mean of novel classes.

Generalization to novel classes not seen during training. In this experiment we use approximately 1M images corresponding to 800 random classes to learn metrics, and evaluate the error of a 1,000-way classification across all classes. We report the error computed over the 30K images in the test set of the held-out 200 classes. Performance among test images of the 800 train classes changes only marginally and would obscure the changes among the test images of the 200 held-out classes.

In Table 3 we show the performance of NCM and k-NN classifiers for several projection dimensions, and compare it to two control settings, training on all 1,000 classes, and using the ℓ 2 distance. The results show that both classifiers generalize remarkably well to new classes. In particular for 1024 dimensional projections of the 4K features, the NCM classifier achieves an error of 39.6 over classes not seen during training, as compared to 36.5 when using all classes for training. For the 64K dimensional features the drop in performance is larger, but it is still surprisingly good considering that training for the novel classes consists only in computing the mean.

To further demonstrate the generalization ability of the NCM classifier using learned metrics, we also compare it against the SVM baseline on the ImageNet-10K dataset. This dataset, introduced in [3], consists of 4.5M training images of 10,184 classes, and a test set of another 4.5M images. We use projections learned on the ILSVRC'10 dataset, and only compute the means of the 10K classes. The results in Table 4 show that even in this extremely challenging setting the NCM classifier performs remarkably well compared to [START_REF] Deng | What does classifying more than 10,000 image categories tell us?[END_REF][START_REF] Sánchez | High-dimensional signature compression for large-scale image classification[END_REF][START_REF] Perronnin | Towards good practice in large-scale learning for image classification[END_REF] and our baseline, all of which require training 10K classifiers. We note that, to the best of our knowledge, our baseline results exceed the previous known state-of-the-art [START_REF] Deng | What does classifying more than 10,000 image categories tell us?[END_REF][START_REF] Sánchez | High-dimensional signature compression for large-scale image classification[END_REF][START_REF] Perronnin | Towards good practice in large-scale learning for image classification[END_REF] on this dataset. Training our SVM baseline system took 9 and 280 CPU days respectively for the 4K and 64K features, while the computation of the means for the NCM classifier took approximately 3 and 48 CPU minutes respectively. This represents roughly a 8,500 fold speed-up as compared to the baseline, without counting the time to learn the projection matrix.

Accuracy as a function of the number of training images of novel classes. In our last experiment we consider the error as a function of the number of images that are used to compute the means of novel classes. We also include results of a zero-shot learning experiment, where we use the ImageNet hierarchy to estimate the mean of novel classes from the means of related training classes. We follow ideas of [START_REF] Rohrbach | Evaluating knowledge transfer and zero-shot learning in a large-scale setting[END_REF] and estimate the mean of a novel class as the average of the means associated with all ancestor nodes in the ILSVRC'10 class hierarchy. The means of internal nodes are computed as the average of the means of all descendant training classes. If we view the estimation of a class mean as the estimation of the mean of a Gaussian distribution, then the sample average µ s corresponds to the Maximum Likelihood (ML) estimate and the zero-shot estimate µ z can be thought of as a prior. We can combine this prior with the ML estimate to obtain a maximum a-posteriori (MAP) estimate µ p on the class mean. The MAP estimate of the mean of a Gaussian is obtained as the ML estimate weighted by the number n of images that were used to compute it, plus the prior mean which has a weight m determined on the validation set [START_REF] Gauvain | Maximum a posteriori estimation for multivariate Gaussian mixture observations of Markov chains[END_REF], i.e. µ p = (nµ s + mµ z )/(n + m).

In Figure 2 we analyze the performance of the NCM classifier trained on the images of the same 800 classes used above, with a learned projection from 64K to 512 dimensions. We again report the error among test images of the held-out classes, both in a 1,000-way classification as above, and in a 200-way classification as in [START_REF] Rohrbach | Evaluating knowledge transfer and zero-shot learning in a large-scale setting[END_REF]. We repeat the experiment 10 times, and show error-bars at three times standard deviation. For the error to stabilize we only need approximately 100 images to estimate the class means. The results also show that the prior leads to zero-shot performance of 64.3, which is comparable to the result of 65.2 reported in [START_REF] Rohrbach | Evaluating knowledge transfer and zero-shot learning in a large-scale setting[END_REF], even though they used a different set of 200 test classes. More importantly, we show that the zero-shot prior can be effectively combined with the empirical mean to provide a smooth transition from the zero-shot setting to a setting with many training examples. Inclusion of the zero-shot prior leads to a significant error reduction in the regime where ten images or less are available.

Conclusions

We have evaluated metric learning techniques to support k-NN and NCM classifiers, which can be applied on large scale dynamic and open-ended image datasets, and allow extensions at (near) zero cost to new classes not used for training. Surprisingly we found that the NCM classifier outperforms the more flexible k-NN approach. Moreover, using a learned metric, the performance of the NCM classifier is comparable to that of SVM classifiers, while projecting the data to only 256 dimensions. Our learned metrics generalize well to unseen classes, as shown in experiments where the metric is learned on a subset of the classes, and further corroborated by our experiments on the ImageNet-10K dataset. In addition, we have shown that our NCM classifiers can be used in a zero-shot setting where no training images are available for novel classes, and that the zero-shot model significantly boosts performance when combined with a class mean estimated from a limited amount of training images.

In the proposed NCM classifiers each class is represented only by its mean, while this has the advantage of obtaining fast linear classifiers at test time, this representation is also rather restrictive. In ongoing work we extend this class representation, for example by using a representation based on a set of class centroids, to obtain more flexible and non-linear classifiers.

Interestingly, query-by-example image retrieval can be seen as a classification problem where a single positive sample is provided. In such a case, the class mean simplifies to the query which shows that the proposed NCM provides a unified way to treat classification and retrieval problems. This is a direction that we will explore in future work.

Fig. 1 .

 1 Fig. 1. The nearest classes for three reference classes using the the ℓ2 and Mahalanobis metric learned for the NCM classifier. Class probabilities are given for a simulated image signature that equals the mean of the reference class, see Section 4.3 for details.

Fig. 2 .

 2 Fig. 2. Performance of NCM as a function of the number of images used to compute the means for classes not used during training, with and without the zero-shot prior. See text for details.

Table 1 .

 1 k-NN classification performance with 4K dimensional features. For all methods, except those indicated by 'Full', the data is projected to a 128 dimensional space.

				k-NN classifiers
	SVM	ℓ2	ℓ2	LMNN	All	Dynamic
	Full	Full + PCA	10 20		10 20
	Flat top-1 error 60.2 75.0	76.3	72.9 72.8 67.9 65.1 66.0
	Flat top-5 error 38.2 55.9	57.3	50.6 50.4 44.2 39.8 40.7

Table 2 .

 2 Performance of k-NN and NCM classifiers, as well as baselines, using the 4K and 64K dimensional features, for various projection dimensions, see text for details.

		4K dimensional features	64K dimensional features
	Projection dim.	32 64 128 256 512 1024 Full	128 256 512	Full
	SVM baseline	38.2		28.0
	k-NN, dynamic 10	47.2 42.2 39.8 39.0 39.1 40.4
	NCM, learned metric 49.1 42.7 39.0 37.4 37.0 37.0	31.7 31.0 30.7
	NCM, PCA+ℓ2	78.7 74.6 71.7 69.9 68.8 68.2 68.0		63.2
	NCM, PCA+inv.cov. 75.5 67.7 60.6 54.5 49.3 46.1 43.8
	PCA+Ridge-regress. 86.3 80.3 73.9 68.1 62.8 58.9 54.6
	WSABIE [7]	51.9 45.1 41.2 39.4 38.7 38.5	32.2 30.1 29.2

Table 3 .

 3 Performance of 1,000-way classification among test images of 200 classes not used for metric learning, and control setting with metric learning using all classes. Left column denotes the number of training classes used, and "plain" denotes k-NN or NCM using the ℓ2 distance.

		4K dimensional features	64K dimensional features
	SVM	k-NN	NCM	SVM	NCM
	Full	128 256 Full 128 256 512 1024 Full	Full 128 256 512 Full
	Plain	54.2	66.6		61.9
	1000 37.6 39.1 38.4	38.6 36.8 36.4 36.5	27.7 31.7 30.8 30.6
	800	42.2 42.4	42.5 40.4 39.9 39.6		39.3 37.7 37.1

Table 4 .

 4 Average per-class performance of the NCM classifier on the ImageNet-10K dataset, using metrics learned on the ILSVRC'10 dataset, and comparison to previously published results.

	4K dimensional features	64K dimensional features 21K 128K 128K
	Proj. dim. 128 256 512 1024 SVM	128 256 512	SVM	[3] [8] [11]
	Flat top-1 91.8 90.7 90.5 90.4 86.0	87.1 86.3 86.1	78.1	93.6 83.3 81.9
	Flat top-5 80.7 78.9 78.6 78.6 72.4	71.7 70.5 70.1	60.9

Even if we disregard the set of target neighbors, each query image is paired with all images of other classes. Thus, if we have N training images evenly distributed among C classes, this


Juan Antonio Cordero

Philippe Jacquet
email: philippe.jacquet@inria.fr

Emmanuel Baccelli
email: emmanuel.baccelli@inria.fr

Impact of Jitter-based Techniques on Flooding over Wireless Ad hoc Networks: Model and Analysis

Jitter is used in wireless ad hoc networks to reduce the number of packet collisions and the number of transmissions. This is done by scheduling random back-off for each packet to be transmitted and by piggybacking multiple packets in a single transmission. This technique has been standardized by the IETF in RFC 5148. This paper investigates on the impact of the standardized jitter mechanism on network-wide packet dissemination -i.e. flooding, an important component for many protocols used today. A novel analytical model is introduced, capturing standard jitter traits. From this model is derived accurate characterization of the effects of jittering on flooding performance, including the additional delay for flooded packets on each traversed network interface, the reduction of the number of transmissions over each network interface, and the increased length of transmissions, depending on jitter parameters. This paper also presents an analysis of the use of jitter in practice, over an 802.11 wireless link layer based on CSMA. The analytical results are then validated via statistical discrete event simulations. The paper thus provides a comprehensive overview of the impact of jittering in wireless ad hoc networks.

I. INTRODUCTION

Periodic and quick network-wide packet dissemination, i.e. flooding, is fundamental to many protocols used in today's Internet. Several flooding techniques exist [START_REF] Qayyum | Multipoint Relaying for Flooding Broadcast Messages in Mobile Wireless Networks[END_REF], [START_REF] Dalal | Reverse Path Forwarding of Broadcast Packets[END_REF], [START_REF] Sasson | Probabilistic Broadcast for Flooding in Wireless Mobile Ad hoc Networks[END_REF] the simplest one relying on the principle that each node in the network forwards a flooded packet once -the first time it receives this packet. In wireless multi-hop ad hoc networks, flooding is an essential component of some of the most prominent routing protocols, such as OLSR [START_REF] Clausen | RFC 3626, Optimized Link State Routing Protocol (OLSR)[END_REF], MANET extensions of OSPF [START_REF] Roy | RFC 5820, Extensions to OSPF to Support Mobile Ad Hoc Networking[END_REF], [START_REF] Ogier | RFC 5614, Mobile Ad Hoc Network (MANET) Extension of OSPF[END_REF], [START_REF] Baccelli | RFC5449, OSPF Multipoint Relay Extension for Ad Hoc Networks[END_REF] and AODV [START_REF] Perkins | RFC 3561, Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF].

Due to the characteristics of the shared wireless medium [START_REF] Baccelli | IP Links in Multihop Ad Hoc Wireless Networks?[END_REF], nodes in ad hoc networks must often forward flooded packets on the same interface they were received on. Upon reception of a flooded packet, nearby nodes are thus likely to simultaneously forward the packet on the shared wireless medium, and thus systematically cause packet collisions.

In order to reduce the number of such collisions in a distributed fashion, random back-off times are independently scheduled by each node before each transmission, which aims at avoiding synchronized wireless medium access. Such a mechanism, called jitter or jittering, was standardized by the IETF in RFC 5148 [START_REF] Clausen | RFC5148, Jitter Considerations in Mobile Ad Hoc Networks[END_REF]. Jitter thus decreases the number of collisions at the price of increased delay.

During the time a node waits before transmitting, additional flooded packets may be received. According to RFC 5148, these packets are then buffered and piggybacked in the node's next transmission. This jittering technique also decreases the number of transmissions, at the price of longer transmissions, i.e. bigger packets.

Unintended jitter has been widely studied, both theoretically and based on experimental analysis, in the context of real-time services (such as for voice transport or video streaming) for several networking scenarios, in particular for ATM [START_REF] Fulton | Delay Jitter First-Order and Second-Order Statistical Functions of General Traffic on High-Speed Multimedia Networks[END_REF], [START_REF] Bisdikian | On the Jitter and Delay Analysis in ATM Multiplexer[END_REF] or IP wired and wireless networks [START_REF] Zheng | Characteristics of network delay and delay jitter and its effect on voice over IP (VoIP)[END_REF], [START_REF] Daniel | An Inter-arrival Delay Jitter Model using Multi-Structure Network Delay Characteristics for Packet Networks[END_REF], [START_REF] Chung | Jitter Analysis of Homogeneous Traffic in Wireless Differentiated Services Networks[END_REF].

Deliberate jitter was initially used in ALOHA and CSMA, which have been widely studied in the literature [START_REF] Takagi | Optimal Transmission Ranges for Randomly Distributed Packet Radio Terminals[END_REF] [START_REF] Oliveira | The influence of broadcast traffic on IEEE 802.11 DCF networks[END_REF]. The optimal jitter range has been studied experimentally in [START_REF] Broch | A performance comparison of multi-hop wireless ad hoc network routing protocols[END_REF], while [START_REF] Friedman | Jittering Broadcast Transmissions in MANETs: Quantification and Implementation Strategies[END_REF] proposed an analytical model for broadcast transmissions, taking a network-wide approach to describe the relationship between jitter range and probability of transmission without collision, and to evaluated the use of jitter at different layers.

This paper studies the use of jitter techniques specified by the IETF in RFC 5148 [START_REF] Clausen | RFC5148, Jitter Considerations in Mobile Ad Hoc Networks[END_REF], in the context of flooding over multi hop wireless networks. An analytical model is introduced, and several results are derived concerning incurred delays, transmission rates reduction and packet size increase. These results offer a comprehensive view of the impact of jitter on flooding performance.

The remainder of this paper is organized as follows. Section II describes in detail the packet jittering technique. This section details the use of jittering techniques for preventing packet collisions in flooding. Section III presents an analytical model of the flooding operation in a link-state router. The impact of random delay in packet forwarding is studied in this analytical framework. Section VI validates the results obtained in the previous section through simulations. Finally, section VII concludes the paper .

II. THE JITTER MECHANISM FOR FLOODING

This section details the use of jittering techniques, as specified in RFC 5148 [START_REF] Clausen | RFC5148, Jitter Considerations in Mobile Ad Hoc Networks[END_REF], in the context of classical flooding, where each node in the network forwards a flooded packet once, the first time the packet is received. In this context, packet collisions occur when two neighboring nodes forward the same packet, immediately after its reception, as illustrated in Figure 1. It is worth to note that collisions in flooding addressed in this paper are systematic, i.e. they are come deterministically from the fact that two or more nearby routers take the same decision (to forward a flooded packet) in reaction to the same event (the reception of that packet). Prevention of these collisions, or at least reduction of them to random events with low probability, becomes thus a central issue to be handled for flooding in ad hoc networks. RFC 5148 [START_REF] Clausen | RFC5148, Jitter Considerations in Mobile Ad Hoc Networks[END_REF] specifies techniques for reducing packet collisions occurences. When an interface receives a message to be forwarded, a jitter value (denoted t throughout this paper ) is selected randomly with a uniform distribution in the interval [0, J m ], where J m is the maximum jitter value (named by M AXJIT T ER in RFC 5148). According to the specification, such jitter values may be used for three cases of message transmission: periodic messages, externally triggered messages, and message forwarding. This paper focuses on the impact of jitter in flooded message forwarding. In the following, we will consider messages disseminated networkwide in flooded packets that may contain one or more messages. The motivation for using jittering techniques in this case is therefore two-fold (a) to reduce the number of wireless collisions by spreading message transmissions over time, and (b) to reduce the number of transmissions by piggybacking several messages in a single packet.

A wireless interface that receives a packet may decide to forward some of the messages contained in this packet. In this case, the interface assigns a jitter value to the messages to be be forwarded -the same value for all messages belonging to the same packet -and schedules their transmission after the expiration of the time-out. A wireless interface may also itself generate messages to be flooded. Such self-generated messages are scheduled for immediate transmission, which is equivalent to assigning them a jitter equal to zero. Then, when a transmission is scheduled, all buffered messages waiting to be transmitted -that were either received from other interfaces in the mean time, or self-generated-are sent in a single packet. The flowchart in Figure 2 summarizes this procedure, in which three elements can be pointed out:

• Effective and scheduled time of transmission. Messages are forwarded with a delay shorter or equal to their scheduled time, given the fact that all pending transmissions are performed together when the jitter of any pending message expires. The gap between scheduled delay and effective delay depends on the arrival rate of packets with messages to be forwarded. are sent immediately also contributes to the gap between scheduled and effective delays. Self-generated message rate, packet reception rate and jitter value bounds (M AXJIT T ER) are therefore factors that impact the effective delay of forwarded messages. If the selfgenerated message rate increases significantly, it may become the dominating factor and render irrelevant changes in the interval for jitter values. • Impact on packet rate. Since forwarded packets may contain messages from one or more received packets, the use of jittering techniques leads to a reduction in the rate of flooded packets -even in cases where an interface forwards all the message it receives. In particular, a wireless interface sends packets at a lower rate than it receives packets to be forwarded. This is, however, at the expense of increasing the size of the forwarded packets, as they contain a growing number of messages. The analysis presented in this paper evaluates the impact of the above three elements by way of a probabilistic theoretical model.

III. SYSTEM MODEL

This section describes the main parameters and assumptions under which the jitter mechanism is evaluated. Section III-A defines the scope of this model and the variables used to parametrize operation of the jitter mechanism. Section III-B presents the types of traffic considered in the model and describes the assumptions over them.

A. Model Scope and Parameters

The model presented in this section examines the use of the jitter mechanism in a particular wireless router (denoted throughout this paper as a node) attached to a network, that participates in the flooding of traffic from other nodes and also generates traffic to be flooded over the network. It is assumed that all nodes in the network have the same configuration of the jitter mechanism. That implies that jitter values, denoted by t throughout this paper , are selected within the same interval [0, J m ] and with the same distribution, where J m is the maximum value for the jitter (denominated M AXJIT T ER in RFC 5148 [START_REF] Clausen | RFC5148, Jitter Considerations in Mobile Ad Hoc Networks[END_REF]).

B. Traffic Model and Assumptions

Nodes participate in flooding by generating, receiving and forwarding messages. These messages are sent through the network in packets, each packet containing one or more messages.

Three types of traffic are distinguished:

• traffic received by the node to be forwarded (in-traffic),

• traffic generated by the node (self-traffic), and

• traffic sent by the node (out-traffic).

There may be an additional type of traffic: traffic received by the node, but not forwarded. For the purposes of this paper , this non-forwarded traffic is not relevant, and is thus not considered. For convenience, it will be therefore considered that all packets received are to be forwarded. Table I displays the variables used for describing the traffic rates in terms of messages per second (γ) and packets per second (λ), and Figure 3 illustrates the traffic model for a particular node.

R λ in , γ in λ g , γ g λ out , γ out

IV. ANALYSIS

This section presents the theoretical results of the analysis based on the previously presented jitter model. Results are presented for a general distribution of the random variable for jitter values, T j , and then particularized for the case of uniform distribution, specified in RFC 5148, i.e.:

f Tj (t) = 1 [0,Jm ] (t) Jm F Tj (t) = t Jm 1 [0,Jm] (t) + 1 (Jm,+∞) (t) (1)
Section IV-A indicates the relationship between the different types of considered traffic, both in terms of messages and packets. The analysis focuses on the collecting phase of a node, which can be defined as follows:

• The collecting phase of a node using jitter for flooding over an ad hoc network is the period between the first in-packet arrival after an out-packet transmission, and the following out-packet transmission. Duration of this length is bounded by the jitter value assigned to such first inpacket. Section IV-B analyzes the average length of the collecting phase, denoted by D(t), where t is the jitter value assigned to in-packet triggering the phase. Figure 4 illustrates the notion of collecting phase in a node reception/transmission timeline.

Out ={0,1,2} In-0 time In-2 Tj1 Tj2
In-1

Tx Rx Rx Rx Tx
Collecting phase triggered by In-0 Delay (jitter) t assigned to In-0 The average number of packets received during the collecting phase, as well as the impact of jitter in out-packet size, are studied in section IV-C. Based on these results, section IV-D describes the out-packet rate, λ out , in function of the inpacket and the self-packet rates, and checks its consistency by examining its asymptotic behavior when one of the two input traffic components (in-traffic and self-traffic) dominates the other. Finally, section IV-E presents and describes the notion of cumulated delay of in-packets of a collecting phase, and computes the average delay for an in-packet, depending on the jitter interval. Some proofs have been sketched or are skipped due to the lack of space; complete proofs can be found in [START_REF] Cordero | RR 7701, A Theoretical Model for Analyzing the Impact of Jitter-based Techniques on Flooding over Wireless Ad Hoc Networks[END_REF].

A. Message and Packet Rates

This section describes the relationship between message and packet rates received and sent by a node. Every message that a node sends to the network (out-message) has been either received to be forwarded (in-message), or created by the node to describe its own topology (self-message). Therefore, message rates satisfy the following relationship:

γ out = γ in + γ g (2)
Packets contain one or more messages. For consistency, it is assumed that a self-generated packet contains one and only one self-generated message, that is:

λ g = γ g (3)
The relationship among packet rates (λ out , λ in , λ g ) depends on the jitter mechanism. In-messages may be forwarded by way of (a) out-packets that contain only other in-messages, or (b) out-packets that contain one (and only one) self-generated message. The rate of out-packets in case (b) is then exactly λ g . Out-packets in case (a) correspond to in-packets for which no self-traffic is generated while waiting for transmission. As outpackets in case (a) contain the messages from all the in-packets received, but not yet forwarded, the rate of out-packets in case (a) is significantly lower than the in-packet rate. If M (t) denotes the average number of in-and self-packets whose messages are included in an out-packet, the out-packet rate can be expressed as follows:

λ out = λ in + λ g E t {M (t)} (4)
Note that, as M (t) ≥ 1, the out-packet rate is always smaller than the addition of in-packet and self-packet rates. Consequently, the average number of messages per out-packet (and thus the out-packet size) increases with respect to the number of messages per in-packet. This measure of the variation in packet size can be computed as follows:

γ out /λ out γ in /λ in = (γ in + γ g )/(λ in + λ g )E t {M (t)} γ in /λ in = = (γ in + λ g )/(λ in + λ g ) γ in /λ in E t {M (t)} (5)
If self-packet rate is significantly lower than in-packet rate (λ g ≪ λ in ), then:

γ out /λ out γ in /λ in ≈ E t {M (t)} (6)
Random variable M (t) and its mean E t {M (t)} are computed and examined in detail in section IV-C.

B. Average Duration of the Collecting Phase

This section studies the relationship between jitter values and length of collecting phases. Intuitively, the collecting phase is longer as the jitter value of the triggering inpacket increases, and gets shorter as the in-packet and selfpacket rates (λ in and λ g , respectively) increase. Theorem 1 describes rigurously the average duration of the collecting phase triggered by an in-packet arrival, denoted as D(t), and its dependency on the jitter value t that such in-packet is assigned, the maximum jitter value, J m and the traffic rates.

Theorem 1. Let D(t) be the average duration of the accumulating phase, with t ∈ [0, J m ] being the scheduled time of retransmission of such first in-packet and J m being the maximum jitter value. Then, D(t) satisfies the following ODE:

D"(t) = (-λ in F Tj (t) -λ g )D ′ (t) (7)
Proof: Given a scheduled jitter value t for the first inpacket, the effect of events happening in dt in the average duration D is examined. For sufficiently small values of dt, only one Poisson event (an in-packet arrival, with rate λ in ; or a self-generated packet, with rate λ g ) may occur. An inpacket arrival at dt (with probability λ in dt) may modify the duration D(t) if the scheduled jitter T j of the arrived packet is lower than the scheduled time of retransmission t; a self-generated packet arrival within at dt (with probability λ g dt) implies that the duration D(t) becomes equivalent to the duration of the phase for a scheduled time dt. When no in-or self-packets arrive at dt, duration D(t) is equivalent to the duration obtained by waiting a dt interval and then scheduling retransmission after an interval t -dt. This is described formally in the following transition equation:

D(t) = λ in dt P (T j > t)D(t) + t 0 f Tj (x)D(x)dx + +λ g dtD(dt) + (1 -(λ in + λ g )dt)(D(t -dt) + dt) Then, D(t) -D(t -dt) = λ in dt (P (T j > t)D(t)+ + t 0 f Tj (x)D(x)dx + +λ g dtD(dt) - -(λ in + λ g )dt(D(t -dt) + dt)
Dividing over dt and for dt -→ 0, taking into account that D(dt -→ 0) -→ 0 by definition of D, the following differential equation arises:

D ′ (t) = λ in P (T j > t)D(t) + t 0 f Tj (x)D(x)dx - -(λ in + λ g )D(t) + 1 = = λ in -F Tj (t)D(t) + t 0 f Tj (x)D(x)dx - -λ g D(t) + 1 As F X (t) = t 0 f X (x)dx, D ′ (t) = λ in t 0 f Tj (x)(D(x) -D(t))dx -λ g D(t) + 1
Differentiating this expression over t:

D"(t) = d dt λ in t 0 f Tj (x)(D(x) -D(t))dx -λ g D ′ (t) (8)
Where the derivative in brackets, denoted I 1 , can be calculated as follows:

I 1 = d dt λ in t 0 f Tj (x)(D(x) -D(t))dx = = λ in f Tj (t)D(t) -λ in d dt D(t)F Tj (t) = = λ in f Tj (t)D(t) -λ in D ′ (t)F Tj (t) -λ in D(t)f Tj (t) = = -λ in D ′ (t)F Tj (t)
Then, replacing I 1 in equation ( 8) leads to the ordinary differential equation (ODE) of order 2:

D"(t) = (-λ in F Tj (t) -λ g )D ′ (t) (9)
Corollary. If jitter values are distributed uniformly within [0, J m ], according to [START_REF] Cordero | RR 7701, A Theoretical Model for Analyzing the Impact of Jitter-based Techniques on Flooding over Wireless Ad Hoc Networks[END_REF], the differential equation ( 7) has the following solution for D(t):

D(t) = 2J m λ in e - λ 2 g 2λ in Jm q Jm 2λ in " λg+ λ in t Jm " q Jm 2λ in λg e -s 2 ds (10)
Proof: The result is immediate by imposing initial conditions D(0) = 0, D ′ (0) = 1 and assuming an uniform distribution for jitter values within [0, J m ].

C. Arrivals during the Collecting Phase and Packet Size

An out-packet sent at the completion of a collecting phase contains the messages included in the in-packet that triggered the phase, and the messages included in the in-packets arrived within the phase. In case that a self-packet is generated within the collecting phase, that terminates the phase and causes the transmission of the corresponding out-packet. Theorem 2 proves that the average number of in-and self-packets included in an out-packet follows the Poisson law.

Theorem 2. Let M (t) be the average number of packets whose messages are transmitted together after the completion of a collecting phase started by an in-packet with initial jitter t ∈ [0, J m Then, the expression of M (t) is as follows:

M (t) = 1 + (λ in + λ g )D(t) (11)
Proof: When an in-packet, with initial jitter t, arrives to an interface and starts a collecting phase, the number of packets whose messages are sent together in the next transmission of such interface is:

M (t) = 1 + N (t)
Where N (t) corresponds to the number of packets (inand self-packets) arrived to the interface during the collecting phase -not including the in-packet that started such phase. For sufficiently small values of dt, the arrival of a self-generated message in dt implies that the out-packet is immediately sent, with only such self-message and the messages from the starting in-packet. In case that an in-packet arrives during dt, the number of packets included in the transmitted out-packet is incremented by one. The transition equation for N (t) is therefore as follows:

N (t + dt) = λ g dt + λ in dt (P (T j > t)(N (t) + 1)+ + t 0 f Tj (x)(N (x) + 1)dx + +(1 -(λ g + λ in )dt)N (t)
Which leads to the following ODE:

N ′ (t) = λ g + λ in 1 + (1 -F Tj (t))N (t)+ + t 0 f Tj N (x)dx -(λ g + λ in )N (t) Differentiating over t: N "(t) = -(λ g + λ in F Tj (t))N ′ (t)
Which is the same ODE as [START_REF]RFC 5340, OSPF for IPv6[END_REF]. Assuming the following initial conditions:

N (0) = 0 N ′ (0) = λ in + λ g
The solution is therefore:

N (t) = (λ in + λ g )D(t)
Random variable N (t) = (λ in + λ g )D(t), introduced in the proof of Theorem 2, computes the number of self-and in-packets arrived during the collecting phase (excluding the in-packet that triggers the phase). Similarly, the number of in-packets can be computed as:

N i (t) = λ in D(t) (12)
Proposition 3 provides the expression of the mean of random variable M (t) for uniform jitter, which comes immediately from the definition of mean and from [START_REF] Chung | Jitter Analysis of Homogeneous Traffic in Wireless Differentiated Services Networks[END_REF]. Proposition 3. In the conditions of Theorem 2, and with a uniformly distributed jitter within [0, J m ], the mean of M (t) w.r.t. the jitter value is as follows:

E t {M (t)} = C 2 C 1 (λ in + λ g ) 2 × × 2 √ π q Jm 2λ in (λin+λg) q Jm 2λ in λg e -s 2 ds + 2λ 3 2 in + +2λ g λ 1 2 in 1 -e Jm 2 (λin+2λg) (13)
Where C 1 and C 2 are defined as follows:

C 1 = 2πJ m e Jm 2 (λ in +λg ) 2 λ in (14)
C 2 = 1 2λ 3 2 in e -Jm 2 (λin+2λg) (15)
The result from Proposition 3 allows to estimate the size increase of out-packets w.r.t. in-packets caused by jitter, as detailed in section IV-A (eq. ( 6)), for the case that in-traffic dominates self-traffic (λ in ≫ λ g ). Figure 5 shows the evolution of E t {M (t)} depending on λ in , for different values of λ g and J m = 1sec.

Self-generated packets cause immediate transmission of outpackets. Therefore, increasing the self-packet rate reduces the duration of collecting phase in a greater extent than increasing the in-packet rate. It can be observed in Figure 5 that selfpacket rate increase in λ g causes a size growth of out-packets only for low values of λ in (λ in ≤ 4 pkt sec in the figure). For moderate and high values of λ in , increases in self-packet rate lead to smaller out-packets. This is due to the fact that arriving self-generated packets are likely to cause an outpacket transmission before the arrival of in-packets that would have been otherwise included in the transmitted out-packet.

D. Out-Packet Rate and Asymptotic Behavior

Proposition 3 completes the characterization of the outpacket rate, λ out , defined in [START_REF] Qayyum | Multipoint Relaying for Flooding Broadcast Messages in Mobile Wireless Networks[END_REF]. The out-packet rate can be computed as follows:

λ out = λ in + λ g E t {M (t)} = = λ in + λ g 1 + E t {N (t)} (16)
Figure 6 illustrates the evolution of the out-packet rate, λ out , with respect to the in-and self-packet rates (λ in and λ g ), for a constant value of J m = 1sec. Proposition 4 explores the asymptotic behavior of the out-packet rate in case of intraffic and self-traffic dominance (λ in → 0 and λ g → 0, respectively), as well as its compatibility with the no-jitter behavior (J m → 0).

lim λg→0 λ out = λ in 1 + λ in E t {D(t)} λg=0 lim λin→0 λ out = λ g lim Jm→0 λ out = λ in + λ g Proof:
• λ g → 0 and J m → 0 are immediate from the definition.

• λ in -→ 0: Consider M (t) = 1 + N (t), as defined in [START_REF] Chung | Jitter Analysis of Homogeneous Traffic in Wireless Differentiated Services Networks[END_REF]. Then, lim λin→0 M (t) can be computed as follows.

M (t) = 1 + (λ in + λ g ) πJ m 2λ in 2 √ π × × q Jm 2λ in " λ in t Jm +λg " q Jm 2λ in λg e -s 2 ds ≈ ≈ 1 + (λ in + λ g ) πJ m 2λ in 2 √ π × e -Jm 2λ in " λ in t Jm +λg " 2 -e -Jm 2λ in λ 2 g λ in t J m
Therefore:

lim λin→0 M (t) = 1 + 0 = 1
Which is a non-zero value that does not depend on t; lim λin→0 λ out can be therefore computed as the quotient of numerator and denominator limits, as follows:

lim λin→0 λ out = lim λin→0 λ in + λ g E t {M (t)} = λ g
The results of Proposition 4 are consistent with the intuitive behavior of jitter. When jitter is not used, the out-packet rate corresponds to the addition of in-and self-packet rates. When self-traffic dominates over in-traffic (λ g ≫ λ in , that is, λ in → 0), the out-packet rate follows the self-packet rate, as self-generated packets cause immediate transmissions. In the inverse case, when self-traffic is negligible w.r.t. in-traffic (λ g ≪ λ in , that is, λ g → 0), the jitter mechanism reduces the packet rate in a ratio that corresponds to the number of inpackets received during a collecting phase (1 + λ in E t {D(t)}).

E. Average Forwarding Delay for In-Packets

This section addresses the average delay that an in-packet experiences, given a jitter configuration (defined by uniform distribution of assigned jitter values within [0, J m ]). Three steps are performed in order to characterize such delay. Theorem 5 describes the cumulated delay of a collecting phase, G(t), depending on the jitter value assigned to the triggering in-packet, t. The cumulated delay is the addition of the delays experienced by all in-packets (include the triggering in-packet) that arrive within the collecting phase. The result is then particularized for the case of uniform jitter. Based on this result, Theorem 6 computes the average delay for in-packets; and this is particularized in the Corollary for uniform jitter.

Theorem 5. Let G(t) be the average cumulated delay in a collecting phase. Then, for an uniformly distributed jitter (T j ∼ U nif orm[0, J m ]), the expression of G(t) is as follows:

G(t) = D(t) + F (t) (17)
Where D(t) is defined in [START_REF] Clausen | RFC5148, Jitter Considerations in Mobile Ad Hoc Networks[END_REF] and F (t) satisfies the following ODE:

F ′ (t) = λ in D ′ (t) t 0 1 -F Tj (x) dx (18)
Proof: Let F (t) be the cumulated delay not corresponding to the one from the in-packet that triggers the collecting phase, i.e. F (t) is defined as F (t) = G(t) -D(t). By restricting the time interval to a sufficiently small value of dt (as in proofs for Theorems 1 and 2), the arrival of a self-generated message implies that there is no additional delay. In case that an inpacket arrives, the additional delay corresponds to the total cumulated delay of such in-packet, G(x) if the assigned jitter x for such packet is smaller than t, and G(t) otherwise. The transition equation for F (t) is therefore as follows:

F (t + dt) = λ in dt (P (T j > t)G(t)+ + t 0 P (T j = x)G(x)dx + +λ g dt0 + (1 -(λ in + λ g )dt)F (t)
When dt → 0:

F ′ (t) = λ in (P (T j > t)(G(t) -F (t))+ + t 0 P (T j = x)(G(x) -F (t))dx - -λ g F (t)
Recalling that G(t) -F (t) = D(t), and derivating again over t:

F "(t) = λ in (1 -F Tj (t))D ′ (t) -(λ in F Tj (t) + λ g )F ′ (t)
Multiplying by D ′ (t) on both sides:

F "(t)D ′ (t) = λ in (1 -F Tj (t))(D ′ (t)) 2 - -(λ in F Tj (t) + λ g )F ′ (t)D ′ (t)
Developing and applying the initial condition F ′ (0) = 0:

F ′ (t) = λ in D ′ (t) t 0 1 -F Tj (x) dx
Corollary. If jitter values are distributed uniformly within [0, J m ], according to [START_REF] Cordero | RR 7701, A Theoretical Model for Analyzing the Impact of Jitter-based Techniques on Flooding over Wireless Ad Hoc Networks[END_REF], the differential equation ( 18) has the following solution for F (t):

F (t) = e Jm 2 λ 2 g λ in J 3 2 m √ λ in 2 π q Jm 2λ in λg+ q λ in 2Jm t q Jm 2λ in λg e -s 2 ds × × λ g - √ π 2 + λ 2 g λ in + t 2 e -λ in t 2 2Jm -λgt - - J m 2 1 -e -λ in t 2 2Jm -λgt λ g λ in + 2 (19)
Proof: Applying the CDF of T j in (18) leads to:

F ′ (t) = λ in D ′ (t) t 0 1 - x J m dx = λ in t 1 - t 2J m D ′ (t)
The result then comes from solving this equation with I.C. F (0) = 0.

The average forwarding delay for an in-packet can be computed by using results obtained in previous sections. Theorem 6 describes the average forwarding delay for inpackets received within a collecting phase with jitter value t. Theorem 6. The average delay between reception and retransmission for a message contained in an in-packet has the expression that follows:

T tx = Jm 0 f Tj (t) D(t) + F (t) 1 + λ in D(t) dt (20)
Proof: Within a collecting phase with jitter value t, the average cumulated delay of in-packets is G(t). From [START_REF] Daniel | An Inter-arrival Delay Jitter Model using Multi-Structure Network Delay Characteristics for Packet Networks[END_REF], the average number of received in-packets is N i (t) = λ in D(t). Therefore:

T tx (t) = G(t) 1 + N i (t) = D(t) + F (t) 1 + λ in D(t)
Averaging over all possible jitter values for the collecting phase:

T tx = E t {T tx (t)} = Jm 0 f Tj (t) D(t) + F (t) 1 + λ in D(t) dt
Corollary. If jitter values are distributed uniformly, the average delay between reception and retransmission for a message contained in an in-packet is as follows:

T tx = 1 J m Jm 0 D(t) + F (t) 1 + λ in D(t) dt (21)
V. DISCUSSION

The above section analyzes the benefit of using of jitter in terms of packet transmission rate reduction. This has been modeled by studying the out-packet rate λ out and its relationship with variables λ in (in-packet rate) and λ g (self-generated packet rate), for a uniformly distributed jitter selected within [0, J m ]. The expression of λ out ≡ λ out (λ in , λ g )| Jm is detailed in equation [START_REF] Qayyum | Multipoint Relaying for Flooding Broadcast Messages in Mobile Wireless Networks[END_REF]. For the parameters chosen for representation in Figures 5 and6 (λ in = 4pkt/sec, J m = 1sec) and λ g = 0.2pkt/sec, for instance, the out-packet rate is λ o ut = 1.66pkt/sec, which implies a packet rate reduction (w.r.t. in-packet rate) of 60%. For a more realistic value of J m = 100msec, the out-packet rate becomes λ out = 3.49pkt/sec, still a significant reduction in the number of transmissions. Less transmissions are indeed very desirable in wireless ad hoc networks, where bandwidth scarcity and hard energy constraints are common.

However, this benefit comes at the cost of additional delay. This delay is accumulated while packets are buffered and waiting for the next backed-off transmission that is scheduled. When an in-packet is received by an interface using jitter, messages contained in the packet are forwarded after a random delay. If such in-packet triggers a new collecting phase, then the time lapse before forwarding corresponds to the length of the collecting phase, for which the average in function of the jitter value t, D(t), is described in equation [START_REF] Clausen | RFC5148, Jitter Considerations in Mobile Ad Hoc Networks[END_REF]. The length of the collecting phase is the upper bound or worst case for the random delay that an in-packet may experience. The average delay for in-packets, given a maximum jitter value J m , is explored in equation [START_REF] Fulton | Delay Jitter First-Order and Second-Order Statistical Functions of General Traffic on High-Speed Multimedia Networks[END_REF]. Even with a large jitter interval, as in the previous example (λ in = 4pkt/sec, λ g = 0.2pkt/sec, J m = 1sec), and from eq. ( 21), such average delay is T tx = 0.24sec; for the maximum jitter value J m = 0.1sec, T tx = 0.04sec. These delays can be thus scaled into acceptable values with the jitter range. Based on the results presented in section IV, Figure 7 displays the plot of the average of the collecting phase length, D(T ), and the average delay for an in-packet, E t {T tx (t)} for an interface with inpacket traffic rate λ in = 4 pkts sec and self-packet traffic rate λ g = 0.2 pkts sec , where T is the average jitter value, distributed uniformly within [0, J m ] with J m = 2T .

Moreover, the benefit of reduced out-packet transmission rate comes also at the cost of longer transmissions (outpackets), as shown in eqs. ( 5), ( 6) and [START_REF] Chung | Jitter Analysis of Homogeneous Traffic in Wireless Differentiated Services Networks[END_REF]. In practice, IETF standardization activity indicates that jitter is used at the network layer, generally above a link layer using CSMA based mechanisms (typically 802.11). The effect of longer packets with CSMA has been studied in various prior work including in [START_REF] Lettieri | Adaptive Frame Length Control for Improving Wireless Link Throughput, Range, and Energy Efficiency[END_REF], where it is shown that if L is the length of packets and B the bit error rate, the achieved throughput G is:

L L + 1 (1 -B) L+1 (22)
Since the bit error rate is generally substantial in wireless ad hoc networks, this means that there is an optimum packet length, above which the throughput decreases. Therefore, the maximum jitter value J m should be chosen so that packet size does not increase beyond the CSMA optimum, in which case the throughput would in fact decrease because of the link layer. In that respect, the choice of an appropriate J m (with respect to out-packet size variation) also depends on λ in and λ g , as shown in Proposition 3.

VI. SIMULATIONS

This section presents simulation results that focus on the two main results obtained in section IV: the delay introduced by jitter in packet forwarding (both the average length of the collecting phase and the average delay between in-packet reception and forwarding), and the relationship between outpacket traffic rate, self-packet traffic rate and in-packet traffic rate when jittering techniques are used. For a better visualization of the impact of the jitter range, each aspect is measured for collecting phases with jitter values T = Jm 2 , for different maximum values of the jitter, J m . Results are presented for a range 0 ≤ T ≤ 0.5sec, or equivalently, 0 ≤ J m ≤ 1sec, and directly compared with the corresponding analytical results that were derived in section IV. The simulations were carried out in Maple and the presented results are averaged over 30 iterations per value. 95% confidence intervals are indicated in the figures. Figure 7 presents the average delay for an in-packet, T tx (T ), the average duration D(T ) of the collecting phase (which corresponds to the delay for the triggering in-packet of the phase), together with the averaged results from the simulations. It can be observed that the obtained analytical results are consistent with the simulation results. This suggests that, with the simulated values, the transmission time of in-messages is frequently determined by the jitter values assigned to inmessages previously arrived, and the event that an in-packet arrival follows an out-packet transmission is rare. The probability of such event may increase when in-packet traffic rate decreases, thus approaching the measures of average in-packet delay, T tx (T ), to the length of the collecting phase, D(T ). Figure 8 displays the in-packet and out-packet rates obtained in simulations for different values of T , with a nominal inpacket rate of λ in = 4 pkts sec and self-packet rate of λ g = 0.2 pkts sec . Simulations are compared with the out-packet rate provided by the theoretical model via expression [START_REF] Qayyum | Multipoint Relaying for Flooding Broadcast Messages in Mobile Wireless Networks[END_REF]. It can be observed that the out-packet rate for T = 0 corresponds to λ in + λ g = 4 + 0.2 pkts sec = 4.2 pkts sec . For non-zero average values of jitter, the out-packet rate decreases significantly as T grows. The slope of this decrease becomes lower (in absolute terms) as T value is higher. Although the range of simulated t is not long enough, the observed evolution is consistent with the horizontal asymptote at λ out = λ g = 0.2 pkts sec , described in Proposition 4.

VII. CONCLUSION

Recurrent network-wide packet dissemination may lead to systematic wireless collisions when performed over wireless multi-hop ad hoc networks. Jittering, a distributed technique based on the schedule of random backed-off transmissions, aims at avoiding such transmissions bound to be synchronized otherwise. Jittering is moreover used to aggregate several packets (those received and buffered while waiting for the next backed-off transmission that has been scheduled) into a single transmission. Reducing the number of transmissions and the number of concurrent transmissions is very desirable in wireless ad hoc networks, where bandwidth is scarce, and energy supply often limited. However, the benefits of jitter come at the price of additional delays, and longer transmissions. This paper introduced a model and analysis of standard jittering as specified by the IETF, and derived results on three key aspects: (i) incurred additional delays, (ii) increase in packet size and (iii) reduction in the number of transmissions. This paper also presented an analysis of the use of jitter in practice, in conjunction with CSMA, the mechanism on which is based most current link layer technologies, such as 802.11. The analytical results are then validated via simulations. This paper thus provides a rather comprehensive analysis of the impact of standard jittering in today's wireless ad hoc networks. Future work will aim at extending the model to consider noninstantaneous packet transmissions, as well as a network-based approach (instead of the interface-based approach used so far) which may capture finer network-wide behavior.

Figure 1 .

 1 Figure 1. Wireless collision caused by concurrent flooding retransmissions. The forwarding of a flooded packet (#1) by router A, received by B and C, causes simultaneous transmissions by routers B and C (#2 and #3), to forward the flooded packet, which cause a wireless collision.

Figure 3 .

 3 Figure 3. Node model.

Figure 4 .

 4 Figure 4. Collecting phase of a node participating in flooding.

Figure 5 .

 5 Figure 5. Mean of M (t) (w.r.t. t) depending on λ in , for different values of λg, Jm = 1sec.

Figure 6 .Proposition 4 .

 64 Figure 6. λout(λ in , λg), for Jm = 0.5sec.

Figure 7 .

 7 Figure 7. Average time to transmission for λ in = 4 pkt s , λg = 0.2 pkt s , for different values of t (simulations and analytical results).

Figure 8 .

 8 Figure 8. Out-packet (λout) and in-packet (λ in ) rates, for different values of T , and a theoretical in-packet rate λ in = 4 pkt s (simulations and analytical results).