WO2004034731A1

WO2004034731A1 - Traffic shaping improvement

Info

Publication number: WO2004034731A1
Application number: PCT/AU2003/001334
Authority: WO
Inventors: Tiller Emil
Original assignee: Foursticks Pty Ltd
Current assignee: Foursticks Pty Ltd
Priority date: 2002-10-10
Filing date: 2003-10-10
Publication date: 2004-04-22
Anticipated expiration: 2005-04-10
Also published as: AU2002952039A0

Abstract

A method and apparatus for traffic shaping (201) in a packet switched network, including the steps of, upon receiving through a selected period of time a plurality of incoming identifiable data traffic streams (207, 208, 209), effecting traffic shaping by selecting packets from each of the incoming data streams in accordance with a selected traffic profile, then emitting these selected packets as one or more amalgamated outgoing data traffic streams (203) at a rate so as to maintain, that when a sum of the incoming data traffic streams instantaneous data rates is greater than a selected minimum data rate value, buffering of at least some of the incoming data traffic packets will be effected.

Description

TRAFFIC SHAPING IMPROVEMENT

TECHNICAL FIELD

This invention relates to digital data traffic control and particularly traffic shaping.

BACKGROUND ART

Traffic shaping works by separating traffic through a device into separate flows and then having some means of choosing from time to time which flow gets to send traffic next. There are problems with current methods which can lead to traffic shaping not occurring properly.

The problem to which this invention has been directed has been identified in a paper publication for traffic shaping technique of weighted fair queuing ("How Unfair can Weighted Fair Queuing be?", Goncalo Quadros, et al., CISUC - Centro de Informatica e Sistemas da Univeridada de Coimbra, 2000) but applies to many other traffic shaping disciplines. Indeed, it appears that it will occur in any environment which includes streams with protocols with differing adaptive congestion avoidance mechanisms or a variable output rate from the traffic shaping device.

A traffic shaper in general categorises incoming packets as belonging to one of a number of defined traffic flows based on some characteristic or combination of characteristics exhibited by that packet. Shaping is effected by choosing at any instant from which of the separate flows to send a packet into an outgoing traffic handling resource. This resource would typically be a wide are network (WAN) router. This choice is based on pre-selected rules concerning the priority and bandwidth allocations which have been accorded to each flow.

In order for the traffic shaper to have any effect, there must be more than one packet buffered in the packet shaper. If there is not, then the traffic shaper will not do any traffic shaping - it will merely take in a packet and immediately forward that packet.

Therefore, if the outgoing rate of the traffic shaper is faster than the incoming rate of packets, then no traffic shaping will occur, as packets are never buffered in the traffic shaper. Instead, traffic will be forwarded to the WAN router. If the WAN router has capacity to immediately forward the packet, no problem occurs. If the router does not have the capacity available to it on its outgoing link to immediately forward every packet but instead has a significant buffering capacity, packets will buffered at the WAN router. Packets will be removed from this buffer in the order dictated by the router, which is likely to be first in, first out. In any case, the congestion which the traffic shaper seeks to manage occurs outside of its operational area and hence the traffic is unshaped.

An object of this invention is to at least reduce the above problem or provide the public with a useful alternative.

DISCLOSURE OF THE INVENTION

In one form of this invention there is provided a method of traffic shaping in a packet switched network, said method including the steps of, upon receiving through a selected period of time a plurality of incoming identifiable data traffic streams, effecting traffic shaping by selecting packets from each of the incoming data streams in accordance with a selected desired traffic profile, then emitting these selected packets as one or more amalgamated outgoing data traffic streams at a rate so as to maintain, that when a sum of the incoming data traffic streams' instantaneous data rates is greater than a selected minimum data rate value, buffering of at least some of the incoming data traffic packets will be effected.

In preference, an output of a traffic shaping device useful for the above method is adapted to be provided to a variable data rate transmission system.

In preference, the said selected minimum data rate is not greater than a minimum data rate guaranteed to be made available by a downstream variable data rate transmission system.

In preference, in the alternative, the selected minimum data rate shall be slightly less than the guaranteed minimum data rate available by the downstream variable data rate transmission system.

