JPH08237282A - Priority controller, congestion controlling method and congestion controller for atm cell - Google Patents

Abstract

PURPOSE: To improve the performance of a congestion controller in a packet communication system such as an ATM communication system, etc. CONSTITUTION: One of, at least, the number of ATM cells accumulated in a buffer device 2, the number of the ATM cells rejected by an ATM cell rejecting device 1, the number of the ATM cells having arrived at the ATM cell rejecting device 1, and the number of the ATM cells rejected by the instruction of the ATM cell rejecting device 1 is observed, and buffer state data is obtained. A buffer state statistical device 3 updates successively its statistic on the basis of this buffer state data, and outputs it as buffer state statistical data. The ATM cell rejecting device 1 changes a criterion when rejecting the ATM cell having arrived or the ATM cell in the buffer device 2 on the basis of one of, at least, various kinds of information related to the buffer state statistical data, the arriving process of the ATM cell from a terminal and the connection state of a cell.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a congestion control method and a congestion control device in an ATM communication system and a packet communication system for communicating and storing information using cells and packets.

Further, the present invention relates to an ATM cell priority control system in an ATM multiplexer and an ATM switch.

[0003]

2. Description of the Related Art Call admission control, priority control, and flow control are examples of congestion control in packet communication systems such as ATM communication systems.

The priority control compares the number of cells in the buffer device with a certain threshold value, and when the number of cells in the buffer device exceeds the threshold value, a threshold value method for restricting input of low priority cells, When a high-priority cell arrives while the buffer device is full, the low-priority cell in the buffer device is discarded and the arrived high-priority cell is put into the buffer device.

The former is relatively easy to realize and can guarantee the worst cell loss rate of high priority cells, no matter how much the load of low priority cells increases, but the actual cell loss rate obtained is There is a drawback in that it is greatly affected by load fluctuations of low priority cells. In addition, the latter cell loss rate of high-priority cells is less susceptible to load fluctuations of low-priority cells, but guarantees the worst cell loss rate of high-priority cells when the load of low-priority cells is excessively concentrated. There is a drawback that you cannot do it.

The call admission control is a control for limiting the connection of calls so that the actual communication quality does not deteriorate below the required communication quality. The expected communication quality when it is assumed that a new call is connected is estimated using the reported parameters and the observed cell arrival rate. However, in general, it is difficult to predict the traffic of cells arriving at the buffer because the cells do not always arrive according to the declared parameters and the traffic may be transformed by the CDV. Therefore, it is difficult to accurately estimate the communication quality.

As a conventional flow control technique, the line congestion is judged by comparing the queue length of a buffer on the input side of the line with a threshold value, and the cell generation amount of the connection connected to the buffer is determined. There is a regulation method. However, as described in the description of the prior art of call admission control, it is difficult to predict the traffic of cells arriving at the buffer. Therefore, this method has a problem that the threshold value for detecting congestion cannot be set accurately.

[0008]

As described above, in the priority control, in the threshold control method and the push-out method, when the load of the low priority ATM cells is increased, the communication quality of the high priority ATM cells is significantly deteriorated. Resulting in. Therefore, in order to guarantee the communication quality of the high-priority ATM cell, it is necessary to reduce the call multiplicity in advance in consideration of the fluctuation of the load of the low-priority ATM cell, which results in efficient use of network resources. There was a problem that I could not do it.

Further, in congestion control such as priority control, call admission control, and flow control, as described in the prior art, the prediction of cell traffic does not always mean that cells arrive according to the declared parameters. Since it is difficult to change due to reasons such as deformation, it is necessary to safely estimate the number of call connections in the thresholds for priority control and flow control and call admission control in order to protect communication quality. There was a problem that network resources could not be utilized.

Therefore, the ATM cell priority control apparatus of the present invention has been made in view of these problems.
It is an object of the present invention to provide an ATM cell priority control apparatus in which communication quality is not affected by fluctuations in input traffic and a higher multiplicity is obtained than in the conventional method.

A further object of the present invention is to provide a congestion control method and a congestion control apparatus using the congestion control method, in which the communication quality is not affected by fluctuations in input traffic and a higher multiplicity is obtained than in the conventional method. To do.

[0012]

In order to achieve the above object, an ATM cell priority control apparatus of the present invention comprises at least one buffer means for accumulating ATM cells, an ATM cell before accumulating, and the buffer. ATM cell discarding means for discarding the ATM cells in the means based on a predetermined discrimination standard, the number of ATM cells accumulated in the buffer means, and the ATM cells discarded by the ATM cell discarding means
The number of cells, the number of ATM cells arriving at the ATM cell discarding means, and the A discarded according to the instruction of the ATM cell discarding means
A buffer state observing means for observing at least one of the number of TM cells and outputting the data obtained by the observation as buffer state data, and a statistic amount of the buffer state observing means while receiving the buffer state data from the buffer state observing means. Is sequentially updated and is output as buffer state statistical data, the ATM cell discarding means is based on at least the buffer state statistical data obtained from the buffer state statistical means, and the discrimination criterion. Change.

Further, the congestion control device of the present invention is provided with at least one buffer means for accumulating packets transferred from a plurality of terminals, and performs congestion control of a packet communication system for accumulating and exchanging packets from the terminals. In the congestion control device, the number of packets arriving at the buffer means, the number of packets accumulated in the buffer means, the communication quality of the packet communication system, a declaration parameter indicating a packet output process at the terminal, and a required quality for communication quality Based on the system state observing statistical means for observing at least any one of the above and outputting the statistic of the data obtained by the observation as the system state statistic. To estimate the arrival characteristics of the packet from the terminal to the buffer means. Means, the packet arrival characteristic estimated by the estimating means, and a predetermined discrimination criterion based on the system state statistic, and discarding the packet before being accumulated or the packet in the buffer means, and the packet output of the terminal. The communication quality is not affected by the fluctuation of the input traffic, and the communication quality is optimized by providing the determining means for determining at least one of the speed regulation and the connection rejection when a new call connection request is made. The flow rate of the cell can be controlled and thus a higher multiplicity is obtained than in the conventional method.

Further, by updating the packet arrival characteristics so as to reduce the difference between the system state statistics estimated based on the packet arrival characteristics and the statistics of the data obtained by the observation, the packet arrival characteristics are updated. The packet arrival characteristic can be obtained with high accuracy by correcting the arrival characteristic (cell arrival parameter) and the actual cell arrival process so that the error is small.

Further, the determining means sets the discrimination criterion so as to minimize the difference between the required communication quality and the communication quality of the communication system estimated from the arrival characteristics of the packet and the system state statistics. By setting it, it becomes possible to perform highly accurate congestion control.

That is, a control signal for controlling the packet communication system is determined from the communication quality estimated with high accuracy using the packet arrival characteristics (cell arrival parameters) estimated with high accuracy and the system state statistics based on the observation data. The calculation enables highly accurate congestion control.

[0017]

BEST MODE FOR CARRYING OUT THE INVENTION Embodiments of the present invention will be described below in detail with reference to the drawings. First, the outline of the present embodiment will be described.

In this embodiment, the buffer state statistic device obtains statistical information about the number of ATM cells in the buffer called the in-system number observed by the buffer state observing device, the number of discarded ATM cells, and the number of arriving ATM cells. Then, from the system data, the ATM cell discard device discards the ATM cells of the lower priority class among the ATM cells that have arrived. Also, the ATM cell in the buffer device is discarded according to a command from the ATM cell discard device.

That is, in the present embodiment, the past ATM cell discard rate is estimated from the past statistical information of the number of cells in the system, the number of discarded ATM cells, and the number of arrived ATM cells. Further, the future ATM cell discard rate is estimated from the statistical information and the declared parameters. If the high-priority ATM cell discard rate in the past is high, or if the high-priority ATM cell discard rate is expected to increase in the future, the input restriction of the low-priority ATM cells is strengthened or the buffer in the buffer is strengthened. Low priority ATM
ATM of high priority ATM cells by discarding cells
The cell discard rate is controlled so as to satisfy the specified value. If this is not the case, the throughput of low-priority ATM cells is secured by relaxing the input restriction of low-priority ATM cells.

As described above, by flexibly discarding the ATM cells of the lower priority class in accordance with the statistical information of the number of ATM cells in the system, the number of discarded ATM cells and the number of arrived ATM cells, and the status of the declared parameters, , Regardless of fluctuations in the number of input ATM cells, while ensuring the throughput of low-priority ATM cells as much as possible, high-priority class ATM
The cell disposal rate can be stabilized.

