CN112491748B - A Credit-Based Proportional Fair Scheduling Method Supporting Data Packet Switching - Google Patents

Abstract

The invention discloses a credit-based proportional fair scheduling method supporting data packet switching, and belongs to the technical field of high-speed serial switching output scheduling. The invention guarantees the boundary of necessary reserved bandwidth and distributable bandwidth for each data flow by means of parameter configuration, and guarantees each data flow to share the bandwidth fairly by using credit borrowing and supplementing mechanisms. By the method, the data stream can be isolated, different service streams can share the guaranteed bandwidth which can be shared by the different service streams, and even if malicious or highly bursty service streams exist, other normal service streams are not influenced.

Description

A Credit-Based Proportional Fair Scheduling Method Supporting Data Packet Switching

technical field

The invention relates to the technical field of high-speed serial switching output scheduling, in particular to a credit-based proportional fair scheduling method supporting data packet switching.

Background technique

The switch chip is mainly responsible for the transmission of data from one port to another port, mainly including input/output ports, switching structure and control module. As the core part of the switching chip, the performance of the switching fabric is related to the overall performance of the switching chip. On the basis of the switching structure, the research of simple and efficient scheduling algorithm to ensure the non-blocking switching of data packets, low delay, high throughput and fairness is an important direction of switching chip research.

The Combined Input and Crosspoint Queuing (CICQ) structure with buffered crosspoint is one of the simplest and high-performance switching structures. It has the advantages of high throughput, low latency, and low complexity and easy scheduling accomplish. At the same time, since each port is more independent in space, in the CICQ structure, the input process and the output process are independent of each other during data transmission, thus canceling the matching scheduling algorithm. This switching structure not only reduces the design difficulty of the algorithm, but also It can ensure the high-speed operation of the switching system.

In addition, since the CICQ structure uses a cross-point buffer, the cross-point buffer isolates the input from the output. Therefore, in the scheduling process, the "request-allow-accept" interactive operation is not required for the scheduling between ports, so the CICQ scheduling algorithm can adopt a distributed scheduling strategy, that is, the scheduling between ports is isolated from each other and There is no information dependency between them. Adopting this distributed scheduling strategy can greatly reduce the complexity of the algorithm, and can adopt different scheduling strategies according to the situation of the port itself, giving the scheduling algorithm greater flexibility and diversity of scheduling methods. In addition, the CICQ structure also supports switching scheduling of variable-length frames, which is difficult for other switching structures without a cross-point buffer structure to implement centralized scheduling.

High-performance switching structures and scheduling algorithms should have many good characteristics such as effectiveness (including throughput, stability and delay characteristics), fairness and complexity in some common problems. Therefore, scheduling algorithms must also be designed to achieve these three goals. Since each port is more independent in space, in the CICQ structure, the input and output terminals are independent of each other during data transmission, so a distributed scheduling method can be adopted, that is, the input terminal scheduling and output terminal scheduling are designed separately. Input scheduling realizes the fair performance between flows within the same port, and output scheduling achieves the fair performance between flows on different ports. Input scheduling and output scheduling jointly realize the flow-based fair scheduling mechanism. Most of the current CICQ scheduling algorithms are developed on the basis of IQ (Input Queued, input queuing), OQ (Output Queued, output queuing), CIOQ (Combined Input and Output Queued, combined input and output queuing) switching structure scheduling algorithm. They can be roughly divided into two categories:

(1) Scheduling without queue status information: such as input scheduling RR (Round Robin, polling) - output scheduling RR, etc. The advantage is that it is simple and easy to implement in hardware. The disadvantage is that although the performance is good under uniform traffic flow, the performance is unsatisfactory under non-uniform traffic flow.

(2) Scheduling based on queue status information: such as input scheduling LQF (Longest Queue First, longest queue first) - output scheduling RR, input scheduling OCF (Oldest Cell First, longest queue first) - output scheduling OCF, etc. Compared with scheduling algorithms without queue state information, these algorithms have better performance but higher algorithm complexity.

SUMMARY OF THE INVENTION

In view of this, the present invention provides a credit-based proportional fair scheduling method supporting data packet exchange, which can achieve QoS support for multi-priority services and fair bandwidth allocation with better fairness and flexibility, Can be used for CICQ switching circuits with buffered crosspoints that support priority scheduling.

