JP3051101B2 - Cell buffer device and selective ATM cell discarding method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

The present invention relates to an ATM (Asynchronou).
s Transfer Mode). The present invention relates to a technique for selectively discarding cells in packet units when the network is congested when a packet is divided into a plurality of cells (transformed into cells) and transferred using an ATM network.

[0002]

2. Description of the Related Art UBR (Unspecified Bit Rate) handling computer communication represented by communication between LANs in an ATM network.
In the service, network resources are not secured when information is transferred. Therefore, when the amount of information to be transferred increases, the network becomes congested and cell loss occurs. Packets in which some of the cells constituting the packet have been lost are discarded even if they arrive at the receiving end because the original packet cannot be restored.

[0003] In a congested state, since such situations occur many times, the effective utilization rate of the network is reduced. Therefore, as a method of solving such a problem, an EPD (Early Packet Dispatch) in which cells are selectively discarded on a packet basis.
card) control is proposed.

In EPD control, it is necessary to identify a packet at a cell level. Therefore, first, a method of identifying a packet at a cell level will be described. In the AAL type 5, the AUU (ATM lay) of a cell constituting a packet is used.
er User to User) parameter is set to “1”, and AUUs of other cells are set to “0”. Therefore, it is possible to identify that the cells from the cell next to the cell whose AUU is “1” to the cell whose next AUU is “1” are cells constituting the same packet.

In EPD control, when the first cell constituting a packet arrives, if the queue length of a buffer for temporarily storing the arriving cell is equal to or larger than a predetermined threshold TH, the same packet as the arriving cell is constituted. All cells are discarded, and if less than TH, all cells making up the same packet as the arriving cell are input to the buffer.

[0006] By performing the EPD control, the effective utilization rate of the network is improved, but the fairness that the network resources are equally distributed among the connections sharing the same network resources is guaranteed. I can't.

