arXiv CSopen access

Dependency-Aware Dominant Resource Fairness for Multi-Tenant Multi-Resource Systems

IEEE TRANSACTIONS ON NETWORKING, VOL. XX, YYYY

1

Dependency-Aware Dominant Resource Fairness for Multi-Tenant Multi-Resource Systems

arXiv:2606.25540v1 [cs.NI] 24 Jun 2026

Zeidan Braik, Francesca Fossati, Sahar Hoteit, Senior Member, IEEE, Stefano Secci, Senior Member, IEEE

Abstract—Multi-resource allocation in network-congested, multi-tenant systems in which demand exceeds available capacity is challenging, as there is no straightforward way to determine how much of each resource to assign, especially when resources are interdependent. Classical approaches such as Dominant Resource Fairness (DRF), which generalizes Max-Min Fairness (MMF) to multiple resources, assume linear proportional dependencies across resources, requiring allocations to follow fixed proportions implied by tenants’ demands. However, this assumption may lead to inefficient allocations and resource waste, with allocated resources that go unused in practice. In this paper, we consider a multi-resource orchestrator and propose the Dependency-aware Dominant Resource Fairness (DDRF) policy, a centralized generalization of DRF that considers inter-resource dependencies: it equalizes active dominant shares of congested resources, preserving DRF’s desirable properties, while avoiding its inefficiency with low-demand tenants. We prove that DDRF always saturates at least one congested resource, ensuring Pareto efficiency and eliminating resource waste. We evaluate DDRF using Amazon EC2 traces and a virtualized radio access network (vRAN) use case while considering real resource dependencies. The results show that DDRF improves effective user satisfaction by up to 80% and reduces resource waste by up to 60% compared to dependency-agnostic baselines, while improving Jain’s fairness index by more than 15% compared to the utilitarian policy. Index Terms—multi-resource allocation, network slicing, DRF.

I. I NTRODUCTION

I

