1
Optimization of Model Splitting, Placement, and Chaining for Multi-hop Split Learning and Inference
arXiv:2604.25197v1 [cs.NI] 28 Apr 2026
Takanori Hara, Member, IEEE, and Masahiro Sasabe, Member, IEEE
Abstract—Service Function Chaining (SFC) establishes efficient communication paths by ensuring that traffic traverses a predefined sequence of network functions in a specified order to meet particular service requirements. Inspired by this concept, we have proposed an SFC-based architecture for multi-hop split learning (MSL) and split inference (MSI), facilitating distributed AI applications to effectively route smashed data across multihop networks. However, the multi-hop environment presents new challenges, including (1) determining optimal cut points, (2) deploying split sub-models on appropriate computing nodes, and (3) routing smashed data through the underlying communication networks while adhering to service requirements. To address these challenges, we formulate an Integer Linear Programming (ILP) model to jointly optimize model splitting, placement, and chaining (data routing) in the SFC-based MSL/MSI architecture, aiming to minimize end-to-end inference or training latency. Additionally, we propose a Block Coordinate Descent (BCD)-based heuristic algorithm to efficiently solve the problem. Comprehensive evaluations demonstrate the effectiveness and characteristics of the proposed formulation and algorithm. Index Terms—Service Function Chaining (SFC), Integer Linear Programming (ILP), Multi-hop Split Learning and Inference (MSL/MSI), Block Coordinate Descent (BCD) algorithm
I. I NTRODUCTION Recently, there has been growing demand for distributed Artificial Intelligence (AI) under stringent constraints on privacy, latency, power consumption, and computational resources through distributed execution across cloud-edge-end environments. Split learning and inference (SL/SI) emerge as key enablers of distributed AI architecture by partitioning a global model into two sub-models, where one sub-model is deployed on a server and the other is deployed on multiple resource-constrained client devices [1]–[3]. Multi-hop split learning and inference (MSL/MSI) extend SL/SI to multihop network environments by partitioning a global model into multiple disjoint sub-models and deploying them across multiple computing nodes [4]–[8]. Unlike SL/SI, which typically assumes direct client-server communication, MSL/MSI must address the routing of processed data, commonly referred to as smashed data, across multiple sub-models through multihop paths in the underlying communication networks. This routing directly affects end-to-end performance metrics such as training and inference latency. This work was supported in part by the Japan Society for the Promotion of Science (JSPS) KAKENHI (B) under Grant 25K03114 and 26K02903 and the Support Center for Advanced Telecommunications Technology Research (SCAT). T. Hara is with the Division of Information Science, Nara Institute of Science and Technology, Nara, Japan, e-mail: [email protected]. M. Sasabe is with the Faculty of Informatics, Kansai University, Takatsuki, Japan, email: [email protected].
Service Function Chaining (SFC) establishes efficient communication paths by ensuring that traffic traverses a predefined sequence of network functions in a designated order to meet specific service requirements [9]. In [6], we proposed an SFCbased distributed AI architecture in which split sub-models are treated as network functions and their composition forms a service chain representing the global model. However, this architecture introduces new challenges: (1) selecting optimal split points, (2) deploying split sub-models on appropriate computing nodes, and (3) routing smashed data through the underlying communication networks while satisfying service requirements. To address these challenges, we formulate a joint optimization problem for model splitting, placement, and chaining (data routing) in the MSL/MSI architecture as an Integer Linear Programming (ILP) model. The objective is to minimize training or inference latency while satisfying the required model execution order and resource constraints. To solve the problem with lower computational cost, we develop a Block Coordinate Descent (BCD)-based algorithm that alternately optimizes (1) model splitting and (2) model placement and chaining. Through extensive evaluation, we quantify the computing-communication tradeoff across mini-batch sizes and service chain lengths and demonstrate that the proposed heuristic achieves comparable latency to the ILP solution with significantly improved scalability. The remainder of this paper is organized as follows. Section II reviews related work. Section III describes the system model of the SFC-based MSL/MSI architecture. Section IV formulates the model splitting, placement, and chaining problem as an ILP model. Section V proposes a heuristic algorithm to efficiently solve the model splitting, placement, and chaining problem. Section VI presents evaluation results. Section VII concludes the paper. II. R ELATED W ORK Numerous studies have addressed resource allocation in model splitting and placement [2]–[5], [10]–[14]. These studies formulate various optimization problems to minimize training/inference latency and energy consumption by optimizing model splitting and placement. However, most existing approaches do not adequately address routing smashed data through the underlying communication network, which is critical in multi-hop environments. Assuming that the model has already been split, Jung et al. formulated an ILP model for model placement and data routing to minimize end-toend latency, including both computation and communication delays, using a layered graph [15]. Xu et al. proposed an
2
optimization framework that jointly optimizes model splitting, placement, and data routing to minimize inference latency [7]. However, their data routing approach relies on selecting from a predetermined set of route candidates. In [16], Sartzetakis et al. formulated a network and computation resource allocation problem for distributed machine learning as an ILP model to optimize monetary cost and accuracy while satisfying resource, accuracy, and latency requirements. In [17], Tajiri et al. proposed a framework for optimizing data and model transfers in federated learning, formulated as a linear programming model to minimize the maximum aggregated data sent to the server. Similarly, in [18], Fan et al. proposed a dynamic virtual network embedding algorithm tailored for distributed training in mobile edge computing. While these studies focus on optimizing either data routing or placement, they do not address the joint optimization of model splitting, placement, and chaining in the context of MSL/MSI. To address these limitations, we formulate the joint optimization of model splitting, placement, and chaining as an ILP problem with the objective of minimizing inference or training latency. The proposed ILP is an extension of our previous work [19], which modeled an SFC and function placement problem as a capacitated shortest path tour problem (CSPTP) using an augmented network model. CSPTP aims at finding the shortest path tour from a source node to a destination node while visiting at least one node from each of the given disjoint node subsets T1 , . . . , T𝐾 in the specified order and satisfying the resource constraints. In [6], we emphasized the similarity between SFC and MSL/MSI and proposed an SFC-based MSL/MSI architecture. In this paper, we extend the CSPTP formulation to jointly optimize model splitting, placement, and chaining in the SFC-based MSL/MSI architecture. III. S YSTEM M ODEL This section introduces the system model of the SFC-based MSL/MSI architecture, as illustrated in Fig. 1. A. Service Chain Request A user’s request for executing a global model 𝑭 is represented as a service chain request (SCR) R = (𝑖𝑑, 𝑠, 𝑑, 𝑏, 𝑚𝑜𝑑𝑒), where 𝑖𝑑 is the identifier of global model 𝑭, 𝑠 is the source node, 𝑑 is the destination node, 𝑏 is the batch size, and 𝑚𝑜𝑑𝑒 ∈ {IF, TR} represents the execution mode, i.e., inference (IF) or training (TR). B. Model Splitting A global model 𝑭 consists of 𝐿 layers (𝐿 = |𝑭|). The system partitions 𝑭 into a sequence of 𝐾 ≥ 2 sub-models, 𝑘 𝑘 𝑘 𝑭 𝑘 (𝑘 = 1, . . . , 𝐾). Each sub-model 𝑭 𝑘 = ( 𝑓 𝑠 , . . . , 𝑓 𝑠 +𝐿 −1 ) 𝐾 ∑︁ contains 𝐿 𝑘 layers, where 𝐿 = 𝐿 𝑘 and 𝐿 𝑘 = |𝑭 𝑘 |. Here, 𝑓 𝑙
Model splitting Layer execution
Activations Layer
1st cut
2nd cut
3
1 2
7 6
11 9 12 10 Model Placement
13
𝑠
5 4
14
𝑣ො1
Gradients Model updates sub-model last cut
𝑣ො2
𝑣ො3
𝑣ො4
𝑣5
𝑣3
𝑣1
8
𝑑 Data routing
𝑣2
Physical network Augmented network
𝑣4
Physical node
Physical link
Forward service path
Imaginary node
Imaginary link
Backward service path
Service Function Chaining and Placement
Fig. 1: System model of SFC-based MSL/MSI.
During the inference phase, only forward computation (propagation) is performed, whereas the training phase involves both forward and backward computation. During the forward computation, given an input matrix X1 , the first sub1 model 𝑭 1 generates the activation matrix Ŷ 𝐿 (step 1 in Fig. 1) and transmits it to the next sub-model 𝑭 2 (step 2 in 𝑘 Fig. 1). Upon receiving the activation X𝑠 from the preceding 𝑘−1 𝑘 sub-model 𝑭 , the sub-model 𝑭 computes the activations 𝑘 𝑘 Ŷ𝑠 +𝐿 −1 (steps 3 and 5 in Fig. 1) and forwards them to the subsequent sub-model 𝑭 𝑘+1 (steps 4 and 6 in Fig. 1). Finally, the last sub-model 𝑭 𝐾 computes the inference result Ŷ 𝐿 (step 7 in Fig. 1). In the backward propagation phase, the last sub-model 𝑭 𝐾 calculates the loss function L ( Ŷ 𝐿 , Y), where Y represents the ground truth matrix. It then computes the gradients, updates the weight parameters (step 8 in Fig. 1), and transmits the gradients to the preceding sub-model 𝑭 𝐾 −1 (step 9 in Fig. 1). Upon receiving the gradients from the succeeding sub-model 𝑭 𝑘+1 , the sub-model 𝑭 𝑘 computes the gradients, updates the weight parameters (steps 10 and 12 in Fig. 1), and transmits the gradients to the preceding sub-model 𝑭 𝑘−1 (steps 11 and 13 in Fig. 1). Finally, the first sub-model 𝑭 1 computes the gradients and updates the weight parameters (step 14 in Fig. 1).
𝑘=1
represents the operation of the 𝑙th layer, and 𝑠 𝑘 indicates the starting layer index of the 𝑘th sub-model 𝑭 𝑘 , with 𝑠1 = 1 and 𝑠 𝑘 = 𝑠 𝑘−1 + 𝐿 𝑘−1 for 𝑘 ≥ 2. In Fig. 1, 𝐾 = 4 and (𝐿 1 , 𝐿 2 , 𝐿 3 , 𝐿 4 ) = (2, 2, 1, 2).
In the model splitting, both the number 𝐾 of sub-models and the split points 𝐿 𝑘 (𝑘 = 1, . . . , 𝐾) must be carefully determined to minimize both computation and communication overheads.
3
C. Physical Network and Augmented Network A physical network is represented as a directed graph G = (V, E), where V denotes the set of physical nodes and E represents the set of physical links. Each physical node 𝑖 ∈ V is equipped with either GPU or CPU resources for data processing. Additionally, each physical node 𝑖 ∈ V has memory and storage capacities denoted as 𝐶𝑖mem and 𝐶𝑖disk , respectively. Each physical link (𝑖, 𝑗) ∈ E is characterized by its uplink (forward-direction) and downlink (backwarddirection) bandwidths, 𝑅𝑖,FW𝑗 and 𝑅𝑖,BW 𝑗 , respectively, as well as its forward-direction and backward-direction propagation BW delays 𝑑𝑖,FW 𝑗 and 𝑑 𝑖, 𝑗 . An augmented network G + = (V + , E + ) is an extension of the physical network, where V + = V∪V̂ and E + = E∪Ê [19]. Here, V̂ and Ê represent sets of imaginary nodes and links, respectively. Each imaginary node 𝑣ˆ 𝑘 ∈ V̂ corresponds to the sub-model 𝑭 𝑘 (𝑘 = 1, . . . , 𝐾). The physical node executing 𝑭 𝑘 is selected from the set V 𝑘 ⊆ V, which represents the candidate nodes capable of hosting the sub-model 𝑭 𝑘 . Links (𝑖, 𝑣ˆ 𝑘 ) and ( 𝑣ˆ 𝑘 , 𝑖) ( 𝑣ˆ 𝑘 ∈ V̂, 𝑖 ∈ V 𝑘 ) are called imaginary links, which represent the possibility of executing 𝑭 𝑘 on physical node 𝑖. Hereafter, we use the notation G (resp. G + ) to refer to the physical (resp. augmented) network including all associated node and link attributes when no confusion arises. In Fig. 1, the imaginary nodes 𝑣ˆ 1 , 𝑣ˆ 2 , 𝑣ˆ 3 , and 𝑣ˆ 4 represent the sub-models 𝑭 1 , 𝑭 2 , 𝑭 3 , and 𝑭 4 , respectively. The imaginary links indicate that 𝑭 1 and 𝑭 4 are deployed on the origin and destination nodes 𝑠 and 𝑑, respectively, and that V 2 = {𝑣 1 , 𝑣 2 } and V 3 = {𝑣 3 , 𝑣 4 }.
IV. I NTEGER L INEAR P ROGRAMMING FOR M ODEL S PLITTING , P LACEMENT, AND C HAINING We formulate the model splitting, placement, and chaining problem PIF (resp. PTR ) for the SFC-based MSI (resp. MSL) architecture as an extension of CSPTP-based ILP [19]: min 𝑇 (𝒙, 𝒚, 𝑏, FW) + I(𝑚𝑜𝑑𝑒 = TR) · 𝑇 (𝒙, 𝒚, 𝑏, BW) +
s.t. 𝑥𝑖,𝑘 𝑗 ∈ {0, 1},
(1)
∀(𝑖, 𝑗) ∈ E , ∀𝑘 ∈ {1, . . . , 𝐾 + 1}, 1 if 𝑖 = 𝑎 𝑘 , ∑︁ ∑︁ 𝑘 𝑘 𝑥 𝑖, 𝑗 − 𝑥 𝑗,𝑖 = −1 if 𝑖 = 𝑏 𝑘 , 𝑗 ∈ V𝑖+ 𝑗 ∈ V𝑖+ 0 otherwise, + ∀𝑖 ∈ V \ {𝑎 𝑘 , 𝑏 𝑘 }, ∀𝑘 ∈ {1, . . . , 𝐾 + 1},
(2)
𝑥𝑖,𝑘 𝑣ˆ 𝑘 = 𝑥 𝑣𝑘+1 ∀(𝑖, 𝑣ˆ 𝑘 ) ∈ E + , ∀𝑘 ∈ {1, . . . , 𝐾 + 1}, ˆ 𝑘 ,𝑖 , 𝑥𝑖,𝑘 𝑣ˆ𝑚 = 0, ∀(𝑖, 𝑣ˆ 𝑚 ) ∈ E + , ∀𝑘 ∈ {1, . . . , 𝐾 + 1},
(4) (5)
𝑦 𝑣ˆ 𝑘 ,𝑙 = {0, 1},
(6)
∀ˆ𝑣 𝑘 ∈ V̂, ∀𝑙 ∈ {1, . . . , 𝐿},
(3)
𝑦 𝑣ˆ1 ,1 = 1,
(7)
𝑦 𝑣ˆ𝐾 ,𝐿 = 1, ∑︁ 𝑦 𝑣ˆ 𝑘 ,𝑙 = 1,
(8) ∀𝑙 ∈ {1, . . . , 𝐿},
(9)
∀ˆ𝑣 𝑘 ∈ V̂,
(10)
𝑣ˆ 𝑘 ∈ V̂ 𝐿 ∑︁
𝑦 𝑣ˆ 𝑘 ,𝑙 ≥ 1,
𝑙=1
𝑦 𝑣ˆ1 ,0 = 0, 𝐿 ∑︁ max(0, 𝑦 𝑣ˆ 𝑘 ,𝑙 − 𝑦 𝑣ˆ 𝑘 ,𝑙−1 ) = 1,
(11) ∀𝑘 ∈ {1, . . . , 𝐾 },
𝑙=𝑘
(12) 𝑦 𝑣ˆ 𝑘 ,𝑙 − 𝑦 𝑣ˆ 𝑘 ,𝑙−1 ≤ 𝑦 𝑣ˆ 𝑘−1 ,𝑙−1 ,
D. Service Path Finding an optimal service path in the augmented network G + corresponds to jointly optimizing model placement and chaining. A service path S is composed of a sequence (S1 , . . . , S𝐾+1 ) of 𝐾 + 1 subpaths. Each 𝑘th subpath S𝑘 connects its source and destination nodes (𝑎 𝑘 , 𝑏 𝑘 ), where 𝑎 𝑘 and 𝑏 𝑘 are defined as follows: the first subpath starts at 𝑠 and ends at 𝑣ˆ 1 , intermediate subpaths connect consecutive imaginary nodes 𝑣ˆ 𝑘−1 and 𝑣ˆ 𝑘 , and the last subpath connects 𝑣ˆ 𝐾 to 𝑑. While the entire service path may include loops, each subpath S𝑘 is loop-free. Selecting an incoming imaginary link (𝑖, 𝑣ˆ 𝑘 ) in the 𝑘th subpath S𝑘 indicates that the sub-model 𝑭 𝑘 is deployed and executed on the physical node 𝑖. The cost of an imaginary link is determined by the forward and backward computation delays, while the cost of a physical link is determined by the activation and gradient transmission delays, as well as the link propagation delay. In the forward computation illustrated in Fig. 1, the forward service path consists of five subpaths: S1 = (𝑠, 𝑣ˆ 1 ), S2 = ( 𝑣ˆ 1 , 𝑠, 𝑣 1 , 𝑣ˆ 2 ), S3 = ( 𝑣ˆ 2 , 𝑣 1 , 𝑣 2 , 𝑣 4 , 𝑣ˆ 3 ), S4 = ( 𝑣ˆ 3 , 𝑣 4 , 𝑑, 𝑣ˆ 4 ), and S5 = ( 𝑣ˆ 4 , 𝑑). Therefore, the sub-models 𝑭 1 , 𝑭 2 , 𝑭 3 , and 𝑭 4 are deployed on the physical nodes 𝑠, 𝑣 1 , 𝑣 4 , and 𝑑, respectively. In the backward computation depicted in Fig. 1, the backward service path is the reverse of the forward one.
∀𝑘 ∈ {2, . . . , 𝐾 }, ∀𝑙 ∈ {2, . . . , 𝐿}, 𝐿 ∑︁ 𝑦 𝑣ˆ 𝑘 ,𝑙 𝑟 𝑙disk ≤ 𝐶𝑖disk , ∀(𝑖, 𝑣ˆ 𝑘 ) ∈ E + , 𝑥𝑖,𝑘 𝑣ˆ 𝑘 𝑥𝑖,𝑘 𝑣ˆ 𝑘
𝑙=1 𝐿 ∑︁
𝑦 𝑣ˆ 𝑘 ,𝑙 𝑟 𝑙mem + 𝑏
𝑙=1
∀(𝑖, 𝑣ˆ 𝑘 ) ∈ E + .
max
𝑙∈ {1,...,𝐿 }, 𝑑𝑖𝑟 ∈𝐷 (𝑚𝑜𝑑𝑒)
(13) (14)
𝑥𝑖,𝑘 𝑣ˆ 𝑘 𝑦 𝑣ˆ 𝑘 ,𝑙 𝛿𝑙𝑑𝑖𝑟 ≤ 𝐶𝑖mem , (15)
Here, there are two kinds of decision variables. Let 𝒙 = [𝑥 𝑖,𝑘 𝑗 ] (𝑘 ∈ {1, . . . , 𝐾 + 1}, (𝑖, 𝑗) ∈ E + ) denote the binary decision variables for model placement and chaining: 1,
𝑥𝑖,𝑘 𝑗 =
0,
if physical/imaginary link (𝑖, 𝑗) is included in the 𝑘th subpath of the service path, otherwise.
Let 𝒚 = [𝑦 𝑣ˆ 𝑘 ,𝑙 ] ( 𝑣ˆ 𝑘 ∈ V̂, 𝑙 ∈ {1, . . . , 𝐿}) denote the binary decision variables for model splitting: ( 1, if the 𝑙th layer is assigned to imaginary node 𝑣ˆ 𝑘 , 𝑦 𝑣ˆ 𝑘 ,𝑙 = 0, otherwise. The difference between PIF and PTR is reflected in the objective function (1), which minimizes the total inference latency 𝑇 (𝒙, 𝒚, IF) = 𝑇 (𝒙, 𝒚, 𝑏, FW) in the inference case or the total training latency 𝑇 (𝒙, 𝒚, TR) = 𝑇 (𝒙, 𝒚, 𝑏, FW) +
𝑇 (𝒙, 𝒚, 𝑏, BW) in the training case. In Eq. (1), I(·) is the indicator function, which equals 1 if the condition is satisfied and 0 otherwise. Here, 𝑇 (𝒙, 𝒚, 𝑏, 𝑑𝑖𝑟) is defined as the sum of the total computation (processing) delay and the total communication delay for the forward (𝑑𝑖𝑟 = FW) or backward (𝑑𝑖𝑟 = BW) direction, which is expressed as follows: ∑︁ comp 𝑇 (𝒙, 𝒚, 𝑏, 𝑑𝑖𝑟) = 𝑥 𝑖,𝑘 𝑣ˆ 𝑘 𝑇𝑖, 𝑣ˆ 𝑘 ( 𝒚, 𝑏, 𝑑𝑖𝑟) (𝑖, 𝑣ˆ 𝑘 ) ∈ Ê
+
∑︁
𝑥 𝑣𝑘+1 ˆ 𝑘 ,𝑚
( 𝑣ˆ 𝑘 ,𝑚) ∈ Ê
∑︁
0011111111111111111111111100000000000 0000000000000000000000000011111111111 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 Layer l
Fig. 2: Relationship between 𝑦 𝑣ˆ 𝑘 ,𝑙 and valid model splitting (𝐾 = 3, 𝐿 = 37).
(𝑖, 𝑗 ) ∈ E
The first term consists of the forward/backward computation comp delay 𝑇𝑖, 𝑣ˆ 𝑘 ( 𝒚, 𝑏, 𝑑𝑖𝑟) for executing a sub-model 𝑭 𝑘 (𝑘 = 1, . . . , 𝐾) at a physical node 𝑖, which is defined as comp
𝑇𝑖, 𝑣ˆ 𝑘 ( 𝒚, 𝑏, 𝑑𝑖𝑟) = 𝜅𝑖 (𝑏, 𝜙 𝑣ˆ 𝑘 ( 𝒚, 𝝆 𝑑𝑖𝑟 )) + 𝜏𝑖 (𝑏).
(17)
Recall 𝑏 denotes the batch size. 𝝆 𝑑𝑖𝑟 = [𝜌1𝑑𝑖𝑟 , . . . , 𝜌 𝐿𝑑𝑖𝑟 ] represents the vector of Floating-point Operations (FLOPs), which are required for the forward (𝑑𝑖𝑟 = FW) or backward (𝑑𝑖𝑟 = BW) computation of each layer. 𝜅 𝑖 () and 𝜏𝑖 () are defined as linear functions that derive the computing time for executing a sub-model 𝑭 𝑘 at physical node 𝑖 and that output a GPU I/O overhead of physical node 𝑖, respectively: 𝜅 𝑖 (𝑏, 𝜙) = (𝛼 𝜅 · 𝑏 + 𝛽 𝜅 ) · 𝜙,
𝜏𝑖 (𝑏) = 𝛼 𝜏 · 𝑏 + 𝛽 𝜏 .
Here, 𝛼 𝜅 , 𝛽 𝜅 , 𝛼 𝜏 , and 𝛽 𝜏 are constant values, which would be fitted by ordinary least squares (OLS) using actual measurements of computing nodes. In case of the CPU node, 𝜏𝑖 (𝑏) is always 0, so 𝛼 𝜏 = 𝛽 𝜏 = 0. The forward/backward computation workload 𝜙 𝑣ˆ 𝑘 ( 𝒚, 𝝆 𝑑𝑖𝑟 ) is the workload to execute the assigned layers: 𝑑𝑖𝑟
)=
𝐿 ∑︁
𝑦 𝑣ˆ 𝑘 ,𝑙 𝜌𝑙𝑑𝑖𝑟 .
𝑙=1
The total forward (resp. backward) communication delay consists of the total activation (resp. gradient) transmission delay and the total forward-direction (resp. backward-direction) link propagation delay. The total activation/gradient transmission delay consists of the activation/gradient transmission delay 𝑇𝑖,trans 𝑗, 𝑣ˆ 𝑘 ( 𝒚, 𝑏, 𝑑𝑖𝑟) between link (𝑖, 𝑗) in the (𝑘 + 1)th subpath (𝑘 = 1, . . . , 𝐾), which is defined as 𝑇𝑖,trans 𝑗, 𝑣ˆ 𝑘 ( 𝒚, 𝑏, 𝑑𝑖𝑟) =
𝑏𝜓 𝑣ˆ 𝑘 ( 𝒚, 𝜹 𝑑𝑖𝑟 )
,
𝑅𝑖,𝑑𝑖𝑟𝑗
(18)
where 𝜹 𝑑𝑖𝑟 = [𝛿1𝑑𝑖𝑟 , . . . , 𝛿 𝑑𝑖𝑟 𝐿−1 ] represents the vector of the activation/gradient size of each layer in bytes, and 𝑅𝑖,𝑑𝑖𝑟𝑗 denotes the forward-direction/backward-direction bandwidth of physical link (𝑖, 𝑗). Let 𝜓 𝑣ˆ 𝑘 ( 𝒚, 𝜹 𝑑𝑖𝑟 ) denotes the activation/gradient size of 𝑘th sub-model: 𝜓 𝑣ˆ 𝑘 ( 𝒚, 𝜹 𝑑𝑖𝑟 ) =
01100000000000000000000000000000000000
trans 𝑑𝑖𝑟 𝑥𝑖,𝑘+1 𝑗 𝑇𝑖, 𝑗, 𝑣ˆ 𝑘 ( 𝒚, 𝑏, 𝑑𝑖𝑟) + 𝑑 𝑖, 𝑗 (16)
𝜙 𝑣ˆ 𝑘 ( 𝒚, 𝝆
Sub-model k v̂3 v̂2 v̂1
4
𝐿−1 ∑︁
𝑦 𝑣ˆ 𝑘 ,𝑙 (1 − 𝑦 𝑣ˆ 𝑘 ,𝑙+1 )𝛿𝑙𝑑𝑖𝑟 .
𝑙=1
The total forward-direction/backward-direction link propagation delay consists of the forward-direction/backwarddirection link propagation delay 𝑑𝑖,𝑑𝑖𝑟𝑗 of link (𝑖, 𝑗) in the (𝑘 + 1)th subpath (𝑘 = 1, . . . , 𝐾).
Constraints (2)–(5) are associated with model placement and chaining, which are the same as those in the CSPTP-based ILP by regarding functions as models. Constraint (2) represents the binary decision variables. Constraint (3) ensures the flow conservation rules of the service path, where V𝑖+ denotes a set of neighbor nodes of 𝑖. Constraint (4) guarantees the connectivity between the 𝑘th and 𝑘 + 1th subpaths. Constraint (5) prohibits the service path from traversing the imaginary node 𝑣ˆ 𝑚 in the 𝑘th subpath (𝑚 ≠ 𝑘). The remaining constraints (6)–(15) are newly added or modified to the CSPTP-based ILP. Constraints (6)–(13) ensure the valid model splitting. Fig. 2 illustrates the relationship between 𝑦 𝑣ˆ 𝑘 ,𝑙 and valid model splitting for 𝐾 = 3 and 𝐿 = 37. Constraint (6) represents the binary decision variables. Constraints (7) and (8) ensure that the first and last layers are assigned to the first imaginary node 𝑣ˆ 1 and the last imaginary node 𝑣ˆ 𝐾 , respectively. Constraint (9) ensures that each layer is always assigned to one imaginary node. Constraint (10) guarantees that each imaginary node executes at least one layer. Under the definition of the dummy variable 𝑦 𝑣ˆ1 ,0 = 0 in constraint (11), constraint (12) guarantees that the layers assigned to each sub-model are contiguous. As illustrated in Fig. 2, for each 𝑘, the values of 𝑦 𝑣ˆ 𝑘 ,𝑙 must start at 0 for layers unassigned to sub-model 𝐹 𝑘 , transition to 1 for the consecutive layers assigned to sub-model 𝐹 𝑘 , and revert to 0 for the remaining layers. In this scenario, max(0, 𝑦 𝑣ˆ 𝑘 ,𝑙 − 𝑦 𝑣ˆ 𝑘 ,𝑙−1 ) in the left-hand side of constraint (12) evaluates to 1 only at the layer 𝑙 where the assignment to sub-model 𝐹 𝑘 begins, and 0 elsewhere. The sum of these values is constrained to equal 1. To ensure that the layers assigned to consecutive sub-models 𝐹 𝑘−1 and 𝐹 𝑘 are sequentially ordered, the relationship 𝑦 𝑣ˆ 𝑘−1 ,𝑙−1 = 1, 𝑦 𝑣ˆ 𝑘 ,𝑙−1 = 0, and 𝑦 𝑣ˆ 𝑘 ,𝑙 = 1 must hold at the first layer 𝑙 assigned to sub-model 𝐹 𝑘 . For instance, in Fig. 2, this corresponds to 𝑦 𝑣ˆ1 ,2 = 1, 𝑦 𝑣ˆ2 ,2 = 0, and 𝑦 𝑣ˆ2 ,3 = 1. Here, the left-hand side of constraint (13) evaluates to 0 until the assignment to sub-model 𝐹 𝑘 begins, becomes 1 at the first assigned layer, remains 0 until the last assigned layer, evaluates to −1 at the next layer, and then reverts to 0. Therefore, the combination of constraint (12) and constraint (13) guarantees that the layers assigned to consecutive sub-models are sequentially ordered. Constraint (14) ensures that the total size of the layers assigned to the sub-model 𝑭 𝑘 does not exceed the storage capacity 𝐶𝑖disk of the physical node 𝑖 executing 𝑭 𝑘 , where 𝑟 𝑙disk represents the disk size required to store the 𝑙th layer. Constraint (15) enforces the memory capacity constraint, where 𝑟 𝑙mem denotes the memory size required for the 𝑙th layer, and 𝐶𝑖mem represents the memory capacity of physical node
5
Algorithm 1 BCD-based heuristic algorithm.
Algorithm 2 𝐾-Sequence Segmentation via DP.
Require: 𝑘=1,...,𝐾 , 𝝆, 𝜹, 𝜀. Ensure: 𝒙∗ , 𝒚 ∗ . 1: 𝑡 ← 0 2: Initialize 𝒚 0 3: G + ← AUGMENTED N ETWORK ( G, R, 𝒚 0 , { V 𝑘 } 𝑘=1,...,𝐾 , 𝝆, 𝜹) 4: 𝒙0 ← DFTS ( G + , 𝑠, 𝑑) 5: repeat 6: 𝑡 ←𝑡 +1 7: 𝒚 𝑡 ← K-S EQUENCE -S EGMENTATION ( 𝒙𝑡 −1 , R, G + , 𝐿, 𝝆, 𝜹) 8: G + ← AUGMENTED N ETWORK ( G, 𝒚 𝑡 , R, { V 𝑘 } 𝑘=1,...,𝐾 , 𝝆, 𝜹) 9: 𝒙𝑡 ← DFTS ( G + , 𝑠, 𝑑) 10: until |𝑇 ( 𝒙𝑡 , 𝒚 𝑡 , 𝑚𝑜𝑑𝑒) − 𝑇 ( 𝒙𝑡 −1 , 𝒚 𝑡 −1 , 𝑚𝑜𝑑𝑒) | ≤ 𝜀
Require: 𝒙𝑡 −1 , R = (𝑖𝑑, 𝑠, 𝑑, 𝑏, 𝑚𝑜𝑑𝑒) , G + , 𝐿, 𝝆, 𝜹. Ensure: 𝒚 𝑡 . 1: for 𝑙 ∈ {1, . . . , 𝐿 − 𝐾 } do 2: 𝑑 𝑝1,𝑙 ← 𝑇 ( 𝒙1𝑡 −1 , 111,𝑙,𝐿 , 𝑏, 𝑚𝑜𝑑𝑒)
R = (𝑖𝑑, 𝑠, 𝑑, 𝑏, 𝑚𝑜𝑑𝑒) , G, 𝐿, { V 𝑘 }
𝑖. This constraint is similar to the storage constraint (14). However, during batch processing, activations or gradients must be temporarily stored in memory for each layer in the sub-model 𝑭 𝑘 . The maximum size of these temporary data is represented by the second term on the left-hand side. Here, 𝐷 (𝑚𝑜𝑑𝑒) is defined as {FW, BW} for 𝑚𝑜𝑑𝑒 = TR, and as {FW} otherwise. In practical scenarios, the memory constraint (15) is often more stringent than the storage constraint (14), as storage systems typically employ compressed formats for model storage and incur lower costs per byte. In practical scenarios, the memory constraint (15) is typically more restrictive than the storage constraint (14), as storage systems often utilize compressed formarts for model strage and incur lower costs per byte. Although the objective function (1), constraints (12), (15), and (14) are non-linear, due to the product of two or more binary decision variables and the max operator, these can be linearized using existing techniques [20]. V. B LOCK C OORDINATE D ESCENT-BASED H EURISTIC A LGORITHM A. Overview To solve the proposed ILP more efficiently, we propose a heuristic algorithm based on the block coordinate descent (BCD) method [21]. The algorithm decomposes the primary problem PIF or PTR into two subproblems: (1) model splitting and (2) model placement and chaining. It then iteratively optimizes these subproblems until convergence. Algorithm 1 outlines the BCD-based heuristic algorithm. For solving PIF , the vectors 𝝆 and 𝜹 are set as 𝝆 FW and 𝜹FW , respectively. For solving PTR , 𝝆 and 𝜹 are set as ( 𝝆 FW , 𝝆 BW ) and (𝜹FW , 𝜹BW ), respectively. In the initialization phase (lines 1–4), the iteration counter 𝑡 is initialized to zero. The initial model splitting 𝒚 0 is determined by evenly dividing the global model into 𝐾 layers. The augmented network 𝐺 + is then constructed based on the physical network 𝐺, the service chain request R, 𝒚 0 , the placement candidates {V 𝑘 } 𝑘=1,...,𝐾 , and the vectors 𝝆 and 𝜹 by invoking the AUGMENTED N ETWORK () function. Using the augmented network 𝐺 + , the source node 𝑠, and the destination node 𝑑, the initial model placement and chaining 𝒙 0 is derived using the depth-first tour search (DFTS) algorithm [22] (i.e., the DFTS() function), which identifies the shortest path tour from 𝑠 to 𝑑.
3: for 𝑘 ∈ {2, . . . , 𝐾 } do 4: if 𝑘 < 𝐾 then 5: L ′ ← { 𝑘, . . . , 𝐿 − 𝐾 − 𝑘 + 2} 6: else 7: L′ ← { 𝐿 } ⊲ The last segment must include the last layer 8: for 𝑙 ∈ L ′ do 9: for 𝑙 ′ ∈ { 𝑘 − 1, . . . 𝑙 − 1} do 10: 𝑑 𝑝𝑘,𝑙 ← min(𝑑 𝑝𝑘,𝑙 , 𝑑 𝑝𝑘−1,𝑙 ′ + 𝑇 ( 𝒙𝑡𝑘−1 , 1𝑙𝑘′ ,𝑙,𝐿 , 𝑏, 𝑚𝑜𝑑𝑒) )
During each iteration (lines 5–10), the algorithm alternates between optimizing 𝒚 𝑡 and 𝒙 𝑡 . First, 𝑡 is incremented by one (line 6). The model splitting 𝒚 𝑡 is optimized using the 𝐾sequence segmentation algorithm via dynamic programming (DP) [23] (i.e., the K-S EQUENCE -S EGMENTATION () function) for the given model placement and chaining 𝒙 𝑡 −1 , R, the vectors 𝝆 and 𝜹, and the number 𝐿 of layers (line 7). Next, the model placement and chaining 𝒙 𝑡 is optimized using the DFTS algorithm for the updated model splitting 𝒚 𝑡 (line 9). If the difference between the objective function values at iterations 𝑡 and 𝑡 − 1 is less than or equal to the convergence tolerance 𝜀 ≥ 0 (line 10), the algorithm terminates and outputs the final solutions 𝒙 ∗ and 𝒚 ∗ . B. 𝐾-Sequence Segmentation via Dynamic Programming 𝐾-sequence segmentation [23] aims at dividing a sequence of length 𝐿 into 𝐾 segments to minimize the total cost of the segments. In our problem, the sequence and segments correspond to the layers of the global model and the sub-models, respectively. Algorithm 2 shows the 𝐾-sequence segmentation via DP to optimize the model splitting 𝒚 𝑡 for a given model placement and chaining 𝒙 (𝑡 −1) . The recurrence relation 𝑑𝑝 𝑘,𝑙 for solving the 𝐾-sequence segmentation problem via DP is defined as follows: 𝑑𝑝 𝑘,𝑙 = min (𝑑𝑝 𝑘−1,𝑙 ′ + 𝑇 (𝒙 𝑘 , 1𝑙𝑘′ ,𝑙,𝐿 , 𝑏, 𝑚𝑜𝑑𝑒)). ′ 1≤𝑙 <𝑙
Here, 𝒙 𝑘 = [𝑥𝑖,𝑘 𝑗 ] (𝑖, 𝑗 ∈ E + ) determines 𝑘th subpath S𝑘 (𝑘 = 1, . . . , 𝐾). Let 1𝑙𝑘′ ,𝑙,𝐿 denote a binary vector of length 𝐿, which has 1s from the 𝑙 ′ th to the (𝑙 − 1)th elements 𝑘 and 0s elsewhere (1 ≤ 𝑙 ′ < 𝑙 ≤ 𝐿). For example, 12,4,5 = [0, 1, 1, 0, 0] indicates that layers 2, 3 are assigned to the 𝑘th sub-model. 1𝑙𝑘′ ,𝑙,𝐿 can be viewed as a specific instance of 𝒚 𝑣ˆ 𝑘 = [𝑦 𝑣ˆ 𝑘 ,1 , . . . , 𝑦 𝑣ˆ 𝑘 ,𝐿 ], i.e., assignment of layers to the 𝑘th sub-model. 𝑇 (𝒙 𝑡𝑘−1 , 1𝑙𝑘′ ,𝑙,𝐿 , 𝑏, 𝑚𝑜𝑑𝑒) indicates the total latency of executing the 𝑘th sub-model with the layer assignment 1𝑙𝑘′ ,𝑙,𝐿 and the model placement and chaining 𝒙 𝑡𝑘−1 . Note that this value is set to infinity if the storage or memory capacity constraints of physical node 𝑖 are violated. In lines 1–2, 𝑑𝑝 1,𝑙 is initialized for the first segment. In lines 3–10, the algorithm iteratively minimizes the cost 𝑑𝑝 𝑘,𝑙 by evaluating all feasible values of 𝑙 for each segment 𝑘, processing sequentially from 𝑘 = 2 to 𝐾. Finally, the algorithm derives the optimal solution 𝒚 by backtracking from 𝑑𝑝 𝐾 ,𝐿 .
6
comp
𝑐 𝑖,𝑘 𝑣ˆ𝑖,𝑘 = 𝑇𝑖, 𝑣ˆ𝑖,𝑘 ( 𝒚, 𝑏, FW) comp
+ I(𝑚𝑜𝑑𝑒 = TR) · 𝑇𝑖, 𝑣ˆ𝑖,𝑘 ( 𝒚, 𝑏, BW). If the storage or memory capacity constraints of physical node 𝑖 are violated, the corresponding imaginary link is not created. By applying the DFTS algorithm to the modified augmented network G + , along with the source node 𝑠 and destination node 𝑑, we can derive the shortest path tour and the model placement results (i.e., 𝒙). D. Computational Complexity and Convergence Property We first evaluate the computational complexity of the BCD-based heuristic algorithm. The computational complexity of the DFTS algorithm is O ((𝐾 + 1)𝑉 + ) + O ((𝐾 + 1)𝐸 + log 𝑉 + ) [24], where the first term represents the complexity of calculating the minimum cost for each subpath, and the second term corresponds to the complexity of the Dijkstra algorithm for determining the entire shortest path. The computational complexity of the 𝐾-sequence segmentation via DP is O (𝐾 𝐿 2 ) [23]. Assuming that the DFTS algorithm and the 𝐾-sequence segmentation algorithm are invoked at most 𝑇max +1 and 𝑇max times, respectively, the overall computational complexity of the BCD algorithm is O (𝑇max 𝐾 𝐿 2 ) + O ((𝑇max + 1)(𝐾 + 1)𝑉 + ) + O ((𝑇max + 1) (𝐾 + 1)𝐸 + log 𝑉 + ). In theory, BCD algorithms are not guaranteed to converge to a global optimal solution for ILP problems due to a nonconvex nature [25]. However, it is well-known that the BCD algorithm often converges to a good solution in practice [3]. 1 For simplicity of notation, we use the same symbol G + as the original augmented network, provided there is no risk of confusion.
v10 v9 v8 3.50 v11 v12 v13 4.2
0
v1 3.
47
6
9.8
26
where 𝑣ˆ 𝑚,𝑘 ∈ V̂ is the imaginary node connected to the physical node 𝑚 that holds the 𝑘th sub-model 𝑭 𝑘 . The link cost 𝑐 𝑖,𝑘 𝑣ˆ𝑖,𝑘 of an imaginary link (𝑖, 𝑣ˆ 𝑖,𝑘 ) for forward/backward computation is defined as:
4.79
11.7 7 v7 3.58
v5 3.6
7.
BW + I(𝑚𝑜𝑑𝑒 = TR) · 𝑇𝑖,trans 𝑗, 𝑣ˆ𝑚,𝑘−1 ( 𝒚, 𝑏, BW) + 𝑑 𝑖, 𝑗 ,
v4 2.83
8.56
FW 𝑐 𝑖,𝑘 𝑗 = 𝑇𝑖,trans 𝑗, 𝑣ˆ𝑚,𝑘−1 ( 𝒚, 𝑏, FW) + 𝑑 𝑖, 𝑗
BW FW BW dFW 9,10 = d9,10 = 2.98 , d10,13 = d10,13 = 1.93 BW FW BW dFW 9,12 = d9,12 = 3.94 , d11,12 = d11,12 = 2.26 BW FW BW dFW 10,11 = d10,11 = 1.83 , d12,13 = d12,13 = 1.23 14.2
v2
5.65
C. Shortest Path Tour Finding To optimize the model placement and chaining 𝒙, we use the DFTS algorithm [22], which identifies the shortest path tour from the source node 𝑠 to the destination node 𝑑 while ensuring that all imaginary nodes 𝑣ˆ 𝑘 ∈ V̂ are visited in the required order. Inspired by our previous work on the VNF placement and chaining problem [24], we construct a modified augmented network G + from the physical network G, utilizing a given 𝒚 to ensure connectivity between the 𝑘th and 𝑘 + 1th subpaths in the DFTS algorithm.1 This modified augmented network G + differs slightly from the original augmented network described in Section III-C. In the modified augmented network G + , the set of imaginary nodes is updated as V̂ = { 𝑣ˆ 𝑖,𝑘 }𝑖 ∈ V 𝑘 ,𝑘 ∈ {1,...,𝐾 } , where each imaginary node 𝑣ˆ 𝑖,𝑘 represents a pair of a placement candidate physical node 𝑖 ∈ V 𝑘 and the split sub-model 𝑭 𝑘 . The corresponding imaginary links are also updated as {( 𝑣ˆ 𝑖,𝑘 , 𝑖)}𝑖 ∈ V 𝑘 ,𝑘 ∈ {1,...,𝐾 } and {(𝑖, 𝑣ˆ 𝑖,𝑘 )}𝑖 ∈ V 𝑘 ,𝑘 ∈ {1,...,𝐾 } . The link cost 𝑐 𝑖,𝑘 𝑗 of physical link (𝑖, 𝑗) in the 𝑘th subpath for forward/backward communication is defined as:
v3
v14
5.64
10.5
v6
Fig. 3: NSFNET topology [26].
VI. E VALUATION A. Evaluation Settings The evaluation is conducted on a server equipped with a 36core Intel(R) Core(TM) i9-10980XE CPU and 128 GB RAM. 1) Model Settings: ResNet101 [27] is adopted as the global model 𝑭. Table I presents the specifications of the ResNet101 model. To balance the modularity and granularity of submodels, each building block is treated as a layer, resulting in 𝐿 = 37. The ImageNet dataset [28] is used, with input and output dimensions of 3 × 224 × 224 and 1,000, respectively. Multiply-accumulate operations (MACs) and the output dimension of each layer are measured using the PyTorch library [29]. Forward-computation FLOPs are calculated as twice the MACs, while backward-computation FLOPs are determined as twice the forward-computation FLOPs. The sizes of activation and gradient data, collectively referred to as smashed data, are calculated based on the output dimensions of each building block, assuming 32-bit floating-point representation for each element. The memory size 𝑟 𝑙mem of each layer 𝑙 (𝑙 = 1, . . . , 𝐿) is calculated based on the number of parameters represented as 32-bit floating-point numbers. For simplicity, it is assumed that the memory size and storage size of each layer 𝑙 are identical (𝑟 𝑙mem = 𝑟 𝑙disk ). In the ResNet101 model, Table I reveals the following key characteristics: (C1) Computational costs are substantially higher in the middle layers (layers 3–35); (C2) The smashed data size monotonically decreases as the layers progress, with the exception of the second layer; and (C3) The layer size tends to increase as the layers progress, except for the second layer and the last two layers. 2) Network Settings: The NSFNET topology [26] shown in Fig. 3, consisting of 14 nodes and 42 directed links, is used as the physical network. Each physical link has a bandwidth of 1 Gbps. The link propagation delays are calculated based on the distance and the speed of light in optical fibers, with values ranging from 1.23 ms to 14.2 ms. Each physical node is equipped with available computing resources, as summarized in Table II. To estimate the parameters 𝛼 𝜅 , 𝛽 𝜅 , 𝛼 𝜏 , and 𝛽 𝜏 , the computation time of ResNet101 is measured while varying the input batch size 𝑏 from 1 to 256. Each measurement is repeated 110 times, with the first 10 trials discarded as warmup. Assuming that computation time scales linearly with 𝑏, the measurements are fitted to an OLS linear model to obtain the
7
TABLE I: Model specification of ResNet101 [27] (3 × 224 × 224-dimension input with 𝑏 = 1). Building block
Building block name
Computational cost (FLOPs)
(Layer) id 𝑙
Smashed data size (bytes)
Layer size (bytes)
Forward 𝜌𝑙FW
Backward 𝜌𝑙BW
Activation 𝛿𝑙FW
Gradient 𝛿𝑙BW
𝑟𝑙mem , 𝑟𝑙disk
1
conv1
236.02 M
472.04 M
3.21 M
3.21 M
37 K
2
conv2_x (batchnorm, relu, maxpool)
6.43 M
12.9 M
0.80 M
0.80 M
512
3
conv2_x
4.74 G
9.48 G
3.21 M
3.21 M
3.02 M
4,5
conv2_x
7.40 G
14.80 G
3.21 M
3.21 M
4.72 M
6
conv3_x
5.76 G
11.52 G
1.61 M
1.61 M
14.68 M
7–9
conv3_x
7.40 G
14.80 G
1.61 M
1.61 M
18.88 M
10
conv4_x
5.76 G
11.52 G
0.80 M
0.80 M
58.76 M
11–32
conv4_x
7.40 G
14.80 G
0.80 M
0.80 M
75.52 M
33
conv5_x
5.76 G
11.52 G
0.40 M
0.40 M
234.92 M
34-35
conv5_x
7.40 G
14.80 G
0.40 M
0.40 M
302.04 M
36
avgpool
200.70 K
401.40 K
8192
8192
0
37
fc
4.10 M
8.20 M
4000
4000
8.20 M
TABLE II: Computing nodes’ specifications. Node type
CPU Intel(R) Xeon(R) Gold 6226R
GPU NVIDIA RTX A6000
𝛼𝜅
1.04 × 10 −10 if 𝑏 ≤ 8 2.07 × 10 −10 if 𝑏 > 8 3.74 × 10 −11 if 𝑏 ≤ 8 −1.60 × 10 −9 if 𝑏 > 8 0 0
3.94 × 10 −12
𝛽𝜅 𝛼𝜏 𝛽𝜏
1.72 × 10 −11 2.07 × 10 −13 1.69 × 10 −13
parameters. Because the CPU case exhibits different behavior for 𝑏 ≤ 8 and 𝑏 > 8, the parameters 𝛼 𝜅 and 𝛽 𝜅 are estimated separately for these two ranges. Each sub-model 𝑭 𝑘 , except the first and last sub-models, has a candidate set V 𝑘 of physical nodes for placement, which is randomly and distinctly selected from the physical nodes, where |V 𝑘 | = 2. The source node 𝑠 is constrained by resource limitations to operate solely with a CPU, categorizing it a CPU node, while all other nodes are equipped with GPUs, classifying them as GPU nodes. Table II summarizes the specifications of the computing nodes. The available memory and storage capacities of these GPU nodes are set to 2 GB each, while those of the CPU node are set to 8 GB. The first and last sub-models are always placed on the source and destination nodes, respectively. 3) Schemes for Evaluation: First, the proposed ILPs (PIF and PTR ), solved using the Gurobi solver 12.3 [30], are employed to analyze the characteristics of the optimal solutions. Subsequently, the solution quality and computational efficiency of the proposed BCD algorithm are assessed, where the algorithm is implemented in Python 3.12 using the NetworkX library [31]. Finally, to verify the importance of jointly optimizing model splitting, placement, and chaining, two comparison schemes are introduced: Computationoriented model splitting (COMP-MS) and communicationoriented model splitting (COMM-MS). Both schemes adopt a two-step ILP approach to solve the model splitting, placement, and chaining problem. In the first step, the ILP optimizes model splitting to minimize either computation or commu-
nication overhead without considering model placement and chaining. In the second step, the ILP corresponds to the problem P based on the optimized model splitting 𝒚 ∗ obtained from the first step. 4) Evaluation Metrics: The inference and training latencies per batch are evaluated as the primary metrics. Additionally, the execution time is measured to assess scalability, where the execution time is defined as the duration required to solve the model splitting, placement, and chaining problem. If the execution time exceeds the predefined limit of 1,000 seconds, the process is terminated, and the result is considered infeasible. All measurements are conducted 10 times, and the average values are reported. B. Fundamental Characteristics of Optimal Solutions We first analyze the fundamental characteristics of optimal solutions derived from the ILP. Figs. 4a and 5a illustrate the inference and training latencies per batch, respectively, for the service chain length 𝐾 ranging from 2 to 7 in increments of 1, and the batch size 𝑏 ranging from 1 to 256 in powers of 2. When focusing on 𝑏, we observe relatively simple trends. As 𝑏 increases, both computation and transmission delays grow, leading to a general increase in inference and training latencies, regardless of 𝐾. Additionally, since MSI involves only forwarding processing and communication, while MSL requires bidirectional processing and communication, the inference latency is approximately half of the training latency. On the other hand, more complex trends are observed with respect to 𝐾. For lightweight tasks such as MSI with 𝑏 ≤ 2, the optimal configuration is 𝐾 = 2, which corresponds to the traditional client-server model splitting approach. In contrast, for heavier tasks such as MSI with 𝑏 ≥ 4 or MSL, the inference and training latencies are minimized at 𝐾 = 3. Beyond this point, an increase in 𝐾 leads to a trend of increasing latency. Generally, increasing 𝐾 reduces the computation delay by distributing more computation across GPU nodes. However, it also increases the communication delay due to the higher number of smashed data transmissions between sub-models. This not only increases the total propagation delay but also has
8
0.20
0.19
0.20
0.25
0.32
0.36
30
0.11
0.11
0.12
0.15
0.19
0.21
20
0.06
0.07
0.07
0.09
0.12
0.13
0.04
0.05
0.05
0.07
0.08
0.09
2
3
4
5
6
Batch size b
Inference latency [s]
1.26
50
0.38
0.36
0.38
0.45
0.59
0.66
40
0.20
0.19
0.20
0.25
0.32
0.36
30
0.11
0.11
0.12
0.15
0.19
0.21
20
0.06
0.07
0.07
0.09
0.12
0.13
0.04
0.05
0.05
0.07
0.08
0.09
1
10 0
7
2
Service chain length K
3
4
5
6
7.39
9.39
1.01
1.81
2.37
1.74
3.72
4.73
50
0.41
0.92
1.20
0.89
2.00
2.50
40
0.21
0.47
0.62
0.47
1.03
1.28
30
0.11
0.25
0.33
0.26
0.54
0.67
20
0.06
0.14
0.18
0.15
0.29
0.35
0.04
0.08
0.10
0.10
0.17
0.21
10 0
7
2
Service chain length K
(a) ILP.
(b) BCD.
3
4
5
6
60
5.93
6.43
6.96
7.51
9.03
7.04
2.78
3.06
3.31
3.60
4.36
3.48
1.20
1.36
1.49
1.64
2.03
2.27
50
0.42
0.50
0.58
0.66
0.87
1.00
40
0.21
0.26
0.31
0.35
0.46
0.53
30
0.12
0.15
0.17
0.20
0.26
0.30
20
0.07
0.09
0.10
0.12
0.15
0.18
0.04
0.06
0.07
0.08
0.10
0.12
3
4
5
6
7
10 0
7
2
Service chain length K
Service chain length K
(c) COMP-MS.
(d) COMM-MS.
70 60
Inference latency [s]
40
1.14
3.44
64 128 256
0.66
0.88
5.20
32
0.59
0.75
3.59
16
0.45
0.73
2.18
12.22 13.27 14.24 15.34 18.35 14.17
8
0.38
1.00
60
Batch size b
0.36
2.45
70
4
16
0.38
2.24
7.15 10.37 6.84 14.72 19.54
2
50
1.71
4.71
1
1.26
1.47
9.97 14.28 20.71 13.63 29.39 39.03
Inference latency [s]
1.14
1.45
64 128 256
0.88
2.18
70
32
0.75
4.84
16
0.73
9.63
4.42
8
32
1.00
60
8.79
3.38
Batch size b
2.45
6.72
2.91
4
2.24
5.79
2.88
2
1.71
5.73
4.71
1
1.47
9.97
Inference latency [s]
1.45
64 128 256
2.18
70
32
4.84
16
9.63
4.42
8
8.79
3.38
4
6.72
2.91
2
64 128 256
5.79
2.88
4
Batch size b
5.73
4.71
1
9.97
2
8
10 0
0.41
0.43
0.52
0.66
0.73
30
0.28
0.23
0.25
0.30
0.38
0.42
20
0.16
0.14
0.16
0.19
0.24
0.27
0.10
0.10
0.11
0.14
0.17
0.19
2
3
4
5
6
Batch size b
Training latency [s]
1.00
0.77
0.80
0.94
1.21
1.33
40
0.52
0.41
0.43
0.52
0.66
0.73
30
0.28
0.23
0.25
0.30
0.38
0.42
20
0.16
0.14
0.16
0.19
0.24
0.27
0.10
0.10
0.11
0.14
0.17
0.19
1
10 0
7
2
Service chain length K
3
4
5
6
2.60
3.65
4.78
3.52
7.48
9.49
50
1.00
1.86
2.42
1.81
3.80
4.81
40
0.52
0.96
1.25
0.95
1.96
2.47
30
0.28
0.51
0.66
0.52
1.09
1.35
20
0.16
0.28
0.36
0.30
0.61
0.74
0.10
0.17
0.21
0.20
0.36
0.43
10 0
7
2
Service chain length K
(a) ILP.
(b) BCD.
3
4
5
6
9.22
9.79 11.25 8.05
3.60
3.87
4.10
4.40
5.16
5.60
50
1.24
1.40
1.55
1.71
2.11
2.35
40
0.63
0.73
0.81
0.90
1.11
1.24
30
0.34
0.40
0.44
0.50
0.61
0.69
20
0.19
0.23
0.26
0.30
0.36
0.40
0.12
0.15
0.17
0.20
0.24
0.26
3
4
5
6
7
10 0
7
70
17.75 18.53 19.45 20.56 23.45 16.41
2
Service chain length K
Service chain length K
(c) COMP-MS.
(d) COMM-MS.
60
Training latency [s]
8
0.52
50
64 128 256
40
2.55
8.79
32
1.33
2.32
8.31
16
1.21
1.79
60
8
0.94
1.54
7.25 10.47 6.95 14.85 18.85
4
0.80
1.51
5.71
2
0.77
2.60
60
36.61 38.33 39.91 42.10 47.84 33.14
1
16
1.00
4.97
Batch size b
50
4.54
70
12.47 14.44 20.87 13.80 29.58 39.22
Training latency [s]
2.55
3.49
64 128 256
2.32
3.01
32
1.79
2.97
26.61 28.81 41.67 27.51 59.04 78.31
16
1.54
5.71
70
8
1.51
9.82
4
32
2.60
60
8.97
2
4.97
6.89
1
4.54
5.95
Batch size b
3.49
12.47 5.88
Training latency [s]
3.01
64 128 256
2.97
26.61 11.71 11.83 13.70 17.83 19.51
32
5.71
70
16
9.82
8
8.97
4
6.89
2
64 128 256
5.95
4
Batch size b
12.47 5.88
1
26.61 11.71 11.83 13.70 17.83 19.51
2
Fig. 4: Inference latency per batch.
10 0
Fig. 5: Training latency per batch. 25.7 ms+6.5 ms 524.3 us+10.6 ms 1–17 (b × 0.80 MB) 18–36 (b × 8192 B) 37 v̂1 v̂2 v̂3 v2
v1
102.8 ms+6.5 ms 38.5 ms+20.8 ms 1 (b × 3.21 MB) 2–17 (b × 0.80 MB) 18–37 v̂1 v̂2 v̂3
25.7 ms+6.5 ms 524.3 us+10.6 ms 1–17 (b × 0.80 MB) 18–36 (b × 8192 B) 37 v̂1 v̂2 v̂3
v2
v2
v4 8.5% 25.7 ms
v5
v7 98.7% 3.4 ms
v9 v8
v14
v3
v10 v11 v12 v13 0.4% 138.3 us
S1 S2
v6
v1
v4 8.5% 25.7 ms
v5
v7 98.7% 3.4 ms
v9 v8
v14
v3
S3 S4
12.8 ms+6.5 ms 524.3 us+10.6 ms 1–34 (b × 0.40 MB) 35–36 (b × 8192 B) 37 v̂1 v̂2 v̂3
S1 S2
v6
(a) ILP.
v10 v11 v12 v13 0.4% 138.3 us
v1
v2
v4 0.1% 57.6 us
v5
v7 33.9% 2.8 ms
v9 v8
v14
v3
S3 S4
S1 S2
v6
(b) BCD.
v10 v11 v12 v13 99.1% 3.4 ms
v1
v4 v5 29.3% 56.0 ms
v7 15.1% 324.1 us
v9 v8
v14
v3
S3 S4
v10 v11 v12 v13 0.4% 138.3 us
S1 S2
v6
S3 S4
(d) COMM-MS.
(c) COMP-MS.
Fig. 6: Optimal service path and model splitting for MSI (𝐾 = 3 and 𝑏 = 2). 1.6 s+6.5 ms 2.5 s+20.8 ms 1–2 (b × 0.80 MB) 3–26 (b × 0.80 MB) 27–37 v̂1 v̂2 v̂3 2.5 s+20.8 ms v2 1.6 s+6.5 ms (b × 0.80 MB) (b × 0.80 MB)
v1
v4 5.1% 18.1 ms
v5
v7 88.1% 281.2 ms
v9 v8
v14
v3 v6
(a) ILP.
S1 S2
1.6 s+6.5 ms 2.5 s+20.8 ms 1–2 (b × 0.80 MB) 3–19 (b × 0.80 MB) 20–37 v̂1 v̂2 v̂3 2.5 s+20.8 ms v2 1.6 s+6.5 ms (b × 0.80 MB) (b × 0.80 MB)
v10 v11 v12 v13 70.2% 114.3 ms S3 S4
v1
v4 5.1% 18.1 ms
v5
v7 61.7% 200.2 ms
v9 v8
v14
v3 v6
S1 S2
6.6 s+6.5 ms 2.5 s+20.8 ms 1 (b × 3.21 MB) 2–19 (b × 0.80 MB) 20–37 v̂1 v̂2 v̂3 2.5 s+20.8 ms v2 6.6 s+6.5 ms (b × 3.21 MB) (b × 0.80 MB)
v10 v11 v12 v13 96.6% 195.3 ms S3 S4
(b) BCD.
v1
v4 5.1% 17.6 ms
v5
v7 61.7% 200.2 ms
v9 v8
v14
v3 v6
(c) COMP-MS.
S1 S2
822.1 ms+6.5 ms 33.6 ms+10.6 ms 1–33 (b × 0.40 MB) 34–36 (b × 8192 B) 37 v̂1 v̂2 v̂3 33.6 ms+10.6 ms v2 822.1 ms+6.5 ms (b × 0.40 MB) (b × 8192 B)
v10 v11 v12 v13 96.6% 195.3 ms S3 S4
v1
v4 v5 30.6% 16.6 s
v7 32.8% 35.8 ms
v9 v8
v14
v3 v6
S1 S2
v10 v11 v12 v13 0.4% 12.7 ms S3 S4
(d) COMM-MS.
Fig. 7: Optimal service path and model splitting for MSL (𝐾 = 3 and 𝑏 = 128).
a more complex effect on the total transmission delay. Since each physical link has an identical caapcity in this evaluation, the total transmission delay is determined by the cumulative size of the smashed data, which is influenced by the model splitting decisions. To clarify the impact of computation, transmission, and propagation delays on inference and training latencies, we analyze the impact of 𝐾 on these latencies with detailed breakdowns for MSI (𝑏 = 2) and MSL (𝑏 = 128), as shown in Figs. 8 and 9, respectively. For lightweight tasks such as MSI
(𝑏 = 2), where the computational load is small, increasing 𝐾 from 2 to 3 reduces the computation delay by distributing the workload across GPU nodes. However, this also increases the communication delay due to the additional smashed data transmissions. As a result, 𝐾 = 2 remains slightly more optimal overall, as it minimizes the combined computation and communication overheads. On the other hand, for heavier tasks such as MSL (𝑏 = 128), where the computational load is significant, it becomes essential to distribute the computational load across GPU nodes by appropriately increasing 𝐾. At the
9
Inference latency [s]
0.5 0.4
Delay component Forward computation delay Activation transmission delay Link propagation delay
Scheme ILP BCD
COMP-MS COMM-MS
0.3 0.2 0.1 0.0
2
3
4 5 6 Service chain length K
7
Fig. 8: Impact of 𝐾 on inference latency with breakdown (𝑏 = 2).
Training latency [s]
50 40 30
Delay component Forward computation delay Backward computation delay Activation transmission delay Gradient transmission delay Link propagation delay
Scheme ILP BCD
COMP-MS COMM-MS
20 10 0
2
3
4 5 6 Service chain length K
7
Fig. 9: Impact of 𝐾 on training latency with breakdown (𝑏 = 128).
same time, to mitigate the accompanying increase in communication overhead, 𝐾 = 3 emerges as the optimal choice. Notably, 𝐾 = 4 achieves inference and training latencies comparable to 𝐾 = 3, but for 𝐾 ≥ 5, the impact of increased communication overhead becomes more pronounced. Model splitting, placement, and chaining decisions are inherently interdependent, as the optimal service path is influenced by the model splitting strategy. This strategy directly affects computation and communication overheads, as well as memory and storage utilization. To explore this relationship in detail, we provide examples of the optimal service path and model splitting for MSI and MSL, illustrated in Fig. 6a (𝐾 = 3, 𝑏 = 2) and Fig. 7a (𝐾 = 3, 𝑏 = 128), respectively. These figures extend Fig. 3 by including imaginary nodes (shown as squares), imaginary links (depicted as black lines), the service chain (indicated by colored dashed arrows labeled with transmission delay plus propagation delay and smashed data sizes), subpaths (represented with colored solid arrows), and the allocated model layers displayed above the imaginary nodes. The source node 𝑣 4 and destination node 𝑣 13 are highlighted in red and blue, respectively. Memory utilization and computation delays for executing sub-models are displayed below the respective physical nodes, 𝑣 4 , 𝑣 7 , and 𝑣 13 . In the MSI example of Fig. 6a, the majority of layers are allocated to the source CPU node 𝑣 4 (i.e., layers 1–17) and the intermediate GPU node 𝑣 7 (i.e., layers 18–36). The
computational costs for these allocations are 210.60 GFLOPs and 263.12 GFLOPs, respectively, with corresponding computation times of 25.7 ms and 3.4 ms. This allocation highlights the advantages of GPU nodes. While it may seem preferable to allocate more layers to the destination GPU node 𝑣 13 , the characteristic (C2) described in Section VI-A1 indicates that splitting the model at later layers is more effective in reducing transmission delays caused by the smashed data size. The comparable computation delay at 𝑣 4 and the total transmission delay in S2 suggests that the model is split to achieve a balance between computation and transmission delays. Regarding the subpaths traversing the physical network, S2 = ( 𝑣ˆ 1 , 𝑣 4 , 𝑣 5 , 𝑣 7 , 𝑣ˆ 2 ) represents the minimumhop path with the smallest propagation delay. In contrast, S3 = ( 𝑣ˆ 2 , 𝑣 7 , 𝑣 8 , 𝑣 11 , 𝑣 12 , 𝑣 13 , 𝑣ˆ 3 ) is not the minimum-hop path but is selected for its minimum propagation delay. This choice is justified by the extremely small transmission delay per hop, measured at 131.1 𝜇s. In contrast, in the MSL example of Fig. 7a, the increased task scale leads to a higher computational cost, resulting in a reduced allocation of layers to the source CPU node 𝑣 4 (i.e., layers 1–2). The remaining layers are distributed between the intermediate GPU node 𝑣 7 (i.e., layers 3–26) and the destination GPU node 𝑣 13 (i.e., layers 27–37) to mitigate the cumulative computation delay. Since the GPU nodes have uniform performance in this evaluation, specific model splitting between these nodes does not affect the their cumulative computation delay. According to characteristic (C2), allocating more layers to the intermediate GPU node would reduce the smashed data size; however, the memory constraints limit the number of layers assigned to 𝑣 7 . Consequently, the computation delays at 𝑣 7 and 𝑣 13 are 281.2 ms and 114.3 ms, respectively, which are significantly higher compared to the MSI example. Additionally, the cumulative transmission delays in S2 and S3 are 1.6 s and 2.5 s, respectively. In case of S3 , the minimum-hop path ( 𝑣ˆ 2 , 𝑣 7 , 𝑣 5 , 𝑣 6 , 𝑣 13 , 𝑣ˆ 3 ) is selected because, on a per-hop basis, the transmission delay of 833 ms is significantly dominant compared to the propagation delay of at most 14.2 ms. These findings emphasize the necessity of addressing the complex interdependencies among model splitting, placement, and chaining to derive optimal solutions tailored to the specific characteristics and requirements of the given tasks. C. Scheme Comparison Next, we assess the effectiveness of the BCD algorithm by comparing its results with the optimal solutions derived from the ILP. The BCD algorithm achieves almost the same objective values as the ILP solutions for both MSI and MSL, as shown in Figs. 4b and 5b, respectively, by iteratively optimizing the model splitting and service path decisions. Furthermore, the BCD algorithm exhibits almost identical trends in the impact of 𝐾 on these latencies with detailed breakdowns as observed in the ILP solution, as shown in Figs. 8 and 9. Figs. 6b and 7b illustrate the service path and model splitting results of the BCD algorithm for MSI (𝐾 = 3, 𝑏 = 2) and MSL (𝐾 = 3, 𝑏 = 128), respectively. Although the splitting
10
10
103
1
ILP COMP-MS COMM-MS BCD
10−1
10−3
2
3 4 5 6 7 Service chain length K
Execution time [s]
103 Execution time [s]
points in BCD and ILP for MSL differ, they represent one of the multiple optimal solutions, as layers 11–32 share the same smashed data size of 𝑏 × 0.80 MB. Similarly, the total computation delay on GPU nodes 𝑣 7 and 𝑣 13 is identical between the ILP and BCD solutions, indicating an equivalent computational load distributed across these nodes. To confirm the joint optimization, we further analyze the performance of COMP-MS and COMM-MS relative to the optimal solutions. Figs. 4c and 5c illustrate the inference and training latencies of COMP-MS, respectively. Additionally, the service path and model splitting of COMP-MS are depicted in Fig. 6c for MSI (𝐾 = 3, 𝑏 = 2) and Fig. 7c for MSL (𝐾 = 3, 𝑏 = 128), respectively. COMP-MS initially performs model splitting to minimize computation overhead by assigning only the first layer to the source CPU node 𝑣 4 while distributing the remaining layers across the intermediate and destination GPU nodes, 𝑣 7 and 𝑣 13 . This results in much smaller computation delays of 57.6 𝜇s and 17.6 ms on the source CPU node 𝑣 4 than the ILP solutions for MSI and MSL examples, respectively. However, this approach also causes a larger smashed data size for S2 (i.e., 𝑏 × 3.21 MB), reflecting the total transmission delays of 102.8 ms and 6.6 s in the subpath S2 for MSI and MSL examples. As a consequence, the transmission delay becomes more significant with increasing 𝐾, and the subsequent step of selecting a service path tends to focus on minimizing the hop count. This can be confirmed from Figs. 8 and 9, where the transmission delay becomes dominant in the COMP-MS scheme as 𝐾 increases. However, we also observe that the overall trend indicates an increase in latency as 𝐾 grows, with a temporary reduction observed at 𝐾 = 5. This phenomenon corresponds to changes in the cumulative smashed data size, which directly influences communication overhead. Moreover, since COMP-MS exclusively focuses on minimizing computation overhead during model splitting, it may select splitting points that yield identical computation overheads but differ in cumulative smashed data sizes, thereby causing variations in communication overhead. Figs. 4d and 5d illustrate the inference and training latencies of COMM-MS, respectively. The service path and model splitting of COMM-MS are depicted in Fig. 6d for MSI (𝐾 = 3, 𝑏 = 2) and Fig. 7d for MSL (𝐾 = 3, 𝑏 = 128), respectively. Since all communication links have uniform capacity in this evaluation, COMM-MS splits the model to minimize the cumulative smashed data size transmitted along subpaths traversing the physical network, specifically S2 and S3 . For 𝐾 = 3, the model is split such that the smashed data sizes for S2 and S3 are 𝑏 × 0.40 MB and 𝑏 × 8192 B, respectively. This results in significantly smaller transmission delays of 12.8 ms and 524.3 𝜇s (resp. 822.1 ms and 33.6 ms) in S2 and S3 for the MSI (resp. MSL) example, compared to the ILP solutions. However, this model splitting assigns the first 34 (resp. 33) layers for MSI (resp. MSL), which constitute the majority of the global model, to the source CPU node 𝑣 4 . This leads to significantly higher computation delays of 56.0 ms and 16.6 s on the 𝑣 4 , as shown in Figs. 8 and 9, respectively. For 𝐾 = 7, even if layers 33–37 are assigned one by one to sub-models after 𝑣ˆ 3 , it becomes necessary to split layers 1– 32 between 𝑣ˆ 1 and 𝑣ˆ 2 . Consequently, GPU nodes are utilized
10
ILP COMP-MS COMM-MS BCD
1
10−1
10−3
10 20 30 40 50 Number V of physical nodes
Fig. 10: Impact 𝐾 on execu- Fig. 11: Impact 𝑉 on execution tion time. time. more effectively, leading to a reduction in computation delay, particularly in the computationally intensive MSL scenario. Considering the computational complexity, which will be evaluated in Section VI-D, the BCD algorithm demonstrates a significant advantage by achieving performance comparable to the ILP while drastically reducing the execution time. This efficiency is attributed to the decomposition of the original problem into two subproblems, enabling iterative optimization with lower computational overhead. D. Scalability Analysis Fig. 10 shows the impact of 𝐾 on the execution time for all schemes. These results are obtained in the training scenario with 𝑏 = 128. It is noteworthy that the execution time exhibits a similar trend in the inference scenario, irrespective of 𝑏. We observe from Fig. 10 that the execution time increases for all schemes as 𝐾 grows. This is attributed to the rise in the number of decision variables and constraints in the ILP formulation with increasing 𝐾. Notably, BCD demonstrates a significant advantage, solving the problem over 100 times faster than ILP and consistently finding a feasible solution within 50 ms. Furthermore, BCD demonstrates shorter execution times compared to both COMP-MS and COMM-MS. To evaluate the scalability of the schemes concerning the network size, we consider randomly generated networks with 𝑉 physical nodes, where each pair of nodes is connected by a physical link with a probability of 0.2. Fig. 11 depicts the impact of 𝑉 on the execution time for all schemes. The results indicate that ILP fails to find an optimal solution within the predefined execution time limit of 1,000 seconds when 𝑉 ≥ 30, whereas the other schemes consistently find feasible solutions. Additionally, BCD achieves shorter execution times compared to both COMP-MS and COMM-MS, regardless of 𝑉. This scalability analysis emphasizes that BCD is more scalable than ILP while maintaining high solution quality. VII. C ONCLUSION This paper addresses the challenges of model splitting, placement, and chaining in multi-hop split inference and training scenarios. We formulate the problem as an Integer Linear Programming (ILP) model designed to minimize the training or inference latency. To improve computational efficiency, we propose a heuristic algorithm based on the block
11
coordinate descent (BCD) method. This algorithm decomposes the original problem into two subproblems: (1) model splitting and (2) model placement and chaining, and iteratively optimizes these subproblems until convergence. Evaluation results reveal the tradeoff between computation and communication across varying mini-batch sizes and service chain lengths. The findings demonstrate that the proposed BCD achieves inference and training latencies comparable to the optimal ILP solution while significantly reducing computation time. Future work will focus on extending the model to address data privacy, multi-path routing, and collaborative model execution across multiple nodes. R EFERENCES [1] P. Vepakomma, O. Gupta, T. Swedish, and R. Raskar, “Split Learning for Health: Distributed Deep Learning without Sharing Raw Patient Data,” Dec. 2018. [2] G. Zhu, Y. Deng, X. Chen, H. Zhang, Y. Fang, and T. F. Wong, “ESFL: Efficient Split Federated Learning over Resource-Constrained Heterogeneous Wireless Devices,” IEEE Internet of Things Journal, vol. 11, no. 16, pp. 27 153–27 166, Aug. 2024. [3] Z. Lin, G. Zhu, Y. Deng, X. Chen, Y. Gao, K. Huang, and Y. Fang, “Efficient Parallel Split Learning over Resource-Constrained Wireless Edge Networks,” IEEE Transactions on Mobile Computing, vol. 23, no. 10, pp. 9224–9239, Oct. 2024. [4] J. Tirana, S. Lalis, and D. Chatzopoulos, “Estimating the Training Time in Single- and Multi-Hop Split Federated Learning,” in Proc. of the 8th International Workshop on Edge Systems, Analytics and Networking, ser. EdgeSys ’25. New York, NY, USA: Association for Computing Machinery, Mar. 2025, pp. 37–42. [5] Z. Lin, W. Wei, Z. Chen, C.-T. Lam, X. Chen, Y. Gao, and J. Luo, “Hierarchical Split Federated Learning: Convergence Analysis and System Optimization,” IEEE Transactions on Mobile Computing, vol. 24, no. 10, pp. 9352–9367, Oct. 2025. [6] T. Hara and M. Sasabe, “Service Function Chaining Architecture for Multi-hop Split Inference and Learning,” Sep. 2025, arXiv:2509.10001. [7] C. Xu, Y. Liu, and J. Yang, “Inference Routing over Multi-Hop Edge Networks,” IEEE Transactions on Cognitive Communications and Networking, vol. 12, pp. 1356–1367, 2026. [8] W. Wei, Z. Lin, T. Li, X. Li, and X. Chen, “Pipelining Split Learning in Multi-hop Edge Networks,” Sep. 2025. [9] J. M. Halpern and C. Pignataro, “Service Function Chaining (SFC) Architecture,” RFC 7665, Oct. 2015. [Online]. Available: https://www.rfc-editor.org/info/rfc7665 [10] J. Yan, S. Bi, and Y.-J. A. Zhang, “Optimal Model Placement and Online Model Splitting for Device-Edge Co-Inference,” IEEE Transactions on Wireless Communications, vol. 21, no. 10, pp. 8354–8367, Oct. 2022. [11] W. Wu, M. Li, K. Qu, C. Zhou, X. Shen, W. Zhuang, X. Li, and W. Shi, “Split Learning over Wireless Networks: Parallel Design and Resource Management,” IEEE Journal on Selected Areas in Communications, vol. 41, no. 4, pp. 1051–1066, Apr. 2023. [12] M. Kim, A. DeRieux, and W. Saad, “A Bargaining Game for Personalized, Energy Efficient Split Learning over Wireless Networks,” in Proc. of IEEE Wireless Communications and Networking Conference (WCNC), Mar. 2023, pp. 1–6. [13] Z. Li, W. Wu, S. Wu, and W. Wang, “Adaptive Split Learning over Energy-Constrained Wireless Edge Networks,” in IEEE INFOCOM 2024 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), May 2024, pp. 1–6. [14] M. Marinova, M. Poposka, Z. Hadzi-Velkov, and V. Rakovic, “Optimal Cut Layer Bounds for Split Learning,” IEEE Communications Letters, vol. 29, no. 4, pp. 749–753, Apr. 2025. [15] S. Jung and H.-W. Lee, “Optimization Framework for Splitting DNN Inference Jobs over Computing Networks,” Computer Networks, vol. 232, p. 109814, Aug. 2023. [16] I. Sartzetakis, P. Soumplis, P. Pantazopoulos, K. V. Katsaros, V. Sourlas, and E. Varvarigos, “Edge/Cloud Infinite-Time Horizon Resource Allocation for Distributed Machine Learning and General Tasks,” IEEE Transactions on Network and Service Management, vol. 21, no. 1, pp. 697–713, Feb. 2024.
[17] K. Tajiri and R. Kawahara, “Optimization of Data and Model Transfer for Federated Learning to Manage Large-Scale Network,” IEEE Transactions on Network and Service Management, vol. 22, no. 2, pp. 958–973, Apr. 2025. [18] W. Fan, D. Wang, F. Xiao, Y. Zuo, M. Lv, L. Han, and S.-Y. Hsieh, “Dynamic Topology and Resource Allocation for Distributed Training in Mobile Edge Computing,” IEEE Transactions on Mobile Computing, vol. 24, no. 11, pp. 11 927–11 941, Jan. 2025. [19] M. Sasabe and T. Hara, “Capacitated Shortest Path Tour ProblemBased Integer Linear Programming for Service Chaining and Function Placement in NFV Networks,” IEEE Transactions on Network and Service Management, vol. 18, no. 1, pp. 104–117, Mar. 2021. [20] R. J. Vanderbei, “Linear Programming,” in Encyclopedia of Applied and Computational Mathematics. Springer, 2015, pp. 796–800. [21] S. J. Wright, “Coordinate Descent Algorithms,” Mathematical Programming, vol. 151, no. 1, pp. 3–34, Jun. 2015. [22] S. Bhat and G. N. Rouskas, “Service-Concatenation Routing with Applications to Network Functions Virtualization,” in Proc. of the International Conference on Computer Communication and Networks (ICCCN). Vancouver, BC, Canada: IEEE, Jul. 2017, pp. 1–9. [23] R. Bellman, “On the Approximation of Curves by Line Segments Using Dynamic Programming,” Commun. ACM, vol. 4, no. 6, p. 284, Jun. 1961. [24] T. Hara and M. Sasabe, “Speedy and Efficient Service Chaining and Function Placement Based on Lagrangian Heuristics for Capacitated Shortest Path Tour Problem,” Journal of Network and Systems Management, vol. 31, no. 1, p. 24, Dec. 2022. [25] L. Grippo and M. Sciandrone, “On the Convergence of the Block Nonlinear Gauss–Seidel Method under Convex Constraints,” Operations Research Letters, vol. 26, no. 3, pp. 127–136, Apr. 2000. [26] D. L. Mills and H. Braun, “The NSFNET Backbone Network,” in Proc. of the ACM Workshop on Frontiers in Computer Communications Technology, Aug. 1987, pp. 191–196. [27] K. He, X. Zhang, S. Ren, and J. Sun, “Deep Residual Learning for Image Recognition,” in Proc. of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Jun. 2016, pp. 770–778. [28] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “ImageNet: A Large-Scale Hierarchical Image Database,” in Proc. of IEEE Conference on Computer Vision and Pattern Recognition, Jun. 2009, pp. 248–255. [29] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Köpf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala, “PyTorch: An Imperative Style, HighPerformance Deep Learning Library,” Dec. 2019, arXiv:1912.01703. [30] Gurobi Optimization, LLC, “Gurobi Optimizer Reference Manual,” 2024. [Online]. Available: https://www.gurobi.com [31] A. Hagberg, P. Swart, and D. S Chult, “Exploring Network Structure, Dynamics, and Function Using Networkx,” Los Alamos National Lab. (LANL), Los Alamos, NM (United States), Tech. Rep. LA-UR-0805495; LA-UR-08-5495, Jan. 2008.
Takanori Hara received the B.Eng. degree from National Institution for Academic Degrees and Quality Enhancement of Higher Education in 2016 and the M.Eng. and Ph.D. degrees from Nara Institute of Science and Technology, Japan, in 2018 and 2021. He is currently an Associate Professor with the Division of Information Science, Graduate School of Science and Technology, Nara Institute of Science and Technology, Japan. His research interests include eBPF/XDP, NFV, SDN, and networking for AI. Dr. Hara is a member of IEEE, ACM, and IEICE.
12
Masahiro Sasabe received the B.S., M.E., and Ph.D. degrees from Osaka University, Japan, in 2001, 2003, and 2006, respectively. He is currently a Professor of Faculty of Informatics, Kansai University, Japan. His research interests include P2P/NFV networking, game-theoretic approaches, human-harmonized network systems, and network optimization. Dr. Sasabe is a member of IEEE, ACM, and IEICE.