RU2832625C1 - Method for optimal formation of link layer frame for fractal aggregated traffic in multiservice data network based on criterion of minimum end-to-end delay - Google Patents

Abstract

FIELD: information technology.

SUBSTANCE: invention relates to means of optimizing placement in a single frame of a link layer of several network layer packets. Technical result is achieved by finding the optimal size of the useful part of the Ethernet frame using the residual service model and smoothing the residual service curve, used to find the optimal solution analytically with subsequent successive approximation to compensate for the smoothing error.

EFFECT: reduced delay when transmitting a fractal aggregated stream in order to improve transmission quality.

1 cl, 2 dwg

Description

The invention relates to the field of optimizing the size of data packets and can be used to minimize end-to-end delay during transmission of pulsed multiplexed traffic taking into account the Hurst index of each microflow included in the aggregate by optimizing the placement of several network layer packets in a single channel layer frame.

This technical solution is primarily intended for dynamic determination of the optimal Ethernet frame size and minimization of end-to-end delay in multiservice data transmission networks, by forming a channel-level frame from several IP packets, which allows the proposed method to be used in virtually any packet data transmission systems and ensures its wide industrial applicability.

The analysis of the information exchange allows us to conclude that there is a significant number of Ethernet frames that are significantly smaller than the maximum possible size of 1500 bytes. As is known, the use of small frames results in the appearance of a large amount of redundant service information, 26 bytes per frame, where: preamble (7 bytes), initial frame delimiter (1 byte), destination MAC address (6 bytes), source MAC address (6 bytes), network protocol type (2 bytes), frame check sequence (4 bytes). It is also necessary to take into account the interpacket interval, corresponding to 12 bytes. This leads to inefficient use of network bandwidth. On the other hand, when the size of the useful part is too large in relation to the service part, this leads to a significant increase in the delay in the transmission of low-speed traffic, due to the need for long-term accumulation of data for a full-size frame. In addition, when servicing fractal aggregated traffic, the use of the assumption of its Poisson distribution for constructing mathematical models and determining the optimal Ethernet frame size is inadequate to the real input flow, which leads to an increase in the end-to-end delay indicator and exceeding the requirements for quality of service (QoS) during data transmission. Moreover, the presence of microflows in the aggregated flow that have different origins and, as a consequence, different fractal characteristics significantly reduces the accuracy of estimating the required bandwidth resources.

This necessitates the use of technical solutions capable of packaging the input stream with an optimal Ethernet frame size, taking into account the fractal properties of each of the microstreams included in the aggregate according to the criterion of minimum end-to-end delay, when ensuring the quality of service of fractal aggregated traffic.

A method and device are known from the prior art that implement a change in packet lengths for transmissions with a high packet data rate (RU patent No. 2341903, 2004). For this purpose, multiple security level (SL) packets can be multiplexed into a single PL packet to increase efficiency, while the SL packets can have variable lengths. In one embodiment, SL packets of different formats for different users are combined into capsules that form a PL packet. Shorter packets are intended for users with poor channel conditions or requiring a smaller amount of data due to the application and associated quality of service (QoS) requirements.

Disadvantages of this technical solution:

1. Select the packet size from a list of predetermined values based on the requested transmission rate.

2. Select the packet size regardless of the traffic flows running parallel to the flow under consideration.

3. They do not take into account the possibility of transmitting traffic through several telecommunications nodes.

4. They do not take into account the performance of telecommunication devices.

5. The fractality of the flow is not taken into account when packaging.

Also known is the Device for calculating the optimal packet size based on the criterion of the minimum difference between the delay and the message transmission time (RU patent No. 203223, 2022). This device allows implementing a method for calculating the optimal packet size based on the criterion of the minimum difference between the delay and the message transmission time.

Disadvantages of this technical solution:

1. When calculating the packet size, the characteristics of traffic flows running parallel to the flow under consideration are not taken into account.

2. When calculating the packet size, the characteristics of all intermediate nodes along the flow route are not taken into account.

3. They do not take into account possible pulsations in the input flow and available bandwidth.

