# PrECast: An Efficient Crypto-Free Solution for Broadcast-Based Attacks in IPv4 Networks
## 6 Performance Analysis of PrECast
### Convergence Analysis
Based on this multicast, all switches in the network learn about the MAC address of both \(u\) and \(v\). The following corollary is immediate from the above theorem. Corollary 1: _Let \(S\ \subseteq\ E(G)\) be a minimum edge cover of \(G\) and \(k\ =\ |\ S\ |\). Then, exactly k ARP resolutions are needed in \(T\) for all switches in the network to learn the <MAC, IP> binding of every host in the network._  
We now focus our attention towards finding the minimum edge cover number for a complete \(m\)-partite graph. The following theorem is true for any graph without any isolated vertex. Theorem 3.2: _Let a graph \(G\) have no isolated vertices. Then, the cardinality of the minimum edge cover \(C\) of \(G\) is equal to the cardinality of the maximum matching \(M\) of \(G\) increased by \(\ |\ V(G)\ |\ -2\times\ |\ M\ |\)._  
Proof: Let \(M\) be a maximum matching of \(G\). Then, \(M\) saturates \(2\times\ |\ M\ |\) vertices. Thus, there are \(\ |\ V(G)\ |\ -2\times\ |\ M\ |\) unsaturated vertices of \(G\). Since \(M\) is a maximum matching, the set of \(M\)-unsaturated vertices of \(G\) forms an independent set. The maximum matching \(M\) can be extended to a minimum edge cover \(C\) of \(G\) by choosing an edge from \(E(G)-M\) for every \(M\)-unsaturated vertex. Thus, \(\ |\ C\ |=\ |\ M\ |\ +\ |\ V(G)\ |\ -2\times\ |\ M\ |\). The following two theorems are due to [PERSON] [23], who calculates the size of the maximum matching for a complete \(m\)-partite graph. **Theorem 3**. : _Let \(K_{m_{1},m_{2},\cdots,m_{n}}\) be a complete multipartite graph with \(m_{i}\) vertices in the \(i\)-th part labelled so that \(m_{1}\leq m_{2}\leq\cdots\leq m_{n}\). If \(m_{n}\geq m_{1}+m_{2}+\cdots+m_{n-1}\), then:_  
1. _The number of edges in any maximum matching_ \(M\) _is_ \(m_{1}+m_{2}+\cdots+m_{n-1}\)_._
2. _The maximum matching is obtained by connecting all vertices in the parts of_ \(m_{1},m_{2},\cdots,m_{n-1}\) _to_ \(m_{n}\)_._  
**Theorem 4**. : _Given any complete multipartite graph \(K_{m_{1},m_{2},\cdots,m_{n}}\) with \(m_{1}\leq m_{2}\leq\cdots\leq m_{n}\) and \(m_{n}<m_{1}+m_{2}+\cdots+m_{n-1}\), then any maximum matching will have \(\lfloor n/2\rfloor\) edges, where \(n=m_{1}+m_{2}+\cdots+m_{n-1}+m_{n}\)._  
Based on all the above theorems, we have the following results:  
**Theorem 5**. : _Let \(G=K_{n_{1},n_{2},\cdots,n_{m}}\) be a complete multipartite graph with \(n_{i}\) vertices in the \(i\)-th part labelled so that \(n_{1}\leq n_{2}\leq\cdots\leq n_{m}\). If \(n_{m}\geq n_{1}+n_{2}+\cdots+n_{m-1}\), then the number of edges in the minimum edge cover \(S\) is \(n_{m}\)._  
Proof. : Let \(M\) be a maximum matching. Then, from Theorem 4, \(\mid M\mid\) = (\(n_{1}+n_{2}+\cdots+n_{m-1}\)). Let \(S\) be a minimum edge covering for \(G\). From Theorem 3, \(\mid S\mid\) = \(\mid M\mid\) + \(\mid V\mid\) - \(\mid M\mid\) - That is, \(\mid S\mid\) = (\(n_{1}+n_{2}+\cdots+n_{m}\)) - (\(n_{1}+n_{2}+\cdots+n_{m-1}\)) = \(n_{m}\). **Theorem 6**. : _Let \(G\) be the complete multipartite graph defined above. If \(n_{m}<n_{1}+n_{2}+\cdots+n_{m-1}\), then the number of edges in the minimum edge cover of \(G\) is \(\lceil n/2\rceil\), where \(n=n_{1}+n_{2}+\cdots+n_{m}\)._  
Proof. : Let \(M\) be a maximum matching and \(S\) be a minimum edge covering for \(G\). From Theorem 5, \(\mid M\mid\) = \(\lfloor n/2\rfloor\). We prove this theorem based on whether the \(G\) has n odd or even number of vertices. Case 1. Let \(n\) be an even number, and \(n=2k\). Then, \(\mid M\mid\) = \(k\). Thus, \(\mid S\mid\) = \(k+2k\) - \(2k\) = \(k\). In this case, the maximum matching itself is a minimum edge covering for \(G\). Case 2. Let \(n\) be an odd number, and \(n=2k+1\). Then, \(\mid M\mid\) = \(k\). Thus, \(\mid S\mid\) = \(k+(2k+1)\) - \(2k\) = \(k+1\) = \(\lceil n/2\rceil\). In this case, there is only one vertex of \(G\) that is not saturated by the maximum matching \(M\). Thus, \(S\) contain edges of \(M\) along with one edge that is incident with the \(M\)-unsaturated vertex of \(G\).