JPH06104917A - Congestion control method and call admission control method - Google Patents

Abstract

PURPOSE:To obtain the congestion control method with less deterioration in communication quality due to a cell with low priority in which congestion is quickly recovered in a packet communication network. CONSTITUTION:A congestion control circuit 9 measures a missing rate of cells for each of queues 12-1-12-n provided corresponding to quality class/output line and allocates momentarily a standby band to a queue whose missing rate exceeds an allowable cell missing rate depending on the quality class in advance. Furthermore, when a cell missing rate is larger than a requested rate and very smaller than the request value, the congestion control circuit 9 informs it to a call reception control section 11 that the missing rate is not optimized and optimizes the operating band of each queue so that the cell missing rate is optimized by the control section 11.

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 in a packet network, and more particularly to an asynchronous transfer system (ATM: A).
synchronous Transfer Mod
The invention relates to a congestion control method for optimizing call admission control while avoiding congestion in a communication network using e).

[0002]

2. Description of the Related Art In an ATM communication network, which is being studied by various research institutes as a next-generation powerful communication system, information is transmitted in a fixed length packet (hereinafter referred to as "cell") format. In ATM, information generated from various media (voice, image, data, etc.) having various transmission speeds is communicated.

Generally, since there is a limit to the communication capacity that can be provided by the network, the network manager side requests each subscriber at the transmission rate, the required communication quality (cell transmission delay time, cell loss rate, etc.). , The bandwidth when the call is allowed,
Estimate the amount of resources consumed in the network (hereinafter referred to as the "required resource amount") such as the buffer amount, and allow the call request only when the estimated amount does not exceed the transmission capacity of the network. ing. Hereinafter, such control performed at the time of calling request is referred to as "call admission control".

If there is an error in estimating the resource amount during call admission control, the required resource amount will temporarily exceed the transmission capacity of the network, and some cells will be lost in the network. In addition, if the number of lost cells increases, the quality required by the subscriber cannot be guaranteed. This state is generally called "congestion state". For example, when a subscriber requests a communication quality of a cell loss rate of 1/10 ⁶ or less, the subscriber supposes that the communication quality is 10 or less.
^{If 7} cells are transmitted, if 10 or more cells among them are lost in the network, the communication network is in a congestion state.

In the ATM communication network, a plurality of subscribers share the same resource in the network to effectively utilize the resource. Therefore, once congestion occurs, the communication quality of unspecified multiple subscribers may deteriorate. The occurrence of congestion can be improved to some extent by, for example, improving the reporting accuracy or the estimation accuracy by rigorous analysis of the required resource amount. However, considering the unexpected emergence of new services in the future, it is difficult to request subscribers to submit a strict declared value for all services at the time of calling, and there is a limit to the improvement of the accuracy of declaration. is there. Further, the required resource amount is estimated analytically, but since some mathematical models that can be analyzed are limited, some kind of approximation is required for the estimation, and the estimated amount has an error.

For the above reasons, it is difficult to completely avoid the occurrence of congestion in the ATM packet network, and when congestion occurs, congestion control for returning from the congestion state to the normal state (non-congestion state) is indispensable. Becomes For example, if 10 out of 5 × 10 ⁶ transmission cells from a subscriber who requested a cell loss rate of 1/10 ⁶ or less as the communication quality are lost, congestion control Cell loss is prevented for 5 × 10 ⁶ cells sent to the cell.

As a conventionally known congestion control method in a packet network, for example, "Consideration of traffic control in an ATM communication network (Traffic Con-trol on
ATM Communication Network
k) ”(Shunji Abe et al., Technical Report of the Institute of Electronics, Information and Communication Engineers, SSE90-119), when a congestion occurs, a packet transmitted from a subscriber having a low required communication quality (hereinafter referred to as“ low priority packet ”). Packet) and a packet transmitted in violation of the contract conditions related to the communication speed, etc., which were established between the subscriber and the network provider at the time of call setup (hereinafter,
The number of packets in the network is reduced by discarding "violating packets") at the nodes in the communication network, and as a result, transmission packets from subscribers with high required communication quality (hereinafter referred to as "high priority packets"). There is a method of avoiding loss in the network.

In this case, the selection whether the cell belongs to the low quality class or is from the subscriber is made based on the required quality of the call stored at the time of call admission control. Further, the discarding process of the low-priority cells is realized by limiting the buffer area that can be used by the low-priority cells by using the threshold value X3 (total buffer amount ≧ X3 ≧ 0). The high-priority cell is allowed to use the entire area of the buffer. According to this method, although the communication quality of the high-priority cell transmitted from the subscriber having a high required quality is temporarily deteriorated, it is eventually improved.

[0009]

However, in the conventional congestion control method, as a result of guaranteeing the quality of the high-priority cells, the quality of the low-priority cells deteriorates, and the required quality of the low-priority cells cannot be guaranteed. is there. In particular, when the ratio of high priority cells received by the network is higher than that of low priority cells, the threshold value X3 is set sufficiently small to guarantee the quality of high priority cells, and most low priority cells are discarded. Since there is no choice but to make such a situation, the quality of communication by the low-priority cell is greatly deteriorated. Also, in a packet network, once congestion occurs, it is desirable to prevent the congestion of the same scale from recurring as much as possible, but in the conventional method, the occurrence of congestion is not fed back to the call admission control. , Congestion of the same scale could occur repeatedly.

It is an object of the present invention to provide a congestion control method and a call admission control method in a packet network that can quickly recover to a normal state even when congestion occurs.

Another object of the present invention is to provide a congestion control method and a call admission control method capable of preventing the recurrence of congestion of the same scale.

Still another object of the present invention is to provide a congestion control method and a call admission control method in which the communication quality of a low priority cell is less deteriorated.

[0013]

In order to achieve such an object, according to the present invention, a buffer memory for temporarily storing an input cell is provided, and cells belonging to different communication quality classes are exchanged based on a logical channel number. In the communication node, a plurality of queues corresponding to the output lines are formed in the buffer memory for each communication quality class, and the band of each output line is divided into a spare band and a plurality of bands dedicated to the queues. further,
The communication quality is observed corresponding to the queue, and when the observed value in any of the queues exceeds the required communication quality value, a spare band is given to the above queue for each cell. In addition, the control unit located above the communication node allows the line utilization rate to be varied to the extent that congestion occurs, and the congestion occurrence status notified from the lower node device is fed back to the line utilization rate. By doing so, the line utilization rate is optimized.

[0014]

According to the present invention, when congestion occurs in a certain queue, it is possible to return the congestion state to the non-congestion state by instantaneously allocating a spare band to the congestion queue. Further, since the queue is divided according to quality classes, congestion related to high priority cells does not affect the communication quality of low priority cells. Also, by optimizing the line utilization rate by the higher-level control unit according to the cell loss situation, it is possible to prevent or reduce the recurrence of congestion of the same scale as the one that once occurred, and as a result, the buffer memory The capacity of the spare band can be reduced and the band dedicated to the queue can be increased, and the communication network can be operated at a high line utilization rate.

[0015]

Embodiments of the present invention will now be described with reference to the drawings.

FIG. 2 shows the structure of the cell 201. The cell includes a header section 201A and a user information storage section 201B. The header portion 201A includes a logical path identifier (VPI; virtual path identifier).
ier) storage unit and logical channel identifier (VCI; v
virtual channel identity
r) and the like. The cell size is currently 53 according to the recommendations of the International Telegraph and Telephone Consultative Committee (CCITT).
It is standardized in bytes. The VCI is given an independent value for each call. The VPI is given a common value for a plurality of VCIs that use the same route.

