Francesca Fossati

Stéphane Rovedakis

Senior, IEEE Stefano Secci

Distributed algorithms for multi-resource allocation

Novel network infrastructures require the distribution of computing and network resource control to meet stringent requirements in terms of latency, reliability and bitrate. 5G systems bring a key novelty in systems design that it the 'network slice'as a new resource provisioning entity. A network slice is meant to serve end-to-end services as a composition of different network and system resources as radio, link, storage and computing resources. Conventionally, each resource is managed by a distinct decision-maker, platform, provider, orchestrator or controller. Naturally, centralized slice orchestration approaches are proposed in the literature, where a multi-domain orchestrator allocates the resources, for instance using a multi-resource allocation rule. Nonetheless, while simplifying the algorithmic approach, centralization can come at the expense of scalability and performance. In this paper, we propose new ways to distribute the slice multi-resource resource allocation problem, using cascade and parallel resource allocations that are functionally compatible with novel software platforms. We also show how to adapt the proposed algorithms to make them able to guarantee service level agreements on the minimum resource needed, and to take into account deadline priority policy scheduling. We provide an exhaustive analysis of the advantages and disadvantages of the different approaches, including a numerical analysis for a realistic setting.

I. INTRODUCTION

Starting with the fifth-generation (5G) systems, communication networks need to meet novel diverse requirements. In 5G, mobile services are categorized in three main classes: enhanced mobile broadband (eMBB), Ultra Reliable Low Latency Communications (URLLC) and massive machine type communications (mMTC) -characterized by bandwidth, latency, frequency and reliability requirements. To guarantee these services are adequately provisioned over an end-toend infrastructure covering multiple resource domaines, the concept of network slice was formalized by 5G standardization bodies [START_REF] Americas | Network Slicing for 5G and Beyond[END_REF] -going beyond former application-level notions of network slices not encompassing multiple resource allocation.

The network slice, as meant starting with 5G systems, is an independent and logically-isolated end-to-end virtual network running on a shared physical infrastructure, aiming to provide the customers required service or vertical corresponding to different business domains such as health care, transport, smart office, agriculture, industry, automotive etc [START_REF] Ngmn | 5G white paper[END_REF]. Hence a network slice spans different parts of the network as the access, transport, core and data-center segments, combining networking, computing and storage programmable resources [3]. The interest towards network slicing is motivated by the increasing Francesca Fossati is with CentraleSuplec, Gif-sur-Yvette, France. francesca.fossati@l2s.centralesupelec.fr Stéphane Rovedakis and Stefano Secci are with Cnam, Cedric, 75003 Paris, France. Email: {firstname.lastname}@cnam.fr A preliminary version of the content of this article appears in [START_REF] Fossati | Decentralization of 5G slice resource allocation[END_REF]. This work was funded by the Agence Nationale de la Recherche (ANR) MAESTRO-5G (ANR-18-CE25-0012) project. programmability of the Radio Access Networks (RANs) as well as of the core elements, also thanks to the novel technologies such as Software-Defined Networking/RAN (SDN/SD-RAN) and Network Function Virtualization (NFV) [START_REF] Americas | Network Slicing for 5G and Beyond[END_REF].

Provisioning resources along an end-to-end path is therefore a multi-resource allocation problem. In the literature, different multi-resource allocation techniques exist, such as the Dominant Resource Fairness (DRF) [5] and the generalization of single-resource allocation rules ones [START_REF] Fossati | Multi-Resource Allocation for Network Slicing[END_REF]; such allocation rules are based on a centralized approach. In network slicing, a centralized approach implies the presence of a multi-domain orchestrator able to manage heterogeneous resources. Nowadays each part of the network is managed separately, as depicted in Fig. 1, and the presence of this kind of orchestrator may not be viable in practice for large-scale multi-domain deployments because resources can belong to different resource providers; e.g., the radio resource can be managed by radio operator, the cloud resource by a cloud service provider, the network link resource by an Internet service access provider.

In this paper we provide an extension of the preliminary work [START_REF] Fossati | Decentralization of 5G slice resource allocation[END_REF] toward the distribution of network slice resource allocation. We are interested in investigating distributed algorithms able to allocate slices. In particular, we propose three algorithms: two following a cascading approach and one a parallel approach.

Our reference technical framework is the one of novel virtualized access networks, depicted in Fig. 1. Large efforts are currently devoted to the design of virtualized/Software-Defined Radio Access Network (vRAN/SD-RAN) systems, such as Open RAN [START_REF]O-RAN Use Cases and Deployment Scenarios[END_REF]. In these systems, a radio intelligent controller (RIC) can coordinate with other resource controllers (SDN link controllers, NFV/MEC orchestrators and resource managers) in the resource allocation and scheduling decisions. Such an interaction is envisioned as being done via an orchestration layer, using standard interfaces already identified in corresponding sub-systems open-source projects. In particular, three level of scheduling are functionally identified: real-time (running at traffic processing device), near-real-time (running at resource controllers) and non-real-time (running at the multi-resource orchestration level). The algorithms we propose in this paper have the potential to be integrated to these systems, running at the near-real-time controller level.

We compare the approaches quantitatively (time complexity, message overhead, latency budget) and qualitatively (advantages, disadvantages). We then propose and test scheduling algorithms dealing with run-time constraints. The novel contributions of this work compared to [START_REF] Fossati | Decentralization of 5G slice resource allocation[END_REF] are:

• the generalization of the distributed algorithms in case of an arbitrary number of providers; • the design of a priority-and-deadline-based scheduling algorithm to consider Service Level Agreement (SLA) targets; • a complete analysis and demonstration of the delay budget and message complexity figures. The paper is organized as follows. Section II provides a background on well-known single-and multi-resource allocation rules, along with a background on recent network slice allocation works. In section III we describe the three proposed algorithms, called Cascading Resource Allocation (CRA), Ordered Cascading Resource Allocation (OCRA) and Parallel Resource Allocation (PRA). Section IV provides the evaluation of the algorithms. Section V proposes a scheduling approach to meet SLA constraints. Finally section VI concludes the paper.

II. BACKGROUND

We give an overview of common single and multi-resource allocation rules and related state of the art in network slicing.

A. Single and multi-resource allocation

Resource allocation problems can be divided into two types: single-resource ones, when only one resource has to be shared among the users, and multi-resource ones, when there are at least two resources to share.

Being N = {1, • • • , n} the set of users, a single resource allocation problem can be modeled by a pair (d, r) where d is a vector containing the demands of the n users (or tenants) and r is the amount of available resource that has to be shared among the users. An allocation a is a n-dimensional vector where a i is the amount of resource given to user i ∈ N . The allocation has to satisfy: (i) non-negativity (a i ≥ 0), (ii) demand boundedness (a i ≤ d i ) and (iii) efficiency ( n i=1 a i =r) [START_REF] Thomson | Axiomatic and game-theoretic analysis of bankruptcy and taxation problems: an update[END_REF]. Let now N = {1, ..., n} be the set of users and let M = {1, ..., m} be the set of m available resources, then a multi-resource allocation problem can be modeled as a pair (D, R). R represents the vector of the available resource amounts and D is the matrix of demands (d ij ∈ D is the quantity of resource j ∈ M demanded by user i ∈ N ). The allocation matrix A is given by assigning to user i for resource j the amount a ij =d ij • x i , where x = (x 1 , ..., x n ) -with 0 ≤ x i ≤ 1 ∀i ∈ N -is the vector of the ratios of resource allocated to each tenant. In the following, we assume that a feasible vector of ratios x must belong to the admissible region F s.t. i∈N x i ≤ 1 (so, a feasible allocation is s.t.

i∈N a ij ≤ r j , ∀j ∈ M ). We now summarize the most common allocation rules, which do solve an actual problem when the resource is scarce, i.e., when i∈N d i > r in case of single resource, or when it exists at least one resource j for which i∈N d ij > R j in the case of multiple resources. Existing rules are as follows:

Weighted proportional rule [START_REF] Fp | Rate control for communication networks: shadow prices, proportional fairness and stability[END_REF]: computes the allocation that maximizes the n i=1 p i log a i . When the weight p i is equal to 1 for each user, the solution is such that increasing the allocation of a user, at least another user gets a loss in proportion larger than the gain of the previous user. When the weights are chosen equal to the demand d i for each user i, the allocation assigns the same proportion of demand to each user, maximizing the fairness Jain's index [START_REF] Jain | A quantitative measure of fairness and discrimination for resource allocation in shared computer system[END_REF].

Max-Min Fair (MMF) rule [START_REF] Dp | Data networks[END_REF]: is an egalitarian solution, privileging the weak users (with small demands). It is calculated in a recursive way maximizing the minimum allocation, then the second lowest allocation, and so on. Ordering the users according to their increasing demand, i.e.,

d 1 ≤ d 2 ≤ • • • ≤ d n , then MMF allocation for user i is given by M M F i (d, r) = min d i , r-i-1 j=1 M M Fj (d,r) n-i+1
.

α-fair rule [START_REF] Mo | Fair end-to-end window-based congestion control[END_REF]: is a family of allocation rules that generalizes the MMF and proportional rules. It is obtained by maximizing

n i=1 a (1-α) i 1-α , where α ≥ 0 1 .
Mood value rule [START_REF] Fossati | A Mood Value for Fair Resource Allocations[END_REF], [START_REF] Fossati | Fair Resource Allocation in Systems with Complete Information Sharing[END_REF]: is a solution conceived for complete awareness situation when users have full knowledge of the other users demand and of the available resource. Each user i can compute its minimal right min i (what remains if all the other users are fully satisfied) and maximal right max i (its own demand or the available resource, if the demand overcomes it), and the allocation is computed as min i + m(max i -min i ) where m in [0,1] is the ratio between what remains when users get the minimum and n i=1 (max i -min i ). Dominant Resource Fairness (DRF) [5] rule: generalizes the MMF rule for a multi-resource context. The allocation is the solution of the following problem: maximize x subject to

ds i x i = ds j x j , ∀i, j ∈ N (1)
where x ∈ F, and

ds i = max k∈M { d ik r k } is called dominant share of user i.
The above described allocation rules (single and multiresource) are Pareto efficient. Definition 1. An allocation a is Pareto efficient if for any other allocation a we have a kj > a kj for some k ∈ N and j ∈ M =⇒ a k j < a k j for some k ∈ N .

Other multi-resource rules: A detailed description of multiresource allocations can be found in [START_REF] Poullie | A survey of the state-of-the-art in fair multi-resource allocations for data centers[END_REF], [START_REF] Fossati | Multi-Resource Allocation for Network Slicing[END_REF]. 1 If α = 1 the solution coincides with the proportional one, if α = 2 with the minimum delay potential allocation, that is the allocation obtained minimizing the total potential delay n i=1

