Juan-Carlos Maureira
email: jcmaurei@sophia.inria.fr

Diego Dujovne
email: diego.dujovne@sophia.inria.fr

Olivier Dalle
email: olivier.dalle@sophia.inria.fr

Network Provisioning for High Speed Vehicles Moving along Predictable Routes -Part 1: Spiderman Handover

Keywords: Wireless Handover, Internet on Rails, Simulation, OMNeT++

This report presents our on-going work on a new system designed to provide a continuous network connectivity to communicating devices located on-board a vehicle moving at "high speed" with a predictable trajectory such as trains, subways or buses. The devices on-board the vehicle form a subnetwork called the "in-motion network". This system we propose is composed of two parts. The mobile part, called Spiderman Device (SD), installed on the roof of the vehicle, and the fixed part is composed of multiples access points, called Wireless Switch Access Points (WS APs), installed along the predictable route of the vehicle. To provide a continuous connectivity, we designed a new handover algorithm that relies on a two IEEE802.11 radio hardware placed in the SD device. This dual-radio architecture allows to minimize or even hide the handover effects, achieving a seamless continuous data-link connection at high speeds, up-to 150 Km/h and possibly more. The link between the SD and the WS AP forms a Layer 2 Ethernet Bridge, supporting any Layer 3 protocol between the infrastructure network and the in-motion network. This concept has been validated by simulations and is currently tested using a real prototype in order to assess the performances and practical feasibility of the system.

Network Provisioning for High Speed Vehicles

Moving along Predictable Routes -Part 1: Spiderman Handover

Résumé : Ce rapport présente nos travaux en cours sur un nouveau système conçu pour fournir une connectivité réseau permanente à des équipements de communication se trouvant à bord d'un véhicule se déplaçant à grande vitesse le long d'une trajectoire prédéterminée, tel qu'un train ou un autobus. Ce système se compose de deux parties. La partie mobile, appelée Spiderman Device (SD), est installée sur le toit du véhicule et la partie fixe, composée de multiples points d'accès placés le long du trajet et appelés Wireless Switch Access Point (WS APs). Pour fournir une connectivité permanente nous avons conçu un nouvel algorithme de handover qui s'appuie sur deux équipement radio IEEE802.11 présents à la fois dans le SD et les WS APs. Cette architecture à deux radio permet de minimizer, et même cacher les effets du handover, ce qui permet de garantir garantir une connexion continue de niveau data-link layer dans des véhicules en mouvement à des vitesses pouvant atteindre 150km/h. Le couple SD-WS AP fonctionne de façon similaire à un pont Ethernet de niveau deux, ce qui permet d'accomplir un routage multi-protocole transparent au niveau 3, entre le réseau d'infrastructure et le réseau en mouvement. Le concept de ce système a été validé au moyen de simulations et des expérimentations réelles et évaluations de performances sont actuellement en cours sur un prototype réel.

Mots-clés : Résea sans fil, Handover, Simulation, Connectivité sur la route, OMNeT++

Introduction

Full-time network connectivity has become a reality, even in a mobile context, with the advent of 3G telephony. Every day, the market presents new devices, such as smartphones and netbooks, that deliver network connectivity to mobile users. However, the actual solutions for providing the networking service to mobile users are mainly based on telephony networks and related technologies (EDGE/3G/UMTS/. . . ). While being widely available, these telephony networks suffer from their popularity, which results in unpredictable quality of service depending on the level of concurrence in the area of use. Therefore, ensuring a sustained quality of service using such networks in a mobile context is extremely difficult. WiMax and Satellite-based solutions are also worth to mention. Satellite connections happen to be relatively expensive and suffer limited capacity compared to "small range" radio solutions. WiMax is still in early ages and mainly considered for providing a replacement to wired networks in urban areas, but it is not expected to be deployed everywhere. Because of their average to long range wireless connections, systems like satellites or WiMax also fail to ensure connections in covered areas like tunnels (railways or subways). Paradoxically, despite its wide use in static or low motion context, the WiFi technology (IEEE802.11) has received little attention so far for providing sustained quality connectivity to communicating devices moving along with a highspeed vehicle like a train or bus, over long distances. Indeed, assuming the costs of standard WiFi equipments will continue to drop down, it becomes reasonable to consider the deployment of WiFi Access Points along high traffic roads or railways, even for long distances, during inter-city transits.

In this report we present our on-going work on such a solution, based on a combination of two standard WiFi equipments. Using simulations, we show that the use of such a double-radio configuration is sufficient to provision and sustain a reasonable quality of service between the static and moving parts of the resulting network, despite the fast and continuously occurring handover events. Indeed, at high speed these handover events occur very frequently due to the limited radio coverage range of standard WiFi equipments (roughly every 5s at 150km/h, for a 200m wide coverage). Our study of such a system is divided in two parts: first, the design and study of a solution for ensuring a continuous connection between the in-motion and the fixed parts of the network; and second, the design and study of a static infrastructure network to carry the traffic of the previous solution. In this report we address the first part, leaving the second part for further studies.

The report is organized as follows: in section 2, we present previous related works. In section 3, we give a description of our WiFi-based solution, covering the operational context and the devices that implement the solution. Then, in section 4 we analyze the requirements that make the solution viable. Following, in section 5, we give our firsts evaluation results, based on simulations. Finally, in section 6, we present our conclusions and further directions.

Previous Related Work

Several studies have explored the feasibility to use IEEE802.11 devices to provide network connectivity to vehicles [START_REF] Eriksson | Cabernet: Vehicular Content Delivery Using WiFi[END_REF] and trains [ZSH + 05] [START_REF] Tse | Study of high-speed wireless data transmissions for railroad operation[END_REF]. The common problem they found was the network disruptions caused by the handover between successive hotspots, problem that is increased at higher speeds. The source of this problem is a combination of two common issues that were addressed independently in the literature. The first issue is about the effects of speed on IEEE 802.11 transmissions. For example, Gass et al. [START_REF] Gass | Measurements of in-motion 802[END_REF] and Ott et al. [START_REF] Ott | Drive-thru internet: Ieee 802.11b for "automobile" users[END_REF], have shown experimentally that IEEE 802.11b technology allows the connectivity between the infrastructure network and the in-motion devices up-to 120 Km/h and 180 Km/h, respectively. The second issue is about minimizing or hiding the loss of connectivity during IEEE802.11 handover, such as Ramachandran et al. [START_REF] Ramachandran | Make-before-break mac layer handoff in 802.11 wireless networks[END_REF] and Brik et al. [START_REF] Brik | Eliminating handoff latencies in 802.11 wlans using multiple radios: applications, experience, and evaluation[END_REF], that propose the use of two-radio hardware, focusing on how to achieve a steady constant bit rate transmission. These two kinds of issues have never been combined in a single study as we do in this report.

INRIA

System Description

In this section, we introduce a definition of the proposed system and describe our assumptions on its operational requirements in order to bound the scope of our work. We use the IEEE 802.11b standard as the reference wireless radio technology, but our approach may be further extended to any wireless technology that uses shared access to the medium, such as CSMA/CA. We assume a circular radio propagation model, described by the well known Free-Space Pathloss equation:

F SP L = 4πd λ α ( 1
)
where d is the distance from the transmitter (in metters), λ is the signal wavelength (in meters) and α is the so called path-loss exponent.

Our proposed system is composed of two devices: the Spiderman Device (SD), installed on the roof of the bus, train or subway, and a WiFi Access Point that operates at OSI level two, called the Wireless Switch Access Point (WS AP). Multiple WS APs are used to access the infrastructure network along the vehicle route. The Spiderman Device provides connectivity to the in-motion network; the corresponding link is established within the OSI layer two. This link is kept established nearly full time, using a two-radio hardware and a new hand-over procedure we designed. This procedure alternates the data link associations between the SD and the WS APs found along the path (hence the name, a metaphoric allusion to the way the comics hero Spiderman moves in the air throwing his spider web ropes one after another.) Indeed, the use of two radios, when cruising at high speed, allows to hide the time needed for association and authentication and to maximize the connection time with each WS AP.

The difference between a WS AP and a standard IEEE802.11 AP is the way associations are handled. A standard AP handles each association as a client (STA) and it only store the MAC address of the that client. On the contrary the WS AP handles each association as a wireless bridge link, and its MAC address table contains all the MAC addresses of the clients handled by the SD (instead of the SD itself). This way, The WS AP acts like an OSI layer two switch, having as switched ports the SD associations and the backbone uplink ports.

Before we enter the detailed description of each of the devices previously introduced, we first give a formal description of their operational conditions of use.

Operational context

Let M be a mobile and P a fixed path of length L, along which M is moving. We note t 0 the time at which the mobile starts from one end of P and t max the time at which it arrives at the other end. For the sake of simplicity, we will use a linear projection of the path P in a one-dimensional space and we note pos M : [t 0 ; t max ] → [0; L] the function that gives the position of M in time. We call N the on-board network attached to M (moving at the same speed).

