Marc Ivaldi

Estelle Malavolti-Grimal

TV on Mobility: a Two-Sided Market Analysis

TV on mobility : a two-sided market analysis

Introduction

The opportunity to watch TV on a mobile phone is taking more and more importance as mobile operators are investing in new technologies allowing a better quality of the broadcasting. According to US consultants of Visiongain, 270 Millions of new subscribers, which represents 10% of the mobile users, are expected by 2009. This paper analyzes how the market of the TV on mobile phone works. We model this market as a two-sided market, where the customers from one side of the market, wants to watch TV on their mobile, and, TV producers/advertisers, on the other side of the market, want to advertise on a new media. Customers and advertisers are not directly related:

The mobile operator plays the role of a platform connecting the two sides of the market.

With respect to the classical TV market (TV at home), this market is larger: Customers can consume TV on their mobile while in mobility. This feature translates in concrete terms to the fact that consumers are willing to pay more to receive the TV on their mobile.

It means as well that the advertisers are willing to pay more to acquire advertising space because the audience is larger. From now on, we will use indifferently "mobile TV" for TV on mobility and TV on mobile phone. There are externalities on the mobile TV market: Customers want to consume broadcasts and not advertisements, whereas broadcasts are made because of the revenues coming from advertising. The mobile operator trades off the two sources of profits: Increasing the space for advertising increases the profit made on the market of advertisers. However there exists a side effect on the other side of the market as customers incur a disutility of watching advertising and decrease consequently their 1 demand for mobile TV, which, in turn, decreases the profit made on TV broadcasting. In our model, the mobile operator is a monopolist. The mobile TV market is an emerging market and mobile operators introduce the possibility to watch TV firstly to their own consumers of mobile phone. They are thus considered to be in a dominant position on this part of the demand.

We show in this paper that a wise mobile operator, i.e. an operator which is aware of the two-sidedness of the mobile TV market, leads to a higher social welfare than a myopic monopolist. The wise monopolist generally produces closer to the social optimum.

We also show that the wise monopolist uses two-part tariffs on both side of the market, to reach higher profits. The wise monopolist broadcasts less advertising and less TV on mobile than a myopic monopolist when the markets are really linked up. It broadcasts less advertising and more TV when the externality of advertising is high. We then show that the wise monopolist always sets a lower price of one minute of TV broadcasted while generally the price paid by advertisers is higher than the myopic monopolist : Because of the existence of the externality, the advertisers bear part of its cost to compensate the consumers.

The literature on two-sided markets is becoming more and more important with a certain number of seminal papers. We use a classical framework as presented in Rochet and Tirole [2004] with usage externalities on both sides of the market as advertisers demand depend on audience and demand for TV depends on advertising. To the difference to [START_REF] Rochet | Platform Competition in Two-Sided Markets[END_REF] or [START_REF] Armstrong | Competition in Two-Sided Markets[END_REF], we do not model competition between platforms in this paper, as consumers are considered to be captive, but fully model the consumers side as in Crampes et alii [2004], adding however one supplementary ingredient:

TV can be consumed while in mobility. This modifies the utility of consumers and the equilibrium prices the mobile operator sets. Besides we use two-part tariffs which allows us to derive interesting results in terms of welfare. The welfare analysis gives results which are close to those found by [START_REF] Anderson | Market provision of Public goods: The case of broadcasting[END_REF] in another context, in which two-part tariffs are absent and TV broadcasting is considered as a public good.

The paper is organized as follows: The second Section presents the model and the different assumptions. The equilibrium of the market is presented in Section 3. A comparison with a benchmark situation, in which the mobile operator is myopic, i.e. when it does not consider the two sides of the market while taking its decisions, is proposed in Subsection 3.3. In Section 4, we propose a normative analysis of the problem. The optimal solutions are then compared with the equilibrium derived in Section 3. Section 5 concludes.

A Two-sided Market Model

Market Characteristics

Mobile operators

The market is a two-sided market in which mobile operators are platforms linking the two markets of advertising and TV consumption, i.e. advertisers and final consumers.

The market is larger than the market of classical TV (TV at home) in the sense that people can consume while in mobility. Consumers are indeed able to watch TV out of their home, when commuting to their working places. Potentially, the frequency of watching TV is thus higher, creating new prospects for advertisers. Consider a situation in which the mobile operator is a monopolist. This assumption avoids modeling the competition between operators to increase their demand for mobile services via the offer of a new service, i.e., TV on their mobile. In other words, the addressed demand for phone services is captive and the fact that consumers could not switch from one operator to another in response to changes in the features of competitors' offer of mobile TV should not affect our result.

The monopolist has to set together the price of advertising and the price of mobile TV.

The prices are two-part tariffs: consumers (resp. advertisers) pay a certain fee for accessing TV to the TV on their mobile (resp. for being able to advertise on mobile phone) and pay as well a price per each minute of TV watched (resp. per each minute of advertising broadcasted). The monopolist chooses this system of prices in order to maximize its profit subject to the following constraints. Firstly, customers (resp. advertisers) are willing to pay the access to the TV on mobile service (resp. to the space on the mobile). This defines the individual rationality constraints. Second, the monopolist faces the demands of each sides of the market: one for advertisers and one for customers.

We denote by (p, T ) the tariff offered to consumers, where T is the fixed part of the tariff, corresponding to the access cost to the TV service, p corresponds to the variable part of the tariff and is defined as a price per minute of TV watched on the mobile. Equally, (r, A) stands for the tariff offered to advertisers, where A is an access fee and r is the price per minute of advertisement broadcasted.

Assume that it costs c per minute of mobile TV consumed and d per minute of advertisement broadcasted. Fixed costs are denoted C A and C N and stand respectively for the fixed cost related to the advertising activity and the broadcasting activity.

TV Producers

The TV producers (and/or advertisers) build up TV broadcasts and advertisements. These packages are supplied to TV mobile operators. The broadcasts are largely subsidized by the advertisements. That is the main reason why we restrict our attention to the market of advertisers.

Advertisers profits are composed of two parts: the first part is the profit generated by the advertising activity. It is composed of the gains coming from advertising minus the costs to produce advertisements. This profit is increasing in the audience: the more the audience, the higher the impact of advertising. The second part of the profits is the costs to broadcast the advertisements to the mobile TV watchers. Advertisers pay an access price A and a price per minute of advertising broadcasted r. The profit is thus equal to Π(a; n) = π(a; n) -Ara, where π(a; n) is increasing and concave. This part of the profit represents together the gains from advertising, and the cost to produce advertisements. Demand for advertising space a D is thus defined by the following equation:

r = δπ(a; n) δa .
The advertising space demand is increasing with the audience n, i.e. the price per minute of advertisement broadcasted r is higher, the higher the audience.

Customers

Customers derive a satisfaction U of the consumption of a composite good z and of watching n minutes of TV on their mobile. Assume that the utility function is separable in the two arguments. Besides, customers incur a disutility because of the presence of advertisements in the TV programs they watch. This disutility is assumed to be proportional to the amount of advertising broadcasted. The existence of this negative externality links the two markets of the customers and of the advertisers, as the audience. The utility writes:

U (z, n) = αz + u(n; m) -λa,
where α and λ are positive parameters and u(.) is strictly increasing and concave in the audience. Parameter m, stands for the possibility to consume the good "TV" more often than the composite good z (to take into account the positive impact of mobility on consumption). As a consequence, the more m, the higher the utility for a given quantity of mobile TV consumed and the higher the marginal utility derived for the consumption of one more unit of TV.

Customers have an exogenous income I affected to the consumption of the two goods.

Without loss of generality, the price of good z is set to 1. The customers pay an access fee T to receive television on their mobile and a price p per minute of TV watched. The budget constraint can thus be written as follows:

I ≥ pn + z + T .
The demand for TV, denoted n D is obtained by saturating the budget constraint and eluding z. The inverse demand function is then

αp(n) = u ′ (n; m) 1 .
Because of the possibility to consume TV while in mobility, the price of one minute of TV, p, is higher than in the case of classical TV. The price is increasing in the marginal utility for TV but decreases with the quantity of TV consumed.

Besides, we assume that customers have a strictly positive reservation utility, corresponding to the utility of the income αI. We denote V (n) the indirect utility function, which writes:

V (n) = α(I -pn -T ) + u(n; m) -λa.
3 Equilibrium of the Market Let us first analyze the situation of an operator which does not take into account the link between the two markets. The monopolist sets the prices r and A to maximize its profit on the advertising market and, independently, p and T to maximize its profit on the final market.

On the market for advertising, the program of the monopolist is the following:

M ax {r,A} Π = ra +A -da s.t. π(a; n) -A -ra π a , r = δπ(a;n) δa .
The participation constraint just says that the advertisers make no loss when not posting any advertisement. π a represents the reservation profit for advertisers. Then, the monopolist sets the fixed part of the tariff A in order to saturate this constraint. When replacing in the operator profit, the first order condition gives:

δπ(a; n) δa = d.
Price r is thus set to cover the marginal cost of broadcasting advertisements on a mobile phone. The myopic monopolist makes all its profit using the fixed part of the tariff.

But, the myopic monopolist takes as given the level of audience n when optimizing its profits. It thus leads to an underestimation of the price advertisers are willing to pay.

The choice of prices p and T is similar to the choice of the advertising tariff: The monopolist sets up the prices to maximize the profit from broadcasting TV on mobile phones, taking as given the amount of advertisements. The program is thus:

M ax {p,T } Π = pn +T -cn -C N s.t. V (n) αI, p = u ′ (n;m) α .
The participation constraint is saturated: The monopolist extracts as much as possible from the customers, provided that they want to consume TV on their mobile phone. The monopolist takes as given the amount of advertisements broadcasted while optimizing its profit on this side of the market. This leads to an overestimation of the demand for TV.

V (n) = αI ⇐⇒ T = u(n;m) α -pn -λ α a
Replacing T and p as their expression as a function of n and solving for n yields the solution. The first order condition gives

u ′ (n;m) α -c = 0.
It means that the monopolist sets the price of one minute of TV, p, exactly at the marginal cost, c, of broadcasting one minute of TV on the mobile.

When the marginal utility of income α is higher, the monopolist prices a lower fee T M .

As the price p M equals the marginal production cost c at equilibrium, the higher c, the lower the subscription fee. On the contrary, the higher the opportunity to consume TV while in mobility, the higher the ability for customers to pay the fee.

At the equilibrium, customers utility derived from the consumption of TV is just equal to zero. Indeed the fixed transfer T M takes all the surplus from customers. The firm makes exactly T M -C N profits as the price p M equals marginal production cost c.

We thus have to check that the mobile operator recoups at least its fixed cost C N by ensuring

T M ≥ 0.
This constraint is easier to fulfill the higher the satisfaction. Given a certain set of parameters, the mobile operator may then find it not profitable to provide customers with TV, because it does not take into account the interaction between the two sides of the market.

A Wise Monopolist (W)

A well-advised operator is aware of the existence of the negative externality advertisements exert on customers as well as the impact of audience on advertising space demand.

The monopolist will trade off the profits made on each side of the market: If the price of advertising space decreases, everything equals, demand for advertising increases and potentially profits from the advertising activity for the monopolist. However, demand for TV decreases and the monopolist makes less profits on this side of the market.

The program of maximization is thus:

M ax {p,r,A,T } Π = ra +A +pn +T -cn -da -C N -C A s.t. V (n) αI π(a; n) π a δπ(a;n) δa = r u ′ (n;m) α = p
The demand for TV on mobile is determined by utility maximizing, customers taken the prices, p and T , as given. The wise monopolist now knows that there is a negative externality exerted by the advertisements: The higher the demand for TV, the higher the demand for advertisements but the lower the utility, everything equals. Taking into account the externality of advertising, the demand for TV n D is then solution of:

p = u ′ (n; m) α - λ α δa D δn ,
where a D is the demand from advertisers.

The price of one minute of advertising is increasing in the mobility parameter: The higher the valuation of the capacity to consume while in mobility or the time spent in mobility, the higher the price customers are ready to pay for one minute of advertising.

The price is also increasing with the marginal utility brought by the consumption of TV.

However, the existence of an externality decreases the price that can be imposed for one minute of TV. To reach the same level of demand for TV, the wise monopolist has to price lower. The demand for TV is, at equilibrium, lower than the demand in the myopic situation since the necessary condition evaluated at the myopic solution is negative.

The demand for advertising space is determined by the first order condition of the advertisers program, but taking into account the effect of the advertising on the audience:

r(a, n) = δπ(a, n) δa + δπ(a, n) δn δn D δa ,
where n D is the demand for mobile TV.

The monopolist will anticipate both the positive externality of the audience on advertising demand and the negative externality exerted by the advertisements on the audience.

To reach the same demand as the myopic monopolist, it has to price lower.

Let us now solve the program. The participation constraints are both binding because the mobile operator profit is increasing in transfers T and A. The monopolist thus wants to increase them while making sure both customers and advertisers participate to the market.

   A W = π(a; n) -π a -r(a, n)a T W = u(n;m) α -p(n, a)n -λ α a Substituting these values into the profit function yields Π = π(a; n) -π a + u(n; m) α - λ α a.
The first order conditions associated with the maximization with respect to a and n

are    δΠ δa = 0 ⇔ δπ(a,n) δa -λ α -d = 0 δΠ δn = 0 ⇔ δπ(a,n) δn + u ′ (n;m) α -c = 0
Recall that at equilibrium, the myopic monopolist sets the price of one minute of TV at the efficient level, i.e., the marginal cost of production. Here, the existence of a negative externality created by advertising decreases the price chosen by the wise monopolist at equilibrium. Everything happens as if the wise monopolist is pooling the cost to provide the TV on mobile between the customers and advertisers. The existence of the externality makes the wise monopolist to set a lower price to customers. This is reinforced by the positive impact of the audience on the demand for advertising space: the advertisers are more willing to pay to have access to space of advertisements if there is a higher audience, which is possible if the price of one minute of TV is lower. The number of minutes of TV watched at equilibrium is not clearly higher because decreasing the price increases the quantity of TV watched, which ceteris paribus increases the demand for advertising space, which in turn decreases the demand for watching TV.

Let us now specify both the utility function and the profit of advertisers to realize numerical simulations. Suppose that u(n; m) = ln(n) + αmn, increasing and concave and π(a, n) = κnaa 2 2 + π a , with κ > 0 representing the impact of the externality of the audience on the advertising profits.

The relevant parameters to take into account the links between the two sides of the market are thus λ, which stands for the negative impact of advertising on mobile TV consumption and κ which measures the positive impact of audience on the advertising demand.

Results are summarized in the following proposition:

Proposition 1 The well-advised monopolist uses two-part tariffs such that fees are used to set up the advertisers and customers to their reservation profit and utility.

The equilibrium level of consumption of TV and of advertising space are, for d 2 α < 1

