JP2001111556A - Congestion avoidance apparatus and method using RED - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a congestion controller, capable of discarding a packet with a small amount of processing by randomly discarding cells except the last call, and its method. SOLUTION: A congestion state deciding part 42 decides the occurrence of a congestion state, in such a manner that a transmitting part 23 monitors the average of queue lengths of a buffer, and the wasteful use of a line caused by discarding the last cell is eliminated, by deciding whether an arriving cell is the last cell to arrive, when it is decided that the congestion state takes place. Also, a packet, including a cell discarded by a cell discard deciding part, can be discarded without executing processing specifying the packet, including the cell by discarding cells other than the last cell, with an arbitrary probability.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an apparatus and a method for avoiding congestion by RED, and more particularly, to a network using an IP over ATM system to which AAL5 is applied.
The present invention relates to a RED-based congestion avoidance apparatus and a method thereof, in which a processing amount is reduced by improving a method of realizing congestion avoidance by RED.

[0002]

2. Description of the Related Art At present, information transmission by computer communication is predominant, regardless of individual level or company level.

However, in computer communication, traffic from each terminal has a strong burst property,
There is a problem that it is difficult to estimate the traffic pattern in advance.

[0004] For this reason, a congestion state occurs at each transit switching node on the network, causing a delay in the communication speed of the entire network.

[0005] In order to efficiently avoid the above-mentioned problems in an ATM network, a conventional CBR service,
Best effort to transmit information efficiently by controlling according to the degree of congestion in the network by a method that does not allocate a bandwidth in advance, such as a UBR service or an ABR service, instead of a method of allocating a bandwidth in advance like a VBR service The agenda on services is being discussed at ATM forums and the like.

Above all, especially in the UBR service, no quality assurance in communication is performed in the ATM layer, and congestion avoidance is performed by a function of an upper layer, for example, by window flow control in the case of TCP, as a substitute means. Therefore, there is a merit that computer communication can be performed at a low cost, so that future development is greatly desired.

[0007] However, in the above UBR service,
As compared with the case where a packet switch having the same buffer size is used, there is a problem that the packet throughput is deteriorated as compared with other services.

[0008] The main cause of this is that in communication by the ATM system, discarding occurs not in units of packets but in units of cells in order to eliminate a congestion state. That is,
Since the receiving side performs control to discard the packet including the discarded cell (hereinafter, referred to as an incomplete packet), the transmitting side requires retransmission control. Therefore, the cells constituting the incomplete packet are transmitted. This is to waste the capacity of the road.

In addition, in the ATM system, when cell discarding is generally performed, since the discarded cells are distributed in different packets, there is also a problem that many incomplete packets are generated.

As a method for solving the above problems,
In a transit switching node of the Internet protocol (hereinafter, referred to as IP), when a sign of congestion starts to appear, a packet is randomly selected and discarded at a low discard rate from packets passing therethrough, or congestion notification in a packet header is performed. By setting a bit, there is congestion avoidance by a Random Early Detection (RED) method, which is a method of notifying an application or a transport protocol of some hosts of the occurrence of congestion and inducing a reduction in the amount of transmission from the host. .

The congestion avoidance by the RED is described in "Randomness" by Sally Floyd and Van Jacobson in the prior art document 1.
Early Detection Gateways for Congestion Adoidanc
e ”, (IEEE / ACM Transaction on Networking, Vol.1 No.
4 August, 1993.).

The prior art document 1 discloses a method for determining a packet to be discarded by randomly determining an interval between a packet to be discarded and a packet to be discarded next. Are further disclosed.

The congestion avoidance by RED disclosed in the above-mentioned prior art document 1 will now be described. First, since the AAL5 recognizes a packet at the cell level, the last cell constituting the packet, that is, End Of Packet (EOP) The EOP is distinguished from other cells by setting the AUU parameter of the cell (same as the last cell) to 1 and the AUU parameter of the other cells to 0.

Therefore, in AAL5, one ATM virtual circuit (hereinafter referred to as V
Paying attention to C), the cell following the received EOP cell is observed, and the cells up to the first received EOP cell can be regarded as cells constituting the same packet.

However, congestion avoidance by RED based on the technique of recognizing a packet at the cell level by using the EOP cell as described above is based on the EOP of the packet.
When a cell is discarded, even if all cells constituting the next packet have reached the receiving side, it is impossible to distinguish the cell from the immediately preceding packet, so that error detection using a CRC code or the like occurs, There is a problem that all cells are discarded up to the received packet (complete packet).

In contrast to the prior art 1, a packet discarding method based on the IP over ATM system using AAL5 is described in the prior art document 2 by Masayoshi Nabeshima in "End Of Pac".
Study on Selective Cell Discarding Method to Prevent Ket Cell Discarding "(SSE98-88, IN96-72, CS96-96).