FIG. 1 is a block diagram of a multiplexer or an ATM cell storage device to which the present invention is applied, which is used when an ATM cell classified into L types of priority classes is multiplexed.
It has a function of performing priority control on the M cell discard rate. This device has one or more buffer devices 2 for storing ATM cells, the number of ATM cells stored in the buffer device 2 called the system number, and the number of ATM cells to be stored in the buffer device 2. , The number of ATM cells discarded because there is no area for accumulating ATM cells in the buffer device 2, the number of ATM cells that have arrived at the ATM cell discard device described later, and the ATM cells discarded according to the instruction of the ATM cell discard device described later A buffer state observing device 4 that observes at least one of the numbers and outputs it as buffer state data, and updates the buffer state data statistic each time the buffer state data is sent from the buffer state observing device 4. And a buffer state statistical device 3 for outputting the data as buffer state statistical data, and the buffer state statistical device 3 Ffa state statistics, A from the terminal
An ATM cell discarding device 1 that discards the arriving ATM cell or the ATM cell in the buffer device 2 based on a predetermined discrimination criterion from at least one of the information regarding the arrival process of the TM cell and the connection status of the call. It has.

FIG. 2 is a diagram showing the configuration of the ATM cell discarding device 1. At least buffer state statistical data obtained from the buffer state statistical device 3 and at least information regarding the arrival process of ATM cells from terminals and the connection state of calls. From any one, the ATM cell discard determination device 6 for calculating the regulation rate for each class and the class of the arriving ATM cell are determined,
According to the regulation rate for each class calculated by the ATM cell discard determination device 6, the buffer device 2 of the arriving ATM cells 2
The ATM cell input regulation device 5 for regulating the transfer to the ATM cell.

This ATM cell input regulation device 5 is an ATM
When the cell priority classes are 0, 1, ..., L, ..., L-1, the arriving ATM cells are buffered according to the regulation rate of each class obtained from the ATM cell discard determining device 6. Transfer to device 2. For example, when a class 1 ATM cell arrives and the class 1 regulation rate is 100%, the ATM cell is discarded on the spot and is not transferred to the buffer device 2. The class 1 regulation rate is 0%. In that case A
The TM cell is transferred to the buffer device 2. When the regulation rate of class l is r%, for example, it waits until n number of class 1 ATM cells arrive, discards [n × r ÷ 100], and transfers the rest to the buffer device 2. Where [x]
Takes a value obtained by rounding x.

FIG. 3 is a diagram showing another configuration of the ATM cell discarding device 1. Buffer state statistical data obtained from the buffer state statistical device 3, information about arrival process of ATM cells from terminals and call connection state. From at least one of the above, the regulation rate for each class and the address in the buffer of the ATM cell in the buffer device 2 to be discarded are calculated A
The ATM cell regulation rate / discarded address arithmetic unit 8 and the class of the arriving ATM cell are discriminated, and the buffer of the arriving ATM cells is buffered according to the regulation rate for each class calculated by the ATM cell regulation rate / discarded address arithmetic unit 8. An ATM cell input regulation device 5 that regulates transfer to the device 2 and an in-buffer ATM cell discard device 7 that discards the ATM cell of the address calculated by the ATM cell regulation rate / discarded address calculation device 8.

FIG. 4 is a diagram showing the configuration of the ATM cell discard judging device 6, which is a call connection state storage device 11 for storing information about the arrival process of ATM cells from terminals and call connection conditions, and the buffer. The threshold value for each class is calculated from the buffer status statistical data obtained from the status statistical device 3 and the information about the arrival process of ATM cells from terminals and the call connection status stored in the call connection status storage device 11. By comparing the threshold value calculated by the threshold value calculation device 10 with either the in-system number of each class or the sum of the in-system numbers of all classes. It comprises a threshold value comparison device 9 which determines whether or not to restrict the input of the ATM cell to the buffer device 2.

FIG. 5 is a diagram showing another configuration of the ATM cell discard judging device 6, which is a call connection state storage device 11 for storing information about the arrival process of ATM cells from terminals and the connection state of calls. The buffer status statistical data obtained from the buffer status statistical device 3 and the call connection status storage device 11
The regulation rate calculation for calculating the regulation rate for regulating the input of the arriving ATM cell to the buffer device for each class from the information about the arrival process of the ATM cell from the terminal and the call connection state stored in And device 12.

In the threshold value comparing device 9 shown in FIG. 4, the threshold value tl of the class l given from the threshold value setting device.
And by comparing the number of ATM cells in the buffer device,

[Equation 1]

An embodiment of the call connection status storage device 11 shown in FIG. 4 or 5 is shown in FIG. Call connection status storage device 1
1 is a call connection state quantizer 33 that quantizes an ATM cell arrival process from a terminal or a current call connection state, and a table ID that stores an ID number of a control table corresponding to the quantized call connection state. It is composed of a register 34. The table ID register 34 stores the table ID in a storage area having the quantized call connection state as an address, and outputs the table ID number corresponding to the call connection state.

As the information indicating the arrival process of the ATM cell from the terminal, the declared parameter of the terminal can be used, and the number of calls classified by the declared parameter as the current call connection state can be used.

An embodiment of the threshold value calculating device 10 shown in FIG. 4 is shown in FIG. In the threshold value calculation device 10, m3 AT
In the buffer device 2 obtained from the call state storage device 11 and the table ID obtained from the call connection state storage device 11 every time M cells arrive, every m3 ATM cell slot, or every time the call connection state changes. ATM
The encoder 30 converts the statistical information regarding the number of cells, the number of ATM cells arriving at the ATM cell input regulation device 5, and the number of discarded ATM cells into the address of the control data RAM 32. A threshold value for each address is written in the control data RAM 32, and the selector 31 reads this threshold value at the beginning of the ATM cell slot and transfers it to the threshold value comparison device 9.

The configuration of the regulation rate calculation device 12 shown in FIG.
It has the same configuration as the threshold value calculation device 10 shown in FIG.
However, in the control data RAM 32, not the threshold value but the regulation rate is written for each address.

In the case of having a plurality of buffer devices, priority control can be performed by using the buffer status observing device 4, the buffer status statistical device 3, and the ATM cell discarding device 1 in a time division manner. However, as many data storage devices as the data RAM 27, the control data RAM 32, the counter, etc., are required to store data.

Further, the threshold value calculating device 10 shown in FIG.
Alternatively, the regulation rate calculating device 12 shown in FIG. 5 may be configured by using a CPU, and the threshold value and the regulation rate may be calculated by a program of the CPU.

FIG. 6 is a diagram showing another configuration of the ATM cell discard determining device 6, which calculates a threshold value for each class from the buffer state statistical data obtained from the buffer state statistical device 3. By comparing the threshold value calculated by the threshold value calculation device 10 with either the device 10 or the in-system number of each class or the sum of the in-system numbers of all classes, The buffer device 2 comprises a threshold value comparing device 9 for determining whether or not to restrict the input.

FIG. 7 is a diagram showing the structure of the buffer state observing device 4, in which the information regarding the number of systems in the buffer device 2 is observed for each 1 ATM cell slot, and the observed information is m
The in-system number observing device 13 that collectively transfers to the buffer status statistical device 3 for each 1QATM cell slot, and the ATM that arrives at the ATM cell discarding device 1 within one ATM cell slot
An ATM cell arrival number observing device 13 for observing information on the number of cells for each 1 ATM cell slot and transferring the observed information for each m 1 ATM cell slot to the buffer status statistical device 3, the buffer device 2, and the ATM cell ATs discarded in 1 ATM cell slot by discarding device 1
An ATM cell discard number observing device 15 is provided for observing information regarding the number of M cells for each 1 ATM cell slot, and collecting the information for each m 1 LATM cell slot and transferring it to the buffer state statistics device 3. However, the buffer state observing device 4 may include at least one of the devices 13, 14, and 15 described above.

FIG. 8 is a diagram showing the configuration of the buffer state statistics device 3, and a system for updating the statistics of the system number data each time the system number data is sent from the system number observation device 14. Internal number statistical device 16 and ATM cell arrival number observing device 1
Every time the ATM cell arrival number data is sent from 3,
ATM cell arrival number statistics device 17 for updating statistics of ATM cell arrival number data, and ATM cell discard number observation device 1
Every time the ATM cell discard number data is sent from 5,
An ATM cell discard number statistics device 18 for updating the statistics of the ATM cell discard number data. However, the buffer status statistics device 3 may include at least one of the devices 16, 17, and 18 described above according to the configuration of the buffer status determination device.

Here, the ATM cells are 0, 1, ..., L-
When there are a total of L priority classes of 1, the system factor observation device 14 observes the system factors of each class. System factor observation device # 0 System factor observation device # 1: System factor observation L observation devices of device # L-1 or L2 observation devices that classify L types of classes into L2 types and observe the sum of the system numbers of the classified classes. In-system number observation device # f1: consists of either in-system number observation device # fL2-1.

