TRAFFIC SHAPING METHOD AND APPARATUS

Abstract

This application provides a traffic shaping method and apparatus. The method includes: A packet marking apparatus receives a first packet; the packet marking apparatus determines an enqueuing queue of the first packet; and the packet marking apparatus marks a queue identifier of the first packet as a queue identifier of the enqueuing queue of the first packet, and then sends the queue identifier of the first packet to a packet output apparatus, where the packet output apparatus is configured to send, based on the queue identifier of the first packet, the first packet to a corresponding queue for outputting. Therefore, packet output time after traffic shaping can be determined.

Claims

1. A traffic shaping method, comprising: receiving, by a packet marking apparatus, a first packet; determining, by the packet marking apparatus, an enqueuing queue of the first packet; and marking, by the packet marking apparatus, a queue identifier of the first packet as a queue identifier of the enqueuing queue of the first packet, and then sending, by the packet marking apparatus, the queue identifier of the first packet to a packet output apparatus, wherein the packet output apparatus is configured to send, based on the queue identifier of the first packet, the first packet to a corresponding queue for outputting.

2. The method according to claim 1, wherein the determining, by the packet marking apparatus, an enqueuing queue of the first packet comprises: determining, by the packet marking apparatus based on an arrival moment of the first packet, queues that the first packet can enqueue; and determining, by the packet marking apparatus, the enqueuing queue of the first packet from the queues that the first packet can enqueue, wherein the enqueuing queue is one queue in a group of gating queues, the group of gating queues comprise N queues, duration in which each queue in the N queues is continuously enabled is T, and the N queues are cyclically enabled in a preset order; and a total length of packets that can be enqueued in each flow i and each queue in the N queues is less than or equal to a first threshold, or a total length of packets that can be enqueued in each flow i and each queue in the N queues is less than or equal to a sum of a first threshold and a maximum packet length of the flow i, wherein N is a positive integer greater than 1, and i is a positive integer.

3. The method according to claim 2, wherein the determining, by the packet marking apparatus based on an arrival moment of the first packet, queues that the first packet can enqueue comprises: determining, by the packet marking apparatus based on the arrival moment of the first packet, maximum transmission duration tm required for sending the packet from the packet marking apparatus to the packet output apparatus, and minimum transmission duration t.sub.min required for sending the packet from the packet marking apparatus to the packet output apparatus, the queues that the first packet can enqueue.

4. The method according to claim 3, wherein the determining, by the packet marking apparatus based on the arrival moment of the first packet, maximum transmission duration t.sub.max required for sending the packet from the packet marking apparatus to the packet output apparatus, and minimum transmission duration t.sub.min required for sending the packet from the packet marking apparatus to the packet output apparatus, the queues that the first packet can enqueue comprises: calculating, by the packet marking apparatus based on the arrival moment to of the first packet and t.sub.max, a latest moment t.sub.1=t.sub.0+t.sub.max at which the first packet arrives at the packet output apparatus, and calculating, by the packet marking apparatus based on the arrival moment to of the first packet and t.sub.min, an earliest moment t.sub.1′=t.sub.0+t.sub.min at which the first packet arrives at the packet output apparatus; and determining, by the packet marking apparatus based on a first queue in an enabled state at the moment t.sub.1 and a second queue in the enabled state at the moment t.sub.1; the queues that the first packet can enqueue.

5. The method according to claim 4, wherein the determining, by the packet marking apparatus based on a first queue in an enabled state at the moment t.sub.1 and a second queue in the enabled state at the moment t.sub.1′; the queues that the first packet can enqueue comprises: if the first queue and the second queue are a same queue, determining, by the packet marking apparatus, that the queues that the first packet can enqueue are N−1 queues in the group of gating queues other than the first queue; if the first queue and the second queue are two adjacent queues, determining, by the packet marking apparatus, that the queues that the first packet can enqueue are N−2 queues in the group of gating queues other than the first queue and the second queue; or if there are J queues between the first queue and the second queue, determining, by the packet marking apparatus, that the queues that the first packet can enqueue are N−J−2 queues in the group of gating queues other than the first queue, the second queue, and the J queues between the first queue and the second queue.

6. The method according to claim 4, wherein the determining, by the packet marking apparatus, the enqueuing queue of the first packet from the queues that the first packet can enqueue comprises: determining, by the packet marking apparatus, that a total length B.sub.add of unoutput packets of a first flow in the queues that the first packet can enqueue is less than a maximum buffer size B of the first flow in the queues that the first packet can enqueue, wherein the first flow is a flow to which the first packet belongs; or determining, by the packet marking apparatus, that a sum of B.sub.add and the first packet is less than or equal to B; and determining, by the packet marking apparatus based on B.sub.add and the first threshold, the enqueuing queue of the first packet from the queues that the first packet can enqueue.

7. The method according to claim 6, wherein the determining, by the packet marking apparatus based on B.sub.add and the first threshold, the enqueuing queue of the first packet from the queues that the first packet can enqueue comprises: if B.sub.add is greater than or equal to M−1 times the first threshold and less than M times the first threshold, determining, by the packet marking apparatus, that the enqueuing queue of the first packet is an M.sup.th queue following the first queue in the queues that the first packet can enqueue, wherein M is a positive integer greater than or equal to 1.

8. The method according to claim 6, wherein the determining, by the packet marking apparatus based on B.sub.add and the first threshold, the enqueuing queue of the first packet from the queues that the first packet can enqueue comprises: if a total length of packets that are of the first flow and that are currently enqueued in a 1.sup.st queue following the first queue is less than the first threshold, determining, by the packet marking apparatus, that the enqueuing queue of the first packet is the 1.sup.st queue following the first queue; or if a total length of packets that are of the first flow and that are currently enqueued in a 1.sup.st queue following the first queue is greater than or equal to the first threshold, determining, by the packet marking apparatus, that the enqueuing queue of the first packet is a K.sup.th queue following the first queue in the queues that the first packet can enqueue, wherein K is a positive integer greater than or equal to 2, and a total length of currently enqueued packets in the K.sup.th queue is less than the first threshold.

9. The method according to claim 8, wherein the determining, by the packet marking apparatus, that the enqueuing queue of the first packet is a K.sup.th queue following the first queue in the queues that the first packet can enqueue comprises: starting from a 2.sup.nd queue following the first queue, determining, by the packet marking apparatus from the queues that the first packet can enqueue, a 1.sup.st queue in which the total length of currently enqueued packets of the first flow is less than the first threshold; and determining, as the K.sup.th queue, the 1.sup.st queue in which the total length of the currently enqueued packets of the first flow is less than the first threshold.

10. The method according to claim 6, wherein the determining, by the packet marking apparatus based on B.sub.add and the first threshold, the enqueuing queue of the first packet from the queues that the first packet can enqueue comprises: if a sum of a total length of packets that are of the first flow and that are currently enqueued in a 1.sup.st queue following the first queue and a length of the first packet is less than or equal to the first threshold, determining, by the packet marking apparatus, that the enqueuing queue of the first packet is the 1.sup.st queue following the first queue; or if a sum of a total length of packets that are of the first flow and that are currently enqueued in a 1.sup.st queue following the first queue and a length of the first packet is greater than the first threshold, determining, by the packet marking apparatus, that the enqueuing queue of the first packet is a K.sup.th queue following the first queue in the queues that the first packet can enqueue, wherein K is a positive integer greater than or equal to 2, and a sum of a total length of currently enqueued packets in the K.sup.th queue and the length of the first packet is less than the first threshold.

11. A traffic shaping method, comprising: receiving, by a packet output apparatus, a first packet, wherein the first packet carries a queue identifier, and the queue identifier is a queue identifier of an enqueuing queue of the first packet; and sending, by the packet output apparatus based on the queue identifier of the first packet, the first packet to a corresponding queue for outputting.

