HK1243565B - Systems and method for single queue multi-stream traffic shaping - Google Patents

Description

System and method for single-queue multi-flow service shaping

Background Art

Traffic shaping is a technique used to regulate network data traffic by slowing down traffic flows that are determined to be less important or less desirable than prioritized traffic flows. There are two common mechanisms for slowing down traffic flows: first, dropping or discarding certain packets, and second, delaying packets. The packet drop mechanism is widely used and, in many cases, is the only viable option. For example, if performed by a separate device to which a computer is connected, traffic shaping can be performed by selectively dropping packets.

Alternatively, a packet delay mechanism can eliminate packet abandonment or reduce the number of abandoned packets. For example, when packets are delayed, a feedback mechanism can exert "back pressure", that is, send feedback to the sending module (e.g., a device or software component) to cause the sending module to reduce the rate at which it sends packets. In the absence of such "back pressure", the traffic shaping module will need to keep receiving packets at a faster rate and will need to buffer them until it can send them at the correct rate. The lack of such "back pressure" will not only prevent applications from immediately becoming aware of traffic congestion, but will also degrade the overall throughput and performance of the packet transmission system.

Summary of the Invention

In one aspect, a system including a network device is provided. The network device includes a network interface driver, a data traffic shaping module, and a network interface card. The network interface driver is configured to send a first set of data packets generated and forwarded by a software application for transmission by the network interface card, store descriptors associated with the received first set of data packets in a primary transmit queue in a first order, and pass the descriptors associated with the received first set of data packets to the data traffic shaping module executed on one of the network interface card and at least one processor. In response to determining that the network interface card has successfully transmitted a packet in the received first set of packets, the network interface driver is configured to communicate a packet transmission completion message to the software application waiting to receive the packet transmission completion message from the network interface driver before forwarding additional data packets to the network interface driver. The data traffic shaping module is configured to maintain a plurality of traffic shaping queues, each traffic shaping queue having at least one associated transmission rate rule. The data traffic shaping module is further configured to receive descriptors of data packets delivered by the network interface driver from the primary transmit queue, determine that transmission by the network card will be delayed, and, in response to such determination, remove the descriptors from the primary transmit queue and store them in a corresponding traffic shaping queue based on the classification result. The data traffic shaping module is further configured to cause the network card to transmit data packets associated with the descriptors stored in the auxiliary traffic shaping queue according to a transmission rate rule associated with the corresponding traffic shaping queue, and notify the network interface driver of successful transmission of the data packets in a second order different from the first order.

In one aspect, a method is provided that includes receiving, by a network interface driver executing on at least one processor, a first set of data packets generated and forwarded by a software application for transmission by a network interface card. The method further includes: storing, by the network interface driver, descriptors associated with the received first set of data packets in a primary transmit queue in a first order; and communicating, by the network interface driver, the descriptors associated with the received first set of data packets to a data traffic shaping module executing on one of the network interface card and the at least one processor. The method further includes, in response to determining that the network interface card has successfully transmitted a packet in the received first set of data packets, communicating, by the network interface driver, a packet transmission completion message to the software application awaiting receipt of the packet transmission completion message from the network interface driver before forwarding additional data packets to the network interface driver. The method further includes maintaining, by the data traffic shaping module, a plurality of traffic shaping queues, each traffic shaping queue having at least one associated transmission rate rule; and receiving, by the data traffic shaping module, the descriptors of the data packets communicated by the network interface driver from the primary transmit queue. The method further includes classifying, by the data traffic shaping module, data packets associated with the received descriptor; determining, by the data traffic shaping module, that transmission of a first data packet associated with the received first descriptor by the network interface card will be delayed, and in response to such determination, removing the first descriptor associated with the first data packet from a main transmission queue and storing the first descriptor in a corresponding traffic shaping queue based on the classification result. The method further includes causing, by the data traffic shaping module, the network interface card to transmit the data packets associated with the descriptor stored in the traffic shaping queue according to a transmission rate rule associated with the corresponding traffic shaping queue; and notifying, by the data traffic shaping module, the network interface driver of the successful transmission of the data packets in a second order different from the first order.

In one aspect, a computer-readable medium stores instructions that, when executed by a computing processor, cause the computing processor to: receive, via a network interface driver on the computing processor, a first set of data packets generated and forwarded by a software application for transmission by a network interface card. The computing processor is further caused to store, via the network interface driver, descriptors associated with the received first set of data packets in a primary transmit queue. The computing processor is further caused to communicate, via the network interface driver, the descriptors associated with the received first set of data packets to a data traffic shaping module executing on one of the network interface card and the computing processor. In response to determining that the network interface card has successfully transmitted a packet in the received first set of packets, the computing processor is further caused to communicate, via the network interface driver, a packet transmission completion message to the software application awaiting receipt of the packet transmission completion message from the network interface driver before forwarding additional data packets to the network interface driver. The computing processor is further caused to maintain, via the data traffic shaping module, a plurality of traffic shaping queues, each traffic shaping queue having at least one associated transmission rate rule. The computing processor is further caused to receive, via the data traffic shaping module, a descriptor of a data packet delivered by the network interface driver from the primary transmission queue; and to classify, via the data traffic shaping module, the data packet associated with the received descriptor. The computing processor is further caused to determine, via the data traffic shaping module, that transmission of a first data packet associated with the received first descriptor by the network card will be delayed, and in response to such determination, remove the first descriptor associated with the first data packet from the primary transmission queue and store the first descriptor in a corresponding traffic shaping queue based on the classification result. The computing processor is further caused to cause, via the data traffic shaping module, the network card to transmit the data packet associated with the descriptor stored in the traffic shaping queue according to a transmission rate rule associated with the corresponding traffic shaping queue. The computing processor is further caused to notify the network interface driver, via the data traffic shaping module, of the successful transmission of the data packet.

BRIEF DESCRIPTION OF THE DRAWINGS

The above and related objects, features, and advantages of the present disclosure will be more fully understood by referring to the following detailed description when taken in conjunction with the following drawings, in which:

FIG1 is a block diagram of a network environment having a data traffic shaping system according to certain embodiments;

FIG2 is a block diagram of an example virtual machine environment;

3 is a flow chart illustrating the operation of a network interface driver according to certain embodiments;

FIG4 is a flow chart illustrating the operation of a data shaping module according to certain embodiments;

5 is a flow chart illustrating the operation of a network interface driver according to certain embodiments;

6A-6D are block diagrams illustrating examples of operations of a data traffic shaping system according to certain embodiments;

7A-7D are block diagrams illustrating examples of operations of a data traffic shaping system according to certain embodiments;

8A-8C are block diagrams illustrating examples of the operation of a data traffic shaping system according to certain embodiments; and

9 is a block diagram of an example computing system.

DETAILED DESCRIPTION

Systems and methods are provided for traffic shaping in a network device. In some embodiments, the systems and methods include a network interface driver of the network device configured to store descriptors associated with packets received in a transmit queue and pass the descriptors to a traffic shaping module. The received packets originate from an application running on a computing device, such as one or more virtual machines hosted by the computing device. The guest operating system of the virtual machine prevents the application from forwarding additional packets to the network interface driver until a message confirming that previously forwarded packets have been successfully transmitted is received. As described herein, in some embodiments, in response to determining that a network interface card successfully transmitted a first packet of the received packets, before forwarding the additional data packets to the network interface driver, the network interface driver communicates a packet transmission completion message to a software application or guest operating system waiting to receive the packet transmission completion message. In some embodiments, in response to determining that transmission of one of the received packets by the network interface driver will be delayed, the traffic shaping module removes the descriptors associated with the packets from the transmit queue and stores the descriptors in a corresponding traffic shaping queue. This configuration can be implemented using a single main transmission queue in the network interface driver and multiple traffic shaping queues (for example, in the network interface card) that use different traffic shaping rules, thereby allowing traffic shaping on a per-flow basis without the need for multiple transmission queues in the network interface driver. Furthermore, using this configuration, the packet source (such as a software application running on the real OS of the network device (as opposed to the guest OS of the virtual machine), or a software application in the guest OS managed by the hypervisor or the upper layer of the TCP stack) does not need to know the traffic shaping algorithm implemented in the network interface driver or on the network card. Therefore, the cost of implementing the network interface driver and the guest operating system in the virtual machine environment can be reduced. In addition, using this configuration, the packet source does not need to know not only the traffic shaping algorithm, but also other configurations, such as packet classification rules and other traffic management policies. Therefore, the overall traffic shaping system can be more reliable than a system in which the application or user can configure such specific rules and policies (for example, the number of queues).

In conventional systems, packets are processed in the order of the transmission queue, which is, for example, a first-in, first-out (FIFO) queue, and completion results are returned in order. In certain embodiments of the present disclosure, the traffic shaping module can cause completion messages to be returned out of order by removing certain data packets from the transmission queue for delayed transmission (without giving up). With the "out of order completion" configuration, because the application will no longer send more data packets before receiving the completion message for the data packet that has been forwarded to the network interface driver, this can enable the application to transmit data packets faster or slower while still having a single transmission queue. That is, this configuration can avoid head-of-line blocking by preventing delayed data packets from remaining in the queue. In addition, in certain embodiments, this "out of order" completion configuration can be applied to separate flows (or streams) of data packets within an application, making it possible to selectively slow down each flow, wherein the application is, for example, an application with thousands of connections opened for the corresponding flow or stream.