and λ < λ, κ ≤ κ ≤ κ:    n W = 1 2ακ 2 (α(c -m) +κ(λ + dα) --4ακ 2 + (α(c -m) + κ(λ + dα) 2 ) a W = 1 2ακ (α(c -m) -κ(λ + dα) --4ακ 2 + (α(c -m) + κ(λ + dα)) 2 ), where λ = √ α -dα, κ = (c -m)(λ + dα), κ = (c-m)α 2 √ α-(λ+dα) .
Proof.

See in appendix.

Both existence and positiveness conditions reflect the trade-off faced by the monopolist: if the externality of advertising is really too high, the monopolist cannot ensure the provision of the market because it would mean negative provision of advertisements. This goes together with a not too low positive externality of audience on the advertising side of the market in order to compensate the negative externality of advertisement.

Making some comparative statics on the equilibrium solution lead us to the following conclusions: both the consumption of TV and the consumption of advertising space are reacting in the same direction with λ and α. Things are more complicated with parameter κ. For instance, the number of minutes of TV broadcasted and the number of minutes of advertisements are decreasing in parameter λ. The higher the externality of advertising, the lower the consumption of TV and advertising space. The externality thus plays a negative role on the equilibrium values of consumption. The first effect of the externality seems to dominate: When λ increases, the demand for TV decreases, ceteris paribus, leading to a decrease of the demand for advertising space (through the parameter κ).

However, as the demand for advertising space decreases, the demand for TV increases because the externality is less important. Now the demand for advertising then increases.

Hence the first effect should dominate at last.

The number of minutes of TV broadcasted is decreasing in parameter α, i.e., the consumption of TV is decreasing with the marginal utility of income. The richer the customers, i.e., the lower parameter α, the higher the consumption of TV. The consumption of advertising space is equally decreasing in α. Richer customers are potentially more likely to address a strong demand for TV, which in turn has a positive impact through the audience on the advertising space demand.

The impact of parameter κ is positive on both advertisements and TV broadcasted.

Indeed the demand for advertising space is increasing with the audience through parameter κ. Thus as κ increases, the equilibrium value of advertisements increases. The number of minutes of TV is increasing with the impact of audience on advertising demand for low values of κ, and then decreasing. When the advertising space demand is really sensitive to the audience, then the potential increase in the demand makes the demand for TV decreasing. Thus when κ is high, n W decreases with κ. On the contrary, when the impact of the audience on advertising demand is low, one need to increase much the number of minutes of TV broadcasted to be of interest for the other side of the market. Thus when κ is low, n W increases with κ.

Comparison myopic/wise monopolist

To analyze the solutions, we set the marginal utility of income to be equal to unity, i.e. α = 1. Results are not qualitatively changed for different strictly positive and bounded values of α. The constraints of existence impose

2(2κ -1) κ ≤ λ ≤ 2κ Proposition 2
The number of minutes of TV broadcasted at equilibrium is higher in the wise monopolist case when both the externality of advertising and the sensitivity of advertising space demand to audience are low. The number of minutes of advertising in the wise monopolist case is generally lower except when the sensitivity to audience is low so as the externality of advertising.

n W > n M if and only if κ > 1 a W > a M if and only if κ < √ 5-1 2 for λ ≤ 2κ 3 1-κ 2
Proof.

See in appendix.

Results are illustrated in Figure 1. to high values of both the externality of advertising and the sensitivity of advertising to audience. In this case, the wise monopolist broadcasts both less minutes of TV on mobile and less advertisements than the myopic monopolist. A high λ and a high κ means that the myopic monopolist has largely underestimated the two-sided aspect of the market.

There is a strong effect of advertising on the demand for TV on mobile and a strong effect of the audience on the demand for advertising space. When λ is high, the demand for TV on mobile is lower in the wise monopolist case. As a consequence, demand for advertising is reduced because κ is high. The induced effect is an increase in the demand for TV on mobile, and in turn an increase of the advertising space demand. Finally, it seems that the first order effect measured by the fact that the myopic monopolist underestimates the links between the two sides of the market dominates for λ and κ sufficiently high.

When the demand for advertising space is less to sensitive to audience, the wise monopolist can provide more demand for TV on mobile. When κ is low, the number of minutes of TV broadcasted is higher than in the myopic monopolist situation. However the number of minutes of advertising depends on the externality of advertising: When the externality is high, the number of minutes of advertising is lower in the case of the wise monopolist. This reflects the fact that the wise monopolist takes into account the impact of the externality on the demand for TV.

Proposition 3

The price of one minute of TV broadcasted on mobile is always lower in the case of the wise monopolist. The price of one minute of advertising on mobile is generally higher except when the sensitivity of the advertising demand to audience becomes high, while the impact of advertising externality is not too important.

p W < p M
for all κ > 0 and λ > 0

r W > r M if and only if λ > -1+3κ 2 + √ κ 4 -6κ 2 +1 2κ for κ ≥ 3 + √ 8
Proof.

See in appendix.

Results are illustrated Figure 2.

The price set by the wise monopolist is always lower than the marginal cost to broadcast one minute of TV on mobile. This is possible and profitable because the monopolist consider simultaneously the two sides of the market: The cost is compensated with the revenues both raised from customers and advertisers. The price paid by customers of the wise monopolist is lower than the one of the myopic monopolist because of the existence of the externality which advertisements exert on customers. This externality has to be taken into account by the one who produce the externality, i.e., the advertisers. The price of one minute of TV is lower to attract more customers, even if, as shown in proposition 2, it may not be sufficient, especially when both κ and λ are high, i.e. when both the externality of advertising and the sensitivity of advertising space demand are important.

The price paid by advertisers is higher in the case of a wise monopolist when both κ and λ are not too high. When the sensitivity of the advertising demand to audience is not too high, the advertisers are sanctioned for the externality they cause on customers.

Indeed when κ and λ are small, it is more profitable for the wise monopolist to increase the number of minutes of TV broadcasted. Thus p W < p M leading to a higher n W . However, because of the existence of κ, the audience being higher, the demand for advertising space will be higher. The wise monopolist will increase the price paid by advertisers to limit the increase of advertisements at equilibrium.

When κ becomes higher, it is only when λ is high enough that the wise monopolist sets a higher price of one minute of advertising to limit the increase of the advertising space demand. When the sensitivity to the audience increases, while the externality of advertising is not too high, it becomes profitable to lower the price of one minute of advertising in order to maintain a sufficient demand of advertising space (even if at equilibrium, the number of minutes of advertising is lower with a wise monopolist).

Normative Analysis

One interesting question is whether to know what would have proposed a benevolent planner, knowing the characteristics of the market. Indeed a benevolent agent internalizes both the negative externality of the advertising and the impact of the audience on advertising space demand, as a wise monopolist. However the objective function of a benevolent is to maximize the sum of consumer surplus and profits of the advertisers and of the mobile operator.

A benevolent planner will choose the amount of advertisements such that the social cost of advertising, i.e., the impact of the externality on customers utility λ, equals the social benefits, i.e., the marginal profit made by the advertisers. The benevolent agent chooses the amount of TV broadcasted in order to equalize the marginal cost of production to the marginal utility of customers plus the marginal profit realized by advertisers through the increase of audience.

The use of the two-part tariffs lead us to make an important remark: the wise monopolist achieves a higher level of Social Welfare than the myopic monopolist. This is due to the fact that the fixed part of the two-part tariffs are used by both monopolists to set the customers and the advertisers down to their reservation utility and profit. The wise monopolist, which knows both the impact of the advertising on audience and the impact of audience on advertising, i.e. which knows more than the myopic monopolist, achieves a higher profit than the myopic monopolist. Thus the Social Welfare is higher in the case of a wise monopolist. These arguments are independent of the shape of the utility function or of the different values of the parameters. It holds because of the structure of the prices, i.e. the two-part tariffs. This result is summed up in the following proposition.

Proposition 4 The wise monopolist achieves a higher social welfare than the myopic monopolist.

Proof.

See in appendix.

Another interesting question is whether to know if the wise and the myopic monopolist rations or not the broadcasting of TV so as the advertising on mobile. In order to explicit the solutions, we make the same assumptions for the analysis of the wise and myopic monopolists.

The Social Welfare is composed of the utility of the customers plus the benefits from advertisers reduced by the total costs to produce the advertisements and to broadcast TV on mobile. We do not have modeled till now the market of the advertisers, by considering only the demand for advertising space. Nonetheless it is easy to reconstitute the profit of the advertisers from the simple assumption on the form of the demand. Demand is

a D = -δr + κn
This demand can be issued from the maximization of the following profit function (defined up to a constant):

π a = κna δ + π a revenues - a 2 2δ cost to produce a - ra cost to broadcast a
Then the social welfare is equal to

SW = αI + u(n) + αmn -λa + π a + κna δ -cn -C - a 2 2δ
The social planner chooses the quantities of TV and advertisements to broadcast in order to maximize the social welfare. The first order conditions on a and n then write:

   δSW δa = 0 ⇔ -λ + κn δ -a δ = 0 δSW δn = 0 ⇔ u ′ (n) + αm -c + κa δ = 0
The quantity of advertisements to broadcast is such that the marginal social benefit, i.e., the marginal gain of the advertisers linked to the audience κn δ , equals the marginal social cost, including the cost to produce advertisements a, i.e., a δ and the cost of the externality of advertising λ.

The quantity of TV broadcasted is defined in the same way: the social benefits composed of the marginal utility of customers u ′ (n) + αm and of the gain of profit of the advertisers κa δ equals the cost to broadcast one minute of TV on mobile c. The following proposition gives explicit forms for the optimal number of minutes of TV and advertisements.

Proposition 5 The social planner chooses the following quantities of TV and advertisements, defined for λ ≥ 2

√ 2κ-1 κ    n * = κλ+1- √ (1+κλ) 2 -8κ 2 4κ 2 a * = -κλ+1- √ (1+κλ) 2 -8κ 2 4κ
Both the wise and the myopic monopolist oversupply the broadcasting of TV when both the sensitivity to the audience and the externality of advertising are high. When this sensitivity is small, the wise monopolist undersupplies less the broadcasting of TV than the myopic monopolist:

         For κ ≥ 1 n M ≥ n W > n * For 2+ √ 2 4 ≤ κ < 1 n W > n M ≥ n * For κ < 2+ √ 2 4 n * > n W > n M Proof.

See in appendix.

Results are illustrated in Figure 3.

When the sensitivity of the advertising demand to audience is high as well as the externality of advertisements, i.e. when the market is clearly two-sided, the social planner broadcasts less TV than the wise monopolist, which broadcasts less TV than the myopic monopolist.

When there is a low interaction between the two sides of the market, i.e. when both κ and λ are low, the optimal level of TV broadcasted is higher. The wise monopolist is again closer to the optimal solution.

Finally, for intermediate levels of κ and λ, there is overproduction of TV. The wise monopolist is the one which produces the more. In the following proposition, we compare the levels of advertisements proposed.

Proposition 6 Both the wise and the myopic monopolists oversupply advertisements when the sensitivity to audience and the externality of advertising are high. Generally the myopic monopolist oversupplies more and more often than the wise monopolist:

                     For κ > 2+ √ 2 4 a M ≥ a W > a * For √ 6- √ 2 2 < κ < 2+ √ 2 4 a M > a * > a W For κ ≤ √ 6- √ 2 2 and λ < 2κ 3 1-κ 2 a * > a W > a M κ(1+κ 2 ) 1-κ 2 < λ < 2κ 3 1-κ 2 a * > a M > a W λ > κ(1+κ 2 ) 1-κ 2 a M > a * > a W Proof.

See in appendix.

Results are illustrated in Figure 4. When the interaction between the two sides of the market is very important, there is overbroacasting of advertisements by the two structures, wise and myopic monopolist.

When the interaction is less important, the level of the externality of advertising is important: when the externality is low, the social planner proposes more advertisements than both the wise and the myopic monopolist. When λ is very low, the wise monopolist is closer to the optimal solution. On the contrary for an intermediate value of λ, the myopic monopolist is closer. When the externality becomes higher, the myopic monopolist overproduces advertisements, while the wise monopolist underproduces.

Conclusion

Considering the mobile TV market as a two-sided market improves the profits of the mobile operator as well as the economic welfare of the Society. This result holds for different specification of demand or utility functions and relies on the use of two-part tariff to implement the equilibrium. One natural extension of the model is to consider competition among the mobile operators. Results should be a convergence to the social optimum.

A Proof of proposition 1: Existence and positiveness of the solutions A.1 Existence

The solutions of the program for the wise monopolist exist provided that

(κ(λ + dα) + (c -m)α) 2 -4ακ 2 ≥ 0.
This expression has the same sign as

κ(λ + dα) + (c -m)α) -2 √ ακ,
since by definition α ≥ 0 and (cm) ≥ 0.2

