domain: spi phys math info

text:
Esteban Restrepo

Antonio Loría

Ioannis Sarras

Julien Marzat

Distributed Full-Consensus Control of Multi-Robot Systems with Range and Field-of-View Constraints

In this paper we solve the full-consensus problem for multiple nonholonomic vehicles interacting over a directed leader-follower topology and subject to sensing constraints in the form of limited range and limited field-of-view. Remarkably, based on a polar-coordinates model transformation, the designed controller is time-invariant and smooth (in the domain of definition). Moreover, the control laws rely only on local measurements, making it well suited for implementation. The asymptotic convergence to the consensus manifold as well as the respect of the constraints is established using Lyapunov's first method and cascaded systems theory. Realistic simulations in the Gazebo-ROS environment, which illustrate the effectiveness of our theoretical contributions, are shown in an accompanying video.

I. INTRODUCTION

The distributed consensus problem, being the basis of most multi-vehicle interactions, has received considerable attention in recent years [START_REF] Cao | Rendezvous of multiple nonholonomic unicycles-based on backstepping[END_REF], [START_REF] Hu | Cooperative control of heterogeneous connected vehicle platoons: An adaptive leader-following approach[END_REF]. For multi-agent systems of nonholonomic vehicles, two main problems are addressed in the literature, position consensus [START_REF] Cao | Rendezvous of multiple nonholonomic unicycles-based on backstepping[END_REF], [START_REF] Bautista-Castillo | Consensus-based formation control for multiple nonholonomic robots[END_REF] and full consensus [START_REF] Maghenem | Lyapunov-based formationtracking control of nonholonomic systems under persistency of excitation[END_REF], [START_REF] Maghenem | Consensus of multiagent systems with nonholonomic restrictions via Lyapunov's direct method[END_REF]. In the first case, all agents converge to the same position with an arbitrary or predetermined orientation. In the second case, agreement on both position and orientation is sought. Furthermore, these protocols may be implemented using absolute position and orientation values [START_REF] Bautista-Castillo | Consensus-based formation control for multiple nonholonomic robots[END_REF], [START_REF] Maghenem | Consensus of multiagent systems with nonholonomic restrictions via Lyapunov's direct method[END_REF] or rather, using relative measurements [START_REF] Hu | Cooperative control of heterogeneous connected vehicle platoons: An adaptive leader-following approach[END_REF], [START_REF] Dai | Adaptive leader-follower formation control of nonholonomic mobile robots with prescribed transient and steady-state performance[END_REF], [START_REF] Delimpaltadakis | Decentralized platooning with obstacle avoidance for car-like vehicles with limited sensing[END_REF]. In most practical scenarios, however, protocols using absolute measurements may not be implementable since only the relative measurements from embedded sensing devices are available to the vehicles. This, in turn, presents an additional challenge, when the sensing devices have a limited range or a limited field of view. Indeed, in such scenarios assuming that each agent has access to its neighbors' information at all times, although necessary from a theoretical viewpoint, might be conservative in practice.

Consequently, considerable attention has been focused on the study of coordination strategies of multi-agent systems subject to distance and field-of-view constraints. In [START_REF] Poonawala | On maintaining visibility in multi-robot-networks with limited field-of-view sensors[END_REF]- [START_REF] Endo | Stability analysis for heterogeneous swarm robots with limited field of view[END_REF] coordination protocols with field-of-view-based connectivity are considered, albeit for linear integrator E. Restrepo, I. Sarras, and J. Marzat are with DTIS, ONERA, Université Paris-Saclay, F-91123 Palaiseau, France. E-mail: {esteban.restrepo, ioannis.sarras, julien.marzat}@onera.fr. A. Loría is with CNRS, 91192 Gif-sur-Yvette, France. E-mail: antonio.loria@centralesupelec.fr E. Restrepo and A. Loría are also with L2S-CentraleSupélec, Université Paris-Saclay, Saclay, France. The work of A. Loría is supported by the French National Research Agency (ANR) via project HANDY, contract number ANR-18-CE40-0010 and by CEFIPRA under the grant number 6001-A. models. For nonholonomic systems, most works in the literature address only the problem of position consensus. Moreover, the solutions are based, for the most part, on non-smooth or time-varying control laws. The latter have the advantage to guarantee uniform forms of asymptotic stability in closed loop, which guarantees robustness, but, in general, they are difficult to tune and may give rise to undesirable behavior, such as oscillations [START_REF] Maghenem | Lyapunov-based formationtracking control of nonholonomic systems under persistency of excitation[END_REF], [START_REF] Maghenem | Consensus of multiagent systems with nonholonomic restrictions via Lyapunov's direct method[END_REF]).

In [START_REF] Kan | Decentralized Rendezvous of Nonholonomic Robots With Sensing and Connectivity Constraints[END_REF] using relative information, a navigation-functionbased controller with distance-based connectivity maintenance is proposed for multi-agent systems interconnected over directed graphs; nevertheless, the controller is nonsmooth and it presents some problems inherent to the navigation-function framework such as local minima and the need to have a bounded workspace. In [START_REF] Lian | Formation Control and Obstacle Avoidance for Multi-Agent Systems Using Barrier Lyapunov Functions[END_REF] distance constraints are considered for leader-follower topologies based on barrier functions. However, only position consensus is achieved and the controller requires the knowledge of absolute positions. In [START_REF] Poonawala | Collisionfree formation control with decentralized connectivity preservation for nonholonomic-wheeled mobile robots[END_REF] distance constraints are addressed and practical stability of a position-consensusbased formation is achieved, but the estimation of global parameters is required. In [START_REF] Dai | Adaptive leader-follower formation control of nonholonomic mobile robots with prescribed transient and steady-state performance[END_REF], [START_REF] Delimpaltadakis | Decentralized platooning with obstacle avoidance for car-like vehicles with limited sensing[END_REF] the authors develop time-varying control laws with prescribed performance considering both distance and field-of-view constraints. Nevertheless, full consensus is not achieved and only the platooning problem, with interaction topologies consisting of single directed chains, is addressed.

In this paper we extend the results obtained in [START_REF] Restrepo | Leader-follower consensus of unicycles with communication range constraints via smooth time-invariant feedback[END_REF], where a distributed controller achieving full consensus of multiple vehicles in a leader-follower configuration is proposed, albeit considering only relative-distance constraints. More precisely, herein the full-consensus problem is solved for multi-agent systems subject to both distance and fieldof-view constraints and interacting over an arbitrary leaderfollower topology, that is, a directed spanning tree graph. The control design is based on a polar-coordinates model for unicycles proposed in [START_REF] Aicardi | Closed loop steering of unicycle like vehicles via Lyapunov techniques[END_REF]. The advantages of using this model are twofold. First, we are able to propose a controller which is time-invariant and smooth in the domain of definition. Second, since the polar-coordinates model relies only on relative variables of distances between agents and line-of-sight angles, the proposed controller may be implemented without inter-agent information exchange. These two characteristics not only facilitate the analysis of the closed-loop system, but they also render the control law more suited to implementation.

The paper is organized as follows. In Section II the model and the problem statement are presented. The main results are presented in Section III and are illustrated via simulations in Section IV. Concluding remarks are given in Section V. Notation. The real n-coordinate space, with n ∈ N, is denoted as R n ; R n ≥0 and R n >0 are the sets of real n-vectors with all elements non-negative and positive, respectively. The notation x is used for the Euclidean norm of a vector x ∈ R n . A function γ : R ≥0 → R ≥0 is said to be of class K, if it is continuous, strictly increasing and zero at zero. If moreover γ(s) → ∞ as s → ∞, we say that γ ∈ K ∞ . A digraph, denoted G = (V, E), is defined by a set of nodes, V := {1, 2, . . . , n} whose elements correspond to the labels of the agents' states and a set of edges, E ⊆ V 2 of cardinality m, that represents the communication between a pair of nodes. A directed edge e k , with k ≤ m, is an ordered pair (i, j) ∈ E if and only if a connection exists from node i to node j. The distance d(i, j) between nodes i, j ∈ V is the number of edges in the shortest path from i to j. A directed spanning tree G T is a graph consisting of a root node, with no parent, and a set of nodes reachable from the root.

II. MODEL AND PROBLEM STATEMENT

We consider a multi-agent system composed of n unicycles. To facilitate the control design and the analysis, the multi-vehicle system is represented using an alternative polar-coordinates-based model. Such model has the advantage that equilibria are reachable via smooth time-invariant feedback. Moreover it naturally leads to the design of controllers that rely only on local relative measurements -cf. [START_REF] Restrepo | Leader-follower consensus of unicycles with communication range constraints via smooth time-invariant feedback[END_REF], [START_REF] Aicardi | Closed loop steering of unicycle like vehicles via Lyapunov techniques[END_REF].

For every pair of leader and follower vehicles in the system, labeled i and j respectively, let ρ k ∈ R ≥0 denote the distance separating them, β k ∈ (-π, π] denote the angle between the line of sight and the leader's direction of motion, and α k ∈ (-π, π] denote the angle between the line of sight and the follower's direction of motion. See Figure 1 for a graphical representation. Then, for a network of agents interacting in a leaderfollower configuration, we have m interconnected dynamical systems described by the following equations:

ρk = v i cos β k -v j cos α k (1a) βk = 1 ρ k [-v i sin β k + v j sin α k ] -ω i (1b) αk = 1 ρ k [-v i sin β k + v j sin α k ] -ω j , (1c)
where v j and ω j are the control inputs, and v i and ω i , which are respectively the leader's velocity and angular rate, are considered as external signals.

The objective is to design distributed control laws that achieve full consensus for the multi-agent system. From a dynamical systems viewpoint, the solutions to Eqs. ( 1) correspond to the leader-follower relative error trajectories for the pair of index k. Therefore, the full consensus control goal is reached if

(ρ k , β k , α k ) → (0, 0, 0) for all k ≤ m.
In addition to the distributed nature of the information in the system, we also assume that the agents cannot communicate with each other. Instead, we consider that each agent is only able to measure or estimate information from its immediate leader. Thus, the leader-follower configuration, may be represented by an arbitrary directed spanning tree G T graph as in Figure 2, where the triple (ρ k , β k , α k ), corresponds to the state of an edge e k in the tree G T . Herein assume to have perfect knowledge of the estimates of the relative state (ρ k , β k , α k ). The estimation of these variables from the on-board measurements is out of the scope of this paper. In graph theory, it is well-known that a directed spanning tree is the minimal configuration necessary to achieve consensus [START_REF] Olfati-Saber | Consensus and cooperation in networked multi-agent systems[END_REF]. However, in this paper we also consider that the vehicles are subject to sensing constraints in the form of a limited field-of-view, described by an angle of view, and limited range described by a maximal detection distance. Therefore, the existence of this minimal topology cannot be assumed, but rather has to be enforced by the control law. Thus, besides achieving full consensus, in this paper we design controllers that ensure the following properties.

Definition 1 (Distance-based connectivity maintenance): For each k ≤ m, let ∆ ρ,k > 0 denote the maximum distance between the leader-follower pair (i, j), i.e., the edge e k , such that the measurements of the follower j are reliable. We say that the distance constraints are respected if the set

