Pierre Cahuc
email: pierre.cahuc@ensae.fr

Guy Laroque

Etienne Lehmann

OPTIMAL TAXATION AND MONOPSONISTIC LABOR MARKET: DOES MONOPSONY JUSTIFY THE MINIMUM WAGE?

Keywords: Minimum wage, Optimal taxation, Monopsony H31, J30, J42

Does monopsony on the labor market in itself justify the implementation of a minimum wage when it would not be used in a competitive economy? This issue is studied in a model of optimal taxation. We adopt a definition most favorable to the minimum wage: the minimum wage is useful whenever it can replace a non negligible part of the tax schedule. The minimum wage is useful to correct the inefficiencies associated with the monopsony when there is a single skill. But the minimum wage is not useful any more when there are a continuum of skills.

Introduction

A popular justi…cation of the minimum wage is that it strengthens the hand of the low skilled workers who are exploited by monopsonist employers. As stressed by [START_REF] Dolado | The Role of the Minimum Wage in the Welfare State: An Appraisal[END_REF], proponents of the minimum wage take the competitive working of the labor market as the exception, rather than the rule, arguing that in many reasonable instances "monopsony" corresponds to the rule. Then, the minimum wage seems to be useful because it increases both employment and the income of low wage workers. This view had a strong in ‡uence on economic policy in the last …fteen years. For instance, in 1994, the OECD Jobs Study was arguing that there was a need to "reassess the role of statutory minimum wages as an instrument to achieve redistributive goals, and switch to more direct instruments" (OECD, 1994). Four years later, after the publication of a set of papers and a book arguing that minimum wage increases could bene…t low skilled employment according to the predictions of the monopsony model of the labor market [START_REF] Card | Myth and Measurement: The new economics of minimum wage[END_REF], the perspective was quite di¤erent: the OECD Employment Outlook stressed that "a well-designed policy package of economic measures, with an appropriately set minimum wage in tandem with in-work bene…ts, is likely, on balance, to be bene…cial in moving towards an employment-centered social policy" (OECD, 1998).

While the recent minimum wage research …nds a wide range of estimates on the overall e¤ects on low-wage employment of an increase in the minimum wage [START_REF] Neumark | Minimum Wages and Employment: A Review of Evidence from the New Minimum Wage Research[END_REF], the monopsony model remains in ‡uential. For instance, in year 2005, it is still argued by the OECD that "the main impact of downward wage ‡exibility may be to worsen inactivity, unemployment and low-pay traps."(OECD, 2005, p 142). As a matter of fact, today, statutory or quasi-statutory minimum wages are in place in 21 OECD countries [START_REF] Immervoll | Minimum Wages, Minimum Labour Costs and the Tax Treatment of Low-wage Employment[END_REF]).

An interpretation of the debate is that the practical justi…cation of a minimum wage is the existence of a large sector of monopsonist employers, while under perfect competition the scope for a minimum wage would be minimal. The purpose of our study is to address this precise question: does monopsony on the labor market in itself justify the implementation of a minimum wage? Our approach is theoretical and considers a situation where the government can use non linear taxes. Of course, if one does not put any restriction on the shape of taxes, a minimum wage W can be mimicked by imposing very high taxes on wages below W ; so that the minimum wage would be redundant. To deal with this issue we choose a view point a priori favorable to the minimum wage: we consider that the minimum wage is a valid instrument whenever it can replace a non negligible part of the tax schedule. For instance, we consider that the minimum wage is useful if taxes prevent hirings below a wage threshold. This approach implies that the minimum wage is useful in the monopsony model with a single skill, a result known since the contributions of [START_REF] Robinson | The Economics of Imperfect Competition[END_REF] and [START_REF] Stigler | The Economics of Minimum Wage Legislation[END_REF]. Indeed, when there is a single skill, the government can reach the competitive equilibrium with the minimum wage without using taxes.

However, when the heterogeneity of skills is accounted for, the minimum wage cannot play this role any more. The government always needs taxes to correct the ine¢ ciencies associated with the monopsony. Strikingly, in that case, we …nd that there is no scope for the minimum wage. This result is not limited to the pure monopsony model. It also applies to monopsonistic competition with free entry.

