CN1868179A - Method and equipment for performing aggregate-portion-specific flow shaping in packet-switched telecommunications - Google Patents

Abstract

The invention relates to a method and equipment for performing aggregate-portion-specific flow shaping in packet-switched telecommunications, in such a way that the traffic flows (V1-VL) arriving in the system can be arbitrarily bundled into shaping groups and the speed properties (CIR, PIR, CBS) of an aggregate portion formed of packets representing the arbitrary shaping group (k) can be monitored and limited (aggregate-portion-specific shaping group). The invention is based on the fact that the earliest permitted moment, at which a packet in the system can be forwarded, is defined as the greatest value of the VTS values of all the shaping groups to which the traffic flow represented by the packet belongs, and as a result of the forwarding of the packet, the VTS values of the same shaping groups (k) are updated, in which the VTS value of an individual shaping group (k) expresses the earliest permitted moment, at which a packet belonging under the relevant shaping group (k) can be forwarded, without breaking the restrictions of the speed properties of the shaping group (k) being examined.

Description

Method and apparatus for performing shaping on a set of specific traffic parts in packet-switched telecommunications

According to claim 1, the invention relates to a method for performing shaping on a set of specific traffic flow parts in packet-switched telecommunications.

According to claim 3, the invention also relates to a device for shaping a set of specific traffic flow parts in packet-switched telecommunications.

In this disclosure, the following abbreviations are used when describing the prior art and the present invention:

CBS Committed Burst (the maximum allowed burst [bits] when the committed information flow is exceeded),

CIR Committed Information Rate (maximum allowed average traffic speed ([bit/s])),

FIFO first in first out rule,

MP measurement point, in which the speed characteristics of the traffic flow (such as average traffic speed, instantaneous traffic speed, burst volume) are measured,