The closest in technical essence to the claimed method and chosen as a prototype is the Method for minimizing delay in the guaranteed transmission of a packetized smoothed stream of digital compressed images (patent RU No. 2764784, 2021).

The essence of this method is to maximize the quality of service of multimedia traffic by minimizing delays and minimizing losses due to overflow of the input buffer, by determining the optimal packetization plan with adaptive reservation of bandwidth and buffer space. To do this, in the prototype method:

1. Set the input stream parameters.

2. Set the parameters of traffic processing devices.

3. Form the curve of the incoming flow.

4. Form a service curve for the communication network.

5. Calculate the minimum playback delay.

6. Determine the optimal size of the useful part of the package.

7. Configure the communication network.

8. Calculate the minimum buffer size.

9. Configure the playback device.

10. Transmit a frame-by-frame stream.

11. Smooth out the flow.

12. They split the stream of compressed images into packets and transmit them over a communication channel.

13. Receive the stream via the communication channel and transmit it to the decoder.

14. Decompress the stream and transmit it to the playback device.

15. Play the stream.

The prototype method has the following disadvantages.

1. When transmitting traffic, the impact of other traffic flows (cross-flows) on telecommunications devices is not taken into account.

2. They do not take into account the individual fractal properties of each of the microflows included in the unit.

3. Do not form Ethernet frames from several IP packets.

4. Repackaging of primary data is performed.

5. Transmit only multimedia traffic.

The problem solved by the proposed method is to minimize the end-to-end delay in the transmission of fractal aggregated traffic, taking into account the fractality of the microflows participating in the aggregation, by determining the optimal size of the Ethernet frame and forming it from several IP packets.

The technical result consists in reducing the delay in transmitting a fractal aggregated flow in order to improve the quality of transmission, due to finding the optimal size of the useful part of the Ethernet frame using a residual service model and smoothing the residual service curve used to find the optimal solution analytically with subsequent successive approximation to compensate for the smoothing error.

The functioning of the invention is explained by the following graphic materials:

Fig. 1 - functional diagram of the Method for optimal formation of channel level frames for fractal aggregated traffic in a multiservice data transmission network based on the criterion of minimum end-to-end delay;

Fig. 2 - dependence of the maximum end-to-end delay on the size of the useful part of the packet when transmitting a fractal aggregated flow.

Figure 1 shows a functional diagram of the Method for optimal formation of channel-level frames for fractal aggregated traffic in a multiservice data transmission network based on the criterion of minimum end-to-end delay, which includes the following elements:

1. Information exchange control server.

2. Source of fractal aggregated traffic.

3. Packaging device.

4. Receiver of fractal aggregated packetized stream.

5. Block for calculating the optimal size of the useful part of the Ethernet frame.

To solve the stated problem, a Method for optimal formation of channel-level frames for fractal aggregated traffic in a multiservice data transmission network is proposed based on the criterion of minimum end-to-end delay, which consists in the fact that:

1. Continuously collect statistics in real time about the network structure and transmitted flows on the server 1 for monitoring information exchange based on packet interception, routing algorithms and bandwidth reservation, as well as monitoring the buffer load of telecommunication devices.

2. The entire input stream is transmitted from the source 2 of the fractal aggregated traffic through the packaging device 3 to the recipient 4 of the fractal aggregated packetized stream, taking into account the current optimal size of the Ethernet frame, the useful part of which at the initial moment in time is taken to be equal to the size of the network layer packet.

3. Collect statistics on input Ethernet frames (arrival time, size, source, recipient and traffic type) in the packaging device 3 and transmit it to the block 5 for calculating the optimal size of the useful part of the Ethernet frame.

4. In block 5 for calculating the optimal size of the useful part of the Ethernet frame, the statistics of the information exchange are analyzed and the Hurst index, the estimate of the mathematical expectation and the standard deviation of the intensity of the input flow in real time for the current volume of statistics are determined.

5. In block 5 for calculating the optimal size of the useful part of the Ethernet frame, the total average speed of the entire aggregated flow is determined for the future, taking into account the current fractality of its microflows.

