Vincent Delaitre

Josef Sivic

Ivan Laptev

Learning person-object interactions for action recognition in still images

We investigate a discriminatively trained model of person-object interactions for recognizing common human actions in still images. We build on the locally order-less spatial pyramid bag-of-features model, which was shown to perform extremely well on a range of object, scene and human action recognition tasks. We introduce three principal contributions. First, we replace the standard quantized local HOG/SIFT features with stronger discriminatively trained body part and object detectors. Second, we introduce new person-object interaction features based on spatial co-occurrences of individual body parts and objects. Third, we address the combinatorial problem of a large number of possible interaction pairs and propose a discriminative selection procedure using a linear support vector machine (SVM) with a sparsity inducing regularizer. Learning of action-specific body part and object interactions bypasses the difficult problem of estimating the complete human body pose configuration. Benefits of the proposed model are shown on human action recognition in consumer photographs, outperforming the strong bag-of-features baseline.

Introduction

Human actions are ubiquitous and represent essential information for understanding the content of many still images such as consumer photographs, news images, sparsely sampled surveillance videos, and street-side imagery. Automatic recognition of human actions and interactions, however, remains a very challenging problem. The key difficulty stems from the fact that the imaged appearance of a person performing a particular action can vary significantly due to many factors such as camera viewpoint, person's clothing, occlusions, variation of body pose, object appearance and the layout of the scene. In addition, motion cues often used to disambiguate actions in video [START_REF] Bobick | The recognition of human movement using temporal templates[END_REF][START_REF] Laptev | Learning realistic human actions from movies[END_REF][START_REF] Moeslund | A survey of advances in vision-based human motion capture and analysis[END_REF] are not available in still images.

In this work, we seek to recognize common human actions, such as "walking", "running" or "reading a book" in challenging realistic images. As opposed to action recognition in video [START_REF] Bobick | The recognition of human movement using temporal templates[END_REF][START_REF] Laptev | Learning realistic human actions from movies[END_REF][START_REF] Moeslund | A survey of advances in vision-based human motion capture and analysis[END_REF], action recognition in still images has received relatively little attention. A number of previous works [START_REF] Gupta | Observing human-object interactions: Using spatial and functional compatibility for recognition[END_REF][START_REF] Ikizler | Recognizing actions from still images[END_REF][START_REF] Wang | Unsupervised discovery of action classes[END_REF] focus on exploiting body pose as a cue for action recognition. In particular, several methods address joint modeling of human poses, objects and relations among them [START_REF] Gupta | Observing human-object interactions: Using spatial and functional compatibility for recognition[END_REF][START_REF] Yao | Modeling mutual context of object and human pose in human-object interaction activities[END_REF]. Reliable estimation of body configurations for people in arbitrary poses, however, remains a very challenging research problem. Less structured representations, e.g. [START_REF] Delaitre | Recognizing human actions in still images: a study of bagof-features and part-based representations[END_REF][START_REF] Yao | Grouplet: A structured image representation for recognizing human and object interactions[END_REF] have recently emerged as a promising alternative demonstrating state-of-the-art results for action recognition in static images.

In this work, we investigate discriminatively trained models of interactions between objects and human body parts. We build on the locally orderless statistical representations based on spatial pyramids [START_REF] Lazebnik | Beyond bags of features: spatial pyramid matching for recognizing natural scene categories[END_REF] and bag-of-features models [START_REF] Csurka | Visual categorization with bags of keypoints[END_REF][START_REF] Fei-Fei | A Bayesian hierarchical model for learning natural scene categories[END_REF][START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF], which have demonstrated excellent performance on a range of scene [START_REF] Lazebnik | Beyond bags of features: spatial pyramid matching for recognizing natural scene categories[END_REF], object [START_REF] Harzallah | Combining efficient object localization and image classification[END_REF][START_REF] Vedaldi | Multiple kernels for object detection[END_REF][START_REF] Zhang | Local features and kernels for classification of texture and object categories: a comprehensive study[END_REF] and action [START_REF] Delaitre | Recognizing human actions in still images: a study of bagof-features and part-based representations[END_REF] recognition tasks. Rather than relying on accurate estimation of body part configurations or accurate object detection in the image, we represent human actions as locally orderless distributions over body parts and objects together with their interactions. By opportunistically learning class-specific object and body part interactions (e.g. relative configuration of leg and horse detections for the riding horse action, see Figure 1), we avoid the extremely challenging task of estimating the full body configuration. Towards this goal, we consider the following challenges: (i) what should be the representation of object and body part appearance; (ii) how to model object and human body part interactions; and (iii) how to choose suitable interaction pairs in the huge space of all possible combinations and relative configurations of objects and body parts.

To address these challenges, we introduce the following three contributions. First, we replace the quantized HOG/SIFT features, typically used in bag-of-features models [START_REF] Delaitre | Recognizing human actions in still images: a study of bagof-features and part-based representations[END_REF][START_REF] Lazebnik | Beyond bags of features: spatial pyramid matching for recognizing natural scene categories[END_REF][START_REF] Vedaldi | Multiple kernels for object detection[END_REF] with powerful, discriminatively trained, local object and human body part detectors [START_REF] Bourdev | Poselets: Body part detectors trained using 3D human pose annotations[END_REF][START_REF] Johnson | Learning effective human pose estimation from inaccurate annotation[END_REF]. This significantly enhances generalization over appearance variation, due to e.g. clothing or viewpoint while providing a reliable signal on part locations. Second, we develop a part interaction representation, capturing pair-wise relative position and scale between object/body parts, and include this representation in a scale-space spatial pyramid model. Third, rather than choosing interacting parts manually, we select them in a discriminative fashion. Suitable pair-wise interactions are first chosen from a large pool of hundreds of thousands of candidate interactions using a linear support vector machine (SVM) with a sparsity inducing regularizer. The selected interaction features are then input into a final, more computationally expensive, non-linear SVM classifier based on the locally orderless spatial pyramid representation.

Related work

Modeling person-object interactions for action recognition has recently attracted significant attention. Gupta et al. [START_REF] Gupta | Observing human-object interactions: Using spatial and functional compatibility for recognition[END_REF], Wang et al. [START_REF] Wang | Unsupervised discovery of action classes[END_REF], and Yao and Fei Fei [START_REF] Yao | Modeling mutual context of object and human pose in human-object interaction activities[END_REF] develop joint models of body pose configuration and object location within the image. While great progress has been made on estimating body pose configurations [START_REF] Andriluka | Pictorial structures revisited: People detection and articulated pose estimation[END_REF][START_REF] Ferrari | Pose search: retrieving people using their pose[END_REF][START_REF] Johnson | Learning effective human pose estimation from inaccurate annotation[END_REF][START_REF] Sapp | Cascaded models for articulated pose estimation[END_REF], inferring accurate human body pose in images of common actions in consumer photographs remains an extremely challenging problem due to a significant amount of occlusions, partial truncation by image boundaries or objects in the scene, non-upright poses, and large variability in camera viewpoint.

While we build on the recent body pose estimation work by using strong pose-specific body part models [START_REF] Bourdev | Poselets: Body part detectors trained using 3D human pose annotations[END_REF][START_REF] Johnson | Learning effective human pose estimation from inaccurate annotation[END_REF], we explicitly avoid inferring the complete body configuration. In a similar spirit, Desai et al. [START_REF] Desai | Discriminative models for static human-object interactions[END_REF] avoid inferring body configuration by representing a small set of body postures using single HOG templates and represent relative position of the entire person and an object using simple relations (e.g. above, to the left). They do not explicitly model body parts and their interactions with objects as we do in this work. Yang et al. [START_REF] Yang | Recognizing human actions from still images with latent poses[END_REF] model the body pose as a latent variable for action recognition. Differently to our method, however, they do not attempt to model interactions between people (their body parts) and objects. In a recent work, Maji et al. [START_REF] Maji | Action recognition from a distributed representation of pose and appearance[END_REF] also represent people by activation responses of body part detectors (rather than inferring the actual body pose), however, they model only interactions between person and object bounding boxes, not considering individual body parts, as we do in this work.

