Philippe-Henri Gosselin
email: gosselin@ensea.fr

Naila Murray

Hervé Jégou

Florent Perronnin

Revisiting the Fisher vector for fine-grained classification

Keywords:

This paper describes the joint submission of Inria and Xerox to their joint participation to the FGCOMP'2013 challenge. Although the proposed system follows most of the standard Fisher classification pipeline, we describe a few key features and good practices that significantly improve the accuracy when specifically considering fine-grain classification tasks. In particular, we consider the late fusion of two systems both based on Fisher vectors, but for which we choose drastically design choices that make them very complementary. Moreover, we propose a simple yet effective filtering strategy, which significantly boosts the performance for several class domains.

Introduction

Given an input image, image classification aims at determining what is the category of the objects depicted in the image. For instance, typical visual classes are 'person ', 'bird', 'cat', 'aircraft', 'chair', etc. Recently, we have witnessed a shift in the interest of the computer vision community towards Finegrained classification (FGC). Although a precise definition of the problem is not formally given, the objective is here to determine the class at a finer level of granularity. For instance, assuming that we know that all considered images contain birds, FGC requests the system to decide what kind of bird is depicted. Another example is to indicate what model of car is present in the image, as opposed to classification that would simply ask to determine whether a car appears in the image.

As noted in [START_REF] Chai | Symbiotic segmentation and part localization for fine-grained categorization[END_REF], FGC differs from standard coarse-grained classification (CGC) in two significant ways:

• Property 1: while in CGC classes exhibit global differences, in FGC classes often share the same global appearance. Therefore, two classes may be visually distinguishable only based on subtle localized details. To better illustrate this challenge, we present in Fig. 1 examples of classes for the airplane domain. For example, if we focus on aircrafts, the FGC system has to distinguish between the different version of Boeing 747 aircrafts. Note that it is possible, for instance if one counts the windows.

• Property 2: while in CGC the background provides valuable context for categorization, in FGC it is rarely discriminative and consequently acts as a source of noise.

For these two reasons, FGC is perceived as significantly more challening than CGC. While the best performing approaches to image classification are fairly well-identified -and include Fisher vectors [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF][START_REF] Perronnin | Improving the fisher kernel for large-scale image classification[END_REF][START_REF] Chatfield | The devil is in the details: an evaluation of recent feature encoding methods[END_REF], deformable part models [START_REF] Felzenszwalb | Object detection with discriminatively trained part-based models[END_REF] and deep learning approaches [START_REF] Krizhevsky | Image classification with deep convolutional neural networks[END_REF] -it is still unclear which approaches perform best for FGC and how they should be adapted to better address the specificities of the problem. The goal of this paper is to evaluate the suitability of the Fisher Vector (FV) in this context. Starting from the standard FV pipeline used in CGC, we derive two subsystems (SA and SB) with different focus, and then combine them in a final solution. These systems have been designed and optimized in the context of the joint participation of Inria and Xerox in the FG-Comp 2013 fine-grained challenge. This challenge evaluates systems for 5 different FGC problems thanks to 5 independent datasets. For this purpose, we split the training set into two sets (75% for learning and 25% for validation).

Our main contribution is to reveal the parameters which are crucial for high-accuracy FV-based FGC. For instance, we show that large vocabularies enable to model subtle visual details, and that a properly cross-validated power-normalization ensures that these details are not overpowered by frequent patches (see property 1). We also show that techniques such as SIFT filtering help in removing non-discriminative visual content in image backgrounds (see property 2). Another important contribution of this work is to show that, despite the recent success of deep-learning-based techniques [START_REF] Krizhevsky | Image classification with deep convolutional neural networks[END_REF] in challenges such as ImageNet, the shallow pipeline that involves coding and pooling patch-based descriptors is still very much relevant in the FGC context.

This paper is organized as follows. Section 2 describes the fine-grained challenge and its evaluation protocol. Section 3 describes the vanilla Fisher classification pipeline, as used in particular in previous evaluation campaigns such as Pascal VOC'07 [START_REF] Everingham | The PASCAL visual object classes (VOC) challenge[END_REF] and Imagenet [START_REF] Dong | Imagenet: A largescale hierarchical image database[END_REF]. Section 4 describes how we have adapted this method to the context of fine-grained classification, and gives a few good practices that may help potential participants of further campaigns. Section 5 analyzes the official results obtained in the FGCOMP 2013 challenge, where our joint participation has obtained the best performance among all participants.

Description of FGComp evaluation campaign

The FGComp challenge aims at evaluating current finegrained classification systems when targeting a specific domain. In this context, the system has to predict a class in an image given its domain, and thus there is no need to determine with which domain an image is associated to. To evaluate different FGC scenarios, FGComp considers 5 datasets, each dataset evaluating a specific problem of FGC:

1. aircrafts. This dataset is compound of photographs of aircrafts in the sky or in airports [START_REF] Maji | Fine-Grained Visual Classification of Aircraft[END_REF]. Classes are very specific models of aircrafts, as illustrated in Fig. 1. 2. birds. This is a subset of the CCUB NABirds 700 dataset, a.k.a. CUB-2001 . This is a collection of photographs in natural environment of birds species that are commonly observed in North America. Birds species can share very similar visual characteristics as well as very different colors and shapes. 3. cars. This dataset focuses on the detection of car models, including different releases of the same car, as illustrated in Fig. 1. Most photographs were taken in urban environment. 4. dogs. This is a collection of dogs species. This dataset has many variability in terms of photographic conditions, like view angles, image resolutions and object counts. 5. shoes. This dataset is very different from the other ones, since this is photographs of shoes in very specific conditions: always a pure white background, same image resolution and well-chosen view angle.

Tables 1 and2 summarize the statistics per domain. For each domain, the number of classes is between 70 and 196, which is relatively large compared to most classification datasets. The average number of annotated samples per class is about 50 labels for most domains except dogs (221 examples in training set). This is significantly smaller than the number of labels one usually finds in the context of image categorization, where thousand of labels are available for each class, typically.

The organizers defined two tracks. The first track assumes that object locations are determined by an external procedure, for instance a user draws a bounding box around the object. As a result, images in both the training and testing sets are provided with a bounding box. The second track only expects that the bounding boxes are provided during the training stage. During the testing stage, it is up to the classification system to find the location of the object inside the image, if necessary.

Fisher standard pipeline

This section briefly describes the "standard" classification pipeline based on Fisher vector (FV) [START_REF] Sánchez | Image classification with the fisher vector: Theory and practice[END_REF], as used by Xerox in prior competitions, e.g. in Pascal VOC [START_REF] Everingham | The PASCAL visual object classes (VOC) challenge[END_REF] and Imagenet challenges [START_REF] Dong | Imagenet: A largescale hierarchical image database[END_REF]. A detailed comparison of this method with other techniques of the state-of-the-art is given by [START_REF] Chatfield | The devil is in the details: an evaluation of recent feature encoding methods[END_REF][START_REF] Huang | Feature coding in image classification: A comprehensive study[END_REF], who conclude that it outperforms other coding techniques (such as bag-of-words or local linear coding) for classification tasks. However, in the latest Imagenet classification challenges, the FV was outperformed by a system based on deep learning [START_REF] Krizhevsky | Image classification with deep convolutional neural networks[END_REF] The Fisher image classification pipeline consists of the following steps:

1. Down-sampling of the images to a fixed size of S pixels, keeping the aspect ratio from the original image. The images smaller than S pixels are not modified. This step drastically reduces the number of descriptors, and avoids extracting descriptors at small resolutions. 2. Extraction of SIFT on a dense multi-resolution grid. The number of resolutions is typically set to 5 and the step size (number of pixels between each sample) on x-and y-axis set to s x = s y = 3 pixels. 3. Post-processing of SIFT descriptors. First, the descriptor dimensions are reduced with PCA, typically to 64 or 80 components. This reduction is important for the next stage, as it ensures that the diagonal covariance matrix assumption is better satisfied. Second, a component-wise processing is applied to the raw SIFT descriptors: we consider both the non-linear processing known as Root-SIFT [START_REF] Arandjelovic | Three things everyone should know to improve object retrieval[END_REF][START_REF] Jain | Hamming embedding similarity-based image classification[END_REF] and the similar sign(x) log(1 + |x|) function used at Xerox in previous challenges. 4. Encoding with the FV. This step converts the set of local descriptors into a single vector representing the image. It relies on a Gaussian Mixture Model (GMM) formed of k Gaussians, assuming a diagonal covariance matrix. This Gaussian mixture is learned on the training set. 5. Spatial pyramid pooling [START_REF] Lazebnik | Beyond bags of features: spatial pyramid matching for recognizing natural scene categories[END_REF] is also applied when using the FV: the image is partitioned into regions, each of which is represented by a FV obtained for the region descriptors. Several partitions are usually considered: 1 × 1 + 3 × 1 + 2 × 2 is a typical setting. 6. We post-process the FV with signed power-law normalization [START_REF] Perronnin | Improving the fisher kernel for large-scale image classification[END_REF]. This step is parametrized by a parameter α, which is the exponent involved in the nonlinear processing of each component x i of the initial FV, as

x i := sign(x i )|x i | α . 7.
The resulting vector is ℓ 2 -normalized and the cosine similarity is used as the similarity metric. 8. A 1-vs-rest support vector machine (SVM) linear classifier is trained and used to determine if the image belongs to a given class.

Color Descriptor. In addition to SIFT and as in previous participations of Xerox in image classification challenges, we additionally used a color descriptor, referred to as X-color in the rest of this report [START_REF] Clinchant | XRCE's participation to ImageEval[END_REF]. It encodes the mean and variance of R,G, and B color channels in each cell of a 4 × 4 grid partition of the patch, resulting in a 2 × 3 × 16 = 96dimensional descriptor. Apart from descriptor computation, all other steps are identical with X-color. The corresponding FV is complementary to that produced with SIFT descriptors.

Adapting the Fisher vector to FGC

We have designed a fine-grained image classification system, which consists of two subsystems, both of them based on FV. All parameters have been optimized on a per-domain basis.