As a packet discarding method disclosed in the prior art document 2, there are an Early Packet Discard (EPD) method, a method used in Partial Packet Discard (PPD), and an improved method of EPD.

Here, in the IP over ATM system on AAL5, one IP packet is divided into a plurality of ATM data cells and transferred. Therefore, in AAL5, A
A bit indicating the end (hereinafter, referred to as a final bit) is defined in the TM cell header portion.

Therefore, the congestion avoidance by the EPD method is a method for resolving a congestion state by discarding a packet that cannot be processed when congestion occurs in the transit switching node.

In the method used in the PPD, when the head cell arrives at the transit switching node, the transit switching node is in a congested state, that is, the queue length stored in the buffer of the transit switching node is determined in advance. If the state exceeds the set threshold, the head cell and the cell constituting the same packet from the cell are forcibly discarded, and
If it is not congested, it receives from its head cell to the last cell that constitutes the same packet and inputs it to its own buffer. Further, in the process of inputting cells to the buffer,
When there is no free space in the buffer, the congestion state is eased by forcibly discarding cells other than the last cell among the cells constituting the same packet arriving from that point.

In other words, in the method used in the PPD, regardless of whether the first cell of the divided packet is limited or not, the forced cell is discarded from the time when it is determined that discarding is necessary to the cell immediately before the last cell. Was performed.

In the EPD improvement method, when a packet is discarded, attention is paid to one VC, and cell discarding from a cell next to a cell whose last bit is ON (hereinafter referred to as a head cell) is started. Are discarded up to the next cell whose last bit is ON (hereinafter referred to as the last cell).

Further, in this EPD improvement method, two types of improvement methods have been proposed in which the last cell is identified and the last cell is not discarded.

First, in the first improved EPD method, if the immediately preceding cell is not the last cell when the head cell constituting the packet arrives at the transit switching node, regardless of whether it is in a congested state or not, Forcibly discard all cells up to one cell before the next last cell. Further, when the leading cell constituting the packet arrives at the transit switching node, the immediately preceding cell is the last cell, and if the cell is in a congested state, all the cells up to immediately before the next last cell are forcibly discarded. Also, when the head cell constituting the packet arrives at the transit switching node, if the immediately preceding cell is the last cell and is not in a congested state, all cells up to the next last cell are input to its own buffer. Further, in the process of inputting cells into the buffer, if the buffer runs out of free space, the cells other than the last cell among the cells constituting the same packet arriving from that point are forcibly discarded.

Further, in the second improved method of EPD, by providing two types of thresholds for detecting congestion, a high threshold and a low threshold, the shortage of free space in the buffer in the process of inputting cells to the buffer. To prevent cell discarding due to

[0026]

However, the RED
Is realized by using the above-described packet discarding function based on the EPD method or the PPD method, the following problems occur.

The first problem is that the EPD method or the PP
In the D system, one packet disassembled and transferred
In order to adopt a method of discarding the entire packet by discarding the packet in units of M cells (hereinafter referred to as a packet level discarding method), a specific VC is monitored, and all ATM cells created by disassembling one packet are monitored. There is a need to specify and discard, and the amount of treatment increases.

The reason is that in order to realize the packet-level discarding method, the type for a plurality of cells is detected such that the last cell is detected and all the cells constituting one packet up to the next last cell are discarded. This is because it is necessary to execute different processes.

Further, in the first and second EPD improvements, an improvement has been made so that the last cell is not discarded.
The process of discarding packets in units of VC remains, which causes a problem that the processing amount increases.

[0030] The reason is that RED is intended for the entirety of aggregating a plurality of connections.
Is applied to the IP over ATM, a process for the VC of the entire flow for determining the packet to be discarded next and a packet level discarding process for the specific VC to which the packet to be discarded is sent are performed. This is because it is necessary to perform a combination.

Further, the congestion avoidance by the EPD and PPD methods is a means for hastening the recovery of the congestion state when the occurrence of congestion is detected in the transit switching node. On the other hand, the congestion avoidance by RED uses the characteristics of TCP so that packets are always discarded with a small probability and the TCP transmission amount (transmission rate)
Is not to be large.

Therefore, the above EPD and PPD schemes and R
Since RED differs in purpose, configuration and means from ED,
When applied to the D and PPD methods, there arises a problem that the processing amount increases.

Therefore, the present invention has been made in view of the above-mentioned problems, and by discarding cells other than the last cell at random, it is possible to discard packets with a small amount of processing, thereby suppressing and controlling congestion. It is an object of the present invention to provide a congestion avoiding device and a method therefor using RED.

