David Margery

Emile Morel

Lucas Nussbaum

Olivier Richard

Cyril Rohr

Resources Description, Selection, Reservation and Verification on a Large-scale Testbed

Keywords: testbed, resources, discovery, description, reservation, verification

The management of resources on testbeds, including their description, reservation and verification, is a challenging issue, especially on of large scale testbeds such as those used for research on High Performance Computing or Clouds. In this paper, we present the solution designed for the Grid'5000 testbed in order to: (1) provide users with an in-depth and machine-parsable description of the testbed's resources;

(2) enable multi-criteria selection and reservation of resources using a HPC resource manager; (3) ensure that the description of the resources remains accurate.

Introduction

All scientific domains relying on experimental methodology require testbeds: particle colliders, synchrotrons, telescopes, greenhouses and experimental farms, etc. Computer science is not different, and the availability of testbeds is a requirement for solid science in fields such as distributed systems and networking.

When working on distributed systems such as Cloud computing infrastructures, high performance computing (HPC), peer-to-peer systems, or grid infrastructures, the scalability of solutions is often of central importance. To evaluate it, researchers rely on large-scale testbeds, much larger than what one laboratory or organization can usually fund and host, and often composed of a large number of resources scattered over various geographical locations.

Such testbeds and their resources raise a number of challenges, from both a testbed operator's and a user's point of view. Specifically, testbed operators need to keep track of all available resources, expose information about them to users, and make sure that they are still functioning adequately. Conversely, users need to be able to explore the resources and reserve them according to their experimental needs. Those operations have a critical role in the quality of research performed on such testbeds, both by ensuring that the initial experimental results are not tainted by malfunctioning or misdocumented resources, and by enabling the experimenter to describe the experimental environment in a way suitable for reproducible research.

This paper describes the framework designed in the context of the Grid'5000 testbed [START_REF] Cappello | Grid'5000: a large scale, reconfigurable, controlable and monitorable Grid platform[END_REF][START_REF] Balouek | Adding virtualization capabilities to the grid'5000 testbed[END_REF], a large scale testbed focusing on Cloud, HPC, P2P and Grid computing, to address the challenges of resources description, selection, reservation and verification. The remainder of this paper is organized as follows. Section 2 describes the Grid'5000 testbed in order to provide the context of this work. Section 3 describes our multi-tier framework for resources management. Related work is discussed in Section 4. Finally, we conclude that paper in Section 5. Started in 2003 and opened to the general public in 2004, the Grid'5000 project aims at providing a testbed for research on parallel and distributed systems, enabling researchers to validate their theoretical results and their software developments. It has been used for a large number of experiments, ranging from small scale to very large scale, and on a variety of topics: low level network protocols, virtualization environments, applications, etc. Grid'5000 has had between 500 and 600 active users per year since 2009, and at least 328 publications have been using Grid'5000.

As of 2014, Grid'5000 is composed of 11 sites (Figure 1), 26 clusters, 1260 nodes, and 8000 CPU cores. One particular focus of the testbed is the level of reconfiguration available to users: they can deploy their own software stacks (operating system, applications) on the bare metal using Kadeploy [START_REF] Jeanvoine | Kadeploy3: Efficient and Scalable Operating System Provisioning[END_REF], with no particular constraint. They can also reconfigure the network to isolate their experiments on the ethernet level (VLAN), in order to protect it from external perturbations, or to protect the testbed from intrusive protocols involved in the experiment. Thanks to those reconfiguration capabilities, Grid'5000 enables users to work on Cloud or Grid middlewares (OpenStack, OpenNebula, Nimbus, gLite) for the duration of an experiment. Figure 2 provides a general overview of our framework designed in the context of the Grid'5000 project to manage resources. This framework is composed of three components:

-The Reference API (Section 3.1) contains the description of all resources, as a set of JSON documents. -The OAR resource manager (Section 3.2) enables users to select and reserve resources. -The g5k-checks tool (Section 3.3) is in charge of the verification of resources.

Resources description with the Reference API

All resources descriptions are centralized in a NoSQL database, as a set of JSON documents that can be retrieved through a RESTful API. Those documents "supported_job_types" : { "deploy" : true, "besteffort" : true, "virtual" : "ivt" }, "chassis" : { "serial" : "27Q7NZ1", "manufacturer" : "Dell Inc.", "name" : "PowerEdge R720" }, "bios" : { "version" : 2, "release_date" : "08/29/2013", "vendor" : "Dell Inc." }, "architecture" : { "platform_type" : "x86_64", "smp_size" : 2, "smt_size" : 16 }, "processor" : { "instruction_set" : "x86-64", "cache_l1i" : 32768, "version" : "E5-2650", "cache_l2" : 262144, "model" : "Intel Xeon", "cache_l1d" : 32768, "cache_l3" : 20971520, "vendor" : "Intel", "clock_speed" : 2000000000 }, "main_memory" : { "ram_size" : 270991937536, }, "storage_devices" : [ { "rev" : "DL10", "model" : "INTEL SSDSC2BB30", "interface" : "SATA II", "device" : "sda", "size" : 300069052416, "driver" : "megaraid_sas" }, { "rev" : "DL10", "model" : "INTEL SSDSC2BB30", "interface" : "SATA II", "device" : "sdb", "size" : 300069052416, "driver" : "megaraid_sas" } ],

"network_adapters" : [ { "ip" : "172.16.68.1", "rate" : 10000000000, "mountable" : true, "interface" : "Ethernet", "mounted" : true, "mac" : "b8:ca:3a:69:12:68", "enabled" : true, "version" : "82599EB", "device" : "eth0", "ip6" : "fe80::baca:3aff:fe69:1268", "network_address" : "graphite-1", "switch_port" : "F1", "switch" : "gw-nancy", "management" : false, "driver" : "ixgbe", "vendor" : "intel" }, { "version" : "IDRAC7", "ip" : "172.17.68.1", "device" : "bmc", "network_address" : "graphite-1-bmc", "switch_port" : "1/0/41", "rate" : 100000000, "switch" : "sgraphene3-ipmi", "mountable" : false, "interface" : "Ethernet", "mounted" : false, "mac" : "f0:1f:af:e1:9a:0c", "management" : true, "vendor" : "DELL", "enabled" : true } ], "sensors" : { "power" : { "via" : { "pdu" : { "uid" : "graphene-pdu9", "port" : 24 }, "api" : { "metric" : "pdu" } }, } }, "mic" : { "mic_model" : "7120P", "mic" : true, "mic_count" : 1 }, "performance" : { "core_flops" : 13170000000, "node_flops" : 187900000000 } Fig. 3. Description of one node in the Reference API.