N computing and networking, resource allocation has been a central research direction for decades, spanning contexts from scheduling in operating systems [1] to resource management in datacenters, cloud and radio networks [2]. More recently, its necessity has become especially prevalent in networking [3], where multi-tenant1 infrastructures, such as 5G and cloud-native systems, must share finite resources across diverse services. A fundamental challenge in these environments is congestion, which arises when aggregate traffic exceeds the capacity of at least one resource. Under congestion, resource allocation must decide how to divide scarce capacity across Zeidan Braik is with the Conservatoire National des Arts et Métiers (Cnam), Cédric, Paris, France. (email: [email protected]). Francesca Fossati is with the Sorbonne Université, CNRS LIP6, Paris, France (email: [email protected]). Sahar Hoteit is with the Université Paris-Saclay, CNRS L2S, CentraleSupélec, Gif-sur-Yvette, and with Institut Universitaire de France (IUF), France (email: [email protected]). Stefano Secci is with the Conservatoire National des Arts et Métiers (Cnam), Cédric, Paris, France (email: [email protected]). This work was funded by the French ANR HEIDIS project (contract nb: ANR-21-CE25-0019; https://heidis.roc.cnam.fr) and the IPCEI ME/CT Orange project (contract nb: DOS0239248/00; https://piiec5g.wp.imt.fr). This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible. 1 Hereafter the terms ”tenants” and ”users” are used interchangeably, we use the feminine pronoun (”she”,”her”); this choice is arbitrary.

Radio Resources 𝑐2 𝑑22

(a)

Non-linear Dependency

Slice2

Dependency-Aware Allocation

𝑑21

𝑑11

Radio Resources 𝑑22

(b)

Slice1

𝑎21

Computing

𝑎11

Radio Resources

𝑐1 Resources

Slice2

𝑐2 𝑎22

Slice1

𝑑21

𝑎12

Computing 𝑐1 Resources

Linear Dependency

Slice2

𝑑12

Slice2

𝑎22

Slice1

𝑑12

𝑐2

Radio Resources 𝑐2

Dependency-Agnostic 𝑎12 Allocation

𝑑11

Demand (Request)

Computing

𝑐1 Resources

Slice1

Wasted Allocation

𝑎21

𝑎11

𝑐1

Computing Resources

Allocation

Fig. 1. Comparison of dependency-aware and dependency-agnostic allocations for two slices. Left: demands with a nonlinear dependency in (a) and the imposed linear dependency in (b). Right: resulting allocations; enforcing the linear relation in (b) yields an unused portion, i.e., resource waste.

demand vectors while adopting principled notions of fairness, ensuring tenants are treated equitably under contention. The theory of single-resource allocation is largely complete [4]–[8], with well-established fairness notions such as Max-Min Fairness (MMF) [6] and Proportional Fairness (PF) [4], [5]. In contrast, multi-resource allocation remains an active frontier [9]–[12], as recent efforts seek to extend singleresource fairness to settings with multiple resources [9], [12]. The extensions to multi-resource rules, developed in contexts ranging from cloud computing to congestion control, formalize different notions of fairness. However, multi-resource rules, throughout the literature, are often built on one of two simplifying assumptions: the first is a linear proportional dependency between resources (e.g., if a user requests 2 units of resource 1 and 4 units of resource 2, then the allocation is expected to maintain the same 2:4 ratio across both resources); the second is a structured utility model, most notably the Leontief utility [13]–[15], where a user’s satisfaction is determined by the smallest proportion of resources received, an approach that, in effect, also reduces to linear proportional dependency. Under such linear assumptions, the inherently multi-dimensional problem is reduced to a single-resource problem, as the task becomes finding a single ratio per user that scales its resource demands uniformly. The need to account for generic and realistic dependencies is increasingly critical in modern applications, particularly in networking. For instance, in mobile networks [16], radio and computing resources are coupled in nonlinear ways [17], [18], moreover link bandwidth over midhaul and backhaul [19] depends on the transport block size (TBS), which is defined in 3GPP specifications as a piecewise-affine function of the

2

number of resource blocks [20]. Existing state-of-the-art policies often oversimplify these dependencies e.g. by assuming linear ratios across resources. We refer to these policies in the following as Dependency-Agnostic ones. Ignoring realistic dependencies leads to allocation waste (i.e., resources allocated to tenants but could not be used in practice). Figure 1 shows an example of two network slices: slice 1 asking for small amount of radio resources but higher computing resources (d11 and d12 ), respectively while slice 2 is asking for the opposite (these demands are denoted d21 , d22 ). Top row shows dependency-aware allocations, the bottom row assumes fixed linear proportions (dependency-agnostic). The computing resources have a limited capacity, denoted by c1 while the radio resources have a limited capacity, denoted by c2 . Rectangles on the right represent the allocated amount of resources (a11 , a12 for slice 1 and a21 , a22 for slice 2), with dashed outlines denoting original demands. As shown in the figure, dependency-agnostic allocation leads to resource waste, i.e., resources are allocated but remain unusable in practice due to existing inter-resource dependencies and potential bottlenecks in one or more resources. The presence of generic inter-resource dependencies has been identified in [12]; however, to the best of our knowledge, no other work in the literature has proposed a multiresource allocation approach that explicitly accounts for these dependencies. Authors in [12] introduce a generic formulation that avoids linear aggregation across resources by defining a decision variable for each user–resource pair, thereby enabling dependencies to be expressed directly as constraints. Nevertheless, that way does not provide a systematic characterization of dependency models, nor does it adapt the objective function to account for such dependencies. To fill this gap, we propose a dependency-aware allocation scheme that explicitly accounts for inter-resource dependencies, with the aim of preventing resource waste while ensuring a fair distribution of resources. To design a fair allocation mechanism, two main approaches exist: (i) maximize a Schur-concave utility function [7], [12], [21] and then analyze the fairness properties induced by the optimizer, or (ii) start from a target fairness principle and impose it explicitly as a constraint while maximizing utilization (i.e., satisfied demand) [9], [22], [23]. In this work, we adopt the second approach. Specifically, we generalize maxmin fairness to the dependency-aware multi-resource setting, where equity is imposed directly on allocations: tenants receive equal allocations unless a tenant’s demand is smaller, in which case it is fully satisfied. This corresponds to the leximin principle, inspired by Rawlsian fairness [24], which maximizes the allocation of the least-served tenant before considering the next, and so on. Our approach differs from the Dominant Resource Fairness (DRF) [9] which applies the leximin principle to multi-resource settings by equalizing tenants’ normalized shares of their bottleneck resource. However, DRF faces key limitations, particularly under congestion and in the presence of low-demand tenants, where it may fail to satisfy properties such as bottleneck saturation and share-incentive. More precisely, in this paper we propose the Dependencyaware Dominant Resource Fairness (DDRF) algorithm, a centralized static allocation mechanism that extends DRF to

IEEE TRANSACTIONS ON NETWORKING, VOL. XX, YYYY

handle congestion and generic inter-resource dependencies. In DDRF, tenant satisfaction is determined per resource by introducing a distinct satisfaction variable for each tenantresource pair, rather than a single satisfaction ratio per tenant. We model dependencies through a family of dependency groups, where each group captures resources that are coupled for that tenant. Within each group, the effective allocation is determined by the congested bottleneck resource (i.e., the resource with the highest demand-to-capacity ratio, referred to as the dominant share). DDRF then equalizes the dominant shares of these bottleneck resources across tenants’ dependency groups that share a common resource, while granting low-demand tenants their full demand, and redistributing any remaining surplus resource among the others according to MMF. This paper makes the following contributions: • We propose the Dependency-aware Dominant Resource Fairness (DDRF) algorithm, which introduces tenantspecific dependency groups to capture generic couplings across resources. DDRF identifies low-demand tenants, reallocates surplus resources when they are present, and equalizes dominant shares of active congested resources across dependency groups that share a common resource. • We introduce an effective satisfaction metric to capture the used allocation’s portion under dependencies. • We develop a practical DDRF solver that combines a convex heuristic with an evolutionary-optimization to handle convex and selected non-convex dependency cases. • We devise a dependency-aware utilitarian baseline for fairness assessment. • We evaluate DDRF on Amazon EC2 traces and a virtualized radio access network (vRAN) case study coordinating radio and computing resources across evolved Node Bs (eNBs). We consider demand profiles, dependency models, and congestion regimes, and benchmark against state-of-the-art baselines in terms of effective satisfaction, allocation waste and fairness. The remainder of this paper is organized as follows. Section II reviews the background and related work. Section III introduces our system model. Section IV presents our proposed DDRF framework. Section V reports the simulation settings and performance evaluation. Section VI provides experimental results, and Section VII concludes the paper. II. BACKGROUND AND RELATED WORK Resource allocation has been extensively studied across diverse contexts. In its general form, when N tenants submit demands for M resources, the system is represented by a N ×M demand matrix D ∈ R+ , where dij ∈ D denotes tenant i’s demand for resource j. The available capacities are given by a vector C ∈ RM + , where cj ∈ C represents the total available capacity of resource j. The ordered pair (D, C) defines a multi-resource allocation problem. The output of this problem N ×M is given by A ∈ R+ where aij ∈ A is the amount of PN resource j allocated to tenant i such that i=1 aij ≤ cj , ∀ j. The system is said toPbe congested if there exists at least one N resource j such that i=1 dij > cj . Under congestion, not all tenants can be fully satisfied, making well-defined notions of

BRAIK et al.: DEPENDENCY-AWARE DOMINANT RESOURCE FAIRNESS FOR MULTI-TENANT MULTI-RESOURCE SYSTEMS

fairness essential. It is worth mentioning that we consider the case where tenants cannot receive more than their demand, i.e., over-provisioning is not allowed in our system; 0 ≤ aij ≤ dij . Most of the papers in the literature consider the case of single-resource allocation (i.e., M = 1) or an oversimplified multiple-resource allocation schemes, in which strict linear proportionality between resources is assumed, resulting in allocations that preserve these fixed ratios. In other terms, under the linear-dependency scenario, the induced allocation is given by aij = xi × dij where xi ∈ [0, 1] denotes the fraction of tenant i’s demand that is satisfied uniformly across all resources; we refer to this xi as the user satisfaction. Several prominent fairness notions have exist for the singleresource setting, including Max-Min Fairness (MMF) [6], [25], [26], Proportional Fairness (PF) [4], [5], the more general αfairness that is also known as (p, α)-Proportional Fairness [7] which spans from utilitarian to PF and MMF, and some game-theoretic solutions such as Constrained Equal Awards, Constrained Equal Losses [27] and Mood Value [28]. A desirable property of any fairness rule is strategyproofness: tenants should not gain by misreporting their demand. Among the above, MMF is unique in being strategyproof, since tenants with demands greater than or equal to C/N cannot improve their allocation by cheating. Formally, a feasible single-resource allocation (a1 , . . . , aN ) is max-min fair if it is impossible to increase the allocation of any tenant i without either violating feasibility or decreasing the allocation of some tenant i′ with ai′ ≤ ai . This notion is closely related to Rawls’ difference principle [24], which seeks to maximize the welfare of the least advantaged. MMF ensures that the weakest tenants (i.e., in terms of demands) are made as well off as possible. MMF allocation can be derived through a water-filling procedure; first, sort demands in non-decreasing order, Dδ = (dδ(1) , . . . , dδ(N ) ), with dδ(1) ≤ · · · ≤ dδ(N ) , then the allocation  for tenant δ(i) is recursively computed as aδ(i) = min dδ(i) ,

C−

Pi−1

j=1 aδ(j) N −i+1

. Intuitively, MMF fol-

lows an egalitarian principle by making the allocated amount equitable, and each tenant receives at least C/N , unless her demand is smaller, in which case she is allocated her full demand and the surplus is redistributed equally among the remaining tenants. Directly applying single-resource allocation rules to multi-resource settings often leads to inefficiency and allocation waste [12], since tenants typically require multiple resources in combination rather than in isolation. This motivates the need for multi-resource allocation rules that extend single-resource fairness notions. Dominant Resource Fairness (DRF) [9] generalizes MMF to multiple resource types, and was originally proposed for cloud systems. Recent works extends DRF to indivisible allocations [29], multiple servers [30], and settings with elastic demands [31]. Other generalizations include axiomatic approaches based on Schur-concave functions [8], [10], extensions of proportional fairness [32], and frameworks unifying multiple notions through ordered weighted averages (OWA) [12] that have re-adapts several fairness notions to network slicing environments. Despite their differences, all these approaches share a com-

3

mon limitation: they assume either linear coupling of resources aij ) which or Leontief-type utility preferences (ui = minj dij treats resources as perfect complements where ui is the utility of user i to maximize. This assumption severely restricts applicability in modern systems, where more general forms of inter-resource dependency arise. Dominant Resource Fairness (DRF) [9] generalizes MMF to multi-resource settings under linear proportional dependency assumption while retaining its desirable axiomatic properties. DRF operates by normalizing each tenant’s i demand through the demand-to-capacity ratio sij = dij /cj for every resource j. For each tenant i, the maximum of these demand-to-capacity ratios, µi = maxj sij , is called tenant i’s dominant share, and the corresponding resource bi = arg maxj sij is the bottleneck resource. Allocations are then determined by equalizing dominant shares across tenants, thereby extending MMF’s fairness guarantees to multi-resource scenarios. Formally, DRF for multi-resource settings with linear dependency solves: max X

N X

xi

i=1 ⊤

(DRF)

s.t. D X ≤ C, µi xi = µj xj ,

∀ i ̸= j ∈ {1, · · · , N },

N

X ∈ [0, 1] . DRF maximizes each component in the vector X but from µi xi = µj xj = λ ⇐⇒ xi = µλi that is increasing in λ and no trade-off between the components we can say it maximizes the sum of all users’ satisfaction (Utilization) subject to capacity constraints, bounds on the satisfaction (non-negativity and no over-provisioning) and a fairness constraint on equalizing dominant shares across tenants. DRF is designed to satisfy four key properties: Share Incentive, guaranteeing that each tenant receives at least a 1/N fraction of her dominant resource if she demands more; Pareto Efficiency, ensuring no tenant can be made better off without harming another; Strategy Proofness, which prevents tenants from gaining by misreporting their demands; and Envy Freeness, meaning every tenant prefers her own allocation to that of others. In essence, DRF reduces the multi-resource allocation problem to a single-resource one by focusing on the dominant share, and then scales allocations proportionally across other resources. Under congestion scenarios, the DRF scheme exhibits two key shortcomings: • Existence of weak tenants. As DRF equalizes dominant shares, a weak tenant with small demand can limit other users to its dominant share, preventing full resource utilization and leaving capacity idle. Example.   Consider 2 tenants and 2 resources with D = 9 9 and C ⊤ = [20, 30], DRF produces the following 14 25 



9 9 allocation 7.56 , fully satisfying tenant 1 whereas 13.5 tenant 2 reaches only 54% satisfaction, even though the resources are not fully used. However, a more   efficient 9 9 allocation than DRF’s output is 11 that fully 19.6429 utilizes resource 2 and raises tenant 2 satisfaction to 78.57%, strictly improving efficiency and preserving fairness. This can be seen geometrically in Figure 2. The

4

IEEE TRANSACTIONS ON NETWORKING, VOL. XX, YYYY

1.2

TABLE I S UMMARY OF THE NOTATION USED IN THE PAPER

demand-unconstrained region demand-bound constraint DRF feasible region capacity constraint (resource 1) capacity constraint (resource 2) fairness equity constraint

satisfaction of user 2

1.0

DRF enhanced solution

0.8

DRF Demand allocation

0.4

0.2

0.2

0.4

0.6

0.8

1.0

satisfaction of user 1

1.2

1.4

1.6

System Model III + IV-A

0.6

0.00.0

Definition

Symbol

Fig. 2. DRF inefficiency in demand satisfaction under congestion: allocation capped by demand. Fairness line prevents capacity saturation due to lowdemand users; ignoring fairness yields efficient orange point.

{1, · · · , N } Set of users {1, · · · , M } Set of resources

D

(dij )1≤i≤N, 1≤j≤M , dij : User’s i demand for resource j

C

(cj )1≤j≤M , cj : The available capacity of resource j

X

(xij ), xij ∈ [0, 1]: User’s i satisfaction for resource j

Ki

∈ N ∪ {0}, Number of dependency functions of user i n o
(k) fi {xij } (k) = 0 (or ≤ 0) : k = 1, . . . , Ki , Set

Fi (k)

j∈S i

of dependency constraints coupling the resources of user i (k)

Si

⊆ M Subset of coupled resources for user i at constraint k by fi

A

(aij ), aij = dij xij The allocated amount of resource j to user i

λj

∈ R+ largest fully allocatable demand for resource j under MMF

yij

1[dij > λj ]: indicator that user i’s demand for resource j is active

Si

Family of maximal dependency groups induced by {Si

S

d (sij ) : sij = cij j

µi

maxj sij User i’ dominant share

bi C

∈ arg maxj∈M sij User i’s bottleneck resource P {j ∈ M : i dij > cj } The set of congested resources

µC i

maxj∈C sij User i’s dominant-share over congested resources

bC i ji′ X⋆

min arg maxj∈C sij User i’ Congested bottleneck resource

(k) Ki }k=1

User i’s share of resource j

min arg maxj∈C: yij =1 sij User i’ active congested bottleneck Optimal solution to DDRF or D-Util (k)

(k)

Ai (j ′ )

{ k ∈ {1, . . . , Ki } : j ′ ∈ Si and fi (X ⋆ ) = 0 } active dependency-constraint indices of user i containing j ′ at X ⋆

BC

{i ∈ N : bi ∈ C} Users with congested bottleneck resource

BN C

N \BC Bottleneck-noncongested users

W

{i ∈ N : ∀j ∈ Cyij = 0} Set of weak users

A

N \W Set of active users

CP E(X, F ) X effective

P i αi zi P i αi

with α, z ∈ RN The weighted mean P [0, 1] Congestion profile, CPj available proportion of i dij n o e ∈ [0, 1]N ×M 0 ≤ eij ≤ Xij , ∀i, j, e ∈ F Effective satisfaction region P P arg maxe∈E(X,F ) i∈N j∈M eij Effective satisfaction

M1 (α; z) M1 (α; z) = Simulation V

To evaluate the efficiency of a resource P allocation problem, the literature often defines efficiency as i Ui (X), where U is a strictly concave, increasing utility function that captures diminishing returns and fairness. A more general formulation is provided by the Ordered Weighted Averaging (OWA) operator, adopted in the Multi-Resource Allocation for Network Slicing (MURANES) framework [12]. It is defined as OWA(z) = P N i=1 wi zδ(i) , where δ orders the inputs in non-decreasing order and w is a strictly decreasing weight vector. With this choice, OWA is Schur-concave, equitable, and satisfies the Pigou-Dalton transfer principle [33]. By tuning the weights, OWA spans objectives from egalitarian w = (1, 0, . . . , 0) to fully utilitarian w = (1, 1, . . . , 1). Hence the relationship among fairness notions: MMF and PF are both egalitarian in spirit, MMF enforces equity at the allocation level, while PF enforces equity at the satisfaction level. In contrast, utilitarian

Theoretical Part IV-B

figure depicts the DRF feasible set with the demandbound constraint xi ≤ 1, ∀i ∈ N (demand-satisfaction allocation) and without it (task allocation). The grey and black points correspond to the DRF solutions without and with the constraint, respectively. The orange point indicates an alternative allocation that preserves DRF’s properties yet Pareto-dominates the black point, by increasing the second user’s allocation without reducing the first user’s allocation. • Dominant share on non-congested resources. Finally, DRF may enforce fairness on a non-congested resource rather than the true bottleneck. Example. Consider 2 tenants and 2 resources with D =   6 9 and C ⊤ = [10, 10]. In this case, resource 1 8 1 is congested, while resource 2 still has spare  capacity. 4 6 DRF outputs the following allocation 6 0.75 . Although this satisfies DRF’s fairness condition, it does so without distinguishing between congested and non-congested resources. Alternatively, equalizing the dominant shares of the congested  resource (resource 1 in this example) 5 7.5 gives 5 0.625 . This adjustment aligns fairness with the actual bottleneck of the system, emphasizing that dominant shares should be defined with respect to congested resources rather than globally across all resources.

N M

M

rules maximize total utility without fairness concerns. In this paper, we address the aforementioned limitations by revisiting multi-resource allocation, which allows us to extend max–min fairness (MMF) to dependency-aware multi-resource settings while preserving its desirable properties. III. S YSTEM MODEL AND PROBLEM FORMULATION We consider a network slicing problem where each tenant manages an isolated slice made up of virtualized resources that are provided by one or more infrastructure providers (InPs). Tenants may correspond to MVNOs (Mobile Virtualized Network Operator) who does not have their own network infrastructure, service providers, vertical industries, or end users with specific QoS requirements. InPs manage the underlying physical infrastructure and allocate resources across slices. Network slicing thus enables customized, isolated virtual networks while ensuring efficient infrastructure sharing and meeting service-level guarantees. For convenience, the main notation used in the paper is summarized in Table I.

BRAIK et al.: DEPENDENCY-AWARE DOMINANT RESOURCE FAIRNESS FOR MULTI-TENANT MULTI-RESOURCE SYSTEMS

5

Algorithm 1 Full Allocation Cutoff Computation Slice 1

Tenant 1

Slice 2 Slice 3

Tenant 2

𝒩 Tenant 3

= 1, 2, 3, 4

Slice 4

Tenant 4 ℳ = {1, 2, 3, 4}

Resource 1

Resource 2

Resource 3 & 4

Infrastructure Provider 1

Infrastructure Provider 2

Infrastructure Provider 3

ℛ = { 1 , 2 , {3, 4}}

𝒫 = {1, 2, 3}

Fig. 3. A system model example with 4 tenants, 3 InPs, 4 resources.

Our system model is shown in Figure 3. Let N = {1, . . . , N }, M = {1, . . . , M }, and P = {1, . . . , P } be tenants, resources, and infrastructure providers (InPs). The tuple (D, C, F) defines the dependency-aware multiN ×M resource allocation problem, with demand matrix D ∈ R+ , where dij denotes tenant i’s demand for resource j. The available capacities are given by a vector C ∈ RM + , where cj is the total capacity of resource j. We adopt Per-Resource Satisfaction2 , with X ∈ RN ×M , where each xij ∈ [0, 1] denotes the fraction of demand dij satisfied for tenant i on resource j. This more general formulation captures arbitrary, potentially non-linear couplings between resources. It enables us to define satisfaction per resource, which is essential for modeling dependencies beyond simple proportionality and is the foundation of our approach. Each tenant i specifies a collection of Ki functional constraints: n o
(k) Fi ≜ fi {xij }j∈S (k) = 0 (or ≤ 0) : k = 1, . . . , Ki , i

where each constraint captures a dependency among a subset (k) of resources Si ⊆ M. An allocation is valid for tenant i only SN if all constraints in Fi are satisfied. Let F = i=1 Fi denote the global set of all dependency constraints. We assume that the fully satisfied demands is a feasible candidate solution (i.e.,
(k) xij = 1 for all j) is feasible for all i, k, so fi {1}j∈S (k) = i 0 (or ≤ 0) ∀ i, k, where 1 is the vector of ones, this model assumption ensures that demands are consistent with the underlying dependencies between resources. Example. Consider tenant i with demand vector (2, 4, 3, 6) across four resources, subject to the following dependencies: (1) fi (xi1 , xi2 ) = (2xi1 )2 − 4xi2 = 0 (quadratic), (2) fi (xi1 , xi3 , xi4 ) = 2xi1 · 3xi3 − 6xi4 = 0 (multiplicative). These constraints capture nonlinear couplings among resources that cannot be represented by fixed linear ratios. We (1) (2) note that fi (1, 1) = 0 and fi (1, 1, 1) = 0 meaning that tenants are rational, so their declared demands are consistent with the specified dependencies; hence, the fully satisfied demand vector is always feasible. Importantly, monotonicity is not required: our model admits both increasing and decreasing relationships. The latter capture trade-offs where allocating 2 Unless otherwise noted, all subsequent definitions adopt this formulation.

N ×M Input: Demand D ∈ R+ , Capacity C ∈ RM + Output: Threshold vector λ ∈ RM 1: for j = 1 to M do 2: dj ← [d1j , . . . , dN j ] ▷ demands on resource j 3: Sort dj : d(0)j ← 0 ≤ d(1)j ≤ · · · ≤ d(N )j 4: S ← 0; found ← false ▷ prefix sum; termination 5: for k = 0 to N − 1 do cj − S 6: λ̃ ← N −k 7: if d(k)j ≤ λ̃ ≤ d(k+1)j then 8: λj ← λ̃; found ← true; break 9: end if 10: S ← S + d(k+1)j 11: end for 12: if found = false then 13: λj ← d(N )j ▷ all demands can be fully satisfied 14: end if 15: end for 16: return λ = [λ1 , . . . , λM ]

more of one resource reduces the need for another, while our optimization framework ensures efficiency by maximizing overall satisfaction across all resources. The output of this ×M problem is given by A ∈ RN where aij = xij · dij , ∀i ∈ + N, j ∈ M is the amount of resource j allocated to tenant i PN such that i=1 aij ≤ cj , ∀ j ∈ M. We consider a centralized setting in which a central entity receives (D, C, F) and computes the allocation. For simplicity, we adopt the standard assumption that resources are divisible3 . Our approach aims at maximizing system efficiency interpreted as the linear sum of user utilities. In our network slicing model, utility is derived directly from user satisfaction on the P allocated resources. The utility of user i is defined as Ui = j∈M xij , with 0 ≤ Ui ≤ M for all i ∈ N . The total system efficiency, P P P or user-centric efficiency, is given by U = i∈N i i∈N j∈M xij . To address one of the main limitations of the DRF solution, namely the presence of weak tenants that lead to inefficiencies, we first formalize the notion of weak tenants. To do so, we compute a threshold λj for each resource j ∈ M. Intuitively, λj represents the largest per-resource demand that can be fully satisfied under the Max-Min Fairness (MMF) principle. Formally, for each resource j with demand vector [d1j , . . . , dN j ] and capacity cj , the threshold λj is defined such that all tenants with dij ≤ λj receive their full demand. Definition 1 (Weak Tenants). A tenant i is classified as weak if dij ≤ λj for all j ∈ M. Weak tenants are automatically satisfied, while only the remaining active tenants participate in the fairness constraint. The thresholds λj are computed using Algorithm 1, which follows the MMF water-filling procedure with time complexity O(M N log N ). 3 We assume each resource is exclusively managed by a single provider to avoid inter-provider contention. Modeling shared-resource scenarios is out of the scope of this paper.

6

IEEE TRANSACTIONS ON NETWORKING, VOL. XX, YYYY

IV. D EPENDENCY- AWARE D OMINANT R ESOURCE FAIRNESS (DDRF) Motivated by the aforementioned objectives: (i) resolving DRF’s inefficiency and (ii) accommodating generic interresource dependencies, we propose a resource-allocation framework for congested systems with arbitrary inter-resource dependencies that overcomes the key limitations of DRF. A. Modeling Coupled Resources via Dependency Groups As a first step, we introduce the concept of dependency groups, an abstraction used purely for algorithmic purposes. Although in practical systems such as cloud and network slicing it is unrealistic for group of resources to be coupled independently of other groups, this abstraction enables a unified and tractable formulation of our algorithm. Definition 2 (User Dependency Family). Given a user i, (k) her dependency constraints Fi and Si the set of coupled resources of each constraint k. The Dependency Family Si is (k) formed by merging all overlapping Si over constraints k, each resulting set is a dependency group. Disjoint interdependent sets form separate groups, and unconstrained resources appear as singletons. These families, derived from F, enable DDRF to enforce fairness within each coupled set of resources, even when coupling is only partial across M . Example. Suppose tenant i requests 7 resources with the following dependency constraints: 2(di2 xi2 ) + 5 − di4 xi4 = 0, 8(di1 xi1 )3 − di6 xi6 = 0, 2 3(di1 xi1 ) + (di5 xi5 )(di3 xi3 ) = 20. Then, Si = {{2, 4}, {1, 3, 5, 6}, {7}}. Special cases. Linear dependency: if xij = xik for all j, k ∈ M, then Si = {M} i.e., all resources are coupled in a single dependency group. No dependency: if all resources are independent, then Si = {{j} : j ∈ M}. The DDRF allocation problem can be formulated as the following optimization program: M N X X xij max i=1 j=1

s.t.

N X

dij xij ≤ cj , ∀j ∈ M,

(1)

i=1

X ∈ F,

(2)

∀ i ̸= k ∈ N , j ∈ M : ∆ikj = max µ̂ij , µ̂kj

(3)

(DDRF)

1 − ŷij ŷkj ,

µ̂ij x̂ij − µ̂kj x̂kj ≤ ∆ikj , µ̂ij x̂ij − µ̂kj x̂kj ≥ −∆ikj , x̂ij ≥ 1 − ŷij ,

∀i ∈ N, j ∈ M

0 ≤ xij ≤ 1, ∀i ∈ N , j ∈ M.

(4) (5)

Here (x̂, µ̂, ŷ) denote the satisfaction, dominant-share, and activity values inherited from each dependency group’s active dominant resource (see Algorithm 2). The optimization P P program (DDRF) maximizes tenants’ satisfaction i∈N j∈M xij subject to five classes of constraints. (1) the capacity constraints ensure that the allocated

Algorithm 2 Fairness Parameters of DDRF ×M Input: Demand D ∈ RN , Capacity C ∈ RM + , Depen+ dency F Output: Fairness parameters (x̂, µ̂, ŷ) 1: Compute normalized shares sij ← dij /cj 2: Compute thresholds λj for each resource j (Alg. 1) 3: Activity matrix yij ← 1[dij > λj ] 4: For each tenant i, obtain dependency family Si 5: for i = 1 to N do 6: for all S ∈ Si do 7: J ← {j ∈ S : yij = 1} ▷ active indices in S 8: if J = ∅ then 9: J ←S ▷ any index in S can be chosen 10: end if 11: j ⋆ ← min arg maxj∈J sij 12: for all j ∈ S do 13: ŷij ← yij ⋆ ▷ inherit activity from j ⋆ 14: µ̂ij ← sij ⋆ ▷ inherit dominant share 15: x̂ij ← xij ⋆ ▷ link satisfactions 16: end for 17: end for 18: end for 19: return x̂, µ̂, ŷ

amount of each resource does not exceed its available capacity. (2) the dependency constraints X ∈ F enforce tenant-specific couplings across resources, so allocations remain consistent with the declared inter-resource relations. (3) the fairness constraints implement the DDRF generalization of DRF. For each tenant, Algorithm 2 maps dependency group to its active dominant (bottleneck) resource and represents the group satisfaction accordingly. DDRF then enforces fairness equity µ̂ij x̂ij = µ̂kj x̂kj when the corresponding groups are active (i.e., both tenants have at least one active resource in the group); when a group has no active resource, the constraint is relaxed and (4) full satisfaction is activated within that group. (5) the bounds 0 ≤ xij ≤ 1, ensure non-negative satisfaction and prevent over-provisioning beyond demand. Algorithm 2 constructs the fairness parameters by defining the activity matrix yij = 1[dij > λj ], where yij = 1 indicates that tenant i is active on resource j (its demand exceeds the MMF cutoff λj ), and yij = 0 otherwise. Together with the normalized demand shares sij = dij /cj , this allows DDRF to select, within each dependency group S ∈ Si , a representative resource index j ⋆ that drives the group’s fairness treatment. Specifically, if the group contains at least one active resource, j ⋆ is chosen as the active resource with the largest sij ; ties are broken by taking the smallest index. If no resource in the group is active, then the group is deemed inactive (and the tenant is weak on that group), so ŷij = 0 for all j ∈ S and no fairness equalization is enforced for that group; moreover, its full satisfaction is guaranteed. The representative index j ⋆ induces the inherited quantities used in (DDRF): for all j ∈ S, we set ŷij = yij ⋆ , µ̂ij = sij ⋆ , and x̂ij = xij ⋆ , so that the group is effectively governed by a single satisfaction variable. B. DDRF Properties We now analyze the properties and features of DDRF.

BRAIK et al.: DEPENDENCY-AWARE DOMINANT RESOURCE FAIRNESS FOR MULTI-TENANT MULTI-RESOURCE SYSTEMS

1) Pareto Efficiency: A key requirement for any resource allocation algorithm is Pareto efficiency: no user can be made better off without making another worse off. In multi-resource settings under congestion, a necessary and sufficient condition for Pareto efficiency is saturation i.e. to fully allocate as much as possible of the congested resources (otherwise, some tenant’s satisfaction can be increased without harming others). We assume F satisfies two mild properties: local regularity and the existence of an improving feasible direction. We first present the main theorem and a supporting lemma, then state the intuition behind these assumptions. Theorem 1 (Pareto-Efficiency of DDRF). Under standard regularity assumptions on F, every optimal solution of (DDRF) for (D, C, F) saturates at least one congested resource. Hence DDRF is Pareto efficient over its feasible set. Definition 3 (Dependency-Aware Utilitarian Framework). By dropping the fairness constraint in (DDRF), we obtain the following dependency-aware utility maximization problem: max

