## 7 The TFL-Free Property
### Algorithm for TFL-Free SDN Updating
#### 7.2.1 Algorithm Overview
In the worst case, each component of a \(Cl_{rp}[j]\) (vector of the control information of the controller process) could have at most one tuple for each process. This was because there was no concurrent message sent from the controller to a switch, i.e., each update message was sent to a specific switch and not to others. Furthermore, each message only piggybacked control information corresponding to their match fields. Let us go back to the scenario example of Section 8, in Table 11, of control information \(Cl_{cp}\) presented in Appendix A. Messages of \(match_{2}\) do not piggyback control information of messages of \(match_{1}\). On the other hand, a component of a \(Cl_{rp_{i}}[j]\) (vector of the control information of a routing process) can have at most N tuples for each process, i.e., for each vector component. This occurs when a routing process should, for example, flood a data packet to all outgoing links. Therefore, \(O(N^{2})\) control information is required to be piggybacked with each message/packet. Concerning memory overhead, a routing process \(rp_{i}\) needs to store a vector \(Cl_{rp_{i}}[j]\) and a matrix \(Delivery_{i}\) of \(N\,X\,N\), which then requires \(O(N^{2})\) integers to be stored. In this work, we introduced a new approach to tackle the TFL SDN update problem based on distributed system principles. By means of this approach, we outperformed the-state-of-the-art by proposing a solution that was more suitable for the characteristics of the SDNs. Indeed, the solution was totally distributed, where the execution model was asynchronous, no global references were required, and it did not assume a message upper bound delivery. The aspects mentioned above favored the following points: (1) the system configuration with the proposed update mechanism aligned with the pure features of a distributed and asynchronous system; (2) the proposed update mechanism minimized the interaction of the controller with the switches during an update (update messages were sent in one shot per updating flow); (3) the controller was not the only network entity that calculated the update operations as the switches contributed in the calculation (based on the exchanged control information and the messages/packets delivery constraints ensured by the update mechanism). ## 10 Conclusions

A model of the TFL pattern based on causal dependencies in SDNs was presented. We characterized the TFL phenomenon in an OpenFlow-based SDN, by identifying the relevant events and conditions under which it could occur during updates. In Definition 6, we specified that a TFL occurred due to a violation of the causal order delivery of a data packet during the process to update flow tables. This updating process was performed through _FlowMod_ controller-to-switch messages of type _add_ and _delete_. Based on this abstraction, we proposed a causal consistent update algorithm oriented to ensure the TFL-free property. To demonstrate this, a proof of correctness of the algorithm was provided. Based on these results, we propose as a future work to extend our solution to manage temporal constraints by including the principle of \(\Delta\)-causal proposed by [PERSON] et al. in [31]. Furthermore, we would like to extend the study to other network invariant violation patterns. This study will allow us to answer whether ensuring causal dependencies will be sufficient to cover consistent network updates in SDNs. **Author Contributions:** Formal analysis, A.G., S.E.P.H., L.M.X.R.H., H.H.K. and A.H.K. ; Investigation, A.G., S.E.P.H., L.M.X.R.H., H.H.K. and A.H.K. ; Methodology, A.G., S.E.P.H., L.M.X.R.H., H.H.K. and A.H.K. All authors have read and agreed to the published version of the manuscript. **Funding:** This research received no external funding. **Acknowledgments:** This work is supported by the Mexican Agency for International Development Cooperation (AMEXCID). **Conflicts of Interest:** The authors declare no conflict of interest.