Vincent Autefage
email: autefage@labri.fr

Damien Magoni
email: magoni@labri.fr

NEmu: a Distributed Testbed for the Virtualization of Dynamic Fixed and Mobile Networks

Keywords: Emulation, mobile, network, testbed, virtualization

Experimentation is typically the last step before launching a network application on a large production scale. However, it is often difficult to gather enough hardware resources for experimenting with a reasonably sized distributed application inside a controlled environment. Virtualization is thus a handy technique for creating such an experimentation testbed. We propose a tool called NEmu designed to create virtual dynamic networks by using emulation for testing and evaluating prototypes of networked or distributed applications with a complete control over the network topology and link parameters. NEmu leverages system emulators such as QEMU for virtualizing the hosts and the routers. It uses vnd for virtualizing components such as links and switches. In addition, NEmu allows users to create such customized topologies with limited hardware resources and without any administrative rights. We validate NEmu by replicating two network experiments and by showing that NEmu gives results very similar to the original ones.

Introduction

Experimentation is important to realistically and accurately test and evaluate network applications. Experimentation on algorithms is usually made by simulation. This technique is available through well known software like ns [START_REF] Henderson | Network simulations with the ns-3 simulator[END_REF] or OMNeT++ [START_REF] Varga | The omnet++ discrete event simulation system[END_REF] and enables to evaluate the efficiency and the scalability of algorithms or protocols. Experimentation on a real program, i.e. implementation, is different to the extent that it is more focused on execution time, processor usage, memory consumption, network properties, etc.

It can be a difficult task when trying to experiment with a network application involving dozens of machines or more. Moreover, the mobility or the dynamics of scenarios can drastically increase the difficulty of experimentation. Using the Internet as a test bed is impractical as no parameters can be controlled. Setting up a hardware test bed is expensive and cumbersome. Furthermore, network applications can have very different ways of connecting hosts to each others and changing the network topology and network parameters of a hardware test bed is time consuming and error prone. Virtualization techniques for creating such an experimentation test bed can save resources and ease manipulations. It is a proven method for reducing the equipment and space costs as well as the energy consumption of using physical hosts [START_REF] Yamini | Cloud virtualization: A potential way to reduce global warming[END_REF].

Our solution to overcome the above hardware constraints is thus to build a test bed able to set up virtualized networks. A virtual network uses virtual machines instead of physical hosts and connects them with virtual links in order to build a virtual network topology. The virtual machines of a virtual network can be hosted on one or several physical hosts depending on the number of virtual machines needed and the resources capacities of the physical ones.

We propose a tool designed to create virtual networks for testing and evaluating prototypes of applications on the top of static, dynamic or mobile networks with a complete control over the network topology and link properties (bandwidth, delay, bit error rate, etc.) and the mobility of nodes. The goal of our tool is to enable the creation of reasonably sized virtual networks while minimizing the number of necessary physical hosts and network equipment needed. It can build host-based overlay networks by using emulators such as QEMU [START_REF] Bellard | QEMU, a fast and portable dynamic translator[END_REF]. We have called our tool NEmu which stands for Network Emulator for mobile universes because it is able to create both fixed and mobile emulated networks. It is also a tribute to the name of the QEMU software which is a powerful machine emulator heavily used by NEmu. The contributions of our work are as follows:

• A detailed description of our NEmu software which is able to manage a distributed set of virtual nodes and links for emulating any arbitrary static, dynamic or mobile network topology (Section 2).

• A detailed description of our nemo tool which implements the mobility inside NEmu and enables to create a complete autonomous mobile network by following a predefined scenario (Section 4).

• A performance validation experiment by making a comparison between NEmu and Mininet [START_REF] Lantz | A network in a laptop: Rapid prototyping for software-defined networks[END_REF] (Section 5).

• A state of the art on related and previous work targeted at networking emulation and a comparison of the features provided by NEmu with the ones offered by similar alternative virtual networking testbeds (Section 6).

This paper is an extended and revised version of our previous work published in [START_REF] Autefage | Network emulator: a network virtualization testbed for overlay experimentations[END_REF].

Description of NEmu

Overall Design

NEmu is a python program consisting of 6000 lines of code which allows to build a dynamic and distributed virtual network infrastructure. It is based on the concept of Network Virtualization Environment (NVE) introduced by N. Chowdhury and R. Boutaba in [START_REF] Chowdhury | Network virtualization: state of the art and research challenges[END_REF]. The main characteristic of a NVE is that it hosts multiple Virtual Networks (VN) that are firstly not aware of one another, and that are secondly completely independent of each other. A VN is a set of virtual nodes connected by virtual links in order to form a virtual topology. NEmu provides the possibility of creating several virtual network topologies with the central property that a VN is strictly disjoint from another in order to ensure the integrity of each VN.

Thus, NEmu integrates characteristics that are fundamental to a NVE: First, the flexibility and heterogeneity allows the user to construct a customized topology, with custom virtual nodes and virtual links. The scalability allows different virtual nodes to be hosted by different physical hosts in order to avoid limitations of a unique physical machine. The isolation decouples the different virtual networks which run on the same infrastructure. It also guaranties a strict separation between the host and the virtual networks. The stability ensures that faults in a virtual network would not affect another one. The manageability ensures that the virtual network and the physical infrastructure are completely independent. Therefore, a VN created on an infrastructure A can be deployed on another infrastructure B. The legacy support ensures that the NVE can emulate former devices and architectures. Finally, the programmability provides some optional network services to simplify the use of the virtual network (such as DHCP, DNS, etc.). It also implies that the user can develop and integrate his own additional services.

In addition, NEmu includes three important extra properties:

• The accessibility which means that NEmu can be fully executed without any administrative rights on the physical infrastructure. Indeed, the major part of public infrastructures, like universities and laboratories, does not provide administrative access to their users in order to ensure the security and the integrity of the whole domain. Therefore, the user execution would allow most people to use NEmu freely.

• The dynamicity of the topology enables node hotconnections which means that a virtual node can join or leave the topology dynamically without perturbing the overall virtual network.

• The mobility of nodes provides a way to create a self defined topology evolution through time and space.

In other words, it is possible to create an autonomous connectivity scenario.

• The community aspect of the virtual network provides the possibility for several people to supply virtual sub-networks in order to build a community network like the Internet is.

Network Elements

NEmu is a distributed virtual network environment which allows users to create arbitrary and dynamic topologies. To this end NEmu is based on different building blocks. NEmu uses virtual nodes connected by virtual links in order to create a virtual network topology. A virtual topology can be hosted by one or several physical hosts. The part of the virtual topology laying on a given physical host represents a NEmu session which is configured by the NEmu manager.

Virtual Node

A virtual node for NEmu is an emulated machine that requires a hard disk image to work. This image is typically provided as a regular file on the physical host machine. Two types of virtual nodes currently exist in NEmu:

• A VHost is a virtual host machine (i.e., end-user terminal) on which the hardware properties and the operating system can be fully configured by the user.

• A VRouter is a virtual router directly configured by NEmu and provides ready-to-use network services.

Each virtual node uses a virtual storage which can be either a real media (cdrom, hard drive, etc.), a raw file or a host directory. A raw file can be privately dedicated or shared by several other virtual nodes. A modification of a shared file by one virtual machine will affect the others which may be troublesome if the file contains the operating system. To solve the problem, NEmu uses Copy-on-Write (CoW) operations on the original file. A CoW file (also known as a sparse file) only stores the differences with its original file. The advantage, compared to a regular copy, is that the CoW file is much smaller. In addition, NEmu can use a regular directory on the physical host (without building a CoW), as a storage media in four different ways:

• by making a Sparse file which only stores the differences with its original file;

• by making a Squash file system which is a read-only raw image;

• by using a FAT16 emulated interface which enables a direct access to a host's file system;

• by using a Virtio interface [8] which also enables a direct access to a host's file system;

• by using a Network Block Device which enables a virtual node to remotely access to a block device through the real IP network [START_REF] Nbd | Network Block Device[END_REF];

• by using a SSH tunnel which enables a virtual node to remotely access to a block device through a secured connection.

As said before, a VHost needs a disk image which must be supplied by the user. This image must be prepared prior to creating the virtual network. Furthermore, one image can be used by many VHosts by using sparse files. NEmu provides a network topology visualization option by processing its topology data file through Graphviz [START_REF] Graphviz | Graph Visualization Software[END_REF].

A VRouter is directly configured by NEmu and provides several services to simplify the virtual network management: DHCP, DNS, NFS, HTTP, SSH, NTP, Netfilter, dynamic routing protocols (RIP and OSPF), and QoS management with Traffic Control [START_REF] Hubert | Linux advanced routing & traffic control[END_REF]. Moreover, it is easily possible to add some new services through a plug-in system available in NEmu. A router is running a customized image version of TinyCore which is a lightweight and highly configurable Linux distribution [START_REF] Shingledecker | TinyCore Linux[END_REF]. Such a system typically requires about ∼30 MBytes on disk and ∼100 MBytes in memory with all services running. Services provided by a VRouter are optional and can be enabled or disabled before or during runtime.

