RU2780659C1 - Method for quasi-optimal multimedia packet streaming based on the criteria of minimum delay and minimum relative loss due to buffer overflow - Google Patents

Abstract

FIELD: communications.

SUBSTANCE: invention relates to the field of communications. The method comprises the steps of: reserving all available bandwidth and buffer space in the router; packetizing multimedia data in a router with a fixed packet size, providing a minimum delay when using all the current reserved bandwidth, taking into account the addition of an overhead to each packet; determining and transmitting the current average speed and the standard deviation of the input stream speed, as well as the value of the Hurst exponent to the block for calculating the optimal redundancy parameters upon receipt of a stable value of the Hurst exponent with a deviation of not more than 0.05 or when the bundling plan is exhausted; the packetization plan is changed, reserved bandwidth and buffer space in the router to the optimal at the current time or allocate the entire available resource in case of lack of performance or buffer space; the process of adjusting the parameters of redundancy and bundling is started when the value of the Hurst exponent changes by more than 0.05 or when the bundling plan is exhausted.

EFFECT: minimization of delay and minimization of losses due to buffer overflow during the transmission of a real-time packetized multimedia stream in order to improve the quality of service of telecommunications traffic under congestion conditions by determining the optimal packetization plan with adaptive bandwidth and buffer space reservation.

1 cl, 1 dwg

Description

The invention relates to the field of optimizing the size of data packets and can be used to maximize the quality of service (QoS) in the transmission of bursty multimedia traffic.

The ability of this technical solution to work with any data transmission systems that support the mechanism of bandwidth and buffer space reservation, regardless of the compression algorithms used, as well as the possibility of two-criteria optimization in terms of minimizing the level of losses due to buffer overflow and minimizing transmission delay, allows you to use it practically in any modern packet multimedia transmission systems, which ensures its wide industrial applicability.

One of the features of modern data transmission systems is the wide distribution of multimedia traffic, which, as you know, is the most "heavy" and demanding on delay, jitter and data loss, and also has a long-term dependence.

Another feature is that packet protocols are widely used in data transmission systems. At the same time, an important point is the optimization of the packet size, since this directly affects the quality of service of telecommunication traffic and, in particular, the delay and loss due to denial of service.

The currently used mechanisms for ensuring the quality of service of telecommunications traffic most successfully cope with their functions in the absence of input stream ripples. In view of this, one of the approaches described in Jean-Yves Le Boudec and Patrick Thiran. Network Calculus: A Theory of Deterministic Queuing Systems for the Internet. Online Version, December, 2019 (pp. 155-173)" and designed to provide the highest quality of service for offline media transmission, is optimal lossless smoothing, but given the random nature of the available bandwidth, mechanisms of this kind are inefficient for transmission in mode real time, since it is not always possible to correctly estimate the bandwidth and buffer space required for a stream. Moreover, if redundant redundancy is carried out, this leads to inefficient use of network resources and oppression of other lower priority flows.

It should also be noted that most of the currently used real-time streaming video transmission protocols do not take into account the delay introduced by packetization and use packet sizes during transmission due to the characteristics of telecommunication equipment, and not the requirement for maximum quality of service. In the context of the proposed method, the maximum quality of service is understood as the minimum delay with a minimum loss due to buffer overflow.

Moreover, often the packet size for the transmission of all types of traffic in a particular system is fixed, or it is fixed within a particular flow and does not change during the current communication session (connection).

The methods described in RU 2459373, RU 2370907, RU 2601604, intended for packet data transmission, are focused on ensuring the compatibility of information exchange protocols or eliminating losses and implement various mechanisms for packetizing, routing or smoothing the input stream. At the same time, in these methods, the main emphasis is placed on the current state of the communication network, the delivery route, ensuring the absence of losses and the exclusion of jitter, which is random in nature and is not always correctly described by the applied mathematical models.

As a result, the analogous methods fail to minimize the delay caused by packetization while eliminating packet loss due to buffer overflows for media streaming in online and offline capable systems.

The closest in technical essence to the claimed method and selected as a prototype is the method described in Premal Shah, and Abhay Karandikar. Optimal Packet Length Scheduling for Regulated Media Streaming. IEEE COMMUNICATIONS LETTERS, VOL. 7 NO. 8, AUGUST 2003 (pp. 409-411).

The essence of this method lies in the fact that for a pre-recorded multimedia file, the optimal packaging plan is determined according to the criterion of minimum relative loss due to buffer overflow, and then transmission is started. For this:

1. Set the characteristics of the communication channel.

2. Determine the interval with the maximum relative losses (interval of maximum overloads).

At this step, by means of three nested loops, a complete enumeration of all possible intervals of splitting the analyzed input data vector is carried out and the interval with the largest relative loss is searched by successive comparison with reassignment. This interval corresponds to the period of time with the greatest congestion due to lack of bandwidth.

3. Make up the optimal packing plan for the section with the highest relative losses.

