Qi Zhang
email: q8zhang@cs.uwaterloo.ca

Jin Xiao
email: j2xiao@cs.uwaterloo.ca

Eren Gürses
email: egurses@cs.uwaterloo.ca

Martin Karsten
email: mkarsten@cs.uwaterloo.ca

Raouf Boutaba
email: rboutaba@cs.uwaterloo.ca

David R Cheriton

Dynamic Service Placement in Shared Service Hosting Infrastructures

Large-scale shared service hosting environments, such as content delivery networks and cloud computing, have gained much popularity in recent years. A key challenge faced by service owners in these environments is to determine the locations where service instances (e.g. virtual machine instances) should be placed such that the hosting cost is minimized while key performance requirements (e.g. response time) are assured. Furthermore, the dynamic nature of service hosting environments favors a distributed and adaptive solution to this problem. In this paper, we present an efficient algorithm for this problem. Our algorithm not only provides a worst-case approximation guarantee, but can also adapt to changes in service demand and infrastructure evolution. The effectiveness of our algorithm is evaluated though realistic simulation studies.

Introduction

With the abundance of network bandwidth and computing resources, large-scale service hosting infrastructures (e.g. content-delivery networks, service overlays and cloud computing environments) are gaining popularity in recent years. For instance, PlanetLab, as a shared academic overlay network, is capable of hosting global-scale services including content delivery [START_REF] Wang | Reliability and security in codeen content distribution network[END_REF] and file storage [START_REF] Park | Scale and performance in the coblitz large-file distribution service[END_REF]. More recently, commercial products such as Amazon Elastic Computing Cloud (EC2) [START_REF]Amazon elastic computing cloud (amazon ec2)[END_REF], Google AppEngine [START_REF]Google app engine[END_REF] and Microsoft Azure [START_REF]Azure services platform[END_REF] have emerged as attractive platforms for deploying web-based services. Compared to traditional service hosting infrastructures, a shared hosting infrastructure offers numerous benefits, including (1) eliminating redundant infrastructure components, (2) reducing the cost of service deployment, and (3) making large-scale service deployment viable. Furthermore, the ability to allocate and deallocate resource dynamically affords great flexibility, thus (4) making it possible to perform dynamic scaling of service deployment based on changing customer demands.

In general, three types of roles are present in a shared hosting environment: (1) the infrastructure provider (InP) who owns the hosting environment; (2) the service provider (SP) who rents resources from the infrastructure provider to run its service, and (3) the client who is a service customer. In this context, a service provider's objective is to (a) satisfy its performance requirements specified in Service Level Agreements (SLAs) such as response time, and (b) minimize its resource rental cost. For example, response time of requests for CNN.com should be less than 2 seconds [START_REF] Tang | On replica placement for qos-aware content distribution[END_REF]; Online game services often have stringent response time requirements [START_REF] Tobias | The effect of latency and network limitations on mmorpgs: a field study of everquest 2[END_REF]. Achieving this delay requirement (objective a) is dependent on where the servers are placed, and typically there is a monetary penalty when this requirement is not met. At the same time, achieving resource cost reduction (objective b) is also server location dependent. Thus, we argue there is a strong and consistent incentive for SPs to choose their servers' placement carefully to minimize the total operating cost. This is the case for cloud computing environment as well. Although the number of data centers used by commercial products is relatively small today, this number will grow (as demand for cloud computing grows), and new architectures such as micro [START_REF] Church | On delivering embarrassingly distributed cloud services[END_REF] and nano [START_REF] Valancius | Greening the internet with nano data centers[END_REF] data centers will emerge. A distributed solution to this problem is desirable in such a large-scale and dynamic environment, as frequent re-execution of centralized algorithms can incur significant overhead for collecting global information [START_REF] Laoutaris | Distributed placement of service facilities in large-scale networks[END_REF][START_REF] Vicari | Dynamic replica placement and traffic redirection in content delivery networks[END_REF]. Hence an adaptive and distributed service placement strategy is strongly favored.

In this paper, we present a solution to the dynamic service placement problem (SPP) that minimizes response time violations and resource rental cost at run time. We formulate SPP mathematically and present a distributed local search algorithm that achieves a theoretical worst-case performance guarantee. The effectiveness of our algorithm is experimentally verified using a set of realistic simulation studies.

The remainder of this paper is organized as follows: We present a generic model of a service hosting infrastructure in Section 2. In Section 3, we present the formulation of SPP and introduce the notations. Our distributed algorithm is presented in Section 4. In Section 5, we show that the algorithm achieves an approximation guarantee of 27. Experimental results are presented in Section 6. We discuss related research in Section 7 and conclude our work in Section 8.

System Overview

We consider a hosting platform that consists of servers that are diversely situated across geographical locations. A generic architecture of a service hosting platform is depicted in Figure 1. An instance of a service may be installed on one or many servers. To achieve locality awareness and load-balancing, a client request is redirected to a nearby server with enough CPU and bandwidth capacity to handle the request. The component which is responsible for redirecting request is the request router. In practice, a request router can be implemented using a variety of techniques, such as DNS-based request redirection, or direct routing of requests [START_REF] Pathan | A taxonomy and survey of content delivery networks[END_REF]. On the other hand, the status of individual servers, including traffic condition, CPU, memory and bandwidth usage are measured at run-time by a monitoring module on each server. It should be pointed out that it is entirely possible that monitoring modules are shared among a group of servers, and our model is fully applicable to such a scenario. The analysis modules are responsible for analyzing the current demand and predicting the future demand during the next time interval, as we shall explain below. Finally, the placement controllers are responsible for dynamically placing services. This includes copying service software (e.g. virtual machine images) to the server, dynamically starting and stopping service instances. The placement controllers are activated periodically, based on the demand prediction received from the analysis modules. In practice, the placement controllers can be implemented either centralized or distributed. For example, Microsoft Azure uses centralized controllers that are managed by service providers [START_REF]Azure services platform[END_REF]. P2P overlay networks, on the other hand, requires distributed placement controllers that are located on individual peers. In such a scenario, a placement controller can collect relevant information using protocols such as local broadcasting and gossiping [START_REF] Jelasity | Gossip-based aggregation in large dynamic networks[END_REF].

Our main objective is to dynamically adapt placement configurations to changing demands and system conditions. The demand can be modeled as function of time and location. Ideally, we want the placement configuration to be adaptive to individual demand changes. However, this is often impractical since frequent placement reconfiguration can be expensive to implement. Moreover, fine-grained demand fluctuations are usually transient and do not persist for long durations. Therefore, it is necessary to both analyze and periodically predict service fluctuations at coarse-grain levels, as illustrated in figure 2. Furthermore, even when the daily service demand follows some predictable pattern, pre-planned configuration or placement strategies at the infrastructure level are not possible because both the infrastructure and services themselves may change drastically (e.g. unexpected system failures and transient services such as VPN for a sports broadcast). The problem of predicting future service demand has been studied extensively in the past, and many solution techniques (e.g. [START_REF] Bodik | Statistical machine learning makes automatic control practical for internet datacenters[END_REF]) have been proposed. It is not our goal to examine better demand prediction methods. Rather, we study how placement configuration should be modified according to a prediction of the future service demand.

Problem Definition and Notations

We represent the hosting platform as a bipartite graph G = (D, F, E), where D is the set of clients, F is a set of candidate servers on which service instances can be installed, and E is the set of edges connecting D and F . A service instance may consume two types of resources: (1) Load-dependent resources, whose consumption is dependent on the amount of demand served by the service instance. Load-dependent resources typically include CPU, memory and bandwidth. (2) Load-independent resources, whose consumption is constant regardless of how much demand the server receives. An example of load-independent resource is storage space of the service software.

We assume every candidate server in F has enough load-independent resources to host the service, since otherwise we can remove it from F . For loaddependent resources, we assume there is a bottleneck capacity cap s on how many client a service instance s ∈ F can serve. The bottleneck capacity can be bandwidth, CPU capacity or memory, whichever is more stringent on each server. It should be noted that this bottleneck capacity may change over time. However, as we shall see our local search algorithm can naturally handle this case. In addition, We assume there is a placement cost p s for renting a service instance on a server s.