Virtual Link

A virtual link for NEmu is an emulated network connection between virtual nodes. This emulated connection can either be performed inside the machine emulator of a node (the link thus being attached to this node) or be performed by a dedicated emulation program (not running any system image in this case). Three types of virtual links currently exist in NEmu:

• A VLine is a virtual point-to-point link interconnecting two nodes.

• A VHub is a virtual multi-point hub emulating a physical Ethernet hub and interconnecting several nodes. In addition, NEmu also provides a Slirp which is a special type of link whose purpose is to provide an Internet access to the virtual node. It is an emulation of a NATed access to the real Internet by using the physical host NIC. Also, NEmu is able to interconnect a virtual NIC to a TUN/TAP kernel interface or to any UNIX socket. Figure 1 shows an example of a NEmu managed virtual network. On the left side, two VHosts are connected to a VRouter through a VSwitch by using UDP tunnels. On the right side, two VHosts are connected to the above VRouter through a VHub by using TCP tunnels. Here, virtual links are created and managed inside vnd processes.

Management of Virtual Networks

We explain below the notion of a NEmu session and we describe the physical resources needed to run a virtual network.

Session

As already said above, a NEmu session represents a complete configuration of a network topology which lays on a physical host (storages, virtual nodes configurations and links). A distributed virtual network on n physical hosts consists in n NEmu sessions at least. A session is represented by an auto-generated directory in order to be saved and re-used. A session can be saved as a sparse archive which compresses all elements and which is compatible with sparse files unlike traditional archives.

Manager

The NEmu manager is the command line user interface to manipulate a session. Sessions are independent even if they are part of the same network topology. The manager can be used in three ways :

• as a python module to be integrated in another script or program;

• as a dynamic python interpreter; • as a python script launcher.

The NEmu manager provides a remote accesses, through SSH connections, to manipulate NEmu sessions laying on other distant hosts. The python language is upgraded in order to interact with other distant sessions.

Example of a Topology

We present in Figure 2 the Python script that generates the network topology previously shown in Figure 1.

Accuracy and Scalability

NEmu does not currently provide any specific primitives or tools for measuring backend side performances or for collecting results from all the nodes in the virtual network. The measurement tools available are all the usual system tools that can be installed and run either inside the virtual machines or on the physical hosts. Typical network performance evaluation tools include: iperf, netperf, etc. The accuracy of NEmu is mainly limited by the underlying network characteristics (e.g., bandwidths, delays, error rates, etc) of the backend connections between the physical hosts. It is obvious that the virtual bandwidth set between two virtual nodes will never be able to be above the real physical bandwidth available between the physical machines hosting those virtual nodes. Finally, the scalability of NEmu is mainly limited by QEMU's requirements for the virtual machines. The needs for each VM is typically at least one dedicated core (if possible) and at least a few hundred megabytes of RAM per VM. Thus, on a single regular machine, a virtual network could scale to a dozen nodes. On a group of regular machines or on a big server or cluster, it could scale to a hundred nodes.

cow'], nics=[VNic()]) VHost('b', conf='chost', hds=[VFs('debian.img', type='cow'], nics=[VNic()]) VHost('c', conf='chost', hds=[VFs('debian.img', type='cow'], nics=[VNic()]) VHost('d', conf='chost', hds=[VFs('debian.img', type='cow'], nics=[VNic()]) # Connects nodes to links Link('router:0', 'switch:0') Link('router:1', 'hub:0') Link('a', 'switch:1') Link('b', 'switch:2') Link('c', 'hub:1') Link('d', 'hub:2') # Starts the virtual network StartNemu()

The Virtual Network Device (vnd )

This section presents our software program called vnd . It is a program which is able to emulate network devices such as a link, hub, switch or an access point from a high level point of view. This is by far not the first software able to emulate network devices but it has some unique features which may prove useful in the network virtualization domain:

• it runs as a lightweight stand-alone process and can fail without killing virtual machines,

• it can support dynamic connections and reconnections as well as disconnections and is immune to the failures of virtual machines,

• it provides many networking backends, such as the sockets API, which is available on any platform, to connect to the virtual machines,

• it can dynamically set the link properties such as bandwidth, delay, jitter and bit error rate,

• it can coarsely emulate wireless interface cards in infrastructure and ad hoc modes as well as access points.

Architecture

A vnd contains an engine and several interfaces. It can contain any number of interfaces as long as system memory is available. Interfaces can be created and destroyed at runtime. Each interface owns an input queue and an output queue. Each queue has a number of buffers which can be set at runtime. Interfaces are internally connected through the engine. Figure 3 shows the architecture of a vnd with two interfaces. Data coming in or out of a vnd can be interpreted in two ways:

• raw: data is considered as an uninterpreted flow of bytes and each buffer can contain data bytes up to its maximum size,

• Ethernet: data is considered as Ethernet frames and each buffer can contain only one frame whose size shall be less or equal than the buffer's maximum size. A vnd can be set to one of six different working modes depending on the network component that it emulates. The first four modes are typical network components which are independent from any virtual machine. The last two modes are used to emulate a Wireless Interface Card (WIC) in either infrastructure or ad hoc mode. Thus in the last two modes, the vnd is not used as a separate network component but it is used in conjunction with a virtual machine to form a mobile node. When the vnd is used as a wireless card emulator, it is connected to its virtual mobile node by a specific and unique interface called a direct interface. If the mobile node is considered using infrastructure mode (BSS or ESS), then the vnd also has another specific and unique interface called an access interface which is connected to the access point that the mobile node is currently associated with. A vnd can be set to one of the six possible modes:

1. link: each interface is directly bound to another interface, which means that any data going into the input of the first interface is forwarded to the output of the second interface in this given direction (i.e., it is one way as shown on Figure 4), 2. hub: each interface is bound to all others, which means that any data going into the input of an interface is forwarded to the output of all the other interfaces except itself as shown on Figure 5, 3. switch: any frame going into the input of an interface is forwarded to the switch engine which uses a forwarding table to determine the output interface leading to the device having the same address as the frame's destination address as shown on Figure 6, 4. access point: any frame going into the input of an interface is forwarded to the switch engine which uses a forwarding table to determine the output interface leading to the device having the same address as the frame's destination address (see Section 4), 5. infrastructure interface: any frame going into the input of the access interface is forwarded to the output of the direct interface leading to the mobile node itself, and any frame going into the input of the direct interface is forwarded to the output of the access interface leading to the access point (see Section 4), 6. ad hoc interface: any frame going into the input of any interface which is not the direct interface is forwarded to the output of the direct interface leading to the mobile node itself, and any frame going into the input of the direct interface is forwarded to all the other output interfaces except itself (see Section 4).

The last four modes only make sense when the data is interpreted as Ethernet frames as MAC addresses are needed.

In order to emulate the IEEE 802.11 protocols, a pseudo header is added to any frame coming from an access point or emulated WIC. The forwarding table is filled as in a hardware switch having auto-learning capability. When a frame is received by an interface, the vnd checks if the source MAC address is associated with this interface. If yes nothing is done, if no, the vnd stores this association in the forwarding table. When a frame is transmitted, the engine looks up the des-

Implementation

In the domain of virtualization, the term network backend is often used to designate the software part of an emulator that enables the connection of the emulator to the other emulators either on the same physical machine or on different ones. Network backends on UNIX are usually implemented with TAP interfaces, VDE [START_REF] Davoli | Vde: Virtual distributed ethernet[END_REF], sockets or slirp (which provides a full TCP/IP stack implementing a virtual NATed network).

The vnd currently provides Internet and UNIX local sockets backends as well as TAP and VDE backends. All these backends are implemented in an object called endpoint. To be useful, a network backend must be tied to a virtual network interface in a machine or a vnd . This tie is implemented in the code of emulators in more or less flexible ways. In order to support the dynamic features presented at the beginning of this section, the vnd implements the tie in a flexible way by separating the virtual interface from the endpoint. This tie can be dynamically created or destroyed by using the bind command as shown on Figure 7. Thus the failure of a network backend connection does not impact a virtual interface except for the loss of traffic. An endpoint can also be rewired to another interface if needed although data can be lost in the process.

As NEmu currently only uses QEMU for system emulation, we show on Figure 8 an example of a TCP connection between the network backends of a QEMU virtual machine and a vnd . QEMU defines a local VLAN object to associate the virtual eth0 interface to the socket backend called socket.0. The difference between the vnd bind and the QEMU VLAN is that a bind creates a bijection between an interface and an endpoint whereas a VLAN can connect several backends to the same interface thus actually acting as a simple VLAN inside the emulator (everything is broadcasted inside though).

