Fabian M Suchanek
email: fabian@xsuchanek.name

Serge Abiteboul
email: serge.abiteboul@xinria.fr

Pierre Senellart
email: pierre@xsenellart.com

Ontology Alignment at the Instance and Schema Level

Keywords: Algorithmique, programmation, logiciels et architectures Alignment, Ontology, Disambiguation, RDFS, Instances, Relations Alignement, Ontologie, Désambiguation, RDFS, Instances, Relations

We present PARIS, an approach for the automatic alignment of ontologies. PARIS aligns not only instances, but also relations and classes. Alignments at the instance-level cross-fertilize with alignments at the schemalevel. Thereby, our system provides a truly holistic solution to the problem of ontology alignment. The heart of the approach is probabilistic. This allows PARIS to run without any parameter tuning. We demonstrate the efficiency of the algorithm and its precision through extensive experiments. In particular, we obtain a precision of around 90% in experiments with two of the world's largest ontologies.

Introduction

Motivation. An ontology is a formal collection of world knowledge. In this paper, we use the word ontology in a very general sense, to mean both the schema (classes and relations), and the instances with their assertions. In recent years, the success of Wikipedia and algorithmic advances in information extraction have facilitated the automated construction of large general-purpose ontologies. Notable endeavors of this kind include DBpedia [START_REF] Auer | DBpedia: A Nucleus for a Web of Open Data[END_REF], KnowItAll [START_REF] Etzioni | Web-scale information extraction in KnowItAll (preliminary results)[END_REF], WikiTaxonomy [START_REF] Ponzetto | Deriving a large-scale taxonomy from Wikipedia[END_REF], and YAGO [START_REF] Suchanek | YAGO: A core of semantic knowledge. Unifying WordNet and Wikipedia[END_REF], as well as commercial services such as freebase.com, trueknowledge.com, and wolframalpha.com. These ontologies are accompanied by a growing number of knowledge bases1 in a wide variety of domains including: music2 , movies3 , geographical data4 , publications 5 , medical and biological data 6 , or government data 7 .

Many of these ontologies contain complementing data. For instance, a general ontology may know who discovered a certain enzyme, whereas a biological database may know its function and properties. However, since the ontologies generally use different terms (identifiers) for an entity, their information cannot be easily brought together. In this respect, the ontologies by themselves can be seen as isolated islands of knowledge. The goal of the Semantic Web vision is to interlink them, thereby creating one large body of universal ontological knowledge [START_REF] Bizer | Web of linked data. A global public data space on the Web[END_REF][START_REF] Bizer | Linked data on the Web[END_REF]. This goal may be seen as a much scaled-up version of record linking, with challenges coming from different dimensions:

• unlike in record linkage, both instances and schemas should be reconciled;

• the semantics of the ontologies have to be respected;

• the ontologies are typically quite large and complex. Moreover, we are interested in performing the alignment in a fully automatic manner, and avoid tedious tuning or parameter settings.

A number of recent research have investigated this problem. There have been many works on entity resolution (i.e., considering the A-Box only) [START_REF] Ferrara | Automatic identity recognition in the semantic web[END_REF][START_REF] Noessner | Leveraging terminological structure for object reconciliation[END_REF][START_REF] Saïs | L2R: A logical method for reference reconciliation[END_REF][START_REF] Saïs | Combining a logical and a numerical method for data reconciliation[END_REF][START_REF] Tummarello | .ma: live views on the web of data[END_REF][START_REF] Hogan | Some entities are more equal than others: statistical methods to consolidate linked data[END_REF][START_REF] Hu | A self-training approach for resolving object coreference on the semantic Web[END_REF]. In another direction, much research has focused on schema alignment (i.e., considering the T-Box only) [START_REF] Gracia | Large scale integration of senses for the semantic Web[END_REF][START_REF] Jean-Mary | Ontology matching with semantic verification[END_REF][START_REF] Aumueller | Schema and ontology matching with COMA++[END_REF][START_REF] Isaac | An empirical study of instance-based ontology matching[END_REF][START_REF] Wang | Learning concept mappings from instance similarity[END_REF]. However, in recent years, the landscape of ontologies has changed dramatically. Today's ontologies often contain both a rich schema and, at the same time, a huge number of instances, with dozens of millions of assertions about them. To fully harvest the mine of knowledge they provide, their alignment has to be built on cross-fertilizing the alignments of both instances and schemas.

In this paper, we propose a new, holistic algorithm for aligning ontologies. Our approach links not just related entity or relationship instances, but also related classes and relations, thereby capturing the fruitful interplay between schema and instance matching. Our final aim is to discover and link identical entities automatically across ontologies on a large scale, thus allowing ontologies to truly complement each other.

Contribution. The contribution of the present paper is three-fold:

• We present paris8 , a probabilistic algorithm for aligning instances, classes, and relations simultaneously across ontologies.

• We show how this algorithm can be implemented efficiently and that it does not require any tuning

• We prove the validity of our approach through experiments on real-world ontologies.

The paper is organized as follows. Section 2 provides an overview of related work. We then introduce some preliminaries in Section 3. Section 4 describes our probabilistic algorithm and Section 5 its implementation. Section 6 discusses experiments. To ease the reading, some technical discussions are postponed to the appendix.

Related Work

Overview. The problem of ontology matching has its roots in the problem of identifying duplicate entities, which is also known as record linkage, duplicate detection, or co-reference resolution. This problem has been extensively studied in both database and natural language processing areas [START_REF] Bleiholder | Data fusion[END_REF][START_REF] Elmagarmid | Duplicate record detection: A survey[END_REF]. These approaches are less applicable in the context of ontologies for two reasons. First, they do not consider the formal semantics that ontologies have (such as the subclassOf taxonomy). Second, they focus on the alignment of instances and do not deal with the alignment of relations and classes. There are a number of surveys and analyses that shed light on the problem of record linking in ontologies. Halpin et al. [START_REF] Halpin | When owl:sameAs isn't the same: An analysis of identity in linked data[END_REF] provide a good overview of the problem in general. They also study difficulties of existing sameAs-links. These links are further analyzed by Ding et al. [START_REF] Ding | SameAs networks and beyond: Analyzing deployment status and implications of owl:sameAs in linked data[END_REF]. Glaser et al. [START_REF] Glaser | Managing co-reference on the semantic Web[END_REF] propose a framework for the management of coreference in the Semantic Web. Hu et al. [START_REF] Hu | How matchable are four thousand ontologies on the semantic Web[END_REF] provide a study on how matches look in general.

Schema Alignment. Traditional approaches to ontology matching have focused mostly either on aligning the classes (the "T-Box") or on matching instances (the "A-Box"). The approaches that align the classes are manifold, using techniques such as sense clustering [START_REF] Gracia | Large scale integration of senses for the semantic Web[END_REF], lexical and structural characteristics [START_REF] Jean-Mary | Ontology matching with semantic verification[END_REF], or composite approaches [START_REF] Aumueller | Schema and ontology matching with COMA++[END_REF]. Unlike paris, these approaches can only align classes and do not consider the alignment of relations and instances. Most similar to our approach in this field are [START_REF] Isaac | An empirical study of instance-based ontology matching[END_REF] and [START_REF] Wang | Learning concept mappings from instance similarity[END_REF], which derive class similarity from the similarities of the instances. Both approaches consider only the equivalence of classes and do not compute subclasses, as does paris. Furthermore, neither can align relations or instances.

Instance Matching. There are numerous approaches to match instances of one ontology to instances of another ontology. Ferrara, Lorusso, and Montanelli [START_REF] Ferrara | Automatic identity recognition in the semantic web[END_REF] introduce this problem from a philosophical point of view. Different techniques are being used, such as exploiting the terminological structure [START_REF] Noessner | Leveraging terminological structure for object reconciliation[END_REF], logical deduction [START_REF] Saïs | L2R: A logical method for reference reconciliation[END_REF], or a combination of logical and numerical methods [START_REF] Saïs | Combining a logical and a numerical method for data reconciliation[END_REF]. The Sig.ma engine [START_REF] Tummarello | .ma: live views on the web of data[END_REF] uses heuristics to match instances. Perhaps closest to our approach is [START_REF] Hogan | Some entities are more equal than others: statistical methods to consolidate linked data[END_REF], which introduces the concept of functionality. Different from their approach, paris does not require an additional smoothening factor. The silk framework [START_REF] Volz | Discovering and maintaining links on the Web of data[END_REF] allows specifying manual mapping rules. The Object-Coref approach by Hu, Chen, and Qu [START_REF] Hu | A self-training approach for resolving object coreference on the semantic Web[END_REF] allows learning a mapping between the instances from training data. With paris, we aim at an approach that uses neither manual input nor training data. We compare some of the results of ObjectCoref to that of paris on the datasets of the ontology alignment evaluation initiative [START_REF] Euzenat | Results of the ontology alignment evaluation initiative[END_REF] in Section 6. Hogan [START_REF] Hogan | Performing object consolidation on the semantic Web data graph[END_REF] matches instances and propose to use these instances to compute the similarity between classes, but provides no experiments. Thus, none of these approaches can align classes and relations like paris.

Holistic Approaches. Only very few approaches address the cause of aligning both schema and instances: the RiMOM [START_REF] Li | Rimom: A dynamic multistrategy ontology alignment framework[END_REF] and iliads [START_REF] Udrea | Leveraging data and structure in ontology integration[END_REF] systems. Both of these have only been tested on small ontologies. The RiMOM system can align classes, but it cannot find subclassOf relationships. Furthermore, the approach provides a bundle of heuristics and strategies to choose from, while paris is monolithic. None of the ontologies the iliads system has been tested on contained full-fledges instances with properties. In contrast, paris is shown to perform well even on large-scale real-world ontologies with millions of instances.

Preliminaries

In this section, we recall the notions of ontology and of equivalence. Finally, we introduce the notion of functionality as one of the key concepts for ontology alignment.

