Morten Lindeberg

Stein Kristiansen

Vera Goebel
email: goebel@ifi.uio.no

Thomas Plagemann
email: plageman]@ifi.uio.no

MAC Layer Support for Delay Tolerant Video Transport in Disruptive MANETs

Keywords: Video transmission, MANET, delay tolerant transport, crosslayer optimization

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Mobile ad-hoc networks (MANETs) can provide valuable communication services for emergency and rescue (ER) operations in the absence of a working communication infrastructure. One such service is the transfer of video data from rescue workers wearing head-mounted video cameras to a remote command and control center (CCC). The dynamicity of MANETs, the possibility of short and long-term network partitions, and the fact that forwarding nodes might be small hand held devices introduce many hard research challenges [START_REF] Jain | Routing in a delay tolerant network[END_REF]. However, this particular video service is in contrast to classical video streaming more tolerant to delay. Video data that is delayed for seconds, minutes or even hours can still be very useful in the CCC to understand what happened. We envisage in the CCC a video client that visualizes the availability of video sequences on a time axis, and allows play-out of live streams and browsing and play-out of locally stored video. The visualization will be immediately updated at the arrival of (delayed) video data. Therefore, video data that passed the play-out time should not be dropped, but instead delivered as fast as possible. Any video sequence might be still of importance.

In order to improve the delivery efficiency, we reduce in this work the number of MAC layer retransmissions that are likely to fail and prevent packet dropping at the MAC layer. Instead of dropping, packets are passed after the maximum number of unsuccessful retransmissions from the MAC layer to an overlay for delay tolerant store-carry-forwarding, called Dts-Overlay. It utilizes information from the routing table and the MAC layer to identify the most promising conditions for forwarding packets.

Packet loss at the MAC layer mainly happens if the link quality, i.e., signal strength, has degraded due to mobility, but the link is still registered in the routing table. In such cases, packets are passed from the transport layer via IP to the MAC layer, which in turn drops the packets after reaching the retransmission limit (typically seven). This problem exists until the routing protocol recognizes that the link is broken, e.g., through a missing hello message in OLSR. The high frequency of link errors between mobile nodes has stimulated cross-layer approaches like CIFLER [START_REF] Yackoski | Cross-layer inference-based fast link error recovery for manets[END_REF] to use fast link error detection for fast link error recovery. COLLIE [START_REF] Rayanchu | Diagnosing wireless packet losses in 802.11: Separating collision from weak signal[END_REF] is another approach to immediately react to link failures through link layer rate adaptation. Our solution is different; before the overlay sends a packet it checks both the routing table and the queue length at the link layer (Link Adapt ). Only if both indicate a working link to the next hop it passes the packet to the transport layer. Obviously, if a link is broken it does not make sense to try several retransmissions. Reducing the maximum number of retransmissions results in lower system load, but might lead also to higher packet loss rate. Therefore, the MAC layer returns in our solution after maximum retransmission trials the packet to the Dts-Overlay instead of dropping it (MAC Return). This is similar to the approach presented by Voorhaen et al. [START_REF] Voorhaen | Analyzing the impact of neighbor sensing on the performance of the olsr protocol[END_REF] where the packet is returned to the IP layer, assuming that an alternate route exists through which the packet can be sent instead. However, this assumption is not valid for scenarios with network partitions. In our ER application domain it might be the case that the CCC is only reachable from the location of the accident via message ferries [START_REF] Zhao | A message ferrying approach for data delivery in sparse mobile ad hoc networks[END_REF]. Another cause of packet loss in MANETs is the separation of neighbourhood discovery in the routing protocol and address resolution in ARP [START_REF] Carter | ARP considered harmful: manycast transactions in ad hoc networks[END_REF]. We study in our system two solutions to avoid this packet loss. First, we avoid the need for ARP by assuming that the devices used during an ER operation are configured and all IP and MAC addresses are exchanged a priori (Static ARP ). Second, when a new link appears in the routing table, the overlay provokes the address resolution of the connected node and sends only video packets to the node after its address is resolved (ARP Adapt ).

All core design decisions are based on measurements performed in real-world experiments. Our ns-3 based evaluation shows that the combination of these mechanisms leads to minimal packet loss, reduced overhead, and neglectable increased delay. The remainder of this paper is structured as follows: Section 2 presents system design and implementation, Section 3 the evaluation, related work is discussed in Section 4, and Section 5 summarizes the main achievements and presents future work.

Design and Implementation

This section explains the design of our solution which is based on UDP, IP, OLSR [START_REF] Jacquet | Optimized link state routing protocol for ad hoc networks[END_REF], and cross-layer enabled IEEE 802.11b (see Figure 1). First, we analyze MAC layer issues and describe the details of our MAC support. Then, we describe Dts-Overlay, and how we address ARP related packet loss. Finally, we present our implementation.

MAC Layer Issues

IEEE 802.11 minimizes link layer packet loss through positive acknowledgements (ACK frames) and retransmissions if no ACK is received. In current implementations, the default value for the maximum limit of (re-)transmissions is seven, i.e., after seven unsuccessful transmissions the packet is dropped. There are two reasons for packet loss in IEEE 802.11, collisions and link quality. For the first one, more retransmissions will likely result in successful transmissions, while this is not true for links of inadequate quality. In MANETs, link quality might be degrading quickly due to mobility and links might not exist even if they are listed in the routing table, i.e., the routing table is outdated. Obviously, it does not make sense to initiate packet retransmission over a low quality link and especially not over a non-existing link. Reducing in these situations the maximum retransmission limit saves energy and bandwidth, and reduces the probability of collisions. The latter is especially important in highly loaded networks. Results from our experiments with a Nokia N900 as forwarding node in a small MANET [START_REF] Kristiansen | On the forwarding capability of mobile handhelds for video streaming over manets[END_REF] reveal a high amount of MAC layer retransmissions when reaching the saturation point in a real wireless ad hoc network setting. The high amount of retransmissions is not only consuming the senders energy and link bandwidth, but also energy and bandwidth of all nodes that are in communication distance to the sender. To investigate this further and identify a better limit for number of retransmissions, we study the overall effect of different retransmission limits in Section 3. Four cases need to be considered when the MAC layer in the original 802.11 implementation would drop packets: [START_REF] Yackoski | Cross-layer inference-based fast link error recovery for manets[END_REF] The link towards the destination is down, but there exist another route. [START_REF] Rayanchu | Diagnosing wireless packet losses in 802.11: Separating collision from weak signal[END_REF] The link towards the destination is down, and there exist no alternative route. (3) The receiving node is not able to forward traffic at the rate received from the link [START_REF] Kristiansen | On the forwarding capability of mobile handhelds for video streaming over manets[END_REF]. (4) Congestion and collisions lead to taildropping in the MAC retransmission queue at the sender side, or rather unlikely, the packet is lost due to collision in all retransmission trials.

For case [START_REF] Yackoski | Cross-layer inference-based fast link error recovery for manets[END_REF], it is sufficient to hand the packet back to the network layer for re-routing, like in [START_REF] Voorhaen | Analyzing the impact of neighbor sensing on the performance of the olsr protocol[END_REF]. For case [START_REF] Rayanchu | Diagnosing wireless packet losses in 802.11: Separating collision from weak signal[END_REF], the packet should be handed to the Dts-Overlay for being temporarily stored in the store-carry-forward buffer. For case (3), retransmissions only worsen node contention, thus we either re-route, or temporarily store packets in the forward buffer. Case (4) should only happen in overload situations, thus it is necessary to reduce the load, i.e., less retransmissions and temporary storage. To strive for simplicity and to be minimal invasive with the MAC layer we hand in all cases the packet to the Dts-Overlay. The cost of this is limited. We have measured the costs of passing a packet through an overlay instead of passing it directly to the network layer, on a Nokia 810 running in energy saving mode with low CPU and bus frequency. Results from our two-hop test-bed indicate that throughput is not worsened, and the additional delay is approximately 10 %. In higher CPU frequency settings, this share of additional delay is even reduced.

Dts-Overlay

The fundamental task of the Dts-Overlay, is to make forwarding decisions, and store transit packets when it is not meaningful to forward them. The Dts-Overlay is formed by autonomously working instances on each node, and packets are forwarded by Dts-Overlay hop-by-hop. Forwarding decisions are based on link status from the MAC layer, and route status from the routing protocol. It is the goal to transport all packets as close as possible to the destination, i.e., the CCC in ER. Dts-Overlay handles packets as follows: (1) If OLSR reports that no route to the destination exists, we check for recent routes in the network topology history, which is kept by Dts-Overlay. (2) If a recent route suggests a next-hop that is within the range of the current node, packets are sent to this next-hop. This is based on the heuristic that the next hop node on the recent route to the destination is probably closer to the receiver. ( 3) If there are no recent routes, we temporarily suspend transmission by maintaining the packet in a store-carryforward buffer part of the Dts-Overlay. ( 4) If the next-hop is identified, we check to see if the MAC layer retransmission queue is filling (representing link status). In that case, we also suspend transmission.

To efficiently leverage message ferries, we currently assume that their IP address is in an a priori defined address range, i.e., message ferries can be identified when their IP address appears in the routing table. Message ferries are used as follows: when no route is found to the destination (CCC), and there exist route(s) to carrier nodes, the packets are forwarded to the closest carrier. To avoid packets looping back, we do not forward packets from carrier to carrier.

In a separate thread of execution, we monitor route updates in the routing table. As route notifications appear, we loop through all suspended packets and see if any of the suspended packets matches the new route(s). If so, they are forwarded to the suggested next-hop. Figure 2 shows the main components of the system, and the main flow of function calls and information exchange between them.

To/from video application

To / from peer Dts-Overlay nodes The Coordinator component implements the main interface (send / receive primitives) for the video streaming applications, and holds the UDP socket used for all peer communication. It is responsible for forwarding and receiving packets from other Dts-Overlay peers through the network, and packets scheduled for retransmission from the store-carry-forward buffer.

