# More on Pipelined Dynamic Scheduling of Big Data Streams
## 3 Preliminaries and Communication Scheduling
### Communication Scheduling  
In our previous work, we described our stepwise strategy and proved that it reduces the overall communication cost. In this subsection, we briefly repeat the scheduling, but without many details. By the end of this section, we show how this scheduler can be used for task migrations. In the big data literature, the latency of communication between two nodes is generally defined by their index difference. For two nodes \(n_{i}\) and \(n_{j}\), the communication latency \(\ell\) increases as the difference \(|i-j|\) becomes larger. In our example, if the tasks from node 5 need to communicate with the tasks of node 0 and vice versa, we have the maximum possible latency of \(\ell=|5-0|\) or \(\ell=|0-5|=5\) time units. In our context, we use the term \"time units\" as a unit that measures the inter-node communication latencies. Our scheduler organizes the internode communication in such a way that each node receives tuples from only one other node. In other words, each node's tasks receive tuples that have been previously processed by the tasks of only one other node. The communicating tasks are explicitly defined by the application's topology. The three steps of our scheduling approach are described below:  
**Step 1:**_Transform CT to a Single Index Matrix_  
The first step transforms the CT to a single-index matrix \(SIM\). To make the transformation from the CT to the SIM, we simply pick each communicating node pair \((n,q)\) found in row \(k\) and we place the \(q\) values interchangeably to column \(n\) of \(SIM\). By interchangeably, we mean that no similar values are placed between adjacent nodes. Thus, the CT of Table 2 will be transformed into the following \(SIM\) matrix:  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Class** & **Communicating Nodes** & \(\mathbf{c}\) \\ \hline
0 & (0,0), (3,0), (1,2), (4,2), (2,4), (5,4) & 4 \\
1 & (0,1), (3,1), (1,3), (4,3), (2,5), (5,5) & 4 \\
2 & (2,0), (5,0), (0,2), (3,2), (1,4), (4,4) & 3 \\
3 & (2,1), (5,1), (  
**Step 2: _Mix Class Elements to Define Communicating Steps_**  
Here, we simply interchange \(\alpha\) elements from homogeneous classes, that reside in corresponding columns, where \(\alpha\) is the number of communications towards different target nodes within each class, \(\alpha\geq 2\). In our example, \(\alpha=3\), so we interchange 3 elements of the homogeneous classes 0 and 1, 3 elements of the homogeneous classes 2 and 3, and 3 elements of the homogeneous classes 4 and 5. These elements reside in columns \(N_{3}-N_{5}\) of the SIM. In this way, will produce the initial scheduling matrix (ISM): \begin{tabular}{c|c c c c c c c}  & & \multicolumn{6}{c}{**Node \(n\)**} \\
**Communicating Step** & 0 & 1 & 2 & 3 & 4 & 5 & **Communication Cost** \\ \hline
0 & 0 & 2 & 4 & 1 & 3 & 5 & **2** \\
1 & 1 & 3 & 5 & 0 & 2 & 4 & **3** \\
2 & 2 & 4 & 0 & 3 & 5 & 1 & **4** \\
3 & 3 & 5 & 1 & 2 & 4 & 0 & **5** \\
4 & 4 & 0 & 2 & 5 & 1 & 3 & **4** \\
5 & 5 & 1 & 3 & 4 & 0 & 2 & **5** \\ \end{tabular} 
**Step 3: _Reducing the Communication Costs_**  
Step 3 reorganizes the matrix produced in Step 2, by taking the following actions:  
\begin{tabular}{c|c c c c c c c}
3.1 & A zero cost communicating step that includes only internal operations (among a node's tasks) is defined. We put these communicating pairs in the first raw of \(ISM\) and make the proper index changes. \begin{tabular}{c|c c c c c c c}
3.2 & & & & & & & & & & & \\
**Spec** & **Spec** & **Spec** & **Spec** & **Spec** &  
where \(\mu_{m}\) is the mean forwarding time (or service time) for the migrated tasks relayed to node \(m\) and the \(\lambda\) values are the mean input rates of tasks to the nodes. Each \(\lambda_{m}\) is a sum of the form  
\[\lambda_{m}=b_{m-1}\lambda_{m-1}, \tag{11}\]  
where \(b_{m-1}\) is the probability of task migrations to node \(m-1\). For example, see Figure 1 and consider the parameter values of Table 3. Then, Equation (11) would produce \(\lambda_{2}=15\) tasks/s and \(\lambda_{3}~{}=~{}20\) tasks/s.