[0034]

In order to achieve the above object, the invention according to claim 1 uses AAL5 as a protocol.
Is a congestion avoidance device based on RED in a network to which the present invention is applied, characterized by having a cell discarding means for specifying and discarding cells other than the last cell based on a cell interval calculated with a predetermined probability.

The second aspect of the present invention provides a RED in a network to which AAL5 is applied as a protocol.
A buffering means for temporarily holding cells received from a line, a queue length monitoring means for calculating a queue length of cells held by the buffering means, and a queue calculated by the queue length monitoring means. A congestion state determination unit that determines the occurrence of a congestion state based on the length, and a final cell determination unit that determines whether an arriving cell is the final cell when the occurrence of the congestion state is determined by the congestion state determination unit. Means, the last cell determination means, when it is determined that the arriving cell is not the last cell, based on the cell interval calculated by a predetermined probability, based on the cell interval, comprising a cell discarding means to discard. I do.

According to the third aspect of the present invention, in the congestion avoiding apparatus according to the second aspect, the queue length monitoring means detects a queue length in the buffering means at predetermined time intervals, The average queue length including the latest queue length is calculated based on the detected queue length, thereby calculating the queue length of the cell held by the buffering means.

According to a fourth aspect of the present invention, in the congestion avoiding apparatus based on the RED according to the second or third aspect, the cell includes, in the header portion constituting the cell, one of the cells constituting the same packet. A final cell indicating whether or not the cell is the last cell, wherein the last cell determination means determines whether or not the cell is the last cell based on the last bit included in the header of the cell. And

According to a fifth aspect of the present invention, in the congestion avoiding apparatus using RED according to any one of the second to fourth aspects, the apparatus further comprises a queue length storing means for storing a predetermined queue length as a threshold value. The congestion state determination means is characterized in that the occurrence of congestion is determined by comparing the queue length calculated by the queue length monitoring means with a predetermined queue length stored in the queue length storage means.

According to a sixth aspect of the present invention, in the congestion avoiding apparatus based on the RED according to any one of the second to fourth aspects, a plurality of predetermined queue lengths are stored as thresholds with different values. The apparatus further includes a queue length congestion level storage unit that further stores a congestion state level corresponding to a predetermined queue length, wherein the congestion determination unit includes a queue length calculated by the queue length monitoring unit and a queue length congestion level storage unit. The stored queue lengths are compared with a plurality of stored queue lengths, and as a result of the comparison, the queue length corresponding to the largest one of the predetermined queue lengths exceeding the queue length calculated by the queue length monitoring means. The congestion level is specified, and occurrence of congestion is determined in stages.

According to a seventh aspect of the present invention, in the congestion avoiding apparatus using the RED according to any one of the first to sixth aspects, the predetermined probability is determined based on an average number of cells into which one packet is divided. Is calculated based on the packet discard rate corresponding to the level of the congestion state, and the cell interval is calculated to be a power of 2 which can be approximated to a predetermined probability.
Based on the value of the power of, a pseudorandom number of equal probability in the range of 0 to twice the value of the power of 2 is created, and specified based on the pseudorandom number, and the cell discarding means is specified based on the cell interval. If the specified cell is not the last cell, the specified cell is discarded.

According to an eighth aspect of the present invention, in the congestion avoiding apparatus using RED according to any one of the first to seventh aspects, the network to which AAL5 is applied as a protocol is a network which employs an IP over ATM system. It is characterized by being.

According to the ninth aspect of the present invention, there is provided a method for avoiding congestion by RED in a network to which AAL5 is applied as a protocol, wherein cells other than the last cell are determined based on a cell interval calculated with a predetermined probability. It is characterized by having a cell discarding step of specifying and discarding.

According to a tenth aspect of the present invention, there is provided a method for avoiding congestion by RED in a network to which AAL5 is applied as a protocol, wherein a buffering step for temporarily holding cells received from a line and a buffering step A queue length monitoring step of calculating a queue length of a held cell, a congestion state determination step of determining occurrence of a congestion state based on the queue length calculated in the queue length monitoring step, and a congestion state determination step in the congestion state determination step. Is determined, the final cell determination step of determining whether the arriving cell is the last cell, and a predetermined probability is determined if the arriving cell is determined to be not the last cell in the final cell determination step. And a cell discarding step of identifying and discarding based on the cell interval calculated by the above.

According to the eleventh aspect of the present invention, in the congestion avoiding method by the RED according to the tenth aspect, the queue length monitoring step detects the queue length in the buffering means at predetermined time intervals, The average queue length including the latest queue length is calculated based on the detected queue length, thereby calculating the queue length of the cell held by the buffering means.

