Pierre Dragicevic

Anastasia Bezerianos
email: anastasia.bezerianos@ecp.fr

Waqas Javed
email: wjaved@purdue.edu

Niklas Elmqvist

Jean-Daniel Fekete
email: fekete@inria.fr

Temporal Distortion for Animated Transitions

Keywords: ACM Classification H.5.1 Multimedia Information Systems: [animations]; H.5.2 User Interfaces: [Graphical user interfaces (GUI)] Animated transitions, animation, information visualization

a) Constant speed. (b) Slow-in/Slow-out. (c) Fast-in/Fast-out. (d) Adaptive speed.

Figure 1. Different temporal distortion strategies for animated transitions. Solid shapes show original positions, faded shapes show ending positions.

INTRODUCTION

Animated transitions, where the transformation between visual states is conveyed with smooth rather than abrupt visual changes [START_REF] Hudson | Animation support in a user interface toolkit: Flexible, robust, and reusable abstractions[END_REF], are increasingly being used in modern interaction design. For example, the photo viewer Picasa smoothly expands and collapses image galleries, the Pivot browser [25] fluidly moves visual entities during faceted browsing, and different information visualization systems use animated transitions when switching between data dimensions [START_REF] Elmqvist | Rolling the dice: Multidimensional visual exploration using scatterplot matrix navigation[END_REF][START_REF]Health Visualizer[END_REF], visual representations [START_REF] Heer | Animated transitions in statistical data graphics[END_REF][START_REF] Yee | Animated exploration of dynamic graphs with radial layout[END_REF], or when navigating in time [START_REF] Chevalier | Using text animated transitions to support navigation in document histories[END_REF]12,26]. Research suggests that animated transitions not only improve the aesthetics of a user interface, but also helps users to understand the underlying data [START_REF] Bederson | Does animation help users build mental maps of spatial information?[END_REF][START_REF] Heer | Animated transitions in statistical data graphics[END_REF][START_REF] Tversky | Animation: can it facilitate?[END_REF]. However, there are many parameters involved in designing effective animations, including motion paths, staging, scheduling, and timing. In this paper, we focus on the latter: timing aspects of animated transitions.

Rather than having objects move or change at a fixed rate during an animation (Figure 1(a)), cartoon animators sometimes use a "slow in" or "slow out" effect [START_REF] Chang | Animation: From cartoons to the user interface[END_REF][START_REF] Johnston | The Illusion of Life: Disney Animation[END_REF], causing more frames to be dedicated to the beginning or end of the animation (Figure 1(b)). Essentially, slow-in and slow-out distort time throughout the animation. Computer applications have been quick to adopt this idea [START_REF] Kochanek | Interpolating splines with local tension, continuity, and bias control[END_REF], and many graphical toolkits (e.g., [START_REF] Bederson | Toolkit design for interactive structured graphics[END_REF][START_REF] Heer | prefuse: a toolkit for interactive information visualization[END_REF]) and animation packages (e.g., Microsoft PowerPoint and Autodesk Maya) use a combination of slow-in and slow-out (SI/SO) as their default animation pacing. Its use has also been advocated for optimizing animations in user interfaces [START_REF] Baecker | Animation at the interface[END_REF][START_REF] Chang | Animation: From cartoons to the user interface[END_REF][START_REF] Hudson | Animation support in a user interface toolkit: Flexible, robust, and reusable abstractions[END_REF][START_REF] Thomas | Applying cartoon animation techniques to graphical user interfaces[END_REF][START_REF] Yee | Animated exploration of dynamic graphs with radial layout[END_REF].

There are several arguments for using SI/SO, one being realism. However, physical realism is generally less crucial in graphical user interfaces than in cartoon animation. Another, more practical reason often cited for using SI/SO pacing is that it helps users to anticipate the beginning and ending of the animation. However, no perceptual studies have been performed to confirm this informal design rule. In particular, SI/SO dedicates less frames to the middle segmenteffectively accelerating it -so it is not clear whether it should be used in all cases, especially when the middle animation segment is visually complex or particularly important.

In this paper, we address this lack of empirical data by comparing object tracking performance in visually cluttered animations under different temporal distortion strategies, and show how effective these strategies are for important low-level tasks. We expect our results to help improve the animated transitions used in user interfaces and information visualization systems so that they become more useful to users.

BACKGROUND

Animation is the rapid display of static sequences to create the illusion of movement. It has been extensively studied by psychologists and applied to both films and computer graphics as well as for improving user interfaces.

Perception of Movement

Perceiving and interpreting motion is a fundamental capability of human perception with deep roots in our evolution: moving objects stand out in our visual field, and the Gestalt principle of common fate states that entities moving in the same direction are seen as a unit [START_REF] Palmer | Vision science: Photons to phenomenology[END_REF]. Perception research suggests that the human visual system is capable of tracking multiple objects simultaneously [START_REF] Cavanagh | Tracking multiple targets with multifocal attention[END_REF][START_REF] Pylyshyn | Tracking multiple independent targets: Evidence for a parallel tracking mechanism[END_REF]. The actual tracking is performed by the visual system using a mechanism known as smooth pursuit [START_REF] Palmer | Vision science: Photons to phenomenology[END_REF]. However, many factors influence this capability, including the number of distractors, object speed, occlusions, and motion paths of the objects being tracked.

Cartoon Animation

Designing animations was an active practice long before computers, and there is a wealth of literature, tradition, and design guidelines to draw upon for designing effective animations. In particular, Johnston and Thomas presented the "12 basic principles of animation" in their seminal work The Illusion of Life: Disney Animation [START_REF] Johnston | The Illusion of Life: Disney Animation[END_REF], discussing effective ways of making animations -particularly character animations -as realistic and as lifelike as possible.

Because most animation nowadays is done with computers, much effort has been devoted to transfering these principles to computer animation [START_REF] Lasseter | Principles of traditional animation applied to 3D computer animation[END_REF]. Accordingly, major computer animation packages such as 3D Studio MAX, AutoDesk Maya, and even Microsoft PowerPoint, today adopt most of the above basic principles of animation in their algorithms.

Animation in User Interfaces

Animations have been used in interactive applications since the advent of graphical user interfaces [START_REF] Baecker | Animation at the interface[END_REF]. Before GUIs, programmers would animate terminal output, e.g., to show progress in a time-consuming task. In 1993, Chang and Ungar [START_REF] Chang | Animation: From cartoons to the user interface[END_REF] as well as Hudson and Stasko [START_REF] Hudson | Animation support in a user interface toolkit: Flexible, robust, and reusable abstractions[END_REF] concurrently proposed applying cartoon animation to interfaces. Thomas and Calder [START_REF] Thomas | Applying cartoon animation techniques to graphical user interfaces[END_REF][START_REF] Thomas | Animating direct manipulation interfaces[END_REF] have since further improved upon this idea.

Similarly, efforts towards evaluating animated transitions date back to the early 1990s. Gonzalez [START_REF] Gonzalez | Does animation in user interfaces improve decision making[END_REF] performed an experiment to show that use of animated transitions in graphical user interfaces can improve the user's decision making process. Later, Bederson and Boltman [START_REF] Bederson | Does animation help users build mental maps of spatial information?[END_REF] empirically measured the effect of animated transitions on user capability to build mental maps of spatial information. Interestingly, Tversky et al. [START_REF] Tversky | Animation: can it facilitate?[END_REF] study the use of animation in graphical interfaces, and find that its use is mostly detrimental -except for congruence of motion. Building on this result, Heer and Robertson [START_REF] Heer | Animated transitions in statistical data graphics[END_REF] present results from two user studies that emphasize the importance of animated transitions for highlighting changes between related statistical data graphics. In a similar study, Shanmugasundaram et al. [START_REF] Shanmugasundaram | Can smooth view transitions facilitate perceptual constancy in node-link diagrams[END_REF] found that smooth transitions dramatically improved performance for memorizing graphs using node-link diagrams. However, all of the above studies investigate the benefits of adding animation to an interactive application, whereas there exists very little work that compares the performance of different types of animations. Notable exceptions focus on using animations as notification mechanisms [START_REF] Athènes | Human factors in ATC alarms and notifications design: an experimental evaluation[END_REF][START_REF] Bartram | Moticons: detection, distraction and task[END_REF]. In particular, we are aware of no existing work studying how temporal pacing for animation affects object tracking performance. While best practice design guidelines suggest the use of smooth animations with slow-in/slow-out extrema, no formal evaluation exists that verifies that this is indeed the optimal pacing strategy for animated transitions.

TEMPORAL DISTORTION IN ANIMATION

