Christophe Kolski

Guillaume Uster
email: guillaume.uster@ifsttar.fr

Jean-Marc Robert
email: jean-marc.robert@polymtl.ca

Káthia Marçal De Oliveira

Bertrand T David
email: bertrand.david@ec-lyon.fr

Kathia Oliveira

Interaction in Mobility: The Evaluation of Interactive Systems Used by Travellers in Transportation Contexts

Keywords: Human-computer interaction, Mobility, Evaluation, transportation

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

This paper is about the evaluation of interactive systems used by travellers in transportation contexts. These contexts are heterogeneous since they include all means of transport (airplanes, ferries, trains, buses, subways, cars, bicycles, walk) and their respective home bases (airports, river ports, train/bus/subway/bicycle stations). What is striking here is the diversity of travellers, activities, interactive systems, and contexts of interaction, the diversity of situations that result from the combination of these elements, and the challenges that travellers' mobility represents for evaluation. This makes transportation a rich and complex domain for studying interaction [START_REF]Interaction homme-machine dans les transports -information voyageur, personnalisation et assistance[END_REF].

The paper is structured as follows. We present some new perspectives on transport and mobility. Then we describe the sources of diversity in transport and we propose to evaluate the User Experience (UX) of travellers. We examine two activities which often occur in transport: learning and playing. Finally we describe some new perspectives offered by a model-based engineering approach.

Some New Perspectives on Transport and Mobility

Over the last years, there has been a diversification of forms of travels. Commuting is not anymore the most frequent form of travel, it has been replaced by occasional journeys. The planning of these journeys requires a lot of information and often comprises a part of uncertainty. For these journeys, private cars are still the principal mean of transport. Augmenting public transport and other green alternatives to private vehicles is the objective of sustainable mobility. But a major weakness of public transport is the lack of information. Indeed, several inquiries about occasional users of public transport mentioned this problem, for example, regarding bus routes and timetables, and the perception that the bus system is difficult to use and that information is difficult to access [START_REF] Beirao | Understanding attitudes towards public transport and private car. A qualitative study[END_REF]. Furthermore, interchange of means of transport is perceived negatively by users and has also been identified as an area of public transport that should be improved [START_REF] Hine | Seamless, accessible travel: users' views of the public transport journey and interchange[END_REF]. Traveller information is a complex and vast research area; ATIS (Advanced Traveller Information Systems) is the common acronym to designate information systems in the area [START_REF] Lyons | Strategic review of Travel Information Research, final report to the department for transport[END_REF]. There are two main concerns in these systems: technology and user needs.

Technology can make the information accessible through a large diversity of media. For instance, during their trip, travellers can use an onboard information system through embedded screens (for instance, in a bus, a train) as well as they can use their own terminals.

User needs can be investigated through different data collection methods, including panels of travellers. Panels allow researchers to use several methods such as direct interviews, phone interviews, and focus groups to collect data [START_REF] Patesson | User needs analysis: an analysis based on the study of activities of the traveller[END_REF].

Results of studies on different travellers indicate that they adapt their behaviors to travel contexts at each step, and tend to focus their attention on only a few pieces of critical information at a time. They need the right information at the right time, and relevant information should be provided in advance, before it is time to decide. Therefore, it is necessary to provide a coherent and efficient spatio-temporal system to meet travellers' needs at all stages of the journey [START_REF] Patesson | User needs analysis: an analysis based on the study of activities of the traveller[END_REF]. Ergonomic studies can provide design specifications for the user interface (UI) of such a system [START_REF] Mouloudi | User information guidance in public transportation systems[END_REF], and accurate information can be delivered by the personalization of user content [START_REF] Brossard | User modelling: the consideration of the experience of time during journeys in public transportation[END_REF].

A travel is not only an itinerary from point A to point B, it is also the moment for travelers to do different activities such as sleeping, reading, listening to music, playing games, sending text messages, making phone calls, working, talking to other passengers, gazing out of the window, watching people, etc. [START_REF] Lyons | The use of travel time by rail passengers in Great Britain[END_REF]. Furthermore, during their trips, travellers pass through several transit spots where there is a continuous flow of information on transport, commercials, services, etc.

The principal success factor for sustainable mobility is to provide good quality interactive services to citizens and customers. This can be achieved on the base of careful observations of travellers at different times and different locations, for example onboard a train or a bus (Fig. 1). A Living Lab offers a good environment for making such observations and testing new equipments and services. It is a user-centred open innovation ecosystem, often operating on a specific territory, which allows one to do research and innovation through exploration, experimentation, and evaluation of innovative ideas, services, and equipments, in real life use cases and with numerous travellers. Furthermore, it allows one to collect data on delays, traffic, destinations, locations of the vehicles, infotainments, local news, touristic or cultural information, etc. Here we analyze the diversity of usage conditions in transportation contexts and its impacts on the evaluation of interactive systems, and we plead for the opportunity to evaluate the User Experience (UX) of travellers. Let's start with diversity which comes from the interaction of four categories of elements:

-Diversity of travellers. This is remarkable, be it in an airplane, a ferry, a bus, a train, a metro, or in the street. Travellers reflect the entire population and include those with specific needs such as the handicapped, elderly, illiterate, colour-blind, people from different languages and cultures, with low technical abilities, with no or little knowledge about the system (because they use it for the first time or occasionally), with their own interactive systems that they expect to be able to use in conjunction with those of carriers. There are impacts on evaluation: in accordance with the objective of universal design, accessibility of systems should be guaranteed to almost all travellers (this is more and more imposed by regulations), usability of interactive systems should be tested with representatives of each category of travellers to make sure that these systems are easy to use, and systems compatibility should be ensured for the benefit of travellers who carry their own systems and expect to be able to use them in conjunction with those of different carriers -Diversity of activities. This was mentioned above. Travellers will perform different activities when using systems of different carriers and their own systems. These activities could be related to the planning and organization of the trip itself, and to work or leisure done during transport or transit. They can be very diversified as shown in these examples: search for information (e.g., on costs, trajectories, arrivals and departures, connections), read dynamic displays, make reservations, register, buy tickets, make electronic payments, show a reservation, valid a ticket, get, renew or recharge a payment card, read and send emails, get a receipt, write texts, play with video games, listen to music, etc. Some activities are connected to others when they have prerequisites and successors, and will be perceived as such by the travellers. Similar activities, with minor differences, will be done on different interactive systems and in different contexts: they can be called generic and correspond to activity patterns. These observations have impacts on evaluation: adequate functionalities should be available in systems of carriers to perform these activities, the procedures imposed by these systems should be short, easy to follow, and consistent, similar (or generic) activities done on different systems and in different contexts should have similar procedures, and UIs that support these functionalities and procedures should be transparent, consistent, and provide adequate guidance to travellers. -Diversity of systems. Travellers will use systems of different carriers as well as their own interactive systems to perform their activities. Here are several examples of such systems, some being interactive and others not: ticket dispenser, information terminal, registration terminal, dynamic visual information displays, automatic teller to refill a payment card or pay parking fees, bank teller, personal computer, smart phone, etc. These systems could be used by the same traveller in a short period of time and in different locations; their rate of use will differ widely depending on the category of travellers (occasional, average, frequent). These observations have impacts on evaluation: these systems should be evaluated as parts of a global technological ecosystem, i.e. as if they were in relation with each other. To compensate the lack of standardization, their external consistency should be emphasized in order to reduce travellers' cognitive load, minimize learning, prevent errors, and improve human performance and satisfaction. This means that the task scenarios behind the usability tests should include different activities, interrelated or not, done successively by a same traveller on different systems. -Diversity of contexts. Travellers will be using systems in very different contexts.

They could be in a city or a country where the language and culture are different from theirs and represent a barrier for the interaction with systems; when using these systems, they could be sitting, standing, or walking; in a hurry because of an imminent departure, or under pressure because of people waiting behind them; in a state of great fatigue because it is late or after a long trip; in a crowded and noisy place; they can be performing an activity for which security is important (e.g., payment); they could be using a system with one or two hands, and be manipulating objects during the interaction (e.g., a travel card, a credit card) while watching their suitcases; they could be alone, in couple, or in family; they could be using one of their systems in conjunction with those of carriers (e.g., show the reservation code on their mobile phone at the booking desk). This reality has impact on evaluation: interactive systems should be tested in the field, not only in a laboratory, with real travellers doing real activities in conditions that represent the diversity and richness of use contexts.

Given the diversity of conditions that can be found in transportation contexts and the challenge it represents for the design of good interactive systems, it is important to adopt a user-centered design approach [START_REF] Gould | How to design usable systems[END_REF] and thus put emphasis on usability of interactive systems. This will help designers to realize systems that are more effective and efficient, easier to learn and use, and more satisfying for the users; these advantages are at the core of the definition of usability [START_REF]Ergonomics of human system interaction -Part 210: Humancentred design for interactive systems (formerly known as 13407)[END_REF]. Despite the necessity of usability (and other qualities such as utility, compatibility, accessibility) of interactive systems in transportation contexts, we argue that it is not sufficient. It is an instrumental quality in a system that helps users to perform tasks and achieve goals. To a large extent it is simply a hygiene factor, i.e. a factor that has to be taken into consideration in order not to create dissatisfaction among users, and not a motivational factor, which is much more positive and attractive for users.

In a context of competition, where carriers aim to attract new travellers and establish their loyalty through good pricing and high quality services, and where travellers spend much time in transport and are critical towards the products and services they use in this domain, it is important to put emphasis on the global satisfaction of travellers. As a consequence, we propose to go beyond usability with its focus of UIs, and adopt UX with its focus of users (or travellers). It is not in the scope of this paper to present UX at length, we will rather present a few highlights that show the relevance of this concept in transport.

ISO 9241-210 (20101, clause 2.15) defines UX as: « A person's perceptions and responses that result from the use and/or anticipated use of a product, system or service ». Another definition is given by [START_REF] Robert | From usability to user experience with user interfaces[END_REF]: « UX is a multidimensional construct that defines the overall effect over time on the user of interacting with a system or service in a specific context ». The main features of the UX are the following: multidimensional, holistic, subjective, connected to the overall impression on the user, resulting from his/her interactions with the product and from a combination of anticipation and actual experience, dynamic (it changes over time at each point of user's contact with the product or service), situated in context (depending on location, time, other human interactions, opportunities and constraints, incidents, issues), and it can be studied at different levels of granularity [START_REF] Robert | Designing and evaluating user experience[END_REF][START_REF] Law | Modeling user experience, An agenda for research and practice[END_REF]. UX is global and takes into account noninstrumental qualities of system, such as aesthetics, sense-making, the capacity to generate pleasure and emotions that were not considered in usability. It has been rapidly adopted by the communities of design, HCI and human factors, at the beginning of the years 2000. It is the object of an abundant literature and it represents some major challenges for researchers, namely understand the process and evolution of UX in time, and develop methods and tools for the evaluation of UX [START_REF] Vermeeren | User Experience Evaluation Methods: Current State and Development Needs[END_REF]. The global approach of UX seems essential for a more complete evaluation of interactive systems in transportation domain.