Furthermore, in some embodiments, in the absence of head-of-line blocking, an "out-of-order" completion configuration can exert "back pressure" on the sending module, regardless of how many main transmission queues there are or how many packets are placed in each queue, as long as the completion messages can be returned out of order. In some embodiments, a traffic shaping mechanism with an out-of-order completion configuration can be implemented using a specific network/hardware configuration (e.g., a specific number of main transmission queues and specific queue assignment rules). For example, in order to shape a thousand flows/streams of traffic, the traffic shaping mechanism can be implemented using only a single queue or a small number of queues (e.g., 16-32 queues). When implemented in a system with a small number of queues, the traffic shaping mechanism can return "out-of-order" completion messages, indicating whether each packet is placed in the correct queue based on a predetermined queue assignment rule or whether the packet traffic is "randomly" spread across the queues. For example, without modifying the network/hardware configuration (e.g., the queue assignment rules or the number of hardware queues in the Linux system), a traffic shaping system for shaping packet traffic from a Linux system spread across multiple hardware queues can be implemented in a virtual machine. In some embodiments, the traffic shaping system can provide such network/hardware compatibility by hiding the traffic shaping layer, flow classification rules, and policies from applications or users.

FIG1 is a block diagram of an example network environment 1000 having a data traffic shaping system 160. In overview, the illustrated network environment includes a network 700 of interconnected network nodes 750. Network nodes 750 participate in network 700 as data sources, data destinations (or sinks), and intermediate nodes that propagate data from the sources to the destinations through network 700. Network 700 includes a data traffic shaping system 160 of network devices 110 having links 600 to various other participating network nodes 750. As shown in FIG1 , network 700 is a network that facilitates interaction between participating devices. The illustrative example network 700 is the Internet; however, in other embodiments, network 700 can be another network, such as a local network within a data center, a network fabric, or any other local or wide area network. Network 700 can be composed of multiple connected subnets or autonomous networks. Network 700 can be a local area network (LAN) such as a corporate intranet, a metropolitan area network (MAN), a wide area network (WAN), an interconnected network such as the Internet, or a peer-to-peer network such as an ad hoc WiFi peer-to-peer network. Any type and/or form of data network and/or communication network can be used for network 700. It can be public, private, or a combination of public and private networks. Generally, network 700 is used to communicate information between computing devices, such as network nodes 750, and network devices 110 of the data traffic shaping system facilitate this communication according to their configuration.

Referring to Figure 1 , network device 110 is a server that hosts one or more virtual machines. Network device 110 includes a data traffic shaping system 160. In certain embodiments, network device 110 includes memory 112 and a network interface card 168. Network device 110 can also include a packet buffer 169 for storing data packets. In certain embodiments, network device 110 has a configuration similar to that of computing system 140 shown in Figure 9 . For example, memory 112 can have a configuration similar to that of memory 144 shown in Figure 9 , and network interface card 168 can have a configuration similar to that of network interface 146 or network interface controller 143 shown in Figure 9 . Computing system 140 is described in more detail below with reference to Figure 9 . Not all elements shown in computing system 140 illustrated in Figure 9 are necessarily present in certain embodiments of network device 110 illustrated in Figure 1 . In certain embodiments, network device 110 can be a software queue or emulated network device, or software acting as a network interface.

Referring again to FIG. 1 , in some embodiments, data traffic shaping system 160 communicates with one or more applications 150 (e.g., applications 150A, 150B, and 150C). One or more of applications 150A-150C can be software applications running on the real operating system of network device 110. Furthermore, one or more of software applications 150A-150C can be software applications running on a guest OS managed by a hypervisor in a virtual machine environment, or upper layers of a protocol stack (e.g., a TCP stack) of a guest OS in a virtual machine environment. For example, referring to FIG. 2 , applications 150A-150C can each be software application 230 running on real OS 220, software application 265 running on guest OS 260 managed by hypervisor 250, or upper layers of protocol stack 261 of guest OS 260 in FIG. Hypervisor 250 and its associated virtual machine environment will be described in detail below with reference to FIG. 2 .

Still referring to FIG. 1 , in some embodiments, network device 110 includes a network interface driver 164 and a data traffic shaping module 166. Network interface driver 164 can be a network interface driver module running on a real operating system. Network interface driver 164 can communicate with one of software applications 150A-150C (e.g., application 265 in FIG. 2 ) directly (if running on the real operating system of network device 110), via a guest operating system of a virtual machine (if running in a virtual machine environment), or, in some embodiments, through a hypervisor and a guest operating system. In some embodiments, network interface driver 164 is included within the first layer of the Transmission Control Protocol (TCP) stack of the real operating system of network device 110 and communicates with software modules or applications included in upper layers of the TCP stack. In one example, network interface driver 164 is included within the transport layer of the TCP stack and communicates with software modules or applications included in the application layer of the TCP stack. In another example, network interface driver 164 is included within the link layer of the TCP stack and communicates with a TCP/IP module included in the internet/transport layer of the TCP stack.

1 , in some embodiments, the data traffic shaping module 166 can be implemented as part of a network interface driver module running on a real OS. In some embodiments, the data traffic shaping module 166 can be included as part of a network card 168 .

1 , in some embodiments, packet buffer 169 can be located in a shared memory of network device 110, such that some or all of application 150, network card 168, network interface driver 164, and data traffic shaping module 166 can directly or indirectly access packet buffer 169. For example, packet buffer 169 can be located in a shared memory accessible to a guest OS, a real OS, network interface driver 164, and network card 168. To send packets over the network, data packets can be stored in packet buffer 169 before being transmitted to network card 168, where packet buffer 169 is accessible to network interface driver 164 and network card 168.

FIG2 shows a block diagram of an example server 200 implementing a virtual machine environment. In certain embodiments, server 200 includes hardware 210, a real operating system (OS) 220 running on hardware 210, a hypervisor 250, and two virtual machines with guest operating systems (guest OSs) 260 and 270. Hardware 210 can include a network interface card (NIC) 215, among other components. Hardware 210 can have a configuration similar to that of computing system 140, as shown in FIG9 . NIC 215 of hardware 210 can have a configuration similar to that of network interface controller 143 or network interface 146, as shown in FIG9 . In certain embodiments, real OS 220 has a protocol stack 225 (e.g., a TCP stack) and software applications running on real OS 220. In certain embodiments, guest OSs 260 and 270 have protocol stacks 261 and 271, respectively. Each of guest OSs 260 and 270 can host a large number of applications, such as software applications 265, 266, 275, and 276. Server 200 may be a file server, an application server, a web server, a proxy server, an appliance, a network appliance, a gateway, a gateway server, a virtual server, a deployment server, an SSL VPN server, or a firewall.

Referring again to FIG. 2 , server 200 executes a hypervisor that instantiates and manages a first guest OS 260 and a second guest OS 270. First guest OS 260 hosts a first software application 265 and a second software application 266. Second guest OS 270 hosts a third software application 275 and a fourth software application 276. For example, the applications can include a database server, a data warehouse program, stock trading software, an online banking application, a content publishing and management system, a hosted video game, a hosted desktop, an email server, a travel reservation system, a customer relationship management application, an inventory control management database, and an enterprise resource management system. In some embodiments, the guest OSes host other types of applications. The interactions between the components of server 200 are further described below with respect to FIG. 3-5 and FIG. 6A-6D .

FIG3 is a flow chart of an example method 300 for shaping network traffic using a network interface driver, such as the network interface driver 164 shown in FIG1 . In summary, the method 300 begins at stage 310, where the network interface driver can receive a first set of data packets generated by an application and forwarded for transmission by a network interface card, such as the network interface card 168 shown in FIG1 . At stage 320, the network interface driver can store descriptors associated with the received first set of data packets in a primary transmit queue. At stage 330, the network interface driver can pass the descriptors associated with the received first set of data packets to a data traffic shaping module, such as the data traffic shaping module 166 shown in FIG1 .

The flowchart in FIG. 3 will now be described in more detail with reference to FIGs. 6A and 6B , which are block diagrams representing examples of the operation of a data traffic shaping system according to certain embodiments.

At stage 310, the network interface driver can receive a first set of data packets generated and forwarded by an application for transmission by the network interface card. For example, referring to FIG6A , network interface driver 164 receives a set of data packets generated and forwarded by one of the applications 150A-150C for transmission by network interface card 168. In some embodiments, in response to receiving the set of data packets, network interface driver 164 stores the received set of data packets in a packet buffer (e.g., packet buffer 169 in FIG1 and FIG6A-6D ). For example, packet buffer 169 can be located in a shared memory between the guest OS and network interface driver 164 as a shared resource, such that packets sent from application 150 running on the guest OS can be stored in packet buffer 169, and a descriptor associated with the packet can point to a location within the shared resource. In some embodiments, a descriptor containing a pointer (e.g., a memory address) to a specific packet in the packet buffer is associated with the specific packet. In some embodiments, descriptors are typically small (eg, 32 bytes or consisting of a few 64-bit integers) and easy to process, while packets are typically a minimum of a few hundred bytes, and often 1500 bytes.