PIR peak information rate (maximum instantaneous traffic velocity allowed ([bit/s]),

PKS packet size in bits,

V1, V2, ... business flow 1, 2 ...,

VTS earliest time, after which the next representative traffic flow or shaping group can be transmitted to avoid violating any rule set for the speed characteristics of said traffic flow or shaping group (effective sending time),

VTSi earliest time after which the next packet representing traffic flow i can be transmitted in order to avoid violating any of the rules set for the speed characteristics of said traffic flow,

VTSk earliest time after which the next packet representing shaping group k can be transmitted in order to avoid violating any of the rules set for the speed characteristics of said shaping group,

VTS_pk the earliest time after which a packet can be transmitted in order to avoid violating any of the rules set for the speed characteristics of any shaping group associated with said packet (effective time to send),

VTS_CIR Earliest time after which the next packet representing a specific traffic flow or shaping group can be transmitted to avoid exceeding the maximum allowed average speed and/or the maximum allowed burst size,

VTS_PIR Earliest moment after which the next packet representing a specific traffic flow or shaping group can be transmitted to avoid exceeding the maximum allowed instantaneous speed,

In general, in packet-switched telecommunications systems, it is advantageous to be able to monitor and limit the speed characteristics of traffic flows (formed by packets being transmitted). For example, the speed characteristic can refer to the average traffic speed (CIR), the burst volume (CBS) (which can momentarily exceed the above average speed), or the instantaneous speed (PIR). A traffic flow may consist of packets to be routed to a specific transit link, packets sent by a specific end user (with a specific source address), or packets to be routed to a specific transit link (with a specific class of service). In the illustrations given in this disclosure, see Figures 1, 2, 3, and 4, individual traffic flows are composed of packets and they are directed to specific queues according to the order in which they enter the system.

Figure 1 shows a method for monitoring and limiting the speed characteristics of traffic flows according to the prior art. In the following description to further clarify the issue, the term "speed characteristic" is used to cover average speed (CIR [bit/s]), burst volume (which can momentarily exceed the above average speed) (CBS [bit]), and instantaneous speed (PIR[bit/s]). When the packet initiating transmission passes the measuring point (MP) marked in FIG. 1 (ie when the first bit of the transmitted data packet passes the point MP), the values of the variables VTS_CIR and VTS_PIR are calculated for the next packet. VTS_CIR gives the earliest time when the next packet that can start to be transmitted is allowed by the MP, so as not to exceed the relevant limit of CIR or CBR. Correspondingly, VTS_CIR gives the earliest time that the next packet that can start to be transmitted passes through the MP, so as not to exceed the relevant constraints of the PIR. Equations 1 and 2 show the general rules used to calculate the VTS_CIR and VTS_PIR values:

VTS_CIRnext=max(t-CBS/CIR, VTS_CIRprev)+PKS/CIR, (1)

as well as

VRS_PIRnext=max(t, VTS_PIRprev)+PKSprev/PIR, (2)

where t is the time, PKS is the packet size in bits, the subscript 'next' refers to the next packet, and the subscript 'prev' refers to the packet whose first bit passed the MP at time t.

When all velocity characteristics are considered, the earliest allowed time (VTS) (ie the time at which the next packet for transmission starts to pass through the point MP) is derived from Equation 3.

VTS＝max(VTS_CIR，VTS_PIR)        (3)

In the remainder of this disclosure, a system by which the speed characteristics of a traffic flow can be monitored and limited will be referred to as a "shaper" (SH), whereas the monitoring and limiting of the speed characteristics of a traffic flow will be The operation is called "shaping". An essential part of shaping is the buffer buffer, in which those packets that cannot be transferred immediately after reaching the system (ie via point MP) due to speed constraints can be stored. If it is hoped that the above shaping does not change the transmission sequence of the packets, a FIFO (first in first out) queuing rule can be applied in the buffer buffer, as shown in FIG. 1 .

Fig. 2 shows a system according to the prior art, in the case of changing (multiplexing) some of the service flows into a single service flow set Va, the system is used for the above-mentioned several parallel Service flows V1...V5 are shaped. For example, multiplexing can be achieved by applying the SFQ (Start Time Fair Queuing [1]) method. In the system shown in the figure, the velocity characteristics of the portion formed by the packets representing the individual traffic flows (V1, ..., or V5) of the traffic set Va can be monitored and limited. The measurement points (MP1, ..., MP5) related to the above multiplexed traffic flows (V1, ... V5) are all at the same position in the output of the multiplexer. The measuring point MPi only monitors the packets representing the multiplexed traffic flow Vi (i=1, . . . , 5). Similarly, only the packets representing the traffic flow Vi are considered when calculating the earliest allowed transmission instant VTSi. For example, as shown in Equations 1, 2, and 3, the earliest allowed transmission instant VTSi can be calculated for the multiplexed traffic Vi.

A case is described below in which it is desirable to shape a set of specific parts, for example, to allow monitoring and limiting the speed characteristics of the part formed by packets representing traffic V1 and V2 in the above-mentioned traffic set, monitoring and Limiting the speed characteristics of the portion formed by the packets representing the traffic V3 and V4 in the above traffic set, and monitoring and limiting the speed characteristics of the entire traffic set. In this disclosure, this type of reshaping is referred to as reshaping on a set of specific parts. In the rest of this disclosure, such a situation will be expressed in such a way that traffic flows V1 and V2 belong to a specific shaping group, V3 and V4 belong to a specific second shaping group, and traffic flows V1, V2, V3, V4, and V5 belong to a specific third shaping group. The shaping group including service flows V1, V2, V3, V4, and V5 includes the shaping group including service flows V1 and V2 and the shaping group including service flows V3 and V4. This means that shaping can be layered.

In the system realized according to Fig. 2, the set of certain parts is shaped, but measured in terms of shaping, it has the restriction that said set of parts is always represented by only a single incoming traffic flow V1, V2 , V3, V4, or V5 service flows.

Fig. 3 shows a system according to the prior art for implementing shaping corresponding to the example situation described above. The service flows V1 and V2 are multiplexed into a service flow V1a, and the shaper SH1a performs shaping on it to obtain a service flow V1b. Service flows V2 and V3 are multiplexed into service flow V2a, and the shaper SH2a performs shaping on it to obtain service flow V2b. The service flows V1b, V2b and V5 are multiplexed into the service flow V3a, and the shaper SH3a performs shaping on it to obtain the service flow V3b.

It is often the case that it is desirable to ensure the transmission capability of the system by setting a higher privilege for a particular incoming traffic flow (eg V1) than another traffic flow (eg V2). In the system shown in Figure 3, when considering the traffic flows V1 and V2, this problem is traditionally solved by an operation, namely controlling the multiplexer Mux1 so that the packet can only be transmitted if the FIFO1a queue is empty to the queue. The established term "back pressure" is used to denote such an operation. This prevents the situation where the queue FIFO1a is filled with packets representing traffic V2; thereby forcing the transmission of later arriving packets representing traffic V1 to be postponed. Such operations complicate the system shown in FIG. 3 .

The following questions concern the system shown in Figure 3:

Problem 1) Even though traffic V1b and V2b are monitored and limited according to desired speed characteristics (e.g. CIR, PIR, CBS), the multiplexing of traffic V5 in multiplexer Mux3 will result in , there is no guarantee that the speed characteristics of the parts of the traffic flow V3b formed by the packets representing the traffic flows V1b and V2b are within their desired limits. In other words, collections of specific parts cannot be reshaped.

