L Bonnin

A Piot

N Isac

A Bosseboeuf
email: alain.bosseboeuf@c2n.upsaclay.fr

Deposition and patterning of electrodes on the vertical sidewalls of deep trenches

Keywords: evaporation, patterning, vertical sidewalls, shadow masking, gnomonics

A process able to produce at wafer scale patterned electrodes on the vertical sidewalls of trenches is described and investigated in details. It is based on metal evaporation at oblique incidence through a shadow mask made in a dry photoresist film. A full model of the deposition and patterning process is established in order to map the shape as well as the thickness and density of patterned electrodes with or without wafer rotation. In the case of wafer rotation, the modelling is based on the analogy of each shadow mask edge with the gnomon of a sundial. The final electrode shape is then computed from the trajectories followed by the shadows of the gnomons. Offset of the substrate tilt axis with respect to substrate plane, and position on the wafer surface, are considered in the analysis, as well as the variation of film density with incidence angle. Advantages and limitations of the proposed process are discussed. It is shown that sidewalls electrodes isolated or connected to top or bottom electrodes can be simply achieved by a suitable sizing and alignment of the shadow mask but that close electrodes on a given sidewall cannot be mutually isolated when the substrate is rotated. The patterning process is demonstrated in the case of Au/Cr electrodes on the sidewalls of through wafer trenches made in GaAs by deep reactive ion etching.

Introduction

The ability to pattern films on vertical or highly tilted sidewalls of etched 3D microstructures can be greatly beneficial for many kinds of devices and advanced packaging technologies [START_REF] Westerik | Sidewall patterning-a new wafer-scale method for accurate patterning of vertical silicon structures[END_REF][START_REF] Vijselaar | Spatial decoupling of light absorption and catalytic activity of Ni-Mo-loaded high-aspect-ratio silicon microwire photocathodes[END_REF][START_REF] Xu | Vertical sidewall electrodes monolithically integrated into 3D glass microfluidic chips using water-assisted femtosecond-laser fabrication for in situ control of electrotaxis[END_REF][START_REF] Morii | Proposal of High-Density Packaging Construction and Conductive Pattern Forming Method on Vertical Wall Using Spray Coating Technology[END_REF][START_REF] Yamaguchi | Thermocouples fabricated on trench sidewall in microfluidic channel bonded with film cover[END_REF][START_REF] Kumagai | Light-absorbent liquid immersion angled exposure for patterning 3D samples with vertical sidewalls[END_REF][START_REF] Borden | Silicon solar cell with a novel low-resistance emitter structure[END_REF][START_REF] Burckel | Oblique patterned etching of vertical silicon sidewalls[END_REF][START_REF] Burckel | Micrometer-Scale Cubic Unit Cell 3D Metamaterial Layers[END_REF][START_REF] Morishita | A three-dimensional silicon shadowmask for patterning on trenches with vertical walls[END_REF]. In the last ten years, various processes were proposed to pattern bare or coated surfaces on the sidewalls of trenches or microstructures with vertical sidewalls. Recently, a process based on conformal deposition of three LPCVD masking layers (SiO2, SiNx and Poly Si), on selective chemical etchings steps and on tilted ion milling was used to remove the top part, middle part or bottom part of an underlying SiO2 layer deposited on the sidewalls of microstructures like pillars [START_REF] Westerik | Sidewall patterning-a new wafer-scale method for accurate patterning of vertical silicon structures[END_REF]. This SiO2 patterning technique was used as a mask for electroplating Ni-Mo layers on Si microwires to fabricate photocathodes [START_REF] Vijselaar | Spatial decoupling of light absorption and catalytic activity of Ni-Mo-loaded high-aspect-ratio silicon microwire photocathodes[END_REF]. This process can be applied at wafer scale to high aspect ratio microstructures of any shape with apertures around them having an aspect ratio up to 5 or more. It has a high patterning resolution but requires a large number of deposition and etching steps. In the case of a photosensitive glass structure, sidewalls electrodes could be patterned by water assisted femto laser spatial etching followed by Au/Cr electroless plating [START_REF] Xu | Vertical sidewall electrodes monolithically integrated into 3D glass microfluidic chips using water-assisted femtosecond-laser fabrication for in situ control of electrotaxis[END_REF]. For patterning films with an aspect ratio close or lower than 1, simpler processes based on exposure, etching or deposition at oblique incidence can be used [START_REF] Morii | Proposal of High-Density Packaging Construction and Conductive Pattern Forming Method on Vertical Wall Using Spray Coating Technology[END_REF][START_REF] Yamaguchi | Thermocouples fabricated on trench sidewall in microfluidic channel bonded with film cover[END_REF][START_REF] Kumagai | Light-absorbent liquid immersion angled exposure for patterning 3D samples with vertical sidewalls[END_REF][START_REF] Borden | Silicon solar cell with a novel low-resistance emitter structure[END_REF][START_REF] Burckel | Oblique patterned etching of vertical silicon sidewalls[END_REF][START_REF] Burckel | Micrometer-Scale Cubic Unit Cell 3D Metamaterial Layers[END_REF][START_REF] Morishita | A three-dimensional silicon shadowmask for patterning on trenches with vertical walls[END_REF]. If the film is deposited by a conformal technique, patterning can be achieved by combining photoresist spray coating, the use of a standard photolithographic mask, tilted UV exposure and etching [START_REF] Morii | Proposal of High-Density Packaging Construction and Conductive Pattern Forming Method on Vertical Wall Using Spray Coating Technology[END_REF][START_REF] Yamaguchi | Thermocouples fabricated on trench sidewall in microfluidic channel bonded with film cover[END_REF]. This process was recently improved by using immersion lithography with an absorbing ink to limit parasitic reflections [START_REF] Kumagai | Light-absorbent liquid immersion angled exposure for patterning 3D samples with vertical sidewalls[END_REF]. Issues related to thickness non uniformity of resist spray coating might be overcome by using the resist coating process proposed in [START_REF] Wasa | Patterning vertical sidewall using standard aligner[END_REF] which relies on the bending by stiction of photoresist cantilevers fabricated over the trench. Another way to perform film patterning on vertical sidewalls could be to pattern the conformal film by tilted reactive ion etching through an inorganic apertured membrane [START_REF] Borden | Silicon solar cell with a novel low-resistance emitter structure[END_REF]. For directional film deposition techniques like evaporation, tilted deposition is a convenient method [START_REF] Borden | Silicon solar cell with a novel low-resistance emitter structure[END_REF][START_REF] Burckel | Oblique patterned etching of vertical silicon sidewalls[END_REF][START_REF] Burckel | Micrometer-Scale Cubic Unit Cell 3D Metamaterial Layers[END_REF]. If elecrodes are needed only on the top parts of the device and microstructure, a maskless process using shadowing effect by the adjacent structure might be sufficient [START_REF] Borden | Silicon solar cell with a novel low-resistance emitter structure[END_REF]. Nevertheless, in the general case, a shadow mask is required. The shadow mask can be an apertured membrane fabricated and aligned on the device [START_REF] Burckel | Oblique patterned etching of vertical silicon sidewalls[END_REF], or an external single level or multilevel silicon shadow mask mechanically aligned on the device wafer [START_REF] Burckel | Micrometer-Scale Cubic Unit Cell 3D Metamaterial Layers[END_REF].

In this work, we investigate a version of the patterning technique based on tilted evaporation through a shadow mask that is greatly simplified thanks to the use of a dry photoresist film for the shadow mask. We initially proposed this process for the patterning of Au/Cr electrodes on the sidewalls of a piezoelectric semi-insulating GaAs 3 axis gyroscope microstructure, to allow vertical motion detection [START_REF] Piot | Electromechanical and process design of a 3 axis piezoelectric MEMS gyro[END_REF]. In this paper we provide a detailed description and analysis of this deposition and patterning process notably in the case of wafer rotation during deposition. Principle and implementation are detailed in section 2. Then, in section 3, we provide a full modelling of the process to determine the shape, the thickness and the density distribution of the lateral electrode. It is compared in section 4 to experimental results in the case of Au/Cr patterns deposited on the sidewalls of deep trenches made by deep reactive etching in GaAs.

Principle and implementation of the patterning process

The principle of the investigated deposition and patterning process of a film on the sidewall of an aperture made in a wafer or a microstructure is depicted in figure 1 in various cases. It is based on the combination of tilt evaporation and shadow masking. The drawings are cross sections in the plane of incidence. The flow of atoms bounded by the shadow mask and arriving on the sidewall at the beginning of the deposition process is schematically drawn. There is a slight shadow mask aperture reduction by film deposition on the top and on the sidewall of the shadow mask. It leads to a thickness gradient at the top and bottom edges of the deposited pattern on the sidewall. This effect will be neglected in this paper because we will only consider the case where the film thickness is much lower than the mask aperture and trench height. Figure 1(a) corresponds to the patterning of an isolated lateral electrode and a non rotating substrate. The pattern geometry is defined by the oblique incidence 𝜃, the width 𝑊 of the trench and the shadow mask overhangs (𝐿 1 and 𝑊 -𝐿 2 ). Without rotation, the pattern thickness is expected to be dependent on its position on the wafer [START_REF] Pulker | Coatings on Glass 2 nd edn[END_REF][START_REF] Bosch | Computer-aided procedure for optimization of layer thickness uniformity in thermal evaporation physical vapor deposition chambers for lens coating[END_REF]. When the substrate is rotated like in figure 1(b), the pattern geometry on the opposite sidewall will be different if 𝐿 1 ≠ 𝑊 -𝐿 2 . This must be taken into account in the electrodes layout design. When the left overhang is zero or negative, the sidewall electrode can be connected to a top electrode (see figure 1(c)). Likewise, when 𝜃 is well chosen, according to the length 𝑊 -𝐿 2 of the right overhang, a connection can be achieved to an electrode at the rear surface of the wafer, like in figure 1(d), or to an electrode at the bottom of the trench, like in figure 1(e). For a through wafer opening, connection of a sidewall film to a film deposited at the rear surface can also be achieved by using configuration of figure 1(c) after flipping the wafer. Figure 1 shows that this patterning process is quite versatile but needs a careful electrode layout and shadow mask design notably when the substrate is rotated. A modelling of the dependence of pattern geometry on shadow mask parameters with and without rotation is given in section 3. The practical implementation of the patterning process is shown in figure 2. Instead of using an external Si shadow mask or a membrane fabricated on the etched wafer as in previous works [START_REF] Burckel | Micrometer-Scale Cubic Unit Cell 3D Metamaterial Layers[END_REF][START_REF] Morishita | A three-dimensional silicon shadowmask for patterning on trenches with vertical walls[END_REF], we use a dry photoresist film laminated on the etched wafer (figure 2(a)) which is then patterned by UV photolithography with a standard aligner (figure 2(b)). This leads to an aligned shadow mask on the wafer after developpement (figure 2(c)). Then the wafer is introduced in an e-beam evaporation set-up allowing deposition under oblique incidence (figure 2(d)). Contrary to an external shadow mask mechanically aligned, the dry film shadow mask can only be used once but its optical alignement with an UV masker is more accurate and without the risk of damaging the microstructures. It is also easier to make than a direct fabrication of a membrane on the etched wafer. Indeed membrane fabrication requires the filling of apertures and a planarisation step before resist coating and photolithography [START_REF] Burckel | Oblique patterned etching of vertical silicon sidewalls[END_REF][START_REF] Burckel | Micrometer-Scale Cubic Unit Cell 3D Metamaterial Layers[END_REF]. Experimental details and results will be given in section 4.

