RU2849161C1 - Method for fair queue management taking into account distance metrics and a device for implementing it - Google Patents

Abstract

FIELD: digital information.

SUBSTANCE: inventions relate to means of fair queue service taking into account distance metrics in transport network routers. The technical result is achieved by additionally including from 1 to n modules for fair packet service, taking into account distance metrics, designed with the possibility of "fair distribution" of the output port bandwidth for variable-length packets, taking into account distance metrics, where each fair packet service module with distance metrics includes a virtual queue module, a GPS scheduler, a random number generator, a module for calculating the distance between alternative packet service options, and a packet scheduler with distance metrics.

EFFECT: reduction in the size of the buffer space allocated for the packet scheduler to operate.

3 cl, 8 dwg

Description

Field of technology

This invention relates to the field of telecommunications and, in particular, to ensuring quality of service in routers (switches) of a transport communications network.

State of the art

For the convenience of describing the method of fair queue servicing taking into account the distance metric and the device implementing it, we introduce a number of definitions.

By data traffic flow we mean the volume of information (Gbit, Tbit, etc.) transmitted through a communications network (routers/switches) over a given period by a single source. Essentially, a data traffic flow is a sequence of protocol data units from router to router or from one personal computer to another.

Protocol data unit (PDU) is a block of data transmitted between logical objects of the same level (see GOST 24402-88).

The scheduler is an algorithm for dividing processor time using “packets scheduling” (see Kucheryavy E.A. Traffic management and quality of service on the Internet. - St. Petersburg. Science and Technology, 2004. - 149 p.).

An active queue is a queue in which at least one packet is stored (see Kucheryavy E.A. Traffic management and quality of service on the Internet. - St. Petersburg. Science and Technology, 2004. - 153 p.).

The head of the queue is the packet that was placed into the queue before other packets in the queue.

The tail of the queue is a packet that was placed into the queue later than other packets in the queue.

The current step of packet servicing is the state of the scheduler at the current moment in time when the packet is transmitted to the output port for servicing (see Kucheryavy E.A. Traffic management and quality of service on the Internet. - St. Petersburg. Science and Technology, 2004. - 153 p.).

The next step of packet servicing is the scheduler state when it is necessary to make a decision about transmitting the next packet to the output port for servicing (see Kucheryavy E.A. Traffic management and quality of service on the Internet. - St. Petersburg. Science and Technology, 2004. - 152 p.).

The end of packet service is the point in time when the last bit of the total packet size will be transmitted into the communication channel of the router (switch) output port.

With the development of the global Internet and the provision of a wide range of multimedia services to users, ensuring quality of service (QoS) for network traffic is an important issue. When ensuring quality of service in IP-based transport networks, multiple data traffic flows have different quality of service requirements and, accordingly, divide the resources of the transport network router. Today, the Internet most commonly uses differentiated service, which allows for the "fair" distribution of transport network router resources among individual traffic classes and ensures priority service for certain traffic segments. Differentiated service involves dividing all traffic into several classes based on the service requirements of each.

A modern packet-switched transport network consists of multiple nodes (routers, switches, hosts, etc.) connected by communication channels. Each router has from 1 to n input ports, to which incoming communication channels are connected, and from 1 to n output ports, to which outgoing communication channels are connected. A router is a shared resource in the transport network. A well-known problem is the allocation of a limited number of shared resources (buffer memory and output port bandwidth) to competing users, services, applications, and classes of service. Queue scheduling controls access to a fixed amount of output port bandwidth by selecting the next packet to be transmitted to the router's output port. Many different queue scheduling disciplines exist, each attempting to find the right balance between complexity, control, and fairness.

The queuing discipline supported by router (switch) vendors is implementation-specific, meaning there are no real industry standards. However, vendors sometimes refer to their own implementation as a standard. The difficulty with recognizing any implementation as a standard is that each vendor combines features from several well-known common queuing disciplines to provide the common functionality their customers need to manage egress port congestion. Difficulties arise when packets arrive at an egress port faster than they can be transmitted. This means the router's egress port is considered congested. The delay caused by congestion can range from the time required to transmit the last bit of a previously arrived packet to infinity, in which case the packet is dropped due to lack of space in the memory buffer (queue). It's important to minimize the number of congested communication channels in the network, as congestion reduces network throughput, increases end-to-end packet delays, causes jitter, and can lead to packet loss if the buffer memory is insufficient to hold all packets awaiting transmission. The router module that implements the queue servicing procedure is called the scheduler.

Early routers used a First-in, First-out (FIFO) scheduler on each output port, with packets placed in a single queue. When a new packet arrives, it is placed at the end of the queue, and until the queue is empty, the router forwards packets from the queue, accepting the packet at the head of the queue (i.e., accepting the "oldest" packet). FIFO thus provides a simple best-effort service for all applications. FIFO has several serious drawbacks. First, a "greedy source" that sends packets at an extremely high bit rate can crowd out other sources and obtain more link capacity than other sources. Second, if several shorter packets are behind a long packet, the FIFO scheme results in a higher average delay (per packet) than if the shorter packets were transmitted before the longer packet. Third, under the FIFO scheme, there are no mechanisms to ensure quality of service for data traffic from high-priority, delay-sensitive sources, such as multimedia traffic.

A priority queuing (PQ) scheduler can be used to ensure latency guarantees. In a classic PQ scheduler, packets are first classified by the system and then placed into various priority queues. Packets are only picked up for service from a queue if all higher-priority queues are empty. Within each priority queue, packets are serviced in FIFO order. The advantage of this scheduler is its simplicity of implementation and the ability to ensure low latency for high-priority data traffic. A disadvantage is the inability to prevent flows from interfering with each other. If high-priority data traffic continually enters a queue at a high rate, data traffic entering other queues will be blocked.

To ensure fair prioritization of the scheduler's access to queues, the GPS (Generalized Processor Sharing) scheduler was developed. It ensures continuous-time fair resource allocation for variable-length packets. The GPS algorithm is an ideal model that ensures continuous-time fair resource allocation in accordance with the max-min criterion for traffic classes with different quality-of-service requirements. The GPS scheduler provides each flow with a guaranteed bit rate (throughput) and fairly distributes excess bandwidth among flows according to their relative bandwidth weights (see E.A. Kucheryavy, Traffic Management and Quality of Service on the Internet. St. Petersburg: Science and Technology, 2004, 152 p.).

It's worth noting that the GPS scheduler cannot be implemented in real hardware, as it assumes the GPS scheduler processes one bit per clock cycle (processor quantum). However, within the router itself, it is possible to virtually simulate a GPS server in continuous time and use these results to select the next packet.

A fairly accurate approximation of the GPS scheduler can be achieved using Weighted Fair Queuing (WFQ). The WFQ scheduler maintains fair bandwidth allocation for variable-length packets by approximating the generalized GPS processor sharing system (see E.A. Kucheryavy, "Traffic Management and Quality of Service on the Internet," St. Petersburg: Nauka i Tekhnika, 2004, 152 p.).

Serving packets in a separate WFQ queue This occurs in the order in which it arrives. Each arriving packet is placed at the end of the corresponding WFQ queue, provided that there is free space in that queue; otherwise, the packet is discarded.

The WFQ scheduler implements the following algorithm:

- generates a list of competing packets using the list of packets served by the virtual queuing system (GPS scheduler) and the numbers of packets at the beginning of the active WFQ queues;

- sorts the list of competing packets using the GPS end-of-service time field and the order relation;

- selects a packet from the WFQ queue using the packet number located at the beginning of the list of competing packets.

