Hugues Chaté

John Toner

Julien Tailleur

Alexandre Solon

Susceptibility of Polar Flocks to Spatial Anisotropy

come   L'archive ouverte pluridisciplinaire

Active matter, being made of energy-consuming units, is well known to exhibit spectacular collective behaviors not permitted in equilibrium. Experimental examples include the defect dynamics of active nematics [1][2][3], low Reynolds number turbulence [4,5], motility-induced phase separation [6][7][8] and, perhaps most famously, flocking [9][10][11][12][13]. Although these phenomena appear in complex, usually living, systems, most of our theoretical understanding comes from studying collections of identical active units evolving in pristine environments, often with periodic boundary conditions. Recently acquired evidence suggests, though, that active systems seem to be fundamentally sensitive to quenched and population disorder [14][15][16][17][18][19][20], and that even the nature of boundaries can influence bulk properties [21].

The sensitivity of active systems to anisotropy, in the form of fixed preferred directions in space, remains largely unexplored. A basic result is available in the context of polar flocks, i.e. collections of simple selfpropelled particles locally aligning their velocities. In two space dimensions, comparing the Vicsek model (VM) [22] to the active Ising model (AIM) [23] shows that the symmetry of the order parameter controls the emerging physics. In the VM, dynamics are rotation invariant, i.e., have continuous symmetry, and the ordered phase exhibits scale-free density and order fluctuations [24][25][26][27][28]. In the AIM, directed motion happens only along two opposite directions, hence the dynamics only has a discrete symmetry, and the correlations are short ranged in the ordered phase. Concomitantly, even though the transition to collective motion is akin to a phase-separation scenario in both the AIM and the VM, their coexistence phases are different [29]: models in the Vicsek class exhibit microphase separation, typically in the form of a smectic train of traveling dense bands [30], whereas the AIM shows a single moving domain and macrophase separation [31].

Anisotropy is generically expected in experimental systems, due to weak external fields. The AIM, by restricting directed motion along one dimension, corresponds to an extreme spatial anisotropy, whose relevance for realistic systems can be questioned. A natural question is then whether polar flocks and the physics of the Vicsek model are robust to weaker forms of anisotropy. In equilibrium, the 2D XY model-which is the passive counterpart of the VM-is in a sense both robust and sensitive to the discreteness of spins: q-state clock models, which break rotational invariance and interpolate between the XY and the Ising models, exhibit a quasi-long-range ordered phase similar to that of the XY model below the BKT transition for q > 4, but this critical phase gives way to a region of long-range order below some finite temperature that vanishes only when q → ∞ [32][33][34][35][36]. Thus, from the XY viewpoint, a new ordered phase emerges at any q, but it is marginal, confined to T = 0, in the q → ∞ limit.

In this Letter, we investigate the susceptibility of polar flocks to weak anisotropy. Using a combination of numerical simulations and analytical arguments, we study q-state active clock models and their hydrodynamic theories. We uncover a scenario qualitatively different from the equilibrium one: the phenomenology of the rotationally invariant Vicsek model disappears for any amount of spin anisotropy, leaving only AIM-like phenomenology with short-ranged correlations and macrophase separation. This, however, happens only asymptotically: at fixed q, one still observes the Vicsek physics up to a typical scale ξ q that diverges exponentially with q, which we estimate using a mean-field theory and a scaling argument. The latter traces back the fundamental difference with equilibrium to the presence of long-range order in the isotropic active system. Active clock models. Particles i = 1, . . . , N carrying a spin s i ∈ {0, 1, . . . , q -1} reside at the nodes R of a square lattice without occupation constraints. They undergo biased diffusion by jumping to neighboring sites with rate D(1 + εd • u i ) with d the direction of the jump and u i = (cos θ i , sin θ i ) the unit vector along the clock angle θ i = 2πs i /q. Spins can rotate to the previous or next "hour"

θ i ≡ θ i ± 2π q at rate w i,R = w 0 exp β 2ρ R m R • (u i -u i ) (1)
where ρ R and m R = j∈R u j are, respectively the number of particles and the magnetization at site R hosting particle i, u i is the new spin direction, and w 0 is a constant [37]. For q = 2, one recovers the AIM used in [31].

As shown in [38], in the isotropic q → ∞ limit, the spin dynamics reduces to the Langevin equation

∂ t θ i = Ω ∞ + 2D ∞ ξ i (2)
where ξ i is a Gaussian white noise of unit variance and the torque and rotational diffusivity are given by

Ω ∞ = 4w0π 2 β q 2 m R ρ R • ∂ui ∂θi + O(q -3 ) and D ∞ = 4w0π 2 q 2
+ O(q -3 ), respectively. In order to have a well-behaved active XY model in the q → ∞ limit, one must thus take w 0 ∝ q 2 . In the following, we set w 0 = q 2 4π 2 to fix D ∞ = 1 and choose D = 1 without loss of generality. For simplicity, we also fix the activity parameter ε = 0.9. [START_REF]For the AIM, the same phenomenology is found for any activity ε > 0[END_REF] The only parameters left to vary, in addition to q, are thus the temperature T = 1/β and the global density ρ 0 = N/(L x L y ), where L x and L y define a rectangular domain with periodic boundary conditions. For numerical efficiency, we use parallel updating, first performing on-site spin rotations, then biased jumps.

Phase diagrams in the (ρ 0 , T ) plane at fixed q all resemble those of the AIM or VM: the disordered gas present at high T and/or low ρ 0 is separated from the low-T /high-ρ 0 polarly-ordered liquid by a coexistence phase (Fig. 1a). The liquid and coexistence phases both have a finite global magnetization m ≡ | m R R |. However, at fixed system size, they display AIM-like or VM-like properties depending on q: For large q, one observes giant number fluctuations in the polar liquid and microphase separation, as for the Vicsek model (Fig. 1c,d). At lower q values, on the contrary, the liquid has normal fluctuations and the system phase separates into a single moving domain (Fig. 1b,d). The direction of global order Φ ≡ arg m R R also behaves differently in the liquid phase, hence distinguishing AIM-like and VM-like behaviors: Φ(t) wanders slowly at large q, whereas it is pinned along a clock angle at small q (Fig. 1e). The results presented in Fig. 1 seem to suggest that active clock models have different behavior at q = 4 and q = 10, similar to the differences between the AIM and the VM. In fact this is only true at finite size, as we now show in both the liquid and phase-separated phases.

We first consider the behavior of correlation func- q = 4 q = 5 q = 6 q = 7 q = 8 q = 9 fit

(k) = m ⊥ (k)m ⊥ (-k) vs k = (k , 0) for q ∈ 4, 9 .
For q = 7 we show the fit to the Ornstein-Zernicke function α/(1 + (ξk) 2 ), (dashed line). (b) Crossover length ξq. For red and blue symbols, ξq is obtained by Ornstein-Zernicke fits of S ⊥ (k) using k = (k , 0) and k = (0, k ⊥ ), respectively. The green curve is the meanfield prediction derived from Eq. ( 5). The black line corresponds to L c⊥ (q), predicted by our scaling argument fitting only the prefactor a in Eq. ( 9). tions in the liquid phase. In Fig. 2a, we show the transverse magnetization structure factor S ⊥ (k) = m ⊥ (k)m ⊥ (-k) for wavelength k calculated in large systems for various q values (the same behavior is observed for the structure factor of the density field). For sufficiently small q, S ⊥ converges to finite values as k → 0. This AIM-like behavior only happens, though, beyond a crossover length scale ξ q . For scales smaller than ξ q , the structure factor exhibits algebraic scaling, as in the VM. The crossover scale ξ q can be extracted by fitting the structure factors to the Ornstein-Zernicke function f (k) = α/(1 + (ξ q k) 2 ) [40]. This yields a typical scale ξ q that increases exponentially rapidly with q (Fig. 2b). Extrapolating these results, we expect that, even for large q values, VM behavior will be observed in the liquid phase up to (large) finite sizes, but that the asymptotic behavior at the largest length scales is Isinglike. Consistently, we observe a transition from unpinned to pinned order parameter in the liquid phase as L increases at fixed q (Fig. 3a).