Ontologies. We are concerned with ontologies available in the Resource Description Framework Schema (RDFS [START_REF]Word Wide Web Consortium[END_REF]), the W3C standard for knowledge representation. An RDFS ontology builds on resources. A resource is an identifier for a real-world object, such as a city, a person, or a university, but also the concept of mathematics. For example, London is a resource that represents the city of London. A literal is a string, date or number. A property (or relation) is a binary predicate that holds between two resources or between a resource and a literal. For example, the property isLocatedIn holds between the resources London and UK. In the RDFS model, it is assumed that there exists a fixed global set R of resources, a fixed global set L of literals, and a fixed global set P of properties. Each resource is described by a URI. An RDFS ontology can be seen as a set of triples O ⊂ R × P × (R ∪ L), called statements. In the following, we assume given an ontology O. To say that x, r, y ∈ O, we will write r(x, y) and we call x and y the arguments of r. Intuitively, such a statement means that the relation r holds between the entities x and y. We say that x, y is a pair of r. A relation r -1 is called the inverse of a relation r

RT n°0408

if ∀x, y : r(x, y) ⇔ r -1 (y, x). We assume that the ontology contains all inverse relations and their corresponding statements. Note that this results in allowing the first argument of a statement to be a literal, a minor digression from the standard.

An RDFS ontology distinguishes between classes and instances. A class is a resource that represents a set of objects, such as, e.g., the class of all singers, the class of all cities or the class of all books. A resource that is a member of a class is called an instance of that class. We assume that the ontology partitions the resources into classes and instances. 9 The rdf:type relation connects an instance to a class. For example, we can say that the resource Elvis is a member of the class of singers: rdf:type(Elvis, singer). A more specific class c can be specified as a subclass of a more general class d using the statement rdfs:subclassOf (c,d). This means that, by inference, all instances of c are also instances of d. Likewise, a relation r can be made a sub-relation of a relation s by the statement rdfs:subpropertyOf(r,s). This means that, by inference again, ∀x, y : r(x, y) ⇒ s(x, y). We assume that all such inferences have been established and that the ontologies are available in their deductive closure, i.e., all statements implied by the subclass and sub-property statements have been added to the ontology.

Equivalence. In RDFS, the sets P, R, and L are global. That means that some resources, literals, and relations may be identical across different ontologies. For example, two ontologies may contain the resource London, therefore share that resource. (In practice, London is a URI, which makes it easy for two ontologies to use exactly the same identifier.) The semantics of RDFS enforces that these two occurrences of the identifier refer to the same real-world object (the city of London). The same applies to relations or literals that are shared across ontologies. Conversely, two different resources can refer to the same real-world object. For example, London and Londres can both refer to the city of London. Such resources are called equivalent. We write Londres ≡ London.

The same observation applies not just to instances, but also to classes and relations. Two ontologies can talk about an identical class or relation. They can also use different resources, but refer to the very same real-world concepts. For example, one ontology can use the relation wasBornIn whereas another ontology can use the relation birthPlace. An important goal of our approach is to find out that wasBornIn ≡ birthPlace.

In this paper, we make the following assumption: a given ontology does not contain equivalent resources. That is, if an ontology contains two instances x and x ′ , then we assume x ≡ x ′ . We assume the same for relations and classes. This is a reasonable assumption, because most ontologies are either manually designed [START_REF] Matuszek | An introduction to the syntax and content of Cyc[END_REF][START_REF] Niles | Towards a standard upper ontology[END_REF], or generated from a database (such as the datasets mentioned in the introduction), or designed with avoiding equivalent resources in mind [START_REF] Suchanek | YAGO: A core of semantic knowledge. Unifying WordNet and Wikipedia[END_REF]. If the ontology does contain equivalent resources, then our approach will still work. It will just not discover the equivalent resources within one ontology.

Functions.

A relation r is a function if, for a given first argument, there is only one second argument. For example, the relation wasBornIn is a function, because one person is born in exactly one place. A relation is an inverse function if its inverse is a function. If r is a function and if r(x, y) in one ontology and r(x, y ′ ) in another ontology, then y and y ′ must be equivalent. In the example: If a person is born in both Londres and London, then Londres ≡ London. The same observation holds for two first arguments of inverse functions. As we shall see, functions play an essential role in deriving alignments between ontologies. Nevertheless, it turns out that the precise notion of function is too strict for our setting. This is due to two reasons:

• First, a relation r ceases to be a function as soon as there is one x with y and y ′ such that r(x, y) and r(x, y ′ ). This means that just one erroneous fact can make a relation r a non-function. Since real-world ontologies usually contain erroneous facts, the strict notion of function is not wellsuited.

• Second, even if a relation is not a function, it may contribute evidence that two entities are the same. For example, the relation livesIn is not a function, because some people may live in several places. However, a wide majority of people live in one place, or in very few places. So, if most people who live in London also live in Londres, this provides a strong evidence for the unification of London and Londres.

Thus, to derive alignments, we want to deal with "quasi-functions". This motivates introducing the concept of functionality, as in [START_REF] Hogan | Some entities are more equal than others: statistical methods to consolidate linked data[END_REF]. The local functionality of a relation r for a first argument x is defined as

f un(r, x) = 1 #y : r(x, y)
where we write "#y : ϕ(y)" to mean "|{y | ϕ(y)}|". Consider for example the relationship isCitizenOf . For most first arguments, the functionality will be 1, because most people are citizens of exactly one country. However, for people who have multiple nationalities, the functionality may be 1 2 or even smaller. The local inverse functionality is defined analogously as

f un -1 (r, x) = f un(r -1 , x)
Deviating from [START_REF] Hogan | Some entities are more equal than others: statistical methods to consolidate linked data[END_REF], we define the global functionality of a relation r as the harmonic mean of the local functionalities, which boils down to

f un(r) = #x : ∃y : r(x, y) #x, y : r(x, y) (1)
We discuss design alternatives and the rationale of our choice in Appendix A.

The global inverse functionality is defined analogously as f un -1 (r) = f un(r -1 ).

Probabilistic Model

Equivalence of Instances

We want to model the probability P (x ≡ x ′ ) that one instance x in one ontology is equivalent to another instance x ′ in another ontology. Let us assume that both ontologies share a relation r. Following our argument in Section 3, we want the RT n°0408

probability P (x ≡ x ′ ) to be large if r is highly inverse functional, and if there are y ≡ y ′ with r(x, y), r(x ′ , y ′ ) (if, say, x and x ′ share an e-mail address). This can be written pseudo-formally as:

∃r, y, y ′ : r(x, y) ∧ r(x ′ , y ′ ) ∧ y ≡ y ′ ∧ f un -1 (r) is high =⇒ x ≡ x ′
We transform this logical rule into a probability assignment for x ≡ x ′ , assuming independence and using the formalization described in Appendix B, obtaining thus:

P 1 (x ≡ x ′ ) := 1 - r(x,y),r(x ′ ,y ′ ) (1 -f un -1 (r) × P (y ≡ y ′ )) (2)
In other words, as soon as there is one relation r with f un -1 (r) = 1 and with r(x, y), r(x ′ , y ′ ), and P (y ≡ y ′ ) = 1, it follows that P 1 (x ≡ x ′ ) = 1. We discuss a design alternative in Appendix C. Note that the probability of x ≡ x ′ depends recursively on the probabilities of other equivalences. These other equivalences may hold either between instances or between literals. We discuss the probability of equivalence between two literals in Section 5. Obviously, we set P (x ≡ x) := 1 for all literals and instances x.

Equation ( 2) considers only positive evidence for an equality. To consider also evidence against an equality, we can use the following modification. We want the probability P (x ≡ x ′ ) to be small, if there is a highly functional relation r with r(x, y) and if y ≡ y ′ for all y ′ with r(x ′ , y ′ ). Pseudo-formally, this can be written as ∃r, y : r(x, y) ∧ (∀y

′ : r(x ′ , y ′ ) ⇒ y ≡ y ′ ) ∧ f un(r) is high =⇒ x ≡ x.
(

) 3
This can be modeled as

P 2 (x ≡ x ′ ) := r(x,y) (1 -f un(r) r(x ′ ,y ′ ) (1 -P (y ≡ y ′ ))) (4)
As soon as there is one relation r with f un(r) = 1 and with r(x, y), r(x ′ , y ′ ), and P (y ≡ y ′ ) = 0, it follows that P 2 (x ≡ x ′ ) = 0. We combine these two desiderata by multiplying the two probability estimates:

P 3 (x ≡ x ′ ) := P 1 (x ≡ x ′ ) × P 2 (x ≡ x ′ ) (5)
In the experiments, we found that Equation (2) suffices in practice. However, we discuss scenarios where Equation ( 5) can be useful in Section 6.

Subrelations

The formulas we have just established estimate the equivalence between two entities that reside in two different ontologies, if there is a relation r that is common to the ontologies. It is also a goal to discover whether a relation r of one ontology is equivalent to a relation r ′ of another ontology. More generally, we would like to find out whether r is a sub-relation of r ′ , written r ⊆ r ′ . Intuitively, the probability P (r ⊆ r ′ ) is proportional to the number of pairs in r that are also pairs in r ′ :

P (r ⊆ r ′ ) := #x, y : r(x, y) ∧ r ′ (x, y) #x, y : r(x, y) (6)

RT n°0408

The numerator should take into account the resources that have already been matched across the ontologies. Therefore, the numerator is more appropriately phrased as:

#x, y : r(x, y) ∧ (∃x ′ , y ′ : x ≡ x ′ ∧ y ≡ y ′ ∧ r ′ (x ′ , y ′ ))
Using again our formalization from Appendix B, this can be modeled as:

r(x,y) (1 - r ′ (x ′ ,y ′ ) (1 -(P (x ≡ x ′ ) × P (y ≡ y ′ )))) (7)
In the denominator, we want to normalize by the number of pairs in r that have a counterpart in the other ontology. This is

r(x,y) (1 - x ′ ,y ′ (1 -(P (x ≡ x ′ ) × P (y ≡ y ′ )))) (8)
Thus, we estimate the final probability P (r ⊆ r ′ ) as:

r(x,y) (1 -r ′ (x ′ ,y ′ ) (1 -(P (x ≡ x ′ ) × P (y ≡ y ′ )))) r(x,y) (1 -x ′ ,y ′ (1 -P (x ≡ x ′ ) × P (y ≡ y ′ ))) (9)
This probability depends on the probability that two instances (or literals) are equivalent.

One might be tempted to set P (r ⊆ r) := 1 for all relations r. However, in practice, we observe cases where the first ontology uses r where the second ontology omits it. Therefore, we compute P (r ⊆ r) as a contingent quantity.

