# PrECast: An Efficient Crypto-Free Solution for Broadcast-Based Attacks in IPv4 Networks
## 6 Performance Analysis of PrECast
### Convergence Analysis
A complete graph on \(n\) vertices is denoted by \(K_{n}\). A graph \(G=(V,E)\) is said to be an \(r\)-partite graph (where \(r\) is a positive integer greater than one) if its vertex set can be partitioned as \(V=V_{1}\cup V_{2}\cup\cdots\cup V_{r}\), such that if \(uv\) is an edge of \(G\), then \(u\) is in some \(V_{i}\) and \(v\in V_{j}\) for some \(i\
eq j\). If \(uv\in E\) for every \(u\in V_{i}\) and \(v\in V_{j}\) for \(i\
eq j\), then \(G\) is called the complete \(r\)-partite graph. It is denoted by \(K_{n_{1},n_{2},\cdots,n_{r}}\), where \(|\ V_{i}|=n_{i}\). A subset \(M\) of the edge set \(E\) of a graph \(G=(V,E)\) is an independent edge set or matching in \(G\), if no two edges of \(M\) have a common vertex. A matching \(M\) is maximal if there is no other matching \(M^{\prime}\) such that \(|\ M^{\prime}\ |>|\ M\ |\). A maximal matching \(M\) is called a maximum matching if \(M\) has the maximum number of edges than any other matching. Let \(G=(V,E)\) be a graph. A set \(S\subseteq E\) is called an edge cover of \(G\) if every vertex of \(G\) is incident with at least one edge of \(S\). \(S\) is called a minimum edge cover of \(G\) if \(|\ S|\) is of minimum size among all edge covering of \(G\). Standard graph-theoretic terms not defined here can be found in Bondy and Murty [22]. As we mentioned before, if two hosts A and B are connected to the same switch that implements the PrECast protocol, then the ARP resolution issued by A for B will be handled by the switch itself. However, if B is connected to another switch and the <MAC, IP> binding for B is not available with the switch to which A is connected, the ARP request will be multicasted. Let \(T\) be the topology that consists of a distribution layer switch connected with \(m\) access layer switches \(S_{1}\), \(S_{2}\), \(\cdots\), \(S_{m}\). Let \(n_{1}\), \(n_{2}\), \(\cdots\), \(n_{m}\) be the number of hosts connected with these switches, respectively. Without loss of generality, we assume that \(n_{1}\ \leq\ n_{2}\ \cdots\ \leq n_{m}\). For the given topology \(T\) running PrECast, we construct a graph \(G=(V,E)\) as follows: The set of vertices of \(G\) comprises the hosts in the network. If \(uv\ \in\ G\) are connected in \(G\) if and only if the \(ARP\) resolution from \(u\) to \(v\) may result in a multicast, the necessary and sufficient condition for this to happen is that \(u\) and \(v\) must be connected to a different switch. Since this relation is symmetric, the resultant graph is an undirected graph. It is easy to see that the resultant graph is the complete \(m\)-partite graph \(K_{n_{1},n_{2},\cdots,n_{m}}\). For the rest of this section, \(T\) and \(G\) denote the above topologies. The following theorem establishes a relation between an edge covering of \(G\) and how all switches in \(T\) learn about the MAC address of all hosts in the network. Theorem 3.1: _Let \(S\ \subseteq\ E(G)\). \(S\) is an edge cover of \(G\) if and only if all the switches in the network learn the <MAC, IP> bindings of every hosts in the network through ARP resolution either from host \(u\) to \(v\) or from host \(v\) to \(u\) for all \(uv\ \in\ S\)._  
Proof: Let a host \(u\) be connected to a switch \(S\). For other switches in the network to know the MAC address of \(u\), either there must be an ARP request from \(u\) or to \(u\) that resulted in a multicast among switches. If there are \(r\)-pairs of hosts \(u_{i}\), \(v_{i}\) through which all switches learn the MAC address of every host in the network, then \(S=\{u_{i}v_{i}\ |\ 1\leq i\leq r\}\) is an edge cover of \(G\). Conversely, let \(S\ \subseteq\ E(G)\) be an edge cover of \(G\). Let \(u\) be any arbitrary vertex of \(G\). We can then find a \(v\ \in\ V(G)\) such that \(uv\ \in\ S\). By the definition of \(G\), the hosts representing \(u\) and \(v\) are not connected with the same switch. Thus, an ARP resolution either from \(u\) or from \(v\) towards the other host will result in a multicast.