Learning and Playing in Mobility

In this section we examine two activities which occur often in transportation contexts: learning and playing. They appear in different terms and involve different people (Table 1). They can occur during travels done individually or in group by car, bus, train, plane, boat, etc. Two categories of people are involved: active or passive actors. Active actors are drivers or crews who will be interested in training as it is related to their work and allows them to improve their knowledge of the task (e.g., rules of operations, procedures about incidents or accidents) and of the equipments they control. Here we talk either of vocational training (for learning techniques or skills), just-in-time learning (for learning things when we just need them for performing an activity), contextual learning (related to a particular space, situation, period of time), or a combination of these. Passive actors are the passengers; let's consider two groups: adults and teenagers. All of them are looking for the best way to spend the transportation time, be it through entertainment (e.g., watch a video, play a video game, listen to music) or some structured learning activities, especially in a context of learning all-along the life. Both groups could be involved in vocational training or contextual learning. On the other hand, only teenagers (and young schoolchildren) will be associated to "anti uproar activities" (to be busy during a long trip in group) and "to do or to finish homework". Figure 2 shows several examples of interactive devices embedded in planes, cars and buses, and of devices carried out by travellers (e.g., laptop, tablet, Smartphone, DVD reader, portable gamer, view goggle). They support individual or collaborative learning and playing activities through a connection to a net. They are often located on the back of a seat of a plane, a car or a bus, and they use a tactile screen or command panel. They use a WIMP or post WIMP interface with gestural, vocal, or multimodal interactions. New forms of interactions provided on new mobile or wearable devices, such as the portable Kinect and WII joysticks, started to appear and should be available in the near future. It is important to evaluate their efficiency and usability, the degree of comfort for users, and their impact on neighbors in transportation context.

Fig. 2. Learning and playing devices 5 New Perspectives Offered by a Model-Based Design Approach

In this section we propose the use of a model-based design approach in transport because of the variety of interactive systems, computing platforms, and medias (e.g., audio, video, image, text) in use. Here is an example. Let's consider the scenario of a person planning a trip by train at home with a PC. Then, while going to the train station s/he gets stuck in a traffic jam. S/he checks train schedules to find another departure, using a PDA, and changes the reservation. When arriving at the train station, s/he goes to the kiosk and uses a terminal to get the ticket. Here, three kinds of platforms were used and different contexts of use have to be taken into account. They represent new challenges for the design of interactive systems: produce systems that can be customized or adapted to all types of platforms, and respect the characteristics and location of the user when interacting with the system.

Model-Driven Architecture (MDA) [START_REF][END_REF] has gained importance as a paradigm that advocates the design of systems at a high level of abstraction. In MDA, models play a more direct role in software production, being amenable to manipulation and transformation by machine with the goal of final code generation. In general, this is done by the definition of three types of models corresponding to three abstraction levels: the computation independent model (CIM) which focuses on the system requirements; the platform independent model (PIM) which specifies the degree of platform independence that is appropriate with different platforms; and, the platform specific model (PSM) which combines the specifications in the PIM with the details that specify how that system uses a particular type of platform. Transformations are used to convert a model into another model (from CIM to PIM, and from PIM to PSM) of the same system, up to the code generation. MDA has also being applied to UI design (see examples in [START_REF] Olivanova | [END_REF][START_REF] Sottet | A Model-Driven Engineering Approach for the Usability of Plastic User Interfaces[END_REF][START_REF] Vanderdonckt | A MDA-Compliant Environment for Developing User Interfaces of Information Systems[END_REF]). UI design is done independently of the platform and then implemented. Models in the three levels and transformations of models should be done considering the context of use of the system, including the user, the platform and the environment [START_REF] Calvary | Unifying Reference Framework for Multi-Target User Interfaces[END_REF]. Even though MDA seems to be an appropriate technology for the design of interactive systems in the transportation domain, two important questions come out: (1) How to consider the particularities of transportation systems with this paradigm? (2) How to evaluate the quality of the user interaction given the high level design model?

The first question is related to the worry of making the transport system usable by everyone and in different contexts. So, for instance, if the traveller is disabled, the system should propose direct itineraries with short walking distances for connections. It should also propose seats that consider his/her disability. In the same vein, if the user informs the system that s/he would like to do personal activities (such as pay bills, do shopping), the system should propose itineraries where services are offered at the connection points. To develop systems that consider all this particularities, we should include explicit models to capture domain knowledge and context information (about use, platform and environment). How to define these models? Which information to consider? Some propositions of context modeling can be found in the literature [START_REF] Kim | An Ontology-Based Context Model in a Smart Home[END_REF][START_REF] Lin | An Efficient Context Modeling and Reasoning System in Pervasive Environment: Using Absolute and Relative Context Filtering Technology[END_REF]. The use of domain ontologies to organize the knowledge about transportation system has also been proposed [START_REF] Houda | A public transportation ontology to support user travel planning[END_REF]. Once these models are included in the design phase, it is essential to perform quality assessments to make sure that the particularities of this domain were really taken into account.

For the second question: since in MDA we talk about models and independence (at some level) or particularities of platform, we consider that the quality models can be generic at some point and should be specified when getting to the final UI (PSM level and final code). Besides, quality is considered multidimensional and depends on the product to evaluate and the perspective of evaluation. Therefore, we should think about what to evaluate for each model and by whom (end users, designers, experts, etc.). For example since the transportation system should be developed to be used by everybody, we should not only focus on usability but on accessibility. Usually, quality models are organized in a hierarchy view (tree view) of quality characteristics, from more general to more specific ones (for example, standards like ISO 9126 [START_REF]Software engineering -Product quality -Part 1: Quality model[END_REF] have characteristics, sub-characteristics and metrics). The problem is when we go to more details in this hierarchy, it is difficult to keep the generality but it is richer about what we should really evaluate. Therefore we should consider top characteristics that can be evaluated for all MDA levels (e.g., usability) and that can be refined in subcharacteristics/attributes appropriate to each model. For example, in the PSM level specific metrics should be defined for the platform or a family of platforms that use one or several interaction modes (such as only speech or graphical and text integrated). Finally, we should analyze which methods to use for the evaluation of each quality characteristic of a model. This is a well-known problem in HCI, and with the MDA paradigm we should also think that we will evaluate generic models that will be used to produce systems for different platforms using different interaction models (speech system or basic textual system). This generality aspect must therefore be taken into account while defining evaluation procedures.

Conclusion and Perspectives

The evaluation of interactive systems in transportation contexts represents a great challenge for researchers and practitioners due to the diversity and complexity of aspects to be taken into account, and the rapid increase of technology. Indeed, this evaluation should cover technical factors such as systems capacity, compatibility, rapidity, security, reliability, robustness, integration, and technological modernity as well as human factors such as utility, accessibility, usability that have a direct impact on travellers' performance and satisfaction. Furthermore, we proposed that the evaluation go beyond these classical factors and cover the more global and inclusive travellers' User Experience.

We propose some ideas for supporting and boosting the evaluation of interactive systems in transport : adopt a global and integrated approach in order to evaluate each system as a component of a larger ecological system; promote the use of facilities such as the Living Lab described above in order to test rapidly and continuously new systems and equipments with real travellers in an environment very close to reality; and finally use the techniques of Web analytics (or equivalent when not on the Web) to collect data on the use of interactive systems, make diagnoses, and continuously improve the user interfaces.

Fig. 1 .

 1 Fig. 1. Living Labs as new evaluation means in transportation contexts

Table 1 .

 1 Learning and playing activities

	Passengers

Acknowledgements. This research work has been supported by CISIT, the Nord-Pasde-Calais Region, and the European Community (FEDER).


Rabah Souam
email: rabah.souam@imj-prg.fr

Stable constant mean curvature surfaces with free boundary in slabs

Keywords: constant mean curvature, free boundary, capillary surfaces, stability Mathematics Subject Classification (2010) 53A10, 49Q10, 53C42, 76B45

We study stable constant mean curvature (CMC) hypersurfaces Σ with free boundary in slabs in a product space M × R, where M is an orientable Riemannian manifold. We obtain a characterization of stable cylinders and prove that if Σ is not a cylinder then it is locally a vertical graph. Moreover, in case M is H n , R n or S n + , if each component of ∂Σ is embedded, then Σ is rotationally invariant. When M has dimension 2 and Gaussian curvature bounded from below by a positive constant κ, we prove there is no stable CMC with free boundary connecting the boundary components of a slab of width l ≥ 4π/ √ 3κ. We also show that a stable capillary surface of genus 0 in a warped product [0, l] × f M where M = R 2 , H 2 or S 2 , is rotationally invariant. Finally, we prove that a stable CMC immersion of a closed surface in M × S 1 (r), where M is a surface with Gaussian curvature bounded from below by a positive constant κ and S 1 (r) the circle of radius r, lifts to M × R provided r ≥ 4/ √ 3κ.

Introduction

Let W be an oriented smooth Riemannian manifold of dimension n ≥ 3 and B ⊂ W a closed domain with smooth boundary. We consider constant mean curvature (CMC) hypersurfaces with free boundary in B, that is, CMC hypersurfaces whose interior is contained in B and whose boundary lies on ∂B and which meet orthogonally ∂B. They are stationary for the area functional for variations preserving the enclosed volume. It is interesting to study CMC hypersurfaces with free boundary which are stable, that is, those for which the second variation of the area is nonnegative for all volume-preserving variations. This problem arises naturally when studying the isoperimetric problem in B. More generally, a capillary hypersurface in B is a CMC hypersurface in B with boundary on ∂B and meeting ∂B at a constant angle. Capillary hypersurfaces are also stationary for a functional which is a linear combination of the area of the hypersurface and the area of the domain enclosed by its boundary on ∂B, for volume-preserving variations. The study of stability of capillary hypersurfaces in balls or with planar boundaries in space forms has attracted a lot of attention very recently, see for instance [START_REF] Ainouz | Stable capillary hypersurfaces in a half-space or a slab[END_REF][START_REF] Barbosa | On CMC free-boundary stable hypersurfaces in a Euclidean ball[END_REF][START_REF] Choe | Stable capillary hypersurfaces in a wedge[END_REF][START_REF] Li | Stability of capillary hypersurfaces with planar boundaries[END_REF][START_REF] Nunes | On stable constant mean curvature surfaces with free boundary[END_REF][START_REF] Wang | Uniqueness of stable capillary hypersurfaces in a ball[END_REF].

We are mainly interested in this paper in stable CMC hypersurfaces with free boundary in slabs of a product space M × R, where M is an orientable Riemannian manifold of dimension ≥ 2. A slab in M × R is the region between two slices M × {t}. Without loss of generality, a slab of width l > 0 in M × R will be taken to be the domain M × [0, l]. The special case M = R n was considered by Athanassenas [START_REF] Athanassenas | A variational problem for constant mean curvature surfaces with free boundary[END_REF] and Vogel [START_REF] Vogel | Stability of a liquid drop trapped between two parallel planes[END_REF], for n = 2, and by Pedrosa and Ritoré [START_REF] Pedrosa | Isoperimetric domains in the Riemannian product of a circle with a simply connected space form and applications to free boundary problems[END_REF], and by Ainouz and Souam [START_REF] Ainouz | Stable capillary hypersurfaces in a half-space or a slab[END_REF] for any n ≥ 2.

