## 2 Materials and Methods
### Proposed Scheme
#### 2.2.2 System Design Details  
Since the proposed mechanism is implemented as a single application over the control plane, any modifications on the OpenFlow or core modules of the SDN controller are not required. The proposed system consists of three components: 2D counting Bloom Filter, Statistics Module, and Timeout calculation module. * 2-dimensional Counting Bloom Filter  
The 2-dimensional Counting Bloom Filter is devised to store and look up the historical statistics of flows, i.e., the number of packets for each flow during a certain amount of time. An original bloom filter is a probabilistic data structure for testing whether an element is a member of a set [11]. It feeds an element to k hash functions to get k positions in an array vector and sets the bits all the positions to one. To query whether an element is a member of the set, it checks if all the positions are set to one. If they are, the element is probably in the set. Otherwise, the element is definitely not in the set. Although a conventional bloom filter provides large data storing and fast look-up, it is not suitable for flow statistics because three types of information for each flow, i.e., the sender, receiver and packet count, must be stored. Therefore, we devise a 2-dimensional counting bloom filter to manage the historical statistics efficiently. It is a 2-dimensional extension of a counting bloom filter [12]. The 2D counting bloom filter is a kind of 2-dimensional counter as shown in Figure 5. While each position of a conventional bloom filter is 1-bit, each one of the 2D counting bloom filters is more than one bit for counting. In this work, we made it 8 bits to count up to 255. One more different thing is to calculate two positions, the column index and the row index. The source and destination of a flow decide the column index and the row index by a hash function, respectively. Then the packet count of the flow is added up to the indexed position. The size of the 2D bloom filter, i.e., the numbers of columns and rows, and the number of hash functions should be calculated based on the network size, i.e., maximum current users accessing a network, and the acceptable false positive with given conditions, which is described later. There are three operations in the 2D counting bloom filter: count, decline, and query as shown in Figure 5. The count operation is the packet number add-up process. This process records the number of packets matching a flow rule during a certain amount of time. The decline operation is called periodically and decreases the number of packets  
Figure 5: Operations of 2D Counting Bloom Filter. for each flow rule as time goes on. Even if a flow has 100 packets, the flow should be considered a new flow after a long period. The decline in operation reflects a reduction over time in the statistics. The query operation retrieves the statistics of the requested flow. Similar to the count operation, it calculates the column and row positions for the requested flow and obtains the number of packets at the position. * Statistics Module  
The statistic module takes charge of collecting and updating the statistics for all flows as shown in Figure 6a. After the connection is established by the handshake between a controller and switches, all flow rules are installed with a flag that makes SDN switches send a flow-removed message to the controller when flow rules expire. After a flow rule expires, the flow-removed message for the expired flow rule is forwarded to the statistics module via the controller. Then the statistics module extracts the packet count, duration, and source/destination information from the message. It updates AFD by Exponentially Weighted Moving Average (EWMA) and adds up the packet count to the corresponding position of the 2D counting bloom filter by the count operation. AFD is simply calculated as (1)  
\[AFD_{new}=\alpha*AFD_{old}+(1-\alpha)*duration \tag{1}\]  
where \(\alpha\) is a sensitive coefficient. The bigger \(\alpha\) makes AFD more sensitive to the current expired flow.