provide an in-depth description of most of the testbed's resources: nodes of course (Figure 3), but also network equipment (switches, routers) and other equipment such as power distribution units (PDU), with information such as the vendor, product name and reference, how the equipment is connected, and instructions on how to access remote control and measurement capabilities through SNMP.

This API is used by a number of tools, to generate documentation (list of all available resources), maps (e.g. network topology), and to enable remote control of resources. For example, the KaVLAN tool in charge of network isolation using VLAN reconfiguration on switches, relies on the mapping between nodes and network switches provided by the Reference API.

Most of the data in the Reference API is collected automatically by g5kchecks, which will be described in Section 3.3. A few data fields, whose value cannot be automatically discovered, require manual intervention from the testbed operator.

The data stored in the reference API is archived in a Git repository, which makes it possible to follow the testbed's evolutions over time, or retrieve the state of the testbed at a given date, which is useful in order to explain specific experimental results.

Resources selection and reservation with OAR

Reserving two nodes for two hours. Nodes must have a GPU and power monitoring:

oarsub -p "wattmeter='YES' and gpu='YES'" -l nodes=2,walltime=2 -I

Reserving one node on cluster a, and two nodes with a 10 Gbps network adapter on cluster b:

oarsub -I -l "{cluster='a'}/nodes=1+{cluster='b' and eth10g='YES'}/nodes=2,walltime=2"

Advance reservation of 10 nodes on the same switch with support for Intel VT (virtualization):

oarsub -l "{virtual='ivt'}/switch=1/nodes=10,walltime=2" -r '2014-11-08 09:00:00' As the Grid'5000 infrastructure was originally designed by the HPC community, it felt natural at the time to use a HPC batch scheduler as the building block for resource reservation. The OAR resource manager [START_REF] Capit | A batch scheduler with high level components[END_REF][START_REF]OAR -a versatile resource and task manager for hpc clusters and other computing infrastructures[END_REF] provides two main useful features in the context of a testbed.

Resources properties

Most HPC resource managers such as Slurm [START_REF] Yoo | Slurm: Simple linux utility for resource management[END_REF] limit the structuring of resources in partitions of nodes considered identical. On the other hand, with OAR, each node can be associated with a number of properties, that can later be used to request resources fulfilling specific needs, as shown in Figure 4. This enables users to request resources matching specific properties, rather than rely on explicit naming of requested resources: the burden of filtering resources for specific user requirements is transferred from the user to the resource manager.

On Grid'5000, OAR properties are generated automatically using data from the Reference API, and cover most of the data available in it. Also, resources are not limited to nodes. On Grid'5000, we also use OAR to reserve storage space and network subnets (for experiments requiring additional network addresses for virtual machines).

Advance reservations of resources Most HPC resource managers focus on batch tasks, where the resource manager tries to start tasks as early as possible given available resources, but does not provide an opportunity for the user to specify when the resources should be allocated. This is a reasonable strategy for a HPC cluster, as the tasks do not require any user intervention. However, in the context of a testbed, most experiments require human intervention, as experiments that can run automatically without problems are quite rare.

OAR provides a batch scheduling mode, but also provides the possibility to request advance reservation of resources: at the time of the resource request, users can specify when they would like the resources to be allocated, and for which duration. On Grid'5000, this is coupled with a policy of only allowing large reservations of resources during nights and week-ends: during week days, this favors shared use of the testbed by many users so that they can prepare their experiments, and then run the actual experiments during nights and weekends. OAR also provides a visualization of the planned reservations as a Gantt diagram (Figure 5).

Resources verification with g5k-checks

A key challenge when maintaining a description of a testbed is to ensure that it is accurate. Inaccuracies could mislead research into making false assumptions, with dramatic consequences: incorrect results, publications that need to be retracted, etc. Unfortunately, hardware failures that have an impact on experiments are not uncommon: malfunctioning hard disk drives or broken RAM memory banks that result in less memory being available occur on a weekly, if not daily basis on Grid'5000.

On Grid'5000, we designed a tool called g5k-checks. g5k-checks is run when a node boots, and at regular intervals when no jobs are scheduled on a node. It is in charge of verifying that the node matches its description in the Reference API, by: (1) retrieving the current description of the node; (2) using several tools to acquire information on the node; (3) comparing the acquired information with the one from the Reference API, and marking the node as unavailable if the information does not match.

For most of its work, g5k-checks uses Ohai [START_REF] Ohai | [END_REF], a Ruby library to detect various attributes on a node. Additionally, it also relies on tools such as ethtool to gather the configuration of network interfaces.

g5k-checks has two additional modes of operation. First, it can be run directly by users during jobs where they pushed their own software environment to the nodes, which is useful in order to record the execution environment of a job. Second, testbed operators can use it to collect the information needed to fill the Reference API. This procedure is also a good opportunities to detect outliers among nodes, which are not uncommon when one installs a large new cluster.

Interfaces with external tools

During the design of this framework, a lot of focus has been put in enabling external contributors to develop their own tools. Both the Reference API and OAR provide APIs that can be used to automate complex tasks. For example, one limitation of the Grid'5000 testbed is its distributed nature: each site has its own instance of the resource manager, which can make it hard to reserve a large number of resources on several sites at once. So one Grid'5000 user developed a tool, called Funk, that uses the Reference and OAR API to find resources matching a specification, and analyze the planning of reservations in order to find a matching time slot.

Related work

Despite a large number of testbeds, both for Internet of Things and WSN [START_REF] Gluhak | A survey on facilities for experimental internet of things research[END_REF] and for HPC and Cloud [START_REF] Desprez | Supporting Experimental Computer Science[END_REF], our work is the only one presented as an integrated solution for the management of resources -most of the testbeds seem to only address a subset of the facets addressed in that paper.

Resource description and selection has been the focus on the more attention. Several solutions have been designed over the years, such as PlanetLab's SWORD [START_REF] Oppenheimer | Distributed resource discovery on planetlab with SWORD[END_REF], GENI's RSpec [START_REF]Rspec[END_REF] or SensorML [START_REF] Aloisio | Sensorml for grid sensor networks[END_REF].

Most testbeds, especially in the WSN context, do not provide a way to reserve resources in advance. A notable exception is SensLab [START_REF] Des Roziers | Using SensLAB as a first class scientific tool for large scale wireless sensor network experiments[END_REF], which also uses OAR, and was actually inspired by our work on Grid'5000 (as both testbeds are mainly located in France).