At this stage, the maximum possible residual bandwidth is determined at each discrete time point in the interval with maximum overload and a bundling plan is made that will use the entire bandwidth. The resulting size vector of the useful part of the packets allows you to use all the available bandwidth.

4. Check the condition for the absence of losses in the analyzed interval.

5. Skip the recursive call if there is no relative loss in the analyzed interval.

6. Compose an optimal packetization plan for the entire optimized transmission interval of the multimedia file.

7. Recalculate the residual capacity for the time preceding the start of the overload, if there are relative losses in the analyzed interval.

8. Recursively call the method for the interval to the left and right of the interval of maximum overloads.

9. A multimedia file packaged in accordance with the received plan is transmitted over the communication channel.

The prototype method has the following disadvantages.

1. Do not transmit multimedia in real time.

2. Do not use bandwidth and buffer space reservations, taking into account the statistical characteristics of the input stream.

3. Do not adapt the boundaries of the reservation to the current characteristics of the input stream.

4. Do not take into account the appearance of service traffic when bundling.

The problem that the proposed method solves is to maximize the quality of service of multimedia traffic by minimizing delay and minimizing losses due to input buffer overflow by determining the optimal packetization plan with adaptive bandwidth and buffer space reservation.

The technical result consists in minimizing delay and minimizing losses due to buffer overflow when transmitting a real-time packetized multimedia stream in order to improve the quality of service for telecommunications traffic under congestion conditions by determining the optimal packetization plan with adaptive bandwidth and buffer space reservation.

Graphic materials used to illustrate the proposed solution:

fig. 1 is a flowchart of a method for quasi-optimal streaming multimedia packet transmission according to the criterion of minimum delay and minimum relative loss due to buffer overflow;

fig. 2 is a plot of the relative loss for various packet size scheduling policies.

The figure 1 shows a functional diagram of the method of quasi-optimal multimedia streaming packet transmission according to the criterion of minimum delay and minimum relative loss due to buffer overflow, which includes the following elements:

1. Router.

2. Media source.

3. Statistics analysis block.

4. Multimedia receiver.

5. Block for calculating optimal redundancy parameters.

6. A block for compiling a quasi-optimal packetization plan for the data accumulated in the buffer.

To solve the problem of maximizing the quality of service of multimedia traffic, a method is proposed for quasi-optimal packet streaming of multimedia according to the criterion of minimum delay and minimum relative loss due to buffer overflow, which consists in the following:

1. Reserve all available bandwidth and buffer space in Router 1.

2. Start transmitting multimedia data from media source 2 to router 1 and statistics analysis unit 3.

3. Multimedia data is packetized in router 1 with a fixed packet size that provides a minimum delay when using all the current reserved bandwidth, taking into account the addition of an overhead to each packet.

Moreover, the size of the useful part of the package is set in accordance with the expression of the form

where: r _in - input stream rate, l _sl - packet overhead size, r _out - maximum reserved output interface rate (router throughput).

4. Start transmitting packetized media data from router 1 to media sink 4.

5. In the statistics analysis block 3, the average speed and standard deviation of the input stream speed, as well as the Hurst index for the function of the volume of multimedia data per unit time, are determined using the normalized range method.

6. The current average speed and the standard deviation of the input stream speed, as well as the value of the Hurst exponent are transmitted to the block for calculating the optimal redundancy parameters 5 upon receipt of a stable value of the Hurst exponent with a deviation of not more than 0.05 or when the bundling plan is exhausted.

7. Calculate the optimal throughput and the amount of buffer space in block 5 required for reservation with a minimum loss due to buffer overflow, taking into account the current value of the Hurst exponent.

At the same time, the following expressions are used to calculate the optimal reserved bandwidth and buffer space:

- средняя скорость входного потока,

- оценка СКО скорости входного потока; Н - показатель Харста входного потока; N_пак - число пакетов принятых от источника мультимедийных данных на текущий момент времени;

- максимальный размер пакета принятого от источника мультимедийных данных на текущий момент времени.where:

- average input flow rate,

- RMS estimation of the input flow rate; H is the Hurst index of the input stream; N _pack - the number of packets received from the source of multimedia data at the current time;

- the maximum packet size received from the source of multimedia data at the current time.

8. The optimal values of throughput and buffer size are transmitted to the block for compiling a quasi-optimal bundling plan 6.

9. A recursive algorithm for optimal scheduling of packet lengths is used according to the criterion of minimum relative losses for the data accumulated in the input buffer of the router. A packetization plan is a table of packet sizes for each discrete moment in time. Wherein:

determine the interval with maximum relative losses (interval of maximum overloads);

make up the optimal bundling plan for the section with the highest relative losses;

check the condition of the absence of losses in the analyzed interval;

a recursive call is skipped if there is no relative loss in the analyzed interval;

make up an optimal packetization plan for the entire optimized transmission interval of the multimedia fragment;

recalculate the residual capacity for the time preceding the start of the overload, if there are relative losses in the analyzed interval;

carry out a recursive call of the algorithm for the interval to the left and to the right of the interval of maximum relative overloads.

