Method and device for establishing a communication link

The invention relates to a method for establishing a communication link for the transmission of digital signals with potentially variable transmission rates in a communication network, in which traffic parameters, including the mean bit rate and the peak bit rate, are transmitted from a network node with a transmission request and from another network node on the basis of the transmitted parameters an acceptance test is carried out whether the connection with a high probability of lossless transmission of all information can be established with regard to the own transmission capacity.

The invention further relates to a device for receiving a plurality of digital signals with potentially variable transmission rates, for which a transmission request and traffic parameters, including the average bit rate and the peak bit rate, are first transmitted to establish the connection, with a device for carrying out an acceptance test by comparing the own transmission capacity with the bandwidth used by existing connections plus the transmission request.

To establish a communication connection, in particular in ATM (asynchronous transfer mode), the receiving network node must check whether the transmission node can handle the transmission intended for transmission. For this purpose, it must be estimated in the network node whether the transmission of the digital signal has a predetermined low cell loss probability (e.g. 10th^-9) can be received. Since the transmitting stations do not regularly transmit with a maximum bandwidth, it is customary for checking the connection acceptance to calculate an effective bandwidth from the traffic parameters signaled when the connection is established. The effective bandwidth is always between the average bandwidth and the maximum bandwidth of a connection. As long as the sum of the effective bandwidths of all connections including the newly arriving ones is below the nominal service rate of the network node (nominal link rate), the new connection can be accepted, otherwise it is rejected.

Since the sum of the maximum bandwidths of all connections can be greater than the link rate, one speaks of statistical multiplexing.

Since the decision about the acceptance of the connection must be made in real time, algorithms have been proposed in which the computation effort is much less than with an exact calculation. Such an algorithm should approximate the achievable utilization of the network node as closely as possible to the exact calculation, but should never exceed it, because this would cause a violation of the quality of service.

A known algorithm has been proposed by Lindberger ("Dimensioning and design methods for integrated ATM networks", Proceedings of the 14th ITC, June 1994, pages 897-906).

With homogeneous traffic, i.e. connections with the same bit rates, the known algorithms based on the effective bandwidth are very successful. They also capture the non-linear relationship between the link rate and the number of connections. In general, if the link rate is doubled, more than twice as many connections can be accepted, because with an increasing number of connections the probability decreases that all transmit at the same time at maximum rate, so that the risk of cell loss decreases with the same relative load.

In contrast, with heterogeneous traffic with potentially very different maximum and average bit rates, the problem arises that statistical multiplexing between connections with very different traffic parameters works less well. The acceptance curve, i.e. the limit curve for the acceptance of connections, is not linear but concave with different traffic parameters. In the case of the linear approximation, as is carried out by the known algorithms, connections would be assumed which would cause a violation of the quality of service.

Optimized algorithms are therefore not available for heterogeneous traffic, which enable a real-time decision on the acceptance of the connection, practically exclude a violation of the quality of service and nevertheless provide a good approximation to the exact calculation of the possible workload of the receiving station.

The present invention is therefore based on the problem of bringing about improvements with regard to the requirements mentioned.

Based on this problem, a method of the type mentioned at the outset is characterized in that in the network node for the acceptance test of a transmission request, a classification of the transmission traffic of the receiving station is carried out with regard to predetermined combinations of the parameters "mean bit rate" and "peak bit rate", that an effective bandwidth is used for the acceptance test by using an algorithm for statistical multiplexing known for homogeneous traffic, taking into account a reduced transmission capacity, and that the effective bandwidths thus determined as required for the classes formed are taken into account essentially additively without statistical multiplexing.

To solve the problem mentioned, a device of the type mentioned at the outset is also equipped with a device which carries out the classification and evaluation mentioned for carrying out the acceptance test.

The present invention is based on the fact that for the calculation of the effective bandwidth of the parameter space formed by the parameters "average bit rate" and "peak bit rate", preferably "average bit rate" and "ratio of peak bit rate to average bit rate", for the connections in classes (regions) is divided. For the calculation of the effective bandwidth of a connection it is assumed that statistical multiplexing works as well within a class as with homogeneous traffic because the connections have relatively similar traffic parameters. No statistical multiplexing is assumed between connections from different classes.