The subsystem SA implements the Fisher processing pipeline described in Section 3. The main differences are 1) the optimization of several parameters assumed to be important for FGC and 2) the choice of a 1 × 1 + 3 × 1 grid for the spatial pyramid (we have not used the 2 × 2 grid to limit the dimensionality of the vector when considering large vocabularies).

The subsystem SB is constructed such that:

• It is as complementary as possible with SA, so that the late fusion of the two subsystems is likely to give a significant boost compared with SA used alone. In order to achieve such a complementary system, we have made different choices in several steps of the processing pipeline, particularly when post-processing local descriptors, and when exploiting spatial information. • It focuses more on the optimization of some domains (namely aircraft, cars and shoes) that can be considered as instance classification. These visual objects correspond to manufactured, man-made objects. Unlike dogs and shoes, we expect little intra-class variability. We also observe less texture on the object itself and in the background.

This section first focuses on demonstrating the importance of the parameters involved in our system and strategies that are specifically adapted to specific domains. Then, we discuss different design choices, which are summarized in Table 3. All the results we present are obtained by cross-validation on the training set, because the annotation of test images is currently not available. We split this set into learn (75% of training set) and val (remaining 25% images). Performance values presented in curves are mean over 5 runs. Standard deviation over these 5 runs are always negligible (about 0.2%-1%), and thus are never plotted.

Large vocabularies

The visual vocabulary used to generate our Fisher vectors must be granular enough to to ensure discriminability between classes, but not so granular as to over-segment the feature space. For coarse-grained visual recognition, a small number of Gaussians (between 256 and 1024) are usually sufficient. However, when inter-class differences classes are subtle, for instance in large-scale particular object retrieval, the vocabulary size is chosen to be very large, comprising up to 1 million visual words. As fine-grained classification may be thought of as in between image classification and particular object recognition, in terms of class granularity, it is worthwhile to evaluate the impact of the vocabulary size on performance.

For the system SA, we have used k = 1, 024 Gaussians for both types of features and for all domains. This choice was mostly guided by storage and memory requirements, Indeed, even with a simple 1×1+3×1 pyramid, k = 1, 024 already gives high-dimensional vectors (D = 2 × 64 × 1024 × 4 = 524, 288). As shown later for SB, k = 1, 024 might not be optimal and more Gaussians can improve accuracy.

Figure 2 shows the impact of the vocabulary sizes in both our subsystems. As one can see, the performance increases for most subdomains. Apart from the shoes domain, we have actually not reached a point of saturation. This suggests that better performance could be further increased by increasing the parameter k, with the caveat that we have to deal with very highdimensional vectors. This problem is partially addressed in SB by an alternative choice for the spatial coordinate coding strategy (SCC) [START_REF] Koniusz | Comparison of mid-level feature coding approaches and pooling strategies in visual concept detection[END_REF]. SCC consists in augmenting each descriptors with values σ x x, σ y y, where x, y ∈ [0, 1] 2 are the descriptor coordinates in the image, and σ x , σ y ∈ R weights tuned though cross validation. To keep complexity at a reasonable level, we have set k=4,096 for aircrafts/birds/cars, k=2,048 for dogs (for computational reasons as dogs is the largest domain) and k=1,024 for shoes. Fig. 3. Cross-validation (in SA) of the α parameter involved in the powerlaw normalization, for the bird domain. In general, α = 0.3 was best for SIFT and α = 0.1 was best for X-color. Consequently, we used these values in SA. For SB, we set α = 0.1.

Power-law

Power-law normalization has become a de facto postprocessing stage applied after coding schemes such as bag-ofwords [START_REF] Jégou | On the burstiness of visual elements[END_REF] or Fisher vectors [START_REF] Perronnin | Improving the fisher kernel for large-scale image classification[END_REF]. Its positive effect is related [START_REF] Jégou | Aggregating local descriptors into compact codes[END_REF] to the non-iid behavior of the descriptors, more specifically the burstiness effect. This is all the more important for FGC as this ensures that infrequent (yet potentially highly informative patches) are not overpowered by frequent (yet not necessarily informative patches) such as uniform background patches. As mentioned in Section 3, this normalization is parametrized by a single parameter α, which is often fixed in the literature. In our case, we have cross-validated this parameter for both SIFT and X-color descriptors. The results are shown in Figure 3, where it can be observed that small values provides much better performance with X-color. The performance is more stable for SIFT in the interval [0.1,0.3]. Therefore, in SA we set α = 0.3 and α = 0.1 for SIFT and X-color, respectively, while in SB we complementarily set α = 0.1. Slightly better results are obtained on the validation set by setting these parameters on a per-domain basis.

Resolution

In systems relying on dense sampling, it is often considered necessary to down-sample the images whose resolution is too Table 4. Performance per domain as a function of the image resolution (down-sampling). Evaluation is done for subsystem SB in Track 2: k = 64, τ = 500, α = 0.1. We do not include the dog domain in this comparison, as the corresponding number of images is large (see Table 1) and we agnostically set the resolution to 100k to limit the computational overhead. large. While reducing the image size is mostly considered for computational reasons, i.e., to limit the number of descriptors to a tractable number (otherwise, this number could be as large as hundreds of thousands), Table 4 reports the relationship between performance and image size. As one can observe, the largest resolution generally offers the best performance. We set S =300k pixels for aircrafts, birds and shoes, and S =100k pixels for dogs and shoes.

Filtering strategy

While sophisticated techniques can be employed to focus the FGC process on the object and its most discriminant parts [START_REF] Chai | Symbiotic segmentation and part localization for fine-grained categorization[END_REF], we introduce a simple technique which involves filtering of low-energy descriptors. It is based on the observation that these patches are not discriminant in a FGC context. Before ℓ 2 -normalizing the SIFT descriptor, we compute the ℓ 2 of the patch and compare it to a threshold τ. This strategy can be seen as an extension of a filtering stage used by Jain et al. [START_REF] Jain | Hamming embedding similarity-based image classification[END_REF], who filter the patches whose quantized values of the gradients are strictly equal to 0. In our case, we apply this strategy in a more extreme manner by setting a threshold τ that filter significantly more patches. Note that even in the case τ = 0, we remove some patches (those whose gradients are 0, similar to Jain et al.).

The consequence is that we remove uniform patches, which are quite common in some domains such as aircraft where the objects are often depicted in the sky. This is also the case for smooth objects like cars, whose interior regions are uniform. Furthermore, with τ large enough, blurry patches are discarded and generally only corners and edges are preserved. Considering the scale of patches, smaller patches are more likely to be removed than larger patches, and thus this increases the weight of higher scales. An example of filtering is shown in Figure 4, which shows the effect of filtering for different values of the threshold τ.

The filtering is consistently applied to descriptors used to train the Gaussian Mixture Model, which focuses more on highenergy patches. The expected benefit is to remove the weights of uninformative patches in the Fisher vector. This results in an increase of classification accuracy for aircrafts, birds and cars domains. However, for dogs we don't see any improvement, which might be explained by high-frequencies textures of these objects. For shoes, since objects are always on a white background, filtering has no effect. For instance in the competition all domains but shoes benefit from this filtering, as shown in Figure 5.

Finally and as shown in Figure 6, this filtering step significantly reduces the number of extracted descriptors, and lowers the computational complexity without penalty on performance. In most domains, τ gives comparable values of accuracy for a relatively large range of values. We favor a stricter filtering (larger value of τ) in order to reduces the computational cost of the subsequent Fisher vector computation, which linearly depends on the number of descriptors.

Classifiers training

SA and SB employ different strategies to train SVM hyperplane classifiers. SA uses a Stochastic Gradient Descent (SGD) solver and employs a resampling strategy that involves randomly sampling a given number of negatives for each positive sample [START_REF] Akata | Label-embedding for attribute-based classification[END_REF]. SB relies on the LASVM package [START_REF] Bordes | Fast kernel classifiers with online and active learning[END_REF]. In order to speed up training, we build for each class a training set consisting of all the positive samples, and a selection of negative samples. The selection is performed by computing for each negative sample the average similarity to all positive samples. Then, we rank all negative samples according to this average similarity, and select the ones that maximize it. The number of selected negative samples is a ratio of the number of positive samples. For the challenge, we use a ratio 40:1. This lead to an average of 2000 negative samples for each class.

Overview of optimization strategy

It is unfeasible to test all the possible combinations of the parameters, given that we rely on limited computational power. The number of parameters tested is bounded by the resources required to make this optimization. We performed a first set of preliminary experiments aimed at determining the typical range of interesting parameters, which were not too costly to compute. In particular, we selected k = 64 to limit the dimensionality of the vectors. Then, in order to reduce the cost of performing the whole cross-validation of all parameters jointly, we adopted the following order for the subsystem SB:

• Resolution to which the images are down-sampled ;

• Spatial coding (σ x and σ y ) jointly with filtering strategy (threshold τ) ; • Filtering threshold τ ;

• Vocabulary size k.

The cross-validation of these parameters is not done classwise, due to large risk of overfitting and of obtaining inconsistent scores across classes. Instead, we carried out the crossvalidation per-domain.

Note that our first pass of cross-validation demonstrated the need to cross-validate the parameters σ x and σ y jointly with the filtering threshold τ. The parameters τ and k have a strong impact on complexity: large τ filters more descriptors and therefore reduces the complexity, while large k increases the complexity. Considering both accuracy and these computational constraints, we finally fixed the parameters shown in Table 5. Note, for the domain shoes, σ x = σ y = 0 means that the spatial coordinate coding is not useful and was not used.

Late fusion strategy

The proposed system implements two fusion stages:

• The late fusion of the classification scores from the SIFTbased representation and the X-color-based representation to give the final scores for SA; • The late fusion of the scores from SA and SB.

In both cases, the fusion score s f is a linear combination of the score provided by the input systems, as s f = ws c1 + (1w)s c2 , where w is a value in in the range [0, 1], s c1 is the score from the first classifier and s c2 is the score from the second. Values of w were chosen via cross-validation on a per-domain basis. The resultant values for both tracks are shown in Figure 7. Note that the classification scores were not calibrated prior to late fusion so that w does not exactly correspond to the relative accuracy of each source of scores. However the weights are broadly consistent with the relative accuracy of each source of scores for a given domain.

Results