J ρ := ρ k ∈ R ≥0 : ρ k < ∆ ρ,k , ∀ k ≤ m (2) is forward invariant. That is, ρ k (0) < ∆ ρ,k implies that ρ k (t) ∈ J ρ for all t ≥ 0.
Definition 2 (Field-of-view connectivity maintenance): For each k ≤ m, let ∆ α,k > 0 denote the maximum line-of-sight angle, corresponding to half the angle of view, such that for the leader-follower pair (i, j), i.e., the edge e k , the leader is inside the follower's field of view. We say that the field-of-view constraints are respected if the set

J α := α k ∈ (-π, π] : |α k | < ∆ α,k , ∀ k ≤ m (3) is forward invariant. That is, if α k (0) < ∆ α,k implies that α k (t) ∈ J α for all t ≥ 0.
Thus, the problem considered herein is to define distributed smooth time-invariant control laws v j and ω j , j ≤ n, such that, the relative variables (ρ k , β k , α k ) converge to zero for all k ≤ m and that connectivity, according to Definition 1 and Definition 2, is maintained for all initial conditions satisfying ρ k (0) ∈ J ρ \{0} and α k (0) ∈ J α , and for all t ≥ 0.

III. MAIN RESULTS

A. Controller design

The control approach is based on the classical backstepping method [START_REF] Khalil | Nonlinear systems[END_REF]. The main idea for system (1) is to first design a virtual input α * k along with v j in order to stabilize the origin of the subsystem (1a)-(1b). Then, the angular rate ω j is designed so that α k (t) → α * k (t), or equivalently, defining the error variable αk := α k -α * k , so that αk → 0. Furthermore, in order to guarantee connectivity and field-of-view requirements, the controller design relies on the concept of barrier Lyapunov functions. These functions are reminiscent of artificial potential fields, which have been extensively used in robotics to enforce constraints [START_REF] Kim | Real-time obstacle avoidance using harmonic potential functions[END_REF], [START_REF] Tee | Barrier Lyapunov functions for the control of output-constrained nonlinear systems[END_REF]. Here, we encode the distance and fieldof-view constraints using the barrier Lyapunov function candidates

U ζ,k (ζ k ) := 1 2 ζ 2 k + ln ∆ 2 ζ,k ∆ 2 ζ,k -ζ 2 k , ζ ∈ {ρ, α}.
(4) Unlike quadratic Lyapunov functions, the barrier Lyapunov functions have the property of growing unbounded as the state approaches the imposed limits, i.e.,

U ζ,k (ζ k ) → ∞ as ζ k → ∆ ζ,k . Therefore, by guaranteeing that U ζ,k (ζ k (t)
) remains bounded along the trajectories of the closed-loop system, the respect of the state constraints is guaranteed.

The control inputs are chosen in terms of the gradient of the barrier function (4), which is given by

∇ ζ U ζ,k ∂U ζ,k ∂ζ k , ζ ∈ {ρ, α}.
After a direct computation we obtain

∇ ζ U ζ,k = p ζ,k (ζ k )ζ k (5)
where

p ζ,k (ζ k ) = 1 + 1 ∆ 2 ζ,k -ζ 2 k .
For further analysis we stress that

p ζ,k (ζ k ) ≥ p 0 > 0 for all |ζ k | < ∆ ζ,k with p 0 a positive constant, and p ζ,k (ζ k ) → ∞ as ζ k → ∆ ζ,k .
Remark 1: Notice that when the sensing limits ∆ ζ,k tend to infinity, that is, there are no constraints on the state, the second term in the right-hand-side of (4) vanishes and the barrier Lyapunov function becomes a quadratic Lyapunov function. Thus, the barrier function (4) may be used for the design of consensus protocols with or without sensing constraints.

From a control theory viewpoint, we want to use the barrier functions as Lyapunov functions for the analysis of the closed-loop system. However, from the backstepping method, the closed-loop system depends on the error variable αk rather than on the constrained variable α k . Therefore, in order to be able to use the barrier function encoding the field-of-view constraints as a Lyapunov function, U α,k has to be modified so that it is made positive definite in αk . For this purpose, we rely on the concept of recentered barrier function introduced in [START_REF] Wills | A recentred barrier for constrained receding horizon control[END_REF], and exploited in multirobot coordination in [START_REF] Panagou | Distributed coordination control for multi-robot networks using Lyapunov-like barrier functions[END_REF] among others. The recentered barrier function Ũα,k is defined as

Ũα,k ( αk ):=U α,k (α k + α * k )-U α,k (α * k )- ∂U α,k (α * k ) ∂α * k αk . (6)
Remark 2: The recentered barrier function Ũα,k is pos- itive definite, that is, Ũα,k (α k ) > 0 for all αk = 0 and Ũα,k (0) = 0, and it tends to +∞ as

|α k | → ∆ α,k , or equivalently, as |α k + α * k | → ∆ α,k .
Therefore it is a valid barrier Lyapunov function for the closed-loop system. Now, following the backstepping approach, the virtual input is designed as [START_REF] Restrepo | Leader-follower consensus of unicycles with communication range constraints via smooth time-invariant feedback[END_REF],

α * k := arctan(-c 3 β k ), (7)
with c 3 a design constant satisfying

0 < c 3 < min k≤m {∆ α,k /π}.
Remark 3: Note that the bound on c 3 comes from the design of the recentered barrier function [START_REF] Dai | Adaptive leader-follower formation control of nonholonomic mobile robots with prescribed transient and steady-state performance[END_REF]. Indeed, in order for the term U α,k (α * k ) to be well defined, we need to guarantee

|α * k | < ∆ α,k . Therefore, since |α * k | ≤ c 3 |β k | and β k ∈ (-π, π] by definition, choosing c 3 < min k≤m {∆ α,k /π}, the terms U α,k (α * k ) and [∂U α,k /∂α * k ] (α * k )
are well defined and upper bounded by some positive constants.

Let the coefficients

a jk := 1 if edge e k is incident on node j 0 otherwise (8)
represent the available information for each agent j based on the interaction topology G T . Then, based on the latter, the distributed control inputs v j and ω j are taken proportional to the gradient of the barrier functions U ρ,k and Ũα,k , respectively. More precisely, the controller is given as follows:

v j := c 1 k≤m a jk η k ∇ ρ U ρ,k (ρ k ), (9)
η k := 1 + (c 3 β k ) 2 (10)
ω j := k≤m a jk c 2 ∇ α Ũα,k (α k ) + ψ k + 1 + c3 η 2 k ωk sin(α k ) ρ k i≤n a ik v i ( 11
)
where c 1 , c 2 > 0 are design constants. In turn, the term

ψ k := -∇ ρ U ρ,k [cos(α k ) -cos(α * k )] ∇ α Ũα,k + β k ρ k [sin(α k ) -sin(α * k )] ∇ α Ũα,k (12)
compensates for the error dynamics coming from the tracking problem of the backstepping method. The term

c 3 η 2 k ωk sin(α k ) ρ k i≤n a ik v i , where ωk := ∂ 2 U α,k (α * k ) ∂α * 2 k αk ∇ α Ũα,k , (13)
is used to dominate the additional terms coming from the derivative of the recentered barrier function [START_REF] Dai | Adaptive leader-follower formation control of nonholonomic mobile robots with prescribed transient and steady-state performance[END_REF]. Remark 4: Note that ( 13) is well posed for all ρ k ∈ J ρ \{0} and all α k ∈ J α . Indeed, using ( 5), ( 6), and L'Hôpital's rule, we have

lim αk →0 αk ∇ α Ũα,k = lim αk →0 1 p α,k (α k ) + ∂ 2 p α,k ( αk ) ∂ α2 k αk = ,
where is a positive constant. Moreover

lim | αk |→∆ α,k αk ∇ α Ũα,k = 0. Furthermore, noting that | sin(α k +α * k )-sin(α * k )| ≤ |α k | and | cos(α k + α * k ) -cos(α * k )| ≤ |α k |,
the previous statement holds also for [START_REF] Lian | Formation Control and Obstacle Avoidance for Multi-Agent Systems Using Barrier Lyapunov Functions[END_REF].

Since the root node (which represents the leader agent) has no incoming edges, a 1k = 0 for all k ≤ m -cf. Eq. ( 8). Therefore, with the full consensus protocol ( 9)- [START_REF] Kan | Decentralized Rendezvous of Nonholonomic Robots With Sensing and Connectivity Constraints[END_REF], the inputs of the leader are set equal to zero, i.e., v 1 (t) = ω 1 (t) = 0. This case is analyzed next. It may be shown, however, that with the proposed controller, the range and field-of-view requirements are satisfied, even when the leader has non-zero inputs which might come from additional objectives like trajectory tracking.

B. Multi-agent system with static leader

Consider a multi-agent system composed of n unicycles with interactions represented through an arbitrary directed spanning tree. The multi-agent system in a leader-follower topology may be represented as a cascaded system. To see this, notice that the tree representing the leader-follower topology may be divided into h ≤ n -1 levels based on the distance to the root node -see Figure 2. Denote E p ⊂ E the set of edges such that the distance from its terminal node to the root of the tree, labeled i = 1, is equal to p ≤ h, i.e., E p := {e k = (i, j) ∈ E : d(1, j) = p}. Without loss of generality, assume that each level p of the tree contains an l p number of edges, such that 1 ≤ l p ≤ m, h p=1 l p = m. Then, for each level p having l p arcs labeled e k with k ∈ [l p-1 + 1, l p ] we define the closed-loop state variables

ξ p := ξ p,1 • • • ξ p,lp ∈ R 3lp , ξ p,k := [ρ k β k αk ] ∈ R 3 .
Using this notation, the systems (1) in closed loop with the inputs ( 9)- [START_REF] Kan | Decentralized Rendezvous of Nonholonomic Robots With Sensing and Connectivity Constraints[END_REF], with k ≤ m and for the considered graph, can be written in the compact cascaded-system form,

ξp =f p (ξ p ) + g p (ξ p , ξ p-1 ), p ∈ [2, h] ξ1 =f 1 (ξ 1 ) (14)
where, for each p ≤ h,

f p (ξ p ) := f p,1 (ξ p,1 ) . . . f p,lp (ξ p,lp ) , g p (ξ p , ξ p-1 ) := g p,1 (ξ p,1 , ξ p-1 ) . . . g p,l p (ξ p,l p , ξ p-1 )
and the nominal systems, ξp,k = f p,k (ξ p,k ), correspond to