(

1 x i
) and if α → ∞ with the MMF rule [START_REF] Mo | Fair end-to-end window-based congestion control[END_REF]. Fig. 2: Diagrams of multi-resource allocation approaches for an example with three providers p i providing one resource r i , with i = 1, 2, 3. D is a n × 3 demand matrix, where n is the tenant number and d i , with i = 1, 2, 3 is a demand vector for the resource i, a is the n × 3 allocation matrix and a i , with i = 1, 2, 3 is an allocation vector for the resource i.

A family of allocation rules, generalizing well-known single and multi-resource problems is the MURANES [START_REF] Fossati | Multi-Resource Allocation for Network Slicing[END_REF]. They are obtained solving the following problem:

maximize OW A(v) subject to x ∈ F, 0 ≤ x i ≤ 1, ∀i ∈ N where OW A(v) = n j=1 v (j) , v (j)
is the j-th smallest element of (v 1 , ..., v n ), the input vector v is the (weighted) satisfaction vector 2 and F provides the region of acceptable solutions. See [START_REF] Fossati | Multi-Resource Allocation for Network Slicing[END_REF] for details. In addition to those already presented, let us mention: (i) the asset fairness [5], aiming at equalizing the resource allocated to each users, (ii) the Nash product that maximizes the product of the percentage of resource to allocate [5] and (iii) the Bottleneck-Based Fairness (BBF) equalizing the share received on the bottleneck resource [START_REF] Etsion | A global scheduling framework for virtualization environments[END_REF].

B. Centralized vs distributed multi-resource allocation

All the described multi-resource allocation rules are centralized, i.e. they are meant to be run by a multi-domain orchestrator (e.g., at the non-real time orchestration layer in Fig. 1) that has a view on all the resources and receives the demands of the users, as represented in Fig. 2a. Centralized approaches imply that there is a relation between the resource; in particular, for all the proposed allocation in previous paragraph, a linear dependency between resources is considered.

Alternatively to centralized approaches, distributed approaches can be considered (e.g., running at the near-real time scheduling layer at resource controllers as in Fig. 1). With these approaches it is possible to let providers calculating their own allocation without sharing confidential information as the quantity of available resource. Naturally, the presence of other providers with their own allocation, can provide not efficient or unfeasible solutions, so a degree of collaboration between providers is necessary to obtain the final allocation, acceptable for all them (Fig. 2b).

A third approach that is possible to follow is to let allocate resources of each provider separately, without any information exchange among resource controllers (Fig. 2c). In this case, that we call de-centralized approach, we can have a resourcewaste problem as described in [START_REF] Fossati | Multi-Resource Allocation for Network Slicing[END_REF]. For this reason, this type of approach is not considered in the following.

In this paper, we compare centralized and distributed algorithms, following the first two approaches. It is worth noting that combinations of the three described approaches can be conceived as well, in particular to deal with situations in which the hypothesis of linear dependency between groups of resources does not hold.

C. Resource allocation in network slicing

Recent works address resource allocation problems in network slicing from many points of view. Categorizing them by the type of resource, some such as [START_REF] Leconte | A resource allocation framework for network slicing[END_REF] deal with the allocation of network link and computing resources, and others that address the radio allocation [START_REF] Caballero | Multi-tenant radio access network slicing: Statistical multiplexing of spatial loads[END_REF], [START_REF] Xiao | Distributed Resource Allocation for Network Slicing Over Licensed and Unlicensed Bands[END_REF].

Many objectives are adopted for the computation of a slice allocation. Some examples are (i) the maximization of the slice customers profit [START_REF] Wang | Resource Allocation for Network Slices in 5G with Network Resource Pricing[END_REF], (ii) the maximization of network revenue [START_REF] Jiang | Network slicing in 5G: An auction-based model[END_REF] or (iii) the achievement of a desirable fairness across the network slices of different tenants and their associated users [START_REF] Caballero | Multi-tenant radio access network slicing: Statistical multiplexing of spatial loads[END_REF].

Different mathematical methods are used. A game theoretic approach is often adopted; in [START_REF] Caballero | Network slicing games: Enabling customization in multi-tenant networks[END_REF], where the authors propose a network slice game as a non-cooperative game, with existence of a Nash equilibrium under appropriate hypothesis; in [START_REF] Xiao | Distributed Resource Allocation for Network Slicing Over Licensed and Unlicensed Bands[END_REF] the network slicing game is a cooperative game, but solved with a distributed algorithm not to force the mobile network operator to reveal private information; in [START_REF] Jiang | Network slicing in 5G: An auction-based model[END_REF] and [START_REF] Halabian | Distributed Resource Allocation Optimization in 5G Virtualized Networks[END_REF], where the resource allocation is the outcome of an auction. Instead, a utility optimization approach, with different objectives, is used in [START_REF] Leconte | A resource allocation framework for network slicing[END_REF], [START_REF] Caballero | Multi-tenant radio access network slicing: Statistical multiplexing of spatial loads[END_REF] and [START_REF] Wang | Resource Allocation for Network Slices in 5G with Network Resource Pricing[END_REF].

Let us position our work with respect to these works.

• Each network slice has a resource demand vector for each resource that has to be allocated, similarly to [START_REF] Halabian | Distributed Resource Allocation Optimization in 5G Virtualized Networks[END_REF].

III. DISTRIBUTED MULTI-RESOURCE ALLOCATION

We propose three algorithmic approaches to address the multi-resource allocation problem in a distributed way. The first two follow a cascading behavior while the third one exploits parallelism. In this section we analyze the slice resource allocation process under the three approaches, describing advantages and disadvantages of each one. Note that while in this section and the following one we focus on static distributed resource allocation approaches, in Section V we develop and evaluate dynamic scheduling variants.

A. Problem modelling

Let N = {1, ..., n} be the set of tenants, M = {1, ..., m} be the set of available resources and P = {1, ..., p} be the set of resource providers. We realistically consider |P | ≤ |M |, that is, an ex-ante per-resource provider competition may have taken place beforehand to select the set of providers involved in the slice resource allocation and provisioning. It follows that in our problem we have only one provider for each resource, and each of them can provide more than one resource. The allocation problem is represented as a triplet (D, R, γ), where D is a n × m matrix with d ij equal to the quantity of resource j ∈ M demanded by tenant i ∈ N , R = (r 1 , ..., r m ) is a vector of positive numbers r j equal to the amount of each available resource j ∈ M , and γ is a n-dimensional vector containing the priority index of the service required by tenants.

In this work, the priority index γ is linked to the latency of the service. Services requiring low latency have high priority and a low value of γ, those tolerant to higher latency have lower priority and the correspondent value of γ is high. E.g., considering the three classes of service formalized for the 5G, following what is recommended in [START_REF] Series | IMT VisionFramework and overall objectives of the future development of IMT for 2020 and beyond[END_REF], the importance of latency requirement is high for URLLC services, which refers to wireless connection with low latency, medium for eMBB services, which needs high data bandwidth and moderate latency, and low for mMTC services because they focus on massive objects connectivity, with no strict latency requirements [START_REF] Popovski | 5G wireless network slicing for eMBB, URLLC, and mMTC: A communication-theoretic view[END_REF]. For this reason, at first instance, we consider 3 priority levels characterizing the three reference 5G classes of services.

Another important aspect to model in network slice resource allocation is the relation between allocated resources. As already assumed in previous works [START_REF] Fossati | Multi-Resource Allocation for Network Slicing[END_REF], [START_REF] Leconte | A resource allocation framework for network slicing[END_REF], [START_REF] Lee | Resource Management in Service Chaining[END_REF], the relationship between resources can be safely approximated with a linear one; this means that if a user asks for 10 Gbps, 40 CPU and 160 GB and it receives only 5 Gbps then the cloud resource provider has to allocate 20 CPU and 80 GB because if the allocation is superior, the cloud resource is wasted, while if inferior, the link resource is wasted.

Let the allocation outcome be represented by a matrix A with components because the resource is not sufficient to fully allocate the demands of the users (i.e. the resource is congested -in the trivial case the resource provider can allocate the demand and x = (1, • • • , 1)). The three algorithms proposed in next subsections take into account that resources can be congested.

a ij = d ij • x i where x = (x 1 , ..., x n ), 0 ≤ x i ≤ 1 ∀i ∈ N ,
The congestion level (µ) of a resource provider p is defined as the ratio between the sum of the demands for its resource(s) and the available quantity of resource(s), i.e.

µ j = n i=1 dij rj
, if it provides only one resource j ∈ M . Contrarily, if it provides more than one resource, the congestion level is the maximum between the level of each resource it provides. If µ p > 1 the resources provided by the provider p are congested. We can notice that the congestion level of a resource provider is used in the proposed algorithms to avoid or reduce the sharing of sensible information by resource providers, e.g., quantity of available resources. The congestion level is:

µ 1 = 20+20+30 100 = 0.7, µ 2 = 10+25+10 30 = 1.5, µ 3 = max{ 160+488+160 600 , 40+64+40 80 } = 1.8.
Each resource provider has to take into account the priority index so that the allocation rule described in Section II has to be adapted to the context. In this work we consider a simple algorithm (Algorithm 1) to adapt the allocation rules. We suppose that the priority index takes integer value from 1 to s, where s is the priority index of the lower priority required service, and lower value of γ corresponds to higher service priority. Algorithm 1 firstly attempts to fully satisfy users with the highest priority, and then the ones with lower priorities. Note that, alternatively, any other algorithm providing Pareto efficient solution could be used as well.

B. Cascading Resource Allocation (CRA)

The first algorithm we propose follows a cascading approach, i.e., each resource provider sends to the following one the information about its allocation, and passing through all the providers the allocation is adjusted taking into account the congestion level of each resource and the allocation proposed by the previous provider. Algorithm 2 describes the CRA approach for the general case with p providers; the steps of the algorithm are labeled within parenthesis. The order follows the natural end-to-end order of the resources, as for the radiolink-cloud three resources scenario presented in Figure 3.

We consider now and later as reference scenario for the examples the one with 3 resources providers (P = {1, 2, 3}) providing radio, link and cloud resources. To make the notation clearer, in this case we use the subscript r for radio (p = 1), l for link (p = 2) and c for cloud (p = 3). .

(2) The radio resource provider calculates the allocation. In this case there is no congestion so a r = (20, 20, 30) and x r = (1, 1, 1).

(3) The link resource provider receives the vector x r . (4) The link resource provider calculates the allocation. In this case there is congestion so x r is not an admissible solution. The provider uses an allocation rule; if it is for example the MMF one, the allocation is a l = (10, 10, 10) and x l = (1, 0.4, 1).

(5) The cloud resource provider receives the vector x l . (6) The cloud resource provider checks if x l is admissible:

• 160 • 1 + 488 • 0.4 + 160 • 1 ? < 600 → yes • 40 • 1 + 64 • 0.4 + 40 • 1 ?
< 80 → no Due to the fact that the proposed x l is not admissible; the cloud provider calculates a new allocation, taking into account that for each user i the upper bound for x ci is x li . For example using the DRF rule we get In the presence of a multi-domain orchestrator that is able to schedule how resource allocation takes one can partially avoid resource re-allocation. Before each decision is taken, the orchestrator asks or receives the congestion level of the resources provided by the p providers and re-order the providers. This cannot guarantee to bypass the re-allocation for all resources, but it can strongly reduce its impact on the solution (see Example 3). The algorithm is described by Algorithm 3, and is depicted in Figure 4 for the radio-linkcloud scenario. (5) The link resource provider receives the vector x A . [START_REF] Fossati | Multi-Resource Allocation for Network Slicing[END_REF] The link resource provider checks if x B is admissible:

10 • 0.67 + 25 • 0.412 + 10 • 0.67 ? < 30
→ yes. The allocation is: x B = x A , a l = (6.7, 10.3, 6.7). [START_REF] Fossati | Decentralization of 5G slice resource allocation[END_REF] The radio resource provider receives the vector x B . [START_REF] Thomson | Axiomatic and game-theoretic analysis of bankruptcy and taxation problems: an update[END_REF] The radio resource provider accepts the proposed x B because the resource is not congested. The allocation is: a r = (13.4, 8.24, 20.1). [START_REF] Fp | Rate control for communication networks: shadow prices, proportional fairness and stability[END_REF] Step not necessary because no resource re-allocation.

It is worth noting that with this algorithm one cannot always avoid re-allocation. In fact if, in Example 3 we increase the value of d 22 from 25 to 30, the order of the resource, based on the congestion level, remains the same (µ l = 1.67), but if the cloud provider proposes the allocation x A = (0.2, 1, 0.2), the link provider cannot accept it because 10•0.2+30•1+10•0.2 > 30. This shows that the re-allocation is not always avoided with this algorithm, but at least its negative impact is decreased.

D. Parallel Resource Allocation (PRA)

In the previous proposed algorithms the computation of the resource allocation is done following a weakly distributed manner. Indeed, the resource allocation is computed according Fig. 5: PRA algorithms; PRA-1 using the 1-phase consensus algorithm, PRA-2 using the 2-phase consensus algorithm.

to a defined sequence among the resource providers, which implies a high dependency and a low collaboration degree between providers. Thus, the computation time required by these algorithms is dominated by the resource provider with the highest response time. To limit the impact of such a situation, we design a fully-distributed algorithm, named Parallel Resource Allocation (PRA), which allows to increase the level of parallelism to compute the allocation and to reduce the computation time. Contrary to the two preceding algorithms, the idea of the PRA approach is to allow each provider to compute its own allocation, then all the resource providers exchange their allocation and use a distributed consensus approach [START_REF] Coulouris | Distributed systems -concepts and designs[END_REF] to obtain the final allocation.

PRA is described in Algorithm 4, and is depicted in Figure 5 for the radio-link-cloud scenario.

We develop the PRA idea with two different consensus algorithm variants. The first one has the property of being fast, but it does not guarantee to saturate at least one of the congested resources, so it is not Pareto efficient as we prove later (Section IV-B). The second one introduces an additional information exchange to the process, but it guarantees to saturate at least one of the congested resources.

The first consensus algorithm, called PRA-1, is a 1-phase algorithm; each resource provider diffuses to all the other ones the value of x, and the allocations are obtained in the following way: (min k∈P x k1 , • • • , min k∈P x kn ). The non-saturation of the resources can happen when there exists at least one user for which the dominant resource, i.e., the resource in percentage most requested by the user, is not the one with higher congestion level (see Example 4).

The second algorithm, called PRA-2, is a 2-phase algorithm; each resource provider diffuses (i) the value of the allocation, (ii) the congestion level and (iii) the resource share of each resource it provides for each user, i.e., rs i = { dij rj } ∀i ∈ N and for each resource j it provides. These information are used in order to limit the exchange of sensible information for resource providers (e.g., quantity of available resource). The provider with the most congested resource can identify itself and calculate the value of x using a multi-resource approach. In fact, the information about the resource share allows the provider to take into account the capacity constraints; moreover the optimization objective is decided by the provider following its fairness goal. We can notice that the calculus of the allocation by each provider is thus not necessary and can be avoided to decrease the delay budget. PRA-2 guarantees a Pareto efficient allocation as proven later. and the resource used is (41.5, 23.4, 409.6, 79.2). This shows that the saturation of the resources is not guaranteed when we use the 1-phase algorithm. In fact, for user 2 the dominant resource is the link resource but the resource with higher congestion level is the cloud one.

With PRA-2, the three resource providers diffuse the following information:

• x r = (1, 1, 1), rs r = (0.2, 0.2, 0.3), µ r =0.7.

• x l = (1, 0.4, 1), rs l = (0.33, 0.83, 0.33), µ l =1.5.

• x c = (0.67, 0.412, 0.67), rs c = (0.5, 0.81, 0.5), µ c =1.8.

The cloud resource is the most congested one and the cloud provider calculates the value of x. For example, if it chooses to use a proportional approach (equalizing the x of each tenant), the solution is x = (0.556, 0.556, 0.556), a r = (11.12, 11.12, 16.68), a l = (5.56, 13.9, 5.56), a c = .

IV. PERFORMANCE EVALUATION

In this section we provide a qualitative and quantitative analysis of the proposed algorithms. Section IV-A provides an analysis in terms of delay budget, Section IV-B highlights advantages and disadvantages of each algorithm, and in Section IV-C we numerically compare the algorithms.

A. Delay budget

We are here interested in estimating the delay budget of each algorithm, i.e., the global time between the submission of a slice demand and the moment in which the computation of the resource allocation is done. Delay contributions in the process are the transfer time covering the transmission delay and the propagation delay for each message and the allocation computation time. Time for checking if an allocation x is admissible can be considered negligible. We also assume in the following the transmission delay to be negligible, given the likely short message size in stake, so the transfer delay corresponds to the propagation delay.

Figure 6 shows delay budget diagrams for the three proposed algorithms, and an arbitrary centralized approach where a multi-domain orchestrator receives the tenants demand and computes the allocation as a one-shot operation. Under the simplification that propagation delays are all roughly equal to a value τ and all allocation computing times are equal to δ, we obtain the estimation of the delay budget in Table I for the general case with p resource providers. We report the value of the delay budget in the best and worst case; these two values do not coincide in case of cascading approaches: the best case is the one in which only one allocation is calculated and is admissible for all the other resource providers, while the worst one is in case an allocation has to be calculated by each resource provider.

Clearly the centralized approach is the one with lower delay budget together with the first distributed approach. The algorithm closer to the centralized approach is PRA-1. Cascading approaches have a higher figure; note that while for the centralized and PRA approaches the value of delay budget does not depend on the number of resource providers p, for cascading approaches it does. Figure 7 compares the delay budget of all the approaches with 3 resource providers, in three different cases: (case 1) the propagation delay is negligible with respect to the computing time, i.e., τ δ, (case 2) the reverse case, i.e., δ τ and (case 3) the two times are comparable -we plot the case τ = δ.

B. Pros and cons

Let us draw advantages and disadvantages of the different algorithms. Table II summarizes the following observations. Choosing a centralized approach we have the advantages of a low delay budget in the creation of the slice, due to the fact that the decision is taken atomically, by a single entity. Meanwhile the fact of having centralization at a multidomain orchestrator can be seen as an obvious drawback in terms of reliability and scalability from the one hand, and confidentiality from the other hand as each provider has to share possibly sensible information, as for example the quantity of resource available in its domain. The presence of a multi-domain orchestrator is also necessary for the OCRA approach, to order the resource providers. In this case it has only a function of dispatcher (note that for OCRA it is however possible to avoid the presence of the multi-domain orchestrator using a distributed approach to exchange the information about the resources congestion level, however impacting performance). All the other approaches have the advantage of not needing such a centralized orchestrator.

Concerning cascading approaches (CRA, OCRA) they have the disadvantage of re-allocating resources during the slice provisioning; this is expected to be highly reduced with the OCRA approach. Advantages of parallel approaches are (i) the low delay budget, due to the simultaneously computation of the allocation and diffusion of the information, and (ii) the possibility to independently allocate some resources. For example, this can be useful for the radio resource for which the hypotheses of linear dependency with the other resources may appear less acceptable with some radio scheduling protocols.

If distributed approaches have good behavior in terms of delay budget compared to the cascading ones, considering the number of messages that have to be exchanged, the judgment is reversed. From Table I, we can see that the number of exchanged messages grows quadratically with the number of providers p. In case in which p = 10 the number of the exchanged messages is between 21 and 30 for the centralized and cascading approaches, while it is 100 and 109 for the two distributed ones. This is the price to pay when we distribute the calculus of the allocation to avoid a single point of failure.

Among the disadvantages, for the PRA-2 we find the low confidentiality disclosure; in fact, providers are forced to exchange much more information compared to the PRA-1 and the centralized approaches. A drawback for the PRA-1 approach is the possibility to get a solution that is not Pareto efficient. In this respect, we can state the following Theorem.

Theorem 1. CRA, OCRA and PRA-2 algorithms provide Pareto-efficient solutions.

Proof. CRA and OCRA algorithms provide Pareto-efficient solutions because the allocation coincides with the one proposed by one provider that selects a Pareto efficient allocation rule. The PRA-2 algorithm provides an allocation that saturates one resource because it is calculated using a multi-resource allocation rule, so it provides a Pareto efficient solution. The algorithm PRA-1, using the minimum value for each component allows the increasing of the allocation of one tenant without decreasing the one of the other. Let us consider the example 4. If we increase the allocation of tenant 2 from 0.4 to 0.412 we obtain the allocation proposed with the OCRA in Example 3. Thus, it is possible to increase the allocation of tenant 2 without modifying the one of the others (allocation not Pareto efficient). Figure 8 shows an example with two tenants and two resources provided by two different providers. We can see how algorithms works and that the Pareto efficiency is guaranteed for the cascade approaches and for the PRA-2 algorithm, while it is not for the PRA-1 algorithm because the solution is inside

C. Numerical analysis

We present a numerical analysis to measure (i) the occurrence of reallocation using the OCRA algorithm, (ii) the occurrence of inefficient solutions for the PRA-1 algorithm, and (iii) the distance of the proposed distributed approaches from the centralized one. The analysis for (i) and (ii) is done considering services with the same priority. In our knowledge there are no previous works considering a congestion scenario so the results show the difference between the 4 distributed approaches and they are compared to centralized ones.