In some embodiments, a data packet can be part of a stream. Application 150 can send the data packets in each stream in a specific order. Each stream can come from a different application (e.g., an application executing on a different guest OS). In the example shown in FIG6A , application 150A sends three packets of a first stream corresponding to descriptors S1, S2, and S3 in a consecutive order. Application 150B sends three packets of a second stream corresponding to descriptors T1, T2, and T3 in a consecutive order. Application 150C sends two packets of a third stream corresponding to descriptors U1 and U3.

At stage 320, the network interface driver can store descriptors associated with the received first set of data packets in a primary transmit queue 161. Referring to Figures 6A-6D, network device 110 includes a primary transmit queue 161 for containing descriptors associated with data packets received from application 150. In some embodiments, primary transmit queue 161 is a single queue. In some embodiments, primary transmit queue 161 can be a hardware queue (e.g., a queue implemented in dedicated hardware) or a software queue. In some embodiments, primary transmit queue 161 is a set of primary transmit queues. For example, primary transmit queue 161 is a plurality of queues implemented in a multi-queue NIC. In some embodiments, the number of primary transmit queues is less than the number of rate limiters (e.g., traffic shaping queues). For example, to shape tens of thousands of flows or streams, network device 110 can have approximately 10 to approximately 32 hardware queues, along with numerous additional traffic shaping queues installed therein to shape tens of thousands of flows. In response to receiving data packets from the application 150, the network interface driver 164 writes descriptors associated with the data packets to a single queue, e.g., the primary transmit queue 161. In some embodiments, the network interface driver 164 writes the descriptors associated with the data packets in each flow to the primary transmit queue 161 in the order in which the packets were sent by the application 150. For example, as shown in FIG6A , the network interface driver 164 receives eight data packets from the application 150 and writes the descriptors associated with the packets (e.g., descriptors T1, U1, T2, S1, U2, S2, S3, T3) to the primary transmit queue 161 for transmission of the packets via the network card 168. In some embodiments, in response to receiving data packets from the application 150, the network interface driver 164 can write the received packets to a single transmit queue (rather than storing the descriptors associated with them).

Network interface driver 164 receives packets of a first flow from application 150A and writes descriptors S1, S2, and S3 to main transmit queue 161 in the order in which they were transmitted, i.e., S1, then S2, then S3. Similarly, network interface driver 164 receives packets of a second flow from application 150B and writes descriptors T1, T2, and T3 to main transmit queue 161 in the order in which they were received, and network interface driver 164 receives packets of a third flow from application 150C and writes descriptors U1 and U2 to main transmit queue 161. In some embodiments, packets of different flows can be interleaved in the main transmit queue while maintaining the order in which the packets in each flow were received. For example, in the example shown in Figure 6A, in the main transmission queue, packets of different streams are interleaved (i.e., in the order of T1, U1, T2, S1, U2, S2, S3 and T3) while maintaining the reception order of the packets of each stream (e.g., for the first stream, the order of S1->S2->S3 is maintained; for the second stream, the order of T1->T2->T3 is maintained; and for the third stream, the order of U1->U2 is maintained).

The network interface driver can pass descriptors associated with the received first set of data packets to the data traffic shaping module at stage 330. For example, referring to FIG6B , in some embodiments, the network interface driver 164 passes descriptors associated with the received data packets (e.g., T1, U1, T2, S1, U2, S2, S3, and T3) to the data traffic shaping module 166.

FIG4 is a flow chart illustrating an exemplary method 400 for shaping network traffic using a data traffic shaping module, such as the data traffic shaping module 166 shown in FIG1 and FIG6A-6D. In summary, the method 400 begins at stage 410, where the data traffic shaping module maintains a plurality of traffic shaping queues and receives descriptors of data packets from a primary transmit queue, delivered by a network interface driver, such as the network interface driver 164 shown in FIG1 and FIG6A-6D. At stage 420, the data traffic shaping module classifies the data packets associated with the received descriptors. At stage 430, the data traffic shaping module determines whether transmission of a first data packet associated with the received first descriptor by a network interface card, such as the network interface card 168 shown in FIG1 and FIG6A-6D, should be delayed. At stage 440, if the data traffic shaping module determines that the network card's transmission of the first data packet associated with the received first descriptor will be delayed, the data traffic shaping module removes the first descriptor associated with the first data packet from the main transmit queue and, based on the classification result, stores the first descriptor in the corresponding traffic shaping queue. Next, at stage 450, the data traffic shaping module causes the network card to transmit the data packet associated with the descriptor stored in the traffic shaping queue according to the transmission rate rules associated with the corresponding traffic shaping queue. At stage 460, if the data traffic shaping module determines that the network card's transmission of the first data packet associated with the received first descriptor will not be delayed, the data traffic shaping module causes the network card to immediately transmit the first data packet. At stage 470, the data traffic shaping module notifies the network interface driver of the successful transmission of the data packet. Note that, as used herein, successful transmission of a data packet does not necessarily require successful reception of the data packet by the recipient. That is, receipt of an acknowledgment of packet reception (e.g., a TCP ACK message) is not a prerequisite for the network interface card to determine that the packet has been successfully transmitted.

The flowchart of FIG. 4 will now be described in detail with reference to FIGs. 6A-6D, which are block diagrams representing example operations of a data traffic shaping system according to certain implementations.

As described above, at stage 410, the data traffic shaping module maintains multiple traffic shaping queues and receives descriptors of data packets delivered by the network interface driver from the main transmit queue. For example, referring to Figures 6A-6D, the data traffic shaping module 166 maintains multiple traffic shaping queues (e.g., traffic shaping queues 162, 163, and 165). In some embodiments, each traffic shaping queue can maintain a corresponding packet buffer (not shown) for storing packets managed by the traffic shaping queue. In some embodiments, at least some of the traffic shaping queues share access to the packet buffer 169 and thus do not need to have their own separate packet buffers. Referring to Figures 6A and 6B, in response to the network interface driver 164 delivering descriptors associated with received data packets to the data traffic shaping module 166 (e.g., T1, U1, T2, S1, U2, S2, S3, and T3), the data traffic shaping module 166 receives the delivered data packet descriptors from the main transmit queue 161.

At stage 420, the data traffic shaping module classifies the data packets associated with the received descriptors. In some embodiments, such as shown in FIG. 6B , the data traffic shaping module 166 classifies the data packets associated with the received descriptors based on a set of classification rules that map the characteristics of each flow to a corresponding traffic shaping queue. For example, the traffic shaping module can classify packets based on a four- or five-tuple of data in the packet header, including four or five of the source and destination IP addresses, source and destination port numbers, and the type of service indicator. In some embodiments, fewer data fields in the header can be used more extensively to classify packets. For example, in some embodiments, packets can be classified based on a single data field, such as a Type of Service (ToS) or Quality of Service (QoS) field (depending on the protocol and protocol version used), a file type field, or a port number, each of which can generally be associated with a priority level. After identifying the relevant characteristics of the packet, the data traffic shaping module 166 compares the identified characteristics with the classification rules and assigns the packet to the traffic shaping queue that meets the classification rules. In some embodiments, the data traffic shaping module 166 maintains a "catch-all" traffic shaping queue for processing all packets that are not assigned to other traffic shaping queues based on their specific characteristics.

In some embodiments, each traffic shaping queue has at least one associated transmission rate rule. The transmission rate rule for a particular traffic queue can specify a flow rate limit for the network interface card (NIC) to transmit packets stored in the particular traffic shaping queue. Referring to Figures 6A-6D, the data traffic shaping module 166 can cause the NIC 168 to transmit packets stored in the particular traffic shaping queue according to the queue's transmission rate rule. In some embodiments, transmission rate rules can be absolute or conditional. Similarly, transmission rate rules can be based on the number of packets or the amount of data. Some example absolute transmission rate rules include 1) unrestricted transmission; 2) a maximum number of packets transmitted per second; 3) an average number of packets transmitted per second; 4) a maximum number of bits transmitted per second; or 5) an average number of bits transmitted per second. In some embodiments, transmission rate rules can include any combination of the above types of rules. For example, a transmission rate rule can specify an average allowable number of bits or packets per second and a maximum number of bits or packets per second to allow for and/or accommodate bursty traffic. Conditional transmission rate rules allow for different absolute transmission rate rules in different situations. For example, a conditional transmission rate rule might grant a transmission rate when a different traffic shaping queue is full, as opposed to when the different traffic shaping queue is empty. Another conditional transmission rule might grant a different transmission rate depending on the number of packets in the queue, for example, to allow for faster processing of packets if the queue becomes undesirably full. The above rules are examples of broad rules that can be implemented for each of the corresponding traffic shaping queues. Specific rules can be set, for example, by a system administrator.

At stage 430, the data traffic shaping module can determine whether transmission of the first data packet associated with the received first descriptor by the network card is to be delayed. If the classification of the packet results in its being assigned to a traffic shaping queue that already stores unsent packets (or their descriptors), transmission of the packet is delayed.

At stage 440, if the data traffic shaping module determines that the transmission of the first data packet associated with the received first descriptor by the network card will be delayed, the data traffic shaping module removes the first descriptor associated with the first data packet from the main transmit queue and stores the first descriptor in the corresponding traffic shaping queue based on the classification result. For example, referring to Figures 6A and 6B, in response to determining that the transmission of the data packet associated with descriptor T1 of the second flow by network card 168 will be delayed, data traffic shaping module 166 removes descriptor T1 from main transmit queue 161 and stores descriptor T1 in traffic shaping queue 165. Similarly, data traffic shaping module 166 removes descriptors T2 and T3 of the second flow from main transmit queue 161 and stores descriptors T2 and T3 in traffic shaping queue 165. In response to determining that the transmission of the data packet associated with descriptor S1 of the first flow by network card 168 will be delayed, data traffic shaping module 166 removes descriptor S1 from main transmission queue 161 and stores descriptor S1 in traffic shaping queue 163. Similarly, data traffic shaping module 166 removes descriptors S2 and S3 of the first flow from main transmission queue 161 and stores descriptors S2 and S3 in traffic shaping queue 163.

