# More on Pipelined Dynamic Scheduling of Big Data Streams
## 3 Preliminaries and Communication Scheduling
### Communication Scheduling
Then, from Equation (10), \(p_{1}=\frac{30\times 20}{1000}=0.6\), \(p_{2}=\frac{15\times 20}{1000}=0.3\), and \(p_{3}=\frac{20\times 40}{1000}=0.8\). Then, the maximum acceptable input rate per node is the one that saturates it, for example \(m_{1}\) is saturated for \(\lambda_{m}>50\) tasks/s because \(\left(50\times 20\right)/1000=1\). **Fair Distribution of the Migrated Tasks** By \"fair distribution\", two things are meant: (1) fairness in terms of distance between nodes, that is, the nodes located closer to the source of migrated tasks should take more load to keep the communication cost to the minimum, and (2) fairness in terms of the load itself, that is, the load of the migrated tasks should be distributed as evenly as possible taking into consideration the maximum acceptable input rate and the nodes distance. To distribute the tasks fairly, we use the following simple three-stepped procedure:  
**Step 1:**_Find the maximum number of tasks \(U_{j\max}\)_ that can be re-allocated to each node: This number is dependent on the total utilization of each node at the current time, that is, on the acceptable input rate discussed previously (see Equation (10)). \[U_{j\max}=T\times p_{j} \tag{12}\]  
where \(T\) is the total number of migrated tasks. **Step 2:**_Divide the number of migrated tasks by the sum of the maximum number of tasks that can be re-allocated to all the nodes based on their utilization._  
\[f=\frac{T}{\sum_{j=1}^{m}U_{j\max}} \tag{13}\]  
Figure 1: Task migration example. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Parameter** & **Symbol** & **Value** \\ \hline Mean arrival rate an node \(m_{1}\) & \(\lambda_{1}\) & 30 tasks/s \\ Mean service time at node \(m_{1}\) & \(1/\mu_{1}\) & 20 ms \\ Mean service time at node \(m_{2}\) & \(1/\mu_{2}\) & 25 ms \\ Mean service time at node \(m_{3}\) & \(1/\mu_{1}\) & 40 ms \\ Probability of task migrations through \(m_{1}\) & \(b_{1}\) & 0.25 \\ Probability of task migrations through \(m_{2}\) & \(b_{2}\) & 0.3 \\ Probability of task migrations through \(m_{3}\) & \(b_{3}\) & 0.4 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Parameters for the task migration example of Figure 1.  
This will produce an analogy of the number of migrated tasks compare to the number of tasks that the system can re-accommodate based on its node utilization. **Step 3:**_Compute the loading factor per node:_  
\[F_{j}=U_{j\max}\times f \tag{14}\]  
The loading factor will decide about the total number of migrated tasks each node can accommodate. For the example of Figure 1, if \(T=50\) and the utilization values yielded are \(p_{1}=0.6,p_{2}=0.3\), and \(p_{3}=0.8\), then \(U_{11\max}=50\times 0.6=30\), \(U_{2\max}=50\times 0.3=15\), and \(U_{3\max}=50\times 0.8=40\). The sum of the \(U_{j\max}\) values is \(30+15+40=85\) and the \(f\) value is \(50/85=0.58\). Then, the \(F\) values are \(F_{1}=30\times 0.58=17.4\), \(F_{2}=15\times 0.58=8.7\), and \(F_{3}=40\times 0.58=23.2\). Thus, the 50 migrated tasks would be re-allocated as follows: 18 to node \(m_{1}\), 9 to node \(m_{2}\), and 23 to node \(m_{3}\). Two things are worth noticing:  
1. The model presented for fair redistribution of the migrated tasks monitors the load per node. Under the assumption that the tuples distributed are of equal size (this is quite natural and many times desirable), then because of the stepwise strategy of our scheduling, the node utilization values would be very close. This would produce even and fair task redistribution. For different sized transmitted tuples, again there is a guarantee that big parts of the cluster would remain balanced in terms of load processing. 2. The method can be expanded to a larger number of clusters or networks by using relay nodes that connect different clusters. We will explain this when we present our experimental results. Finally, note that, as a result of the queuing approach of our fair task re-allocation policy, there is some type of exponential effect on the system's throughput (see [30]).