This section presents the official results obtained by our system compared to those of all other participants2 . For the submission, we have used the whole training set to train the SVM classifiers. For SB, we augment it by mirroring the images, as we assume that a mirrored image is also a valid instance of the target class. On our validation set, we validate that this choice increases the classification accuracy.

The results for Track 1 and Track 2 are shown in Tables 6 and7, respectively. As one can see, our whole system outperforms all others, including the methods that have used external data for training. We have also submitted separately SA and SB, in order to measure the individual performance of each subsystem, as well as the benefit of our choice to seek complementary methods.

The subsystem SA is better than SB for the domains birds and dogs. This is expected, as color is important for these domains, as already suggested by the cross-validated weights in the late fusion step 7. The inverse conclusion holds for the domain cars and shoes. This is also consistent with our crossvalidated weights. This is, in our opinion, mainly due to the use of larger vocabularies and the use of our filtering strategy in SB.

Other submissions to FGComp '13

Of the 9 participating teams, 5 had submissions which used deeply-learned features, including the CafeNet, VisionMetric, CognitiveVision, DPD Berkeley and Infor FG submissions. Each of these submissions required additional training data (for example the ImageNet dataset [START_REF] Deng | Imagenet: A large-scale hierarchical image database[END_REF]) in order to adequately learn the feature representations. As such, these methods have a nominal training advantage. Of the remaining 4 submissions, 3 used Fisher-based feature-representations (Inria-Xerox, Symbiotic and MPG) and one used an information graph building algorithm (InterfAIce).

Top-performing methods include that of the CafeNet team, whose submission was an implementation of the convolutionalneural-net-based system of Krizhevsky et al. [START_REF] Krizhevsky | Image classification with deep convolutional neural networks[END_REF]. The network was pre-trained with ImageNet 2012 data, and fine-tuned with FGComp data. The VisionMetric team used HOG features with LLC coding and combined these features with those from a pre-trained CNN. Distance metric learning provided a low-dimensional embedding. These two deeplearning methods achieved high performance but require very large amounts of training data, which was unavailable in this challenge, as is typical in fine-grained classification scenarios. This limited training data may have hampered their performance.

The Symbiotic team's submission was based on their stateof-the-art FGC system [START_REF] Chai | Symbiotic segmentation and part localization for fine-grained categorization[END_REF], which jointly trains part detection and segmentation models using training images and training bounding boxes. Fisher-encoded SIFT and color histograms were extracted from the foreground and each detected part and combined to form an image representation. Vertically-mirrored training images augmented the original training set. A key difference is the use of a small number of 256 Gaussians in [START_REF] Chai | Symbiotic segmentation and part localization for fine-grained categorization[END_REF].

The MPG submission was most similar to ours. However they used more low-level descriptors than we did, namely SIFT, RGB-SIFT, Opponent-SIFT, and C-SIFT. Their spatial pyramid was also more detailed (whole image + 4 quadrants + 3 horizontal strips). However, their visual vocabulary consisted of only 256 words, which in our experiments were not sufficient to encode subtle inter-class differences.

Conclusion

In this paper, we have described several adaptations to the Fisher vector which improve its performance in the FGC context. Our main recommendations for high-accuracy FGC are as follows. First, large vocabularies are important: dor most domains, the best performance is obtained with the largest mixture model and we did not observe any saturation. This suggests that better performance could be achieved by further increasing this size, although this would also raise computational issues. Second, properly cross-validating the power-normalization parameter is crucial in the FGC context. Third, patch filtering is a simple alternative to more complex object and part localization strategies [START_REF] Chai | Symbiotic segmentation and part localization for fine-grained categorization[END_REF]. Overall, these insights led us to establish a new state-of-the-art in FGC, as demonstrated by our winning participation in the FGComp challenge.

Fig. 1 .

 1 Fig. 1. Examples of aiplane classes. The system has to find the visual differences between these images, using only few training samples.

Fig. 4 .Fig. 5 .

 45 Fig. 4. Impact of the filtering step on the selected dense patches.

  Fig. 6. SB: Impact of the dense-SIFT filtering strategy on the average number of patches kept per image (images down-sampled to 100k pixels).

Fig. 7 .

 7 Fig. 7. Track 2: Cross-validated late fusion weights for systems SA (blue) vs SB (red).

Table 1 .

 1 FGComp 2013 challenge: statistics on number of classes, minimum/maximum and average numbers of labels per class.

				train examples		test
	domain classes min avg max	total	size
	aircraft	100	66	66	67	6667	3333
	bird	83	50	50	50	4150	4105
	car	196	24	41	68	8144	8041
	dog	120 198 221	302 26580 12000
	shoes	70	23	50	195	3511	1002

Table 2 .

 2 FGComp 2013 challenge: image properties on train set.

			image resolution (pixels)
	domain	min average std. dev.	max
	aircraft 330k	840k	270k	2M
	bird	100k	180k	20k 250k
	car	5k	480k	980k 21M
	dog	9k	190k	200k	8M
	shoes	307k	307k	0 307k

Table 3 .

 3 Comparison of our two sub-systems. Subsystem A (SA) is close to the Fisher classification pipeline described in Section 3. Subsystem B (SB), while also relying on Fisher vector, has been designed with the objective of being complementary with SA. A range of parameters indicate that we have cross-validated the parameter on a validation set (subset of training set).

		Subsystem				SA	SB
		Image (re-)sizing			100k pixels	100k-300k pixels
		dense sampling			every 3 pixels	every 3 pixels
		input descriptor		SIFT	X-color	SIFT
		desc. filtering		no	no	filter low-energy patches
		desc. post-processing sign(x) log(1 + |x|)	no	RootSIFT (Arandjelovic and Zisserman, 2012)
		desc. PCA			96	48	80
		vocabulary size k			1,024	1,024 -4,096
		spatial coding	spatial pyramid (Lazebnik et al., 2006): 1 × 1 + 3 × 1 spatial coordinate coding (Koniusz et al., 2013)
		classifier			Stochastic Gradient Descent (Bottou)	LASVM (Bordes et al., 2005), C = 100
		S A , Track 2, domain: birds	S B , Track 2, SIFT-Filter: τ=500
		0.6	SIFT			1	aircrafts
	mean accuracy	0.2 0.3 0.4 0.5	X-color			0.4 0.8 0.6	birds cars dogs shoes
		0.1				0.2
		0				0
		128	256	512	1024	64	1024 4096
			vocabulary size k			vocabulary size k

Fig.

2

. Impact of vocabulary size on performance. Left, for the SA standard pipeline with spatial pyramid coding (shown only for the 'bird' domain). Right, for SB (in this case, without spatial coding, images down-sampled to 100k pixels).

Table 5 .

 5 Track 1: Parameters fixed from cross-validation results and complexity constraints for SB.

			Track 1			Track 2
	domain	τ	σ x	σ y	k	τ	σ x	σ y	k
	aircraft 700 100 500 4k 800 100 500 4k
	birds	700	10	50 4k 900	75 100 4k
	cars	700	10	50 4k 900	-	-4k
	dogs	700	10	50 2k 600	-	-2k
	shoes	0	-	-1k	0	-	-1k

Table 6 .

 6 FGCOMP's Official results in Track 1. The asterisk * indicates that external data was used for learning. These runs are therefore not directly comparable.

	Team	Aircrafts Birds	Cars Dogs Shoes Overall
	Ours: SA +SB	81.46 71.69 87.79 52.90 91.52	77.07
	CafeNet*	78.85 73.01 79.58 57.53 90.12	75.82
	Ours: SA	75.88 66.28 84.70 50.42 88.63	73.18
	VisionMetric*	75.49 63.90 74.33 55.87 89.02	71.72
	Symbiotic	75.85 69.06 81.03 44.89 87.33	71.63
	Ours: SB	80.59 58.54 84.67 35.62 90.92	70.07
	CognitiveVision*	67.42 72.79 64.39 60.56 84.83	70.00
	DPD Berkeley*	68.47 69.58 67.40 50.84 89.52	69.16
	VisionMetric	73.93 51.35 69.31 38.63 87.33	64.11
	CognitiveVision	58.81 51.69 52.37 47.37 78.14	57.68
	MPG	9.45 54.57 69.27 42.92 88.42	52.93
	MPG	9.45 56.47 63.77	0.97 88.42	43.82
	Infor FG*	30.39	9.06	4.45	0.82 35.23	15.99
	InterfAIce	5.79	2.56	1.12	6.96	5.99	4.48

Table 7 .

 7 FGCOMP's official results in Track 2.

	Team	Aircrafts Birds	Cars Dogs Shoes Overall
	Ours: SA +SB	80.74 49.82 82.71 45.71 88.12	69.42
	Symbiotic	72.49 46.02 77.99 37.14 89.12	64.55
	Ours: SA	66.40 44.51 76.35 43.96 86.33	63.51
	Ours: SB	80.74 34.45 76.89 24.40 87.33	60.76
	DPD Berkeley*	45.51 42.70 43.38 41.91 59.98	46.70
	Infor FG*	9.66	5.75	3.71 32.71	4.69	11.30
	InterfAIce	5.43	2.58	1.17	6.94	5.29	4.28

http://www.birds.cornell.edu/nabirds/

Official results: https://sites.google.com/site/fgcomp2013

Acknowledgments

This work was supported by the Fire-ID project, funded by the French National Research Agency.


Raihan Muntasir

Rahman
email: mr2rahman@cs.uwaterloo.ca

Issam Aib
email: iaib@cs.uwaterloo.ca

Raouf Boutaba
email: rboutaba@cs.uwaterloo.ca

David R Cheriton

Survivable Virtual Network Embedding

Keywords: Survivability, Virtual Network Embedding, Network Virtualization

Network virtualization can offer more flexibility and better manageability for the future Internet by allowing multiple heterogeneous virtual networks (VN) to coexist on a shared infrastructure provider (InP) network. A major challenge in this respect is the VN embedding problem that deals with the efficient mapping of virtual resources on InP network resources. Previous research focused on heuristic algorithms for the VN embedding problem assuming that the InP network remains operational at all times. In this paper, we remove that assumption by formulating the survivable virtual network embedding (SVNE) problem and developing a hybrid policy heuristic to solve it. The policy is based on a fast re-routing strategy and utilizes a pre-reserved quota for backup on each physical link. Evaluation results show that our proposed heuristic for SVNE outperforms baseline heuristics in terms of long term business profit for the InP, acceptance ratio, bandwidth efficiency, and response time.

