John Tobin
email: john.tobin.1@ucdconnect.iechristina.thorpe@ucd.ie

Christina Thorpe

Damien Magoni
email: damien.magoni@ucd.ieliam.murphy@ucd.ie

Liam Murphy

An Approach to Mitigate Multiple Malicious Node Black Hole Attacks on VANETs

Keywords: black hole attack, vehicular networks, denial of service, network security, VANET

Inter-vehicular communication is a growing trend among the motor vehicle industry, as part of the shift to the Intelligent Transportation System (ITS) paradigm and the emergence of autonomous vehicles. The benefits of using vehicular communication systems are many: traffic congestion can be abated leading to increased route efficiency and fuel economy; road traffic accidents and fatalities can be prevented; and new services are made available to both driver and passengers. Due to the important functions carried out by these networks, it is essential that communication is secure and free from interference by malicious parties. But the very nature of these networks (i.e. public and dynamically forming, over a shared medium) make them susceptible to certain attack vectors. Black hole attacks are a discernible threat to vehicular communication and the availability of Vehicular Ad Hoc Networks (VANETs). Previously, we proposed a solution to mitigate these attacks in the case of a single malicious node. This countermeasure comprised a detection, accusation, and blacklisting scheme. We now extend that work to also account for cases where multiple malicious nodes are present in the same network. For cases where there is only one malicious node on multiple routes, we add a recursive element to our algorithm to handle additional detections during the accusation phase. Routes containing a node with a pending accusation are also precluded from selection. Where multiple malicious nodes exist on the same route, we adapt our former strategy to allow for multiple concurrent accusations and to find alternate routes to non-malicious nodes that need to be queried when verifying an accusation. We provide validation for our proposal using a simulation model built in NS-3. Results from simulation show the efficacy of our solution in detecting and preventing multiple malicious node black hole attacks in VANETs.

Introduction

Intelligent Transportation Systems are on the rise and offer a plethora of benefits to users. Improved road utilisation, efficiency and safety are among the top advantages. VANETs are wireless networks that facilitate inter-vehicular communication. VANETs play a substantial role in ITS by propagating traffic and important safety information to nodes. For example, if there is a road traffic accident ahead which is blocking off a road, nodes in the VANET will alerted to this prior to reaching the scene of the incident. Nodes can then divert and avoid a traffic build-up around the accident. A more recent safety application (with the potential to save lives) is the electronic brake light system [START_REF] Biswas | Vehicle-to-Vehicle Wireless Communication Protocols for Enhancing Highway Traffic Safety[END_REF]. Such systems transmit braking information to nearby nodes within a VANET and alert drivers to when other vehicles apply their brakes, which is particularly useful as brake lights can often be obscured by other vehicles. However, more advanced and integrated versions of this technology provide an even greater advantage: they can have the vehicle automatically apply the brakes in response to receiving a message, and sensing, that another vehicle directly ahead has suddenly applied their brakes (e.g. due to an obstacle on the road). The ability to react in this case is quicker than that of the human driver and may prevent a road traffic incident from occurring. VANETs can additionally provide multimedia content, communication and messaging services, and automobile internet access. Due to the importance of some of these applications, and particularly with the emergence of autonomous vehicles, the security of VANETs is a paramount safety consideration.

VANETs are a close relative of the Mobile Ad-Hoc Network (MANET) but differences in node mobility and a rapidly-changing topology distinguish them. Furthermore, VANETs are formed spontaneously and often have a short lifespan. Mobile nodes (i.e. vehicles) are the primary consumer of a VANET but networks may be supported by fixed infrastructure known as Road Side Units (RSUs). Nodes that wish to communicate with another node in the network may do so by routing through nodes to reach their destination, if not directly in range. Many routing protocols exist, however, in this paper we will focus on Ad hoc On-Demand Distance Vector Routing (AODV) [START_REF] Perkins | RFC 3561: Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF] which is one of the most commonly used.

Attacks on availability are of considerable concern to VANETs -particularly as reliance on applications requiring intervehicular communication increases. In this paper, we focus on the black hole attack. In this attack, a node falsely advertises itself as having the shortest route to a destination. After this route is selected, the node should relay packets from the source to the next hop on the route, but instead maliciously drops these packets thereby preventing communication between the source and destination nodes.

We have previously proposed a countermeasure to this attack for instances where there is a single malicious node present in a network. We consider the single malicious node scenario to be the base case of this problem and our work is intended to be incremental, gradually increasing the scope of detection and prevention afforded by our countermeasure. This paper proposes two new algorithms to extend our countermeasure to be able to detect and prevent against black hole attacks with multiple malicious nodes. We validate the efficacy of these new algorithms and our revised countermeasure with simulations of the attack and an implementation of our solution in Network Simulator-3 (NS-3) [START_REF] Riley | The NS-3 Network Simulator[END_REF]. Accurate detection and effective prevention of black hole attacks with our countermeasure is demonstrated in the results of these simulations. The use of our solution led to a corresponding increase in network performance against non-use in scenarios where a black hole attack was present.

This paper is structured hereinafter as follows: Section 2 discusses related work from the literature. In Section 3, we outline the concept behind a black hole attack and show how this attack is performed in practice. Section 4 concerns our proposed countermeasure to mitigate the threat posed by black hole attacks on VANETs. We first detail our previous work in this area, a solution to single malicious node black hole attacks. We then propose two new algorithms to expand the scope of this solution to detect and prevent against multiple malicious node black hole attacks. In Section 5, simulations undertaken and their parameters are described, while the results from these simulations are discussed in Section 6. Finally, Section 7 concludes the paper.

Related Work

A black hole attack is an attack vector that poses a threat across a wide range of disciplines and is not unique to the vehicular networking domain. MANETs, the parent network from which the VANET emerged, are particularly sensitive to this type of attack and much of the work regarding detection of prevention of these attacks has been focused in the MANET domain. Different approaches to countering this attack vector have been proposed, with reputation-based schemes among the most common. The use of collaborate Bayesian watchdogs [START_REF] Serrat-Olmos | Accurate Detection of Black Holes in MANETs using Collaborative Bayesian Watchdogs[END_REF], where each node monitors their neighbours' behaviour and assigns reputation values accordingly, yields accurate attack detection but at the expense of significant overhead from message passing and packet transmission monitoring of all neighbouring nodes. Fidelity tables, where each node essentially has a reliability level, have been used with some success [START_REF] Tamilselvan | Prevention of Co-operative Black Hole Attack in MANET[END_REF]. Here, when a node acts unreliably (e.g. no ACK is received) its fidelity level is decremented. When ACKs are received, it's fidelity level is incremented. When a node's fidelity level reaches 0 it is deemed to be a malicious node and is excluded from the network. This solution can counter multiple malicious node attacks but results show that its effectiveness is considerably reduced with increasing node speed, making it unsuitable for VANETs.

A number of efforts at mitigating black hole attacks have focused on the routing protocol itself as a means of preventing this attack. New protocols have been developed with this in mind, however, due to the prevalence of AODV, few have been adopted for use. Secure AODV (SAODV) is an extension of AODV proposed due to the lack of security offered at the routing layer [START_REF] Zapata | Secure Ad-hoc On-Demand Distance Vector (SAODV) Routing[END_REF]. It employs cryptographic means to offer security features (e.g. authentication) that AODV lacks. While not the author's intention, it indirectly offers limited protection against black hole attacks as a malicious node can only lie about itself and reduce the hop count in an RREP by one. However, this is the extent of its protection against this attack vector. Other protocols extending AODV have been designed specifically to offer protection against black hole attacks. One such protocol by [START_REF] Khamayseh | A New Protocol for Detecting Black Hole Nodes in Ad Hoc Networks[END_REF] modifies the AODV protocol to have each node maintain a trust table holding the addresses of reliable nodes. For a node to be added to another node's trust table, it must pass a behavioural analysis filter which considers link parameters of the other node's active connections and other historic information that nodes must store. This modification yielded a 13 -15% increase in Packet Delivery Ratio (PDR) for single and multiple malicious node attacks. However, the modified protocol lacks a means to remove a malicious node from a network and raises questions regarding the overhead incurred by nodes from having to store historic network data on its neighbours.