If connections with a constant bit rate frequently occur when establishing the communication connections, it is particularly expedient to assign these connections to a separate class, which is treated in the same way as the other classes formed, i.e. as a special case of a class with a variable bit rate.

The partitioning of the connections with variable bit rate into the different classes takes place exclusively for the calculation of the effective bandwidth. This means that the shares of the individual classes in the total capacity (link rate) of the receiving station are completely flexible and that a new connection is only rejected if the sum of all effective bandwidths would be greater than the link rate.

For the mathematical calculation, the transmission capacity of the network node is taken into account as service rate C and the cell loss probability B. A target limit is set for the cell loss rate<maths id="math0001" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext>B</mtext></mrow><mo>^</mo></mover></mrow></math><img file="EP0940952A2_D0001.tif" /></maths> formulated.

The concept of effective bandwidth transmission rates provides that the effective bandwidths c_i be calculated for each connection so that the connection can be accepted as long as applies<maths id="math0002" num=""><math display="block"><mrow><apply>&lt;sum /&gt;<lowlimit><mtext>i</mtext></lowlimit>&lt;uplimit /&gt;<mrow><msub><mrow><mtext>c</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><mtext> ≤ C</mtext></mrow></apply></mrow></math><img file="EP0940952A2_D0002.tif" /></maths>

The difficulty now is to find an expression for the effective bandwidth. With a homogeneous operation is the greatest number of connections<maths id="math0003" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext>N</mtext></mrow><mo>^</mo></mover></mrow></math><img file="EP0940952A2_D0003.tif" /></maths> find for whom the cell loss probability is still below <maths id="math0004" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext>B</mtext></mrow><mo>^</mo></mover></mrow></math><img file="EP0940952A2_D0004.tif" /></maths> lies. The effective bandwidth then results in<maths id="math0005" num=""><math display="inline"><mrow><mtext>c = C /</mtext><mover accent="true"><mrow><mtext>N</mtext></mrow><mo>^</mo></mover></mrow></math><img file="EP0940952A2_D0005.tif" /></maths>.

The Lindberger algorithm is a simple formula for calculating the effective bandwidth, which is based on the traffic parameters m (average bit rate) and h (peak bit rate), as well as the service rate C and the target size <maths id="math0006" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext>B</mtext></mrow><mo>^</mo></mover></mrow></math><img file="EP0940952A2_D0006.tif" /></maths> for the cell loss probability supports:<maths id="math0007" num=""><img file="EP0940952A2_D0007.tif" /></maths> With <maths id="math0008" num=""><math display="block"><mrow><mtext>a = 1 - </mtext><mfrac><mrow><mtext>log</mtext><mover accent="true"><mrow><mtext mathvariant="italic">B</mtext></mrow><mo>^</mo></mover></mrow><mrow><mtext>50</mtext></mrow></mfrac><mtext> and </mtext><mtext mathvariant="italic">z</mtext><mtext> = </mtext><mfrac><mrow><mtext>-2 * log</mtext><mover accent="true"><mrow><mtext mathvariant="italic">B</mtext></mrow><mo>^</mo></mover></mrow><mrow><mtext mathvariant="italic">C</mtext><mtext>/</mtext><mtext mathvariant="italic">H</mtext></mrow></mfrac><mtext>.</mtext></mrow></math><img file="EP0940952A2_D0008.tif" /></maths>

In any case, the Lindberger approximation is very good for large values ​​of C / h. It also takes into account the profit that can be achieved by statistical multiplexing and increases with the service rate C.

A linear approximation is made for the acceptance limit, which assumes that the effective bandwidths are independent of heterogeneous traffic conditions. However, it has been shown that for large deviations, in particular high peak bit rates in relation to the mean bit rate, there are considerable deviations from the linear approximation, so that the linear approximation underestimates the cell loss probability in a manner which cannot be neglected. This applies in particular to a mix of connections with constant bit rate and the mentioned connections with variable bit rate.