The main function of the Decision Maker is to provide the next-hop IP address for a given packet destination, and control the store-carry-forward buffer. Currently, it implements a simplified and adapted version of the TCP congestion control algorithm to control the send rate in which the feedback is not provided by the receiving node, but instead by the local link status. It is the responsibility of the Resource Manager to collect and monitor network state information. Figure 2 illustrates from where it obtains this information. The resource manager serves as information broker, and provides data to the Decision Maker. It also serves as the entry point for packets that reach the final retransmission limit at the MAC layer.

We have implemented the store-carry-forward packet buffer as a drop tail FIFO queue. The size of this queue represents a tradeoff between memory consumption, and delay tolerant packet forwarding. Currently, we have a relatively large queue size (500 MB) to avoid tail dropping. Recent developments in solidstate drives provide relatively cheap, large and fast storage to the mobile devices. Thus, we expect that for low bit rate video streams within relative short network scenarios, it is realistic to expect that the buffer sizes do not limit the store-carry-forward capabilities of nodes. Packet exchange between peers is performed through overlay messages. Currently, the header is very simple; it only keeps the IP address of the destination. This information is lost at the IP layer, since overlay messages are only sent hop-by-hop.

Address Resolution

Carter et al. [START_REF] Voorhaen | Analyzing the impact of neighbor sensing on the performance of the olsr protocol[END_REF] identified ARP as one cause for packet loss in case several packets are sent immediately after an ARP request before the resolution process has finished, because only one packet could be buffered in ARP. Despite substantially increased buffer space in ARP in the recent ns-3 implementation, we identified a severe packet loss between the Dts-Overlay and the MAC layer. Packets are still silently dropped at the IP layer, when a MAC address for a given IP destination (reported by the routing protocol) has not been discovered. Further investigations revealed that this happens in cases the ARP reply is lost. To avoid these packet drops, we have implemented and evaluated two different approaches. First, we avoid the need for ARP by assuming that all devices in an ER operation are configured a priori with fixed IP addresses and all IP and MAC addresses are stored on all devices. In our second solution, we assure that the address resolution process is successfully finished before sending video packets, by sending an empty dummy packet to the IP destination. This leads to some overhead in terms of transmitted bytes, but our results show that the gain in packet reception at the destination is significant.

Implementation

We have adapted an already existing UDP based application for transmitting video traces (UdpTraceClient) which is part of the ns-3 code distribution. It generates UDP packets with packet sizes based on a given video trace, and adds a sequence number and timestamp to each packet. Dts-Overlay is implemented in C++ as an ns-3 application. This should make it easily portable to real devices.

We achieve cross-layer parameter exchange through the use of the ns-3 object aggregation system. In essence, ns-3 models network nodes and its protocol instances as objects. The smart pointer system enables access to these objects. This means that our Resource Manager component, realized as an object, can interact with, e.g., the OLSR routing protocol instance through function calls. We have implemented function calls within the ns-3 implementation of the IEEE 802.11 MAC layer, the ARP protocol, and the OLSR routing protocol that enables the Resource Manager to get the necessary state data.

Evaluation

In this section, we consider three network topologies, (1) ER scenario, (2) sparse MANETs, and (3) dense MANETs. The simulations are conducted in ns-31 , version 3.9. For the ER Scenario, we have created a mobility model that reflects realistic ER scenarios. It contains two network partitions and a set of designated message ferries moving between them (see Figure 3). On-location nodes move with a speed of 2 m/s (approximately walking speed) 10 s pause time, according to the Random Walk mobility model, within a 500 m x 500 m area. Carrier nodes pause both at the CCC and on location for 60 seconds, allowing data exchange. During the carrier phase, they move following a straight line at 10 m/s, the distance is 1750 m. The CCC node is not moving at all.

In addition to the ER scenario, we consider (2) Sparse MANET with area size 1250 m x 1250 m, and (3) Dense MANET with area size 250 m x 250 m. Each with 20 nodes, Random Walk mobility, node speed of 2 m/s, and 10 s pause time. In all network scenarios, nodes use IEEE 802.11b in ad-hoc mode. The devices simulate direct-sequence spread spectrum (DSSS) modulation, and a constant data transmission mode of 11 Mbps. For modelling the wireless channel, we utilize the constant speed propagation delay model, and the Friis propagation loss model.

Workload and metrics

The workload consists of a single unicast stream of the video entitled Foreman, obtained from the Video Traces Research Group2 . The resolution is CIF (352x288) with a 25 fps frame rate, and the video is pre-encoded using H.264 baseline profile with a target bitrate of 256 kb/s. We packetize the H.264 encoded video into a .mp4 container, with MTU size set to 1400 bytes. The 12-second video stream is repeated 300 times, i.e., we obtain a total duration of 1 hour.

For the dense scenario, our purpose is to identify how MAC support handles packet collisions. To achieve this, four UDP streams are sent between randomly selected intermediate nodes. Each UDP stream comprises 7500 packets per second with a uniform packet size of 1024 bytes. The resulting bitrate is higher than the available bandwidth, thus packet collisions are provoked.

We use four metrics to evaluate our solution: the percentage of video packets that are correctly received at the destination, denoted packet reception Rx v ; number of packets that are stored in intermediate nodes, denoted buffered packets B uf ; the percentage of lost packets, denoted packet loss P l ; and the overhead in terms of the total number of bytes of video packets transmitted at the physical layer, denoted T x t . Since we support delay tolerant video transfer it does not make sense to use video quality measures based on signal to noise ratio. All numbers are averages from five experiment runs, unless otherwise stated, and we present the standard deviation (σ).

Results

In the MAC Support evaluation, we compare five configurations (C3 -C7) to evaluate the effect of MAC Return (MR) and Link Adapt (LA). The configuration settings are shown in Table 1. Retransmission Limit and Link Adapt Limit: To understand and quantify the tradeoffs of reliability and costs related to the maximum number of retransmissions, we measure packet loss and costs for (1) different retransmission limits, and (2) different MAC retransmission queue size limits that prevent the Dts-Overlay to send packets in the LA mechanism. For (1), we show that we reduce overhead by lowering the retransmission limit, at the cost of packet loss. For (2), we see that we actually reduce both packet loss and cost (see Figure 4). The experiments are performed with the default Dts-Overlay configuration in the ER scenario with duration of 30 min. We present the average of five experiment runs. The highest packet loss occurs with a retransmission limit of one (56.5 %). With a limit of three, packet loss is lower (31 %). A limit of five results in 22.0 %, a limit of seven in 19.5 %, and a limit of eleven in 15.4 % packet loss. At the same time we see an increase in the cost T x t of 47 %, from retry limit of one up to eleven. Notice that the curve is almost flat after five retries (T x t = 221 MB). In our simulation studies, this behaviour can be attributed to tail dropping in the MAC retransmission queue. The current maximum queue size for this queue in ns-3 is 400 packets, which is very often reached in the experiments.

We have found that MAC retransmission queue size serves as a good indication of the link status. If packets destined on a certain link start piling up, the link is probably down. LA stops all ongoing transfers over the specific link, in case the queue starts filling up. Currently, this adaptation limit is set to 75 for our main experiments. The reason is that the limit is beneficial for MR configurations shown by preliminary experimentation. As a pre-study we investigate its effect on default configurations. Notice that we utilize a fixed retry limit of three.

The figure clearly indicates that we get the lowest packet loss with an adaptation limit set to one. At 25, packet reception is worse. Finally at 200, packet loss has almost doubled from the limit set to one, i.e., 31 % of the packets are lost. The gain in reduced packet loss for low limit settings is even combined with reduced cost T x t . Such a strict limit means we stop using links in which packets are scheduled for retransmission. For denser networks with more frequent random collisions, we expect such a setting to be too strict, i.e., packets will be kept from being sent over working links. ER Scenario: Due to the distance between the ER location and the CCC, all packet receptions come via carrier nodes. The numbers in the table show that our MR configurations (C6 and C7) outperform C3 when it comes to packet reception (16 % improvement), and loss is reduced from 17.4 % to <1 %. Remaining packets are kept in intermediate node buffers. LA (C5 and C7) has little effect in terms of loss and packet reception. By reducing the retransmission limit for default configuration , packet loss is increased to 29.8 % (C4), however, we reduce overhead in terms of meaningless physical layer transmissions. Most notable, the total transmitted bytes for C7 is in average 1 MB lower than in C3. In comparison, C6 achieves in average 21 MB more byte transmission than C7, thus LA improves our results. To summarize, MAC Support (MR plus LA) increases packet reception, reduces packet loss, and reduces cost in ER scenarios. Sparse MANET Scenario: In total, we see that packet reception has decreased for the MR configurations, compared to the ER scenario. We achieve with 91 % the highest packet reception in both cases (C6 and C7). Packet reception is better (≈ 10 %) than for C3, where packet loss is 18.7 %. Remaining packets are kept in the buffers, although we experience 1 % packet loss for C6.

The C4 and C5 configuration achieve both 77 % packet reception, thus LA does not improve packet reception. Packet loss is 23.4 % in these two cases. Standard deviation is quite high, also for the total transmission of bytes. The reason for this is that the packet loss is in some runs high and in others rather low, depending on the seed for the generation of random mobility. In the following we only use one seed that creates a scenario with high packet loss.

Figure 5 shows Rx v and T x t for one particular experiment run over time. For C3, we receive 52 % of the packets. By reducing the retransmission limit to three (C4), packet reception is lower, e.g., 39.2 %, and 39.3 % with LA enabled. Packet reception is 64.8 % for C6, and 65.0 % for C7. This demonstrates that MR is useful in scenarios with high packet loss.

Turning our focus to overhead, we see that overall packet transmission is reduced quite heavily by lowering the retransmission limit from seven to three. For C3 and C4, a reduction of T x t ≈ 400 MB, i.e., a factor of 0.5. Configuration C7 leads to approximately 63 % more transmitted PHY packets than in C3, and close to 65 % more packet reception. It should be noted that those packet that did not reach the destination are kept in forward buffers of intermediate nodes, i.e., no packet loss occurred in C7.