Intrusion detection systems have been adopted to tackle the problem of black hole attacks in MANETs. [START_REF] Alem | Preventing Black Hole Attack in Mobile Ad-hoc Networks Using Anomaly Detection[END_REF] used anomaly detection to develop an effective solution capable of detecting malicious nodes and preventing the attack thereafter. This particular scheme can be used with any number of malicious nodes and has a low network overhead between nodes. The disadvantage of this countermeasure is that each node protects only itself. Furthermore, a centralised node monitoring traffic flows is required, thus making such a solution impractical for use in a VANET. [START_REF] Mishra | A Novel Approach for Detecting and Eliminating Cooperative Black Hole Attack using Advanced DRI Table in Ad hoc Network[END_REF] propose using Data Routing Information (DRI) tables (which store information on packet forwarding by neighbouring nodes) in conjunction with probe packets to determine if a node is malicious. Another cooperative node, for acknowledging the probe packets, is required. Simulation results for this strategy show meaningful network performance improvements and that multiple malicious node attacks can be aptly detected. The authors do not reference the overhead incurred by such a solution, however, but do acknowledge that detection of malicious nodes remains a challenge.

Black Hole Attack

A black hole attack is an attack on availability and a type of Denial-of-Service (DoS) attack. In this attack, a malicious node fraudulently advertises itself as having the shortest route to a source node requesting a route to its destination. Then, after the source selects this route for use, the malicious node drops all data packets it receives, instead of relaying these to the next hop in the route. No message alteration or inspection takes place in this attack, rather, its goal is to prevent communication between nodes in a network.

We distinguish between a black hole attack and a grey hole attack. In the former, malicious nodes drop all data packets indiscriminately. In the latter, malicious nodes may selectively drop packets or discard them in line with a probability distribution. We are concerned only with black hole attacks in this paper. For scoping purposes, we assume that all honest nodes (i.e. non-malicious nodes) always act in good faith. Furthermore, we presume that there are multiple paths from a source node to its destination and vice versa. Finally, we assume that malicious nodes are always malicious and cannot change or spoof their identity to evade detection. There are practical ways in which this may be enforced, such as through Electronic Vehicle Identification (EVI) or integration of security hardware modules (e.g. Tamper Proof Hardware (TPH) and Electronic License Plates (ELP) (Al-kahtani, 2012)) into vehicles by manufacturers. Under AODV routing, when a source node requires a route, it broadcasts a RREQ to neighbouring nodes. RREQs are propagated through the network to neighbours, as shown in Figure 1, until the destination (or a node with a valid route to the destination) is reached. A RREP is then unicast back to the source.

In a black hole attack, a malicious node endeavours to be selected as part of an active route. As such, it is advantageous for malicious nodes to advertise themselves as having the shortest route possible -that they have a direct path to the destination -in response to any RREQ received. This is irrespective of whether such a path exists between the malicious node and the destination. As the malicious node has no intention of relaying the source's packets towards the destination, it is not concerned with having a route to the destination and so the malicious node forges an RREP stating that the destination is its next hop. This RREP is then sent back to the source node, as per Figure 2. It is the malicious node's hope that the source selects the false route it has replied with, as depicted in Figure 3. If so, the node starts to receive traffic to relay, which it discards -hence the name of the attack, the malicious node becomes a black hole for the source's traffic.

Figure 3: Active route with malicious node performing black hole attack

Variations of this attack present when more than one malicious node is introduced to the network. When multiple malicious nodes partake in a black hole attack, they do so independently. If these nodes were to act in concert, it would constitute a grey hole attack instead. We have identified two scenarios in which multiple malicious nodes may organise themselves (and which require different strategies to counter).

One Malicious Node per Route on Multiple Routes

In the first of the identified scenarios, the malicious nodes are organised such that there is only a single malicious node on any given route. As there are multiple malicious nodes present in the network in this instance, multiple routes will likely have a malicious node as a hop. This is akin to the single malicious node case of a black hole attack, albeit with multiple occurrences thereof within a single network. Figure 4

Multiple Malicious Nodes on Single Route

A more complex scenario occurs when multiple malicious nodes exist on a single route. Should two nodes independently of each other seek out a route to their counterpart, and two or more malicious nodes separate them, then it is probable that each will fall victim to a black hole attack perpetrated by a different malicious node to the other. Accordingly, both will be presented a different, non-existent, route by the respective malicious node. This makes detection of the black hole attack markedly more difficult for our countermeasure. This is due to each endpoint of the route initiating detection procedures on a different malicious node, and consensus requirements in blacklisting. A visual representation of this scenario is given in Figure 5.

Proposed Countermeasure

Previously, we proposed a solution to prevent single malicious node black hole attacks [START_REF] Tobin | An Approach to Mitigate Black Hole Attacks on Vehicular Wireless Networks[END_REF]. We consider this to be the base case for such an attack. Now, we propose two new algorithms that build upon our previous solution to expand its scope. This incremental work is intended to detect and prevent against black hole attacks in cases of both a single malicious node and multiple malicious nodes present in the network. This Section begins by discussing our previous work on this countermeasure and then goes on to propose two new algorithms for black hole attacks with multiple malicious nodes.

Previous Work -Single Malicious Node Attacks

Our prior work serves as the foundation for our countermeasure. It solely mitigates the threat of black hole attacks with a single malicious node. Our solution takes a 3-step approach to detecting malicious nodes and preventing the attack by removal of such nodes from participation in the network. These steps consist of: attack detection, node accusation, and malicious node blacklisting. Once an attack is detected, and the offending node isolated, measures are taken to prevent the node from causing further disruption or joining other networks. Part of this countermeasure requires that nodes can digitally sign (and can verify a digital signature). All nodes should support asymmetric cryptography and possess a public-private key pair to fulfil this requirement. The OpenPGP standard [START_REF] Callas | RFC 4880: OpenPGP Message Format[END_REF] is proposed for this purpose.

Attack Detection

Attack detection is complicated by the inherently lossy nature of the shared wireless medium of VANETs. Indiscriminate public user access and rapidly changing network topologies further compound this. Typically, when network connectivity is lost or a link goes down, an intermediate node along a route will detect this (as all nodes periodically monitor neighbouring link status). Upon detection, the node will transmit a Route Error (RERR) message back along the route, informing nodes that the route is no longer valid. This is how nodes become aware of a problem with packet transmission, particularly with stateless protocols such as UDP. Unfortunately, this is not the case when a network is subjected to a black hole attack. As nodes do not lose the link to the malicious node, the routing protocol offers no assistance in detecting packet non-delivery.

Under AODV, nodes do not know the full composition of a route. Instead, any node with a route to a particular destination has knowledge only of the next hop and the number of hops. This hinders attack detection. Thus, to facilitate attack detection we modify the RREP message format to have intermediary nodes append their hop number and IP address to any RREP received and being relayed. This adds minimal overhead to routing protocol messaging. A standard RREP is 160 bits. Our modified RREP, for any given hop in a route, has a size of 160 + 40n bits, where n is a given node's hop number. Considering the throughput of modern IEEE 802.11 standards and typical number of hops in a VANET route, we conclude that this overhead is negligible.

