WO2025223244A1 - Packet reordering method and apparatus, and chip, device, storage medium and program product - Google Patents

Abstract

The present application relates to a packet reordering method and apparatus, and a device, a storage medium and a program product. The method comprises: receiving an out-of-order packet sent by a requester, wherein the out-of-order packet comprises a message sequence number and a packet sequence number; on the basis of the message sequence number and the packet sequence number, determining whether the out-of-order packet is in the current in-order delivery segment of a hardware processing engine of a network device; when the out-of-order packet is in the current in-order delivery segment, on the basis of the message sequence number and the packet sequence number, determining an ordering position of the out-of-order packet in a bitmap of queue pair context corresponding to the current in-order delivery segment; and adding marking information to the ordering position, so as to reorder the out-of-order packet.

Description

Message rearrangement methods, apparatuses, chips, devices, storage media, and program products

Related applications

This application claims priority to Chinese patent application No. 2024105011218, filed on April 24, 2024, entitled “Message Rearrangement Method, Apparatus, Chip, Device, Storage Medium and Program Product”, the entire contents of which are incorporated herein by reference.

Technical Field

This application relates to the field of chip technology, and in particular to a message rearrangement method, apparatus, chip, device, storage medium, and program product.

Background Technology

In emerging scenarios such as artificial intelligence and machine learning, network throughput is more important than network latency. The number of CPUs and GPUs operating is relatively small, but the individual traffic is large, requiring low tail latency per load. Because Remote Direct Memory Access over Converged Ethernet (ROCEV)2 does not support out-of-order transmission and reordering, ROCEV2 cannot solve the problem of high throughput and low tail latency.

In related technologies, some software can perform out-of-order reordering of the same queue pair (QP) for Remote Direct Memory Access (RDMA) through the processor or coprocessor.

However, since the sorting process of the processor or coprocessor requires contextual relationships, it needs to be done using a real-time clock (RTC). This makes it impossible to use multiple threads to complete the sorting for a single QP, which results in the inability to support large-scale out-of-order message correction.

Summary of the Invention

According to various embodiments of this application, a message rearrangement method, apparatus, device, storage medium, and program product are provided.

Firstly, this application provides a message rearrangement method. The method includes:

Receive out-of-order messages sent by the requesting end, wherein the out-of-order messages include message sequence number and packet sequence number;

Based on the message sequence number and the packet sequence number, determine whether the out-of-order message is within the current sorting delivery segment of the network device's hardware processing engine;

When the out-of-order message is within the current order delivery segment, the order position of the out-of-order message is determined in the bitmap of the queue management context corresponding to the current order delivery segment based on the message sequence number and packet sequence number.

The out-of-order messages are rearranged by adding marker information at the sorting positions.

In one embodiment, determining whether the out-of-order packet is within the current ordering delivery segment of the network device's hardware processing engine based on the message sequence number and packet sequence number includes:

If the difference between the message sequence number and the expected message sequence number is less than or equal to the number of maintainable messages of the hardware processing engine and the difference between the packet sequence number and the expected packet sequence number is less than or equal to the number of maintainable messages of the hardware processing engine, then the out-of-order message is determined to be within the current sorting delivery segment of the hardware processing engine.

If the difference between the message sequence number and the expected message sequence number is greater than the number of messages that the hardware processing engine can maintain, or if the difference between the packet sequence number and the expected packet sequence number is greater than the number of messages that the hardware processing engine can maintain, then it is determined that the out-of-order message is not in the current sorting delivery segment of the hardware processing engine.

In one embodiment, the expected message sequence number is the message sequence number corresponding to the first sorting position in the bitmap of the queue management context, and the expected packet sequence number is the packet sequence number corresponding to the first sorting position in the bitmap of the queue management context.

In one embodiment, after determining whether the out-of-order message is within the current ordering delivery segment of the network device's hardware processing engine based on the message sequence number and packet sequence number, the method further includes:

When the out-of-order message is not in the current sorting delivery segment of the hardware processing engine, a first out-of-order event message is reported to the micro-engine pool. The first out-of-order event message includes the out-of-order message. The micro-engine pool is used to call the host memory to sort the out-of-order message.

In one embodiment, after rearranging the out-of-order packets by adding marker information at the sorting position, the method further includes:

The bitmap of the queue management context is moved according to the added marker information in the bitmap of the queue management context;

When the bitmap of the queue management context moves from the current sorting delivery segment to the next sorting delivery segment and the first out-of-order event message has been reported, a second out-of-order event message is reported to the micro-engine pool. The second out-of-order event message is used to request the micro-engine pool to release the first sorting information of the out-of-order packets corresponding to the next sorting delivery segment.

In one embodiment, after reporting the second out-of-order event message to the micro-engine pool, the method further includes:

Receive the first sorting information sent by the micro-engine pool;

The first sorting information is bitwise ORed with the second sorting information in the bitmap of the queue management context corresponding to the next sorting delivery segment to update the bitmap of the queue management context corresponding to the next sorting delivery segment.

Secondly, this application provides a message rearrangement apparatus. The apparatus includes:

The receiving module is used to receive out-of-order messages sent by the requesting end, wherein the out-of-order messages include message sequence numbers and packet sequence numbers;

The processing module is configured to determine whether the out-of-order packet is within the current sorting and delivery segment of the hardware processing engine of the network device based on the message sequence number and the packet sequence number; if the out-of-order packet is within the current sorting and delivery segment, the module determines the sorting position of the out-of-order packet in the bitmap of the queue management context corresponding to the current sorting and delivery segment based on the message sequence number and the packet sequence number.

The rearrangement module is used to rearrange the out-of-order packets by adding marker information at the sorting positions.