The papers which look at the minimum wage in labor markets with imperfect competition typically ask whether increasing the minimum wage can improve employment or welfare in the absence of other policy tools. 1 The e¢ ciency of the minimum wage when there are taxes has mostly been considered in labor markets with perfect competition. 2 Most models have adopted the standard [START_REF] Mirrlees | An Exploration in the Theory of Optimum Income Taxation[END_REF] model on optimal taxation with labor supply at the intensive margin where individuals choose the number of hours they work and where the government observes earnings but neither hourly wages nor hours of work. It turns out that the minimum wage can be welfare improving when tax schemes are constrained or when there are speci…c assumptions made to allow the government to observe skills at the bottom of the income distribution (Allen, 1984[START_REF] Guesnerie | Minimum Wage Legislation as a Second-Best Policy[END_REF][START_REF] Boadway | A Minimum Wage can be Welfare Improving and Employment-Enhancing[END_REF]. However, as stressed by Guesnerie and Roberts (1987) and more recently by [START_REF] Lee | Optimal Minimum Wage Policy in Competitive Labor Markets[END_REF], informational inconsistencies arise when a minimum wage is introduced in the Mirrlees model because the minimum wage implementation requires observing hourly wages. But if hourly wages were directly observable, then the government could achieve any …rst best allocation by conditioning taxes and transfers on hourly wage and the minimum wage would obviously not be useful. This informational inconsistency leads us to focus on labor supply at the extensive margin where the agents' decision is zero-one, to work or not to work, as in the studies of Diamond (1980), [START_REF] Beaudry | Taxes and Employment Subsidies in Optimal Redistribution Programs[END_REF], [START_REF] Saez | Optimal Income Transfer Programs: Intensive versus Extensive Labor Supply Responses[END_REF], Choné andLaroque (2005, 2008) and [START_REF] Laroque | Income Maintenance and Labor Force Participation[END_REF]. [START_REF] Lee | Optimal Minimum Wage Policy in Competitive Labor Markets[END_REF] have studied the consequence of the minimum wage in this type of model assuming perfect competition on the labor market. They derive precise conditions on the shape of the rationing scheme on the labor market under which a minimum wage can be a useful complement to taxes in a competitive environment. In particular, they …nd that the minimum wage is useful under the assumption that workers who involuntary lose their job because of the minimum wage are those with the highest opportunity cost of work.

In our paper, we analyze the scope for minimum wages when labor markets are monopson-istic. We consider the standard optimum tax environment of model of optimal taxation with labor supply at the extensive margin. There is a large population of workers who have heterogeneous productivities and opportunity costs of work which are independently distributed in the population. The government is all powerful but is limited by his lack of information on the characteristics of the private agents. Given its preferences for redistribution, it chooses the optimal tax scheme implementing the second best allocation.

We …rst present the model with heterogeneous skills and heterogeneous opportunity costs of work (section 2). Then, we give the de…nition of the usefulness of the minimum wage that we apply to the model (section 3). We recall that this de…nition implies that the minimum wage is useful in the textbook model of the monopsony, which corresponds to the case of a single skill (section 4). The rest of the paper shows that the minimum wage is not useful any more when there are a continuum of skills. To obtain this result, we study the optimal tax scheme when the labor market is monopsonistic instead of perfectly competitive. Section 5 describes the optimal tax schemes when the labor market is perfectly competitive. Section 6 de…nes second best allocations with monopsonistic labor markets. Technically, the contribution of the paper is to adapt the standard principal agent setup where the principal is the government and the agents are the tax payers to a situation where there is a third party, the monopsonist, who sets wages. Compared with the laissez-faire, apart from the allocative distortions (wage and employment are lower than under perfect competition), the monopsonist' pro…ts create a speci…c redistributive issue which we analyze in two stages. First, in section 7, we suppose that the government has the information and power to fully tax pro…ts. We prove that there is a labor tax schedule that implements the second best allocation of the competitive model. Taxing pro…ts and giving employment subsidies yield the optimal allocation. This allows us to show that there is no room for minimum wage. Second, in section 8, we introduce a simple model of monopsonistic competition with free entry to investigate what happens when the taxation of pro…ts is limited by information constraints. We consider an economy with a large number of identical islands, which only di¤er by i.i.d. entry costs. The government implements corporate subsidies (or taxes) on top of the labor tax schedule. Strikingly, the previous result still holds: the tax tools are enough to undo the wrongs of the monopsonist and get the same allocations as in a competitive economy. Accordingly, in our framework, monopsonistic competition does not justify the introduction of a minimum wage. Finally, section 9 provides some concluding comments.

The model

We consider an economy made of a continuum of agents of measure 1. A typical agent is described by a couple of exogenous characteristics, denoted by = (!; ). The …rst component ! denotes her productivity when working full time in market activities, producing an undi¤erentiated desirable commodity. The second component, , is a …xed cost of participating in the labor market, also measured in commodity units. In the economy there are pro…t maximizing …rms that allow the transformation of the agents'labor into commodity, and a benevolent government with a redistributive social aim, who can raise taxes or distribute subsidies and set a minimum wage. The general structure of the economy and the distribution of agents'characteristics are common knowledge.

The labor market works as follows. The government cannot observe the individual characteristics: it only sees whether an agent works or not, and in the former case, the wage paid by her employer. An employer observes the productivities y's of his employees, but not their opportunity costs of work. When she works, the type-(!; ) agent produces a quantity y, at most equal to ! (the opportunity cost of work is …xed : it does not depend on the di¤erence (! y)). When working and producing y, an employee gets a net wage W (y), possibly subject to a minimum wage constraint W (y)

W . The tax schedule, denoted by T (W ) (if negative, the absolute value of T is a subsidy to work), yields a labor cost

C(W ) = W + T (W ).
Production may generate pro…ts. We assume that after tax pro…ts, if any, are dissipated by the owners of the …rms with no contribution to social welfare. Under full information, we consider both the normal case where pro…ts are taxed away in a lump sum fashion and the situation where they are not taxed at all. In section 8 we introduce an information based model of pro…t taxation.

The tax receipts are then used to give a subsistence income r to the unemployed agents.

We assume that ! and are independently distributed. The cumulative distributions of and ! are denoted F ( ) and G(!) respectively. F has support

[ ; ] while G has support [!; !].
We suppose

0 < 1 and 0 ! < ! 1:
F and G have continuous derivatives, denoted by f and g respectively, which are strictly positive everywhere on their support. A part of the analysis carries through with an unrestricted distribution for the couple ( ; !), involving mass points and correlation between the two characteristics:

we shall point out speci…cally when the independence assumption is needed.

The agents have a simple choice criterion, linear in income. They decide to produce an output y rather than stay on the dole whenever their …nancial incentive to work, W (y) r; is larger than their work opportunity cost . Their choice follows from:3 u(W; r; ; !) = max

0 y ! [r; W (y) ]: (1)
Let y(!) be the production of an agent of productivity ! who works. The proportion of agents of productivity ! that are employed is

F [W (y(!)) r].
The preferences of the government are represented by a social welfare function

Z Z (u(W; r; ; !)) dF ( ) dG(!);
where is a non decreasing concave function.

To be feasible, the quadruple (W; T; r; y) must satisfy the budget constraint of the government. When the pro…ts of the …rms are not taxed, the budget constraint takes the form

Z ! ! T fW (y(!))g F [W (y(!)) r] dG(!) = r Z ! ! f[1 F [W (y(!)) r]g dG(!): (2)
The left hand side represents the collected taxes, while the right hand side measures the unemployment bene…ts. When the …rms pro…ts are taxed away, the government collects taxes T and pro…ts y T W on each job, so that the budget constraint becomes:

Z ! ! fy(!) W (y(!))g F [W (y(!)) r] dG(!) = r Z ! ! f[1 F [W (y(!)) r]g dG(!): (3)
The sequence of decisions is such that the government announces its policy, the tax function, the subsistence income and possibly the minimum wage at the beginning of the period, while anticipating the budget constraint. Then the …rms choose the net wage function which relates productivity to net wage. Finally the workers decide on their labor supply.

On taxation and the minimum wage

Through the tax function T; the tax on pro…ts and the subsistence income r, the government has powerful policy tools at his disposal. Is a minimum wage useful in this circumstance? To address this issue we take the most favorable stance toward the minimum wage: we admit that the minimum wage is useful whenever it can replace a non negligible part of the tax schedule.

Let us de…ne the usefulness of a policy instrument when the government has multiple, possibly redundant, instruments at its disposal. Here, the set of instruments is made of open wage intervals [W n ; W n+1 ) with non zero associated tax functions, T n (W ), and a positive minimum wage W : When an instrument is not used, laissez-faire is the benchmark: T (W ) = 0 on the relevant interval or W = 0, keeping the subsistence income r unchanged. We de…ne an instrument as useful if: …rst, it enters a combination of instruments that supports the optimal allocation; second, among all such combinations, there exists at least one from which the instrument cannot be dropped out without reducing welfare. Consider a situation where the optimum allocation is supported by two instruments: a tax function equal to in…nity on [0; W ), and another non zero function T (W ) above W . Suppose that both instruments are useful: the allocation is not implemented with a zero tax on [0; W ): This allocation is also supported by a minimum wage W and the function T (W ) above W . Dropping the minimum wage, as the in…nite tax before, would be welfare reducing. Thus, the minimum wage is useful. 4This de…nition has the following implication:

Proposition 1 Consider an allocation where W 0 is the lower bound of the wage distribution supported by taxes. Then the minimum wage is useful if and only if laissez-faire over the interval [0; W 0 ) does not support the optimum.

Proof : Consider an allocation where W 0 is the lower bound of the wage distribution supported by taxes T (W ). A minimum wage can be substituted for the tax T (W ) over the interval [0; W 0 ):

The question is whether it is useful. There are two cases to consider.

First, suppose that laissez-faire does not support the optimum over the interval [0; W 0 ). This means that either T (W ) > 0 or the minimum wage prevent individuals from working over some parts of [0; W 0 ): Thus, the minimum wage is useful.

Second, suppose that the minimum wage is useful over the interval [0; W 0 ). This means that setting the minimum wage to zero and T (W ) = 0 over [0; W 0 ) induces individuals to work at wages below W 0 : Thus, laissez-faire does not support the optimum over the interval [0; W 0 ):

QED.

This proposition implies that the minimum wage is not useful when the lowest value of productivity of employed workers, ! inf ; is equal to the sum of the subsistence income, r; and the lowest work opportunity cost, : In this case, under laissez-faire over the interval [0; W 0 ), the potential wage of persons of productivity smaller than ! inf is below r + , the minimum income required to participate in the labor market.

With this de…nition we recall in the next section that the minimum wage is useful to correct the ine¢ ciencies associated with the monopsony when there is a single skill. However, the de…nition also implies that there is no need for a minimum wage when skills are heterogeneous.

The case with a single skill

It is worth brie ‡y recalling the justi…cation of the minimum wage in the textbook model of monopsony introduced by [START_REF] Robinson | The Economics of Imperfect Competition[END_REF]. All workers are homogeneous with respect to productivity: there is a single productivity level !: Moreover, taxes and transfers on labor are usually not considered, so that we can set r and T equal to zero for now.

The monopsonist is assumed to face a labor supply curve that relates the wage, W; to the level of employment, equal to F (W ). The monopsonist maximizes his pro…t, knowing the shape of the supply curve, i.e. the quantity

= (! W )F (W ):
This leads to the …rst order condition5

! = W + F (W ) F 0 (W ) . ( 4
)
The left-hand side of this equation is the marginal productivity of labor and the right-hand side is the marginal cost of hiring an extra worker. The marginal cost is higher than the wage W because the employer computes the overall e¤ect of the increase on his wage bill, knowing the labor supply schedule: the derivative of the wage bill W F (W ) with respect to Pro…t maximization yields the same …rst order condition as (4) where ! t is substituted for !.

W is W F 0 (W ) + F (W ),
Accordingly, the employer is induced to choose the competitive wage W = ! and the competitive employment level if t = F (!)=F 0 (!); i.e. the tax is a subsidy. Assume that pro…ts can be taxed away in a lump sum way: this allows the government to …nance the subsidies. Therefore, a complete system of taxes is equivalent to the minimum wage in this model. This is reminiscent of the subsidy proposed by A. Robinson, (Robinson, 1933, p. 163), to lead a monopolist to produce the competitive output.

To summarize, the textbook model of monopsony shows that e¢ ciency can be reached either with the minimum wage or with taxes on pro…ts whose proceeds are used to …nance employment subsidies. In this setup, the minimum wage is useful according to our de…nition. Moreover, it seems easier to use the minimum wage, rather than levying taxes on pro…ts and redistributing the proceeds of these taxes under the form of employment subsidies. In what follows, we show that the minimum wage does not perform so well when there is a diversity of skills.

Second best tax schemes with perfectly competitive labor markets

Before studying imperfect competition, it is useful to recall the properties of optimal taxation and of the second best allocations in a perfectly competitive economy with heterogeneous skills.

A second best optimum is a triple (W; r; y), such that 1. the workers choose whether to work or not, and the amount they produce y(!), taking as given (W; r), according to

max 0 y ! [r; W (y) ]; (5)
2. anticipating the behavior of the agents, the government chooses a tax schedule (W; r) which maximizes the social welfare function:

Z ! ! ( Z W [y(!)] r [W (y(!)) ] dF ( ) + f1 F [W (y(!)) r]g (r)
)

dG(!); (6)
subject to the budget constraint: 6

Z ! ! fy(!) W [y(!)] + rg F [W (y(!)) r] dG(!) = r: (7)
The optima, as de…ned by 1. and 2., are studied in some details in [START_REF] Choné | Optimal Taxation in the Extensive Model[END_REF]. Following the de…nition, second best optima are found as follows. First (5) implies that without loss of generality one can restrict the attention to non decreasing functions W and that workers work at their full productivity. Second, one solves the optimization problem of the government, maximizing (6) with respect to (W; r) subject to the constraint (7) on the set of non decreasing functions W . The tax wedge is then merely the di¤erence between the productivity ! and the net wage W (!):

At the optimum the wage function is uniquely de…ned on an interval [! inf ; !] of productivities, for which there are working agents. It can be given any arbitrary value, at most equal to r + for smaller productivities. We can also show that the lowest productivity among the employees, denoted by ! inf , is at most equal to : 7 Accordingly, ! inf is lower than r + and following proposition 1, the minimum wage is of no use at the competitive equilibrium in our setup.

This would not be necessarily the case when the elasticity of labor demand is …nite as in the contribution of [START_REF] Lee | Optimal Minimum Wage Policy in Competitive Labor Markets[END_REF].

Second best tax schemes with monopsonistic labor markets

We consider now the case where the government faces a large …rm, which is the sole buyer on the labor market. We de…ne second best allocations. Formally, a second best optimum is a 6 Under perfect competition, pro…ts are equal to zero, so that (2) coincides with (3). 7 Let us write the Lagrangian of the program of the government for productivity ! :

Z W r (W )dF ( ) + [1 F (W r)] (r) + [(! W + r)F (W r) r]
where stands for the marginal cost of public funds. Suppose that W (!) = r + for ! 2 ( ; ! inf ]: On this interval, the derivative of the Lagrangian would be

(! W + r)f (W r) = (! )f ( ) > 0:
Therefore, a small increase in W would increase the value of the Lagrangian. Thus ! inf at the optimum.

quadruple (W; T; r; y), such that 1. the workers choose whether to work or not, and the amount they produce y(!), taking as given (W; r), according to

max 0 y ! [r; W (y) ]; (8)
2. the monopsonist chooses the net wage, taking as given (T; r), and anticipating the reactions of the workers to its choice, by maximizing max

Z ! ! [y(!) W (y(!)) T (W (y(!)))] F [W (y(!)) r]dG(!); (9)
3. the government chooses (T; r), anticipating the behavior of the monopsonist and of the workers, maximizing the social welfare function:

Z ! ! ( Z W (y(!)) r (W (y(!)) )dF ( ) + f1 F [W (y(!)) r]g (r)
) dG(!); [START_REF] Dolado | The Role of the Minimum Wage in the Welfare State: An Appraisal[END_REF] subject to the feasibility constraint

Z ! ! fy(!) W (y(!)) + rg F (W (y(!)) r) dG(!) = r; (11)
when pro…ts are taxed, or

Z ! ! fT (W (y(!))) + rg F (W (y(!)) r) dG(!) = r; (12)
when they are not. We assume that the government chooses a continuous and bounded below tax function T:

In order to simplify the resolution of this problem, it is useful to show that one can restrict the analysis to net wages that increase with productivity.

Lemma 1 At a second best optimum, without loss of generality:

1. the monopsonist can choose a net wage function W that is non decreasing with respect to productivity;

2. the government can choose a tax schedule T such that the function x ! x + T (x) is everywhere non decreasing;

3. all the employees work at their full productivity !:

Proof : see appendix.

This lemma shows that any second best allocation can be reached with non decreasing net wage and cost schedules. At a second best optimum individuals work at their full time productivity and the net wage is a non decreasing function of productivity in the competitive environment. These properties also hold when the labor market is dominated by a monopsonist.

Monopsony with full taxation of pro…ts

We consider a monopsony whose pro…ts can be fully taxed by the governement. We prove that the government can bypass the monopsonist and implement the second best allocation of the competitive economy. Then we present two simple examples that illustrate the shapes of the tax schedules.

The optimal tax schedule

The description of the programs of the government (compare 2. in the de…nition of second best optima in section 5 with 3. in the de…nition of second best optima in section 6) makes it clear that, when pro…ts can be fully taxed, the only di¤erence between the competitive and monopsony problems comes from the (possible) restrictions imposed by the behavior of the monopsonist [START_REF] Diamond | Income Taxation with Fixed Hours of Work[END_REF]. As a consequence, the second best optima of the monopsonistic economy cannot Pareto dominate those of the competitive economy. They can at best coincide with them if the government manages to undo the wrongs caused by the monopsonist. We are going to show that this is indeed the case.

The Lagrangian of the program of the government in a competitive economy is

L = Z ! ! ( Z W (!) r (W (!) )) dF ( ) + (r)f1 F [W (!) r]g + f[! W (!) + r]F [W (!) r] rg ) dG(!); ( 13
)
to be maximized over (W (:); ; r), for non decreasing W 's. Let [! inf ; !] be the endogenous set of productivities for which there are a positive number of employees at the optimum. The Lagrangian can be rewritten equivalently as

L = r + (r) + (14) Z ! ! inf ( ! W (!) + r + Z W (!) r (W (!) ) (r) F [W (!) r] dF ( ) ) F [W (!) r] dG(!):
Now, the objectives of the government ( 14) and of the monopsonist ( 9) are aligned provided that to any value W; W > r + ; of the net wage corresponds a value C(W ) = W + T (W ) of the labor cost such that

C(W ) = W r Z W r (W ) (r) F [W r] dF ( ): (15)
Note that C can take any value when wages are smaller than r + since nobody works for such wages. Therefore Theorem 1 The second best optimal allocations in a monopsonistic economy where the pro…ts can be fully taxed are identical to that of a competitive economy. An optimum in the monopsonistic economy can be implemented through a tax wedge T (W ) which satis…es

T (W ) = r c 1 c Z W r c (W ) F [W r c ] dF ( ) (r c ) for W r c + ;
where r c and c are respectively the optimal subsistence income and marginal cost of public funds of the competitive economy.

Theorem 1 states that all allocations that can be reached in a competitive economy can also be reached, with di¤erent tax schedules, when the labor market is monopsonistic. It is a striking result which means that the government can systematically undo the wrongs caused by the monopsonist at no cost. Actually, this is already the case in the textbook example, discussed above, where the government can use either employment subsidies …nanced by taxes on pro…ts or a minimum wage to reach the desired allocation. However, when skills are heterogeneous, the minimum wage is not useful any more. Indeed, since the allocation is the same as in the competitive economy, the lowest productivity of the employees is smaller than the lowest bound of the opportunity costs of work, . This implies that nobody with productivity below ! inf would want to work under laissez-faire, i.e. when T (W ) = 0 for all wages below r c + : Then, Proposition 1 entails that the minimum wage is not useful.

Also it is easily checked that the tax function T is negative for W r c + . Employment subsidies are e¢ cient because they counteract the natural inclination of the monopsonist to reduce its demand for labor 8 .

It should be stressed that the proof of Theorem 1 relies on the independence of the distributions of productivities and work opportunity costs. Indeed, in case of dependence, the argument does not go through: the number of workers, that is equal to F (W (!) r) in equation ( 14), becomes a function F (W (!) rj!) that depends on !: Then, the expression of the cost that aligns the objective of the government and the monopsonist, de…ned in equation [START_REF] Immervoll | Minimum Wages, Minimum Labour Costs and the Tax Treatment of Low-wage Employment[END_REF], has no economic meaning since it depends on the unobserved !.

It would be of interest to know whether Theorem 1 extends to situations where productivity is correlated with work opportunity cost. We do not have a general answer to this question.

However, there is an extreme polar case which is easily dealt with: this is the situation where the work opportunity cost is a continuous increasing function of productivity, say a(!). It can be shown that the …rst best optimum consists in putting to work all individuals of productivity ! greater than or equal to a(!), while distributing welfare equally with a utility level equal to r for everyone where

r = Z ! a(!) [! a(!)]G(!):
The government can implement this optimum in a monopsonistic economy, when the monopsony pro…ts are taxed away. Let C(W ) = W r (compare with [START_REF] Immervoll | Minimum Wages, Minimum Labour Costs and the Tax Treatment of Low-wage Employment[END_REF]). Then the monopsonist pays the workers at the lowest acceptable net wage, W (!) = a(!) + r, and employs all individuals who bring a non negative pro…t, i.e. such that ! C(W (!)) = ! a(!) 0, the same individuals as in the …rst best optimum. 9 Let us now look more precisely at the shape of the second best tax schedules in the monopsonistic model.

The shape of optimal tax schedules: two examples

The tax policy is not the same in the competitive and the monopsonistic case. The properties of the tax schedule in these two cases can be illustrated by looking at two polar assumptions about the objective of the government: …rst an output maximizing government, whose preferences are represented by the social welfare function (x) = x; then a Rawlsian government which maximizes the welfare of the most disadvantaged agents.

Output maximizing government

When the labor market is competitive, the equilibrium without tax and subsistence income, r c = T (W ) = 0, yields a …rst best allocation. It is easy to check, from [START_REF] Guesnerie | Minimum Wage Legislation as a Second-Best Policy[END_REF], that the marginal cost of public funds c is equal to 1. An agent with characteristics (!; ) gets a utility level 9 In the case where labor supply is in…nitely elastic one might think that minimum wages are justi…ed because monopsonistic employers take subsidies in their pocket instead of giving wage increases. Actually, in that case, the monopsonist always sets the net wage at the reservation level a(!) + r, whatever the labor tax or subsidy. Employment subsidies serve to implement the optimal level of employment, and the minimum wage is not needed. Indeed the objectives of the monopsonist and of the government are aligned when the elasticity of labor supply is in…nite as far as the determination of the net wage is concerned.

ω W(ω) = ω C(W(ω)) = ω /2 T(W(ω)) = -ω /2

Entry and limits on corporate taxes

We have so far assumed that pro…ts are entirely taxed away, as is consistent with the fact that the government knows the pro…t level. To put limits to the power of the government to tax …rms while keeping with the spirit of optimal taxation models à la Mirrlees, we introduce additional information asymmetries which allow the …rms to keep some rents. A simple and illustrative way to proceed is to consider a situation where the government regulates a continuum of separate local labor markets. In all these labor markets, there is the same distribution of workers as the one of the previous section: these markets work independently and there is no labor mobility across markets. Firms have to pay an entry cost 10 h; which is drawn independently across labor markets with the c.d.f. H. The government, which observes net wages as before but not the entry costs of the …rms, announces the same tax schedule (T; r) over the whole territory, with additionally a lump sum subsidy s ( s is the level of the tax when s is negative) given to the …rms to help them pay their costs. Given our informational assumption, the subsidy can only be constant, identical across labor markets. The economy works as follows: …rst the government announces the full tax and subsidy schedule common to all markets; second the random entry costs and productivity are drawn; the …rms decide to operate when the sum of their expected pro…ts and subsidy exceeds the entry cost; …nally production is undertaken and wages are paid in the markets which operate; in the other markets, nobody works and everyone gets the subsistence income r.

When labor markets are competitive operating pro…ts are equal to zero under constant returns to scale and …rms decide to operate when s h is non negative. The government program then is

max [T ( );r;s] H(s) Z ! ! ( Z W (!) r (W (!) ) dF ( ) + f1 F [W (!)) r]g (r)
)

dG(!) + [1 H(s)] (r);
subject to the feasibility constraint

H(s) Z ! ! f! W (!) + rg F (W (!) r) dG(!) = r + sH(s):
Let be the multiplier of the feasibility constraint, and for further reference denote (T c ; r c ; s c ; c ) a solution of the above program for the competitive economy.

When the labor markets are monopsonistic, the …rms'operating pro…ts allow them to …nance some of the entry costs and the subsidy may be negative. The before tax operating pro…t of the typical …rm is

= Z ! ! f! W (!) T (W (!))g F (W (!) r) dG(!);
under (T; r). The …rm decides to operate when + s h is non negative, i.e. with probability

H( + s).
The program of the government becomes max

T m (W ) = r c Z W (!) r c (W ) (r c ) c F [W r ] dF ( ):
The pro…t of the monopsonistic …rm follows, and the value of s m is computed from s m = s c m .

This implies that the government can reach the same allocation as in the competitive economy.

It is worth noting that the function T m has the same analytical expression as in Theorem 1, but di¤erent values of the marginal costs of public funds and the subsistence income. Therefore, as discussed in section 7, the government does not need the minimum wage to undo the wrongs of the monopsony even when pro…ts cannot be fully taxed. With the instruments adapted to its information structure, the government has all the necessary …scal tools to reach the second best optimum of the competitive economy without using the minimum wage. It could be worth analyzing the degree of generality of this result.

Conclusion

In this paper we compare income redistribution in two economies which only di¤er by the functioning of their labor markets, competitive or monopsonistic. The government has a large range of instruments at its disposal, which includes wages and pro…ts taxes and the minimum wage. By de…ning the minimum wage as useful whenever it can replace a non negligible part of the tax schedule, we take the view point the most favorable to the minimum wage. Even with this view point, the minimum wage appears to be of no use to correct the transfers or ine¢ ciencies associated with the monopsony when the heterogeneity of skills is accounted for.

This result holds when abilities are distributed independently of work opportunity costs. It is also satis…ed when work opportunity cost is a deterministic increasing function of ability. We do not know how to handle the intermediate cases.

The conclusion that monopsony does not justify the minimum wage does not mean that the minimum wage is useless as a part of e¢ cient redistributive schemes in all circumstances (indeed see [START_REF] Lee | Optimal Minimum Wage Policy in Competitive Labor Markets[END_REF] for a counter example). What we claim here is that in the absence of restrictions on the set of available tax instruments, a monopsony on the labor market can be dealt with without using a minimum wage in a linear technology setup. Whether the minimum wage somehow can be useful in other circumstances is an open question. More research is needed in this area.

Figure 1 :

 1 Figure 1: The textbook model of monopsony

Figure 2 : 0 Figure 3 :

 203 Figure 2: The net wage schedule W (!), the tax schedule T (W (!)); the labor cost schedule C(W (!)) when there is an output maximizing government in a monopsonistic economy with uniform distribution functions.

  dF ( ) + f1 F [W (!)) r]g (r)) dG(!)+ [1 H( + s)] (r);subject to the feasibility constraintH( + s) Z ! ! f! W (!) + rg F (W (!) r) dG(!) = r + ( + s)H( + s);while the monopsonist sets a wage schedule according toW ( ) = arg max S( ) Z ! ! f! S(!) T (S(!))g F (S(!) r) dG(!):Although the pro…t ; which depends on T; shows up in the objective and the feasibility constraint of the government, this does not create di¢ culties since it only appears through the after tax pro…t + s: Indeed put + s = s c in the program of the government: ignoring the behavior of the monopsony the solution of the program is then a competitive optimum (the government manages to tax away all monopsony pro…ts!). This allows us to transpose here the argument of Theorem 1. The objective of the government and of the monopsonist are aligned and yield the competitive net wage W c if one de…nes

