JP3079072B2 - Competition control circuit - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

The present invention relates to an ATM (Asynchronou).
s Transfer Mode) Used for communication. The present invention is suitable for use in an ATM communication network in which cells of different service classes coexist. The present invention is a technique developed for cells in ATM communication, but can be widely applied to packet communication other than ATM communication.

[0002]

2. Description of the Related Art In ATM communication, information is mounted on fixed-length packets called cells, and information is transmitted and received.
At this time, if there are a large number of cells having the same destination and they are sent out to the same line at the same time, collisions between the cells occur, and the number of cells to be discarded increases. When the number of cells to be discarded increases, the transmission source needs to perform retransmission, so that the throughput of the ATM communication network decreases.

In order to avoid such a situation, an ATM is used.
The switch and other cell output route control devices perform cell collision avoidance control called contention control. A conventional conflict control circuit will be described with reference to FIGS. FIG. 21 is an overall configuration diagram of a conventional competition control circuit.
FIG. 22 shows an ATM in which cells of different service classes coexist.
FIG. 2 is an overall configuration diagram of a conventional contention control circuit in a communication network.

In FIG. 21, 1-1 to 1-4 are input lines, 17-1 to 17-4 are read control circuits, 65 is a ring arbiter device, and 40-1 to 40-4 are queuing buffers. Cells A to D transferred from input lines 1-1 to 1-4 are temporarily stored in queuing buffers 40-1 to 40-4. The read control circuits 17-1 to 17-4 are
When a cell arrives or waits, a read request is sent to the ring arbiter device 65. The ring arbiter device 65 includes a read control circuit 1 having a read request.
Read permission is sent to 7-1 to 17-4 in order.