We propose a malicious node detection scheme based on route backtracking and querying of intermediate nodes for statistics to determine the malicious node. This is achieved by analysing statistics (e.g. packets sent/received) for each node and finding the node causing the discrepancy, thus revealing the malicious node. There are many suitable network statistics for this purpose, however, our experiments have shown the packets sent and received counter to be a reliable indicator for malicious node detection, consistently yielding good results. In our implementation, the triggering node will query the next hop (and so on) for the number of packets it received from its previous hop and the number of packets it relayed to its next hop. Should the node fail to reply to such a request, the node is flagged as potentially malicious. This attack detection step is triggered by a source or destination node noticing a lack of expected replies (or missing ACKs) with no reported link lossage (e.g. no RERR received). Application layer services may be involved in triggering this step.

If a node is flagged, and a discrepancy is not large enough to support an accusation, the triggering node proceeds to alert its counterpart (e.g. the destination node if the source is the triggering node) to begin attack detection using an alert message that is sent on an alternate route without the flagged node or its previous hop. The alert message contains details of the active route, the alternate route, and the IP addresses of the flagged node and the previous hop in the active route. Where there is no alternate route excluding both of these nodes, the triggering node attempts to send the alert on alternate routes excluding one of these nodes, using a timeout before proceeding to the next possible route. The alert must be acknowledged by the other party and as a result, if one alternate route fails to receive an alert ACK, this can infer that the flagged node on this route is the malicious node and support an accusation thereof.

Upon receiving an alert message, the counterpart node begins attack detection in the same manner as the triggering node. After reaching and querying the flagged node, if there is still no reply from this node then the counterpart moves to accuse this node. Should this node reply, this suggests that it is in fact the next hop that is the malicious node (the 'previous hop' in the alert message). This can be confirmed by querying the next hop and failing to receive a reply, which triggers node accusation. If both nodes reply, the counterpart node looks for a discrepancy in the statistics received to derive which is the malicious node. Failing that, the counterpart continues backtracking along the route. If the triggering node is reached, attack detection is dropped by both parties as this indicates no black hole attack along the route.

Node Accusation

Node accusation is ordinarily started by the node receiving an alert message, though either source or destination may accuse a node along its route following attack detection. Accusation involves sending an accusation message to the other party on an alternate route excluding the accused node. An accusation message contains details of the active route, the IP address of the accused node and its previous hop, and packet statistics as reported by both these nodes for verification. This message also requires acknowledgement.

On receipt of an accusation message, the receiving node moves immediately to querying the accused node and the other node included in the accusation message. With the packet statistics from the other end of the route in addition to the statistics it received from its own query, the receiving node now determines if the accused node is acting maliciously or not. If the receiving node concurs and upholds the accusation, the receiving node moves to blacklist the accused. Without concurrence by both parties, the accusation is dropped thus terminating the countermeasure process.

Malicious Node Blacklisting

A blockchain [START_REF] Nakamoto | Bitcoin: A Peer-to-Peer Electronic Cash System[END_REF] is used as the distributed public ledger maintaining all blacklist entries. As all nodes hold a copy of the blockchain, a blacklist is not limited to any short lived VANET but rather is global, applying to all VANETs. The effect of a blacklist entry is that all nodes subscribed to the blockchain will refuse to communicate with (or through) the blacklisted node, excluding it from participation in any VANET.

Blacklist entries are time-limited, set by policy, thereby allowing the possibility of node redemption. A blacklist entry consists of the offending node's unique identifier, a timestamp of when the entry was created and of when it is due to expire. In addition, the unique identifiers of source and destination nodes, their public keys, and a digital signature on the blacklist entry by each node are also included.

New Algorithms Proposed -Multiple Malicious Node Attacks

Having examined the literature to identify black hole attack adaptations with multiple malicious nodes, it appears only two true variations of multiple malicious node black hole attacks exist. Other proposed instances of this attack that are of a co-operative or selective nature instead fall under the remit of grey hole attacks, despite erroneous labelling as black hole attacks at times. The two scenarios that are within the scope of black hole attacks for multiple malicious nodes are outlined in Sections 3.1 and 3.2.

Algorithm 1 -The Recursive Element

The first algorithm deals with what essentially multiple single malicious node attacks within a VANET, as described in Section 3.1. This scenario has a number of malicious nodes (at least two), however, in any given route there exists no more than one malicious node. Our previously proposed countermeasure is ill-equipped to deal with this scenario. This is because our countermeasure will hang during the sending of an alert message on an alternate route if this route is also subject to a separate black hole attack by a different malicious node. The first revision of our solution furthermore fails to trigger attack detection on the alternate route, even if it appears there is an active black hole attack.

To protect against this attack variant, we modify our previously proposed attack detection step. We amend this step such that when an alert message does not receive a reply, attack detection is triggered on the alternate route that the alert message was sent on, if necessary (e.g. no RERR received). This happens recursively if the same is true of further alternate routes. A timeout is added as it is necessary should nodes go out of range while the countermeasure executes on other routes.

Algorithm 2 -Multiple Detection Cooperation

In a scenario where more than one malicious node is present along a single active route, such as in Figure 5, it is likely that source and destination nodes would each detect a different malicious node. On the triggering of the detection step of our countermeasure, the source and destination nodes will detect the malicious node closest (in terms of hops) to them. This raises issues in our previous iteration of this countermeasure when it comes to the counterpart node verifying the accusation as during the backtracking algorithm, the malicious node closest to the counterpart will instead be detected as the malicious node rather than the accused node.

To resolve the issues this attack scenario presents, we must modify our attack detection and accusation verification steps. The countermeasure is modified such that when both source and destination nodes have made a detection and send the respective counterpart node an alert message or accusation message, the first received of these messages is dealt with first. If both endpoint nodes have independently made detections at this point, the counterpart node halts its execution of the countermeasure while it handles the alert or accusation message it has received. The counterpart node resumes its execution of the countermeasure on its detected potentially malicious node when finished. Furthermore, the counterpart node uses its detection (if one has separately been made by it at this stage) to its advantage in excluding this flagged node, where possible, when selecting an alternate route.

The backtracking algorithm is modified to cater for detections by the counterpart, following receipt of an alert message, of a node (or nodes) other than the flagged node. The counterpart node adds the detected potentially malicious node to a list and an alert message is sent flagging this node (for each node on the list). These other detections are handled upon completion of the current execution of the countermeasure. The alert messages being sent during the current run of the countermeasure serve to build a list of potentially malicious nodes to be handled using this countermeasure on a First In, First Out (FIFO) basis, and to allow the triggering node to best select an alternate route to its counterpart. The backtracking algorithm continues as before however detected nodes other than the flagged node are isolated and an alternate route to hops beyond any detected nodes is found. If the flagged node is found to be non-responsive when reached, the counterpart node moves to accuse the flagged node.

The accusation step is amended to use knowledge of other detections when selecting an alternate route. Where possible, an alternate route excluding nodes on the detection list will be chosen. Furthermore, in order to verify an accusation, the node receiving an accusation message is required to query the next hop after the accused node on its active route. As it can no longer be assumed that only a single malicious node is present on an active route, instances where an accusation message is sent without a prior alert message must trigger attack detection backtracking instead of directly moving to query the accused node. This is to prevent false positives caused instead by another undetected malicious node on the active route. The node verifying an accusation must also use an alternate route that excludes the node prior to the accused node on the active route in querying the accused node or its next hop. This, again, is to prevent false positive detections. Taking Figure 5 as an example, if the destination node has sent an accusation message accusing node G of being malicious, the source node querying node G through node F would result in node G being falsely verified as acting maliciously, when in fact it is nodes C and F that are malicious. By having the source node exclude node F when querying nodes G and C, this prevents the false detection of node G as a malicious node.

