Jean-Claude Martin
email: martin@limsi.fr

Radoslaw Niewiadomski

Laurence Devillers

Stephanie Buisine
email: stephanie.buisine@paris.ensam.fr

Catherine Pelachaud
email: c.pelachaud@iut.univ-paris8.fr

MULTIMODAL COMPLEX EMOTIONS: GESTURE EXPRESSIVITY AND BLENDED FACIAL EXPRESSIONS

Keywords: Emotion, multimodality, Embodied Conversational Agent, corpus

One of the challenges of designing virtual humans is the definition of appropriate models of the relation between realistic emotions and the coordination of behaviors in several modalities. In this paper, we present the annotation, representation and modeling of multimodal visual behaviors occurring during complex emotions. We illustrate our work using a corpus of TV interviews. This corpus has been annotated at several levels of information: communicative acts, emotion labels, and multimodal signs. We have defined a copy-synthesis approach to drive an Embodied Conversational Agent from these different levels of information. The second part of our paper focuses on a model of complex (superposition and masking of) emotions in facial expressions of the agent. We explain how the complementary aspects of our work on corpus and computational model is used to specify complex emotional behaviors.

Introduction

One of the challenges of designing virtual humans is the definition of appropriate models of the relation between realistic emotions and the coordination of behaviors in several modalities. Studies of the non-verbal behaviors occurring during emotions have focused on mono-modal and acted basic emotions during experimental in-lab situations. Yet, in order to design Embodied Conversational Agents (ECAs) with human-like qualities, other sources of knowledge on multimodal behaviors occurring during real-life complex emotions deserve consideration, such as audiovisual corpora of spontaneous behaviors. This raises several questions: How does one collect data on spontaneous emotions? How does one represent and classify such complex emotions? Which dimensions of multimodal behaviors are perceptually related to these emotions and require representation?

Our aim is not only to reproduce multimodal behaviors with an ECA but also to study the coordination between modalities during emotional behaviors, in particular in the case of complex emotions. In order to design ECAs with such human-like qualities, one preliminary step is to identify the levels of representation of emotional behavior. For example, regarding the analysis of videos of real-life behaviors, before achieving the long-term goal of fully automatic processing of emotion from low levels (e.g. image processing, motion capture) to related behaviors in different modalities, a manual annotation phase might help to identify the representation levels that are relevant for the perception of complex emotions. Similarly to the copy-synthesis approaches that have been developed for speech, the replay by an ECA of these manually annotated behaviors can be useful for the validation of the model relating emotions and multimodal behaviors.

Since the externalization of nonverbal behaviors plays an important role in the perception of emotions, our approach is to model what is visible; that is we consider the signals and how they are displayed and perceived. We do not model the processes that were made to arrive to the display of such and such signals; we simply model the externalization part. We are interested in understanding and modeling how a given emotion would be both perceived and expressed quantitatively and qualitatively.

In this paper, we propose a model for the representation of non-verbal visual behaviors occurring during complex emotions. It makes a distinction between two types of complex emotions: superposition of emotions and masking of emotions.

The first part of the model aims at representing gesture expressive behaviors during superposition of emotions and is grounded in a video corpus. The second part of the model aims at representing facial behaviors during superposition of emotions and masking of emotions. It is grounded in the literature of facial expressions during complex emotions.

The remaining parts of this paper are structured as follows. Section 2 summarizes some of the studies on complex emotions, gesture expressivity, and facial expressions. Section 3 provides two examples of gesture and facial expression behaviors observed during complex emotions in videos of TV interviews. Section 4 describes the part of the model that we propose for representing gesture expressivity. Section 5 describes the part of the model focusing on facial expressions of complex emotions. Section 6 explains how this model has been used for the annotation of expressive behaviors observed in videos, and for the specification of expressive gestures in the Greta agent. [START_REF] Ekman | Unmasking the Face. A Guide to Recognizing Emotions from Facial Clues[END_REF]

Related Work

There has been a lot of psychological research on emotion and nonverbal communication in facial expressions, [START_REF] Ekman | Unmasking the Face. A Guide to Recognizing Emotions from Facial Clues[END_REF] vocal expressions [START_REF] Schröder | Experimental study of affect burst[END_REF][START_REF] Cowie | Emotional states expressed in speech[END_REF][START_REF] Banse | Acoustic profiles in vocal emotion expression[END_REF] and expressive body movements. [START_REF] Demeijer | The contribution of general features of body movement to the attribution of emotions[END_REF][START_REF] Newlove | Laban for Actors and Dancers[END_REF][START_REF] Boone | Children's decoding of emotion in expressive body movement: The development of cue attunement[END_REF][START_REF] Wallbott | Bodily expression of emotion[END_REF] Yet, these psychological studies w e r eb a s e dm o s t l yo na c t e db a s i c emotions: anger, disgust, fear, joy, sadness, surprise. In the area of affective computing, recent studies are also limited with respect to the number of modalities or the spontaneity of the emotion. Cameras are used by Kapur et al. to capture markers placed on various points of the whole body in order to recognize four acted basic emotions (sadness, joy, anger, fear). 9 Some studies deal with more complex emotions. In the "Lost Luggage" experiment, passengers at an airport were informed that their luggage has been lost, and the participants were asked to rate their emotional state. [START_REF] Scherer | Analyzing emotion blends[END_REF] Scherer and his colleagues show in this experiment that some events may give rise to several simultaneous emotions. These emotions are referred to as complex emotions and also as blends of emotions. [START_REF] Ekman | Unmasking the Face. A Guide to Recognizing Emotions from Facial Clues[END_REF][START_REF] Scherer | Analyzing emotion blends[END_REF][START_REF] Devillers | Emotion detection in real-life spoken dialogs recorded in call center[END_REF] They may occur either as a quick succession of different emotions, the superposition of emotions, the masking of one emotion by another one, the suppression of one emotion or the overacting of one emotion.

In particular, in the visual modalities, these blends produce "multiple simultaneous facial expressions." [START_REF] Richmond | Non Verbal Behavior in Interpersonal Relations[END_REF] Depending on the type of blending, the resulting facial expressions are not identical. A masked emotion may leak over the displayed emotion, 1 while superposition of two emotions will be shown by different facial features (one emotion being shown on the upper face while another one on the lower face). [START_REF] Ekman | Unmasking the Face. A Guide to Recognizing Emotions from Facial Clues[END_REF] Perceptual studies have shown that people are able to recognize facial expression of felt emotion [START_REF] Ekman | Felt, false, miserable smiles[END_REF][START_REF] Wiggers | Jugments of facial expressions of emotion predicted from facial behavior[END_REF] as well as fake emotion. [START_REF] Ekman | Felt, false, miserable smiles[END_REF] Similar studies producing similar results have been conducted on ECAs. [START_REF] Pandzic | MPEG-4 Facial Animation. The Standard, Implementation and Applications[END_REF] In a study on a deceiving agent, Rhem and André found that the users were able to differentiate when the agent was displaying expression of felt emotion or expression of fake emotion. [START_REF] Rehm | Catch me if you can -Exploring lying agents in social settings[END_REF] Aiming at understanding if facial features or regions play identical roles in emotion recognition, Bassili 17 and later on Gouta and Miyamoto, [START_REF] Gouta | Emotion recognition, facial components associated with various emotions[END_REF] and Constantini et al. [START_REF] Constantini | Recognizing emotions in human and synthetic faces: The role of the upper and lower parts of the face[END_REF] performed various perceptual tasks, and Cacioppo et al. [START_REF] Cacioppo | Electromyographic activity over facial muscle regions can differentiate the valence and intensity of affective reactions[END_REF] studied psychological facial activity. They found that positive emotions are mainly perceived from the expression of the lower face (e.g. smile) while negative emotion from the upper face (e.g. frown).

