## 3 System Design
### Path State-Aware Multicast Tree Node Selection Mechanism
Max Load field refers to the maximum link rate among all links in the path. Total Load refers to the sum of link rates of all links in the path. The link rate of a link is the same as the interface rate of the router connected to the link. \begin{table} \begin{tabular}{l c c c} \hline \hline
**Symbol** & **Meaning** & **Symbol** & **Meaning** \\ \hline \(\{MTN\}\) & the list of multicast tree nodes & \(L_{\text{\emph{avr}}}^{\text{\emph{opti}}}\) & the average link load of \(MTN_{\text{\emph{opti}}}\) \\ \(MTN_{\text{\emph{opti}}}\) & the optimal multicast tree node & \(L_{\text{\emph{max}}}\) & the maximum link load of the \(MTN\) \\ \(L_{\text{\emph{max}}}^{\text{\emph{opti}}}\) & the maximum link load of \(MTN_{\text{\emph{opti}}}\) & \(L_{\text{\emph{aver}}}\) & the average link load of the \(MTN\) \\ \hline \hline \end{tabular}   
Step 1: Initialization: \(MTN_{\text{\emph{opti}}}=\varnothing\), \(L_{\text{\emph{max}}}^{\text{\emph{opti}}}=\infty\), \(L_{\text{\emph{avr}}}^{\text{\emph{opti}}}=\infty\). Step 2: For each \(MTN\) in \(\{MTN\}\), the edge router sends a path state detection message to the \(MTN\) to obtain the maximum link load \(L_{\text{\emph{max}}}\) and the average link load \(L_{\text{\emph{avr}}}\) of the path between the edge router and the \(MTN\), and then go to step 3. Step 3: If \(L_{\text{\emph{max}}}<\ L_{\text{\emph{max}}}^{\text{\emph{opti}}}\), then set \(MTN_{\text{\emph{opt}}}\) to the \(MTN\), set \(L_{\text{\emph{max}}}^{\text{\emph{opti}}}\) to \(L_{\text{\emph{max}}}\), set \(L_{\text{\emph{avr}}}^{\text{\emph{opti}}}\) to \(L_{\text{\emph{avr}}}\), and go to step 5. Otherwise, go to step 4. Step 4: If \(L_{\text{\emph{max}}}=\ L_{\text{\emph{max}}}^{\text{\emph{opti}}}\) and \(L_{\text{\emph{avr}}}<\ L_{\text{\emph{avr}}}^{\text{\emph{opti}}}\), then set \(MTN_{\text{\emph{opt}}}\) to the \(MTN\) and set \(L_{\text{\emph{avr}}}^{\text{\emph{opti}}}\) to \(L_{\text{\emph{avr}}}\). Then, go to step 5. Step 5: Check if all \(MTN\)s in \(\{MTN\}\) have been visited. If satisfied, then go to step 6. Otherwise, return to step 2. Step 6: Output the optimal multicast tree node \(MTN_{\text{\emph{opti}}}\), which has the best path state. \begin{tabular}{l} \hline \hline Input: \(\{MTN\}\) \\ Output: \(MTN_{\text{\emph{opti}}}\) \\
1: Initialization: \(MTN_{\text{\emph{opti}}}=\varnothing\), \(L_{\text{\emph{max}}}^{\text{\emph{sel}}}=\infty\), \(L_{\text{\emph{avr}}}^{\text{\emph{sel}}}=\infty\) \\
2: for each \(MTN\) in \(\{MTN\}\) do: \\
3: Send _Link Detection Message_ to the \(MTN\) and get the \(L_{\text{\emph{max}}}\) and \(L_{\text{\emph{avr}}}\); \\
4: if \(L_{\text{\emph{max}}}<\ L_{\text{\emph{max}}}^{\text{\emph{sel}}}\) then: \\
5: \(MTN_{\text{\emph{opti}}}=MTN\); \\
6: \(L_{\text{\emph{max}}}^{\text{\emph{sel}}}=L_{\text{\emph{max}}}\); \\
7: \(L_{\text{\emph{avg}}}^{\text{\emph{sel}}}=L_{\text{\emph{avr}}}\); \\
8: else if \(L_{\text{\emph{max}}}=\ L_{\text{\emph{max}}}^{\text{\emph{sel}}}\) and \(L_{\text{\emph{avr}}}<\ L_{\text{\emph{avr}}}^{\text{\emph{sel}}}\) then: \\
10: \(MTN_{\text{\emph{opti}}}=MTN\); \\
11: \(L_{\text{\emph{avr}}}^{\text{\emph{sel}}}=L_{\text{\emph{avr}}}\);After receiving the path state detection message, the intermediate router first increases the Hop Count by 1. Then the intermediate router compares the downstream rate R of the interface that received the message with the value \(L_{max}\) of the Max Load field in the message. If \(R>~{}L_{max}\), set the value of the Max Load field to R. Then, the intermediate router increases the value in the Total Load field by R. Finally, the intermediate router forwards the path state detection message to the MTN. When the path state detection message arrives at the MTN, the MTN performs the following operations:  
Step 1: Get the value \(C\) of the Hop Count field, the value \(L_{max}\) of the Max Load field, and the value \(L_{sum}\) of the Total Load field in the path state detection message, and get the downstream rate R of the interface that received the message.