See, among others[START_REF] Robinson | The Economics of Imperfect Competition[END_REF],[START_REF] Stigler | The Economics of Minimum Wage Legislation[END_REF],[START_REF] Drazen | Optimal Minimum Wage Legislation[END_REF],[START_REF] Jones | Minimum Wage Legislation in a Dual Labor Market[END_REF],[START_REF] Manning | How do We Know that Real Wages are Too High ?[END_REF]

2003),[START_REF] Rebitzer | The Consequences of Minimum Wage Laws, Some New Theoretical Ideas[END_REF],[START_REF] Bhaskar | Minimum Wages for Ronald McDonald Monopsonies: A Theory of Monopsonistic Competition[END_REF],[START_REF] Masters | Wage posting in two-sided search and the minimum wage[END_REF],[START_REF] Cahuc | The consequences of the minimum wage when other wages are bargained over[END_REF][START_REF] Flinn | Minimum Wage E¤ects on Labor Market Outcomes under Search, Bargaining, and Endogenous Contact Rates[END_REF].[START_REF] Bhaskar | Minimum Wages for Ronald McDonald Monopsonies: A Theory of Monopsonistic Competition[END_REF] The recent paper of[START_REF] Hungerbühler | On the optimality of a minimum wage: New insights from optimal tax theory[END_REF], where the usefulness of the minimum wage is analyzed in a search and matching model, is an exception.