Very few models of facial expressions for such complex emotions have been developed so far for ECAs. The interpolation between facial parameters of given expressions is commonly used to compute the new expression. MPEG-4 proposes to create a new expression as a weighted interpolation of any of the six predefined expressions of emotions. [START_REF] Pandzic | MPEG-4 Facial Animation. The Standard, Implementation and Applications[END_REF][START_REF] Ostermann | Animation of synthetic faces in MPEG-4[END_REF] More complex interpolation schemes have been proposed. [START_REF] Albrecht | Mixed feelings: Expression of non-basic emotions in a muscle-based talking head[END_REF][START_REF] Tsapatsoulis | Emotion recognition and synthesis based on MPEG-4 FAPs[END_REF][START_REF] Ruttkay | Emotion disc and emotion squares: Tools to explore the facial expression face[END_REF] Duy Bui 25 introduced a set of fuzzy rules to determine the blended expressions of the six basic emotions. In this approach, a set of fuzzy rules is attributed to each pair of emotions. The intensities of muscles contraction for the blended expression are related to emotions intensities using fuzzy inference. With respect to other modalities than facial expressions, static postures were recorded by De Silva et al. using a motion capture system during acted emotions (two nuances for each of four basic emotions). [START_REF] De Silva | Towards unsupervised detection of affective body posture nuances[END_REF] Gunes et al. fused the video processing of facial expression and upper body gestures in order to recognize six acted emotional behaviors (anxiety, anger, disgust, fear, happiness, uncertainty). [START_REF] Gunes | Fusing face and body display for bi-modal emotion recognition: Single frame analysis and multi-frame post integration[END_REF] A vision-based system that infers acted mental states (agreeing, concentrating, disagreeing, interested, thinking, and unsure) from head movement and facial expressions was described by el Kaliouby et al. [START_REF] El Kaliouby | Generalization of a vision-based computational model of mind-reading[END_REF] Choi et al. described how video processing of both facial expressions and gaze are mapped onto combinations of seven emotions. [START_REF] Choi | An affective user interface based on facial expression recognition and eye-gaze tracking[END_REF] Yet, real-life multimodal corpora are indeed very few despite the general agreement that it is necessary to collect audio-visual databases that highlight naturalistic expressions of emotions as suggested by Douglas-Cowie et al. [START_REF] Douglas-Cowie | Emotional speech: Towards a new generation of databases[END_REF] Regarding the design of ECAs, the majority of the works in this research area use either motion capture data, [START_REF] Cao | Real-time speech motion synthesis from recorded motions[END_REF][START_REF] Egges | Imparting individuality to virtual humans[END_REF] or videos. [START_REF] Tsapatsoulis | Emotion recognition and synthesis based on MPEG-4 FAPs[END_REF][START_REF] Pandzic | Facial Motion Cloning[END_REF] Some studies do not use any corpus but propose sophisticated models of mixed emotional expressions. For example, an algorithm for generating facial expressions for a continuum of pure and mixed emotions of varying intensity is described by Albrecht et al. [START_REF] Albrecht | Mixed feelings: Expression of non-basic emotions in a muscle-based talking head[END_REF] Results from the literature in psychology are useful for the specification of ECAs, but provide few details, nor do they study variations about the contextual factors of multimodal emotional behavior. Very few researchers have been using context specific multimodal corpora for the specification of an ECA. [START_REF] Kipp | Gesture Generation by Imitation. From Human Behavior to Computer Character Animation[END_REF] Cassell et al. [START_REF] Cassell | Coordination and context-dependence in the generation of embodied conversation[END_REF] described how the multimodal behaviors of subjects describing a house were annotated and used for informing the generation grammar of the REA agent.

Complex Emotions: Two Illustrative Examples

In this section, we briefly describe two illustrative examples of multimodal behaviors observed during complex emotions in videos of TV interviews from the EmoTV corpus. [START_REF] Abrilian | EmoTV1: Annotation of reallife emotions for the specification of multimodal affective interfaces[END_REF] In video #3, a woman is reacting to a recent trial in which her father was kept in jail. As revealed by the manual annotation of this video by three coders, her behavior is perceived as a complex combination of despair, anger, sadness and disappointment. Furthermore, this emotional behavior is perceived in speech and in several visual modalities (head, eyes, torso, shoulders and gestures). In another video (video #41), a woman is pretending to be positive after negative election results. Such a video has been annotated as a combination of negative labels (disappointment, sadness, anger) and positive labels (pleased, serenity). The annotation of multimodal behaviors reveals that her lips show a smile but with lips pressed. This example illustrates the combinations of facial features during complex emotions.

Several levels of annotation are coded in EmoTV using the Anvil tool [START_REF] Kipp | Anvil -A generic annotation tool for multimodal dialogue[END_REF] :s o m e information regards the whole video (called the "global level"); while some other information is related to emotional segments (the "local" level); at the lowest level, there is detailed time-based annotation of multimodal behaviors including movement expressivity. Several emotional segments are identified by the annotators as being perceptually consistent. The annotation scheme enables the coders to select two verbal labels describing the emotion for a single emotional segment. Three annotators created this segmentation and labeled each segment with one or two labels. [START_REF] Abrilian | EmoTV1: Annotation of reallife emotions for the specification of multimodal affective interfaces[END_REF] The three annotations are combined into a single soft vector. [START_REF] Douglas-Cowie | Multimodal databases of everyday emotion: Facing up to complexity[END_REF][START_REF] Devillers | Representing real life emotions in audiovisual data with non basic emotional patterns and context features[END_REF] In video #3, three emotional segments have been identified by the coders and annotated with the following vectors: segment 1 (100% anger), segment 2 (67% anger, 11% despair, 11% disappointment, 11% sadness), segment 3 (56% despair, 33% anger, 11% sadness). A perceptive test on this video with 40 coders validated these annotations. [START_REF] Abrilian | Annotation of emotions in real-life video interviews: Variability between coders[END_REF]

Representing, Modeling and Evaluating Expressivity

Representing expressivity

Several taxonomies of communicative gestures have been proposed highlighting the link between gesture signals and its meaning. [START_REF] Mcneill | Hand and Mind -What Gestures Reveal about Thoughts[END_REF][START_REF] Kendon | Gesture: Visible Action as Utterance[END_REF][START_REF] Poggi | Mind markers, in Gestures. Meaning and Use[END_REF] Thet ypeofthegesture,itsposition in the utterance, its shape but also its manner of execution provide information about the speaker's mental and emotional state. Facial expressions are recognized for their power of expressing emotional state. Many studies have characterized facial expressions for emotion categories 1 and for appraisal dimensions. [START_REF] Kaiser | Facial expressions as indicators of appraisal processes[END_REF] While there is a less direct link between gesture shapes and emotions, several studies have shown that gesture manners are good indicators of emotional state. [START_REF] Wallbott | Bodily expression of emotion[END_REF][START_REF] Wallbott | Cues and channels in emotion recognition[END_REF][START_REF] Gallaher | Individual differences in nonverbal behavior: Dimensions of style[END_REF] Gesture manners are also linked to personality traits (nervousness), physiological characteristics (graciousness), physical state (tiredness), etc. Most of computational models of ECA behavior have dealt with gesture selection and gesture synchronization with speech. [START_REF] Kopp | Synthesizing multimodal utterances for conversational agents[END_REF][START_REF] Kopp | Towards integrated microplanning of language and iconic gesture for multimodal output[END_REF][START_REF] Hartmann | Formational parameters and adaptive prototype instantiation for MPEG-4 compliant gesture synthesis[END_REF] We propose a model of gesture manner, called gesture expressivity, that acts on the production of communicative gestures. Our model of expressivity is based on studies of nonverbal behavior. [START_REF] Wallbott | Bodily expression of emotion[END_REF][START_REF] Wallbott | Cues and channels in emotion recognition[END_REF][START_REF] Gallaher | Individual differences in nonverbal behavior: Dimensions of style[END_REF] We describe expressivity as a set of six dimensions. [START_REF] Hartmann | Implementing expressive gesture synthesis for embodied conversational agents[END_REF] Each dimension acts on a characteristic of communicative gestures. Spatial Extent describes how large the gesture is in space. Temporal Extent describes how fast the gesture is executed. Power describes how strong the performance of the gesture is. Fluidity describes how two consecutive gestures are co-articulated one merging with the other. Repetition describes how often a gesture is repeated. Overall activity describes how many behavior activities there are over a time span. This model has been implemented in the Greta ECA. [START_REF] Pelachaud | Multimodal expressive embodied conversational agent[END_REF]

Evaluation of the gesture expressivity model

We have conducted two studies to evaluate our gesture expressivity model which is the central part of the copy-synthesis approach described in Sec. 6. These two studies involved a total number of 106 users (80 males, 26 females; aged 17 to 25).

All were first and second year French university students. Each user completed only one of the two tests. Both tests consisted in observing sets of video clips (two per trial for the first test, four for the second test) and answering a questionnaire. The video clips differ only on the gesture expressivity of the agent (same audio and same gesture type).

The goal of the first study was to test the following hypothesis: the chosen implementation for mapping single dimensions of expressivity onto animation parameters is appropriate -a change in a single dimension can be recognized and correctly attributed by users. In this test, users (N = 52) were asked to identify a single dimension in forced-choice comparisons between pairs of animations. Table 1 presents the distribution of users' answers for each parameter. Gray cells indicate when they met our expectations: this diagonal totals 320 answers, which corresponds to 43.1% of accurate identifications of parameters. The chi-square test shows that this distribution cannot be attributed to chance [χ 2 (35) = 844.16,p<0.001].

Recognition was best for the dimensions Spatial Extent and Temporal Extent. Modifications of Fluidity and Power were judged incorrectly more often, but the correct classification still had the highest number of responses. The parameter Repetition was frequently interpreted as Power. Overall Activation was not well recognized.

Overall, we take the results of the first test as indication that the mapping from dimensions of expressivity to gesture animation parameters is appropriate for the Spatial Extent and Temporal Extent dimensions while it needs refinement for the other parameters.