In one embodiment, the processing module is further configured to: determine that the out-of-order message is within the current sorting and delivery segment of the hardware processing engine when the difference between the message sequence number and the expected message sequence number is less than or equal to the number of maintainable messages of the hardware processing engine and the difference between the packet sequence number and the expected packet sequence number is less than or equal to the number of maintainable messages of the hardware processing engine; and determine that the out-of-order message is not within the current sorting and delivery segment of the hardware processing engine when the difference between the message sequence number and the expected message sequence number is greater than the number of maintainable messages of the hardware processing engine or the difference between the packet sequence number and the expected packet sequence number is greater than the number of maintainable messages of the hardware processing engine.

In one embodiment, the expected message sequence number is the message sequence number corresponding to the first sorting position in the bitmap of the queue management context, and the expected packet sequence number is the packet sequence number corresponding to the first sorting position in the bitmap of the queue management context.

In one embodiment, the processing module is further configured to report a first out-of-order event message to the micro-engine pool when the out-of-order message is not in the current sorting delivery segment of the hardware processing engine. The first out-of-order event message includes the out-of-order message, and the micro-engine pool is configured to call the host memory to sort the out-of-order message.

In one embodiment, the processing module is further configured to move the bitmap of the queue management context according to the added tag information in the bitmap of the queue management context; when the bitmap of the queue management context moves from the current sorting delivery segment to the next sorting delivery segment and the first out-of-order event message has been reported, a second out-of-order event message is reported to the micro-engine pool, the second out-of-order event message being used to request the micro-engine pool to release the first sorting information of the out-of-order packets corresponding to the next sorting delivery segment.

In one embodiment, the receiving module is further configured to receive the first sorting information sent by the micro-engine pool;

The processing module is further configured to perform a bitwise OR operation between the first sorting information and the second sorting information in the bitmap of the queue management context corresponding to the next sorting delivery segment, so as to update the bitmap of the queue management context corresponding to the next sorting delivery segment.

Thirdly, this application provides a chip. The chip includes a memory and a processor, the memory storing a computer program, and the processor executing the computer program to implement the message reordering method of the first aspect described above.

Fourthly, this application also provides a computer device. The computer device includes a processor and a chip as described in the third aspect, the chip being configured to schedule messages to the processor or to process them itself, the processor being configured to process messages scheduled by the chip.

Fifthly, this application also provides a computer-readable storage medium. The computer-readable storage medium stores a computer program thereon, which, when executed by a processor, implements a message reordering method.

Sixthly, this application also provides a computer program product. The computer program product includes a computer program that, when executed by a processor, implements a message reordering method.

Details of one or more embodiments of this application are set forth in the following drawings and description. Other features, objects, and advantages of this application will become apparent from the specification, drawings, and claims.

Attached Figure Description

To more clearly illustrate the technical solutions in the embodiments of this application or the conventional technology, the drawings used in the description of the embodiments or the conventional technology will be briefly introduced below. Obviously, the drawings described below are only embodiments of this application. For those skilled in the art, other drawings can be obtained based on the disclosed drawings without creative effort.

Figure 1 is a schematic diagram of the application environment of a message rearrangement method provided in an embodiment of this application;

Figure 2 is a flowchart illustrating a message rearrangement method provided in an embodiment of this application;

Figure 3 is a schematic diagram of a packet-by-packet equalization implementation provided by an embodiment of this application;

Figure 4 is a bit diagram of a micro-engine pool before update provided in an embodiment of this application;

Figure 5 is an updated bit diagram corresponding to a micro-engine pool provided in an embodiment of this application;

Figure 6 is a bit diagram of a queue management context provided in an embodiment of this application;

Figure 7 is a bit diagram of another queue management context provided in an embodiment of this application;

Figure 8 is a bit diagram corresponding to another micro-engine pool provided in the embodiment of this application;

Figure 9 is a bit diagram of the next sorting delivery segment corresponding to a micro-engine pool provided in an embodiment of this application;

Figure 10 is a bit diagram of another queue management context provided in an embodiment of this application;

Figure 11 is a bit diagram of another queue management context provided in an embodiment of this application;

Figure 12 is a schematic diagram illustrating the principle of message reordering provided in an embodiment of this application;

Figure 13 is an interactive schematic diagram of message rearrangement provided in an embodiment of this application;

Figure 14 is a flowchart illustrating another message rearrangement method provided in an embodiment of this application;

Figure 15 is a schematic diagram of a message rearrangement device provided in an embodiment of this application;

Figure 16 is a schematic diagram of the internal structure of a computer device provided in an embodiment of this application.

Detailed Implementation

The technical solutions of the embodiments of this application will be clearly and completely described below with reference to the accompanying drawings. Obviously, the described embodiments are only some embodiments of this application, and not all embodiments. Based on the embodiments of this application, all other embodiments obtained by those skilled in the art without creative effort are within the scope of protection of this application.

The following section will first explain the application environment of the message rearrangement method.

The message reordering method provided in this application embodiment can be applied to network devices. Figure 1 is a schematic diagram of the application environment of a message reordering method provided in this application embodiment. As shown in Figure 1, the network device may include a requesting end 101 and a receiving end 102. The requesting end 101 on one network device can send an out-of-order message to the receiving end 102 on another network device. The out-of-order message includes a message sequence number and a packet sequence number. Subsequently, the receiving end 102 determines whether the out-of-order message is within the current ordering delivery segment of the network device's hardware processing engine based on the message sequence number and the packet sequence number. When the out-of-order message is within the current ordering delivery segment, the receiving end 102 determines the ordering position of the out-of-order message in the bitmap of the queue management context corresponding to the current ordering delivery segment based on the message sequence number and the packet sequence number. Subsequently, the receiving end 102 reorders the out-of-order message by adding marking information to the ordering position. When an out-of-order packet is not within the current ordering delivery segment of the hardware processing engine, the receiver 102 reports a first out-of-order event message to the network device's micro-engine pool 103. This first out-of-order event message includes the out-of-order packet, and the micro-engine pool uses host memory to order the out-of-order packet. The micro-engine pool can be a processor module of the network device. The host can be the network device's system (e.g., operating system).

