JPH10242986A - Cell discarding method and apparatus for implementing the method - Google Patents

Abstract

(57) [Summary] [PROBLEMS] To continuously discard cells on the input side when a plurality of connections share a buffer, and to wastefully transfer and waste cells that are discarded at the destination terminal. Provided is a cell discarding method and an apparatus therefor, which can reduce a decrease in throughput due to a delay of an Ack returned to a side and can eliminate a limit on the number of simultaneous connections. SOLUTION: A buffer monitoring means (buffer monitoring unit 2) for monitoring a state of a buffer 1 and a comparing means (Comparison) for comparing a queue length of a buffer obtained by the buffer monitoring means with a predetermined threshold value Unit 3) and a buffer control unit for discarding a certain number of cells in the buffer when the queue length of the buffer exceeds a predetermined threshold value as a result of the comparison by the comparison unit (the buffer control unit 4). ).

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method of discarding cells at the time of congestion when an information frame is decomposed into cells and data communication for transferring the cells is performed, and more particularly, communication between LANs (Local Area Network). Is applied to the nodes that make up the network,
As a result, the present invention also relates to a cell discarding method effective for improving network throughput and a cell discarding device for realizing the method.

[0002]

2. Description of the Related Art FIG. 6 shows an outline of a typical conventional cell discarding method. In this method, the node always manages the queue length of the cell stored in the buffer, that is, the queue length, and this queue length is equal to the buffer length (physical capacity of the buffer), and the buffer becomes full. If
This is to discard the arrival cell newly reaching the node. That is, in the example shown in FIG. 6, three cells (cells 2, 3, and 4) are already stored in a buffer having a buffer length of 4 (FIG. 6A), and two cells are stored therein. When (cells 5 and 6) arrive, the cell 6 is discarded because the cell 5 is input and the buffer becomes full and there is no room for the cell 6 (FIG. 6B).

Another conventional cell discarding method is shown in FIG.
Has also been proposed. In this method, the node always manages the queue length of the buffer, and if the queue length exceeds a predetermined threshold smaller than the buffer length, a new arrival cell and a cell included in the packet to which the cell belongs are included. Are all discarded. That is,
Explaining with the example shown in FIG. 7, for example, the threshold value is previously set to 3 for the buffer length 4. It is assumed that some cells 2 of packet A and cells 3 and 4 of packet B are stored in the buffer (FIG. 7A). When the packet C composed of the cells 5 and 6 arrives there, the empty space in the buffer is 1, and the cell 6 overflows. Therefore, cell 6
All the cells included in the packet C to which the cell belongs, including the cell 5, are discarded (FIG. 7B).

[0004]

In the conventional typical cell discarding method as shown in FIG. 6, when the buffer becomes full and becomes congested, the following problems occur. (1) When a plurality of connections share a buffer, the input speed is higher than the output speed. Therefore,
When the buffer is exhausted due to the congestion state, there is a high possibility that cells are continuously discarded on the input side.

(2) For example, ATM (Asynchronous Tra)
In the case of a method in which one upper-layer packet is divided into a plurality of lower-layer cells and transmitted as in the case of the nsfer mode (asynchronous transfer mode), the lower layer is used in the above-described conventional typical cell discarding method. Therefore, only a part of the lower layer cells constituting the packet of the upper layer is discarded. However, non-discarded cells belonging to the same packet are also discarded at the destination terminal.
In other words, cells that are discarded at the destination terminal are being transferred, and resources are wasted.

(3) As an example, IP over ATM
A case is considered in which TCP (Transmission Control Protocol) is used in an upper layer of (a method of transferring IP packets by ATM). In a window control method called fast-retransmit of TCP, when an originating TCP receives an Ack requesting retransmission of a specific packet repeatedly, it is assumed that congestion has occurred and the originating window is reduced. However, in the above-described conventional typical cell discarding method, cells arriving at the time of congestion when the empty buffer becomes zero are discarded, so that cells subsequent to the discarded cells pass through the buffer by the number of cells in all buffers. I have to wait for a minute. Therefore, the arrival of the next cell continuous to the discarded cell on the receiving side is delayed by the waiting time, and A
ck is delayed to return. In other words, it is delayed that the sending-side TCP performs window control. As a result, many cells are discarded, TCP timeout occurs, and there is a high possibility that the throughput is significantly reduced.