ρk = -c 1 ∇ ρ U ρ,k 1 + [cos(α k ) -cos(α * k )]η k (15a) βk = -2c 1 p ρ,k (ρ k ) c 3 β k -[ sin(α k ) -sin(α * k ) η k (15b) αk = -c 2 ∇ α Ũα,k -c 1 ψ k η k -(1 -ωk ) c3 η k sin(α k ) ρ k ∇ ρ U ρ,k (15c)
where we recall that α k = αk + α * k . The interconnection term g p (ξ p , ξ p-1 ) depends on states relative to the p-th level in the tree and to the previous one in the following way. Fix k ∈ [l p-1 +1, l p ] and r ∈ [l p-2 + 1, l p-1 ] in a manner that the edge e r ∈ E p-1 is incident on e k ∈ E p , that is, so that the terminal node of e r is the initial node of e k -see Figure 2. Let ξ p-1,r := [ρ r β r αr ] be the state associated to e r . Then,

g p,k (ξ p,k , ξ p-1 ) =   c 1 cos(β k )η r ∇ ρ U ρ,r gβ (ξ p,k , ξ p-1,r ) gα (ξ p,k , ξ p-1,r )   , (16)
where η r := 1 + (c 3 β r ) 2 ,

gβ := -c 1 η r ∇ ρ U ρ,r sin(β k ) ρ k + 1 + c 3 η 2 r ωr sin(αr) ρr + ψ r -c 2 ∇ α Ũα,r and
gα := - c 2 c 3 η 2 k ∇ α Ũα,r -c 1 η r ∇ ρ U ρ,r 1 + c 3 η 2 k sin(β k ) ρ k + c 3 η 2 k ψ r + 1 + c 3 η 2 r ωr sin(αr) ρr (17)
where α r = αr + α * r . We stress that ∇ ρ U ρ,r is a function of ρ r only and [∇ ρ U ρ,r ](0) = 0. Similarly, [∇ α Ũα,r ](0) = 0. Therefore, from the definition of g p we have g p (ξ p , 0) ≡ 0. Hence, based on cascaded-systems theory [START_REF] Loría | From feedback to cascade-interconnected systems: Breaking the loop[END_REF], [START_REF] Panteley | Growth rate conditions for uniform asymptotic stability of cascaded time-varying systems[END_REF], one can assert that if for every p ∈ [2, h + 1] the solution of ξp-1 = f p-1 (ξ p-1 ) converges to zero and if, for every p ∈ [2, h], the solutions of ξp = f p (ξ p ) + g p (ξ p , ξ p-1 ), denoted ξ p (t), remain bounded, we also have ξ p (t) → 0. This is established in our main statement.

Proposition 1 (Main result): Consider a multi-agent system composed of n unicycles, described by the m interconnected systems (1), interacting over a directed spanning tree G T and subject to distance and field-of-view constraints as defined by ( 2)-(3). The smooth time-invariant controller ( 9)-( 11) asymptotically achieves full consensus with connectivity maintenance, i.e., (ρ k , β k , α k ) → (0, 0, 0), and ρ k (t) ∈ J ρ and α k (t) ∈ J α , for all k ≤ m, all t ≥ 0, and for all initial conditions (ρ k (0),

β k (0), α k (0)) such that ρ k (0) ∈ J ρ \{0} and α k (0) ∈ J α .
The proof of this statement, which is omitted due to space constraints, follows arguments from cascaded systems' theory [START_REF] Loría | From feedback to cascade-interconnected systems: Breaking the loop[END_REF], [START_REF] Panteley | Growth rate conditions for uniform asymptotic stability of cascaded time-varying systems[END_REF], where convergence to the consensus manifold is concluded by establishing asymptotic stability for each nominal system and boundedness of the interconnections. Moreover, the connectivity and field-ofview constraints hold by showing that the barrier functions remain bounded along the trajectories of the system.

IV. SIMULATION RESULTS

To illustrate our theoretical results, some numerical simulations were performed in MATLAB. Furthermore, using the Gazebo-ROS simulator, we validated the connectivitymaintenance property of the proposed algorithm in a more realistic simulation scenario. A video with representative simulations accompanies this paper.

For the tests we consider six agents interconnected in a leader-follower topology (a directed spanning tree) as illustrated in Figure 3. For all the simulations, the controller parameters are fixed to c 1 = 0.2, c 2 = 1 and c 3 = 0.2, and the initial conditions were set to In Figures 4567are presented the MATLAB simulation results. It is clear from the figures that, the leader being static, the triple (ρ k , β k , α k ) converges asymptotically to the origin, meaning that full-consensus is achieved for the group of agents. Moreover, as can be evidenced from Figures 5 and6, both distance and field-of-view constraints are always respected. A smooth time-invariant distributed feedback controller is proposed in this paper that solves the problem of full consensus of a multi-vehicle system subject to distance and field-of-view constraints and interconnected through an arbitrary leader-follower (directed spanning tree) topology. Moreover, we show that the solutions of the multi-vehicle system remain bounded and the constraints are respected for all time instants, even when the leader agent's inputs are non-zero. Remarkably, using a polar-coordinates-based model, the proposed control law is smooth time-invariant and relies only on relative inter-agent variables, which renders it more suited for practical implementation and facilitates the analysis through Lyapunov and cascaded systems' theory. The effectiveness of the controller was asserted with numerical simulations and, in an accompanying video, using a realistic Gazebo-ROS simulator. Current and future work is focused on extending the results to 3D models and considering additional control objectives such as formation tracking and collision avoidance.

[x 1 (0), y 1 (0), θ 1 (0)] = [-4, 0, π/2] [x 2 (0), y 2 (0), θ 2 (0)] = [3.5, 0, 2.72] [x 3 (0), y 3 (0), θ 3 (0)] = [-

Fig. 1 .

 1 Fig. 1. Leader-follower scheme and polar-coordinates variables

Fig. 2 .

 2 Fig. 2. Directed spanning tree G T .

5 Fig. 3 .

 53 Fig.3. Labeled directed spanning tree graph. The leader is labeled as "1".

  11, 5, -0.21] [x 4 (0), y 4 (0), θ 4 (0)] = [-11, -5, 0.21] [x 5 (0), y 5 (0), θ 5 (0)] = [11, 5, -2.16] [x 6 (0), y 6 (0), θ 6 (0)] = [11, -5, 2.16]. The distance and field-of-view constraints are set, respectively, as ∆ ρ,1 = 8 m, ∆ ρ,2 = 8.8 m, ∆ ρ,3 = 8.7 m, ∆ ρ,4 = 9.3 m, ∆ ρ,5 = 9.5 m, and ∆ α,k = 25 • , k ≤ 5.

Fig. 4 .

 4 Fig. 4. MATLAB simulation -Full consensus with a static leader

Fig. 5 .Fig. 6 .

 56 Fig. 5. MATLAB simulation -Inter-agent distances. Dashed lines: distance constraints.

Fig. 7 .

 7 Fig. 7. MATLAB simulation -Angles β k .


Marc-Antoine Coppo
email: coppo@unice.fr

New identities involving Cauchy numbers, harmonic numbers and zeta values

Keywords: Cauchy numbers, harmonic numbers and zeta values Cauchy numbers, Roman harmonic numbers, binomial identities, series with zeta values, Ramanujan summation of series Mathematics Subject Classification (2020) 05A19, 11B75, 11M06, 40G99

HAL is

Introduction

Several years ago, we introduced a method based on the Ramanujan summation of series which enabled us to generate a number of interesting identities linking together Cauchy numbers (also known as Bernoulli numbers of the second kind), harmonic numbers and values of the Riemann zeta function at positive integers [START_REF] Candelpergher | A new class of identities involving Cauchy numbers, harmonic numbers and zeta values[END_REF]. Thanks to new formulas recently proved in our last paper [START_REF] Coppo | A note on some formulae related to Euler sums[END_REF], we can refine and improve these earlier results by providing new closed form evaluations of the same kind (see Proposition 1 and Corollary 1). In order to do this, we consider a natural generalization of the Roman harmonic numbers that were first introduced in [START_REF] Candelpergher | Le produit harmonique des suites, Enseign[END_REF] (see Definition 2), and use a general transformation formula that links the Cauchy numbers to the Ramanujan summation of series [START_REF] Candelpergher | Ramanujan Summation of Divergent Series[END_REF]Theorem 18]. A noteworthy fact is the presence in most of our formulas of certain alternating series with zeta values (see Definition 3) that recently appeared in different contexts [START_REF] Boyadzhiev | A special constant and series with zeta values and harmonic numbers[END_REF][START_REF] Coppo | A note on some formulae related to Euler sums[END_REF][START_REF] Dil | On values of the Riemann zeta function at positive integers[END_REF]. In the aim to help the reader to find his way among our various formulas, a summary of the most noteworthy identities, ranked in ascending order of complexity, is given in the penultimate section of the article.

Preliminaries : reminder of the main definitions and results

We first recall various definitions and results that appeared in our previous work, refering to the indicated references for the proof of these results.

Harmonic numbers

Definition 1. The generalized harmonic numbers H (r) n are defined for non-negative integers n and r by

H (r) 0 = 0 and H (r) n = n j=1 1 j r for n ≥ 1 . (1)
For r = 1, they reduce to classical harmonic numbers H n = H (1) n . The sums

S r,p = ∞ n=1
H (r) n,0 = 1 n r-1 and H (r) n,k = n≥j 1 ≥•••≥j k ≥1 1 j 1 j 2 • • • j r k for k ≥ 1 .
(

) 2
In particular, for k = 1, they reduce to classical generalized harmonic numbers

H (r) n,1 = H (r) n ,
and for k = 2, we have the expression

H (r) n,2 = n j=1 H (r) j j .
For r = 1, the harmonic numbers

H (1)
n,k will be noted H n,k in the remainder of the article.

Remark 1. The harmonic numbers H n,k are nothing else than the ordinary Roman harmonic numbers introduced three decades ago by Roman, Loeb and Rota (see [START_REF] Sesma | The Roman harmonic numbers revisited[END_REF] and the references to the original papers given inside). It is well-known (see e.g. [4, Eq. ( 18)], [10, Eq. ( 29)]) that the Roman harmonic number

H n,k = H (1)
n,k can be expressed as a polynomial in the generalized harmonic numbers H (1) n ,

• • • , H (k) n .
In particular, we have the expressions

H n,2 = n j=1 H j j = 1 2 (H n ) 2 + 1 2 H (2) n , (3)
and

H n,3 = 1 6 (H n ) 2 + 1 2 H n H (2) n + 1 3 H (2) n ( 4
)
that will be useful later on.

In addition, by Abel's lemma, we have the reciprocity formula (cf. [8, Eq. (2.2)])

n j=1 H (r) j j + n j=1 H j j r = H n H (r) n + H (r+1) n (r ≥ 1)
which leads to the useful relation

H (r) n,2 = H n H (r) n + H (r+1) n - n j=1 H j j r (r ≥ 1) . ( 5
)
The generalized Roman harmonic numbers

H (r)
n,k also verify the following binomial identity [5, Eq. (4.7)]:

H (r) n,k = n j=1 (-1) j-1 n j H j,r-1 j k (k ≥ 1) . ( 6
)
By inverse binomial transform 1 , formula (6) also admits a reciprocal: Example 1. For r = 1, formula (6) reduces to

