Leveraging joint allocation of multidimensional resources for distributed task assignment

Jialong Li; Jialong Li; Nan Hua; Nan Hua; Kangqi Zhu; Kangqi Zhu; Chen Zhao; Chen Zhao; Guanqin Pan; Yanhe Li; Xiaoping Zheng; Xiaoping Zheng; Bingkun Zhou; Bingkun Zhou

doi:10.1364/JOCN.446747

Journal of Optical Communications and Networking
Vol. 14,
Issue 5,
pp. 351-364
(2022)
•https://doi.org/10.1364/JOCN.446747

Leveraging joint allocation of multidimensional resources for distributed task assignment

Jialong Li, Nan Hua, Kangqi Zhu, Chen Zhao, Guanqin Pan, Yanhe Li, Xiaoping Zheng, and Bingkun Zhou

Not Accessible

Your library or personal account may give you access

Get PDF
Email
Share
Get Citation
Copy Citation Text
Jialong Li, Nan Hua, Kangqi Zhu, Chen Zhao, Guanqin Pan, Yanhe Li, Xiaoping Zheng, and Bingkun Zhou, "Leveraging joint allocation of multidimensional resources for distributed task assignment," J. Opt. Commun. Netw. 14, 351-364 (2022)

Export Citation
- BibTex
- Endnote (RIS)
- HTML
- Plain Text
Citation alert
Save article

Abstract

Edge computing has changed the landscape of telecommunication networks. Different from cloud computing in which thousands of servers are centralized in a remote site, computation and storage resources are deployed at the network edge in edge computing, reducing the end-to-end latency and the amount of transmitting data in metro/backbone networks significantly. Due to the limited resource capacity in a single edge node and the requirements of distributed applications, some applications are supposed to be decomposed into multiple interdependent tasks and executed in distributed resource-constrained nodes. Assigning tasks to geographically distributed edge nodes is quite challenging because of the allocation of multidimensional resources (i.e., computation, storage, and transmission) as well as constraints of the interdependency between different tasks. Strategies that take only one factor into account for optimization will cause improper task assignments, leading to higher end-to-end latency and lower resource utilization efficiency. To solve this problem, we formulate a mathematical model aiming at minimizing the job completion time by jointly considering the availability of multidimensional resources and the interdependency among different tasks. We obtain optimal results in small topology by using optimization software that validates the correctness of the proposed mathematical model. Furthermore, we analyze the complexity and design of a practical algorithm by narrowing the searching space in large-scale topology. Simulation results present its effectiveness over greedy algorithms. Finally, we conduct a proof-of-concept experiment to validate the feasibility of the proposed strategy.

Full Article | PDF Article

More Like This

Cost-Optimized Joint Resource Allocation in Grids/Clouds With Multilayer Optical Network Architecture

Pan Yi, Hui Ding, and Byrav Ramamurthy
J. Opt. Commun. Netw. 6(10) 911-924 (2014)

Agent-based distributed protocol for resource discovery and allocation of virtual networks over elastic optical networks

Danilo Bórquez-Paredes, Alejandra Beghelli, Ariel Leiva, Nicolás Jara, Astrid Lozada, Patricia Morales, Gabriel Saavedra, and Ricardo Olivares
J. Opt. Commun. Netw. 14(8) 667-679 (2022)

Dependency-aware task cooperative offloading on edge servers interconnected by metro optical networks

Shan Yin, Wei Zhang, Yutong Chai, and Shanguo Huang
J. Opt. Commun. Netw. 14(5) 376-388 (2022)

Previous Article Next Article

Cited By

You do not have subscription access to this journal. Cited by links are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

Figures (14)

You do not have subscription access to this journal. Figure files are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

Tables (4)

You do not have subscription access to this journal. Article tables are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

Equations (20)

You do not have subscription access to this journal. Equations are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

Input	Description
$G (N, E)$	Network topology, where $N$ and $E$ represent the set of nodes and fiber links, respectively
$A$	Set of DAGs
$a$	DAG and $a \in A$
$W$	Set of wavelengths in each fiber link
$c$	Speed of light in the fiber
$(a_{p}, a_{q})$	Computation result transmission between tasks $a_{p}$ and $a_{q}$ , where $a_{p}$ is the forward task and $a_{q}$ is the backward task; $a_{p}, a_{q} \in a$
$T^{(a_{p}, a_{q})}$	Number of time slices required by transmission $(a_{p}, a_{q})$
$(b, a_{p})$	Raw data transmission for task $a_{p}$ , where raw data are stored in node $b$ initially; $b \in N$
$T^{(b, a_{p})}$	Number of MOTSs required by transmission $(b, a_{p})$
$C^{a_{p}}$	Number of MOTSs required by execution $a_{p}$
$t$	Length of a MOTS
$S$	Set of MOTSs in one frame
$l^{(a_{p}, a_{q})}$	Lightpath used by computation result transmission $(a_{p}, a_{q})$
$l^{(b, a_{p})}$	Lightpath used by raw data transmission $(b, a_{p})$
$D^{l}$	Physical length of lightpath $l$
$D^{e}$	Physical length of edge $e$ , $e \in l$
CPU	CPU capacity of each node
RAM	RAM capacity of each node
${cpu}^{a_{p}}$	CPU resource requirements for task $a_{p}$
${ram}^{a_{p}}$	RAM resource requirements for task $a_{p}$

Variables	Description
$x_{n}^{a_{p}}$	Binary decision variable, which is one if task $a_{p}$ is executed in node $n$
$y_{(e, w, i)}^{(a_{p}, a_{q})}$	Binary decision variable, which is one if result transmission $(a_{p}, a_{q})$ uses the $i$ th time slice on wavelength $w$ in edge $e$
$z_{(e, w, i)}^{(b, a_{p})}$	Binary decision variable, which is one if data transmission $(b, a_{p})$ uses the $i$ th time slice on wavelength $w$ in edge $e$
$π_{(e, w)}^{(a_{p}, a_{q})}$	Binary decision variable, which is one if result transmission $(a_{p}, a_{q})$ uses wavelength $w$ in edge $e$
$θ_{(n, i)}^{a_{p}}$	Binary decision variable, which is one if task $a_{p}$ uses computation resources in the $i$ th time slice in node $n$

Parameters	Value
Small topology	6 nodes, 8 links
Distance between two adjacent nodes	20 km
Number of wavelengths in each link	4
Length of an OTSS frame	10 ms
Number of MOTS in an OTSS frame	100
Computation result transmission time ( $T_{c o t r}$ )	100/200 µs
Task execution time ( $T_{e x e c}$ )	100 µs
Raw data transmission time ( $T_{r a t r}$ )	300 µs
Maximum CPU capacity in each node	100
Maximum RAM capacity in each node	100
Required CPU capacity for a task	5–50
Required RAM capacity for a task	5–50
Number of jobs	1–600

Parameters	Value
Large topology	38 nodes, 59 links
Distance between two adjacent nodes	20/100 km
Number of wavelengths in each link	16
Length of an OTSS frame	100 ms
Number of MOTS in an OTSS frame	1000
Computation result transmission time ( $T_{c o t r}$ )	100–300 µs
Task execution time ( $T_{e x e c}$ )	100–800 µs
Raw data transmission time ( $T_{r a t r}$ )	100–400 µs
Maximum CPU capacity in each node	80/100
Maximum RAM capacity in each node	80/100
Required CPU capacity for a task	1–10
Required RAM capacity for a task	1–10
Number of jobs	100–1500

Input	Description
$G (N, E)$	Network topology, where $N$ and $E$ represent the set of nodes and fiber links, respectively
$A$	Set of DAGs
$a$	DAG and $a \in A$
$W$	Set of wavelengths in each fiber link
$c$	Speed of light in the fiber
$(a_{p}, a_{q})$	Computation result transmission between tasks $a_{p}$ and $a_{q}$ , where $a_{p}$ is the forward task and $a_{q}$ is the backward task; $a_{p}, a_{q} \in a$
$T^{(a_{p}, a_{q})}$	Number of time slices required by transmission $(a_{p}, a_{q})$
$(b, a_{p})$	Raw data transmission for task $a_{p}$ , where raw data are stored in node $b$ initially; $b \in N$
$T^{(b, a_{p})}$	Number of MOTSs required by transmission $(b, a_{p})$
$C^{a_{p}}$	Number of MOTSs required by execution $a_{p}$
$t$	Length of a MOTS
$S$	Set of MOTSs in one frame
$l^{(a_{p}, a_{q})}$	Lightpath used by computation result transmission $(a_{p}, a_{q})$
$l^{(b, a_{p})}$	Lightpath used by raw data transmission $(b, a_{p})$
$D^{l}$	Physical length of lightpath $l$
$D^{e}$	Physical length of edge $e$ , $e \in l$
CPU	CPU capacity of each node
RAM	RAM capacity of each node
${cpu}^{a_{p}}$	CPU resource requirements for task $a_{p}$
${ram}^{a_{p}}$	RAM resource requirements for task $a_{p}$

Abstract

Cited By

Figures (14)

Tables (4)

Equations (20)

Journal of Optical Communications and Networking