A set of n wireless Access Points, noted AP 1 to AP n , each one covering an identical circular area of radius r, are installed along the path P. The segment of P that intersects the coverage area of AP i is noted coverage(i). We assume that AP index are sequentially attributed along the path, such that we have a total order of minimal points of each coverage, and maximal points of each coverage respectively: ∀i ∈ {1, . . . , n -1}, min(coverage(i)) < min(coverage(i + 1)) and max(coverage(i)) < max(coverage(i + 1)).

We note A(x) = {i, . . . , j}, 1 ≤ i, j ≤ n the set of the index of AP for which M is in the coverage area when arrived at position x of the path.

At any time, we assume the following property is observed (any segment of the path is covered by at least one AP):

∀k ∈ A(x), x ∈ coverage(k) and ∀k / ∈ A(x), x / ∈ coverage(k).
All APs are connected to an Infrastructure network I, which links the APs together to the same Ethernet network. Traffic to/from external networks goes through a unique gateway. Notice when we state that M is exchanging traffic with I, we are implicitly stating that in-motion network N is exchanging traffic with I. Fig. 1 depicts the described scenario. Following, we further describe the handover algorithm implemented by the SD. As previously stated in related works, the use of a two-radio hardware was already presented by Brik, Mishra and Banerjee [START_REF] Brik | Eliminating handoff latencies in 802.11 wlans using multiple radios: applications, experience, and evaluation[END_REF] and, after by Ramachandran et al. [START_REF] Ramachandran | Make-before-break mac layer handoff in 802.11 wireless networks[END_REF]. They tried to minimize and possibly hide the handover time in order to provide a constant bit rate (CBR) transmission between a single device and an infrastructure network. Our work differs from theirs on two points. First, we aim at providing a continuous connectivity not for a single device, but to an entire network moving at high speed; and second, we consider and evaluate the effects of speed on the proposed handover algorithm, issue that was not addressed by previous works.

INRIA

The Spiderman Device

In short, the Spiderman Device is an IEEE802.11 two-radio bridge client device with handover capabilities. More precisely, we define the SD as a network bridge that connects on one side, an Ethernet wired port (in-motion network uplink), and on the other side, an Ethernet wireless virtual port, provided by the Wireless Switch Access Point to which the SD is associated with.

The Handover Procedure

In the following, we describe the handover procedure implemented by the Spiderman Device we just described. During the initial synchronization phase, the algorithm starts scanning two frequencies at a time until it detects a first WS AP in the neighborhood, noted AP 1 . Once AP 1 is found, the corresponding radio link, noted RL 1 is used to establish the first association and enter the connected phase. During the connected phase, the SD uses the already associated radio (named active) to exchange user traffic packets with the WS AP i ; it uses the other radio (named passive) to scan the neighbourhood and find the next WS AP i+1 . This is done as follows: when the algorithm detects that the active radio link receives three consecutive beacons with decreasing SNR values, it starts the channel scanning process, using the passive radio. This results in an early start of the scanning process, before M arrives to the coverage(i) limit. When the algorithm has found WS AP i+1 , it commands the passive radio to stop scanning and starts the authentication/association process with WS AP i+1 . All these operations must be done before the active radio looses connection with the WS AP i , which is possible if coverage(i) and coverage(i + 1) are sufficiently overlapping. When the passive radio is already associated to WS AP i+1 , the algorithm activates the Input Queue on the Radio Switch in order to buffer the incoming packets from the in-motion network. Then, it commands the active radio Management module to move all the queued packet to the passive radio Management module; then it inserts one Gratuitous ARP packet for each ARP Cache entry in its ARP Cached Table into the Input Queue, and flushes it into the passive associated radio. Then, it waits for these ARP packets to come back via the current active radio, generating an ARP loop between the SD radios and the infrastructure network. The arrival of the last ARP packet triggers the radio state swap: passive becomes active and vice verse. The effect of this Gratuitous ARP "loop" is to update the layer two route on the backbone network, allowing external traffic to reach the in-motion network through the new association. The delay for updating the route in the fixed network (from WS AP i+1 to the network gateway) is evaluated in the section 4. Finally, when the radio states are swapped, the Input Queue is deactivated and the packet flow now is directly routed to the new active radio. This process is repeated forever until, possibly, both radios lose connectivity. In this case the algorithm is restarted.

Operationally, the described algorithm will alternate the data-link associations between the two radios, using the coverage(i) overlapping to minimize, or even to hide, the handover time, and so, to avoid breaking the connection between the in-motion and the infrastructure networks. Fig. 3 presents a sequencechart of the handover procedure. Fig. 4 presents the states of each radio, and table 1 shows all the algorithm states. As M has a fixed predictable route, the WS AP channel assignment can be done by using a predefined sequence, let us say 1,6,11,1,6,11,. . . This allows the algorithm to reduce the scanning time by avoiding to perform a full scan every time. It is worth noticing that the scanning operation is always an active . This reduced scanning is relevant when M is cruising at high speeds, since the time available to find the next WS AP is only the time where M is under mutual coverage between WS AP i and WS AP i+1 .

The Wireless Switch Access Point

The WS AP is basically an IEEE802.11 Access Point, but it handles the associations as OSI layer 2 bridges and not as wireless stations (STA). It means that the WS AP will consider as stations all the devices behind the associated radio 1 Probe-Response method RR n➦ 6850 instead of the radio itself. This modification implies to handle a MAC address table for each bridged association, having as gateway address the association MAC address. This set up is analogous to a Ethernet Layer 2 Switch, since it must implement MAC routing and a sort of spanning tree. Hence its name, since it behaves in the same way as a regular switch, but having as switched port each association and the wired uplink port. The Fig. 5 shows a Wireless Switch Access Point with two bridges associated, illustrating the MAC look-up tables built after each association. Notice that the WS AP has an association table, where it handles each associated device, and additionally, it has a MAC address table handling the MAC addresses that are known through each association (and the uplink port). Both tables, association and MAC address have ageing timers associated. A MAC entry is erased from a table after a certain time in case there is no traffic. If one association is removed, all the learned MAC addresses through that association are removed as well.

The consequence of changing from one WS AP to the following is that I must learn all the MAC addresses of the in-motion network inside M to route the packets to the correct destination. This route update is performed by the Gratuitous ARP loop defined in the previous section. The route update is transparent to each WS AP.

INRIA 4 Requirements Analysis

In this section, we analyze the problems affecting the network connectivity between an in-motion network and a fixed infrastructure network when using only IEEE802.11 technology at high speeds. As earlier mentioned in related works, the handover time is critical to ensure a continuous connection. When a singleradio hardware is used, the scanning operation causes a disruption in the datalink layer link, generating packet losses. We analyze the standard handover operation for multiple clients inside a mobile at different speeds by means of simulations, quantifying the handover times and packet losses depending on the mobile speed. Hereafter, we first give a formal description of the handover operation in order to better explain the subsequent results.

Functional Requirement

An IEEE802.11 wireless station triggers a handover procedure when it needs to move the physical layer connection and state information from one AP to the next. As explained in section 4.2, the handover operation takes a variable amount of time to be accomplished. The time required to perform handover between AP (i -1) and AP (i) is noted as T h (i), with T h (0) = 0 when entering the coverage(0) area. We divide the handover delay, T h , in two parts as follows:

T h (i) = T scanning (i) + T auth/assoc (i) (2)
where T scanning (i) is the time needed to scan radio channels and discover that AP (i) is the next AP, and T auth/assoc (i) is the time needed to authenticate/associate with AP (i). During T h (i), no data can be transferred between M and I. Consequently, packets are delayed in queues at both ends of the data link, until the link is re-established. Because queues have finite size, there is a probability of packet drops. Also, notice that T h (i) depends on the level of SIR/SNR.

Let us note T c (i) the time that M remains within coverage of AP (i) and T d (i) the time during which on-board stations can transmit data to/from I. We have:

T d (i) = T c (i) -T h (i) (3)
In addition, we define T u (i) as the time taken by the IEEE 802.11 MAC protocol to transmit/receive the minimal number of overhead packets before user data can successfully be sent or received. Proposition 4.1. A required condition to have a functional system is :

T d (i) > T u (i)
In other words, after handover operation, the remaining time until the next handover must be long enough to establish a minimal data exchange.

Timing Constraints

As previously stated, the handover time T h depends only on two components: scanning start time and AP discovery and Authentication/Association. Let us further characterize each of these quantities. First, the scanning start time depends only on the appropriate choice of the out of range detection algorithm. Raghavendra et al. [START_REF] Raghavendra | Understanding handoffs in large ieee 802.11 wireless networks[END_REF] have pointed out that even in static scenarios, the handover rate is surprisingly high. This is consequence of the current mechanisms that trigger the handover under conditions of high medium utilization and packet loss rate. Additionally, the AP discovery depends on the number of channels to scan. Mishra et al. [START_REF] Mishra | An empirical analysis of the ieee 802.11 mac layer handoff process[END_REF] have demonstrated that this is the most time consuming operation when handover occurs, even with active scanning 2 . Second, the Authentication and Association time, T auth/assoc , depends on the complexity of the authentication protocol; this complexity may vary a lot according the security schema to be used. However, T auth/assoc can be well described by the number of exchanged packets between APs and stations when performing the authentication and association process.