The simplest examples of CMC hypersurfaces with free boundary in a slab M × [0, l] are obtained by taking cylinders above closed CMC hypersurfaces in M. Our first result (Theorem 3.3) gives a characterization of stable cylinders in terms of the first eigenvalue of the stability operator of the base and the width of the slab. When M is the Euclidean space R n , the hyperbolic space H n or the unit sphere S n , this characterization of stable tubes is explicit in terms of their radius and the width (Corollary 3.4).

In the general case, we show (Theorem 3.5) that a stable free boundary CMC hypersurface in M × [0, l] that is not a cylinder has to be locally a vertical graph. It is moreover a global graph in case each of its boundary components is embedded and M is simply connected. When M is the Euclidean space R n , the hyperbolic space H n or a hemisphere S n + , the previous hypotheses imply that the hypersurface is rotationally invariant. This extends results obtained in [START_REF] Ainouz | Stable capillary hypersurfaces in a half-space or a slab[END_REF] in the Euclidean case.

When M is two-dimensional with curvature bounded from below by a positive constant κ, we prove (Theorem 3.7) that no stable CMC surface with free boundary can connect the boundary components of a slab M × [0, l] whose width satisfies l ≥ 4π/ √ 3κ.

In section 4, we consider stable capillary surfaces in warped products of the type [0, l] × f M where M = R 2 , H 2 or S 2 . We prove they have to be rotationally invariant when they have genus zero, extending a result obtained in [START_REF] Ainouz | Stable capillary hypersurfaces in a half-space or a slab[END_REF] in the Euclidean case. This applies, in particular, to the region bounded by two parallel horospheres in the hyperbolic space H 3 (Corollary 4.2 ).

Finally, in Section 5, we obtain a result of the same type as Theorem 3.7 for closed stable CMC surfaces in the product M ×S 1 (r) of an orientable surface M, with curvature bounded from below by a positive constant κ, by the circle S 1 (r) of radius r > 0. More precisely, we show that if r ≥ 4/ √ 3κ, then the immersion lifts to a stable CMC immersion in M × R (Theorem 5.1).

Preliminaries

Let W be an oriented smooth Riemannian manifold of dimension n ≥ 3 and B ⊂ W a closed domain with smooth boundary. A capillary hypersurface in B is a compact and constant mean curvature (CMC) hypersurface, with non-empty boundary, which is contained in B and meets ∂B at a constant angle along its boundary. When the angle of contact is π/2, that is, when the hypersurface is orthogonal to ∂B, the hypersurface is said to be a CMC hypersurface with free boundary in B. Capillary hypersurfaces are critical points of an energy functional for volume-preserving variations. In the free boundary case the energy functional is the area functional. We refer to [START_REF] Ainouz | Stable capillary hypersurfaces in a half-space or a slab[END_REF] for more details.

Consider a capillary hypersurface defined by a smooth immersion ψ : Σ -→ B and let N be a global unit normal to Σ along ψ chosen so that its (constant) mean curvature satisfies H ≥ 0. Denote by N the exterior unit normal to ∂B. The angle of contact is the angle θ ∈ (0, π) between N and N . We denote by ν the exterior unit normal to ∂Σ in Σ and by ν the unit normal to ∂Σ in ∂B so that {N, ν} and {N , ν} have the same orientation in (T ∂Σ) ⊥ . The angle between ν and ν is also equal to θ.

The index form I of ψ is the symmetric bilinear form defined on the first Sobolev space H 1 (Σ) of Σ by

I(f, g) = Σ ∇f, ∇g -(|σ| 2 + Ric(N ))f g dΣ - ∂Σ q f g d(∂Σ),
where ∇ stands for the gradient for the metric induced by ψ, σ is the second fundamental form of ψ, Ric(N ) is the Ricci curvature of W in the direction N and

q = 1 sin θ II(ν, ν) + cot θ σ(ν, ν).
Here II denotes the second fundamental form of ∂B associated to the unit normal -N .

Let F = {f ∈ H 1 (Σ), Σ f dΣ = 0}. The immersion ψ is capillarily stable if I(f, f ) ≥ 0 for all f ∈ F.
The stability operator on Σ is the linear operator defined on C 2 (Σ) by

L = ∆ + |σ| 2 + Ric(N )
where ∆ is the Laplacian on Σ induced by ψ.

A function f ∈ F is said to be a Jacobi function of ψ if it lies in the kernel of I, that is, if I(f, g) = 0 for all g ∈ F. By standard arguments, this is equivalent to saying that f ∈ C ∞ (Σ) and satisfies Lf = constant on Σ ∂f ∂ν = q f on ∂Σ

We will also need to consider compact immersed CMC hypersurfaces without boundary. Given such an immersion ψ : Σ -→ W in an orientable Riemannian manifold W, it is said to be stable if I(f, f ) ≥ 0 for all f ∈ F = {f ∈ H 1 (Σ), Σ f dΣ = 0} where I is the index form defined on H 1 (Σ) by

I(f, g) = Σ ∇f, ∇g -(|σ| 2 + Ric(N ))f g dΣ.
An immersion ψ of a closed or capillary CMC is said to be strongly stable if

I(f, f ) ≥ 0 for all f ∈ H 1 (Σ).
It is also interesting to consider, as a more general setting for capillarity, the case where the contact angle is constant along each component of ∂Σ, allowing it to vary from one component to the other. All the previous discussion on stability extends to this more general case (cf. [START_REF] Ainouz | Stable capillary hypersurfaces in a half-space or a slab[END_REF]).

Stable CMC hypersurfaces with free boundary in a slab in a product space M × R

Let M be a connected oriented Riemannian manifold of dimension n ≥ 2. We discuss in this section the case of CMC immersed hypersurfaces with free boundary in slabs M × [0, l], l > 0, of the product space M × R. The function q vanishes identically and the index form takes a simple form:

I(f, g) = Σ ∇f, ∇g -(|σ| 2 + Ric(N ))f g dΣ.
The simplest examples of free boundary CMC hypersurfaces in a slab M × [0, l] are cylinders over closed CMC hypersurfaces in M. We will discuss the stability of cylinders. For this, we will need a criterion for stability of closed CMC hypersurfaces. It was established by Koiso ([10], Theorem 1.3) for compact CMC surfaces with boundary in R 3 but the result readily extends to the closed case in general ambient manifolds. Theorem 3.1. Let ψ : Σ -→ M be a closed and two-sided immersed CMC hypersurface in a Riemannian manifold M of dimension n ≥ 2 . Denote by λ 1 (Σ) and λ 2 (Σ), respectively, the first and second eigenvalues of the stability operator L on Σ. The following hold (I) λ 1 (Σ) ≥ 0 if and only if ψ is strongly stable.

(II) If λ 1 (Σ) < 0 and λ 2 (Σ) > 0, then there exists a uniquely determined smooth function u on Σ such that Lu = 1 and ψ is stable if and only if Σ u dΣ ≥ 0.

(III) If λ 1 (Σ) < 0 and λ 2 (Σ) = 0 and there exists an eigenfunction associated to λ 2 (Σ) satisfying Σ g dA = 0, then ψ is unstable.

(IV) If λ 1 (Σ) < 0 and λ 2 (Σ) = 0 and Σ g dA = 0 for any eigenfunction g associated to λ 2 . Denoting by E the eigenspace associated to λ 2 (Σ) = 0, there exists a uniquely determined smooth function u ∈ E ⊥ (the orthogonal to E in the L 2 sense) which satisfies Lu = 1. Then ψ is stable if and only if Σ u dA ≥ 0.

(V) If λ 2 (Σ) < 0, then ψ is unstable. Remark 3.2.
If λ 1 (Σ) < 0 and λ 2 (Σ) ≥ 0 and we know beforehand the existence of a smooth function u satisfying Lu = 1, then, it is easily checked that (II) and (IV) can be restated simply by saying that ψ is stable if and only if Σ u dA ≥ 0.

We can now give the following characterization of stable cylinders. Theorem 3.3. Let ψ : Γ → M be an immersion with constant mean curvature H of a closed oriented manifold Γ of dimension n ≥ 1 in an (n + 1)-dimensional oriented manifold M and let l > 0. The map ψ

ψ := ψ × {id} : Γ × [0, l] -→ M × [0, l],
is an immersion of constant mean curvature (n-1) n H with free boundary. Denote by λ 1 (Γ) the first eigenvalue of the stability operator L on Γ. The following hold

(i) If ψ is unstable, then ψ is unstable too. (ii) If ψ is stable, then ψ is stable if and only if (3.1) λ 1 (Γ) + π l 2 ≥ 0.
Proof. The first statement about ψ is straightforward.

Denote by L the stability operator of ψ and by I the associated index form.

(i) Suppose ψ is unstable, then there exists u ∈ H 1 (Γ) such that Γ u = 0 and

I(u, u) < 0. Define ū on Γ × [0, l] by ū(p, t) = u(p), for all (p, t) ∈ Γ × [0, l]. Then clearly ū ∈ H 1 (Γ × [0, l]), Γ×[0,l] ū = 0 and I(ū, ū) = I(u, u) < 0, which shows that ψ is unstable. (ii) Suppose ψ is stable. If λ 1 (Γ) + π l 2 < 0, let u be an eigenfunction of L associated to λ 1 (Γ). Then the function v := u cos (πt/l) on Γ × [0, l] satisfies Γ×[0,l] v = 0 and I(v, v) = (λ 1 (Γ) + π l 2 ) Γ×[0,l] v 2 < 0. So ψ is unstable. Suppose now that λ 1 (Γ) + π l 2 ≥ 0.
We will first show that the CMC immersion

ψ := ψ × {id} : Γ × S 1 l π -→ M × S 1 l
π is stable, where S 1 l π denotes the circle of radius l π . Let Ric and Ric, be the Ricci curvature tensors of M and M ×R, respectively, and denote by σ, and σ, the second fundamental forms of ψ and ψ, respectively. We note that | σ| = |σ| and if N is a unit field normal to Γ along ψ, then it is also normal to Γ × S 1 l π along ψ and Ric(N, N ) = Ric(N, N ). We denote by L be the stability operator of ψ and let I be the associated index form.

The eigenvalues and eigenfunctions of the eigenvalue problem

f ′′ + µ f = 0 on S 1 l π are given by µ n = (nπ/l) 2 , n = 0, 1, 2, . . . and f n (t) = cos √ µ n t.
Let λ 1 (Γ) < λ 2 (Γ) ≤ .... ≤ λ k (Γ) ≤ ... be the sequence of eigenvalues of the operator L on the closed manifold Γ. As the function | σ| 2 + Ric(N, N ) = |σ| 2 + Ric(N, N ) depends only on the first factor of the product Γ × S 1 l π , a standard argument shows that the eigenvalues of the operator L on Γ × S 1 l π are given by λ m (Γ) + n 2 π 2 /l 2 , m, n ∈ N. In particular, the first and second eigenvalues of L on Γ × S 1 l π verify:

(3.2) λ 1 Γ × S 1 l π = λ 1 (Γ) (3.3) λ 2 Γ × S 1 l π = min{λ 1 (Γ) + π 2 l 2 , λ 2 (Γ)} If λ 1 (Γ) ≥ 0, then, by (3.2), λ 1 (Γ × S 1 l π ) ≥ 0, that is, ψ is strongly stable. So we assume λ 1 (Γ) < 0. In this case we know that λ 2 (Γ) ≥ 0 (Theorem 3.1 (V)). Therefore, by (3.3), λ 2 Γ × S 1 l π ≥ 0.
Consider then the solution u ∈ C ∞ (Γ) to the equation Lu = 1 described in Theorem 3.1, (II) or (IV). Then, the function û, defined on Γ × S 1 ( l π ) by û(p, t) = u(p), for (p, t) ∈ Γ × S 1 ( l π ), verifies Lû = Lu = 1 and Γ×S 1 ( l π ) û = 2l Γ u ≥ 0. Theorem 3.1 (and Remark 3.2) shows that ψ is stable.

We now show that stability of ψ implies stability of ψ.

Let u ∈ H 1 (Γ × [0, l]) satisfying Γ×[0,l] u = 0. We extend u to a function in H 1 (Γ × [0, 2l]) by reflection across M × {l}, that is, we set u(p, t) = u(p, 2l -t) for all p ∈ Γ and t ∈ [l, 2l]. Clearly this function gives rise to a function û ∈ H 1 Γ × S 1 l π satisfying Γ×S 1 ( l π ) û = 0 and I(u, u) = 1 2 I(û, û) ≥ 0.
Therefore ψ is stable. This completes the proof.

For instance, consider the case of a tube of radius

ρ in M n (κ) × [0, l], κ = -1, 0, 1, n ≥ 2, where M n (-1) = H n , M n (0) = R n and M n (1) = S n .
The stability operator of the tube writes

L = ∆ + (n -1)(c κ (ρ) -1 + κ) with c -1 (ρ) = tanh 2 ρ c 0 (ρ) = ρ 2 c 1 (ρ) = tan 2 ρ
As round spheres in space forms are stable, we get the following characterization of stable tubes in M n (κ) × R, the case of tubes in R 3 was treated by Athanassenas [START_REF] Athanassenas | A variational problem for constant mean curvature surfaces with free boundary[END_REF] and Vogel [START_REF] Vogel | Stability of a liquid drop trapped between two parallel planes[END_REF].

Corollary 3.4. A tube of radius ρ and height l in

H n × [0, l] is stable if and only if π sinh ρ ≥ √ n -1 l.
A tube of radius ρ and height l in

R n × [0, l] is stable if and only if πρ ≥ √ n -1 l.
A tube of radius ρ and height l in

S n × [0, l] is stable if and only if π sin ρ ≥ √ n -1 l.
We now prove a general fact about the geometry of stable free boundary CMC hypersurfaces in a slab in M × R. It extends the result proved in [START_REF] Ainouz | Stable capillary hypersurfaces in a half-space or a slab[END_REF] for the case M = R n . Theorem 3.5. Let M be an n-dimensional connected and oriented Riemannian manifold and ψ : Σ → M × [0, l] a stable free boundary immersion connecting the two boundary components M × {0} and M × {l}, l > 0, of a slab in the Riemannian product M × R.

Then, either ψ(Σ) is a vertical cylinder over a closed immersed stable CMC in M or ψ(Σ) is locally a vertical graph and in this case the lowest eigenvalue of the stability operator on Σ with Dirichlet boundary condition is equal to 0. Furthermore, suppose ψ(Σ) is not a vertical cylinder. If M is simply connected and the restriction of ψ to each component of ∂Σ is an embedding, then ψ(Σ) is a global vertical graph over a domain in M. In particular, if M is either the Euclidean space R n , the hyperbolic space H n or a hemisphere S n + , then, under the same hypotheses, ψ(Σ) is rotationally invariant around an axis {p} × R, for some p ∈ M.

Proof. We start with the following general fact. Let ψ : Σ → M be a CMC immersion of an orientable manifold Σ of dimension n in an orientable Riemannian manifold M of dimension n + 1 and N a global unit normal to Σ. If X a Killing vector field on M then the function X • ψ, N lies in the kernel of the Jacobi operator L of Σ. We include a proof of this fact for the reader's convenience. The Jacobi operator is also known to be the linearized operator of the mean curvature functional. More precisely, let ψ t be a smooth deformation, through immersions, of ψ 0 = ψ and let H t be the mean curvature function of ψ t , then:

(3.4) 2 ∂H t ∂t | t=0 = L( ∂ψ t ∂t | t=0 , N ).
Now, let φ t be the local flow of isometries of M generated by the Killing field X and consider the deformation ψ t = φ t • ψ of ψ. Clearly, H t = H for all t and so the lefthand side of (3.4) vanishes. Furthermore, ∂ψt ∂t | t=0 = X • ψ. This shows that the function X • ψ, N lies in the kernel of L.

In our case, as the vertical unit vector field ∂ ∂t is a Killing field of the product M × R, the function v = ∂ ∂t , N verifies Lv = 0. If v is identically zero, then ψ(Σ) is a vertical cylinder whose base is an immersed CMC hypersurface in M and which is moreover stable by Theorem 3.3. Assume v is not identically zero. We will show it has a sign in the interior of Σ. Suppose by contradiction that v changes sign and consider the functions v + = max{v, 0} and v -= min{v, 0} which lie in the Sobolev space H 1 (Σ). Using the fact that v = 0 on ∂Σ, one has

I(v + , v + ) = Σ { ∇v + , ∇v + -(|σ| 2 + Ric(N ))(v + ) 2 } dΣ = Σ { ∇v, ∇v + -(|σ| 2 + Ric(N ))vv + } dΣ = - Σ {(∆v)v + + (|σ| 2 + Ric(N ))vv + } dΣ = 0
and similarily I(v -, v -) = 0. As we supposed that v changes sign, there exists a ∈ R such that Σ (v + + av -) dΣ = 0. So we can use v := v + + av -as a test function for stability. We have

I( v, v) = I(v + , v + ) + 2aI(v + , v -) + a 2 I(v -, v -) = 0.
Since ψ is stable, we conclude that v is a Jacobi function and so is, in particular, smooth. We distinguish two cases:

(i) If a = 1, then we conclude that v + and v -are smooth and so we can write Lv = Lv + + Lv -= 0 and L v = Lv + + aLv -= 0. It follows that Lv + = 0 and so, by the unique continuation principle [START_REF] Aronszajn | A unique continuation theorem for solutions of elliptic partial differential equations or inequalities of second order[END_REF], v + has to be identically 0, which is a contradiction.

(ii) If a = 1. Then v = v is a Jacobi function and so satisfies ∂v ∂ν = 0 on ∂Σ. Let p ∈ ∂Σ with ψ(p) ∈ M × {0} and Ω a neighborhood of p in Σ, diffeomorphic to the halfspace R n + , such that ψ : Ω → M × [0, l] is an embedding. Identify S = ψ(Ω) with Ω and call τ the reflection in M × R through M × {0}. Then S := S ∪ τ (S) is a C 2 hypersurface in M × R with constant mean curvature; S is therefore smooth. We now extend v to a function v on S by setting v = 0 on τ (S). As ∂v ∂ν = 0 on ∂S, we have v ∈ C 1 (S). Furthermore, because v = ∂v ∂ν = 0 on ∂S, one checks that v satisfies the equation Lv = 0 on S in the sense of distributions; L denoting the Jacobi operator on S. By regularity theory for elliptic PDEs, v is smooth. As v vanishes on a non empty subset, the unique continuation principle [START_REF] Aronszajn | A unique continuation theorem for solutions of elliptic partial differential equations or inequalities of second order[END_REF] implies that v ≡ 0 on S. Again, by the unique continuation principle, one has v ≡ 0 on Σ, which is a contradiction.

We have thus shown that the function v does not change sign in Σ. We will assume v ≥ 0, the case v ≤ 0 being similar. The function v satisfies v ≥ 0, Lv = 0.

As we are assuming v is not identically zero, by the strong maximum principle (Theorem 2.9 in [START_REF] Kazdan | Applications of partial differential equations to problems in geometry[END_REF]) we know that v > 0 on the interior of Σ. So the interior of ψ(Σ) is a local vertical graph. Moreover, since v does not vanish in the interior of Σ, it is a first eigenfunction of L and so 0 is the lowest eigenvalue of L for the Dirichlet problem on Σ. This proves the first statement.

Let us now prove the second statement. Assuming M is simply connected and ψ(Σ) is not a cylinder, we will show it is globally a vertical graph by analyzing its behaviour near its boundary.

For the sake of simplicity, we set M 0 = M × {0} and M 1 = M × {l}. Let Γ 1 , . . . , Γ k denote the connected components of ∂Σ. By hypothesis, ψ restricted to Γ i is an embedding and so ψ(Γ i ) separates the slice containing it, among M 0 and M 1 , into two connected components ( [START_REF] Hirsch | Differential topology[END_REF]).

Denote by P : M × R → M the projection on the second factor and set F = P • ψ. Fix i = 1, . . . , k and let ϕ : U -→ R be a smooth function defined in a neighborhood U ⊂ M of ψ(Γ i ) such that ψ(Γ i ) = {ϕ = 0} and for each p ∈ Γ i , ∇ϕ(ψ(p)) = N (p). For instance we may take ϕ to be the signed distance function to ψ(Γ i ).

Let us take a point p ∈ Γ i , and a curve γ : (-ǫ, 0] → Σ parametrized by arclength with γ(0) = p and γ(0) = ν(p). Set γ(s) := ψ(γ(s)) = (α(s), t(s)) where α = F • γ : (-ǫ, 0] → M and define the real function h on (-ǫ, 0] by h(s) = ϕ(α(s)).

Denoting by D the connection on M, and by D the one on M × R, we have

ḣ(0) = h(0) = 0, ḧ(0) = ∇ 2 ϕ( α(0), α(0)) + ∇ϕ(ψ(p)), D α ds (0) = N (p), D γ ds (0) = σ(ν(p), ν(p)).
Note that

∂v ∂ν = -σ(ν, ν) ν, e n+1 = +σ(ν, ν) if ψ(Γ i ) ⊂ M 0 , -σ(ν, ν) if ψ(Γ i ) ⊂ M 1 .
By the boundary point maximum principle (see, for instance, Theorem 2.8 in [START_REF] Kazdan | Applications of partial differential equations to problems in geometry[END_REF]), ∂v ∂ν < 0 on ∂Σ. So for t small, F (γ(t)) lies in the component of M \ F (Γ i ) which has N (p) as outwards (resp. inwards) pointing normal at

F (p) if ψ(Γ i ) ⊂ M 0 (resp. if ψ(Γ i ) ⊂ M 1 ).
It follows that there is a thin strip in the interior of Σ around Γ i which projects on this component. We call D i the component of M \ F (Γ i ) which does not intersect this projection.

