CN-122027588-A - Programmable data packet scheduling method and system for network switching chip

CN122027588ACN 122027588 ACN122027588 ACN 122027588ACN-122027588-A

Abstract

The application relates to the technical field of network communication, in particular to a programmable data packet scheduling method and a programmable data packet scheduling system for a network switching chip, wherein the method comprises the steps of constructing a hierarchical scheduling tree; the hierarchical scheduling tree includes leaf node levels and root node levels, each node configured with a bitmap mapping bucket queue, a dynamic priority window mapping module, and a reconfigurable priority calculator. The method can overcome the technical problems of the existing scheduler in terms of flexibility, performance and expansibility, and further realize multi-algorithm dynamic deployment, priority range expansion and hierarchical scheduling optimization while maintaining the linear speed processing performance.

Inventors

SHI JIANGYI
WANG YIXIN
MA PEIJUN
PAN WEITAO
CHEN HONGGAN
TIAN ZIYI

Assignees

西安电子科技大学

Dates

Publication Date: 20260512
Application Date: 20260128

Claims (10)

1. A programmable packet scheduling method for a network switch chip, the method comprising: constructing a hierarchical scheduling tree, wherein the hierarchical scheduling tree comprises a leaf node level and a root node level, and each node is configured with a bitmap mapping bucket queue, a dynamic priority window mapping module and a reconfigurable priority calculator; at the leaf node level, calculating the initial priority of metadata in the data packet by a reconfigurable priority calculator; If the currently activated scheduling algorithm requires to support the priority beyond the hardware range, mapping the initial priority to the limited priority index range supported by the hardware in real time through a dynamic priority window mapping module; based on the mapped priority, inserting the data into a bitmap mapping bucket queue of the leaf node for sorting, and outputting dequeued metadata to a root node level; at the root node level, receiving metadata from each leaf node and distributing the metadata to different logical partitions of the root node level bitmap mapping bucket queue based on key fields of the metadata; In each logic partition, calculating the relative priority of metadata in the partition by a reconfigurable priority calculator, and determining the global absolute priority of the metadata in a bitmap mapping bucket queue of a root node level by combining the partition offset to queue; scheduling among the logical partitions based on a configurable dequeue policy, and determining metadata to be dequeued in each logical partition to complete global scheduling.
2. The method according to claim 1, wherein if the currently activated scheduling algorithm requires support of priorities beyond the hardware range, mapping the initial priorities into the limited priority index range supported by the hardware in real time through dynamic priority window mapping comprises: If the currently activated scheduling algorithm requires to support the priority beyond the hardware range, dividing the bitmap mapping bucket queue example into a main queue and a side queue, wherein the main queue stores the priority in the following way Metadata in range, side queue buffer priority in Metadata within a range; Mapping the offset for a preset priority; when the main queue is empty, the priority window is shifted through a window scrolling mechanism Dequeuing is started by switching the side queue to the main queue, and the original main queue is switched to the side queue and the buffer priority is in Metadata within a range; the window scroll mechanism process is repeatedly performed to extend the priority index range.
3. The method of claim 1, wherein the configurable dequeue policy is implemented by a partition arbitration module, wherein the scheduling between logical partitions based on the configurable dequeue policy and determining metadata to dequeue within the logical partitions to complete global scheduling comprises: executing an arbitration policy by a partition arbitration module, wherein the arbitration policy comprises at least one of strict priority, weighted polling and deficit polling; a dequeue mask is generated based on the arbitration policy to determine a next scheduled logical partition in the bitmap map bucket queue of the root node based on the dequeue mask and to support expansion of other arbitration policies.
4. The method of claim 1, wherein calculating, by the reconfigurable priority calculator, an initial priority of metadata in the data packet, comprises: Analyzing the packet header vector of the data packet and extracting key fields to construct metadata; Performing arithmetic logic operation in a multistage pipeline mode, and calculating the priority of metadata; and storing and analyzing instruction codes issued by the software, and configuring the operation modes and the data flow directions of the single operation processing units.
5. The method of claim 4, wherein storing and configuring the operation mode and data flow of each single operation processing unit comprises: Obtaining a source operand from an operand register based on a source operand field of an instruction code; performing an arithmetic logic operation based on an operation mode field of the instruction code, wherein the arithmetic logic operation includes an addition, subtraction, multiplication, division, or comparison operation; the calculation result is written into a register based on the result-to-field of the instruction code, transferred to the next stage or directly output.
6. A programmable packet scheduling system for a network switch chip, comprising: The system comprises a construction module, a reconstruction module and a reconstruction module, wherein the construction module is used for constructing a hierarchical scheduling tree, the hierarchical scheduling tree comprises a leaf node level and a root node level, and each node is provided with a bitmap mapping bucket queue, a dynamic priority window mapping module and a reconfigurable priority calculator; The system comprises a leaf node scheduling module, a dynamic priority window mapping module, a bit map mapping bucket queue, a root node level, a bit map mapping bucket queue, a leaf node scheduling module and a bit map mapping bucket queue, wherein the leaf node scheduling module is used for calculating the initial priority of metadata in a data packet through a reconfigurable priority calculator at the leaf node level; The root node scheduling module is used for receiving metadata from each leaf node at the root node level and distributing the metadata to different logic partitions of the root node level bitmap mapping bucket queue based on key fields of the metadata, calculating the relative priority of the metadata in each logic partition through a reconfigurable priority calculator, determining the global absolute priority of the metadata in the bitmap mapping bucket queue at the root node level by combining partition offset and then queuing, scheduling among the logic partitions based on a configurable dequeue strategy, and determining the metadata to be dequeued in each logic partition so as to complete global scheduling.
7. The system of claim 6, wherein each node in the hierarchical scheduling tree comprises: the reconfigurable priority calculator is used for constructing metadata, analyzing an algorithm instruction code programmed by software, and configuring the algorithm instruction code into the operation processing unit array to finish the initial priority calculation of the metadata; The dynamic priority window mapping module is used for maintaining a dynamic rolling priority window, and mapping the initial priority generated by the reconfigurable priority calculator into a limited priority index range which can be supported by a bitmap mapping bucket queue in real time, wherein the module takes effect when a scheduling algorithm needing an infinite priority range is deployed; And the bitmap mapping bucket queue is used for sequencing and outputting the received metadata based on the mapped priority.
8. The system of claim 7, wherein the reconfigurable priority calculator comprises a preprocessing module, an array of arithmetic processing units, and an instruction code storage and decoding module; The preprocessing module is used for analyzing the packet header vector of the data packet and extracting key fields to construct metadata; The arithmetic processing unit array is formed by interconnecting a plurality of single arithmetic processing units and is used for executing arithmetic logic operation in a multistage pipelining mode and calculating the priority of metadata; the instruction code storage and decoding module is used for storing and analyzing the instruction codes issued by the software and configuring the operation modes and the data flow directions of the single operation processing units.
9. The system of claim 7, wherein the dynamic priority window mapping module embeds a dynamic priority window scroll controller, the dynamic priority window scroll controller implemented based on a finite state machine, wherein the finite state machine includes an IDLE state, a CHECK_H state, a ROLL2L state, a CHECK_L state, and a ROLL2H state; In the IDLE state, when the algorithm is detected to need an infinite priority range, switching to the CHECK_H state; In the CHECK_H state, monitoring the bitmap of the high-order partition and the element number, and if both the bitmap and the element number are zero, switching to the ROLL2L state; in the ROLL2L state, the dequeue mask and the priority offset are updated and then the CHECK_L state is switched to; In the CHECK_L state, monitoring the bitmap of the low-level partition and the element number, and if both the bitmap and the element number are zero, switching to the ROLL2H state; in the ROLL2H state, the CHECK_H state is returned after the dequeue mask is updated to cycle support priority window scrolling.
10. A computer readable storage medium storing a computer program, wherein the computer program, when executed by a processor, is capable of implementing a programmable packet scheduling method for a network switch chip according to any one of claims 1 to 5.

