Abstract: The existence of time-varying network delay will have some negative impacts on some network services. The dynamic changes of network delay reflect the load characteristics of network path. An important basis for the implementation of congestion control and routing is the accurate prediction of network delay. In this paper, a delay prediction model based on Radial Basis Function (RBF) neural network is establishe which is trained by APC-III algorithm and the method of least squares. This model avoids the cumbersome process of model structure identification and model checking in traditional time-series analysis and overcomes the shortcoming that the traditional neural network can easily fall into local extremum and overtraining. The simulation results show that this model can predict network delay with high accuracy.
INTRODUCTION
In recent years with the rapid development of some delay-sensitive real-time network applications, the Internet needs to provide more reliable and stable network services. Thus, delay characteristics of the network have been paid more and more attention to. Network delay is influenced by multiple factors, such as network topology, forwarding node and background traffic. These factors change randomly over time which can reflect the current performance of the network link (Paxson, 1999; Allman and Paxson, 1999). The use of network resources and performance trends can be obtained by forecasting the dynamic changes of the network delay which can provide a reference for balancing the network load and optimize network performance (Johari and Tan, 2001).
Wong (1978), based on the traditional queuing analysis theory, holds the view that there is no correlation between time intervals of data transmission but the predicted results have a great difference with the network measured data. The conclusion from these articles (Jiao et al., 2006; Li and Millis, 2001; Yang and Li, 2003) is that the accurate model of the time series based on network delay can be established by AR or ARIMA model of low level which provides predictive values with high accuracy. However, the model cannot meet the requirement of dynamic prediction of network delay. Parlos (2002) and Srikar (2004) have respectively carried out prediction and analysis of the variation of network delay by using Multilayer Perceptron (MLP) neural network with different algorithms. However, there are some questions for the traditional neural network, for example, falling into the local extremum easily and the limited capacity of extrapolation.
Compared with multilayer perceptron, RBF neural network overcomes many disadvantages of the traditional neural network which has its own unique characteristics in terms of network structure, learning algorithm and status updating rules. For this reason, RBF neural network is widely used in many aspects, such as nonlinear function approximation, time series analysis, pattern recognition, information processing, data classification, image processing and system modeling. The main contribution of this study is the design and realization of a model based on RBF neural network to predict the network delay. The model is trained by actual statistical data and then its effectiveness is analyzed and researched through contrasting the actual network delay value with the predicted delay value.
Delay characteristics: The transmission delay of the network constantly changes with operating state of the entire network system. There are some factors that have a great impact on network delay, for example, the amount of data in the network and processor performance of the nodes. In order to find out the characteristics of network delay we should measure network delay continuously for a long time. After carrying out statistical analysis of a large number of experimental data, we summarize that (Zhang, 2003):
| • | The delay values will be very different at different times and in different places |
| • | Network delay is a randomly varying value. The delay, which is discrete, exits at any time |
| • | In any network, the transmission delay between two nodes is within a certain range |
These features will provide assistance to the following simulation and analysis of the results.
Delay prediction model based on RBF neural network: Among popular neural network models, the theory used to build RBF neural network model not only has a solid mathematical foundation but also has many advantages. The most basic form of RBF neural network consists of three layers Fig. 1. The task of its input layer nodes is simply to pass the input data to the hidden layer. In RBF neural network, the basis function of the hidden layer is generally the distance function and its activation function is the Gaussian function in most instances.
APC-III (Hwang and Bang, 1994) algorithm is extended from APC-I algorithm. This method can calculate the center of the radial basis function through a rapid clustering on the collected samples. This algorithm is widely used in pattern classification, because of its high computing speed and small amount of calculation. APC-III algorithm can determine the number of basis functions and the center vector and the width of the radial basis function is a fixed value.
The sole parameter needed to be pre-determined is the clustering radius denoted as R in APC-III algorithm. Generally, R is computed via Eq. 1.
| (1) |
where, S is the number of samples and α is the adjustment factor. The value of α can affect the result of R. The amount of calculation is too much, especially when there are a large number of samples, by using the mentioned equation.
| Fig. 1: | Structure diagram of RBF neural network |
If we just take a subset of samples to compute R approximately, the accuracy of the neural network will be affected. In order to improve the accuracy, we can take the arithmetic mean of R computed from a plurality of different subsets. The specific implementations of the algorithm are as follows.
At first, define some variables. The input of the algorithm is X = {X1, X2, …, XS} and the output is the center of each class. We denote the center of class j as bj, the number of samples in class j as nj, the number of clusters as m, the distance between the sample Xi and the center of class j as Dij.
| Step 1: | Initialize the parameters. The initial value of m is set to be 1 and b1 is set to be X1; the value of n1 is 1. Also, there has to be an appropriate value for α |
| Step 2: | Calculate the value of R via Eq. 1 |
| Step 3: | Compare Dij, the distance between Xi which is a new input sample and the existent cluster center, with R. When Dij = R, Xi should be classified into class j and the data center of class j should be updated via Eq. 2. Also, the number of samples in class j increases, that is, nj = nj+1. When Dij>R, we need create a new class and increase the number of clusters, that is, m = m+1. Then, bm, the center of class m, is set to be Xi and nm is set to be 1: |
| (2) |
| Step 4: | Execute step (2) and step (3) repeatedly until all samples are trained |
After the end of the algorithm, the hidden layer structure of RBF neural network will be determined. Then, we can carry out a supervised learning for RBF neural network by using the method of least squares to get the optimal weight of the hidden layer.
So far, the delay prediction model based on RBF neural network has been established.
Simulation experiments of delay prediction based on RBF neural network: Network delay is the time interval that a data packet transmits from a node to another which is one-way delay. However, it is very difficult to establish an accurate computational model for network delay, because network load and dynamic routing change over time. Nowadays, Round Trip Time (RTT) is used in actual experimental research process, instead of one-way delay. RTT is the time interval that a packet is transmitted from one host to another and back to the original host.
We selected a host from campus networks of North China Electric Power University and Central South University respectively for measuring network delay. We continuously measured the delay during the daytime and recorded these measurements for several days. The measurements of each day were regarded as a sample space. During measurement, network delay was measured every 25 sec. Four data packets were sent each time and the size of each packet was 128 bytes. The average of each measurement was recorded as a delay datum. We carried out the simulation experiment by using two sample spaces selected optionally from the sample set. The delay graphs of these two sample spaces are presented in Fig. 2. It is revealed that the trends and ranges of the delay are roughly the same. Network delay is small during the daytime; however, it becomes big to some extend in the evening, due to the increase in the amount of network usage. The change of network delay shows certain regularity.
In the simulation, the delay prediction model was established by using the method elaborated in the previous section. At first, we need select a center vector from the training sample set and calculate the variance for the basis function of the hidden layer. Then, we could compute the optimal weight of the hidden layer by using the method of least squares. Under the premise of not affecting prediction accuracy and training speed, the delay prediction model was trained by the delay data measured in the network. In order to predict the time delay of a certain moment accurately, we selected seven network delays in previous times and another three variables which were the variations of network delay in previous times as the input of the delay prediction model.
We conducted our simulation experiment by using these selected samples in MATLAB. The delay data of one day were used to train the neural network as initial sample. After the training, we validated the effect of the neural network model by using three data sets which were selected from another sample in different time periods. There were 300 consecutive data in each data set. The results of prediction are presented in Fig. 3.
The curves of predicted delay and actual delay are very similar to each other. When the actual delay fluctuates smoothly or dramatically, the variation of the predicted delay becomes small or big accordingly.
| Fig. 2: | Delay of two days |
| Fig. 3(a-f): | Results of prediction, (a) Delay in the morning, (b) Delay prediction in the morning, (c) Delay in the afternoon, (d) Delay prediction in the afternoon, (e) Delay in the evening and (f) Delay prediction in the evening |
| Fig. 4(a-c): | Prediction errors, (a) Error in the morning, (b) Error in the afternoon and (c) Error in the evening |
Therefore, RBF neural network can well predict the variation of network delay, especially in the condition that the change of delay is random and non-linear. Prediction errors are presented in Fig. 4 to show the performance of the delay prediction model based on RBF neural network. Most of the prediction errors are less than 2 m sec and nearly half of the prediction error rates are beyond 5%. Moreover, when delay variation is violent, the prediction error becomes bigger.
CONCLUSION
In this study, we establish a time delay prediction model based on RBF neural network by using APC-III algorithm and carry out the simulation experiment in MATLAB. The results show that this time delay prediction model can predict the trend of network time delay accurately and the value of network delay with relatively high accuracy. However, dramatic changes in delay will reduce prediction accuracy to some extent. In order to obtain a better effect, we need seek a better algorithm for the delay prediction model based on RBF neural network to further improve the accuracy and reduce the impact of dramatic changes on prediction accuracy.
ACKNOWLEDGEMENT
The study is supported by the Fundamental Research Funds for the Central Universities.