Introduction

Network virtualization has been proposed as a diversifying attribute of the future inter-networking paradigm that can enable seamless integration of new features to the current Internet resulting in rapid evolution of the Internet architecture [START_REF] Anderson | Overcoming the internet impasse through virtualization[END_REF][START_REF] Chowdhury | Network virtualization: state of the art and research challenges [topics in network and service management[END_REF][START_REF] Feamster | How to lease the internet in your spare time[END_REF]. By allowing multiple heterogeneous network architectures to cohabit on a shared physical infrastructure, network virtualization promises better flexibility, security, manageability and decreased power consumption for the Internet. In a network virtualization environment (NVE), the traditional role of the Internet Service Provider (ISP) has been divided into two separate entities: (1) the infrastructure providers (InP) who are responsible for deploying and maintaining physical network resources (routers, links etc.) and the (2) service providers (SP) who implement various network protocols and heterogeneous network architectures on virtual networks (VNs) composed from physical network resources leased from one or more infrastructure providers.

Virtual Network Embedding (VNE) is the central resource allocation problem in network virtualization. It deals with the efficient mapping of virtual networks onto physical network resources. More specifically, for each virtual network creation request, the VNE is responsible for mapping virtual nodes onto physical nodes and virtual edges onto one or more physical paths. The VNE problem, with constraints on virtual nodes and virtual links, can be reduced to the N Phard multi-way separator problem, even if the schedule of VN requests is known beforehand [START_REF] Andersen | Theoretical approaches to node assignment[END_REF]. Even when all the virtual nodes are already mapped, the virtual link embedding problem remains N P-hard. In order to reduce the hardness of the VN embedding problem and enable efficient heuristics, existing research has been restricting the problem space in different dimensions, e.g., considering the off-line version of the problem [START_REF] Lu | Efficient mapping of virtual networks onto a shared substrate[END_REF][START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF], ignoring either node or link requirements [START_REF] Fan | Dynamic topology configuration in service overlay networks -a study of reconfiguration policies[END_REF][START_REF] Lu | Efficient mapping of virtual networks onto a shared substrate[END_REF], assuming infinite capacity of the substrate nodes and links to obviate admission control [START_REF] Fan | Dynamic topology configuration in service overlay networks -a study of reconfiguration policies[END_REF][START_REF] Lu | Efficient mapping of virtual networks onto a shared substrate[END_REF][START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF], and focusing on specific virtual topologies [START_REF] Lu | Efficient mapping of virtual networks onto a shared substrate[END_REF]. Recently the authors in [START_REF] Chowdhury | Virtual network embedding with coordinated node and link mapping[END_REF][START_REF] Lischka | A virtual network mapping algorithm based on subgraph isomorphism detection[END_REF] have proposed VNE heuristics that combine the node and link embedding phases. The authors in [START_REF] Houidi | A distributed virtual network mapping algorithm[END_REF] have proposed a distributed algorithm that simultaneously maps virtual nodes and virtual links without any centralized controller. However, a limitation of all these heuristics is that they assume the substrate network to be operational at all times, which is not realistic. The existing heuristics are not capable of handling substrate node and link failures, which may lead to poor performance and increased frustration for the SP.

In this paper, we formulate the survivable virtual network embedding (SVNE) problem to incorporate single substrate link failures in VNE and propose an efficient heuristic for solving it. To the best of our knowledge, this is the first work to consider survivability strategies in the network virtualization environment.

The rest of the paper is organized as follows. Section 2 provides an overview of the related work. Section 3 formalizes the network model and formulates the virtual network embedding and survivable virtual network embedding problems. In Section 4, we present our proposed hybrid policy heuristic as a solution to the survivable virtual network embedding problem. Section 5 presents simulation results that evaluate the proposed hybrid policy heuristic compared to base-line heuristics. Section 6 concludes by identifying future research directions.

Related Work

Node and link failure survivability problems have been investigated extensively for optical and multi-protocol label switched (MPLS) networks [START_REF] Stern | Multiwavelength Optical Networks: A Layered Approach[END_REF], and real time systems [START_REF] Zheng | Fault-tolerant real-time communication in distributed computing systems[END_REF]. Our work differs in a number of aspects, due to unique challenges introduced by the network virtualization environment. First, the VNE problem is on-line in nature, whereas the survivable logical topology design problem in optical and mpls networks [START_REF] Kurant | Survivable Routing of Mesh Topologies in IP-over-WDM Networks by Recursive Graph Contraction[END_REF][START_REF] Lee | Cross-layer survivability in wdm-based networks[END_REF][START_REF] Thulasiraman | Circuits/cutsets duality and a unified algorithmic framework for survivable logical topology design in ip-overwdm optical networks[END_REF] is off-line. Secondly, in NVEs, we need to ensure that all virtual links are intact in the presence of failures. This restriction is not present, for example, in optical networks where the goal is to only ensure that all virtual nodes remain connected in the presence of failures, even if they are not connected via a direct virtual link. Our contribution also differs from existing work in terms of the objective formulation. Our aim is to develop a survivable virtual network embedding solution that simultaneously maximizes the long term revenue for the InP and, at the same time minimizes the long term penalty incurred by the InP due to service violations caused by failures. This dual nature of the objective function in the presence of failures is absent both in the existing research on optical and mpls networking domains and the existing VNE heuristics. Another novel aspect of our work is that we utilize path-flow based optimization formulations for solving the SVNE problem. The path formulation allows control over the characteristics of the paths selected for embedding and survivability against failures. For instance, we can directly control the total number of paths, number of hops per path, and impose delay constraints on virtual links for QoS purposes. This is not possible with a linkflow based formulation which has been used for the previous VNE heuristics [START_REF] Chowdhury | Virtual network embedding with coordinated node and link mapping[END_REF][START_REF] Lischka | A virtual network mapping algorithm based on subgraph isomorphism detection[END_REF][START_REF] Yu | Rethinking virtual network embedding: Substrate support for path splitting and migration[END_REF][START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF].

3 Problem Formulation

Substrate Network

We model the substrate network as a weighted graph G S (N S , E S ), where N S and E S represent the set of substrate nodes and links respectively. Each substrate node x ∈ N S has an associated cpu capacity cpu(x) and a geographical location value loc(x). A substrate link s = (s x , s y ) ∈ E S between substrate nodes s x , s y ∈ N S has a bandwidth capacity b(s). From now on, we denote the endpoints of any substrate link s as s x and s y .

Virtual Network Request

A Virtual Network (VN) request G V (N V , E V ) is also modeled as a weighted graph. VN requests are associated with constraints and QoS requirements embodied into service level agreements (SLA) [START_REF] Aib | On leveraging policy-based management for maximizing business profit[END_REF]. A virtual nodes y ∈ N V has a cpu capacity requirement cpu(y) and geographical location requirement loc(y). A virtual link v ∈ E V is characterized by a bandwidth capacity requirement b(v) and a delay constraint d(v). d(v) is used to preselect the set of admissible simple substrate paths that can be used to embed v. An example of a typical substrate network and two virtual network topologies are shown in figure 1. The numerical values beside the substrate nodes and links represent cpu and bandwidth constraints of those nodes and links respectively.

Resource Usage Metrics

We assume that substrate network resources are finite. As a result, the amount of residual substrate network resources diminishes as new VN requests are processed. We keep track of the residual substrate node and link capacities in order to make sure we don't accept a request unless there are adequate resources to serve it. The residual capacity of a substrate node x ∈ N S is defined as:

R N (x) = cpu(x) - y∈V (x) cpu(y), (1)
where V (x) denotes the set of virtual nodes mapped onto x. Similarly the residual capacity of a substrate link s ∈ E S is defined as:

R E (s) = b(s) - {v:∃p∈Γ E (v), s∈p} b(v), (2)
where, Γ E (v) defines the set of paths in the InP that are used to embed the virtual link v (Section 3.4). The residual capacity values are updated after each new VN request has been successfully mapped on top of the substrate network as long as there remains adequate residual resources. The values are also updated after a VN departs and link failure arrivals and departures.

In order to protect against single substrate link failures, we dedicate a certain percentage of bandwidth resources on each substrate link for backup purposes. For a substrate link s with total bandwidth b(s), α(s)b(s) bandwidth is reserved for primary flows, whereas β(s)b(s) is reserved for backup flows, where α(s) + β(s) = 1. The residual bandwidth measure is accordingly decomposed into primary and backup residual bandwidth measures R α (s) and R β (s) respectively. As a result, we need to keep track of these two residual bandwidth measures separately.

VN Embedding

The VN Embedding process refers to the mapping of the virtual network topology (logical topology) on top of the substrate network topology (physical topology) subject to certain constraints. The constraints are normally manifested in terms of the residual resource availability of the substrate network and the QoS parameters specified by the VN request. An example of a VN embedding can be seen in figure 1. From graph theoretic standpoint, the VN embedding process can be separated into two separate stages:

1-Node Embedding Phase: Each virtual node from a VN request is mapped to a single distinct substrate node by a one-to-one mapping:

Γ N : N V ← N S , (3)
such that Γ N (x) = Γ N (y), if f x = y ∀x, y ∈ N V , subject to the cpu capacity constraints: cpu(x) ≤ R N (Γ N (x)) ∀x ∈ N V .
2-Link Embedding Phase: Each virtual link is mapped to either an unsplittable substrate path or a splittable multi-commodity flow based set of multiple paths between the substrate nodes corresponding to the endpoints of the virtual link. Mathematically, we have a mapping:

Γ E : E V ← P S , (4)
such that ∀v = (v x , v y ) ∈ E V , and P S is the set of simple paths of G S . We have

Γ E (v) ⊆ P(Γ N (v x ), Γ N (v y )), subject to the bandwidth capacity con- straints: b(v) ≤ R E (p), ∀p ∈ Γ E (e V )
, where P(z, w) denotes the set of simple substrate paths between substrate nodes z and w, and R E (p) = min s∈p R E (s). For any virtual link v ∈ E V , we specify the set of QoS constrained substrate paths for v as P(v) = {p ∈ P S |delay(p) ≤ d(v)}.

Formulation of SVNE

We represent the input to SVNE as a tuple < G S , G V , j, l, {α(s)} s∈E S >, where G S and G V represent the substrate and virtual networks respectively, j represents the service class of the SP owning G V , l ∈ E S is the failed substrate link, and β(s) = 1α(s), such that β(s) represents the percentage of bandwidth on each substrate link s reserved for backups. Let Π(G V ) denote the revenue generated from G V , where

Π(G V ) = T (G V )[C 1 v∈E V b (v) + C 2 x∈N V cpu (x)] (5)
C 1 and C 2 are weight factors which represent the relative importance of bandwidth and cpu to the generated revenue respectively. T (G V ) represents the lifetime of the VN characterized by G V . Each service class j is associated with a penalty function S j (.), where S j (v) represents the monetary penalty incurred if the bandwidth contract of virtual link v is violated.

Let V denote the set of all virtual links affected by the failure of l. Then the expected total penalty incurred by the InP to the corresponding SP is:

X (G V ; l) = M T T R(l) v∈V∩E V S j (v) db(v) b(v) (6)
M T T R(l) is the mean time to repair for l. The difference between the bandwidth requested for v, and the actual bandwidth supplied by the InP is represented as db(v). Let G S 1 , G S 2 , G S 3 , . . . be the sequence of VN requests, and l 1 , l 2 , l 3 , . . . be the sequence of substrate link failure events. Then the objective of SVNE is to maximize long term business profit expressed as:

Π ∞ = ∞ p=1 ∞ q=1 [Π(G V q ) -X (G V q ; l p )] (7)

HYBRID Policy Heuristic for SVNE

We propose a hybrid policy heuristic for solving SVNE. The heuristic consists of three separate phases. In the first phase, before any VN request arrives, the InP pro-actively computes a set of possible backup detours for each substrate link using a path selection algorithm. Therefore, for each substrate link l, we have a set D l of candidate backup detours. The InP is free to utilize any path selection algorithm that suits its purposes, e. g. k-shortest path algorithm [START_REF] Topkis | A k shortest path algorithm for adaptive routing in communications networks[END_REF], column generation or primal dual methods [START_REF] Ahuja | Network Flows: Theory, Algorithms, and Applications[END_REF]. The second phase is invoked when a VN request arrives. In this phase, the InP performs a node embedding using existing heuristics [START_REF] Chowdhury | Virtual network embedding with coordinated node and link mapping[END_REF][START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF] and a multi-commodity flow based link embedding, that we denote as HYBRID LP LE. Finally, in the event of a substrate link failure, a reactive backup detour optimization solution HYBRID LP BDO is invoked which reroutes the affected bandwidth along candidate backup detours selected in the first phase. The pseudo-code for the hybrid policy is shown in the following algorithm (Figure 2). We now show the formulations of HYBRID LP LE and HYBRID LP BDO.

Formulation of HYBRID LP LE

In this phase we use a path flow based multi-commodity flow to embed all the virtual links simultaneously. For each pair (x, y) ∈ V S × V S , we have a set of preselected end-to-end paths P(x, y). For a virtual link v ∈ E V , we denote P(v) = P(v x , v y ) as the set of pre-selected QoS constrained simple paths for embedding v, where v x and v y are the end-points of v. Since the node embedding phase precedes the link embedding phase, we already know which virtual node is mapped to which substrate node. For any virtual link v = (x ′ , y ′ ) ∈ E V , we denote this as x ′ → Γ N (x ′ ) = x and y ′ → Γ N (y ′ ) = y. HYBRID LP LE can be expressed as the following linear program:

HYBRID LP LE -Objective Function Minimize v∈E V p∈P(v) b(p, v) (8)
Subject to -Primary Capacity Constraint

v∈E V p∈P(v) δ s (p)b(p, v) ≤ R α (s), ∀s ∈ E S . (9)
-Primary Bandwidth Constraint p,v) are stored and later used in the subsequent phase of the heuristic. 4. Constraint 9 is the primary capacity constraint which states that the total primary bandwidth allocated for all virtual links must be within the primary residual capacity of each substrate link. 5. Constraint 10 is the primary bandwidth constraint which specifies that the total bandwidth requirement of each virtual link must be distributed among all the QoS constrained paths allows for that virtual link.

