JP6660716B2 - Packet control device - Google Patents

Description

  The present invention relates to a packet control device having a buffer, and more particularly, to a packet control device that discards packets so that the buffer does not overflow.

  In recent years, with the increase in the number of users performing communication and the amount of traffic per user, it has become important to implement an efficient congestion control function in a packet control device. One of the techniques for realizing congestion control is RED (Random Early Detection) (for example, see Non-Patent Document 1).

  The RED performs congestion control for avoiding buffer overflow by randomly discarding a packet arriving at a packet control device based on a set discard probability (probability of discarding a packet) before storing the packet in a buffer. I do. The RED periodically observes the buffer accumulation amount, which is the amount of data accumulated in the buffer, and calculates the drop probability from the observed buffer accumulation amount. The drop probability depends on the user who transmits the packet. Is determined. Therefore, in RED, the same discard probability is obtained for each user, and fairness between users is ensured.

  Since the RED requires complicated arithmetic processing to calculate the discard probability, it has been originally realized by a method combining hardware and software. However, it is expected that this method cannot cope with the traffic volume that has been increasing in recent years, since the processing speed requires a long time.

  To solve this problem, Patent Literature 1 proposes a method of implementing RED using only hardware. In the packet processing device described in Patent Document 1, when realizing RED by hardware, the moving average value of the buffer accumulation amount used for calculating the discard probability is subjected to threshold processing at evenly spaced thresholds, and the result of the threshold processing is obtained. The value of the corresponding drop probability is obtained by referring to a look-up table. This look-up table associates the values of the discard probabilities with each of the sections divided by each threshold value. As described above, in this packet processing apparatus, in order to obtain the discard probability, the threshold processing at predetermined equal intervals and the reference processing using the look-up table are employed, thereby limiting the hardware resources. RED can be realized efficiently.

JP 2005-94392 A

S. Floyd and V. Jacobson, "Random Early Detection Gateways for Congestion Aidance," IEEE / ACM Trans. on Networking, vol. 1 pp. 397-413, Aug. 1993.

  However, in the packet processing device described in Patent Literature 1, the intervals of the thresholds used in the threshold processing are equal, and the intervals need to be increased to some extent in order to increase the difference in processing speed from RED. Due to these factors, in this packet processing apparatus, when the distribution of the moving average value of the buffer accumulation amount is concentrated in a specific range, fairness among users, which is one of the advantages of RED, is not sufficient depending on traffic conditions. Cannot be secured. Specifically, when the distribution of the moving average value is concentrated around a certain threshold, a small difference in the buffer accumulation amount causes a large difference in the discard probability, and when the packet of the specific user arrives, Assuming a traffic condition in which only the buffer accumulation amount slightly increases, only the packet of the same user has a high discard probability, causing unfairness with other users.

  SUMMARY OF THE INVENTION The present invention has been made in view of the above-described circumstances, and an object of the present invention is to provide a packet control device having a buffer between users who transmit packets when discarding an incoming packet so that the buffer does not overflow. The goal is to make injustice less likely.

The packet control device of the present invention includes a packet discarding unit that discards an amount of packets according to a drop probability from an arriving packet, and temporarily stores packets that have not been discarded by the packet discarding unit among the arriving packets. A buffer for outputting after accumulation, an average value calculation unit for sequentially calculating a moving average value of the accumulation amount of the packets stored in the buffer, and a plurality of moving average values sequentially calculated by the average value calculation unit Among the statistical processing unit that generates a frequency distribution for a calculation period including the calculation time point of the past moving average value having the same value as the current moving average value, and the frequency distribution generated by the statistical processing unit Accordingly, a threshold value determining unit that determines a plurality of threshold values for the moving average value, and one of a plurality of sections divided by the plurality of threshold values determined by the threshold value determining unit, Perform serial threshold for classifying the moving average value calculated by the average value calculating unit process, characterized by having a probability determination unit configured to determine the drop probability according to the result of the threshold processing.

  According to the present invention, in a packet control device having a buffer and capable of discarding arriving packets so that the buffer does not overflow, a plurality of moving average values based on a frequency distribution of a moving average value of a buffer accumulation amount are provided. Since the thresholds are determined and the drop probability is determined using the thresholds, unfairness is unlikely to occur between users who transmit packets.

FIG. 2 is a block diagram illustrating a configuration example of a packet control device according to Embodiment 1 of the present invention. FIG. 9 is a diagram illustrating a relationship between a moving average value of a buffer accumulation amount and a discard probability in Comparative Example 1. FIG. 13 is a diagram illustrating a relationship between a moving average value of a buffer accumulation amount and a discard probability in Comparative Example 2 in comparison with a relationship in Comparative Example 1. FIG. 14 is a diagram illustrating an approximate discard probability table indicating a relationship between a moving average value of a buffer accumulation amount and a discard probability in Comparative Example 2. FIG. 2 is a diagram illustrating an example of a frequency distribution generated by a statistical processing unit in the packet control device of FIG. 1. FIG. 3 is a diagram illustrating an example of a relationship between a threshold value determined in the packet control device of FIG. 1 and a drop probability candidate value. FIG. 5 is a block diagram illustrating another configuration example of the packet control device according to the first embodiment of the present invention. 8 is a flowchart illustrating an example of a table update process in the packet control device of FIG. 7; FIG. 9 is a diagram illustrating an example of a table updated by the table updating process of FIG. 8; FIG. 14 is a diagram illustrating an example of a moving average value of a buffer accumulation amount accumulated along with time information in the packet control device according to the second embodiment of the present invention. FIG. 14 is a diagram illustrating an example of a frequency distribution used for determining a threshold value in the packet control device according to the second embodiment of the present invention. FIG. 13 is a block diagram illustrating a configuration example of a packet control device according to a third embodiment of the present invention. FIG. 13 is a block diagram showing another configuration example of the packet control device according to the third embodiment of the present invention. FIG. 9 is a diagram illustrating another configuration example of the packet control device according to the first to third embodiments of the present invention.

  Hereinafter, a packet control device according to each embodiment of the present invention will be described with reference to the drawings. The packet control device according to the present invention can be installed to avoid traffic congestion in a network that employs various protocols in which signals and data are transmitted in packets. This packet control device is preferably incorporated in a gateway device such as a router or a server device, but can also be incorporated in a packet input unit in various electronic devices such as a television device or an audio playback device.