Dense MANET Scenario: Nodes are randomly distributed in the relatively small area compared to signal propagation length, i.e., node density is high. As a result, packet loss is mostly caused by collisions, rather than insufficient signal strength. Configuration C3 handles collisions well, i.e., no packet loss. For Rxv 100.0 % (σ:0.4) 99.0 % (σ:0.6) 99.3 % (σ:0.1) 99.8 % (σ:0.0) 99.8 %(σ:0.1) B uf 0.0 % (σ:0.0) 0.2 % (σ:0.6) 0.0 % (σ:0.1) 3.5 % (σ:0.1) 3.5 % (σ:0.2) P l 0.0 % (σ:0.0) 0.8 % (σ:0.1) 0.6 % (σ:0.1) -3.4 % (σ:0.1) -3.4 % (σ:0.1) T xt 149 MB (σ:2) 149 MB (σ:3) 98 MB (σ:6) 151 MB (σ:3) 92 MB (σ:8) configurations C4 and C5, packet collisions cause ≈ 1 % packet loss resulting in ≈ 99 % packet reception. For the MR configurations (C6 and C7), we encompass close to 100 % packet reception and some amount of duplicates, indicated by a negative packet loss of ≈ -3.5%. The cause of these duplicates is that our MAC support interferes with the MAC layer functionality to handle frame duplicates due to missing MAC acknowledgements.

We see that C7 achieves the lowest overhead, from C3, a 62 % reduction, which is substantial. In general, a severe reduction applies to all LA configurations, proven highly beneficial in congested and dense MANETs.

Related Work

The related work falls into three categories: (1) delay tolerant transport, (2) video delivery over MANETs, and (3) adaptations to MAC or PHY conditions. The typical approach of delay tolerant networking is to provide an alternative to TCP, to achieve some reliability for end-to-end transport. One alternative is to introduce a layer that adds delay tolerance above existing routing protocols, like in SAFT [START_REF] Heimlicher | SaFT: Reliable transport in mobile networks[END_REF]. Reliability is provided through a double control-loop, including end-to-end feedback and TCP hop-by-hop. Applying TCP between each hop substantially increases the number of control packets. Delay-tolerant video transport over IP is achieved in MOMENTUM [START_REF] Cabrero | Overlay solution for multimedia data over sparse MANETs[END_REF], like in our approach through an overlay. However, only selected nodes, called session nodes, actively transport the video data and require knowledge about all session nodes. Furthermore, adaptations to lower layers are not considered, e.g., to determine the buffer empty rate. Another alternative is to implement a delay tolerant routing protocol, resulting in what is often referred to as space-time routing. This is explored already in [START_REF] Jain | Routing in a delay tolerant network[END_REF], the authors suggest that algorithms should take congestion into account, and that performance can still be good without global knowledge. Evaluation results from our autonomous solution support this.

In [START_REF] Lindeberg | Challenges and techniques for video streaming over mobile ad hoc networks[END_REF], a detailed survey of research on video streaming over MANETs is given. A popular approach is to combine cross-layered multipath MANET routing with multiple description video coding, often leading to NP-hard optimization problems. It should be noted that all these works assume that one or more routes between source and destination exist.

The effect of MAC layer retransmissions on video quality is studied in [START_REF] Chan | The impact of linklayer retransmissions on video streaming in wireless mesh networks[END_REF][START_REF] Choudhury | Effect of payload length variation and retransmissions on multimedia in 802.11a WLANs[END_REF]. Both efforts aim to adapt the retransmission limit, to better meet user video quality demands. COLLIE [START_REF] Rayanchu | Diagnosing wireless packet losses in 802.11: Separating collision from weak signal[END_REF] and CIFLER [START_REF] Yackoski | Cross-layer inference-based fast link error recovery for manets[END_REF] enable the routing protocol to better react to link status. The reduction of packet loss, caused by lack of exact link status for the OLSR routing protocol is targeted in [START_REF] Voorhaen | Analyzing the impact of neighbor sensing on the performance of the olsr protocol[END_REF]. In case a packet could not be transferred over a link, it is returned to the IP layer assuming another route exists. Thus, tolerance to path disruptions is neither considered nor supported. Authors show, as we do with our related technique, improvements in terms of reduced packet loss.

Conclusion

This work reduces packet loss in disruptive MANETs by MAC layer support, and paired with the Dts-Overlay, achieves tolerance to network disruptions. As part of MAC support, our MAC Return algorithm enables us to drastically reduce packet loss, in turn allowing us to reduce overhead by lowering the MAC layer retransmission limit. In addition, our Link Adapt algorithm allows us to reduce overhead in that we do not try to send packets over links that are down. This has been supported by extensive simulation studies. More precisely, we have shown that our approach achieves both a reduction in physical layer packet transmissions, while avoiding packet loss through the use of intermediate node buffering, paired with a higher packet reception rate in both a sparse MANET setting, and in our special purpose ER scenario. In addition, the usability of our approach is strengthened through evaluation results in a dense MANET setting. With high density, we see improvements of packet reception/packet loss, although at the cost of some packet duplicates.

There are still open issues and remaining challenges. Currently, MAC Return does not support packet fragmentation at the MAC or IP layer. As seen in the dense MANET setting, it can obstruct existing MAC functionality for identifying duplicates. When acknowledgements from the receiver node are lost, we encounter a false negative error. This might lead to the sender retransmitting packets that are already received at the receiver. There are yet parameters to fine-tune. For one, we can improve our rate control algorithm for emptying the store-carry-forward buffer by utilizing physical layer parameters, such as signal strength. We should account for video coding parameters and frame priority in our forwarding decisions. At the network and routing layer, improvements can be done to, e.g., OLSR, by removing links from OLSR data structures known to be down. At the MAC layer, we could benefit from deploying one of the existing rate adaptation algorithms, such as CARA [START_REF] Kim | CARA: Collision-Aware Rate Adaptation for IEEE 802.11 WLANs[END_REF]. For future work, we plan to incorporate an energy model in the simulated nodes to enable energy aware forwarding strategies. We aim to implement our work on a real mobile device, such as the Nokia N900. This would strengthen the realism of our performance evaluations. As stated in [START_REF] Kristiansen | On the forwarding capability of mobile handhelds for video streaming over manets[END_REF], we are aware that mobile hand helds have lower forwarding capability than what the wireless medium supports. Especially, we hope to investigate how to tackle packet loss due to node contention, as opposed to weak signal strength or packet collisions.

Fig. 1 .

 1 Fig. 1. Cross-layer Information Flow in Dts-Overlay.

Fig. 2 .

 2 Fig. 2. Dts-Overlay System Design.

Fig. 3 .

 3 Fig. 3. ER Scenario.

Fig. 4 .

 4 Fig. 4. Effect of Retransmission Limit and Link Adapt Limit Settings.

Fig. 5 .

 5 Fig. 5. Sparse MANET single run, Node speed 2m/s.

Table 1 .

 1 MAC Support Evaluation Configurations.

		C1	C2 C3 C4 C5 C6 C7
	Retransmission Limit	7	7	7	3	3	3	3
	MAC Return

Table 2 .

 2 ARP Effect on Packet Loss

	C1	C2	C3
	P l 39.3 (σ:9.4) % 31.7 % (σ:4.1) 19.5 % (σ:5.1)
	Effect of ARP: First, we compare the impact of ARP on packet loss in the
	default setting C1 with our solution based on pre-configured IP and MAC ad-
	dresses (C2), and our alternative solution to send packets after the resolution
	process has successfully finished C3. Results are averages from five experiment
	runs with 30-minute duration, ER scenario. We focus on packet loss P l . Results
	indicate that packet loss is heavily affected by our second solution. The packet
	loss with default settings (C1) is 39.3 %, 31.7 % with static ARP (C2), and
	19.5 % with ARP Adapt (C3). In C1 and C2, packets are sent immediately
	also over links with poor quality. In C3 packet forwarding is delayed until ARP

Table 3 .

 3 Evaluation Results ER Scenario

	C3	C4	C5	C6	C7
	Rxv 77.5 % (σ:1.8) 65.7 % (σ:1.6) 66.3 % (σ:1.0) 93.5 % (σ:0.5) 93.6 % (σ:0.7)
	B uf 5.1 % (σ:0.7) 4.5 % (σ:0.6) 4.5 % (σ:0.3) 5.6 % (σ:0.4) 6.1 % (σ:0.6)
	PL 17.4 % (σ:2.1) 29.8 % (σ:1.2) 29.2 % (σ:1.2) 0.9 % (σ:0.3) 0.3 % (σ:0.0)
	T xt 455 MB (σ:19) 412 MB (σ:7) 411 MB (σ:10) 475 MB (σ:15) 454 MB (σ:28)

Table 4 .

 4 Evaluation Results Sparse Manet Scenario

	C3	C4	C5	C6	C7
	Rxv 81.3 % (σ:24.6) 76.6 % (σ:30.7) 76.5 % (σ:30.8) 91.3 % (σ:14.8) 91.4 % (σ:15.0)
	B uf 0.0 % (σ:0.0)	0.0 % (σ:0.0)	0.1 % (σ:0.2) 7.3 % (σ:13.6) 8.1 % (σ:14.7)
	P l 18.7 % (σ:24.6) 23.4 % (σ:30.7) 23.4% (σ:30.7) 1.4 % (σ:1.9)	0.5 % (σ:0.6)
	T xt 397 MB (σ:362) 245 MB (σ:162) 247 MB (σ:165) 381 MB (σ:356) 379 MB (σ:354)

Table 5 .

 5 Evaluation Results Dense Manet Scenario

	C3	C4	C5	C6	C7

Available at http://www.nsnam.org/

http://trace.kom.aau.dk/