12. The method according to claim 11, wherein the enqueuing queue of the first packet is one queue in a group of gating queues, the group of gating queues comprise N queues, duration in which each queue in the N queues is continuously enabled is T, and the N queues are cyclically enabled in a preset order; and a total length of packets that can be enqueued in each flow i and each queue in the N queues is less than or equal to a first threshold, or a total length of packets that can be enqueued in each flow i and each queue in the N queues is less than or equal to a sum of a first threshold and a maximum packet length of the flow i, wherein N is a positive integer greater than 1, and i is a positive integer.

13. The method according to claim 12, wherein the first threshold is B.sub.i×T, B.sub.i is a bandwidth of a first flow, and the first flow is a flow to which the first packet belongs.

14. A traffic shaping apparatus, comprising: a receiving module, configured to receive a first packet; a determining module, configured to determine an enqueuing queue of the first packet; and a sending module, configured to: mark a queue identifier of the first packet as a queue identifier of the enqueuing queue of the first packet, and then send the queue identifier of the first packet to a packet output apparatus, wherein the packet output apparatus is configured to send, based on the queue identifier of the first packet, the first packet to a corresponding queue for outputting.

15. The apparatus according to claim 14, wherein the determining module comprises: a determining unit, configured to determine, based on an arrival moment of the first packet, queues that the first packet can enqueue; and a processing unit, configured to determine the enqueuing queue of the first packet from the queues that the first packet can enqueue, wherein the enqueuing queue is one queue in a group of gating queues, the group of gating queues comprise N queues, duration in which each queue in the N queues is continuously enabled is T, and the N queues are cyclically enabled in a preset order; and a total length of packets that can be enqueued in each flow i and each queue in the N queues is less than or equal to a first threshold, or a total length of packets that can be enqueued in each flow i and each queue in the N queues is less than or equal to a sum of a first threshold and a maximum packet length of the flow i, wherein N is a positive integer greater than 1, and i is a positive integer.

16. The apparatus according to claim 15, wherein the determining unit is configured to: determine, based on the arrival moment of the first packet, maximum transmission duration t.sub.max required for sending the packet from the packet marking apparatus to the packet output apparatus, and minimum transmission duration t.sub.min required for sending the packet from the packet marking apparatus to the packet output apparatus, the queues that the first packet can enqueue.

17. The apparatus according to claim 16, wherein the determining unit is configured to: calculate, based on the arrival moment t.sub.0 of the first packet and t.sub.max, a latest moment t.sub.1=t.sub.0+t.sub.max at which the first packet arrives at the packet output apparatus, and calculate, based on the arrival moment to of the first packet and t.sub.min, an earliest moment t.sub.1′=t.sub.0+t.sub.min at which the first packet arrives at the packet output apparatus; and determine, based on a first queue in an enabled state at the moment t.sub.1 and a second queue in the enabled state at the moment t.sub.1′, the queues that the first packet can enqueue.

18. The apparatus according to claim 17, wherein the determining unit is configured to: if the first queue and the second queue are a same queue, determine that the queues that the first packet can enqueue are N−1 queues in the group of gating queues other than the first queue; if the first queue and the second queue are two adjacent queues, determine that the queues that the first packet can enqueue are N−2 queues in the group of gating queues other than the first queue and the second queue; or if there are J queues between the first queue and the second queue, determine that the queues that the first packet can enqueue are N−J−2 queues in the group of gating queues other than the first queue, the second queue, and the J queues between the first queue and the second queue.

19. The apparatus according to claim 17, wherein the processing unit is configured to: determine that a total length B.sub.add of unoutput packets of a first flow in the queues that the first packet can enqueue is less than a maximum buffer size B of the first flow in the queues that the first packet can enqueue, wherein the first flow is a flow to which the first packet belongs; or determine, that a sum of B.sub.add and the first packet is less than or equal to B; and determine, based on B.sub.add and the first threshold, the enqueuing queue of the first packet from the queues that the first packet can enqueue.

20. The apparatus according to claim 19, wherein the processing unit is configured to: if B.sub.add is greater than or equal to M−1 times the first threshold and less than M times the first threshold, determine that the enqueuing queue of the first packet is an M.sup.th queue following the first queue in the queues that the first packet can enqueue, wherein M is a positive integer greater than or equal to 1.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0088] FIG. 1 is a schematic diagram of an architecture of a communication system to which a traffic shaping method according to an embodiment of this application can be applied;

[0089] FIG. 2 is a flowchart of an embodiment of a traffic shaping method according to this application;

[0090] FIG. 3 is a schematic diagram of enabling and disabling a gating queue according to this application;

[0091] FIG. 4 is a schematic diagram in which enabling time of each gating queue is corresponding to a period on a time axis;

[0092] FIG. 5 is a schematic diagram of determining queues that a first packet can enqueue according to an embodiment of this application;

[0093] FIG. 6 is a schematic diagram of a first queue in an enabled state at a moment t.sub.1 according to an embodiment of this application;

[0094] FIG. 7 is a schematic diagram of a second queue in an enabled state at a moment t.sub.1′ according to an embodiment of this application;

[0095] FIG. 8 is another schematic diagram of a first queue in an enabled state at a moment t.sub.1 according to an embodiment of this application;

[0096] FIG. 9 is another schematic diagram of a second queue in an enabled state at a moment t.sub.1′ according to an embodiment of this application;

[0097] FIG. 10 is a schematic diagram of discarding a first packet according to an embodiment of this application;

[0098] FIG. 11 is a schematic diagram of determining an enqueuing queue of a first packet according to an embodiment of this application;

[0099] FIG. 12 is a flowchart of an embodiment of a traffic shaping method according to this application;

[0100] FIG. 13 is a schematic diagram of a process in which a packet is sent to a packet output apparatus after the packet is processed by a packet marking apparatus;

[0101] FIG. 14 is a schematic diagram of outputting a packet within determined time;

[0102] FIG. 15 is a schematic diagram of a structure of an embodiment of a traffic shaping apparatus according to this application;

[0103] FIG. 16 is a schematic diagram of a structure of an embodiment of a traffic shaping apparatus according to this application;

[0104] FIG. 17 is a schematic diagram of a structure of an embodiment of a traffic shaping apparatus according to this application; and

[0105] FIG. 18 is a schematic diagram of a structure of a traffic shaping apparatus according to this application.

DESCRIPTION OF EMBODIMENTS

[0106] In embodiments of this application, words such as “example” or “for example” are used to indicate examples, instances, or description. Any embodiment or solution described as “example” or “for example” in embodiments of this application is not to be construed as being more preferred or having more advantages than another embodiment or solution. Exactly, use of the word such as “example” or “for example” is intended to present a relative concept in a specific manner. Terms “first” and “second” are merely used for a purpose of description, and shall not be understood as an indication or implication of relative importance.

[0107] Embodiments of this application mainly relate to a traffic shaping technology of a deterministic network. Traffic shaping is a measure used to actively adjust a traffic output rate. A typical function of traffic shaping is to limit traffic and a burst that exits a connection of a network, so that packets are sent out at a relatively even speed. Traffic shaping forces traffic to follow a certain bandwidth allocation limit by reducing the traffic output rate.

[0108] Embodiments of this application may be applied to the deterministic network. A core of the deterministic network is to ensure an end-to-end bandwidth, a latency, and jitter of a service flow. A shaping requirement on an iGW in the deterministic network is as follows: A burst (burst) volume of traffic after traffic shaping on the iGW is less than or equal to B.sub.i×T bytes, where B.sub.i represents a bandwidth specified in a service level agreement of each flow i. Embodiments of this application may be applied to a case in which traffic with a low average rate and a large burst degree accesses the deterministic network after being shaped by using the traffic shaping method provided in this application, to implement a deterministic latency. The “deterministic latency” means that a latency and jitter during a packet transmission meet a specified upper limit on the premise that the packet complies with a preset burstness requirement.

