CN109379304B - Fair scheduling method for reducing low-priority packet delay - Google Patents

Abstract

The invention discloses a fair scheduling method for reducing the delay of low-priority packets, which is suitable for CICQ switching structure, has low average delay, strong expansibility and simple hardware implementation. It relates to the field of high-speed serial switching input queuing scheduling. When designing different allocation strategies according to the priority, the present invention cannot take into account the fairness of low-priority services, and at the same time, when facing the needs of multiple users with different QoS, the invention has poor scalability, higher complexity problems. The advantage of applying this method is that the maximum delay of low-priority packet transmission can be determined by parameter configuration, and the existing scheduling algorithm can be flexibly extended according to design requirements, and at the same time, it has low complexity and strong versatility and is suitable for all supported priorities. High-speed switching fabric for business.

Description

A Fair Scheduling Method for Reducing the Delay of Low Priority Packets

technical field

The invention relates to a high-speed serial switching scheduling algorithm with better fairness, which is particularly suitable for CICQ switching circuits supporting priority scheduling, and can realize QoS support for multi-priority services with better fairness and flexibility.

Background technique

The switching system is mainly responsible for the transmission of data from one port to another port, and it mainly includes three parts: input (output) port, switching structure, and control module. The control module is the core of the entire switching system. The switch fabric and control module can also be combined into a switch kernel. Due to the multi-port characteristics of the switching structure, different input and output ports can only have one cell input or output in each time slot. If the switching structure wants to have good non-blocking characteristics, it is necessary to set up buffers at the nodes. Therefore, there is an input queue and an output queue.

First, in a linear channel X, there are several cells waiting to be output, because the input of the queue is only limited by the size of the queue buffer, and in the output process, only the cell at the head of the queue participates in scheduling. As a result, other cells in the buffer queue are blocked by the head-of-line cell, and other cells in the queue do not participate in scheduling, so a head-of-line blocking (HOL) problem occurs. According to the mathematical analysis, the maximum throughput rate that the switch port can achieve is limited to 58.6%. There are also many solutions, mainly including the following: windowing method, acceleration method and virtual output queue method. Among them, the virtual output queue method is the main technology to solve this problem.

When the virtual output queue method is used, input competition is introduced. Input end competition means that multiple cells arriving at different output ends in the same input end need to be transmitted in the same time slot; therefore, an efficient and fair scheduling algorithm is required to solve the competition between the input and output ends of cells and establish multiple input /Output connection, and control the operation of the switch fabric to ensure that cells are transmitted without collisions.

SUMMARY OF THE INVENTION

The technical problem to be solved by the present invention is to provide an efficient and fair scheduling algorithm, which can be used to switch between strict priority round-robin scheduling and starvation-avoidance priority round-robin scheduling. Use configurable threshold parameters to set the count threshold of the scheduler, which effectively reduces the average delay of low-priority packets and avoids starvation of a certain service.

The technical scheme adopted in the present invention is:

A fair scheduling method for reducing the delay of low-priority packets, comprising the following steps:

(1) Configure the threshold parameters, buffer the input data packets at the input end, and generate the labels of the data packets at the same time, divide the labels of the data packets into different virtual queues according to the priority and the target port, and set the settings for each virtual queue a counter;

(2) Each virtual queue sends an application to the scheduler according to the situation that the queue is full;

(3) The scheduler selects the highest priority virtual queue from the application signal set to authorize arbitration, and the virtual queues of the same priority with different target ports use the polling method to authorize arbitration; at the same time, the counter of each virtual queue is counted, and the counting rule is: : When the virtual queue is not empty and it is authorized to arbitrate other virtual queues, the counter value of the virtual queue is increased by 1. When the count reaches the configured threshold parameter, the virtual queue is marked as over, otherwise it is marked as under;

(4) The scheduler judges whether there is a virtual queue marked over, if so, the scheduler keeps locking the virtual queue marked over, and grants priority to arbitrate the queue until the over state is released when the queue is empty; otherwise, go back to the step (3), until all virtual queues are empty;

(5) According to the arbitration result, the tag is read from the virtual queue, and the data packet is selected according to the tag and sent to the corresponding destination port.

Wherein, the label in step (1) includes the storage space location, output port number and priority information of the input data packet.

Wherein, in step (4), the scheduler keeps locking the virtual queue marked as over, and authorizes the arbitration of the queue in priority until the over state is released when the queue is empty. Specifically, the scheduler selects the highest priority from the virtual queue marked as over. The virtual queues of the same priority level authorize arbitration, and the over virtual queues of the same priority use the polling strategy to authorize arbitration until the virtual queue is released from the space-time over state.

