## 3 Flow Table Overflow with Different Switches  
Figure 1 shows a simple linear network using SDN that has switches with flow tables of different sizes. If the flow entry for the packet does not exist in the flow table of the switch when the packet is forwarded from a source to a destination, a new entry is generated by exchanging messages with the controller and inserted to the table. If multiple packets that have different flow entries are forwarded after some time, the flow table is filled with the generated entries. If the packet having a new flow entry is sent when the flow table is full, the flow table experiences table overflow. When this happens, the existing entries should be deleted from the flow table to generate and insert the new flow entries. The deletion and insertion is performed through multiple exchanges of messages between the switch and controller. If 100 packets with different flow entries are forwarded under the network environment, as shown in Figure 1, for example, 100 flow entries are generated and the switch whose flow table size is smaller than 100 experiences the flow table overflow. This leads to a flow entry replacement in the flow table. Figure 2 shows the process of deleting the existing flow entries and generating new ones when the flow table overflow occurs. If a switch receives a new packet when the flow table is full, the switch looks up a matching flow entry with the packet from the table. If there is no flow entry, the switch sends PacketIn message to the controller to generate it. The controller computes paths and sends FlowModify message to the switch to insert the flow entry to the table. PacketOut message is also sent to designate the destination of the packet. However, when the flow table is full, the existing flow entry should be deleted to insert the new flow entry. In order to do so, the switch selects a flow that seems not to be used any longer and replaces it with the new one. Then, it transmits the FlowRemoved message to the controller to notify the changed status of the flow table. Overall, the controller and switch exchange the messages four times in the process so as to update the flow table. The frequent flow entry replacement causes the overhead to the controller and switch so that the replacement should be minimized to reduce the network overhead in the SDN. Figure 3 is an example of inefficient flow entry replacements when applying the LRU scheme to decide the flow entry to delete. In the figure, \(F\_ID\) represents the identifier to distinguish the flow entry and Time representing matching time of the flow entry. Let us assume that Flow \(C\) and \(D\) are the ones related with the multimedia services and are generated repeatedly unlike the web traffic. In the figure, Flow \(A\) and \(B\) are inserted at \(t_{0}\). Then Flow \(C\), \(D\) and \(E\) arrive at \(t_{1}\) and entries corresponding to the flows are generated at the flow table. When Flow \(C\), \(D\) and \(E\) arrive again at \(t_{2}\), they match the existing entries. Figure 1: The Software Defined Network (SDN) comprising switches with different sizes of the flow tables. Figure 2: Flow table updating process in the SDN. When Flow \(F\) and \(G\) arrive at \(t_{3}\), Flow \(A\) and \(B\) are deleted and Flow \(F\) and \(G\) are inserted according to the LRU scheme. After Flow \(H\) and \(I\) arrive at \(t_{4}\), Flow \(C\) and \(D\) are deleted from the current flow table by the LRU scheme. Finally, Flow \(E\) and \(F\) are deleted and Flow \(C\) and \(D\) are inserted when Flow \(C\) and \(D\) arrive again at \(t_{5}\).This example shows that Flow \(C\) and \(D\) are deleted from the flow table by generation of other flows although they are related with the multimedia services that are repeatedly used. Consequently, the overhead of the switch and controller increased by exchange messages to generate the flow again and the user QoS falls.