According to the schematic and exemplary representation in FIG. 1, the connections with variable bit rate (VBR connections) are divided into classes, which are regions VBR 1, VBR 2, VBR 3, VBR 4 of the here by the average bit rate m and the ratio of Result in peak bit rate h at medium bit rate m on a spanned parameter space. In addition, the connections with constant bit rate CBR are taken into account separately.

The linear approximation method described above is applied to the connections within the individual classes. On the other hand, if there are two connections in different classes i and j, a reduced service rate C_red,_i used as parameters for the effective bandwidth formula for connections in class i:<maths id="math0009" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><mtext mathvariant="italic">red</mtext></mrow></msub><msub><mrow><mtext>​</mtext></mrow><mrow><mtext>,</mtext><mtext mathvariant="italic">i</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">C</mtext><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><mtext mathvariant="italic">CBR</mtext></mrow></msub><mtext> - </mtext><apply>&lt;sum /&gt;<lowlimit><mtext mathvariant="italic">k</mtext><mtext>=</mtext><mtext mathvariant="italic">l</mtext><mtext></mtext><mtext mathvariant="italic">k</mtext><mtext>≠</mtext><mtext mathvariant="italic">i</mtext></lowlimit><uplimit><mtext mathvariant="italic">K</mtext></uplimit><mrow><mtext></mtext><msub><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><mtext mathvariant="italic">VBR</mtext></mrow></msub><msub><mrow><mtext>​</mtext></mrow><mrow><mtext>,</mtext><mtext mathvariant="italic">k</mtext></mrow></msub></mrow></apply></mrow></math><img file="EP0940952A2_D0009.tif" /></maths>

The service rate is thus determined by the sum of the CBR bandwidths C_CBR and reduced by summed effective bandwidths of the other VBR classes.

Furthermore, the target variable B is also corrected for the cell loss probability as follows:<maths id="math0010" num=""><math display="block"><mrow><msubsup><mrow><mover accent="true"><mrow><mtext mathvariant="italic">B</mtext></mrow><mo>˜</mo></mover></mrow><mrow><mtext mathvariant="italic">i</mtext></mrow><mrow><mtext>*</mtext></mrow></msubsup><mtext> = </mtext><mover accent="true"><mrow><mtext mathvariant="italic">B</mtext></mrow><mo>^</mo></mover><mtext> · </mtext><mfrac><mrow><apply>&lt;sum /&gt;<lowlimit><mtext mathvariant="italic">k</mtext></lowlimit>&lt;uplimit /&gt;<mrow><msub><mrow><mtext mathvariant="italic">M</mtext></mrow><mrow><mtext mathvariant="italic">VBR</mtext></mrow></msub><msub><mrow><mtext>​</mtext></mrow><mrow><mtext>,</mtext><mtext mathvariant="italic">k</mtext></mrow></msub><mtext>+</mtext><msub><mrow><mtext mathvariant="italic">M</mtext></mrow><mrow><mtext mathvariant="italic">CBR</mtext></mrow></msub></mrow></apply></mrow><mrow><msub><mrow><mtext mathvariant="italic">M</mtext></mrow><mrow><mtext mathvariant="italic">VBR</mtext></mrow></msub><msub><mrow><mtext>​</mtext></mrow><mrow><mtext>,</mtext><mtext mathvariant="italic">i</mtext></mrow></msub></mrow></mfrac></mrow></math><img file="EP0940952A2_D0010.tif" /></maths> where M_VBR the sum of the average bit rate of the VBR connections in a class and M_CBR specify the average bit rate for CBR connections.

