Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1998-05-07
2002-02-12
Patel, Ajit (Department: 2661)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S235000
Reexamination Certificate
active
06347077
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to a method for measuring traffic in a communication system, the method comprising the steps of directing information corresponding to traffic units to be forwarded, such as cells, to a number of parallel traffic gapping gates (G
1
, . . . , G
n
) which make a gap or pass decision on individual traffic units, and estimating the distribution concerning frequency of occurrence of the traffic units by simultaneously calculating the estimates of the relative frequency of occurrence on several value ranges. The solution according to the invention is particularly intended for measuring cell traffic in an ATM network, but it is applicable in connection with other kind of traffic as well, for example in calls, as will be disclosed below. Due to the many operational environments, the cells, packets, calls etc entities transferred in the system will below be referred to with a general term “traffic unit”.
BACKGROUND OF THE INVENTION
The call control methods based on traffic measurements are based on the fact that it is difficult for a user to describe accurately the nature of the traffic in advance. For example, the average bit rate of a compressed video signal is very difficult to determine in advance. In fact, the user may have to give the traffic parameters (such as cell maximum rate and cell average rate) values higher than actual, because the exact characteristics of the traffic are unknown prior to establishing a connection. Consequently, the connection is allocated more resources than needed in the network, possibly resulting in a lower degree of utilization in the network. The inaccurate description given by the user is compensated for by carrying out measurements from actual traffic. By means of these measurements, the utilization degree of the network resources can be improved. In fact, the most efficient traffic control methods are based on measurements performed from actual traffic.
An efficient method of studying traffic is to measure a so-called histogram information from the traffic. The efficiency is a result of the histogram containing a lot of information on the traffic stream. In order to facilitate understanding the description below, these histograms are first briefly discussed.
A histogram refers to a bar chart illustrating the frequency distribution of a quantity, in which the width of the bar represents a specific value range and the height of the bar represents the frequency of the values within the value range in question. Thus, a histogram illustrates how the values of a specific quantity are distributed among all possible values. If the quantity is a random variable r (which may represent e.g. the frequency of occurrence of incoming cells at the input of a device, or the rate of incoming calls on a specific trunk line), the histogram is an estimate of r's probability density function f.
FIG. 1
shows a histogram in which the height (0.1) of the first bar is an estimate of the subsequent value of the random variable to be between zero and five, the height (0.2) of the next bar is an estimate of the subsequent value of the random variable to be between five and ten, etc. By computing a sum of heights up to the bar whose x coordinate is greater than X, an estimate of r's probability distribution function F will be obtained at the point r=X. For example, the sum of the two leftmost bars (0.1+0.2=0.3) is an estimate of the subsequent value of the random variable to be lower than or equal to ten.
For a discrete random variable, the probability density function f and the probability distribution function F are determined as follows:
f
(
X
)
=
P
{
any
r
i
=
X
}
,
i
=
0
,
1
,
2
,
…
F
(
X
)
=
P
{
any
r
i
≤
X
}
=
∑
r
i
≤
X
f
(
r
i
)
If the functions f and F are known, then we know almost everything there is to know about the behaviour of the random variable. In practice, however, this is impossible because in such a case-we would need to know not only the previous values of the random variable sequence but also its future values. However, this is not possible because the traffic originates from an external source which is independent of the measuring device and whose behaviour cannot be known in advance. In addition, the functions f and F may be functions of time (that is, they may vary with time).
In the method according to the present invention, traffic distribution is estimated by gathering information corresponding to a histogram from either all or just some of the previous values of the random variable. (It should be noted that a histogram is usually understood to refer to a graphic representation. For this reason, reference in connection with the present invention is usually made to information corresponding to a histogram because the measuring information gathered does not have to be in a graphic form.) In the description below, the letter h denotes an (empirical) estimate of the probability density function f and the letter H denotes an (empirical) estimate of the probability distribution function F, i.e. h≈f and H≈F.
Calculating the histogram information of the frequency of occurrence (i.e. arrival rate) for the traffic units forms the basis of various traffic analyses, therefore also establishing the core of many different implementations. Examples of such implementations utilizing traffic measurements are Connection Admission Control and bandwidth allocation in fast packet networks, particularly in the ATM networks. Traffic measurements may also be carried out in order for a specific transfer device or a part thereof to be optimized for precisely a specific type of traffic. For example, buffer size should be big enough to buffer most of the incoming traffic.
FIG. 2
illustrates a typical solution which can be used to measure the estimate h of the probability density function f. Measured traffic or corresponding information (e.g. a pulse sequence in which every pulse corresponds to an incoming traffic unit) is fed to a sorting device SD which calculates a momentary arrival rate r. This is obtained by taking an inverse value of the difference between time t
1
(i.e. the current time) of the arriving traffic unit and time t
2
of the preceding traffic unit, i.e. r=1/(t
1
−t
2
). This value is calculated at every arriving traffic unit. (If the calculation does not utilize an inverse value but the difference t
1
−t
2
, the distribution of time between successive traffic units is estimated instead of the distribution of arrival rate.) The actual calculation is carried out by means of counters C
1
, . . . , C
n
, of which there is one per each histogram bar, i.e. one per each “frequency band”. For example, to evaluate the information of
FIG. 1
, eight counters are required (the first between zero and five, the second between five and ten, etc, and the last counter between thirty-five and infinity.) Having found out the instantaneous arrival rate, the sorting device SD must decide on which histogram bar x-axis range the result belongs. For this purpose, it has, stored in its memory (denoted by reference mark MEM), information on which x-axis range matches which counter C
1
, . . . , C
n
. Thus, the sorting device compares the result it calculated to the information stored in the memory, and following this increments the counter which matches the “frequency band” on which the result belongs. In this manner, the calculation results of the counters provide the estimate h of the probability density function. At the beginning of the measurement, the counters were zeroed. Following the measurement, the counter values will be stored and the counters zeroed, after which the next measurement may follow.
The way described above will provide an instantaneous pattern or instantaneous distribution of the traffic. However, momentary minor fluctuations are usually of no interest, but instead we would like to evaluate a long-term behaviour of the traffic, because s
Altera Law Group LLC
Nokia Telecommunications Oy
Patel Ajit
Phunkulh Bob A.
LandOfFree
Traffic measurement in a communication system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Traffic measurement in a communication system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Traffic measurement in a communication system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2979812