## 2 Materials and Methods
### Timeout Revisit and Intuition
#### 2.1.2 Intuition  
This work began with the intuition that an appropriate time-out value can avoid both flow table overflow and unnecessary control traffic. Figure 2 shows the intuition. Although a shorter timeout can make more available space in a flow table, it may result in excessive rule re-installation overhead caused by unnecessary control traffic as shown in Figure 2a. In contrast, a longer timeout is more likely to overflow a flow table as shown in Figure 2b since flow rules are not removed for a long time.  
The key point is how to decide the appropriate value of the timeout. Our strategy is to set a longer timeout to a more trustable flow, and we derive the index of trust from history under the assumption that a flow with more packets in the past is more trustable. Since attackers spoof a number of packets with different match fields, e.g., different source and destination IP addresses and ports, to make the rules for the flows overflow a flow table, the assumption is reasonable.  
For the strategy execution, we needed a tactic, how we can get the historical information for flows, and introduced a 2D counting bloom filter. Different from an original bloom filter, the 2D counting bloom filter has two dimensions, the source and destination identifiers as shown in Figure 3 in order to distinguish each flow. Each element has 8 bits to count the number of packets. When a flow arrives, the timeout of the flow is calculated based on the packet count recorded in the 2D bloom filter.  
We added one more feature that can enhance the performance, the Average Flow Duration (AFD) for timeout calculation. AFD is the average time how long flow rules stay in the flow table. Our strategy gives a new flow a short timeout, which works very well under attack. However, this might cause the rule re-installation overhead in a normal  
Figure 3: 2D Counting Bloom Filter Concept.  
Figure 2: Timeout: (**a**) A too-short timeout may incur unnecessary control traffic. Since the flow f1 has too-short hard timeout, each packet of f1 generates the control messages, packet-in/out. (**b**) A too-long timeout may overflow the flow table. Although there is no control message, the flow table overflow happens.  
situation since a normal but new flow without any record also has a short timeout at first. The new flow is removed in a short time, which makes more control messages sent to a controller. To handle this, we introduced AFD as a base of timeout. In a normal situation, even the flow rule for a new flow remains in the flow table for a longer time because of the AFD-based timeouts, which reduce packets in messages. Let us consider when attack packets are incoming. Since the purpose of attack packets is to occupy and overflow the flow table, the number of the attack flows is high but the number of packets in each attack flow is very low, which means the duration of each attack flow is short. As the attack flows dominate, AFD decreases gradually. The attack flows have a shorter and shorter timeout, and they finally are removed from the table shortly. On the other hand, normal flows can have a relatively long timeout because they have records in the past. Therefore, the excessive rule re-installation overhead in a normal situation can be avoided.  
In the next subsection, we describe the details of the proposed scheme, how this strategy is implemented and how timeouts are calculated.