## 7 The TFL-Free Property
### Algorithm for TFL-Free SDN Updating
#### 7.2.1 Algorithm Overview
**Input:** Ingoing data packets  
1: \(t_{rp_{i}}:=0\), \(CI_{rp_{i}}[j]=\{\}\)\(\forall j:1\ldots N\)  
2: \(t_{rp_{i}}:=t_{rp_{i}}+1\)  
3: \(pkt=(rp_{i},t_{rp_{i}},header,data,rp_{j})\)  
4: \(FwdP(pkt,CI_{rp_{i}})\)  
5: \(CI_{rp_{i}}[j]:=(rp_{i},t_{rp_{i}})\)```
0: OpenFlow messages sent from the controller and in-fly data packets
1:\(Delivery_{rp_{j}}[i,k]=0\)\(\forall i,k:1\ldots N\), \(CI_{rp_{j}}[i]=\{\}\)\(\forall i:1\ldots N\)
2:\(RecMP(mp=(p_{i},t_{i},content,p_{j},CI_{mp}))\) (the content may be an OpenFlow message or a packet)
3:\(wait\) (\(\forall k\) (\(k,x\)) \(\in\)\(CI_{mp}[j]\)\(|\)\(Delivery_{j}[k,j]\geq x\))
4:\(DlvMP(mp)\)
5:\(Delivery_{j}[i,j]:=t_{mp}\)
6:\(\forall k\)\(|\)\((k,y)\)\(\in\)\(CI_{mp}[i]\): \(Delivery_{j}[k,i]:=max(Delivery_{j}[k,i],y)\)
7:\(CI_{j}[j]:=(CI_{j}[j]\cup_{max}\)\(\{i,t_{mp}\})\)\(-_{max}\)\(CI_{mp}[j]\)
8:\(\forall p_{k}\in P\)\(|\)\(k\
eq i,j\): \(CI_{j}[k]:=CI_{j}[k]\cup_{max}CI_{mp}[k]\)
9:\(\forall p_{k}\in P\)\(|\)\(k\
eq j\):
10:\(\forall(l,x)\in C\)\(I_{j}[k]\)
11:if \(Delivery_{j}[l,k]\geq x\)then
12: delete (\(l,x\)) from \(CI_{j}[k]\)
```

**Algorithm 3** Switch message/packet reception. #### 7.2.2 Data Structures

In the algorithm, each process \(p_{i}\in P\) maintains a vector of control information \(CI_{i}\) of length \(N\) to store direct dependency information (\(N\) is the number of processes). Each element of \(CI_{i}\) is a set of tuples of the form \((process_{id},logical_{clock})\). For instance, let \(CI_{i}\) be the vector of a process \(p_{i}\) such that \((k,t)\in CI_{i}[j]\) (\(i\
eq j\)). This implies that any message sent by a process \(p_{i}\) should be delivered to \(p_{j}\) after the message \(mp\) of sequence number \(t\) sent by \(p_{k}\) has been delivered to \(p_{j}\). Furthermore, each process \(rp_{i}\) maintains an \(N\times N\) integer matrix \(Delivery_{i}\) to track dependency information. Each matrix \(Delivery_{i}\) records the messages of the last sequence number delivered to other processes. For instance, \(Delivery_{i}\)\([j,k]=t\) denoted that \(p_{i}\) knows that messages sent by process \(p_{j}\) to \(p_{k}\), whose sequence numbers are less than or equal to \(t\), have been delivered to \(p_{k}\). #### 7.2.3 Algorithm Details

Controller-to-switch message sending: This algorithm (see Algorithm 1) takes all update messages calculated by the controller that should be communicated to the routing processes as input. As a condition, all messages of type delete should be disseminated by the controller before all messages of type add. Before sending the messages, they should be grouped by _match_ (see Line 2). In each message send event, the logical clock of \(cp\) (denoted by \(t_{cp}\)) is incremented (see Line 3) to associate a timestamp with \(m\) (see Line 4). Upon sending \(m\), \(CI_{cp}\) is encapsulated into the send event (see Line 5). \(CI_{cp}[k]\) contains information about the direct predecessors of \(m\) with respect to messages sent to \(p_{k}\). After sending \(m\), \(CI_{cp}[i]\) is updated by adding \((cp,t_{cp})\) as a potential direct predecessor of future messages sent to \(rp_{i}\) after \(m\) (see Line 6). In general, \(CI_{cp}[i]\) contains delivery constraints of messages sent to \(rp_{i}\) by \(cp\). Switch-to-switch packet forwarding: This algorithm (see Algorithm 2) takes ingoing data packets as input. Before forwarding a packet \(pkt\) to an \(rp_{j}\), the logical clock of \(rp_{i}\) (denoted by \(t_{rpi}\)) is incremented (see Line 2) to associate a timestamp with \(pkt\) (see Line 3). Upon forwarding a \(pkt\) to its next hop, \(CI_{rp_{i}}\) is encapsulated into the forwarding event (see Line 4). \(CI_{rp_{i}}[k]\) contains information about the direct predecessors of \(pkt\) with respect to OpenFlow messages/packets sent to \(p_{k}\). After forwarding \(pkt\), \(CI_{rp_{i}}[j]\) is updated by adding \((rp_{i},t_{rp_{i}})\) as a potential direct predecessor of future packets sent to \(rp_{j}\) after \(pkt\) (see Line 5). The instructions of this algorithm are similar to the previous one.