Performances

In order to be useful and realistic, the vnd program must have acceptable performances. We have carried out several measurements to evaluate its performances and compare them to other emulators, namely QEMU and Dynamips, as they also provide socket-based network backends. The scenario was interconnecting two QEMU virtual machines via a virtual network device (line, hub and switch) emulated by either a QEMU, a Dynamips or a vnd process. All network backend connections were TCP connections made on the loop-back interface of the physical machine which was an Intel Core 2 equipped desktop PC. An FTP session was established between the two virtual machines and a 1GB file was transferred and timed to compute the bandwidth. Table 1 shows the throughput of the various possible emulations of virtual network devices. We can see that our vnd program performs at least as well as the others when emulating any device. We can also see that QEMU limits the throughput of the virtual machines at around 34MB/s.

To measure the maximum throughput of the vnd itself, we have used two netcat processes interconnected by a vnd in raw mode. The throughput amounts to 682 Mbps to be compared with the 910 Mbps obtained by a direct connection between the two nc. Thus the vnd only achieves 75% of the throughput achieved by the direct connection. This loss is due to the pipelining of the two TCP connections as well as the queueing and the processing time inside the vnd .

Finally we have also done measurements to evaluate the accuracy of the vnd bandwidth and delay parameters. Concerning the bandwidth, we can deduce from the above results that the vnd can at most emulate 100 Mbps speeds. We have observed by varying the bandwidth parameter from 100 kbps to 100 Mbps that the difference between the value of the bandwidth parameter (set on the interface of the vnd by the user) and the value of the measured bandwidth does not exceed 2%.

The Network Mobilizer (nemo)

4.1. Design NEmu can emulate mobile networks. Thus it is possible to create a virtual network topology that evolves in time. In order to manage mobility, NEmu uses a special mobility engine called nemo. nemo [START_REF] Magoni | Network Mobilizer[END_REF] is a lightweight C++ program which can generate connectivity scenarios for mobile networks. A connectivity scenario is a time stamped list of wireless link connection and disconnection events between mobile nodes. Indeed, nemo is based on a specific use of the vnd [START_REF] Magoni | Virtual Network Device[END_REF] software, which can on-thefly create virtual links having dynamically set characteristics. nemo is able to send orders to NEmu in real time which enables to emulate the changes of connectivity between mobile nodes by creating, destroying or changing the characteristics of the links at the appropriate time. nemo works behind the scene and is entirely controlled by NEmu which acts as the user interface. nemo is implemented in C++, contains around 3000 lines of code, and is using some Boost [START_REF] Dawes | Boost C++ Libraries[END_REF] libraries including the powerful asynchronous input/output library called asio. It is a lightweight program using around 1MB in RAM and it is portable thanks to Boost (on the majority of UNIX and Windows variants). nemo is composed of two parts : one part based on a simulated time scheduler and another part based on a real time scheduler. The source code is available at [START_REF] Magoni | Network Mobilizer[END_REF].

Simulated Time Scheduler

The simulated time scheduler is the heart of the simulation part of nemo. It can generate connectivity scenarios for the real time scheduler. Three steps are necessary to generate a connectivity scenario:

• generate a map;

• generate a mobility scenario on this map;

• generate a connectivity scenario from the mobility scenario. At each step, the results of the step can be saved on disk in order to be loaded at a later time to avoid recomputation. The simulated time scheduler runs the mobility scenario and at each time interval (set by the user), it computes the distances and the possible wireless connections between all the pairs of mobile nodes. The steps are illustrated on Figure 9. Being able to generate connectivity scenarios is an advantage over using a network simulator interconnecting real applications with taps, because the latter must compute the mobility at every run and this computation could be too heavy to enable the real-time execution of the applications. Up to now, nemo generate rectangular maps and purely random mobility scenarios. This is useful for carrying functional tests. nemo is also capable of importing ns-2 formatted mobility files produced by tools such as Bonnmotion [START_REF] Aschenbruck | Modelling mobility in disaster area scenarios[END_REF] providing realistic mobility models such as the Gauss-Markov Mobility Model [START_REF] Liang | Predictive distance-based mobility management for pcs networks[END_REF] or the Reference Point Group Mobility Model [START_REF] Hong | A group mobility model for ad hoc wireless networks[END_REF]. In the future, nemo will be able to load more elaborate 2D or 3D maps containing attenuation information.

The simulated time scheduler suffers from several limitations:

• it may require intensive computation of the order of O(n 2 ) (that is why it is written in C++);

• it requires the user to make a tradeoff between the temporal precision (the time interval between each connectivity evaluation), the computation time and the number of events detected.

Real Time Scheduler

The real time scheduler is the heart of the emulation part of nemo. It executes the connectivity events at their exact time stamp, set with respect to the start of the scenario. The temporal precision used in the real time scheduler is equal to the one set during the processing of the mobility scenario by the simulated time scheduler. The interaction of the real-time scheduler with NEmu is illustrated on Figure 10. It shows that NEmu plays the role of a central controller for the other processes. In a virtual mobile network, one vnd is used to emulate each wireless network interface card (WIC). Thus there is one vnd per virtual mobile node and inside it are instanciated the real network backend links (i.e., TCP or UDP tunnels). NEmu transmits the orders of the user (e.g., start, stop, etc) to nemo. When the real time scheduler is running, NEmu also recovers the connectivity events generated by nemo and retransmit them to the various vnd corresponding to the WICs of the virtual mobile nodes in order to make the network topology evolve. The real time scheduler can be paused and resumed at any moment by the user.

The real time scheduler suffers from several limitations:

• as opposed to NEmu, nemo is centralized;

• it is better to execute all the sessions and nodes on a unique physical host to avoid reducing the performances;

• the sockets used to connect the vnd introduce delays and reduce the temporal precision. The latter will be at best of the order of the millisecond.

Experimentation

We present the results of two experiments that we replicated in order to show the accuracy of NEmu. The first experiment was initially done with the Mininet containerbased emulator, the second was done with the JBotSim simulator. In both cases, we were able to accurately replicate the results with NEmu.

Mosh Experiment Replication

In order to validate the accuracy of experimentation results obtained with NEmu, we reproduce a performance benchmark of Mosh [START_REF] Winstein | Mosh: An interactive remote shell for mobile clients[END_REF]. Mosh is a remote terminal application which is more tolerant to connectivity break than SSH by using the SSP protocol and a predictive algorithm.

The experimentation consists in measuring the average keystrokes response time for Mosh and SSH. This experiment has been previously carried out on Mininet [START_REF] Lantz | A network in a laptop: Rapid prototyping for software-defined networks[END_REF], another network emulator which is well known for its degree of realism in experimental conditions [START_REF] Handigol | Reproducible network experiments using container-based emulation[END_REF].

We reproduce the exact experimentation described in a Stanford network lecture [START_REF] Aljunied | Evaluation of Mosh performance results[END_REF] and which has been officially supported by Mosh developers. In this experimentation the client is connected to a switch through an emulated 3G network, and the server through an emulated Wi-Fi network. Authors consider the following experimental network conditions:

• 3G:
packet loss rate: 0.01; -bandwidth: 1 Mbps; -delay: 450ms.

• Wi-Fi:

packet loss rate: 0.08; -bandwidth: 25 Mbps; -delay: 30ms. Thanks to our vnd program, we configure the network properties as detailed above. Original results are presented in Figure 11. Our results are illustrated in Figure 12. We can notice that both results are nearly identical. Those results imply that NEmu can offer a similar degree of realism than Mininet.

AMiRALE Experiment Replication

In order to validate the accuracy of experimentation with mobile devices performed with NEmu, we replicate performance results obtained by simulation of a multiagents system called AMiRALE [START_REF] Autefage | A mission-oriented service discovery mechanism for highly dynamic autonomous swarms of unmanned systems[END_REF]. Emulation is performed with NEmu while simulations are carried out with JBotSim [START_REF] Casteigts | Jbotsim: a tool for fast prototyping of distributed algorithms in dynamic networks[END_REF], a Java library which enables the design of low and high level communication scenarios and behaviors of heterogeneous mobile nodes.

AMiRALE is a distributed system which enables several autonomous vehicles to perform common tasks collaboratively. The application scenario consists in a team of ground robots which has to collect a given number of garbage in a park, each one being a target for the cleaning robots. We evaluate the output data rates generated by AMiRALE as a function of the number of targets to process. Each robot is specialized which means that it can only clean one kind of garbage. When a robot finds a garbage which it is not able to collect itself, it generates a new mission in order to inform other robots of the existence of this garbage. This strategy enables a robot to clean a garbage which has been discovered by another robot.