Next, a conventional contention control circuit in an ATM communication network in which cells of different service classes coexist will be described. As shown in FIG. 22, each buffer unit 2-1
For ~ 2-4, high priority class (hereinafter referred to as H class)
Buffers 4-1 to 4-4 and low-priority class (hereinafter, L class) buffers 5-1 to 5-4 are provided. The operation of the buffer unit 2-1 will be described taking the input line 1-1 (# 1) as an example.

When a cell is input to the buffer unit 2-1,
The control unit (not shown) of the buffer unit 2-1 refers to the quality class identifier in the header of the cell, and identifies the H class or the L class. The selector 33-1 selects H
The data is distributed to the class buffer 4-1 and the L class buffer 5-1.

In the buffer unit 2-1, cells AH1, AH2 and AH3 are stored in the H class buffer 4-1 and cells AL1 are stored in the L class buffer 5-1. When the cells of the H class are stored, the selector 6-1 preferentially selects the cells of the H class regardless of the presence or absence of the cells of the L class. The L class cell is selected by the selector 6-1 only when the H class cell is not stored in the H class buffer 4-1.

Therefore, the buffer unit 2-1 is an H class cell AH1, and the buffer unit 2-2 is an L class cell BL.
1. The buffer unit 2-3 sends a cell output request signal of the L class cell CL1 to the competition control unit 90, and the buffer unit 2-4 sends a cell output request signal of the L class cell DL1.

In the ring arbiter device 65, assuming that the transmission right is currently on the input line 1-1 (# 1), the cell A
H1 is sent first. Subsequently, the transmission right is the input line 1-2.
(# 2), and the cell BL1 is transmitted. Similarly, thereafter, the cell CL1, the cell DL1, the cell AH2,
Cell BL2 is transmitted.

[0010]

In such a conventional ring arbiter of a competitive control circuit, each of the input lines 1-1 to 1-1 is used.
Only the read number equality between −4 and −4 is guaranteed, and the cell arrival order is not guaranteed.

For example, FIG. 23 is a time chart showing an output state of the conventional competition control circuit shown in FIG.
Cell C of input line 1-3 (# 3) is composed of other cells A, B,
Arrived late compared to D. In FIG. 23, cell D (t
Cell C (arriving at t = 3) is read earlier than arriving at = 1. In this way, the overall time order is not guaranteed at all, but only the equality of the number of readings between input lines is guaranteed. In this example, cells A, B, C, and D are stored in the queuing buffers 40-1 to 40-4.
It is said that there were no other waiting cells.

In the case of a conventional contention control circuit in an ATM communication network in which cells of different service classes are mixed as shown in FIG. 22, a large number of H class cells are accumulated in a buffer section on an input line. Even in such a case, in order to maintain equality in the number of readouts between input lines, cells of the L class in other input lines may be read out first.

FIG. 24 is a time chart showing the output state of the conventional contention control circuit shown in FIG. 22. In this example, after the H-class cell AH1 is transmitted from the buffer unit 2-1, it is still at H level. Although the cells AH2 and AH3 of the class remain, the cell BL1 of the L class is transmitted from the buffer unit 2-2.
3 to L class cell CL1, buffer unit 2-4 to L
The cell DL1 of the class is transmitted. Thus, the H-class cell AH2 is transmitted only after the L-class cell DL1 is transmitted from the buffer unit 2-4. Therefore, the quality of the H class may be degraded.

When the size of the ATM switch becomes large, the ring arbiter must monitor all the read control circuits, and it takes a long time for the ring arbiter to make a round. In addition, when expansion is performed, after increasing the number of input lines, complicated work such as changing the program of the ring arbiter apparatus 3 that controls the entire system is required, so that expandability is low.

The present invention has been made in view of such a background, and an object of the present invention is to provide a contention control circuit capable of guaranteeing a time order. An object of the present invention is to provide a contention control circuit capable of performing contention control autonomously and decentralized. An object of the present invention is to provide a contention control circuit with high expandability. An object of the present invention is to provide a contention control circuit capable of performing contention control for each quality class. An object of the present invention is to provide a contention control circuit that does not degrade the transmission quality of H class cells due to the traffic of L class cells.

[0016]

SUMMARY OF THE INVENTION The present invention simply compares a cell transferred from an upstream with a priority state of a cell output by itself without grasping a state of a waiting cell of all input lines. The most important feature is that complete competition control can be performed.

The prior art is different from the prior art in that it does not have a centralized ring arbiter, that it can perform competitive control in a distributed manner, and that the output is determined in consideration of the time sequence including the arrival time. What you can do is different.

That is, the present invention relates to a contention control circuit, which includes a plurality of buffer units (2-1 to 2-4) for temporarily storing cells arriving from a plurality of input lines, respectively, and read out from the buffer units. Contention control means (3-1 to 3-3) for transmitting the output cells to one output line without colliding with each other.
-4, 50).

Here, a feature of the present invention is that each of the plurality of buffer units (2-1 to 2-4) includes a first buffer (40-1 to 40-4), The control means controls the first buffer (40-1 to 40-
4) means (50) for writing information indicating the priority for outputting the cell to the cell input to (4), and the output provided for each of the first buffers (40-1 to 40-4) Contention control unit (3
-1 to 3-4), and each of the conflict control units (3-1 to 3-4)
4) a second buffer (70-1) for temporarily storing cells output from the upstream contention control unit with respect to the output line;
To 70-4) and information indicating the priority described in the first cell among the cells stored in the first buffer and the first cell among the cells stored in the second buffer. Means for comparing (60-1 to 60-4) and cells are selected from the first buffer and the second buffer in descending order of priority according to the comparison result of the comparing means, and the cells are selected for the output line. Output selection means (80-1
~ 80 ~ 4, 7).

[0020] The information indicating the priority may be time information when a cell is input to the first buffer, or the information indicating the priority may be information indicating a time when a cell is input to the first buffer. It can also be information on the waiting time since the request was made.

Further, the above described means can be provided individually for the first buffer, or the above described means can be provided in common for a plurality of the first buffers.

Means for counting the number of cells continuously transmitted with respect to the first and second buffers, and counting the first cell of the first and second buffers from the waiting time information described in the cells. Means for subtracting the counting results of the means and using the result of the subtraction as new waiting time information as information representing the priority.

That is, when assuming a situation where cells are concentrated in a specific buffer, when the last cell comes to the head position of the buffer, the waiting time information written in the cell has a large value. . On the other hand, looking at the buffer in which cells sparsely arrive, the waiting time information described in the cell at the head position of the buffer has a small value.

At this time, for example, when the head cell of the buffer where cells are concentrated and the head cell of the buffer where cells sparsely arrive are the cells arriving at the same time, the cell existing before the cell The waiting time information is determined according to the presence / absence of the cell, so the head cell of the buffer where the cells are concentrated is the head cell of the buffer where the cells arrive sparsely despite the cells arriving at the same time. Since the value of the waiting time information is larger than that of the waiting time information, it is preferentially transmitted.

For example, the waiting time information described in the head cell of the buffer in which cells are concentrated is "10", and the waiting time information described in the head cell of the buffer in which cells sparsely arrive is "1". If the two cells arrive at the same time, the cell with the waiting time information "10" is output with higher priority.
Further, with respect to the following cells, the waiting time information “9”, “8”, “7”,... Follow, and until the cell eventually becomes “1”, the leading cell of the buffer in which the cells sparsely arrive is You will have to wait for the output.

In order to eliminate this unfairness, the number of cells continuously transmitted from the first and second buffers is counted, and the counting result is subtracted from the waiting time information described in the cells, so that a new number is obtained. Generate wait time information. Cell contention control is performed according to the new waiting time information.

In the above example, since the waiting time information of the head cell of the buffer in which the cells are concentrated is "10" and the number of continuous transmission cells of the buffer is "9", the subtraction of 10-9 = 1 is performed. I do. Also, since the waiting time information of the head cell of the buffer in which the cells arrive sparsely is "1" and the number of cells continuously transmitted in the buffer is "0", the subtraction of 1-0 = 1 is performed. Contention control is performed on these new waiting time information. Here, since both are "1", it is determined that the priorities are the same.

The selecting means, when the comparison result of the comparing means indicates that the priority is the same, according to a predetermined read probability from the first buffer and the second buffer, respectively. It is desirable to have a configuration including means (7) for reading out cells. At this time, the read probability is k from the upstream with respect to the output line.
The level (k is a natural number) is 1 / k for the first buffer and (k-1) / k for the second buffer, so that fairness of contention control can be maintained.

Further, when the present invention is applied to an ATM communication network in which cells of different service classes coexist, each of the distributed control units identifies H class and L class cells, and It is characterized in that contention control is preferentially performed for cells of the class. The contention control unit has buffers for the H class and the L class, and the H class cell does not compete with the L class cell at all.
L-class cells do not degrade quality.

That is, the present invention relates to a contention control circuit, comprising a plurality of buffer units (2, 2-1 to 2-4) for temporarily storing cells arriving from a plurality of input lines, respectively, and reading from the buffer units. Contention control means (3, 3) for transmitting the output cells to one output line without colliding with each other.
-1 to 3-4), and the plurality of buffer units (2-
1 to 2-4) respectively, a first high-priority buffer (4) in which cells of a service class with high transmission quality are stored.
A first low-priority buffer (5) in which cells of a service class with low transmission quality are stored, and a first selection for preferentially outputting the cells stored in the first high-priority buffer (4). A conflict control circuit including means (6).

Here, a feature of the present invention is that the contention control means includes the buffer units (2-1 to 2-4).
The contention control units (3, 3-1 to 3-4) are provided for each output line and cascade connected to the output line. A second high-priority buffer (23) in which cells of a service class having high transmission quality are accumulated for cells output from the upstream contention control unit with respect to the output line, and an output from the upstream contention control unit. A second low-priority buffer (24) in which cells of a service class having low transmission quality are stored for the selected cells, and a second which preferentially outputs the cells stored in the second high-priority buffer (23). Selection means (9)
And when one of the first selecting means (6) and the second selecting means (9) outputs a cell of a high service class, reads the cell of the high service class. (6) and read selection means (7) for performing contention control when the second selection means (9) intends to output cells of the same service class, reading the cells and outputting to the output line. is there.

Means (20, 21) for writing information on the waiting time from the input of the cell to the output of the cell input to the first and second high-priority buffers (4, 23). ), And it is preferable that the read selection means (7) reads from the cell having the larger value of the waiting time information.