Acknowledgements This work is funded by the VERDIKT program of the Norwegian Research Council, through the DT-Stream project (no. 183312/S10). The authors would like to thank Sergio Cabrero, Isaías Martínez Yelmo and Daniel Rodríguez-Fernández for valuable insights.


Daniel Schlosser

Michael Duelli

Sebastian Goll

Performance Comparison of Hardware Virtualization Platforms

Keywords: hardware virtualization, analysis, commodity hardware, network throughput, isolation

Hosting virtual servers on a shared physical hardware by means of hardware virtualization is common use at data centers, web hosters, and research facilities. All platforms include isolation techniques that restrict resource consumption of the virtual guest machines. However, these isolation techniques have an impact on the performance of the guest systems. In this paper, we study how popular hardware virtualization approaches (OpenVZ, KVM, Xen v4, VirtualBox, VMware ESXi) affect the network throughput of a virtualized system. We compare their impact in a dedicated and a shared host scenario as well as to the bare host system. Our results provide an overview on the performance of popular hardware virtualization platforms on commodity hardware in terms of network throughput.

Introduction

Hardware virtualization means abstracting functionality from physical components and originated already in the late 1960s. Recently, the importance of virtualization has drastically increased due to its availability on commodity hardware, which allows multiple virtual guests to share a physical machine's resources. The resource access is scheduled and controlled by the virtual machine monitor (VMM), also called hypervisor. Different virtualization platforms have been implemented and are widely used in professional environments, e.g. data centers and research facilities like G-Lab [1], to increase efficiency and reliability of the offered resources. The resources that may be used by a virtual guest system as well as lower performance bounds regarding these resources are determined in service level agreements (SLA) between providers and customers. The implementation of the VMM influences how well the resource allocation complies with these SLAs and to which extent different guests interfere with each other. Hence, a provider has to know the performance limitations, the impact factors, and the key performance indicators of the used VMM to ensure isolation and SLAs.

Hardware virtualization is used in two basic scenarios. In the dedicated scenario, only a single virtual guest is run on a physical host. By means of hardware virtualization, the guest system is made independent of the underlying physical hardware, e.g., to support migration in case of maintenance or hardware failures. Hardware virtualization is also used to consolidate the resources of the physical host among multiple virtual guest systems in a shared scenario. While the performance of a virtualized system can be directly compared to the bare host system in the dedicated scenario, the performance of a virtual guest may be also affected by interference with other virtual guests in a shared scenario.

The performance cost of virtualization and isolation, i.e. the prevention of virtual guest interference, has been widely studied for CPU, memory, and hard disk usage. Nowadays, most commodity servers have built-in hardware support for virtualization enabling fast context switching in the CPU and resource restriction for the memory. However, the input/output (I/O) system, especially network throughput, is still a crucial factor.

Therefore, we focus on the network throughput of virtualized systems as the performance metric in this paper. We apply this metric on a non-virtualized Linux and on a virtualized version of this system using several popular hardware virtualization platforms, i.e. OpenVZ, KVM, Xen v4, VirtualBox, VMware ESXi. Furthermore, we install a second virtual guest and analyze the effects when the second virtual guest is idle, running some CPU/memory intensive tasks, or is transmitting packets.

The remainder of this paper is structured as follows. In Section 2, we present the different virtualization concepts used by the considered VMMs and related work. We explain our measurement setup and methodology in Section 3. Results for the dedicated scenario considering only a single guest are described in Section 4. An analysis of two virtual guests in shared scenarios is discussed in Section 5. In Section 6, we draw conclusions and give an outlook on future work.

Background and Related Work

In this section, we describe the techniques used by the considered VMMs to virtualize the underlying hardware and give an overview on related work.

Virtualization Concepts

The recent popularity of virtualization on commodity hardware created a plethora of virtualization platforms with different complexity and environmentdependent applicability. An overview of virtualization platforms is given in [START_REF]Wikipedia: Comparison of platform virtual machines -Wikipedia, The Free Encyclopedia[END_REF].

Several ways to realize hardware virtualization have evolved, which differ in the required adaptations of the guest system. For instance, a VMM may run on bare hardware (called Type 1, native, or bare metal ) or on top of an underlying/existing operating system (OS) (called Type 2 or hosted ). Also hybrids between Type 1 and 2 are possible. Finally, OS-level virtualization is a special form, where the guests are run in a container of the OS operating directly on the hardware. Native VMMs and hosted VMMs provide a full virtualization, i.e. the guest system does not have to be modified. This means that the virtualized guest operating system is working as if it would run directly on the hardware. But whenever the guest wants to access a hardware resource, which is only a virtualized resource, the VMM has to interrupt the guest and 'emulate' this hardware access. This affects the performance of the guest system. To alleviate these problems, the guest system can be modified, e.g. with special drivers, to redirect resource accesses to function calls of the VMM. This method is called para-virtualization and may improve the performance of the guest. OS level virtualization solves this resource access problem by using the same modified kernel in the guest containers as in the hosting OS. Hence, this technique has the advantage that the overhead for virtualization is quite low compared to the other solutions. However, the OS and the kernel of the guest is predetermined.

In this work, we consider five popular hardware virtualization platforms which can be categorized as native virtualization, represented by VMware ESXi [19] and Xen v4 [21], host virtualization, represented by VirtualBox [16] and KVM [START_REF]KVM: Kernel-based virtual machine[END_REF], and operating system-level virtualization, represented by OpenVZ [START_REF]OpenVZ: Open virtualization[END_REF].

Figure 1 depicts how the considered virtualization platforms encapsulate virtual guests and indirect access to resources for applications, which run in user space.

Fair access to the physical hardware is important and known to work for resources that can be split into quotas, e.g. memory, disk space, or processor cycles per second. However, access to any of these separately restricted resources involves the input and output (I/O) of data which typically shares a single bottleneck, e.g. an internal bus. Especially, network I/O fairness is a crucial issue which involves another shared physical resource, the network interface card (NIC). In this paper, we consider the packet forwarding throughput of the aforementioned virtualization platforms as a performance metric.

Related Work

An overview of virtualization techniques and mechanisms as well as their history and motivation is given in [START_REF] Van Doorn | Hardware virtualization trends[END_REF]. Several publications consider resource access fairness when multiple guest systems run on a single host. In [START_REF] Ongaro | Scheduling I/O in virtual machine monitors[END_REF], virtualization was done using Xen. The authors show that while the processor resources are fairly shared among guests, the scheduling of I/O resources is treated as a secondary concern and decreases with each additional guest system. The authors of [START_REF] Anwer | Network I/O fairness in virtual machines[END_REF] use a NetFPGA-based prototype to achieve network I/O fairness in virtual machines by applying flexible rate limiting mechanisms directly to virtual network interfaces. Fairness issues in software virtual routers using Click are considered in [START_REF] Egi | Fairness issues in software virtual routers[END_REF]. The impact of several guests with and without additional memory intensive tasks on packet forwarding is measured. More details and performance tuning for the Click router is provided in [START_REF] Egi | Towards high performance virtual routers on commodity hardware[END_REF].

As mentioned before, the performance and fairness heavily depend on the used VMM. Hence, several comparisons of mostly two VMMs have been conducted. We focus on the references considering network I/O performance which altogether consider packet forwarding performance with different packet lengths from 64 to 1500 bytes. In [START_REF]VMware: A Performance Comparison of Hypervisors[END_REF], a comparison of VMware ESX Server 3.0.1 and open-source Xen 3.0.3 with up to two guests was conducted by VMware using the Netperf packet generator. They show that Xen heavily lags behind VMware ESX. This study was repeated with VMware ESX Server 3.0.1 and open-source Xen Enterprise 3.2.3 in [START_REF]XenSource Inc: A Performance Comparison of Commercial Hypervisors[END_REF] by Xen Inc. which showed that a specialized Xen Enterprise lags by a few percent. The authors of [START_REF] Bredel | Analyzing router performance using network calculus with external measurements[END_REF] consider multiplexing of two data flows with different scheduling mechanisms on a real Cisco router, a virtual machine host, in two VM guests using Xen, and a NetFPGA packet generator. They show the dependency of the software routers on the packet length. Measurements of OpenVZ and User Mode Linux (UML) were conducted in [START_REF] Bhanage | Analyzing router performance using network calculus with external measurements[END_REF] on wireless nodes of the Orbit test bed. UDP throughput and FTP performance is measured, but it is also stated that the hardware is not the best choice for virtualization. In [START_REF] Bhatia | Trellis: a platform for building flexible, fast virtual networks on commodity hardware[END_REF], the network virtualization platform Trellis is presented and packet-forwarding rates relative to other virtualization technologies and native kernel forwarding performance are compared. The considered virtualization technologies comprise Xen, Click, OpenVZ, NetNS, and the Trellis platform. The Linux kernel module pktgen [START_REF] Olsson | pktgen the Linux packet generator[END_REF] is used for packet generation. In their results, Xen has the lowest performance followed by OpenVZ.

To the best of our knowledge, this is the first paper to compare the packet forwarding performance of today's most popular hardware virtualization platforms on a common commodity server system without special hardware requirements, e.g. NetFPGA cards, or fine-tuned virtualization parameters, such that comparisons can be easily repeated.

Hardware Setup and Measurement Scenarios

In the following section, we give an overview on the hardware setup of our measurements and provide technical details on the considered scenarios.

Hardware Setup