Removing descriptors associated with traffic flows determined to be delayed from a single transmit queue can resolve a queuing problem known as "head-of-line blocking." If the transmission of a packet at the head of a first-in, first-out (FIFO) queue is delayed but remains in the transmit queue, that packet will block the processing of all other packets associated with descriptors stored after it in the queue (including packets that would not be delayed based on the traffic shaping rules implemented by the traffic shaping module), causing a "head-of-line blocking" problem. Conversely, for data packets determined to be delayed based on traffic shaping rules, the data traffic shaping module 166 can transfer the descriptors associated with the head packet from the transmit queue. This removal can allow processing of other packets associated with the descriptors stored in the queue to continue, thereby resolving the "head-of-line blocking" problem. Furthermore, in response to removing a descriptor from a transmit queue, the data traffic shaping module 166 can transfer the descriptor to the corresponding traffic shaping queue, thereby allowing the delayed packet to be transmitted without discarding the descriptor or its corresponding packet.

Referring again to FIG. 6B , in some embodiments, if data traffic shaping module 166 determines that NIC 168 will delay transmission of data packets in a first flow (e.g., data packets corresponding to descriptor S1), data traffic shaping module 166 stores the descriptors associated with the data packets in the first flow in a first traffic shaping queue (i.e., traffic shaping queue 163). If data traffic shaping module 166 determines that NIC 168 will delay transmission of data packets in a second flow different from the first flow (e.g., data packets corresponding to descriptor T1), data traffic shaping module 166 stores the descriptors associated with the data packets in the second flow in a second traffic shaping queue (e.g., traffic shaping queue 165). In some embodiments, packets associated with different flows can be delivered to the same traffic shaping queue. That is, data traffic shaping module 166 can maintain fewer traffic shaping queues than the number of flows processed by data traffic shaping module 166, and in many cases, significantly fewer traffic shaping queues.

At stage 450, the data traffic shaping module causes the network interface card (NIC) to transmit data packets associated with the descriptors stored in the traffic shaping queues according to the transmission rate rules associated with the corresponding traffic shaping queues. For example, referring to Figures 6B-6D, data traffic shaping module 166 causes NIC 168 to transmit data packets associated with descriptors S1, S2, and S3 stored in traffic shaping queue 163 in a delayed manner according to the transmission rate rules associated with traffic shaping queue 163. Data traffic shaping module 166 can also cause NIC 168 to transmit data packets associated with descriptors T1, T2, and T3 stored in traffic shaping queue 165 in a delayed manner according to the transmission rate rules associated with traffic shaping queue 165.

At stage 460, if the data traffic shaping module determines that the transmission of the first data packet associated with the received first descriptor by the network card will not be delayed, the data traffic shaping module can cause the network card to immediately transmit the data packet associated with the descriptor stored in the traffic shaping queue. For example, if the data packet is classified so that it is assigned to a traffic shaping queue with a transmission rate rule that allows an unlimited transmission rate and the queue is empty, the data packet can be transmitted immediately without delay. The packets associated with descriptors U1 and U2 are processed as in the example shown in Figures 6A-6D. Similarly, if the packet is classified into a traffic shaping queue that is empty and does not exceed the transmission rate identified in its corresponding transmission rate rule, the packet can be transmitted immediately.

In some embodiments, the network card 168 transmits the data packet by using a resource. In some embodiments, the resource is a memory buffer (e.g., packet buffer 169 in Figures 1 and 6A-6D) shared by some or all of the application 150, the network interface driver 164, and the network card 168. For example, the network card 168 uses a descriptor associated with the data packet to identify the address of the data packet in the packet buffer 169 (in the shared memory) and then transmits the data packet from the packet buffer 169. In some embodiments, in response to transmitting the data packet using the packet buffer 169, the network card 168 can cause the packet buffer to release memory space used to store the transmitted packet so that the space can be used to store a new packet.

At stage 470, the data traffic shaping module can notify the network interface driver of the successful transmission of the data packets. For example, referring to FIG6C , in response to the successful completion of the (immediate) transmission of the data packets associated with descriptors U1 and U2 via network interface card 168, data traffic shaping module 166 notifies network interface driver 164 of the successful transmission of the data packets. In some embodiments, data traffic shaping module 166 can notify network interface driver 164 of the successful transmission of the data packets by forwarding a single message generated by network interface card 168 to network interface driver 164, wherein the single message indicates the successful transmission of the data packets associated with descriptors U1 and U2. In some embodiments, data traffic shaping module 166 can individually notify network interface driver 164 of the successful transmission of each of the data packets associated with descriptors U1 and U2 by forwarding a separate transmission completion message to network interface driver 164 for each packet.

Similar communications can be generated and forwarded for delayed transmissions. For example, referring to FIG6D , in response to the successful completion of the (delayed) transmission of the data packets associated with descriptors T1, S1, T2, S2, T3, and S3 via network interface card 168, data traffic shaping module 166 notifies network interface driver 164 of the successful transmission of the data packets. In some embodiments, data traffic shaping module 166 can notify network interface driver 164 of the successful transmission of the data packets by forwarding a single message generated by network interface card 168 to network interface driver 164, wherein the single message indicates the successful transmission of multiple data packets. In some embodiments, data traffic shaping module 166 can separately notify network interface driver 164 of the successful transmission of each individual data packet.

FIG5 is a flow chart of an example method 500 performed by a network interface driver to shape network traffic. In summary, the method 500 begins at stage 510, where a network interface driver (such as the network interface driver 164 shown in FIG1 and FIG6A-6D) determines whether a network interface card (such as the network interface card 168) successfully transmits a packet from a first set of received packets. At stage 520, if the network interface driver determines that a packet from the first set of received packets was successfully transmitted, the network interface driver transmits a packet transmission complete message to an application waiting to receive the packet transmission complete message from the network interface driver before forwarding additional data packets to the network interface driver.

The method shown in the flowchart of FIG. 5 is described in detail below with reference to FIG. 6A-6D .

5 , at stage 510, the network interface driver determines whether the network card 168 successfully transmitted packets from the received first set of packets. For example, referring to FIG6C , in response to network card 168 successfully completing transmission of the data packets associated with descriptors U1 and U2, data traffic shaping module 166 communicates a single message or multiple messages to network interface driver 164 notifying the network interface driver 164 of the successful transmission of the data packets. Based on the notification of the successful transmission of the data packets from data traffic shaping module 166, network interface driver 164 determines that network card 168 successfully transmitted each of the received packets.

At stage 520, in response to the network interface driver determining that a packet from the received first set of packets was successfully transmitted, the network interface driver transmits a packet transmission completion message to the application waiting to receive the packet transmission completion message from the network interface driver before forwarding the additional data packet to the network interface driver. For example, referring to FIG6C , in response to determining that network card 168 has successfully transmitted a packet associated with descriptor U1 from the third stream sent by application 150C, network interface driver 164 communicates a packet transmission completion message 167 corresponding to descriptor U1 (e.g., M-U1 in FIG6C ) to application 150C. Similarly, in response to determining that network card 168 has successfully transmitted a packet associated with descriptor U2 from application 150C, network interface driver 164 communicates a packet transmission completion message 167 corresponding to descriptor U2 (e.g., M-U2 in FIG6C ) to application 150C. In some embodiments, transmission completion message 167 can be relatively small (e.g., 32 bytes or a small 64-bit integer). In some embodiments, in response to receiving a single message (not shown) from the data traffic shaping module 166 indicating the successful transmission of data packets associated with descriptors U1 and U2, the network interface driver 164 generates two separate transmission completion messages (e.g., M-U1 and M-U2 in FIG. 6C ) and communicates each message to a corresponding packet source, e.g., application 150C, in the order in which the data packets were successfully transmitted. In some embodiments, in response to receiving a message (not shown) from the data traffic shaping module 166 indicating the successful transmission of each of the data packets associated with descriptors U1 and U2, the network interface driver 164 can forward the received message to the corresponding packet source (e.g., application 150C) as a transmission completion message.

6D , in response to determining that network card 168 has successfully transmitted the packet associated with descriptor T1 of the second stream sent by application 150B, network interface driver 164 communicates a packet transmission completion message 167 (e.g., M-T1 in FIG. 6D ) corresponding to descriptor T1 to application 150B. Similarly, in response to determining that network card 168 has successfully transmitted the packet associated with descriptor S1 of the first stream sent by application 150A, network interface driver 164 communicates a packet transmission completion message 167 (e.g., M-S1 in FIG. 6D ) corresponding to descriptor S1 to application 150B. In some embodiments, in response to receiving a single message (not shown) from the data traffic shaping module 166 indicating the successful transmission of data packets associated with descriptors T1, S1, T2, S2, T3, and S3, the network interface driver 164 can generate six separate transmission completion messages (e.g., M-T1, M-S1, M-T2, M-S2, M-T3, and M-S3 in FIG. 6C ) and communicate each message to the corresponding packet source (e.g., application 150A for descriptors T1, T2, T3 of the first flow and application 150B for descriptors S1, S2, S3 of the second flow) in the order in which the data packets were successfully transmitted (e.g., in the order of T1, S1, T2, S2, T3, and S3). Alternatively, as each message is received from the data traffic shaping module 166, only one message can be sent to each source (e.g., one message to application 150A and one message to application 150B), where each message identifies multiple successfully transmitted packets.