N X M X

xij

i=1 j=1

s.t.

N X

dij xij ≤ cj , ∀j ∈ M,

(D-Util)

i=1

X ∈ F, 0 ≤ xij ≤ 1,

∀i ∈ N , j ∈ M.

Lemma 1 (Pareto-Efficiency of D-Util). Under the same assumptions on F as in Theorem 1, every optimal solution of D-Util saturates at least one congested resource, and is Pareto efficient. Local regularity and local improving feasible direction. We require that certain functions in F satisfy two mild assumptions. The first is local regularity, meaning that the function and its first-order derivatives are continuous in a neighborhood of the optimal solution X ⋆ of (DDRF) or (D-Util); this allows the corresponding partial derivatives to be well defined and used in the analysis. The second is a local improving feasible direction condition, which ensures that, under the dependency constraints, an increase in one coordinate can be accompanied by compensating variations in the coupled coordinates so that the overall feasible variation remains locally improving. The precise identification of the functions in F to which these assumptions apply, together with the exact formal statements, is given in Appendix A. The detailed proofs of Lemma 1 and Theorem 1 are deferred to appendix B and C. Intuitively, if congested resources were left unsaturated, then under the assumptions on F one could construct a small feasible perturbation, consistent P with the dependency constraints, that strictly increases i,j xij while preserving feasibility, contradicting optimality. Hence, both the dependency-aware utilitarian problem and DDRF admit only optimal solutions that saturate at least one congested resource. 2) Sufficient Full Utilization: When low-demand (weak) tenants are present, classical DRF may leave congested resources unsaturated. Under linear dependencies, where each