We are now in a position to generalize Equation (2) to the case where the two ontologies do not share a common relation. For this, we need to replace every occurrence of r(x ′ , y ′ ) by r ′ (x ′ , y ′ ) and factor in the probabilities that r ′ ⊆ r or r ⊆ r ′ . This gives the following value to be assigned to P r(x ≡ x ′ ):

1 - r(x,y),r ′ (x ′ ,y ′ ) (1 -P (r ′ ⊆ r) × f un -1 (r) × P (y ≡ y ′ )) × (1 -P (r ⊆ r ′ ) × f un -1 (r ′ ) × P (y ≡ y ′ )) (10)
If we want to consider also negative evidence as in Equation ( 5), we get for

P (x ≡ x ′ ): 1 - r(x,y),r ′ (x ′ ,y ′ ) (1 -P (r ′ ⊆ r) × f un -1 (r) × P (y ≡ y ′ )) × (1 -P (r ⊆ r ′ ) × f un -1 (r ′ ) × P (y ≡ y ′ )) × r(x,y),r ′ 1 -f un(r) × P (r ′ ⊆ r) × r ′ (x ′ ,y ′ ) (1 -P (x ≡ x ′ )) × 1 -f un(r ′ ) × P (r ⊆ r ′ ) × r ′ (x ′ ,y ′ ) (1 -P (x ≡ x ′ )) (11)
This formula looks asymmetric, because it considers only P (r ′ ⊆ r) and f un(r) one one hand, and P (r ⊆ r ′ ) and f un(r ′ ) on the other hand (and not, for instance, P (r ′ ⊆ r) together with f un(r ′ )). Yet, it is not asymmetric,

RT n°0408

because each instantiation of r ′ will at some time also appear as an instantiation of r. It is justified to consider P (r ′ ⊆ r), because a large P (r ′ ⊆ r) implies that r ′ (x, y) ⇒ r(x, y). This means that a large P (r ′ ⊆ r) implies that f un(r) < f un(r ′ ) and f un -1 (r) < f un -1 (r ′ ).

If there is no x ′ , y ′ with r ′ (x ′ , y ′ ), we set as usual the last factor of the formula to one, r ′ (x ′ ,y ′ ) (1 -P (x ≡ x ′ ))) := 1. This decreases P (x ≡ x ′ ) in case one instance has relations that the other one does not have.

To each instance from the first ontology, our algorithm assigns multiple equivalent instances from the second ontology, each with a probability score. For each instance from the first ontology, we call the instance from the second ontology with the maximum score the maximal assignment. If there are multiple instances with the maximum score, we break ties arbitrarily, so that every instance has at most one maximal assignment.

Subclasses

A class corresponds to a set of entities. One could be tempted to treat classes just like instances and compute their equivalence. However, the class structure of one ontology may be more fine-grained than the class structure of the other ontology. Therefore, we aim to find out not whether one class c of one ontology is equivalent to another class c ′ of another ontology, but whether c is a subclass of c ′ , c ⊆ c ′ . Intuitively, the probability P (c ⊆ c ′ ) shall be proportional to the number of instances of c that are also instances of c ′ :

P (c ⊆ c ′ ) = # c ∩ c ′ #c
. Again, we estimate the expected number of instances that are in both classes as