It should be understood that the embodiments of this application do not limit the network devices. In some embodiments, the network devices may include network interface cards (NICs), etc.

In one embodiment, as shown in Figure 2, a message rearrangement method is provided. Taking the application of this method to the receiving end in Figure 1 as an example, the method includes S201-S204:

S201. Receive out-of-order messages sent by the requesting end. The out-of-order messages include message sequence number and packet sequence number.

In this application, when the requester supports out-of-order message delivery, the requester can send out-of-order messages to the responder so that the responder can rearrange the out-of-order messages.

The Message Sequence Number (MSN) and Packet Sequence Number (PSN) mentioned above are descriptors for out-of-order messages.

It should be understood that in RDMA, there is a concept of a message, and a message can include one or more packets (PKTs). Accordingly, when the requesting end sends an out-of-order message, it can attach a message sequence number (MSN) and a packet sequence number (PSN), so that the receiving end can reorder the out-of-order message based on the MSN and PSN.

In some embodiments, out-of-order packets are generated when a network interface card (NIC) or switch dynamically load balances and swaps source packets to multiple transmission paths.

It should be understood that dynamic load balancing is a core networking solution used to distribute traffic among multiple servers in a server farm. Load balancing improves application availability and responsiveness and prevents server overload. The load balancing service sits between client devices and backend servers, receiving incoming requests and then distributing them to any available server capable of fulfilling those requests.

For example, a web server typically has multiple workers (e.g., processes or threads). When multiple clients connect to the same worker, that worker becomes busy and experiences significant tail latency, while other workers remain idle. To reduce overall resource utilization and lower the performance requirements of the web server, dynamic load balancing can be used to prevent multiple clients from connecting to the same worker.

Figure 3 is a schematic diagram of packet-by-packet load balancing provided in an embodiment of this application. As shown in Figure 3, in this application, source packets can be switched to multiple transmission paths by network interface cards or switches through dynamic load balancing, reducing the tail latency of a single stream and greatly shortening the single stream transmission completion time.

For example, when implementing packet-by-packet load balancing through dynamic load balancing using a switch, the out-of-order transmission path (PATH) can be determined by the switch using a key hash factor. This key hash factor can include source IP address, source IP address + destination IP address, source IP address + destination IP address + source port number + destination port number, etc.

For example, when implementing packet-by-packet load balancing through dynamic load balancing via the network interface card, the source port number of the User Datagram Protocol (UDP) (e.g., UDP.SPORT) can be modified, and the lower 16 bits of the Packet Sequence Number (PSN) can be used as the UDP source port number, thereby exchanging source packets to different paths through the modified UDP source port number.

In this application, based on packet-by-packet distribution ordering, network interface cards (NICs) or switches can better utilize dynamic load balancing algorithms for various types of traffic, avoiding the unbalanced effects caused by single large flows or equal-cost multi-path (ECMP) routing of multiple flows in the network.

S202. Based on the message sequence number and packet sequence number, determine whether the out-of-order message is within the current ordering delivery segment of the network device's hardware processing engine.

In this step, after the receiving end receives the out-of-order message sent by the requesting end, it can determine whether the out-of-order message is within the current ordering delivery segment of the network device's hardware processing engine based on the message sequence number and packet sequence number.

The hardware processing engine can be an RDMA Processing Engine (RPE).

The currently sorted delivery segment is the sequence of messages currently being sorted.

In some embodiments, out-of-order packets corresponding to the current ordering delivery segment are aligned before the out-of-order packets corresponding to the next ordering delivery segment are aligned. That is, in each ordering delivery segment, the hardware processing engine only maintains the out-of-order packets for which packets are expected to be received.

It should be understood that the embodiments of this application do not impose restrictions on how to determine whether an out-of-order message is within the current sorting and delivery segment of the hardware processing engine of the network device. In some embodiments, when the difference between the message sequence number and the expected message sequence number is less than or equal to the number of messages that the hardware processing engine can maintain and the difference between the packet sequence number and the expected packet sequence number is less than or equal to the number of messages that the hardware processing engine can maintain, it is determined that the out-of-order message is within the current sorting and delivery segment of the hardware processing engine.

For example, if the MSN-Expected Message Sequence Number (EPSN) ≤ X and the PSN-Expected Packet Sequence Number (EPSN) ≤ n, the receiver can determine that the out-of-order message is within the current ordered delivery segment of the hardware processing engine. Accordingly, the ordering position of the out-of-order message can be determined in the bitmap of the Queue Pair Context (QPC) corresponding to the current ordered delivery segment. Here, X is the number of maintainable messages in the hardware processing engine, and n is the number of maintainable packets in the hardware processing engine.

In other embodiments, if the difference between the message sequence number and the expected message sequence number is greater than the number of messages that the hardware processing engine can maintain, or the difference between the packet sequence number and the expected packet sequence number is greater than the number of messages that the hardware processing engine can maintain, then it is determined that the out-of-order message is not in the current sorting delivery segment of the hardware processing engine.

For example, when MSN-EMSN > X, or PSN-EPSN > n, the receiver can determine that the out-of-order message is not within the current ordering delivery segment of the hardware processing engine. Here, X is the maintainable message count of the hardware processing engine, and n is the maintainable message count of the hardware processing engine.

