JP5432195B2 - Frame marking circuit - Google Patents

Description

  The present invention relates to a traffic control technique in a communication apparatus, and more particularly to a technique for performing fine marking according to various rates while allowing burstiness of user traffic.

  In general, a communication device that performs data transfer control in an access network collects traffic transferred from a user, multiplexes each user traffic, and then core network (large-capacity backbone communication that connects communication carriers) Network). Each communication device identifies a transmission source user using a user identifier such as VLANID with respect to user traffic. In an area with a large user scale, it is possible to cover an area with a small number of connection stages by constructing a device that can accommodate a large scale user. In an area where the user scale is small, a wide area is covered. Therefore, a configuration is required in which a small number of communication apparatuses are connected in multiple stages to perform concentration and connect to the core network.

  In general, it is known that transfer quality such as throughput and delay deteriorates according to the number of multistage connections of communication devices. For this reason, due to the difference in network configuration on the user scale, unfairness in transfer quality such as throughput and delay occurs for each user traffic accommodated in each communication device. This is because as the user traffic is accommodated in a communication device far from the core network, the number of times of concentrating increases, and accordingly, the number of waiting for the transfer order in the queue increases, delay increases, and throughput decreases. In order to eliminate such unfairness, a traffic control method for realizing fairness of transfer quality is required. Note that a queue is a queue. Here, frames received by a communication device and sorted according to priority, user identifier, and the like have a first-in first-out list structure in preparation for transmission to a destination communication port. It is retained.

  As a first conventional technique for realizing such fairness of transfer quality, there is a 2-rate 3-color marker described in Non-Patent Document 1, for example. This technique marks a frame using a traffic rate, and a peak rate (PIR), a minimum guaranteed rate (CIR), a peak burst size (PBS), and a minimum guaranteed burst size (CBS). If the traffic rate exceeds the PIR, the marking is red. If the traffic rate does not exceed the PIR and the CIR is exceeded, the marking is yellow. Otherwise, the marking is green. Thereafter, the frame is discarded according to the marked color. At this time, the red frame is most likely to be discarded, and the green frame is least likely to be discarded. With this technique, frames with higher rates are more likely to be discarded, and the fairness of throughput can be improved.

As a second conventional technique for realizing fairness of transfer quality, there is Rainbow Fair Queuing (RFQ) described in Non-Patent Document 2. With this technology, the edge router estimates the rate for each flow, and the frames with higher rates are marked in multiple colors, transferred to the core router, and the core router detects congestion when the buffer threshold is exceeded, and the rate is high. Discard the colored frame to be colored. By increasing the number of colors that are discarded when congestion continues, frames are discarded in order from the flow with the highest rate, thereby achieving fair throughput. At this time, the rate is obtained by r _new = (1−e− ^{Tk / K} ) 1 _k / T _k + e ^{(−Tk / K)} r _old . Here, the rates before and after the update are r _new and r _old , the arrival time of the _kth frame is t _k , T _k = t _k −t _k−1 , K is a constant, and the frame length is l _k. , L _k / T _k is the current actual rate.

  By using these techniques, it is possible to perform marking so that user traffic frames with a high rate are easily discarded, and to improve the fairness of transfer quality between user traffic.

RFC 2698 A Two Rate Three Color Marker, pp. 1-5. Rainbow fair queuing: fair bandwidth sharing with per-flow state, IEEE INFOCOM 2000, vol. 2,922-931.

  However, with these techniques, it is not possible to perform fine marking according to various rates while allowing burstiness, and the fairness of transfer quality between traffics may be reduced.

  For example, in the technology of Non-Patent Document 1, two threshold values are set for each frame in order to transfer frames that do not satisfy the minimum guaranteed rate and discard frames that exceed the peak rate for each user traffic. Use to mark any of the three colors. Therefore, only three-level rate control can be performed, that is, fairness cannot be realized by fine rate control of four or more levels. In addition, in order to increase the number of marking steps, if N is simply a natural number and N rate N + 1 color by the same method, N token buckets are required, and there is a problem that the apparatus becomes complicated.