E(# c ∩ c ′ ) = x:type(x,c) (1 - y:type(y,d) (1 -P (x ≡ y)))
We divide this expected number by the total number of instances of c:

P (c ⊆ c ′ ) = x:type(x,c) (1 -y:type(y,d) (1 -P (x ≡ y))) #x : type(x, c) (12)
The fact that two resources are instances of the same class can reinforce our belief that the two resources are equivalent. Hence, it seems tempting to feed the subclass-relationship back into Equation [START_REF] Ferrara | Automatic identity recognition in the semantic web[END_REF]. However, in practice, we found that the class information is of less use for the equivalence of instances. This may be because of different granularities in the class hierarchies. It might also be because some ontologies use classes to express certain properties (MaleSingers), whereas others use relations for the same purpose (gender = male). Therefore, we compute the class equivalences only after the instance equivalences have been computed.

Implementation

Iteration

Our algorithm takes as input two ontologies. As already mentioned, we assume that a single ontology does not contain duplicate (equivalent) entities.

RT n°0408

This corresponds to some form of a domain-restricted unique name assumption. Therefore, our algorithm considers only equivalence between entities from different ontologies. Strictly speaking, the functionality of a relation (Equation ( 1)) depends recursively on the equivalence of instances. If, e.g., every citizen lives in two countries, then the functionality of livesIn is 1 2 . If our algorithm unifies the two countries, then the functionality of livesIn jumps to 1. However, since we assume that there are no equivalent entities within one ontology, we compute the functionalities of the relations within each ontology upfront.

We implemented a fixpoint computation for Equations ( 9) and [START_REF] Ferrara | Automatic identity recognition in the semantic web[END_REF]. First, we compute the probabilities of equivalences of instances. Then, we compute the probabilities for sub-relationships. These two steps are iterated until convergence. In a last step, the equivalences between classes are computed by Equation ( 12) from the final assignment. To bootstrap the algorithm in the very first step, we set P (r ⊆ r ′ ) = θ for all pairs of relations r, r ′ of different ontologies. We chose θ = 0.10. The second round uses the computed values for P (r ⊆ r ′ ) and no longer θ. We have not yet succeeded in proving a theoretical condition under which the iteration of Equations ( 9) and ( 10) reaches a fixpoint. In practice, we iterate until the entity pairs under the maximal assignments change no more (which is what we call convergence). In our experiments, this state was always reached after a few iterations. We note that one could always enforce convergence of such iterations by introducing a progressively increasing dampening factor. Our model changes the probabilities of two resources being equal -but never the probability that a certain statement holds. All statements in both ontologies remain valid. This is possible because an RDFS ontology cannot be made inconsistent by equating resources, but this would not be the case any more for richer ontology languages.

Optimization

The equivalence of instances (Equation ( 10)) can be computed in different ways. In the most naive setting, the equivalence is computed for each pair of instances. This would result in a runtime of O(n 2 m), where n is the number of instances and m is the average number of statements in which an instance occurs (a typical value for m is 20). This implementation took weeks to run one iteration. We overcame this difficulty as follows.

First, we optimize the computation of Equation [START_REF] Ferrara | Automatic identity recognition in the semantic web[END_REF]. For each instance x in the first ontology, we traverse all statements r(x, y) in which this instance appears as first argument. (Remember that we assume that the ontology contains all inverse statements as well.) For each statement r(x, y), we consider the second argument y, and all instances y ′ that the second argument is known to be equal to ({y ′ : P (y ≡ y ′ ) > 0}). For each of these equivalent instances y ′ , we consider again all statements r(x ′ , y ′ ) and update the equality of x and x ′ . This results in a runtime of O(nm 2 e), where e is the average number of equivalent instances per instance (typically around 10). Equations ( 9) and ( 12) are optimized in a similar fashion.

Generally speaking, our model distinguishes true equivalences (P (x ≡ x ′ ) > 0) from false equivalences (P (x ≡ x ′ ) = 0) and unknown equivalences (P (x ≡ x ′ ) not yet computed). Unknown quantities are simply omitted in the sums and products of the equations. Interestingly, most equations contain a probability P (x ≡ x ′ ) only in the form (1 -P (x ≡ x ′ )). This means that the formula RT n°0408 will evaluate to the same value if P (x ≡ x ′ ) is unknown or if P (x ≡ x ′ ) = 0. Therefore, our algorithm does not need to store equivalences of value 0 at all.

Our implementation thresholds the probabilities and assumes every value below θ to be zero. This greatly reduces the number of equivalences that the algorithm needs to store. Furthermore, we limit the number of pairs that are evaluated in Equations ( 9) and ( 12) to 10, 000. For each computation, our algorithm considers only the equalities of the previous maximal assignment and ignores all other equalities. This reduces the runtime by an order of magnitude without affecting much the relation inclusion assessment. We stress that all these optimizations have for purpose to decrease the running time of the algorithm without significantly affecting the outcome of the computation. We have validated in our experiments that it is indeed the case.

Our implementation is in Java, using the Java Tools developed for [START_REF] Suchanek | Combining linguistic and statistical analysis to extract relations from Web documents[END_REF] and Berkeley DB. We used the Jena framework to load and convert the ontologies. The algorithm turns out to be heavily IO-bound. Therefore, we used a solid-state drive (SSD) with high read bandwidth to store the ontologies. This brought the computation time down from the order of days to the order of hours on very large ontologies. We considered parallelizing the algorithm and running it on a cluster, but it turned out to be unnecessary.

Literal Equivalence

The probability that two literals are equal is known a priori and will not change. Therefore, such probabilities can be set upfront (clamped), for example as follows:

• The probability that two numeric values of the same dimension are equal can be a function of their proportional difference.

• The probability that two strings are equal can be inverse proportional to their edit distance.

• For other identifiers (social security numbers, etc.), the probability of equivalence can be a function that is robust to common misspellings. The checksum computations that are often defined for such identifiers can give a hint as to which misspellings are common.

• By default, the probability of two literals being equal should be 0.

These functions can be designed depending on the application or on the specific ontologies. They can, e.g., take into account unit conversions (e.g., between Kelvin and Celcius). They could also perform datatype conversions (e.g., between xsd:string and xsd:anyURI ) if necessary. The probabilities can then be plugged into Equation [START_REF] Ferrara | Automatic identity recognition in the semantic web[END_REF].

For our implementation, we chose a particularly simple equality function. We normalize numeric values by removing all data type or dimension information. Then we set the probability P (x ≡ y) to 1 if x and y are identical literals, to 0 otherwise. The goal of this work is to show that even with such a simple, domainagnostic, similarity comparison between literals, our probabilistic model is able to align ontologies with high precision; obviously, precision could be raised even higher by implementing more elaborate literal similarity functions.

RT n°0408

Parameters

Our implementation uses the following parameters:

• The initial value θ for the equivalence of relations in the very first step of the algorithm. We show in the experiments that the choice of θ does not affect the results.

• Similarity functions for literals. These are application-dependent. However, we show that even with the simple identity function, the algorithm performs well.

Therefore, we believe we can claim that our model has no dataset-dependent tuning parameters. Our algorithm can be (and in fact, was) run on all datasets without any dataset specific settings. This contrasts paris with other algorithms, which are often heavily dependent on parameters that have to be tuned for each particular application or dataset. Traditional schema alignment algorithms, for example, usually use heuristics on the names of classes and relations, whose tuning requires expertise (e.g., [START_REF] Li | Rimom: A dynamic multistrategy ontology alignment framework[END_REF]). A major goal of the present work was to base the algorithm on probabilities and make it as independent as possible from the tuning of parameters. We are happy to report that this works beautifully. In order to improve results further, one can use smarter similarity functions, as discussed in Section 5.3.

Experiments

Setup

All experiments were run on a quad-core PC with 12 GB of RAM, running a 64bit version of Linux; all data was stored on a fast solid-state drive (SSD), with a peak random access bandwidth of approximately 50 MB/s (to be compared with a typical random access bandwidth of 1 MB/s for a magnetic hard drive).

Our experiments always compute relation, class, and instance equivalences between two given ontologies. Our algorithm was run until convergence (i.e., until less than 1 % of the entities changed their maximal assignment). We evaluate the instance equalities by comparing the computed final maximal assignment to a gold standard, using the standard metrics of precision, recall, and F-measure. For instances, we considered only the assignment with the maximal score. For relation assignments, we performed a manual evaluation. Since paris computes sub-relations, we evaluated the assignments in each direction. Class alignments were also evaluated manually. For all evaluations, we ignored the probability score that paris assigned, except when noted.

Benchmark Test

To be comparable to [START_REF] Hu | A self-training approach for resolving object coreference on the semantic Web[END_REF][START_REF] Li | Rimom: A dynamic multistrategy ontology alignment framework[END_REF][START_REF] Noessner | Leveraging terminological structure for object reconciliation[END_REF][START_REF] Saïs | L2R: A logical method for reference reconciliation[END_REF], we report results on the benchmark provided by the 2010 edition of the ontology alignment evaluation initiative (OAEI) [START_REF] Euzenat | Results of the ontology alignment evaluation initiative[END_REF]. We ran experiments on two datasets, each of which consists of two ontologies. 10 For each dataset, the OAEI provides a gold standard list of instances of the first ontology that are equivalent to instances of the second ontology. The relations and classes are identical in the first and second ontology. To make the task more challenging for paris, we artificially renamed the relations and classes in the first ontology, so that the sets of instances, classes, and relations used in the first ontology are disjoint from the ones used in the second ontology.

For the person dataset, paris converged after just 2 iterations and 2 minutes. For the restaurants, paris took 3 iterations and 6 seconds. Table 1 shows our results. 11 We achieve near-perfect precision and recall, with the exception of recall in the second dataset. As reported in [START_REF] Hu | A self-training approach for resolving object coreference on the semantic Web[END_REF], all other approaches [START_REF] Li | Rimom: A dynamic multistrategy ontology alignment framework[END_REF][START_REF] Noessner | Leveraging terminological structure for object reconciliation[END_REF][START_REF] Saïs | L2R: A logical method for reference reconciliation[END_REF] remain below 80 % of F-measure for the second dataset, while only Object-Coref [START_REF] Hu | A self-training approach for resolving object coreference on the semantic Web[END_REF] achieves an F-measure of 90 %. We achieve an F-measure of 91 %. We are very satisfied with this result, because unlike ObjectCoref, paris does not require any training data. It should be further noted that, unlike all other approaches, paris did not even know that the relations and classes were identical, but discovered the class and relation equivalences by herself in addition to the instance equivalences.

Design Alternatives

To measure the influence of θ on our algorithm, we ran paris with θ = 0.001, 0.01, 0.05, 0.1, 0.2 on the restaurant dataset. A larger θ causes larger probability scores in the first iteration. However, the sub-relationship scores turn out to be the same, no matter what value θ had. Therefore, the final probability scores are the same, independently of θ. In a second experiment, we allowed the algorithm to take into account all probabilities from the previous iteration (and not just those of the maximal assignment). This changed the results only marginally (by one correctly matched entity), because the first iteration already has a very good precision. In a third experiment, we allowed the algorithm to take into account negative evidence (i.e., we used Equation ( 11) instead of Equation ( 10)). This made paris give up all matches between restaurants. The reason for this behavior turned out to be that most entities have slightly different attribute values (e.g., a phone number "213/467-1108" instead of "213-467-1108"). Therefore, we plugged in a different string equality measure. Our new measure normalizes two strings by removing all non-alphanumeric characters and lowercasing them. Then, the measure returns 1 if the strings are equal and 0 otherwise. This increased precision to 100 %, but decreased recall to 70 %. Our experience with 11 Classes and relations accumulated for both directions. Values for ObjCoref as reported in [START_REF] Hu | A self-training approach for resolving object coreference on the semantic Web[END_REF]. Precision and recall are not reported in [START_REF] Hu | A self-training approach for resolving object coreference on the semantic Web[END_REF]. ObjCoref cannot match classes or relations.

RT n°0408

YAGO and DBpedia (see next experiment) indicates that negative evidence can be helpful to distinguish entities of different types (movies and songs) that share one value (the title). However, in our settings, positive evidence proved sufficient.

Real-world Ontologies

We wanted to test paris on real-world ontologies of a large scale, with a rich class and relation structure. At the same time, we wanted to restrict ourselves to cases where an error-free ground truth is available. Therefore, we first chose to align the YAGO [START_REF] Suchanek | YAGO: A core of semantic knowledge. Unifying WordNet and Wikipedia[END_REF] and DBpedia [START_REF] Auer | DBpedia: A Nucleus for a Web of Open Data[END_REF] Table 2: YAGO [START_REF] Suchanek | YAGO: A core of semantic knowledge. Unifying WordNet and Wikipedia[END_REF], DBpedia [START_REF] Auer | DBpedia: A Nucleus for a Web of Open Data[END_REF] and IMDb.

YAGO vs. DBpedia. With several million instances, these are some of the largest ontologies available. Each of them has thousands of classes and at least dozens of relations. We took only the non-meta facts from YAGO, and only the manually established ontology from DBpedia, which yields the datasets described in Table 2. Both ontologies use Wikipedia identifiers for their instances, so that the ground truth for the instance matching can be computed trivially. 13 However, the statements about the instances differ in both ontologies, so that the matching is not trivial. The class structure and the relationships of YAGO and DBpedia were designed completely independently, making their alignment a challenging endeavor. We ran paris for 4 iterations, until convergence. Table 3 shows the results per iteration. To compute recall, we counted the number of shared instances in DBpedia and YAGO. Since YAGO selects Wikipedia pages with many categories, and DBpedia selects pages with frequent infoboxes, the two resources share only 1.4 million entities. paris can map them with a precision of 90 % and a recall of 73 %. If only entities with more than 10 facts in DBpedia are considered, precision and recall jump to 97 % and 85 %, respectively. paris assigns one class of one ontology to multiple classes in the taxonomy of the other ontology, taking into account the class inclusions. Some classes are assigned to multiple leaf-classes as well. For our evaluation, we excluded 19 highlevel classes (such as yagoGeoEntity, physicalThing, etc.). Then, we randomly sampled from the remaining assignments and evaluated the precision manually. It turns out that the precision increases substantially with the probability score (see Figure 1). We report the numbers for a threshold of 0.4 in Table 3 (the number of evaluated sample assignments is 200 in both cases). The errors come from 3 sources: First, paris misclassifies a number of the instances, which worsens the precision of the class assignment. Second, there are small inconsistencies in the ontologies themselves (YAGO, e.g., has several people classified as lumber, because they work in the wood industry). Last, there may be biases in the instances that the ontologies talk about. For example, paris estimates that 12 % of the people convicted of murder in Utah were soccer players. As the score increases, these assignments get sorted out. Evaluating whether a class is always assigned to its most specific counterpart would require exhaustive annotation of candidate inclusions. Therefore we only report the number of aligned classes and observe that even with high probability scores (see Figure 2 and Table 3) we find matches for a significant proportion of the classes of each ontology into the other. The relations are also evaluated manually in both directions. We 4 shows some of the alignments. paris finds non-trivial alignments of more fine-grained relations to more coarse-grained ones, of inverses, of symmetric relations, and of relations with completely different names. There are a few plainly wrong alignments, but most errors come from semantic differences that do not show in practice (e.g., burialPlace is semantically different from deathPlace, so we count it as an error, even though in most cases the two will coincide). Recall is hard to estimate, because not all relations have a counterpart in the other ontology and some relations are poorly populated. We only note that we find alignments for half of YAGO's relations in DBpedia.

YAGO vs. IMDb. Next, we were interested in the performance of paris on ontologies that do not derive from from the same source. For this purpose, we constructed an RDF ontology from the IMDb. IMDb is predestined for the matching, because it is huge and there is an existing gold standard: YAGO contains some mappings to IMDb movie identifiers, and we could construct such a mapping for many persons from Wikipedia infoboxes. The content of the IMDb database is available for download as plain-text files. 14 The format of each file is ad hoc but we transformed the content of the database in a fairly straightforward manner into a collection of triples. For instance, the file actors.list lists for each actor x the list of all movies y that x was cast in, which we transformed into facts actedIn(x, y). Unfortunately, the plain-text database does not contain IMDb movie and person identifiers (those that we use for comparing to the gold standard). Consequently, we had to obtain these identifiers separately. For this purpose, and to avoid having to access each Web page of the IMDb Web site, which would require much too many Web server requests, we used the advanced search feature of IMDb 15 to obtain the list of all movies from a given year, or of all persons born in a certain year, together with their identifiers and everything needed to connect to the plain-text databases. Since our IMDb ontology has only 24 relations, we manually created a gold standard for relations, aligning 15 of them to YAGO relations. As Table 5 shows, paris took much longer for each iteration than in the previous experiment. The results are convincing, with an F-score of 92 % for the instances. This is a considerable improvement over a baseline approach that aligns entities by matching their rdfs:label properties (achieving 97 % precision and only 70 % recall, with an F-score of 82 %).

Examining by hand the few remaining alignment errors revealed the following patterns: As illustrated here, alignment of instances and relations work very well in paris, whereas class alignment leaves still some room for improvement. Overall, the results are very satisfactory, as this constitutes, to the best of our knowledge, the first holistic alignment of instances, relations, and classes on some of the world's largest ontologies, without any prior knowledge, tuning, or training.

Conclusion

We have presented paris, an algorithm for the automated alignment of RDFS ontologies. Unlike most other approaches, paris computes alignments not only for instances, but also for classes and relations. It does not need training data and it does not require any parameter tuning. paris is based on a probabilistic framework that captures the interplay between schema alignment and instance matching in a natural way, thus providing a holistic solution to the ontology alignment problem. Experiments show that our approach works extremely well in practice.

paris does not use any kind of heuristics on relation names, which allows aligning relations with completely different names. We conjecture that the name heuristics of more traditional schema-alignment techniques could be factored into the model.

Currently, paris cannot deal with structural heterogeneity. If one ontology models an event by a relation (such as wonAward), while the other one models it by an event entity (such as winningEvent, with relations winner, award, year), then paris will not be able to find matches. The same applies if one ontology is more fine-grained than the other one (specifying, e.g., cities as birth places instead of countries), or if one ontology treats cities as entities, while the other one refers to them by strings. For future work, we plan to address these types of challenges. We also plan to analyze under which conditions our equations are guaranteed to converge. It would also be interesting to apply paris to more than two ontologies. This would further increase the usefulness of paris for the dream of the Semantic Web.

RT n°0408

A Global Functionality

There are several design alternatives to define the global functionality:

1. We can count the number of statements and divide it by the number of pairs of statements with the same source:

f un(r) = #x, y : r(x, y) #x, y, y ′ : r(x, y) ∧ r(x, y ′ ) This measure is very volatile to single sources that have a large number of targets. This definition is treacherous: Assume that we have n people and n dishes, and the relationship likesDish(x, y). Now, assume that all people like all dishes. Then likesDish should have a low functionality, because everybody likes n dishes. But the above definition assigns a functionality of f un(likesDish) = n n = 1.

RT n°0408

3. We can average the local functionalities, as proposed in [START_REF] Hogan | Some entities are more equal than others: statistical methods to consolidate linked data[END_REF]:

f un(r) = avg x f un(r, x) = avg x 1 #y : r(x, y) = 1 #x∃y : r(x, y) x 1 #y : r(x, y) However, the local functionalities are ratios, so that the arithmetic mean is less appropriate. This notion is equivalent to the harmonic mean.

With these considerations in mind, we chose the harmonic mean for the definition of the global functionality.

B Probabilistic Modeling of First-Order Formulas

In Section 4, we presented our probabilistic model of ontology alignment based on descriptions as first-order sentences of our rules, such as Equation (3), reproduced here:

∃r, y : r(x, y) ∧ (∀y ′ : r(x ′ , y ′ ) ⇒ y ≡y ′ ) ∧ f un(r) is high =⇒ x ≡x

We derive from these equations probability assessments, such as Equation (4), by assuming mutual independence of all distinct elements of our models (instance equivalence, functionality, relationship inclusion, etc.). This assumption is of course not true in practice but it allows us to approximate efficiently the probability of the consequence of our alignment rules in a canonical manner.

RT n°0408

Figure 1 :Figure 2 :

 12 Figure 1: Precision of class alignment yago ⊆ DBpedia as a function of the probability threshold.

2 .

 2 We can define functionality as the ratio of the number of first arguments to the number of second arguments:f un(r) =#x∃y : r(x, y) #y∃x : r(x, y)

4 . 5 .

 45 We can average the local functionalities not by the arithmetic mean, but by the harmonic mean insteadf un(r) = HM x f un(r, x) = HM x 1 #y : r(x, y) = #x∃y : r(x, y)x #y : r(x, y) = #x∃y : r(x, y) #x, y : r(x, y) . We may say that the global functionality is the number of first arguments per relationship instance: f un(r) = #x∃y : r(x, y) #x, y : r(x, y)

Table 1 :

 1 Results (precision, recall, F-measure) of instance, class, and relation alignment on OAEI datasets, compared with ObjectCoref[START_REF] Hu | A self-training approach for resolving object coreference on the semantic Web[END_REF]. The "Gold" columns indicate the number of equivalences in the gold standard.

				Instances			Classes			Relations
	Dataset	System	Gold	Prec	Rec	F	Gold	Prec	Rec	F	Gold	Prec	Rec	F
	Person	paris ObjCoref	500	100 % 100 %	100 % 100 %	100 % 100 %	4	100 % -	100 % -	100 % -	20	100 % -	100 % -	100 % -
	Rest.	paris ObjCoref	112	95 % N/A	88 % N/A	91 % 90 %	4	100 % -	100 % -	100 % -	12	100 % -	66 % -	88 % -

  ontologies, and then to align YAGO with an ontology built out of the IMDb 12 .

	Ontology #Instances #Classes #Relations
	YAGO	2,795,289	292,206	67
	DBpedia	2,365,777	318	1,109
	IMDb	4,842,323	15	24

Table 4 :

 4 Some relation alignments between YAGO and DBpedia with their scores

		YAGO ⊆ DBpedia		DBpedia ⊆ YAGO
	y:actedIn	⊆ dbp:starring -1	0.95	dbp:birthName	⊆ rdfs:label	0.96
	y:graduatedFrom ⊆ dbp:almaMater	0.93	dbp:placeOfBurial	⊆ y:diedIn	0.18
	y:hasChild y:hasChild	⊆ dbp:parent -1 ⊆ dbp:child	0.53 0.30	dbp:headquarter dbp:largestSettlement ⊆ y:isLocatedIn -1 ⊆ y:isLocatedIn	0.34 0.52
	y:isMarriedTo	⊆ dbp:spouse -1	0.56	dbp:notableStudent	⊆ y:hasAdvisor -1	0.10
	y:isMarriedTo	⊆ dbp:spouse	0.89	dbp:formerName	⊆ rdfs:label	0.73
	y:isCitizenOf	⊆ dbp:birthPlace	0.25	dbp:award	⊆ y:hasWonPrize	0.14
	y:isCitizenOf	⊆ dbp:nationality	0.88	dbp:majorShrine	⊆ y:diedIn	0.11
	y:created y:created y:created	⊆ dbp:artist -1 ⊆ dbp:author -1 ⊆ dbp:writer -1	0.13 0.17 0.30	dbp:slogan dbp:author dbp:composer	⊆ y:hasMotto ⊆ y:created -1 ⊆ y:created -1	0.49 0.70 0.61
	RT n°0408

Table 5 :

 5 Results on matching YAGO and IMDb over iterations 1-4 consider only the maximally assigned relation, because the relations do not form a hierarchy in YAGO and DBpedia. In most cases one assignment dominates clearly. Table

  • Some errors were caused by errors in YAGO, usually caused by incorrect references from Wikipedia pages to IMDb movies.• paris sometimes aligned instances in YAGO with instances in IMDb that were not equivalent, but very closely related: for example, King of the Royal Mounted was aligned with The Yukon Patrol, a feature version of this TV series with the same cast and crew; Out 1, a 13-hour movie, was aligned with Out 1: Spectre, its shortened 4-hour variation.• Some errors were caused by the very naive string comparison approach, that fails to discover, e.g., that Sugata Sanshirô and Sanshiro Sugata refer to the same movie. It is very likely that using an improved string comparison technique would further increase precision and recall of paris.paris could align 80 % of the relations of IMDb and YAGO, with a precision of 100 %. paris mapped half of the IMDb classes correctly to more general or equal YAGO classes (at threshold 0). It performs less well in the other direction. This is because YAGO contains mostly famous people, many of whom appeared in some movie or documentary on IMDb. Thus, paris believes that a class such as People from Central Java is a subclass of actor.

http://www.w3.org/wiki/DataSetRDFDumps

http://musicbrainz.org/

http://www.imdb.com/

http://www.geonames.org/

http://www.informatik.uni-trier.de/~ley/db

http://www.uniprot.org/

http://www.govtrack.us/ , http://source.data.gov.uk/data/ RT n°0408

Probabilistic Alignment of Relations, Instances, and Schema RT n°0408

RDFS allows classes to be instances of other classes, but in practice, this case is rare.RT n°0408

We could not run on the third dataset, because it violates our assumption of nonequivalence within one ontology.RT n°0408

This work has been partially funded by the ERC grant Webdam.

Instances Classes Relations

The Internet Movie Database, http://www.imdb.com 13 We hid this knowledge from paris. Independence allows us to use the following standard identities:

RT n°0408

Then, a rule ϕ =⇒ ψ is translated as a probability assignment P (ψ) := P (ϕ) and ϕ is recursively decomposed using these identities. Following the example of Equation ( 3), we derive the value of Pr 2 (x ≡ x ′ ) in Equation ( 4) as follows:

since r(x, y) and r(x ′ , y ′ ) are crisp, non-probabilistic facts.

Similarly, when we need to estimate a number such as "#x : ϕ(x)", we compute E(#x : ϕ(x)) using the aforementioned identities.

C Equivalence of Sets

We compare two instances for equivalence by comparing every statement about the first instance with every statement about the second instance (if they have the same relation). This entails a quadratic number of comparisons. For example, if an actor x acted in the movies y 1 , y 2 , y 3 , and an actor x ′ acted in the movies y ′ 1 , y ′ 2 , y ′ 3 , then we will compare every statement actedIn(x, y i ) with every statement actedIn(x ′ , y ′ j ). Alternatively, one could think of the target values as a set and of the relation as a function, as in actedIn(x, {y 1 , y 2 , y 3 }) and actedIn(x ′ , {y ′ 1 , y ′ 2 , y ′ 3 }). Then, one would have to compare only two sets instead of a quadratic number of statements. However, all elements of one set are potentially equivalent to all elements of the other set. Thus, one would still need a quadratic number of comparisons.

One could generalize a set equivalence measure (such as the Jaccard index) to sets with probabilistic equivalences. However, one would still need to take into account the functionality of the relations: If two people share an e-mail address (high inverse functionality), they are almost certainly equivalent. By contrast, if two people share the city they live in, they are not necessarily equivalent. To unify two instances, it is sufficient that they share the value of one highly inverse functional relation. Conversely, if two people have a different birth date, they are certainly different. By contrast, if they like two different books, they could still be equivalent (and like both books). Our model takes this into account. Thus, our formulas can be seen as a comparison measure for sets with probabilistic equivalences, which takes into account the functionalities.


Ilhem Fajjari
email: ilhem.fejjari@ginkgo-networks.com

Nadjib Aitsaadi
email: nadjib.aitsaadi@inria.fr

Guy Pujolle
email: guy.pujolle@lip6.fr

Hubert Zimmermann
email: hubert.zimmermann@ginkgo-networks.com

VNR Algorithm: A Greedy Approach For Virtual Networks Reconfigurations

Keywords: Network virtualization, Embedding problem, Reconfiguration

In this paper we address the problem of virtual network reconfiguration. In our previous work on virtual network embedding strategies, we found that most virtual network rejections were caused by bottlenecked substrate links while peak resource use is equal to 18%. These observations lead us to propose a new greedy Virtual Network Reconfiguration algorithm, VNR. The main aim of our proposal is to 'tidy up' substrate network in order to minimise the number of overloaded substrate links, while also reducing the cost of reconfiguration. We compare our proposal with the related reconfiguration strategy VNA-Periodic, both of them are incorporated in the best existing embedding strategies VNE-AC and VNE-Greedy in terms of rejection rate. The results obtained show that VNR outperforms VNA-Periodic. Indeed, our research shows that the performances of VNR do not depend on the virtual network embedding strategy. Moreover, VNR minimises the rejection rate of virtual network requests by at least ≃ 83% while the cost of reconfiguration is lower than with VNA-Periodic.

I. INTRODUCTION

In the last few years, network virtualization has attracted a great deal of interest from industry and research communities as a means for designing the future Internet architecture. In fact, Network virtualization offers a promising way to share a physical network among many simultaneous, independent and isolated virtual networks [START_REF] Chowdhury | Network virtualization: State of the art and research challenges[END_REF], [START_REF] Carapinha | Network virtualization: a view from the bottom[END_REF]. Each Virtual Network (VN ) allocates resources in the Substrate Network (SN ) such as processing power, memory and bandwidth. The network virtualization paradigm is confronted with many challenges [START_REF] Chowdhury | A survey of network virtualization[END_REF], such as security, interoperability, resource scheduling, etc.

In this research paper, we will examine the problem of resource allocation in SN s. The main objective is to maximise the VN provider's revenue by finding a judicious assignment of a VN request in the SN . It is worth noting that each virtual node is hosted in only one substrate node. Furthermore, each virtual link is embedded into one substrate path. Indeed, in our previous work [START_REF] Fajjari | VNE-AC: Virtual Network Embedding Algorithm based on Ant Colony Metaheuristic[END_REF], we proposed an embedding strategy, denoted by VNE-AC. It is based on Max-Min Ant System metaheuristic and outperforms all the related strategies found in existing literature [START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF]- [START_REF] Chowdhury | Virtual network embedding with coordinated node and link mapping[END_REF]. However, in spite of the efficiency of the proposed algorithm, we observed two drawbacks in the results obtained. The first one is the underuse of the SN 's resources. In this regard, we noticed that the average rate of bandwidth use is low (i.e. ≃ 15%). We can therefore conclude that the SN 's profitability can be improved. The second drawback is bottlenecking in the substrate links. Therefore, in most cases, rejected VN requests are caused by a bandwidth shortfall. It is worth noting that, over time, the SN 's resources become fragmented due to the arrival and departure of new and already hosted VN s respectively. These observations have motivated us to explore the reconfiguration of VN s mapped in the SN so as to overcome the problem of resource fragmentation. In other words, we aim to 'tidy up' the SN in order to minimise the rate of overloaded substrate links. The rejection rate of VN requests will in turn be minimised.

In this paper we will propose a new hybrid (i.e. reactive and proactive) Virtual Network Reconfiguration algorithm, denoted by VNR. The proposed approach is reactive so it is carried out only when an embedding strategy cannot assign a VN request in the SN . Moreover, VNR is a proactive approach in that it operates only with the SN and its hosted VN s in order to minimise the rejection rate of future VN requests. Note that VNR is not interrelated with any mapping algorithm and operates only with the SN and its hosted VN s. A virtual node with its attached hanging virtual links form a star moving candidate, denoted by ℵ i . Since migration is costly in terms of service interruption period, VNR does not migrate a whole VN topology but only a minimum set of {ℵ i } hosted in the SN . The main idea behind our proposal is to relocate, using migration, star moving candidates {ℵ i } in the aim of minimising the number of congested substrate links. To do so, VNR first of all sorts, in decreasing order, star moving candidates {ℵ i } of all VN s deployed in the SN . Candidates are sorted based on a predefined metric, κ i , quantifying the suitability for migration of each ℵ i . Then, VNR selects only the first successful migrating ℵ i in the sorted selection, among the N max highest (i.e. in terms of κ i ) star moving candidates

{ℵ 1 , ℵ 2 , • • • , ℵ Nmax }.
If VNR does not succeed the migration, the embedding strategy rejects the VN request. Otherwise, the embedding strategy tries to map the VN request again. If it fails once more, the process is repeated from the sorting stage, at the most N mig iterations.

We incorporated our reconfiguration scheme, VNR, with the best embedding strategies, in term of rejection rate, found in existing literature i) VNE-Greedy [START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF] and ii) VNE-AC [START_REF] Fajjari | VNE-AC: Virtual Network Embedding Algorithm based on Ant Colony Metaheuristic[END_REF]. Based on extensive simulations, we found that VNR significantly decreases the rejection rate of VN requests. Moreover, we compared VNR with the reconfiguration algorithm VNA-Periodic [START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF]. The results obtained show that our proposal outperforms VNA-Periodic.