The ATM cell arrival number observation device 13
Is an ATM cell arrival number observing device # 0 for observing the number of ATM cells arriving for each class. L number observing devices of ATM cell arrival number observing device # 1: ATM cell arrival number observing device # L-1. L2 classifiers that classify L classes into L2 classes and observe the sum of the number of arrivals of ATM cells of the classified classes ATM cell arrival number monitor # f0 ATM cell arrival number monitor # f1: ATM cell One of the arrival number observation devices # fL2-1.

The ATM cell discard number observing device 15
Is an ATM cell discard number observing device # 0 for observing the number of ATM cells arriving for each class, L number of ATM cell discard number observing device # 1: ATM cell discard number observing device # L-1, or L2 classifiers that classify L classes into L2 classes and observe the sum of the number of discarded ATM cells of the classified classes ATM cell discard number monitor # f0 ATM cell discard number monitor # f1: ATM cell It consists of one of the discard number observation devices # fL2-1.

Further, the in-system number statistic device 16 determines, for each class, each time the in-system number data is sent from the in-system number observing device 14 in accordance with the configuration of the in-system number observing device 14. Updating the statistical amount of the in-system number data of, the in-system number statistical device # 0, the in-system number statistical device # 1: consisting of L statistical devices in the in-system number statistical device # L-1 or classified. L2
It is composed of any one of a system number statistical device # f0, a system number statistical device # f1, and a system number statistical device # fL2-1 for updating the statistics of the sum of the system numbers for each class.

Further, the ATM cell arrival number statistical device 17
Depending on the configuration of the ATM cell arrival number observation device 13,
Every time the ATM cell arrival number observation device 13 sends the ATM cell arrival number data, the statistic of the ATM cell arrival number data of the ATM cell for each class is updated. ATM cell arrival number statistical device # 0 ATM Cell arrival number statistic device # 1: consists of L statistic devices of ATM cell arrival number statistic device # L-1, or is classified into L2
An ATM cell arrival number statistical device # f0 ATM cell arrival number statistical device # f1: ATM cell arrival number statistical device # LL2-1 that updates the statistic of the sum of the number of ATM cell arrivals for each class Become.

Also, the ATM cell discard number statistics device 18
Depending on the configuration of the ATM cell discard number observing device 15,
Every time ATM cell discard number data is sent from the ATM cell discard number observing device 15, the statistic of the ATM cell discard number data of the ATM cell of each class is updated. ATM cell discard number statistics device # 0 ATM Cell discard number statistics device # 1: L statistics device of ATM cell discard number statistics device # L-1 or update the statistics of the sum of the discard numbers of ATM cells for each of the classified L2 classes. ATM cell discard number statistics device # f0 ATM cell discard number statistics device # f1: Either ATM cell discard number statistics device # LL2-1.

Further, as shown in FIG. 9, the in-system number observation device #l, the ATM cell arrival number observation device #l, and the ATM cell discard number observation device #l (l = 0, ..., L-1, Or f
0, ..., fL2-1) are each: for each 1 ATM cell slot, a data observing device 20 for observing data such as the in-system number of the corresponding class, the number of ATM cell arrivals, and the number of ATM cell discards; A data counter 21 for obtaining the sum of the data obtained by the data observing device, the data counter 21 being m1Q or m1A or m1L
An ATM cell slot counter 1 (22) that clears for each ATM cell slot; -Reads the value of the data counter 1 immediately before the data counter 21 is cleared and uses it as buffer status data for the ATM cell discard determination device 6 The data transfer device 19 transfers the data to the device.

The in-system number observing device #l, the ATM cell arrival number observing device #l, the ATM cell discarding number observing device #l
l (l = 0, ..., L-1 or f0, ..., fL2-1)
10, where x is the output data of the counter, counter #i (i = 1, 2, ..., M) 24, and x is xi-1 with respect to a predetermined xi. ≤
When x <xi (i = 1, 2, ..., M), a comparator #i (23) for issuing a command to count up the corresponding counter #i (24), and the counter #i (24). Of the ATM cell slot counter 2 (25) for issuing a command for clearing every fixed ATM cell slot period, the in-system statistic device #l, the ATM cell arrival number statistic device #l, and the ATM cell discard number statistic device #l.
According to the configuration of the buffer state observation device 4.

The in-system number observing device #l, the ATM cell arrival number observing device #l, the ATM cell discarding number observing device #l
l (l = 0, ..., L-1 or f0, ..., fL2-1)
When the output data of x is x, as shown in FIG. 11, x is xi-1 ≤
a comparator #i (26) that outputs i when x <xi (i = 1, 2, ..., M); an ATM cell slot counter 3 (28) that indicates the current ATM cell slot number; The number of the ATM cell slot counted by the ATM cell slot counter 3 (28) is stored in the data RAM 2
An address encoder 29 for converting to an address of 7; data RA for writing the output of the comparator #i (26) to an address designated by the address encoder 29
M27 and an in-system number statistics device #l, an ATM cell arrival number statistic device #l, and an ATM cell discard number statistic device #l are provided according to the configuration of the buffer state observing device 4.

The following is a description of the regulation rate calculation procedure when the buffer state statistical apparatus 3 shown in FIG. 10 is used and the regulation rate calculation apparatus 12 shown in FIG. 5 is configured using a CPU with reference to FIG. Here, the data to be observed is only the sum of system numbers of all classes, and m1Q = 1 and L = 2.

[0047]

[Equation 2]

Here, the regulation rate r is calculated as follows.

[0049]

(Equation 3)

[0050]

[Equation 4]

[0051]

(Equation 5)

[0052]

(Equation 6)

[0053]

(Equation 7)

[0054]

(Equation 8)

The class of the ATM cell may be classified by the CLP bit written in the header of the ATM cell in the ATM communication, or VCI or VPI. Also, classes may be divided by a combination of CLP bit, VCI, and VPI.

FIG. 14 is a diagram showing the overall configuration of an embodiment of the priority control apparatus shown in FIG. 4 or 8.

FIG. 15 is a diagram showing the hardware configuration of the common buffer switch. The ATM cells arriving at the switch are multiplexed by the MUX 35 and AT
It is transferred to the M cell discard device 1. The buffer status statistic device 3 obtains statistical data of the number of systems, the number of discarded ATM cells, and the number of arriving ATM cells observed by the buffer status observing device 4. The ATM cell discard device 1 calculates the ATM cell regulation rate from the data of the buffer state statistics device 3, and discards the arrived ATM cell according to the calculated rate. Further, the address of the ATM cell in the buffer device 2 to be discarded is calculated from the data of the buffer state statistical device 3, and the corresponding ATM cell in the buffer device 2 is discarded. The ATM cells that have passed through the ATM cell discard device 1 are stored in the buffer device 2. At that time, the buffer device 2 in which the ATM cell is stored
The physical position within the address is designated by the address management device 37 from the routing tag added to the ATM cell. The address of the ATM cell output from the buffer device 2 is also managed by the address management device 37. The buffer state observation device 4 uses the address management device 37.
To obtain information about the number of systems.

FIG. 16 shows a hardware configuration when priority control is performed by the input buffer.

The ATM cell arriving from the physical layer function 38 is first transferred to the routing tag addition device 40 and added with the routing tag. After that, it is transferred to the ATM cell discard device 1. The buffer status statistic device 3 obtains statistical data of the number of systems, the number of discarded ATM cells, and the number of arriving ATM cells observed by the buffer status observing device 4. ATM
The cell discard device 1 calculates the ATM cell regulation rate from the data of the buffer state statistics device 3 and discards the ATM cells that arrive according to the calculated rate. Also, the buffer status statistics device 3
The address of the ATM cell in the buffer to be discarded is calculated from the data of 1. and the corresponding ATM cell in the buffer device 2 is discarded. The ATM cells that have passed through the ATM cell discard device 1 are stored in the buffer device 2.

As the system number, either the system number of both the buffer in the ATM switch 39 and the buffer device installed on the input side of the ATM switch 39, or the system number of the buffer device is used. Flow control is applied to the buffer device installed from the buffer in the ATM switch 39 to the input side of the switch. When the buffer in the ATM switch becomes full, the buffer device installed to the input side of the switch is controlled. Transfer of ATM cells from the device is suspended.

FIG. 17 is a diagram showing a hardware configuration when priority control is performed by the output buffer. The speed of the inside and the output link of the ATM switch 39 is the same as or higher than the link speed of the physical layer, and ATM cells are accumulated from the buffer device 2 installed on the output side of the ATM switch 39. Buffer device 2 to ATM switch 3
9 is subjected to flow control, and when the buffer device 2 is full, transfer of ATM cells from the ATM switch 39 is temporarily stopped.