1) Occurrence of re-allocation: The aim here is to understand if there is a real gain using an ordered approach, i.e., if the re-allocation of the resources is reduced and consequently the delay budget induced by allocation computation. We generate 300 problems with three tenants, three resources belonging to three providers, randomly associating a level of congestion between 0.1 and 2 for each provider. Table III shows the results of the simulations when all providers use the same allocation rule (Proportional, Mood value, MMF). We can see that there is a real gain in using an OCRA approach because with the proportional allocation and the mood value we have no reallocations, while with the MMF there are situations in which one re-allocation is needed, but two are needed only for a negligible number of cases. 2) Percentage of inefficient solutions in PRA-1: We test here the efficiency of the solutions when we use the PRA-1 algorithm. Using the same data generated for the previous simulations, we calculate the percentage of time in which the PRA-1 algorithm does not provide a Pareto-efficient solution (Table IV) and we estimate how much is the loss for the tenants in term of resources (Fig. 9). Clearly, PRA-1 has high probability to provide allocations that are not Pareto-efficient. When providers use the same allocation rule, more than half of the time the produced allocation is not Pareto efficient. Furthermore the resource loss is high. The median value in percentage, obtained in the boxplot (Fig. 9) belongs to the interval of [0.8, 0.9]. We can also observe that the higher resource loss is experienced with the Mood value allocation.

3) Distance from a centralized approach: We firstly introduce a measure of the distance between a centralized approach and a distributed one. A simple measure we can consider is the Chebyshev distance (or L ∞ metric) defined as follows.

Definition 2. The Chebyshev distance between two vectors y 1 and y 2 is d che = max i |y 1i -y 2i |.

In our case, considering a solution vector obtained with a centralized approach and one with a distributed one, the measure indicates the gain (or loss) of the user that obtains the maximum gain (or loss) when a distributed approach is used. This measure provides an estimation of the satisfaction (unsatisfaction) of the users in adopting a distributed approach.

We developed an ad-hoc simulator in Python that we make available in [START_REF]Simulation code[END_REF] for verification and reproducibility. We sim- ulate 200 problems with five tenants, taking inspiration from Amazon EC2 instances [START_REF]Amazon EC2 instances comparison[END_REF] (the same considered instances as in [START_REF] Fossati | Multi-Resource Allocation for Network Slicing[END_REF]); we report in the supplementary materials the detailed instance table: we select those templates with different 'instance type' ('General Purpose', 'Computer Optimized', 'Memory Optimized', 'Accelerated Computing'and 'Storage Optimized') and we consider three resources belonging to two providers (CPU and memory for the cloud provider, link capacity in Gbps for the network link provider), a level of congestion between 0.1 and 1.5 for each provider, and both the case in which the tenants have the same priority and belong to the same class (single-class) and the case in which the tenants have different priorities and belong to different classes (multi-class). In the second case we arbitrarily associate to the different Amazon templates a type of service as follows: URLLC to Accelerated Computing instance, eMBB to Computer and Memory Optimized instance, mMTC to Storage Optimized instance, and best effort to General Purpose instance. The considered services, defined accordingly to 5G standards, are differentiated accordingly to the demand and the priority index.

Figure 10 shows the boxplot of the distance for each algorithm, using different combinations of allocation rules, when the centralized approach uses the DRF rule. When the priority is the same for each tenant there are users that can gain or loose a lot when the providers adopt as distributed approach the CRA, OCRA and PRA-1. In the single-class case, the distance is reduced using the PRA-2 approach because the proposed allocation is calculated as a multi-resource allocation taking into account the information provided by each provider. In the multi-class case we notice a performance improvement of the distributed algorithms. In fact, in this case, the differences emerge only for the group of tenants belonging to the same priority class for which the remaining resource, after that tenants with higher priority are fully served, is not enough. In this case due to the small cardinality of the subset of users belonging to the same class, there is a high probability that the distributed solution is close to the centralized one.

We then consider the distance measure inside each group of services and the service rate, i.e., the percentage of requests processed (Figure 11). The distributed algorithm always serves the users with higher priority and the service rate decreases with the service priority. On average, the distance increases decreasing the service priority, but a decrease of the distance is possible because (i) services with low priority have high probability not to be served both with the centralized and distributed approaches (Figure 11) and (ii) as already said, if the cardinality of the last served group is small the distributed and centralized solutions can be close. We can also observe that: (i) CRA has better behavior in terms of distance than OCRA algorithm for best-effort services, vice-versa for the URLLC and eMBB services, (ii) although PRA-1 is not Pareto efficient, it achieves Chebyshev distances close to the cascade approaches and (iii) PRA-2 algorithm returns allocations which are the closest to the centralized algorithm in terms of distance for the MMF and DRF allocations and it has the worst results when using the mood-DRF allocation.

V. INTEGRATION OF SLA AND PRIORITY-BASED

SCHEDULING

In section III we proposed different distributed algorithms to slice the network in a given time frame. We want now to enrich these algorithms with policies taking into account Service Level Agreement (SLA) constraints [START_REF] Americas | Network Slicing for 5G and Beyond[END_REF]. In the literature we can find cloud scheduling algorithms that meet tenants' Quality of Service (QoS) requirements. Examples are: (i) the work in [START_REF] Liu | Preemptive hadoop jobs scheduling under a deadline[END_REF] where a deadline job scheduling algorithm is proposed considering the current status of the system and the job execution cost model; (ii) the work in [START_REF] Abhaya | Performance analysis of edf scheduling in a multi-priority preemptive m/g/1 queue[END_REF] proposing the Earliest Deadline First (EDF) that is a dynamic priority real-time scheduling algorithm that considers time constraints of tasks in scheduling for execution and (iii) the work in [START_REF] Jia | A Deadline Constrained Preemptive Scheduler Using Queuing Systems for Multi-tenancy Clouds[END_REF] proposing an algorithm called Earliest Maximal Waiting Time First (EMWTF), that enhances the EDF algorithm. None of these works provide an algorithm able to provide a fair allocation over the time considering all our constraints (SLA constraints, priority, deadline and service time frame).

In this section we discuss (i) how to guarantee the continuity of the service, i.e., when a tenant is served, it has to be served for the required time and (ii) how to guarantee a minimum capacity, i.e., the minimum quantity of resource specified in the contract between the provider and the consumer. The main aim is to guarantee time-fair allocations, i.e., to serve with a similar service availability rate users asking for services of equal priority.

Under this setting, given a time frame t, the resource allocation problem is a tuple (D t , D m t , γ t , ν t , τ t , λ t , R t ) where: • D t is the demand matrix, • D m t is the matrix containing the minimum values of resource to allocate to each tenant defined in the SLA, • γ t is a vector containing the priority index of each tenant, • ν t is a vector containing the availability rate of each tenant, i.e. the percentage of time the tenant was served, with at least a minimum resource amount,

• τ t is the number of time frames the demand is for3 • λ t is the deadline, i.e. the number of time frames the tenant can wait before being served, • R t is the available resource 4 . We link the priority index to the latency of the service: if the service requires a low latency its priority is higher, otherwise it is lower. For instance URLLC services can be characterized by higher priority indexes compared to eMBB and mMTC services because they are low-latency services.

The structure of the algorithms remains similar but we have to define a users delay policy (V-A), how to allocate the resources, under the constraint of guaranteeing a minimum share of resource (V-B) and how the cascade (V-C1) and parallel algorithms work (V-C2). Finally we propose a SLA and deadline priority algorithm (V-D).

A. User delay policy

When a provider p is not able to satisfy the minimum allocation of each tenant ( n i=1 d m ij > R j , for at least one resource j provided by p), it has to remove one or more tenants, putting them in hold for possible servicing in the next time slot. Different user removal/delay policies can be proposed. Here we propose one that takes into account both the user priority index and the current availability rate of each tenant, already used in [START_REF] Fossati | Multi-Resource Allocation for Network Slicing under Service Level Agreements[END_REF], for its desirable property of guaranteeing fairness over the time.

The idea is that, to order users, we should firstly consider the priority index. Tenants with high priority have to be removed only if the tenants with lower priority do not exist or are already been removed. This can match operational constraints because high priority services are the ones asking for low latency, and tenants asking for this type of services have to be served as fast as possible.

One time users are ordered depending on the priority index, the removal/delay policy considers the value of ν. The highest is the value of ν, the highest is the percentage of time the tenants were served in past time slots. It follows that users with same priority have to be ordered by descending values of ν, in order to guarantee a sort of time-fairness. An example of users re-ordering, considering the described policy is given in Example 5.

Example 5. Let us consider five tenants with priority vector

γ = [1, 2, 1, 3, 1]
, where lower value of γ means higher priority, and availability vector ν = [0.1, 1, 0.5, 0.9, 0.3]. The ordered users vector, following the policy proposed is [START_REF]O-RAN Use Cases and Deployment Scenarios[END_REF][START_REF] Ngmn | 5G white paper[END_REF]3,5,[START_REF] Americas | Network Slicing for 5G and Beyond[END_REF].

The users re-ordering has to be done by each provider at the beginning of each time frame and in case the expiration time of a tenant falls in currently time slot, providers automatically set the priority of the user as the highest one, trying to avoid the delaying of the tenant (as further explained in Section V-D).

Once the order of the users to remove is established, each provider tests if the minimum of the resources it provides can be allocated, if not it excludes a user following the order described above and it checks if in the group of the excluded one there is one or more one that can be re-introduced. The users' re-introduction order is inverse with respect to the elimination one.

B. Resource allocation with minimum capacity constraints

We now discuss how resource allocation rules can be modified to take into account the user's minimum demand.

Concerning the rules obtained as solutions of optimization problem, it is sufficient to add a constraint regarding the value of the percentage of resource to allocate x, or alternatively on the value of the minimal allocation. For single-resource allocations (weighted proportional, α-fairness) we can modify the demand boundness constraints (a i ≤ d i ) adding a lower bound: d m i ≤ a i ≤ d i ; for multi-resource allocation the boundness constraints (x i ≤ 1) becomes x m i ≤ x i ≤ 1 with

x m i = max j d m ij dij
, when each provider considers the resources j it provides.

The re-definition of the mood value and the MMF allocation rules, in case of minimal demand to guarantee, is less intuitive. The MMF allocation is not solvable as an optimization problem and it is not clear how the problem with the minimal demand to satisfy can be solved. In particular Figure 12 shows how, using the hydraulic interpretation of the MMF allocation, the re-definition problem is challenging. This open problem represents an interesting possible future work.

The mood value instead can be interpreted as the results of an optimization problem [START_REF] Fossati | A Mood Value for Fair Resource Allocations[END_REF], [START_REF] Fossati | Fair Resource Allocation in Systems with Complete Information Sharing[END_REF], after that the minimal allocation, calculated considering the other users demands, is allocated to each user. Under the hypothesis that the sum of the minimal demands is inferior to the available resource (always respected otherwise we remove one or more users), the mood value allocation can be calculated as follows.

C. Cascade and parallel algorithms enhancements