In preference, only selected incoming data traffic streams shall be subject to some buffering at all such times.

In preference, such buffering shall be achieved by ensuring a selected number of packets are queued by a traffic shaping device for each of the selected streams at all such times.

In preference, such selected streams shall be those using selected communications protocols such protocols having adaptive end to end congestion avoidance mechanisms.

In preference, the selected communications protocol shall be TCP/IP.

In preference, there is provided means to receive and store a specification of a minimum bandwidth the traffic shaping device is shaping for.

In preference, no traffic shaping shall be effected when the sum of the data rates of all the streams arriving at the traffic shaper is less than the minimum data rate of the downstream variable data rate transmission system.

In preference, the method is such wherein the variable data rate transmission system is a Frame Relay system.

In the alternative there is a method of shaping traffic in a packet switched network, where the traffic includes a plurality of identifiable data traffic streams composed of packets, including the steps of establishing separate queues for the packets of each of said data streams; selecting a maximum and a minimum output rate at which packets may be emitted; selecting a maximum and a minimum number of packets to be held in any one or any combination of queues at any instant; establishing an instantaneous output rate at which packets are to be emitted; while input incoming packets continue to be received, iteratively performing the following steps a-b; a. if the number of packets in the queues is below said minimum number of packets, decreasing said instantaneous output rate; b. if the number of packets in the queues is above said maximum number of packets, increasing said instantaneous output rate. In further preference the invention can lie in a computer programmed to perform the method as set out hitherto.

In further preference the invention can lie in a program adapted to effect a method as hitherto when operatively acting within a computer In preference in the alternative the invention can be said to reside in a traffic shaping apparatus arranged to perform the method as hitherto identified.

In a further form of the invention, it may be said to reside in a traffic shaping apparatus for shaping packet switched network traffic, said traffic including a plurality of incoming identifiable data traffic streams, the apparatus including means to effect traffic shaping by selecting packets from each of the incoming data streams in accordance with a selected traffic profile, means to emit these selected packets as one or more amalgamated outgoing data traffic streams at a rate so as to maintain, that when a sum of the incoming data traffic streams instantaneous data rates is greater than a selected minimum data rate value, buffering of at least some of the incoming data traffic packets will be effected.

In preference an output of the apparatus is adapted to be provided to a variable data rate transmission system.

In preference the selected minimum data rate is not greater than a minimum data rate selected to be made available by the downstream variable data rate transmission system.

In preference the selected minimum data rate is slightly less than the minimum data rate selected to be made available by the downstream variable data rate transmission system.

In preference there are means to select which of the incoming data traffic streams shall be subject to some buffering at all such times.

In preference such buffering is achieved by ensuring a selected number of packets are queued for each of selected streams at all such times.

In preference the selected streams are those using selected communications protocols where such protocols incorporate adaptive end to end congestion avoidance.

In preference at least one of the selected communications protocol is TCP/IP.

In preference there are provided means to receive and store a specification of a minimum bandwidth the traffic shaping apparatus is shaping for.

In preference, in one form of the invention, the variable data rate transmission system is a Frame Relay system.

In a yet further form of the invention it may be said to reside in a traffic shaping apparatus for shaping traffic in a packet switched network, where the traffic includes a plurality of identifiable data traffic streams composed of packets, including separate queues for the packets of each of said data streams; means to select and store a maximum and a minimum value for an output rate at which packets may be emitted; means to select and store a maximum and a minimum value for a number of packets to be held in any one or any combination of queues at any instant; means to emit packets at an instantaneous rate; means to iteratively perform the following steps a-b while input packets continue to be received; a. if the number of packets in the queues is below said minimum number of packets, decreasing said instantaneous output rate; b. if the number of packets in the queues is above said maximum number of packets, increasing said instantaneous output rate.

The method using this invention has an advantage that it can dynamically adapt an outgoing rate of a traffic shaper to ensure that there are enough packets in the traffic shaper to do effective traffic shaping whilst not allowing the number of packets being buffered for this purpose to grow unacceptably large or introduce unbounded packet delays through the device.