The remainder of this paper is organised as follows. In the next Section we will summarise the related approaches to solving the VN reconfiguration problem. In Section III we will outline the main reasons that motivated this research. Then, we will formulate the VN reconfiguration problem in Section IV, before describing our VN reconfiguration algorithm, VNR, and providing a performance evaluation in Section V and Section VI respectively. Finally, Section VII will conclude this paper.

II. RELATED WORK

VN reconfiguration is a challenging problem that has only been tackled by a handful research papers. To the best of our knowledge, only the following VN reconfiguration algorithms can be found in existing literature.

In [START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF], the authors propose the VN reconfiguration algorithm VNA-Periodic. It is a periodic scheme and is mainly composed of two stages. The first stage involves marking a set of VN s hosted in the SN that make use of at least one overloaded physical node or link. Then, in the second stage, VNA-Periodic uses the corresponding embedding strategy to relocate the marked VN s. The authors claim that the cost of reconfiguration is reduced because only a subset of already mapped VN s is marked. However, we noticed that the cost of VNA-Periodic reconfiguration is high since it is periodically triggered and reassigns the whole VN topology. However, a judicious approach should migrate only virtual nodes and links deployed in excessively loaded substrate nodes and links. Moreover, VNA-Periodic does not move the marked VN s by itself. It 'sub-contracts' the work to the initial embedding strategy.