Finally, while many tools can be used to explore the content of a resource (lshw, hwinfo) or to benchmark it, we are not aware of any other general attempt of comparing the results of such tools with a reference in order to detect malfunctioning hardware in the context of a testbed.

Conclusions and future work

In this paper, we presented an integrated, and fully-functional solution for the management of resources designed in the context of the Grid'5000 testbed. This solution provides users with an in-depth and machine-parsable (JSON) description of the testbed's resources. It enables multi-criteria selection and reservation of resources by using the OAR HPC job scheduler. Finally, it ensures that the description of resources remains accurate, by comparing it on a regular basis with information retrieving by a tool executed on each resource.

The main area of future improvement of this work is the verification of resources. Most of the tests currently implemented confirm the presence and the vendor & product information of a given piece of hardware, but do not verify its performance. It would be extremely useful to extend g5k-checks with some performance testing, especially for pieces of hardware that tend to fail frequently, such as hard disk drives. However, this needs to be balanced with the load imposed on the testbed by such testing -one need to use or design testing tools that are sufficiently efficient to provide an accurate performance measurement after a very short test.

Fig. 1 .

 1 Fig. 1. Map of the Grid'5000 testbed.

Fig. 2 .

 2 Fig. 2. General structure of resource management framework.

Fig. 4 .

 4 Fig. 4. Example uses of OAR properties to request resources matching requirements.

Fig. 5 .

 5 Fig. 5. Visualization of the usage of a Grid'5000 site using a Gantt diagram.


Tomasz Buchert

Emmanuel Jeanvoine

Lucas Nussbaum

Emulation at Very Large Scale with Distem

Keywords: large scale, emulation, VXLAN, virtualization

Prospective exascale systems and large-scale cloud infrastructures are composed of dozens of thousands of nodes. Evaluating applications that target such environments is extremely difficult. In this paper, we present an extension of the Distem emulator to allow experimenting on very large scale emulated platforms thanks to the use of a VXLAN overlay network. We demonstrate that Distem is capable of emulating 40,000 virtual nodes on 168 physical nodes, and use the resulting emulated environment to compare two efficient parallel command runners: TakTuk and ClusterShell.

I. INTRODUCTION

In the fields of cloud computing or high performance computing, the next generation platforms will involve more and more computing units. Being able to efficiently use those new infrastructures is a real challenge and numerous efforts are needed to write appropriate distributed applications. Furthermore, evaluating such applications can be complicated since the final platform is sometimes not available, at least for development purpose.

In previous work, we presented Distem [START_REF] Sarzyniec | Design and Evaluation of a Virtual Experimental Environment for Distributed Systems[END_REF], that provides an emulated platform on top of a regular cluster in order to facilitate the experimentation with distributed systems. In this paper, we focus on enhancing Distem to deal with large-scale experiments, typically those involving several dozens of thousands of nodes. In particular, we explain how leveraging overlay networks helps to push back some previously reached limitations. Being able to build largescale platform is required to conduct large-scale experiments but is not enough. Indeed, we also present a methodology that leverages XPFlow [START_REF] Buchert | A workflowinspired, modular and robust approach to experiments in distributed systems[END_REF] to perform clean and reproducible large-scale experiments.

The paper is organized as follows. Section II presents a general overview of Distem and how it has been enhanced to be able to emulate very large-scale platforms. Section III presents experiments carried out on 40,000 nodes that aimed at showing the scalability of two efficient parallel command tools. Section IV gives conclusions and presents future works.

II. LARGE SCALE DISTRIBUTED SYSTEM EMULATOR

A. General overview

Distem [START_REF] Sarzyniec | Design and Evaluation of a Virtual Experimental Environment for Distributed Systems[END_REF] is a distributed system emulator that leverages advanced Linux features like LXC, CPU frequency scaling and traffic control, to emulate a heterogeneous platform on top of a homogeneous cluster. Heterogeneity can be obtained by (1) specifying a virtual network topology where latency and bandwidth of the links can be defined, (2) emulating a degraded CPU capability, (3) executing several virtual nodes on a single physical node. Furthermore, Distem is able to inject failures in the virtual platform in order to perform experiment in realistic conditions.

Distem is a valuable tool for distributed system evaluation since it allows one to perform experiments in various conditions with only one physical testbed. Furthermore, Distem improves reproducibility since the same experimental setup can be reproduced on different physical infrastructure. Typical applications are: the study of a peer-to-peer protocol, the study of a load-balancing algorithm, the study of a scheduler, etc.

B. Enabling Large-Scale Experiments in Distem

Previously, we have explored the Distem scalability to several thousands of virtual nodes (vnodes). Such virtual platforms can easily be set up on clusters with 100 nodes. Going beyond these numbers in terms of scale meets with various network issues. As a reminder1 , virtual nodes are connected together in the following way. Every vnode has a Virtual Ethernet device (veth) bridged into a Linux bridge created on the physical node (pnode). The network interface of the pnode is bridged into the Linux bridge. As a consequence, vnodes and pnodes are in the same L2 network. When running more than 5,000 vnodes using this architecture, several ARP-related problems appear. The ARP protocol is used to provide mapping between a network hardware address (i.e., MAC) and an IP address, a process required in Ethernet networks to enable communication between any two nodes. The encountered problems are:

1) the ARP protocol does not scale very well, in particular when a lot of requests are performed at the same time, a phenomenon known as ARP flooding;

2) the ARP tables, in particular those in the network equipment, have a hard-wired size limit (usually 8,096 or 16,192 entries) or are rather small (in the case of default Linux settings); consequently, the addresses of vnodes cannot be stored simultaneously in the table, leading to excessive numbers of ARP requests since the table is updated according to a LRU policy. In a related work on large-scale virtualization [START_REF] Minnich | Ten Million and One Penguins, or, Lessons Learned from booting millions of virtual machines on HPC systems[END_REF], the authors worked around this problem by partitioning the address into smaller networks, using routing between those smaller networks; 3) by default, the ARP entries are purged after a quite short time, leading to unnecessary and intrusive ARP traffic during an experiment. Some of those issues has been fixed at the system level. Indeed, Distem performs tuning of various operating systems parameters on the pnodes to avoid useless ARP requests. In particular, on each pnode, Distem increases the ARP table size and the aging time of the ARP entries. Furthermore, Distem can be used to statically set a complete ARP table on all the vnodes, completely avoiding the ARP requests between them. These adjustments prove to be very effective, making it possible to perform experiments with 15,000 vnodes in the same L2 network. However, the problem of ARP tables still affects the network equipment, since in most of the cases it is not possible to modify their ARP settings.

