JP3461110B2 - Band shared circuit - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a band sharing circuit for sharing a band for a single output or a plurality of outputs with a plurality of connections.

[0002]

2. Description of the Related Art A band sharing circuit has a minimum guaranteed bandwidth (hereinafter referred to as "MCR") that guarantees transmission for each connection.
(Minimum Cell Rate) ”, and it is required that the bandwidth above the MCR be evenly distributed to each connection.

As a band sharing circuit which requires such operation, when the total band of the cells collected in the band sharing circuit is larger than the output side shared band, cells exceeding MCR are appropriately discarded. Some have a shaping function that narrows the total bandwidth below the shared bandwidth.

FIG. 11 shows the configuration of a conventional band sharing circuit having a shaping function. In the figure, the input cell is stored in the cell storage means 22 via the passage blocking means 21, and the cell read from the cell storage means 22 is output from the band sharing circuit. A threshold value observing unit 23 for observing the amount of accumulated cells is connected to the cell accumulating unit 22. The passage blocking means 21 controls whether or not to discard the input cell according to the state of the input cell and the cell accumulation amount observed by the threshold observing means 23.

FIG. 12 shows a specific operation flow of the passage blocking means 21. For the input cell, it is determined whether or not it is the first cell forming the packet, and if it is the first cell, it is determined whether or not the belonging connection is less than or equal to MCR,
If it is less than MCR, the input cell is passed. If it exceeds the MCR, it is determined whether the usage amount of the buffer of the cell accumulating unit 22 is equal to or less than the discard threshold value. Here, if it is less than the discard threshold, the input cell is passed, and if it exceeds the discard threshold, the input cell is discarded. That is, when the cell storage amount of the cell storage means 22 exceeds the threshold value, the cells exceeding the MCR are discarded.

On the other hand, when the input cell is not the first cell forming the packet, it is judged whether or not the cells forming the same packet are discarded, and if they are discarded, the input cell is discarded and discarded. If not, the input cell is passed.

[0007]

The conventional band sharing circuit shown in FIG. 11 has the following problems. First, since there is no regulation regarding the amount of cell storage that can be stored in the cell storage unit 22 after the start of cell discard, there is a risk of discarding cells that do not meet the MCR.

Secondly, since the cell storage amount is not managed for each connection, when the cell storage amount exceeds a threshold value for a specific connection, the connection in which the cells are stored up to the threshold value and the other connections are the same. Will be thrown away. Also, cells of other connections that have started inputting after cells of other connections have accumulated will be transmitted after waiting for cells of other connections that have already accumulated to complete transmission, so transmission delay will occur. To do.
That is, through the cell accumulation by the cell accumulating means, an unfairness occurs between the connections because of the history of other connections, not the past cell transmission history of the own connection, which causes cell discard and transmission delay. Furthermore, this transmission delay imparts burstiness to the connections arriving at regular cell intervals, and even severely prevents cell transmission in MCR.

In order to solve the above problems, in order to guarantee the MCR and the fairness between the connections, the number of cells that can be stored in the cell storage means is defined for each connection, and the cells are already stored. It is necessary to combine the round-robin reading in which the cells of the connected connection are sequentially read in the band guaranteeing the MCR. However, the band sharing circuit having such a function also has the following problems.

First, in order to guarantee the MCR of a cell that has arrived while waiting for the round robin reading, a long cell storage amount is required. Next, in round robin reading, it is necessary to search whether or not a cell for each connection exists in the cell storage means, but the number of connections that can be searched is limited by the access speed and the length of the scheduler. . Further, when forming a shared band in which a plurality of shared bands are bundled, unless a limit is set on the round-robin read speed of each shared band, when only cells of a single shared band connection are input, There is a problem that data is read out beyond the upper limit of the band.

It is an object of the present invention to provide a band sharing circuit that guarantees MCR (minimum guaranteed bandwidth) and enables fair bandwidth allocation among connections without using round robin reading.

[0012]

The band sharing circuit of the present invention detects, for an input cell, whether or not the minimum guaranteed bandwidth is exceeded for each connection and whether or not the shared bandwidth of the entire group of connections sharing the bandwidth is exceeded. Accordingly, among the input cells, connections with a bandwidth less than the minimum guaranteed bandwidth, or cells with connections with a shared bandwidth that is more than the minimum guaranteed bandwidth are passed in packet units, and connections with the minimum guaranteed bandwidth or more are shared. Blocks and discards the cells of a connection that has no bandwidth in packet units.