The hypothesis tested in the second study was the following: combining parameters in such a way that they reflect a given communicative intent will result in a more believable overall impression of the agent. Avoiding behavior qualities that imply an emotional state or a personality trait, we considered the three following qualities: abrupt, sluggish, and vigorous. Abrupt is characterized by rapid, discontinuous and powerful movements. Sluggish is characterized by slow, effortless and close to the body but fluid movements. Vigorous is characterized by a lot of large, fast, fluid and repetitive movements. For each quality, we generated four animations. One animation corresponds to the neutral, generic animation, two to variants of the chosen expressive intent (strongly and slightly expressive) and one to an opposite assignment of expressivity parameters. This test (N = 54) was conducted as a preference ranking task: the user had to order four animations from the most appropriate to the least appropriate with respect to the expressive intent. For the abrupt and vigorous qualities, users preferred the coherent performances as we had hoped [F (3/153) = 31.23,p<0.001 and F (3/153) = 104.86,p<0.001, respectively]. The relation between our parameterization and users' perception can also be expressed as a linear correlation, which amounts to +0.655 for the abrupt quality and +0.684 for the vigorous quality. Conversely for the sluggish quality, the effect of input stimuli was not significant [F (3/153) = 0.71, N.S.]: the overall rating of stimuli was random and the linear correlation was almost null (+0.047). This may be attributable partly to the inadequacy between the specific gestures that accompanied the text and the way a sluggish person would behave. This finding raises the need for integrating gesture selection and gesture modification to best express an intended meaning.

In the first test, we checked if subjects perceived variation of each parameter, while in the second perceptual test we looked at the interpretation of these variations. Since our expressivity parameters show some dependency with one another, we wanted to check that the subject perceived their individual changes and their combined meaning in two separate perceptual tests. The results confirm that our general approach for expressivity modeling is worthwhile pursuing. A notable advantage of our implementation is to enable the decomposition of gesture expressivity and the test of parameters one by one. In the experiment by Wallbott, actors were instructed to act basic emotions. [START_REF] Wallbott | Bodily expression of emotion[END_REF] This experiment revealed that each acted emotion had an impact on all the parameters of expressivity. The first perceptual test we conducted would have been surely more difficult to control with a human actor instead of an agent: humans may be able to control their expressivity to a certain extent but can hardly isolate each parameter. In our animations, the decomposition of expressivity may have produced artificial behaviors but this step seemed necessary to evaluate our model and highlight possible ways of improvement. These results will be used to refine the technical implementation of individual parameters to achieve higher quality animation and better visibility of changes to the parameters. For the second perceptual test, we were careful to avoid introducing labels related to personality or emotion. While we ultimately want to simulate such traits and mental states, the link from these high-level concepts to the expressive dimensions is still not clear -the social psychology literature on this problem appears to be very sparse. This second test mainly showed that we need to integrate gesture selection and gesture modification when generating an animation. A shortcoming of the current test was that only a single utterance with a unique gesture selection was used with varying animations. A wider variety of different utterances and corresponding gesture selections is needed to understand the perception of expressivity.

Representing and Modeling Blended Facial Expressions

In this section, we present a computational model of facial expressions arising from blends of emotions. Instead of formulating our model at the level of facial muscle contractions or FAP values, we propose a face partition based model, which not only computes the complex facial expressions of emotions but also distinguishes between different types of blending. Blends (e.g. superposition and masking) are distinguished among each other as they are usually expressed by different facial areas. [START_REF] Ekman | Unmasking the Face. A Guide to Recognizing Emotions from Facial Clues[END_REF][START_REF] Ekman | The Face Revealed[END_REF] Expressions may also occur in rapid sequences one after the other. Moreover, the expression of masking a felt emotion by a fake one (i.e. not felt) is different from the expression corresponding to the superposition of two felt emotions. [START_REF] Ekman | Unmasking the Face. A Guide to Recognizing Emotions from Facial Clues[END_REF] Thus complex facial expressions can be distinguished depending on the type of emotions, their apparition in time (sequence, superposition) as well as if the emotions are felt or fake. For the moment, we have considered only two cases of complex facial expressions: the superposition of two felt emotions and the masking of a felt emotion with a fake one. In the following sub-section, we present a general framework for our model and describe next details of computational procedures based on fuzzy inference.

Blend of emotions

The analysis of the video corpus has revealed the evidence of disparity between different types of complex expressions. [START_REF] Douglas-Cowie | Multimodal databases of everyday emotion: Facing up to complexity[END_REF] Different situations such as "superposed," "masked" or "sequential" were recognized by annotators. In our model, we have defined for each type of blend a set of fuzzy rules SFR. In Ekman's research on blend of emotions, his analysis is restricted to a small number of so-called basic emotions: anger, disgust, fear, joy, sadness and surprise. Our model is based on the set of rules he has established for the blending of these six emotions. However, there exist many more expressions of emotions, 23 some of which are considered to have a universal aspect as well. [START_REF] Keltner | Signs of appeasement: Evidence for the distinct displays of embarrassment, amusement, and shame[END_REF][START_REF] Matsumoto | More evidence for the universality of a contempt expression[END_REF] Emotions like disappointment, despair or pride appear in the annotation of our video corpus. To overcome this restriction, we introduced the notion of similarity between expressions. We compute similarity between expressions of any given emotion and basic emotion using fuzzy similarity. [START_REF] Bouchon-Meunier | Towards general measures of comparison of objects[END_REF] Let Exp(E i )b e the expression of an emotion E i and Exp(N ) be the neutral expression. Let us suppose that any facial expression is divided into n areas F k ,k=1 ,...,n.E a c h F k represents a unique facial part like brows or eyes. For any emotion E i ,E x p ( E i ) is composed by n different facial areas. Thus, Exp(E i )={F (Ei) k ,k=1,...,n}.I n our model we are currently considering seven areas, namely brows, upper eyelids, lower eyelids, cheeks, nose, upper lip and lower lip.

Let E i and E j be the emotions occurring in a blend and Exp blend (E i ,E j ) the resulting complex expression, where blend is either masking (M )o rs u p e r p osition (S). The Exp blend (E i ,E j ) is also composed by the combination of n different face areas, where each

F (Ei,Ej) k
is equal to one corresponding area from Exp(E i ), Exp(E j ), Exp(N ). We note, that for any k in the interval [1, n], F (Ei,Ej) k cannot contain simultaneously elements of two different expressions; it can be either Exp(E i ), Exp(E j ), or Exp(N ). That is, a facial area can not show different expressions at the same time; it can show one expression at a time: this expression can come from either emotion or the neutral expression. Combining facial expressions on the same facial area can have the artefact to introduce a new expression. For example, if we add the facial actions in the eyebrow region of surprise "raise-eyebrow" and of anger "frown" we obtain a new facial action "upper-raised-eyebrow-down" that is typically linked to fear. Thus, we opt for the rules that no facial action can be added up on a same facial region. This ensures the conformity of our model with empirical evidence. [START_REF] Ekman | Unmasking the Face. A Guide to Recognizing Emotions from Facial Clues[END_REF] Let E u be one of the basic emotions and let E i be an input emotion. We aim to compute which basic emotion is the most similar E i expression-wise. Thus, the fuzzy similarity between E i and E u needs to be established. Each emotion E u is associated to a set of fuzzy intervals in which all plausible expressions for this emotion are defined. That is, for each numerical parameter of an expression of E u there is a fuzzy interval that specifies a range of plausible values. The value of fuzzy similarity for each significant parameter of Exp(E i )a n dE x p ( E u ) is then established. Finally, all values are combined linearly. At the moment the M-measure of resemblance on FAP values of each expression is used to establish similarity values. [START_REF] Bouchon-Meunier | Towards general measures of comparison of objects[END_REF][START_REF] Dubois | Fuzzy Sets and Systems[END_REF] Our algorithm works as follows: for each input expression Exp(E i )wefirstdefine its similarity with the six basic expressions Exp(E u ),u=1,...,6. The best value, that is, the highest value of similarity, defines the basic emotion whose expression is the most similar to the input one. According to the degree of similarity, the final expression Exp blend (E i ,E j )is chosen based on rules of the adequate SFR set. Each type of the blend {S, M } uses different set of fuzzy rules (SFR S in case of superposition or SFR fake and SFR felt: in case of masking; see also Secs. 5.2 and 5.3). These rules describe the principles of composition of facial expressions depending on the blending type. The final expression Exp blend (E i ,E j ) is obtained by combining face areas of Exp(E i ), Exp(E j ) and/or Exp(N ).

Masking