In the technique of Non-Patent Document 2, since the rate of each traffic is measured using a parameter for time attenuation, traffic with high burstiness may not be allowed. That is, since the updated rate r _new is calculated so that the influence of the rate r _old before the update is attenuated as time elapses, it is possible to allow a certain amount of frames during a specific time range and transfer the burst. Contrary to the concept, traffic frames with high burstiness are marked with a color that is more likely to be discarded. As a result, the fairness of the transfer quality tends to decrease.

  The problem to be solved by the present invention is that the prior art cannot perform fine marking according to various rates while permitting burstiness, resulting in a decrease in fairness of transfer quality between traffics. Is a point. For example, in 2 rate 3 color marking, it is not possible to perform detailed marking of 4 levels or more, and in order to increase the number of marking steps, N token N buckets are used to make N rate N + 1 color in the same way. There is a problem that the apparatus needs to be held, and the apparatus becomes complicated and expensive. In addition, while the NQ rate N + 1 colorization is possible in RFQ, traffic frames with higher burstiness are marked in a color that is more likely to be discarded, resulting in a decrease in fairness.

  Accordingly, in order to solve the above-described problems, an object of the present invention is to easily perform fine marking according to various rates while allowing burstiness of user traffic.

  In order to achieve the above object, the input frame is marked with a marking value equal to or lower than the marking threshold so that the higher the frame marking value, the higher the frame discard priority. One token bucket is arranged, a token is generated as time passes, and a token is consumed according to the frame size of the input frame.

  When the input frame size per input frame is small, where token generation exceeds token consumption, every time the token bucket is full, the token is removed and the marking threshold is decreased to reduce the input frame Made it difficult to be discarded.

  When the input frame size is large in the input frame unit time, where token consumption exceeds token generation, each time the token bucket is empty, the token is replenished and the marking threshold is increased so that the input frame It was made easy to be discarded.

  When the frame size to be input per unit time of the input frame is large, the token is replenished by the token consumption initial value, and an allowable burst amount is set according to the token consumption initial value. Even when the burst is being input, if the marking threshold is gradually increased, the burst is less likely to be discarded if it is set to a certain level.

  Specifically, the present invention provides a marking unit that marks a marking value that is equal to or less than a marking threshold value in an input frame, and a token bucket that accumulates tokens so that the discard priority of the frame increases as the marking value of the frame increases. The token generator that generates tokens in the token bucket as time passes, the token consumer that consumes tokens in the token bucket according to the frame size of the input frame, and the token amount in the token bucket When the token maximum amount of the token bucket is exceeded, the token amount of the token bucket is set to a token accumulation initial value, and a marking threshold decrease unit that decreases the marking threshold, and the token amount of the token bucket Depending on frame size And when less than the amount of token, and sets the token of the token bucket token consumption initial value, a frame marking circuit characterized in that it comprises a marking threshold increasing portion for increasing the marking threshold.

  According to this configuration, it is possible to easily perform fine marking according to various rates while allowing burstiness of user traffic.

  In the present invention, the token generation unit sets a token generation rate, and the token consumption unit sets the token consumption amount to L when the frame size of the input frame is L and the marking threshold is d. / (D + 1) is a frame marking circuit characterized by being set.

  According to this configuration, when the token generation rate is set to r, for example, the marking threshold d may converge to an integer m of 0 or more that satisfies mr <R ≦ (m + 1) r with respect to the frame arrival rate R. it can.

  In the present invention, the token generation unit sets a token generation rate to a value proportional to d + 1 when the marking threshold is d, and the token consumption unit has a frame size of an input frame of L. In some cases, the frame marking circuit is characterized in that the token consumption is set to L.

  According to this configuration, when the proportionality coefficient is set to r, for example, the marking threshold d can converge to an integer m of 0 or more that satisfies mr <R ≦ (m + 1) r with respect to the frame arrival rate R. .

  Further, the present invention is the frame marking circuit, wherein the marking threshold reduction unit sets the token accumulation initial value to a value corresponding to the marking threshold.

  According to this configuration, when the token accumulation initial value is made variable according to the marking threshold, the marking threshold can be decreased faster as the token accumulation initial value is increased, and the token accumulation initial value is decreased as The marking threshold can be decreased slowly.

  The marking threshold value increasing unit may set the token consumption initial value to a value corresponding to the marking threshold value.

  According to this configuration, when making the token consumption initial value variable according to the marking threshold, the larger the token consumption initial value, the larger the allowed burst amount, and the smaller the token consumption initial value. The marking threshold can be increased quickly.

  Further, the present invention is the frame marking circuit, wherein the marking unit equalizes the appearance frequency of all marking values not more than the marking threshold value.

  According to this configuration, it is possible to easily mark the input frame.

  Further, the present invention is the frame marking circuit, wherein the marking unit equalizes the appearance frequency of all marking values equal to or less than the marking threshold value, and adds a non-linear conversion to the all marking threshold value.

  According to this configuration, when marking an input frame, the marking granularity can be made variable according to the level of discard priority.

  Further, the present invention is the frame marking circuit, wherein the marking unit weights the appearance frequency of all marking values not more than the marking threshold value.

  According to this configuration, when marking an input frame, the marking granularity can be made variable according to the level of discard priority.

  The present invention can easily perform fine marking according to various rates while allowing burstiness of user traffic.

