Hichem Magnouche

Guillaume Doyen
email: guillaume.doyen@imt-atlantique.fr

Caroline Prodhon

Leveraging Micro-Services for Ultra-Low Latency: An Optimization Model for Service Function Chains Placement

Keywords: micro-services, Placement and Routing, Optimization, Orchestration

The evolution of the Internet tends toward ever requiring lower latency services. Cloud robotics or drone piloting are service use-cases in which the latency of traffic cannot exceed a few milliseconds. Reducing the latency can be achieved through several means, and micro-services deployed over virtual infrastructures appears as a promising way by enabling service chain reductions, micro-function mutualization and parallelism. However, the placement and routing of such components appears as an harder task to achieve as compared to monolithic approaches of the state of the art. Consequently, we propose in this paper a comprehensive optimization model in charge of placing micro-services in a virtualized network infrastructure, under ultra-low latency constraints while preserving resource consumption. By challenging our model with several realistic scenarios in terms of topology and service function chains (SFC), we demonstrate to what extent it improves the overall performance of SFC by especially minimizing the gap between the expected latency and the actual one, as compared to several competitors, thus making it a well-fitted approach for ultra-low latency services.

I. INTRODUCTION

The Internet is ever evolving according to novel usage and needs expressed from end-users and the evolution of the technologies that it leverages. Reducing traffic latency is a core concern for today's cloud gaming and interactive video systems, and especially for emerging services such as cloud robotics, metavers, augmented and virtual reality and haptic internet. For these future services, being able to carry their traffic with no more than a few millisecond is a prerequisite to enable them bringing the expected quality of service to the end-users and consequently allow their adoption.

Reducing the Internet latency is not an issue targeting a single component or service in the end-to-end delivery of traffic, but rather, it can be achieved by considering all the points that can be inflected to globally improve the traffic forwarding delay. Some relevant work has been proposed during the last few years on novel congestion control algorithms (e.g. TCP-Prague) or active queue management strategies (e.g. L4S) to improve the sole packet forwarding performance in routing elements. Besides, network traffic does not only cross routers but also a set of Network Functions (NF) such as firewalls or NAT, all bringing a latency penalty, and thus being subject to improvement.

The Network Function Virtualization (NFV) is now acknowledged as the standard means to deploy such NF. Although its standard usage consists to deploy monolithic NF, it has been recently identified that the split of such functions into micro-services could be highly beneficial to reduce the usage of resources while improving the overall performance of the service delivery. Indeed, micro-services enable the reduction of Service Function Chains (SFC) by removing redundant micro-functions (e.g. packet parsing), mutualizing micro-functions belonging to different NF (e.g. packet classifiers) or parallelizing the processing on independent packet fields. However, in the context where the number of microservices is roughly one order of magnitude larger than that of network functions, and service chains must be restructured to actually leverage the power of micro-services, the question of their efficient orchestration appears as an open issue. Indeed, standard orchestration algorithms, in charge of placement and routing of monolithic NF, are no longer applicable given these particular characteristics (i.e. parallelization, mutualization and scale) exposed by microservices since they consider SFC service chains as linear and therefore do not handle forks and merges.

To that aim, we propose in this paper an optimization model which allows a routing and placement orchestration function to operate on SFC that will eventually be deployed as microservices while preserving ultra-low latency constraints. Our model intrinsically integrates the capability to both mutualize and parallelize micro-services. Furthermore, it is comprehensive, meaning that it encompasses the set of constraints that must be considered to efficiently achieve a satisfying deployment of service function chains and especially the resource it consumes. In order to validate the relevance of our proposal, we implemented it into the CPLEX solver and we performed an exhaustive performance evaluation in which we considered a realistic telco topology, some set of SFC extracted from realistic use-cases and we demonstrate to what extent it outperforms current approches from the state of the art leveraging monolithic NF but also micro-services leveraging the sole mutualization feature.

The paper is organized as follows. Section II presents a literature review of the recent approaches for service function orchestration. Section III presents our model and its math-ematical formulation. In Section IV, tests on the model are developed and analyzed. Finally, Section V concludes the paper.

II. RELATED WORK

A large literature covers the question of placement and chaining of Virtual Network Functions (VNF) in NFV as a means to ensure a prescribed performance level while ensuring a satisfying usage of resources. Besides, several improvements on VNF have been recently proposed to further enhance the overall latency induced by service chains. These are especially VNF parallelization and micro-service architectures. As a set of fields closely related to our work, we subsequently review them and state to what extent our approach fills the gap to provide efficient orchestration means for the placement and chaining of restructured SFC composed of micro-services fulfilling ultra-low latency constraints.

A. VNF Placement and Routing

The VNF Placement and Routing (VNF-PR) problem has attracted a lot of attention for a decade [START_REF] Kaur | A comprehensive survey of service function chain provisioning approaches in sdn and nfv architecture[END_REF]. It exhibits two objectives which are: (1) the placement of VNF on network nodes, and (2) their chaining to satisfy the service requests while respecting various associated constraints. In the majority of the related literature, the formulation of the VNF-PR problem is achieved through an Integer Linear Program (ILP) or a Mixed ILP (MILP). Concerning the resolution of the problem, some proposals use a solver such as CPLEX [START_REF] Addis | On a virtual network functions placement and routing problem: Some properties and a comparison of two formulations[END_REF], [START_REF] Gupta | On service-chaining strategies using virtual network functions in operator networks[END_REF], while some others develop a heuristic algorithm [START_REF] Riggio | Scheduling wireless virtual networks functions[END_REF], [START_REF] Cohen | Near optimal placement of virtual network functions[END_REF] or a meta-heuristic [START_REF] Rankothge | Optimizing resource allocation for virtualized network functions in a cloud center using genetic algorithms[END_REF]. In [START_REF] Addis | On a virtual network functions placement and routing problem: Some properties and a comparison of two formulations[END_REF], Addis et al. consider the placement and routing problem of VNF with only one type of VNF for all services thus making it restricted. In Casado et al. [START_REF] Casado | Virtualizing the network forwarding plane[END_REF], the authors consider the problem in a similar way with a single type of VNF but they use a heuristic algorithm to solve it and consequently reduce the computation time.

In [START_REF] Luizelli | Piecing together the nfv provisioning puzzle: Efficient placement and chaining of virtual network functions[END_REF], Luizelli et al. deal with the VNF-PR issue by using an ILP composed of 9 constraints reflecting the real situation of a network. In this work, close from ours regarding the operational features it considers while being restricted to monolithic VNF and not micro-services, the latency minimization is translated into a constraint instead of the objective function which is rather formulated with the aim of minimizing the number of VNF instances. The authors especially break down the problem into sub-problems and try to optimize them. To that aim, they develop a Variable Neighborhood Search algorithm that tries to find a near-optimal solution for each sub-problem. Similarly, in [START_REF] Luizelli | A fix-and-optimize approach for efficient and large scale virtual network function placement and chaining[END_REF], the authors keep the same model but they use a meta-heuristic-based algorithm and they demonstrate to what extent it is more efficient. In [START_REF] Moens | Vnf-p: A model for efficient placement of virtualized network functions[END_REF], the authors minimize the number of activated nodes instead of VNF instances which shows the relevance of the cost metric choice in the formulation of the VNF-PR issue.

B. VNF Parallelization

