KR101698601B1 - Bandwidth management apparatus using differential packet drop between flows and method of the same - Google Patents

Abstract

The present invention relates to an apparatus and method for managing a bandwidth by applying differentiated packet dropping between flows and dividing a heavy flow into a non-response flow and a response flow, and applying different packet drop rates to each of the non- It improves the bandwidth and link delay which is the user 's perceived quality of the network by preventing the degradation of the bandwidth service speed of the link by controlling the congestion of the link at the same time while uniformly adjusting the uneven network bandwidth among the users in the network in real time.

Description

TECHNICAL FIELD [0001] The present invention relates to a bandwidth management apparatus using differential packet dropping between flows,

The present invention relates to a bandwidth management apparatus, and more particularly, to a bandwidth management apparatus and method for managing bandwidth congestion while maintaining a fair bandwidth by applying differentiated packet drop rates between traffic flows in a high speed link .

In a network router or a switch, a packet is temporarily stored in a buffer queue, and when a congestion occurs in a link while a service is being performed, a method of discarding (deleting) a packet controls traffic, .

In the present Internet link, a drop-tail method using a first in first out (FIFO) queue is almost always used.

The drop tail method discards all incoming packets when a queue overflow occurs. This causes a lock-out and global synchronization phenomenon, which causes instability of the network due to a sudden jolt of traffic volume. .

Recently, random early detection (Random Early Detection or Random Early Discard) technique has appeared to solve such a problem.

The random early detection scheme can control the queue overflow by discarding randomly selected packets before the queue overflows.

According to the random early detection method, when the average queue size (AQS) is smaller than the minimum reference value, no packets are stored in the queue without discarding. If the average queue size is between the minimum reference value and the maximum reference value, Randomly selected packets are dropped with a specific drop probability value according to size, and when the average queue size is larger than the maximum reference value, all packets are discarded.

However, such a random early detection technique has a problem in that all packets are processed identically without discrimination of traffic.

The present invention provides a new bandwidth management method that can maintain fair bandwidth and link quality while using a simple FIFO queue.

A bandwidth management apparatus using differentiated packet dropping between flows according to an embodiment of the present invention generates a flow for incoming packets and determines whether the flow is heavy flow or not and outputs a heavy flow A queue manager for managing a queue according to a predefined queue management algorithm and generating and outputting a queue packet drop rate when a predetermined condition occurs; And a bandwidth manager for discarding the packets by applying different drop rates to the heavy flows using the packet information.

In the bandwidth management apparatus of the present invention, the bandwidth management unit calculates a process bandwidth for incoming flows, filters incoming packets by the process bandwidth, and transmits the processed bandwidth to the link queue management unit. If the incoming flow is a heavy flow, (Unresponsive flow) or a response flow (response flow), and applies different packet drop rates to the respective packets. In this case, the non-response flow is a flow in which the average packet drop rate of the heavy flow exceeds a preset reference value, and the response flow is a flow in which the average packet drop rate of the heavy flow is equal to or less than a predetermined reference value.

In the bandwidth management apparatus of the present invention, the bandwidth manager discards a packet by applying a first packet drop rate (F) to the non-response flow, and if the packet is not dropped according to the first packet drop rate, Discard the packet. At this time, the first packet drop rate F

(여기에서, B는 해당 헤비 플로우가 가져야 하는 공정 대역폭의 크기, q₀는 상기 큐 패킷 드랍율의 평균값, Ri는 비응답 플로우의 전송 속도)에 따라 계산될 수 있으며, 상기 공정 대역폭은

(Where B is the size of the process bandwidth that the heavy flow should have, q ₀ is the average value of the queue packet drop rate, and Ri is the transfer rate of the non-response flow)

(여기에서, D_T는 비응답 플로우가 아닌 모든 플로우가 겪은 실제 패킷 드랍의 총합, D_q는 비응답 플로우가 아닌 플로우가 도착했을 때 전달받은 상기 큐 패킷 드랍율의 총합, B(t-T)는 T초 이전의 공정 대역폭)에 따라 계산될 수 있다.

(Where D _T is the sum of the actual packet drops experienced by all flows that are not non-responsive flows, D _q is the sum of the queue packet drop rates delivered when the flow arrives, rather than the non-response flow, B ≪ / RTI > second).

In the bandwidth management apparatus of the present invention, the bandwidth management unit discards packets by applying a second packet drop rate (P) to the response flow, and the second packet drop rate (P)

(여기에서, R_j는 응답 플로우가 보내는 전송 속도, P_{j ,O}는 응답 플로우가 겪은 평균 패킷 드랍율, R_q는 링크에 도착하는 전체 패킷 도착 속도이며, F_i는 비응답 플로우의 드랍율)에 따라 계산될 수 있다.

