B Bonnard

M Chyba

J Rouot

D Takagi

A Numerical Approach to the Optimal Control and Efficiency of the Copepod Swimmer

This article presents a geometric and numerical approach to compute the optimal swimming strokes of a larval copepod. A simplified model of locomotion at low Reynolds number is analyzed in the framework of Sub-Riemannian geometry. Both normal and abnormal geodesics are considered along which the mechanical power dissipated by the swimmer is conserved. Numerical simulations show that, among various periodic strokes, a normal stroke consisting of a simple loop shape is maximizing the efficiency.

I. INTRODUCTION

Swimming microorganisms employ a variety of mechanisms of propulsion, and they have inspired numerous models starting with undulating sheets and filaments introduced in the fifties [START_REF] Gray | The propulsion of sea-urchin spermatozoa[END_REF], [START_REF] Taylor | Analysis of the swimming of microscopic organisms[END_REF]. Recent studies have explored optimal strategies for swimming with minimal amount of mechanical work, an important criterion for assessing the fitness of different organisms and for designing efficient robotic swimmers [START_REF] Lauga | The hydrodynamics of swimming microorganisms[END_REF]. Previous studies have computed optimal solutions in the framework of variational analysis or optimal control [START_REF] Alouges | Optimal strokes for low Reynolds number swimmers: an example[END_REF], [START_REF] Becker | On self-propulsion of micromachines at low Reynolds number: Purcell's three-link swimmer[END_REF], [START_REF] Bettiol | The Purcell Three-link swimmer: some geometric and numerical aspects related to periodic optimal controls[END_REF], [START_REF] Tam | Optimal Stroke Patterns for Purcell Three-Link Swimmer[END_REF].

Recently a new model was developed to mimic the locomotion of larval copepods, an abundant type of zooplankton thriving in the ocean [START_REF] Lenz | Choreographed swimming of copepod nauplii[END_REF], [START_REF] Takagi | Swimming with stiff legs at low Reynolds number[END_REF]. The simplest form of the model, hereafter referred to as the copepod swimmer, is a symmetric body consisting of two pairs of legs, with the pairs making respectively an angle θ 1 and θ 2 with respect to the displacement direction Ox (see Fig. 1).

x(t)

x θ 1 (t) bernard.bonnard@u-bourgogne.fr, jeremy.rouot@inria.fr

θ 1 (t) l l θ 2 (t) θ 2 (t) θ = π θ = 0
The swimming velocity is given by [START_REF] Takagi | Swimming with stiff legs at low Reynolds number[END_REF] ẋ = θ1 sin θ 1 + θ2 sin θ 2 2 + sin 2 θ 1 + sin 2 θ 2 [START_REF] Alouges | Self-propulsion of slender microswimmers by curvature control: N-link swimmers[END_REF] and the controls are the angular velocities

θ1 = u 1 , θ2 = u 2 . ( 2
)
We also have the state constraints θ i ∈ [0, π], i = 1, 2, and

θ 1 ≤ θ 2 .
The true cost corresponding to the mechanical energy of the system is given by the quadratic form qt M q where q = (x, θ 1 , θ 2 ) and

M =   2 -1 2 (cos 2 θ 1 + cos 2 θ 2 ) -1 2 sin θ 1 -1 2 sin θ 2 -1 2 sin θ 1 1 3 0 -1 2 sin θ 2 0 1 3   Using (1)
, the optimization problem is equivalent to minimizing the quadratic cost

T 0 a(q)u 2 1 + 2b(q)u 1 u 2 + c(q)u 2 2 dt (3)
with

a = 1 3 - sin 2 θ1 2(2+sin 2 θ1+sin 2 θ2) , b = - sin θ1 sin θ2 2(2+sin 2 θ1+sin 2 θ2) , c = 1 3 - sin 2 θ2
2(2+sin 2 θ1+sin 2 θ2) . This copepod swimmer serves as a suitable model for computing optimal controls in the framework of sub-Riemannian (SR) geometry. The system is three-dimensional (two shape variables and one displacement variable), which is arguably simpler than the five-dimensional system (two shape variables and three displacement variables) of the previously studied Purcell swimmer where the expression of the control fields is complicated (see [START_REF] Passov | Supplementary notes to: Dynamics of Purcell's three-link microswimmer with a passive elastic tail[END_REF]). It is a global model of SR-geometry which can be analyzed in detail, illustrating in particular the role of normal and abnormal geodesics in the motion. In addition, the optimal controls could be compared with observations of copepods to determine whether they are optimizing their strokes to minimize mechanical energy. Copepods must swim in order to find food and escape from predators, and they have had a chance to adapt and evolve over millions of years, but it remains unknown to what extent they have adapted their strokes to maximize their swimming efficiency. Thus the model optimization could offer new insight into biological behavior.

Time t

Position x 0 (t) Angle Fig. 2. Two legs oscillating sinusoidally according to θ 1 = π/4 + a cos t and θ 2 = 3π/4 + a cos(t + π/2), where a = π/4 is the amplitude. The second leg (blue) oscillates about Φ 2 = 3π/4, while the first leg (red) oscillates about Φ 1 = π/4 with a phase lag of π/2. The swimmer position x translates about a fifth of the leg length after one cycle.

This article is organized into two sections. Sections II-III contain the contribution of this article. In section II, we recall some properties of the copepod swimmer [START_REF] Takagi | Swimming with stiff legs at low Reynolds number[END_REF] and the mathematical tools from geometric optimal control (see [START_REF] Bonnard | Singular trajectories and their role in control theory[END_REF] for a general reference). This section is also devoted to geometric computations of the copepod swimmer to study the role of normal and abnormal strokes. In section III we present numerical simulations to describe the normal strokes in relation with the classification of periodic planar curves [START_REF] Berger | La taxonomie des courbes[END_REF]. Finally, the optimal strokes satisfying the constraints are numerically computed using the two software: Bocop (www.bocop.org, [START_REF] Bonnans | Bocop -A collection of examples[END_REF]) and HamPath (http:// cots.perso.enseeiht.fr/hampath/, [START_REF] Cots | Contrôle optimal géométrique: méthodes homotopiques et applications[END_REF]).

II. PRELIMINARY RESULTS

A. Periodic strokes

A (general) stroke of period T consists in a periodic motion in the shape variables (θ 1 , θ 2 ). Assuming x(0) = 0, the corresponding displacement is x(T ). In [START_REF] Takagi | Swimming with stiff legs at low Reynolds number[END_REF], two types of geometric motions are described: First case (Fig. 2): The two legs are assumed to oscillate sinusoidally with period 2π according to

θ 1 = Φ 1 + a cos(t), θ 2 = Φ 2 + a cos(t + k 2 )
with a = π/4, Φ 1 = π/4, Φ 2 = 3π/4 and k 2 = π/2. This produces a displacement x(2π) = 0.2. Parameters a, Φ 1 , Φ 2 and k 2 are designed to maximize the efficiency. Second case (Fig. 3): The two legs are paddling in sequence followed by a recovery stroke performed in unison. In this case the controls u 1 = θ1 , u 2 = θ2 produce bang arcs to steer the angles from the boundary 0 of the domain to the boundary π, while the unison sequence corresponds to a displacement from π to 0 with the constraint θ 1 = θ 2 .

Time t

Position x 0 (t) Angle Fig. 3. Two legs paddling in sequence. The legs perform power strokes in sequence and then a recovery stroke in unison, each stroke sweeping an angle π.

Our main objective is to analyze these motions from the perspective of geometric optimal control.

B. Abnormal curves

With q = (x, θ 1 , θ 2 ), the system is written as a driftless affine control system

q(t) = 2 i=1 u i (t)F i (q(t))
where the control vector fields are given by

F i = sin θ i ∆ ∂ ∂x + ∂ ∂θ i with ∆ = 2+sin 2 θ 1 +sin 2 θ 2 .
We denote by D the distribution generated by the two vector fields:

D = span {F 1 , F 2 }.
The Lie bracket of two vector fields F, G is computed with the convention

[F, G](q) = ∂F ∂q (q)G(q) - ∂G ∂q (q)F (q).
Finally, we denote by p = (p 1 , p 2 , p 3 ) the adjoint vector associated with q.

We first recall basic facts concerning the local classification of two-dimensional distributions in relation with abnormal curves.

1) Local classification of two-dimensional distributions in dimension three and abnormal curves:

Let D = span {G 1 , G 2 } be the distribution generated by two vectors fields G 1 , G 2 in R 3 . Let z = (q, p) and denote H i (z) = p, G i (q) , i = 1, 2 the Hamiltonian lifts. The Poisson bracket is given by {H 1 , H 2 }(z) = dH 1 ( H 2 )(z) = p, [G 1 , G 2 ](q) .
Abnormal curves are defined by

H 1 (z) = H 2 (z) = 0,
and differentiating using the dynamics

dz dt = 2 i=1 u i - → H i (z)
we obtain the relations

{H 1 , H 2 }(z) = 0 u 1 {{H 1 , H 2 } , H 1 } (z) + u 2 {{H 1 , H 2 } , H 2 } (z) = 0
defining the corresponding abnormal controls. Tools from singularity theory can be used to classify the distributions, see [START_REF] Zhitomirskiȋ | Typical singularities of differential 1-forms and Pfaffian equations[END_REF]. Here we present only the two (stable) models related to our study. Contact case. We say that q 0 is a contact point if

{G 1 , G 2 , [G 1 , G 2 ]
} is of dimension three at q 0 . At a contact point, identified to 0, there exists a system of local coordinates q = (x, y, z) such that

D = ker(α), α = ydx + dz.
Observe that dα = dy ∧ dx (Darboux form) and that ∂ ∂z is the characteristic direction of dα. This form is equivalent to

D = ker(α ), α = dz + (xdy -ydx), with D = span{G 1 , G 2 }, G 1 = ∂ ∂x + y ∂ ∂z , G 2 = ∂ ∂y -x ∂ ∂z , G 3 = [G 1 , G 2 ] = 2 ∂ ∂z . (4)
The Martinet case.

A point q 0 is a Martinet point if at q 0 , [G 1 , G 2 ] ∈ D = span{G 1 , G 2 } and at least one Lie bracket [[G 1 , G 2 ], G 1 ] or [[G 1 , G 2 ], G 2 ]
does not belong to D. Then, there exist local coordinates q = (x, y, z) near q 0 identified to 0 such that

D = ker ω, ω = dz - y 2 2 dx,
where

G 1 = ∂ ∂x + y 2 2 ∂ ∂z , G 2 = ∂ ∂y , G 3 = [G 1 , G 2 ] = y ∂ ∂z , [[G 1 , G 2 ], G 1 ] = 0, [[G 1 , G 2 ], G 2 ] = ∂ ∂z .
(5) The surface Σ :

y = 0 where G 1 , G 2 , [G 1 , G 2 ]
are coplanar is called the Martinet surface and is foliated by abnormal curves, solutions of ∂ ∂x . In particular, through the origin it corresponds to the curve t → (t, 0, 0).

2) Computations in the copepod case:

We have

F 3 = [F 1 , F 2 ] = f (θ 1 , θ 2 ) ∂ ∂x with f (θ 1 , θ 2 ) = 2 sin θ 1 sin θ 2 (cos θ 1 -cos θ 2 ) ∆ 2 , [[F 1 , F 2 ], F 1 ] = ∂f ∂θ 1 (θ 1 , θ 2 ) ∂ ∂x , [[F 1 , F 2 ], F 2 ] = ∂f ∂θ 2 (θ 1 , θ 2 ) ∂ ∂x .
We deduce the following lemma.

Lemma 1: The singular set Σ : {q; det(F 1 (q), F 2 (q), [F 1 , F 2 ](q)) = 0}, where the vector fields

F 1 , F 2 , [F 1 , F 2 ]
are coplanar, is given by 2 sin θ 1 sin θ 2 (cos θ 1 -cos θ 2 ) = 0 which corresponds to

• θ 1 = 0 or π, • θ 2 = 0 or π, • θ 1 = θ 2 .
It is formed by the boundary of the physical domain:

θ i ∈ [0, π], θ 1 ≤ θ 2 , with respective controls u 1 = 0, u 2 = 0 or u 1 = u 2 .
Remark 1: The previous lemma provides the interpretation of the policy represented in Fig. 3. In the shape space (θ 1 , θ 2 ) it corresponds to a triangle. The edges of the triangle are abnormal curves (where by definition the linearized system is not controllable).

Remark 2: A recent contribution [START_REF] Hakavuori | Non-minimality of corners in sub-Riemannian geometry[END_REF] proves that a trajectory with a corner of this type cannot be optimal (not taking into account the state constraints). To analyze the first situation of Fig. 2, the mechanical energy has to be used in relation with SR-geometry.

C. Sub-Riemannian geometry

The problem is written

q = 2 i=1 u i G i (q), min u(.) T 0 (u 2 1 + u 2 2 )dt,
where the cost is defined for a fixed final time T . In this representation, we assume that the vector fields G 1 , G 2 are orthonormal.

The Pontryagin Maximum Principle. The admissible controls are bounded measurable mappings. According to the Pontryagin maximum principle, we introduce the pseudo-Hamiltonian in the normal case

H(z, u) = 2 i=1 u i H i (z) - 1 2 2 i=1 u 2 i ,
where the H i 's are the Hamiltonian lifts p, G i (q) . The maximization condition is equivalent to ∂H ∂ui = 0, i = 1, 2. It follows that u i = H i and plugging this expression for u i into H produces the true Hamiltonian in the normal case

H n = 1 2 H 2 1 + H 2 2 .
Definition 2: A normal stroke is a solution of -→ H n such that θ 1 and θ 2 are periodic with period T .

According to the transversality conditions of the maximum principle the adjoint variables p 2 and p 3 are such that p 2 and p 3 are both periodic with period T (to produce a smooth solution). Second order optimality condition. In the normal case, the first conjugate point corresponds to the first point where a normal geodesic ceases to be optimal with respect to the C 1topology on the set of curves with fixed endpoints conditions. They can be computed using the HamPath software [START_REF] Cots | Contrôle optimal géométrique: méthodes homotopiques et applications[END_REF].

This leads to the following definition. Definition 3: A normal stroke is called strict if it is not the projection of an abnormal extremal.

Lemma 4: A necessary optimality condition for a strict normal stroke to provide a weak minimizer is the nonexistence of a conjugate point on ]0, T [.

D. Computations and analysis for the copepod swimmer

We start by considering the simplified cost

min u(.) T 0 (u 2 1 + u 2 2 )dt
in relation with the contact case. Some geometric computations can be made, linked to the Heisenberg case. They can be used in the numerical implementation, in particular to compute strokes with small amplitudes. In this case,

H n = 1 2 H 2 1 + H 2 2
and straightforward computations can be done inside the abnormal triangle. Using the Poincaré coordinates (q, H), H = (H 1 , H 2 , H 3 ) and H i = p, G i (q) . Indeed:

Ḣ1 = dH 1 ( H n ) = {H 1 , H 2 }H 2 = H 2 H 3 , Ḣ2 = dH 2 ( H n ) = {H 2 , H 1 }H 1 = -H 1 H 3 , Moreover Ḣ3 = dH 3 ( H n ) = {H 3 , H 1 }H 1 + {H 3 , H 2 }H 2 ,
where

{H 3 , H 1 }(z) = p, [[G 1 , G 2 ], G 1 ](q) {H 3 , H 2 }(z) = p, [[G 1 , G 2 ], G 2 ](q) .
At a contact point, G 1 , G 2 , G 3 form a frame, therefore we obtain

[[G 1 , G 2 ] , G 1 ] (q) = 3 i=1 λ i (q)G i (q)
where λ 1 = λ 2 = 0, ∂f ∂θ1 = λ 3 f . Similarly,

[[G 1 , G 2 ] , G 2 ] (q) = 3 i=1 λ i (q)G i (q), with λ 1 = λ 2 = 0, ∂f ∂θ 2 = λ 3 f.
We conclude that

Ḣ1 = H 2 H 3 , Ḣ2 = -H 1 H 3 , Ḣ3 = H 3 (λ 3 H 1 + λ 3 H 2 ) . (6)
The associated one dimensional distribution can be analyzed by setting ds = H 3 dt to obtain

dH 1 ds = H 2 , dH 2 ds = -H 1 , dH 3 ds = λ 3 H 1 + λ 3 H 2 . ( 7
)
In particular, differentiating one more time the first relation of ( 7) with respect to s and using the second relation, we have the harmonic oscillator H 1 + H 1 = 0. Furthermore H 3 can be analyzed using the remaining equation [START_REF] Bonnans | Bocop -A collection of examples[END_REF]. Observe that, with the approximation that λ 3 and λ 3 are constants, the equation takes the form

dH 3 ds = A cos(s + ρ)
for some constants A and ρ. In those computations, we recognize the Heisenberg case, corresponding to λ 3 = λ 3 = 0.

Observe that when q is not a contact point (that is

G 2 = [G 1 , G 2 ] ∈ span{G 1 , G 2 }
, in order to deal with the Martinet case, we can choose the frame G 1 , G 2 and G 3 , where

G 1 = G 1 , G 2 = G 2 and G 3 = ∂ ∂x . Remark 3:
Under the assumption of considering the simplified cost, we recover the policy described in Fig. 2 where the controls are given by trigonometric functions.

III. NUMERICAL RESULTS

The period T is fixed to 2π in our simulations. We use the HamPath software [START_REF] Cots | Contrôle optimal géométrique: méthodes homotopiques et applications[END_REF] for:

1) Solving the shooting equations associated with the problem and given by

x(0) = 0, x(2π) = x f , θ i (0) = θ i (2π), i = 1, 2 p j (0) = p j (2π), j = 2, 3.
2) Showing that the normal stroke is optimal. This is done by testing the nonexistence of conjugate points using the variational equation to compute the Jacobi fields. Recall that according to [START_REF] Bonnard | Singular trajectories and their role in control theory[END_REF], given a reference curve (q(t), p(t)) solution of -→ H n , a time t c ∈]0, 2π] is a conjugate time if there exists a Jacobi field δz = (δq, δp), that is a non-zero solution of the variational equation

δz(t) = ∂ H n ∂z (q(t), p(t))δz(t) (8)
such that δq(0) = δq(t c ) = 0. We denote δz i = (δq i , δp i ), i = 1, ..., n, n-independent solutions of (8) with initial condition δq i (0) = 0. At time t c we have the following rank condition rank{δq 1 (t c ), ..., δq n (t c )} < n.

1) Sample of various possible strokes: We present a sequence of numerical simulations, not taking into account the state constraints.

Fig. 4-5-6 illustrate three different strokes illustrating the complexity of the model and are related to the generic classification of periodic planar curves [START_REF] Berger | La taxonomie des courbes[END_REF]. Conjugate points are also computed to check the second order optimality conditions. There is no conjugate point on [0, 2π] in the case of the simple loop whereas they appear for the limac ¸on case, the eight case and more complicated cases. Hence, the only candidates for optimality are the simple loops. 2) Optimal curves circumscribed in the triangle of constraints: We use a combination of the Bocop and HamPath softwares. Bocop software: This software is suitable for taking into account constraints on the state variables. Fig. 7 gives numerical simulation with this software, describing a crawling normal stroke in accordance with the abnormal triangle policy. We use the Bocop software to initialize the simple shooting algorithm of the HamPath software. HamPath software: This software cannot be directly applied to compute the optimal solution using the Maxi- mum Principle with state constraints. Fig. 8 describes a normal stroke tangent to the boundary.

3) Geometric efficiency:

To compare the different normal and abnormal solutions corresponding to different displacements and in relation with the SR-interpretation we represent the ratio E = x/L where L is the length of the stroke and x is the corresponding displacement (this quantity does not depend upon the parameterization). For the triangle, a displacement along the vertical or horizontal edge gives x = 2 and the total displacement is 2.742.10 -1 . The length of a normal stroke γ is L(γ) = 2π 0 q, q dt and easily computed using the energy level H n = 1 2 q, q = c and is 2π √ 2c. The efficiency curve is presented in Fig. 9. The normal strokes corresponding to the maximal efficiency is represented in Fig. 9. For optimal strokes with constant mechanical power over time, the efficiency introduced in [START_REF] Takagi | Swimming with stiff legs at low Reynolds number[END_REF] is proportional to the square of the geometric efficiency E. Thus both efficiencies are maximized by the same strokes. Application. From our analysis we deduce that the (triangle) abnormal stroke is not optimal. Indeed, one can choose a normal stroke (inside the triangle) such that the displacement is x/2 with x = 2.742 and length < L/2 where L =length of the triangle. Applying twice the normal stroke, we obtain the same displacement x than with the abnormal stroke but with a length < L.

IV. CONCLUSION

In this article we have investigated the copepod swimmer showing:

• from the micro-local point of view various topological strokes (simple loop, eight, limac ¸on, ...) are obtained confirming the complexity of the model. • Using second order optimality conditions only simple loops are candidates for optimality. • The abnormal triangle forming the boundary of the domain is shown to be not optimal, using the computation of the efficiency. This numerical study opens the road to analyze the more complicated Purcell three-link swimmer, see [START_REF] Bettiol | The Purcell Three-link swimmer: some geometric and numerical aspects related to periodic optimal controls[END_REF] for preliminary results.

Fig. 1 .

 1 Fig. 1. Copepod swimmer . J. Rouot is supported by the French Space Agency CNES, R&T action R-S13/BS-005-012 and by the région Provence-Alpes-Côte d'Azur M. Chyba and D. Takagi: 2565 McCarthy the Mall, Department of Mathematics, University of Hawaii, Honolulu, HI 96822, USA chyba@hawaii.edu, dtakagi@hawaii.edu Bernard Bonnard and Jeremy Rouot: Inria Sophia Antipolis and Institut de Mathématiques de Bourgogne, 9 avenue Savary, 21078 Dijon, France

Fig. 4 .Fig. 5 .

 45 Fig. 4. Normal stroke with a simple loop shape.

Fig. 6 .

 6 Fig. 6. Normal stroke with eight shape.

Fig. 7 .

 7 Fig. 7. Normal stroke with a simple loop shape where the constraints are satisfied, obtained with the Bocop software.

Fig. 8 .Fig. 9 .

 89 Fig. 8. Normal stroke with a simple loop shape where the constraints are satisfied.


O Delmas

F Havet

M Montassier

S Pérennes

Design of fault-tolerant on-board networks with variable switch sizes

Keywords: Fault tolerance, switching networks, flow networks, vulnerability