For our measurements, we use seven Sun Fire X4150 x64 servers from the G-Lab testbed [1], each with 2×Intel Xeon L5420 Quad Core CPU (2×6 MB L2 Cache, 2.5 GHz, 1333 MT/s FSB, and 8×2 GB RAM. The unit under test (UUT) is equipped with eight 1 Gigabit ports, while all other servers are equipped with only four 1 Gigabit ports. The UUT is connected on each NIC to three other servers each with a single connection using Cat.5e TP cable or better. The setup and interconnection of the servers is illustrated in Figure 2. Each machine is running Debian 5.0.4 ("lenny") with Linux kernel 2.6.26 compiled for the amd64 (x86 64) architecture. Only for the test of Xen we needed to adjust the base system with Debian 5.0.5 ("lenny") with Linux kernel 2.6.31 for amd64. Since VMware ESXi installs directly on the host machine, the choice of a custom operating system is not applicable in this case. We investigate the following versions of the different VMMs with a Debian "lenny" as a guest system and the given Kernel installed:

-KVM 0.9.1 (kvm-72) [START_REF]KVM: Kernel-based virtual machine[END_REF]: Guest running Linux 2.6.26 for amd64 -OpenVZ 3.0.22 [START_REF]OpenVZ: Open virtualization[END_REF]: Guest running same OS kernel as host -VirtualBox 3. For the KVM and VirtualBox machines, virtual NICs are using the "virtio" para-virtualized network driver. For OpenVZ and Xen, para-virtualization is achieved implicitly through the OS-level or para-virtualization approach taken by OpenVZ and Xen, respectively. For VMware ESXi, both the "E1000" fullvirtualized network driver and the "VMXNET 3" para-virtualized network driver (using the VMware Tools on the guest) are considered.

Measurement Metrics and Methodology

In all scenarios, we investigate the packet forwarding throughput performance of the different virtualization solutions on the UUT. In each experiment, network traffic is generated using the packet generator integrated into the Linux kernel (pktgen [START_REF] Olsson | pktgen the Linux packet generator[END_REF]). It sends out UDP packets which are forwarded by the UUT to another destination server where the traffic is recorded by tcpdump [3] and discarded afterwards. After stopping packet generation, the packet generator reports how many packets it was able to send. We calculate the "offered bandwidth" from this value and the time in which the traffic has been sent as well as the "measured throughput" from the data of the tcpdump file.

For our performance evaluation, we set up two different scenarios, a dedicated host scenario and a shared host scenarios, which we describe in the next sections.

Dedicated Host Scenario -Impact of Virtualization

In this scenario, we measure the packet forwarding performance of the Linux system without any virtualization (raw ) and compare it with a setup where the same system is installed inside the tested VMM. We consider up to three traffic sources. It has to be noted that each traffic stream through the UUT does not interfere with any other stream outside the server, i.e. each traffic stream enters the server over a different network interface and also leaves the system via another distinct network interface. Each network interface is directly bridged to a corresponding virtual interface of the guest system.We consider packets with an Ethernet frame size of 64, 500, 1000, and 1500 byte for each data stream.

For each packet size, a target bandwidth of 10, 100, 200, 400, 600, 800, 900, and 1000 Mbit/s was run nine times for statistical evidence. Since pktgen does not allow for setting a target bandwidth, but instead manages different loads of traffic by waiting a certain amount of time between sending two consecutive packets, this delay had to be calculated. For target bandwidth b [Mbit/s] and target packet size s [byte], the resulting delay [ns] would be 8000×(s+24)/b. This formula works well for large packet sizes, but the kernel is not able to generate small packets fast enough. Hence, we adopted the inter packet delay to 1 and 0 ns to maximize the generated traffic and send as many packets as possible.

Shared Host Scenario -Impact of other Guest Systems

The consolidation of multiple virtual systems on a single physical host may have an impact on the network performance of the virtualized guests. Thus, we add a second virtual guest to the VMM, which runs another Debian "lenny" and repeat all measurements. Initially, the second guest does not run any processes generating additional load (no load ). In order to investigate if CPU intensive processes in another guest systems has an influence of the performance of our UUT, we generate variable amounts of CPU and virtual memory load with the stress tool (version 0.18.9) [START_REF]Stress tool[END_REF] and considered two more cases. In the first case, called light load, stress was running with parameter --cpu 1, corresponding to a single CPU worker thread. In the second case, called heavy load, stress was running with parameters --cpu 8 --vm 4, corresponding to 8 CPU worker threads, and 4 virtual memory threads which allocate, write to, and release memory. In case of full virtualization (KVM, VirtualBox, VMware, and Xen), each virtual guest was assigned a single (virtual) CPU out of the 8 physical CPU cores installed on the server.

Besides CPU and memory load, we targeted the influence of a second guest systems network load, even if the guests do not share physical network interfaces. We focus in this scenario on Ethernet frame sizes of 64 byte, as the previous scenarios revealed this packet size to be most critical. Hence, we reconfigured the UUT to have only two virtual interfaces, which are bridged to different physical interfaces. We adjust the second guest system to have also two virtual interfaces, which are bridged to two distinct physical interfaces. We run the same tests as before, but this time we send traffic through the second guest. We adjust the traffic in such a way that it is 50% and 95% of the maximum rate, which we measured in the test with the second guest being idle. For this test, we also measure the throughput of the second guest to investigate if the second guest system can still forward the offered data rate.

The Performance Cost of Virtualization

Depending on the used VMM, the network throughput performance of the virtual guests differs significantly. In Figure 3, we plot the bandwidth the traffic generator produced ("offered bandwidth") against the throughput the central test system was able to forward ("measured throughput") averaged over all nine repetitions of a test. The error bars, which in many cases can hardly be seen, present the 95% confidence intervals for the mean values. The graphs for the 1500 byte packets reveal no difference between the system without virtualization and most of the VMMs. Only the VirtualBox system is not able to forward all packets. For smaller packet sizes, i.e. 1000 bytes and 500 bytes, the difference between the different VMMs is clearly visible. The fact that the offered bandwidth for all packet sizes above 500 bytes increases up to the maximum of the link, i.e. 1 Gbit/s, shows that the VMMs are able to fetch the packets from the network interface. However, in all cases in which the measured bandwidth is lower than the offered bandwidth, a significant number of packets get lost in the unit under test (UUT). Looking at Figure 3d, two additional effects can be noticed for the smallest used packet sizes, i.e. 64 bytes. Not all graphs extend to the same length on the y-axis. This means that the traffic generator was not able that in all cases, except the one sending the 64 byte packets, the performance of the raw system scales linearly, i.e. we measure a throughput of 1 Gbit/s, 2 Gbit/s, and 3 Gbit/s. In the case of 64 byte packets, Figure 4d also reveals a limitation of the raw system, as the accumulated throughput for two and three traffic generators is the same. It has to be noted that in this case the raw system uses layer-2 flow control to throttle down the traffic generators. But the raw system is able to forward all received packets, in contrast to all VMMs which accept up to 600 Mbit/s input rates but drop packets down to the depicted maximum accumulated throughput. Another behavior which cannot be seen in the bar plots is that we measured a significant difference in the mean throughput of the three data streams for the VMware system without the para-virtualized driver.

K V M O p e n V Z V M w - E V M w -V M X e n V B o x Measured Throughput [Mbit/s]
K V M O p e n V Z V M w -E V M w -V M X e n V B o x Measured Throughput [Mbit/s]
K V M O p e n V Z V M w - E V M w - V M X e n V B o x Measured Throughput [Mbit/s]
K V M O p e n V Z V M w -E V M w -V M X e n V B o x Measured Throughput [Mbit/s]
The results in Figure 4 show that most VMMs have a throughput limitation, which varies with the packet size. All VMMs except OpenVZ reveal this limitation even for 1500 byte packet sizes. Only OpenVZ is able to forward packets of this size with the same performance as the raw system. However, if we look at the results for the other packet sizes, we clearly see the impact of virtualization even for OpenVZ. For smaller packet sizes, i.e. 500 byte and below, the VMware with the para-virtualized VMXNET3 driver (abbreviated by VMw-VM in the figures) outperforms all other solutions.

In conclusion, we see that the performance costs of virtualization gets higher, the more small packets are sent and the higher the bandwidth on the UUT is. Also OpenVZ, which only provides OS-level virtualization, has a noticeable influence on the systems' performance in these cases. The biggest problem identified is that the VMMs try to take as many packets of the network card as possible and therefore prevent layer-2 flow control to limit incoming data to a rate, which can be handled by the system. Hence, the majority of packets is lost before entering the guest system.

Isolation of Guest Systems

Initially, we conducted tests with a second virtual guest Linux that was only idle. These tests showed that the difference to the scenario with only a single guest are mostly negligible. Only OpenVZ showed a difference in the shape of its collapse for high offered bandwidth rates with small packets. Hence, we focus in this paper on the more interesting effects. More details are provided in [START_REF] Schlosser | Performance Comparison of Common Server Hardware Virtualization Solutions Regarding the Network Throughput of Virtualized Systems[END_REF]. For 64 byte packets it seems as if the VMware system with VMXNET3 driver outperforms the unvirtualized system. But this is not the case. Due to the fact that we send packets through the second guest relative to the performance we measured before, the raw system handles 270 Mbit/s of 64 byte packets in the background and forwards all packets. The VMware system is only forwarding about 200 Mbit/s in the second guest and is buying the higher throughput of the test system by a loss rate of about 20%.

K V M O p e n V Z V M w - E V M w - V M X e n V B
K V M O p e n V Z V M w - E V M w - V M X e n V B
The offered bandwidth and the measured throughput for the second guest in this experiment are provided for both load scenarios in Table 2 and Table 3, respectively. These measurements reveal that the second guest is also negatively affected. If both guests are forwarding 64 byte packets, loss rates up to 50% can be experienced. The most severe impact can again be seen for OpenVZ. It seems as if the well known problem of the Linux kernel to handle small packets, c.f. [START_REF] Han | PacketShader: a GPU-accelerated software router[END_REF], has an even larger impact when using OS-level virtualization. This effect has to be considered when planning experiments on experimentation facilities using this kind of virtualization, as it might cause a high variance in the results of experiments, depending on the processes in other guest systems.

Conclusion

In this paper, we analyzed the impact of virtualization for a single system in terms of packet forwarding throughput. We compared KVM, OpenVZ, VMware, Xen, and VirtualBox to a raw host system and the impact of another virtual guest system performing CPU and memory intensive tasks as well as forwarding of small packets. Our results revealed that the impact of virtualization is noticeable for most virtualization platforms even when only considering the throughput on a single network interface. When increasing the number of interfaces and traffic sources, each VMM revealed a throughput bottleneck, which depends on the size of the packets being transmitted but is significantly lower than the forwarding capacity of the raw system. The impact of a second guest, which is idle or running only CPU and memory intensive tasks, is rather small. However, a second guest that forwards small packets even at comparably low rates is able to influence the performance of a virtualized system severely. Our findings show that virtualized and the traffic they handle need to be monitored. In professional system, network monitoring and exact measurements of the used systems enable the diagnosis of performance bottlenecks and definition of relocation strategies. But also for research facilities, in which many scientists share the resources of a test bed, it is crucial to record all influences which might be introduced by another test running on the same test bed, in order to provide credible scientific results. In future work, we will integrate the results from this paper into performance models for virtualized systems and virtual software routers to analyze and optimize throughput and isolation.

Fig. 1 :

 1 Fig. 1: Virtualization concepts of the considered VMMs.

Fig. 2 :

 2 Fig. 2: The hardware setup.

Fig. 4 :

 4 Fig. 4: Maximum accumulated throughput of VMMs.

Fig. 5 :

 5 Fig.5: Maximum throughput considering a second guest transmitting small packets relative to the maximum throughput in the dedicated scenario, c.f. Figure4d.

Table 1 :

 1 Averaged relative throughput changes considering a single traffic source and a second guest running CPU/Memory intensive processes,cf. Section 3.4.

	packet	KVM	OpenVZ	VM-E1000	VM-VMXNET3		Xen	VirtualBox
	size light	heavy light	heavy light	heavy light	heavy light	heavy light	heavy
	64 4.2%	-0.4% 1.0%	-18.2% -2.7% -4.5% -0.5% -0.6% 6.8%	7.9%	2.1%	2.0%
	500 5.5%	4.0%	1.5%	-11.4% -4.4% -5.3% 0.0%	-0.1% 3.7%	3.4%	-2.0% -4.0%
	1000 5.1%	5.6%	0.0%	0.0%	0.0%	0.0%	0.0%	0.0%	0.8%	1.7%	3.6%	-4.8%
	1500 0.0%	0.0%	0.0%	0.0%	0.0%	0.0%	0.0%	0.0%	0.0%	0.0%	3.4%	2%

Table 2 :

 2 Averaged offered bandwidth (in) and throughput measured(out) for 2nd guest in background at 50% relative load, c.f. Figure4d.

Acknowledgments The authors would like to thank Prof. Tran-Gia for the stimulating environment which was a prerequisite for this work.

This work was funded by the Federal Ministry of Education and Research (BMBF) of the Federal Republic of Germany (Förderkennzeichen 01BK0917, GLab). The authors alone are responsible for the content of the paper.

to offload the same amount of traffic to the UUT in all cases. This behavior is caused by layer-2 flow control. Whenever the frame buffer of the network card is fully occupied, the network card sends a notification to the sending interfaces to throttle down the packet rate. The maximum throughput of the UUT is never affected by this behavior. We kept it activated, as it provides another option to the test system to react on traffic rates it cannot handle besides dropping packets. Please note that in all cases in which the layer-2 flow control is actively reducing the sent packets, the test system already drops packets. This behavior, therefore, never influences the maximum throughput of the system. The second observable effect is the behavior of OpenVZ when forwarding 64 byte packets.

The OpenVZ system achieves a maximum throughput at a given input rate and collapses afterwards. We also notice this effect in other scenarios with 64 byte and 500 byte packet sizes. But in these cases, the throughput rate does not only collapse but is heavily varying for some offered traffic rates. Next, we consider how the throughput of the UUT scales if we increase the number of traffic generators. Figure 4 depicts the maximum achieved throughput with one, two, and three traffic sources. Note that as we have seen, e.g. in Figure 3c, the maximum achieved throughput is not necessarily recorded at the highest offered bandwidth. The bar plot for the UUT without any VMM reveals The impact of a second virtual guest, which is performing CPU and memory intensive tasks, is also small. We, therefore, provide only the difference in maximum achieved throughput in Table 1. It has to be noted that positive values in Table 1 correspond to an increase of throughput under these conditions. For example, Xen forwards in any considered scenario more packets, if a second virtual guest is running CPU or CPU and memory intensive tasks. Only OpenVZ is negatively affected by more than 10% relative forwarding performance considering small packets. This effect might be caused by the fact that OpenVZ, in the original implementation, does not foresee the option to restrict the execution of processes to predefined CPUs. Thus, the stress processes are run on all CPUs compared to the other scenarios, where the stress processes are strictly bound to the CPU of the second process. It has to be noted that both OS containers in OpenVZ are started with the "CPUUNIT" parameter, which means equal sharing of CPU resources. This result is surprising and we intend to study it closer in future work.

However, the impact of a second guest is clearly recognizable, whenever it is handling small packets. Figure 5 depicts our measurement results for the measurement scenario in which the second guest forwards small packets, cf. Section 3.4. Even if the UUT is only handling 1500 byte packets KVM and Xen achieve a lower maximum throughput. But if we consider the results for streams of 1000 byte and 500 byte packets, also OpenVZ and VMware without a paravirtualized network driver are affected, whereas the raw system and the VMware guest with VMXNET3 driver still handle all packets.


George Bosilca

Clément Foyer

Emmanuel Jeannot

Guillaume Mercier

Guillaume Papauré

Online Dynamic Monitoring of MPI Communications

Keywords: MPI, Monitoring, Communication Pattern, Process Placement

As the complexity and diversity of computer hardware and the elaborateness of network technologies have made the implementation of portable and efficient algorithms more challenging, the need to understand application communication patterns has become increasingly relevant. This paper presents details of the design and evaluation of a communication-monitoring infrastructure developed in the Open MPI software stack that can expose a dynamically configurable level of detail concerning application communication patterns.

Introduction

With the expected increase of applications concurrency and input data size, one of the most important challenges to be addressed in the forthcoming years is data transfer and locality (i.e., how to improve data accesses and transfers in the application). Among the various aspects of locality, one issue stems from the memory and the network. Indeed, the transfer time of data exchanges between processes of an application depends on both the affinity of the processes and their location. A thorough analysis of the application's behavior and of the target underlying execution platform combined with clever algorithms and strategies have the potential to dramatically improve the application communication time, making it more efficient and robust in the midst of changing network conditions (e.g., contention). The general consensus is that the performance of many existing applications could benefit from improved data locality [START_REF] Hoefler | An overview of topology mapping algorithms and techniques in high-performance computing[END_REF].

Hence, to compute an optimal -or at least an efficient -process placement we need to understand the underlying hardware characteristics (including memory hierarchies and network topology) and how the application processes are exchanging messages. The two inputs of the decision algorithm are therefore the machine topology and the application communication pattern. The machine topology information can be gathered through existing tools or be provided by a management system. Among these tools Netloc/Hwloc [START_REF] Broquedis | hwloc: A generic framework for managing hardware affinities in hpc applications[END_REF] provides a (nearly) portable way to abstract the underlying topology as a graph interconnecting the various computing resources. Moreover, the batch scheduler and system tools can provide the list of resources available to the running jobs and their interconnections.

To address the second point and understand the data exchanges between processes, precise information about the application communication patterns is needed. Existing tools are either addressing the issue at a high level and thus failing to provide accurate details, or they are intrusive and deeply embedded in the communication library. To confront these issues, we designed a light and flexible monitoring interface for MPI applications with the following features. First, the need to monitor more than simply two-sided communications-interactions in which the source and destination of the message are explicitly invoking an API for each message-is becoming prevalent. As such, our monitoring support is capable of extracting information about all types of data transfers: two-sided, one-sided (or remote memory access), and I/O. In the scope of this paper, we will focus our analysis on one-and two-sided communications. We recorded the number of messages, the sum of message sizes, and the distribution of the sizes between each pair of processes. We also recorded how these messages have been generated by direct user calls via the two-sided API or automatically generated as a result of collective algorithms, a process related to one-sided messages. Second, we provided mechanisms for the MPI applications themselves to access this monitoring information through the MPI tool information interface. This allowed the monitoring-which may involve recording only specific parts of the code or recording only during particular time periods-to be dynamically enabled or disabled, and it gave the ability to introspect the application behavior. Last, the output of this monitoring provides different matrices describing this information for each pair of processes. Such data is available both online (i.e., during the application execution) and off-line (i.e., for the post-mortem analysis and optimization of a subsequent run).

We conducted experiments to assess the overhead of this monitoring infrastructure and to demonstrate its effectiveness as compared with other solutions from the literature.

In Section 2 of this paper we present the related work; in Section 3, the required background; in Section 4, the design; in Section 5, the implementation; in Section 6, the result; and in Section 7, the conclusion.

Related Work

Monitoring an MPI application can be achieved in many ways but in general relies on intercepting the MPI API calls and delivering aggregated information. We present here some examples of such tools.

PMPI is a customizable profiling layer that allows tools to intercept MPI calls. Therefore, when a communication routine is called, keeping track of the processes involved and the amount of data exchanged is possible. This approach has drawbacks, however. First, managing MPI datatypes is awkward and requires a conversion at each call. Also, PMPI cannot comprehend some of the most critical data movements, because an MPI collective is eventually implemented by point-to-point communications, and yet the participants in the underlying data exchange pattern cannot be guessed without knowledge of the collective algorithm implementation. A reduce operation is, for instance, often implemented with an asymmetric tree of point-to-point sends/receives in which every process has a different role (i.e., root, intermediary, and leaves). Known examples of stand-alone libraries using PMPI are DUMPI [START_REF] Janssen | A simulator for large-scale parallel computer architectures[END_REF] and mpiP [START_REF] Vetter | Statistical scalability analysis of communication operations in distributed applications[END_REF].

Another tool for analyzing and monitoring MPI programs is Score-P [START_REF] Knüpfer | Score-P: A Joint Performance Measurement Run-Time Infrastructure for Periscope[END_REF]. It is based on different but partially redundant analyzers that have been gathered within a single tool to allow both online and offline analysis. Score-P relies on MPI wrappers and call-path profiles for online monitoring. Nevertheless, the application monitoring support offered by these tools is kept outside of the library, which means access to the implementation details and the communication pattern of collective operations once decomposed is limited.

PERUSE [START_REF] Keller | Implementation and Usage of the PERUSE-Interface in Open MPI[END_REF] takes a different approach, in that it allows the application to register callbacks that will be raised at critical moments in the point-to-point request lifetime. This method provides an opportunity to gather information on state-changes inside the MPI library and gain detailed insight on what type of data (i.e., point-to-point or collectives) is exchanged between processes, as well as how and when. This technique has been used in [START_REF] Brown | Tracing Data Movements Within MPI Collectives[END_REF][START_REF] Keller | Implementation and Usage of the PERUSE-Interface in Open MPI[END_REF].

Tools that provide monitoring that is both light and precise (e.g., showing collective communication decomposition) do not exist.

Background

The Open MPI Project [START_REF] Gabriel | Open MPI: Goals, Concept, and Design of a Next Generation MPI Implementation[END_REF] is a comprehensive implementation of the MPI 3.1 standard [START_REF] Forum | MPI: A Message-Passing Interface Standard[END_REF] that was started in 2003 and takes ideas from four earlier institutionally based MPI implementations. Open MPI is developed and maintained by a consortium of academic, laboratory, and industry partners and is distributed under a modified BSD open-source license. It supports a wide variety of CPU and network architectures used in HPC systems. It is also the base for a number of commercial MPI offerings from vendors, including Mellanox, Cisco, Fujitsu, Bull, and IBM. The Open MPI software is built on the Modular Component Architecture (MCA) [START_REF] Barrett | Analysis of the Component Architecture Overhead in Open MPI[END_REF], which allows for compile or runtime selection of the components used by the MPI library. This modularity enables experiments with new designs, algorithms, and ideas to be explored while fully maintaining functionality and performance. In the context of this study, we take advantage of this functionality to seamlessly interpose our profiling components along with the highly optimized components provided by the stock Open MPI version. MPI Tool Information Interface has been added in the MPI-3 standard [START_REF] Forum | MPI: A Message-Passing Interface Standard[END_REF]. This interface allows the application to configure internal parameters of the MPI library and get access to internal information from the MPI library. In our context, this interface will offer a convenient and flexible way to access the monitored data stored by the implementation and control of the monitoring phases.

Process placement is an optimization strategy that takes into account the affinity of processes (represented by a communication matrix) and the machine topology to decrease the communication costs of an application [START_REF] Hoefler | An overview of topology mapping algorithms and techniques in high-performance computing[END_REF]. Various algorithms to compute such a process placement exist, one being TreeMatch [START_REF] Jeannot | Process Placement in Multicore Clusters: Algorithmic Issues and Practical Techniques[END_REF] (designed by a subset of the authors of this article). We can distinguish between static process placement, which is computed from traces of previous runs, and dynamic placement computed during the application execution (see the experiments in Section 6).

Design

Monitoring generates the application communication pattern matrix. The order of the matrix is the number of processes, and each (i, j) entry gives the amount of communication between process i and process j. Monitoring outputs several values and, hence, several matrices: the number of bytes and the number of messages exchanged. Moreover, it distinguishes between point-to-point communications and collective or internal protocol communications.

It is also able to keep track of collective operations after their transition to point-to-point communications. Therefore, monitoring requires interception of the communication inside the MPI library itself instead of relinking weak symbols to a third-party dynamic one, which allows this component to be used in parallel with other profiling tools (e.g., PMPI).

For scalability reasons, we can automatically gather the monitoring data into one file instead of dumping one file per rank.

In summary, we plan to cover a wide spectrum of needs while employing different levels of complexity for various levels of precision. Our design provides an API for each application to enable, disable, or access its own monitoring information. Otherwise, an application can be monitored without any modification of its source code by activating the monitoring components at launch time; results are retrieved when the application completes.

We also supply a set of mechanisms to combine monitored data into communication matrices. They can be used either at the end of the application (when MPI_Finalize is called) or post-mortem. For each pair of processes, a histogram of geometrically increasing message sizes is available.

Implementation

The precision required for the results prompted us to implement the solution within the Open MPI stack5 . The component described in this article was developed in a branch of Open MPI (available at [14]) and is now available in the development version of Open MPI, and on all stable version after 3.0. Because we were planning to intercept all types of communications-two-sided, one-sided, and collectives-we exposed a minimalistic common API for the profiling as an independent engine and then linked all the MCA components doing the profiling with this engine. Due to the flexibility of the MCA infrastructure, the active components can be configured at runtime either via mpirun arguments or via the API (implemented with the MPI Tool Information Interface). All implementation details are available at [START_REF] Bosilca | Online Dynamic Monitoring of MPI Communications: Scientific User and Developper Guide[END_REF].

To cover the wide range of operations provided by MPI, we added four components to the software stack: one in the collective communication layer (COLL), one in the one-sided layer (remote memory accesses, OSC), one in the point-topoint management layer (PML), and one common layer capable of orchestrating the information gathered by the other layers and record data. When activated at launch time (through the mpiexec option --mca pml_monitoring_enable x ), this enable all monitoring components, as indicated by the comma-separated value of x. The design of Open MPI allows for easy distinctions between different types of communication tags, and x allows the user to include or exclude tags related to collective communications or to other internal coordination (these are called internal tags as opposed to external tags, which are available to the user via the MPI API).

Specifically, the PML layer sees communications after collectives have been decomposed into point-to-point operations. COLL and OSC both work at a higher level to be able to record operations that do not go through the PML layer (e.g. when dedicated drivers are used). Therefore, as opposed to the MPI standard profiling interface (PMPI) method where the MPI calls are intercepted, we monitored the actual point-to-point calls that are issued by Open MPI, which yields much more precise information. For instance, we can infer the underlying topologies and algorithms behind the collective algorithms (e.g. the tree topology used for aggregating values in an MPI_Reduce call). However, this comes at the cost of a possible redundant recording of data for collective operations when the data-path goes through the COLL and the PML components 6 .

For an application to enable, disable or access its own monitoring, we implemented a set of callback functions using the MPI Tool Information Interface. The functions make knowing the amount of data exchanged between a pair of processes possible at any time and in any part of the application's code. An example of such code is given in Fig. 1. The call to MPI_T_pvar_get_index provides the index (e.g., the key) of the performance variable. This variable is allocated and attached to the communicator with a call to MPI_T_pvar_handle_alloc. This starts a monitoring phase that resets the internal monitoring state. Then, an MPI_T session is started with the MPI_T_pvar_start call. When necessary, the monitored values are retrieved with MPI_T_pvar_read. Last, a call to MPI_Allreduce allows each processes to get the maximum of each value.

Furthermore, the final summary dumped at the end of the application gives us a detailed output of the data exchanged between processes for each pointto-point, one-sided, and collective operation. The user is then able to refine the results.

Internally, these components use an internal process identifier (ids) and a single associative array employed to translate sender and receiver ids into their MPI_COMM_WORLD counterparts. Our mechanism is, therefore, oblivious to communicator splitting, merging, or duplication. When a message is sent, the sender updates three arrays: the number of messages, the size (in bytes) sent to the specific receiver, and the message size distribution. Moreover, to distinguish between external and internal tags, one-sided emitted and received messages, and collective operations, we maintain five versions of the first two arrays. Also, the histogram of message sizes distribution is kept for each pair of ids, and goes from 0 byte messages to messages of more than 2 64 bytes. Therefore, the memory overhead of this component is at maximum 10 arrays of N 64 bits elements, in addition to the N arrays of 66 elements of 64 bits for the histograms, with N being the number of MPI processes. These arrays are lazily allocated, so they exist for a remote process only if communications occur with it.

In addition to the amount of data and the number of messages exchanged between processes, we keep track of the type of collective operations issued on each communicator: one-to-all operations (e.g., MPI_Scatter), all-to-one operations (e.g., MPI_Gather) and all-to-all operations (e.g., MPI_Alltoall). For the first two types of operations, the root process records the total amount of data sent and received respectively and the count of operations of each kind. For all-to-all operations, each process records the total amount of data sent and the count of operations. All these pieces of data can be flushed into files either at the end of the application or when requested through the API.

Results

We conducted out the experiments on an Infiniband cluster (HCA: Mellanox Technologies MT26428 (ConnectX IB QDR)). Each node features two Intel Xeon Nehalem X5550 CPUs with 4 cores (2.66 GHz) per each CPU.

Overhead Measurement

One of the main issues of monitoring is the potential impact on the application time-to-solution. As our monitoring can be dynamically enabled and disabled, we can compute the upper bound of the overhead by measuring the impact with the monitoring enabled on the entire application. We wrote a micro benchmark that computes the overhead induced by our component for various kinds of MPI functions and measured this overhead for both shared-and distributed-memory cases. The number of processes varies from 2 to 24, and the amount of data ranges from 0 up to 1MB. Fig. 2 displays the results as heatmaps (the median of a thousand measures). Blue nuances correspond to low overhead, and yellow Fig. 1: Monitoring Code Snippet. colors to higher overhead. As expected, the overhead was more visible on a shared memory setting, where the cost of the monitoring is more significant compared with the decreasing cost of data transfers. Also, as the overhead is related to the number of messages and not to their content, the overhead decreases as the size of the messages increased. Overall, the median overhead is 4.4% and 2.4% respectively for the shared-and distributed-memory cases, which proves that our monitoring is cost effective. To measure the impact on applications, we used some of the NAS parallel benchmarks-namely BT, CG and LU. These tests have the highest number of MPI calls, and so we chose them to maximize the potential impact of the monitoring on the application. Table 1 shows the results, which are an average of 20 runs. Shaded rows mean that the measures display a statistically significant difference (using the Student's t-Test on the measures) between a monitored run and non-monitored one. Overall, we see that the overhead is consistently below 1% and on average around 0.35%. Interestingly, for the LU kernel, the overhead seems lightly correlated with the message rate, meaning the larger the communication activity, the higher the overhead. For the CG kernel, however, the timings are so small that it is hard to see any influence of this factor beyond We have also tested the Minighost mini-application [START_REF] Barrett | Minighost: a miniapp for exploring boundary exchange strategies using stencil computations in scientific parallel computing[END_REF] that computes a stencil in various dimensions to evaluate the overhead. An interesting feature of this mini-application is that it outputs the percentage of time spent to perform communication. In Fig. 3, we depict the overhead depending on this communication ratio. We ran 114 different executions of the MiniGhost application and split those runs into four range categories depending on the percentage of time spent in communications (0%-25%, 25%-50%, 50%-75% and 75%-100%). A point represents the median overhead (in percent) and the error bars represent the first and third quartile. We see that the median overhead is increasing with the percentage of communication. Indeed, the more time you spend in communication the more visible the overhead for monitoring these communications. However, the overhead accounts for only a small percentage.

q q q q 0 1 2 3 0% -25% 25% -50% 50% -75% 75% -100%

Ratio of communication Median overhead percentage

Fig. 3: Minighost application overhead as a function of the communication percentage of the total execution time.

MPI Collective Operations Optimization

In these experiments we have executed an MPI_Reduce collective call on 32 and 64 ranks (on 4 and 8 nodes respectively), with a buffer that ranged from 1.10 6 to 2.10 8 integers and a rank of 0 acting as the root. We took advantage of the Open MPI infrastructure to block the dynamic selection of the collective algorithm and instead forced the reduce operation to use a binary tree algorithm. Because we monitored the collective communications after they have been broken down into point-to-point communications, we were able to identify details of the collective algorithm implementation and expose the underlying binary tree algorithm (see Fig. 4b). This provided a much more detailed understanding of the underlying communication pattern compared with existing tools, where the use of a higher-level monitoring tool (e.g., PMPI) completely hides the collective algorithm communications. With this pattern, we used the TreeMatch algorithm to compute a new process placement and compared it with the placement obtained using a high-level monitoring method (that does not see the tree and hence is equivalent to the round-robin placement). Results are shown in Fig. 4a. We see that the optimized placement is much more efficient than the one based on high-level monitoring. For instance with 64 ranks and a buffer of 5.10 6 integers the walltime is 338 ms vs. 470 ms (39% faster). Fig. 4: MPI_Reduce Optimization.

Use Case: Fault Tolerance with Online Monitoring

In addition to the usage scenarios mentioned above, the proposed dynamic monitoring tool has been demonstrated in our recent work. In [START_REF] Cores | An application-level solution for the dynamic reconfiguration of mpi applications[END_REF]we used the dynamic monitoring feature to compute the communication matrix during the execution of an MPI application. The goal was to perform elastic computations in case of node failures or when new nodes are available. The runtime system migrated MPI processes when the number of computing resources changed. To this end, the authors used the TreeMatch [START_REF] Jeannot | Process Placement in Multicore Clusters: Algorithmic Issues and Practical Techniques[END_REF] algorithm to recompute the process mapping onto the available resources. The algorithm decides how to move processes based on the application's gathered communication matrix: the more two processes communicate, the closer they are remapped onto the physical resources. Gathering the communication matrix was performed online using the callback routines of the monitoring: such a result would not have been possible without the tool proposed in this paper.

Static Process Placement of applications

We tested the TreeMatch algorithm for performing static placement to show that the monitoring provides relevant information allowing execution optimization. To do so, we first monitored the application using the proposed monitoring tool of this paper. Second, we built the communication matrix (here using the number of messages) and then applied the TreeMatch algorithm on this matrix and the topology of the target architecture. Finally, we re-executed the application using the newly computed mapping. Different settings (kind of stencil, the stencil dimension, number of variables per stencil point, and number of processes) are shown in fig. 5. We see that the gain is up to 40% when compared with round-robin placement (the standard MPI placement) and 300% against random placement. The decrease of performance is never greater than 2%.

Conclusion

Parallel applications tend to use a growing number of computational resources connected via complex communication schemes that naturally diverge from the underlying network topology. Optimizing the performance of applications requires any mismatch between the application communication pattern and the network topology to be identified, and this demands a precise mapping of all data exchanges between the application processes.

In this paper we proposed a new monitoring framework to consistently track all types of data exchanges in MPI applications. We implemented the tool as a set of modular components in OPEN MPI that allow fast and flexible lowlevel monitoring (with collective operation decomposed to their point-to-point expression) of all types of communications supported by the MPI-3 standard (including one-sided communications and I/O). We also provided an API based on the MPI Tool Information Interface standard for applications to monitor their state dynamically, with a focus on only the critical portions of the code. The basic use of this tool does not require any change in the application nor any special compilation flag. The data gathered can be provided at different granularities, either as communication matrices or as histograms of message sizes. Another significant feature of this tool is that it leaves the PMPI interface available for other usages, allowing additional monitoring of the application using more traditional tools.

Microbenchmarks show that the overhead is minimal for intra-node communications (over shared memory) and barely noticeable for large messages or distributed memory. After being applied to real applications, the overhead remain hardly visible (at most, a few percentage points). Having such a precise and flexible monitoring tool opens the door to dynamic process placement strategies and could lead to highly efficient process placement strategies. Experiments show that this tool enables large gain for dynamic or static cases. The fact that the monitoring records the communication after collective decomposition into point-to-points allows optimizations that were not otherwise possible.

Fig. 2 :

 2 Fig. 2: Monitoring overhead for MPI_Send, MPI_Alltoall and MPI_Put operations. Left: distributed memory, right: shared memory.

  monitoring PML MonitoringMPI_Reduce time at root after process placement (a) MPI_Reduce (MPI_MAX) walltime (x and y logscale) for 32 and 64 ranks and various buffer sizes. Process placement based on our PML monitoring vs. highlevel monitoring (RR placement) pattern as seen by our monitoring tool (once the collective communication is decomposed into point-to-point communications).

Fig. 5 :

 5 Fig. 5: Average gain of TreeMatch placement vs. Round Robin and random placements for various MiniGhost runs.

Table 1 :

 1 Overhead for the BT, CG and LU NAS kernels measurements noise.

	Kernel Class NP	Monitoring time	Non mon. time	#msg/proc Overhead #msg/sec
	bt	A 16	6.449	6.443	2436.25	0.09%	6044.35
	bt	A 64	1.609	1.604	4853.81	0.31%	193066.5
	bt	B 16 27.1285	27.1275	2436.25	0.0%	1436.87
	bt	B 64	6.807	6.8005	4853.81	0.1%	45635.96
	bt	C 16 114.6285 114.5925	2436.25	0.03%	340.06
	bt	C 64	27.23	27.2045	4853.81	0.09%	11408.15
	cg	A 16	0.1375	0.1365	1526.25	0.73%	177600.0
	cg	A 32	0.103	0.1	2158.66	3.0%	670650.49
	cg	A 64	0.087	0.0835	2133.09	4.19% 1569172.41
	cg	B	8	11.613	11.622	7487.87	-0.08%	5158.27
	cg	B 16	6.7695	6.7675	7241.25	0.03%	17115.0
	cg	B 32	3.8015	3.796	10243.66	0.14%	86228.33
	cg	B 64	2.5065	2.495	10120.59	0.46% 258415.32
	cg	C 32	9.539	9.565	10243.66	-0.27% 34363.87
	cg	C 64	6.023	6.0215	10120.59	0.02% 107540.76
	lu	A	8	8.5815	8.563	19793.38	0.22%	18452.14
	lu	A 16	4.2185	4.2025	23753.44	0.38%	90092.45
	lu	A 32	2.233	2.2205	25736.47	0.56% 368816.39
	lu	A 64	1.219	1.202	27719.36	1.41% 1455323.22
	lu	B	8	35.2885	35.2465	31715.88	0.12%	7190.08
	lu	B 16	18.309	18.291	38060.44	0.1%	33260.53
	lu	B 32	9.976	9.949	41235.72	0.27% 132271.75
	lu	B 64	4.8795	4.839	44410.86	0.84% 582497.18
	lu	C 16	72.656	72.5845	60650.44	0.1%	13356.19
	lu	C 32 38.3815	38.376	65708.22	0.01%	54783.24
	lu	C 64	20.095	20.056	70765.86	0.19% 225380.19

  Group by Number of proc, Number of variables and affinity metric type

									64					64				64						128						128						128						128		128
			1						4					20				40							1							4							10						20		40
	1.4
	0.98 1 1.1 1.2 1.4 2 3 Gain (avg values)																																																TM vs. Round Robin TM vs. Random
	1.2
	1.1
	0.98 1
	1_21	1_23	1_24	10_21	10_23	10_24	1_21	1_23	1_24	10_21	10_23	10_24	10_21	10_23	10_24	1_23	1_24	10_21	10_23	10_24	70_21	70_23	1_21	1_23	1_24	10_21	10_23	10_24	95_21	95_23	1_21	1_23	1_24	10_21	10_23	10_24	55_21	55_23	55_24	79_21	79_23	79_24	95_21	95_23	95_24	10_21	10_23	10_24	10_21 10_23 10_24 55_21 55_23 55_24 79_21 79_23 79_24 95_21 95_23 95_24
																	Grid size and stencil type

A proof-of-concept version of this monitoring has been implemented in MPICH

Nevertheless, a precise monitoring is still possible with the use of the monitoring API.

Acknowledgments

This work is partially funded under the ITEA3 COLOC project #13024, and by the USA NSF grant #1339820. The PlaFRIM experimental testbed is being developed with support from Inria, LaBRI, IMB, and other entities: Conseil Régional d'Aquitaine, FeDER, Université de Bordeaux, and CNRS.