Masking occurs when a felt emotion should not be displayed for some reason; it is preferred to display a different emotional expression. It may be due to some sociocultural norms, often called display rules. [START_REF] Ekman | The repertoire of nonverbal behavior's: Categories, origins, usage and coding[END_REF] Masking can be seen as an asymmetric emotion-communicative function in the sense that given two emotions E i and E j , the masking of E i by E j leads to a different facial expression than the masking of E j by E i . [START_REF] Ekman | Unmasking the Face. A Guide to Recognizing Emotions from Facial Clues[END_REF] Often humans are not able to control all their facial muscles. Ekman claims that the features of the upper face of any expression are usually more difficult to control. [START_REF] Ekman | Unmasking the Face. A Guide to Recognizing Emotions from Facial Clues[END_REF] Moreover, felt emotions may be characterized by specific facial features: e.g. sadness brows 1 or orbicularis oculi activity in case of joy. [START_REF] Ekman | Darwin, deception, and facial expression[END_REF] Such reliable features lack in fake emotions as they are difficult to do voluntarily. [START_REF] Ekman | Darwin, deception, and facial expression[END_REF] Ekman describes, for any of the so-called basic emotions, which features are missing in fake expressions, in particular in the case of masking. On the other hand, people are not able to inhibit felt emotions completely. Based on Darwin's work, Ekman proposed the inhibition hypothesis: elements of facial expressions that are hardly done voluntarily, are also hardly inhibited. [START_REF] Ekman | Darwin, deception, and facial expression[END_REF] Finally, Ekman provides a description of which part of the felt expression leaks during masking. [START_REF] Ekman | Unmasking the Face. A Guide to Recognizing Emotions from Facial Clues[END_REF] We call Exp M (E i ,E j ) the expression resulting from the masking of a felt emotion E i by a fake emotion E j . Two independent sets of fuzzy rules, SFR fake and SFR felt , are defined in the case of masking. The first one -SFR fake -describes the features of the fake expression, while SFR felt -of the felt expression. All rules are of the certainty type. [START_REF] Hüllermeier | Fuzzy rules in case-based reasoning[END_REF] The value of fulfilment of a rule is a degree of similarity between E i and E u . Each input variable corresponds to one basic emotion E u ,u=1,...,6, and each output variable corresponds to one facial region F k of the resulting expression.

In particular, each rule of SFR felt describes leakage of the felt emotion E u during the masking. Each rule is defined as: the more the input expression of E i is similar to the expression of E u , the more certain the face areas corresponding to the reliable features of E u should be used in the final expression.

For example, in the case of the rule for the felt sadness the following information is applied: "t h em o r et h einput expression is (similar to) sadness, the more certain the input brows and upper eyelids should be visible." It is described in SFR felt by the following rule: where X expresses degree of similarity to Exp(SADNESS)a n dF k are face areas of the input expression E j . According to the inhibition hypothesis, if there is a face area in the masking expression that is not used by the felt emotion, it does not mean that it has to be used by the fake emotion. Each rule of SFR fake describes the reliable features which will certainly not appear in the fake expression of E i . For example, in the case of the fake joy the following rule is applied: "t h em o r et h e input expression is (similar to) joy, the more certain the area of lower eyelids should not be visible." It corresponds to the following rule of SFR fake :

If Xi sS A D N E S
If X is JOY then F brows is VISIBLE and F upper eyelids is VISIBLE and F lower eyelids is NOT VISIBLE and ... and F upper lip is VISIBLE and F lower lip is VISIBLE.

The system takes as input two emotion labels: the felt E i and fake E j .

If the expressions of both emotions are not one of the basic ones (that is if Exp(E i ) and/or Exp(E j ) is different from Exp(E u ),u=1 ,...,6, the model predicts the final expression based on the degree of similarity between Exp(E i ) and/or Exp(E j ) and basic expressions. The fake and felt areas of the masking expression are considered separately. Finally, for each F k ,the results of SFR felt and of SFR fake are composed to obtain Exp M (E i ,E j ) expression. The conflicts that may rise on some facial areas are resolved according to the inhibition hypothesis. In the case in which neither the felt nor the fake emotion can be shown in a given region of the face, the neutral expression is used instead. The final expression is composed of facial regions of the felt emotion, the fake and the neutral ones.

Figure 1 shows the agent displaying the masked expression of disappointment (computed as similar to sadness) and fake joy. The images (a) and (b) display the expressions of disappointment and joy, respectively. Image (d) shows the masking expression. We can notice that the absence of orbicularis oculi activity as indicator of unfelt joy [START_REF] Ekman | Darwin, deception, and facial expression[END_REF] . is visible on both images (c) and (d), the annotated video and the corresponding Greta simulation.

Superposition

Superposition occurs when two different emotions are felt and shown simultaneously. Contrary to the masking case, it does not have the property of asymmetry.

The expression Exp S (E i ,E j )resulting from the superposition of E i and E j is equal to the superposition of E j and E i .T h a ti s :E x p S (E i ,E j )=Exp S (E j ,E i ). Ekman described this case of blending for all pairs of the six basic emotions. [START_REF] Ekman | Unmasking the Face. A Guide to Recognizing Emotions from Facial Clues[END_REF] No constructive rules to build the superposition were introduced and only the resulting expressions are described. The superposition of two emotions is usually expressed by combining the upper part of one expression with the lower part of the other one. However, not all combinations of the upper and the lower faces are plausible.

As mentioned in Sec. 2, negative emotions are mainly recognized by their upper face (e.g. frown of anger) while positive emotion by their lower face (e.g. smile of happiness) [START_REF] Bassili | Emotion recognition: The role of facial movement and the relative importance of upper and lower areas of the face[END_REF][START_REF] Gouta | Emotion recognition, facial components associated with various emotions[END_REF][START_REF] Constantini | Recognizing emotions in human and synthetic faces: The role of the upper and lower parts of the face[END_REF] Let Z be a set of plausible (according to Ekman) schemas for the superposition expression Exp S . By "schema" we intend the particular division of n face regions F k ,k=1,...,n between any two emotions. At the moment, ten different schemas are considered. The fuzzy inference is used to model the combination of facial expressions Exp(E i )a n dE x p ( E j )o ft w oe m o t i o n sE i and E j . Each fuzzy rule associates a pair of basic emotions to an element of Z. Each rule is defined as: the more the input expression of E i is (similar to) the expression of E u and the more the input expression of E j is (similar to) the expression of E w ,t h em o r e certain the upper/lower face areas of E i and lower/upper face areas of E j should be used.

For example, the superposition of an emotion similar to sadness (X) and of an emotion similar to joy (Y ) is described in SFR S by the following rule: belong to Y . The meaning of this rule is: t h em o r eo n eo ft h einput expressions is (similar to) sadness and the other input expression is (similar to) joy, the more certain is that the final expression contains brows, and upper eyelids of the first expression and the mouth area rest of the second.

If X is SADNESS and Y is JOY then S 1 is
The inputs to our system consist of two emotion labels E i and E j . The model predicts the final expression based on the degrees of similarity between Exp(E i ) (resp.E x p ( E j )) and Exp(E u ),u=1,...,6. The values of fuzzy similarity between adequate pairs of expressions serve to classify an input pair according to plausible schemas for superposition Z. The inhibition hypothesis is not applied in the superposition case. As consequences the neutral expression is not used in the computation of the final expression. Figure 2 shows an example of superposition expression computed by our model. Images (a) and (b) show, respectively, the expressions of joy and of sadness. Image (d) shows the superposition of both expressions as a composition of face areas of both input expressions. In that image, the upper face expresses sadness, and the lower face joy. However, the expression of joy is expressed by F lowereyelids , which contains orbicularis oculi muscle contraction, sign of felt joy. We can note that this muscular contraction was not shown in the Masking condition (Fig. 1). Image (c) shows a video frame annotated with superposition of joy and sadness. Image (d) shows the corresponding Greta simulation.

Copy-Synthesis Approach

Our copy-synthesis approach (Fig. 3) is composed of three main steps, namely, annotation of the data, extraction of parameters, and generation of the synthetic agent.

Annotation

Annotation is composed of two steps.

Step 1 aims at the automatic annotation of the video with data that can be useful either for the manual annotation of the video or the specification of the agent's behavior: pitch, intensity, etc.

Step 2 involves manual annotations of the video. The word-by-word transcription including punctuation is achieved following the LDC norms for hesitations, breath, etc. The video is then annotated at several temporal levels (whole video, segments of the video, behaviors observed at specific moments) and at several levels of abstraction. The global behavior observed during the whole video is annotated with communicative act, emotions and multimodal cues. The segments are annotated with emotion labels and the

5) Generation Face and Gaze

Associations between emotion labels, facial expressions and gaze

A N N O T A T I O N E X T R A C T I O N G E N E R A T I O N 1

5) Generation Face and Gaze

Associations between emotion labels, facial expressions and gaze

A N N O T A T I O N E X T R A C T I O N G E N E R A T I O N Fig. 3.
Copy synthesis approach for studying gesture expressivity during emotions.

modalities perceived as relevant with regards to emotion. We have grounded this coding scheme in requirements collected from the parameters known as perceptually relevant for the study of emotional behavior, and the features of our emotionally rich TV interviews. This section describes how each modality is annotated in order to enable subsequent computation of the relevant parameters of emotional behavior.

Each track is annotated one after the other while playing the audiovisual clip (e.g. the annotator starts by annotating the first track for the whole video and then proceeds to the next track). Movement expressivity is annotated for torso, head, shoulders, and hand gestures. The annotators were instructed to use their own perception for annotating these expressive dimensions. The head pose track contains pose attributes adapted from the FACS coding scheme. [START_REF] Ekman | Manual for the Facial Action Coding System[END_REF] Facial expressions are coded using combinations of Action Units.