As a result, it is possible to perform discard control regardless of the accumulation history of the cell accumulating means, and to realize fair band allocation between connections while guaranteeing MCR.

[0014]

DETAILED DESCRIPTION OF THE INVENTION

(First Embodiment) FIG. 1 shows a first embodiment of a band sharing circuit of the present invention.

In the figure, the input cell is the passage blocking means 1
1 and the cell storage means 12 to output. The passage blocking means 11 observes whether or not the MCR is exceeded for each connection, and whether or not the shared bandwidth of the entire group of connections sharing the bandwidth is exceeded. The observation results are integrated by the integrating means 13 to determine the number of cells per hour or the band.

According to the integrated value of the integrating means 13, the passage blocking means 11 determines, in packet units, the cells of the connections that are less than or equal to the MCR or that have a margin in the shared band that is shared with other connections even if it is greater than or equal to the MCR. To pass through. On the other hand, a cell of a connection having a connection equal to or higher than MCR and having no margin in the shared band shared with other connections is blocked and discarded in packet units.

FIG. 2 shows a specific operation flow of the passage blocking means 11. For the input cell, it is judged whether or not it is the first cell forming the packet, and if it is the first cell, it is judged whether or not the belonging connection is less than or equal to MCR, and M
If it is less than CR, the input cell is passed. If it exceeds the MCR, it is determined whether the used bandwidth of the belonging group is less than or equal to the threshold value. Here, if it is less than the threshold value, the input cell is allowed to pass, and if it exceeds the threshold value, the input cell is discarded. on the other hand,
If the input cell is not the first cell that forms the packet, determine whether the cells that form the same packet are discarded. If they are discarded, the input cell is discarded. If not, the input cell is discarded. Pass through.

The passage blocking means 11 uses CMP (Cell Loss Priority) bits or the like, which means a discard priority cell in ATM, in some or all of the packets in the band not less than the MCR which is not blocked and the cells constituting the packets. A mark may be added. When this is added, the measurement result of the MCR measured by this band sharing circuit can be used in the destination circuit.

The cell accumulating means 12 has a purpose of absorbing an excess of the shared band generated because the discard by the pass blocking means 11 is in units of packets and ensuring a band equal to or lower than the MCR of each connection. Therefore, the passage blocking means 11
It is necessary that the number of cells that can be stored after the start of passage prevention by is larger than the amount that can secure the MCR of each connection. In other words, when all connections sharing the band simultaneously input / output to / from the band sharing circuit in the maximum band (hereinafter referred to as "PCR (Peak Cell Rate)"), the cell storage amount that does not drop each packet of all connections is required. To be done. For example, it is (maximum packet length) × (number of connections) or more. In the band sharing circuit that accommodates the connection in which the statistical multiplexing effect is effective, this cell amount may be an equivalent amount in which the amount of the statistical multiplexing effect is reduced.

If the integrated value of the integrating means 13 contains an error, it is necessary to add the cell accumulation amount corresponding to the error. It is the amount of MCR plus the error
This is because the cells of MCR including this error must be stored so as not to drop. As an example of the error, in the case where the MCR is measured in packet units, it becomes (longest packet length-1 bit) / (observation time × MCR) depending on the measurement method. In this case, a cell accumulation amount equal to or greater than the sum of MCR and this error is required.

As another example of the error of the observed value, the cells below the MCR and the MCR for each observation window which is the subdivided observation time.
There is a case where the method of separating the cells exceeding the above and describing the fact with tags etc. is applied. In the case of this method, the situation shown in FIG. 3 is conceivable. In the situation shown in FIG. 3, it is assumed that the shared band has just arrived when a packet exceeding the MCR arrives in all the connections. At this time, if the input cell is the first cell in the packet, it cannot be discarded,
A packet described as MCR or less in the next observation window cannot be discarded. Therefore, in the band sharing circuit adopting such an observation method, the error is included as the substantial or equivalent cell storage amount of the cell storage means (the total number of connections) × (longest packet length) × 2 or more. And need to.