In view of this, Per-VC EPD control has been proposed which determines whether a packet should be input to a buffer or discarded, taking into account the number of cells of each connection existing in the buffer (H. Li et. al., "Performance of TCP
over UBR Service in ATM Networks with Per-VC Ealy
Packet Discard Schemes ", IPCCC'96).

The Per-VC EPD control will be described with reference to FIG. FIG. 9 is a diagram for explaining Per-VC EPD control. Per-VC EP shown in FIG.
In the D control, when the head cell constituting the packet of the connection i arrives, the queue length is equal to or more than a predetermined threshold TH, and the number of cells of the connection i present in the buffer is equal to the threshold TH or the queue length. If the value is greater than the value obtained by dividing the number of connections having even one cell in the buffer, all cells constituting the same packet as the arriving cell are discarded, otherwise, all cells constituting the same packet as the arriving cell Into the buffer.

[0009] For example, in FIG.
Suppose that the first cell (denoted as BOM) that constitutes the packet has arrived. Although the queue length (= 4) is equal to or greater than the threshold value TH (= 3), the number of cells of the connection 1 existing in the buffer is “0” and the threshold value TH (= 3) or the queue length (=
4) The number of connections having even one cell in the buffer (=
Since the value is smaller than the value (= 1.5 or 2) divided by two of the connections 2 and 3, all the cells constituting the same packet as the arriving cell are input to the buffer.

[0010]

In such a conventional technique, the number of cells of each connection currently existing in the buffer is used for determination. Therefore, the number of cells of each connection input to the buffer in the past is not used.

As described above, in order to use the number of cells of each connection currently existing in the buffer, it is necessary to manage the number of cells input to and output from the buffer for each connection. This is extremely difficult as compared with the case where only the number of cells input to the buffer is managed, and is a major obstacle in implementing the method shown in the conventional example.

The present invention has been made in such a background, and it is an object of the present invention to selectively discard cells in packet units while guaranteeing fairness between connections using common network resources. Cell buffer device and selective A
An object of the present invention is to provide a method for discarding a TM cell. SUMMARY OF THE INVENTION It is an object of the present invention to provide a cell buffer device and a selective ATM cell discarding method capable of executing a cell acceptance judgment only by managing cells input to a buffer. An object of the present invention is to provide a cell buffer device and a selective ATM cell discarding method capable of distributing network resources to each connection at a preset ratio.

[0013]

SUMMARY OF THE INVENTION The present invention utilizes information on the number of cells of each connection previously input to a buffer, and when the first cell constituting a packet arrives,
It is characterized in that all cells constituting the same packet as the cells constituting the arrived packet are inputted to the buffer or discarded.

The conventional technique is different from the prior art in that it uses the information on the number of cells of each connection input to the past buffer to determine whether to accept a packet, and there is no need to manage the number of cells output from the buffer. The only difference is that only the number of cells input to.

That is, a first aspect of the present invention is a cell buffer device, which comprises a buffer for temporarily storing arriving cells, and means for determining whether cells in the buffer can be accepted. The means for performing is a cell buffer device including a means for performing acceptability determination in units of one or more cells constituting the packet of the connection i.

Here, the present invention is characterized in that means for measuring the number of cells constituting the packet of the connection i input to the buffer during the period T, and the number of cells measured by the measuring means Means for smoothing the reception, and the means for determining whether or not the reception is acceptable, when the head cell constituting the packet of the connection i newly arrives, according to the number of cells smoothed by the smoothing means. It includes means for making a determination as to whether or not it is possible.

In the buffer, first and second thresholds are set for the queue length, and the first threshold is larger than the second threshold. If the queue length of the buffer is equal to or less than the second threshold, the cells constituting the packet of the arriving connection i are input to the buffer without performing the acceptability determination, and the queue length of the buffer is equal to the first threshold. If it is between the second thresholds, the acceptability determination is made for the cells constituting the packet of the connection i which has arrived according to the smoothed cell number, and if the queue length of the buffer is not less than the first threshold, the arrival It is desirable to include means for discarding the cells constituting the packet of the connection i without performing the acceptability determination.

The number of cells that have been smoothed is MIC, the number of cells constituting the packet of the connection i input to the buffer during the period T is CIC, and the smoothing coefficient is α (0 ≦ α ≦ 1 ), And when the previous number of smoothed cells is MIC ′, it is preferable that the smoothing means includes means for calculating MIC = (1−α) × MIC ′ + α × CIC. The smoothed cell number MIC indicates the average number of cells input to the buffer during the period T.

Further, the means for making the acceptability determination comprises: if the queue length of the buffer is between the first threshold value and the second threshold value, the smoothed cell number MIC; According to the number of connections Na in which at least one cell is included in the buffer, when MIC / T <1 / Na, the cell can be accepted in the buffer. When MIC / T ≧ 1 / Na, the cell can be accepted in the buffer. It is desirable to adopt a configuration that includes a unit that makes it impossible.

At this time, if it is desired to distribute a large number of network resources only to a specific connection i, instead of equally distributing the network resources among the connections sharing a common network resource, the acceptability determination is made. The means for performing is MIC / T <Wi / W, where Wi is the ratio of network resources desired to be allocated to connection i, and W is the sum of Wi of connections in which at least one cell is included in the buffer in connection i. In this case, the buffer may be configured to receive cells, and when MIC / T ≧ Wi / W, the buffer may include a unit that disables the reception of cells.

A second aspect of the present invention is a selective ATM cell discarding method, which determines whether or not to accept a cell in a buffer for temporarily storing an arriving cell, when one or more packets constituting a connection i packet are accepted. This is a selective ATM cell discarding method in which acceptability is determined for each cell.

Here, the feature of the present invention is that during the period T, the number of cells constituting the packet of the connection i input to the buffer is measured, and the measured number of cells is smoothed. When the first cell constituting the packet of the connection i arrives, the acceptability determination is made according to the smoothed cell number.

The buffer has first and second thresholds set for its queue length, the first threshold being greater than the second threshold, and the queue length of the buffer being equal to the second threshold. If the threshold is equal to or less than the threshold, the cell constituting the packet of the arriving connection i is input to the buffer without performing the acceptability determination, and if the queue length of the buffer is between the first threshold and the second threshold, Acceptance determination is performed on the cells constituting the packet of the connection i arriving according to the smoothed cell number, and if the queue length of the buffer is equal to or greater than the first threshold, the cell constituting the packet of the arrived connection i is accepted. It is desirable to discard without making the determination.

[0024]

Embodiments of the present invention will be described with reference to FIG. FIG. 1 is a block diagram of a main part of a cell buffer device according to a first embodiment of the present invention.

The present invention is a cell buffer device comprising a buffer 6 for temporarily storing arriving cells, and a determination unit 2 for determining whether or not cells in the buffer 6 can be accepted. Is a cell buffer device that determines acceptability in units of one or more cells constituting a packet of connection i.

Here, the features of the present invention include a queue length monitoring unit 4 for measuring the number of cells constituting the packet of the connection i input to the buffer 6 during the period T, And a management table 5 including a low-pass filter as a means for smoothing the number of cells measured by the unit 4. The determination unit 2 determines whether the first cell constituting the packet of the connection i newly arrives. there is to performing acceptance determination according to the number of cells that are smoothed by the low pass filter.

In the buffer 6, a threshold value MAX-TH and a threshold value MIN-TH as first and second threshold values are set for the queue length, and the threshold value MAX-TH is larger than the threshold value MIN-TH. If the queue length of the buffer 6 is equal to or smaller than the threshold MIN-TH, the determination unit 2 inputs the cells constituting the packet of the arriving connection i to the buffer 6 without performing the acceptability determination, and determines that the queue length of the buffer 6 is If the threshold value is between the threshold value MAX-TH and the threshold value MIN-TH, the acceptability determination is performed on the cells constituting the packet of the connection i arriving according to the smoothed cell number, and the queue length of the buffer 6 is equal to or greater than the threshold value MAX-TH. If so, the cell constituting the packet of the arriving connection i is discarded without performing the acceptability determination.

The number of cells smoothed is MIC, the number of cells constituting the packet of connection i input to the buffer 6 during the period T is CIC, and the smoothing coefficient is α
When (0 ≦ α ≦ 1) and the previous number of smoothed cells is MIC ′, the low-pass filter calculates as MIC = (1−α) × MIC ′ + α × CIC. The smoothed cell number MIC indicates the average number of cells input to the buffer 6 during the period T.

The first embodiment of the present invention is an embodiment for equally distributing network resources among connections sharing a common network resource. The judging unit 2 determines that the queue length of the buffer 6 is equal to the threshold value MAX- If TH is between TH and the threshold MIN-TH, the smoothed cell number MIC, the period T, the buffer 6
According to the number of connections Na including at least one cell, when MIC / T <1 / Na, the cell can be accepted in the buffer 6, and when MIC / T ≧ 1 / Na, the cell can be accepted in the buffer 6. Not allowed.

The second embodiment of the present invention is an embodiment for distributing a large amount of network resources only to a specific connection i. The determination unit 2 sets the ratio of network resources to be allocated to the connection i to Wi, Of the connection in which at least one cell is included in the buffer 6 in the connection i
When i is the sum, when MIC / T <Wi / W, the buffer 6 can accept the cell, and when MIC / T ≧ Wi / W, the buffer 6 cannot accept the cell.

[0031]

DESCRIPTION OF THE PREFERRED EMBODIMENTS (First Embodiment) A first embodiment of the present invention will be described with reference to FIGS. FIG. 1 is as described above. FIGS. 2 to 6 are flowcharts showing the algorithm of the first embodiment of the present invention. FIG. 7 is a diagram showing the configuration of the management table according to the first embodiment of this invention.

The cell identification unit 1 shown in FIG. 1 identifies the VCI and AUU of the cell that has arrived. Also, the management table 5
Is the number of active connections, the packet status for each VC, and the number of cells input during the current period T (CIC:
Current Input Cell and average number of input cells (MIC:
Mean input cell), the queue length monitoring unit 4 monitors the queue length of the buffer 6, the determination unit 2 determines whether the arriving cell is to be input to the buffer 6 or discarded, and the processing unit 3
Inputs or discards the cell to the buffer 6 according to the judgment of the judgment unit 2. Here, the active connection refers to a connection having at least one cell in the buffer 6, and the number of active connections refers to the number of connections.

Here, the packet status of the management table 5 can be "00", "01", "10", or "11".
The packet state “00” indicates a state in which a packet is not currently being transferred. The packet state “01” indicates a state in which a packet is currently being transferred and cells constituting the packet are being input to the buffer 6.

The packet state "10" indicates a state in which a packet is currently being transferred and all cells constituting the packet are forcibly discarded from the first cell.

The packet state "11" indicates that the packet is currently being transferred and the cells constituting the packet have been input to the buffer 6, but the cells constituting the packet have been discarded, and the last packet state has been discarded. This shows a state in which cells other than the discarded cells and subsequent cells are forcibly discarded.

FIGS. 2 to 6 show the algorithm of the first embodiment of the present invention. Hereinafter, the first embodiment of the present invention will be described with reference to FIGS. 2 to 6 while referring to the configuration of FIG. When a cell arrives (S0), the cell identifying unit 1 identifies the VCI and AUU of the arriving cell and notifies the judging unit 2 of the information. The determination unit 2 determines the VC notified from the cell identification unit 1
It is checked whether the packet status of I is “00” (S
1). (1) When the notified VCI packet state is not “00” (S1) and the notified AUU is “1” (S2), the packet state corresponding to the notified VCI is “10”. Is checked (S4). As a result, if the packet status is “10” (S4), the processing unit 3 is notified that the packet is discarded, and the VCI packet status notified to the management table 5 is notified that the packet status is changed to “00” (S6). If the packet status is not "10" (S4), the queue length monitoring unit 4 checks whether the queue length is smaller than the buffer size (S4).
5). As a result, if it is smaller, the processing unit 3 is notified of the input,
The packet status of the VCI notified to the management table 5 is changed to “00”, and the CIC (Current I
nput Cell), the processing unit is notified of the discard if it becomes smaller, and the packet state of the VCI notified to the management table is notified to be changed to "00" (S7). (2) If the packet status of the notified VCI is not “00” (S1) and the notified AUU is “0” (S2), the packet status corresponding to the notified VCI is “01”. Is checked (S8). As a result, "0
If "1", the queue length monitoring unit 4 checks whether the queue length is smaller than the buffer size (S10). as a result,
If the queue length is smaller than the buffer size, the input is notified to the processing unit 3 and the VCI notified to the management table 5 is notified.
Is notified that "1" is added to the CIC (S11). If the queue length is not smaller than the buffer size (S1
0), the processing unit 3 is notified that the packet is discarded, and the management table 5 is notified that the packet status is changed to "11" (S12). If the packet state is not "01" (S8), the processing unit 3 is notified of discard (S9). (3) If the packet status of the notified VCI is "00" (S1) and the notified AUU is "1" (S3), the queue length monitoring unit 4 sets the queue length to the threshold MAX-
It is checked whether it is larger than TH (S14), smaller than threshold value MIN-TH (S13), or any other value. If the queue length is larger than the threshold value MAX-TH (S14), the processing unit 3 is notified of discard (S16). Queue length is threshold MIN
If it is smaller than -TH (S13), the processing unit 3 is notified of the input, and the CCI of the VCI notified to the management table 5 is notified.
(S17). Otherwise, the MIC (Mean Input) corresponding to the notified VCI
It is checked whether the value obtained by dividing (Cell) by T is greater than the value obtained by dividing 1.0 by the number of active connections Na (S15).
If it is larger, the processing unit 3 is notified of discard (S1).
6). If it is not large, the processing unit 3 is notified of the input, and
It notifies that "1" is added to the CIC of the VCI notified to the management table 5 (S17). (4) If the packet status of the notified VCI is “00” (S1) and the notified AUU is “0” (S3), the queue length monitoring unit 4 sets the queue length to the threshold MAX.
It is checked whether it is larger than −TH (S19), smaller than the threshold MIN-TH (S18), or any other value. If the queue length is larger than the threshold value MAX-TH (S19), the processing unit 3 is notified that the packet is discarded, and the management table 5 is notified that the packet status is changed to "10" (S21). If the queue length is smaller than the threshold value MIN-TH (S18), the processing unit 3
And the packet status is set to “0” in the management table 5.
"1", and notifies that "1" is added to the CIC of the notified VCI (S22). Otherwise, it is checked whether the value obtained by dividing the MIC corresponding to the notified VCI by T is greater than the value obtained by dividing 1.0 by the number Na of active connections (S20). If it is larger, the processing unit 3 is notified that the packet is discarded, and the management table is notified that the packet status is changed to "10" (S21). If not, the processing unit 3
And the packet status is set to "0" in the management table.
The VCI is changed to "1" and notified by adding "1" to the CIC of the notified VCI (S22).

Here, the configuration and creation procedure of the management table 5 will be described with reference to FIG. Timer unit 5 shown in FIG.
0 notifies the management unit 51 of a signal every period T. The management unit 51, which has received the signal from the timer unit 50,
Is notified to the calculation unit 52 to calculate. Calculation unit 52
Means that the previous MIC is MIC ′ and the smoothing coefficient is α (0
.Ltoreq..alpha..ltoreq.1 and a new MIC is calculated from the formula of MIC = (1-.alpha.). Times.MIC '+. Alpha..times.CIC, and the result is notified to the management unit 51. The management unit 51 that has received the notification from the calculation unit 52 writes the new MIC into the table 53,
All ICs are set to "0". Further, the number of connections in which the MIC is equal to or greater than a certain value (for example, 1) is written in the number of active connections.

As described above, the average number of cells MIC input to the buffer 6 during the period T is
Since the calculation can be performed by measuring the number of cells CIC input to the buffer 6, both the number of cells of the connection i input to the buffer 6 and the number of cells of the connection i output from the buffer 6 are monitored as in the related art. Therefore, the management table 5 serving as a reference for determining whether the buffer 6 can be accepted can be easily created.

(Second Embodiment) A second embodiment of the present invention will be described with reference to FIG. FIG. 8 is a view for explaining the second embodiment of the present invention. The first embodiment of the present invention is an embodiment in a case where network resources are equally distributed between connections sharing a common network resource, but the second embodiment of the present invention
This is an embodiment in a case where it is desired to distribute many network resources only to a specific connection i.

It is assumed that the ratio of the network resources to be allocated to the connection i is Wi, and W is the sum of Wi of the active connections. For example, the number of connections is 5, and the respective Wis of the connections 101 to 105 are (connection 101) W1 = 5 (connection 102) W2 = 4 (connection 103) W3 = 3 (connection 104) W4 = 2 (connection 105) When W5 = 1, let W be the total of Wi of the connections that are active connections. For example, if the connections 101, 103, and 105 are active connections, W = W1 + W3 + W5 = 5 + 3 + 1 = 9.

At this time, as shown in FIG. 8, S1 in FIG.
5 and FIG. 6 by replacing MIC / T ≧ 1 / Na with MIC / T ≧ Wi / W, network resources can be allocated to connection i at a ratio Wi.

[0042]

As described above, according to the present invention,
Since there is no need to manage the number of output cells, it is possible to fairly allocate network resources among connections using common network resources with a simpler hardware configuration. Also, since network resources can be distributed to each connection at a preset ratio, a minimum bandwidth can be guaranteed for each connection.

[Brief description of the drawings]

FIG. 1 is a block diagram of a main part of a cell buffer device according to a first embodiment of the present invention.

FIG. 2 is a flowchart showing an algorithm according to the first embodiment of the present invention.

FIG. 3 is a flowchart showing an algorithm according to the first embodiment of the present invention.

FIG. 4 is a flowchart showing an algorithm according to the first embodiment of the present invention.

FIG. 5 is a flowchart showing an algorithm according to the first embodiment of the present invention.

FIG. 6 is a flowchart showing an algorithm according to the first embodiment of the present invention.

FIG. 7 is a diagram showing a configuration of a management table according to the first embodiment of the present invention.

FIG. 8 is a diagram for explaining a second embodiment of the present invention.

FIG. 9 is a diagram for explaining Per-VC EPD control.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 Cell identification part 2 Judgment part 3 Processing part 4 Queue length monitoring part 5 Management table 6 Buffer 50 Timer part 51 Management part 52 Calculation part 53 Table

──────────────────────────────────────────────────続 き Continued on the front page (58) Field surveyed (Int.Cl. ⁷ , DB name) H04L 12/28

Claims (7)

(57) [Claims] 1. A buffer for temporarily storing arriving cells, and means for judging the acceptability of cells in the buffer, wherein the means for judging acceptability comprises one or more cells constituting a packet of connection i. A cell buffer device including means for determining acceptability in units of: a means for measuring the number of cells constituting a packet of a connection i input to the buffer during a period T; and the number of cells measured by the measuring means. Means for smoothing the connection.
A cell buffer device comprising: means for determining acceptability based on the number of cells smoothed by the smoothing means when a leading cell constituting the packet arrives. 2. The buffer is set with first and second thresholds for its queue length, the first threshold being greater than the second threshold, and performing the acceptability determination. Means for arriving connection i if the queue length of the buffer is less than or equal to the second threshold.
The cells constituting the packet are input to the buffer without performing the acceptability determination and if the queue length of the buffer is between the first threshold and the second threshold, according to the smoothed cell number A determination is made as to whether or not the cell constituting the packet of the arriving connection i is acceptable. If the queue length of the buffer is equal to or greater than the first threshold, the cell constituting the packet of the arriving connection i is discarded without performing the acceptability determination. 2. The cell buffer device according to claim 1, comprising means. 3. The method according to claim 1, wherein the smoothed cell number is MIC,
Connection i input to the buffer during the period T
When the number of cells constituting the packet is represented by CIC, the smoothing coefficient is represented by α (0 ≦ α ≦ 1), and the number of previously smoothed cells is represented by MIC ′, the means for smoothing: MIC = 3. The cell buffer device according to claim 1, further comprising means for calculating (1−α) × MIC ′ + α × CIC. 4. The means for performing the acceptability determination includes: when the queue length of the buffer is between the first threshold value and the second threshold value, the smoothed cell number MIC; the period T; According to the number of connections Na in which at least one cell is included in the buffer, when MIC / T <1 / Na, the cell can be accepted in the buffer. When MIC / T ≧ 1 / Na, the cell can be accepted in the buffer. 4. The cell buffer device according to claim 2, further comprising: means for disabling the cell buffer. 5. The method according to claim 1, wherein the means for determining whether the connection is acceptable includes setting a ratio of network resources to be allocated to the connection i to Wi, and storing at least one W in the buffer in the connection i.
When MIC / T <Wi / W, the buffer can accept a cell. When MIC / T ≧ Wi / W, the cell accepts a cell in the buffer. 5. The cell buffer device according to claim 4, further comprising means for disabling. 6. A selective ATM cell discarding method for determining the acceptability of one or more cells constituting a packet of a connection i when determining the acceptability of a cell in a buffer for temporarily storing an arriving cell. At T, the number of cells constituting the packet of the connection i input to the buffer is measured, and the measured number of cells is smoothed. When the head cell newly constituting the packet of the connection i arrives, A method for selectively discarding ATM cells, wherein the acceptability decision is made according to the smoothed cell number. 7. A first and a second threshold value are set for the queue length of the buffer, the first threshold value is larger than the second threshold value, and the queue length of the buffer is set to the second threshold value. If the threshold value is equal to or less than the second threshold value, the cell constituting the arriving connection i packet is input to the buffer without performing the acceptability determination, and if the queue length of the buffer is between the first threshold value and the second threshold value, For example, the acceptability determination is performed for the cells constituting the connection i packet arriving according to the smoothed cell number, and the cells constituting the arrived connection i packet if the queue length of the buffer is equal to or greater than the first threshold value. 7. The selective ATM cell discarding method according to claim 6, wherein the discarding is performed without determining the acceptability.