Computer animations can be modelled as parametric graphics with time-varying parameters (object positions, size, color, opacity, etc.). The simplest way to animate parametric graphics between two visual states is by linear interpolation, i.e., for each parameter p changing from p 0 to p 1 :

p(t) = p 0 + t(p 1 -p 0 ), t ∈ [0, 1]
where t is a global parameter that controls the speed and duration of the entire animation. When p is an object's position, this formulation produces trajectories that follow straight paths. If objects follow non-straight paths [START_REF] Johnston | The Illusion of Life: Disney Animation[END_REF][START_REF] Lasseter | Principles of traditional animation applied to 3D computer animation[END_REF], arc-length parametrization can be used instead.

On a computer screen the animation must be sampled. Assuming a constant frame rate f and given a total time T for the animation, we need n = f × T frames to complete the animation. Typical values for f are 60 Hz and typical durations of T are 0.5-1.0 seconds for transitions [START_REF] Heer | Animated transitions in statistical data graphics[END_REF]. The pacing of an animation is defined by a list of n values of t:

t ∈ {t 1 , t 2 , • • • , t n }
Setting t 1 = 0 and t n = 1, the increments ∆t(i) = t i -t i-1 for i ∈ [2, n -1] are left in the hands of the animation designer. Below we will discuss different strategies for determining these increments of the animation parameter t.

Constant Rate

Choosing a fixed ∆t = 1/(n -1) results in an animation with constant rate throughout its duration (Figure 2(a)). When an object's position is animated, this pacing yields a constant object velocity. In a collection of moving objects, all objects start and stop at the same time, but move with different velocities depending on the distance they must travel.

Constant rate animation has several advantages: it is easy to implement and yields predictable motion because the initial speed of an object suggests its final destination [START_REF] Rosenbaum | Perception and extrapolation of velocity and acceleration[END_REF]. However, it also produces high accelerations and decelerations on the first and last frames, and has a mechanical look that has been referred to as the "computer signature" [START_REF] Kochanek | Interpolating splines with local tension, continuity, and bias control[END_REF]. Using a varying ∆t(i) -or equivalently, applying a transformation t(i) → t ′ (i) to the constant pacing [START_REF] Hudson | Animation support in a user interface toolkit: Flexible, robust, and reusable abstractions[END_REF] -can be used instead in order to emphasize different parts of the animation. Below we describe some approaches to achieve this.

Slow-in/Slow-out

The concept of slow-in/slow-out (SI/SO) [START_REF] Johnston | The Illusion of Life: Disney Animation[END_REF][START_REF] Kochanek | Interpolating splines with local tension, continuity, and bias control[END_REF] uses t(i) values that devote more frames (smaller increments of t) to the endpoints of the animation, causing the motion to gradually speed up then slow down. Although many SI/SO pacings are possible, we use the following quadratic transformation of the linear pacing, illustrated in Figure 2(b):

t ′ = 2t 2 if t ≤ 0.5 1 -2(1 -t) 2 if t > 0.5
SI/SO is a recommended animation pacing for transitions in user interfaces [START_REF] Chang | Animation: From cartoons to the user interface[END_REF][START_REF] Hudson | Animation support in a user interface toolkit: Flexible, robust, and reusable abstractions[END_REF][START_REF] Yee | Animated exploration of dynamic graphs with radial layout[END_REF] and is used by default in several applications -e.g., MS PowerPoint, 3D Studio MAX and AutoDesk Maya -as well as graphical libraries like Piccolo [START_REF] Bederson | Toolkit design for interactive structured graphics[END_REF] and Prefuse [START_REF] Heer | prefuse: a toolkit for interactive information visualization[END_REF]. Beyond aesthetics, the supposed benefits of SI/SO are (i) that the gradual speed increase at the beginning of the animation helps users to start tracking an animated object, and (ii) that the decreasing speed at the end allows users to predict when an object will stop moving.

Fast-in/Fast-out

One potentially harmful effect of SI/SO is that it accelerates the middle of the animation, which can be problematic if something important occurs at this point. The middle of an animation can also be more cluttered and more difficult to follow, which happens for example when many points move from a random location to another [START_REF] Heer | Animated transitions in statistical data graphics[END_REF]. In this case, one intuition would be to slow down the midpoint of the animation instead of slowing down its endpoints. This not only reduces object velocity, but it also smoothens object motion, which can help visually resolving cluttered animations [START_REF] Thomas | Applying cartoon animation techniques to graphical user interfaces[END_REF].

We define fast-in/fast-out (FI/FO) animation as the dual of SI/SO, slowing down the animation in the middle as opposed to at its extrema. Again, many designs are possible but we use the following function to achieve this effect (Fig. 2(c)):

t ′ = (2t) 0.75 2 if t ≤ 0.5 1 -(2(1-t)) 0.75 2 if t > 0.5
Of course, this strategy has the unfortunate side effect that objects will move at their fastest speed at the beginning and end of the animation, presumably making it difficult to start and stop tracking any of them. In other words, this idea completely abandons the predictability property of SI/SO animation in favor of reducing visual complexity in the middle.

Adaptive Rate

SI/SO slows down the animation to emphasize its endpoints whereas FI/FO slows down its middle. To strike a balance between these two, we designed an adaptive technique that dynamically selects the frames with the highest visual complexity and slows down the animation around these frames. Figure 2(d) showcases this idea with one visual complexity peak at frame 18. We use an exponential function to slow down (but not completely stop) the animation around this frame. The technique is a generalization of both SI/SO and FI/FO: with peaks at the extrema or at the midpoint of the animation, the technique will reduce to the former or latter.

The remaining design parameters in this scheme are the calculation of visual complexity and the selection of peaks. For the former, complexity depends on the particular type of animated transition and the type of task. In our study, we focus on tracking points in animated point clouds, so for complexity we use a simple distance metric calculated on a per-frame basis for the constant rate animation:

D(t) = i min j =i ||p i (t) -p j (t)||
where p i (t) is the position of the point i at t in the constant rate animation. The intuition is that a frame t with low D is complex to follow because a large portion of the objects are located very close to each other, resulting in high degrees of occlusion and making single object tracking difficult.

The final step is to select a small set of frames representing visual complexity peaks, and to slow down the animation speed around these. Bear in mind that given a finite animation time T , slowing down one moment of an animation means speeding up another, so this should be done sparingly. We use a greedy scheme that keeps selecting peaks of high visual complexity (to a particular maximum) as long as they fall within a specific proximity (90-95%) of the most com-plex frame. This will result in at least one peak -the most complex one -being selected for slow-down. Because visual complexity often changes smoothly throughout an animation, we also enforce a minimum peak separation to avoid one portion of an animation to dominate the peak selection.

USER STUDY BACKGROUND

Here we present several decisions we made in the design of our user study, as well as some first exploration results.

Task Rationale

The goal of our user study is to determine the best way to present animated transitions in terms of temporal distortion, and we thus evaluated how accurately users understood different types of transitions under different temporal distortion schemes. Although what is exactly meant by "understanding" a visual transition is a matter of debate, a common experimental task is to have subjects track an object among others [START_REF] Chevalier | Using text animated transitions to support navigation in document histories[END_REF][START_REF] Heer | Animated transitions in statistical data graphics[END_REF]. This is an elementary low-level task, ensuring that if users are unable to perform it, then more complex tasks -e.g. following multiple independent objects or groups of objects -will be equally or more difficult. It is also safe to assume that many higher-level tasks will be difficult to perform if single objects cannot be tracked. For example, reading a scrollable text aloud is likely to be difficult if individual words cannot be tracked during scrolling.

Since our task is tracking an object among others, we focus on visual transitions that involve moving objects. Object translation is the most basic operation in animations. Other examples are changes in color or shape, but to keep the task simple we focused on moving objects that do not change during transitions. To further ensure that perceptual phenomena not directly related to animations such as object recognition and preattentive processing [START_REF] Ware | Information Visualization: Perception for Design[END_REF] will not interfere with the task, all objects were visually identical. One can assume that if an animation is effective for identical objects, it will also be effective for dissimilar objects. Arguably, in real applications users can highlight objects to facilitate tracking, but interactive highlighting is an orthogonal and complementary approach to animation: effective animations with highlighting support are preferable to poor animations with highlighting support, because they better help users follow objects that are not of immediate interest to them -hence providing context and facilitating incidental discoveriesand saves time by not requiring explicit object selection.