In [START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF], the authors restrain the reconfiguration problem. In fact, migration is allowed to the virtual links and prohibited to the virtual nodes. To do so, first the reconfiguration algorithm periodically detects the over-loaded substrate links. Then, it finds new substrate paths or updates the split ratio of virtual links that are in transit within overloaded substrate links. Note that the authors base their proposal on traffic path splitting. Moreover, the authors do not take advantage of migrating traffic sources and sinks (i.e. virtual nodes) to minimise bottlenecking in the SN .

In [START_REF] Marquezan | Distributed autonomic resource management for network virtualization[END_REF], the authors propose an autonomic and distributed reconfiguration algorithm. It is run locally within all substrate nodes. The main idea is to shorten the physical path embedding a virtual link that overloads at least one substrate link according to its incoming/outgoing traffic. To do this, either the source or the destination of traffic (i.e. virtual node) is moved in order to shunt the overloaded substrate link. The reconfiguration algorithm is divided into five stages. First, each substrate node monitors and analyses the presence of overloading traffic. Then, it exchanges monitoring information with its neighbours. Next, each substrate node analyses the received information and decides whether to migrate one of its hosted virtual nodes or to receive a virtual node from its neighbours. After that, a receiving substrate node allocates the resources required to host the moving node. Finally, the virtual node is moved and hence the path length is reduced. The main criticism of this approach is that the migration of nodes is triggered without considering the notion of access and core routers. Besides, contracting a path may require a great deal of moving until the path's length becomes equal to one hop. Moreover, the migration frequency of routers depends on the traffic load, which is actually unstable and correlated to the running applications.

In [START_REF] Butt | Topology-awareness and reoptimization mechanism for virtual network embedding[END_REF], the authors propose a reactive reconfiguration scheme that is executed only when the defined embedding strategy rejects the VN request. To achieve this, the proposed algorithm first detects the unmapped virtual nodes and links causing the VN request rejection. Then, candidate substrate nodes, C i , for each unmapped virtual node, n i , are selected. Next, in order to map n i , the algorithm tries to migrate one of the virtual nodes mapped in C i to one node among the potential candidate nodes. The algorithm also detects the bottlenecked substrate links causing the embedding to be blocked. Then, the strategy tries to re-assign one of the virtual links transiting over the overloaded substrate link. To do so, the authors make use the maximum flow algorithm when setting the residual bandwidth of the bottlenecked link to zero. Note that the authors assume that candidate substrate nodes are predefined for each virtual node, which is not realistic. In fact, many embedding strategies do not return this information, such as [START_REF] Fajjari | VNE-AC: Virtual Network Embedding Algorithm based on Ant Colony Metaheuristic[END_REF]- [START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF]. Moreover, the reconfiguration strategy re-assigns virtual links without taking advantage of moving the source and destination (i.e. virtual node). Besides, the maximum flow algorithm does not minimise the path length and consequently bandwidth allocation is not optimised.