Embodiment 1 FIG.
FIG. 1 is a block diagram showing a configuration example of the packet control device according to the first embodiment of the present invention. In FIG. 1, a thick arrow indicates a flow of a packet, and a thin arrow indicates a flow of control information.

  The packet control device 1 illustrated in FIG. 1 includes a packet discarding unit 11, a buffer 12 functioning as a packet storage unit, an average value calculating unit 13, a probability determining unit 14, a statistical processing unit 15, and a threshold determining unit 16. Further, the packet control device 1 may be configured to have a control unit (not shown) for controlling the whole. The packet arriving at the packet control device 1 is output from the packet control device 1 via the packet discarding unit 11 and the buffer 12.

  The packet discarding unit 11 discards a packet arriving at the packet control device 1, that is, a packet input to the packet control device 1, in an amount according to the discard probability determined by the probability determining unit 14. The packet discarding unit 11 may discard an amount of packets from the arrived packet according to the discard probability. The packet discarding unit 11 may randomly select a packet to be discarded or a passage target according to the discard probability. A discard target may be selected at a fixed cycle that matches the discard probability.

  The buffer 12 temporarily stores packets that have not been discarded by the packet discarding unit 11 among the arrived packets, and then outputs the packets. That is, the buffer 12 holds a packet that has passed without being discarded by the packet discarding unit 11 until it is output from the packet control device 1. Note that the buffer 12 may output the packet by, for example, FIFO (First In, First Out), but is not limited thereto. In addition, the capacity of the buffer 12 and the output timing of the packet in the packet control device 1 may be determined, for example, so that the process in a device connected to the subsequent stage of the packet control device 1 does not overflow.

  The average value calculation unit 13 sequentially calculates the average value of the accumulation amount of packets accumulated in the buffer 12 (hereinafter, referred to as a buffer accumulation amount). The average value calculated here means an average value sequentially calculated at predetermined calculation intervals based on the time-series data, that is, a moving average value. Here, the average value calculation unit 13 may measure (monitor) the accumulation amount of the buffer 12 or the remaining amount that can be accumulated at the above-described calculation interval. Alternatively, the buffer 12 may measure the accumulation amount or the remaining amount, and pass the measurement result to the average calculation unit 13. In the following, various processes are performed based on the buffer accumulation amount, including other embodiments, but the process of indirectly acquiring the moving average value based on the remaining amount of the buffer 12 is also included in the concept of the present invention. It is.

  The probability determination unit 14 determines the above-mentioned discard probability by calculating the above-mentioned discard probability or extracting the discard probability using a table described later. The discard probability is determined so that the incoming packets are discarded at an appropriate ratio according to the capacity of the buffer 12 without overflowing the buffer 12 in order to avoid traffic congestion. Details of this determination method will be described later.

  The statistical processing unit 15 generates a frequency distribution (frequency distribution) for a plurality of moving average values sequentially calculated by the average value calculation unit 13. The generation interval of the frequency distribution may be the same as the calculation interval of the moving average value in the average value calculation unit 13, but it is preferable to make the interval longer than that in order to reduce the processing load. Further, the statistical processing unit 15 has a storage unit 15a therein for generating a frequency distribution, and inputs a plurality of moving average values sequentially calculated by the average value calculation unit 13 to the storage unit 15a. Store (hold). The storage unit 15a may be provided outside the statistical processing unit 15.

  The threshold determining unit 16 receives information on the frequency distribution (referred to as statistical information) generated by the statistical processing unit 15 and determines a plurality of thresholds for the moving average value of the buffer accumulation amount according to the frequency distribution. . Then, the probability determining unit 14 performs a threshold process of classifying the moving average calculated by the average calculating unit 13 into one of the plurality of sections divided by the plurality of thresholds determined by the threshold determining unit 16. Then, the discarding probability used in the packet discarding unit 11 is determined according to the result of the threshold processing (that is, the classification result). The probability determination unit 14 may perform the threshold processing at the same interval as the calculation interval of the moving average value in the average value calculation unit 13 to determine the above-described discard probability, but at a probability determination interval longer than the calculation interval. You may perform those processes.

  Before specifically describing the determination of the discard probability in the present embodiment, comparative examples 1 and 2 relating to RED will be described with reference to FIGS. FIG. 2 is a diagram illustrating the relationship between the moving average value of the buffer accumulation amount and the discard probability in Comparative Example 1. FIG. 3 is a diagram showing the relationship between the moving average value of the buffer accumulation amount and the discard probability in Comparative Example 2 in comparison with the relationship of Comparative Example 1, and FIG. It is a figure showing an approximate discard probability table which shows a relation with a discard probability.

