JP2000183880A - Packet flow monitoring device - Google Patents

Abstract

(57) [Summary] The present invention relates to a packet flow monitoring device, and an object thereof is to provide a packet flow monitoring device capable of reducing the amount of hardware. SOLUTION: In a variable length packet flow monitoring device using a token bucket, means 23 for storing the time and the token bucket counter value at the time of previous packet arrival, the stored token bucket parameter at the time of packet arrival, and A means 21 for calculating the token bucket counter value at that time from the arrival time, the current time, and the added rate; and a comparing means 21 for comparing the calculated value with the packet length. Is configured to be performed.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

The present invention relates to a packet flow monitoring device. In recent years, in communication using variable-length packets such as the Internet, end-to-
The provision of a quality assurance type service that guarantees end delay or a band that can always be occupied is realized by IETF (Internet E
Negering Task Force).

[0002] A user is given information such as the flow rate of outgoing packets for each flow in advance, and the network side reserves resources in the network for the user based on the information. However, if the user sends a packet that does not follow the information, the network congests resources more than expected, and the effect of the packet may result in the quality of other users. It is necessary to monitor the flow rate of output packets and discard the packets if the user sends many packets, or reduce the quality of the excess packets and discard the packets before the network becomes congested. . IP (Internet Protc)
ol) As a packet flow monitoring function, a normal token bucket algorithm is used.

[0003]

2. Description of the Related Art FIG. 10 is an explanatory diagram of a conventional flow rate monitoring function. In the conventional flow monitoring function using a token bucket for a variable-length packet 2, a token bucket counter 1 is used to count tokens falling at regular intervals in accordance with a guaranteed bandwidth flow rate, and set the counter value to a maximum value. Add up to When the user packet 2 arrives, the token bucket counter value is compared with the packet length of the user.

If the counter value is larger, the packet is determined to be conforming, and the packet is transmitted after subtracting the token bucket counter value by the packet length. If the counter value is small, the packet is determined to be non-conforming and the arriving packet is discarded. Alternatively, the quality condition of the arriving packet on the network is lowered and the packet is transmitted.

[0005]

In the above-mentioned prior art, a counter must be prepared for each flow from the user. If the number of flows to be monitored at the entrance of the network is large, a large number of counters are required. There is a problem that it becomes necessary and the amount of hardware increases.

The present invention has been made in view of such a problem, and has as its object to provide a packet flow monitoring device capable of reducing the amount of hardware.

[0007]

(1) FIG. 1 is a principle block diagram of the first invention. In the figure, reference numeral 2 denotes an input variable-length packet, and reference numeral 3 denotes a determination unit that receives the variable-length packet, determines a flow, and determines a packet size.
Reference numeral 4 denotes a packet operation unit that receives a packet output from the determination unit 3 and determines whether or not to transmit the packet in accordance with a determination result from the operation control unit 20 described later.

Reference numeral 20 denotes an arithmetic control unit which characterizes the present invention. In the arithmetic and control unit 20, reference numeral 22 denotes a clock for outputting time information, and reference numeral 23 denotes a memory for storing token bucket parameters for each flow. 21 is a discriminator 3
, A packet size and a flow identification signal output from the clock 22, time information from the clock 22,
3 is a discrimination function unit that receives a parameter corresponding to the flow from 3 and calculates a token bucket counter value and compares it with the packet length of the packet 2. The discrimination function unit 21
The determination result is notified to the packet operation unit 4.

According to the configuration of the present invention, the conformity / non-conformity of the arriving packet can be determined by comparing the token bucket counter value calculated when the packet arrives with the packet length. According to this, it is not necessary to provide a counter for packet length comparison for each flow, so that the amount of hardware can be reduced.

(2) According to a second aspect of the present invention, in a variable length packet flow monitoring device using a token bucket, the time when the token bucket counter value returns to the initial bucket size when the previous packet arrives is calculated. Means for calculating the token bucket counter value at that time from the time stored at the time of packet arrival, the current time, and the addition rate; and comparing means for comparing the calculated value with the packet length. In addition, it is characterized in that the conformity / non-conformity determination of the arriving packet is performed.