In this paper we will propose a new virtual network reconfiguration, VNR. Unlike [START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF], we do not relocate the whole VN topology but only a star in the aim of minimising the cost of reconfiguration. Moreover, our proposal is reactive and is not periodically executed as 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] Marquezan | Distributed autonomic resource management for network virtualization[END_REF]. Besides, it can be considered as a proactive approach since it also 'tidies up' the SN in order avoid future VN rejection. Unlike [START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF], [START_REF] Butt | Topology-awareness and reoptimization mechanism for virtual network embedding[END_REF], VNR is not interrelated with the embedding strategy and does not need any details about the VN request rejected (e.g. unmapped virtual nodes, etc). Finally, our proposal is not based on path splitting as in [START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF] and takes into account the access and core routers, unlike [START_REF] Marquezan | Distributed autonomic resource management for network virtualization[END_REF].

III. MOTIVATION FOR VN RECONFIGURATION

In our previous work [START_REF] Fajjari | VNE-AC: Virtual Network Embedding Algorithm based on Ant Colony Metaheuristic[END_REF], we proposed the embedding strategy called VNE-AC which is based on Max-Min Ant System metaheuristic. The rejection rate of VN requests obtained with VNE-AC is equal to 4.56 ± 0.40%. It is worth noting that the latter result is the lowest obtained result compared with related strategies and it is calculated according to the benchmark scenario assumed in [START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF]- [START_REF] Chowdhury | Virtual network embedding with coordinated node and link mapping[END_REF]. We analysed the extensive simulation traces and determined the reasons for VN rejection. In fact, ≃ 99% of rejections were caused by a bandwidth shortage (i.e. substrate links). The remaining, ≃ 1% was due to a lack of processing power or memory (i.e. substrate nodes).

We calculated the average resource use as illustrated in Fig. 1 and noticed that during simulations, the peak average bandwidth use in the SN is equal to 18%. Thus, we concluded that SN use is not optimised since ≃ 99% of VN rejections are caused by bandwidth deficiency while, at the most, only 18% of bandwidth is exploited in the SN . Moreover, we concluded that many substrate links are overloaded (i.e. bottlenecked).

These findings motivated us to explore the reconfiguration of VN s already hosted in the SN . Thanks to migration techniques, moving virtual nodes [START_REF] Wang | Virtual routers on the move: Live router migration as a networkmanagement primitive[END_REF] and paths [START_REF] Agrawal | Routerfarm: towards a dynamic, manageable network edge[END_REF] becomes easily feasible. Thus, our aim is to propose a new reconfiguration algorithm to balance the load within the SN . As a result, the VN rejection rate will be minimised.

IV. FORMULATION OF VN RECONFIGURATION PROBLEM

We can model the SN as an undirected graph, denoted by G s (N s , E s ), where N s and E s are the sets of physical nodes and their connected links respectively. Each physical node, n s i ∈ N s , is characterised by its i) residual processing power (C n s i ), ii) residual memory (M n s i ) and iii) type: access or core (X n s i ). Note that if X n s i = 1, then n s i is an access node. Otherwise, X n s i = 0. Likewise, each physical link, e s x ∈ E s , is typified by its available residual bandwidth, denoted by B e s

x . Similarly, a VN request can be modelled as an undirected graph, denoted by G v (N v , E v ), where N v and E v are the sets of virtual nodes and their virtual links respectively. Within a VN request, each virtual node, n v i ∈ N v , is associated with the i) required processing power (C n v i ), ii) required memory (M n v i ), and iii) its type (X n v i ). Moreover, each virtual link, e v

x ∈ E v , requests B e v x in terms of bandwidth. As stated in Section III, the main aim is to decrease the number of congested substrate links since substrate nodes do not affect the rejection of VN requests. Let ζ denote the set of α-congested substrate links. Formally,

ζ = {e s x ∈ E s : B e s x ≤ (1 -α)B max e s x } (1)
where B max e s

x is the bandwidth capacity of e s x and 0 ≤ α ≤ 1. In fact, our first objective is to reconfigure the Accepted VN Requests, AR, within the SN in the aim of minimising the number of α-congested links. Formally,

minimise AR (|ζ|) (2)
Our second objective is to minimise the cost of reconfiguration. Let φ denote the migration cost, based on the reconfiguration cost proposed in [START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF], then we can define φ as the weighted sum of migrated virtual nodes φ n and links φ e (i.e. φ = aφ n + bφ e ). Formally,

minimise AR (aφ n + bφ e ) (3)
where 0 ≤ a ≤ 1 and 0 ≤ b ≤ 1 are the weights of φ n and φ e respectively. Note that a + b must be equal to 1.

In addition, a virtual node, n v , can move to a substrate node, n s , only if both nodes are of the same type (i.e. access or core). Besides, a substrate node cannot embed two virtual nodes belonging to the same VN . The problem outlined above is a multi-objective optimisation problem with conflictual objectives. It is a combinatorial optimisation problem that is known as NP-hard [START_REF] Ehrgott | A survey and annotated bibliography of multiobjective combinatorial optimization[END_REF]. In spite of the similarities between our problem and the MPLS routing problem, none of the MPLS-related strategies [START_REF] Kodialam | Minimum interference routing with applications to mpls traffic engineering[END_REF] can be used. Indeed, the MPLS problem can be formulated as a Multi-Commodity Flow problem [START_REF] Srinivasan | A survey of the role of multicommodity flow and randomization in network design and routing[END_REF] since a source/destination of traffic cannot be migrated. However, in our case, we have more flexibility and the possibility of reducing bottlenecking in the SN by migrating sources/destinations of traffic and/or reassigning virtual links. Hereafter, we will describe our new Virtual Network Reconfiguration algorithm, VNR.

V. PROPOSAL: VNR ALGORITHM

In this section we will describe our VN hybrid reconfiguration algorithm, VNR. Our proposal is a reactive scheme, in that it is executed when the VN embedding strategy rejects a VN x request. Moreover, VNR is not interrelated with any VN embedding strategy. Indeed, VNR is a proactive approach in that it operates only with the SN and its hosted VN s in order to minimise the rejection rate of future VN requests. In other words, our proposal 'tidies up' the SN further to physical resource fragmentation due to the arrival and departure of new and already hosted VN s respectively.

As explained in Section III, the main problem is overloaded substrate links. In this respect, we propose to migrate in each iteration one star moving candidate, denoted by ℵ i . Note that ℵ i is formed by one virtual node and its attached hanging virtual links. The main idea behind star topology moving is to reassign virtual links while migrating the central virtual node. In other words, we can see the migration as an elastic movement in which a moving virtual node n v is fastened with its attached virtual links that can be considered like elastics. Indeed, in most cases, the moving virtual node can land in any substrate node since all VN rejections are caused by a lack of bandwidth, as explained in Section III. Thus, our challenge is to find the best hosting substrate node to reduce the number of α-congested links. In doing so, we will not re-embed all the VN topology but only the canonical star topology ℵ i . Consequently, we will reduce the service interruption period When a VN request is rejected, VNR begins by sorting out the star moving candidates {ℵ i }, in decreasing order, of all VN s mapped in the SN . They are sorted according to κ i a criterion which quantifies the ℵ i 's suitability for migration. To this end, κ i is defined according to i) the number, A i , of αcongested links in the paths embedding ℵ i 's virtual links and ii) its residual lifetime, T i . Formally,

κ i = A i × T i (4)
Note that we favour star moving candidates that will expire as late as possible and which whose virtual links pass through the greatest number of α-congested links. In fact, reconfiguring a {ℵ i } that is soon set to leave the SN is not judicious. For this reason, κ i is proportional to the residual lifetime T i . Initially, VNR selects only the first successful migrating ℵ i , according to the sorting order, among the N max highest ranking star moving candidates {ℵ 1 , ℵ 2 , • • • , ℵ Nmax }. If VNR does not succeed the migration, the embedding strategy rejects the VN request. Otherwise, the embedding strategy tries to map the VN request again. If it fails once more, the process is repeated from the sorting stage, at the most N mig iterations. The VNR strategy is summarised in Algorithms 1 and 2.

To reconfigure ℵ i , our proposal proceeds as follows. First, VNR generates a new substrate network, denoted by SN . It is similar to SN in terms of i) topology and ii) residual resources but without substrate links with residual bandwidth lower than the minimum bandwidth required by ℵ i 's virtual links. Next, VNR verifies whether SN contains a connected component including all the substrate nodes hosting the one-hop neighbours of ℵ i 's star-centre virtual node. If the connected component does not exist, it is impossible to migrate ℵ i because at least one ℵ i 's virtual link cannot be mapped. Otherwise, VNR selects substrate node n s within the connected component, in the aim of migrating ℵ i 's virtual node to n s and its attached virtual links thus minimising ̺ ns ℵi . It is equal to:

̺ ns ℵi =
Average bandwidth of substrate paths hosting

ℵ i A i + 1 (5)
Note that the reassignment of ℵ i 's virtual links is based on a shortest path algorithm using our proposed path definition metric in [START_REF] Fajjari | VNE-AC: Virtual Network Embedding Algorithm based on Ant Colony Metaheuristic[END_REF]. The star moving candidate ℵ i migration method is summarised in Algorithm 3.

VI. PERFORMANCE EVALUATION

In this section, we will study the efficiency of our proposal, VNR. To achieve this, we will first describe our discrete event VN embedding simulator. Then, we will define several metrics in the aim of showing the advantages of VNR compared to the proactive reconfiguration algorithm VNA-Periodic [START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF]. Note that we cannot compare our proposal with the reconfiguration algorithms proposed in [START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF], [START_REF] Marquezan | Distributed autonomic resource management for network virtualization[END_REF], [START_REF] Butt | Topology-awareness and reoptimization mechanism for virtual network embedding[END_REF] since the assumptions and constraints are different. In [START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF] the authors assume a path splitting approach, while in [START_REF] Marquezan | Distributed autonomic resource management for network virtualization[END_REF] the type of router (i.e. access and core) is not taken into consideration and in [START_REF] Butt | Topology-awareness and reoptimization mechanism for virtual network embedding[END_REF] the algorithm requires as inputs the virtual nodes and links that the embedding algorithm failed to assign (see Section II).

Our reconfiguration scheme VNR and VNA-Periodic will be incorporated with the best embedding strategies found in existing literature i) ii) VNE-AC [START_REF] Fajjari | VNE-AC: Virtual Network Embedding Algorithm based on Ant Colony Metaheuristic[END_REF] and ii) VNE-Greedy [START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF]. Finally, we will build on the outputs of the above simulations to assess our proposal and comment the results obtained.