As for gesture annotation, we have kept some of the attributes used in research on gestures. Thus, our coding scheme enables the annotation of the structural description ("phases") of gestures as their temporal patterns might be related to emotion [START_REF] Kipp | Gesture Generation by Imitation. From Human Behavior to Computer Character Animation[END_REF][START_REF] Mcneill | Hand and Mind -What Gestures Reveal about Thoughts[END_REF] : preparation (bringing arm and hand into stroke position), stroke (the most energetic part of the gesture), sequence of strokes (a number of successive strokes), hold (a phase of stillness just before or just after the stroke), and retract (movement back to rest position). We have selected the following set of gesture functions ("phrases") as they were revealed to be observed in our corpus: manipulator (contact with body or object), beat (synchronized with the emphasis of the speech), deictic (arm or hand is used to point at an existing or imaginary object), illustrator (represents attributes, actions, relationships about objects and characters), emblem (movement with a precise, culturally defined meaning). [START_REF] Kipp | Gesture Generation by Imitation. From Human Behavior to Computer Character Animation[END_REF][START_REF] Mcneill | Hand and Mind -What Gestures Reveal about Thoughts[END_REF] Currently, the hand shape is not annotated since it is not considered as a main feature of emotional behavior in our survey of experimental studies nor in our videos.

Whereas the annotations of emotions have been done by three coders and lead to computation of agreement, 39 the current protocol used for the validation of the annotations of multimodal behaviors is to have a second coder checks the annotations done by a first coder followed by brainstorming discussions. We are currently considering the validation of the annotations by the automatic computation of intercoder agreements from the annotations by several coders.

Extraction from annotations

A module has been designed for extracting from the various annotations the pieces of information which have been identified as required for generation (Step 3 in Fig. 3):

the speech transcription, the communicative act, the emotion labels, the dimensions of emotions, the multimodal behaviors (including the number of occurrences and the duration of each multimodal behavior within each segment). The data extracted are used to compute a model of multimodal expressive behavior along three dimensions: emotion, activation of head/torso/hand, and gesture expressivity. Table 2 illustrates such results. The percentages indicated in Table 2 are percentages of time and are computed by considering the duration of a given annotation (e.g. Anger) over the whole duration of annotated segments. As explained below, the role of these descriptive profiles is to drive the specifications of the emotional behavior to be replayed by the ECA.

Generation

Our ECA system, Greta, incorporates communicative conversational and emotional qualities. [START_REF] Pelachaud | Multimodal expressive embodied conversational agent[END_REF] The agent's behavior is synchronized with her speech and is consistent with the meaning of her sentences. To determine speech-accompanying non-verbal behaviors, the system relies on a taxonomy of communicative functions proposed by Isabella Poggi. [START_REF] Poggi | Mind markers, in Gestures. Meaning and Use[END_REF] A communicative function is defined as a pair (meaning, signal)

where meaning corresponds to the communicative value the agent wants to communicate and signal to the behavior used to convey this meaning. We have developed a language to describe gesture signals in a symbolic form. [START_REF] Hartmann | Formational parameters and adaptive prototype instantiation for MPEG-4 compliant gesture synthesis[END_REF] An arm gesture is described by its wrist position, palm orientation, finger direction as well as hand shape. We use the HamNoSys system to encode hand shapes. [START_REF] Prillwitz | Hamburg notation system for sign languages: An introductory guide[END_REF] To control the agent's behavior, we are using the APML representation language, where the tags of this language are the communicative functions. [START_REF] De Carolis | APML, a markup language for believable behavior generation[END_REF] The system takes as input a text tagged with APML labels as well as values for the expressivity dimensions that characterize the manner of execution of the agent's behaviors. The system parses the input text and selects which behaviors to perform. Facial expressions and gaze behaviors are synchronized with speech defined within APML tags. The system looks for the emphasis word. It aligns the stroke of a gesture with this word. Then it computes when the preparation phase of the gesture is as well as if a gesture is hold, if it co-articulates to the next one, or if it returns to the rest position. The expressivity model controls the spatial and dynamism properties of the gestures. The outputs of the system are animation and audio files that drive the animation of the agent.

Generation of the APML file

Step 4 consists of generating the APML file used by the Greta system from the data extracted from the annotations such as the speech transcription, the pitch, the communicative act, and the emotion labels. The transcription is directly used in the APML file since it corresponds to the text that the Greta agent has to produce. It is enhanced with several tags. The pitch enables to validate/correct the annotation of prosodic curves adapted from the ToBI model and used by APML.

We have also defined a table connecting the annotated communicative act with the closest performative the Greta system knows about. Thus the communicative goal "to complain" used for annotating the video #3 is translated to the performative "to criticize" which corresponds to a specification of the global behavior of the agent (gaze at listener + frown + mouth criticize). In the videos we studied, the emotional behaviors are complex and are often annotated with several emotional labels. These annotations made by three or more annotators are grouped into an emotional vector.

The third segment of video #3 has been annotated with the following vector: 56% of despair, 33% of anger and 11% of sadness. The two most represented categories are grouped into a label "superposition(Despair, Anger)" that is sent to the blend computation module (see Sec. 5). The value of the affect attribute of the rheme tag is specified as this combination of the two major emotion labels computed from the emotional profiles resulting from the annotations (Table 2).

Generation of gaze behaviors

The annotations of facial expressions are used in Step 5 to associate the combined emotion label to the annotated gaze behaviors. The durations of the annotation of the gaze are used to specify in the agent the durations of gaze towards the right and left, and the maximum duration of gaze towards the camera. In the third segment of video #3, which has a total duration of 13 seconds, 41 annotations were done for the gaze: towards left (12% of the duration of the segment), towards right (45%).

In order to simplify the specification of the behavior to be replayed by the ECA, the gazes which were not directed towards left or right were grouped into a single class of gazes towards the camera for 43% of the segment's duration.

Generation of expressive parameters for the gestures

Step 6 aims at generating expressive animation. Five gestures were annotated for the third segment. Gesture quality was annotated as follows: fluidity (79% of the gesture annotations were perceived as being smooth, and 21% as being jerky), power (soft = 10%, hard = 21%, normal = 69%), speed (fast = 100%), spatial extent (contracted = 100%). These annotations are used to compute the values of the expressive parameters of the expressive agent. For example, in the Greta agent, the values of the fluidity (FLT) parameter have to be between -1 (jerky) and +1 (smooth). Thus, we computed the value of the FLT parameter for the third segment of video #3 (Table 2 provides the values of the expressivity parameters for the whole video) as follows: FLT = -1 × 0.21 + 1 × 0.79 = 0.58. This computation enables us to set the fluidity of the generated gestures to an average value which represents the perception of global distribution of smooth versus jerky gestures.

Conclusions and Future Directions

We have presented a model of multimodal complex emotions involving gesture expressivity and blended facial expressions. We have described a methodology based on the manual annotation of a video corpus to create expressive ECAs via an analytical approach; we have proposed a representation scheme and a computational model for such an agent. We explained how the multi-level annotation of TV interviews is compatible with the multi-level specifications of our ECA. Our approach is at an exploratory stage and does not currently include the computation of statistics over a large number of videos. Yet, it did enable us to identify the relevant levels of representation for studying the complex relation between emotions and multimodal behaviors in non-acted and non-basic emotions. Whereas the first part of the model focuses on gesture expressivity, the second part of the model addresses how such complex emotions can impact on the display of superposed or masked facial expressions. Currently, we do not use all the annotations provided by the EmoTV corpus.

The manual annotations of intensity are not considered yet: we only differentiate between major and minor labels. These annotations of intensity could be involved in the computation of the vector of emotion labels which is used for generating the emotional behavior of the ECA. The context annotations include other information related to "appraisal" dimensions such as the time of the event, the implication of the person, etc. which might be interesting to consider in the model of the agent.

Other levels might also be relevant (head movements) so as to generate different behaviors with different levels of fidelity.

In the near future, we aim to perform perceptual tests to evaluate our methodology as well as our model of blend of facial expressions. We believe that the results of the two perceptual tests that we have described in this paper will be used to improve the copy-synthesis approach and specify other perceptual tests evaluating if the contextual cues, the emotion and the multimodal behaviors are perceptually equivalent in the original video and in the simulation of the corresponding behaviors by the ECA, thus revealing how much such a technique is successful. These perceptual tests will also help finding out if differences of quality and of level of details between the real and the simulated multimodal behaviors have an impact on the perception of emotion. For example, we currently compute average values for expressivity parameters and we do not specify precisely which gestures are to be performed by the ECA and with which expressive characteristics. Another application of these tests that we foresee is the possibility to refine our ECA system. Indeed, having to reproduce complex real behaviors allows us to refine our behavioral engine; we will apply the methodology learning by imitation. The corpus will also enable us to compute other relations between (i) the multimodal annotations, and (ii) the annotation of emotions (labels, intensity and valence), and the global annotations such as the modalities in which activity was perceived as relevant to emotion. [START_REF] Devillers | Representing real life emotions in audiovisual data with non basic emotional patterns and context features[END_REF] We are considering the use of image processing approaches in order to validate the manual annotations. Finally, we intend to extend the part of our model on complex facial expressions to include the combination of the expressivity parameters of the blended emotions. This will enable us to deal with the masked behaviors observed in our corpus and apply the copy-synthesis approach that we have defined for gesture. Indeed, in the video #41, a lady masks her disappointment with a tense smile. This could be modeled by blending the smile of the faked happiness and the tenseness of the felt disappointment.