We therefore chose as visual transitions large sets of small objects that move from one location to another, i.e., point cloud transitions. This type of transition captures common visualization applications, such as scatterplot-based data exploration (e.g. [START_REF] Elmqvist | Rolling the dice: Multidimensional visual exploration using scatterplot matrix navigation[END_REF]12,26]) and faceted browsing of object collections (e.g. [START_REF]Health Visualizer[END_REF]25]). Finally, since we focus on time and not space, points move on straight paths. Although other trajectories have been proposed [START_REF] Elmqvist | Rolling the dice: Multidimensional visual exploration using scatterplot matrix navigation[END_REF][START_REF] Lasseter | Principles of traditional animation applied to 3D computer animation[END_REF], this is a simple approach that has been widely employed so far [12,[START_REF]Health Visualizer[END_REF]25].

Datasets

We use two datasets of point cloud transitions. The first one is randomly generated. User studies sometimes involve randomly generated data (e.g., synthetic graphs [START_REF] Moscovich | Topology-aware navigation in large networks[END_REF] or images [START_REF] Elmqvist | Color lens: Adaptive color scale optimization for visual exploration[END_REF]) because compared to real-world data, it is easier to describe in a reproductible way, eliminates the problem of selecting unbiased case scenarios -which is challenging when real-world data is very heterogeneous -and allows for better experimental control. Since we do not know of a method for randomly generating structured point cloud transitions, we introduce such a method. We also use another set of point cloud transitions taken from a real information visualization dataset (described in the User Study section).

A random point cloud is defined by 6 parameters:

• r is the random seed,

• n is the number of points in the cloud, • c is the amount of point clustering,

• p is the clustering power, • s is the separation between points, and • i is the number of iterations.

Figure 3 illustrates some values for c and s. A random point cloud transition is defined by the parameters above -which serve to generate the initial and final point clouds -plus the parameter m or motion coherence that affects how the final point indices are mapped to the initial ones (Figure 4). Details on the dataset generation are described in an appendix.

Task Difficulty

We first set out to discover what makes a point cloud animation easy or hard to follow with regards to tracking single points. We experimented with various randomly generated point cloud transitions and although we did not find any perfectly reliable predictor of task difficulty, we found that the number of object crossings strongly affected difficulty. We define distractor count or NDIST as the number of objects which cross the object of interest over the course of the animation. Incidentally, NDIST also captures the density of the point cloud (in denser clouds we expect more crossings), as well as the distance traveled by the target (the longer the distance, the more distractors are likely to cross the target).

Pilot Study

We conducted a pilot study investigating the traditional pacing profiles: constant speed and SI/SO. For this study we generated 100 random point cloud transitions by varying the parameters r, n, c, p, s, i, and m. We ensured that the generated trials had different instances of NDIST values. All animated transitions were limited to 1 second, a common duration for even complex animated transitions [START_REF] Heer | Animated transitions in statistical data graphics[END_REF]. The task consisted of tracking a point, and was identical to the one used in the full study. Four subjects participated in our pilot.

We explored the data using ScatterDice [START_REF] Elmqvist | Rolling the dice: Multidimensional visual exploration using scatterplot matrix navigation[END_REF] and first observed that all tasks for which all 4 users were successful using constant rate were also successfully completed by all 4 users using SI/SO. We then examined tasks for which SI/SO yielded more successful trials than constant rate. These were all tasks where the target point (i.e., the point to follow) was surrounded by other points (e.g., inside or next to a cluster) at the beginning and/or at the end of the animation. We hence postulated that SI/SO worked well primarily because it allowed users to better see what happens when the animation was the most difficult to follow. Inspired by this finding, we designed the adaptive speed technique and decided to also include the FI/FO technique (the dual of SI/SO) in the study.

Distractor Profiles

To test whether temporal distortion helps in following complex parts of an animation, we decided to explicitly include trials where animations are the most complex in the middle or at the endpoints. We thus introduce the measure distractor profile or DISTPROF, which captures the evolution of animation complexity in time, i.e., whether it is mostly complex at the endpoints or the middle (for a given target point to track):

DISTPROF = (n 1 + n 3 )/2 + 1 n 2 + 1
where

n 1 is the NDIST measure for t ∈ [0, 1 3 [ , n 2 is NDIST for t ∈ [ 1 3 , 2 3 ] and n 3 is NDIST for t ∈] 2 3 , 1]
. An animation that is mostly complex at the endpoints (e.g., the target goes from a dense cluster to another) yields DISTPROF > 1. An animation that is mostly complex at the middle (e.g., the target point goes through a dense cluster) yields DISTPROF < 1.

Error Metric

As our transitions were of fixed duration, we chose to not measure completion time but rather accuracy in tracking the target. Our selection error or ERROR metric is defined as:

ERROR(p s , p 1 t ) = err(p s , p 1 t ) E(err(p 1 i , p 1 t ))
, err(a, b) = ||a -b|| where p 1 t is the position of the target in the final point cloud, p s that of the user selection, and E(err(p 1 i , p 1 t )) is the expected error that would have been measured had the participant given a random answer, and is equal to the average distance of all points from the target. Thus, an average value of 1 means users guessed the answer whereas a value well above 1 could mean users were misled by the animation.

The definition of the ERROR metric is such that if the user selects the correct target, her error is 0. If she selects an object close to the target, her error is smaller than when selecting an object far from the target. Thus, good approximate selections are penalized less than completely random ones. Moreover, the normalization with the expected error ensures that in cases where most objects are close to the target, as in a tight object cluster, an arbitrary object selection within the cluster does not give too small an error.

USER STUDY

Given the above background, we designed a controlled experiment to formally evaluate object tracking performance under different temporal distortion strategies. We describe the details of this experiment in this section.

Task Generation

A task consists of a point cloud transition and a target, i.e., a particular point to follow. We included two task datasets (one generated, one real) with different properties in terms of structure. The generated dataset (see Figures 3 and4) was used to ensure we could fully test the different techniques under different distractor profiles. The use of the real dataset ensured that our findings were generalizable to real life data.

Generated:

We generated a set of random transitions with n = 200, c ∈ [-0.25, 0.5], p = -2, s ∈ [0, 0.05], i = 60 and m ∈ [0, 1]. For each of these transitions, we generated a task by randomly selecting a target point that (i) is not occluded by other points at the first and last animation frame and (ii) travels a minimum distance of 0.5i.e., half of the point cloud size. We then pruned tasks for which NDIST < 15 in order to further ensure that they were not too easy. We grouped these tasks into into three bins (d e , d m , d o ). Tasks in the first bin d e are complex at the two endpoints (DISTPROF > 1), and we chose ones with DISTPROF ∈ [5, ∞[. In bin d m tasks are complex in the middle (0 < DISTPROF < 1) with DISTPROF ∈ [0, 0.5]. Finally, tasks in d o are close to constant complexity (DISTPROF ∼ 1) and we chose ones with DISTPROF ∈ [0.8, 1.2]. The chosen margins for the values of DISTPROF between bins ensures that tasks differ enough in their distractor profile. We randomly selected 12 tasks per bin and obtained a total of 36 randomly-generated tasks.

Real:

The second dataset is a high-dimensional dataset of digital cameras 1 (1,038 objects and 8 dimensions per object). A point cloud transition in this dataset depicted the change between two scatterplots of different dimension pairs. To select tasks that follow the distractor profiles we wanted to explore, we generated about 800 potential tasks by combining (i) random transitions (combinations of dimensions), and (ii) random objects as targets, always ensuring that the target was not covered by other objects at the first and last animation frame. Since values for DISTPROF were very close to 1, we used only two bins (d e , d m ) for which we selected the 12 tasks with highest DISTPROF (complexity at the extrema) and the 12 with lowest DISTPROF. The selected bins verified DISTPROF > 1.2 and DISTPROF < 0.8 respectively.

Procedure and Apparatus

Participants were first shown the initial point cloud. They were asked to press the Space bar to highlight the target in red. After releasing Space, the highlighting of the target would disappear (but persisted for at least 1 second). When subjects were ready to begin the trial they pressed Space again, after which all objects were animated to their final state. Participants were then asked to use the mouse to select the target in this final state as accurately as possible.

The experiment was conducted on a desktop computer equipped with a mouse, keyboard, and a 19" LCD monitor (1280 × 1024 resolution, 60 Hz refresh). Point clouds were shown in a 800 × 800 rectangular area, with points being dark gray 16-pixel squares. Animations lasted one second.

Experimental Design and Procedure

12 participants (paid university students) were randomly assigned to one of 4 groups. Each group used all 4 techniques described in the design space section in an ordering balanced using a Latin square. Tasks were selected as described previously, and were repeated across techniques. To avoid learning, task order was randomized across techniques, and point clouds were rotated by 90 o between techniques.

Prior to each technique users were given brief instructions, without explaining the implementation details of each technique, and performed a short warm-up session (2 trials) to familiarize themselves with the technique. The experiment lasted on average 45 minutes and had the following design:

RESULTS

Trials were marked as outliers when ERROR was beyond 3 standard deviations from the mean for a given subject, TECH and DISTPROF (1% of all trials), and were removed from further analysis. The remaining trials were aggregated per subject for each combination of conditions, and followed closely the normal distribution.

Error (Figure 5)

Generated Dataset

ANOVA showed a significant effect of TECH on ERROR (F 3,33 = 35.1, p < .0001). Post-hoc pair-wise means comparison (all adjustments Bonferroni) showed that SI/SO and C were significantly different from each other and from all other techniques (all p < .01). Mean ERROR was lowest for SI/SO (0.28), then C (0.49), A (0.63), and FI/FO (0.65).

A significant TECH × DISTPROF interaction was present (F 6,66 = 4.4, p < .0001). Pair-wise means comparison (all p < .05) showed that SI/SO was significantly better than all other techniques across distractor profiles. However, the results differ for the remaining techniques. Specifically under the d m and d o distractor profile, A performs significantly worse than C, but not in the d e distractor profile case.

Real Dataset

ANOVA on the real dataset yielded a significant effect of TECH on ERROR (F 3,33 = 17.6, p < .0001). Pair-wise means comparison (all p < .05) showed that SI/SO was significantly more accurate than C and FI/FO, with no significant difference between SI/SO and A. Contrary to the generated dataset, mean ERROR was less for SI/SO (0.25), followed this time by A (0.32), C (0.39), and FI/FO (0.51).

A significant TECH × DISTPROF interaction was present (F 3,33 = 2.9, p < .05) for the 2 distractor profiles. Pairwise means comparison (all p < .05) showed that for the d e distractor profile, the trends follow that of the main analysis (SI/SO not different from A, but better than C and FI/FO). However, for the d m distractor profile, we found that SI/SO was significantly better than A, but not C.

Correct Answers (Figure 6)

Although we were mainly interested in the selection error ERROR, we investigated perfectly correct trials (trials where ERROR = 0) to see the percentage of correct answers per technique and distractor profile.

Error rates were relatively high compared to the many user studies that focus on completion time. This is because we only measure errors: had we measured low error rates (by giving trivial tracking tasks) we would have seen little or no difference between techniques. Note that the relatively high difficulty of our tasks is not artificial, as many graphical applications display large numbers of objects and animate them very rapidly so as not to slow users down (e.g., [25]).

Generated Dataset

The number of correct answers (303 overall) was higher for SI/SO (38%), followed by C (31%), FI/FO (15%), and A (14%). There was a significant effect of TECH (F 3,33 = 21, p < .0001), with SI/SO and C having more completely correct trials than A and FI/FO (all p < .05). A significant TECH × DISTPROF (F 6,66 = 5.1, p < .0001) interaction showed that this trend was not followed in the d e distractor profile, where SI/SO was significantly better than C as well, but not A (all p < .05). By examining the correct trials in detail, we found that if a task was completed correctly in any of the techniques (303 correct trials corresponding to 17 tasks), it was also performed correctly using SI/S0 in 95% of tasks.

Real Dataset

The number of correct answers (352 overall) was higher for SI/SO (36%), then for A (34%), C (32%), and finally FI/FO (20%). There was a significant effect on TECH (F 3,33 = 12.2, p < .0001), where SI/SO had significantly more correct trials than C and FI/FO, but not A (all p < .05). No interaction effect with distractor profile was present. We further found that if a task was completed correctly in any of the techniques (352 trials corresponding to 24 tasks), it was also performed correctly with SI/SO in 84% of tasks.

DISCUSSION

We can summarize the results from the study as follows:

• The SI/SO animation pacing technique has better performance (i.e., significantly higher accuracy) than any of the other techniques tested for all distractor profiles;

• The other pacing techniques, while all less accurate than SI/SO, have different performance depending on the distractor profile; in particular, we see the following:

• Adaptive speed pacing works best for transitions with high complexity at the extrema of the animation (d e ), where it basically reduces to SI/SO; and

• Constant speed motion is better than adaptive speed and FI/FO for all other distractor profiles (d m and d o ), second only to SI/SO.

In the following section, we try to explain and generalize these results. We also try to offer some recommendations for designers planning to use animation in interaction design.

Explaining the Results

There seems to be two primary and conflicting principles at work for how to effectively design the temporal pacing of linear animated motion of point clouds:

P1 Allocate frames to endpoints: Spend the majority of the frame budget on the beginning and end of an animation to allow users to anticipate motions; or P2 Allocate frames to complex segments: Spend the frame budget on segments of an animation that are visually complex, either by calculating the complexity (adaptive) or by observing typical point cloud transitions (fast-in/fast-out).

Principle P1 has so far been the dominant approach in animation literature, practice, and tradition, whereas P2 has barely received any attention at all. One of the conclusions of the present work should be that this emphasis on the endpoints of an animation has been justified, and that a strategy based on adapting animation speed depending on frame complexity will only be successful when those complex frames happen at the animation endpoints. In other words, easing in and out of an animation seems much more important than slowing down and speeding up around frames of high visual complexity. The question is of course why this is the case.

A common explanation is that gradually accelerating and then decelerating motion aids tracking the object as well as helps the user in anticipating the beginning and ending of the animation. In particular, if the user is not expecting the animation to happen in the first place, a slow and gradual start will help the user to detect that the animation is starting and to adjust to the tracking task accordingly. In other words, predictability seems to be one of the key features named for slow-in/slow-out pacing, not that the slow movement allows users to better decipher complex parts of the animation (P2 above). To begin to find an explanation for why predictability is so dominant in this task, it is necessary to delve into the workings of the human visual system.

Human Vision and Smooth Pursuit

Voluntary eye movement can be performed in only two separate ways: saccadic movement and smooth pursuit [START_REF] Krauzlis | The control of voluntary eye movements: New perspectives[END_REF][START_REF] Palmer | Vision science: Photons to phenomenology[END_REF], where the latter is the method employed during object tracking (at least for objects moving slowly enough that catch-up saccades are not necessary [START_REF] Barnes | Cognitive processes involved in smooth pursuit eye movements[END_REF]). Research in smooth pursuit shows that it consists of two stages [START_REF] Krauzlis | Temporal properties of visual motion signals for the initiation of smooth pursuit eye movements in monkeys[END_REF]: open-loop and closed-loop pursuit. Open-loop pursuit is the first visuomotor response to motion and typically lasts 100 ms; it is ballistic and thus not attuned to the velocity or direction of the visual stimulus. Closed-loop pursuit then takes over until the motion ends, and is characterized by uniform pursuit gain, i.e., the ratio between angular velocity of the eye and the target is close to 1 (the target's retinal velocity is zero).

This suggests two things: First, that a slow and gradual start of an animated motion will help mitigate any inaccuracies caused by the ballistic behavior of the first open-loop response. This presumably prevents the user from losing tracking of an object in the first few instants of the animation. Second, a gradual slow-down will help the closed-loop stage in dynamically adjusting the angular velocity of the eye to maintain zero retinal velocity of the moving object.

In other words, this presumably prevents the user's eye from overshooting a target as it reaches the end of its motion path.

Note that recent evidence in vision science suggests that overshooting generally does not occur, even if the motion stops unexpectedly [START_REF] Krauzlis | Transitions between pursuit eye movements and fixation in the monkey: Dependence on context[END_REF], and that the eye, after a latency of about 100 ms, is capable of decreasing its velocity to zero in a constant time of 100 ms [START_REF] Pola | Offset dynamics of human smooth pursuit eye movements: effects of target presence and subject attention[END_REF]. Nevertheless, overshooting the target as it stopped was a common complaint among participants for other pacing techniques than slow-in/slowout in our experiment. We speculate that because our point clouds involved many distractor objects that often ended up in the same vicinity at the end of an animation, the final few instants of an animation were crucial for successfully distinguishing the target, and thus that the ∼200 ms response may cause tracking loss for abrupt stops.

It should also be noted that given the time intervals involved in smooth pursuit, i.e., 100 ms for the ballistic open-loop response, 100 ms latency for detecting motion termination, and 100 ms for slowing down the eye velocity to zero, our one-second animations are highly taxing for the visual system -around 30% of the duration of the animation is spent in visuomotor response to the motion! Nevertheless, onesecond transitions remain an informal guideline for interaction design [START_REF] Heer | Animated transitions in statistical data graphics[END_REF], and the fact that the error rate in our experiment was so low for such comparably difficult tasks attributes to the capabilities of the human visual system.

Scientific findings on smooth pursuit may also explain why principle P2 is not more significant than it is. While it is generally difficult to initiate smooth pursuit without visual stimulus [START_REF] Krauzlis | The control of voluntary eye movements: New perspectives[END_REF], research shows that it is possible to continue smooth pursuit if a target is momentarily occluded [START_REF] Barnes | Cognitive processes involved in smooth pursuit eye movements[END_REF]. This suggests that visual complexity in the form of overlapping and crossing motion paths may not be as serious a problem as we may have initially thought, and that frame budgets are better spent on the extrema of the motion.

Finally, it is possible that abrupt changes in object velocity must be avoided not only at animation endpoints, but also during the animation itself in order to facilitate object tracking. If true, this would suggest a third design principle (P3): keep velocity variations as low as possible, from which P1 (SI/SO) would simply be a consequence. This is an intriguing possibility that needs further investigation in the future.

Limitations

Our work makes a number of assumptions that may limit its broad applicability to other areas. For example, we focus on animated transitions of point clouds where each point has the same visual appearance, whereas it can be argued that in many real-world animations, the objects have a unique visual identity which would simplify object tracking. However, this is an orthogonal aspect of temporal distortion, and we think that our results should generalize to real-world tasks as well.

Another potential limitation is that our study only measured tracking of a single object, but many realistic tasks involve several objects moving simultaneously; in fact, perceptual research suggests that most humans are capable of tracking up to four or more objects at the same time [START_REF] Cavanagh | Tracking multiple targets with multifocal attention[END_REF][START_REF] Pylyshyn | Tracking multiple independent targets: Evidence for a parallel tracking mechanism[END_REF]. Our motivation here is that object tracking of a single object is clearly a task component of tracking multiple objects, so our results should give an indication of the general case. Nevertheless, more research is needed to study this in full detail.

Furthermore, recent results in vision science show that it is possible to initiate smooth pursuit even before the target starts to move, especially if the person knows exactly when it will start [START_REF] Barnes | Cognitive processes involved in smooth pursuit eye movements[END_REF]. This was of course the case for our experiment, where participants initiated the transition by pressing the space bar. More research is needed to see whether unexpected animated transitions will cause different results for animation pacing on object tracking than those we observed.

Finally, given the perceptual nature of our evaluation, it would be interesting to also study these effects using a highprecision eye tracker. For example, is there an overshooting effect when an object moving at constant speed stops, and is there a marked difference for slow-in/slow-out motion?

Generalizations

Despite the above limitations, we still believe that our task and our findings are general enough to apply to a wide spectrum of interaction and visualization scenarios. In other words, our recommendation for short-duration animated transitions to show state changes in an interactive application is to use slow-in/slow-out animation pacing -not only does this result in more realistic and aesthetically pleasing motion, it also provides the high predictability necessary for reliably tracking individual objects in the animation.

It is hard to say whether our findings also generalize to other animation durations or to non-linear motion paths. They should hold for slightly different animation durations, but with very different durations we would have observed either a ceiling effect or a floor effect given our task difficulties. As for non-linear paths, animation practice suggests using them [START_REF] Johnston | The Illusion of Life: Disney Animation[END_REF][START_REF] Lasseter | Principles of traditional animation applied to 3D computer animation[END_REF], but our intuition suggests that this would again decrease the predictability of the motion. Future research should address this question.

Finally, it is important to note that our work has not addressed the question whether or not to use animation in the first place, but rather which pacing methodology should be chosen if animation is adopted in an interactive application.

For the former question, we refer the reader to existing literature on the topic, such as that of Tversky et al. [START_REF] Tversky | Animation: can it facilitate?[END_REF].

CONCLUSION AND FUTURE WORK

We have presented results from a formal user study evaluating object tracking accuracy in animated point cloud transitions under different temporal distortion strategies. These results provide solid empirical data on the use of animation for graphical user interfaces, an area that so far has largely been dominated by design principles from general animation that may not necessarily transfer to interaction design. Our findings show that slow-in/slow-out, i.e., smoothly stretching time at the endpoints of an animation, is the most accurate temporal distortion strategy, and we speculate that this is because it maximizes the predictability of the motion.

In future work, we plan to design temporal distortions that support both design principle P1 -slowing down around the endpoints of the animation -and principle P2 -slowing down around visually complex animation frames. We are also interested in mathematically optimizing temporal distortion functions similar to van Wijk and Nuij's approach to pan-and-zoom animation [START_REF] Van Wijk | A model for smooth viewing and navigation of large 2D information spaces[END_REF]. Finally, we would like to explore more complex time distortion schemes, such as staging animation [START_REF] Heer | Animated transitions in statistical data graphics[END_REF] so that all objects move at the same velocity.

Animation for interaction design is a large topic, and we plan to continue to study differences between this domain and cartoon animation. For example, slow-in/slow-out is just one of Disney's 12 basic principles of character animation [START_REF] Johnston | The Illusion of Life: Disney Animation[END_REF], and it would be useful to explore the other principles in equal depth as our present work. In addition, our results also open up an array of new questions on human perception that needs further investigation, including impacts of momentary occlusion, curved motion paths, and the number of distractors.

  (a) Constant rate. (b) Slow-in/Slow-out. (c) Fast-in/Fast-out. (d) Adaptive rate (frame 18).

Figure 2 .

 2 Figure2. Evolution of the animation parameter t (black squares) and animation rate ∆t (red crosses) for 4 different temporal pacing strategies in an animation consisting of n = 60 frames. The animation rate is normalized across all 4 techniques to allow for comparison. For adaptive speed, the technique has detected a complexity peak at frame 18. Note that all techniques except SI/SO have abrupt speed changes at the start and end.

Figure 4 .

 4 Figure 4. Two transitions between the same point clouds, one with low motion coherence (m = 0) and one with high motion coherence (m = 1). Point trajectories are shown with trails going from blue to red.

Figure 3 .

 3 Figure 3. Examples of point clouds generated with parameter values r=0, n=200, p=-2, i=60, and various values of c (clustering amount) and s (point separation). The second point cloud shows a true pseudo-random distribution.

12 participants 4

 124 TECH (C, SI/SO, FI/FO, A) 2 DATASET (Generated, Real) 3, 2 DISTPROF (d e , d m , d o ) × 12 repetitions 2280 total trials 1 Collected from http://www.dpreview.com/.

Figure 5 .

 5 Figure 5. Mean selection error ERROR grouped by distractor profile DISTPROF for all TECH. Generated (left) and real DATASET (right).

Figure 6 .

 6 Figure 6. Percent of correct answers grouped by DISTPROF for all TECH. Generated (left) and real DATASET (right).

APPENDIX

To generate a random point cloud from the parameters listed in the Datasets section (in bold here), we first initialize the random seed to r and choose n points p i ∈ S, with S being the unit square. We then move them using a force-directed algorithm and i iterations. The force exerted on each p i is:

• F C is the clustering force, defined as:

k-p being the force magnitude. We use k = 7 because it yields similar degrees of visual clustering for different values of p. u is the unit vector u ||u|| d Cmin is the minimum distance above which the force applies. We use d Cmin = 0.1 if c > 0 and = 0.05 otherwise. f C0min is the force applied below the minimum distance. We use f C0min = f C0 if c > 0 and = 0 otherwise.

• F SQ is the clustering force in an homogeneous square, a term that prevents the whole point cloud from collapsing:

• F R is the point repulsion force that locally reduces cluster density and point overlap:

• p i p j if ||p i -p j || < s 0 otherwise f R0 being the amount of repulsion. We use f R0 = 0.001.

• F ER is the edge repulsion force that prevents points from going past the unit square:

otherwise Ω is the point on S's edge closest to p i . We use f ER0 = 2.

• F F is the fluid friction force that prevents points from moving too fast:

To generate a transition, we first generate two point clouds P 0 = (r, n, c, p, s, i) and P 1 = (r + 1, n, c, p, s, i) with the previous method. At this point, every point of index i moves from the location p 0 i ∈ P 0 to the location p 1 i ∈ P 1 . We then increase motion coherence by taking two random indices i and j and swapping p 1 i and p 1 j if this yields a lower value of ∆ i + ∆ j . This operation is repeated n 2 m 2 times. ∆ i is the relative motion of the point of index i, defined as:

(p 1 j -p 0 j ) di,j j|di,j =0 1 di,j with d i,j = (p 0 i p 0 j ) 2 + (p 1 i p 1 j ) 2


Sonia Belhareth

David Coudert

Dorian Mazauric

Nicolas Nisse

MASCOTTE Issam Tahiri

Reconfiguration with physical constraints in WDM networks

In a WDM network, setting up a new wavelength in a fiber requires recalibrating the other wavelengths passing through this fiber. This induces a cost (e.g., time, energy, degradation of QoS) that depends nonlinearly on the number of wavelengths using the fiber. When a set of connection requests must change their optical paths in the network (e.g., during a maintenance operation on a link in the network), the order in which requests are switched affects the total cost of the operation. That is, the reconfiguration of the routing in a WDM network has some cost due to physical layer impairments. We initiate the study of the corresponding optimization problem by modeling the cost of switching a request as a non-linear function depending on the load of the links used by the new lightpath. We prove that determining the optimal rerouting order is NP-complete for a 2nodes network. We then give general lower and upper bounds on the minimum cost and we identify classes of instances where the problem can be solved in polynomial time. We design heuristics for this problem and analyze their behavior through simulations.

I. CONTEXT AND MOTIVATION

In connection oriented networks such as Wavelength Division Multiplexing (WDM) networks, each connection request d ∈ Π is assigned a lightpath under the wavelength continuity constraint, that is to say a path in the topology and an endto-end wavelength. The Routing and wavelength assignment (RWA) problem consists in assigning such a lightpath for each request under the constraint that two optical paths sharing a fiber have distinct wavelengths [START_REF] Mukherjee | WDM-based local lightwave networks-P. II: Multi-hop systems[END_REF], [START_REF] Jaumard | Comparison of ILP formulations for the RWA problem[END_REF]. The set of lightpaths, or routes, obtained in that way is called a configuration.

Current WDM networks are becoming more flexible, offering new on-demand services for provisioning new lightpaths, but also allowing better management of maintenance operations (requiring to switch off equipments) and equipments failures -due to earthquake, tsunami, or a backhoe unfortunately breaking a pipe containing some fibers. A building block for flexibility and reliability is the possibility to reconfigure the routing, that is to compute new optical paths for some connection requests and then to switch the traffic from former to new optical paths. Such process may however affect the quality of service by inducing potential traffic disruptions. Moreover, due to physical layer impairments [START_REF] Saradhi | Physical layer impairment aware routing (pliar) in wdm optical networks: issues and challenges[END_REF], reconfiguring the routing -setting up the new lightpaths -induces some cost for the network operator, in particular if service level agreements are not fulfilled. Thus, the routing reconfiguration process must be carefully optimized.

A classical approach for reconfiguring the routing is based on the Move-to-Vacant (MTV) scheme [START_REF] Lee | A wavelength rerouting algorithm in wide-area alloptical networks[END_REF]- [START_REF] Chu | A study of lightpath rerouting schemes in wavelength-routed WDM networks[END_REF] which consists in sequentially choosing a lightpath, computing a new route using available resources for the corresponding request, and then switching the request from its current lightpath to its new route in a make-before-break fashion as standardized for MPLS networks [START_REF] Mannie | Recovery (protection and restoration) terminology for generalized multi-protocol label switching (GMPLS)[END_REF]. This process is repeated sequentially until the reached configuration achieves the desired constraints (e.g., overall usage of resources, availability of a desired route). The main issues when using the MTV approach are to guarantee the convergence of such a process and to control the number of route changes. Moreover, such solutions are not sufficient and interruptions may be necessary [START_REF] Jose | Connection rerouting/network reconfiguration[END_REF], [START_REF] Cohen | Tradeoffs when optimizing Lightpaths Reconfiguration in WDM networks[END_REF].

To ensure both a fast termination and that the final configuration satisfies the desired performance criteria, another approach consists in pre-computing the target configuration and then to focus on the reconfiguration itself, that is deciding in which ordering the existing lightpaths should be switched to achieve the final configuration. More formally, the reconfiguration problem is to determine the "best" sequence (order) of connections rerouting to move from the current configuration to a predetermined target configuration, under the constraint that the connections are moved one by one [START_REF] Jose | Connection rerouting/network reconfiguration[END_REF]. However, the final lightpath of a request d ∈ Π may use resources (e.g., a wavelength on a fiber) that are used by the initial lightpath of another request d ∈ Π. This latter request d must then be moved before the connection d. The difficulty of the reconfiguration problem lies mainly in the existence of dependency cycles that require to temporarily suspend some connections to allow switching the other requests. Such an interruption corresponds to the concept of break-before-make standardized for MPLS networks [START_REF] Mannie | Recovery (protection and restoration) terminology for generalized multi-protocol label switching (GMPLS)[END_REF]. A break-before-make starts by interrupting the lightpath of a request before establishing the new route. Several recent studies have considered the framework proposed by Jose and Somani [START_REF] Jose | Connection rerouting/network reconfiguration[END_REF] to minimize either the total number of interruptions, or the maximum number of requests that are simultaneously interrupted, during a reconfiguration [START_REF] Cohen | Tradeoffs when optimizing Lightpaths Reconfiguration in WDM networks[END_REF]- [START_REF] Solano | Lightpath reconfiguration in WDM networks[END_REF].

In this article, we address the problem of reconfiguration in a different way, which is the inclusion of physical constraints to the establishment of an optical path. We aim at optimizing the reconfiguration cost which is induced by physical layer impairments. Indeed, the transmission of an optical signal in a fiber is subject to many parameters: bandwidth, transmission power, signal attenuation requiring the use of amplifiers every 50-80 km, phase shifts associated the imperfection of the laser and the distortion of the fiber, and various electro-magnetic effects (see [START_REF] Saradhi | Physical layer impairment aware routing (pliar) in wdm optical networks: issues and challenges[END_REF] for more details). This requires extremely fine adjustments to ensure good transmission quality, but everything has to be redone (or adapted) when a new wavelength is used in the fiber. Thus, setting up a new lightpath in a network has a cost (energy, time and/or man power) due to the recalibration on all fibers used by the path which depends (non-linearly) on the number of wavelengths already present. In addition, these changes can affect the entire network by spreading corrections to be made. See [START_REF] Manousakis | Offline impairment-aware routing and wavelength assignment algorithms in translucent WDM optical networks[END_REF] for an example including these effects in the computation of optical routing.

1) Results: In this preliminary work, we propose to model the cost of rerouting a request in a configuration as a simple non-linear function depending on the load of the links used by the lightpath to be established, where the load of a link is the number of lightpaths crossing it in the current configuration. Our cost function also depends on a tunable parameter α ≥ 0 which is an exponent, e.g., α = 1 corresponds to a linear cost function. Given an initial configuration and a precomputed target one, the objective is to switch sequentially the requests from their initial route to the final one in order to achieve a minimum global cost. Since minimizing the number of interruptions during a configuration is known to be NP-complete and difficult to approximate [START_REF] Cohen | Tradeoffs when optimizing Lightpaths Reconfiguration in WDM networks[END_REF], [START_REF] Coudert | Rerouting requests in wdm networks[END_REF], we have preferred studying the cost optimization problem by itself. Therefore, we assume that the reconfiguration may be performed regardless of unavoidable interruptions: we assume that all connections have different wavelengths and thus no interruptions are needed.

With this model and hypothesis, we prove that the routing reconfiguration problem is NP-complete even in a physical network with two nodes and when α = 0. We then characterize a particular class of instances where the problem can be solved in linear time, for any α ≥ 0. In the particular case of a ring topology and α = 1, we give a simple linear algorithm for solving the problem. Due to lack of space, proofs have been sketched or omitted and can be found in [START_REF] Belhareth | Reconfiguration with physical constraints in wdm networks[END_REF]. Finally, we design several heuristics and report on numerical simulations that are compared whenever possible to the optimal solutions (e.g., in the case of a ring and α = 1), and with generic upper and lower bounds that we have exhibited.

2) Related work: The reconfiguration problem has been widely studied using the Move-To-Vacant method. Integer Linear Programming (ILP) modelisation [START_REF] Klopfenstein | Rerouting tunnels for MPLS network resource optimization[END_REF], [START_REF] Zhang | Optimization of semi-dynamic lightpath rearrangements in a wdm network[END_REF] and heuristic algorithms [START_REF] Lee | A wavelength rerouting algorithm in wide-area alloptical networks[END_REF]- [START_REF] Chu | A study of lightpath rerouting schemes in wavelength-routed WDM networks[END_REF] have been proposed.

More recently, the notion of dependency digraph has been introduced to study routing reconfiguration problems [START_REF] Jose | Connection rerouting/network reconfiguration[END_REF]. The dependency digraph of an instance of the reconfiguration problem has one vertex per connection to be moved and an arc from request d to request d when d must be moved to allow the establishment of the new optical path of d [START_REF] Jose | Connection rerouting/network reconfiguration[END_REF]. Using this concept, Jose and Somani showed that the minimum number of requests to be interrupted during the reconfiguration equals the minimum feedback vertex set of the dependency digraph. In [START_REF] Coudert | Rerouting requests in wdm networks[END_REF], the routing reconfiguration problem has been modeled in terms of digraph processing game on the dependency digraph. The main objectives studied in this context are the minimization of the total number of interruptions and the minimization of the maximum number of simultaneous interruptions. The corresponding decision problems are NP-complete in general and difficult to approximate [START_REF] Cohen | Tradeoffs when optimizing Lightpaths Reconfiguration in WDM networks[END_REF], [START_REF] Coudert | Rerouting requests in wdm networks[END_REF]. Tradeoffs between these two objectives are studied in [START_REF] Cohen | Tradeoffs when optimizing Lightpaths Reconfiguration in WDM networks[END_REF]. ILPs and heuristics to address this problem have been proposed [START_REF] Solano | Analyzing two different objectives of the WDM network reconfiguration problem[END_REF], [START_REF] Solano | Lightpath reconfiguration in WDM networks[END_REF], [START_REF] Coudert | Reconfiguration of the routing in WDM networks with two classes of services[END_REF].

II. MODELING

We start by defining the notations used throughout this paper. We then define formally the cost induced by switching a request from a lightapth to another one in a given configuration. The reconfiguration problem studied in this paper consists in minimizing the cost of a sequence of switchings to go from an initial configuration to a given final one.

Let D = (V, A) be the directed connected multi-graph modeling the physical network. A request d in D is a pair of vertices (s d , t d ), the source and the destination. Let Π ∈ V ×V be the set of connection requests, and let m = |Π|. For any request d ∈ Π, a route R d for d is a lightpath for d, i.e., a path from s d to t d in D together with a wavelength. Abusing the notation, R d denotes also the path in D of the route R d . Given a physical network D and a set of requests Π, a configuration C is a set of routes in D, one for each request d ∈ Π. The load of a link e ∈ A in a configuration C is the number of routes using e in C, that is,

l C (e) = |{d ∈ Π : e ∈ A(R d ), R d ∈ C}|
In this paper, we do not consider the capacity of wavelengths nor network's links, that is the number of routes sharing some edge of E is not limited. Hence, given any configuration, it is always possible to establish the route of a new request -no interruption of existing requests is required. However, in order to take into consideration the physical constraints described in the Introduction, we define the cost of establishing a new request as the following non-linear cost function. Informally, the cost depends on the load (in the current configuration) of the links used by the route of new established request. More formally, let α ≥ 0, and let us consider the configuration C. Then, the cost of switching the request d from its initial route R d to its final route R d in configuration C is defined by:

cost(d, C) = e∈A(R d )\A(R d ) (l C (e)) α
If α = 0, we set that x α = 1 if x > 0 and 0 otherwise. The case α = 0 is interesting since the cost is bounded by the optical path length, i.e., by the number of network links on which an intervention is necessary, independently from the load. Note that request d may be not already established in configuration C, in which case A(R d ) is set to ∅.

In the context of routing reconfiguration, we are given two configurations

C init = (R init d ) d∈Π and C f in = (R f in d ) d∈Π where, for any request d ∈ Π, R init d is the initial route of d and R f in d
is its final route. Let us emphasize that we are not considering the problem of computing the new routing, i.e, the initial and final configurations C init and C f in are given as inputs of this problem which "only" consists in ordering the rerouting of every request.

The reconfiguration problem consists in rerouting sequentially the requests from their initial route to their final one, and otherwise. The initial configuration C init is denoted by C ∅ . To simplify the notations, we will note l S (e) (e ∈ A) instead of l C S (e), that is, l S (e) is the number of optical paths using the link e in configuration C S .

We are now able to formally define the reconfiguration problem. Given a network topology D, a set of requests Π, and the initial and final optical routings, the reconfiguration problem is to find an ordering

O = d 1 , d 2 , • • • , d m on the requests that minimizes cost(O) = j≤m cost(d j , C Sj ), where S 1 = ∅ and S j = {d 1 , • • • , d j-1 } for j > 1.

Reconfiguration problem. Inputs

: A digraph D = (V, A), a set of requests Π, two configurations C init and C f in of Π. Output: An ordering O = d 1 , d 2 , • • • , d m of Π such that cost(O) is minimum.
An important remark is that the cost of rerouting a request does not depend on the order in which previous requests have been rerouted, but only on the set S of those requests.

As an example, consider the physical network depicted in Figure 1, where the links are symmetric, together with the initial routing (left) and the final one (right) of three requests. Requests 1, 2 and 3 have initial routes (a, A, D, G, d), (b, C, F, G, e) and (c, F, D, A, B, f ) respectively. Their final routes are (a, A, B, d), (b, C, D, E, e) and (c, F, G, f ) respectively. If Request 1 is switched first, this induces a cost 1 α due to the load of the arc (A, B). Then, if Request 3 is moved, it costs 1 α due to the load of the arc (F, G). Hence, switching the requests in the order 1, 3, 2 would cost 2 • 1 α , while the ordering 2, 3, 1 would have cost 0.

III. COMPLEXITY, BOUNDS AND SIMPLE INSTANCES

In this section, we prove that the routing reconfiguration problem defined in previous section is NP-complete even in the case of basic instances. We then characterize some instances in which the problem can be easily solved. We also provide easily computable upper and lower bounds for the minimum cost of a rerouting. These bounds will allow us to analyze the performances of the heuristics we propose in the next section.

To prove the NP-hardness of the routing reconfiguration problem, we present a reduction from the Minimum Feedback Vertex Set (MFVS) problem. Given a digraph D = (V, A), a feedback vertex set S ⊆ V is a set of vertices the removal of which leaves D acyclic, i.e., the subdigraph D[V \ S] of D induced by V \ S is a Directed Acyclic Graph. The MFVS Problem consists in finding a feedback vertex set with minimum size. This problem is a well known NP-complete problem [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. It is easy to check that it is NP-complete in the class of loopless connected digraph with minimum in-degree at least one (since a vertex with no in-neighbors can be removed without changing the feedback vertex sets).

Theorem 1: The reconfiguration problem is NP-complete even if the physical network has only 2 nodes and α = 0.

Proof: Let D = (V, A) be a loopless n-node m-arc connected digraph with minimum in-degree at least one, which is an instance of the MFVS Problem. From D, we build the following instance of the routing reconfiguration problem.

Let the physical network be the digraph D * = (V * , A * ) with two nodes, V * = {u, v}, and n > 0 arcs from u to v. There is a one-to-one correspondence between the vertices of D and the arcs of D * , i.e.,

A * = V = {a 1 , • • • , a n }. Let Π be a set of m ≥ n requests from u to v.
There is a one-to-one correspondence between the arcs of D and the requests of Π, i.e., Π = A. Note that the path of a route for a request in Π must be an arc in A * . Moreover, for any request d ∈ Π, corresponding to an arc (x, y) ∈ A, the initial route R init Because α = 0, rerouting a request on an empty link does not cost anything and it costs one otherwise. Hence, for any arc a ∈ A, the contribution of the link a to the total cost of a reconfiguration is c(a) -1 if a is empty when the first request with final route a is rerouted, and its contribution is c(a) otherwise. Indeed, after the first request has been rerouted on a, the rerouting of each of the reminding c(a) -1 requests with final route a will cost one. Thus, for any ordering O,

m -n = i≤n (c(a i ) -1) ≤ cost(O) ≤ i≤n c(a i ) = m.
More precisely, we show that the optimal cost of the rerouting equals m -n + M F V S(D), where M F V S(D) denotes the minimum size of a feedback vertex set in D, which proves the NP-hardness. The problem belongs to NP.

Even if the routing reconfiguration problem is NP-complete in general, there exist some instances where it can be solved efficiently. Hereafter, we characterize some cases where the problem is polynomialy-time solvable. In particular, we propose a linear time algorithm for solving the problem optimally on a directed symmetric ring if α = 1. We start by giving some general bounds.

Let (D, Π, C init , C f in ) be an instance of the routing reconfiguration problem. For any arc a ∈ A of D, we denote the number of requests using the link a only in their initial route by I(a), resp., only in their final route by F (a). Let P (a) denote the number of requests using the link a both in their initial and final routes. More formally, In particular, if I(a) = 0 for every a ∈ A , the optimal cost equals the above lower bound and it is achieved by any order of request reroutings. More generally, we give a simple sufficient condition to decide whether the optimal cost matches with the above lower bound. To do so, we give an alternative definition of the dependency digraph of an instance of the routing reconfiguration problem.

• I(a) = |{d ∈ Π : a ∈ A(R init d ) \ A(R f in d )}|; • F (a) = |{d ∈ Π : a ∈ A(R f in d ) \ A(R init d )}|; • P (a) = |{d ∈ Π : a ∈ A(R f in d ) ∩ A(R init d )}|.
The dependency graph D dep of (D, Π,

C init , C f in ) is the digraph defined as follows. The vertex-set of D dep is Π and there is an arc from d ∈ Π to d ∈ Π if (A(R f in d )\A(R init d ))∩ (A(R init d ) \ A(R f in d )) = ∅.
Note that this definition differs from the classical definition [START_REF] Cohen | Tradeoffs when optimizing Lightpaths Reconfiguration in WDM networks[END_REF], [START_REF] Coudert | Rerouting requests in wdm networks[END_REF].

Theorem 2: Let α ≥ 0. If the dependency graph D dep of the reconfiguration instance is acyclic, then every inverse topological ordering of V (D dep ) corresponds to an ordering with cost a∈A P (a)+F (a)-1 i=P (a) i α and therefore is optimal. A directed symmetric ring is a digraph with vertex-set

V = {v 1 = v n+1 , v 2 , • • • , v n } (n ≥ 3
) and for any i ≤ n, there are the arcs (v i , v i+1 ) and (v i+1 , v i ). In such a physical topology, we may assume that, for any request between two nodes, only two routes are possible: clockwise and anti-clockwise.

Theorem 3: Consider an instance of the routing reconfiguration problem where the physical network is a directed symmetric ring. Let us consider the requests that must be switched be ordered in any non-increasing ordering of the length of their initial route. In the case α = 1, this ordering achieves the minimum cost.

IV. HEURISTICS AND SIMULATIONS

As the reconfiguration problem is NP-complete even on very simple physical instances (Theorem 1), we have proposed one heuristic to solve it.

Recall that the routing reconfiguration problem is a scheduling problem that aims at finding a minimum cost ordering of the requests. Therefore, two natural and simple other heuristics have been implemented to evaluate the performance of the heuristic. The Random Schedule (RS) simply returns a random ordering of the requests. Motivated by Theorem 3, we also consider the Decreasing Length Schedule (DLS) that returns any ordering of the requests in the non-increasing ordering of the length of their initial routes.

Next subsection describes the heuristic we propose and then, we will evaluate its behavior through simulations.

A. Heuristic by Local Optimization (HLOf)

Recall that our goal is to go from the initial configuration C init to the final one C f in . For any subset S ⊆ Π, C S denotes the configuration obtained from C init after having rerouted the requests of S.

Roughly speaking, this heuristic is based on a matrix that describes, in the current configuration C S , which requests would be the cheapest one to be switched.

1) Cost Matrix: Given a configuration C S , where

S = {d 1 , • • • , d t-1 } ⊆ Π = {d 1 , • • • , d m }, the corresponding cost matrix M (C S ) is defined as follows: M (C S ) = (M i,j ) t≤i,j≤m where M ij = cost(d j , C S∪{di} ) -cost(d j , C S ) if i = j and M ii = 0
M ij compares the cost of rerouting d j in the current configuration to the cost of rerouting d j knowing that the request d i has already been rerouted (The cost of rerouting d i is not taken into account). Intuitively, if there exists a k ∈ {t, • • • , m} such that, for every ∈ {t, • • • , m}, M k ≤ 0, Then locally (in the current configuration) rerouting the request d k before all the others is the cheapest.

2) Greedy heuristic by matrices: The heuristic we propose starts by computing the matrix M (C ∅ ). Then, one request d k ∈ Π to be rerouted is chosen according to some choice function f (M (C ∅ )) depending only on the matrix. The request d k is then rerouted and the matrix M (C {d k } ) corresponding to the next configuration is computed. Once the requests of the set S ⊂ Π have been rerouted, the request d is rerouted then, with = f (M (C S )), and the matrix M (C S∪{d } ) is computed. In this preliminary work, f (M ) is the row index k such that j≤m M kj is minimum.