Figure 13 shows the results of our experiment as a function of the number of targets. Standard deviation values are also shown on the plots. Since all missions are broadcast without any restriction, we can calculate the theoretical data rates by multiplying the number of missions by the size of an unique mission and divide the result by the frequency of broadcasts. This result is provided by the theoretical plot. The emulation plot shows results from the NEmu experiments while the simulation plot shows results from the JBotSim simulations. This figure shows that theoretical, simulation and emulation results are very similar which implies that NEmu provides coherent performance results for this mobile devices' scenario.

Related Work

Node Emulation Systems

Currently, NEmu uses QEMU virtual machines as virtual network nodes. Despite the fact that a lot of solutions of host virtualization exist, we chose QEMU which is a generic and open source machine emulator and virtualizer [START_REF] Bellard | QEMU, a fast and portable dynamic translator[END_REF]. QEMU runs without any administrative rights and emulates a lot of various hardware architectures [START_REF] Ribiere | Emulation of obsolete hardware in open source virtualization software[END_REF]. Therefore, instantiating a QEMU virtual machine as a virtual node allows the user to configure freely its hardware and software layers which fills perfectly with the flexibility and heterogeneity properties of a NVE.

Others systems such as VMware [START_REF]VMware[END_REF] or Xen [27, 28] have better I/O performances but can only emulate x86 and x64 architectures [START_REF] Che | A synthetical performance evaluation of openvz, xen and kvm[END_REF][START_REF] Domingues | Evaluating the performance and intrusiveness of virtual machines for desktop grid computing[END_REF] which compromises the legacy support defined in Section 2. Moreover, Xen is too close to the system which means that it requires administrative rights to be configured properly.

Virtualization systems such as VirtualBox [START_REF]Oracle, VirtualBox[END_REF] and Hyper-V [START_REF]Hyper-V[END_REF] are also limited to x86 and x64 architecture emulation.

Regarding UML [START_REF] Dike | A user-mode port of the Linux kernel[END_REF], the software is now unmaintained and only can emulate Linux operating systems.

OpenVZ [START_REF] Parallels | OpenVZ Linux Containers[END_REF] can be see as the successor of UML but also only supports Linux operating systems.

LXC [START_REF] Lezcano | [END_REF] is a Linux kernel system which can encapsulate several process and a sub-file system in a virtual container. This solution cannot be consider as a real virtualization system and does not enable any hardware configuration.

Dynamips [START_REF] Fillot | Dynamips[END_REF] is an emulation system dedicated to CISCO systems. Therefore, it cannot emulate standard user machines.

Link Emulation Systems 6.2.1. Virtual Switches

NEmu uses a program called vnd in order to emulate customized virtual links. Nevertheless, other systems enable to inter-connect several virtual machines.

VDE [START_REF] Davoli | Vde: Virtual distributed ethernet[END_REF] is a virtual switch which inter-connects virtual machines through the shared memory system inside the Linux kernel. Such a system cannot be distributed on several physical machines. Moreover, VDE does not include any mechanism in order to manipulate link properties like bandwidth, delay, etc.

Open vSwitch [START_REF] Pfaff | Extending networking into the virtualization layer[END_REF] is an open source project which enables to instantiate virtual switches with a high customization of virtual links. However, this software relies on virtual network interfaces inside the Linux kernel which can only be created by a system administrator of the physical infrastructure. The accessibility defined in Section 2 would be impossible with Open vSwitch.

Vnet [START_REF] Sundararaj | Dynamic topology adaptation of virtual networks of virtual machines[END_REF] is a distributed inter-connection system which enables to link several virtual machines which lay on different physical hosts. Even if the system is distributed, it does not provide any link customization mechanism.

Click [START_REF] Kohler | The click modular router[END_REF] is a Linux kernel framework which allows to create software defined routers (i.e. at network layer 3). Therefore, this solution is not suitable for our needs.

Link Properties Manipulation

Our program vswitch includes the link properties customization in order to configure bandwidth, delay, jitter and bit error rate. Several other solutions exist in order to make this job. For instance NetEm [START_REF] Hemminger | Network emulation with netem[END_REF], which relies on the Linux kernel tools Traffic Control [START_REF] Hubert | Linux advanced routing & traffic control[END_REF], enables to manipulate same properties. However, it requires root privileges on the real infrastructure.

Dummynet [START_REF] Carbone | Dummynet revisited[END_REF] enables to create some customizable virtual links between two entities. Therefore, it cannot play the role of a multi-point device like a hub or a switch. Moreover, this solution operates directly in the kernel which is not compliant with the accessibility target.

A similar project called netpath [START_REF] Agarwal | Scalable network path emulation[END_REF] uses the Click library in order to create customize virtual links.

Another project called Trickle [START_REF] Eriksen | Trickle: A userland bandwidth shaper for unix-like systems[END_REF] can be used without any administrative rights in order to fix the maximum date rates for a process. However, it can only fix this property for the entire process. Thus our virtual switch is much more configurable.

Network Virtualization Environment

Dynagen [START_REF] Anuzelli | Dynagen[END_REF] is for Dynamips, the equivalent of NEmu for QEMU. Dynagen manages fleet of Dynamips machines and their inter-connections. However, the dynamicity of the topology is strongly limited, adding network services is quite impossible and there is not any community aspect.

GNS [START_REF]Graphical Network Simulator[END_REF] is an open source software which allows to build a virtualized network topology with Dynamips, Vir-tualBox and QEMU virtual machines. However, it does not provide the possibility to build a community network and adding network services is as complicated as Dynagen. Finally GNS is hardly usable without any graphical interface making difficult the creation of a complex network.

Velnet [START_REF] Kneale | Velnet: virtual environment for learning networking[END_REF] is a virtual environment dedicated to teaching which uses VMware virtual machines. The complete topology can only run on a single host which implies strong limitations on the size of the virtual network.

ModelNet [START_REF] Vahdat | Scalability and accuracy in a large-scale network emulator[END_REF] emulates a distributed virtual network but this one remains static at runtime. Thus, the dynamicity is not ensured with ModelNet. Further, the management of this system is fully centralized on an unique physical machine which disables the community aspect.

Vagrant [START_REF] Hashimoto | Vagrant[END_REF] uses VirtualBox virtual machines in order to emulate virtual network. The topology is hosted on a single physical machine and remains static at runtime. Finally, the inter-connections are built inside the host kernel making a flat network, i.e. a network which not relies on standards ways of addressing and routing.

VINI [START_REF] Bavier | In vini veritas: realistic and controlled network experimentation[END_REF] is a distributed virtual network which overhangs the PlanetLab testbed [START_REF] Bavier | Operating system support for planetary-scale network services[END_REF] which is an international distributed cluster system. VINI uses UML virtual machines which strongly limits operating systems for nodes. Moreover, connections between nodes are made with virtual networks interfaces inside the kernel of the physical machine which makes the configuration impossible without administrative rights.

Violin [START_REF] Jiang | Violin: Virtual internetworking on overlay infrastructure[END_REF] is similar to VINI but provides some virtual routers which hosted different services like NEmu. However the use of UML and the need of an existing overlay limits the use scope of this solution.

NetKit [START_REF] Pizzonia | Netkit: easy emulation of complex networks on inexpensive hardware[END_REF] relies also on UML and VDE switches which do not require any administrative rights. Such a system cannot be distributed.

Marionnet [START_REF] Lodo | Marionnet[END_REF] is a virtual environment dedicated to teaching. It provides several network services and the community aspect but relies on UML.

Virconel [START_REF] Benchaib | Virconel: A network virtualizer[END_REF] uses OpenVZ virtual machines which also strongly limits operating systems for nodes. Moreover, The topology is static during runtime and the interconnections between virtual machines are made in the host kernel which requires special rights on the physical system.

VNUML [START_REF] Dit | [END_REF] is a static virtual system relying on UML and which requires administrative rights.

VNX [START_REF] Dit | [END_REF] is the successor of VNUML is a compatible with other virtualization systems. However, as VNUML, it requires administrative rights and does not include any link property mechanism.

Cloonix [START_REF] Perrier | Cloonix[END_REF] is a dynamic virtual network environment. Nevertheless, it does not include link property mechanism.

Mininet [START_REF] Lantz | A network in a laptop: Rapid prototyping for software-defined networks[END_REF] is a Container-Based Emulator which allows to create a custom and dynamic topology on a unique physical host. The second version of this system is highly demanding about fairness of experimentation conditions [START_REF] Handigol | Reproducible network experiments using container-based emulation[END_REF].

CORE [START_REF] Ahrenholz | Core: A realtime network emulator[END_REF] is a graphic tool which enables to emulate virtual mobile networks. This system relies on a framework called IMUNES [START_REF] Puljiz | IMUNES[END_REF] which runs over the FreeBSD [START_REF] Freebsd | FreeBSD[END_REF] operating system. Nodes and links are managed inside the operating system kernel which implies strong limitations in terms of flexibility.