The first low-priority buffer (5) and the second low-priority buffer may be configured as one buffer (5). That is, the contention control unit may be provided with a buffer for only the H class, and the L class cells transferred to the contention control unit may be transferred to the L class buffer of the buffer unit. As a result, the buffer amount of the contention control unit can be reduced, and the operation algorithm for cell reading selection performed when a cell output request is output from the buffer unit and the contention control unit can be simplified.

The read selecting means (7) may include means for reading cells from the first and second selecting means (6, 9) in accordance with predetermined read probabilities. At this time, the readout probability is k-th stage (k is a natural number) from the upstream with respect to the output line.
By setting 1 / k for the first selecting means and (k-1) / k for the second selecting means, fairness of the competition control can be maintained.

Further, if the read selection means is used, a plurality of buffer units (2-1 to 2-4) for temporarily storing cells arriving from a plurality of input lines, respectively, and a cell read from this buffer unit Control means (3-1 to 3-4, 5) for transmitting the same to one output line without colliding with each other.
0), the contention control means comprises a contention control unit (3) provided for each of the buffer units (2-1 to 2-4) and connected in cascade to the output line. -1 to 3-4), and each competition control unit (3-1)
3-4) includes a buffer (70-) for temporarily storing cells output from the upstream contention control unit with respect to the output line.
1 to 70-4) and read selection means (7) for reading a cell from the buffer unit and the buffer according to a predetermined read probability, respectively, and outputting the read cell to the output line. Can be configured.

At this time, for the k-th stage (k is a natural number) from the upstream with respect to the output line, the read probability is 1 / k for the buffer unit and (k for the buffer of the contention control unit. -1) / k makes it possible to maintain fairness in contention control.

[0037]

BEST MODE FOR CARRYING OUT THE INVENTION

[0038]

【Example】

(First Embodiment) A first embodiment of the present invention will be described with reference to FIG. FIG. 1 is an overall configuration diagram of the first embodiment of the present invention.

The present invention relates to a contention control circuit, which includes buffer units 2-1 to 2-4 for temporarily storing cells arriving from input lines 1-1 to 1-4, respectively.
-1 to 2-4 are output to one output line OU.
A conflict control circuit including conflict control means for sending T without colliding with each other.

Here, a feature of the present invention is that the buffer units 2-1 to 2-4 are provided with queuing buffers 40-1 to 40-4, respectively. A timer 50 which is a means for writing information indicating the priority for outputting the cell to the cell input to .about.40-4;
-1 to 40-4, each of which includes cascade control units 3-1 to 3-4 connected in cascade to the output line OUT. Line OUT
Buffers 70-1 to 70-4 for temporarily storing cells output from the upstream contention control unit, and a head cell and a waiting buffer among cells stored in the waiting buffers 40-1 to 40-4. 70-1 to 70-
4, timer value comparison circuits 60-1 to 60-4, which are means for comparing the information indicating the priority described in the head cell among the cells stored in No. 4 and the timer value comparison circuits 60-1 to 60-4. According to the comparison result of 60-4, the waiting buffers 40-1 to 40-4 and the waiting buffer 70
A selector 8 which is a selecting means for selecting cells from -1 to 70-4 in descending order of priority and outputting to the output line OUT
0-1 to 80-4. In the first embodiment of the present invention, the information indicating the order is time information when cells are input to the queuing buffers 40-1 to 40-4.

The operation of the first embodiment of the present invention will be described with reference to FIGS. FIG. 2 is a block diagram of the buffer unit 2-i and the contention control unit 3-i according to the first embodiment of the present invention (i = 1 to 4). FIG. 3 is a time chart showing an output state in the first embodiment of the present invention. 3-
1 to 3-4 are contention control units, 60-1 to 60-4 are timer value comparison circuits, 70-1 to 70-4 are queuing buffers for cascade connection, and 80-1 to 80-4 are 2: 1. Selectors 50-1 to 50-4 are timers for stamping arrival times.

In FIG. 1, cells A, B, C,
D, the arrival time is written by the synchronized timers 50-1 to 50-4, and the waiting buffer 40-1
~ 40-4.

In each of the contention control units 3-1 to 3-4, the queuing buffers 40-1 to 40-4 and 70-1 to 70-
The timer values stamped on the header portion of the cell stored in No. 4 are compared by timer value comparing circuits 60-1 to 60-4. In the example of FIG. 2, the timer value of the cell A is "1" and the timer value of the cell C is "3", so that the cell A has priority.
Of course, the timers 50-1 to 50-4 may be finite counter values that are long enough.

If no cells are stored in the queuing buffers 70-1 to 70-4 or 40-1 to 40-4, the cells stored in the other buffer are output preferentially without comparison. Needless to say. If the queuing buffers 70-1 to 70-4 cannot receive the read permission, the BP (back pressure) stops the reading in the upper stage. The result is output to the output line OUT in the order of arrival at all the input lines 1-1 to 1-4 as shown in FIG.

(Second Embodiment) A second embodiment of the present invention will be described with reference to FIG. FIG. 4 is an overall configuration diagram of the apparatus according to the second embodiment of the present invention. In the device of the second embodiment of the present invention, in order to realize the operation of the timers 50-1 to 50-4 of the device of the first embodiment of the present invention, one timer 50 is connected to all the buffer units 2-1.
To 2-4 are provided in common. This reduces the number of timers and facilitates synchronization.

(Third Embodiment) A third embodiment of the present invention will be described with reference to FIGS. FIG. 5 is an overall configuration diagram of the device according to the third embodiment of the present invention. FIG. 6 is a block diagram of the contention control circuit according to the third embodiment of the present invention. 51-1 to 51-
Numeral 4 denotes a waiting time writing circuit of the waiting buffers 40-1 to 40-4, which sets a point of time when each cell arrives at "0", gives a trigger for each cell until reading, and increments by one. The cell read as a result has the time information of the waiting time in the header.