FIG. 1 is a block diagram showing an embodiment of a communication node device to which the congestion control method and the call admission control method according to the present invention are applied. In the figure, 1 (1-1 to 1-
n) is an input line connected to a subscriber terminal (not shown), 2 (2-1 to 2-n) is an input line corresponding part provided for each input line, and 3 is a line corresponding part. A multiplexing unit for multiplexing outputs, 4 is a cell buffer for temporarily storing input cells, and 5 is a cell buffer for selectively outputting output cells from the cell buffer 4 to an output line 7 (7-1 to 7-n). 6 (6-1 to 6-n) is an output line corresponding part provided in each output line 7, and 8 is a write / read control for controlling writing and reading of cells to and from the cell buffer. Circuit, 9 is a congestion control circuit, 10 is an adaptation circuit,
Reference numeral 11 is a control unit that performs call admission control.

The cell 201 output to the input line 1 from each subscriber terminal (not shown) arrives at the input line corresponding unit 2. Each input line corresponding unit 2 is provided with a table 13 in which the output line number RT and the quality class number CLS are stored in correspondence with VPI / VCI, and the above table using the VPI / VCI included in the header of the arrival cell 201 as an address. RT / CLS is read from 13 and these are stored in cell 20
1 is added to the header section 201A and is input to the multiplexing section 3 in the format of the intra-node cell 202 shown in FIG. The cell output from the multiplexing unit 3 is input to the cell buffer 4. At this time, RT and CLS of the additional header section are also input to the write / read control circuit 8 via the signal line 14.

FIG. 3 shows a logical structure of the cell buffer 4. In the present invention, the cell buffer 4 is divided into a plurality of queue areas 12-1 to 12-m corresponding to quality classes, and queues corresponding to output lines are formed in the respective queue areas. In the following description, the quality class number and the output line number are represented by the symbols CLS and RT, respectively, and the quality class is CL.
S, the queue for storing cells whose output line is RT is Q (C
LS, RT). CLS = 1 to m, RT =
1 to n, for example, the queue represented by Q (1,1) stores the cell 202 of CLS = RT = “1”.

The write / read control circuit 8 determines the arrival cell storage queue Q (CLS, RT) determined according to the additional header information (RT / CLS) of the arrival cell notified from the multiplexing unit 3 via the signal line 14. ) Is read to the cell buffer 4 via the signal line 15
It is given as a write address. As a result, in the writing period to the cell buffer, each arriving cell has a queue Q (CLS, R) corresponding to each additional header information.
T). Queue Q (C
If a large number of cells are already stored in (LS, RT) and there is no free area for storing a new arrival cell, arrival cell 2
02 is discarded. When the cell arrives, the write / read control circuit 8 notifies the congestion control circuit 9 of the header information of the arriving cell via the signal line 16, and when the cell is discarded, the discard notification information is sent to the signal line 16 described above. To the congestion control circuit 9 via

Each queue Q (CLS, R in the cell buffer
The capacity CP (CLS, RT) and the read band BW (CLS, RT) are allocated to T). Above capacity C
P (CLS, RT) indicates the number of cells that can be stored in the queue Q (CLS, RT), and the read band BW
(CLS, RT) indicates the frequency (bps) at which the cells stored in the queue Q (CLS, RT) are read to the output line 7. For example, if the output line speed is 156 Mbps and B
When W (1,1) = 52 Mbps, 156 Mbps
Since ÷ BW (1,1) = 3, cells from the queue Q (1,1) are read out at a rate of one cell every three cell times for the output line. Here, 1 cell time indicates the time required for one cell to pass through on the output line, and when the line speed is 156 Mbps, 1 cell time≈2.7 μ.
s.

The congestion control circuit 9 outputs RT / CLS according to the read band and inputs it to the write / read control circuit 8 via the signal line 17. For example, BW (1,1) =
In case of 52 Mbps, once every 3 cell times,
RT = CLS = “1” is output. The write / read control circuit 8 that receives RT / CLS from the congestion control circuit 9
The address of the read cell stored in the queue Q (CLS, RT) is given to the cell buffer 4 via the signal line 15 together with the read signal. By this, Q (C
The cells are read from LS, RT) in a first-in first-out format.

The cell read by the queue Q (CLS, RT) is output to the output line corresponding unit 6 of the output line corresponding to RT via the separating unit 5, and the additional header unit is generated at the line corresponding unit 7. It is removed and sent to the output line 7 in the form of cell 201.

The congestion control circuit 9 measures the number of arriving cells A (CLS, RT) and the number of lost cells L (CLS, RT) corresponding to the above-mentioned queue in the cell buffer, and identifies the queue where congestion is occurring. , Detecting queues with insufficient read bandwidth utilization and very few lost cells. These queues are detected by the congestion detection unit 22 in the congestion control circuit 9,
The detection result is notified to the control unit 18 via the signal line 18.

The congestion control circuit 9 controls to increase the reading bandwidth of the queue in the congested state (hereinafter referred to as "congestion queue") in order to reduce the cell loss rate of the queue in the congested state. Operate. That is, in order to increase the cell read frequency from the congestion queue, the output frequency of the RT / CLS designating the congestion queue on the signal line 17 is increased.
In the present invention, a spare band is provided for each output line 7 in order to perform the above-mentioned read frequency control.

Next, the "quality class" in this embodiment will be described.

Each subscriber (terminal device), when making a call request,
The control unit 1 determines the quality class number (CLS) to which the device belongs.
Declare to 1. The quality class is determined by, for example, the cell loss rate and the cell delay time, and an example of the correspondence relationship between the quality class number and the loss rate / delay time is as follows.

Quality class 1: CLR ≦ CLRmax (1) = 1/1
0⁹ DT ≤ DTmax (1) = 1 ms Quality class 2: CLR ≤ CLRmax (2) = 1/1
0⁹  DT ≤ DTmax (2) = 10 ms Quality class 3: CLR ≤ CLRmax (3) = 1/1
0⁶ DT ≤ DTmax (3) = 1 ms Here, CLRmax (CLS), DTmax (CL
S) is the permissible loss rate for each class and
Indicates the maximum delay time. "Quality class 1" is
Prioritized classes for loss rate and delay time
The target media is, for example, a TV phone
Power is raised. "Quality class 2" is given priority by loss rate,
It is a class that is not prioritized by delay time and
Then, general data transfer communication can be mentioned. "quality
"Class 3" is given priority to loss rate and priority to delay time
It is a class, and the target media is the voice signal of the telephone
Is mentioned.

The subscriber knows the correspondence with the above-mentioned quality class in advance, and determines or selects the quality class number according to the cell loss rate and the delay time required for the communication to be started, and the call is issued. At the time of calling, this is reported to the control device 11 on the network side. The control unit 11 assigns an identifier VP to each call during the call acceptance process performed prior to the start of each communication.
I / VCI is assigned and the quality class declared by each subscriber is managed in accordance with VPI / VCI. The output line number RT to be stored in the table 13 in each line corresponding unit is determined based on the destination device ID (for example, telephone number) declared by the subscriber. The control unit 11 determines the output line number (RT) and the quality class number (CLS) determined to be compatible with VPI / VCI.
Is notified to the line corresponding part of the input line accommodating the calling subscriber, and this information is stored in the line table 13. The control information such as the call request output from the subscriber terminal is transferred from the input line interface 2, the multiplexer 3, the cell buffer 4, the demultiplexer 5, the signal line 20, and the adaptation circuit 10.
Is input to the control unit 11 via.

Next, the quality control method in this embodiment will be described.

The loss rate and the delay time are set to CLRmax (CLS) and DT which are set corresponding to the class, respectively.
It is necessary to control the value to be equal to or less than the value of max (CLS). For example, the queue Q (1, n) is a queue corresponding to the class 1 and the output line n, and the cells stored in this queue are controlled so that the loss rate ≦ 1/10 ⁹ and the delay time ≦ 1 ms. There is a need to. The cell delay time depends on the setting operation of the buffer capacity CP and the read band BW.
The loss rate is controlled by the setting operation of the queue usage rate. These setting operations are performed by the control unit 11, the buffer capacity CP is set in the write / read control circuit 8, and
The read band BW is set in the congestion control circuit 9, respectively.

The delay time is controlled as follows. now,
If the time length in which a cell is stored in the queue Q (CLS, RT) is defined as the “delay time DT” of that cell, the following equation holds for the delay time DT. DT (CLS, RT) ≦ (1 cell time) × CP (CLS, RT) × (line speed) / BW (CLS, RT) (Equation 1) Thus, the delay time is CP (CLS, RT) ) And BW
Depends on (CLS, RT). In addition, here, BW (C
LS, RT) is assumed to be determined based on past communication demand over a relatively long period (one month, one week, etc.),
There is no particular restriction on the specific method of determining the BW.