MobiEmu simulates mobile networks through ns3 for the mobility and LXC containers for nodes. This tool does not enable NVE possibilities.

OpenNebula [START_REF] Labs | OpenNebula[END_REF] provides a powerful solution to manage a virtual cloud on a wide physical infrastructure with an important number of nodes. OpenNebula manages the whole cloud domain from a single access point. Storage medias are centralized and are accessible through the network which implies the use of a NAS or NFS.

NET [START_REF] Maier | Experiences with node virtualization for scalable network emulation[END_REF] is a powerful hardware-based infrastructure which allows to perform realistic experimentation on mobile networks. However, this solution uses real network inter-connection devices (i.e. switches, etc.) in order to build the virtual network.

PdP [START_REF] Liao | Network virtualization substrate with parallelized data plane[END_REF] is partial NVE implementation which focuses itself on flexibility, isolation, high-speed data rates and low cost. It uses OS level virtualization nodes such as OpenVZ.

Onelab2 [START_REF] Carbone | An emulation tool for planetlab[END_REF] is a well known emulation tool over Plan-etLab. It also relies on DummyNet which strongly limits the flexibility of this solution.

IP-TNE [START_REF] Simmonds | Towards scalable network emulation[END_REF] is an original solution which enables hosts and real network to interact with a virtual mobile network. It is not really an emulation solution since it provides only the mobility properties of nodes and not the real node virtualization.

Research platforms such as PlanetLab [START_REF] Bavier | Operating system support for planetary-scale network services[END_REF], GENI [66] and FEDERICA [START_REF] Garr | [END_REF] supply virtual infrastructure built on the top of slices of third parties owned hardware. This approach leads to the concept of Testbed as a Service (TaaS), exemplified by FanTaaStic [START_REF] Willner | Fantaastic: Sustainable management of future internet testbed federations[END_REF]. Federations of testbeds have also been recently emerging, such as the EU-driven OpenLab federation [START_REF] Fdida | The express sdn experiment in the openlab large scale shared experimental facility[END_REF] as well as the OneLab federation [START_REF] Baron | Onelab: Major computer networking testbeds open to the ieee infocom community[END_REF], managed by UPMC. In all these cases, the user needs a specific account, must comply to specific us-age policies and has to use the tools, services and APIs of these testbeds.

Table 2 exhibits several properties of those previous solutions compared to NEmu. We see that NEmu can cover all usages (test and proof, performance evaluation as well as learn and teach). It can achieve a high realism as a research tool by managing dynamic virtual networks and by being able to be distributed over several physical machines. Furthermore, it can be easily used and deployed as no special rights are required on the physical machines. The creation of a complex network is facilitate by the important number of available network services and the easy way to add another ones. Finally, it offers a new feature called community aspect that enables several users to merge their virtual networks together in order to build a single larger network.

NVE+ compliant Dynagen • • • • • • • • • • • GNS3 • • • • • • • • • • • Velnet • • • • • • • • • • • ModelNet • • • • • • • • • • • Vagrant • • • • • • • • • • • VINI • • • • • • • • • • • Violin • • • • • • • • • • • NetKit • • • • • • • • • • • Marionnet • • • • • • • • • • • Virconel • • • • • • • • • • • VNUML • • • • • • • • • • • VNX • • • • • • • • • • • Cloonix • • • • • • • • • • • Mininet • • • • • • • • • • • CORE • • • • • • • • • • • MobiEmu • • • • • • • • • • • NET • • • • • • • • • • • PdP • • • • • • • • • • • Onlab2 • • • • • • • • • • • NEmu • • • • • • • • • • • • Yes • No

Conclusion

NEmu and its associated programs vnd and nemo enable the creation and management of dynamic, heterogeneous and mobile virtual networks. They provide a good compromise between ease of use, low cost and realism. Such virtual networks can be distributed over several physical hosts and be controlled without any administrative rights. They can also evolve in real time with nemo by following a pre-calculated connectivity scenario.

We have compared NEmu to Mininet with regard to the Mosh experiment and have shown that the results are nearly identical thus demonstrating that NEmu can be used for similar purposes. The advantage being that it can be distributed over several physical machines unlike Mininet. This is important as NEmu uses full system emulation and not container based emulation. We have compared NEmu to JBotSim with regard to the AMi-RALE experiment and the obtained results are similar, thus validating its use for virtual mobile devices' experimentation. NEmu can therefore overcome the cost of a physical testbed infrastructure while enabling the evaluation of real applications thanks to its low level emulation of network and system components. NEmu can also emulate mobile ad hoc networks which, as far as we know, is a unique feature among network emulators.

As envisioned by Conti et al. [START_REF] Conti | Research challenges towards the future internet[END_REF], the Internet of the future will be polymorphic, i.e., it will allow various specific networking environments to coexist, thanks to virtualization and federation. The extended concepts of NVE presented in this paper clearly embrace those two properties. Our software is a first step towards building such virtual networks. Its current use is mainly for research experimentation and teaching but its long term use could include production. The variety of supported backends could indeed lead our software to provide new network services.

Several next steps are already planned for our future work on NEmu. They consist in the following tasks by order of priority:

• the integration of migration capabilities for virtual machines in order to enable load balancing;

• the integration of new services inside the virtual router;

• implementation of more sophisticated map generation algorithms;

• the improvement of the accuracy of the vnd .

Figure 2 :Figure 3 :

 23 Figure 2: A example of a topology script written for NEmu.

Figure 4 :

 4 Figure 4: Link mode.

Figure 6 :

 6 Figure 6: Switch mode.

Figure 7 :

 7 Figure 7: Bind between an emulated interface and a network backend in a vnd.

Figure 8 :

 8 Figure 8: TCP connection between the network backends of a QEMU and a vnd.

Figure 9 :

 9 Figure 9: Generation of connectivity scenarios with nemo.

Figure 10 :

 10 Figure 10: Emulation of virtual mobile networks with nemo.

Figure 11 :Figure 12 :

 1112 Figure 11: Original Mosh results obtained by mininet.

Figure 13 :

 13 Figure 13: AMiRALE results obtained by JBotSim and NEmu.

  tination MAC address of the frame in the forwarding table and forward the frame to the interface associated with that address. Currently, the forwarding table does not remove entries depending on a given lifetime and thus the table must be manually cleared if needed. The vnd supports port-based VLANs in hub and switch modes. The vnd does not yet implement the Spanning Tree Protocol, thus it is up to the user to avoid making loops in the topology of the virtual network.

Table 1 :

 1 Throughput of the switch emulators

	Network	Emulation	Measured
	Component Program	Throughput
	Baseline	nc to nc link	910 Mbps
		vnd (raw connections)	682 Mbps
	VLine	QEMU to QEMU direct link	272 Mbps
		vnd (link mode)	240 Mbps
	VHub	QEMU hub	160 Mbps
		vnd (hub mode)	240 Mbps
	VSwitch	Dynamips switch	12 Mbps
		vnd (switch mode)	156 Mbps

Table 2 :

 2 Comparison of network virtualization tools.

	Test and proof	Evaluation	Teaching	Dynamic	Distributed	Mobility	Community aspect	Network services	Regular privileges	Configurable links


Tristan Cazenave
email: cazenave@lamsade.dauphine.fr

Generalized Rapid Action Value Estimation

Monte Carlo Tree Search (MCTS) is the state of the art algorithm for many games including the game of Go and General Game Playing (GGP). The standard algorithm for MCTS is Upper Confidence bounds applied to Trees (UCT). For games such as Go a big improvement over UCT is the Rapid Action Value Estimation (RAVE) heuristic. We propose to generalize the RAVE heuristic so as to have more accurate estimates near the leaves. We test the resulting algorithm named GRAVE for Atarigo, Knighthrough, Domineering and Go.

Introduction

Monte Carlo Tree Search (MCTS) is a general search algorithm that was initially designed for the game of Go [START_REF] Coulom | Efficient selectivity and backup operators in Monte-Carlo tree search[END_REF]. The most popular MCTS algorithm is Upper Confidence bounds applied to Trees (UCT) [START_REF] Kocsis | [END_REF]. All modern computer Go programs use MCTS. It has increased the level of Go programs up to the level of the strongest amateur players. Rapid Action Value Estimation (RAVE) [START_REF] Gelly | Combining online and offline knowledge in UCT[END_REF]2011] is commonly used in Go programs as it is a simple and powerful heuristic.

MCTS and RAVE are also used in MoHex the best Hex playing program [Arneson et al., 2010]. Adding the RAVE heuristic to MoHex produces a 181 Elo strength gain.