Let C s denote the set of demand assigned to s. For every demand i ∈ D, let s i represent the service instance who serves i. For every demand i ∈ C si , denote by d(i, s i ) the distance between i and s i that represents the communication latency between i and s i . Furthermore, let U si denote the number of client assigned to a server s i . Using a simple M/M/1 queuing model1 , We obtain the actual response time r(i, s i ) of a service request i as a function of U si and d(i, s i ):

r(i, s i ) = d(i, s i ) + µ si 1 -U si /cap si = d(i, s i ) + cap si • µ si cap si -U si
where µ s is the service time of a request at the server. The second term essentially models the queuing delay of the request. We construct a cost penalty cp(i, s i ) if the request response time exceeds a threshold value d max . Specifically, we define

cp(i, s i ) = a( r(i, s i ) d max ) 2
where a is a monetary penalty cost. We use a quadratic penalty function here as it reflects the general form of the penalty payout for SLA violation. Higher order polynomial is also possible and does not affect our analysis technique. Our objective is to select a set of servers S ⊆ F to deploy our service as to minimize the sum of hosting cost c f (S) and service cost c s (S): This problem is difficult to solve directly due to the load factor U s in the equation. We remedy the situation by having a preferred load value l s for U s . In this case we define SPP as follows:

c(S) = c s (S) + c f (S) = i∈D cp(i, s i ) + s∈S p s (1
Definition 1 (SPP). Given a demand set D and a server set F , each with a renting cost p s and a service cost cp(i, s i ) = a((d(i, s i ) + 2 , select a set of servers S ⊆ F to host the service and assign the demand to S such that |C s | ≤ l s for every s ∈ S, minimizing the total cost c(S) = i∈D cp(i, s i ) + s∈S p s .

µs i 1-ls i /caps i )/d max )
It is actually provable that the original problem can be reduced to this formulation (We skip the proof due to space constraints). In fact, setting a preferred load value is more practical for implementation, since typically a service provider may define an expected utilization for each service instance [START_REF] Vicari | Dynamic replica placement and traffic redirection in content delivery networks[END_REF].

We observe that SPP is similar to the Capacitated Facility Location Problem (CFLP) [START_REF] Pal | Facility location with nonuniform hard capacities[END_REF]. CFLP can be briefly described as follows: Given a graph G = (V, E) and a set of candidate sites F ⊆ V for installing service facilities (each site s ∈ F has an installation cost f s and a service capacity U s ), select a subset of sites S ⊆ F to install facilities and assign each client to a facility in S such that the sum of the connection cost c s (S) = i∈V d(i, s i ) and the installation cost c f (S) = i∈S f s is minimized. CFLP is an NP-hard optimization problem [START_REF] Zhang | Multi-exchange local search algorithm for capacitated facility location problem[END_REF], for which many centralized approximation algorithms have been proposed. In distributed settings, however, only the uncapacitated case has been studied [START_REF] Frank | Distributed facility location algorithms for flexible configuration of wireless sensor networks[END_REF][START_REF] Moscibroda | Facility location: Distributed approximation[END_REF].

It can be seen that CFLP is almost identical to SPP except the connection cost is defined as cp(i, s i ) = d(i, s i ). It is easy to show SPP is NP-hard using the same argument for CFLP. Motivated by this observation, we developed an approximation algorithm for SPP based on the local search algorithm for CFLP described in [START_REF] Pal | Facility location with nonuniform hard capacities[END_REF]. In our work, we also assume our distance metric satisfies triangular inequality. This is a practical assumption since we can always use the network coordinate services [START_REF] Dabek | Vivaldi: A decentralized network coordinate system[END_REF] to compute the distance metric. Furthermore, it is also known that Internet triangular inequality is approximately satisfied (i.e.

d(i, j) ≤ k(d(i, k) + d(k, j))),
where k is roughly 3 [START_REF] Francis | An architecture for a global internet host distance estimation service[END_REF]. It is easy to adjust our prove technique to accommodate this effect.

A Local Search Approximation Algorithm for SPP

Local search is a well known meta-heuristic for solving optimization problems. A local search algorithm starts with arbitrary solution and incrementally improves the solution using local operations until the solution can no longer be improved. Local search algorithms can naturally tolerate dynamic changes in the problem input, as they can start from arbitrary solutions. We believe a local search algorithm for SPP is favorable as it not only tolerates system dynamicity, but also provides a provable worst-case performance guarantee.

Based on the theoretical work by Pal et. al. [START_REF] Pal | Facility location with nonuniform hard capacities[END_REF], Algorithm 1 is our proposed local search algorithm for SPP. In our work, we use the term server and facility interchangeably. Two particular terminologies used in the paper are opening and closing a facility t, which means installing a service and uninstalling a service at location t. This algorithm starts from any feasible initial solution, and incrementally improves the solution with one of three types of operations: (1) add(s), which opens a facility s and assign a set of clients to s. Due to its simplicity and adaptive nature, this algorithm fits very well with our objective. However, this algorithm cannot be directly implemented in a distribute way, since finding an open(s, T ) and a close(s, T ) requires solving a knapsack problem and a single node capacitated facility location (SNCFL) [START_REF] Gortz | Analysis of some greedy algorithms for the single-sink fixed-charge transportation problem[END_REF] problem, respectively. Both problems are NP-hard in general, but can be solved in pseudo-polynomial time using dynamic programming [START_REF] Pal | Facility location with nonuniform hard capacities[END_REF]. However, this dynamic programming approach does not apply to distributed settings since it is both expensive and requires global knowledge.

Hence, it is our objective to show that both open(s, T ) and close(s, T ) can be computed locally and distributedly. In this regard, our algorithm is local in the sense that each operation is computed using neighborhood information. Specifically, Each node s in our algorithm maintains a list of neighborhood servers within a fixed radius. The list of neighbors can be obtained using neighborhood discovery protocols or a gossiping protocol [START_REF] Jelasity | Gossip-based aggregation in large dynamic networks[END_REF]. Since the servers are usually static and do not change often overtime, the list of neighboring servers will not require frequent update.

Implementing add(s)

The purpose of the add operation is to reduce the total connection cost. In an add(s) operation, if a facility s is not opened, it will become opened and start serving clients. In this case the cost reduction (CR) of the add(s) operation is:

CR(add(s)) = i∈U cp(i, s i ) -cp(i, s) -p s
where U ⊆ V is a set of clients. On the other hand, if facility s is already opened, it can invite more clients to join its cluster. In this case we set f s = 0 in the above equation. An add(s) operation can be performed when CR(add(s)) > 0.

However the straightforward implementation, i.e. Letting s contact the other facilities to find the set of potential clients, is cumbersome to implement. This

Algorithm 2 Local Algorithm for computing an admissible open(s, T ) move

1: Sort facilities in decreasing order of their cost efficiencies, cs ← 0 2: while cs ≤ caps and costEffopen(t) ≥ 0 for the next t do 3: • d max to guarantee an admissible add(s) operation will be found by a facility s.

T ← T ∪ t,

Implementing open(s, T )

In an open(s, T ) operation, a single facility s is opened and a set of facilities T become closed. All the clients of facilities in T get assigned to s. The total reduction of this operation is computed as: CR(open(s, T )) = t∈T (p t -|C t |cp(t, s)) -p s Again, notice that if s is already opened before the move, then p s is set to 0. The key challenge here is to determine the suitable set T . The problem of finding the optimal set T that maximizes CR(open(s, T )) can be formulated as a 0-1 knapsack problem: Let s be a knapsack with capacity cap s , and each open facility t be an item with size(t) = |C t | and value(t) = p t -|C t |d(s, t). The objective is to select a set of items to be packed in the knapsack to maximize the total value. Although it can be solved in pseudo-polynomial time using dynamic programming, it is not practical to implement because it requires global knowledge. Hence, we replace the dynamic programming procedure by a well-known greedy 0.5 approximation algorithm (Algorithm 2), where the cost efficiency of each facility t is defined as value(t) size(t) , which is costEff open (t) = pt |Ct| -cp(s, t). To implement Algorithm 2 distributedly, notice that for any facility t, if cp(s, t) ≥ pt |Ct| , then costEff(t) becomes negative and can be safely ignored in the calculation. Hence each facility t only need to contact neighborhood facilities in radius

Implementing close(s, T )

The objective of the close(s, T ) is to close a facility s, open a set of facilities T , and assign all of the clients of s to facilities in T . Again, the main difficulty is to find a suitable set T . The cost reduction of close(s, T ) can be computed as:

CR(close(s, T )) = p s - t∈T (p t + u t cp(s, t))
Where u t represents the amount of demand assigned to t after closing s. Similar to open(s, T ), if a facility t ∈ T is already opened, then p t is set to 0 in the above equation. Computing the optimal T can be formulated as a single-demand capacitated facility location problem (SNCFL) [START_REF] Gortz | Analysis of some greedy algorithms for the single-sink fixed-charge transportation problem[END_REF]. In this problem, we wish to select a set of facilities T with total capacity at least |C s |, assigning clients of s to facilities in T to minimize

cost SN CF L = t∈T (p t + u t cp(s, t))
This problem is also NP-hard. However, a greedy algorithm is known for this problem [START_REF] Gortz | Analysis of some greedy algorithms for the single-sink fixed-charge transportation problem[END_REF]. In this algorithm, the facilities are sorted by their cost efficiencies, which in our case, is defined as costEff close (t) = pt capt + cp(s, t) This algorithm (Algorithm 3) can be described as follows: the output set T is initially empty. we first sort facilities in increasing order of their cost efficiencies, and then try to add facilities T according to the sorting order. In each step, if adding next facility into T will cause t∈T cap t ≥ |C s | (i.e. facilities in T have enough capacity to handle demands of s), then T is a candidate solution. Now, if CR(close(s, T )) ≥ 0, this is an admissible operation and the algorithm stops. Otherwise, we do not add this facility to T . This process repeats until every facilities in U has been examined. The following lemma is a known result for this algorithm: Lemma 1. [START_REF] Gortz | Analysis of some greedy algorithms for the single-sink fixed-charge transportation problem[END_REF] The greedy algorithm outputs a solution S with cost SN CF L ≤ t∈T (2p t + u t cp(s, t)) for any T ⊆ F .

Clearly, a facility in T can not be outside a radius ps a • d max , as in this case the reassignment cost will exceed p s . Hence close(s, T ) operation can be computed locally by s within in this radius.

Algorithm Analysis

In this section, we show that our algorithm achieves an approximation factor 27. There are two challenges to this problem. First, our distance function is nonlinear, as opposed to the linear function used in CFLP. Second, since we have replaced the dynamic programming procedures with greedy algorithms, we need to show our algorithm can still provide a performance guarantee. while not every node in U has been examined do 6:

t ← next facility in the sorted list 7:

if remcapt ≥ 0 then 8:

T ← T ∪ t, currentCR ← t∈T (pt + captd(s, t)), rem ← remcapt 9: else 10:

if CR(close(s, T ∪ t)) ≥ 0 then 11:

return T ∪ t 12: until U == {∅ } 13: output there is no admissible close operation Proof. Since Algorithm 2 is a 1 2 -approximation of the knapsack problem, it is true for any

T ′ ⊆ F \{s}, SOL ALG2 ≥ 1 2 ( t∈T ′ p t -|C t |d(s, t)).
Since it fails to find a admissible operation, SOL ALG2 -p s ≤ 0 must hold. The claim follows.

Lemma 3. If a close operation close(s, T ) computed using Algorithm 3 is not feasible, then t∈T ′ (2p t + u t cp(s, t)) -p s ≥ 0 for any set of T ′ ⊆ F \{s}.

Proof. Since Algorithm 3 is a 2-approximation algorithm for the SN CF L, we must have, for any set T ′ ⊆ F \{s}, SOL ALG3 ≤ t∈T ′ (2p t + u t cp(s, t)). Since it fails to find an admissible move, we must have p s -SOL ALG3 ≤ 0. The lemma follows.

Using the above lemmas, we can prove our main result: Theorem 1. The distributed algorithm achieves an approximation factor 27.

Proof. See appendix.

Experiments

We have implemented our distributed algorithm in a discrete event simulator and conducted several simulation studies.

We construct topology graphs using the GTITM generator [START_REF]Gtitm homepage[END_REF], which can generate transit-stub topologies that simulate latencies between hosts on the Internet. We specify the average communication latency at intra-transit, stubtransit and intra-stub domain links to be 20ms, 5ms and 2ms respectively [START_REF] Ratnasamy | Topologically-aware overlay construction and server selection[END_REF]. We randomly pick a subset (10%) of nodes as candidate locations for placing servers. Each candidate location can host up to 5 instances. In our experiments, we set d max = 400ms, µ s =20ms, a = 1 and p s = 4 for 200 node graph, 8 for 400 node graph and so on. For benchmarking purpose, we have implemented a centralized greedy placement algorithm [START_REF] Qiu | On the placement of web server replicas[END_REF], which has been shown to perform well in practice.

In our first experiment, we evaluate the performance of distributed algorithm in static topologies where there is no demand fluctuation. To estimate the value of optimal solution, we implemented a simple routine that outputs a lower-bound on the optimal solution by ignoring capacity constraints. Our experimental results are shown in Figure 3(a). We observe that although both algorithms perform well compared to the lower-bound values, our algorithm performs better than the greedy algorithm in all cases. This result indicates that, the solution produced by our algorithm is near optimal.

In our next experiment, we evaluate the effectiveness of our algorithm under dynamic conditions, i.e. demand of clients fluctuate overtime and servers may fail randomly. To make experiment realistic, we used a real internet topology graph from the Rocketfuel project [START_REF] Spring | Measuring isp topologies with rocketfuel[END_REF]. Figure 3(b) shows the cost of the solution at runtime. For comparison purpose, at each time stamp we also show the solution of the greedy heuristic that has access to global topology information. As shown on Figure 3(b), our distributed algorithm is quite adaptive to the dynamic conditions, and in some cases, performs better than the greedy heuristic. Figure 3(c) depicts the change in the number of instances in response to the changes in client population. We observe that the number of instances used, as suggested by our algorithm, follows the service demand very closely. Figure 3(d) illustrates the average distance between clients and their servers at runtime and it is comparable to the centralized greedy solution. These results suggests our algorithm will perform well in practical settings.

Related Work

Placing services in large-scale shared service hosting infrastructures has been studied both theoretically and experimentally. Oppenheimer et. al. [START_REF] Openheimer | Service placement in a shared wide-area platform[END_REF] studied the problem of placing applications on PlanetLab. They discovered that CPU and network usage can be heterogenous and time-varying among the Planet-Lab nodes. Furthermore, a placement decision can become sub-optimal within 30 minutes. They suggested that dynamic service migration can potentially improve the system performance. They also studied a simple load-sensitive service placement strategy and showed it significantly outperforms a random placement strategy. NetFinder [START_REF] Zhu | Overlay network assignment in planetlab with netfinder[END_REF] is a service discovery system for PlanetLab that employs a greedy heuristic for service selection, based on CPU and bandwidth usage.

Theoretically, Laoutaris et. al. formulated SPP as a uncapacitated facility location problem (UFLP) [START_REF] Laoutaris | Distributed placement of service facilities in large-scale networks[END_REF], and presented a local search heuristic for improving the quality of service placement solutions. There are several differences between their work and ours. First, server capacity, such as CPU and bandwidth capacity, are considered in our formulation but not in theirs. Second, their heuristic does not provide a worst-case performance guarantee.

Our problem is also related to the replica placement problem, which has been studied extensively in the literature, primarily in the context of content delivery networks. Most of the early work on this problem focus on centralized cases where the network topology is static [START_REF] Tang | On replica placement for qos-aware content distribution[END_REF][START_REF] Qiu | On the placement of web server replicas[END_REF][START_REF] Szymaniak | Latency-driven replica placement[END_REF][START_REF] Karlsson | Choosing replica placement heuristics for wide-area systems[END_REF]. More recent work has also studied dynamic cases [START_REF] Vicari | Dynamic replica placement and traffic redirection in content delivery networks[END_REF][START_REF] Presti | Dynamic replica placement and user request redirection in content delivery networks[END_REF], in which iterative improvement algorithms are proposed. However, none of the above work was able to provide a theoretical worst-case performance guarantee. Our algorithm is as efficient as the above algorithms, and achieves theoretical performance ratio at the same time. A potential research direction is on improving this theoretical performance guarantee.

Another problem related to SPP is the web application placement in data centers. The objective is to achieve load balancing so as to reduce total response time. Several heuristics have been proposed for the problem [START_REF] Carrera | Utility-based placement of dynamic web application with fairness goals[END_REF][START_REF] Tang | A scalable application placement controller for enterprise data centers[END_REF], using local algorithms. The main difference between their work and ours is that we consider the distance (which could be latency or hop count) between clients and the servers in our formulation. This is not a concern in their work, since they assume all the servers are located in a single data center.

Conclusion

Large-scale shared service hosting infrastructures have emerged as popular platforms for deploying large-scale distributed services. One of the key problems in managing such a service hosting platform is the placement of service instances as to minimize operating costs, especially in the presence of changing network and system conditions. In this paper, we have presented a distributed algorithm for solving this problem. Our algorithm not only provides a constant approximation guarantee, but is also simple to implement. Furthermore, it can automatically adapt to dynamic network and system conditions.

As part of our future work, we would like to extend our work to handle more complex scenarios such as services with interdependencies. We would also like to improve our approximation guarantee. Furthermore, we are also interested in developing a control-theoretic framework for SPP. Most importantly, we would like to conduct a realistic experimentation on a real service hosting infrastructures such as PlanetLab.

A Proof of Theorem 1

Let S * denote the facility set in the optimal solution. We proof our algorithm achieves an approximation ratio of 27. Proof. Similar to lemma 4.1 in [START_REF] Pal | Facility location with nonuniform hard capacities[END_REF], except we use the fact the triangular inequality is 3-satisfied. Now we bound the facility opening cost c f (S). Similar to [START_REF] Pal | Facility location with nonuniform hard capacities[END_REF], we select a set of operations (add, open and close) to convert S to S * . The key difference between our approach and theirs is that we use greedy algorithms to approximate the optimal open and close operations. Recall that from lemma 2 and 3, 2p s + t∈T ′ (u t cp(s, t) -p t ) ≥ 0 for all feasible open(s, T ) operations, and p s ≤ t∈T (p t + u t cp(s, t)) for all close(s, T ) operations. We say an open operation opens s twice, but close each facility in T once. Similarly, an close(s, T ) operation close s once and opens each facility in T twice. Hence, using the same set of operations, we can show the following result: Lemma 6. With our greedy algorithm 2 and 3, the same set of operations in [START_REF] Pal | Facility location with nonuniform hard capacities[END_REF] opens p t at most 14 times for each t ∈ S * , and closes p s exactly once for each s ∈ S\S * .

Proof. Follow the same analysis as in Lemma 5.1 of [START_REF] Pal | Facility location with nonuniform hard capacities[END_REF], except we use lemma 2 and 3 to bound the cost of open and close operations. Lemma 7. The total reassignment cost of all selected operations is at most 2 • 3(c s (S * ) + c s (S)).

Fig. 1 .

 1 Fig. 1. System Architecture Fig. 2. Dynamic Demand Prediction

) Algorithm 1

 1 Local Search Algorithm for SPP 1: while ∃ an add(s), open(s, T ) or close(s, T ) that reduces total cost do 2: execute this operation