The packet control device of Comparative Example 1 determines the packet discard probability based on the moving average value of the buffer accumulation amount. Here, the moving average value of the buffer accumulation amount is defined by the following equation (1), where Qav is the moving average value of the buffer accumulation amount, Q is the current buffer accumulation amount, and w is the weighting factor.
Qav ← (1-w) × Qav + w × Q (1)

  Also, as shown in FIG. 2, in Comparative Example 1, when the buffer storage amount is less than the minimum threshold minTH, no packet is discarded (discard probability becomes 0%), and when the buffer storage amount exceeds the maximum threshold maxTH, All the packets are discarded (the discard probability becomes 100%). When the buffer accumulation amount is not less than minTH and not more than maxTH, the packet is discarded based on the discard probability according to the value of the buffer accumulation amount as indicated by the discard probability line Kr in FIG. In FIG. 2, maxP is the discard probability at the maximum threshold value maxTH, and is a parameter that determines the slope of the discard probability line Kr.

  On the other hand, the packet control device of Comparative Example 2 calculates the discard probability in Comparative Example 1 using a table called an approximate discard probability table, which associates the moving average value of the buffer accumulation amount with the discard probability. This approximate discard probability table is generated in advance based on the three parameters minTH, maxTH, and maxP of Comparative Example 1. Specifically, this approximate discard probability table is basically indicated by a discard probability line Kp in FIG. 3 obtained by dividing the buffer accumulation amount between the minimum threshold minTH and the maximum threshold maxTH of Comparative Example 1 into N equal parts. The relationship between the moving average value of the buffer accumulation amount and the discard probability is tabulated in advance, and is an approximate discard probability table as shown in FIG. For example, the packet control device of Comparative Example 2 refers to the predetermined approximate discard probability table of FIG. 4 and, when the moving average value of the current buffer storage amount is 70.00%, from among the discard probability candidate values. 37.5% is selected and set as the drop probability, and the arriving packet is dropped according to the drop probability. In FIG. 4, the moving average value of the buffer accumulation amount is, for example, 56.25 (%) or more and less than 62.50 (%) in the second row, and is simply described. The same is true for rows. However, the moving average value of the bottom row in FIG. 4 indicates 100.00 (%).

  Here, in FIG. 3, for example, when the distribution of the moving average value of the buffer accumulation amount is concentrated in a specific area near the threshold value such as the area Ra in the figure, the discard probability line Kp is changed to the discard probability line of Comparative Example 1. Compare with Kr. In the region Ra, the difference Dr of the drop probability in the comparative example 1 is small, but the difference Dp of the drop probability in the comparative example 2 is large. This is because the packet control device of the comparative example 2 performs the threshold processing at N steps at equal intervals. This is because the threshold processing is performed with a predetermined fixed threshold group irrespective of the distribution. Therefore, in Comparative Example 1, even when the distribution is concentrated in the area Ra, since there is no large difference in the drop probability between arriving packets, there is no unfairness among users under any traffic conditions. On the other hand, in Comparative Example 2, when the above distribution is concentrated in the area Ra, a small difference in the buffer accumulation amount causes a large difference in the discard probability due to the quantization, so that the discard probability between the arriving packets is large. Assuming a traffic condition in which the buffer storage amount slightly increases only when the packet of the specific user arrives at the packet control device of Comparative Example 2, the probability of discarding only the packet of the same user increases, Unfairness occurs between users sending packets.

  In order to reduce such unfairness, in the present embodiment, as described above, a plurality of thresholds are determined according to the frequency distribution of the moving average value of the buffer accumulation amount, and the discard probability is determined using those thresholds. To determine. Hereinafter, such processing will be described with a specific example while referring to FIGS. 5 and 6 together. FIG. 5 is a diagram illustrating an example of a frequency distribution generated by the statistical processing unit 15 in the packet control device 1, and FIG. 6 is a diagram illustrating an example of a relationship between a threshold value determined in the packet control device 1 and a discard probability candidate value. It is.

  First, the average value calculation unit 13 calculates the moving average value of the buffer accumulation amount as described above, and Expression (1) can be used as a calculation formula of the moving average value. In the present embodiment, a calculation formula to which another type of weighting method is applied may be employed instead of the calculation formula. However, the calculation of equation (1) is desirable because the average value calculation unit 13 can be configured by hardware, and the processing speed is high because it can be executed only from the past moving average value and the current buffer accumulation amount.

  When using the equation (1), the average value calculating unit 13 stores a past moving average amount inside or outside thereof, and overwrites the moving average value every time the moving average value is calculated. (Not shown) may be provided. Further, in the equation (1), the past buffer accumulation amount affects the calculation result. However, the effect of the distant past buffer accumulation amount is that the weighting coefficient (1-w) is accumulated in the value. Few. Even when another type of weighting method is applied, a storage amount storage unit (not shown) for storing the past buffer storage amount up to the present may be provided inside or outside the average value calculation unit 13. Thus, when calculating the moving average value of the current buffer storage amount, the average value calculation unit 13 can read the buffer storage amount stored in the storage amount storage unit.

  In the case of using the expression (1), the description has been made on the assumption that all buffer storage amounts up to the present are reflected, and on the assumption that the storage amount storage unit stores all buffer storage amounts up to the present. . However, the average value calculation unit 13 does not have to use all the past buffer accumulation amounts when calculating the current moving average value. When the equation (1) is employed, for example, when the reset button separately provided in the packet control device 1 is pressed or when the power is turned on after the power is turned off, the average value calculation unit 13 and the like are stored in the moving average value storage unit. The stored past moving average value data may be deleted. When calculating the current moving average value by using the past buffer accumulated amount data instead of using the past moving average value as it is in Expression (1), the reset button or the power-off state after the power is turned off is used. When the power is turned on, the average value calculation unit 13 and the like may delete the data of the past buffer storage amount stored in the storage amount storage unit. As an alternative process, the average value calculation unit 13 stores the past buffer storage amount from the present to a certain period before in the storage amount storage unit, that is, deletes the buffer storage amount before that. You may keep it. In the packet control device 1, the storage unit 15a and the moving average value storage unit or the accumulation amount storage unit can use a common storage device.

  The moving average values sequentially calculated by the average value calculation unit 13 are sequentially output to the probability determination unit 14 and the statistical processing unit 15. The statistical processing unit 15 stores these moving average values in the storage unit 15a, and generates a frequency distribution for the stored moving average values. The frequency distribution may be a histogram (frequency distribution diagram) as illustrated in FIG. 5 or a bin B value (moving average value) and its frequency value, as illustrated in the illustrated histogram. An associated lookup table (hereinafter, referred to as a frequency table) may be used. However, since a threshold value determination process described later can be executed if there is at least a frequency table, it is sufficient to generate a frequency table. The vertical axis in FIG. 5 represents the frequency (occurrence frequency) of the moving average value of the buffer accumulation amount in the buffer 12, and the total frequency of packets transmitted from all users (specifically, terminals of all users). Is represented.

  The width and the number of bins B in this frequency distribution may be determined in advance based on the minimum threshold minTH and the maximum threshold maxTH as used in Comparative Example 1, or may simply be the average value calculation unit 13. The unit that can be calculated in is a bin width, and the calculated moving average value is assigned to each bin B as it is, and the number of bins B may be determined based on the minimum threshold minTH and the maximum threshold maxTH. The number of bins B can be calculated by dividing the difference between the maximum threshold value maxTH and the minimum threshold value minTH by the bin width. In addition, at the time of division, it is sufficient to actually perform integer conversion using a ceiling function or the like, and in that case, processing such as increasing or decreasing the width of both ends in the frequency distribution may be required. is there.

  Here, an example using the minimum threshold minTH and the maximum threshold maxTH in Comparative Example 1 has been described. However, the minimum threshold and the maximum threshold in the present embodiment may be 0% and 100%, respectively, and both may be fluctuation values. It may be. In the example in which the minimum threshold and the maximum threshold are set as the fluctuation values, the statistical processing unit 15 refers to the moving average stored in the storage unit 15a, and sets the minimum and maximum of the actual moving average to the minimum threshold and the maximum. What is necessary is just to use it as a threshold value. In this case, the width or number of the bins may be determined in advance. If the width of the bin is determined, the number of bins can be calculated as described above. In this case, when converting to an integer, it is necessary to increase or decrease the width at both ends in the frequency distribution. Sometimes. Conversely, if the number of bins is determined, the width of the bin can be calculated by dividing the difference between the maximum threshold and the minimum threshold by the number of bins.

  In addition, by storing the generated frequency distribution information (statistical information) in the storage unit 15a, the next generation of the statistical information can be executed using the statistical information. For example, when the statistical processing unit 15 receives the current moving average value from the average value calculating unit 13, the statistical processing unit 15 only increases the frequency value corresponding to the moving average value by 1 with respect to the statistical information at that time, Statistical information can be updated.

  The moving average value stored in the storage unit 15a may be deleted after a certain period of time, or by pressing the reset button or turning on the power after turning off the power. Thereby, the statistical processing unit 15 can obtain a frequency distribution that reflects the recent tendency more, and the threshold value determining unit 16 can use the frequency distribution to determine a threshold value and the like. When the moving average value accumulated in the storage unit 15a is deleted after the elapse of a certain period, the statistical processing unit 15 may store the moving average value in the storage unit 15a together with time information. Also, the statistical processing unit 15 stores the statistical information generated in the storage unit 15a together, so that only the process of decreasing the frequency value corresponding to the moving average value to be deleted by 1 is performed, and the statistical information Updates are possible.

  The threshold value determining unit 16 receives the statistical information generated by the statistical processing unit 15 and, based on the frequency distribution indicated by the statistical information, sets a plurality of threshold values (moving average values of the buffer accumulation amount) for the moving average value of the buffer accumulation amount. (A plurality of thresholds used for the determination). Note that the threshold determination unit 16 basically uses the minimum threshold and the maximum threshold used in the statistical processing unit 15 as they are, and determines a threshold within the range indicated by the threshold and the maximum threshold. However, the threshold value determining unit 16 may separately determine the minimum threshold value and the maximum threshold value so as to narrow or expand the range indicated by the minimum threshold value and the maximum threshold value used in the statistical processing unit 15.

  An example of the threshold value determining process in the threshold value determining unit 16 will be described. FIG. 5 also shows the result of drawing a frequency curve Fd connecting the frequency values of each bin B based on the generated histogram. The threshold determination unit 16 receives the histogram from the statistical processing unit 15 and derives such a frequency curve Fd. This frequency curve Fd can be derived only from the frequency table. The process of deriving the frequency curve Fd may be performed by the statistical processing unit 15.

  Next, the threshold determination unit 16 (or the statistical processing unit 15) calculates an area S surrounded by the frequency curve Fd and the axis of the moving average value of the buffer accumulation amount. The threshold value determining unit 16 (or the statistical processing unit 15) adds the [width of bin B] × [the frequency value] for all bins B from only the frequency table without obtaining the frequency curve Fd to obtain the area. S may be configured to be calculated.