• If λ ≥ λ ≡ 2 √ αdα, then there is no other constraint on κ needed to ensure existence of the solutions.

• If λ < λ, then one needs

κ ≤ κ(λ) ≡ (c -m)α 2 √ α -(λ + dα) ,
where κ(λ) is increasing in λ at an increasing rate.

Besides, the second order conditions state

n W ≤ 1 κ 2 α .

A.2 Positiveness

When a W and n W exist, one have to check there positiveness. There is no ambiguity for n W , while there are conditions on the parameters to ensure a W is positive.

a W ≥ 0 is equivalent to α(c -m) -κ(λ + dα) --4ακ 2 + (α(c -m) + κ(λ + dα)) 2 ≥ 0.
One necessary condition for this condition to hold is to ensure that κ is not too high:

α(c -m) -κ(λ + dα) ≥ 0, which is equivalent to κ ≤ κ(λ) ≡ (c -m)α λ + dα ,
where κ(λ) is decreasing with λ at an increasing rate.

Then, a W ≥ 0 if

κ ≥ κ(λ) ≡ (c -m)(λ + dα),
where κ(λ) is increasing with λ.

The compatibility of the two last conditions is ensured for a certain level of parameter λ:

κ(λ) ≤ κ(λ),
only for λ such that

λ 2 + 2dαλ + d 2 α 2 -α ≤ 0.
The relevant solution for this second order equation is

λ = √ α -dα,
which we need to be positive, implying

d 2 α < 1.
The compatibility is then ensured for λ ≤ λ.

A.3 Compatibility between existence and positiveness

Notice that λ < λ, which means that existence imposes a third constraint on κ.

Notice as well that

κ( λ) = κ( λ) = κ( λ) = (c -m) √ α.
Thus, as κ(.) is increasing and κ(.) is decreasing, it is immediate that for the range of acceptable parameter λ ≤ λ:

• κ(λ) > κ(λ)

• κ(λ) > κ(λ).

Notice then that κ(0) = (cm)dα and that κ(0)

= (c-m)α 2 √ α-dα . Then κ(0) ≤ κ(0)
if and only if

-αd 2 + 2 √ αd -1 ≤ 0
which is always true for d > 0 and α > 0. Thus κ(0) < κ(0), which means, as κ(.) is linear and κ(.) is increasing that κ(.) ≤ κ(.).

As a conclusion, solutions a W and n W exist only if

   λ ≤ λ κ ≤ κ ≤ κ.

B Proof of Proposition 2

First constraint is the existence of both n W and a W which simplifies to λ > 2(2κ -1) κ for α = 1. Second constraint is to be sure that the equilibrium does give positive solutions. There is no problem with the number of minutes of TV broadcasted, however the equilibrium advertising space is positive only if λ ≤ 2κ after simplifications. The solution of the myopic problem is

n M = 1
and the wise monopolist solution simplifies to

n W = 2 + κλ - √ -16κ 2 + 4 + 4κλ + κ 2 λ 2 4κ 2
The computation of the difference n Wn M leads to the following condition:

n W > n M if and only if λ < 2 κ
Adding the existence conditions, the comparison leads to the following condition:

n W > n M if and only if κ < 1
The computation to the difference a Wa M leads to the following expression

1 4κ (1 - κλ 2 -2κ 2 -(1 + κλ 2 ) 2 -4κ 2 )
which is positive only if

λ(-1 + κ 2 ) ≥ 2κ 3
Thus this condition is never satisfied for κ > 1, in this case a W < a M . For κ ≤ 1, we have then

a W ≥ a M if and only if λ ≤ 2κ 3 1-κ 2 with κ < √ 5-1 2

C Proof of Proposition 3

Firstly, the constraints on existence and positivity of the solutions have to be taken into account. For this reason, λ > 2(2κ -1) κ for α = 1 and λ ≤ 2κ

. The equilibrium price in the case of a myopic monopolist is just the marginal cost to broadcast one minute of TV on the mobile. After computations, the equilibrium price in the case of the wise monopolist is

p W = m -κλ + 2κ 2 1 + κλ 2 -(1 + κλ 2 ) 2 -4κ 2
for α = 1 and δ = 1 2 . The computation of the difference of the two prices leads to the following expression, after assuming cm = 1,

p W -p M = -1 -κλ + 2κ 2 1 + κλ 2 -(1 + κλ 2 ) 2 -4κ 2
This expression is equal to zero for the unique solution

κ = - λ 2 + λ 2
, which is negative. The derivative of the difference between the two prices is strictly negative. Thus the difference of prices is positive before κ and negative after. As we only care about positive values for parameter κ and λ, we can say that the difference p Wp M is unambiguously negative for κ > 0 and λ > 0.

The equilibrium price of one minute of advertising is equal to r M = κ in the case of a myopic monopolist, while it is equal to r

W = 1+ 3 2 κλ- q (1+ κλ 2 ) 2 -4κ 2 2κ
in the wise monopolist situation. The analysis of the difference leads to the following condition:

λ > λ is equivalent to r W > r M Where λ = -1 + 3κ 2 + √ κ 4 -6κ 2 + 1 2κ
and when λ is defined, i.e. for κ ≥ 3 + √ 8.

D Proof of Proposition 4

The myopic monopolist uses the fixed part of the two-part tariffs to set both the advertisers and the customers to their reservation utility/profit. Thus the social welfare at the equilibrium is equal to

SW M = αI + π a + Π M
The wise monopolist chooses the fees exactly in the same purpose. Thus the social welfare achieved is thus:

SW W = αI + π a + Π W
The profit of the wise monopolist is higher than the one of the myopic monopolist because the wise monopolist, as shown in section 3, does differently from the myopic monopolist. This means that even if the wise monopolist could replicate what the myopic monopolist did and thus reach the same level of profit, it is not optimal to do so. As Π M ≤ Π W , then

SW M ≤ SW W .

E Proof of Proposition 5

The social planner chooses the quantities of TV and advertisements to broadcast in order to maximize the social welfare which is equal to

SW = αI + u(n) + αmn -λa + π a + κna δ -cn -C - a 2 2δ
The first order conditions on a and n write: The two solutions are always positive, however they are defined only for

λ ≥ 2 √ 2κ -1 κ
Computing the difference n * -n W leads to the following expression:

n * -n W = 1 4κ 2 (-1 -(1 + κλ) 2 -8κ 2 + (1 + κλ 2 ) 2 -4κ 2 )
Let us denote ∆ = (1 + κλ) 2 -8κ 2 and ∆ = (1 + κλ 2 ) 2 -4κ 2 . The difference is positive only if

(-1 - √ ∆ + ∆) ≥ 0
We show that this is possible for κ ≤ 2+ √ 2 4 , when λ ≤ 2κ, which corresponds to the definition of a W ≥ 0. Moreover, for κ > 1, the difference is always negative, i.e. n W > n * .

As we already shown that for κ > 1, n M > n W , hence, n M > n W > n * .

For κ ≤ 1, we have to compute (n * -n M ), which writes:

κλ + 1 -4κ 2 - √ ∆ 4κ 2
It is positive when the following condition is satisfied, for κ ≤ 2+

F Proof of Proposition 6