Problem 2) The logical topology of a multiplexing and shaping system depends on how traffic arriving at the system is packaged into different shaping groups. The system shown in Figure 3 is only responsible for packaging individual service flows into different shaping groups. In other words, the topology is arbitrary. This hinders the implementation of shaping systems. Circuit implementation, for example using ASIC (Application Specific Integrated Circuit) microcircuits, in particular becomes very difficult, while software implementation is also difficult.

The present invention seeks to eliminate the drawbacks of the prior art disclosed above, and for this purpose creates entirely new methods and devices to perform shaping in packet-switched telecommunication. It is an object of the present invention to provide a method and a device which perform shaping in a specific way so as to avoid the aforementioned problems associated with the prior art.

The method according to the invention is characterized by what is stated in the characterizing part of claim 1 .

Instead, the device according to the invention is characterized by what is stated in the characterizing part of claim 3 .

In the following, the invention will be explained in more detail with the aid of examples shown in the drawings.

Fig. 1 shows a block diagram of a method for monitoring and limiting traffic flow velocity characteristics according to the prior art.

Figure 2 shows the monitoring and limiting of the above-mentioned multiple parallel traffic flows V1, ..., V5 according to the prior art in case said traffic flows are altered (multiplexed) into a single traffic set Va A block diagram of the speed characteristics of the system.

Figure 3 shows a block diagram of a system according to the prior art relating to an example situation in which it is desired to perform shaping in order to be able to monitor and limit the traffic set formed by the packets representing the traffic flows V1 and V2 The speed characteristic can monitor and limit the speed characteristic of the service flow set formed by the packets representing the service flows V3 and V4, and the speed characteristic of the service flow set V3 can be monitored and limited.

Fig. 4 shows a block diagram of a system according to the present invention, which is used to perform shaping, so that traffic arriving at the system can be assigned to each shaping group in an arbitrary manner, and can monitor and restrict Velocity characteristics of the set of parts formed by grouping (reshaping for a set of specific parts).

The theoretical basis of the method according to the invention can be clearly understood by reading the following description.

Traditionally, shaping is used for specific traffic flows, eg according to Fig. 1, 2, or 3, where packets are moved in time order. In the method according to the invention, the core concept is the shaping group (ie a collection of parts). As mentioned above, a shaping group consists of incoming traffic flows, and the traffic formed by the packets representing these traffic flows is monitored and restricted using an entire set of constraints on specific speed characteristics, such as the entire set of constraints formed by CIR, PIR, and CBS values. Velocity characteristic of a collection of traffic flow parts. In the method according to the invention, a specific shaping group has a specific VTS value. Thus, the VTS value for a particular shaping group indicates that, to avoid violating any of the rules set for the associated shaping {group}'s speed characteristics (such as CIR), a packet representing the associated shaping group (first bit passing through the measuring point) may be transmitted earliest time allowed. Logically, a specific shaping group also has a specific measuring point. In Figure 4, the measuring points of all shaping groups k are located at the same position. It is then naturally possible to realize a shaping device in which the positions of the measuring points MP of one or more shaping groups k are set independently. The following description is limited to a situation in which the measuring points MP of all shaping groups are at the same position. It is then possible to refer only to the above-mentioned hits, without mentioning the hits associated with a particular shaping group.

A single service flow can belong to one, several or zero shaping groups k. If the service flow does not belong to any shaping group k, naturally, the above-mentioned shaping device will not set any restrictions on the speed characteristics of the service flow.

On the basis of all shaping groups k to which said packet representing the traffic flow belongs, the earliest permissible moment at which this single packet (the first bit passes through the above-mentioned measuring point) can be transmitted is determined. More precisely,

VTS_pk＝max(VTSk, group belonging to shaping group k), (4)

Wherein VTS-pk is the earliest time after which the packet (its first bit passes through the above-mentioned measuring point) can be transmitted in order to avoid violating any rule set for the speed characteristic of any shaping group related to said packet, And VTSk is the VTS value of shaping group k.

