Cross Traffic Estimation By Loss Process Analysis

Cross traffic estimation by loss process analysis Kavé S ALAMATIAN, Bruno BAYNAT, Thomas B UGNAZET Abstract— This paper applies to cross traffic estimation, a new methodology for analyzing and interpreting measurement collected over Internet. This new approach is based on inferring cross traffic characteristics that lead to the observed losses by using an associated a priori constructive model. The constructive model used in this paper is an MMPP/M/1/N single server bottleneck. The originality of this solution is that we start with observed loss process and infer inputs that have lead to these observations. These methods presented in the paper provides a powerful solution to address the complexity of interpreting IP active measurement and empirical network modeling.

I. I NTRODUCTION Much research effort has been spent during the last decade on measuring and describing the performance of IP networks and the Quality of Service (QoS) provided by them. These studies have contributed to a better understanding of the real Internet. However, most of this researches has remained descriptive and studies focusing on interpreting and modeling these measurement are relatively infrequent. Modeling the QoS in real networks is a challenging task, as flows crossing the network experience highly varying loss rates and delays. This task is made more difficult by the fact that QoS is the reflection of the traffic interactions in the network and the relation between QoS and traffic is not straightforward. In this paper, a new methodology presented in [1] is applied to cross traffic estimation. This approach is original as it proceed in inverse direction compared to classical approach : it begin from the observed losses traces and estimates by statistical inference, the input profile that have led to the loss trace. By this way, it open the way for an interpretation of observation by the inferred cross traffic. Surveys campaign over Internet have been widely carried during the past years [2], [3], [4]. Globally two general classes of measurement were applied : active and passive measurement. Passive measurements are by nature non-intrusive. In this class of measurements, traffic parameters are monitored at a particular point of the network such as a router or a Point of Presence (POP). This restricts the gathering of passive measurements to network operator who have access to these measurement points. Nevertheless, passive measurements, even if they are very useful for calibrating models and understanding what happens inside a network, are hardly applicable for end-to-end QoS prediction as they remain local to the point of measurement. Active measurement are more intrusive, as they inject traffic into the network. The rationale behind active measurement is that estimating the end to end QoS, as sensed by real application can only be done by putting oneself in place of the real application. In this approach a probe sending process injects probe packets into the network. At the other end of the network a measurement agent records some metrics on each received probe packet. The IPPM group of the IETF has defined a framework for end-to-end performance metrics [5] to be collected on probe

packets. Three main types of information are extracted from the received probe packet flow: packet size, packet loss process and packet delay process. These basic metrics are used to derive more complex metrics such as loss rate, loss run length, jitter, etc. The probe packets may be sent into the so-called "type P" packets. ICMP (in ping surveys) or UDP packets might be "P" packets. However, ICMP probing is nowadays more difficult because of issues related to the Ping of the Death attack. A lot of active [3], [6], [7], [6], [4] measurement surveys has been made during the past few years and some measurement infrastructures have been deployed [8], [9]. Due to non-synchronized clocks between receivers and senders, the reliable measurement of packet delay is difficult. Strict synchronization of two entities connected by a varying delay link, can prove to be impossible without access to an external universal time reference as provided by a GPS (Global Positioning System) time reference. Even if GPS acquisition cards are now more frequently used enabling feasible delays with a resolution around 1 sec, It worths to try to extract as much as information from the loss process which much more simple to measure. Active measurements are the source of some interesting and challenging problems. The first one is related to interpreting them. By interpreting measurement we mean to relate effect, i.e. observations, to causes, i.e. traffic fluctuations. Interpretation is necessary to answer to "what if" questions, that are essential for proactive traffic engineering. IP performance metrics are measured by end users who are positioned at the border of the network and cannot observe cross traffic inside the networks. This means that active measurements don’t give a complete view of the causes leading to the losses or delays measured. This important remark explains to some extent why interpretation of active measurement is difficult. In fact, interpretation of active measurement needs some a priori model about the process leading to the observations, and some knowledge about the cross traffic and the network characteristics. However, as this information is not readily available, it should be inferred using the information obtained from the network by the measurement probes. In this paper, the methodology presented in [1] is applied to infer characteristics of traffic that most likely led to an observed loss trace. This new methodology use an a priori model describing how flows interact inside the network and lead to packet losses. Based on this a priori model, the traffic parameters that will most likely lead to the observed (or measured) loss process are inferred by a statistical estimation procedure. This methodology helps in bypassing the previously described problem caused by incomplete access of end users to traffic inside network, as the inferred cause of losses will be available at the same time as the observed loss process. This approach has been followed subconsciously, with a simple a priori M/M/1 model, in [10]. In this paper, we will generalize the results of [10] to the more flexible and powerful Markov Modulated Poisson

Process (MMPP) traffic models, and at the same time formalize a methodology for inferring network and traffic characteristics based in active measurements. The paper is organized as follows: the applied methodology is introduced in section II. In section III, the a priori model describing how flows interact inside the network will is presented and its loss behavior is derived. The methodology described in section II is applied in section IV to some scenarii and the results are analyzed. Concluding remarks and directions for future research are given in section V.