Complex emotions are common in everyday conversation. Display rules, lies, and social context often lead to the combination of emotions as those observed in our corpus. We believe that the methodology that we have described might be useful with other real-life situations than TV interviews.

Fig. 1 .

 1 Fig. 1. Disappointment masked by joy.

Fig. 2 .

 2 Fig. 2. Superposition of sadness and joy.

Table 1 .

 1 Distribution of users' answers as a function of the modified parameter.

					Perceived modification
		Spatial	Temporal				Overall	No	Do not
		extent	extent	Fluidity Power	Repetition	activation	modification	know	Total
	Modified parameter
	Spatial Extent	77	2	5	5	3	3	3	8	106
	Temporal Extent	3	104	7	13	7	1	1	5	141
	Fluidity	2	4	42	10	23	2	34	7	124
	Power	7	8	23	42	9	6	27	8	130
	Repetition	18	12	17	20	35	5	10	8	125
	Overall Activation	7	7	7	17	6	20	41	11	116
	Total	114	137	101	107	83	37	116	47	742

  Sthen F brows is VISIBLE and F upper eyelids is VISIBLE and ... and F upper lip is NOT VISIBLE and F lower lip is NOT VISIBLE,

  FALSE and S 2 is FALSE and S 3 is FALSE and S 4 is FALSE and S 5 is TRUE and S 6 is FALSE and S 7 is FALSE and S

8

is FALSE and S 9 is FALSE and S 10 is FALSE where S i are schemas from a set Z.I np a r t i c u l a rS 5 corresponds to the schema in which the face areas F brows and F uppereyelids belong to X while the other face areas

Table 2 .

 2 Illustrative multimodal emotional profiles extracted from the annotations of three videos (global profile of the whole videos).

		Videos	Video #3	Video #36	Video #30
		Duration	37 s	7 s	10 s
	EMOTION	Emotion labels	Anger (55%) Anger (62%) Exaltation (50%)
			Despair(45%) Disapoint. (25%)	Joy (25%)
				Sadness (13%)	Pride (25%)
		Intensity (1: min -5: max)	5	4.6	4
		Valence (1: neg -5: pos)	1	1.6	4
	GESTURE	% fast vs. % slow	47% vs. 3%	33% vs. 13%	83% vs. 0%
	EXPRESSIVITY % hard vs. % soft	17% vs. 17%	20% vs. 0%	0% vs. 27%
		% jerky vs. % smooth	19% vs. 8%	6% vs. 0%	5% vs. 50%
		% expanded vs. % contracted 0% vs. 38%	13% vs. 20%	0% vs. 33%

Acknowledgments

This work was partially supported by the Network of Excellence HUMAINE (Human-Machine Interaction Network on Emotion) IST-2002-2.3.1.6/Contract no. 507422 (http://emotion-research.net/). The authors are very grateful to Susanne Kaiser, Bjoern Hartmann, Maurizio Mancini, and Sarkis Abrilian for their suggestions and help.


Olivier Dalle
email: olivier.dalle@inria.fr

Emilio P Mancini
email: emilio.mancini@inria.fr

NetStep: a micro-stepped distributed network simulation framework

Keywords: I.6.8 [Ssimulation and Modeling]: Types of Simulationsparallel, C.2.1 [Computer-Communication Networks]: Network Architecture and Design, D.2.13 [Software Engineering]: Reusable Software Simgrid, Peer-to-peer computing time-step, overlap, lookahead, simulator

This paper presents NetStep, a prototype for the distributed simulation of very large scale network simulations, such as the simulation of peer-to-peer applications. We use simulation micro-steps as a means for optimizing the overlap of communications and computations, without changing the original event-driven model. As a consequence, NetStep allows for the reuse of unmodified existing sequential simulators for building large-scale distributed simulations: the overall simulation is divided both in time and space, into a large number of simulation micro-steps, each of which being executed by a legacy sequential simulator. By choosing the time-step smaller than the minimal look-ahead due to communications, we avoid the need for synchronization between Logical Processes during the simulation. Instead, the simulated communications become inputs and outputs of the simulation micro-steps, and are routed in parallel between LPs by a NetStep dedicated entity. Our prototype is based on the SimGrid sequential simulator.

INTRODUCTION

Analytical methods, especially the stochastic ones, are commonly used to study large distributed systems like peerto-peer systems [START_REF] Ge | Modeling peer-peer file sharing systems[END_REF][START_REF] Dalle | Analysis of failure correlation impact on peer-to-peer storage systems[END_REF]. Unfortunately, such techniques require to comply with a number of hypotheses (independence of events, steady-state, stationarity, etc.) that make them unsuitable for the study of many problems. Given that experimenting on real systems have an obvious hard limit in terms of scalability, the only option left for the study of such very large systems is simulation. However, unless the model of the system is over-simplified, a parallel approach seems unavoidable to cope with the resulting computation complexity of the simulation. This complexity can easily be explained by the two-dimensional nature of the simulation models: The longer the history of the model needs to be computed, the longer the computation needs to run, and the larger the model space (usually abstracted in terms of states), the more the computation needs memory.

If we except the special case for parallel replications, parallelization techniques follow this two-dimensional scheme in time and space [START_REF] Chandy | Space, time, and simulation[END_REF] and fall accordingly into the categories of time-parallel and space-parallel simulations. However, these categories have a strong impact on the simulation internals, that is, on the simulation algorithm used to compute the model trajectory in parallel.

In this paper, we present a hybrid solution, that combines both space-and time-parallel decompositions, but our aim is to propose a solution that can be implemented using an existing sequential simulator without any change to its implementation. In particular, we do not present an optimization of the time-or space-parallel simulation algorithms, as many examples can be found in literature [START_REF] Ayani | Parallel simulation using conservative time window[END_REF][START_REF] Park | A fast hybrid time-synchronous/event appraach to parallel discrete event simulation of queuing networks[END_REF][START_REF] Riley | Spaceâ ȂŞparallel network simulations using ghosts[END_REF][START_REF] Jain | Massively time-parallel, approximate simulation of loss queueing systems[END_REF][START_REF] Wu | Time-parallel trace-driven simulation of CSMA/CD[END_REF].

Indeed, the performance (or scalability) of a distributed simulation is highly dependent on the amount of time spent in the communications between Logical Processes (LPs) during the computation. Therefore, following a classical approach in high performance parallel computing, our solution tries to minimize the time lost in communications. Two obvious directions of investigation can be explored to minimize this loss of time, without trying to optimize the simulation algorithm or simplifying the model: Maximizing the overlap between computations and communications, or reducing the amount of inter-LPs communications. The work we present in this paper contributes mostly to the first direction, but it opens interesting perspectives in the second as well.

Introducing the solution

Our solution is based on a pragmatic approach, that does not apply to all the simulation scenarios, but only to some particular cases, and in particular to the simulation of large peer-to-peer systems, for which we can make the following hypotheses:

(H1) The systems we study are composed of a large number of sub-systems or entities (the peers), noted N ;

(H2) The simulation of these sub-systems can be split in space and assigned to a number of Logical Processes, noted P , running on C computing nodes;

(H3) The system has good locality property, such that over a short period of time, called a time-slot and noted h, each sub-system interacts only with a limited number of the other sub-systems; Or stated differently, it is possible to find a period of time sufficiently short, such that no sub-system has enough time over that period to reach more than a fraction of the other peers; we call model-span and note α(h) the maximum number subsystems that can be reached for a period of duration h;

(H4) Assuming that the sending of a message between any two peers takes some time, and that the only interactions that exist in the model between peers are the messages they exchange, we can find a minimal (nonzero) delay of interaction between any two peers, called the causal latency and defined as the smallest amount of time that must elapse between the sending of a message by a peer to another peer, and its notification on the receiver side. This causal latency is a concept similar to the directional distance introduced by Ayani and Rajaei [START_REF] Ayani | Parallel simulation using conservative time window[END_REF].

The solution we present in this paper consists in dividing the overall simulation both in time and space, into a large number of micro-simulation steps. In the space dimension, the division consists in forming a number of clusters of entities, that are each assigned to a given LP. Entities are groups of peers formed according to their locality properties (eg. connected to the same DSL equipement or access network). In time, each LP simulates in parallel with other LPs the behavior of the cluster of entities it is assigned for similar periods of time. The duration of this time period, called a time-step, is chosen such that no communication is needed between LPs until the completion of the time-step: It is chosen sufficiently small to ensure that no communication occuring in the simulation model between two peers not belonging to the same LP can be completed (fully simulated) during the same simulation step.

This can be achieved by chosing the duration of the microstep starting at the simulated time t on LPi, noted θ(t, i), such that:

∀t, ∀i θ(t, i) < Lmin.
where Lmin is minimal causal latency between two peers that are simulated within two different LPs.

Going further with this idea, we suggest that the duration of the time-step should even be chosen small enough to ensure that the communication inititiated during the timestep i should not complete before the time-step i + k, k > 1. This way, we enforce a strong overlap between the computation of the time-steps and the transmission of their resulting communications. For example, it is easy to show that by choosing θ(t, i) < 1 2 Lmin we can ensure that no communication initiated during time-step i will complete before the end of the time-step i + 1, which allows to overlap the communications generated by step i with the computations of step i + 1. Some level of synchronization is required among LPs, but with some flexibility: a given LP cannot be ahead of the others more than a few steps (ie. no more than the minimum causal latency). The main problem to be solved when reusing an existing sequential simulator in such a time-parallel approach, is the dependency between consecutive time-steps. In our case this dependency mostly consists in passing the workload status of each access network from one time-step to the next one, such that the initial workload of the network at the beginning of a time-step is well taken into account in the computation of the communication times.

Rationale and observations

The rationale for this solution is that in a non time-stepped parallel discrete-event simulation (PDES), the communications occuring between the LPs at the runtime level are directly related to those occuring in the model between peers: As shown on Figure 1, the simulation of a communication between two peers Pi and Pj may in turn require a communication between two LPs at the runtime level if Pi and Pj happen to be simulated by different LPs. Our hypotheses make sense with respect to the typical parameter values we are considering: our goal is to simulate several millions of peers (eg. N = 10 7 ) using a grid computing facility offering up to a few thousands of computing nodes (C > 10 3 ). The number of LP per core also defines the number of peer per LP, and can therefore be used as an adjustement variable to optimize the overall performance of the simulation (this is left as a perspective for further studies). For example, with P = C, we end up with an average of 10 4 peers per LP, but this number can be as low as a hundred peers per LP if we chose to have P = 100 × C (that is a hundred of LPs per computing node), which is not unreasonable to consider on a massively multi-core architecture.

The time-step duration h is in the order of a few tens of milliseconds: If we except the particular case of peers running on the same local network, the typical value of Lmin is the communication delay observed between any two peers connected to internet through a DSL connexion, which is in the order of a hundred milliseconds. Indeed, if we arrange for peers that are in very close range in the real system to be simulated by the same LP, then the only communications left between LPs are those corresponding to messages exchanged between peers that are not in close range, which leads to the corresponding value of h = 1

k Lmin if we want to achieve a strong overlap.

In hypothesis (H3), the model-span α(T ) may be bounded assuming that a communication occuring between any two peers in the system keeps both of them busy and unable to send or receive another message for a minimum amount of time, noted τ , and such that τ > 0. Hence, the maximum of peers that can be reached over the period of time h of a time-step is such that α(T ) ≤ h τ . This hypothesis makes sense with respect to the previous figures: in a real large-scale peer-to-peer system, even in the most extreme case, the number of peers that can be reached by a single peer in a time interval of a few tens of milliseconds is limited and certainly much smaller than the total number of peers in the system. This limitation is further reinforced by the fact that in a large system, a peer has only a partial view of the system (defined as its neighborhood in the peer-to-peer routing scheme).

Obviously, since our solution makes it impossible for a long-distance full communication to complete during a microsimulation step, it also discards the corresponding need for communications between LPs at runtime level during the simulation. In addition, since no coordination is required between LPs during the micro-simulation steps, most existing sequential event-driven simulation engines can be reused for implementing each simulation micro-step.

However, communications are still needed in order to coordinate the time-steps: Each simulation step starts with a number of pending receptions coming from previous steps, and produces a number of outgoing communications that will be received during a future step.

We also assume that if two peers are sufficiently close (eg. on the same subnet), they should be simulated within the same LP. The dual of this assumption is that any two peers that are simulated by two different LPs are always assumed not to be directly contending with each other on a local network. This way, we can safely assume that micro-simulations run in two distinct LPs have no local interactions and can only influence each other's behavior through long distance message passing. This assumption is consistent with the kind of system we target: Peer-to-peer systems are mostly running in residential networks and connected to the Internet through a DSL connection (or 3G/4G connection in the case of handheld devices) usually refered to as the Access Network. As shown on Figure 2, these local access networks are then connected through a backbone network that we call the Core Network. This is also consistent with the fact that in many simulators, given its complexity, this core network cannot be simulated using the same level of details as the local access network (discovering its actual topology is already a challenging research problem [START_REF] Oliveira | In search of the elusive ground truth: the internet's as-level connectivity structure[END_REF]). For example, the contention events can possibly be modeled in detail at the local level, while a more abstract stochastic model seems to be hardly avoidable at the core level.