The contention control unit 3-i shown in FIG. 6 compares the value of the waiting time of the cell arriving from the upstream with the value of the waiting time of the cell output from the queuing buffer 40-i by a waiting time comparing circuit 60 '. By comparing with -i, the cell that has arrived the oldest from the present time can be output. Also, in this case, a synchronized absolute time timer is not required. In the example of FIG. 6, the waiting time of the cell A is "2" and the waiting time of the cell C is "7", so that the cell C is output with priority.

(Fourth Embodiment) The fourth embodiment of the present invention is shown in FIGS.
This will be described with reference to FIG. FIG. 7 is a diagram showing a cell arrival state for explaining the fourth embodiment of the present invention. FIG. 8 is a diagram showing a cell accumulation state for explaining the fourth embodiment of the present invention. FIG. 9 is an overall configuration diagram of the fourth embodiment of the present invention.
FIG. 10 is a diagram showing a contention control circuit according to a fourth embodiment of the present invention. FIG. 11 is a diagram showing the result of contention control according to the fourth embodiment of the present invention.

In the fourth embodiment of the present invention, a specific input line 1
It is assumed that cells are concentrated in -1 to 1-4. In the example of FIG. 7, cells are concentrated on the input lines 1-3 (# 3).

As shown in FIG. 7, a specific input line 1-3
When the cells arrive in a concentrated manner, as shown in FIG. 8, the three cells C, C ', and C "are stored in the queuing buffer 40-3.
Are accumulated, and the other waiting buffers 40-1, 40-
One cell A, one cell B, and one cell D are stored in 2, 40-4, respectively.

According to FIG. 7, cells A, B, C ", and D arrive at the same time. Therefore, the queuing buffers 40-1 to 40-4 set the cells A, B, C", and D to be the same. Attempt to send at the time. However, when the cell C "comes to the head position of the waiting buffer 40-3, the waiting time information is described as" 3. "The other waiting buffers 40-1, 40-2, and 40-4 In the cell at the head position, "1" is described as the waiting time information.

Here, assuming that the cells arriving at the same time are output according to the order of input line numbers # 1 to # 4, the transmission order is correctly cell A → cell B → Cell C ″ → cell D. However, since the waiting time information of cell C ″ is “3”, according to the third embodiment of the present invention, the transmission order is cell C ″ → cell A. → cell B → cell D

Therefore, in the fourth embodiment of the present invention, as shown in FIG. 9, the continuous transmission counter 62 is provided in each of the queuing buffers 40-1 to 40-4 and 70-1 to 70-4.
-1 to 62-4 and 63-1 to 63-4.

As shown in Fig. 10, the cell C "which is the head cell of the queuing buffer 40-3 has the waiting time information" 3 ". The cell A which is the head cell of the queuing buffer 70-3 is , The waiting time information is “1”.
According to the third embodiment of the present invention, the cell with the larger value of the waiting time information is output preferentially, so that the cell C "gets the priority. In the fourth embodiment of the present invention, , Continuous transmission counters 62-3 and 63-3 whose count values are "2" and "0", respectively. The count results of 62-3 and 63-3 are subtracted. That is, for the waiting buffer 40-3, (value of the waiting time information “3”) − (value of the continuous transmission counter “2”) = 1, and for the waiting buffer 70-3, (value of the waiting time information) “1”) − (the value of the continuous transmission counter “0”) = 1. The waiting time comparison circuit 60 "-3 compares the subtraction results. In this case, since both are" 1 ", it is determined that the priorities are the same. , The cell A is output with priority over the cell C ″ because the transmission is performed in the order of the input line numbers # 1 to # 4. By performing such contention control, it is possible to output a cell row in which the time order as shown in FIG. 11 is guaranteed.

Since the cells C and C 'are continuously transmitted from the waiting buffer 40-3, the continuous transmission counter 62-
3 is "2", but since the cell C "at the end of the three cells C, C ', and C" that have arrived consecutively has been transmitted, the counted value of the continuous transmission counter 62-3 is "2". Reset when the cell C ″ is sent.

The reset of the continuous transmission counters 62-1 to 62-4 and 63-1 to 63-4 is performed when the read request from the queuing buffers 40-1 to 40-4 and 70-1 to 70-4 takes one cell time. It is performed when the above is stopped. In the example of FIG. 11, the cell C ″ loses the competition control with the cells A and B. However, the cell C ″ from the queuing buffer 40-3 also indicates the cell time at which the cells A and B were transmitted. Are continuously transmitted, and in response to this, the count value of the continuous transmission counter 62-3 is held.

(Fifth Embodiment) The structure of a fifth embodiment of the present invention will be described with reference to FIGS. FIG. 12 is an overall configuration diagram of the fifth embodiment of the present invention. FIG. 13 is a block diagram of a buffer unit and a contention control unit according to the fifth embodiment of the present invention.

The present invention relates to a contention control circuit, which includes buffer units 2, 2-1 to 2-4 for temporarily storing cells arriving from input lines 1-1 to 1-4, respectively. Contention control means for sending out the cells read from -1 to 2-4 to one output line OUT without colliding with each other, and transmit the cells to the buffer units 2 and 2-1 to 2-4, respectively. H-class buffer 4 as a high-priority buffer for storing cells of a high-quality service class, L-class buffer 5 as a low-priority buffer for storing cells of a low-quality service class, and H-class buffer 4
And a selector 6 for preferentially outputting the cells stored in the memory.

Here, a feature of the present invention is that the contention control means is provided for each of the buffer units 2 and 2-1 to 2-4, and is provided in the contention control means cascaded to the output line OUT. The contention control units 3, 3-1 to 3-4 respectively include an output line OUT
An H class buffer 23 in which cells of a service class with high transmission quality are stored for cells output from the upstream contention control unit, and a service class with low transmission quality for cells output from the upstream contention control unit. , A selector 9 for preferentially outputting the cells stored in the H class buffer 23, and when one of the selectors 6 and 9 outputs a cell of a higher service class. There is a read selection circuit 7 for reading out the cells of the higher service class and performing contention control when the selectors 6 and 9 are to output cells of the same service class, reading out the cells and outputting them to the output line OUT.

For the cells input to the H class buffers 4 and 23, there are provided timers 20 and 21 as means for writing the waiting time information from the time when the cell is input to the time when the cell is output to the cell. Is read from the cell with the larger value of the waiting time information. In the fifth embodiment of the present invention, scalability is improved by arranging the conflict control units 3-1 to 3-4 in an autonomous decentralized manner.

Next, the operation of the fifth embodiment of the present invention will be described. The operation of the buffer units 2-1 to 2-4 is basically as follows.
This is the same as the operation of the buffer unit described in the conventional example. The buffer units 2-1 to 2-4 include an H class buffer 4 and an L class buffer 5. As shown in FIG. 13, when a cell is input to the buffer unit 2, the control unit (not shown) of the buffer unit 2 refers to the quality class identifier in the header of the cell and determines whether it is an H class or an L class. Identify.

The cell whose class is identified is stored in the selector 33
To the H class buffer 4 or the L class buffer 5, respectively. The selector 6 preferentially selects the H class buffer 4 when H class cells are stored in the H class buffer irrespective of the presence or absence of L class cells.

The reason why the L class buffer 5 is selected by the selector 6 is that the cells of the H class are selected by the H class buffer 4.
Only when it is not stored in

For the H class cell, the buffer residence time calculated from the time when the cell is input to the H class buffer 4 from the input line is written in a part of the cell header. FIG. 14 is a diagram showing the structure of a cell according to the fifth embodiment of the present invention. The residence time may be incremented every time one cell time elapses, or may be incremented every time a certain cell time elapses. You may. This writing is performed by the timer 20.

In the contention control unit 3, cells are transferred from a higher-level contention control unit via the line 18. However, the highest-level conflict control unit (in the example of FIG. 12, the conflict control unit 3-
In 1), since there is no higher-level contention control unit, no cell is transferred from the higher-level contention control unit.

In the contention control unit 3, the H class buffer 23
And an L class buffer 24. Cell is line 18
, The control unit (not shown) of the conflict control unit 3 refers to the quality class identifier in the header of the cell and identifies the H class or the L class.

The cell whose class has been identified is distributed to the H class buffer 23 or the L class buffer 24 by the selector 8. When the cells of the H class are accumulated in the H class buffer 23, the selector 9
The H class buffer 23 is preferentially selected regardless of the presence or absence of L class cells in the L class buffer 24. The L class buffer 24 is selected by the selector 9 only when H class cells are not stored in the H class buffer 23. The line 19 is a control signal line for transmitting the back pressure signal BP-H when the H class buffer 23 is in a buffer full state (when there is no free area for storing cells). The line 17 is a control signal line for transmitting the back pressure signal BP-L when the L class buffer 24 is in a buffer full state. However,
The lowest competitive control unit (in the example of FIG. 12, the competitive control unit 3-
In 4), since there is no lower-level conflict control unit, no BP signal is transmitted from the lower-level conflict control unit.

The cell input to the H class buffer 23 by the contention control unit 3 operates in the same manner as the buffer unit 2 with respect to the staying time. That is, based on the residence time of the H class transferred from the higher-level contention control unit or the buffer unit, the timer 21 causes the contention control unit 3 to perform a constant cell cycle while staying in the H-class buffer 23. To further increase the residence time.

Next, the read selection circuit 7 will be described with reference to FIG. FIG. 15 is a flowchart showing the operation of the read selection circuit 7 according to the fifth embodiment of the present invention. Cell reading is performed at certain intervals. FIG. 15 shows the operation in a certain read cycle. The same operation is repeated in the next read cycle. First, if a BP-H signal has been received from the lower-level contention control unit, the process ends (S1). B from lower-level contention control unit
If the PH signal has not been received, it is determined whether a cell output request has been issued from both the buffer pair 30 of the buffer unit 2 and the buffer pair 31 of the contention control unit 3 (S2). If there is only one, the cell for which the cell output request has been issued is read (S3). However, when the BP-L signal is received, the cell of the L class is not read.

When the cell output request is issued from both the buffer pair 30 and the buffer pair 31 (S2), the following 4
Perform the following operations. 1. H class buffers 4 and 2
3 issues a cell output request (S4), the cell to be read is selected by an H class competition algorithm (S4).
5). The selected cell is read (S6). 2. When the H class buffer 4 and the L class buffer 24 have issued a cell output request (S7), the cells of the H class buffer 4 are read (S8). 3. When the L class buffer 5 and the H class buffer 23 are issuing a cell output request (S
9) Read out the cells of the H class buffer 23 (S1)
0). 4. When the L class buffers 5 and 24 have issued a cell output request (S11), a cell to be read is selected by the L class competition algorithm (S12). The selected cell is read (S13). However, when the BP-L signal is being received, the cell of the L class is not read.