In order to achieve the above object, the technical scheme adopted in the present invention is:

A credit-based proportional fair scheduling method supporting data packet switching, comprising the following steps:

(1) Queue the data packets at the CICQ intersection, and sort according to the priority of the data packets in the buffer at the intersection, and set a counter and a comparator for each CICQ intersection;

(2) Each intersection queue sends an application to the output scheduler according to the empty condition of the queue;

(3) The output scheduler selects the application with the highest priority to authorize arbitration, and the polling method is used to authorize arbitration when the priority is the same;

(4) The initially assigned credit of each column intersection is a positive value resvn. When there is a data packet output at the intersection, the credit resvn is decremented by 1 every clock cycle until the credit resvn is negative;

(5) When the credit amount resvn of the column intersection point is negative, the initial credit amount of the intersection point in the idle state is borrowed, and the total borrowable amount is the sum of the credit amounts of all the intersection points in the idle state, and the polling and arbitration continues; If the total credit of the column intersection with negative amount reaches the threshold min, the credit value of all intersection queues will be cleared, and return to step (1); if the total borrowed credit reaches the sum of the credit of the intersection in the idle state, and If there is no intersection credit amount resvn reaches the threshold min, then enter step (6);

(6) Use the intersection with the negative credit to supplement the resvn-sized credit once. If the credit of the port is positive after the supplement, the port will send continuous transmission until the credit of all ports is negative, and start polling. , polling until the sum of the credits of the intersections of the idle state is reached again, and supplement it again; until the credits of some ports reach the min value, go back to step (1).

Further, in step (1), the data packets are buffered at the CICQ intersection, and are queued according to the priority labels of all data packets at the intersection. The high-priority data packets are output before the low-priority data packets, and the same priority The data packets of the advanced level are output according to the output scheduling result.

Further, the resvn allocated to the intersection in step (4) is updated in real time, and the resvn update takes the clock cycle as the unit, and the update settlement is completed at the end of each clock cycle.

Further, after the credit amount resvn is negative in step (6), when supplementing the credit amount, only the available credit value of the intersection is provided, and the resvn value of the intersection is not modified, and the resvn value is the same when the data packet is output at the intersection. The update method remains the same.

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

(1) The present invention converts the calculation of the bandwidth into the calculation of the credit amount, and does not need to store a large amount of queue status information during the implementation process. It only needs to set the bandwidth counter and the corresponding threshold, and increase or decrease the value of different conditions. Realize dynamic allocation of output bandwidth. Therefore, the design difficulty and complexity of the scheduling algorithm are reduced.

(2) The present invention ensures their available bandwidth by reserving credits for each intersection, and ensures that different data streams can enjoy their own bandwidth by setting up an independent credit update mechanism for each intersection, Even if there is malicious or highly bursty business, it will not affect its normal data flow.

(3) The present invention configures two parameters, max and min. These two parameters set the limit that the credits of each intersection can be accumulated to ensure that they will not increase or decrease infinitely. The parameter value can also be flexibly configured to deal with the boundary detection when the intersection suffers from irregular flow (for example, one is a 272byte data packet and the other is a 32byte data packet).

(4) The present invention also has strong flexibility and applicability, can be used in various queuing switching structures supporting variable-length packets, and can flexibly configure parameters according to business types, so that the switching can achieve better performance.

Description of drawings

FIG. 1 is a schematic diagram of output scheduling of a cross-point buffered CICQ switching structure in an embodiment of the present invention.

FIG. 2 is a block diagram of an implementation of a cross point in an embodiment of the present invention.

FIG. 3 is a flowchart of a fair scheduling method in an embodiment of the present invention.

FIG. 4 is an implementation block diagram of a fair scheduler in an embodiment of the present invention.

Detailed ways

1 to 4, a credit-based proportional fair scheduling method supporting data packet switching, which includes the following steps:

(1) Configure the threshold parameters resvn, max, min (negative value), queue the input data packets at the CICQ intersection, and sort the packets according to the priority of the data packets in the buffer at the intersection. Each CICQ intersection Set up a counter and a comparator;

(2) Each intersection queue sends an application to the output scheduler according to the empty condition of the queue;

(3) The output scheduler selects the application with the highest priority to authorize arbitration. When the priority is the same, the polling method is used to authorize arbitration.

