JPH1188357A - Cell buffer device - Google Patents

Abstract

(57) [Summary] [Problem] FCFD method and LCFD as cell discarding method
Depending on the traffic situation, these methods may discard valid cells without discarding invalid cells. SOLUTION: A delay time of a head cell of a low priority class is recognized, and the delay time is compared with a threshold to determine whether the head cell is a valid cell or an invalid cell. If the first cell is not discarded, the last cell is discarded.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

The present invention relates to an ATM (Asynchronou).
s Transfer Mode). BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an apparatus for temporarily storing cells in an ATM switching apparatus to avoid cell collision.

[0002]

2. Description of the Related Art An information transmission system in a wideband ISDN is called an ATM. This ATM divides a wide variety of information into short fixed-length blocks with headers called "cells" and multiplexes these blocks for transmission. The advantages of conventional circuit switching and packet switching are obtained. It can be held together and can transmit at a very high speed, and can be applied to the transmission of moving images.

[0003] For such cell exchange in ATM communication, an ATM exchange device for exchanging fixed-length cells at high speed by hardware using a simplified protocol is used. The switch used in the ATM switching apparatus, that is, the ATM switch essentially eliminates the possibility of cell collision, that is, the possibility that a plurality of cells arriving from different incoming lines require a connection to the same outgoing line at the same time. Have.

[0004] When such a cell collision occurs, cells are temporarily stored in a cell buffer provided inside the switching device, thereby avoiding cell discarding and suppressing the cell discarding rate in the switching device. It is necessary. FIG. 6 shows A
FIG. 3 is a diagram illustrating a relationship between a TM switching device and a cell buffer device. As shown in FIG. 6, the cell buffer device 20 is an ATM.
The contention control device 30 is provided on the output side of the exchange device 50.
The cell is output to the outgoing line so that the cells do not collide with each other according to the control of.

When cells having different required qualities are mixed, the quality is controlled by a cell buffer device. In order to efficiently use the resources of the ATM network, there is a push-out method as a means for providing a low priority class (best effort) that allows a certain degree of deterioration of the cell loss rate and the delay quality.

In the push-out method, a service class according to the priority of cell transfer is divided into two classes, a high-priority class and a low-priority class, and a high-priority class cell is written into one buffer with priority. Reading is performed. The cells of the low priority class are stored only when there is a free space in the buffer, and the reading is performed only when there is no cell of the high priority class. When the buffer is full, cells of the high priority class are pushed out and cells of the low priority class are discarded to accumulate cells of the high priority class in the buffer.

[0007] In the push-out method, an FCFD (First Come Firs) for discarding the cell of the oldest low priority class.
t Drop) method and LCFD (Last Come First Drop) method for discarding the cell of the newest lower priority class. FIG.
And FIG. 8 are conceptual diagrams of the FCFD method and the LCFD method, respectively.

FIG. 9 shows a block configuration of a conventional cell buffer device for performing push-out. The conventional cell buffer device 20 includes a priority class identification unit 1, a buffer write management unit 2, a buffer read management unit 3, and a buffer 4. FIG. 10 is a block diagram of the conventional buffer write management unit 2. The buffer write management unit 2 includes a cell write unit 5,
It comprises a high priority class address management unit 7 and a low priority class address management unit 6. FIG. 11 is a block diagram of the conventional buffer read management unit 3. As shown in FIG. The buffer read management unit 3 includes a cell read unit 8 and an address management unit 9.

[0009] Among the conventional push-out methods, FCFD
The writing algorithm of the method will be described with reference to FIG. FIG. 12 is a flowchart showing a writing algorithm of the conventional FCFD method. When a new cell arrives at the buffer 4 (S0), the priority class identification unit 1 identifies the priority class of the cell (S1). For the identification of the priority class, for example, a priority class identifier in a cell header is referred to, or a VCI / VPI number is referred to. If the cell is in the low priority class, the buffer write management unit 2 checks whether or not the buffer 4 has a free space (S2).
If there is a vacancy, the cell is stored in the last memory of the low priority class (S3). When storing the low priority class, the low priority class address management unit 6 manages the address. If there is no free space in the buffer 4, the cell is discarded (S4).