( 2 )

 2 open(s, T ), which opens a facility s, close a set of facilities T , and assign the clients of facilities in T to s. (3) close(s, T ), which closes a facility s, open a set of facilities T and assign the client of s to facilities in T . In all three operations, a facility can be opened multiple times but closed only once.

  pt a•|Ct| • d max . A neighboring facility s can then compute an admissible open(s, T ) once it discovers the entire T .

Lemma 2 .Algorithm 3

 23 If an open operation open(s, T ) computed using Algorithm 2 is not admissible, then 2p s + t∈T ′ (u t cp(s, t) -p t ) ≥ 0 for any set of T ′ ⊆ F \{s}. Local Algorithm for computing an admissible close(s, T ) move 1: rem ← |Cs|, T ← ∅, currentCR ← 0, U ← facilities within radius ps a • dmax, 2: sort U in increasing order of their cost efficiencies 3

Fig. 3 .

 3 Fig. 3. Experimental result

Lemma 4 .

 4 cp(s, o) ≤ 3(cp(i, s) + cp(i, o)) for any client i and two facilities s,o. Proof. By definition, cp(s, o) = a((d(s, o) + µo 1-lo/capo )/d max ) 2 . Using d(s, o) ≤ d(i, s) + d(i, o) to expand this equation, and applying the fact a 2 + b 2 ≥ 2ab for any a, b ∈ R, the lemma is proven. Lemma 4 essentially states that the triangular inequality is 3-satisfied in SPP. Lemma 5. c s (S) ≤ c f (S * ) + 3c s (S * ) of a local solution S.

  cs ← cs + |Ct| 4: return either T or the next facility t / ∈ T in the list, whichever is larger is because s does not know a-priori which facility has clients with high connection cost. Instead, in our implementation, we allow neighborhood facilities to exchange client information and record potential clients. Once s have recorded enough potential clients, s can become open (if not already opened), and start serving these clients. Observe that a client i must satisfy cp(i, s) ≤ cp(i, s i ) in order for the reassignment to be beneficial, hence d(s, s

i ) ≤ d(i, s i ) + d(i, s) ≤ d(i, s i ) + cp(i,s) a • d max ≤ d(i, s i ) + cp(i,si) a • d max .