As described above, it is necessary to satisfy DT (CLS, RT) ≦ DTmax (CLS) (Equation 2). Therefore, in order to establish this relationship, CP ( CLS, RT). For example, BW (1, n) = 52 Mbps, line speed = 156
In the case of Mbps, from equations 1 and 2, CP (1, n) ≦ DTmax (1) × BW (1, n) / {(1 cell time) × (line speed)} ≈122 (cell) (however, the decimal point The value of CP (1, n) can be calculated as shown below.

By using the buffer capacity calculated by using the above equation 3, the delay time of class 1 is calculated by DTm.
It is possible to control to ax (1) or less.

Next, cell loss rate control and congestion control will be described.

When the cell loss rate is small, the cell arrival rate to the queue Q (CLS, RT) is cell arrival rate≈queue usage rate. When the cell arrival rate is high, the number of stored cells in the queue may increase and the number of accumulated cells in the queue may become equal to the queue capacity. When a new cell arrives in that state, the queue overflows and the arrival cell is lost. The greater the number of calls accommodated in the same queue Q (CLS, RT), the higher the queue usage rate and the cell loss rate. The cell loss rate is also affected by the traffic characteristics of the accommodated call such as the communication speed and the burst property of the arriving cell. Therefore, the control unit 11 needs to accommodate the newly generated call in the corresponding queue within a range in which the cell loss rate does not exceed the requested value CLRmax (CLS) of each subscriber.

Specifically, at the time of making a call request, the traffic characteristics such as the communication speed declared by the subscriber, and CLRmax.
Estimate the required bandwidth ρ vir of the call based on (CLS). Here, the “required band ρ vir” means a band (bps) that needs to be allocated to a call in order to guarantee the cell loss rate to be CLRmax (CLS) or less. The sum of the required bandwidth ρvir of the calls already accommodated in the queue Q (CLS, RT) that should accommodate the newly generated call is ρ (CLS,
RT), the new call is accepted when the following expression is satisfied. ρ (CLS, RT) + ρvir ≦ ρmax (CLS, RT) (Equation 4) where ρmax (CLS, RT) is the loss rate CLRm.
It is the upper limit of the band ρ that can be accommodated in the queue for controlling to ax (CLS) or less, and ρmax (CLS, RT) ≤ BW (CLS, RT) (Equation 5).

The above-mentioned estimation of the required band ρvir is performed by mathematical analysis, computer simulation, etc., but the applicable model that can be analyzed is limited, or the applicable simulation time is limited. , Etc., some approximation is necessary regardless of the estimation method. As a result, even if Equation 4 is established, the loss rate may exceed CLRmax, that is, the congestion state may occur.

When congestion occurs in a certain queue Q (CLS, RT), in order to reduce the cell loss rate,
Capacity CP (CLS, RT) or read bandwidth BW
It is necessary to increase either (CLS, RT). However,
When CP is increased, the delay time also increases, so
In this embodiment, the value of CP is left unchanged and BW is increased. Further, in order to increase the BW, a spare band BW (res, RT) is prepared in advance for each output line 7, and the spare band BW (res, RT) is appropriately allocated to the queue in the congestion state. At this time, the read bandwidth of the queue in the congestion state is temporarily changed as follows: BW (CLS, RT) = BW (CLS, RT) + BW (res, RT) (Equation 6)

The congestion control circuit 9 detects the congestion and changes the band. The congestion control circuit 9 stores, for example, a logic circuit configured by hardware and a threshold data necessary for detecting the occurrence of congestion in order to realize the change of the band at high speed (in cell time order). A memory or the like for performing the operation is provided. By preparing a sufficiently large spare band in advance, the queue Q (C
Cell loss rate in LS, RT), the required value (CLRm
ax) or less.

The optimization process of ρmax (CLS, RT) is performed as follows.

One of the causes of congestion is ρmax included in the right side of Expression 4 applied to call admission control.
The value of (CLS, RT) is not optimized. That is, the congestion factor is that ρmax (CLS, RT) is larger than the amount of bandwidth that can be accommodated in the queue Q (CLS, RT). If congestion occurs ρ
If the value of max (CLS, RT) is not changed, similar congestion may occur again, so in the present invention, ρ
The value of max (CLS, RT) is changed according to the following equation. ρmax (CLS, RT) = ρ (CLS, RT) -Δ (Equation 7) The magnitude of ρmax needs to be smaller than the accommodation band ρ when the congestion occurs, and the magnitude of the decrease Δ is the congestion. It is decided according to the degree (scale). This change is not required to have a high cell time order, unlike the change of the band shown in Expression 6, and thus can be executed by software processing by the processor configuring the control unit 11. still,
Occurrence of congestion and notification of the degree of congestion to the control unit 11 are performed from the congestion control circuit 9 via the signal line 18.

In this embodiment, the communication states are classified into, for example, the following three types. (1) Congestion state: When CLR ≧ CLRmax is satisfied. (2) Appropriate state: CLRmax> CLR ≧ (CLRma
x / l) holds. (3) Excess quality state: CLR <(CLRmax / l)
When is satisfied. However, l = 10, 100, 1000, ...

Here, the excess quality state means a state in which the cell loss rate is extremely low compared to the required value, even if the equal sign is satisfied in Expression 5, for example, in the case of l = 100. , Cell loss rate is 1/100 of required value CLRmax
Refers to the state of. The excessive quality state is a highly desirable state from the viewpoint of quality assurance, but the request loss rate can be satisfied even if the capacity of the queue is increased to some extent. It can be said that the read band BW is not sufficiently effectively utilized. For this reason, in the present invention, ρmax (CLS, RT) is changed according to the following equation even in the excessive quality state. ρmax (CLS, RT) = ρ (CLS, RT) + Δ (Equation 8) The value of ρmax can be made larger than the accommodation band ρ at the time when the excessive quality state occurs. Further, the size of Δ is determined according to the cell loss rate. Ρm according to Equation 7
The change of ax (CLS, RT) is executed by software processing by the processor of the control unit 11 because high speed of the cell time order is not required. Further, the congestion control circuit 9 notifies the control unit 11 of the occurrence of the excessive quality state and its degree via the signal line 18.

In the congestion control method of the present embodiment, congestion is detected for each queue 12 shown in FIG. 3, and the reserve band is speeded up to the queue in which congestion has occurred without passing through the processor. By allocating, the congestion state is instantly returned to the normal state (non-congestion state). In addition, since the queue used for each quality class and the band are made independent, there is an advantage that the congestion occurring in a certain quality class does not affect the communication quality of another quality class. Further, the control unit 11 is notified of the occurrence status of congestion and the occurrence status of excess quality status, and the control unit based on these pieces of information, the accommodation bandwidth upper limit value ρmax of the call accommodated in the corresponding queue.
Therefore, once congestion occurs, the same degree of congestion recurrence can be prevented, and there is an advantage that the bandwidth can be effectively used within the range where the cell loss rate does not deteriorate.

Next, the operation of the write / read control circuit 8 will be described with reference to FIG.

The write / read control circuit 8 performs write control for storing the arriving cell in the queue 12 in the cell buffer 4 and read control of the cell already stored in the queue to the output line 7. That is, the address of the cell buffer 4 that should store the arrival cell 202 and the address of the cell that should be read from the cell buffer 4 are output, and these addresses are given to the cell buffer as a write address or a read address.

The write / read control circuit 8 includes address management units 401-1 to 401-m provided corresponding to classes.
, A free address FIFO 402, decoders 403 and 405, selectors 404 and 406, and the like. For example, the class 1 compatible address management unit 401
-1 manages the address of the queue area 12-1 corresponding to class 1, and the free address FIFO 402 holds the address of the cell non-storage area in the cell buffer 4.

Class 1 compatible address management unit 401-
1 is the address FIFO 412 and the threshold value judgment circuit 413.
, Cell number counter 414, decoders 410 and 4
11 and selectors 415 and 416.

The address FIFO 412-1 manages the address of the queue Q (1,1), and the cell number counter 414-1 counts the number of cells stored in the queue Q (1,1) and sets the threshold value. The determination circuit 413-1 detects the presence or absence of cell loss based on the number of cells stored in the queue Q (1,1) and the queue capacity CP (1,1) counted by the cell number counter 414-1. For example, when a cell whose header information is CLS = RT = “1” arrives in a state where the following equation is satisfied, this arriving cell is discarded.

Number of storage cells in Q (1,1) = CP (1,1) (Equation 9) The write control of the arrival cell 202 to the buffer 4 is performed as follows.

When the cell arrives, the RT / CLS of the arriving cell 202 is notified via the signal line 14. The output of the threshold value judgment circuit 413 (413-1 to 413-n) is the output line selector 415, the class selector 404, and the inversion circuit 4.
It is input to the read enable (RE) input of the empty address FIFO 402 via 17. As a result, when the expression 9 is not satisfied, the FIFO 402 outputs an empty address, which is input to the write address input of the cell buffer 4 via the signal line 15-1. The arrival cell 201 is the cell buffer 4 designated by the above address.
Is stored in the area inside.

The output of the class selector 404 is also input to the control signal input of the class decoder 403, and when the equation 9 is not satisfied, the class decoder 403 generates an enable signal (EN), which controls the output line decoder 410. It is designed to be input to the signal input. The output of the output line decoder 410 is the write enable input (WE) of the address FIFO 412 and the cell number counter 41.
4 is input to the increment input. Address FIF
In O412, the storage addresses of the arrival cells 201 output from the vacant address FIFO 402 are sequentially stored. In addition, each time the above operation is performed, the cell number counter 414
Is incremented by one. In this way, the queue Q (1,
The addresses of the cells stored in 1) are stored in the order of cell arrival, and the cell number counter 414-1 stores Q (1,
The number of cells stored in 1) is counted. still,
Arrival cell header information (RT, CLS) and selector 4
The cell loss information output from 04 is signal line 1 respectively.
The congestion control circuit 9 is notified via 6.

The read control of the storage cell from the buffer 4 is performed as follows. The congestion control circuit 9 outputs, on the signal line 17, an output line number and a quality class number (RT / CLS) that specify a queue that is a cell read target according to the read band BW (CLS, RT). The empty display (EMP) output of the address FIFO 412 is input to the control input of the buffer circuit 407 via the output line selector 416 and the class selector 406. The selectors 416 and 406 are the address FIFOs corresponding to the RT / CLS notified via the signal line 17, respectively.
411 and the output of the address management unit 401 corresponding to the class are selected.

The buffer circuit 407 has an address FIFO.
When no address is stored in 412, that is, when the read target queue Q (CLS, RT) is not empty, the quality class number (CLS) is output. The output from the buffer circuit 407 is passed through the class decoder 405,
Input to the output line decoder 411 control input. The output of the output line decoder 411 is the address FIFO 41.
The read enable input (RE) and the decrement input of the cell number counter are input. From the address FIFO 412, the buffer 4 pointing to the storage position of the first cell accumulated in Q (CLS, RT)
The internal address is output. The address is the signal line 15
-2 to the read address input of the buffer 4, which causes the queue Q in the cell buffer 4 to be read.
The first cell is read from (CLS, RT). In addition, as the cell is read, the read address becomes
It is input to the data input DI of the vacant address FIFO 402 and stored as a vacant address. Each time the above operation,
The count value of the cell number counter 414 is decremented by one.

With the above circuit configuration, arrival cell write control to an arbitrary queue 12 in the cell buffer 4, cell loss detection, notification of cell loss and cell arrival to the congestion control circuit 9, and congestion control circuit 9 It can be seen that the cell read control from the queue specified by is performed.

FIG. 5 is a flow chart showing the procedure of the congestion detection carried out by the congestion detection section 22 which constitutes the congestion control circuit 9. One embodiment of the configuration of the congestion detection unit 22 will be described later with reference to FIG.

The congestion detector 22 receives the header information (RT, CL) of the arrival cell notified by the write / read control circuit 8.
The number of arriving cells A (CL
S, RT) and the number of lost cells L (CLS, RT) are measured, and the queue Q (CLS, RT) in which congestion has occurred and the queue Q (CLS, R) in which the loss rate is small and in an excessive quality state
T) and are detected. When the number of arriving cells is A and the number of lost cells is L, the value of the cell loss rate is calculated by the following formula. CLR (measured value) = L / A By comparing CLR (measured value) with the maximum loss rate CLRmax, the communication state of the queue is classified into the following three states. (1) Congestion state: When CLR ≧ CLRmax is satisfied. (2) Appropriate state: CLRmax> CLR ≧ (CLRma
x / l) holds.