Importantly, the crossover from VM to AIM phenomenology is also observed the phase-coexistence region. Systems with linear size L ξ q exhibit microphase separation, as in the VM. On the contrary, for L ξ q , the systems show full phase separation as in the AIM. Fig. 3b illustrates this: the transition from microphase to macrophase separation happens upon increasing the transverse system size at fixed q, whereas the reverse transition is seen upon increasing q at fixed system size.

The crossover from VM to AIM behavior can be summarized in the (q, T ) phase diagram at fixed global density. The three expected phases are present, but one can, at a given system size, define boundaries between Ising and Vicsek behavior within the coexistence and the liquid-phase regions, as shown in Fig. 3c and described in its caption. These boundary lines are displaced to higher and higher q values as the system size is increased. Extrapolating to the infinite-size limit, VM-like behavior is singular, confined to the infinite-q (active XY) limit. Note that the transitions in the coexistence and liquid phases happen at different system sizes in Fig. 3c. We believe this to be due to the peculiar and poorly understood mechanism by which the Vicsek-type long-range correlated fluctuations break the phase separation into a microphase separation [29]. This need not happen at the same system size as the pinning of the order parameter in the liquid although the underlying physics -a cross-over from Ising-like to Vicsek-like physics-is the same.

Effective continuous description. In equilibrium, clock models are sometimes described at the field-theoretical level as continuous spins subjected to an anisotropic potential V q (φ) [32], where φ parameterizes the local rection of order. While usually postulated on symmetry grounds, we have derived this potential at large q using a mean-field approximation [38], which yields

V q (φ) = - 2ρ β I q (β|m|/ρ) I 0 (β|m|/ρ) cos(qφ) (3)
with m and ρ the local magnetization and density, φ = arg(m), and I n the modified Bessel function of the first kind. Equation ( 3) is only the leading order conat large q, but direct comparisons with simulations of the fully connected clock model show that it is already a good approximation for q = 4 [38].

We now demonstrate that we can understand the behavior of our microscopic active clock model using the mean-field hydrodynamic description of its isotropic, q = ∞ limit complemented by the anisotropic potential (3). This hydrodynamic theory, derived in [38] with standard techniques akin to those used for the AIM [31], reads

∂ t ρ =D∆ρ -v∇ • m (4a) ∂ t m = β 2 -1-β 2 8ρ 2 m 2 m + D∆m -β ρ ∂ φ V q (φ) m ⊥ + βv 4ρ (m ⊥ ∇ • m ⊥ -m∇ • m) -v 2 ∇ρ , (4b)
where m ⊥ ≡ (-m y , m x ). q = 4 q = 5 q = 6 q = 7 q = 8 q = 9 Consider a perturbation of the homogeneous ordered state m = (m 0 + δm , δm ⊥ ). To linear order, using sin qφ ≈ qφ ≈ qm ⊥ /m , we obtain for the m ⊥ field

δm ⊥ = D∆δm ⊥ + {drift terms} -α q δm ⊥ (5)
with α q = 2q 2 Iq(βm0/ρ0) I0(βm0/ρ0) . When α q = 0, there is no mass on m ⊥ . This happens happens when q → ∞, as expected from the continuous rotational symmetry. With α q > 0 however, a mass damps the fluctuations of m ⊥ and therefore pins the direction of order. The typical length scale on which this damping occurs is ξ = D/α q , which compares well to the crossover length ξ q measured in the microscopic model (Fig. 2b) albeit-unsurprisingly-not quantitatively. To account for the structure factor reported in Fig. 2 for the microscopic model, we complement Eq. (4b) with an isotropic centered Gaussian white noise field η(r, t) of unit variance. The structure factor of m ⊥ , shown in Fig. 4a, is found to be qualitatively similar to that of Fig. 2. Moreover a pinning transition occurs when L is increased (Fig. 4b), as in Fig. 3a for the microscopic models.

Our hydrodynamic description also captures the nature of the coexistence region. Complementing Eq. (4b) with the density-dependent coefficients needed to account for inhomogeneous profiles [38], we show in Fig. 4c that increasing q at a given system size leads from macro-to micro-phase separation whereas the converse happens when increasing L at fixed q. Again, the VM phenomenology is observed at large q and small sizes, whereas AIM physics is found to be the asymptotic behaviour at large L.

Scaling argument. All in all, anisotropy is thus always relevant asymptotically. This is markedly different from what happens in equilibrium where, for q > 4, there is a range of temperature over which the anisotropy is irrelevant asymptotically, and one observes quasi-long-range order, as for a continuous spin. The argument used to derive a crossover length from the linearized hydrodynamic equation in Eq. ( 5) therefore fails in equilibrium. Indeed, there is no homogeneous ordered state to perturb from, only a quasi-ordered state with algebraically decaying correlations. This difference is essential, as is clear from looking at the scaling with system size of the energy H q = d 2 r cos(qθ(r)) due to the "clock potential".

Let us then compare the scaling with L of H q 0 , where the average is taken in the unperturbed system without H q , in equilibrium and in the active case. Of course, we do not actually have a Hamiltonian in this last case, but this argument should roughly capture the effect of the potential in the equation of motion (4). In equilibrium, the unperturbed state can be described by the spinwave Hamiltonian H 0 = d 2 r K 2 [∇θ(r)] 2 with stiffness K. The perturbation is then evaluated as

H q 0 ≈ d 2 r e iqθ(r) 0 = d 2 re -q 2 2 G(0) (6)
where G is the Green function of the Laplacian in infinite space. In Fourier space Ĝ(k) = T Kk 2 , which, in 2D, gives G(0) = T log(L/Λ)/(2πK) for a system of size L, with Λ a short distance cut-off. Inserting this into Eq. ( 6) yields

H q 0 ∼ L 2-q 2 T 4πK . (7)
Equation ( 7) predicts anisotropy to be relevant as L → ∞ whenever T < T q ≡ 8πK q 2 and irrelevant otherwise. If T q < T BKT ≡ πK 4 , which happens for q > q c = 4, one observes a quasi-long range ordered phase where anisotropy is irrelevant for T q < T < T BKT , and a long-range ordered phase where anisotropy is relevant for T < T q .

In the active case, the ordered state of the unperturbed system is long-range ordered. Assuming that θ(r) shows Gaussian fluctuations with variance σ 2 around its mean value θ 0 leads to e iqθ(r) 0 = e -q 2 σ 2 /2 . In turn, Eq. ( 6) becomes

H q active 0 ≈ d 2 r e iqθ(r) 0 = L 2 e -q 2 σ 2 /2 (8)
Anisotropy is thus always relevant when L L q ≡ e q 2 σ 2 /4 , so that H q active 0 1. For L L q , on the contrary, anisotropy is exponentially suppressed by q and Vicsek physics may be observed.

The argument above qualitatively explains the different responses to anisotropy observed in the active and passive cases. In equilibrium, it has been made more rigorous using renormalization group calculations [32,33]. In the active case, its essential conclusions hold within a dynamical renormalization group analysis [24,27] which shows that the lengthscale L c⊥ beyond which the symmetry-breaking field changes the physics obeys [START_REF] Solon | [END_REF] L c⊥ (q, σ) = a exp q 2 σ 2 /(2z) .

(

) 9
where a is a microscopic length and z a dynamic exponent whose most recent numerical estimate is z 1.33 [28]. After measuring σ in a microscopic simulation [START_REF]We measure σ in the active XY model (i.e. with q = ∞) by fitting the distribution P (θ R -θ ) with θ R the local orientation on site R to a normal distribution[END_REF], we show in Fig. 2b that the prediction of Eq. ( 9) is consistent with the observed crossover length.

Conclusion. We have shown that polar flocks are strongly altered, at large scales, by spatial anisotropy. This is reflected by the suppression of hallmark features of the Vicsek model: in the liquid phase the correlations are short ranged, not scale free, the direction of order is pinned, not wandering; and one has macrophase instead of microphase separation at coexistence. Interestingly, these changes occur only beyond a characteristic lengthscale that diverges for vanishingly small anisotropy and large q. In the liquid and coexistence regions, the crossover from VM to AIM physics can be understood using a hydrodynamic description where anisotropy is accounted for by an effective potential. In the liquid phase, the difference with the passive case can be explained using a scaling argument, which shows that the presence of long-range order is sufficient to render the anisotropy relevant asymptotically for any value of q and T .

