# Adaptive Data Synchronization Algorithm for IoT-Oriented Low-Power Wide-Area Networks
## 4 Adaptive File Synchronization  
The previous observations highlight the importance of a suitable parameter setup when dealing with file synchronization. However, in the literature, this issue seems to be handled in a somewhat general fashion, without properly considering how some aspects, such as the file update percentage, may significantly impact the protocol performance. Unfortunately, this kind of approach turns out to be inefficient in the IoT context with different connected entities exchanging different types of data, giving rise to heterogeneous and hardly predictable data traffic. For these reasons, we propose an adaptive _rsync_-based file synchronization algorithm where the chunk size is dynamically tuned based on update distribution within the file, to optimize the number of literal bytes and tokens to be transmitted. Furthermore, the chunk dimension drives the choice between a signature-based or signature-free approach to be used. Before detailing the algorithm, we summarize the following remarks about the original _rsync_ mechanism:  
* By referring to Figure 2, the search for matching chunks in \(F_{DIoT}\) is performed by using a \(d\)-bytes sliding window \(B_{DIoT,k}\) identified through the index of its first byte \(k\) (in Figure 2 the window moves from left to right, that is from first byte to last). As long as no matchings are found, the scanning proceeds by shifting the sliding window by a single position (\(k\) is incremented by a one unit). On the other hand, if the current chunk matches, the sliding window is moved by \(d\) positions (\(k\) is incremented by \(d\)). * If the chunk \(B_{DIoT,k}\) matches, a token is generated. Specifically, a token is an index reporting the position of the matched chunk within the file, therefore it will be represented exactly by the corresponding index \(k\). An example of this occurrence is reported in Figure 2(a), representing a portion of the scanned file \(F_{DIoT}\). The sub-chunks in green refer to the bytes that are not changed with respect to the previous version of \(F_{DIoT}\). In that case, the chunk \(B_{DIoT,k}\) matches, therefore a token with index \(k\) is created. Then the file scanning continues considering the window \(B_{DIoT,k+d}\). That chunk is matching too, leading to the generation of another token, identified by \(k+d\). * The generic chunk \(B_{DIoT,k}\) is not matching if containing _at least_ one single byte that is new with respect to the previous file version. This occurrence is described in Figure 2(b)-c, where the new bytes are marked in red. Specifically, in Figure 2(a) the chunk \(B_{DIoT,k}\) is matching, but the following \(B_{DIoT,k+d}\) is not because the \((k+d)\)-th byte is a new one. Consequently, the \((k+d)\)-th byte is added to the list of literal bytes to be sent to the cloud for update, and the sliding window is shifted by a single position. The next chunk \(B_{DIoT,k+d+1}\) is recognized as known, therefore the relating token with index \(k+d+1\) is sent. Regarding the case of Figure 3b, the new byte is _placed_ at the end of \(B_{DIoT,k+d}\), hence 4 single shifts are necessary before finding another matching chunk \(B_{DIoT,k+2d}\). Interestingly, considering the generic chunk \(B_{DIoT,j}\), as the file scanning moves on from the left to the right (that is, \(j\) increases from \(k+d\) to \(k+2d\)), the new byte slides from the right to the left within \(B_{DIoT,j}\) until it completely moves out when \(j=k+2d\). By doing so, the bytes from the \((k+d)\)-th to the \((k+2d-1)\)-th one are _all_ judged as new and sent to the cloud. Actually, it would not have been necessary to transmit the bytes from the \((k+d)\)-th to the \((k+2d-2)\)-th one since they are not new, but in that case the size of the chunk \(d\) is too large, unavoidably leading to the transmission of unnecessary, redundant literal bytes. Let us note that the examples in Figure 3a,b consider only a single byte to be updated; however, the same discussion remains valid even if multiple new bytes are present in the file.