(3) Excessive quality condition: CLR <(CLRm
ax / l) holds. However, l = 10, 100, 1000, ...

In order to identify the above three states, the threshold value A
Use th and Lth. There is the following relationship between these thresholds and the maximum loss rate. Lth / Ath = CLRmax (CLS) The threshold value Ath is equal to the number of sample cells required to measure the cell loss rate, and controls the measurement accuracy of the loss rate together with the threshold value Lth. For example, CLRmax (3) ≦ 1/10
^In the case of ⁶ , Lth = 10 and Ath = 10 ⁷ are set in order to make the number of significant digits of the measured loss rate two digits. The threshold value is set by the control unit 11 at the time of initial setting.

When a cell loss notification arrives at the congestion detection circuit 22 from the write / read control circuit 8 via the signal line 16 (step 501), the number L of lost cells and the number A of arrived cells are each incremented by 1 (step 502). 5,
03). This increment operation is performed for each queue based on the header information (RT, CLS) that arrives together with the cell loss signal. The increment operation of the number of arriving cells A is also performed when the cells arrive.

Next, the number of lost cells (L) is the threshold value (Lth).
Is determined (step 504). If equal, it is determined whether the number of arriving cells (A) is smaller than the threshold value (Ath) (step 505). A ≦ Ath
In the case of, L / A ≧ Lth / Ath = CLRmax (Equation 10) holds, so it is determined that congestion has occurred in the queue Q (CLS, RT), and the queue Q (CLS, CLS, (RT) displays congestion occurrence in the area (step 506), issues a congestion detection report to the control unit 11 (step 507), and initializes the values of the lost cell number L and the arrival cell number A (steps 508 and 509). The routine is finished (step 510).

At decision step 504, L = Lth
Otherwise, L is less than Lth. In this case, A is compared with Ath in step 511. If A> At
In the case of h, since L / A <Lth / Ath = CLRmax (Equation 11) holds, the congestion state is not established. In this case, the number A of arriving cells is the number A of arriving cells required to measure the loss rate.
If it exceeds th, the number L of lost cells and the number A of arriving cells are initialized (steps 508 and 509), and the process ends (step 510).

When A is larger than 1Ath in step 512, L / A <Lth / (1Ath) = CLRmax / l (Equation 12) (where, 1 = 10, 100, 1000, ...) Is established. In this case, the control unit 1 judges that it is in the excessive quality state.
After notifying 1 (step 513), the process proceeds to step 508.

In step 511, A is Ath
In the following cases, since the number of arriving cells has not reached the number of samples Ath required for measuring the loss rate, this routine is terminated without initializing the number L of lost cells and the number A of arriving cells (step 510).

In the above embodiment, the presence / absence of congestion is detected only by comparing the number of arriving cells and the number of lost cells with a predetermined threshold value. Can be achieved with.

FIG. 6 shows an example of the configuration of the congestion detector 22. The congestion detection unit 22 uses the table memories 601 and 602.
, Selectors 603, 607, 615, size determination circuits 608, 609, 610, and addition circuits 604, 606.
A multiplication circuit 605, gate circuits 617 and 618,
AND circuits 611 and 612, a NAND circuit 613,
And a congestion display register 616.

In the table memories 601, 602, the number A of arriving cells, the threshold Ath, the number L of lost cells and the threshold Lth are stored.
Are stored corresponding to the queue Q (CLS, RT) 12.
When the cell arrives, the signal line 1 from the write / read control circuit 8
Header information (R
T, CLS) is input to the table memory 601 as an address, whereby the number of arriving cells A (CL) from the table memory 601 to the queue Q (CLS, RT) is input.
S, RT) is output. In the following description, unless otherwise specified, the number of arrival cells A (CL
S, RT) is simply referred to as "A". The number of arriving cells A is input to the adder circuit 604 and incremented by 1, and then the table memory 601 is passed through the selector circuit 603.
Will be rewritten to. Note that the selector 603 outputs the initial value “1” when the number of arriving cells A is initialized (step 508 in FIG. 5).