An (n, k, r)-network is a triple N = (G, in, out) where G = (V, E) is a graph and in, out are nonnegative integer functions defined on V called the input and output functions, such that for any v ∈ V , in(v)+out(v)+deg(v) ≤ 2r where deg(v) is the degree of v in the graph G. The total number of inputs is in(V ) = v∈V in(v) = n, and the total number of outputs is out(

An (n, k, r)-network is valid, if for any faulty output function out (that is such that 0 ≤ out (v) ≤ out(v) for any v ∈ V , and out (V ) = n), there are n edge-disjoint paths in G such that each vertex v ∈ V is the initial vertex of in(v) paths and the terminal vertex of out (v) paths.

We investigate the design problem of determining the minimum number N (n, k, r) of vertices in a valid (n, k, r)-network and of constructing minimum (n, k, r)-networks, or at least valid (n, k, r)networks with a number of vertices close to the optimal value.

We first give some upper bounds on N (n, k, r). We show N (n, k, r) ≤ k+2 2r-2 n 2 . When r ≥ k/2, we prove a better upper bound: N (n, k, r) ≤ r-2+k/2 r 2 -2r+k/2 n + O(1). Next, we establish some lower bounds. We show that if k ≥ r, then N (n, k, r) ≥ 3n+k 2r . We improve this bound when k ≥ 2r: N (n, k, r) ≥ 3n + 2k/3 -r/2 2r -2 + 3r k r

.

Finally, we determine N (n, k, r) up to additive constants for k ≤ 6.

Introduction

Modern telecommunication satellites are very complex to design, and one of the most important industrial issues is to provide robustness at the lowest cost possible. Alcatel Space Industries is a major provider of telecommunication satellites. A key component of their satellites is an interconnection network which allows the redirection of signals received by the satellite to a set of amplifiers from which the signals are retransmitted (a detailed overview on the model and the motivations can be found in [START_REF] Darrot | Diffusion de messages longs et propriétés structurelles dans les réseaux d'interconnexion[END_REF][START_REF] Bermond | Design of Fault-Tolerant Networks for Satellites (TWTA Redundancy)[END_REF]). For reliability convenience, wave guide technology has been chosen by Alcatel Space Industries to build these on-board networks (for background information see [START_REF] Eng | Switch matrix for TWTA redundancy an communication satellites[END_REF][START_REF] Roddy | Satellite Communications[END_REF]). So this interconnection network consists of expensive four-port switches, of wave guides linking these switches, of inputs (where the signals enter the network) and of outputs (where the signals leave the network). Before being transmitted downwards, the signals must be amplified, so the outputs are amplifiers based on Travelling Wave Tube Amplifier technology [START_REF] Eng | Switch matrix for TWTA redundancy an communication satellites[END_REF][START_REF] Roddy | Satellite Communications[END_REF]. However, amplifiers are prone to failure. Switches are also prone to failure, but due to the wave guide technology, the probability that a fault appears on a switch is much smaller than the probability that a fault appears on an amplifier. For this reason, only faults on amplifiers are considered [START_REF] Bermond | Design of Fault-Tolerant Networks for Satellites (TWTA Redundancy)[END_REF]. In the past, an important number of techniques have been proposed to increase the reliability and the fault-tolerance of multistage interconnection networks or switching networks (see [START_REF] Adams | A survey and comparison of fault-tolerant multistage interconnection networks[END_REF][START_REF] Leighton | Introduction to Parallel Algorithms and Architectures: Arrays • Trees • Hypercubes[END_REF][START_REF] Duato | Interconnection Networks An Engineering Approach[END_REF]). These techniques consider networks with switches (or links between switches) subject to failure and do not consider faulty outputs. This previous work focused on aspects such as deadlock and adaptive routing schemes that are not relevant to our problem.

In this paper, following [START_REF] Bermond | Design of Fault-Tolerant Networks for Satellites (TWTA Redundancy)[END_REF], [START_REF] Bermond | Design of fault tolerant flow networks[END_REF] and [START_REF] Havet | Repartitors, selectors and superselectors[END_REF], we focus on designing networks that are able to reroute the input signals to operational output ports in the presence of faulty output ports. Since the components of a satellite cannot be repaired, redundant amplifiers are added and the interconnection network satisfies the following fault tolerance property: the network connects the set of input ports with the set of output ports, and for any set of at most k output port failures, there exists a set of edge-disjoint paths connecting the input ports to the non-faulty output ports. Since each switching device induces a high cost, these interconnection networks are constructed with the fewest switches possible, or at least with a number of switches close to the minimum value. The considered networks are controlled centrally from Earth. Each time some used amplifiers become faulty, this controller sends messages to the switches to make them change position so that the inputs are still connected to non-faulty amplifiers.

Other variations of the initial problem have been considered in which there are two kinds of inputs in order to guarantee a certain quality of service [START_REF] Bermond | Fault tolerant on board networks with priorities[END_REF][START_REF] Havet | Repartitors, selectors and superselectors[END_REF], but they will not be considered in this paper.

The existing switches currently have four ports. The problem was initially studied for such switches in [START_REF] Bermond | Design of Fault-Tolerant Networks for Satellites (TWTA Redundancy)[END_REF] (k ≤ 4 failures), and then in [START_REF] Bermond | Design of fault tolerant flow networks[END_REF] (up to 12 failures). For this, the cheapest type of switch, all wave guides are drawn in the plane and due to technological constraints, they should not cross. For four-port switches, this was not problematic since there is a 2-dimensional switch which is as powerful as the one realizing all possible matchings of ports (see [START_REF] Bermond | Design of Fault-Tolerant Networks for Satellites (TWTA Redundancy)[END_REF]). However, for a larger number of ports, the types of switches that can be built in the plane under this non-crossing constraint are not very powerful and do not allow the construction of networks with sufficiently few vertices. For this reason, in this paper we seek to design on-board networks with more powerful switches, that is 3-dimensional switches with more than four ports. In practice, such a switch will be expensive. Hence less powerful but cheaper switches are also envisioned. For sake of simplicity, we consider here a simple model in which every switch has 2r ports and can realize all matchings among them. The aim is to provide elements to determine the number of ports minimizing the cost of the network (this will depend on the cost of construction of 2r-port switches). Obviously, the larger the number of ports, the more expensive the switches will be, but fewer are required. So the cost of such a network involves a trade-off between the total number of switches and the cost of a switch. In this paper, we give some bounds on the minimum number of 2r-port switches in interconnection networks with n inputs and n + k outputs.

Generalizing the definition of (n, k)-networks introduced in [START_REF] Bermond | Design of Fault-Tolerant Networks for Satellites (TWTA Redundancy)[END_REF] and [START_REF] Bermond | Design of fault tolerant flow networks[END_REF], we define (n, k, r)-networks as follows: An (n, k, r)-network is a triple N = (G, in, out) where G = (V, E) is a graph and in, out are non-negative integer functions defined on V called input and output functions, such that for any v ∈ V , its number of ports por(v) defined by por(v) = in(v) + out(v) + deg(v) is at most 2r. (deg(v) denotes the degree of v in the graph G, that is the number of edges of G incident to v.) Let i and o be two non-negative integers. An (i|o)-switch or switch of type i|o is a switch s with i inputs and o outputs, i.e. with in(s) = i and out(s) = o. The total number of inputs is in(V ) = v∈V in(v) = n and the total number of outputs is out(

V ) = v∈V out(v) = n + k.
Any integer function out defined on V such that 0 ≤ out (v) ≤ out(v) for any v ∈ V , and out (V ) = n is called a faulty output function. Note that out(v) -out (v) is the number of faults at vertex v. An (n, k, r)-network is valid, if for any faulty output function out , there are n edge-disjoint paths in G such that each vertex v ∈ V is the initial vertex of in(v) paths and the terminal vertex of out (v) paths.

Let us denote the minimum number of vertices in a valid (n, k, r)-network by N (n, k, r). A valid (n, k, r)-network with exactly N (n, k, r) vertices is called a minimum (n, k, r)-network. The design problem consists of determining N (n, k, r) and of constructing minimum (n, k, r)-networks, or at least valid (n, k, r)-networks with a number of vertices close to the optimal value. Let us present an example: We would like to construct valid (4, 4, 2)-networks. A first solution is depicted in Figure 1. The network N 1 is composed of eight switches u i , v i for 1 ≤ i ≤ 4. The associated graph G = (V, E) is the 4 × 2 grid. The input and output functions are defined as follows: in For any faulty output function out , it is easy to see that there are four edge-disjoint paths in G such that each vertex v ∈ V is the initial vertex of in(v) paths and the terminal vertex of out (v) paths. This implies that this network is valid. It follows that N (4, 4, 2) ≤ 8. But this solution is not the best possible. The network depicted in Figure 2 In this paper, we first give some general lower and upper bounds on N (n, k, r). We then give optimal values up to additive constants when k ≤ 6 and exhibit (almost) minimum networks. We prove the following bounds:

(v i ) = 1, in(u i ) = 0 for 1 ≤ i ≤ 4, and out(v 2 ) = out(v 3 ) = 0, out(v 1 ) = out(u 2 ) = out(u 3 ) = out(v 4 ) = 1, out(u 1 ) = out(u 4 ) = 2. 0|2 u 1 0|1 u 2 0|1 u 3 0|2 u 4 1|1 v 1 1|0 v 2 1|0 v 3 1|1 v 4
1. For any n, k, r, N (n, k, r) ≤ k+2 2r-2 n 2 . 2. For k ≥ 3 and r ≥ k/2, N (n, k, r) ≤ r-2+k/2 r 2 -2r+k/2 n + O(1). 3. For k ≥ r, 3n+k 2r ≤ N (n, k, r). 4. For k ≥ 2r, 3n + 2k/3 -r/2 2r -2 + 3r k r ≤ N (n, k, r).

Properties of minimum networks and Cut Criterion

Obviously, if 2n + k = in(V ) + out(V ) ≤ 2r, then a network with one switch connected to all inputs and outputs is valid, and thus N (n, k, r) = 1. Hence in the following, we will assume that 2r < 2n + k.

If k ≤ k , we can easily obtain a valid (n, k, r)-network from a valid (n, k , r)-network by removing an arbitrary set of k -k outputs.

Proposition 1 If k ≤ k , then N (n, k, r) ≤ N (n, k , r).
Before we proceed with the lower and upper bounds on N (n, k, r), we make an observation on the structure of valid (n, k, r)-networks. We are free to add an edge between two unused ports as long as there are two of them. Hence we can assume that in an (n, k, r)-network all switches have 2r ports, with an exception of one having 2r -1 ports, if k is odd. Let (k) = 1 if k is odd, and (k) = 0 otherwise. Proposition 2 There is a minimum (n, k, r)-network in which all switches have 2r ports except exactly (k) which have 2r -1 ports.

A switch with 2r-1 ports is called defective. In the remainder of this paper, we assume that all switches of an (n, k, r)-network have 2r ports except (k) which are defective.

All the results that will be proved in this paper rely on Lemma 3, which gives a necessary and sufficient condition, called the Cut Criterion, for an (n, k, r)-network to be valid. It extends a result of [START_REF] Bermond | Design of fault tolerant flow networks[END_REF] for r = 2 and easily follows from the Ford-Fulkerson Theorem [START_REF] Ford | Flows in Networks[END_REF] (Theorem 1.1 p.38).

Let W be a set of switches of an (n, k, r)-network. Its number of inputs and outputs in(W ) = v∈W in(v) and out(W ) = v∈W out(v), respectively. Denote by Γ(W ) the set of edges with one endvertex in W and the other in

W = V \ W and set deg(W ) = |Γ(W )|. The excess of W , denoted exc(W ), is defined by exc(W ) = deg(W )-in(W )+out(W )-min{out(W ), k}.
Intuitively, in(W ) -out(W ) + min{out(W ), k} is the difference between the number of inputs in W and the minimum number of outputs in W over all possible faulty output functions. Hence it corresponds to (a lower bound of) the number of paths with input in W and terminal veretx in W in the worst case. Those signals paths use distinct edges of Γ(W ). Thus, if the network is valid, deg(W ) must be at least in(W ) -out(W ) + min{out(W ), k}, that is exc(W ) ≥ 0. We now show that this necessary condition is also sufficient.

Lemma 3 (Cut Criterion) An (n, k, r)-network is valid if and only if every set of vertices W ⊂ V has non-negative excess.

The proof of this lemma is identical to the proof for (n, k, 2)-networks given in [START_REF] Bermond | Design of fault tolerant flow networks[END_REF].

Proof

Let out be a fixed faulty output function, then a supply/demand flow problem is defined by an integer (not necessarily positive) demand at each vertex v. In our case, the demand of a vertex v ∈ V is demand(v) = out (v) -in(v). Note that demand(V ) = 0, which is always the case for supply/demand problems. A variant of the Ford-Fulkerson Theorem states that the supply/demand problem is feasible if and only if

∀W ⊂ V : deg(W ) ≥ demand(W ) = out (W ) -in(W ) = in(W ) -out (W ).
The (n, k, r)-network is valid if all supply/demand flow problems defined by the possible faulty output functions are feasible. Therefore the (n, k, r)-network is valid if and only if

∀W ⊂ V : deg(W ) ≥ in(W ) -min{out (W ) | out faulty output function}. ( 1
)
By definition, min{out (W ) | out faulty output function} is the minimum number of non-faulty outputs in W . This minimum is attained either by choosing all outputs in W to be faulty when out(W ) ≤ k, or by choosing k outputs in W to be faulty when out(W ) ≥ k.

Hence, min{out (W ) | out faulty output function} = out(W ) -min{out(W ), k}. The property follows then from Equation [START_REF] Adams | A survey and comparison of fault-tolerant multistage interconnection networks[END_REF].

2

Using the Cut Criterion, we shall show some properties of minimum (n, k, r)-networks.

Proposition 4 (i) In a valid (n, k, r)-network, there is no switch with more than r outputs.

(ii) In a minimum (n, k, r)-network, there is no switch with r (or more) inputs.

Proof Let N be a valid (n, k, r)-network.

(i) Suppose for a contradiction that N contains a switch s with out(s

) ≥ r + 1. Let W = V \ {s}. As 2n + k > 2r, the set W is not empty. Then deg(W ) = deg(s) ≤ 2r -in(s) -out(s), in(W ) = n -in(s) and out(W ) = n + k -out(s). If k ≤ out(W ), then exc(W ) ≤ 2r -2 out(s) ≤ -2 which contradicts the Cut Criterion. If k > out(W ) then exc(W ) ≤ 2r -n -out(s) < r -n < 0 because 2n + k > 2r.
Again this contradicts the Cut Criterion.

(ii) Suppose that N contains a switch s with in(s) ≥ r. If in(s) > r or in(s) = r and out(s) ≥ 1, then {s} has negative excess which contradicts the Cut Criterion. If not, s is incident to r links e 1 , . . . , e r . Now the (n, k, r)-network obtained from N by removing s and adding one input to the endvertex of each e i is also valid and so N is not minimum.

2

Proposition 4-(ii) asserts a switch has at most r -1 inputs in a minimum (n, k, r)-network. As observed in [START_REF] Bermond | Design of fault tolerant flow networks[END_REF] for r = 2, switches with r -1 inputs, called block switch, play a special role. Non-block switches are called S-switches. We define blocks as maximum connected subgraphs made of block switches.

Proof

Set N = (G, in, out). Suppose for a contradiction that there is a cycle C of q switches in a block B. Then in(C) = (r -1)q. Moreover, there are q edges between switches of the cycle. So

deg(C) ≤ 2rq -2q -in(C) -out(C) ≤ (r-1)q-out(C). Hence exc(C) ≤ min{out(C), k}. Since exc(C) ≥ 0 by the Cut Criterion, out(C) = 0 and deg(C) = (r -1)q.
Consider the network N obtained by removing C and adding one input to a vertex v per edge from v to C.

Formally N = (G -C, in , out) with in (v) = in(v) + |{e = vu | e ∈ E(G), u ∈ V (C)}|.
It is simple matter to see that N is a valid (n, k, r)-network, because in N , (r -1)q paths must leave C. This contradicts the minimality of N . Hence the blocks are acyclic and so are trees since they are connected by definition.

Consider a block B with q switches. Then there are q -1 edges between switches of B and in(B) = (r -1)q. So deg(B)

≤ 2rq -2q + 2 -in(B) -out(B) ≤ (r -1)q + 2 -out(B). Hence exc(B) ≤ 2 -min{out(B), k}. By the Cut Criterion, exc(B) ≥ 0, so out(B) ≤ 2 as k ≥ 3.
Note that if B has no defective vertex, then the inequality above is an equality so deg(B) = (r -

1)q + 2 -out(B) = in(B) + 2 -out(B). Similarly, if B contains the defective vertex, then deg(B) = in(B) + 1 -out(B). 2
In order to prove that a network is valid, by Lemma 3, we need to prove that every set of switches has non-negative excess. We now prove that it is in fact sufficient to prove it for connected sets.

Lemma 6 If W is not connected and exc(W ) < 0, then W has a connected component W 1 such that exc(W 1 ) < 0. Hence a network is valid if and only if every connected subset has non-negative excess.

Proof

Let W i , 1 ≤ i ≤ l, be the connected components of W . Then exc(W ) = l i=1 exc(W i ). Thus, if exc(W ) < 0, then there is at least one W i which has also negative excess.

2

We now strengthen Lemma 6 by showing that establishing whether an (n, k, r)-network is valid or not only requires to check the Cut Criterion for some special sets of vertices, called essential. Let N be an (n, k, r)-network and let X be a set of S-switches, and denote by B(X) the set of blocks adjacent to X. A set W of vertices of N is essential if there exists a proper subset X of S (i.e. X = ∅ and X = S) such that W = X ∪ B∈B(X) B and W is connected.

Lemma 7 An (n, k, r)-network is valid if and only if every essential set of vertices has non-negative excess.

Proof

Since an essential set is connected, by Lemma 6, if an (n, k, r)-network is valid, then all its essential sets of vertices have non-negative excess.

Let us now prove the opposite. We need the following claim:

Claim 7.1 Let W be a set of vertices of an (n, k, r)-network. If W is adjacent to a vertex v / ∈ W such that deg(v) ≤ in(v) -out(v) + 2, then exc(W ∪ {v}) ≤ exc(W ).
Proof. Since there is an edge between between v and w, we have deg

(W ∪ {v}) ≤ deg(W ) + deg(v) -2. By definitions, in(W ∪ {v}) = in(W ) + in(v) and out(W ∪ {v}) = out(W ) + out(v). So min{out(W ∪ {v}), k} ≥ min{out(W ), k}. Hence exc(W ∪ {v}) = deg(W ∪ {v}) -in(W ∪ {v}) + out(W ∪ {v}) -min{out(W ∪ {v}), k} ≤ deg(W ) + deg(v) -2 -in(W ) -in(v) + out(W ) + out(v) -min{out(W ), k} ≤ exc(W ) + deg(v) -in(v) + out(v) -2 ≤ exc(W )

♦

Let us now prove that, if every essential set has non-negative excess, then every connected subset has non-negative excess. Together with Lemma 6, this yields the result.

Let W be a connected subset. Let X be the set of S-switches in W and

W = X ∪ B∈B(X) B. Clearly, W is essential, W ⊂ W and every vertex in W \ W is a block switch. Now every block switch v has r -1 inputs so deg(v) ≤ 2r -in(v) -out(v) = r + 1 -out(v) ≤ in(v) -out(v) + 2.
Hence applying Claim 7.1 for every vertex of W \ W one after another, we get that exc(W ) ≥ exc(W ) ≥ 0. 2

Upper bounds

In this section, we present two constructions that combine two valid networks with certain properties into a larger valid network.

First construction

We distinguish two cases according to the parity of k.

First construction for even k

Let k be even. For i = 1, 2, let

N i = (G i , in i , out i ) be an (n i , k, r)-network with a set A i = {v 1 i , . . . , v k/2 i } of k/2 switches having at least two outputs each (i.e. out i (v j i ) ≥ 2 for 1 ≤ j ≤ k/2). We construct the (n 1 + n 2 , k, r)-network N 1 ⊕ N 2 = (G, in, out) from N 1 and N 2 as follows: we remove one output from each v j i (out(v j i ) = out i (v j i ) -1)
, and we add a link between v j 1 and

v j 2 for 1 ≤ j ≤ k/2. Let M = {v j 1 v j 2 : 1 ≤ j ≤ k/2}
be the set of added links. The following theorem is an extension of Theorem 9 of [START_REF] Bermond | Design of Fault-Tolerant Networks for Satellites (TWTA Redundancy)[END_REF].

Theorem 8 Let k be even. Let N 1 be a valid (n 1 , k, r)-network with s 1 switches and let N 2 be a valid (n 2 , k, r)-network with s 2 switches both containing at least k/2 switches having at least two outputs each. Then,

N 1 ⊕ N 2 is a valid (n 1 + n 2 , k, r)-network with s 1 + s 2 switches. Proof By construction, N 1 ⊕ N 2 has s 1 + s 2 switches.
Let us now show that it is valid. By Lemma 3, we need to prove that any set W of switches of N has non-negative excess.

Let W be a set of switches, and for i = 1, 2 set

W i = V (G i ) ∩ W .
Denote by e the number of links of M between W 1 and W 2 , and denote by e 1 (resp. e 2 ) the number of links of M between W 1 (resp. W 2 ) and the switches of N 2 (resp. N 1 ) not in W 2 (resp. W 1 ). See Figure 3.

A 1 A 2 N 1 N 2 W 1 W 2 M e e 1 e 2
Figure 3: The first construction for even k.

By construction, we have:

out(W ) = out 1 (W 1 ) + out 2 (W 2 ) -e 1 -e 2 -2e; (2) in(W ) = in 1 (W 1 ) + in 2 (W 2 ); (3) deg(W ) = deg 1 (W 1 ) + deg 2 (W 2 ) + e 1 + e 2 . ( 4
)
Since N i is valid, the Cut Criterion yields

deg i (W i ) ≥ in i (W i ) -out i (W i ) + min{out i (W i ), k} where deg i (W i ) is the degree of W i in N i .
We distinguish the following cases based on the value of min{out i (W i ), k}.

Case 1. Suppose that out 1 (W 1 ) ≥ k and out 2 (W 2 ) ≥ k. Hence by the Cut Criterion, for i = 1, 2,

deg i (W i ) ≥ in i (W i ) + k -out i (W i ) and so, deg 1 (W 1 ) + deg 2 (W 2 ) ≥ in 1 (W 1 ) + in 2 (W 2 ) + 2k -out 1 (W 1 ) -out 2 (W 2 ).
Hence, by ( 2), ( 3) and (4), we obtain

deg(W ) ≥ in(W ) -out(W ) + 2k -2e ≥ in(W ) -out(W ) + k. Case 2. Suppose that out 1 (W 1 ) < k and out 2 (W 2 ) < k. For i = 1, 2, we have deg i (W i ) ≥ in i (W i ), so deg 1 (W 1 ) + deg 2 (W 2 ) ≥ in 1 (W 1 ) + in 2 (W 2 ).
So, by ( 3) and (4),

deg(W ) ≥ in(W ) ≥ in(W ) -out(W ) + min{out(W ), k}. Case 3. Suppose that out 1 (W 1 ) < k and out 2 (W 2 ) ≥ k. Then, deg 1 (W 1 ) ≥ in 1 (W 1 ) and deg 2 (W 2 ) ≥ in 2 (W 2 ) + k -out(W 2 ). So, deg 1 (W 1 ) + deg 2 (W 2 ) ≥ in 1 (W 1 ) + in 2 (W 2 ) + k -out 2 (W 2 ).
By (2), (3), et (4), we obtain:

deg(W ) ≥ in(W ) + k -out(W ) + out 1 (W 1 ) -2e.
Moreover, by construction, out 1 (W 1 ) ≥ 2e since each vertex of W 1 incident to an edge of M satisfies out 1 ≥ 2. Hence,

deg(W ) ≥ in(W ) -out(W ) + k.
In all three cases, W satisfies the Cut Criterion. 2

First construction for odd k

Let k = 2p + 1 be odd. For i = 1, 2, let N i = (G i , in i , out i ) be an (n i , k, r)-network with a set A i = {v 1 i , . . . , v p i } of p switches having at least two outputs each (i.e. out i (v j i ) ≥ 2 for 1 ≤ j ≤ p). Let w 1 be a switch of V (G 1 ) \ A 1 with an output (out 1 (w 1 ) ≥ 1) or a vertex of A 1 with at least 3 outputs (out 1 (w 1 ) ≥ 3). Let z 2 be the unique switch of N 2 with 2r -1 ports. We construct the (n 1 + n 2 , k, r)network N 1 ⊕ N 2 from N 1 and N 2 as follows: we remove on each v j i one output and we add a link between v j 1 and v j 2 for 1 ≤ j ≤ k/2. Moreover we remove an output to w 1 and connect w 1 to z 2 . See Figure 4.

A 1 A 2 N 1 N 2 w 1 z 2
Figure 4: The first construction for odd k.

We will now prove an analogue to Theorem 8 for odd k. Therefore, we need the following well-known lemma:

Lemma 9 (folklore) Let u and v be two vertices of a graph G. If u and v have both odd degree and all other vertices have even degree, then there is a path in G with endvertices u and v.

Theorem 10 Let k = 2p + 1 be odd. Let N 1 be a valid (n 1 , k, r)-network with s 1 switches and let N 2 be a valid (n 2 , k, r)-network with s 2 switches containing both at least p switches with at least two outputs.

Then N 1 ⊕ N 2 is a valid (n 1 + n 2 , k, r)-network containing s 1 + s 2 switches. Proof By construction, N 1 ⊕ N 2 has s 1 + s 2 switches.
Let us now show that it is valid. Let out be a faulty output function such that out (N

1 ⊕N 2 ) = n 1 +n 2 .
Note that our construction is very close to the one of Theorem 8 and in most of the cases, the paths may be found by removing one output of N 1 and one output of N 2 to obtain two networks satisfying the conditions of Theorem 8.

In fact, one can see N 1 as a valid (n 1 , k -1, r)-network, with one output less at w 1 . Rigorously, the network

M 1 = (G 1 , in 1 , sor 1 ), defined by sor 1 (v) = out 1 (v) if v ∈ V (G 1 ) \ {w 1 } and sor 1 (w 1 ) = out 1 (w 1 ) -1 otherwise, is a valid (n 1 , k -1, r)-network. Moreover, by the choice of w 1 , every vertex v of A 1 satisfies sor 1 (v) ≥ 2. For any vertex s 2 , the (n 2 , k -1, r)-network M 2 = (G 2 , in 2 , sor 2 ), defined by sor 2 (v) = out 2 (v) if v ∈ V (G 1 ) \ {s 2 }
and sor 2 (s 2 ) = out 2 (s 2 ) -1 otherwise, is valid. However, to apply Theorem 8 to M 1 ⊕ M 2 , we need the condition sor 2 (v) ≥ 2 for all v ∈ A 2 . This condition is only verified when s 2 is not in A 2 , the set of vertices v of A 2 such that out 2 (v) = 2. Therefore, we distinguish two cases depending on whether there is a switch

s 2 of V (G 2 ) \ A 2 such that out (s 2 ) < out(s 2 ).
If there is a switch s 2 of V (G 2 ) \ A 2 such that out (s 2 ) < out(s 2 ), then the networks M 1 and M 2 define above fulfill the conditions of Theorem 8, and so M 1 ⊕ M 2 is valid. Hence we can find n 1 + n 2 edge-disjoint paths in M 1 ⊕ M 2 such that each vertex v ∈ V is the initial vertex of in(v) paths and the terminal vertex of out (v) paths. Since the graph of M 1 ⊕ M 2 is the one of N 1 ⊕ N 2 minus the edge w 1 z 2 , these paths are the desired ones in N 1 ⊕ N 2 .

Suppose now that every vertex v such that out (v) < out(v) is in A 2 . Note that for such a v, out (v) = out(v) -1 = 0 because out(v) = out 2 (v) -1 = 1. The proof can be sketched as follows. We apply the validity of N 1 and N 2 to some well-chosen faulty output functions out 1 and out 2 . Doing so, we will obtain a set of n 1 + n 2 edge-disjoint paths, n 1 in N 1 and n 2 in N 2 , which is very close to the desired one. The problems are the following: for some vertices of A 1 and for w 1 , the number of paths ending in the vertex exceeds by 1 its faulty output function, while for some vertices of A 2 and for one specific vertex w 2 ∈ A 2 (to be defined later), the faulty output function exceeds by 1 the number of paths ending in the vertex. Using the edges between vertices of A 1 and A 2 , we solve the problems at vertices in A 1 and A 2 . It then remains to find a path from w 1 to w 2 that is edge-disjoint from the previously constructed paths. This is done using Lemma 9. We now give the detailed proof.

Let

p 2 = out(V (G 2 )) -out (V (G 2 )), J 2 = {j, 1 ≤ j ≤ p and out (v j 2 ) < out(v j 2 )}. Clearly |J 2 | = p 2 . Set J 1 = {1, 2, . . . , p} \ J 2 . Let us define out 1 by out 1 (v) = out (v) + 1 if v ∈ {v j 1 , j ∈ J 1 } ∪ {w 1 } and out 1 (v) = out (v) if v ∈ V (G 1 ) \ ({v j 1 , j ∈ J 1 } ∪ {w 1 }). Let w 2 be an arbitrary vertex of V (G 2 ) \ A 2 such that out 2 (w 2 ) ≥ 1.
(Such a vertex exists as the total number of outputs in A 2 is at most 2k.) Let us define out 2 by out

2 (v) = out (v) -1 if v ∈ {v j 2 , j ∈ J 1 \ {w 2 }}, out 2 (v) = out (v) if v ∈ V (G 2 ) \ ({v j 2 , j ∈ J 1 } ∪ {w 2 }) and out 2 (w 2 ) = out(w 2 ) -2 if w 2 ∈ {v j 2 , j ∈ J 1 } and out 2 (w 2 ) = out(w 2 ) -1 otherwise.
For i = 1, 2, the function out i is a faulty output function of N i . Since N i is valid, one can find a set P i of n i edge-disjoint paths in N i such that each vertex v ∈ V (G i ) is the initial vertex of in(v) paths and the terminal vertex of out i (v) paths. P 1 ∪P 2 is almost the set of desired paths. The only problems are that each vertex of {v j 1 , j ∈ J 1 } ∪ {w 1 } is the end of one path too many and each vertex of v ∈ {v j 2 , j ∈ J 1 } ∪ {w 2 } is the end of one path too few. (If w 2 ∈ {v j 2 , j ∈ J 1 }, then w 2 is the end of two paths too few.) For any j ∈ J 1 , let P j be a path P 1 ending in v j 1 and Q j = P j v j 1 v j 2 and let P be a path of P 1 ending in w 1 . Consider the graph H 2 obtained from G 2 by removing all the edges of the paths in P 2 . Let us show that H 2 has exactly two vertices with odd degree z 2 and w 2 unless

z 2 = w 2 . Let v be a vertex of V (G 2 ) \ {w 2 , z 2 }. If v ∈ {v j 2 , j ∈ J 2 } \ {z 2 }, then out 2 (v) = 2
and v is the end of no paths of P 2 . So the number e(v) of edges incident to v in paths of P 2 has the same parity as in 2 (v). Hence deg

H2 (v) = 2r-out 2 (v)-in 2 (v)-e(v) is even. If v ∈ {v j
2 , j ∈ J 1 }, then v is the end of out 2 (v)-2 paths of P 2 . So the number e(v) of its incident edges in paths of P 2 has the same parity as in 2 (v) + out 2 (v). Hence deg H2 (v) is even. If v ∈ V (G 2 )\A 2 , then v is the end of out 2 (v) and the start of in 2 (v) paths of P 2 . Thus the number e(v) of edges incident to v in paths of P 2 has the same parity as in 2 (v) + out 2 (v). It follows that deg H2 (v) is even. Analogously, one shows that the degrees of w 2 and z 2 in H 2 are odd unless w 2 = z 2 . Thus, by Lemma 9, there is a path Q from z 2 to w 2 . Now (P

1 ∪ P 2 ) \ ({P j , j ∈ J 1 } ∪ {P }) ∪ ({Q j , j ∈ J 1 } ∪ {Q})
is the desired set of paths. 2

Derived upper bound

Observe that if both N 1 and N 2 contains k switches with at least two outputs, then N 1 ⊕ N 2 contains also k such switches. In fact, in N 1 , k/2 switches with two outputs lose one output to be linked to a switch of

N 2 . So at least k -k/2 = k/2 switches of N 1 have two outputs in N 1 ⊕ N 2 . Similarly, at least k/2 switches of N 2 have two outputs in N 1 ⊕ N 2 .
Hence, in total, N 1 ⊕ N 2 contains at least k switches having at least two outputs each.

In particular, we can apply recursively Theorems 8 and 10 with N 1 .

Corollary 11 Let k be an integer. Let N 1 be a valid (n, k, r)-network with s switches, k of whom have at least two outputs. For any integer l, N l = N 1 ⊕ N l-1 is a valid (ln, k, r)-network with l • s switches.

Havet [START_REF] Havet | Repartitors, selectors and superselectors[END_REF] showed that

N (1, k, 2) = k 2 and N (2, k, 2) = k+2 2
. Moreover there are optimum networks all switches of which have at least two outputs. We generalize these results for general r:

Proposition 12 N (1, k, r) = k 2r-2 and N (2, k, r) = k+2
2r-2 . Moreover, there are optimum networks whose switches all have at least 2r -2 outputs.

Proof Consider the network N 1 (resp. N 2 ) with s switches v 1 , . . . , v s such that v 1 is a (0|2r -1)-switch Corollary 13

(resp. (1|2r -2)-switch), v s is a (1|2r -2)-switch, each v i , 2 ≤ i ≤ s -1, is a (0|2r -2)-switch and (v 1 , v 2 , . . . , v l ) is
If n is even,

N (n, k, r) ≤ k + 2 2r -2 n 2 .
If n is odd,

N (n, k, r) ≤ k + 2 2r -2 n -1 2 + k 2r -2 .

Second construction

Let k be an even integer and r ≥ k/2.

For i = 1, 2, let N i = (G i , in i , out i ) be an (n i , k, r)-network containing an (r -k/2|r)-switch u i . We construct the (n 1 + n 2 -(r -k/2), k, r)-network N 1 ⊗ N 2 =
(G, in, out) from N 1 and N 2 as follows: we identify u 1 and u 2 into a new vertex u and we set in(u ) = out(u ) = r -k/2. See Figure 5.

N 1 ⊗ N 2 N 1 r -k/2|r u 1 r -k/2|r u 2 N 2 r -k/2|r -k/2 N 1 ⊗ N 2 u (a) (b)
Figure 5: The second construction.

Theorem 14 Let k be an even integer and r ≥ k/2. Let N 1 = (G 1 , in 1 , out 1 ) be a valid (n 1 , k, r)network with s 1 switches and let N 2 = (G 2 , in 2 , out 2 ) be a valid (n 2 , k, r)-network with s 2 switches both containing at least one (r -k/2|r)-switch.

Then N 1 ⊗ N 2 = (G, in, out) is a valid (n 1 + n 2 -(r - k/2), k, r)-network containing s 1 + s 2 -1 switches.
Proof Let out be a faulty output function on N 1 ⊗ N 2 . We shall exhibit a set

P of n 1 + n 2 -(r -k/2) edge-disjoint paths such that any vertex v of V (G)
is the initial vertex of in(v) paths and the terminal vertex of out(v) paths. Let f 1 be the number of faults on the vertices of V (G 1 ) \ {u 1 } and f 2 be the number of faults on the vertices of V (G 2 ) \ {u 2 }. Let us define the faulty output function out 1 on N 1 by out 1 (v) = out (v) for any vertex v ∈ V (G 1 ) \ {u 1 } and out 1 (u 1 ) = out(u 1 ) + f 2 . Similarily, we define the faulty output function out 2 on N 2 by out 2 (v) = out (v) for any vertex v ∈ V (G 2 ) \ {u 2 } and out 2 (u 2 ) = out(u 2 ) + f 1 . Since for i = 1, 2, N i is valid, there exists a set P i of edge-disjoint paths such that any vertex v ∈ V (G i ) is the initial vertex of in i (v) paths and the terminal vertex of out i (v) paths. The set P = P 1 ∪ P 2 is almost the desired set. The vertex u is the terminal vertex of r -k/2 paths too many and the initial vertex of r -k/2 paths too many. It suffices now to merge one to one r -k/2 paths ending at u with as many paths beginning at u to obtain the desired set of paths. 2

If N contains two (r -k/2|r)-switches, then N ⊗ N contains also two such switches and we can apply recursively Theorem 14.

Corollary 15 Let k be an integer. Let N 1 be a valid (n, k, r)-network with s switches containing two (r -k/2|r)-switches. For any integer l ≥ 2,

N l = N 1 ⊗ N l-1 is a valid (ln -(l -1)(r -k/2), k, r)- network with ls -(l -1) switches. Corollary 16 If r > k/2 then N (n, k, r) ≤ n r -k/2 .
Proof By Proposition 1, it suffices to prove the result for even k. Suppose r > k/2 and k is even, the (2r -k, k, r)-network consisting of two (r -k/2|r)-switches joined by k/2 edges is trivially valid. Hence, by Corollary 15, N (n, k, r)

≤ n r-k/2 . 2
However this upper bound may be improved for k ≥ 3 using better initial network.

Theorem 17 For k ≥ 3 and r ≥ max{3, k/2},

N (n, k, r) ≤ r -2 + k/2 r 2 -2r + k/2 n + O(1).
Proof By Proposition 1, it suffices to prove the result for even k.

Let H be the (r 2 -r, k, r)-network depicted in Figure 6 with

r ≥ k/2. It is composed of r -1 + k/2 switches: -k/2 switches b 1 , . . . , b k/2 of type r -1|2, and -r -1 switches s 1 , . . . , s r-1 of type r -k/2|r. k/2 r -k/2|r s 1 r -1|2 b 1 . . . r -k/2|r s r-1 r -1|2 b k/2 r -k/2|r s j ×(r -3) Figure 6: An (r 2 -r, k, r)-network with k ≥ 2 and r ≥ max{3, k/2}.
Each s i is connected to all b j . Using Lemma 7, it is easy to check the validity of the network H. Let W be an essential set of vertices. Let S W be the set of (r -k/2|r)-switches contained in W . Suppose that |S W | = j (1 ≤ j ≤ r -2). By the observation made in the proof of Lemma 7, we can assume that W contains all b i for 1

≤ i ≤ k/2. Now, exc(W ) = deg(W ) -in(W ) + out(W ) -min{out(W ), k} = (r -1 -j)k/2 -((r -k/2)j + (r - 1)k/2) + j • r + k/2 • 2 -min{out(w), k} = k -min{out(W ), k} ≥ 0. Hence, the network H is valid.
Corollary 15 applied to N 1 = H shows that the (n, k, r)-network depicted in Figure 7 is valid. Proposition 17 follows.

2

Remark 18 Theorem 17 does not hold for r = 2. The construction does not work since H has only one (r -k/2|r)-switch, and so H ⊗H has none. Bermond et al. [START_REF] Bermond | Design of fault tolerant flow networks[END_REF] showed that N (n, 6, 2) = 5n 4 + n 8 +θ(1).

k/2 r -k/2|r r -1|2 . . . r -k/2|r -k/2 r -1|2 r -k/2|r ×(r -3) r -1|2 . . . r -1|2 r -k/2|r ×(r -3) • • • k/2 r -k/2|r -k/2 k/2 r -1|2 . . . r -k/2|r r -1|2 r -k/2|r ×(r -3)

Proof

Let N = (G, in, out) be a valid (n, k, r)-network with s switches. For any switch v, deg(v) ≤ 2r -in(v) -out(v). By Proposition 4, a switch has at most r outputs, so at most k outputs. Thus, by the Cut Criterion, deg(v) ≥ in(v). Combining these two inequalities, we obtain 2r ≥ 2 in(v) + out(v). Summing such inequalities over all switches v, we obtain 2r • s ≥ 3n + k. Hence s ≥ 3n+k 2r . 2

In the remaining of this subsection, we prove a better upper bound on N (n, k, r), when k ≥ 2r. Some preliminaries are required.

Let G = (V, E) be a graph and p is a positive integer: A p-quasi-partition of G is a set {A 1 , A 2 , . . . , A m } of subsets of V , such that:

1. For every 1 ≤ i ≤ m, the subgraph induced by A i , G[A i ], is connected; 2. For every 1 ≤ i ≤ m, p/2 ≤ |A i | ≤ p; 3. V = m i=1 A i and m i=1 |A i | ≤ |V | + |{A i , |A i | ≥ 2p 3 + 1}| + p/6.
Lemma 20 Let p be a positive integer and let G be a connected graph of order at least p/2. Then G admits a p-quasi-partition.

Proof Every connected graph G has a spanning tree T , and a p-quasi-partition of T is clearly a p-quasipartition of G. Hence, it suffices to prove the result for the tree T . If p ≤ 2, then the result is trivial, because the family of singleton {v}, v ∈ V (T ), is a p-quasi-partition. Henceforth, we assume that p ≥ 2.

We prove it by induction on |V (T )| the result being trivial if |V (T )| ≤ p. For any positive real number q, let E q be the set of edges of T such that each of the two components of T \ e has at least q vertices. Claim 20.1 (i) If E q = ∅, then the subgraph H q induced by the edges of E q is a subtree of T .

(ii) If E q = ∅, then there exists a vertex x such that all components of T -x have less than q vertices. Proof. (i) Let e 1 and e 2 be two edges of E q . Since T is a tree, there is a unique path (x 1 , . . . , x p ) in T such that x 1 x 2 = e 1 and x p-1 x p = e 2 . The forest T \ e 1 has one component C 1 containing x 1 and one component containing x 2 (and thus all the x i , i ≥ 3). Similarly, T \ e 2 has one component C 2 containing x p and one component containing x p-1 . Since e 1 and e 2 are in E q , both C 1 and C 2 have at least q vertices. Now for every 2 ≤ i ≤ p -2, T \ x i x i+1 has one component C 1 containing x i and another C 2 containing x i+1 . Clearly C 1 contains C 1 because the path (x 1 , . . . , x i ) is in C 1 . Similarly, C 2 contains C 2 . Hence both C 1 and C 2 have at least q vertices, and so x i x i+1 ∈ E q .

Hence, the subgraph H q is connected and thus is a tree.

(ii) Let us orient the edges of T as follows. Let e = uv be an edge of T . Because E q is empty, we have e / ∈ E q . Thus, at least one component of T \ e has size less than q. Without loss of generality, this component is the one containing v. Orient the edge e from u to v. Now every orientation of a tree contains a vertex x with outdegree 0. Consider a component C of T -x. It contains exactly one neighbour y of x, and it is precisely the component of T \ xy containing y. Thus |C| < q because the edge is oriented from x to y. Hence all components of T -x have less than q vertices. ♦

In view of Claim 20.1, we define the q-heart of T , denoted H q , as follows: if E q is not empty, then H q is the subtree induced by the edges of E q ; if E q is empty, then H q is a tree reduced to a vertex x such that all components of T -x have less than q vertices. (Note that if E q is empty, then the q-heart is not uniquely defined, but any x having the given property is fine.)

Assume that p ≤ |T | ≤ 3p/2. Set t = |T |. If E p/2 contains an edge uv, then let C u (resp. C v ) be the component of T \ uv containing u (resp. v). We have |C u | + |C v | = |T | and |C u |, |C v | ≥ p/2. Thus, |C u | ≤ |T | -p/2 ≤ p and similarly |C v | ≤ p. Hence (V (C u ), V (C v )) is a p-quasi-partition of T .
Suppose now that the p/2-heart H p/2 is reduced to a single vertex x. Let C i , 1 ≤ i ≤ l, be the components of T -x indexed in decreasing order of their size:

|C 1 | ≥ |C 2 | ≥ • • • ≥ |C l |. Let i be the smallest integer such that i j=1 |C j | ≥ (t -2)/3. Set A 1 = i j=1 C j ∪ x.
Since the components are indexed in decreasing order of their size, then

|A 1 | ≤ 2t/3. Thus B = V (T ) \ A 1 contains at least t/3 vertices. Let T 2 be a subtree of T [A 1 ] on max{ p/2 -|B| , 1} vertices containing x. Such a tree exists since |A 1 | ≥ t/3 ≥ t/6 ≥ p/2 -|B|. Now (A 1 , V (T 2 ) ∪ B) is a p-quasi-partition of T .
Assume now that T has more than 3p/2 vertices. Let u be a leaf of H p . Let C i , 1 ≤ i ≤ l, be the components of T -H p which are connected to u. By definition of H p , each of the C i has less than p vertices and |C i | + 1 ≥ p. Without loss of generality, we may assume that the C i are indexed in decreasing order of their size:

|C 1 | ≥ |C 2 | ≥ • • • ≥ |C l |.
We shall distinguish two cases.

= i j=1 V (C j ) ∪ {u}, one checks easily that {A 1 , A 2 , . . . , A m , A m+1 } is a p-quasi-partition of T since T ∩ A m+1 = {u}. 2 Theorem 21 If k ≥ 2r, then N (n, k, r) ≥ 3n + 2k/3 -r/2 2r -2 + 3r k r
.

Proof

Let N = (G, in, out) be a valid (n, k, r)-network with s switches. Set p = k r . Since k ≥ 2r, we have p ≥ 2. Since all outputs are on switches, s ≥ k/2r ≥ p/2. So by Lemma 20, G admits a p-quasi-

partition {A 1 , A 2 , . . . , A m }. Let m 1 = |{A i , |A i | ≤ 2p 3 }| and m 2 = |{A i , |A i | > 2p 3 }|. By definition of p-quasi-partition, we have s ≥ m i=1 |A i | -m 2 - p 6 ≥ p 2 m 1 + 2p 3 + 1 m 2 -m 2 - p 6 . Therefore 3r p s ≥ 3r 2 • m 1 + 2rm 2 - r 2 ≥ 2m 1 + 2rm 2 - r 2 . (5)
For 1 ≤ i ≤ m, let e i be the number of edges joining two vertices of A i . Since G[A i ] is connected, we have e i ≥ |A i | -1. Furthermore, because every input, output or edge is connected to a port of a switch,

2r|A i | ≥ in(A i ) + out(A i ) + deg(A i ) + 2e i , so deg(A i ) ≤ 2(r -1)|A i | + 2 -in(A i ) -out(A i ).
But, by Proposition 4, a switch has at most r outputs, so A i has at most k outputs. Thus, by the Cut Criterion, deg(A i ) ≥ in(A i ). Combining the last two inequalities, we obtain 2(r -1)|A i | + 2 ≥ 2 in(A i ) + out(A i ). Summing these inequalities over all i, we obtain

2m + 2(r -1) m i=1 |A i | ≥ 2 m i=1 in(A i ) + m i=1 out(A i ), 2m + 2(r -1)(s + m 2 + p/6) ≥ 2 in(G) + out(G), and
2m 1 + 2rm 2 + (2r -2)s ≥ 3n + k -(r -1) p 3 ≥ 3n + 2k 3 . (6)
Combining Eq.( 6) and Eq.( 5) we obtain

3r p s + (2r -2)s ≥ 3n + 2k 3 - r 2 , so s ≥ 3n + 2k 3 -r 2 2r -2 + 3r p . 2
4.2 Optimal lower bounds for k ≤ 6

Bermond, Pérennes and Tóth [START_REF] Bermond | Design of fault tolerant flow networks[END_REF] proved:

• for k ∈ {1, 2}, N (n, k, 2) = n, • for k ∈ {3, 4}, N (n, k, 2) = 5n 4
, and

• for k ∈ {5, 6}, N (n, k, 2) = 5n 4 + n 8 + Θ(1)
.

We now present bounds for N (n, k, r), which are optimal up to an additive constant, for some cases where k ≤ 6 and r ≥ 3.

By Proposition 4, in a minimum (n, k, r)-network, the number of inputs n is at most r -1 times the number of switches.

N (n, k, r) ≥ n r -1 .
For k ∈ {1, 2}, this lower bound matches the upper one given by Corollary 16.

Theorem 22

N (n, 1, r) = N (n, 2, r) = n r -1 .
For larger value of k, we need to look more precisely at the blocks and S-switches of the network. Let us introduce some notations. Let 0 ≤ i ≤ r -1 and 0 ≤ o ≤ 2. Denote by S i the set of switches with i inputs and s i its cardinality. In particular, S r-1 is the set of block switches, and the blocks are maximum connected subgraphs made of vertices of S r-1 . Denote B o the set of blocks with o outputs and b o its cardinality. We call B o -block a block in B o and we denote by t o the total number of switches in the B o -blocks. By Proposition 5, a block has at most two outputs, so the total number of block switches is s r-1 = t 0 + t 1 + t 2 . Let S be the set of S-switches, that is S = r-2 i=0 S i . Let s i|o denote the number of (i|o)-switches, s S the number of S-switches and e S the number of edges joining two S-switches. Finally, s denotes the total number of switches of the network.

Let N be a valid (n, k, r)-network. Set (N ) = 1 if an S-switch is defective, (N ) = -1 if a block switch is defective, and (N ) = 0 otherwise. We now get better lower bounds provided that k ≥ 5. We first provide new inequalities satisfied by a valid (n, k, r)-network if k ≥ 5. Define (N ) = 1 if a switch having less than r -2 inputs is defective, and (N ) = 0 otherwise. Note that if k ≥ 2 a B 2 -block B does not contain any defective vertex for otherwise deg(B) = in(B) -1, and so exc(B) = -1, which is impossible by the Cut Criterion. A B 2 -block B is not adjacent to a switch v of type r -2|3 or r -2|4 for otherwise B ∪ {v} has negative excess which is impossible. For 0 ≤ j ≤ 2, let a j be the number of links between B 2 -blocks and switches of S r-2 having j outputs. If j = 1, 2, a switch of type r -2|j cannot be incident to two links incident to B 2 -blocks, for otherwise the union of this switch and the two B 2 -blocks connected to it has negative excess. Hence a j ≤ s r-2|j for j = 1, 2. A switch of type r -2|0 cannot be incident to three links incident to B 2 -blocks, for otherwise the union of this switch and the three B 2 -blocks connected to it has negative excess. Hence 2a 0 ≤ s r-2|0 . Consequently, e = a 0 + a 1 + a 2 ≤ s r-2|1 + s r-2|2 + 2s r-2|0 .

Hence we obtain:

Figure 1 :

 1 Figure 1: A first solution: the network N 1 .

Figure 2 :

 2 Figure 2: A better solution: the network N 2 .

5 . 1 . 6 . 2 - 2

 51622 For k ∈ {1, 2} and r ≥ 1, N (n, k, r) = n r-For k ∈ {3, 4} and r ≥ 3, N (n, k, r) = r r r+2 n + Θ(1).

7 .

 7 For k ∈ {5, 6} and r ≥ 7, N (n, k, r) = r+1 r 2 -2r+3 n + Θ(1).

Proposition 5

 5 Let N be a minimum (n, k, r)-network for k ≥ 3. Then the following hold: -the blocks of N are trees and contain at most 2 outputs; -for any block B of N , deg(B) = in(B) + 2 -out(B) unless it contains the defective vertex in which case deg(B) = in(B) + 1 -out(B).

2 by 2 Corollary 11 and

 2211 a path. It is easy to check that N 1 and N 2 are a valid (1, (2r -2)s, r)-network and a valid (2, (2r -2)s -2, r)-network, respectively. It follows that N (1, k, r) ≤ k 2r-2 and N (2, k, r) ≤ k+2 2r-Proposition 1. Moreover, the above upper bounds are tight since a valid network must be connected. Proposition 12 yield:

Figure 7 :

 7 Figure 7: An (n, k, r)-network with k ≥ 2 and r ≥ max{3, k/2}.

•

  Assume first that |C 1 | ≥ p/2 vertices. The tree T -C 1 has at least p/2 vertices. Hence, by the induction hypothesis, T -C 1 has a p-quasi-partition {A 1 , A 2 , . . . , A m }. Setting A m+1 = V (C 1 ), then one verifies easily that {A 1 , A 2 , . . . , A m , A m+1 } is a p-quasi-partition of T since (T -C 1 ) ∩ C 1 = ∅. • Assume now that |C 1 | < p/2. (In particular, p ≥ 3 and 2p/3 + 1 ≤ p). Let i be the smallest integer such that i j=1 |C j | ≥ 2p/3. Since the components are indexed in decreasing order of their size, then i j=1 |C j | < p. The tree T = T -i j=1 V (C j ) has at least p/2 vertices. Hence, by the induction hypothesis, T has a p-quasi-partition {A 1 , A 2 , . . . , A m }. Now setting A m+1

Corollary 25

 25 For k ∈ {3, 4} and r ≥ 3, N (n, k, r) = r r 2 -2 r + 2 n + Θ(1).

Proposition 26

 26 If k ≥ 5 and r ≥ 4, a valid (n, k, r)-network N satisfies the following inequalities:b 1 ≤ t 1 ;(14)(2r + 2)s r-1 + (2r -6)s r-2 -r-3 j=0 2j • s r-3-j + k ≤ 6s. (15)Proof Eq.(14) expresses the fact that a B 1 -block contains at least one switch.Let us now show Eq.(15). LetH = B 0 ∪ B 1 ∪ B 2 ∪ S r-2 and H = H \ B 2 . We have out(H) + out(H) = in(H) + in(H) + k so out(H) -in(H) = k + in(H) -out(H) = k + (r -1)S r-1 -b 1 -2b 2 + 4 o=0 (r -2 -o)s r-2|o . Let us now compute deg(H) = deg(H).Since there is no edge between blocks, deg(H) = deg(H ) + B∈B2 deg(B) -2e with e the number of edges between B 2 -blocks and switches of S r-2 . By the Cut Criterion, deg(H ) ≥ in(H ) -out(H ) ≥ (r -1)(t 1 + t 0 ) -b 1 + 4 o=0 (r -2 -o)s r-2|o .

3 j=0( 6 + 2 Proposition 27

 36227 deg(H) ≥ (r -1)(t 2 + t 1 + t 0 ) -b 1 + (r -6)(s r-2|4 + s r-2|2 + s r-2|0 ) + (r -5)(s r-2|3 + s r-2|1 ). So deg(H) + out(H) -in(H) ≥ k + 2(r -1)s r-1 -2b 1 -2b 2 + (2r -12)s r-2|4 +(2r -10)(s r-2|3 + s r-2|2 ) + (2r -8)(s r-2|1 + s r-2|0 ).By (14) b 1 ≤ t 1 , and by[START_REF] Leighton | Introduction to Parallel Algorithms and Architectures: Arrays • Trees • Hypercubes[END_REF] b 2 ≤ t 2 . Thus deg(H) + out(H) -in(H) ≥ k + 2(r -2)s r-1 + (2r -12)s r-2 . (16) Now deg(H) + out(H) -in(H) ≤ v∈H (deg(v) + out(v) -in(v)) ≤ v∈H (2r -2 in(v)). deg(H) + out(H) -in(H) ≤ r-2j)s r-3-j .(17)Combining (16) and (17), we obtain (15). For r ≥ 7 and k ≥ 5, N (n, k, r) ≥ (r + 1)n + k r 2 -2r + 3 .

Proposition 23 Let N be a minimum (n, k, r)-network. s S + t 0 + t 1 + t 2 = s;

(7)

-

Proof

Eq.( 7), Eq.( 8) and Eq.( 9) count the number of switches, inputs and outputs, respectively, in the network.

Eq.( 10) counts the number of edges between blocks and S-switches. The number of edges leaving the B 0 -blocks (resp. B 1 -blocks, B 2 -blocks) is (r -1)t 0 + 2b 0 (resp. (r -1)t 1 + b 1 , (r -1)t 2 ) decreased by 1 if a block switch is defective; the number of edges leaving S is

Eq.( 11) expresses the fact that a B 2 -block contains at least one switch. 2

Proposition 24 For r ≥ 3 and k ≥ 3,

, by Eq. ( 9).

Hence,

Now, let us count the total number of ports of the S-switches :

by Eq. ( 9)

by Eq. ( 11)

The inequalities ( 12) and (13) give a lower bound of s = s S + s r-1 :

One of these two functions (of s r-1 ) increases while the other decreases, thus the minimum is achieved when the two bounds are equal that is when

. We obtain s ≥ rn

For k ∈ {3, 4}, the lower bound of this proposition matches the upper one given by Theorem 17.

The lower bound of Proposition 27 matches the upper one given by Theorem 17 for k = {5, 6}.

Corollary 28 For k ∈ {5, 6} and r ≥ 7, N (n, k, r) = r + 1 r 2 -2r + 3 n + Θ(1).

We conjecture that Proposition 27 also holds for r ≤ 7. Together with Theorem 17, this would yield the following conjecture.

Conjecture 29 For k ∈ {5, 6} and r ≥ 3, N (n, k, r) = r + 1 r 2 -2r + 3 n + Θ(1).