To go beyond this limitation, we leveraged the capabilities of overlay networks, and in particular the VXLAN [START_REF] Mahalingam | VXLAN: A Framework for Overlaying Virtualized Layer 2 Networks over Layer 3 Networks[END_REF] protocol. VXLAN encapsulates L2 network traffic in UDP datagrams, which is very interesting in our context. Indeed, encapsulating the inter-pnode traffic using VXLAN overlay relieves the network switches since they do not have to deal anymore with vnode traffic directly: their ARP tables only need to store information about pnodes. We have explored a similar approach with GRE-tunnel encapsulation [START_REF] Farinacci | Generic Routing Encapsulation (GRE)[END_REF]. This is working well with a few pnodes in the network, but it does not scale at all since a full mesh between pnodes has to be created. Our experiments were unsuccessful with more than 10 pnodes.

Furthermore, to enable high bandwidth and low latency between pnodes, we used an InfiniBand network. This allows to lower the inter-vnode latency and to achieve large-scale experiments since the involved network equipment is more efficient when dealing with high-throughput traffic.

C. Technical details

Using VXLAN to encapsulate the inter-pnode traffic slightly modifies the previous Distem design. To virtual network, for instance it is used as a foundation of the network management of OpenStack. However, for simplicity of use and to minimize dependencies, we based Distem's VXLAN support on top of the Linux implementation. Figure 1 presents the network stack of a vnode when using the VXLAN encapsulation in Distem. First, a VXLAN interface is set on top of the pnode's physical interface. Because the VXLAN overlay carries aggregated traffic of all vnodes, a high-performance network interface offering IP interface, like 10G-Ethernet interface or IPoIB, is needed. Then, each pnode has a bridge that contains the VXLAN interface and interfaces of all vnodes on the given pnode. In this case, the bridge does not contain directly the physical network interface and all the vnodes' traffic is encapsulated before reaching the physical network interface. There is no need to specify routes between pnodes since VXLAN uses multicast-based discovery features that allow to establish the routes between several nodes automatically.

III. EXPERIMENTAL VALIDATION

A. Purpose

In those experiments, we want to study two parallel commands tools: TakTuk [START_REF] Claudel | TakTuk, adaptive deployment of remote executions[END_REF] and ClusterShell [START_REF] Thiell | Clus-terShell, a scalable execution framework for parallel tasks[END_REF], [START_REF] Thiell | ClusterShell, Python library and tools for scalable cluster administration[END_REF] (aka Clush). Both tools aim at efficient execution of command on a large set of nodes, which is a critical concern since executing administrative tasks or executing complex applications on large-scale clusters may rely on such tools. For instance, executing a simple command on dozens of thousands of nodes can take a lot of time if not performed in a proper way.

ClusterShell and TakTuk differ in their way to achieve high performance. ClusterShell uses a sliding window: the root node establishes SSH connections in parallel to several nodes, bounding the number of concurrent connections. TakTuk, instead, uses a tree-based algorithm, using nodes already connected to connect to additional nodes 3 . The experiment presented below will allow the comparison of those two strategies.

B. Physical Setup

The experiment has been executed on the Grid'5000 testbed [START_REF]Grid'5000[END_REF]. More precisely, we used the Graphene and Griffon clusters from the Nancy site. Graphene is composed of 144 nodes (1 CPU Intel X3440 @2.53 GHz, 4 cores/CPU, 16GB RAM on each node) and Griffon is composed of 92 nodes (2 CPU Intel L5420 @2.50GHz, 4 cores/CPU, 16GB RAM on each node). Both clusters are interconnected with 20Gbit InfiniBand network and run Debian Jessie with Linux kernel at version 3.12.

On top of those clusters, we emulated a virtual platform with Distem and 162 physical nodes. Each pnode hosted 246 vnodes. All inter-pnode traffic was encapsulated inside a VXLAN overlay. Each VXLAN interface was plugged on top of an IPoIB interface to leverage the performance of the InfiniBand network.

C. Methodological Setup

Experiments where carried out with XPFlow [START_REF] Buchert | A workflowinspired, modular and robust approach to experiments in distributed systems[END_REF], a tool based on business processes and workflows, and specifically designed to manage large-scale experiments. Among its features are robust failure handling and useful workflow patterns that model common experimental activities. In particular, XPFlow allowed us to transparently manage a failure of one physical node during our experiments, as it is explained in the following section. Figure 2 presents the experimental workflow.

Although our primary goal is to verify and show scalability of Distem, we wanted to show it using a study of various methods for command execution in large computer installations. To this end, we measured the time necessary to successfully execute the command true on a varying number of nodes. Each measure is repeated 3 times and the results are presented with 95% confidence intervals according to Student's t-distribution.

The raw results, the experimental workflow and associated files are available at http://www.loria.fr/ ∼ buchert/scale2014. tar.xz.

D. Results

The results with small number of nodes are presented in Figure 3. This range was chosen to show the size of infrastructure when sliding-window algorithms for command execution become inferior to ones based on tree topology. It happens around 1,400 nodes (for TakTuk with arity 3) and around 1,800 nodes (for TakTuk with arity 2).

Figure 4 shows the same type of experiments, but with a much larger infrastructure. Distem, thanks to it use of VXLAN encapsulation, shows a great scalability. Our goal of 40,000 nodes was almost reached, as we were able to successfully run our measurements with up to 39,852 virtual nodes. The reason for that is that one physical node failed during our measurements and had to be discarded. Fortunately, the presence of this failure was promptly detected and addressed by our experimental framework. Apart from that detail, we do not see why the scalability of Distem could not be pushed even more.

It can be expected that the total execution time consists of a constant factor, a linear factor (due to a constant time required by each node) and a logarithmic factor (due to a tree topology used by TakTuk). Therefore, we modeled the execution time using the model function

T (n) = A • n + B • log (n) + C (1)
where T -execution time, n -number of nodes, and A, B, C -parameters of the model. The least squares fitting of the data to this model gives:

T C (n) = 0.01649 • n -7.55 • log (n) + 52, (2)
T 2 (n) = 0.00146 • n + 3.55 • log (n) -4, (3)
T 3 (n) = 0.00099 • n + 2.27 • log (n) + 4. (4)
where T C , T 2 , T 3 are results for Clush, TakTuk with arity 2, and TakTuk with arity 3, respectively. Figure 4. The time required to execute a command using various methods (large number of nodes). Clush is increasingly outperformed by both variations of TakTuk which use a tree overlay to execute commands.