Simulation Details

VANET simulation was accomplished using Network Simulator-3 (NS-3). The different black hole attack variants previously described were implemented through various simulation scenarios. The resulting effect on network dynamicity, the attack vector, and the efficacy of our countermeasure was observed. To ensure a particular attack variant remained constant throughout a simulation and did not change due to movement of nodes, node positions were fixed and a constant mobility model installed. Some scenarios were repeated with a more realistic mobility model installed. We intend to run further simulation scenarios modelling practical situations going forward. Control simulations with no attack (both with and without our countermeasure implemented) were also undertaken to establish a baseline. All simulations were run a minimum of ten times and results averaged over these runs. Simulation parameters are outlined in Table 1. The scenarios simulated can broadly be classified into four main groups, which we label for clarity. These scenario groups are as follows: a control scenario with no attack and no solution implemented (NA_NS); a control scenario with no attack but with our solution implemented (NA_WS); a scenario with a black hole attack performed on the network and no solution in place (WA_NS); and, a scenario with a black hole attack performed on the network and with our solution in place (WA_WS). The latter two black hole attack groups can be further subdivided into the following subgroups: a single malicious node black hole attack (BH_SN); a multiple malicious node black hole attack with one malicious node at most per route (BH_MN_1PR); and, a multiple malicious node black hole attack with multiple malicious nodes per route (BH_MN_MPR). Several metrics were recorded during simulation runs to evaluate the effectiveness of our countermeasure. These included: detection time, detection accuracy (i.e. false positives/false negatives), average throughput, and PDR. Figure 6 shows us the packet delivery ratio, calculated each second, for two control and two multiple malicious node black hole attack scenarios over a 100 second window. We can see that in the attack scenarios, our countermeasure begins to restore the PDR as it detects and blacklists malicious nodes from the network. Detection in the BH_MN_1PR scenario is delayed due to a range of alternate routes being subject to a black hole attack. In the BH_MN_MPR scenario, an additional dip in PDR is seen after 38 seconds as additional malicious nodes are present on a selected alternate route. Fluctuations in PDR are attributable to nodes going out of range and retransmissions. Figure 6 also shows us the network throughput. Both attack scenarios degrade the aggregate network throughput however this is restored quickly with our countermeasure in place.

Results Discussion

There was a 0.89% false positive detection rate overall.

Conclusion

This paper sought to build on our previous countermeasure to single malicious node black hole attacks in vehicular wireless networks. We described two new variants of this attack where multiple malicious nodes undertake a black hole attack on a network. Furthermore, we introduced two new algorithms to expand the scope of our solution to detect and prevent against both identified scenarios. Simulation results show that this is a viable attack vector capable of effectively preventing communication between selected targets and causing a significant reduction in overall network packet delivery and throughput. As expected, the introduction of multiple malicious nodes produced a more drastic and substantial denial of service throughout the network. Implementation of our proposed algorithms to our existing countermeasure resulted in accurate attack detection and, similarly, prevention through blacklisting of malicious nodes. Network performance began to restore as blacklisting took effect. Further simulations are planned going forward with a focus on optimisation of our solution. Future work will target detection of a variety of grey hole attacks and expansion of our countermeasure to mitigate the threat of these attack vectors.

Figure 1 :

 1 Figure 1: RREPs back propagated to the source node after an RREQ reaching the destination.

Figure 2 :

 2 Figure 2: RREQs propagating through the VANET, however, in this case a malicious node forges an RREP stating dishonestly that it has a direct path to the destination.

  depicts this scenario.

Figure 4 :

 4 Figure 4: Two Malicious Nodes, (C) and (E), Performing a Black Hole Attack on Separate Routes (One Malicious Node per Route)

Figure 5 :

 5 Figure 5: Two Malicious Nodes, (C) and (F), Performing Black Hole Attack on a Single Route (A-F-G-C-D-E)

Figure 6 :

 6 Figure 6: Packet Delivery Ratio and Aggregate Throughput for Multiple Simulation Scenarios

Table 1 : Simulation Parameters

 1

	Number of Nodes	5, 10 -50 (step: 10)
	Number of Malicious Nodes	Variable
	Wireless Interface & Bandwidth 802.11p at 5.9 GHz
	Antenna	Omnidirectional
	Transmission Range	Dynamic
	Traffic Type	Constant Bit Rate (CBR)
	Mobility Model	Constant Position, Constant Velocity, Random Waypoint
	Node Speed	5, 10, 15, and 20 m/s
	Simulation Time	300 s
	Map Grids	2 (1 blank grid; 1 urban map grid)
	Grid Area	1000 m x 1000 m
	Runs per Simulation	10

Acknowledgements

This work was supported with the financial support of the Science Foundation Ireland grant 13/RC/2094 and co-funded under the European Regional Development Fund through the Southern & Eastern Regional Operational Programme to Lero -the Irish Software Research Centre (www.lero.ie)


Marianne Noel

Frédérique Bordignon

The pitfalls of signature. Questionning affiliation in French research and higher education institutions

The pitfalls of signature -Questioning affiliation in French higher education institutions Marianne Noël -LISIS, Univ Paris-Est, CNRS, INRA, UPEM, ESIEE Paris, Champs-sur-Marne, France -noel@ifris.fr @MNoel75 Frédérique Bordignon -Pôle IST, Ecole des Ponts ParisTech, Champs-sur-Marne, France -frederique.bordignon@enpc.fr @freddie2310

Researchers

High-level managers

Scholarly communication specialists

Case study: A prestigious school of engineering set up for 20 years in a large university campus Injunctions, paradoxes, unexpected facts, incongruities…

Actors are pulled back and forth between conflicting and non-coordinated demands and emphasize unintended effects of the tagging/tracking activities.

Researchers: a confusing situation due to multi-affiliations status; uncomfortable feeling with the signature that should be technical and not personal; affiliations reflect multiple socialities.

Scholarly communication specialists: job profile moving to "data scientist" (from library to bibliometrics); necessity to collaborate with publishers (Elsevier) despite disagreement upon Open Access.

Publishers: selling products in a more competitive landscape in the frame of public procurements.

High-level managers: key issues at stake like increasing visibility, reliability of benchmarkings and better self-understanding.

-

  Unexpected effect: Analyses reveal that, despite Civil engineering being the main activity of the institution, it is not the most important domain where researchers publish their work in. It has consequences on its position in international rankings. Perspectives: Work in progress… Recommendations and efforts are quite ineffective. Is it specific to the French case? Development of new tool: Opalia -of references exported from Scopus, WoS and the French Open Archive HAL -Manual sorting by information specialists -Generation of charts and tables for analyses Collaboration with data providers: -Scopus: implementation of a new way to display information -WoS: providing a list of the insitution name variants in order to improve the database algorithm Background and context: -Accountibility regime (Wouters, 1999) -Challenge for individuals and institutions to be easily identified -10 years of new funding schemes and structures in France (the "millefeuilles" pastry phenomenon) Method: A participatory/reflexive approach


A Omar Portillo-Dominguez
email: andres.portillo-dominguez@ucdconnect.ie

Miao Wang
email: miao.wang@ucd.ie

Damien Magoni
email: magoni@labri.fr

Philip Perry
email: philip.perry@ucd.ie

John Murphy
email: j.murphy@ucd.ie

Load Balancing of Java Applications by Forecasting Garbage Collections