In case of indi¤erence between several maxima, we suppose that the worker chooses the largest production.

From an institutional viewpoint, it may make sense to separate the enforcement of the tax scheme at the bottom of the income distribution, when it presents features of a minimum wage, from the general accounting rules associated with a tax schedule. For instance, in the US, the minimum wage can be enforced through monetary, civil or criminal penalties. Employers who willfully or repeatedly violate the minimum wage requirements are subject to a civil money penalty of up to $1,000 for each violation. Such considerations are absent from our theoretical model.

When the function F is log concave, an assumption which is often made, the logarithm of pro…t is concave so that there is a single maximum characterized by the …rst order condition.

Note that the function C(W ); de…ned in[START_REF] Immervoll | Minimum Wages, Minimum Labour Costs and the Tax Treatment of Low-wage Employment[END_REF], can have decreasing parts. The construction of Lemma 1 allows us to de…ne an equivalent non decreasing cost function C(W ) = min x W C(x). It is easy to see that the associated tax schedule, T; is also negative, as the original function T , for all W > r c + :

0 A positive value of h corresponds to an entry cost; a negative value can be interpreted as a rent of size jhj.

A Appendix: Proof of Lemma 1 1) This is a consequence of the behavior of workers. When confronted with a net wage schedule W , workers'choice of y follows from:

]:

Let W (y) = supfW (z)j0 z yg:

By construction W is non decreasing, the utility levels attained by the agents under W and W are identical, while the labor supply under W is a subset of the labor supply under W . Therefore, the monopsonist can choose a non decreasing net wage schedule without loss of generality.

2) This follows from a study of the behavior of the monopsonist. Consider any bounded below function C, and let

C(x):

De…ne C = fwjC(w) < C(w)g, or equivalently fwj there exists z > w such that C(z) < C(w)g. This set is empty if C is non decreasing, and C coincides with C outside of C.

We show that a monopsonist facing the tax schedule leading to C will never employ a worker at a net wage in C, so that C and C lead to the same allocation.

Let W be a net wage schedule. The monopsony pro…ts are

where y(!) is the production of a worker of productivity ! who faces the net wage schedule W .

Property: Assume that C is a continuous bounded below function on IR + . There is an optimal non decreasing net wage schedule W such that

Proof of the property: Take a W associated with C, which is non decreasing by 1), whose range may have a non empty intersection with C. We modify it into a new function W whose range does not intersect C, while weakly increasing the pro…ts of the monopsonist.

By continuity of C, the set C is made of the union of disjoint intervals, say (w 0 ; w 1 ). One of the two following situations arises: a) either C(z) > C(w 1 ) for all z smaller than w 1 ; b) or there exists w 0 such that C(w 0 ) = C(w 1 ), and C(z) > C(w 1 ) for all z such that w 0 > z > w 1 .

We treat the two cases in turn, supposing that there is some z in the interval and some y such that z = W (y).

a) In the …rst case, let

We modify W for all y y 1 through de…ne:

for C(w 1 ) < y < y 1 :

By construction the new W is non decreasing. It leads to pro…ts at least as large as the original W :

if there are points such that y < C(w 1 ); the pointwise pro…t initially equal to [y C(W (y))]F (W (y)); is negative, but becomes null because nobody works when W (y) + r; when there are points such that C(w 1 ) < y < y 1 ; the pointwise pro…t is initially positive, but is at least as large after the transformation since C(w 1 ) C(W (y)) and F (w 1 ) F (W (y)). The range of the modi…ed W has an empty intersection with [0; w 1 ) as desired.

b) In the second case, let y 0 = supfyjW (y) w 0 g; and y 1 = inffyjW (y) w 1 g:

We modify W on the interval (y 0 ; y 1 ) through W (y) = w 0 for y 0 < y < C(w 1 ) w 1 for C(w 1 ) < y < y 1 :

By construction, the new W is non decreasing. It leads to pro…t sat least as large as the original W : for the y's such that y 0 < y < C(w 1 ), if any, this follows from the fact that the pointwise pro…t [y C(W (y))]F (W (y) r) is negative, associated with the inequalities C(W (y)) > C(w 0 ) and F (w 0 r) F (W (y) r); similarly for the y's such that C(w 1 ) < y < y 1 , the pointwise pro…t is positive and F (w 1 r) F (W (y) r). The range of the modi…ed W has an empty intersection with (w 0 ; w 1 ).

This completes the proof of the Property.


Houssam Elbouanani

Chadi Barakat

Walid Dabbous

Thierry Turletti

Troubleshooting Distributed Network Emulation

Keywords: network emulation, passive delay measurement, network tomography

Distributed network emulators allow users to perform network evaluation by running large-scale virtual networks over a cluster of fewer machines. While they offer accessible testing environments for researchers to evaluate their contributions and for the community to reproduce its results, their use of limited physical network and compute resources can silently and negatively impact the emulation results. In this paper, we present a methodology that uses linear optimization to extract information about the physical infrastructure from emulation-level packet delay measurements, in order to pinpoint the root causes of emulation inaccuracy with minimal hypotheses. We evaluate the precision of our methodology using numerical simulations, then show how its implementation performs in a real network scenario.

I. INTRODUCTION

Distributed network emulation is a relatively recent approach for network experimentation that uses containers and virtual switches to emulate the behaviour of real, physical networks for research and/or education purposes. In particular, it allows users to run a large-scale virtual network over a cluster of fewer machines, each running a subset of the virtual machines, and which are connected using overlay networking technologies. Mininet [START_REF] Lantz | A network in a laptop: rapid prototyping for software-defined networks[END_REF] and its forks (Mininet CE [1], Maxinet [START_REF] Wette | Maxinet: Distributed emulation of software-defined networks[END_REF], and Distrinet [START_REF] Di | Distrinet: A mininet implementation for the cloud[END_REF]) implement this network emulation approach with a focus on accessibility and flexibility by providing users with a simple-to-use Python API.

A direct challenge of network emulation is resource contention: running multiple virtual components over fewer machines leads to concurrency in using the available physical resources. This aspect of network emulation has been extensively researched in previous studies, e.g., [START_REF] Muelas | Assessing the limits of mininet-based environments for network experimentation[END_REF], [START_REF] Ortiz | Evaluation of performance and scalability of mininet in scenarios with large data centers[END_REF]. In its extreme cases, this may lead to emulated packets getting scheduled for transmission later than normal when the packet rates exceed the speed of the hardware CPUs, or to virtual links getting throughputs lower than normal when the total packet rates exceed the capacity of the underlying network. In general, the underlying physical infrastructure adds delay to emulated packets which might lower emulation quality, in a way that tends to be silent and can bias the results unless a careful analysis is carried out.

To measure this delay, the authors in [START_REF] Elbouanani | Passive delay measurement for fidelity monitoring of distributed network emulation[END_REF] have implemented a methodology that passively monitors the network delay of emulated packets to gauge its increase by the physical infrastructure, ultimately in order to detect eventual occurrences of contention failures. In this paper we use this passive delay measurement tool to infer information about the underlying infrastructure. Such information can be useful for troubleshooting purposes, i.e., to identify which resource -particularly network links-has not had enough available capacities to correctly host the emulated network, and have thus contributed to stretching the network delay of emulated packets. In particular, we propose a network tomography [START_REF] Mark | Network tomography for internal delay estimation[END_REF], [START_REF] He | Network Tomography: Identifiability, Measurement Design, and Network State Inference[END_REF] algorithm1 to infer the network delay of the infrastructure components from the delay measurements passively collected by Mininet or its distributed variants. Indeed, distributed network emulators are mainly designed to run on shared infrastructures (grids and clouds), which can be virtual, and whose topology the user might know but cannot directly access or measure. These main assumptions define the crux of the problem. Using carefully tailored heuristics, our algorithm performs relatively well even in settings where the user's emulation scenario does not provide enough measurements to infer infrastructure delay.

Our troubleshooting methodology is heavily inspired from previous works on delay tomography, whose objective is inferring delays of internal links from end-to-end delay measurements. This problem has been formulated in [START_REF] Kakkavas | A review of advanced algebraic approaches enabling network tomography for future network infrastructures[END_REF], [START_REF] Ni | Network tomography based on additive metrics[END_REF] and while it was historically solved using active measurementbased methods, more recent attempts have instead focused on internal delay inference from passive measurements. In [START_REF] He | Robust monitor placement for network tomography in dynamic networks[END_REF] for instance, the authors have focused on monitoring optimisation: solving for the minimum set of vantage end-points in a network from which a statistically accurate estimation of the internal links' delay distributions can be achieved. A later study [START_REF] Rahali | Tom: a self-trained tomography solution for overlay networks monitoring[END_REF] assumed the impossibility of completely inferring the internal (physical) delays of a network infrastructure from the measurements collected at overlay virtual networks, and proposed to train a neural network from simulated traffic to fill in the missing information. This paper deals with similar assumptions in a context of network emulation, where emulated traffic can be very diverse and too short-lived to be learned by a model. Instead we propose optimisation heuristics to solve it.

The remainder of this paper is organised as follows: the next section presents the problem in more details. We particularly argue our choice of hypotheses and present our modeling framework. Section III describes our delay tomography algorithm along its implementation using existing tools, which we then evaluate in Section IV. Finally, Section V concludes the paper with a summary and a discussion of possible future work in this direction.

II. PROBLEM STATEMENT