In this case, a mathematical model of fractal flow aggregation is used, for each group of flows with equal values of the Hurst index, separately implemented by the invention (Sytsevich N.F., Belov P.Yu., Miroshnik K.S., Method of reserving bandwidth for aggregated fractal traffic with adaptation to the current load. Patent No. 2804500 dated 02.10.2023).

The following theoretical principles are used in constructing a mathematical model.

From the theory of self-similar processes, a mathematical model of time scaling of a fractal process is known, which in the context of telecommunication traffic transmission can be represented as follows:

where H is the Hurst index of telecommunication traffic, a is the scale factor, x(⋅) is the volume of traffic received during time (⋅). We will reason as follows.

Let us represent the volume of traffic x(t) received by the system during time t through the data transfer rate:

Where - average speed of telecommunication traffic.

It is obvious that for the union of flows the following expression is valid:

where x ₁ (t), x ₂ (t), …, x _n (t) is the volume of traffic received during time t for each of the n flows participating in the aggregation, and the corresponding data receipt rates.

Let us perform elementary algebraic transformations of the right-hand side of expression (3), showing how much the total average speed of all flows will exceed the speed of the first flow. As a result, expression (3) will take the form:

If we assume that the flows x ₁ , x ₂ , …, x _n , have the same Hurst exponent H, then can be considered as a time scale factor for the first flow. Thus, taking into account expression (2), the following mathematical model of fractal flow aggregation is valid

If, similarly to expression (2), we represent the left-hand side of expression (5) as then the data receipt rate for the aggregated flow, after elementary algebraic transformations (5), can be described by an expression of the form:

Then it is necessary to sum the calculated velocities for all groups of flows with equal values of the Hurst exponent. This allows us to obtain - the total average speed of the entire flow.

6. In block 5, the calculation of the optimal size of the useful part of the Ethernet frame is determined, the burstiness for the curve of receipt of aggregated traffic.

In this case, the traffic arrival curve is understood as a function of time that describes the dependence of the total amount of received data and has the form:

Where:

M - maximum size of Ethernet frame in a stream;

P - peak flow rate;

b - permissible burstiness of the flow, determined by the product of the maximum size of the Ethernet frame in the flow M by the number of microflows in the unit;

- stable average flow rate.

7. Request data on the network structure and the flows transmitted in it from the information exchange control server 1 to the block 5 for calculating the optimal size of the useful part of the Ethernet frame.

8. In block 5 for calculating the optimal size of the useful part of the Ethernet frame, the parameters of the residual service curve on the route of the aggregated traffic are calculated.

In this case, the following provisions of the theory of deterministic network calculus are used.

Network calculus is a set of mathematical results that allow one to study the boundary values of the characteristics of the functioning of such complex technical systems as communication networks, digital electrical circuits, competing programs, etc. Network calculus provides a theoretical basis for the analysis of the guaranteed performance of telecommunication packet networks, in contrast to the theory of queuing, which operates mainly with average values of indicators.

To construct a residual service curve on the route of a traffic aggregate, it is necessary to construct the curves of arrival of flows (cross-flows) passing through the telecommunications equipment through which the analyzed traffic aggregate (cross-flows) passes. where F is the cross-flow aggregate, an is the number of aggregates), as well as the service curves of this telecommunications equipment.

The service curve is defined by the parameters: R - the traffic processing speed and T - the maximum delay of the bit stream in the device and has the form:

After finding the traffic arrival curves for all cross-flows and the service curves of telecommunications equipment along the route of the traffic aggregate, it is necessary to find the residual service curves of these traffic processing devices by finding the pointwise difference of the equipment service curves and the sum of all cross-traffic aggregates passing through it:

Where: - the residual service curve of the traffic processing device S on the route of the unit, β _(s) - the service curve of the traffic processing device S on the route of the unit, - the curve of cross-flow arrival on the route of the traffic aggregate, n is the number of cross-flows passing through device S.