[0109] In the conventional technology, traffic shaping is implemented by running a leaky bucket algorithm and inter-flow scheduling per flow. A problem in the method is that a scheduling latency causes uncertain output time of a packet. This application provides a traffic shaping method and apparatus. In this method, a group of gating queues rotated by timing switches are used, the group of gating queues include N queues, and duration in which each queue in the N queues is continuously enabled is T. After a packet marking apparatus receives a packet, an enqueuing queue of the packet is first determined, and then the packet is marked with a queue identifier of the enqueuing queue of the packet, then the packet is sent to a packet output apparatus, and the packet output apparatus sends, based on the queue identifier of the packet, the packet to a corresponding queue for outputting. A total length of packets that can be enqueued in each flow i and each queue in the N queues is less than or equal to a first threshold, or is less than or equal to a sum of a first threshold and a maximum packet length of the flow i. Because packets are output from different gating queues, and enabling time of different gating queues is known, packet output time is fixed, that is, the packet output time is known.

[0110] In addition, in order to achieve high performance, packets are processed in batches instead of packets per packet in the traffic shaping method in the conventional technology. As a result, a burst occurs. After packets with a low average rate are shaped by using the foregoing method, a traffic burst volume exceeds a quantity of bytes allowed to be sent in each period (B.sub.i×T). Consequently, traffic shaping precision is poor, a traffic shaping requirement of a deterministic network is not met. In this application, a total length of packets that can be enqueued in each flow i and each queue is less than or equal to the first threshold, or a total length of packets that can be enqueued in each flow i and each queue is less than or equal to a sum of the first threshold and a maximum packet length of the flow i. In other words, a quantity of bytes sent by each flow i in each period T is controlled to be less than or equal to the first threshold, or a quantity of bytes sent by each flow i in each period T is controlled to be less than or equal to a sum of the first threshold and the maximum packet length of the flow i, where the first threshold may be B.sub.i×T. In this way, high shaping precision is ensured, and a shaping requirement of a deterministic network is met.

[0111] The following describes in detail the traffic shaping method and apparatus provided in this application with reference to the accompanying drawings.

[0112] FIG. 1 is a schematic diagram of an architecture of a communication system to which a traffic shaping method according to an embodiment of this application can be applied. As shown in FIG. 1, the communication system may include a base station (Base Station, BS) 11, a base station gateway (Cell Site Gateway, CSG) 12, an aggregation site gateway (Aggregation Site Gateway, ASG) 13, and a mobile edge computing (Mobile Edge Computing, MEC) server 14. Each substation is connected to a BS by using a data transfer unit (Data Transfer unit, DTU). For example, each BS is connected to two DTUs, and each BS is connected to a network through a CSG. A plurality of CSGs form a CSG ring, and each ASG can be connected to n CSG rings. For example, one CSG ring includes 20 CSGs, and the CSG ring is connected to an ASG. For example, each ASG can be connected to 20 CSG rings. When the BS transmits data to the MEC, a packet sent from the BS reaches the ASG through the CSG ring, and traffic reaches the MEC through one hop on the ASG. The BS is an upstream device of the CSG, and the CSG may be referred to as an ingress gateway. The BS sends a packet to the CSG. When traffic increases or decreases instantaneously, a packet transmission rate is uneven. In this case, traffic shaping needs to be performed. Specifically, traffic shaping may be performed on each CSG. An apparatus for performing the traffic shaping method provided in this application may be disposed on each CSG, so that traffic shaping can be performed on the CSG. For example, the packet marking apparatus and the packet output apparatus provided in this embodiment of this application may be disposed on each CSG, so that traffic shaping can be performed on the CSG by using the packet marking apparatus and the packet output apparatus.

[0113] The communication system shown in FIG. 1 is merely an example, and this application is not limited thereto.

[0114] The traffic shaping method provided in this embodiment of this application may be performed by a network device such as a router or a switch, and the network device may be specifically an ingress gateway or a provider edge (Provider Edge, PE) router. The packet marking apparatus and the packet output apparatus shown in the following may be disposed in the ingress gateway or the PE router. Optionally, the packet marking apparatus may be a network processor (Network Processor, NP), and the packet output apparatus may be a traffic managing device. Alternatively, the packet marking apparatus and the packet output apparatus may be different hardware modules. The packet marking apparatus and the packet output apparatus may be deployed on a same device, or may be separately deployed on a connected previous-hop network device and a connected next-hop network device.

[0115] FIG. 2 is a flowchart of an embodiment of a traffic shaping method according to this application. As shown in FIG. 2, the method in this embodiment may include the following steps.

[0116] S101: A packet marking apparatus receives a first packet.

[0117] Specifically, a first device may receive the first packet sent by an upstream device of the first device, and the packet marking apparatus may receive a packet at a moment, or may receive a pack of packets at a moment, where the first packet is one of the pack of packets. The packet marking apparatus performs the method of S102 and S103 on each packet flow by flow according to an order of packet arrival moments to perform processing.

[0118] S102: The packet marking apparatus determines an enqueuing queue of the first packet.

[0119] Specifically, the enqueuing queue of the first packet is one queue in a group of gating queues. Specifically, the group of gating queues in this embodiment of this application includes N queues. FIG. 3 is a schematic diagram of enabling and disabling the gating queues according to this application. As shown in FIG. 3, the group of gating queues include the N queues, where the N queues are, for example, Q.sub.0, Q.sub.1, Q.sub.2, Q.sub.3, Q.sub.4, . . . , and Q.sub.N−1. Duration in which each queue in the N queues is continuously enabled is T, only one of the N queues is enabled at any moment, and remaining queues are disabled. As shown in FIG. 3, the queue Qi is enabled at a moment, the remaining queues Q.sub.0, Q.sub.2, Q.sub.3, Q.sub.4, . . . , and Q.sub.N−1 are disabled, and the N queues are enabled in a preset order. For example, the N queues are cyclically enabled in a natural order from a 1.sup.st queue to an N.sup.th queue. After enabling time of each queue ends, a current queue is disabled, and a next queue is enabled. FIG. 4 is a schematic diagram of enabling time of each gating queue corresponding to a period on a time axis. As shown in FIG. 4, the N queues are enabled in the order of Q.sub.0, Q.sub.1, Q.sub.2, Q.sub.3, Q.sub.4, . . . , and Q.sub.N−1, and Q.sub.N−1 is disabled after being enabled for duration of T, and then Q.sub.0 is enabled. A total length of packets that can be enqueued in each flow i and each queue in the N queues is less than or equal to a first threshold. For example, the total length of packets that can be enqueued in each queue of the N queues is equal to the first threshold, is subtracted by 1 byte from the first threshold, or is subtracted by 2 bytes from the first threshold. Alternatively, a total length of packets that can be enqueued in each flow i and each queue in the N queues is less than or equal to a sum of a first threshold and a maximum packet length of the flow i, where i is a positive integer. For example, for the flow i, the total length of packets that can be enqueued in each flow i and each queue is less than or equal to the sum of the first threshold and the maximum packet length of the flow i. Optionally, the first threshold may be B.sub.i×T, and Bi is a bandwidth of a flow to which the first packet belongs. In this embodiment of this application, the total length of packets that can be enqueued in each flow i and each queue is less than or equal to the first threshold, or the total length of packets that can be enqueued in each flow i and each queue is less than or equal to the sum of the first threshold and the maximum packet length of the flow i. In other words, a quantity of bytes sent by each flow i in each period T is controlled to be less than or equal to the first threshold, or a quantity of bytes sent by each flow i in each period T is controlled to be less than or equal to the sum of the first threshold and the maximum packet length of the flow i. In this way, high shaping precision is ensured, and a shaping requirement of a deterministic network is met.