(Where R _j is the transmission rate of the response flow, P _{j , O} is the average packet drop rate experienced by the response flow, R _q is the total packet arrival rate arriving at the link, and F _i is the drop rate of the non- Can be calculated accordingly.

A method for managing a bandwidth using differentiated packet drop between flows according to an embodiment of the present invention includes a first step of determining whether an incoming packet is a heavy flow, a step of, when it is determined that the heavy flow is a heavy flow, a second step of determining whether the response flow is an unresponsive flow or a responsive flow, and a third step of discarding packets by applying different packet drop rates to the non-response flow and the response flow.

In the bandwidth management method of the present invention, the first step is a step of generating a flow for incoming packets, calculating a process bandwidth for the flows, filtering the incoming packets by the process bandwidth, and transmitting the processed bandwidth to a queue .

In the bandwidth management method of the present invention, the second step determines the non-response flow if the average packet drop rate of the heavy flow exceeds a preset reference value, and otherwise determines the response flow.

The present invention improves the bandwidth and link delay of the user's network perception quality by preventing the quality degradation of the bandwidth service speed of the link by simultaneously controlling the congestion of the link while uniformly adjusting the uneven network bandwidth among users in the communication network in real time. I will.

1 is a block diagram showing the configuration of a bandwidth management apparatus according to the present invention;
BACKGROUND OF THE INVENTION 1. Field of the Invention [0001] The present invention relates to a bandwidth management method and a bandwidth management method using differentiated packet dropping between flows according to the present invention.

Hereinafter, preferred embodiments of the present invention will be described in detail with reference to the accompanying drawings.

1 is a block diagram showing a configuration of a bandwidth management apparatus according to the present invention.

The bandwidth management apparatus includes a heavy flow detection unit 10, a bandwidth management unit 20, and a link queue management unit 30.

The heavy flow detection unit 10 generates a flow for the incoming packets, determines a flow having a bandwidth equal to or larger than a predetermined bandwidth as a heavy flow, and transmits information about the heavy flow to the bandwidth management unit 20. As a method of detecting the heavy flow, for example, a process bandwidth for each flow is calculated to determine a flow having a bandwidth larger than the process bandwidth or a specific reference bandwidth, and then determine a flow having a bandwidth larger than the reference bandwidth as a heavy flow .

The bandwidth management unit 20 filters the dropped packets according to the process bandwidth and delivers the dropped packets to the link queue management unit 30. The bandwidth management unit 20 notifies the link queue management unit 30 of the queue packet drop rate calculated by the link queue management unit 30, Information is provided. The bandwidth management unit 20 uses the heavy flow information provided from the heavy flow detection unit 10, the queue packet drop rate q provided from the link queue management unit 30, and the packet information calculated using the incoming packet And discards the packets by applying a different drop rate to the heavy flow. That is, the bandwidth management unit 20 calculates the process bandwidth for each flow without unconditionally sending the packets to the link queue management unit 30, and then dropping the packets, which flow more than the process bandwidth, in each flow in advance, 30). At this time, the process bandwidth provides a fair bandwidth to each flow using the entire packets and the total link bandwidth, and a detailed description thereof will be described later. If the flow of the incoming packet is determined to be a heavy flow, the bandwidth management unit 20 determines whether the heavy flow is an unresponsive flow causing a lot of congestion or a responsive flow causing less congestion And discards the packet by applying different packet drop rates (F, P) for each. When calculating the packet drop rates F and P, information on the queue packet drop rate q provided from the link queue manager 30 is used.

The link queue management unit 30 manages queues according to a predefined queue management algorithm and generates a queue packet drop rate q when a queue overflow occurs or a packet is accumulated in a buffer queue over a certain level And transmits it to the bandwidth management unit 20. At this time, the link queue manager 30 may preset the specific drop rate value at the queue packet drop rate, and may transmit the predetermined drop rate to the bandwidth manager 20 when an overflow occurs or a packet is accumulated in the buffer queue at a predetermined level or higher. In addition, the queue packet drop rate q may be calculated by applying various algorithms according to the queue management method.