The selected packet is sent to the egress port for servicing. After the egress port has fully served the packet, the WFQ scheduler selects the next packet for servicing in accordance with the previously described algorithm (see Kucheryavy E.A. Traffic management and quality of service on the Internet. - St. Petersburg. Science and Technology, 2004. - 152 p.).

It's worth noting that network equipment documentation often states that it implements the WFQ algorithm. However, this doesn't necessarily mean it implements the algorithm discussed above; it likely implements a simpler scheduler. This is because WFQ is often used to refer to a whole class of algorithms that approximate GPS (see E.A. Kucheryavy, "Traffic Management and Quality of Service on the Internet," St. Petersburg: Science and Technology, 2004, 152 p.).

A serious challenge for the WFQ scheduler is that GPS modeling can predict that multiple packets may end up with the same virtual end time. Updating the virtual end time function between two successive packet arrivals can require a large amount of computation and buffer space. Specifically, if N active sessions (data traffic flows) are simultaneously transmitted on a link, updating the virtual end time can entail O(N) sessions or queues. The number of active flows can be very large. For example, there may be tens of thousands or even hundreds of thousands of queues sharing a single link. This leads to a proportionally large amount of computation and memory. This problem is called iterative deletion.

Due to the high complexity associated with modeling the GPS system, various solutions to this problem have been proposed in recent years. Many methods have been proposed to simplify the virtual time calculations. Some of these methods include self-clocked fair queuing (SCFQ), virtual clock (VC), start-time fair queuing (SFQ), frame-based fair queuing (FFQ), minimum-delay self-clocked fair queuing (MD-SCFQ), and discrete-rate scheduling (DR). In general, such simplifying approaches lead to reduced fairness (flow isolation) or increased delay bounds, or do not solve the repeated deletion problem.

A "Weighted Fair Service Scheduler" (US Patent 7,461,159 B2, December 2, 2008) is known. It uses GPS modeling to determine the servicing order of objects and employs a new dynamic data structure with a complex yet simple pointer update mechanism. Preferred scheduler variants perform a fixed amount of work per scheduling event. A scheduling event can be either the calculation of a new virtual completion timestamp upon a new entry into the scheduler or the determination of which objects should leave the GPS system because their completion timestamp has expired. Such a scheduler can be used for scheduling packets in a packet processing device such as a router (switch), scheduling access of software processes to a computer processor, etc. The scheduler can implement a weighted fair queue (WFQ).

A device known as a "General Weighted Fair Queue (WFQ) Generator" (US Patent No. 8,638,664 B2, filed January 28, 2014) includes a port, a buffer, a flow control module, and a service differentiation module. The port is configured to send and receive packets, and the port is connected to a network entity. The buffer is configured to store packets. The flow control module is configured to control the transmission of packets within the network device. A service differentiation module is connected to the buffer and the flow control module. The service differentiation module is configured to regulate the storage of packets in the buffer and to regulate the transmission of packets from the network device to the network entity. The service differentiation module is also configured to determine excess bandwidth available within the network device and to allocate the excess bandwidth for the transmission of packets to the network entity.

A method and device “Method for probabilistic priority servicing of queues and a device implementing it” (RU Patent No. 2776658 C1 dated July 22, 2022) are known, which consists in setting a weight for each intermediate queue, receiving priority data traffic flows at the input ports of the router, classifying priority data traffic flows into classes in accordance with the ToS Precedence field of the IP packet header, or in accordance with the DSCP field of the IP packet header, or in accordance with the DSCP field of the IP packet header, routing priority data traffic flows to the corresponding output ports of the router based on the routing table, placing priority data traffic packets of the corresponding class in an intermediate queue in accordance with the original ToS Precedence field of the IP packet header, or in accordance with the original DSCP field of the IP packet header, measuring the arrival rate of priority data traffic flows of the corresponding class and the average length of packets of the corresponding class, form a table of correspondence between the flow identifier and the ToS Precedence field of the IP packet header, or in accordance with the DSCP field of the IP packet header, or with the DSCP field of the IP packet header, form a matrix of intervals taking into account the rate of arrival of priority data traffic flows, the average length of packets and the weight for each intermediate queue, generate a random number uniformly distributed in the interval from 0 to 1, change the original priority of the packet in the DSCP field of the IP packet header, or in the ToS Precedence field of the IP packet header, taking into account the matrix of intervals and the random number, transfer the packet to the priority queue in accordance with the modified ToS Precedence field of the IP packet header, or in accordance with the modified DSCP field of the IP packet header, place data traffic packets of the corresponding class at the end of the corresponding priority queue in accordance with the modified ToS Precedence field of the IP packet header, or in accordance with the modified DSCP field of the IP packet header, service packets in priority queues by the scheduler with PQ priorities, restore the original packet priority in the DSCP field of the IP packet header, or in the ToS Precedence field of the IP packet header taking into account the correspondence matrix, and transmit priority data traffic to the output port of the router.

A method and device for "Method of Probabilistic Weighted Fair Queue Servicing" (RU Patent No. 2777035 C1 dated 01.08.2022) are known, which consists in the fact that at the first stage, an absolute weight is established for each queue, the rate of receipt of priority data traffic flows and the average packet size for each priority data traffic flow, all variants (combinations) of active queues are formed, a service intensity vector (WM) is calculated for each variant (combination) of active queues, a service intensity interval vector (IntWM) is formed for each service intensity vector, at the second stage, priority data traffic flows are received at the input ports of the device, priority data traffic flows are classified into classes in accordance with the ToS Precedence field of the IP packet header, or in accordance with the DSCP field of the IP packet header, or in accordance with the DSCP field of the IP packet header, and priority data traffic flows are routed to the corresponding output ports of the router based on the table routing, place data traffic packets of the corresponding class in a queue in accordance with the ToS Precedence field of the IP packet header, or in accordance with the DSCP field of the IP packet header, or in accordance with the DSCP field of the IP packet header, check the current state of the output port of the device, check the presence of packets in the queues, if the queues are not empty, then form a vector of active queues, select a vector of service intensity intervals taking into account the vector of active queues, generate a random number uniformly distributed in the interval from 0 to 1, select the number of the active queue taking into account the random number and the vector of service intensity intervals (IntWM), transmit the packet to the output port of the device, update the current state of the output port of the device. A probabilistic weighted fair queuing device comprising from 1 to n input ports for receiving flows of priority data traffic, a classifier configured to classify data traffic flows in accordance with a ToS Precedence field of an IP packet header, or in accordance with a DSCP field of an IP packet header, or in accordance with a DSCP field of an IP packet header, a routing module configured to forward a packet to an output port in accordance with a routing table, from 1 to n queuing modules for placing packets in a queue of the corresponding class in accordance with a ToS Precedence field of an IP packet header, or in accordance with a DSCP field of an IP packet header, or in accordance with a DSCP field of an IP packet header; measuring the rate of arrival of data traffic and the average length of packets of the corresponding class, from 1 to n output ports for transmitting streams of priority data traffic into the communication channel, characterized in that from 1 to n modules of probabilistic weighted fair queuing are additionally included, wherein the streams of priority data traffic are received at the input ports, then from the input ports the streams of priority data traffic are transmitted to the input of the classifier, the output of the classifier is connected to the input of the routing module, from the output of the routing module the streams of priority data traffic are received at the input of the corresponding queuing module, from the output of the queuing module the streams of priority data traffic are transmitted to the corresponding module of probabilistic weighted fair queuing, from the output of the module of probabilistic weighted fair queuing the streams of priority data traffic are received at the output ports.