In some embodiments, each of the applications 150 can be configured to wait for a packet transfer completion message from the network interface driver 164 before forwarding additional data packets to the network interface driver 164. In some embodiments, each of the applications 150 can be configured to wait for a transfer completion message for data packets for a particular flow from the network interface driver 164 before forwarding additional data packets in the same flow to the network interface driver 164. For example, as shown in FIG6C , the application 150C waits for a transfer completion message for a data packet in the third flow corresponding to descriptor U1 from the network interface driver 164. Referring to FIG6D , in response to the application 150C receiving the transfer completion message corresponding to descriptor U1, the application 150C forwards additional data packets of the same third flow (e.g., data packets corresponding to descriptors U3 and U4 as shown in FIG6D ) to the network interface driver 164. In this manner, application 150C can maintain a small number of packets (e.g., 1, 2, or 3 packets) for each flow in the main transmit queue by sending additional packets to network interface driver 164 only when application 150C receives a packet transfer completion message indicating packets for the same flow transmitted by network card 168. In some embodiments, in response to receiving a transfer completion message corresponding to a descriptor for a particular flow, the application can forward additional data packets for flows other than the particular flow to network interface driver 164.

The methods shown in the flowcharts of Figures 3-5 are further described below with reference to Figures 7A-7D, which are block diagrams illustrating exemplary operations of a data traffic shaping system according to certain embodiments. In Figures 7A-7D, the same reference numerals as in Figures 6A-6D are used, and the same descriptions are omitted. Figures 7A-7D illustrate the operation of the data traffic shaping system when application 150D sends packets of different streams or flows (e.g., packets corresponding to descriptors V1, V2, and V3 in the fourth stream, and packets corresponding to descriptors W1, W2, and W3 in the fifth stream) to network interface driver 164.

At stage 310 in FIG3 , the network interface driver can receive a first set of data packets generated and forwarded by an application for transmission by a network interface card. For example, referring to FIG7A , the network interface driver 164 receives a set of data packets generated and forwarded by an application 150D for transmission by a network interface card 168. In the example shown in FIG7A , application 150D transmits three packets corresponding to descriptors V1, V2, and V3 in a fourth stream in sequential order. The same application 150D transmits three packets corresponding to descriptors W1, W2, and W3 in a fifth stream in sequential order.

At stage 320 in Figure 3, the network interface driver can store descriptors associated with the received first set of data packets in the main transmit queue 161. In some embodiments, the network interface driver 164 writes the descriptors associated with the data packets from each flow to the main transmit queue 161 in the order in which the packets were sent by application 150D. For example, as shown in Figure 7A, the network interface driver 164 receives six data packets from application 150D and writes the descriptors associated with the packets (e.g., descriptors W1, W2, V1, V2, V3, W3) to the main transmit queue 161 for transmission of the packets via the network card 168. The network interface driver 164 receives packets for the fourth and fifth flows from application 150D and writes the corresponding descriptors (e.g., V1, V2, V3 for the fourth flow; and W1, W2, W3 for the fifth flow) to the main transmit queue 161 in the order in which they were transmitted (e.g., W1, then W2, then V1, then V2, then V3, then W3). In some embodiments, packets from different flows can be interleaved in the primary transmit queue while maintaining the order in which the packets were received within each flow. For example, in the example shown in FIG7A , packets from different flows are interleaved in the primary transmit queue (i.e., in the order W1, W2, V1, V2, V3, W3) while maintaining the order in which the packets were received within each flow (e.g., for the fourth flow, the order V1->V2-V3 is maintained; and for the fifth flow, the order W1->W2->W3 is maintained).

At stage 330 in FIG. 3 , the network interface driver can pass descriptors (eg, W1 , W2 , V1 , V2 , V3 , W3 ) associated with the received first set of data packets to the data traffic shaping module 166 .

4 , at stage 410, the data traffic shaping module maintains a plurality of traffic shaping queues and receives descriptors of data packets delivered by the network interface driver from the main transmit queue. Referring to FIG7A and 7B , in response to the network interface driver 164 delivering descriptors associated with received data packets to the data traffic shaping module 166 (e.g., W1, W2, V1, V2, V3, and W3), the data traffic shaping module 166 receives the descriptors of the delivered data packets from the main transmit queue 161.

At stage 420 in Figure 4, the data traffic shaping module classifies the data packets associated with the received descriptors. In some embodiments, for example, as shown in Figure 7B, the data traffic shaping module 166 classifies the data packets associated with the received descriptors based on a set of classification rules for mapping the characteristics of each flow to a corresponding traffic shaping queue.

At stage 430 in Figure 4, the data traffic shaping module can determine whether transmission of the first data packet associated with the received first descriptor by the network card will be delayed. If transmission of the packet results in its assignment to a traffic shaping queue that already stores unsent packets (or their descriptors), transmission of the packet is delayed.

At stage 440 in FIG4 , if the data traffic shaping module determines that the transmission of the first data packet associated with the received first descriptor by the network interface card will be delayed, the data traffic shaping module removes the first descriptor associated with the first data packet from the main transmit queue and, based on the classification result, stores the first descriptor in a corresponding traffic shaping queue. For example, referring to FIG7A and FIG7C , in response to determining that the transmission of the data packets associated with descriptors W1 and W2 of the fifth flow by network interface card 168 will be delayed, data traffic shaping module 166 removes descriptors W1 and W2 from main transmit queue 161 and stores descriptors W1 and W2 in traffic shaping queue 163.

At stage 450 in FIG4 , the data traffic shaping module causes the network interface card (NIC) to transmit data packets associated with the descriptors stored in the traffic shaping queues according to the transmission rate rules associated with the corresponding traffic shaping queues. For example, referring to FIG7B-7D , data traffic shaping module 166 causes NIC 168 to transmit data packets associated with descriptors W1, W2, and W3 stored in traffic shaping queue 163 in a delayed manner according to the transmission rate rules associated with traffic shaping queue 163.

At stage 460 in FIG. 4 , if the data traffic shaping module determines that the NIC's transmission of the first data packet associated with the received first descriptor will not be delayed, the data traffic shaping module can cause the NIC to immediately transmit the data packet associated with the descriptor stored in the traffic shaping queue. For example, if the data packet is classified so as to be assigned to a traffic shaping queue with a transmission rate rule that allows an unlimited transmission rate and the queue is empty, the data packet can be immediately transmitted without delay. Packets associated with descriptors V1, V2, and V3 are processed as shown in the examples in FIG. 7A-7D .

At stage 470 in Figure 4 , the data traffic shaping module can notify the network interface driver of the successful transmission of the data packets. For example, referring to Figure 7C , in response to the (immediate) successful completion of the transmission of the data packets associated with descriptors V1, V2, and V3 via the network card 168, the data traffic shaping module 166 notifies the network interface driver 164 of the successful transmission of the data packets. In some embodiments, as shown in Figure 7C , the data traffic shaping module 166 can individually notify the network interface driver 164 of the successful transmission of each of the data packets associated with descriptors V1, V2, and V3 by forwarding a separate transmission completion message to the network interface driver 164 for each packet.

For delayed transmissions, similar communications can be generated and forwarded. For example, referring to FIG7D , in response to the successful (delayed) completion of the transmission of the data packets associated with descriptors W1, W2, and W3 via network card 168, data traffic shaping module 166 notifies network interface driver 164 of the successful transmission of the data packets.

At stage 510 in Figure 5 , the network interface driver determines whether the network card successfully transmitted packets in the first set of received packets. For example, referring to Figure 7C , in response to network card 168 successfully completing the transmission of the data packets associated with descriptors V1, V2, and V3, data traffic shaping module 166 notifies network interface driver 164 of the successful transmission of the data packets by communicating a single message or multiple messages. Based on the notification of the successful transmission of the data packets from data traffic shaping module 166, network interface driver 164 determines that network card 168 successfully transmitted each of the received packets.

At stage 520 in Figure 5 , in response to the network interface driver determining that a packet in the received first set of packets was successfully transmitted, the network interface driver communicates a packet transmission completion message to the application waiting to receive the packet transmission completion message from the network interface driver before forwarding the additional data packet to the network interface driver. For example, referring to Figure 7C , in response to determining that network card 168 successfully transmitted a packet associated with descriptor V1 in the fourth stream sent by application 150D, network interface driver 164 communicates a packet transmission completion message 167 corresponding to descriptor V1 (e.g., M-V1 in Figure 7C ) to application 150D. Similarly, in response to determining that network card 168 successfully transmitted a packet associated with descriptors V2 and V3 in the fourth stream sent by application 150D, network interface driver 164 communicates two packet transmission completion messages 167 corresponding to descriptors V2 and V3 (e.g., M-V2 and M-V3 in Figure 7C ) to application 150D. In some embodiments, the applications 150D can be configured to wait for a packet transfer completion message from the network interface driver 164 before forwarding additional data packets to the network interface driver 164. In some embodiments, each of the applications 150D can be configured to wait for a transfer completion message for data packets in a particular flow from the network interface driver 164 before forwarding additional data packets in the same flow to the network interface driver 164. For example, as shown in FIG7C , the application 150D waits for a transfer completion message for data packets corresponding to descriptor V1 in the third flow from the network interface driver 164. Referring to FIG7D , in response to the application 150D receiving the transfer completion message corresponding to descriptor V1, the application 150D forwards additional data packets in the same fourth flow (e.g., data packets corresponding to descriptors V4 and V5 as shown in FIG7D ) to the network interface driver 164. In this way, application 150D is able to maintain a small number of packets (e.g., 1 or 2 or 3 packets) for each flow in the main transmit queue by sending additional packets to network interface driver 164 only when it receives a packet transfer completion message instructing network card 168 to transmit packets in the same flow.