It should be understood that the embodiments of this application do not limit how the expected message sequence number and the expected packet sequence number are determined. In some embodiments, the expected message sequence number is the message sequence number corresponding to the first sorting position in the bitmap of the queue management context, and the expected packet sequence number is the packet sequence number corresponding to the first sorting position in the bitmap of the queue management context.

It should be understood that the embodiments of this application do not limit the number of maintainable messages and maintainable packets of the hardware processing engine, and can be specifically set according to hardware resources and/or system round-trip time (RTT).

For example, based on hardware resources and system RTT, 64, 128, or 256 can be selected as the maintainable message count for the hardware processing engine. For example, based on hardware resources, 2, 4, 8, or 16 can be selected as the maintainable message count for the hardware processing engine. For example, the ordered delivery segment can be further subdivided into sub-segments; for instance, an ordered delivery segment of length n can be divided into m sub-segments, where m is 4 or 8.

S203. When an out-of-order message is within the current ordering delivery segment, the ordering position of the out-of-order message is determined in the bitmap of the queue management context corresponding to the current ordering delivery segment based on the message sequence number and packet sequence number.

In this step, once it is determined that the out-of-order message is within the current ordering delivery segment, the ordering position of the out-of-order message can be determined in the bitmap of the queue management context corresponding to the current ordering delivery segment based on the message sequence number and packet sequence number.

In some embodiments, the position of the corresponding message can be located in the bitmap first based on the message sequence number, and then the position of the corresponding packet can be located in the bitmap based on the packet sequence number, thereby determining the sorting position of the out-of-order messages.

For example, when the current sorted delivery segment has an MSN of 0 and an iPSN of 1 to 15, out-of-order messages with an MSN of 0 and an iPSN of 1 to 15 do not need to be sent to the micro-engine pool for processing. It is only necessary to determine the corresponding bit in the QPC bitmap and mark the corresponding bit with 1 to indicate that the out-of-order message has been received and sorted.

In other embodiments, when an out-of-order message is not in the current sorting delivery segment of the hardware processing engine, a first out-of-order event message is reported to the micro-engine pool. The first out-of-order event message includes the out-of-order message, and the micro-engine pool is used to call the host memory to sort the out-of-order message.

In some embodiments, a bitmap table can also be maintained in the micro-engine pool. Whenever the micro-engine pool receives the first out-of-order event message, it can determine the sorting position of the out-of-order message in the bitmap table corresponding to the micro-engine pool. Then, the bit of the sorting position is set to 1 to complete the sorting.

For example, when the current sorting delivery segment corresponds to MSN 0 and iPSN is 1 to 15, the hardware processing engine cannot sort out-of-order packets when the received MSN is equal to 0 and the iPSN is greater than 16, or when the MSN is not equal to 0. In this case, the hardware processing engine can send a first out-of-order event message to the micro-engine pool to enable the micro-engine pool to sort the out-of-order packets.

The message reordering method provided in this application embodiment, through the bitmap table maintained by the micro-engine pool, can realize a software-hardware combined reordering scheme of the micro-engine pool and the hardware processing engine. Compared with related technologies, the software-hardware combined reordering scheme provides both the line-speed sorting processing capability of the hardware processing engine and the flexible sorting extension capability based on the micro-engine pool microcode, thereby effectively controlling hardware resources and costs.

Furthermore, compared to existing solutions, the hardware processing engine at the reordering end aggregates the received out-of-order messages. After receiving a complete out-of-order message within the current ordering delivery segment, it interacts with the micro-engine pool once. During this interaction, the micro-engine pool sends the first ordering information of the out-of-order messages corresponding to the next ordering delivery segment that exceeds the out-of-order level of the hardware processing engine to the hardware processing engine. This allows the hardware processing engine to perform a bitwise OR operation with the second ordering information in the bitmap of the queue management context corresponding to the next ordering delivery segment to sort the out-of-order messages corresponding to the next ordering delivery segment, thereby accelerating the sorting speed of out-of-order messages.

Figure 4 shows the bitmap before update for a micro-engine pool according to an embodiment of this application, and Figure 5 shows the updated bitmap for a micro-engine pool according to an embodiment of this application. As shown in Figures 4 and 5, when the current sorted delivery segment has MSN 0 and iPSN 1 to 15, out-of-order packets with MSN 0 and iPSN 17, MSN 0 and iPSN 32, and MSN 1 and iPSN 0 are not in the current sorted delivery segment. A corresponding first out-of-order event message can be generated and reported to the micro-engine pool. The sorting is then updated in the bitmap table corresponding to the micro-engine pool, so that the bitmap table corresponding to the micro-engine pool shown in Figure 4 is updated to the bitmap table corresponding to the micro-engine pool shown in Figure 5.

For example, out-of-order packets received beyond the expected order can be sent to the micro-engine pool for sorting, within the space of the micro-engine pool's maximum maintainable bitmap of size z. Where msn - emsn < y.

The bitmap maintained by the engine pool uses memory at double the system data rate (DDR). z is typically greater than n, for example, 256 or 384. y represents the total number of messages that the memory can maintain, for example, 8, 16, or 32.

For example, if msn-emsn≥y or psn-epsn≥z, the out-of-order message exceeds the system's processing capacity and can be discarded directly, and subsequently recovered through relevant protocols (e.g., the go-back-n protocol).

In some embodiments, after reordering out-of-order packets by adding marker information at the sorting position, the bitmap of the queue management context can be moved according to the marker information already added to the bitmap of the queue management context.

For example, the bitmap of the queue management context can be shifted based on the length of the sub-segments in the current ordered delivery segment. If the length of the current ordered delivery segment is 16, the previous ordered delivery segment can be divided into 4 sub-segments, each corresponding to 4 bits. Then, after setting the first 4 bits to 1 to add marker information, the bitmap of the queue management context can be shifted 4 bits.