3) Case of the linear cost function (α = 1): The complexity of the heuristics depends on the complexity of the choice function (in our case O(m 2 )) and on the complexity of updating the matrix. The definition of the cost matrix makes this latter operation particularly easy in the case α = 1. In this case,

M ij = |A(R f in dj ) ∩ A(R f in di )| -|A(R f in dj ) ∩ A(R init di )
| which is completely independent from the current network configuration. Therefore, for α = 1, only M (C ∅ ) is initially computed and, after rerouting the request d k , the update only consists of the deletion of the row and the column k.

4) Heuristic by local optimization: Given an ordering of the requests, the Heuristic by Local Optimization (HLO) consists in, while it is possible, inverting 2 consecutive requests if it decreases the global cost. More generally, k ≥ 3 being fixed, It is possible to perform local optimization by taking k consecutive requests and choosing the minimum cost among the k! orders. Finally, the heuristic HLOf consists of the following. We first compute an ordering of the requests via the greedy heuristic using matrices described above. Then, starting from the obtained ordering, we use the Local Optimization heuristic (for k = 2) to locally improve the solution. We have considered the two topologies studied in Section III: a directed symmetric ring (10 nodes, 60 requests) and a 2-node network with multi-edges (5 edges, 20 requests). Simulations are performed using the open-source mathematics software Sage [19] and the results are presented in Figure 2. On the abscissa axis, α varies from 0 to 2 with a step of 0.1, and on the ordinate axis, the total cost of the reconfiguration is represented. In both topologies and for each value of α, the depicted cost is the mean value over 100 executions where the set of requests, their initial and final routes have been chosen randomly in every run. We have simulated the heuristic by local optimization going from orders obtained using the heuristic by matrices (HLOf). Then, the obtained solutions are compared with the ones provided by the Random Schedule (RS) heuristic. In the case of the ring, the solution provided by Heuristic HLOf is compared with the ones obtained by the Decreasing Length Schedule (DLS) heuristic. Notice that DLS and RS are equivalent in the case of the second instance since all routes have same length. We compare as well all the results with the general bounds (LB and UB) given in Lemma 1.

