# More on Pipelined Dynamic Scheduling of Big Data Streams
## 5 Pipelined Scheduling  
This section shows how to pipeline the main procedures involved in a data stream processing problem. The overall work required by data stream processing applications is divided into three stages: The _transferring stage_ is the stage at which data streams are forwarded according to the communicating steps defined by the \(FSM\) of Section 3 and \(B_{1}\) is used to denote the maximum-cost communication step. The _processing stage_ is the stage at which the streams are processed by the nodes. In this context, we will assume with no loss of generality that all the data streams are considered equal so processing is implemented in constant time \(B_{2}\). Finally, the _packing stage_ is the stage at which the resulting processed streams are put into buffers, in order to be forwarded to the next nodes for further processing. This is the fastest stage. The packing time is \(B_{3}\), and is equal for all the streams being processed. It should be noted that the migrated task go through these stages as well.  
In the analysis that follows, some communication steps are more expensive compared to the actual stream processing (apparently the ones that involve nodes placed far apart), while others are less expensive. Thus, \(B_{1}>B_{2}>B_{3}\). Other cases that may arise (for example all communication steps are \"cheaper\" or \"more expensive\" than the processing costs) can be examined similarly.  
In Figure 2, the gray areas indicate pipeline stage stalls, that is, a stage has no work to do and waits until it becomes busy again. The \"fade to black\" areas indicate the work being implemented for migrations. Let two communication steps, \(S_{0},S_{1}\), have the maximum cost \(B_{1}\) and let there be two task migrations. Since \(B_{1}>B_{2}\), the streams with maximum cost are transferred in \(2u\) time, while their processing will have finished at time \(2B_{1}+B_{2}\). The next two steps \(S_{2},S_{3}\), require \(B_{4}\) time, where \(B_{4}<B_{1}\), but \(B_{4}>B_{2}\). This means that their transfer would be completed at times, \(2B_{1}+B_{4}\) and \(2B_{1}+2B_{4}\), respectively,while their processing will have finished at times \(2B_{1}+B_{4}+B_{2}\) and \(2B_{1}+2B_{4}+B_{2}\), respectively. The communication steps \(S_{4},S_{5}\) require \(B_{5}\) and \(B_{6}\) time, where \(B_{1}>B_{5}>B_{6}\). The transfer stage for \(S_{4}\) and the processing stage for \(S_{3}\) start at time \(2B_{1}+2B_{4}\), but the streams of \(S_{4}\) would be transferred by \(2B_{1}+2B_{4}+B_{5}\), while the processing of \(S_{3}\) which started simultaneously ends later, at time \(2B_{1}+2B_{4}+B_{2}\). Finally, the streams of \(S_{5}\) will be transferred by \(2B_{1}+2B_{4}+B_{5}+B_{6}\) and during that time, the processing \(S_{4}\) streams takes place. It takes \(2B_{1}+2B_{4}+B_{5}+B_{6}+B_{2}\) to transfer, process, and pack all the streams involved in steps \(S_{0}-S_{5}\). Now, assume that there are two task migrations. In our scheme, to achieve synchronization, we start them immediately after transferring the streams for \(S_{5}\). Thus, we always kill the tasks found in the former hosts of the migrated tasks, after the completion of the scheduled communication steps and after the completion of the task migration. The nodes that will accommodate the migrated tasks are determined as shown in Section 4. The migrated tasks are also transferred using the communication scheme described in Section 3 and impose at most (assuming these migrations have the maximum cost \(B_{1}\) plus an extra overhead \(B_{7}\) for the checkpoints) an extra latency of \(\rho B_{1}+\rho B_{7}\). An approximation to the total cost \(TC\) is:  
\[TC=(\rho+2)B_{1}+(k-2)B_{4}+B_{5}+B_{6}+B_{2}+B_{3}+\rho B_{7} \tag{15}\]  
where \(k\) is the number of communication steps and \(\rho\) is the number of times migrations are needed. Recall that, by employing this pipelined organization, some processing/packing costs are actually \"absorbed\" resulting in reduced overall delays. This will be shown in the next section.