An advantage of this approach is that it dynamically adapts traffic shaper performance to the incoming rate of packets to the traffic shaper or the outgoing rate of packets accepted by the WAN router whilst trying to ensure the total number of buffered packets remains constant. It ensures a sufficient backlog of packets in the shaper for the purpose of making shaping decisions.

A further advantage of this approach is that traffic shaping occurs correctly for varying overall system packet output rates.

BRIEF DESCRIPTION OF THE DRAWINGS

For a better understanding of this invention this will now be described with reference to a preferred embodiment which shall be described with assistance of drawings wherein:

Figure 1 shows a traffic shaper of the prior art using conventional methods feeding a WAN router with substantial buffering capability;

Figure 2 shows a traffic shaper operating in accordance with the preferred embodiment of the invention, with packets retained in the stream queues within the traffic shaper.

BEST MODE FOR CARRYING OUT THE INVENTION

The problem is shown in Fig 1. Traffic is coming from an internal network, through a traffic shaper 104. The input rate at 100 is the rate at which traffic is flowing into the traffic shaper. The output rate at 101 is the rate at which traffic is flowing out of the traffic shaper into a WAN router 105. The rate at which traffic flows out of the traffic shaper at 101 is equal to the input rate to the WAN router at 102. The WAN router's output rate at 103 is not fixed and may vary, above or below the rate at 101. The WAN router or the network beyond it has substantial buffering capacity. The traffic shaper 104 selects which packet shall be sent to the WAN router next. This selection is based on user settings in order to share the resource of the outgoing route according to the priorities assigned to the various traffic flows by the user. In this case, only one packet 106 is buffered in the traffic shaper. Hence, this packet is forwarded immediately, and no traffic shaping occurs.

However, WAN router 105 has a substantial buffer 107. This buffer continues to accept and hold incoming packets even when the output 103 of the router is in congestion.

The traffic shaper in Figure 2, 201 has incoming physical data channel 200 comprising three traffic streams 207, 208, and 209 entering it with packet rates of r., r₂ and r₃, giving a total incoming packet rate, R, that varies between 0 bytes per second and the maximum rate which the underlying physical medium can handle. Traffic is then buffered in the three channel queues 204, 205 and 206. Packets are selected from these queues in accordance with the defined traffic shaping profile set for the traffic shaper, to form one amalgamated outgoing traffic stream. The traffic is then sent over an outgoing data link 203 to a frame Relay transmission system 210. Prior to traffic leaving the traffic shaper via the outgoing data link 203, a rate limiter 202 is used to limit the rate at which packets leave the system. The minimum value this rate limiter may limit to can be designated 0_M,_N. This rate is set by the user to be slightly less than the guaranteed minimum output rate which is the minimum rate guaranteed to be accepted by the frame relay transmission system. The maximum value can be designated 0_MAX and is the maximum value that the frame relay transmission system will accept. The actual rate which the frame relay transmission system will accept at any moment is the actual available output rate. It varies continually depending on factors in the downstream network, but in normal operation does not fall below the guaranteed minimum output rate.

The rate limiter starts operation with a limiting rate of 0_MIN. When the incoming rate R is less than the minimum outgoing rate 0_MIN, no packets shall be buffered apart from the packet that just entered the system. In this case, the outgoing link is said to be underutilized and there is no need to do any traffic shaping. As soon as the incoming rate R is greater than the minimum outgoing rate 0_MIN, packets will become buffered in the channel queues 204, 205 and 206 since the rate limiter shall not allow all packets entering the system to leave immediately. The system will therefore start to shape traffic according to the particular traffic shaping regime implemented, selecting packets from the channel queues for transmission on the outgoing link according to the link sharing regime. As time goes on, the backlog of packets in the buffer will increase. We do not wish to allow this increase to be unbounded, since ideally the traffic shaper should buffer no more packets than is required to ensure effective traffic shaping. Otherwise the incoming streams would never be able to take advantage of the outgoing capacity which is periodically available, but not guaranteed on the outgoing link. The optimal number of packets that should be buffered will depend on the traffic being shaped, but is typically between 2 and 100 packets. This is configurable by the user of the system. Therefore, once the number of packets in the buffer exceeds a certain number of packets, the outgoing rate of the rate limiter 202 is increased incrementally (but the rate will never exceed 0_MAX). This allows the backlog of packets to decrease. The rate limiter shall keep increasing its outgoing rate until the number of packets buffered in the system falls below the minimum number of buffered packets as configured by the user, at which time it shall decrease its outgoing rate to force a backlog of packets to build up in the channel queues (but the rate will never fall below 0_MIN). This mode of operation continues while R remains lees than or equal to the actual available outgoing rate. When R exceeds this value, the outgoing link is congested and the traffic shaper is able to shape the outgoing traffic in the traditional way.