The heuristic (HLOf) give results that are close to the lower bound and much better than those corresponding to random orders in both topologies. In Particular, HLOf is identical to DLS in the ring (optimal for α = 1 according to Theorem 3).

V. CONCLUSION

In this work, we present a first theoretical study of the routing reconfiguration problem including physical layer im-pairments. While simple, the cost function we propose allows to capture several constraints due to physical layer impairments as the non-linearity. The preliminary simulations' results indicate that the heuristic HLOf we have proposed achieves good performance on simple instances. Next, we plan to extend the study to more general topologies, and to investigate the challenging problem of determining jointly the best new configuration and the reconfiguration ordering taking into account possible interruptions.

Fig. 1 .

 1 Fig. 1. Example of instance of the reconfiguration problem

  d of d is set to x ∈ A * and its final route R f in d is set to y ∈ A * . By definition, R init d = R f in d for any d ∈ Π (because D is loopless), and, for any a ∈ A * , there is d ∈ Π such that {a} = R f in d (because D has minimum in-degree at least one). Let c(a) denote the number of requests using the link a ∈ A * in the final configuration, i.e., c(a) = |{d ∈ Π : {a} = R f in d }|. Note that c(a) > 0 for any a ∈ A * because any arc is assumed to be the final route of at least one request (because D has minimum in-degree at least one).

  Finally let A ⊆ A be the set of links a s.t F (a) > 0. The following bounds are straightforward. Abusing the notation, we consider that y i=x i α = 0 if y < x. Lemma 1: For any α ≥ 0 and any rerouting ordering O, a∈A P (a)+F (a)-1 i=P (a) i α ≤ cost(O) ≤ a∈A P (a)+I(a)+F (a)-1 i=P (a)+I(a) i α .

Fig. 2 .

 2 Fig. 2. Results on directed symmetric ring (up) and 2-node network (down)

ACKNOWLEDGMENT

The authors would like to thanks Daniel C. Kilper for fruitful discussions, and acknowledge the financial support of ANR DIMAGREEN and Région PACA.