ATM output from ATM switch 39
The cell is transferred to the ATM cell discard device 1. The buffer status statistic device 3 obtains statistical data of the number of systems, the number of discarded ATM cells, and the number of arriving ATM cells observed by the buffer status observing device 4. The ATM cell discard device 1 calculates the ATM cell regulation rate from the data of the buffer state statistics device 3 and discards the ATM cells that arrive according to the calculated regulation rate. Further, the address of the ATM cell in the buffer device 2 to be discarded is calculated from the data of the buffer state statistical device 3, and the corresponding ATM cell in the buffer device 2 is discarded. ATM
The ATM cells that have passed through the cell discard device 1 are accumulated in the buffer device 2. ATM output from the buffer device 2
The cell has its routing tag deleted by the routing tag deletion device 41 and transferred to the ATM physical layer function 38.

The following is a simulation result when the buffer state statistical device 3 shown in FIG. 10 is used and the regulation rate calculation device 12 shown in FIG. 5 is configured using a CPU. Here, the data to be observed is only the sum of system numbers of all classes, m1Q = 1, L = 2, and the arrival rate set values of the high priority ATM cell and the low priority ATM cell are λH and λL, respectively. , If the arrival rate of low priority ATM cells is increased by ΔL, the ATM cell discard rate (CLR-
H) and the ATM cell discard rate (CLR-) of low priority ATM cells.
The variation of L) is shown in FIG. The conventional method is an ordinary fixed threshold method. As can be seen from this figure, both show the same performance when the input traffic is the set value, but when the input traffic of the low priority ATM cell increases, the ATM cell discard rate of the high priority ATM cell of this method is the same as that of the conventional method. You can see that it is lower.

Next, the second embodiment will be described.
That is, the congestion control method and the congestion control device 100 will be described.

First, the outline of the second embodiment will be described.

In the ATM communication network, as shown in FIG.
When a terminal 101 outputs a cell passing through the packet communication system 102, it is said that a call passing through the packet communication system 102 is set up from the terminal 101. To set up a call, the terminal also declares a declaration parameter that is characteristic of the occurrence of a cell. Further, in the packet communication system 102, there is a buffer device (buffer device 113) for temporarily accumulating cells, and according to the present invention, the communication quality represented by the cell delay time or the cell discard rate generated in the buffer device. Can be controlled.

Next, terms and variables used in the following description will be described.

It is assumed that the terminal 1 sends out a cell every unit time, each unit time is identified by a sequential number n, and this unit time is called a slot.

In addition, the cell arriving from the terminal 101 has L
Assume that the class priority is added in advance,
The cell class 1 is represented by (0 ≦ l ≦ L−1). Also, the cell arrival parameter of class l is represented by a scalar or vector λ _l . The case where λ _l is a vector is the case where there are multiple types of cell arrival parameters. λ _l is the class and λ _l
According to the method of calculating, it is classified as follows.

Λ _lR ^q : A parameter that represents the characteristics of a cell flow in which cells of class l generated by all terminals connected to the buffer device are superimposed, and is calculated by the system state observation statistical device 105 from only the declared parameters. It

Λ _lE ^s : Estimated value of the cell arrival parameter representing the characteristics of the cell flow in which cells of class l generated by all terminals connected to the buffer device are superimposed, and is estimated by the arrival parameter estimation device 103. It

Λ _lO ^ut : the output of the arrival parameter estimator 103, calculated from λ _lE ^s and λ _lR ^qn _ew .

Λ _lR ^qn _ew : Declaration parameter of the terminal that issued the connection request for the call passing through the buffer device.

The system state representing the state of the packet communication system includes the number of cells of the buffer device 113 in the packet communication system 102, the number of cells arriving at the packet communication system 102 from the terminal 101, and the cell output process at the terminal 101. It comprises at least one of a declaration parameter to be expressed, communication quality in the packet communication system, and required quality for communication quality.

The buffer device in the packet communication system 102 is a FIFO with priority control by FIFO or push-out, or a packet switch having the FIFO, a packet multiplexer, a packet storage device, or
These are networks in which multiple connections are made.

Next, referring to FIG. 20, the congestion control device 10
The configuration of 0 will be described. The congestion control device 100 may be provided for each buffer device or one for a plurality of buffers.

The arrival parameter estimation device 103 calculates the cell arrival parameter λ _lE ^s and the cell arrival parameter λ _lO ^ut . That is, in the arrival parameter estimation device 103, the sum of the arrival rates of the cells of class l declared from the call connected to the buffer device 113 is defined as λ _lR ^q , and the product of this and a certain constant e _l gives a new cell. The arrival parameter λ _lE ^s is estimated from the following equation (1).

Λ _lE ^s = λ _lR ^q × e _l (1) Here, the constant e _l is, for example, when the cell arrival at the buffer device 113 arrives according to Poisson arrival of the average λ _lE ^{s in} each slot. The class l cell loss rate CLR _l in the buffer device 113 can be determined to be equal to the communication quality QOS for the cell loss rate required for class l.

Another method for calculating the cell arrival parameter λ _lE ^s is as follows. That is, at time (n-1), the cell of class l has λ _lE ^s (n-1)
The theoretical value of the average number of cells in the buffer of the buffer device 113 when arriving in accordance with is calculated by q _l− (n−1), and is observed at the head of the cell slot in the statistic calculated by the system state observation statistic device 105. Number of cells in buffer k _l (n)
Statistic s _l- (n) calculated from equation (7) described later is k _l- (n), and λ _lE ^s (n) = λ _lE ^s (n-1) × k _l- (n ) / Q _l− (n−1) λ _lE ^s (0) = λ _lR ^q (2). q _l− (n−1) can be calculated by the same method as the communication quality estimation apparatus 109 described later.
λ _lR ^q can be the sum of the arrival rates of class l cells declared from the calls currently connected to the buffer device 113.

Furthermore, the following is another method of calculating the cell arrival parameter λ _lE ^s . That is, first, when n = 0, calculation is performed by λ _lE ^s (0) = λ _lR ^q (3).

In the case of n ≧ 1, for a certain real number C, the following J kinds of candidates λ _l ^Es (n) λ _lE ^s (n) _j (1 ≦ j
≦ J) is calculated from the following equation (4), and λ _lE ^s (n) _j = λ _lE ^s (n−1) + (j−J / 2) λ _lE ^s (n−1) / (J × C) ) (4) By the same method as the communication quality estimation device 109 described later, q ^-j (n)
And the cell arrival parameter λ _lE ^s

[Equation 9]

It is calculated from

That is, according to the equations (2) and (5), the cell arrival parameter λ is _set so that the difference between the cell arrival parameter λ _lE ^s and the actual cell arrival process based on k _l− (n) becomes small. _lE ^s is being updated. Such an operation is shown in FIG.
Cell arrival parameter calculation device 106 of the arrival parameter estimation device 103 and system state estimation device 107 shown in FIG.
It is supposed to be done in.

The cell arrival parameter λ _lO ^ut is calculated as, for example, λ _lO ^ut = λ _lE ^s (n) + λ _lR ^qn _ew (6)

The λ _l calculated as described above can also be quantized and output so that the flow rate control device 104 can handle it.

The system status observation / statistical device 105 determines the number of cells in the buffer of the buffer device 113, the buffer device 11
3 or the number of cells discarded by the cell discard device 112 described later,
The communication quality regarding the delay time received by the cell in the buffer device 113, the number of cells arriving from the terminal, the output parameter of the terminal currently outputting the cell passing through the buffer device 113 or desired in the future, the cell loss rate and the cell delay time. Is an element s _i (i = 1, 2, 3, ...), and a system state S = (s ₁ ,
_{s 2, s 3, ...,} s i, a ...), so as to observe at one slot or more intervals.

Then, S = (s ₁ , s ₂ , s ₃ , ..., S
_The statistic s _i- (n) for s _i of some or all of _i , ...) Is calculated by the following equation (7).

[0088]

[Equation 10]

Here, μ ₀ and μ ₁ are constants of 0 or more. In addition, s _i- (n) is converted to s _i (n-Nw) to s _i (n)
It may be an average between. Further, s _i may be output as it is without taking such statistics. In that case, for example, information of the buffer in the UPC in the packet communication system can be used as s _i .

It should be noted that such a statistic is calculated every predetermined time.

The flow rate control device 104 communicates with the communication quality estimation device 109 that estimates the communication quality of the cell from the cell arrival parameter λ _lO ^ut obtained from the arrival parameter estimation device 103, as shown in FIG. Quality estimation device 1
09, and the control signal calculation device 110 that calculates a control signal from at least one of the system state statistics obtained from the system state observation statistical device 105.