For example, Figure 6 is a bitmap of a queue management context provided in an embodiment of this application, and Figure 7 is a bitmap of another queue management context provided in an embodiment of this application. When the hardware processing engine receives an out-of-order message with MSN of 0 and iPSN of 0, the bitmap of the queue management context is as shown in Figure 6. At this time, the bits with MSN of 0 and iPSN of 0 in the bitmap of the queue management context can be set to 1, so that the first 4 bits are all set to 1. At this time, as shown in Figure 7, the bitmap of the queue management context can be shifted left by 4 bits, so that the first bit becomes MSN of 0 and iPSN of 4.

It should be noted that, due to the shifting of the bitmap of the queue management context, the message sequence number and packet sequence number corresponding to the first sorted position in the bitmap of the queue management context will also change. Consequently, out-of-order messages that were not originally in the current sorted delivery segment may become part of the current sorted delivery segment.

For example, after the message sequence number and packet sequence number corresponding to the first sorting position are changed from MSN 0 and iPSN 0 to MSN 0 and iPSN 4, out-of-order messages with MSN 0 and iPSN 16-19 are changed from not being in the current sorting delivery segment to being in the current sorting delivery segment.

In some embodiments, when the bitmap of the queue management context moves from the current sorted delivery segment to the next sorted delivery segment and a first out-of-order event message has been reported, a second out-of-order event message is reported to the micro-engine pool. The second out-of-order event message is used to request the micro-engine pool to release the first sorting information of the out-of-order packets corresponding to the next sorted delivery segment.

For example, when the current sorted delivery segment corresponds to out-of-order packets with MSN 0 and iPSNs 1 to 15, the current sorted delivery segment can move to the next sorted delivery segment when MSN 0 and iPSNs 1 to 16 are reached. The next sorted delivery segment corresponds to out-of-order packets with MSN 0 and iPSNs 16 to 31. At this time, if the bitmap corresponding to the micro-engine pool is as shown in Figure 8, the bitmap corresponding to the next sorted delivery segment with MSN 0 and iPSNs 16 to 31, as shown in Figure 9, can be sent to the hardware processing engine.

In other embodiments, after reporting the second out-of-order event message to the micro-engine pool, first sorting information sent by the micro-engine pool can be received. Subsequently, the first sorting information is bitwise ORed with the second sorting information in the bitmap of the queue management context corresponding to the next sorted delivery segment to update the bitmap of the queue management context corresponding to the next sorted delivery segment.

For example, when the microengine pool sends a bitmap corresponding to the next sorted delivery segment (as shown in Figure 9) with an MSN of 0 and an iPSN of 16 to 31 to the hardware processing engine, the hardware processing engine can perform a bitwise OR operation between the bitmap of the queue management context (as shown in Figure 10) and the bitmap sent by the microengine pool to obtain the bitmap of the queue management context (as shown in Figure 11).

Figure 12 is a schematic diagram of the principle of message reordering provided in an embodiment of this application. As shown in Figure 12, the message reordering method provided in this embodiment of the application greatly reduces the number of messages sent to the micro-engine pool for processing by adopting hardware segmented sorting. Furthermore, the micro-engine pool uses the system's memory to reduce hardware overhead, achieving the ability to improve system performance while achieving feasibility, thereby possessing the ability of system line-speed sorting.

S204. Reorder out-of-order messages by adding marker information to the sorting position.

In this step, once the sorting position of out-of-order packets is determined, the out-of-order packets can be rearranged by adding marker information to the sorting position.

It should be understood that reordering out-of-order packets allows the data of the out-of-order packets to be written directly to the host's buffer via the address specified in the packet header, requiring only the sorting of the packet descriptors. That is, marking information is added to the sorting positions corresponding to the descriptors in the bitmap; this marking information could, for example, set the bit at the sorting position to 1.

Referring again to Figure 12, after the hardware processing engine completes the sorting of out-of-order packets, it can return an acknowledgment request to the receiving end based on the maintenance information. Furthermore, the receiving end can report the Completion Queue Entry (CQE) to the host based on the opcode.

The interactive events during the message reordering process are described below. Figure 13 is a schematic diagram of message reordering interaction provided in an embodiment of this application. As shown in Figure 13, after the requesting end sends an out-of-order message to the receiving end, if the out-of-order message is not within the current ordering delivery segment, the hardware processing engine can report a first out-of-order event message to the micro-engine pool. When the first out-of-order event message has been reported and the bitmap of the queue management context moves to the next ordering delivery segment, the hardware processing engine can report a second out-of-order event message to the micro-engine pool. The formats of the first and second out-of-order event messages can be as shown in Table 1.

Table 1

Subsequently, upon receiving the second out-of-order event message, the microengine can send a response message. This response message can release the first ordering information of the out-of-order packets corresponding to the next ordering delivery segment to the hardware processing engine, thereby synchronizing the corresponding bitmap of the microengine. The format of the response message can be shown in Table 2.

Table 2

In this application, based on the sorting capabilities of the hardware processing engine, it can support processing one sort per sorting delivery segment at the fastest, with performance far exceeding that of sorting based on processor cores. This meets the sorting capability requirements of various data centers now and in the future, providing effective bandwidth for the entire data center. Simultaneously, the sorting scheme based on the hardware processing engine and micro-engine pool provides support for large-scale out-of-order correction capabilities, offers a degree of flexibility, and reduces the overall cost of the reordering scheme.