H n,r-1 n k = n j=1 (-1) j-1 n j H (r) j,k (k ≥ 1) . ( 7
) 1. If b(n) = 1 n n j=1 (-1) j-1 n j j a(j), then a(n) = 1 n n j=1 (-1) j-1 n j j b(j) (cf.
H n,k = n j=1 (-1) j-1 n j 1 j k
which is a classical property of Roman harmonic numbers [10, Eq. ( 20)], and for r = 2, it may be written

H (2) n,k = n j=1 (-1) j-1 n j H j j k .
In particular, we have

H (2) n = n j=1 (-1) j-1 n j H j j and n j=1 H (2) j j = n j=1 (-1) j-1 n j H j j 2 .

Alternating series with zeta values

Definition 3 ([1, 6, 7]). The numbers τ p are defined for all positive integers p by the series representation

τ p = ∞ k=1 (-1) k+p ζ(k + p) k . ( 8
)
For p ≥ 2, they verify the following identity [1, Proposition 7], [6, Lemma 1]:

∞ n=1 ln(n + 1) n p = -ζ (p) -(-1) p τ p . ( 9
)
For p = 1, we have [1, Theorem 2 (a)]

τ 1 = 1 0 ψ(x + 1) + γ x dx ,
where ψ is the digamma function and γ = -ψ(1) is Euler's constant.

Cauchy numbers

Definition 4 ([2, 4, 9]). The classical Cauchy numbers c n are defined for n ≥ 1 by

c n = 1 0 x(x -1) • • • (x -n + 1) dx .
The Cauchy numbers alternate in sign. Using the notations introduced in [START_REF] Candelpergher | A new class of identities involving Cauchy numbers, harmonic numbers and zeta values[END_REF], we consider the sequence {λ n } n of non-alternating Cauchy numbers defined by

λ n = (-1) n-1 c n (n ≥ 1) .
The first terms of the sequence are the following:

λ 1 = 1 2 , λ 2 = 1 6 , λ 3 = 1 4 , λ 4 = 19 30 , λ 5 = 9 4
, λ 6 = 863 84 , etc.

Series with Cauchy numbers and Roman harmonic numbers

We first recall the transformation formula [START_REF] Candelpergher | Ramanujan Summation of Divergent Series[END_REF]Theorem 18] that links the Cauchy numbers to the Ramanujan summation of series: if a is a function analytic in the half-plane P = {Re(z) > 0} such that there exists a constant C > 0 with

|a(z)| < C 2 |z| for all z ∈ P , then ∞ n=1 λ n n! n n j=1 (-1) j-1 n j j a(j) = R n≥1 a(n) ( 10
)
where R n≥1 denotes the R-sum of the series i.e. the sum of the series in the sense of Ramanujan's summation method [START_REF] Candelpergher | Ramanujan Summation of Divergent Series[END_REF][START_REF] Candelpergher | A new class of identities involving Cauchy numbers, harmonic numbers and zeta values[END_REF]. In particular, using formula (6) and its reciprocal [START_REF] Dil | On values of the Riemann zeta function at positive integers[END_REF], we deduce from [START_REF] Sesma | The Roman harmonic numbers revisited[END_REF] the following reciprocal identities:

∞ n=1 λ n n! n H (r) n,k = R n≥1 H n,r-1 n k+1 (k ≥ 0, r ≥ 1). ( 11
)
and

∞ n=1 λ n n! n k+1 H n,r-1 = R n≥1 H (r) n,k n (k ≥ 0, r ≥ 1). ( 12
)
We can now state our main result.

Proposition 1. For any integer p ≥ 2, we have the following identities:

a) ∞ n=1 λ n n! n H n,p-1 = ζ(p) - 1 p -1 . (13) b) ∞ n=1 λ n n! n 2 H n,p-1 = γζ(p) + ζ(p + 1) -S 1,p -ζ (p) -(-1) p τ p -σ p ( 14
)
with

σ p = 1 + (-1) p p + p-2 j=1 (-1) j ζ(p -j) (j -1)!(p -1 -j)! (p -1)! - 1 j . c) ∞ n=1 λ n n! n H (2) n,p-1 = S 1,p - p-2 j=1 (-1) p-j j ζ(p -j) + (-1) p ζ (p) + τ p . ( 15
)
Proof. Applying (12) with r = p gives for k = 0

∞ n=1 λ n n! n H n,p-1 = R n≥1 H (p) n,0 n = R n≥1 1 n p = ζ(p) - 1 p -1 (cf. [3, Eq. (1.22)]), and for k = 1 ∞ n=1 λ n n! n 2 H n,p-1 = R n≥1 H (p) n n .
Hence formula ( 14) results from [6, Eq. ( 10)]. Specializing [START_REF] Wang | Euler sums and Stirling sums[END_REF]

with k = p -1 gives for r = 2 ∞ n=1 λ n n! n H (2) n,p-1 = R n≥1 H n n p .
Hence formula (15) results from [6, Eq. ( 6)].

Summing ( 14) and ( 15), we obtain the following corollary:

Corollary 1. For any even integer p ≥ 2, we have the relation

∞ n=1 λ n n! n 2 H n,p-1 + nH (2) n,p-1 = γζ(p) + ζ(p + 1) - p-2 j=0 (-1) j a j,p ζ(p -j) - 2 p ( 16
)
with a 0,p = 0 , and a j,p = (j -1)

!(p -1 -j)! (p -1)! for j ≥ 1 . Remark 2.
a) Since H n,0 = 1, formulae (13) and ( 14) also extend to the case p = 1 for which they reduce to the identities [START_REF] Boyadzhiev | New series identities with Cauchy, Stirling, and harmonic numbers, and Laguerre polynomials[END_REF][START_REF] Candelpergher | A new class of identities involving Cauchy numbers, harmonic numbers and zeta values[END_REF][START_REF] Merlini | The Cauchy numbers[END_REF]), and

∞ n=1 λ n n! n = γ (cf.
∞ n=1 λ n n! n 2 = 1 2 γ 2 - 1 2 ζ(2) + γ 1 + τ 1
where γ 1 is the first Stieltjes constant (cf. [6, Eq. ( 13)]).

b) Taking into account the identity (9), formula (14) can be seen as a refinement of [4, Eq. ( 27)].

Example 2.

For the first values of p, formulas (13), ( 14) and (15) translate respectively into the following identities:

1) For p = 2, ∞ n=1 λ n n! n H n = ζ(2) -1 , (17)
∞ n=1 λ n n! n 2 H n = γζ(2) -ζ(3) -ζ (2) -τ 2 -1 , ( 18
) ∞ n=1 λ n n! n H (2) n = 2ζ(3) + ζ (2) + τ 2 . ( 19
)
2) For p = 3,

∞ n=1 λ n n! n n j=1 H j j = ζ(3) - 1 2 , ( 20
) ∞ n=1 λ n n! n 2 n j=1 H j j = γζ(3) - 1 4 ζ(4) - 1 2 ζ(2) -ζ (3) + τ 3 , ( 21
) ∞ n=1 λ n n! n n j=1 H (2) j j = 5 4 ζ(4) -ζ(2) -ζ (3) + τ 3 . ( 22
)
Remark 3. a) Formula ( 17) is a well-known series representation for ζ(2) which seems to appear for the first time in [START_REF] Merlini | The Cauchy numbers[END_REF] (see also [START_REF] Boyadzhiev | New series identities with Cauchy, Stirling, and harmonic numbers, and Laguerre polynomials[END_REF] and [START_REF] Candelpergher | A new class of identities involving Cauchy numbers, harmonic numbers and zeta values[END_REF]). b) By means of (3), formula (20) can be rewritten under the following equivalent form:

∞ n=1 λ n n! n (H n ) 2 + H (2) n = 2ζ(3) -1 (23)
which coincides with [2, Eq. ( 9)]. Subtracting (19) from (23) enables to deduce easily another interesting identity:

∞ n=1 λ n n! n (H n ) 2 = -ζ (2) -τ 2 -1 . ( 24
)
c) Subtracting ( 18) from ( 24) and replacing H n -1 n by H n-1 inside this expression leads to the surprisingly simple relation

∞ n=1 λ n n! n H n H n-1 = ζ(3) -γζ(2) . ( 25
)
d) By means of [6, Eq. ( 14)] we can also prove the following dual formula of (22):

∞ n=1 λ n n! n n j=1 H j j 2 = 7 4 ζ(4) + ζ(2) + 2ζ (3) -2τ 3 -1 . (26)
Summing ( 22) and (26) and using the relation ( 5) with r = 2 leads to the following formula

∞ n=1 λ n n! n H (3) n + H n H (2) n = 3ζ(4) + ζ (3) -τ 3 -1 . ( 27
)
Furthermore, by applying (13) with p = 4 and using the polynomial expression (4), we have

∞ n=1 λ n n! n (H n ) 3 + 3H n H (2) n + 2H (3) n = 6ζ(4) -2 . ( 28
)
Thus, a simple comparison of ( 27) and ( 28) gives yet another interesting formula

∞ n=1 λ n n! n (H n ) 3 + H n H (2) n = -2ζ (3) + 2τ 3 . ( 29
)

Summary of main formulas

The most noteworthy identities are listed below in increasing order of complexity.

∞ n=1 λ n n! n H n = π 2 6 -1 (A) ∞ n=1 λ n n! n (H n ) 2 + H (2) n = 2ζ(3) -1 (B) ∞ n=1 λ n n! n H n H n-1 = ζ(3) -γ π 2 6 (C) ∞ n=1 λ n n! n 2 H n + nH (2) n = γ π 2 6 + ζ(3) -1 (D) ∞ n=1 λ n n! n (H n ) 2 = -ζ (2) -τ 2 -1 (E) ∞ n=1 λ n n! n H (2) n = 2ζ(3) + ζ (2) + τ 2 (F) ∞ n=1 λ n n! n 2 H n = γ π 2 6 -ζ(3) -ζ (2) -τ 2 -1 (G) ∞ n=1 λ n n! n (H n ) 3 + H n H (2)

Conclusion

Theoretically, the reciprocal identities ( 11) and ( 12) should allow us to compute a large number of infinite sums involving Cauchy numbers and (generalized) Roman harmonic numbers. Unfortunately, finding an explicit evaluation of the R-sums in the right-hand side of these identities remains a difficult task in most of cases. This highlights both the interest and the practical limits of our method.

  [5, Definition 5 and Corollary 1]).


domain: info spi

text:
Francis Lepage

René Kopp
email: rene.kopp@tdf.fr

Eric Gnaedinger

C Colombo