Then, the threshold determination unit 16 divides the acquired histogram so that the area S is equal to N (S ₁ = S ₂ =... = S _N = S / N), and the division point X, which is the division boundary, is obtained. _{0, X} 1, ..., to calculate the _{X N.} Here, N is the number of thresholds previously determined, _{X 0} is the minimum threshold MINTH, _{X N} is determined in advance respectively on the maximum threshold maxth. Note that S = S ₁ + S ₂ +... + _SN . This division can also be executed only from the frequency table. If the cumulative frequency value is separately calculated for each bin B, a bin B indicating the cumulative frequency value corresponding to the value obtained by dividing the area S by N can be obtained, and similarly, the value of k / N of the area S Can be obtained. As described above, the threshold value determination unit 16 can be configured to have the frequency table.

As can be seen from FIG. 5, since the area S is divided into N equal parts, the difference between adjacent division points is larger in a range with a small frequency value than in a range with a large frequency value. For example, the frequency value is between X ₀ of X ₁ is smaller than the other ranges, such as between X _k-1 of X _k, in other ranges, such as the difference between [Delta] X ₁ division point difference [Delta] X _k It is wider than that.

Then, the threshold value determination unit 16 sets the division points X ₀ , X ₁ ,..., X _N as representative values of the moving average value of the buffer accumulation amount (hereinafter, referred to as moving average representative values). In addition, as illustrated in FIG. 6, the threshold value determination unit 16 determines the average value of the determined moving average representative value and the adjacent moving average representative value as the threshold values Y ₁ , Y ₂ ,..., Y _N. Specifically, for example, the threshold determination unit 16, _wherein, to determine the _{Y k = (X k-1} + X k) / 2 by the threshold _{Y k.} As shown in FIG. 6, a section Δ _k (k = 1, 2,..., N) divided by adjacent thresholds Y _k−1 , Y _k is narrow in a section where the frequency of the moving average value is large (for example, the section Δ ₅ , Δ ₆ ) and wide in sections with low frequency (eg, sections Δ ₂ , Δ ₃ ). The threshold determining unit 16 outputs (notifies) the determined threshold to the probability determining unit 14. In the example described here, the threshold value determining unit 16 does not output the moving average representative value to the probability determining unit 14.

Further, here, an example is described in which the division point X _k is set as a moving average representative value and the average value Y _k of adjacent division points is set as a threshold, but the threshold value determination unit 16 sets the division point X _k as a threshold. The threshold value may be determined, and the average value Y _k (= (X _k−1 + X _k ) / 2) of adjacent division points may be determined as the moving average representative value.

  Referring to FIG. 5, an example is given in which the threshold is determined by dividing the area S into N equal parts. However, as in this example, the threshold determining unit 16 has a high frequency of the moving average value indicated by the frequency distribution. It is preferable to determine a plurality of thresholds so that the section becomes narrower as the section becomes smaller. As described above, the threshold determination unit 16 narrows the section (the interval between adjacent thresholds) in a range where the frequency value is large (range of the moving average value), and widens the section in a range where the frequency value is small, thereby increasing the buffer accumulation amount. Many threshold values can be arranged in a portion where the distribution of the moving average value is concentrated.

  It is possible to realize the determination of the threshold value in such a tendency by other methods. For example, the threshold determination unit 16 extracts a moving average value having the highest frequency value, obtains a certain range centered on the moving average value (for example, a range separated by a certain number of bins from the center), Is defined as another fixed range that is wider than the fixed range. Then, the threshold value determination unit 16 determines a boundary between these ranges as a threshold value.

  Next, an example of the probability determining process in the probability determining unit 14 will be described. It is preferable that the probability determination unit 14 determines a plurality of discard probability candidates corresponding to a plurality of sections divided by the plurality of thresholds determined by the threshold determination unit 16. The packet control device 1 includes a threshold storage unit that stores the threshold value determined by the threshold determination unit 16 and a discard probability candidate value storage unit that stores the discard probability candidate value inside or outside the probability decision unit 14. The storage unit also stores information on the association between the discard probability candidate value and the section (or the threshold value at both ends). The threshold storage unit may be replaced by an electric element such as a variable resistor that outputs a voltage value corresponding to each section. The discard probability candidate value storage unit can be replaced with an electric element such as a variable resistor that outputs a voltage value corresponding to each of the discard probability candidates.

Specifically, when a plurality of threshold values are input from the threshold value determining unit 16, the probability determining unit 14 updates a plurality of past threshold values with the input values and, for example, updates the plurality of threshold values of the discard probability line Ki shown in FIG. In this manner, a plurality of discard probability candidates corresponding to a plurality of sections on a one-to-one basis are calculated. In the example of the discard probability line Ki, for each of the sections Δ _k (k = 1, 2,..., N) separated by the adjacent thresholds Y _k−1 , Y _k , from the minimum value 0% to the maximum value maxP as the interval and interval delta _k disposal adjacent probability candidate values _{P k-1, P k} are proportional to the calculated discard probability candidate values _{P 1, P 2, ...,} P k-1, a ... _{P N-1} are doing. This proportionality coefficient is the same as the slope of the discard probability line Kr of Comparative Example 1, but is not limited to this.

Also, the probability determining unit 14 calculates the discard probability linear Kr of Comparative Example 1 prepared in advance, the value of the drop probability corresponding to the median value of each interval delta _k (corresponding to the moving average representative value X _k-1) By doing so, or by extracting with reference to the correspondence stored in advance, the discard probability candidate value P _k−1 in that section may be determined.

  Then, the probability determination unit 14 performs threshold processing on the moving average calculated by the average calculation unit 13, and the plurality of discard probabilities corresponding to the section indicated by the result of the threshold processing among the plurality of sections. The discard probability candidate value among the candidate values is output to the packet discard unit 11 as the discard probability. Explaining briefly with the example of FIG. 6, the probability determining unit 14 determines the discard probability from the input moving average value with reference to the discard probability line Ki (or information describing the relationship).

Thereby, the packet discarding unit 11 can discard the arriving packet with the discard probability according to the current moving average value and the distribution of the moving average value. For example, in the portion shown in FIG. 6 at d _2, but the drop probability candidate value greatly changes from P ₁ to P _2, the frequency of the moving average of the packet accumulated amount is in the interval [Delta] X ₂ that contains this portion The number is small (that is, it is rare that the moving average value corresponding to this neighborhood is input from the average value calculation unit 13). Meanwhile, for example, in the portion indicated by the d ₅ 6 corresponds from the packet accumulated amount in the frequency of the moving average value is large (i.e. the average value calculating unit 13 in the section [Delta] X ₅ including the portion to the vicinity movement The input of the average value is concentrated), but the change in the discard probability candidate value is small. Therefore, in the present embodiment, as a whole, the frequency of unfairness remaining between users is small, and the fairness can be improved.