Learning spatial groupings of low-level (SIFT) features for recognizing person-object interactions has been explored by Yao and Fei Fei [39]. While we also learn spatial interactions, we build on powerful body part and object detectors pre-learnt on separate training data, providing a degree of generalization over appearance (e.g. clothing), viewpoint and illumination variation. Differently to [START_REF] Yao | Grouplet: A structured image representation for recognizing human and object interactions[END_REF], we deploy dicriminative selection of interactions using SVM with sparsity inducing regularizer.

Spatial-pyramid based bag-of-features models have demonstrated excellent performance on action recognition in still images [1,[START_REF] Delaitre | Recognizing human actions in still images: a study of bagof-features and part-based representations[END_REF] outperforming body pose based methods [START_REF] Gupta | Observing human-object interactions: Using spatial and functional compatibility for recognition[END_REF] or grouplet models [START_REF] Yao | Modeling mutual context of object and human pose in human-object interaction activities[END_REF] on their datasets [START_REF] Delaitre | Recognizing human actions in still images: a study of bagof-features and part-based representations[END_REF]. We build on these locally orderless representations but replace the low-level features (HOG) with strong pre-trained detectors. Similarly, the object-bank representation [START_REF] Li | Object bank: A high-level image representation for scene classification and semantic feature sparsification[END_REF], where natural scenes are represented by response vectors of densely applied pre-trained To get a strong interaction response, the pair of detectors (here visualized at positions p i and p j ) must fire in a particular relative 3D scale-space displacement (given by the vector v) with a scale-space displacement uncertainty (deformation cost) given by diagonal 3×3 covariance matrix C (the spatial part of C is visualized as a yellow dotted ellipse). Our image representation is defined by the max-pooling of interaction responses over the whole image, solved efficiently by the distance transform.

object detectors, has shown a great promise for scene recognition. The work in [START_REF] Li | Object bank: A high-level image representation for scene classification and semantic feature sparsification[END_REF], however, does not attempt to model people, body parts and their interactions with objects.

Related work also includes models of contextual spatial and co-occurrence relationships between objects [START_REF] Desai | Discriminative models for multi-class object layout[END_REF][START_REF] Rabinovich | Objects in context[END_REF] as well as objects and the scene [START_REF] Harzallah | Combining efficient object localization and image classification[END_REF][START_REF] Hoiem | Putting objects in perspective[END_REF][START_REF] Torralba | Contextual priming for object detection[END_REF]. Object part detectors trained from labelled data also form a key ingredient of attribute-based object representations [START_REF] Farhadi | Describing objects by their attributes[END_REF][START_REF] Lampert | Learning to detect unseen object classes by between-class attribute transfer[END_REF]. While we build on this body of work, these approaches do not model interactions of people and their body parts with objects and focus on object/scene recognition rather than recognition of human actions.

Representing person-object interactions

This section describes our image representation in terms of body parts, objects and interactions among them.

Representing body parts and objects

We assume to have a set of n available detectors d 1 , . . . , d n which have been pre-trained for different body parts and object classes. Each detector i produces a map of dense 3D responses d i (I, p) over locations and scales of a given image I. We express the positions of detections p in terms of scalespace coordinates p = (x, y, σ) where (x, y) corresponds to the spatial location and σ = log σ is an additive scale parameter log-related to the image scale factor σ making the addition in the position vector space meaningful.

In this paper we use two types of detectors. For objects we use LSVM detector [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] trained on PASCAL VOC images for ten object classes1 . For body parts we implement the method of [START_REF] Johnson | Learning effective human pose estimation from inaccurate annotation[END_REF] and train ten body part detectors2 for each of sixteen pose clusters giving 160 body part detectors in total (see [START_REF] Johnson | Learning effective human pose estimation from inaccurate annotation[END_REF] for further details). Both of our detectors use Histograms of Oriented Gradients (HOG) [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF] as an underlying low-level image representation.

Representing pairwise interactions

We define interactions by the pairs of detectors (d i , d j ) as well as by the spatial and scale relations among them. Each pair of detectors constitutes a two-node tree where the position and the scale of the leaf are related to the root by scale-space offset and a spatial deformation cost. More precisely, an interaction pair is defined by a quadruplet q = (i, j, v, C) ∈ N × N × R 3 × M 3,3 where i and j are the indices of the detectors at the root and leaf, v is the offset of the leaf relatively to the root and C is a 3 × 3 diagonal matrix defining the displacement cost of the leaf with respect to its expected position. Figure 1 illustrates an example of an interaction between a horse and the left thigh for the horse riding action.

We measure the response of the interaction q located at the root position p 1 by:

r(I, q, p 1 ) = max p2 d i (I, p 1 ) + d j (I, p 2 ) -u T Cu (1)
where u = p 2 -(p 1 + v) is the displacement vector corresponding to the drift of the leaf node with respect to its expected position (p 1 + v). Maximizing over p 2 in (1) provides localization of the leaf node with the optimal trade-off between the detector score and the displacement cost. For any interaction q we compute its responses for all pairs of node positions p 1 , p 2 . We do this efficiently in linear time with respect to p using distance transform [START_REF] Felzenszwalb | Distance transforms of sampled functions[END_REF].

Representing images by response vectors of pair-wise interactions

Given a set of M interaction pairs q 1 , • • • , q M , we wish to aggregate their responses (1), over an image region A. Here A can be (i) an (extended) person bounding box, as used for selecting discriminative interaction features (Section 4.2) or (ii) a cell of the scale-space pyramid representation, as used in the final non-linear classifier (Section 4.3). We define score s(I, q, A) of an interaction pair q within A of an image I by max-pooling, i.e. as the maximum response of the interaction pair within A:

s(I, q, A) = max p∈A r(I, q, p). (2)
An image region A is then represented by a M -vector of interaction pair scores z = (s 1 , • • • , s M ) with s i = s(I, q i , A).

(3)

Learning person-object interactions

Given object and body part interaction pairs q introduced in the previous section, we wish to use them for action classification in still images. A brute-force approach of analyzing all possible interactions, however, is computationally prohibitive since the space of all possible interactions is combinatorial in the number of detectors and scale-space relations among them. To address this problem, we aim in this paper to select a set of M action-specific interaction pairs q 1 , . . . , q M , which are both representative and discriminative for a given action class. Our learning procedure consists of the three main steps as follows. First, for each action we generate a large pool of candidate interactions, each comprising a pair of (body part / object) detectors and their relative scale-space displacement. This step is data-driven and selects candidate detection pairs which frequently occur for a particular action in a consistent relative scale-space configuration. Next, from this initial pool of candidate interactions we select a set of M discriminative interactions which best separate the particular action class from other classes in our training set. This is achieved using a linear Support Vector Machine (SVM) classifier with a sparsity inducing regularizer. Finally, the discriminative interactions are combined across classes and used as interaction features in our final non-linear spatial-pyramid like SVM classifier. The three steps are detailed below.

Generating a candidate pool of interaction pairs

To initialize our model, we first generate a large pool of candidate interactions in a data-driven manner. Following the suggestion in [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] that the accurate selection of the deformation cost C may not be that important, we set C to a reasonable fixed value for all pairs, and focus on finding clusters of frequently co-occurring detectors (d i , d j ) in specific relative configurations.

For each detector i and an image I, we first collect a set of positions of all positive detector responses

P I i = {p | d i (I, p) > 0}
, where d i (I, p) is the response of detector i at position p in image I. We then apply a standard non-maxima suppression (NMS) step to eliminate multiple responses of a detector in local image neighbourhoods and then limit P I i to the L top-scoring detections. The intuition behind this step is that a part/object interaction is not likely to occur many times in an image.

For each pair of detectors (d i , d j ) we then gather relative displacements between their detections from all the training images I k : D ij = k {p j -p i | p i ∈ P I k i and p j ∈ P I k j }. To discover potentially interesting interaction pairs, we perform a mean-shift clustering over D ij using a window of radius R ∈ R 3 (2D-image space and scale) equal to the inverse of the square root of the deformation cost: R = diag(C -1 2 ). We also discard clusters which contribute to less than η percent of the training images. The set of m resulting candidate pairs

(i, j, v 1 , C), • • • , (i, j, v m , C) is built from the centers v 1 , • • • , v m of
the remaining clusters. By applying this procedure to all pairs of detectors, we generate a large pool (hundreds of thousands) of potentially interesting candidate interactions.

Discriminative selection of interaction pairs

The initialization described above produces a large number of candidate interactions. Many of them, however, may not be informative resulting in unnecessary computational load at the training and classification times. For this reason we wish to select a smaller number of M discriminative interactions.

Given a set of N training images, each represented by an interaction response vector z i , described in eq. ( 3) where A is the extended person bounding box given for each image, and a binary label y i (in a 1-vs-all setup for each class), the learning problem for each action class can be formulated using the binary SVM cost function:

J(w, b) = λ N i=1 max{0, 1 -y i (w ⊤ z i + b)} + w 1 , (4)
where w, b are parameters of the classifier and λ is the weighting factor between the (hinge) loss on the training examples and the L 1 regularizer of the classifier.

By minimizing (4) in a one-versus-all setting for each action class we search (by binary search) for the value of the regularization parameter λ resulting in the sparse weight vector w with M nonzero elements. Selection of M interaction pairs corresponding to non-zero elements of w gives M most discriminative (according to (4)) interaction pairs per action class. Note that other discriminative feature selection strategies such as boosting [START_REF] Freund | A decision theoretic generalisation of online learning[END_REF] can be also used. However, the proposed approach is able to jointly search the entire set of candidate feature pairs by minimizing a convex cost given in (4), whereas boosting implements a greedy feature selection procedure, which may be sub-optimal.

Using interaction pairs for classification

Given a set of M discriminative interactions for each action class obtained as described above, we wish to train a final non-linear action classifier. We use spatial pyramid-like representation [START_REF] Lazebnik | Beyond bags of features: spatial pyramid matching for recognizing natural scene categories[END_REF], aggregating responses in each cell of the pyramid using max-pooling as described by eq. ( 2), where A is one cell of the spatial pyramid. We extend the standard 2D pyramid representation to scalespace resulting in a 3D pyramid with D = 1 + 2 3 + 4 3 = 73 cells. Using the scale-space pyramid with D cells, we represent each image by concatenating M features from each of the K classes into a M KD-dimensional vector. We train a non-linear SVM with RBF kernel and L 2 regularizer for each action class using a 5-fold cross-validation for the regularization and kernel band-width parameters. We found that using this final non-linear classifier consistently improves classification performance over the linear SVM given by equation (4). Note that feature selection (section 4.2) is necessary in this case as applying the non-linear spatial pyramid classifier on the entire pool of all candidate interactions would be computationally infeasible.

Experiments

We test our model on the Willow-action dataset downloaded from [4] and the PASCAL VOC 2010 action classification dataset [START_REF] Everingham | The pascal visual object classes (voc) challenge[END_REF]. The Willow-action dataset contains more than 900 images with more than 1100 labelled person detections from 7 human action classes: Implementation details: We use our implementation of body part detectors described in [START_REF] Johnson | Learning effective human pose estimation from inaccurate annotation[END_REF] with 16 pose clusters trained on the publicly available 2000 image database [3], and 10 pre-trained PAS-CAL 2007 Latent SVM object detectors [2]: bicycle, car, chair, cow, dining table, horse, motorbike, person, sofa, tvmonitor. In the human action training/test data, we extend each given person bounding box by 50% and resize the image so that the bounding box has a maximum size of 300 pixels. We run the detectors over the transformed bounding boxes and consider the image scales

s k = 2 k/10 for k ∈ {-10, • • • , 10}.
At each scale we extract the detector response every 4 pixels and 8 pixels for the body part and object detectors, respectively. The outputs of each detector are then normalized by subtracting the mean of maximum responses within the training bounding boxes and then normalizing the variance to 1. We generate the candidate interaction pairs by taking the mean-shift radius R = (30, 30, log(2)/2), L = 3 and η = 8%. The covariance of the pair deformation cost C is fixed in all experiments to R -2 . We select M = 310 discriminative interaction pairs to compute the final spatial pyramid representation of each image.

Results: Table 1 summarizes per-class action classification results (reported using average precision for each class) for the proposed method (d. Interactions), and three baselines. The first baseline (a. BOF) is the bag-of-features classifier [START_REF] Delaitre | Recognizing human actions in still images: a study of bagof-features and part-based representations[END_REF], aggregating quantized responses of densely sampled HOG features in spatial pyramid representation, using a (non-linear) intersection kernel. Note that this is a strong baseline, which was shown [START_REF] Delaitre | Recognizing human actions in still images: a study of bagof-features and part-based representations[END_REF] to outperform the recent person-object interaction models of [START_REF] Yao | Grouplet: A structured image representation for recognizing human and object interactions[END_REF] and [START_REF] Gupta | Observing human-object interactions: Using spatial and functional compatibility for recognition[END_REF] on their own datasets. The second baseline (b. LSVM) is the latent SVM classifier [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] trained in a 1-vs-all fashion for each class. To obtain a single classification score for each person bounding box, we take the maximum LSVM detection score from the detections overlapping the extended bounding box with the standard overlap score [START_REF] Everingham | The pascal visual object classes (voc) challenge[END_REF] higher than 0.5. The final baseline (c. Detectors) is a SVM classifier with an RBF kernel trained on max-pooled responses of the entire bank of body part and object detectors in a spatial pyramid representation but without interactions. This baseline is similar in spirit to the object bank representation [START_REF] Li | Object bank: A high-level image representation for scene classification and semantic feature sparsification[END_REF], but here targeted to action classification by including a bank of pose-specific body part detectors as well as object detectors. On average, the proposed method (d.) outperforms all baselines, obtaining the best result on 4 out of 7 classes. The largest improvements are obtained on Riding Bike and Horse actions, for which reliable object detectors are available. The improvement of the proposed method d. with respect to using the plain bank of object and body part detectors c. directly demonstrates the benefit of modeling interactions. Example detections of interaction pairs are shown in figure 2.

Table 2 shows the performance of the proposed interaction model (d. Interactions) and its combination with the baselines (e. BOF+LSVM+Inter.) on the Pascal VOC 2010 data. Interestingly, the proposed approach is complementary to both the BOF (51.25 mAP) and LSVM (44.08 mAP) methods and by combining all three approaches (following [START_REF] Delaitre | Recognizing human actions in still images: a study of bagof-features and part-based representations[END_REF]) the overall performance improves to 60.66 mAP. We also report results of the "Poselet" method [START_REF] Maji | Action recognition from a distributed representation of pose and appearance[END_REF], which, similar to our method, is trained from external non-Pascal data. Our combined approach achieves better overall performance and also outperforms the "Poselet" approach on 6 out of 9 classes. Finally, our combined approach also obtains competitive performance compared to the overall best reported result on the Pascal VOC 2010 data -"SURREY MK KDA" [1] -and outperforms this method on the "Riding Horse" and "Walking" classes.

Conclusion

We have developed person-object interaction features based on non-rigid relative scale-space displacement of pairs of body part and object detectors. Further, we have shown that such features can be learnt in a discriminative fashion and can improve action classification performance over a strong bag-of-features baseline in challenging realistic images of common human actions. In addition, the learnt interaction features in some cases correspond to visually meaningful configurations of body parts, and body parts with objects. In the examples shown, the interaction features capture either a body part and an object, or two body part interactions. Note that while these interaction pairs are found to be discriminative, due to the detection noise, they do not necessary localize the correct body parts in all images. However, they may still fire at consistent locations across many images as illustrated in the second row, where the head detector consistently detects the camera lens, and the thigh detector fires consistently at the edge of the head. Similarly, the leg detector seems to consistently fire on keyboards (see the third image in the first row for an example), thus improving the confidence of the computer detections for the "Interacting with computer" action. We use only a small set of object detectors available at [2], however, we are now in a position to include many more additional object (camera, computer, laptop) or texture (grass, road, trees) detectors, trained from additional datasets, such as ImageNet or LabelMe. Currently, we consider detections of entire objects, but the proposed model can be easily extended to represent interactions between body parts and parts of objects [START_REF] Brox | Object segmentation by alignment of poselet activations to image contours[END_REF].

Figure 1 :

 1 Figure1: Representing person-object interactions by pairs of body part (cyan) and object (blue) detectors. To get a strong interaction response, the pair of detectors (here visualized at positions p i and p j ) must fire in a particular relative 3D scale-space displacement (given by the vector v) with a scale-space displacement uncertainty (deformation cost) given by diagonal 3×3 covariance matrix C (the spatial part of C is visualized as a yellow dotted ellipse). Our image representation is defined by the max-pooling of interaction responses over the whole image, solved efficiently by the distance transform.

Figure 2 :

 2 Figure2: Example detections of discriminative interaction pairs. These body part interaction pairs are chosen as discriminative (high positive weight w i ) for action classes indicated on the left. In each row, the first three images show detections on the correct action class. The last image shows a high scoring detection on an incorrect action class. In the examples shown, the interaction features capture either a body part and an object, or two body part interactions. Note that while these interaction pairs are found to be discriminative, due to the detection noise, they do not necessary localize the correct body parts in all images. However, they may still fire at consistent locations across many images as illustrated in the second row, where the head detector consistently detects the camera lens, and the thigh detector fires consistently at the edge of the head. Similarly, the leg detector seems to consistently fire on keyboards (see the third image in the first row for an example), thus improving the confidence of the computer detections for the "Interacting with computer" action.

  Interaction with Computer, Photographing, Playing Music, Riding Bike, Riding Horse, Running and Walking. The training set contains 70 examples of each action class and the rest (at least 39 examples per class) is left for testing. The PASCAL VOC 2010 dataset contains the 7 above classes together with 2 other actions: Phoning and Reading. It contains a similar number of images. Each training and testing image in both datasets is annotated with the smallest bounding box containing each person and by the performed action(s). We follow the same experimental setup for both datasets.

Table 1 :

 1 Per-class average-precision for different methods on the Willow-actions dataset.

	Action / Method		a. BOF [11]	b. LSVM	c. Detectors	d. Interactions
	(1) Inter. w/ Comp.	58.15	30.21	45.64	56.60
	(2) Photographing		35.39	28.12	36.35	37.47
	(3) Playing Music		73.19	56.34	68.35	72.00
	(4) Riding Bike		82.43	68.70	86.69	90.39
	(5) Riding Horse		69.60	60.12	71.44	75.03
	(6) Running		44.53	51.99	57.65	59.73
	(7) Walking		54.18	55.97	57.68	57.64
	Average (mAP)		59.64	50.21	60.54	64.12
	Action / Method	d. Interactions	e. BOF+LSVM+Inter.	Poselets[30]	MK-KDA[1]
	(1) Phoning		42.11	48.61		49.6	52.6
	(2) Playing Instr.		30.78	53.07		43.2	53.5
	(3) Reading		28.70	28.56		27.7	35.9
	(4) Riding Bike		84.93	80.05		83.7	81.0
	(5) Riding Horse		89.61	90.67		89.4	89.3
	(6) Running		81.28	85.81		85.6	86.5
	(7) Taking Photo		26.89	33.53		31.0	32.8
	(8) Using Computer		52.31	56.10		59.1	59.2
	(9) Walking		70.12	69.56		67.9	68.6
	Average (mAP)		56.30	60.66		59.7	62.2

Table 2 :

 2 Per-class average-precision on the Pascal VOC 2010 action classification dataset.

The ten object detectors correspond to object classes bicycle, car, chair, cow, dining table, horse, motorbike, person, sofa, tv/monitor

The ten body part detectors correspond to head, torso, {left, right} × {forearm, upper arm, lower leg, thigh}

Acknowledgements. This work was partly supported by the Quaero, OSEO, MSR-INRIA, ANR DETECT (ANR-09-JCJC-0027-01) and the EIT-ICT labs.


Emna Salhi
email: emna.salhi@irisa.fr

Samer Lahoud
email: samer.lahoud@irisa.fr

Bernard Cousin
email: bernard.cousin@irisa.fr

Global Vs. Per-Domain Monitoring of Multi-Domain Networks

Mutli-domain monitoring aims at guaranteeing QoS for services crossing several domains. It is often desirable to perform global monitoring to guarantee end-to-end QoS for services across domains and to reduce the monitoring cost. However, global monitoring might be infeasible due to confidentiality constraints. The alternative solution is to perform per-domain monitoring.

In this work, we propose to evaluate global and per-domain monitoring techniques. For this end, we study the properties of multi-domain networks and the requirements of multi-domain monitoring. We formulate the problem as an Integer Linear Program (ILP). We show that it is a Nondeterministic Polynomial Time Hard (NP-Hard) problem, and therefore, we devise a heuristic that meets multi-domain properties. We show that confidentiality is far from being the only constraint to global multi-domain monitoring. In our evaluation, the confidentiality constraint has been relaxed, in order to investigate other performance metrics; namely, the monitoring cost, the quality of monitored paths, the anomaly detection delays, and the fairness of monitoring load distribution among domains. Simulation results on random topologies show that per-domain monitoring outperforms global monitoring for all these metrics, except the monitoring cost that is slightly lower for global monitoring.

I. INTRODUCTION

Link-level anomaly monitoring is a means to detect and localize anomalies on links that occur due to physical failures, network congestion and security attacks. It evaluates the delays and loss rates on links and their available bandwidth capacities, in order to guarantee the QoS requirements for services crossing the network. Most existing studies on link-level network monitoring have focused on mono-domain networks (e.g. [START_REF] Zhao | Towards efficient largescale VPN monitoring and diagnosis under operational constraints[END_REF], [START_REF] Baford | Network performance anomaly detection and localization[END_REF], [START_REF] Argawal | Diagnosing link-level anomalies using passive probes[END_REF], [START_REF] Naidu | Detecting anomalies using end-to-end path measurements[END_REF], [START_REF] Bajerano | Robust Monitoring of Link Delays and Faults in IP Networks[END_REF], [START_REF] Suh | Locating network monitors: Complexity, heuristics, and coverage[END_REF]). However, usually, services cross multiple domains that belong to different administrative authorities, and that are likely to have conflict of interests. This raises some confidentiality problems that constrain the monitoring task. Namely, most proposed monitoring schemes, which assume a detailed knowledge of the network topology, cannot be applied on multi-domain networks. This is because domains are usually not willing to disclose detailed information of their network topology and available resources.

In this paper, we focus on the problem of diagnosing link-level anomalies in multi-domain networks. This includes locating monitors and selecting monitoring paths than can cover all the links. Our goal is to come up with a monitoring This work has been supported by Alcatel-Lucent labs France, under the grant n. 09CT310-01 scheme that overcomes confidentiality limitations. To this end, we investigate the problem along two axes. The first axis ignores confidentiality constraints and considers the multidomain network as a single domain. This is the global monitoring technique. The second axis overcomes confidentiality considerations by minimizing the information that is to be exchanged between domains. Each domain monitors its intradomain links independently from the other domains, i.e. without disclosing any information of its intra-domain topology. Neighboring domains exchange only the set of their border nodes that are candidate to hold monitoring devices, in order to compute monitor locations and paths that can cover the interdomain links connecting them. This is the per-domain monitoring technique. Practically, the global monitoring technique might be infeasible. However, a comparative study of these two monitoring techniques aims at finding out and evaluating all the constraints, other than confidentiality, that the multidomain monitoring must comply to.

The problem of monitor location and anomaly detection has gained great interest over the few last years. The shared goal of all these works is to minimize the monitoring cost, that is the cost of locating monitoring devices and the cost of injecting monitoring flows along monitoring paths. In this work, we adopt the monitoring scheme proposed in [START_REF] Salhi | Joint Optimization of Monitor Location and Network Anomaly Detection[END_REF] [START_REF] Salhi | Heuristics for Joint Optimization of Monitor Location and Network Anomaly Detection[END_REF] that has been proven to achieve a smooth trade-off between monitor location cost and anomaly detection cost by minimizing the two costs jointly. The main challenge is to adapt the proposed solutions to multi-domain networks with respect to topology characteristics. We provide a mathematical formulation of the problem, and we show that it is NP-Hard. Therefore, we devise a heuristic solution that takes into considerations the characteristics and the limitations of multi-domain network topology.

The proposed heuristic is used by the global monitoring technique and the per-domain technique. Besides the computation time and the monitoring cost, we consider new criteria to evaluate the two monitoring techniques. These criteria emerge from the characteristics of multi-domain networks and impact the monitoring performance. First multi-domain networks are large networks. Therefore, the global monitoring technique that considers the multi-domain network as a single domain is likely to monitor long paths that cross multiple domains. This would result in large detection delays. Indeed, the longer the monitored paths are, the larger the anomaly detection delays are. Furthermore, long monitoring paths result in large number of suspect links in case of failure. This is because all the links of a monitoring path that exhibits an anomaly are suspect to be anomalous. Second, multi-domain networks are composed of domains that belong to different administrative and economic authorities. Therefore, the monitoring solution should distribute the monitoring load among domains fairly. Otherwise, the most overloaded domains would not be willing to collaborate.

We show through simulations that confidentiality is not the only limitation to global multi-domain monitoring. Indeed, results show that this monitoring technique delivers solutions with relatively long monitored paths and does not guarantee a fair distribution of monitoring load among domains. Besides, the computation time for the global monitoring technique is drastically high compared to the computation time for the per-domain monitoring technique. In contrast, the difference of costs of the solutions delivered by the two monitoring techniques, in terms of number of monitors and redundant measurements of links, is tiny. This is due to the characteristics of multi-domain topology that will be discussed throughout this paper.

II. PROBLEM FORMULATION

A. Network Model

We can model a multi-domain network composed of M connected domains as a set of undirected graphs

G i = (V i , L i ), i = 1, 2, ..., M . V i is the set of nodes of domain i. It is composed of two sets: V inter i and V intra i . V inter i
represents the set of border nodes that connect domain i to its neighboring domains, and V intra i represents the set of core nodes. Similarly, the set of links L i is composed of two sets:

L intra i and L inter i . L intra i
represents the set of intra-domain links that connect the core nodes, and L inter i represents the set of inter-domain links that connect nodes of V inter i to the border nodes of neighboring domains. We denote by P i , i = 1, 2, ..., M the set of intra-domain paths of domain i. A path p ∈ P is a set of undirected intra-domain links. We denote by P inter the set of inter-domain paths of the multi-domain network. A path p inter ∈ P inter includes at least one interdomain link. We refer to

G intra i = (V i , L intra i
) as the intradomain graph of domain i. Let Nd = {(i, j); i, j = 1, 2, ..., M ; i and j are neighbor domains} be the set of neighbor domains. We refer to G (i,j) = (V i,j , L i,i ) as the graph of the interdomain topology connecting domain i to domain j. V i,j is the set of border nodes of domains i and j that are connected to each other, and L i,j is the set of inter-domain links connecting domain i to domain j.

B. Problem Definition

This work addresses the problem of monitor location and network anomaly detection in multi-domain networks. For mono-domain networks, minimizing the cost of monitor location and network anomaly detection consists in deploying as few monitors as possible and avoiding redundant measurements of links, i.e. avoiding overlaps among monitoring paths.

These two minimization objectives are conflictual. It turned out that a joint optimization of monitor location and anomaly detection costs balances efficiently the trade-off and reduces the two costs [START_REF] Salhi | Joint Optimization of Monitor Location and Network Anomaly Detection[END_REF]. However the problem is NP-Hard. Heuristics have been proposed for mono-domain networks in [START_REF] Salhi | Heuristics for Joint Optimization of Monitor Location and Network Anomaly Detection[END_REF]. For multi-domain networks, the problem can be formulated as follows. We want to deploy monitors and select monitoring paths between the deployed monitors. The aim is to cover all the inter-domain and the intra-domain links, while reducing the number of deployed monitors and avoiding redundant measurements.

Until now, multi-domain monitoring seems to be similar to mono-domain monitoring. However, there are some constraints to multi-domain monitoring that stem from the characteristics of multi-domain networks. The first constraint is related to the structure of multi-domain networks. A multi-domain network is a set of domains that belong to different administrative authorities. Due to economic and security considerations, domains are usually not willing to share detailed information of their network topologies and resources. This is a blocking constraint to the global monitoring technique. This technique assumes the existence of a central entity that has a detailed knowledge of the intra-domain topologies of all the domains composing the multi-domain network as well as the inter-domain topologies connecting neighboring domains. An alternative solution would be to let each domain cover its intra-domain links using intra-domain paths only. Neighboring domains collaborate to cover inter-domain links connecting them. This is the per-domain technique.

At first glance, when the global topology is known, we tend to assert that the global monitoring technique outperforms the per-domain monitoring technique. This is because, considering only the metrics of number of monitors and number of redundant measurements of links, all the solutions of the per-domain monitoring technique are feasible solutions of the global monitoring technique. We illustrate our assertion in Fig. 1. and Fig. 2. Hereby, we consider a multi-domain network composed of two domains connected by a single inter-domain link [START_REF] Zhao | Towards efficient largescale VPN monitoring and diagnosis under operational constraints[END_REF][START_REF] Argawal | Diagnosing link-level anomalies using passive probes[END_REF]. We assume that the cost of deploying a monitor equals the cost of a redundant measurement, i.e. the cost of measuring a link that is already measured. Grey nodes hold monitoring devices. The black thick lines draw the monitored paths. Fig. 1. depicts a minimal per-domain monitoring solution, whereas Fig. 2. depicts a minimal global monitoring solution. We notice that the per-domain solution deploys 4 monitors, against 2 monitors and 1 redundant measurement for the global solution. The global monitoring technique succeeded to reduce the monitoring cost by removing monitors that are deployed on the border nodes of each domain.

The question that arises here is the following: how worse is the performance of the per-domain technique compared to the global monitoring technique ?

To answer this question, we investigate the quality of the global monitoring solutions. Reducing the number of monitors results in longer monitoring paths. The figures above validate this claim. Nonetheless, multi-domain networks are usually very large networks. Subsequently, the global monitoring technique is likely to select very long monitoring paths. This is the second constraint to global monitoring; because the longer the monitored paths are, the larger the anomaly detection delays are and the larger the number of suspect links in case an anomaly occurs is. Furthermore, when domains accept to collaborate to perform global monitoring, they expect to achieve individual benefits in return. This means that the monitoring solution should distribute the monitoring load among the participating domains evenly. Therefore, besides the monitoring cost, the quality of monitoring paths and the fairness of monitoring load distribution must be considered in the evaluation of the two monitoring techniques.

Based on this discussion, we claim that confidentiality is so far not the only constraint to global monitoring, and that per-domain monitoring might turn out to be more efficient with respect to some metrics. We validate our claims in the remainder of this paper.

C. Architecture and Cost Model of Multi-Domain Monitoring

Fig. 3. depicts a sample multi-domain monitoring architecture, only nodes that hold monitoring devices are drawn. In each domain there is a Network Operation Center, denoted Domain NOC, that communicates with the monitors of the domain, in order to collect monitoring information and manage the monitoring task within the domain. A domain NOC has a detailed knowledge of the domain topology and resources. In addition, there is a central NOC that communicates with all the Domain NOCs. It collects and analyzes monitoring information collected within domains. This multi-domain architecture matches the usual architecture proposed in most works on multi-domain monitoring (e.g. [START_REF] Sadasivan | Quittek Architecture for IP Flow Information Export[END_REF], [START_REF] Schmoll | Final Architecture Specification, INTER-MON Deliverable[END_REF]). For global monitoring, the central NOC has a detailed knowledge of the topologies and the resources of all the domains; whereas for per-domain monitoring, it does not participate in the monitoring task.

We note that monitor location and anomaly detection means deploying monitors in the network and selecting monitoring paths that can cover all the network links in order to detect potential link-level anomalies. In this work, we are not interested in the localization of anomalies. The cost of deploying a monitoring device on node n C l i

The cost of monitoring the intra-domain link

l i C l (i,j)
The cost of monitoring the inter-domain link l i,j δ l i p A binary parameter that indicates whether link l i belongs to path p δ l (i,j) p A binary parameter that indicates whether the inter-domain link l (i,j) belongs to path p δn i p A binary parameter that indicates whether node n i is an end node of path p DR i (SP ) the detection ratio of path p i considering the set of selected monitoring paths SP CP

The set of candidate monitoring paths SP The set of selected monitoring paths SM The set of selected monitors A summary of the symbols used in the remainder of the paper is depicted in TABLE I. The multi-domain monitoring cost can be expressed as the sum of the following costs: * Monitor location cost: it includes the effective cost of deploying hardware and software monitoring devices and the cost of their maintenance. In addition, it includes the cost of communications between monitors and their corresponding Domain NOC. For instance, the cost of communications between a monitor and the NOC can be expressed as a function of the physical distance that separates them. Let us denote by C ni the cost of deploying a monitor on node n i , the multidomain monitor location cost can be expressed as follows:

∑ i=1,2,...,M, ni∈Ni C ni Y ni (1)
* Anomaly detection cost: it expresses the overhead of monitoring flows on the underlying network. Each link must be monitored at least once. Redundant measurements of links are considered as monitoring overhead. Let us denote by C li the cost of measuring link l i . C li must be proportional to the load of link l i , in order to avoid multiple measurements of the most overloaded links of the network. The multi-domain anomaly detection cost can be expressed as follows:

∑ i=1,2,...,M, li∈Li, p∈Pi∪P inter δ lip C li Z p + ∑ (i,j)∈N d, l (i,j) ∈L (i,j) , p∈P inter δ l (i,j) p C l (i,j) Z p (2)

III. ILP FORMULATION

The monitoring solution aims at minimizing the location cost (1), and the anomaly detection cost [START_REF] Salhi | Heuristics for Joint Optimization of Monitor Location and Network Anomaly Detection[END_REF]. In our previous works, we have demonstrated that there is an interplay between these two minimization objectives. However, it turned out that the joint minimization of the two objectives balances efficiently this interplay [START_REF] Salhi | Joint Optimization of Monitor Location and Network Anomaly Detection[END_REF], [START_REF] Salhi | Heuristics for Joint Optimization of Monitor Location and Network Anomaly Detection[END_REF]. Therefore, our ILP formulation minimizes jointly the monitoring costs expressed above. Let α and β be relative weights of the monitor location cost and the anomaly detection cost, respectively. The objective function reads as follows:

minimize: α*(1) + β*(2)
All the links of the multi-domain network, i.e. the intradomain and the inter-domain links, must be monitored at least once. Practically, this means that each link must belong at least to one monitored path. These link coverage constraints read as follows:

∑ i=1,2,...,M, p∈Pi∪P inter δ lip Z p ≥ 1; ∀i = 1, 2, ..., M, ∀l i ∈ L i (3) ∑ p∈P inter δ l (i,j) p Z p ≥ 1; ∀(i, j) ∈ N d, ∀ l (i,j) ∈ L (i,j) , (4)
The end nodes of all the monitored paths must hold monitoring devices. These monitor location constraints read as follows:

Y ni ≥ δ nip Zp, ∀i = 1, 2, ..., M, ∀n i ∈ N i , ∀p ∈ P i ∪ P inter (5)
The equivalent problem for mono-domain networks has been shown to be NP-Hard [START_REF] Salhi | Joint Optimization of Monitor Location and Network Anomaly Detection[END_REF]. The multi-domain monitoring problem is reduced to the mono-domain monitoring problem, introduced in [START_REF] Salhi | Joint Optimization of Monitor Location and Network Anomaly Detection[END_REF], for N d = ∅ and P inter = ∅. We conclude that the multi-domain monitoring problem is NP-Hard, and thus, we propose a heuristic solution in the next section.

IV. HEURISTIC SOLUTION

The heuristic solution aims at minimizing the monitor location cost and the anomaly detection cost jointly, thereby balancing the trade-off between these two minimization objectives; while considering the properties and the limitations of inter-domain networks.

Muli-domain networks are, usually, composed of dense domains interconnected by few inter-domain links. Therefore, the number of paths between two nodes belonging each to a different domain, which is proportional to the number of interdomain links separating the two domains, is small compared to the total number of paths. In [START_REF] Salhi | Joint Optimization of Monitor Location and Network Anomaly Detection[END_REF], we have proposed a heuristic for joint optimization of monitor location and anomaly detection in mono-domain networks. This heuristic performs an in-depth exploration of the network graph, in order to find candidate monitoring paths between two given nodes. It has been shown that this technique delivers good 1 candidate monitoring paths in a short time [START_REF] Salhi | Joint Optimization of Monitor Location and Network Anomaly Detection[END_REF]. However, when we ran this heuristic on multi-domain networks and mono-domain networks of the same size (i.e. the same number of links and the same number of nodes), we noted that the computation time of the multi-domain solution is drastically higher than the computation time of the mono-domain solution. As expected, this exponential increase of the computation time is due to the computation time of candidate monitoring paths in multidomain networks. We consider the multi-domain network depicted in Fig. 4. to illustrate our assertions.

The network is composed of two domains. The dotted links are inter-domain links and the gray nodes hold monitoring devices. The thick black line draws an inter-domain path that starts from the monitor located in Domain 1, reaches domain 2 and then returns back to domain 1. The dotted thick line draws an intra-domain path that starts from the monitor located in Domain 1, crosses the two border nodes of Domain 1 (nodes 9 and 8), but do not reach Domain 2. We note that we avoid looping paths, i.e. paths that cross the same nodes multiple times. These are two examples of excluded paths: long paths 1 We refer to the work in [START_REF] Salhi | Joint Optimization of Monitor Location and Network Anomaly Detection[END_REF] for more details on the criteria and the computation technique of candidate monitoring paths in mono-domain networks that do not end at a monitoring device and whose computation time is long. It is the existence of such bad paths that makes the computation time of inter-domain candidate monitoring paths quite long, and therefore, the heuristic proposed in [START_REF] Salhi | Joint Optimization of Monitor Location and Network Anomaly Detection[END_REF] inappropriate for global monitoring of multi-domain networks. Further, other works on intra-domain monitoring have not provided solutions for the problem of candidate monitoring path computation (e.g. [START_REF] Zhao | Towards efficient largescale VPN monitoring and diagnosis under operational constraints[END_REF], [START_REF] Baford | Network performance anomaly detection and localization[END_REF], [START_REF] Argawal | Diagnosing link-level anomalies using passive probes[END_REF], [START_REF] Naidu | Detecting anomalies using end-to-end path measurements[END_REF], [START_REF] Bajerano | Robust Monitoring of Link Delays and Faults in IP Networks[END_REF], [START_REF] Suh | Locating network monitors: Complexity, heuristics, and coverage[END_REF]).

A. Candidate Monitoring Path Computation in Multi-domain networks

The solution that we propose to compute candidate monitoring paths consists in assigning a positive weight to each network link, and exploring the network links with a probability that is proportional to their weights. The underlying idea is to reduce the probability to re-explore bad sequences of links, while increasing the probability to cross inter-domain links. Initially, all the links have an equal weight. This means that links have the same probability to be added to the computed path. The computation ends when the path reaches the target node, this is a good path, or when it reaches a node whose neighboring nodes already belong to the path, this is a bad path. If the computed path is good, the weights of all its links are incremented. Since all the good paths cross inter-domain links, this will increase the probability to use those links. We resume the computation of new paths from the starting node, in order to increase the space of explored paths.

B. Greedy Monitor Location and Path Selection Algorithm

Here, we give an outline of Algorithm 1. The algorithm starts by selecting two monitor locations that have the lowest costs; or in case several couple of monitor locations have the lowest cost, it selects a couple arbitrary. Next, it computes a set of candidate paths between the selected monitor locations Algorithm 1 end if 24: end if 25: Select a new monitor that minimize the monitor location cost 26: Add the new monitor to SM 27: Clear CP 28: CP ← candidate paths between the new monitor and the deployed monitors 29: Remove paths that incur redundant measurements from SP and add them to CP 30: Go to line 5 as described above. For each candidate path, the algorithm computes a detection ratio that expresses the ratio between the number of links that are covered by the path and the number of redundant measurements, i.e. the number of links that belong to the path and that are already covered by selected monitoring paths, i.e. paths in SP . The path that have the highest detection ratio is selected. This is because it achieves the best trade-off between the number of covered links and the number of redundant measurements. The detection ratios are updated whenever a new path is selected.

Monitoring paths are selected until all the network links are covered, or all the candidate paths have their detection ratios equal to zero. In the latter case, the deployed monitors are not sufficient to cover all the network links, therefore, a new monitor is deployed. In the first case we get a full monitoring solution, i.e. full coverage of the network links. However, as said earlier, we want to find the best trade-off between the monitor location cost and the anomaly detection cost. Therefore, when the algorithm gets a full solution, it verifies whether it can diminish the anomaly detection cost by deploying new monitors. It decides to deploy a new monitor if the cost of the new monitor is lower than the anomaly detection cost of the solution computed over the previous iteration. Now, when a new monitor is deployed, the algorithm removes all the paths that incur redundant measurements from the set of selected paths and inject them into the set of candidate paths CP , and then updates the detection ratios and selects monitoring paths with respect to their detection ratios.

V. EVALUATION

In this section we first describe the evaluation methodology, and then we present and discuss numerical results.

A. Evaluation Methodology

The aim of the evaluation is to assess the performance of per-domain monitoring versus global monitoring of multi-domain networks. To this end, we run the heuristic proposed in the previous section for these two monitoring techniques on several multi-domain network topologies generated randomly using the network generator Brite (Waxman model: α = β = 0.4, random node placement) [14]. Unless mentioned, we consider the following setting to generate multi-domain topologies: the network is composed of 3 domains; a domain of 10 nodes and 31 links is connected to a domain of 15 nodes and 59 links, which is in turn connected to a domain of 10 nodes and 31 links. The number of border nodes that connect each domain to a neighboring domain ranges from 2 to 3 nodes, and the number of inter-domain links between two neighboring domains ranges from 4 to 6 links. In the remainder of the paper, we refer to this setting as the default setting. Fig. 5. depicts a sample multi-domain topology. We assume that all the network nodes are candidate to hold monitoring devices and that the cost of deploying monitors is the same for all the nodes; i.e. C ni = 1, ∀n i ∈ N i ∀i = 1, 2, ..., M . Furthermore, we assume that the link monitoring cost is the same for all the network links; i.e. C li = 1, ∀l i ∈ L i ∀i = 1, 2, ..., M . We assume that α = β = 1. All simulation measures are the mean over 30 simulations on randomly generated topologies. Our simulation plateform is developed in C++ For global monitoring, we assume that the central NOC, which has a global knowledge of the multi-domain topology, runs the heuristic on the global topology including the 3 domains and the inter-domain links connecting them. For perdomain monitoring, each domain runs the heuristic on its intradomain topology. Once all the intra-domain links are covered, neighboring domains exchange their set of border nodes that hold monitoring devices, if any, in order to cover the interdomain links connecting them using the same heuristic on the inter-domain topology. We note that in our simulations, if two intra-domain solutions have the same monitoring cost, we choose the solution that deploys the most monitors on its border nodes so that they can be re-used to cover inter-domain links.

B. Numerical Results

We evaluate and compare the global monitoring technique and the per-domain monitoring technique along four metrics:

1) Monitoring Cost: we expect that the fewer are the interdomain links, the smaller is the difference between the costs of the solutions delivered by global monitoring and the solutions delivered by per-domain monitoring. Indeed, global monitoring reduces the monitoring cost by monitoring inter-domain paths, i.e. paths that cross multiple domains. This is because the monitoring of inter-domain paths requires less monitoring devices and can cover links of crossed domains and also inter-domain links. However, the number of non-overlapping inter-domain monitoring paths is proportional to the number of inter-domain links. Therefore, the global monitoring optimization gets blocked by redundant measurements of interdomain links, and ends by deploying additional monitors to avoid overlaps among inter-domain paths.