Seamless Multicast : an SDN-based architecture for continuous audiovisual transport Constant Colombo (Corresponding

Keywords: Multicast, Seamless, Real-time audiovisual stream, Disjoint trees, SDN, OpenFlow

For audiovisual network operators, end-users satisfaction is a major issue. This is the case for TDF who operates a nationwide network in France whose main purpose is to carry Digital Terrestrial Television (DTT) streams. Such audiovisual content is forwarded through multicast real-time streams which require continuity of service. Therefore, the main goal of this work is to define a new architecture to prevent impact during network healing time. The proposed architecture aims to use a pair of redundant multicast trees, and ensure their seamless resiliency. This architecture called "Seamless Multicast" takes advantage of the networkend equipment's ability to receive and combine two identical streams, complete or not. The main contribution of this paper is the development and evaluation of an algorithm for the computation of a pair of multicast trees and the associated hitless deployment scheme. Implementation requires an Software-Defined Networking (SDN) architecture, in which performance knowledge and bandwidth management are centralized in a controller. A proof of concept controller has been used for validation of the architecture's global behaviour using a virtualized environment in multiple scenarios.

Introduction

Availability and continuity of service are two of the main problematics addressed by network operators, as they directly impact the end-user degree of satisfaction. Availability is defined as the global uptime of a system over a period, while service continuity describes the uninterrupted uptime of a service.

TDF is a French network operator, whose main activity is to provide a transport infrastructure for realtime audio and video streams nationwide, specifically Digital Terrestrial Television channels (DTT) and national radios, from the recording studios to broadcasting antennas. TDF operates its own network which is disconnected from the Internet.

DTT streams are real-time, which implies not only that transport must be fast and stable, but also that data re-transmission is impossible. As a consequence, TCP-associated methods cannot be applied, and any failure on the network may create content impact. Enduser satisfaction can be studied using Quality of Experience (QoE) [START_REF]Vocabulary for performance, quality of service and quality of experience[END_REF] metrics, and addressed through Quality of Service (QoS) [START_REF]Terms and definitions related to quality of service and network performance including dependability[END_REF] tools. Usually, commitments on availability, latency, jitter, and loss are specified for each business customer in the Service Level Agreement (SLA). Based on Seamless Reception techniques, this works' goal is to exploit redundancy and resiliency to propose a new reliable transport architecture for continuous service. Seamless Reception is the set of techniques enabling packet selection and recombination from multiple identical data streams to provide an output without any apparent interruption, as illustrated in Fig. 1. The standard Seamless Protection Switching (SPS) [START_REF]Seamless Protection Switching of SMPTE ST 2022 IP Datagrams[END_REF] defines the combination process of two redundant streams into a single coherent stream, without any cut in case of data loss in the streams. Such techniques help enforce the continuity of service commitment specified in the SLA, in case of degradation or failure of one of the stream.

In this paper, Seamless Switching advantages are the basis for the proposed architecture, called Seamless Multicast. This architecture is bipartite : an novel algorithm is used to compute two redundant trees from the source of the stream to the set of destinations, and a novel deployment scheme ensures the dynamic hitless implementation of those multicast trees in a network.

The principle is the following. A pair of multicast transport tree is computed, both of them deployed as active, carrying the same data to the same set of destinations. Each destination receives the streams through Seamless Reception. Therefore, if only one of the stream is impacted by a failure, the destination still receives all the data. As such, the main computational objective is to find the pair of most independent trees. It can be easily demonstrated that the probability of simultaneous failure of both trees is minimal if both trees are independent. This scheme differs from backup mechanisms, as both trees are active at the same time and supply the same destinations. A major drawback lies in overall network bandwidth consumption, as twice more bandwidth is required for the same service due to data duplication. That is why the second main computational goal is to minimize the total bandwidth consumption.

While redundancy ensures a proactive protection in case of a simple failure, some destinations may not be protected whenever multiple failures occur. Similarly, when any failing element resumes functionning, the deployed multicast trees are not as optimal as they could Dest.

Fig. 2 Maximally independent delay-constrained trees be. That is why the Seamless Multicast architecture involves dynamic deployment. Furthermore, during any deployment, no impact should be visible. The scheme proposed in this paper enables hitless deployment in case of network component failure or recovery.

To summarize, the Seamless Multicast architecture not only builds the lightest pair of maximally independent redundant trees from the source of the stream to the destinations as illustrated in Fig. 2, but also ensures hitless dynamicity of those trees to account for multiple failures.

However, in order to implement and test the proposed architecture, traditional networking protocols are not adaptable enough. This paper also presents an actual implementation of the architecture through to SDN technologies.

Software-Defined Networking (SDN) [START_REF] Denazis | RFC 7426 : Software-Defined Networking (SDN): Layers and Architecture Terminology[END_REF] is a network paradigm in which the control plane and the data plane are physically isolated. An entity called "controller" handles routing and switching decisions while network nodes only perform data forwarding. Thanks to network programmability, any functionality can be implemented in a centralized fashion. This paper's SDN-based solution is illustrated in Fig. 3. The network is divided in four main planes : the application plane, describing service in a non-technical fashion, usually specifying an interface for the network operator ; the control plane, carried by the controller, where this paper's contribution resides ; the management plane, responsible for network management ; the data plane, which applies the controller's traffic forwarding decisions.

This paper presents the complete Seamless Multicast architecture and experimental validation. It is organized as follow: Section 2 presents the state of the art techniques for multicast reliable communications. In Section 3 industrial constraints are described and transposed into a new graph theory formulation. Related works on this specific multi-tree computation problem are reviewed. In Section 4, the proposed algorithm Iterative SHERPA (IS) is explained. Section 5 presents the novel dynamic scheme for trees deployment. The Seamless Multicast implementation using SDN is detailed 2 Related works on reliable multicast transport Solutions for reliable transport have been studied in the scientific literature and industry for various network architectures.

Interior Gateway Procotol (IGP), in other words rerouting, is the base of most traditional IP solutions, through dynamic computation or backup paths. The industrial standard Multicast VPN (MVPN) [START_REF] Rosen | RFC 6513 : Multicast in MPLS/BGP IP VPNs[END_REF] is a combination of the IGMP and PIM protocols, both relying on the IGP to establish a multicast tree and to ensure its resiliency. Rerouting-based resiliency schemes necessarily cause micro-cuts of the service, and thus impact the content viewing. Usually, buffers of the receiving equipment are designed to absorb a part of the rerouting time, but end equipment's' buffers are limited due to the real-time nature of the streams. As a consequence, the only solution would be to improve rerouting performance, which can be complex and costly.

Within the same industrial context as this paper, the method proposed [START_REF] Pirlot | IP/MPLS network modeling using Bayesian networks to improve double failure recovery[END_REF] by Pirlot et al. develops robustness through network survivability, and provides modeling tools for MVPN solutions to evaluate the protocol's reliability. Their works propose enhanced MVPN variants showing that improvement of a traditional architecture is possible but limited due to the aforementioned resiliency impact.

In a different context, Xiong and Chen propose a scheme for data-center environment based on multiple trees to ensure reliable multicast distribution [START_REF] Xiong | MTM: A Reliable Multiple Trees Multicast for Data Center Network[END_REF]. This trees are specifically computed for hierarchical network. Using rapid path rerouting through pre-computed multicast trees, loss is avoided. Consecutive network events are not considered, and impact cannot be avoided due to the computation time.

To ensure communication reliability over Networked Controlled Systems, a genetic algorithm to deploy two spanning trees is proposed by Kubler et al. [START_REF] Kubler | Dual path communications over multiple spanning trees for networked control systems[END_REF]. Though it ensures redundancy and protects the network thanks to redundancy, it is bandwidth-inefficient. In audiovisual networks, bandwidth consumption is a major issue.

Different SDN-based solutions can be found in the literature. A proactive backup path deployment scheme is proposed by Ghannami and Shao [START_REF] Ghannami | Efficient Fast Recovery Mechanism in Software-Defined Networks: Multipath routing approach[END_REF]. While this solution improves service availability, it is not based on multicast trees and is not bandwidth-efficient.

A reliable unicast solution is proposed by Vafaei et al. in [START_REF] Vafaei | QoSaware multi-path video streaming for urban VANETs using ACO algorithm[END_REF] for audiovisual streams. Similar QoS constraints are applied to a redundant path computation problem. The proposed Ant Colony algorithm is intended for Vehicular Networks (VANET), dynamic by nature, and tends to the real-time constraint through rapid rerouting. In these works, the independent path do not carry the same data, but two parts of the stream. As such, the bandwidth optimization goal is not considered.

A survey by Islam et al. [START_REF] Islam | A Survey on Multicasting in Software-Defined Networking[END_REF] highlights the challenges of the SDN-based multicast architectures, notably QoS and scalability, both in tree computation and node forwarding states. Other issues linked to the dynamic nature of some multicast uses, or distribution's security are also considered. This survey shows that SDN-based multicast proposal often aim to solve the customer subscription issue, which is not relevant in our case because the network operator TDF selects the source and destination of a service per customer's contract. The survey concludes that SDN approaches do not propose a general framework for multicast applications, but will enable the development of solutions for specific environments. In these works, we focused on architectures aiming to improve continuity of service under various constraints.

In [START_REF] Yen | PIM-compliant SDN-enabled IP multicast service[END_REF] Yen et al. propose an hybrid multicast solution. It integrates SDN architecture to traditional IP architecture using PIM. Though these works do not provide novel routing methods for reliable multicast, its goal is to interconnect the industry legacy standard to new solutions.

Most of the reliable multicast SDN-based solutions are either proactive or reactive. An architecture exploiting cached multicast trees for fast deployment is proposed by Kotani et al. in [START_REF] Kotani | A Design and Implementation of OpenFlow Controller Handling IP Multicast with Fast Tree Switching[END_REF]. Similarly, Renganathan et al. develop a subtree based approach, with precomputed segment reroutes in [START_REF] Renganathan Raja | A subtree-based approach to failure detection and protection for multicast in SDN[END_REF].

The works of Mohammadi et al. [START_REF] Mohammadi | A novel multicast traffic engineering technique in SDN using TLBO algorithm[END_REF] are very close to this paper's context : the objective is to exploit SDN technologies to provide reliable and optimized multicast transport solutions. The formulation of the Delay Constraint Least Cost tree problem (DCLC) involves similar constraints and optimization goal. The proposed approach uses a single multicast tree, and reactive rerouting. It showed greater performance than traditional IP solutions in terms of latency, jitter and packet loss, but continuity of service has not been studied in [START_REF] Mohammadi | A novel multicast traffic engineering technique in SDN using TLBO algorithm[END_REF].

The novelty of the proposal described in this paper is to approach absolute continuity of service by using both proactivity and reactivity. Seamless receivers are powered by multicast trees that are as independent as possible, under constraint delay, limiting bandwidth consumption and ensuring seamless redeployment in the event of a tree failure.

Audiovisual transport graph theory formulation

Audiovisual transport is associated with specific characteristics, and the first novel contribution of this work is to propose a formal definition of the addressed issue.

Problem statement

Multicast is a communication mode in which data are sent to a group of receivers in a single transmission using data duplication on the transport path. This differs from multiple unicast transmissions, that is to say data duplication at source level. As such, multicast communications rely on distribution trees. If network topology is modelled as a graph, tree computation methods from graph theory can be applied. A simple example is the spanning tree, a multicast connection to every node, efficient enough in simple topologies and computable using well-known algorithms.

This work was realized in collaboration with the network operator TDF, and the problem's constraints are induced by the context. The data to be transported form a continuous real-time stream. As a consequence, it must be carried without loss and within minimal delay.

Lossless transportation, in other words continuity of service, is the issue addressed by this paper's proposal. The concept is for each destination to be reached through two disjoint paths. The two paths carry identical streams, providing path diversity for Seamless Reception techniques. The complete set of paths forms a multicast tree, in which pair of paths must be independent. Given real network topologies, totally disjoint paths are not always possible. For example, some areas may be reachable by a unique path for geographic reasons. This means a Single Point of Failure is unavoidable in some areas of the network. Therefore, pathdisjointedness is not required to be strict in the problem statement.

The minimal-delay constraint is a global service limitation : from the source to any destination, a delay threshold value must be respected. This constraint is usually specified in the SLA, and emerges from the realtime nature of the data. In practice, each edge of the graph will be set with the maximum link delay measured over a significant period, to ensure that the delay threshold will not be violated over the real network because of jitter.

Finally, as the network carries multiple services for different customers, bandwidth management must be considered. A minimum of total bandwidth must be consumed per service. This constraint is one of the reasons for using only two multicast trees for path diversity. While more redundancy would improve the system, the bandwidth cost is too important. In practice, prior to any computation, links that have insufficient available bandwidth are removed from the usable topology.

Given the goal and constraints, the problem is stated as finding Delay-constrained Minimal Destination maximally-disjoint Trees (DMDT).

DMDT proposed cost function

In a directed graph G 0 = (V, E), with V the set of vertices and E ∈ V 2 the set of edges, weighted by C 0 and D respectively link-cost and link-delay, given a delay constraint ∆, the DMDT problem's goal is to find for a source s and a destination set T a pair of trees A R and A B connecting s to T , maximally-disjoint per destination and globally lightest.

Let R and B denote the two binary vectors corresponding to the trees A R and A B . Each element of those vectors represents a link (x, y) ∈ E. Their value is 1 if the link belongs to the tree, 0 otherwise. Let Z denote a vector which elements represent the usage of links in both A R and A B to reach the same destination. Values of Z(x, y) range from 0 to |T |, because each time a link is used by both trees to reach a destination, Z(x, y) is increased by 1.

The cost function ( 1) is composed of three terms. The first two are the sum of each tree's weight, and the third one represents the cost of inter-dependence between the trees.

F(R, B) = (x,y)∈E C 0 (x, y)R(x, y) + (x,y)∈E C 0 (x, y)B(x, y) + 2 (x,y)∈E C 0 (x, y) (x,y)∈E Z(x, y) (1)
Using twice the total weight of the graph as a coefficient gives a greater importance to independence. The cost optimization becomes secondary. This is proven in Theorem 1.

Theorem 1 Let β RB denote the sum of Z values for a given pair of trees A R , A B . ∀A 1 , A 2 ⊂ E and associated β 12 ≥ 0, ∀A 3 , A 4 ⊂ E and associated β 34 ≥ 0, If β 12 < β 34 then: C 0 (A 1 ) + C 0 (A 2 ) + β 12 * 2 * C 0 (E) < C 0 (A 3 ) + C 0 (A 4 ) + β 34 * 2 * C 0 (E) (2)
Proof.

Given G 0 = (V, E) a graph weighted by C 0 ≥ 0, ∀A ⊂ E, A = ∅, 0 < C 0 (A) ≤ C 0 (E) ⇒ 0 < C 0 (A i ) + C 0 (A j ) ≤ 2C 0 (E), ∀A i , A j ⊂ (E) (3) ∀A 1 , A 2 ⊂ E and associated β 12 ∈ N + , A 1 = ∅, A 2 = ∅, ∀A 3 , A 4 ⊂ E and associated β 34 ∈ N + , A 3 = ∅, A 4 = ∅, 0 ≤ β 12 < β 34 ⇒ β 12 + 1 ≤ β 34 as β 12 , β 34 ∈ N + ⇒ β 12 * 2C 0 (E) + 2 * C 0 (E) ≤ β 34 * 2C 0 (E) as C 0 (E) > 0 ⇒ β 12 * 2C 0 (E) + C 0 (A 1 ) + C 0 (A 2 ) ≤ β 34 * 2C 0 (E) according to (3) ⇒ β 12 * 2C 0 (E) + C 0 (A 1 ) + C 0 (A 2 ) < β 34 * 2C 0 (E) + C 0 (A 3 ) + C 0 (A 4 ) as C 0 (A 3 ) > 0 and C 0 (A 4 ) > 0
This proposed formulation of the cost function does not guarantee the absence of cycles nor multiple paths to a single node. Nevertheless, the minimization of the function eliminates this issue, as pseudo-trees with cycles or multiple path will have a higher cost. The optimal solution does not contain any by definition.

N P-hardness

The DMDT problem is N P-hard and this section focuses on its proof.

Theorem 2

The DMDT problem is N P-hard.

Proof.

The MDP problem of finding Maximally-independent Delay-constrained Paths is N P-hard as proven by Orda and Sprintson [START_REF] Orda | Efficient algorithms for computing disjoint QoS paths[END_REF].

The MDP problem is a special case of the DMDT problem. Using the following DMDT definition: find a minimal pair of redundant trees connecting a root node to |T | destinations, delay-constrained, in which internal paths to a destination are maximally-independent ; for |T | = 1, the DMDT problem becomes an instance of the MDP problem. By generalization of the MDP problem which is N P-hard, the DMDT problem is itself N P-hard.

In practice, N P-hardness means that it is impossible to guarantee finding an optimal solution fast. In other words, either a solution is found quickly with the hope that it is satisfying for the application, or the computation of an optimum is fast enough to match the application constraints. In this paper, we propose a heuristic to solve the DMDT problem meeting the computation time constraint of the architecture's deployment mechanism presented in Section 5.

Related works on DMDT computation

In order to solve the DMDT problem, literature provides no method as far as we know. Nevertheless, to compute a single delay-constrained multicast tree, many heuristics have been proposed such as by Forsati et al. [START_REF] Forsati | An efficient algorithm for bandwidthdelay constrained least cost multicast routing[END_REF], and even an exact solution by Feng [START_REF] Feng | Delay constrained multicast routing: What can we learn from an exact approach?[END_REF].

Medard et al. proposed an algorithm to compute redundant trees in an edge-redundant graph [START_REF] Medard | Redundant Trees for Preplanned Recovery in Arbitrary Vertex-Redundant or Edge-Redundant Graphs[END_REF], that is to say when it is guaranteed that two completely independent paths can be found between any pair of vertices in the graph. The proposed algorithm can account for costs and a delay constraint. However, this work relies on undirected graphs, while within our context we consider different costs on each direction of a link, as audiovisual content-providing services are unidirectional. Furthermore, the edge-redundant graph requirement is not met in practice, and thus the algorithm cannot be used.

Bejerano et al. intended to provide another algorithm [START_REF] Bejerano | Optimal construction of redundant multicast trees in directed graphs[END_REF][START_REF] Bejerano | Efficient Construction of Directed Redundant Steiner Trees[END_REF][START_REF] Bejerano | Link-coloring based scheme for multicast and unicast protection[END_REF]. This method relies on directed graphs to result in close to optimal solutions, but does not consider any delay constraint and requires graphs with too specific properties.

Architecture's dedicated routing algorithm

In order to solve the DMDT problem, the proposed heuristic uses a delay-constrained shortest path algorithm (CBF) from the literature [START_REF] Widyono | The design and evaluation of routing algorithms for real-time channels[END_REF], and a newly proposed delay-constrained shortest pair of path algorithm (SHERPA).

Delay-constrained shortest path algorithm

For this work, the Constrained Bellman-Ford algorithm (CBF) [START_REF] Widyono | The design and evaluation of routing algorithms for real-time channels[END_REF] has been selected. It is based on the Bellman-Ford algorithm [START_REF] Bellman | On a routing problem[END_REF].

The CBF algorithm is a breadth-first search, discovering paths with increasing delay while recording the shortest path to each node visited, until the exploration cumulative delay exceeds the delay constraint.

SHaring-Edges Restrained PAths -SHERPA

In a graph G 0 = (V, E), for a given pair (s, t) ∈ V × V , the SHaring-Edges Restrained PAths (SHERPA) [START_REF] Colombo | SHERPA: A SDN Multipath Approach to Eliminate Resilience Impact on Video Streams[END_REF] algorithm's goal is to find two lightest delay-constrained maximally edge-disjoint paths from s to t. It is based on the Suurballe-Tarjan algorithm [START_REF] Suurballe | A quick method for finding shortest pairs of disjoint paths[END_REF], which does not account for delay constraint and ensures only strict disjointedness. To create the proposed algorithm, it has been altered in two ways. Firstly, the shortest path algorithm used (Dijkstra's algorithm) has been replaced by the delay-constrained algorithm CBF. The second modification consists in a re-weighting scheme imposing a maximal weight on some links to provide relaxed disjointedness.