According to the twelfth aspect of the present invention, in the congestion avoidance method using RED according to the tenth or eleventh aspect, the cell includes, in a header portion constituting the cell, a cell among cells constituting the same packet. A final cell indicating whether or not the cell is the last cell, wherein the final cell determination step determines whether or not the cell is the last cell based on the last bit included in the header of the cell. And

According to a thirteenth aspect of the present invention, in the congestion avoiding method according to any one of the tenth to twelfth aspects, the method further comprises a queue length storing step of storing a predetermined queue length as a threshold value. The congestion state determination step, the queue length calculated in the queue length monitoring step,
The occurrence of congestion is determined by comparing a predetermined queue length stored in the queue length storage step.

According to a fourteenth aspect of the present invention, in the congestion avoiding method using the RED according to any one of the tenth to twelfth aspects, the congestion determining step includes the step of: A plurality of queue lengths are compared with a plurality of queue lengths stored so as to correspond to the respective levels of the congestion state. As a result of the comparison, of the predetermined queue lengths exceeding the queue length calculated by the queue length monitoring means,
It is characterized in that a congestion level corresponding to a predetermined queue length that is the largest value is specified, and occurrence of congestion is determined stepwise.

According to a fifteenth aspect of the present invention, in the congestion avoidance method using RED according to any one of the ninth to fourteenth aspects, the predetermined probability is determined by the average number of cells into which one packet is divided. The cell interval is calculated based on the packet loss rate corresponding to the congestion state level, and the cell interval is determined to be a power of 2 which can be approximated to a predetermined probability. , A pseudorandom number of equal probability is created in a range from 0 to twice the value of the power of 2 and specified based on the pseudorandom number, and the cell discarding step is performed based on the cell specified based on the cell interval. If is not the last cell, the identified cell is discarded.

According to a sixteenth aspect of the present invention, in the congestion avoiding method using RED according to any one of the ninth to fifteenth aspects, the network to which AAL5 is applied as a protocol is a network that employs an IP over ATM system. It is characterized by being.

[0050]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Hereinafter, a congestion control apparatus using RED and a method thereof according to the present invention will be described in detail with reference to the drawings.

(Overview of RED) Here, RED in the embodiment of the present invention uses the IP over ATM system and presupposes TCP as its upper layer protocol.

In this TCP, since flow control is performed end-to-end, the transmission window size is controlled so as to gradually increase until it reaches the reception window size (upper limit) of the receiving side. Therefore, the case where TCP reduces the transmission window size to reduce the transmission amount is limited to only when packet discard is detected.

Therefore, the transit switching node monitors the time average of the queue length, and if the time average becomes large to some extent, discards the packet with a small probability. This is based on the EPD method and PPD described in the above prior art.
The method is fundamentally different in purpose, configuration, and means.

Also, in TCP, the transmission window size is increased until packet discard detection, so that packet discard is premised. Therefore, using the packet discarding by TCP for the purpose of avoiding congestion in a network does not cause any adverse effect.

In RED, packets to be discarded are selected at random in order to equalize the bandwidth used. Therefore, in each TCP connection, the number of discarded packets increases in proportion to the used bandwidth.

Further, in RED, since packets are discarded at random, as a result, the interval between packets to be discarded is randomly selected.

(Overview of IP over ATM)
In the RED congestion control device and method according to the present invention, the communication mode is the IP over ATM system.
In the IP over ATM method, AAL5 is a protocol that is assumed for computer communication as a main application. This aims at simplifying ATM communication by omitting advanced additional functions such as ATM cell loss compensation and delay fluctuation compensation as much as possible.

Here, as a feature of AAL5, since the packet is assembled on the transmission side and the reception side (end / end) in communication, the end node has one of a plurality of cells constituting one packet. That is, it is possible to easily determine the last cell and cells other than the last cell.

In a relay switching node (relay ATM node) in ATM communication, an ATM flowing through one VC
By continuously monitoring cells, a plurality of cells constituting a packet obtained by decomposing a certain ATM cell can be distinguished in detail as a first cell, a last cell, and an intermediate cell (a cell other than the first cell and the last cell).

Here, in the packet discarding by the IP over ATM method, there are the EPD method and the PPD method. Both of them discard a cell which cannot be processed at the time of occurrence of congestion when all the ATM cells constituting one packet are discarded. It is intended to be disposed of. Therefore, when cells constituting a packet are selectively discarded, discarding the cells completely at random results in a large number of packets being discarded, resulting in a large number of retransmitted packets from the upper layer (TCP). This is for avoiding the deterioration of the congestion state caused by the congestion.

