Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1998-08-18
2001-12-04
Yao, Kwang B. (Department: 2664)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S253000
Reexamination Certificate
active
06327247
ABSTRACT:
The present invention relates to a method to characterize cell traffic of a connection as defined in the preamble of claim 1, and a device adapted to perform this method, as defined in the preamble of claim 2.
Such a method and device are already known in the art, e.g. from the article ‘Fundamental Limits and Tradeoffs of Providing Deterministic Guarantees to VBR Video Traffic’, from the authors Edward W. Knightly, Dalls E. Wrege, Jörg Liebeherr and Hu! Zhang. In paragraph 3.1 thereof, measuring an empirical envelope &egr;, which represents the maximum number of cell arrivals within a time interval as a function of the length of this time interval, is proposed to characterize video traffic. The empirical envelope &egr; is expressed mathematically by the formula (2) on page 102 of the cited article. As is indicated in paragraph 3.2 on page 103, line 6-8, this empirical envelope can be measured by means of leaky buckets.
When the cell traffic in a connection is characterized by the known empirical envelope, the parameters needed for policing the traffic by means of the Generic Cell Rate Algorithm (GCRA) cannot be derived in a simple way. The known technique for cell traffic characterization thus is not optimally suited to determine the GCRA parameters.
An object of the present invention is to provide a method and device to characterize cell traffic of the above known type, but which produce a cell traffic characteristic that is more suitable for determination of the GCRA parameters.
According to the present invention, this object is achieved by the method defined in claim 1 and the device defined in claim 2.
Indeed, by Legendre transforming the known empirical envelope, a cell traffic characterization curve is obtained which represents cell rate in the monitored connection as a function of tolerance on the arrival time of cells of the monitored connection. From this cell traffic characterization curve, the minimum cell rate to be used by the Generic Cell Rate Algorithm for policing the traffic can be read off for each value of the tolerance. On the other hand, this cell traffic characterizing curve allows to read off the maximum tolerance allowable for a source which transmits at a certain cell rate, and which is policed by the GCRA algorithm.
An additional advantage of the method according to the present invention is that the accumulation of data is separated from the representation thereof in the form of a cell traffic characterizing curve. A consequence of this independent nature of data accumulation and data representation is that the representation parameters such as the accuracy and range can be modified without any effect on the data accumulation phase. In the known method, any change in accuracy or range implies a complete new measurement of the empirical envelope.
It is to be noticed that the term ‘comprising’, used in the claims, should not be interpreted as being limitative to the means listed thereafter. Thus, the scope of the expression ‘a device comprising means A and B’ should not be limited to devices consisting only of components A and B. It means that with respect to the present invention, the only relevant components of the device are A and B.
Similarly, it is to be noted that the term ‘coupled’, also used in the claims, should not be interpreted as being limitative to direct connections only. Thus, the scope of the expression ‘a device A coupled to a device B’ should not be limited to devices or systems wherein an output of device A is directly connected to an input of device B. It means that there exists a path between an output of A and an input of B which may be a path including other devices or means.
An additional feature of the device according to the present invention is defined in claim 3.
In this way, the empirical envelope becomes real-time measurable without the use of complex hardware resources like the parallel leaky bucket structure proposed in the above cited article. Indeed, as is indicated in paragraph 3.2 of the article written by E. W. Knightly et al., measuring N points of the empirical envelope to constitute therefrom a piece-wise linear approximation of the empirical envelope requires a parallel structure of N leaky buckets. The hardware complexity hence is linearly proportional to the number of points measured when using the known technique. This parallelism in hardware resources is avoided according to the present invention.
It is noticed that the two cells of the connection in between which the interarrival time is measured are not necessarily subsequent cells of that connection. If however the two cells are no subsequent cells of the connection, their interarrival distance can always be calculated from interarrival distances between subsequent cells of the connection. This means that measuring interarrival times between subsequent cells suffices to be able to determine the interarrival time in between any arbitrary pair of cells of the monitored connection. More details with respect hereto are given later.
Another additional feature of the present device is defined in claim 4.
The interarrival time between the two non-idle cells, i.e. the two cells which belong to the connection that is monitored, is thus determined as an integer amount of idle or non-idle cells received during that interarrival time. This is so because each cell transmission time corresponds to the receipt of either an idle or a non-idle cell.
Also an additional feature of the present invention is defined in claim 5.
As already indicated above, the interarrival time determination means has to measure the interarrival time only for subsequent non-idle cells. All other interarrival times between cells of the monitored connection can then be calculated from the measured interarrival times by simply adding them together.
Yet another additional feature of the present device is claimed in claim 6.
Indeed, the lowest cell rate for which the cell traffic characterizing curve has to be determined, defines the maximum interarrival distance that can be measured between two subsequent cells of the connection and thus also the word length to be foreseen for the counter means. A concrete example illustrating the choice of the word length of the counter means will be given later.
It is further remarked that the counter should be implemented so that it does not overflow in absence of non-idle cells. In the latter situation, the counter has to stop at its maximum value.
A further feature of the present invention is defined by claim 7.
Thus, the length of the time interval determines the memory locations that will be accessed, and the data stored at the addressed memory locations represent the maximum number of cells of that connection received during a time interval of that length.
It is noticed that the maximum number of cells of the connection received during a time interval with a certain length is also the maximum number of cells received during any time interval with a greater length, provided that there was no other time interval of this greater length during which more cells were received. Thus, the counted maximum number of cells will be memorized on several subsequent memory locations.
Another further feature of the present invention is defined in claim 8.
In this way, data accumulation and storage in the memory means can overlap in time with data representation of the previous measurements. Alternatively, if data accumulation takes too much time, overlap in time between data accumulation and data representation can be realised by executing the Legendre transformation repeatedly on partial results of an ongoing measurement.
Also a further feature of the present device is described in claim 9.
In this way, by temporarily storing and processing information, the number of memory accesses can be reduced significantly as will be shown later. Optimizing this number of memory accesses by intelligently pre-processing the information is important for real-time cell traffic characterization of the connection.
Moreover, a further feature of the present device is defined in claim
Alcatel
Yao Kwang B.
LandOfFree
Method and device to characterize cell traffic does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and device to characterize cell traffic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and device to characterize cell traffic will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2588710