Wherein, step (5) is specifically:

Read the label from the virtual queue according to the arbitration result, extract the storage location sequence number and output port number of the data packet in the label, read the corresponding data packet from the input buffer according to the storage location sequence number, and send the data according to the output port number in the label. Packet to the corresponding crosspoint of the output destination port.

Compared with the background technology, the present invention has the following advantages:

(1) The present invention can effectively reduce the traffic between modules by distinguishing service priorities and target ports through virtual queues, so that the queues themselves carry priority and routing information, thus reducing the design difficulty and complexity of scheduling algorithms.

(2) The present invention calculates the service frequency of each queue by setting a counter for each virtual queue, and determines the limit value of each queue by comparing with a preset threshold parameter, so that low-priority services can be restricted The maximum delay of a packet to prevent starvation of a queue or service.

(3) The present invention further expands the different attributes of the priority by increasing the queue classification of over and under, and in this way, the real-time performance of the business can be better guaranteed.

(4) The present invention also has strong flexibility and applicability, can be used in conjunction with other algorithms in various queuing switching structures, and can also flexibly configure threshold parameters according to business types, so that switching achieves better performance.

Description of drawings

FIG. 1 is a flowchart of the implementation of the scheduling algorithm of the present invention.

Fig. 2 is the label generation and enqueue process and virtual queue structure of the input packet of the present invention.

FIG. 3 is a block diagram of the implementation of the counter set for each queue according to the present invention.

FIG. 4 is a schematic block diagram of the CICQ switching structure of the present invention.

Detailed ways

The present invention will be further explained below in conjunction with the accompanying drawings.

Referring to FIG. 1, a fair scheduling method for reducing the delay of low-priority packets according to the present invention includes the following steps:

(1) Configure the threshold parameters, buffer the input data packets at the input end, and generate the labels of the data packets at the same time, divide the labels of the data packets into different virtual queues according to the priority and the target port, and set the settings for each virtual queue A counter; the label contains the storage location, output port number, and priority information of incoming packets.

Fig. 2 is the label generation and enqueue process and virtual queue structure of the input packet of the present invention. When the packet parsing is completed, a label will be generated, and the label will be stored in the virtual queue in the label queuing area. The queuing principle of labels is: the labels of the same priority and the same target port are cached in the same virtual queue according to the first-in, first-out method, and the same virtual queue is buffered according to the first-in, first-out method.

(2) Each virtual queue sends an application to the scheduler according to the situation that the queue is full;

(3) The scheduler selects the highest priority virtual queue from the application signal set to authorize arbitration, and the virtual queues of the same priority with different target ports use the polling method to authorize arbitration; at the same time, the counter of each virtual queue is counted, and the counting rule is: : When the virtual queue is not empty and it is authorized to arbitrate other virtual queues, the counter value of the virtual queue is increased by 1. When the count reaches the configured threshold parameter, the virtual queue is marked as over, otherwise it is marked as under;

(4) The scheduler judges whether there is a virtual queue marked over, if so, the scheduler selects the virtual queue with the highest priority from the virtual queue marked over to authorize arbitration, and the over virtual queue with the same priority uses polling The strategy authorizes arbitration until the virtual queue is released from the space-time over state; otherwise, return to step (3) until all virtual queues are empty;

(5) According to the arbitration result, the tag is read from the virtual queue, and the data packet is selected according to the tag and sent to the corresponding destination port. Specifically: read the label from the virtual queue according to the arbitration result, extract the storage location sequence number and output port number of the data packet in the label, read the corresponding data packet from the input buffer area according to the storage location sequence number, and output the port number according to the label Send the packet to the crosspoint corresponding to the output destination port.

Among them, as shown in FIG. 1 , the packet analysis designed by the present invention mainly completes the enqueuing function of data packets. It mainly includes several main processes of address application, label generation, enqueue control, virtual queue organization and scheduling based on output code group and priority, and result processing.

The address application is mainly to apply for an actual address from the RAM of the shared cache for the data packet to be queued, and the data packet can be stored in this RAM. At the same time, when dequeuing, the dequeue is completed by receiving the packet storage sequence number in the label obtained from the scheduling result.

When a packet needs to be queued, the packet processing function will write the free address applied for by the current packet and the acquired information corresponding to the packet into the label, including storage space location, output port number and priority information, etc. . The enqueue control will write the newly obtained label into the corresponding virtual queue according to the priority and target port information in the label, so as to complete the link between the storage of the data packet and the organization of the label virtual queue.