(4) Each column intersection is initially assigned the initial credit amount resvn (positive value), when there is a data packet output at the intersection point, the credit amount resvn is decremented by 1 every clock cycle until the credit amount resvn is negative;

(5) When the column intersection credit amount resvn is negative, it will borrow the initial credit amount of the intersection in the idle state, and the total borrowable amount is the sum of the credit amounts of all the intersection points in the idle state, and start to continue polling and arbitration. If the total credit of the column intersection with negative credit amount reaches the threshold min, then clear the credit value of all intersection queues, and return to step (1). Otherwise go to step (6).

(6) If the total borrowed credit reaches the sum of the credits of the intersections in the idle state, and there is no intersection credit resvn reaches the min value, the intersections with negative credits will each replenish the credits of the size of resvn once. Cross-point polling scheduling with positive credit (if only one port credit is positive after replenishment, and the port continues to send until it is negative), poll until the threshold (the value of step (3)) is reached again, and replenish again . Until the port credit reaches the min value. Reset start step (1).

As shown in Figure 1, the data packet enters the CICQ switching structure from the input port, and the data packet enters the corresponding cross point according to its target output port for buffering and queuing, and the data packet with the highest priority is queued at the top of the cross point. The fair scheduling process refers to a process in which data packets are scheduled from a certain column of N intersections to the buffer of output port N through output scheduling.

In Figure 1, output scheduling refers to selecting a cross point with data packets from a column of cross point buffers, and sending the front data packet queued at the cross point to the output port.

FIG. 2 is a block diagram of an implementation of a cross point in an embodiment of the present invention. According to the scheduling result, the scheduler interface module controls the data packet to apply to the fair scheduler according to the situation of the intersection, reads it from the cache according to the scheduling result of the scheduler, and feeds back the current state of the intersection to the scheduler.

FIG. 3 is a flowchart of a fair scheduling method in an embodiment of the present invention. Among them, the port is divided into five different states: _idle ( _idle ), _waking (waiting to wake up), wait (waiting), series (burst) and round (round). The states are defined as follows:

idle: Q _i =0 and c _i >0;

waking: Q _i =0 and c _i ≤ 0;

wait: Q _i > 0 and p _i <p;

series: Q _i >0 and c _i >0, p _i ≥p; (p is the priority of the first packet of other teams)

round: Q _i >0 and c _i ≤ 0, p _i ≥ p.

The output scheduler selects the application authorization arbitration with the highest priority, which means to compare the priority of the first data packet of each intersection, and select the highest priority as the scheduling result. When the highest priority data packets appear in the same column at the same time, multiple At the intersection point, round-robin arbitration is performed, and the fair scheduling mechanism is started.

In process 2, the idle state refers to the initial time when there is no data packet at the intersection, and the initial credit is allocated; the waking state is the state when the credit consumption becomes negative or 0.

The waiting state in process 3 indicates that there is a data packet at the intersection, but the priority of the data packet is lower than that of other intersection points, and the intersection needs to wait to send data packets.

FIG. 4 is an implementation block diagram of a fair scheduler in an embodiment of the present invention. The configuration module configures the three related parameters max, min and resvn of the algorithm. The parameters are defined as follows:

resvn: reserved credits, credits at each intersection in the initial state, and credits replenished at each intersection each time.

min: The minimum value that can be achieved by the credit of a single cross point. After reaching the minimum value, all ports are reset to the initial state. This value is a negative value.

max: The configurable maximum value of the resvn register.

The bandwidth allocation register determines the bandwidth that can be allocated by each cross-point according to the consumption and replenishment of each cross-point credit. The credit amount counting and updating module determines the increase and decrease of the credit amount according to the algorithm rules.

In this method, the max value is a positive value, the min value is a negative value, and the absolute values of the two numbers are equal. resvn is a positive value between max and 0. The meanings of the three parameters are: resvn represents the reserved credit amount, the credit amount of each intersection point in the initial state, and the credit amount supplemented each time at each intersection point. min indicates the minimum value that can be achieved by the credit of a single crosspoint. After reaching the minimum value, all ports are reset to the initial state. max indicates the configurable maximum value of the resvn register.

The update method of the credit amount described in step (4) is: when there is a data packet output at the intersection, the credit amount is subtracted by 1 in each clock cycle, until the data packet transmission is completed, or there is an update operation of the credit amount.