Here, the H class contention control algorithm compares the residence time of both cells and outputs the one with the longer residence time. Alternatively, a cell readout probability may be given to both of them in advance, and a cell may be selected and read out at any time according to the probability.

In the competition control algorithm of the L class, cell readout probabilities are given to both in advance, and cells are selected and read out at any time according to the probabilities. Alternatively, as in the case of the H-class competition control algorithm, the residence times of both cells may be compared, and the longer residence time may be output. However, in this case, timers 20 and 21
Therefore, it is necessary to write the buffer residence time converted from the time when the data is input to the L class buffers 5 and 24 into a part of the cell header also for the L class cell.

As described above, the cells of the H class and the L class are stored in separate buffers by the contention control units 3-1 to 3-4, and are selectively read out, so that the quality of the H class is L.
It is not degraded by class traffic. In addition, scalability is improved by arranging the conflict control units 3-1 to 3-4 autonomously in a distributed manner.

Here, the contention control based on the cell reading probability when the priorities are equal will be further described. Consider a k-th (k = 1, 2,..., N) buffer unit 2-k and a contention control unit 3-k counted from the upstream. This k
When cells compete in the second buffer unit 2-k and the competition control unit 3-k, the cells read from the buffer pair 30 and the cells read from the buffer pair 31 shown in FIG.
It is set so that they are selected at the probability of 1 / k and (k-1) / k, respectively.