Wherein, according to the state of the current virtual queue, a scheduling application is sent to the scheduling control, and after the scheduling is completed, the corresponding queue label information is read according to the scheduling result. According to the data packet storage sequence number and other information in the label information, it cooperates with the output bus controller to move the data packet to the cross point or the next level corresponding to the output port.

Among them, the implementation process of step (4) is: when there is an over virtual queue with a high priority, the high priority over virtual queue is scheduled first; the over virtual queue with the same priority is marked as "over" with a polling strategy Select from the virtual queue of over; if there is no over virtual queue, use the polling strategy to select from the under queue.

Wherein, the implementation process of step (5) is to read the head tag of the corresponding virtual queue according to the arbitration result of the scheduler, and obtain information such as the packet storage sequence number and the output port number in the tag. According to the data packet storage sequence number and other information in the label information, it cooperates with the output bus controller to move the data packet to the cross point or the next level corresponding to the output port.

Figure 3 is a block diagram of the design principle of the counter in step (3). The judgment logic is based on each arbitration result and the current cache situation of the virtual queue KN. If there is a packet in the queue, but the arbitration result pointer points to another queue, the counter increases. When the value of the counter reaches the pre-configured value, the over signal of the queue is pulled high, otherwise the under signal is pulled high.

Figure 4 is a schematic block diagram of the CICQ switching structure. Where N is the switch fabric port number. When a data packet enters from a certain port, virtual queuing is performed at the input port first, and an application is made to the input scheduler to accept the arbitration result. The implementation process of step (5) is to send the corresponding data packet to the cross point corresponding to the output port of the data packet for buffering according to the arbitration result and the output port information in the label. For example, a packet entering from port 1 to port 3 will be sent to the intersection of row 1 and column 3 in Figure 4 for buffering. Output scheduling selects packets to send to output ports based on the status of different intersections in the same column. A fair scheduling method for reducing the delay of low-priority packets in the present invention refers to an input scheduling process.

Claims (4)

1. A fair scheduling method for reducing low-priority packet delay is characterized in that comprising the following steps: (1) Configure the threshold parameters, buffer the input data packets at the input end, and generate the labels of the data packets at the same time, divide the labels of the data packets into different virtual queues according to the priority and the target port, and set the settings for each virtual queue A counter; among them, the queuing principle of labels is: the same priority, the labels of the same target port are cached in the same virtual queue according to the first-in, first-out method, and the same virtual queue is cached according to the first-in, first-out method; (2) Each virtual queue sends an application to the scheduler according to the situation that the queue is full; (3) The scheduler selects the highest priority virtual queue from the application signal set to authorize arbitration, and the virtual queues of the same priority with different target ports use the polling method to authorize arbitration; at the same time, the counter of each virtual queue is counted, and the counting rule is: : When the virtual queue is not empty and it is authorized to arbitrate other virtual queues, the counter value of the virtual queue is increased by 1. When the count reaches the configured threshold parameter, the virtual queue is marked as over, otherwise it is marked as under; (4) The scheduler judges whether there is a virtual queue marked over, if so, the scheduler keeps locking the virtual queue marked over, and grants priority to arbitrate the queue until the over state is released when the queue is empty; otherwise, go back to the step (3), until all virtual queues are empty; (5) According to the arbitration result, the tag is read from the virtual queue, and the data packet is selected according to the tag and sent to the corresponding destination port. 2. a kind of fair scheduling method for reducing low-priority packet delay according to claim 1, is characterized in that: in step (1), in label, comprise the storage space position, output port number and priority of input data packet information. 3. a kind of fair scheduling method for reducing low-priority packet delay according to claim 1, is characterized in that: in step (4), scheduler locks the virtual queue marked as over all the time, priority authorizes to arbitrate this queue, Until the queue is empty, the over state is released, specifically: the scheduler selects the highest priority virtual queue from the virtual queue marked over to authorize arbitration, and the over virtual queue of the same priority uses the polling strategy to authorize arbitration until The virtual queue is released from the space-time over state. 4. a kind of fair scheduling method for reducing low-priority packet delay according to claim 1, is characterized in that: step (5) is specifically: Read the label from the virtual queue according to the arbitration result, extract the storage location sequence number and output port number of the data packet in the label, read the corresponding data packet from the input buffer according to the storage location sequence number, and send the data according to the output port number in the label. Packet to the corresponding crosspoint of the output destination port.

Images