Modern computer applications, especially at enterprise-level, are commonly deployed with a big number of clustered instances to achieve a higher system performance, in which case single machine based solutions are less cost-effective. However, how to effectively manage these clustered applications has become a new challenge. A common approach is to deploy a front-end load balancer to optimise the workload distribution between each clustered application. Since then, many research efforts have been carried out to study effective load balancing algorithms which can control the workload based on various resource usages such as CPU and memory. The aim of this paper is to propose a new load balancing approach to improve the overall distributed system performance by avoiding potential performance impacts caused by Major Java Garbage Collection. The experimental results have shown that the proposed load balancing algorithm can achieve a significant higher throughput and lower response time compared to the round-robin approach. In addition, the proposed solution only has a small overhead introduced to the distributed system, where unused resources are available to enable other load balancing algorithms together to achieve a better system performance.

I. INTRODUCTION AND RELATED WORK

Enterprise applications commonly require to achieve fast response time and high throughput to constantly meet their service level agreements. These applications make wide use of variants of distributed architectures, usually using some form of load balancing to optimise their performance. Since then researchers have made efforts to improve the business intelligence of load balancers to effectively manage workloads. For example, the authors of [START_REF] Rupprecht | Dynamic load balancing in data grids by global load estimation[END_REF] proposed a technique to estimate the global workload of a load balancer to use this information in the balancing of new workload. Meanwhile, the work on [START_REF] Laskowski | Dynamic load balancing based on applications global states monitoring[END_REF] presented a framework for processor load balancing during the execution of application programs. Regarding Java technologies, the authors of [START_REF] Carmona | Adaptive Load Balancing between Static and Dynamic Layers in J2EE Applications[END_REF] enhanced a load balancing algorithm for Java applications by considering the utilisation of the JVM threads, heap and CPU to decide how to distribute the load. Similarly the work in [START_REF] Liu | Research on self-adaptive load balancing in EJB clustering system[END_REF] proposes a function to calculate the utilisation of an Enterprise JavaBean (EJB) and then uses this information to balance the load among the available EJB instances. However, Garbage Collection (GC) metrics have not been considered so far. This gap offers an interesting niche which is yet to be exploited.

GC is a core feature of Java which automates most of the tasks related to memory management. However, when the GC is triggered, it has an impact on the system performance by pausing the involved programs. Even though milliseconds pauses caused by GC does not necessarily lead to a harmful problem, delays of hundreds of milliseconds, let alone full seconds, can cause trouble for applications requiring fast response time or high throughput. This is more likely to occur in the Major Garbage Collection (MaGC), which has the most expensive type of GC pauses [START_REF]Memory Management in the Java HotSpot Virtual Machine[END_REF].

Many research studies have provided evidence to quantify the performance costs of the GC. For example, in [START_REF] Xian | Garbage Collection : Java Application Servers' Achilles Heel[END_REF] authors identified the GC as a major factor degrading the behaviour of a Java Application Server (a traditional Java business niche) due to the sensitivity of the GC to the workload. In these experiments the GC took up to 50% of the execution time of the Java Virtual Machine (JVM), involving pauses as high as 300 seconds. The MaGC represented 95% of those pauses on the heaviest workload. Similarly, a survey conducted among Java practitioners [START_REF] Snatzke | Perf. survey[END_REF] reported GC as a typical area of performance issues in the industry. For these reasons, it is commonly agreed that the GC plays a key role in the performance of Java systems.

The goal of this work is to predict the MaGC events and use this information in the decision making process of a load balancer to improve the system performance. Our solution consists of two algorithms. A load balance algorithm which avoids sending any incoming workloads to the application nodes which are likely to suffer MaGC, and an forecast algorithm to predict the MaGCs. The experiment results have shown that this strategy offers a significant performance gain: The average response time of the tested applications decreased between 74% and 99%, while the average throughput increased between 4% and 51%.

In summary, the contributions of this paper are: 1) A novel load balance algorithm that uses MaGC forecasts to improve the performance of distributed Java systems. 2) A novel forecast algorithm that enables Java systems to predict when a MaGC event will occur. 3) A validation of the algorithms consisting of a prototype and two experiments. The first proves the accuracy of the MaGC forecast. The second demonstrates the performance benefits of using the forecast for load balancing.

II. BACKGROUND

Memory Management in Java. GC is a form of automatic memory management which offers significant software engineering benefits over explicit memory management: It frees programmers from the burden of manual memory management, preventing the most common sources of memory leaks and overwrites [START_REF] Wilson | Uniprocessor Garbage Collection Techniques[END_REF], as well as improving the programmer's productivity [START_REF] Phipps | Comparing Observed Bug and Productivity Rates for Java and C++. Software Practice and Experience[END_REF]. Despite these advantages, the GC comes with a cost (as discussed in Section I).

Nowadays the most common heap type in Java is the generational heap 1 , where the objects are segregated by age into memory regions called generations. New objects are created in the Youngest generation. The survival rates of younger generations are usually lower than those of older ones, meaning that younger generations are more likely to be garbage and can be collected more frequently than older ones. The GC in the younger generations is known as Minor GC (MiGC). It is usually inexpensive and rarely causes a performance concern. MiGC is also responsible of moving the live objects which have become old enough to the older generations, meaning that the MiGC plays a key role in the memory allocation of older generations. The GC in the older generations is known as MaGC and is commonly accepted as the most expensive GC due to its performance impact [START_REF]Memory Management in the Java HotSpot Virtual Machine[END_REF]. Also, it is not possible to programmatically force the execution of the GC [START_REF] Manning | Scjp sun certified programmer for java 6 exam[END_REF]. The closest action a developer can perform is to call the method System.gc() to suggest the JVM to execute a MaGC. However, the JVM is not forced to fulfill this request and may choose to ignore it. The usage of this method is discouraged by the JVM vendors2 because the JVM usually does a much better job on deciding when to do GC.

Garbage Collection Optimisation & Memory Forecast.

Multiple research works have proposed new GC algorithms [START_REF] Cho | Scheduling GC in dynamic RT systems with statistical timing assurances[END_REF], [START_REF] Kalibera | Replicating real-time GC for Java[END_REF], [START_REF] Pizlo | A study of concurrent real-time Garbage Collection[END_REF], [START_REF] Siebert | Limits of parallel GC[END_REF] that have smaller performance impacts on the applications. Even though all these works have helped to reduce the impact of the MaGC, GC remains a concern due to the different factors that can affect its performance.

Memory forecast is also an active research topic, looking for ways to invoke a GC only when it is worthwhile. For example, the work presented in [START_REF] Wegiel | Dynamic prediction of collection yield for managed runtimes[END_REF] exploits the observation that dead objects tend to cluster together to estimate how much space would be reclaimable to avoid low-yield GCs. However memory forecasts alone do not provide enough information to know when the next MaGC would occur.

III. PROPOSED SOLUTION

A. Use case: Adaptive Load Balancer

In a distributed Java system, it is preferable that the occurrence of MaGCs in the individual nodes do not affect the performance of the system. To achieve this goal, a system can take different actions. For instance, a system might change its workload schedule to avoid the impact of the MaGCs or encourage a MaGC when a resource load (i.e. CPU) is low. Among the potential use cases, our work centered on enhancing the performance of a load balancer. This use case was selected because variants of this distributed architecture are commonly used at enterprise-level. This scenario is shown in Figure 1, where the load balancer selects those nodes which are less likely to suffer a MaGC pause as optimal nodes for given workloads. This strategy can keep the system performance safe from any major MaGC pauses.

B. Major GC Forecast Algorithm

The next sections describe our proposed forecast algorithm. The below definitions will be used on the algorithm discussion:

Time is always expressed as the number of milliseconds that have passed since the application started.

Young/Old Generation Samples are composed of a timestamp and the usage of the corresponding memory generation.

MiGC sample is composed of the start time, the end time and the memory usage before and after the latest MiGC event.