Modelling of the patterning process

The aim of this section is to predict the shape and thickness distribution of the film deposited on the sidewall of a trench. It depends on the geometric parameters of the e-beam evaporator, notably the tilt angle, on the size and alignment of the aperture in the dry film shadow mask, and on the position of the trench on the wafer. We will first analyse the case of tilted deposition on the wafer surface, then we will consider the case of sidewall deposition without rotation of the wafer. Finally, we will study the impact of a rotation of the wafer.

Modelling of tilted deposition

The dependence on oblique incidence of incoming evaporated species of the deposition rate was modelled for the e-beam evaporation set-up used (PLASSYS Bestek 550S). The geometrical configuration during deposition at oblique incidence is schematically drawn in figure 3. In this set up, the tilt axis is not in the wafer plane: the center of rotation O of the wafer holder for deposition at oblique incidence is at a distance 𝑅 to the wafer surface center O'. Consequently, during tilting, the wafer undergoes a non negligible translation in 𝑥 direction and the true oblique incidence 𝜃 on the wafer surface is different from the tilt angle 𝛽 even in the centre of the wafer. The mininum distance between the wafer surface centre and the crucible occurs at normal incidence and is equal to 𝐻 -𝑅. It is considered sufficiently large (650 mm) with respect to the crucible diameter (17 mm), the radius 𝑅 (62.5 mm) and the wafer radius (50 mm) to allow the crucible to be approximated as a small area directed source for all points P on the wafer surface. Let us consider a point P on the wafer top surface with polar coordinates 𝜌 and 𝛼, at a distance r from the crucible, at an angle 𝜙 with respect to the crucible normal, and with oblique incidence 𝜃 (see figure 3). It can be shown that the deposited thickness 𝑡 is given by [START_REF] Pulker | Coatings on Glass 2 nd edn[END_REF][START_REF] Bosch | Computer-aided procedure for optimization of layer thickness uniformity in thermal evaporation physical vapor deposition chambers for lens coating[END_REF][START_REF] Holland | The distribution of thin films condensed on surfaces by the vacuum evaporation method[END_REF][START_REF] Wang | Layer uniformity of glancing angle deposition[END_REF][START_REF] Wang | Simulation and Optimization of Film Thickness Uniformity[END_REF].

𝑡 = 1 𝜇 d𝑚 d𝐴 = 𝑚 𝜋𝜇 ( 𝑛+1 2 ) cos 𝜃 cos 𝑛 𝜙 𝑟 2 (1)
where 𝑚 is the total mass of evaporated material, 𝜇 the film density, and 𝑛 an exponent that depends on evaporation conditions. In the following we will consider 𝑛 = 1. This is valid for low deposition rates and crucibles with low depth to diameter ratio [START_REF] Wang | Simulation and Optimization of Film Thickness Uniformity[END_REF]. Let P' be the intersection of the normal at point P and the crucible plane and S be the crucible centre (see figure 3). If ∧ denotes the vector product and (|) the scalar product, 𝜃 can be expressed, after some trigonometric computations, as a function of the coordinates of point 𝑃, of the tilt angle 𝛽, and of the geometric parameters 𝐻 and 𝑅: Tops of the hyperbolas are connected by a dashed line to better show the assymetry of pattern shape when the aperture is not in the (𝑥𝑂𝑧) plane.

tan 𝜃 = ‖𝑃𝑃 ′ ⃗⃗⃗⃗⃗⃗⃗⃗ ∧𝑃𝑆 ⃗⃗⃗⃗⃗ ‖ (𝑃𝑃 ′ ⃗⃗⃗⃗⃗⃗⃗⃗ |𝑃𝑆 ⃗⃗⃗⃗⃗ ) (2a) = [(𝜌 sin 𝛼) 2 +(𝐻 sin 𝛽+𝜌 cos 𝛼) 2 ] 1 2 𝐻 cos 𝛽-𝑅 (2b)
In the following, we will consider the point 𝑃 to be on the sidewall of a straight trench partially covered with a dry film creating an overhang. To simplify the computations, we will assume that the direction of the trench is initially perpendicular to the plane (𝑥𝑂𝑧) (see figure 3). A trench filling this condition is shown in figure 4. This means that, to apply the model without rotation described in the next section, the orientation of the wafer on the wafer holder must be carefully adjusted before deposition. In addition, we will consider that the mask aperture is centred with respect to (𝑥𝑂𝑧) plane so the angle 𝛼 is equal to zero. We will see later that this is not a large limitation of the model as long as 𝜌 is low with respect to distance r, and angle 𝛽 is sufficiently large.

Case of a non-rotating wafer

In the case of a non-rotating wafer the pattern thickness is expected to be quasi-uniform along the trench as its length is usually very low with respect to its distance to the crucible. Another film deposition after a 180° rotation of the wafer would be needed to pattern electrodes on the opposite sidewall. Likewise, other depositions after rotations of 90° and -90° would be required for the patterning of electrodes on the sidewalls of perpendicular trenches.

It is clear from figure 5 that the vertical location and size of the pattern depends on the overhang 𝐿 1 , on the opening 𝐿 2 -

𝑊 ≥ 𝐿 2 > 𝐿 1 ≥ 0 (3)
is filled, the depths 𝑑 1 and 𝑑 2 are simply related to 𝐿 1 and 𝐿 2 by:

{ 𝐿 1 = 𝑑 1 tan 𝜃 𝐿 2 = 𝑑 2 tan 𝜃 (4)
Consequently:

𝐿 1 𝑑 1 ⁄ = 𝐿 2 𝑑 2 ⁄ (5)
and:

𝜃 = tan -1 (𝐿 1 𝑑 1 ⁄ ) = tan -1 (𝐿 2 𝑑 2 ⁄ ) (6)
To maximize the film deposition rate and density, the angle of incidence on the sidewall must be minimized and thus the value of 𝜃 (0 ≤ 𝜃 < 90°) must be maximized. Consequently, according to equation ( 6), the values of 𝐿 1 and 𝐿 2 must be maximized while keeping true the conditions (1) and ( 5). The optimized solution is:

𝐿 2 = 𝑊, 𝐿 1 = 𝐿 2 𝑑 1 𝑑 2 ⁄ , 𝜃 = tan -1 (𝑊 𝑑 2 ⁄ ) (7)
Using equation [START_REF] Vijselaar | Spatial decoupling of light absorption and catalytic activity of Ni-Mo-loaded high-aspect-ratio silicon microwire photocathodes[END_REF], it is possible to compute the associated angle 𝛽. Note that once 𝛽 is set, the dimensions 𝐿 1 and 𝐿 2 must be adapted for trenches elsewhere on the wafer because 𝜃 depends on the coordinates (𝜌, 𝛼) of the considered position on the wafer.

To get a connection with a top electrode with a recess e (see A full connexion with a non-recessed bottom electrode on the rear surface can be achieved by using the conditions given by equation ( 7) and by setting 𝑑 2 = ℎ, where ℎ is the thickness of the wafer. If the rear electrode is recessed, the sample must be flipped during evaporation, and the condition given above for a connection to the top electrode must be used.

These different conditions might be difficult to fulfil for devices with a large range of trench widths and electrode geometries. So, devices with trenches having similar widths should be designed to apply this patterning technique. As this is also a requirement to limit aspect ratio dependent etching, in deep reactive ion etching processes, this is not so a critical issue.

Case of a rotating wafer

The case of patterning sidewall electrodes on straight trenches on a rotated wafer is much more complex but allows film deposition and patterning on every trench sidewall in a single run. As shown in figure 1(b), the pattern geometry will generally be different on the opposite side of the trench. Actually to get the same geometry, the overhang of the shadow mask must be the same on both sides of the trench, i.e. 𝐿 1 = 𝑊 -𝐿 2 . When the substrate is rotated during deposition, the pattern geometry becomes variable along the trench length. This effect can be modelled by analogy with a sundial and by using gnomonics, the art of making and using sundials [18]. Indeed, we can consider each edge of the shadow mask rectangular aperture as a gnomon of a sundial, the crucible as the sun, the trench sidewall as the sundial plate with a horizontal position at equator and the pattern shape border as the path travelled by the gnomon shadow on the sundial plate (see figure 6). Four different gnomons, corresponding to the four edges of the rectangular aperture, have to be taken into account to determine the borders of the shape on the trench. The two gnomons of length 𝐿 = 𝐿 1 delimit the top of the electrode while the two gnomons of length 𝐿 = 𝐿 2 delimit the bottom of the electrode. Equation 1 shows that the thickness, at any sample location, is the ratio of the deposited mass of the material and of its density. Both depend on the local angle of incidence of the vapour beam on the considered surface. We will first determine the pattern shape and thickness distribution on a trench sidewall from the deposited mass, then the density distribution in the pattern from the measured dependence of density with incidence angle, and finally the thickness distribution by taking into account the density distribution.

For the mathematical modelling, it is more convenient to consider the crucible rotating and the sample fixed as shown in figure 7. Each pattern border is then a conic corresponding to the intersection of the sidewall of the trench and the cone described by the point 𝐴 as the apex (the end of the gnomon) and by the circle made by the crucible centre 𝑆 around the rotation axis.

The initial orientation of the wafer at rotation angle 𝜁 = 0° is chosen such as the trench is perpendicular to the plane (𝑥𝑂𝑧). 𝑂′′ is the point at the corner on the top of the trench.

In the new frame of reference (𝑂′′𝑋𝑌𝑍), we can express the coordinates of points 𝐴, 𝑆 and 𝐷, where 𝐷 is the centre of the circle made by 𝑆 during rotation (see figure 7).

𝐴: (𝑋 𝐴 , 𝑌 𝐴 , 𝑍 𝐴 ) = (𝐿, 0,0) 𝑆: (𝑋 𝑆 , 𝑌 𝑆 , 𝑍 𝑆 ) = (𝐻 sin 𝛽 + 𝜌 cos 𝛼 , 𝜌 sin 𝛼 , 𝐻 cos 𝛽 -𝑅ℎ)

𝐷: (𝑋 𝐷 , 𝑌 𝐷 , 𝑍 𝐷 ) = (𝜌 cos 𝛼 , 𝜌 sin 𝛼 , 𝐻 cos 𝛽 -𝑅 -ℎ)

To predict the pattern shape on the sidewall, we will use a mathematical procedure valid in the general case but to simplify the mathematical expressions, we will establish the analytical formula only in the case 𝛼 = 0° represented in figure 4 for the central aperture. We will see later that this is an acceptable simplification of the general case. We thus rewrite the coordinates of points 𝐴, 𝑆 and 𝐷 in the case

The conic described by the shadow of the gnomon is the intersection between the cone from equation [START_REF] Wasa | Patterning vertical sidewall using standard aligner[END_REF] and the plane (𝑌𝑂′′𝑍) ⇔ 𝑋 = 0. By using equations (9a), (9b), (9c) and [START_REF] Wasa | Patterning vertical sidewall using standard aligner[END_REF] we find the equation of the conic in the frame of reference(𝑂′′𝑋𝑌𝑍):

(𝜌-𝐿) 2 -𝐻 2 sin 2 𝛽 (𝐻 cos 𝛽-𝑅-ℎ) 2 𝑍 2 + 𝑌 2 + 2𝐿 𝜌-𝐿 𝐻 cos 𝛽-𝑅-ℎ 𝑍 + 𝐿 2 = 0 (12)
This equation has a physically valid solution, i.e. with negative 𝑍, if one of the following conditions is true:

0 ≤ 𝐿 < 𝜌 (13) |sin 𝛽| > |𝜌-𝐿| ℎ 0 (14)
A negative value of 𝐿 would correspond to the other side of the trench (not represented in figure 7 to simplify the drawing) with 𝐿 = 𝐿 2 -𝑊 for the top border of the pattern shape and 𝐿 = 𝐿 1 -𝑊 for the bottom border. If equation ( 14) is true, the border of the pattern shape on the sidewall is a hyperbola. This is the common case. If equation ( 13) is true, the pattern shape depends on another condition. If equation ( 15) is a strict inequality, the pattern shape is an ellipse, whereas if it is an equality, the pattern shape is a parabola. Usually, the overhang length is much lower than the wafer radius (𝐿 ≪ 𝜌). In that case, we can compute the maximum angle 𝛽 𝑚𝑎𝑥 = sin -1 (𝜌 ℎ 0 ⁄ ) to get an ellipse. For 𝜌 = 50 mm this would give 𝛽 𝑚𝑎𝑥 = 4°. This case is not convenient in practise because for such a tilt, the film deposition rate and density on the sidewalls would be very low.

Figure 8 shows the computed pattern shape for a chosen set of deposition parameters close to the ones used in our experiments. When compared to the pattern shape without rotation (dot-dash line), its bottom is strongly deformed whereas its top is similar in the common width range. The presence of the hyperbolas in the rectangular area shows that the rotation also influences this zone by shading some parts.

The calculation above was made for a mask aperture centred in the trench like the one in the middle in figure 4. The effect of a lateral shift of the aperture is illustrated in the top of figure 4. It leads to an asymmetry of the hyperbolas that depends on the sign of coordinate 𝑦 = 𝜌 sin 𝛼 of the aperture. The deformation is visible, especially for low value of 𝛽, but it remains small when 𝜌 is small with respect to the distance 𝑟 between the crucible and the considered location 𝑃. Adding the fact that 𝛽 is often higher than 20°, the simplifying assumption 𝛼 = 0° is generally a good approximation for the modelling of the pattern shape. In the case of non-rotating wafer (section 3.2), the amplitude of deformation is even lower because the surface of the sidewall exposed to vapour beam is smaller.

Beside a pattern shape distortion, the deposited film thickness and density are not uniform because the incidence angle and the deposited mass of metal vary with position. To compute the thickness distribution in the pattern shape, we use equation ( 1) but we replace cos 𝜃 by cos 𝜓 (see figure 7) because the deposition is done on the sidewall. We also simplify the equation by considering the approximation 2 and ‖𝑂 ′′ 𝑃 ⃗⃗⃗⃗⃗⃗⃗⃗ ‖ is less than the length of the trench which is usually far less than (𝐻 -𝑅ℎ) 2 . So the deposited thickness on the sidewall is given by:

‖𝑆𝑃 ⃗⃗⃗⃗ ‖ ≈ ‖𝑆𝐴 ⃗⃗⃗⃗⃗ ‖. Indeed we have ‖𝑆𝑃 ⃗⃗⃗⃗ ‖ 2 = ‖𝑆𝐴 ⃗⃗⃗⃗⃗ ‖ 2 + ‖𝐴𝑂′′ ⃗⃗⃗⃗⃗⃗⃗⃗ ‖ 2 + ‖𝑂 ′′ 𝑃 ⃗⃗⃗⃗⃗⃗⃗⃗ ‖ 2 with ‖𝑆𝐴 ⃗⃗⃗⃗⃗ ‖ 2 > (𝐻 -𝑅 -ℎ) 2 while ‖𝐴𝑂′′ ⃗⃗⃗⃗⃗⃗⃗⃗ ‖ 2 = 𝐿 2 ≪ (𝐻 -𝑅 -ℎ)
𝑡 = 𝑚 𝜋𝜇 cos 𝜓 cos 𝜙 ‖𝑆𝑃 ⃗⃗⃗⃗⃗ ‖ 2 ≈ 𝑚 𝜋𝜇 cos 𝜓 cos 𝜙 ‖𝑆𝐴 ⃗⃗⃗⃗⃗ ‖ 2 (16)
In equation ( 16), the density 𝜇 is dependent on the incidence angle 𝜓 but we will first consider it constant along the trench. We express the coordinates of the points 𝑆, 𝐴 and 𝑂 in the frame of reference (𝑂′′𝑋𝑌𝑍) but we now take into

The insertion of equations ( 18), ( 19) and (20) into equation ( 16) allows the determination of the thickness variation 𝑡(𝜁). To take into account the deposition at different values of 𝜁 during rotation, we integrate 𝑡(𝜁). For each point within the pattern shape (figure 8) and each angle 𝜁 between -𝜋 and 𝜋, we numerically compute the intersection point between the line (𝑆𝑃) and the plane (𝑋𝑂′′𝑌) ⇔ 𝑍 = 0. If this point is inside the mask aperture, the vapour beam reaches the sidewall. So we compute the associated thickness 𝑡(𝜁) and use it for the integration, otherwise, we ignore it. In figure 9, the result of such integration is shown for a chosen set of parameters. It gives the thickness distribution in the pattern when the sample is rotated. As we considered a constant density 𝜇, we normalized the thickness to its maximum value. Figure 9 shows that for the chosen deposition parameters, the film thickness decreases by more than 60 % in the targeted area and continues to decrease along the hyperbolas.

Actually the density 𝜇 is not constant in the deposited area. In order to evaluate the variation of the density as a function of the incidence angle, three deposits Au/Cr were done with 𝛽 = 0°, 30° and 60° on a plain wafer. The targeted thickness were 200 nm at 0.3 nm s -1 for the gold film and 20 nm at 0.1 nm s -1 for the chromium adhesion promoting sublayer. Thanks to a Sartorius microbalance having a 0.3 µg repeatability, the gold film density was measured by weighting 1 cm 2 coated Si dies at the centre of the wafer before and after selective Au layer etching in a KI:I2:H2O bath. For the simulation, the Au film density was arbitrarily fitted by a 2 nd degree polynomial to estimate its value between the measurement points (Figure 10).

By using this polynomial and equation (20), we can plot the map of a one turn average of the density 𝜇 in the deposited area (figure 11). It is quite constant in the targeted area and decreases along the hyperbolas arms. Then, by using equation ( 16), the normalized thickness distribution can be evaluated by taking into account the variation of film density μ. The result is shown in figure 12. When compared with figure 9 where 𝜇 is supposed constant, the thickness in the hyperbolas arms is slightly higher, as expected from figure 11. For example, it increases the size in the arms of the 0.1 normalized level contours. Nevertheless, it finally does not change the general predicted pattern shape of the deposited electrode on the sidewall.

Implementation and results of the patterning process

The proposed process was applied to the patterning of lateral electrodes on structures with trenches around fabricated by bulk micromachining of 450 µm thick semiinsulating GaAs wafers. This substrate material was chosen because the patterning process was initially intended as a fabrication step of a 3 axis GaAs piezoelectric gyroscope [START_REF] Piot | Electromechanical and process design of a 3 axis piezoelectric MEMS gyro[END_REF]. Deep reactive ion etching (DRIE) in BCl3/Cl2 plasma was used as the etching technique. Various geometries were investigated with narrow or wide lateral electrodes connected to top electrodes. In all cases, rotation of the wafer holder was activated during deposition. After fabrication, the samples were inspected with a Keyence VHX-5000 digital optical microscope.

Shadow mask fabrication

The dry film used for shadow mask fabrication is a MX5015 negative photoresist from Dupont company having a thickness of 15 µm. Its top face is protected by a polyester film and its bottom face by a polyethylene (PET) film. Dry film lamination with bottom PET film removal was performed on 100 mm in diameter semi-insulating GaAs wafers with a laminator (Model 4200 from Think and Tinker company). After some preliminary tests, the heating roll temperature was adjusted to 100 °C and the lamination roll speed to 5 rpm. The roll pressure was set to its minimum value in order to reduce the risk of breaking the device. This is also favourable to a lower deformation of the dry film. By using a recessed wafer holder during dry film lamination (see figure 2(a)), this lamination could be made on wafers with deep trenches or through-wafer etched areas without breaking. After lamination the coated wafer was transferred to an EVG 620 mask aligner. The dry film was exposed to UV with a total dose of 50 mJ cm -2 then baked 5 min at 100 °C on a hot plate. The protective polyester film was then peeled off and the dry film was developed in a MRD4000 bath for 1 min 30 s.

These conditions lead to resist patterns with quasi vertical sidewalls and a minimum pattern size larger than 5 µm. This shadow mask is thus only suitable for relatively large apertures. Dry films with a thickness down to 5 µm are available so shadow masks compatible with smaller trenches and patterns could be done. However, thinner is the dry film, larger might be its deformation induced by mechanical stress generated by its processing or by the evaporated film stress.

Figures 13 and14 show optical microscope pictures of narrow and wide apertures made in a dry film over 300 µm wide through wafer trenches. White lines can be observed in the dry films over the trenches. They are due to reflectance variations by ripples of the dry film. These ripples are more or less sinusoidal in the dry film overhangs along the trench borders (see figure 14). They can be attributed to dry film buckling induced by compressive stress generated during dry film processing. Phase shifting interferometry measurements showed that these ripples have an amplitude of a few hundreds of nm. They are expected to degrade the pattern shape on the sidewall by a similar amount. Over large trenches, an additional downward deflection of the dry film was also observed. For example, a 1 µm general bow was measured over a 300 µm wide trench. Nevertheless, the dry film adhesion remained good enough to make apertures over 300 µm wide trenches without observing dry film delamination.

Film patterning on vertical sidewalls of trenches

Au/Cr film deposition was performed in a Plassys Bestek 550S e-beam evaporation set-up which allows a tilt angle in the 0 to 90° range. High purity Cr and Au pellets were sucesssively evaporated after outgassing from 15 cm 3 alumina crucibles. The background pressure was 1.3x10 -8 mbar before evaporation and 1.3x10 -7 mbar during evaporation. This evaporation set-up is equipped with a quartz microbalance that allows a monitoring of the deposition rate that would occur at normal incidence. It was calibrated from thickness measurements of films deposited on flat Si wafers without tilt.

The etched GaAs dies covered with dry films have an area of about 1x1 cm 2 . They were placed at the centre of the wafer holder. The film depositions were performed with a tilt angle 𝛽 = 46° and a wafer rotation speed of 5 rpm. The selected deposition conditions provide, at normal incidence, a 10 nm thick chromium adhesion promoting layer with an evaporation rate of 0.1 nm s -1 , and a 400 nm thick gold film with a deposition rate of 0.3 nm s -1 .

Figure 15 shows lateral electrodes deposited all around a free-clamped beam on half of its thickness. The bottom border of the lateral electrode does not appear sharp even at this scale because GaAs DRIE, contrary to Si DRIE, produces trenches with a high sidewalls surface roughness. The lateral electrode border (not visible in figure 15) presents a hyperbolic deformation but it remains small with respect to the length of the electrode. Nevertheless, this result demonstrates that this patterning process is suitable for the design of long lateral electrodes only connected to the top electrode on both sides of trenches.

As shown above in figure 12, for rotated substrates and narrow apertures, the model detailed in section 3.3 predicts a decrease of the deposited film thickness and density on a trench sidewall outside the shadow mask opening. On a rough surface and for a non-conformal deposition technique like evaporation, this density reduction is larger because of local shadowing effects by asperities. A direct comparison of the model with experiments is quite difficult because there is not a common technique able to measure thickness distribution of a metallic film on a rough trench sidewall. Nevertheless, we can clearly observed in figure 16 that the optical contrast between the Au film and the GaAs surface is a decreasing function of the distance to the shadow mask opening. Optical calculation showed that both the normal incidence optical reflectance of a gold film and its contrast on a smooth GaAs surface become high only for wavelengths in the visible-NIR range above about 0.55 µm. In this wavelength range, the reflectance contrast decreases rapidly when the gold film thickness is lower than about 50 nm. From the optical microscopy image of figure 16, we could then very roughly estimate that the film thickness is lower than 50 nm beyond a lateral distance equal to ≈75 µm and a vertical distance equal to ≈150 µm from the shadow mask edge. Actually, the light absorption of an Au film is decreasing with film density so this distance can be significantly underestimated.

A major limitation of the investigated process for patterning lateral electrodes is illustrated in figure 17. When two narrow electrodes are located on the same sidewall, the hyperbolic deformation of the patterned electrodes induced by wafer rotation during deposition can create an electric short circuit, even with a quite large space between them. This must be considered during the mask layout design or a slight metal film etch has to be performed after deposition. Another way to overcome this limitation could be to change the shape of the mask aperture or of the sidewall.

Conclusion

A simple process applicable at the wafer scale and allowing the deposition and alignment of patterned electrodes on the sidewalls of microstructures is demonstrated and analyzed in details. It is based on tilted evaporation through a dry film photoresist shadow mask having a specific design. The sidewall patterns can be connected or not to bottom or top electrodes by a suitable alignement of the shadow mask edges. The proposed process can be applied to any evaporated films that must be patterned on the vertical walls of trenches with a width approximately equal to 1/3 to 1/2 of the dry film thickness. A first specific limitation of the process is the stress-induced distorsion of the dry film shadow mask edges during dry film processing. This issue might be increased or decreased by the deposited film residual stress. Rotation of the wafer during the evaporation allows the deposition and patterning of films on every sidewalls simultaneously but it leads to a hyperbolic deformation of the laterak electrode borders. This must be considered in the mask design or corrected after deposition. A mathematical model predicting the shape and the thickness of a lateral electrode with or without rotation has been developed. It could be applied or adapted to all patterning processes based on tilt deposition, tilt etching or tilt lithography.

Figure 1 .

 1 Figure 1. Principle of the patterning process. (a) Isolated sidewall film pattern, (b) Film patterns on both sidewalls (𝜔 > 0), (c) Sidewall film pattern connected to a top film, (d) Sidewall film pattern connected to a bottom film, (e) Sidewall film pattern connected to a film at the bottom of the aperture.

Figure 2 .

 2 Figure 2. Flowchart of the patterning process.

Figure 3 .

 3 Figure 3. Geometry of film deposition at oblique incidence (Not to scale, 𝐻 divided by a factor 4).

Figure 4 .

 4 Figure 4. A wafer with an etched trench covered by dry film observed from behind the crucible (not to scale). For three apertures in the dry film, corresponding hyperbolas on the sidewall created by rotation of the wafer holder (see section 3.3) are plotted for 𝛽 ranging from 10° (bottom line) to 60° (top line) with steps of 10°. Tops of the hyperbolas are connected by a dashed line to better show the assymetry of pattern shape when the aperture is not in the (𝑥𝑂𝑧) plane.

Figure 5 .

 5 Figure 5. Pattern geometry defined by shadow masking with tilted deposition without wafer rotation 𝐿 1 of the shadow mask and on incidence angle 𝜃.It can be seen that the thickness of the shadow mask has no effect on the top border of the sidewall film pattern but it shifts upward its lower border: it reduces 𝑑 2 by an amount equal to the shadow mask thickness. Likewise, film deposition on the top of the dry film gradually shifts the lower border of the patternn and film deposition on the dry film edge gradually shifts the upper border of the pattern. To simplify the computations, we will consider, in the following and in the next section, that 𝑡 1 , 𝑡 3 and the thickness of the dry film are equal to zero and we will neglect the effect of film deposition on the top and edge of the shadow mask. Let 𝑊 be the width of the trench. If the condition:

Figure 6 .

 6 Figure 6. Analogy of shadow masking and operation of a sundial for an edge of the shadow mask aperture.figure5) we must have 𝐿 1 ≤ -𝑒. Let us emphasize that the film porosity will be different on the top part and on vertical sidewall if the incidence angle is different from 45°. A full connexion with a non-recessed bottom electrode on the rear surface can be achieved by using the conditions given by equation (7) and by setting 𝑑 2 = ℎ, where ℎ is the thickness of the wafer. If the rear electrode is recessed, the sample must be flipped during evaporation, and the condition given above for a connection to the top electrode must be used. These different conditions might be difficult to fulfil for devices with a large range of trench widths and electrode geometries. So, devices with trenches having similar widths should be designed to apply this patterning technique. As this is also a requirement to limit aspect ratio dependent etching, in deep reactive ion etching processes, this is not so a critical issue.

Figure 7 .

 7 Figure 7. Half section of a trench of height ℎ and its overhang of length 𝐿 on a rotating wafer when 𝜁 = 0°. 𝑆′ is the image of 𝑆 by a rotation of 180°, 𝐷 is the centre of the circle passingby 𝑆 and 𝑆′. 𝐴 is the point at the end of the dry film. The trajectory of the point 𝑃 on the sidewall is a conic. Note that a new reference (𝑋𝑌𝑍) different from (𝑥𝑦𝑧) presented in figures 3 and 4 is used.

Figure 8 .

 8 Figure 8. Shape of the lateral deposit with width aperture of 150 µm and parameters: 𝐿 1 = 50 µm, 𝐿 2 = 250 µm, 𝑊 = 300 µm, 𝜌 = 0 mm, 𝛽 = 41.4° and ℎ = 450 µm. where 𝛼 = 0°: 𝐴: (𝑋 𝐴 , 𝑌 𝐴 , 𝑍 𝐴 ) = (𝐿, 0,0) (9a) 𝑆: (𝑋 𝑆 , 𝑌 𝑆 , 𝑍 𝑆 ) = (𝐻 sin 𝛽 + 𝜌, 0, 𝐻 cos 𝛽 -𝑅 -ℎ) (9b) 𝐷: (𝑋 𝐷 , 𝑌 𝐷 , 𝑍 𝐷 ) = (𝜌, 0, 𝐻 cos 𝛽 -𝑅 -ℎ)(9c)We express the equations of the lines (𝐴𝑆) and (𝐴𝐷).(𝐴𝑆) { 𝑌 = 0 𝑍 𝑆 (𝑋 -𝐿) + (𝐿 -𝑋 𝑆 )𝑍 = 0 ⇔ 𝑋 = 𝐿 + 𝑋 𝑆 -𝐿 𝑍 𝑆 𝑍 (10a)

Figure 9 .

 9 Figure 9. Film thickness normalized distribution in a trench sidewall pattern when the film density 𝜇 is considered constant. Same deposition parameters as for figure 8.

Figure 10 .

 10 Figure 10. Measured film density as function of incidence angle. into account the rotation angle 𝜁 of the wafer: 𝐴: (𝐿, 0,0) 𝑆: (𝐻 sin 𝛽 cos 𝜁 + 𝜌, -𝐻 sin 𝛽 sin 𝜁 , 𝐻 cos 𝛽 -𝑅 -ℎ) (17) 𝑂: (𝜌, 0, -𝑅 -ℎ) We compute the distance ‖𝑆𝐴 ⃗⃗⃗⃗⃗ ‖ 2 as: ‖𝑆𝐴 ⃗⃗⃗⃗⃗ ‖ 2 = 𝐻 2 + (𝑅 + ℎ) 2 + (𝜌 -𝐿) 2 +2𝐻((𝜌 -𝐿) sin 𝛽 cos 𝜁 -(𝑅 + ℎ) cos 𝛽) (18)

Figure 11 .

 11 Figure 11. Estimation of one turn average density 𝜇 of a lateral deposit. Same deposition parameters as for figure 8.

Figure 12 .

 12 Figure 12. Film thickness normalized distribution in a trench sidewall pattern when the variation of the deposited film density 𝜇 with angle of incidence is taken into account. Same deposition parameters as for figure 8.

Figure 13 .

 13 Figure 13. (a) Schematic 3D drawing of deep trenches in a GaAs wafer coated with a dry film masking layer.A small rectangular aperture is designed to make a connection between the top surface and a lateral side. (b) Top view image of the sample area delineated by black dashed lines in the 3D drawing. The mask aperture is shown by white dashed lines.

Figure 14 .

 14 Figure 14. (a) Schematic 3D drawing of a bulk micromachined GaAs clamped-free beam after dry film lamination and photolithography. The dry film mask is not covering the beam end to allow a connection between the top and the lateral electrodes. (b) Top view image of the sample area delineated by white dashed in the 3D drawing.

Figure 15 .

 15 Figure 15. Optical microscopy images with enhanced colors of parts of a clamped-free beams with lateral electrodes (a) before and (b) after lift-off of the dry film (noted d.f.). A connection from sidewall to top electrode is visible at the end of the beam.

Figure 16 .

 16 Figure 16. (a) Schematic 3D drawing of the expected shapes of the top and lateral electrodes on a deep trench when a rectangular mask opening like in figure 13 is used.and when the wafer is rotated during deposition. (b) Tilted view image of a trench after patterning Au/Cr electrodes through a 150 µm wide shadow mask aperture with 𝐿 1 = 0 and 𝐿 2 = 220 µm. The borders of the electrode on the trench sidewall are approximately drawn in dashed lines to show the hyperbolic-like shape of the deposited film.

Figure 17 .

 17 Figure 17. Three sets of top and lateral Au/Cr electrodes obtained with a dry film shadow mask patterned with narrow rectangular apertures.

Acknowledgements

This work was performed in the frame of two PhD theses grants supported by DGA and ONERA. Film deposition and measurements were performed in the micro/nano fabrication platform of C2N supported by the Renatech French national network. The authors wish to thank Marie-Paule Pante and David Bouville for their assistance in clean rooms for film deposition and photolithography respectively.


Jean-Claude Bermond
email: bermond@sophia.inria.fr

Laurent Braud
email: laurent.braud@ens-lyon.fr

David Coudert
email: dcoudert@sophia.inria.fr

Traffic Grooming on the Path

Keywords: Traffic grooming, graph, design theory, WDM

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Traffic grooming is the generic term for packing low rate signals into higher speed streams (see the surveys [START_REF] Dutta | Traffic grooming in WDM networks: Past and future[END_REF][START_REF] Modiano | Traffic grooming in WDM networks[END_REF][START_REF] Somani | Survivable traffic grooming in WDM networks[END_REF]). By using traffic grooming, one can bypass the electronics in the nodes for which there is no traffic sourced or destinated to it. Typically, in a WDM network, instead of having one SONET Add Drop Multiplexer (shortly ADM) on every wavelength at every node, it may be possible to have ADMs only for the wavelength used at that node, the other wavelengths being optically routed without electronic switching. For example in Figure 1 node 1 has an ADM only for wavelength w 3 , the other wavelengths (w 1 and w 2 ) being optically routed.

In the past many papers on WDM networks had for objective to minimize the transmission cost and in particular the number of wavelengths to be used [START_REF] Beauquier | Graph problems arising from wavelength-routing in all-optical networks[END_REF][START_REF] Dutta | A survey of virtual topology design algorithms for wavelength routed optical networks[END_REF][START_REF] Coudert | Lightpath assignment for multifibers WDM optical networks with wavelength translators[END_REF]; recent research has focused on reducing the total number of ADMs used in the network, trying to minimize it.

Here, we consider the particular case of paths (the routing is unique) with static uniform allto-all traffic (one request for each pair of vertices). To each request {i, j} routed on the path from i to j, we want to assign a wavelength in such a way that at most C requests use the same wavelength on a given edge of the path. Equivalently, each request uses 1/C of the bandwidth of the wavelength. C is called the grooming ratio (or grooming factor). For example, if the request from i to j is one OC-12 and a wavelength can carry an OC-48, the grooming factor is 4. Given the grooming ratio C and the path P N with N vertices, the objective is to minimize the total number of (SONET) ADMs used, denoted A(P N , C), and so reducing the network cost by eliminating as many ADMs as possible from the "no grooming case".

Figure 2 shows how to groom requests for a grooming factor C = 2 and a path P N with N = 3, 7, 9 vertices. In the figure each level represents a wavelength (1 for N = 3, 6 for N = 7 and 10 for N = 9), on each wavelength the • indicate the vertices where an ADM is put for this wavelength and the lines represented requests routed on this wavelength. For example for N = 7 we have 5 ADM's on wavelength w 1 in nodes 0,1,2,3,6 and we groom requests {0, 1}, {1, 2}, {0, 2}, {2, 3}, {3, 6}, {2, 6} on this wavelength. Note that, for C = 2, we group mainly the requests by groups of 3 ({a, b}, {b, c} and {a, c}), some groups sharing a common extremity.

For N = 3 we have 3 requests. So, if we give a priori one wavelength to each request (no grooming), we will need 2 ADMs per request and altogether 6 ADMs. However, in the case C = 1 we can use the same wavelength for the two requests {0, 1} and {1, 2}, thus using 3 ADMs for this wavelength (saving 1) and another wavelength for {0, 2} with 2 ADMs, so altogether 5 ADMs. Furthermore, when C = 2 we can use the same wavelength for the 3 requests and so need only 3 ADMs (one in each vertex).

For N = 7 we have 21 requests. So, a priori, if we give one wavelength to each request we need 42 ADMs. Using the same wavelength for disjoint requests (case C = 1), we will see after that 33 ADMs suffice. Indeed two requests may share an ADM if they have a common extremity. For C = 2 we will see that the construction given in Figure 2 is optimal and uses 6 wavelengths and 20 ADMs (note that 4 requests share the same ADM in vertex 2).

To the best of our knowledge, the problem for paths has only been studied in [START_REF] Huang | Traffic grooming in path, star, and tree networks: Complexity, bounds, and algorithms[END_REF], where it has been proved NP-complete for a general set of requests (and for given C ≥ 2) and no other results are known. Other topologies have also been considered and in particular unidirectional rings primarily in the context of variable traffic requirements [START_REF] Chiu | Traffic grooming algorithms for reducing electronic multiplexing costs in WDM ring networks[END_REF][START_REF] Dutta | On optimal traffic grooming in WDM rings[END_REF][START_REF] Goldschmidt | The SONET edge-partition problem[END_REF][START_REF] Wan | Grooming of arbitrary traffic in SONET/WDM BLSRs[END_REF][START_REF] Yuan | Wavelength assignment to minimize the number of SONET ADMs in WDM rings[END_REF]; but the case of fixed traffic requirements has also been widely studied [START_REF] Bermond | Minimizing SONET ADMs in unidirectional WDM ring with grooming ratio 3[END_REF][START_REF] Bermond | Grooming in unidirectional rings : K 4 -e designs[END_REF][START_REF] Bermond | Traffic grooming in unidirectional WDM ring networks using design theory[END_REF][START_REF] Bermond | Traffic grooming in unidirectional WDM ring networks: the all-to-all unitary case[END_REF][START_REF] Dutta | Traffic grooming in WDM networks: Past and future[END_REF][START_REF] Gerstel | Wavelength assignment in a WDM ring to minimize cost of embedded SONET rings[END_REF][START_REF] Gerstel | Cost-effective traffic grooming in WDM rings[END_REF][START_REF] Hu | Optimal traffic grooming for wavelength-division-multiplexing rings with all-to-all uniform traffic[END_REF][START_REF] Hu | Traffic grooming in WDM ring networks: A linear programming solution[END_REF][START_REF] Modiano | Traffic grooming in WDM networks[END_REF][START_REF] Wang | Improved approches for cost-effective traffic grooming in WDM ring networks: ILP formulations and single-hop and multihop connections[END_REF][START_REF] Zhang | An effective and comprehensive approach for traffic grooming and wavelength assignment in SONET/WDM rings[END_REF].

In this paper we model the grooming problem on the path as a graph partition problem. We show how a greedy algorithm gives a solution for C = 1 and any set of requests. Then, using tools of design theory, we determine exactly the number of ADMs in the case C = 2 for the all-to-all set of requests.

A preliminary version of this paper has been presented at SIROCCO'05 [START_REF] Bermond | Traffic grooming on the path[END_REF].

Modeling

Here we are given a physical graph and a set of requests I. The physical graph will be the path P N with vertex set V = {0, 1, 2, . . . , N -1} and where the edges are the pairs {i, i + 1}, 0 ≤ i ≤ N -2. The set of requests I is a set of pairs {u, v} that we model by a graph I where each edge e = {u, v} is associated to the request {u, v}. Each request is routed along the unique subpath in P N from u to v and we associate to it a wavelength w.

For a subgraph B of requests of I, we define the load of an edge e = {i, i + 1} of P N , L(B, e), as the number of requests which are routed through e, that is the number of edges {u, v} of B such that u ≤ i < v. Now let B w = (V w , E w ) be the subgraph of I containing all requests carried by wavelength w. The fact that the grooming ratio is C can be expressed as L(B w , e) ≤ C for each edge e of P N . The number of ADMs used for the wavelength w is nothing else than |V w |.

So the problem corresponds to partition the edges of I (set of requests) into subgraphs B w (set of requests with wavelength w) such that L(B w , e) ≤ C.

It is straightforward to see that minimizing the number W of wavelengths needed to route all requests is equivalent to minimizing the number of subgraphs in the partition. Furthermore this is an easy problem since the load L(G, e) is easy to compute. For example if I is the complete graph K N , L(K N , {i, i + 1}) = (i + 1)(N -i -1). If L max (G) is the maximum load over all the edges, L max (G) = max e∈P N L(G, e), then we need at least L max (G) C wavelengths and we can assign them in a greedy way. For the complete graph, the number of wavelengths is therefore: Proposition 2.1 For the all-to-all set of requests on the path P N and grooming ratio C, the minimum number of wavelengths needed is N 2 -ε

4C

, where ε = 1 when N is odd and 0 otherwise.

Proof: We have L max (K N ) = max e∈P N L(K N , e) = max {i,i+1}=e∈P N (i + 1)(N -i -1) = N 2 -ε

4

, where ε = 1 when N is odd and 0 otherwise.

Here our objective is to minimize the number of ADMs, that is the sum of the number of vertices in the B w . Thus the problem can be formalized as follows:

Problem 2.2 (Grooming problem on the path)

Inputs : a path P N , a grooming ratio C and a set of requests I modeled by the graph I.

Output : a partition of the edges of I into subgraphs B w = (V w , E w ), w = 1, . . . , W , such that load(B w , e) ≤ C for each edge e of P N . Objective :minimize 1≤w≤W |V w |.

We will denote the minimum of 1≤w≤W |V w | by A(P N , I, C). As we will mainly consider in this paper I = K N , following [START_REF] Bermond | Traffic grooming in unidirectional WDM ring networks using design theory[END_REF], we will shortly denote A(P N , K N , C) by A(P N , C), that is the optimal number of ADMs for a grooming ratio C and the all-to-all set of requests on the path.

We have formalized the problem in its undirected version, but for paths it is the same for directed or symmetric directed versions. Indeed, if we consider a dipath -→ P N where the arcs are from i to i + 1, and if the requests are the couples (u, v), with u < v, the problem is exactly the same. If we consider a symmetric dipath P * N with arcs (i, i + 1) and (i + 1, i) and the requests are the couples (u, v), we can split the problem into 2 disjoint subproblems, one with the dipath -→ P N oriented from 0 to N -1 with all requests (u, v) with u < v, and the second on the dipath ← -P N oriented from N -1 to 0 with requests (u, v) with v < u.

To the best of our knowledge, this problem has only been studied in [START_REF] Huang | Traffic grooming in path, star, and tree networks: Complexity, bounds, and algorithms[END_REF] where it has been proved NP-complete, and no other results are known. However, the grooming problem for rings has been extensively studied. For example in [START_REF] Bermond | Traffic grooming in unidirectional WDM ring networks using design theory[END_REF] we have shown that the grooming problem on the unidirectional ring can be formalized as follows:

Problem 2.

(Grooming problem on the cycle)

Inputs : a cycle C N and a grooming ratio C.

Output : a partition of the edges of

K N into subgraphs B w = (V w , E w ), w = 1, . . . , W , such that |E w | ≤ C. Objective :minimize 1≤w≤W |V w |.
Note that in Problem 2.3, for the ring, it is supposed that the two requests (u, v) and (v, u) are assigned to the same wavelength (using thus 1/C of the capacity of the wavelength). Clearly, a bound on the number of ADMs for unidirectional ring gives a bound for our problem, but there might be very different (for example for C = 2 and for the cycle C 3 we need 5 ADMS, but A(P 3 , 2) = 3) due to capacity constraints.

In fact, the problem for unidirectional rings corresponds to the problem of path "without erasure" [START_REF] Huang | Traffic grooming in path, star, and tree networks: Complexity, bounds, and algorithms[END_REF]. In this model a request (u, v) uses 1/C of the bandwidth on the whole path and not only on the subpath between u and v. The "load condition" becomes: there are at most C requests in any subgraph B w which is exactly the constraint of Problem 2.3.

We will show in the next section that the grooming problem on the path with erasure for C = 1 and general instances can be solved polynomially, which is not the case on the ring (in the erasure model) [START_REF] Shalom | A 10/7 + approximation for minimizing the number of ADMs in SONET rings[END_REF][START_REF] Wan | Grooming of arbitrary traffic in SONET/WDM BLSRs[END_REF][START_REF] Epstein | Better bounds for minimizing SONET ADMs[END_REF].

Grooming ratio C = 1

When the grooming ratio is equal to 1, the grooming problem on the path can be solved optimally for any set of requests in polynomial time. We prove this in Proposition 3.1 and give the exact number of ADMs in the all-to-all case in Corollary 3.2. Let d - I (i) (resp. d + I (i) denote the indegree (resp. outdegree) of node i in I, that is the number of requests {u, i} with u < i (resp. {i, u} with i < u).

Proposition 3.1 A(P N , I, 1) = N -1 i=0 max d - I (i), d + I (i) .
Proof: The lower bound is simple since in each node i of the path P N we can not do better than sharing an ADM between a request ending in this node, that is a request {u, i} with u < i, and a request starting from it, that is {i, v} with i < v. Thus A(P N , I, 1)

≥ N -1 i=0 max d - I (i), d + I (i)
. Now, note that it is always possible to put a request ending in node i and a request starting from i in a same subgraph. Thus we can form the subgraphs using a greedy process: scan the nodes of the path from 0 to N -2 and add to each subgraph containing a request ending in i a request starting from i (if any left), and then create a new subgraph for each remaining request that start from i (if any). Therefore, in each node i, we will use max d - I (i), d + I (i) ADMs and so the lower bound is attained.

Finally, one may remark that this process will create more subgraphs than necessary, but we can merge two subgraphs if they contain disjoint requests. Doing so we will use the optimal number of subgraphs.

Corollary 3.2 A(P N , 1) = 3N 2 -2N -ε

4

, where ε = 1 when N is odd and 0 otherwise .

The corollary follows from the fact that d -

I (i) = i and d + I (i) = N -1 -i.
Another simple construction is the following. We have A(P 2 , 1) = 2 and A(P 3 , 1) = 5. Now let the vertices of P N be 0, 1, . . . , N -1; arrange them in this order, and suppose that A(P N , 1) = (3N 2 -2N -ε)/4, where ε = 1 when N is odd and 0 otherwise. Let now the vertices of P N +2 be x, 0, 1, . . . , N -1, y and arrange them in this order. The subgraphs of the partition of K N +2 will be: the N subgraphs B j , 0 ≤ j ≤ N -1, each of them containing the edges {x, j} and {j, y}, and so |V (B j )| = 3; the subgraph B N which contains only the edge {x, y}, and so |V (B N )| = 2; and the subgraphs of the partition of K N . So altogether the partition of

K N +2 contains 2 + 3N + (3N 2 -2N -ε)/4 = 3(N + 2) 2 -2(N + 2) -ε /4
, where ε = 1 when N is odd and 0 otherwise.

When the grooming ratio is C ≥ 2, the problem is NP-complete and difficult to approximate for general instance. In particular, when the grooming ratio is equal to C = 2, this problem is similar to partition the edges of I into the maximum number of K 3 s (see [START_REF] Dor | Graph decomposition is NP-complete: a complete proof of Holyer's conjecture[END_REF][START_REF] Holyer | The NP-completeness of some edge-partition problems[END_REF]), although such partition only provides an upper bound of the total number of ADMs (two K 3 may share an ADM). However, for I = K N we will give in the next sections the exact number of ADMs for C = 2.

Lower bounds

Consider a valid construction for the Problem 2.2 and let a p denote the number of subgraphs of the partition with exactly p nodes, A the number of ADMs, and W the number of subgraphs of the partition. We have the following equalities:

A = N p=2 pa p (1)
N p=2 a p = W (2)
W w=1 |E w | = |E| (3)
To obtain accurate lower bounds we need to bound the value of |E w | for a graph with |V w | = p vertices, satisfying the load constraint. Let γ(C, p) be this maximum number of edges. The determination of γ(C, p) is a challenging problem. In a first version of this paper we conjectured that we have to take the edges of smallest length (distance on the path); that corresponds to the intuition that, in order to satisfy the maximum number of requests, one has to choose the smallest ones. This conjecture is true for C = 1, as γ(1, p) = p -1. We will see that it is true also for C = 2, where γ(2, p) = 3p-3 2 . It is also true for C = 3, where γ(3, p) = p -1 + p -2 = 2p -3 obtained by taking all the edges of length 1 and 2. However, this conjecture is not true in general and has been disproved in [START_REF] Bermond | Optimal solution of the maximum all request path grooming problem[END_REF], were is given a closed formula for γ(C, p). For example when C = s(s+1) 2 and p > s(s -1) then γ(C, p) = sp -C.

In the particular case where I = K N , we know by Proposition 2.1 that W ≥ N 2 -ε

4C

, where ε = 1 when N is odd and 0 otherwise, and we have |E| = N (N -1)

2

. Therefore Equations 2 and 3 become

N p=2 a p ≥ N 2 -ε 4C (4) N p=2 a p γ(C, p) ≥ N (N -1) 2 (5)
For example when C = 3 and using the value γ(3, p) = 2p -3 we obtain

N p=2 (2p -3)a p ≥ N (N -1) 2 (6)
that is

2A(P N , 3) ≥ N (N -1) 2 + 3 N 2 -ε 12 (7)
In what follows we will restrict ourselves to the case C = 2, which is already non immediate and for which we have been able to obtain exact values. To obtain the right lower bounds when N is even, we need to determine γ(2, p, 2h) which is the maximum number of edges of a graph B with p vertices with at least 2h vertices of odd degree and such that L(B, e) ≤ 2 for each edge of P N . Note that γ(2, p) = γ(2, p, 0). Lemma 4.1 γ(2, p, 2h) = 3p-3-h 2 Proof: We prove the lemma by induction. It is true for p = 2 as a graph with two vertices has at most one edge. In that case h = 1 and we have equality. For p = 3 the maximum number of edges is 3, obtained with a K 3 , and there is equality for h = 0. With h = 1, the graph has at most 2 edges and the equality is attained with a P 3 . Similarly for p = 4, the graph has at most 4 edges. Let the vertices be {a, b, c, d} with a < b < c < d. For h = 0 the equality is attained for example with the graph C 4 consisting of the 4 edges {a, b}, {b, c}, {c, d} and {a, d}; for h = 1 equality is attained with the graph consisting of an edge joined by a vertex to a K 3 more precisely the 4 edges {a, b}, {b, c}, {c, d} and {b, d}; and for h = 2 equality is attained with a 3-star K 1,3 {a, b}, {b, c} and {b, d}.

Now consider a graph B with p vertices and 2h vertices of odd degree. Let m(B) be the number of edges of B, and let u 0 be the first vertex of B (in the order of the path).

1. If u 0 has degree 1, B -{u 0 } has at least 2h -2 vertices of degree 1 and therefore m

(B) ≤ γ(2, p -1, 2h -2) + 1 = 3p-3-h 2 2.
If u 0 is of degree 2, let u 1 and u 2 be the 2 neighbors of u 0 , with u 0 < u 1 < u 2 . As L(B, {u 1 -1, u 1 }) ≤ 2 there is no edge {u, u 1 } with u < u 1 , and as L(B, {u 1 , u 1 + 1}) ≤ 2 there is at most one edge {u 1 , v} with v > u 1 .

(a) If there is no edge {u 1 , v}, the graph obtained from B by deleting u 0 and u 1 has at least 2h -2 vertices of odd degree and so m(B) ≤ γ(2, p -2, 2h -2) + 2 = 3p-4-h 2 .

(b) If there is an edge {u 1 , v 1 } 3 subcases can appear.

i. either v 1 = u 2 and the graph obtained from B by deleting u 0 and u 1 (and therefore the K 3 {u 0 , u 1 , v 1 }) has the same number of vertices of odd degree as B and so

m(B) ≤ γ(2, p -2, 2h) + 3 = 3p-3-h 2 .
ii. or v 1 < u 2 . Due to the load constraint there is no edge {u, v 1 } with u < v 1 and at most one edge {v 1 , v} with v 1 < v. The graph obtained from B by deleting u 0 , u 1 , v 1 has at least 2h -2 vertices of odd degree and 3 or 4 edges less than B. So

m(B) ≤ γ(2, p -3, 2h -2) + 4 = 3p-3-h 2 .
iii. or v 1 > u 2 we do the same reasoning by deleting from B the vertices u 0 , u 1 , u 2 and we obtain m(B)

≤ 3p-3-h 2 .
So in all cases the bound is proved.

Remark: a careful analysis indicates when the bound is attained. An optimal (p, 2h) graph can be obtained either by adding an edge joined to a vertex of even degree of a (p -1, 2h -2) optimal graph (case 1); or by adding two edges {a, b} and {a, c} with a < b < c, c being a vertex of even degree of an optimal (p -2, 2h -2) graph with p + h even (case 2.a); or by adding a K 3 joined to a vertex of an optimal (p -2, 2h) graph (case 2.b.i); or by adding a C 4 joined to a vertex of an optimal (p -3, 2h) graph (careful analysis of case 2.b.iii).

In particular when p is odd and h = 0, the optimal graph is unique and consists of a sequence of 3p-3 6 K 3 's sharing two by two a vertex (K 3 + K 3 + • • • + K 3 ) where G + H denote the graph obtained by merging the right most node of G with the left most node of H.

For any h, equality is attained with the graph consisting of 3p-3-3h 6 K 3 s and h edges merged in the following way e

+ K 3 + e + K 3 + • • • + K 3 + e + K 3 + K 3 + • • • + K 3 (
with p ≥ h, and p odd when h even and p even when h odd). Theorem 4.2

• A(P N , 2) ≥ 11N 2 -8N -3 24 when N is odd • A(P N , 2) ≥ N (N -1) 3 + N 2 8 + N 6
when N is even.

Proof: By Lemma 4.1 we know that |E w | ≤ γ(2, p w , 2h w ) ≤ 3pw-3-hw 2
for a B w with p w vertices and 2h w vertices with odd degree. So

W w=1 |E w | ≤ N p=2 3p -3 2 a p - W w=1 h w 2 ( 8
)
If N is odd, W w=1 h w can be equal to 0, but when N is even all vertices of K N being of odd degree, W w=1 2h w ≥ N . So Equation 1and Inequalities 4 and 5 become Equation 9and Inequalities 10 and 11, where ε = 1 if N is odd and ε = 0 otherwise.

A = N p=2 pa p (9) N p=2 a p ≥ N 2 -ε 8 ( 10
) N p=2 3p -3 2 a p -(1 -ε) N 4 ≥ N (N -1) 2 (11)
Thus Inequality 11 becomes

N p=2 3pa p ≥ N (N -1) + 3 N p=2 a p + (1 -ε) N 2 ( 12
)
and so

A(P N , 2) ≥ N (N -1) 3 + N 2 -ε 8 + (1 -ε) N 6 ( 13
)
When N is odd, we have ε = 1 and so A(P N , 2) ≥ 11N 2 -8N -3

24

, and when N is even, we have ε = 0 and so A(P N , 2) ≥ N (N -1)

3 + N 2 8 + N 6 .
5 Constructions for C = 2

3-GDD

Let v 1 , v 2 , . . . , v l be non negative integers; the complete multipartite graph with group sizes v 1 , v 2 , . . . , v l is defined to be the graph with vertex set

V 1 ∪ V 2 ∪ • • • ∪ V l where |V i | = v i
, and two vertices u ∈ V i and v ∈ V j are adjacent if i = j. Using terminology of Design Theory, the graph of type p α 1 1 p α 2 2 . . . p α l l will be the complete multipartite graph with α i groups of size p i . The existence of a partition of this multipartite graph into K k is equivalent to the existence of a k-GDD (Group Divisible Design) of type p α 1 1 p α 2 2 . . . p α l l . Here we are interested in the existence of 3-GDD's, that is partitions into K 3 's.

Theorem 5.1 (Existence of a 3-GDD (see [START_REF]The CRC handbook of Combinatorial designs[END_REF])) There exists a 3-GDD of type p α 1 1 p α 2 2 . . . p α l l if and only if (i) each node of the complete multipartite graph has even degree, and (ii) the number of edges is a multiple of 3.

Various constructions are explained in [START_REF] Lindner | Design Theory[END_REF]. One can find in [START_REF]The CRC handbook of Combinatorial designs[END_REF] a collection of multipartite graphs for which there exists a 3-GDD. For example when the total number of nodes is 22, there exists 3-GDDs of type 6 1 4 4 , 6 3 4 1 , 8 1 6 1 4 1 2 2 and 10 1 2 6 . Some other values are given in Theorem 5.2.

Constructions for small values of N

We have reported in Table 1 the number A(P N , 2) of ADMs and the number W of subgraphs of optimal constructions for some small cases. Direct constructions for the value that cannot be obtained in the following constructions are given in Appendix A.

N

Constructions for odd values

In this section we show that the lower bound is always attained for odd N . To prove that, we use the 3-GDD described in Theorem 5.2 from which we deduce a generic construction in Corollary 5.3. Finally, we show in Theorem 5.4 that the bound is reached for all odd values.

Theorem 5.2 (1.26 page 190 of [START_REF]The CRC handbook of Combinatorial designs[END_REF]) Let u and v be positive integer with v ≤ u. Then a 3-GDD of type

u 1 v 1 1 u exists if and only if (u, v) ≡ (1, 1), (3, 1), (3, 3), (3, 5), (5, 1) (mod (6, 6)).
Corollary 5.3 Given u and v satisfying the condition of Theorem 5.2 and an optimal construction for both u and v, we can build an optimal construction for N = 2u + v.

Proof: Let the nodes of K N be numbered from left to right 0, 1, . . . , u-1, u, . . . , u+v -1, . . . , 2u+ v -1 = N and let A = {0, 1, . . . , u -1}, B = {u, u + 1, . . . , u + v -1} and C = {u+v, u+v +1, . . . ,

2u + v -1}.
The examples of Figure 2 for N = 7 (resp. N = 9) are obtained with this construction using u = 3 and v = 1 (resp. v = 3). The 3-GDD of type u 1 v 1 1 u has 3u 2 -u+4uv 6 K 3 , and we say that the K 3 s are of type ABC or ACC or CCC depending of their number of nodes in A, B and C. There are uv K 3 of type ABC,

u(u-v) 2 K 3 of type ACC and u(v-1) 6 K 3 of type CCC. Each node of A is the left most node of v + u-v 2 = u+v 2 K 3 of type ABC or ACC.
Since each node of A is the right most node of at most u-1 2 subgraphs of the decomposition of K u , we can merge each of the u 2 -1 8 subgraphs with one K 3 and so we save

u 2 -1 8 ADMs. Each node of C is the right most node of v K 3 of type ABC. It is also involved in u -v K 3 of type ACC and in u-1-(u-v) 2 = v-1
2 K 3 of type CCC. Thus we can merge each K 3 of type CCC with a K 3 of type ABC and so we save u(v-1) 6 more ADMs. Note that since each node of B is the middle node of a K 3 of type ABC, we can not merge the subgraphs of the partition of K v .

Thus, the number of ADMs used in this construction is

3u 2 -u + 4uv 2 + A(P u , 2) - u 2 -1 8 - u(v -1) 6 + A(P v , 2) (14)
Since for w = u or v, we have A(P w , 2) = 11w 2 -8w-3

24

+ ε w , where ε w = 1 3 for w ≡ 5 (mod 6) and 0 otherwise, Equation 14 become

3u 2 -u + 4uv 2 + 11u 2 -8u -3 24 + ε u - u 2 -1 8 - u(v -1) 6 + 11v 2 -8v -3 24 + ε v (15) = 11(2u + v) 2 -8(2u + v) -3 24 + (ε u + ε v )
Finally, if (u, v) ≡ (1, 1), (3, 1), (3, 3) (mod [START_REF] Bermond | Traffic grooming in unidirectional WDM ring networks using design theory[END_REF][START_REF] Bermond | Traffic grooming in unidirectional WDM ring networks using design theory[END_REF]), then we have ε u = ε v = 0 and we obtain the lower bound, and if (u, v) ≡ (3, 5) or (5, 1) (mod [START_REF] Bermond | Traffic grooming in unidirectional WDM ring networks using design theory[END_REF][START_REF] Bermond | Traffic grooming in unidirectional WDM ring networks using design theory[END_REF]), then 2u + v ≡ 5 (mod 6) but

ε u + ε v = 1 3
and we get again the lowerbound.

Note that, as expected, the number of subgraphs in the partition is

3u 2 -u + 4uv 6 - u(v -1) 6 + v 2 -1 8 = (2u + v) 2 -1 8 (16)
We can now prove that the bound is attained for all odd values.

Theorem 5.4 When N is odd, A(P N , 2) = 11N 2 -8N -3

24

. Furthermore, the construction contains

N 2 -1 8
subgraphs.

Proof: For N = 3, 5, 13, 17 we give direct constructions in Lemmas A.1, A.3, A.6 and A.8. For other values we will use Corollary 5.3 using induction on u.

• When N = 12t + 1, t ≥ 2, let u = 6t -3 and v = 7. Since (6t -3, 7) ≡ (3, 1) (mod [START_REF] Bermond | Traffic grooming in unidirectional WDM ring networks using design theory[END_REF][START_REF] Bermond | Traffic grooming in unidirectional WDM ring networks using design theory[END_REF])), we can use Corollary 5.3.

• When N = 12t + 3, t ≥ 0, we can use Corollary 5.3 with u = 6t + 1 and v = 1 with a K 3 of type ABC and so save 2u(v-1) 3

ADMs. Furthermore, we can merge each edge c 1 i , c 2 i such that c 1 i , c 2 i ∈ C i , 1 ≤ i ≤ u, with a K 3 of type ABC or ACC and so save u more ADMs. Each node of A is the left most node of 2v + u -v = u + v K 3 of type ABC or ACC and is the right most node of at most 2u-2 2 + 1 = u subgraphs of the optimal construction for 2u. Thus we can merge each subgraph and save 4u 2 8 more ADMs.

By hypothesis we have

A(P 2u , 2) - 4u 2 8 = 2u(2u -1) 3 + 2u 6 = u(4u -1) 3 = u(4u -1) 3 + α u (18)
where α u = 1 3 when u ≡ 2 (mod 3) and 0 otherwise. Altogether the construction has the following number of ADMs.

A(P N , 2) ≤ A(P 2u , 2) - 4u 2 8 + A(P 2v , 2) + (6u 2 -2u + 8uv) - 2u(v -1) 3 +2u -u ≤ u(4u -1) 3 + α u + 44v 2 -8v 24 + ε v + 18u 2 -u + 22uv 3 ( 19
) ≤ 11(4u + 2v) 2 -4(4u + 2v) 24 + α u + ε v (20)
Now we have to check that α u + ε v = ε N in all cases. For that, observe that the conditions of Lemma 5.5 are satisfied when v = 1 and when v = 4, assuming that u ≥ v ≥ 1. So we have reported in the following table all cases that satisfies the above construction.

N condition u v α u ε v ε N 12t + 2 t ≥ 1 3t 1 0 1 2 1 2 12t + 4 t ≥ 2 3t -1 4 1 3 0 1 3 12t + 6 t ≥ 0 3t + 1 1 0 1 2 1 2 12t + 8 t ≥ 2 3t 4 0 0 0 12t + 10 t ≥ 0 3t + 2 1 1 3 1 2 5 6 12t + 12 t ≥ 1 3t + 1 4 0 0 0
Furthermore, the number of subgraphs in our construction for N = 4u + 2v is equal to the number of K 3 of type ABC, plus the number of K 3 of type ACC, plus the number of subgraphs in the construction for 2v, that is 4uv + 2u(u -v)

+ 4v 2 8 = (4u+2v) 2 8 .
In conclusion, Theorem 5.6 is true for all even N . Lemma A.7 A(P 16 , 2) = 115 Proof: Let the vertices of P 16 be A ∪ B ∪ C, where A = {a 0 , a 1 , a 2 , a 3 , a 4 , a 5 }, B = {b 0 , b 1 , b 2 , b 3 } and C = {c 0 , c 1 , c 2 , c 3 , c 4 , c 5 }. Our construction is based on the existence of a 3-GDD of type 6 1 4 1 2 3 , which consist on 24 K 3 of type ABC, 6 K 3 of type ACC and 2 K 3 of type CCC, and by merging the 5 subgraphs of the decomposition of K 6 with K 3 s of type ABC, the 2 K 3 of type CCC and the 3 edges {c i , c i+1 }, i = 0, 1, 2, with K 3 s of type ABC. Altogether this construction uses 115 ADMs and the subgraphs of the decomposition are: • The 2 subgraphs on 6 vertices, the K 3 + e + K 3 {a 0 , a 3 , a 4 } + {a 4 , a 5 } + {a 5 , b 0 , c 2 } and the e + K 3 + K 3 {a 0 , a 1 } + {a 1 , a 2 , a 4 } + {a 4 , b 0 , c 1 }, so 12 ADMs.

• The 4 subgraphs K 3 + K 3 {a 0 , b 0 , c 0 } + {c 0 , c 2 , c 4 }, {a 1 , b 1 , c 1 } + {c 1 , c 3 , c 5 }, {a 0 , a 2 , a 5 } + {a 5 , b 1 , c 0 } and {a 1 , a 3 , a 5 } + {a 5 , b 3 , c 3 },so 20
• The 21 Proof: The decomposition is based on the existence of a 3-GDD of type 3 2 5 1 3 2 (which was kindly given to us by C.J. Colbourn) and the subgraphs are:

K 3 {a 0 , b 1 , c 5 }, {a 0 , b 2 , c 3 }, {a 0 , b 3 , c 4 }, {a 0 , c 1 , c 2 }, {a 1 , b 0 , c 5 }, {a 1 , b 2 , c 2 }, {a 1 , b 3 , c 0 }, {a 1 , c 3 , c 4 }, {a 2 , b 0 , c 3 }, {a 2 , b 1 , c 4 }, {a 2 , b 3 , c 1 }, {a 2 , c 2 , c 5 }, {a 3 , b 0 , c 4 }, {a 3 , b 2 , c 1 }, {a 3 , c 0 , c 5 }, {a 4
• The 9 subgraphs K 3 + K 3 {0, • The 3 graphs of the decomposition of the K 5 on 6, 7, 8, 9, 10: the 2 K 3 {6, 8, 10} and {6, 7, 9} and the C 4 {7, 8, 9, 10}, so 10 more ADMs.

In summary our construction has 127 ADMs.

Lemma A.9 A(P 20 , 2) = 180

Proof: The decomposition is based on a 3-GDD of type 2 3 8 1 2 3 in which the vertices are labeled a 0 , a 1 , b 0 , b 1 , c 0 , c 1 , 0, 1, . . . , 7, d 0 , d 1 , e 0 , e 1 , f 0 , f 1 and ranked in this order. The subgraphs are:

• The 2 subgraphs K 3 + K 3 {a 1 , c 0 , 0} + {0, 3, 6} and {0, 5, 7} + {7, d 0 , f 1 }, and the 3 subgraphs e + K 3 + e {a 0 , a 1 } + {a 1 , 4, d 0 } + {d 0 , d 1 }, {b 0 , b 1 } + {b 1 , 4, e 0 } + {e 0 , e 1 } and {c 0 , c 1 } + {c 1 , 4, f 0 } + {f 0 , f 1 }, so 25 ADMs.

• The 4 subgraphs on 6 vertices: the two K 3 + e + K 3 {a 0 , b 1 , 0} + {0, 1} + {1, 2, 7} and {2, 5, 6} + {6, 7} + {7, e 1 , f 0 }, the K 3 + K 3 + e {b 0 , c 1 , 0} + {0, 2, 4} + {4, 5} and the e + K 3 + K 3 {2, 3} + {3, 4, 7} + {7, d 1 , e 0 } so 24 ADMs.

• The 2 subgraphs K 3 +K 3 +K 3 {a 0 , b 0 , c 0 }+{c 0 , 2, d 0 }+{d 0 , e 0 , f 0 } and {a 1 , b 1 , c 1 }+{c 1 , 2, d 1 }+ {d 1 , e 1 , f 1 }, so 14 ADMs.

• The 39 K 3 {1, 4, 6}, {1, 3, 5}, {0, d 0 , e 1 }, {0, e 0 , f 1 }, {0, d 1 , f 0 }, {a 0 , c 1 , 7}, {a 1 , b 0 , 7}, {b 1 , c 0 , 7}, {a 0 , 1, d 0 }, {b 0 , 1, e 0 }, {c 0 , 1, f 0 }, {a 1 , 1, d 1 }, {b 1 , 1, e 1 }, {c 1 , 1, f 1 }, {a 0 , 2, e 0 }, {b 0 , 2, f 0 }, {a 1 , 2, e 1 }, {b 1 , 2, f 1 }, {a 0 , 3, f 0 }, {b 0 , 3, d 0 }, {c 0 , 3, e 0 }, {a 1 , 3, f 1 }, {b 1 , 3, d 1 }, {c 1 , 3, e 1 }, {a 0 , 4, d 1 }, {b 0 , 4, e 1 }, {c 0 , 4, f 1 }, {a 0 , 5, e 1 }, {b 0 , 5, f 1 }, {c 0 , 5, d 1 }, {a 1 , 5, e 0 }, {b 1 , 5, f 0 }, {c 1 , 5, d 0 }, {a 0 , 6, f 1 }, {b 0 , 6, d 1 }, {c 0 , 6, e 1 }, {a 1 , 6, f 0 }, {b 1 , 6, d 0 } and {c 1 , 6, e 0 }, so 117 more ADMs

Altogether this construction has 180 ADMs.

Figure 1 :

 1 Figure 1: Placement of ADMs in the network: one ADM for each wavelength used in a node.

10 Figure 2 :

 102 Figure 2: Constructions for N = 3, 7 and 9.

•

  ADMs. The 3 K 3 + e {a 2 , b 2 , c 0 } + {c 0 , c 1 }, {a 3 , b 3 , c 2 } + {c 2 , c 3 } and {a 4 , b 2 , c 4 } + {c 4 , c 5 }, and the e + K 3 {a 2 , a 3 } + {a 3 , b 1 , c 3 }, so 16 ADMs.

•

  , b 1 , c 2 }, {a 4 , b 3 , c 5 }, {a 4 , c 0 , c 3 }, {a 5 , b 2 , c 5 }, {a 5 , c 1 , c 4 } and {b 0 , b 2 , b 3 }, so 63 ADMs. The star {b 0 , b 1 } + {b 1 , b 2 } + {b 1 , b 3 }, 4 ADMs. Lemma A.8 A(P 17 , 2) = 127

Table 1 :

 1 Number of ADMs and number of subgraphs in small cases

		2 3 4 5	6	7	8	9 10 11 12 13 16	17	20
	A(P N , 2) 2 3 7 10 16 20 28 34 45 52 64 73 115 127 180
	W	1 1 2 3	5	6	8 10 13 15 18 21 32	36	50

  1, 2} + {2, 3, 11}, {3, 4, 5} + {5, 13, 15}, {1, 4, 11} + {11, 12, 13}, {2, 4, 14} + {14, 15, 16}, {0, 5, 6} + {6, 11, 14}, {2, 5, 7} + {7, 11, 16}, {0, 4, 8} + {8, 11, 15}, {1, 5, 9} + {9, 13, 14} and {0, 3, 10} + {10, 12, 14}, so altogether 45 ADMs. • The 24 K 3 s {4, 6, 12}, {1, 6, 13}, {2, 6, 15}, {3, 6, 16} {1, 7, 12}, {4, 7, 13}, {3, 7, 15}, {0, 7, 14} {2, 8, 12}, {3, 8, 13}, {1, 8, 16}, {5, 8, 14} {3, 9, 12}, {4, 9, 15}, {2, 9, 16}, {0, 9, 11} {2, 10, 13}, {1, 10, 15}, {4, 10, 16}, {5, 10, 11} {1, 3, 14}, {0, 12, 15}, {0, 13, 16} and {5, 12, 16}, so 72 ADMs.

Acknowledgments

Many thanks to C.J. Colbourn for his help in solving the case N = 17 and for two anonymous referees for helpful remarks.

partially funded by the European project IST fet Aeolus, and has been done in the context of the crc Corso with France Telecom and the European action COST 293.

† Part of this work has been done during the internship of Laurent Braud in the Mascotte project, june-july 2004.

• When N = 12t + 5, t ≥ 3, we can use Corollary 5.3 with u = 6t -3 and v = 11, and for t = 2, that is N = 29 we can use Corollary 5.3 with u = 11 and v = 7

• When N = 12t + 7, t ≥ 0, we can use Corollary 5.3 with u = 6t + 3 and v = 1

• When N = 12t + 9, t ≥ 0, we can use Corollary 5.3 with u = 6t + 3 and v = 3.

• When N = 12t + 11, t ≥ 1, we can use Corollary 5.3 with u = 6t + 3 and v = 5. Finally, we can also use Corollary 5.3 for N = 11 with u = 5 and v = 1

Construction for even values

In view of the lower bound, an optimal partition will have exactly N 2

8

subgraphs and each vertex will appear once with odd degree and otherwise the value 3p-3 2 is attained. So we will have mainly K 3 's, plus N 2 graphs K 3 + e (except for some congruence classes where one edge is isolated) some of these K 3 's or K 3 + e being merged together. Lemma 5.5 There exists a 3-GDD of type (2u) 1 (2v) 1 2 u when u ≥ v ≥ 1 and u(v-1) ≡ 0 (mod 3).

Proof: To deduce the lemma from Theorem 5.1, one has to check that all nodes have even degree (which is true) and that the total number of edges 4u 2 +4uv +4uv +4 u(u-1) 2 = 6u 2 +6uv +2u(v -1) is a multiple of 3 which follows from u(v -1) ≡ 0 (mod 3).

24

+ ε N , where ε N = 1 2 when N ≡ 2 or 6 (mod 12), ε N = 1 3 when N ≡ 4 (mod 12), ε N = 5 6 when N ≡ 10 (mod 12), and 0 when N ≡ 0 or 8 (mod 12). Furthermore, the construction contains N 2 8 subgraphs.

Proof: First of all, the theorem is true for N = 2, 4, 8, 12, 16, 20 by Lemmas A.1, A.2, A.4, A.5, A.7 and A.9 (see Appendix A). Now suppose that the result is true for 2u and 2v, that is for w = u or v,

where ε w = 1 2 when 2w ≡ 2 or 6 (mod 12), ε w = 1 3 when 2w ≡ 4 (mod 12), ε w = 5 6 when 2w ≡ 10 (mod 12), and 0 otherwise. Furthermore, the number of subgraph is 4w 2

8

.

Let now N = 4u + 2v, where u and v are such that there exists a 3-GDD of type (2u) 1 (2v) 1 2 u . Let also the nodes be

To simplify the notation, we say that an edge is of type CC if it has one node in C i and another in C j with i = j.

The 3-GDD of type (2u)

3 of type CCC. We observe that each node of C is the right most node of 2v K 3 of type ABC and is involved in 2u -2v K 3 of type ACC and v -1 K 3 of type CCC. Thus, we can merge each K 3 of type CCC A Appendix: small cases Remark that all the subgraphs that we consider in the constructions satisfy L(B w , e) ≤ 2. It is clear for a K 3 {u, v, w}, where we suppose u < v < w. For a graph e + K 3 , where the edge {t, u} is glued with the K 3 {u, v, w}, we suppose that t < u < v < w. For a graph K 3 + e, where the K 3 {u, v, w} is glued with the edge {w, x}, we suppose that u < v < w < x. Proof: The subgraphs of the decomposition are the two K 3 {0, 2, 4} and {0, 1, 3}, plus the subgraph B 3 containing the 4 edges {1, 2}, {2, 3}, {3, 4} and {1, 4}. This construction uses 10 ADMs, which fits the lower bound.

in this order. We have 4 groups of 2 consecutive nodes and we use a 3-GDD of type 2 4 . The decomposition contain the 4

Proof: Let the vertices of P 13 be Z 13 and remark that K 13 can be partitioned into the 26 K 3 {i, i + 1, i + 4} and {i, i + 5, i + 7}, i ∈ Z 13 . Our decomposition contains the subgraph K 3 +K 3 +K 3 {0, 1, 4} + {4, 5, 8} + {8, 9, 12}, plus the 3 subgraphs K 3 + K 3 {i, i + 1, i + 4} + {i + 4, i + 5, i + 8}, i = 1, 2, 3, plus the 4 K 3 {j, j + 1, j + 4}, j = 9, 10, 11, 12, and plus the 13 K 3 {k, k + 5, k + 7}, k ∈ Z 13 . Altogether the construction has 7 + 3 × 5 + 17 × 3 = 73 ADMs.