Therefore, RED is simply expressed as IP over ATM
If a packet is randomly discarded by applying the method described above, there arises a problem that a processing amount increases. this is,
This is because the RED starts operating when the usage rate is low, and is considered to be operating at all times. Therefore, when the processing amount is large, the overhead increases. This is an ATM switch that accommodates ultra-high-speed lines.
This is a more prominent problem.

The reason why the amount of processing increases as described above is that the following two different levels of processing are performed.

First, as the first processing, the relay ATM
This is a process of monitoring all cells passing through the node and determining the next discarded packet. As the second process,
This is a process of discarding a packet in VC units. The second process is a process of discarding all ATM cells constituting the packet next to the VC determined in the first process, and the ratio occupied by this process is large as a cause of an increase in the processing amount.

(Characteristics of the Present Invention) Accordingly, the present invention reduces the processing amount of the relay ATM node (ATM switch) by delegating the entire packet to the end AAL5.

That is, the ATM switch is used for a non-final AT.
When one M cell is discarded, the discard of the packet including the ATM cell is delegated to the end AAL5. Also, AT
The probability of discarding M cells is obtained from (average number of cells / packet) and the packet discard rate. Further, cells other than the last cell are discarded at random cell intervals in accordance with the discard probability.

Thus, in the apparatus and method for avoiding congestion by RED according to the present invention, the RED does not operate when congestion occurs, but discards packets at a low discard rate when the average resource usage rate becomes high to some extent. This operation causes unnecessary cells to flow on the line as compared with the conventional method of discarding all cells constituting one packet. However, the influence of this is small and the occurrence of congestion is efficiently prevented. To make things possible.

Accordingly, the apparatus and method for avoiding congestion by RED according to the present invention do not discard all ATM cells constituting one packet, but a plurality of ATM cells obtained by decomposing one packet at random cell intervals. Of which
It is characterized in that an ATM cell that is not the last cell (hereinafter, abbreviated as an intermediate cell) is discarded.

For this reason, at the start of the processing, first, the interval (cell interval) between the cell to be discarded and the cell to be discarded next is obtained, and then the intermediate cell arriving first after the obtained cell interval is separated. Discard the cell.

The cell interval between the cell to be discarded and the cell to be discarded next is obtained by calculation from the minimum value 0, the average number of cells required to transfer one packet, and the packet discard rate according to the congestion level. It is determined by randomly selecting from the cell interval with the maximum value. The method for calculating the cell interval will be described in detail below.

Also, by discarding the intermediate cell, the end (packet receiving side) at the end (AT side)
In the process of assembling a packet from M cells, this 1
The control by the AAL5 is used to detect whether the number of cells constituting a packet is insufficient or not, and to execute a process of discarding the packet if the number is insufficient.

Therefore, only by discarding the intermediate cell, it is possible to obtain the same congestion avoidance effect as discarding one packet.

In the case of discarding the last cell which has been a problem in the prior art, in the prior art, the receiving side includes a part excluding the last cell of the first packet and a cell obtained by disassembling the second packet. Are combined into one packet, an excessive number of cells constituting one packet is detected, and the completely received second packet is also discarded in addition to the first packet to be discarded. In contrast, the RED congestion avoidance apparatus and method according to the present invention solves such a problem by selectively discarding the intermediate cell instead of the final cell. Becomes possible.

Further, in the apparatus and method for avoiding congestion by RED according to the present invention, discarding an ATM cell other than an intermediate cell is performed to start discarding a packet (or setting a congestion indication) when a sign of congestion is found. Instead, by performing normal control, it is possible to avoid retransmission of completely received packets. Therefore, it is possible to prevent network congestion from further worsening.

(First Embodiment) A first embodiment of an apparatus and method for avoiding congestion by RED according to the present invention will be described in detail with reference to the drawings.

FIG. 1 is a block diagram showing the structure of an ATM switch (transit switching node). In FIG. 1,
The ATM switch has, as its main configuration, a line corresponding unit.
2. From 1 It is composed of N line corresponding units up to N and a switch unit 2.

In FIG. 1, an ATM cell received from a line is sent to a line-corresponding unit corresponding to a line to be transmitted via a switch unit 2.

FIG. 2 is a block diagram showing a configuration of line corresponding unit 3 shown in FIG. In FIG. 2, the line correspondence unit 3 includes a line control unit 21 and a reception unit 2 as its main components.
2 and a transmission unit 23.

In FIG. 2, the ATM cell received from the line is sent to the switch unit 2 via the line control unit 21 and the receiving unit 22. Also, A received from the switch unit 2
The TM cell is sent to the switch unit via the transmission unit 23 and the line control unit 21.

Here, the present invention relates to the function of the transmitting section 23 in the line corresponding section 3 shown in FIGS. 1 and 2.