[0120] The gating queues in this embodiment of this application may be a group of gating queues deployed for each output port, or may be a group of gating queues shared by all output ports. The output port may be an output port on a device such as an ingress gateway or a PE router.

[0121] In an implementation, S102 may include the following steps.

[0122] S1021: The packet marking apparatus determines, based on an arrival moment of the first packet, queues that the first packet can enqueue.

[0123] The arrival moment of the first packet is a moment at which the first packet arrives at the packet marking apparatus. Specifically, if the first packet enqueues at a moment t, the first packet cannot enqueue a queue in an enabled state at the moment t. For example, if the queue in the enabled state at the moment t is Q, the first packet cannot enqueue Q.sub.x, because if the first packet enqueues the queue Q.sub.x, the first packet may not be sent in time before Q.sub.x is disabled. The packet marking apparatus needs to first determine the queues that the first packet can enqueue, that is, queues that can be currently enqueued, and then determine a final enqueuing queue from the queues that the first packet can enqueue. Specifically, the packet marking apparatus may determine, based on the arrival moment of the first packet, maximum transmission duration t.sub.max required for sending the packet from the packet marking apparatus to the packet output apparatus, and minimum transmission duration t.sub.min required for sending the packet from the packet marking apparatus to the packet output apparatus, the queues that the first packet can enqueue.

[0124] The maximum transmission duration t.sub.max required for sending the packet from the packet marking apparatus to the packet output apparatus and the minimum transmission duration t.sub.min required for sending the packet from the packet marking apparatus to the packet output apparatus may be preset values. Specifically, data transmission duration between the packet marking apparatus and the packet output apparatus may be pre-stored in the packet marking apparatus after being determined.

[0125] In a possible implementation, that the packet marking apparatus determines, based on the arrival moment of the first packet, t.sub.max, and t.sub.min, the queues that the first packet can enqueue may include:

[0126] First, the packet marking apparatus calculates, based on the arrival moment t.sub.0 of the first packet and t.sub.max, a latest moment t.sub.1=t.sub.0+t.sub.max at which the first packet arrives at the packet output apparatus, and calculates, based on the arrival moment to of the first packet and t.sub.min, an earliest moment t.sub.1′=t.sub.0+t.sub.min at which the first packet arrives at the packet output apparatus.

[0127] Then, the packet marking apparatus determines, based on a first queue in an enabled state at the moment t.sub.1 and a second queue in the enabled state at the moment t.sub.1′, the queues that the first packet can enqueue.

[0128] Specifically, the duration T in which each queue in the gating queues is continuously enabled and enabling time of a 1.sup.st queue in the gating queues are pre-stored in the packet marking apparatus and the packet output apparatus. Both the packet marking apparatus and the packet output apparatus learn of the duration T in which each queue in the gating queues is continuously enabled and the enabling time of the 1.sup.st queue in the gating queues. Therefore, the packet marking apparatus may determine, based on the pre-stored duration T in which each queue in the gating queues is continuously enabled and the pre-stored enabling time of the 1.sup.st queue in the gating queues, the first queue in the enabled state at the moment t.sub.1 and the second queue in the enabled state at the moment t.sub.1′. The packet marking apparatus may determine the enqueuing queue of the first packet based on the first queue and the second queue.

[0129] There are three possible cases in which the packet marking apparatus determines, based on the first queue in the enabled state at the moment t.sub.1 and the second queue in the enabled state at the moment t.sub.1′, the queues that the first packet can enqueue.

[0130] 1. If the first queue and the second queue are a same queue, the packet marking apparatus determines that the queues that the first packet can enqueue are N−1 queues in the group of gating queues other than the first queue.

[0131] 2. If the first queue and the second queue are two adjacent queues, the packet marking apparatus determines that the queues that the first packet can enqueue are N−2 queues in the group of gating queues other than the first queue and the second queue.

[0132] 3. If there are J queues between the first queue and the second queue, the packet marking apparatus determines that the queues that the first packet can enqueue are N−J−2 queues in the group of gating queues other than the first queue, the second queue, and the J queues between the first queue and the second queue.

[0133] For example, the group of gating queues include N=10 queues. FIG. 5 is a schematic diagram of determining queues that the first packet can enqueue according to an embodiment of this application. As shown in FIG. 5, the first packet arrives at the packet marking apparatus at a moment t.sub.0. An earliest moment at which the first packet arrives at the packet output apparatus is t.sub.1′=t.sub.0+t.sub.min, a latest moment at which the first packet arrives at the packet output apparatus is t.sub.1=t.sub.0+t.sub.max, and a moment at which the first packet may arrive at the packet output apparatus is between t.sub.1′ and t.sub.1. The first queue in the enabled state at t.sub.1 is Q.sub.8, the second queue in the enabled state at t.sub.1′ is Q.sub.7, and Q.sub.7 and Q.sub.8 are two adjacent queues. Therefore, Q.sub.7 and Q.sub.8 are queues that cannot be enqueued, the queues that the first packet can enqueue are N−2=8 queues other than Q.sub.7 and Q.sub.8, that is, Q.sub.9, Q.sub.0, Q.sub.1, Q.sub.2, Q.sub.3, Q.sub.4, Q.sub.5, and Q.sub.6, and a .sup.st queue that the first packet can enqueue is Q.sub.9, and a last queue that the first packet can enqueue is Q.sub.6.

[0134] FIG. 6 is a schematic diagram of the first queue in the enabled state at the moment t.sub.1 according to an embodiment of this application. FIG. 7 is a schematic diagram of the second queue in the enabled state at the moment t.sub.1′ according to an embodiment of this application. As shown in FIG. 6 and FIG. 7, the first queue and the second queue are the same, and both the first queue and the second queue are Q.sub.x. In this case, the enqueuing queue of the first packet is one of N−1 queues other than the first queue Q.sub.x. It should be noted that if a queue in the enabled state at the moment t.sub.1 is Q.sub.x, the first packet cannot enqueue Q.sub.x, because if the first packet enqueues the queue Q.sub.x, the first packet may not be sent in time before Q.sub.x is disabled. Therefore, an earliest period in which the first packet can be sent is a period in which Q.sub.x−1 is enabled, and a latest period in which the first packet can be sent is a period in which Q.sub.x−1 is enabled. In this case, the enqueuing queue of the first packet is one of N−1 queues other than the first queue Q.sub.x.

[0135] FIG. 8 is another schematic diagram of the first queue in the enabled state at the moment t.sub.1 according to an embodiment of this application. FIG. 9 is another schematic diagram of the second queue in the enabled state at the moment t.sub.1′ according to an embodiment of this application. As shown in FIG. 7 and FIG. 8, the first queue and the second queue are different queues. If the first queue is Q.sub.x, and the second queue is Q.sub.x−1, the enqueuing queue of the first packet is one of N−2 queues other than the first queue Q.sub.x and the second queue Q.sub.x−1. It should be noted that if a queue in the enabled state at the moment t.sub.1 is Q.sub.x, the first packet cannot enqueue Q.sub.x, because if the first packet enqueues the queue Q.sub.x, the first packet may not be sent in time before Q.sub.x is disabled. Therefore, an earliest period in which the first packet can be sent is a period in which Q.sub.x+1 is enabled. If a queue in the enabled state at t.sub.1′ is Q.sub.x−1, the first packet cannot enqueue because if the first packet enqueues the queue Q.sub.x−1, the first packet may not be sent in time before Q.sub.x−1 is disabled. Therefore, a latest period in which the first packet can be sent is a period in which Q.sub.x−2 is enabled. In this case, the enqueuing queue of the first packet is one of N−2 queues other than the first queue Q.sub.x and the second queue Q.sub.x−1.