7A-7D , typically, network traffic belongs to multiple flows or streams (e.g., the packets corresponding to descriptors V1, V2, and V3 in the fourth stream, and the packets corresponding to W1, W2, and W3 in the fifth stream). Each flow/stream can belong to a specific application (e.g., application 150D) or go to a specific remote location. For example, multiple flows/streams belong to the same application (e.g., application 150D in FIG. 7A-7D ) or to different applications (e.g., applications 150A-150C in FIG. 6A-6D ). At any given time, a network device can process hundreds or thousands or even millions of different flows/streams, and sometimes, it may be necessary to slow down traffic directed to a specific target or traffic directed to a specific application. 7A-7D , in some embodiments, the data traffic shaping module 166 can independently rate limit or traffic shape different flows/streams sent from the same application 150D without head-of-line blocking by attaching queues corresponding to flows/streams (e.g., traffic shaping queues 162 and 163) and slowing down all traffic sent through the same queue (e.g., slowing down all packets associated with descriptors W1, W2, and W3 sent through traffic shaping queue 163). With this configuration, regardless of how the applications place flows on those queues (e.g., receiving multiple flows from corresponding different applications, as shown in FIG6A-6D , or receiving multiple flows from the same application, as shown in FIG7A-7D ), flows can be selectively slowed down without incurring head-of-line blocking or dropping any packets, and without requiring each application to be aware of how traffic sent from each application can be classified and traffic shaped.

The methods illustrated in the flowcharts of Figures 3-5 are further described below with reference to Figures 8A-8C, which are block diagrams illustrating exemplary operations of a data traffic shaping system according to certain embodiments. In Figures 8A-8C, the same reference numerals as in Figures 6A-6D are used, and the same descriptions are omitted. Figures 8A-8C illustrate the operation of the data traffic shaping system when the primary transmit queue 161 is a collection of primary transmit queues 161A-161C. For example, primary transmit queue 161 can be a plurality of queues implemented in a multi-queue NIC. In certain embodiments, the number of primary transmit queues 161A-161C is less than the number of rate limiters or traffic shaping queues 162A-162D. For example, to shape tens of thousands of flows or streams, the network device 110 can have 10 to 32 hardware queues, while having numerous additional traffic shaping queues installed therein to shape tens of thousands of flows.

At stage 310 in FIG3 , the network interface driver can receive a set of data packets generated and forwarded by application 150 for transmission by the network interface card. For example, referring to FIG8A , network interface driver 164 receives a set of data packets generated and forwarded by applications 150A-150C for transmission by network interface card 168. In the example shown in FIG8A , application 150A sends three packets corresponding to descriptors S1, S2, and S3 in a first stream in a sequential order. Application 150B sends three packets corresponding to descriptors T1, T2, and T3 in a second stream in a sequential order. Application 150C sends two packets corresponding to descriptors U1 and U3 in a third stream. In some embodiments, network interface driver 164 receives the data packets in the order in which application 150 sends the packets (e.g., T1, then U1, then T2, then S1, then U2, then S2, then S3, then T3).

At stage 320 in FIG3 , the network interface driver can store descriptors associated with the received first set of data packets in a set of primary transmit queues 161A-161C. In some embodiments, the network interface driver 164 randomly selects one of the primary transmit queues 161A-161C for each received data packet and writes the corresponding descriptors to the selected transmit queue in the primary transmit queues 161. For example, referring to FIG8A , the network interface driver 164 writes descriptors T1, S1, and S3 (in the order of T1, S1, and S3) to the primary transmit queue 161A, descriptors U1, T2, and U2 (in the order of U1, T2, and U2) to the primary transmit queue 161B, and descriptors T2, S2, and T3 (in the order of S2 and T3) to the primary transmit queue 161C. In some embodiments, within each primary transmit queue, packets from different flows can be interleaved while maintaining the order in which the packets in each flow were received. For example, in the example shown in Figure 8A, in the main transmission queue 161A, packets of different flows are interleaved (i.e., in the order of T1, S1, S3) while maintaining the reception order of packets in each flow (e.g., for the third flow, the order of S1->S3 is maintained).

At stage 330 in Figure 3, the network interface driver 164 is capable of passing the descriptors associated with the received first set of data packets and stored in each main transmit queue (e.g., T1, S1, S3 stored in the main transmit queue 161A) to the data traffic shaping module 166.

4 , at stage 410, the data traffic shaping module maintains a plurality of traffic shaping queues and receives descriptors of data packets delivered by the network interface driver from each of the primary transmit queues 161A-161C. Referring to FIGS. 8A and 8B , in response to the network interface driver 164 delivering descriptors associated with received data packets to the data traffic shaping module 166, the data traffic shaping module 166 receives descriptors of data packets (e.g., descriptors T1, S1, S3) from the primary transmit queue 161A, descriptors of data packets (e.g., descriptors U1, T2, U2) from the primary transmit queue 161B, and descriptors of data packets (e.g., descriptors S2, T3) from the primary transmit queue 161C. In some embodiments, the data traffic shaping module maintains a plurality of traffic shaping queues and receives descriptors of data packets delivered by the network interface driver from each of the primary transmit queues. For example, referring to Figures 8A-8C, the data traffic shaping module 166 maintains a plurality of traffic shaping queues (eg, traffic shaping queues 162A-162D).

At stage 420 in Figure 4, data traffic shaping module 166 classifies the data packets associated with the received descriptors from each primary transmit queue. At stage 430, data traffic shaping module 166 can determine whether the transmission of the first data packet associated with the received first descriptor by the network card should be delayed. If its classification results in it being assigned to a packet (or its descriptor) that already has an unsent packet stored, the transmission of the packet is delayed.

At stage 440 in FIG. 4 , if the data traffic shaping module determines that the NIC's transmission of the first data packet associated with the received first descriptor will be delayed, the data traffic shaping module removes the first descriptor associated with the first data packet from each primary transmit queue and, based on the classification result, stores the first descriptor in the corresponding traffic shaping queue. For example, referring to FIG. 8A and 8B , for primary transmit queue 161A, the data traffic shaping module determines that NIC 168's transmission of the data packets associated with descriptors T1, S1, and S3 stored in primary transmit queue 161A will be delayed. In response to determining that NIC 168's transmission of the data packet associated with descriptor T1 of the second flow will be delayed, data traffic shaping module 166 removes descriptor T1 from primary transmit queue 161A and stores it in traffic shaping queue 162C. Similarly, data traffic shaping module 166 removes descriptor S1 of the first flow from primary transmit queue 161A and stores it in traffic shaping queue 162B. Data traffic shaping module 166 also removes descriptor S3 from main transmission queue 161A and stores it in traffic shaping queue 162B. Similarly, as shown in Figures 8A and 8B , for main transmission queue 161B, data traffic shaping module 166 removes descriptor U1 of the third stream from main transmission queue 161B and stores it in traffic shaping queue 162A, removes descriptor T2 of the second stream from main transmission queue 161B and stores it in traffic shaping queue 162C, and removes descriptor U2 of the third stream from main transmission queue 161B and stores it in traffic shaping queue 162A. In a similar manner, as shown in Figures 8A and 8B, for the main transmission queue 161C, the data traffic shaping module 166 removes the descriptor S2 of the first stream from the main transmission queue 161C and stores the descriptor S2 in the traffic shaping queue 162B, and removes the descriptor T3 of the second stream from the main transmission queue 161C and stores the descriptor T3 in the traffic shaping queue 162C.

At stage 450 in FIG4 , the data traffic shaping module causes the network interface card (NIC) to transmit data packets associated with the descriptors stored in the traffic shaping queues according to the transmission rate rules associated with the corresponding traffic shaping queues. For example, referring to FIG8B-8C , data traffic shaping module 166 causes NIC 168 to transmit data packets associated with descriptors S1, S2, and S3 stored in traffic shaping queue 162B in a delayed manner according to the transmission rate rules associated with traffic shaping queue 162B. Data traffic shaping module 166 can also cause NIC 168 to transmit data packets associated with descriptors T1, T2, and T3 stored in traffic shaping queue 162C in a delayed manner according to the transmission rate rules associated with traffic shaping queue 162C.