Referring to FIG. 3, FIG. 3 is a block diagram showing the configuration of the transmitting section 23 shown in FIG. 2, and has functions and data necessary for explaining the (first embodiment) of the present invention. It is configured. FIG. 3 shows only a configuration necessary for describing the first embodiment of the present invention.

In FIG. 3, the ATM cell received from the switch unit 2 is discarded by the cell discard judgment unit 43, or it is judged whether it is connected to the transmission queue 31. Here, the transmission waiting queue 31 is a waiting queue until a cell can be transmitted via the line control unit 21.

The average queue length monitoring unit 4 in FIG.
Reference numeral 1 has a function of monitoring the average queue length of the transmission queue 31 for each reference time.

Further, the congestion state judging section 42 uses its own ATM switch 1 based on the output of the average queue length monitoring section 41.
Has a function of determining whether or not congestion has occurred or whether or not the congestion state has been resolved.

As a method of determining the congestion state at this time, a threshold value is provided for the queue length detected by the average queue length monitoring unit 41, and whether or not the detected average queue length exceeds the threshold value is determined. Is used to determine the occurrence of congestion.

Further, the congestion state determination unit 42 can determine the level of the congestion state stepwise by having the above-described threshold value in a plurality of levels.

The data shown in FIG. 3 is data used by the cell discarding judging section 43 to judge whether or not to discard the received cell.

The pseudo-random number table 51 is a table composed of 2 K powers of data, in which 2 K powers from 0 to (2 K powers) −1 are stored at random. ing.

Further, a pseudorandom table index 5
2 is data storing an index for indexing the pseudo-random number table 51, and every time this value is referred to, 1 is stored.
Is a cyclic counter.

The shift bit number data 53 is data set when the congestion state determination unit 42 determines that the ATM switch 1 is in the congestion state. After discarding one ATM cell, the maximum number of cells not discarded until the next ATM cell to be discarded is ｛(2 to the power of L) −
When 1｝ is set, the congestion determination unit 42 sets (L−
K) is set.

Therefore, by shifting the obtained pseudo random number value to the right by the value of the shift bit number data 53 (division by a power of 2), the cell interval to the next discarded cell can be obtained.

The processing for determining the cell interval will be described in more detail. First, the packet discard rate corresponding to the congestion state level determined by the congestion state determination unit and the average number of cells into which one packet is divided are shown. The cell discard rate is obtained by
Power). Based on the specified value of 2 to the power of n, pseudorandom numbers of equal probability are generated in the range of 0 to (2 to the power of (n + 1)). Therefore, by referring to this pseudo random number table, the interval to the next cell to be discarded is specified.

The discard cell interval obtained as described above is temporarily stored in the discard cell counter 54. Therefore,
The cell discard determination unit 43 refers to the value of the discard cell counter 54 every time an ATM cell is received, and
It is determined whether to discard the TM cell.

The congestion state data 55 is data for setting a value corresponding to expressing the congestion state numerically when the congestion state determination unit 42 detects the start and end of the congestion. This numerical expression expresses the degree of the congestion state by setting the level of the congestion state for each queue length waiting for transmission.

Therefore, by changing the probability of discarding cells according to this level, it is possible to avoid congestion according to the congestion state. Similarly, it becomes possible to notify each transmitting node of the congestion state according to the congestion state.

Although the configuration in the first embodiment has been described in detail, the average queue length monitoring unit 41 shown in FIG.
Since the congestion state determination unit 42 is not directly related to the present invention, detailed processing is omitted.

Next, the operation of the cell discard determination unit 43 in the congestion state will be described in detail with reference to FIG.

[0097] In FIG.
When the M cell arrives, the cell reception is determined in step S61. If a cell has been received, step S
At 62, a process of determining the value of the discard cell counter 54 is executed.

If the value of the discarded cell counter 54 is not 0, the value of the discarded cell counter 54 is decremented by 1 in step S66, and then the received AT is discarded in step S67.
Execute a process of registering the M cell in the transmission queue 31;
Thereafter, the process returns to step S61.

If the value of the discard cell counter 54 is 0, the value of the last bit defined by AAL5 is 0, that is, OFF, by referring to the value of the ATM header of the received cell in step S63. Whether or not the received cell is the last cell is determined depending on whether or not the received cell is the last cell.

If the value of the ATM header of the received cell is not off, then in step S67 the received ATM
A process for registering the cell in the transmission waiting queue is performed, and thereafter, the process returns to step S61.

Further, when the value of the ATM header of the received cell is off, the received ATM cell is discarded in step S64, a discarded cell counter updating process is executed in step S65, and the process returns to step S61.