Therefore s i only needs to exchange client information with servers within radius d(i, s i ) + cp(i,si) a

More sophisticated model can be easily incorporated by changing the equations for r(i, si) and cp(i, si).

Proof. This proof is identical to Lemma 5.2 in [START_REF] Pal | Facility location with nonuniform hard capacities[END_REF], except we use the fact the triangular inequality is 3-satisfied.

Finally, we bound our approximation factor: Proof (Of Theorem 1). Based on Lemma 6 and 7, the sum of all the inequalities is at most 14c

Adding c s (S) + c f (S ∩ S * ) to both sides and using c s (S) ≤ 3c s (S * ) + c f (S * ) proved by lemma 5, we obtain c(S) ≤ 23c f (S * ) + 27c s (S * ).


Julien Moras

Véronique Cherfaoui

Philippe Bonnifait

Evidential Grids Information Management in Dynamic Environments

An occupancy grid map is a common world representation for mobile robotics navigation. Usually, the information stored in every cell is the probability on the occupancy state. In this paper, an evidential approach based on Dempster-Shafer theory is proposed to process the information in accordance with the least commitment principle. The map grid is updated by a fusion mechanism by using an inverse model of the sensor. We show that the evidential framework offers powerful tools to make a good management of uncertainties especially when the sensory data are poor in terms of information. After having presented the key concepts of evidential grids with respect to probabilistic ones, entropy and specificity metrics are introduced to qualify the degree of information stored in the cells. Some comparisons with the probabilistic approach are given on fusion and decision results using simulation. We also report experimental results to illustrate the performance of a real-time implementation of the method with a 4-layer lidar mounted in the bumper of a car driving in real urban traffic conditions.

I. INTRODUCTION

Occupancy Grids (OG) are often used as the backbone of mobile perception systems for intelligent vehicles navigation like for data fusion [START_REF] Stepan | Robust data fusion with occupancy grid[END_REF], localization [START_REF] Zhao | SLAM in a dynamic large outdoor environment using a laser scanner[END_REF] and obstacle avoidance [START_REF] Cherubini | Visual navigation with obstacle avoidance[END_REF]. As OGs manage a representation of the environment that does not make any assumption on the geometrical shape of the detected elements, they provide a general framework to deal with complex perception conditions. Many works have contributed to improve this framework at different levels : geometric (from 2D to 2.5D [START_REF] Himmelsbach | LIDAR-based 3D Object Perception[END_REF] and 3D [START_REF] Wurm | {OctoMap}: A Probabilistic, Flexible, and Compact {3D} Map Representation for Robotic Systems[END_REF]), uncertainty management [START_REF] Oriolo | Fuzzy maps: A new tool for mobile robot perception and planning[END_REF], dynamic conditions [START_REF] Mitsou | Temporal Occupancy Grid for mobile robot dynamic environment mapping[END_REF] and clustering and tracking [START_REF] Kamel Mekhnacha | The Fast Clustering-Tracking Algorithm in the Bayesian Occupancy Filter Framewok[END_REF].