The lost information notified from the write / read control circuit 8 via the signal line 16 when the cell is lost is the gate 6
It is input to 18 as a control signal. The gate 618
Outputs the header information (RT, CLS) of the arriving cell 202 only when the cell is lost. The above header information (R
T, CLS) is input as an address to the memory 602, whereby the queue Q (R
The threshold values Ath and Lth corresponding to (T, CLS) and the number of lost cells L are output. The number L of lost cells is incremented by 1 in the adder circuit 606 (step 50).
2) The data is rewritten in the lost cell number (L) storage area of the memory 602 via the selector 607. The selector 607 outputs an initial value "1" when L is initialized (step 509).

As described above, each time a cell arrives at the cell buffer 4, the number of arriving cells A read from the memory and incremented, and the threshold values Ath, L, and Lth read when the cell is lost in the cell buffer 4. Is used to perform the congestion detection operation described with reference to FIG.

The size judgment circuit 608 judges the size of the arrival cell number A and the threshold value Ath (steps 505 and 511), and the size judgment circuit 609 judges the size of the arrival cell number A and the threshold value lAth (step 512), the size value. The determination circuit 610 is
Judgment of the number L of lost cells and the threshold Lth (step 50)
4) Perform each.

The outputs of the size determination circuits 610 and 608 are AN.
It is input to the D circuit 611 and L = Lth (step 50
4) and A ≦ Ath (step 505), the AND circuit 611 outputs a congestion signal. The congestion signal is transmitted via the signal line 18 to the control unit 11
(Step 507), and at the same time, it is also input to the selector 615 as a control input. Selector 61
5 receives the congestion signal, the congestion display register 616
The flag "1" indicating the congestion state is stored in (step 5).
06). The congestion display register 616 stores the queue Q (C
LS, RT) corresponding congestion display information is stored, and RT / CLS of the arriving cell is given to the write address WA of the congestion register 616 via the gate 617. The gate 617 is controlled so as to transmit the RT / CLS to the register 616 only when the lost signal arrives. The control unit 11 is also notified of A and Ath together with the congestion signal via the signal line 18.

From the magnitude determination circuit 610, L = Lth
A signal indicating (step 504) is output, and this signal is transmitted via the OR circuit 614 to the selectors 603 and 607.
Entered in. At this time, the selectors 603 and 607 select “1” respectively, and the initial values are stored in the A and L storage areas of the memories 601 and 602, whereby the initialization of A and L (steps 508 and 509) is performed. Be done.

The NAND circuit 613 is the size determination circuit 61.
0 and 608 are received and L ≠ Lth (step 50
When the two conditions 4) and A> Ath (step 511) are satisfied, the detection signal is output. The output signal of the NAND circuit 613 is input to the selectors 603 and 607 via the OR circuit 614. At this time, the selectors 603 and 607
Selects "1" respectively, which initializes the values A and L (steps 508, 509).

The AND circuit 612 is the NAND circuit 6 described above.
13 output and the output of the magnitude determination circuit 609 are input,
When A ≧ lAth (step 512) is satisfied, a notification signal indicating excess quality is output. This notification signal is notified to the control unit 11 via the signal line 18 (step 51).
3). It should be noted that the controller 11 is connected to the RT via a signal line 18.
/ CLS, A, Ath, L, Lth are also notified.

By the circuit operation described above, the congestion state,
Alternatively, the queue in the excessive quality state is detected, and the control unit 1
1 is notified, and the fact that the queue is congested is stored in the register 616. The threshold values Ath and Lth are set in the memories 601 and 602 via the signal line 18 by the control unit 11 at the time of initial setting. Further, the control unit 11 releases the congestion display flag stored in the congestion display register 616 via the signal line 18. The cancellation of the congestion display flag will be described later with reference to FIGS. 11 and 13.

According to the above congestion detection method, L = Lt
When h is satisfied, the congestion detection signal is output. Therefore, if congestion control is performed at high speed to prevent subsequent cell loss, the cell loss rate can be calculated as CLRmax = Lth / Ath.
It can be:

Next, with reference to FIG. 7, the configuration and operation of the bandwidth accommodation unit 13 for performing congestion control will be described.

The bandwidth accommodating portion 13 has the queues Q (CLS,
RT) read band BW (CLS, R)
RT / CLS is output according to T), and this is output to the signal line 17
Is supplied to the write / read control circuit 8 via
The congestion display register 616 is monitored, and if there is a queue in the congestion state, a spare band is given to the queue in the congestion state. The write / read control circuit 8 reads a cell from the corresponding Q (CLS, RT) of the cell buffer 4 in accordance with RT / CLS given from the band interchange unit 13.

As shown in FIG. 7, the bandwidth interchange unit 13 has an RT counter 701 and a congestion class register 702.
, Maximum value registers 703 and 706, and timer 704
, CLS table 705, and match detection circuits 707 and 7
08, 711, a decoder 709, a register 711,
714 and selectors 712 and 713.