If the new cell is a high-priority cell (S1), the buffer write management unit 2
It is checked whether there is an empty space (S5). If there is a vacancy, the cell is stored in the last memory of the high priority class (S6). The first cell of the low-priority class is attached after the last cell of the stored high-priority class (S
7). That is, the address next to the address where the last cell of the high priority class is stored is set as the address of the first cell of the low priority class. This recombination of addresses is performed by the high-priority class address management unit 7 and the low-priority address management unit 6. If there is no free space in the buffer 4, it is checked whether cells of the low priority class are stored (S4).
8). If the cell of the low priority class is not stored, the new cell is discarded (S9). If a low-priority class cell is stored, the first cell of the low-priority class is discarded (S10), and a new cell is stored in the last memory of the high-priority class (S11). Further, the first cell of the low priority class is attached after the last cell of the stored high priority class (S12).

FIG. 13 is a flowchart showing an algorithm of a conventional push-out readout operation. At the read timing (S20), if a cell of the high priority class is stored (S21), the first cell of the high priority class is read (S22). If no high-priority class cell is stored and a low-priority class cell is stored (S23), the first cell of the low-priority class is read (S23).
24). If neither the high-priority class nor the low-priority class cell is stored, an empty cell is transmitted (S2).
5).

[0012] Among the conventional push-out methods, LCFD
The writing algorithm of the method will be described with reference to FIG. FIG. 14 is a flowchart showing a conventional LCFD writing algorithm. The difference from the FCFD scheme is that when the cell of the high priority class pushes out the cell of the low priority class, the LCFD scheme pushes out the last cell of the low priority class (S1).
0 '). Other operations are the same as those of the writing algorithm of the conventional FCFD system shown in FIG.

As described above, in order to use the resources of the ATM communication network efficiently, when the buffer 4 runs out of space, a push to discard cells of a low priority class that allows a certain degree of cell loss rate and deterioration of delay quality is performed. The out method can improve the buffer use efficiency and the transmission link use efficiency.

References (Oki, Yamanaka, Shimura, "Performance evaluation of push-out cell discarding method in ATM network", IEICE, Society Conference, B-6-43, 199
(July 1995) evaluated the delay time characteristics of the low priority class in the FCFD system and the LCFD system by simulation. The input traffic of the high-priority class and the low-priority class is Poisson arrival, and the buffer length is 128. FIG. 15 shows the average delay time and the maximum delay time (99.9% value) of the cells of the low priority class when the traffic load of the high priority class is fixed (0.5) and the load of the low priority class is changed. FIG. The horizontal axis indicates the load of the low priority class, and the vertical axis indicates the delay time.

Here, the delay time is defined as the time from the time when the cell is input to the buffer to the time when the cell is read from the buffer. However, low-priority cells that have been input to the buffer and then discarded are retransmitted from the transmission source, and the same cells are input to the buffer again. The time from the time of input to the buffer to the time when this cell is finally read from the buffer is set.

As shown in FIG. 15, as the load of the low priority class increases, the cells of the low priority class are pushed out by the cells of the high priority class, and the delay time increases.
This indicates that the load of the low-priority class increases and the cell loss rate of the low-priority class increases. However, there is no difference in the cell loss rate depending on the cell discarding method.

In FIG. 15, the average delay time is almost the same in both cell discarding systems.
On the other hand, the maximum delay time has the same value when the input load is small, but when the congestion state occurs, the FCFD scheme rises sharply, and the LCFD scheme has a shorter maximum delay time than the FCFD scheme. This is because the low-priority class cells are discarded in bursts, and the variance of the delay distribution is increased.

As described above, among the two push-out schemes, it has been reported that the LCFD scheme is better in terms of the characteristic of the maximum delay time of the low-priority class cell.

[0019]

However, there is a case where a delay of a certain time _Tmax or more cannot be tolerated even in a cell of a low priority class. That is, when the cell of the low priority class reaches _Tmax , it may become invalid as information.

[0020] Here, invalid cell cell delay time is T _max above, the delay time is defined as the effective cell T _max smaller cells, the use of LCFD method, the first cell of the low priority class is already Despite being an invalid cell, the last cell of the low priority class may be discarded. In this way, without discarding invalid information,
Valid information may be discarded.

Therefore, in the conventional cell buffer device using the push-out method, even if the state of the cell in the buffer changes, only one of the push-out methods is employed. Delay time)
, The possibility of transferring invalid cells is high, and the delay quality may be degraded.