In the original algorithm, links that belonged to the first computed path were deleted from the graph in order to compute the second independently. Instead, in our proposed variant, such links are only made prohibitive to use for a second path computation. Any other link is weighted following the Suurballe-Tarjan scheme, that is to say subtracting from their original cost the difference of distance from the source of their ending point and starting point.

For a directed graph G 0 = (V, E) weighted by C 0 , let d(v) denote the cost in C 0 of the shortest path from v ∈ V to s. Let P a denote the set of links of the first computed delay-constrained path, whose weight is to be made prohibitive. The new graph cost C 1 of G 0 is defined by equation ( 4) ∀(x, y) ∈ E :

C 1 (x, y) = e∈E e C 0 (e) if (x, y) ∈ P a C 0 (x, y) -d(y) + d(x) otherwise ( 4
)
For a directed graph G 0 = (V, E) weighted by C 0 and D respectively cost and delay, a source s, a destination t and a delay constraint ∆, the SHERPA algorithm can be summarized as follows:

1. A first delay-constrained shortest path P a is computed from s to t; 2. The graph is re-weighted following equation (4); 3. A second delay-constrained shortest path P b is computed from s to t; 4. P a ∪ P b contains the two paths after sort out operations.

The complete procedure is detailed in Appendix A, Algorithm 1 and it is illustrated in Fig. The two paths are as independent as possible, while not using the link d -c, which would provide more independence but would also violate the delay constraint.

Based on the Suurballe-Tarjan algorithm's variation for node-disjointedness, our proposed algorithm SHERPA is adjustable to find delay-constrained maximally node-disjoint paths. This variation can be used in higher level algorithms aiming to find node-disjoint trees.

The SHERPA algorithm allows to find a pair of paths, and is used in the novel IS algorithm presented below.

Iterative SHERPA -IS

The proposed algorithm to solve the DMDT problem is based on the multipath algorithm SHERPA. It is called Iterative SHERPA (IS) [START_REF] Colombo | Two SDN Multi-tree Approaches for Constrained Seamless Multicast[END_REF]. IS iteratively computes pairs of paths using SHERPA, and assigns them to the trees according to the maximum independence provided.

The IS procedure relies on iterations of the SHERPA algorithm. An instance of the SHERPA algorithm runs for each destination not yet reached by the trees to provide a pair of paths starting at the trees' root (i.e. the source node). Then, in increasing pair-cost order, each path of a pair is assigned to one of the trees so that independence is maximal between the newly completed trees. If the provided independence is equal for both possible affectations, no decision is made and the affected node is skipped to be processed in later iterations. When all nodes have been processed, if all remaining nodes cannot be assigned, an arbitrary decision is made and the algorithm resumes. This process is repeated until all destinations are reached by the trees.