The actual similarity between Figures 1 and2 is not fortuitous: NetStep is designed to ensure that within a given LP, the communications occuring between local peers is fully simulated by the (sequential) simulation engine running in the corresponding LP; On the contrary, a communication occuring between two peers not located in the same LP is a long distance communication, and its simulation follows a three phases protocol: (1) simulation of the local communication in the Access Network on the sender side, (2) simulation of Core Network transmission, and (3) simulation of the local communication in the Access Network on the receiver side.

The local communication in the Access Network is handled by the simulator reused for the micro-simulations. For the Core Network transmission, two options can be considered: either rely on the legacy model of the reused simulator, or delegate this part of the simulation to NetStep. In the first case, the computation has to be split between both ends or done fully by one end. In NetStep, the core simulation is done by the source end, such that the time of arrival at the other end of the core network is known. This last option also helps avoiding a performance issue when simulating flooding scenarios: If the simulation was to be done on the receiver side, the receiver LP would have to process all the messages sent to the flooded Peers, which would result in a flooding of the receiver side LP and its simulation engine as well. On the contrary, simulating the core network on the sender side opens interesting perspectives in terms of optimization.

The remainder of this paper is organized as follows: The related works are presented in Section 2; We give a formal definition of the micro-simulation in Section 3, and a description of the NetStep architecture in Section 4; We present our conclusions in Section 5.

RELATED WORK

Parallel time-stepped simulation is also commonly called time-parallel simulation, because it divides the simulation model in the time dimension and attempts to process the corresponding divisions in parallel, as opposed to the spaceparallel simulation that divides the simulation model in the space dimension [START_REF] Fujimoto | Parallel and Distributed Simulation Systems[END_REF].

For network simulation, the time-stepped approach is often used to reduce the number of events, as shown for example by Lu and Schormans [START_REF] Lu | Time-stepped approach for accelerated simulation of mobile ad hoc networks[END_REF]. They try to reach a reasonable trade-off between loss of accuracy (compared to event driven) and increased computation efficiency. Here, we can distinguish two main approaches: Either trying to reduce the number of events by replacing the packet-related events by some higher level abstraction events, such as packet trains [START_REF] Suk Ahn | Packet network simulation: Speedup and accuracy versus timing granularity[END_REF] or chunks of packets [START_REF] Guo | Time-stepped hybrid simulation (TSHS) for large scale networks[END_REF], or by replacing the packet model by a fluid model as initially proposed by Kesidis et al. for the simulation of ATM networks [START_REF] Cheung | Feasibility of fluid-driven simulation for ATM network[END_REF]. In the latter case, streams of packet are modeled as fluids, and events are associated to the change of fluid levels according to the traffic variations, meaning that the simulator can still be purely eventdriven. Yan and Gong showed that a time-driven stepped approach can be used with fluid models and that by varying the duration of the time-step, it allows to change the trade-off between accuracy of the results and complexity of the computation [START_REF] Yan | Time-driven fluid simulation for high-speed networks with flow-based routing[END_REF]. Although this technique allows better simulation speed-ups, this improvement comes at the cost of an additional tuning step to find the best trade-off.

A closely related approach, proposed by Ayani and Berkman, consists in trying to align the occurrence of events in order to obtain a synchronous processing. This technique, called time-synchronous parallel simulation, has been shown to be well suited for the SIMD model of parallel execution [START_REF] Ayani | Parallel discrete event simulation on SIMD computers[END_REF]. Even though the error generated by this forced synchronization can be minimized [START_REF] Park | A fast hybrid time-synchronous/event appraach to parallel discrete event simulation of queuing networks[END_REF], our approach in NetStep is to avoid model transformation and keep the asynchronous behavior of the model. However, we still have to solve an issue when the initial workload status at the beginning of a time step is missing.

Our solution is actually inspired by the conservative approach proposed by Lubachevsky [START_REF] Lubachevsky | Bounded lag distributed discrete event simulation[END_REF] that consists in defining a period of time, called bounded lag, during which it is safe to process events in parallel. Following a very similar idea, Nicol [START_REF] Nicol | Performance bounds on parallel self-initiating discrete-event simulation[END_REF] assigns a global ceiling to each LP. Similarly, Steinman [START_REF] Steinman | Discrete-event simulation and the event horizon[END_REF] suggests using the notion of Event Horizon to define a safe time period during which events can be processed in parallel. Even though the safe window defined by the event horizon could potentially be larger than the one defined by using the fixed causal latency, as proposed in our algorithm, it comes at the cost of an additional synchronization between the LPs, in order for each to compute and distribute the minimal event horizon among all the LPs.

Furthermore, given the figures we have in mind (several thousands of peers are to be simulated by each LP), we believe there is a high probability that this distributed minimum computation ends up with the same causal latency we already have chosen in our algorithm: It is sufficient that one peer sends a message at the very beginning of the time slot, and that this message needs only the minimal latency to reach a peer simulated by another LP.