Before adapting the two types of algorithms proposed in section III for long term allocations, let us further elaborate on a hypothesis of our problem. We assume that the minimal demand of each user maintains the same linear dependence between the resources expressed by the nominal demand. As we can see from Figure 13, this implies that for each tenant the portion of the nominal demand demanded as minimal demand is the same for each resource. Consequently, each user, instead of submitting the minimal demand for each resource, can simply submit the demand ratio vector needed to receive the minimal allocation for each resource. Thus, alternatively to the demand matrix D m , we can consider a vector d m , where each component gets value between 0 and 1 and that represents the percentage of demand each user requires as minimal one 5 .

We are now ready to describe how cascade and parallel algorithms work at each instant of time, taking in consideration the user delay policy and the guarantee on the minimal allocation. In fact, differently from the classical algorithms, now, when a provider proposes an allocation it takes into account the minimal allocation, hence it uses allocation rules described in V-B. We first present hereafter the enhanced algorithm, and then we explain the general algorithm over the time, considering the redefined cascade and parallel algorithms and the deadline priority policy.

1) Cascade algorithms (sCRA, sOCRA): The two enhanced cascade algorithms, we name sCRA and sOCRA, work similarly to the static case but, in order to provide feasible allocations, providers need to know which users can be served by every provider. This can be done by adding a pre-processing step at the beginning of the classical CRA algorithm, or while providers send their congestion for the OCRA algorithm.

If we do not add the pre-processing step in the sCRA algorithm the budget-delay can excessively increase because each time a provider k delays a user, served by the previous ones, this information has to be sent to the first provider that has to update the allocation and consequently each of the following provider had to re-calculate the allocation. Adding this preliminary step, the sCRA algorithm has the same delaybudget of the sOCRA and, as the sOCRA, it needs the presence of a multi-domain orchestrator. Consequently the sCRA loses all the advantages over the sOCRA and therefore we consider only the sOCRA algorithm next.

2) Parallel algorithms (sPRA-1, sPRA-2): In parallel algorithms the notion about which user is served and which is delayed is learned after that each provider diffuses the allocation. In fact if a user cannot be served, the allocation is zero. It follows that sPRA1 and sPRA2 work as the classical parallel algorithms.

D. SLA and deadline priority algorithm

We here describe how to integrate the re-defined cascade and parallel algorithms with a general SLA and deadline priority scheme.

At each instant of time t the algorithm can be decomposed in the following phases. Let N a be the set of users that have started to be served at time t, N n the set of new tenants submitting their first demands at time t and N d the set of users whose demands were delayed at time t -16 .

1) Resource availability update: a group of N a users with demand matrix and minimal demand matrix respectively D a and D m a has to be served because accepted in a previous instant of time, with a service time frame still not expired. Each resource is consequently updated as follows R * j = R j -i∈Na D m aij , ∀j ∈ M , i.e., considering that at least a minimal demand for each user has to be guaranteed. This is possible if the available resource of the provider does not change, due to the fact that in the previous instant of time t -1 demands were servedin some cases also with other users undergoing service expiration at time t -1 7 . 2) Distributed allocation: Cascade or parallel algorithms described in section V-C1 and V-C2 provide the distributed allocation. The user delay policy is considering only users delayed in a previous step N d and the new group of tenants N n arriving at instant t. 3) Demand, priority and availability rate update: After the resource is allocated:

• the users with the service expired at time t are removed from N a , • the users served for the first time at the t instant are added to N a , • the users submitting a demand at t but not served are added to N d . In order to try to serve also users with low priority, if the deadline of a tenant demand falls at time t + 1, the priority is increased to the highest one 8 . In this way the tenant has higher probability not to be delayed and consequently served before the expiration of its request. If, despite the increased priority, the tenant cannot be served, its availability rate is updated. Figure 14 gives an example of algorithm dynamics. We can notice that each user can be accepted or delayed in the service time frame between the demand submission and the deadline, once a demand of a tenant is accepted it is served for a number of instants of time equal to the service time frame τ t . The acceptance or delay of the demand depends, as already explained, on the resource R * j and the delay policy used by the providers.

To conclude, let us highlight that in order to account for dynamic resource demand, we can model different demands for a same user over different service time frames, including as well a change in priority over time to favor servicing demands in due time. Furthermore in practice, the available resource can vary across service time frames, with no actual impact on the algorithm which can adapt to changing available resource parameters over time.

E. Numerical analysis

We provide a numerical analysis of the sOCRA, sPRA1 and sPRA2 algorithms. We simulate 1000 time instants, with demands arrival following a Poisson distribution with mean 3. The demands are generated as done in Section IV-C3 while the minimum demand is set to 40% of the demand for each user. Table V shows the settings of the simulations. The four considered services are differentiated accordingly to the demand, the priority index, the deadline and the service time 7 In case the providers decrease their available resource it is possible that the allocation for some of these users fall below the minimum threshold given by the SLA 8 Other strategies can be used to try to serve also users with low priority before their demand expire. For example, the priority can be increased in a gradual way (passing from the tenants user level of priority to the upper one) each given number of instants of time. We consider two metrics to analyze the performance of our algorithm. The first one is the Waiting Time Ratio (WTR) calculated as the ratio of the waiting time over the deadline, that is the maximum waiting time of a tenant. The second metric is the Acceptance Ratio that is the ratio of the number of users served, independently of when (soon or at an instant of time close to the deadline), over the number of users demanded resources. We compare our proposed scheduling algorithm to a baseline one where the selection of the user to serve is random instead of following the user delay policy. We want to emphasize that the analysis does not go into the value of the allocation provided using the cascade or parallel algorithms as we want to assess the effectiveness in using an enhanced user selection policy.

Figure 15 shows the Cumulative Distributed Function (CDF) of the WTR for the two algorithms, as a function of the available resource. If the waiting time is zero, i.e., the tenant is served when it submits the demand, then the WTR is equal to 0 while if WTR=1 the tenant is not served. As one would expect, the number of served users, both with the baseline and our algorithm, is increasing if the available resources Fig. 16: Boxplot of the Acceptance Ratio as function of the congestion level. increase; for example, in the case of URLLC requests with R 1 = 3Colavg(D) we are able to serve less than 20% of the tenants while with R 4 = 20Colavg(D) we can serve around 35% of the tenants with the baseline algorithm and more than the 60% of the tenants with our algorithm. We highlight that the step-like behavior of the URLLC CDF is due to the fact that the deadline is equal to 2, and consequently the WTR can have only three values. Furthermore, we can observe the good performance of the algorithm into serving users with high priority. In fact, in case of URLLC and eMBB services the number of served users, independently of the waiting time, is higher with our algorithm while it is inferior for mMTC and Best effort services. In particular, the greater increase of served users with our algorithm happens thanks to the increase of the priority in the instant preceding the deadline. As a negative aspect it must be noted that the dotted line is above the straight line until the instant before the deadline thus the waiting times are longer with our approach.

In Figure 16 we group the results based on the congestion level and we plot the acceptance ratio. We can notice an expectable behavior, with higher acceptance ratio for services with higher priorities, for each congestion range, and decreasing acceptance ratio for each type of service when the congestion level increases. In particular, when the congestion is high (Fig. 16c and16d), due to the lack of sufficient resources, tenants of low priority services as the mMTC and Best effort ones are rarely served.

VI. CONCLUSION

In this work we proposed algorithms to decentralize 5G slice resource allocation, using two cascading algorithms and two parallel algorithms. We extensively compared them, showing the advantages and disadvantages, also with respect to a centralized approach. In particular, we analyze the delay budget, the pros and cons in terms of reallocation, presence of a multi-domain orchestator, message complexity, level of confidentiality and possibility of allocate the radio resources independently. Finally by numerical simulations we (i) characterize the re-allocation events using the OCRA approach, (ii) estimate the percentage of inefficient solutions using PRA-1, and (iii) calculate the distance of distributed approaches solutions to the centralized one.

We then extended the algorithms proposing an algorithm to include Service Level Agreements for enforcing minimal allocation guarantees and time constraints. The numerical analysis shows that the proposed algorithm has good performances in terms of waiting time and acceptance ratio, increasing the service rate of tenants with high priority compared to a baseline algorithm not considering the tenants priorities.

Future works on the subject can be on fault-tolerant distributed multi-resource allocation, and on the integration into ORAN/SDRAN systems of the proposed algorithms. Moreover, new fairness concepts and allocation rules for distributed multi-resource allocation may also be investigated.

APPENDIX

Proof of the delay budget and message complexity Let us remember that the transfer times is τ , the allocation computing times is δ and that the actions bringing delay in the algorithms are:

• Demand submission: delay between the submission of the demand by the users and the receipt of the demand by the multi-domain orchestrator (centralized case) or the resource provider (distributed case); • Solution submission: delay between the submission of the solution by one or more provider and the receipt of the solution by one or more provider; • Other information submission: delay between the submission of other information type by one or more providers or by the multi-domain orchestrator and the receipt of the solution by one or more providers or by the multi-domain orchestrator; • Allocation computation: delay required by the provider or multi-domain orchestrator to calculate the solution. Table VI shows the number of each action necessary to allocate the resources with the considered algorithms and the budget delay resulting from this. To calculate the message complexity we need to count the exchanged messages, i.e., the number of arrows in Figure 6 in case of three providers. For a general case with p providers the results are proved in Table VII.

Numerical analysis: Amazon ECinstances

We provide in the following the Amazon EC2 instances table used to generate users demands.

Fig. 1 :

 1 Fig. 1: Multi-resource subsystems in virtualized access networks.

  is the vector of the percentage of demand allocated to each tenant. The allocation is not trivial if it exists a resource j ∈ M such that n i=1 d ij > r j Algorithm 1 Priority-aware allocation rules logic Input: R, D, N, M, γ Output: x for pr = 1 : s do S=set of user with γ = pr Q=set of user with γ > pr if i∈S dij ≤ rj, ∀j ∈ M then x=ones(|S|) else xS= solution of the selected allocation rule xQ=zeros(|Q|) exit for loop end if end for

Example 1 .

 1 Let us consider the problem (D, R, γ) with R = (100, 30, 600, 80) and D = 1, 1, 1). The resources are radio (in number of resource blocks RB), link (in Gbps), RAM (in GB) and CPU (in number of vCPU). The resource providers are 3: radio, network link and cloud providers.

Fig. 3 :

 3 Fig. 3: CRA algorithm. Algorithm 2 CRA Input: R, D, N, M, γ, P Output: x Each provider k ∈ P receives D k , i.e. the submatrix of demands for the resources provided by k The first provider calculates x The first provider sends x to the second provider for k = 2 : p do if n i=1 dijxi > rj, for at least one j provided by k then Provider k updates x (old values of xi are upper bound) end if if k < p then Provider k sends x to provider k + 1 else Provider k sends x to all the other providers Providers 1, ...., p -1 reallocate the resources end if end for

