# IDSMatch: A Novel Deployment Method for IDS Chains in SDNs +
## 4 IDSMatch: Deploying IDS Chains in SDN
We summarize the steps of the proposed approach as follows:  
* Perform clustering for the pair \((s_{j},d_{j})\) using a distance metric defined as the sum of distances from \(s_{j}\) to the center \(\overline{s}_{k}\) and from \(d_{j}\) to the center \(\overline{d}_{k}\) within a cluster with its central point at \(c_{k}\). The distance between each host and the cluster center is computed as the cumulative number of hops. * Find balanced GroupFlows based on the amount of traffic for each group. * Employ the standard perfect matching technique to establish pairs between cluster centers and IDS chain configurations. Note that the connections between IDS chain heads and tails are not fixed and can be reconfigured as needed. The process of grouping flows is achieved by employing a modified variant of the \(K\)-means clustering technique. In Algorithms 1 and 2, the procedures for grouping incoming traffic into \(K\) clusters, creating balanced groups, and then matching the GroupFlows to the IDS chains are delineated. The initial step involves the random initialization of \(K\) cluster centroids. Subsequently, in the second step, the distances between each pair \((s_{j},d_{j})\) and  
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline  & \multicolumn{2}{c}{**Shortest Path**} & \multicolumn{2}{c}{**Balanced**} & \multicolumn{2}{c}{**Matching**} \\ \cline{2-7}
**Flow** & **Group** & **IDS** & **Group** & **IDS** & **Group** & **IDS** \\ \hline \(f_{1}\) & \((c_{1},6)\) & \((h_{1},t_{1}  
the centroid \(c_{k}\) are computed, and flows are assigned to their respective clusters based on these distances. Once all the flows have been clustered, the centroids are updated by identifying new centroids in a way that minimizes the sum of the shortest path distances from all flows in the cluster \(j\) to the new centroid. This iterative process continues until it reaches a stable state. When using any clustering method, it is important to ensure that the algorithm is converging in a meaningful way. To answer this question, we need to define a related optimization problem and make the concept of convergence more precise as per the reference [41]. Convergence in this context means that the algorithm has successfully completed the clustering or grouping of data points into \(K\) clusters. The algorithm will be deemed to have correctly grouped the data points if the difference in the values of the last two iterations is less than a specified threshold. The classical \(K\)-means algorithm is designed for the Euclidean distance, which is known to satisfy the triangle inequality as per reference [42]. ```
0: Flow set \(F\)
1: Initialize the \(K\) cluster centroids
2:Shortest Path
3:repeat
4:for each \((s_{f},d_{f})\) of flow \(f\in F\)do
5:for each centroid \(c_{k}\)do
6:\(\bar{s}_{k}\leftarrow\) source of \(c_{k}\),
7:\(\bar{d}_{k}\leftarrow\) destination of \(c_{k}\)
8:\(j\leftarrow_{k}\{dis(s_{f},\bar{s}_{k})+dis(d_{f},\bar{d}_{k})\}\)
9:\(F_{j}\gets F_{j}\cup f\)
10:until Convergence
11:Balanced Clustering
12:for each cluster \(F_{j}\)do
13: Calculate number of members \(M_{j}=|F_{j}|\)
14: Calculate average number of members \(\overline{M}\)
15:for each cluster \(F_{j}\)do
16: Change the membership if \(M_{j}\) is not the same as \(\overline{M}\)
17: Find \(c^{\prime}_{j}\) as a new centroid based on new members
18:Perfect Minimum Bipartite Matching
19:Call Algorithm 2
20:return List of clusters assigned to IDS chains
```  
**Algorithm 1** Balanced flow grouping. In order to avoid redundant distance calculations, it is necessary to use triangle inequality in order to determine the bounds. Since most distance calculations using standard k-means are redundant, the optimized algorithm uses a more efficient calculation method. The distance between a point and a center does not need to be calculated in order to deter mine that the point should not be assigned to that center if it is far from the center.