It is a figure which shows the structure of the frame marking circuit of this invention. It is a figure which shows the token storage algorithm of Embodiment 1. It is a figure which shows the token consumption algorithm of Embodiment 1. It is a figure which shows the token accumulation | storage algorithm of Embodiment 2. FIG. It is a figure which shows the token consumption algorithm of Embodiment 2.

  Embodiments of the present invention will be described with reference to the accompanying drawings. The embodiments described below are examples of the present invention, and the present invention is not limited to the following embodiments.

(Embodiment 1)
The configuration of the frame marking circuit of the present invention is shown in FIG. The frame marking circuit 1 receives an input frame In from a device having a frame distribution function (not shown) or a part of the device, and outputs an output frame Out to a transfer queue or the like to another communication device (not shown). . At the time of marking, N is a natural number and marking is performed with N rate N + 1 color. That is, the frame is marked with N + 1 colors using different N rates.

  A frame transmitted from a user terminal such as a computer (not shown) has information (user identifier) for identifying the user and a priority for setting whether the frame is to be subject to discard control or non-discard control. Is given. The frame transferred to the frame marking circuit 1 is distributed using a user identifier or a priority or both by a device having a frame distribution function (not shown) or a part of the device.

  The frame marking circuit 1 includes a buffer 11, a marking unit 12, a token bucket 13, a token generation unit 14, a token consumption unit 15, and a marking threshold setting unit 16. The marking threshold setting unit 16 includes a marking threshold reduction unit 17 and a marking threshold value. The threshold increase unit 18 is configured. The buffer 11 inputs and stores the input frame In from the outside of the frame marking circuit 1 and outputs the output frame Out to the outside of the frame marking circuit 1 through the token consumption unit 15 and the marking unit 12 in the FIFO (first-in first-out) order. .

  The marking unit 12 marks the input frame In with a marking value less than or equal to the marking threshold d so that the frame discard priority increases as the frame marking value increases. The token bucket 13 stores tokens. The marking unit 12 performs marking with N rate N + 1 color, but the number of token buckets 13 is one instead of N.

  The token generation unit 14 generates a token in the token bucket 13 as time elapses. The token consumption unit 15 consumes tokens in the token bucket 13 according to the frame size L of the input frame In. When the frame size L of the input frame In is small and when the arrival interval of the input frame In is long, the token generation exceeds the token consumption. When the frame size L of the input frame In is large and when the arrival interval of the input frame In is short, the token consumption exceeds the token generation.

Marking threshold reduction unit of the marking threshold setting unit 16 17, when the amount of tokens k token bucket 13 exceeds the token maximum amount B of the token bucket 13, the amount of token k token bucket 13 in the token storage initial value a _d While setting, the marking threshold d is decreased. That is, when the frame size L input in the unit time of the input frame In is small, the token threshold generation unit 17 removes the token every time the token bucket 13 becomes full, where the token generation exceeds the token consumption. At the same time, the marking threshold d is decreased to make it difficult for the input frame In to be discarded.

The marking threshold value increasing unit 18 of the marking threshold value setting unit 16 uses the token amount k in the token bucket 13 as the initial token consumption when the token amount k in the token bucket 13 is lower than the token amount corresponding to the frame size L of the input frame In. and sets the value c _d, increases the marking threshold d. That is, when the frame size L inputted in the unit time of the input frame In is large, the marking threshold increasing unit 18 replenishes the token every time the token bucket 13 becomes empty, where the token consumption exceeds the token generation. At the same time, the marking threshold d is increased so that the input frame In is easily discarded.