In practice, we have found that certain traffic types can fail to shape in the presence of other traffic. Most notably, TCP traffic (which has end to end congestion avoidance mechanisms) will fail to shape correctly if it is required to compete for bandwidth with unconstrained streams of UDP traffic (which have no such congestion avoidance mechanism). The reason for this is that if TCP sees congestion at any point in its end to end network path, it will back off from sending more packets. This means that channels in the traffic shaper that are shaping TCP streams can be starved of incoming packets and thus prevented from properly shaping if UDP is allowed to swamp the link at a point outside of the traffic shaping device's control. We found that the best way to ensure that this does not occur is to make sure that there are some TCP packets in the backlog of packets in the traffic shaper. If the traffic shaper is then making sensible shaping decisions, then traffic will be shaped according to the traffic profile specified by the user and misbehaving UDP traffic will only be allocated that percentage of the link specified by the profile the user has allowed.

Therefore, the user of the system is given the option to make the rate limiter adapt to the incoming rate based only on specific types of traffic (in most cases, TCP will be selected). Thus, when looking at the backlog of packets for making the decision for increasing or decreasing the rate of the outgoing rate limiter, the shaper may choose to only use the number of backlogged packets of a certain type.

The complete algorithm for the method is presented below. In the algorithm description, the following refer to:

0_M,_N - The minimum output rate of the rate limiter 202

0_MAX - The maximum output rate of the rate limiter 202

LIMITERRATE - The output rate of the rate limiter 202 any instant

PB - The number of packets buffered (backlogged) in the traffic shaper queues 204, 205 and 206. Note that this may be either all packets in the system or only a certain type of traffic (for example, TCP)

UPDATETIME - The time between checks to decide whether to increase or decrease LIMITRATE

CURRENTTIME - The current time.

DECTHRESHOLD - The threshold number of backlogged packets at which a decrease in LIMITERRATE value is made.

INCTHRESHOLD - The threshold number of backlogged packets at which an increase in LIMITERRATE value is made.

INCRATE - The quantum by which LIMITERRATE is increased when required.

DECRATE - The quantum by which LIMITERRATE is decreased when required. while (incoming packets are being received)