The objective in this paper is troubleshooting emulation failures by inferring physical infrastructure load from network measurements collected at the virtual level. The main idea is to determine if there is any unexpected load in the virtual network, evidenced by higher packet delays, and identify which elements of the underlying infrastructure are responsible for it. As any underlying hardware (links and/or machines) can add undesirable network delay to packets proportional to its load, we can extract load information from the passively measured delay of emulated packets. In this section, we describe the problem in more details by presenting our working hypotheses, our mathematical modeling, and by discussing raised challenges.

A. Hypotheses

Consider for example the simple scenario in Figure 1: a virtual network (consisting of a virtual client and a virtual server connected to a virtual switch) is emulated on top of a physical network of three hosts H 1 , H 2 , and H 3 connected by a switch S. The virtual server sends a flow of packets to the virtual client. Using traffic control tools, the virtual links v 1 and v 2 are configured by the user to shape the traffic according to the scenario they wish to emulate: limiting link bandwidth, adding propagation delay, introducing packet loss, etc. Given these traffic shaping parameters, each packet P should experience a certain normal delay d(P ) depending on its size, its position in the virtual links' queues, etc. As this packet moves over the virtual network, the links L 1 , L 2 , and L 3 of the physical network that are crossed by the packet will also add a certain error delay ϵ(P ) depending on the packet itself and on the current load of the infrastructure. When this error delay exceeds some tolerance value, it will negatively impact the results of the emulation. Unfortunately, the user does not have full control over the physical infrastructure to monitor the delay in all network nodes and links. However, using the measurement tool designed by the authors in [START_REF] Elbouanani | Passive delay measurement for fidelity monitoring of distributed network emulation[END_REF], the user can monitor their own emulated network delays, and can easily get information about error delays ϵ and use them to infer infrastructure delays.

In our example, a packet P crossing the virtual link v 1 will experience a total measurable delay d(P ) = d(P ) + d 1 (P ) + d 2 (P ), where d(P ) is the normal emulation delay2 , d i (P ) is the error delay introduced by physical link L i to the packet P . Likewise, a packet Q crossing the virtual link v 2 will experience a delay

d(Q) = d(Q) + d 2 (Q) + d 3 (Q).
The total error delays ϵ(P ), ϵ(Q) experienced by packets P and Q respectively can be written as:

ϵ(P ) = d 1 (P ) + d 2 (P ) and ϵ(Q) = d 2 (Q) + d 3 (Q).
It follows that information about the delays experienced by the packet on each underlying infrastructure link is embedded in the measured delay of packets in the virtual network. However, it is impossible to extract that information by analysing each packet individually. Instead, we can resort to a statistical approach that analyses infrastructure link delays d i on finite time intervals, and that examines a large number of packets from different emulated links (i.e., that pass over different infrastructure paths). Given some prior information on the mapping of the virtual network onto the infrastructure, statistics on the link delays of the infrastructure can thus be inferred. In our scenario for example, if we define x i (T ) as the average delay on link L i during a certain time interval T ∈ T , and ϵ j (T ) as the mean delay error of all sampled packets during T , we have:

x 1 (T ) + x 2 (T ) = ϵ 1 (T ) x 2 (T ) + x 3 (T ) = ϵ 2 (T )
In the general case, to each physical link L i corresponds a sequence of variables (x i (T )) T ∈T , and to each virtual link3 v j corresponds a sequence of mean delay errors (ϵ j (T )) T ∈T . According to how virtual links map to the infrastructure network, infrastructure and virtual links can then be related by linear equations of the form:

i a i,j (T ) • x i (T ) = ϵ j (T ), (1)
where a i,j (T ) is a binary value equal to 1 if virtual link v j crosses physical link L i and 0 otherwise. The above set of linear equations can be further rewritten into a more compact form:

A(T ) • X(T ) = b(T ), (2)
where A(T ) is defined as the embedding matrix whose coefficients are (a i,j (T )), X(T ) is a vector of variables (x i (T )),

and b(T ) is a vector of collected delay errors (ϵ j (T )). For instance, the example networks above are described by the embedding matrix;

A = 1 1 0 0 1 1
Our problem then translates into solving the set of equations in (2) under the following three main hypotheses:

• the underlying topology and the embedding of the emulated network are known, but the total load on the different links of the infrastructure is unknown and cannot be directly measured; • through sampled passive delay measurement of emulated packets, we are given broad information about the added error delays, as well as the timestamps of packets to be able to assign them to time intervals T ; and • over time intervals of finite length, packets from different virtual links crossing the same infrastructure link experience more or less the same delay distribution. The first hypothesis essentially implies that the user knows how the nodes of the infrastructure are connected, but does not know their loads at all time instants, and cannot access them for direct monitoring. This hypothesis is the default scheme in shared infrastructures such as grids and clouds, where static information (topology, component characteristics, etc.) can be provided but the user cannot directly access networking nodes and/or measure dynamic information (load, delay, packet loss) as it is impacted by other users of the infrastructure.

The second hypothesis defines our source of data: the user has complete control of her emulation scenario and can implement a monitoring tool to passively measure the delays of emulated packets. Such tools essentially intercept a subset of the emulated packets (based on a preconfigured sampling rate) and use information available to the emulator (queue lengths, virtual link speed, etc.) to infer normal delays. The last hypothesis is to ensure that different emulated packets experience the same infrastructure network conditions when they pass by the same infrastructure link even if they are from different virtual links. In practice, this holds in all distributed network emulators forked from Mininet, independently of the emulated scenario, as they use typical tunneling protocols, e.g., Generic Routing Encapsulation (GRE) and Virtual Extensible LAN (VXLAN) to create virtual Ethernet links on top of an infrastructure network. Thus, neither differentiated treatment of virtual links nor QoS mechanisms are used.

B. Challenges

1) Time synchronization: Being an explicit measure of time, network delay measurement inevitably requires some degree of time synchronization. Previous works like [START_REF] Elbouanani | Passive delay measurement for fidelity monitoring of distributed network emulation[END_REF] have discussed these limitations in passive delay measurement, and have demonstrated that in a geographically localised network, it is possible to achieve as few as 100 nanoseconds of clock drift using only regular time synchronization protocols without specialised hardware. In cases where this cannot be achieved, these works propose to measure the joint round-trip delay d(P, Q) of pairs of packets (P, Q) instead of their individual one-way delays d(P ) and d(Q). Whether we consider individual one-way delays or joint round-trip delays, our above model does not change: if ϵ j are measures of mean roundtrip delays on virtual links, then x i will also be measures of round-trip underlay link delays.

2) Time decomposition: In the previous subsection we have stated that infrastructure link delays x i can be approximated by considering the mean absolute error of emulated packet delays on a certain virtual link at a certain time interval. The quality of such approximation heavily depends on the number of collected packets and the length of the time interval. The former can be improved by collecting packets using a higher sampling rate, but the latter requires a compromise: longer time intervals will contain more values but will challenge the assumption that the physical link delay distribution is stationary.

3) Problem dimension: The set of equations (2) have unique solutions x i (T ) only if there are enough virtual links that cross the diverse set of infrastructure links, i.e., when the embedding matrices have more linearly independent rows than columns. In such cases, a solution can directly be obtained by discarding extra rows (those which are linear combinations of other rows), and inverting the embedding matrix:

X(T ) = A -1 (T ) • b(T ).
However, one must be cautious of potential noise added to the measurements b(T ), which is due to the inevitable lack of precision of any tool used to passively measure the delay. This noise can be large enough to cause negative solutions to the equations, which would correspond to negative values of infrastructure delay. Nonetheless, an invertible matrix can help control such errors: if instead of precise measurements b(T ) the user provides approximations b(T ), then they can only hope to get an approximate solution X(T ) but which can be as close to the real solution as necessary, provided the measurements are precise enough. Indeed, it follows from the continuity of the matrix A -1 (T ) that:

∀ ε > 0, ∃ δ > 0, ∥ b -b∥ < δ ⇒ ∥ X -X∥ < ε .
In the general case however, we cannot assume to have an easily invertible embedding matrix. In the previous example (Figure 1), the system of equations in (1) transforms into 2 equations (corresponding to 2 virtual links) and 3 variables (corresponding to 3 physical links), or equivalently to a noninvertible matrix, which cannot yield a unique solution. The following section aims at working around all these constraints by solving the problem suboptimally with the minimum possible error.

III. TROUBLESHOOTING ALGORITHM

A. Methodology

Considering all discussed challenges, a resolution methodology necessarily requires controlling measurement imprecision and circumventing underdimensioned matrices. To deal with the former, we add a vector ε(T ) of artificial variables ε j (T ) that represent estimation and approximation errors for measurements on virtual links v j . The system then has the form