In the example described above, the threshold value determination unit 16 determines the moving average representative value. However, an example in which the threshold value is not determined may be adopted. For example, the division point _Xk may be determined as a threshold, and the average value _Yk of adjacent division points may not be calculated. Also in such an example, the probability determining unit 14 can determine a plurality of discard probability candidate values corresponding to a plurality of sections divided by a plurality of thresholds, and calculate the moving average value input from the average value calculating unit 13. Since a threshold value process can be performed, the drop probability output to the packet drop unit 11 can be determined.

  FIG. 7 shows a packet control device 1a having a configuration example different from that of the packet control device 1 of FIG. As shown by the packet control device 1a, the probability determining unit 24 provided in place of the probability determining unit 14 has a table (lookup table) 24t in which a plurality of sections are associated with a plurality of discard probability candidates. Note that the table 24t may be stored in a storage unit inside the probability determining unit 24, but the table 24t may be configured as hardware separate from the probability determining unit 24. Further, the threshold storage unit and the discard probability candidate value storage unit described above may be storage units that store the table 24t.

  Further, every time a plurality of threshold values are determined by the threshold value determining unit 16, the probability determining unit 24 inputs those threshold values, determines a discard probability candidate value according to the threshold values, and displays the table 24t with the result. Update it. The table 24t is formally the same as the approximate discard probability table of FIG. However, as described above, the threshold value determination unit 16 determines the threshold value by allowing the width of the section to be different, and determines the discard probability candidate value according to the threshold value. Different from the approximate discard probability table.

  Then, the probability determining unit 24 performs threshold processing on the current moving average value input from the average value calculating unit 13 with reference to the table 24t, and discard probability candidates corresponding to the section indicated by the result of the threshold processing. The value is extracted as a drop probability output to the packet drop unit 11. In this way, by configuring the probability determining unit 24 to have the table 24t, it is only necessary to update and refer to the table 24t.

  As described above, in the present embodiment, a plurality of threshold values for the moving average value of the buffer accumulation amount are determined by utilizing the frequency distribution of the moving average value of the buffer accumulation amount, and the discard probability is determined based on the threshold values. Are determined, and a large number of thresholds are arranged in a portion where the distribution of the moving average value of the buffer accumulation amount is concentrated (a fine portion), and a small number of thresholds are arranged in a portion where the distribution is sparse. Therefore, in the present embodiment, it is possible to prevent a large difference in the drop probability between packets in a portion where the distribution of the moving average value is concentrated, and it is unlikely that unfairness occurs between users who transmit packets, and between users. Fairness can be achieved. Further, in the present embodiment, a configuration using hardware is possible, and the processing speed is faster than that in Comparative Example 1. Further, by setting the interval of the update processing of the threshold value and the discard probability candidate value longer than the interval of the current discard probability determination processing using those values, it is possible to particularly reduce the processing load.

  In the above example, the discard probability is determined by performing a threshold process on the moving average value output from the average value calculation unit 13. However, upon determining the discard probability, the moving average value is once thresholded to determine the moving average. After being converted to a value (in other words, after being quantized), the discard probability may be determined. The quantization in this case corresponds to non-linear quantization because the quantization step width corresponding to the threshold interval is not constant. In this case, the threshold value means a quantization threshold value, and the moving average representative value means a quantization representative value.

  An example of a method for determining a discard probability using such non-linear quantization will be described. However, here, an example of the flow of the method of determining the discard probability described with reference to FIGS. 5 and 6 is again simplified from the viewpoint of non-linear quantization, and the current moving average value is changed to the moving average. A description will be given of a changed portion in a case where an application example in which a discard probability is determined after conversion into a representative value (quantized representative value) is adopted.

  In this example, the threshold value determination unit 16 determines not only the quantization threshold value but also the quantization representative value, and outputs the quantization representative value to the probability determination unit 24. The probability determining unit 24 stores a discard probability candidate value in association with each of the quantized representative values. Also in this example, a lookup table such as the table 24t can be used. In the above application example, the quantization representative value is described in the table 24t instead of the quantization threshold. Hereinafter, an example in which the table 24t is used will be described, but non-linear quantization can be similarly used in an example where the table 24t is not used.

  First, as the initial value of the quantization representative value in the table 24t, for example, a value when the buffer storage amount is equally divided into N is set. Also in this example, the process of updating the quantization representative value, the quantization threshold value, and the discard probability candidate value (the process of updating the table 24t in this example) and the process of determining the current discard probability using these values are performed. It may be performed periodically at the same time interval. In this example, the same time interval indicates the quantization cycle.

  An example of such a process of updating the table 24t will be described with reference to FIGS. 8 and 9 together. FIG. 8 is a flowchart illustrating an example of a table update process in the packet control device 1a of FIG. 7, and FIG. 9 is a diagram illustrating an example of a table updated by the table update process of FIG.

  First, the statistical processing unit 15 generates a frequency distribution (exemplified by a histogram as shown in FIG. 5) of the moving average value of the buffer accumulation amount input from the average value calculation unit 13, and the threshold value determination unit 16 generates the frequency distribution. The statistical information indicating the distribution is obtained (step S1). Next, the threshold value determination unit 16 divides the histogram indicated by the statistical information into N parts such that the areas are equal (Step S2), and determines a value that is a boundary when the N division is made as a quantization representative value (Step S2). S3) The average value of adjacent quantized representative values is determined as a quantization threshold (step S4). Next, the threshold determination unit 16 notifies the probability determination unit 24 of the quantization representative value and the quantization threshold (Step S5). The details of these processes are as described with reference to FIGS.

Next, each time the quantization representative value and the quantization threshold are input from the threshold determination unit 16, the probability determination unit 24 determines a discard probability candidate value (for example, the discard probability in FIG. 6) based on the quantization representative value (or the quantization threshold). probability candidate values _{P 1, P 2, ...,} and calculates the _{P N-1)} (step S6). The details of this calculation process are also as described with reference to FIG.

