Nicoló Rivetti
email: rivetti@dis.uniroma1.it

Yann Busnel
email: yann.busnel@ensai.fr

Leonardo Querzoni
email: querzoni@dis.uniroma1.it

Load-Aware Shedding in Stream Processing Systems

Keywords: CCS Concepts, Software and its engineering → Distributed systems organizing principles;, Theory of computation Stream Processing, Data Streaming, Load Shedding

Load shedding is a technique employed by stream processing systems to handle unpredictable spikes in the input load whenever available computing resources are not adequately provisioned. A load shedder drops tuples to keep the input load below a critical threshold and thus avoid tuple queuing and system trashing. In this paper we propose Load-Aware Shedding (LAS), a novel load shedding solution that drops tuples with the aim of maintaining queuing times below a tunable threshold. Tuple execution durations are estimated at runtime using efficient sketch data structures. We provide a theoretical analysis proving that LAS is an (ε, δ)approximation of the optimal online load shedder and show its performance through a practical evaluation based both on simulations and on a running prototype.

INTRODUCTION

Distributed stream processing systems (DSPS) are today considered as a mainstream technology to build architectures for the real-time analysis of big data. An application running in a DSPS is typically modeled as a directed acyclic graph where data operators (nodes) are interconnected by streams of tuples containing data to be analyzed (edges). The success of such systems can be traced back to their ability to run complex applications at scale on clusters of commodity hardware.

Correctly provisioning computing resources for DSPS however is far from being a trivial task. System designers need Accepted to the 10th ACM International Conference on Distributed and Event-based Systems (DEBS '16) to take into account several factors: the computational complexity of the operators, the overhead induced by the framework, and the characteristics of the input streams. This latter aspect is often critical, as input data streams may unpredictably change over time both in rate and content. Bursty input load represents a problem for DSPS as it may create unpredictable bottlenecks within the system that lead to an increase in queuing latencies, pushing the system in a state where it cannot deliver the expected quality of service (typically expressed in terms of tuple completion latency). Load shedding is generally considered a practical approach to handle bursty traffic. It consists in dropping a subset of incoming tuples as soon as a bottleneck is detected in the system.

Existing load shedding solutions either randomly drop tuples when bottlenecks are detected or apply a pre-defined model of the application and its input that allows them to deterministically take the best shedding decision. In any case, all the existing solutions assume that incoming tuples all impose the same computational load on the DSPS. However, such assumption does not hold for many practical use cases. The tuple execution duration, in fact, may depend on the tuple content itself. This is often the case whenever the receiving operator implements a logic with branches where only a subset of the incoming tuples travels through each single branch. If the computation associated with each branch generates different loads, then the execution duration will change from tuple to tuple. A tuple with a large execution duration may delay the execution of subsequent tuples in the same stream, thus increasing queuing latencies and possibly cause the emergence of a bottleneck.

On the basis of this simple observation, we introduce Load-Aware Shedding (LAS), a novel solution for load shedding in DSPS. LAS gets rid of the aforementioned assumptions and provides efficient shedding aimed at matching given queuing latency goals, while dropping as few tuples as possible. To reach this goal LAS leverages a smart combination of sketch data structures to efficiently collect at runtime information on the time needed to compute tuples and thus build and maintain a cost model that is then exploited to take decisions on when load must be shed. LAS has been designed as a flexible solution that can be applied on a per-operator basis, thus allowing developers to target specific critical stream paths in their applications.

In summary, the contributions provided by this paper are (i) the introduction of LAS, the first solution for load shedding in DSPS that proactively drops tuples to avoid bottlenecks without requiring a predefined cost model and without any assumption on the distribution of tuples, (ii) a theoretical analysis of LAS that points out how it is an ( , δ)approximation of the optimal online shedding algorithm and, finally, (iii) an experimental evaluation that illustrates how LAS can provide predictable queuing latencies that approximate a given threshold while dropping a small fraction of the incoming tuples.

Below, the next section states the system model we consider. Afterwards, Section 3 details LAS whose behavior is then theoretically analyzed in Section 4. Section 5 reports on our experimental evaluation and Section 6 analyzes the related works. Finally Section 7 concludes the paper.

SYSTEM MODEL AND PROBLEM DEF-INITION

We consider a distributed stream processing system (DSPS) deployed on a cluster where several computing nodes exchange data through messages sent over a network. The DSPS executes a stream processing application represented by a topology: a directed acyclic graph interconnecting operators, represented by vertices, with data streams (DS), represented by edges.

Data injected by source operators is encapsulated in units called tuples and each data stream is an unbounded sequence of tuples. Without loss of generality, here we assume that each tuple t is a finite set of key/value pairs that can be customized to represent complex data structures. To simplify the discussion, in the rest of this work we deal with streams of unary tuples each representing a single non negative integer value. We also restrict our model to a topology with an operator LS (load shedder ) that decides which tuples of its outbound DS σ consumed by operator O shall be dropped. Tuples in σ are drawn from a large universe [n] = {1, . . . , n} and are ordered, i.e., σ = t1, . . . , tm . Therefore [m] = 1, . . . , m is the index sequence associated with the m tuples contained in the stream σ. Both m and n are unknown. We denote with ft the unknown frequency of tuple t, i.e., the number of occurrences of t in σ.

We assume that the execution duration of tuple t on operator O, denoted as w(t), depends on the content of t. In particular, without loss of generality, we consider a case where w depends on a single, fixed and known attribute value of t. The probability distribution of such attribute values, as well as w, are unknown, may differ from operator to operator and may change over time. However, we assume that subsequent changes are interleaved by a large enough time frame such that an algorithm may have a reasonable amount of time to adapt. On the other hand, the input throughput of the stream may vary, even with a large magnitude, at any time.

Let q(i) be the queuing latency of the i-th tuple of the stream, i.e., the time spent by the i-th tuple in the inbound buffer of operator O before being processed. Let us denote as D ⊆ [m], the set of dropped tuples in a stream of length m, i.e., dropped tuples are thus represented in D by their indices in the stream [m]. Moreover, let d ≤ m be the number of dropped tuples in a stream of length m, i.e., d = |D|. We can define the average queuing latency as:

Q(j) = i∈[j]\D q(i)/(j -d) for all j ∈ [m].
The goal of the load shedder is to maintain the average queuing latency smaller than a given threshold τ by dropping as less tuples as possible while the stream unfolds. The quality of the shedder can be evaluated both by comparing the resulting Q against τ and by measuring the number of dropped tuples d. More formally, the load shedding problem can be defined as follows 1 : Problem 2.1 (Load Shedding). Given a data stream σ = t1, . . . , tm , find the smallest set D such that ∀j ∈ [m] \ D, Q(j) ≤ τ.

LOAD AWARE SHEDDING

Overview

Load-Aware Shedding (LAS) is based on a simple, yet effective, idea: if we assume to know the execution duration w(t) of each tuple t in the operator, then we can foresee queuing times and drop all tuples that will cause the queuing latency threshold τ to be violated. However, the value of w(t) is generally unknown.

LAS builds and maintain at run-time a cost model for tuple execution durations. It takes shedding decision based on the estimation C of the total execution duration of the operator: C = i∈[m]\D w(ti). In order to do so, LAS computes an estimation ŵ(t) of the execution duration w(t) of each tuple t. Then, it computes the sum of the estimated execution durations of the tuples assigned to the operator, i.e., C = i∈[m]\D ŵ(t). At the arrival of the i-th tuple, subtracting from C the (physical) time elapsed from the emission of the first tuple provides LAS with an estimation q(i) of the queuing latency q(i) for the current tuple.

To enable this approach, LAS builds a sketch on the operator (i.e., a memory efficient data structure) that will track the execution duration of the tuples it processes. When a change in the stream or operator characteristics affects the tuples execution durations w(t), i.e., the sketch content changes, the operator will forward an updated version to the load shedder, which will than be able to (again) correctly estimate the tuples execution durations. This solution does not require any a priori knowledge on the stream or system, and is designed to continuously adapt to changes in the input stream or on the operator characteristics.

LAS design

The operator maintains two Count Min [START_REF] Cormode | An improved data stream summary: The count-min sketch and its applications[END_REF] sketch matrices (Figure 1.A): the first one, denoted as F, tracks the tuple frequencies ft; the second one, denoted as W, tracks the tuples cumulated execution durations Wt = w(t) × ft. Both Count Min matrices share the same sizes and 2-universal hash functions [START_REF] Carter | Universal classes of hash functions[END_REF]. The latter is a generalized version of the Count Min providing (ε, δ)-additive-approximation of point queries on stream of updates whose value is the tuple execution duration when processed by the instance. The operator will update (Listing 3.1 lines 27-30) both matrices after each tuple execution.

The operator is modeled as a finite state machine (Figure 2) with two states: START and STABILIZING. The START state lasts as long as the operator has executed N tuples, where N is a user defined window size parameter. The transition to the STABILIZING state (Figure 2.A)

c 1 2 3 4 r 2 1 F c 1 2 3 4 W F, W O LAS C F, W LS tuple | tuple, C F , W ∆ A B C D E Figure 1: Load-Aware Shedding design with r = 2 (δ = 0.25), c = 4 (ε = 0.70).
triggers the creation of a new snapshot S. A snapshot is a matrix of size r × c where ∀i ∈

[r], j ∈ [c] : S[i, j] = W[i, j]/F[i, j] (Listing 3.1 lines 15-17).
We say that the F and W matrices are stable when the relative error η between the previous snapshot and the current one is smaller than a configurable parameter µ, i.e.,

η = ∀i,j |S[i, j] -W[i,j] F [i,j]) | ∀i,j S[i, j] ≤ µ (1)
is satisfied. Then, each time the operator has executed N tuples (Listing 3.1 lines 18-25), it checks whether Equation 1 is satisfied. (i) In the negative case S is updated (Figure 2.B).