When there is only one cross point credit C _i > 0 and there are data packets, the cross point is in the series state, and the scheduler continuously schedules the cross point data packets until the state changes. When there are multiple cross-point credits C _i > 0 and there are data packets, these cross-points will be in the round state, and the scheduler will perform round-robin scheduling at these cross-points until the state changes.

The borrowed credits described in step (5) are updated in real time, and the sum value is updated when the intersection changes from the idle state to other states. For example, there is only one cross-point to send packets at the beginning, and the amount of borrowable credits is (N-1) times resvn. At this time, there are data packets waiting to be sent at another intersection, and the total available credits are immediately updated to (N-2) times resvn.

The amount of credit at the intersection of the idle state described in step (5) must be positive, and it cannot be borrowed when it is negative.

The intersections described in step (6) each replenish resvn once, which means that all intersections in the current state have data packets waiting to be sent (non-empty queues) to replenish the credit value. Specifically, first calculate the credit consumption at the intersection of the borrowing state in real time, and compare the sum of the credits at the intersection of the idle state. Intersections with negative credits are replenished, and each intersection is replenished with resvn.

The credit consumption of the borrow state intersection refers to the sum of the actual borrow amount of all borrow state intersections.

The sum of the credits of the idle state intersections refers to the sum of the credits that can be borrowed at the current column intersections. Its value is always greater than the sum of the actual borrowings.

This method sets the count boundary of the scheduler through configurable threshold parameters and initial credits, and based on the borrowing and replenishment mechanism of the credits of each independent intersection, it ensures that the data flow from each port can be The ratio enables fair sharing of output bandwidth among data streams on different ports.

In a word, the present invention aims at the problem that the output scheduling algorithm of the cross-point buffered CICQ switching structure may be allocated different service bandwidths for the data streams of different sources, which cannot be shared fairly. The boundary of bandwidth and allocable bandwidth is reserved, and the credit borrowing and replenishment mechanism is used to ensure that each data flow shares the bandwidth fairly. The method can also isolate the data flow to ensure that different service flows can enjoy the guaranteed bandwidth that they can enjoy. Even if there are malicious or highly bursty service flows, other normal service flows will not be affected.

Claims (3)

1. a credit-based proportional fair scheduling method supporting data packet exchange, characterized in that, comprising the following steps: (1) Queue the data packets at the CICQ intersection, and sort according to the priority of the data packets in the buffer at the intersection, and set a counter and a comparator for each CICQ intersection; (2) Each intersection queue sends an application to the output scheduler according to the empty condition of the queue; (3) The output scheduler selects the application with the highest priority to authorize arbitration, and the polling method is used to authorize arbitration when the priority is the same; (4) The initially assigned credit of each column intersection is a positive value resvn. When there is a data packet output at the intersection, the credit resvn is decremented by 1 every clock cycle until the credit resvn is negative; (5) When the credit amount resvn of the column intersection point is negative, the initial credit amount of the intersection point in the idle state is borrowed, and the total borrowable amount is the sum of the credit amounts of all the intersection points in the idle state, and the polling and arbitration continues; If the total credit of the column intersection with negative amount reaches the threshold min, the credit value of all intersection queues will be cleared, and return to step (1); if the total borrowed credit reaches the sum of the credit of the intersection in the idle state, and If there is no intersection credit amount resvn reaches the threshold min, then enter step (6); (6) Supplement a resvn-sized credit for the intersection with negative credit. If the credit of any port is positive after the supplement, the port will send continuous transmission until the credit of all ports is negative, and start polling , polling until the sum of the credits of the intersection of the idle state is reached again, and supplement it again; until the credit of a port reaches the min value, go back to step (1); after the credit resvn is negative, its credit When supplementing, only the credit value available at the intersection is provided, and the resvn value of the intersection is not modified. The update method of the resvn value at the intersection outputting data packets remains unchanged. 2 . A credit-based proportional fair scheduling method supporting data packet switching according to claim 1 , wherein in step (1), data packets are buffered at a CICQ intersection, and all data packets at the intersection The priority label is queued, the high-priority data packets are output before the low-priority data packets, and the data packets of the same priority are output according to the output scheduling result. 3. A credit-based proportional fair scheduling method for supporting data packet switching according to claim 1, wherein the resvn allocated for the cross point in step (4) is updated in real time, and the resvn update is based on a clock cycle of Unit, the settlement is updated at the end of each clock cycle.

Images