# PrECast: An Efficient Crypto-Free Solution for Broadcast-Based Attacks in IPv4 Networks
## 6 Performance Analysis of PrECast
### Convergence Analysis  
One of the optimization schemes available to reduce the number of ARP broadcast requests is to cache the recent <MAC, IP> bindings. If the MAC address of the recently-received ARP-reply is needed at a later point in time, it can be retrieved from the cache. According to the standard, all active hosts on the network hearing an ARP broadcast from Host A should update their own ARP cache entry for Host A. Even though this feature potentially reduces the number of ARP broadcasts in the network, it poses a serious security problem. Thus, several operating systems do not support this feature. Furthermore, any unsolicited ARP reply will be silently dropped. In the traditional ARP process, the ARP cache table is empty for every host during the startup. Every time a host issues an ARP resolution, it adds an entry to the ARP cache table. There are no more ARP broadcasts in the network under the following two conditions:  
1. Every host knows about the MAC address of all other hosts in the network. 2. All hosts know about the MAC address of other frequently-communicating hosts in the network. Condition (1) is a stronger condition and includes Condition (2). There is no need for every host to know about all other hosts in the network. Thus, the ARP convergence mostly depends on Condition (2). For the completeness of the paper, we analyse both of these conditions. Let us assume that there are \(r\) frequently-used hosts in the network (like default gateway, DNS server, and so on). Let an arbitrary host \(A\) need the <MAC, IP> binding for Host B. Host A will issue an ARP broadcast, only when the MAC address is not available in A's ARP cache table. Thus, the probability of Host A issuing an ARP broadcast for Host B is \((n-1-t)/(n-1)\), where \(t\) is the number of ARP entries present in A's ARP-cache table at the time of a request. Initially, when [PERSON]'s ARP-cache table is empty, this probability is one. When there is only one host in the network not known to A, this probability is \(1/(n-1)\). When the remaining \(n-1\) host's <MAC, IP> bindings are available with a host, then this probability is zero. After this stage, Host A will not issue any ARP broadcast. The convergence time is the time it takes for this probability to change from one to either \(1/(n-1)\) or \((n-r)/(n-1)\), depending on whether we are interested in Condition (1) or (2). The quickest convergence happens when every ARP resolution results in a broadcast message and a new entry is added to the ARP cache table of a host. In order to keep the ARP-cache fresh, it has a time-out value. The time-out process is discussed in the later part of this paper. In the absence of any time-out:  
1. The quickest time in which Host A knows about the remaining \((n-1)\) hosts in the network is \((n-1)/\lambda\), where \(\lambda\) is the arrival rate of the ARP-requests with the probability \(\prod_{i=1}^{n-1}(\frac{n-i}{n-1})\). 2. The quickest time in which Host A knows about all the frequently-used \(r\) hosts in the network is \(r/\lambda\) with the probability \(\prod_{i=1}^{r}(\frac{n-i}{n-1})\). We now analyse the convergence of PrECast. We assume that there are \(n_{1}\), \(n_{2}\), \(\cdots\), \(n_{m}\) number of hosts connected with each access-layer switch, respectively. We analyse the quickest convergence of PrECast through edge covering for graphs. Before we establish a bijective relation between PrECast and edge covering, we define some of the standard graph-theoretic terminologies used in this paper. A graph \(G\) consists of a finite non-empty set \(V=V(G)\) of vertices together with a set \(\mathrm{E}=\mathrm{E}(\mathrm{G})\) of unordered pairs of distinct vertices of V. The pair \(e=\{u,v\}\) of vertices in \(E\) is called an edge of \(G\). We also write an edge \(e=\{u,v\}\) as \(e=uv\). If \(e=uv\in E\), then \(u\) and \(v\) are called adjacent vertices and \(e\) is incident with each of its two vertices \(u\) and \(v\). If every pair of vertices of a graph is adjacent, it is then called a complete graph.