Our study calls for understanding spatial anisotropy in other active-matter systems, like active nematics. Finally, the absence of any effect of the anisotropy of the lattice used in our clock model -our results hold for an off-lattice version-is almost surprising. Whether lattice anisotropy couples to the aligning dynamics at larger scales than those considered here surely deserves further study.

10 FIG. 1 .

 101 FIG. 1. (a) Typical phase diagram in the (ρ0, T ) plane (q = 4), Transition lines are defined by the coexisting densities at a given temperature T = 1/β, computed in systems of size 400 × 20). (b,c): Snapshots of density field in the coexistence phase in a long 800 × 20 system suitable for the observation of many traveling bands (steady state, ρ0 = 10, q = 4 in (b), q = 10 in (c)). (d) Number fluctuations n 2 c vs n = ρ0 2 , the number of particles in a square box of linear size calculated in the liquid phase of square 200 × 200 systems (ρ0 = 10, β = 3.5). "Giant" anomalous fluctuations are observed for q = 10, but not for q = 4. (e) Time series of Φ ≡ arg m k k , the orientation of the global polar order (parameters as in (d)).

FIG. 2 .

 2 FIG.2. Liquid phase of clock models (ρ0 = 5.5, β 4, system size 800 × 800): (a) S ⊥ (k) = m ⊥ (k)m ⊥ (-k) vs k = (k , 0) for q ∈ 4, 9 . For q = 7 we show the fit to the Ornstein-Zernicke function α/(1 + (ξk) 2 ), (dashed line). (b) Crossover length ξq. For red and blue symbols, ξq is obtained by Ornstein-Zernicke fits of S ⊥ (k) using k = (k , 0) and k = (0, k ⊥ ), respectively. The green curve is the meanfield prediction derived from Eq. (5). The black line corresponds to L c⊥ (q), predicted by our scaling argument fitting only the prefactor a in Eq. (9).

2 FIG. 3 .

 23 FIG. 3. Transition from the Vicsek to the active Ising behavior as system size increases. (a): Direction of global order in the liquid phase showing a transition between unpinned and pinned as system size increases. The dashed lines indicate the hours of the clock. β = 4, ρ0 = 5.5, q = 8. (b): Snapshots of the density obtained after a long time t = 5 × 10 5 starting from a large ordered band. The transition is shifted to larger q as L increases. Same color code as in Fig. 1. β = 3.2, ρ0 = 5.5. (c): Phase diagram in the q -T plane at ρ0 = 5.5. The line between macro-(G + LI ) and micro-phase separation (G + LV ) is defined as the transition between a single and multiple bands after time t = 10 6 at the system size indicated in the legend. The line separating the two liquids (LI and LV ) is defined as the transition between pinned and unpinned order parameter orientation after time t = 10 5 .

1200 × 20 , q = 6 1200 7 FIG. 4 .

 20674 FIG. 4. Simulations of the PDE with noise (a) Structure factor S ⊥ (k) = m ⊥ (k)m ⊥ (-k) vs k = (k , 0) in the ordered phase for several q values (system size 200 × 200). (b) Time series of the orientation of global order Φ in the ordered phase showing a transition between unpinned and pinned dynamics as the system size increases (q = 9). (c) Simulations with the additional density-dependent term necessary to observe band solutions [38]. As in Fig. 3 (b), snapshots of the density after a long time t = 5 × 10 5 starting from a large ordered band. Parameters: β = 4, D = 1, v = 1.8, ρ0 = 5.5 (a,b) and ρ0 = 1.85 (c).

We thank Mourtaza Kourbane-Houssene for his early involvement in this work, and Benoît Mahault for a critical reading of the manuscript. This work was partially supported by the French ANR through projects NeqFluids to HC and THEMA to JT.


Roland Godet
email: rgodet@laas.fr

Arthur Bit-Monnot
email: abitmonnot@laas.fr

Chronicles for Representing Hierarchical Planning Problems with Time

In temporal planning, chronicles can be used to represent the predictive model of durative actions. Unlike the classical state-oriented representation, the usage of chronicles allows a rich temporal qualification of conditions and effects, beyond the mere start and end times of an action. In this paper we propose an extension of the standard chronicle representation to support hierarchical problems. In particular, we show that the addition of temporally qualified subtasks to chronicles makes them suitable to represent not only primitive actions but also HTN methods. We show how the set of solutions to a chronicle-based hierarchical problem can be quite naturally represented as a Constraint Satisfaction Problem (CSP). To associate semantics to this extended chronicle representation, we propose a set of rules that must hold for any solution to the hierarchical problem, specified as constraints on the associated CSP.

Introduction

In Artificial Intelligence, planning with Hierarchical Task Networks (HTNs) is an approach to automated planning where actions are hierarchically structured [START_REF] Erol | HTN planning: Complexity and Expressivity[END_REF][START_REF] Höller | HDDL: An Extension to PDDL for Expressing Hierarchical Planning Problems[END_REF] with compound tasks, which can be broken down into subtasks. This hierarchy of tasks allows the planning problem to be described at several levels, starting with more abstract tasks and ending with directly applicable primitive tasks.

In its simplest expression, an HTN [START_REF] Erol | HTN planning: Complexity and Expressivity[END_REF][START_REF] Höller | HDDL: An Extension to PDDL for Expressing Hierarchical Planning Problems[END_REF]) planning problem consists of (i) an initial state, (ii) an initial task network describing the aim, (iii) a set of actions, (iv) a set of compound tasks, and (v) a set of methods.

A state defines the values of a set of state variables, each describing a specific attribute of the environment (e.g. the position of a truck).

A task network is a set of tasks and constraints. Each task describes a particular operation to be fulfilled (e.g. bring a package from A to B). It is composed of its name and a list of parameters, which may be variables or constants. There are two kinds of tasks: the actions (or primitive tasks), which can be directly executed, and the compound tasks, that the planner must refine into actions. The constraints might, e.g., restrict the value of some variables or the order of tasks.

An action consists of (i) a set of conditions over state variables, they characterize the set of states in which the action is applicable, and (ii) a set of effects on state variables, that update the state to reflect the consequences of the action.

A method is a pair m = (t c , tn), where t c is a compound task and tn is a task network. It represents the fact that one way to perform t c is to execute the tasks laid out in tn.

Given an initial state s 0 , an initial task network tn, a set of actions, and a set of methods, a plan is a sequence of actions a 1 , ..., a n . To produce a plan, a planner must systematically replace any compound task in the initial task network by the subtasks of a compatible method, repeating the process until only primitive tasks remain. Along with ordering, this approach defines the set of candidate plans as the ones that can be decomposed from the initial task network. A candidate plan is a solution of the planning problem if the corresponding action sequence is applicable in the initial state.

Approach Rather than this state-oriented view, another representation for planning follows a time-oriented view, as proposed with chronicles [START_REF] Ghallab | Automated Planning: Theory and Practice[END_REF]Bit-Monnot 2018) or timelines [START_REF] Smith | Bridging the gap between planning and scheduling[END_REF]. Several works have considered the introduction of hierarchies for time-oriented planners, notably FAPE [START_REF] Bit-Monnot | FAPE: a Constraint-based Planner for Generative and Hierarchical Temporal Planning[END_REF] and CHIMP [START_REF] Stock | Hierarchical Hybrid Planning in a Mobile Service Robot[END_REF]. The ANML language is also a very relevant proposal, but lacks clearly defined semantics [START_REF] Smith | The ANML Language[END_REF].

In this paper, we introduce hierarchical chronicles, an extension of the chronicles proposed by Bit-Monnot (2018) for generative planning. This is done by associating a chronicle with the task it achieves as well as the subtasks it requires. We show this to be sufficient for chronicles to represent HTN methods, in addition to HTN actions.

While conceptually simple, our formalization of the resulting problem as a CSP allows for advanced temporal features (e.g. intermediate conditions and effects) and closely relates to the time-oriented representation of scheduling problems which we hope will facilitate the application of scheduling techniques to hierarchical planning.

Hierarchical Chronicles

A type is defined by a set of values. It can be either a set of domain constants (e.g. the type Truck = { R 1 , R 2 } defines two truck objects R 1 and R 2 ) or a discrete set of numeric values. A type of particular interest for this formalization is the set of timepoints that we assume to be a discrete set of evenly spaced numeric values representing absolute times at which events can occur.1 A decision variable is related to a type which defines its initial domain (i.e. possible values).