First, the operation of outputting RT / CLS to the signal line 17 according to the read band BW will be described.
The RT counter 701 designates an output line number (RT) as an output destination of the cell read from the cell buffer 4. Since one cell is read out for each output line within one cell time (period), the RT counter 701 is
It is incremented by 1 at a cycle of "1 cell time / number of output lines n", and count values of 1 to n are output in ascending order within 1 cell time. The maximum value register 703 stores the value of the number of output lines n.

The timer 704 is the RT counter 701.
Incrementing by 1 in 1-cell time cycle with the output from 1 to Tm within 1-Tm (cell time)
The count value of ax is output in ascending order. That is, the timer 704 sets the time value to 1 to Tma in cell time units.
Output in the x range. The maximum value register 706 stores the maximum value Tmax of the time value.

The output line number (RT) output from the RT counter 701 and the time value output from the timer 704 are input to the CLS table 705. In the CLS table 705, the quality class number (CL to be read out from the cell corresponding to the time value and the output number (RT) is read.
S) is stored.

FIG. 8 shows an example of data stored in the CLS table 705. Column 801 is the output line number (R
T), column 802 shows the time, and column 803 shows the quality class number (CLS) that has the cell read right. Figure 8
In order to simplify the description, only the table portion corresponding to the output line RT = n is shown, and the portions corresponding to the other output lines are omitted from the drawing.

In this example, quality class 1 has a ratio of 4 cell read rights within 12 cell hours. Therefore,
The read bandwidth of class 1 is BW (1, n) = 4/12 × 156 = 52 Mbps. Similarly, the allocated bandwidths of class 2 and class 3 and the reserve bandwidth Res are as follows. BW (2, n) = 4/12 × 156 = 52 Mbps BW (3, n) = 3/12 × 156 = 36 Mbps BW (res, n) = 1/12 × 156 = 12 Mbps Storage in the CLS table 705 The quality class number is stored by the control unit 11 at the time of initial setting in the read bandwidth BW.
In accordance with the above, it is performed via the signal line 18.

The quality class number (CLS) output from the CLS table 705 corresponds to the selector 713 and the signal line 17.
To the write / read control circuit 8 via. R
The output of the T counter 701 is also given to the write / read control circuit 8 via the signal line 17. That is, on the signal line 17, RT / CLS corresponding to the read band BW
Is output and the write / read control circuit 8 outputs the RT /
A cell is read from the queue Q (CLS, RT) specified by CLS.

Next, the operation of allocating the spare band to the congestion queue will be described.

The congestion class register 702 stores the quality class number (CLS) of the queue in the congestion state corresponding to the output line.
I remember. Further, the register 710 stores a bit pattern indicating the reserve band. Match detection circuit 71
1 is the output of the CLS table 705 and the register 71
0 is compared with the stored bit pattern indicating the reserve band. The coincidence detection signal is input to the selector 713 as a control input, and at this time (when the output of the table 705 indicates the reserve band), the selector 713 selects the class number stored in the congestion class register 702 and CL
Output as S. By this, for the queue Q (CLS, RT) in the congestion state, the spare band BW (re
s, RT) is assigned.

Next, the operation of storing the quality class number (CLS) of the congestion state queue in the congestion class register 702 based on the congestion display flag stored in the congestion display register 616 will be described.

The output line number (RT) output from the RT counter 701 and the quality class number (CLS) output from the CLS table 705 are stored in the congestion display register 61.
6 is input as a read address (RA). RT
If the queue Q (CLS, RT) designated by C and LS is in the congestion state, the value "1" indicating the congestion is output from the congestion display register 616. When the match detection circuit 707 detects that the output of the congestion display register 616 is "1", it inputs a match detection signal to the decoder 709. When the output of the register 616 is "1", the decoder 709
In response to the control signal given from the selector 712,
Quality class number output from table 705 (CL
S) is selected and given to the congestion class register 702 for storing the congestion class corresponding to the output line (RT).

The coincidence detection circuit 708 stores the quality class number in congestion stored in the register 702 and the table 7
A match with the quality class number output from 05 is detected. When the output of the table 705 matches the output of the register 702 and the output of the register 616 is not “1”, it is determined that the congestion of the class set in the register 702 has been resolved, and the selector 712 stores it in the register 714. Select and output the bit pattern indicating the reserved band
The content stored in the register 702 is changed to the bit pattern of the reserve band (res). If the output of the register 702 and the output of the table 705 do not match and the output of the register 616 is not “1”, the register 702
It is determined that the congestion of the class stored in (1) is still continuing, and the selector 712 selects the output of the register 702.

As described above with reference to FIGS. 5 to 7, the congestion detection unit 22 detects the queue Q (CLS, RT) in the congestion state based on the number of lost cells, and the congestion display register 6
In the storage area corresponding to the queue Q (CLS, RT) in 16, the flag information indicating the occurrence of congestion is stored. The band interchange unit 13 uses the RT / CLS corresponding to the read band BW.
Is output to the signal line 17, and the congestion display register 61
A spare band is allocated to the queue in the congestion state according to the stored contents of 6.

In the case of the table structure shown in FIG. 8, since the time zone for the spare band allocation processing is prepared once every 12 cell times, the worst case is 12 cell hours after the congestion is detected. After that (after about 32 μs), the allocation of the spare band to the congestion queue can be completed. That is, when the number of lost cells becomes equal to Lth, congestion is detected and a spare band is allocated. In this case, if a spare band with sufficient capacity is prepared for the congestion queue, loss of cells after spare band allocation can be prevented, and cell loss occurs within 12 cell time until completion of spare band allocation. Unless otherwise, the cell loss rate can be controlled to be CLRmax = Lth / Ath or less.

Next, the configuration diagram shown in FIG. 9 and FIGS.
The configuration and operation of the control unit 11 will be described with reference to the flowchart shown in FIG.

As shown in FIG. 9, the control unit 11 includes a call processing processor 901, a ROM 902, and an optimizing unit 90.
3, a required bandwidth storage unit 904, and a bandwidth management memory 90
5, etc.

The control unit 11 responds to the call setup / call disconnection processing in response to the call origination request and the call disconnection request transmitted from the subscriber terminal, and the congestion notification and excess quality notification transmitted from the congestion control circuit 9. Perform optimization processing. The call origination request and the call disconnection request arrive at the control unit 11 via the input line 1, the multiplexing unit 3, the cell buffer 4, the demultiplexing unit 5, the signal line 20, and the adaptation circuit 10.

At the time of making a call request, the subscriber receives the number information indicating the communication partner (destination device) and the traffic characteristics (maximum speed M
AX (bps), average speed AVE (bps), burst length BURST (cell)), and quality class number (CLS)
Declare. When the adaptation circuit 10 receives the call request and the declared value data, the adaptation circuit 10 temporarily holds the received information and interrupts the processor 901.

In response to the interrupt, the processor 901 reads out the bit pattern indicating the call request and the declared value data from the adaptation circuit 10. At the time of the call request, the processor 901 performs the control operation according to the flowchart shown in FIG. First, the table 915 is referred to based on the destination device number, and the output line (RT) connected to the destination device is determined. Also, the declared CLS
And the determined RT, the queue Q (CLS, RT) used by the subscriber is determined (step 1002 in FIG. 10).

The band required for communication between the subscriber and the destination device, that is, the required band ρ vir (bps) is the declared traffic characteristics, quality class, queue Q (CLS, RT) used by the subscriber. Capacity CP (CLS, RT),
It depends on the read band BW (CLS, RT). For example, communication speed (MAX, AVE), burst length (BUR)
The larger the ST) or the smaller the required cell loss rate, the larger the required band ρvir. Further, the larger the queue capacity CP and the read bandwidth BW, the more the required bandwidth ρvir.
Can be small.

