# On the Modeling of RTT Time Series for Network Anomaly Detection

Authors: Ye Kuang; Dandan Li; Xiaohong Huang; Mo Zhou
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Network anomalies can seriously influence the performance of networks and cause huge financial losses. Existing studies modeled the round-trip time (RTT) time series of each link and identified their abnormal patterns independently to detect the network anomalies. However, they rarely investigated the correlation among links, and they rarely considered the goodness of fit and complexity in model selection, which led to low timeliness and accuracy of detection. They failed to understand the impact of network anomalies. In this work, we propose the RTS detection approach to address these challenges. Specifically, we, firstly, propose a link clustering method to cluster the links into different classes based on the topological location of pairwise links and the similarity between their RTT time series. Then, for each class of links, we consider the goodness of fit and complexity in model selection and select the suitable model to analyze their RTT time series. Finally, we propose a detection method to detect the network anomalies by observing the deviation between the probability density distribution of the current RTT values and the reference value. We perform experiments with data from public measurement infrastructures like RIPE Atlas to evaluate the performance of our approach. The results show that our approach can not only reduce the detection time and improve the accuracy of detection effectively but also can roughly evaluate the impact of network anomalies.


---

## Body

## 1. Introduction

Network anomalies, such as link congestion, can seriously disrupt connectivity and degrade the performance of the network, which causes huge financial losses [1–3]. For example, Amazon found that 1% of their sales would be lost because of an additional 100 ms of delay in loading a web page [4, 5]. As a consequence, because of the destructive impact of network anomalies, their detection has become vital [6–8].Currently, the intuitive way to detect network anomalies is to measure the performance metric of the network [9, 10]. Since the round-trip time (RTT) has been proved to be a key metric to gain better insights into network performance [11–14], there are a few approaches proposed in the past to detect network anomalies by modeling the RTT time series [14–16]. Specifically, Zhang et al. proposed [15] to model the RTT time series of all links. They detected network anomalies by estimating the delay between the arbitrary end hosts. Fontugne et al. [16] leveraged log-normal distribution to model the RTT time series of all links and detected network anomalies by identifying the abnormal patterns of their RTT time series. To detect network anomalies and address the traffic asymmetry challenge, Fontugne et al. [14] leveraged normal distribution to model differential RTT time series and derived the reference range of RTT for all links by the Wilson Score [14]. Then, they detected the network anomalies if the RTT of any link is not located in their corresponding reference ranges.The above approaches detected the network anomalies by modeling the RTT time series of each link. However, they rarely investigated the correlation among links and the goodness of fit and complexity in model selection. As a result, they lacked the knowledge to answer even simple questions, such as “When does the network anomaly occur on a link?” “How many links will it affect?” and “Which statistical model is appropriate for analyzing the RTT time series of the links in detection area?” The answers to these questions could significantly benefit network managers to detect network anomalies.In detail, the benefits are mainly manifested in two aspects. Firstly, network anomalies usually affect multiple entities, and investigating the correlation between them can provide deeper insights into the network state. Specifically, when a network anomaly occurs on a certain link, it will affect the network state of its neighbors that share similar characteristics with it [17]. Hence, investigating the correlations of links in the detection area and obtaining the set of links with similar characteristics can help network managers roughly evaluate the impact of anomaly caused by any link in this set. Secondly, because of the stochastic nature of network measurements, the selection of statistical models directly affects the accuracy and timeliness of anomaly detection [18]. The model with higher goodness of fit can optimize the analysis of RTT time series and provide an accurate understanding of the current network condition for network managers [11]. Meanwhile, the model with lower complexity can reduce the computation time and prevent unnecessary computational costs [11].By considering these two benefits, this paper proposes a new approach for network anomaly detection in this paper, which is called RTS detection. Specifically, we, firstly, cluster the links with similar characteristics into different classes by considering their correlations. Then, by considering the goodness of fit and complexity of the statistical models, we select the appropriate model for each class of link and analyze their RTT time series. Based on the modeling results, we monitor the RTT of links constantly and calculate the deviation between the probability density of the RTT and the modeling results. Finally, we detect the network anomalies by observing whether the deviation exceeds the threshold. The main contributions are listed as follows:(i)
We propose a link clustering method using seeded region growing (SRG). Our method clusters the links into different classes based on the topological location of pairwise links and the similarity between their RTT time series.(ii)
We leverage the Bayesian Information Criterion (BIC) to select the appropriate model for each class of links, which includes three aspects, i.e., the number of samples, the number of parameters, and the goodness of fit.(iii)
We propose a detection method by employing the theory of Large Deviations (LD) and Sanov’s theorem. Our approach obtains the deviation of the probability density distribution between the current RTT values and the reference value and detects the network anomalies based on the threshold of deviations we set.The rest of this article is organized as follows: the following section provides a brief overview of network anomaly detection. Our approach and the architecture used for detecting the network anomaly have been explained in Section3. The performance of the detection approach is discussed in Section 4. Finally, we give a discussion in Section 5 and draw the conclusion in Section 6.


## 2. Related Work

Several approaches have been proposed to detect network anomalies by modeling the RTT time series of all links in the detection area [19, 20]. These approaches can be roughly divided into two categories according to the different statistical models they are based on, i.e., the approaches based on the normal distribution model and the approaches based on the log-normal distribution model, respectively.


### 2.1. Anomaly Detection Based on the Normal Distribution Model

The approaches based on the normal distribution model, such as [14, 15, 17], have been proposed to detect the network anomalies. These approaches utilize the normal distribution model to analyze the RTT time series of all links in the detection area and identify the abnormal pattern of RTT to detect the network anomalies. Specifically, Zhang et al. [15] proposed a detection approach named DS2, which leveraged the normal distribution to model the RTT time series of all links in the detection area. Then, they detected network anomalies by observing whether the RTT of links deviated obviously from the normal state. To detect network anomalies and address the traffic asymmetry challenge, Fontugne et al. [14] leveraged the normal distribution to model the differential RTT time series of all links in the detection area and derived the reference range of RTT for all links based on the Wilson Score [14]. Then, they detected network anomalies by observing whether the RTT of any link exceeded its corresponding reference range. However, this approach [14] is sensitive to the noise of measurements and has a high false positive rate. To address this challenge, Hou et al. [17] leveraged the normal distribution to model the RTT time series of all links and executed the RTT anomaly extraction algorithm twice to detect the network anomalies. This approach can minimize the influence of noise and exactly distinguish the network anomalies from “normal” RTT fluctuations.


### 2.2. Anomaly Detection Based on the Log-Normal Distribution Model

Although the detection approaches based on the normal model have achieved satisfactory results, some researchers have found that the RTT distribution of some links has multiple patterns, and the normal distribution model failed to distinguish these patterns, which affected the accuracy of anomaly detection [16]. To address this challenge, Fontugne et al. [16] leveraged the log-normal distribution to model the RTT time series of all links in the detection area and obtained multiple RTT distribution patterns of links. Then, they detected the network anomalies by monitoring the transition probability between the distribution patterns of each link.


### 2.3. Other Distribution Model

Detection approaches based on the normal distribution model or log-normal distribution model usually detect the network anomalies by monitoring the change of the median value of RTT. Recently, Daniel Perdices et al. [11] found that except the median value of RTT, focusing on the extreme value of RTT is also conducive to providing the theoretical support for analyzing the network anomalies [21, 22]. Hence, [11] leveraged two statistical models to analyze the RTT time series, i.e., the Generalized Extreme Value (GEV) model [23] and the Burr Type XII model [24], respectively. Experimental results showed that these two statistical models can effectively characterize the change of network delay. Although [11] did not use the modeling data for further network anomaly detection, it provided initial inroads towards our goal, i.e., leveraging these statistical models to analyze the RTT time series of links and detect the network anomaly.Note that in the phase of data modeling, existing work did not consider the goodness of fit and complexity of the statistical models, which affected the timeliness and accuracy of anomaly detection. Meanwhile, existing work rarely considered the correlation between links, and they detected the network anomalies by monitoring each link respectively, which increases the time and cost of detection in practice. On the contrary, analyzing the correlation between links can infer the state of partial links based on the state of other links sharing similar characteristics with them, which can roughly evaluate the impact of network anomalies.Based on the above analysis, we propose an approach to detect network anomalies by monitoring the RTT time series of links. We, firstly, cluster the links with similar characteristics into different classes by considering their correlations. Then, we select the appropriate model for each class of link and analyze their RTT time series. Finally, we detect the network anomalies by observing whether the relative entropy of the RTT of the link exceeds the threshold.


## 2.1. Anomaly Detection Based on the Normal Distribution Model

The approaches based on the normal distribution model, such as [14, 15, 17], have been proposed to detect the network anomalies. These approaches utilize the normal distribution model to analyze the RTT time series of all links in the detection area and identify the abnormal pattern of RTT to detect the network anomalies. Specifically, Zhang et al. [15] proposed a detection approach named DS2, which leveraged the normal distribution to model the RTT time series of all links in the detection area. Then, they detected network anomalies by observing whether the RTT of links deviated obviously from the normal state. To detect network anomalies and address the traffic asymmetry challenge, Fontugne et al. [14] leveraged the normal distribution to model the differential RTT time series of all links in the detection area and derived the reference range of RTT for all links based on the Wilson Score [14]. Then, they detected network anomalies by observing whether the RTT of any link exceeded its corresponding reference range. However, this approach [14] is sensitive to the noise of measurements and has a high false positive rate. To address this challenge, Hou et al. [17] leveraged the normal distribution to model the RTT time series of all links and executed the RTT anomaly extraction algorithm twice to detect the network anomalies. This approach can minimize the influence of noise and exactly distinguish the network anomalies from “normal” RTT fluctuations.


## 2.2. Anomaly Detection Based on the Log-Normal Distribution Model

Although the detection approaches based on the normal model have achieved satisfactory results, some researchers have found that the RTT distribution of some links has multiple patterns, and the normal distribution model failed to distinguish these patterns, which affected the accuracy of anomaly detection [16]. To address this challenge, Fontugne et al. [16] leveraged the log-normal distribution to model the RTT time series of all links in the detection area and obtained multiple RTT distribution patterns of links. Then, they detected the network anomalies by monitoring the transition probability between the distribution patterns of each link.


## 2.3. Other Distribution Model

Detection approaches based on the normal distribution model or log-normal distribution model usually detect the network anomalies by monitoring the change of the median value of RTT. Recently, Daniel Perdices et al. [11] found that except the median value of RTT, focusing on the extreme value of RTT is also conducive to providing the theoretical support for analyzing the network anomalies [21, 22]. Hence, [11] leveraged two statistical models to analyze the RTT time series, i.e., the Generalized Extreme Value (GEV) model [23] and the Burr Type XII model [24], respectively. Experimental results showed that these two statistical models can effectively characterize the change of network delay. Although [11] did not use the modeling data for further network anomaly detection, it provided initial inroads towards our goal, i.e., leveraging these statistical models to analyze the RTT time series of links and detect the network anomaly.Note that in the phase of data modeling, existing work did not consider the goodness of fit and complexity of the statistical models, which affected the timeliness and accuracy of anomaly detection. Meanwhile, existing work rarely considered the correlation between links, and they detected the network anomalies by monitoring each link respectively, which increases the time and cost of detection in practice. On the contrary, analyzing the correlation between links can infer the state of partial links based on the state of other links sharing similar characteristics with them, which can roughly evaluate the impact of network anomalies.Based on the above analysis, we propose an approach to detect network anomalies by monitoring the RTT time series of links. We, firstly, cluster the links with similar characteristics into different classes by considering their correlations. Then, we select the appropriate model for each class of link and analyze their RTT time series. Finally, we detect the network anomalies by observing whether the relative entropy of the RTT of the link exceeds the threshold.


## 3. Detection Approach Based on RTT Time Series

In this section, we propose a detection approach based on RTT time series. The approach is called RTS detection, which mainly consists of three parts:link clustering, model selection, and anomaly detection. The architecture is depicted in Figure 1. Next, we describe each part in turn.Figure 1
The architecture of RTS detection.


### 3.1. Link Clustering

Previous study found that the RTT of the link will be affected by its neighbor correlation when the network anomaly occurs [17]. Specifically, when the RTT of a link is affected by the network anomaly, the fluctuation of its RTT will also influence the RTT of the adjacent links sharing similar characteristics with this link. Therefore, clustering the set of links that affect each other in case of network anomalies can help the internet service providers (ISPs) to detect network anomalies by monitoring a small number of links and to roughly evaluate the impact of network anomalies in time.Based on the above analysis, we propose two rules to cluster two links in the detection area into one class, which are as follows: (1) the RTT time series between these two links must be similar, and (2) these two links need to be connected. Meanwhile, inspired by the SRG [25], this section proposes a link clustering method to cluster the links in the detection area. Specifically, we, firstly, extract the RTT data from traceroutes to form the RTT time series of each link. We then leverage Euclidean distance to calculate the similarity between the RTT time series of pairwise links. Finally, we cluster the links based on topological location and the similarity between their RTT time series.


#### 3.1.1. Data Preprocessing

Our analysis in this paper is based on the public datasets, i.e., RIPE Atlas dataset [26]. For a certain detection area D (e.g., a city), we obtain their corresponding traceroutes A. Dataset A contains each hop (address) from the probes (sources) to the destinations and the RTT at which the probe packet reaches to each hop. In this paper, we only focus on the links formed by each two adjacent nodes and the RTT of each link. One thing to note is that not all traceroutes can be used for our analysis: (1) some Atlas probes (anchors) cannot conduct measurement consecutively because of the failure. (2) Some traceroutes do not have complete information because a part of the router does not respond to probes.Hence, in the first step, we group the traceroutes of each probe into 30-minute time-bins and discard the probe that conducts less than 3 measurements in any bin according to [1]. This sanity check prevents us from making incorrect inferences using the probes that cannot conduct measurements consecutively. In the second step, we filter out the traceroutes with incomplete information. Finally, we determine the measurement period. Then, during the measurement period, we extract the RTT of each link at the same time interval (every 10 minutes) and form their RTT time series, respectively. This step ensures that each RTT time series has the same time interval and sequence length.


#### 3.1.2. RTT Time Series Similarity

After processing the traceroutes, we start to calculate the similarity between the RTT time series of pairwise links. Based on a comparative study using quantitative and large-scale assessment strategies, the authors in [27] provided two findings: (1) dynamic time warping (DTW) [28] is found to be consistently superior to the other studied approaches. (2) The Euclidean distance [29] remains a quite accurate, robust, simple, and efficient way of measuring the similarity between two time series.However, the work [17] suggested that DTW is not suitable for calculating the similarity of massive RTT time series because of its high computational complexity. Hence, in this paper, we adopt the Euclidean distance to calculate the similarity between the two time series. It is worth noting that work [27] showed that Euclidean distance is inapplicable for analyzing the time series with misaligned time steps and different sequence lengths. This paper addresses it effectively since we have ensured that each RTT time series has the same sequence length and time interval in the data processing phase.Next, we describe the process of similarity calculation. For convenience, we denote theith link in detection area D as li. During the measurement period, we continuously extract t RTT of li every 10 minutes and form the corresponding RTT time series of li, which is denoted as X1:ti=x1i,x2i,…,xki,…,xti. X1:ti is an independent and identically-distributed (i. i. d.) sequence [30], where xki represents the kth RTT of X1:ti (k∈1,2,…,t). Similarly, the RTT time series of lj can be expressed as X1:tj=x1j,x2j,…,xki,…,xtj. Based on the Euclidean distance, the similarity between li and lj is calculated as follows:(1)SX1:ti,X1:tj=1∑k=1txki−xkj21/2.Note that the larger theSX1:ti,X1:tj, the more the similarities between X1:ti and X1:tj. Given the similarity threshold Δ1, if the similarity between X1:ti and X1:tj satisfies the condition,(2)SX1:ti,X1:tj≥Δ1.We conclude thatli and lj are similar.


#### 3.1.3. Link Clustering Algorithm

Existing work showed that the RTT of links will be affected by their neighbor correlation when a network anomaly occurs [17]. Specifically, when a network anomaly occurs on a certain link, it will affect the RTT of its neighbors that share similar characteristics with it. It indicates that clustering the links with similar characteristics should not only consider the similarity between their RTT time series but also focus on the connected relation between links (i.e., topological locations). To achieve this, we propose a link clustering algorithm based on SRG. The pseudocode of the algorithm is shown in Algorithm 1.Algorithm 1: Link clustering.
Input: detection area D, dataset A;Output: the set of class C;(1)
Extract all the links inD from A,(2)
Randomly select a linkli in D as a seed,(3)
Extract the links connected withli in D, and denote the set of these links as Li,(4)
According to (1), calculate the similarity between the RTT time series of li and the RTT time series of each link from Li,(5)
if there is no link sharing similar characteristic with li (satisfies (2)), then(6)
Clusterli as a class,(7)
else(8)
Extract the links satisfying (2), and denote the set of these links as Bi (including li),(9)
end if(10)
Choose the links inBi that are not selected as seed before, and let each of them be a new seed, respectively,(11)
Extract the links inD that connect with each new seed, and for each link, we calculate the similarity between the RTT time series and the RTT time series of the new seed it connects with, respectively,(12)
if no link is similar to the new seed that connects with it, then(13)
Cluster all links ofBi into a class,(14)
else(15)
Put the links that are similar to the new seed intoBi,(16)
goto step 9,(17)
end if(18)
if all the links in D are clustered into their corresponding classes, then(19)
return the set of class C.(20)
else(21)
Filter the links inBi from D, and randomly select a link li from the remaining links,(22)
goto step 2,(23)
end ifAlgorithm 1 consists of four phases, and each phase is described as follows: in the first phase, for a certain detection areaD, we randomly select a link li as a seed and extract the links connected with it. The set of these links is denoted as Li. Then, we calculate the similarity between the RTT time series of li and the RTT time series of each link in Li. Next, based on the similarity results, we extract the links that satisfy (2) and denote the set of these links as Bi, where li belongs to set Bi.In the second phase, we choose the links inBi that are not selected as seed before and denote each of them as a new seed, respectively. Then, we extract the links in D that connect with each new seed, and for each link, we calculate the similarity of its RTT time series with the new seed it connects with. Next, based on the similarity results, we extract the links satisfying (2) and put them into Bi.In the third phase, we keep repeating the second phase until there is no link inD being similar with the new seeds. Then, we cluster all links of Bi into the same class. In the last phase, we filter the links in Bi from D and randomly select a link li from the remaining links. Then, we perform the previous three phases again in order. Finally, all links in D are clustered into C classes, and the kth class is denoted as Ck, which contains Mk links.


### 3.2. Model Selection

In practice, network managers have high requirements for the timeliness and accuracy of anomaly detection, and selecting an appropriate statistical model to analyze the measurements can improve the timeliness and accuracy of anomaly detection [11]. Hence, by considering the goodness of fit and complexity of the statistical models, this paper selects an appropriate statistical model to analyze the RTT time series of the links, aiming to reduce the detection time and improve the accuracy of detection.In this section, we, firstly, summarize the statistical models used in the existing approaches for anomaly detection. Then, for each class of links, we use the Bayesian information criterion (BIC) [31] to select the appropriate statistical model for them and leverage the model to analyze their RTT time series.


#### 3.2.1. Statistical Models for RTT

Leveraging the statistical model to analyze the RTT of links is an effective way to characterize the network condition. Hence, existing work has used different statistical models to analyze the RTT time series of links for anomaly detection. Next, we describe the statistical models that are widely used in turn.(1) Normal Model. The normal model is a common approach when coping with data analysis [32]. Previous works have demonstrated that the RTT distribution of the link roughly follows the normal distribution [14]. Hence, they leveraged the probability density function of the normal distribution to approximate the distribution of RTT measurements. The probability density function is computed as follows:(3)fx|u,δ=12πδ2e−x−u2/2δ2,where u is the mean value, and δ is the variance.(2) Log-Normal Model. A large number of cases demonstrate that the normal model achieves satisfying performance in describing the distribution of RTT measurements. However, recent studies [14] reported that the RTT distribution of some links is characterized by several distinct modes, and the normal model fails to distinguish these modes. To address this challenge, they leveraged the log-normal model to describe the distribution of RTT for these links [14]. The probability density function of log-normal distribution is computed as follows:(4)fx|u,δ=1xδ2πe−lnx−u2/2δ2,where u is the mean value, and δ is the variance.(3) GEV Model. Normal and log-normal models typically focus on the median of RTT measurements and ignore their extreme values. However, an extreme value is often closely related to the occurrence of anomalous events [21, 22]. Thus, analyzing the extreme value of RTT measurements is beneficial to provide theoretical support for the statistical analysis of anomalous events. The model widely used to analyze the extreme value of RTT data is the generalized extreme value (GEV) distribution [23]. Its probability density function is computed as follows:(5)fx|u,δ,ξ=1δ1+ξx−uδ−1/ξ+1e1+ξx−u/δ−1/ξ,where 1+ξx−u/δ>0, u is the location parameter, δ is the scale parameter (δ>0), and ξ is the shape parameter.(4) Burr Type XII Model. Similar to the GEV model, the Burr Type XII model can also be used to analyze the extreme value of RTT measurements [24]. Different from the GEV model, the Burr Type XII model is a flexible distribution model that can characterize multiple distribution patterns. Based on its flexibility, using the Burr type XII model to analyze RTT time series can reduce the noise and improve the accuracy of modeling. However, the modeling time of the Burr Type XII model is relatively long, which will affect the timeliness of anomaly detection. The probability density function of the Burr Type XII model is computed as follows:(6)fx|a,c,k=kc/ax/ac−11+x/ack+1,where c and k are the shape parameters, and a is the scale parameter. All the parameters should be greater than zero.


#### 3.2.2. Select the Appropriate Model

The above four statistical models can effectively characterize the distribution of RTT measurements but how to select an appropriate model to analyze the RTT time series of each class of links remains a challenge. Specifically, the RTT distribution of each class of link is not completely consistent. To reduce the detection time and improve the accuracy of detection, the statistical model should not only fit the RTT distribution of links but also have a low modeling time.Considering thatBayesian Information Criterion (BIC) is a well-known metric to evaluate the goodness of fit and complexity of the model [31], we leverage BIC to select the model with a high fitting degree and low complexity for each class of links. In detail, the fitting degree represents the accuracy of the model in characterizing the RTT measurements, and the complexity considers the influence of the number of links and model parameters on the modeling time.Without loss of generality, we take the classCk as an example to illustrate the process of model selection. We, firstly, leverage the four statistical models mentioned above to characterize the RTT distribution of the links in Ck and calculate the BIC value of each statistical model. Then, we select the statistical model with the smallest BIC value as the final model for Ck. The BIC value of the statistical model is computed as follows:(7)BIC=∑i=1IlogIK−2logLX1:tiI,where I is the number of links in Ck, K is the number of parameters of the model, and LX1:ti represents the maximum value of the likelihood function for the time series X1:ti. For the class Ck, the smaller BIC value of the model represents that the model has less complexity and can characterize the RTT distribution of the links in Ck more accurately.


### 3.3. Anomaly Detection

After determining the corresponding statistical model of each class of links, we propose a detection method based onlarge deviation theory [33] and Sanov’s theorem [30] to detect network anomalies. Next, this section describes the detection rationale and workflow of the detection method.


#### 3.3.1. Detection Rationale

Based on the large-scale measurement and long-term analysis, Jiang and Dovrolis [34] found that under the normal network state, the RTT of the link is basically in a stable state. In detail, [34] analyzed the RTT distribution of the links in the detection area based on different time scales (seconds, minutes, hours, days, months, and years). They found that under any time scale, the cumulative probability distribution of the RTT remained basically stable over time. These results proved that the distribution probability of the RTT of links is in a relatively stable range.Inspired by the results of [34], we, firstly, obtained the distribution probability of the RTT of each link under the normal network state. Next, we continuously monitored the RTT of links, and we believed that for each link, the frequency of occurrence for each value of RTT under the normal network state should be similar to its distribution probability we obtained before. Only during the network anomaly, the RTT of links will fluctuate obviously, resulting in a large deviation between the occurrence frequency of each value of RTT and its distribution probability we obtained under the normal network state.Based on the above analysis, an effective way to detect the network anomaly is by characterizing and analyzing the deviation between the occurrence frequency of each value of RTT and its distribution probability. Therefore, this section uses the large deviation theory to analyze this deviation and detects the network anomaly by observing whether the value of deviation exceeds the critical value.


#### 3.3.2. Workflow

Without the loss of generality, we take the linkli as an example to illustrate the workflow of detection method. We suppose that the link li belongs to class Ck. Firstly, we measure the RTT of li within t consecutive time intervals under the normal network state and obtain the RTT time series of li, which is denoted as X1:ti=x1i,x2i,…,xki,…,xti. Then, we extract each value of RTT in X1:ti and sort them in an ascending order manner, which forms the sequence Ri. Ri=r1i,r2i,…,rki,…,rni, where n represents the number of different RTT value in X1:ti, rki is the kth element of Ri, r1i is the minimum value of RTT in X1:ti, and rni is the maximum value of RTT in X1:ti.Next, we leverage four statistical models (mentioned in Section3.2) to analyze the links in Ck. According to the BIC value, we select the final statistical model for class Ck. Then, we use the final statistical model to analyze the links in Ck and obtain the probability density of each value in Ri. The sequence of probability density is denoted as Ui=u1i,u2i,…,uki,…,uni, where uki is the kth element of Ui, and it represents the probability density of rki. To compare the probability density with that under network anomaly, we denote Ui as the sequence that contains the reference value of RTT probability density of li.After determining the reference value of RTT probability density ofli, we still measure the RTT of li within t consecutive time intervals and obtain its RTT time series. The RTT time series is denoted as Y1:ti=y1i,y2i,…,ypi,…,yti, where Ypi is the pth element of Y1:ti. Then, for each value of Ri, (1) we calculate the number of occurrences that it appears in sequence Y1:ti, (2) divide the number of occurrences by t, and obtain its frequency of occurrence on Y1:ti. After obtaining the frequency of occurrence of each value in turn, we use these values to form the frequency sequence εi=ε1i,ε2i,…,εki,…,εni, where the kth element εki is computed as follows:(8)εki=1t∑p=1t1xkiYpi,k=1,2,…,n,where 1xkiYpi is the generating function of the event Ypi=xki. The function is defined as follows:(9)1xkiYpi=1,ypi=xki,0,ypi≠xki.Generally, the frequency of occurrence of each value inRi should be approximately equal to its corresponding probability density in sequence Ui, i.e., εi is approximately equal to Ui. However, the occurrence of network anomaly will lead to an obvious inconsistency between εi and Ui. The phenomenon of this obvious inconsistency is rare, and understanding the probability of this rare phenomenon is an effective method to detect network anomaly [35]. According to Sanov’s theorem [30], the probability is computed as follows:(10)Pi≈10−nHεi/Ui,where Hεi/Ui represents the relative entropy between εi and Ui. The relative entropy is computed as follows:(11)HεiUi=∑k=1nεkilog0.1εkiuki,where Hεi/Ui is used to describe the similarities between εi and Ui, i.e., the distance between them. The larger value of Hεi/Ui indicates that there is a lager deviation between the actual network state and normal state, and the probability of this phenomenon Pi is low. Actually, the RTT of links is stable over a longer period of time [36, 37]. Hence, for each link, the relative entropy between the measured value and reference value is small, and the probability Pi is always large. Only when a network anomaly occurs, the relative entropy increases, and the large deviation probability Pi will be much lower than the reference value in the normal state.Hence, for the linkli, we calculate the relative entropy between its measured value and its reference value. Then, we obtain its large deviation probability Pi. Given the threshold of large deviation probability Δ2, if Pi satisfies the condition, then,(12)Pi≤Δ2.We conclude that the network anomaly occurs in the linkli. Meanwhile, based on the analysis of correlation, we can roughly infer that the links in class Ck may be affected by this network anomaly.


### 3.4. Anomaly Detection Algorithm

Based on the analysis of Section III-A to Section III-C, we propose an anomaly detection algorithm based on the RTT time series in this section, which includes three phases: link clustering, model selection, and anomaly detection. The pseudocode of the algorithm is shown in Algorithm 2.Algorithm 2: Anomaly detection algorithm.
Input: detection area D, dataset A, times of the measurement t ;Output: network anomaly and its impact;Link clustering(1)
Extract all the links inD from A,(2)
Extract the RTT of links fromA during t consecutive time intervals, and form their RTT time series, respectively,(3)
Calculate the similarity between the RTT time series of pairwise links, and cluster the links intoC classes using Algorithm 1. The kth class is denoted as Ck, which contains Mk links,Model selection(4)
fork∈1,Cdo,(5)
Leverage four statistical models to analyze the RTT time series of the links inCk, and obtain the BIC value of each statistical model,(6)
Select the statistical model with the lowest BIC value as the final model ofCk,Anomaly detection(7)
fori∈1,Mkdo,(8)
Under the normal state, leverage the final model to analyze the RTT time series of linkli, and obtain the sequence Ui,(9)
Monitor the RTT of linkli during t consecutive time intervals, and obtain the sequence εi,(10)
Calculate the relative entropy betweenεi and Ui, and obtain the large deviation probability Pi,(11)
ifPi≤Δ2, then(12)
return network anomaly, and the network anomaly may affect all the links in class Ck.(13)
end if(14)
end for(15)
end for,In the phase of link clustering, we obtain the RTT time series of the links inD, and calculate the similarity between the RTT time series of pairwise links according to (1). Based on the topological location of pairwise links and the condition of similarity ((2)), we cluster the links in D into different classes.In the next phase, i.e., model selection, we, firstly, leverage four statistical models to analyze the RTT time series of the links in each class. Then, for each class, we calculate the BIC value of each statistical model and select the statistical model with the lowest BIC value as the final model of the class.In the phase of anomaly detection, we, firstly, determine the final model of each link based on the second phase. Secondly, for a certain link, we leverage its final model to analyze its RTT time series under the normal state and obtain its reference value of RTT probability density. Thirdly, we monitor the RTT of this link constantly and obtain the frequency of occurrence of each RTT value. Next, we calculate the relative entropy between the measured value and reference value and obtain the large deviation probability. Finally, if the large deviation probability is below the critical value we set, we conclude that the network anomaly occurs in this link, and the network anomaly may affect the links having the same class as this link.


## 3.1. Link Clustering

Previous study found that the RTT of the link will be affected by its neighbor correlation when the network anomaly occurs [17]. Specifically, when the RTT of a link is affected by the network anomaly, the fluctuation of its RTT will also influence the RTT of the adjacent links sharing similar characteristics with this link. Therefore, clustering the set of links that affect each other in case of network anomalies can help the internet service providers (ISPs) to detect network anomalies by monitoring a small number of links and to roughly evaluate the impact of network anomalies in time.Based on the above analysis, we propose two rules to cluster two links in the detection area into one class, which are as follows: (1) the RTT time series between these two links must be similar, and (2) these two links need to be connected. Meanwhile, inspired by the SRG [25], this section proposes a link clustering method to cluster the links in the detection area. Specifically, we, firstly, extract the RTT data from traceroutes to form the RTT time series of each link. We then leverage Euclidean distance to calculate the similarity between the RTT time series of pairwise links. Finally, we cluster the links based on topological location and the similarity between their RTT time series.


### 3.1.1. Data Preprocessing

Our analysis in this paper is based on the public datasets, i.e., RIPE Atlas dataset [26]. For a certain detection area D (e.g., a city), we obtain their corresponding traceroutes A. Dataset A contains each hop (address) from the probes (sources) to the destinations and the RTT at which the probe packet reaches to each hop. In this paper, we only focus on the links formed by each two adjacent nodes and the RTT of each link. One thing to note is that not all traceroutes can be used for our analysis: (1) some Atlas probes (anchors) cannot conduct measurement consecutively because of the failure. (2) Some traceroutes do not have complete information because a part of the router does not respond to probes.Hence, in the first step, we group the traceroutes of each probe into 30-minute time-bins and discard the probe that conducts less than 3 measurements in any bin according to [1]. This sanity check prevents us from making incorrect inferences using the probes that cannot conduct measurements consecutively. In the second step, we filter out the traceroutes with incomplete information. Finally, we determine the measurement period. Then, during the measurement period, we extract the RTT of each link at the same time interval (every 10 minutes) and form their RTT time series, respectively. This step ensures that each RTT time series has the same time interval and sequence length.


### 3.1.2. RTT Time Series Similarity

After processing the traceroutes, we start to calculate the similarity between the RTT time series of pairwise links. Based on a comparative study using quantitative and large-scale assessment strategies, the authors in [27] provided two findings: (1) dynamic time warping (DTW) [28] is found to be consistently superior to the other studied approaches. (2) The Euclidean distance [29] remains a quite accurate, robust, simple, and efficient way of measuring the similarity between two time series.However, the work [17] suggested that DTW is not suitable for calculating the similarity of massive RTT time series because of its high computational complexity. Hence, in this paper, we adopt the Euclidean distance to calculate the similarity between the two time series. It is worth noting that work [27] showed that Euclidean distance is inapplicable for analyzing the time series with misaligned time steps and different sequence lengths. This paper addresses it effectively since we have ensured that each RTT time series has the same sequence length and time interval in the data processing phase.Next, we describe the process of similarity calculation. For convenience, we denote theith link in detection area D as li. During the measurement period, we continuously extract t RTT of li every 10 minutes and form the corresponding RTT time series of li, which is denoted as X1:ti=x1i,x2i,…,xki,…,xti. X1:ti is an independent and identically-distributed (i. i. d.) sequence [30], where xki represents the kth RTT of X1:ti (k∈1,2,…,t). Similarly, the RTT time series of lj can be expressed as X1:tj=x1j,x2j,…,xki,…,xtj. Based on the Euclidean distance, the similarity between li and lj is calculated as follows:(1)SX1:ti,X1:tj=1∑k=1txki−xkj21/2.Note that the larger theSX1:ti,X1:tj, the more the similarities between X1:ti and X1:tj. Given the similarity threshold Δ1, if the similarity between X1:ti and X1:tj satisfies the condition,(2)SX1:ti,X1:tj≥Δ1.We conclude thatli and lj are similar.


### 3.1.3. Link Clustering Algorithm

Existing work showed that the RTT of links will be affected by their neighbor correlation when a network anomaly occurs [17]. Specifically, when a network anomaly occurs on a certain link, it will affect the RTT of its neighbors that share similar characteristics with it. It indicates that clustering the links with similar characteristics should not only consider the similarity between their RTT time series but also focus on the connected relation between links (i.e., topological locations). To achieve this, we propose a link clustering algorithm based on SRG. The pseudocode of the algorithm is shown in Algorithm 1.Algorithm 1: Link clustering.
Input: detection area D, dataset A;Output: the set of class C;(1)
Extract all the links inD from A,(2)
Randomly select a linkli in D as a seed,(3)
Extract the links connected withli in D, and denote the set of these links as Li,(4)
According to (1), calculate the similarity between the RTT time series of li and the RTT time series of each link from Li,(5)
if there is no link sharing similar characteristic with li (satisfies (2)), then(6)
Clusterli as a class,(7)
else(8)
Extract the links satisfying (2), and denote the set of these links as Bi (including li),(9)
end if(10)
Choose the links inBi that are not selected as seed before, and let each of them be a new seed, respectively,(11)
Extract the links inD that connect with each new seed, and for each link, we calculate the similarity between the RTT time series and the RTT time series of the new seed it connects with, respectively,(12)
if no link is similar to the new seed that connects with it, then(13)
Cluster all links ofBi into a class,(14)
else(15)
Put the links that are similar to the new seed intoBi,(16)
goto step 9,(17)
end if(18)
if all the links in D are clustered into their corresponding classes, then(19)
return the set of class C.(20)
else(21)
Filter the links inBi from D, and randomly select a link li from the remaining links,(22)
goto step 2,(23)
end ifAlgorithm 1 consists of four phases, and each phase is described as follows: in the first phase, for a certain detection areaD, we randomly select a link li as a seed and extract the links connected with it. The set of these links is denoted as Li. Then, we calculate the similarity between the RTT time series of li and the RTT time series of each link in Li. Next, based on the similarity results, we extract the links that satisfy (2) and denote the set of these links as Bi, where li belongs to set Bi.In the second phase, we choose the links inBi that are not selected as seed before and denote each of them as a new seed, respectively. Then, we extract the links in D that connect with each new seed, and for each link, we calculate the similarity of its RTT time series with the new seed it connects with. Next, based on the similarity results, we extract the links satisfying (2) and put them into Bi.In the third phase, we keep repeating the second phase until there is no link inD being similar with the new seeds. Then, we cluster all links of Bi into the same class. In the last phase, we filter the links in Bi from D and randomly select a link li from the remaining links. Then, we perform the previous three phases again in order. Finally, all links in D are clustered into C classes, and the kth class is denoted as Ck, which contains Mk links.


## 3.1.1. Data Preprocessing

Our analysis in this paper is based on the public datasets, i.e., RIPE Atlas dataset [26]. For a certain detection area D (e.g., a city), we obtain their corresponding traceroutes A. Dataset A contains each hop (address) from the probes (sources) to the destinations and the RTT at which the probe packet reaches to each hop. In this paper, we only focus on the links formed by each two adjacent nodes and the RTT of each link. One thing to note is that not all traceroutes can be used for our analysis: (1) some Atlas probes (anchors) cannot conduct measurement consecutively because of the failure. (2) Some traceroutes do not have complete information because a part of the router does not respond to probes.Hence, in the first step, we group the traceroutes of each probe into 30-minute time-bins and discard the probe that conducts less than 3 measurements in any bin according to [1]. This sanity check prevents us from making incorrect inferences using the probes that cannot conduct measurements consecutively. In the second step, we filter out the traceroutes with incomplete information. Finally, we determine the measurement period. Then, during the measurement period, we extract the RTT of each link at the same time interval (every 10 minutes) and form their RTT time series, respectively. This step ensures that each RTT time series has the same time interval and sequence length.


## 3.1.2. RTT Time Series Similarity

After processing the traceroutes, we start to calculate the similarity between the RTT time series of pairwise links. Based on a comparative study using quantitative and large-scale assessment strategies, the authors in [27] provided two findings: (1) dynamic time warping (DTW) [28] is found to be consistently superior to the other studied approaches. (2) The Euclidean distance [29] remains a quite accurate, robust, simple, and efficient way of measuring the similarity between two time series.However, the work [17] suggested that DTW is not suitable for calculating the similarity of massive RTT time series because of its high computational complexity. Hence, in this paper, we adopt the Euclidean distance to calculate the similarity between the two time series. It is worth noting that work [27] showed that Euclidean distance is inapplicable for analyzing the time series with misaligned time steps and different sequence lengths. This paper addresses it effectively since we have ensured that each RTT time series has the same sequence length and time interval in the data processing phase.Next, we describe the process of similarity calculation. For convenience, we denote theith link in detection area D as li. During the measurement period, we continuously extract t RTT of li every 10 minutes and form the corresponding RTT time series of li, which is denoted as X1:ti=x1i,x2i,…,xki,…,xti. X1:ti is an independent and identically-distributed (i. i. d.) sequence [30], where xki represents the kth RTT of X1:ti (k∈1,2,…,t). Similarly, the RTT time series of lj can be expressed as X1:tj=x1j,x2j,…,xki,…,xtj. Based on the Euclidean distance, the similarity between li and lj is calculated as follows:(1)SX1:ti,X1:tj=1∑k=1txki−xkj21/2.Note that the larger theSX1:ti,X1:tj, the more the similarities between X1:ti and X1:tj. Given the similarity threshold Δ1, if the similarity between X1:ti and X1:tj satisfies the condition,(2)SX1:ti,X1:tj≥Δ1.We conclude thatli and lj are similar.


## 3.1.3. Link Clustering Algorithm

Existing work showed that the RTT of links will be affected by their neighbor correlation when a network anomaly occurs [17]. Specifically, when a network anomaly occurs on a certain link, it will affect the RTT of its neighbors that share similar characteristics with it. It indicates that clustering the links with similar characteristics should not only consider the similarity between their RTT time series but also focus on the connected relation between links (i.e., topological locations). To achieve this, we propose a link clustering algorithm based on SRG. The pseudocode of the algorithm is shown in Algorithm 1.Algorithm 1: Link clustering.
Input: detection area D, dataset A;Output: the set of class C;(1)
Extract all the links inD from A,(2)
Randomly select a linkli in D as a seed,(3)
Extract the links connected withli in D, and denote the set of these links as Li,(4)
According to (1), calculate the similarity between the RTT time series of li and the RTT time series of each link from Li,(5)
if there is no link sharing similar characteristic with li (satisfies (2)), then(6)
Clusterli as a class,(7)
else(8)
Extract the links satisfying (2), and denote the set of these links as Bi (including li),(9)
end if(10)
Choose the links inBi that are not selected as seed before, and let each of them be a new seed, respectively,(11)
Extract the links inD that connect with each new seed, and for each link, we calculate the similarity between the RTT time series and the RTT time series of the new seed it connects with, respectively,(12)
if no link is similar to the new seed that connects with it, then(13)
Cluster all links ofBi into a class,(14)
else(15)
Put the links that are similar to the new seed intoBi,(16)
goto step 9,(17)
end if(18)
if all the links in D are clustered into their corresponding classes, then(19)
return the set of class C.(20)
else(21)
Filter the links inBi from D, and randomly select a link li from the remaining links,(22)
goto step 2,(23)
end ifAlgorithm 1 consists of four phases, and each phase is described as follows: in the first phase, for a certain detection areaD, we randomly select a link li as a seed and extract the links connected with it. The set of these links is denoted as Li. Then, we calculate the similarity between the RTT time series of li and the RTT time series of each link in Li. Next, based on the similarity results, we extract the links that satisfy (2) and denote the set of these links as Bi, where li belongs to set Bi.In the second phase, we choose the links inBi that are not selected as seed before and denote each of them as a new seed, respectively. Then, we extract the links in D that connect with each new seed, and for each link, we calculate the similarity of its RTT time series with the new seed it connects with. Next, based on the similarity results, we extract the links satisfying (2) and put them into Bi.In the third phase, we keep repeating the second phase until there is no link inD being similar with the new seeds. Then, we cluster all links of Bi into the same class. In the last phase, we filter the links in Bi from D and randomly select a link li from the remaining links. Then, we perform the previous three phases again in order. Finally, all links in D are clustered into C classes, and the kth class is denoted as Ck, which contains Mk links.


## 3.2. Model Selection

In practice, network managers have high requirements for the timeliness and accuracy of anomaly detection, and selecting an appropriate statistical model to analyze the measurements can improve the timeliness and accuracy of anomaly detection [11]. Hence, by considering the goodness of fit and complexity of the statistical models, this paper selects an appropriate statistical model to analyze the RTT time series of the links, aiming to reduce the detection time and improve the accuracy of detection.In this section, we, firstly, summarize the statistical models used in the existing approaches for anomaly detection. Then, for each class of links, we use the Bayesian information criterion (BIC) [31] to select the appropriate statistical model for them and leverage the model to analyze their RTT time series.


### 3.2.1. Statistical Models for RTT

Leveraging the statistical model to analyze the RTT of links is an effective way to characterize the network condition. Hence, existing work has used different statistical models to analyze the RTT time series of links for anomaly detection. Next, we describe the statistical models that are widely used in turn.(1) Normal Model. The normal model is a common approach when coping with data analysis [32]. Previous works have demonstrated that the RTT distribution of the link roughly follows the normal distribution [14]. Hence, they leveraged the probability density function of the normal distribution to approximate the distribution of RTT measurements. The probability density function is computed as follows:(3)fx|u,δ=12πδ2e−x−u2/2δ2,where u is the mean value, and δ is the variance.(2) Log-Normal Model. A large number of cases demonstrate that the normal model achieves satisfying performance in describing the distribution of RTT measurements. However, recent studies [14] reported that the RTT distribution of some links is characterized by several distinct modes, and the normal model fails to distinguish these modes. To address this challenge, they leveraged the log-normal model to describe the distribution of RTT for these links [14]. The probability density function of log-normal distribution is computed as follows:(4)fx|u,δ=1xδ2πe−lnx−u2/2δ2,where u is the mean value, and δ is the variance.(3) GEV Model. Normal and log-normal models typically focus on the median of RTT measurements and ignore their extreme values. However, an extreme value is often closely related to the occurrence of anomalous events [21, 22]. Thus, analyzing the extreme value of RTT measurements is beneficial to provide theoretical support for the statistical analysis of anomalous events. The model widely used to analyze the extreme value of RTT data is the generalized extreme value (GEV) distribution [23]. Its probability density function is computed as follows:(5)fx|u,δ,ξ=1δ1+ξx−uδ−1/ξ+1e1+ξx−u/δ−1/ξ,where 1+ξx−u/δ>0, u is the location parameter, δ is the scale parameter (δ>0), and ξ is the shape parameter.(4) Burr Type XII Model. Similar to the GEV model, the Burr Type XII model can also be used to analyze the extreme value of RTT measurements [24]. Different from the GEV model, the Burr Type XII model is a flexible distribution model that can characterize multiple distribution patterns. Based on its flexibility, using the Burr type XII model to analyze RTT time series can reduce the noise and improve the accuracy of modeling. However, the modeling time of the Burr Type XII model is relatively long, which will affect the timeliness of anomaly detection. The probability density function of the Burr Type XII model is computed as follows:(6)fx|a,c,k=kc/ax/ac−11+x/ack+1,where c and k are the shape parameters, and a is the scale parameter. All the parameters should be greater than zero.


### 3.2.2. Select the Appropriate Model

The above four statistical models can effectively characterize the distribution of RTT measurements but how to select an appropriate model to analyze the RTT time series of each class of links remains a challenge. Specifically, the RTT distribution of each class of link is not completely consistent. To reduce the detection time and improve the accuracy of detection, the statistical model should not only fit the RTT distribution of links but also have a low modeling time.Considering thatBayesian Information Criterion (BIC) is a well-known metric to evaluate the goodness of fit and complexity of the model [31], we leverage BIC to select the model with a high fitting degree and low complexity for each class of links. In detail, the fitting degree represents the accuracy of the model in characterizing the RTT measurements, and the complexity considers the influence of the number of links and model parameters on the modeling time.Without loss of generality, we take the classCk as an example to illustrate the process of model selection. We, firstly, leverage the four statistical models mentioned above to characterize the RTT distribution of the links in Ck and calculate the BIC value of each statistical model. Then, we select the statistical model with the smallest BIC value as the final model for Ck. The BIC value of the statistical model is computed as follows:(7)BIC=∑i=1IlogIK−2logLX1:tiI,where I is the number of links in Ck, K is the number of parameters of the model, and LX1:ti represents the maximum value of the likelihood function for the time series X1:ti. For the class Ck, the smaller BIC value of the model represents that the model has less complexity and can characterize the RTT distribution of the links in Ck more accurately.


## 3.2.1. Statistical Models for RTT

Leveraging the statistical model to analyze the RTT of links is an effective way to characterize the network condition. Hence, existing work has used different statistical models to analyze the RTT time series of links for anomaly detection. Next, we describe the statistical models that are widely used in turn.(1) Normal Model. The normal model is a common approach when coping with data analysis [32]. Previous works have demonstrated that the RTT distribution of the link roughly follows the normal distribution [14]. Hence, they leveraged the probability density function of the normal distribution to approximate the distribution of RTT measurements. The probability density function is computed as follows:(3)fx|u,δ=12πδ2e−x−u2/2δ2,where u is the mean value, and δ is the variance.(2) Log-Normal Model. A large number of cases demonstrate that the normal model achieves satisfying performance in describing the distribution of RTT measurements. However, recent studies [14] reported that the RTT distribution of some links is characterized by several distinct modes, and the normal model fails to distinguish these modes. To address this challenge, they leveraged the log-normal model to describe the distribution of RTT for these links [14]. The probability density function of log-normal distribution is computed as follows:(4)fx|u,δ=1xδ2πe−lnx−u2/2δ2,where u is the mean value, and δ is the variance.(3) GEV Model. Normal and log-normal models typically focus on the median of RTT measurements and ignore their extreme values. However, an extreme value is often closely related to the occurrence of anomalous events [21, 22]. Thus, analyzing the extreme value of RTT measurements is beneficial to provide theoretical support for the statistical analysis of anomalous events. The model widely used to analyze the extreme value of RTT data is the generalized extreme value (GEV) distribution [23]. Its probability density function is computed as follows:(5)fx|u,δ,ξ=1δ1+ξx−uδ−1/ξ+1e1+ξx−u/δ−1/ξ,where 1+ξx−u/δ>0, u is the location parameter, δ is the scale parameter (δ>0), and ξ is the shape parameter.(4) Burr Type XII Model. Similar to the GEV model, the Burr Type XII model can also be used to analyze the extreme value of RTT measurements [24]. Different from the GEV model, the Burr Type XII model is a flexible distribution model that can characterize multiple distribution patterns. Based on its flexibility, using the Burr type XII model to analyze RTT time series can reduce the noise and improve the accuracy of modeling. However, the modeling time of the Burr Type XII model is relatively long, which will affect the timeliness of anomaly detection. The probability density function of the Burr Type XII model is computed as follows:(6)fx|a,c,k=kc/ax/ac−11+x/ack+1,where c and k are the shape parameters, and a is the scale parameter. All the parameters should be greater than zero.


## 3.2.2. Select the Appropriate Model

The above four statistical models can effectively characterize the distribution of RTT measurements but how to select an appropriate model to analyze the RTT time series of each class of links remains a challenge. Specifically, the RTT distribution of each class of link is not completely consistent. To reduce the detection time and improve the accuracy of detection, the statistical model should not only fit the RTT distribution of links but also have a low modeling time.Considering thatBayesian Information Criterion (BIC) is a well-known metric to evaluate the goodness of fit and complexity of the model [31], we leverage BIC to select the model with a high fitting degree and low complexity for each class of links. In detail, the fitting degree represents the accuracy of the model in characterizing the RTT measurements, and the complexity considers the influence of the number of links and model parameters on the modeling time.Without loss of generality, we take the classCk as an example to illustrate the process of model selection. We, firstly, leverage the four statistical models mentioned above to characterize the RTT distribution of the links in Ck and calculate the BIC value of each statistical model. Then, we select the statistical model with the smallest BIC value as the final model for Ck. The BIC value of the statistical model is computed as follows:(7)BIC=∑i=1IlogIK−2logLX1:tiI,where I is the number of links in Ck, K is the number of parameters of the model, and LX1:ti represents the maximum value of the likelihood function for the time series X1:ti. For the class Ck, the smaller BIC value of the model represents that the model has less complexity and can characterize the RTT distribution of the links in Ck more accurately.


## 3.3. Anomaly Detection

After determining the corresponding statistical model of each class of links, we propose a detection method based onlarge deviation theory [33] and Sanov’s theorem [30] to detect network anomalies. Next, this section describes the detection rationale and workflow of the detection method.


### 3.3.1. Detection Rationale

Based on the large-scale measurement and long-term analysis, Jiang and Dovrolis [34] found that under the normal network state, the RTT of the link is basically in a stable state. In detail, [34] analyzed the RTT distribution of the links in the detection area based on different time scales (seconds, minutes, hours, days, months, and years). They found that under any time scale, the cumulative probability distribution of the RTT remained basically stable over time. These results proved that the distribution probability of the RTT of links is in a relatively stable range.Inspired by the results of [34], we, firstly, obtained the distribution probability of the RTT of each link under the normal network state. Next, we continuously monitored the RTT of links, and we believed that for each link, the frequency of occurrence for each value of RTT under the normal network state should be similar to its distribution probability we obtained before. Only during the network anomaly, the RTT of links will fluctuate obviously, resulting in a large deviation between the occurrence frequency of each value of RTT and its distribution probability we obtained under the normal network state.Based on the above analysis, an effective way to detect the network anomaly is by characterizing and analyzing the deviation between the occurrence frequency of each value of RTT and its distribution probability. Therefore, this section uses the large deviation theory to analyze this deviation and detects the network anomaly by observing whether the value of deviation exceeds the critical value.


### 3.3.2. Workflow

Without the loss of generality, we take the linkli as an example to illustrate the workflow of detection method. We suppose that the link li belongs to class Ck. Firstly, we measure the RTT of li within t consecutive time intervals under the normal network state and obtain the RTT time series of li, which is denoted as X1:ti=x1i,x2i,…,xki,…,xti. Then, we extract each value of RTT in X1:ti and sort them in an ascending order manner, which forms the sequence Ri. Ri=r1i,r2i,…,rki,…,rni, where n represents the number of different RTT value in X1:ti, rki is the kth element of Ri, r1i is the minimum value of RTT in X1:ti, and rni is the maximum value of RTT in X1:ti.Next, we leverage four statistical models (mentioned in Section3.2) to analyze the links in Ck. According to the BIC value, we select the final statistical model for class Ck. Then, we use the final statistical model to analyze the links in Ck and obtain the probability density of each value in Ri. The sequence of probability density is denoted as Ui=u1i,u2i,…,uki,…,uni, where uki is the kth element of Ui, and it represents the probability density of rki. To compare the probability density with that under network anomaly, we denote Ui as the sequence that contains the reference value of RTT probability density of li.After determining the reference value of RTT probability density ofli, we still measure the RTT of li within t consecutive time intervals and obtain its RTT time series. The RTT time series is denoted as Y1:ti=y1i,y2i,…,ypi,…,yti, where Ypi is the pth element of Y1:ti. Then, for each value of Ri, (1) we calculate the number of occurrences that it appears in sequence Y1:ti, (2) divide the number of occurrences by t, and obtain its frequency of occurrence on Y1:ti. After obtaining the frequency of occurrence of each value in turn, we use these values to form the frequency sequence εi=ε1i,ε2i,…,εki,…,εni, where the kth element εki is computed as follows:(8)εki=1t∑p=1t1xkiYpi,k=1,2,…,n,where 1xkiYpi is the generating function of the event Ypi=xki. The function is defined as follows:(9)1xkiYpi=1,ypi=xki,0,ypi≠xki.Generally, the frequency of occurrence of each value inRi should be approximately equal to its corresponding probability density in sequence Ui, i.e., εi is approximately equal to Ui. However, the occurrence of network anomaly will lead to an obvious inconsistency between εi and Ui. The phenomenon of this obvious inconsistency is rare, and understanding the probability of this rare phenomenon is an effective method to detect network anomaly [35]. According to Sanov’s theorem [30], the probability is computed as follows:(10)Pi≈10−nHεi/Ui,where Hεi/Ui represents the relative entropy between εi and Ui. The relative entropy is computed as follows:(11)HεiUi=∑k=1nεkilog0.1εkiuki,where Hεi/Ui is used to describe the similarities between εi and Ui, i.e., the distance between them. The larger value of Hεi/Ui indicates that there is a lager deviation between the actual network state and normal state, and the probability of this phenomenon Pi is low. Actually, the RTT of links is stable over a longer period of time [36, 37]. Hence, for each link, the relative entropy between the measured value and reference value is small, and the probability Pi is always large. Only when a network anomaly occurs, the relative entropy increases, and the large deviation probability Pi will be much lower than the reference value in the normal state.Hence, for the linkli, we calculate the relative entropy between its measured value and its reference value. Then, we obtain its large deviation probability Pi. Given the threshold of large deviation probability Δ2, if Pi satisfies the condition, then,(12)Pi≤Δ2.We conclude that the network anomaly occurs in the linkli. Meanwhile, based on the analysis of correlation, we can roughly infer that the links in class Ck may be affected by this network anomaly.


## 3.3.1. Detection Rationale

Based on the large-scale measurement and long-term analysis, Jiang and Dovrolis [34] found that under the normal network state, the RTT of the link is basically in a stable state. In detail, [34] analyzed the RTT distribution of the links in the detection area based on different time scales (seconds, minutes, hours, days, months, and years). They found that under any time scale, the cumulative probability distribution of the RTT remained basically stable over time. These results proved that the distribution probability of the RTT of links is in a relatively stable range.Inspired by the results of [34], we, firstly, obtained the distribution probability of the RTT of each link under the normal network state. Next, we continuously monitored the RTT of links, and we believed that for each link, the frequency of occurrence for each value of RTT under the normal network state should be similar to its distribution probability we obtained before. Only during the network anomaly, the RTT of links will fluctuate obviously, resulting in a large deviation between the occurrence frequency of each value of RTT and its distribution probability we obtained under the normal network state.Based on the above analysis, an effective way to detect the network anomaly is by characterizing and analyzing the deviation between the occurrence frequency of each value of RTT and its distribution probability. Therefore, this section uses the large deviation theory to analyze this deviation and detects the network anomaly by observing whether the value of deviation exceeds the critical value.


## 3.3.2. Workflow

Without the loss of generality, we take the linkli as an example to illustrate the workflow of detection method. We suppose that the link li belongs to class Ck. Firstly, we measure the RTT of li within t consecutive time intervals under the normal network state and obtain the RTT time series of li, which is denoted as X1:ti=x1i,x2i,…,xki,…,xti. Then, we extract each value of RTT in X1:ti and sort them in an ascending order manner, which forms the sequence Ri. Ri=r1i,r2i,…,rki,…,rni, where n represents the number of different RTT value in X1:ti, rki is the kth element of Ri, r1i is the minimum value of RTT in X1:ti, and rni is the maximum value of RTT in X1:ti.Next, we leverage four statistical models (mentioned in Section3.2) to analyze the links in Ck. According to the BIC value, we select the final statistical model for class Ck. Then, we use the final statistical model to analyze the links in Ck and obtain the probability density of each value in Ri. The sequence of probability density is denoted as Ui=u1i,u2i,…,uki,…,uni, where uki is the kth element of Ui, and it represents the probability density of rki. To compare the probability density with that under network anomaly, we denote Ui as the sequence that contains the reference value of RTT probability density of li.After determining the reference value of RTT probability density ofli, we still measure the RTT of li within t consecutive time intervals and obtain its RTT time series. The RTT time series is denoted as Y1:ti=y1i,y2i,…,ypi,…,yti, where Ypi is the pth element of Y1:ti. Then, for each value of Ri, (1) we calculate the number of occurrences that it appears in sequence Y1:ti, (2) divide the number of occurrences by t, and obtain its frequency of occurrence on Y1:ti. After obtaining the frequency of occurrence of each value in turn, we use these values to form the frequency sequence εi=ε1i,ε2i,…,εki,…,εni, where the kth element εki is computed as follows:(8)εki=1t∑p=1t1xkiYpi,k=1,2,…,n,where 1xkiYpi is the generating function of the event Ypi=xki. The function is defined as follows:(9)1xkiYpi=1,ypi=xki,0,ypi≠xki.Generally, the frequency of occurrence of each value inRi should be approximately equal to its corresponding probability density in sequence Ui, i.e., εi is approximately equal to Ui. However, the occurrence of network anomaly will lead to an obvious inconsistency between εi and Ui. The phenomenon of this obvious inconsistency is rare, and understanding the probability of this rare phenomenon is an effective method to detect network anomaly [35]. According to Sanov’s theorem [30], the probability is computed as follows:(10)Pi≈10−nHεi/Ui,where Hεi/Ui represents the relative entropy between εi and Ui. The relative entropy is computed as follows:(11)HεiUi=∑k=1nεkilog0.1εkiuki,where Hεi/Ui is used to describe the similarities between εi and Ui, i.e., the distance between them. The larger value of Hεi/Ui indicates that there is a lager deviation between the actual network state and normal state, and the probability of this phenomenon Pi is low. Actually, the RTT of links is stable over a longer period of time [36, 37]. Hence, for each link, the relative entropy between the measured value and reference value is small, and the probability Pi is always large. Only when a network anomaly occurs, the relative entropy increases, and the large deviation probability Pi will be much lower than the reference value in the normal state.Hence, for the linkli, we calculate the relative entropy between its measured value and its reference value. Then, we obtain its large deviation probability Pi. Given the threshold of large deviation probability Δ2, if Pi satisfies the condition, then,(12)Pi≤Δ2.We conclude that the network anomaly occurs in the linkli. Meanwhile, based on the analysis of correlation, we can roughly infer that the links in class Ck may be affected by this network anomaly.


## 3.4. Anomaly Detection Algorithm

Based on the analysis of Section III-A to Section III-C, we propose an anomaly detection algorithm based on the RTT time series in this section, which includes three phases: link clustering, model selection, and anomaly detection. The pseudocode of the algorithm is shown in Algorithm 2.Algorithm 2: Anomaly detection algorithm.
Input: detection area D, dataset A, times of the measurement t ;Output: network anomaly and its impact;Link clustering(1)
Extract all the links inD from A,(2)
Extract the RTT of links fromA during t consecutive time intervals, and form their RTT time series, respectively,(3)
Calculate the similarity between the RTT time series of pairwise links, and cluster the links intoC classes using Algorithm 1. The kth class is denoted as Ck, which contains Mk links,Model selection(4)
fork∈1,Cdo,(5)
Leverage four statistical models to analyze the RTT time series of the links inCk, and obtain the BIC value of each statistical model,(6)
Select the statistical model with the lowest BIC value as the final model ofCk,Anomaly detection(7)
fori∈1,Mkdo,(8)
Under the normal state, leverage the final model to analyze the RTT time series of linkli, and obtain the sequence Ui,(9)
Monitor the RTT of linkli during t consecutive time intervals, and obtain the sequence εi,(10)
Calculate the relative entropy betweenεi and Ui, and obtain the large deviation probability Pi,(11)
ifPi≤Δ2, then(12)
return network anomaly, and the network anomaly may affect all the links in class Ck.(13)
end if(14)
end for(15)
end for,In the phase of link clustering, we obtain the RTT time series of the links inD, and calculate the similarity between the RTT time series of pairwise links according to (1). Based on the topological location of pairwise links and the condition of similarity ((2)), we cluster the links in D into different classes.In the next phase, i.e., model selection, we, firstly, leverage four statistical models to analyze the RTT time series of the links in each class. Then, for each class, we calculate the BIC value of each statistical model and select the statistical model with the lowest BIC value as the final model of the class.In the phase of anomaly detection, we, firstly, determine the final model of each link based on the second phase. Secondly, for a certain link, we leverage its final model to analyze its RTT time series under the normal state and obtain its reference value of RTT probability density. Thirdly, we monitor the RTT of this link constantly and obtain the frequency of occurrence of each RTT value. Next, we calculate the relative entropy between the measured value and reference value and obtain the large deviation probability. Finally, if the large deviation probability is below the critical value we set, we conclude that the network anomaly occurs in this link, and the network anomaly may affect the links having the same class as this link.


## 4. Experimental Results

In this section, we execute experiments on real internet paths to demonstrate the validity of RTS detection in detecting the network anomaly. We begin by presenting the results of link clustering. Based on these results, we select the appropriate statistical model for each class of links. Next, we leverage an abnormal historical event to determine the threshold of large deviation probability. Finally, we leverage another abnormal historical event to evaluate the rationality of model selection and the validity of RTS detection. Although our approach is applicable for network anomaly detection in any detection area, because of space limitations, this paper takes the United States as the detection area to show the experimental results of the approach.


### 4.1. Dataset

To ensure that the measured data can truly reflect the RTT distribution of the links, this paper collects the traceroutes whose hops are located in the United States from the RIPE Atlas dataset [26] from January 1st 2019, to December 31st 2021. For convenience, we denote the traceroutes as dataset A1. Then, we obtain all the links from A1, and extract their RTT every 15 minutes continuously. Next, we discard the links with incomplete information and finally obtain the RTT time series of 28,984 IPv4 links in the United States. Based on the RTT time series of each link, we give the cumulative probability distribution of RTT in three years, which is shown in Figure 2.Figure 2
The cumulative probability distribution of the RTT of links.It can be seen from Figure2 because of the influence of COVID-19, the distribution in 2019 was slightly different from other years. However, the cumulative probability distribution of RTT is basically the same as the year goes on. Based on this phenomenon, we conclude that analyzing the RTT of 28,984 links for one whole year can effectively contain and characterize all the RTT values of these links. Therefore, this paper only uses the RTT data in 2021 for experiments.


### 4.2. Results of Link Clustering

After obtaining the RTT time series of 28,984 links, we calculate the similarity between the RTT time series of pairwise links according to (1). The cumulative probability distribution of similarity is given in Figure 3, where the x-axis is the similarity, and the y-axis is the cumulative probability.Figure 3
The cumulative probability distribution of the similarity between the RTT time series of pairwise links.From Figure3, we observe that the cumulative probability increases rapidly when the similarity is below 0.017. Then, when the similarity is between 0.017 and 0.04, the cumulative probability increases slowly. Finally, the cumulative probability stabilizes when the similarity is above 0.04. As mentioned before, the RTT of the link affected the network state of its neighbors that share similar characteristics with it [17]. Moreover, the more similar the links, the stronger the interaction. Clustering the links sharing less similar characteristics will affect the results of model selection and detection. Therefore, to ensure the validity of RTS detection, we set Δ1 as 0.017.After determining the threshold of similarity, we use Algorithm 1 to cluster 28,984 IPv4 links, and the results of clustering are shown in Table1.Table 1
Results of clustering.
ParameterNumberNumber of links28,984Number of classes1066Minimum number of links in a class1Maximum number of links in a class7888Number of class containing only one link4336Number of class containing 7888 links1As can be seen from Table1, 28,984 IPv4 links are clustered into 1066 classes, and only one class contains the largest number of links, i.e., 7888. Meanwhile, there are 436 links for which we cannot find any similar links in the United States.


### 4.3. Model Selection

Based on the results of clustering, this paper takes the class containing 7888 links as an example to describe the process of model selection. For convenience, we denote this class asC1. Firstly, we leverage the normal model, log-normal model, GEV model, and Burr Type XII model to analyze the RTT time series of the 7888 links, respectively. Then, we calculate the BIC value of each statistical model, and the results are shown in Table 2.Table 2
BIC value of the four statistical models.
Statistical modelBIC valueNormal model−1879.146Log-normal model−2229.938GEV model−3284.676Burr type XII model−2768.298As can be seen from Table2, the GEV model achieves the smallest BIC value. As mentioned before, the smaller BIC value indicates that the model has less complexity and can characterize the RTT distribution of the links more accurately. Hence, we select the GEV model as the final model of the class C1.In addition, based on the same experimental platform, this paper compares the modeling time of these four statistical models, and the results are shown in Table3. As can be seen from Table 3, the GEV model requires the least modeling time. The shorter modeling time can reduce the detection time effectively, which can help network managers to mitigate the serious damage caused by network anomalies timely. The experimental results demonstrate that our approach can select the statistical model with low complexity to reduce the modeling time.Table 3
Modeling time of the four statistical models.
Statistical modelModeling time (s)Normal model135Log-normal model121GEV model88Burr type XII model187


### 4.4. Threshold of the Large Deviation Probability

After determining the final model of each class, we need to determine the threshold of the large deviation probability to detect the network anomaly. Because of space limitations, this paper takes California as the detection area to illustrate the process of threshold determination. Specifically, we leverage an abnormal historical event that occurred in California to help us determine the threshold of the large deviation probability. This abnormal event lasted from 21:45 to 24:00 on May24th 2019, and it affected 238 links [38].Firstly, we extract the RTT time series of these 238 links from the datasetA1 and select the appropriate statistical model for each link. It is worth noting that the final models of these 238 links contain the four statistical models we discussed before. Secondly, we use the corresponding final model to analyze the RTT time series of the 238 links, respectively. Finally, we can obtain the sequences of RTT probability density of these 238 links, and these sequences are considered to be the reference values of the RTT probability density of the 238 links.Next, we collect the traceroutes flowing through California on May24th 2019 from the RIPE Atlas dataset and extract the RTT of these 238 links every 15 minutes continuously to form their RTT time series. Then, according to the duration of the abnormal event, we denote the time period from 21:45 to 24:00 on May 24th as the time period of network anomaly and denote the rest of the time period on May 24th as the time period of the normal network state.After that, we divide the RTT time series of each link into two parts. One is the RTT time series under the normal network stat and the other is the RTT time series under network anomaly. According to equations (8) to (11), we calculate the large deviation probability of each link during the period of network anomaly and normal network state, respectively. Then, we give the cumulative probability distribution of the large deviation probability under the normal network state and the network anomaly. The results are shown in Figure 4, where the x-axis is the large deviation probability, and the y-axis is the cumulative probability.Figure 4
The cumulative probability distribution of the large deviation probability under the normal network state and the network anomaly.As can be seen from Figure4, the large deviation probability values of 96.1% links are greater than 10−24 under the normal network state. On the contrary, the large deviation probability values of all the links are lower than 10−24 under the network anomaly. Suppose that the threshold of large deviation probability is 10−24, our approach can detect the network anomaly accurately and only has the false detection rate of 3.9%. To ensure that our approach can detect all the network anomalies in California effectively, we set Δ2 as 10−24. According to this method, researchers can determine the threshold of large deviation probability for any detection area.It is worth noting that the threshold of large deviation probability (i.e.,10−nHεi/Ui=10−24) is too small, leading to the fact that it is inconvenient for network managers to detect the network anomaly in practice. To address this challenge, this paper takes nHεi/Ui (see equation (10)) as the criterion for anomaly detection, which is called the relative entropy of RTT. Specifically, when the relative entropy of RTT of the link is greater than 24, we conclude that the network anomaly occurs in this link. Moreover, while detecting the network anomaly in California, the critical value of the relative entropy of RTT we set is applicable for any statistical model because the final models of the 238 links contains all statistical models.


### 4.5. Case Study

#### 4.5.1. The Validity of RTS detection

Based on the threshold of the relative entropy of RTT, we also select California as the detection area and leverage another historical abnormal event occurred in California to evaluate the rationality of model selection and the validity of RTS detection. This abnormal event lasted from 11:53 to 17:20 on October21st 2016 [39].We, firstly, extract the links located in California from the 28,984 IPv4 links, and these links are clustered into the classC1. Based on the previous analysis (see Section 4.3), we select the GEV model to analyze the RTT time series of the 7888 links. Then, we obtain the sequences of RTT probability density of these 7888 links, and these sequences are considered to be the reference value of RTT probability density of the 7888 links.Next, we collect the traceroutes flowing through California on October21st 2016 from the RIPE Atlas dataset and extract the RTT of the 7888 links every 15 minutes continuously to form their RTT time series. Then, we monitor the RTT of each link continuously and calculate their relative entropy of RTT. Finally, we detect the network anomaly by observing whether the relative entropy of RTT of any link exceeds 24.Because of space limitations, this paper selects one link randomly (i.e., 184.105.213.xx-184.105.65.xx) from the 7888 links and takes its RTT time series as an example to illustrate the process of anomaly detection. To protect the privacy of link information, we hide the last four-bit of the addresses. The relative entropy of RTT of link 184.105.213.xx-184.105.65.xx is shown in Figure5, where the x-axis is the time (in hours), the y-axis is the relative entropy of RTT, and the dotted line is the critical value of the relative entropy of RTT.Figure 5
The Relative entropy of RTT of the link 184.105.213.xx-184.105.65.xx.As can be seen from Figure5, the relative entropy of RTT is below the critical value before 11:53. Then, it increases rapidly and exceeds the critical value from 11:53 to 12:20. Then, the relative entropy of RTT is gradually below the critical value from 12:20 to 17:05. Next, the relative entropy of RTT increases again and exceeds the critical value from 17:05 to 17:20. It can be inferred from Figure 5 that the network anomaly occurred from 11:53 to 12:20 and from 17:05 to 17:20, respectively, which is basically in good agreement with the time reported in [40]. Therefore, the experimental results demonstrate that RTS detection can detect the network anomaly effectively.


#### 4.5.2. The Correlation between Links

To verify the correlation between links, we also observe the relative entropy of RTT of the remaining 7887 links. The experimental results show that monitoring the relative entropy of RTT of 7104 links can detect network anomaly effectively. For the remaining 783 links, we speculate that because these links are located far away from the place where the network anomaly occurred, they are not significantly affected by the network anomaly. Although RTS detection cannot accurately evaluate the impact of network anomaly, it can detect the network anomaly by monitoring any one of the 7105 links. Therefore, the approach we proposed can greatly reduce the cost and detection time and understand the impact of network anomaly roughly.


#### 4.5.3. The Validity of Model Selection

To verify the validity of model selection, this paper uses the remaining three statistical models to analyze the relative entropy of the RTT of the link 184.105.213.xx-184.105.65.xx again and gives the trend of the relative entropy of RTT in turn. The results are shown in Figures6 to 8.Figure 6
Anomaly detection based on the normal model, and the relative entropy of RTT of the link 184.105.213.xx-184.105.65.xx.Figure 7
Anomaly detection based on the log-normal model, and the relative entropy of RTT of the link 184.105.213.xx-184.105.65.xx.Figure 8
Anomaly detection based on the Burr Type XII model, and the relative entropy of RTT of the link 184.105.213.xx-184.105.65.xx.Based on the experimental results from Figure5 to Figure 8, we give the accuracy and false positive rate of the four statistical models, respectively, which are shown in Table 4. Accuracy represents the probability that the detection method can detect the network anomalies accurately, and the false positive rate represents the probability that the detection method identifies the normal network state as the network anomaly by mistake.Table 4
The accuracy and false positive rate of the four statistical models.
Statistical modelAccuracy (%)False positive rate (%)Normal model92.346.7Log-normal model95.133.2GEV model99.80.5Burr type XII model99.40.9Based on the results of Table4, we can draw three conclusions: (1) because of the lower goodness of fit of the normal model and the log-normal model, the detection method based on the normal model or the log-normal model achieves lower accuracy and higher false positive rate. Therefore, the detection methods based on these two models is unacceptable. (2) The detection method based on the Burr type XII model achieves better results of detection, however, it has a longer modeling time than the GEV model (see Table 3). In practice, the detection method based on the Burr type XII model may consume a long time for anomaly detection. (3) The experimental results show that the Bayesian information criterion can be used to select the appropriate model (i.e., the GEV model) for analyzing the RTT time series of links, which can help the network managers detect the network anomaly effectively.


## 4.1. Dataset

To ensure that the measured data can truly reflect the RTT distribution of the links, this paper collects the traceroutes whose hops are located in the United States from the RIPE Atlas dataset [26] from January 1st 2019, to December 31st 2021. For convenience, we denote the traceroutes as dataset A1. Then, we obtain all the links from A1, and extract their RTT every 15 minutes continuously. Next, we discard the links with incomplete information and finally obtain the RTT time series of 28,984 IPv4 links in the United States. Based on the RTT time series of each link, we give the cumulative probability distribution of RTT in three years, which is shown in Figure 2.Figure 2
The cumulative probability distribution of the RTT of links.It can be seen from Figure2 because of the influence of COVID-19, the distribution in 2019 was slightly different from other years. However, the cumulative probability distribution of RTT is basically the same as the year goes on. Based on this phenomenon, we conclude that analyzing the RTT of 28,984 links for one whole year can effectively contain and characterize all the RTT values of these links. Therefore, this paper only uses the RTT data in 2021 for experiments.


## 4.2. Results of Link Clustering

After obtaining the RTT time series of 28,984 links, we calculate the similarity between the RTT time series of pairwise links according to (1). The cumulative probability distribution of similarity is given in Figure 3, where the x-axis is the similarity, and the y-axis is the cumulative probability.Figure 3
The cumulative probability distribution of the similarity between the RTT time series of pairwise links.From Figure3, we observe that the cumulative probability increases rapidly when the similarity is below 0.017. Then, when the similarity is between 0.017 and 0.04, the cumulative probability increases slowly. Finally, the cumulative probability stabilizes when the similarity is above 0.04. As mentioned before, the RTT of the link affected the network state of its neighbors that share similar characteristics with it [17]. Moreover, the more similar the links, the stronger the interaction. Clustering the links sharing less similar characteristics will affect the results of model selection and detection. Therefore, to ensure the validity of RTS detection, we set Δ1 as 0.017.After determining the threshold of similarity, we use Algorithm 1 to cluster 28,984 IPv4 links, and the results of clustering are shown in Table1.Table 1
Results of clustering.
ParameterNumberNumber of links28,984Number of classes1066Minimum number of links in a class1Maximum number of links in a class7888Number of class containing only one link4336Number of class containing 7888 links1As can be seen from Table1, 28,984 IPv4 links are clustered into 1066 classes, and only one class contains the largest number of links, i.e., 7888. Meanwhile, there are 436 links for which we cannot find any similar links in the United States.


## 4.3. Model Selection

Based on the results of clustering, this paper takes the class containing 7888 links as an example to describe the process of model selection. For convenience, we denote this class asC1. Firstly, we leverage the normal model, log-normal model, GEV model, and Burr Type XII model to analyze the RTT time series of the 7888 links, respectively. Then, we calculate the BIC value of each statistical model, and the results are shown in Table 2.Table 2
BIC value of the four statistical models.
Statistical modelBIC valueNormal model−1879.146Log-normal model−2229.938GEV model−3284.676Burr type XII model−2768.298As can be seen from Table2, the GEV model achieves the smallest BIC value. As mentioned before, the smaller BIC value indicates that the model has less complexity and can characterize the RTT distribution of the links more accurately. Hence, we select the GEV model as the final model of the class C1.In addition, based on the same experimental platform, this paper compares the modeling time of these four statistical models, and the results are shown in Table3. As can be seen from Table 3, the GEV model requires the least modeling time. The shorter modeling time can reduce the detection time effectively, which can help network managers to mitigate the serious damage caused by network anomalies timely. The experimental results demonstrate that our approach can select the statistical model with low complexity to reduce the modeling time.Table 3
Modeling time of the four statistical models.
Statistical modelModeling time (s)Normal model135Log-normal model121GEV model88Burr type XII model187


## 4.4. Threshold of the Large Deviation Probability

After determining the final model of each class, we need to determine the threshold of the large deviation probability to detect the network anomaly. Because of space limitations, this paper takes California as the detection area to illustrate the process of threshold determination. Specifically, we leverage an abnormal historical event that occurred in California to help us determine the threshold of the large deviation probability. This abnormal event lasted from 21:45 to 24:00 on May24th 2019, and it affected 238 links [38].Firstly, we extract the RTT time series of these 238 links from the datasetA1 and select the appropriate statistical model for each link. It is worth noting that the final models of these 238 links contain the four statistical models we discussed before. Secondly, we use the corresponding final model to analyze the RTT time series of the 238 links, respectively. Finally, we can obtain the sequences of RTT probability density of these 238 links, and these sequences are considered to be the reference values of the RTT probability density of the 238 links.Next, we collect the traceroutes flowing through California on May24th 2019 from the RIPE Atlas dataset and extract the RTT of these 238 links every 15 minutes continuously to form their RTT time series. Then, according to the duration of the abnormal event, we denote the time period from 21:45 to 24:00 on May 24th as the time period of network anomaly and denote the rest of the time period on May 24th as the time period of the normal network state.After that, we divide the RTT time series of each link into two parts. One is the RTT time series under the normal network stat and the other is the RTT time series under network anomaly. According to equations (8) to (11), we calculate the large deviation probability of each link during the period of network anomaly and normal network state, respectively. Then, we give the cumulative probability distribution of the large deviation probability under the normal network state and the network anomaly. The results are shown in Figure 4, where the x-axis is the large deviation probability, and the y-axis is the cumulative probability.Figure 4
The cumulative probability distribution of the large deviation probability under the normal network state and the network anomaly.As can be seen from Figure4, the large deviation probability values of 96.1% links are greater than 10−24 under the normal network state. On the contrary, the large deviation probability values of all the links are lower than 10−24 under the network anomaly. Suppose that the threshold of large deviation probability is 10−24, our approach can detect the network anomaly accurately and only has the false detection rate of 3.9%. To ensure that our approach can detect all the network anomalies in California effectively, we set Δ2 as 10−24. According to this method, researchers can determine the threshold of large deviation probability for any detection area.It is worth noting that the threshold of large deviation probability (i.e.,10−nHεi/Ui=10−24) is too small, leading to the fact that it is inconvenient for network managers to detect the network anomaly in practice. To address this challenge, this paper takes nHεi/Ui (see equation (10)) as the criterion for anomaly detection, which is called the relative entropy of RTT. Specifically, when the relative entropy of RTT of the link is greater than 24, we conclude that the network anomaly occurs in this link. Moreover, while detecting the network anomaly in California, the critical value of the relative entropy of RTT we set is applicable for any statistical model because the final models of the 238 links contains all statistical models.


## 4.5. Case Study

### 4.5.1. The Validity of RTS detection

Based on the threshold of the relative entropy of RTT, we also select California as the detection area and leverage another historical abnormal event occurred in California to evaluate the rationality of model selection and the validity of RTS detection. This abnormal event lasted from 11:53 to 17:20 on October21st 2016 [39].We, firstly, extract the links located in California from the 28,984 IPv4 links, and these links are clustered into the classC1. Based on the previous analysis (see Section 4.3), we select the GEV model to analyze the RTT time series of the 7888 links. Then, we obtain the sequences of RTT probability density of these 7888 links, and these sequences are considered to be the reference value of RTT probability density of the 7888 links.Next, we collect the traceroutes flowing through California on October21st 2016 from the RIPE Atlas dataset and extract the RTT of the 7888 links every 15 minutes continuously to form their RTT time series. Then, we monitor the RTT of each link continuously and calculate their relative entropy of RTT. Finally, we detect the network anomaly by observing whether the relative entropy of RTT of any link exceeds 24.Because of space limitations, this paper selects one link randomly (i.e., 184.105.213.xx-184.105.65.xx) from the 7888 links and takes its RTT time series as an example to illustrate the process of anomaly detection. To protect the privacy of link information, we hide the last four-bit of the addresses. The relative entropy of RTT of link 184.105.213.xx-184.105.65.xx is shown in Figure5, where the x-axis is the time (in hours), the y-axis is the relative entropy of RTT, and the dotted line is the critical value of the relative entropy of RTT.Figure 5
The Relative entropy of RTT of the link 184.105.213.xx-184.105.65.xx.As can be seen from Figure5, the relative entropy of RTT is below the critical value before 11:53. Then, it increases rapidly and exceeds the critical value from 11:53 to 12:20. Then, the relative entropy of RTT is gradually below the critical value from 12:20 to 17:05. Next, the relative entropy of RTT increases again and exceeds the critical value from 17:05 to 17:20. It can be inferred from Figure 5 that the network anomaly occurred from 11:53 to 12:20 and from 17:05 to 17:20, respectively, which is basically in good agreement with the time reported in [40]. Therefore, the experimental results demonstrate that RTS detection can detect the network anomaly effectively.


### 4.5.2. The Correlation between Links

To verify the correlation between links, we also observe the relative entropy of RTT of the remaining 7887 links. The experimental results show that monitoring the relative entropy of RTT of 7104 links can detect network anomaly effectively. For the remaining 783 links, we speculate that because these links are located far away from the place where the network anomaly occurred, they are not significantly affected by the network anomaly. Although RTS detection cannot accurately evaluate the impact of network anomaly, it can detect the network anomaly by monitoring any one of the 7105 links. Therefore, the approach we proposed can greatly reduce the cost and detection time and understand the impact of network anomaly roughly.


### 4.5.3. The Validity of Model Selection

To verify the validity of model selection, this paper uses the remaining three statistical models to analyze the relative entropy of the RTT of the link 184.105.213.xx-184.105.65.xx again and gives the trend of the relative entropy of RTT in turn. The results are shown in Figures6 to 8.Figure 6
Anomaly detection based on the normal model, and the relative entropy of RTT of the link 184.105.213.xx-184.105.65.xx.Figure 7
Anomaly detection based on the log-normal model, and the relative entropy of RTT of the link 184.105.213.xx-184.105.65.xx.Figure 8
Anomaly detection based on the Burr Type XII model, and the relative entropy of RTT of the link 184.105.213.xx-184.105.65.xx.Based on the experimental results from Figure5 to Figure 8, we give the accuracy and false positive rate of the four statistical models, respectively, which are shown in Table 4. Accuracy represents the probability that the detection method can detect the network anomalies accurately, and the false positive rate represents the probability that the detection method identifies the normal network state as the network anomaly by mistake.Table 4
The accuracy and false positive rate of the four statistical models.
Statistical modelAccuracy (%)False positive rate (%)Normal model92.346.7Log-normal model95.133.2GEV model99.80.5Burr type XII model99.40.9Based on the results of Table4, we can draw three conclusions: (1) because of the lower goodness of fit of the normal model and the log-normal model, the detection method based on the normal model or the log-normal model achieves lower accuracy and higher false positive rate. Therefore, the detection methods based on these two models is unacceptable. (2) The detection method based on the Burr type XII model achieves better results of detection, however, it has a longer modeling time than the GEV model (see Table 3). In practice, the detection method based on the Burr type XII model may consume a long time for anomaly detection. (3) The experimental results show that the Bayesian information criterion can be used to select the appropriate model (i.e., the GEV model) for analyzing the RTT time series of links, which can help the network managers detect the network anomaly effectively.


## 4.5.1. The Validity of RTS detection

Based on the threshold of the relative entropy of RTT, we also select California as the detection area and leverage another historical abnormal event occurred in California to evaluate the rationality of model selection and the validity of RTS detection. This abnormal event lasted from 11:53 to 17:20 on October21st 2016 [39].We, firstly, extract the links located in California from the 28,984 IPv4 links, and these links are clustered into the classC1. Based on the previous analysis (see Section 4.3), we select the GEV model to analyze the RTT time series of the 7888 links. Then, we obtain the sequences of RTT probability density of these 7888 links, and these sequences are considered to be the reference value of RTT probability density of the 7888 links.Next, we collect the traceroutes flowing through California on October21st 2016 from the RIPE Atlas dataset and extract the RTT of the 7888 links every 15 minutes continuously to form their RTT time series. Then, we monitor the RTT of each link continuously and calculate their relative entropy of RTT. Finally, we detect the network anomaly by observing whether the relative entropy of RTT of any link exceeds 24.Because of space limitations, this paper selects one link randomly (i.e., 184.105.213.xx-184.105.65.xx) from the 7888 links and takes its RTT time series as an example to illustrate the process of anomaly detection. To protect the privacy of link information, we hide the last four-bit of the addresses. The relative entropy of RTT of link 184.105.213.xx-184.105.65.xx is shown in Figure5, where the x-axis is the time (in hours), the y-axis is the relative entropy of RTT, and the dotted line is the critical value of the relative entropy of RTT.Figure 5
The Relative entropy of RTT of the link 184.105.213.xx-184.105.65.xx.As can be seen from Figure5, the relative entropy of RTT is below the critical value before 11:53. Then, it increases rapidly and exceeds the critical value from 11:53 to 12:20. Then, the relative entropy of RTT is gradually below the critical value from 12:20 to 17:05. Next, the relative entropy of RTT increases again and exceeds the critical value from 17:05 to 17:20. It can be inferred from Figure 5 that the network anomaly occurred from 11:53 to 12:20 and from 17:05 to 17:20, respectively, which is basically in good agreement with the time reported in [40]. Therefore, the experimental results demonstrate that RTS detection can detect the network anomaly effectively.


## 4.5.2. The Correlation between Links

To verify the correlation between links, we also observe the relative entropy of RTT of the remaining 7887 links. The experimental results show that monitoring the relative entropy of RTT of 7104 links can detect network anomaly effectively. For the remaining 783 links, we speculate that because these links are located far away from the place where the network anomaly occurred, they are not significantly affected by the network anomaly. Although RTS detection cannot accurately evaluate the impact of network anomaly, it can detect the network anomaly by monitoring any one of the 7105 links. Therefore, the approach we proposed can greatly reduce the cost and detection time and understand the impact of network anomaly roughly.


## 4.5.3. The Validity of Model Selection

To verify the validity of model selection, this paper uses the remaining three statistical models to analyze the relative entropy of the RTT of the link 184.105.213.xx-184.105.65.xx again and gives the trend of the relative entropy of RTT in turn. The results are shown in Figures6 to 8.Figure 6
Anomaly detection based on the normal model, and the relative entropy of RTT of the link 184.105.213.xx-184.105.65.xx.Figure 7
Anomaly detection based on the log-normal model, and the relative entropy of RTT of the link 184.105.213.xx-184.105.65.xx.Figure 8
Anomaly detection based on the Burr Type XII model, and the relative entropy of RTT of the link 184.105.213.xx-184.105.65.xx.Based on the experimental results from Figure5 to Figure 8, we give the accuracy and false positive rate of the four statistical models, respectively, which are shown in Table 4. Accuracy represents the probability that the detection method can detect the network anomalies accurately, and the false positive rate represents the probability that the detection method identifies the normal network state as the network anomaly by mistake.Table 4
The accuracy and false positive rate of the four statistical models.
Statistical modelAccuracy (%)False positive rate (%)Normal model92.346.7Log-normal model95.133.2GEV model99.80.5Burr type XII model99.40.9Based on the results of Table4, we can draw three conclusions: (1) because of the lower goodness of fit of the normal model and the log-normal model, the detection method based on the normal model or the log-normal model achieves lower accuracy and higher false positive rate. Therefore, the detection methods based on these two models is unacceptable. (2) The detection method based on the Burr type XII model achieves better results of detection, however, it has a longer modeling time than the GEV model (see Table 3). In practice, the detection method based on the Burr type XII model may consume a long time for anomaly detection. (3) The experimental results show that the Bayesian information criterion can be used to select the appropriate model (i.e., the GEV model) for analyzing the RTT time series of links, which can help the network managers detect the network anomaly effectively.


## 5. Discussion

The framework proposed in this paper has several implications for the networking community for the following reasons: (1) as our approach can reduce the time for anomaly detection, the network managers can leverage our approach to detect the network anomalies quickly, which can reduce the impact of network anomalies on their customers. (2) According to the clustering algorithm proposed in this paper, network managers can monitor and manage a large number of links in the detection area effectively, which can improve their maintenance efficiency.However, several limitations should be considered when leveraging our approach. Firstly, with the proposal of a large number of statistical models, the statistical model considered in this paper may not be the most suitable model for anomaly detection in some scenarios. Hence, we need to consider more models rather than the four in this paper. Secondly, our approach can only evaluate the impact of network anomalies roughly. Hence, it cannot accurately give the number of links that are affected by network anomalies. The solutions to these limitations are left as future work.


## 6. Conclusion

In this paper, we have proposed RTS detection, an approach to detect the network anomaly based on the RTT time series of links. Specifically, we have proposed a link clustering method by considering the topological location of pairwise links and the similarity between their RTT time series. After clustering the links into different classes, we have leveraged the BIC value to select the appropriate model for each class of links. Next, we have leveraged the appropriate model to analyze the RTT time series of links. Based on the results of modeling, we have proposed a detection method by employing the theory of Large Deviations and Sanov’s theorem. The experimental results demonstrate that the RTS detection can not only reduce the detection time and improve the accuracy of detection effectively but also can roughly evaluate the impact of network anomalies.



---

*Source: 5499080-2022-05-06.xml*