A state variable describes the progression of a specific attribute of the environment over time. It is generally parameterized by one or multiple domain objects. For instance loc(R 1 ) denotes the evolution of the position of the truck R 1 over time. A state variable expression is often parameterized by variables, in which case the particular state variable it refers to depends on the value taken by its parameters, e.g., loc(r) will correspond to loc(R 1 ) or loc(R 2 ) depending on the value taken by the variable r of type Truck.

A task denotes a particular operation to be fulfilled in the environment over time. It is generally parameterized by one or multiple domain objects. For instance [5, 10]Go(R 1 , L 1 ) denotes the operation of moving the truck R 1 to the location L 1 over the temporal interval [5,10]. A task might be parameterized by variables, in which case the particular task it refers to depends on the value taken by its parameters.

A chronicle can be thought of as defining the requirements of a process in the planning problem, and in particular the process of executing an action or carrying out a method. A chronicle is a tuple C = (V, τ, X, C, E, S) where:

• V is a set of variables appearing in the chronicle, partitioned into a set of temporal variables V T whose domains are timepoints and a set of non-temporal variables V O . A planning problem defines a set of chronicle templates T where each template can be instantiated into a chronicle instance by substituting all variables in the template with fresh variables. We typically consider two types of chronicles templates: action chronicles that have effects but no subtasks, and method chronicles with subtasks but no effects.

Considering a method template Deliver ∈ T that delivers a package p from a position l s to a position l e with a truck r, it can be instantiated as the method chronicle C 1 Deliver where: • τ = [t s , t e ]Deliver(p, l e ), i.e., this chronicle should result in delivering the package p to l e over the temporal interval

[t s , t e ]. • C = { [t s , t s ]loc(p) = l s , [t s , t s ]loc(r) = l s }, i.e., the
package p and the truck r have to be at the starting location l s at the beginning of the method.

• E = ∅, this is a method chronicle, with no direct effects. • S = { [t L s , t L e ] Load(p, r), [t M s , t M e ] Move(r, l s , l e ), [t U s , t U e ]
Unload(p, r) }, i.e., to achieve this delivery action, the following tasks have to be done: loading the package in the truck, moving the truck from l s to l e , and unloading the package.

• V O = { p, r, l s , l e } are the parameters of the method (package, truck, start and end location) and

V T = { t s , t e , t L s , t L e , t M s , t M e , t U s , t U e }
where t s , t e are timepoints representing the start and the end of the method (from τ ), and t L s , . . . , t U e are the corresponding start/end of subtasks. • X = { t e ≤ t s + 10, l s = l e , t L e ≤ t M s , . . . }, e.g., impose that the method should take no more than 10 units of time, the two locations must be different and the Move subtask has to be executed after the Load subtask. Considering the action template Move ∈ T that moves a truck r from l s to l e , it can be instantiated as a chronicle C Move with the following effects: E = { [t s , t e ]loc(r) ← l e }, i.e., the truck r will be at the ending location l e at the end of the action, but its position is unknown during the action execution. This chronicle C Move achieves the eponymous task [t s , t e ]Move(r, l s , l e ).

We distinguish an initial chronicle C 0 encoding the initial state as effects and the objectives of the planning problem as conditions and subtasks. It might also specify the anticipated evolution of the environment outside the planner's control, e.g., that a bus will pass at 6pm. This chronicle is the only one not associated to a meaningful task τ . For instance, the problem where the package P 1 is initially in location L 0 and must be brought to location L 1 or L 2 before time 50, can be described by the following initial chronicle C 0 :

•

V O = { l }, V T = { t s , t e } • X = { t < 50, l = L 1 ∨ l = L 2 }, constraints restricting the solution set. • C = { [t e , t e ]loc(R 1 ) = l }, specifying the goals. • E = { [0, 0]loc(P 1 ) ← L 0 , [0, 0]loc(R 1 ) ← L 0 }, effects
specifying the initial state.

C 0 t 1 t 2 m 1 2 m 1 1 m 2 1 m 2 2
Figure 1: Decomposition graph resulting from the expansion of two tasks t 1 : t(x) and t 2 : t(y)

• S = { [t s , t e ]Deliver(P 1 , l) }, subtasks specifying specific tasks to be achieved by a solution plan.

A planning problem is the association (C 0 , T ) of an initial chronicle, defining the initial state and objectives, with a set of chronicle templates which can be instantiated, defining usable actions and methods.

Planning Problem as a CSP Problem Instantiation

At this point we have defined the initial chronicle (representing the problem) and a set of chronicle templates (representing possible actions and methods). We now introduce the procedure to build a set of chronicle instances Π that can be used to represent a solution.

We initially set Π = { C 0 }, i.e., limited to the initial chronicle. Suppose the initial chronicle C 0 contains two subtasks t 1 : t(x) and t 2 : t(y) and that the task t(•) can be achieved by one of two methods m 1 and m 2 (i.e. the task of m 1 /m 2 are of the form [•, •]t(•)). As the first task t 1 might be achieved by either m 1 or m 2 , we add two fresh instantiations m 1 1 and m 1 2 to Π. We record the motivation for the introduction of both chronicles in a lookup-table decomposes(m 1 1 ) ← t 1 and decomposes(m 1 2 ) ← t 1 . Similarly, we introduce two distinct chronicle instances m 2 1 and m 2 2 to represent the possible refinements of t 2 . This process can be seen as creating a decomposition graph such as the one in Figure 1.

We refer to this process as chronicle expansion. More formally, for each subtask t of a chronicle instance C ∈ Π, and each chronicle template T i ∈ T whose task is unifiable with t, we instantiate a new chronicle instance T k i and add it to Π. Each instantiated chronicle is uniquely associated to the task it was introduced to decompose with the decomposes lookup table, effectively defining a decomposition tree. Any chronicle instance added to Π as a result of expansion will need to be expanded itself, making this a recursive process. In the case of cyclic HTN problems, the depth of resulting decomposition tree might not be bounded. For practical purpose -e.g. to encode the problem in a CSP solver -one might decide to bound the depth of the tree to obtain a finite number of chronicles.

Of course, it is not the case that each chronicle instance will be part of the solution plan. In Figure 1,the m 1 1 and m 2 1 chronicle instances are mutually exclusive as only one method can be used to decompose the t 1 task. To capture this fact, we associate each a chronicle instance C ∈ Π to a boolean variable present (C) that is true ( ) if C is present in the solution plan and false (⊥) otherwise. Note that the initial chronicle must always be present, so present (C 0 ) is always true.

With this process, we have created a set of chronicle instances Π, representing all possible methods and actions that might appear in the plan. Each such chronicle instance C ∈ Π is associated with a boolean variable present (C) that represents whether it is part of a solution, and a task decomposes(C) that it might decompose. We now ought to define what are the constraints that must hold for this set of optional chronicle instances to form a solution to the original planning problem. Before doing so, we introduce a synthetic representation for conditions, effects and tasks that will allow us to specify their behavior independently of the context in which they appear.

Core structures

Considering a planning problem Π, the core structures to express the constraints it must fulfill are described here. Token Characteristics Effect tokens here address the evolution of state variables over time. Each (present) effect token forces another value to its state variable, which is compelled to be maintained within a given temporal interval, thus encoding the state evolution. Condition tokens put requirements on the state evolution by imposing a state variable to have a given value over a temporal interval.

Condition Token

Each token (condition, effect, and task) is present in the solution plan if and only if its associated chronicle instance is present in the solution plan. Given a token (condition, effect, or task) ω from a chronicle instance C ∈ Π, we have present (ω) = present (C).

Constraints

Considering a planning problem Π, the constraints used to encode the consistency of a plan are described here.2

Coherence Constraint A state variable cannot take several values at the same time. This implies that for two distinct effect tokens ε and ε in E Π to be coherent, they may not concurrently impose a value or transition to the same state variable.

Given ε = p : [s, e, t]var(p 1 , . . . , p n ) ← v ∈ E Π ε = p : [s , e , t ]var(p 1 , . . . , p n ) ← v ∈ E Π the constraint coherent (ε, ε ) is defined as: p ∧ p =⇒ t ≤ s ∨ t ≤ s ∨ p 1 = p 1 ∨ • • • ∨ p n = p n
By forcing two effect tokens to be non overlapping (over the presence p, time [s, t] and the state variable var(p 1 , . . . , p n ) dimensions), this constraint ensures that a state variable will be given at most one value at any timepoint.