We clearly see that the linear factor of Clush has the most impact on its total execution time, whereas in the case of TakTuk methods the linear factor is an order of magnitude smaller and constitutes a smaller percentage of execution time.

IV. CONCLUSIONS AND FUTURE WORK

In this paper, we showed Distem's ability to scale to large emulated infrastructures. This feature depends on VXLAN encapsulation which is a modern network virtualization technology to address problems associated with large-scale distributed systems. We were able to successfully run our experiments with 39,852 virtual nodes hosted on 162 physical nodes interconnected with InfiniBand (although one node failed unexpectedly), showing scalability of VXLAN and Distem. Finally, we used this infrastructure to perform a simple analysis of different methods for command execution.

Future work will follow two directions. The first direction is to improve Distem in order to perform very large scale experiments with nodes in a single L2 network. Our next goal is to reach experiments involving more than 100,000 vnodes. Currently, one of the difficulties is to get access to large number of nodes in the same L2 network with root rights. The second direction is to enhance Distem with a distributed mode in order to perform experiments involving nodes from several geographical sites and many L2 networks. This way, Distem would be able to deal with extreme scale experiments.

3 Figure 2 .

 32 Figure2. Experimental workflow. After the infrastructure is prepared (the first line of the workflow), a varying number of nodes (n) is used to run Clush and TakTuk methods in a simple loop (denoted with "="). At each iteration, the Distem infrastructure is analyzed and failed nodes are discarded if necessary.

  create such an overlay, at least two possibilities exist: (1) leveraging OpenVSwitch 2 that offers VXLAN encapsulation, or[START_REF] Buchert | A workflowinspired, modular and robust approach to experiments in distributed systems[END_REF] leveraging Linux that added VXLAN support since 3.7 version. OpenVSwitch is probably the best direction to create Network stack of a virtual node when using VXLAN encapsulation. Each virtual node has a virtual interface (veth i ) that is bridged with VXLAN interface (vxlan 0 ) on each pnode. This interface is associated with physical IP interface (ib 0 ). In our study IPoIB is used, but more traditional IP over Ethernet can be used as well.

		Pnode		Pnode
	Vnode	Vnode	Vnode	Vnode
	veth 0	. . . veth n	veth 0	. . . veth n
			. . .
		br 0		br 0
		vxlan 0		vxlan 0
		ib 0	IP	ib 0
			network
			InfiniBand
	Figure 1.
	2 http://openvswitch.org/

See[START_REF] Sarzyniec | Design and Evaluation of a Virtual Experimental Environment for Distributed Systems[END_REF] for a complete explanation.

A similar mode of operation is available in ClusterShell's development branch, but we encountered problems when using it and discarded it from our experiments.

ACKNOWLEDGMENT

Experiments presented in this paper were carried out using the Grid'5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr).


Hybrid Sampling Bayesian Occupancy Filter

Amaury Nègre1 and Lukas Rummelhard2 and Christian Laugier 2 Abstract-Modeling and monitoring dynamic environments is a complex task but is crucial in the field of intelligent vehicle. A traditional way of addressing these issues is the modeling of moving objects, through Detection And Tracking of Moving Objects (DATMO) methods. An alternative to a classic object model framework is the occupancy grid filtering domain. Instead of segmenting the scene into objects and track them, the environment is represented as a regular grid of occupancy, in which each cell is tracked at a sub-object level. The Bayesian Occupancy Filter [START_REF] Coué | Bayesian occupancy filtering for multitarget tracking: an automotive application[END_REF] is a generic occupancy grid framework which predicts the spread of spatial occupancy by estimating cell velocity distributions. However its velocity model, corresponding to a transition histogram per cell, leads to huge data management which in practice makes it hardly compatible to severe computational and hardware constraints, like in many embedded systems. In this paper, we present a new representation for the BOF, describing the environment through a mix of static and dynamic occupancy. This differentiation enables the use of a model adapted to the considered nature: static occupancy is described in a classic occupancy grid, while dynamic occupancy is modeled by a set of moving particles. Both static and dynamic parts are jointly generated and evaluated, their distribution over the cells being adjusted. This approach leads to a more compact model and to drastically improve the accuracy of the results, in particular in term of velocities. Experimental results show that the number of values required to model the velocities have been reduced from a typical 900 per cell (for a 30x30 neighborhood) to less than 2 per cell in average. The massive data compression allows to plan dedicated embedded devices.

I. INTRODUCTION

In the fields of mobile robotics or intelligent vehicle, a key requirement for basic functionalities, such as navigation, mapping or collision awareness systems, is the ability to perceive and model a relevant representation of the dynamic environment. This crucial task is a challenging step. Its complexity is caused not only by the expectancies in term of result accuracy and pertinence, but also by the observed environment constitution itself. Indeed the exploration of an uncontrolled environment implies a meticulous analysis, robust to the diversity in the backgrounds, the encountered objects, their conceivable behaviors, the potential sensor errors or occlusions. Probabilistic methods enable to formally introduce in the models the uncertainties and prior knowledge, and have led to the development of efficient techniques, especially in static environments. When confronted to moving objects, many new issues are raised, the field of dynamic environment modeling still being active [START_REF] Petrovskaya | Awareness of road scene participants for autonomous driving[END_REF]. A classic way to address this problem is to adopt an objectbased representation, which leads to multiple target object tracking literature [START_REF] Fortmann | Multi-target tracking using joint probabilistic data association[END_REF], [START_REF] Khan | An mcmc-based particle filter for tracking multiple interacting targets[END_REF]. Another common approach is the field of occupancy grids [START_REF] Elfes | Using occupancy grids for mobile robot perception and navigation[END_REF], [START_REF] Moravec | Sensor fusion in certainty grids for mobile robots[END_REF], which works on spatial occupancy without higher level segmentation. Significant advantages are then to avoid the delicate data segmentation and recognition, and producing a spatially dense model, empty space management being often needed, especially for intelligent vehicles.

The Bayesian Occupancy Filter (BOF) [START_REF] Coué | Bayesian occupancy filtering for multitarget tracking: an automotive application[END_REF] is a occupancy grid solution which infers the cell occupancy motion by a sub-object level tracking. To each cell are associated random variables modeling the occupancy and the velocity, concretely in the form of a transition histogram. This representation is convenient, facilitating computing parallelisation, but inserts in the method serious defaults, as aliasing issues and a curse of dimensionality when applied in practice.