Observations are used in a statistical context and are composed of one independent and one dependent values. When the dependent value does not contain historical data, the observation is referred as a forecast observation.

Steady state is the state an application reaches after the JVM finishes loading all its classes. It is assumed that this state has been reached if the number of loaded classes remain unchanged for a certain number of consecutive samples. After it occurs, the other phases are iteratively done to produce MaGC forecasts continuously: New samples are retrieved from the monitored JVM in the Data Gathering phase. Then new observations are generated using the new samples in the Observations Assembly phase. Next the Forecast Calculation occurs. Finally, the logic awaits a Sampling Interval before a new iteration starts. This loop continues until the monitored application finishes.

Our algorithm is designed to work on generational heaps, as it is the most common type of Java heap. It only uses standard data that can be obtained from any JVM (such as GC) to make it easy to implement either within or outside the JVM. If the algorithm is implemented within the JVM, the interaction with potential consumers would be simplified. If it is implemented outside the JVM, the implementation would work with any JVM currently available, facilitating the adoption.

2) Detailed Algorithm: It is presented in Algorithm 1, and its phases are explained in the following sections. • Time between MiGCs (∆ T M iGC ): How much time elapsed between the latest two MiGCs.

• YoungGen Memory Allocation (∆ YMA M iGC ): How much memory was used to create new objects between the latest two MiGCs. • OldGen Memory Allocation (∆ OMA M iGC ): How much OldGen Allocation occurred because of the latest MiGC (meaning that some objects have became old enough to be moved to the OldGen by the latest MiGC). The above metrics are added up into their respective totals (e.g., Total Time between MiGCs) to keep track of how the metrics grow through time. This data is the key input of the regression models used by the algorithm, as explained below.

Observations Assembly. Two types of observations are generated and added to their histories. Each is composed of one independent (y axis) and one dependent (x axis) values: The first type (YoungGen-OldGen) captures the relationship between the memory allocation rates (MAR) in the Young and Old Generations. This captures how the Old Generation grows (eventually leading to a MaGC) in relation to the object allocations requested by the application (which occur in the Young Generation). In this observation the dependent value is the Total YoungGen Memory Allocation and the independent value is the Total OldGen Memory Allocation. The second type of observation (Time-YoungGen) captures the relationship between the time and the Young MAR. Here the dependent value is the Total Time between MiGCs and the independent value is the Total YoungGen Memory Allocation. Forecast Calculation. This phase first evaluates if the application has reached the steady state. If so, two projections are calculated using linear regression models (LRM). The first projection corresponds to how much memory allocation needs to occur in the Young Generation before the free memory in the Old Generation gets exhausted (hence triggering a MaGC). This is calculated by initializing a LRM with a subset of YoungGen-OldGen observations (defined by the FWS) and then feeding the LRM with a forecast observation whose independent value is the sum of the current Total OldGen Allocation and the free OldGen memory. This is shown in Figure 3. In this example, the free OldGen memory is 1,000MB. As our Total OldGen Allocation is also 1,000MB, the independent value of our forecast observation is 2,000MB. Using the observations within the FWS (the rounded rectangle), the LRM predicts how much memory allocation needs to occur in the YoungGen before the next MaGC occurs (4,500MB).

The second projection is the core output of this algorithm: The MaGC forecast time. It is calculated by initializing a LRM with a subset of Time-YoungGen observations and feeding it with a forecast observation whose independent value is the result of the first projection. This is represented in Figure 4. Using the observations within our FWS, the LRM predicts when the necessary memory allocation in the YoungGen will occur (4,500MB in our example), consequently triggering the next MaGC (around the millisecond 13,000 in our example). Sampling Wait Period. Finally, the process waits the number of milliseconds configured in the Sampling Interval before starting the next round of iterative steps of the algorithm.

C. MaGC-Aware Load Balancing

To assess the performance benefits that can be achieved by adapting the load balancing based on the MaGC forecast information, we modified the well-known round robin load balancing algorithm 3 . Our proposed algorithm is presented in Algorithm 2. It requires two inputs: The Number of available nodes from which the algorithm will select the next node to send workload; and the MaGC Threshold, which is the time threshold when a node stops being considered a feasible candidate because the next MaGC is too close. For example, if the MaGC Threshold is 5 seconds and the current time is 4:00:00PM, any nodes which report a MaGC forecast between 4:00:00PM and 4:00:05PM will be skipped as their forecasts fall within the configured MaGC Threshold.

When compared against the normal round robin, our algorithm has two differences. The main one is that it performs an additional check to adapt the selection of the next node to a close MaGC event. This check reviews if the pre-selected node (as per the normal round-robin logic) will suffer a MaGC within the MaGC Threshold. If it does, the node is skipped and the next available node is evaluated (lines 11 to 15). The second change is an escape condition (the forecastTries variable) which counts the number of evaluated nodes to prevent an infinite loop in case all nodes are about to suffer a MaGC within the MaGC Threshold. If this occurs, the algorithm would behave as a normal round robin algorithm.

D. Prototype Implementations

MaGC Forecast Algorithm. This prototype was developed external to the JVM, using Java Management Extension (JMX) 4 to interact with the monitored JVM. This technology was chosen because it is a standard component of Java which can retrieve all needed information (e.g., GCs).

MaGC-Aware Load Balancing Algorithm. This prototype was built on top of the Central Directory5 , which is a lightweight load balancer. This solution was chosen because it is open source and developed in Java, characteristics which facilitated its integration with the MaGC forecast prototype.

IV. EXPERIMENTAL EVALUATION A. Experiment #1: MaGC Forecast Accuracy

Environment. All experiments were performed in a virtual machine (VM) equipped with 3 CPUs, 10GB of RAM, and 50GB of HD; Linux Ubuntu 12.04L 64-bit, and Oracle Hotspot JVM 7. The JVM was configured to initialise its Java Heap to its maximum size to keep it constant during the experiments. The calls to programmatically request a MaGC were disabled.

Java Benchmarks. The DaCapo6 benchmark 9.12 was chosen because it stresses the GC system more than other benchmarks (as proved in [START_REF] Blackburn | The DaCapo Benchmarks: Java Benchmarking Development and Analysis[END_REF]) and it also offers a wide range of application behaviours to test. For each benchmark, the largest Sample size was used (among the available pre-defined sizes 7 ). Also different Number of iterations (in increments of 5) and Heap sizes (in increments of 50MB) were tried until achieving successful executions that triggered MaGCs. These configurations are summarized in Table I. Also, a Warm-up timeframe of 5 seconds was found to be big enough to allow all programs to finish loading their classes before the first forecast was generated.

MaGC Forecast Algorithm parameters. As explained in Section III-B, this algorithm requires 3 parameters. To evaluate the behaviour of the algorithm to the FWS, a broad range of values was tested (2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048 and 4096). A value of 100ms was selected as Sampling Interval, assuming that no more than one GC would occur within that timeframe (hence not missing to sample any GC). Finally, a Warm-up Window Size of 50 was used (the result of dividing the Warm-up timeframe by the Sampling Interval).

GC strategies. Three of the most commonly used GC strategies 8 in the industry were selected: Serial GC is preferable for client JVMs, Parallel GC is better for server JVMs except when response time is more important than throughput. If so, Concurrent GC is preferred.

Metrics. The key metric used was the Forecast Error (FE), which is the ratio of the absolute forecasting error as a proportion of the time elapsed since the previous MaGC:

F E = (F T -RT ) (RT -P RT ) ( 1
)
where FT is the Forecast Time of when the next MaGC will occur, RT is the Real Time when the MaGC occurs and PRT is the Real Time when the Previous MaGC occurred. FE=0 means a perfect match between the forecast and the reality. FE>0 means the real MaGC occurred before the forecast, and FE<0 means the real MaGC occurred after the forecast. It is usually expressed as a percentage to be comparable among different programs. To illustrate the metric, consider a case where FT was 15 sec since the application started and RT was 14.8 sec. Assuming PRT was 10 sec, FE would be 4.17%. Experimental Results. The objective was to assess the accuracy of the forecast algorithm. Even though the results varied among the different GC strategies, it was possible to achieve a Forecast Error (FE) below 10% for all the benchmarks. These results are presented in Figure 5. As no single FWS achieved the lowest FE for all benchmarks, the analysis centered in understanding the factors behind the preferred FWS. As an initial step, the results were sorted by the average number of MiGCs between MaGCs (M iGC AV G ). This criterion was chosen because it captures the relationship between the allocation needs of an application and the heap size (major factors influencing the GC, as proved by [START_REF] Mao | Influence of program inputs on the selection of garbage collectors[END_REF] and [START_REF] Singer | The economics of garbage collection[END_REF] respectively). The smaller the M iGC AV G is, the more frequent the application exhausts its Old Generation memory. If the value is close to zero (i.e. 5 or less), the application is close to an Out-Of-Memory exception. On the contrary, a value far from zero (i.e. 1,000 or more) indicates that the Old Generation is infrequently exhausted. The results showed a relationship between the M iGC AV G and the preferred FWS: If an application has a high M iGC AV G , a large FWS is preferred because a small one does not capture the behaviour of the allocations in the Old Generation, which happens infrequently. Similarly, if an application has a low M iGC AV G , a small FWS works better. This tendency is visually shown in Figure 6 and experimentally proved in Figure 7.

To further explore the sensitivity of the algorithm to the FWS, the results were analyzed with the coefficient of variation 9 M iGC CV (standard deviation of the M iGC AV G depicted as a percentage of the average) to compare the applications in terms of variability. This analysis showed that the higher the value of M iGC CV (reflecting a more heterogeneous behaviour of the application in terms of memory usage), the more sensitive the algorithm is to changes in FWS. When this occurs, a more precise selection of FWS is required to achieve a low FE. On the contrary, if the M iGC CV is low, a broader range of FWS can be used. Figure 7 exemplifies these two scenarios: h2-Serial GC has a low M iGC AV G [START_REF] Singer | The economics of garbage collection[END_REF], so smaller FWS are preferable. As h2 also has a high M iGC CV (70%), it requires a more exact FWS range (between 2 and 16).

On the contrary, larger FWS are preferable for tomcat-Serial GC because it has a high M iGC AV G (12673). As tomcat also has a low M iGC CV (7%), a low FE can be achieved using a broader FWS range (between 1024 and 4096).

In conclusion, this experiment proved that the forecast algorithm can achieve a low FE (below 10%) when configured properly. Also two relevant factors to consider in the selection of the FWS (M iGC AV G and M iGC CV ) were identified.

B. Experiment #2: MaGC-Aware Load Balancing

Environment. It was composed of seven VMs: Five application nodes, one load balancer and one load tester (using Apache JMeter 2.9 10 ). All VMs had the characteristics described in the Experiment #1.

Java Benchmarks. From the DaCapo suite, the two programs closest to our use case were selected (tradebeans and tradesoap). Internally they leverage on the DayTrader benchmark 11 which simulates an online stock trading system. This benchmark ran over a Geronimo Application Server12 2.1.4 with a 10GB heap, and an in-memory Derby 13 database.

Load Balance Algorithms. Our algorithm was compared against the normal round robin algorithm. To compensate the Forecast Error (FE) of the MaGC forecast, the MaGC Threshold was set to the F E AV G of the tested programs (5 seconds). Internally, our forecast algorithm used a FWS of 64.

GC. Among the strategies used in the experiment #1, the two which suffer the longest pauses [START_REF]Memory Management in the Java HotSpot Virtual Machine[END_REF] (benefitting more from our load balance algorithm) were used: Serial and Parallel.

Metrics. Throughput (tps) and response time (ms) were collected with JMeter. The CPU (%) and memory (MB) utilisations of the load balancer were collected with nmon 14 .

Experimental Results. The objective was to assess the benefits of load balancing based on the MaGC forecast. Two types of runs were performed for each program and GC strategy: One used the normal round robin algorithm and was considered the Baseline (BL). The other type used our load balance algorithm (GCLB). Each run involved 150 concurrent users, lasted approximately 30 minutes and produced around 50,000 transactions. Originally we considered to also compare our algorithm against a reactive strategy, where the workload got adapted once a MaGC occurs. However this strategy could not be implemented because it is not possible to know, from a JVM, when a GC is happening (only when it has ended) 15 . 14 The results proved that considering the MaGC forecast in the load balance logic improves significantly the performance of the system. The average response time (RT AV G ) was reduced between 74% and 98.9%, while the maximum response time (RT M AX ) was reduced between 57.5% and 94.7%. The throughput experienced a similar improvement: The average throughput (T AV G ) increased between 3.8% and 50.6%, while the minimum throughput (T M IN ) increased between 57.4% and 158.8%. These results are presented in Table II.

The performance gains were the result of preventing that the MaGCs in the nodes affected the performance of the system. This behaviour is depicted in Figures 8 and9, which show the results of one of the tested configurations. In Figure 8.a, it can be noticed how the response time of the Baseline is affected when a MaGC occurs. On the contrary, Figure 8.b shows that these peaks do not occur when using our algorithm. The throughput (Figure 9) shows a similar behaviour.

To understand better the performance gains of our algorithm over the Baseline, the results were analysed under two perspectives. Firstly, the performance was compared during the periods of time when there were no MaGC events (non-MaGC time). These results (shown in Table III) proved that our algorithm does not affect the performance of the system during the non-MaGC time, as both algorithms performed similarly. Then the performance was compared during the periods of time of the MaGC events (MaGC time). These results (shown in Table IV) demonstrated that our algorithm improves the system performance during the MaGC time: RT AV G decreased between 87.4% and 99%, while T AV G increased between 42.6% and 97.5%. These improvements were the result of minimising the number of transactions affected by the MaGC. With our algorithm, the only affected transactions were those in the pipeline to be processed by the node which sufferred the MaGC, transactions which led to the triggering of the MaGC.

To understand the costs of our algorithm, we also compared the resource usages in the load balance node. Table V shows these results. The average CPU usage (CP U AV G ) increased between 3.5% and 7.2%, and the maximum CPU usage (CP U M AX ) between 1.5% and 5.5%. Regarding memory, its average usage (M EM AV G ) increased 0.3GB and its maximum usage (M EM M AX ) between 0.1 and 0.3GB. These memory increases were caused by the historical information that the forecast algorithm maintained. These increments were considered tolerable because the load balancer was far from exhausting its resources.

In summary, this experiment demonstrated the performance gains of using our proposed algorithm. By avoiding the impact of the MaGCs, the system performance was significantly improved in terms of response time and throughput.

V. CONCLUSIONS AND FUTURE WORK

This paper proposes a new load balancing algorithm to improve the throughput and response time of a distributed system with a small performance overhead. The algorithm utilises JVM data to predict the future occurrences of the MaGC event, which can cause a long pause time on the underlying application. The results have shown that the proposed load balance algorithm can offer a high improvement in response time and throughput (up to 99% and 51% respectively) by using the forecast to decide on how to balance the workload among the system nodes. Furthermore, the proposed algorithm explores and uses a new aspect of the system resource information: The GC. As a result, our work can be combined with other load balancing algorithms to form a more sophisticated solution. This scenario will be explored in our future work, as well as how best to simplify the configuration of our algorithms (e.g., the FWS selection) to improve their applicability.

