# BGP Neighbor Trust Establishment Mechanism Based on the Bargaining Game
## 5 Simulation and Efficiency Analysis
### Average Convergence Time  
In the BNTE-BG mechanism, we add the service quality attribute quotations and payoffs calculations during the TCP three-way handshake, which will cause a time delay. Therefore, adding the BNTE-BG mechanism to the BGP will have an impact on the convergence time. The average convergence time is related to the number of neighbor establishment instances \(\#sum\), the number of quotations \(\#quote\), the time spent in quotation calculation \(t_{quote}\), the number of dicker judgments \(\#dick\), and the time spent in dicker judgment \(t_{dick}\), etc. Assuming that the number of ASes in the network topology is \(N\), the maximum number of neighbor establishment times are \(\#sum=\frac{N*(N-1)}{2},\ N\geq 2\). In the BGP protocol neighbor establishment process, after the TCP connection is completed at the transport layer, it needs to exchange parameters through FSM. If exchanging parameters fails, the neighbor establishment will fail. Thus, a successful neighbor establishment has a probably. Assuming that the probability of a successful FSM is \(p\), then the convergence time increment model is as follows:  
\[\Delta\text{Time}=\text{ p*}\#\text{sum}*\left(\#\text{quote}*\text{t}_{ \text{quote}}+\#\text{dick}*\text{t}_{\text{dick}}\right),\]  
where \(\Delta Time\) represents the increase in convergence time after adding the BNTE-BG mechanism to the BGP. Before the average convergence time experiment, we analyze the influence of concession factor \(k\), the negotiation ability \(\delta\) and, the number of quotations \(T\) on \(k+(1-k)*(t/T)^{\delta}\) representing the concession of AS. By setting \(\delta\) = 0.8, we respectively examined the changes of \(k+(1-k)*(t/T)^{\delta}\) under \(k\) = 0.1, \(k\) = 0.5, and \(k\) = 0.9. The experimental results are shown in Figure 3; the greater the value of k, the greater the concession that AS will make, but the lower the concession rate. \begin{table}
\begin{tabular}{c c c} \hline \hline  & **Storage Overhead Per Router/Byte** & **Packet Length Increment/Byte** \\ \hline BNTE-BG & 20 & 5 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Storage increment of BNTE-BG. By setting k = 0.4, we respectively examined the changes of \(k+(1-k)*(t/T)^{\delta}\) under \(T=3\), \(T=5\) and \(T=7\). The experimental results are shown in Figure 4; the fewer the number of quotations, the greater the concession and concession rate of AS. We set \(k=0.4\) and examined the changes of \(k+(1-k)*(t/T)^{\delta}\) under \(\delta=0.1\), \(\delta=0.5\), and \(\delta=0.9\). The experimental results are shown in Figure 5; the greater the value of \(\delta\), the greater the concession that AS will make. When \(\delta=0.1\), \(k+(1-k)*(t/T)^{\delta}\) initially increases rapidly and then tends to level off. When \(\delta=0.9\), \(k+(1-k)*(t/T)^{\delta}\) increases at a steady speed. Therefore, \(AS\) can be divided into two types. When \(0<\ \delta<0.5\), the AS is eager to  
Figure 4: The influence of the number of quotations \(T\) on \(k+(1-k)*(t/T)^{\delta}\). Figure 3: The influence of concession factor \(k\) on \(k+(1-k)*(t/T)^{\delta}\). establish neighbor relations. When \(0.5\leq\delta<1\), the AS is calm and has enough patience to negotiate. In the average convergence time experiment, we use the CAIDA IPv4 Routed/24 Topology Dataset [24] and extract some subgraphs from it for experiments. The specific parameters were set as follows: the link delay was 0.6 s, \(p=0.9\), \(\delta=0.7\), \(k=0.5\), and \(T=3\). The purpose of the experiment is to investigate the changes in the average convergence time of BNTE-BG, BGP, and NS-BGP mechanisms as the size of the AS topology changes. The experimental results are shown in Figure 6.  
Figure 5: The influence of negotiation ability \(\delta\) on \(k+(1-k)*(t/T)^{\delta}\). Figure 6: Average convergence time. As the topology's scale expands and the number of neighbor establishments increases, the average convergence time of the BNTE-BG mechanism, BGP, and NS-BGP mechanism gradually increases.