{ if( timeToUpdate exceeded)

{ if( PB < DECTHRESHOLD )

{ decrease LIMITERRATE by DECRATE but do not go below

OMIN } else if( PB between DECTHRESHOLD and INCTHRESHOLD)

{ keep LIMITERRATE the same

} else if( PB > INCTHRESHOLD ) { increase LIMITERRATE by INCRATE but do not go above 0_MAX

} timeToUpdate = CURRENTTIME + UPDATETIME

> continue.

Claims

1. A method of traffic shaping in a packet switched network, said method including the steps of, upon receiving through a selected period of time a plurality of incoming identifiable data traffic streams, effecting traffic shaping by selecting packets from each of the incoming data streams in accordance with a selected traffic profile, then emitting these selected packets as one or more amalgamated outgoing data traffic streams at a rate so as to maintain, that when a sum of the incoming data traffic streams instantaneous data rates is greater than a selected minimum data rate value, buffering of at least some of the incoming data traffic packets will be effected.

2. The method of claim 1 wherein an output of the method is adapted to be provided to a variable data rate transmission system.

3. The method of claim 2 wherein the said selected minimum data rate is not greater than a minimum data rate which has been made available by the downstream variable data rate transmission system.

4. The method of claim 2 wherein the selected minimum data rate is slightly less than the minimum data rate actually available by the downstream variable data rate transmission system.

5. The method as in any one of the preceding claims further characterised in that only selected incoming data traffic streams shall be subject to some buffering at all such times.

6. The method of claim 5 wherein such buffering is achieved by ensuring a selected number of packets are queued for each of selected streams at all such times.

7. The method of claim 6 wherein such selected streams are those using selected communications protocols where such protocols incorporate adaptive end to end congestion avoidance.

8. The method of claim 6 wherein at least one of the selected communications protocol is TCP/IP.

9. The method of any one of the preceding claims wherein there is provided means to receive and store a specification of a minimum bandwidth the traffic shaping method is shaping for.

10. The method of claim 9 wherein the method is further characterised in that no traffic shaping is effected when a sum of the data rates of all the streams arriving to be dealt with is less than a minimum data rate of the downstream variable data rate transmission system.

11. The method of claim 9 wherein the variable data rate transmission system is a Frame Relay system.

12. A method of shaping traffic in a packet switched network, where the traffic includes a plurality of identifiable data traffic streams composed of packets, including the steps of establishing separate queues for the packets of each of said data streams; selecting a maximum and a minimum output rate at which packets may be emitted; selecting a maximum and a minimum number of packets to be held in any one or any combination of queues at any instant; establishing an instantaneous output rate at which packets are to be emitted; while input packets continue to be received, iteratively performing the following steps a-b; a. if the number of packets in the queues is below said minimum number of packets, decreasing said instantaneous output rate; b. if the number of packets in the queues is above said maximum number of packets, increasing said instantaneous output rate.

13. A computer programmed to perform the method of any one of the preceding claims.

14. A computer program adapted to effect a method as in any one of the preceding claims when operatively acting within a computer

15. A traffic shaping apparatus arranged to perform the method of any one of preceding claims 1 through 12.

16. A traffic shaping apparatus for shaping packet switched network traffic, said traffic including a plurality of incoming identifiable data traffic streams, the apparatus including means to effect traffic shaping by selecting packets from each of the incoming data streams in accordance with a selected traffic profile, means to emit these selected packets as one or more amalgamated outgoing data traffic streams at a rate so as to maintain, that when a sum of the incoming data traffic streams instantaneous data rates is greater than a selected minimum data rate value, buffering of at least some of the incoming data traffic packets will be effected.

17. The traffic shaping apparatus of claim 16 wherein an output of the apparatus is adapted to be provided to a variable data rate transmission system.

18. The traffic shaping apparatus of claim 17 wherein the said selected minimum data rate is not greater than a minimum data rate selected to be made available by the downstream variable data rate transmission system.

19. The traffic shaping apparatus of claim 17 wherein the selected minimum data rate is slightly less than the minimum data rate selected to be made available by the downstream variable data rate transmission system.

20. The traffic shaping apparatus of any one of claims 16 to 18 further including means to select which of the incoming data traffic streams shall be subject to some buffering at all such times.

21. The traffic shaping apparatus of claim 20 wherein such buffering is achieved by ensuring a selected number of packets are queued for each of selected streams at all such times.

22. The traffic shaping apparatus of claim 21 wherein such selected streams are those using selected communications protocols where such protocols incorporate adaptive end to end congestion avoidance.

23. The traffic shaping apparatus of claim 22 wherein at least one of the selected communications protocol is TCP/IP.

24. The traffic shaping apparatus of any one of the preceding claims 16 to 23 further including means to receive and store a specification of a minimum bandwidth the traffic shaping apparatus is shaping for.

25. The traffic shaping apparatus of claim 24 wherein the variable data rate transmission system is a Frame Relay system.

26. A traffic shaping apparatus for shaping traffic in a packet switched network, where the traffic includes a plurality of identifiable data traffic streams composed of packets, including separate queues for the packets of each of said data streams; means to select and store a maximum and a minimum value for an output rate at which packets may be emitted; means to select and store a maximum and a minimum value for a number of packets to be held in any one or any combination of queues at any instant; means to emit packets at an instantaneous rate; means to iteratively perform the following steps a-b while input packets continue to be received; a. if the number of packets in the queues is below said minimum number of packets, decreasing said instantaneous output rate; b. if the number of packets in the queues is above said maximum number of packets, increasing said instantaneous output rate.

Dated this 10th day of October 2003

FOURSTICKS PTY LTD

By his Patent Attorneys

COLLISON & CO