Destinations are processed in increasing pair-cost order, so that the algorithm can be deterministic. Better solutions could be found using a different order, but determinism is a major issue for practical use and network management.

Node-disjointedness can be achieved by using the node-disjoint variation of SHERPA algorithm, and by estimating the best path assignation using the number of common vertices instead of common edges.

The proposed IS scheme ensures maximal path diversity per destination. Path cost is minimized, but total tree cost is not guaranteed to be minimized, as path affectation only depends on independence. The complete procedure is detailed in Appendix A, Algorithm 2. The algorithm is illustrated in Fig. 5. Original graph representation and constraints are described in Fig. 5a. The IS algorithm builds a solution using node r as source, and a, d, e as destinations. According to the algorithm, the pairs of paths computed are illustrated in Fig. 5b, 5d and 5f, and assigned respectively in Fig. 5c, 5e and 5g.

Validity of the solutions

The process of the IS algorithm as presented is incomplete. Indeed, cycles or multiple path to a same node may appear in the two computed trees, making them pseudo-trees. There is no guarantee that the provided solution is a pair of valid trees : a tree is defined as an acyclic graph, containing unique paths from the root to each node. The IS computational process only provides a solution in which all target nodes are reached while matching the delay constraint on at least one of each path to each destination.

To ensure the validity of the results, two supplementary steps are necessary : cycles removal, and unique path selection.

Through a Depth First Search (DFS), cycles are identified and eliminated : during the search, if an already visited node is met, it means that the last used edge belongs to a cycle, goes towards the root of the tree and thus should be removed. A new iteration of the DFS rooted to the source is then started. During this removal process, 2-length cycles are processed as special cases. 2-length cycles are defined as cycles between only two nodes.

It has been observed in practice that such cases require specific treatment. Firstly, they are processed as every other cycle and kept in memory for later refinement. Once all cycles have been processed, that is to say when the DFS performs complete graph exploration, a new procedure is applied to every 2-length cycle previously met.

Algorithm 3 details the procedure. The principle is the following : both links are examined, and if one of them is required for the tree to be continuous, this link is preserved in the final solution. Otherwise, the shortest-delay path between the two nodes is kept, to ensure that the delay constraint is not violated. Note that this scheme may provide a wrong solution when multiple consecutive 2-length cycle happen in the pseudotree, but this case has rarely been observed in practice.

Once cycles are removed, unique path selection must be performed for the solution to be a valid pair of trees. For any vertex with more than two predecessor in a tree, the shortest-delay path from source is found and only the predecessor matching this path is kept. All other unnecessary edges are removed, that is to say tree branches not leading to a target node. Appendix A, Algorithm 4 details the procedure.

To summarize, to obtain a valid solution from the IS algorithm solution, the following process must be applied :

-DFS rooted at the trees' source is performed to find and break cycles while keeping in memory 2-length cycles met ; -2-length cycles are processed for final selection ; -Multiple paths are eliminated through shortest-delay selection, and useless branches removed.

IS algorithm evaluation

Within TDF network, some multicast services already exploit path diversity. Those services have been used as comparison points to evaluate the performance of the IS algorithm against existing solutions. The network is composed of 928 nodes and 1960 unidirectional links. 43 representative services have been selected for this experiment. The network and affiliated services are subject to trade secret protection and are therefore not further detailed in this paper.

For each existing service, the pair of maximallyindependent trees was designed by experienced network engineers. Within the constrained context of this problem, these human-designed pairs of trees are considered as pseudo-optimums, given that human methods are not able to find better solutions.

The cost function presented in equation ( 1) is used to evaluate human solution versus the IS-found solution. Results show that in 18 cases the IS-found solution is better, either by bandwidth consumption fine optimization or significant improvement of independence. In 17 cases, it is identical or equivalent to the humanfound solution.

A notable element is that existing services all supply a limited number of destinations (generally inferior to 14), otherwise the problem is to complex to be examined by humans. Therefore, not only the IS algorithm can generally provide better solutions, always faster than a human could, but it can also be applied to problems that were de facto excluded by the operator.

Architecture's deployment mechanism

The proposed Seamless Multicast architecture aims to be resilient to multiple failures. Thanks to path diversity, destinations are protected against a single failure. Given maximal path independence, if a failure occurs at least one of the path is still active. But a second failure may occur on this path, and interrupt the stream transportation. In this section, a dynamic scheme for trees' deployment is presented to overcome this drawback. The purpose of this scheme is to ensure that, at any time, a complete pair of trees is deployed on the network, never leaving a destination unsecured.

Traditionally, in case of failure, resilient transport protocols use full path rerouting, segment rerouting or failover components. In the case of multicast protocols, rerouting solutions may be used, for example in the MVPN standard [START_REF] Rosen | RFC 6513 : Multicast in MPLS/BGP IP VPNs[END_REF]. Nevertheless, this raises some issues : in our case, rerouting implies a loss in the optimality of the solution, and eventually a divergence from the expected transport topology following network's evolution. Failover solutions are also being developed in multicast protocols as in [START_REF] Morin | Multicast VPN fast upstream failover[END_REF].

The objective of the deployment mechanism is to always come back to the assumed optimal state without any impact during transitions. To this end, we propose a successive tree switchover scheme. Indeed, a simple failover mechanism to a new pair of trees would imply an impact. The idea is the following: when the network topology changes, a new pair of tree is computed. If necessary, path rerouting is used to ensure that at least one of the previous trees is reaching all destinations. Then, each previous tree is successively switched to one of the newly computed trees. As a result, there is at any time at least one complete tree supplying the stream to every destination, and in the end the transport topology is optimal. This scheme applies similarly for failures, recovery or network additions. Fig. 6 describes the mechanism and its operation is shown in Fig. 7. Destinations are reached by a pair of trees A R and A B . When the link from d to e fails, the A R tree is reconnected, a new pair of trees is computed, the A B tree is switched to a new version while the A R tree sustains the stream, and finally the A R tree is switched to a new version while the A B tree ensures service continuity.

SDN Implementation

In order to further validate and evaluate the proposed Seamless Multicast architecture, we developed a Proof of Concept SDN controller for experimentation. SDN is a network architecture aiming at programmable networks. The control plane, traditionally distributed in network nodes, is centralised in the entity called controller. In more advanced designs, the controller can be distributed over a control network. This controller collects data on the network through the management plane, and receives input from the network operator. Network nodes are only applying rules defined by the controller's behaviour. The programmability of the network comes from this behaviour, implemented as software in the controller.

The concept of a centralized network architecture is not new, but it recently became more popular and standardized [START_REF] Denazis | RFC 7426 : Software-Defined Networking (SDN): Layers and Architecture Terminology[END_REF]. New technologies are being developed in both the research community and the industry, a good example of which being the Open Networking Foundation.

Due to their flexibility, SDN architectures have been considered for Internet, for example IXP connection [START_REF] Antichi | ENDEAVOUR: A Scalable SDN Architecture For Real-World IXPs[END_REF][START_REF] Bruyere | Rethinking IXPs' Architecture in the Age of SDN[END_REF], but also for Smart Grid energy networks [START_REF] Gyllstrom | Recovery from link failures in a Smart Grid communication network using OpenFlow[END_REF][START_REF] Dorsch | Enhanced Fast Failover for Software-Defined Smart Grid Communication Networks[END_REF], VoIP applications [START_REF] Hasrouty | SDN-Driven Multicast Streams with Adaptive Bitrates for VoIP Conferences[END_REF], or even data-center environment [START_REF] Shukla | MCDC: Multicast routing leveraging SDN for Data Center networks[END_REF].

OpenFlow

The OpenFlow protocol [START_REF] Mckeown | OpenFlow: Enabling Innovation in Campus Networks[END_REF], is a technology providing an abstraction layer between the controller and the network nodes.

OpenFlow uses a set of rules called Flows. Each Flow is a combination of a Match, Actions, and statistics. The Match is an identification filter, based on multiple criterion not requiring payload inspection. For example, a Match could be on protocol type, network addresses, incoming port... The Actions belong to a predetermined set, notably including "forwarding", "dropping" or "altering a frame's header". The Actions of a Flow are applied to every data unit filtered by the Match. OpenFlow defines a set of Actions, but not their implementation. As such, vendors retain a competition leverage on performance.

The OpenFlow protocol specifies the communication between network nodes and the controller. The controller can specify Flows, and send them to the nodes. The nodes apply those Flows, and may send to the controller packets that do not match any to ask for new Flows.

Newer versions of the OpenFlow protocol offer more functionalities, notably the Fast Failover Groups from specification 1.1. They are not used in this work, and are not further detailed. Our mechanism only requires elements existing from specification 1.0.

Seamless Multicast Controller

PCE-based architectures are specified in RFC 4655 [START_REF] Farrel | RFC 4655 : A path computation element (PCE)-based architecture[END_REF] as architectures in which an entity ensures the computation of network routes with various constraints. This entity called the Path Computation Element (PCE), can be located on a network component or out of the network. An overview of the usage of PCE-based architectures in the literature has been published by Paolucci et al. [START_REF] Paolucci | A Survey on the Path Computation Element (PCE) Architecture[END_REF]. This paper's proposed SDN architecture is PCEbased. The PCE is part of the controller, and is based on the IS algorithm presented in Section 4. The logical architecture of our controller is summarized in Fig. 8. A northbound interface connects the network controller to a GUI for operator usage, while a southbound interface enables the controller to communicate with the network elements.

Experiments and Results

For experimental purposes, the controller's implementation is based on the POX controller [START_REF]POX Controller[END_REF]. It deploys Flows matching on VLAN tagging, forwarding on one or multiple ports. Each VLAN tag is associated with one of the two trees of a pair, and the forwarding ports depend on the path computed by the PCE. As a result, for a given service (i.e. source and set of destinations), there are at most 2 rules per switch.

Validation experiments are led using Mininet [START_REF] Lantz | A Network in a Laptop: Rapid Prototyping for Software-Defined Networks[END_REF], a tool for network virtualization. The operating system used for nodes is Open vSwitch [START_REF] Pfaff | The Design and Implementation of Open vSwitch[END_REF]. Links' behaviour is emulated using Linux Traffic Control tool.

In order to validate the controller's behaviour, two identical IP streams are forged and sent simultaneously through the network. Each forged packet contains an identifier. Endpoints (i.e. destinations) listen for the two streams, and account for each packet. Consequently, missing or delayed packets are identified, and an elementary Seamless interpretation can be made.

Even though the IP stream are forged and random data are used for padding, the whole infrastructure is real. Mininet provides a virtualization environment, it is not a simulator. This means that even though nodes perform switching faster or slower than real equipment (depending on the physical host), their behaviours are identical. Furthermore, the controller implementation is real (given it is only software), and is connected to the virtual nodes as it would be on a real network.

Various scenarios were tested. Due to space constraint and readability, only one of those will be presented in this paper. The scenario and results are summarized in Fig. 9. The initial state is illustrated in Fig. 9a : the northern node is the source (i.e. where the two streams are emitted), and the two southern nodes in grey R1 and R2 are the destinations, listening for the streams. The controller initially deploys two trees : A R in red dashed lines, and A B in blue full lines. The link R1 -R2 will be the failure location, emulated through Mininet commands.