We let Σ denote the (topological) manifold obtained by attaching, for each i = 1, . . . , k, D i to Σ using the diffeomorphism ψ| Γ i : Γ i → ∂D i (see, for instance, Theorem 9.29 in [START_REF] Lee | Introduction to smooth manifolds[END_REF] for the details of such a construction).

We define F : Σ → M by

F = F on Σ identity on D i , i = 1, . . . , k.
Note that F is well defined since, by construction of Σ, each x ∈ Γ i is identified with ψ(x) ∈ ∂D i . As the interior of ψ(Σ) is locally a vertical graph and thanks to the above analysis of the behaviour of ψ near ∂Σ, we see that F is a local homeomorphism. It is also clear that F is a proper map, thus it is a covering map. Therefore F is a global homeomorphism onto M. Consequently, ψ(Σ) is a graph over a domain in M . In particular, when M = R n , H n or S n + , Alexandrov's reflection technique shows that ψ(Σ) is a hypersurface of revolution around a vertical axis, see [START_REF] Wente | The symmetry of sessile and pendent drops[END_REF].

Remark 3.6. It is clear from the proof that a similar result is true for stable CMC hypersurfaces with free boundary in a half-space M × [0, +∞).

It is not difficult to deduce from Theorem 3.3 that if the Ricci curvature of M is bounded from below by a positive constant κ, then there is no stable cylinder in M × [0, l] for l > π/ √ κ (see the argument below). When M has dimension 2, we have the following stronger statement.

Theorem 3.7. Let M be an orientable Riemannian surface with Gaussian curvature

K ≥ κ > 0. If l ≥ 4π √ 3κ then there is no immersed stable free boundary CMC surface in M ×R connecting M ×{0} to M × {l}.
Proof. Let ψ : Σ → M × [0, l] be a stable CMC immersion with free boundary. Suppose ψ(Σ) is not a cylinder. By Theorem 3.5, we know that 0 is the lowest eigenvalue of the stability operator L on Σ with Dirichlet boundary condition. Denote by H the mean curvature of Σ and by S the scalar curvature function of M × R. We have

3H 2 + S(p, t) = 3H 2 + K(p) ≥ κ, for (p, t) ∈ M × R.
We can therefore apply Theorem 1 in [START_REF] Rosenberg | Constant mean curvature surfaces in homogeneously regular 3-manifolds[END_REF] which gives an upper bound for the intrinsic distance in Σ to ∂Σ. More precisely, for each x ∈ Σ,

d Σ (x, ∂Σ) ≤ 2π √ 3κ . If ψ : Σ → M × [0, l] connects M × {0} to M × {l}, take x ∈ Σ such that ψ(x) ∈ M × { l 2 }. Then l 2 ≤ d Σ (x, ∂Σ) ≤ 2π √ 3κ .
Moreover, if we have the equality l/2 = 2π/ √ 3κ, then d Σ (x, ∂Σ) = l/2 and so at least one of the geodesic segments {x} × [0, l/2] or {x} × [l/2, l] is contained in Σ. In this case, by Theorem 3.5, ψ(Σ) has to be a cylinder.

To conclude we need to check that cylinders over closed constant geodesic curves are unstable for l ≥ 4π/ √ 3κ. In fact a stronger statement is true. Consider a curve γ of constant geodesic curvature h in M. The lowest eigenvalue λ 1 (γ) of the stability operator on γ satisfies

λ 1 (γ) ≤ I(1, 1) γ ds = - γ (h 2 + K)ds γ ds ≤ -κ.

R. Souam

For l > π/ √ κ, we get

λ 1 (γ) + π 2 l 2 ≤ -κ + π 2
l 2 < 0 and so, according to Theorem 3.3, the cylinder is unstable. This completes the proof.

Stable capillary surfaces of genus zero in certain warped products

In this section we are interested in stable capillary surfaces in warped product spaces of the type [0, l] × f M where M = R 2 , S 2 or H 2 and f : [0, l] → R is a smooth positive function. More precisely, [0, l] × f M is the product space [0, l] × M endowed with the metric (with some abuse of notation) g = dt 2 + f (t) 2 g 0 , g 0 being the metric on M.

An important feature of these spaces we will use is that if ϕ : M -→ M is an isometry, then its trivial extension {id} × ϕ :

[0, l] × f M -→ [0, l] × f M is an isometry too.
We have the following extension to these spaces of a theorem proved in the Euclidean case in [START_REF] Ainouz | Stable capillary hypersurfaces in a half-space or a slab[END_REF]. Proof. Let γ be a connected component of ∂Σ such that ψ(γ) lies on {0} × M. We claim there is a circle C in M bounding a disk containing ψ(γ) and touching ψ(γ) at least at 2 points. For M = R 2 , the circumscribed circle about ψ(γ) has this property (cf. [START_REF] Osserman | Circumscribed circles[END_REF]). When M = H 2 , we can just take the (Euclidean) circumscribed circle about ψ(γ) in the half-space model since Euclidean circles in this model are also metric circles for the hyperbolic metric. When M = S 2 , we pick a point p ∈ S 2 \ ψ(γ) and perform stereographic projection σ from the point p onto the Euclidean plane R 2 . Let C * be the circumscribed circle in R 2 about σ(ψ(γ)). Its inverse image C := σ -1 (C * ) is a circle in S 2 which has the required property.

We will show that ψ(Σ) is a surface of revolution around the vertical axis passing through the center x of C. In the case of S 2 , we take x to be the center of the disk bounded by C that contains ψ(γ).

Let us consider the Jacobi function u on Σ induced by the rotations around the vertical axis passing through x. The function u verifies (4.1) Lu = 0 on Σ ∂u ∂ν = q u on ∂Σ

We will prove that u ≡ 0 on Σ.

Suppose, by contradiction, u is not identically zero. Then its nodal set u -1 (0) in the interior of Σ has the structure of a graph (cf. [START_REF] Cheng | Eigenfunctions and nodal sets[END_REF]). We will show that u has at least 3 nodal domains by analyzing the set u -1 (0)∩γ; a nodal domain of u being a connected component of Σ \ u -1 (0).

Otherwise said, H 3 can be viewed as the warped product R × e -t R 2 and we may assume, up to a rigid motion, that the two parallel horospheres are slices {x 3 = cst}. We can thus state the following Corollary 4.2. Let ψ : Σ → H 3 be an immersed capillary surface of genus zero connecting two parallel horospheres. If ψ is stable then ψ(Σ) is a surface of revolution around an axis orthogonal to the horospheres.

The isoperimetric problem in regions bounded by two parallel horospheres in H 3 was studied in [START_REF] Chaves | A free boundary isoperimetric problem in hyperbolic 3-space between parallel horospheres[END_REF] by Chaves, da Silva and Pedrosa.

Stable closed CMC surfaces in a product M × S 1 (r)

In this section, we consider stable CMC surfaces in a product M × S 1 (r), where M is a Riemannian surface with curvature positively bounded from below, K ≥ κ, with κ > 0 a constant and S 1 (r) is the circle of radius r > 0. We have the following result which is in the same vein as Theorem 3.7.

Theorem 5.1. Let ψ : Σ → M × S 1 (r) be a stable CMC immersion of a closed connected and oriented surface Σ in M × S 1 (r) where M is an orientable surface with Gaussian curvature satisfying K ≥ κ > 0, for some constant κ, and S 1 (r) is the circle of radius r > 0. Denote by p : M × S 1 (r) → S 1 (r) the canonical projection. Suppose that

r ≥ 4 √ 3κ ,
then the induced homomorphism

(p • ψ) * : π 1 (Σ) → π 1 (S 1 (r))
is trivial and therefore ψ lifts to a stable CMC immersion ψ : Σ → M × R.

Proof. We first derive an upper bound for the diameter of Σ.

λ 2 (Σ) = inf E⊂H 1 (Σ),dimE=2 sup u∈E\{0} -Σ uLu dΣ Σ u 2 dΣ . Since B d/2 (x) and B d/2 (y) have disjoint interiors, it follows that λ 2 (Σ) ≤ max{λ 1 (B d/2 (x)), λ 1 (B d/2 (y))}.
Therefore at least one of the numbers λ 1 (B d/2 (x)) and λ 1 (B d/2 (y)) is nonnegative.

Denoting by H the mean curvature of Σ and by S the scalar curvature function of M ×S 1 (r), we have

3H 2 + S(p, θ) = 3H 2 + K(p) ≥ κ, for (p, θ) ∈ M × S 1 (r).
We can thus apply Theorem 1 in [START_REF] Rosenberg | Constant mean curvature surfaces in homogeneously regular 3-manifolds[END_REF] which gives the upper bound d/2 ≤ 2π/ √ 3κ, that is, (5.1) diam(Σ) ≤ 4π √ 3κ .

Suppose now that the induced homomorphism π 1 (Σ) → π 1 (S 1 (r)) is not trivial and consider a loop γ : S 1 → Σ such that the loop p • ψ • γ : S 1 → S 1 (r) is nontrivial. We may assume that γ is a piecewise C 1 -immersion. Denote by d 0 the distance on M × S 1 (r), by d Σ the one on Σ and by d 1 the one on S 1 (r). Let x ∈ γ(S 1 ), then p • ψ • γ(S 1 ) is not entirely contained in an interval of radius < πr centered at p(ψ(x)) in S 1 (r), because otherwise the loop p • ψ • γ would be trivial. Therefore, there exists a point y ∈ γ(S 1 ) such that Moreover, if r = 4/ √ 3κ, then all the inequalities in (5.2) are equalities. In particular πr = d 1 (p(ψ(x)), p(ψ(y))) = d 0 (ψ(x), ψ(y)). It follows that if ψ(x) = (x 0 , θ) ∈ M × S 1 (r) then, we necessarily have ψ(y) = (x 0 , θ * ), where θ * ∈ S 1 (r) is the antipodal point of θ. Now, we can deform slightly the loop γ to a homotopic one γ satisfying x ∈ γ(S 1 ) and ψ(y) / ∈ ψ(γ(S 1 )). By the same argument as before, there must exist a point ȳ ∈ γ(S 1 ) satisfying πr = d 1 (p(ψ(x)), p(ψ(ȳ))) = d 0 (ψ(x), ψ(ȳ)). Again this implies that ψ(ȳ) = (x 0 , θ * ) = ψ(y), which is a contradiction. Therefore r < 4/ √ 3κ if the induced homomorphism π 1 (Σ) → π 1 (S 1 (r)) is not trivial. This completes the proof.

