# Enhancing Robustness of Per-Packet Load-Balancing for Fat-Tree
## 5 Handling Queue Length Differentials
### Numerical Results  
We calculate the queue lengths under the mechanism presented in Table 3, by presenting the numerical results about the queue length for each hop in an 8-ary fat-tree. Adopting the time-slot model that is used in [16], we made similar assumptions. All packets have the same length. All switches are output-queued, and the capacity of each port is 1. Each  
Figure 8: A switch is in one of the three states. qlen(i) indicates the queue length of an output port in link group i.  
\begin{table}
\begin{tabular}{l l l} \hline \hline \multicolumn{1}{c}{**if** (this switch is a ToR switch) **then**} \\ D \(\leftarrow\) LSB of the destination address & \\ else if (this switch is an aggregation switch) **then** & \\ D \(\leftarrow\) second LSB of the destination address & \\ end & \\ S \(\leftarrow\) parity of the input port through the packet came in & \\ \hline \hline \multicolumn{1}{c}{State 1} & State 0 & State 2 \\ \hline \hline \multicolumn{1}{c}{**if** (D == 0) **then**} & \multicolumn{1}{c}{**if** (D == 0) **then**} & \multicolumn{1}{c}{**if** (D == 1) **then**} \\ \multicolumn{1}{c}{**if** (S == 0) **then**} & \multicolumn{1}{c}{group = 0} & \multicolumn{1}{c}{**if** (S == 0) **then**} \\ \multicolumn{1}{c}{group = 0} & \multicolumn{1}{c}{**else**} & \multicolumn{1}{c}{group = 0} \\ \multicolumn{1}{c}{**else**} & \multicolumn{1}{c}{group = 1} & \multicolumn{1}{c}{**else**} \\ \multicolumn{1}{c}{group = 1} & \multicolumn{1}{c}{**end**} & \multicolumn{1}{c}{group = 1} \\ \multicolumn{1}{c}{**end**} & \multicolumn{1}{c}{**else**} & \multicolumn{1}{c}{**end**} \\ \multicolumn{1}{c}{**else**} & \multicolumn{1}{c}{**else**} & \multicolumn{1}{c}{group = 1} \\ \multicolumn{1}{c}{group = 1} & \multicolumn{1}{c}{**end**} & \multicolumn{1}{c}{group = 0} \\ \hline \hline \end{tabular}
\end{table}
Table 3: Determining a link group for a packet in each state.  
output port transmits one packet at each time-slot if the queue is not empty. Permutation traffic patterns are used and therefore once a host is selected for packet generation, the destination address of the generated packet is determined accordingly. In each time slot, each host generates packets using Bernoulli distribution.  
To evaluate the behavior of a round robin manner, we randomly select a host for each pod in each time-slot and then generate four consecutive packets with the offered load \(\rho\) on each input port of each ToR switch. Packets are sent for 1000 time slots. We repeated this process for 100 randomly generated traffic permutation patterns. We varied the offered load \(\rho\) from 0.3 to 0.9.  
We calculated not only the average queue lengths but also the difference between the queue lengths of different link groups. Recall that the queue lengths at the ports in the same link group are always almost equal. Figure 8(a) shows the average queue lengths for the upward hop outputs. We can see that traffic distribution mechanism prevents the queue lengths from growing excessively. As the offered load \(\rho\) increases, the queue lengths at the second hop (aggregation switches) are longer than those at the first hop (ToR switches). The reason is that aggregation switches less frequently perform state transitions in order to reduce message exchanges between aggregation switches. At the third hop (i.e., output ports of core switches), the average queue length increases linearly with respect to the offered load \(\rho\), and remains below 1. Figure 8(b) shows the difference between the queue lengths of different link groups. Since aggregation switches less frequently perform state transitions, the queue length differences at the second hop are larger than those at the first hop.