The closest in technical essence to the claimed method and chosen as a prototype is the "Method for performing weighted queuing scheduling using a set of fairness coefficients" (patent US 10291540 B2 dated 05/14/2019), which consists in receiving packet data from multiple source ports; classifying packet data based on multiple source ports and their associated destination ports; sorting packet data into multiple queues in a buffer; scheduling each of a plurality of queues for transmission based on a temporary weight of each of the plurality of queues that is calculated based on a set of fairness factors, wherein the set of fairness factors includes: a validity bit of the corresponding queue, a priority weight of the corresponding queue, an identification of a first position indicating the position of the corresponding queue, and an identification of a second position indicating the position of the last scheduled queue with the highest priority from the previous round, the scheduling further includes selecting from at least two queues with the same maximum priority weight, and wherein an additional amount is added to the temporary weight of the corresponding queue if the identification of the first position indicates a lower position than the identification of the second position, and wherein the additional amount is equal to the number of queues selected from the at least two queues with the same maximum priority weight; and updating the static state of the corresponding queue from among the plurality of queues responsive to a data packet being input into the corresponding queue or output from the corresponding queue; sending the output packet data removed from the scheduler queue to the destination.

The closest in technical essence to the claimed device and selected as a prototype is the "Device for performing weighted scheduling of queues using a set of fairness coefficients" (patent US 10291540 B2 dated 05/14/2019), containing at least one processor and at least one tangible non-transitive machine-readable storage medium storing instructions that, when executed by at least one processor, cause the device to perform a method of using a scheduler to process requests, including: receiving packet data from multiple source ports; classifying packet data based on multiple source ports and destination ports associated with them; sorting packet data into multiple queues in a buffer; scheduling each of a plurality of queues for transmission based on a temporary weight of each of the plurality of queues that is calculated based on a set of fairness factors, wherein the set of fairness factors includes: a validity bit of the corresponding queue, a priority weight of the corresponding queue, an identification of a first position indicating the position of the corresponding queue, and an identification of a second position indicating the position of the last scheduled queue with the highest priority from the previous round, the scheduling further includes selecting from at least two queues with the same maximum priority weight, and wherein the temporary weight of the corresponding queue is increased by an additional amount if the identification of the first position indicates a lower position than the identification of the second position, and wherein the additional amount is equal to the number of queues selected from the at least two queues with the same maximum priority weight; and updating the static state of the corresponding queue from among multiple queues responsive to a data packet being input into the corresponding queue or output from the corresponding queue; and sending the output packet data removed from the scheduler queue to the destination.

A technical issue is the large buffer space required for the packet scheduler. This is because the scheduler requires storing the virtual service time of the GPS server (scheduler), as well as the packet numbers stored in the queues.

The technical result consists in reducing the size of the buffer space allocated for the operation of the packet scheduler, due to the fact that from 1 to n modules of fair packet servicing taking into account the distance metric are additionally included, configured with the possibility of "fair distribution" of the throughput of the output port for packets of variable length taking into account the distance metric, wherein each module of fair packet servicing taking into account the distance metric includes a virtual queue module, a GPS scheduler, a random number generator, a module for calculating the distance between alternative packet servicing options, a packet scheduler taking into account the distance metric.

The creation of a method for fair queue servicing taking into account the distance metric and the device implementing it are aimed at solving this technical problem, which makes it possible to reduce the size of the buffer space allocated for the operation of the packet scheduler.

Disclosure of invention

In the claimed method, this technical problem is solved by the fact that in the method of fair queuing taking into account the distance metric, which consists in the fact that at the first stage they set for each output port devices the total number of queues, the maximum number of packets in each queue, the throughput, the share of throughput allocated to the schedulers taking into account the distance metric, the weight for each queue, the parameters of the random early detection mechanism RED for each queue, at the second stage receive data traffic flows on the input ports of the device, classify the data traffic flows into classes in accordance with the ToS Precedence field of the IP packet header, or in accordance with the DSCP field of the IP packet header, the source IP address, the destination IP address, or in accordance with such parameters as the protocol, access lists and the input interface, route the data traffic flows to the corresponding output ports of the device based on the routing table and the destination IP address, or based on the forwarding table and the MPLS label, place data traffic packets of the corresponding class into physical queues in accordance with the ToS Precedence field of the IP packet header, or in accordance with the DSCP field of the IP packet header, the source IP address, the destination IP address, or in accordance with such parameters as protocol, access lists and input interface, while the packet is placed at the end of the corresponding queue, provided that there is free space in this queue (Drop Tail mechanism) and the RED mechanism does not discard the packet in case of congestion detection, otherwise the packet is removed, data traffic packets of the corresponding class are placed in virtual queues in accordance with the ToS Precedence field of the IP packet header, or in accordance with the DSCP field of the IP packet header, the source IP address, the destination IP address, or in accordance with such parameters as protocol, access lists and input interface, while the packet is placed at the end of the corresponding virtual queue, provided that there is free space in this virtual queue (Drop Tail mechanism) and the RED mechanism does not discard the packet in case of congestion detection, otherwise the packet is removed, the current state of the output port and the virtual output port of the device, as well as the state of the GPS scheduler and the packet scheduler taking into account the distance metric are checked for the end of servicing the packet by the output port or the virtual output port at the current moment time, select a packet that is located at the beginning of the active virtual queue, the packet from which was serviced at the current moment in time, for servicing at the next step, transmit the packet and the weight of the corresponding queue to the virtual output port of the device, form a vector of the number of packets standing in virtual queues at the current servicing step, form a vector of the number of packets standing in physical queues at the current servicing step, form a vector of alternative options for the number of packets standing in physical queues at the next servicing step, calculate the distance metric between each element of the vector of alternative options for the number of packets standing in physical queues at the next servicing step and the vector of the number of packets standing in virtual queues at the current servicing step, select an element or elements from the vector of alternative options for the number of packets standing in physical queues at the next servicing step with the smallest distance metric, split the interval from 0 to 1 into a number of identical ranges equal to the number of selected elements from the vector of alternative options for the number of packets standing in physical queues at the next servicing step with the same distance metric, generate a random a number uniformly distributed in the interval from 0 to 1, select the range number into which the generated random number falls, select the packet that is located at the beginning of the corresponding physical queue for servicing at the next step with the smallest distance metric and taking into account the selected range number, transmit the packet to the output port of the device.

The new set of essential features makes it possible to achieve the specified technical result by placing data traffic packets of the corresponding class into physical queues in accordance with the ToS Precedence field of the IP packet header, or in accordance with the DSCP field of the IP packet header, the sender IP address, the recipient IP address, or in accordance with such parameters as the protocol, access lists and the input interface, while the packet is placed at the end of the corresponding queue, provided that there is free space in this queue (Drop Tail mechanism) and the RED mechanism does not discard the packet in the event of overload detection, otherwise the packet is deleted, placing data traffic packets of the corresponding class into virtual queues in accordance with the ToS Precedence field of the IP packet header, or in accordance with the DSCP field of the IP packet header, the sender IP address, the recipient IP address, or in accordance with such parameters as the protocol, access lists and the input interface, while the packet is placed at the end of the corresponding virtual queue, provided that there is free space in this virtual queue ( Drop Tail) and the RED mechanism does not discard a packet if an overload is detected, otherwise the packet is deleted, check the current state of the output port and the virtual output port of the device, as well as the state of the GPS scheduler and the packet scheduler taking into account the distance metric for the end of servicing the packet by the output port or the virtual output port at the current time, select a packet that is located at the beginning of the active virtual queue from which the packet was serviced at the current time for servicing at the next step, transmit the packet and the weight of the corresponding queue to the virtual output port of the device, form a vector of the number of packets standing in virtual queues at the current servicing step, form a vector of the number of packets standing in physical queues at the current servicing step, form a vector of alternative options for the number of packets standing in physical queues at the next servicing step, calculate the distance metric between each element of the vector of alternative options for the number of packets standing in physical queues at the next servicing step and the vector of the number of packets standing in virtual queues at the current servicing step, select an element or elements from the vector of alternative options for the number of packets standing in physical queues, at the next step of service with the smallest distance metric, the interval from 0 to 1 is divided into a number of identical ranges equal to the number of selected elements from the vector of alternative options for the number of packets standing in physical queues, at the next step of service with the same distance metric, a random number is generated, uniformly distributed in the interval from 0 to 1, the number of the range into which the generated random number falls is selected, a packet located at the beginning of the corresponding physical queue is selected for service at the next step with the smallest distance metric and taking into account the selected range number, the packet is transmitted from the beginning of the corresponding physical queue to the output port of the device.