For example, in the third buffer section 2-3 and the competition control section 3-3, the number of cells read from the buffer pair 30 and the number of cells read from the buffer pair 31 are 1/3 and 2/3, respectively. Make it selected by probability. When the cell readout probabilities are set in this way, the probabilities that the cells input to the k-th buffer pair 30 and 31 are selected in the cell conflict before the cells input to the output line are determined by the respective buffer units 2-3. 1-2-N and contention control section 3-1
The product of the probabilities of being selected in cell contention by the time the cells input to the ~ 3-N buffer pairs 30 and 31 are sent to the output line is: (1 / k) × (k / (k + 1)) ×. × ((N−2) /
(N−1)) × (N−1) / N = 1 / N. Here, the first term on the left side of this equation is the probability that a cell read from the buffer pair 30 by the k-th buffer unit 2-k and the competition control unit 3-k is selected, and the second term is the (k + 1) -th cell. Of the cell read from the buffer pair 31 by the buffer unit 2- (k + 1) and the competition control unit 3- (k + 1), and the last term is the N-th buffer unit 2-N and the competition control unit 3- N is the probability that a cell read from buffer pair 31 will be selected. The right side of this equation is the N-th buffer unit 2-N and the conflict control unit 3
-N equals the probability 1 / N that a cell read from buffer pair 30 will be selected. Therefore, when the priorities are equal, it is understood that the fairness of the selection probabilities is maintained by performing such contention control based on the cell readout probabilities.

FIG. 16 is a block diagram of the buffer unit and the contention control unit according to the fifth embodiment of the present invention shown in FIG.
Class buffers 5 and 24 or H class buffer 4
And 23 are removed, and accordingly selectors 33, 6,
FIG. 10 is a diagram showing an example in which 8 and 9 are removed. Here, when an ATM communication network in which service classes are not mixed is assumed again, if the above-described contention control using the readout probability is performed, FIG.
The block configuration of the buffer unit and the contention control unit according to the fifth embodiment of the present invention shown in FIG. 3 can be equivalently simplified as shown in FIG.

That is, the buffer unit 2-k for temporarily storing the cells arriving from the input line 1-k and the cell read from the buffer unit 2-k colliding with one output line OUT. In the contention control circuit provided with the contention control means for transmitting the data without the output, the contention control means is provided for each of the buffer units 2-k and the output line O is provided.
A queuing buffer for temporarily storing cells output from an upstream contention control unit with respect to an output line OUT, including a contention control unit 3-k connected in cascade to the UT; 70-k, the queuing buffer 40-k and the queuing buffer 70 of the buffer unit 2-k.
And a read selection circuit 7 that reads cells from -k in accordance with a predetermined read probability and outputs the read cells to the output line OUT, thereby realizing a competition control circuit. At this time, the readout probability is set to the queuing buffer 40-k of the buffer unit 2-k for the k-th stage (k is a natural number) from the upstream with respect to the output line OUT.
1 / k, and (k-1) / k for the queuing buffer 70-k of the contention control unit 3-k.

(Sixth Embodiment) FIG. 17 shows the operation of the read selection circuit 7 in the sixth embodiment of the present invention. FIG. 17 is a flowchart showing the operation of the read selection circuit 7 according to the sixth embodiment of the present invention. In the fifth embodiment of the present invention, as shown in FIG. 15, when the contention control unit 3 receives the BP-H signal from the lower-level contention control unit, the readout of the L-class cell is stopped as shown in FIG. Was. In the sixth embodiment of the present invention, BP-H
Even if a signal is received, the L class buffers 5 and 24
Issues a cell output request, if the BP-L signal has not been received, the selected cell of the L class is read. Of course, when the BP-H signal is received, the cell of the H class is not read. When the BP-L signal is received, the cell of the L class is not read.

That is, the BP-H
Regardless of whether a signal is received or not, the cell output request is sent to the buffer pair 30 of the buffer unit 2 and the contention control unit 3
It is determined whether the data is output from both buffer pairs 31 (S2).
1). If there is only one, the cell for which the cell output request has been issued is read (S22). However, when the BP-L signal is received, the cell of the L class is not read.

When a cell output request is issued from both the buffer pair 30 and the buffer pair 31 (S21), the following four operations are performed. 1. When the H class buffers 4 and 23 are issuing a cell output request (S23), the cell to be read is selected by the H class competition algorithm (S24). The selected cell is read (S25). However, when the BP-H signal is being received, the cell of the H class is not read. 2. When the H class buffer 4 and the L class buffer 24 have issued a cell output request (S26), the cells of the H class buffer 4 are read (S27). However, BP-H
When a signal is being received, an H class cell is not read. 3. When the L class buffer 5 and the H class buffer 23 have issued a cell output request (S28), the cells of the H class buffer 23 are read (S29). However, BP-
When receiving the H signal, the cell of the H class is not read. 4. When the L class buffers 5 and 24 have issued a cell output request (S30), the cell to be read is selected by the L class competition algorithm (S31). The selected cell is read (S32). However, when the BP-L signal is being received, the cell of the L class is not read.

(Seventh Embodiment) The seventh embodiment of the present invention is shown in FIG.
This will be described with reference to FIG. FIG. 18 is an overall configuration diagram of the seventh embodiment of the present invention. FIG. 19 is a block diagram of the buffer unit 2 and the contention control unit 3 according to the seventh embodiment of the present invention. In the fifth and sixth embodiments of the present invention, as shown in FIG. 13, the contention control unit 3 has an H class buffer 23 and an L class buffer 24, whereas in the seventh embodiment of the present invention, FIG. As shown, there is no buffer corresponding to the L class buffer 24 in the fifth embodiment of the present invention. Instead,
When an L-class cell is transferred from the higher-level contention control unit via the line 18, the cell is selected by the selector 8 and transferred to the L-class buffer 5 of the buffer unit 2.

The cell reading operation of the buffer section 2 is the same as that of the fifth embodiment of the present invention. When the H class buffer 23 of the contention control unit 3 is in the buffer full state, the BP-H signal is sent to the higher-level contention control unit, as in the fifth embodiment of the present invention. In the seventh embodiment of the present invention, since the contention control unit 3 does not have an L class buffer, as shown in FIG.
The -L signal becomes unnecessary.