Using the same notations as for the proof of proposition 5, the computation of the difference a * -a W leads to the following expression For κ < 1, we have to compute a * -a M , which writes:

1 4κ (- κλ 2 - √ ∆ + ∆)
which is positive only if λ ≤ κ(1+κ 2 ) 1-κ 2 . Besides, we know that for λ < 2κ 3 1-κ 2 , a W > a M . To summarize, we do identify 4 areas:

                     For κ > 2+ √ 2 4 a M ≥ a W > a * For √ 6- √ 2 2 < κ < 2+ √ 2 4 a M > a * ≥ a W For κ ≤ √ 6- √ 2 2 and λ < 2κ 3 1-κ 2 a * ≥ a W > a M κ(1+κ 2 ) 1-κ 2 < λ < 2κ 3 1-κ 2 a * ≥ a M > a W λ > κ(1+κ 2 ) 1-κ 2 a M ≥ a * > a W

3. 1

 1 Benchmark: a Myopic Monopolist (M)

2 Figure 1 :

 21 Figure 1: Comparison of quantities

Figure 2 :

 2 Figure 2: Comparison of prices

2 Figure 3 :

 23 Figure 3: Comparison of minutes of TV broadcasted

2 Figure 4 :

 24 Figure 4: Comparison of minutes of advertisements broadcasted

  ⇔ u ′ (n) + αmc + κa δ = 0After simplifying with cm = 1, δ = 1 2 , α = 1 and assuming u(n) = ln(n), we obtain

√ 2 4 For 2+ √ 2 4 ≤ 4 n

 444 2κ ≥ λ which is compatible with the definition of n * since 2κ > (2 √ 2κ -1) κthus there is no problem with the existence condition. To sum up:For κ ≥ 1 n M ≥ n W > n * κ < 1 n W > n M > n * For κ < 2+ √ 2 * > n W > n M .

2 4 2 4 ,

 224 , we have shown that a M > a W , thus, for κ ≥ 2+ √ a M ≥ a W > a *

As m is an exogenous parameter in our model, we denote u ′ (n; m) the first derivative of u(n; m) with respect to n.

For c¡m, the profit is strictly increasing in n and there is no interior solution. Indeed, if the opportunity to consume TV on mobility is higher than the marginal production cost, utility is increasing in n.


Manar Qamhieh
email: manar.qamhieh@univ-paris-est.fr

Serge Midonnet
email: serge.midonnet@univ-paris-est.fr

Schedulability Analysis for Directed Acyclic Graphs on Multiprocessor Systems at a Subtask Level

This paper addresses the problem of scheduling parallel realtime tasks of Directed Acyclic Graph (DAG) model on multiprocessor systems. We propose a new scheduling method based on a subtask-level, which means that the schedulability decisions are taken based on the local temporal parameters of subtasks. This method requires modifying the subtasks to add more parameters which are necessary for the analysis, such as local offsets, deadlines and release jitters. Then we provide interference and workload analyses of DAG tasks, and we provide a schedulability test for any work conserving scheduling algorithm.

Introduction

Recently, the performance of systems has been increased using multiprocessors instead of uniprocessors to overcome processor physical limitations and to produce faster and smaller processors. The use of parallelism in software makes them compatible with multiprocessor hardware, because the calculations of parallel applications are performed on multiple processors simultaneously. In real-time systems, scheduling parallel real-time tasks on multiprocessor systems is a challenging problem, and the extension of uniprocessor schedulability conditions to parallel multiprocessor systems is not trivial. The need of synchronization between parallel tasks and processors makes the scheduling process more complicated.

In this paper, we are interested in scheduling Directed Acyclic Graph (DAG) tasks on multiprocessor systems. The contribution is to provide schedulability conditions for DAG tasks that take into account subtasks' parameters instead of DAG-level parameters (a solution commonly used in previous researches found in literature).

The remainder of this paper is organized as follows. In Section 2, we present a state-of-the-art of methods relative to real-time parallel task scheduling on multiprocessor systems especially for the DAG model. The considered model and the used terminology are described in Section 3. In Section 4, we explain the subtask-level scheduling process, and we define additional parameters to subtasks in order to be scheduled individually using any work conserving algorithm. A workload analysis is given in Section 5. This workload analysis is used to derive a schedulability test for any work conserving scheduling algorithms. Finally, we conclude this study and show future work in Section 6.

2R e l a t e d w o r k

Many hard real-time scheduling algorithms and schedulability analyses on homogeneous multiprocessor systems have been proposed in the literature [START_REF] Davis | A survey of hard real-time scheduling algorithms and schedulability analysis techniques for multiprocessor systems[END_REF]. They mostly focus on the traditional sequential independent real-time task model.

Regarding parallel tasks, there are different models and each has its own advantages and limitations. First there is the Fork-join model, in which a parallel task is an alternating sequence of parallel and sequential segments, a stretching algorithm to execute parallel segments as sequential as possible was proposed in [START_REF] Lakshmanan | Scheduling Parallel Real-Time Tasks on Multi-core Processors[END_REF].

A more general model of parallel tasks, called the segment model, has been studied in the literature. The multiprocessor scheduling of periodic tasksets with implicit deadlines with this model has been addressed in [START_REF] Saifullah | Multi-core Real-Time Scheduling for Generalized Parallel Task Models[END_REF]. This model represent a task as a sequence of segments, each segment consists of a number of identical threads.

The analysis has been extended to the DAG model and the same results can be applied. Another scheduling approach based on the response time analysis for the multi-threaded segment model has been provided in [START_REF] Liu | Supporting Soft Real-Time Parallel Applications on Multicore Processors[END_REF] for soft real-time multi-core systems.

The DAG model has been studied in [START_REF] Chetto | Dynamic scheduling of real-time tasks under precedence constraints[END_REF] in the uniprocessor case. The authors considered a hybrid task set of periodic independent tasks and dependent sporadic graph tasks that execute only once. A graph task in this model consists of a set of tasks with precedence constraints and each task has a release time and deadline. They proposed an algorithm based on a modification of task parameters in order to remove the dependencies between the tasks in the analysis. We use a similar technique in Section 4 to modify subtasks with few differences due to the characteristics of the model.

A capacity augmentation bound of 4-2 m and a resource augmentation bound of 2 -1 m have been proposed recently for GEDF scheduling of periodic implicitdeadline DAG tasksets in [START_REF] Li | Analysis of Global EDF for Parallel Tasks[END_REF], where m is the number of processors in the system. Also, Bonifaci et al. [START_REF] Bonifaci | Feasibility Analysis in the Sporadic DAG Task Model[END_REF] studied the schedulability of a DAG set on multiprocessor systems. They proved that GEDF has a speedup bound of 2-1/m, and Deadline monotonic a speedup bound equal to 3-1/m. It is worth noticing that the above described scheduling methods do not consider the internal structure of DAGs in the analysis. And the parallel DAG tasks are either transformed into a collection of independent sequential tasks or they are scheduled directly while considering the global parameters of the DAGs, such as their total worst-case execution time and the critical path length.

More recently, we proposed in [START_REF] Qamhieh | Global EDF Scheduling of Directed Acyclic Graphs on Multiprocessor Systems[END_REF] a schedulability test of periodic implicitdeadline DAG tasks when GEDF is used. The schedulability decisions are based on a DAG-level (the global deadline of the DAGs), while the workload analysis of the test considered the internal structure of DAGs. We proved by experimental results that this method reduces analysis pessimism and enhances scheduling performance for DAGs. This paper is an extension of this work, in which we aim at enhancing the scheduling analysis by proposing a DAG scheduling on a subtask-level. To our best knowledge, no similar research exists using the method to address the problem of scheduling parallel DAG tasks.

System model

In this paper, we consider a taskset τ of n real-time Directed Acyclic Graph (DAG) tasks scheduled on m identical processors. Each DAG task τ i is a sporadic constrained-deadline graph composed of n i subtasks under precedence constraints.

A DAG task τ i is characterized by

(n i , {1  j  n i |τ i,j },G i ,D i ,T i )
, where n i is the number of its subtasks, the second parameter is the set of subtasks, G i is the set of directed relations between the subtasks, D i is the relative deadline of τ i and T i is the minimum inter-arrival time between the successive jobs.