Description

Programmable data packet scheduling method and system for network switching chip Technical Field The embodiment of the application relates to the technical field of network communication, in particular to a programmable data packet scheduling method and system for a network switching chip. Background With the rapid development of cloud computing, artificial intelligence, and 5G/6G technology, modern data center networks are facing explosive growth of traffic scale and extremely diverse traffic types. Network applications, such as high performance computing, distributed machine learning training, etc., place different and stringent quality of service requirements on bandwidth, delay, jitter, and reliability of network data transmissions. In this context, the network switching chip serves as a core engine for data forwarding, and its packet scheduling capability directly determines the performance and efficiency of the entire network. Although the traditional fixed-function exchange chip can provide high-speed forwarding capability, the scheduling logic of the traditional fixed-function exchange chip is usually solidified in the chip design stage, and cannot be dynamically adjusted according to the network state and service requirements which change in real time after deployment, so that the traditional fixed-function exchange chip is difficult to adapt to different network service quality requirements. Schedulers based on programmable hardware primitives, such as Push-In-First-Out Queue (PIFO), are considered to be a more advanced hardware scheduling architecture. The core idea is to use a hardware queue structure of "enqueue, i.e. order". As each packet is enqueued, a ranking is calculated for it by a programmable module according to a particular algorithm, and the packet is then inserted into the corresponding location of the queue according to the ranking. Dequeue operations are reduced to fetching packets from the head of the queue. The structure can simulate a plurality of scheduling algorithms by using a single queue in theory, but is limited by comparison ordering logic, so that the capacity of the queue is difficult to expand while high throughput rate is supported, massive concurrent flows cannot be handled, and the structure is difficult to adapt to the scene of processing huge concurrent flows at the line speed faced by the cloud intelligent network card. Therefore, how to realize multi-algorithm dynamic deployment, priority range expansion and hierarchical scheduling optimization while maintaining the line speed processing performance is a technical problem to be solved at present. Disclosure of Invention In view of this, the embodiment of the application provides a programmable data packet scheduling method and a programmable data packet scheduling system for a network switching chip, which can overcome the technical problems of the existing schedulers in terms of flexibility, performance and expansibility, and further realize multi-algorithm dynamic deployment, priority range expansion and hierarchical scheduling optimization while maintaining the line speed processing performance. To achieve the above object, an embodiment of the present application provides a programmable packet scheduling method for a network switching chip, the method including the steps of: constructing a hierarchical scheduling tree, wherein the hierarchical scheduling tree comprises a leaf node level and a root node level, and each node is configured with a bitmap mapping bucket queue, a dynamic priority window mapping module and a reconfigurable priority calculator; at the leaf node level, calculating the initial priority of metadata in the data packet by a reconfigurable priority calculator; If the currently activated scheduling algorithm requires to support the priority beyond the hardware range, mapping the initial priority to the limited priority index range supported by the hardware in real time through dynamic priority window mapping; based on the mapped priority, inserting the data into a bitmap mapping bucket queue of the leaf node for sorting, and outputting dequeued metadata to a root node level; at the root node level, receiving metadata from each leaf node and distributing the metadata to different logical partitions of the root node level bitmap mapping bucket queue based on key fields of the metadata; In each logic partition, calculating the relative priority of metadata in the partition by a reconfigurable priority calculator, and determining the global absolute priority of the metadata in a bitmap mapping bucket queue of a root node level by combining the partition offset to queue; scheduling among the logical partitions based on a configurable dequeue policy, and determining metadata to be dequeued in each logical partition to complete global scheduling. Optionally, if the currently activated scheduling algorithm requires support of priority beyond the hardware range, mapping the initial priority in rea