In the communication quality estimation apparatus 109, the buffer apparatus 113 is a single FIFO without priority control, a FIFO with a priority control function by the fixed threshold method, or a FI with a priority control function by the pushout method.
If the maximum number of cells that can be stored in the buffer device 113 is K and the cell arrival process can be assumed to be Poisson process, Bernoulli process, MMPP, MMBP, it is obtained from the arrival parameter estimation device 103. from the cell arrival parameter λ _lO ^ut that is, queuing theory (L.Klei
nrock, "Queueing Systems Vol.I Theory", John Wile
y & Sons or T. Czachorski, et.al, "Diffusion
Model of the Push-out Buffer Management Policy ", IE
CLR _l can be obtained from EE INFOCOM '92 Proceedings.

Further, the buffer device 113 has a plurality of FIFs.
When configured with O or a packet switch, a single non-priority FIFO with the closest characteristics, a FIFO with a fixed threshold method priority control function, or a push-out method priority control function FIF
With O, the buffer device 113 can be approximated and CLR ₁ can be calculated by the above method.

In the configurations of FIGS. 20 and 21, the system state statistic is obtained by the system state observation / statistical device 105, but as shown in FIG. 22, the system obtained by the packet communication system 102 is used. The congestion control device 100 may perform the above-described control processing based on the state statistics.

Next, the overall processing operation of the congestion control device of this embodiment will be described with reference to the flowchart shown in FIG.

First, the system status observation / statistical device 105 or the packet communication system 102 observes the system status of the packet communication system 102 to calculate a system statistic (steps S1 to S2), and obtains the result. Based on the system statistics obtained
In the arrival parameter estimation device 103, the cell arrival parameter λ ₁ is calculated while obtaining the estimated value q _l− (n−1) of the system state and its statistic (step S 3 to step S 4).

Next, the communication quality estimation device 109 of the flow rate control device 104 estimates the communication quality by _obtaining the cell discard rate CLR _l of the class based on the arrival parameter λ _lO ^ut obtained by the arrival parameter estimation device 103. (Step S5), and further, in the control signal calculation device 110,
The communication quality estimated in step S5 and the system state observation statistical device 105 or the packet communication system 102
A control signal is calculated from at least one of the system state statistics obtained from (step S6), and the control signal is transmitted to the packet communication system 102 to control the cell flow (step S7).

Next, a case will be described in which priority is given to each cell and congestion control is performed by performing priority control of cells according to the priority.

FIG. 25 is a congestion control device 1 for performing priority control.
00 schematically illustrates the entire configuration when 00 is applied to the packet communication system 102.

At least one or more terminals 101 are connected to the packet communication system 102, and when priority control is performed according to a control signal obtained from the flow rate control device 104, the packet communication system 102 connects each terminal. It includes a communication network 111 including a network and an exchange, a buffer device 113, and a cell discard device 112 that discards cells arriving from a terminal according to a control signal obtained from the flow control device 104.

Here, in order to control the cell discard rate CLR _l of the class l discarded due to the buffer overflow of the buffer device 113, the cell discard device 112 is controlled according to the control signal from the flow rate control device 104 before the cells enter the buffer. The case of discarding will be described.

The system state observed by the system state observation / statistical device 105 is the number of cells in the buffer k (n) at the head of the slot n of the buffer device 113, the declaration parameter, and the communication quality QOS regarding the cell loss rate. .

In the system state observation / statistical device 105, the statistic k of the buffer device 113, the number of cells in the buffer k (n)
^- a (n) statistic ^s - as (n), is calculated from equation (7).

The flow rate control device 104 _{compares the} number of cells k _arr in the buffer device 113 at the moment when the cells arrive at the cell discard device 112 and the threshold value t _l (n) corresponding to the class l of the arrived cells. , K _arr <t _l (n) (8), the cell of class l is transferred to the buffer device 113, and otherwise, the cell discard device 112 outputs a command to discard the cell.

For example, when L = 2, t _l (n) is determined as follows.

[0106] t ₀ (n) is constant at t ₀ (n) = K. Here, let K be the maximum number of cells that can be stored in the buffer device 113.

T ₁ (n) is determined as follows.
That is, a value λ ₀ obtained by dividing λ _0O ^ut obtained from the arrival parameter estimation device 103 by the number of multiplexing N _Mux and a certain λ ₁ ′.
Therefore, for t ₁ = 0, 1, ..., K, C obtained by analysis from the state transition probability matrix P (λ ₀ , λ ₁ ', t ₁ )
LR _l is below the communication quality QOS _l of cell class l, and, CLR _l the average value in the buffer the number of cells when given the lambda ₁ 'having the maximum value, k (λ _0, t ₁ ),

[Equation 11]

It is assumed that Where 1 ≦ t ₁ ≦ K + 1, λ _lR
^{Set qn} _ew = 0. Further, P (λ ₀ , λ ₁ ', t ₁ ) and k (λ ₀ , t ₁ ) are related to the threshold value of the priority control unit in the ATM network, B-431, "ATM network. Examination "and IEICE Technical Technique S
SE93-39, "CAC / UPC / ATM network"
It can be determined by the method described in "Integration of priority control".

As a second priority control processing method of the flow rate control device 104, π (n) = (π ₀ , ..., π _i , ..., π _K ) π _i = 1 if i = k (n ) π _i = 0 if i ≠ k (n) π (n + 1 | t ₁ ) = P (λ ₀ , λ ₁ ', t ₁ ) π (n) is substituted into the equation (7). π ^- (n + 1 |
t ₁ ), and λ _H = λ ₀ , λ _L = λ ₁ ′, using CLR ₀ (n + 1 | t ₁ ) calculated from Equation (26) described later,

(Equation 12)

It can also be determined by. Where QOS ₀
Is the required quality for the cell loss rate for class 0.

In the equation (10), the number of cells in the buffer of the buffer device 13 is compared with the threshold value t _l (n) to output the control signal for notifying whether or not to discard the cell. The threshold value is controlled so that the difference between the estimated value of the future communication quality based on the arrival parameter estimated by the arrival parameter estimation device 103 and the required communication quality QOS ₀ becomes small. That is, even if the characteristics of the cell flow generated by the terminal 101 vary from the declared parameters, the threshold can be set so that the communication quality in the packet communication system maintains the same value as the required quality.

Next, the congestion control device 10 for performing call admission control
A case where 0 is applied to the packet communication system 102 will be described with reference to FIG.

FIG. 26 schematically shows the overall configuration when the congestion control device 100 for performing call admission control is applied to the packet communication system 102.

At least one or more terminals 101 are connected to the packet communication system 102, and when there is a call connection request passing through the packet communication system 102, a call admission control is performed to judge whether or not to accept the request. In the case of performing the communication, the packet communication system 102 determines whether or not a call can be connected to the requesting terminal in accordance with a control signal obtained from the communication network 111 including a network connecting each terminal and a switch, the buffer device 113, and the flow control device 104. It is composed of a connection availability determination notifying device 115 for notifying.

As shown in FIG. 26, the flow control device 104
Can be composed of, for example, the communication quality estimation device 109 and the control signal calculation device 110.

In the communication quality estimation apparatus 109, for example, from the sum of average cell arrival rates from the terminal newly requesting call connection and the terminal currently connected, λ _lR ^q + λ _lR ^qn _ew , the queuing theory (L. Kleinrock, “Queueing Systems V
ol.I Theory ", John Wiley & Sons, or T.Czachorsk
i, et.al, “Diffusion Model of the Push-out Buffe
r Management Policy ", by the IEEE INFOCOM '92 Proceedings), it is possible to find the CLR _l.

In the control signal calculation device 110, for the required quality QOS _l for all classes l, if CLR _l ≤QOS _l , a call connection admission signal is issued, otherwise a connection disapproval signal is issued. The connection permission / inhibition determination notification device 115 is instructed to notify the selected terminal.

Next, a case where the congestion control device 100 for simultaneously performing priority control and call admission control is applied to the packet communication system 102 will be described with reference to FIG.

FIG. 27 shows a congestion control device 100 for performing priority control and call admission control at the same time as a packet communication system 102.
2 is a schematic diagram showing the entire configuration when applied to.

At least one or more terminals 101 are connected to the packet communication system 102. When priority control and call admission control are simultaneously performed in the packet communication system 102, the packet communication system 102 controls each terminal. Communication network 11 consisting of connecting networks and exchanges
1, the buffer device 113, and the connection availability determination notifying device 115 that notifies the terminal that has issued the request of the connection availability determination according to the control signal obtained from the flow control device 104.
And the cell arriving from the terminal 101, the flow control device 104
Cell discard device 1 for discarding according to a control signal obtained from
12 and.

The priority control is performed as described with reference to FIG.

In order to perform call admission control, the flow rate control device 104 is further composed of, for example, a communication quality estimation device 109 and a control signal calculation device 110 having the following functions.

That is, for example, when L = 2, the terminal 1
When there is a request for generation of a cell that passes through the buffer device 113 from 01, the communication quality estimation device 109 uses λ _0R ^qn _ew and λ _1R ^qn _ew obtained from the declared value from the terminal that made the call request. From λ _lO ^ut calculated by the arrival parameter estimation device 103 and a certain t _1new , P (λ ₀ , λ ₁ , t
_1new ), and calculates CLR ₀ and CLR ₁ in the same manner as the communication quality estimation device 109 in the call _admission control described above.

In the control signal calculation device 110, the CLR ₀ and CLR ₁ calculated by the communication quality estimation device 109 are QOS respectively.
If there is no t _{1new that} is equal to or less than ₀ and QOS ₁ , the connection availability determination notifying device 115 is notified that the cell from the newly applied terminal is not permitted to pass through the buffer device 113, and otherwise. Notify you to allow.

Next, the congestion control device 10 for performing flow control
A case where 0 is applied to the packet communication system 102 will be described with reference to FIG.

FIG. 28 schematically shows the overall configuration when the congestion control device 100 for performing flow control is applied to the packet communication system 102.

At least one terminal 101 is connected to the packet communication system 102, and when performing flow control according to a control signal obtained from the flow rate control device 104, the packet communication system 102 is a network connecting the terminals. And a switching device 103, and a regulated amount notifying device 114 for notifying the terminal of a request for reducing or temporarily suspending cell transmission according to a control signal obtained from the flow control device 104.

In the flow control device 104, the cell generation from the terminal of class l occurs when k _arr > t _l (n) instead of discarding the low priority cell by using the equation (8) in the above priority control. issued a notice to suppress the amount to the terminal, for some integer C _his-, when _{k arr ≧ t l (n)} -C his, terminal a notification for canceling the notification to suppress cell generation amount from the terminal of class l By controlling the flow rate, the flow control can be performed and the flow rate of the cell can be controlled.

In this case, λ ₀ represents the lowest cell arrival rate guaranteed by the flow control or the cell arrival rate from the terminal not performing the flow control.

Next, a case where the congestion control device 100 for simultaneously performing flow control and call admission control is applied to the packet communication system 102 will be described with reference to FIG.

FIG. 29 shows a congestion control device 100 for performing flow control and call admission control at the same time as a packet communication system 10.
2 is a schematic diagram showing the entire configuration when applied to No. 2.

At least one or more terminals 101 are connected to the packet communication system 102. When the packet communication system 102 performs flow control and call admission control at the same time, the packet communication system 102 connects each terminal. Communication network 11 consisting of networks and exchanges
1, the buffer device 113, and the connection availability determination notifying device 115 for notifying the requesting terminal according to the control signal obtained from the flow control device 104, and the flow control device 10.
4 is a control amount notification device 114 that notifies the terminal of a request to reduce or temporarily stop cell transmission in accordance with the control signal obtained from FIG.

The flow control is performed as described with reference to FIG.

In order to perform call admission control, the flow rate control device 104 is further composed of, for example, a communication quality estimation device 109 and a control signal calculation device 110 having the following functions.

Communication quality estimating apparatus 109 has the same function as the case of simultaneously performing the priority control and the call admission control described with reference to FIG.

Further, the control signal calculation device 110 is shown in FIG.
It has the same function as the case of performing the priority control and the call admission control simultaneously described with reference to.

Next, a case where the congestion control device 100 for simultaneously performing priority control, flow control and call admission control is applied to the packet communication system 102 will be described with reference to FIG.

FIG. 30 schematically shows the overall configuration when the congestion control device 100 for simultaneously performing priority control, flow control and call admission control is applied to the packet communication system 102.

At least one or more terminals 101 are connected to the packet communication system 102. When the packet communication system 102 simultaneously performs flow control, priority control, and call admission control, the packet communication system 102 A communication network 111 including a network connecting each terminal and a switch, a buffer device 113, a connection availability determination notifying device 115 for notifying the requesting terminal according to a control signal obtained from the flow rate control device 104,
In accordance with a control signal obtained from the flow rate control device 104, the regulation amount notification device 114 for notifying the terminal of a request to reduce or temporarily suspend the transmission of cells according to the control signal obtained from the flow control device 104, It is composed of a cell discard device 112 for discarding.

In this case, the priority control is the same as described above.

In the flow control device 104, for example,
When L = 2, the threshold value t calculated by the equation (10)
₁ (n) is, when the k _F was following some integer K, t ₁ (n) regulations amount to notify reduce or transmission of a cell, a request to suspend the terminal when ≧ K-k _F Flow control is performed by issuing an instruction to the notification device 114.

In order to perform call admission control, the flow control device 1
04 further includes, for example, a communication quality estimation device 109 and a control signal calculation device 110 having the following functions.

Communication quality estimating apparatus 109 is the same as the case of simultaneously performing the priority control and the call admission control described with reference to FIG.

The control signal calculation device 110 is similar to the case of simultaneously performing the priority control and the call admission control described with reference to FIG.

As described above, according to the above embodiment, the cell arrival parameter λ _l is estimated with high accuracy, and the cell loss rate and delay time estimated using this are calculated from the system state observation statistical device 105. By controlling the flow rate of the cell together with the information of the cell, even if the information about the cell arrival process is insufficient or the declared parameters are incorrect,
The flow rate of the cell can be controlled optimally.

Next, a third embodiment will be described.

That is, another embodiment in the case where the priority is given to each cell and the priority control of the cell is performed according to the priority will be described.

The threshold value method used here is different from the threshold value method in the second embodiment in that the threshold i of the cell slot is compared with the in-system number i at the head of the cell slot, and low priority is given to the cell slot. Cell regulation r _i

(Equation 13)

(0% or 100%) is determined. The threshold is set for each cell slot. If the priority classes are two classes, high priority and low priority, the relationship between the threshold values t and r _i is as follows.

[0150]

[Equation 14]

At this time, it is assumed that cells arrive from the respective input links in accordance with the Bernoulli process to the priority control system having the number of input links N _MUX , the buffer length K, the priority class 2, and the threshold value t ^O. , The priority control system,
A state transition probability equation based on the B / D / 1 / K model can be expressed as follows.

[0152]

(Equation 15)

Here, λ _H is a value obtained by dividing λ _0O ^ut calculated by the arrival parameter estimation device 103 by N _MUX , and
The maximum cell load _loss CLR _H of the high priority cell and the cell loss rate CLR _L of the high priority cell satisfy the communication quality QOS _H of the high priority cell and the communication quality QOS _L of the low priority cell, respectively, λ _Lall
Let t ^O be the threshold value that gives λ _Lall , and let λ _L be the value obtained by dividing λ _Lall by N _MUX . Here, λ _0i ^Rq _new = 0.

Λ = λ _H + λ _L , the state transition probability is

[Equation 16]

Further, α _k () is expressed by the following equation.

[0156]

[Equation 17]

Next, the relationship between the threshold value t and the regulation rate is expressed by the formula (1
2) At some time, the control input u for changing the threshold value from the initial value t ^O to t is defined by the following equation.

[0158]

(Equation 18)

At this time,

[Formula 19]

Then, the priority control system uses π (n) and u
It can be expressed by the bilinear equation (18) of (n).

[0161]

(Equation 20)

However, for simplification, 1 ≦ t ^O ≦ K−1. Also,

[Equation 21]

Then, using these,

[Equation 22]

[0164]

(Equation 23)

Here, the number of rows and columns is counted from 0. Further, P ′ _iK represents the element in the i-th row and the K-th column of P ′.

Furthermore, using the variables defined below,

[Equation 24]

Expression (18) is modified as follows.

[0168]

(Equation 25)

Next, the cell loss rate in each cell slot is defined. Due to the problem formulation, the state probability vector is
It is assumed that the cell arrives after the observation at the beginning of the cell slot and the control input is calculated, and the cell is discarded according to the state. However, the number of arriving cells and the number of discarded cells shall be observed simultaneously with the state probability vector in the next cell slot. Therefore, cell slot n + 1
The cell loss rate CLR _H (n + 1) of the high priority cells in the above is the number of cells N _AH (n) of the high priority cells that arrived in the cell slot n and the number N _LH (n) of the discarded high priority cells. Is defined by the following equation.

CLR _H (n + 1) = N _LH (n) / N _AH (n) (23) This relationship is shown in FIG.

Further, the average cell loss rate in cell slots 0 to n is calculated by the following weighted average cell loss rate CLR _H-
Defined in (n).

[0172]

(Equation 26)

The relationship between the cell loss rate CLR (n) in the cell slot n and the state probability vector π (n) with respect to an arbitrary threshold is CLR _H (n) = π ^t (n) Θ ₁ (25) Is approximated by. Here, the probability that two of i cells from the end of the cells that have arrived at _i β = (λ _H , λ _L ) are high priority cells,

[Equation 27]

Θ ₀ and Θ ₁ are the following K +
It is a one-dimensional vector.

[0175]

[Equation 28]

From this, QOS _H = π ^t (∞) Θ ₁ (28)

Therefore, equations (25), (28), (2
From 4) and (21)

[Equation 29]

Is obtained.

From Θ defined by equations (26) and (27),
Q ^* obtained by the following equation,

[Equation 30]

When A _C and Q ^{* C} are given,

[Equation 31]

Solution matrix of

[Equation 32]

From

[Expression 33]

Define

The solution of the threshold control problem for stabilizing the cell loss rate of high priority cells is as follows.
After that, the threshold value t can be obtained from u by solving the equations (12) and (16) in reverse. But,
In the process, u _i is calculated from the in-system number at the head of the cell slot, and the cell slot regulation rate r _i is calculated from equation (16). Therefore, in the threshold value method that determines the regulation rate for each cell slot used in the present embodiment, it is not necessary to use the threshold value t in order to determine the regulation rate of the low priority cell in the cell slot. Therefore, π obtained by the following equation from the system number k (n) observed at the beginning of the cell slot
Using (n) and equation (22),

(Equation 34)

The control input u _{k (n)} that minimizes V (n + 1) in the equation (33) can be determined.

FIG. 32 shows a control algorithm of the priority control method by the variable threshold method according to this embodiment.

Next, a fourth embodiment will be described.

That is, another method of estimating the cell arrival parameter relating to the cell priority control method will be described.

At the beginning of each cell slot,

[Equation 35]

As equations (16), (18) and (1
9), (26) to (33) are calculated, and the following values are further calculated.

Here, A _C (λ _L ) is A _C in equation (22) when λ _L is used as the arrival rate of the low priority cells.
Represents

[0192]

[Equation 36]

Next, for each ν = Δμ, 0, −Δμ,

(37)

Ν which gives the minimum value of the three

(38)

By using, μ ₀ and λ _{L in} cell slot n
To

[Formula 39]

It is calculated as follows.

However, in equation (39), if μ (n-1) + ν <μ _min, then μ (n) = μ _min , and if μ (n-1) + ν> μ _max, then μ (n) = μ _max. And

Using these parameters, the second
The control input in the cell slot n is calculated by the priority control processing method of.

FIG. 33 shows a simulation result by the second priority control processing method in order to show the effect of the priority control of the cell according to the fourth embodiment.

FIG. 33 shows that when the arrival parameters of the low-priority cells are increased by ΔL when the declared parameters for the average arrival rates of the high-priority cells and the low-priority cells are λ _H and λ _L , respectively.
It shows the variation of the cell loss rate (CLR-H) of the high priority cell and the cell loss rate (CLR-L) of the low priority cell. The conventional method is an ordinary fixed threshold method. As is clear from FIG. 33, both have the same performance when the input traffic is the set value, but even if the input traffic of the low priority cells increases, the cell loss rate of the high priority cells does not change according to the present invention. Therefore, the quality of the high-priority cell can be maintained even when the declared parameters are inaccurate or when traffic fluctuations are expected. Therefore, it is not necessary to connect a call with a margin on the safe side, so that network resources can be efficiently used.

[0201]

As described in detail above, according to the present invention, from the information on the number of ATM cells in the buffer, the number of arrivals of ATM cells, the number of discarded ATM cells, and the arrival rate of ATM cells, according to the situation, Since the arriving ATM cells and the ATM cells accumulated in the buffer can be discarded, the discard rate of the ATM cells of the high priority class can be stabilized more than the conventional method regardless of the variation in the number of input ATM cells. It is possible to provide a priority control device for an ATM cell that can be used.

Further, according to the present invention, the communication quality is not affected by the fluctuation of the input traffic, and the cell flow rate can be optimally controlled. Therefore, the congestion control method and the congestion control method which can obtain a higher multiplicity than the conventional method. A congestion control device using the same can be provided.

[Brief description of drawings]

FIG. 1 is a configuration diagram of a multiplexer or an ATM cell storage device to which the present invention is applied.

FIG. 2 is a diagram showing a configuration of an ATM cell discard device.

FIG. 3 is a diagram showing another configuration of the ATM cell discard device.

FIG. 4 is a diagram showing a configuration of an ATM cell discard determination device.

FIG. 5 is a diagram showing another configuration of the ATM cell discard determination device.

FIG. 6 is a diagram showing another configuration of the ATM cell discard determination device.

FIG. 7 is a diagram showing a configuration of a buffer state observation device.

FIG. 8 is a diagram showing a configuration of a buffer status statistics device.

FIG. 9 is a diagram showing respective configurations of an in-system number observing device #l, an ATM cell arrival number observing device #l, and an ATM cell discard number observing device #l.

FIG. 10 is a diagram showing respective configurations of an in-system number statistical device #l, an ATM cell arrival number statistical device #l, and an ATM cell discard number statistical device #l.

FIG. 11 is a diagram showing respective configurations of an in-system number statistical device #l, an ATM cell arrival number statistical device #l, and an ATM cell discard number statistical device #l.

FIG. 12 is a diagram showing an embodiment of a threshold value calculation device.

FIG. 13 is an embodiment of the call connection status storage device of the present invention.

FIG. 14 is an overall configuration diagram of the present invention.

FIG. 15 is a diagram showing a hardware configuration when priority control is performed by a common buffer switch.

FIG. 16 is a diagram showing a hardware configuration when priority control is performed by an input buffer.

FIG. 17 is a diagram showing a hardware configuration when priority control is performed by an output buffer.

FIG. 18 is a diagram comparing the performances of the present invention and a conventional method obtained by simulation.

FIG. 19 is a flowchart showing a regulation rate calculation procedure.

FIG. 20 is a diagram showing a configuration example of a congestion control device according to a second embodiment.

FIG. 21 is a diagram showing another configuration example of the congestion control device.

FIG. 22 is a diagram showing still another configuration example of the congestion control device.

FIG. 23 is a flowchart for explaining a congestion control processing operation of the congestion control device.

FIG. 24 is a diagram showing still another configuration example of the congestion control device.

FIG. 25 is a diagram showing an example of the overall configuration when a congestion control device that performs priority control is applied to a packet communication system.

FIG. 26 is a diagram showing an example of the overall configuration when a congestion control device that performs call admission control is applied to a packet communication system.

FIG. 27 is a diagram showing an example of the overall configuration when a congestion control device that performs priority control and call admission control is applied to a packet communication system.

FIG. 28 is a diagram showing an example of the overall configuration when a congestion control device that performs flow control is applied to a packet communication system.

FIG. 29 is a diagram showing an example of the overall configuration when a congestion control device that performs flow control and call admission control is applied to a packet communication system.

FIG. 30 is a diagram showing an example of the overall configuration when a congestion control device that performs priority control, call admission control, and flow control is applied to a packet communication system.

FIG. 31 is a diagram for explaining the timing of state observation in cell priority control according to the third embodiment.

FIG. 32 is a diagram showing a control algorithm of a priority control method based on the variable threshold method according to the third embodiment.

FIG. 33 is a view showing the performance evaluation result of the priority control method by the variable threshold method according to the third embodiment.

[Explanation of symbols]

1 ... ATM cell discarding device, 2 ... buffer, 3 ... buffer state statistic device, 4 ... buffer state observing device, 5 ... ATM
Cell input regulation device, 6 ... ATM cell discard determination device, 7 ...
ATM cell discard device in buffer, 8 ... ATM cell regulation rate / discarded address arithmetic device, 9 ... Threshold value comparison device, 10
... threshold value calculating device, 11 ... call connection state storage device, 12
… Regulation rate calculation device, 13… ATM cell arrival number observation device,
14 ... In-system number observation device, 15 ... ATM cell discard number observation device, 16 ... In-system number statistical device, 17 ... ATM cell arrival number statistical device, 18 ... ATM cell discarded number statistical device, 19 ... Data transfer device, 20 ... data observing device, 21 ... data counter, 22 ... ATM cell slot counter 1, 23 ... comparator, 24 ... counter, 25 ... ATM cell slot counter 2, 26 ... comparator, 27 ... data RAM, 28 ... A
TM cell slot counter, 29 ... Address encoder, 30 ... Encoder, 31 ... Selector, 32 ... Control data RAM, 33 ... Call connection state quantizer, 34 ... Table ID register, 35 ... MUX, 36 ... DEMUX,
37 ... Address management device, 38 ... Physical layer function, 39
... ATM-SW, 40 ... Routing tag addition device, 41
… Routine deletion device, 100… Congestion control device, 1
01 ... terminal, 102 ... packet communication system, 103 ...
Arrival parameter estimation device, 104 ... Flow rate control device, 10
5 ... System state observation statistical device, 106 ... Cell arrival parameter calculation device, 107 ... System state estimation device, 10
9 ... Communication quality estimation device, 110 ... Control signal calculation device.

Claims (13)

[Claims] 1. At least one buffer means for accumulating ATM cells, ATM cell discarding means for discarding the ATM cells before accumulation and the ATM cells in said buffer means based on a predetermined discrimination criterion, and said buffer means. The number of ATM cells stored therein, the number of ATM cells discarded by the ATM cell discarding means, the number of ATM cells arriving at the ATM cell discarding means,
ATM discarded according to the instruction of the ATM cell discarding means
A buffer state observing means for observing at least one of the number of cells and outputting the data obtained by the observation as buffer state data, and a statistic amount thereof while receiving the buffer state data from the buffer state observing means. Buffer state statistical means for sequentially updating and outputting as buffer state statistical data; and the ATM cell discarding means, based on at least the buffer state statistical data obtained from the buffer state statistical means, the discrimination criterion. A priority control device for an ATM cell, characterized in that 2. At least one buffer means for accumulating ATM cells, ATM cell discarding means for discarding the ATM cells before the accumulation and the ATM cells in the buffer means based on a predetermined discrimination criterion, and the buffer means. The number of ATM cells stored therein, the number of ATM cells discarded by the ATM cell discarding means, the number of ATM cells arriving at the ATM cell discarding means,
ATM discarded according to the instruction of the ATM cell discarding means
A buffer state observing means for observing at least one of the number of cells and outputting the data obtained by the observation as buffer state data, and a statistic amount thereof while receiving the buffer state data from the buffer state observing means. Buffer state statistical means for sequentially updating and outputting as buffer state statistical data, said ATM cell discarding means, based on at least said buffer state statistical data obtained from said buffer state statistical means, each ATM cell Calculating a regulation rate for regulating the transfer of ATM cells to the buffer means for each priority class assigned to A
TM cell discard determining means, and ATM cell input regulating means for discriminating the priority class of the ATM cell and regulating transfer of ATM cells to the buffer device according to the regulation rate calculated by the ATM cell discard determining means. An ATM cell priority control device characterized by being provided. 3. At least one buffer means for accumulating ATM cells, ATM cell discarding means for discarding the ATM cells before accumulation and the ATM cells in said buffer means based on a predetermined discrimination criterion, and said buffer means. The number of ATM cells stored therein, the number of ATM cells discarded by the ATM cell discarding means, the number of ATM cells arriving at the ATM cell discarding means,
ATM discarded according to the instruction of the ATM cell discarding means
A buffer state observing means for observing at least one of the number of cells and outputting the data obtained by the observation as buffer state data, and a statistic amount thereof while receiving the buffer state data from the buffer state observing means. Buffer state statistical means for sequentially updating and outputting as buffer state statistical data, said ATM cell discarding means, based on at least said buffer state statistical data obtained from said buffer state statistical means, each ATM cell For each priority class assigned to the buffer means, a regulation rate for regulating transfer of ATM cells to the buffer means, and an ATM cell regulation rate / discarded address calculation for calculating addresses of ATM cells to be discarded in the buffer means Means and the priority class of the ATM cell, and the ATM cell regulation rate and discard The ATM cell input regulation means for regulating transfer of ATM cells to the buffer device according to the regulation rate calculated by the address calculation means, and the ATM cell of the address calculated by the ATM cell regulation rate / discarded address calculation means. An ATM cell priority control apparatus comprising: an ATM cell discarding means in a buffer for discarding. 4. At least one buffer means for accumulating ATM cells, ATM cell discarding means for discarding the ATM cells before accumulation and the ATM cells in said buffer means based on a predetermined discrimination criterion, and said buffer means. The number of ATM cells stored therein, the number of ATM cells discarded by the ATM cell discarding means, the number of ATM cells arriving at the ATM cell discarding means,
ATM discarded according to the instruction of the ATM cell discarding means
A buffer state observing means for observing at least one of the number of cells and outputting the data obtained by the observation as buffer state data, and a statistic amount thereof while receiving the buffer state data from the buffer state observing means. Buffer state statistical means for sequentially updating and outputting as buffer state statistical data, said ATM cell discarding means, based on at least said buffer state statistical data obtained from said buffer state statistical means, each ATM cell Calculating a regulation rate for regulating the transfer of ATM cells to the buffer means for each priority class assigned to A
An AT that discriminates the TM cell discard determining means and the priority class of the ATM cell and regulates the transfer of the arriving ATM cell to the buffer device according to the regulation rate calculated by the ATM cell discarding determining means.
M cell input restriction means, the ATM cell discard determination means includes call connection state storage means for storing information about arrival process of ATM cells from terminals and connection status of calls, and the buffer state statistics means. In the buffer means, a threshold value calculating means for calculating a threshold value corresponding to each priority class based on the obtained buffer status statistical data and the information stored in the call connection status storing means. Among the ATM cells accumulated in the above, either the number of ATM cells of each priority class or the sum of the number of ATM cells of all priority classes is compared with the threshold value calculated by the threshold value calculation means. By
A priority control device for an ATM cell, comprising: a threshold value comparing means for determining whether or not the input of the arriving ATM cell to the buffer means is restricted. 5. A congestion control device for performing congestion control of a packet communication system, comprising at least one buffer means for accumulating packets transferred from a plurality of terminals, and accumulating and exchanging packets from said terminals, said buffer means Observing at least one of the number of packets arriving at, the number of packets accumulated in the buffer means, the communication quality of the packet communication system, the declaration parameter indicating the output process of the packet at the terminal, and the required quality for the communication quality. Then, the system state observation statistical means for outputting the statistical amount of the data obtained by the observation as the system state statistical amount, and the buffer means from the terminal based on the system state statistical amount obtained from the system state observation statistical means. Estimating means for estimating the arrival characteristics of packets to the Based on the arrival characteristic of the stored packet and a predetermined discrimination criterion based on the system state statistic, the packet before being accumulated or the packet in the buffer means is discarded, the packet output speed of the terminal is regulated, and a new call connection is established. A congestion control device comprising: a determination unit that determines at least one of refusing a connection when a request is made. 6. A congestion control device for congestion control of a packet communication system, comprising at least one buffer means for accumulating packets transferred from a plurality of terminals, and accumulating and exchanging packets from said terminals, said buffer means Observing at least one of the number of packets arriving at, the number of packets accumulated in the buffer means, the communication quality of the packet communication system, the declaration parameter indicating the output process of the packet at the terminal, and the required quality for the communication quality. Estimating means for estimating the arrival characteristics of the packet from the terminal to the buffer means, based on the statistics of the data obtained by the above, and the arrival characteristics of the packet and the system state statistics estimated by the estimating means. Based on a predetermined discrimination criterion based on And a packet output rate of the terminal, and rejecting the connection when a new call connection request is made, and a deciding means for deciding at least one of the following: congestion control apparatus. 7. The estimating means updates the packet arrival characteristic so as to reduce a difference between a system state statistic estimated based on the packet arrival characteristic and a statistic of data obtained by the observation. The congestion control device according to claim 5, wherein the congestion control device comprises: 8. The congestion control device according to claim 5, wherein the system state observation statistic means calculates a statistic amount of data obtained by observation every predetermined time. 9. The determination means sets the discrimination criterion so as to minimize a difference between a requested communication quality and a communication quality of the communication system estimated from the arrival characteristics of the packet and the system state statistics. The congestion control device according to claim 5, wherein the congestion control device is set. 10. A congestion control method for a packet communication system, comprising at least one buffer means for accumulating packets transferred from a plurality of terminals, and accumulating and exchanging packets from said terminals, wherein a packet arriving at said buffer means Number, the number of packets accumulated in the buffer means, the communication quality of the packet communication system, the declaration parameter indicating the output process of the packet at the terminal, and the required quality for the communication quality. Based on the statistic of the obtained data, the arrival characteristic of the packet from the terminal to the buffer means is estimated, and based on a predetermined discrimination criterion based on the estimated arrival characteristic of the packet and the system state statistic, Discard packets before being accumulated or packets in the buffer means, packets of the terminal Congestion control method characterized in that regulation of force speed, determines a new reject connections when there is a call connection request, of at least any one. 11. The packet arrival characteristic is updated so as to reduce a difference between a system state statistic estimated based on the packet arrival characteristic and a statistic of data obtained by the observation. The congestion control method according to claim 10. 12. The statistical amount of data obtained by observation is calculated every predetermined time.
The described congestion control method. 13. The discrimination so as to minimize the difference between the communication quality of the communication system estimated from the arrival characteristics of the packet and the statistics of the data obtained by the observation, and the requested communication quality. The congestion control method according to claim 10, wherein a standard is set.