[0136] S1022: The packet marking apparatus determines, from the queues that the first packet can enqueue, the enqueuing queue of the first packet.

[0137] The enqueuing queue of the first packet is one queue in a group of gating queues, the group of gating queues include N queues, duration in which each queue in the N queues is continuously enabled is T, and the N queues are cyclically enabled in a preset order. A total length of packets that can be enqueued in each flow i and each queue in the N queues is less than or equal to a first threshold, or a total length of packets that can be enqueued in each flow i and each queue in the N queues is less than or equal to a sum of a first threshold and a maximum packet length of the flow i, where N is a positive integer greater than 1.

[0138] Specifically, the queues that the first packet can enqueue are determined, and whether the first packet can enqueue, and which queue in the queues that the first packet can enqueue need to be further determined. In an implementation, S1022 may be:

[0139] First, the packet marking apparatus determines that a total length B.sub.add of unoutput packets of a first flow in the queues that the first packet can enqueue is less than a maximum buffer size B of the first flow in the queues that the first packet can enqueue; or the packet marking apparatus determines that a sum of B.sub.add and the first packet is less than or equal to B, and the first flow is a flow to which the first packet belongs.

[0140] Then, the packet marking apparatus determines, based on B.sub.add and the first threshold, the enqueuing queue of the first packet from the queues that the first packet can enqueue.

[0141] The unoutput packets of the first flow in the queues that the first packet can enqueue is enqueued packets that are accumulated in the first flow before the enqueuing queue of the first packet is determined. In other words, when the packet marking apparatus determines the enqueuing queue of the first packet, the packet marking apparatus needs to first determine whether a current accumulated total length B.sub.add of enqueued packets of the first flow is less than the maximum buffer size B of the first flow in the queues that the first packet can enqueue, or whether a sum of B.sub.add and the first packet is less than or equal to B. For the foregoing two cases, determining whether the sum of B.sub.add and the first packet is less than or equal to B is applicable when a packet length is unchanged, and determining whether B.sub.add is less than or equal to B is applicable when a packet length changes. The method of determining whether B.sub.add is less than or equal to B indicates that a total length of packets stored in each queue is long. If the total length of packets stored in each queue is long, the enqueuing queue of the first packet can be determined from the queues that the first packet can enqueue based on B.sub.add and the first threshold. As shown in FIG. 5, queues Q.sub.9, Q.sub.0, Q.sub.1, Q.sub.2, Q.sub.3, Q.sub.4, Q.sub.5, and Q.sub.6 that the first packet can enqueue are used as an example. B.sub.add indicates a total length (also referred to as a total quantity of bytes) of packets that are of the first flow and that are enqueued in the queues (that is, buffered) Q.sub.9, Q.sub.0, Q.sub.1, Q.sub.2, Q.sub.3, Q.sub.4, Q.sub.5, and Q.sub.6. B is a total length (also referred to as a total quantity of bytes) of packets that are of the first flow and that are allowed to be buffered in Q.sub.9, Q.sub.0, Q.sub.1, Q.sub.2, Q.sub.3, Q.sub.4, Q.sub.5, and Q.sub.6. B may be preconfigured, and a configuration range of B is limited by a quantity of queues that the first packet can enqueue. Optionally, in the queues that the first packet can enqueue shown in FIG. 5, a maximum configuration of B may be 8B.sub.i×T.

[0142] The maximum buffer size B of the first flow in a currently enqueueable queue may be preconfigured, and the maximum buffer size B of different flows may be different.

[0143] Specifically, B is a maximum buffer size of the first flow in the currently enqueueable queue. When the enqueuing queue of the first packet is determined, it is necessary to first determine whether a total length B.sub.add of unoutput packets of the first flow in the currently enqueueable queue is less than B. If the total length B.sub.add of the unoutput packets of the first flow in the currently enqueueable queue is greater than or equal to B, it indicates that the total length B.sub.add of the unoutput packets of the first flow in the currently enqueueable queue reaches or exceeds the maximum buffer size B of the first flow in the currently enqueueable queue. In this case, the first packet cannot be enqueued, and the first packet is discarded. Queues that the first packet can enqueue are allocated only when B.sub.add is less than B. FIG. 10 is a schematic diagram of discarding the first packet according to an embodiment of this application. As shown in FIG. 10, B is equal to 3B.sub.i×T, and before the first packet arrives, B.sub.add already reaches 3B.sub.i×T. Therefore, the first packet is discarded. Alternatively, it is determined whether a sum of B.sub.add and the first packet is less than or equal to B, and when the sum of B.sub.add and the first packet is less than B, queues that the first packet can enqueue are allocated. When determining that the sum of B.sub.add and the first packet is greater than or equal to B, the packet marking apparatus discards the first packet.

[0144] Specifically, the packet marking apparatus determines, based on B.sub.add and the first threshold, the enqueuing queue of the first packet from the queues that the first packet can enqueue, in the following three implementations:

[0145] Implementation 1: If B.sub.add is greater than or equal to M−1 times the first threshold and less than M times the first threshold, the packet marking apparatus determines that the enqueuing queue of the first packet is an M.sup.th queue following the first queue in the queues that the first packet can enqueue, where M is a positive integer greater than or equal to 1.

[0146] Specifically, the packet marking apparatus determines an interval in which B.sub.add is located directly based on B.sub.add and the first threshold. For example, B.sub.add is greater than 5 times the first threshold and less than 4 times the first threshold. In this case, the enqueuing queue of the first packet is a 4.sup.th queue following the first queue in the queues that the first packet can enqueue.

[0147] Implementation 2: If a total length of packets that are of the first flow and that are currently enqueued in a 1.sup.st queue following the first queue is less than the first threshold, the packet marking apparatus determines that the enqueuing queue of the first packet is the 1.sup.st queue following the first queue.

[0148] If a total length of packets that are of the first flow and that are currently enqueued in a 1.sup.st queue following the first queue is greater than or equal to the first threshold, the packet marking apparatus determines that the enqueuing queue of the first packet is a K.sup.th queue following the first queue in the queues that the first packet can enqueue, where K is a positive integer greater than or equal to 2, and a total length of currently enqueued packets in the K.sup.th queue is less than the first threshold.

[0149] Specifically, in this manner, the enqueuing queue of the first packet starts from the 1.sup.st queue following the first queue. As shown in FIG. 5, queues Q.sub.9, Q.sub.0, Q.sub.1, Q.sub.2, Q.sub.3, Q.sub.4, Q.sub.5, and Q.sub.6 that the first packet can enqueue are used as an example. Q.sub.9, Q.sub.0, Q.sub.1, Q.sub.2, Q.sub.3, Q.sub.4, Q.sub.5, and Q.sub.6 tare queues following the first queue. A queue in which a total length of currently enqueued packets is less than the first threshold may be sequentially determined starting from Q.sub.9. If the first packet still fails to be enqueued after the first packet attempts to enqueue Q.sub.6, the first packet continues to be enqueued cyclically starting from Q.sub.9.

[0150] That the packet marking apparatus determines that the enqueuing queue of the first packet is a K.sup.th queue following the first queue in the queues that the first packet can enqueue may be:

[0151] The packet marking apparatus determines, starting from a 2.sup.nd queue following the first queue, from the queues that the first packet can enqueue, a 1.sup.st queue in which the total length of currently enqueued packets of the first flow is less than the first threshold, and determines, as the K.sup.th queue, the 1.sup.st queue in which the total length of the currently enqueued packets of the first flow is less than the first threshold.