In order to achieve the above object, in accordance with another aspect of the present invention, a distance metric based fair queueing device is provided.

In the claimed device, this problem is solved in that the device for fair queuing, taking into account the distance metric, contains from 1 to n input ports for receiving data traffic flows, a classifier configured to assign data traffic flows to classes in accordance with the ToS Precedence field of the IP packet header, or in accordance with the DSCP field of the IP packet header, the sender IP address, the recipient IP address, or in accordance with such parameters as the protocol, access lists and the input interface, a routing module configured to forward a packet to an output port in accordance with the routing table and the recipient IP address, or on the basis of the forwarding table and the MPLS label, from 1 to n physical queuing modules for placing packets in a queue of the corresponding class in accordance with the ToS Precedence field of the IP packet header, or in accordance with the DSCP field of the IP packet header, the sender IP address, the recipient IP address, or in accordance with such parameters as the protocol, access lists and the input interface; Setting the weight for each queue; Setting the parameters of the random early congestion detection mechanism RED for each queue, from 1 to n output ports for transmitting data traffic flows to the communication channels. Additionally, the device for fair queuing with respect to the distance metric includes from 1 to n modules of fair packet servicing with respect to the distance metric, configured to "fairly distribute" the output port bandwidth for variable-length packets with respect to the distance metric, wherein the data traffic flows arrive at the input ports, then from the input ports the data traffic flows are transmitted to the input of the classifier, the output of the classifier is connected to the input of the routing module, from the output of the routing module the data traffic flows arrive at the input of the corresponding physical queuing module, from the output of the physical queuing module the data traffic flows are transmitted to the corresponding module of fair packet servicing with respect to the distance metric, from the module of fair packet servicing with respect to the distance metric the data traffic flows arrive at the output ports.

According to one particular embodiment, the module for fair packet servicing taking into account the distance metric comprises a virtual queuing module configured to place packets in virtual queues that correspond to physical queues for the corresponding classes, a GPS scheduler configured to implement in continuous time the principle of "fair resource distribution" for variable-length packets, a random number generator configured to generate a random number uniformly distributed in the interval from 0 to 1, a module for calculating the distance between alternative packet servicing options, configured to generate a vector of the number of packets standing in virtual queues at the current servicing step; generating a vector of the number of packets standing in physical queues at the current servicing step; generating a vector of alternative options for the number of packets standing in physical queues at the next servicing step; calculating the distance metric between each element of the vector of alternative options for the number of packets standing in physical queues at the next servicing step and the vector of the number of packets standing in virtual queues at the current servicing step; selecting an element or elements from a vector of alternative options for the number of packets standing in physical queues at the next servicing step with the smallest distance metric; dividing the interval from 0 to 1 into a number of identical ranges equal to the number of selected elements from the vector of alternative options for the number of packets standing in physical queues at the next servicing step with the same distance metric; selecting the number of the range into which the generated random number falls, a packet scheduler taking into account the distance metric, configured to; select a packet that is located at the beginning of the corresponding physical queue for servicing at the next step with the smallest distance metric, taking into account the selected range number; transmitting the packet to the output port with the implementation of the principle of "fair servicing" of queues taking into account the distance metric, wherein all modules in the device are connected via a common internal AXI4 bus, which acts as a means of exchanging information between the modules.