To validate our expectations, we run the heuristics for global and per-domain monitoring on topologies with the default setting, and also on topologies for which we doubled the number of inter-domain links. Fig. 6. plots the monitoring cost, i.e. the number of deployed monitors and the number of redundant measurements of links, for the two monitoring techniques applied on topologies with the default setting. As expected, Fig. 6. shows that the difference between the monitoring costs of the solutions delivered by the two monitoring techniques is low for the default setting. We notice We note that practically the number of inter-domain connections is generally small in usual networks, and thus, the default setting is more realistic [START_REF] Spring | Measuring ISP Topologies with Rocketfuel[END_REF].

2) Computation Time: Fig. 8. draws the average CPU computation time for global and per-domain monitoring. The figure shows that per-domain monitoring is much more faster than global monitoring. As explained earlier, this is because it takes longer time to compute candidate monitoring paths that cross multiple domains than to compute intra-domain candidate monitoring paths. However, the heuristic succeeds to deliver a solution for global monitoring in about 1200 seconds, whereas other heuristics devised for mono-domain networks have stumbled against the topology properties of multi-domain networks.

3) Quality of monitored paths: We categorize the monitoring paths according to their lengths, in terms of number of links, into five groups: paths of length in [START_REF] Salhi | Joint Optimization of Monitor Location and Network Anomaly Detection[END_REF][START_REF] Salhi | Heuristics for Joint Optimization of Monitor Location and Network Anomaly Detection[END_REF][START_REF] Zhao | Towards efficient largescale VPN monitoring and diagnosis under operational constraints[END_REF][START_REF] Baford | Network performance anomaly detection and localization[END_REF][START_REF] Argawal | Diagnosing link-level anomalies using passive probes[END_REF], paths of length in [START_REF] Naidu | Detecting anomalies using end-to-end path measurements[END_REF][START_REF] Bajerano | Robust Monitoring of Link Delays and Faults in IP Networks[END_REF][START_REF] Suh | Locating network monitors: Complexity, heuristics, and coverage[END_REF][START_REF] Spring | Measuring ISP Topologies with Rocketfuel[END_REF][START_REF] Sadasivan | Quittek Architecture for IP Flow Information Export[END_REF], paths of length in [START_REF] Schmoll | Final Architecture Specification, INTER-MON Deliverable[END_REF][START_REF] Pitoura | Distribution fairness in Internet-scale networks[END_REF][START_REF] Dagum | The generation and distribution of income, the Lorenz curve and the Gini ratio[END_REF][14][15], paths of length in [16-20], and paths of length in [21-30]. In Fig. 9., we show the distribution of network links by path length groups for the two monitoring techniques. A link belongs to a path length group if it is monitored by a path whose length is included in the length range of that group.

