## 7 The TFL-Free Property
### Algorithm for TFL-Free SDN Updating
#### 7.2.1 Algorithm Overview
Updatemessages are illustrated in Table 1. Table 1 shows piggybacked control information of update messages, and Table 2 depicts control information for future update messages. TFLs that occur when updating forwarding path related to \(match_{1}\): We will follow a packet \(pkt_{k}\) from the origin to its destination taking into consideration the routing tables of switches corresponding to the initial policy of \(match_{1}\) (colored with purple). Assuming that \(rp_{src}\) and \(rp_{n}\) update their flow tables, then \(rp_{src}\) forwards an ingoing matched data packet \(pkt_{k}\) to \(rp_{n}\) (see the dashed purple arrow between \(rp_{src}\) and \(rp_{n}\)). After delivering \(pkt_{k}\), \(rp_{n}\) forwards it to \(rp_{n-1}\), and the latter delivers \(pkt_{k}\) before updating its flow table. As a result, \(pkt_{k}\) ends in a TFL between \(rp_{n-1}\) and \(rp_{n}\) (see the dashed purple arrow between \(rp_{n}\) and \(rp_{n-1}\) and the solid purple arrow between \(rp_{n-1}\) and \(rp_{n}\)). If the last assumption is not the case, i.e., \(rp_{n-1}\) delivers \(pkt_{k}\) after having updated its flow table, then \(rp_{n-1}\) should forward \(pkt_{k}\) to \(rp_{n-2}\). The same risk that \(pkt_{k}\) enters into a TFL between \(rp_{n-2}\) and \(rp_{n-1}\) exists if \(rp_{n-2}\) delivers \(pkt_{k}\) before updating its flow tables. \(pkt_{k}\) may indeed enter into TFLs between all the subsequent \(rp\) pairs, i.e., until \(pkt_{k}\) reaches \(rp_{2}\), and then, the risk may arise between \(rp_{1}\) and \(rp_{2}\). How the update algorithm proceeds to capture and avoid TFLs: As already mentioned, in each hop, there is a risk of falling into a TFL during the update of the forwarding path. We will review how the initial condition and the algorithm prevent this from happening. Table 2 illustrates the behavior of the data packet \(pkt_{k}\), which interleaves with the disseminated update messages corresponding to \(match_{1}\). Note that in each hop, \(pkt_{k}\) gets a different identifier. In the first row, for example, \(pkt_{k}\) must travel from the \(Source\) switch to the switch \(S_{n}\). Later, in the following hop, \(pkt_{k}\) is forwarded from \(S_{n}\) to \(S_{n-1}\) (second row). This continues until \(pkt_{k}\) reaches the \(Destination\) switch. As mentioned above, before performing the update, the algorithm (see Section 7.2) begins with the initial condition by sorting update messages by their match fields and arranging the dissemination of messages as follows: all delete messages are disseminated before all add messages. We describe now the algorithmic part. Each disseminated message (see Table 1) piggybacks direct dependency information related to message(s), which directly depend(s) on it and correspond(s) only to their match fields. Table 1 shows the control information (\(CI_{m}\)) encapsulated into each message when sending it from the controller, and Table 2 illustrates the control information needed to be piggybacked for future messages. In Table 1, the vectors \(CI_{m}\) of tuples encapsulated into update messages are presented and referred to the messages that causally depend on the message, i.e., messages that should be delivered to a switch before the message in question, while Table 2 presents the vector of the controller \(CI_{cp}\) and the tuples stored just after sending each message and that should be encapsulated with the future messages. On the other hand, the control information piggybacked by \(pkt_{k}\) is built after delivering it in each hop. Upon receiving messages/packets (see Table 3), switches also receive the control information \(CI_{mp}\) related to messages and packets. After each delivery, new potential direct dependencies on subsequent messages/packets are added to a receipt switch \(CI_{rp}\). In this scenario, all add update messages sent to the intermediate routing processes \(rp_{1},rp_{2},\ldots,rp_{n}\) are delivered without any restriction as no message

Figure 6: Two forwarding path update scenarios from the same source to the same destination.