Next, the probability determining unit 24 updates the approximate drop probability table 24t based on the quantization threshold and the drop probability candidate value (step S7). This table 24t can be illustrated in FIG. Note that in FIG. 9, Y ₁ , Y ₂ ,..., Y _N indicate quantization thresholds. In FIG. 9, the moving average value of the buffer accumulation amount indicates, for example, not less than minTH (%) and less than Y1 (%) in the second row, and the same applies to other rows. is there. In addition, the moving average value of the bottom row in FIG. 9 indicates maxTH (%) or more. In the application example described above, in step S7, the table 24t is updated so that the quantization representative value is used instead of the quantization threshold value, and the plurality of quantization representative values and the plurality of discard probability candidates are associated one-to-one.

  The table 24t is updated as described above. The subsequent determination of the discard probability corresponding to the current moving average value in the probability determination unit 24 is as described above. However, in the above application example, the quantization representative value is described in place of the quantization threshold in the table 24t, and therefore, the table 24t cannot be referred to simply by the threshold processing of the current moving average value.

  Therefore, in the above application example, the probability determining unit 24 calculates a plurality of quantization thresholds and a plurality of quantization representative values determined by the threshold value determining unit 16 for the current moving average value input from the average value calculating unit 13. (Non-linear quantization) based on, and is converted to a quantization representative value. That is, the probability determining unit 24 classifies the input current moving average value into one of a plurality of sections divided by the quantization threshold, and associates the quantized representative value with the section indicated by the classification result. Convert to Thereafter, the probability determining unit 24 refers to the table 24t to extract a discard probability candidate value associated with the quantized representative value of the quantization result, and uses the extracted discard probability candidate value as a discard probability. 11 is output.

  When the table 24t is used in the above application example, a table in which a plurality of quantization threshold values and a plurality of quantization representative values are associated one-to-one, and a plurality of quantization representative values and a plurality of discard probability candidate values are one-to-one. Are made up of two tables, the table corresponding to. In the above application example, the quantization representative value may be a value having a smaller amount of information such as a quantization index.

  Further, in the above, the process of updating the threshold value and the candidate value of the discard probability (for example, the process of updating the table 24t) and the process of determining the current discard probability using those values are periodically performed at the same time interval. Alternatively, the present embodiment has been described, particularly on the premise that the interval between the update processing of the threshold value and the discard probability candidate value is made longer than the interval of the current discard probability determination processing using those values.

  However, the above-described update processing may not be performed at regular time intervals. For example, each time the statistical processing unit 15 obtains a certain amount of statistical information, the threshold value determining unit 16 updates the threshold value, and the probability determining unit 14 or the probability determining unit 24 updates the discard probability candidate value or the like in accordance with the update ( For example, a process of updating the table 24t) may be executed.

  An example of such processing will be described. First, the average value calculation unit 13 is configured not to output the result to the statistical processing unit 15 when the result of calculating the moving average value is smaller than a certain value (for example, minTH in FIGS. 5 and 6). . In this case, the average value calculation unit 13 may be configured to output the result to the probability determination unit 14 or the probability determination unit 24. The average value calculation unit 13 outputs the moving average value to the statistical processing unit 15 irrespective of the result, and the statistical processing unit 15 ignores the result when the result is smaller than the fixed value, and A moving average value that is effective only when the value is equal to or greater than the value may be handled.

  Then, the statistical processing unit 15 notifies the threshold determination unit 16 of the update timing of the threshold every time a fixed amount of effective moving average value is obtained, that is, each time a certain amount of statistical information is obtained. Alternatively, the threshold determination unit 16 monitors the accumulation amount of the statistical information in the statistical processing unit 15 and determines a timing at which the amount increases by a certain accumulation amount as the update timing. In any case, the threshold value determination unit 16 executes the update process of the threshold value at the update timing, and the probability determination unit 14 or the probability determination unit 24 receiving the result executes the update process of the discard probability candidate value or the like. When the update timing is determined in this manner, the statistical processing unit 15 discards old statistical information exceeding the above-mentioned fixed storage amount, or sets the statistical information as a reference target in the threshold determination unit 16. It is preferable not to do so.

  With such processing, when the input rate to the packet control devices 1 and 1a is high, a large amount of statistical information can be obtained, so that the update interval is short. When the input rate is low, only a small amount of statistical information can be obtained. The update interval becomes longer. That is, by such processing, the update processing can be executed at the timing when the same amount of statistical information (the number of samples) is accumulated regardless of the input rate, and the following effects are obtained.

  That is, when the input rate is high, if the update process is executed every time a certain amount of statistical information is obtained, the threshold value can be updated immediately when sufficient statistical information can be obtained, as compared to the periodic update process. (It can be optimized for the latest statistical information.) Therefore, high fairness can always be secured. In addition, when the input rate is low, if the update process is executed every time a certain amount of statistical information is obtained, the threshold value is updated at a timing that is meaningful for the update, compared to the periodic update process, and thus unnecessary The arithmetic processing is not performed, and the processing time can be reduced.

Embodiment 2 FIG.
A packet control device according to Embodiment 2 of the present invention will be described with reference to FIGS. 10 and 11 together. The configuration of the packet control device according to the present embodiment is basically the same as FIG. 1 or FIG. In addition, various examples described in Embodiment 1 can be applied to this embodiment. FIG. 10 is a diagram illustrating an example of a moving average value of the buffer accumulation amount accumulated together with time information in the packet control device according to the present embodiment. FIG. 11 is a diagram illustrating statistical information used for determining a threshold value in the packet control device. It is a figure showing an example.

  In the first embodiment, a plurality of threshold values are determined according to the frequency distribution of the moving average value of the buffer accumulation amount, and the discard probability is determined based on the threshold values. Is generated from information close to the moving average value of the current buffer storage amount. Specifically, the statistical processing unit 15 in the present embodiment calculates a past moving average value having the same value as the current moving average value among the plurality of moving average values calculated by the average value calculating unit 13. A frequency distribution is generated for a calculation period including a time point.

More specifically, the statistical processing unit 15 first uses the time series data X (t) of the moving average value of the buffer accumulation amount as illustrated in FIG. past moving average value and the calculated time with the same value as the moving average value X _P amount (calculation time also including calculation date is preferred) is extracted. Then, the statistical processing unit 15 extracts only the moving average value calculated before the calculation period T elapses from the calculation date and time as a start point as a target of the statistical processing, and generates a frequency distribution. The calculation period T may be a predetermined period. Further, the moving average value of the current buffer storage amount may be counted as a target of the statistical processing. When there are a plurality of target start points, such as the time-series data X (t) illustrated in FIG. 10, the statistical processing unit 15 extracts all of them.

  Note that the statistical processing unit 15 may set only the moving average value calculated within the calculation period T including the calculation date and time as the target of the statistical processing, instead of using the calculation date and time as a starting point, but basically, Since it is necessary to cope with the overflow of the buffer 12 that may occur in the future from the present time, it is preferable that the calculation period T is determined so as to include more moving average values than the above calculation date and time.

As illustrated in FIG. 11, the histogram HT generated from the moving average value in the calculation period T including the calculation date and time as a starting point or the like is a histogram generated from the moving average value in the entire period as in the first embodiment. compared to HA, so the frequency is higher than the essentially other ranges around the moving average value X _P of the current buffer fullness.

The histogram generated as described above is used in the process of determining a threshold value and the like in the threshold value determining unit 16 as in the first embodiment, and the subsequent processes are the same as in the first embodiment. As a result, threshold determined from the histogram HT, compared to the threshold determined from the histogram HA, it can be positioned in a number around the moving average value X _P of the current buffer fullness. Therefore, in the present embodiment, as compared with the first embodiment, a large difference in the drop probability between packets is less likely to occur, and it is possible to further ensure fairness among users.

In the above example, the statistical processing unit 15 generates the frequency distribution from the moving average value for the calculation period T including the calculation date and time. The extraction method (extraction conditions) is not limited to this. For example, the statistical processing unit 15 extracts the past moving average value and the calculated date and time that the difference has a value which falls within a constant value between the moving average value X _P of the current buffer fullness, calculation period including the calculation date Only the moving average calculated within T is used for generating the frequency distribution. In this case, although there are duplicate data, only one duplicate is used.

And other examples, the statistical processing section 15, or decreased the current with reference to the moving average value back calculation from the current moving average value X _P period T (or different calculation period length) that is increasing It is determined whether there is a tendency. The statistical processing section 15 are the same as the moving average value X _P (or difference falls within a predetermined value) of the moving average value calculated in the calculation period T including a calculation time of past moving average, the current The frequency distribution is generated only from those having the same tendency as the tendency. In the example of FIG. 10, since the present trend is decreasing, the frequency distribution is generated only from the moving average value of the third calculation period T among the four calculation periods T in the time-series data X (t). become. By employing such extraction conditions, as well as many threshold near the moving average value X _P as a result is to be placed, also be able to reflect predicted based on time series data X (t) .