In another conventional cell discarding method shown in FIG. 7, when a predetermined threshold value is exceeded, a new arriving cell and all cells included in a packet to which the cell belongs are discarded. The above problems (1) and (2) can be slightly solved. However, this method not only can not solve the problem (3) but also (4)
Has the following problems.

(4) The node holds a table that is distinguished for each connection and describes whether cells newly arriving in the buffer should be discarded or input to the buffer, and accessed each time a cell arrives. You must decide what to do with that cell. Therefore, the table must be accessed every time a cell is input, and there is a limit to the number of simultaneous connections due to problems such as processing time.

[0009] The present invention solves the above-mentioned problems, and continuously discards cells on the input side when a plurality of connections share a buffer, and wastefully transfers cells discarded at the destination terminal. A cell discarding method and a cell discarding device for realizing the method capable of reducing a decrease in throughput due to resource consumption and a delay of an Ack returned to the calling side and further eliminating a limit on the number of simultaneous connections. It is intended to provide.

[0010]

In order to achieve the above object, the cell discarding method of the present invention always manages a buffer at a node and monitors a queue length of the buffer, and the queue length is determined in advance. When the threshold value S1 is exceeded (step 102 in FIG. 5: Y), a fixed number D of cells are collectively discarded from the buffer (the output side of the buffer) (step 1 in FIG. 5).
03).

Further, the cell discarding device of the present invention comprises a buffer monitoring means (buffer monitoring unit 2) for monitoring the state of a buffer (buffer 1 in FIG. 4) in a node, and a buffer queue obtained by the buffer monitoring means. Comparing means (same comparing section 3) for comparing the length with a predetermined threshold value; and as a result of comparison by the comparing means, when the queue length of the buffer exceeds a predetermined threshold value, And a buffer control unit (buffer control unit 4) for discarding a fixed number D of cells. Here, the constant number D is 1/1 of the buffer length.
A large value such as 3 or 1/4 is assumed.

[0012]

DESCRIPTION OF THE PREFERRED EMBODIMENTS In the present invention, a node always manages a buffer, and when a buffer queue length exceeds a predetermined threshold, a fixed number of cells are buffered, for example, from the output side of the buffer. Collectively discard. As described above, the present invention collectively discards a large number of continuous cells at a time, so it is premised on a network having a large number of simultaneous connections and a high rate of traffic flowing compared to the capacity of the network. Then, the problem described in (1) and (2) above can be alleviated and the problem described in (3) can be solved, even though the control is very simple. In addition, since it can be realized by a very simple control of collectively discarding, the above-mentioned problem (4) can be solved.

Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings. As an example of data communication to which the present invention applies,
The following description is based on the premise that TCP packets such as IP over ATM are carried by ATM cells. FIG.
FIG. 3 is a diagram for explaining an outline of the present invention, and is an example in a case where a threshold value S1 of a buffer is set to “3”. In FIG. 1A, three cells (cells 2, 3, and 4) equal to the threshold value S1 are already stored in the buffer.
It is assumed that a new cell 5 arrives here. In this case, when the cell 5 is stored, the buffer exceeds the threshold value. Therefore, as shown in FIG. 1B, the D (cell), that is, the cells 2, 3, and 4 are discarded from the (output side) of the buffer. .

FIG. 2 is a diagram showing an example of a network configuration to which the present invention is applied. The example in the figure shows a case where N originating terminals are connected to N destination terminals via a transmitting node A, a 150 Mbps line, and a receiving node B.

FIG. 3 is a diagram showing a specific example of the state transition. FIG. 3A shows a transition model of the window size (Mbps) on the transmission side when TCP is used in the upper layer as an example, and FIG. 3B shows a threshold value S1 = B-1.
And the queue length of the corresponding transmitting node (Mbp
The transition of s) is shown.

In FIG. 3, at T1, the window size on the transmitting side exceeds the link bandwidth, and the queue length of the buffer is affected by the window size and starts to increase from time t1. At time t2, the queue length becomes larger than the threshold value S1 (= B-1) and becomes equal to the buffer size (B).
Discard the D cells from the buffer. Due to this discard, the queue length becomes BD. At T3, the window size starts to drop due to the influence of cell discard at the time t2. At the time point t3, the queue length of the node starts to decrease due to the effect that the window size on the transmitting side decreases at T3 and the number of output packets decreases.