Here, in the configuration of the first embodiment shown in FIG. 1 and the conventional configuration shown in FIG. 11, the input cell, the pass cells and the discard cells of the pass blocking means 11, 21 and the cell storage means 12, The relationships among the 22 storage cells are shown in FIGS. 4 and 5, and the fairness between connections in cell discard will be described. 4 and 5, the horizontal axis represents time, and the vertical axis represents (1) input cell amount, (2) passing cell amount, (3) discarded cell amount, and (4) accumulated cell amount. Also, the shared bandwidth is shown by a broken line.

From time t ₁ to time t ₂ , cells up to the shared band upper limit are input by a single connection 1. During this period, in the conventional example of FIG. 4, since the input / output bands of the cell accumulating means 22 are the same, no cells are accumulated and no cell discard occurs. In the first embodiment shown in FIG. 5, cell accumulation and discard do not occur in the same manner.

From time t ₂ to time t ₃ , a cell exceeding the shared band is input by the two connections 1 and 2. During this period, in the conventional example shown in FIG. 4, cells corresponding to the total input bandwidth minus the shared bandwidth are accumulated in the cell accumulating means 22. However, since the accumulated amount does not reach the threshold value at which discard occurs until time t ₃ , discard does not occur during this period. On the other hand, in the first embodiment of FIG. 5, the cells of each connection are evenly discarded by the excess of the shared band. As a result, the inputs and outputs of the band sharing circuit are balanced, and no cells are stored in the cell storage means 12.

From time t ₃ to time t ₄ , cells exceeding the shared band are input by the three connections 3, 4, and 5. During this period, in the conventional example of FIG. 4, since the cell accumulation amount has already reached the discard start threshold value, only cells of MCR or less pass through for each connection, and cells exceeding MCR are discarded. At this time, the amount obtained by subtracting the cell band below the MCR of each connection from the shared band is t ₂ −
Used to digest accumulated cells during t ₃ .
This process, because past accumulated history of each connection is performed regardless, t connection between ₂ -t ₃ and t ₃
Even if the connection between -t ₄ is different, the cells of the connection input later are uniformly discarded, and the cell discard of each connection becomes unfair. Also,
The first cell of the connection entered at t ₃ is t ₂ −t
_The output is kept waiting until the cells of other connections accumulated during ₃ are output, and the delay of each connection becomes unfair. In the band sharing circuit in which the unfair delay occurs, the cell transmission amount depends on the input timing for a protocol such as TCP / IP in which the transmission waiting time influences the transmission cell amount. This causes an increase in unfairness regarding the use of the shared band.

On the other hand, in the first embodiment of FIG. 5, t ₂ −
As in the period of t _3, the cells of the connections 3, 4, and 5 are evenly discarded by the excess amount with respect to the shared band. That is, the band of MCR or more is divided and used among three connections that are input at the same time, and in principle, cells are not stored. Therefore, unlike the conventional example, there is no delay due to outputting cells of other connections accumulated in the past, and there is no unfairness in cell discard according to input time order. In addition, since there is no cell accumulation in principle, it is possible to easily change the MCR of the connection or the shared band during operation and avoid the cell drop associated therewith, as compared with the conventional example in which cells are constantly accumulated. it can. As described above, in the present embodiment, cell discard and delay between connections can be made fair compared to the conventional example.

Here, CL indicating a cell to be preferentially discarded
In a band sharing circuit that accommodates connections with a mark such as P, when a packet is discarded, cells with that mark may be preferentially discarded on a packet-by-packet basis. Alternatively, the control may be performed based on the observation of the passage blocking means.

The connection sharing the band may be any one of connection, path, channel, virtual connection, virtual path, virtual channel, output route, or a combination thereof. Further, the group of connections sharing the band may be one of output routes, service classes, MCRs, PCRs, or a combination thereof. In the case of grouping with the same PCR, the band sharing circuit can narrow down to less than the PCR for the connections that may input more than the set PCR to the band sharing circuit.
In addition, as shown in FIG. 6, by grouping with the same PCR,
You may set so that the sum of MCR of all the connections in a group may not exceed PCR.

Furthermore, groups of connections sharing a band may be further grouped together to form a large group for each output route or output line. In that case, the unused band can be exchanged by notifying the used band by the group in the large group.