Example 2 .( 1 )

 21 Let us consider the same problem (D, R, γ) of Example 1. The algorithm's steps are: The radio resource provider receives the demand vector (20, 20, 30), the link resource provider receives the demand vector (10, 25, 10) and cloud resource provider receives the demand matrix

Fig. 4 :

 4 Fig. 4: OCRA algorithm. The steps not always necessary are drawn in dashed line. Algorithm 3 OCRA Input: R, D, N, M, γ, P Output: x Each provider k ∈ P receives D k , i.e. the submatrix of demands for the resources provided by k Each provider k ∈ P calculates the congestion level µ k and sends it a multi-domain orchestrator Each provider k ∈ P receives the new order of the resources calculated by the multi-domain orchestrator The first provider calculates x The first provider sends x to the second provider for k = 2 : p do if n i=1 dijxi > rj, for at least one j provided by k then Provider k updates x (old values of xi are upper bound) Provider k sends x to all the k -1 previous providers Providers 1, ...., k -1 reallocate the resources end if if k < p then Provider k sends x to provider k + 1 end if end for

2 .( 7 )

 27 x c = (0.68, 0.4, 0.68) and a c = 108.8 27.2 195.2 25.6 108.8 27.The cloud resource provider sends the vector x c = (0.68, 0.4, 0.68) to the link and radio resource providers that re-allocate the resources obtaining a r = (13.6, 8, 20.4) and a l = (6.8, 10, 6.8). C. Ordered Cascading Resource Allocation (OCRA) Algorithm 4 PRA Input: R, D, N, M, γ, P Output: x Each provider k ∈ P receives D k , i.e. the submatrix of demands for the resources provided by k Each provider k ∈ P calculates the value of x Each provider sends the allocation vector to each of the other providers A consensus algorithm provides the final value of x

Example 3 .

 3 Let us consider the same problem (D, R, γ) of Example 1. The algorithm's steps are: (1) Each resource provider receives the demand vector/matrix. (2) Each resource provider calculates the congestion level: µ r = 0.7 µ l = 1.5, µ c = 1.8. (3) The multi-domain orchestrator sends the resources order to the resource providers. The first resource to be allocated is the cloud followed by the link and the radio. (4) The cloud resource provider calculates the allocation, for example using the DRF: x A = (0.67, 0.412, 0.67), a c = 107.2 26.8 201.1 26.4 107.2 26.8

Fig. 6 :

 6 Fig. 6: Involved signaling for the centralized algorithm and the proposed distributed ones, for the radio-link-cloud scenario, as a function of time, under the hypothesis of upper bound on transfer times (τ ) and equal allocation computing times (δ). The dashed arrows indicate not necessary steps, and the red arrows correspond to extra steps of the 2-phase consensus algorithm.

Example 4 .

 4 Let us consider the problem (D, R, γ) of Example 1. The value of x calculated in a parallel way is x r =(1, 1, 1) for the radio resource, x l =(1, 0.4, 1) for the link resource using the MMF allocation rule and x c =(0.67, 0.412, 0.67) for the cloud resource, using the DRF allocation rule.Using the PRA-1, each resource provider allocates the resources using x = (0.67, 0.4, 0.67). The allocations are: a r = (13.4, 8, 20.1), a l = (6.7, 10, 6.7), a c =

Fig. 7 :

 7 Fig. 7: Comparison of delay budgets with p = 3. Case 1: τ δ, t = δ. Case 2: δ τ , t = τ . Case 3: τ = δ = t.

Fig. 8 :Fig. 9 :

 89 Fig. 8: Pareto efficiency for an example with 2 tenants and 2 resources provided by p 1 and p 2 . Hypothesis: in the OCRA plot p 1 more congested than p 2 and in the PRA-2 plot p 2 more congested than p 1 .

Fig. 10 :

 10 Fig. 10: Chebyshev distance.

Fig. 11 :

 11 Fig. 11: Chebyshev distance average and service rate.

Fig. 12 :

 12 Fig. 12: Different resource allocation scenarios. The MMF extension is challenging, for example, if users with high demands have high minimal demands as in (b) and (c). The resource left after the allocation of the minimal demand has to be divided equally between users (b) or it has to be allocated to the one with smaller demand (c).

Definition 3 .Fig. 13 :

 313 Fig.13: Bi-dimensional representation of a nominal and minimal demand for two resources, when the linear dependency between resources is the same for the two types of demands.

Fig. 14 :

 14 Fig. 14: Example of SLA-deadline priority algorithm dynamic.

Fig. 15 :

 15 Fig. 15: WTR CDF -The dotted line is for the baseline algorithm and the straight one for our proposal. frame. The service time frame is simulated using a geometric distribution with different parameters depending on the service type. We consider four experiments varying the quantity of available resource. The value of the resource, linked to the average demand of each resource, is chosen as follows: R 1 = 3Colavg(D), R 2 = 5Colavg(D), R 3 = 10Colavg(D), R 4 = 20Colavg(D), where Colavg(D) is the average by column of the simulated demands in the dataset D.We consider two metrics to analyze the performance of our algorithm. The first one is the Waiting Time Ratio (WTR) calculated as the ratio of the waiting time over the deadline, that is the maximum waiting time of a tenant. The second metric is the Acceptance Ratio that is the ratio of the number of users served, independently of when (soon or at an instant of time close to the deadline), over the number of users demanded resources. We compare our proposed scheduling algorithm to a baseline one where the selection of the user to serve is random instead of following the user delay policy. We want to emphasize that the analysis does not go into the value of the allocation provided using the cascade or parallel algorithms as we want to assess the effectiveness in using an enhanced user selection policy.Figure15shows the Cumulative Distributed Function (CDF) of the WTR for the two algorithms, as a function of the available resource. If the waiting time is zero, i.e., the tenant is served when it submits the demand, then the WTR is equal to 0 while if WTR=1 the tenant is not served. As one would expect, the number of served users, both with the baseline and our algorithm, is increasing if the available resources

TABLE I :

 I Delay budget and message complexity -General case with p resource providers.

TABLE II :

 II Pros vs cons of studied algorithms.

TABLE III :

 III Occurrence of re-allocations with the OCRA algorithm using common single-resource rules.

	Allocation rule	Percentage of non-optimal solutions
	MMF	57%
	Mood value	72%
	Proportional	56%

TABLE IV :

 IV Percentage of non-Pareto efficient solutions using the PRA-1 algorithm.

  8) x-1 0.8 Best effort 1 + (1 -0.01) x-1 0.01

		URLLC	2
	Deadline λ	eMBB mMTC	100 50
		Best effort	100
		URLLC	1
	Priority γ	eMBB mMTC	2 3
		Best effort	4

TABLE V :

 V Simulation settings.

Table 1 :

 1 Amazon EC2 instances

	API Name	Memory (GB)	vCPUs Gbps	Instance Type
	m4.10xlarge	160.00	40.00	10.00	General purpose
	m4.16xlarge	256.00	64.00	25.00	General purpose
	c5.9xlarge	72.00	36.00	10.00	Compute optimized
	c5.18xlarge	144.00	72.00	25.00	Compute optimized
	c4.8xlarge	60.00	36.00	10.00	Compute optimized
	r4.8xlarge	244.00	32.00	10.00	Memory optimized
	r4.16xlarge	488.00	64.00	25.00	Memory optimized
	x1.16xlarge	976.00	64.00	10.00	Memory optimized
	x1.32xlarge	1952.00	128.00	25.00	Memory optimized
	x1e.16xlarge	1952.00	64.00	10.00	Memory optimized
	x1e.32xlarge	3904.00	128.00	25.00	Memory optimized
	p3.8xlarge	244.00	32.00	10.00	Accelerated comput.
	p3.16xlarge	488.00	64.00	25.00	Accelerated comput.
	p2.8xlarge	488.00	32.00	10.00	Accelerated comput.
	p2.16xlarge	732.00	64.00	25.00	Accelerated comput.
	g3.8xlarge	244.00	32.00	10.00	Accelerated comput.
	g3.16xlarge	488.00	64.00	25.00	Accelerated comput.
	f1.16xlarge	976.00	64.00	25.00	Accelerated comput.
	h1.8xlarge	128.00	32.00	10.00	Storage optimized
	h1.16xlarge	256.00	64.00	25.00	Storage optimized
	d2.8xlarge	244.00	36.00	10.00	Storage optimized
	i3.8xlarge	244.00	32.00	10.00	Storage optimized
	i3.16xlarge	488.00	64.00	25.00	Storage optimized

The considered (weighted) satisfaction vectors are x, ds • x, ps and ds • ps where x is the classical satisfaction, i.e. the percentage of resource allocated to a user, ds • x is the weighted classical satisfaction that takes inspiration from the DRF allocation rule, ps is player satisfaction the correct way to measure the satisfaction in full knowledge environment[START_REF] Fossati | A Mood Value for Fair Resource Allocations[END_REF],[START_REF] Fossati | Fair Resource Allocation in Systems with Complete Information Sharing[END_REF] and ds • ps is the weighted player satisfaction considering the dominant share to weight the ps satisfaction.

• We consider multi-resource allocation problems in order to provide end-to-end network slices, and not only spectrum sharing problems as in[START_REF] Caballero | Multi-tenant radio access network slicing: Statistical multiplexing of spatial loads[END_REF],[START_REF] Xiao | Distributed Resource Allocation for Network Slicing Over Licensed and Unlicensed Bands[END_REF]. • We provide distributed algorithms, i.e., the decisionmaking is the result of a distributed set of computations at different nodes, in order to let each resource provider play a role in the slice provisioning, differently from the above-mentioned works.

We consider that during the service time frame τ the demand of the user is fixed. In practice, it can change across service time frames so as to take into account dynamic resource demands.

We consider the available resource as fixed in a given time frame, knowing that the resource available could also vary at different service time frames, to cope for the fact that externalities can change the actual available resource at a given service time frame.

In practice, the minimum service to be guaranteed is established by the SLA, which is a contract between the resources providers and the users so it is possible that, for different resources, different minimum values are negotiated.

Note that we avoid the subscript t for the sake of simplicity.

Email: {firstname.lastname}@cnam.fr


Semaan Amine
email: semaan.amine@irccyn.ec-nantes.fr

Stéphane Caro
email: stephane.caro@irccyn.ec-nantes.fr

Philippe Wenger
email: cphilippe.wenger@irccyn.ec-nantes.fr

Constraint and Singularity Analysis of the Exechon

Keywords: parallel manipulator, singularity, Grassmann-Cayley algebra, Exechon