In this paper, we present a new representation for the BOF, in which the scene is analysed through a static-dynamic duality. The static part is a occupancy grid structure, and the dynamic field is modeled by moving particles. Both sections are jointly generated and evaluated. This distinction is pertinent for the scene interpretation, but also for a way more efficient calculation, allowing to focus the velocity computation on the dynamic objects.

II. RELATED WORKS

The field of occupancy grid representation based interpretation of the environment is a developed study domain, overlapping various applications, such as intelligent environment management, automatic autonomous navigation or extended vehicle perception. The aim is to produce a compact regularly subdivided estimation of the spatial occupancy, without the requirement of object concepts. This structure usually implies the inference of cell dynamics. According to the method used to design and fill the grid, the algorithms are more or less reliant on the sensor type. To build the scene representation of their perceptive vehicle, Badino et al. [START_REF] Badino | The stixel world-a compact medium level representation of the 3d-world[END_REF] use an efficient medium level representation based on occupancy grids, but precisely designed for stereo vision, and traffic application. In many practical cases, in which are not a priori known the surroundings or even the types of the to be used sensors, a more generic approach is necessary.

The Bayesian Occupancy Filter [START_REF] Coué | Bayesian occupancy filtering for multitarget tracking: an automotive application[END_REF] is a generic Bayesian framework which updates a dynamic occupancy grid by filtering the occupancy and velocity in each cell in parallel. The observation model is incorporated as an instantaneous occupancy grid, which is generated by the used sensors but presents the observations in a generic form. To each cell is associated a estimated motion distribution in the form of a neighbourhood transition histogram. This motion discretization design leads to high computational costs and aliasing issues. The BOFUM [START_REF] Gindele | Bayesian occupancy grid filter for dynamic environments using prior map knowledge[END_REF] proposes to use prior map knowledge to accelerate the convergence of the BOF, and then potentially reduce the required data dimensions, but such maps are not always available and their use requires a precise localization. To reduce the motion field dimensions, the histogram in each cell being mainly empty, a sampling of the motion distribution can be used. An importance sampling method has been proposed [START_REF] Brechtel | Recursive importance sampling for efficient grid-based occupancy filtering in dynamic environments[END_REF], but by drawing a fixed number of discrete velocity vectors per cell the aliasing problem is not resolved, and if the dimensions of the dynamics is already highly reduced, a more adaptive method can still drastically decrease it. As most cells, like empty or static ones, do not necessitate elaborated representation, important processing ressources can be saved. In the process presented by Danescu et al. [START_REF] Danescu | Modeling and tracking the driving environment with a particle-based occupancy grid[END_REF], the idea to use a variable number of samples per cell, according to the occupancy estimated, is implemented. The scene is represented by a set of moving particles having not discretized positions and values, which corrects most of aliasing problems. The number of particles per cell corresponds to the occupancy of the cell, which leads to a very compact model. Nevertheless, a huge number of particles are still stated to represent static objects. Furthermore it deserves a generic Bayesian formalization.

III. BOF FORMALISATION

The Bayesian Occupancy Filter (BOF) is a process that recursively estimates the occupancy and the velocity state of spatial cells. It associates to each cell random variables which evolution is used to describe the scene. The displayed here model is mainly based on the one defined in [START_REF] Tay | An efficient formulation of the bayesian occupation filter for target tracking in dynamic environments[END_REF], to which is added a dynamic model to handle non constant velocity objects and priors on speeds and occupancies to avoid empty cells to move. The formalism used in the description comes from the Bayesian programming framework [START_REF] Bessière | Bayesian Programming[END_REF]. Given the set of random variables, the expression of their joint probability decomposition, the wanted distribution can easily be expressed, as presented in the following.

A. Variable definition

C : Index that identify each 2D cell.

A : Index that identify each possible antecedent of a cell. O : Occupancy of the cell at current time. Its possible values are {occ, emp}. O -1 : Occupancy of the antecedent cell at previous time. V : Speed of the cell at current time. It's possibles values is a 2D vector in R 2 . V -1 : Speed of the antecedent cell at previous time. Z : Sensor measurement.

B. Joint distribution

P (CAOO -1 V V -1 Z) = P (A) P (O -1 V -1 |A) P (OV |O -1 V -1 ) P (C|AV ) P (Z|OV C) (1)
Each expression can be interpreted as follows :

• P (A) is the distribution over all possible antecedent of the cell. It is chosen to be uniform as the cell is considered reachable from all the antecedents with equal probability.

• P (O -1 V -1 |A) is the conditional joint distribution over the occupancy and velocity of the antecedents. This distribution is updated at each time step.

• P (OV |O -1 V -1
) is the prediction model. The chosen model can be decomposed as the product of two terms, P (O|O -1 )P (V |V -1 O) .

-P (O|O -1 ) is the conditional distribution over the occupancy of the current cell given the occupancy of the previous cell. It is defined by a transition matrix :

T = 1 -ǫ ǫ ǫ 1 -ǫ
, which allow a cell to change its occupancy state with a low probability to take into account approximation errors. -P (V |V -1 O) is the conditional distribution over the current velocity knowing the previous velocity. We usually choose a Normal law, centered on the previous speed to represent a Gaussian acceleration model. This distribution can be adapted to fit various observed objects. As we consider that an empty cell can not move, a Dirac function is added in order to prevent it.

• P (C|AV ) is the distribution that explains if the cell c is reachable from the antecedent [A = a] with the velocity

[V = v].
This distribution is a Dirac with value equal to one if and only if a X + v X δt ∈ c.

• P (Z|OV C) is the distribution over the sensor measurement value.

C. Problem computation

The aim of the bayesian filtering process is to estimate the occupancy and the speed with respect to the current observation for every cells P (OV |ZC). By using a discretization of the antecedent cells and of the velocities, the filtering equation can be write as follows :

P (OV |ZC) = AO -1 V -1 P (CAOO -1 V V -1 Z) AOO -1 V V -1 P (CAOO -1 V V -1 Z) (2)
IV. HYBRID SAMPLING

A. Introduction

The classic Bayesian Occupancy Filter (BOF) is a discretized uniform grid structure based Bayesian algorithm, in which the environment is subdivided in cells, each cell having an occupancy likelihood and associated motion distribution represented as a neighborhood transition histogram. If this representation is convenient for the fusion of data (the rigid structure gives a useful framework to merge data of heterogeneous layout) and potential antecedent research, since the potential antecedents of any cell is exactly structuredetermined, it also raises determinant issues :

