WO1999009782A1 - Method for atm communication statistical multiplexing - Google Patents

Abstract

During ATM communications a plurality of communications are transmitted through common link sections. New incoming communications are allowed on the basis of decisions made by acceptance algorithms. However only yes/no decisions are made. It is nevertheless desirable that the reserved band width required for all the communications carried out by said link sections be known. This problem is solved by the invention whereby the band width is evaluated by steps while communications are being set up/switched out, by modifying the sigma rule algorithm.

Description

description

Method for statistical multiplexing of ATM connections.

The invention relates to a method according to the preamble of claim 1.

A plurality of connection types are defined for connections via which information is transmitted according to an asynchronous transfer mode (ATM). On the one hand, connections with strict requirements for cell delay times are differentiated from connections that do not have strict requirements for line delay times.

The former include, in particular, connections via which information is transmitted at a constant bit rate (constant bit rate, CBR), and connections via which real-time information is transmitted at a variable bit rate (rt-VBR).

The latter include non-real-time VBR connections (nrt-VBR), or connections via which information is transmitted at a variable bit rate (available bitrate, ABR) or unspecified bitrate connections (UBR).

The information on all five connection types is routed in ATM cells together via virtual paths or virtual lines with a predetermined bit rate (bandwidth). As part of the establishment of new connections which have stringent requirements for the line delay times, it is necessary to calculate the bandwidth which is required for the entirety of all connections made via a connection section / connection line or a virtual path. To calculate this effective bandwidth, it is necessary to determine at what rate it is for that type of connection as well as the other connection types (nrt-VBR, ABR, UBR) provided large cell memory may be emptied.