In order to optimise the latency of SFC, some contributions propose to parallelize the execution of VNF. [START_REF] Zhang | Parabox: Exploiting parallelism for virtual network functions in service chaining[END_REF] develops a pioneer work with an algorithm allowing to carry out a graph parallelizing the whole of the parallelizable VNF. To that aim, the algorithm is based on a table which states whether or not two services function are parallelizable given that the processing carried out on the packets are not related to each other. The authors propose to implement parallelism of VNF for those deployed on the same node as well as different nodes, standing for internal and external parallelism. Nevertheless, the parallelism on different nodes can controversially degrade the SFC latency as it requires to copy and merge packets, whereas within the same node, the VNF can use a shared memory, as proposed by DPDK [START_REF] Foundation | Data plane development kit[END_REF]. Subsequently, among the most relevant proposals, [START_REF] Sun | Nfp: Enabling network function parallelism in nfv[END_REF] proposes to solely implement internal parallelism of NF with the condition that all SFC are placed on the same node. In order to limit the copy/merge time, the authors propose two techniques: (1) only copy the header when some processing is performed on it, and (2) use the shared memory when the processed packet fields are different. In a similar way to the former [START_REF] Zhang | Parabox: Exploiting parallelism for virtual network functions in service chaining[END_REF], [START_REF] Sun | Nfp: Enabling network function parallelism in nfv[END_REF] also proposes a parallelization table allowing to state which VNF can be parallelized. Finally, [START_REF] Xie | Flexchain: Bridging parallelism and placement for service function chains[END_REF] proposes a parallelization approach that addresses the weaknesses of [START_REF] Zhang | Parabox: Exploiting parallelism for virtual network functions in service chaining[END_REF] and [START_REF] Sun | Nfp: Enabling network function parallelism in nfv[END_REF] by parallelizing VNF placed on the same node without any condition on the whole SFC, thus preventing the loss in copy/merge latency on different nodes. Besides, it also allows better agility because the parallelism is decided after deployment and does not require the whole SFC to be on the same node.

C. Micro-services: Architectures and Orchestration

For a couple of years, the benefits of micro-services have been demonstrated [START_REF] Chowdhury | Re-architecting nfv ecosystem with microservices: State of the art and research challenges[END_REF] as an alternative to standard monolithic VNF which exhibit three important limits: the overlapping of functionalities, the loss of CPU cycles and the lack of flexibility in scaling. Following this idea, several microservices architectures have been designed and implemented, such as Microboxes [START_REF] Liu | Microboxes: High performance nfv with customizable, asynchronous tcp stacks and dynamic subscriptions[END_REF] and Openbox [START_REF] Bremler-Barr | Openbox: A software-defined framework for developing, deploying, and managing network functions[END_REF], all bringing specific performance enhancements which mainly leverage lightweight virtualization with containers and zero-copy of packets with DPDK [START_REF] Foundation | Data plane development kit[END_REF].

Concerning the placement and chaining of micro-services, in [START_REF] Hassan | Exploring microservices as the architecture of choice for network function virtualization platforms[END_REF], the authors address the intra-and inter-server connectivity and their impact on the communication between microservices that should be well-performing to minimize end-toend latency. They propose an ILP placement model whose objective function is to minimize the latency delay between the different micro-services. They also propose some constraints specific to the end-to-end latency as well as the NFV infrastructure. However, no resolution algorithm is developed to demonstrate the capability of the approach to be considered in real situations. In [START_REF] Sheoran | Contained: An nfv micro-service system for containing e2e latency[END_REF], the authors also develop a placement solution that limits end-to-end latency and minimizes the exchange of messages between VNF. In order to reduce latency, the authors focus on minimizing the communication delay between the different VNF and underlying micro-services and therefore, they create network micro-service bundles called Affinity Aggregates which are a set of VNF or micro-services that exhibit a heavy communication and should therefore be deployed in a close way. [START_REF] Meng | Micronf: An efficient framework for enabling modularized service chains in nfv[END_REF] exploits the advantages of microservices (re-usability, light weightiness, and better scaling) to overcome the performance degradation that NFV can generate with monolithic NF. It proposes MicroNF, a framework based on three axes: (1) a reconstruction of SFC upon reception in order to re-use micro-services already deployed in the infrastructure and also to re-factor micro-services when possible; (2) a micro-services placement which tries to consolidate them on the same node (i.e. with the largest number of microservices related to the same VNF); and (3) a scaling approach that attempts to balance the load between the network nodes to avoid duplicating micro-service instances and thus limit communications.

Mutualization consists of grouping two identical microservices belonging to the same SFC in a single one. It makes possible first to shorten the length of the SFC and consequently its latency, and second to save memory and CPU resources. Such an approach has been studied in [START_REF] Meng | Micronf: An efficient framework for enabling modularized service chains in nfv[END_REF], [START_REF] Chowdhury | A disaggregated packet processing architecture for network function virtualization[END_REF] as part of the functional decomposition of VNFs into microservices. These research works particularly show that the mutualization of two identical micro-services is not systematic. Indeed, it requires checking the overall set of micro-services from the original SFC to be sure that the processing of packet data will not be affected. This is achieved thanks to a mutualization table as proposed by [START_REF] Meng | Micronf: An efficient framework for enabling modularized service chains in nfv[END_REF] who focuses on this particular enhancement. Besides, [START_REF] Chowdhury | A disaggregated packet processing architecture for network function virtualization[END_REF] also proposes a framework supporting microservices that includes an algorithm allowing the mutualization of micro-services. However, it does not propose any model nor algorithm for the placement and chaining of micro-services.

Through this survey of related literature, we observe that a consequent work has been carried out in order to minimize the latency of SFC, whether it relies on the routing and placement modeling [START_REF] Kaur | A comprehensive survey of service function chain provisioning approaches in sdn and nfv architecture[END_REF], [START_REF] Addis | On a virtual network functions placement and routing problem: Some properties and a comparison of two formulations[END_REF], [START_REF] Casado | Virtualizing the network forwarding plane[END_REF]- [START_REF] Moens | Vnf-p: A model for efficient placement of virtualized network functions[END_REF], VNF parallelism [START_REF] Zhang | Parabox: Exploiting parallelism for virtual network functions in service chaining[END_REF], [START_REF] Sun | Nfp: Enabling network function parallelism in nfv[END_REF], [START_REF] Xie | Flexchain: Bridging parallelism and placement for service function chains[END_REF] or micro-services decomposition and mutualisation [START_REF] Chowdhury | Re-architecting nfv ecosystem with microservices: State of the art and research challenges[END_REF], [START_REF] Hassan | Exploring microservices as the architecture of choice for network function virtualization platforms[END_REF], [START_REF] Chowdhury | A disaggregated packet processing architecture for network function virtualization[END_REF]. As highlighted in [START_REF] Meng | Micronf: An efficient framework for enabling modularized service chains in nfv[END_REF], we also state that the micro-services approach used without mutualization, exhibits a negative impact on the global latency of SFC. In a similar way, the parallelism, used in a non-optimal way, can further increase the latency instead of reducing it [START_REF] Xie | Flexchain: Bridging parallelism and placement for service function chains[END_REF] and to the best of our knowledge, it has only been considered for monolithic VNF. Consequently, we propose in this paper a comprehensive optimization model specific for a robust and flexible microservices orchestration leveraging both mutualization and optimized parallelism.

III. A MICRO-SERVICE ORCHESTRATION MODEL

In this section, we present the micro-services placement and chaining orchestration problem and then, we develop its mathematical formulation. Wishing to optimise the SFC latency and benefit from the agility offered by micro-services, we propose an approach allowing to: (1) mutualize microservices through a pre-processing algorithm; (2) place and chain micro-services through a MILP that also (3) efficiently manages internal and external parallelization of micro-services according to the infrastructure setup (i.e. number of nodes and links as well as their available resources).

A. Problem Statement

Definition: The micro-services placement and routing problem we study, is defined on a network graph G = (N, L), where N is a set of nodes and L a set of links between nodes. Q is a set of SFC requests, with each request q ∈ Q being characterized by a source S q , a destination D q , a nominal bandwidth B q statistically representative for request q, a maximum execution latency Λ q and a set of micro-services of different types to be traversed by an edge flow. The microservices placement and chaining optimization problem consists in finding:

• The placement of micro-services over network nodes;

• The assignment of requests to micro-services already placed; • The chaining for each request, subject to:

• Memory node capacity constraints;

• Micro-services forwarding and execution latency constraints; • Parallelism execution constraints. The optimization objective chosen in our work is the minimization of the latency delay on service requests according to their latency specification. Indeed, we consider that:

• The available nodes have no usage cost but the available resources expressed in terms of CPU and memory are limited; • The available links have no usage cost but the flow rate on each one is limited; • The memory required for the deployment of microservices is similar for all micro-services; • Sharing the usage of micro-services between different SFC is not allowed.

B. Overall Approach