We used simulations to evaluate the handover time, T h according to three variables: Number of Clients, Mobile Speed and packet losses.

Number of Clients

We define a simulation scenario based on the operational context earlier described in 3.1. We consider an in-motion network with a number of wireless clients varying from 1 to 50 (1, 5, 10, 20, 30, 40 and 50), each one establishing connections directly to the infrastructure network. First, we evaluate the handover time for each wireless client using a constant speed. Fig. 6 shows the influence of the amount of clients on the handover time T h . An ANOVA Multiple Range Test analysis [Jr.86] of T h with respect to the number of clients shows significant difference between clients groups (1,5,10,20,30,40,50). This evidences that the number of clients affects significantly the handover time when all the clients compete to perform handover during the same period.

Effects of Speed

Considering now the effects of speed in presence of handover, it is worth noticing that during handover, the client can not exchange packets with the current associated AP. This fact implies a direct correlation between handover time and packet losses. When the mobile speed V increases, the number of traversed AP coverage spots per unit of time increases, as well as the probability of packet loss per unit of time. This effect is observed on Fig. 7, where M is traveling several times along P , at various speeds, with a single on-board station. The AP coverage spot traversing time T c is displayed on Table 2 for different speed ranges within a coverage area of 200 m for a fixed SNR. The on-board client is able to exchange data with I while traversing a coverage spot, for T d units of time. After the time T d is up, the on-board client must trigger a handover to connect to the next AP and resume transmission during the next T d transmission time slot. As T d depends on the speed of M , there is a speed limit where T d becomes similar to T u , turning the system unusable, due the usable time for transmission is smaller than the minimal time required to exchange a minimal amount of data with the AP. This speed limit can be expressed as follow:

V limit = coverage(i) (T u + T h ) (4)
When V approaches to V limit , the time to traverse the coverage area of an AP decreases, while the number of areas traversed per unit of time increases. Hence, the frequency of handover increases, increasing the packet losses. The overall packet losses are increased according to the number of traversed hot-spots per unit of time.

To summarize, the two key factors which influence packet loss are V and the number of in-motion wireless clients inside M .

Packet Losses

When a wireless station (STA) performs a handover, there are two possible sources of packet loss. One is packet buffering on both sides (AP and STA) when the radio is performing the handover operation; the other is during the update of the OSI layer 2 route table in the infrastructure network. is common practice for each wireless station to broadcast Gratuitous ARP packets to inform the infrastructure network about the new layer 2 route to be used. In simpler words, when a STA is inside the next hotspot, and the infrastructure network is not informed about it yet, it still routes packets to the former AP until the new AP starts sending packets to the infrastructure (and so, update the route). During this transition period, all packets previously routed to the former AP will be lost due to MAC-level retransmission failures. As a consequence, route reconfiguration delays increases the probability of packet loss during the handover.

Summarizing, these three factors are closely related when traveling with a speed such that the radio spot traversing time T d is comparable to the time taken for handover T h . In the extreme case, T d falls to zero. Furthermore, if multiple on-board stations interact directly with the infra-structure network, they compete with each other for the medium during handover, raising the packet loss probability. Moreover, when approaching the coverage limit, all onboard stations will trigger the handover process at the same time, which further increases T h .

INRIA 5 System Evaluation

In this section we evaluate the performance of the proposed system by means of simulations. We simulate a train trip with multiple on-board end-user stations, exchanging traffic with peer stations connected to the fixed network, outside the train. Our simulation scenarios are based on the reference scenario described in the section 3.1. The performance metrics we consider are communication delays (Round Trip Time and One Trip Time) and packet losses. These metrics are used to compare the conditions of connectivity between the Spiderman device and the WS AP on one hand, and with normal wireless stations and standard AP on the other hand. We compare these two configurations using two kinds of traffic: ICMP echo-reply loops, and UDP streams. Finally, we discuss the channel availability in both cases.

Simulation Scenario

We simulate a scenario similar to the one proposed by Zhou et al. [ZSH + 05] which represents a standard railroad environment and corresponds to our context of reference. The scenario consists of 100 stations, half of which are located in the moving vehicle, and the other half being static, connected to the fixed infrastructure network. The traffic exchanged between the in-motion and the external stations is configured in order to load the network up to the limit at which packets start to get dropped when handover occurs and both devices (AP and client) start buffering the incoming traffic. For the configuration without the Spiderman system, the 50 on-board wireless stations are connected directly to standard IEEE802.11 wireless Access Points placed along the route of the vehicle. For the configuration with the Spiderman system, the on-board stations are connected to an on-board access point, which is linked to the Spiderman Device, and Wireless Switch Access Points (WS APs) are used in place of standard APs along the route of the vehicle.

For each simulation run, the train, travels with a fixed speed S, chosen in the range of 10-70m/s with 10m/s steps. On the infrastructure side, a 10Km long route is used and covered by 33 access points. The upstream and downstream rates are fixed to 2 Mbps (half duplex). Each AP is connected to an Ethernet Switch using 100 Mbps full-duplex links. Furthermore, all the traffic exchanged with the infrastructure is concentrated in a Layer 3 (IP) gateway. The 50 external stations are beyond this gateway. We initiate two flows for each pair of stations (external station, on-board station): one 10Kbps CBR UDP flow from external to on-board stations, and one ICMP Ping flow at a rate of 1 packet per second. These traffic profiles met the condition of saturation we stated earlier in this section. We also fixed the queue size to 10 packets for all the participating devices inside the train. The simulation time t is configured to 142s, which is the time required time to traverse 33 APs at 70 m/s and produce steady confidence intervals for the measured variables. Additionally, statistical confidence intervals are computed over 30 simulations with different random seeds.

The simulation software used is Omnet++ (v3.3) with the INET Framework (v20061020) [START_REF] Varga | The omnet++ discrete event simulation system[END_REF]. The INET Framework has been modified in order to support the depicted scenario. The most important modifications are the support of multiple wireless cards in the same host and the support of Gratuitous ARP in the ARP module3 .

We have chosen the Pathloss model which is the most appropriate for a short-wireless link without obstacles.

Delays

We observe on Fig. 8 two graphs showing the ICMP ping Round Trip Time (RTT). The graph 8(a) corresponds to the configuration without the SD, and the graph 8(b) to the configuration with the SD and WS APs. The graph 8(a) shows small periodic connectivity drops, that increase with the vehicle speed. These drops are caused by tail drops in queues due to buffering during handover. This contrasts with graph 8(b) in which these drops disappear. This confirms that the Spiderman Device successfully prevents dropping packets during handover disconnections, but it also shows this improvement increases apparently the maximum transmission delay.

Despite the maximum delays are higher in 8(b) than 8(a), in the case of the SD configuration, our statistical analysis of the delay variable in both configurations does not show a significant difference 4 These peaks are caused by the Gratuitous ARP packets inserted in the Input Queue (one sent for each onboard station) when a handover occurs between two hotspots. However, these peaks are not enough to significantly impact the delay mean.

Packet loss

In the following we compare the packet losses suffered by both our configurations (with and without Spiderman). The comparison is two-fold: first, we study the outbound traffic case (on-board traffic toward Infrastructure); and second, we study the inbound traffic case. In both cases we calculate the packet losses that correspond to MAC drops and queue tail drops in the transmission queues. Fig. 9 compares the packet loss observed in our generated UDP flow for a fixed simulation time, in both configurations. In the configuration without Spiderman, we see that the packet loss is growing linearly with the speed of the vehicle, from less than 10% at 10 m/s up to 50% at 70 m/s. This is a direct consequence of the increased number of handover per unit of time and demonstrates the inability of standard handover to operate at high speed.

This strong correlation between speed and packet loss disappears with the second configuration. This is explained by the fact that the Spiderman device is able to queue the packets while handovers are happening. Indeed, the handover time being shorter, the queueing capacity required is limited, which results in a better ability to avoid packet losses at all speeds. Notice in particular that the packet loss variance is uniform for all the simulated speeds we considered.

Packet losses are kept independent of the speed until a critical speed is reached, which depends on the time required for traversing a hotspot (discussed on section 4.2.2). If the usable time, T d is similar or bigger than T u5 , the proposition 4.1 does not hold, and the system becomes unusable. Thus, the larger the coverage area, the higher the speed limit. This is the boundary condition for the speed of M .