(ii) In the positive case the operator sends the F and W matrices to the load shedder (Figure 1.B), resets their content and moves back to the START state (Figure 2

.C).

There is a delay between any change in w(t) and when LS receives the updated F and W matrices. This introduces a skew in the cumulated execution duration estimated by LS. In order to compensate this skew, we introduce a synchronization mechanism that kicks in whenever the LS receives a new pair of matrices from the operator.

The LS (Figure 1.C) maintains the estimated cumulated execution duration of the operator C and a pairs of initially empty matrices F, W . LS is modeled as a finite state machine (Figure 3) with three states: NOP, SEND and RUN. The LS executes the code reported in Listing 3.2. In particular, every time a new tuple t arrives at the LS, the function shed is executed. The LS starts in the NOP state where no action is performed (Listing 3.2 lines 15-17). Here we assume that in this initial phase, i.e., when the topology has just been deployed, no load shedding is required. When LS receives the first pair F, W of matrices (Figure 3.A), it moves into the SEND state and updates its local pair of matrices (Listing 3.2 lines 7-9). While being in the SEND states, LS sends to O the current cumulated execution duration estimation C (Figure 1.D) piggy backing it with the first tuple t that is not dropped (Listing 3.2 lines 24-26) and moves in the RUN state (Figure 3

if state = Start ∧ m mod N = 0 then Figure 2.

27:

for i = 1 to r do 28:

F [i, h i (t)] ← F [i, h i (t)] + 1
29: In the RUN state, the load shedder computes, for each tuple t, the estimated queuing latency q(i) as the difference between the operator estimated execution duration C and the time elapsed from the emission of the first tuple (Listing 3.2 line 18). It then checks if the estimated queuing latency for t satisfies the Check method (Listing 3.2 lines 19-21).

W[i, h i (t)] ← W[i, h i (t)] + l 30:
This method encapsulates the logic for checking if a desired condition on queuing latencies is violated or not. In this paper, as stated in Section 2, we aim at maintaining the average queuing latency below a threshold τ . Then, Check tries to add q to the current average queuing latency (Listing 3.2 lines 31). If the result is larger than τ (i), it simply returns true; otherwise (ii), it updates its local value for the average queuing latency and returns f alse (Listing 3.2 lines 34-36). Note that different goals, based on the queuing latency, can be defined and encapsulated within Check.

If Check(q) returns true, (i) the load shedder returns true as well, i.e., tuple t must be dropped. Otherwise (ii), the operator estimated execution duration C is updated with the estimated tuple execution duration ŵ(t), increased by a factor 1 + ε to mitigate potential under-estimations2 , and the load shedder returns f alse (Listing 3.2 line 28), i.e., the tuple must not be dropped. Finally, if the load shedder receives a new pair F, W of matrices (Figure 3.D), it will again update its local pair of matrices and move to the SEND state (Listing 3.2 lines 7-9). Now we will briefly discuss the complexity of LAS.

Theorem 3.1 (Time complexity of LAS). For each tuple read from the input stream, the time complexity of LAS for the operator and the load shedder is O(log 1/δ).

Theorem 3.2 (Space Complexity of LAS).

The space complexity of LAS for the operator and load shed- Note that the communication cost is low with respect to the stream size since the window size N should be chosen such that N 1 (e.g., in our tests we have N = 1024). Proofs for the previous theorems are available in [START_REF] Rivetti | Load-aware shedding in stream processing systems[END_REF].

der is O 1 ε log 1 δ (log m + log n) bits.

THEORETICAL ANALYSIS

Data streaming algorithms strongly rely on pseudo-random functions that map elements of the stream to uniformly distributed image values to keep the essential information of the input stream, regardless of the stream elements frequency distribution. Here we provide the analysis of the quality of the shedding performed by LAS in two steps. First we study the correctness and optimality of the shedding algorithm, under full knowledge assumption (i.e., the shedding strategy is aware of the exact execution duration wt for each tuple t). For the sake of clarity, and to abide to space limits, all the proofs are available in a companion paper [START_REF] Rivetti | Load-aware shedding in stream processing systems[END_REF].

We suppose that tuples cannot be preempted, i.e. they must be processed in an uninterrupted fashion on the available operator instance. Given our system model, here we consider the problem of minimizing d, the number of dropped tuples, while guaranteeing that the average queuing latency Q(t) will be upper-bounded by τ , ∀t ∈ σ. The solution must work online, thus the decision of enqueueing or dropping a Listing 3.2: Load shedder 1: init do 2:

C ← 0 3: F , W ← 0r,c, 0r,c
zero matrices pair of size r × c

4:

Same hash functions h 1 . . . hr of the operator

5:

state ← NOP 6: end init 7: upon F , W do q ← C-elapsed time from first tuple 19:

if Check(q) then 20:

return true 21:

end if 22: i ← arg min i∈[r] {F [i, h i (t)]}
23:

C ← C + (W[i, h i (t)]/F [i, h i (t)]) × (1 + ε)

24:

if state = Send then Figure 3.B

25:

piggy back C to operator on t

26:

state ← Run

27:

end if

28:

return f alse 29: end function 30: function Check(q) 31:

if Q/ > τ then

32:

return true

33:

end if 34:

Q ← Q + q 35: ← + 1

36:

return f alse 37: end function tuple has to be made only resorting to knowledge about tuples received so far in the stream.

Let OPT be the online algorithm that provides the optimal solution to Problem 2.1. We denote with D σ OP T (resp. d σ OP T ) the set of dropped tuple indices (resp. the number of dropped tuples) produced by the OPT algorithm fed by stream σ (cf., Section 2). We also denote with d σ LAS the number of dropped tuples produced by LAS introduced in Section 3.2 fed with the same stream σ.

Theorem 4.1 (LAS Correctness & Optimality).

For any σ, we have

d σ LAS = d σ OP T and ∀t ∈ σ, Q σ LAS (t) ≤ τ .
Now we remove the previous assumptions and analyze the approximation made on execution duration w(t) for each tuple t. LAS uses two matrices, F and W, to estimate the execution time w(t) of each tuple submitted to the operator. By the Count Min sketch algorithm [START_REF] Cormode | An improved data stream summary: The count-min sketch and its applications[END_REF] and Listing 3.1, we have that for any t ∈ [n] and for each row i ∈ [r],

F[i][hi(t)] = ft + n u=1,u =t fu1 {h i (u)=h i (t)} .
and

W[i][hi(t)] = ftw(t) + n u=1,u =t fuw(u)1 {h i (u)=h i (t)} ,
Let us denote respectively by wmin and wmax the minimum and the maximum execution durations. We trivially have

wmin ≤ W[i][hi(t)] F[i][hi(t)] ≤ wmax (2)
Let assume that all the frequencies are equal 3 , that is for each t, we have ft = m/n. Let us define T = n t=1 w(t). We then have

E W[i][h i (t)] F [i][h i (t)] = T -w(t) n -1 - c(T -n × w(t)) n(n -1) 1 -1 - 1 c n
From the Markov inequality we have, for every x > 0,

Pr W[i][hi(t)] F[i][hi(t)] ≥ x ≤ E W[i][h i (t)] F [i][h i (t)]
x .

By the independence of the r hash functions, we obtain Pr min i=1,...,r

W[i][h i (t)] F [i][h i (t)] ≥ x ≤ Pr W[i][h i (t)] F [i][h i (t)] ≥ x r ≤   E W[i][h i (t)] F [i][h i (t)] x   r .
The proofs of these equations as well as some numerical applications to illustrate the accuracy are discussed in [START_REF] Rivetti | Load-aware shedding in stream processing systems[END_REF]. By finely tuning the parameter r to log(1/δ), under the assumption of [START_REF] Rivetti | Load-aware shedding in stream processing systems[END_REF], we are then able to (ε, δ)-approximate w(t) for any t ∈ [n]. Then, according to Theorem 4.1, LAS is an (ε, δ)-optimal algorithm for load shedding, as defined in Problem 2.1, over all possible data streams σ.

EXPERIMENTAL EVALUATION

In this section we evaluate the performance obtained by using LAS to perform load shedding. We will first describe the general setting used to run the tests and will then discuss the results obtained through simulations and with a prototype of LAS integrated within Apache Storm. Due to space constraints, the exhaustive presentation of these experiments are available in the companion paper [START_REF] Rivetti | Load-aware shedding in stream processing systems[END_REF].

Setup

Datasets -In our tests we consider both synthetic and real datasets. Synthetic datasets are built as streams of integer values (items) representing the values of the tuple attribute driving the execution duration when processed on the operator. We consider streams of m = 32, 768 tuples, each containing a value chosen among n = 4, 096 distinct items. Streams have been generated using the Uniform and Zipfian distributions with different values of α ∈ {0.5, 1.0, 1.5, 2.0, 2.5, 3.0}, denoted respectively as Zipf-0.5, Zipf-1.0, Zipf-1.5, Zipf-2.0, Zipf-2.5, and Zipf-3.0. We define wn as the number of distinct execution duration values that the tuples can have. These wn values are selected at constant distance in the interval [wmin, wmax]. Unless otherwise specified the frequency distribution is Zipf-1.0 and the stream parameters are set to wn = 64, wmin = 0.1 ms and wmax = 6.4 ms; this means that the wn = 64 execution durations are picked in the set {0.1, 0.2, • • • , 6.4} milliseconds. 3 The experimental evaluation (cf., Section 5.2) points out that uniform or lightly skewed distributions represent worst cases for our solution. Let W be the average execution duration of the stream tuples, then the stream maximum theoretical input throughput sustainable by the setup is equal to 1/W . When fed with an input throughput smaller than 1/W the system will be over-provisioned (i.e., possible underutilization of computing resources). Conversely, an input throughput larger than 1/W will result in an under-provisioned system. We refer to the ratio between the maximum theoretical input throughput and the actual input throughput as the percentage of under-provisioning that, unless otherwise stated, was set to 25%.

In order to generate 100 different streams, we randomize the association between the wn execution duration values and the n distinct items: for each of the wn execution duration values we pick uniformly at random n/wn different values in [n] that will be associated to that execution duration value. This means that the 100 different streams we use in our tests do not share the same association between execution duration and item as well as the association between frequency and execution duration (thus each stream has also a different average execution duration W ). Each of these permutations has been run with 50 different seeds to randomize the stream ordering and the generation of the hash functions used by LAS. This means that each single experiment reports the mean outcome of 5, 000 independent runs.

As constraints on the queuing latency we considered AVG(τ ), thus requiring that the total average queuing latency does not exceeds τ milliseconds: ∀i ∈ [m] \ D, Q(i) ≤ τ . In all our experiments we set τ = 6.4.

The LAS operator window size parameter N , the tolerance parameter µ and the number of rows of the F and W matrices δ are respectively set to N = 1024, µ = 0.05 and δ = 0.1 (i.e., r = 4 rows). By default, the LAS precision parameter (i.e., the number of columns of the F and W matrices) is set to ε = 0.05 (i.e., c = 54 columns), however in one of the test we evaluated LAS performance using several values: ε ∈ [0.001, 1.0].

For the real data, we used a dataset containing a stream of preprocessed tweets related to the 2014 European elections. Among other information, the tweets are enriched with a field mention containing the entities mentioned in the tweet. These entities can be easily classified into politicians, media and others. We consider the first 500, 000 tweets, mentioning roughly n = 35, 000 distinct entities and where the most frequent entity has an empirical probability of occurrence Tested Algorithms -We compare LAS performance against three other algorithms: (i) a Base Line algorithm that takes as input the percentage of under-provisioning and drops at random an equivalent fraction of tuples from the stream, (ii) a Straw-Man algorithm that uses the same shedding strategy of LAS considering the average execution duration W as the estimated execution duration ŵ(t) for each tuple t and (iii) a Full Knowledge algorithm that uses the same shedding strategy of LAS feeding it with the exact execution duration wt for each tuple t.

Evaluation Metrics -The evaluation metrics we provide, when applicable, are the dropped ratio α = d/m, the shedding ratio λ = (d alg -d Base Line )/d Base Line representing the ratio of tuples dropped by algorithm alg with respect to Base Line, the average queuing latency Q = i∈[m]\D q(i)/(md) and the average completion latency, i.e., the average time it takes for a tuple from the moment it is injected by the source in the topology, till the moment operator O concludes its processing. Whenever applicable we provide the maximum, mean and minimum figures over the 5, 000 runs.

Simulation Results

In this section we analyze through simulations the sensitivity of LAS while varying several characteristics of the input load. The simulator faithfully simulates the execution of LAS and the other algorithms and simulates the execution of each tuple t on O doing busy waiting for w(t) milliseconds. Further results, not included in this paper, are available in [START_REF] Rivetti | Load-aware shedding in stream processing systems[END_REF].

Input Throughput -Figure 4 shows the average queuing latency Q as a function of the percentage of underprovisioning ranging from 90% to -10% (i.e., the system is 10% over-provisioned with respect to the average input throughput). As expected, in this latter case all algorithms perform at the same level as load shedding is superfluous. In all the other cases both Base Line and Straw-Man do not shed enough load and induce a huge amount of exceeding queuing latency. On the other hand, LAS average queuing latency is quite close to the required value of τ = 6.4 milliseconds, even if this threshold is violated in some of the tests. Finally, Full Knowledge always abide to the constraint and is even able to produce a much lower average queuing latency while dropping no more tuples that the competing solutions. The resulting average queuing latency is strongly linked to which tuples are dropped: Base Line and Straw-Man, in particular, shed the same amount of tuples, LAS slightly more and Full Knowledge is in the middle. This result corroborates our initial claim that dropping tuples on the basis of the load they impose allows to design more effective load shedding strategies.

Frequency Probability Distributions -Figure 5 shows the average queuing latency Q (left) and shedding ratio λ (right) as a function of the input frequency distribution. As Figure 5a shows Straw-Man and Base Line perform invariably bad with any distribution. The span between the best and worst performance per run increases as we move from a uniform distribution to more skewed distributions as the latter may present extreme cases where tuple latencies match their frequencies in a way that is particularly favorable or unfavorable for these two solutions. Conversely, LAS performance improve the more the frequency distribution is skewed. This result stems from the fact that the sketch data structures used to trace tuple execution durations perform at their best on strongly skewed distribution, rather than on uniform ones. This result is confirmed by looking at the shedding ratio (Figure 5b) that decreases, on average, as the value of α for the distribution increases. Time Series -Figure 6 shows the average queuing latency Q (left) and dropped ratio α (right) as the stream unfolds (x-axis). Both metrics are computed on a jumping window of 4.000 tuples, i.e., each dot represent the mean queuing latency Q or the dropped ratio α computed on the previous 4.000 tuples. Notice that the points for Straw-Man, LAS and Full Knowledge related to a same value of the x-axis are artificially shifted to improve readability. In this test we set τ = 64 milliseconds. The input stream is made of 140.000 tuples and is divided in phases, from a A through G, each lasting 20.000 tuples. At the beginning of each phase we inject an abrupt change in the input stream throughput and distribution, as well as in w(t) as follows:

phase A : the input throughput is set in accordance with the provisioning (i.e., 0% under-provisioning); phase B : the input throughput is increased to induce 50% of under-provisioning; phase C : same as phase A; phase D : we swap the most frequent tuple 0 with a less frequent tuple t such that w(t) = wmax, inducing an abrupt change in the tuple values frequency distribution and in the average execution duration W ; phase E : the input throughput is reduced to induce 50% of over-provisionig; phase F : the input throughput is increased back to 0%

under-provisioning and we also double the execution duration w(t) for each tuple, simulating a change in the operator resource availability; phase G : same as phase A.

As the graphs show, during phase A the queuing latencies of LAS and Straw-Man diverge: while LAS quickly approaches the performance provided by Full Knowledge, Straw-Man average queuing latencies quickly grow. In the same timespan, both Full Knowledge and LAS drop slightly more tuples than Straw-Man. All the three solutions correctly manage phase B: their average queuing latencies see slight changes, while, correctly, they start to drop larger amounts of tuples to compensate for the increased input throughput. The transition to phase C brings the system back in the initial configuration, while in phase D the change in the tuple frequency distribution is managed very differently by each solution: both Full Knowledge and LAS compensate this change by starting to drop more tuples, but still maintaining the average queuing latency close to the desired threshold τ . Conversely, Straw-Man can't handle such change, and its performance incur a strong deterioration as it drops still the same amount of tuples. In phase E the system is strongly over-provisioned, and, as it was expected, all three solution perform equally well as no tuple needs to be dropped. The transition to phase F is extremely abrupt as the input throughput is brought back to the equivalent of 0% of under-provisioning, but the cost to handle each tuple on the operator is doubled. At the beginning of this phase both Straw-Man and LAS perform bad, with queuing latencies that are largely above τ . However, while the phase unfolds LAS quickly updates its data structures and converges toward the given threshold, while Straw-Man diverges as tuples continue to be enqueued on the operator worsening the bottleneck effect. Bringing back the tuple execution durations to the initial values in phase G has little effect on LAS, while the bottleneck created by Straw-Man cannot be recovered as it continues to drop an insufficient number of tuples.

Prototype

To evaluate the impact of LAS on real applications we implemented it as a bolt within the Apache Storm [START_REF]Apache Storm[END_REF] framework. We have deployed our cluster on Microsoft Azure cloud service, using a Standard Tier A4 VM (4 cores and 7 GB of RAM) for each worker node, each with a single available slot.

The test topology is made of a source (spout) and two operators (bolts) LS and O. The source reads from the dataset and emits the tuples consumed by bolt LS. Bolt LS uses either Straw-Man, LAS or Full Knowledge to perform the load shedding on its outbound data stream consumed by bolt O. Finally operator O implements the logic. Simple Application with Real Dataset -In this test we pretended to run a simple application on a real dataset: for each tweet of the twitter dataset mentioned in Section 5.1 we want to gather some statistics and decorate the outgoing tuples with some additional information. However the statistics and additional informations differ depending on the class the entities mentioned in each tweet belong. We assumed that this leads to a long execution duration for media (e.g., possibly caused by an access to an external DB to gather historical data), an average execution duration for politicians and a fast execution duration for others (e.g., possibly because these tweets are not decorated). We modeled execution durations with 25 milliseconds, 5 milliseconds and 1 millisecond of busy waiting respectively. Each of the 500, 000 tweets may contain more than one mention, leading to wn = 110 different execution duration values from wmin = 1 millisecond to wmax = 152 milliseconds, among which the most frequent (36% of the stream) execution duration is 1 millisecond. The average execution time W is equal to 9.7 millisecond, the threshold τ is set to 32 milliseconds and the under-provisioning is set to 0%. Figure 7 reports the average completion latency as the stream unfolds. As the plot show, LAS provides completion latencies that are extremely close to Full Knowledge, while dropping a similar amount of tuples. Conversely, Straw-Man completion latencies are at least one order of magnitude larger. This is a consequence of the fact that in the given setting Straw-Man does not drop tuples, while Full Knowledge and LAS drop on average a steady amount of tuples ranging from 5% to 10% of the stream. These results confirm the effectiveness of LAS in keeping a close control on queuing latencies (and thus provide more predictable performance) at the cost of dropping a fraction of the input load.

RELATED WORK

Aurora [START_REF] Abadi | Aurora: a new model and architecture for data stream management[END_REF] is the first stream processing system where shedding has been proposed as a technique to deal with bursty input traffic. A large number of works has proposed solutions aimed at reducing the impact of load shedding on the quality of the system output (semantic load shedding), as drop policies are linked to the significance of each tuple with respect to the computation results. Tatbul et al. first introduced in [START_REF] Tatbul | Load shedding in a data stream manager[END_REF] the idea of semantic load shedding. Het et al. in [START_REF] He | On load shedding in complex event processing[END_REF] specialized the problem to the case of complex event processing. Babcock et al. in [START_REF] Babcock | Load shedding for aggregation queries over data streams[END_REF] provided an approach tailored to aggregation queries. Finally, Tatbul et al. in [START_REF] Tatbul | Staying fit: Efficient load shedding techniques for distributed stream processing[END_REF] ported the concept of semantic load shedding in the realm of DSPS. We believe that avoiding an excessive degradation in the performance of the DSPS and in the semantics of the deployed query output are two orthogonal facets of the load shedding problem. To the best of our knowledge, all these works assume that each tuple induces the same load in the system, independently from their content. A different approach has been proposed in [START_REF] Reiss | Data triage: An adaptive architecture for load shedding in TelegraphCQ[END_REF], with a system that build summaries of dropped tuples to later produce approximate evaluations of queries. The idea is that such approximate results may provide users with useful information about the contribution of dropped tuples. A classical control theory approach based on a closed control loop with feedback has been considered in [START_REF] Kalyvianaki | Overload management in data stream processing systems with latency guarantees[END_REF][START_REF] Tu | Load shedding in stream databases: a control-based approach[END_REF][START_REF] Zhang | A novel adaptive load shedding scheme for data stream processing[END_REF]. In all these cases the goal is to reactively feed the stream processing engine system with a bounded tuple rate, without proactively considering how much load these tuples will generate.

CONCLUSIONS

In this paper we introduced Load-Aware Shedding (LAS), a novel solution for load shedding in DSPS. LAS is based on the observation that load on operators depends both on the input rate and on the content of tuplesLAS leverages sketch data structures to efficiently collect at runtime information on the operator load characteristics and then use this information to implement a load shedding policy aimed at maintaining the average queuing latencies close to a given threshold. Through a theoretical analysis, we proved that LAS is an ( , δ)-approximation of the optimal algorithm. Furthermore, tests conducted both on a simulated environment and on a prototype implementation confirm that by taking into account the specific load imposed by each tuple, LAS can provide performance that closely approach a given target, while dropping a limited number of tuples.

r 9 :

 9 .B). This informations is used to synchronize the LS with O and remove the skew between O's cumulated execution duration C and the estimation C at LS. O replies to this request (Figure 1.E) with the difference ∆ = C -C (Listing 3.1 lines 11-13). When the load shedder receives the synchronization reply (Figure 3.C) it updates its estimation C + ∆ (Listing 3.2 lines 11-13). hash functions h 1 , . . . , hr : [n] → [c] from a 2-universal family. function update(tuple : t, execution time : l, request : C)

