Long-Lasting Sequences of BGP Updates

Abstract

The Border Gateway Protocol (BGP) is the protocol that makes the various networks composing the Internet communicate to each other. Routers speaking BGP exchange updates to keep the routing up-to-date and allow such communication. This usually is done to reflect changes in the routing configurations or as a consequence of link failures. In the Internet as a whole it is normal that BGP updates are continuously exchanged, but for any specific IP prefix, these updates are supposed to be concentrated in a short time interval that is needed to react to a network change. On the contrary, in this paper we show that there are many IP prefixes involved in quite long sequences consisting of a large number of BGP updates. Namely, examining ${\sim }30$ billion updates collected by 172 observation points distributed worldwide, we estimate that almost $30\%$ of them belong to sequences lasting more than one week. Such sequences involve $222\,285$ distinct IP prefixes, approximately one fourth of the number of announced prefixes. We detect such sequences using a method based on the Discrete Wavelet Transform. We publish an online tool for the exploration and visualization of such sequences, which is open to the scientific community for further research. We empirically validate the sequences and report the results in the same online resource. The analysis of the sequences shows that almost all the observation points are able to see a large amount of sequences, and that $53\%$ of the sequences last at least two weeks.

Appendices

Appendices

A The Discrete Wavelet Transform

The DWT series decomposition of the signal $w_{cp,\rho }\left( n\right)$ is defined as follows:

$$\begin{aligned} w_{cp,\rho }\left( n\right) =\sum ^{K}_{k=0}{c_{\ell ,k}{\phi }_{\ell ,k}(n)}+\sum ^{\ell }_{j=1}{\sum ^{K }_{k=0}{d_{j,k}{\psi }_{j,k}(n)}} \end{aligned}$$

Where $K+1$ is the number of samples of the signal. For the sake of simplicity we assume that $K=2^{\ell }-1$. Functions $\phi$ and $\psi$ are the father and mother functions respectively. The j and k indexes represent the scaling and translation factors respectively. Each (j, k) pair gives a wavelet coefficient, which can also be seen as the cross-correlation at lag k between the signal function to be decomposed and the $\psi$ wavelet basis function, described below, dilated by a scaling factor of $2^{j}$. The coefficients $c_{\ell ,k}$ are called approximation coefficients because derived by a low pass filtering, while the coefficients $d_{j,k}$ are called detail coefficients because derived by an high pass filtering. Function $\psi _{j,k}$ is defined as: ${\psi }_{j,k}\left( n\right) =2^{{-j}/{2}}\ \psi (2^{-j}n-k)$, where $\psi$ is the mother wavelet (also known as generic wavelet basis function) and can be chosen in a set of mother wavelet functions. For the duality principle the function $\phi$ is called father wavelet, or scaling function, because varying the j scaling index it gives a different resolution of the signal representation, creating a multi-resolution view of it. In the decomposition series formula above, $\phi _{\ell ,k}$ represents $\phi _{j,k}$ computed in $j = \ell$, that describes the last resolution level of the signal decomposition.

Once the signal has been represented in the DWT domain, we can compute its scalogram representation, that describes the percentage of energy for each wavelet coefficient. The scalogram can be arranged in a matrix form, denoted by P, with $\ell$ rows and $K+1$ columns. Each element of P is denoted by P[j, k].

Value P[j, k] is the normalized power of coefficient $d_{j,k}$ that, to further generalize the DWT, we will briefly represent with the Continuous Wavelet Transform formalism

$$P[j,k]=\frac{1}{2\pi \cdot C\cdot 2^{2j}}{\left| d_{j,k}\right| }^2 \,\,\,\,\,\,\,\,\,\text {where}\,\,\,\,\,\,\,\,\, C=\int _{-\pi }^{\pi }{\frac{{|\widehat{\psi } \left( \omega \right) |}^2}{\left| \omega \right| }d\omega }$$

is a normalization constant regarding the admissibility condition of a mother wavelet $\psi$, with $\widehat{\psi }(\omega )$ denoting the Fourier Transform of $\psi (n)$.

Formally, the normalization is chosen so that $\sum _{j}\sum _{k}{P[j,k]}=1$. This means that P[j, k] represents the percentage of the signal power at time k in the range of frequencies ${\varDelta f}_j$ defined below. According to the Nyquist-Shannon rule:

$$\begin{aligned} {\varDelta f}_j= \left[ \frac{f_s/2\ }{2^{j}},\frac{f_s/2\ }{2^{j-1}}\right) \end{aligned}$$

where $f_s$ is the sampling frequency.

B The Collector Peers and their Locations

The locations of CPs are reported in Table 1.

Table 1. List of collector peers. Locations are retrieved from [16].