Next, the operation of read selection circuit 7 will be described with reference to FIG. FIG. 20 is a flowchart showing the operation of the read selection circuit 7 according to the seventh embodiment of the present invention. Cell reading is performed at certain intervals. FIG. 20 shows the operation in a certain read cycle. The same operation is repeated in the next read cycle. First, if a BP-H signal has been received from a lower-order contention control circuit, the process ends (S41). If the BP-H signal has not been received from the lower-level contention control circuit, it is determined whether or not the cell output request has been issued from both the buffer pair 30 and the H class buffer 23 of the buffer unit 2 (S42). When there is only one cell, the cell for which the cell output request has been issued is read (S
43).

The output request of the cell is buffer pair 30 and H
If it is out of both of the class buffers 23 (S4
2) The following two operations are performed. 1. When the H class buffers 4 and 23 have issued a cell output request (S44), a cell to be read is selected by an H class competition algorithm (S45). The selected cell is read (S46). 2. When the L class buffer 5 and the H class buffer 23 have issued a cell output request (S47), the cells of the H class buffer 23 are read.

The H class competition control algorithm compares the residence time of both cells and outputs the one with the longer residence time. Alternatively, a cell reading probability may be given to both in advance, and a cell may be selected and read at any time according to the probability.

As described above, instead of the L class buffer 24 of the contention control unit 3 shown in the fifth and sixth embodiments of the present invention, the L class cell transferred from the upper level contention control unit is used for the buffer unit 2. , The amount of L class buffer is reduced, and the operation algorithm of the read selection circuit 7 is simplified. As in the fifth and sixth embodiments of the present invention, the quality of the H class is
It is not degraded by L-class traffic.
In addition, scalability is improved by arranging the conflict control units 3-1 to 3-4 autonomously in a distributed manner.

As described above, the H-class and L-class cells are stored in separate buffers by the contention control unit and selectively read out, so that the quality of the H-class is not deteriorated by the traffic of the L-class. . Further, by arranging the conflict control units autonomously and decentralized, scalability can be improved. Further, instead of the L-class buffer of the contention control unit, the L-class cell transferred from the higher-level contention control unit is transferred to the L-class buffer of the buffer unit, thereby reducing the amount of L-class buffer. In addition, the operation algorithm of the cell readout selection circuit can be simplified.

[0088]

As described above, according to the present invention,
When cell contention control is performed, a time order can be guaranteed. In addition, since contention control can be performed autonomously and decentralized, scalability can be increased. Furthermore, contention control can be performed for each quality class. This allows
The transmission quality of the H class cell is not degraded by the traffic of the L class cell.

[Brief description of the drawings]

FIG. 1 is an overall configuration diagram of an apparatus according to a first embodiment of the present invention.

FIG. 2 is a block diagram of a buffer unit and a contention control unit according to the first embodiment of the present invention.

FIG. 3 is a time chart showing an output state in the first embodiment of the present invention.

FIG. 4 is an overall configuration diagram of a second embodiment of the present invention.

FIG. 5 is an overall configuration diagram of an apparatus according to a third embodiment of the present invention.

FIG. 6 is a block diagram of a buffer unit and a contention control unit according to a third embodiment of the present invention.

FIG. 7 is a diagram showing a cell arrival state for explaining a fourth embodiment of the present invention.

FIG. 8 is a diagram showing a cell accumulation state for explaining a fourth embodiment of the present invention.

FIG. 9 is an overall configuration diagram of a fourth embodiment of the present invention.

FIG. 10 is a diagram illustrating a buffer unit and a contention control unit according to a fourth embodiment of the present invention.

FIG. 11 is a diagram showing a result of contention control according to the fourth embodiment of the present invention.

FIG. 12 is an overall configuration diagram of a fifth embodiment of the present invention.

FIG. 13 is a block diagram of a buffer unit and a contention control unit according to a fifth embodiment of the present invention.

FIG. 14 is a diagram showing a configuration of a cell according to a fifth embodiment of the present invention.

FIG. 15 is a flowchart showing the operation of the readout selection circuit according to the fifth embodiment of the present invention.

FIG. 16 is a diagram showing an example in which an L class buffer or an H class buffer and a selector are removed from the buffer unit and the contention control unit according to the fifth embodiment of the present invention.

FIG. 17 is a flowchart showing the operation of the readout selection circuit according to the sixth embodiment of the present invention.

FIG. 18 is an overall configuration diagram of a seventh embodiment of the present invention.

FIG. 19 is a block diagram of a buffer unit and a contention control unit according to a seventh embodiment of the present invention.

FIG. 20 is a flowchart showing the operation of the readout selection circuit according to the seventh embodiment of the present invention.

FIG. 21 is an overall configuration diagram of a conventional competition control circuit.

FIG. 22: AT in which cells of different service classes coexist
FIG. 1 is an overall configuration diagram of a conventional contention control circuit in an M communication network.

FIG. 23 is a time chart showing an output state of a conventional competition control circuit.

FIG. 24 is a time chart showing an output state of a conventional competition control circuit.

[Explanation of symbols]

1-1 to 1-4 Input line 2, 2-1 to 2-4 Buffer unit 3, 3-1 to 3-4, 90 Contention control unit 4, 4-1
4-4, 23 H class buffer 5, 5-1 to 5-4, 24 L class buffer 6, 6-1 to 6-4, 8, 9, 33, 33-1 to 33-33
4 selector 7 read selection circuit 10-16, 18, 19 line 17-1-17-4 read control circuit 20,21 timer 30,31 buffer pair 40-1-40-4, 70-1 to 70-4 waiting buffer 50, 50-1 to 50-4 Timer 51-1 to 51-4 Wait time writing circuit 60-1 to 60-4 Timer value comparison circuit 60'-1 to 60'-4, 60 "-1 to 60" -4 Wait time comparison circuit 62-1 to 62-4, 63-1 to 63-4 Continuous transmission counter 65 Ring arbiter device 80-1 to 80-4 Selector OUT output line