In this paper, we focus on the use of a multi-echo and multi-layer lidar system in order to characterize the dynamic surrounding environment of a vehicle driving in common traffic conditions. The perception strategy involves map and scan grids [START_REF] Moras | Credibilist occupancy grids for vehicle perception in dynamic environments[END_REF], [START_REF] Moras | Moving Objects Detection by Conflict Analysis in Evidential Grids[END_REF]. Indeed, an instantaneous scan grid built from the lidar doesn't provide enough reliable information because of noise and miss-detections. The map grid acts as a filter that accumulate information and allows to detect moving objects.

In dynamic environments, it is crucial to have a good modeling of the information flow in the data fusion process in order to avoid adding wrong implicit prior knowledge that will need time to be forgotten. In this context, Evidential OG are particularly interesting to make a good management of the information since it is possible to explicitly make the distinction between non explored and moving cells. In this paper, we conduct a study with the classical probabilistic approach to highlight the added values.

This paper is organized as follows. The concept of occupancy grids with inverse sensor models is explained in section II. Then, evidential occupancy grids are presented in section III. Section IV compares the probabilistic framework with the evidential one. Finally, conclusion and outline perspectives are given in section V.

II. ROBOTIC PERCEPTION WITH OCCUPANCY GRIDS

A. Occupancy Grid in Dynamic Environments

The basic idea of an OG is to divide the surrounding environment (the ground plane of 2D world) into a set a cells (denoted C i , i ∈ [0, n]) in order to estimate their occupancy state. In a probabilistic framework, the aim is to estimate the probabilities P O i |z 1:t and P F i |z 1:t given a set of measures z 1:t from the beginning up to the current time t. O i (resp. F i ) denotes the occupied (resp. free) state of the cell C i . Finally, a decision rule is applied (e.g. Maximum A Posterior -MAP) in order to select the most likely state for each cell.

Occupancy grids can be classified into two categories depending on the use of a forward or inverse sensor model. The forward model [START_REF] Elfes | Using occupancy grids for mobile robot perception and navigation[END_REF] relies on Bayes inference. Since this approach takes into account the conditional dependency of the cells of the map, it is well adapted to a sensor that observes a large domain of cells with only one reading measurement (e.g. a ultrasonic sonar). However, it requires heavy processing that can be handled by optimized approximation [START_REF] Thrun | Learning occupancy grid maps with forward sensor models[END_REF] or GPU computing [START_REF] Tay | The Bayesian occupation filter[END_REF].

The inverse model approach is well adapted to narrow fields of measures sensors (e.g. lidar). It is composed of two separate steps. First, a snapshot map of the sensor reading is built using an inverse sensor model P O i |z t . This model can take into account the conditional dependency between the sensor reading and the occupancy of the seen cells. Then, a fusion process (denoted ⊙) is done with the previous map P O i |z 1:t-1 as an independent opinion poll fusion:

P O i |z 1:t = P O i |z t ⊙ P O i |z 1:t-1 (1)
In a probabilistic framework, the usual fusion operation between states A and B is:

Inverse approaches have very efficient implementations (e.g. log-odd) that make them very popular in mobile robotics [START_REF] Thrun | Probabilistic Robotics[END_REF], [START_REF] Weiss | Robust Driving Path Detection in Urban and Highway Scenarios Using a Laser Scanner and Online Occupancy Grids[END_REF]. Maps built using inverse models are usually less accurate, since they just take into account the dependency of the cells observed in one reading, but it is a good approximation with accurate and high resolution sensors observing a limited number of cells at a time. Moreover, when the sensor is multiecho and multi-layer, the conditional dependency of the seen cells can be modeled in an efficient way.

B. Fusion strategy with the inverse model

When dealing with the inverse model approach, an estimate of the pose of the robot has to be available and map grid G M has to be handled. This grid is defined in a worldreferenced frame (so it does not move with the robot) and is updated when a new sensor reading is available. Because of the likely evolution of the world in a dynamic environment, the OG update has to be completed by a remanence strategy. The fusion architecture follows then a prediction-correction paradigm and can be used to fuse one or several sensors.

a) Prediction step: The prediction step computes the predicted map grid at time t from the map grid estimated at time t -1. Depending on the available information, this step can be very refined like done in [START_REF] Tay | The Bayesian occupation filter[END_REF]. As we consider here that no specific information on the velocity of the objects (or cells) is available, the prediction is done by discounting. The confidence in aged data is controlled by a remanence factor α ∈ [0; 1]. The prediction stage is therefore:

ĜM t = discount ĜM t-1 , α b) Correction step:
The correction step consists in the combination of the previously estimated map grid with the grid built from the current measures thanks to the inverse model sensor. This one is called ScanGrid G S t . As this information is referenced in the sensor frame, a 2D warping is applied to reshape this grid into the fusion frame. To perform this operation, the current pose q t is estimated using a GPS sensor and the rigid homogeneous transformation matrix H t is computed. When GPS becomes unavailable, the CAN bus is used to get the car odometric data. The motion matrix H t and the extrinsic calibration matrix C are used to compute a remapping function f (Eq. 3).

f (x, y) = C • H t •   x y 1   (3)
Finally, the ScanGrid is remapped with f and fused with the previous map grid.

ĜM

t (i, j) = ĜM t (i, j) ⊙ G S t (f (i, j)) (4)
The evidential OGs that are described in the next sections follow this paradigm.

III. EVIDENTIAL OCCUPANCY GRIDS

A. Belief functions basic concepts

The Transferable Belief Model introduced by Smets in [START_REF] Smets | The transferable belief model[END_REF] is a formalization of Dempster-Shafer Theory [START_REF] Dempster | Upper and Lower Probabilities Induced by a Multivalued Mapping[END_REF], [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF]. Let X be a variable that takes value in a discrete frame of discernment (FOD) Ω. Let us define a mass function m. This function is a multi-valued mapping m : 2 Ω -→ [0 1], where 2 Ω is called the powerset of Ω. m verifies A∈2 Ω m(A) = 1. For each element A of 2 Ω , m (A) refers to the part of belief that supports the hypothesis X ∈ A and nothing more. An initial mass function m S called basic belief assignment (bba) can be created from a piece of evidence on X provided by a source S which can be either a sensor measurement or an information model.

In the general case, bba verifies m S (∅) = 0 (i.e. there no conflicting information) and the Least Commitment (LC) Principle [START_REF] Smets | Belief functions: The disjunctive rule of combination and the generalized Bayesian theorem[END_REF]. The basic idea of the LC principle is to never give more support to elements of the belief domain than justified. It permits to select the least informative belief function in a set of equally justified belief functions. For instance, the specialized bba used [START_REF] El Najjar | A Road-Matching Method for Precise Vehicle Localization Using Belief Theory and Kalman Filtering[END_REF] respects this principle. In the following of this paper, we suppose that every bba respects this principle.

Fusion

Like probabilities, mass functions can be combined with fusion operators. Let be two sources that give mass functions m 1 and m 2 on the same FOD. In case of two sources with independent errors and if both sources are fully reliable then the fusion is performed by the Dempster rule ⊕ defined in Eq.5:

m 1 ⊕ m 2 (A) =    m 1 ∩ 2 (A) 1-m 1 ∩ 2 (∅) A = ∅ 0 A = ∅ ( 5
)
where ∩ is the conjunctive rule:

∀A ∈ 2 Ω , m 1 ∩ 2 (A) = B, C∈2 Ω |A=B∩C m 1 (B)•m 2 (C) (6)

Belief and plausibility representation

Information can be represented by belief bel () or plausibility functions pl () instead of mass functions.

∀A ∈ 2 Ω , bel (A) = B|B⊆A m (B) (7) ∀A ∈ 2 Ω , pl (A) = B|B∩A =∅ m (B) (8)
Within the transferable belief model, the degree of belief bel(A) given to a subset A quantifies the amount of justified specific support to be given to A, and the degree of plausibility pl(A) quantifies the maximum amount of potential specific support that could be given to A.

Discounting

A discounting effect can be applied on a mass function m if a piece of information has its reliability lowered. In this case, a new mass function m α is computed from m and a part of the mass of each element of the FOD is transferred to the unknown Ω.

m α (A) = α • m (A) if A = Ω α • m (A) + (1 -α) if A = Ω

Back to probability