According to the configuration of the present invention, the number of parameters can be reduced. (3) A third invention relates to a variable length packet flow monitoring device using a token bucket, a means for storing the time and the token bucket counter value at the time of previous packet arrival, and a token bucket counter for every fixed period. Means for recalculating and re-storing the value, and upon packet arrival, calculating the token bucket counter value at that time from the stored token bucket parameter and the arrival time or the recalculated time, the current time, and the addition rate. Means and a comparing means for comparing the calculated value with the packet length, and is adapted to judge the conformity / non-conformity of the arriving packet.

According to the configuration of the present invention, the number of bits of the memory and the clock can be reduced. (4) In the fourth invention, the addition rate of the third invention is 1
It is characterized in that each parameter is set such that

According to the configuration of the present invention, by storing 1 / r instead of r as the addition rate in the memory, the division becomes unnecessary and the circuit can be simplified.

[0014]

Embodiments of the present invention will be described below in detail with reference to the drawings. FIG. 2 is a block diagram showing the first embodiment of the present invention. 1 are denoted by the same reference numerals. The configuration shown in the figure shows the detailed configuration of the arithmetic control unit 20 in FIG. In the figure,
A subtractor 31 receives the time information T from the clock 22 and the time information pT from the memory 23, and 32 receives the output (T-pT) of the subtractor 31 and the addition rate signal r from the memory 23, and A multiplier for performing a × (T−pT) operation.

Reference numeral 33 denotes an output r × (T−p) of the multiplier 32.
T) and the information pTBC from the memory 23
+ R × (T−pT) operation, an adder 34 receives the output of the adder 33 and the bucket size b from the memory 23, and outputs the smaller one as the TBC. A subtractor 35 receives the output of the value selection unit 34 and the packet size and calculates the difference between them. A comparison unit 35 compares the packet size L with the value TBC based on the calculation result to determine conformity / nonconformity. In the memory 23, parameters b, r, pT, and pTBC are stored for each flow. When an operation is performed, the flow is selected and corresponding data is output. The operation of the circuit thus configured will be described as follows.

A quality QOS guarantee service for each flow is started using a fixed contract base with a user or a reservation protocol such as RSVP. When the service is started, the flow-specific parameters of the flow's bucket size b and rate information r, the service start time are set to the previous arrival time pT, and the bucket size b is set in the memory 23 as a change parameter of the initial value of the token bucket counter value pTBC. I do.

FIG. 3 is an explanatory diagram of the operation of the first embodiment. The vertical axis is the token amount, and the horizontal axis is the time t. The initial value of the token amount is b. This is the bucket size initial value. Each time a packet arrives, the discrimination function unit 21 identifies the flow of the packet, and sets parameters b, r, pT, pTBC.
From the memory 23. Then, a token bucket counter value TBC at the present time is obtained by calculation from the information and the time information T of the clock 22.

First, the subtractor 31 calculates T-pT, the multiplier 32 calculates r × (T-pT), and the adder 33 calculates pTBC + r × (T-pT). As a result, the minimum value selecting unit 34 calculates the value p obtained by the above-described calculation.
TBC + r × (T−pT) is compared with the bucket and the size b, and the smaller value is selected as the TBC. That is, TBC = min (b, pTBC + r × (T−p
T)).

When this calculation is completed, the comparing unit 35 compares the value TBC with the size L of the arriving packet.
If L> TBC, the comparing unit 35 discards the arriving packet as non-conforming, or transfers the packet with reduced priority or quality. At this time, pT and pTBC in the memory 23 may be left as they are, or the time information T and TBC may be stored.

If L ≦ TBC, the arriving packet is forwarded as conforming. PT = T, pTB of the memory at that time
As C = TBC-L, the data is written to the memory 23 in response to a write instruction from the comparison unit 35.

As described above, according to this embodiment,
The token bucket determination algorithm can be realized with one arithmetic unit and one memory. According to this embodiment, the conformity / non-conformity of the arriving packet can be determined by comparing the token bucket counter value calculated when the packet arrives with the packet length. Further, according to this, it is not necessary to provide a counter for comparing with the packet length for each flow, so that the amount of hardware can be reduced.