Then, when the frame size L of the input frame is large, the marking threshold increasing portion 18, supplemented by an amount token token consumption initial value c _d, sets the burst amount allowed according to the token consumption initial value c _d . Here, a burst is a certain amount of frames that are allowed and transferred during a specific time range. Therefore, since the marking threshold d is set to be small before the burst is input, if the marking threshold d is set to be small to some extent even when the burst is gradually input, the burst is set. A large marking value having a high discard priority is not marked and is not easily discarded.

  Thereby, fine marking according to various rates can be easily performed while allowing burstiness of user traffic.

  The token accumulation algorithm of the first embodiment is shown in FIG. The token generation unit 14 determines whether the time has elapsed by Δt (step S1). If the token generation unit 14 determines that the time has elapsed by Δt (YES in step S1), the token generation unit 14 generates rΔt as the token amount k (step S2). Here, r is a token generation rate. If token generation unit 14 determines that the time has not elapsed by Δt (NO in step S1), token generation unit 14 repeatedly executes the process of step S1.

The marking threshold reduction unit 17 determines whether or not the token amount k exceeds the token maximum amount B (step S3). Marking threshold reduction unit 17, it is judged that the amount of token k exceeds the token maximum amount B (in step S3 YES), it sets the amount of token k token storage initial value a _d (step S4), and the marking threshold d is decreased by 1 (step S5), and the token accumulation algorithm is terminated. Here, the token accumulation initial value _ad is 0 or more and the token maximum amount B or less. If the marking threshold reduction unit 17 determines that the token amount k does not exceed the token maximum amount B (NO in step S3), the marking threshold reduction unit 17 ends the token accumulation algorithm.

  The token consumption algorithm of Embodiment 1 is shown in FIG. The token consumption unit 15 inputs the frame size L of the input frame In from the buffer 11 (step S11), inputs the marking threshold d from the marking threshold setting unit 16 (step S12), and sets L / (d + 1) as the token amount k. Is consumed (step S13).

The marking threshold value increasing unit 18 determines whether or not the token amount k after consumption is less than 0 (step S14). That is, the marking threshold value increasing unit 18 determines whether the token amount k before consumption is less than L / (d + 1). Marking threshold increasing portion 18, it is judged that the amount of token k after consumption is below 0 (YES at step S14), and sets the amount of token k token consumption initial value c _d (step S15), and the marking threshold d is increased by 1 (step S16), and the token consumption algorithm is terminated. Here, the token consumption initial value c _d is less is 0 or more tokens maximum amount B. If the marking threshold increase unit 18 determines that the token amount k after consumption is not less than 0 (NO in step S14), the marking threshold increase unit 18 ends the token consumption algorithm.

  The token accumulation algorithm shown in FIG. 2 and the token consumption algorithm shown in FIG. 3 are repeatedly executed in parallel. Here, if the generation of tokens and the consumption of tokens are balanced, rΔt = RΔt / (d + 1) is established, where R is the frame arrival rate. If m <R ≦ (m + 1) r, where m is an integer greater than or equal to 0, then m−1 <d ≦ m. Therefore, the marking threshold d can converge to an integer m of 0 or more that satisfies mr <R ≦ (m + 1) r with respect to the frame arrival rate R.

The marking threshold reduction unit 17 may set the token accumulation initial value _ad to a value corresponding to the marking threshold d. Thus, as the token accumulation initial value _ad is increased, it takes less time to update the marking threshold d, and thus the marking threshold d can be reduced more quickly. Then, as the token accumulation initial value a _d is decreased, it takes time until the marking threshold d is updated. Therefore, the marking threshold d can be decreased later.

Marking threshold increasing portion 18 may set the token consumption initial value c _d to a value corresponding to the marking threshold d. Thus, the larger the token consumption initial value c _d, for increasing the consumption to the update of the marking threshold d, it is possible to increase the burst amount allowed. Then, the smaller the token consumption initial value c _d, for not requiring time to update the marking threshold d, it is possible to increase faster marking threshold.