At stage 460 in FIG4 , if the data traffic shaping module determines that the NIC's transmission of the first data packet associated with the received first descriptor will not be delayed, the data traffic shaping module can cause the NIC to immediately transmit the data packet associated with the descriptor stored in the traffic shaping queue. For example, if the data packet is classified so as to be assigned to a traffic shaping queue with a transmission rate rule that allows an unlimited transmission rate and the queue is empty, the data packet can be immediately transmitted without delay. Packets associated with descriptors U1 and U2 are processed according to the example shown in FIG8A-8C .

At stage 470 in Figure 4 , the data traffic shaping module can notify the network interface driver of the successful transmission of the data packets. For example, referring to Figures 8B and 8C , in response to the (immediate) successful completion of the transmission of the data packets associated with descriptors U1 and U2 via the network interface card 168, the data traffic shaping module 166 notifies the network interface driver 164 of the successful transmission of the data packets. For example, referring to Figures 8B and 8C , in response to the (delayed) successful completion of the transmission of the data packets associated with descriptors T1, S1, T2, T3, and S3 via the network interface card 168, the data traffic shaping module 166 notifies the network interface driver 164 of the successful transmission of the data packets.

5 , at stage 510 , the network interface driver determines whether the network card successfully transmits the packets in the received first set of packets.

At stage 520, in response to the network interface driver determining that a packet in the received first set of packets was successfully transmitted, the network interface driver communicates a packet transmission completion message to an application waiting to receive a packet transmission completion message from the network interface driver before forwarding the additional data packet to the network interface driver. For example, referring to FIG8C , in response to determining that network card 168 successfully transmitted a packet associated with descriptor U1 in the third stream sent by application 150C, network interface driver 164 communicates a packet transmission completion message 167 corresponding to descriptor U1 (e.g., M-U1 in FIG8C ) to application 150C. Similarly, in response to determining that network card 168 successfully transmitted a packet associated with descriptor U2 in the third stream sent by application 150C, network interface driver 164 communicates a packet transmission completion message 167 corresponding to descriptor U2 (e.g., M-U2 in FIG8C ) to application 150C. Similarly, in some embodiments, in response to receiving a message (not shown) from the data traffic shaping module 166 indicating successful transmission of data packets associated with descriptors T1, S1, T2, S2, T3, and S3, the network interface driver 164 is capable of generating six separate transmission completion messages (e.g., M-T1, M-S1, M-T2, M-S2, M-T3, and M-S3 in FIG. 8C ) and communicating each message to the corresponding packet source in the order in which the data packets were successfully transmitted (e.g., in the order of T1, S1, T2, S2, T3, and S3).

8C , in some embodiments, each of the applications 150 can be configured to wait to receive a packet transfer completion message from the network interface driver 164 before forwarding additional data packets to the network interface driver 164. In some embodiments, each of the applications 150 can be configured to wait to receive a transfer completion message for data packets in a particular flow from the network interface driver 164 before forwarding additional data packets in the same flow to the network interface driver 164.

8A-8C , in some embodiments, the application 150 or network interface driver 164 can distribute flows/streams and their corresponding packets across the set of primary transmit queues 161A-161C in any manner configured (e.g., randomly across the queues, or in a round-robin fashion). In some embodiments, the application 150 or network interface driver 164 can distribute flows/streams and their corresponding packets across the set of primary transmit queues in the same manner, regardless of the number of primary transmit queues. In some embodiments, the application 150 or network interface driver 164 is configured to be unaware of the implementation details of the data traffic shaping module 166, the traffic shaping queues 162A-162D, and how traffic is classified within those queues. For example, traffic from an application executing in a virtual machine can be shaped or rate-limited without head-of-line blocking and without informing the virtual machine administrator of the details of the traffic shaping queues and the classification rules for each queue. Utilizing the configuration illustrated in Figures 8A-8C, packets can leave the primary transmit queue as quickly as possible and can be sorted into the traffic shaping queue after leaving the primary transmit queue without returning a completion message. In some embodiments, as shown in Figures 8A-8C, completion messages are not returned until the packet leaves the traffic shaping queue, such that completion messages are returned out of order, i.e., in an order different from the order in which the packets were stored in the primary transmit queue and not in the FIFO, thereby allowing an application sending a faster stream to send more additional packets than another application sending a slower stream. 8A-8C , where the data traffic shaping module 166 is implemented in a system having multiple main transmission queues 161A-161C, the network interface driver 164 is capable of returning “unordered” completion messages (e.g., the order of the completion messages M-U1, M-U2, M-T2 is different from the order in which the corresponding packets are stored in the main transmission queue 161B, i.e., U1, T2, U2; see FIGURES 8A and 8C ), indicating whether each packet is placed in the correct queue based on predetermined queue assignment rules, or whether the packet traffic is “randomly” spread across the queues.

FIG9 is a block diagram of an example computing system 140. According to an illustrative embodiment, the example computing system 140 is suitable for use in implementing the computerized components described herein. In general terms, the computing system 140 includes at least one processor 148 for performing actions according to instructions, and one or more memory devices 144 or 149 for storing instructions and data. The illustrated example computing system 140 includes one or more processors 148 communicating with memory 144 via a bus 142, at least one network interface controller 143 having a network interface port 146 for connecting to a network (not shown), and other components 145 (e.g., input/output ("I/O") components 147). Typically, the processor 148 executes instructions received from memory. The illustrated processor 148 incorporates or is directly connected to a cache memory 149. In some instances, instructions are read from memory 144 into cache memory 149 and executed by the processor 148 via cache memory 149.

More specifically, processor 148 can be any logic circuit that processes instructions, such as instructions retrieved from memory 144 or cache 149. In various embodiments, processor 148 is a microprocessor unit or a dedicated processor. Computing device 140 can be based on any processor, or collection of processors, capable of operating as described herein. Processor 148 can be a single-core or multi-core processor. Processor 148 can be a plurality of different processors.

Memory 144 can be any device suitable for storing computer-readable data. Memory 144 can be a device with fixed storage or a device for reading removable storage media. Examples include all of the following: non-volatile memory, media and memory devices, semiconductor memory devices (e.g., EPROM, EEPROM, SDRAM, and flash memory devices), magnetic disks, magneto-optical disks, and optical disks (e.g., CD ROM, DVD-ROM, or disk). Computing system 140 can have any number of memory devices 144.

Cache memory 149 is typically a form of computer memory placed very close to processor 148 for fast read times. In some embodiments, cache memory 149 is part of or on the same chip as processor 148. In some embodiments, there are multiple levels of cache memory 149, such as L2 and L3 cache layers.

The network interface controller 143 manages data exchange via a network interface 146 (sometimes referred to as a network interface port). The network interface controller 143 handles the physical and data link layers of the OSI model for network communications. In some embodiments, some of the network interface controller's tasks are handled by one or more of the processors 148. In some embodiments, the network interface controller 143 is part of the processor 148. In some embodiments, the computing system 140 has multiple network interfaces 146 controlled by a single controller 143. In some embodiments, the computing system 140 has multiple network interface controllers 143. In some embodiments, each network interface 146 is a connection point for a physical network link (e.g., a Category 5 Ethernet link). In some embodiments, the network interface controller 143 supports wireless network connections, and the interface port 146 is a wireless (e.g., radio) receiver/transmitter (e.g., for any of the IEEE 802.11 protocol, near-field communication (NFC), Bluetooth, ANT, or any other wireless protocol). In some embodiments, the network interface controller 143 implements one or more network protocols, such as Ethernet. Typically, computing system 140 exchanges data with other computing devices via physical or wireless links through network interface 146. Network interface 146 may be linked to another device directly or via an intermediary device, such as a network device (such as a hub, bridge, switch, or router), connecting computing device 140 to a data network, such as the Internet.

Computing system 140 may include or provide interfaces for one or more input or output ("I/O") devices. Input devices include, but are not limited to, keyboards, microphones, touch screens, foot switches, sensors, MIDI devices, and pointing devices such as mice or trackballs. Output devices include, but are not limited to, video displays, speakers, Braille terminals, lights, MIDI devices, and 2D or 3D printers.

Other components 145 may include I/O interfaces, external serial device ports, and any additional co-processors. For example, computing system 140 may include interfaces (e.g., Universal Serial Bus (USB) interfaces) for connecting input devices, output devices, or additional storage devices (e.g., portable flash drives or external media drives). In some embodiments, computing device 140 includes additional devices 145 such as co-processors, for example, mathematical co-processors that can assist processor 148 in performing high-precision or complex calculations.

The subject matter described in this specification and the implementation of the operation can be implemented in a digital electronic circuit, or in a computer software embedded as a tangible medium, firmware, or hardware, including the structure disclosed in this specification and its structural equivalent, or a combination of one or more of them. The implementation of the subject matter described in this specification can be implemented as one or more computer programs embedded in a tangible medium, that is, one or more modules of computer program instructions encoded on one or more computer storage media to be executed by a data processing device or for controlling the operation of a data processing device. The computer storage medium can be a computer-readable storage device, a computer-readable storage substrate, a random or sequential access memory array or device, or a combination of one or more of them, or included therein. The computer storage medium can also be one or more separate components or media (e.g., multiple CDs, disks, or other storage devices), or included therein. The computer storage medium can also be tangible and non-temporary.

The operations described in this specification can be implemented as operations performed by a data processing apparatus on data stored on one or more computer-readable storage devices or received from other sources.