p∈P(v) b(p, v) = b(v), ∀v ∈ E V (10)

Formulation of HYBRID LP BDO

HYBRID LP BDO can be expressed as the following linear program.

HYBRID LP BDO -Objective Function

Minimize

v∈E V S j (v) p∈P(v) δ l (p)⌈b(p, v)⌉[1 - d∈P l b(d, p, v) b(p, v) ] ( 11
)
Subject to -Backup Capacity Constraint

v∈E V ,p∈P(v),d∈D l ⌈b(p, v)⌉ δ s (d) b(d, p, v)δ l (p) ≤ R β (s)∀s ∈ E S (12)
-Recovery Constraint

d∈D l ,v∈E V ,p∈P(v) δ l (p) ⌈b(p, v)⌉ δ s (d) b(d, p, v) ≤ d∈D l ,v∈E V ,p∈P(v) δ l (p) b(p, v) (13)
Remarks 1. j represents the service class associated with the VN. Subsequently S j (v) denotes the penalty incurred for violating the bandwidth reservation for a virtual link v belonging to a VN of service type j. b(p, v), that is for the primary path p allocated for virtual link v. 5. The objective (equation 11) refers to the penalty function formulated in equation 6. 6. Constraint 12 is the backup capacity constraint which states that the total backup flow on all the detours passing through a substrate link must be within the backup residual capacity of that substrate link. 7. Constraint 13 is the recovery constraint and it signifies that the total disrupted primary bandwidth must be allocated along the precomputed set of detours. The objective function ensures that the virtual links that have higher penalty values will be given priority in the recovery constraint.

Both HYBRID LP LE and HYBRID LP BDO are linear programs, as a result our proposed HYBRID policy is a polynomial time heuristic for SVNE. Another important feature of HYBRID is that it decouples primary and backup bandwidth provisioning. As a result, we don't need complex disjoint constraints in our solution which would have resulted in a hard mixed integer program. The objective functions of HYBRID LP LE and HYBRID LP BDO jointly solve the long term objective of SVNE as expressed in equation 7.

Performance Analysis

In this section, we first describe our simulation environment, then present evaluation results. Our evaluation is aimed at quantifying the performance of the proposed HYBRID policy approach to SVNE in terms of long term business profit for the InP by maximizing revenue earned from VN's and minimizing the penalty incurred due to substrate link failures.

Simulation Environment

We implemented a discrete event simulator for SVNE adapted from our ViNE-Yard simulator [START_REF] Chowdhury | Virtual network embedding with coordinated node and link mapping[END_REF]. Since network virtualization is still not widely deployed, the characteristics of VN's and failure are not well understood. Specifically there are no analytical or experimental results on the substrate and virtual network topology characteristics, VN arrival dynamics or link failure dynamics in network virtualization. As a result, we use synthetic network topologies, and poisson arrival processes for VN's and link failures in our simulations. However our choice of substrate and virtual topologies and VN arrival process parameters are chosen in accordance with previous work on this problem [START_REF] Chowdhury | Virtual network embedding with coordinated node and link mapping[END_REF][START_REF] Yu | Rethinking virtual network embedding: Substrate support for path splitting and migration[END_REF]. We used glpk [START_REF] Makhorin | GNU Linear Programming Kit[END_REF] to solve the linear programs.

The substrate network topologies in our experiments are randomly generated with 50 nodes using the GT-ITM tool [START_REF] Topkis | A k shortest path algorithm for adaptive routing in communications networks[END_REF] in 25 x 25 grids. Each pair of substrate nodes is randomly connected with probability 0.5. The cpu and bandwidth resources of the substrate nodes and links are real numbers uniformly distributed between 50 and 100. We assume that both VN requests and substrate link failure events follow a Poisson process with arrival rates λ V and λ F . The ratio γ = λ F λ V is a parameter that we vary in our simulations. We use realistic values for M T T R(l) based on failure characteristics of real ISP networks [START_REF] Markopoulou | Characterization of failures in an operational ip backbone network[END_REF] which represent InP networks in a NVE. In each VN request, the number of virtual nodes is a uniform variable between 2 and 20. The average VN connectivity is fixed at 50%. The bandwidth requirement of a virtual link is a uniform variable between 0 and 50, and the penalty value S j (v) for a virtual link v is set to a uniform random variable between 2 and 15 monetary units. In our simulations, we set α(s) = α, ∀s belonging to the substrate network and vary α, where 0 ≤ α ≤ 1. For each set of experiments conducted, we plotted the average of 5 values for the performance metrics.

Comparison Method

Comparing our heuristics with previous work is difficult since the earlier heuristics do not consider substrate resource failures. As a result we evaluate our proposed hybrid policy against two base-line policies. The first one (we call it a blind policy) recomputes a new embedding for each VN affected by the substrate link failure. The second one is a proactive policy which pre-reserves both primary and backup bandwidth for each virtual link on link disjoint substrate paths. We omit details of these baseline policies due to space limitation. For node embedding, we use greedy [START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF] and DViNE heuristics [START_REF] Chowdhury | Virtual network embedding with coordinated node and link mapping[END_REF]. In our evaluation, we have compared six algorithms that combine different node embedding strategies [START_REF] Chowdhury | Virtual network embedding with coordinated node and link mapping[END_REF][START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF] with our proposed survivable link embedding strategies, namely, SVNE-Greedy-Hybrid, SVNE-DViNE-Hybrid, SVNE-Greedy-Proactive, SVNE-DViNE-Proactive, SVNE-Greedy-Blind, and SVNE-DViNE-Blind.

Evaluation Results

We use several performance metrics for evaluation purposes in our experiments. We measure the long term average profit earned by the InP by hosting VN's. The profit function depends on both the revenue earned from VN's by leasing resources and penalties incurred due to service disruption caused by substrate link failures. The penalty depends on both the amount of bandwidth violated due to a failure and the time it takes to recover from a failure as expressed in equations 6 and 7. We also measure the long term average acceptance ratio, percentage of backup bandwidth usage and response time to failures. We present our evaluation results by summarizing the key observations.