The marking unit 12 equalizes the appearance frequencies of all marking values p that are equal to or less than the marking threshold d. For example, there are a method in which i is a frame number and p _i = (p _i−1 +1) MOD (d + 1), a method of generating a uniformly distributed random number of 0 or more and d or less, and substituting it into p. . After p is generated, if p exceeds N, N is substituted for p.

  The marking unit 12 marks a value corresponding to the marking value p. As the marking position, for example, DSCP or COS in the header of the input frame In may be used, a new field may be defined, and a new bit string may be inserted at that time.

  If m ≦ N−1, a value from 0 to m is generated at the same frequency with respect to p, and an output frame Out marked with each value from 0 to m is output at a rate r. If m> N-1, the output frame Out marked with each value between 0 and N-1 is output at the rate r, and the output frame Out marked N is output at the rate R-Nr. Thereby, it is possible to easily mark the input frame In.

(Embodiment 2)
The second embodiment is similar in marking method to the first embodiment, but is different in token accumulation algorithm and token consumption algorithm.

  FIG. 4 shows a token accumulation algorithm according to the second embodiment. The token generation unit 14 determines whether the time has elapsed by Δt (step S21). If it is determined that the time has passed by Δt (YES in step S21), the token generation unit 14 generates r (d + 1) Δt as the token amount k (step S22). Here, r is a proportionality coefficient. If token generation unit 14 determines that the time has not elapsed by Δt (NO in step S21), token generation unit 14 repeatedly executes the process of step S21.

The marking threshold reduction unit 17 determines whether or not the token amount k exceeds the token maximum amount B (step S23). Marking threshold reduction unit 17, it is judged that the amount of token k exceeds the token maximum amount B (in step S23 YES), it sets the amount of token k token storage initial value a _d (step S24), and the marking threshold d is decreased by 1 (step S25), and the token accumulation algorithm is terminated. Here, the token accumulation initial value _ad is 0 or more and the token maximum amount B or less. If the marking threshold reduction unit 17 determines that the token amount k does not exceed the token maximum amount B (NO in step S23), the marking threshold reduction unit 17 ends the token accumulation algorithm.

  The token consumption algorithm of Embodiment 2 is shown in FIG. The token consumption unit 15 inputs the frame size L of the input frame In from the buffer 11 (step S31), and consumes L as the token amount k (step S32).

The marking threshold value increasing unit 18 determines whether or not the token amount k after consumption is less than 0 (step S33). That is, the marking threshold value increasing unit 18 determines whether or not the token amount k before consumption is less than L. Marking threshold increasing portion 18, it is judged that the amount of token k after consumption is below 0 (YES in step S33), it sets the amount of token k token consumption initial value c _d (step S34), the marking threshold d is increased by 1 (step S35), and the token consumption algorithm is terminated. Here, the token consumption initial value c _d is less is 0 or more tokens maximum amount B. If the marking threshold value increasing unit 18 determines that the token amount k after consumption is not less than 0 (NO in step S33), it ends the token consumption algorithm.

  The token accumulation algorithm shown in FIG. 4 and the token consumption algorithm shown in FIG. 5 are repeatedly executed in parallel. Here, if the generation of tokens and the consumption of tokens are balanced, r (d + 1) Δt = RΔt is established with R as the frame arrival rate. If m <R ≦ (m + 1) r, where m is an integer greater than or equal to 0, then m−1 <d ≦ m. Therefore, the marking threshold d can converge to an integer m of 0 or more that satisfies mr <R ≦ (m + 1) r with respect to the frame arrival rate R.

(Embodiment 3)
The third embodiment is similar to the first and second embodiments in the token accumulation algorithm and the token consumption algorithm, but the marking method is different.

The marking unit 12 equalizes the appearance frequencies of all marking values p that are equal to or less than the marking threshold value d, and adds a nonlinear transformation to the total marking threshold value p. For example, p is generated so that the appearance frequencies of the values of 0 or more and d or less are equal. If the generated p is 0, no conversion is performed. When the generated p is 1 or more, after converting c = ceil (log ₂ p) using ceil (x) as a ceiling function of x, N is substituted into p only when p> N. With this method, it is possible to vary the rate at which the frames marked with each value are output.

  When the above conversion is performed, when p before conversion is 0, p after conversion is 0, and when p before conversion is greater than 1 and 2 or less, p after conversion is 1, and p before conversion is When it is greater than 3 and less than or equal to 4, p after conversion is 2, and when p before conversion is greater than 4 and less than or equal to 8, p after conversion is 3. In this way, the more granular the marking is performed, the smaller the value to be marked with a smaller frame arrival rate, the smaller the value to be marked, while the larger the value to be marked with a larger frame arrival rate, the larger the value to be marked. The rough marking can be performed.

  Thereby, when marking the input frame In, the granularity of marking can be made variable according to the level of discard priority.