Next, the updating process of the discarded cell counter shown in step S65 of FIG. 4 will be described in detail with reference to FIG.

First, in step S71, 1 is added to the value of the pseudo random number table index 52 and stored.

Next, in step S72, the value of the pseudo random number is obtained by indexing the pseudo random number table 51 with the value of the pseudo random number table index 52. Further, a value obtained by shifting the value of the pseudorandom number to the right by the value of the shift bit number data 53 is stored in the discard cell counter 54, and the process ends.

As described above, in the first embodiment, since the cell received by the transit switching node is determined to be an intermediate cell or not, it is determined whether or not the cell can be discarded. Extremely low throughput.

Further, in the first embodiment, 1
Since the discarded cells are determined by collecting all the received cells flowing on one line, the ATM cell headers are respectively separately focused on all VCs in order to discard the entire packet as in the packet discarding process by the EPD method. No need to monitor.

Accordingly, it is also possible to avoid performing the processing for each VC and the processing for the entire integrated VC jointly.

In the first embodiment, all connections are handled as IP over ATM. However, by adding service class determination processing for each VC, IP over A
Since the UBR is used in the TM system and other than the UBR can be used in other ATM communication,
It is also possible to apply to a mode in which communication using IP over ATM and communication of another type are mixed and used.

(Other Embodiments) In the first embodiment, an embodiment in which an ATM switch is applied has been described. However, IP over ATM traffic of other AAL5 such as a host network interface card for ATM, etc. Can be applied to the device for processing congestion by RED according to the present invention.

[0110]

As described above, the RE according to the present invention
According to the congestion avoiding apparatus and the method thereof according to D, the following unique effects of the present invention can be obtained.

First, as a first effect, since only one intermediate cell is selected and discarded, it is possible to notify the application of the packet discarding with less processing than the packet discarding method by the EPD method. Becomes

The reason is that it is possible to reduce a large number of processes required for discarding all cells constituting one packet in the discarding process by the EPD method.

The second effect is that since only one intermediate cell is discarded from the entire aggregated flow, RED is processed with less processing than the packet discarding method using the EPD method. Can be realized.

The reason is that it is possible to reduce the processing for discarding all cells constituting one packet for each VC in the packet discarding method based on the EPD method.

Further, the congestion avoidance by RED does not operate when congestion occurs, but discards packets at a low discard rate when the average resource usage rate becomes high to some extent, so that all cells constituting one packet are discarded. Although unnecessary cells flow on the line as compared with the conventional method, the influence of this is small, and it is possible to efficiently avoid the occurrence of congestion.

[Brief description of the drawings]

FIG. 1 is a block diagram showing a configuration of an ATM switch (transit switching node).

FIG. 2 is a block diagram showing a configuration of a line corresponding unit 3 shown in FIG.

FIG. 3 is a block diagram showing a configuration of a transmission unit 23 shown in FIG. 2, which has functions and data necessary for describing the first embodiment of the present invention.

FIG. 4 is a flowchart illustrating an operation of the cell discard determination unit 43 in a congestion state.

FIG. 5 is a flowchart showing a discarded cell counter updating process shown in step S65 of FIG. 4;

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 ATM switch 2 Switch part 3.1-3.n Line correspondence part 21 Line control part 22 Receiving part 23 Transmitting part 31 Transmission queue 41 Average queue length monitoring part 42 Congestion judging part 43 Cell discard judging part 51 Pseudo random number table 52 Pseudo random number table index 53 Shift bit number data 54 Discarded cell counter 55 Congestion state data

Claims (16)