Nevertheless, similar to the solution described by Steinman, our solution can benefit from the fact that the events being sent to other LPs will be inserted in the destination event queue at a later time than the time of an equivalent sequential simulation. As shown by Steinman, late insertion may significantly lower the load on the Future Event Set and finally impact positively the performance of the native simulator.

NetStep also has similarities and some shared motivations with the GENESIS tool developed by Szymanski et al. [START_REF] Boleslaw | Genesis: A system for large-scale parallel network simulation[END_REF]. Indeed both tools divide the simulation model both in time and space, and both aim at reusing existing simulation tools. However, genesis is a more general purpose tool, aimed at the simulation of any large-scale network while NetStep is more specifically geared at the simulation of P2P networks. This difference allows NetStep to make opportunistic assumptions and avoid synchronisation, while GENESIS uses an iterative approach that needs the same time-step to be computed several times until some convergence criterion is met that allows the simulation to proceed with the next time step.

In their Aurora system [START_REF] Park | Aurora: An approach to high throughput parallel simulation[END_REF], Park and Fujimoto use a Master/Worker architecture to distribute the simulation work, divided into work units, to computing nodes. Although there are some similarities with our work, their solution requires synchronization algorithms in order to compute lower bound on time-stamp (LBTS), while our solution avoids this requirement by putting restrictions on the kind of models supported, which in turns allows us to reuse in parallel multiple instances of an existing sequential simulator. Some general (non simulation related) parallelization techniques exist to improve the overlapping between computation and communications. The wait-by-necessity approach offered in GCM [START_REF] Henrio | An asynchronous distributed component model and its semantics[END_REF] is a seamless way of improving the over-lapping by using a programming language run-time construction. Our solution deals with the overlapping issue at a higher level by removing the need for synchronous communications during the computation steps. Nevertheless, synchronization communication still occur, but only during the transitions between the computation tasks.

A number of frameworks dedicated to P2P systems engineering have also emerged in the last few years. Splay, for example, provides a lightweight run-time for emulating the behavior of distributed algorithms, including P2P networks [START_REF] Leonini | P2P experimentations with Splay: From idea to deployment results in 30 min[END_REF]. The behavior of the Peers (or agents) is described using a high-level prototyping language, namely Lua. The benefits of using Lua and its extensions for Splay, is to make the code of each agent overly compact. For example, a Chord P2P agent requires no more than a hundred lines of Lua. Splay also provides a distributed run-time with strong isolation and web-services for real-time observations. Compared to Splay, our solution does not try to simplify the run-time or provide a lightweight solution, but rather to scale-up an existing sequential simulator and transform it into a large-scale distributed simulator, with the obvious benefit of being able to reuse all the existing models contributed to that sequential simulator.

SIMULATION MICRO-STEPS

A NetStep parallel simulation is divided in many sequential sub-simulations, each of which consisting of a number of micro-steps: The sequential simulations are used to divide the model in the space dimension, while the steps are used to divide each sequential simulation in the time dimension. µ t 0 →h (i)

P i1 P i2 P in I t 0 →h (i) O t 0 →h (i)
Figure 3: A simulation micro-step

In the spatial dimension, the system under study, which is composed of N entities (Peer, agents or any communicating devices using message passing as a means for interaction), is divided into P sub-systems, which represent groups of clusters of the previous entities. In the time dimension, each of these group is simulated in parallel, for the short period of time corresponding to a time-step, using an unmodified sequential simulator. Each unit of simulation is called a simulation micro-step and is executed by a Logical Process (LP). (A new LP may be created for each micro-simulation.) A schematic representation of a simulation micro-step is given Figure 3 (the notations used in the figure are explained hereafter).

We note µ t 0 →h (i) the simulation micro-step starting at simulation time t0 on LPi, i ∈ {1 . . . P } for a duration h = θ(t0, i); this micro-step simulates a sub-model of the system noted model(i, t0). We note P(t0, i) the set of peers being simulated by model(i, t0) in the micro-simulation step µ t 0 →h (i). The set of pending receptions at time t to be com- The set of all pending receptions at the begining of the time step µ t 0 →h (i) is called the time step input, and is noted I t 0 →h (i):

I t 0 →h (i) = k∈P(t 0 ,i) R(t, i, k), t ∈ [t0; t0 + h[
Similarly, the set of pending messages sent during the time step µ t 0 →d (i) is called the time step output, and is noted O t 0 →h (i):

O t 0 →h (i) = l∈P(t 0 ,i) S(t, i, l), t ∈ [t0; t0 + h[

ARCHITECTURE

The NetStep architecture consists of a number of Logical Processes (LPs), each executing an instance of the SimGrid simulator, and a Coordinator process.

The Coordinator includes four modules to manage the simulation micro-steps: a work-flow manager, an environment manager, a launcher and a message manager. The work-flow manager dispatches the micro-simulations steps and the corresponding inputs (incoming communications and initial state) to LPs. The environment manager then creates an opportune directory (sandbox) with all the necessary files. The launcher starts the simulation processes. When the peer network topology is fixed, the same simulation process may be used several times to run multiple time-steps in sequence; Otherwise, a new simulation process has to be started when the network topology varies between time-steps. The last module, the message manager, uses a client/server pattern to collect the un-dispatched messages from the various LPs. It memorizes them temporarily, so that they can reach the destination in the next simulation micro-step. If the number of the messages is too high for the available memory, a distributed message manager could be easily implemented.

In order to run a simulation micro-step without modifying the simulation engine, NetStep introduces a virtual simulation entity in each LP. This virtual entity acts as a proxy for the communications with external entities (peers located in other LPs): On their way out, the departing messages first go through the sender's access network and get routed to the proxy through a link that simulates the core network. Given the delay due to the core network, the message is expected after the end of the micro-simulation step and gets stored by the proxy as part of the micro-step's outputs. After the end of the micro-step, the coordinator routes the outputs of the last step to the corresponding future steps where they become the new inputs. It is important to note here that the future step is not necessarily the one coming right after the last one but possibly several steps later, depending on the core network delays. When the simulation running the step of the time of arrival starts, the pending inputs for that step are read by the LP proxy that schedules them to be routed on their expected time of arrival to the destinaton peer through the receiver's access network.

CONCLUSION

In this paper we presented NetStep, a framework that helps to distribute a simulation, dividing the execution both in spatial and temporal dimensions, using multiple LPs running in parallel series of simulation micro-steps. The timestepped simulation is used to optimize the simulation of the entities and of the events coordinating the simulation of small time windowed simulation steps. We implemented our solution by reusing the SimGrid simulation engine in order to reuse existing models, and tested on a simple peerto-peer model.

Our main motivation for this work is to be able to simulate very large scale border networks such as peer-to-peer networks or networks of handheld devices by reusing existing sequential simulators.

However, as mentioned in introduction, since our solution allows for a loose-synchronization between consecutive time-steps, some data may be missing at the beginning of a time-step, such as the workload status of the access network at the end of the previous step. We have started working on various solutions to this problem. For example, assuming that the only effect of the workload is to increase the communication delay in the source and destination access network, we first compute a slightly erroneous schedule for the sending and receiving events by assuming no workload, and then we make a correction to the schedule once the initial workload level is received from the previous time-step. This solution seems to solve well the case of outgoing communications, that can easily be buffered until the workload level is finally received (possibly as late as the end of the time-step); however this correction may come to late for the early receptions and produce a slightly erroneous (optimistic) reception schedule. Another idea to be investigated in the case of early receptions, is to use the last available workload level (possibly coming from a few steps back in the past), instead of waiting for the very last one. This is not fully accurate, but we think it might be safe to assume that the workload variations over reasonably short periods of time are sufficiently small to make this approximation acceptable.

It should also be noted that our solution only addresses the parallel execution of the simulation model, which leaves aside the parallel execution of other common tasks found in a simulation, such as the on-line statistics computation. Parallelizing all these activities is a challenging issue as long as those activities are coded inline with model. However, following our previous works [START_REF] Ribault | OSIF: A Framework To instrument, Validate, and Analyze Simulations[END_REF], we strongly believe that this problems can be dealt separately by using proper separation of concerns techniques.

Figure 1 :

 1 Figure 1: The two levels of communication in a PDES of a Peer-to-peer system model.

Figure 2 :

 2 Figure 2: The two levels of network model in a typical Peer-to-peer architecture.

  ∈ P(t0, i) during the step µ t 0 →h (i) is noted R(t, i, k), and the set of messages sent from a peer P l ∈ P(t0, i) in the simulation time interval [t0, t[ of the step µ t 0 →h (i), with t < t0 + h, is noted S(t, i, l).

				storage local
	model(i,t)			model(j,t)
	Proxy Network Layer Peers	routing message	Proxy Network Layer Proxy Network Layer Peers
	Simulation Engine			Simulation Engine
	LP(i)@Node(n)			LP(j)@Node(m)
	Message Manager	Environ. Manager
	Launcher		Workflow Manager
		Coordinator
	Figure 4: NetStep's architecture
	pleted by a peer P k

ACKNOWLEDGEMENTS

This work is partly funded by the SONGS project of the French National Research Agency, under contract ANR-11-INFRA-13.