[0152] Implementation 3: If a sum of a total length of packets that are of the first flow and that are currently enqueued in a 1.sup.st queue following the first queue and a length of the first packet is less than or equal to the first threshold, the packet marking apparatus determines that the enqueuing queue of the first packet is the 1.sup.st queue following the first queue.

[0153] If a sum of a total length of packets that are of the first flow and that are currently enqueued in a 1.sup.st queue following the first queue and a length of the first packet is greater than a first threshold, the packet marking apparatus determines that the enqueuing queue of the first packet is a K.sup.th queue following the first queue in the queues that the first packet can enqueue, where K is a positive integer greater than 1, and a sum of a total length of currently enqueued packets in the K.sup.th queue and the length of the first packet is less than the first threshold.

[0154] Specifically, in this manner, the enqueuing queue of the first packet starts from the 1.sup.st queue following the first queue. As shown in FIG. 5, queues Q.sub.9, Q.sub.0, Q.sub.1, Q.sub.2, Q.sub.3, Q.sub.4, Q.sub.5, and Q.sub.6 that the first packet can enqueue are used as an example. Q.sub.9, Q.sub.0, Q.sub.1, Q.sub.2, Q.sub.3, Q.sub.4, Q.sub.5, and Q.sub.6 are queues following the first queue. A queue in which a sum of a total length of currently enqueued packets and the length of the first packet is less than the first threshold may be sequentially determined starting from Q.sub.9. If the first packet still fails to be enqueued after the first packet attempts to enqueue Q.sub.6, the first packet continues to be enqueued cyclically starting from Q.sub.9.

[0155] That the packet marking apparatus determines that the enqueuing queue of the first packet is a K.sup.th queue following the first queue in the queues that the first packet can enqueue may be:

[0156] The packet marking apparatus determines, starting from a 2.sup.nd queue following the first queue, from the queues that the first packet can enqueue, a 1.sup.st queue in which a sum of a total length of currently enqueued packets of the first flow and the length of the first packet is less than or equal to the first threshold, and determines, as the K.sup.th queue, the 1.sup.st queue in which the sum of the total length of the currently enqueued packets of the first flow and the length of the first packet is less than or equal to the first threshold.

[0157] S103: The packet marking apparatus marks a queue identifier of the first packet as a queue identifier of the enqueuing queue of the first packet, and then sends the queue identifier of the enqueuing queue of the first packet to the packet output apparatus.

[0158] S104: The packet output apparatus sends, based on the queue identifier of the first packet, the first packet to a corresponding queue for outputting.

[0159] Specifically, the packet output apparatus receives the first packet, where the first packet carries a queue identifier, and the queue identifier is the queue identifier of the enqueuing queue of the first packet.

[0160] After the packet marking apparatus determines the enqueuing queue of the first packet in S102, for example, determines that the enqueuing queue of the first packet is Q.sub.2, the packet marking apparatus sends a queue identifier 2 of the enqueuing queue Q.sub.2 of the first packet to the packet output apparatus. The packet output apparatus sends, based on the queue identifier of the first packet, the first packet to a corresponding queue for outputting.

[0161] Further, in a possible implementation, after the packet marking apparatus marks the queue identifier of the enqueuing queue of the first packet and sends the first packet to the packet output apparatus in S103, the method may further include:

[0162] S105: The packet marking apparatus adds the length of the first packet to B.sub.add.

[0163] FIG. 11 is a schematic diagram of determining the enqueuing queue of the first packet according to an embodiment of this application. As shown in FIG. 11, the enqueuing queue of the first packet is Q.sub.2, and if B is greater than 3B.sub.i×T, the length of the first packet is added to B.sub.add.

[0164] S106: The packet marking apparatus subtracts a first threshold from B.sub.add when determining that a 1.sup.st queue that the first packet can enqueue is different from a 1.sup.st queue that a previous packet of the first packet can enqueue.

[0165] Specifically, the 1.sup.st enqueuing queue of the first packet is a 1.sup.st queue in the enqueuing queue of the first packet. For example, as shown in FIG. 5, the queues Q.sub.9, Q.sub.0, Q.sub.1, Q.sub.2, Q.sub.3, Q.sub.4, Q.sub.5, and Q.sub.6 that the first packet can enqueue are used as an example, and the 1.sup.st queue in the enqueuing queue of the first packet is Q.sub.9.

[0166] S107: When determining that B.sub.add is less than the first threshold, the packet marking apparatus sets B.sub.add to 0.

[0167] It should be noted that, there is no execution sequence of S105 to S107.

[0168] According to the traffic shaping method provided in this embodiment, after receiving the first packet, the packet marking apparatus determines the enqueuing queue of the first packet, marks the queue identifier of the first packet as the queue identifier of the enqueuing queue of the first packet, and then sends the queue identifier of the first packet to the packet output apparatus; and the packet output apparatus sends, based on the queue identifier of the first packet, the first packet to the corresponding queue for outputting. Packets are output from different queues, and enabling time of different queues is known. Therefore, packet output time is fixed, to implement that the packet output time is fixed.

[0169] The following describes in detail the technical solution in the method embodiment shown in FIG. 2 by using a specific embodiment.

[0170] FIG. 12 is a flowchart of an embodiment of a traffic shaping method according to this application. As shown in FIG. 9, the method in this embodiment may include the following steps.

[0171] S201: A packet marking apparatus receives a first packet.

[0172] S202: The packet marking apparatus determines, based on an arrival moment of the first packet, queues that the first packet can enqueue.

[0173] In an implementation, the packet marking apparatus may determine, based on the arrival moment to of the first packet, maximum transmission duration t.sub.max required for sending a packet from the packet marking apparatus to a packet output apparatus, and minimum transmission duration t.sub.min required for sending the packet from the packet marking apparatus to the packet output apparatus, the queues that the first packet can enqueue.

[0174] Specifically, the queues that the first packet can enqueue may be determined based on a first queue in an enabled state at a moment t.sub.1=t.sub.0+t.sub.max and a second queue in the enabled state at a moment t.sub.1′=t.sub.0+t.sub.min. If the first queue and the second queue are a same queue, the packet marking apparatus determines that the queues that the first packet can enqueue are N−1 queues in a group of gating queues other than the first queue. If the first queue and the second queue are two adjacent queues, the packet marking apparatus determines that the queues that the first packet can enqueue are N−2 queues in the group of gating queues other than the first queue and the second queue. If there are J queues between the first queue and the second queue, the packet marking apparatus determines that the queues that the first packet can enqueue are N−J−2 queues in the group of gating queues other than the first queue, the second queue, and the J queues between the first queue and the second queue.

[0175] S203: The packet marking apparatus determines whether a total length B.sub.add of unoutput packets of the first flow in the queues that the first packet can enqueue is less than a maximum buffer size B of the first flow in the queues that the first packet can enqueue, where the first flow is a flow to which the first packet belongs.

[0176] If B.sub.add is less than B, S204 is performed, or if B.sub.add is greater than or equal to B, the first packet is discarded.

[0177] Specifically, B is the maximum buffer size of the first flow in a currently enqueueable queue. When the enqueuing queue of the first packet is determined, it is necessary to first determine whether a total length B.sub.add of unoutput packets of the first flow in the currently enqueueable queue is less than B. If the total length B.sub.add of the unoutput packets of the first flow in the currently enqueueable queue is greater than or equal to B, it indicates that the total length B.sub.add of the unoutput packets of the first flow in the currently enqueueable queue reaches or exceeds the maximum buffer size B of the first flow in the currently enqueueable queue. In this case, the first packet cannot enqueue. When the total length of the unoutput packets of the first flow in the currently enqueueable queue is less than or equal to B, queues that the first packet can enqueue are allocated.

