# A Distributed Multicast QoS Routing Construction Approach in Information-Centric Networking
## 3 System Design
### Tree Construction Algorithm
#### 3.5.4 Grafting Process  
Following the method described in Section 3.5.2, the tree node extracts information recorded in the tail entry of the LS Table within the JOIN message and calculates \(D_{meas}\) and \(C_{meas}\). Additionally, TN maintains the accumulated delay, \(D_{accum}\)[TN]. As illustrated in Figure 9, the multicast delay for R under the current join path is calculated as Formula (7):  
\[Delay[\text{TN}]=D_{meas}+D_{accum}[\text{TN}] \tag{7}\]  
If _Delay_[TN] meets the delay requirement of QoS, update the information maintained by the node and the fields in the message accordingly. Append the NA recorded in the tail entry of the LS Table to the forwarding node list of MFT[MID]. The Message Type and Request Node field in the message is modified to GRAFT and TN's NA, respectively. Forward the message to the NA recorded in the tail entry of the LS Table, and then remove the tail entry. Subsequently, the node forwards multicast data packets by utilizing entries in the multicast replication forwarding table. If TN's delay does not meet the QoS requirement, the relay node selection Algorithm 1 is employed to choose a relay node from the LS table. This selection is based on the already detected link information and the neighborhood state information maintained by the local node. Subsequently, a new path is established from TN to the relay node. At this time, add the Gateway returned by the algorithm to the forwarding node list of MFT[MID]. The multicast delay from RN to the receiver node (R), depicted in Figure 10, is determined by the accumulated delay from RN to TN, the delay from TN to Relay, and the delay from Relay to R. The multicast delay can be represented as Formula (8):  
\[Delay=D_{accum}[TN]+D_{est}[Relay]+D_{meas}[Relay] \tag{8}\]  
Figure 8: Construction of LS Table During JOIN Message Propagation. Figure 9: The delay measured upon arrival of the join message at the tree node. Advancing to the Relay Node Selection phase, the delay of the minimum-cost path from the current tree node to the receiver has been precisely calculated. If this path fails to meet the delay constraints, adaptation occurs by selecting a relay node along the path. After this selection, adjustments are made to the forwarding path from TN to the relay node to align with the minimum delay route. The relay node selection process involves access to precise delay information, covering the accumulated delay at the TN node, the delay from the relay node to the receiver, and neighborhood delay information in NSIB. The only imprecise information lies in the delay from TN (Tree Node) to the relay node. Evaluate the recorded delays of various nodes in the multicast message, treating them as potential relays, and select the node most likely to satisfy delay constraints while minimizing costs. The relay node selection Algorithm 1 utilizes symbols listed in Table 2, and the detailed execution steps of the algorithm are provided below:  
```
1:Input:LS Table, \(D_{\text{QoS}}\), \(LDT\), \(NSIB\)
2:Output:Gateway, Cost\({}_{\text{Candidate}}\), Delay\({}_{\text{Candidate}}\)
3:\(NA_{\text{Candidate}}=nil\), Cost\({}_{\text{Candidate}}=\infty\), Delay\({}_{\text{Candidate}}=\infty\)
4:for each\({}_{Si}\) in LS Tabledo
5:\({}_{\text{ProbeDelay}}=LS_{i}.Delay+D_{accum}+LDT[LS_{i}.NA].Delay\)
6:\({}_{\text{Candidate}}\)\(Delay={}_{\text{ProbeDelay}}-LDT[LS_{i}.NA].rowHopDelay+NSIB[NA].Delay\)
7:if\({}_{\text{Candidate}}\)\(Delay<=D_{\text{QoS}}\) or \({}_{\text{Candidate}}\) then
8:\({}_{\text{Gateway}}=LDT[LS_{i}.NA].Gateway\)
9:\(NA_{\text{Candidate}}=LS_{i}.NA\)
10:\({}_{\text{Candidate}}=LS_{i}.Cost+LDT[LS_{i}.NA].Cost\)
11:\({}_{\text{Candidate}}=LS_{i}.Delay+LDT[LS_{i}.NA].Delay\)
12:endif
13:endfor
14:Erase entry in LS Table from \(NA_{\text{Candidate}}\) to tail
15:return\({}_{\text{Gateway}}\), Cost\({}_{\text{Candidate}}\), Delay\({}_{\text{Candidate}}\)
```  
**Algorithm 1** Relay Node Selection Algorithm 1.