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

Return interval statistics of BGP updates.a, Schematic illustration of the BGP update return intervals. Shown are the intervals τ1 and τ2 calculated for threshold q = 1 and q = 2 respectively. b, Typical sequence of 500 BGP update return intervals for NTT, where q = 4, calculated for (magenta) original and (black) shuffled data. c, The distribution function Pq(τ) of BGP update return intervals of the NTT, calculated for different values of q. The inset depicts the average return interval  as a function of threshold q. d, Pq(τ) for BGP update return intervals of the NTT monitor calculated for q = 1. Original data is shown with red while shuffled data is shown with black. e, Scaled plots of the BGP return intervals for the NTT monitor. f, The mean conditional return interval  as a function of preceding return interval τ0 for the NTT monitor. Both  and τ0 are normalized with the mean return interval (). For BGP updates without memory we expect , as supported by the open symbols obtained for shuffled return interval data.
© Copyright Policy
Related In: Results  -  Collection

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

pone.0141481.g005: Return interval statistics of BGP updates.a, Schematic illustration of the BGP update return intervals. Shown are the intervals τ1 and τ2 calculated for threshold q = 1 and q = 2 respectively. b, Typical sequence of 500 BGP update return intervals for NTT, where q = 4, calculated for (magenta) original and (black) shuffled data. c, The distribution function Pq(τ) of BGP update return intervals of the NTT, calculated for different values of q. The inset depicts the average return interval as a function of threshold q. d, Pq(τ) for BGP update return intervals of the NTT monitor calculated for q = 1. Original data is shown with red while shuffled data is shown with black. e, Scaled plots of the BGP return intervals for the NTT monitor. f, The mean conditional return interval as a function of preceding return interval τ0 for the NTT monitor. Both and τ0 are normalized with the mean return interval (). For BGP updates without memory we expect , as supported by the open symbols obtained for shuffled return interval data.

Mentions: The appearance of long-range correlations in BGP update time series indicates that at a given time the state of a particular BGP router is determined by its previous states. Consequently, long-range correlations may imply the presence of memory effects in the inter-domain Internet routing. To probe for the latter we ask, what is a typical time interval τ separating two large events. Formally, we define a return interval τ(q) as a time separation between two consecutive events z(t1) and z(t2), such that z(t1) > q and z(t2) > q (see Fig 5a). The evidence of memory in BGP update time series is seen in Fig 5b, which displays typical sequence of 500 consecutive return intervals for the NTT monitor. The original return interval data (shown in magenta) is characterized by “patches” of extreme return intervals, while there is no such “patches” in the shuffled data (shown in black) obtained by randomizing the time-order of the original series of BGP updates.


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

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

Return interval statistics of BGP updates.a, Schematic illustration of the BGP update return intervals. Shown are the intervals τ1 and τ2 calculated for threshold q = 1 and q = 2 respectively. b, Typical sequence of 500 BGP update return intervals for NTT, where q = 4, calculated for (magenta) original and (black) shuffled data. c, The distribution function Pq(τ) of BGP update return intervals of the NTT, calculated for different values of q. The inset depicts the average return interval  as a function of threshold q. d, Pq(τ) for BGP update return intervals of the NTT monitor calculated for q = 1. Original data is shown with red while shuffled data is shown with black. e, Scaled plots of the BGP return intervals for the NTT monitor. f, The mean conditional return interval  as a function of preceding return interval τ0 for the NTT monitor. Both  and τ0 are normalized with the mean return interval (). For BGP updates without memory we expect , as supported by the open symbols obtained for shuffled return interval data.
© Copyright Policy
Related In: Results  -  Collection

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

pone.0141481.g005: Return interval statistics of BGP updates.a, Schematic illustration of the BGP update return intervals. Shown are the intervals τ1 and τ2 calculated for threshold q = 1 and q = 2 respectively. b, Typical sequence of 500 BGP update return intervals for NTT, where q = 4, calculated for (magenta) original and (black) shuffled data. c, The distribution function Pq(τ) of BGP update return intervals of the NTT, calculated for different values of q. The inset depicts the average return interval as a function of threshold q. d, Pq(τ) for BGP update return intervals of the NTT monitor calculated for q = 1. Original data is shown with red while shuffled data is shown with black. e, Scaled plots of the BGP return intervals for the NTT monitor. f, The mean conditional return interval as a function of preceding return interval τ0 for the NTT monitor. Both and τ0 are normalized with the mean return interval (). For BGP updates without memory we expect , as supported by the open symbols obtained for shuffled return interval data.
Mentions: The appearance of long-range correlations in BGP update time series indicates that at a given time the state of a particular BGP router is determined by its previous states. Consequently, long-range correlations may imply the presence of memory effects in the inter-domain Internet routing. To probe for the latter we ask, what is a typical time interval τ separating two large events. Formally, we define a return interval τ(q) as a time separation between two consecutive events z(t1) and z(t2), such that z(t1) > q and z(t2) > q (see Fig 5a). The evidence of memory in BGP update time series is seen in Fig 5b, which displays typical sequence of 500 consecutive return intervals for the NTT monitor. The original return interval data (shown in magenta) is characterized by “patches” of extreme return intervals, while there is no such “patches” in the shuffled data (shown in black) obtained by randomizing the time-order of the original series of BGP updates.

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