Our approach is developed with the aim of taking advantage of the micro-service features in order to reduce the endto-end latency of SFC. It consists in two parts: (1) a preprocessing algorithm that performs the mutualization, a preparallelization on the set of SFC, and provides the Q set and parallelism parameters to be used in our model, and (2) a Mixed Integer Linear Programming (MILP) translating the problem of placement and chaining of micro-services, which is solved by taking into consideration the parallelism parameters among other constraints.

1) SFC Pre-processing: The pre-processing phase needs two-dimensional parallelism and mutualization tables as inputs, which indicate whether two micro-services are mutualizable or parallelizable as developed in the literature [START_REF] Xie | Flexchain: Bridging parallelism and placement for service function chains[END_REF], [START_REF] Meng | Micronf: An efficient framework for enabling modularized service chains in nfv[END_REF]. To understand the pre-processing, let us take the example depicted in Figure 1, where a request q is made up of an original SCF containing 5 sequential micro-services. Supposing that the tables indicate that micro-services 1 and 5 can be mutualized and micro-services 2, 3 and 4 can be parallelized, our algorithm builds a new SFC made up of 4 micro-services as pictured in the second part of Figure 1. Note that depending on the infrastructure constraints, the MILP of the second phase may not necessarily lead to the placement and execution of micro-services 2, 3 and 4 in parallel, even if this was allowed in the pre-processing phase.

2) Managing Parallelized Micro-services: The preprocessed SFC are provided to the model with some parallelism parameters to carry out a placement and chaining. The aim here is to minimize the sum of the gaps between the required and achieved latency after deployment, for each SFC while taking into account the infrastructure setup. The key-point stands in the choice of service parallelization which is managed by the model through the generation of forks and mergers of two types:

• internal forking: a packet is duplicated within a node to reach a set of further parallelized micro-services located on the same node. This kind of internal parallelism does not require copying data, nor merging, since, as reviewed in sub-section II-B, technologies such as DPDK allow shared memory to be used. • external forking: a packet outgoing from one node is duplicated to subsequent NF located on two or more successor nodes. Such external parallelism implies a copy of the packets to be sent to the different micro-services deployed on different nodes and then a merging of the resulting packets too.

This latter mechanism leads us to add a latency cost for the external fork corresponding to the copy and merge time, unlike the internal fork. The originality of the model lies then in the fact that depending on its configuration, it decides which micro-services to parallelize internally, externally or not at all. However, this complicates the computation of the induced latency. Indeed, when the model defines a placement, it also has to indicate whether the micro-services on the nodes (if parallelizable) are visited consecutively or not. In order to know which micro-services are running in parallel within a node, we use groups that gather them together.

To illustrate this principle, the example in Figure 2 shows 3 different possible deployments for request q, as introduced in Figure 1. The first one (A) does not parallelize any microservices: although two are on the same node (i.e. microservices 2 and 3), they do not belong to the same group. In this case, the resulting SFC is composed of a single group (g 1 ) on nodes B and D, and two groups (g 1 and g 2 ) on node E. The second deployment (B) proposes an external parallelization of micro-services 2 and 3 on two different nodes, thus a single group (g 1 ) per node. This induces an additional latency corresponding to the copying and merging operations. Finally, deployment (C) parallelizes micro-services 2, 3 and 4 by performing internal and external parallelism. This time, a single group (g 1 ) is assigned to each of nodes B, C and D. In this case also, a fork cost is accounted because the latter is external. Beyond, this SFC example

C. Mathematical Formulation

Table I provides the set of notations used for the formulation of our MILP formalizing the problem of placement and chaining of micro-services.

In this model, we define seven decision variables. x nf q are used to decide which micro-service f ∈ F of request q ∈ Q should be placed on which node n ∈ N . y nf q allow to know whether micro-service f ∈ F is placed on the nodes preceding n ∈ N (n included) on the path related to request q ∈ Q. Variables a n1n2q are used to decide whether the link between nodes n 1 and n 2 from set N is used for service request q ∈ Q, all links being oriented in this model. Having allowed the forks, we introduce variables l n1n2qh to decide whether the link between nodes n 1 and n 2 from set N is used within path h ∈ F q of the chaining of request q ∈ Q. This allows to define the set of possible paths for the chaining of each SFC. Variables bf nqh indicate the existence of a fork on node n ∈ N relative to a request q ∈ Q and path h ∈ F q . Then, the latency of request q ∈ Q finishing its process at node n ∈ N is equal to the greatest latency of the different relative paths. This requires to define a longest path, managing the notion of group as introduced in section III-B2. A group g ∈ F q is composed of a set of a single or several parallelized micro-services assigned to node n ∈ N for request q ∈ Q and for path h ∈ F q . Since all the micro-services belonging to the same group run in parallel, we use variable γ nqf g to indicate whether micro-service f ∈ F related to request q ∈ Q is placed in group g ∈ F q attached to node n ∈ N , and variable σ nqgh which corresponds to the latency of group g ∈ F q relative to request q ∈ Q and path h ∈ F q . Finally, in order to minimize the overall gap between the required and actual latency we introduce variable r q which represents the gap latency for each request q ∈ Q .

This leads to the following model, consisting in minimizing an objective function relative to the lag behind expected Fig. 2 Parallelism possibility into service request Model parameters m Constant value guaranteeing compliance with constraints Binary variables x nf q = 1 if function f is placed on node n for request q y nf q = 1 if function f is placed on node n or before for request q an 1 n 2 q = 1 if link (n 1 , n 2 ) is activated for request q l n 1 n 2 qh = 1 if link (n 1 , n 2 ) is activated for request q for path h γ nqgf = 1 if function f related to request q placed on node n belongs to group g bf nqh = 1 if there is a fork on node n for request q and for path h p nf q

Intermediate variable Continuous non-negative variables rq

Gaps between the required and achieved latency for request q after deployment σ nqgh Latency of group g related to request q, node n and path h onq Order of node n in the chaining of request q TABLE I: Notation table latency and subject to the two dozen of constraints that we describe subsequently.

The objective function (1) minimizes the latency delay, r q of request q. The second term is relative to additional variables used in the constraints. min q∈Q r q + n∈N q∈Q f ∈Fq h∈Fq y nf q + bf nq h + p nf q (1) Constraints ( 2) and (3) guarantee that if there is an incoming flow in a node for a certain service request q, and the node is neither a source nor a destination node, an outgoing flow must exist and vice-versa. Unlike a standard chaining problem, outgoing flows can be greater or lower than incoming flows and vice-versa, due to the fork-merge managed by the model.

e∈N a enq ≥ a nsq ∀q ∈ Q, n, s ∈ N ̸ = S q , D q (2) s∈N a nsq ≥ a enq ∀q ∈ Q, n, e ∈ N ̸ = S q , D q (3)
In order to avoid cycles in the chain and to force it to be elementary, constraints (4) ensure that each node has an order in the chain and that this order is respected.

o n1 q ≥ o n2 q +a n2 n1 q -m(1-a n2 n1 q ) ∀n 1 , n 2 ∈ N (4)
The set of constraints ( 5) to [START_REF] Moens | Vnf-p: A model for efficient placement of virtualized network functions[END_REF] allow to set variables y nf q to 1 in case function f is placed on node n or before for request q. y nf q ≥ x nf q ∀n ∈ N, f ∈ F, q ∈ Q (5)

a n1 n2 q -1 + x n1 f q -x n2 f q ≤ y n2 f q ∀n 1 , n 2 ∈ N, ∀q ∈ Q, ∀f ∈ F q (6) y n1 f q -1 + a n1 n2 q ≤ y n2 f q ∀n 1 , n 2 ∈ N, ∀q ∈ Q, ∀f ∈ F q (7) n1∈N y n1 f q + a n1 nq ≤ p nf q ∀n ∈ N, ∀q ∈ Q, ∀f ∈ F q (8) x nf q ≤ p nf q ∀n ∈ N, ∀q ∈ Q, ∀f ∈ F q (9) y nf q ≤ p nf q ∀n ∈ N, ∀q ∈ Q, ∀f ∈ F q (10)
More specifically, constraints (5) allow to set variables y nf q to 1 if x nf q equal to 1. Constraints (6) aim at setting variables y n2f q to 1 if the relative function f is placed on node n 1 , preceding node n 2 and concerning request q. Constraints (7) allow to set variables y n2f q to 1 if y n1f q equal to 1 and if n 1 is preceding node n 2 concerning request q. The set of constraints ( 8), ( 9) and ( 10) allow to set variables y nf q to 0 if function f is not placed on node n and it is not placed on any of the preceding nodes of n as well as their respective preceding nodes.