II. M ETHODOLOGY Two main classes of approaches have been applied so far to the analysis of losses in networks: constructive approaches and descriptive approaches. Constructive approach has been widely used for many years to model systems in general. It is based on the derivation of a model that ideally produces the same output as the system for an external observer. These models provide a description of network elements that is as close as possible to the real network. The network is described as a combination of queues, routers, etc., and a scenario defining the parameters of the system in terms of the arrival process, capacity, buffer space, etc. This approach is widely adopted in performance analysis and queuing theory. The generalization of the use of ns [11] as a simulation tool for complex networks has made possible very precise and detailed modeling of network elements and their analysis with this approach. Even if the constructive approach can answer "what if" questions, arising when one wants to evaluate the impact of changes in network parameters or architecture, in the performance of the system under study, Nevertheless, this approach suffers from a major drawback: the assumption put on the structure of the network and on the scenario are so strong that it is very unlikely that the results obtained by this way will generalize to the real Internet. This drastically restricts the field of application of the constructive approach for modeling and evaluating real loss traces gathered in the Internet. On the other hand, the descriptive approach is based on measurements of some metric, such as the loss process, in operational networks. It models the QoS as seen in the real world by describing it by some statistical parameters such as moments of different orders (mean, variance, autocorrelation, Hurst parameter, etc). This approach sees the network as an opaque black box, meaning that the descriptive approach only describes the metrics measured without trying to explain the mechanism generating the observations. This process mainly aims toward predicting the QoS experienced by applications under some reproducibility or stationarity assumptions. However, as these models do not integrate the mechanisms generating the observation, they cannot help in predicting what will happen if these stationarity assumptions are broken, due to changes in network architecture or more simply due to changes in traffic parameters. This means that this approach cannot be used for network dimensioning, capacity planning or predicting the QoS improvement consecutive to changes in network parameters.