Embodiment 3 FIG.
Third Embodiment A third embodiment of the present invention will be described with reference to FIGS. FIG. 12 is a block diagram illustrating a configuration example of a packet control device according to the present embodiment, and FIG. 13 is a block diagram illustrating another configuration example. Although the present embodiment will be described focusing on differences from the packet control device 1 of FIG. 1 in the first embodiment, the various examples described in the first and second embodiments can also be applied to the present embodiment.

  In the first embodiment, an example in which RED is used as a congestion control method will be described, and one type of packet arriving at the packet control device 1 or, even if there are a plurality of types, the processing will not differ for each type. Is assumed. In the packet control device according to the present embodiment, when there are a plurality of types of arriving packets, the processing is different for each type.

  As illustrated in FIG. 12, a packet control device 1b according to a configuration example of the present embodiment includes, in addition to the configuration of the packet control device 1 of FIG. 1, a determination unit that determines an arrival type, which is a type of an arrived packet. Seventeen. The packet control device 1b further has a probability determining unit. This probability determining unit determines the drop probability for each reference type that is a predetermined packet type, and can be configured by, for example, providing the probability determining units 14 in FIG. 1 by the number of reference types. .

  Here, an example in which three probability determination units 14 are provided in consideration of a packet with a priority to which priority information indicating any of a high priority, a medium priority, and a low priority is added as a packet type And these are referred to as a first probability determining unit 14a, a second probability determining unit 14b, and a third probability determining unit 14c. However, when the probability determination units 14a to 14c are configured by hardware, they may be configured as one piece of hardware.

  The determining unit 17 according to the present embodiment transmits not only the arriving packet but also information indicating the type of arrival to the packet discarding unit 11. The packet discarding unit 11 inputs information indicating the arrival type, and discards packets belonging to this arrival type in an amount corresponding to the discard probability of the reference type corresponding to the arrival type. Therefore, a discard probability corresponding to each of the reference types is set in the packet discard unit 11. In this example, the information indicating the arrival type corresponds to the result of the priority discrimination (priority information), and the packet discard unit 11 has three discard probabilities corresponding to the priority types as examples of the reference type. Is set.

  That is, the first probability determining unit 14a determines the discard probability Pa for the high priority as one of the reference types, and the second probability determining unit 14b determines the discard probability Pb for the medium priority as one of the reference types. And the third probability determining unit 14c determines the drop probability Pc for the low priority as one of the reference types, and outputs the drop probability Pc to the packet drop unit 11, respectively.

  Specifically, a method of determining the discard probabilities Pa to Pc will be described. First, the threshold determination unit 16 determines a plurality of thresholds (hereinafter, referred to as threshold groups) as in Embodiment 1, and outputs the thresholds to the first to third probability determination units 14a to 14c. The first to third probability determining units 14a to 14c all receive a common threshold group. The frequency distribution used when the threshold value group is determined by the threshold value determining unit 16 is also common, and the statistical processing unit 15 does not perform statistical processing for each reference type. That is, the statistical processing unit 15 does not separately perform the statistical processing for each of the high priority, the medium priority, and the low priority.

  The first probability determination unit 14a determines a high-priority discard probability candidate value for each of a plurality of sections separated by the threshold group, and determines a corresponding adjacent threshold (adjacent threshold in the threshold group). Alternatively, it is associated with a corresponding section. In addition, the second probability determination unit 14b determines, for each of the plurality of sections divided by the threshold value group, a medium-priority discard probability candidate value such that the value becomes larger than that for the high priority, It is associated with a corresponding adjacent threshold or a corresponding section. Supplementally, with such a determination, the medium-priority discard probability candidate value corresponding to a certain section Δk becomes larger than the high-priority discard probability candidate value corresponding to the section Δk, This is true for all sections. Similarly, the third probability determination unit 14c determines a low-priority discard probability candidate value for each of the sections divided by the threshold group so as to have a larger value than the medium-priority section. Associated with adjacent thresholds or corresponding sections. In this example, the maximum value (maxP) of the discard probability candidate values is smaller for the high priority than for the medium priority, and smaller for the medium priority than for the low priority.

  In addition, the discard probability candidate values and the like determined in this manner may be described in a look-up table such as the table 24t shown in FIG. 7, and in that case, each of the probability determination units 14a to 14c may be described. Can be configured to have different tables.

  Then, the first probability determination unit 14a performs a threshold process of classifying the moving average calculated by the average calculation unit 13 into any of a plurality of sections divided by the common threshold group. The high-priority drop probability candidate value corresponding to the section indicated by the processing result is output to the packet drop unit 11 as the drop probability Pa.

  When the result of the determination by the determining unit 17 indicates that the priority is one of the reference types, the packet discarding unit 11 discards the high-priority packet according to the high-priority discard probability Pa. Perform disposal. That is, when a high-priority packet arrives, the packet discarding unit 11 determines whether to discard or pass the high-priority packet that has arrived according to the discard probability Pa, and discards or passes according to the determination result. Execute.

  Similarly, the second probability determination unit 14b performs threshold processing on the moving average calculated by the average calculation unit 13 using the common threshold group, and performs processing corresponding to the section indicated by the result of the threshold processing. Then, the discard probability candidate value for medium priority is output to the packet discard unit 11 as the discard probability Pb. When the result of the determination by the determining unit 17 indicates that the packet has the medium priority, the packet discarding unit 11 discards the packet of the medium priority according to the discard probability Pb for the medium priority.

  Similarly, the third probability determining unit 14c performs threshold processing on the moving average value calculated by the average value calculating unit 13 using the common threshold group, and corresponds to the section indicated by the result of the threshold processing. The discard probability candidate value for low priority is output to the packet discarding unit 11 as the discard probability Pc. If the result of the determination by the determining unit 17 indicates that the priority is low, the packet discarding unit 11 discards the low-priority packet according to the low-priority discard probability Pc.

  The method of making the processing different for each priority is realized by WRED (Weighted RED) assuming that the above-described priority information is attached to a packet and arrives. However, in the present embodiment, As described above, the discard probability for each priority is made different according to the statistical information. Also in the present embodiment, various applications applicable to WRED can be applied.

  Next, another configuration example of the present embodiment will be described with reference to FIG. The packet control device in this configuration example includes a threshold value determination unit that determines a plurality of threshold values for each reference type that is a predetermined packet type. This threshold determination unit can be configured by, for example, providing the threshold determination units 16 of FIG. 1 by the number of reference types.

  Also in this configuration example, an example in which three types of priorities are applied as packet types will be described. As illustrated in FIG. 13, the packet control device 1c of the present configuration example is provided with three threshold value determination units 16 in the packet control device 1b, and the three threshold value determination units 16a and the second threshold value It is referred to as a determination unit 16b and a third threshold value determination unit 16c. However, when the threshold value determination units 16a to 16c are configured by hardware, they may be configured as one piece of hardware.

  In this configuration example, the first threshold value determination unit 16a determines a threshold group for high priority as one of the reference types. Similarly, the second threshold determination unit 16b determines a threshold group for medium priority as one of the reference types, and the third threshold determination unit 16c determines a threshold group for low priority as one of the reference types. Determine groups. The first to third threshold value determination units 16a to 16c all use common statistical information to determine different threshold value groups. The first to third threshold value determination units 16a to 16c may be set so that, for example, the higher the priority, the smaller the section divided by the threshold group. This is because, as will be described later, also in this example, the lower the priority, the larger the maximum value (maxP) of the discard probability candidate values, and the higher the priority, the smaller the difference between the discard probability candidate values in adjacent sections. It is.

  The probability determination unit in this configuration example performs a threshold process for each reference type to determine a discard probability. Specifically, first, the first probability determining unit 14a uses the threshold group Tha for high priority determined by the first threshold determining unit 16a, and performs a process for each of the plurality of sections divided by the threshold group Tha. , A discard probability candidate value for high priority is determined, and is associated with a corresponding adjacent threshold (adjacent threshold in the threshold group Tha) or a corresponding section. The second probability determining unit 14b uses the threshold group Thb for middle priority determined by the second threshold determining unit 16b, and calculates a medium priority for each of the plurality of sections divided by the threshold group Thb. A discard probability candidate value is determined, and is associated with a corresponding adjacent threshold (adjacent threshold in the threshold group Thb) or a corresponding section. The third probability determining unit 14c uses the low-priority threshold group Thc determined by the third threshold determining unit 16c, and performs a low-priority threshold group for each of the plurality of sections divided by the threshold group Thc. The discard probability candidate value is determined, and is associated with a corresponding adjacent threshold (adjacent threshold in the threshold group Thc) or a corresponding section.

  The first to third probability determination units 14a to 14c have different threshold groups, but for any moving average value, the discard probability candidate value for medium priority compared to that for high priority And the discard probability candidate value for the low priority becomes larger than that for the medium priority. Also in this example, the maximum value (maxP) of the discard probability candidates is smaller for the high priority than for the medium priority, and smaller for the medium priority than for the low priority.

  Then, the first probability determination unit 14a performs a threshold process of classifying the moving average calculated by the average calculation unit 13 into any of a plurality of sections divided by the threshold group Tha. The high-priority drop probability candidate value corresponding to the section indicated by the result is output to the packet drop unit 11 as the drop probability Pa. Similarly, the second probability determining unit 14b performs threshold processing on the moving average value calculated by the average value calculating unit 13 using the threshold group Thb, and calculates a moving average corresponding to the section indicated by the result of the threshold processing. The priority discard probability candidate value is output to the packet discard unit 11 as the discard probability Pb. Similarly, the third probability determining unit 14c performs threshold processing on the moving average value calculated by the average value calculating unit 13 using the threshold group Thc, and performs a low processing corresponding to the section indicated by the result of the threshold processing. The priority discard probability candidate value is output to the packet discard unit 11 as the discard probability Pc.

  Also in this configuration example, the packet discarding unit 11 performs the same processing as in the configuration example of FIG. That is, the packet discarding unit 11 discards packets belonging to the arrival type in an amount corresponding to the discard probability of the reference type corresponding to the arrival type.

  As described above, according to the present embodiment, it is possible to cope with a congestion control technique such as WRED in which a plurality of types of packets arrive without adding a large amount of hardware resources. Also, the example of classifying packets according to the difference in priority as the type of packet has been described. For example, packets are classified according to types such as video, audio, and other information (such as control information necessary for output control at a receiving device). It can also be categorized by other types. For each packet of video, audio, and other information, information indicating the type is described in the header of the packet. In the packet control devices 1b and 1c, for example, the audio packet has a lower discard probability than the video packet. In addition, the processing may be performed such that the other information packet has a lower discard probability than the voice packet.