10. Send to router 1 new reservation parameters and packetization plan for the data accumulated in the buffer.

11. Change the packetization plan, reserved bandwidth, and buffer space in Router 1 to be optimal at the current time, or allocate the entire available resource in the event of a lack of performance or buffer space.

12. Continue to transmit multimedia data, taking into account the optimal packetization plan and reservation parameters.

13. The process of adjusting the reservation and bundling parameters is started when the value of the Hurst exponent changes by more than 0.05 or when the bundling plan is exhausted in the block for calculating the optimal parameters of the reservation 5.

In this case, steps (5-12) are repeated.

The "industrial applicability" of the method is due to the possibility of implementing it using both programmable integrated circuits and program-controlled telecommunications equipment.

Comparison of the claimed method of quasi-optimal streaming multimedia packet transmission according to the criterion of minimum delay and minimum relative loss due to buffer overflow with the prototype shows that the claimed method differs significantly from the prototype.

General features of the proposed method and prototype:

1. A recursive algorithm for optimal scheduling of packet lengths is used according to the criterion of minimum relative losses.

2. Set the characteristics of the communication channel.

3. A packetized multimedia stream according to the received plan is transmitted over the communication channel.

Distinctive features of the proposed solution.

1. Read the multimedia transmission without using the preview of the entire file, but in near real-time mode.

2. Reserve all available bandwidth and buffer space in the router when starting a transmission.

3. Multimedia data is packetized in a router with a fixed packet size, which ensures a minimum delay when using all the current reserved bandwidth, taking into account the addition of an overhead to each packet, until an optimal packetization plan is drawn up using a recursive algorithm.

4. Make up an optimal packetization plan for the data accumulated in the input buffer, and not for the entire transmitted data fragment.

5. Combine the batching mechanism with a fixed batch size and using a batching plan depending on the availability of data in the input buffer.

6. Change the reserved bandwidth and buffer space, taking into account the statistical characteristics of the input stream, ensuring a minimum loss due to buffer overflow.

Thus, the claimed method of quasi-optimal multimedia packet streaming according to the criterion of minimum delay and minimum relative losses due to buffer overflow, allows minimizing the packetization delay and losses due to input buffer overflow, while taking into account the emerging service traffic.

To ensure the ability to work with online and offline streams, two packaging mechanisms are implemented. One uses a fixed packet size to minimize latency, and the other uses variable packet length packetization to minimize buffer overflow losses.

The introduction of a redundancy mechanism into the proposed method, which takes into account the fractal properties of the input stream, and its combination with the mechanism of recursive optimal scheduling of packet lengths according to the criterion of minimum relative losses, made it possible to reduce the consequences caused by the inadequacy of the applied mathematical models and obtain a significant increase in the quality of service for pulsating real-time multimedia streams in conditions of unstable behavior of the communication network.

Moreover, the use of expressions (2) and (3) when calculating the reserved bandwidth and buffer space allows minimizing the buffer and, therefore, reducing the latency.

Claims (1)

A method for quasi-optimal packet streaming of multimedia according to the criterion of minimum delay and minimum relative losses due to buffer overflow, which consists in the following: reserve the entire resource of the router; start transmitting the media data from the media source to the router and the statistics analysis unit; packetizing the multimedia data in the router; start transmitting the packetized media data from the router to the media receiver; determine the parameters of the input stream; transmitting the parameters of the input stream to the block for calculating the optimal parameters of the reservation; calculate the optimal redundancy parameters; transmitting the optimal reservation parameters to a quasi-optimal bundling plan compiler; use a recursive algorithm for optimal scheduling of packet lengths according to the criterion of minimum relative losses; change the bundling plan and reservation parameters; continue to transmit multimedia data, taking into account the optimal packetization plan and reservation parameters; start the process of adjusting the parameters of reservation and packetization, characterized in that: reserve all available bandwidth and buffer space in the router; packetizing multimedia data in a router with a fixed packet size, providing a minimum delay when using all the current reserved bandwidth, taking into account the addition of an overhead to each packet; determine in the statistics analysis block the average speed and the standard deviation of the speed of the input stream, as well as the Hurst exponent for the function of the amount of multimedia data per unit time by the normalized range method; transmitting the current average speed and the standard deviation of the input stream speed, as well as the value of the Hurst exponent to the block for calculating the optimal redundancy parameters upon receipt of a stable value of the Hurst exponent with a deviation of not more than 0.05 or when the bundling plan is exhausted; calculate the optimal throughput and the amount of buffer space required for reservation with a minimum loss due to buffer overflow, taking into account the current value of the Hurst exponent; using a recursive algorithm for optimal scheduling of packet lengths according to the criterion of minimum relative losses, for the data accumulated in the input buffer of the router; change the packetization plan, reserved bandwidth and buffer space in the router to the optimal at the current time or allocate the entire available resource in case of lack of performance or buffer space; start the process of adjusting the reservation and bundling parameters when the value of the Hurst exponent changes by more than 0.05 or when the bundling plan is exhausted.

Images