Constraints [START_REF] Zhang | Parabox: Exploiting parallelism for virtual network functions in service chaining[END_REF] ensure that all micro-services related to each request q are placed on the destination node or before on the chain related to q. y nf q ≥ y Dq f q ∀q ∈ Q, ∀f ∈ F q , ∀n ∈ N [START_REF] Zhang | Parabox: Exploiting parallelism for virtual network functions in service chaining[END_REF] Constraints ( 12) to ( 14) guarantee that if two micro-services are placed in the same group, they can be processed in parallel, and this in two ways: the first states that the two micro-services can be technically parallelizable, the second states that, in the SFC, the two micro-services are parallelizable, i.e. none of them is in the precedence list of the other.

γ nqgf1 + γ nqgf2 ≤ T f1f2 + 1 ∀n ∈ N, ∀q ∈ Q, ∀g, f 1 , f 2 ∈ F q (12) γ nqgf1 + γ nqgf2 ≤ P f1 f2 q + 1 ∀n ∈ N, ∀q ∈ Q, ∀g, f 1 , f 2 ∈ F q (13) σ nqgh ≥ λ f (γ nqgf + l nn2qh -1) ∀q ∈ Q, f ∈ F q , ∀n, n 2 ∈ N, ∀h, g ∈ F q (14)
Constraints ( 14) ensure that variables σ nqgh are greater than or equal to the execution latency of all the micro-services belonging to group g on path h.

Constraints ( 15) allow variables r q to be equal to the gaps between the required and achieved latency for request q which do not respect their latency specification.

n1∈N n2∈N l n1n2qh * ∆ n1 n2 + n∈N g∈F q σ nqgh + n∈N bf n * CB -Λ q ≤ r q ∀q ∈ Q, ∀h ∈ F q (15)
Constraints ( 16) and ( 17) respectively ensure that the CPU resources and the available flow rate on each link are respected for each node.

q∈Q f ∈Fq x nf q * Rm f ≤ R n ∀n ∈ N (16) q∈Q f ∈Fq a n1n2q * Db q ≤ Da n1n2 ∀n 1 , n 2 ∈ N (17)
Finally, the model includes the following types of variables.

x nf q ∈ {0, 1} ∀n ∈ N, f ∈ F, q ∈ Q (18) y nf q ∈ {0, 1} ∀n ∈ N, f ∈ F, q ∈ Q (19) a n1n2q ∈ {0, 1} ∀n 1 , n 2 ∈ N, q ∈ Q (20) l n1n2qh ∈ {0, 1} ∀n 1 , n 2 ∈ N, q ∈ Q, h ∈ F q (21) γ nqf g ∈ {0, 1} ∀n ∈ N, q ∈ Q, f ∈ F, g ∈ F q (22) bf nqh ∈ {0, 1} ∀n ∈ N, q ∈ Q, h ∈ F q (23) p nf q ∈ {0, 1} ∀n ∈ N, q ∈ Q, f ∈ F (24) r q ≥ 0 ∀q ∈ Q (25) σ nqgh ≥ 0 n ∈ N, q ∈ Q, g ∈ F q , h ∈ F q (26) o nq ≥ 0 n ∈ N, q ∈ Q (27)
Besides, the model also includes some additional constraints, not detailed here due to space constraints. Briefly, they ensure that: (a) the placement of all the micro-services related to each request is achieved; (b) the chaining passes through the necessary micro-services; (c) the memory capacity of each node is respected; (d) each chaining starts with the source node and ends with the destination node related to each request; (e) variables bf nqh are activated when an external fork takes place on node n for request q and on the path h ; (f) the links related to each path h are only active if they are active in the request chain; (g) the flows for each path are respected; (h) each path related to a request q passes through at least one microservices related to its request; (i) each deployed micro-services belongs to a group. One can lastly notice that the constraints of nodes ordering respect and micro-services ordering respect were inspired by the work carried out in [START_REF] Addis | On a virtual network functions placement and routing problem: Some properties and a comparison of two formulations[END_REF], [START_REF] Mouaci | Virtual network functions placement and routing problem: Path formulation[END_REF]. This studied problem is NP-complete. Indeed, by considering the particular case with only one type of VNF, made of a single microservice without parallelism nor mutualisation option, it reduces to the classical VNF placement and chaining problem that is already NP-Complete [START_REF] Addis | On the complexity of a virtual network function placement and routing problem[END_REF].

IV. EVALUATION

A. Implementation

In order to validate our model and its performance under various conditions, we have implemented it into CPLEX v20.1.0. The C++ code is 1135 lines long and available at: https://www.mosaico-project.org/outcomes for reproductibility. The correctness checking has consisted in verifying the following bias: (1) absence of circuits, (2) deployment of all micro-services related to each request, (3) respect of the ordering between micro-services, (4) respect of memory resource consumption, (5) correctness of latency computation, and finally (6) correctness of parallelism and mutualization in relation to the mutualization and parallelism tables. All experiments were performed on a 11th gen. Intel Core i7-1165g7@2.80GHz 1.69GHz computer with 16GB of RAM and Windows 10 Prof. Educ. as the underlying operating system.

B. Evaluation Scenarios

Our evaluation scenarios aims at (1) understanding the performance of our model in realistic situations and (2) comparing it with current competitors. We have especially considered those standing for acknowledged approaches in the literature, namely: (a) Monolithic VNF placement (Mono); (b) Microservices placement with neither mutualization nor parallelization enhancements (Micro); (c) Micro-services placement with mutualization enhancement (MicroM), and finally (d) Microservices placement with both mutualization and parallelization enhancements (MicroMP); the latter standing for our model.

All the parameters we considered in our evaluation are summarized in Table II and motivated subsequently. The implemented topology, extracted from the SNDlib 1 library, is 1 Survivable fixed telecommunication Network Design -http://sndlib.zib.de/ Then, each region has been split into two layers: one node acting as a regional PoP connected to other regional PoPs according to the telco topology, but also acting as an aggregation point for a few local nodes connected to it through a regional loop forming a ring sub-topology. The different SFC we consider are the reflect of those that have been studied in the dedicated literature [START_REF] Luizelli | A fix-and-optimize approach for efficient and large scale virtual network function placement and chaining[END_REF], [START_REF] Mouaci | Virtual network functions placement and routing problem: Path formulation[END_REF] which are composed of NF (Firewall, NAT, Traffic monitor and IPS) whose decomposition into microservices is acknowledged. As the core benefits of micro-services, we have considered the mutualization and parallelization tables illustrated in Table III, as defined in [START_REF] Meng | Micronf: An efficient framework for enabling modularized service chains in nfv[END_REF] and [START_REF] Zhang | Parabox: Exploiting parallelism for virtual network functions in service chaining[END_REF], where a "X" in a cell means that the related row and column micro-services can be mutualized or parallelized, respectively. Finally, regarding the varying parameters of our experiments, we have deliberately chosen to limit the computation time, which may be very long in case of exact-resolution, to a realistic order of magnitude to respect what the usage of such a placement algorithm in a real maintenance process of a virtual telco infrastructure could be. As such, the computation time of each experiment has been limited to 600s and, given this limit, the computable instances of placement covers the scales provided in [START_REF] Meng | Micronf: An efficient framework for enabling modularized service chains in nfv[END_REF] and [START_REF] Zhang | Parabox: Exploiting parallelism for virtual network functions in service chaining[END_REF] more than 30 hours of computation to encompass all cases. Finally, the prescribed latency for SFC ranges from 5 to 10ms, thus standing for those of realistic ultra-low latency use-cases.

C. Results Analysis