A computer program (also referred to as a program, software, software application, script, or code) can be written in any form of programming language, including compiled or interpreted languages, declarative or procedural languages, and can be deployed in any form, including standalone programs or including modules, components, subroutines, objects, or other units suitable for use in a computing environment. A computer program can, but need not, correspond to a file in a file system. A program can be stored in a portion of a file hosting other programs or data (e.g., one or more scripts stored in a markup language document), can be stored in a single file dedicated to the program in question, or can be stored in multiple collaborative files (e.g., files storing one or more modules, subroutines, or partial codes). A computer program can be deployed to execute on one or more computers, the one or more computers being located in one location or distributed in multiple locations and interconnected by a communication network. Examples of communication networks include local area networks ("LANs") and wide area networks ("WANs"), interconnected networks (e.g., the Internet), and peer-to-peer networks (e.g., peer-to-peer networks).

The processes and logic flows described in this specification can be performed by one or more programmable processors executing one or more computer programs to perform actions by operating on input data and generating output. The processes and logic flows can also be performed by devices that can also be implemented as special-purpose logic circuits, such as FPGAs (field programmable gate arrays) or ASICs (application-specific integrated circuits). Such special-purpose circuits may be referred to as computer processors, even though they are not general-purpose processors.

While this specification contains numerous specific implementation details, these should not be construed as limiting the scope of any invention that may be claimed, but rather as descriptions of features specific to particular implementations of particular inventions. Certain features described in this specification in the context of separate implementations can also be implemented in combination in a single implementation. Conversely, various features described in the context of a single implementation can also be implemented separately in multiple implementations or in any suitable subcombination. Furthermore, while features may be described above as functioning in certain combinations and even initially claimed as such, one or more features from a claimed combination can be deleted from the combination in certain circumstances, and a claimed combination can be directed to a subcombination or variations of a subcombination.

Similarly, although operations are depicted in the accompanying drawings in a particular order, this should not be understood as requiring that such operations be performed in the particular order shown or in a sequential order, or that all illustrated operations be performed in order to achieve the desired results. In some cases, multitasking and parallel processing may be advantageous. Furthermore, the separation of various system components in the embodiments described above should not be understood as requiring such separation in all embodiments, and it should be understood that the described program components and systems can generally be integrated together in a single software product or packaged into multiple software products.

References to "or" can be interpreted as inclusive, such that any term described using "or" can refer to any of the described terms, singly, plurally, and all. The labels "first," "second," "third," etc. are not necessarily intended to indicate an order and are generally used only to distinguish between identical or similar items or elements.

Thus, specific embodiments of the subject matter have been described. Other embodiments are within the scope of the following claims. In some cases, the actions recited in the claims can be performed in a different order and still achieve the desired results. Furthermore, the processes depicted in the accompanying figures do not necessarily require the specific order shown, or sequential order, to achieve the desired results. In some embodiments, multitasking or parallel processing may be utilized.

Claims (15)

1. A network device, comprising: Network card; At least one processor; Memory; A network interface driver executing on the at least one processor, the network interface driver being configured to: Receive a set of data packets, the set of data packets including a first subset of data packets generated and forwarded by a first software application for transmission by the network interface card (NIC) and a second subset of data packets generated and forwarded by a second software application for transmission by the NIC; Descriptors associated with the set of data packets are stored in the main transmission queue in a first order; The descriptor associated with the set of data packets is passed to a data service shaping module that executes on one of the at least one processor and the network interface card; and In response to determining that the network interface card (NIC) has successfully transmitted data packets from the data packet set, before forwarding an additional subset of data packets to the network interface driver, a packet transmission completion message is communicated to a software application that has generated and forwarded the packets for transmission by the NIC and is waiting to receive the packet transmission completion message from the network interface driver, the software application including either the first software application or the second software application; and The data service shaping module is configured as follows: Maintain multiple service shaping queues, wherein the multiple service shaping queues include at least a first service shaping queue and a second service shaping queue, and wherein each service shaping queue has at least one associated transmission rate rule; Receive the descriptor associated with the set of data packets transmitted by the network interface driver from the main transmission queue; The data packets associated with the received descriptors are classified. For each data packet in the data packet set, determine whether the transmission of the data packet will be delayed by the network interface card; If it is determined that the data packets are delayed: Remove the first descriptor associated with the data packet from the main transmission queue and store the first descriptor in a specific service shaping queue among the plurality of service shaping queues based on the classification result of the data packet; The network interface card (NIC) transmits the data packets associated with the first descriptor stored in the corresponding service shaping queue according to the transmission rate control rules associated with the specific service shaping queue; and If it is determined that the data packet was not delayed, the network interface card (NIC) transmits the data packet; and The network interface driver is notified of the successful transmission of the data packet set in a second order different from the first order. 2. The network device of claim 1, wherein the network interface driver is included within a first layer of the Transmission Control Protocol (TCP) stack of an operating system executing on the at least one processor, and is configured to communicate with a software application included in an upper layer of the TCP stack, the upper layer including the application layer or the Internet/transport layer of the TCP stack. 3. The network device according to claim 1, wherein the network interface card is configured as follows: Transmitting a first data packet using a first resource, wherein the first resource stores the first data packet; and In response to transmitting the first data packet, the first resource releases the memory space used to store the first data packet to store the new data packet, and the software application can access the first resource. 4. The network device of claim 3, wherein the first resource is part of a memory buffer. 5. The network device of claim 1, wherein the data packets determined not to be delayed are transmitted before the data packets determined to be delayed are transmitted. 6. The network device of claim 1, wherein the network interface card is configured to transmit the one or more data packets associated with the one or more descriptors stored in the main transmission queue in a shuffled order relative to the order in which the one or more descriptors are stored in the main transmission queue. 7. The network device of claim 1, wherein the first subset of data packets belongs to a first flow, and wherein the second subset of data packets belongs to a second flow. 8. The network device according to claim 7, wherein the network interface card is configured as follows: Transmit one or more data packets associated with the one or more descriptors stored in the first service shaping queue in the order in which they are stored; and One or more data packets associated with the one or more descriptors stored in the second service shaping queue are transmitted in the order in which they are stored in the second service shaping queue. 9. A method for multi-stream service shaping, comprising: A set of data packets is received by a network interface driver executing on at least one processor, the set of data packets including a first subset of data packets generated and forwarded by a first software application for transmission by a network interface card (NIC) and a second subset of data packets generated and forwarded by a second software application for transmission by the NIC; The network interface driver stores descriptors associated with the set of data packets in the main transmission queue in a first order; The network interface driver passes the descriptor associated with the data packet set to a data service shaping module that is executed on one of the at least one processor and the network interface card; In response to determining that the network interface card has successfully transmitted data packets in the data packet set, before forwarding an additional subset of data packets to the network interface driver, the network interface driver communicates a packet transmission completion message to a software application that has generated and forwarded the packets for transmission by the network interface card and is waiting to receive the packet transmission completion message from the network interface driver, the software application including the first software application or the second software application. The data service shaping module maintains multiple service shaping queues, wherein the multiple service shaping queues include at least a first service shaping queue and a second service shaping queue, and wherein each service shaping queue has at least one associated transmission rate rule; The data service shaping module receives the descriptor associated with the set of data packets transmitted by the network interface driver from the main transmission queue; The data service shaping module classifies the set of data packets associated with the received descriptors. For each data packet in the data packet set, the data service shaping module determines whether the transmission of the data packet will be delayed by the network card; If it is determined that the data packets are delayed: Remove the first descriptor associated with the data packet from the main transmission queue and store the first descriptor in a specific service shaping queue among the plurality of service shaping queues based on the classification result of the data packet; The data service shaping module causes the network interface card (NIC) to transmit the data packets associated with the first descriptor stored in the corresponding service shaping queue, according to the transmission rate control rules associated with the specific service shaping queue; and If it is determined that the data packet was not delayed, the network interface card (NIC) transmits the data packet; and The data service shaping module notifies the network interface driver of the successful transmission of the data packet set in a second order different from the first order. 10. The method of claim 9, wherein the network interface driver is included within a first layer of a Transmission Control Protocol (TCP) stack of an operating system executing on the at least one processor, and is configured to communicate with a software application included in an upper layer of the TCP stack, the upper layer including the application layer or Internet/transport layer of the TCP stack. 11. The method of claim 9, further comprising: The network interface card (NIC) uses a first resource to transmit a first data packet, the first resource storing the first data packet; and In response to transmitting the first data packet, the first resource releases the memory space used to store the first data packet to store the new data packet, and the software application can access the first resource. 12. The method of claim 11, wherein the first resource is a portion of a memory buffer. 13. The method of claim 9, wherein the data packets determined not to be delayed are transmitted before the data packets determined to be delayed; and/or The method further includes: The network interface card (NIC) transmits the one or more data packets associated with the one or more descriptors stored in the main transmission queue in a shuffled order relative to the order in which the descriptors are stored in the main transmission queue. 14. The method of claim 13, wherein the first subset of data packets belongs to a first stream, and wherein the second subset of data packets belongs to a second stream; and/or The method further includes: The network interface card (NIC) transmits one or more data packets associated with one or more descriptors stored in the first service shaping queue in the order in which they are stored in the first service shaping queue; and The network interface card (NIC) transmits one or more data packets associated with one or more descriptors stored in the second service shaping queue in the order in which they are stored in the second service shaping queue. 15. A non-transitory computer-readable storage medium comprising instructions that, when executed by at least one processor, cause the at least one processor to perform the method of any one of claims 9 to 14.