The present invention has been made in view of such a background, and has as its object to provide a cell buffer device capable of transferring low priority class cells having good delay quality. An object of the present invention is to provide a cell buffer device that can select an optimal push-out method according to a traffic situation that changes every moment.

[0023]

A feature of the present invention is to recognize a delay time of a head cell of a low priority class stored in a buffer, and to use the FCFD method and the LCF according to the delay time.
The most important feature is to select the D method.

That is, the present invention relates to a cell buffer device, a buffer for temporarily storing an incoming cell, a unit for writing a cell to the buffer, a unit for reading a cell from the buffer, and a service for the incoming cell. Means for identifying a class, wherein the means for writing includes means for discarding low priority class cells accumulated in the buffer when a new high priority class cell arrives with no free space in the buffer. This is a cell buffer device.

Here, the feature of the present invention is characterized in that it comprises means for recognizing the delay time of the first cell of the low priority class stored in the buffer, and the discarding means comprises means for recognizing the recognized delay time. When the threshold value is exceeded, the first cell is discarded, and when the delay time does not exceed the threshold value, means for discarding the last cell of the low priority class is included.

Means for adding storage time information to the low-priority class cells stored in the buffer, wherein the recognizing means subtracts the storage time information from the current time to obtain the current value of the first cell in the buffer. It may be configured to include a means for calculating the residence time until the time.

That is, at the entrance of the buffer, the time information at that time is added to the low-priority class cell as accumulation time information. When this cell eventually becomes the head cell of the low-priority class, the accumulation information added at the entrance is added. By extracting the time information and subtracting it from the current time, the residence time of this cell in the buffer can be calculated. The dwell time is compared with a threshold value set from the maximum allowable delay time of the cell. If the dwell time exceeds the threshold value, the cell is already an invalid cell ( Alternatively, the cell becomes an invalid cell at the expected read time.
Select a method. If the staying time of this cell has not yet exceeded the threshold value, it is determined that the first cell is still a valid cell, and the LCFD method of discarding from the last cell of the low priority class is selected.

Alternatively, the recognizing means may further add, to the calculated dwell time, a read completion time of the high-priority class cells stored in the buffer, and read the head cell from the buffer. A configuration including means for estimating the time may also be employed.

That is, in addition to simply calculating the residence time of the head cell of the low-priority class in the buffer, the time until the next reading is estimated. As a result, it is possible to avoid that the top cell of the low-priority class, which was a valid cell when the push-out method was selected, becomes an invalid cell when the read-out method is actually read out. A choice of method can be made.

[0030]

Embodiments of the present invention will be described with reference to FIG. FIG. 1 is a block diagram of a cell buffer device common to the first and second embodiments of the present invention. FIG. 2 is a block diagram of the buffer write manager 2 according to the first embodiment of the present invention. FIG. 4 is a block diagram of the buffer write manager 2 according to the second embodiment of the present invention.

The present invention relates to a cell buffer device 20,
A buffer 4 for temporarily storing incoming cells, and a buffer write management unit 2 as a means for writing cells into the buffer 4.
A buffer read management unit 3 for reading cells from the buffer 4; and a priority class identification unit 1 for identifying a service class of an incoming cell. 4 is a cell buffer device 20 including a cell writing unit 5 provided with means for discarding low-priority class cells stored in the buffer 4 when a new high-priority class cell arrives.

Here, the feature of the present invention is that a means for recognizing the delay time of the first cell of the low priority class stored in the buffer 4 is provided.
When the recognized delay time exceeds the threshold, the first cell is discarded, and when the delay time does not exceed the threshold, the last cell of the low priority class is discarded.

A counter value writing unit 10 for adding storage time information to low priority class cells stored in the buffer 4 is provided. In the first embodiment of the present invention, the recognizing unit is as shown in FIG. As shown in the figure, the accumulation time information is subtracted from the current time indicated by the counter 11 and the residence time calculation unit 13 is a means for calculating the residence time of the first cell in the buffer 4 up to the current time.

In the second embodiment of the present invention, as shown in FIG. 4, the recognizing means includes, in addition to the residence time calculation unit 13 and the residence time calculated by the residence time calculation unit 13, And a delay time estimating unit 14 for estimating the scheduled read time of the first cell from the buffer 4 by adding the scheduled read completion time of the high-priority class cell stored in the buffer. The buffer read management unit 3
Are common to those of the conventional example shown in FIG.

[0035]

【Example】

(First embodiment) Cell buffer device 2 of the first embodiment of the present invention
FIG. 3 is a flowchart showing a push-out method writing algorithm at 0. When a new cell arrives at the buffer (S0), the priority class identification unit 1 identifies the priority class of the cell (S1). For the identification of the priority class, for example, a priority class identifier in a cell header is referred to, or a VCI / VPI number is referred to. If the cell is in the low priority class, the buffer write management unit 2 checks whether or not the buffer 4 has a free space (S2). If there is a space, the counter value writing unit 10 writes the value of the counter into the header of the cell (S31). For example,
The counter is incremented by one every 2G cell time. The cell in which the counter value has been written is stored in the last memory of the low priority class (S3). When storing the low priority class, the low priority class address management unit 6 manages the address. If there is no free space in the buffer 4, the cell is discarded (S4).

If the new cell is a high-priority class cell (S1), the buffer write manager 2 checks whether or not there is a free space in the buffer 4 (S5). If there is a vacancy, the cell is stored in the last memory of the high priority class (S6). The first cell of the low priority class is attached after the last cell of the stored high priority class (S7).
That is, the address next to the address where the last cell of the high priority class is stored is set as the address of the first cell of the low priority class. This recombination of addresses is performed by the high-priority class address management unit 7 and the low-priority class address management unit 6. If there is no free space in the buffer 4, it is checked whether cells of the low priority class are stored (S4).
8). If the cell of the low priority class is not stored, the new cell is discarded (S9).