The size of the required band ρvir can be calculated by mathematical analysis or computer simulation. This calculation need not be performed each time a call request is made, and may be calculated off-line in advance. The required bandwidth ρvir table 912 is a memory for storing the required bandwidth ρvir calculated in advance as a table, and the address decoder 911 uses the declared value (MAX,
AVE, BURST), the quality class (CLS) to which the subscriber belongs, and the queue capacity (CP) used by the subscriber
And the read band (BW) based on the table 91.
The address for reading the required band ρvir from 2 is output.

The processor 901 reads the required bandwidth ρvir from the table 912 (step 1003), and adds this to the total sum ρ (bps) of the required bandwidth ρvir of the calls already accommodated in the queue Q (CLS, RT) (step 1004). ). The value of ρ is the queue Q (CLS, RT)
Correspondingly stored in the memory 914.

When ρ + ρvir <ρmax (Equation 13) is established, the call request is permitted and the call is accepted in the queue Q (CLS, RT). Note that ρmax indicates the maximum band that can be accepted, and is stored in the memory 914 corresponding to the queue Q (CLS, RT).

If the calculated value of the required band ρvir does not include an error, ρmax = BW (CLS, RT) (Equation 14) holds. However, in the normal case, the required bandwidth ρv
Since an approximation formula is used to calculate ir, the calculated value includes an error due to the influence of approximation, and the above formula 14 is not always established.

When Expression 14 is satisfied, ρ is changed according to the following expression (step 1005) and stored in the memory 914. ρ = ρ + ρvir ... (Equation 15) Next, call setup is performed (step 1006). Call setup is the provision of an identifier (VPI / VCI) to a subscriber, RT
/ CLS table 13 and processing such as setting of the table 913. The table 913 stores the required bandwidth ρvir, the output line number (RT), and the quality class number (CLS) in correspondence with VPI / VCI.

When these call setting operations are completed, a call acceptance notice is sent to the subscriber terminal (step 1007). The above notification is transmitted to the subscriber terminal via the adaptation circuit 10, the multiplexing unit 3, the cell buffer 4, the demultiplexing unit 5, and the output line 7. The call acceptance notification includes the assigned identifier (VPI / VCI), and the assigned identifier is set in the VPI / VCI area of the cell received from the subscriber terminal thereafter.

If the expression 13 is not established in step 1004, a call loss notification is sent to the subscriber terminal (step 1009).

When the call disconnection notification arrives from the subscriber terminal, the adaptation circuit 10 interrupts the processor 901 as in the case of the call setting request described above. Upon receiving the call disconnection notice, the processor 10 executes the control operation according to the flowchart of FIG.

First, the required bandwidth ρvir is read from the table 913 based on the VPI / VCI of the arriving cell (step 1102), and ρ in the memory 914 is changed based on the following equation (step 1103). [rho] = [rho]-[rho] vir (Equation 16) Next, call release processing is performed (step 1104). In the call release process, the RT / CLS table 13 and the table 9 are
At 14, the VPI / VCI area that is the disconnection target is cleared. Steps 1105 to 1107 in FIG. 11 will be described in the operation of the optimization unit 903 described below.

The optimizing unit 903 comprises interface memories 906 and 910, a ROM 907, an optimizing processor 909, and an OR circuit 908. RO
A program executed by the processor 909 is stored in the M907.

The term "optimization" as used herein means the optimization of ρmax on the right side of Expression 13. As described in Expression 14, since the calculated value of the required band ρvir includes an approximation error and the like, Expression 14 does not always hold. Therefore, the value of ρmax needs to be optimized.
In this embodiment, the value of ρmax is optimized for the quality class and the output line. To simplify the description, ρma corresponding to the class number CLS and the output line number RT
x (CLS, RT) is simply ρm unless otherwise specified.
Notated as ax.

When the congestion notification arrives, the optimization unit 903 determines that congestion has occurred because ρmax is too large, and changes ρmax shown in Equation 7. [rho] max = [rho]-[Delta] (Equation 7) However, [Delta] = a (Ath-A) ... (Equation 17), and A represents the number of cells that arrived while Lth cells were lost, The smaller A is, the higher the cell loss rate is. Therefore, in this embodiment, the value of ρmax is changed by subtracting the correction value Δ that increases as A decreases from ρ. Note that a in the correction value Δ is a positive constant.

When congestion is detected, the congestion control circuit 9
Congestion notification and class number C of queue 12 in congestion state
LS, the output line number RT, the threshold value Ath assigned to the queue 12, and the number A of cells arriving at the queue 12.
To the interface memory 91 via the signal line 18.
Store in 0.

The interface memory 910 is composed of a quality status storage area, an A / Ath storage area, an L / Lth storage area, and an RT / CLS storage area. A bit pattern indicating a congestion notification is stored in the quality status storage area. It Further, the interface memory 910 has a FIFO memory structure capable of storing a plurality of congestion notifications and excess quality notifications, and the congestion control circuit 9 notifies the processor 909 when the congestion notifications and the like are stored in the memory 910. Send an interrupt signal.

The processor 909 receiving the above interrupt
When the contents of the quality state storage area of the memory 910 are read and if the congestion notification is stored, first, as shown in the flowchart of FIG. 12, first, A, Ath, RT,
The value of CLS is read from the memory 910, and formula 17 is executed (step 1202).

Next, the processor 909 stores the congestion notification and Δ, RT and CLS in the interface memory 906, and sends an interrupt signal to the processor 901. The processor 901 stores ρmax stored in the memory 901.
The value of (RT, CLS) is changed according to Expression 7 (step 1203). Further, a bit pattern indicating congestion is stored in the congestion display area corresponding to the quality class number CLS and the output line number RT in the memory 914 (step 1204). As a result, the routine of FIG. 12 ends (step 1205).

When the excess quality notification arrives, ρ = ρmax
Is satisfied, it is determined that an excess quality state has occurred, and ρmax is changed according to Expression 8. ρmax = ρ + Δ (Equation 8) Δ = b {Lth (A / L) -Ath} (Equation 18) Here, A represents the number of cells that have arrived before L cells are lost. , Lth (A / L) indicate the number of cells expected to arrive before Lth cells are lost.
In this embodiment, a correction value Δ that increases as the cell loss rate decreases is added to ρ. In addition, b
Is a positive constant.

When the excessive quality state is detected, the congestion control circuit 9 notifies the excessive quality and the queue 1 in the excessive quality state.
2 class number CLS, output line number RT, thresholds Ath and Lth assigned to the queue 12, the number A of cells arriving at the queue 12, and the number L of lost cells in the queue
To the interface memory 91 via the signal line 18.
Store in 0. The excess quality notification is stored in the quality status storage area in the interface memory 910. The congestion control circuit 9 sends an interrupt signal to the processor 909 when the excess quality notification or the like is stored in the memory 910.

The processor 909 receiving the above interrupt
When the contents of the quality state storage area of the memory 910 are read, and if the excess quality notification is stored, the values of A, Ath, L, Lth, RT, and CLS are read from the memory 910 as shown in FIG. Formula 18 is executed (step 1302).

The processor 909 next sends the excess quality notification and the Δ, RT, and CLS to the interface memory 906.
Then, an interrupt signal is sent to the processor 901.
The processor 901 searches the memory 914 for Q (CL
For the used bandwidth ρ (CLS, RT) of (S, RT), it is checked whether ρ (CLS, RT) = ρmax (CLS, RT) (Equation 19) holds (step 130).
3).