Then, a min+convolution of the resulting residual service curves is performed. all service devices along the unit's route:

Where: - the residual service curve provided by the communication network for the target traffic aggregate, - residual service curve of the traffic processing device on the route of the unit, m - the number of traffic processing devices on the route of the unit.

9. Calculate the optimal size of the Ethernet frame in block 5 for calculating the optimal size of the useful part of the Ethernet frame.

The following theoretical principles are used.

To optimize the size of the useful part of the Ethernet frame according to the criterion of minimum end-to-end delay, it is necessary to calculate this delay. In network calculus, for the above types of arrival curve and the curve of the type "rate-delay" (service curve), the formula for calculating the maximum delay of the bit stream in the node is known:

However, (11) does not take into account the delay time for the formation of one Ethernet frame, which can be defined as the ratio of the frame size (which consists of L _pl - the size of the useful part of the frame and L _sl - the size of the service part of the frame) to the speed of traffic processing by the device:

Also not taken into account is the increase in peak flow rate (P) when using small frames, due to the increase in redundancy caused by the appearance of a larger amount of service data. It is possible to take into account this increase in P by introducing the coefficient:

Substituting expressions (13) and (12) into (11), we obtain the expression:

Since the delay function of the useful part size of an Ethernet frame has an extremum (Fig. 2 - dependence of the maximum end-to-end delay on the useful part size of a frame when transmitting a fractal aggregate flow), the search for a solution for calculating the optimal useful part size of an Ethernet frame is reduced to finding the value of L _pl at which the first derivative of expression (14) is equal to zero. As a result of cumbersome algebraic transformations, the solution is as follows:

However, the residual service curve of the nodes of telecommunication equipment obtained by us for the target aggregate of fractal traffic of interest will not always be of the "speed-delay" type. The residual service curve can have the form of a multi-stage pseudo-affine curve. In this case, the maximum frame delay over time t is determined as:

Calculating the delay for each possible Ethernet frame payload size and then comparing them using expression (15) can take an unacceptably long time.

This can be avoided in the following way.

Let us reduce the residual service curve obtained for the traffic aggregate of interest to the "speed-delay" form by averaging. To do this, we add up all the curve values that are not equal to 0 and divide by the number of such values, obtaining the average service speed. Substituting this speed into expression (8), we obtain the average residual service curve of the nodes of telecommunications equipment for the target fractal traffic aggregate of interest. Substituting its parameters into expression (15), we can find a quasi-optimal solution.

Having calculated the quasi-optimal solution, we find the optimal solution on the set of integers using the method of successive approximations.

To do this, we find d _max when the useful part size of the Ethernet frame is 1 byte larger than the quasi-optimal value obtained earlier. If the obtained value of d _max is smaller than that obtained with the calculated quasi-optimal frame size, we continue to increase the useful part size of the Ethernet frame until the value of d _max starts to increase. If the value of d _max increases with the first increase in the useful part size of the Ethernet frame, then to find the optimal solution, we decrease the useful part size of the Ethernet frame by 1 byte. We repeat this action until d _max starts to increase. If, with the initial increase in the useful part size of the Ethernet frame, and then with the initial decrease in the useful part, the values of d _max exceed the already calculated one, then the solution found is already optimal.

This approach allows to significantly reduce computational costs and the time for finding the optimal solution compared to a complete enumeration of the size of the useful part of the Ethernet frame and the application of expression (16) for each iteration.

10. The value of the optimal size of the useful part of the Ethernet frame obtained in block 5 for calculating the optimal size of the useful part of the Ethernet frame is transmitted to the packaging device 3.

11. Form Ethernet frames from several IP packets in the device 3 for packaging in accordance with the order of priority servicing of IP packets and equality to the optimal size of the Ethernet frame.

In this case, in general, the size of the Ethernet frame will differ from the optimal one. The decision to place the next IP packet into the frame is made based on the criterion of the minimum modulus of the difference between the optimal and the generated Ethernet frame according to an expression of the form

If the received modules are equal, the next IP packet is included in the Ethernet frame, since the function d _max of the size of the useful part of the Ethernet frame increases at a lower rate with an increase in the argument (Fig. 2).