(Embodiment 4)
The fourth embodiment is similar to the first and second embodiments in the token accumulation algorithm and the token consumption algorithm, but the marking method is different.

  The marking unit 12 weights the appearance frequency of all marking values p that are equal to or less than the marking threshold d. For example, the weight of the appearance frequency of 0, 1, 2,..., D at the time of generating p is defined as 1: 2: 3:. However, if the generated p exceeds N, N is substituted for p. In this case, when d ≦ N−1, the ratio of output rates of frames marked 0, 1, 2,..., D is 1: 2: 3:. When d> N−1, the ratio of the output rates of frames marked 0, 1, 2,..., d−1 is 1: 2: 3:.

  Thereby, when marking the input frame In, the granularity of marking can be made variable according to the level of discard priority.

  The frame marking circuit according to the present invention can be applied when fine marking according to various rates is performed while allowing burstiness of user traffic.

1: frame marking circuit 11: buffer 12: marking unit 13: token bucket 14: token generating unit 15: token consumption unit 16: marking threshold setting unit 17: marking threshold decreasing unit 18: marking threshold increasing unit In: input frame Out: Output frame

Claims (7)

A marking unit for marking the input frame with a marking value equal to or lower than a marking threshold so that the discarding priority of the frame increases as the marking value of the frame increases,
A token bucket for storing tokens;
A token generation unit that sets a token generation rate when generating a token in the token bucket as time passes,
When the token of the token bucket is consumed according to the frame size of the input frame, when the frame size of the input frame is L and the marking threshold is d, the token consumption is set to L / (d + 1) A token consumption unit
A marking threshold reduction unit that sets the token amount of the token bucket to a token accumulation initial value when the token amount of the token bucket exceeds the token maximum amount of the token bucket, and reduces the marking threshold;
A marking threshold increasing unit for setting the token amount of the token bucket to a token consumption initial value and increasing the marking threshold when the token amount of the token bucket is lower than the token amount according to the frame size of the input frame;
A frame marking circuit comprising: A marking unit for marking the input frame with a marking value equal to or lower than a marking threshold so that the discarding priority of the frame increases as the marking value of the frame increases,
A token bucket for storing tokens;
A token generation unit that sets a token generation rate to a value proportional to d + 1 when the marking threshold is d when generating a token in the token bucket over time;
Depending on the frame size of the input frame, when consuming tokens in the token bucket, when the frame size of the input frame is L, a token consumption unit that sets the token consumption amount to L ,
A marking threshold reduction unit that sets the token amount of the token bucket to a token accumulation initial value when the token amount of the token bucket exceeds the token maximum amount of the token bucket, and reduces the marking threshold;
A marking threshold increasing unit for setting the token amount of the token bucket to a token consumption initial value and increasing the marking threshold when the token amount of the token bucket is lower than the token amount according to the frame size of the input frame;
A frame marking circuit comprising: The marking threshold reduction unit, and sets the token accumulation initial value to a value corresponding to the marking threshold, the frame marking circuit according to claim 1 or 2. The frame marking circuit according to any one of claims 1 to 3 , wherein the marking threshold value increasing unit sets the token consumption initial value to a value corresponding to the marking threshold value. The marking unit is characterized in that to equalize the frequency of occurrence of all the marking values below the marking threshold, the frame marking circuit according to any one of claims 1 to 4. The marking unit is configured to equalize the frequency of occurrence of all the marking values below the marking threshold, characterized in that said adding non-linear transformation to all the marking threshold, the frame marking circuit according to any one of claims 1 to 4. The marking unit is characterized by weighting the frequency of occurrence of all the marking values below the marking threshold, the frame marking circuit according to any one of claims 1 to 4.

Images