──────────────────────────────────────────────────続 き Continuation of the front page (72) Inventor Tsuneo Matsumura 3-19-2 Nishi-Shinjuku, Shinjuku-ku, Tokyo Within Nippon Telegraph and Telephone Corporation (56) References JP-A-7-235934 (JP, A) JP-A-4-316241 (JP, A) JP-A-3-1622031 (JP, A) JP-A-6-53989 (JP, A) JP-A-5-136813 (JP, A) JP-A-1-160130 (JP JP, A) JP-A-6-338905 (JP, A) 1997 IEICE General Conference B-6-41 OKI, N.M. Yamanaka, "A High-Speed ATM Switch Based on Scalable Distributed Arbitration", IE ICE TRANS. COMMUN. , VOL. E80-B, NO. 9 SEPT EMBER 1997, pp. 1372-1376 (58) Field surveyed (Int.Cl. ⁷ , DB name) H04L 12/28 H04L 12/56

Claims (13)

(57) [Claims] 1. A cell arriving from a plurality of input lines.
A plurality of buffer units (2-1 to 2-4) for temporarily storing the data;
And the cells read from this buffer
Contention control means for sending out lines without colliding with each other
(3-1 to 3-4, 50).
And the plurality of buffer units (2-1 to 2-4) respectively
A first buffer (40-1 to 40-4), wherein the contention control unit includes the first buffer (40-1 to 40-4).
To output the cell to the cell input in 40-4)
Means (50) for describing information indicating the priority of
It is set for each of the first buffers (40-1 to 40-4).
Contention control cascaded to the output line
(3-1 to 3-4), and each of the contention control units (3-1 to 3-4)
To temporarily store cells output from the upstream contention controller.
A second buffer (70-1 to 70-4);
Of the cells stored in the buffer of
Of the first cell among the cells stored in the second buffer.
Means for comparing the information indicating the priority order described
(60-1 to 60-4) and a comparison result of this comparing means.
According to the first buffer and the second buffer
And selecting the cells in descending order of priority and selecting the output line
Output means (80-1 to 80-4, 7).
See The selecting means selects the comparison result of the comparing means having the same comparison result.
When the first buff is indicated,
From the second buffer and the second buffer, respectively.
Means for reading a cell according to the read probability set (7)
including A conflict control circuit, characterized in that: 2. The contention control circuit according to claim 1, wherein the information indicating the priority is time information when a cell is input to the first buffer. 3. The contention control circuit according to claim 1, wherein the information indicating the priority is information on a waiting time after a cell is input to the first buffer. 4. The contention control circuit according to claim 1, wherein said means for describing is provided individually for said first buffer. 5. The contention control circuit according to claim 1, wherein said means is provided in common for a plurality of said first buffers. 6. A means for counting the number of cells continuously transmitted for the first and second buffers, and for the first cell of the first and second buffers, the number of cells transmitted from the first and second buffers is calculated from the waiting time information described in the cells. 4. The contention control circuit according to claim 3 , further comprising means for subtracting the count results of the counting means, and using the subtraction result as new waiting time information as information indicating the priority. 7. The method according to claim 1, wherein the read probability is
For the k-th stage (k is a natural number) from the upstream, the first
1 / k for the buffer and (k-
The contention control device according to claim 1 , wherein 1) / k . 8.Cells arriving from multiple input lines
A plurality of buffer units (2, 2-1 to 2-
4) and the cells read from the buffer
Contention control means to send to the output line without collision
And a step (3, 3-1 to 3-4). Each of the plurality of buffer units (2-1 to 2-4)
Cells of service class with high transmission quality
First high-priority buffer (4) and service with low transmission quality
First low-priority buffer in which cells of class are stored
(5) and stored in the first high priority buffer (4).
First selecting means (6) for preferentially outputting the selected cell.
Equipped In the competition control circuit, The contention control means includes a buffer unit (2-1 to 2-
4) cascaded to the output line provided for each
Including connected contention control units (3, 3-1 to 3-4), The contention control units (3, 3-1 to 3-4) respectively include:
Output from the upstream contention control unit to the output line
Cells of service class with high transmission quality for cells are stored.
A second high priority buffer (23) to be stacked;
Low transmission quality for cells output from contention control unit
Second low priority buffer where cells of service class are stored
(24) and stored in the second high-priority buffer (23).
Second selecting means for preferentially outputting the stacked cells
(9) the first selecting means (6) and the second
One of the selection means (9) leaves the cell of the higher service class.
Force The cell of the higher service class when
The first selection means (6) and the second selection means.
Selector (9) outputs cells of the same service class
When you are trying to do this, perform conflict control and read the cell
Reading selection means (7) for outputting to the output line, The read selection means (7) is configured to perform the first and second selections.
Predetermined reading from the means (6, 9)
Includes means to read cells according to probability Features
To be Contention control circuit. 9.The first and second high priority buffers
For the cell input to (4, 23), that cell is input
Wait time information from output to output to the cell
Means (20, 21) for writing The read selection means (7) determines the value of the value of the waiting time information.
Read from the other cell Claim 8 Contention control circuit. 10. The first low priority buffer (5)
The second low-priority buffer is one buffer (5).
9. The contention control circuit according to claim 8, wherein: 11. The read probability is calculated for the output line.
The k-th stage (k is a natural number) from the upstream
1 / k for the selection means, for the second selection means
9. The contention control device according to claim 8 , wherein (k-1) / k . 12.Cells arriving from multiple input lines
A plurality of buffer units (2-1 to 2-
4) and the cells read from the buffer
Contention control means to send to the output line without collision
Stage (3-1 to 3-4, 50)
And The contention control means includes a buffer unit (2-1 to 2-
4) cascaded to the output line provided for each
Including the connected conflict control units (3-1 to 3-4), Each of the contention control units (3-1 to 3-4) has the output line
Temporarily store cells output from the upstream competition controller
Buffers (70-1 to 70-4), and the buffer
Unit and the buffer
Read the cell according to the read probability
Reading selection means (7) for outputting Characterized by
To Contention control circuit. 13. The readout probability is calculated for the output line.
The k-th stage (k is a natural number) from the upstream
1 / k for the buffer section, and for the buffer of the contention control section.
13. The contention control device according to claim 12 , wherein (k-1) / k .