In the following, we compare our two configurations in presence of incoming traffic from the Infrastructure AP to the on-board stations. On Fig. 10 we observe the queue length and packet losses during a transition between two APs from the infrastructure point of view. Let us first consider the configuration without the Spiderman device. When the on-board stations exit the current AP coverage and lose connection with the infrastructure network, the AP queue becomes rapidly full since the MAC is hopelessly retransmitting packets. Packets are not received by the on-board stations, and for each ACK timeout there is a retransmission until the retry limit is reached. The time taken by each packet on the queue to arrive to the MAC increases and the queue becomes full. Consequently, packets start to be dropped at the queue level too. During this period, the on-board station starts a full channel scan, finds the next AP, associates and authenticates and finally sends a Gratuitous ARP to announce to the infrastructure switches the route update. The switches stop sending packets to the former AP and start sending packets to the next AP. As a consequence, the queue drop events on the former AP stop and packets are lost only due to failed retransmissions. During this process, all the packets which arrived to the former AP between the start of channel scanning until the switch to the next AP are lost. Now, let us consider the configuration with the Spiderman device. We define the time dt as the time interval during which the Input Queue is active. As explained in the section 3, the Input Queue is active while the Spiderman Device is swapping radios (from the moment that the passive radio gets connection, to the moment when the Input Queue is completely flushed into the new active radio). In this case, when dt starts, the Spiderman device has already done scanning, authentication, association and has already sent the Gratuitous ARP packets to switch the traffic to the next AP. Then, the external traffic coming from the infrastructure switch is transmitted from the next AP smoothly. From the in-motion devices, only dt is observed as the time when the devices are not connected to the infrastructure network.

Channel availability

Another expected benefit of the Spiderman Device and its companion Wireless Switch AP is the maximization of the channel availability for user data transmissions. The time-line of the handover process presented in Fig. 11 shows the difference between the two configurations. In the case of Spiderman (overlapping bars in the middle), we see that handover and transmission periods, respectively noted T h and T d , are overlapping. This overlap means that T h does not affect length of T d , since the device uses the passive radio to scan frequencies and find the next AP in parallel with the active radio. In the other configuration, without Spiderman, we can see that T d and T h periods alternate with each other. And since the sum of both these durations is a constant, the longer we spend in T h for handover, the less time we have left in T d for user traffic transmission. Notice also that without Spiderman, assuming a configuration in which each on-board is directly connected to the Infrastracture APs, each station has to execute the handover independently, which results in as many full scan being performed in parallel as there are onboard stations, which further increases T h , and decreases T d . This behavior can be observed on Fig. 12(a), which shows T d at 60m/s in such a configuration in which all the on-board stations are competing to access the channel, while in Fig. 12(b) we show the Spiderman device using full scanning and the reduced scanning6 . The usable transmission time T d presented in Fig. 12(a) without Spiderman is visibly lower than the one shown on Fig. 12(b) with Spiderman, either using quick or full scanning. The channel availability time is increased by 60%, from 3s to 5s per coverage area traversal. The use of a reduced set of channels to scan, or Full scanning does not affect the T d length. Nevertheless, reduced channel set scanning is more robust than Full scanning because of a shorter repetition cycle, increasing the probability to find the next 12 gives an empirical illustration, based on simulations, of the timings presented on Fig. 11. This graph shows T d , which stays constant around 3 seconds, T h for both handover methods, and dt (the buffering period for the Spiderman device). As we can see, the influence of a full scan is the main cause of the low utilization of the channel even when the stations are within the AP coverage. The Spiderman device reduces unavailability period without significant packet loss, which is 10 times higher in the configuration without Spiderman.

Conclusions

In this report we present the Spiderman Device and evaluate its suitability for providing continuous network connection to mobile users located on-board a vehicle cruising at "high speed" along a fixed, predictable route. Using simulations, we have shown that the use of the Spiderman dual-radio used in combination with a custom handover procedure and a custom Wireless Switch Access Point is enough to provide a continuous network connectivity to on-board stations inside a Mobile up to at least 150 km/h. Interestingly, these new devices use regular IEEE 802.11 protocols and can easily be built using standard, lowcost, off-the-shelf equipments.

It is also worth to mention that this 150 km/h limit is a worst case conservative estimation based on our limited knowledge of the Doppler effects on 802.11 transmissions at very high speed. Higher speeds up to 250 km/h are envisaged, but this will require further experiments in real conditions. Nevertheless, at higher speeds, the usable transmission time T d becomes similar or greater than the minimal time required to transmit data to the infrastructure, T u , which results in a non-functional system once the speed limit is reached. A possible solution to investigate is to use a wider AP coverage area to increase the speed limit (the coverage area used in this study is 200m wide).

We have also shown that the addition of a new input queue to avoid losing packets when switching between the two radios does not affect the overall traffic delay. In addition, we propose to trigger the early sending of Gratuitous ARP packets in order to reduce the handover time and speed up the layer 2 route update.

Another consequence of the use of a single device with two radios is the increase of IEEE 802.11 channel availability time, (+60%) due the aggregation of in-motion clients traffic on a single outgoing interface.

Furthermore, an additional good property is multi-protocol routing ability of the proposed solution, since the proposed device acts as a bridge with handover capabilities. Consequently, any layer 3 protocol can be used. In the special case of IP, there is no need of per client IP address translation, and seamless IP Portability is guaranteed along the path.

Further Work

This report leaves issues open for further studies. In particular, the fixed infrastructure design introduces a new challenge that must be investigated: the Infrastructure Network must be cost-effective, self-managed, fault-tolerant, and easy to deploy.

The previous works from Gass, Scott and Diot [START_REF] Gass | Measurements of in-motion 802[END_REF] and Zhou et al. [ZSH + 05], which have measured packet loss at different Mobile speeds, are good starting points, but a more realistic channel model should be used in simulations in order to provide a better evaluation of the behavior of the proposed handover method under more stressing conditions. Furthermore, implementation and experimentation of the Spiderman device with the Wireless Switch in a real environment would be an important step towards standardization and consolidation as a industry accepted solution to the problem.

INRIA

Security is another crucial issue to address in current communication systems, and especially in the wireless context. The Spiderman device could benefit from the use of a One Time Password generation function or with the recently standardised 802.11r amendment. Both alternatives will be considered in further studies.

Figure 1 :

 1 Figure 1: Studied Scenario

Figure 2 :

 2 Figure 2: Spiderman Device Block Diagram

INRIA

FigureFigure 4 :

 4 Figure 3: Spiderman Handover procedure

Figure 5 :

 5 Figure 5: Wireless Switch Access Point and two Mobiles with on-board networks connected to an Infrastructure Network

Figure 6 :Figure 7 :

 67 Figure 6: Handover Time versus amount of clients2 Active channel scanning consists in sending packet probes in each channel: the wireless card stabilizes in the new channel, then it sends a probe packet and waits for a response from an eventual AP in the same channel. Probe packets may also collide with other packets in the same channel, thus giving a response timeout.

  ICMP Ping RTT at different speeds without Spiderman ICMP Ping RTT at different speeds with Spiderman

Figure 8 :

 8 Figure 8: ICMP Ping delay without the Spiderman device (a), and with Spiderman device (b)

Figure 9 :

 9 Figure 9: UDP Packet losses at different Speeds

  Figure 10: Access Point queue length and drop behavior (50 on-board stations). Fig.(a) without Spiderman. Fig.(b) with Spiderman.

Figure 11 :

 11 Figure 11: Timing diagram (not to scale)

  Figure 12: Traveling Time and Handover Time in both scenarios, at 60m/s: (a) without Spiderman, and (b) with Spiderman

Table 1 :

 1 Full decision table of a spiderman Station

	Input RC1 Input RC2 Output RC1 Output RC2
	Lost1	Lost2	Searching1	Searching2
	Lost1	Searching2	Searching1	No change
	Lost1	Ready2	Searching1	Active2
	Lost1	Active2	Searching1	No change
	Searching1	Lost2	No change	Searching2
	Searching1 Searching2	Wait1	Wait2
	Searching1	Ready2	No change	Active2
	Searching1	Active2	Wait1	Wait2
	Ready1	Lost2	Active1	Searching2
	Ready1	Searching2	Active1	No change
	Ready1	Ready2	Active1	No change
	Ready1	Active2	Wait1	Wait2
	Active1	Lost2	No change	Searching2
	Active1	Searching2	Wait1	Wait2
	Active1	Ready2	Wait1	Wait2
	Active1	Active2	Not valid	Not valid

Handover Time (Th) Means Plot for several amount of clients

  Multiple Range Tests for T h by ClientNumber

	Contrast	Sig.	Difference	+/+ Limits
	1-5	Yes	-0,472828	0,0158718
	1-10	Yes	-0,499724	0,0151961
	1-20 1-30 1-40 1-50 5-10 5-20 5-30 5-40 5-50 10-20 10-30 10-40 10-50 20-30	Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes	-0,552362 -0,605759 -0,660888 -0,717752 -0,0268966 -0,0795345 -0,132931 -0,18806 -0,244924 -0,0526379 -0,106034 -0,161164 -0,218028 -0,0533966	0,0148467 0,0147284 0,0146689 0,0146331 0,0079359 0,00724445 0,0069988 0,00687269 0,0067959 0,00561153 0,0052906 0,0051226 0,0050191 0,00418259	Sig.	Handover Time (sec)	1.3 1.4 1.5 1.6 1.7 1.8 1.9 2.0
	20-40	Yes	-0,108526	0,00396795			1	5	10	20	30	40	50
	20-50 30-40	Yes Yes	-0,16539 -0,0551293	0,0038334 0,0034994					Amount of clients
	30-50	Yes	-0,111993	0,00334607
	40-50	Yes	-0,0568638	0,00307356
	= statistically significant difference.