The initial value of pTBC is 0, and the TBC at the time of packet arrival is TBC = max (0, pTBC-r ×
(T−pT)), the arriving packet is determined to be non-conforming if TBC + L> b, and the arriving packet is determined to be conforming if TBC + L ≦ b. it can.

FIG. 4 is a block diagram showing a second embodiment of the present invention. The same components as those in FIG. 2 are denoted by the same reference numerals. In this embodiment, the memory 23 stores the bucket size b, the rate information r, and the time n
T. The QOS guarantee service for each flow is started using a contract protocol with the user or a reservation protocol such as RSVP. When the service is started, the flow-specific parameters of the bucket size b and the rate information r of the flow and the service start time are stored in the memory 23 as the initial value of the counter initial value time nT.

Each time a packet arrives, the discrimination function unit 21 identifies the flow of the packet, and stores the corresponding b,
Receive r and nT. These information and the current time information T of the clock
As a result, the packet arrival time is obtained by calculation as the current token bucket counter value TBC. FIG. 5 is an operation explanatory diagram of the second embodiment.

When nT> T, TBC = br × r
According to (nT−T), when nT ≦ T, the calculation is performed as TBC = b. In FIG. 4, a subtractor 31 receives information T from a clock 22 and time information nT from a memory 23 to obtain nT-T. Next, the multiplier 32 receives the rate information from the memory 23 and calculates r × (nT−T) by calculation. Next, the subtractor 37 receives the b information from the memory,
Calculate −r × (nT−T).

The output of the subtracter 37 and the b information from the memory 23 are input to the selector 38. Selector 38
Is input T and nT, and nT>
In the case of T, the output of the subtracter 37 is selected from the selection unit 38 and output as TBC, and in the case of nT ≦ T, b is selected and output as TBC.

The ratio unit 35 includes a packet size L, a TBC
Compare the size with. Then, according to the comparison result, a conformity / non-conformity signal indicating whether or not the packet conforms is output. That is, if the TBC is larger than the packet size L, the packet is transferred, and if the TBC is smaller than the packet size L, the packet is determined to be unsuitable and the packet is discarded or the priority is lowered and transferred. At that time, nT of the memory 23 is left as it is.

The nT value in the case of a match is obtained as follows. The divider 41 receives the rate information r and the packet size information L and calculates L / r. Next, the adder 42 outputs the output of the divider 41 and the output max of the maximum value selector 40.
In response to (nT, T), both values are added. That is, L
If ≦ TBC, the arriving packet is transferred as conforming, and the memory 23 at that time is stored in the memory 23 as nT = max (nT, T).
+ (L / r) or nT = T + (b− (TBC−L)) / r. The latter equation is based on FIG.

According to this embodiment, the number of parameters can be reduced. That is, the parameter pTBC is reduced by one compared to the case of FIG. When nT> T, the TBC at the time of packet arrival is TB
C = r × (nT−T), TBC = 0 when nT ≦ T
If TBC + L> b, arriving packets are made non-conforming, and if TBC + L ≦ b, arriving packets are made conforming, it is also possible to realize the leaky bucket algorithm.

FIG. 6 is a block diagram showing a third embodiment of the present invention. The same components as those in FIG. 2 are denoted by the same reference numerals. In the figure, reference numeral 21 denotes a discrimination function unit having the same configuration as that of the first embodiment of FIG. 40 is a recalculation function unit, which includes a subtractor 45, a multiplier 46, an adder 47,
It comprises a minimum value selector 48 and a flow identification generator 49.

In the case of this embodiment, the parameters to be stored are the same as those of the first embodiment.
It has a recalculation function for recalculating the values of T and pTBC. The setting at the time of service start and the setting of packet arrival are the same as in the first embodiment. FIG. 7 is an operation explanatory diagram of the third embodiment.

The recalculation function unit 40 receives b, r, pT, and pTBC from the memory 23 at a constant cycle for each flow. Then, the current token bucket counter value TBC is obtained by the following calculation.