Support Constraint A condition token β ∈ C Π is said supported by an effect token ε ∈ E Π if this effect establishes the value required by β and this value persists for the span of β.

Given β = p : [s, e]var(p 1 , . . . , p n ) = v ∈ C Π ε = p : [s , e , t ]var(p 1 , . . . , p n ) ← v ∈ E Π the constraint supported-by (β, ε ) is defined by: p ∧ e ≤ s ∧ e ≤ t ∧ p 1 = p 1 ∧ • • • ∧ p n = p n ∧ v = v A condition token β ∈ C Π is said supported if it
is supported by at least one effect token in E Π . More formally, the constraint supported (β) is defined by:

present (β) =⇒ ε∈EΠ supported-by (β, ε) Refinement Constraint A task token γ ∈ Γ Π is said re- fined by a chronicle instance C ∈ Π if (i)
C was introduced as a potential decomposition of γ, (ii) it is part of the solution and (iii) the task it achieves is identical to the one of γ.

Given γ = p : [s, e]task(x 1 , . . . , x n ) ∈ Γ Π and C ∈ Π whose achieved task is of the form, task(C) = [s , e ]task(x 1 , . . . , x n ) the constraint refined-by (γ, C) is defined by: p ∧ decomposes(C) = id(γ) ∧ s = s ∧ e = e ∧ x 1 = x 1 ∧ • • • ∧ x n =
x n where id(γ) uniquely identifies the task associated to γ.

A task token γ ∈ Γ Π is said refined if it is refined by a chronicle instance in Π. More formally, the constraint refined (γ) is defined by:

present (γ) =⇒ C∈ΓΠ refined-by (γ, C)
Motivation constraint For an HTN problem it is normally the case that a method or action is only allowed to be part of the solution if it derives from the initial task network. In a sense, it means that the presence of a chronicle must be motivated by the achievement of a task higher up in the hierarchy.

Consider a chronicle instance C ∈ Π that was introduced to decompose a task γ (i.e. decomposes(C) = id(γ)). Then the motivated (C) constraint is expressed as:

present (C) =⇒ present (γ) ∧ refined-by (γ, C) C ∈siblings(C) ¬present (C )
where siblings(C) is the set of all other chronicle instances C that were introduced as a potential decomposition of the same task γ. This constraint effectively enforces that, if present, a chronicle instance uniquely achieves a task higherup in the hierarchy.

Internal Chronicle Consistency Considering a chronicle C ∈ Π, all its constraints X must be verified if C is part of the solution. It is represented by the constraint consistent (C):

present (C) =⇒ x∈X x
Any requirement regarding a chronicle structure should be explicitly or implicitly encoded in the set X of chronicle constraints. In particular, a common requirement for hierarchical problems is that a method spans exactly the same time interval as its subtasks, i.e., that for any method chronicle C with a non-empty set of subtasks subtasks(C): Formulation as a CSP Finally, a planning problem Π can be encoded as a CSP with variables V Π and constraints X Π where:

V Π = { V | (V, τ, X, C, E, S) ∈ Π } ∪ { present (C) | C ∈ Π } X Π = { coherent (ε, ε ) | (ε, ε ) ∈ E 2 Π , ε = ε } ∪ { supported (β) | β ∈ C Π } ∪ { refined (γ) | γ ∈ Γ Π } ∪ { motivated (C) | C ∈ (Π \ { C 0 }) } ∪ { consistent (C) | C ∈ Π }
Solution and Plan Extraction A solution to a hierarchical planning problem Π is an assignment to all variables in V Π that satisfies all constraints in X Π . The decision process involved in building the assignment will effectively impose the presence of methods and actions (through presence variables) as well as their instantiation (through parameter variables) and orderings (through temporal variables). We say that a chronicle C ∈ Π is present in the solution if its presence variable present (C) evaluates to true given the assignment.

From a solution assignment, it is straightforward to extract a solution plan: any action chronicle C ∈ Π present in the solution corresponds to an action in the plan. The value of its parameters as well as start and end times are given by the value of the corresponding variables in the assignment.

Likewise, the assignment encodes a full decomposition from the initial task network into the solution plan as the refinement and motivation constraints ensure that, for any subtask of a chronicle present in the solution, there is exactly one refining chronicle (action or method) present in the solution.

It should be noted that setting the presence variable of a chronicle to false has the same effect as not including it in the set Π of chronicles considered in the CSP. This suggests that bounding the depth of a decomposition tree should be interpreted as a decision restricting the set of solution. To maintain the completeness of a decision procedure, this bound should be reconsidered (i.e. increased) when it is shown that no solution exists within a given depth.

Discussion and Related Work

To the best of our knowledge all existing temporal HTN planners, including FAPE (Bit-Monnot et al. 2020), CHIMP [START_REF] Stock | Hierarchical Hybrid Planning in a Mobile Service Robot[END_REF] and SIADEX [START_REF] Castillo | Temporal Enhancements of an HTN Planner[END_REF], interpret HTN planning as a constructive process: they start from an initial task network that is iteratively expanded into a solution, each expansion bringing its own new subtasks, actions and additional constraints. This proposal adopts a different interpretation of hierarchical planning as a constraint satisfaction problem. While the two interpretations remain compatible, a key feature of the CSP interpretation is its proximity with the representation of scheduling problems. In particular, the notion of optional time intervals in scheduling solvers such as CPOptimizer [START_REF] Laborie | IBM ILOG CP Optimizer for Scheduling[END_REF]) brought many modeling capabilities that have a clear mapping with the structure of HTN problem (e.g. the alternative and span constraints of [START_REF] Laborie | Reasoning with Conditional Time-Intervals[END_REF].

The closest formalism is the one used by FAPE (Bit-Monnot et al. 2020) that supports both hierarchical and generative planning. In FAPE this is allowed by annotating some actions as task-dependent, meaning that they can only be introduced as a refinement of an existing task. Unlike FAPE, this proposal focuses on pure hierarchical (HTN-like) planning allowing to remove this distinction. The addition of explicit temporal variables representing the end of the persistence of an effect is a subtle change that avoids an explicit handling of causal-links and threats (threats being particularly problematic for scalability as they might involve any combination of two effects and one condition, leading to a cubic number of constraints).

The notion of tokens (including the effect persistence) is inspired by the homonymous tokens of timeline-based planners such as Europa [START_REF] Barreiro | EUROPA: A Platform for AI Planning, Scheduling, Constraint Programming, and Optimization[END_REF] or CHIMP [START_REF] Stock | Hierarchical Hybrid Planning in a Mobile Service Robot[END_REF]. Unlike timeline-based planners however, we do maintain a distinction between conditions and effects and use an action-centric formalism.

Several hierarchical planners such as SIADEX [START_REF] Castillo | Temporal Enhancements of an HTN Planner[END_REF] or SHOP2 extensions [START_REF] Goldman | Durative Planning in HTNs[END_REF]) have enabled temporal features in a state-progression setting by timestamping states. Relationships with these state-oriented representations are less obvious as this paper adopts a timeoriented view where the evolution of each state variable is handled independently of the others.

Conclusion

In this paper, we introduced a constraint-based representation for hierarchical planning under temporal constraints. This encoding assumes a time-oriented view and a fully lifted representation. Its foundation on previous chronicle approaches allows leveraging their temporal expressiveness with a very limited increase in complexity.