Another successful application of MCTS is General Game Playing (GGP). The goal of GGP is to play games unknown in advance and to design algorithms able to play well at any game. An international GGP competition is organized every year at AAAI [START_REF] Genesereth | [END_REF]. The best GGP programs use MCTS [START_REF] Finnsson | Simulation-based approach to general game playing[END_REF][START_REF] Méhat | Jean Méhat and Tristan Cazenave. A parallel general game player[END_REF]. In this paper we propose an algorithm that can be applied to many games without domain specific knowledge. Hence it is of interest to GGP engines.

MCTS can also be applied to other problems than games [START_REF] Browne | [END_REF]. Examples of non-games applications are Security, Mixed Integer Programming, Traveling Salesman Problem, Physics Simulations, Function Approximation, Constraint Problems, Mathematical Expressions, Planning and Scheduling.

The paper is organized in three remaining sections: section two presents related works for games, MCTS and RAVE, sec-tion three details the GRAVE algorithm and section four gives experimental results for various numbers of playouts and various sizes of Atarigo, Knightthrough, Domineering and Go.

Related Work

UCT is the standard MCTS algorithm. It uses the mean of the previous random playouts to guide the beginning of the current playouts. There is a balance between exploration and exploitation when choosing the next move to try at the beginning of a playout. Exploitation tends to choose the move with the best mean, while exploration tends to try alternative and less explored moves to see if they can become better. The principle of UCT is optimism in face of uncertainty. It chooses the move with the UCB formula, m is a possible move:

argmax m (mean m + c × log(playouts)
playoutsm )

The c exploration parameter has to be tuned for each problem. Low values encourage exploitation while high values encourage exploration.

The All Moves As First heuristic (AMAF) [START_REF] Bouzy | Monte-Carlo Go developments[END_REF] is a heuristic that was used in Gobble, the first Monte Carlo Go program [Brügmann, 1993]. It consists in updating the statistics of the moves of a position with the result of a playout, taking into account all the moves that were played in the playout and not only the first one.

RAVE [START_REF] Gelly | Combining online and offline knowledge in UCT[END_REF]2011] is an improvement of UCT that was originally designed for the game of Go and that works for multiple games. It consists in memorizing in every node of the tree the statistics for all possible moves even if they are not yet tried in the node. When a playout is over, the statistics of all the nodes it has traversed are updated with all the moves of the playout. Another way to describe it is that the AMAF value of each possible move is recorded in a node. When there are few playouts, the AMAF value is used to choose a move. When the number of playouts increases the weight of the mean increases and the weight of AMAF decreases. The formula to choose the move can be stated with a weight β m , p m is the number of playouts starting with move m and pAM AF m is the number of playouts containing move m:

β m ← pAM AFm pAM AFm+pm+bias×pAM AFm×pm argmax m ((1.0 -β m ) × mean m + β m × AM AF m )
In their paper [START_REF] Gelly | Monte-Carlo tree search and rapid action value estimation in computer Go[END_REF]] Sylvain Gelly and David Silver state: "In principle it is also possible to incorporate the AMAF values, from ancestor subtrees. However, in our experiments, combining ancestor AMAF values did not appear to confer any advantage.". On the contrary, we found that it can be useful.

RAVE is used in many computer Go programs. Examples of such programs are Mogo [Lee et al., 2009] and Fuego [Enzenberger et al., 2010].

RAVE has also been used for GGP in CadiaPlayer [START_REF] Finnsson | Learning simulation control in general gameplaying agents[END_REF]. CadiaPlayer with RAVE is much stronger at Breakthrough, Checkers and Othello than the usual MCTS. On the contrary it is slightly weaker with RAVE at Skirmish.

An alternative to RAVE for Go programs is to use learned patterns and progressive widening [START_REF] Coulom | Rémi Coulom. Computing elo ratings of move patterns in the game of go[END_REF]Ikeda and Viennot, 2014]. The principle is to learn a weight for each pattern. This weight can be used in playouts to bias the policy and in the tree to select promising moves. Progressive widening starts with only the best ranked move as a possible move in a node and then increases the number of moves that can be tried as the number of playouts of the node also increases. It is related to GRAVE since it only tries the most promising moves when there are few playouts.

In Mogo, an improvement of RAVE is to start with heuristic values for moves sampled only a few times [Lee et al., 2009]. The heuristic value is computed after patterns that match around the move. The score of a move is calculated according to three weights, α, β and γ. The weight for the mean of the playouts is α, it starts at zero for few playouts and then increases as more playouts are played. The weight for the AMAF mean is β. It starts at zero then increases to 1 with more playouts and then decreases to zero with even more playouts. The last weight is γ, it starts with a value greater than 1 and then decreases as more playouts occur.

The GRAVE algorithm also uses an estimate different from the node's AMAF mean for moves that have only few playouts. But on the contrary of the γ weight associated to a valued pattern it does not use domain specific and learned knowledge. It is more simple and more general.

Another improvement of Mogo is to use the RAVE values of moves during the playouts [Rimmel et al., 2011]. This improvement gives good results for the game of Havannah and for the game of Go. The algorithm descends the tree using the usual RAVE algorithm and when it is outside the tree it uses the RAVE values of the last node with at least 50 simulations. During the playout it chooses one of the k moves with the best RAVE values with a given probability. Otherwise it uses the usual playout policy.

GRAVE

RAVE computes an estimate of each possible move when only a few playouts have been played. The principle of GRAVE is to use AMAF values of a state higher up in the tree than the current state. There is a balance between the accuracy of an estimate and the accordance to the current state of the estimate. A state upper in the tree has better accuracy since it has more associated playouts. However the statistics are about a different state some moves before and are less to the point for the lower state in the tree than the statistics of lower states. GRAVE principle is to only use statistics that were calculated with more than a given number of playouts. We take as a reference state the closest ancestor state that has more playouts than a given ref constant. The reference state can be the current state if the number of playouts of the current state is greater than ref .

The GRAVE algorithm is given in algorithm 1. The algorithm is close to the RAVE algorithm. The main difference is that it uses a tref parameter that contains the transposition table entry of the last node with more than ref playouts. The ref constant is to be tuned as well as the bias. This tref entry is used to get the RAVE statistics instead of the usual t entry. If the number of playouts of a node is greater than ref then tref is equal to t and the algorithm behaves as usual RAVE. If the number of playouts of the current node is lower than ref then the algorithm uses the last entry along the path to the node that has a number of playouts greater than ref . This entry is named tref and is used to compute the AMAF values at the current node.

Instead of only updating the AMAF statistics for the color and the moves of the node, GRAVE updates statistics for all possible moves by both colors at every node.

GRAVE is a generalization of RAVE since GRAVE with ref equals to zero is RAVE.

We will now detail algorithm 1. It starts with calculating the possible moves that will be used later to find the most promising move. If the board is terminal, the game is over and the score is returned. The algorithm does not explicitly represent the tree. Instead it uses a transposition table to remember all the visited states and stores in each entry of the transposition table the number of wins of each move, the number of playouts of each move, the number of AMAF wins for all possible moves in the entire game and not only in the state, that is including the opponent player moves, the number of AMAF playouts for all possible moves in the entire game. These values stored in the variables w, p, wa, pa are used to calculate the β m parameter as well as the AM AF and mean values of a move. The usual RAVE formula is then used to calculate the value of a move. The move with the best value is played and the algorithm is recursively called. The recursion ends when reaching a state that is not in the transposition table. In this case the state is added in the transposition table, a playout is played and the transposition table entry is updated with the result of the playout.

The only difference to the usual RAVE algorithm is the tref parameter and the ref constant. Instead of using the usual t entry of the transposition table in order to calculate the AMAF value of a move, the algorithm calculates the AMAF value using the tref entry. The tref entry is updated using the condition t.

Experimental Results

In order to test GRAVE we have used the following method: the RAVE bias is first tuned playing different RAVE bias against UCT with a 0.4 exploration parameter (the exploration parameter used for GGP), then the GRAVE bias as well as the ref constant are tuned against the tuned RAVE. The resulting GRAVE algorithm is then tested against RAVE with different bias to make sure there is no over-fitting nor a miss of a good RAVE bias and that GRAVE performs well against all possible RAVE. In order to tune both RAVE and GRAVE we test as bias all the powers of 10 between 10 -1 and 10

Atarigo 8 × 8

Atarigo is a simplification of the game of Go. The winner of a game is the first player to capture a string of stones.