A(T ) • X(T ) = b(T ) + ε(T ) . (3)
While this mitigates measurement errors, it adds more unknown variables to an already underdimensioned problem. In practice, measurements tools designed for network emulation are implemented with high precision as an important specification, to thoroughly reduce these errors 4 . This observation can help us control those measurement errors ε j (T ) by assigning them the smallest possible values in order to have a solvable set of equations. That being said, our resolution methodology will operate in two steps. First, starting from an incomplete formulation and noisy measurements, we look for the smallest error vector ε(T ) to be accounted for to obtain a solvable system. The output of this step is a set of values for the ε j (T ) vector that allow the system to be solved. In concrete terms, we first solve the convex optimization problem:

minimize X,ε ∥ε(T )∥ 2 subject to A(T ) • X(T ) = b(T ) + ε(T ) (4) X(T ) ≥ 0 .
Solving this convex optimization problem yields one solution with values for variables ε * j (T ) as well as the variables of interest x i (T ) (i.e., infrastructure link delays). However in this first step we are only interested in the solvability of the system and not in its entire resolution. In the case of Figure 1 for example, we would be dealing with a linear system of equations of dimension two and three unknowns, after measurements are corrected with ε * (T ) values.

The objective of the second step of our algorithm is to reduce the set of possible solutions, and to select one of them based on a certain heuristic. One way to achieve this is, again taking inspiration from convex optimization, to choose the solution that minimizes an objective function f :

minimize X f (X(T )) subject to A(T ) • X(T ) = b(T ) + ε * (T ) (5) X(T ) ≥ 0 .
Next, we present two heuristics with incremental complexity and comment on their signification.

1) Heuristic 1: This formulation is based on the observation that the probability that a large number of infrastructure links exhibit high delay is relatively low. Indeed, in a complex physical network, only a small subset of links -generally those with the lowest capacities and/or that transport the most traffic volumes-can be overloaded at the same time. This means that among all solutions, we will select those that describe a situation where the least number of overloaded infrastructure links are the cause of delay emulation errors in the virtual network.

To achieve this, we first need to define a threshold delay value θ, above which an infrastructure link should be considered overloaded. The choice of such a threshold clearly depends on the situation at hand, but in general this should be in the order of few milliseconds 5 . We then define our function f as the number of x i values that exceed the threshold θ, i.e.,

f (x 1 , ..., x n ) = i 1(x i > θ) .
This formulation does not involve a convex function, but it can be rewritten into an equivalent form by adding new binary variables z i , where z i = 1 if and only if x i > θ. We can write:

f (x 1 , ..., x n ) = i z i .
We then add new constraints that link variables z i and x i together: θ -

x i ≤ M • (1 -z i ) and x i -θ ≤ M • z i ,
where M is a very large constant. The problem is then formulated as:

minimize X,Z i z i (T ) subject to A(T ) • X(T ) = b(T ) + ε * (T ) X(T ) ≥ 0 θ -x i (T ) ≤ M (1 -z i (T )), ∀i x i (T ) -θ ≤ M z i (T ), ∀i .
While this effectively implements the described strategy, its main drawback is its computational difficulty. No algorithm to solve such a linear program in polynomial time exists, and thus the system can be computationally intractable for relatively large networks. An easier and more straightforward variant eliminates the z i variables and minimizes instead the total physical delay:

f (x 1 , ..., x n ) = i x i .
This behaves similarly, but not always exactly, to the previous objective function but is continuous and does not involve integer variables:

minimize X i x i (T ) subject to A(T ) • X(T ) = b(T ) + ε * (T ) (6) X(T ) ≥ 0 .
2) Heuristic 2: The above heuristic reduces the set of solutions by choosing those that have a certain special property, i.e., those that minimize the set of infrastructure links causing the emulation delay anomaly. However, in some cases, this may not be enough to select a good solution. One can find cases (see our evaluation setup in Section IV) where two or more infrastructure links always appear together in the embedding of virtual links, which translates to a clique of variables x i that either appear together or not at all in all equations. In such cases more information is needed to discriminate between the x i variables and select a good candidate for a solution. Such information can be accounted for in the form of coefficients α i ∈ R for each link L i , leading to an objective function of the form:

f (x 1 , ..., x n ) = i α i x i ,
such that for any two links L i and L j , we have α i > α j if link L j is more likely to cause delay emulation error than link L i . If direct information about the infrastructure links can be obtained (static characteristics such as type, length, or bandwidth, or dynamic information about the traffic such as load and queue backlog), the values of the α i coefficients can be chosen to reflect this information. In the case this information is not available (lack of control on the infrastructure by the emulator), one can draw data from the history of the links: if a physical link has consistently been the cause of delay emulation error in previous time intervals S ∈ T (as concluded by the heuristic itself), then its coefficient α i (T ) at the current time interval T can be lowered to reflect this fact.

An example implementation of this observation is by assigning the values α i (T ) as inverse (log-)probabilities of overload of links L i , estimated from previous time intervals:

α i (T ) = -log S∈T ,S<T 1{x i (S) > θ} |{S ∈ T , S < T }| .
The following algorithm summarises our methodology for estimating the delay of infrastructure links with either of the two heuristics presented above.

Algorithm 1 Physical delay inference methodology

α i ← 1 for t ∈ T do
Solve Convex Program (4) and get values for ε * Solve Linear Program (5) Update coefficients α i end for

B. Numerical simulations

The objective of this preliminary series of simulations is to evaluate our delay inference methodology and to compare the performances of the proposed heuristics.

We consider for our simulations an abstraction of the physical network shown in Figure 2. This network is designed as a 4-ary fat tree topology typically used in data centers. The end servers are simulated to host a certain number of virtual nodes and links. In particular, a number of virtual links are hosted between randomly selected pairs of end servers. Then, a Markovian network traffic of random rate is simulated asynchronously on each of these virtual links. We timestamp each packet at both ends of the virtual link on which it is simulated, but also on both ends of each physical link it crosses. Finally, the first set of measurements (at the virtual level) is fed to our algorithm to infer the underlying physical delays at specific time intervals (of 10 ms), which are then compared to ground truth on the delay obtained from the second set of measurements (at the infrastructure level). The experiment is designed to last an average of 100 s.

The results are shown in Figure 3. Each dot represents the mean measured delay (x-axis) and estimated delay (y-axis) on a certain physical link for a certain time interval. We can see how well our algorithm performs overall, and how Heuristic 2 behaves relatively well (less underestimated values) compared to Heuristic 1. Knowing that the embedding matrices A(T ) in more than 90% of all time intervals had ranks6 less than half their number of columns, the results are an average error over all links and all time intervals of 2.50 ms (resp. 1.63 ms) between measured and estimated values for Heuristic 1 (resp. Heuristic 2). With the precision of an estimation algorithm defined as the fraction of links that are correctly identified as overloaded (with a tolerance threshold value of 10 ms), our methodology achieves an average precision of 81.5% with Heuristic 1, and 86.2% with Heuristic 2 over all time intervals. The measurements clustered in a vertical line at (x = 8.10 -4 s, y > x) correspond to time intervals when one of the core links had normal delay but was mistakenly designated as faulty by our algorithm. Indeed, our heuristics are designed to minimize the total delay in the infrastructure network (or a weighted sum over all links for Heuristic 2), and thus will tend to assume high delays in links that are part of multiple paths (in this case, core links). Nonetheless, this constitutes less than 10% of all measurements in this scenario.

C. Implementation

In real distributed emulators, our troubleshooting algorithm can be implemented by building on top of the delay mea-Fig. 3: Scatterplot of measured delays (x-axis) vs. estimated delays (y-axis) using Heuristic 1 (left) and Heuristic 2 (right). Each dot shows the measured and estimated delay of a certain link (colour) during a certain time interval. surement tool designed in [START_REF] Elbouanani | Passive delay measurement for fidelity monitoring of distributed network emulation[END_REF]. This tool allows the user to passively monitor the link-level delay of network packets in virtual and/or physical networks, by plugging an Extended Berkeley Packet Filter (eBPF) [START_REF] Vieira | Fast packet processing with ebpf and xdp: Concepts, code, challenges, and applications[END_REF] program into both ends of each link. This lightweight program is a set of instructions added to the traffic control subsystem to log relevant information (packet hash, timestamp, size of queue and head-of-line packet at arrival) about all intercepted packets in persistent files, which are later parsed and analysed offline for delay measurement. However, this tool, when used in virtual links set up by the emulator, measures the link-level delay of emulated packets, which does not directly inform about the underlying infrastructure delay. In the example in Figure 1, by plugging the eBPF code on both ends of virtual link v 1 , we can measure the delay d(P ) of every packet P , which is the sum of its emulated delay d(P ) and the physical (error) delay ϵ(P ). Thus, we modify the program to also log the emulated delay d(P ) in order to evaluate the physical delay.

In short, our algorithm can be implemented as:

• packet loggers: eBPF code pluggable into the traffic control (Linux TC) subsystem of emulated links, which intercepts emulated packets and logs in files raw information about their transmission and reception (timestamps, packet hashes, emulated delay, etc.). As explained in [START_REF] Elbouanani | Passive delay measurement for fidelity monitoring of distributed network emulation[END_REF], eBPF performs this task in a low-overhead manner, as it does not add more than a microsecond of delay to intercepted packets; and • an offline analyser which gathers all logged information to estimate measured infrastructure delays. As it uses the same design logic as the delay measurement tool presented in [START_REF] Elbouanani | Passive delay measurement for fidelity monitoring of distributed network emulation[END_REF], the interception and logging of packets does not decrease the performance of the virtual network. The authors show that it only adds sub-microsecond delay to each intercepted packet. However, the information logging can be heavy in terms of storage. Nonetheless, as intercepting each and every packet is not necessary, using a sampling strategy (e.g. random packet sampling with a rate of 10%) reduces this overhead without decreasing the overall performance of our troubleshooting algorithm.

IV. EXPERIMENTAL EVALUATION

A. Testbed

We consider the network scenario described in Figure 4. In this scenario, 40 clients (vc 1 , vc 2 , ..., vc 40 ) are synchronously downloading a 100 MB file from a random server (vs 1 , vs 2 , ..., vs 5 ) located on the same Ethernet segment. All clients are connected to the central switch by links of 100 Mbps bandwidth and 1 ms delay; the servers are connected by links with no traffic control, i.e., without limitation of bandwidth and practically without delay. The experiment is run using Distrinet [START_REF] Di | Distrinet: A mininet implementation for the cloud[END_REF], and is embedded on an private cloud infrastructure composed of four hosting machines connected with two switches as shown in Figure 4. Each machine runs an Ubuntu 18.04 Linux distribution with a 4.15.0 kernel, using a CPU Intel Core i7-2600 processor and 8 GB of RAM. Furthermore, the embedding algorithm used is configured in a way that all emulated file servers and the virtual switch are hosted in the same machine (host H 1 ); the emulated clients in their turn are distributed fairly over the four other machines.

Throughout the duration of the experiment, we collect passive measurements of emulated packet delays (with a random sampling of 10%), from which we extract the error delays added by the infrastructure network components. We use our methodology described earlier to infer the load on the infrastructure which we interpret and discuss in light of the conclusions made from a more situational analysis.

B. Results

Figure 5 summarizes our results. The figure shows the evolution during the experiment time of the host throughput and the virtual link delay error. We first note how the clients experience different throughput values depending on whether they are hosted in H 1 and H 2 (mean throughput around 90 Mbps and 85 Mbps respectively), or H 3 and H 4 (mean throughput around 42 Mbps) (Figure 5a), even though all clients are designed in the emulated experiment with equal bandwidths of 100 Mbps. This is also evident from the delay emulation errors: virtual links for clients in hosts H 3 and H 4 experience higher delay emulation error (Figure 5b).

These absolute error values, which correspond to the delays added by the underlying infrastructure, are then fed to our estimation algorithm. Given the size of the downloaded file and the achieved throughput, each experiment lasts approximately 20 seconds in total, which are divided into T intervals of 100 ms each. Figure 6 shows the inferred delays for each link of the infrastructure. With a tolerance threshold of 1 ms, we can conclude that links H 1 -S 1 and S 1 -S 2 are the main causes behind the emulation inaccuracy. However, this conclusion depends on which heuristic is used: while the results of Heuristic 2 show that link S 1 -S 2 adds the largest delay throughout the entirety of the experiment, Heuristic 1 switches from S 1 -S 2 to H 1 -S 1 mid-run. We discuss this difference in the next subsection, and explain why Heuristic 2 better reflects the reality in our particular scenario.

C. Discussion

For each time interval, our algorithm solves a linear program modeling the virtual-to-infrastructure embedding and taking into account the measured emulation delay errors. The solution to this linear program consists of an estimation of the infrastructure link delays during the considered time interval. The form of this linear program depends on the set of available measurements. In particular, during the first half of the experiment, as all virtual links are active, the linear program is written as: minimize α 1 x 1 + α 2 x 2 +α 3 x 3 + α 4 x 4 +α 5 x 5 subject to x 1 + x 2 = M AE 1

x 1 +x 3 + x 4 = M AE 2

x 1 +x 3 +x 5 = M AE 3 .

Once clients in H 1 and H 2 finish downloading the file, traffic stops on their links, and so variable x 2 and Equation (2) are no longer part of the program: minimize α 1 x 1 + α 3 x 3 +α 4 x 4 + α 5 x 5 [START_REF] Kakkavas | A review of advanced algebraic approaches enabling network tomography for future network infrastructures[END_REF] subject to x 1 + x 3 +x 4 = M AE 2 (8)

x 1 + x 3 + x 5 = M AE 3 . (9)
In this new formulation, variables x 1 and x 3 essentially play the same role if α 1 = α 3 as with the case of Heuristic 1 (where all coefficients α i are equal to 1). Thus, any solution (x 1 , x 2 , x 4 , x 5 ) is valid for Heuristic 1 as long as x 1 + x 3 = c for some constant c. However, using Heuristic 2, coefficients α i are dynamically chosen based on the solutions in previous time intervals. And as link S 1 -S 2 is more often designated faulty at the first half of the experiment, we have α 3 < α 1 . Under these circumstances, variable x 3 is preferred, which makes S 1 -S 2 more likely to be designated faulty in the second half of the experiment as well, consistent with the fact that the link is purposely underdimensioned.

V. CONCLUSION

Network emulation requires delicate fidelity monitoring to assess the accuracy of obtained results and avoid incorrect conclusions. But once the failure is acknowledged, an important next step is to troubleshoot the potential root causes and identify which parts of the infrastructure could not handle the emulation load. In this paper, we have presented a methodology inspired by past studies on network tomography, that uses passive measurements collected in an overlay emulated network to infer the delay of the underlay infrastructure network. This methodology models the two networks and the embedding of the former over the latter as a linear optimization problem, whose solution tries to capture the information on the delay values in each component of the underlay network. While we have shown that this modeling can yield good results with fair precision, some of its aspects can be further developed: the choice of the objective function (see Section III) and how to dynamically update its coefficients, for instance, can be improved to better quantify the likelihood of each component being faulty. Additionally, our troubleshooting algorithm only aims to perform root cause analysis of the underlying network, but does not offer solutions to overcome possible failures. Such a solution can be a better embedding of the emulated network, or a better routing policy. These aspects are to be developed in future work.

Fig. 1 :

 1 Fig. 1: Emulated and infrastructure topologies.

Fig. 2 :

 2 Fig. 2: Graph representation of a 4-ary fat tree topology. The central vertices represent the cores switches, which connect 4 pods of aggregate and edge switches; the end servers are represented by the vertices of degree 1.

Fig. 4 :

 4 Fig. 4: Emulated network (red) and underlying cluster network.

  (a) Application-level throughput achieved by each emulated client: clients hosted in H1 in blue; clients hosted in H2 in red; clients hosted in H3 in green; and clients hosted in H4 in magenta.(b) Mean Absolute Errors of virtual links emulated in H1 (blue), between H1 and H2 (red), between H1 and H3 (green), and between H1 and H4 (magenta).

Fig. 5 :

 5 Fig. 5: High-level (a) and low-level (b) evidence of emulation inaccuracy caused by infrastructure overload.

Fig. 6 :

 6 Fig. 6: Network delay of each link of the infrastructure estimated using Heuristic 1 (left) and Heuristic 2 (right).

The source code of the algorithm's implementation, as well as instructions to reproduce all the results in this paper are available at https://github.com/ distrinet-hifi/tshoot.

An emulated network can be congested due to a surge in emulated traffic. The delay of its packets d(P ) remains normal as long as the physical infrastructure does not interfere with the emulation.

Without loss of generality, virtual links that cross the same path of infrastructure links can be aggregated into a single virtual link. The measurements from these virtual links are combined into one homogeneous set.

The precision of the measurement tool depends on its design and implementation. In this paper we use the tool from[START_REF] Elbouanani | Passive delay measurement for fidelity monitoring of distributed network emulation[END_REF] which is guaranteed to achieve a precision of a few hundred nanoseconds.

We know from queuing theory that in practice, an overloaded link with a finite size will result in high loss rate, which translates to infinite delay. Thus the actual value of such threshold should not be of large concern.

The rank of a matrix or of a linear system is defined as the number of linearly independent rows or equations.

ACKNOWLEDGEMENT

This work was carried out with the support of the SLICES-SC project, funded by the European Union's Horizon 2020 programme (grant 101008468). This work has received partial funding from the Fed4FIRE+ project under grant agreement No 732638 from the Horizon 2020 Research and Innovation Programme.