Finally, the pignistic transformation BetP [START_REF] Smets | Decision making in the TBM: the necessity of the pignistic transformation[END_REF] allows to compute a probability measure from a mass function by distributing proportionally the mass of the subsets on their focal elements:

∀A ∈ Ω, BetP (A) = B∈2 Ω m (B) • |A ∩ B| |B| (9)
where card (A) is the cardinal of subset A.

Hoverer, this transformation is not bijective (a part of the information is lost). So, one can find an infinity of mass functions with the same pignistic probability. This issue is inherent in the nature of probabilities which are not able to distinguish ignorance from inconsistency.

B. Evidential occupancy grids

As described in [START_REF] Ribo | A comparison of three uncertainty calculi for building sonar-based occupancy grids[END_REF] and [START_REF] Pagac | An evidential approach to probabilistic map-building[END_REF], evidential grids handle occupancy information and uncertainty with Belief functions. In this problem, the FOD is Ω = {F, O} and for each cell C i , one can define a mass function m i that represents its occupancy. In this particular case, m is a vector composed of 4 masses: [m (∅) m (F ) m (O) m (Ω)] where m (Ω) represents the part of ignorance and m (∅) represents the conflict.

Example 1. A source says that a cell is free with a confidence level of 70%. The LC bba is :

m (∅) m (F ) m (O) m (Ω) 0 0.7 0 0.3
70% supports the state F whereas the 30% remaining does not support any specific state and so Ω = {F, O}.

This representation is the main advantage of the evidential concept. It is demonstrated in section IV.

IV. PROBABILISTIC AND EVIDENTIAL GRIDS COMPARISON

A. Effect of representation on the fusion result

The first advantage of the evidential representation is to be able to distinguish:

• a non-informative value; when a cell is not observed (masked cells, out of sensor coverage cells,etc..), the mass assignment is m (Ω) = 1 from • an ambiguous value; when the state of the cell results from contradictory beliefs, the mass is split on m (O) and m (F ).

Let us illustrate this with examples. Let consider the fusion of two pieces of information coming from two different sources 1 and 2 and let consider two cases. The mass function m 1 is the same in the two cases but the mass function m 2 changes. In the first case, source n°2 represents an unspecific information (non-informative) and in the second case, it represents a state of conflict (ambiguous). The pignistic transform is used to compute equivalent probabilities P 1 and P 2 . One can notice that, in both cases, information is represented by the same probabilities. Tab I shows the results of the fusion. The result of the fusion can be the same (case 1) but can slightly differ (case 2) when there are ambiguous sources.

Assignment Fusion m1 m2 P1 P2 m1⊕2 BetP1⊕2 P1⊙2 ∅ 0 0 × × 0 × × F 0.

B. Information metrics

In probability, Shannon's entropy is a measure of uncertainty due to ignorance or to conflict. It is defined for a discrete random variable A, such as:

H P = - A∈Ω P (A) • ln (P (A)) (10)
In the Belief framework, Yager introduced in [START_REF] Yager | Entropy and Specificity in a Mathematical Theory of Evidence[END_REF] two uncertainty measures of mass functions that generalize Shannon's entropy: entropy and specificity. Entropy of a mass function is defined as follows:

E m = - A⊆Ω m (A) • ln (pl (A)) (11)
Yager's entropy characterizes inconsistency in the assumptions supported by mass function.

For instance, let consider the FOD Ω = {F, O}. In the case of a simple mass function (i.e. the mass is distributed on a single focal element F or O and on Ω), entropy equals zero E m = 0.

When there is no ignorance, Yager's and Shannon's entropies are the same.

The specificity of a mass function (which has no equivalent in probability) is defined as:

S m = A ⊆ Ω A = ∅ m (A) |A| . (12)
With Ω = {F, O}, one can demonstrate that specificity belongs to the interval 1 2 ; 1 .

1 2 ≤ S m ≤ 1 ( 13
)
High specificity is used to characterize the fact that the masses are mainly attributed to small subsets. This usually indicates that the mass function is not doubtful even if it can be conflictual. Thereby, a mass function that is informative and unambiguous has got a high specificity and a low entropy. Therefore, entropy and specificity are measures used to characterize the uncertainty of mass functions. More details on these metrics can be found in [START_REF] Smarandache | Contradiction measures and specificity degrees of basic belief assignments[END_REF]. An evidential occupancy grid being a spacial set of mass functions, these measures represent therefore perception uncertainty.

C. Decision

Finally, let consider the capability of both approaches to make decisions. Probabilistic approaches generally use a MAP decision rule like P (O) > 0.5. In the evidential framework, one can transform the mass function to probabilities with the pignistic transform and then use a MAP estimator. Nevertheless, as the credal level (mass function space) provides more information, this framework can potentially make better decisions. The belief bel and plausibility pl (acting as lower and upper bounds of probability) allow to compute more specific decision rules.

In order to detect the occupied and free space, one can use bel (O) > 0.5 or bel (F ) > 0.5. This ensures to chose the most likely level without considering the part of unknown. Then, an important part of the mass on the unknown Ω will be rejected and a sound decision can be computed for this cell.

V. EXPERIMENTS

In the coming sections, we do a comparison between the probabilistic and the evidential frameworks to show the benefits of these concepts.

A. Simulation example

Let focus on a particular cell of the grid. In order to carry out an appropriate comparison, the probabilistic fusion follows the same scheme as the evidential one. Sensor bbas are first converted into probabilities using the pignistic transformation.

To compare probabilistic and evidential uncertainty measures, let consider two simulations which are presented on Fig. 1 and Fig. 2. Let us suppose that the state of the cell of the grid changes because of the dynamic of the scene (an object appears and then moves to another cell). In each scenario, the top plot of the figure shows the sensor detection bba. The middle plot displays the result of the Bayesian fusion with the resulting Shannon's entropy H. The bottom plot shows the evidential result with the corresponding entropy E and specificity S. Recall that specificity doesn't exist in probability.

The sensor confidence parameters are set to m (F ) = 0.85 m (Ω) = 0.15 when the cell is free and m (O) = 0.7 m (Ω) = 0.3 when occupied. They respect the principle of minimal commitment. Physically, it means that when the cell is free, 85% of the time the cell is well classified and 15% of the time the sensor is not able to say anything. The discounting factor α was set to 0.05. The corresponding time constant τ can be computed using the relation α = 1e ∆t τ where ∆t = 1 F req is the sampling period. For a lidar sensor with F req = 15Hz, we assume a remanence of τ = 1.3s for α = 0.05.

In the first simulation (Fig. 1), two changes occur in the cell: free to occupied at time index 10 and occupied to free at time index 30. It corresponds to a scenario where an obstacle crosses this cell. Mass functions are initialized to ignorance m (Ω) = 1 and probabilities equally distributed to 0.5 as is usually done. Shannon's entropy H follows similar evolutions at time indexes 0, 12 and 33. So, it doesn't allow to distinguish initial ignorance (time 0) from state change (time 12 and 33). This is perfectly in agreement with the fact that probabilities make no difference between ignorance and conflict.

In the case of belief functions, entropy E raises just when state changes. Specificity S starts from 0.5 due to the initial ignorance and then stays close to 1 since the sensor always provides information. Thanks to this specific behavior, one can notice that the belief masses are informative for t > 2.

During intervals [11; 17] and [31; 35], masses are ambiguous. This refined analysis is not possible using probabilities.

In the second simulation (Fig. 2), the cell is free at the beginning but it is not observed during a lapse of time (20 < t < 45s) because of an outage for instance and, when it is observed again, its state has changed. After the transient phase, Shannon's entropy H increases slowly during the outage as the information on the cell is discounted. Nevertheless, when the cell is observed again (t>45), nothing indicates the change of the state. In the case of belief masses, the specificity S slowly decreases indicating that the loss of sensor information. Entropy E stays null up to index 45 because their is no measurement that indicates a change of state. When a measurement is again available (t>45), the specificity reaches 1 again which indicates that the belief masses are again informative. The entropy peak (t=45) is due to the change of state. Its amplitude remains small because of the ignorance level.

B. Real-time example with real data

The proposed system has been implemented in real-time and embedded in an experimental vehicle. In this implementation, we only make the fusion of the data provided by a IBEO Alasca XT lidar scanner installed in the front bumper. In this case, the amount of data is relatively sparse compared to the scene complexity. An inertial positioning system with hybridized GPS (Novatel Span CPT) provided the pose of the vehicle with a high sampling rate.