Fig. 9h illustrates data reception from R1 and R2 for each stream carried by A R and A B . The black arrows represent stream synchronisation. In other words, an arrow links two received packets with the same identifier. For ease of reading, each link of the topology has a delay of 1 second.

In the initial state Fig. 9a, both R 1 and R 2 receive the two streams. Streams are not synchronized due to different transport path. When the failure occurs in Fig. 9b, each node only receives one stream. The Seamless function ensures the continuity of service, hence no content should be lost. According to the deployment mechanism, the tree A B is rapidly connected in Fig. 9c. Both destinations now receive the stream from the tree

A B .
Once the new version of the pair of trees has been computed by the PCE, the tree A R is deleted and deployed in its new version in Fig. 9d and Fig. 9e. The reception of the stream from the tree A B on both destination ensures the continuity.

Similarly, the tree A B is also deleted and deployed in Fig. 9f and Fig. 9g, even though in this simple case it is identical to the temporary version. This example illustrates the deployment mechanism in practice, and shows the valid implementation behaviour.

Even though this implementation is an efficient proof of concept for the Seamless Multicast, multiple implementation issues must be addressed for industrial deployment. The main one is the timing of deployment operations. For example, during dynamic switchover operation, acknowledgement of first tree deployment from the network nodes must be received by the controller before deleting and deploying the second tree. Otherwise, some destinations may be cut off from both streams. However, OpenFlow does not support such acknowledgment. The implementation used in this work uses various timers, tuned according to network characteristics. The implementation and experimentation provided in Section 6 prove the feasibility of the Seamless Multicast architecture. It also shows that, as intended, for single failure cases, the Seamless Multicast provide a continuity of service that is not expected from the MVPN standard.

To further illustrate the enhancement provided by the Seamless Multicast architecture, we evaluate the availability of the service at each delivery node. To provide an estimation, we will use the data from [START_REF] Pirlot | Survivabilité dans les Réseaux de Transport de Vidéo et d'Audio sans Dégradation de la Qualité Perçue par l'Utilisateur[END_REF], where the same industrial issue is addressed through traditional network techniques, notably the MVPN standard. As stated, the values presented are representative but not real for trade secret protection.

In [START_REF] Pirlot | Survivabilité dans les Réseaux de Transport de Vidéo et d'Audio sans Dégradation de la Qualité Perçue par l'Utilisateur[END_REF], Pirlot provides useful but non trivial techniques to accurately estimate the availability of a system using Bayesian networks. Such studies are considered for future works. For this paper's estimation, we use the following reasoning : the unavailability of the Seamless Multicast is equivalent to the simultaneous failures of both trees, or at least failures within a short segment of time corresponding to the A 34 and A 56 in-terruptions from Fig. 6. To upper bound a tree's availability, we use the value for a RSTP tree : a single tree, sub-optimal given our constraints, and as it is a spanning tree, it is much more prone to partial failure than one of the trees computed through the IS algorithm.

Let A SM denote the availability of the Seamless Multicast, A A R and A A B the availability of the trees A R and A B , and A RST P the availability of an RSTP tree. Let P denote the respective failure probabilities.

A SM = 1 -P SM = 1 -P A R * P A B = 1 -(1 -A A R ) * (1 -A A B ) = 1 -(1 -A RST P ) 2 (5)
Based on values provided in [START_REF] Pirlot | Survivabilité dans les Réseaux de Transport de Vidéo et d'Audio sans Dégradation de la Qualité Perçue par l'Utilisateur[END_REF] for what is described as a multicast real case A RST P = 0.995651019. Using this value, Table 1 illustrates the improvements provided by the Seamless Multicast. Nearly 18 hours of availability are gained, in other words an improvement of 99% in availability. Such large numbers are not surprising : the cost of the Seamless Multicast solution is the utilization of twice as much bandwidth, and the implementation of a SDN architecture. Further works could provide a more complete and precise comparison. For example, the mean time of a failure, the convergence time for MVPN, is a parameter to be studied. For audiovisual content, the length of a impact is a matter of QoE, which requires appropriate measurements.

Conclusion

In this paper we proposed a new SDN-based architecture called Seamless Multicast, which exploits redundant trees to ensure that a real-time audiovisual stream is transported without interruption from a source to multiple destinations. We proposed a centralized algorithm Iterative SHERPA (IS) to compute maximally edge or node-independent delay-constrained trees. This algorithm is associated with a dynamic switchover mechanism in case of topology change, to guarantee continuity of service and optimisation.

The network programmability provided by SDN architectures allows for the redundancy algorithm and the dynamic switchover mechanism to be deployed in practice. We validated the Seamless Multicast using a Proof of Concept controller implementation over a virtual network. The proposed SDN-based architecture enables continuous transport of audiovisual streams.

Regarding scalability, the proposed IS algorithm is scalable to larger network, and experiments have shown a less than 10 s computation time on the studied network largest cases. This performance is a major improvement for the industry. The dynamic switchover mechanism itself is only limited by the deployment time of the OpenFlow rules. Even though the number of OpenFlow rules is limited in our proposal, the connection to multiple network nodes for rule installation may be the time-limiting element of the architecture. Henceforth, the Seamless Multicast is scalable to larger networks, and must be tuned to account for control delay.

Finally, even though some technology compatibility issues must be addressed for complete industrial deploy-ment, experiments have shown the expected continuity of service provided by the Seamless Multicast.

A Complete algorithms

This appendix presents the complete details of the different algorithms proposed and used in this paper.

Algorithm 1 SHERPA -Sharing-Edges Restrained Paths

Input: A directed graph G 0 = (V, E) weighted by C 0 an D respectively cost and delay, a source s, a destination t and a delay constraint ∆. Output: Two paths P A and P B as disjoint as possible, delay-constrained, shortest from s to t.

Fig. 1

 1 Fig. 1 Seamless Reception concept

Fig. 3

 3 Fig. 3 Architecture Overview

4 .

 4 In the example presented in Fig 4a, the goal is to connect the node s to the node t, with two maximally-independent paths under the delay constraint of 5s. Every link has a delay of 1s except d -c. Fig 4b illustrates the first path P R computed using CBF. The graph is re-weighted in Fig 4c according to the SHERPA algorithm. The most notable element is the prohibitive weight of the links s -b, b -c and c -t, which were part of the path P R . The second path P B is computed by CBF and illustrated in Fig 4d.

Fig. 4

 4 Fig. 4 SHERPA illustration

Fig. 5

 5 Fig. 5 IS Illustration

D2Fig. 6

 6 Fig. 6 Deployment mechanism

Fig. 7

 7 Fig. 7 Dynamic switchover illustration

Fig. 9

 9 Fig. 9 Sample representative result from experiment led with Proof of Concept Seamless Multicast Controller

Table 1

 1 MVPN vs Seamless Multicast Comparison

		MVPN	SM
	Availability	0.997858060	0.999981086364
	Yearly failure (h)	18.7633944	0.165683449068
			Never, except if
	Single failure impact	Always	failing link is the single existing
			path
	Overall
	Bandwidth	Simple	Double
	Consumption
	Network	Traditional	SDN

  1: for v ∈ V do 2:P ← CBF (G 0 , s, v, ∆) 3:d 0 (v) ← C(P ) 4: end for 5: P a ← CBF (G 0 , s, a, ∆)6: G 1 ← G 0 residual graph weighted by C 1 7: C 1 ← C 0 8: for (x, y) ∈ E do 9: C 1 (x, y) = C 0 (x, y) -d 0 (y) + d 0 (x)10: end for 11: C total ← i∈E C 0 (i), total weight of G 0 12: for (x, y) ∈ P a do 13: C 1 (x, y) ← C total 14: C 1 (y, x) ← 0 15: end for 16: P b ← CBF (G 1 , s, t, ∆) 17: S ← P a ∪ P b 18: S AB ← P a ∩ P b 19: for (x, y) ∈ P a do 20: if (y, x) ∈ P b then P B ← S ∪ S AB 36: return P A , P B Algorithm 2 IS -Iterative SHERPA Input: A directed graph G 0 = (V, E) weighted by C 0 an D respectively cost and delay, a source s, a set of destinations T and a delay constraint ∆. Output: Two trees A R and A B as link-disjoint as possible, delay-constrained, lightest from s to T . 1: A r ← ∅ 2: A b ← ∅ 3: p ← |T | 4: p prev ← |T | 5: P P ← ∅ 6: for t ∈ T do 7: P t,A , P t,B ← SHERP A(s, t, ∆) 8: P P ← P P ∪ {(P t,A , P t,B )} 9: end for 10: Optional : arrange P P 11: while P P = ∅ do 12:(P A , P B ) ← F irst(P P ) 13:if p = p prev then 14:A r ← A r ∪ P A 15:A b ← A b ∪ P B 16:P P ← P P \ {(P A , P B )} A , P B ) ∈ P P do 22: if |(A r ∪P A )∩(A b ∪P B )| > |(A r ∪P B )∩(A b ∪P A )| then 23: A r ← A r ∪ P A 24: A b ← A b ∪ P B 25: P P ← P P \ {(P A , P B )} 26: else if |(A r ∪ P A ) ∩ (A b ∪ P B )| < |(A r ∪ P B ) ∩ (A b ∪ P A )| then 27:A r ← A r ∪ P B 28:A b ← A b ∪ P A A R ← Ref inement(A r ) (Alg. 3) 37: A B ← Ref inement(A b ) (Alg. 3) 38: return A R , A B

	21: 22: 23: end for S ← S \ {(x, y), (y, x)} end if 24: P A ← ∅ 25: v ← t 26: while v = s do 27: for (x, y) ∈ S do 28: if y = v then 29: S ← S \ {(x, y)} 30: P A ← P A ∪ {(x, y)} 31: v ← x 32: end if 33: end for 34: end while 35: 17: 18: 19: 20: 21: for (P 29: p ← 0 else p prev ← p p ← 0 P P ← P P \ {(P A , P B )} 30: else 31: p ← p + 1 32: end if 33: end for 34: end if 35: end while 36:

Algorithm 3 Refinement

Input: A directed graph G 0 = (V, E) weighted by C 0 an D respectively cost and delay, a source s, a set of destinations T and a delay constraint ∆.

A pseudo-tree A 0 ⊂ E from s to T . Output: A valid tree A N from s to T .

1: Θ ← Cycles identified by a DF S over A 0 from s 2:

end if 23:

end if 24: end for 25:

A 3 ← Multiple path elimination(A 3 , v) (Alg. 4) 29: end for 30:

N ← L A 4 \ T 38: end while 39: return A 4

Algorithm 4 Multiple path elimination procedure

Input: A directed graph G 0 = (V, E) weighted by C 0 an D respectively cost and delay, a source s, a set of destinations T and a delay constraint ∆.

An acyclic directed sub-graph

, and a node m ∈ V A 1 with multiple paths from s to m in A 1 . Output: A set A 2 ⊂ A 1 in which there is one and only one path from s to m, with the shortest possible delay. 1: