Research Abstracts - 2006

Network Performance Prediction

Ji Li & Karen Sollins

1. Introduction

Currently most research efforts focus on either temporal network behavior prediction or spatial performance inference. However, many network problems require us to consider time and space simultaneously. Previous research has equipped us with strong analytic tools in both aspects. We propose to leverage these techniques by combining them and gaining inspiration from them to create new techniques, so that we can obtain a more accurate and comprehensive understanding of network behaviors. Furthermore, each network element has multiple property metrics. The fact that those metrics may be correlated may help us improve the prediction accuracy.

There has been extensive research on network performance prediction and spatial inference, as we will discuss in detail next. We plan to improve the current techniques in these two areas. Besides, we aim to investigate the following problems: (1) Cross-metric inference; (2) Comparison between different models; (3) Combination of inference and prediction techniques; (4) Error suppression and cancellation; (5) Segment composition.

2. Temporal and spatial techniques

2.1 Temporal prediction

Since we are not good at understanding our future needs or at even future behavior, the best we can do is to learn from the past, including both first and second order effects. Time series analysis has been used extensively to study network performance prediction [1]. Various statistical methods have been applied, including mean, moving average, ARIMA, fractional models, to the history network data in different time scales. Markov Models have also been used to model network behaviors such as loss and delay. Those models include k-th order Markov Chains, discrete-time Hidden Markov Model, and continuous-time Hidden Markov Model. Finally, wavelet-based methods provide a natural way to achieve multi-scale prediction.

2.2 Spatial inference

Spatial inference is often referred as network tomography. Network tomography deals with inferential network monitoring in uncoordinated networks [2]. It uses a limited number of measurements to infer network performance parameters using various statistical techniques under a prior model. A good network tomography scheme does not require cooperation from network devices and does not impact network load. Generally there are three categories of network tomography problems. The first is link-level parameter estimation based on end-to-end, path-level traffic measurements. The second is path-level traffic estimation based on link-level traffic measurements. The third is topology inference. Topology inference is derived from the need of the first two problems because both require network topology information.

2.3 Cross-metric inference

The difficulty in obtaining different network performance metrics can vary widely. For example, latency is easy to measure with low cost, while bandwidth is hard to measure and incurs more cost, and loss rate is very hard to measure due to its small scale. We know that in general some metrics are correlated to some extent. For example, if latency increases, this may be due to longer queues at routers, and loss rate may increase at the same time due to packet drop. Therefore, we can use one network performance metric to predict another. However, so far there is not much work in this area yet.

Our approach is a process of exploration and exploitation. First, we plan to explore the correlation between different performance metrics, such as latency, bandwidth and loss rate. We expect these metrics to show strong correlation when they are determined or affected by the same factors, such as queue length. Otherwise, we will probably not observe strong correlation. Second, based on the result of the first step, we can exploit the correlation to do cross-metrics inference accordingly. For example, if we observe that an increase in latency is usually accompanied with an increase in loss rate or a decrease in bandwidth, then the observations on latency can help to improve the inference and prediction results.

3. Research issues

3.1 Techniques integration

There are different ways in which we can combine temporal prediction, spatial inference and cross-metric inference techniques. One might expect that for our setting, there is some dependency in the prediction and inference. The practical implication of the dependency is that we could obtain a better solution to the problem by solving it as one piece instead of solving the subparts independently and combining them. To gain a sense of the dependency structure that might be present in the two subproblems, we will first analyze the cases where the predict-then-infer model works better than the infer-then-predict one, and vice versa.

Depending the results of this analysis, our research will proceed in different ways. If the analysis shows that the subproblems are indeed dependent, we will use this data to help us design techniques that solve our problem directly, for instance by adding a cased based analysis first and then deciding whether to use the predict-then-infer module or the infer-then-predict model to solve it. On the other hand, it is also possible to design more sophisticated techniques instead of just coupling the independent modules together.

3.2 Error suppression and cancellation

Tightly coupled with the technique integration issue is the error suppression and cancellation problem. In general, neither prediction nor inference techniques can produce perfectly accurate network performance results. All of them introduce some errors in the processing, and these errors propagate between the processing components. If we cannot prevent the errors from propagating between those components, the final prediction result may become too coarse. For our setting, if we understand the relationship between the techniques and the propagation pattern of errors, we may be able to suppress error propagation. Furthermore, we may even make structural parts of the error cancel each other out.

3.3 Segment composition

Not only are segments likely to have different behaviors, but they may be measured independently of each other. Thus, for example, each ISP involved in a path may provide information about the bandwidth that it believes will be available on its segment, but cannot necessarily provide useful information about what other ISPs will provide. In addition, each ISP may use different tools. But more than that, the approaches may be different in different parts of the net, so some ISPs may perform measurements inside their routers, while other performance information may only be available through tomography, from the edges of the net. Different properties need to be composed differently. It is worth noting that in composing metrics across segments, jitter is particularly challenging. The composition function is nothing a simple as additive or bounded by an upper or lower bound.

4. Summary

To summarize, our approach involves various techniques, each of which requires significant research efforts. Cross-metric inference is especially interesting here since it allows us to leverage easy-to-measure metrics to estimate hard-to-measure metrics. More importantly, these techniques are unlikely to be independent, and the way we combine them together is vital to the success of our approach.

References:

[1] A. Sang and S. Li. A predictability analysis of network traffic. In The Proceedings of IEEE Infocom, March 2000.

[2] R. Castro, M. Coates, G. Liang, R. Nowak and B. Yu. Network Tomography: Recent Developments. In Statistical Science, 2004.