Figure 2 :

 2 Figure 2: Operator finite state machine.

Figure 3 :

 3 Figure 3: Load shedder LS finite state machine.

Theorem 3 . 3 ( 1 ε

 331 Communication complexity of LAS). The communication complexity of LAS is of O m N messages and O m N log 1 δ (log m + log n) + log m bits.

Figure 3

 3 Figure 3.A and 3.D

Figure 4 :

 4 Figure 4: Average queuing latency Q varying the amount of under-provisioning.

Figure 5 :

 5 Figure 5: LAS performance varying the frequency probability distributions.

Figure 6 :

 6 Figure 6: Simulator time-series.

Figure 7 :

 7 Figure 7: Average completion latency in the prototype use case.

This correction factor derives from the fact that ŵ(t) is a (ε, δ)-approximation of w(t) as shown in Section 4.

ACKNOWLEDGMENT

This work has been partially founded by the French ANR project SocioPlug (ANR-13-INFR-0003) and by the DeSceNt project granted by the Labex CominLabs excellence laboratory (ANR-10-LABX-07-01).


Jérôme Thauvin

Guillaume Barraud

Xavier Roboam

Bruno Sareni

Marc Budinger

Dimitri Leray

Hybrid Propulsion for Regional Aircraft: a Comparative Analysis based on Energy Efficiency