A. Simulation Environment

We implemented a discrete event VN embedding simulator. In this respect, the GT-ITM tool is used to generate random SN and VN topologies. The arrival of VN requests is modelled by a Poisson Process with rate λ A and VN lifetime is modelled by exponential distribution with mean µ L .

As stated in [START_REF] Fajjari | VNE-AC: Virtual Network Embedding Algorithm based on Ant Colony Metaheuristic[END_REF], [START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF], [START_REF] Butt | Topology-awareness and reoptimization mechanism for virtual network embedding[END_REF], we make use the following benchmark scenario. The SN size is set to 100 and, in this case, the ratio of access and core nodes is fixed at 20% and 80%, respectively. Furthermore, the VN size is set according to a discrete uniform distribution, using the values given in [START_REF] Carapinha | Network virtualization: a view from the bottom[END_REF][START_REF] Butt | Topology-awareness and reoptimization mechanism for virtual network embedding[END_REF]. Since virtual access nodes are defined by customers, we can assume that each virtual node could be access or core with a probability of 0.5. It is worth noting that in both cases (VN and SN ), each pair of nodes is randomly connected with a probability of 0.5. The arrival rate, λ A , and the average lifetime, µ L , of VN s are fixed to 4 requests per 100 time unit ) are set according to a continuous uniform distribution, using the values given in [START_REF] Butt | Topology-awareness and reoptimization mechanism for virtual network embedding[END_REF]20]. The number of VN requests are set to 2000, and, based on extensive simulations, N mig and N max are set to 5% and 10% of currently mapped virtual nodes respectively.

We set the parameters of VNE-AC and VNA-Periodic as calibrated in [START_REF] Zhu | Algorithms for assigning substrate network resources to virtual network components[END_REF] and [START_REF] Fajjari | VNE-AC: Virtual Network Embedding Algorithm based on Ant Colony Metaheuristic[END_REF] respectively. Note also that each performance value of pseudo-random strategies is equal to the average of 30 simulations. Moreover, simulation results are always presented with confidence intervals corresponding to a confidence level of 99.70%. Only minute confidence intervals are not shown in the following figures.

B. Performance Metrics

In this section, we will define the performance metrics used to assess our proposal.

1) Q: is the final rejection rate of VN requests.

2) φ: is the cost of migration as defined in equation 3, φ = (aφ n + bφ e ). We set a = b = 1 2 . 3) U(t): measures the average use rate of resources (i.e. processing power, memory, bandwidth) in the SN substrate links at time t. For example, the average bandwidth use rate can be expressed as:

U(t) = 1 |E s | × e x s ∈E s B e x s B max e x s (6)
In the following section, we will present the results of our simulations and summarise the key observations.

C. Evaluation Results

Table I shows a comparison of the rejection rate of VN requests obtained by the embedding strategies VNE-AC and VNE-Greedy when the reconfiguration algorithms (i.e. VNA-Periodic and VNR) are incorporated. We can first of all see that our reconfiguration algorithm VNR and VNA-Periodic decrease the rejection rate of VN requests whatever the embedding strategy used (i.e. VNE-AC and VNE-Greedy). This means that reconfiguration algorithms enhance the acceptance of VN s in the SN . Moreover, the results show that our proposal, VNR, significantly reduces the rejection rate with both mapping strategies and more so than VNA-Periodic. In fact, as illustrated in Table II, our VNR strategy reduces the rejection rate by at least 83% . This is consistently better than VNA-Periodic since VNR is at least 10 times more effective in terms of reducing VN rejection rate.

An important factor to consider when evaluating the effectiveness of a reconfiguration-strategy is the incurred cost of migrating virtual nodes and links. In fact, in spite of the respectively. Note that the rejection rate improvement stills high while the arrival rate grows exponentially. Moreover, with high values of λ, the SN is saturated. On the other hand, VNA-Periodic does not resist to the VN request flow. For example with VNE-AC and λ is equal to 8 and 32, VNA-Periodic reduces the rejection rate by 3.41% and 0.8% respectively. Besides, our tests showed that when λ = 16, VNA-Periodic slightly increases the rejection rate.

Fig. 3 shows the impact of the value of α-congested substrate links on the rejection rate of VN s. We can see that when α is high (e.g. 90%), the rejection rate increases. This can be explained by the fact that VNR only deals with bottlenecked substrate links. Hence, VNR cannot easily 'tidy up' the SN since it acts late. However, with small α values VNR prevents the overloading of substrate links by moving the virtual links mapped to bottlenecked substrate links. Based on extensive simulations, we can see that good performances are achieved with a small value of α.

Fig. 4 illustrates the impact of maximal number of iterations, N mig , on VNR's performance. Note that Fig. 4 depicts the rate of accepted VN requests that needed to be reconfigured in the SN to be mapped. This is carried out according to the maximum number of reconfigurations allowed per VN request (i.e. N mig ). The results show that most (i.e. ≃ 50%) of the embedded VN requests require only one reconfiguration. Moreover, the arrival rate of VN requests has no impact on these results.

VII. CONCLUSION

Our research studied the problem of virtual network reconfiguration. The main objective was to reduce the rejection of virtual networks. To do so, we proposed a new greedy reconfiguration algorithm, VNR whose main aim is to reassign canonical star virtual topologies hosted in the overloaded substrate nodes and links. We incorporated our proposal with the best existing embedding strategies (i.e. VNE-AC and VNE-Greedy) and compared it with the related virtual network reconfiguration algorithm VNA-Periodic. The results obtained show that VNR minimises the virtual network rejection rate at least by ≃ 83% while the cost of reconfiguration is also lower (five times lower than VNA-Periodic).

Fig. 1 .

 1 Fig. 1. VNE-AC: Average resources use

Algorithm 1 : 1 VN x ← Q.pop 2 stop 1 ← f alse 3 i ← 1 4while 6 if

 1121316 Embedding scheme of VN x while VN queue Q is not empty do ( (stop 1 = f alse) and (i ≤ N mig ) ) do 5 Call the embedding strategy to assign VN x

Algorithm 2 : 1 for j=1 to |ℵ| do 2 Calculate κ j for ℵ j 3 4 stop 2 ← f alse 5 j ← 1 6while 7 Migrate

 212342517 VNRGenerate the set of star moving candidates ℵ in the SN Sort out decreasingly {ℵ j } according to {κ j } (stop 2 = f alse) & (j ≤ N max ) do

Fig. 4 .

 4 Fig. 4. VNE-AC + VNR: Impact of N mig

Algorithm 3 :

 3 Migration of ℵ i SN ← SN /{e s x : B e s x < min B e v x ∈ℵi B e v x } s ∈ CC x / migration of ℵ i 's virtual node to n s Select the best substrate node n s ∈ CC x :

	6
		and its attached virtual links succeeds then
	7	Failed migration
	8	else
	9
		migration of ℵ i 's virtual node to n s and its attached virtual links minimises ̺ ns ℵi
	10	Successful reconfiguration
	11	else
	12	Failed migration

1 N v ← {set of 1-hop virtual neighbours of ℵ i 's central 2 virtual node} N s ← {set of susbsrate nodes hosting virtual nodes N v } 3 CC ← connected components of SN 4 if ∃ CC x ∈ CC/ N s ⊆ CC x then 5 if ∄ n

TABLE I REJECTION

 I RATE OF VN REQUESTS -Q (%)

	Strategy	VNE-AC	VNE-Greedy
	Without reconfiguration	4.56 ± 0.40	12.95
	VNA-Periodic	4.31 ± 0.38	11.55
	VNR	0.37 ± 0.098	2.2
	and 1000 time units respectively. We calibrate the capacity of
	substrate nodes and links (i.e. C n s i , M n s i , and B e s x ) according
	to a continuous uniform distribution, taking the values in
	[50, 100]. Similarly, the required virtual resources (i.e. C n v i ,
	M n v i , and B e v x

  Impact of α-congested level to see that our proposal significantly reduces the rejection rate with both VN embedding strategies (i.e. VNE-AC and VNE-Greedy) while the arrival rate of VN s grows. For example, with VNE-AC and λ equal to 8, 16 and 32, VNR reduces the rejection rate by 69.81%, 33.69% and 16.17%

		0.05									TABLE II DECREASE OF REJECTION RATE (%)
		0.045
		0.035 0.04		VNE-AC + VNR VNE-Greedy + VNR					Strategy VNA-Periodic VNR	VNE-AC VNE-Greedy 5.48 10.81 91.88 83.01
		0.03
	Q	0.025
		0.02
		0.015
		0.01
		0.005								0.1
		0	0.5	0.55	0.6	0.65 α-Congested 0.7 0.75	0.8	0.85	0.9	Q	VNE-AC VNE-AC + VNR VNE-Greedy + VNR VNE-Greedy
				Fig. 3. VNR:				0.01
										5	10	15	20	25	30
											λ
											(a) VNR
										Q	VNE-AC VNE-AC + VNA-Periodic VNE-Greedy VNE-Greedy + VNA-Periodic
										0.1
										5	10	15	20	25	30
											λ
											(b) VNA-Periodic
										Fig. 2. Robustness of VN reconfiguration algorithms
											TABLE III
											COST OF MIGRATION -φ
											Strategy	VNE-AC	VNE-Greedy
										VNA-Periodic 2598.13 ± 134.74	3625
											VNR	500.67 ± 35.83	1866
										flexibility that virtualization offers in terms of moving virtual
										nodes and links, the service disruption caused by migrations
										can have a negative impact on running applications (e.g.
										video streaming, VoIP, etc.). Indeed, in [16] we evaluated the
										average migration delay in testbed platform to 2ms, which
										can disturb real-time applications. By triggering reconfigura-
										tion only when needed, VNR significantly reduces the cost

of reconfiguration. As illustrated in Table

III

, our proposal considerably reduces the cost of migration. In fact, the results show that VNR reduces the cost between 2 and 5 times more than VNA-Periodic. We can therefore conclude that our proposal outperforms VNA-Periodic in terms of rejection rate and cost of migration.

Fig.

2

evaluates the robustness of VNR and VNA-Periodic when the arrival rate of VN requests, λ, increases while their average lifetime is fixed. It is clear