## 7 The TFL-Free Property
### Algorithm for TFL-Free SDN Updating
#### 7.2.1 Algorithm Overview
or packet sent before them with a common destination exists. However, for example, the delivery of \(pkt_{k}\) with identifier \(pkt_{2}\) is left on standby (wait) by \(rp_{n-1}\) as \(pkt_{2}\) piggybacked the tuple \((cp,n-1)\), which means that the message disseminated from the controller \(cp\) with sequence number \(n-1\) should be delivered before \(pkt_{2}\) to \(rp_{n-1}\) (see Table 3). Once the message sent by \(cp\) with sequence number \(n-1\) is delivered, \(pkt_{2}\) can be delivered to \(rp_{n-1}\). The algorithm treats all \(pkt_{k}\) in the same way in the subsequent hops, i.e., \(rp_{n-2},...,rp_{1}\), if they reach them before the delivery of the delete messages. Therefore, any forwarding of \(pkt_{k}\) generated by an installation of an add update message will not be delivered by the next hop switch before the delivery of the corresponding delete message (if it exists), preventing any \(pkt_{k}\) from going back to a switch from which it was forwarded, avoiding having them enter TFLs during the update. \begin{table}
\begin{tabular}{c c} \hline \hline
**Message** & **Message Content** \\ \hline \multicolumn{3}{c}{Delete update messages that correspond to \(match_{1}\)} \\ \(m_{1}\) & \((cp,t_{cp}=1,(match_{1},delete),rp_{src})\) \\ \(m_{2}\) & \((cp,t_{cp}=2,(match_{1},delete),rp_{1})\) \\ \(m_{3}\) & \((cp,t_{cp}=3,(match_{1},delete),rp_{2})\) \\ \(...\) & \(...\) \\ \(m_{n-2}\) & \((cp,t_{cp}=n-2,(match_{1},delete),rp_{n-2})\) \\ \(m_{n-1}\) & \((cp,t_{cp}=n-1,(match_{1},delete),rp_{n-1})\) \\ \(m_{n}\) & \((cp,t_{cp}=n,(match_{1},delete),rp_{n})\) \\ \multicolumn{3}{c}{Delete update messages that correspond to \(match_{2}\)} \\ \(m_{n+1}\) & \((cp,t_{cp}=n+1,(match_{2},delete),rp_{src})\) \\ \(m_{n+2}\) & \((cp,t_{cp}=n+2,(match_{2},delete),rp_{n})\) \\ \(m_{n+3}\) & \((cp,t_{cp}=n+3,(match_{2},delete),rp_{n-1})\) \\ \(...\) & \(...\) \\ \(m_{n+m}\) & \((cp,t_{cp}=n+m,(match_{2},delete),rp_{2})\) \\ \(m_{n+m+1}\) & \((cp,t_{cp}=n+m+1,(match_{2},delete),rp_{1})\) \\ \multicolumn{3}{c}{Add update messages that correspond to \(match_{1}\)} \\ \(m_{n+m+2}\) & \((cp,t_{cp}=n+m+2,(match_{1},add),rp_{src})\) \\ \(m_{n+m+3}\) & \((cp,t_{cp}=n+m+3,(match_{1},add),rp_{n})\) \\ \(m_{n+m+4}\) & \((cp,t_{cp}=n+m+4,(match_{1},add),rp_{n-1})\) \\ \(...\) & \(...\) \\ \(m_{n+m+k+1}\) & \((cp,t_{cp}=n+m+k,(match_{1},add),rp_{2})\) \\ \(m_{n+m+k+1}\) & \((cp,t_{cp}=n+m+k+1,(match_{1},add),rp_{1})\) \\ \multicolumn{3}{c}{Add update messages that correspond to \(match_{2}\)} \\ \(m_{n+m+k+2}\) & \((cp,t_{cp}=n+m+k+2,(match_{2},add),rp_{src})\) \\ \(m_{n+m+k+3}\) & \((cp,t_{cp}=n+m+k+3,(match_{2},add),rp_{1})\) \\ \(m_{n+m+k+4}\) & \((cp,t_{cp}=n+m+k+4,(match_{2},add),rp_{2})\) \\ \(...\) & \(...\) \\ \(m_{n+m+k+j}\) & \((cp,t_{cp}=n+m+k+j,(match_{2},add),rp_{n-2})\) \\ \(m_{n+m+k+j+1}\) & \((cp,t_{cp}=n+m+k+j+1,(match_{2},add),rp_{n-1})\) \\ \(m_{n+m+k+j+2}\) & \((cp,t_{cp}=n+m+k+j+2,(match_{2},add),rp_{n})\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Update messages calculated for updating \(P_{rp}\) that correspond to \(match_{1}\) and \(match_{2}\). \begin{table}
\begin{tabular}{c c c} \hline \hline
**Packet \(\mathbf{pkt_{k}}\)** & **Packet Content** \\ \hline \(pkt_{1}\) & \((rp_{src},t_{rp_{src}}=1,(match_{1},data),rp_{n})\) \\ \(pkt_{2}\) & \((rp_{n},t_{rp_{n}}=1,(match_{1},data),rp_{n-1})\) \\ \(pkt_{3}\) & \((rp_{n-1},t_{rp_{n-1}}=1,(match_{1},data),rp_{n-2})\) \\... & \\ \(pkt_{n}\) & \((rp_{2},t_{rp_{2}}=1,(match_{1},data),rp_{1})\) \\ \(pkt_{n+1}\) & \((rp_{1},t_{rp_{1}}=1,(match_{1},data),rp_{dst})\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Packets interleaving with update messages that correspond to \(match_{1}\).