Although the bandwidth management unit 20 and the link queue management unit 30 are shown separately in FIG. 1, an algorithm for managing the link queue may be operated within the bandwidth management unit 20. [

In the present invention, the bandwidth management unit (20) drops the packets flowing into the queue in advance using the process bandwidth, thereby preventing an overflow in the queue in advance. However, when an overflow occurs due to a situation where the amount of queue is greater than the amount of processing in the queue due to, for example, the delay of the queue, the link queue management unit 30 generates a queue packet drop rate The bandwidth management unit 20 notifies the bandwidth management unit 20 of the drop of the packets flowing into the link by reflecting the queue bandwidth drop rate as well as the process bandwidth.

2 is a flowchart illustrating a bandwidth management method using differentiated packet dropping between flows according to the present invention.

When a packet is generated on the link, the heavy flow detection unit 110 generates a flow for the corresponding packet based on the received packets, and determines whether the corresponding flow corresponds to a heavy flow using a predefined heavy flow detection algorithm If it is determined to be a heavy flow, the bandwidth management unit 20 transmits the information to the bandwidth management unit 20 (step 210).

The present invention generates a flow using information of an incoming packet when packets are flowed to control traffic by flow, and then determines whether the flow is heavy or not. At this time, the flow includes five pieces of information (a source address, a destination address, a source port, a destination port, And protocol type}, the heavy flow detection unit 110 can generate a flow for a packet using this information.

As a method of determining the heavy flow, the heavy flow sensing unit 110, for example, calculates a process bandwidth (B) to be fairly allocated to each flow, and determines a flow flowing at a speed greater than the process bandwidth as a heavy flow .

At this time, the process bandwidth (B) can be obtained by using the following principle.

For example, when the flows a, b, and c are flowing into the link at 6 Mbps, 8 Mbps, and 1 Mbps, respectively, and the total bandwidth of the link is 9 Mbps, the entire bandwidth is divided into three flows (a, b, Only 3Mbps is allowed for each flow to have. However, since the flow c only sends 1 Mbps and 2 Mbps remains, the flows a and b are divided by 1 Mbps. Thus, the final process bandwidths for flows a, b, and c are 4 Mbps, 4 Mbps, and 1 Mbps, respectively.

When the process bandwidth is obtained, the heavy flow detection unit 110 determines the flows a and b for sending packets larger than the process bandwidth as a heavy flow, and transfers the information to the bandwidth management unit 20.

If the flow of the incoming packet is determined as a heavy flow and the heavy flow detection unit 110 transmits the heavy flow information to the bandwidth management unit 20, the bandwidth management unit 20 determines whether the heavy flow is an unresponsive flow Or whether it is a responsive flow (step 220).

In this embodiment, the non-response flow indicates a case where the average packet drop rate of the flow is larger than a predetermined reference value (for example, h = 0.2), and the flow with the average packet drop rate of 0.2 or less is defined as a responsive flow.

Therefore, when a packet of a specific flow is first flowed, the flow is regarded as a response flow, but when the amount of dropped packets increases due to congestion due to continuous flow of packets of the flow, the flow is changed to a non-response flow.

If the flow is determined to be a non-response flow, that is, if the flow is a heavy flow and the amount of incoming packets is excessive, and the average packet drop rate is greater than a certain level (h), the bandwidth management section 20 The drop rate of the probability F is applied to drop the packet (step 230).

At this time, when the non-response flow is referred to as i-flow, the drop rate F is calculated using the following equation.

And the above equation, B is the size (bps) of the process, the bandwidth which should have a corresponding heavy flow, q ₀ recently (no unit), about a second mean value of (queue packet Drop rate of the output link queue management unit (30)) q, Ri is the transmission rate (bps) of the i-flow.

The size of the process bandwidth (B) for the flow of packets flowing in real time can be calculated by the following equation.

Where D _T is the sum of the actual packet drops (bps) experienced by all non-responding flows during the last one second, and D _q denotes the sum of q (queue packet drop rate) values received when a flow arrives, not a non-response flow for about one second in the past, and B (tT) denotes a B value before T seconds. The T value is preferably set to a value between about 0.02 and 0.5. Bars above expression means a whole B value of the constant period T (unit sec) only once, and to the update to the second, a method for updating T seconds previous value (B (tT)) and D _T, D _q of B And updates it with the result calculated in the above equation.

However, even when a packet is dropped by applying a specific drop rate, since the actual packet drop is randomly performed according to the probability, the packet may not drop normally.

Accordingly, if the drop rate F is applied to the packets of the non-response flow, but the packet drop does not normally occur (step 240), the bandwidth management unit 20 updates the queue packet received from the link queue management unit 30 The packet of the flow is dropped according to the drop rate q (step 250).

If it is determined in step 220 that the flow is a response flow, that is, if the flow is a heavy flow, but the flow rate is not an excessively large amount of packets, but the average packet drop rate is less than a certain level (h) ) Drops the packet by applying the drop rate of probability P to the flow (step 260).

At this time, when the response flow is referred to as a j-flow, the drop rate P is calculated according to the following equation.

Where R _j is the transmission rate (in bps) sent by the j flow, P _{j , O} is the average packet drop rate (no unit) experienced by the j flow for the last one second, R _q is the total packet arrival rate (bps), and F _i denotes the drop rate (F) of the i-flow.

If the drop rate q and P are applied at step 250 or 260 and the packet is not dropped normally (step 270), the bandwidth management unit 20 sequentially processes the incoming packets To the link queue management unit 30 so that normal packet service is performed.

If it is determined in step 210 that the flow of the incoming packet is not a heavy flow, the heavy flow detection unit 110 does not provide information on the heavy flow to the bandwidth management unit 20.

If the heavy flow information is not transmitted from the heavy flow detection unit 110, the bandwidth management unit 20 does not apply the differential rate for each flow according to the steps 220 to 270 for the flow, To the link queue management unit 30 so that normal packet service is performed.

It will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the appended claims. As shown in Fig.

For example, in the present embodiment, since the heavy flow sensing unit 10 is provided with information on the heavy flow to the bandwidth management unit 20, it is possible to use the known heavy flow sensing algorithm other than the above- .

10: Heavy flow detection unit 20: Bandwidth management unit
30: Link queue manager

Claims (15)

A heavy flow sensing unit for generating a flow for incoming packets, calculating a process bandwidth for the generated flow, determining a flow flowing at a speed greater than the process bandwidth as a heavy flow, and outputting heavy flow information;
Managing a queue according to a predefined queue management algorithm, generating a queue packet drop rate when a predetermined condition occurs, and outputting the queue packet drop rate; And
And a bandwidth manager for discarding packets by applying a different drop rate to the heavy flows using the heavy flow information, the queue packet drop rate, and packet information for incoming packets,
The bandwidth management unit,
When the heavy flow information is received from the heavy flow detection unit, the non-response flow is defined as a non-response flow when the packet drop rate of the flow exceeds a preset reference value. Otherwise, the response flow is defined as a different packet drop rate Wherein a higher packet drop rate is applied to the non-response flow than the response flow. delete delete delete The apparatus of claim 1, wherein the bandwidth manager
Wherein the first packet drop rate (F) is applied to the non-response flow to discard the packet, and if the packet is not dropped according to the first packet drop rate, the packet is discarded according to the queue packet drop rate A bandwidth management device using differentiated packet dropping. 6. The method of claim 5, wherein the first packet drop rate (F)

(Where B is the size of the process bandwidth that the heavy flow should have, q ₀ is the average value of the queue packet drop rate, and Ri is the transmission rate of the non-response flow)
Wherein the bandwidth is calculated according to the difference between the flows. 7. The method of claim 6,

(Where D _T is the sum of the actual packet drops experienced by all flows that are not non-responsive flows, D _q is the sum of the queue packet drop rates delivered when the flow arrives, rather than the non-response flow, B Second < / RTI > process bandwidth)
Wherein the bandwidth is calculated according to the difference between the flows. 7. The apparatus of claim 6, wherein the bandwidth manager
The second packet drop rate (P) is applied to the response flow to discard the packet, and the second packet drop rate (P)

(Wherein, R _j is a transmission rate to send the response flow, P _{j, O} is the average packet Drop rate responds flow experienced, R _q is the total packet arrival rate to the link destination, F _i is a flow Drop rate of non-response)
Wherein the bandwidth is calculated according to the difference between the flows. The method comprising: generating a flow for incoming packets, calculating a process bandwidth for the generated flow, and determining a flow that flows at a rate greater than the process bandwidth as a heavy flow;
A second step of determining a non-response flow when the packet drop rate exceeds a predetermined reference value according to a packet drop rate of the heavy flow, and determining a response flow if the packet drop rate is not heavy; And
And a third step of applying a different packet drop rate to the non-response flow and the response flow, and discarding the packet by applying a higher packet drop rate to the non-response flow than the response flow. Method of using bandwidth management. delete delete 10. The method of claim 9, wherein the third step comprises:
And discards the packet according to the queue packet drop rate generated by the pre-defined queue management algorithm if the packet is not dropped according to the first packet drop rate, applying the first packet drop rate (F) to the non-response flow, Wherein the bandwidth is differentiated between the flows. 13. The method of claim 12, wherein the first packet drop rate is

(Where B is the size of the process bandwidth that the heavy flow should have, q ₀ is the average value of the queue packet drop rate, and Ri is the transmission rate of the non-response flow)
Wherein the bandwidth is calculated according to the difference between the flows. 14. The method of claim 13,

(Where D _T is the sum of the actual packet drops experienced by all flows that are not non-responsive flows, D _q is the sum of the queue packet drop rates delivered when the flow arrives, rather than the non-response flow, B Second < / RTI > process bandwidth)
Wherein the bandwidth is calculated according to the difference between the flows. 14. The method of claim 13, wherein the third step comprises:
Applying a second packet drop rate (P) to the response flow to discard the packet, and the second packet drop rate

(Wherein, R _j is a transmission rate to send the response flow, P _{j, O} is the average packet Drop rate responds flow experienced, R _q is the total packet arrival rate to the link destination, F _i is a flow Drop rate of non-response)
Wherein the bandwidth is calculated according to the difference between the flows.

Images