If cells of the low priority class are stored, either the first cell or the last cell of the low priority class is discarded. Which cell is to be discarded is determined as follows.

The delay time threshold value memory 12 sets a threshold value of the residence time in advance, and stores the information of the counter value and the current counter value written in the header of the first cell of the low priority class. Based on this, the residence time of the cell is calculated by the residence time calculator 13. If the calculated residence time is greater than the residence time threshold (S30), the first cell in the low priority class is discarded (S10). If the calculated residence time is equal to or less than the residence time threshold, the last cell of the low priority class is discarded (S10 '). After discarding the low priority class cell, a new cell is stored in the last memory of the high priority class (S11). Further, the first cell of the low priority class is attached after the last cell of the stored high priority class (S12). The reading algorithm in the cell buffer device 20 is common to the conventional example.

(Second Embodiment) In the first embodiment of the present invention, the residence time of the first cell of the low priority class in the buffer 4 up to the current time is compared with a predetermined threshold value, and It has been determined whether to discard the first cell of the priority class or the last cell of the low priority class.

In the second embodiment of the present invention, the low-priority class head cell is determined not on the basis of the residence time in the buffer 4 until the current time but on the basis of the residence time and the queue length information of the high-priority class. By comparing the delay time from when the cell of the priority class is input to the buffer 4 to when the cell is read out with a predetermined threshold value of the delay time, the first cell of the low priority class is discarded or the low priority class is discarded. The difference lies in whether to discard the last cell of the class.

In FIG. 4, the queue length of the high priority class is measured by the high priority class address management unit 7. The delay time d in the buffer 4 of the first cell of the low priority class is obtained by the sum of the dwell time d _{1 up} to the present and the dwell time d ₂ from the present to the time of reading. That is, d = d ₁ + d ₂ (qh) (1). Since the second term on the right side is a function of the queue length of the high-priority class, the queue length of the high-priority class is qh, and the estimated value of the residence time from the present to the time of reading is d ₂
(Qh). In general, when qh is large, d
There is a high probability that ₂ (qh) will increase. For example, d
As ₂ (qh) is proportional to qh, it is possible to estimate the d ₂ (qh) by a _{d 2 (qh) = C *} qh ... (2). Here, C is a constant.

The cell buffer device 20 according to the second embodiment of the present invention
FIG. 5 is a flowchart showing a write-out algorithm of the push-out method in FIG. The estimated delay time d of the head cell of the low priority class is stored in the delay time threshold memory 15.
Is compared with a preset delay time threshold.
If d is greater than the delay time threshold (S32), the first cell of the low priority class is discarded (S10). If d is equal to or less than the delay time threshold, the last cell of the low priority class is discarded (S10 '). Others are the same as the algorithm of the first embodiment of the present invention shown in FIG.

[0043]

As described above, according to the present invention,
Since the push-out method is selected according to the state of the cells in the buffer (delay time), the possibility of transferring invalid cells is small, and the delay quality can be improved. That is, it is possible to select an optimal push-out method according to the traffic situation that changes every moment.

[Brief description of the drawings]

FIG. 1 is a block diagram of a cell buffer device common to first and second embodiments of the present invention.

FIG. 2 is a block diagram of a buffer write management unit according to the first embodiment of the present invention.

FIG. 3 is a flowchart illustrating a write algorithm of a push-out method in the cell buffer device according to the first embodiment of the present invention.

FIG. 4 is a block diagram of a buffer write management unit according to a second embodiment of the present invention.

FIG. 5 is a flowchart showing a push-out type writing algorithm in the cell buffer device according to the second embodiment of the present invention.

FIG. 6 is a diagram showing a relationship between an ATM switching device and a cell buffer device.

FIG. 7 is a conceptual diagram of the FCFD method.

FIG. 8 is a conceptual diagram of the LCFD system.

FIG. 9 is a block diagram of a conventional cell buffer device that performs push-out.

FIG. 10 is a block diagram of a conventional buffer write management unit.

FIG. 11 is a block diagram of a conventional buffer read management unit.

FIG. 12 is a flowchart showing a writing algorithm of the conventional FCFD method.

FIG. 13 is a flowchart showing an algorithm of a conventional push-out read operation.

FIG. 14 is a flowchart showing a conventional LCFD writing algorithm.

FIG. 15 shows that the traffic load of the high priority class is constant,
The figure which shows the average delay time and the maximum delay time of the cell of a low priority class when the load of a low priority class is changed.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 Priority class identification part 2 Buffer writing management part 3 Buffer reading management part 4 Buffer 5 Cell writing part 6 Low priority class address management part 7 High priority class address management part 8 Cell reading part 9 Address management part 10 Counter value writing Unit 11 Counter 12 Residence time threshold memory 13 Residence time calculation unit 14 Delay time estimation unit 15 Delay time threshold memory 20 Cell buffer device 30 Contention control device 50 ATM switching device

Claims (3)

[Claims] 1. A buffer for temporarily storing an incoming cell, means for writing a cell to the buffer, means for reading a cell from the buffer, and means for identifying a service class of the incoming cell, The writing means is a cell buffer device including a means for discarding low priority class cells accumulated in the buffer when a new high priority class cell arrives without empty space in the buffer, Means for recognizing the delay time of the accumulated head cell of the low priority class, wherein the discarding means discards the head cell when the recognized delay time exceeds the threshold value and increases the delay time. A cell buffer device comprising means for discarding the last cell of a low priority class when the threshold value is not exceeded. 2. A device for adding storage time information to low priority class cells stored in the buffer, wherein the recognizing unit subtracts the storage time information from a current time and stores the information in the buffer of the head cell. 2. The cell buffer device according to claim 1, further comprising means for calculating a residence time up to the current time. 3. The recognizing means further adds, to the calculated dwell time, a read completion time of a high-priority class cell stored in the buffer, and reads the head cell from the buffer. 3. The cell buffer device according to claim 2, further comprising means for estimating a time.