Limits...
Long-Range Correlations and Memory in the Dynamics of Internet Interdomain Routing.

Kitsak M, Elmokashfi A, Havlin S, Krioukov D - PLoS ONE (2015)

Bottom Line: The Border Gateway Protocol (BGP) is responsible for discovering and distributing this reachability information to all ASes.In the view of the quick growth of the Internet there are significant concerns with the scalability of the BGP updates and the efficiency of the BGP routing in general.The presented statistical characterization of BGP update dynamics could serve as a basis for validation of existing and developing better models of Internet interdomain routing.

View Article: PubMed Central - PubMed

Affiliation: Department of Physics, Northeastern University, Boston, MA, United States of America.

ABSTRACT
Data transfer is one of the main functions of the Internet. The Internet consists of a large number of interconnected subnetworks or domains, known as Autonomous Systems (ASes). Due to privacy and other reasons the information about what route to use to reach devices within other ASes is not readily available to any given AS. The Border Gateway Protocol (BGP) is responsible for discovering and distributing this reachability information to all ASes. Since the topology of the Internet is highly dynamic, all ASes constantly exchange and update this reachability information in small chunks, known as routing control packets or BGP updates. In the view of the quick growth of the Internet there are significant concerns with the scalability of the BGP updates and the efficiency of the BGP routing in general. Motivated by these issues we conduct a systematic time series analysis of BGP update rates. We find that BGP update time series are extremely volatile, exhibit long-term correlations and memory effects, similar to seismic time series, or temperature and stock market price fluctuations. The presented statistical characterization of BGP update dynamics could serve as a basis for validation of existing and developing better models of Internet interdomain routing.

No MeSH data available.


Related in: MedlinePlus

Correlations in the BGP update times series.Fluctuations of the detrended BGP update time series as a function of window size.
© Copyright Policy
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC4631327&req=5

pone.0141481.g004: Correlations in the BGP update times series.Fluctuations of the detrended BGP update time series as a function of window size.

Mentions: All three methods indicate the presence of long-range correlations in the BGP update time-series (see Fig 4 and S1 Fig). Specifically, we find that DFA1 performed for NTT, IIJ and Tinet and AT&T indicates that fluctuations grow as a power-law with aggregation window size Δ, F(Δ) ∼ Δα, where α = 0.75 (Fig 4). To highlight the effects of long-range correlations in the BGP updates time series we also performed DFA1 for the randomized counterparts of the BGP updates (see Methods). In the randomized case we obtained Frandom(Δ) ∼ Δα with α = 0.5, which corresponds to the uncorrelated time series (Fig 4). Similar results are obtained by ACF and PS analysis. The autocorrelation function of the BGP updates decays as a power law over several orders of magnitude for all monitors, ACF(Δz) ∼ z−γ (S1a Fig). We obtain similar γ values for three monitors: γ = 0.5 for NTT, and γ = 0.4 for IIJ and Tinet monitors. The power spectrum density, S(f), also decays as a power-law with frequency, S(f) ∼ f−β, where β = 0.6 for all monitors (S1b Fig). We note that the obtained values of correlation exponents approximately conform with expected relations, γ = 1 − β, , and γ = 2(1 − α) [17, 29–31].


Long-Range Correlations and Memory in the Dynamics of Internet Interdomain Routing.

Kitsak M, Elmokashfi A, Havlin S, Krioukov D - PLoS ONE (2015)

Correlations in the BGP update times series.Fluctuations of the detrended BGP update time series as a function of window size.
© Copyright Policy
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC4631327&req=5

pone.0141481.g004: Correlations in the BGP update times series.Fluctuations of the detrended BGP update time series as a function of window size.
Mentions: All three methods indicate the presence of long-range correlations in the BGP update time-series (see Fig 4 and S1 Fig). Specifically, we find that DFA1 performed for NTT, IIJ and Tinet and AT&T indicates that fluctuations grow as a power-law with aggregation window size Δ, F(Δ) ∼ Δα, where α = 0.75 (Fig 4). To highlight the effects of long-range correlations in the BGP updates time series we also performed DFA1 for the randomized counterparts of the BGP updates (see Methods). In the randomized case we obtained Frandom(Δ) ∼ Δα with α = 0.5, which corresponds to the uncorrelated time series (Fig 4). Similar results are obtained by ACF and PS analysis. The autocorrelation function of the BGP updates decays as a power law over several orders of magnitude for all monitors, ACF(Δz) ∼ z−γ (S1a Fig). We obtain similar γ values for three monitors: γ = 0.5 for NTT, and γ = 0.4 for IIJ and Tinet monitors. The power spectrum density, S(f), also decays as a power-law with frequency, S(f) ∼ f−β, where β = 0.6 for all monitors (S1b Fig). We note that the obtained values of correlation exponents approximately conform with expected relations, γ = 1 − β, , and γ = 2(1 − α) [17, 29–31].

Bottom Line: The Border Gateway Protocol (BGP) is responsible for discovering and distributing this reachability information to all ASes.In the view of the quick growth of the Internet there are significant concerns with the scalability of the BGP updates and the efficiency of the BGP routing in general.The presented statistical characterization of BGP update dynamics could serve as a basis for validation of existing and developing better models of Internet interdomain routing.

View Article: PubMed Central - PubMed

Affiliation: Department of Physics, Northeastern University, Boston, MA, United States of America.

ABSTRACT
Data transfer is one of the main functions of the Internet. The Internet consists of a large number of interconnected subnetworks or domains, known as Autonomous Systems (ASes). Due to privacy and other reasons the information about what route to use to reach devices within other ASes is not readily available to any given AS. The Border Gateway Protocol (BGP) is responsible for discovering and distributing this reachability information to all ASes. Since the topology of the Internet is highly dynamic, all ASes constantly exchange and update this reachability information in small chunks, known as routing control packets or BGP updates. In the view of the quick growth of the Internet there are significant concerns with the scalability of the BGP updates and the efficiency of the BGP routing in general. Motivated by these issues we conduct a systematic time series analysis of BGP update rates. We find that BGP update time series are extremely volatile, exhibit long-term correlations and memory effects, similar to seismic time series, or temperature and stock market price fluctuations. The presented statistical characterization of BGP update dynamics could serve as a basis for validation of existing and developing better models of Internet interdomain routing.

No MeSH data available.


Related in: MedlinePlus