12. Perform continuous adaptation of the Ethernet frame size to the current statistics of the input stream.

The “industrial applicability” of the method is determined by the possibility of implementing it using both programmable integrated circuits and a program in the operating system of the corresponding telecommunications equipment (controlled switch, router, etc.).

A comparison of the claimed Method for optimal formation of a channel-level frame for fractal aggregated traffic in a multiservice data transmission network based on the criterion of minimum end-to-end delay with the prototype shows that the claimed method differs significantly from the prototype.

General features of the claimed method and prototype:

1. Use deterministic network calculus algebraic analysis approaches to determine end-to-end delay.

2. Take into account the fractal nature of the transmitted telecommunication traffic.

3. Use a packaging mechanism.

4. Transmit and receive a packet stream.

5. Take into account the characteristics of the input flow.

6. Take into account the characteristics of the data transmission channel. Distinctive features of the proposed solution.

1. Take into account the fractal nature of each microflow included in the target aggregate of flows.

2. Perform averaging of the residual service curve to reduce the time to find the optimal Ethernet frame size.

3. Using the method of successive approximations, find the optimal Ethernet frame size for the real arrival curve.

4. Form an Ethernet frame from several IP packets.

5. A decision is made about placing the next IP packet into the frame based on the criterion of the minimum modulus of the difference between the optimal and the generated Ethernet frame.

6. Transmit any type of traffic.

7. Adapt the Ethernet frame size to the state of the communication channel in near real time.

Thus, the claimed Method of optimal formation of a channel-level frame for fractal aggregated traffic in a multiservice data transmission network according to the criterion of minimum end-to-end delay allows minimizing the end-to-end delay of delivery of telecommunication traffic taking into account the time for the formation of one Ethernet frame and taking into account the increase in the peak flow rate when using small-sized frames, due to the increase in redundancy caused by the appearance of a larger amount of service data. At the same time, adaptability is ensured.

Claims (1)

A method for optimally forming a data link layer frame for fractal aggregated traffic in a multiservice data transmission network based on the criterion of minimum end-to-end delay, comprising the following: continuously collecting statistics on the network structure and transmitted flows on the information exchange control server; transmitting all input traffic through the packetizing device to the recipient; collecting statistics on input Ethernet frames in the packetizing device; analyzing the information exchange statistics in the block for calculating the optimal size of the useful part of the Ethernet frame and determining the Hurst index, an estimate of the mathematical expectation and the standard deviation of the intensity of the input flow in real time for the current volume of statistics; determining the total average speed of the entire aggregated flow in the block for calculating the optimal size of the useful part of the Ethernet frame; determining the burstiness for the aggregated traffic arrival curve in the block for calculating the optimal size of the useful part of the Ethernet frame; requesting data on the network structure and the flows transmitted in it from the information exchange control server. calculate in the block for calculating the optimal size of the useful part of the Ethernet frame the parameters of the residual service curve on the route of the aggregated traffic; form Ethernet frames in the packaging device; perform continuous adaptation, characterized in that: transmit all the input traffic from the source through the packaging device to the recipient taking into account the current optimal size of the Ethernet frame, the useful part of which at the initial moment in time is taken to be equal to the size of the network layer packet; collect in the packaging device statistics on the time of receipt, size, source, recipient and type of traffic of the input Ethernet frame and transmit it to the block for calculating the optimal size of the useful part of the Ethernet frame; determine in the block for calculating the optimal size of the useful part of the Ethernet frame the total average speed of the entire aggregated flow for the future taking into account the current fractality of its microflows; calculate in the block for calculating the optimal size of the useful part of the Ethernet frame the optimal size of the Ethernet frame; transmit to the packaging device the value of the optimal size of the useful part of the Ethernet frame; Form frames from several IP packets in the Ethernet packetization device in accordance with the order of priority servicing of IP packets and equality to the optimal Ethernet frame size; continuously adapt the Ethernet frame size to the current statistics of the input stream.