In the system shown in FIG. 4, the packet is the packet closest to the multiplexer of a certain FIFO queue (ie, the packet at the head of the queue). When the packet is provided to the multiplexer 10, and if the multiplexer 10 selects said packet, the packet immediately moves and passes the measuring point. Therefore, there is no internal transfer delay in the multiplexer device. Thus, VTS_pk specifies the earliest time that the packet is allowed to be provided to the multiplexer. For this reason, in FIG. 4 , between the FIFO queue I-L and the multiplexer 10 , an allow/deny operation regarding the transfer of the packet is provided.

When the packet starts to move and passes the measuring point, the VTS values of all shaping groups to which the packet belongs are updated. If the constraints on the shaping group velocity characteristics are expressed in the form of CIR, PIR, CBS, then as shown in Equations 1, 2, and 3, each VTS value can be updated.

In short, the principle of the shaping system according to the invention is as follows:

Situation: A packet (first bit) passes a measuring point.

Action: Update all VTS values of each shaping group to which the above group belongs.

Situation: Determine the earliest time at which the above-mentioned grouping can pass through the above-mentioned measuring point.

Operation: Find the maximum VTS value of each shaping group to which the above packet belongs.

From the above description, it is surprising to note that the method according to the invention does not impose restrictions on the way in which traffic entering the system can be grouped into different shaping groups. According to Fig. 4, by setting the measuring point positions of all shaping groups, it is possible to monitor and limit the velocity characteristics of a partial set formed by groups representing arbitrary shaping groups.

references:

[1] Pawan Goyal, Harric M. Vin, Haichen Cheng. Start Time Fair Queuing: A Scheduling Method for Integrated Services Packet Switched Networks Technical Report TR-96-02, Department of Computer Science, University of Texas at Austin .

Claims (4)

1. method of in packet-switched telecommunications, the set of given traffic streams part being carried out shaping, in the method,

-transmit digital information with the constant or variable grouping of length,

-described grouping with at least two independently Business Stream (V1-VL, Business Stream) form arrive system,

-at least one shaping group (k) of definition in described system, wherein each shaping group comprises at least one Business Stream that arrives described system (V1-VL), and

-at least one shaping group (k) be provided with constraint (as CIR, PIR, CBS), and described shaping group comprise at least two arrival described systems Business Streams (V1-VL),

It is characterized in that:

-will allow to transmit the maximum VTS value that is defined as all the shaping groups (k) under the Business Stream (V1-VL) that described grouping represents the earliest constantly of grouping in the described system, and

The result who transmits described grouping has upgraded the VTS value of identical shaping group (k), wherein, the VTS value representation of single shaping group (k), under the situation of the constraint of the speed characteristics of not breaking described shaping group (k), can transmit the grouping that belongs to this relevant shaping group (k) permission constantly the earliest.

2. the method for claim 1 is characterized in that, the Business Stream (V1-VL) that is included at least one shaping group (k) also all is comprised in certain second shaping group (layering shaping).

3. equipment of the set of given traffic streams part being carried out shaping in packet-switched telecommunications, wherein this equipment comprises

-be used to receive the device of the constant or variable grouping of the length of carrying digital information,

-be used for the grouping that arrives system is classified, make one of them the device of Business Stream (V1-VL, Business Stream) of its expression arrival system,

-be used for device in described system at least one shaping group (k) of definition so that make each shaping group (k) comprise at least one Business Stream that arrives described system (V1-VL) and

-be used to each the shaping group at least one such shaping group (k) the speed characteristics constraint to be set (as CIR; PIR, CBS) device, wherein each such shaping group comprises at least two Business Streams (V1-VL) that arrive described systems, and

-send grouping the device of one or more outgoing links to,

It is characterized in that described equipment comprises

-a kind of device, by means of this device, can be with the maximum that allow to transmit in all the VTS values that be defined as the shaping group (k) under the Business Stream of representing by described grouping the earliest constantly of grouping in the described system, and, by means of this device, can upgrade the VTS value of identical shaping group (k) because of the transmission of described grouping, wherein, the VTS value representation of single shaping group (k), under the situation of the speed characteristics constraint of not breaking described shaping group, allow to send the moment the earliest of the grouping that belongs to described shaping group (k).

4. equipment as claimed in claim 3, it is characterized in that, described equipment comprises a kind of device, and by means of this device, the Business Stream (V1-VL) that all can be included at least one shaping group (k) is defined as (the layering shaping) that belongs to certain second shaping group.

Images