In general, when an ATM connection is set up, the sending device must inform a higher-level control device (call acceptance control) of predetermined parameters. This is necessary to ensure the quality of the connection for all participants (Quality of Service). For example, if too many cells are transmitted and the transmission capacity is exceeded, too many cells would have to be discarded. However, this should be avoided under all circumstances, as this always involves a loss of information. For this purpose, standardization bodies, for example, call for a cell loss probability of 10 ^{"10 of} a connection. For this reason, it is calculated when the connection is established whether this new connection to existing connections can be accepted. If the transmission capacity has already been exhausted, the requesting connection is rejected.

A number of transmission parameters are defined to describe these processes. This includes, for example, the peak cell rate (PCR) defined on a connection. This is an upper limit for the number of ATM cells that can be transmitted over this connection per second. Furthermore, the control device is informed by the sending device of a permanently permitted cell rate (SCR) in the case of a connection with a variable bit rate. This is the upper limit of an average cell rate at which the cells are transmitted during the connection. As a further parameter, the control device knows the maximum possible transmission capacity of the connecting line (Link Cell Rate, C) and the maximum possible load on the connecting line (p ₀ ). The former is essentially a material constant of the connecting line, while the latter defines a size with which the maximum permissible total cell rate is specified on the connection line. This is usually 95% of the maximum possible transmission capacity of the connecting line. Based on these parameters, it is then decided whether new connection requests can be met or not.

For this purpose, an algorithm runs in the higher-level control device, by means of which the parameters received from the sending device are checked. Furthermore, these are compared with parameters that have already been calculated and relate to the instantaneous load on the connecting line. Based on these comparisons, a decision is then made as to whether the new connection request can be met and whether this connection can still be permitted. The key parameters include use the already mentioned peak cell rate or the sustainable cell rate.

In the prior art, a number of methods have been developed to deal with these processes. The Sigma Rule algorithm is a simple procedure. This algorithm is disclosed in detail in German patent application DP 196 49 646.7. An nth connection is only permitted if the following applies to the (n-1) existing connections plus the nth connection:

(a) PCR, <p ₀ -C

The connection is also permitted if, taking into account additional properties of the n connections, as explained below, the following condition (b) is fulfilled.

(b) ∑ SCR _! + q (c, class S) • (∑ SC_V (PCR. - SCR) ¹² <VC _X ε class S VC _λ ε class S

P _o "C - ∑ PCR, VCj ε class P where c = p ₀ -C - ∑ PCR _{± is} the free capacity for class S.

The condition (b) shows that the pending connections are divided into two classes. At the start of the connection establishment, the sigma rule algorithm must therefore decide which of two classes, namely a class S and a class P, the ATM connection which is to be added is to be divided.

All virtual connections are assigned to class S, for which statistical multiplexing according to the sigma rule algorithm would bring a clear gain compared to the peak cell rate reservation algorithm. As a criterion for this type of connection, the following condition must be met for the peak cell rate and the permanently permitted cell rate of all compounds to be statistically multiplexed:

PCR / C <0.03 and (0.1 <SCR / PCR <0.5)

All other virtual connections are assigned to class P. This includes, in particular, the connections with constant bit rate. Furthermore, all the connections are assigned here for which the parameters SCR and PCR are very close to each other - or very far apart, or which already have a high peak cell rate PCR in relation to the total capacity of the connecting line. The criterion for this is a peak cell rate that is greater than 3% of the maximum possible transmission capacity of the connecting line.

A factor q can also be taken from condition (b). This factor depends on both class S and the free capacity c of class S. For a defined class S, the q (c) values have to be calculated using a complex program. Simplifying under dynamic facial the dependence on the size c is estimated by a hyperbolic function q (c) = q ₁ + q ₂ / c.

In this prior art, an nth virtual connection VC _n with a defined peak cell rate PCR _n and a permanently permitted cell rate SCR _n becomes (nl) already existing virtual connections VC _± with the parameters SCRi and PCRi (l <i <nl ) permitted on a connecting line if conditions (a) or (b) are met.

According to condition (a), it is checked whether the sum of the peak cell rates of all n connections on the connecting line is less than or equal to the maximum possible transmission capacity on the connecting line. If this is the case, the nth virtual connection can be accepted and there is no need to query condition (b). If this is not the case, then condition (b) checks whether the upper estimate of the mean of the sum of the peak cell rates of all compounds of class S together with a cell rate which is calculated from the burstiness of all compounds of class S is smaller or is the cell rate currently available for Class S connections. If this is the case, the nth virtual connection is accepted, in the other case it is rejected.

In this prior art, the first class S is now subdivided into further sub-classes S _x , S ₂ or S _{3 in} order to achieve an even finer classification. If a new connection request is received, the sigma rule algorithm must therefore check which of the subclasses this new connection is to be assigned to, in accordance with specified query criteria. The cheapest sub-class S _x is then automatically selected. A subclass S _x is defined via a lower limit or upper limit of the peak cell rate PCR and the ratio of the transmission parameters SCR / PCR. Formula (b) is thus modified by the sub-classes S _k , P mentioned

∑ SCR _{i +} q (c, S _k ) - ∑ SCIMPCR, SCRi, <c

VCiεS _k I VC _j εS _j

where c = p ₀ .C - ∑PCR _; the free capacity for the class S vc _jε p _k

The q factor thus results in q (c, S _k ) = ql _St + q2 _Sk 1 c

This connection acceptance algorithm according to this prior art is therefore able to decide whether a given bandwidth, for example the bandwidth of a virtual path or a line, is sufficient for a group of connections as a whole. Since such acceptance algorithms provide a yes / no decision as to whether a connection is to be accepted or not, they are not suitable directly for calculating the effective bandwidth for a group of connections.

The effective bandwidth required for a group of connections in accordance with the Sigma Rule acceptance algorithm used could in principle be determined as precisely as desired using an iterative approximation method. The problem with this method, however, is that the acceptance algorithm would have to be run through several times per connection establishment and would therefore cost a great deal of processor capacity.

The invention has for its object to show a way how to design an acceptance algorithm in such a way that a bandwidth representative of all connections can be calculated in an efficient manner. The invention is achieved on the basis of the features specified in the preamble of claim 1 by the features of the characterizing part.

It is particularly advantageous for the invention that the sigma rule algorithm is used as the acceptance algorithm. Starting from an initial value, the bandwidth is determined step by step with the connection setup / disconnection. The sigma rule algorithm is started at every step and, in addition to a yes / no decision, provides an estimate of the bandwidth by first adding or subtracting a conservative traffic parameter value to a class-specific bandwidth based on acceptance criteria. The conservative traffic parameter value is different in the case of connection establishment than in the case of connection disconnection. If the sigma rule algorithm determines that the conservative bandwidth estimate would be sufficient, a more aggressive traffic parameter value is added or subtracted from the class-specific bandwidth. Here, too, the more aggressive traffic parameter value is different in the case of connection establishment than in the case of connection disconnection.

Advantageous developments of the invention are specified in the subclaims.

The invention is explained in more detail below using an exemplary embodiment.

Show it:

Fig. 1 drive a flow chart according to the invention. Fig. 2 is a flowchart according to the invention. 1 shows a flow chart of the method according to the invention. The sigma rule algorithm SR described at the outset as prior art is used as the acceptance algorithm. Accordingly, additional state variables are introduced in addition to the state variables guided in the Sigma Rule Algorithm SR. These are the state variables c ^Sκ , c ^Pk and c * ¹ :

The state variable c ^Sκ is the effective bandwidth of the virtual connections which, according to the sigma rule algorithm SR, are to be assigned to one of the classes S _k . The state variable c ^p "specifies the sum of the peak cell rates PCR of all virtual connections in class P, while the state variable c ^ * is defined as the effective bandwidth of all connections in relation to the classes k.

(1) c ^ "= c ^ + c ^Pk

In order to establish a connection, existing ₍ V- _± ) connections VC _± are now calculated with the parameters PCR _{i (} SCR _± , whether

1. the new connection VC _n can be accepted or not,

2. the effective bandwidth c ⁶ * "to be reserved for the (n-1) existing connections VCi including the newly added connection VC _n .

In a first step, it is first checked whether the new, possibly to be accepted, connection VC _n can be assigned to one of the classes S _k or P _k . As an example, assume that this can be assigned to one of the S classes. In this case, it is checked whether the following condition is met for all virtual connections VCi, including any additional connections:

(2) ∑SCR _i + q (c ^Sκ + SCR _n , S _k ) <c ^Sκ + SCR _t

In obiger Formel wird Formel (c) als Basis genommen und die dort verwendete Variable c durch die für die (n-l) Verbindungen reservierte Bandbreite c^ zuzüglich der dauernd erlaubten mittleren Zellenrate SCR_n, die für die n-te gegebe- nenfalls anzunehmende Verbindung VC_n zu reservieren ist, ersetzt. Das Vervahren wird wie gemäß Fig. 1 ersichtlich ist, mit einem Wert c^Sκ =0 gestartet.VC _j εS _k

In the above formula, formula (c) is used as the basis and the variable c used there is determined by the bandwidth c ^ reserved for the (nl) connections plus the permanently permitted average cell rate SCR _n , the connection VC that is to be assumed for the nth connection _n to be reserved is replaced. As can be seen in FIG. 1, the process is started with a value c ^Sκ = 0.

Strict application of condition (2) may result in a bandwidth that is greater than the sum of the peak cell rates PCR _{n of} all compounds. Since the sum of all added effective bandwidths can never be greater than the sum of their peak cell rates PCR _n , condition (2) is modified in such a way that

(3: min ∑ SCR _{i +} q (c ^Sk + SCR _n , S _k ). ∑SCR ^ PCR - SCR _; ), ∑PCR _;

VC, εS _k VC.ε ^ VC.ε ^

c ^Sκ -t-SCR _n

is taken. This provides certainty in the estimation.

If the above condition ^applies, the effective bandwidth used up to that point, plus the mean cell rate SCR _n permanently permitted for the nth connection VC _n , is taken as the new effective bandwidth c ^Sκ . This results in:

(4) c ^ c ⁸ * + SCR _n

If condition (3) is not met, the effective bandwidth used up to that point plus the peak cell rate PCR _n permitted for the nth connection VC _n is taken as the new effective bandwidth c ^.

(5) (. **: = c ^Sk + PCR " In the event that the new, possibly additional, connection VC _{n is to be assigned to} one of the classes S _k , a value for the effective bandwidth c ^{κ has been} found.

If the new, possibly additional, connection VC _n cannot be assigned to one of the classes S _k , it is automatically assumed that it is to be assigned to one of the classes P _k . This results in:

(6) c ^Pk : = c ^Pk + PCR _n

The effective one can then be used using the formula (1)

Calculate bandwidth ceff ^κ :

c ^effk = c ^Sk + c ^Pk

An effective bandwidth is thus found in the event of a connection being established.

In the following it has to be determined whether the new connection VC _n can be accepted. To do this, the condition

c ^ ≤Po-C

be fulfilled.

In the following, it is assumed according to FIG. 1 that a connection is to be cleared down. It is assumed here that with n existing connections VC _± a connection VC _n is cleared down with the parameters PCR _t , SCR.

When the connection is triggered, it is first checked whether this connection VC _{n in} question was assigned to one of the classes S. In this case, a query criterion is applied to all remaining virtual connections VCi (excluding connection VC _n ) according to condition (7): ∑SCR, -r- qCc ^ - PCR _n , S _k ). ∑ SCR,. (PCR, - SCR,) ≤ c ^Sk - PCR _n

(7) VC, εS _k V VC, εS _k

Strict application of condition (7) now results in a bandwidth for the remaining (n-1) connections that is greater than the sum of the peak cell rates of the connections. Therefore condition (7) should be modified in such a way that

(8) min ∑ SCR _I + q (c ^s> - PCR _fI , S _k ). ∑SCR ^ PCR, - SCR,), ∑ PCR,

VC, εS _k VC.εΣ ^ VC, εS _k

<c ^Sκ -PCR _n

results.

If the above condition applies, then the effective bandwidth used up to that point minus the peak cell rate PCR _n permitted for the nth connection VC _n is taken as the new effective bandwidth c ^s ".

(9) c ^ c ⁵¹ -PCR _n

If the condition (8) is not met, the effective bandwidth used up to that point minus the cell rate SCR _n permanently permitted for the nth connection VC _n is taken as the new effective bandwidth c ^Sκ .

(10) c ^ c ¹ -SCR _D

In the event that the cleared connection VC _{n was assigned to} one of the classes S _k , a value for the effective bandwidth c ^{eSκ was} found. If the cleared connection VC _{n was} not assigned to one of the classes S, it is automatically assumed that it was assigned to one of the classes P _k . This results in:

(11) c ^Pk : = c ^Pk -PCR _n

The effective bandwidth c " ² * can then be calculated using formula (1):

c ^effk = c ^ + c ^Pk

This means that an effective bandwidth is found in the event of a connection being terminated.

In one embodiment of the invention, instead of the formula (10)

to put. Thus, when connections that were assigned to one of the classes S _k are ^cleared , the value of the class-specific bandwidth c ^{S κ is capped} by the sum of the peak ^{cell rate of} all connections assigned to the classes S _k . The corresponding relationships are shown in FIG.

Claims

claims l. Method for statistical multiplexing of ATM connections, with a plurality of ATM connections which are routed via a common connecting line and for which an effective bandwidth (c ^6ffκ ) is reserved in total on this connecting line, and with an acceptance algorithm. thmus (SR), of which, when a connection request arrives, a further connection that may be added is assigned to a first (S _k ) or second class (P), and from which a decision is made in connection with acceptance criteria with regard to a bandwidth to be observed, whether this further, if applicable additional connection can still be accepted on the common connection line, characterized in that the effective bit rate (c ^) is determined step by step from an initial value with the establishment / termination of connections by starting the acceptance algorithm (SR) at each step, and a first for the first class (S _k ) representative bandwidth (c ^Sκ ) and a second for the second class (P _k ) representative bandwidth (c ^Pk ) is defined, and according to the assignment of the connection in question to one of the two classes (S _k , P _k ) and little - At least one acceptance criterion (c ^effκ ) the first or second bandwidth (c ^Sκ , c ^Pk ) is changed by a first (SCR) or a second traffic ^parameter value (PCR). 2. The method according to claim 1, characterized in that the first traffic parameter value is the permanently allowed cell rate (SCR) and the second traffic parameter value is the peak cell rate (PCR) of the connection in question. 3. The method according to claim 1 or 2, characterized in that the acceptance criterion in the case of the connection establishment is designed such that if the possibly newly added connection can be assigned to the first class (S), it is calculated whether the one determined in the step beforehand the first bandwidth (c ^Sκ ) including this connection is sufficient, whereby it is ensured that the calculated first bandwidth must not exceed the sum of the peak cell rates of all connections and that if the acceptance criterion is met, the first bandwidth (c ^Sk ) around the first traffic ^parameter value (SCR _n ) and is otherwise increased by the second traffic parameter value (PCR _n ). 4. The method according to claim 3, characterized in that if the possibly new connection of the first class (S _k ) is not assignable, this is automatically assigned to the second class (P _k ), and the second bandwidth (c ^p ") is increased by the second traffic parameter value (PCR _n ). 5. The method according to claim 1, 2, characterized in that the acceptance criterion in the case of the connection clearing is designed such that if the connection to be cleared was assigned to the first class (S _k ), it is calculated whether the first determined in the step Bandwidth (c ^Sκ ) exclusive of this connection is sufficient for the remaining connections, it being ensured that the calculated first bandwidth must not exceed the sum of the peak ^{cell rates of} all connections, and that if the acceptance ^{criterion is met,} the first bandwidth (c ^Sκ ) is ^reduced by the second traffic ^parameter value (PCR _n ) or otherwise by the first traffic ^parameter value (SCR _n ). 6. The method according to claim 5, characterized in that if the connection to be broken down was not assigned to the first class (S _k ), it is automatically assumed that this was assigned to the second class (P _k ), and in this case the second Bandwidth (c ^{? K} ) is reduced by the second traffic parameter value (PCR _n ). 7. The method according to claim 5, characterized in that the acceptance criterion in the case of connection clearing is designed such that if the connection to be ^{cleared was} assigned to the first class (S), it is calculated whether the first bandwidth (c ^Sκ ) previously determined exclusive of this connection is sufficient for the remaining connections, and that if the acceptance ^criterion is met, the first bandwidth (c ^Sκ ) is reduced by the second traffic ^parameter value (PCR _n ), or otherwise the value of the determined first bandwidth (c ^Sκ ) is reduced by the The sum of the first class peak cell rates (S _k ) is capped. 8. The method according to any one of the preceding claims, characterized in that the effective bandwidth (c " ⁰ *) results from the sum of the first (c ^Sκ ) and second (c ^p ") bandwidth. 9. The method according to any one of the preceding claims, characterized in that the acceptance algorithm (SR) is only started once for each connection that may be added or to be terminated.