Atarigo has been solved up to size 6 × 6 with threat based algorithms [Cazenave, 2003;[START_REF] Boissac | De nouvelles heuristiques de recherche appliquées à la résolution d'atarigo[END_REF]. In this paper we use the 8 × 8 board size.

All algorithms use 10,000 playouts. We first tuned the RAVE bias against UCT. Results are given in table 1. The best bias is 10 -7 and it wins 94.2 % of the games against UCT.

We then tuned GRAVE against the best RAVE. Results are given in table 2. The best GRAVE has a ref equals to 50 and a bias of 10 -10 , it wins 88.4 % of the games against RAVE.

When playing GRAVE with ref equals to 50 and bias equals to 10 -10 against all RAVE bias, the worst score obtained by GRAVE was 85.2 % against a RAVE bias of 10 -4 .

Atarigo 19 × 19

We played RAVE with 1,000 playouts and with various bias against UCT with 1,000 playouts. The results are in table 3. The best result is 72.4 % for a bias of 0.001.

We then played GRAVE with different bias and ref against the best RAVE. The results are in table 4. The best GRAVE wins 78.2 % with ref equals to fifty and a 10 -5 bias.

Knightthrough 8 × 8

Knightthrough is played on a 8 × 8 chess board. The initial position has two rows of white knights on the bottom and two rows of black knights on the top. Players alternate moving a knight as in chess except that the knight can only go forward and not backward. Captures can occur as in chess. The first player to move a knight on the last row of the opposite side has won. Knightthrough is a game from the GGP competitions, it is derived from Breakthrough that is a similar game with pawns.

Table 5 gives the results of RAVE against UCT. Each player is allocated 1,000 playouts at each move. The best bias is 0.01 as it wins 69.4 % against UCT.

Table 6 gives the results for GRAVE with different ref values against RAVE with a bias of 0.01. They both use 1,000 playouts for each move. GRAVE with ref equals to 50 and a bias of 10 -4 wins 67.8 % against RAVE.

Table 7 gives the results of RAVE against UCT for different bias and 10,000 playouts each. The best bias is 10 -10 as it wins 56.2 % against UCT.

Table 8 gives the results for GRAVE with different ref values against RAVE with a bias of 10 -10 . Each player uses 10,000 playouts per move. The best GRAVE player with ref equals to 50 and a bias of 0.001 wins 67.2 % against the tuned RAVE.

Domineering 8 × 8

Domineering is a two player combinatorial game usually played on an 8×8 board. It consists in playing 2×1 dominoes on the board. The first player put the dominoes vertically and the second player put them horizontally. If a player cannot play anymore, he loses the game.

Domineering was invented by Göran Andersson [Gardner, 1974]. As it decomposes in independent parts it was studied [START_REF] Lachmann | [END_REF]. Boards up to 10 × 10 were solved using αβ search [START_REF] Bullock | Domineering: Solving large combinatorial search spaces[END_REF]. Recently a knowledge based method was proposed that can solve large rectangular boards without any search [START_REF] Uiterwijk | Jos WHM Uiterwijk. Perfectly solving domineering boards[END_REF].

In order to tune the RAVE bias we played RAVE against UCT with 10,000 playouts. The best RAVE bias is 10 -3 which wins 72.6 % of the time against UCT as can be seen in table 9.

We then played different GRAVE algorithms against the tuned RAVE. The results are given in table 10. With ref equals to 25 and a bias of 10 -5 , GRAVE wins 62.4 % of the time against the tuned RAVE.

When playing GRAVE with ref equals to 25 and bias equals to 10 -5 against all RAVE bias, the worst score obtained by GRAVE was 58.2 % against a RAVE bias of 10 -4 .

Domineering 19 × 19

In order to tune the RAVE bias for Domineering 19 × 19 we ran the experiment RAVE with 1,000 playouts against UCT with 1,000 playouts, but RAVE won all of its games with all bias. So we ran another experiment: RAVE with 1,000 playouts against UCT with 10,000 playouts. The results are given in table 11. The best score is 63.8 % obtained for a bias of 10 -7 .

We tuned GRAVE against the best RAVE algorithm. Results are given in table 12. The best score is 56.4 % with ref equals to 100 and a bias of 10 -6 .

Go 9 × 9

Go is an ancient oriental game of strategy that originated in China thousands of years ago [START_REF] Bouzy | Computer Go: An AI oriented survey[END_REF]Müller, 2002]. It is usually played on a 19 × 19 grid. Players alternate playing black and white stones on the intersections of the grid. The goal of the game using Chinese rules is to have more stones on the board than the opponent at the end of the game. There is a capture rule: when a string of stones of the same color is surrounded by stones of the opposing color, the surrounded string is removed from the board. There are a lot of Go players in China, Japan and Korea and hundreds of professional players. Go is the last of the popular board games that is better played by humans than by computers. The best computer Go players are currently four stones behind the best Go players.

MCTS has been very successful for the game of Go. The original RAVE algorithm was designed for computer Go [START_REF] Gelly | Combining online and offline knowledge in UCT[END_REF].

This section deals with Go 9 × 9, the next section is about Go 19 × 19.

The playout policy we used in our experiments for Go 9×9 and Go 19 × 19 is Mogo style playouts with patterns [Gelly et al., 2006].

We have first tuned RAVE with 1,000 playouts against UCT with 1,000 playouts. The results are given in table 13. The best bias is 10 -7 and it wins 89.6 % of the games against UCT.

We have then played GRAVE against the tuned RAVE. The results are given in table 14. The best GRAVE configuration is ref equals to 100 and a bias of 10 -6 . It wins 66.0 % against the tuned RAVE.

We repeated the experiments for 10,000 playouts. The RAVE bias was tuned against UCT. The results are in table 15. The best bias for RAVE is 10 -4 and it wins 73.2 % against

Go 19 × 19

When tuning the RAVE bias against UCT with 1,000 playouts, all results were greater than 98 %. We therefore tuned RAVE with 1,000 playouts against GRAVE with 1,000 playouts, ref equals to 400 and a bias of 10 -5 . The worst result for GRAVE was 72.2 % against a RAVE bias of 10 -5 . We then tuned GRAVE against RAVE with a bias of 10 -5 . The results are given in table 17. The best result is 81.8 % with ref equals to 100 and a bias of 10 -9 .

The best RAVE bias for 1,000 playouts was reused to tune GRAVE with 10,000 playouts against RAVE with 10,000 playouts. We only tuned GRAVE with ref equals to 100. The best result for GRAVE was 73.2 % with a bias of 10 -12 . We then played GRAVE with a bias of 10 -12 and ref equals to 100 against all RAVE with bias between 10 -1 and 10 -12 . The worst result for GRAVE was 62.4 % against the 10 -7 bias.

Three Color Go 9 × 9

Multicolor Go is a variation of the game of Go which is played with more than two players. For example it is possible to add a third color, say red, and to play with stones of three different colors [Cazenave, 2008]. The rules are the same as in the Chinese version of the game. At the end of the game when all three players have passed, the score for a given color is the number of stones of the color on the board In order to test an algorithm we make it play the six possible combinations of colors against two other algorithms, one hundred times. This results in six hundreds games played. The percentage of wins for algorithms that are close in strength is therefore close to 33.3 %. An algorithm scoring 50.0 % is already much better than the two other algorithms.

The motivation for testing GRAVE at Three Color Go is that playouts contain less moves of a given color than in usual two player Go. The AMAF statistics take more playouts to be accurate than in two player Go. So GRAVE which uses more accurate statistics may perform better.

Mogo style playouts do not work well for multicolor Go, so for these experiments we use a uniform random playout policy without patterns.

We tuned the RAVE bias with 1,000 playouts against two UCT players each with 1,000 playouts. The results are given in table 18. The best RAVE bias is 0.001 with 70.83 % wins. This is a clear win for RAVE since it is well above the standard score of 33.33 %.

We played GRAVE against two tuned RAVE with a bias of 0.001. The results are given in Table 19. The best GRAVE has a ref equals to 100 and a bias of 10 -5 and it wins 57.17 % against a tuned RAVE.

Three Color Go 19 × 19

For Three Color Go on a 19 × 19 board, RAVE is much better than UCT when they both use 1,000 playouts. We therefore did the same as in Go 19 × 19 and tuned RAVE with 1,000 playouts against two players using GRAVE with 1,000 playouts, ref equals to 400 and a bias of 10 -5 . The best result for RAVE was 18.5 % with a bias of 10 -9 . 10 -5 10 -9 10 -11 56.00 % 57.17 % 54.50 % 55.17 %

Conclusion

We have presented a generalization of RAVE named GRAVE. It uses the AMAF values of an ancestor node when the number of playouts is too low to have meaningful AMAF statistics. It uses a threshold on the number of playouts of the node to decide whether to use the current node's statistics or the ancestor node's statistics. It is a generalization of RAVE since GRAVE with a threshold of zero is RAVE.

GRAVE is better than RAVE and UCT for Atarigo, Knightthrough, Domineering and Go.

For Atarigo 8 × 8 the results show that GRAVE is a large improvement over RAVE since GRAVE wins 85.2 % against RAVE when they both use 10,000 playouts. For Atarigo 19 × 19 and 1,000 playouts GRAVE wins 78.2 % For Knightthrough 8 × 8 GRAVE with 1,000 playouts wins 67.8 % against RAVE with 1,000 playouts. GRAVE with 10,000 playouts wins 67.2 % against RAVE with 10,000 playouts. RAVE is a large improvement over UCT for Knightthrough 8×8 and GRAVE is a large improvement over RAVE.