First, we notice that the longest monitoring paths for the per- domain monitoring technique are of length less than or equal to 15 links; whereas for the global monitoring technique, the length of monitoring paths reaches 30 links. This is because the global monitoring technique monitors inter-domain paths that are naturally longer than intra-domain paths. Second, Fig. 9. shows that more than 40% of network links belong to long paths, paths whose length is more than or equal to 15. This means that in 40% of cases of link-level anomalies, we get between 15 and 30 suspect links. In contrast, for per-domain monitoring almost 90% of network links belong to short paths, paths whose length is less than or equal to 10. We conclude that per-domain monitoring technique reduces the length of monitoring paths, and therefore, reduces anomaly detection delays and the number of suspect links when an anomaly occurs.

4) Fairness of monitoring solutions:

In this section we propose to show the distribution of monitors and redundant measurements across domains. The aim is to evaluate the fairness of the monitoring solutions delivered by the two monitoring techniques in distributing the monitoring load among domains. To this end, we consider in our simulations multi-domain networks composed of 4 domains having the same number of intra-domain links, 18 links, and the same number of nodes, 8 nodes. Each of the 4 domains is connected to 2 other domains. The number of inter-domain connections, i.e. number of inter-domain links and inter-domain nodes connecting two neighboring domains, is the same for each couple of neighboring domains. For such symmetric multidomain networks, a fair monitoring solution would distribute monitors and redundant measurements among domains evenly.