This paper deals with the constraint and the singularity analysis of the Exechon. Using the screw theory, the constraint and actuation wrenches acting on the moving platform are analyzed. The motion pattern of the Exechon is characterized based on a representation of the constraint wrenches in the projective space. A wrench graph representing the constraint and actuation wrench systems in the projective space is obtained. Based on this wrench graph, a superbracket of the Exechon is formulated. Finally, this superbracket is explored to provide the geometric conditions for the parallel singularities of the Exechon.

Introduction

When the manipulation tasks require less than six dof, the use of a lower-mobility parallel manipulator (PM) may bring some advantages (very fast machine, simple architecture) in addition to the known features of PMs. The parallel singularities of lower-mobility PMs are critical configurations characterized by either a loss of control or a change of the motion performed by the moving platform. Thus, the determination of these singularities is a central issue in the field of parallel robots. The kinematic characteristics of lower-mobility PMs make their constraint analysis, singularity analysis and design a more complex problem in comparison with their 6-dof counterparts.

For a ( 6) n  -dof PM, in a general configuration, the actuators apply a n -system, a  , of actuation wrenches, whereas the limbs apply a (6 ) n  -system, c  , of constraint wrenches on the moving platform. Based on screw theory [START_REF] Ball | A Treatise On the Theory of Screws[END_REF][START_REF] Hunt | Kinematic Geometry of Mechanisms[END_REF][START_REF] Kong | Type Synthesis of Parallel Mechanisms[END_REF], Ling and Huang [START_REF] Ling | Kinestatic analysis of general parallel manipulators[END_REF], and then Joshi and Tsai [START_REF] Joshi | Jacobian Analysis of Limited-DOF Parallel Manipulators[END_REF], developed a method to derive a 6 6  Jacobian matrix J for a lower-mobility PM. Accordingly, in a general configuration, the rows of J for a ( 6) n  -dof PM are composed of n linearly independent actuation wrenches plus [START_REF] Ben-Horin | Singularity Analysis of a Class of Parallel Robots Based on Grassmann-Cayley Algebra[END_REF] n  linearly independent constraint wrenches.

Parallel singularities are related to the rank deficiency of J. Classical methods for the parallel singularity analysis consist in a direct analysis of J by exploring the vanishing conditions of its determinant. These methods mostly fail to provide satisfactory results since the determinant of the Jacobian matrix is usually unwieldy to assess, even with a computer algebra system. Thus, alternative approaches, using Grassmann-Cayley Algebra (GCA) [START_REF] Ben-Horin | Singularity Analysis of a Class of Parallel Robots Based on Grassmann-Cayley Algebra[END_REF][START_REF] Kanaan | Singularity Analysis of Lower-Mobility Parallel Manipulators using Grassmann-Cayley Algebra[END_REF][START_REF] Amine | \Singularity Analysis of the H4 Robot using Grassmann-Cayley Algebra[END_REF][START_REF] Amine | Singularity Conditions of 3T1R Parallel Manipulators with Identical Limb Structures[END_REF] and/or Grassmann Geometry (GG) [START_REF] Amine | Singularity Conditions of 3T1R Parallel Manipulators with Identical Limb Structures[END_REF][START_REF] Merlet | Singular Configurations of Parallel Manipulators and Grassmann Geometry[END_REF], were proposed in the literature to deal with the vanishing conditions of this determinant. These approaches are based on the correspondence between the lines composing the Jacobian matrix and Plücker vectors, namely, six-component vectors representing lines in the 3dimensional projective space.

The GCA provides an approach for the singularity analysis of a PM through the superbracket, which is bracket representation of the determinant of the Jacobian matrix. By exploring this superbracket, the parallel singularity conditions of a PM can be obtained.

The classification of singularities of PMs has stimulated the interest of many researchers [START_REF] Joshi | Jacobian Analysis of Limited-DOF Parallel Manipulators[END_REF][START_REF] Gosselin | Singularity Analysis of Closed-Loop Kinematic Chains[END_REF][START_REF] Zlatanov | Singularity Analysis of Mechanisms and Robots Via a Velocity-Equation Model of the Instantaneous Kinematics[END_REF][START_REF] Fang | Structure Synthesis of a Class of 4-DoF and 5-DoF Parallel Manipulators with Identical Limb Structures[END_REF][START_REF] Conconi | A New Assessment of Singularities of Parallel Kinematic Chains[END_REF]. In this paper, we adopt a classification similar to the one used in [START_REF] Joshi | Jacobian Analysis of Limited-DOF Parallel Manipulators[END_REF][START_REF] Fang | Structure Synthesis of a Class of 4-DoF and 5-DoF Parallel Manipulators with Identical Limb Structures[END_REF]. Accordingly, a lower-mobility PM can exhibit two types of parallel singularities, namely, constraint singularities and actuation singularities. Constraint singularities of a n<6-dof PM correspond to the degeneracy of its (6-n)-constraint wrench system c  . In such configurations, at least one of the initial limited motions will be no longer constrained and the moving platform of the PM gains one or several dof. In turn, actuation singularities correspond to configurations in which J is rank deficient while the PM is not in a constraint singularity, namely, while its constraint wrench system c  does not degenerate. In such configurations, the moving platform of the PM has some instantaneous uncontrolled motions. This paper deals with the constraint and singularity analysis of the Exechon [START_REF] Neumann | Adaptive in-jig high load Exechon machining & assembly technology[END_REF]. To this vein and to better understand the geometric characteristics of the Exechon, it is necessary to use the concept of points at infinity [START_REF] Kanaan | Singularity Analysis of Lower-Mobility Parallel Manipulators using Grassmann-Cayley Algebra[END_REF][START_REF] Amine | Singularity Conditions of 3T1R Parallel Manipulators with Identical Limb Structures[END_REF] in the projective space 3  . This concept allows to visualize the relations between the constraint wrenches (the intersection of two parallel constraint forces and the representation of the constraint moment, which is a line at infinity) and to formulate a superbracket expression that provides geometric conditions for parallel singularities.

The paper is organized as follows. First, the main properties of points and lines at infinity in 3  as well as the expression of the superbracket decomposition of GCA are recalled. Then, the constraint analysis of the Exechon is performed. The motion of the moving platform is not easy to grasp. Thus, a representation of the constraint wrench system in 3  helps understand the PM's motion pattern. A wrench graph representing the actuation and the constraint wrenches in P 3 is also obtained. This wrench allows formulating a superbracket of the PM. Finally, this superbracket is explored to provide geometric conditions for the parallel singularities of the Exechon.

Background

The 3 -dimensional projective space 3  is characterized by the affine space 3  in addition to the plane at infinity   . It is noteworthy that the coordinates of a projective element are determined up to scale. A projective point has four homogeneous coordinates whereas a projective line has six Plücker coordinates represented by its Plücker coordinate vector. The following properties highlight the relations between projective elements:  A finite point, A , is represented by its homogeneous coordinates vector ( , , ,1) T a a a a  , the first three coordinates being its Cartesian coordinates in 3  ;  A finite line,  , is represented by its Plüker coordinates vector ( ; )   s r s  ; where s is the unit vector of  , r is the position vector of any point on  and (  r s ) represents the moment of  with respect to the origin;  Let underlined points denote points at infinity. Any finite line, ( ;

)   s r s 
, has a unique point at infinity ( ;0) c  s . This point only depends on the line direction and is determined up to scale. Accordingly, if a and b are two finite points on F , then c b a   .

Furthermore, all finite lines directed along s intersect at one common point at infinity, namely, c ;  All finite planes of normal vector m , have a common line at infinity. This line is given by: (0; )  m  and passes through the point at infinity on any finite line orthogonal to m ;

 Two lines at infinity 1

1 (0; )  m  and 2 2 (0; )  m  intersect at a unique point at infinity 1 2 ( ;0) g   m m
.

GCA and superbracket

The GCA was developed by H. Grassmann (1809-1877) as a calculus for linear varieties operating on extensors with the join  and meet  operators. The latter are associated with the span and intersection of vector spaces of extensors characterized by their step. GCA makes it possible to work at the symbolic level, and therefore, to produce coordinate-free algebraic expressions for the singularity conditions of spatial PMs. For further details on GCA, the reader is referred to [START_REF] Ben-Horin | Singularity Analysis of a Class of Parallel Robots Based on Grassmann-Cayley Algebra[END_REF][START_REF] White | Handbook of Geometric Computing[END_REF] and references therein.

The superbracket and its decomposition

Many researchers in the field of parallel robots have explored the determinant of the 6 6  Jacobian matrix J to analyze the singularities. The columns of T J of a PM are usually six Plücker vectors. Each Plücker vector, being of six components, is the support of an extensor of step 1 in the 5dimensional projective space 5  (a Plücker vector corresponds to a point in 5  ). The join (also called superjoin) of these six 1-extensors in 5  is equal to the determinant of T J , up to scale. This determinant matrix, whose columns are the Plücker coordinates of six lines (2-extensors), is called the

superbracket in GCA (2) ( ) V  [17]
. Thus, a singularity occurs when this superbracket vanishes. The superbracket is an expression involving 12 points selected on six projective lines (2extensors) and can be developed into a linear combination of 24 bracket monomials [START_REF] Ben-Horin | Singularity Analysis of a Class of Parallel Robots Based on Grassmann-Cayley Algebra[END_REF][START_REF] Mcmillan | Invariants of Antisymmetric Tensors[END_REF], each one being the product of three brackets of four projective points:

where

1 [ ][ ][ ] y abcd efgi hjkl   2 [ ][ ][ ] y abcd efhi gjkl  3 [ ][ ][ ] y abcd efgj hikl  4 [ ][ ][ ] y abcd efhj gikl   5 [ ][ ][ ] y abce dfgh ijkl  6 [ ][ ][ ] y abde cfgh ijkl   7 [ ][ ][ ] y abcf degh ijkl   8 [ ][ ][ ] y abdf cegh ijkl  9 [ ][ ][ ] y abce dghi fjkl   10 [ ][ ][ ] y abde cghi fjkl  11 [ ][ ][ ] y abcf dghi ejkl  12 [ ][ ][ ] y abce dghj fikl  13 [ ][ ][ ] y abdf cghi ejkl   14 [ ][ ][ ] y abde cghj fikl   15 [ ][ ][ ] y abcf dghj eikl   16 [ ][ ][ ] y abdf cghj eikl  17 [ ][ ][ ] y abcg defi hjkl  18 [ ][ ][ ] y abdg cefi hjkl   19 [ ][ ][ ] y abch defi gjkl   20 [ ][ ][ ] y abcg defj hikl   21 [ ][ ][ ] y abdh cefi gjkl  22 [ ][ ][ ] y abdg cefj hikl  23 [ ][ ][ ] y abch defj gikl  24 [ ][ ][ ] y abdh cefj gikl   A bracket [
] abcd is null if and only if (iff) the projective points , , a b c and d are coplanar. The bracket of four projective points is defined as the determinant of the matrix whose columns are the homogeneous coordinates of these points.

Constraint analysis of the Exechon