Let τ i,j denote the j th subtask of the set of subtasks forming DAG task τ i ,w h e r e1 j  n i . Each subtask τ i,j is a single-threaded task that has a single timing parameter which is its worst case execution time (WCET) C i,j . The subtasks of a DAG inherit the period and deadline of their DAG. Let g i,j i,k 2 G i represent a directed link from subtask τ i,j to τ i,k .Ad i r e c tl i n k between subtask τ i,j and τ i,k means that subtask τ i,k cannot start its execution unless subtask τ i,j completes its own. In this case, subtask τ i,j is called a parent subtask of τ i,k where τ i,j 2 parents(τ i,k ) 2 pred(τ i,k ), where pred(τ i,k )i st h e set of all predecessors of subtask τ i,k from the source of the DAG which have to execute indirectly before τ i,k (such as parents of τ i,k 's parents). Likewise, subtask τ i,k 2 children(τ i,j ) is called a child subtask of τ i,j , and the set of all successors of τ i,k is denoted by succ(τ i,k ). Subtask τ i,j may have zero or more parent/children subtasks. A source subtask has no parent subtasks and a sink subtask is the one without any successors.

Let C i denote the total WCET of DAG task τ i ,w h e r eC i = P ni k=1 C i,k . Let L i denote the length of the critical path of DAG task τ i , which is defined as the longest execution path in τ i when it executes on a platform of infinite number of processors.

We assume that each DAG task τ i generates an infinite sequence of jobs. Let J k i be the k th job of DAG task τ i which is characterized by (r i , d i ), where r i is the release time of the job, and d i is its absolute deadline. Each DAG job J k i consists of a collection of subtask jobs each is denoted by J k i,j , j 2 1 ...n i . In the remainder of this paper, the numeration of jobs is removed when it is unnecessary for the clarity of the discussion.

Figure 1(a) shows an example of a DAG task τ 1 which consists of 6 subtasks. Subtask τ 1,1 is the source of the DAG and τ 1,6 is its sink. The lines in the figure represent the directed precedence constraints between the subtasks. The critical path of τ 1 is {τ 1,1 , τ 1,2 , τ 1,6 } and its length is L i = 6. For subtask τ 1,5 , its parent subtask is τ 1,3 while τ 1,1 is one of its predecessor.

For any DAG taskset, there are two necessary basic conditions, if at least one of them is false, the taskset is not feasible:

X τi2τ C i T i  m 8{τ i 2 τ } : L i  D i
In the following sections, we provide a schedulability analysis for DAG tasks using any global work conserving scheduling algorithm. A global algorithm allows job migration and preemptions between processors (migration costs and preemption costs are not taken into account in this work), while a work conserving algorithm does not authorize delaying the execution of an active job if there is an idle processor in the system.

DAG task Scheduling

When scheduling DAG sets on multiprocessor systems, the interference on each DAG task has the following two sources:

an external interference from jobs of higher priority DAG tasks, in which some or all of the interfering subtasks can contribute to the interference, -an internal interference from the subtasks of the same DAG on each other.

For parallel DAG tasks, a DAG-level scheduling algorithm means that the scheduling decisions are based on global parameters of the DAG tasks. According to this scheduling, the priorities are assigned to DAG tasks which are applied then to their respective subtasks. The DAG-level schedulability analysis depends on the global parameters of the DAGs, such as their deadline, period, total WCET and the length of their critical path. Usually, the resulted schedulability tests are pessimistic, and the internal structure of the DAGs is not considered in the performed analysis.

Hence, the interference analysis of DAG-level scheduling is difficult to be calculated and it is harder to identify the exact sources of interference. However, if the scheduling algorithm uses extra knowledge about subtasks and their execution flow, then the interference analysis can be more accurate and precise. In this case the scheduling process is said to be done at a subtask-level. According to this, subtasks will be assigned priorities based on the scheduling algorithm. However, the schedulability analysis requires extra temporal parameters for each subtask other than its WCET provided by the DAG model.

Further in this paper, we will propose a technique to add local temporal parameters to the subtasks based on their dependencies and the precedence constraints between them. As a result, the problem of scheduling parallel DAG tasks on multiprocessor systems will be simplified to scheduling a set of independent sequential subtasks on multiprocessor systems, which is widely studied in the literature.

Subtask analysis and modification

In a previous work [START_REF] Qamhieh | Global EDF Scheduling of Directed Acyclic Graphs on Multiprocessor Systems[END_REF], we provided algorithms to add two temporal parameters, in addition to the WCET parameter (provided by the model), to each subtask in the DAG set. This was done to improve the interference analysis of DAG scheduling in the case of GEDF scheduling. These two parameters are the local offset and deadline of each subtask, and they were derived from the internal structure of the DAG task and the execution flow of the subtasks in the best case scenario. We consider that this scenario happens when a DAG set executes on an infinite number of processors, all of its subtasks execute in parallel as soon as possible without being delayed due to interference. Definition 1. Al o c a lo ffset O i,j of a subtask τ i,j is defined as the earliest possible activation time of the subtask w.r.t. the release of its DAG task τ i . Definition 2. Alo c alde adlineD i,j of a subtask τ i,j is the latest time for subtask τ i,j to complete its execution so as to leave enough time for its successors to execute within their local deadlines.

For each subtask, the local offset and deadline are calculated using straightforward depth-first search algorithms (a detailed description can be found in [START_REF] Qamhieh | Global EDF Scheduling of Directed Acyclic Graphs on Multiprocessor Systems[END_REF]). The local offset of a subtask takes into consideration the time needed for its predecessor subtasks to execute in the best case scenario. Respectively, the local deadline of a subtask leaves enough time for its successor subtasks to execute.

Observation 1 If a subtask τ i,j 2 τ i misses its local deadline D i,j , then its DAG task τ i will definitely miss its deadline D i .

Based on the definition of the local deadline, when a subtask misses its local deadline, the time remaining until the global deadline of the DAG task is not enough for the successors to execute in the best case. Therefore, an early schedulability failure can be announced based on the subtask's deadline instead of waiting for the DAG's deadline miss.

Figure 1 shows the mapping between the DAG task τ 1 and its subtasks after the modification. The timing diagram of each subtask τ 1,j ,w h e r e1 j  6, of the DAG is shown in Figure 1(b). The local offset O 1,1 of the source subtask τ 1,1 equals to 0 because this subtask has no predecessors and it is released at the release time of the DAG task τ 1 . Its local deadline D 1,1 = 3 because its successors need at least 5 time units to execute in the best case, which is the longest path from τ 1,1 (excluded) to a sink subtask ({τ 1,2 , τ 1,6 } in the example). Then, both subtasks τ 1,2 and τ 1,3 are released after the completion of τ 1,1 . As a result, O 1,2 = O 1,3 = 1. For the rest of the subtasks, their local offsets and deadlines are shown in Figure 1(b).

The local offsets and deadlines of subtasks are calculated based on their best-case activation scenario, in which all the subtasks execute as soon as they are released with no interference or delays, These parameters helps in identifying the longest execution window of each subtask. However, the activation of a subtask job can be delayed due to the interference of higher priority subtasks. Respectively, the latest possible activation of a subtask job occurs when all of its predecessors execute as late as possible (just before their local deadlines). According to this, the activation of a subtask job can happen at any time within this interval, and this can be considered as the maximum release jitter of the subtask. Definition 3. A maximum release jitter b j i,j of a subtask τ i,j is defined as the difference between the earliest and latest release time of the subtask with respect to the activation of the DAG task. b j i,j = max 8τ i,k 2P arents(τi,j )

(D i,k -(O i,j -O i,k )) (1)
Based on the definition of the release jitter of a subtask, all of its jobs are released within the jitter interval, which is shown in the following equation: 1(b) shows the maximum release jitter values for the subtasks in DAG τ 1 from Figure 1(a). It's worth noticing that the source subtask τ 1,1 has no jitter since it has no predecessor subtasks.

8J j i,k ,j2 N, τ i,k 2 τ i : r j i,k 2 [O i,k ,O i,k + b j i,j ] Figure
From Equation 4.1 and the example in Figure 1(b), we can notice that the calculation of the release jitter of the subtasks is pessimistic, and it considers always that the predecessor subtasks execute as late as possible. According to this, the critical subtasks of a DAG task (subtasks forming its critical path) will have no slack time1 if they are activated at their maximum release jitter. In the following sections, we provide an optimization to the release jitter of subtasks based on the interference analysis.

Regarding the period of the subtasks (minimum inter-arrival time for sporadic tasks), each subtask inherits the period of its DAG task, where 8τ i,j 2 τ i ,T i,j = T i .

As a result, the subtasks of a given DAG task are characterized now by a local offset, a WCET, a local deadline and a release jitter. These parameters will allow us to treat subtasks individually and independently in order to provide a schedulability analysis at a subtask-level.

Interference Analysis

For the subtask-level scheduling process using any work conserving algorithm, the execution of a subtask can be blocked by higher priority subtasks. The interference on a subtask τ k,h 2 τ k is defined as follows:

Definition 4. I k,h (a, b)
is the length of all intervals where subtask τ k,h is ready to execute but blocked by higher priority subtasks in an interval [a, b).

Definition 5. I i,j k,h (a, b)
is the length of all intervals where subtask τ k,h is ready to execute but blocked by subtask τ i,j which has higher priority in an interval [a, b).

Since the subtasks are single-threaded sequential real-time tasks, the relation between I k,h (a, b) and I i,j k,h (a, b) is denoted by the following equation:

I k,h (a, b)= 1 m ⇤ X 8τi,j 2τi2τ I i,j k,h (a, b) (2)
Due to the characteristics of the DAG tasks and the precedence constraints between the subtasks, the interference on a subtask τ k,h is divided into two sources, external and internal interference. Let Ie k,h (a, b) denote the interference from higher priority subtasks of DAG tasks other than τ k in the set, which is defined as follows:

Ie k,h (a, b)= 1 m ⇤ X i6 =k,8τi,j 2τi I i,j k,h (a, b) (3)
Where some or all of the subtasks of DAG task τ i (i 6 = k) can interfere with τ k,h based on their priorities. Furthermore, subtasks of DAG τ k can block the execution of τ k,h which is defined as the internal interference Ii k,h (a, b). Since we consider constrained deadline DAG tasks, for a given job of subtask τ k,h , one job at most from each subtask contributes to the interference. The internal interference depends on the type of interfering subtasks which are divided into the following categories:

a predecessor subtask τ k,x 2 pred(τ k,h ) of subtask τ k,h : this subtask will delay the activation of τ k,h , but once subtask τ k,x completes its execution, subtask τ k,h will start its own and there will be no further effect of τ k,x on τ k,h , -a sibling subtask τ k,x 2 sibling(τ k,h ) is the subtask that executes in parallel with no dependencies with subtask τ k,h .T h esibling(τ k,h ) is the set of subtasks that are not predecessors or successors of subtask τ k,h , -a successor subtask τ k,x 2 succ(τ k,h ) has no interference with subtask τ k,h , because both subtasks cannot execute in parallel and subtask τ k,x starts its execution after τ k,h completes its own. According to this, I k,x k,h (a, b) = 0, -subtask τ k,h has no interference on itself since we consider constrained deadline DAG tasks, in which only one job of each DAG task is activated at any time t. Hence, I k,h k,h (a, b) = 0. Based on the above definitions, the internal interference Ii k,h (a, b) on subtask τ k,h in the interval [a, b) is defined as:

Ii k,h (a, b)= 1 m ⇤ X 8τ k,i 6 2succ(τ k,h );i6 =h I k,i k,h (a, b) (4)
Let J ⇤ k,h be the job of subtask τ k,h which has maximum interference, and let

I k,h (r ⇤ k,h ,d ⇤ k,h ) denote the worst-case interference for subtask job J ⇤ k,h of τ k,h in the interval [r ⇤ k,h ,d ⇤ k,h ).
For the sake of clarity, we will use b

I k,h = I k,h (r ⇤ k,h ,d ⇤ k,h ) in this document.
Lemma 1. A taskset τ , of sporadic constrained deadline DAG tasks, is schedulable on m identical processors, for any work conserving algorithm if:

8τ k,h 2 τ k 2 τ b I k,h = b Ie k,h + b Ii k,h  (D k,h -C k,h ) (5)
Proof. The proof of this lemma is straight-forward. The interference on a subtask job has two main sources; internal and external. In order for any subtask to be schedulable, its execution window (between its activation and deadline) should be enough to execute its execution time plus the interference workload which is identified above.

Interference from Predecessor subtasks

As described earlier, a predecessor subtask should complete its execution before its successors are activated. Hence, a successor subtask can only be delayed by its predecessors. In Section 4.1, we assigned a maximum release jitter for each subtask in the DAG. This parameter represents the interval in which the subtask job can be activated and it replaces the dependencies between the subtasks. If we consider that all the predecessors of τ k,h have executed as late as possible, then the subtask job J ⇤ k,h will be delayed to the end of this interval ( b j k,h time units after its offset), then the condition in Lemma 1 will be modified as follows: Lemma 2. A taskset τ of DAG tasks is schedulable on m identical processors, using any work conserving algorithm, if:

8τ k,h 2 τ k 2 τ b Ie k,h + b Ii k,h  (D k,h -C k,h -b j k,h )  (D k,h -C k,h -j k,h ) (6) where b Ii k,h = 1 m ⇤ X 8τ k,i 2sibling(τ k,h ) I k,i k,h (a, b)
Proof. As shown in Figure 2 and based on the definition of the release jitter in Equation 4.1, if all predecessors respected their local deadlines, then subtask τ k,h will be activated no later than t =(r k + O k,h + b j k,h ). In the interval [t, d k,h ), predecessors will have no further interference, and only sibling subtasks of τ k,h will interfere with τ k,h , which should be less than the available slack time We have mentioned earlier that considering the maximum release jitter b j k,h of subtask τ k,h in the interference analysis is too pessimistic, because it considers that the predecessors will execute as late as possible. As a result, the upper bound of interference used in Lemma 2 will be always zero for any critical subtask τ k,h since their release jitter b j

(D k,h - C k,h -j k,h ). k,h rk dk dk,h Ok,h jk,h Dk,h Dk,h-Ck,h-jk,h
k,h = D k,h -C k,h .
As shown in Figure 3, it is possible to optimize the jitter of each subtask by knowing that a parent subtask τ k,i has a response time equal to ( b I k,i +C k,i )when a work conserving algorithm is used. Its latest finish time f ⇤ k,i can be defined as:

f ⇤ k,i = C k,i + b I k,i  D k,i
The finish time f k,i of any job of a schedulable subtask τ k,i should not be greater than its local deadline D k,i , or a deadline miss will occur.

By using the finish time of each parent subtask of τ k,h , we can calculate an optimized release jitter j 0 k,h defined by the following equation:

j 0 k,h = max 8τ k,i 2parents(τ k,h ) (f ⇤ k,i -(O k,h -O k,i )) = max 8τ k,i 2parents(τ k,h ) (C k,i + b I k,i -(O k,h -O k,i )) (7)  b j k,h k,i k,h rk dk Ck,i Ck,h jk,h j'k,h Ik,h dk,i dk,h fk,i
Fig. 3. The optimized release jitter of subtask τ k,h from its sole parent τ k,i .

Corollary 1. A taskset τ of DAG tasks is schedulable on m identical processors, using any work conserving algorithm, if:

8τ k,h 2 τ k 2 τ b Ie k,h + b Ii k,h  (D k,h -C k,h -j 0 k,h ) (8) where b Ii k,h = 1 m ⇤ X 8τ k,i 2sibling(τ k,h ) I k,i k,h (a, b) (9)
The use of the optimized release jitter of a subtask instead of its maximum release jitter improves the schedulability test by considering a more accurate upper bound on interference.

Workload Analysis

It is difficult to identify the actual interference from external and sibling subtasks required for the schedulability test in Corollary 1. However, we can use an upper bound on the interference based on the workload computation of an interfering subtask, knowing that the interference of a subtask on another one in a fixed interval cannot exceed the workload of the interfering subtask during the same interval. Let W i,j (a, b) be the amount of work done by the jobs of subtask τ i,j in the interval [a, b). Then:

I i,j k,h (a, b)  W i,j (a, b) Within the interference interval [a, b)
, let a carry-in job of an interfering subtask be defined as the job that is released before the start of the interval and has a deadline within the interval. While a body job is the job that is released within the interval [a, b) and its deadline can be within or after the end of the interval.

Workload from sibling subtasks

A sibling subtask τ k,i of τ k,h is the subtask from the same DAG task τ k that can execute in parallel with τ k,h . Moreover, subtask τ k,i has no precedence relations with τ k,h and it cannot be among its predecessors or successors.

For a given subtask job, one job at most from each sibling subtask will interfere with it, because the jobs of sibling subtasks belong to the same DAG job, and the release of their DAG job is considered as their activation reference. In other words, one job from each sibling subtask τ k,h is released in the interval

[r k + O k,h ,r k + O k,h + b j k,h ].
For any work conserving algorithm, the interference b Ii k,i k,h of a subtask τ k,i on its sibling τ k,h is calculated by identifying the maximum interfering interval L k,i k,h of τ k,i on τ k,h . This interval is defined as the longest interval in which subtasks τ k,h and τ k,i can execute in parallel. It is calculated as follows:

L k,i k,h = min(D 0 k,i ,D 0 k,h ) -max(O k,i ,O k,h ) (10)
For the sake of clarity, we considered D 0 k,h to be the relative deadline of subtask τ k,h from the release of the DAG task, where

D 0 k,h = O k,h + D k,h . Lemma 3. The maximum internal interference b Ii k,i k,h of subtask τ k,i on a job of its sibling subtask τ k,h is b Ii k,i k,h  min(C k,i ,L k,i k,h )= c Wi k,i (11)
Proof. Based on the definition of the interference interval L k,i k,h , the maximum possible workload of subtask τ k,i in the interval happens when τ k,i executes as long as possible in this interval. From here comes the min in the Equation 11.

Workload Analysis for External subtasks

For any work conserving algorithm, Bertogna et al. identified, in their paper [START_REF] Bertogna | Schedulability Analysis of Global Scheduling Algorithms on Multiprocessor Platforms[END_REF], the worst-case activation scenario of jobs of an interfering task in a fixed interval (a, b) which generates the maximum possible workload. They considered a task model of independent sequential single-threaded tasks. As shown in Figure 4, this scenario happens when the carry-in job of the interfering task starts its execution at the beginning of the interference window and executes as late as possible. The following body jobs then execute as soon as possible until the end of the window. This scenario is proved in [START_REF] Bertogna | Schedulability Analysis of Global Scheduling Algorithms on Multiprocessor Platforms[END_REF] to generate the maximum workload in the interval. We use this scenario to calculate the workload of each external subtask in order to be used as an upper bound of its interference on a given subtask in the system. Since each external subtask τ i,j has no precedence constraints with τ k,h (where k 6 = i), then this scenario can be applied to each subtask independently. As shown in Figure 5, the subtasks of an interfering DAG task τ i will interfere on subtask job J ⇤ k,h . Assume that subtask job J ⇤ k,h has an activation window [r ⇤ k,h ,d ⇤ k,h ) as shown in Figure 5(b), while Figure 5(a) shows the DAG task τ i and its internal structure. In order to calculate the worst-case workload of its subtasks on j k,h , the worst-case activation scenario is applied to each subtask τ i,j . As shown in Figure 5(b), the first job of each subtask starts its execution as late as possible at the beginning of the interference interval, and the following job executes as soon as possible. Based on this scenario, the maximum workload done in the interference interval is 10.

However, applying this scenario on each subtask of the same DAG task independently is pessimistic. Because in reality, these interfering subtasks have precedence constraints that define their execution flow. For example, subtask τ i,1 in Figure 5(b) cannot execute in parallel with its children subtasks τ i,2 and τ i,3 . But still, the workload in this activation scenario can be used as an upper bound for workload. Using the following example, we will show that it is not trivial to find a worst-case activation scenario of jobs adapted to DAG tasks that generates the maximum workload. i1 (0,4) i2 [START_REF] Saifullah | Multi-core Real-Time Scheduling for Generalized Parallel Task Models[END_REF][START_REF] Saifullah | Multi-core Real-Time Scheduling for Generalized Parallel Task Models[END_REF] i3 [START_REF] Saifullah | Multi-core Real-Time Scheduling for Generalized Parallel Task Models[END_REF][START_REF] Saifullah | Multi-core Real-Time Scheduling for Generalized Parallel Task Models[END_REF] (c) The worst workload activation scenario for subtask jobs of τi for Global EDF.

(d) First possible activation scenario of subtasks of τi. Total workload is 3.

(e) Second possible activation scenario of subtasks of τi. Total workload is 4.

(f) Third possible activation scenario of subtasks of τi. Total workload is 5. Example Back to the DAG task τ i from Figure 5(a). According to the precedence constraints between its subtasks, the activation scenario of its subtask jobs is shown in Figures 5(d to the interfering subtasks. For example, Figure 5(d) considers that subtask τ i,1 starts at the beginning of the interfering interval, and its total workload is 3. While Figure 5(e) considers that subtasks τ i,2 and τ i,3 start at the beginning of the interval and the total workload is 4. However, the maximum workload happens in Figure 5(f), in which the interference interval starts within subtask τ i,1 and it ends at the deadline of τ i,2 and τ i,3 . In this case the total workload is 5.

Based on this example, we conclude that in order to calculate the maximum workload of external subtasks of the same DAG, we have to analyze all the possible positions of interference interval w.r.t. the activation of subtasks, and this is done at each time instant in the interfering interval. k,h of subtask τ i,j on subtask τ k,h in an interval, whose length is equal to the absolute deadline D k,h of τ k,h , is bounded by:

b Ie i,j k,h  N i,j (D k,h )C i,j + (12) min(C i,j ,D k,h + D i,j -C i,j -N i,j (D k,h )T i,j )
where

N i,j (D k,h )=b D k,h + D i,j -C i,j T i,j c
Proof. The maximum interference workload from the external subtask τ i,j on subtask τ k,h happens based on the execution scenario described in [START_REF] Bertogna | Schedulability Analysis of Global Scheduling Algorithms on Multiprocessor Platforms[END_REF] and shown in Figure 4. The calculations of workload is based on number of interfering jobs which lie completely within the interfering window plus the last job in the interval which may contribute partially in the interference. More details about these equations can be found in [START_REF] Bertogna | Schedulability Analysis of Global Scheduling Algorithms on Multiprocessor Platforms[END_REF].

A schedulability test for DAG tasks using any work conserving algorithm on m identical processors is provided as follows: Theorem 1. A DAG set τ is schedulable on m identical processors using any work conserving algorithm if:

8τ k,h 2 τ k 2 τ X τ k,i 2sibling(k,h) min( b Ii k,i k,h ,D k,h -C k,h -j 0 k,h )+ X τi,j ; i6 =k min( b Ie i,j k,h ,D k,h -C k,h -j 0 k,h )  m(D k,h -C k,h -j 0 k,h )
Proof. Knowing that the interference of a subtask in a given interval can never exceed the workload of this subtask in the same interval, we can transform the interference schedulability bound on subtask τ k,h described in Lemma 3 into a workload bound of schedulability of the same subtask. However, the internal and the external interference are based on their respective workload calculations shown in Equations 11 and 12,

The schedulability test described in the above theorem can be used to optimize the release jitter value of each subtask. Based on the test, the optimized release jitter can be calculated for each successor of the subtask. If the calculated release jitter is more than the actual release jitter (the maximum release jitter by default), then the calculated value is discarded and the actual release jitter will not be modified.

In order to analyze the performance of our schedulability test, we compare it with another test found in literature. Bonifaci et al. in [START_REF] Bonifaci | Feasibility Analysis in the Sporadic DAG Task Model[END_REF] provided a GEDF schedulability test for DAG set on m identical processors. The test depends on the global parameters of the DAG tasks without considering the internal structure and the execution flow of the subtasks. Our schedulability test provided in Theorem 1 is provided for any work conserving algorithm. For the sake of simulation, we derived a special case of this test for GEDF scheduling algorithm and the results are shown in Figure 6. We generated a large number of random DAG tasksets, and we applied both GEDF-schedulability tests on the sets of utilization that range from 0 to 8. As shown in Figure 6, our own scheduling test (denoted by OWN ) performs better than the test from [START_REF] Bonifaci | Feasibility Analysis in the Sporadic DAG Task Model[END_REF] (denoted by BMS ). For each system utilization, our test schedules more DAG sets than the BMS test.

The simulation results provided in this section proves the importance of the internal structure of DAG tasks in the schedulability analysis.

Conclusion

In this paper, we were interested in the scheduling of parallel real-time DAG tasks on multiprocessor systems. Our motivation was to show that the scheduling of real-time DAG tasks is affected by the internal structure of the DAG and the execution flow of its subtasks. Hence, we applied the scheduling algorithms at subtask-level instead of DAG-level. This means that the scheduling decisions are based on local parameters of subtasks instead of the global parameters of DAGs.

We modified the subtasks by adding local parameters such as local offset, deadline and release jitter for each subtask. Then we provided interference and workload analyses for any work conserving scheduling algorithm.

As a future perspective, we aim at extending our work to analyze common scheduling algorithms such as EDF and DM, so as to provide precise schedulability test for each algorithm. Also, we aim at providing further analysis for subtask-level schedulers including performance metrics such as speedup factor and approximations ratio. These metrics can be used as an indication of the performance of our proposed scheduling method.

  A DAG task τ1 consists of 6 subtasks with parameters: D1 = 8, C1 =10,L1 =6.

Fig. 1 .

 1 Fig. 1. Example of DAG model.

Fig. 2 .

 2 Fig. 2. The interference window excluding interference from predecessor subtasks.

  i

Fig. 4 .

 4 Fig. 4. The densest possible packing of jobs in interval pf length L for traditional task using any work conserving algorithm.

  (a) Example of a DAG task τi.

  The worst workload activation scenario for subtask jobs of τi for any work conserving algorithm.

Fig. 5 .

 5 Fig. 5. Workload analysis for external subtasks.

  )-5(f). We consider an interference interval of length L = 3. Each Figure in 5(d)-5(f) shows a possible position of the interference interval w.r.t.

Lemma 4 .

 4 The external interference b Ie i,j

Fig. 6 .

 6 Fig. 6. Simulation results.

Slack time is the time difference between the deadline of a task and its WCET.