All modules can be implemented according to a well-known scheme, for example, the Eltex ME 5000 router (see https://eltex-co.ru/catalog/provider_edge_router/marshrutizator_me5000).

A new set of essential features makes it possible to achieve the specified technical result by additionally introducing 1 to n modules of fair packet servicing taking into account the distance metric, wherein each module of probabilistic weighted fair queue servicing contains a GPS scheduler, a random number generator, a module for calculating the distance between alternative packet servicing options, and a packet scheduler taking into account the distance metric.

An analysis of the state of the art revealed that there are no comparable inventions with a set of features identical to all the features of the claimed method for fair queue management using distance metrics and the device implementing it. Consequently, each of the claimed inventions meets the patentability requirement of "novelty."

A search of prior art in this and related fields of technology to identify features that match the distinctive features of the claimed invention revealed that these features are not clearly evident from the prior art. The prior art also failed to reveal any prior art knowledge of the impact of the transformations envisaged by the essential features of the claimed invention on achieving the stated technical result. Consequently, each of the claimed inventions meets the patentability requirement of "inventive step."

“Industrial applicability” is determined by the presence of an elementary base on which the device and the given method can be made to achieve the result specified in the invention.

To more clearly illustrate the technical solutions according to the embodiments of the present invention, a brief description of the accompanying drawings is given below.

Fig. 1 shows the operation diagram of the fair queue service method taking into account the distance metric (start).

Fig. 2 shows a diagram of the operation of the method of fair queue servicing taking into account the distance metric (continued).

Fig. 3 shows a device for fair queue service taking into account the distance metric.

Fig. 4 shows a diagram of a fair packet service module taking into account the distance metric.

Fig. 5 shows the principle of placing packets in a physical/logical queue of class k.

Fig. 6 shows an example of the implementation of two queues in the physical queue module and the virtual queue module.

Fig. 7 shows an example of a class 1 packet arriving at the physical queue module.

Fig. 8 shows an example of a class 1 packet arriving at the virtual queue module.

Below, the technical solutions for embodiments of the present invention will be fully and clearly described with reference to the accompanying drawings. It should be obvious that the embodiments described below are only a part of the present invention, and not all possible embodiments of the present invention. All other embodiments obtained by those skilled in the art based on the embodiments of the present invention and not using a creative approach fall within the scope of protection of the present invention.

The implementation of the claimed method is as follows (Fig. 1-2).

The first stage

101. Installed for each output port devices total number of queues, maximum number of packets in each queue, throughput, share of throughput allocated to schedulers taking into account the distance metric, weight for each queue, parameters of the random early congestion detection mechanism RED for each queue.

The second stage

102. Receive data traffic streams to the input ports of the device.

103. Classify data traffic flows into classes according to the ToS Precedence field of the IP packet header, or according to the DSCP field of the IP packet header, the source IP address, the destination IP address, or according to parameters such as protocol (TCP, UDP, etc.), access lists (Access List), and input interface (FastEthernet 10/100 Base-T, GigabitEthernet).

104. Route data traffic flows to the appropriate router output ports based on the Routing Table and the destination IP address, or based on the Forwarding Table and the MPLS label.

105. Data traffic packets of the corresponding class are placed in physical queues in accordance with the ToS Precedence field of the IP packet header, or in accordance with the DSCP field of the IP packet header, the sender IP address, the recipient IP address, or in accordance with such parameters as the protocol (TCP, UDP, etc.), access lists (Access List) and the input interface (FastEthernet 10/100 Base-T, GigabitEthernet), while the packet is placed at the end of the corresponding queue (Fig. 5) provided that there is free space in this queue (Drop Tail mechanism) and the RED mechanism does not discard the packet in the event of overload detection, otherwise the packet is deleted.

106. Data traffic packets of the corresponding class are placed in virtual queues in accordance with the ToS Precedence field of the IP packet header, or in accordance with the DSCP field of the IP packet header, the sender IP address, the recipient IP address, or in accordance with such parameters as the protocol (TCP, UDP, etc.), access lists (Access List) and the input interface (FastEthernet 10/100 Base-T, GigabitEthernet), and the packet is placed at the end of the corresponding virtual queue (Fig. 5) provided that there is free space in this virtual queue (Drop Tail mechanism) and the RED mechanism does not discard the packet in the event of overload detection, otherwise the packet is deleted.

107. Check the current state of the output port and the virtual output port of the device, as well as the state of the GPS scheduler and the packet scheduler taking into account the distance metric for the end of packet servicing by the output port or the virtual output port at the current time.

108. Select the one located at the beginning of the active virtual queue for servicing at the next step.

109. Transmit the packet and the weight of the corresponding queue to the virtual output port of the device.

110. Form a vector of the number of packets standing in virtual queues at the current service step.

For example, three queues are configured. The first virtual queue stores two packets, the second virtual queue stores one packet, and the third virtual queue stores three packets. In this case, the vector of the number of packets in the virtual queues is .

111. Form a vector of the number of packets standing in physical queues at the current service step.

For example, three queues are configured. The first physical queue stores two packets, the second physical queue stores one packet, and the third physical queue stores three packets. In this case, the vector of the number of packets in the physical queues is It is worth noting that the vector of the number of packets standing in virtual queues at the current service step may not correspond to the vector of the number of packets standing in physical queues at the current service step.

112. A vector of alternative numbers of packets in physical queues at the next servicing step is formed. The number of alternative numbers of packets in physical queues at the next servicing step is equal to the number of active queues.

For example, for the above-considered vectors, the vector of alternative variants of the number of packets standing in physical queues at the next step of service will consist of 3 vectors - , , .

113. Calculate the distance metric between each element of the vector of alternative options for the number of packets standing in physical queues at the next service step and the vector of the number of packets standing in virtual queues at the current service step.

The distance metric chosen in the claimed method is a parametric metric on the Minkowski Euclidean space.

,

Where - vector of the number of packets standing in physical queues at the current service step; - a vector of alternative variants of the number of packets standing in physical queues at the next step of service; - a parameter that determines the type of metric. It is worth noting that when - Hemingway distance, at - the Euclidean distance, and when - Chebyshev distance.

114. Select an element or elements from the vector of alternative options for the number of packets standing in physical queues at the next service step with the smallest distance metric.

For example, for each alternative number of packets standing in physical queues, at the next service step (step 112), a distance metric with the parameter is calculated (Euclidean metric). We obtain the following values: for the vector metrics , for vector metrics , for vector metrics Therefore, two alternative options will be chosen. And .

115. The interval from 0 to 1 is divided into a number of identical ranges equal to the number of selected elements from the vector of alternative options for the number of packets standing in physical queues at the next service step with the same distance metric.

Since at step 114 for two alternative options for the number of packets standing in physical queues, at the next step of servicing the distance metric is the same, then the interval from 0 to 1 is divided into two intervals: , .

116. Generate a random number uniformly distributed between 0 and 1.

Example: generated number 0.75.

117. Select the number of the range that contains the generated random number.

Example: Since the random number 0.75 was generated, the second range is selected. .

118. Select the packet that is located at the beginning of the corresponding physical queue for servicing at the next step with the smallest distance metric and taking into account the selected range number.

For example, a packet is selected from the third queue, which corresponds to an alternative number of packets standing in physical queues at the next service step. .

119. Transmit the packet from the beginning of the corresponding physical queue to the output port of the device.

Example: Space in the third queue (free buffer space) is freed up in accordance with the length of the transmitted packet.

The claimed method of fair servicing of queues taking into account the distance metric makes it possible to achieve the specified technical result - a decrease in the size of the buffer space allocated for the operation of the packet scheduler due to the fact that data traffic packets of the corresponding class are placed in physical queues in accordance with the ToS Precedence field of the IP packet header, or in accordance with the DSCP field of the IP packet header, the sender IP address, the recipient IP address, or in accordance with such parameters as the protocol, access lists and the input interface, while the packet is placed at the end of the corresponding queue, provided that there is free space in this queue (Drop Tail mechanism) and the RED mechanism does not discard the packet in the event of overload detection, otherwise the packet is deleted, data traffic packets of the corresponding class are placed in virtual queues in accordance with the ToS Precedence field of the IP packet header, or in accordance with the DSCP field of the IP packet header, the sender IP address, the recipient IP address, or in accordance with such parameters as the protocol, access lists and the input interface, while the packet is placed at the end of the corresponding virtual queue, provided that there is free space in this virtual queue (Drop Tail mechanism) and the RED mechanism does not discard the packet in case of overload detection, otherwise the packet is deleted, the current state of the output port and the virtual output port of the device is checked, as well as the state of the GPS scheduler and the packet scheduler taking into account the distance metric for the end of servicing the packet by the output port or the virtual output port at the current moment in time, the packet located at the beginning of the active virtual queue is selected for servicing at the next step, the packet and the weight of the corresponding queue are transmitted to the virtual output port of the device, a vector of the number of packets standing in virtual queues is formed at the current servicing step, a vector of the number of packets standing in physical queues is formed at the current servicing step, a vector of alternative options for the number of packets standing in physical queues is formed at the next servicing step, the distance metric is calculated between each element of the vector of alternative options for the number of packets standing in physical queues at the next servicing step and the vector of the number of packets standing in virtual queues at the current servicing step, an element or elements are selected from a vector of alternative options for the number of packets standing in physical queues at the next service step with the smallest distance metric, the interval from 0 to 1 is divided into a number of identical ranges equal to the number of selected elements from the vector of alternative options for the number of packets standing in physical queues at the next service step with the same distance metric, a random number is generated uniformly distributed in the interval from 0 to 1, the number of the range into which the generated random number falls is selected, the packet located at the beginning of the corresponding physical queue is selected for servicing at the next step with the smallest distance metric and taking into account the selected range number, the packet is transmitted from the beginning of the corresponding physical queue to the output port of the device.

The device for fair queuing with regard to the distance metric (Fig. 3) consists of from 1 to n input ports, a classifier 21, a routing module 22, from 1 to n physical queue modules 23, from 1 to n modules for fair servicing of packets with regard to the distance metric 24, from 1 to n output ports, wherein the data traffic flows arrive at the input ports, then from the input ports the data traffic flows are transmitted to the input of the classifier, the output of the classifier is connected to the input of the routing module, from the output of the routing module the data traffic flows arrive at the input of the corresponding physical queue module, from the output of the physical queue module the data traffic flows are transmitted to the corresponding module for fair servicing of packets with regard to the distance metric, from the module for fair servicing of packets with regard to the distance metric the data traffic flows arrive at the output ports.

Input ports 1 to n are configured to receive data traffic streams.

The classifier 21 is configured to classify data traffic flows according to the ToS Precedence field of the IP packet header, or according to the DSCP field of the IP packet header, the source IP address, the destination IP address, or according to parameters such as protocol, access lists, and input interface.

Routing module 22, configured to forward a packet to an output port in accordance with a routing table (Routing Table) and the recipient IP address, or based on a forwarding table (Forwarding Table) and an MPLS label.

The physical queue modules 23 (from 1 to n) are configured to place packets at the end of the queue of the corresponding class in accordance with the ToS Precedence field of the IP packet header, or in accordance with the DSCP field of the IP packet header, the source IP address, the destination IP address, or in accordance with such parameters as protocol, access lists, and input interface; setting the weight for each queue; setting the parameters of the random early congestion detection mechanism RED for each queue.

Output ports 1 to n are configured to transmit data traffic streams to communication channels.

Distance-metric-based fair packet handling modules 24 (from 1 to n) designed to "fairly distribute" the output port bandwidth for variable-length packets based on the distance metric.

Each module of fair packet service taking into account the distance metric 24 contains a module of virtual queues 24.1, a GPS scheduler 24.2, a packet scheduler taking into account the distance metric 24.3, a random number generator 24.4, a module for calculating the distance between alternative packet service options 24.5, and all modules in the device are connected via a common internal AXI4 bus, which acts as a means of exchanging information between the modules.

The virtual queue module 24.1 is configured to place packets at the end of a virtual queue that corresponds to a physical queue of the corresponding class.

The GPS 24.2 scheduler is designed to implement continuous-time "fair resource sharing" for variable-length packets.

The 24.3 distance-based packet scheduler is designed to implement "fair distribution" of the output port bandwidth for variable-length packets based on the distance metric and to forward the packet from the beginning of the corresponding physical queue to the output port of the device.

The random number generator 24.4 is configured to generate a random number uniformly distributed in the range from 0 to 1.

The module for calculating the distance between alternative options for servicing packets 24.5 is configured to form a vector of the number of packets standing in virtual queues at the current servicing step; to form a vector of the number of packets standing in physical queues at the current servicing step; to form a vector of alternative options for the number of packets standing in physical queues at the next servicing step; to calculate the distance metric between each element of the vector of alternative options for the number of packets standing in physical queues at the next servicing step and the vector of the number of packets standing in virtual queues at the current servicing step; to select an element or elements from the vector of alternative options for the number of packets standing in physical queues at the next servicing step with the smallest distance metric; to split the interval from 0 to 1 into a number of identical ranges equal to the number of selected elements from the vector of alternative options for the number of packets standing in physical queues at the next servicing step with the same distance metric; to select the number of the range into which the generated random number falls.

All modules can be implemented according to a well-known scheme, for example, the Eltex ME 5000 router (see https://eltex-co.ru/catalog/provider_edge_router/marshrutizator_me5000).

The device works as follows.

At the first stage, the fair queueing device is configured taking into account the distance metric, namely, it is set for each output port devices total number of queues, maximum number of packets in each queue (modules 23, 24.1), throughput, share of throughput allocated for schedulers taking into account the distance metric (modules 24.2, 24.3), weight for each queue (modules 23, 24.1), parameters of the random early congestion detection mechanism RED for each queue (modules 23, 24.1).

At the second stage, priority data traffic flows are received at the router's input ports and then transmitted to the classifier. In classifier 21, data traffic flows are classified into classes according to the ToS Precedence field of the IP packet header, or according to the DSCP field of the IP packet header, the source IP address, the destination IP address, or according to parameters such as protocol (TCP, UDP, etc.), access lists (Access List), and input interface (FastEthernet 10/100 Base-T, GigabitEthernet). After classifier 21, data traffic flows enter the routing module, where packets are forwarded to the corresponding output ports of the device based on the routing table (Routing Table) and the destination IP address, or based on the forwarding table (Forwarding Table) and the MPLS label to the corresponding physical queue module 23 and virtual queue module 24.1. In the physical queue module 23, data traffic packets of the corresponding class are placed into physical queues in accordance with the ToS Precedence field of the IP packet header, or in accordance with the DSCP field of the IP packet header, the source IP address, the destination IP address, or in accordance with parameters such as protocol, access lists, and input interface, and the packet is placed at the end of the corresponding queue, provided that there is free space in this queue (Drop Tail mechanism) and the RED mechanism does not discard the packet if congestion is detected, otherwise the packet is deleted. In the virtual queue module 24.1, data traffic packets of the corresponding class are placed into virtual queues in accordance with the ToS Precedence field of the IP packet header, or in accordance with the DSCP field of the IP packet header, the source IP address, the destination IP address, or in accordance with parameters such as protocol, access lists and input interface, and the packet is placed at the end of the corresponding virtual queue, provided that there is free space in this virtual queue (Drop Tail mechanism) and the RED mechanism does not discard the packet in case of congestion detection, otherwise the packet is deleted.

In the fair packet service module, taking into account the distance metric 24, the state of the device's virtual output port is checked, as well as the state of the GPS scheduler 24.2, for the end of packet servicing by the virtual output port at the current time.

In the module for fair packet servicing taking into account the distance metric 24, the state of the device's output port is checked, as well as the state of the packet scheduler taking into account the distance metric 24.3 for the end of packet servicing by the output port at the current time. In the GPS scheduler module 24.2, a packet located at the beginning of the active virtual queue is selected for servicing at the next step and this packet and the weight of the corresponding queue are transmitted to the virtual output port of the device. In the module for calculating the distance between alternative servicing options 24.5, a vector of the number of packets standing in virtual queues at the current servicing step is formed; a vector of the number of packets standing in physical queues at the current servicing step. After this, in the module for calculating the distance between alternative servicing options 24.5, a vector of alternative options for the number of packets standing in physical queues is formed at the next servicing step and the distance metric is calculated between each element of the vector of alternative options for the number of packets standing in physical queues at the next servicing step and the vector of the number of packets standing in virtual queues at the current servicing step. Next, the distance calculation module 24.5 selects an element or elements from the vector of alternative options for the number of packets standing in physical queues at the next service step with the smallest distance metric and divides the interval from 0 to 1 into a number of identical ranges equal to the number of selected elements from the vector of alternative options for the number of packets standing in physical queues at the next service step with the same distance metric. After this, the random number generator 24.4 generates a random number uniformly distributed in the interval from 0 to 1 and transmits this value to the distance calculation module 24.5. In the distance calculation module 24.5, the range number in which the generated random number falls is selected and this information is transmitted to the packet scheduler, taking into account the distance metric 24.3. In the packet scheduler, taking into account the distance metric 24.3, a packet is selected that is located at the beginning of the corresponding physical queue for servicing at the next step with the smallest distance metric and, taking into account the selected range number, the packet is transmitted from the beginning of the corresponding physical queue to the output port of the device.

Thanks to a new set of essential features, the specified technical result is achieved due to additionally introduced from 1 to n modules of fair packet servicing taking into account the distance metric, configured with the possibility of “fair distribution” of the throughput of the output port for packets of variable length taking into account the distance metric, wherein each fair packet servicing taking into account the distance metric 24 contains a virtual queue module 24.1, a GPS scheduler 24.2, a packet scheduler taking into account the distance metric 24.3, a random number generator 24.4, a module for calculating the distance between alternative packet servicing options 24.5.

Interactive process of operation of the method of fair queuing taking into account the distance metric and the device implementing it

At the first stage

For each output port the devices in the physical queue module 23 and the virtual queue module 24.1 set the number of queues to 2, the maximum number of packets in the class 1 queue is 4 packets, the maximum number of packets in the class 2 queue is 2 packets (Fig. 6), the weight of the class 1 queue is 0.7, the weight of the class 2 queue is 0.3, the parameters of the RED mechanism for all queues are as follows:- the lower threshold of the queue length is equal to the upper threshold of the queue length and is equal to the queue length, i.e. for a class 1 queue - 4 packets, for a class 2 queue - 2 packets,- the maximum value of packet drop probability for the area between And is equal to 0, i.e. packets are dropped due to the lack of free space in the queue; the throughput of all output ports FastEthernet 10/100 Base-T is 100 Mbps; the share of the throughput allocated to the GPS scheduler 24.2 and the packet scheduler taking into account the distance metric 24.3 is 0.95 (95% of the total throughput of the port).

At the second stage

Receive data traffic flows to the input ports of the FastEthernet 10/100 Base-T device. Then, in classifier 21, classify the data traffic flows into classes in accordance with the ToS Precedence field of the IP packet header, or in accordance with the DSCP field of the IP packet header, the source IP address, the destination IP address, or in accordance with such parameters as the protocol (TCP, UDP, etc.), access lists (Access List), and the input interface (FastEthernet 10/100 Base-T). After this, in routing module 22, the data traffic flows are routed to the corresponding output ports of FastEthernet 10/100 Base-T based on the routing table (Routing Table) and the destination IP address, or based on the forwarding table (Forwarding Table) and the MPLS label to the corresponding physical queue module 23 and virtual queue module 24.1.

Assume that there are currently two packets in the Class 1 physical queue, and one packet in the Class 2 physical queue. A Class 1 packet arrives at physical queue module 23. Since there is free space in the Class 1 physical queue, the packet is placed in the queue. As a result, there are three packets in the Class 1 physical queue, and one packet remains in the Class 2 physical queue (Fig. 7).

In virtual queue module 24.1, there is currently a second packet in the first-class virtual queue, and two packets in the second-class virtual queue. Accordingly, when a first-class packet arrives, it is placed in the first-class virtual queue because there is free space. As a result, there are three packets in the first-class virtual queue, and two packets remain in the second-class virtual queue (Fig. 8).

In the distance-based fair packet service module, the state of the device's virtual output port and the state of GPS scheduler 24.2 are checked to determine whether the virtual output port has currently finished servicing the packet. In the distance-based fair packet service module, the state of the device's output port and the state of GPS scheduler 24.3 are checked to determine whether the output port has currently finished servicing the packet. Assume that the virtual output port has currently completed servicing the previous packet (i.e., has serviced the last bit of this packet) from the Class 1 virtual queue.

Accordingly, the GPS 24.2 scheduler selects a packet that is located at the beginning of the active virtual queue of class 1 for servicing at the next step, transmits the serviced packet and the weight of the corresponding queue (0.3) to the virtual output port of the device.

In the module for calculating the distance between alternative service options 24.5, a vector of the number of packets standing in virtual queues is formed at the current service step: there are 2 packets in the virtual queue of class 1, there are 2 packets in the virtual queue of class 2 - ; form a vector of the number of packets standing in physical queues; at the current step of service, there are 3 packets in the physical queue of class 1, and 1 packet in the physical queue of class 2 - .

After this, in the module for calculating the distance between alternative service options 24.5, a vector of alternative options for the number of packets standing in physical queues is formed at the next service step: the first alternative option is , i.e. a packet from the physical queue of class 1 will be taken for servicing, the second alternative option is , i.e. a packet from the physical queue of class 2 will be taken for servicing.

Next, in the module for calculating the distance between alternative service options 24.5, the distance metric is calculated between each element of the vector of alternative options for the number of packets standing in physical queues at the next service step and the vector of the number of packets standing in virtual queues at the current service step.

Table 1 presents the results of calculating the Euclidean distance metric for all possible combinations of packets in class 1 and 2 queues. The leftmost column describes the number of packets in virtual queues, and the top row describes the number of packets in physical queues.

After calculating the distance metric, an element or elements from the vector of alternative options for the number of packets in physical queues are selected at the next service step with the smallest distance metric. For the example considered, the Euclidean distance metric for the alternative option is equal to 1, and for the alternative option is equal to 2.236. Since 1<2.236, then an alternative option for the number of packets standing in physical queues is chosen accordingly at the next step of service - .

Next, in the 24.5-step distance calculation module, the interval from 0 to 1 is divided into a number of identical ranges equal to the number of selected elements from the vector of alternative packet counts in physical queues at the next service step with the same distance metric. In this case, one interval from 0 to 1.

The random number generator generates a random number uniformly distributed between 0 and 1 and transmits it to the module calculating the distance between alternative service options 24.5. For the considered example, the random number generator generated a random number of 0.536, so one interval is selected in each case.

Thus, given the smallest Euclidean distance metric of 1 and the selected range of first, the 24.5 alternative service option distance calculation module selects the packet located at the head of the Class 1 physical queue for servicing at the next hop. The 24.5 alternative service option distance calculation module then passes this information to the packet scheduler, taking into account the 24.3 distance metric.

The packet scheduler, taking into account the distance metric 24.3, transmits a packet that is located at the beginning of the physical queue of class 1 to the output port of the device.

Let's use an example of calculating the buffer space size to demonstrate the theoretical assumptions. For example, a device is configured with three queues, each capable of storing 20 packets. Consequently, the total number of packets to be stored in the queues is 60. WFQ-class schedulers, which approximate GPS, require storing the virtual end-of-service time for each packet. In iOS and Linux network operating systems, 8 bytes are allocated for storing virtual time. WFQ-class schedulers, which approximate GPS, also require storing packet numbers. These numbers are integers, and in the Python programming language, it is advisable to use the uint8 data type (an unsigned integer in 1 byte: from 0 to 255), which requires 1 byte of memory. Therefore, the required buffer space size for this example is 60⋅(8+1)=540 bytes.

The proposed method for fair queue servicing, taking into account the distance metric, and the device implementing it requires storing the current number of packets in the physical and virtual queues. Since the device is configured with three queues, and each queue can hold 20 packets, 5 bits (2 ^{× 5} = 32) of buffer space are required to store information about 20 packets. The minimum memory cell in modern network equipment is 1 byte, therefore, 1 byte of buffer space (2 × ⁸ = 256) is allocated to store information about the number of packets in the queue. Since the proposed method and device propose storing packets in both the physical and virtual queue modules, 1 byte multiplied by 6 queues (3 physical queues and 3 virtual queues) equals 6 bytes of buffer space.

Thus, using a simple example where the device is configured with three queues and each queue can accommodate 20 packets, the prototype requires 540 bytes of buffer space, while the proposed method for fair queue servicing, taking into account the distance metric and the device implementing it, requires 6 bytes. It's worth noting that the buffer space savings will increase as the number of queues and the number of packets in the queues increases.

The claimed method of fair queuing taking into account the distance metric and the device implementing it ensure a reduction in the size of the buffer space allocated for the operation of the packet scheduler due to the fact that data traffic packets of the corresponding class are placed in physical queues in accordance with the ToS Precedence field of the IP packet header, or in accordance with the DSCP field of the IP packet header, the sender IP address, the recipient IP address, or in accordance with such parameters as the protocol, access lists and the input interface, while the packet is placed at the end of the corresponding queue, provided that there is free space in this queue (Drop Tail mechanism) and the RED mechanism does not discard the packet in the event of overload detection, otherwise the packet is deleted, data traffic packets of the corresponding class are placed in virtual queues in accordance with the ToS Precedence field of the IP packet header, or in accordance with the DSCP field of the IP packet header, the sender IP address, the recipient IP address, or in accordance with such parameters as the protocol, access lists and the input interface, while the packet is placed at the end of the corresponding virtual queue, provided that there is free space in this virtual queue (Drop Tail mechanism) and the RED mechanism does not discard the packet in case of overload detection, otherwise the packet is deleted, the current state of the output port and the virtual output port of the device is checked, as well as the state of the GPS scheduler and the packet scheduler taking into account the distance metric for the end of servicing the packet by the output port or the virtual output port at the current moment in time, the packet located at the beginning of the active virtual queue is selected for servicing at the next step, the packet and the weight of the corresponding queue are transmitted to the virtual output port of the device, a vector of the number of packets standing in virtual queues is formed at the current servicing step, a vector of the number of packets standing in physical queues is formed at the current servicing step, a vector of alternative options for the number of packets standing in physical queues is formed at the next servicing step, the distance metric is calculated between each element of the vector of alternative options for the number of packets standing in physical queues at the next servicing step and the vector of the number of packets standing in virtual queues at the current servicing step, an element or elements are selected from a vector of alternative options for the number of packets standing in physical queues at the next service step with the smallest distance metric, the interval from 0 to 1 is divided into a number of identical ranges equal to the number of selected elements from the vector of alternative options for the number of packets standing in physical queues at the next service step with the same distance metric, a random number is generated uniformly distributed in the interval from 0 to 1, the number of the range into which the generated random number falls is selected, the packet located at the beginning of the corresponding physical queue is selected for servicing at the next step with the smallest distance metric and taking into account the selected range number, the packet is transmitted from the beginning of the corresponding physical queue to the output port of the device.

Claims (3)

1. A method for fair queuing with respect to the distance metric, which consists in the following: at the first stage, the total number of queues, the maximum number of packets in each queue, the bandwidth, the share of the bandwidth allocated for the operation of schedulers with respect to the distance metric, the weight for each queue, the parameters of the random early congestion detection mechanism RED for each queue are set for each output port of the device; at the second stage, data traffic flows are received at the input ports of the device, the data traffic flows are classified into classes in accordance with the ToS Precedence field of the IP packet header, or in accordance with the DSCP field of the IP packet header, the source IP address, the destination IP address, or in accordance with parameters such as the protocol, access lists and the input interface are routed to the corresponding output ports of the router based on the routing table and the destination IP address, or based on the forwarding table and the MPLS label, the data traffic packets of the corresponding class are placed into physical queues in accordance with the ToS Precedence field of the header IP packet, or in accordance with the DSCP field of the IP packet header, the source IP address, the destination IP address, or in accordance with parameters such as protocol, access lists and input interface, while the packet is placed at the end of the corresponding queue, provided that there is free space in this queue (Drop Tail mechanism) and the RED mechanism does not discard the packet in case of detecting congestion, otherwise the packet is removed, data traffic packets of the corresponding class are placed in virtual queues in accordance with the ToS Precedence field of the IP packet header, or in accordance with the DSCP field of the IP packet header, the source IP address, the destination IP address, or in accordance with parameters such as protocol, access lists and input interface, while the packet is placed at the end of the corresponding virtual queue, provided that there is free space in this virtual queue (Drop Tail mechanism) and the RED mechanism does not discard the packet in case of detecting congestion, otherwise the packet is removed, the current state of the output port and the virtual output port of the device is checked, and also the state of the GPS scheduler and the packet scheduler taking into account the distance metric for the end of servicing the packet by the output port or virtual output port at the current time, selecting a packet that is located at the beginning of the active virtual queue for servicing at the next step, transmitting the packet and the weight of the corresponding queue to the virtual output port of the device, forming a vector of the number of packets standing in virtual queues at the current servicing step, forming a vector of the number of packets standing in physical queues at the current servicing step, forming a vector of alternative options for the number of packets standing in physical queues at the next servicing step, calculating the distance metric between each element of the vector of alternative options for the number of packets standing in physical queues at the next servicing step and the vector of the number of packets standing in virtual queues at the current servicing step, selecting an element or elements from the vector of alternative options for the number of packets standing in physical queues at the next servicing step with the smallest distance metric, dividing the interval from 0 to 1 into a number of identical ranges equal to the number of selected elements from the vector of alternative options for the number of packets, standing in physical queues, at the next step of service with the same distance metric, generate a random number uniformly distributed in the interval from 0 to 1, select the range number in which the generated random number falls, select a packet that is located at the beginning of the corresponding physical queue, for service at the next step with the smallest distance metric and, taking into account the selected range number, transmit the packet from the beginning of the corresponding physical queue to the output port of the device. 2. A distance-based fair queuing device comprising 1 to n input ports for receiving data traffic flows, a classifier configured to classify data traffic flows according to a ToS Precedence field of an IP packet header, or according to a DSCP field of an IP packet header, a source IP address, a destination IP address, or according to parameters such as a protocol, access lists, and an input interface, a routing module configured to forward a packet to an output port according to a routing table and a destination IP address, or based on a forwarding table and an MPLS label, 1 to n physical queuing modules for placing packets in a queue of the corresponding class according to a ToS Precedence field of an IP packet header, or according to a DSCP field of an IP packet header, a source IP address, a destination IP address, or according to parameters such as a protocol, access lists, and an input interface; setting a weight for each queue; setting the parameters of the random early congestion detection mechanism RED for each queue, from 1 to n output ports for transmitting data traffic flows into the communication channel, characterized in that from 1 to n distance metric fair packet service modules are additionally included, configured to "fairly distribute" the output port throughput for variable-length packets taking into account the distance metric, wherein the data traffic flows are received at the input ports, then from the input ports the data traffic flows are transmitted to the input of the classifier, the output of the classifier is connected to the input of the routing module, from the output of the routing module the data traffic flows are received at the input of the physical queuing module for placing packets into a queue of the corresponding class in accordance with the ToS Precedence field of the IP packet header, or in accordance with the DSCP field of the IP packet header, the sender IP address, the recipient IP address, or in accordance with parameters such as the protocol, access lists and the input interface, from the distance metric fair packet service module the data traffic flows are received at the output ports. 3. The device according to claim 2, in which the module for fair packet servicing taking into account the distance metric comprises a virtual queuing module configured to place packets in a virtual queue that corresponds to a physical queue of the corresponding class, a GPS scheduler configured to implement in continuous time the principle of "fair distribution of resources" for packets of variable length, a random number generator configured to generate a random number uniformly distributed in the interval from 0 to 1, a module for calculating the distance between alternative packet servicing options, configured to generate a vector of the number of packets standing in virtual queues at the current servicing step; generating a vector of the number of packets standing in physical queues at the current servicing step; generating a vector of alternative options for the number of packets standing in physical queues at the next servicing step; calculating the distance metric between each element of the vector of alternative options for the number of packets standing in physical queues at the next servicing step and the vector of the number of packets standing in virtual queues at the current servicing step; selecting an element or elements from a vector of alternative options for the number of packets standing in physical queues at the next servicing step with the smallest distance metric; dividing the interval from 0 to 1 into a number of identical ranges equal to the number of selected elements from the vector of alternative options for the number of packets standing in physical queues at the next servicing step with the same distance metric; selecting the number of the range into which the generated random number falls, a packet scheduler taking into account the distance metric, configured to select a packet that is located at the beginning of the corresponding physical queue for servicing at the next step with the smallest distance metric, taking into account the selected range number; transmitting the packet to the output port with the implementation of the principle of "fair servicing" of queues taking into account the distance metric, wherein all modules in the device are connected via a common internal AXI4 bus, which acts as a means of exchanging information between the modules.