We use the Gini coefficient to measure the efficiency of monitoring cost balancing among domains [START_REF] Pitoura | Distribution fairness in Internet-scale networks[END_REF] [START_REF] Dagum | The generation and distribution of income, the Lorenz curve and the Gini ratio[END_REF]. Fig. 10. plots the Lorenz curves for the two monitoring techniques. Here, the curves are functions of the cumulative percentage of the number of domains ordered by their monitoring cost, i.e. the number of monitors located in the domain and the number of redundant measurements of the domain links, on the xaxis mapped onto the corresponding cumulative percentage of their monitoring costs on the y-axis. We note that if an interdomain link is measured multiple times, we add the cost of this redundant measurement to the monitoring costs of the two domains it connects. If the monitoring cost is distributed among domains evenly, the Lorenz curve is a diagonal line that we call the line of equality. Uneven distributions generate curves below this line. The larger is the area between the line of equality and the Lorenz curve, the greater is the inequality in the distribution of monitoring load among domains. Fig. 10. shows that the curve corresponding to the global monitoring technique falls below the curve corresponding to the per-domain technique. This means that per-domain technique balances the monitoring load among domains more efficiently. This is explained by the fact that, in contrast to the per-domain monitoring technique, the global monitoring technique considers the multi-domain networks as a single domain. This generates uneven distributions of the monitoring load among domains.