The message reordering method provided in this application first receives an out-of-order message sent by the requesting end. The out-of-order message includes a message sequence number and a packet sequence number. Then, based on the message sequence number and packet sequence number, it is determined whether the out-of-order message is within the current ordering delivery segment of the network device's hardware processing engine. If the out-of-order message is within the current ordering delivery segment, its ordering position is determined in the bitmap of the queue management context corresponding to the current ordering delivery segment based on the message sequence number and packet sequence number. Finally, the out-of-order message is reordered by adding marker information to the ordering position. Because hardware segmented ordering is used, the number of messages sent to the microprocessor pool for processing is greatly reduced, and hardware overhead is also reduced. This achieves message reordering feasibility while improving message reordering performance, thereby supporting large-scale out-of-order message correction.

Figure 14 is a flowchart illustrating another message rearrangement method provided in an embodiment of this application. As shown in Figure 14, the message rearrangement method includes steps S301-S310:

S301. Receive out-of-order messages sent by the requesting end. The out-of-order messages include message sequence number and packet sequence number.

In some embodiments, out-of-order packets are generated when a network interface card (NIC) or switch dynamically load balances and swaps source packets to multiple transmission paths.

S302. Based on the message sequence number and packet sequence number, determine whether the out-of-order message is within the current ordering delivery segment of the network device's hardware processing engine.

If yes, then execute S304; otherwise, execute S303.

In some embodiments, when the difference between the message sequence number and the expected message sequence number is less than or equal to the number of messages that the hardware processing engine can maintain and the difference between the packet sequence number and the expected packet sequence number is less than or equal to the number of messages that the hardware processing engine can maintain, it is determined that the out-of-order message is within the current sorting delivery segment of the hardware processing engine.

In some embodiments, if the difference between the message sequence number and the expected message sequence number is greater than the number of messages that the hardware processing engine can maintain, or the difference between the packet sequence number and the expected packet sequence number is greater than the number of messages that the hardware processing engine can maintain, then it is determined that the out-of-order message is not in the current sorting delivery segment of the hardware processing engine.

S303. Report the first out-of-order event message to the micro-engine pool. The first out-of-order event message includes out-of-order packets, which the micro-engine pool uses to call the host memory to sort the out-of-order packets.

S304. Based on the message sequence number and packet sequence number, determine the order position of the out-of-order message in the bitmap of the queue management context corresponding to the current order delivery segment.

S305. Reorder out-of-order messages by adding marker information to the sorting position.

S306. Move the bitmap of the queue management context according to the added marker information in the bitmap of the queue management context.

S307. Determine whether the bitmap of the queue management context has been moved from the current sorted delivery segment to the next sorted delivery segment and whether the first out-of-order event message has been reported.

If yes, then execute S301; otherwise, execute S308.

S308, then report the second out-of-order event message to the micro-engine pool. The second out-of-order event message is used to request the micro-engine pool to release the first ordering information of the out-of-order message corresponding to the next ordering delivery segment.

S309, Receive the first sorting information sent by the micro-engine pool.

S310. Perform a bitwise OR operation between the first sorting information and the second sorting information in the bitmap of the queue management context corresponding to the next sorting delivery segment to update the bitmap of the queue management context corresponding to the next sorting delivery segment.

The message reordering method provided in this application first receives an out-of-order message sent by the requesting end. The out-of-order message includes a message sequence number and a packet sequence number. Then, based on the message sequence number and packet sequence number, it is determined whether the out-of-order message is within the current ordering delivery segment of the network device's hardware processing engine. If the out-of-order message is within the current ordering delivery segment, its ordering position is determined in the bitmap of the queue management context corresponding to the current ordering delivery segment based on the message sequence number and packet sequence number. Finally, the out-of-order message is reordered by adding marker information to the ordering position. Because hardware segmented ordering is used, the number of messages sent to the microprocessor pool for processing is greatly reduced, and hardware overhead is also reduced. This achieves message reordering feasibility while improving message reordering performance, thereby supporting large-scale out-of-order message correction.

It should be understood that although the steps in the flowcharts of the above embodiments are shown sequentially according to the arrows, these steps are not necessarily executed in the order indicated by the arrows. Unless explicitly stated herein, there is no strict order restriction on the execution of these steps, and they can be executed in other orders. Moreover, at least some steps in the flowcharts of the above embodiments may include multiple steps or multiple stages. These steps or stages are not necessarily completed at the same time, but can be executed at different times. The execution order of these steps or stages is not necessarily sequential, but can be performed alternately or in turn with other steps or at least some of the steps or stages of other steps.

Based on the same concept, this application also provides a message reordering apparatus for implementing the message reordering method described above. The solution provided by this apparatus is similar to the implementation described in the above method; therefore, the specific limitations in one or more message reordering apparatus embodiments provided below can be found in the limitations of the message reordering method described above, and will not be repeated here.

In one embodiment, as shown in FIG15, a message rearrangement apparatus 400 is provided, including: a receiving module 401, a processing module 402, and a rearrangement module 403, wherein:

The receiving module 401 is used to receive out-of-order messages sent by the requesting end. The out-of-order messages include message sequence numbers and packet sequence numbers.

The processing module 402 is used to determine whether an out-of-order packet is within the current sorting and delivery segment of the network device's hardware processing engine based on the message sequence number and packet sequence number; if the out-of-order packet is within the current sorting and delivery segment, the processing module 402 determines the sorting position of the out-of-order packet in the bitmap of the queue management context corresponding to the current sorting and delivery segment based on the message sequence number and packet sequence number.

The rearrangement module 403 is used to rearrange out-of-order packets by adding marker information at the sorting position.