• the structure requires the process rate to be constant, and a priori known.

• in the case of a moving grid, such as an application of car perception, many aliasing problems can appear, not only in the occupancy grid, but also in the motion distributions. An interpolation in 4-dimension field to fill each value of the histograms can quickly become unreasonable.

• to be able to match the slowest moves in the scene and the smallest objects, as well as the most dynamic objects, high resolution and range motion histograms are required. These huge grids are paradoxically mostly empty : most of the occupied cell motion histogram will be empty (most cells are occupied by a single object), and an empty cell motion distribution is irrelevant.

Besides, when the perception system is used to represent the direct environment of a moving subject (car for instance), the encoded velocity is a relative one, which implies, if we consider the maximal motion speed to be V max , to maintain a motion distribution able to represent speeds from -2 * V max to 2 * V max . The necessity of such a sized structure is a huge limitation of a practical use of the method, and prevents it from being used with satisfying results on an embedded device. Considering those limitations, another representation of the environment, more suited to describe the velocities of the surrounding of a moving vehicle, should be introduced. The first idea is to represent the motion distribution of a cell as a set of particles instead of a regular grid (figure 1). This leads to a more compact and discretization limitation free representation. The second step is to take into account that in a common practical setting, most of the scene is static : the background and most objects have null velocity, and empty cells have no velocity. Those scene areas do not necessitate any complex velocity model. The goal of our representation is to decompose the scene into two parts : the static scene, and the dynamic section.

B. Data representation : dynamics segregation

To represent the spatial occupancy, a regular grid is used, as it is effective to merge various observation data, but also as in most applications, a dense, complete representation of the environment is required. The motion analysis is decomposed into two sections : a static field, where are represented the static objects and the free areas, and a dynamic field, for the moving objects.

• Grids for static cells : The static part of the scene is composed by the stationary objects and free areas, which by convention are assigned zero speed (if the velocity of the empty space is irrelevant, the knowledge of emptiness in an area should be spread in time). It corresponds to P (V = 0).

• Particles for dynamic objects : The dynamics of the moving areas are represented by a set of particles {χ i }.

Those particles are composed of a velocity vector v i and an exact spatial position x i , to avoid aliasing. Those samples are drawn along the distribution P (V = v|V = 0). A weight w i is also associated to each particle to represent the distribution of the speed in a cell. As further explained in the re-sampling part, the particles set is a shared resource for the scene representation, a fixed number of particles is drawn for the entire representation of the scene dynamics, spatially allocated according to the distribution P (V = 0). Each cell can therefore be decomposed in three sections: the empty section, the static occupied section and the dynamic occupied section (figure 1(b)).

C. Distribution inference

The resolution the global equation consists in computing the probability associated to each particle P (O = occ, V = v k |ZC) and to the static field P (O = occ, V = 0|ZC) and P (O = emp|ZC). In this section, we will consider a single cell c.

By using the decomposition 1, and considering the denominator as scale factor, equation 2 can be rewritten as follows:

P (OV |ZC) ∝ P (Z|OV C) AO -1 V -1 P (A)P (O -1 V -1 |A) P (O|O -1 )P (V |OV -1 )P (C|AV ) (3)
Let us note

α(o, v) = AO -1 V -1 P (A)P (O -1 V -1 |A)
P (o|O -1 )P (v|oV -1 )P (C|Av) (4)

For null velocity (static part), this distribution can be expressed by using only the static part of the cell at previous time step p -1 occ,0 and p -1 emp,0

p -1 occ,0 = P (O -1 = occ, V -1 = 0|A = c) (5) p -1 emp,0 = P (O -1 = emp, V -1 = 0|A = c) (6)
We have

α(occ, 0) = p -1 occ,0 • (1 -ǫ) + p -1 emp,0 • ǫ (7) α(emp, 0) = p -1 occ,0 • ǫ + p -1 emp,0 • (1 -ǫ) (8)
where ǫ = P (O = occ|O -1 = emp) = P (O = emp|O -1 = occ) is given by the transition matrix T defined in the previous section.

For the dynamic part (v = 0), we first apply the motion model to the previous set of particles on the grid, according to the distribution P (V |V -1 ) :

v i = v -1 i + σ ( 9
)
x i = x -1 i + dt • v i ( 10
)
with σ ∼ N (0, Σ) is a 0 centered Gaussian noise of covariance Σ.

Then, for each particles projected in the cell c (x i ∈ c), we note a i the previous cell of the particle (x i -1 ∈ a i ) and

w -1 i = P (O -1 = occ, V -1 = v -1 i |A = a i ).
We can express α(occ, v i ) as follows:

α(occ, v i ) = w -1 i • (1 -ǫ) (11)
As empty cell are assumed to have null speed :

α(emp, v i ) = 0 (12)
To end the resolution of Equation 3, we apply the observation model :

β(occ, 0) = P (Z|O = occ, V = 0) α(occ, 0) (13) β(emp, 0) = P (Z|O = emp, V = 0) α(emp, 0)(14) β(occ, v k ) = P (Z|O = occ, V = v k ) α(occ, v k )(15)
The marginalization over the occupancy and the velocity gives the scale factor d:

d = β(occ, 0) + β(emp, 0) + k β(occ, v k ) (16)
Finally the normalized bayesian filter estimation on probability for the null velocity is :

P (O = occ, V = 0|ZC) = β(occ, 0) d (17)
and for velocity v i :

P (O = occ, V = v i |ZC) = β(occ, v i ) d (18)

D. Re-sampling

When the solving is completed, are available for each cell the evaluation of P (O = occV = 0|ZC) and a set of weighted particles {(x i , v i , w i )} representing P (O = occV = v|ZC). As for classic particle filtering, a resampling is required to sample a new population of particles for each cell from the previous one. In order to keep a constant framerate and to ease the parallelization of the process, the global number of particle remains constant. The re-sampling step adapts the local number of particles per cell and duplicates the best particles. This process is described by the following algorithm : Algorithm 1: Re-sampling 1 newP articles ← ∅ ; 2 for i ← 1 to nbP articles do 3 Draw a cell index c according to the cell weights, defined as P (occ, v = 0|ZC) ; 4 Randomly select a particle p i in this cell according to the cell particle relative weights, that is to say the distribution P (occ, v|Z, c) ; 5 newP articles ← newP articles ∪ {p i } ; 6 end 7 Normalize particle weights per cell.

E. Particles management