If Equation 19 holds, Equation 8
Is executed (step 1304), and the value of ρ stored in the memory 914 is updated. Furthermore, the congestion display area of the memory 914 is searched, and when Q (CLS, RT) is in the congestion state, the congestion display is cleared and the signal line 1
The congestion display stored in the Q (CLS, RT) area of the congestion display register is cleared via 8 (step 13
06) and terminates the routine of FIG. 13 (step 130).
7).

The above-mentioned operation of clearing the congestion display is shown in FIG.
It is also executed at the time of the call disconnection request shown in. When the call is disconnected (step 1104), it is displayed in the memory 914 that the queue in use by the call to be disconnected is in a congested state (step 1106), and when ρ <ρmax is satisfied due to the call disconnection ( The step 1105) clears the congestion display (step 1107). The target to be cleared is the congestion display stored value for the call to be disconnected in the memory 914 and the register 616.

FIG. 14 shows ρma in the above-mentioned present invention.
It is the figure which showed notionally the process of optimization of x. The vertical axis 1406 of the graph represents ρmax, and the horizontal axis 1407 represents elapsed time.

Here, the solid lines 1401, 1402, 140
3 shows the variation of ρmax, respectively, and the broken lines 1404,
1405 shows the converged value (optimized value) of ρmax. A straight line 1401 indicates ρmax when there is no error in the calculation of ρvir (ideal state), and curves 1402 and 140
3 shows the variation of ρmax when there is an error. ρm
The initial value of ax is BW, and the curves 1402 and 1403
Correspond to the conditions of the following expressions 20 and 21, respectively. ρmax (convergence value)> BW (Equation 20) ρmax (convergence value) <BW ... (Equation 21) As apparent from the above description, according to the present invention, ρm
ax can be optimized. In general analysis, as a result, the approximation on the safe side is performed so as to satisfy Expression 20, and the virtual band ρ
Since vir is calculated and operated under the condition of ρmax ≤ BW (Equation 22), an unused band, that is, an unused band ≥ρmax (convergence value) -BW ... (Equation 23) Can be effectively used.

In addition, even if the congestion control circuit 9 is used to quickly allocate the spare band to the congestion queue to optimize ρmax by utilizing the above-mentioned congestion occurrence,
The cell loss rate never exceeds the required value CLRmax.
When an excessive quality notification arrives, ρmax is increased to actively generate congestion, and ρmax is optimized by the control unit 11 based on the number of lost cells notified from the congestion control circuit 9. By doing so, the time required for convergence can be shortened. In addition, since the probability of occurrence of congestion decreases after the optimization is completed, for example, when the size of the spare band is reduced, the band can be used more effectively.

Although buffers are provided for the quality class in the embodiment, these buffers may be provided for the virtual path (VP). In that case, the call admission control is optimized for the VP. be able to.

[0126]

As is apparent from the above description, according to the present invention, the output line band is divided into a dedicated band and a spare band for a plurality of queues, and the number of lost cells is observed corresponding to the queues. As a result, when congestion occurs in a certain queue, it is possible to instantly allocate a spare band to the congestion queue and quickly get out of the congestion state. Also, in the control unit in charge of call admission control, by optimizing the usage rate for queues based on the cell loss situation,
It is possible to improve the usage rate of the output line.

[Brief description of drawings]

FIG. 1 is a block diagram showing an embodiment of a node device to which a congestion control method of the present invention is applied.

FIG. 2 is a diagram showing a configuration of a cell.

FIG. 3 is a diagram showing a configuration of a cell buffer 4 having a plurality of queues.

FIG. 4 is a diagram showing a configuration of a write / read control circuit 8.

FIG. 5 is a flowchart for explaining the congestion detection method of the present invention.

6 is a diagram showing a specific configuration of a congestion detection unit 22 in FIG.

7 is a diagram showing a specific configuration of a band accommodation unit 13 in FIG.

8 is a diagram showing a specific configuration of a CLS table 705 in FIG.

9 is a diagram showing a detailed configuration of a control unit 11 in FIG.

FIG. 10 is a flowchart of a call request process executed by the control unit 11.

FIG. 11 is a flowchart of call disconnection processing executed by the control unit 11.

FIG. 12 is a flowchart of an optimization process executed when the congestion notification arrives executed by the control unit 11;

FIG. 13 is a flowchart of an optimization process executed by the control unit 11 upon arrival of an excessive quality state notification.

FIG. 14 is a diagram for explaining an example of the effect of the present invention.

─────────────────────────────────────────────────── ───

[Procedure amendment]

[Submission date] March 29, 1993

[Procedure Amendment 1]

[Document name to be amended] Statement

[Name of item to be corrected] 0126

[Correction method] Change

[Correction content]

[0126]

As is apparent from the above description, according to the present invention, the output line band is divided into a dedicated band and a spare band for a plurality of queues, and the number of lost cells is observed corresponding to the queues. As a result, when congestion occurs in a certain queue, it is possible to instantly allocate a spare band to the congestion queue and quickly get out of the congestion state. Also, in the control unit in charge of call admission control, by optimizing the usage rate for queues based on the cell loss situation,
It is possible to improve the usage rate of the output line.

[Procedure Amendment 2]

[Document name to be amended] Statement

[Name of item to be corrected] Brief description of the drawing

[Correction method] Change

[Correction content]

[Brief description of drawings]

FIG. 1 is a block diagram showing an embodiment of a node device to which a congestion control method of the present invention is applied.

FIG. 2 is a diagram showing a configuration of a cell.

FIG. 3 is a diagram showing a configuration of a cell buffer 4 having a plurality of queues.

FIG. 4 is a diagram showing a configuration of a write / read control circuit 8.

FIG. 5 is a flowchart for explaining the congestion detection method of the present invention.

6 is a diagram showing a specific configuration of a congestion detection unit 22 in FIG.

7 is a diagram showing a specific configuration of a band accommodation unit 13 in FIG.

8 is a diagram showing a specific configuration of a CLS table 705 in FIG.

9 is a diagram showing a detailed configuration of a control unit 11 in FIG.

FIG. 10 is a flowchart of a call request process executed by the control unit 11.

FIG. 11 is a flowchart of call disconnection processing executed by the control unit 11.

FIG. 12 is a flowchart of an optimization process executed when the congestion notification arrives executed by the control unit 11;

FIG. 13 is a flowchart of an optimization process executed by the control unit 11 upon arrival of an excessive quality state notification.

FIG. 14 is a diagram for explaining an example of the effect of the present invention.

 ─────────────────────────────────────────────────── ─── Continuation of the front page (72) Inventor Noboru Endo 1-280, Higashikoigokubo, Kokubunji, Tokyo Inside the Central Research Laboratory, Hitachi, Ltd.

Claims (3)

[Claims] 1. A switching node configured to temporarily store information received in cell format from an input line in a queue in a buffer memory and then output the information to any output line determined by a logical channel number of each cell. , A plurality of queues corresponding to output lines are formed in the buffer memory for each communication quality class, and the band of each output line is divided into a dedicated band and a spare band in advance for the queues, and a cell is provided for each queue. The congestion control method is characterized by observing a change in communication quality due to accumulation of data and allocating a spare band to the queue when the observed value exceeds a threshold value in any of the queues. 2. The utilization rate of each output line is set so that the communication quality temporarily deteriorates from the required quality, and the line utilization rate is changed according to the observed communication quality. The congestion control method according to claim 1, wherein the congestion control method is performed. 3. A switching node adapted to temporarily store information received in a cell format from an input line in a queue in a buffer memory and then output the information to any output line determined by the logical channel number of each cell. , A plurality of queues corresponding to output lines are formed in the buffer memory for each communication quality class, the line utilization is set so that the communication quality temporarily deteriorates from the required quality, and the above line utilization is observed. A call admission control method characterized in that it is changed according to communication quality.