In one embodiment, the processing module 402 is further configured to determine that the out-of-order message is within the current sorting and delivery segment of the hardware processing engine when the difference between the message sequence number and the expected message sequence number is less than or equal to the number of maintainable messages of the hardware processing engine and the difference between the packet sequence number and the expected packet sequence number is less than or equal to the number of maintainable messages of the hardware processing engine; and to determine that the out-of-order message is not within the current sorting and delivery segment of the hardware processing engine when the difference between the message sequence number and the expected message sequence number is greater than the number of maintainable messages of the hardware processing engine or the difference between the packet sequence number and the expected packet sequence number is greater than the number of maintainable messages of the hardware processing engine.

In one embodiment, the expected message sequence number is the message sequence number corresponding to the first sorting position in the bitmap of the queue management context, and the expected packet sequence number is the packet sequence number corresponding to the first sorting position in the bitmap of the queue management context.

In one embodiment, the processing module 402 is further configured to report a first out-of-order event message to the micro-engine pool when the out-of-order message is not in the current sorting delivery segment of the hardware processing engine. The first out-of-order event message includes the out-of-order message, and the micro-engine pool is used to call the host memory to sort the out-of-order message.

In one embodiment, the processing module 402 is further configured to move the bitmap of the queue management context according to the added marker information in the bitmap of the queue management context; when the bitmap of the queue management context moves from the current sorting delivery segment to the next sorting delivery segment and a first out-of-order event message has been reported, a second out-of-order event message is reported to the micro-engine pool. The second out-of-order event message is used to request the micro-engine pool to release the first sorting information of the out-of-order message corresponding to the next sorting delivery segment.

In one embodiment, the receiving module 401 is further configured to receive first sorting information sent by the micro-engine pool.

The processing module 402 is further configured to perform a bitwise OR operation between the first sorting information and the second sorting information in the bitmap of the queue management context corresponding to the next sorting delivery segment, so as to update the bitmap of the queue management context corresponding to the next sorting delivery segment.

Each module in the aforementioned message rearrangement device can be implemented entirely or partially through software, hardware, or a combination thereof. These modules can be embedded in the processor of a computer device in hardware form or independent of it, or stored in the memory of the computer device in software form, so that the processor can call and execute the operations corresponding to each module.

In one embodiment, a computer device is provided, which may be a server. The server has a network interface card (NIC) with a chip. The internal structure of the server can be shown in Figure 16. The computer device includes a processor, memory, input/output (I/O) interfaces, and a communication interface. The processor, memory, and I/O interfaces are connected via a system bus, and the communication interface is connected to the system bus via the I/O interfaces. The processor provides computing and control capabilities. The memory includes non-volatile storage media and internal memory. The non-volatile storage media stores the operating system, computer programs, and a database. The internal memory provides an environment for the operation of the operating system and computer programs stored in the non-volatile storage media. The database stores data. The I/O interfaces are used for exchanging information between the processor and external devices. The communication interface is used for communicating with external terminals via a network connection. Those skilled in the art will understand that the structure shown in Figure 16 is merely a block diagram of a portion of the structure related to the present application and does not constitute a limitation on the computer device to which the present application is applied. Specific computer devices may include more or fewer components than those shown in the figure, or combine certain components, or have different component arrangements.

In one embodiment, a chip is provided. The chip includes a memory and a processor, the memory storing a computer program, and the processor executing the computer program to implement the aforementioned message reordering method. The chip may be a data processing unit (DPU) chip.

In one embodiment, a computer device is provided. The computer device includes a processor and the chip provided in the foregoing embodiment. The chip is used to schedule packets to the processor or to process them itself. The processor is used to process packets scheduled by the chip. The computer device may be a server, a server cluster, etc.

In one embodiment, a computer-readable storage medium is provided having a computer program stored thereon, which, when executed by a processor, implements the above-described message reordering method.

In one embodiment, a computer program product is provided, including a computer program that, when executed by a processor, implements the above-described message rearrangement method.

Those skilled in the art will understand that all or part of the processes in the methods of the above embodiments can be implemented by a computer program instructing related hardware. The computer program can be stored in a non-volatile computer-readable storage medium. When executed, the computer program can include the processes of the embodiments of the above methods. Any references to memory, databases, or other media used in the embodiments provided in this application can include at least one of non-volatile and volatile memory. Non-volatile memory can include read-only memory (ROM), magnetic tape, floppy disk, flash memory, optical memory, high-density embedded non-volatile memory, resistive random access memory (ReRAM), magnetic random access memory (MRAM), ferroelectric random access memory (FRAM), phase change memory (PCM), graphene memory, etc. Volatile memory can include random access memory (RAM) or external cache memory, etc. By way of illustration and not limitation, RAM can take many forms, such as Static Random Access Memory (SRAM) or Dynamic Random Access Memory (DRAM). The databases involved in the embodiments provided in this application may include at least one type of relational database and non-relational database. Non-relational databases may include, but are not limited to, blockchain-based distributed databases. The processors involved in the embodiments provided in this application may be general-purpose processors, central processing units, graphics processing units, digital signal processors, programmable logic devices, quantum computing-based data processing logic devices, etc., and are not limited to these.

The technical features of the above embodiments can be combined in any way. For the sake of brevity, not all possible combinations of the technical features in the above embodiments are described. However, as long as there is no contradiction in the combination of these technical features, they should be considered to be within the scope of this specification.

The above embodiments are merely illustrative of several implementation methods of this application, and their descriptions are relatively specific and detailed. However, they should not be construed as limiting the scope of this application. It should be noted that those skilled in the art can make various modifications and improvements without departing from the concept of this application, and these all fall within the protection scope of this application. Therefore, the protection scope of this application should be determined by the appended claims.

Claims (15)