The different metrics we measure in our performance evaluation campaign aims at first considering the overall latency of service chains as a prerequisite and then the resource consumption to instantiate SFC over the telco infrastructure. More precisely, this stands for (1) the sum of the differences between the latency required by each SFC and the effective latency after deployment, as depicted in first row of Figure 3; (2) the number of nodes activated for the deployment of all the SFC, an activated node being a node on which at least one micro-service is instantiated, as depicted in second row of Figure 3; and (3) the number of links activated for the deployment of all SFC, as depicted in third row of Figure 3.

1) Latency Benefit: The first line of Figure 3 shows that MicroMP performs better in terms of latency gap in the different configurations under test. Moreover, this latency gain does not require a higher consumption of resources. We also notice that the more the system increases in size and load, the greater the benefit of MicroMP is. The reason is that the more micro-services there are, the more chances of parallelism and mutualization there are, these two enhancements allowing the actual latency reduction. One can also see that Micro is the approach with the largest latency gap for all configurations. This is due to its basic decomposition into micro-services which generates a latency overhead since there are more entities to deploy. This confirms again that the decomposition into micro-services is relevant in terms of latency gain only when using mutualization and parallelism enhancements. One can also see from the last figure of the first row, that bringing more available resources does not induce much gain in latency. The three configurations +80%, +50% and +20% are indeed almost equivalent regarding that metric.

2) Usage of Infrastructure Resources: The second and third rows of Figure 3 represent the nodes and links usage of the four approaches according to the different configurations. One can see that the usage of resources is more important when switching the micro-services approach and this for all the configurations. The reason is again that with the micro-services approach, more entities have to be deployed, a VNF being composed of 4 micro-services on average [START_REF] Meng | Micronf: An efficient framework for enabling modularized service chains in nfv[END_REF]. Nevertheless, mutualization manages to reduce the consumption of resources by reducing the number of micro-services to be deployed, thus exhibiting a consumption equivalent to that of Mono. Moreover, parallelism forces some of the micro-services to be deployed on the same node, thus bringing a slight gain for MicroMP as compared to MicroM and which, in some cases, even exceeds Mono.