Figure 3 shows some results in an urban environment (Paris) under real traffic conditions. The top left figure presents an image of the scene acquired by a camera embedded in the vehicle used only for visualization. And top right one shows a 3D view of the current lidar scan, the vehicle is represented by the 3 axis on the bottom of the figure. The bottom images present a set of grids that represent different values (probabilities, mass functions, metrics, etc...). The size of the grid is 10 m width and 40 m length with a cell resolution of 0.1 m. The car is at the bottom of the grid looking upwards. The 4-layers lidar is working at 15 Hz. The sensor model used in this experiment is described in [START_REF] Moras | Moving Objects Detection by Conflict Analysis in Evidential Grids[END_REF]. The discounting rate α was set to 0.05 corresponding to a time constant of 1.3 s as stated before. Sensor reliability was set to 0.8 for occupied and free detection. These are the only parameters needed by the perception method.

On figure 3c the grids represent respectively (from the left to the right) : Evidential entropy E m , evidential specificity Sm , mass evidential function m, occupancy probability P (O) and the probabilistic entropy H. All theses value are normalized to the interval [0, 1] to be represented as a gray scale image (0:black, 1:white). For the specificity, the value presented is the complementary Sm = 1-S m in order to make the comparison with the entropy easier. The mass function is represented by a color grid, each color represents a specific mass (green : free, red occupied, empty-set : blue and black unknown).

Here, the ego-vehicle is waiting at traffic lights and a car coming from the left turns to the left. The environment is composed of a lot of elements and the coverage of the sensor is small because of masking.

First, the mass function m and the probabilistic grids P (O) present quite similar results. Nevertheless, the evidential grid is able to distinguish clearly the masked cells (black) of the cells that make conflict (blue) whereas, in the second, this is represented by the same gray level. The grids of metrics illustrate these phenomena. One can remark that the probabilistic entropy H and the complementary specificity S are very similar. This shows that, in this case, for most of the cells that have a high entropy, this is caused by ignorance. These cells haven't captured information from the previous reading (because non observed) and so they can be fused with any specific information directly in both frameworks. Nevertheless, differences are apparent on these grids in areas where the car is turning. These differences are highlighted by evidential entropy E. It presents a low value everywhere except on the car and on the borders. This entropy shows a competition between the two states O and F . Contrary to a non information, this means that the sensor provides reading about this cell but the fusion brings conflict because of model errors. Here, the static world assumption and the discretization of the world induce this entropy. The entropy level can be used to detect any inconsistency between the model and the data. So, a mean level of the entropy of the grid can be an indicator of the proper functioning.

C. Decision

Figure 4 shows the result of the decision bel (F ) > 0.5, bel (O) > 0.5 and P (O > 0.5) on the same snapshot previously presented. We can remark that the two evidential decisions are not complementary, because there are cells that cannot be decided as free or occupied ones. If we observe the probabilistic and evidential grids, we can see that the bel (O) is similar but finer than the probabilistic one. This is because cells near the borders support both O and Ω that are not distinguishable by probabilities. The fact that belief functions are able to represent explicitly ignorance and conflict improves the behavior of the data fusion process particularly when the knowledge of the state of the cells is poor because of the high dynamic of the perception scene and the limited sensor coverage. We have also presented belief function tools like specificity, entropy, belief and plausibility that can help to build relevant indicators to improve the reliability of the estimation process.

The frame of discernment presented here is simple and considers only two states which is very efficient for a realtime implementation as it has been shown by the real-time results. We believe that similar approaches can be applied to larger frames to enhance the understanding of the scene by refining the classification process.

1 Figure 1 .

 11 Figure 1. Change of state of the occupancy of a cell: F → O → F .

Figure 2 .

 2 Figure 2. Effect of discounting factor α = 0.05, occupancy of the cell: F → Ω (i.e. not observed) → O.

Figure 4 .

 4 Figure 4. Decision. Left: pl (O) > 0.5 (evidential), Middle: bel (O) > 0.5 (evidential), Right: P (O) > 0.5 (probabilistic)

  (a) Camera Image (b) Current lidar cloud points (c) Information metric comparison on a real occupancy grid.

Figure 3 .

 3 Figure 3. Results of the real-time implementation using a four layers lidar.


Ulrich Rührmair

Stefan Katzenbeisser

Martin Steinebach

Sascha Zmudzinski

Watermark-Based Authentication and Key Exchange in Teleconferencing Systems

In this paper we propose an architecture which combines watermarking with traditional cryptographic key agreement protocols to establish an authenticated or encrypted channel in teleconferencing systems. Technically the proposed method embeds messages of the key agreement protocol within an audio or video stream and is based on the assumption that the human communication partners can recognize each other easily; the watermark establishes a close coupling between the cryptographic key exchange messages and the media stream. We argue that the security of the scheme is based on a yet unexplored security property of digital watermarks; furthermore we present preliminary research results that suggest that this property holds in standard watermarking schemes.

Introduction

After the introduction of public-key cryptography, the problem of secure communication between two parties who have never exchanged secret keys seemed to be solved in practice. Ideally, communication partners access a trusted register (similar to a telephone book) in order to download each others public keys, which should be maintained by a trusted certification authority. Subsequently, the parties can use this key in order to encrypt and authenticate messages. Over three decades later, it has turned out that realizing this vision through a worldwide Public Key Infrastructure (PKI) is by no means simple. In fact, all attempts to establish a large-scale PKIs have failed due to organizational problems and lack of trust in certification authorities [START_REF] Ellison | Ten Risks of PKI: What You're not Being Told about Public Key Infrastructure[END_REF][START_REF] Ellison | Risks of PKI: Secure Email[END_REF].

It is thus pressing to consider alternative ways of authentication and key exchange, which do not utilize a PKI, but still allow to establish an encrypted and authenticated channel between two parties. In this paper, we consider a teleconferencing scenario, where two parties use digital telephony or a video conferencing system to establish a connection. Often, both communication partners know each other well enough to recognize their voices and/or each other on the transmitted audio or video stream. We propose to utilize this human knowledge and mutual recognition ability to authenticate a channel; key transfer is realized by using a watermark, which is directly embedded in this channel. More precisely, we embed messages of a key agreement protocol inseparably into the transmitted audio or video signal by means of a robust watermark. The analog voice or video signals, which can mutually be recognized as genuine by the communication partners, provide an authenticated channel that inhibits real-time masquerading attacks.

A natural way of establishing an encrypted phone or video conference utilizing the approach depicted above would work as follows: In the first phase, conversation is only transmitted in plain, but carries embedded information allowing secure key exchange. The messages required for key exchange are embedded by a watermark in the content. The two communication partners identify each other by recognizing the transmitted audio or video stream, and thereby implicitly authenticate the embedded key exchange messages. Once the key exchange has been completed, the system can encrypt all further communication between Alice and Bob in a second phase. The method seems suitable for establishing encrypted telephone or video communication in a highly convenient, ad hoc fashion, and would readily be usable with existing technology such as skype or similar services.

The approach is in principle similar to the Cryptophone architecture [1], where the communication equipment used by both communication partners sends Diffie-Hellman key exchange messages to each other. To detect a potential man-in-the-middle attack, the phones generate digests of the sent messages, which are displayed to the users. Both communication partners read the digest displayed on the phone over the encrypted line and the partner verifies if the hash was read correctly. If any discrepancy is detected, potentially a man-in-the-middle attack occurred. In comparison to the existing Cryptophone architecture, our approach is much more convenient as it does not require reading hash values aloud but ensures authenticity in the background of the communication. The approach also differs from [START_REF] Enayah | Securing Telecommunication based on Speaker Voice as the Public Key[END_REF], where a key is directly extracted from significant components of the speakers voices.

The rest of the paper is organized as follows. In Section 2 we propose a protocol that realizes the above mentioned authentication method in audio or video signals. Subsequently, Section 3 discusses the security of the proposed protocol; in particular we analyze which security property the underlying watermarking scheme needs to have to make the overall scheme secure.

Authentication Protocol