Table 2 :

 2 Time to traverse a 200m cell at various speeds

	Mobile Speed	Time to traverse a 200m-wide cell [T d ]
	10 km/h -50 km/h	72.00 sec -14.40 sec
	51 km/h -100 km/h	14.10 sec -7.20 sec
	101 km/h -150 km/h	7.12 sec -4.80 sec
	150 km/h -300 km/h	4.80 sec -2.40 sec

RR n➦ 6850

The complete modified INET framework is available at http://wwwsop.inria.fr/members/Juan-Carlos.Maureira Bravo/download/INET-20061020-JcM.tar.gz

4 A Student t-test has been used to compare the population means of the delay samples collected during the simulations of both

configurations.5 In this case, there is no time left to transmit a minimal amount of data to the infrastructure.INRIA

scan only channels 1,6,11 as we explained earlier in this report.RR n➦ 6850

Acknowledgements

The authors would like to thank everyone who helped us write this report. This work was partly founded by the IST-FET AEOLUS project.


Landy Andriamampianina

Franck Ravat

Jiefu Song

Nathalie Vallès-Parlangeau

Querying Temporal Property Graphs

Keywords: Operators, Temporal evolution, Implementation, Neo4j, OrientDB

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Many activities involve people (or objects) that interact in many ways over time [START_REF] Wang | Time-dependent graphs: Definitions, applications, and algorithms[END_REF]. For instance, an infectious disease spreads over time through the contacts among a population. Developing applications to manage these activities requires taking into account both the interconnectivity and the temporal features of the latter. In the context of the Information System, the interconnectivity can be managed by a property graph, which connects entities together through relationships and describes them with attributes [4]. The temporality, however, is not studied in this field. In other words, changes in interconnected data over time (adding, removing and updating entities, relationships as well as their attributes) are neither represented nor exploitable in existing property graph based systems. Our research question is therefore how to model and query interconnected data, taking into account their different types of changes over time.

Temporal management of data has been studied in other domains, such as relational databases [START_REF] Johnston | A Brief History of Temporal Data Management[END_REF] and Semantic Web [START_REF] Gutierrez | Introducing Time into RDF[END_REF]. In light of this work, the graph community has been working on classic graph modelling [START_REF] Angles | Survey of graph database models[END_REF] and graph-oriented databases [START_REF] Angles | A Comparison of Current Graph Database Models[END_REF] that have failed to manage data temporality up to now [START_REF] Lazarevic | Keeping track of graph changes using temporal versioning[END_REF][START_REF] Semertzidis | Time Traveling in Graphs using a Graph Database[END_REF]. Some works propose different extensions of classic graph data models to integrate time dimension [START_REF] Zaki | Comprehensive Survey on Dynamic Graph Models[END_REF]. In parallel, some works have developed their own management systems for temporal graph data [START_REF] Byun | ChronoGraph: Enabling Temporal Graph Traversals for Efficient Information Diffusion Analysis over Time[END_REF][START_REF] Debrouvier | A model and query language for temporal graph databases[END_REF][START_REF] Khurana | Storing and Analyzing Historical Graph Data at Scale[END_REF][START_REF] Ramesh | A Distributed Path Query Engine for Temporal Property Graphs[END_REF]. The overall observation is thus that there is no unified framework for both modelling and querying temporal interconnected data [START_REF] Angles | Foundations of Modern Query Languages for Graph Databases[END_REF][START_REF] Sharma | Practical and comprehensive formalisms for modeling contemporary graph query languages[END_REF]. Existing solutions focus mainly on specific implementations and lack of a conceptual view to meet the needs of designers and developers [START_REF] Angles | A Comparison of Current Graph Database Models[END_REF][START_REF] Angles | Foundations of Modern Query Languages for Graph Databases[END_REF][START_REF] Sharma | Practical and comprehensive formalisms for modeling contemporary graph query languages[END_REF].

The contribution of our work is to provide a conceptual solution (independent of any implementation aspects) for designers and developers to model and query temporal interconnected data. To do so, we propose operators for querying temporal graph data, which are based on a model proposed in our previous work [START_REF] Andriamampianina | Towards an Efficient Approach to Manage Graph Data Evolution: Conceptual Modelling and Experimental Assessments[END_REF]. The remainder of the paper is organized as follows. First, we review the literature on the management of temporal graph data (Section 2). Second, we define our conceptual model (Section 3.1) and operators (Section 3.2). Third, we present translation rules of our solution into technical environments in Section 3.3. Fourth, we evaluate the feasibility of our operators, presented in Section 4. Finally, we conclude the paper.

Related work

Temporal evolution of interconnected data shows how entities, relationships and their attributes may evolve in time. This evolution can be categorized into two categories: topological evolution (addition and removal of entities and relationships) and attributes evolution (addition, removal and update of attributes of entities and relationships) [START_REF] Zaki | Comprehensive Survey on Dynamic Graph Models[END_REF]. To address the management of such data, we study their modelling and querying in the literature.

Property-graph and RDF data models are commonly used in the context of graph data management [START_REF] Angles | A Comparison of Current Graph Database Models[END_REF]. The property graph model allows for representing entities and relationships, using nodes linked by edges, and their attributes, using properties contained in nodes and edges [4]. The RDF model allows for representing the semantic links between data, using nodes linked by edges, but does not allow the nesting of data such as properties contained in nodes and edges [START_REF] Lassila | Resource description framework (RDF) model and syntax specification[END_REF]. Several graph query languages rely on the previous models such as SPARQL (W3C) 3 for the RDF data model, Cypher (Neo4j)4 , G-Core (LDBC) [START_REF] Angles | G-CORE: A Core for Future Graph Query Languages[END_REF] and PQGL (Oracle) [START_REF] Van Rest | PGQL: a property graph query language[END_REF] (and so on) for the property graph model. However, they only provide basic graph operations for interconnected data [START_REF] Angles | Foundations of Modern Query Languages for Graph Databases[END_REF][START_REF] Sharma | Practical and comprehensive formalisms for modeling contemporary graph query languages[END_REF]. To query temporal aspects of interconnected data, it requires an underlying data model that traces evolution. Although the property graph model incorporates some aspects of data we are interested in, it does not take into account the different types of changes that may occur on interconnected data.

To support temporal evolution, some works propose to extend current graph query languages, based on temporal property graph models, to support basic graph operations and add expressions for time dimension querying [START_REF] Byun | ChronoGraph: Enabling Temporal Graph Traversals for Efficient Information Diffusion Analysis over Time[END_REF][START_REF] Debrouvier | A model and query language for temporal graph databases[END_REF][START_REF] Khurana | Storing and Analyzing Historical Graph Data at Scale[END_REF]. However, graph query languages are database-dependent but not user-oriented. Implementation details behind graph query languages need to be understood to formulate queries. Therefore, the use of these extended graph query languages can be difficult for designers and developers [START_REF] Bloesch | ConQuer: A Conceptual Query Language[END_REF]. Moreover, graph query languages may evolve over time (the addition or removal of functionalities) so they are not very consistent as a basis of a new query language [START_REF] Bloesch | ConQuer: A Conceptual Query Language[END_REF]. The work of [START_REF] Ramesh | A Distributed Path Query Engine for Temporal Property Graphs[END_REF] proposes a graph query language independent of current graph query languages. However, it has the same limited composability as for graph query languages. Composability5 allows complex queries to be built up from smaller (or simpler ones). This facilitates the understanding of complex queries and the reuse of existing operations [START_REF] Angles | G-CORE: A Core for Future Graph Query Languages[END_REF].