Further, in the above description of the embodiment, cells are discarded or passed in packet units, but this packet may be an actual packet or a virtual packet. An example of using a virtual packet is a case where a cell is a connection according to a protocol that does not form a packet and a case where a packet other than a packet format such as an MTU length that leads a data length assumed in a band sharing circuit is input. In some cases, packets conforming to multiple packet formats are mixed. The former two cases may be handled as the packet format set by the band sharing circuit. In the third case, the maximum amount of information that can be transmitted in one packet is 1500 bytes or 9180 bytes, and packets of different formats are handled by the same group, and packets of all connections are long format packets. May be treated as At that time, the unfairness due to the difference in packet length may be eliminated by delaying the discarding of the short packets by the amount corresponding to the ratio of the short packets to the long packets.

(Second Embodiment) FIG. 7 shows a second embodiment of the band sharing circuit of the present invention. In the figure, the input cell is output via the passage blocking means 14 and the cell storage means 12. The integrating means 15 does not integrate the results observed by the passage blocking means as in the first embodiment,
It is characterized in that the band information inputted separately is diverted to control the passage blocking means 14. For example, a UPC, a shaver, or A that recognizes the number of cells existing in the preceding stage of the band sharing circuit.
ATM switch, ATM-P compatible with BR service class
The information about the number of cells for each connection recognized by the band allocation circuit of the DS transmission device, the external CLP adding circuit, and the like is received, and part or all of the information is diverted.

The passage preventing means 14 and the integrating means 15
FIG. 8 shows a specific operation flow of the above. The accumulator 14 receives the bandwidth usage of the connection, and the bandwidth usage is M
Condition 1 is set when CR or less, or when the bandwidth usage exceeds MCR and the bandwidth used by the belonging group is equal to or less than the threshold. The condition 2 is that the bandwidth usage of the connection exceeds the MCR and the bandwidth usage of the belonging group exceeds the threshold value.

The passage blocking means 14 applies to the input cell
It is determined whether or not it is the first cell forming the packet. If it is the first cell, the input cell is passed under the condition 1 and the input cell is discarded under the condition 2. On the other hand, when the input cell is not the first cell forming the packet, it is judged whether or not the cells forming the same packet are discarded. If the input cell is discarded, the input cell is discarded, and if it is not discarded. Pass the input cell.

(Third Embodiment) FIG. 9 shows a third embodiment of the band sharing circuit of the present invention. In the figure, the input cell is output via the passage blocking means 16 and the cell storage means 12. The cell accumulation observing means 17 observes whether or not the cell accumulation means 12 has started accumulation of cells, and at the start of cell accumulation, the passage prevention means 16 prevents the cell passage.

FIG. 10 shows a specific operation flow of the passage blocking means 16. For the input cell, it is determined whether or not it is the first cell forming the packet, and if it is the first cell, it is determined whether or not the belonging connection is less than or equal to MCR,
If it is less than MCR, the input cell is passed. If the MCR is exceeded, the cell accumulation status of the cell accumulation means 12 is obtained from the cell accumulation observation means 17. Here, the input cell is passed if the cell is not stored in the cell storage means 12, and the input cell is discarded if the cell is stored. On the other hand, when the input cell is not the first cell forming the packet, it is determined whether or not the cells forming the same packet are discarded, and if they are discarded, the input cell is discarded,
If not discarded, pass through the input cell.

The cell accumulation observing means 17 integrates the number of cells per hour of the cell accumulating means 12 or observes the actually read band, instead of directly observing the cell accumulation start of the cell accumulating means 12. You may do it. In this case, it is desirable to add or subtract the band at which passage stop is started in consideration of the error of observation.

Here, the difference between the control by the cell accumulation observation means 17 in this embodiment and the control by the conventional threshold observation means 23 will be described. Conventionally, cells are discarded when the buffer usage exceeds a predetermined discard threshold, but this embodiment corresponds to the case where the discard threshold is set to zero. As a result, in principle, cells are not accumulated, so that unfairness between connections can be eliminated as in the first and second embodiments.

[0038]

As described above, the band sharing circuit of the present invention discards cells on a packet-by-packet basis based on the band of the group in which the connections are bundled, so that cell discard and delay based on past accumulation history can be avoided. Eliminate injustice,
It is possible to guarantee MCR and enable fair band allocation between connections.

[Brief description of drawings]

FIG. 1 is a block diagram showing a first embodiment of a band sharing circuit of the present invention.

FIG. 2 is a flowchart showing a specific operation example of the passage blocking unit 11.

FIG. 3 is a diagram for explaining a necessary cell accumulation amount when the observation window is crossed.

