# IDSMatch: A Novel Deployment Method for IDS Chains in SDNs +
## 4 IDSMatch: Deploying IDS Chains in SDN
It is not necessary to calculate the exact distance to determine that a point should be assigned to the first center if a point is substantially closer to it than to any other [43, 44]. In order to have balanced GroupFlows, there is some transferring of flows between GroupFlows, resulting in an even number of flows in each group. Eventually, there would be an equal number of flows in each GroupFlow. In the experiment section, we consider the number of flows and traffic rate \(r_{f}\) for balancing groups. The perfect matching method is performed based on the hop count between the GroupFlows and the heads and tails of the IDS chains. There is not any fixed connection between heads and tails. Perfect matching makes some cross-connection between heads and tails based on finding the best chain for GroupFlows. This algorithm returns a list of balanced groups and their matched IDS chain. This problem is NP-hard. To address it, we take an approach that relies on an approximation technique involving the reconfiguration of incoming flows using a modified version of the \(K\)-means clustering algorithm. We formulate the problem of grouping incoming traffic as an optimization problem with the primary aim of reducing overhead or minimizing costs. This issue is divided into two sub-problems: one involving the grouping of incoming traffic, and the other focused on IDS assignment. They can be formulated as follows. **Problem 1. ** The first objective is to group incoming traffic in a balanced manner to reduce transmission delay. Factors that should be considered when determining the appropriate grouping include the distance of flows to the cluster's centroid and the total amount of traffic flows in each cluster:  
\[ \begin{split}\text{minimize}&\sum_{F_{j}\in F} Cost(F_{j})\\ \text{subject to}& Cost(F_{j})=|F_{j}|\cdot\sum_{f \in F_{j}}r_{f}\end{split}  \tag{1}\]  
Here, \(Cost(F_{j})\) represents the cost of clustering incoming traffic. This cost represents the overhead of the controller due to the additional work required for grouping the incoming traffic. The cost is based on the total number of traffic flows and total traffic rate \(r_{f}\) in each cluster \(F_{j}\). For the purpose of simplification, we can assume that the value of \(r_{f}\) is equal to \(1\) in our calculations. **Problem 2. ** The secondary goal is to allocate an IDS chain to each GroupFlow \(F_{j}\) in a manner that reduces the overall count of malicious packets while guaranteeing that all traffic passes through an IDS chain prior to reaching its final destination. Given that the positions of IDS chains are pre-established, the problem can be formulated as follows:  
\[ \begin{split}\text{minimize}&\sum_{i\in I}Cost(I)\\ \text{subject to}& Cost(I)=\sum_{M_{ij}=1}R_{j}*\min(dis( F_{j},I_{i}))\\ & R_{j}=\sum_{f\in F_{j}}r_{f}\\ & 1\leq|I_{i}|.\end{split}  \tag{2}\]  
Here, we evaluate the cost associated with assigning a GroupFlow \(F_{j}\) to an IDS chain \(I_{i}\), denoted as \(Cost(I)\). This cost is determined by considering the cumulative traffic rate of each GroupFlow and the distance between the GroupFlow's centroid and the IDS chain. The traffic rate of the j-th GroupFlow is represented as \(R_{j}\), and the data rate of a flow \(f\) is denoted as \(r_{f}\). The distance between the IDS chain \(I\) and the GroupFlow \(F_{j}\) is quantified as \(dis(F_{j},I_{i})\), which signifies the number of hops between the cluster's head \(\overline{s}j\) and \(h_{i}\). The matrix \(Mj\), \(i\) is employed to indicate the assignment of each GroupFlow \(F_{j}\) to a specific IDS chain \(I_{i}\). **Theorem 2**. : _The proposed approach is a 3-approximation algorithm [45] for flows with different sources to different destinations in a network with some IDS chains._Proof. : The calculation of the 3-approximation ratio is based on the triangle inequality and the optimality of each matching stage. For each head node \(h\in V\), there is a corresponding tail node \(t\in V\), which is assigned in the first round of approach.