[Claims] An apparatus for avoiding congestion by RED in a network to which AAL5 is applied as a protocol, comprising: cell discarding means for specifying cells other than the last cell based on a cell interval calculated with a predetermined probability and discarding the cells. A congestion avoidance device based on RED. 2. An apparatus for avoiding congestion by RED in a network to which AAL5 is applied as a protocol, comprising: buffering means for temporarily holding cells received from a line; and calculating a queue length of cells held by the buffering means. Queue length monitoring means, based on the queue length calculated by the queue length monitoring means,
Congestion state determination means for determining occurrence of a congestion state; and final cell determination means for determining whether or not the arriving cell is the last cell when the occurrence of the congestion state is determined by the congestion state determination means. A cell discarding means for identifying and discarding, based on a cell interval calculated by a predetermined probability, when the arriving cell is determined not to be the last cell by the last cell judging means. Congestion avoidance device. 3. The queue length monitoring unit detects a queue length in the buffering unit at predetermined time intervals, and calculates an average queue length including the latest queue length based on the detected queue length. 3. The apparatus according to claim 2, wherein the calculation calculates a queue length of a cell held by the buffering unit. 4. The last cell judging means, wherein the cell has a last bit in a header part constituting the cell, the last bit indicating whether the cell is the last cell among cells constituting the same packet, Is based on the last bit included in the header of the cell,
4. The congestion avoidance device according to claim 2, wherein it is determined whether the cell is the last cell. 5. A queue length storage unit for storing a predetermined queue length as a threshold value, wherein the congestion state determination unit stores the queue length calculated by the queue length monitoring unit and the queue length storage unit. The RE according to any one of claims 2 to 4, wherein the occurrence of congestion is determined by comparing the stored queue length with the predetermined queue length.
Congestion avoidance device by D. 6. A queue length congestion level storage unit that stores a plurality of predetermined queue lengths as different threshold values with different values, and further stores a congestion state level corresponding to the plurality of the predetermined queue lengths, The congestion determination unit compares the queue length calculated by the queue length monitoring unit with the plurality of predetermined queue lengths stored in the queue length congestion level storage unit, and as a result of the comparison, Identify the congestion level corresponding to the predetermined queue length that is the largest value among the predetermined queue lengths exceeding the queue length calculated by the queue length monitoring means, and determine the occurrence of congestion in a stepwise manner. 5. The congestion avoidance device using RED according to claim 2, wherein: 7. The predetermined probability is calculated based on an average number of cells into which one packet is divided and a packet discard rate corresponding to the level of the congestion state. 1 / power of 2 which can approximate the probability of
Is calculated, and based on the value of the power of 2, a pseudo-random number of equal probability is created in a range from 0 to twice the value of the power of 2,
7. The method according to claim 1, wherein the cell discarding unit discards the specified cell if the cell specified by the cell interval is not the last cell. 5. A congestion avoidance device using RED according to claim 1. 8. The congestion avoidance device using RED according to claim 1, wherein the network to which AAL5 is applied as the protocol is a network employing an IP over ATM system. 9. A method for avoiding congestion by RED in a network to which AAL5 is applied as a protocol, comprising a cell discarding step of identifying and discarding cells other than the last cell based on a cell interval calculated with a predetermined probability. A congestion avoidance method using RED. 10. A method for avoiding congestion by RED in a network to which AAL5 is applied as a protocol, comprising: a buffering step of temporarily holding cells received from a line; and calculating a queue length of the cells held in the buffering step. A queue length monitoring step, a congestion state determination step of determining the occurrence of a congestion state based on the queue length calculated in the queue length monitoring step, and a case where the occurrence of a congestion state is determined in the congestion state determination step. A final cell determining step of determining whether or not the arriving cell is the last cell; and a cell calculated by a predetermined probability when it is determined in the final cell determining step that the arriving cell is not the last cell. A method of discarding congestion by RED, comprising a step of discarding cells based on intervals and discarding them. 11. The queue length monitoring step includes detecting a queue length in the buffering means at predetermined time intervals, and calculating an average queue length including the latest queue length based on the detected queue length. 11. The congestion avoidance method by RED according to claim 10, wherein the calculation calculates a queue length of a cell held by the buffering means. 12. The final cell determination step, wherein the cell has a final bit indicating whether or not the cell is the last cell among cells configuring the same packet in a header portion configuring the cell. Is based on the last bit included in the header of the cell,
The method according to claim 10 or 11, wherein it is determined whether or not the cell is the last cell. 13. A queue length storing step of storing a predetermined queue length as a threshold value, wherein the congestion state determining step includes the queue length calculated in the queue length monitoring step and the queue length storing step. 13. The congestion avoidance method according to claim 10, wherein the occurrence of congestion is determined by comparing the stored queue length with the predetermined queue length. 14. The congestion determining step compares the queue length calculated in the queue length monitoring step with a plurality of queue lengths stored such that a plurality of congestion state levels correspond to each other, As a result of the comparison, the congestion level corresponding to the predetermined queue length which is the largest value among the predetermined queue lengths exceeding the queue length calculated by the queue length monitoring means is specified, and 13. The method according to claim 10, wherein the occurrence of congestion is determined. 15. The predetermined probability is calculated based on an average number of cells into which one packet is divided and a packet loss rate corresponding to the level of the congestion state. 1 / power of 2 which can approximate the probability of
Is calculated, and based on the value of the power of 2, a pseudo-random number of equal probability is created in a range from 0 to twice the value of the power of 2,
The method according to claim 9, wherein the identification is performed based on the pseudorandom number, and the cell discarding step discards the specified cell if the cell specified based on the cell interval is not the last cell. A congestion avoidance method using RED according to any of the above. 16. The network to which AAL5 is applied as the protocol is a network employing an IP over ATM system.
A method for avoiding congestion by RED according to any one of the above.