FIG. 4 is a diagram for explaining a situation of cell passage / discard / accumulation in a conventional band sharing circuit.

FIG. 5 is a diagram for explaining the status of cell passage / discard / accumulation in the first embodiment.

FIG. 6 is a diagram showing an example of band allocation of groups.

FIG. 7 is a block diagram showing a second embodiment of the band sharing circuit according to the present invention.

FIG. 8 is a flowchart showing a specific operation example of the passage blocking unit 14 and the integrating unit 15.

FIG. 9 is a block diagram showing a third embodiment of the band sharing circuit of the present invention.

FIG. 10 is a flowchart showing a specific operation example of the passage blocking unit 16.

FIG. 11 is a block diagram showing a configuration of a conventional band sharing circuit.

FIG. 12 is a flowchart showing a specific operation example of the passage blocking unit 21.

[Explanation of symbols]

11, 14, 16 Passage blocking means 12 cell storage means 13,15 integrating means 17 Cell accumulation observation method 21 Passage blocking means 22 Cell storage means 23 Threshold observation means

Continuation of front page (58) Fields surveyed (Int.Cl. ⁷ , DB name) H04L 12/28 H04Q 3/00

Claims (8)

(57) [Claims] 1. In a band sharing circuit in which a band for a single or a plurality of outputs is shared by a plurality of connections, whether or not a minimum guaranteed band is exceeded for each connection for an input cell, and an entire group of connections sharing the band. And an integrating unit that detects whether or not the shared band exceeds the shared band, and depending on the integrated value of the integrating unit, there is a margin in the shared band even if the connection is less than the minimum guaranteed band of the input cells or more than the minimum guaranteed band. Passing-through means for passing cells of a certain connection in packet units, blocking and discarding cells of connections having a minimum guaranteed bandwidth and having no margin in the shared band in packet units, and passing through the passage blocking means And a cell storage unit for storing the stored cells. 2. The band sharing circuit according to claim 1, wherein the integrating means integrates the number of cells passing through the passage blocking means per hour, and shares the band with the presence or absence of excess of the minimum guaranteed bandwidth for each connection. A band sharing circuit, which is configured to detect whether or not the shared band of the entire group of connections is exceeded. 3. The band sharing circuit according to claim 1, wherein the accumulator receives a notification of the number of cells per hour or the band observed in the circuit preceding the band sharing circuit, and determines the minimum guaranteed bandwidth for each connection. A band sharing circuit characterized by being configured to detect whether or not excess is present and whether or not the shared bandwidth of the entire group of connections sharing the bandwidth is exceeded. 4. The band sharing circuit according to claim 1, wherein the cell accumulating unit has a cell accumulating amount that is equal to or more than the number of cells that can be accumulated after the passage preventing unit starts passage inhibition to ensure a minimum guaranteed bandwidth of each connection. A band sharing circuit characterized by having a configuration having a. 5. A band sharing circuit in which a band for a single output or a plurality of outputs is shared by a plurality of connections, and the band is shared even if the connection is less than the minimum guaranteed band or more than the minimum guaranteed band among the input cells. Pass the cells of a connection that have a margin in the shared bandwidth of the entire group of connections in packet units, and pass the cells of a connection that has a minimum guaranteed bandwidth and has no margin in the shared bandwidth in a packet unit and discard it. Blocking means and cell storage for accumulating cells that have passed through the passage blocking means, with the number of cells that can be stored after the passage blocking means has started to block the passage so that the minimum guaranteed bandwidth of each connection can be secured Means and the cell accumulation start of the cell accumulating means, and the passage obstructing means obstructs passage according to the information. A band sharing circuit comprising: a cell accumulation observation means for controlling cells to be stopped. 6. The band sharing circuit according to claim 4 or 5, wherein the cell storage amount of the cell storage means is equal to or more than the product of the total number of connections and the number of cells forming the longest packet of each connection. Characteristic band shared circuit. 7. The band sharing circuit according to claim 4 or 5, wherein the cell storage amount of the cell storage means is at least twice the product of the total number of connections and the number of cells forming the longest packet of each connection. A band sharing circuit characterized by being present. 8. The band sharing circuit according to claim 1, wherein the connection is one of a connection, a path, a channel, a virtual connection, a virtual path, a virtual channel, and an output route, or A band sharing circuit characterized by being a combination.