Acceptance ratio and Business profit: The hybrid policy leads to higher acceptance ratio and increased business profit in the presence of failures. Figures 3 shows the long term business profit against the percentage α of substrate link bandwidth for primary flows, while Figure 4 does it against the ratio of failure and VN rate γ. We notice that over the range of values for α and γ, the hybrid policy outperforms both the blind and proactive policies. Also the hybrid policy generates the highest profit at α = 80%, whereas the proactive and blind policies generate lesser profit with increased values of α. As α increases, there is less bandwidth available for backups on the substrate link and this hinders the performance of these policies. This also affects the hybrid policy, but it still has better performance due to its reactive nature. The profit and acceptance ratio for the blind policy drops more rapidly than the hybrid policy against increase in γ as shown in Figures 4 and6. Although, the profit for the proactive policy Responsiveness to Failures: The hybrid policy has faster reaction time to failures than its counterparts. In Figure 8, we notice that the hybrid policy reacts faster than the blind policy when a failure occurs. When a substrate link fails, the blind policy recomputes the entire embedding, which is time consuming. The hybrid policy, on the other hand, only re-routes the bandwidth of the affected virtual links which results in faster response time and ultimately lower penalty values for the InP.

Bandwidth Efficiency: The hybrid policy is bandwidth efficient. The proactive policy pre-reserves additional bandwidth for each virtual link during the instantiation phase. On the other hand, the hybrid policy does not pre-reserve any backup bandwidth during the link embedding phase. It pre-selects the candidate paths for re-routing and allocates backup bandwidth only when an actual failure occurs. As a result, the average bandwidth usage increases less rapidly with γ compared to the blind policy. This is shown in Figure 7.

Conclusion

In this paper, we have formulated the SVNE problem to incorporate substrate failures in the virtual network embedding problem. We have also proposed an efficient HYBRID policy heuristic to solve SVNE. To the best of our knowledge this is the first attempt to add survivability to virtual network embedding algorithms along with support for business profit oriented optimization. Moreover, our proposed heuristic can be extended to deal with multiple link failures, and subsequently combined with a node migration strategy [START_REF] Wang | Virtual routers on the move: live router migration as a network-management primitive[END_REF] to solve the single substrate node failure problem. However, there are a number of future research directions that can be pursued. Survivability in a multi-domain NVE could raise further challenges since it involves both intra and inter domain link failures. It would also be interesting to extend survivability to recursive NVE, where the first level VNs can act as InPs to a second level of VNs. Resource allocation, protection, and restoration issues in such recursive environments could be investigated under cross layer optimization or network utility maximization (NUM) frameworks.

Fig. 1 .

 1 Fig. 1. Mapping of VN requests onto a shared substrate network.

2 .

 2 ⌈x⌉ denotes the ceiling of x, that is ⌈x⌉ = 1 iff x > 0. So ⌈b(p, v)⌉ = 1 indicates that p is a path used for the embedding of v. Note that the b(p, v) values are calculated and stored in the HYBRID LP LE phase. 3. For the failed substrate link l, we have the set of candidate backup detours, D l = P(l x , l y ) \ {l}. 4. b(d, p, v) denotes the amount of rerouted bandwidth on detour d ∈ D l for

Fig. 3 . 4 .

 34 Fig. 3. Business profit against α Fig. 4. Business profit against γ