A. Constructive approach Constructive approaches have been widely applied to the loss process analysis in the performance analysis literature. These works mostly make the assumption that an end to end link crossing the network can be described by the behavior of a single server queue at the bottleneck with a drop tail policy. The loss probability is then specified to be the overflow probability of this single server queue. The simplest case of an M/M/1/N model has been extensively studied in [10]. More general cases with general traffic (even Long Range Dependent) have also been studied in [12], [13]. More complex and sophisticated analyses can be done by simulation, even without the single bottleneck assumption. Empirical observations have shown that the correlation structure of loss process is an important property. Nevertheless most of the performance and the constructive analyses have put emphasis on the probability of overflow in queues, and the correlation structure of the loss process has not been much investigated analytically. Memory observed in the loss process can be explained as resulting from the queuing system, and from the dependencies introduced by the input traffic. In the case of M/M/1/N it is clear that the memory can only result from the queuing since the input traffic is memoryless. M/M/1/N queue have an exponentially fast convergence to the stationary state of the queue, meaning that the memory generated by the queue is small and may not be able to describe the large memory observed in loss traces. It will be shown in the appendix that the loss process observed by an active measurement flow at the output of the M/M/1/N queue will be uniform and memoryless. The analysis given in [10] is not satisfactory as an input process with memory is needed to express memory observed in empirical loss traces. In this paper, a MMPP/M/1/N a priori constructive model is assumed for the single bottleneck. The MMPP/M/1/M is not the only model that can be applied to the analysis of losses observed on Internet. The single bottleneck model can be trade with a "network of queues" model or even more complex input traffic hypothesis. However the proposed model is good enough. It will be shown in this paper that it can reasonably explain losses observed over real networks and there is no need from more complex model. Moreover, the MMPP input traffic is convenient since it permits a controlled amount of correlation into the loss process. Moreover under some reasonable hypotheses it remains tractable. This constructive model will be described in section III. B. Descriptive Approach Descriptive approaches have also been widely applied to the analysis of losses. These approaches describe the loss process by some statistical parameters such as means or higher order moments (autocorrelation, variances, Hurst parameter, etc). Descriptive approaches to losses observed on the Internet have shown that the distribution of the number of consecutive lost packets is approximately geometric, or rather that the head of the distribution is geometric, and that the tail includes a few events (that might contribute significantly to the overall loss rate, since a single event in the tail indicates a loss burst with a large num-

ber of lost packets) that appear not to have any specific structure [7], [6], [14], [4]. The network connecting the sender and the receiver is a communication channel disturbed by packet losses. In [15], a channel model based on Hidden Markov Model (HMM) is proposed.



) extracted from a measureThe loss process (  if the th measurement ment probe flow is defined as
probe packet reaches its destination and
 if the packet is lost. In HMMs the channel is modelled by "switches" between  different states following a Markov chain
  with
       and stochastic transition matrix state space


 
where     
   . In each of these  states, the channel is uniformly blocking or passing. This defines a probability that a packet is lost at time  while the channel is in state  (     ). [15] presents a procedure based on the Expectation Maximization algorithm for estimating the number of needed states  , the loss probability in each state       , and the transition matrix , based on an observed loss sequence . Unlike non Hidden models, HMMs exhibit infinite dependencies in the observed process, even with only 2 states. This strongly reduces the number of states needed to describe a given loss process. [15] shows that in almost all cases studied less than 4 states are sufficient, where [4] used up to 42 states. Moreover, it will be shown in this paper that HMM states can be related to different traffic regimes in the network, opening the way to estimation of traffic parameters based on the loss process.








C. Mixed Approach In this paper, the methodology described in [1] is applied to the analysis of losses observed on an Internet path during an active measurement round (or during an application session). In this methodology, an a priori model structure is first chosen based on a constructive approach with some of its parameters left unknown. Then descriptive methods are applied to calibrate the unknown parameters to performance metrics as measured on the real network. This approach is innovative as it proceed in an opposite direction compared to classical approach : it begin from the observed losses traces and estimates by statistical inference, the parameters of the cross traffic that give the best explanation of the observed the loss trace In this paper a MMPP/M/1/N single server queue will be used as an a priori constructive model (see section III). Since input traffic to the queue is not observable from the loss process at the output of the queue, a hidden variable estimation procedure based on Maximum Likelihood estimation (using the Expectation Maximization algorithm) will be applied, to infer the unknown input traffic parameters generating the observed loss process. In the sequel we will suppose that measurement probe packets are not fragmented during their sojourn in the network, and we will also assume that packets are either dropped somewhere in the network or received errorless at the other end of the network after a variable transit delay. These assumptions are reasonable if probe packet size are not too large and if we remain on the wired Internet. The measured metric (loss or delay) over each packet of the measuring (or applicative) flow can be seen as a sample of the

state of the bottleneck queue at the arrival time
   of the packet. Now if the sampling renewal process
   verifies the ASTA (Arrivals See Time Averages), the estimates based on probe measurement will be unbiased. The ASTA is valid for Poisson sampling (which lead to PASTA property). However it should be pointed, that even if a single bottleneck assumption is formulated here, measurement probe packet go through several queues before getting to the bottleneck. After passing the first queue, packet will be spreaded by competing background traffic, meaning that when they reach the bottleneck they will no more keep their initial interpacket interval (even if they had been send with a Poisson distribution). In this situation it is difficult to reach to a simple framework as is the case for pure Poisson hypothesis. In this case, the Bias formula given in [16] might be useful for estimating the bias induced by the particular sampling process. However, the derivation of the bias will need a precise analysis of the delay distribution from the source to the bottleneck. This subject is out of the scope of this paper. Nevertheless, because of the random effect of the cross traffic in routers upstream the bottleneck, out of some pathological and non pratical case, we can reasonably assume that the bias will be small and even that LBA (Lack of Bias Assumption) is validated meaning that ASTA property is valid [16]. In order to be able to interpret loss traces obtained by active measurement, we need to relate the observed loss process to traffic inside the network. The methodological approach presented in [1] consists of defining a priori classes of models relating the inbound traffic to these processes. The relationship between the traffic flowing into the network and the loss process can be described by a constructive model defining precisely (or even roughly) the interactions between different flows resulting in the QoS as observed at the output of the network.

Unknown input

θ

Constructive Model

Ti S(t) D(t)

S(Ti) D(Ti)

Fig. 1. Constructive Model based interpretation framework

Some parameters of the constructive model () remain unknown and should be inferred by statistical estimation methods based on the observed loss process. This way, the best (related to an optimization criteria such as Maximum Likelihood or Least Mean squared Error) set of parameters describing the measured performance metric under the assumption of the a priori constructing model is derived. We will describe these steps in section III. III. A NALYSIS OF SINGLE - BOTTLENECK MODEL UNDER MMPP TRAFFIC AND HYPOTHESIS A. Model The constructive model used in this paper is a single server queue representing the bottleneck node, as in [10] (see Figure 2). The queue has a finite buffer of  spaces including the customer in service and uses a drop tail discipline. Packets dropped are lost. The incoming traffic is modeled by combining two

independent processes. The first one models the probe traffic generated by the active measurement (or any other specific application traffic), and is assumed to be Poisson with rate  . The second one represents the cross traffic which will be a superposition of many different traffic flows.

γ

λ1+γ

ss

tra

ffic

λ1+γ

0,1

2,1

α12

α21

α12

0,2

4,1

µ α21

α12

λ2+γ 1,2

µ

λ1+γ 3,1

µ

λ2+γ

µ

λ1+γ

1,1 µ

α21

cro

los t

λ1 λ2 : λK

Horizontal transitions are due to queue size changes and vertical transitions result in state transition in the MMPP.

µ α21

α12

λ2+γ 2,2

µ

α21

α12

λ2+γ 3,2

µ

4,2 µ

Fig. 3. Underlying Markov chain of Model M.

c

affi

tr obe

N

pr

Fig. 2. Model M: a single finite buffer queue under MMPP cross traffic arrival.

As opposed to [10], we model the cross traffic by a  states Markov Modulated Poisson Process (MMPP). When the MMPP is in state , load arrives to the queue according to a Poisson process with rate  . In other words the interarrival time is exponentially distributed with mean 
. State transitions are governed by a Continuous Time Markov Chain (CTMC). Let us call  the infinitesimal generator of this CTMC (   ). This class of models has been proposed for modeling bursty traffic as observed in real networks. These models can capture memory observed in bursty traffic and can also exhibit Hurst parameter for a limited scale range [17], [18]. The service times, more likely to be proportional to packet sizes, are assumed to be i.i.d. exponentially distributed variables, with rate . The resulting model will be referred to as Model M and is depicted in Figure 2 . B. Analysis of the model We thus came up with the constructive model represented in Figure 2. This model is totally defined by the following set of parameters: , the service rate of the server;  , the capacity of the buffer;  , the load induced by "probe traffic";   , the background load of "cross traffic" when the CTMC is in state ; and , the infinitesimal generator of the CTMC (as  is a    matrix, it contains  
   unknowns). The overall traffic intensity in each state  of the MMPP is defined by:



 

Following the methodology described in section II, we need a procedure to determine all of these unknown parameters that best fit the observed loss process measured on the network. Before proceeding further, it is worthwhile noticing that, once all the undetermined parameters have been estimated, all performance parameters of interest of the queuing system Model M such as the queue length distribution or the overflow probability, can easily be derived using any numerical technique [19] applied on the Underlying Markov Chain (UMC). This UMC

and  . is illustrated in Figure 3 in the case where 

However what we need here is to derive the queue characteristics at the time of observation, i.e. at time of arrival of packet probe, meaning that we need to transform the time continuous system to a a discrete one sampled at instant of arrival of the packet probes. The classical method for transforming the time continous MMPP/M/1/N queue to a discrete one is the wellknown uniformization technique [20]. In this technique the time continuous UMC
defining the queue dynamic is transformed

  to a discrete process
 by uniformization, i.e.
 with  being a Poisson point process. It can be shown that the
 and
have the same stationnary distribution. The choice of Poisson sampling process results from the PASTA property. However, we argued in section II-C that the even if the arrival time of the probes are not exactly Poisson distributed however the LBA hypothesis can be accepted. Meaning that the probes uniformization technique can be applied here. Nevertheless, in the case of interest and under mild and realistic hypotheses, the resolution of the overall queuing system can be done easily by the following intuitive argument. It is realistic to think that packet arrival rates are much higher than state transition rates of the MMPP. In other words, in Figure 3 horizontal transitions are much more frequent than vertical transitions. This means that between each MMPP state transition, the queue has enough time to reach a stationary distribution. Under this hypothesis the overall queue behavior can be described as a mixture of stationary behaviors each one corresponding to a given state of the MMPP input traffic. This approach, will be validated by numerical example in section IV, and will be applied in section III-C.4. In order to analyze the loss behavior at the output of the MMPP/M/1/N queue, we first study the behavior of the queue in each state of the MMPP traffic separately. In each of these states the model is an M/M/1/N queue and is equivalent to the model used in [10]. This model is depicted in Figure 4 and will be referred as Model   . From M/M/1/N analysis, it is well known [21] that the overflow probability of the queue of Model   , which is also the loss probability, is given the following expression:

  where



 
        


(1)

 

is the traffic intensity. Figure 5 shows the application of Equation 1 for different values of  . Globally the loss probability

γ

ss t

los t

λi

cro

raff

µ

ic

c

affi

tr obe

N

pr

Fig. 4. Model

.

defined in 1, is a monotone increasing function of . The highest loss probability achieved with a value of    is given by :


 





 

Meaning that when loss rates higher than this maximal value are observed, they are due to    . We will assume in the remaining of the paper that our model has a large value of  (as it is the case in practical networks) meaning that the observed loss probability results from    . At first attempt this hypothesis , all loss rate may appear as a strong one however, for  higher than 1% should be related to a    , and it is clear that in practice loss rate at this level are common. Let’s give another precision here. The previous hypothesis says that high loss rates are explained by traffic intensity higher than 1 in the bottleneck. It is clear that traffic intensity in non-bottleneck routers may be lower than 1, as it is obviously the case in core router where over provisionning is applied. However bottleneck can occur in ingress or peering point and in that points we may have value of   .

0.8

0.7

0.6 Loss probability

C. Estimation of the unknown parameters of the model C.1 Estimation of We let denote the service rate of the bottleneck node. It can easily be obtained from a "packet pair" technique [22], [3]. A packet pair consists of two packets of same size  sent backto-back, i.e., with a spacing that is as short as possible. If this packet pair reaches the bottleneck with capacity back-to-back, i.e. they are consecutive packets in the queue, they will reach the receiver dispersed (spaced) by a transmission delay equal to   . So, the receiver can compute the capacity from the  . Actually it can be meameasured dispersion  , as sured by the pathrate [23] tool. We assume that this parameter is known.

0.9

0.5

0.4 N=5 N=10 N=100

0.3

However, this relation does not say much about the structure of memory in the loss process observed in a M/M/1/N single server model. In the appendix, it is shown that if measurement packet probes are sufficiently spaced, the loss process observed at the output of Model   will be uniform and memoryless with loss probability related to the traffic getting inside the queue by equation (2). The intuitive argument is that if the time interval between probing packets is larger than the time needed by the queue to reach its stationary point, the state of the queue will be uncorrelated, therefore the losses will be independent. We stated earlier that the behavior of the MMPP/M/1/N queue can be described as a mixture of stationary behaviors each one corresponding to a given state of the MMPP input traffic. It was shown that Model  , which is in fact the model describing the loss behavior of each state of the MMPP input traffic, leads to a uniform and memoryless loss process and that there is a one to one relation between the loss probability and the traffic load input to the queue (equation 2). Combining these two remarks leads to the following: loss behavior at the output of the MMPP/M/1/N queue can be described by a mixture of memoryless loss processes each one with a loss probability directly related to the amount of input load at this point. As the input load state will follow a markov chain (because of the MMPP behavior), the loss at the output of the MMPP/M/1/N will follow a HMM, as described in section II-B, with the state of the MMPP acting as the hidden state of HMM. Therefore, all the needed information about the constructive model was derived. We now focus on the second step of the methodology which is the estimation of the unknown parameter of the model.

0.2

C.2 Choice of 

0.1

We let  denote the capacity of the bottleneck node. In this paper we are only concerned with the loss process behavior. It will be shown in section III-C.4 that the loss behavior in a realistic scenario ( large) is insensitive to the value of  . This can be understood intuitively if the traffic intensity is greater than 1. In this case, whatever the value of  , the queue will surely overflow and the behavior of the queue will resume in small fluctuations on queue length. This means that the model and the analysis can be done with an arbitrary (but large enough) value of  . Nevertheless, the delay will be greatly affected by the value of  . It is thus possible to calibrate  in order to gen-

0

0

1

2

3

4 5 6 Value of traffic intensity

Fig. 5. Loss rate as predicted by model

7

8

9

10

 for different values of  .

In this case, Equation 1 can approximately be inverted to obtain the following one-to-one relation between loss rate and traffic intensity (which is insensitive to  ):



   

(2) 

erate a model that also fits with the mean delay. This calibration is out of the scope of this paper. Following considerations explained in section III-B, we only need to have a large value of  . We will use an arbitrary value of  , meaning that all loss rate above   are due to traffic intensity higher than 1. C.3 Estimation of  We let  denote the rate of probe packet traffic. It is obviously a known parameter. However, this value should be chosen carefully, as a value too high will change the state of the measured network and a value too small will reduce the quality of the estimation. C.4 Estimation of the traffic intensity   It has been shown in section III-B, that the loss at the output of the MMPP/M/1/N will follow a HMM with a one to one relation between loss probability in each state and input traffic load. In order to estimate the traffic intensity in each state   and from it the rate  of the cross traffic packets, we need to first estimate and calibrate an HMM best describing the measurement loss process. The procedure for HMM model calibration has been presented in [15]. This procedure is based on the ExpectationMaximization algorithm and gives the number of needed states for describing a given active measurement loss trace as well as the parameters of the HMM model which are the transition ma  and the vector   . The procedure of HMM trix model calibration give also the sufficient number of state to consider. The sufficiency is determined following a entropic argument. Now following the conclusions found in section III-B we will assign to each state  a value of   given by equation (2). Therefore, one can estimate the unknown parameter   :







  



  for 

  

(3)

Thus, each state  of the HMM is now associated with a rate  . This value will be used as an estimate of the cross traffic rate of Model M, when the MMPP is in state . C.5 Estimation of the infinitesimal generator  The remaining parameter to estimate is the infinitesimal generator  of the CTMC driving the behavior of the MMPP arrival cross process. The HMM calibrating procedure described    of the HMM, where in [15] gives the transition matrix  represents the probability of one probe finding the MMPP cross traffic process in state  (with intensity   ) and the next one finding it in state (with intensity   ). Following the discussion about the uniformization technique given in section III-B, we can relate the required infinitesimal of the generator  of the CTMC to the transition matrix HMM, by the following argument. With any Continuous-Time Markov Chain described by an infinitesimal generator , can be associated a transition matrix 
 within a time  defined as:










½
 

  


        

  ¼             





 

TABLE I PARAMETERS OF THE MMPP TRAFFIC SOURCE USED IN SCENARIO 1

The coefficients of this matrix are the probabilities of transiting between states in a time equal to . In other words, 
  is the probability of being in state at time  , knowing that the CTMC was in state  at time , and this for any time . Using this property, one can relate  to by setting the transition matrix associated with  in a time equal to the mean interarrival time of the measurement probes (
) equal to the transition matrix of the HMM :








   

 

(4)

The factor  controls the dynamics of the CTMC. From this relation, we obtain the estimation of the unknown infinitesimal generator:



   

This calculation can be performed by diagonalizing matrix :



  


 is thus obtained from: 

 
   


(5)

where   is a diagonal matrix in which each diagonal element is the logarithm of that in . For each value of  a specific infinitesimal matrix will be derived. Higher values of  lead to more dynamic and rapidly changing MMPP cross traffic. For the purpose of interpreting and modeling active measurement, . This value will make the scale of one could choose  variation of the MMPP and loss process the same. However, if information about the dynamics of the input traffic is available, e.g. by passive measurement, it can be fine tuned. IV. N UMERICAL R ESULTS In this section, we will see the validation of the proposed approach to one simulated scenario as well as to a real loss trace gathered over the Internet. For the simulated scenario, we have added to the ns environnement [11] the MMPP traffic generating source and we have simulated over a topology issued from the model shown in fig.  2 with a queue length   and a bottleneck capacity Mbps. The loss trace observed by a probe flow with rate 16 kbps was gathered. The parameter of the MMPP used in this simulation are shown in table I. We have applied the proposed approach to the loss process observed by the probe flow and we have inferred the MMPP parameters. The loss probabilities in each state predicted using




               ¼              


                             
     

TABLE II I NFERRED PARAMETERS OF THE MMPP TRAFFIC SOURCE FOR SCENARIO 1

Eq. 2 and Eq. 1 are
         . The infered loss probability based on the observed loss process are
       . We have used Eq. 2 for inferring the load factor relative to the last two states and Eq. 1 for the first states (we have supposed that  is known for the first state). The results are shown in table II As it can be seen the inference process was successfull to retrieve the parameter of the initial MMPP source. However the inference for low loss rate (or equivalently low load factor) is difficult specially if the queue length is large and/or unknown. Nevertheless, the inferred MMPP model is able to interpret correctly the observed loss process as the method enable to track state variations correctly (Fig. 6).

TABLE III HMM PARAMETERS CALIBRATED ON THE OBSERVED LOSS PROCESS

state of the input MMPP process, the losses can be assumed as independent, as the queue has enough time to be completely renewed between the arrival of two probe packets (see appendix). The loss rate measured over windows of 5 sec on this loss trace are depicted in Fig 7 and shows the highly fluctuating profile of this trace. Loss rate observed over windows of 5 sec 1

0.9

0.8

0.7

Simulated state transition

0.6 Loss rate

3

2.5

0.5

0.4

2 0.3

1.5 0.2

1 950

1000

1050

1100

time Inferred state transition

0.1

0

3

0

1000

2000

3000

4000

5000

6000

Fig. 7. Loss rate observed over windows of 5 sec on the loss trace measured on Internet.

2.5

2

1.5

1 950

1000

1050

1100

time

Fig. 6. Simulated and inferred state transition for the simulated MMPP source.

After validating the approach over a simulated scenario, we have applied the methodology on a real trace gathered over Internet. This trace contain 8 hours of active measurement made by a flow of 100 bytes packet sent with 50 ms interval (leading to a rate of 16 Kbps) sent from a university site in France (LRI, Orsay) and the ICSI ( International Computer Science Institute) in California, USA in July 2000. The bottleneck capacity at the time of measurement was 34 Mbps. The mean loss rate observed on this trace was 18.58%, which is high and was not so unusual at that time. Concepts developed in previous are applied to sequences of 10,000 packets (corresponding to a period of 500 seconds). The applied procedure will be described. The interpacket time (50 ms) is larger than the time scale of the queue as defined in the appendix. This means that conditioned on the

The application of the HMM estimation process [15] generates the results in Table III. The stationary state distribution is also shown as  . The HMM calibration procedure give also the sufficient number of states for modelling the given sequence of loss. In this case only three states were sufficient to model the loss process at the observation level. Following the previously described procedure, parameters of the HMM can be transformed into the parameters of the a priori constructive model. This transformation results in the values shown in table IV. Before getting to the interpretation of these results, let’s check the intuitive approximation presented in section III-B for the resolution of the UMC and the derivation of the queue length distribution. We numerically solved by the Gauss-Seidel technique [19] the UMC for a queue size   and for the infinitesimal matrix given in Table IV. The UMC has 153 states and the developed program in C takes 2 minutes (and 20000 iterations) for converging to the steady state queue length distribution. On the other side, the proposed approximation explain the behavior of the MMPP/M/1/N queue as a mixture of the stationary


               ¼              



TABLE IV C ALIBRATED PARAMETERS FOR THE a priori MODEL

behavior of a M/M/1/N model (Model   ) corresponding to a given state of the MMPP input traffic. This approximation give ! as : the queue length distribution Prob
Prob


!

  




 Prob


!



(6)

where  is the stationary probability of the MMPP traffic being in state  and Prob
 ! is the queue length distribution for Model  which is given by [21] : Prob




!


       
  



The two distributions (calculated by the Gauss-Sidel method and predicted by the approximation) are shown in figure 8 in a log scale (to show the small difference between the two distribution in small values of queue length). It can be seen that these two Pdf of the MMPP/M/1/N queue length for N=50

0

10

might mostly result from a slashing in the capacity of the bottleneck, instead than a surge in the amount of data getting into the network. Moreover 65% of the time the traffic intensity was around 1.24. Meaning that most of time the input load was 24% higher than the capacity of the bottleneck. This can be explained by the lack of admission control in the actual Internet as well as by the bang-bang behavior of TCP who opens its window till a loss is observed and by this way injects more traffic than can be processed by network. In the remaining 31% of time the input load exceeds the bottleneck capacity by 7%. Another interesting application of the calibrated model is a posteriori state estimation based on observed loss trace. The estimated state transition can greatly help on understanding the loss process behaviour as it will show at each time point what was the state of the input traffic. [15] presents a procedure for estimating the sequence of states taken by the HMM and the state transitions. This procedure can follow a Viterbi algorithm with a look ahead windows of several packet or a Maximum a Posteriori Mode (MPM) which make possible to estimate the actual state of the network. The MPM has been applied to the dataset and the estimated state transitions are shown in Figure 9 for 10,000 packets (500 seconds). A clear regime transition around packet 338 between state 2 and 3 can be seen. It means that the traffic intensity went from 1.259 to 1.07. The inverse transition occurs around packet 483. Some spurious transition between state 1 and 2 representing surging traffic load or sudden slashing of the capacity of the bottleneck, that has completely congested the network (with a traffic intensity around 20) can be observed. This example shows the feasibility of doing an online monitoring of the inbound traffic to the bottleneck, by monitoring the loss process gathered from an active measurement flow.

Numerical derivation Approximation Heuristics Estimated state by MPM method

−1

10

10

State

Probability

3 −2

2

−3

10

1 −4

10

0

10

20

30 Queue length

40

50

60



Fig. 8. Steady state queue length distribution calculated by numerical derivation . of the 150 state UMC and the mixture of models Models

0

1000

2000

3000

4000 5000 6000 Packet number

7000

8000

9000

10000

Fig. 9. Estimated state transition for the measured trace.

distributions are only slightly different at small queue size. As we are more interested in the last part of the distribution when losses occurs, the adequation between the two curve is even better. Meaning that the simple approximation is correct. The calibrated MMPP/M/M/1/N makes possible to interpret the loss trace measured over the network. First, results in Table IV show that the traffic intensity of the network was as high as 20 for at least 2.6% time. This high value of traffic intensity

Another very interesting application of the MMPP/M/1/N model is for simulation. It is possible to get loss traces similar to real traces by feeding the calibrated MMPP traffic to a queuing system simulator. In Figure 10 the loss traces simulated using the parameters shown in Table IV is shown. The simulated trace will exhibit similar statistical properties as the real trace gathered on Internet. This can be shown by de-

Loss rates observed on the loss trace simulated using the MMPP/M/1/N model 0.7

0.6

Loss rate

0.5

0.4

0.3

0.2

0.1

0

0

100

200

300

400

500

600

700

800

Fig. 10. Loss rate observed over windows of 5 sec on the loss trace simulated using MMPP model.


                             

 

TABLE V HMM PARAMETERS CALIBRATED ON THE LOSS PROCESS SIMULATED BY THE MMPP/M/1/N MODEL

by this way make the interpretation of the measurement feasible. In classical approaches, an input scenario is first setup and the performance are then derived. The use of this approach in the context of simulation is clear as it makes possible to simulate in a very easy way loss traces that have real traces characteristics. However, even if the model is able to interpret the observed losses (and is per se useful), the validity of the traffic model inferred by the methodology described in this paper remains an open question. For validating the traffic model, a coupled active and passive measurement survey is needed, that may give at the same time the end to end loss and the traffic in the bottleneck. Such a survey is under work. Some open perspectives remains. The most important is to use the proposed framework for deriving compensation methodology for the effect of measurement traffic on the network state. Active QoS measurement needs the development of methodologies that contains the measurement procedure (measurement traffic inter-arrival pdf, probe traffic rate etc.), as well as the estimation procedure and confidence level (QoS estimator, compensation procedure, etc). Some steps were made in this paper, but there is still a long way to go for this ambitious goal. Another possible extension of this work will be to integrate the analysis of the delay. In this paper we only emphasize on the loss, however delay is clearly another source of information that can be used for inferring about traffic characteristics. This subject is actually under study. R EFERENCES [1] [2]

riving the Hidden Markov Model by the estimation procedure described in [15]. The results are resumed in Table V. By comparison with values in Table III it can be seen that the two models are almost the same. The above procedure was applied on more than 36 loss traces obtained on Internet Paths between France and different sites in US and Europe with loss rates ranging between 2.5% to 22% . Similar results were got and the interpretation framework was applicable. V. C ONCLUSION In this paper a mixed constructive/descriptive approach was applied to the analysis and the interpretation of loss traces measured over the Internet. This new approach was based on inferring traffic characteristics that lead to the observed loss trace based on an associated MMPP/M/1/N single server bottleneck model. It was shown that contrary to previous works [10], the use of MMPP/M/1/N model makes possible to explain the correlation observed in the loss process by memory in the traffic process, while these models remain tractable. It was also shown how the Hidden Markov Model developed in [15] can be related to the estimation of the traffic parameters. The originality of this approach is that it proceed in inverse direction compared to classical approach. In the proposed approach, we begin with the observed performance (or QoS) measures and derive inputs that have led to these observations, and

[3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17]

removed because of blind review V. Paxson and S. Floyd, “Wide-area traffic: The failure of poisson modeling,” IEEE/ACM Trans. on Networking, vol. 3, no. 3, pp. 226–244, June 1995. V. Paxson, Measurements and Analysis of End-to-End Internet Traffic, Ph.D. thesis, UC Berkeley, February 1997. Maya Yajnik, Sue Moon, Jim Kurose, and Don Towsley, “Measurement and modelling of the temporal dependence in packet loss,” in infocom, New York, Mar. 1999. V. Paxson, G. Almes, J. Mahdavi, and M. Mathis, “Framework for IP performance metrics,” RFC-2330, May 1998. J. Andren, M. Hilding, and D. Veitch, “Understanding end-to-end internet traffic dynamics,” in Proceedings of Globecomm’98, 1998. J.C. Bolot, S. Fosse-Parisis, and D. Towsley, “Adaptive fec-based error control for internet telephony,” in Proceedings of IEEE INFOCOM, NY, March 1999, pp. 1453–1460. V. Paxson, A. Adams, and M. Mathis, “Experiences with nimi,” in Proceedings of Passive and Active Measurement: PAM-2000, 2000. H. Uijterwaal and R. Wilhem, “Ripe ncc : Test traffic project homepage available from http://www.ripe.net/test-traffic,” 1999. Sara Alouf, Philippe Nain, and Don Towsley, “Inferring network characteristics via moment-based estimators,” in infocom, Anchorage, Alaska, Apr. 2001. VINT project, “Ucb/lbnl/vint network simulator - ns (version 2), http://www.isi..edu/nsnam,” . N. Duffield and N. O’Connell, “Large deviations and overflow probabilities for the general single-server queue,” Proc. Cam. Phil. Soc., 1993. Zhen Liu, Philippe Nain, Don Towsley, and Zhi-Li Zhang, “Asymptotic behavior of a multiplexer fed by a long- range dependent process,” Tech. Rep. RR-3230. M. Yajnik, J. Kurose, and D. Towsley, “Packet loss correlation in the mbone multicast network,” in IEEE Global Internet Conf.,London,UK, 1996. removed because of blind review B. Melamed and D. Yao, The ASTA Property, chapter 7, CRC Press, 1995. Sandrine Vaton, “Fractal versus markov models of traffic and near completely decomposable markov models of traffic,” in ATM & IP workshop, Ilkley, UK, 2000.

[18] S. Robert and J. Le Boudec, “New models for self-similar traffic.,” Performance Evaluation, vol. 30, no. 1-2, July 1997. [19] W. Steward, Introduction to the Numerical Solution of Markov Chains, Princeton University Press. [20] P. R. Kumar and P. Varaiya, Stochastic Systems: Estimation, Identification, and Adaptive Control, Prentice-Hall, Englewood Cliffs, N.J., 1986. [21] Leonard Kleinrock, Queueing Systems — Theory, vol. 1, WileyInterscience, New York, New York, 1975. [22] Constantinos Dovrolis, Parmesh Ramanathan, and David Moore, “What do packet dispersion techniques measure?,” in infocom, Anchorage, Alaska, Apr. 2001. [23] Constantinos Dovrolis, “Pathrate,” can be downloaded from http://www.cis.udel.edu/ dovrolis/bwmeter.html, 2001. [24] M. Marcus and H. Ming, A survey of matrix theory and matrix inequalities, Allyn and Bacon, Inc., Boston, 1964.

A PPENDIX Let us analyze the transition matrix of a M/M/1/N model with an infinitesimal generator . It is well know [21] that matrix  for a M/M/1/N queue has the following structure :







   
   











   ..  .



 

    

 
  defined

As stated in section III-C.5, the matrix as:  is the transition matrix within a time  associated with any infinitesimal generator . The matrix 
  will converge exponentially fast toward the stationary transition matrix (
) which is a matrix having the stationary state distribution  in all its rows, where  is given by:  . The speed of convergence of 
  will be governed by the second largest eigen-value   . Matrix theory [24] shows that the second largest eigen-value of the matrix  of an M/M/1/N queue will be lower bounded by:


 

  "



 

meaning that , which is the time needed for the queue to flush, is the time scale for the M/M/1/N queue to reach its stationary state. The previous analysis on transition matrix will help on deriving the autocorrelation function (#
 ) of the loss process. #
  is defined by :

#
 



 $



    $



where

  means that a
packet arriving at time  will be lost and  

  is the loss (or queue overflow) probability. This value can be easily derived from matrix 
  as : #
  
    . Now, we have 
 , meaning that:

#
   

exponentially fast with a time scale around  . Therefore if the  active measurement probes are sent with an interval larger than the the time scale, the loss process measured will be memoryless and uniform.