[0178] In another possible implementation, S203 may be: The packet marking apparatus determines whether a sum of B.sub.add and the first packet is less than or equal to B. If B.sub.add is less than B, S204 is performed, or if B.sub.add is greater than or equal to B, the first packet is discarded.

[0179] S204: The packet marking apparatus determines, based on B.sub.add and a first threshold, the enqueuing queue of the first packet from the queues that the first packet can enqueue.

[0180] Specifically, the packet marking apparatus determines, based on B.sub.add and the first threshold, the enqueuing queue of the first packet from the queues that the first packet can enqueue in the following three implementations. For details, refer to related descriptions in the embodiment shown in FIG. 2. Details are not described herein again.

[0181] S205: The packet marking apparatus marks a queue identifier of the first packet as a queue identifier of the enqueuing queue of the first packet, and then sends the queue identifier of the enqueuing queue of the first packet to the packet output apparatus.

[0182] S206: The packet output apparatus sends, based on the queue identifier of the first packet, the first packet to a corresponding queue for outputting.

[0183] FIG. 13 is a schematic diagram of a process in which a packet is sent to a packet output apparatus after the packet is processed by a packet marking apparatus. As shown in FIG. 13, the packet marking apparatus processes packets flow by flow. For example, a plurality of packets shown in FIG. 13 are received, and receiving moments of the plurality of packets may be the same or different. For a 1.sup.st packet, the packet marking apparatus discards the 1.sup.st packet when determining that a total length B.sub.add of unoutput packets of a first flow in queues that the first packet can enqueue is less than or equal to a maximum buffer size B of the first flow in the queues that the first packet can enqueue, where the first flow is a flow to which the first packet belongs. When determining that B.sub.add is less than B, the packet marking apparatus determines, by performing S204, a queue that a 1.sup.st packet can enqueue, and then marks a corresponding queue identifier of the queue and sends the queue identifier to the packet output apparatus. Then, a 2.sup.nd packet is also processed in the same way, and the packet output apparatus marks a corresponding identifier and sends the queue identifier to the packet output apparatus. For example, as shown in FIG. 13, a first part of the packets enqueue a queue 1, and a second part of the packets enqueue a queue 2. The packet output apparatus sends each packet to a corresponding queue based on an identifier of each packet, and outputs the packet when a queue is enabled.

[0184] According to the traffic shaping method provided in this application, a packet can be output within determined time. For example, FIG. 14 is a schematic diagram of outputting a packet within the determined time. A first packet arrives at a current network device at a moment t.sub.0, that is, the first packet arrives at a packet marking apparatus at the moment t.sub.0. A moment at which the first packet may arrive at a packet output apparatus is a value between t.sub.1′ and t.sub.1, where t.sub.1=t.sub.0+t.sub.max, and t.sub.1′=t.sub.0+t.sub.min. A queue in an enabled state at the moment t.sub.1 is a first queue. It is assumed that start time of a 1.sup.st queue following the first queue is t.sub.2. The first packet may be controlled to be output between t.sub.2 and t.sub.2m×T by using the traffic shaping method provided in this embodiment, where m is greater than or equal to 1. For example, if the first packet is controlled to be output between t.sub.2 and t.sub.2+T, and a queue enabled at the moment t.sub.2+T is queue 4, after marking the first packet with a queue identifier 4, the packet marking apparatus sends the first packet to the packet output apparatus, the packet output apparatus sends the first packet to the queue 4, and the queue 4 is enabled at the moment t.sub.2+T and disabled at the moment t.sub.2+2T. In this way, a packet is output within determined time.

[0185] After S205, the method in this embodiment may further include the following steps.

[0186] S207: The packet marking apparatus adds a length of the first packet to B.sub.add.

[0187] S208: The packet marking apparatus subtracts a first threshold from B.sub.add when determining that a 1.sup.st queue that the first packet can enqueue is different from a 1.sup.st queue that a previous packet of the first packet can enqueue.

[0188] FIG. 15 is a schematic diagram of a structure of an embodiment of a traffic shaping apparatus according to this application. As shown in FIG. 15, the apparatus in this embodiment may include a receiving module 11, a determining module 12, and a sending module 13.

[0189] The receiving module 11 is configured to receive a first packet.

[0190] The determining module 12 is configured to determine an enqueuing queue of the first packet.

[0191] The sending module 13 is configured to: mark a queue identifier of the first packet as a queue identifier of the enqueuing queue of the first packet, and then send the queue identifier of the first packet to a packet output apparatus, where the packet output apparatus is configured to send, based on the queue identifier of the first packet, the first packet to a corresponding queue for outputting.

[0192] The apparatus in this embodiment may be configured to perform the technical solution in the method embodiment shown in FIG. 2. Implementation principles and technical effects of the apparatus are similar. Details are not described herein again.

[0193] FIG. 16 is a schematic diagram of a structure of an embodiment of a traffic shaping apparatus according to this application. As shown in FIG. 16, the apparatus in this embodiment is based on the apparatus shown in FIG. 15. Further, the determining module 12 includes a determining unit 121 and a processing unit 122.

[0194] The determining unit 121 is configured to determine, based on an arrival moment of the first packet, queues that the first packet can enqueue.

[0195] The processing unit 122 is configured to determine the enqueuing queue of the first packet from the queues that the first packet can enqueue, where the enqueuing queue is one queue in a group of gating queues, the group of gating queues include N queues, duration in which each queue in the N queues is continuously enabled is T, and the N queues are cyclically enabled in a preset order. A total length of packets that can be enqueued in each flow i and each queue in the N queues is less than or equal to a first threshold, or a total length of packets that can be enqueued in each flow i and each queue in the N queues is less than or equal to a sum of a first threshold and a maximum packet length of the flow i, where N is a positive integer greater than 1, and i is a positive integer.

[0196] Optionally, the determining unit 121 is configured to: [0197] determine, based on the arrival moment of the first packet, maximum transmission duration t.sub.max required for sending the packet from the packet marking apparatus to the packet output apparatus, and minimum transmission duration twin required for sending the packet from the packet marking apparatus to the packet output apparatus, the queues that the first packet can enqueue.

[0198] Optionally, the determining unit 121 is configured to: [0199] calculate, based on the arrival moment t.sub.0 of the first packet and t.sub.max, a latest moment t.sub.1=t.sub.0+t.sub.max at which the first packet arrives at the packet output apparatus, and calculate, based on the arrival moment to of the first packet and t.sub.min, an earliest moment t.sub.1′=t+t.sub.min at which the first packet arrives at the packet output apparatus; and [0200] determine, based on a first queue in an enabled state at the moment t.sub.1 and a second queue in the enabled state at the moment t.sub.1′, the queues that the first packet can enqueue.

[0201] Optionally, the determining unit 121 is configured to: if the first queue and the second queue are a same queue, determine that the queues that the first packet can enqueue are N−1 queues in the group of gating queues other than the first queue; [0202] if the first queue and the second queue are two adjacent queues, determine that the queues that the first packet can enqueue are N−2 queues in the group of gating queues other than the first queue and the second queue; or [0203] if there are J queues between the first queue and the second queue, determine that the queues that the first packet can enqueue are N−J−2 queues in the group of gating queues other than the first queue, the second queue, and the J queues between the first queue and the second queue.

[0204] Optionally, the processing unit 122 is configured to: determine that a total length B.sub.add of unoutput packets of the first flow in the queues that the first packet can enqueue is less than a maximum buffer size B of the first flow in the queues that the first packet can enqueue, where the first flow is a flow to which the first packet belongs; or determine that a sum of B.sub.add and the first packet is less than or equal to B, and determine, based on B.sub.add and the first threshold, the enqueuing queue of the first packet from the queues that the first packet can enqueue.