VI. CONCLUSION

In this paper, we investigated the problem of monitor location and anomaly detection in multi-domain networks. An ILP formulation was proposed; and a heuristic that takes into account the the limitations of multi-domain topologies and the requirements of multi-domain monitoring was devised. This heuristic is used to evaluate and compare two multidomain monitoring techniques, global monitoring and perdomain monitoring, with respect to a set of performance metrics that emerge from the properties of multi-domain networks. Simulation results show that confidentiality is so far not the only constraint to global monitoring, and demonstrate that perdomain monitoring is an efficient alternative. In our future works, we will investigate the problem of anomaly localization in mono-domain and multi-domain networks.

Fig. 1 .

 1 Fig. 1. Per-domain Monitoring Solution

Fig. 3 .

 3 Fig. 3. Sample Multi-domain Monitoring Architecture

  Dotted links: inter-domain links Grey nodes: hold monitoring devices Thick lines: excluded candidate monitoring paths

Fig. 4 .

 4 Fig. 4. Illustrative multi-domain network

7 :

 7 find p s ∈ CP/∀p i ∈ CP, DR s (SP ) ≥ DR i (SP ) 8: if (DR s (SP ) == 0 ) then 9: Go to line 25 /* the deployed monitors cannot cover all the network links*p s to SP 12: remove p s from CP 13: update DR i (SP ), ∀p i ∈ CP 14: end if 15: end while 16: if ( Not all links are covered ) then 17: Go to line 25 18: else 19: if (the cost of deploying a new monitors ≥ redundant measurements incurred by paths in SP ) then 20: End of the algorithm 21:

Fig. 5 .

 5 Fig. 5. Illustrative multi-domain topology

  Fig 7 plots the same metrics for the two monitoring techniques applied on topologies for which we have doubled the number of inter-domain links.

Fig. 7 .

 7 Fig. 6. Monitoring Cost: default setting

Fig. 8 .

 8 Fig. 8. CPU Computation Time (logarithmic scale)

Fig. 9 .

 9 Fig. 9. Distribution of network links by path length groups

Fig. 10 .

 10 Fig. 10. Distribution of monitors and redundant measurements across domains

TABLE I

 I

		NOTATIONS USED THROUGHOUT THE PAPER
	Symbol	Definition
	Zp	A binary variable that indicates whether path p
		is selected to be monitored
	Yn i	A binary variable that indicates whether node n i
		is selected as a monitor location
	Cn i

1 :

 1 SP = ∅ 2: Select two monitor locations m 1 , m 2 that have the lowest monitor locations costs 3: Add m1 and m2 to SM 4: CP ← {candidate paths between m1 and m2} 5: ∀p i ∈ CP, DR i (SP ) ← (# of links covered by p i ) / (number of links of p i that are covered by paths in SP ) 6: while ( not all links are covered ) do