While the paper is restricted to the discussion of the planning formalism, our current work is focused on the exploitation of this formalism and associated encoding in a constraint-based planner that leverages scheduling techniques.

  Given a chronicle instance C ∈ Π, each condition in C is associated to a condition token: present (C) : [s, e]var(p 1 , . . . , p n ) = v This token states that, if C is present in the solution plan (present (C) = ), then the state variable var(p 1 , . . . , p n ) must have the value v over the temporal interval [s, e]. The set of condition tokens in Π is denoted C Π . Effect Token Given a chronicle instance C ∈ Π, each effect in C is associated to an effect token: present (C) : [s, e, t]var(p 1 , . . . , p n ) ← v Note the new temporal variable t ∈ V T . This token states that, if C is present in the solution plan (present (C) = ), then the state variable var(p 1 , . . . , p n ) is undefined over the temporal interval ]s, e[ and has the value v over the temporal interval [e, t]. The expansion with the new timepoint t allows us to encode a minimal persistence of the effect until a later time t. The set of effect tokens in Π is denoted E Π . Task Token Given a chronicle instance C ∈ Π, each subtask in C is associated to a task token: present (C) : [s, e]task(x 1 , . . . , x n ) This token states that, if C is present in the solution plan (present (C) = ), then the task task(x 1 , . . . , x n ) must be achieved over the temporal interval [s, e]. The set of task tokens in Π is denoted Γ Π .

  method chronicle with no subtasks should be instantaneous (i.e. start(C) = end(C)).

  • τ is the task achieved by the chronicle. It is of the form [s, e]task(x 1 , . . . , x n ) where s and e are temporal variables in V T , task(x 1 , . . . , x n ) is the parameterized task (with each x i ∈ V O ). S is a set of subtasks. Each subtask has the form [t s , t e ]task(x 1 , . . . , x n ) where t s and t e are temporal variables in V T and task(x 1 , . . . , x n ) is a parameterized task (with each x j ∈ V O ). It denotes a required task that must be achieved by another chronicle over [t s , t e ].

	s and e respectively denote the start
	and end instants at which the chronicle is active, and we
	will refer to them as start(C) and end(C) respectively.
	• X is a set of constraints over the variables in V .
	• C is a set of conditions, Each condition is of the form
	[s, e]var(p 1 , . . . , p n ) = v where s and e are variables
	in V T , var(p 1 , . . . , p n ) is a parameterized state variable
	(with each p

i ∈ V O )

and v is a variable in V O . A condition states that the state variable var(p 1 , . . . , p n ) must have the value v over the temporal interval [s, e]. • E is a set of effects. Each effect is in the form of [s, e]var(p 1 , . . . , p n ) ← v where s and e are variables in V T , var(p 1 , . . . , p n ) is a parameterized state variable (with each p i ∈ V O ) and v is a variable in V O . An effect states that the state variable var(p 1 , . . . , p n ) takes the value v at time e. Over the temporal interval ]s, e[, the state variable is transitioning from its previous value to v, and has an undetermined value. •

While this definition assumes a discrete time representation, it could be equally interpreted with a continuous time representation. Also note that discrete time is no less expressive when instantaneous changes are forbidden, as common in temporal planning in general and PDDL in particular (

[START_REF] Cushing | When is Temporal Planning Really Temporal[END_REF]. In general however the computational complexity might differ between a discrete and a continuous time representation.

Note that the coherence and support constraints are identical to the ones ofBit-Monnot (2018) and repeated here for completeness.


L Duquerroy
email: laurence.duquerroy@space.alcatel.fr

S Josset

O Alphand
email: oalphand@laas.fr

P Berthou
email: berthou@laas.fr

T Gayraud
email: gayraud@laas.fr

SatIPSec : an optimized solution for securing multicast and unicast satellite transmissions

In satellite networks, the security of data exchanged on the satellite segment is threatened by many types of attacks such as eavesdropping, intrusion of unauthorized satellite terminals, satellite terminal cloning… The integration of security mechanisms is therefore considered today as an essential requirement. Some existing solutions may be recommended, however they do not offer all the necessary security services. For instance, the optional security mechanisms defined in the DVB-RCS standard provide insufficient security support, especially in satellite networks with natural broadcast/multicast capability over large areas. The use of well-known upper layers security protocols such as SSL (Secure Socket Layer) or IPSec/IKE can be considered too, but they are dedicated to unicast communications. The SatIPSec solution has been designed to provide an optimized and adapted security solution for satellite networks. It offers a new way of transparently and efficiently securing unicast and multicast satellite transmissions, with a strong access control, data confidentiality, data integrity, and data authentication as security services. SatIPSec has recently been implemented in a demonstrator developed in the context of the SATIP6 IST project. In this implementation, which allows to manage centrally secure multicast groups and Virtual Private Networks, key distribution is achieved according to the "Flat Multicast Key Exchange" protocol of SatIPSec, and data are encrypted and authenticated according to the IPSec protocol adapted to multicast. This paper introduces the principles of the security mechanisms involved in SatIPSec, and presents the features of the implementation and its results.

Nomenclature

I. Introduction

The security of data exchanged in networks is today a major concern for all network designers. Many security solutions have been developed, and current satellite systems enable security solutions dedicated to satellite context. However, most of them come from the "Broadcast" world and therefore focus on basic security services that a oneway broadcasting system requires. With the evolution towards two-way satellite systems (DVB-RCS) that support various types of connectivity (in particular multicast links), new security requirements appear (confidentiality and integrity on forward and return links, for multicast and unicast transmissions, authentication of satellite terminals…) that existing security solutions for satellite-based networks cannot satisfy. Besides the DVB-RCS standard defines optional security mechanisms, but they provide insufficient security support, especially in satellite networks with natural broadcast/multicast capability. The use of well-known uppers layers security protocols defined initially for terrestrial networks may be suggested, but they are dedicated to unicast communications. One example is the IPSec standard, which is the most widely used security protocol in terrestrial networks, and which offers strong security services. It could be implemented in multicast environment. However it would not provide an optimized solution because of its key exchange protocol (called Internet Key Exchange -IKE 1 ), which is dedicated to point-to-point communications. Indeed, in order to protect a multicast flow between a sender and several recipients, an IPSec tunnel should be established between the sender and each recipient. The sender should then duplicate each multicast packet, encrypt independently the copies and encapsulate them in their respective IPSec tunnel. This solution does not therefore take advantage of the natural broadcast capability of the satellite link.

This paper introduces a new security solution called SatIPSec 2,3 , which has been designed to satisfy the new data security requirements of satellite systems. This solution, dedicated to satellite-based networks, offers a new way of transparently and efficiently securing unicast and multicast satellite transmissions. It avoids in particular multicast packet duplication and multiple encryption computations per packet. SatIPSec has recently been implemented in a demonstrator developed in the context of the IST SATIP6 project. This implementation, where the key distribution is achieved according to the Flat Multicast Key Exchange protocol (FMKE) 4 of SatIPSec, and where unicast and multicast data are encrypted and authenticated according to the IPSec ESP protocol 5 , is presented in the following. Besides, this implementation works in IPv4 and IPv6.

II. SATIP6 6 architecture overview

A. Presentation of SATIP6

The objective of SATIP6 project is to evaluate and demonstrate key issues of the integration of satellite-based access networks into the Internet in order to offer multimedia services over wide areas. IP serves as the common denominator to allow interoperability for services and transport technology within integrated networks. Most immediate technical issues facing satellite broadband access in the coming years are examined, namely the functions to be implemented in the protocol layer between physical medium access and the IP Layer (i.e. typically layer 2). The project is considering two stages:

• short-to-medium term, focussing on better adaptation of DVB-RCS access for IP services with current satellites, • longer term, in which protocols more optimized for IPv6 are introduced, and considering next generation satellites (including both transparent and regenerative payloads). This paper is related to the second step. In this step, the shorter term solutions defined for IP/DVB-RCS have been extended and adapted for more advanced satellite systems supplemented with mesh connectivity (directly between users) via transparent or regenerative payloads (with on-board packet switching). In addition, satellite integration into Next Generation Networks (NGN), based on IPv6 and associated with a range of advanced features (in terms of mobility and security for instance), has been targeted. Moreover Layer 2 protocols, such as "IPdedicated" 7 introduced in the IST BRAHMS 8 project, has been further defined for more optimized transport of IPv6 over satellite (compared with MPLS).

The introduction of IPv6 into the Internet is seen as the paving the way to the next leap forward in telecoms services, and opening up a wide range of new and enhanced service capabilities. Besides, the introduction of satellite-based IPv6 transport through systems with wide coverage areas should allow users in many regions, where IPv6 services are non-existent or slow to be introduced, to gain early and high speed access to advanced services. Many satellite digital TV services have been introduced in recent years, and Internet services are being introduced on the back of them, using DVB standards. More recently return channels via satellite based on DVB-RCS have also been considered, which seems to offer the most immediate market opportunity for IP services.

The introduction of IPv6 (compared to today's IPv4) requires modification of user applications and network infrastructure. This is a gradual process, which has to be implemented differently in different parts of the global network. The satellite system and notably the satellite transport protocols, as well as the interfacing and interworking with the core network at the gateway stations, have to be adapted to provide cost-effective services compatible with terrestrial network IPv6 services. The SATIP6 project has tackled these different issues.

B. Overview of the emulated satellite system architecture.

One of the starting points of the SATIP6 project has been the architecture developed in the IST BRAHMS project, and adopted within the ETSI BSM group. The SATIP6 architecture is presented in Fig. 1.

Figure 1. SATIP6 architecture

On the left is depicted the end-user side of the platform. On the right is shown the provider/enterprise/Internet side of the platform. We distinguish also between the satellite network side (in the middle) and the IP network sides (on left and right ends), the frontier being delimited by satellite terminals (ST).

The satellite in our emulation covers primarily one spot. However this is not a restriction: we are able to emulate multi-spot coverage. Inside a spot several channels are allocated: for the forward DVB-S path, for the return DVB-RCS path, and also a dedicated control channel.

Three main components have to be distinguished in the satellite network (middle side):

• the Satellite Emulator (SE)

• the Satellite Terminals (ST)

• the Network Control Center (NCC)

The SE is a regenerative satellite that uses IP-dedicated as an optimization layer for switching frames on the basis of labels. Functionally ST acts as a router, that is to say that Satellite Network is considered as a special link in classical network point of view. By using special mechanisms (IP-dedicated 7 address resolution) ST are able to transmit IP packets from one side of the IP network to the other side of the IP network.

C. Experimental platform

The testbed that has been developed is able to emulate the three main parts of a satellite communication system (SE, ST, NCC). It is described in Fig. 2. The middle side interconnects two user LANs (individual user, company subsidiaries …) involving a SubLAN, and the right LAN (LAN 3), acting as an Internet Service Provider site or as the company headquarters. LAN 3 provides also Internet interconnection, using native IPv6. Each LAN consists of one Satellite Terminal (ST), several user workstations (WS), no or one " gateway" equipment (GW) associated with a specific terminal called GWS. Role and function are given in Table 1, related to the chosen validation scenario. The security scenario is mentioned in the last line.

D. SatIPSec Architecture

The security solution which has been implemented to protect satellite transmissions in the SATIP6 simulated architecture is a new layer 3 security solution called SatIPSec 2,3 . This solution is based on two main entities entitled SatIPSec client and SatIPSec Group Controller & Key Server (SatIPSec GCKS). The SatIPSec system architecture is thus formed of several SatIPSec clients and of one GCKS. SatIPSec clients are in charge of securing IP traffic flows during their transmission over the satellite links. For that purpose, they apply some security treatments (ciphering/deciphering, computation and checking of authentication values…) to IP datagrams. The GCKS centrally ensures the management of SatIPSec clients and the establishment of the security architecture. Its function is to configure SatIPSec clients, by supplying them with the necessary information for securing data transmissions according to the data security requirements.

The Fig. 3 presents the security architecture defined in the SATIP6 project. SatIPSec clients and GCKS are implemented in external boxes (independently of the other Satcom equipments) ‡ . There is one SatIPSec client box behind each Satellite Terminal (ST), and the GCKS is located at the gateway side.

The location of SatIPSec clients allows to apply security mechanisms to IP traffic (if requested) so as to ensure its protection during its transmission over the satellite network. In transmission, the SatIPSec client can cipher each IP packet and compute an authentication value before transmitting it on satellite system. In reception, the SatIPSec client(s) can decipher it and check the authentication value, before transmitting it on the terrestrial network it (they) is (are) connected to.

The implementation of the SatIPSec solution in the context of the SATIP6 project allows to protect any unicast or multicast IP flows transmitted on satellite links, from Hub to ST, from ST to Hub and from ST to ST (remark : multicast IP traffic is only generated at the Hub side). ‡ However SatIPSec mechanisms could also be implemented directly inside the satellite terminal IP stack . • Traffic Processing per data flow: Each IP flow can be secured independently (with its own keys and security attributes), and encapsulated in its own IPSec tunnel. An IP data flow can be identified by its IP source and destination addresses (representing equipment, end-user, subnet, multicast IP address) and its source and destination port numbers. Thanks to this service, the access to a flow can easily be limited only to the allowed receivers. These services can be offered simultaneously for all types of traffic (unicast and multicast). Besides SatIPSec allows one part of the traffic to be secured and the other part not.

Access control

Access control aims at guaranteeing that only authorized recipients get access to data transmitted on satellite links in clear. With SatIPSec, each IP flow requiring to be protected is encrypted before being transmitted on satellite network. The security parameters allowing to secure it in emission, and to decrypt it in reception, are distributed only to authorized SatIPSec clients. Thus SatIPSec solution enables a strong access control. All security parameters defining how to secure an IP flow (keys, cryptographic algorithms to use, flow identifier…) are contained in a Security Association (SA).

Access control is managed by the GCKS. It authenticates each SatIPSec client before distributing it, in a secure manner, only the Security Associations it is authorized to receive.

Centralized management

The SatIPSec implementation allows to establish and manage Virtual Private Networks (VPN) and Secure Multicast Groups, in a centralized manner .

A VPN is established when two distant terrestrial sites wish to communicate securely together through the satellite network. A secure tunnel is established; its end-points are the SatIPSec clients connected to each site. This tunnel can be configured to secure for instance the exchanges between two end-users or subnets belonging to these sites, or all unicast traffic exchanged between these two sites.

A Secure Multicast Group is composed of members (i.e. SatIPSec clients) sharing a common security configuration allowing to secure IP multicast flows. Only group members can get access to the corresponding traffic (in clear) in reception. Each multicast IP packet is indeed encrypted and encapsulated before its transmission on satellite network by a group member. In reception, only group members can decipher it, and then transmit the packet on the terrestrial network they are connected to. The SatIPSec solution encapsulates multicast packets in new multicast packets, the establishment of a secure multicast group can therefore be considered as the establishment of multicast IPSec tunnels.

SatIPSec clients, VPNs and Secure Multicast Groups are managed by the GCKS. The establishment of a VPN or a Secure Multicast Group requires the selective distribution of the corresponding SAs by the GCKS (a SA contains all the necessary information to establish an IPSec tunnel to secure one unidirectional flow). For a VPN, both SAs (one for each direction) are transmitted only to the SatIPSec clients end-points of the VPN to establish. For a Multicast Secure Group, SAs (one for each multicast flow) are transmitted only to SatIPSec clients belonging to the group.

B. SatIPSec Functional architecture

As previously presented, two entity types are involved in SatIPSec: GCKS and SatIPSec clients. In the following their functional architecture and associated protocols are described.

In IPSec, the data plane and the control plane are separated : the data plane implements the IPSec ESP protocol 5 or the IPSec AH 9 protocol, which are in charge of encrypting/decrypting and/or authenticating IP packets; the control plane implements the IKE 1 protocol, which is in charge of establishing and renewing IPSec SA between two equipments. In the same way, in SatIPSec, data plane and control plane are separated. The control plane implements a new protocol called Flat Multicast Key Exchange protocol (FMKE) 4 . It is a layer 3 protocol, mainly dedicated to group key and SA management. The data plane (in charge of encrypting and authenticating data) can be implemented at layer 2 or 3. In the implementation realized for the SATIP6 project, the selected data plane is the IPSec ESP protocol.

SatIPSec client and GCKS functional architectures are described in Fig. 4. SatIPSec Clients are composed of a control plane part and a data plane part. The data plane is managed by the control plane. The Client control plane is configured by the GCKS control plane.

C. Security Data plane

The selected security data plane is the ESP (Encapsulating Security Payload) protocol of IPSec. The ESP protocol is implemented and used as it is defined in the standard. ESP defines two IP packet secure encapsulations. In transport mode, the ESP header is inserted after the IP header and before the upper layer protocol header, and only the packet payload is encrypted. In tunnel mode, the ESP header is inserted before an encapsulated IP header, and both payload and header are encrypted and encapsulated in a new IP packet. The SatIPSec implementation enables the tunnel mode only.

In the implementation, confidentiality, data origin authentication and IP address confidentiality services are provided like in ESP, by using the same mechanisms. The cryptographic algorithms of the demonstrator are usually used with ESP: AES, 3DES, DES, Blowfish for the encryption algorithms, and HMAC-SHA1, HMAC-MD5 for integrity-source authentication algorithms

GCKS

D. Control plane : FMKE

The Flat Multicast Key Exchange (FMKE) protocol is a new group key management protocol, based on a centralized management achieved by the GCKS. Its objective is to manage securely Security Associations destined to protect multicast and unicast IP traffic, i.e. establish and update SAs in clients participating to Secure Multicast Groups and VPN. The FMKE protocol is in particular optimized for very large multicast groups in flat environment (i.e. no intermediate routers between GCKS and a large amount of clients) like in satellite networks. In fact, FMKE is derived from the Group Domain Of Interpretation (GDOI) protocol 10 defined by the IETF Multicast SECurity (MSEC) group, and can be seen as a use case adapted to satellite networks and to the needs of the SATIP6 project. There are three main differences. First of all, FMKE manages SAs for group and unicast exchanges, contrary to GDOI, which manages only groups, and requires therefore to add external mechanisms to establish VPNs. Secondly, FMKE exchanges implement reliability mechanisms based on positive, negative acknowledgements… in order to guaranty a reliable key distribution (in unicast and in multicast). GDOI does not guaranty at all reliable key distribution. At last, in GDOI, the client has to request to get access to a particular group in order to receive the corresponding SAs if it is authorized, while in FMKE, the client receives directly all SAs it is authorized to get access to, without having to send a request for each group. This way FMKE limits the consumed bandwidth. Indeed the client does not have to send a request for each group, and a FMKE message from the GCKS can contain SAs from different groups and VPNs. However, FMKE could be defined with a GDOI-like behavior.

FMKE is thus used securely to configure SatIPSec clients with the necessary SAs to establish the required security architecture (i.e. VPNs, Secure Multicast Groups). Client configuration is achieved thanks to three different phases described in Ref. 4. The implementation achieved in the context of the SATIP6 project enables the two first ones.

Figure 4. SatIPSec entity functional architecture

The first phase is dedicated to the establishment of a secure ISAKMP 11 channel between the GCKS control plane and the client control plane. This establishment is preceded by a mutual authentication. In the SatIPSec implementation, the method which has been selected for this phase is the method called « Main-Mode with pre-Shared key for Authentication » defined in the IKE protocol 1 (IKE phase 1). Authentication is based on a pre-shared secret.

The second phase is dedicated to the SatIPSec client configuration. The GCKS transmits to the client, SAs that it is authorized to receive. These SAs are sent securely in unicast, thanks to the secure ISAKMP channel established during the previous phase (confidentiality, data origin authentication and integrity are provided). SAs concerns VPN and Secure Multicast Groups.

The cryptographic methods and algorithms used in the SATIP6 demonstrator are Diffie-Hellman group 1 and group 2 for key exchange, DES, 3DES and AES for encryption, and HMAC-SHA1, HMAC-MD5 for integrity/source authentication.

The FMKE third phase is dedicated to the configuration of a Secure Multicast Group (i.e. of its group members). The GCKS transmits, in multicast, to all group members, SAs allowing to secure multicast flows. These transmissions are protected by a secure multicast control channel dedicated to the group, whose parameters have been previously transmitted to each group member thanks to phase 2. The interface between control plane and data plane (IPSec ESP) relies on the PF_KEY API system 12 available on Unix platforms. This demonstrator is based a customized version of the OpenBSD kernel. Some modifications have indeed been realized in the IP stack, in particular at multicast forwarding, routing, and IPSec levels. The SatIPSec implementation has been developed to work in IPv4 and in IPv6.

B. SatIPSec System configuration and graphical interfaces

The initial configuration of both clients and GCKS is done thanks to configuration files. The configuration file of a SatIPSec client contains few information: its IP address, GCKS IP address, a secret shared only by itself and GCKS (for mutual authentication), and parameters for the ISAKMP secure channel to establish in phase 1. The GCKS configuration file contains a set of client IP address with shared secrets and client's profile that defines the list of SAs each client is authorized to receive, and a list of SAs with their attributes. A graphical interface has been developed to facilitate the GCKS configuration. It creates automatically its configuration file, according to the information given by the security operator. The graphical interface is presented in Fig. 6 'GCKS configuration interface', and is composed of three main parts :

• SatIPSec client configuration : this step consists of giving SatIPSec clients' IP address and shared secret.

• Secure Multicast Group configuration : this step consists of indicating the Secure Multicast Groups to establish.

The configuration of a Secure Multicast Group involves the selection of its group members among all SatIPSec clients, the identification of IP multicast flows to be secured by the group (multicast IP address, Source IP address, and source and destination port numbers), and for each identified flow, selection of the security parameters to use (encryption and integrity algorithms, key lifetime). • VPN configuration : this step consists of indicating the VPNs to establish. The configuration of a VPN involves the selection of two SatIPSec clients as VPN tunnel end-points, the identification of the unicast flow to secure (source and destination IP addresses representing subnets or hosts, source and destination port numbers), and the security parameters to use (encryption and integrity algorithms, key lifetime). Thanks to the information given by the security operator, the GCKS configuration file is built. SA cryptographic keys and SPI (Secure Parameter Index, i.e. SA identifier) are generated randomly.

The interface represented in Fig. 6 entitled 'GCKS control interface' allows to control during SatIPSec processing the connection status of each client with GCKS. This interface also indicates all the SAs (with their security attributes) which have to be established, and for each client, the list of SAs they are going to receive. Three VPNs have been established on the simulated architecture: between each remote site and the Hub, securing all unicast bi-directional traffic exchanged respectively between LAN 3 and LAN 2, and LAN 3 and LAN 1, and between both remote sites, securing all unicast bi-directional traffic exchanged between LAN 2 and LAN 1 (Fig. 7).

Three different Secure Multicast Groups have been established, in order to limit the access to multicast flows only to the authorized remote sites. Multicast traffic is generated at the hub side only. The three groups obviously contain the SatIPSec client located at the Hub side, and respectively the client connected to LAN 1, the client connected to LAN 2, and the clients connected respectively to LAN 1 and to LAN 2. These multicast groups have allowed to secure video streaming sent in multicast, destined only to LAN 1, LAN 2, or both LAN 1 and 2.

  Here are described the security services offered by the SatIPSec solution implemented in the context of the SATIP6 project.1. IP traffic protection• Data confidentiality : achieved by the ciphering of the entire IP packet (data and header) • Data integrity and Data origin authentication: achieved by the computation of an authentication value depending of the IP packet, before its transmission on satellite network. In reception SatIPSec clients can verify the integrity of the packet (i.e. if it has been modified or not during transmission) and the identity of its source, by checking its authentication value. • IP address confidentiality: achieved by the ciphering of the entire IP packet (data and header) and its encapsulation into a new IP packet. The IP addresses of the initial packet are therefore encrypted. The source IP address of the new packet is the address of the SatIPSec client which has encapsulated the initial packet. The destination IP address is the address of the SatIPSec client which should desencapsulate the packet, or the initial multicast IP address in the case of a multicast packet.

Figure 3 .

 3 Figure 3. Protection of satellite IP transmissions by SatIPSec solution

  Figure 5. FMKE phases

Figure 6 .

 6 Figure 6. Graphical interfaces : GCKS configuration interface & GCKS control interface

Table 1 -Testbed components involved in validation scenario

 1

		Figure 2.Full SATIP6 testbed
		ST	WS	GW	GWS
	Function	Satellite terminal	User workstation	"Gateway"	Specific terminal
	QoS scenario	With enabled QoS Server With enabled QoS Agent	Not used	Not used
	Multicast scenario	With enabled mcastd	With enabled mcastd	Not used	Not used
	PEP scenario	Basic configuration	Not used	PEP	User terminal
	Mobility scenario	Basic configuration	Not used	HA/Router	User terminal
	Security scenario	Basic configuration	Not used	SatIPSec client	User terminal

B. Applications

Several unicast and multicast applications have been used to validate the SatIPSec demonstrator :

• Video & Audio streaming : VideoLanClient (VLC) VLC is a multimedia player for various media sources (DIVX files to DVDs) and a audio and video streaming server that supports a complete set of codecs, single or multiple diffusion (respectively unicast and multicast) and various protocols (IPv4 or IPv6, RTP, UDP …).