The subtractor 45 generates time information T from the clock 22.
And the information pT from the memory 23, and calculates T-pT. The next multiplier 46 receives the output of the subtractor 45 and the rate information r and calculates r × (T−pT). The next adder 47 receives the output of the multiplier 46 and pTBC and receives pTB
Calculate C + r × (T−pT). Minimum value selector 48
Receives the initial value b and the output of the calculator 47 and selects the smaller value as the token bucket counter value TBC. That is, TBC = min (b, pTBC + r × (T−pT)) This equation is a recalculation equation. And pT = T, TBC =
It is stored in the memory 23 as pTBC in preference to the discrimination function unit 21. Here, when the TBC obtained by the recalculation exceeds b, b is set, and when the TBC does not exceed b, pTB is set.
C.

Thus, T and p at the time of packet arrival
Since the difference from T is limited to the recalculation function of the recalculation function or less, the number of bits of the memory for storing pT and the clock 22 can be reduced.

Also, as described in the first embodiment, the recalculation function is performed when TBC = max (0, pTBC-
If it is calculated as r × (T−pT)) and stored as TBC = pTBC, it can also be realized by a leaky bucket algorithm.

FIG. 8 is a block diagram showing a fourth embodiment of the present invention. The same components as those in FIG. 2 are denoted by the same reference numerals. The QoS guarantee service for each flow is started using a fixed contract base with the user or a reservation protocol such as RSVP. At the start of service, the relative value b '= b / r of the bucket size of the flow, the flow-specific parameter of the rate information r, the service start time is defined as the previous arrival time pT, and the relative value of the bucket size b' is defined as the token bucket counter value. Is set in the memory 23 as a change parameter as an initial value of the relative value pTBC ′ = pTBC / r. Here, b and pTBC are the same as the parameters described in FIG.