As an application, consider the sphere S 2 endowed with a Riemannian metric g of Gaussian curvature K ≥ κ > 0, for some positive constant κ and let r ≥ 4/ √ 3κ. Under these hypotheses, it follows from Theorem 5.1 and Theorem 3 in [START_REF] Ros | Stable periodic constant mean curvature surfaces and mesoscopic phase separation[END_REF] that an isoperimetric region in S 2 (g) × S 1 (r) is either a slab or a domain bounded by a surface of genus ≤ 2. Indeed, the boundary Σ of an isoperimetric domain Ω in (S 2 , g) × S 1 (r) lifts to an embedded stable closed CMC surface in (S 2 , g) × R by our result. By Theorem 3 in [START_REF] Ros | Stable periodic constant mean curvature surfaces and mesoscopic phase separation[END_REF], Σ has genus at most 2 if it is connected and is a union of a finite number of horizontal slices if it is disconnected. In the latter case, Ω has to be a finite union of disjoint slabs S 2 × [θ i , θ i + α i ], i = 1, . . . , n, in S 2 × S 1 (r). Note that a slab of width n i=1 α i has the same volume as the union U = ∪ n i=1 S 2 × [θ i , θ i + α i ] and its boundary has area less than the area of ∂U . As Ω is an isoperimetric domain, it has to be a slab in this case.

Theorem 4 . 1 .

 41 Let ψ : Σ → [0, l] × f M be an immersed capillary surface of genus zero connecting the two boundary components of [0, l] × f M where M = R 2 , H 2 , or S 2 and having constant contact angles θ 0 and θ 1 with {0} × M and {l} × M, respectively. If ψ is stable then ψ(Σ) is a surface of revolution around an axis R × {x}, x ∈ M .

(5. 2 )

 2 πr = d 1 (p(ψ(x)), p(ψ(y)) ≤ d 0 (ψ(x), ψ(y) ≤ d Σ (x, y) ≤ diam(Σ).It follows from (5.1) and (5.2) that r ≤ 4/ √ 3κ.

We first note that, because of the boundary condition satisfied by u, if p ∈ u -1 (0) ∩ ∂Σ then ∂u ∂ν (p) = 0. It follows from the boundary point maximum principle (see Theorem 2.8 in [START_REF] Kazdan | Applications of partial differential equations to problems in geometry[END_REF]) that u changes sign in any neighborhood of p ∈ u -1 (0) ∩ ∂Σ unless u is identically zero in a neighborhood of p. In the latter case, by the unique continuation principle [START_REF] Aronszajn | A unique continuation theorem for solutions of elliptic partial differential equations or inequalities of second order[END_REF], u would vanish everywhere on Σ, contradicting our assumption. Consequently each such point lies on the boundary of at least 2 components of the set {u = 0}.

If p ∈ ∂Σ is a critical point of the distance function to x restricted to γ, then one can check that u(p) = 0. Now, we observe that by the choice of C, there are at least 3 points in u -1 (0) ∩ γ. Indeed, we already know that there are two points in u -1 (0) ∩ γ. A third one is a point of γ whose image by ψ is a closest one to the center x of C.

Since by hypothesis Σ is topologically a planar domain, using the above information and the Jordan curve theorem, it is easy to see this implies that u has at least 3 nodal domains.

Denote by Σ 1 and Σ 2 two of these components and consider the following function in the Sobolev space H 1 (Σ):

where α ∈ R is chosen so that Σ u dA = 0. Using (4.1) we compute

Using a similar computation on Σ 2 , we deduce that I( u, u) = 0. As Σ is stable, we conclude that u is a Jacobi function. Indeed, the quadratic form on F associated to I has a minimum at u and so u lies in the kernel of I. However, u vanishes on a non empty open set. By the unique continuation principle [START_REF] Aronszajn | A unique continuation theorem for solutions of elliptic partial differential equations or inequalities of second order[END_REF], u has to vanish everywhere, which is a contradiction.

Therefore u ≡ 0. This means that ψ(Σ) is a surface of revolution around the axis through x.

The above result applies to the region bounded by two spheres centered at the origin for metrics on R 3 that are invariant under the group SO(3). This is, for instance, the case for the region bounded by two concentric spheres in R 3 , H 3 or S 3 . Another interesting case to which the result applies is the region bounded by two parallel horospheres in H 3 . Indeed, consider the half-space model of H 3 , that is,

equipped with the metric

Making the change of variables t = log x 3 , we see that the metric writes ds 2 = e -2t (dx 2 1 + dx 2 2 ) + dt 2 .


Dawin Baden

Pierre Henry

Ginette Saracco

Lionel Marié

Alain Tonetto

Yves Guglielmi

Seiji Nakagawa

Gérard Massonnat

Total Jean-Paul Rolando

How seismic anisotropy changes with scale

à 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:

This study is consecutive to a series of published works aiming at characterizing both reservoir and elastic properties of Lower Cretaceous limestone from the Urgonian platform of Provence (SE, France). References describing the characteristics of this platform in terms of facies, and biostratigraphy are available e.g. [START_REF] Leonide | Relation between Stratigraphic Architecture and Multi-Scale Heterogeneities in Carbonate Platforms: The Barremian-lower Aptian of the Monts de Vaucluse, SE France[END_REF]). These microporous bioclastic limestones are analogues of different hydrocarbon reservoirs in Middle East, e.g. Kharaib and Shuaiba formations [START_REF] Borgomano | Petrophysics of Lower Cretaceous Platform Carbonate Outcrops in Provence (SE France ): Implications for Carbonate Reservoir Characterisation[END_REF]). In addition, several published databases document coupled porosity, and elastic waves velocities measurements from the Urgonian platform [START_REF] Fournier | Critical Porosity and Elastic Properties of Microporous Mixed Carbonate-Siliciclastic Rocks[END_REF][START_REF] Fournier | Elastic Properties of Microporous Cemented Grainstones[END_REF][START_REF] Fournier | Pore Space Evolution and Elastic Properties of Platform Carbonates (Urgonian Limestone, Barremian-Aptian, SE France)[END_REF][START_REF] Borgomano | Petrophysics of Lower Cretaceous Platform Carbonate Outcrops in Provence (SE France ): Implications for Carbonate Reservoir Characterisation[END_REF]. In these works, the authors used conventional laboratory approach, i.e. velocity measurements carried out on 1" to 1.5" mini-cores, under effective stress; and they discussed "effective media theory", and the concept of "pore aspect ratio" extensively. Nevertheless, a known limitation of these approaches is the implicit assumption of medium's isotropy. Despite this assumption is generally true at plug scale, it is rarely the case at larger scale. Carbonate rocks are often fractured and may have either "facies-related" or "patchy" porosity distribution that may lead to seismic anisotropy.

The works presented here focus on the impact of up-scaling onto elastic properties of carbonates rocks. Ultrasonic measurements have been carried out onto laboratory-sized samples, and the results are compared to published works, and to our crosshole acoustic survey (cf. our first presentation).

Geological context:

The studied formations are located within vadose zone of "Fontaine de Vaucluse" aquifer system. LSBB (Low Noise Underground Laboratory) GAS-gallery gives access to the 30° southward-dipping layers, and five vertical fully-cored boreholes (~20m deep) were drilled as part of previous works [START_REF] Jeanne | Architectural, Petrophysical and Hydromechanical Properties of Fault Zones in Fractured-Porous Rocks: Compared Studies of a Moderate and a Mature Fault Zones (France)[END_REF]Jeanne, Guglielmi, and Cappa 2013;Jeanne, Guglielmi, and Cappa 2012;Jeanne et al. 2012). The present study focuses on analyzing elastic properties of six 5" cores (C01 to C06), which are representative of different layers intersected by the boreholes (Figure 1). The facies sampled are inner-platform facies i.e. low to moderate energy, muddy or peloidal carbonate sands with abundant rudists. Cores analyses emphasized two facies groups:

(1) Calcarenites (grainstone to rudstone), (2) Calcilutites (wackestone to packestone). Reservoir properties of this facies are related to diagenesis [START_REF] Léonide | Diagenetic Patterns and Pore Space Distribution along a Platform to Outer-Shelf Transect (Urgonian Limestone, Barremian-Aptian, SE France)[END_REF], hence, we do not describe them any further in this abstract, instead, we give extensive description of two cores selected to exemplify our works (i.e. C03 & C04). C03 was selected because it shows gradual transition within a same facies. It is a bioclastic grainstone to rudstone with abundant centimeter scaled rudists fragments and foraminifera. The transition is materialized by the relative abundance of macroscopic bioclasts (rudists), the top of C03 has higher density of macroscopic fragments, whereas bottom has only sand scaled bioclasts. We did not observe any variations in the matrix, and thin sections show large rudists fragments packed into a fine grained matrix, the grains size is <300µm, and the matrix texture ranged from packestone to grainstone (Figure 2). The micrite in C03 is compact, with low intercrystalline pores. Expectedly, porosity (<1%) and permeability (<1mD) values are as bad as guessed from the SEM images. Absence of macroscopic pores (i.e. other than fractures), and tightness of micrite crystals explain the poor reservoir quality. Another important feature of C03 is partly-open fractures and cracks crossing the sample. The footprint of fracturing, is visible on thin sections, since fractures' porosity, significantly increases the overall porosity.

C04 represents the most porous interval in studied formation, its porosity is about 15% but may reach up to 20%, and its permeability ranges from 2 to 3.5mD. C04 facies is a bioclastic grainstone to rudstone with large rudists' fragments. The thin sections show grain size ranging from 200µm, for the finest, to 2mm for the largest (Figure 2). Macroscopic pores both moldic and vuggy, are frequent, but the overall porosity, is dominated by intercrystalline porosity within the micrite (microporosity). SEM images show that micrite crystals are larger than that of the non-porous samples. The micrite crystals are loosely packed, euhedral, and heterogeneous in size, (i.e. 1 to 5µm), while intercrystalline pores are abundant, and relatively well connected because of either poor sorting, or low contact area between micrite crystals.

Material and methods:

Ultrasonic measurements were carried out in two parts. Firstly, the 5" cores were preliminarily saturated, then flooded in an acoustic tank, 20°C tap water was used during all steps. We do not give an extensive description of the experimental set up in this abstract, but Figure 3 shows the experiment. Secondly, three 1.5" mini-cores (plugs) were drilled out of each 5" core. The mini-cores were taken in directions normal, parallel, and 45° to beddings, then wave velocities were measured using pairs of P-and S-wave PANAMETRICS ultrasonic transducers (1MHz). Good surface contact was ensured by using a thin lead foil at each interface, and by applying surface contact force using a vise. The data were investigated using model of transversely isotropic (TI). For TI materials, the stiffness tensor (CIJ) written in Voigt's notation, requires only five independent components to fully describe the elasticity (equation ( 1)).

                       (1)