7

tenant receives the same satisfaction level across all resources (i.e., xij = xi for all j), and with C the set of congested resources as in table I, DDRF reduces to the following scalar formulation (X ∈ RN ): X max xi s.t.

i∈N ⊤

D X ≤ C, µCi xi − µCk xk ≤ max(µCi , µCk )(1 − yibCi ykbCk ), ∀i ̸= k µCi xi − µCk xk ≥ − max(µCi , µCk )(1 − yibCi yktbCk ), ∀i ̸= k xi ≥ 1 − yibCi , 0 ≤ xi ≤ 1,

∀i ∈ N ∀i ∈ N ,

where µCi the share of the congested bottleneck and bCi the congested bottleneck resource are defined in table I. Only tenants with yibCi = 1 (active on their congested bottleneck) are equalized; weak tenants are fully satisfied. 3) Congestion-Aware Bottleneck Selection: In DDRF, fairness is enforced only along limiting (congested) resources. This anchors each dependency group to its most limiting active resource and avoids driving fairness decisions by non-limiting coordinates, which can improve efficiency compared to DRF. We introduce two classes of users based on their bottleneck resource The first one is users whose bottleneck resource is congested BC and the second is the bottleneck-noncongested users BN C defined in table I. Under linear dependencies and C ̸= ∅, the following scenarios occur: Case (BN C = ∅)

(BN C ̸= ∅)

Active ∀ i ∈ BC : yibi = 1 ∀ i ∈ BN C and i ∈ BC : ∃ j ∈ C : yij = 1 M1 (αC ; d·j ⋆ ) (i) cj ⋆ M1 (α; d·j ′ ) ≤ cj ′ M1 (αC ; d·j ⋆ ) (ii) cj ⋆ M1 (α; d·j ′ ) > cj ′

Weak ∃ i ∈ BC : yibi = 0 ∃ i ∈ BN C, or i ∈ BC : ∀ j ∈ C : yij = 0 c̃j̃ ⋆ (i) |W| + C M1 (αA ; dA,·j̃ ⋆ ) cj ′ ≥ M1 (α; d·j ′ ) c̃j̃ ⋆ (ii) |W| + C M1 (αA ; dA,·j̃ ⋆ ) cj ′ < M1 (α; d·j ′ )

Where W the set of weak users, A the set of active users, µi the dominant share, µCi the congested dominant share and M1 (β; z) is the weighted mean. They are defined in table I. Set M0 = M ∪ {0} and di0 = 1 for all i ∈ N , and define dA,·j = (dij )i∈A for each j ∈ M0 . Associate the weights C αi = 1/µi , αiC =
P 1/µCi , and αA = (αiC )i∈A . Next,
P define C C C c0 = mini∈N µi i∈N αi , c0 = mini∈N µi i∈N αi , C and cj = cj for all j ∈ M. In thePweak case, define the residual capacities c̃j =
Pcj − C i∈W dij for all j ∈ M, and c̃0 = mini∈A µCi i∈A αi . Finally, define M (α;d ) M1 (αC ;d·j ) , j ′ ∈ arg minj∈M0 1 cj ·j , cC j M (αC ;d ) and j̃ ⋆ ∈ arg minj∈M0 1 Ac̃j A,·j .

j ⋆ ∈ arg minj∈M0

Theorem 2. Under linear dependencies, let xDDRF and xDRF denote the solutions and DRF, respectively. Then P P of DDRF DDRF DRF x ≥ x in all scenarios except in the i∈N i i∈N i two cases labeled (ii) under BN C = ̸ ∅ (Weak and Active).

8

IEEE TRANSACTIONS ON NETWORKING, VOL. XX, YYYY