For Domineering 8 × 8 GRAVE with 10,000 playouts wins 62.4 % against RAVE with 10,000 playouts. For Domineering 19 × 19 GRAVE with 1,000 playouts wins 56.4 % against RAVE with 1,000 playouts.

For Go 9 × 9 GRAVE with 1,000 playouts wins 66.0 % against RAVE with 1,000 playouts. For 10,000 playouts it wins 54.4 %. For Go 19 × 19 GRAVE with 10,000 playouts wins 62.4 % against RAVE with 10,000 playouts.

For Three Color Go 9 × 9, GRAVE wins 57.17 % against a tuned RAVE. For Three Color Go 19 × 19, RAVE only wins 18.5 % against an unoptimized GRAVE.

GRAVE is a simple and generic improvement over RAVE. It works for at least four games without game specific knowledge.

  playouts > ref . It means that tref contains the last entry in the recursive calls with a number of playouts greater than ref .

	Algorithm 1 The GRAVE algorithm
	GRAVE (board, tref )
	moves ← possible moves
	if board is terminal then
	return score(board)
	end if
	t ← entry of board in the transposition table
	if t exists then
	if t.playouts > ref then
	tref ← t
	end if
	bestV alue ← -∞
	for m in moves do
	w ← t.wins[m]
	p ← t.playouts[m]
	wa ← tref.winsAM AF [m]
	pa ← tref.playoutsAM AF [m] pa β m ← pa+p+bias×pa×p AM AF ← wa pa mean ← w
	end if
	end for
	play(board, bestM ove)
	res ← GRAV E(board, tref )
	update t with res
	else
	t ← new entry of board in the transposition table
	res ← playout(player, board)
	update t with res
	end if
	return res

p value ← (1.0 -β m ) × mean + β m × AM AF if value > bestV alue then bestV alue ← value bestM ove ← m

Table 1 :

 1 -15 . Additionally the ref constants tested for GRAVE are 25, 50, 100, 200 and 400. Tuning the RAVE bias against UCT at Atarigo 8 × 8 Go 9 × 9, Go 19 × 19 and three color Go. The algorithms are tested for 1,000 and 10,000 playouts. For twoplayer games each result is the average winning rate over 500 games, 250 playing first and 250 playing second.

	with 10,000 playouts.
	bias	0.1	0.01	0.001	10 -4	10 -5
		74.4 % 91.2 % 90.6 % 92.8 % 91.4 %
	bias	10 -6	10 -7	10 -8	10 -9	10 -10
		92.8 % 94.2 % 91.4 % 91.6 % 91.0 %
	bias	10 -11	10 -12	10 -13	10 -14	10 -15
		93.8 % 92.2 % 92.2 % 92.2 % 92.2 %
	Table 2: GRAVE against RAVE at Atarigo 8 × 8 with 10,000
	playouts.
		ref	25	50	100
		bias	10 -8	10 -10	10 -3
			86.2 % 88.4 % 87.8 %
	19 × 19,

The tested games are Atarigo 8 × 8, Atarigo 19 × 19, Knightthrough 8 × 8, Domineering 8 × 8, Domineering

Table 3 :

 3 Tuning the RAVE bias against UCT at Atarigo 19 ×

	19 with 1,000 playouts.
	bias	0.1	0.01	0.001	10 -4	10 -5
		63.6 % 67.6 % 72.4 % 73.2 % 68.6 %
	bias	10 -6	10 -7	10 -8	10 -9	10 -10
		67.8 % 66.8 % 67.0 % 67.8 % 70.4 %
	bias	10 -11	10 -12	10 -13	10 -14	10 -15
		70.4 % 70.4 % 70.4 % 70.4 % 70.4 %

Table 6

 6

	: GRAVE against RAVE at Knightthrough 8 × 8 with
	1,000 playouts.
	ref	25	50	100
	bias	0.01	10 -4	0.01
		62.0 % 67.8 % 63.0 %

Table 7 :

 7 Tuning the RAVE bias against UCT at Knightthrough 8 × 8 with 10,000 playouts.

	bias	0.1	0.01	0.001	10 -4	10 -5
		38.0 % 55.2 % 52.6 % 53.8 % 53.8 %
	bias	10 -6	10 -7	10 -8	10 -9	10 -10
		49.4 % 52.8 % 53.6 % 53.6 % 56.2 %
	bias	10 -11	10 -12	10 -13	10 -14	10 -15
		52.0 % 52.0 % 52.0 % 52.0 % 52.0 %
	Table 8: GRAVE against RAVE at Knightthrough 8 × 8 with
	10,000 playouts.
		ref	25	50	100
		bias	10 -9	0.001	0.001
			65.8 % 67.2 % 65.4 %
	by the combinatorial games community. They solved it for
	small boards

Table 9 :

 9 Tuning the RAVE bias against UCT at Domineering

	8 × 8 with 10,000 playouts.
	bias	0.1	0.01	0.001	10 -4	10 -5
		50.6 % 71.2 % 72.6 % 68.4 % 68.0 %
	bias	10 -6	10 -7	10 -8	10 -9	10 -10
		67.8 % 71.6 % 70.6 % 69.2 % 65.2 %
	bias	10 -11	10 -12	10 -13	10 -14	10 -15
		69.2 % 69.2 % 69.2 % 69.2 % 69.2 %

Table 11 :

 11 Tuning the RAVE bias with 1,000 playouts against UCT with 10,000 playouts at Domineering 19 × 19.

	bias	0.1	0.01	0.001	10 -4	10 -5
		28.0 % 51.4 % 59.6 % 59.0% 60.8%
	bias	10 -6	10 -7	10 -8	10 -9	10 -10
		60.2 % 63.8 % 59.6 % 62.8 % 60.0 %
	bias	10 -11	10 -12	10 -13	10 -14	10 -15
		62.4 % 62.4 % 62.4 % 62.4 % 62.4 %

Table 12

 12

	: GRAVE against RAVE at Domineering 19 × 19
	with 1,000 playouts.
	ref	50	100	200	400
	bias	10 -7	10 -6	10 -9	10 -8
		55.6 % 56.4 % 56.0 % 53.8 %

Table 13 :

 13 Tuning the RAVE bias against UCT at Go 9 × 9 UCT. GRAVE was then played against the tuned RAVE. The results are given in table 16. GRAVE with a bias of 10 -4 and ref equals to 50 wins 54.4 % against RAVE.

	with 1,000 playouts.
	bias		0.1		0.01	0.001	10 -4	10 -5
	83.6 % 88.2 % 87.0 % 89.6 % 87.2 %
	bias	10 -6		10 -7		10 -8	10 -9	10 -10
	87.0 % 89.6 % 88.0 % 86.2 % 86.2 %
	bias	10 -11	10 -12	10 -13	10 -14	10 -15
	86.2 % 86.2 % 86.2 % 86.2 % 86.2 %
	Table 14: GRAVE against RAVE at Go 9 × 9 with 1,000
	playouts.
	ref		25		50	100	200
	bias	10 -8	10 -10	10 -6	10 -6
			65.2 % 62.6 % 66.0 % 61.2 %

Table 15 :

 15 Tuning the RAVE bias against UCT at Go 9 × 9 of eyes of the color. The winner is the player that has the greatest score at the end.

	with 10,000 playouts.
	bias	0.1	0.01	0.001	10 -4	10 -5
		29.0 % 69.4 % 73.2 % 62.8 % 68.6 %
	bias	10 -6	10 -7	10 -8	10 -9	10 -10
		64.6 % 64.6 % 63.2 % 63.8 % 67.0 %
	bias	10 -11	10 -12	10 -13	10 -14	10 -15
		63.6 % 68.4 % 68.4 % 68.4 % 68.4 %

Table 18 :

 18 Tuning the RAVE bias against UCT at Three Color Go 9 × 9 with 1,000 playouts.

	bias	0.1	0.01	0.001	10 -4	10 -5
		49.7 % 70.5 % 70.8 % 66.7 % 68.2 %
	bias	10 -6	10 -7	10 -8	10 -9	10 -10
		67.3 % 64.5 % 67.8 % 63.5 % 64.7 %
	bias	10 -11	10 -12	10 -13	10 -14	10 -15
		63.3 % 63.3 % 63.3 % 63.3 % 63.3 %

Table 19 :

 19 GRAVE against RAVE at Three Color Go 9 × 9 with 1,000 playouts.

	ref	50	100	200	400
	bias	10 -4

Acknowledgments

This work was granted access to the HPC resources of MesoPSL financed by the Region Ile de France and the project Equip@Meso (reference ANR-10-EQPX-29-01) of the programme Investissements d'Avenir supervised by the Agence Nationale pour la Recherche