Fig. 1 .

 1 Fig. 1. Adaptive Load Balancer

Fig. 2 .

 2 Fig. 2. MaGC Forecast Process -Overview 1) Algorithm Overview: Figure 2 depicts an overview of the algorithm, which is composed of five main phases. First the Initialisation which sets the parameters required by the

Fig. 3 .

 3 Fig. 3. Old memory exhaustion forecast

Fig. 4 .

 4 Fig. 4. MaGC event forecast

Algorithm 2 : 4 nextN ode := undefined 5 while nextNode is undefined do 6 indexN extN ode := indexNextNode+1 7 if indexN extN ode >avNodes then 8 indexN extN ode := 1 9 13 if remainingT ime <=maGCThres then 14 nextN

 24567811314 MaGC-Aware Load Balancing Input: Number of available nodes avNodes, MaGC Threshold maGCThres Output: Next available node (nextNode) 1 indexN extN ode := 0 2 f orecastT ries := 0 3 while load balance adaptiveness is needed do nextN ode := indexNextNode 10 if f orecastT ries <avNodes then 11 Get MaGC forecast of server indexN extN ode 12 remainingTime := forecast Time -current time

Fig. 6 .

 6 Fig. 6. Preferred FWS vs. MiGC AVG

Fig. 5 .

 5 Fig. 5. Forecast Error per DaCapo Benchmark and GC strategy

Fig. 8 .Fig. 9 .

 89 Fig. 8. Performance Comparison -Response Time (tradebeans -Serial GC)

  How many samples are used to determine if the application has reached its steady state. Data Gathering. Its objective is to capture an updated snapshot of the monitored JVM. It starts by collecting a new Old Generation sample. Then, if the application has not reached the steady state yet, a new loaded classes sample is collected and its history is reviewed. If the warm-up period is over, a flag is set to indicate this. Later a new MiGC sample is collected and added to the MiGC history. After having samples from at least two MiGCs, the next metrics are calculated:

Algorithm 1: MaGC Forecast Input: Sampling Interval, Forecast Window Size, Warm-up Window Size Output: Forecast time of the next MaGC event 1 steadyState := not reached 2 while forecast is needed do 3 Get new OldGen sample 4 if steadyState is not reached then 5 Get new loaded classes sample 6 if warm-up period is over then 7 steadyState := reached 8 Get new MiGC sample 9 Calculate new memory deltas 10 Update memory totals 11 Generate new observations 12 if steadyState is reached then 13 Forecast memory pending to be allocated 14 Forecast time of the next MaGC event 15 Wait the Sampling Interval Initialisation. Here the configuration parameters are set: • Sampling Interval: How often the samples are collected. • Forecast Windows Size (FWS): How many observations are used as historical data in the forecast calculation. • Warm-up Window Size:

  http://nmon.sourceforge.net/ 15 http://docs.oracle.com/javase/7/docs/api/java/lang/management/-GarbageCollectorMXBean.html

										Forecast Error									Forecast Error
		100%									100%
	Forecast Error (%)	-50% 0% 50%								Forecast Error (%)	-50% 0% 50%
		2	4	8	16	32	64	128	256	512 1024 2048 4096	2	4	8	16	32	64	128	256	512 1024 2048 4096
						Forecast Window Size						Forecast Window Size
						(a) h2-Serial GC						(b) tomcat-Serial GC
								Fig. 7. Forecast Error per FWS for h2 and tomcat benchmarks

TABLE II THROUGHPUT

 II AND RESPONSE TIME COMPARISON -FULL EXPERIMENT

	Bench.	GC			Response Time (ms)					Throughput (tps)
				RT AV G			RT M AX			T AV G			T M IN
			BL	GCLB	Diff.(%)	BL	GCLB	Diff.(%)	BL	GCLB	Diff.(%)	BL	GCLB	Diff.(%)
	tradebeans	S	4,552.4	112.2	-97.5%	330,813.0	17,596.4	-94.7%	41.4	53.7	29.6%	20.8	38.1	83.5%
	tradebeans	P	1,900.1	494.9	-74.0%	305,098.0	33,366.0	-89.1%	46.7	48.5	3.8%	24.8	39.0	57.4%
	tradesoap	S	6,757.8	72.0	-98.9%	139,678.0	59,348.9	-57.5%	17.2	25.9	50.6%	11.1	19.2	72.4%
	tradesoap	P	845.5	146.0	-82.7%	115,655.0	21,389.7	-81.5%	16.6	17.8	7.4%	5.1	13.1	158.8%

TABLE III THROUGHPUT

 III AND RESPONSE TIME COMPARISON -NON-MAGC TIME

	Bench.	GC			Response Time (ms)					Throughput (tps)
				RT AV G			RT M AX			T AV G			T M IN
			BL	GCLB	Diff.(%)	BL	GCLB	Diff.(%)	BL	GCLB	Diff.(%)	BL	GCLB	Diff.(%)
	tradebeans	S	39.1	31.5	-19.4%	1,953.6	1,948.7	-0.3%	48.3	48.9	1.3%	39.2	40.1	2.3%
	tradebeans	P	241.6	336.5	39.3%	1,135.2	1,157.4	2.0%	49.6	49.5	-0.3%	37.1	39.00	5.0%
	tradesoap	S	22.3	19.8	-11.2%	287.1	267.9	-6.7%	25.6	26.3	2.5%	16.4	19.2	16.7%
	tradesoap	P	123.1	124.4	1.1%	376.8	391.4	3.9%	17.6	17.3	-1.7%	15.5	13.1	-15.2%

TABLE IV THROUGHPUT

 IV AND RESPONSE TIME COMPARISON -MAGC TIME

	Bench.	GC			Response Time (ms)					Throughput (tps)
				RT AV G			RT M AX			T AV G			T M IN
			BL	GCLB	Diff.(%)	BL	GCLB	Diff.(%)	BL	GCLB	Diff.(%)	BL	GCLB	Diff.(%)
	tradebeans	S	9,065.6	192.8	-97.9%	330,813.0	17,596.4	-94.7%	34.5	50.3	45.5%	20.8	38.1	83.5%
	tradebeans	P	10,192.5	1,287.0	-87.4%	305,098.0	33,366.0	-89.1%	29.4	43.5	47.9%	24.8	39.0	57.4%
	tradesoap	S	9,163.4	90.6	-99.0%	139,678.0	59,349.0	-57.5%	13.0	25.8	97.5%	11.1	19.2	72.4%
	tradesoap	P	3,012.9	210.8	-93.0%	115,655.0	21,389.7	-81.5%	13.6	19.4	42.6%	5.1	13.1	158.7%

http://www.oracle.com/technetwork/java/javase/memorymanagementwhitepaper-150215.pdf

2 http://docs.oracle.com/cd/E13150 01/jrockit jvm/jrockit/geninfo/devapps/codeprac.html

http://publib.boulder.ibm.com/infocenter/wsdatap/4mt/ topic/com.ibm.dp.xa.doc/administratorsguide.xa35263.htm

http://www.oracle.com/technetwork/java/javase/tech/javamanagement-140525.html

[START_REF] Laskowski | Dynamic load balancing based on applications global states monitoring[END_REF] http://javalb.sourceforge.net/

http://dacapobench.org/

http://www.dacapobench.org/benchmarks.html

http://www.oracle.com/technetwork/java/javase/gc-tuning-6-140523.html

http://ncalculators.com/statistics/coefficient-of-variance-calculator.htm

http://jmeter.apache.org/

http://www.dacapobench.org/daytrader.html

https://geronimo.apache.org/

http://db.apache.org/derby/

VI. ACKNOWLEDGMENTS Supported, in part, by Science Foundation Ireland grant 10/CE/I1855.