The Exechon is a machine tool recently developed by Neumann [START_REF] Neumann | Adaptive in-jig high load Exechon machining & assembly technology[END_REF] based on the Tricept PM. The kinematic analysis of the Exechon was addressed in [START_REF] Bonnemains | Definition of a new static model of Parallel Kinematic Machines: highlighting of overconstraint influence[END_REF][START_REF] Zoppi | Kinematics Analysis of the Exechon Tripod[END_REF]. The basic architecture of the Exechon consists of a 3-dof PM mounted in series with a spherical wrist. This paper deals with the constraint analysis of the first part only, called hereafter the Exechon PM.

The Exechon PM presented in Fig. 1 has three limbs: , is directed along i p ;  The axis of 3 R is directed along 3 s , which is orthogonal to 2 s . ( , )

1 1 1 1 1 12 3 L UPR R R P R   , 2 2 2 2 2 1 2 3 L UPR R R P R   and
A   s r s  ,  1 1 02 2 2
( , )

A   s r s  ,  1 1 1 (, )   p  and  1 1 03 2 2 ( , ) B   s r s 
, respectively where the superscript  () denotes a unit screw. Since  span( , ) span( , )

      [8], with  1 12 2 1 (, )    s p  . Therefore, 1
L is a 2T2R limb, namely, it generates two independent translations and two independent rotations. The constraint wrench system 1 c  of limb 1

L is spanned by screws that are reciprocal to all the twists of 1  :

  1 1 1 span( , ) c c c     (2)
where

 1 1 2 2 ( , ) c A   s r s  and  1 1 2 (0, ) c   s s  .
Limb 2 L

The twist system 2  of limb 2 L is spanned by:  ( , )

A   s r s  ,  2 2 02 2 2 ( , ) A   s r s  ,  2 2 (0, )   p  ,
c c c c      , with    12 1 2 1 2 (0, ) c c c     s s    .
Limb 3 L

The twist system 3  of limb 3 L is spanned by:  L is given by: 

3 3 span( ) c c    (4)
where 

( , )

c A   s r s  .

Constraint wrench system of the Exechon PM

Since  

1 3 c c  
 , the limbs of the Exechon PM apply four different constraints to its moving platform. The constraint wrench system of this PM is given by:    

1 2 3 1 span( , , , ) c c c c c PM       (5)
where

 1 1 2 2 ( , ) c A   s r s  ,  2 2 2 2 ( , ) c A   s r s  ,  3 3 3 3 ( , ) c A   s r s  and  1 1 2 (0, ) c   s s  . Since     1 2 1 1 span( , ) span( , ) c c c c      , c PM
 is a 3 -system. Therefore, the Exechon PM is an overconstrained 3 -dof parallel manipulator. Indeed, the limbs apply redundant constraint on the moving platform.

Motion of the moving platform in a general configuration

The constraint wrench system c PM  of the Exechon PM provides information about the constraints applied to its moving platform in a general configuration. In order to characterize the motion of the moving platform in such a configuration, one should determine the twist system PM  of the moving platform, which is reciprocal to c PM  .

Let 1 a , 2 a and 3 a be the extensors of step 1 associated with points 1 A , 2 A and 3 A , respectively and let ( ,0)

i i s  s , 1, 2,3 i 
, be the 1-extensor representing the point at infinity in the direction of i s . Then,  a s ;  A A (Fig. 1) is directed along 1 s , the point at infinity on this line is 1 s . Hence, the line at infinity of plane  is   . Thus, they form a 1-$\  -system spanned by:  span( , , )

PM       ( 6
)
where  01  and  02  are any two distinct zero-pitch twists whose axes lie in plane  and pass through point I . The moving platform of the Exechon PM provides a pure translation along 1 2  s s plus two independent rotations. These rotations are about any two distinct axes in plane  and passing through point I .

Actuation wrench system of the Exechon PM

Each limb of the Exechon applies one pure actuation force whose axis is along the direction of the corresponding actuated \textsf{P}-joint, as follows:

 1 1 1 1 ( , ) a A   p r p  ;  2 2 2 2 ( , ) a A   p r p  and  3 3 3 3 ( , ) a A   p r p 
. The actuation wrench system of the Exechon PM is given by:    . A wrench graph of the Exechon PM is obtained in Fig. 3.

Singularity conditions of the Exechon PM

The Exechon is an over-constrained PM since the limbs can apply four distinct constraint wrenches but they constrain only three dof. In that case, the transpose of the Jacobian matrix can be written as a 6 7  matrix, namely,

       1 2 3 1 2 3 1 T a a a c c c c      J        (8)

Superbracket expression

A parallel singularity occurs when the rank of J becomes smaller than six, namely, when the seven wrenches of Eq. 8 span a n<6-system  Consequently, there are

3 3 2       
ways to select two among these three wrenches in the superbracket expression and thus, we can formulate 3 superbracket expressions for the Exechon PM. However, since    

1 2 1 1 span( , ) span( , ) c c c c     
in any robot configurations, these three superbracket expressions are always equivalent to each other. Thus, it is sufficient to analyze one of the three possible expressions.

Superbracket decomposition and singularity conditions

Here we will analyze uniquely the superbracket of 1

The decomposition of 1 S leads to three non-zero monomials as follows:

1 1 1 2 2 1 2 2 3 2 3 3 3 1 1 2 2 1 2 2 3 2 3 3 3 1 1 2 2 1 2 2 3 2 3 3 3 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

S

a p s a a a s a p p a s a p s p a a s a a p a s a p s a a a p a s p a s

   (10)
Now let consider the sum 1

• • • 2 2 1 1 2 1 2 3 3 3 3 2 [ ] [
] [ ] a p s a a a s a p p a s . It is developed as follows:

• • • 2 2 1 1 2 1 2 3 3 3 3 2 [ ] [
] [ ] a p s a a a s a p p a s = [ a p s s

1 2 2 3 2 3 3 3 ][ ][ ] a a p a a p a s + 1 1 2 2 1 2 2 3 [ ] [ a p s p a a a a 2 3 3 3 ][ ] s p a s -1 1 2 2 1 2 2 3 2 3 3 3 [ ] [ ] [ ] a p s p a a s a a p a s (11)
The crossed out brackets of Eq. 11 being equal to zero, we can notice that the superbracket of the Exechon PM can be written as:

• • • 2 2 1 1 1 2 1 2 3 3 3 3 2 [ ] [ ] [ ] S
a p s a a a s a p p a s 

From [START_REF] Ben-Horin | Singularity Analysis of a Class of Parallel Robots Based on Grassmann-Cayley Algebra[END_REF], it follows that the right hand side of Eq. 12 is the result of the meet of four planes:

1 1 2 ( ) a p s , 1 2 3 ( ) a a a , 3 3 3 ( ) p a s and 2 2 2 ( ) a s p . Hence, 1 1 1 2 1 2 3 3 3 3 2 2 2 ( ) ( ) ( ) ( ) S a p s a a a p a s a s p     (13)
The singularity conditions of the Exechon PM depend on some relations between four planes. Plane L and 3 L , respectively. Figure 4 shows planes 1 2 ,   and 3  of the Exechon PM. Generally, the Exechon PM exhibits a parallel singularity whenever the four foregoing planes intersect at least at one point. This point can be a finite point or a point at infinity. As a matter of fact, the four planes 1 The superscript • () stands for permuted elements as pointed out in [START_REF] White | Handbook of Geometric Computing[END_REF] intersect at a point at infinity whenever one can find a finite line (or a direction) parallel to the four planes at once. Moreover, Eq. 13 also holds the following particular cases:

Conclusions

This paper presented the constraint and singularity analysis of the Exechon. The constraint analysis was performed by using the concept of points and lines at infinity and the screw theory. The motion pattern of the moving platform was not easy to grasp. Thus, a representation of the constraint wrenches in the projective space proved very useful to describe the motion of the moving platform in a general configuration. Then, a wrench graph representing all the wrenches of the manipulator in the projective space was obtained to help formulating the superbracket expression. Finally, this superbracket was explored to provide geometric conditions for the parallel singularities of the Exechon.

Figure 1 : 1 L

 11 Figure 1: Schematic representation of the Exechon PM

  Let  be the finite plane containing the axes of  1c  and  2c  . Since line 1 2

   . The constraint wrenches of the Exechon PM are illustrated in Fig.2.

Figure 2 :

 2 Figure 2: Twist system of the Exechon PM Infinite-pitch twists in PM  should be orthogonal to the axes of  1c  ,  2c  and 

  3c

  other hand, the axis of a zero-pitch twist  0  in PM  should be: coplanar with the axis of  3c  , coplanar with the axes of  1c  and  2c  and orthogonal to 1 2  s s . In order to satisfy these two conditions, the axis of a  0i  in PM  should necessarily belong to plane  and cross at the same time the axis of  3c  . Let I be the intersection point between plane  and the axis of  3c  . Hence, zero-pitch twists in PM  form a planar pencil of finite lines in plane  and passing through point I as shown in Fig. 2. Consequently,

Figure 3 :

 3 Figure 3: Wrench graph of the Exechon in 3 



  are always linearly dependent.

1 2 3 a a a is spanned by three fixed points 1 A , 2 A and 3 A

 3123 lying in the plane of the fixed base.

Figure 4 : 2 ,   and 3  1 .

 4231 Figure 4: The Exechon PM, planes 1 2 ,   and 3 

This cannot occur since vectors 3 p and 3 s

 3 are orthogonal in any robot configuration. 2. Two of the four planes coincide. 3. Three of the four planes intersect at a common line. 4. The four planes intersect at a common point.

  and 

									2 03		2 B s r s 2 ( , 	2	)	. The wrench system 2 c  of limb 2 L is given by:
	2 c 		span(	  2 , c   2	c	)			(3)
	where  	2	c		2 A s r s 2 ( , 	2	)	and   2	c 	(0,	1 s s 	2	)	. It should be noticed that   and  1c  are 2c
	identical. Moreover,   and  1c  have parallel axes. Thus, 2c	span(	  1 ,	2	  1 ) span( ,	1 2	)

  This plane contains the axes of the actuation force  However, since vectors 1 p and 2 s are orthogonal in any robot configuration, the foregoing condition turns to be impossible.

							1c  of limb 1 L that
	intersect at a fixed point 1 A . Thus, this plane degenerates if and only if 1 2 p s  , i.e., if 1 2 0   s s	,
	i.e., if the two forces 
	 Plane 2 		2 2 2 a s p	, whose Plücker coordinate vector is	  	2 A r p s 2 2 2 •(   p s	2	)	  	, degenerates.
	This cannot occur since vectors 2 p and 2 s are orthogonal in any robot configuration.
	 Plane 3 		3 3 3 p a s	, whose Pl\"ucker coordinate vector is

1a  and the constraint force  1c  and  1a  become coaxial.