## 7 The TFL-Free Property
### Algorithm for TFL-Free SDN Updating
#### 7.2.1 Algorithm Overview
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Message/Packet** & \(\mathbf{CI_{mp}}\) & **Delivery Condition** & \(\mathbf{CI_{rp}}\) \\ \hline Reception of the delete update message by \(rp_{src}\) & & \\ \(m_{1}\) & \(CI_{m_{1}}\) & Delivered (\(\mathbf{\check{\check{\check{\check{\check{\check{\check{\check{\check{\check{\check{\check{  \check



## 9 Discussion

The problem of TFL during updates was intensively attacked by using different techniques. The proposed solutions can be classified into four approaches: ordered update, n-phase commit update, timed update, and the causal update (see Section 4 for more details). Although previous works have reached loop-free updates, they have not achieved effective and efficient solutions. We refer to the trade-off between ensuring TFL-free updates and performing updates with tolerable computational cost. To achieve a better trade-off, an important consideration is how to reason about the modeling of TFL-free updates. In this context, while all previous works set up synchronous execution models to perform updates, our solution was based on an asynchronous model. This allowed getting rid of the strong assumptions and certain constraints that come with a synchronous execution model. Indeed, solutions based on strong assumptions tend to be less applicable. In regards to the ordered update approaches [12; 13; 14], such as the loop-free routing update algorithms proposed by [14], it has to be noticed that algorithms are centralized into the controller side to calculate updates. During each routing policy update, they perform updates in a free-loop manner by calculating the possible edges that can be updated without generating loops. To do so, the algorithms take forwarding graph properties (set of nodes, set of edges to be added, set of edges to be removed, etc.) as input. In the worst case, the algorithms require \(\mid\)number of new edge to be added \(\mid\)loop-free update steps to perform one routing policy update [14], which is very expensive in terms of update time and bandwidth. The fact that the controller should stop disseminating update messages at each k-step of an update until receiving acknowledgment messages from all involved switches means that the update requires extra time to be completed. Furthermore, acknowledgment messages result in bandwidth overhead. In contrast, our algorithm proposed to disseminate update messages in one-shot. As shown in Section 7.2, the only required treatment is to sort update messages by their match fields and arranging the dissemination of messages following a predefined order (see Algorithm 1). In addition, switches are not required to send acknowledgment messages to the controller as the proposed algorithm works with one-step update, and unlike [14], it does not need acknowledgment messages that confirm the reception of the disseminated messages in order to start another update step. Regarding the solutions based on the two-phase commit update [4; 16], they require that each switch maintains the entries of both policies (the initial and the final ones) during the transition synchronous phase. This may end by congesting the memories of switches. Even worse, this approach may not be feasible when the number of entries bypasses the memory limit size of the switches. Our proposed solution avoids such a problem since the update algorithm is based on the replacement of entries. Firstly, it consists of computing an order in which the switches should consume the delete entry update message prior to the add entry update message, instructed by the controller. Secondly, by ensuring the computed order of message execution through causal order delivery of messages/packets, no switch will have entries of both policies at the same time. As far as the one-phase commit update approach ez-Segway [17] is concerned, updating tasks are delegated to the switches, qualifying it as a decentralized approach. However, consistent updates are ensured through centralized calculus performed by the controller.