Therefore, between t2 and t3, the signal goes from a certain point (such as a node) on the transmission path to the receiving terminal in the forward direction, then returns to the transmitting terminal, and then returns to the first point (node Etc.), there is a difference in RTT (Round Trip Time) indicating the propagation delay time required to return to t3 = t2
+ RTT is established. At t4, the queue length becomes 0. In FIG. 3, f1 indicating the change of the window of the calling terminal is shown.
And f2 indicating the change in the queue length of the node caused by the change of the window, Ti + Δt
= Ti (Δt: propagation delay from the calling terminal to the node).

Next, an example of an apparatus configuration for realizing the cell discarding method of the present invention will be described. FIG. 4 is a diagram illustrating an example of hardware for implementing the present invention. In the figure,
1 is a buffer of the node, 2 is a buffer monitoring unit that constantly monitors the queue length of the buffer 1, and 3 is a buffer monitoring unit 2.
The comparing unit 4 compares the queue length of the buffer 1 monitored by the comparator with a predetermined threshold value (S1). As a result of the comparison by the comparing unit 3, the queue length is determined in advance. If the threshold value (S1) is exceeded, a buffer control unit that discards a fixed number (D) of cells from the buffer 1, for example, from the output side of the buffer.

FIG. 5 is a flowchart showing a processing procedure in the node. Next, the processing on the node side will be described with reference to the configuration diagram of FIG. 4 and the flowchart of FIG. First, the buffer monitoring unit 2 constantly monitors the queue length of the buffer 1. When the buffer receives a cell (step 101), the buffer monitoring unit 2 is determined in advance by the comparison unit 3 as the queue length of the buffer. The threshold value S1 is compared (step 102). If the queue length exceeds the threshold value S1 (step 102: Y), the buffer control unit 4 is notified of the fact. When the buffer control unit 4 receives the notification from the comparison unit 3, the buffer control unit 4 sets the cell in the buffer to D (cel).
1) Discard (step 103). However, if the queue length does not exceed the threshold (step 10).
2: N) Do nothing.

According to the embodiment described above, even if a plurality of connections share a buffer, the possibility that cells are continuously discarded on the input side in a congested state is low, and a part of an information packet is constituted. Is less likely to waste resources by carrying cells that are discarded on the terminal side and discarding resources on the terminal side, and the time required for the terminal to take control when the network is congested is reduced. as a result,
The network can be used effectively, and the throughput of the network can be improved. Further, since complicated control such as extraction of a cell belonging to a unique packet is not required, there is no problem of the number of simultaneous connections and the like, and the feasibility is high.

[0021]

According to the cell discarding method of the present invention, continuous discarding of cells at the input side when a plurality of connections share a buffer, and wasteful transfer of cells discarded at the destination terminal. It is possible to reduce a decrease in throughput due to resource consumption and a delay of the Ack returned to the caller, and to eliminate the limit on the number of simultaneous connections.

[Brief description of the drawings]

FIG. 1 is a diagram showing an outline of a cell discarding method of the present invention.

FIG. 2 is a diagram showing a configuration example of a network to which the present invention is applied.

FIG. 3 is a diagram illustrating a transition model of a window size on a transmission side and a transition of a queue length of a transmission side node corresponding to the transition model.

FIG. 4 is a diagram showing an example of the cell discarding device of the present invention.

FIG. 5 is a diagram showing a procedure on the node side in the present invention.

FIG. 6 is a diagram showing a conventional typical cell discarding method.

FIG. 7 is a diagram showing another conventional cell discarding method.

[Explanation of symbols]

 1: buffer, 2: buffer monitoring unit, 3: comparison unit, 4: buffer control unit

Claims (3)

[Claims] 1. A method for discarding a buffer cell when a node is congested in a data communication system in which an information frame (packet) is decomposed into cells and transferred, wherein a buffer state in the node is monitored and a queue length of the buffer is predetermined. Determining whether the threshold value exceeds a predetermined threshold value, and, in the determining step, when the queue length of the buffer exceeds a predetermined threshold value, discarding a fixed number of cells from the buffer. A cell discarding method comprising: 2. The cell discarding method according to claim 1, wherein the step of collectively discarding a certain number of cells is a step of collectively discarding a certain number of cells from an output side of a buffer. 3. A buffer discarding device in a data communication system for disassembling an information frame (packet) into cells and transferring the cells when the node is congested. Comparing means for comparing the queue length of the buffer obtained by the above-mentioned method with a predetermined threshold value; and as a result of the comparison, when the queue length of the buffer exceeds a predetermined threshold value, A buffer control unit for discarding a certain number of cells in the cell.