Fig. 5 . 6 .Fig. 7 . 8 .

 5678 Fig. 5. Acceptance ratio against α Fig. 6. Acceptance ratio against γ

  The objective function 8 corresponds to the revenue function Π for the VN. 3. b(p, v) is the amount of bandwidth allocated on path p for virtual link v. A strictly positive value for b(p, v) will indicate that p is a substrate path used for v. The values of b(

Remarks 1. δ s (p) is the link-path indicator variable, that is, δ s (p) = 1 if s ∈ p, 0 otherwise. 2.

Acknowledgment

This work was jointly supported by the Natural Science and Engineering Council of Canada (NSERC) under its Discovery program, Cisco Systems, and WCU (World Class University) program through the Korea Science and Engineering Foundation funded by the Ministry of Education, Science and Technology (Project No. R31-2008-000-10100-0).


Nabeel Farooq Butt

Mosharaf Chowdhury
email: mosharaf@cs.berkeley.edu

Raouf Boutaba
email: rboutaba@uwaterloo.ca

David R Cheriton

Topology-Awareness and Reoptimization Mechanism for Virtual Network Embedding

Keywords: Topology-awareness, Re-embedding, Virtual Network Embedding, Network Virtualization

Embedding of virtual network (VN) requests on top of a shared physical network poses an intriguing combination of theoretical and practical challenges. Two major problems with the state-of-the-art VN embedding algorithms are their indifference to the underlying substrate topology and their lack of reoptimization mechanisms for already embedded VN requests. We argue that topology-aware embedding together with reoptimization mechanisms can ameliorate the performance of the previous VN embedding algorithms in terms of acceptance ratio and load balancing. The major contributions of this paper are twofold:

(1) we present a mechanism to differentiate among resources based on their importance in the substrate topology, and (2) we propose a set of algorithms for reoptimizing and re-embedding initially-rejected VN requests after fixing their bottleneck requirements. Through extensive simulations, we show that not only our techniques improve the acceptance ratio, but they also provide the added benefit of balancing load better than the previous proposals.

Introduction

Network virtualization is widely considered to be a potential candidate for providing the essential basis for future Internet architectures [START_REF] Anderson | Overcoming the internet impasse through virtualization[END_REF][START_REF] Turner | Diversifying the internet[END_REF][START_REF] Feamster | How to lease the Internet in your spare time[END_REF][START_REF] Chowdhury | A survey of network virtualization[END_REF]. One major challenge in network virtualization environment (NVE) is the allocation of substrate network resources, managed by infrastructure providers (InPs), to online VN requests by different service providers (SPs) [START_REF] Feamster | How to lease the Internet in your spare time[END_REF][START_REF] Chowdhury | A survey of network virtualization[END_REF]. Unfortunately, the VN embedding problem reduces to the multi-way separator problem, which has been shown to be N P -hard [START_REF] Andersen | Theoretical approaches to node assignment[END_REF]. From the point of view of an InP, a preferable allocation scheme should increase long-term revenue while reducing the cost of hosting individual VNs. Consequently, mechanisms that can increase acceptance ratio are of great interest to InPs, because acceptance ratio is directly proportional to their revenue.

While embedding a VN request, existing proposals [START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF][START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF][START_REF] Chowdhury | Virtual network embedding with coordinated node and link mapping[END_REF][START_REF] Lu | Efficient mapping of virtual networks onto a shared substrate[END_REF][START_REF] Houidi | A distributed virtual network mapping algorithm[END_REF] do not distinguish between different substrate nodes and links. However, in practice, some substrate nodes and links are more critical than others. For example, resource depletion in bridges and articulation points in the substrate topology are expected to have deeper impact on future embeddings than a random resource near the edge of the network. Choosing amongst feasible VN embeddings, the one that uses fewer critical resources can be a key to improving acceptance ratio in the long run.

In this paper, we investigate how differentiating between substrate resources can increase the acceptance ratios of the existing VN embedding algorithms [START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF][START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF][START_REF] Chowdhury | Virtual network embedding with coordinated node and link mapping[END_REF][START_REF] Lu | Efficient mapping of virtual networks onto a shared substrate[END_REF][START_REF] Houidi | A distributed virtual network mapping algorithm[END_REF]. For differentiating resources, we design a mechanism for assigning weights to substrate nodes and links based on their residual capacities and their importance in the substrate topology. These weights help us in prioritizing certain VN embeddings over others. Other than links' or nodes' resource depletion being able to partition the network, attributes of the created partitions are also an important factor in weight assignment. In case of a substrate network partitioning, any virtual link from a VN request has to be turned down if its two ends can only be mapped in different partitions. We argue that distinguishing substrate resources is a key for better load balancing and for ameliorating the acceptance ratio.

Over time, as new VNs are embedded and old ones expire, resources in the substrate network become fragmented. The obvious consequence is the rejection of many VN requests lowering the acceptance ratio and revenue. This could be amended had the fragmented resources been consolidated using reoptimization techniques. We propose algorithms for identification and re-embedding of VNs that cause VN request rejection. Our reoptimization mechanism consists of two stages: detection of bottleneck links and nodes, followed by relocation of virtual links and nodes to free up resources on bottlenecks.

The remainder of this paper is organized as follows. Section 2 summarizes background and related work. Our proposals for distinguishing and reoptimizing critical resources are discussed in Section 3. Section 4 presents performance metrics, our experimental setup, and their results. We conclude in Section 5.

Background and Related Work

The intra-domain VN embedding problem refers to the mapping of VN requests from different SPs on top of substrate network resources managed by an InP. A substrate network in this problem formulation is defined as an undirected graph with substrate nodes and links with CPU and bandwidth capacities, respectively. Similarly, a VN request is defined as an undirected graph with virtual nodes and links with CPU and bandwidth requirements and additional constraints.

The long-term objective of a VN embedding algorithm is to maximize the revenue of an InP while minimizing its cost of embedding online VN requests.

Any virtual node can be embedded onto at most substrate node, whereas a virtual link can refer to a physical path in the substrate network. Further details on the basic VN embedding problem formulation can be found in [START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF][START_REF] Chowdhury | Virtual network embedding with coordinated node and link mapping[END_REF].

Allocating resources for Virtual Private Networks [START_REF] Gupta | Provisioning a virtual private network: A network design problem for multicommodity flow[END_REF][START_REF] Ricci | A solver for the network testbed mapping problem[END_REF] is the earliest, but simpler, incarnation of the VN embedding problem. It is different in its consideration of only the bandwidth constraints on virtual links. Since constraints on virtual nodes are ignored, this problem often simplifies to selecting paths that satisfy the given constraints.

VN embedding proposals in the existing literature address the problem by simplifying constraints in different dimensions. Szeto et al. [START_REF] Szeto | A multi-commodity flow based approach to virtual network resource allocation[END_REF] have presented algorithms for embedding only the virtual links, with an assumption that the virtual nodes have already been mapped. Off-line version of the VN embedding problem had been the focus of some of the existing research [START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF][START_REF] Lu | Efficient mapping of virtual networks onto a shared substrate[END_REF]. Precluding admission control complexities by assuming infinite capacities of substrate nodes and links have been addressed in [START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF][START_REF] Lu | Efficient mapping of virtual networks onto a shared substrate[END_REF][START_REF] Fan | Dynamic topology configuration in service overlay networks: A study of reconfiguration policies[END_REF]. Lu et al. [START_REF] Lu | Efficient mapping of virtual networks onto a shared substrate[END_REF] have developed algorithms for specific topologies. Yu et al. [START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF] have provided a two stage algorithm for mapping the VNs. They start off by mapping the virtual nodes first and then proceed to map the virtual links using shortest paths and multi-commodity flow (MCF) algorithms. Chowdhury et al. [START_REF] Chowdhury | Virtual network embedding with coordinated node and link mapping[END_REF] have recently presented a solution to the VN embedding problem by coordinating the node and the link mapping phases. by using mixed integer programming formulation. Backtracking algorithms in conjunction with graph isomorphism detection to map VN requests are used in a dynamic fashion in [START_REF] Lischka | A virtual network mapping algorithm based on subgraph isomorphism detection[END_REF]. Distributed algorithms for simultaneously embedding virtual links and virtual nodes [START_REF] Houidi | A distributed virtual network mapping algorithm[END_REF] have shown issues with scalability and poorer performance than their centralized counterparts.

Although all these approaches strive for improving VN embedding by various degrees, none of them foresee the possibility of narrowing down the chances for accepting future VN requests. They treat all the substrate nodes and links equally, which is not practical. Their indifference to the underlying topology, allows uninformed decisions while mapping resources on 'critical' substrate links and nodes that can affect the acceptance ratio in the future. Another potential candidate for improving the accepting ratio is the effective use of reoptimization mechanisms. By detecting and relocating bottleneck link and node embeddings to better alternates, we can achieve improvements. Ideally, we want to keep all the VNs optimized at all times (e.g., through periodic updating [START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF]). But this will result in relocation of a lot of virtual links and virtual nodes and incur significant overhead. A better way to deal with this problem is to take action only when it is inevitable [START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF]. However, unlike [START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF], we propose algorithms for relocation of virtual nodes as well as links.

Before proceeding to the next section, we want to mention that we use the same formulation for revenue as in the previous literature [START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF][START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF][START_REF] Chowdhury | Virtual network embedding with coordinated node and link mapping[END_REF], but in up-coming sections we will provide a slightly better cost function.

Indifference to the attributes of the substrate network resources and lack of reoptimization mechanisms are the two major candidates for improvement in the existing VN embedding algorithms [START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF][START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF][START_REF] Chowdhury | Virtual network embedding with coordinated node and link mapping[END_REF][START_REF] Lu | Efficient mapping of virtual networks onto a shared substrate[END_REF][START_REF] Lischka | A virtual network mapping algorithm based on subgraph isomorphism detection[END_REF]. In the following sections, we present techniques to incorporate topology-awareness and reoptimization mechanisms for bottleneck embeddings in these algorithms to improve their overall performance.

Topology-Aware Embedding

We differentiate between substrate network resources by introducing scaling factors to their costs. The scaling factor (SF) of a resource refers to its likelihood of becoming a bottleneck. It is calculated as a combination of two weight factors, critical index and popularity index, explained later in this section.

We aim to incorporate topology-awareness in existing algorithms with minimal changes. In our solution, proposals using MCF only need to update their objective functions (constraints require no change) and proposals using shortest path algorithms should select paths with minimum total scaled costs to upgrade themselves.

Critical Index

The first weight function we define is the critical index (CI) of a substrate resource. The CI of a resource measures the likelihood of a residual substrate network partition4 due to its unavailability. To understand the impact of such partitioning, consider the following scenario: suppose that a substrate network is partitioned into two -almost equal-sized -components. The probability of both the end nodes of any new virtual link to be embedded in different partitions is 0.5. In this case, we might have to reject almost 50% of the VN requests.

We denote CI by ζ (ζ : x → [0, 1)), where x is either a substrate link or a node. Higher value of ζ(x) means its highly likely that unavailability of x will partition the substrate graph and vice versa. The mathematical definition of CI is given in equations 1 and 2 for links and nodes respectively.

ζ(e S ) =          1 -|c 1 -c 2 | 2 + 1 2 e S ∈ cut-edges φ + ψ 4 e S / ∈ cut-edges (1) ζ(n S ) =              1 2 c∈C P {c} 1 |C| + 1 2 n S ∈ cut-vertices φ + ψ 4 n S / ∈ cut-vertices (2)
In equation 1, if e S is a bridge (cut-edge) then removing it partitions the graph. c 1 and c 2 are the fractions of substrate nodes in each of these partitions. When e S is not a bridge, then after removing it we get φ and ψ, where φ and ψ are the fractions of new cut-nodes or cut-edges to the total cut-nodes or cutedges respectively. In equation 2, C is the set of components we get when we remove n S . P {c} here is the fraction of nodes present in c. In both equations 1 and 2, we make sure that a cut-resource has its CI value ≥ 0.5. Computing ζ is required only once in the beginning and it is updated whenever a substrate network is extended. Also, it is not computationally intensive.

Popularity Index Resource saturation is the other major factor that can cause substrate network partition. Popularity Index (PI) measures "how many different VNs are affected when a link or a node is unavailable?" To be more specific, PI (ρ : x → [0, 1)) is the time weighted average of occupied resources on a particular link or a node. It also takes into account the number of VNs that are mapped on that resource. In equation 3, R Ei-1 is the percent of reserved bandwidth on link x, where the index i -1 means the previous value of R E ; similarly, R Ni-1 is the percent of reserved CPU capacity at the node x. The variables a and b (a + b = 1) are used to assign different weights to current and previous values. In equation 3, ν is the number of VNs mapped on top of x. The higher the value of ρ the higher the probability that mapping onto this link or node will saturate it and create a bottleneck.

ρ(x) =              aR Ei-1 + bR Ei 1 ν x ∈ E S aR Ni-1 + bR Ni 1 ν x ∈ N S (3)
Scaling Factor Both CI and PI values are very crucial when mapping a particular link or node. Together they are referred to as the scaling factor and denoted by ℵ. In equation 4, we have multiplied both CI and PI by α and β respectively. We also use ω, which is a parameter and can be used to further tune the cost. The objective functions of the LP formulations of previous proposals [START_REF] Chowdhury | Virtual network embedding with coordinated node and link mapping[END_REF] can be updated by scaling the cost of resources by ℵ. We use a slightly different cost function, C(G V ), than that of the previous literature. In the modified formula, we are scaling up the cost by the scaling factor to avoid embedding onto critical resources whenever possible. In the formula below, n S is the substrate node on which a virtual node n V is mapped, f e V e S is the flow on substrate link e S for the virtual link e V , and c(n V ) is the cost of the virtual node n V .

ℵ(x) = 1 + ω αζ(x) + βρ(x) (4)
C(G V ) = e V ∈E V e S ∈E S ℵ(e S )f e V e S + n V ∈N V ℵ(n S )c(n V ) (5)

Reoptimizing Bottleneck Embeddings

Although efficient algorithms exist for embedding of VNs onto a substrate network, arbitrary lifetimes of VNs can cause some embeddings to drift toward inefficiency over time. Such embeddings can be reoptimized by relocating virtual nodes and reassigning virtual links to better alternate embeddings. From a practical point of view, it has been shown how to migrate virtual nodes (virtual routers) from one physical node to another [START_REF] Wang | Virtual routers on the move: Live router migration as a networkmanagement primitive[END_REF]. Link migration can also be achieved by dynamically setting up and tearing down physical links; it is already achieved using programmable transport networks [START_REF]Routerfarm: towards a dynamic, manageable network edge[END_REF].

Our proposed solution can be divided into two stages. First, we detect the virtual links and nodes that caused a VN request to be rejected. Second, we relocate/reassign these nodes/links to less critical regions of the substrate network. We illustrate the basic idea behind our relocation and reassignment mechanism using the example in Fig. 1 and Fig. 2. In Fig. 1 (a), VN request VN-6 is being rejected because one of its virtual nodes cannot be mapped, i.e., node U which requires 43% of CPU capacity. There are three possible embeddings for this node (i.e., nodes a, b, and c), but none with the required capacity for U. In Fig. 1 (b), relocating a VN-1 node from node a to node c makes enough room to accommodate U. All the associated virtual links of VN-1 are also reassigned to the new location. Now suppose that we want to embed a virtual link U-V. We can see that it cannot be mapped because of the bottleneck substrate link w-z (Fig. Algorithm 1 Detecting V-Nodes that cannot be mapped for all substrate node n ∈ C N S (vn) do 5:

L low ← All virtual nodes mapped on n that have lower priority than V N rej 6:

if capacity(L low ) > required capacity then 7:

Save (n, L low ), for relocating later 8:

end if 9:

end for 10:

fails if vn cannot be fixed 11: end for (a)). As shown in Fig. 2 (b), VN-2 is reassigned to free up some bandwidth on the substrate link w-z so that the virtual link U-V can be accommodated.

Detecting Bottleneck Nodes and Links For bottleneck detection, we deal with VN requests that cannot be embedded due to lack of residual capacities in substrate resources. Contrary to the periodic reconfiguration scheme presented in [START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF], we have taken a reactive approach in detecting bottlenecks -we reoptimize whenever a VN request gets rejected.

Algorithm 1, finds a list of virtual nodes that cannot be mapped, and for each one of them it stores corresponding bottleneck substrate nodes. After detecting the candidate substrate nodes for an unmapped virtual node, it figures out whether enough capacity can be salvaged on any of the candidate nodes or actually on L low . L low is the set of virtual nodes of other VN requests with less priority than the rejected VN request. If a single virtual node cannot be mapped we do not proceed any further. Finally, L low and associated substrate node n Algorithm 2 Detecting V-Links that cannot be mapped 1: L bad ← All virtual links v such that MaxFlow(v) < ReqCap(v) 2: for all virtual links v ∈ L bad do 3: repeat 4:

for all substrate link e ∈ M inCut(v) do 5:

L low ← All virtual links mapped on e that have lower priority than V N rej 6:

Save (e, L low ) 7:

end for 8:

until Capacity(M inCut(v)) < ReqCapacity(v) 9:

fails if v cannot be fixed 10: end for are stored for later use in the relocation phase. The worst case running time of algorithm 1 is O(n 2 ), but on the average it would be much faster than that.

Next, we use algorithm 2 to determine the unmapped virtual links, L bad , and corresponding bottleneck links. A virtual link is rejected if there is not enough capacity between its two end nodes. The maximum flow from the source to the sink 5 and the minimum s-t cut can be computed in O(V 3 ) using the Edmond-Karp maximum flow algorithm [START_REF] Diestel | Graph theory[END_REF]. Algorithm 2 iterates through L bad and for every virtual link it finds the minimum cut 6 . Re-assigning some virtual links on the minimum cut can increase the maximum flow between source and sink. Note that even if we made enough room in the first minimum cut it might still not guarantee the required flow between the source and the sink. Since the minimum cut can change over time, we have to iteratively compute the minimum cut. To keep the running time of algorithm 2 small, we repeat this only a constant number of times. Next we re-assign links in L low to free up some capacity on these links. It is useless to proceed if we fail to map only a single virtual link; in this case, we can just reject this request immediately.

Nodes & Links Selection and Placement Algorithm 3, relocates a virtual node v n which is currently mapped on a substrate node s n to some other substrate node, provided all the virtual links incident on v n can also be reassigned. Q vn is a set of virtual nodes adjacent to v n and C vn is a list of substrate nodes which are potential hosts for v n . Note that C vn is sorted according to the overhead cost. The algorithm iterates on C vn and for every substrate node n in C vn , it checks whether it can map all the virtual links after v n is relocated to n. If it can map all these links then v n can be relocated to the substrate node used to map these links; finally, it relocates v n .

For reassigning a virtual link, algorithm 4 takes the virtual link e V which is mapped to substrate link e S . First it sets the available bandwidth on e S to zero, so that the freed capacity on e S is not allocated to e V , when e V is reassigned. It then finds the maximum flow between the end nodes of e V and if its zero 5 Source and sink are the end nodes of the rejected virtual link. 6 For information on Max-Flow Min-Cut theorem, readers are referred to [START_REF] Diestel | Graph theory[END_REF]. Re-embed virtual link eV 9: else 10:

Algorithm 3 Relocating a Virtual Node

1: Q vn = v-
Free c amount of flow from eS 11:

Augment c amount of flow elsewhere 12: end if 13: Restore and Adjust RE(eS) 14: return true than nothing can be done. If the maximum flow is greater than the required bandwidth capacity of the link e V then it just free the old mapping of e V and remaps it again. If the maximum flow is less than the required capacity then we can free c amounts of capacity from e S and map c units of capacity elsewhere by using the computed flow. Finally, we restore and adjust the freed bandwidth capacity on e S (which was set to zero at the beginning). These link mappings should be done using topology-aware LP formulation, to keep the overhead cost of reassigning e V to minimum.

Evaluation

Our evaluation focuses primarily on quantifying the effectiveness of our techniques when applied to the VN embedding algorithms in the existing literature. We consider the following four algorithms in our evaluation: D-ViNE and R-ViNE [START_REF] Chowdhury | Virtual network embedding with coordinated node and link mapping[END_REF] map nodes deterministically and randomly, respectively; in both the algorithms, links are embedded using a modified MCF. G-SP [START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF] and G-MCF [START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF] both use greedy node mapping; for link embedding, the former uses shortest path algorithm, whereas the latter uses MCF.

Experimental Setup and Performance Metrics

We have extended the simulator of [START_REF] Chowdhury | Virtual network embedding with coordinated node and link mapping[END_REF] to include our proposed techniques and algorithms. We have used GT-ITM [START_REF] Zegura | How to model an Internet[END_REF] for generating topologies for the underlying substrate networks. Substrate networks in our experiments have 100 nodes and around 400 links, on the average. Node CPU capacities and link bandwidth capacities are randomly chosen between 50 to 100. For VN requests, we used a similar setup as previously used in [START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF][START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF][START_REF] Chowdhury | Virtual network embedding with coordinated node and link mapping[END_REF]. VN requests arrive in a Poisson process with an inter-arrival time of 20 time units. Lifetimes of the VN requests follow an exponential distribution with mean 1000 time units. Virtual nodes for VN requests are chosen uniformly between 5 to 10. CPU and bandwidth requirements are distributed uniformly between 0 to 20 and 0 to 50 respectively. The metrics we use to measure performance are increase in acceptance ratio, revenue-cost ratio, incurred cost, and distribution of utilization of resources.

Evaluation Results

Improvement in Acceptance Ratio In our first set of experiments, we compare the increase in acceptance ratios of all the algorithms. As shown in Fig. 3, in steady state, our mechanisms improve acceptance ratios by almost 40% for G-MCF and just below 35% for G-SP. For D-ViNE and R-ViNE, the improvements are smaller but still a sizeable 17%. We believe that the lower increase for D-ViNE and R-ViNE is due to the fact that they already have much higher acceptance ratio than G-SP and G-MCF without the proposed improvements [START_REF] Chowdhury | Virtual network embedding with coordinated node and link mapping[END_REF].

Revenue/Cost Ratio We present the per request revenue/cost ratio for the compared algorithms in Fig. 4. We see that quite a few readings are close to zero which indicates that those VN requests are being mapped to one or more very critical links or nodes. On the average, the revenue/cost ratio of D-ViNE and R-ViNE is slightly above 2 for 90% of the accepted VN requests, which is significantly higher than that of G-SP and G-MCF. This shows that our techniques not only improve the acceptance ratios (Fig. 3), but they also keep the revenue/cost ratio within acceptable range (specially for D-ViNE and R-ViNE).

Acceptance Ratio vs Incurred Cost An important factor in evaluating the effectiveness of our techniques is the cost incurred by increasing the acceptance ratio. In Fig. 5, we have plotted the percentage increase in acceptance ratio against the percentage increase in cost for making room for these VN requests. Here the incurred cost is the sum of the cost of moving already embedded VN requests and accepting VN requests rejected earlier. Fig. 5 shows that the maximum increase in cost is close to 250%, but the range of acceptance ratio improvement varies from 7 -77% for various algorithms. For all the algorithms there are several readings with very low or even zero incurred cost. This is because the VNs required to move to make room for rejected VN requests have a lot of alternative embeddings of equal cost and incurred no additional cost.

Differentiating Resources In Fig. 6, we have plotted the CDF of the scaling factors of all links and nodes for R-ViNE [START_REF] Chowdhury | Virtual network embedding with coordinated node and link mapping[END_REF] and R-ViNE incorporated with topology-aware embedding (hereinafter referred to as "TA-R-ViNE"). The other algorithms, compared with their extended versions, also show similar characteristics. SF is a good measure because it gives an indication of potential bottlenecks; an SF value close to 1 means that a resource is more likely to become a bottleneck. We can see here that TA-R-ViNE has significantly fewer resources being indicated as bottlenecks than R-ViNE. With TA-R-ViNE, only 15% resources have SF values above 0.4; whereas with R-ViNE, it is almost 35%. This graph shows that topology-awareness plays a significant role in identifying bottlenecks.

Link and Node Utilization A comparison between link utilization of TA-R-ViNE and R-ViNE is shown in Fig. 7. It presents an average of multiple runs of carefully designed experiments that made sure that both techniques could map the same VN requests. We can see that for R-ViNE, almost 90% of the links are utilizing less than 25% of bandwidth, whereas for TA-R-ViNE it is almost 80%. An explanation would be that these links are alternative links to bottlenecks; hence they are used more often. We can also see that TA-R-ViNE used almost 8% fewer substrate links than R-ViNE. In Fig. 8, almost 50% of the nodes have less utilization than 50% of the nodes mapped by TA-R-ViNE, but the other 50% have much higher utilization. This figure shows that to avoid bottlenecks TA-R-ViNE has distributed load among nodes.

Conclusion

In this paper, we have presented mechanisms for differentiating various resources (links and nodes) according to their impact on the connectivity of the substrate network, and their utilization coupled with the number of VNs utilizing them. We have also proposed algorithms for reoptimizing the already embedded VN requests in order to improve the overall acceptance ratio. Through simulation we have shown that our techniques significantly improve the performance of the existing algorithms in terms of increase in acceptance ratio, revenue-cost ratio, cost incurred by these techniques and load balancing based on criticalness of resources. Experimental results endorse the fact that our techniques have enough potential to be seriously considered as an integral part of any future VN embedding algorithm design.

Fig. 1 .

 1 Fig. 1. Relocating a virtual node of VN-1 to make room for virtual node U

2

 2

Fig. 2 .

 2 Fig. 2. Reassigning links to make room for virtual link

1 :

 1 R E (eS) = 0 2: (u, v) be the virtual nodes of eV 3: c = M axF low(u, v) 4: if c = 0 then 5:return false 6: end if 7: if ReqCap(eV ) <= c then 8:

Fig. 3 .Fig. 4 .

 34 Fig. 3. Improvement in Acceptance Ratios for Different Algorithms

Fig. 5 .Fig. 6 .

 56 Fig. 5. Acceptance Ratio vs Incurred Cost

Fig. 8 .

 8 Fig. 8. Average node utilization

  nodes that are adjacent to vn 2: C vn = candidate s-nodes for vn 3: status = false 4: for all substrate node n ∈ C vn do

	5:	status = true
	6:	for all virtual link v ∈ Q vn do
	7:	Map-Link(Substrate(v), vn)
	8:	if map fails then
	9:	status = false
	10:	break
	11:	end if
	12:	end for
	13:	if status then
	14:	Relocate vn to n
	15:	end if
	16: end for
	Algorithm 4 Reassigning a Virtual Link

We refer to residual substrate network while discussing partitioning in this paper. A residual substrate network is composed of residual capacities of substrate resources.

Acknowledgment

This work was jointly supported by the Natural Science and Engineering Council of Canada (NSERC) under its Discovery program, Cisco Systems, and WCU (World Class University) program through the National Research Foundation of Korea funded by the Ministry of Education, Science and Technology (Project No. R31-2008-000-10100-0).