Consider 2 users and 2 resources, with D =  Example.  4 8 ⊤ and C = [10, 10], resource 1 is congested while 7 1 resource 2 is not. In this instance, µ = (0.8, 0.7) and µC = (0.4, 0.7), hence α = (1.25, 1.4286) and αC = (2.5, 1.4286). With M0 = 0, 1, 2, the minimizers are j ⋆ = 1 and j ′ = 1, C ·1 ) and we obtain M1 (αc1 ;d·1 ) ≈ 0.6585 < M1 (α;d c1 P ≈ 0.7222. > Thus condition (active, BN C = ̸ ∅) (i) holds, so i xDDRF i P DRF x (DDRF is more efficient here). The weighted coni i gested pressure at DDRF’s bottleneck resource (with weights 1 ) is not larger than the pressure of DRF (with weights µ1i ). µC i The proof of Theorem 2 is deferred to appendix D.

TABLE II C OMPARISON OF ALLOCATION OUTCOMES UNDER DIFFERENT FAIRNESS RULES . WASTE IS MEASURED AS THE TOTAL DEPENDENCY- VIOLATION NORMALIZED BY TOTAL SYSTEM CAPACITY. I DLE IS THE UNALLOCATED CAPACITY NORMALIZED BY TOTAL SYSTEM CAPACITY

Resulting Allocation

Algorithm

DRF

15.55

0.53

313.43

  22.24

1.10

224.14

30.00

1.10

151.20

38.00

1.20

424.40

  38.00

1.20

424.40

30.00

 MMF

C. Numerical Example

60 with D =45 30

2.054 2.22 1.097

1209.6 453.6  where the columns correspond 151.2

to the resources and the rows to the tenants. The available   resources are given by C ⊤ = 106 3.5 1000 . To obtain DDRF solution we compute the active de1

1 1 1 1 and the share matrix s = 0 0 0 1.2096 0.4536. Clearly, user 1 has bottleneck on 0.1512

mands matrix y = 1 

0.566 0.4245 0.283

0.5869 0.6343 0.3134

resource 3 with µ1 = 1.2096, user 2 has bottleneck on resource 2 with µ2 = 0.6343 and user 3 is labelled as weak. DDRF allocation is obtained by solving the following program: max X

3 X 3 X

xij

(Objective)

PF

Idle (%)

33.12%

31.58%

30.91%

0%

43.21%

2.90%

Utilitarian

38.21%

1.71%

151.20 666.67

  24.80

1.22

250.00

16.53

0.60

83.33

27.18

0.93

547.91

  29.85

1.47

300.89

30.00

0%

33.92%

0%

2.83%

     

1.10

151.20

18.08

1.13

364.53

  14.98

1.28

151.02

30.00

1.10

151.20

39.62

1.67

798.74

   4.97

0.73

50.06 

30.00

1.10

151.20

 D-Util

 

1.13

 DDRF



1.10

 dependency-agnostic

 

33.07



We consider 3 tenants with 3 resources that are the number of physical resource blocks NPRB , the CPU clock frequency f and the fronthaul bandwidth B FH . Demands are as follows: slice 1: (60, 2.1, 1209.6), slice 2: (45, 2.22, 453.6) and slice 3: (30, 1.25, 151.2) FH where each tuple corresponds to (NPRB , f[GHz] , B[Mbps] ). The aggregate demand is (135, 5.371, 1814.4) exceeds the available capacities (106, 3.5, 1000), so all resources are congested. We have a linear proportional dependency beFH tween NPRB and B[Mbps] (xi1 = xi3 ) for each user i ∈ {1, 2, 3} and a quadratic dependency between NPRB and f[GHz] (αi xi1 ≤ x2i2 , α = (0.9992, 0.9921, 0.9733)) for each user as well. This choice is inspired from realistic dependencies reported in O-RAN literature [17], [18]. The dependencyaware multi  resource allocation  problem becomes (D, C, F)

Waste (%)

FH-7.2x ) (NPRB , f[GHz] , B[Mbps]  

     

Where ⊙ is the Hadamard element-wise product, the program is nonconvex because the constraints in (Latency Dependency) are the hypograph of a convex function. To handle the resulting DC (difference-of-convex) constraint, we apply the Convex–Concave Procedure (CCP) [34]. CCP linearizes the term x2i2 around a tangent point ai using its first-order Taylor expansion, namely x2i2 ≥ a2i + 2ai (xi2 − ai ) = 2ai xi2 −a2i . Replacing x2i2 by this affine under-estimator yields the convex surrogate constraint αi xi1 −(2ai xi2 −a2i ) ≤ 0. This step is conservative: because 2ai xi2 − a2i ≤ x2i2 for all xi2 , any point satisfying αi xi1 ≤ 2ai xi2 − a2i also satisfies the original constraint αi xi1 ≤ x2i2 , hence feasibility is preserved (0) at every iteration. Starting from an initial feasible point ai , CCP solves the resulting convex program at iteration k and (k+1) (k) updates the linearization point as ai ← xi2 , repeating until convergence to a stationary (locally optimal) solution.

i=1 j=1

subject to " 60 45 30

2.1 2.22 1.25

1209.6 453.6 151.2

0 ≤ xij ≤ 1,

D. Allocation and Waste Comparison Against DependencyAgnostic Baselines

!⊤ " #

# ⊙X

1 1 1

i, j ∈ {1, 2, 3}

" ≤

#

106 3.5 1000

(Capacity) (Bounds)

1.2096 x13 = 0.6343 x22

(Fairness)

xi3 = xi1 , i ∈ {1, 2, 3}

(Fonthaul Dependency)

0.9992 x11 − x212 ≤ 0

(Latency Dependency)

0.9921 x21 − x222 ≤ 0 0.9733 x31 − x232 ≤ 0

(Latency Dependency) (Latency Dependency)

We report allocation results (approximated to two decimal digits) together with the percentage of waste and idle resource for the numerical example in Section IV-C under several baselines that either ignore inter-resource dependencies or enforce a linear dependency model: (i) DRF, (ii) per-resource MMF (applied independently on each resource), (iii) a generalized PF baseline derived from the MURANES framework [12] with a scalar satisfaction variable xi and weights (1, 0, . . . , 0), and (iv) a dependency-agnostic utilitarian baseline enforcing a linear proportional dependency across all resources with

BRAIK et al.: DEPENDENCY-AWARE DOMINANT RESOURCE FAIRNESS FOR MULTI-TENANT MULTI-RESOURCE SYSTEMS

dependency-aware DDRF and dependency-aware utilitarian DUtil. As shown in Table II, all baselines incur allocation waste under the nonlinear processing dependency, whereas DDRF and D-Util achieves zero waste. In particular, DDRF satisfies the dependency constraints and fully utilizes at least one congested resource (here, the computing budget). By contrast, DRF saturates none of the resources and can violate the processing-time constraint, yielding PRB allocations that are not effectively processable. V. S IMULATION AND EVALUATION APPROACH To assess the performance of DDRF, we design an interslice scenario. This involves selecting an appropriate demand set, identifying the resources to be allocated across slices, defining representative congestion scenarios, and specifying how resource coupling constraints are enforced. A. Tenants demands generation Demands were derived from Amazon EC2 instance traces [35], which capture heterogeneous workloads across diverse applications and thus reflect realistic cloud infrastructure patterns relevant to 5G slicing. This diversity makes them a strong benchmark for evaluating allocation mechanisms under varying demand conditions. We selected 23 demand profiles from different instance families (e.g., general purpose, compute-optimized, memory-optimized), each representing a slice, among these slices, 3 slices were chosen to be weak (i.e., their demands are low as defined in III). Each demand spans four resources: memory (GiB), vCPU, network bandwidth (Gbps), and radio blocks (RBs). The first three are provided directly by the EC2 dataset, while RB demands were synthetically generated. For regular users, RB demands were drawn uniformly from U[15, 25], and for weak users from U[1, 4]. All demands were normalized to match the predefined resource capacities: [17128, 1364, 566.25, 273] for (memory, vCPU, bandwidth, RBs), respectively. he choice of 273 RBs corresponds to a 100 MHz NR carrier at 30 kHz SCS, which allows scheduling up to 273 RBs in the frequency domain per slot [36]. In our setting, resources are allocated at the slice level as static, long-term guarantees rather than dynamic per-slot scheduling. B. Congestion profiles To evaluate the performance of DDRF, we consider varying congestion profiles, defined as tuples in [0, 1]4 where each coordinate specifies the fraction of the corresponding resource capacity available. Formally, with demand matrix D (columns corresponds to memory, vCPU, bandwidth and RBs respectively) and a congestion profile PN CP, the available capacity of resource j will be: cj = ( i=1 dij ) · CPj . For example, the congestion profile (0.3, 0.9, 0.9, 0.9) means that only 30% of the total memory demands are available, while 90% of the demands for vCPU, bandwidth, and RBs remain respectively. We impose 14 congestion profiles to capture both symmetric (e.g., [0.3, 0.3, 0.3, 0.3], [0.9, 0.9, 0.9, 0.9]) and asymmetric resource limitations (e.g. [0.3, 0.8, 0.8, 0.8], [0.8, 0.3, 0.3, 0.8]). This design enables stress-testing under both balanced congestion scenarios and highly asymmetric conditions where a single resource becomes the bottleneck.

9

C. Dependency scenarios We introduce three types of coupling between resources for each user. In the linear proportional case, all resources must be allocated in the same ratio, i.e., xij = xik , ∀i ∈ N , j ̸= k ∈ M. In the affine linear case, dependencies are expressed as constraints of the form aAmem +bAcpu +cAbandwidth +dArb + e = 0, where Ar denotes the allocated amount of resource r. In the polynomial quadratic case, constraints take the form β γ η aAα mem + bAcpu + cAbandwidth + dArb + e = 0, with exponents {α, β, γ, η} ∈ {0, 1, 2} and at least one exponent equal to 2, thus capturing quadratic couplings. Based on these definitions, we design three experiments: (i) all couplings follow the linear proportional model, (ii) all couplings follow the affine linear model, and (iii) all couplings follow polynomial quadratic model with γ = 2 and α = β = η = 1. In all experiments, we consider that each user’s dependency family is Si = {M}, ∀ i ∈ N , thus, all resources belong to a single dependency set and are mutually dependent. The coefficients (a, b, c, d, e) are derived to align with the demand matrix such that allocating the full demand (k) of each user (i.e., fi ({1}j∈S (k) ) = 0 (or ≤ 0)) satisfies i the coupling constraints. This construction is consistent with our assumption on F. All optimization problems were solved using the CVXPY [37] library with the DCCP extension [38]. D. Baselines We benchmark DDRF against the following baselines: DRF obtained from [12], with resource aggregation si xi , X ∈ RN and w = (1, 0, · · · , 0); PF obtained from [12], which generalizes weighted proportional fairness (PF) to multi-resource settings, where resource aggregation is xi , X ∈ RN and w = (1, 0, · · · , 0); Mood [12], which allocates resources under complete information sharing, here resource aggregation is P Si xi , X ∈ RN and P Si is the player satisfaction of user i defined in [28] computed on his bottleneck resource with w = (1, 0, · · · , 0); MMF, applied independently on each resource; and the dependency-aware utilitarian solution defined in (D-Util). E. Effective Satisfaction Formulation We formalize the notion of effective satisfaction, which quantifies the portion of an allocation that remains usable once tenant dependencies are enforced. This captures the distinction between raw allocations and the subset that yields meaningful utility under inter-resource couplings. Definition 4 (Effective Satisfaction Region). Given a satisfaction matrix x ∈ [0, 1]N ×M and global dependency constraints F, the effective satisfaction region is:  E(X, F) = e ∈ [0, 1]N ×M 0 ≤ eij ≤ Xij , ∀i, j, e ∈ F This set consists of all feasible satisfaction matrices e that (i) do not exceed the raw allocation x, and (ii) respect every tenant’s declared dependencies. Definition 5 (Effective Satisfaction). The effective satisfaction matrix is defined as: X X X effective = arg max eij . e∈E(X,F )

i∈N j∈M

10

IEEE TRANSACTIONS ON NETWORKING, VOL. XX, YYYY

Only the dependency-respecting portion of the allocation contributes to utility, ensuring that efficiency is measured in terms of usable satisfaction. Example. (Linear Dependency) Suppose each tenant has a linear dependency across two resources:  x11 = x12 , x21 = 0.5 x22 . For an allocation X = 0.3 , effective satisfaction 0.2 0.7 enforces equality across each tenant’s resources, yielding   0.3 0.3 X effective = 0.2 . 0.2 Example. (Nonlinear Dependency) Consider quadratic cou  0.5 0.5 plings: (a11 )2 = a12 and (a22 )2 = a21 . Given X = 0.6 , 0.6 projecting onto thefeasible region defined by these constraints  0.5 0.25 yields X effective = 0.36 . 0.6 F. Performance metrics We assess allocations using three complementary metrics: 1) Capacity partitioning: In multi-resource environments with dependencies, not all allocated resources contribute to utility. We therefore partition system capacity into: • Used capacity: the effectively utilized portion, P P effective dij . i∈N j∈M Xij • Wasted capacity: resources allocated but unusable due to P P effective violated dependencies, i∈N j∈M (Xij −Xij )dij . • Idle capacity: resources not allocated and remain with
P P InP, j∈M cj − i∈N Xij dij . Only the used capacity reflects realizable tenant satisfaction, while wasted and idle capture different forms of inefficiency. we report the fraction of capacity that is used, wasted (violating dependencies), or idle to draw conclusions on the fraction of allocated capacity that was usable by each baseline and how fairness affects efficiency. 2) Cumulative density function (CDF) of the effective satisfaction: We plot the distribution of realized satisfactions across users, reflecting how heterogeneous demands are met. the smoother and gradually increasing the curve the balanced the allocation was without any jumps (some users given low satisfaction while others are high). 3) Fairness: Fairness is evaluated using Jain’s index [39], a standard metric in single-resource settings. For any vector z = (z1 , . . . , zN ) (either allocations or satisfactions {aij }N , i=1 PN 2 ( P i=1 zi ) N {xij }i=1 ∀j ∈ M), it is defined as J(z) = N N z2 . i=1 i We compute J per resource on the allocation and report the average across all resources between DDRF and dependencyaware utilitarian baseline. VI. N UMERICAL R ESULTS We report numerical results for each evaluation metric, detailing the methodology, obtained figures, and interpretation4 . A. Dependency-Aware vs. Dependency-Agnostic 1) Resource Partitioning: Figure 4 reports the average partitioning of total capacity across congestion profiles. Each bar is divided into three components: wasted (hatched, with the percentage labeled), used (solid, outlined together with waste), and idle (light shade). For each congestion profile, we 4 DDRF and simulations’ implementation are available on: https://gitlab.roc. cnam.fr/braikz/dependency-aware-drf.git.

run all algorithms to obtain the satisfaction matrix, derive the corresponding effective matrix, and then compute the shares of wasted, used, and idle capacity. Results are averaged across profiles to smooth out demand-specific variations. Several trends emerge. First, as expected, both DDRF and the Utilitarian approach achieve zero waste across all settings (decreasing allocation waste by roughly 60%), since both explicitly enforce resource dependencies. In contrast, all dependency-agnostic baselines (DRF, PF, Mood, and MMF) incur non-trivial waste because they ignore coupling. MMF in particular always saturates resources but yields the highest waste, as it allocates without regard to dependencies. Second, DDRF consistently improves efficiency compared to DRF: the presence of weak users leads DRF to stall before saturating resources, resulting in idle capacity, whereas DDRF reallocates surplus to other tenants once weak users are fully satisfied (effective Satisfaction rate enhanced from 6.2% to 60% in the polynomial quadratic case). Interestingly, PF and Mood align to identical behavior in these cases, confirming their sensitivity to weak tenants. Third, the Utilitarian approach achieves the highest overall efficiency, often allocating nearly all available capacity whenever dependencies permit; however, this comes at the cost of fairness: many tenants are fully satisfied while others are left starved. DDRF, by contrast, balances efficiency and fairness, avoiding starvation while still adapting to the coupling structure. Finally, PF and Mood perform comparatively better under homogeneous congestion (where the same congestion level is applied to all resources), even outperforming all other baselines in the linear proportional case (confirming why they have achieved larger average effective satisfaction rate than utilitarian in the linear proportional dependency case, and why they have larger confidence interval). 2) Effective Satisfaction Distribution: Figure 5 presents the cumulative distribution function (CDF) of effective satisfaction rates aggregated over all congestion profiles, showing the proportion of user-resource allocations that achieve less than or equal to a given satisfaction level. Complementarily, Figure 6 reports the CDF of each user’s minimum effective satisfaction across resources, aggregated over all profiles, thereby capturing the worst-case satisfaction experienced by each tenant. Three key insights. First, DDRF consistently achieves at least the level of satisfaction guaranteed by MMF: in the linear proportional case DDRF and MMF nearly coincide, while in scenarios with generic dependencies DDRF strictly outperforms MMF while enforcing zero waste. Importantly, both DDRF and MMF yield smooth, gradual CDF curves (in overall satisfaction and per-user minimum satisfaction), reflecting balanced satisfaction across users, having this close performance confirms that DDRF is as good as MMF effective satisfaction. Second, the behavior of the other baselines diverges significantly; the Utilitarian approach produces a steep jump in its CDF: many tenants are fully satisfied, but a large fraction receive zero satisfaction, Figure 6 emphasize this aspect. PF and Mood collapse to identical performance, characterized by vertical growth in their CDFs due to strict satisfaction equalization. Finally, DRF is clustered with PF and Mood in the top-left region of the CDF plots, confirming that most users receive low satisfaction when dependencies

11

1.2 1.0 0.8 64.2%

0.6

56.1%

54.2% 40.1%

0.4

26.9%

0.2

25.1%

41.2%

18.3%

PF waste PF used PF idle

ria

n

od

Uti

Polynomial Quadratic Mood waste Mood used Mood idle

lita

Mo

PF

F

F

0.0%

MM

RF

lita

DD

ria

n

od

F

PF

F

Affine Linear MMF waste MMF used MMF idle

0.0%

Uti

Linear Proportional

Mo

DD

MM

RF

lita

DR

ria

n

od

DRF waste DRF used DRF idle

Uti DDRF waste DDRF used DDRF idle

0.0%

DR

0.0%

0.0%

0.0%

Mo

MM

F

0.0%

PF

0.0%

F

0.0%

RF

0.0

DR

10.2%

DD

Average resource partitioning (waste / used / idle)

BRAIK et al.: DEPENDENCY-AWARE DOMINANT RESOURCE FAIRNESS FOR MULTI-TENANT MULTI-RESOURCE SYSTEMS

Utilitarian waste Utilitarian used Utilitarian idle

Fig. 4. Average partitioning of total resource capacity into wasted, useful, and idle components under different dependency structures across congestion profiles.

Linear Proportional

Affine Linear

1.0

0.8

0.6

0.6

0.6

0.2

CDF

0.8

0.4

0.4 0.2

0.0 0.0

0.2

0.4

0.6

Effective Satisfaction

0.8

Polynomial Quadratic

1.0

0.8 CDF

CDF

1.0

0.4 0.2

1.0

0.0 0.0

DDRF

DRF

0.2

0.4

0.6

0.8

PF

Mood

Effective Satisfaction MMF

0.0 0.0

1.0

0.2

0.4

0.6

Effective Satisfaction

0.8

1.0

Utilitarian

Fig. 5. CDF of effective overall satisfaction rate across users and resources, aggregated over all congestion profiles.

Linear Proportional

Affine Linear

1.0

0.8

0.6

0.6

0.6

0.2 0.0 0.0

CDF

0.8

0.4

0.4 0.2

0.2

0.4

0.6

0.8

Per-user minimum effective satisfaction

Polynomial Quadratic

1.0

0.8 CDF

CDF

1.0

0.4 0.2

1.0

0.0 0.0

DDRF

DRF

0.2

0.4

0.6

0.8

PF

Mood

Per-user minimum effective satisfaction MMF

1.0

0.0 0.0

0.2

0.4

0.6

0.8

Per-user minimum effective satisfaction

1.0

Utilitarian

are ignored. Taken together, these results show that DDRF combines the fairness balance of MMF with the ability to handle generic dependencies, outperforming all baselines in worst-case user satisfaction without introducing waste. B. Fairness of Dependency-Aware Allocation To assess fairness, we quantify it using Jain’s index and compare DDRF against the Utilitarian baseline. Figure 7 shows boxplots of the average Jain’s index over resources across all congestion profiles. Fairness is evaluated based on allocations. DDRF, designed as an extension of MMF to multiresource settings, explicitly enforces fairness at the allocation level. In almost all cases, DDRF achieves higher median fairness than Utilitarian under the three dependency models,

Average Jain's index across resources

Fig. 6. CDF of users’ minimum effective satisfaction rate across resources, aggregated over all congestion profiles.

1.0 0.8 0.6 0.4 0.2 0.0

DDRF Utilitarian Linear Proportional

Affine Linear

Polynomial Quadratic

Fairness computed from allocations Fig. 7. Boxplots of Jain’s fairness index across congestion profiles for DDRF and Utilitarian. We report fairness computed on allocation.

it increases fairness by more than 15%. Evidently, DDRF

Average Jain's index across resources

IEEE TRANSACTIONS ON NETWORKING, VOL. XX, YYYY

1.2 1.0 0.8 0.6 0.4

31.0%

0.2

16.0%

10.1%

0.0%

DRF waste DRF used DRF idle

PF waste PF used PF idle

Utilitarian waste Utilitarian used Utilitarian idle

Fig. 8. Average partitioning of total resource capacity into wasted, useful, and idle components under different dependency structures across congestion profiles for realistic dependencies.

Real-Resource Dependency

Real-Resource Dependency

1.0

0.8

0.8

0.6

0.6

CDF

CDF

1.0

0.4 0.2

0.4 0.2

0.0 0.0

DDRF

0.2

0.4

0.6

Effective Satisfaction DRF

MMF

(a)

PF

0.8

Utilitarian

1.0

0.0 0.0

DDRF

0.4 0.2 0.0

DDRF Utilitarian

Real-Resource Dependency

n lita

MMF waste MMF used MMF idle

0.6

Fig. 10. Boxplots of Jain’s fairness index across congestion profiles for DDRF and Utilitarian for realistic dependencies. We report fairness on allocation.

Uti

Real-Resource Dependency DDRF waste DDRF used DDRF idle

0.8

ria

PF

F DR

DD

MM F

0.0

1.0

Fairness computed from allocations

-0.0%

RF

Average resource partitioning (waste / used / idle)

12

0.2

0.4

0.6

0.8

Per-user minimum satisfaction DRF

MMF

PF

1.0

Utilitarian

(b)

Fig. 9. CDF of effective (a) overall and (b) minimum satisfaction rate across users and resources, aggregated over all profiles with realistic dependencies.

is well suited to allocation-equity-based fairness formulations that account for inter-resource dependencies C. Experimental Evaluation on a vRAN Use Case with Real Resource Dependencies The previous results were obtained based on synthetic dependencies, however it is desirable to assess the performance on a realistic use case with real resource dependencies. We build a realistic vRAN dependency model by coupling the per-eNB radio load (occupied RBs) to its compute demands (CPU utilization) using measurement-based profiling inspired from [40]. We consider an InP operating a vRAN edge cloud co-located with the eNB instances at the same physical site (same room), where multiple virtual co-located eNB instances (any UE can be admitted to any of the eNBs) are provisioned at a non-real-time timescale (seconds to minutes) via the SMO/non-RT RIC through pereNB budgets for RBs and CPU. To match the adopted profiling regime, each eNB can serve up to 4 UEs (n ∈ [1, 4]) at predefined SINR with MCS ∈ 1, . . . , 27, while the occupied RB load varies across slices. For each eNB i, we sample RBi ∼ U[1, 50] for N − 3 slices and add three “weak” slices with RB ∈ {1, 2, 3} to increase heterogeneity. We then generate demands di = (di,RB , di,CPU , di,n ) with CPU utilization demand adopted from the regression model taken

from [40], di,CPU = 3.46 n + 0.325 RBi + 0.28 MCSi + 26.55 (with MCSi ∼ U[1, 27]). Capacities are generated from the aggregate demand vector P c = i di and a set of pre-defined congestion profiles. We select profiles that create RB-, CPU-, or n-bottlenecks while avoiding near-infeasible corners caused by tight CPU baselines under the above equalities (each eNB requires CPU utilization even if no user was admitted and no RBs were assigned). Finally, if the assigned CPU utilization for eNB i is below the baseline term (0.28 · MCSi + 26.55), we consider all the assigned resources to it as wasted: without sufficient CPU to sustain the baseline processing implied by the selected MCS, any allocated RB/UE budget is effectively unusable at run time, hence it cannot be converted into delivered service. Similar to the synthetic experiment we report stacked bar plot for capacity partitioning, Figure 8, CDF for the overall satisfaction, Figure 9a, CDF for the minimum satisfaction, Figure 9b and allocation based Jain’s fairness index between DDRF and utilitarian, Figure 10, these figures assert the numerical results obtained with the synthetic experiment. Our framework enforces fairness while respecting userspecific inter-resource dependencies. When dependencies are affine, the resulting DDRF program remains convex and can be solved efficiently. In contrast, nonlinear dependencies typically make the problem nonconvex particularly when equality constraints couple linear and nonlinear terms creating challenges in both feasibility enforcement and global optimization. We therefore emphasize that DDRF is a general framework rather than a single fixed solver: the appropriate solution approach depends on the structure of the dependency functions. In practice, one can leverage problem-specific properties via convexification, sequential linearization, conservative relaxations, or carefully designed heuristics, while preserving the fairness logic of DDRF. Another limitation concerns fairness quantification. The multi-resource allocation literature still lacks a widely accepted global quantitative fairness measure. More importantly, we argue that any meaningful metric must be dependencyaware: assessing fairness purely from allocated shares without accounting for whether those shares are actually usable under the declared inter-resource couplings can be misleading. This is precisely what we observed in the Jain-index boxplots under nonlinear proportional dependencies, where allocation-based fairness did not reflect the effective fairness experienced by tenants. Designing robust dependency-aware fairness metrics is therefore a key direction we leave for future work.

BRAIK et al.: DEPENDENCY-AWARE DOMINANT RESOURCE FAIRNESS FOR MULTI-TENANT MULTI-RESOURCE SYSTEMS

VII. C ONCLUSION AND PERSPECTIVES This paper introduced Dependency-Aware Dominant Resource Fairness (DDRF), a generalization of max–min fairness (MMF) to multi-resource allocation under generic interresource dependencies. Building on the principles of dominant resource fairness (DRF), DDRF resolves three key shortcomings: it properly accounts for weak users, redefines the bottleneck resource in the presence of dependencies, and reformulates the notion of user satisfaction to reflect dependencyfeasible service levels. As a result, DDRF guarantees Pareto efficiency and bottleneck fairness. The framework is practical: given demand vectors, resource capacities, and dependency constraints, DDRF computes fair allocations in a centralized manner. Extensive experiments show that DDRF maximizes the number of fully satisfied tenants without starving others, strictly outperforms MMF in terms of effective satisfaction, and guarantees resource saturation whenever feasible. Across a broad range of settings - from linear to nonlinear dependencies - DDRF consistently achieved zero waste, improved satisfaction compared to dependencyagnostic approaches, and delivered stronger fairness than dependency-aware baselines. Notably, DDRF increased the effective satisfaction rate by up to 80%, improved Jain’s fairness by up to 60%, and reduced waste by about 60%. Future directions include extending our theoretical guarantees beyond Pareto efficiency and saturation. While we derived structural assumptions on dependency sets that ensure saturation of at least one congested resource and thus Pareto efficiency an important next step is to identify weaker (more general) assumptions under which additional fairness properties can be guaranteed, such as share-incentive, strategyproofness, and envy-freeness, especially in the presence of nonlinear dependencies. Finally, moving beyond centralized allocation is essential for scalability, motivating the design of distributed implementations suitable for large-scale systems. R EFERENCES [1] A. Chandra, M. Adler, P. Goyal, and P. Shenoy, “Surplus fair scheduling: A proportional-share cpu scheduling algorithm for symmetric multiprocessors,” in Proceedings of the 4th Symposium on Operating Systems Design and Implementation (OSDI). USENIX Association, 2000. [2] E. Boutin, J. Ekanayake, W. Lin, B. Shi, J. Zhou, Z. Qian, M. Wu, and L. Zhou, “Apollo: Scalable and coordinated scheduling for cloudscale computing,” in Proceedings of the 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI). USENIX Association, 2014, pp. 285–300. [3] P. Rost, C. Mannweiler, D. S. Michalopoulos, C. Sartori, V. Sciancalepore, N. Sastry, O. Holland, S. Tayade, B. Han, D. Bega, D. Aziz, and H. Bakker, “Network slicing to enable scalability and flexibility in 5g mobile networks,” IEEE Communications Magazine, vol. 55, no. 5, pp. 72–79, 2017. [4] F. Kelly, “Charging and rate control for elastic traffic,” European transactions on Telecommunications, vol. 8, no. 1, pp. 33–37, 1997. [5] F. P. Kelly, A. K. Maulloo, and D. K. H. Tan, “Rate control for communication networks: shadow prices, proportional fairness and stability,” Journal of the Operational Research society, vol. 49, no. 3, pp. 237–252, 1998. [6] D. Bertsekas and R. Gallager, Data networks. Athena Scientific, 2021. [7] J. Mo and J. Walrand, “Fair end-to-end window-based congestion control,” IEEE/ACM Transactions on networking, vol. 8, no. 5, pp. 556– 567, 2002. [8] T. Lan, D. Kao, M. Chiang, and A. Sabharwal, An axiomatic theory of fairness in network resource allocation. IEEE, 2010.

13

[9] A. Ghodsi, M. Zaharia, B. Hindman, A. Konwinski, S. Shenker, and I. Stoica, “Dominant resource fairness: Fair allocation of multiple resource types,” in 8th USENIX symposium on networked systems design and implementation (NSDI 11), 2011. [10] W. Wang, B. Liang, and B. Li, “Multi-resource fair allocation in heterogeneous cloud computing systems,” IEEE Transactions on Parallel and Distributed Systems, vol. 26, no. 10, pp. 2822–2835, 2014. [11] C. Joe-Wong, S. Sen, T. Lan, and M. Chiang, “Multiresource allocation: Fairness–efficiency tradeoffs in a unifying framework,” IEEE/ACM Transactions on Networking, vol. 21, no. 6, pp. 1785–1798, 2013. [12] F. Fossati, S. Moretti, P. Perny, and S. Secci, “Multi-resource allocation for network slicing,” IEEE/ACM Transactions on Networking, vol. 28, no. 3, pp. 1311–1324, 2020. [13] T. Bonald and J. Roberts, “Multi-resource fairness: Objectives, algorithms and performance,” in Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, ser. SIGMETRICS ’15. New York, NY, USA: Association for Computing Machinery, 2015, p. 31–42. [Online]. Available: https://doi.org/10.1145/2745844.2745869 [14] M. Chowdhury, Z. Liu, A. Ghodsi, and I. Stoica, “Hug: multi-resource fairness for correlated and elastic demands,” in Proceedings of the 13th Usenix Conference on Networked Systems Design and Implementation, ser. NSDI’16. USA: USENIX Association, 2016, p. 407–424. [15] P. Poullie, T. Bocek, and B. Stiller, “A survey of the state-of-the-art in fair multi-resource allocations for data centers,” IEEE Transactions on Network and Service Management, vol. 15, no. 1, pp. 169–183, 2018. [16] M. Polese, L. Bonati, S. D’oro, S. Basagni, and T. Melodia, “Understanding o-ran: Architecture, interfaces, algorithms, security, and research challenges,” IEEE Communications Surveys & Tutorials, vol. 25, no. 2, pp. 1376–1411, 2023. [17] S. Khatibi, K. Shah, and M. Roshdi, “Modelling of computational resources for 5g ran,” in 2018 European Conference on Networks and Communications (EuCNC). IEEE, 2018, pp. 1–5. [18] H. Hojeij, G. I. Ricardo, M. Sharara, S. Hoteit, V. Vèque, and S. Secci, “On flexible association and placement in disaggregated ran designs,” Computer Communications, vol. 238, p. 108166, 2025. [19] Y. Xiao, J. Zhang, and Y. Ji, “Can fine-grained functional split benefit to the converged optical-wireless access networks in 5g and beyond?” IEEE Transactions on Network and Service Management, vol. 17, no. 3, pp. 1774–1787, 2020. [20] TS 38.214: NR; Physical layer procedures for data, 3rd Generation Partnership Project (3GPP) Std. TS 38.214, 2023, release 17, v17.6.0. [Online]. Available: https://www.3gpp.org/ftp/Specs/archive/38 series/ 38.214/ [21] A. W. Marshall, I. Olkin, and B. C. Arnold, Inequalities: theory of majorization and its applications. Springer, 1979. [22] M. Zaharia, D. Borthakur, J. Sen Sarma, K. Elmeleegy, S. Shenker, and I. Stoica, “Delay scheduling: a simple technique for achieving locality and fairness in cluster scheduling,” in Proceedings of the 5th European conference on Computer systems, 2010, pp. 265–278. [23] L. Popa, G. Kumar, M. Chowdhury, A. Krishnamurthy, S. Ratnasamy, and I. Stoica, “Faircloud: Sharing the network in cloud computing,” in Proceedings of the ACM SIGCOMM 2012 conference on Applications, technologies, architectures, and protocols for computer communication, 2012, pp. 187–198. [24] J. Rawls, “A theory of justice, harvard,” Press, Cambridge, 1971. [25] W. Ogryczak, H. Luss, M. Pióro, D. Nace, and A. Tomaszewski, “Fair optimization and networks: A survey,” Journal of Applied Mathematics, vol. 2014, no. 1, p. 612018, 2014. [26] P. Namyar, B. Arzani, S. Kandula, S. Segarra, D. Crankshaw, U. Krishnaswamy, R. Govindan, and H. Raj, “Solving Max-Min fair resource allocations quickly on large graphs,” in 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI 24). Santa Clara, CA: USENIX Association, Apr. 2024, pp. 1937– 1958. [Online]. Available: https://www.usenix.org/conference/nsdi24/ presentation/namyar-solving [27] H. Moulin, “Axiomatic cost and surplus sharing,” Handbook of social choice and welfare, vol. 1, pp. 289–357, 2002. [28] F. Fossati, S. Hoteit, S. Moretti, and S. Secci, “Fair resource allocation in systems with complete information sharing,” IEEE/ACM Transactions on Networking, vol. 26, no. 6, pp. 2801–2814, 2018. [29] D. C. Parkes, A. D. Procaccia, and N. Shah, “Beyond dominant resource fairness: Extensions, limitations, and indivisibilities,” ACM Transactions on Economics and Computation (TEAC), vol. 3, no. 1, pp. 1–22, 2015. [30] W. Wang, B. Li, and B. Liang, “Dominant resource fairness in cloud computing systems with heterogeneous servers,” in IEEE INFOCOM

14

IEEE TRANSACTIONS ON NETWORKING, VOL. XX, YYYY

2014-IEEE Conference on Computer Communications. IEEE, 2014, pp. 583–591. [31] M. Chowdhury, Z. Liu, A. Ghodsi, and I. Stoica, “{HUG}:{MultiResource} fairness for correlated and elastic demands,” in 13th USENIX symposium on networked systems design and implementation (NSDI 16), 2016, pp. 407–424. [32] T. Bonald and J. Roberts, “Multi-resource fairness: Objectives, algorithms and performance,” SIGMETRICS Perform. Eval. Rev., vol. 43, no. 1, p. 31–42, Jun. 2015. [Online]. Available: https: //doi.org/10.1145/2796314.2745869 [33] H. Dalton, “The measurement of the inequality of incomes,” The Economic Journal, vol. 30, no. 119, pp. 348–361, 1920. [34] X. Shen, S. Diamond, Y. Gu, and S. Boyd, “Disciplined convexconcave programming,” 2016 IEEE 55th Conference on Decision and Control (CDC), pp. 1009–1014, 2016. [Online]. Available: https://stanford.edu/∼boyd/papers/dccp.html [35] Vantage, “Ec2instances.info - easy amazon ec2 instance comparison,” https://instances.vantage.sh/. [36] 3GPP, “TS 38.104: NR; Base Station (BS) radio transmission and reception,” 3rd Generation Partnership Project (3GPP), Tech. Rep., 2023, release 17, v17.9.0. [Online]. Available: https://www.etsi.org/deliver/ etsi ts/138100 138199/138104/17.09.00 60/ts 138104v170900p.pdf [37] S. Diamond and S. Boyd, “CVXPY: A Python-embedded modeling language for convex optimization,” Journal of Machine Learning Research, vol. 17, no. 83, pp. 1–5, 2016. [38] X. Shen, S. Diamond, Y. Gu, and S. Boyd, “Disciplined convex-concave programming,” arXiv preprint arXiv:1604.02639, 2016. [39] R. K. Jain, D.-M. W. Chiu, W. R. Hawe et al., “A quantitative measure of fairness and discrimination,” Eastern Research Laboratory, Digital Equipment Corporation, Hudson, MA, vol. 21, no. 1, pp. 2022–2023, 1984. [40] S. Pramanik, A. Ksentini, and C. F. Chiasserini, “Cost-efficient slicing in virtual radio access networks,” Computer Communications, vol. 209, pp. 349–358, 2023.

A PPENDIX A A SSUMPTIONS ON D EPENDENCIES FOR S ATURATION We now specify the assumptions on F that guarantee the Pareto efficiency of (DDRF) and (D-Util). Consider the dependency-aware multi-resource problem (D, C, F) and assume that at least one resource is congested. Let X ⋆ be an optimal solution of (D-Util) or (DDRF). Local regularity and local improving feasible direction. For any tenant i ∈ N such that there exists an active congested d bottleneck resource ji′ ∈ arg maxj∈C: yij =1 cijj , we impose the (k)

following assumptions on the dependency constraints fi of (k) tenant i that are active at X ⋆ , i.e., fi (X ⋆ ) = 0, and whose (k) dependency sets Si ⊆ Si contain j ′ . ′ Define Ai (j ) ≜ { k ∈ {1, . . . , Ki } : j ′ ∈ (k) (k) Si and fi (X ⋆ ) = 0 }, the set of active dependency constraints of tenant i that contain j ′ and active at X ⋆ . We distinguish two cases according to the cardinality of Ai (j ′ ). • Case (i) (unique active constraint). Suppose that Ai (j ′ ) = {k}. Then we assume: (1) (Local regularity) (k) The function fi is C 1 in a neighborhood of X ⋆ with respect to the variables (xir )r∈S (k) . (2) (Improvingi

∂f

(k)

direction inequality) Define gr ≜ ∂xiir (X ⋆ ) for all (k) r ∈Si . Then:  P P gj ′ g < r∈S (k) \{j ′ } gr2 . (k) r r∈S \{j ′ } i

•

i

Case (ii) (multiple active constraints). Suppose that |Ai (j ′ )| ≥ 2. Then we assume: (1) (Local regularity) (k) For every k ∈ Ai (j ′ ), the function fi is C 1 in a neigh⋆ borhood of X . (2) (Joint improving-direction condition)

S (k) Let Ui (j ′ ) ≜ k∈Ai (j ′ ) Si be the set of coordinates of tenant i allowed to vary. Define the Jacobian matrix ′ ′ Jact (X ⋆ ) ∈ R|Ai (j )|×|Ui (j )| by: ∂f

(k)

[Jact (X ⋆ )]k,r ≜ ∂xiir (X ⋆ ), for k ∈ Ai (j ′ ) and r ∈ Ui (j ′ ), with the convention ∂f

(k)

(k)

that ∂xiir (X ⋆ ) = 0 whenever r ∈ / Si . We assume ′ that there exists a direction ∆i ∈ R|Ui (j )| such that ∆ij ′ > 0, Jact (X ⋆ )∆i = 0, and 1⊤ ∆i > 0, and (k) moreover ∇fi (X ⋆ )⊤ ∆i ≤ 0 for every active inequality constraint k ∈ Ai (j ′ ). A PPENDIX B P ROOF OF L EMMA 1 Proof. We prove saturation (hence Pareto efficiency) by contradiction. Without loss of generality, we consider the minimal case where there is a single congested resource j ′ ∈ M. Let X ⋆ be an optimal solution of (D-Util). We show that j ′ must be PN saturated, i.e., i=1 dij ′ x⋆ij ′ = cj ′ . Assume for contradiction PN that j ′ is not saturated: i=1 dij ′ x⋆ij ′ < cj ′ . Let the excess PN be sj ′ ≜ P cj ′ − i=1 dij ′ x⋆ij ′ > 0. Since j ′ is congested in the sense i dij ′ > cj ′ , feasibility implies that there exists a tenant i′ ∈ N with x⋆i′ j ′ < 1. We construct a perturbation supported on tenant i′ only. The key intuition is the first-order Taylor expansion of each (k) C 1 dependency constraint fi′ around X ⋆ : for any direction ′ ∆xi′ and any k ∈ Ai′ (j ), we have: (k) (k) (k) fi′ (X ⋆ + ε∆X) = fi′ (X ⋆ ) + ε ∇fi′ (X ⋆ )⊤ ∆xi′ + o(ε) as ε → 0, where o(ε) denotes a remainder satisfying o(ε)/ε → (k) 0 as ε → 0. Hence an active equality constraint fi′ (X ⋆ ) = 0 (k) is preserved to first order by imposing ∇fi′ (X ⋆ )⊤ ∆xi′ = 0. Fix the pair (i′ , j ′ ) given by the assumptions of Lemma 1. (k′ ) If |Ai′ (j ′ )| = 1, write Ai′ (j ′ ) = {k ′ }, let S ≜ Si′ , ′ (k ) let J ≜ S \ {j ′ }, and define gr ≜ ∂fi′ /∂xi′ r (X ⋆ ) for all r ∈ S. Define P a direction ∆xi′ by ∆xi′ j ′ = 1, ∆xi′ r = −(gj ′ gr )/ ℓ∈J gℓ2 for r ∈ J, and ∆xi′ r = 0 for P (k′ ) r∈ / S. Then ∇fi′ (X ⋆ )⊤ ∆xi′ = gj ′ + r∈J gr ∆xi′ r = 0, hence the unique active dependency constraint is preserved to first order. Moreover, Pthe utilityPgain along this direction is 1⊤ ∆xi′ = 1 − (gj ′ r∈J gr )/ r∈J gr2 , which is strictly positive by the inequality in Case (i) (2) in appendix A. (k′ ) By C 1 -regularity, ∇fi′ (X ⋆ )⊤ ∆xi′ = 0 ensures that the active dependency constraints are preserved to first order. To enforce them exactly (not only to first we invoke P order), 2 the implicit function theorem: since g > 0, there ℓ∈J ℓ (k′ ) ⋆ exists r0 ∈ J with ∂fi′ /∂xi′ r0 (X ) ̸= 0, so for ε > 0 small enough one can choose xi′ r0 as a C 1 function of the remaining perturbed coordinates (including xi′ j ′ ) so that (k′ ) fi′ (X ⋆ + ε∆X) = 0 holds exactly. We n then choose any ε ∈⋆ (0, ε̄) such that ε̄⋆ ≜o s ′ 1−x xi′ r min d j′ ′ , minr∈S: ∆xi′ r >0 ∆x i′′ r , minr∈S: ∆xi′ r <0 −∆x i j i r i′ r Since ∆xi′ j ′ = 1, this guaranteesP that 0 ≤ x⋆i′ r + ε∆xi′ r ≤ 1 ⋆ ′ ′ for every r ∈ S. Moreover, i dij (xij ′ + ε∆xij ) = P ⋆ ′ x ′ + di′ j ′ ε ≤ cj ′ . Thus the bound constraints on d ij ij i the perturbed coordinates and the capacity constraint on j ′ remain satisfied.

BRAIK et al.: DEPENDENCY-AWARE DOMINANT RESOURCE FAIRNESS FOR MULTI-TENANT MULTI-RESOURCE SYSTEMS

P Finally, the objective strictly increases: i,j (x⋆ij +ε∆xij ) = P ⋆ ⊤ ⊤ ′ ′ i,j xij + ε 1 ∆xi , and 1 ∆xi > 0, hence the objective is larger for any such ε > 0. This contradicts optimality of X ⋆ . PN ⋆ ′ ′ Therefore i=1 dij xij ′ = cj , i.e., at least one congested resource is saturated at the utilitarian optimum and Pareto efficiency immediately follows.

cC

15

cC⋆

= minj∈M0 M1 (αjC ;d·j ) = M1 (αCj ;d·j⋆ ) ,

M (αC ;d )

where j ⋆ ∈ arg minj∈M0 1 cC ·j (with cC0 = j P (mini µCi ) i αiC , dn·0 = 1). o c Similarly, t = min mini∈N µi , minj∈M0 P αji dij , i P DRF P cj ′ cj = t i αi = minj∈M0 M1 (α;d = M1 (α;d , i xi ) ′) ·j ·j

M (α;d )

Note: Inactive inequality constraints are those with (k) (k) fi (X ⋆ ) < 0. For such constraints, continuity at X ⋆ of fi for k ∈ Ai (j ′ ) is enough: sufficiently small perturbations

preserve strict feasibility. Thus only active constraints need to be enforced explicitly. A PPENDIX C P ROOF OF T HEOREM 1 Proof. We argue by contradiction and, without loss of generality, consider the minimal nontrivial case of a single congested resource j ′ ∈ M with exactly two active tenants i′ , i′′ on it. Let X ⋆ be an optimal P solution of (DDRF), and suppose that N ′ jP is not saturated, i.e., i=1 dij ′ x⋆ij ′ < cj ′ . Set sj ′ ≜ cj ′ − ⋆ ′ ′′ ′ ′ i dij xij ′ > 0. Since i and i are active on j , the fairness ⋆ ⋆ equality gives µi′ j ′ xi′ j ′ = µi′′ j ′ xi′′ j ′ . We therefore choose the perturbation on the bottleneck coordinate j ′ as x⋆i′ j ′ 7→ x⋆i′ j ′ +ε/µi′ j ′ and x⋆i′′ j ′ 7→ x⋆i′′ j ′ +ε/µi′′ j ′ , so that the fairness equality on j ′ is preserved exactly for every ε > 0. By the assumptions of Appendix A, for each tenant t ∈ {i′ , i′′ } there exists a tenant-wise feasible direction ∆xt supported on the coordinates coupled to j ′ such that ∆xtj ′ = 1/µtj ′ , the active dependency constraints containing j ′ are preserved to first order (and exactly after the same implicitfunction as in Lemma 1), and 1⊤ ∆xt > 0. Let St denote the set of perturbed coordinates of tenant t. We then choose any ε ∈ (0, ε̄) such ( that: ε̄ = min

sj ′ ′ ′′ di′ j ′ /µi′ j ′ +di′′ j ′ /µi′′ j ′ , mint∈{i ,i } x⋆

1−x⋆

)

tr . minr∈St : ∆xtr >0 ∆xtrtr , mint∈{i′ ,i′′ } minr∈St : ∆xtr <0 −∆x tr

The remainder of the proof then follows exactly as in Lemma 1. A PPENDIX D P ROOF OF T HEOREM 2 A. Case 1: All Users active, some have bottleneck on a noncongested resource Proof. Assume linear dependency and that the equalization constraints hold for all users (Active case). With αiC = 1/µCi , αi = 1/µi , µCi xi = tC ⇒ xi = tC αiC , µi xi = t ⇒ xi = tαi . Moreover, xi ≤ 1 implies: tC ≤ mini∈N µCi , t ≤ mini∈N µi . For j ∈ M0 : P P C cC C C C C P jC . i dij xi ≤ cj ⇒ t i αi dij ≤ cj ⇒ t ≤   i αi dij C c Hence, tC = min mini∈N µCi , minj∈M0 P αjC dij . i i P DDRF P Therefore, x = tC  i αiC =  P  iPi C cC j i αi C C P C min mini µi i αi , minj∈M0 α dij i

i

where j ′ ∈ arg minj∈M0 1 cj ·j (with c0 = P (mini µi ) i αi ). P P cC⋆ cj ′ Thus: i xDDRF ≥ i xDRF ⇐⇒ M1 (αCj ;d·j⋆ ) ≥ M1 (α;d i i ′) M (α;d ′ ) M1 (αC ;d·j ⋆ ) ≤ 1 c ′ ·j . cC j j⋆ P DDRF M1 (αC ; d·j ⋆ ) M1 (α; d·j ′ ) (i) If , then ≤ i xi C ′ cj cj ⋆ P DRF . i xi P DDRF M1 (αC ; d·j ⋆ ) M1 (α; d·j ′ ) (ii) If > , then i xi C cj ′ cj ⋆ P DRF . i xi

·j

⇐⇒

≥

<

B. Case 2: At least one User weak, some have bottleneck on a non-congested resource In DDRF, xi = 1 for all i ∈ W. For i ∈ A. The equalization constraints give µCi xi = tC ⇒ xi = tC αiC , i ∈ A, Hence x ≤ 1 implies tC P ≤ mini∈A µCi . For j ∈ i P PM, d x ≤ c ⇒ d x ≤ c − ij i j ij i j i∈N i∈A i∈W dij ⇒ P tC i∈A αiC dij ≤ c̃j , P where c̃j P ≜ cj − With c̃0 ≜ i∈W dij . (mini∈A µCi ) i∈A αiC and M0 = M ∪ {0} (and di0 = 1). c̃ This yields: tC = minj∈M0 P jαC dij , i∈A P i P DDRF = |W| + tC i∈A αiC = |W| + i∈N xi c̃j̃ ⋆ c̃j minj∈M0 M1 (αC ;dA,·j ) = |W| + M1 (αC ;d ⋆ ) , A

M (αC ;d

A,·j̃

A

)

where j̃ ⋆ ∈ arg minj∈M0 1 Ac̃j A,·j . For DRF, µi xi = t ⇒ xi = tαi , t c minj∈M0 P jαi dij , i∈N P P cj DRF = t i∈N αi = minj∈M0 M1 (α;d i∈N xi ·j ) cj ′ M1 (α;d ′ ) ,

= =

·j

M (α;d )

where j ′ ∈ arg minj∈M0 1 cj ·j . P P DDRF DRF Therefore, ≥ ⇐⇒ |W| + i∈N xi i∈N xi c̃j̃ ⋆ cj ′ ≥ M1 (α;d ′ ) , M1 (αC ·j A ;dA,·j̃ ⋆ ) P P and the reverse inequality yields i xDDRF < i xDRF . i i