Keywords: hybrid propulsion, gas turbine, energy storage, energy recovering, power management, distributed electric propulsion

This article assesses the potential benefits of transient energy storage for a hybrid regional aircraft. The mission profile of a reference aircraft is analyzed according to energetic intermittence and the results are compared to typical figures for cars, trains, and ships. Also, the opportunity of recovering energy in descent and during landing is studied. This article shows that energy saving potential brought by transient energy storage is much smaller than for ground-based transportation. In addition, energy recovering does not bring benefit on a hybrid aircraft in normal operation. Nevertheless, the best energy management strategies in descent are highlighted and the use of a hybrid propulsion system in this phase shows significant potential energy savings. Finally, the article addresses other strategies enabled by hybrid propulsion to improve the aircraft energy efficiency.

I. INTRODUCTION

Propulsion system innovations have been a key driver of aeronautic evolution. The increase of propulsion performance and efficiency has enabled aircraft to travel at higher speeds over longer ranges while carrying larger payloads. Today the improvement of conventional engine technologies is reaching an asymptote, while future demands on the air transport systems still dictate that aircraft should be less polluting, less noisy and more fuel efficient. In this context, hybrid architectures offer the opportunity to transform in the long term the landscape of aircraft propulsion and furthermore enable new aircraft configurations.

In this article the term hybrid aircraft is used to define an aircraft that operates more than one type of energy source and/or power flow for propulsion means. Aircraft propulsion is indeed currently limited to kerosene and mechanical transmissions. Hybrid electric propulsion provides the opportunity to combine different energy sources or power flows by integrating new technology bricks. Those give additional degrees of freedom to improve overall aircraft performance, limit the use of non-renewable fossil resources and reduce the aircraft environmental footprint.

Today, hybrid technology has mainly been applied to ground-based transports, cars, buses and trains but also ships. However, the feasibility of hybrid architectures in the air industry has to be established and the improvement in aircraft performance has still to be demonstrated. This paper aims to assess the potential benefits of transient energy storage for a hybrid regional aircraft. These opportunities are evaluated with respect to a reference conventional aircraft that was designed for the purpose of this study. At first order, results are independent of the hybrid propulsion architecture due to the methods used.

II. REFERENCE AIRCAFT AND REFERENCE ENGINE

The reference aircraft is a conventional twin-turbo propeller designed with an in-house preliminary aircraft design tool assuming a 2035 technology level. The engine size and the reference area are constrained by the time to climb to 20,000 ft (17 min) and the approach speed (113 kt) requirements. Despite the range capability of 400 nm, the aircraft performance is evaluated on a 200 nm mission (Table I) as this aircraft is expected to operate most of its life on such range. The reference aircraft is fitted with two turbopropeller engines of 3500 thermal horsepower each. Fig. 1 provides the power profile of one engine along the 200 nm mission.

III. TRANSIENT ENERGY STORAGE

A. Energy Sharing

Generally, for hybrid architectures using energy storage devices, the main energy generator provides the average load of the mission while energy storage devices provide peak loads. This allows the main energy generator to be downsized and to be used at a better efficiency. In [START_REF] Turpin | Systemic Design Methodologies for Electrical Energy Systems: Analysis, Synthesis and Management[END_REF], the authors propose two criteria to assess the relevance of a propulsion system to be hybridized with energy storage devices: the potential for hybridization in power and the potential for hybridization in energy. For reasons linked to power density and rarefied air operation, the main energy generator of hybrid aircraft will 978-1-5090-0813-1/16/$31.00 ©2016 IEEE likely remain gas turbine. As the maximum available output power of a gas turbine evolves with speed and altitude, a new definition of the potential for hybridization in power is proposed hereafter. Also, the potential for hybridization in energy is slightly modified for a better characterization of the storage unit.

1) Potential for Hybridization in Power PHP

The potential for hybridization in power PHP defined by (1) expresses the potential reduction in size of the main source of power enabled by the use of an energy storage. This definition assumes that the state of energy of the storage unit at both start and end times of the mission are the same (i.e. the storage unit is recharged to its initial state). This energy management strategy is surely not best suited for aircraft mission profile but is convenient for the purpose of this mission profile comparison. Note that if the maximum available output power P maxNRJgen of the main source of power is independent of time-typically the case for ground-based application-( 1) is strictly identical to the definition in [START_REF] Turpin | Systemic Design Methodologies for Electrical Energy Systems: Analysis, Synthesis and Management[END_REF].

PHP=1-<P mission >/<P maxNRJgen >

(1

)
Where <X> is the mean value of the function X(t) along the mission.

PHP=0 expresses a mission profile that is strictly unsuitable for the reduction of the main energy generator size through hybridization while PHP=1 expresses a mission profile that firmly supports it.

2) Potential for Hybridization in Energy PHE

The potential for hybridization in energy PHE defined by (4) is the ratio of the maximum power delivered or received by the storage unit to the useful energy E u of the storage device during the mission. The useful energy can be determined according to (3) from the evolution of the energy E s (t) in the storage device given by (2). Thus, the PHE is homogenous to a frequency which relates to the inverse of a time constant τ sto that characterizes the storage unit in terms of dynamic performance and can be placed in the Ragone chart accordingly. Based on its definition, it can be stated that the smaller the PHE, the more energy abundant the storage.

E s (t)=  t t0 [P mission (τ)-(1-PHP)P maxNRJgen (τ)]dτ (2) E u =max E s (t)-min E s (t) t∈[t 0; t f ] (3)
PHE=max[P mission (t)-(1-PHP)P maxNRJgen (t)]/E u t∈[t 0; t f ] (4)

3) Mission Profile Analysis and Comparison

The two indicators are now used to characterize the power profile of the reference aircraft shown in the next figure. II). In the case of cars, calculations are based on Common Artemis Driving Cycles assuming a vehicle mass of 1400 kg, a reference area of 2.7 m² (frontal area), a drag coefficient of 0.25 and a 0.028 rolling friction coefficient. Results for trains are based on the study carried out in [START_REF] Akli | Energy management and sizing of a hybrid locomotive[END_REF]. Note that local service refers here to the transportation of freight between two cities that are within 40 km from each other. Mission profiles for ships are taken from [START_REF] Carlton | Marine propellers and propulsion[END_REF] and the power required is calculated assuming a proportional increase with the ship speed to the third power.

The PHPs of regional aircraft and container ship are very low compared to the other applications. This can be explained by the fact that their conventional propulsion systems operate at a relatively high level throughout the mission versus its maximum capability. Therefore the potential reduction in size of the main energy source is small. Obviously, the longer the cruise phase, the smaller the PHP. This emphasizes why a regional aircraft is chosen as a reference aircraft in the paper.

The time constant τ sto of the regional aircraft falls into the battery category. However, the small PHE calculated for the regional aircraft expresses a huge capacity need that might be critical for this application.

B. Energy Recovering

While hybrid vehicles are now entering the market in increasing numbers, their interest is mainly limited to urban driving cycles characterized by its numerous stops and starts. Main savings come from the ability of the hybrid architecture to recover kinetic energy during deceleration. This section analyses potential energy savings of the reference aircraft through energy recovering at landing and during the descent phase.

1) Braking Energy

In order to stop at landing an aircraft dissipates its kinetic energy through several braking systems: disc brakes, airbrakes and thrust reversers. Calculating the maximum kinetic energy at landing of the reference aircraft using the maximum landing weight and the reference approach speed yields to 36 MJ or 0.19% of the total energy consumed during the nominal mission. Assuming a Fuel Lower Heating Value FLHV of 42.8MJ/kg and a gas turbine efficiency of 40%, 36MJ is the energy that can be obtained by burning 2 kg of fuel (to be compared with the total fuel burn of Table I). Also, as the landing phase lasts only few seconds, the energy recovering system should be able to withstand very high power flows leading to a heavy and complex device. Regarding the small portion of energy that can be recovered and the additional complexity brought by an energy recovering system, the potential benefit of braking energy recovering will not be investigated further.

2) Gravitational Potential Energy

With its cruise altitude of 20,000 ft the reference aircraft benefits from a 1183 MJ potential energy at the end of cruise (19,800 kg). That is, 6.3% of the energy consumed over the mission. Hybridization could enable aircraft to convert gravitational potential energy during descent through windmilling propellers, store it in electric batteries, and use it during a later phase. The following study addresses this point and tends to highlight the best energy management in descent.

Let D ac be the drag force applied to the reference aircraft without its propeller blades, but including nacelles and spinners. In constant-speed cruise, the thrust generated by the propulsion system exactly compensates D ac . For the purpose of this study, four different operating modes of the propellers in descent are defined:  Folded: propeller blades are fully folded along or in the nacelles to reduce as far as possible the propeller drag in descent. The aircraft drag penalty associated to this propeller mode is assumed to be zero.

 Feathered: the propeller blades can rotate parallel to the airflow reducing the propeller drag in comparison with uncontrolled windmilling. Still, a feathered propeller generates drag that is taken into consideration by scaling the drag coefficient of [START_REF] Black | Aerodynamic design and performance testing of an advanced 30° swept, eight bladed propeller at mach numbers from 0.2 to 0.85[END_REF] with respect to the propeller diameter and the number of blades. In this propeller mode, both propellers of the reference aircraft are assumed to be feathered, and a drag penalty of 60 drag counts in the aircraft reference area is imparted to D ac .

 Transparency: the propeller is rotating but produces neither drag nor thrust. The small amount of power required to operate this mode is taken into consideration using the propeller efficiency map [START_REF] Thauvin | Hybrid regional aircraft: a comparative review of new potentials enabled by electric power[END_REF] and optimizing the propeller speed as a function of flight conditions to minimize the required amount of shaft power. No drag component is added to D ac .

 Wind turbine: the aircraft recover some energy during the descent. The additional drag is defined proportionally to D ac through the energy recovering coefficient k. The total aircraft drag is therefore "(1+k)D ac ". The shaft power extracted from the windmilling propellers is calculating using the actuator disk theory, hence neglecting friction losses and blade tip losses.

Fig. 2 illustrates the effect of the different propeller modes on the aircraft flight path. The distance covered in folded mode was chosen as the reference distance to destination from cruise altitude. Note that under the assumptions of this study, the transparency mode involves the same flight path as the folded mode. The feathered mode and the wind turbine propeller mode require a steeper descent slope due to the additional drag. As a consequence the distance covered in descent is less than the reference and the cruise flight must be extended to reach the destination. Note that the comparison between propeller operating modes is performed at iso-timeto-descent which explains why the descent speeds are different. Nevertheless, the cruise part is flown at the design speed. This study aims to compare the onboard energy consumption of the aircraft in descent depending on the propeller operating mode and the descent time. In this analysis the following assumptions are considered:  The aircraft weight is supposed to be constant and equal to 19,800 kg during the descent (Table I).

 Five different descent times are considered ranging from 16 min to 5 min.

 The distance covered in folded mode for the 16 min descent time is chosen as the reference range to destination as the descent speed for this case approaches the speed of best lift-to-drag ratio.  For the wind turbine mode, coefficient k was varied from 0.1 to 3.0 with a 0.1 step for each descent time as far as the stall speed was not reached. In the results (Fig. 456) only the case providing the minimum overall energy consumption is depicted.

 The energy consumption of non-propulsive systems is taken into account throughout the range to be covered by assuming a constant power consumption P sys of 140 kW.

 The propeller efficiency for the cruise segment is set to 90%.

To go even further, additional assumptions are made on the efficiency of the power generation system depending on the flight segment.

 If the additional cruise segment is performed with a gas turbine type system its efficiency is set to 40% which applies between the energy source and the propeller shaft but also between the energy source and the non-propulsive systems. For the descent segment, an efficiency of 10% is considered for this type of system to account for the low efficiency of gas turbines in idle [START_REF] Thauvin | Hybrid regional aircraft: a comparative review of new potentials enabled by electric power[END_REF].

 If an electrical power generation system is used in place of the thermal system for the additional cruise and/or the descent a 90% efficiency is considered.

The power flows and possible efficiency combinations are illustrated in Fig. 3. Results of this trade study are depicted on Fig. 456. The onboard energy consumption is represented as a function of gravitational potential energy between cruise altitude and 1500ft (i.e. 1093 MJ).

The energy management strategy of the reference aircraft can be analyzed through the 10 min descent and the transparency mode of Fig. 4. The propeller does not operate in a transparency mode in reality but the average thrust along the descent approaches zero. It can be shown that going to the feather mode would reduce the energy consumption by 20% for the same descent time. Of course this may entail a complex modification of the engine architecture as the mechanical offtakes have to be provided even if the propeller gearbox output shaft is stopped. The hybrid power generation system (Fig. 5) brings significant reduction in overall energy consumption versus the full thermal system due to its high efficiency in descent. Contrary to the full thermal power generation it is better to perform the descent in transparency mode rather that in feather mode: the energy cost for keeping the propellers rotating is much less than the energy required to fly the additional cruise segment when feathered propellers are used. As energy recovering is now assumed possible with this system, it can be noted that the lowest overall energy consumption with the wind turbine mode is performed with a 4% recovery of the gravitational potential energy only. Still, the transparency and folded modes are always more energy efficient than the wind turbine mode for descent time longer than 10 minutes. Note that the descent time is generally constrained by cabin repressurization limits and will likely never be shorter than 7 minutes in normal operation.

For the full electrical power generation system, the overall energy consumption with the wind turbine mode is generally better than the transparency mode as the energy cost for additional cruise is much less than with the previous hybrid system. The recovered energy also participates in lowering this cost even further. Nonetheless, the most efficient case in transparency mode (16 min) to cover the reference distance is still better than the most efficient case in wind turbine mode (16 min also).

This analysis based on efficiency considerations shows that:

 If possible, propellers should be folded during the descent whatever the power generation system.

 The use of a hybrid power generation system could largely help reducing the energy consumption in descent (-60% for 10 min descent time versus full thermal power generation). With the high efficiency of such system in descent, the propeller should be operated in transparency mode rather than being feathered or being used as wind turbines for descent in normal operation.

 Finally, energy recovering through windmilling propellers is definitely not the most energy efficient way to use the gravitational potential energy of the aircraft if there is no constraint on the descent time: the aircraft should descend at the speed of best lift over drag with the propellers folded or operated in transparency mode.

These results are of course to be mitigated with possible weight penalties imparted by new power generation systems, in particular for the full electric system.

IV. OTHER STRATEGIES

If transient energy storage and energy recovering are not promising concepts for a hybrid regional aircraft, other strategies could be implemented to take benefit from the hybrid architecture and to decrease the overall energy consumption.

A. Power Management and Efficiency

Reference [START_REF] Thauvin | Hybrid regional aircraft: a comparative review of new potentials enabled by electric power[END_REF] analyses the power chain efficiency of the reference aircraft along the nominal mission and points out potential energy savings related to the following technologies:  Low propeller rpm in Taxi: the minimum propeller speed of the reference aircraft is limited by the minimum frequency required by non-propulsive systems and other hydraulic power generation equipment connected to the gearbox. Using hybridelectric systems during taxi should enable to release this minimum speed constraint: the propeller efficiency could be increased by 49%.

 Secondary Energy source for Start and Stop: assuming that this start and stop function can be mature and reliable enough, including rapid re-activation of the gas turbine, the descent could be flown with the gas turbines off as already studied in this paper. In the same way, taxi phases could be performed on a full electric mode. The energy consumption in taxi could be decreased by 90%.

 Single Engine Aircraft: using one big gas turbine of twice the power of the reference engine would enable to save 10.5% on the prime mover efficiency at design point. However, having a single turbine in nominal operation requires a back-up system sized to cope with the failure of this turbine.

 Engine downsizing: as the reference engine is sized by the time-to-climb constraint, the cruise power is approximately 14% less than the design power at cruise level. Designing the engines for cruise power would result in a 0.5% penalty on the specific fuel consumption that will be imparted to the block fuel. Nonetheless, economic aspects have to be considered to come to a conclusion.

B. Improved Aerodynamics

Driving wheels, propellers or fans electrically instead of mechanically provides great flexibility as far as locating is concerned. Electrical power is thus a key enabler for distributed propulsion. Reference [START_REF] Thauvin | Hybrid regional aircraft: a comparative review of new potentials enabled by electric power[END_REF] also focuses on aerodynamic improvements for the reference aircraft enabled by new propeller or fan integrations and the associated concepts such as differential thrust, blown wing and boundary layer ingestion.

Fig. 1 .

 1 Fig. 1. Power profile of the reference aircraft Same calculations are performed for typical mission profiles for cars, trains and ships (TableII). In the case of cars, calculations are based on Common Artemis Driving Cycles assuming a vehicle mass of 1400 kg, a reference area of 2.7 m² (frontal area), a drag coefficient of 0.25 and a 0.028 rolling friction coefficient. Results for trains are based on the study carried out in[START_REF] Akli | Energy management and sizing of a hybrid locomotive[END_REF]. Note that local service refers here to the transportation of freight between two cities that are within 40 km from each other. Mission profiles for ships are taken from[START_REF] Carlton | Marine propellers and propulsion[END_REF] and the power required is calculated assuming a proportional increase with the ship speed to the third power.

Fig. 2 .

 2 Fig. 2. Flight path comparison for 10 min descent time

Fig. 4 .

 4 Fig. 4. Comparison of onboard energy consumption for full thermal power generation system -Cruise: Thermal/Descent: Thermal

Fig. 3 .

 3 Fig. 3. Possible power flows for cruise segment (left) and descent (right)

Fig. 5 .

 5 Fig. 5. Comparison of onboard energy consumption for hybrid power generation system -Cruise: Thermal/Descent: Electric

TABLE II .

 II

						MISSION PROFILE COMPARISON
			Car			Train [2]	Ship [3]	Aircraft
		Urban	Rural road	Motorway (150km/h)	Local service	Switching	Urban transportation	Container	Ro/Ro passenger ferry	Regional (200 nm)
	PHP (%)	94	85	74	65	83	91	43	63	32
	PHE (mHz)	66	30	12	3	29	20	n/a	n/a	0.22
	τ sto	15 s	34 s	1.4 min	5.8 min	35 s	50 s	n/a	n/a	77 min

TABLE I .

 I MISSION OVERVIEW