[0205] Optionally, the processing unit 122 is configured to: if B.sub.add is greater than or equal to M−1 times the first threshold and less than M times the first threshold, determine that the enqueuing queue of the first packet is an M.sup.th queue following the first queue in the queues that the first packet can enqueue, where M is a positive integer greater than or equal to 1.

[0206] Optionally, the processing unit 122 is configured to: [0207] if a total length of packets that are of the first flow and that are currently enqueued in a 1.sup.st queue following the first queue is less than the first threshold, determine that the enqueuing queue of the first packet is the 1.sup.st queue following the first queue; or if a total length of packets that are of the first flow and that are currently enqueued in a 1.sup.st queue following the first queue is greater than or equal to the first threshold, determine that the enqueuing queue of the first packet is a K.sup.th queue following the first queue in the queues that the first packet can enqueue, where K is a positive integer greater than or equal to 2; and a total length of currently enqueued packets in the K.sup.th queue is less than the first threshold.

[0208] Optionally, the processing unit 122 is specifically configured to: [0209] determine, starting from a 2.sup.nd queue following the first queue, from the queues that the first packet can enqueue, a 1.sup.st queue in which the total length of currently enqueued packets of the first flow is less than the first threshold; and determine, as the K.sup.th queue, the 1.sup.st queue in which the total length of the currently enqueued packets of the first flow is less than the first threshold.

[0210] Optionally, the processing unit 122 is configured to: [0211] if a sum of a total length of packets that are of the first flow and that are currently enqueued in a 1.sup.st queue following the first queue and a length of the first packet is less than or equal to the first threshold, determine that the enqueuing queue of the first packet is the 1.sup.st queue following the first queue; or if a sum of a total length of packets that are of the first flow and that are currently enqueued in a 1.sup.st queue following the first queue and a length of the first packet is greater than the first threshold, determine that the enqueuing queue of the first packet is an M.sup.th queue following the first queue in the queues that the first packet can enqueue, where M is a positive integer greater than 1, and a sum of a total length of currently enqueued packets in the M.sup.th queue and the length of the first packet is less than the first threshold.

[0212] Optionally, the processing unit 122 is specifically configured to: [0213] determine, starting from a 2.sup.nd queue following the first queue, from the queues that the first packet can enqueue, a 1.sup.st queue in which a sum of a total length of currently enqueued packets of the first flow and the length of the first packet is less than or equal to the first threshold; and determine, as an M.sup.th queue, a 1.sup.st queue in which a sum of a total length of currently enqueued packets of the first flow and the length of the first packet is less than or equal to the first threshold.

[0214] Further, the processing unit 122 is further configured to: [0215] determine that B.sub.add is greater than or equal to B; or determine that the sum of B.sub.add and the first packet is greater than B, and discard the first packet.

[0216] Further, the processing unit 122 is further configured to: after the queue identifier of the first packet is marked as the queue identifier of the enqueuing queue of the first packet, and the queue identifier of the enqueuing queue of the first packet is sent to the packet output apparatus, add the length of the first packet to B.sub.add; when determining that a 1.sup.st queue that the first packet can enqueue is different from a 1.sup.st queue that a previous packet of the first packet can enqueue, subtract the first threshold from B.sub.add; and when determining that B.sub.add is less than the first threshold, set B.sub.add to 0.

[0217] Optionally, the first threshold is B.sub.i×T, and B.sub.i is a bandwidth of the first flow.

[0218] The apparatus in this embodiment may be configured to perform the technical solutions in the foregoing method embodiment. Implementation principles and technical effects of the apparatus are similar. Details are not described herein again.

[0219] FIG. 17 is a schematic diagram of a structure of an embodiment of a traffic shaping apparatus according to this application. As shown in FIG. 17, the apparatus in this embodiment may include a receiving module 21 and a processing module 22.

[0220] The receiving module 21 is configured to receive a first packet, where the first packet carries a queue identifier, and the queue identifier is a queue identifier of an enqueuing queue of the first packet.

[0221] The processing module 22 is configured to send, based on the queue identifier of the first packet, the first packet to a corresponding queue for outputting.

[0222] Optionally, the enqueuing queue of the first packet is one queue in a group of gating queues, the group of gating queues include N queues, duration in which each queue in the N queues is continuously enabled is T, and the N queues are cyclically enabled in a preset order. A total length of packets that can be enqueued in each flow i and each queue in the N queues is less than or equal to a first threshold, or a total length of packets that can be enqueued in each flow i and each queue in the N queues is less than or equal to a sum of a first threshold and a maximum packet length of the flow i, where N is a positive integer greater than 1, and i is a positive integer.

[0223] Optionally, the first threshold is B.sub.iT, B.sub.i is a bandwidth of a first flow, and the first flow is a flow to which the first packet belongs.

[0224] FIG. 18 is a schematic diagram of a structure of a traffic shaping apparatus according to this application. A flow i traffic shaping apparatus 100 includes: [0225] a memory 101 and a processor 102.

[0226] The memory 101 is configured to store a computer program.

[0227] The processor 102 is configured to execute the computer program stored in the memory, to implement the key agreement method in the foregoing embodiment. For details, refer to related descriptions in the foregoing method embodiment.

[0228] Optionally, the memory 101 may be independent, or may be integrated with the processor 102.

[0229] When the memory 101 is a component independent of the processor 102, the traffic shaping apparatus 100 may further include: [0230] a bus 103, configured to connect the memory 101 and the processor 102.

[0231] Optionally, this embodiment further includes a communication interface 104. The communication interface 104 may be connected to the processor 102 through the bus 103. The processor 102 may control the communication interface 104 to implement the foregoing obtaining function of the traffic shaping apparatus 100.

[0232] The apparatus may be configured to perform steps and/or procedures in the foregoing method embodiment.

[0233] This application further provides a readable storage medium. The readable storage medium stores executable instructions. When at least one processor of an electronic device executes the executable instructions, the electronic device performs the traffic shaping method in the foregoing method embodiment.

[0234] This application further provides a program product. The program product includes execution instructions, and the execution instructions are stored in a readable storage medium. At least one processor of an electronic device may read the executable instructions from the readable storage medium, and the at least one processor executes the executable instructions, so that the electronic device implements the traffic shaping method in the foregoing method embodiment.

[0235] This application further provides a chip. The chip is connected to a memory, or a memory is integrated on the chip. When a software program stored in the memory is executed, the traffic shaping method in the foregoing method embodiment is implemented.

[0236] A person of ordinary skill in the art may understand that all or some of the foregoing embodiments may be implemented by software, hardware, firmware, or any combination thereof. When software is used to implement the embodiments, all or a part of the embodiments may be implemented in a form of a computer program product. The computer program product includes one or more computer instructions. When the computer program instructions are loaded and executed on a computer, the procedures or functions according to embodiments of this application are all or partially generated. The computer may be a general-purpose computer, a dedicated computer, a computer network, or another programmable apparatus. The computer instructions may be stored in a computer-readable storage medium or may be transmitted from one computer-readable storage medium to another computer-readable storage medium. For example, the computer instructions may be transmitted from a website, computer, server, or data center to another website, computer, server, or data center in a wired (for example, a coaxial cable, an optical fiber, or a digital subscriber line (DSL)) or wireless (for example, infrared, radio, or microwave) manner. The computer-readable storage medium may be any usable medium accessible by the computer, or a data storage device, such as a server or a data center that integrates one or more usable media. The usable medium may be a magnetic medium (for example, a floppy disk, a hard disk, or a magnetic tape), an optical medium (for example, a DVD), a semi-conductor medium (for example, a solid-state drive Solid State Disk (SSD)), or the like.