An alternative approach to calculating the reduced service rate can be:<maths id="math0011" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><mtext mathvariant="italic">red</mtext></mrow></msub><msub><mrow><mtext>​</mtext></mrow><mrow><mtext>,</mtext><mtext mathvariant="italic">i</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">C</mtext><mtext> - </mtext><msub><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><mtext mathvariant="italic">CBR</mtext></mrow></msub><mtext> - </mtext><apply>&lt;sum /&gt;<lowlimit><mtext mathvariant="italic">k</mtext><mtext>= l </mtext><mtext mathvariant="italic">k</mtext><mtext>≠</mtext><mtext mathvariant="italic">i</mtext></lowlimit><uplimit><mtext mathvariant="italic">K</mtext></uplimit><mrow><mtext></mtext><msub><mrow><mtext mathvariant="italic">M</mtext></mrow><mrow><mtext mathvariant="italic">VBR</mtext></mrow></msub><msub><mrow><mtext>​</mtext></mrow><mrow><mtext>,</mtext><mtext mathvariant="italic">k</mtext></mrow></msub></mrow></apply></mrow></math><img file="EP0940952A2_D0011.tif" /></maths>

In the following, the first-mentioned approach for the reduced service rate will be considered. In the receiving station, the variables C_CBR, M_CBR, C_{VBR, k} and M_{VBR, k} (k = 1, ..., K; K is the number of classes) must be known or determined. When receiving a transmission request for a VBR connection with the parameters m_New and h_New the following process steps are carried out:<ul id="ul0001" list-style="none"><li>1. Determination of class k_New for the new connection by evaluating m_New and h_New.</li><li>Second Calculation of the reduced service rate C_red, k_New for class k_New according to the given equation.</li><li>Third Calculation of<img file="EP0940952A2_D0012.tif" /></li><li>4th Effective bandwidth calculation <maths id="math0012" num=""><math display="inline"><mrow><msub><mrow><mtext>c</mtext></mrow><mrow><mtext>New</mtext></mrow></msub><mtext> = c</mtext></mrow></math><img file="EP0940952A2_D0013.tif" /></maths> (m_New, H_New, C_red, k_New,<img file="EP0940952A2_D0014.tif" /> with the Lindberger formula.</li><li>5th If<maths id="math0013" num=""><math display="block"><mrow><msub><mrow><mtext>c</mtext></mrow><mrow><mtext>New</mtext></mrow></msub><msub><mrow><mtext> + C</mtext></mrow><mrow><mtext>CBR</mtext></mrow></msub><mtext> + </mtext><apply>&lt;sum /&gt;<lowlimit><mtext>k</mtext></lowlimit>&lt;uplimit /&gt;<mrow><msub><mrow><mtext> C</mtext></mrow><mrow><mtext>VBR, k</mtext></mrow></msub><mtext> ≤ C,</mtext></mrow></apply></mrow></math><img file="EP0940952A2_D0015.tif" /></maths> Accept connection, otherwise reject.</li><li>6th If the connection can be accepted, update from C_{VBR, k} and M_{VBR, k} (k = 1, ..., K).</li></ul>

The step 6 update is also required to reflect the impact on connections in other classes. If a connection is added or removed in another class, the effective bandwidths of all existing connections have to be recalculated and added up for each class to the value C_{VBR, k} to obtain. This procedure must be carried out as an iterative procedure until the variables C_{VBR, k} converge to their exact values. In practice, however, it is sufficient to carry out only a few iteration steps. The data must also be updated if a CBR connection is established instead of a VBR connection.

If a connection with the parameters m_rem and h_rem a procedure similar to that described above is performed. The effective bandwidth for the terminated connection is calculated and by C_{VBR, krem} subtracted for the class in question. M_{VBR, krem} is around m_rem reduced. Then an update of all C_{VBR, k}- Variables updated in the same way as for connecting.

As the effective bandwidth can be calculated very quickly with the Lindberger formula, the updates are not too time-consuming for a reasonable number of connections. However, a compromise must be found between the computing capacity and the accuracy of the bandwidth calculation. It may be justified not to update if the composition of the existing connections has not varied too much since the last update.

It may be sufficient to carry out the update calculations not at every connection change but at regular time intervals, which can result from a time lapse (eg every 30 s) or event-driven (for example after every 10 connections have been established or terminated).