After equation ( 2), components of CIJ can be obtained from the density (ρ), and five velocity measurements including both quasi-longitudinal (Vp), and pure-shear (Vsh) phase-velocities [START_REF] Mavko | The Rock Physics Handbook[END_REF].

      1 2 2 11 (
c Vp c c c c 2c c Vsh c c c c c Vsh                            (2)
Thomsen ( 1986) definition for weak TI media states the conditions 1  and/or 1  must hold, and the author also suggested an approximation of P-wave phase velocity Vp(θ) for weak TI material, using P-wave velocity (noted α in equation ( 3)), and three constants, namely ε, γ, and δ, given by following formulas:

                 
                         (3)
For mini-cores, components of CIJ were computed using equation( 2). Regarding mini-cores size, any anisotropy at this scale is related either to matrix, or micro-cracks, but not to macroscopic fractures. For 5" cores we fitted Vp(θ) models, using equation ( 3), onto velocity data for each transversal section. This gave us an estimation of quantities α, ε, and δ.

Finally, these quantities (Thomsen's parameters) and/or the stiffness coefficients, were compared to results obtained on mini-cores (1.5"), cores (5"), and crosshole survey (meter to multi-meter).

Results and Discussion:

The results of the "mini-core approach" are given in Table 1. CIJ components are nearly identic for non-porous samples (i.e. C01, C02, C03, and C05), whereas they are significantly lower for porous ones (i.e. C04, C06). This values are consistent with CIJ components obtained from 1" mini-cores, and crossholeultrasonic survey (see Baden et al., @submitted article, [START_REF] Fournier | Pore Space Evolution and Elastic Properties of Platform Carbonates (Urgonian Limestone, Barremian-Aptian, SE France)[END_REF], and #1 Baden et al., @SEG2017), but are significantly higher than that from [START_REF] Bereš | Seismic Anisotropy Analysis at the Low-Noise Underground Laboratory (LSBB) of Rustrel (France)[END_REF], for measurements at seismic frequencies (Table 2). Focusing on C03 and C04 (Table 1), one can see that shear anisotropy (γ) is <1%, therefore it is negligible. Conversely, ε is very low for C03 (2.3%), but is significant for C04, where it reaches ~12%. This results emphasizes that at matrix scale, porous samples can show significant P-wave anisotropy, whereas not-porous ones are nearly isotropic. Consequently, intercrystalline pores may be responsible for most of observed anisotropy.

Table 1. Results of the analyses on mini-cores. 0,004 0,048 0,023 -0,118 -0,025 -0,014 γ 0,003 0,001 -0,002 -0,008 -0,002 -0,001 δ -0,074 0,137 -0,167 -0,201 0,080 -0,053

CIJ×10 9 ; ρ (kg/m 3 )
Up-scaling analyses to 5" cores, one can see in most cases, Pwave velocities are low anisotropic in the transverse plane, i.e. ε range between ±5%, for given transversal-section, (Figure 4, and Figure 5). When particular features such as fractures or large cemented-bioclasts (e.g. recrystallized corals and rudists) occur, P-wave velocities become clearly anisotropic, and ε can reach up to ±20%. CT scan imaging show that in non-porous samples (e.g. C03) anisotropy (in transverse plane) is related to fractures and cracks only, and its magnitude can be related to either high density of thin cracks, or thick single-fracture. In porous sample (e.g. C04) anisotropy in transverse plane can be related to either density contrasts within porous matrix, or inclusion of macro-fossils (Figure 5). In first case, P-wave velocity can stay close to mini-cores values, but in the second case it can be significantly higher than that of matrix alone.

Table 2. Ranges for CIJ (×10 9 ) in Urgonian limestone.

[ ,9 -36,9 96,3 -39,5 110,3 -29,5 110,4 -26,8 C13 19,7 -18,3 43,5 -12

1] [2] [3] [4] C11 44

Conclusion:

Our multi-scale approach integrated data from centimeter-scale (1", 1.5" mini-cores), decimeter-scale (5" cores), multi-meter (ultrasonic crosshole), and hectometer-scale (seismic), these data were collected using frequency ranges suitable for the scales investigated, i.e. 1MHz, 250kHz, 50kHz, and 1-100Hz, respectively.

Although anisotropy is measureable at every scales, causes of that anisotropy can vary, or interfere with each other, according to scale. The data showed that porous matrix could be weakly anisotropic, at plug-scale, inter-crystalline pores may be the reason [START_REF] Fournier | Pore Space Evolution and Elastic Properties of Platform Carbonates (Urgonian Limestone, Barremian-Aptian, SE France)[END_REF]. At centimeter-scale, patchy distribution of some physical properties (e.g. density) and/or local fractures/cracks distribution, produce anisotropy in the transverse plane, meaning similar consequences may be expected in the vertical plane. Effects of minerals/pores orientation and local fractures distribution are also visible at multi-meter scale, they are expressed by anisotropy being tightly correlated to beddings. However, when fracturing dominates signal from matrix anisotropy may be overlapped by fracture-related anisotropy. As shown by lack of correlation between CIJ components from seismic-scale measurements, and laboratory to multi-meter scale ones (Table 2). Therefore scale effect must be handled carefully in anisotropy analyses, especially for carbonate formations.

Figure 1 .

 1 Figure 1. Synthetic lithology and porosity logs of studied formations, and localization of cores C01 to C06.

Figure 2 .

 2 Figure 2. Stained thin-sections (left) and SEM imaging (right) of cores C03 (top) and C04 (bottom). Notice the contrast in micrite crystals shapes and inter-crystalline pores between the non-porous C03 and porous C04.

Figure 3 .

 3 Figure 3. Experimental set up for ultrasonic analyses on 5" cores. The instrumentation included: 250-kHz IMASONIC immersion transducers, oscilloscope TEKTRONIX-DPO4034, pulse generator-receiver PANAMETRICS-5058PR.During acquisition transducers rotate around the sample. The rotation step (Δϴ), is 5°, and for a given transversalsection, 72 signals (stacked: ×64) are recorded. After that the transducers are moved 1cm up (ΔZ=1cm), then the process is repeated.

Figure 4 .

 4 Figure 4. Estimation of α, ε, and δ using curve fitting of Vp(θ) on the 5" cores data (cf. transversal-section). The count is given by ordinate axes [0, 40].

Figure 5 .

 5 Figure 5. P-wave velocity maps and CT scan images of C03 & C04. Maps are 2D version (i.e. unrolled) of the 3D acquisition grid. The CT scan slices (longitudinal, and transversal) are commented to emphasize impact of bioclasts and fractures on recorded velocities. The gray level gives an idea of actual density, e.g. whitedensenon-porous.

Acknowledgements:

This works were supported by two Research programs: H-CUBE project (ANR-12-SEED-0006), D. Baden's PhD grant; and ALBION-HPMSCa project, funded by TOTAL.


John Gliksberg

Antoine Capra

Alexandre Louvet

Pedro Javier Garcia

Devan Sohier

Pedro Javier García

High-Quality Fault Resiliency in Fat Trees

Keywords: HPC, routing, fat-tree, fault-resiliency !

INTRODUCTION

A MAJORITY of current leading network topologies for High Performance Computing (HPC) clusters are fattree variants. (The five most powerful clusters of the June 2019 Top500 list [START_REF] Strohmaier | Top500[END_REF] had fat-tree topologies.) These networks have some form of static routing tables computed by a centralised routing engine and uploaded to all switches.

It is sufficient for fat-tree-specific routing algorithms to be minimal to guarantee deadlock-free routing, and the regular nature of their target topology class should simplify load-balancing strategies. PGFTs [START_REF] Zahavi | D-mod-k routing providing non-blocking traffic for shift permutations on real life fat trees[END_REF] describe all regular fattrees for which there is at most one downward switch-path from any switch to any node (as shown in Figure 1). In this article we refer to fat-trees as PGFTs. The oblivious routing algorithm for non-degraded PGFTs (Dmodk [START_REF] Zahavi | D-mod-k routing providing non-blocking traffic for shift permutations on real life fat trees[END_REF], see Section 2) uses this property and their connection logic to provide load balance through an arithmetic rule.

Due to the sheer amount of equipment in current and future supercomputers, hardware failures are to be expected [START_REF] Domke | Fail-in-place network design: interaction between topology, routing algorithm and failures[END_REF] (especially in optical links [START_REF] Connors | Simulation framework for studying optical cable failures in dragonfly topologies[END_REF] typically used in higher levels of fat-trees) and should not hinder running applications as far as possible. The fabric manager can react to equipment failures that do not break graph connectivity by uploading updated routing tables. In order to do this it requires a fault-resilient routing algorithm capable of rapid re-routing. The challenge is to provide these characteristics while maintaining high-quality static load balance.

Some of the research regarding oblivious fault-resilient routing focuses on techniques that explicitly target degradations to regular fat-trees [START_REF] Zahavi | Quasi fat trees for hpc clouds and their fault-resilient closed-form routing[END_REF] [START_REF] Quintin | Transitively deadlock-free routing algorithms[END_REF]; there are several re-routing strategies for these techniques. OpenSM's UPDN [START_REF] Opensm | Current OpenSM Routing § UPDN Routing Algorithm[END_REF] and Ftree [START_REF] Zahavi | Optimized InfiniBand™ fat-tree routing for shift all-to-all communication patterns[END_REF] routing engines can also be applied from scratch to a degraded fat-tree. PQFT [START_REF] Zahavi | Quasi fat trees for hpc clouds and their fault-resilient closed-form routing[END_REF] is similar, though it requires a complete list of faults. The combination of Dmodk + Ftrnd_diff [START_REF] Vignéras | The bxi routing architecture for exascale supercomputer[END_REF] available in BXI FM [START_REF]Bull exascale interconnect[END_REF] is applied in an offline/online manner (with an iterative list of network changes and an up-to-date view of the network), the goal being fast reaction to faults with minimal routing changes.

• * Li-Parad, UVSQ, Versailles, {john.gliksberg,devan.sohier}@uvsq.fr • † Atos, Bruyères-le-Châtel, {antoine.capra,alexandre.louvet}@atos.net Fabriscale [START_REF] Villanueva | Routing and faulttolerance capabilities of the fabriscale fm compared to opensm[END_REF] also provides fast centralised re-routing of fat-trees, by precomputing alternative routes. A short summary of the limits of the existing approaches is provided in a previous conference paper [START_REF] Gliksberg | High-quality fault-resiliency in fat-tree networks (extended abstract)[END_REF].

The approach that we propose to meet that challenge is to apply the closed-form arithmetic formula of Dmodk while relaxing the topological constraint. For that purpose, we compute shortest paths explicitly rather than relying on an addressing scheme, and we balance load according to locally propagated information rather than relying on levelwide constants. These two goals are addressed together during preprocessing and will be the focus of this article, whose main contribution is the detailed algorithm description in Section 3.

DMODK

The Dmodk routing algorithm and corresponding PGFT topology are described in detail in [START_REF] Zahavi | D-mod-k routing providing non-blocking traffic for shift permutations on real life fat trees[END_REF]. The algorithm relies on a criterion (not shown here) to determine whether a destination d must be routed within the down ports and, if so, which one. Otherwise, an arithmetic formula defines the up port (with index p) to select:

p = d / l k=1 w k mod (w l+1 p l+1 )
The level-wide constants (or arities) w l and p l respectively denote the numbers of uplinks and of interlinks of all switches at level l. With this formula, each destination's routes are coalesced as early as possible, and routes to different destinations are spread out as much as possible, thus minimising collisions between independent traffic. These closed-form steps rely on a given organisation of addresses of switches and indexing of their ports. Dmodk is a very low complexity and perfectly parallel routing algorithm for PGFTs, but it is not applicable to degraded PGFTs or irregular fat-trees.

DMODC DESCRIPTION

The idea behind the fault-resilient algorithm that we propose is to rely on local information while using the same closed-form arithmetic formula as Dmodk. The c in Dmodc refers to the neighbouring switches explicitly determined to be closer to the destination among which paths are chosen. The aim is fast centralised computation of routing tables for degraded PGFTs, providing optimal or well-balanced deterministic routes even under heavy fabric degradation. The algorithm begins with a preprocessing phase (that can be multi-threaded) followed by a parallel computation phase. Links are assumed to be bi-directional; notations used in the expressions hereafter are defined in Table 1. is the cost of switch s to leaf switch l Πs is the divider of switch s

Basic Preprocessing

For ranking, levels and link directions are determined according to leaf switches being equivalent to the lowest level. Groups of ports linked to the same switch are prepared and sorted by globally unique identifier (GUID) to help with same-destination route coalescing.

Cost

We define the cost c s,l of a switch s to a leaf switch l to be the minimum number of hops between each other under up-down restrictions according to rank, as defined in Procedure 1 and illustrated in Figure 2. This later allows us to determine valid paths by exploring neighbouring switches and comparing costs. That exploration could be done here to prepare sets of output ports, but it's better to leave it for later since each set is only used once (see Subsection 3.4). Other all-pairs shortest paths methods could be substituted here. At each propagation step, the updated costs are in grey. Note that in steps 3-5, some propagations are interrupted due to the c s,l + 1 < c s ,l condition in the procedure. They could have been achieved with a simple c s ,l = ∞ condition instead; however this would have also interrupted the propagation of 2 in step 5. As a result, the long path on the left would not have been avoided. For PGFTs (degraded or not), such cases are actually impossible and the simple condition would suffice; but it would not guarantee shortest up-down paths in fat-tree-like topologies.

∞ 0 ∞ ∞ ∞ ∞ 0. ∞ 0 1 ∞ 1 ∞ 1. 4 0 1 3 1 2 2.-4.

Procedure 1 Compute costs and dividers

for all s ∈ S do for all l ∈ L do c s,l ← ∞ Π s ← 1 for all l ∈ L do c l,l ← 0 for all s ∈ S sorted in ascending rank order do π ← Π s × #{s s} for all s s do for all l ∈ L | c s,l + 1 < c s ,l do c s ,l ← c s,l + 1 for all s s | Π s < π do Π s ← π for all s ∈ L sorted in descending rank order do for all s s do for all l ∈ L | c s,l + 1 < c s ,l do c s ,l ← c s,l + 1

Thanks to the up-down restriction, the complexity of this procedure is in O(#E#L). This restriction is only for efficiency, it does not enforce deadlock-freedom. Some fat-treelike topologies would result in up-down-up-down paths (if such shortcuts appear in neighbouring switches), since path selection does not distinguish up and down neighbours. Avoiding this requires a slightly different method: an extra integer must be stored, similar to cost but only for downpaths. More detail can be found in Section 3.4.

In our partially parallel implementation, each worker thread obtains a block of switches to propagate with one barrier per level upwards, then downwards.

Divider

Dmodc is based on the same arithmetic formula as Dmodk. Prior to the modulo operation, it begins with an integer division by the product of #{s ∈ S | s s} (the upward arity At each propagation step, the updated dividers are in grey. Note that in step 2, the first upswitch is not updated because π = 2 × 2 ≤ 6. Even though there are multiple degradations in the considered case, all top switches end up with the divider that they would have had in the complete network.

of s) of switches at each lower level. This value represents the number of consecutive destinations to route through the same port. It is multiplied when going up levels to mirror the number of consecutive choices by switches below before each switch is chosen again. To reflect the actual state of the network (in which switches of the same level may have different arities), only local information must be considered; in turn, this operation is based on the products of up-to-date counts of upswitches (switches connected above), as defined in Procedure 1. Each downpath corresponds to a potential divider value, and we choose to keep only the maximum (as illustrated in Figure 3). The underlying motivation is to generate the same values as in the non-degraded PGFT, as long as the topological subgroup is not systematically degraded. The complexity of this part of the procedure is in O(#E).

Routes Computation

The deterministic output port p s,d and alternative output ports P s,d of every switch s for every destination d ∈ N (not directly linked to s) are selected with a closed-form formula based on the results previously determined. First, port groups leading closer to λ d are selected in (1) (without taking ranking into account), setting corresponding alternative output ports in (2):

C s,λ d ← g ∈ G s | c Ωg,λ d < c s,λ d (1) P s,d ← {p ∈ g | g ∈ C s,λ d } (2)
Selected port groups C are stored in an array (ordered by GUID of their remote switch), also represented by C: individual groups are accessed with indices i ∈ [0, #C s,λ d [ using the C s,λ d [i] notation. From this, the output port group is chosen in (3) and the port within that group in (4):

g s,d ← C s,λ d [ d Π s mod #C s,λ d ] (3)
p s,d ← g s,d [ d Π s × #C s,λ d mod #g s,d ] (4)
Routes are computed in a loop over leaves so that C s,λ is determined only once for all nodes connected to λ (with P s,d

P s,20

Π = 4 g s,20 (2)
p s,20 also unchanging ∀ d | ∃ λ d ). Figure 4 illustrates assignments (1), ( 2), (3), and (4).

The cost variant for up-down restriction described in 3.2 requires (1) to compare c values for upswitches and the downpath cost value for downswitches.

RESULTS

The algorithm was implemented in the fabric management software for Atos's Bull eXascale Interconnect (BXI). The same code has been used for validation, simulation, and in production.

Validity

Routing is valid for degraded PGFTs if and only if the cost of every leaf switch to every other leaf switch is finite: this reflects every node pair having an up-down path. Our implementation includes a pass through all leaf switch pairs to verify this condition. The up-down path restriction is sufficient to guarantee deadlock-freedom within degraded PGFTs [START_REF] Quintin | Transitively deadlock-free routing algorithms[END_REF].

Runtime

Our C99 implementation had computation of cost, divider, and routes spread over POSIX threads fetching work with a switch-level granularity. Figure 5 reports complete algorithm execution time alongside OpenSM (version 3.3.21) routing times (measured by adding timers in the source code) running on the same machine. For clusters ranging up to many tens of thousands of nodes, Dmodc provides fast enough re-routing for a centralised fabric manager to react to faults before applications are interrupted.

Quality

The routing algorithm was tested for quality by generating randomly degraded networks, computing corresponding routing tables, and then determining maximum congestion risk for multiple communication patterns. This study is available in a previously published extended abstract [START_REF] Gliksberg | High-quality fault-resiliency in fat-tree networks (extended abstract)[END_REF]. The results are comparable or better than the other available algorithms across the studied range of degradations.

CONCLUSION

The simulation results in Section 4 show that Dmodc provides high-quality centralised fault-resilient routing for PGFTs at a fraction of the runtime of existing algorithms, without relying on partial re-routing. Dmodc is also applicable to fat-tree-like topologies (as mentioned in Figure 2) but with lower-quality load balancing. As defined here, no effort has been made to minimise the size of updates to be uploaded to switches throughout the fabric. This algorithm is implemented inside BXI FM [START_REF]Bull exascale interconnect[END_REF] and has been successfully deployed to an 8490 node PGFT production network in which it helps provide fault-resiliency even when faced with thousands of simultaneous changes. Devan Sohier PhD in Computer Science, is a full professor at Versailles Saint-Quentin-en-Yvelines University (UVSQ), within the LI-PaRAD lab. He has previously been an associate professor at the University of Reims and at UVSQ. His primary research interest is distributed algorithms (in particular probabilistic distributed algorithms in stochastic environments), with applications to HPC. He has advised 3 PhD students, and is currently advising 2 others.

Antoine Capra

Fig. 2 .

 2 Fig. 2. Example sequence of cost propagation steps in a degraded part of a network. Costs to the bottom-right switch are shown in switches.At each propagation step, the updated costs are in grey. Note that in steps 3-5, some propagations are interrupted due to the c s,l + 1 < c s ,l condition in the procedure. They could have been achieved with a simple c s ,l = ∞ condition instead; however this would have also interrupted the propagation of 2 in step 5. As a result, the long path on the left would not have been avoided. For PGFTs (degraded or not), such cases are actually impossible and the simple condition would suffice; but it would not guarantee shortest up-down paths in fat-tree-like topologies.

Fig. 3 .

 3 Fig.3. Example sequence of divider propagation steps in a degraded part of a network. Dividers are shown in switches. At each propagation step, the updated dividers are in grey. Note that in step 2, the first upswitch is not updated because π = 2 × 2 ≤ 6. Even though there are multiple degradations in the considered case, all top switches end up with the divider that they would have had in the complete network.

Fig. 4 .

 4 Fig. 4. Example route computation with s in grey, Πs = 4, and d = 20. Costs to λ 20 are shown in switches. Indices are ordered from left to right. The top-right group is chosen as g s,20 because 20/4 mod 2 = 1, and the right port in g s,20 is chosen as p s,20 because 20/(4 × 2) mod 3 = 2.

Fig. 5 .

 5 Fig. 5. Algorithm runtime on a 2.50GHz Intel Xeon E5-2680 v3 for Real-Life Fat-Trees of varying sizes (in log-log scale; lower is better).

  PhD in Computer Science, is a lead technical developer in two BXI projects at Atos, France. His thesis work focused on virtualisation in HPC context. His research interests include routing algorithms for HPC interconnects and optimisations to the MPI software layer. He has contributed to several routing algorithms used in BXI-based clusters. Alexandre Louvet Lead technical developer in multiple BXI projects at Atos, France. His research interests include storage, algorithmic, and low-level optimisations for HPC. He has re-architectured the BXI fabric management software, developed several routing algorithms used in BXI-based clusters and improved numerous aspects of BXI's stack. Pedro Javier García PhD in Computer Science, is an Associate Professor of Computer Architecture and Technology at Castilla-La Mancha University (UCLM), Spain. His research focuses on high-performance interconnection networks. He has published around 60 refereed papers in journals and conferences. He has guided 2 doctoral theses. He has coordinated 3 research projects funded by the Spanish and Castilla-La Mancha Governments. He has coordinated 4 R&D agreements between UCLM and different companies.

TABLE 1 Notations

 1 Used in Expressions.

	Gs	is the ordered list of port groups of switch s
	Ωg	is the switch connected to port group g
	#	denotes cardinality
		Dmodc-specific notations:
	c s,l

S

is the set of switches L is the set of leaf switches (L ⊂ S) N

is the set of nodes E is the set of edges λn is the (only) leaf switch connected to node n (λn ∈ L) , respectively denote down and up links, according to rank

ACKNOWLEDGEMENTS

This research has been undertaken under a cooperation between CEA and Atos. with the goal of co-designing extreme computing solutions. This research was partly funded by a grant of Programme des Investissements d'Avenir. This work has been jointly supported by the Spanish Ministry of Science, Innovation and Universities under the project RTI2018-098156-B-C52 and by JCCM under project SBPLY/17/180501/000498. BXI development was also part of ELCI, the French FSN (Fond pour la Société Numérique) cooperative project that associates academic and industrial partners to design and provide software components for new generations of HPC datacenters.