3) Deployment Agility: The third important aspect to notice concerns the deployment agility. Indeed, it can be seen that for some instances and under some configurations (e.g. #Microservices = 5, #SFC = 2), the model cannot find a solution for Mono, despite a sufficient amount of infrastructure resources for their deployment. Indeed, the breakdown into microservices allows for better agility as compared to Mono because the components are lighter and memory space management is therefore easier to achieve. Table IV summarises the average computation features of CPLEX for the different instances. Each instance represents a configuration setup with the values presented in Table II, and it has been repeated eight times with different SFC to bring some randomness. Regarding the computation time, limited to 600s, we notice that for the Mono approach, the optimal solutions were found much earlier (1,5 seconds on average) contrary to the Micro approach for which the resolution time is over our limit for almost all instances. In a similar way, the gap with respect to the optimal solution of the Mono approach is zero while that of Micro is around 45%. This indicates that the solutions obtained for the Micro approach can be improved if we allowed more computation time. Nevertheless, with such a limited computation time, the Micro approach is penalized. By contrast, regarding the MicroM and MicroMP approaches, the computation time is below the limit for more than 55% of the cases. In comparison to the Mono approach, this reveals two insights: [START_REF] Kaur | A comprehensive survey of service function chain provisioning approaches in sdn and nfv architecture[END_REF] with MicroM and MicroMP the obtained solutions are not necessarily optimal and, in spite of that, they are better than the optimal solutions of Mono. This means that with more computing time, one could have still better solutions for the MicroM and MicroMP approach; (2) the switch to MicroM and MicroMP requires more computing time due to the complexity of the approach, but less than the Micro approach since there are fewer micro-services to deploy, thus demonstrating the reasonable cost of these approaches.

D. Analysis of Computation Features

V. CONCLUSION AND FUTURE WORK

The development of ultra-low latency applications has required the development of different models optimizing the placement and chaining of VNF, but also the transition to the micro-services approach in order to further reduce latency. However, considering the micro-services approach without optimization controversially augments the latency and the mutualization of redundant micro-services and their parallelization appears as the expected enhancement to reveal the actual performance gain of micro-services. In this paper, we have proposed a micro-services orchestration approach composed of a pre-processing algorithm and a comprehensive mathematical model allowing the placement and chaining of micro-services taking into account their mutualization and parallelism and having as a main objective the reduction of the SFC latency to reach strong prerequisites. With extensive computation of the model, we have demonstrated that it exhibits the best latency performance as compared to monolithic approaches and also various micro-services alternatives. However, the resolution of the model with an exact method is very expensive in computation time which leads us to foresee the realization, in our future work, of an approximate resolution method based on a heuristic algorithm. Beyond, we plan to develop a dynamic version which adapts the placement and chaining according to the evolution of service demands and the infrastructure resources.

Fig. 1 :

 1 Fig. 1: Pre-processing example

Fig. 3 :

 3 Fig. 3: Histogram of the different successful measurements featuring the performance of our model (MicroMP) against three competitors (Mono, Micro and MicroM). (a) Gap of latency between the SFC requirement and that computed by the placement algorithm; (b) Number of nodes required to place the requested SFC; and (c) Number of links required to place the requested SFC, according to (from left to right sub-figures): The number of micro-services, number of SFC, number of nodes and the extra allocated memory resources. Each result is the average of eight repetitions bounded with 95% confidence intervals.

  : A deployment example

		Sets
	N	Nodes
	L in N × N	Links
	Q	Service requests
	F	Micro-services
		Micro-service parameters
	λ f	Execution latency
	Rm f	CPU resource requirements
		Demand parameters
	Sq	Source
	Dq	Destination
	Λq	Latency
	Bq	Throughput
	Fq in Q	Micro-services composition
		Infrastructure parameters
	Mn	Node memory
	Rn	Node CPU resource
	∆n 1 n 2	Link latency
	Dan 1 n 2	Link flow rate
	CB	Bifurcation cost
		Parallelism parameters
	T f 1 f 2 P f 1 f 2 q	Parallelism possibility

TABLE II :

 II Evaluation parameters that of the DFN-Verein European telco. We have partitioned it by selecting only some Point of Presence (PoP) for a given region.

  Table II for the number of nodes, SFC numbers, SFC lengths and nodes capacities. Overall, the results exposed subsequently required

		Rd HC Md Al Dp CIH HC CU PC Out		Rd HC Md Al Dp CIH HC CU PC Out
	Rd	x					Rd	x									x
	HC	x	x	x	x	x	HC	x	x	x	x	x	x	x	x	x	x
	Md	x	x	x	x	x	Md	x			x	x	x	x	x	x	x
	Al		x	x	x	x	Al	x	x		x	x	x	x	x	x	x
	Dp		x	x	x	x	Dp	x			x	x	x	x	x		x
	CIH		x	x	x	x	CIH				x	x	x		x
	HC				x		HC	x	x		x		x	x	x		x
	CU		x	x	x	x	CU	x		x	x	x	x	x	x	x	x
	PC					x	PC	x			x	x	x	x	x		x
	Out					x	Out	x									x

TABLE III :

 III Parallelism (left) and mutualization (right) tables as defined in

TABLE IV :

 IV Features of the different model computations, with I: Instance, Obj (ms): Objective function, Dur (ms): Computation duration, Gap (%): Latency gap.

ACKNOWLEDGMENT

This work is partially funded by the French ANR MO-SAICO project, No ANR-19-CE25-0012.


Michel Crucianu

Jean-Philippe Philippe Tarel

Marin Ferecatu

An Exploration of Diversified User Strategies for Image Retrieval with Relevance Feedback

Keywords: content-based retrieval, user strategy, user emulation, evaluation

HAL is

Introduction

The scarcity and inherent incompleteness of the textual annotations of multimedia content promote the use of search by content in multimedia databases [START_REF] Gevers | Content-based image retrieval: An overview[END_REF], in spite of limitations due to the "semantic gap". To go beyond simple query by example in order to identify more precisely what a user is actually looking for, search engines must include the user in the retrieval loop.

In search with relevance feedback, a session is divided into several consecutive rounds during which the user provides feedback regarding the retrieved results, usually by qualifying content items returned as either "relevant" or "irrelevant". From this feedback, the engine learns the features associated with the desired content and proposes to the user the newly retrieved results. The many relevance feedback methods developed, mostly in the content-based image retrieval community, endeavor to minimize the amount of interaction required for ranking most of the "relevant" images before "irrelevant" ones.

Since large-scale experiments with real users are costly and difficult to set up, evaluations and comparisons of relevance feedback algorithms usually rely on the use of ground truth databases and on an emulation of the user. Such a database is partitioned into well-defined classes of images and the emulated user follows a single, well-prescribed strategy in qualifying returned images as "relevant" or "irrelevant".

But the behavior of real users in qualifying the returned images cannot be expected to comply to strict specifications. Moreover, it is reasonable to imagine that the choice of a strategy has an impact on the quality of the results. How general and meaningful are then the conclusions drawn from comparisons performed with ground truth databases? This is the main issue addressed in the following. For similar cost reasons, we also emulate the user behavior and rely on ground truth databases. However, in the evaluation presented below, multiple user strategies are employed, as well as several image databases of different complexity.

While such an evaluation cannot replace large-scale experiments with real users, it allows to explore the impact of various user strategies, at a lower cost and in a controlled way. This study should bring more confidence in the comparisons between relevance feedback algorithms and to provide some insight into possible relations between the algorithm, the database and the user strategy.

It is also important to find out whether some user strategies help the system perform consistently better, or provide more robustness to changes in the complexity of the database. Such a strategy can then be recommended to the users, even if they would not follow it strictly.

The next section provides details about the relevance feedback algorithms compared here. The eight user strategies that are investigated are introduced in Section 3. Section 4 presents the setting of the study and includes a description of the four ground truth databases employed. The results of all the comparative evaluations are presented and discussed in Section 5.

Relevance Feedback with Support Vector Machines

It is assumed that every image is represented by a signature describing its visual content. The image signatures employed here are presented in Section 4.1. A relevance feedback method is defined by two components: a learner and a selector. At every feedback round, the learner uses the signatures of the images labeled as "relevant" or "irrelevant" by the user to re-estimate a split of the signature space in "relevant" and "irrelevant" regions. Given the current estimation of this split, the selector chooses according to its selection criterion the images for which the user is asked to provide feedback at the next round.

Much work on relevance feedback relies on the use of support vector machines [START_REF] Schölkopf | Learning with Kernels[END_REF] to discriminate between "relevant" and "irrelevant" images (e.g. [START_REF] Hong | Incorporate support vector machines to content-based image retrieval with relevant feedback[END_REF][START_REF] Tong | Support vector machine active learning for image retrieval[END_REF][START_REF] Jing | Learning region weighting from relevance feedback in image retrieval[END_REF]). A support vector machine maps the data (image signatures in the case under study) to a higher-dimensional feature space using a non-linear transformation associated to a reproducing kernel; then, it performs linear discrimination between "relevant" and "irrelevant" items in this feature space. The discriminating hyperplane is only defined by the support vectors and learning is based on quadratic optimization under linear constraints. Learning leads to a decision function over the space of signatures. For every signature, the value of this function is the signed distance between the hyperplane and the mapping of the signature in the higher-dimensional feature space.

The decision function can be used for ranking all the images in the database: the most "relevant" images are those for which the decision function takes the highest positive values. Among the advantages of support vector machines over other learners in the relevance feedback context, can be mentioned the absence of too restrictive assumptions regarding the data, the flexibility (can be tuned by kernel engineering) and the fast learning and evaluation for medium-sized databases.

Most studies consider the Gaussian kernel, K(x i , x j ) = exp (γ x ix j 2 ), with a fixed value for the scale parameter γ. The high sensitivity of the Gaussian kernel to the scale parameter is an important drawback for relevance feedback [START_REF] Ferecatu | Retrieval of difficult image classes using SVM-based relevance feedback[END_REF]. Indeed, since significant variations in spatial scale from one class to another can be found for classes in ground truth databases (as for user-defined classes in real-world applications), any fixed value for the scale parameter will be inadequate for many of these classes. Following [START_REF] Fleuret | Scale-invariance of support vector machines based on the triangular kernel[END_REF][START_REF] Ferecatu | Retrieval of difficult image classes using SVM-based relevance feedback[END_REF], the conditionally positive definite "angular" kernel K(x i , x j ) =x ix j is employed here. It was shown in [START_REF] Schölkopf | The kernel trick for distances[END_REF] that the convergence of support vector machines using this kernel is nevertheless guaranteed. In [START_REF] Fleuret | Scale-invariance of support vector machines based on the triangular kernel[END_REF], the angular kernel was found to have the interesting property of making the support vector machine insensitive to the scale of the data (within the limits set by the regularization bound C).

In most systems, the selection consists in choosing the images currently considered by the learner to be the most relevant. This criterion will be called the selection of the "Most Positive" (MP) candidates. An active learning framework for relevance feedback using support vector machines was introduced in [START_REF] Tong | Support vector machine active learning with applications to text classification[END_REF][START_REF] Campbell | Query with large margin classifiers[END_REF]. The associated selection criterion consists in choosing the images whose signatures are the closest to the current frontier between "relevant" and "irrelevant" images. This will be called the selection of the "Most Ambiguous" (MA) candidates. A drawback of the MA criterion is that very similar images may be selected together. An additional condition of low redundancy was put forward in [START_REF] Ferecatu | Retrieval of difficult image classes using SVM-based relevance feedback[END_REF] and requires the selection of candidates that are far apart, in order to better explore the current frontier between "relevant" and "irrelevant". More specifically, consider that x i and x j are the signatures of two candidate images. To have x i and x j far apart, a low value for K(x i , x j ) is required, since the value of the angular kernel decreases with an increase of the distance d(x i , x j ). The inclusion of this low redundancy condition in the MA criterion will be denoted by MAO (Most Ambiguous and Orthogonal).

To implement the MAO criterion, a larger set of unlabeled images is first selected using MA. Then, the MAO selection is obtained by iteratively choosing as a new candidate the vector x j that minimizes the highest value of K(x i , x j ) for all x i already included in the current MAO selection: x j = argmin x∈S max i K(x, x i ). S is the set of images selected by MA and not yet included in the MAO selection, while x i are the images already in the MAO selection. The number of unlabeled images preselected with MA is a multiple of the number of images for which the user is asked to provide feedback at the next round ("window size", ws below). The size of the preselection is 2 × ws because in previous experiments [START_REF] Ferecatu | Retrieval of difficult image classes using SVM-based relevance feedback[END_REF] it was found to be a good compromise between ambiguousness and low redundancy. The MP and MAO selection criteria are compared in the following, using support vector machines with the angular kernel.

User Strategies

The evaluation and the comparison of relevance feedback algorithms usually rely on an emulation of the user according to the following strategy: given a target class from a ground truth database, the user qualifies at every round all the images returned by the selector as either "relevant" (belong to the target class) or "irrelevant" (don't belong to the target class) and makes no mistakes; this will be called "stoic" user behavior (STO below).

Given the cost and difficulty of setting up large-scale experiments with real users, ground truth databases and user emulation are also employed, but variations of the behavior of the users are investigated (in a controlled way) by defining the following seven new strategies:

(1) An "annoyed" user (ANN) labels only a fixed ratio (50% in the experiments reported here) of the images returned by the selector; the user randomly chooses the images to label, but makes no mistake when labeling them. (2) A "greedy" user (GRE) correctly labels all the "relevant" images (images belonging to the target class), if present, together with the most "irrelevant" image (not belonging to the target class), if any is present. (3) A "cooperative" user (COO) correctly labels the most "relevant" image if at least one is present and the most "irrelevant" image if not. (4) A "minimalist" user (MIN) correctly labels one randomly chosen "relevant" image, if present, and one randomly chosen "irrelevant" image, if present. (5) An "optimistic" user (OPT) correctly labels the most ambiguous among the "relevant" images and the most "irrelevant" image. (6) A "restrictive" user (RST) correctly labels the most "relevant" image if at least one is present and all the "irrelevant" images. (7) A "tired" user (TIR) labels all the images returned by the selector, but makes mistakes (i.e. labels as "irrelevant" a "relevant" image, or as "relevant" an "irrelevant" image) with a given probability (of 0.1 in the following).

While other strategies can be defined, we consider that those listed above cover the main variations expected for the behavior of the users: reliable vs. error-prone, diligent vs. uninvolved, and different ways of collaborating with the system. Most of these strategies were identified by studying the retrieval sessions of a few knowledgeable but non professional users. Two strategies, GRE and RST, were specifically included to study the benefits of labeling many more "relevant" or many more "irrelevant" images. Real behaviors appear to follow a mixture of several strategies, where MIN or ANN steps are more frequent than STO steps.

Four of these strategies (GRE, COO, OPT and RST) rely on the evaluation of a "degree of relevance" by the user. Since the crisp classes of typical ground truth databases do not provide such information, an attempt was made to obtain it automatically. For every class of the ground truth, a support vector machine is trained using as positive examples all the images of the class and as negative examples the rest of the images; the decision function of this support vector machine is then employed for emulating the user during the retrieval sessions. Given a target class and a set of images shown to the emulated user, the more positive the value of this function is, the higher the "relevance", and the more negative its value is, the higher the "irrelevance"; the most ambiguous "relevant" image (for OPT) is the one for which the value of the function is positive but closest to 0. The evaluation of the degree of relevance by real users was found to be relatively subjective. The emulation relying on the decision function of a support vector machine may not correspond to the rating by a real user. The emulation of GRE, COO, OPT and RST may be overly optimistic but MIN can serve as a baseline because it does not employ the decision function.

4 Setting of the Study

ground truth Databases and Description of the Visual Content

Ground truth image databases are used for evaluating the selection criteria and the user strategies described above; for every database, the ground truth consists in the definition of a set of crisp classes (mutually exclusive here), covering the entire database. For a ground truth database a user can usually find many other classes overlapping those of the ground truth, so the evaluation of a retrieval algorithm on such a database cannot be considered exhaustive, even with respect to the content of that single database. To cover a wide range of contexts, it is very important to use several databases and to have complexity differences not only among the databases, but also among classes of each database.

Since relevance feedback algorithms must help reducing the semantic gap, the databases should not have too many "trivial" classes, i.e. for which simple lowlevel visual similarity is sufficient for correct classification. This could happen if the classes were produced for evaluating simple queries by visual example. With these criteria in mind, the first two databases employed here are:

• GT72, composed of the 52 most difficult classes-in terms of internal diversity within classes and of separability between classes-from the Columbia color database, each class containing 72 images. • GT100, having 9 classes, each composed of 100 images selected from the Corel database. The internal diversity of the classes is stronger than for GT72.

While both GT72 and GT100 are difficult for queries by visual example, every class in these databases can be relatively well modeled by a unimodal distribution. To bring in more complexity, two ground truth databases were designed where each class has several modes:

• GT9F contains 43 classes composed of 2, 3 or 4 sub-classes of 9 images each (see Fig. 1). Every sub-class consists of images selected from several sources and has a visual coherence. Some sub-classes are grouped into classes according to visual similarity, other according to a more semantic similarity. • GT30F contains 27 classes composed of 2, 3 or 4 sub-classes of 30 images each (see Fig. 2). As for GT9F, every sub-class consists of images selected from several sources (Web Museum, Corel, Vistex). However, for GT30F there is more internal diversity within each sub-class. The criteria for grouping sub-classes into classes are similar to those employed for GT9F.

The difficulty of the GT9F and GT30F databases comes both from the separation between the different modes of a class and from the presence, in-between some modes, of images belonging to other classes (see Fig. 1). The relevance feedback algorithm must not only succeed in finding, for every class, the other modes that may not be near to the mode of the first "relevant" image, but also be able to exclude "intruders" that belong to other classes; the resulting shape of a class can be rather complex.

The choice of GT9F and GT30F is not only explained by their additional complexity. In real-world retrieval, the starting point of a search session may not belong to the target class of the user, who may have to progressively "guide" the system toward this class, based on a subjective visual similarity.

But the crisp nature of the classes found in ground truth databases does not allow to emulate this "focusing" stage of a search session. The presence of several modes in the classes of GT9F and GT30F is then also an attempt to include the constraint of such real-world behavior into the ground truth-based evaluation.

The following signatures are employed for the description of the visual content of the images: a classic HSV color histogram, a Laplacian weighted color histogram [START_REF] Boujemaa | IKONA: Interactive generic and specific image retrieval[END_REF], a probability weighted color histogram [START_REF] Boujemaa | IKONA: Interactive generic and specific image retrieval[END_REF], a texture histogram [START_REF] Ferecatu | Image retrieval with active relevance feedback using both visual and keyword-based descriptors[END_REF] relying on the Fourier transform and a shape feature [START_REF] Ferecatu | Image retrieval with active relevance feedback using both visual and keyword-based descriptors[END_REF] inspired by the Hough transform. Weighted color histograms are a low-cost solution for taking into account local color uniformity. The texture histogram is based on the application of the Fourier transform to an image and describes the presence of different frequencies along various angles. To obtain the shape feature for a color image, the gray-level image is first computed, then the direction of the gradient is found for every pixel and a reference point is considered; for every pixel, the angle of the gradient and the length of the projection of the reference point along the tangent line going through the pixel position are counted in a joint histogram that is the shape feature.

The complete feature vector is the concatenation of the five types of feature vectors and its dimension is higher than 600, which could make relevance feedback impractical. Linear Principal Component Analysis is a generic unsupervised method for dimension reduction (see e.g. [START_REF] Jolliffe | Principal Component Analysis[END_REF]). For the databases and the descriptors considered here, by applying this method and keeping only 95% of the variance in the data, the dimension could be divided by 5.

Fig. 1. A sample of images from GT9F. Every line corresponds to a class ("collector", "dog" and respectively "feline") and the different images on a same line come from different sub-classes of that class. The sub-classes of "collector" are better separated than those of the "dog" class. The first sub-class of "collector" may have been added to the "dog" class as well. In the description space, one mode of the "feline" class is between two modes of the "dog" class. Fig. 2. A sample of images from GT30F. Every line corresponds to a class ("portrait" and respectively "human") and every pair of images on a same line comes from a different sub-class of that class. As compared to GT9F, there is also more diversity within each sub-class.

To allow a reliable comparison of selection criteria and of user strategies, the relevant discriminating information of the ground truth should continue to be represented in the reduced feature vector. It was checked that this strong dimension reduction did not produce a significant loss on the precision/recall diagrams built for queries by visual example.

Evaluation Method

For all the four databases, at every feedback round the emulated user must label images displayed in a window of size ws = 9. Every search session is initialized by considering one "relevant" example and ws -1 "irrelevant" examples. Every image in the database serves as the initial "relevant" example for a different relevance feedback session, while the associated initial ws -1 "irrelevant" examples are randomly selected. In the following evaluations, the focus is on ranking most of the "relevant" images before the "irrelevant" ones rather than on finding a frontier between the class of interest and the other images. Since the ground truth only provides a crisp class membership, the precise ranking of the "relevant" images is ignored.

To evaluate the speed of improvement of this ranking, the precision measure should not give a prior advantage to one selection criterion, nor to some user strategies. Concerning the selection criteria, if precision was defined by counting at every round the already labeled images plus those selected for being labeled during this round, then the MP criterion would be favored over the MAO criterion. Instead, the precision measure is computed as follows: let n be the number of images in the target class; at every feedback round, count the number of images from the target class that are found in the n images considered as most positive by the current decision function of the support vector machine; this number is then divided by n. The "mean precision" reported in all the figures presented here is obtained by averaging the precision measure defined above over all the images in the database, each serving as the initial "relevant" example for a retrieval session.

Regarding the fair comparison of the user strategies defined in Section 3, one can notice that strategies requiring the user to label more images (STO and TIR, followed by ANN, GRE and RST) are favored if the precision measure is computed in terms of iterations (or rounds). Indeed, for any given number of rounds, these strategies provide many more examples to the learner than the other strategies. Computing the precision measure in terms of clicks may then seem more equitable. Nevertheless, it can be argued-and this is specific to images-that the time a user needs for evaluating the relevance of all the images in a window is less than proportional to the number of images. Both precision measures are used here: by iterations and by clicks. Since the infor-mation regarding the precision is only available on a by iteration basis, linear interpolation provides the evolution of precision by click for the user strategies that label more than one image during each round.

Measuring precision as a function of the number of clicks is more relevant for other types of digital content such as texts, music or videos. In all these cases the evaluation of a content item is expensive: the user may have to read a section of text, listen to a fragment of music or watch a video sequence.

5 Evaluation Results

Comparison Between the Selection Criteria

Comparisons were performed between the MP and MAO selection criteria described in Section 2, on the four ground truth databases and with the eight user strategies. When the strategy of the user changes, it is noticed that:

• For the eight user strategies, the MAO selection criterion performs consistently better than the MP selection criterion. These differences are directly illustrated in Fig. 3 for the ANN strategy with an iteration-based evaluation and in Fig. 4 for the MIN strategy with a click-based evaluation. For the other strategies, the same conclusion can be drawn by comparing Fig. 5 with Fig. 6 and Fig. 7 with Fig. 8. • The differences in terms of number of clicks between MP and MAO are higher for OPT, MIN, GRE and COO than for STO, ANN and TIR. This advantage of OPT, MIN, GRE and COO can be explained by the fact that for these strategies the selector benefits from more frequent updates of the estimation of the target class by the learner.

These findings apply to all four databases of different complexities. The influence of the complexity of the classes (separability, shape and presence of several modes) can be summarized as follows:

• As expected, performance in terms of number of clicks tends to decrease as the complexity of the database increases. For instance, to achieve a precision of 90%, with the best user strategy among the eight, the number of clicks required is 12 for GT72, 80 for GT100, 250 for GT9F and 200 for GT30F. • The ranking of the user strategies is relatively stable with respect to changes in database complexity, both in terms of clicks and in terms of iterations, as shown in Tables 1 and2. • With MAO, two groups of strategies can be identified: the first consists of COO, GRE and OPT, the second of STO, ANN and RST. As shown in Tab. 2 or in Figures 7 and8, the performances within the first group are very similar for each database. This can be partly explained by the fact that small variations in the value of the decision function of the support vector machine do not allow a reliable identification of the most or the least relevant (or irrelevant) image. The disparity between the two groups increases with the complexity of the database. • Whatever the complexity of the database, the reduction in performance is not catastrophic with 10% of errors in the labels provided by the user. For click-based evaluations, Figures 7 and8 show a typical example, with the TIR strategy 40% lower than the best strategy with MP after 30 clicks and 30% lower with MAO. For iteration-based evaluations, it is most natural to compare TIR to STO since both strategies label all the images returned; as shown in Figures 5 and6, the "noise" introduced by the errors for TIR degrades performance by 10%.

The fact that the comparison between MP and MAO is so stable and consistent both with respect to strategy chosen by the user and with respect to the database leads to conclude, with a rather strong confidence, that the MAO selection criterion should be preferred over MP for relevance feedback based on support vector machines with the angular kernel.

Note that the mean precision continuously increases toward 1 when the number of clicks or iterations is incremented, even when images are grouped into classes according to higher level semantics. This is the case for the GT9F and GT30F databases, where each class has multiple (and sometimes wellseparated) modes. This result was not obvious a priori and is very encouraging with regard to the use of relevance feedback for the reduction of the semantic gap.

Complementary evaluations performed with other kernels and not reported here show that kernels that are highly sensitive to a scale parameter (such as the Gaussian kernel) perform significantly worse on GT9F and GT30F. A tentative explanation is that with such "local" kernels, distant mode easily fall out of sight. In [START_REF] Ferecatu | Retrieval of difficult image classes using SVM-based relevance feedback[END_REF] it was argued that since the spatial scales of user-defined classes cannot be known before attempting retrieval, strong variations can be expected for the performance of relevance feedback if kernels such as the Gaussian one are employed. The result regarding multi-modal classes further encourages to prefer kernels that make the learner insensitive to the scale of the data.

Comparison of User Strategies

The rank between user strategies being surprisingly stable with respect to class complexity and rather similar for the two selection criteria, some user strategies can be advised. If the number of clicks is used for evaluation, the best strategies are COO, GRE and OPT, both with MP and MAO.

Increasing the number of negative examples is counter-productive, as shown by the results obtained with RST and STO for click-based evaluations. The classes of images in real generalist databases can have a rather complex shape in the space of image signatures and sometimes several distinct modes, as for GT9F and GT30F. In such cases, relevance feedback can be seen as a process where the user "guides" the system through the description space from already discovered modes to yet undiscovered ones; too many negative examples can block the access to some parts of this space. User strategies that avoid labeling too many negative images tend to perform better in terms of speed of identification of the target class.

With either selection criteria, the GRE strategy appears to be a good tradeoff between the number of clicks and the number of iterations. This is also consistent with the above point of view that negative examples are necessary but should be employed with care.

Conclusion

Relevance feedback is an established method for finding complex, user-defined classes of images. The behavior of real users when labeling images (as "relevant" or not) cannot be expected to follow strict guidelines. An evaluation of the sensitiveness of the retrieval results to likely variations in user behavior was presented here.

Two relevance feedback algorithms based on support vector machines were compared and the user was emulated according to eight significantly different strategies on four ground truth databases of different complexities. It was first found that the ranking of the two algorithms did not depend much on the selected strategy. Second, the ranking between strategies appeared to be relatively independent of the semantic level of the ground truth classes, partly because the kernel employed leads to scale invariance in classification. This robustness to variations in the strategy of the user and in the complexity of the database is a very desirable property when designing systems that should be effective for most users.

Comparisons between relevance feedback algorithms are usually performed using only one user strategy, so it is always questionable whether conclusions extend to real users or not. The comparisons should be conducted with several different strategies-such as the ones put forward above-and the stability of the results evaluated with respect to changes in user strategy and in the complexity of the database. It was also found that user strategies that avoid labeling too many negative examples could be advised to real users because they perform systematically better the other strategies evaluated.

Finally, in the experiments presented it was noticed how important the choice of the kernel was for relevance feedback. The interaction between the choice of the kernel and user strategies deserves further investigation, in particular for kernels belonging to a larger family of kernels leading to scale invariance.

Fig. 3 .Fig. 4 .Fig. 5 .Fig. 6 .Fig. 7 .

 34567 Fig. 3. Iteration-based comparison between the MP and MAO selection criteria with the ANN user strategy on the different databases. The results on GT9F are not shown because they are very similar to those on GT30F.

Fig. 8 .

 8 Fig. 8. Click-based comparison of the 8 user strategies on the GT30F database, using the MAO selection criterion.

Table 1

 1 Ranks of the eight user strategies on the four databases, with the MP and MPO criteria. Ranks are defined by the mean precision after 10 iterations.

	Criterion		MP				MAO
	Database GT72 GT100 GT9F GT30F GT72 GT100 GT9F GT30F
	STO	1	1	1	1	1	1	1	1
	ANN	3	3	4	4	2	3	4	3
	GRE	2	2	2	3	5	5	3	4
	COO	8	8	8	8	8	8	8	8
	MIN	6	6	6	6	4	7	7	7
	OPT	7	7	7	7	6	6	6	6
	RST	5	5	5	5	3	4	5	5
	TIR	4	4	3	2	7	2	2	2

Table 2

 2 Ranks of the eight user strategies on the four databases, with the MP and MPO criteria. Ranks are defined by the mean precision after 30 clicks. The same rank was given when differences were too small to be considered reliable (these cases are marked by *).

	Criterion		MP				MAO
	Database GT72 GT100 GT9F GT30F GT72 GT100 GT9F GT30F
	STO	6	6	6*	6*	5*	5*	5*	5*
	ANN	4	4	6*	6*	5*	5*	5*	5*
	GRE	3	3	1*	1*	1*	1*	1*	1*
	COO	7	7	1*	1*	1*	1*	1*	1*
	MIN	2	2	1*	1*	4	4	4	4
	OPT	1	1	1*	1*	1*	1*	1*	1*
	RST	5	5	5	5	5*	5*	5*	5*
	TIR	8	8	8	8	8	8	8	8