Modified example.
FIG. 14 is a diagram illustrating another configuration example of the packet control device according to the first to third embodiments. Each of the packet control devices 1, 1a, 1b, and 1c illustrated in FIGS. 1, 7, 12, and 13 has a memory 31 as a storage device for storing a program as software and various data, and a packet stored in the memory 31. (For example, by a computer) using the processor 32 as an information processing unit (including the above-described control unit that performs overall control such as the processing timing of the packet control device) for executing the program.

  In this case, the memory 31 includes the buffer 12 and the storage unit 15a, the moving average value storage unit, the accumulated amount storage unit, the threshold value storage unit, and the discard probability candidate value storage unit in FIG. Further, the processor 32 includes the packet discarding unit 11, the average value calculating unit 13, the probability determining unit 14 (first to third probability determining units 14a to 14c), the statistical processing unit 15, and the threshold value determining unit 16 (FIG. 1). A program for realizing the functions of the first to third threshold value determination units 16a to 16c) and the determination unit 17 and the function of the control unit is executed. This program may be stored in a memory inside the processor 32 instead of the memory 31. A part of each of these units 11 to 17 may be realized by a memory 31 shown in FIG. 14 and a processor 32 executing a program. Further, the above-described software program can be distributed by being stored in a non-temporary recording medium and distributed, or stored in a server device and distributed via the Internet.

1, 1a, 1b, 1c Packet control device, 11 packet discarding unit, 12 buffer (packet accommodation unit), 13 average value calculating unit, 14 probability determining unit, 14a first probability determining unit, 14b second probability determining unit , 14c a third probability determining unit, 15 statistical processing unit, 15a storage unit, 16 threshold determining unit, 16a first threshold determining unit, 16b second threshold determining unit, 16c third threshold determining unit, 17 determining unit , 24 probability determination unit, 24t table, 31 memory, 32 processor.

Claims (6)

A packet discard unit that discards an amount of packets according to the drop probability from the arrived packet;
A buffer for temporarily storing and outputting packets that have not been discarded by the packet discarding unit among the arrived packets;
An average value calculation unit that sequentially calculates a moving average value of the accumulation amount of the packets accumulated in the buffer,
Statistical processing for generating a frequency distribution for a calculation period including a time point of calculating a past moving average value having the same value as a current moving average value among a plurality of moving average values sequentially calculated by the average value calculating unit Department and
According to the frequency distribution generated by the statistical processing unit, a threshold determination unit that determines a plurality of thresholds for the moving average value,
Performing threshold processing for classifying the moving average calculated by the average calculator in any of a plurality of sections divided by the plurality of thresholds determined by the threshold determiner; And a probability determining unit that determines the discard probability according to the result.   The packet control device according to claim 1, wherein the threshold value determination unit determines the plurality of threshold values such that the higher the frequency of the moving average value indicated by the frequency distribution, the narrower the section. . A determining unit that determines an arrival type that is a type of the arrived packet;
The probability determination unit determines the drop probability for each reference type that is a predetermined packet type,
The packet discard section, the packets belonging to arrive type, the amount corresponding to the discard probability for the reference type corresponding to the arrival type, packet control according to claim 1 or 2, characterized in that discarding apparatus. A determining unit that determines an arrival type that is a type of the arrived packet;
The threshold value determination unit determines the plurality of threshold values for each reference type that is a predetermined packet type,
The probability determination unit, for each of the reference type, determines the discard probability by executing the threshold processing,
The packet discard section, the packets belonging to arrive type, the amount corresponding to the discard probability for the reference type corresponding to the arrival type, packet control according to claim 1 or 2, characterized in that discarding apparatus. The probability determining unit determines a plurality of discard probability candidate values corresponding to the plurality of sections,
Corresponding to the threshold processing results show sections of the plurality of sections, the discard probability candidate value of the plurality of drop probability candidate value from claim 1, characterized in that said discard probability 4 The packet control device according to any one of the above. The probability determination unit has a table in which the plurality of sections and the plurality of discard probability candidate values are associated, each time the plurality of thresholds is determined by the threshold value determination unit, updates the table,
The packet control device according to claim 5 , wherein with reference to the table, the discard probability candidate value corresponding to the section indicated by the result of the threshold processing is extracted as the discard probability.

Images