In this section we propose a protocol for teleconferencing systems that authenticates messages of key agreement protocols by help of the human user. As an example we describe the protocol in conjunction with the Diffie-Hellman key exchange. The protocol utilizes a watermarking scheme which only needs to be robust against varying channel conditions (the recipient will abort the protocol if no watermark is detectable). Instead, we use a different security assumption, which is detailed in the next section.

1. Both parties share the public system parameters: a random prime p, a generator g of Z * p and a global watermarking key K W . These parameters can e.g. be distributed along with the communication software. 2. Alice chooses suitably and uniformly at random an exponent a. 3. Alice and Bob begin their telephone or video call. 4. Alice embeds in her part of the conversation during the first seconds a watermark by use of the watermarking key K W . This watermark contains the payload H(p, g, g a mod p), where H denotes any cryptographic hash function. Furthermore, Alice sends the tuple (p, g, g a mod p) alongside the communication.

5. Bob verifies whether Alice's transmission was watermarked with key K W , that the watermark payload is a hash of the sent key exchange message, and that he is speaking to Alice by recognizing her image/voice. Furthermore, Bob also uses a detector software to scan for artifacts of signal manipulations, similar to tools used in forensic investigations (see Section 3). If any test fails, or if he did not receive a watermarked content, he aborts the protocol. 6. Bob chooses an exponent b and embeds a watermark with payload H(g b ) in the data stream (simultaneously to Alice). Furthermore, he sends g b to Alice. 7. Analogously to Bob, Alice verifies whether Bob's transmission was watermarked with key K W , that the watermark payload is the hash of the key exchange message and that she is speaking to Bob by recognizing his image/voice. She performs the same tests as Bob to detect any tampering with the audio or video stream. If any test fails, or if she did not receive watermarked content, she aborts the protocol. 8. Alice and Bob set their joint secret key to be K = g ab . 9. Alice and Bob henceforth encrypt their communication with the key K. Optionally, Alice and Bob may send each other confirmation messages that are authenticated with the key K to verify that the key exchange was successful.

The described mechanism for authenticating messages via watermarks and voice and/or image signals does not necessarily need to be used in connection with the Diffie-Hellman key exchange protocol. Any other key exchange protocol that operates in one challenge-response round is also possible; in this case, the public Diffie-Hellman messages are replaced with the messages of the key exchange protocol.

Instead of authenticating the messages of a key exchange protocol, one can also directly exchange and authenticate the public keys of the communication partners via the described mechanism in the audio and/or video streams. As usual, these transferred public keys can subsequently be used for encryption and authentication of further speech or video signals.

As a further variant, one could imagine that communication partners record little voice and/or video samples, embed their public key in the sample via a watermarking scheme, and post these sequences on their web-pages. Others can download these samples, watch them to judge whether they are genuine, and recover the embedded public key. These sequences could also be recorded newly in short distances, for example on a daily basis, with recorded person pronouncing the current date. This would not overstretch the security properties of the watermarks: They merely had to remain secure for one day in that example.

Security

Since the underlying key exchange mechanism is known to be secure, attacks mainly stem from the watermarking layer. It is crucial to note that, due to the fixed symmetric watermarking key K W , we have to assume that this key is available to an adversary as well. In principle we can distinguish between passive and active attackers; the former record the exchanged communication and try to obtain the key K, while the latter replace messages in order to impersonate one communication partner.

Passive attacks. The system inherits its security against passive attacks from the use of the Diffie-Hellman protocol. That is, an eavesdropper will not be able to restore K, unless he can break the cryptographic part of the protocol. However, since Diffie-Hellman key exchange provides no security against active attackers, security against active attackers must be considered separately.

Active attacks: Replaying unmarked sequences. In this type of attack, an adversary tries to obtain unmarked video or audio sequences of the communication partner (such as fragments of speech posted on web sites or captured by analog recording devices), selects its own Diffie-Hellman message and embeds the message into the signal by using its knowledge of the watermarking key K W . In a more sophisticated system, an adversary may even assemble speech fragments of one communication partner in order to generate a new coherent speech signal. Note that the same attack is possible against the Cryptophone architecture (record the voice of the communication partner when he pronounces the individual characters of the message digest and use speech synthesis to create a speech signal for a new digest). This attack cannot be prevented by technical means, but must be tackled by the communication partners themselves. For example, both communication partners can try to individualize the initial (unencrypted) part of the communication, e.g. by saying the time, the date, or by having Alice and Bob pronounce randomly chosen, unusual words from a dictionary. Alternatively, Alice and Bob might ask each other questions that only the correct communication partner can answer, or take similar measures to assure that the communication is not replayed or modified. Note that prevention of this attack in our scenario seems to be easier than in the Cryptophone architecture, since it is considerably easier to automatically synthesize speech pronouncing a small set of message digests rather than complex text.

Active attacks: Masquerading Attacks. Another threat consists in an adversary who records one protocol run and replays it at a later time with a different watermark. If successful, such an attack would allow to alter the watermark payload (to point to the key of the attacker), while the audio file is still authenticated by the recipient. This attack is particularly problematic, since many phone calls resemble each other in the first part (i.e., the parties state their names, greet each other, etc.). To exploit this, Eve records one typical initial conversation of Alice and re-embeds her own watermark into the data stream (potentially after performing signal processing operations aiming at removing the first watermark). Subsequently she can mount a masquerading attack by replaying the newly watermarked sequence.

Protection against this attack requires a novel security property of the employed digital watermark: a communication partner must be able to decide whether the watermark was embedded in a previously unmarked media object or in one that already carried a watermark that was embedded with the same key; first results can be found in [START_REF] Steinebach | Audio watermarking forensics: detecting malicious re-embedding[END_REF]. For the security of the scheme, both parties thus need to perform an analysis of the audio or video stream to detect such manipulation attempts. In contrast to the re-marking problem (where several watermarks are embedded with different keys), the particular problem has not extensively been discussed in the literature yet.

By applying methods from media forensics, it is possible to distinguish (within some error bounds) whether a media file has been marked before with the same key, since every watermarking process irreversibly changes the statistical characteristics of a media object. To see whether this is possible using a standard watermarking scheme we performed some initial experiments. In particular, we used an audio watermarking system, which employs the Patchwork embedding method in the Fourier domain and is used in commercial products [START_REF] Steinebach | Evaluation of robustness and transparency of multiple audio watermark embedding[END_REF][START_REF] Steinebach | Audio watermarking forensics: detecting malicious re-embedding[END_REF]. We tested different (mono) audio material of approximately 8.5 hours length, sampled at a rate of 44.1 kHz, into which we embedded a watermark sequence; subsequently we attacked the content in order to make a watermark visible where all payload bits are flipped. If a second watermark is embedded at the same strength as the first one (3dB in our experiment), the histograms of the detection statistics within single (Figure 1 an attacker embeds the second watermark with a larger strength (6dB), the two cases can still be distinguished (Figures 1(d) and 1(e) show the histograms of single and doubly marked content, while Figures 1(f) depicts the ROC curve), albeit at larger error rates (EER of approximately 20%). In addition, closer analysis shows that the adversary has to accept significant losses in sound quality, which might signal the attack to the communication partner. These preliminary results indicate that by using appropriate forensic analysis of the watermark detection responses, it is in principle possible to automatically determine whether a signal underwent malicious re-marking attacks under the same key. Further research is ongoing to determine the susceptibility of this classifier to other signal processing attacks.

Conclusions

We described a protocol that allows key establishment in digital telephony or video conferencing applications. In particular, we bind messages of a key exchange protocol as watermark to the audio or video stream and rely on the communication partners to recognize their voices. Due to the coupling of the messages and the digital data stream, the source of the messages is authenticated. We showed that the security of the approach crucially depends on a novel security property of watermarks, which has not been extensively discussed in the literature: one should be able to distinguish an object where a watermark was embedded in a previously unmarked media from one that already carried a watermark with the same key. Initial experiments showed that this question can in principle be answered (using a standard watermarking scheme) by analyzing the statistical properties of the detection response. Future work thus includes the definition of forensic methods that yield lower error rates.

Fig. 1 .

 1 Fig. 1. Robustness against re-marking with the same key.

  (a)) and doubly marked content (Figure1(b)) are clearly distinguishable by a simple classifier which compares the value of the detection response by a threshold. The ROC curve of this classifier is shown in Figure1(c); this plot shows that both cases can be distinguished with an EER of approximately 7%. If