Other works propose an algebra of composable operators for querying temporal property graphs models, in the same idea as the relational algebra [19,[START_REF] Rost | Distributed temporal graph analytics with GRADOOP[END_REF]. They extend existing graph operations [START_REF] Angles | A Comparison of Current Graph Database Models[END_REF][START_REF] Angles | Foundations of Modern Query Languages for Graph Databases[END_REF][START_REF] Sharma | Practical and comprehensive formalisms for modeling contemporary graph query languages[END_REF], such as the basic graph pattern matching 6 , to incorporate temporal operators functionally similar to Allen operators [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF]. They also introduce novel operators such as the snapshot operator, which extracts subgraphs (nodes and edges) that existed at a user-defined time range. They allow operators to be combined for advanced analysis, such as comparing two graphs obtained by the snapshot operator to observe changes between the two. However, the algebra in [19] relies on the sequence of property graph snapshots, a graph-specific adaptation of the temporal data modelling strategy in the relational databases [START_REF] Dey | A Complete Temporal Relational Algebra[END_REF]. This approach fails to trace changes at the level of the graph component (node and edge). Therefore, it does not allow direct querying of temporal graph data at the graph component level [START_REF] Kosmatopoulos | Hinode: implementing a vertexcentric modelling approach to maintaining historical graph data[END_REF]. Both [19] and [START_REF] Rost | Distributed temporal graph analytics with GRADOOP[END_REF]'s operators manipulate data-oriented concepts from their underlying models, such as nodes and edges, instead of user-oriented concepts, such as entities and relationships. Moreover, there is no technical environment that implements them directly.

To sum up, existing works fail to either provide a user-oriented solution or support all temporal analysis operations. To do so, we propose a solution to query temporal graph data according to the following user-oriented criteria (i, ii and iii) and analysis criteria (iv and v): (i) to rely on a user-oriented conceptual model, (ii) to be composable to facilitate the formulation of temporal queries and their combination, (iii) to be directly implementable, (iv) to support basic and temporal graph operations, and (v) to support direct querying at all levels of the graph (a component, a set of components and the whole graph). To satisfy the previous criteria, we introduce in the following section our conceptual model and operators for representing and querying temporal interconnected data.

Proposition

Model

We define a conceptual model of temporal property graphs, on which rely our operators. All the details of this model are available in [START_REF] Andriamampianina | Towards an Efficient Approach to Manage Graph Data Evolution: Conceptual Modelling and Experimental Assessments[END_REF].

Our model provides concepts to represent objects, relationships between objects and their evolution in terms of (i) topology i.e., their addition and removal over time as well as (ii) attributes (or properties) i.e, the addition and removal of new attributes and the change in attribute values. To handle such evolution, the model manages time through the concept of valid time interval, which represents when something has occurred or changed in the real world. We denote it T = [t s , t f [ which indicates a time interval starting from the time instant t s and extending to but excluding the time instant t f .

To describe an object, we propose the concept of temporal entity. A temporal entity e i has an identifier id and a label l that describes its semantic. At each change of an entity, in terms of topology and attributes, a new state of the entity is created instead of overwriting the old state version to keep track of changes. Therefore, a temporal entity is composed of a non-empty set of states S ei . Each state s j ∈ S ei describes the characteristics of the entity through a set of attributes A sj , the related set of attribute values V sj and a valid time interval T sj indicating the time during which A sj and V sj do not change. The function Σ e returns for a temporal entity all of its states: Σ e : e i → {s 1 , ..., s m } A relationship between two objects does not have an independent existence. Its existence depends on the objects it links. To describe such relationship, we propose the concept of temporal relationship. A temporal relationship r i is defined according to the same concepts and functions as a temporal entity. Its particularity is to describe the link between two entity states (s k , s j ). The function ρ returns, for two entity states s k and s j and a relationship label l, a temporal relationship r i if it exists:

ρ : s k × s j × l → r i
Following these definitions, a Temporal Property Graph is defined by T G = E, R where E = {e 1 , ..., e g } is a finite set of temporal entities and R = {r 1 , ..., r h } is a finite set of temporal relationships. Subsets of entities (or relationships) in the graph can share the same semantic. The function δ returns for a label l, the set of entities E k (or relationships R k ) having the label l: Example 1. In this example, we propose a real-world use case of our temporal property graph model to present its graphical notation. A social experiment 7 was designed to study the contagion of flu symptoms of students from MIT. The study includes daily surveys about the flu symptoms of students: cough, fever and so on. Moreover, it includes information about interpersonal relationships (close friends, socialize 8 , etc.) and physical information (proximity 9 , call, etc.).

δ e : l → E k where E k ⊂ E δ r : l → R k where R k ⊂ R
We present in Figure 1 a short example of the temporal property graph representation of such dataset. Students are modelled as labelled temporal entities and illustrated by nodes in grey. All descriptive information, such as flu symptoms of students, are modelled through attributes. Students evolve in terms of their attribute values. Indeed, they have different states (illustrated by the white nodes) because their flu symptoms can change over time 10 . For instance, the student identified 35 has two states numbered 4 and 5 because he got fever and cough at state 5 that he did not have at state 4. The interpersonal relationships and physical information between students evolve only according to their topology (addition and removal over time). Each of them is modelled as a temporal relationship between two states of students and illustrated by a black edge. Each temporal relationship is labelled with its semantic (socialize, proximity or call etc.). It can have several states (illustrated by white rectangles) as they occur several times. For instance, the student 76 calls two times the student 15 that is why the relationship CALL has two states numbered 7 and 8.

Operators

In this section, our objective is to propose user-oriented operators. Instead of proposing a set of operations with a technical view (such as projection), we propose two emblematic operators for temporal graph analysis: (i) extraction of a subgraph satisfying selection and temporal criteria and (ii) extraction of a subgraph satisfying pattern criteria.

Our proposed operators rely on the previous model of temporal property graph (Section 3.1). They return a temporal subgraph T G output whose entities and relationships are subsets of an input temporal property graph T G input .

In the context of temporal interconnected data, users may reason over time dimension to express their analyses [START_REF] Wang | Time-dependent graphs: Definitions, applications, and algorithms[END_REF]. To do so, we propose the matching predicate operator for querying temporal property graphs according to conditions on attributes and time. 7 available on the Reality Commons website http://realitycommons.media.mit. edu/socialevolution.html 8 participate at least one common activity 9 Bluetooth signal sent from whose mobile phone and received by whose mobile phone and time, indicating the sender's mobile phone was within 10 meters of the receiver's mobile phone at the time of the record. 10 The value of a symptom attribute equals 0 if the student does not have the symptom and 1 if the student has the symptom.

Table 1: Predicate matching operator.

Operator: matching predicate (T Ginput, π) Input: an input graph T Ginput; a set of user-defined predicates π Output:

a subgraph T Goutput Actions:

1. Extract all the labels in π 2. T Goutput ← ∅, ∅ 3. For each l ∈ π 4.

Extract the set of entities or relationships labelled l from T Ginput using δe(l) or δr(l) 5.

For each e h ∈ δe(l) or r h ∈ δr(l) 6.

Get the states of e h or r h using Σe(e h ) or Σr(r h ) 7.

For each si ∈ Σe(e h ) or si ∈ Σr(r h ) linking (sj, s k ) 8.

If si satisfies all conditions in π 9.

T Goutput ← T Goutput ∪ {si}, ∅ 10.

or T Goutput ← T Goutput ∪ {sj, s k }, {si} 11.

End If 12.

End For 13.

End For 14. End For 15. Return T Goutput.

Definition 1. The matching predicate operator is used to extract the subgraph T G output from an input graph T G input according to a user-defined set of predicates on each element of entity and relationship sets of the input graph. Within a predicate, the user has access to an entity or relationship label l, attributes, valid time intervals and can express a logical condition. The algorithm of the execution of time matching operator is presented in Table 1.

matching predicate : T G input × π → T G output
where π = {p 1 β p 2 ...p n-1 β p n } is a set of user-defined predicates combined with connective operators β such as AN D or OR (etc.).

Each predicate p i equals l.aθw or l.T θw where l is an entity or relationship label, a is an attribute, T is a valid time interval, w is a user defined value and θ is a comparison operator.

In the case of an attribute predicate p i = l.aθw, θ could be, for instance =, < or > (etc.) to express that the attribute a satisfies a given value or range. In the case of a time predicate p i = l.T θw, θ is a temporal operator such as an Allen operator presented in Table 2.

Contrary to the filter operation for static property graphs [START_REF] Angles | A Comparison of Current Graph Database Models[END_REF][START_REF] Angles | Foundations of Modern Query Languages for Graph Databases[END_REF][START_REF] Sharma | Practical and comprehensive formalisms for modeling contemporary graph query languages[END_REF], the proposed matching predicate operator allows filtering graph data not only according to predicates on attributes but also on valid time intervals. As we can see in Table 1, the matching predicate operator extracts only entities and relationships that satisfy the set of predicates at the level of states. A fundamental operation of graph analytics is to explore subgraphs that match a user-defined graph pattern. To do so, we propose the following operator. Definition 2. A matching pattern operator returns for an input graph T G input , an output subgraph T G output matching a user-defined graph pattern defined by a starting entity label l Ei , an ending entity label l E k , and a relationship label l Rj Table 3: Graph pattern matching operator.

Operator: matchingpattern(T Ginput, (lE i , lR j , lE k )) Input:

two entity labels lE i and lE k ; a relationship label lR j Output:

a subgraph T Goutput Actions:

1. T Goutput ← ∅, ∅ 2. Extract the set of entities labelled lE i and lE k from T Ginput using δe(lE i ) and δe(lE k ) 3. For each e h ∈ δe(lE i ) 4.

Get the states of e h using Σe(e h ) 5.

For each e f ∈ δe(lE k ) 6.

Get the states of e f using Σe(e f ) 7.

For each si ∈ Σe(e h ) 8.

While there exists an entity state sj ∈ Σe(e f ) such that ρ(si, sj, lR j ) = ∅ 9.

T Goutput ← T Goutput ∪ {si, sj}, {ρ(si, sj, lR j )} 10.

End while 11.

End For 12.

End For 13. End For 14. Return T Goutput to be traversed between the two entity labels. The algorithm of the execution of graph pattern matching operator is presented in Table 3.

matching pattern : T G input × (l Ei × l Rj × l E k ) → T G output
Contrary to the graph pattern matching operation for static property graphs [START_REF] Angles | A Comparison of Current Graph Database Models[END_REF][START_REF] Angles | Foundations of Modern Query Languages for Graph Databases[END_REF][START_REF] Sharma | Practical and comprehensive formalisms for modeling contemporary graph query languages[END_REF], the proposed matching pattern operator allows extracting subgraph structures with time dependent information. Indeed, it extracts subgraphs having the same pattern as the user-defined graph pattern at the level of states (Table 3). It excludes from the result set the states of entities and relationships that are not labelled with the labels specified in the user-defined graph pattern and that do not verify the existence of relationship states between each pair of entity states.

Example 3. Following Example 1, we want to know if students that had fever socialized since 03/11/2021 with students that did not have fever.

To do so, we apply to the temporal graph T G in Figure 1 T G 2 = matching predicate (T G, {(ST U DEN T 1 .f ever = 0) AN D (ST U DEN T 2 .f ever = 1) AN D (SOCIALIZE.T • [03/11/2021, +∞[)}) to select entities and relationships satisfying our attribute and time conditions. Then, we apply T G 3 = matching pattern (T G 2 , (ST U DEN T 1 , SOCIALIZE, ST U DEN T 2 )) on T G 2 to obtain the relationships between the selected entities. We obtain the subgraph T G 3 in Figure 3. We observe that the relationship has two states (numbered 9 and 11) meaning that the relationship has changed. Here, as there is no attribute in the relationship, we only have information about its evolution in terms of topology, i.e. the time of its occurrence (when it is added and removed).

Mapping from temporal graph operators to a property graph operators

In this section, our objective is to define translation rules of our operators into existing property graph operations to enable a direct implementation in propertygraph based systems. As a preliminary step, we have to map our conceptual temporal property graph T G into a logical property graph P G [4]. A property graph P G is composed of nodes and edges. Each edge is associated to a pair of nodes. Each node (or edge) can be associated with a set of labels and can contain properties. Each property is a key-value pair. For each state s of an entity e in T G, a node is created in P G with a label corresponding to the label of e and a set of properties corresponding to the identifier of e, the attributes of s, the start and end instants of the valid time interval of s. An entity in the property graph corresponds therefore to a set of nodes having the same identifier. For each state s of a relationship r in T G, an edge is created in P G by connecting the two nodes corresponding to two states that r links, with a label corresponding to the label of r and a set of properties corresponding to the attributes of s, the start and end instants of the valid time interval of s. A relationship in the property graph corresponds therefore to a set of edges linking the same pair of nodes. As a result, we obtain the translation rules in Table 4 of our temporal property graph into the property graph to implement the model in any graph oriented NoSQL database compatible with the property graph.

In Table 6, we define translation rules of our proposed operators in existing property graph languages. The algorithms of our proposed operators (Tables 1 Table 4: Translation rules of our conceptual model into the logical model of property graph, the property graph in Neo4j and the property graph in OrientDB.

* startvalidtime and endvalidtime. * * with different valid time intervals.

Operator Description Notation

Bgpm Extracts subgraphs from a property graph G according to pattern P τ (G, P ) P rojection Returns a subset of the output variables O of the result of a bgpm µ(G, O)

F ilter

Extracts subgraphs from G satisfying user-defined conditions C σ(G, C) and 3) define the scope of the sequence of basic operations in existing property graph query languages (Table 5). A matching predicate (T G input , π) operation is translatable into property graph query languages through the execution of the filter operation σ(T G input , π) to extract the subgraphs G 1 from the temporal property graph T G input satisfying user-defined predicates π. Then, the projection operation µ(G 1 , G 1 ) returns the graph resulting from the previous operation.

A matching pattern (T G input , (l Ei , L Rj , l E k )) operation is translatable into property graph query languages through the execution of the basic pattern matching operation τ (T G input , (l Ei , L Rj , l E k )) to extract subgraphs G 1 with the pattern (l Ei , L Rj , l E k ). Then, it uses the µ operator as in the chain of operations of matching predicate to get the result set.

In some environments, existing property graph query languages include sufficient functionalities to translate easily our proposed operators. In other environments, our proposed operators could not be easily implementable via the property graph query language. Due to the rich functionalities of the query languages of Neo4j and OrientDB graph databases, the mapping of our operators is simple.

(T G input , π) (T G input , (l E i , l R j , l E k )) PG Operators 1. G 1 = σ(T G input , π) G 1 = τ (T G input , (l E i , l R j , l E k )) 2. G 2 = µ(G 1 , G 1 ) G 2 = µ(G 1 , G 1 ) Neo4j QL M AT CH (a : l) M AT CH (a : l E i ) -(b : l R j ) W HERE l.p x AN D l.p y -(c : l E k ) RET U RN a
RET U RN a, b, c OrientBD QL M AT CH{class : l, as : a, M AT CH{class : l E i }.outE(l R j )

where :

p x AN Dp y } .inV (l E k ) RET U RN * RET U RN *

Experimental evaluation

We run an experiment with the objective of evaluating the feasibility of our solution (our model and operators) through their implementation in technical environments.

Protocol

To validate the feasibility of our solution, we implement two datasets in two different graph database systems. We used Neo4j and OrientDB graph database systems. More precisely, we used the following hardware configuration for the experiment: PowerEdge R630, 16 CPUs x Intel(R) Xeon(R) CPU E5-2630 v3 @ 2.40Ghz, 63.91 GB. Two virtual machines are installed on this hardware. Each virtual machine has 6 GB in terms of RAM and 100 GB in terms of disk size. On each of the two virtual machines, we installed respectively a graph database compatible with the property graph model: (i) Neo4j (version 4.1.3) and (ii) OrientDB (version 3.0.4). To avoid any bias in the disk management, we did not use any customized optimization techniques, but relied on default tuning of Neo4j and OrientDB.

To avoid any bias in datasets, we need to include both real and benchmark datasets. The first one we used is the Social experiment dataset presented in Example 1. The second one is a dataset generated from a reference benchmark available online, namely TPC-DS benchmark 11 . We transformed both datasets into the temporal property graph. Then, we stored the Social Finally, we need temporal analyses adapted for each dataset. The objective is to express them into our operators and then translate them into the graph query languages of the graph database systems we used.

A Neo4j-based implementation

We query the Social Experiment dataset in Neo4j to make temporal analyses based on our operators. The first query concerns the analysis of the evolution of an entity during a period. The second query concerns the analysis of the evolution of several entities at a time point. In the following, we express the previous analyses using our operators and translating them into Cypher, the Neo4j's query language. The above query is translated (

-T G 1 = matching predicate (T G input , {(ST U DEN T 1 .f ever = 1) AN D (ST U DEN T 2 .f ever = 0) AN D (SOCIALIZE.T • [05/03/2009, 06/03/2009[)}) -T G 2 = matching pattern (T G 1 , (ST U DEN T 1 , SOCIALIZE, ST U DEN T 2 ))
The above query is translated (Table 6) into Cypher as:

MATCH p=(s1:Student)-[r:Socialize]-(s2:Student) WHERE s1.fever="1" AND s2.fever ="0" AND date(r.startvalidtime) < date("2009-03-06") AND date(r.endvalidtime) >= date("2009-03-05") RETURN p

An OrientDB-based implementation

We query the TPC-DS dataset in OrientDB to conduct a temporal analysis based on our operators. The query concerns the analysis of the evolution of a set of entities during a period. In the following, we express the previous query using our operators and translating them into OrientDB query language. The above query is translated (Table 6) into OrientDB query language as: MATCH {class: Store, as: s}.outE("SS_Promotion").inV("Promotion") {as: p, where: (start_valid_time.asDate().format("yyyy-MM") < date("1996-04", "yyyy-MM").format("yyyy-MM") AND end_valid_time.asDate().format("yyyy-MM") >= date("1996-03", "yyyy-MM").format("yyyy-MM"))} RETURN *

Conclusion and future work

In this paper, we proposed two conceptual operators to help designers and developers to query temporal property graphs. They combine several advantages compared to current graph query languages and operators. First, they support classic and temporal graph operations. Second, they allow for a direct querying at different levels of the graph and at different time granularity. Third, they manipulate user-oriented concepts instead of database-oriented concepts to facilitate the formulation of queries. Finally, they are directly implementable into existing property graph database systems. To validate their feasibility, we examined use cases based on real and benchmark datasets. We showed how our operators can be used to express real-world analysis cases, and how they can be easily translated into queries in Neo4j and OrientDB using our translation rules.

In our future work, we will have several research directions. First, regarding our proposition, we will make a theoretical study to prove the completeness of our operators and add new operators if necessary. Second, regarding the evaluation of our solution, we are currently working on the performance evaluation of our operators. This evaluation will include several experiments based on several alternative implementations of graph database management systems and graph query languages, and based on different datasets and query types. Then, we will evaluate the query performance via experiments. To do so, we will study different optimization techniques, and propose several scale factors to test scalability. The objective is to propose guidelines for the implementation choice according to the analytical needs. Finally, we identified a possible extension of our solution in other domains, such as the Semantic Web domain [START_REF] Batsakis | Temporal representation and reasoning in owl 2[END_REF][START_REF] Ravat | Efficient querying of multidimensional rdf data with aggregates: Comparing nosql, rdf and relational data stores[END_REF]. We will verify its implementation in new environments and make a performance comparison with classic graph database systems such as the ones used in our paper.

Fig. 1 :

 1 Fig. 1: Graphical notation of our temporal property graph.

Fig. 2 :

 2 Fig. 2: Result of example 2.

Fig. 3 :

 3 Fig. 3: Result of example 3.

Query 1 :

 1 How did evolve the symptoms of student 76 during the period from 19/01/2009 to 23/01/2009 ? This query corresponds to the following operation in our solution: -T G 1 = matching predicate (T G input , {(ST U DEN T.id = 76) AN D (ST U DEN T.T d[19/01/2009, 23/01/2009])}

Query 3 :

 3 Find the stores that proposed a promotion at the month 03/1996 ? This query corresponds to the following sequence of operations in our solution: -T G 1 = matching predicate (T G input , {(P romotion.T • ([03/1996, 04/1996[)}) -T G 2 = matching pattern (T G 1 , (Store, SS_P romotion, P romotion))

Table 2 :

 2 Allen operators. T = [t s , t f [ is a valid time interval. T u = [x, y[ is a user-defined time interval where variables x and y are time instants.

  interval of an entity state T s j two properties * two properties two properties a valid time interval of a relationship state T s b two properties * two properties two properties a temporal entity ei a set of nodes * * a set of nodes a set of vertices a temporal relationship ri a set of edges * * a set of edges a set of edges a label of a temporal entity l

	Temporal property graph	Property graph	Neo4j	OrientDB
	a state of a temporal entity sj	a node	a node	a vertex
	a state of a temporal relationship sb	an edge	an edge	an edge
	a valid time a label	a label	a vertex class
	a label of a temporal relationship l	a label	a type	an edge class
	an attribute of a temporal entity a e i q	a property	a property	a property
	an attribute of a temporal relationship a r i d	a property	a property	a property

Table 5 :

 5 Graph operations to query property graphs. Bgpm = Basic graph pattern matching.

Table 6 :

 6 Translation of our temporal graph operators into property graph query languages. l.p x and l.p y are user-defined predicates in π. TG = Temporal Property Graph, PG = Property Graph, QL = Query Language.

	TG Operators	matching predicate	matching pattern

Table 7 :

 7 Characteristics of datasets. Y= Yes, N= No, AV = Attribute Value, AS = Attribute Set, T = Topology. experiment dataset in Neo4j and the TPC-DS dataset in OrientDB by applying the mapping rules in Table4. As a result, we obtained two implementations having different volumes (from 0.3 GB to 17 GB), different temporal evolutions (many nodes in one dataset and many edges in another) and different domains (social networks and a retail company). Details of both implementations are presented in Table7and available on the website https: //gitlab.com/2573869/queryingtemporalpropertygraphs.

	Implementation	Social experiment	TPC-DS
	Number of nodes	33 934	2 348 965
	Number of edges	2 168 270	41 898 261
	Size in GB	0.3	17
	Evolution types of entities	AV,T	AV,AS,T
	Evolution types of relationships	T	AV,AS,T

Table 6

 6 Are there students that had fever and socialized at the day 05/03/2009 with other students that did not have fever ? This query corresponds to the following sequence of operations in our solution:

	) into Cypher as:

https://www.w3.org/TR/rdf-sparql-query/

https://neo4j.com/developer/cypher/querying/

Graphs are input and output of queries[START_REF] Angles | G-CORE: A Core for Future Graph Query Languages[END_REF].

Basic graph pattern matching consists in retrieving subgraphs that match a userdefined pattern (or graph structure).

http://www.tpc.org/tpc_documents_current_versions/pdf/tpc-ds_v2.13.0. pdf


Andrey Besedin

Pierre Blanchart

Michel Crucianu

Deep Online Storage-Free Learning on Unordered Image Streams

published or not. The documents may come

2) Classes don't have to be equal → Want to learn well on classes of different sizes.

3) Streams are potentially of a very big (infinite) size → Want to avoid storing historical data.

4) At some point several data classes can never appear again in the stream → Need to avoid catastrophic forgetting of already learned information.

5) Data classes, never seen by the learning system before, can appear → Need a model, able to adapt to new classes

Generative Adversarial Networks (GAN) [1]

Deep Convolutional GANs [2] -difference from classic GANs:

Learning classification models on streams with no storage using GANs G is taught to produce samples similar to the real data and D is simultaneously trained to distinguish generated samples from the real ones.

Minimax game between G and D is based on loss function:

min G max D L G , D ( x)= E x ~pS ( x) [ log D ( x)]+ E s * ~p S* (s * ) [log( 1-D (G( s *)))]
• All pooling layers are replaced by strided convolutions, which allows the network learn its own down-sampling • Batch normalization[3] is used to avoid poor initialization problems. • Small values of k provoke forgetting, previously learned classes get crushed

• ~94% classification accuracy with big enough k in completely online settings (99.6% in batch mode with the same net architecture)

• Very big k = a lot of data to generate, can become a problem for the datasets with 100+ classes

Results:

• We get to stable accuracy with the size of generated set of 20% of the initial training set

• Lose >4% in accuracy comparing to the original data usage -the price to pay for not storing the data

BACKGROUND

Online learning in realistic stream scenario on complex dataset (LSUN)

Data classes are mixed and only partially presented in the stream at every time point

  Commissariat à l'énergie atomique et aux énergies alternatives Institut List | CEA Saclay | Digiteo -Bât. 565 -PC 192 91191 Gif-sur-Yvette Cedex | FRANCE www-list.cea.fr Contact | prenom.nom@cea.fr Deep Online Storage-Free Learning on Unordered Image Streams Andrey Besedin Encadrant : Pierre Blanchart (LADIS) Directeur : Michel Crucianu (CNAM) Co-directeur: Marin Ferecatu (CNAM) Deep learning on data streams vs static learning, application for the classification task 1) Data comes with high speed → Need real time information extraction and learning.

  and have to be processed in real time. The whole dataset is stored on the disc and is available at any moment.Deep learning on static datasetDeep learning on data streams 1) Dataset is of a limited size and exact training time per epoch can always be estimate. 2) Sizes of data classes are usually similar or can be equalized before training 3) The whole dataset is available for learning and retraining at any moment 4) All the data classes are available at every training epoch. Moreover, training Is based on gradient-based methods, usually need multiple training epochs 5) Number of classes together with labels for each data sample are provided before training. Dataset is available at http://yann.lecun.com/exdb/mnist/ (b) Dataset is available at http://lsun.cs.princeton.edu/2016/ G Real data (S) s -real data sample s* -generated sample Randomly choose x from {s, s*} D P(x Є S) L G,D (x) Input noise Schematic representation of GAN. Generator (G) and discriminator (D) are Neural Networks.

•

  No fully-connected hidden layers • Better suited for image datasets Goal: • Use generative models in classification scenario on data stream with data arriving incrementally class-by-class to remove the necessity of storing historical data while not introducing forgetting • Check the influence of the amount of generated data on classification accuracy Schematic representation of proposed solution: Ideas in development and perspectives • Move forward more efficient learning → Better performance with less training examples (one-shot learning, non-gradient optimization methods, … ) • Define and implement sub-space constrains when learning new data classes to avoid catastrophic forgetting without reusing historical information at all. • Study the "separability" of Neural Networks activations, depending on data type/class, to introduce activation scheduling inside networks → more efficient learning with less forgetting Batch learning on generated data (MNIST dataset) Goal: To check the ability of generative models to produce data that represent well the initial dataset before passing to the online scenario Method: • Train one generator per data class • Use generators to recreate synthetic dataset of the size, proportional to the initial one • Train batch classifier on generated dataset • Test obtained classifier on the original validation set Adaptive learning on incremental data stream Forming batches to train classifiers.

•

  Using more advanced generative models should reduce the loss Examples of images, used for training (left) and samples, generated with GANs (right) 1) Goodfellow, Ian, et al. "Generative adversarial nets." Advances in neural information processing systems. 2014. 2) Radford, Alec, Luke Metz, and Soumith Chintala. "Unsupervised representation learning with deep convolutional generative adversarial networks." arXiv preprint arXiv:1511.06434 (2015).