To this point, the issue of the velocity distribution initialization has not yet been addressed. If a new object appears in the grid, new particles are to be created. To do so, an "apparition" probability is added, corresponding to the likelihood of the antecedent to be unknown (and so with unknown properties). If we note p a this appearance probability, we can simply add pa 4 and pa 2 respectively to equation ( 7) and ( 8) and a dynamic term α(occ, v = "unknown") = pa 4 . Then, in the re-sampling process, when the "unknown" velocity is selected, the velocity is drawn from an uniform distribution.

A second enhancement is to prevent particles from following static objects. This way, to each particle weight are assigned an additional coefficient, significantly downgrading slow ones, and conversely a contribution to the static probability α(occ, 0). For each particle i, we have :

α(occ, 0) += e -||v i || 2 2σ 2 s • w -1 i • (1 -ǫ) (19) α(occ, v i ) = (1 -e -||v i || 2 2σ 2 s ) • w -1 i • (1 -ǫ) (20)
where σ s is a constant coefficient representing the static velocity contribution (for ||v i || > 3σ s the static contribution is insignificant).

F. Summary

The proposed algorithm can be summarized by the following algorithm : For the experiments, a standard road vehicle has been equipped with two multilayer Lidars Ibeo Lux under the two front lights. The horizontal field of view covered by the two lidars is of almost 180 degrees. The odometry has been computed using vehicle velocity and steering data collected from the CAN bus system. The algorithm inputs are sequences of occupancy grids computed from the two lidars. To merge the eight laser scan layers acquired by the two lidars, we use a method similar to [START_REF] Adarve | Computing Occupancy Grids from Multiple Sensors using Linear Opinion Pools[END_REF]. The presented algorithm has been implemented on the Nvidia Cuda parallel architecture in order to run on a Graphic Processing Unit (GPU). The program runs in real-time at more than 25Hz on a Nvidia Quadro 2000 GPU.

In the first experiment, we have tested a crossing scenario, the vehicle remaining static and observing a second approaching vehicle, while a third one passing from right to left. The grid dimensions are 50m by 30m with a cell size of 0.1m and the total number of particles is set to 262144, which corresponds to an average of 1.75 particles per cell. The results of our algorithm are displayed in figure 2. We can note that the occupancy of the approaching vehicle is well maintained when the crossing vehicle masks the approaching one. Further analysis of the particles localized on the approaching vehicle shows that the particles converge quickly to the right vehicle velocity (-25km/h in Y direction).

On the second experimental set (Figure 3), different urban and highway situations have been evaluated. In both cases, the number of particles has been set to 262144 and the grid resolution to 0.1m. The size of the grid lightly differs between urban and highway situation to adapt the field of view to interesting areas. On urban situations (first row) the size of the grid is 50m x 30m while on highway situation the range is a bit larger (75m x 30m). The average number of particles per cell is thus 1.75 for urban data and 1.17 on highway. The presented figure represents the occupancy grid and the average velocity of dynamic cells (red lines). A cell is considered dynamic if the probability P (occ, v = 0) > 0.5. To remove noisy data on speed estimation, only the average velocity on the cell containing a minimum number of 8 particles is displayed. We can see that all dynamic objects (pedestrians, vehicles and cycles) are well detected with an Fig. 2. Result of the algorithm on a crossing scenario. In the first row, we have a view from a front camera. In the second row is displayed the observation grid obtained from 2 lidars. The third row is the occupancy grid obtained by our algorithm. In the last row we plotted the velocity distribution for the cell marked with a red circle in 3rd row. We can notice that even when the encircled vehicle is hidden by the second car, the occupancy is maintained at the correct position. In the last row, we can see that all particles are concentrated around the right speed. accurate velocity. However some outliers are perceptible on the bottom left grid : the highway median strip is considered dynamic because of its linear geometry. As we always observe occupancy in the median strip direction, the moving hypothesis is as much probable as static hypothesis.

If we consider the memory and computation costs, the gain in classic urban and highway conditions is considerable. For the same cell resolution of 0.1m at 25Hz, the original BOF requires a velocity grid with a size of 30 × 30 = 900 samples to handle speed of 130 km/s. We saw that with our sampling method, an average of less than 2 samples per cell is enough. If we consider that each particles have a memory cost of 5 floats for the position, the speed and the probability, the global memory and computing reduction factor is about 100.

VI. CONCLUSION

In this paper we presented an efficient hybrid sampling approach to solve the Bayesian Occupancy Filter (BOF). The proposed method jointly estimates the occupancy and the velocity distributions while splitting the scene into static and dynamic cases. This static-dynamic estimation is used to accumulate the samples not just on occupied area but rather on moving objects. The memory and computing costs of the BOF, thanks to this optimization, are drastically reduced: in typical applications, the number of samples of velocity per cell has been reduced from 900 to less than 2 in average. Additionally, the accuracy can be better than in the original BOF as the velocity samples allocation is adaptive and not limited by the grid resolution.

Further works will concentrate on object based clustering to long term objects tracking. Even if reactive manoeuvres can be performed using the estimated occupancy and velocity grid, higher level perception, as lane change prediction or intersection understanding, can be valuable. Thanks to the sampling method proposed in this paper, the obtained performance and the precision gains will make it possible to use the velocity field as well as the static-dynamic classification to easily detect and track moving objects in real time.

Fig. 1 .

 1 Fig. 1. Data representations

Algorithm 2 : 5 foreach particle k ∈ c do 6 8

 2568 Global algorithm1 Apply motion model to each particle using Eq 9-10; 2 foreach cell c do 3 Compute β(occ, 0) (Eq 13); 4 Compute β(emp, 0) (Eq 14); Compute β(occ, v k ) (Eq 15); 7 end Normalize all previous values to obtain the resulting distribution P (OV |ZC) (Eq 16,17,18); 9 end 10 Re-sample particles (Algorithm 1); V. RESULTS

Fig. 3 .

 3 Fig.3. Resulting occupancy grid and velocity field on different urban and highway situations. Black cells represent the occupied space and red lines represent the average velocity vector for cell with a high dynamic probability.

CNRS, LIG name.surname@imag.fr

Inria, e-Motion name.surname@inria.fr

ACKNOWLEDGMENT

This work has been carried out as part of the IRT Nanoelec project "PERFECT", which has received financial support from the French State. The authors would like to thank Toyota Motor Europe for their collaboration and their continuous support on the Lexus car. Our thanks are given to Nicolas Turro and Jean-Franc ¸ois Cuniberto for their technical assistance in setting our experimental platform.