A message rearrangement method, characterized in that the method includes: Receive out-of-order messages sent by the requesting end, wherein the out-of-order messages include message sequence number and packet sequence number; Based on the message sequence number and the packet sequence number, determine whether the out-of-order message is within the current sorting delivery segment of the network device's hardware processing engine; When the out-of-order message is within the current order delivery segment, the order position of the out-of-order message is determined in the bitmap of the queue management context corresponding to the current order delivery segment based on the message sequence number and packet sequence number. The out-of-order messages are rearranged by adding marker information at the sorting positions. The method according to claim 1, characterized in that, determining whether the out-of-order packet is within the current sorting delivery segment of the hardware processing engine of the network device based on the message sequence number and the packet sequence number includes: If the difference between the message sequence number and the expected message sequence number is less than or equal to the number of maintainable messages of the hardware processing engine and the difference between the packet sequence number and the expected packet sequence number is less than or equal to the number of maintainable messages of the hardware processing engine, then the out-of-order message is determined to be within the current sorting delivery segment of the hardware processing engine. If the difference between the message sequence number and the expected message sequence number is greater than the number of messages that the hardware processing engine can maintain, or if the difference between the packet sequence number and the expected packet sequence number is greater than the number of messages that the hardware processing engine can maintain, then it is determined that the out-of-order message is not in the current sorting delivery segment of the hardware processing engine. According to the method of claim 2, the expected message sequence number is the message sequence number corresponding to the first sorting position in the bitmap of the queue management context, and the expected packet sequence number is the packet sequence number corresponding to the first sorting position in the bitmap of the queue management context. The method according to claim 1, characterized in that, after determining whether the out-of-order message is within the current ordering delivery segment of the hardware processing engine of the network device based on the message sequence number and the packet sequence number, the method further includes: When the out-of-order message is not in the current sorting delivery segment of the hardware processing engine, a first out-of-order event message is reported to the micro-engine pool. The first out-of-order event message includes the out-of-order message. The micro-engine pool is used to call the host memory to sort the out-of-order message. According to the method described in claim 4, the method further includes, after rearranging the out-of-order packets by adding marker information at the sorting position: The bitmap of the queue management context is moved according to the added marker information in the bitmap of the queue management context; When the bitmap of the queue management context moves from the current sorting delivery segment to the next sorting delivery segment and the first out-of-order event message has been reported, a second out-of-order event message is reported to the micro-engine pool. The second out-of-order event message is used to request the micro-engine pool to release the first sorting information of the out-of-order packets corresponding to the next sorting delivery segment. The method according to claim 5, characterized in that, after reporting the second out-of-order event message to the micro-engine pool, the method further includes: Receive the first sorting information sent by the micro-engine pool; The first sorting information is bitwise ORed with the second sorting information in the bitmap of the queue management context corresponding to the next sorting delivery segment to update the bitmap of the queue management context corresponding to the next sorting delivery segment. A message rearrangement apparatus, characterized in that the apparatus comprises: The receiving module is used to receive out-of-order messages sent by the requesting end, wherein the out-of-order messages include message sequence numbers and packet sequence numbers; The processing module is configured to determine whether the out-of-order packet is within the current sorting and delivery segment of the hardware processing engine of the network device based on the message sequence number and the packet sequence number; if the out-of-order packet is within the current sorting and delivery segment, the module determines the sorting position of the out-of-order packet in the bitmap of the queue management context corresponding to the current sorting and delivery segment based on the message sequence number and the packet sequence number. The rearrangement module is used to rearrange the out-of-order packets by adding marker information at the sorting positions. The apparatus according to claim 7, wherein the processing module is further configured to: determine that the out-of-order message is within the current sorting and delivery segment of the hardware processing engine when the difference between the message sequence number and the expected message sequence number is less than or equal to the number of maintainable messages of the hardware processing engine and the difference between the packet sequence number and the expected packet sequence number is less than or equal to the number of maintainable messages of the hardware processing engine; and determine that the out-of-order message is not within the current sorting and delivery segment of the hardware processing engine when the difference between the message sequence number and the expected message sequence number is greater than the number of maintainable messages of the hardware processing engine or the difference between the packet sequence number and the expected packet sequence number is greater than the number of maintainable messages of the hardware processing engine. The apparatus according to claim 8, wherein the expected message sequence number is the message sequence number corresponding to the first sorting position in the bitmap of the queue management context, and the expected packet sequence number is the packet sequence number corresponding to the first sorting position in the bitmap of the queue management context. The apparatus according to claim 7, wherein the processing module is further configured to report a first out-of-order event message to the micro-engine pool when the out-of-order message is not in the current sorting delivery segment of the hardware processing engine, the first out-of-order event message including the out-of-order message, and the micro-engine pool is configured to call the host memory to sort the out-of-order message. The apparatus according to claim 10, wherein the processing module is further configured to move the bitmap of the queue management context according to the added marker information in the bitmap of the queue management context; when the bitmap of the queue management context moves from the current sorting delivery segment to the next sorting delivery segment and the first out-of-order event message has been reported, a second out-of-order event message is reported to the micro-engine pool, the second out-of-order event message being used to request the micro-engine pool to release the first sorting information of the out-of-order packets corresponding to the next sorting delivery segment. A chip, characterized in that it includes a memory and a processor, the memory storing a computer program, characterized in that the processor executes the computer program to implement the steps of the method according to any one of claims 1 to 6. A computer device includes a processor and the chip of claim 8, characterized in that the chip is used to schedule messages to the processor or to process them on its own, and the processor is used to process messages scheduled by the chip. A computer-readable storage medium having a computer program stored thereon, characterized in that, when the computer program is executed by a processor, it implements the steps of the method according to any one of claims 1 to 6. A computer program product includes a computer program, characterized in that, when executed by a processor, the computer program implements the steps of the method according to any one of claims 1 to 6.