FIG. 9 is a diagram for explaining the operation of the fourth embodiment. Each time a packet arrives, the discrimination function unit 21 identifies the flow of the packet and sets the corresponding parameters b ′, r, p
T and pTBC ′ are received from the memory 23. Based on this information and the current time T of the clock 22, the relative value TBC 'of the token bucket counter at the present time is calculated by TBC' = min (b ', pTBC + (T-pT)). The process of calculating this equation will be described below.

First, the subtractor 31 receives the time information T from the clock 22 and the time information pT from the memory 23, and
Calculate T. Next, receiving the outputs of the adder 33 and the subtractor 31 and pTBC from the memory 23, pTBC + (T−p
T) is calculated. The output of the adder 33 and the memory 23
Is compared with b ′ normalized by r from.

The minimum value selector 34 outputs the output p of the adder 33
The smaller of TBC + (T−pT) and b ′ is output as TBC ′. That is, TBC ′ = min (b ′, pTBC + (T−pT)), which is the above equation, holds.

On the other hand, the multiplication unit 50 receives the packet size L and 1 / r from the memory 23, normalizes L with r, and obtains L '= L / r. The comparing unit 35 compares L / r with the TBC '.

In the case of L '>TBC', the arriving packet is determined to be non-conforming and is discarded or transferred with reduced priority or quality. At this time, pT and pTBC of the memory 23 may be left as they are, or T and TBC 'may be stored.

If L'≤TBC ', the arriving packet is forwarded as conforming. PT of memory at this time = T, p
TBC 'is stored as pTBC' = TBC '-(L / r). That is, the subtractor 36 receives L / r and TBC ′, and calculates the difference TBC′−L / r into the pTB of the memory 23.
Write to C.

According to this embodiment, storing the parameter 1 / r instead of the rate information (addition rate) r eliminates the need for division at the time of calculating pTBC ', thereby simplifying the circuit. Can be.

The leaky bucket algorithm can be realized similarly to the other embodiments. As described above, according to the present invention, the parameters are stored in the memory for each flow, and the flow determination is performed for each packet arrival and for each fixed period by using those parameters, whereby the counter for each flow is not used. In addition, the flow monitoring of a large number of packets can be performed.

[0045]

As described above in detail, (1) According to the first invention, in the variable length packet flow monitoring device using the token bucket, the time when the previous packet arrived and the token bucket counter Means for storing a value, at the time of packet arrival, the stored token bucket parameter, the arrival time, the current time,
It is provided with a means for calculating the token bucket counter value at that time from the addition rate, and a comparing means for comparing the calculated value with the packet length. The conformity / non-conformity of the arriving packet can be determined by comparing the token bucket counter value with the packet length. According to this, it is not necessary to provide a counter for packet length comparison for each flow, so that the amount of hardware can be reduced.

(2) According to the second invention, in the variable length packet flow monitoring device using the token bucket,
Means for calculating and storing the time when the token bucket counter value returns to the bucket size which is the initial value when the packet arrives at the previous time, and the token at the time based on the time stored at the time of packet arrival, the current time, and the addition rate. The apparatus includes a means for calculating a bucket counter value, and a comparing means for comparing the calculated value with the packet length, and makes a determination as to whether or not a received packet is suitable or not, thereby reducing the number of parameters.

(3) According to the third invention, in the flow rate monitoring device for variable length packets using the token bucket,
Means for storing the time and the token bucket counter value at the time of the previous packet arrival, means for recalculating and storing the token bucket counter value at regular intervals, and the token bucket parameter stored at the time of packet arrival. Means for calculating a token bucket counter value at that time from the arrival time, the arrival time, the current time, and the addition rate;
Comparing means for comparing the calculated value with the packet length is provided, and the conformity / nonconformity determination of the arriving packet is performed, whereby the number of bits of the memory and the clock can be reduced.

(4) According to the fourth aspect of the invention, by setting each parameter so that the addition rate becomes 1, the 1 / r is stored in the memory instead of r as the addition rate. , The division becomes unnecessary and the circuit can be simplified.

[Brief description of the drawings]

FIG. 1 is a principle block diagram of the first invention.

FIG. 2 is a block diagram illustrating a first embodiment of the present invention.

FIG. 3 is an operation explanatory diagram of the first embodiment.

FIG. 4 is a block diagram showing a second embodiment of the present invention.

FIG. 5 is an operation explanatory diagram of the second embodiment.

FIG. 6 is a block diagram showing a third embodiment of the present invention.

FIG. 7 is an operation explanatory diagram of the third embodiment.

FIG. 8 is a block diagram showing a fourth embodiment of the present invention.

FIG. 9 is an operation explanatory diagram of the fourth embodiment.

FIG. 10 is an explanatory diagram of a flow rate monitoring function.

FIG. 11 is another operation explanatory view of the second embodiment.

[Explanation of symbols]

 2 Variable length packet 3 Discriminator 4 Packet operation unit 20 Operation control unit 21 Discrimination function unit 22 Clock 23 Memory

 ────────────────────────────────────────────────── ─── Continued on the front page (72) Inventor Naoto Watanabe 4-1-1, Kamiodanaka, Nakahara-ku, Kawasaki-shi, Kanagawa F-term within Fujitsu Limited (reference) 5K030 GA05 HB15 HB16 HB28 HC01 JA10 KA13 LC04 MB09 MB11

Claims (4)

[Claims] 1. A variable-length packet flow monitoring device using a token bucket, comprising: means for storing a time and a token bucket counter value at the time of previous packet arrival; A means for calculating the token bucket counter value at that time from the arrival time, the current time, and the addition rate; and a comparing means for comparing the calculated value with the packet length, and determines whether or not the arrival packet conforms. A packet flow monitoring device, characterized in that: 2. A variable length packet flow monitoring device using a token bucket, comprising: means for calculating and storing a time at which a token bucket counter value returns to an initial value bucket size when a previous packet arrives; A means for calculating the token bucket counter value at that time from the time stored at the time of packet arrival, the current time, and the addition rate; and a comparing means for comparing the calculated value with the packet length. A packet flow monitoring device for determining a match. 3. A variable length packet flow monitoring device using a token bucket, means for storing the time and the token bucket counter value at the time of previous packet arrival, and recalculating the token bucket counter value at regular intervals. And
Means for re-storing, means for calculating the token bucket counter value at the time from the stored token bucket parameters, arrival time, current time and addition rate when the packet arrives, and comparing the calculated value with the packet length A packet flow monitoring device, comprising: comparing means for determining whether a packet has arrived or not. 4. The packet flow monitoring device according to claim 1, wherein each parameter is set such that the addition rate is 1.